#50132 Ticket 49658 - In replicated topology a single-valued attribute can diverge
Closed 3 years ago by spichugi. Opened 5 years ago by tbordaz.
tbordaz/389-ds-base ticket_49658  into  master

The added file is too large to be shown here, see it at: dirsrvtests/tests/tickets/ticket49658_test.py
file modified
+257 -147
@@ -359,6 +359,13 @@ 

   * Preserves LDAP Information Model constraints,

   * returning an LDAP result code.

   */

+ static void entry_dump_stateinfo(char *msg, Slapi_Entry* e);

+ static Slapi_Value *attr_most_recent_deleted_value(Slapi_Attr *a);

+ static void resolve_single_valued_two_values(Slapi_Entry *e, Slapi_Attr *a, int attribute_state, Slapi_Value *current_value, Slapi_Value *second_current_value);

+ static void resolve_single_valued_check_restore_deleted_value(Slapi_Entry *e, Slapi_Attr *a);

+ static void resolve_single_valued_zap_current(Slapi_Entry *e, Slapi_Attr *a);

+ static void resolve_single_valued_set_adcsn(Slapi_Attr *a);

+ static void resolve_single_valued_zap_deleted(Slapi_Attr *a);

  static void resolve_attribute_state_single_valued(Slapi_Entry *e, Slapi_Attr *a, int attribute_state);

  static void resolve_attribute_state_deleted_to_present(Slapi_Entry *e, Slapi_Attr *a, Slapi_Value **valuestoupdate);

  static void resolve_attribute_state_present_to_deleted(Slapi_Entry *e, Slapi_Attr *a, Slapi_Value **valuestoupdate);
@@ -387,6 +394,20 @@ 

      return retVal;

  }

  

+ /* Used for debug purpose, it dumps into the error log the

+  * entry with the replication stateinfo

+  */

+ static void

+ entry_dump_stateinfo(char *msg, Slapi_Entry* e)

+ {

+ 	char *s;

+ 	int32_t len = 0;

+ 

+ 	s = slapi_entry2str_with_options(e, &len, SLAPI_DUMP_STATEINFO);

+ 	slapi_log_err(SLAPI_LOG_ERR, msg, "%s\n", s);

+ 	slapi_ch_free((void **)&s);

+ }

+ 

  static int

  entry_add_present_values_wsi_single_valued(Slapi_Entry *e, const char *type, struct berval **bervals, const CSN *csn, int urp, long flags)

  {
@@ -705,6 +726,10 @@ 

                  /* The attribute is single valued and the value was successful deleted */

                  /* but there could have been an add in the same operation, so double check */

                  if (valueset_isempty(&a->a_present_values)) {

+                     /* A doubt here, a direct update deletes the last value

If we have a doubt, we could put in a PR_ASSERT to try and catch any possible concerns during testing and devel if we think it could be an issue?

I think my concern was invalid.

Deleting the last value of an attribute (CSN_A) moves the attribute to the set of deleted attribute but not that the attribute was deleted at CSN_A.
If on an other master, a value is added with a CSN_B < CSN_A this value will move back the attribute to the present list. That is the expected behavior.
But if the attribute deletion was set on CSN_A, then the CSN_B update will be discard.

Note this behavior is the same on single/multi valued attribute

+                      * of a single valued attribute. It will only contain deleted values.

+                      * Why not setting the adcsn (attr_set_deletion_csn) ?

+                      */

                      entry_present_attribute_to_deleted_attribute(e, a);

                  }

              } else if (retVal != LDAP_SUCCESS) {
@@ -1229,169 +1254,254 @@ 

      }

  }

  

- static void

- resolve_attribute_state_single_valued(Slapi_Entry *e, Slapi_Attr *a, int attribute_state)

+ /* Retrieve from the deleted values the one that

+  * was the most recently deleted. Based on its vdcsn

+  */

+ static Slapi_Value *

