replmd: parsed_dn_find() finds insertion point as well as exact hit
authorDouglas Bagnall <douglas.bagnall@catalyst.net.nz>
Wed, 28 Dec 2016 23:12:23 +0000 (12:12 +1300)
committerDouglas Bagnall <dbagnall@samba.org>
Thu, 9 Feb 2017 02:17:15 +0000 (03:17 +0100)
This will allow us to maintain the list of links in sorted order.

Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>
source4/dsdb/samdb/ldb_modules/repl_meta_data.c

index c9deb36c66df408a5ffab81bb3bfb32d2d4cd200..46f29942d847e3218f317a40bc931bdbfa34535d 100644 (file)
@@ -1794,35 +1794,134 @@ struct parsed_dn {
        struct ldb_val *v;
 };
 
+struct compare_ctx {
+       struct GUID *guid;
+       struct ldb_context *ldb;
+       TALLOC_CTX *mem_ctx;
+       const char *ldap_oid;
+       int err;
+       const struct GUID *invocation_id;
+};
+
+
 static int parsed_dn_compare(struct parsed_dn *pdn1, struct parsed_dn *pdn2)
 {
        return GUID_compare(&pdn1->guid, &pdn2->guid);
 }
 
-static int GUID_compare_struct(struct GUID *g1, struct GUID g2)
+static int la_guid_compare_with_trusted_dn(struct compare_ctx *ctx,
+                                          struct parsed_dn *p)
 {
-       return GUID_compare(g1, &g2);
+       /*
+        * This works like a standard compare function in its return values,
+        * but has an extra trick to deal with errors: zero is returned and
+        * ctx->err is set to the ldb error code.
+        *
+        * That is, if (as is expected in most cases) you get a non-zero
+        * result, you don't need to check for errors.
+        */
+       NTSTATUS status;
+
+       if (GUID_all_zero(&p->guid)) {
+
+               status = dsdb_get_extended_dn_guid(p->dsdb_dn->dn, &p->guid, "GUID");
+               if (!NT_STATUS_IS_OK(status)) {
+                       ctx->err = LDB_ERR_OPERATIONS_ERROR;
+                       return 0;
+               }
+       }
+
+       return GUID_compare(ctx->guid, &p->guid);
 }
 
