diff options
Diffstat (limited to 'ldap/servers/plugins/replication/tests')
| -rw-r--r-- | ldap/servers/plugins/replication/tests/dnp_sim.c | 1033 | ||||
| -rw-r--r-- | ldap/servers/plugins/replication/tests/dnp_sim2.c | 972 | ||||
| -rw-r--r-- | ldap/servers/plugins/replication/tests/dnp_sim3.c | 1489 | ||||
| -rwxr-xr-x | ldap/servers/plugins/replication/tests/makesim | 58 |
4 files changed, 3552 insertions, 0 deletions
diff --git a/ldap/servers/plugins/replication/tests/dnp_sim.c b/ldap/servers/plugins/replication/tests/dnp_sim.c new file mode 100644 index 00000000..ff524988 --- /dev/null +++ b/ldap/servers/plugins/replication/tests/dnp_sim.c @@ -0,0 +1,1033 @@ +/** BEGIN COPYRIGHT BLOCK + * Copyright 2001 Sun Microsystems, Inc. + * Portions copyright 1999, 2001-2003 Netscape Communications Corporation. + * All rights reserved. + * END COPYRIGHT BLOCK **/ +/* dnp_simulation.c - this file varifies the correctness of dnp algorithm + by generating random sequences of operations, applying + the algorithm and outputing the result + + usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>] + -h - print usage information. + -n <number of simulations> - how many simulations to perform; default - 1. + -v - verbose mode (prints full entry state after each operation execution) + -f <output file> - file where results are stored; by default results are + printed to the screen. + -o <op file> - file that contains operation sequence to execute; by default, + random sequence is generated. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <errno.h> +#include <memory.h> +#include <string.h> +#include <time.h> + +#define MAX_OPS 12 /* maximum number of operations in a simulation */ +#define MAX_VALS 10 /* maximum number of values is entry or dn */ +#define NOT_PRESENT -1 + +/* data types */ +typedef struct value_state +{ + int value_index; /* value */ + int presense_csn; /* last time at which we know the value was present */ + int distinguished_csn; /* last time at which we know the value was distinguished */ + int delete_csn; /* last attempt to delete this value */ + int non_distinguished_csns [MAX_OPS];/* list of times at which value became non-distinguished */ + int present; /* flag that tells whether the value iscurrently present */ +} Value_State; + +typedef struct entry_state +{ + int dn_index; + int dn_csn; + Value_State values[MAX_VALS]; /* values of the attribute */ + int attr_delete_csn; /* last attempt to delete the entire attribute */ +} Entry_State; + +typedef enum +{ + OP_ADD_VALUE, + OP_RENAME_ENTRY, + OP_DELETE_VALUE, + OP_DELETE_ATTR, + OP_END +} Operation_Type; + +typedef struct operation +{ + Operation_Type type; /* operation type */ + int csn; /* operation type */ + int value_index; /* value to add, remove or rename from */ + int old_dn_index; /* new dn - rename only */ +}Operation; + +typedef struct simulator_params +{ + int runs; /* number of runs */ + FILE *fout; /* output file */ + int value_count; /* number of values */ + int verbose; /* verbose mode */ + Operation *ops; /* operation sequence to apply */ + int op_count; +}Simulator_Params; + + +/* gloabl data */ +Simulator_Params sim; +char *g_values[] = +{ + "v", + "u", + "w", + NULL +}; + +/* forward declarations */ + +/* initialization */ +void process_cmd (int argc, char **argv); +void set_default_sim_params (); +int count_values (); +void parse_operations_file (char *name); +void parse_operation (char *line, int pos); +int value2index (char *value); +void print_usage (); + +/* simulation run */ +void run_simulation (); +void generate_operations (Operation **ops, int *op_count); +void generate_operation (Operation *op, int csn, int *last_dn_index); +int* generate_operation_order (int op_count, int seq_num); +void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry); +void init_entry_state (Entry_State *entry); +void init_value_state (Value_State *val, int seq_num); +void apply_operation (Entry_State *entry, Operation *op); +void free_operations (Operation **ops); +int ** new_perm_table (int op_count); +void free_perm_table (int ***perm_table, int op_count); +int get_perm_count (int op_count); +void generate_perm_table (int *elements, int element_count, int static_part, + int **perm_table); +void apply_add_operation (Entry_State *entry, Operation *op); +void apply_value_delete_operation (Entry_State *entry, Operation *op); +void apply_attr_delete_operation (Entry_State *entry, Operation *op); +void apply_rename_operation (Entry_State *entry, Operation *op); +void make_value_distinguished (int op_csn, Entry_State *entry, int value_index); +void make_value_non_distinguished (int op_csn, Entry_State *entry, int value_index); +void purge_value_state (Value_State *value); +void purge_non_distinguished_csns (Value_State *value); +void resolve_value_state (Entry_State *entry, int value_index); +int value_distinguished_at_delete (Value_State *value, int attr_delete_csn); +int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run); + +/* data tracing */ +void dump_operations (Operation *ops, int op_count, int *order); +void dump_operation (Operation *op); +void dump_perm_table (int **perm_table, int op_count); +void dump_entry_state (Entry_State *entry); +void dump_value_state (Value_State *value); +void dump_list (int *list); + +/* misc functions */ +int max_val (int a, int b); +int is_list_empty (int *list); +int min_list_val (int *list); +int list_equal (int *list1, int *list2); + +int main (int argc, char **argv) +{ + int i; + + process_cmd (argc, argv); + + for (i = 0; i < sim.runs; i++) + { + fprintf (sim.fout, "*******running simulation #%d ...\n\n", i+1); + run_simulation (); + fprintf (sim.fout, "\n*******done with simulation #%d ...\n\n", i+1); + } + + if (sim.fout != stdout) + fclose (sim.fout); + + return 0; +} + +void process_cmd (int argc, char **argv) +{ + int i; + + set_default_sim_params (); + + if (argc == 1) + { + return; + } + + if (strcmp (argv[1], "-h") == 0) /* print help */ + { + print_usage (); + exit (0); + } + + i = 1; + while (i < argc) + { + if (strcmp (argv[i], "-v") == 0) /* verbose mode */ + { + sim.verbose = 1; + i ++; + } + else if (strcmp (argv[i], "-n") == 0) + { + if (i < argc - 1) + { + int runs = atoi (argv[i + 1]); + if (runs > 0) + sim.runs = runs; + i+=2; + } + else + { + /* ONREPL print warning */ + i++; + } + } + else if (strcmp (argv[i], "-f") == 0) /* output file */ + { + if (i < argc - 1) + { + FILE *f = fopen (argv[i + 1], "w"); + if (f == 0) + { + printf ("failed to open output file; error - %s, using stdout\n", + strerror(errno)); + } + else + { + /* ONREPL print warning */ + sim.fout = f; + } + + i += 2; + } + else + i++; + } + else if (strcmp (argv[i], "-o") == 0) /* file with operation sequence */ + { + if (i < argc - 1) + { + parse_operations_file (argv[i+1]); + i += 2; + } + else + { + /* ONREPL print warning */ + i ++; + } + } + else /* unknown option */ + { + printf ("unknown option - %s; ignored\n", argv[i]); + i ++; + } + + } +} + +void set_default_sim_params () +{ + memset (&sim, 0, sizeof (sim)); + sim.runs = 1; + sim.fout = stdout; + sim.value_count = count_values (); +} + +/* file format: <op count> + add <value> + delete <value> + delete attribute + rename <value> to <value> + */ +void parse_operations_file (char *name) +{ + FILE *file = fopen (name, "r"); + char line [256]; + int i; + + if (file == NULL) + { + printf ("failed to open operations file %s: error = %d\n", name, errno); + print_usage (); + exit (1); + } + + i = 0; + while (fgets (line, sizeof (line), file)) + { + if (i == 0) + { + /* read operation count */ + sim.op_count = atoi (line); + if (sim.op_count < 1 || sim.op_count > MAX_OPS/2) + { + printf ("invalid operation count - %d; value must be between 1 and %d\n", + sim.op_count, MAX_OPS/2); + print_usage (); + exit (1); + } + else + { + sim.ops = (Operation*)malloc (sim.op_count * sizeof (Operation)); + } + } + else + { + if (strlen (line) == 0) /* skip empty lines */ + continue; + parse_operation (line, i); + } + + i ++; + } + +} + +void parse_operation (char *line, int i) +{ + sim.ops [i - 1].csn = i; + + if (line[strlen(line) - 1] == '\n') + line[strlen(line) - 1] = '\0'; + + if (strncmp (line, "add", 3) == 0) + { + sim.ops [i - 1].type = OP_ADD_VALUE; + sim.ops [i - 1].value_index = value2index (&line[4]); + } + else if (strncmp (line, "delete attribute", 16) == 0) + { + sim.ops [i - 1].type = OP_DELETE_ATTR; + } + else if (strncmp (line, "delete", 6) == 0) + { + sim.ops [i - 1].type = OP_DELETE_VALUE; + sim.ops [i - 1].value_index = value2index (&line[7]); + } + else if (strncmp (line, "rename", 6) == 0) + { + char *tok; + sim.ops [i - 1].type = OP_RENAME_ENTRY; + /* strtok() is not MT safe, but it is okay to call here because this is a program test */ + tok = strtok (&line[7], " "); + sim.ops [i - 1].old_dn_index = value2index (tok); + /* skip to */ + tok = strtok (NULL, " "); + tok = strtok (NULL, " "); + sim.ops [i - 1].value_index = value2index (tok); + } + else + { + /* invalid line */ + printf ("invalid operation: %s\n", line); + exit (1); + } +} + +int value2index (char *value) +{ + int i; + + for (i = 0; i < sim.value_count; i++) + { + if (strcmp (g_values[i], value) == 0) + return i; + } + + return -1; +} + +void print_usage () +{ + printf ("usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>]\n" + "\t-h - print usage information\n" + "\t-n <number of simulations>; default - 1\n" + "\t-v - verbose mode\n" + "\t-f <output file> - by default, results are printed to the screen\n" + "\t-o <op file> - file that contains operation sequence to execute;\n" + "\tby default, random sequence is generated.\n"); +} + +int count_values () +{ + int i; + + for (i = 0; g_values[i]; i++); + + return i; +} + +void run_simulation () +{ + int *order; + int i; + int perm_count; + Entry_State entry_first, entry_current; + int error = 0; + + init_entry_state (&entry_first); + fprintf (sim.fout, "initial entry state :\n"); + dump_entry_state (&entry_first); + + if (sim.ops == NULL) + { + generate_operations (&sim.ops, &sim.op_count); + } + fprintf (sim.fout, "initial operation set:\n"); + dump_operations (sim.ops, sim.op_count, NULL/* order */); + + perm_count = get_perm_count (sim.op_count); + for (i = 0; i < perm_count; i++) + { + fprintf (sim.fout, "--------------------------------\n"); + fprintf (sim.fout, "simulation run %d\n", i + 1); + fprintf (sim.fout, "--------------------------------\n"); + order = generate_operation_order (sim.op_count, i); + if (i == 0) + apply_operation_sequence (sim.ops, sim.op_count, order, &entry_first); + else + { + apply_operation_sequence (sim.ops, sim.op_count, order, &entry_current); + error |= compare_entry_state (&entry_first, &entry_current, i + 1); + } + } + + switch (error) + { + case 0: fprintf (sim.fout, "all runs left the entry in the same state\n"); + break; + case 1: fprintf (sim.fout, "while value presence is consistent across all runs, " + "the exact state does not match\n"); + break; + case 3: fprintf (sim.fout, "the runs left entries in an inconsistent state\n"); + break; + } + + free_operations (&sim.ops); +} + +void generate_operations (Operation **ops, int *op_count) +{ + int i; + int last_dn_index = 0; + + /* generate number operations in the sequence */ + *op_count = slapi_rand () % (MAX_OPS / 2) + 1; + *ops = (Operation *)malloc (*op_count * sizeof (Operation)); + + for (i = 0; i < *op_count; i ++) + { + generate_operation (&((*ops)[i]), i + 1, &last_dn_index); + } +} + +void generate_operation (Operation *op, int csn, int *last_dn_index) +{ + /* generate operation type */ + op->type = slapi_rand () % OP_END; + + /* generate value to which operation applies */ + op->value_index = slapi_rand () % sim.value_count; + + op->csn = csn; + + /* generate new distinguished value */ + if (op->type == OP_RENAME_ENTRY) + { + op->old_dn_index = *last_dn_index; + while (op->value_index == op->old_dn_index) + op->value_index = slapi_rand () % sim.value_count; + *last_dn_index = op->value_index; + } +} + +int* generate_operation_order (int op_count, int seq_num) +{ + static int **perm_table = NULL; + + /* first request - generate pemutation table */ + if (seq_num == 0) + { + int elements [MAX_OPS]; + int i; + + if (perm_table) + free_perm_table (&perm_table, op_count); + perm_table = new_perm_table (op_count); + + for (i = 0; i < op_count; i++) + elements [i] = i; + + generate_perm_table (elements, op_count, 0 /* static part */, + perm_table); + /* dump_perm_table (perm_table, op_count);*/ + } + + return perm_table [seq_num]; +} + +void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry) +{ + int i; + + init_entry_state (entry); + + if (!sim.verbose) + { + if (!sim.verbose) + { + fprintf (sim.fout, "operation_sequence for this run:\n"); + dump_operations (ops, op_count, order); + } + } + + for (i = 0; i < op_count; i++) + { + apply_operation (entry, &(ops [order[i]])); + } + + if (!sim.verbose) + { + fprintf (sim.fout, "final entry state :\n"); + dump_entry_state (entry); + } + +} + +void init_entry_state (Entry_State *entry) +{ + int i; + + memset (entry, 0, sizeof (*entry)); + entry->attr_delete_csn = NOT_PRESENT; + + for (i = 0; i < sim.value_count; i++) + { + init_value_state (&(entry->values[i]), i); + } +} + +void init_value_state (Value_State *val, int seq_num) +{ + memset (val, 0, sizeof (*val)); + val->value_index = seq_num; + val->present = 1; + val->delete_csn = NOT_PRESENT; + if (seq_num > 0) /* only first value is distinguished */ + val->distinguished_csn = -1; +} + +void apply_operation (Entry_State *entry, Operation *op) +{ + switch (op->type) + { + case OP_ADD_VALUE: apply_add_operation (entry, op); + break; + + case OP_DELETE_VALUE: apply_value_delete_operation (entry, op); + break; + + case OP_DELETE_ATTR: apply_attr_delete_operation (entry, op); + break; + + case OP_RENAME_ENTRY: apply_rename_operation (entry, op); + break; + } + + if (sim.verbose) + { + fprintf (sim.fout, "operation: "); + dump_operation (op); + fprintf (sim.fout, "\n"); + dump_entry_state (entry); + } +} + +void free_operations (Operation **ops) +{ + free (*ops); + *ops = NULL; +} + +int **new_perm_table (int op_count) +{ + int i; + int **perm_table; + int perm_count = get_perm_count (op_count); + + perm_table = (int**)malloc (perm_count * sizeof (int*)); + for (i = 0; i < perm_count; i ++) + perm_table [i] = (int*) malloc (op_count * sizeof (int)); + + return perm_table; +} + +void free_perm_table (int ***perm_table, int op_count) +{ + int i; + int perm_count = get_perm_count (op_count); + + for (i = 0; i < perm_count; i ++) + free ((*perm_table)[i]); + + free (*perm_table); + *perm_table = NULL; +} + +void generate_perm_table (int *elements, int element_count, int static_part, + int **perm_table) +{ + int i; + int elements_copy [MAX_OPS]; + int start_pos; + + if (element_count - 1 == static_part) + { + memcpy (*perm_table, elements, element_count * sizeof (int)); + return; + } + + start_pos = 0; + for (i = 0; i < element_count - static_part; i ++) + { + memcpy (elements_copy, elements, element_count * sizeof (int)); + elements_copy [static_part] = elements [static_part + i]; + elements_copy [static_part + i] = elements [static_part]; + generate_perm_table (elements_copy, element_count, static_part + 1, + &perm_table [start_pos]); + start_pos += get_perm_count (element_count - static_part - 1); + } +} + +int get_perm_count (int op_count) +{ + int i; + int perm_count = 1; + + for (i = 2; i <= op_count; i ++) + perm_count *= i; + + return perm_count; +} + +void apply_add_operation (Entry_State *entry, Operation *op) +{ + if (entry->values[op->value_index].presense_csn < op->csn) + { + entry->values[op->value_index].presense_csn = op->csn; + entry->values[op->value_index].present = 1; + resolve_value_state (entry, op->value_index); + } +} + +void apply_value_delete_operation (Entry_State *entry, Operation *op) +{ + if (entry->values[op->value_index].delete_csn < op->csn) + { + entry->values[op->value_index].delete_csn = op->csn; + resolve_value_state (entry, op->value_index); + } +} + +void apply_attr_delete_operation (Entry_State *entry, Operation *op) +{ + int i; + + if (entry->attr_delete_csn < op->csn) + { + entry->attr_delete_csn = op->csn; + + for (i = 0; i < sim.value_count; i++) + { + resolve_value_state (entry, i); + } + } +} + +void apply_rename_operation (Entry_State *entry, Operation *op) +{ + if (entry->dn_csn < op->csn) + { + entry->dn_index = op->value_index; + entry->dn_csn = op->csn; + } + + make_value_non_distinguished (op->csn, entry, op->old_dn_index); + make_value_distinguished (op->csn, entry, op->value_index); +} + +void make_value_distinguished (int op_csn, Entry_State *entry, int value_index) +{ + Value_State *value = &(entry->values[value_index]); + + if (value->distinguished_csn < op_csn) + { + value->distinguished_csn = op_csn; + + if (value->presense_csn < op_csn) + { + value->present = 1; + value->presense_csn = op_csn; + } + + resolve_value_state (entry, value_index); + } +} + +void make_value_non_distinguished (int op_csn, Entry_State *entry, int value_index) +{ + int i = 0; + int index; + Value_State *value = &(entry->values[value_index]); + + if (op_csn < value->distinguished_csn) + return; + + /* insert into sorted list */ + while (value->non_distinguished_csns[i] && value->non_distinguished_csns[i] < op_csn) + i++; + + if (value->non_distinguished_csns[i] == 0) + value->non_distinguished_csns[i] = op_csn; + else + { + index = i; + + while (value->non_distinguished_csns[i]) + i++; + + memcpy (&(value->non_distinguished_csns[index + 1]), + &(value->non_distinguished_csns[index]), (i - index) * sizeof (int)); + + value->non_distinguished_csns[index] = op_csn; + } + + resolve_value_state (entry, value_index); +} + +void purge_value_state (Value_State *value) +{ + /* value state information can be purged once a value was + readed/made distinguished because at that point we know that the value + existed/was distinguished */ + + purge_non_distinguished_csns (value); + + if (value->delete_csn < max_val (value->distinguished_csn, value->presense_csn)) + value->delete_csn = NOT_PRESENT; +} + +void purge_non_distinguished_csns (Value_State *value) +{ + int i = 0; + int index; + + while (value->non_distinguished_csns[i] && + value->non_distinguished_csns[i] < value->distinguished_csn) + i ++; + + if (i > 0) + { + index = i-1; + while (value->non_distinguished_csns[i]) + i ++; + + if (i > index + 1) + { + memcpy (value->non_distinguished_csns, &value->non_distinguished_csns[index+1], + (i - index - 1) * sizeof (int)); + memset (&(value->non_distinguished_csns[index+1]), 0, sizeof (int) * (i - index - 1)); + } + else + { + memset (value->non_distinguished_csns, 0, sizeof (int) * i); + } + } +} + +int is_list_empty (int *list) +{ + return (list[0] == 0); +} + +int min_list_val (int *list) +{ + return (list [0]); +} + +void resolve_value_state (Entry_State *entry, int value_index) +{ + Value_State *value = &(entry->values[value_index]); + + purge_value_state (value); + + /* no deletes that effect the state */ + if (max_val (value->delete_csn, entry->attr_delete_csn) < + max_val (value->distinguished_csn, value->presense_csn)) + return; + + if (value->present) /* check if it should be removed based on the current state */ + { + if (!value_distinguished_at_delete (value, entry->attr_delete_csn)) + { + /* note that we keep presence csn because we might have to restore + the value in the future */ + value->present = 0; + } + } + else /* not present - check if it should be restored */ + { + if (value_distinguished_at_delete (value, entry->attr_delete_csn)) + { + value->present = 1; + } + } +} + +/* Note we can't trim distinguished_csn (even during regular trimming) + because in some cases we would not be able to figure out whether + a value was distinguished or not at the time of deletion. + + Example 1: Example2: + csn order operation csn order operation + 1 1 make V distinguished 1 1 make V distinguished + 3 3 delete V 2 2 make V non distinguished + 4 2 make V non-distinguished 3 4 delete V + 4 3 make V non distinguished (on another server) + + if the csns up to 2 were triimed, when delete operation is received, the state + is exactly the same in both examples but in example one delete should not go + through while in example 2 it should + + */ +int value_distinguished_at_delete (Value_State *value, int attr_delete_csn) +{ + if (value->distinguished_csn >= 0 && + (is_list_empty (value->non_distinguished_csns) || + min_list_val (value->non_distinguished_csns) > + max_val (value->delete_csn, attr_delete_csn))) + return 1; + else + return 0; +} + +int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run) +{ + int j; + int error = 0; + + /* first - quick check for present / not present */ + for (j = 0; j < sim.value_count; j++) + { + if (entry1->values[j].present != entry2->values[j].present) + { + fprintf (sim.fout, + "value %s is %s present in the first run but %s present in the %d run\n", + g_values[j], entry1->values[j].present ? "" : "not", + entry2->values[j].present ? "" : "not", run); + error = 1; + } + } + + if (error) + return 3; + + /* compare value state */ + error = 0; + if (entry1->attr_delete_csn != entry2->attr_delete_csn) + { + fprintf (sim.fout, "attribute delete csn is %d for run 1 " + "but is %d for run %d\n", entry1->attr_delete_csn, + entry2->attr_delete_csn, run); + error = 1; + } + + for (j = 0; j < sim.value_count; j++) + { + if (entry1->values[j].presense_csn != entry2->values[j].presense_csn) + { + fprintf (sim.fout, "presence csn for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[j], entry1->values[j].presense_csn, + entry2->values[j].presense_csn, run); + error = 1; + } + + if (entry1->values[j].distinguished_csn != entry2->values[j].distinguished_csn) + { + fprintf (sim.fout, "distinguished csn for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[j], entry1->values[j].distinguished_csn, + entry2->values[j].distinguished_csn, run); + error = 1; + } + + if (entry1->values[j].delete_csn != entry2->values[j].delete_csn) + { + fprintf (sim.fout, "delete csn for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[j], entry1->values[j].delete_csn, + entry2->values[j].delete_csn, run); + error = 1; + } + + if (!list_equal (entry1->values[j].non_distinguished_csns, + entry2->values[j].non_distinguished_csns)) + { + fprintf (sim.fout, "pending list mismatch for valye %s in runs 1 and %d\n", + g_values[j], run); + dump_list (entry1->values[j].non_distinguished_csns); + dump_list (entry2->values[j].non_distinguished_csns); + } + } + + if (error != 0) + { + return 1; + } + else + return 0; +} + +void dump_operations (Operation *ops, int op_count, int *order) +{ + int index; + int i; + + for (i = 0; i < op_count; i ++) + { + if (order == NULL) /* current order */ + index = i; + else + index = order [i]; + + dump_operation (&ops[index]); + } + + fprintf (sim.fout, "\n"); +} + +void dump_operation (Operation *op) +{ + switch (op->type) + { + case OP_ADD_VALUE: + fprintf (sim.fout, "\t%d add value %s\n", op->csn, + g_values [op->value_index]); + break; + case OP_DELETE_VALUE: + fprintf (sim.fout, "\t%d delete value %s\n", op->csn, + g_values [op->value_index]); + break; + case OP_DELETE_ATTR: + fprintf (sim.fout, "\t%d delete attribute\n", op->csn); + break; + case OP_RENAME_ENTRY: + fprintf (sim.fout, "\t%d rename entry from %s to %s\n", op->csn, + g_values [op->old_dn_index], g_values [op->value_index]); + break; + } +} + +void dump_perm_table (int **perm_table, int op_count) +{ + int i, j; + int perm_count = get_perm_count (op_count); + + for (i = 0; i < op_count; i++) + { + for (j = 0; j < perm_count; j++) + { + fprintf (sim.fout, "%d ", perm_table [j][i]); + } + + fprintf (sim.fout, "\n"); + } +} + +void dump_entry_state (Entry_State *entry) +{ + int i; + fprintf (sim.fout, "\tentry dn: %s; dn csn - %d\n", + g_values [entry->dn_index], entry->dn_csn); + + if (sim.verbose) + fprintf (sim.fout, "\n"); + + for (i = 0; i < sim.value_count; i++) + { + dump_value_state (&(entry->values[i])); + } + + fprintf (sim.fout, "\n"); +} + +void dump_value_state (Value_State *value) +{ + fprintf (sim.fout, "\tvalue %s is %s\n", g_values[value->value_index], + value->present ? "present" : "not present"); + + if (sim.verbose) + { + fprintf (sim.fout, "\t\tpresent csn: %d\n", value->presense_csn); + fprintf (sim.fout, "\t\tdistinguished csn: %d\n", value->distinguished_csn); + fprintf (sim.fout, "\t\tdelete value csn: %d\n", value->delete_csn); + fprintf (sim.fout, "\t\tnon distinguished csns: "); + + dump_list (value->non_distinguished_csns); + + fprintf (sim.fout, "\n"); + } +} + +void dump_list (int *list) +{ + int i = 0; + + while (list[i]) + { + fprintf (sim.fout, "%d ", list[i]); + i ++; + } + + fprintf (sim.fout, "\n"); +} + +/* misc functions */ +int max_val (int a, int b) +{ + if (a >= b) + return a; + else + return b; +} + +int list_equal (int *list1, int *list2) +{ + int i; + + i = 0; + while (list1[i] && list2[i]) + { + if (list1[i] != list2[i]) + return 0; + + i ++; + } + + if (list1[i] != list2[i]) + return 0; + else + return 1; +} diff --git a/ldap/servers/plugins/replication/tests/dnp_sim2.c b/ldap/servers/plugins/replication/tests/dnp_sim2.c new file mode 100644 index 00000000..e1838aa6 --- /dev/null +++ b/ldap/servers/plugins/replication/tests/dnp_sim2.c @@ -0,0 +1,972 @@ +/** BEGIN COPYRIGHT BLOCK + * Copyright 2001 Sun Microsystems, Inc. + * Portions copyright 1999, 2001-2003 Netscape Communications Corporation. + * All rights reserved. + * END COPYRIGHT BLOCK **/ +/* dnp_simulation.c - this file varifies the correctness of dnp algorithm + by generating random sequences of operations, applying + the algorithm and outputing the result + + usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>] + -h - print usage information. + -n <number of simulations> - how many simulations to perform; default - 1. + -v - verbose mode (prints full entry state after each operation execution) + -f <output file> - file where results are stored; by default results are + printed to the screen. + -o <op file> - file that contains operation sequence to execute; by default, + random sequence is generated. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <errno.h> +#include <memory.h> +#include <string.h> +#include <time.h> +#include <windows.h> + +#define MAX_OPS 18 /* maximum number of operations in a simulation */ +#define MAX_VALS 10 /* maximum number of values is entry or dn */ +#define NOT_PRESENT -1 + +/* data types */ +typedef struct value_state +{ + int value_index; /* value */ + int presence_csn; /* last time at which we know the value was present */ + int distinguished_index; /* index into dncsn list */ + int delete_csn; /* last attempt to delete this value */ + int present; /* flag that tells whether the value iscurrently present */ +} Value_State; + +typedef struct dn_csn +{ + int csn; /* dn csn */ + int value_index; /* dn value */ +} Dn_Csn; + +typedef struct entry_state +{ + Dn_Csn dn_csns [MAX_VALS + 1]; /* list of dn csns for this entry */ + int dn_csn_count; /* csn of the current dn */ + Value_State values[MAX_VALS]; /* values of the attribute */ + int attr_delete_csn; /* last attempt to delete the entire attribute */ +} Entry_State; + +typedef enum +{ + OP_ADD_VALUE, + OP_DELETE_VALUE, + OP_RENAME_ENTRY, + OP_DELETE_ATTR, + OP_END +} Operation_Type; + +typedef struct operation +{ + Operation_Type type; /* operation type */ + int csn; /* operation type */ + int value_index; /* value to add, remove or rename from */ +}Operation; + +typedef struct simulator_params +{ + int runs; /* number of runs */ + FILE *fout; /* output file */ + int value_count; /* number of values */ + int verbose; /* verbose mode */ + Operation *ops; /* operation sequence to apply */ + int op_count; +}Simulator_Params; + + +/* gloabl data */ +Simulator_Params sim; +char *g_values[] = +{ + "v", + "u", + "w", + NULL +}; + +/* forward declarations */ + +/* initialization */ +void process_cmd (int argc, char **argv); +void set_default_sim_params (); +int count_values (); +void parse_operations_file (char *name); +void parse_operation (char *line, int pos); +int value2index (char *value); +void print_usage (); + +/* simulation run */ +void run_simulation (); +void generate_operations (Operation **ops, int *op_count); +void generate_operation (Operation *op, int csn); +int* generate_operation_order (int op_count, int seq_num); +void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry); +void init_entry_state (Entry_State *entry); +void init_value_state (Value_State *val, int seq_num); +void apply_operation (Entry_State *entry, Operation *op); +void free_operations (Operation **ops); +int ** new_perm_table (int op_count); +void free_perm_table (int ***perm_table, int op_count); +int get_perm_count (int op_count); +void generate_perm_table (int *elements, int element_count, int static_part, + int **perm_table); +void apply_add_operation (Entry_State *entry, Operation *op); +void apply_value_delete_operation (Entry_State *entry, Operation *op); +void apply_attr_delete_operation (Entry_State *entry, Operation *op); +void apply_rename_operation (Entry_State *entry, Operation *op); +void purge_value_state (Entry_State *entry, int index); +void resolve_value_state (Entry_State *entry, int value_index); +int value_distinguished_at_delete (Entry_State *entry, int value_index); +int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run); + +/* dnc_csn handling */ +int dn_csn_add (Entry_State *entry, int value_index, int csn); +int get_value_dn_csn (Entry_State *entry, int value_index); + +/* data tracing */ +void dump_operations (Operation *ops, int op_count, int *order); +void dump_operation (Operation *op); +void dump_perm_table (int **perm_table, int op_count); +void dump_entry_state (Entry_State *entry); +void dump_value_state (Value_State *value); +void dump_dn_csn_list (Entry_State *entry); + +/* misc functions */ +int max_val (int a, int b); + +int main (int argc, char **argv) +{ + int i; + + process_cmd (argc, argv); + + for (i = 0; i < sim.runs; i++) + { + fprintf (sim.fout, "*******running simulation #%d ...\n\n", i+1); + run_simulation (); + fprintf (sim.fout, "\n*******done with simulation #%d ...\n\n", i+1); + } + + if (sim.fout != stdout) + fclose (sim.fout); + + return 0; +} + +void process_cmd (int argc, char **argv) +{ + int i; + + set_default_sim_params (); + + if (argc == 1) + { + return; + } + + if (strcmp (argv[1], "-h") == 0) /* print help */ + { + print_usage (); + exit (0); + } + + i = 1; + while (i < argc) + { + if (strcmp (argv[i], "-v") == 0) /* verbose mode */ + { + sim.verbose = 1; + i ++; + } + else if (strcmp (argv[i], "-n") == 0) + { + if (i < argc - 1) + { + int runs = atoi (argv[i + 1]); + if (runs > 0) + sim.runs = runs; + i+=2; + } + else + { + /* ONREPL print warning */ + i++; + } + } + else if (strcmp (argv[i], "-f") == 0) /* output file */ + { + if (i < argc - 1) + { + FILE *f = fopen (argv[i + 1], "w"); + if (f == 0) + { + printf ("failed to open output file; error - %s, using stdout\n", + strerror(errno)); + } + else + { + /* ONREPL print warning */ + sim.fout = f; + } + + i += 2; + } + else + i++; + } + else if (strcmp (argv[i], "-o") == 0) /* file with operation sequence */ + { + if (i < argc - 1) + { + parse_operations_file (argv[i+1]); + i += 2; + } + else + { + /* ONREPL print warning */ + i ++; + } + } + else /* unknown option */ + { + printf ("unknown option - %s; ignored\n", argv[i]); + i ++; + } + + } +} + +void set_default_sim_params () +{ + memset (&sim, 0, sizeof (sim)); + sim.runs = 1; + sim.fout = stdout; + sim.value_count = count_values (); +} + +/* file format: <op count> + add <value> + delete <value> + delete attribute + rename to <value> + + all spaces are significant + */ +void parse_operations_file (char *name) +{ + FILE *file = fopen (name, "r"); + char line [256]; + int i; + + if (file == NULL) + { + printf ("failed to open operations file %s: error = %d\n", name, errno); + print_usage (); + exit (1); + } + + i = 0; + while (fgets (line, sizeof (line), file)) + { + if (i == 0) + { + /* read operation count */ + sim.op_count = atoi (line); + if (sim.op_count < 1 || sim.op_count > MAX_OPS/2) + { + printf ("invalid operation count - %d; value must be between 1 and %d\n", + sim.op_count, MAX_OPS/2); + print_usage (); + exit (1); + } + else + { + sim.ops = (Operation*)malloc (sim.op_count * sizeof (Operation)); + } + } + else + { + if (strlen (line) == 0) /* skip empty lines */ + continue; + parse_operation (line, i); + } + + i ++; + } +} + +void parse_operation (char *line, int i) +{ + sim.ops [i - 1].csn = i; + + if (line[strlen(line) - 1] == '\n') + line[strlen(line) - 1] = '\0'; + + if (strncmp (line, "add", 3) == 0) + { + sim.ops [i - 1].type = OP_ADD_VALUE; + sim.ops [i - 1].value_index = value2index (&line[4]); + } + else if (strncmp (line, "delete attribute", 16) == 0) + { + sim.ops [i - 1].type = OP_DELETE_ATTR; + } + else if (strncmp (line, "delete", 6) == 0) + { + sim.ops [i - 1].type = OP_DELETE_VALUE; + sim.ops [i - 1].value_index = value2index (&line[7]); + } + else if (strncmp (line, "rename to", 6) == 0) + { + sim.ops [i - 1].type = OP_RENAME_ENTRY; + sim.ops [i - 1].value_index = value2index (&line[10]); + } + else + { + /* invalid line */ + printf ("invalid operation: %s\n", line); + exit (1); + } +} + +int value2index (char *value) +{ + int i; + + for (i = 0; i < sim.value_count; i++) + { + if (strcmp (g_values[i], value) == 0) + return i; + } + + return -1; +} + +void print_usage () +{ + printf ("usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>]\n" + "\t-h - print usage information\n" + "\t-n <number of simulations>; default - 1\n" + "\t-v - verbose mode\n" + "\t-f <output file> - by default, results are printed to the screen\n" + "\t-o <op file> - file that contains operation sequence to execute;\n" + "\tby default, random sequence is generated.\n"); +} + +int count_values () +{ + int i; + + for (i = 0; g_values[i]; i++); + + return i; +} + +void run_simulation () +{ + int *order; + int i; + int perm_count; + Entry_State entry_first, entry_current; + int error = 0; + + init_entry_state (&entry_first); + fprintf (sim.fout, "initial entry state :\n"); + dump_entry_state (&entry_first); + + if (sim.ops == NULL) + { + generate_operations (&sim.ops, &sim.op_count); + } + fprintf (sim.fout, "initial operation set:\n"); + dump_operations (sim.ops, sim.op_count, NULL/* order */); + + //DebugBreak (); + + perm_count = get_perm_count (sim.op_count); + for (i = 0; i < perm_count; i++) + { + fprintf (sim.fout, "--------------------------------\n"); + fprintf (sim.fout, "simulation run %d\n", i + 1); + fprintf (sim.fout, "--------------------------------\n"); + order = generate_operation_order (sim.op_count, i); + if (i == 0) + apply_operation_sequence (sim.ops, sim.op_count, order, &entry_first); + else + { + apply_operation_sequence (sim.ops, sim.op_count, order, &entry_current); + error |= compare_entry_state (&entry_first, &entry_current, i + 1); + } + } + + switch (error) + { + case 0: fprintf (sim.fout, "all runs left the entry in the same state\n"); + break; + case 1: fprintf (sim.fout, "while value presence is consistent across all runs, " + "the exact state does not match\n"); + break; + case 3: fprintf (sim.fout, "the runs left entries in an inconsistent state\n"); + break; + } + + free_operations (&sim.ops); +} + +void generate_operations (Operation **ops, int *op_count) +{ + int i; + + /* generate number operations in the sequence */ + *op_count = slapi_rand () % (MAX_OPS / 2) + 1; + *ops = (Operation *)malloc (*op_count * sizeof (Operation)); + + for (i = 0; i < *op_count; i ++) + { + generate_operation (&((*ops)[i]), i + 1); + } +} + +void generate_operation (Operation *op, int csn) +{ + /* generate operation type */ + op->type = slapi_rand () % OP_END; + + /* generate value to which operation applies */ + op->value_index = slapi_rand () % sim.value_count; + + op->csn = csn; +} + +int* generate_operation_order (int op_count, int seq_num) +{ + static int **perm_table = NULL; + + /* first request - generate pemutation table */ + if (seq_num == 0) + { + int elements [MAX_OPS]; + int i; + + if (perm_table) + free_perm_table (&perm_table, op_count); + perm_table = new_perm_table (op_count); + + for (i = 0; i < op_count; i++) + elements [i] = i; + + generate_perm_table (elements, op_count, 0 /* static part */, + perm_table); + } + + return perm_table [seq_num]; +} + +void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry) +{ + int i; + + init_entry_state (entry); + + if (!sim.verbose) + { + if (!sim.verbose) + { + fprintf (sim.fout, "operation_sequence for this run:\n"); + dump_operations (ops, op_count, order); + } + } + + for (i = 0; i < op_count; i++) + { + apply_operation (entry, &(ops [order[i]])); + } + + if (!sim.verbose) + { + fprintf (sim.fout, "final entry state :\n"); + dump_entry_state (entry); + } + +} + +void init_entry_state (Entry_State *entry) +{ + int i; + + memset (entry, 0, sizeof (*entry)); + entry->attr_delete_csn = NOT_PRESENT; + entry->dn_csn_count = 1; + + for (i = 0; i < sim.value_count; i++) + { + init_value_state (&(entry->values[i]), i); + } +} + +void init_value_state (Value_State *val, int seq_num) +{ + memset (val, 0, sizeof (*val)); + val->value_index = seq_num; + val->present = 1; + val->delete_csn = NOT_PRESENT; + if (seq_num > 0) /* only first value is distinguished */ + val->distinguished_index = -1; +} + +void apply_operation (Entry_State *entry, Operation *op) +{ + switch (op->type) + { + case OP_ADD_VALUE: apply_add_operation (entry, op); + break; + + case OP_DELETE_VALUE: apply_value_delete_operation (entry, op); + break; + + case OP_DELETE_ATTR: apply_attr_delete_operation (entry, op); + break; + + case OP_RENAME_ENTRY: apply_rename_operation (entry, op); + break; + } + + if (sim.verbose) + { + fprintf (sim.fout, "operation: "); + dump_operation (op); + fprintf (sim.fout, "\n"); + dump_entry_state (entry); + } +} + +void free_operations (Operation **ops) +{ + free (*ops); + *ops = NULL; +} + +int **new_perm_table (int op_count) +{ + int i; + int **perm_table; + int perm_count = get_perm_count (op_count); + + perm_table = (int**)malloc (perm_count * sizeof (int*)); + for (i = 0; i < perm_count; i ++) + perm_table [i] = (int*) malloc (op_count * sizeof (int)); + + return perm_table; +} + +void free_perm_table (int ***perm_table, int op_count) +{ + int i; + int perm_count = get_perm_count (op_count); + + for (i = 0; i < perm_count; i ++) + free ((*perm_table)[i]); + + free (*perm_table); + *perm_table = NULL; +} + +void generate_perm_table (int *elements, int element_count, int static_part, + int **perm_table) +{ + int i; + int elements_copy [MAX_OPS]; + int start_pos; + + if (element_count - 1 == static_part) + { + memcpy (*perm_table, elements, element_count * sizeof (int)); + return; + } + + start_pos = 0; + for (i = 0; i < element_count - static_part; i ++) + { + memcpy (elements_copy, elements, element_count * sizeof (int)); + elements_copy [static_part] = elements [static_part + i]; + elements_copy [static_part + i] = elements [static_part]; + generate_perm_table (elements_copy, element_count, static_part + 1, + &perm_table [start_pos]); + start_pos += get_perm_count (element_count - static_part - 1); + } +} + +int get_perm_count (int op_count) +{ + int i; + int perm_count = 1; + + for (i = 2; i <= op_count; i ++) + perm_count *= i; + + return perm_count; +} + +void apply_add_operation (Entry_State *entry, Operation *op) +{ + if (entry->values[op->value_index].presence_csn < op->csn) + { + entry->values[op->value_index].presence_csn = op->csn; + resolve_value_state (entry, op->value_index); + } +} + +void apply_value_delete_operation (Entry_State *entry, Operation *op) +{ + if (entry->values[op->value_index].delete_csn < op->csn) + { + entry->values[op->value_index].delete_csn = op->csn; + resolve_value_state (entry, op->value_index); + } +} + +void apply_attr_delete_operation (Entry_State *entry, Operation *op) +{ + int i; + + if (entry->attr_delete_csn < op->csn) + { + entry->attr_delete_csn = op->csn; + + for (i = 0; i < sim.value_count; i++) + { + resolve_value_state (entry, i); + } + } +} + +void apply_rename_operation (Entry_State *entry, Operation *op) +{ + int index; + + if (entry->values[op->value_index].presence_csn == NOT_PRESENT) + entry->values[op->value_index].presence_csn = op->csn; + + index = dn_csn_add (entry, op->value_index, op->csn); + + if (index > 0) + resolve_value_state (entry, entry->dn_csns[index - 1].value_index); + + resolve_value_state (entry, entry->dn_csns[index].value_index); +} + +void purge_value_state (Entry_State *entry, int value_index) +{ + Value_State *value = &(entry->values[value_index]); + int value_distinguished_csn = get_value_dn_csn (entry, value_index); + + if (value_distinguished_csn == -1 && value->presence_csn > value->delete_csn) + value->delete_csn = NOT_PRESENT; + else if (value->delete_csn < max_val (value_distinguished_csn, value->presence_csn)) + value->delete_csn = NOT_PRESENT; +} + +void resolve_value_state (Entry_State *entry, int value_index) +{ + Value_State *value = &(entry->values[value_index]); + int value_distinguished_csn = get_value_dn_csn (entry, value_index); + + purge_value_state (entry, value_index); + + /* no deletes that effect the state */ + if (max_val (value->delete_csn, entry->attr_delete_csn) < + max_val (value_distinguished_csn, value->presence_csn)) + { + value->present = 1; + return; + } + + if (value->present) /* check if it should be removed based on the current state */ + { + if (!value_distinguished_at_delete (entry, value_index)) + { + value->present = 0; + } + } + else /* not present - check if it should be restored */ + { + if (value_distinguished_at_delete (entry, value_index)) + { + value->present = 1; + } + } +} + +int value_distinguished_at_delete (Entry_State *entry, int value_index) +{ + Value_State *value = &(entry->values[value_index]); + int value_distinguished_csn = get_value_dn_csn (entry, value_index); + int delete_csn; + int i; + + /* value has never been distinguished */ + if (value_distinguished_csn == -1) + return 0; + + delete_csn = max_val (entry->attr_delete_csn, value->delete_csn); + + for (i = 0; i < entry->dn_csn_count; i++) + { + if (entry->dn_csns[i].csn > delete_csn) + break; + } + + /* i is never equal to 0 because the csn of the first element is always + smaller than csn of any operation we can receive */ + return (entry->dn_csns[i-1].value_index == value_index); +} + +int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run) +{ + int i; + int error = 0; + + /* first - quick check for present / not present */ + for (i = 0; i < sim.value_count; i++) + { + if (entry1->values[i].present != entry2->values[i].present) + { + fprintf (sim.fout, + "value %s is %s present in the first run but %s present in the %d run\n", + g_values[i], entry1->values[i].present ? "" : "not", + entry2->values[i].present ? "" : "not", run); + error = 1; + } + } + + if (error) + return 3; + + /* compare dnc_csn list */ + if (entry1->dn_csn_count != entry2->dn_csn_count) + { + fprintf (sim.fout, "dn_csn count is %d for run 1 and %d for run %d\n", + entry1->dn_csn_count, entry2->dn_csn_count, run); + error = 1; + } + + for (i = 0; i < entry1->dn_csn_count; i++) + { + if (entry1->dn_csns [i].csn != entry2->dn_csns [i].csn || + entry1->dn_csns [i].value_index != entry2->dn_csns [i].value_index) + { + fprintf (sim.fout,"elements %d of dn csn list are different:\n" + "\tfirst run: csn - %d, value - %s\n" + "\t%d run: csn - %d, value - %s\n", i, + entry1->dn_csns [i].csn, + g_values[entry1->dn_csns [i].value_index], + run, entry2->dn_csns [i].csn, + g_values[entry2->dn_csns [i].value_index]); + + error = 1; + } + } + + /* compare value state */ + if (entry1->attr_delete_csn != entry2->attr_delete_csn) + { + fprintf (sim.fout, "attribute delete csn is %d for run 1 " + "but is %d for run %d\n", entry1->attr_delete_csn, + entry2->attr_delete_csn, run); + error = 1; + } + + for (i = 0; i < sim.value_count; i++) + { + if (entry1->values[i].presence_csn != entry2->values[i].presence_csn) + { + fprintf (sim.fout, "presence csn for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[i], entry1->values[i].presence_csn, + entry2->values[i].presence_csn, run); + error = 1; + } + + if (entry1->values[i].distinguished_index != entry2->values[i].distinguished_index) + { + fprintf (sim.fout, "distinguished index for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[i], + entry1->values[i].distinguished_index, + entry2->values[i].distinguished_index, run); + error = 1; + } + + if (entry1->values[i].delete_csn != entry2->values[i].delete_csn) + { + fprintf (sim.fout, "delete csn for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[i], entry1->values[i].delete_csn, + entry2->values[i].delete_csn, run); + error = 1; + } + } + + if (error != 0) + { + return 1; + } + else + return 0; +} + +int dn_csn_add (Entry_State *entry, int value_index, int csn) +{ + int i, j; + int distinguished_index; + + for (i = 0; i < entry->dn_csn_count; i++) + { + if (entry->dn_csns[i].csn > csn) + break; + } + + if (i < entry->dn_csn_count) + { + distinguished_index = i; + for (j = i; j < entry->dn_csn_count; j ++) + { + if (entry->dn_csns[j].value_index == value_index) + distinguished_index = j + 1; + + if (entry->values [entry->dn_csns[j].value_index].distinguished_index == j) + entry->values [entry->dn_csns[j].value_index].distinguished_index ++; + } + + memcpy (&(entry->dn_csns[i+1]), &(entry->dn_csns[i]), + (entry->dn_csn_count - i) * sizeof (Dn_Csn)); + } + else + { + distinguished_index = entry->dn_csn_count; + } + + entry->values[value_index].distinguished_index = distinguished_index; + entry->dn_csns[i].csn = csn; + entry->dn_csns[i].value_index = value_index; + entry->dn_csn_count ++; + + return i; +} + +int get_value_dn_csn (Entry_State *entry, int value_index) +{ + Value_State *value = &(entry->values [value_index]); + + if (value->distinguished_index == -1) + return -1; + else + return entry->dn_csns [value->distinguished_index].csn; +} + +void dump_operations (Operation *ops, int op_count, int *order) +{ + int index; + int i; + + for (i = 0; i < op_count; i ++) + { + if (order == NULL) /* current order */ + index = i; + else + index = order [i]; + + dump_operation (&ops[index]); + } + + fprintf (sim.fout, "\n"); +} + +void dump_operation (Operation *op) +{ + switch (op->type) + { + case OP_ADD_VALUE: + fprintf (sim.fout, "\t%d add value %s\n", op->csn, + g_values [op->value_index]); + break; + case OP_DELETE_VALUE: + fprintf (sim.fout, "\t%d delete value %s\n", op->csn, + g_values [op->value_index]); + break; + case OP_DELETE_ATTR: + fprintf (sim.fout, "\t%d delete attribute\n", op->csn); + break; + case OP_RENAME_ENTRY: + fprintf (sim.fout, "\t%d rename entry to %s\n", op->csn, + g_values [op->value_index]); + break; + } +} + +void dump_perm_table (int **perm_table, int op_count) +{ + int i, j; + int perm_count = get_perm_count (op_count); + + for (i = 0; i < op_count; i++) + { + for (j = 0; j < perm_count; j++) + { + fprintf (sim.fout, "%d ", perm_table [j][i]); + } + + fprintf (sim.fout, "\n"); + } +} + +void dump_entry_state (Entry_State *entry) +{ + int i; + + dump_dn_csn_list (entry); + + for (i = 0; i < sim.value_count; i++) + { + dump_value_state (&(entry->values[i])); + } + + fprintf (sim.fout, "\n"); +} + +void dump_value_state (Value_State *value) +{ + fprintf (sim.fout, "\tvalue %s is %s\n", g_values[value->value_index], + value->present ? "present" : "not present"); + + if (sim.verbose) + { + fprintf (sim.fout, "\t\tpresent csn: %d\n", value->presence_csn); + fprintf (sim.fout, "\t\tdistinguished index: %d\n", value->distinguished_index); + fprintf (sim.fout, "\t\tdelete value csn: %d\n", value->delete_csn); + } +} + +void dump_dn_csn_list (Entry_State *entry) +{ + int i; + + fprintf (sim.fout, "\tdn csn list: \n"); + for (i = 0; i < entry->dn_csn_count; i++) + { + fprintf (sim.fout, "\t\tvalue: %s, csn: %d\n", + g_values[entry->dn_csns[i].value_index], entry->dn_csns[i].csn); + } +} + +/* misc functions */ +int max_val (int a, int b) +{ + if (a >= b) + return a; + else + return b; +} diff --git a/ldap/servers/plugins/replication/tests/dnp_sim3.c b/ldap/servers/plugins/replication/tests/dnp_sim3.c new file mode 100644 index 00000000..d018597a --- /dev/null +++ b/ldap/servers/plugins/replication/tests/dnp_sim3.c @@ -0,0 +1,1489 @@ +/** BEGIN COPYRIGHT BLOCK + * Copyright 2001 Sun Microsystems, Inc. + * Portions copyright 1999, 2001-2003 Netscape Communications Corporation. + * All rights reserved. + * END COPYRIGHT BLOCK **/ +/* dnp_simulation.c - this file varifies the correctness of dnp algorithm + by generating random sequences of operations, applying + the algorithm and outputing the result + + usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>] + -h - print usage information. + -n <number of simulations> - how many simulations to perform; default - 1. + -v - verbose mode (prints full entry state after each operation execution) + -f <output file> - file where results are stored; by default results are + printed to the screen. + -o <op file> - file that contains operation sequence to execute; by default, + random sequence is generated. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <errno.h> +#include <memory.h> +#include <string.h> +#include <time.h> +#include <windows.h> + +#define MAX_OPS 18 /* maximum number of operations in a simulation */ +#define MAX_VALS 10 /* maximum number of values is entry or dn */ +#define MAX_ATTR_NAME 16 /* max length of the attribute name */ +#define NOT_PRESENT -1 +#define SV_ATTR_NAME "sv_attr" /* name of the singlevalued attribute */ +#define MV_ATTR_NAME "mv_attr" /* name of the multivalued attribute */ + +/* data types */ + +/* value */ +typedef struct value_state +{ + int value_index; /* value */ + int presence_csn; /* last time at which we know the value was present */ + int delete_csn; /* last attempt to delete this value */ + int present; /* flag that tells whether the value is present */ +} Value_State; + +/* shared attribute state */ +typedef struct attr_state +{ + int delete_csn; /* last deletion csn */ + int present; /* flag that tells whether the attribute is present */ +}Attr_State; + +/* singlevalued attribute */ +typedef struct sv_attr_state +{ + Attr_State attr_state; /* shared attribute state */ + Value_State current_value; /* current attribute value */ + Value_State *pending_value; /* latest pending value */ +} SV_Attr_State; + +/* maltivalued attribute */ +typedef struct mv_attr_state +{ + Attr_State attr_state; /* shared attribute state */ + Value_State values [MAX_VALS]; /* latest pending value */ + int value_count; /* number of values in the array */ +} MV_Attr_State; + +/* node of dn_csn_list */ +typedef struct dn_csn +{ + int csn; /* dn csn */ + int sv_attr; /* is this single valued or multivalued attr */ + int value_index; /* dn value */ +} Dn_Csn; + +typedef struct entry_state +{ + Dn_Csn dn_csns [MAX_VALS + 1]; /* list of dn csns for this entry */ + int dn_csn_count; /* csn of the current dn */ + SV_Attr_State sv_attr; /* singlevalued attribute */ + MV_Attr_State mv_attr; /* singlevalued attribute */ +} Entry_State; + +typedef enum +{ + OP_ADD_VALUE, + OP_DELETE_VALUE, + OP_RENAME_ENTRY, + OP_DELETE_ATTR, + OP_END +} Operation_Type; + +typedef struct operation +{ + Operation_Type type; /* operation type */ + int csn; /* operation csn */ + int sv_attr; /* is this applied to singlevalued attribute */ + int value_index; /* value to add, remove or rename from */ + int delete_old_rdn; /* rename only */ + int old_rdn_sv_attr; /* is oldrdn a singlevalued attribute */ + int old_rdn_value_index; /* index of old_rdn */ +}Operation; + +typedef struct simulator_params +{ + int runs; /* number of runs */ + FILE *fout; /* output file */ + int value_count; /* number of values */ + int verbose; /* verbose mode */ + Operation *ops; /* operation sequence to apply */ + int op_count; +}Simulator_Params; + + +/* gloabl data */ +Simulator_Params sim; +char *g_values[] = +{ + "v", + "u", + "w", + NULL +}; + +/* forward declarations */ + +/* initialization */ +void process_cmd (int argc, char **argv); +void set_default_sim_params (); +int count_values (); +void parse_operations_file (char *name); +void parse_operation (char *line, int pos); +int value2index (char *value); +void print_usage (); + +/* simulation run */ +void run_simulation (); +void generate_operations (Operation **ops, int *op_count); +void generate_operation (Operation *op, int csn); +int* generate_operation_order (int op_count, int seq_num); +void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry); +void init_entry_state (Entry_State *entry); +void init_sv_attr_state (SV_Attr_State *sv_attr); +void init_mv_attr_state (MV_Attr_State *mv_attr); +void init_value_state (Value_State *val, int seq_num); +void free_operations (Operation **ops); +int ** new_perm_table (int op_count); +void free_perm_table (int ***perm_table, int op_count); +int get_perm_count (int op_count); +void generate_perm_table (int *elements, int element_count, int static_part, + int **perm_table); +void apply_operation (Entry_State *entry, Operation *op); +void apply_add_operation (Entry_State *entry, Operation *op); +void apply_value_delete_operation (Entry_State *entry, Operation *op); +void apply_attr_delete_operation (Entry_State *entry, Operation *op); +void apply_rename_operation (Entry_State *entry, Operation *op); +void resolve_mv_attr_state (Entry_State *entry, Value_State *value); +void resolve_sv_attr_state (Entry_State *entry, Value_State *value); +void purge_sv_attr_state (Entry_State *entry); +void purge_mv_attr_state (Entry_State *entry, Value_State *value); +int value_distinguished_at_csn (Entry_State *entry, int sv_attr, Value_State *value, int csn); + +/* state comparison */ +int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run); +int compare_entry_state_quick (Entry_State *entry1, Entry_State *entry2, int run); +int compare_sv_attr_state_quick (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run); +int compare_mv_attr_state_quick (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run); +int compare_sv_attr_state (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run); +int compare_mv_attr_state (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run); +int compare_value_state (Value_State *value1, Value_State *value2, int run); + +/* dnc_csn handling */ +int dn_csn_add (Entry_State *entry, int sv_attr, int value_index, int csn); + +/* data tracing */ +void dump_operations (Operation *ops, int op_count, int *order); +void dump_operation (Operation *op); +void dump_perm_table (int **perm_table, int op_count); +void dump_entry_state (Entry_State *entry); +void dump_sv_attr_state (SV_Attr_State *sv_attr); +void dump_mv_attr_state (MV_Attr_State *mv_attr); +void dump_value_state (Value_State *value, int sv_attr); +void dump_dn_csn_list (Entry_State *entry); + +/* misc functions */ +int max_val (int a, int b); + +int main (int argc, char **argv) +{ + int i; + + process_cmd (argc, argv); + + for (i = 0; i < sim.runs; i++) + { + fprintf (sim.fout, "*******running simulation #%d ...\n\n", i+1); + run_simulation (); + fprintf (sim.fout, "\n*******done with simulation #%d ...\n\n", i+1); + } + + if (sim.fout != stdout) + fclose (sim.fout); + + return 0; +} + +void process_cmd (int argc, char **argv) +{ + int i; + + set_default_sim_params (); + + if (argc == 1) + { + return; + } + + if (strcmp (argv[1], "-h") == 0) /* print help */ + { + print_usage (); + exit (0); + } + + i = 1; + while (i < argc) + { + if (strcmp (argv[i], "-v") == 0) /* verbose mode */ + { + sim.verbose = 1; + i ++; + } + else if (strcmp (argv[i], "-n") == 0) + { + if (i < argc - 1) + { + int runs = atoi (argv[i + 1]); + if (runs > 0) + sim.runs = runs; + i+=2; + } + else + { + /* ONREPL print warning */ + i++; + } + } + else if (strcmp (argv[i], "-f") == 0) /* output file */ + { + if (i < argc - 1) + { + FILE *f = fopen (argv[i + 1], "w"); + if (f == 0) + { + printf ("failed to open output file; error - %s, using stdout\n", + strerror(errno)); + } + else + { + /* ONREPL print warning */ + sim.fout = f; + } + + i += 2; + } + else + i++; + } + else if (strcmp (argv[i], "-o") == 0) /* file with operation sequence */ + { + if (i < argc - 1) + { + parse_operations_file (argv[i+1]); + i += 2; + } + else + { + /* ONREPL print warning */ + i ++; + } + } + else /* unknown option */ + { + printf ("unknown option - %s; ignored\n", argv[i]); + i ++; + } + + } +} + +void set_default_sim_params () +{ + memset (&sim, 0, sizeof (sim)); + sim.runs = 1; + sim.fout = stdout; + sim.value_count = count_values (); +} + +/* file format: <operation count> + add <attribute> <value> + delete <attribute>[ <value>] + rename to <attribute> <value>[ delete <attribute> <value>] + + all spaces are significant + */ +void parse_operations_file (char *name) +{ + FILE *file = fopen (name, "r"); + char line [256]; + int i; + + if (file == NULL) + { + printf ("failed to open operations file %s: error = %d\n", name, errno); + print_usage (); + exit (1); + } + + i = 0; + while (fgets (line, sizeof (line), file)) + { + if (i == 0) + { + /* read operation count */ + sim.op_count = atoi (line); + if (sim.op_count < 1 || sim.op_count > MAX_OPS/2) + { + printf ("invalid operation count - %d; value must be between 1 and %d\n", + sim.op_count, MAX_OPS/2); + print_usage (); + exit (1); + } + else + { + sim.ops = (Operation*)malloc (sim.op_count * sizeof (Operation)); + } + } + else + { + if (strlen (line) == 0) /* skip empty lines */ + continue; + parse_operation (line, i); + } + + i ++; + } +} + +#define ADD_KEYWORD "add " +#define DELETE_KEYWORD "delete " +#define RENAME_KEYWORD "rename to " +#define DELET_OLD_RDN_KEYWORD " delete " + +void parse_operation (char *line, int i) +{ + int rc = 0; + char *pos; + char buff [64]; + + sim.ops [i - 1].csn = i; + + if (line[strlen(line) - 1] == '\n') + line[strlen(line) - 1] = '\0'; + + /* add <attribute> <value> */ + if (strncmp (line, ADD_KEYWORD, strlen (ADD_KEYWORD)) == 0) + { + sim.ops [i - 1].type = OP_ADD_VALUE; + pos = strchr (&line[strlen (ADD_KEYWORD)], ' '); + if (pos == NULL) + { + rc = -1; + goto done; + } + + memset (buff, 0, sizeof (buff)); + strncpy (buff, &line[strlen (ADD_KEYWORD)], pos - &line[strlen (ADD_KEYWORD)]); + sim.ops [i - 1].sv_attr = strcmp (buff, MV_ATTR_NAME); + sim.ops [i - 1].value_index = value2index (pos + 1); + } + /* delete <attribute>[ <value>] */ + else if (strncmp (line, DELETE_KEYWORD, strlen (DELETE_KEYWORD)) == 0) + { + pos = strchr (&line[strlen (DELETE_KEYWORD)], ' '); + if (pos == NULL) /* delete attribute version */ + { + sim.ops [i - 1].type = OP_DELETE_ATTR; + sim.ops [i - 1].sv_attr = strcmp (&line[strlen (DELETE_KEYWORD)], + MV_ATTR_NAME); + } + else /* delete value version */ + { + memset (buff, 0, sizeof (buff)); + sim.ops [i - 1].type = OP_DELETE_VALUE; + strncpy (buff, &line[strlen (DELETE_KEYWORD)], + pos - &line[strlen (DELETE_KEYWORD)]); + sim.ops [i - 1].sv_attr = strcmp (buff, MV_ATTR_NAME); + sim.ops [i - 1].value_index = value2index (pos + 1); + } + } + /* rename to <attribute> <valued>[ delete <attribute> <value>] */ + else if (strncmp (line, RENAME_KEYWORD, 10) == 0) + { + char *pos2; + + sim.ops [i - 1].type = OP_RENAME_ENTRY; + + pos = strchr (&line[strlen (RENAME_KEYWORD)], ' '); + if (pos == NULL) + { + rc = -1; + goto done; + } + + memset (buff, 0, sizeof (buff)); + strncpy (buff, &line[strlen (RENAME_KEYWORD)], pos - &line[strlen (RENAME_KEYWORD)]); + sim.ops [i - 1].sv_attr = strcmp (buff, MV_ATTR_NAME); + + pos2 = strstr (pos + 1, DELET_OLD_RDN_KEYWORD); + if (pos2 == NULL) /* no delete old rdn part */ + { + sim.ops [i - 1].value_index = value2index (pos + 1); + sim.ops [i - 1].delete_old_rdn = 0; + } + else + { + memset (buff, 0, sizeof (buff)); + strncpy (buff, pos + 1, pos2 - pos - 1); + sim.ops [i - 1].value_index = value2index (buff); + pos2 += strlen (DELET_OLD_RDN_KEYWORD); + pos = strchr (pos2, ' '); + if (pos == NULL) + { + rc = -1; + goto done; + } + + memset (buff, 0, sizeof (buff)); + strncpy (buff, pos2, pos - pos2); + sim.ops [i - 1].delete_old_rdn = 1; + sim.ops [i - 1].old_rdn_sv_attr = strcmp (buff, MV_ATTR_NAME); + sim.ops [i - 1].old_rdn_value_index = value2index (pos + 1); + } + } + else + { + /* error */ + rc = -1; + } + +done: + if (rc) + { + /* invalid line */ + printf ("invalid operation: %s\n", line); + exit (1); + } +} +int value2index (char *value) +{ + int i; + + for (i = 0; i < sim.value_count; i++) + { + if (strcmp (g_values[i], value) == 0) + return i; + } + + return -1; +} + +void print_usage () +{ + printf ("usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>]\n" + "\t-h - print usage information\n" + "\t-n <number of simulations>; default - 1\n" + "\t-v - verbose mode\n" + "\t-f <output file> - by default, results are printed to the screen\n" + "\t-o <op file> - file that contains operation sequence to execute;\n" + "\tby default, random sequence is generated.\n"); +} + +int count_values () +{ + int i; + + for (i = 0; g_values[i]; i++); + + return i; +} + +void run_simulation () +{ + int *order; + int i; + int perm_count; + Entry_State entry_first, entry_current; + int error = 0; + + init_entry_state (&entry_first); + fprintf (sim.fout, "initial entry state :\n"); + dump_entry_state (&entry_first); + + if (sim.ops == NULL) + { + generate_operations (&sim.ops, &sim.op_count); + } + fprintf (sim.fout, "initial operation set:\n"); + dump_operations (sim.ops, sim.op_count, NULL/* order */); + + perm_count = get_perm_count (sim.op_count); + for (i = 0; i < perm_count; i++) + { + fprintf (sim.fout, "--------------------------------\n"); + fprintf (sim.fout, "simulation run %d\n", i + 1); + fprintf (sim.fout, "--------------------------------\n"); + order = generate_operation_order (sim.op_count, i); + if (i == 0) + apply_operation_sequence (sim.ops, sim.op_count, order, &entry_first); + else + { + apply_operation_sequence (sim.ops, sim.op_count, order, &entry_current); + error |= compare_entry_state (&entry_first, &entry_current, i + 1); + } + } + + switch (error) + { + case 0: fprintf (sim.fout, "all runs left the entry in the same state\n"); + break; + case 1: fprintf (sim.fout, "while value presence is consistent across all runs, " + "the exact state does not match\n"); + break; + case 3: fprintf (sim.fout, "the runs left entries in an inconsistent state\n"); + break; + } + + free_operations (&sim.ops); +} + +void generate_operations (Operation **ops, int *op_count) +{ + int i; + + /* generate number operations in the sequence */ + *op_count = slapi_rand () % (MAX_OPS / 2) + 1; + *ops = (Operation *)malloc (*op_count * sizeof (Operation)); + + for (i = 0; i < *op_count; i ++) + { + generate_operation (&((*ops)[i]), i + 1); + } +} + +void generate_operation (Operation *op, int csn) +{ + /* generate operation type */ + op->type = slapi_rand () % OP_END; + op->csn = csn; + + /* choose if the operation applies to the single value or + the multivalued attribute */ + op->sv_attr = slapi_rand () % 2; + + /* generate value to which operation applies */ + op->value_index = slapi_rand () % sim.value_count; + + if (op->type == OP_RENAME_ENTRY) + { + op->delete_old_rdn = slapi_rand () % 2; + if (op->delete_old_rdn) + { + op->old_rdn_sv_attr = slapi_rand () % 2; + op->old_rdn_value_index = slapi_rand () % sim.value_count; + + while (op->old_rdn_sv_attr == op->sv_attr && + op->old_rdn_value_index == op->value_index) + { + op->old_rdn_sv_attr = slapi_rand () % 2; + op->old_rdn_value_index = slapi_rand () % sim.value_count; + } + } + } +} + +int* generate_operation_order (int op_count, int seq_num) +{ + static int **perm_table = NULL; + + /* first request - generate pemutation table */ + if (seq_num == 0) + { + int elements [MAX_OPS]; + int i; + + if (perm_table) + free_perm_table (&perm_table, op_count); + perm_table = new_perm_table (op_count); + + for (i = 0; i < op_count; i++) + elements [i] = i; + + generate_perm_table (elements, op_count, 0 /* static part */, + perm_table); + } + + return perm_table [seq_num]; +} + +void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry) +{ + int i; + + init_entry_state (entry); + + if (!sim.verbose) + { + if (!sim.verbose) + { + fprintf (sim.fout, "operation_sequence for this run:\n"); + dump_operations (ops, op_count, order); + } + } + + for (i = 0; i < op_count; i++) + { + apply_operation (entry, &(ops [order[i]])); + } + + if (!sim.verbose) + { + fprintf (sim.fout, "final entry state :\n"); + dump_entry_state (entry); + } +} + +void init_entry_state (Entry_State *entry) +{ + memset (entry, 0, sizeof (*entry)); + entry->dn_csn_count = 1; + + init_sv_attr_state (&entry->sv_attr); + init_mv_attr_state (&entry->mv_attr); +} + +void init_sv_attr_state (SV_Attr_State *sv_attr) +{ + memset (sv_attr, 0, sizeof (*sv_attr)); + sv_attr->attr_state.delete_csn = NOT_PRESENT; + sv_attr->attr_state.present = 1; + init_value_state (&sv_attr->current_value, 1); +} + +void init_mv_attr_state (MV_Attr_State *mv_attr) +{ + int i; + + memset (mv_attr, 0, sizeof (*mv_attr)); + mv_attr->attr_state.delete_csn = NOT_PRESENT; + mv_attr->attr_state.present = 1; + mv_attr->value_count = sim.value_count; + + for (i = 0; i < mv_attr->value_count; i++) + { + init_value_state (&(mv_attr->values[i]), i); + } +} + +void init_value_state (Value_State *val, int seq_num) +{ + memset (val, 0, sizeof (*val)); + val->value_index = seq_num; + val->present = 1; + val->delete_csn = NOT_PRESENT; +} + +void apply_operation (Entry_State *entry, Operation *op) +{ + switch (op->type) + { + case OP_ADD_VALUE: apply_add_operation (entry, op); + break; + + case OP_DELETE_VALUE: apply_value_delete_operation (entry, op); + break; + + case OP_DELETE_ATTR: apply_attr_delete_operation (entry, op); + break; + + case OP_RENAME_ENTRY: apply_rename_operation (entry, op); + break; + } + + if (sim.verbose) + { + fprintf (sim.fout, "operation: "); + dump_operation (op); + fprintf (sim.fout, "\n"); + dump_entry_state (entry); + } +} + +void free_operations (Operation **ops) +{ + free (*ops); + *ops = NULL; +} + +int **new_perm_table (int op_count) +{ + int i; + int **perm_table; + int perm_count = get_perm_count (op_count); + + perm_table = (int**)malloc (perm_count * sizeof (int*)); + for (i = 0; i < perm_count; i ++) + perm_table [i] = (int*) malloc (op_count * sizeof (int)); + + return perm_table; +} + +void free_perm_table (int ***perm_table, int op_count) +{ + int i; + int perm_count = get_perm_count (op_count); + + for (i = 0; i < perm_count; i ++) + free ((*perm_table)[i]); + + free (*perm_table); + *perm_table = NULL; +} + +void generate_perm_table (int *elements, int element_count, int static_part, + int **perm_table) +{ + int i; + int elements_copy [MAX_OPS]; + int start_pos; + + if (element_count - 1 == static_part) + { + memcpy (*perm_table, elements, element_count * sizeof (int)); + return; + } + + start_pos = 0; + for (i = 0; i < element_count - static_part; i ++) + { + memcpy (elements_copy, elements, element_count * sizeof (int)); + elements_copy [static_part] = elements [static_part + i]; + elements_copy [static_part + i] = elements [static_part]; + generate_perm_table (elements_copy, element_count, static_part + 1, + &perm_table [start_pos]); + start_pos += get_perm_count (element_count - static_part - 1); + } +} + +int get_perm_count (int op_count) +{ + int i; + int perm_count = 1; + + for (i = 2; i <= op_count; i ++) + perm_count *= i; + + return perm_count; +} + +void apply_add_operation (Entry_State *entry, Operation *op) +{ + if (op->sv_attr) + { + Value_State *val; + Value_State temp_val; + + if (op->value_index == entry->sv_attr.current_value.value_index) + { + val = &entry->sv_attr.current_value; + } + else if (entry->sv_attr.pending_value && + op->value_index == entry->sv_attr.pending_value->value_index) + { + val = entry->sv_attr.pending_value; + } + else /* new value */ + { + init_value_state (&temp_val, op->value_index); + val = &temp_val; + } + + if (val->presence_csn < op->csn) + val->presence_csn = op->csn; + + resolve_sv_attr_state (entry, val); + } + else + { + if (entry->mv_attr.values[op->value_index].presence_csn < op->csn) + { + entry->mv_attr.values[op->value_index].presence_csn = op->csn; + resolve_mv_attr_state (entry, &(entry->mv_attr.values[op->value_index])); + } + } +} + +void apply_value_delete_operation (Entry_State *entry, Operation *op) +{ + if (op->sv_attr) + { + if (entry->sv_attr.attr_state.delete_csn < op->csn) + { + entry->sv_attr.attr_state.delete_csn = op->csn; + resolve_sv_attr_state (entry, NULL); + } + } + else /* mv attr */ + { + if (entry->mv_attr.values[op->value_index].delete_csn < op->csn) + { + entry->mv_attr.values[op->value_index].delete_csn = op->csn; + resolve_mv_attr_state (entry, &(entry->mv_attr.values[op->value_index])); + } + } +} + +void apply_attr_delete_operation (Entry_State *entry, Operation *op) +{ + int i; + + if (op->sv_attr) + { + if (entry->sv_attr.attr_state.delete_csn < op->csn) + { + entry->sv_attr.attr_state.delete_csn = op->csn; + resolve_sv_attr_state (entry, NULL); + } + } + else /* mv attr */ + { + if (entry->mv_attr.attr_state.delete_csn < op->csn) + { + entry->mv_attr.attr_state.delete_csn = op->csn; + + for (i = 0; i < sim.value_count; i++) + { + resolve_mv_attr_state (entry, &(entry->mv_attr.values[i])); + } + } + } +} + +void apply_rename_operation (Entry_State *entry, Operation *op) +{ + int index; + Operation del_op; + + /* insert new dn into dn_csn_list */ + index = dn_csn_add (entry, op->sv_attr, op->value_index, op->csn); + + /* issue delete value operation for the old rdn */ + if (op->delete_old_rdn) + { + del_op.type = OP_DELETE_VALUE; + del_op.csn = op->csn; + del_op.sv_attr = op->old_rdn_sv_attr; + del_op.value_index = op->old_rdn_value_index; + + apply_value_delete_operation (entry, &del_op); + } + + /* resolve state of the previous node in dn_csn_list */ + if (index > 0) + { + if (entry->dn_csns[index-1].sv_attr) + { + if (entry->dn_csns[index-1].value_index == + entry->sv_attr.current_value.value_index) + { + resolve_sv_attr_state (entry, &(entry->sv_attr.current_value)); + } + else if (entry->sv_attr.pending_value && + entry->dn_csns[index-1].value_index == + entry->sv_attr.pending_value->value_index) + { + resolve_sv_attr_state (entry, entry->sv_attr.pending_value); + } + } + else + { + int i = entry->dn_csns[index-1].value_index; + resolve_mv_attr_state (entry, &(entry->mv_attr.values[i])); + } + } + + /* resolve state of the new dn */ + if (op->sv_attr) + { + Value_State *value; + Value_State temp_val; + if (op->value_index == entry->sv_attr.current_value.value_index) + { + value = &entry->sv_attr.current_value; + } + else if (entry->sv_attr.pending_value && + op->value_index == entry->sv_attr.pending_value->value_index) + { + value = entry->sv_attr.pending_value; + } + else /* new value */ + { + init_value_state (&temp_val, op->value_index); + value = &temp_val; + } + + if (value->presence_csn == NOT_PRESENT || value->presence_csn < op->csn) + value->presence_csn = op->csn; + resolve_sv_attr_state (entry, value); + } + else + { + if (entry->mv_attr.values[op->value_index].presence_csn == NOT_PRESENT || + entry->mv_attr.values[op->value_index].presence_csn < op->csn) + entry->mv_attr.values[op->value_index].presence_csn = op->csn; + + resolve_mv_attr_state (entry, &(entry->mv_attr.values[op->value_index])); + } +} + +void purge_mv_attr_state (Entry_State *entry, Value_State *value) +{ + if (value->presence_csn > value->delete_csn) + value->delete_csn = NOT_PRESENT; +} + +void purge_sv_attr_state (Entry_State *entry) +{ + if (entry->sv_attr.attr_state.delete_csn != NOT_PRESENT) + { + if (entry->sv_attr.pending_value) + { + if (entry->sv_attr.attr_state.delete_csn < + entry->sv_attr.pending_value->presence_csn) + { + entry->sv_attr.attr_state.delete_csn = NOT_PRESENT; + } + } + else + { + if (entry->sv_attr.attr_state.delete_csn < + entry->sv_attr.current_value.presence_csn) + entry->sv_attr.attr_state.delete_csn = NOT_PRESENT; + } + } +} + +void resolve_mv_attr_state (Entry_State *entry, Value_State *value) +{ + purge_mv_attr_state (entry, value); + + /* no deletes that effect the state */ + if (max_val (value->delete_csn, entry->mv_attr.attr_state.delete_csn) < + value->presence_csn) + { + value->present = 1; + return; + } + + if (value->present) /* check if it should be removed based on the current state */ + { + if (!value_distinguished_at_csn (entry, 0, value, + max (value->delete_csn, entry->mv_attr.attr_state.delete_csn))) + { + value->present = 0; + } + } + else /* not present - check if it should be restored */ + { + if (value_distinguished_at_csn (entry, 0, value, + max (value->delete_csn, entry->mv_attr.attr_state.delete_csn))) + { + value->present = 1; + } + } + + if (entry->mv_attr.attr_state.delete_csn == NOT_PRESENT) + { + entry->mv_attr.attr_state.present = 1; + } + else + { + int i; + int distinguished = 0; + + for (i = 0; i < entry->mv_attr.value_count; i ++) + { + distinguished |= value_distinguished_at_csn (entry, 0, + &(entry->mv_attr.values[i]), + entry->mv_attr.attr_state.delete_csn); + } + + entry->mv_attr.attr_state.present = distinguished; + } +} + +void resolve_sv_attr_state (Entry_State *entry, Value_State *value) +{ + purge_sv_attr_state (entry); + + if (value) + { + /* existing value is modified */ + if (value == &(entry->sv_attr.current_value) || + value == entry->sv_attr.pending_value) + { + /* check if current value should be replaced with the pending value */ + if (entry->sv_attr.pending_value) + { + if (!value_distinguished_at_csn (entry, 1, &entry->sv_attr.current_value, + entry->sv_attr.current_value.presence_csn)) + { + /* replace current value with the pending value */ + memcpy (&entry->sv_attr.current_value, entry->sv_attr.pending_value, + sizeof (Value_State)); + free (entry->sv_attr.pending_value); + entry->sv_attr.pending_value = NULL; + } + } + } + else /* addition of a new value */ + { + /* new value is before the current value; note that, for new value, + presence_csn is the same as distinguished_csn */ + if (value->presence_csn < entry->sv_attr.current_value.presence_csn) + { + /* if new value is distinguished, it should become current and the + current can become pending */ + if (value_distinguished_at_csn (entry, 1, value, + entry->sv_attr.current_value.presence_csn)) + { + if (entry->sv_attr.pending_value == NULL) + { + entry->sv_attr.pending_value = (Value_State*) + malloc (sizeof (Value_State)); + memcpy (entry->sv_attr.pending_value, &entry->sv_attr.current_value, + sizeof (Value_State)); + } + + memcpy (&entry->sv_attr.current_value, value, sizeof (Value_State)); + } + } + else /* new value is after the current value */ + { + /* if current value is not distinguished, new value should + become distinguished */ + if (!value_distinguished_at_csn (entry, 1, &entry->sv_attr.current_value, + value->presence_csn)) + { + memcpy (&entry->sv_attr.current_value, value, sizeof (Value_State)); + } + else /* current value is distinguished - check if new value should replace + the pending value */ + { if (entry->sv_attr.pending_value) + { + if (value->presence_csn > entry->sv_attr.pending_value->presence_csn) + { + memcpy (entry->sv_attr.pending_value, value, sizeof (Value_State)); + } + } + else + { + entry->sv_attr.pending_value = (Value_State*)malloc (sizeof (Value_State)); + memcpy (entry->sv_attr.pending_value, value, sizeof (Value_State)); + } + } + } + } + } + + /* update the attribute state */ + purge_sv_attr_state (entry); + + /* set attribute state */ + if (entry->sv_attr.attr_state.delete_csn != NOT_PRESENT && + !value_distinguished_at_csn (entry, 1, &entry->sv_attr.current_value, + entry->sv_attr.attr_state.delete_csn)) + { + entry->sv_attr.attr_state.present = 0; + } + else + { + entry->sv_attr.attr_state.present = 1; + } +} + +int value_distinguished_at_csn (Entry_State *entry, int sv_attr, Value_State *value, int csn) +{ + int i; + + for (i = 0; i < entry->dn_csn_count; i++) + { + if (entry->dn_csns[i].csn > csn) + break; + } + + /* i is never equal to 0 because the csn of the first element is always + smaller than csn of any operation we can receive */ + return (entry->dn_csns[i-1].value_index == value->value_index && + entry->dn_csns[i-1].sv_attr == sv_attr); +} + +int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run) +{ + int i; + int error = 0; + + error = compare_entry_state_quick (entry1, entry2, run); + + if (error) + return 3; + + /* compare dnc_csn list */ + if (entry1->dn_csn_count != entry2->dn_csn_count) + { + fprintf (sim.fout, "dn_csn count is %d for run 1 and %d for run %d\n", + entry1->dn_csn_count, entry2->dn_csn_count, run); + error = 1; + } + + for (i = 0; i < entry1->dn_csn_count; i++) + { + if (entry1->dn_csns [i].csn != entry2->dn_csns [i].csn || + entry1->dn_csns [i].sv_attr != entry2->dn_csns [i].sv_attr || + entry1->dn_csns [i].value_index != entry2->dn_csns [i].value_index) + { + fprintf (sim.fout,"elements %d of dn csn list are different:\n" + "\tfirst run: csn - %d, attr - %s, value - %s\n" + "\t%d run: csn - %d, attr - %s value - %s\n", i, + entry1->dn_csns [i].csn, + entry1->dn_csns [i].sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME, + g_values[entry1->dn_csns [i].value_index], + run, entry2->dn_csns [i].csn, + entry2->dn_csns [i].sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME, + g_values[entry2->dn_csns [i].value_index]); + + error = 1; + } + } + + error |= compare_sv_attr_state (&entry1->sv_attr, &entry2->sv_attr, run); + + error |= compare_mv_attr_state (&entry1->mv_attr, &entry2->mv_attr, run); + + if (error != 0) + { + return 1; + } + else + return 0; +} + +/* just compare if the same attributes and values are present */ +int compare_entry_state_quick (Entry_State *entry1, Entry_State *entry2, int run) +{ + int error; + + error = compare_sv_attr_state_quick (&entry1->sv_attr, &entry2->sv_attr, run); + + error |= compare_mv_attr_state_quick (&entry1->mv_attr, &entry2->mv_attr, run); + + return error; +} + +int compare_sv_attr_state_quick (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run) +{ + int error = 0; + if (sv_attr1->attr_state.present != sv_attr2->attr_state.present) + { + fprintf (sim.fout, "singlevalued attribute is %s present in the first run " + "but is %s present in the %d run\n", + sv_attr1->attr_state.present ? "" : "not", + sv_attr2->attr_state.present ? "" : "not", run); + return 1; + } + + if (sv_attr1->attr_state.present && + sv_attr1->current_value.value_index != sv_attr2->current_value.value_index) + { + fprintf (sim.fout, "different values for singlevalued attribute: %s for the \n" + "first run and %s for the %d run\n", + g_values [sv_attr1->current_value.value_index], + g_values [sv_attr2->current_value.value_index], run); + return 1; + } + + return 0; +} + +int compare_mv_attr_state_quick (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run) +{ + int i; + int error = 0; + + if (mv_attr1->attr_state.present != mv_attr2->attr_state.present) + { + fprintf (sim.fout, "multivalued attribute is %s present in the first run " + "but is %s present in the %d run\n", + mv_attr1->attr_state.present ? "" : "not", + mv_attr2->attr_state.present ? "" : "not", run); + return 1; + } + + /* value count does not change during the iteration, so we don't have + to check if the count is the same for both attributes */ + for (i = 0; i < mv_attr1->value_count; i++) + { + if (mv_attr1->values[i].present != mv_attr2->values[i].present) + { + fprintf (sim.fout, "value %s is %s present in the multivalued attribute\n" + "in the first run but %s present in the %d run\n", + g_values[i], mv_attr1->values[i].present ? "" : "not", + mv_attr2->values[i].present ? "" : "not", run); + error = 1; + } + } + + return error; +} + +int compare_sv_attr_state (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run) +{ + int error = 0; + + if (sv_attr1->attr_state.delete_csn != sv_attr2->attr_state.delete_csn) + { + fprintf (sim.fout, "singlevalued attribute deletion csn is %d for run 1 " + "but is %d for run %d\n", sv_attr1->attr_state.delete_csn, + sv_attr2->attr_state.delete_csn, run); + error = 1; + } + + error |= compare_value_state (&sv_attr1->current_value, &sv_attr2->current_value, run); + + if ((sv_attr1->pending_value && !sv_attr1->pending_value) || + (!sv_attr1->pending_value && sv_attr1->pending_value)) + { + fprintf (sim.fout, "pending value is %s present in the singlevalued attribute\n" + " in the first run but is %s in the %d run\n", + sv_attr1->pending_value ? "" : "not", + sv_attr2->pending_value ? "" : "not", run); + + return 1; + } + + if (sv_attr1->pending_value) + error |= compare_value_state (sv_attr1->pending_value, sv_attr2->pending_value, run); + + return 0; +} + +int compare_mv_attr_state (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run) +{ + int error = 0; + int i; + + if (mv_attr1->attr_state.delete_csn != mv_attr2->attr_state.delete_csn) + { + fprintf (sim.fout, "multivalued attribute deletion csn is %d for run 1 " + "but is %d for run %d\n", mv_attr1->attr_state.delete_csn, + mv_attr2->attr_state.delete_csn, run); + error = 1; + } + + for (i = 0; i < mv_attr1->value_count; i++) + { + error |= compare_value_state (&mv_attr1->values[i], &mv_attr2->values[i], run); + } + + return error; +} + +int compare_value_state (Value_State *value1, Value_State *value2, int run) +{ + int error = 0; + + if (value1->presence_csn != value2->presence_csn) + { + fprintf (sim.fout, "multivalued attribute: presence csn for value %s is %d " + "in run 1 but is %d in run %d\n", g_values[value1->value_index], + value1->presence_csn, value2->presence_csn, run); + error = 1; + } + + if (value1->delete_csn != value2->delete_csn) + { + fprintf (sim.fout, "multivalued attribute: delete csn for value %s is %d in run 1 " + "but is %d in run %d\n", g_values[value1->value_index], + value1->delete_csn, value2->delete_csn, run); + error = 1; + } + + return error; +} + +int dn_csn_add (Entry_State *entry, int sv_attr, int value_index, int csn) +{ + int i; + + for (i = 0; i < entry->dn_csn_count; i++) + { + if (entry->dn_csns[i].csn > csn) + break; + } + + if (i < entry->dn_csn_count) + { + memcpy (&(entry->dn_csns[i+1]), &(entry->dn_csns[i]), + (entry->dn_csn_count - i) * sizeof (Dn_Csn)); + } + + entry->dn_csns[i].csn = csn; + entry->dn_csns[i].sv_attr = sv_attr; + entry->dn_csns[i].value_index = value_index; + entry->dn_csn_count ++; + + return i; +} + +void dump_operations (Operation *ops, int op_count, int *order) +{ + int index; + int i; + + for (i = 0; i < op_count; i ++) + { + if (order == NULL) /* current order */ + index = i; + else + index = order [i]; + + dump_operation (&ops[index]); + } + + fprintf (sim.fout, "\n"); +} + +void dump_operation (Operation *op) +{ + switch (op->type) + { + case OP_ADD_VALUE: + fprintf (sim.fout, "\t%d add value %s to %s\n", op->csn, + g_values [op->value_index], + op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME); + break; + case OP_DELETE_VALUE: + fprintf (sim.fout, "\t%d delete value %s from %s\n", op->csn, + g_values [op->value_index], + op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME); + break; + case OP_DELETE_ATTR: + fprintf (sim.fout, "\t%d delete %s attribute\n", op->csn, + op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME); + break; + case OP_RENAME_ENTRY: + fprintf (sim.fout, "\t%d rename entry to %s=%s", op->csn, + op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME, + g_values [op->value_index]); + if (op->delete_old_rdn) + fprintf (sim.fout, " delete old rdn %s=%s\n", + op->old_rdn_sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME, + g_values [op->old_rdn_value_index]); + else + fprintf (sim.fout, "\n"); + break; + } +} + +void dump_perm_table (int **perm_table, int op_count) +{ + int i, j; + int perm_count = get_perm_count (op_count); + + for (i = 0; i < op_count; i++) + { + for (j = 0; j < perm_count; j++) + { + fprintf (sim.fout, "%d ", perm_table [j][i]); + } + + fprintf (sim.fout, "\n"); + } +} + +void dump_entry_state (Entry_State *entry) +{ + dump_dn_csn_list (entry); + + dump_sv_attr_state (&entry->sv_attr); + dump_mv_attr_state (&entry->mv_attr); + + fprintf (sim.fout, "\n"); +} + +void dump_sv_attr_state (SV_Attr_State *sv_attr) +{ + fprintf (sim.fout, "\tattribute %s is %s present", SV_ATTR_NAME, + sv_attr->attr_state.present ? "" : "not"); + if (sv_attr->attr_state.present) + { + fprintf (sim.fout, " and has the value of %s\n", + g_values[sv_attr->current_value.value_index]); + } + else + { + fprintf (sim.fout, "\n"); + } + + if (sim.verbose) + { + fprintf (sim.fout, "\t\tdeletion csn: %d\n", sv_attr->attr_state.delete_csn); + fprintf (sim.fout, "\t\tcurrent value: "); + dump_value_state (&sv_attr->current_value, 1/* for single valued attr */); + if (sv_attr->pending_value) + { + fprintf (sim.fout, "\t\tpending value: "); + dump_value_state (sv_attr->pending_value, 1/* for single valued attr */); + } + } +} + +void dump_mv_attr_state (MV_Attr_State *mv_attr) +{ + int i; + + fprintf (sim.fout, "\tattribute %s is %s present\n", MV_ATTR_NAME, + mv_attr->attr_state.present ? "" : "not"); + + if (sim.verbose) + { + fprintf (sim.fout, "\t\tdeletion csn: %d\n", mv_attr->attr_state.delete_csn); + } + + for (i = 0; i < mv_attr->value_count; i++) + { + dump_value_state (&(mv_attr->values[i]), 0); + } +} + +void dump_value_state (Value_State *value, int sv_attr) +{ + if (!sv_attr) + { + fprintf (sim.fout, "\tvalue %s is %s present\n", g_values[value->value_index], + value->present ? "" : "not"); + } + else + { + fprintf (sim.fout, "%s\n", g_values[value->value_index]); + } + + if (sim.verbose) + { + fprintf (sim.fout, "\t\t\tpresence csn: %d\n", value->presence_csn); + fprintf (sim.fout, "\t\t\tdeletion value csn: %d\n", value->delete_csn); + } +} + +void dump_dn_csn_list (Entry_State *entry) +{ + int i; + + fprintf (sim.fout, "\tdn csn list: \n"); + for (i = 0; i < entry->dn_csn_count; i++) + { + fprintf (sim.fout, "\t\t %s=%s, csn: %d\n", + entry->dn_csns[i].sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME, + g_values[entry->dn_csns[i].value_index], entry->dn_csns[i].csn); + } +} + +/* misc functions */ +int max_val (int a, int b) +{ + if (a >= b) + return a; + else + return b; +} diff --git a/ldap/servers/plugins/replication/tests/makesim b/ldap/servers/plugins/replication/tests/makesim new file mode 100755 index 00000000..0cedd6e1 --- /dev/null +++ b/ldap/servers/plugins/replication/tests/makesim @@ -0,0 +1,58 @@ +# BEGIN COPYRIGHT BLOCK +# Copyright 2001 Sun Microsystems, Inc. +# Portions copyright 1999, 2001-2003 Netscape Communications Corporation. +# All rights reserved. +# END COPYRIGHT BLOCK +# +# gnu makefile for LDAP Server tools. +# + +MCOM_ROOT = ../../../../../.. +LDAP_SRC = ../../../.. + +NOSTDCLEAN=true # don't let nsconfig.mk define target clean +NOSTDSTRIP=true # don't let nsconfig.mk define target strip + +OBJDEST = $(OBJDIR)/lib/replication-plugin +BINDIR = $(OBJDIR)/bin + +include $(MCOM_ROOT)/netsite/nsdefs.mk +include $(MCOM_ROOT)/netsite/nsconfig.mk +include $(LDAP_SRC)/nsldap.mk + +LDFLAGS += $(EXLDFLAGS) + +ifeq ($(ARCH), WINNT) +SUBSYSTEM=console +endif + +DEPLIBS= + +EXTRA_LIBS_DEP = + +EXTRA_LIBS = + +ifeq ($(ARCH), WINNT) +EXTRA_LIBS += user32.lib +endif + +DNP_SIM = $(addsuffix $(EXE_SUFFIX), \ + $(addprefix $(BINDIR)/, dnp_sim)) + + +all: $(OBJDEST) $(BINDIR) $(DNP_SIM) + +$(DNP_SIM): $(OBJDEST)/dnp_sim3.o $(EXTRA_LIBS_DEP) + $(LINK_EXE) $(OBJDEST)/dnp_sim3.o \ + $(EXTRA_LIBS) $< + + +$(OBJDEST): + $(MKDIR) $(OBJDEST) + +$(BINDIR): + $(MKDIR) $(BINDIR) + +clean: + -$(RM) $(ALL_OBJS) + -$(RM) $(BINS) |