+ attr_most_recent_deleted_value(Slapi_Attr *a)

  {

-     Slapi_Value *current_value = NULL;

-     Slapi_Value *pending_value = NULL;

-     Slapi_Value *new_value = NULL;

-     const CSN *current_value_vucsn;

-     const CSN *pending_value_vucsn;

-     const CSN *pending_value_vdcsn;

-     const CSN *adcsn;

+     Slapi_Value *v, *most_recent_v;

I think 'i' can not be a size_t , it is used for attr_first_deleted_value/attr_next_deleted_value that returns -1 when there is no more value.

      int i;

I don't expect you to change this, but this could be a size_t for futureproofing and correctness.

+     CSN *vdcsn, *most_recent_vdcsn;

  

-     /*

-      * this call makes sure that the attribute does not have a pending_value

-      * or deletion_csn which is before the current_value.

-      */

-     i = slapi_attr_first_value(a, &current_value);

-     if (i != -1) {

-         slapi_attr_next_value(a, i, &new_value);

-     }

-     attr_first_deleted_value(a, &pending_value);

-     /* purge_attribute_state_single_valued */

-     adcsn = attr_get_deletion_csn(a);

-     current_value_vucsn = value_get_csn(current_value, CSN_TYPE_VALUE_UPDATED);

-     pending_value_vucsn = value_get_csn(pending_value, CSN_TYPE_VALUE_UPDATED);

-     pending_value_vdcsn = value_get_csn(pending_value, CSN_TYPE_VALUE_DELETED);

-     if ((pending_value != NULL && (csn_compare(adcsn, pending_value_vucsn) < 0)) ||

-         (pending_value == NULL && (csn_compare(adcsn, current_value_vucsn) < 0))) {

-         attr_set_deletion_csn(a, NULL);

-         adcsn = NULL;

+     vdcsn = NULL;

+     most_recent_vdcsn = NULL;

+     i = attr_first_deleted_value(a, &v);

+     most_recent_v = v;

+ 

+     while (i != -1) {

+         vdcsn = value_get_csn(v, CSN_TYPE_VALUE_DELETED);

+ 

+         if (csn_compare((const CSN *)most_recent_vdcsn, (const CSN *)vdcsn) < 0) {

+             most_recent_v = v;

+             most_recent_vdcsn = vdcsn;

+         }

+         i = attr_next_deleted_value(a, i, &v);

      }

+     return most_recent_v;

+ }

  

-     /* in the case of the following:

-      * add: value2

-      * delete: value1

-      * we will have current_value with VUCSN CSN1

-      * and pending_value with VDCSN CSN2

-      * and new_value == NULL

-      * current_value != pending_value

-      * and

-      * VUCSN == VDCSN (ignoring subseq)

-      * even though value1.VDCSN > value2.VUCSN

-      * value2 should still win because the value is _different_

-      */

-     if (current_value && pending_value && !new_value && !adcsn &&

-         (0 != slapi_value_compare(a, current_value, pending_value)) &&

-         (0 == csn_compare_ext(current_value_vucsn, pending_value_vdcsn, CSN_COMPARE_SKIP_SUBSEQ))) {

-         /* just remove the deleted value */

-         entry_deleted_value_to_zapped_value(a, pending_value);

-         pending_value = NULL;

-     } else if (current_value && pending_value && !new_value && adcsn &&

-                (attribute_state == ATTRIBUTE_DELETED) &&

-                current_value_vucsn && !pending_value_vucsn && pending_value_vdcsn &&

-                (csn_compare(current_value_vucsn, pending_value_vdcsn) > 0) &&

-                (csn_compare(adcsn, pending_value_vdcsn) == 0)) {

-         /* in the case of the following:

-          * beginning attr state is a deleted value

-          * incoming operation is

-          * add: newvalue

-          * attribute_state is ATTRIBUTE_DELETED

-          * so we have both a current_value and a pending_value

-          * new_value is NULL

-          * current_value_vucsn is CSN1

-          * pending_value_vucsn is NULL

-          * pending_value_vdcsn is CSN2

-          * adcsn is CSN2 == pending_value_vdcsn

-          * CSN1 > CSN2

-          * since the pending_value is deleted, and the current_value has

-          * a greater CSN, we should keep the current_value and zap

-          * the pending_value

+ /* This routine applies for single valued attribute.

+  * The attribute has two current values, it keeps the most recent one

+  * and zap the oldest

+  */

+ static void

+ resolve_single_valued_two_values(Slapi_Entry *e, Slapi_Attr *a, int attribute_state, Slapi_Value *current_value, Slapi_Value *second_current_value)

+ {

+ 

+     CSN *current_value_vucsn;

+     CSN *second_current_value_vucsn;

+     Slapi_Value *value_to_zap;

+     

+     current_value_vucsn = value_get_csn(current_value, CSN_TYPE_VALUE_UPDATED);

+     second_current_value_vucsn = value_get_csn(second_current_value, CSN_TYPE_VALUE_UPDATED);

+     

+     /* First determine which present value will be zapped */

+     if (csn_compare((const CSN *)second_current_value_vucsn, (const CSN *)current_value_vucsn) < 0) {

+         /*

+          * The second value is older but was distinguished at the time the current value was added

+          * then the second value should become current

           */

-         /* just remove the deleted value */

-         entry_deleted_value_to_zapped_value(a, pending_value);

-         /* move the attribute to the present attributes list */

-         entry_deleted_attribute_to_present_attribute(e, a);

-         pending_value = NULL;

-         attr_set_deletion_csn(a, NULL);

-         return; /* we are done - we are keeping the present value */

-     } else if (new_value == NULL) {

-         /* check if the pending value should become the current value */

-         if (pending_value != NULL) {

-             if (!value_distinguished_at_csn(e, a, current_value, pending_value_vucsn)) {

-                 /* attribute.current_value = attribute.pending_value; */

-                 /* attribute.pending_value = NULL; */

-                 entry_present_value_to_zapped_value(a, current_value);

-                 entry_deleted_value_to_present_value(a, pending_value);

-                 current_value = pending_value;

-                 pending_value = NULL;

-                 current_value_vucsn = pending_value_vucsn;

-                 pending_value_vucsn = NULL;

-             }

+         if (value_distinguished_at_csn(e, a, second_current_value, (const CSN *)current_value_vucsn)) {

+             value_to_zap = current_value;

+         } else {

+             /* The second value being not distinguished, zap it as it is a single valued attribute */

+             value_to_zap = second_current_value;

          }

-         /* check if the current value should be deleted */

-         if (current_value != NULL) {

-             if (csn_compare(adcsn, current_value_vucsn) > 0) /* check if the attribute was deleted after the value was last updated */

-             {

-                 if (!value_distinguished_at_csn(e, a, current_value, current_value_vucsn)) {

-                     entry_present_value_to_zapped_value(a, current_value);

-                     current_value = NULL;

-                     current_value_vucsn = NULL;

-                 }

-             }

+         

+     } else {

+         /* Here the current_value is older than the second_current_value */

+         if (value_distinguished_at_csn(e, a, current_value, (const CSN *)second_current_value_vucsn)) {

+             /* current_value was distinguished at the time the second value was added

+              * then the current_value should become the current */

+             value_to_zap = second_current_value;

+         } else {

+             value_to_zap = current_value;

          }

-     } else /* addition of a new value */

-     {

-         const CSN *new_value_vucsn = value_get_csn(new_value, CSN_TYPE_VALUE_UPDATED);

-         if (csn_compare(new_value_vucsn, current_value_vucsn) < 0) {

-             /*

-              * if the new value was distinguished at the time the current value was added

-              * then the new value should become current

+     }

+     entry_present_value_to_zapped_value(a, value_to_zap);

+     

+ 

+ 

+ }

+ 

+ /* This routine applies for single valued attribute.

+  * It checks if the deleted value is more recent than

+  * the present one. If it is, it resurect the deleted value

+  *

+  * This function leaves untouch the adcsn

+  */

+ static void

+ resolve_single_valued_check_restore_deleted_value(Slapi_Entry *e, Slapi_Attr *a)

+ {

+     Slapi_Value *deleted_value = NULL;

+     Slapi_Value *current_value = NULL;

+ 

+     /* Retrieve the deleted and current value */

+     deleted_value = attr_most_recent_deleted_value(a);

+     if (deleted_value == NULL) {

+         return;

+     }

+     slapi_attr_first_value(a, &current_value);

+ 

+     if (current_value == NULL) {

+         /* An attribute needs a present value */

+         entry_deleted_value_to_present_value(a, deleted_value);

+     } else {

+         CSN *current_value_vucsn;

+         CSN *deleted_value_vucsn;

+         CSN *deleted_value_vdcsn;

+ 

+         deleted_value_vucsn = value_get_csn(deleted_value, CSN_TYPE_VALUE_UPDATED);

+         deleted_value_vdcsn = value_get_csn(deleted_value, CSN_TYPE_VALUE_DELETED);

+         current_value_vucsn = value_get_csn(current_value, CSN_TYPE_VALUE_UPDATED);

+         if (deleted_value_vucsn &&

+                 !value_distinguished_at_csn(e, a, current_value, (const CSN *)deleted_value_vucsn) &&

+                 (csn_compare((const CSN *)current_value_vucsn, (const CSN *)deleted_value_vucsn) < 0) &&

+                 (csn_compare((const CSN *)deleted_value_vdcsn, (const CSN *)current_value_vucsn) < 0)) {

+             /* the condition to resurrect the deleted value is 

+              *  - it is more recent than the current value

+              *  - its value was deleted before the current value

+              *  - the current value is not distinguished

               */

-             if (value_distinguished_at_csn(e, a, new_value, current_value_vucsn)) {

-                 /* attribute.pending_value = attribute.current_value  */

-                 /* attribute.current_value = new_value  */

-                 if (pending_value == NULL) {

-                     entry_present_value_to_deleted_value(a, current_value);

-                 } else {

-                     entry_present_value_to_zapped_value(a, current_value);

-                 }

-                 pending_value = current_value;

-                 current_value = new_value;

-                 new_value = NULL;

-                 pending_value_vucsn = current_value_vucsn;

-                 current_value_vucsn = new_value_vucsn;

-             } else {

-                 /* new_value= NULL */

-                 entry_present_value_to_zapped_value(a, new_value);

-                 new_value = NULL;

-             }

-         } else /* new value is after the current value */

-         {

-             if (!value_distinguished_at_csn(e, a, current_value, new_value_vucsn)) {

-                 /* attribute.current_value = new_value */

-                 entry_present_value_to_zapped_value(a, current_value);

-                 current_value = new_value;

-                 new_value = NULL;

-                 current_value_vucsn = new_value_vucsn;

-             } else /* value is distinguished - check if we should replace the current pending value */

-             {

-                 if (csn_compare(new_value_vucsn, pending_value_vucsn) > 0) {

-                     /* attribute.pending_value = new_value */

-                     entry_deleted_value_to_zapped_value(a, pending_value);

-                     entry_present_value_to_deleted_value(a, new_value);

-                     pending_value = new_value;

-                     new_value = NULL;

-                     pending_value_vucsn = new_value_vucsn;

-                 }

-             }

+             entry_present_value_to_zapped_value(a, current_value);

+             entry_deleted_value_to_present_value(a, deleted_value);

          }

      }

+ }

+ /* This function deals with single valued attribute

+  * It zap the current value if the adcsn is more recent and the value is not distinguished

+  */

+ static void

+ resolve_single_valued_zap_current(Slapi_Entry *e, Slapi_Attr *a)

+ {

+     Slapi_Value *current_value = NULL;

+     CSN *current_value_vucsn;

+     CSN *adcsn;

  

-     /*

-      * This call ensures that the attribute does not have a pending_value

-      * or a deletion_csn that is earlier than the current_value.

+     /* check if the current value should be deleted because 

+      * older than adcsn and not distinguished

       */

-     /* purge_attribute_state_single_valued */

-     if ((pending_value != NULL && (csn_compare(adcsn, pending_value_vucsn) < 0)) ||

-         (pending_value == NULL && (csn_compare(adcsn, current_value_vucsn) < 0))) {

+     slapi_attr_first_value(a, &current_value);

+     current_value_vucsn = value_get_csn(current_value, CSN_TYPE_VALUE_UPDATED);

+     adcsn = attr_get_deletion_csn(a);

+     if (current_value != NULL) {

+         if (csn_compare((const CSN *)adcsn, (const CSN *) current_value_vucsn) > 0) {

+             /* the attribute was deleted after the value was last updated */

+             if (!value_distinguished_at_csn(e, a, current_value, (const CSN *) current_value_vucsn)) {

+                 entry_present_value_to_zapped_value(a, current_value);

+             }

+         }

+     }

+ }

+ /* This function deals with single valued attribute

+  * It reset the adcsn if

+  * - there is no deleted value and current value is more recent than the adcsn

+  * - there is a deleted value and it is more recent than the adcsn

+  */

+ static void

+ resolve_single_valued_set_adcsn(Slapi_Attr *a)

+ {

+     Slapi_Value *deleted_value = NULL;

+     Slapi_Value *current_value = NULL;

+     CSN *current_value_vucsn;

+     CSN *deleted_value_vucsn;

+     CSN *adcsn;

+     

+     slapi_attr_first_value(a, &current_value);

+     current_value_vucsn = value_get_csn(current_value, CSN_TYPE_VALUE_UPDATED);

+     deleted_value = attr_most_recent_deleted_value(a);

+     deleted_value_vucsn = value_get_csn(deleted_value, CSN_TYPE_VALUE_UPDATED);

+     adcsn = attr_get_deletion_csn(a);

+     if ((deleted_value != NULL && (csn_compare(adcsn, (const CSN *) deleted_value_vucsn) < 0)) ||

+         (deleted_value == NULL && (csn_compare(adcsn, (const CSN *) current_value_vucsn) < 0))) {

          attr_set_deletion_csn(a, NULL);

-         adcsn = NULL;

      }

+ }

+ /* This function deals with single valued attribute

+  * It checks if the deleted value worth to be kept

+  * 

+  * deleted value is zapped if

+  * - it is the result of MOD_REPL that is older than current value

+  * - It is the result of MOD_DEL_<value> that is belong to the same operation that set the current value

+  */

+ static void

+ resolve_single_valued_zap_deleted(Slapi_Attr *a)

+ {

+     Slapi_Value *deleted_value = NULL;

+     Slapi_Value *current_value = NULL;

+     CSN *current_value_vucsn;

+     CSN *deleted_value_vucsn;

+     CSN *deleted_value_vdcsn;

+     CSN *deleted_value_csn;

+     PRBool deleted_on_mod_del = PR_FALSE; /* flag if a value was deleted specifically */

+ 

+     /* Now determine if the deleted value worth to be kept */

+     slapi_attr_first_value(a, &current_value);

+     current_value_vucsn = value_get_csn(current_value, CSN_TYPE_VALUE_UPDATED);

+ 

+     deleted_value = attr_most_recent_deleted_value(a);

+     deleted_value_vucsn = value_get_csn(deleted_value, CSN_TYPE_VALUE_UPDATED);

+     deleted_value_vdcsn = value_get_csn(deleted_value, CSN_TYPE_VALUE_DELETED);

+ 

+     /* get the appropriate csn to take into consideration: either from MOD_REPL or from MOD_DEL_specific */

+     if (csn_compare((const CSN *) deleted_value_vdcsn, (const CSN *) deleted_value_vucsn) <= 0) {

+         deleted_value_csn = deleted_value_vucsn;

+     } else {

+         deleted_value_csn = deleted_value_vdcsn;

+         if (0 == csn_compare_ext((const CSN *) current_value_vucsn, (const CSN *) deleted_value_vdcsn, CSN_COMPARE_SKIP_SUBSEQ)) {

+             /* the deleted value was specifically delete in the same operation that set the current value */

+             deleted_on_mod_del = PR_TRUE;

+         }

+     }

+     if ((csn_compare((const CSN *) deleted_value_csn, (const CSN *) current_value_vucsn) < 0) || deleted_on_mod_del) {

+         entry_deleted_value_to_zapped_value(a, deleted_value);

+     }

+ }

+ 

+ /* This function deals with single valued attribute

+  * It does a set of cleanup in the current/deleted values in order

+  * to conform the schema, take care of distinguished values and only preserve the

+  * values that worth to be kept.

+  */

+ static void

+ resolve_attribute_state_single_valued(Slapi_Entry *e, Slapi_Attr *a, int attribute_state)

+ {

+     int32_t nbval, i;

+     Slapi_Value *current_value = NULL;

+ 

+     /* retrieve the current value(s) */

+     slapi_attr_get_numvalues(a, &nbval);

+     i = slapi_attr_first_value(a, &current_value);

+ 

+     /* If there are several values, first determine which value will be the current (present) one */

+     if (nbval > 1) {

+         /* There are several values for a single valued attribute, keep the most recent one */

+         if (i == -1) {

+             slapi_log_err(SLAPI_LOG_ERR, "resolve_attribute_state_single_valued", "Unexpected state of %s that contains more than one value but can not read the second\n", a->a_type);

+         } else {

+             Slapi_Value *second_current_value = NULL;

+ 

+             slapi_attr_next_value(a, i, &second_current_value);

+             resolve_single_valued_two_values(e, a, attribute_state, current_value, second_current_value);                

+         }

+     }

+     /* There is only one current value (present value) */

+ 

+     /* Now determine if the deleted value needs to replace the current value */

+     resolve_single_valued_check_restore_deleted_value(e, a);

+ 

+     /* Now determine if the deleted value worth to be kept (vs. current value)  */

+     resolve_single_valued_zap_deleted(a);

+ 

+     /* Now determine if the current value worth to be kept (vs. adcsn) */

+     resolve_single_valued_zap_current(e, a);

+ 

+     /* Now set the adcsn */

+     resolve_single_valued_set_adcsn(a);

  

-     /* set attribute state */

+     /* set the attribute in the correct list in the entry: present or deleted  */

+     slapi_attr_first_value(a, &current_value);

      if (current_value == NULL) {

          if (attribute_state == ATTRIBUTE_PRESENT) {

              entry_present_attribute_to_deleted_attribute(e, a);

Bug Description:
When deleting a specific value of a single valued attribute,
the deleted value can be erronously resurrected.

Fix Description:
This second fix is a rewrite of entry state resolution.
The original function (resolve_attribute_state_single_valued) implemented
a main algorythm but it was heavily merged with resolution of specific cases.
It was too difficult to make the function understandable and preserving
the handling of the specific cases.
The risk of that rewrite fix is that I can not guarantee it fully covers
the set of specific cases

https://pagure.io/389-ds-base/issue/49658

Reviewed by: ?

Platforms tested: F27

Flag Day: no

Doc impact: no

These shhouldn't be const because you immediately change them ;) if they need to be const, for the functions you call, then you probably should
cast as const at the function call

I think the rewrite looks very nice, a few C related changes though, but great :)

rebased onto 88ad2e29324f379c015fe75250a0e2eff1df53d2

5 years ago

@firstyear Thank you sooo much for having look at this long patch.
I fixed your remarks. in the previous rebase

Is CSN_String actually 100 bytes long? Or is this just a guess at how long it could be? Is there a risk this could overrun?

Thanks mate for the update. Two more little things, but otherwise it looks good :)

rebased onto 47b83246f12d7bcc9bf136d7f14e29bfe99c231c

5 years ago

Thanks, I change the patch (csn_string useless, int->int32_t, remove a debug message)

I realize the patch is somehow complex and it is almost impossible to be sure it covers the various cases handled by the former code. Cleaning this part of code was intentional and it would be great to have it upstream. If it introduces regression, at least we will have a clearer algo to fix ;). Any volunteer ?

If we have a doubt, we could put in a PR_ASSERT to try and catch any possible concerns during testing and devel if we think it could be an issue?

I don't expect you to change this, but this could be a size_t for futureproofing and correctness.

Two very minor comments, but otherwise I think this code looks good :) So ack from me if you want, or you can apply the comments and I'll check again. :)

I think my concern was invalid.

Deleting the last value of an attribute (CSN_A) moves the attribute to the set of deleted attribute but not that the attribute was deleted at CSN_A.
If on an other master, a value is added with a CSN_B < CSN_A this value will move back the attribute to the present list. That is the expected behavior.
But if the attribute deletion was set on CSN_A, then the CSN_B update will be discard.

Note this behavior is the same on single/multi valued attribute

I think 'i' can not be a size_t , it is used for attr_first_deleted_value/attr_next_deleted_value that returns -1 when there is no more value.

rebased onto e09725e

5 years ago

Pull-Request has been merged by tbordaz

5 years ago

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This pull request has been cloned to Github as issue and is available here:
- https://github.com/389ds/389-ds-base/issues/3191

If you want to continue to work on the PR, please navigate to the github issue,
download the patch from the attachments and file a new pull request.

Thank you for understanding. We apologize for all inconvenience.

Pull-Request has been closed by spichugi

3 years ago