-static struct parsed_dn *parsed_dn_find(struct parsed_dn *pdn,
-                                       unsigned int count, struct GUID *guid,
-                                       struct ldb_dn *dn)
+
+
+static int parsed_dn_find(struct ldb_context *ldb, struct parsed_dn *pdn,
+                         unsigned int count,
+                         struct GUID *guid,
+                         struct ldb_dn *target_dn,
+                         struct parsed_dn **exact,
+                         struct parsed_dn **next,
+                         const char *ldap_oid)
 {
-       struct parsed_dn *ret;
        unsigned int i;
-       if (dn && GUID_all_zero(guid)) {
-               /* when updating a link using DRS, we sometimes get a
-                  NULL GUID. We then need to try and match by DN */
-               for (i=0; i<count; i++) {
-                       if (ldb_dn_compare(pdn[i].dsdb_dn->dn, dn) == 0) {
-                               dsdb_get_extended_dn_guid(pdn[i].dsdb_dn->dn, guid, "GUID");
-                               return &pdn[i];
+       struct compare_ctx ctx;
+       if (pdn == NULL) {
+               *exact = NULL;
+               *next = NULL;
+               return LDB_SUCCESS;
+       }
+
+       if (unlikely(GUID_all_zero(guid))) {
+               /*
+                * When updating a link using DRS, we sometimes get a NULL
+                * GUID when a forward link has been deleted and its GUID has
+                * for some reason been forgotten. The best we can do is try
+                * and match by DN via a linear search. Note that this
+                * probably only happens in the ADD case, in which we only
+                * allow modification of link if it is already deleted, so
+                * this seems very close to an elaborate NO-OP, but we are not
+                * quite prepared to declare it so.
+                *
+                * If the DN is not in our list, we have to add it to the
+                * beginning of the list, where it would naturally sort.
+                */
+               struct parsed_dn *p;
+               if (target_dn == NULL) {
+                       /* We don't know the target DN, so we can't search for DN */
+                       DEBUG(1, ("parsed_dn_find has a NULL GUID for a linked "
+                                 "attribute but we don't have a DN to compare "
+                                 "it with\n"));
+                       return LDB_ERR_OPERATIONS_ERROR;
+               }
+               *exact = NULL;
+               *next = NULL;
+
+               DEBUG(3, ("parsed_dn_find has a NULL GUID for a link to DN "
+                         "%s; searching through links for it",
+                         ldb_dn_get_linearized(target_dn)));
+
+               for (i = 0; i < count; i++) {
+                       int cmp;
+                       p = &pdn[i];
+                       cmp = ldb_dn_compare(p->dsdb_dn->dn, target_dn);
+                       if (cmp == 0) {
+                               dsdb_get_extended_dn_guid(p->dsdb_dn->dn,
+                                                         &p->guid, "GUID");
+                               *exact = p;
+                               return LDB_SUCCESS;
                        }
                }
-               return NULL;
+               /*
+                * Here we have a null guid which doesn't match any existing
+                * link. This is a bit unexpected because null guids occur
+                * when a forward link has been deleted and we are replicating
+                * that deletion.
+                *
+                * The best thing to do is weep into the logs and add the
+                * offending link to the beginning of the list which is
+                * at least the correct sort position.
+                */
+               DEBUG(1, ("parsed_dn_find has been given a NULL GUID for a "
+                         "link to unknown DN %s\n",
+                         ldb_dn_get_linearized(target_dn)));
+               *next = pdn;
+               return LDB_SUCCESS;
        }
-       BINARY_ARRAY_SEARCH(pdn, count, guid, guid, GUID_compare_struct, ret);
-       return ret;
+
+       ctx.guid = guid;
+       ctx.ldb = ldb;
+       ctx.mem_ctx = pdn;
+       ctx.ldap_oid = ldap_oid;
+       ctx.err = 0;
+
+       BINARY_ARRAY_SEARCH_GTE(pdn, count, &ctx, la_guid_compare_with_trusted_dn,
+                               *exact, *next);
+
+       if (ctx.err != 0) {
+               return ctx.err;
+       }
+       return LDB_SUCCESS;
 }
 
 /*
@@ -2188,7 +2287,17 @@ static int replmd_modify_la_add(struct ldb_module *module,
 
        /* for each new value, see if it exists already with the same GUID */
        for (i=0; i<el->num_values; i++) {
-               struct parsed_dn *p = parsed_dn_find(old_dns, old_num_values, &dns[i].guid, NULL);
+               struct parsed_dn *p;
+               struct parsed_dn *next;
+               int err = parsed_dn_find(ldb, old_dns, old_num_values,
+                                        &dns[i].guid,
+                                        dns[i].dsdb_dn->dn,
+                                        &p, &next,
+                                        schema_attr->syntax->ldap_oid);
+               if (err != LDB_SUCCESS) {
+                       talloc_free(tmp_ctx);
+                       return err;
+               }
                if (p == NULL) {
                        /* this is a new linked attribute value */
                        new_values = talloc_realloc(tmp_ctx, new_values, struct ldb_val, num_new_values+1);
@@ -2208,7 +2317,6 @@ static int replmd_modify_la_add(struct ldb_module *module,
                        /* this is only allowed if the GUID was
                           previously deleted. */
                        uint32_t rmd_flags = dsdb_dn_rmd_flags(p->dsdb_dn->dn);
-
                        if (!(rmd_flags & DSDB_RMD_FLAG_DELETED)) {
                                struct GUID_txt_buf guid_str;
                                ldb_asprintf_errstring(ldb, "Attribute %s already exists for target GUID %s",
@@ -2347,9 +2455,18 @@ static int replmd_modify_la_delete(struct ldb_module *module,
        for (i=0; i < num_to_delete; i++) {
                struct parsed_dn *p = &dns[i];
                struct parsed_dn *p2;
+               struct parsed_dn *next = NULL;
                uint32_t rmd_flags;
+               ret = parsed_dn_find(ldb, old_dns, old_el->num_values,
+                                    &p->guid,
+                                    NULL,
+                                    &p2, &next,
+                                    schema_attr->syntax->ldap_oid);
+               if (ret != LDB_SUCCESS) {
+                       talloc_free(tmp_ctx);
+                       return ret;
+               }
 
-               p2 = parsed_dn_find(old_dns, old_el->num_values, &p->guid, NULL);
                if (!p2) {
                        struct GUID_txt_buf buf;
                        ldb_asprintf_errstring(ldb, "Attribute %s doesn't exist for target GUID %s",
@@ -2405,8 +2522,20 @@ static int replmd_modify_la_delete(struct ldb_module *module,
                } else {
                        unsigned int num_values = 0;
                        unsigned int j = 0;
+                       struct parsed_dn *exact = NULL, *next = NULL;
+
                        for (i = 0; i < old_el->num_values; i++) {
-                               if (parsed_dn_find(dns, num_to_delete, &old_dns[i].guid, NULL) != NULL) {
+                               ret = parsed_dn_find(ldb, dns, num_to_delete,
+                                                    &old_dns[i].guid,
+                                                    NULL,
+                                                    &exact, &next,
+                                                    schema_attr->syntax->ldap_oid);
+                               if (ret != LDB_SUCCESS) {
+                                       talloc_free(tmp_ctx);
+                                       return ret;
+                               }
+
+                               if (exact != NULL) {
                                        /* The element is in the delete list.
                                           mark it dead. */
                                        ret = replmd_add_backlink(module,
@@ -2444,10 +2573,22 @@ static int replmd_modify_la_delete(struct ldb_module *module,
                */
                for (i=0; i<old_el->num_values; i++) {
                        struct parsed_dn *p = &old_dns[i];
+                       struct parsed_dn *exact = NULL, *next = NULL;
                        uint32_t rmd_flags;
 
-                       if (num_to_delete && parsed_dn_find(dns, num_to_delete, &p->guid, NULL) == NULL) {
-                               continue;
+                       if (num_to_delete != 0) {
+                               ret = parsed_dn_find(ldb, dns, num_to_delete,
+                                                    &p->guid,
+                                                    NULL,
+                                                    &exact, &next,
+                                                    schema_attr->syntax->ldap_oid);
+                               if (ret != LDB_SUCCESS) {
+                                       talloc_free(tmp_ctx);
+                                       return ret;
+                               }
+                               if (exact == NULL) {
+                                       continue;
+                               }
                        }
 
                        rmd_flags = dsdb_dn_rmd_flags(p->dsdb_dn->dn);
@@ -2540,7 +2681,7 @@ static int replmd_modify_la_replace(struct ldb_module *module,
        /* mark all the old ones as deleted */
        for (i=0; i<old_num_values; i++) {
                struct parsed_dn *old_p = &old_dns[i];
-               struct parsed_dn *p;
+               struct parsed_dn *exact = NULL, *next = NULL;
                uint32_t rmd_flags = dsdb_dn_rmd_flags(old_p->dsdb_dn->dn);
 
                if (rmd_flags & DSDB_RMD_FLAG_DELETED) continue;
@@ -2553,8 +2694,16 @@ static int replmd_modify_la_replace(struct ldb_module *module,
                        return ret;
                }
 
-               p = parsed_dn_find(dns, el->num_values, &old_p->guid, NULL);
-               if (p) {
+               ret = parsed_dn_find(ldb, dns, el->num_values,
+                                    &old_p->guid,
+                                    NULL,
+                                    &exact, &next,
+                                    schema_attr->syntax->ldap_oid);
+               if (ret != LDB_SUCCESS) {
+                       talloc_free(tmp_ctx);
+                       return ret;
+               }
+               if (exact) {
                        /* we don't delete it if we are re-adding it */
                        continue;
                }
@@ -2571,11 +2720,22 @@ static int replmd_modify_la_replace(struct ldb_module *module,
         * to old_el
        */
        for (i=0; i<el->num_values; i++) {
-               struct parsed_dn *p = &dns[i], *old_p;
+               struct parsed_dn *p = &dns[i];
+               struct parsed_dn *old_p = NULL, *next = NULL;
+
+               if (old_dns) {
+                       ret = parsed_dn_find(ldb, old_dns, old_num_values,
+                                            &p->guid,
+                                            NULL,
+                                            &old_p, &next,
+                                            schema_attr->syntax->ldap_oid);
+                       if (ret != LDB_SUCCESS) {
+                               talloc_free(tmp_ctx);
+                               return ret;
+                       }
+               }
 
-               if (old_dns &&
-                   (old_p = parsed_dn_find(old_dns,
-                                           old_num_values, &p->guid, NULL)) != NULL) {
+               if (old_p != NULL) {
                        /* update in place */
                        ret = replmd_update_la_val(old_el->values, old_p->v, p->dsdb_dn,
                                                   old_p->dsdb_dn, invocation_id,
@@ -6135,7 +6295,7 @@ static int replmd_process_linked_attribute(struct ldb_module *module,
        struct ldb_result *target_res;
        const char *attrs[4];
        const char *attrs2[] = { "isDeleted", "isRecycled", NULL };
-       struct parsed_dn *pdn_list, *pdn;
+       struct parsed_dn *pdn_list, *pdn, *next;
        struct GUID guid = GUID_zero();
        NTSTATUS ntstatus;
        bool active = (la->flags & DRSUAPI_DS_LINKED_ATTRIBUTE_FLAG_ACTIVE)?true:false;
@@ -6359,7 +6519,17 @@ linked_attributes[0]:
        }
 
        /* see if this link already exists */
-       pdn = parsed_dn_find(pdn_list, old_el->num_values, &guid, dsdb_dn->dn);
+       ret = parsed_dn_find(ldb, pdn_list, old_el->num_values,
+                            &guid,
+                            dsdb_dn->dn,
+                            &pdn, &next,
+                            attr->syntax->ldap_oid);
+       if (ret != LDB_SUCCESS) {
+               talloc_free(tmp_ctx);
+               return ret;
+       }
+
+
        if (pdn != NULL) {
                /* see if this update is newer than what we have already */
                struct GUID invocation_id = GUID_zero();