ldb: relatively efficient functions for finding duplicate values
[samba.git] / lib / ldb / ldb_tdb / ldb_tdb.c
index 6a91f053f64d722f068b8459942f43fc579c0e07..1822ea01a08380e8f43899c4aee335fdf265bdfb 100644 (file)
@@ -330,7 +330,7 @@ static int ltdb_add_internal(struct ldb_module *module,
 {
        struct ldb_context *ldb = ldb_module_get_ctx(module);
        int ret = LDB_SUCCESS;
-       unsigned int i, j;
+       unsigned int i;
 
        for (i=0;i<msg->num_elements;i++) {
                struct ldb_message_element *el = &msg->elements[i];
@@ -355,12 +355,23 @@ static int ltdb_add_internal(struct ldb_module *module,
                        continue;
                }
 
-               /* TODO: This is O(n^2) - replace with more efficient check */
-               for (j=0; j<el->num_values; j++) {
-                       if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
-                               ldb_asprintf_errstring(ldb,
-                                                      "attribute '%s': value #%u on '%s' provided more than once",
-                                                      el->name, j, ldb_dn_get_linearized(msg->dn));
+               if (check_single_value) {
+                       struct ldb_val *duplicate = NULL;
+
+                       ret = ldb_msg_find_duplicate_val(ldb, discard_const(msg),
+                                                        el, &duplicate, 0);
+                       if (ret != LDB_SUCCESS) {
+                               return ret;
+                       }
+                       if (duplicate != NULL) {
+                               ldb_asprintf_errstring(
+                                       ldb,
+                                       "attribute '%s': value '%.*s' on '%s' "
+                                       "provided more than once in ADD object",
+                                       el->name,
+                                       (int)duplicate->length,
+                                       duplicate->data,
+                                       ldb_dn_get_linearized(msg->dn));
                                return LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
                        }
                }
@@ -449,7 +460,7 @@ static int ltdb_delete_internal(struct ldb_module *module, struct ldb_dn *dn)
 
        /* in case any attribute of the message was indexed, we need
           to fetch the old record */
-       ret = ltdb_search_dn1(module, dn, msg);
+       ret = ltdb_search_dn1(module, dn, msg, LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC);
        if (ret != LDB_SUCCESS) {
                /* not finding the old record is an error */
                goto done;
@@ -522,8 +533,7 @@ static int find_element(const struct ldb_message *msg, const char *name)
 
   returns 0 on success, -1 on failure (and sets errno)
 */
-static int ltdb_msg_add_element(struct ldb_context *ldb,
-                               struct ldb_message *msg,
+static int ltdb_msg_add_element(struct ldb_message *msg,
                                struct ldb_message_element *el)
 {
        struct ldb_message_element *e2;
@@ -567,7 +577,6 @@ static int ltdb_msg_add_element(struct ldb_context *ldb,
   delete all elements having a specified attribute name
 */
 static int msg_delete_attribute(struct ldb_module *module,
-                               struct ldb_context *ldb,
                                struct ldb_message *msg, const char *name)
 {
        unsigned int i;
@@ -634,7 +643,7 @@ static int msg_delete_element(struct ldb_module *module,
                }
                if (matched) {
                        if (el->num_values == 1) {
-                               return msg_delete_attribute(module, ldb, msg, name);
+                               return msg_delete_attribute(module, msg, name);
                        }
 
                        ret = ltdb_index_del_value(module, msg->dn, el, i);
@@ -679,7 +688,7 @@ int ltdb_modify_internal(struct ldb_module *module,
        TDB_DATA tdb_key, tdb_data;
        struct ldb_val ldb_data;
        struct ldb_message *msg2;
-       unsigned int i, j, k;
+       unsigned int i, j;
        int ret = LDB_SUCCESS, idx;
        struct ldb_control *control_permissive = NULL;
 
@@ -725,6 +734,10 @@ int ltdb_modify_internal(struct ldb_module *module,
                struct ldb_val *vals;
                const struct ldb_schema_attribute *a = ldb_schema_attribute_by_name(ldb, el->name);
                const char *dn;
+               uint32_t options = 0;
+               if (control_permissive != NULL) {
+                       options |= LDB_MSG_FIND_COMMON_REMOVE_DUPLICATES;
+               }
 
                switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
                case LDB_FLAG_MOD_ADD:
@@ -769,7 +782,7 @@ int ltdb_modify_internal(struct ldb_module *module,
                        /* Checks if element already exists */
                        idx = find_element(msg2, el->name);
                        if (idx == -1) {
-                               if (ltdb_msg_add_element(ldb, msg2, el) != 0) {
+                               if (ltdb_msg_add_element(msg2, el) != 0) {
                                        ret = LDB_ERR_OTHER;
                                        goto done;
                                }
@@ -793,30 +806,43 @@ int ltdb_modify_internal(struct ldb_module *module,
 
                                /* Check that values don't exist yet on multi-
                                   valued attributes or aren't provided twice */
-                               /* TODO: This is O(n^2) - replace with more efficient check */
-                               for (j = 0; j < el->num_values; j++) {
-                                       if (ldb_msg_find_val(el2, &el->values[j]) != NULL) {
-                                               if (control_permissive) {
-                                                       /* remove this one as if it was never added */
-                                                       el->num_values--;
-                                                       for (k = j; k < el->num_values; k++) {
-                                                               el->values[k] = el->values[k + 1];
-                                                       }
-                                                       j--; /* rewind */
-
-                                                       continue;
-                                               }
-
+                               if (!(el->flags &
+                                     LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK)) {
+                                       struct ldb_val *duplicate = NULL;
+                                       ret = ldb_msg_find_common_values(ldb,
+                                                                        msg2,
+                                                                        el,
+                                                                        el2,
+                                                                        options);
+
+                                       if (ret ==
+                                           LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS) {
                                                ldb_asprintf_errstring(ldb,
-                                                                      "attribute '%s': value #%u on '%s' already exists",
-                                                                      el->name, j, ldb_dn_get_linearized(msg2->dn));
-                                               ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+                                                       "attribute '%s': value "
+                                                       "#%u on '%s' already "
+                                                       "exists", el->name, j,
+                                                       ldb_dn_get_linearized(msg2->dn));
+                                               goto done;
+                                       } else if (ret != LDB_SUCCESS) {
                                                goto done;
                                        }
-                                       if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
-                                               ldb_asprintf_errstring(ldb,
-                                                                      "attribute '%s': value #%u on '%s' provided more than once",
-                                                                      el->name, j, ldb_dn_get_linearized(msg2->dn));
+
+                                       ret = ldb_msg_find_duplicate_val(
+                                               ldb, msg2, el, &duplicate, 0);
+                                       if (ret != LDB_SUCCESS) {
+                                               goto done;
+                                       }
+                                       if (duplicate != NULL) {
+                                               ldb_asprintf_errstring(
+                                                       ldb,
+                                                       "attribute '%s': value "
+                                                       "'%.*s' on '%s' "
+                                                       "provided more than "
+                                                       "once in ADD",
+                                                       el->name,
+                                                       (int)duplicate->length,
+                                                       duplicate->data,
+                                                       ldb_dn_get_linearized(msg->dn));
                                                ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
                                                goto done;
                                        }
@@ -858,12 +884,30 @@ int ltdb_modify_internal(struct ldb_module *module,
                                goto done;
                        }
 
-                       /* TODO: This is O(n^2) - replace with more efficient check */
-                       for (j=0; j<el->num_values; j++) {
-                               if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
-                                       ldb_asprintf_errstring(ldb,
-                                                              "attribute '%s': value #%u on '%s' provided more than once",
-                                                              el->name, j, ldb_dn_get_linearized(msg2->dn));
+                       /*
+                        * We don't need to check this if we have been
+                        * pre-screened by the repl_meta_data module
+                        * in Samba, or someone else who can claim to
+                        * know what they are doing. 
+                        */
+                       if (!(el->flags & LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK)) {
+                               struct ldb_val *duplicate = NULL;
+
+                               ret = ldb_msg_find_duplicate_val(ldb, msg2, el,
+                                                                &duplicate, 0);
+                               if (ret != LDB_SUCCESS) {
+                                       goto done;
+                               }
+                               if (duplicate != NULL) {
+                                       ldb_asprintf_errstring(
+                                               ldb,
+                                               "attribute '%s': value '%.*s' "
+                                               "on '%s' provided more than "
+                                               "once in REPLACE",
+                                               el->name,
+                                               (int)duplicate->length,
+                                               duplicate->data,
+                                               ldb_dn_get_linearized(msg2->dn));
                                        ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
                                        goto done;
                                }
@@ -887,7 +931,7 @@ int ltdb_modify_internal(struct ldb_module *module,
                                }
 
                                /* Delete the attribute if it exists in the DB */
-                               if (msg_delete_attribute(module, ldb, msg2,
+                               if (msg_delete_attribute(module, msg2,
                                                         el->name) != 0) {
                                        ret = LDB_ERR_OTHER;
                                        goto done;
@@ -895,7 +939,7 @@ int ltdb_modify_internal(struct ldb_module *module,
                        }
 
                        /* Recreate it with the new values */
-                       if (ltdb_msg_add_element(ldb, msg2, el) != 0) {
+                       if (ltdb_msg_add_element(msg2, el) != 0) {
                                ret = LDB_ERR_OTHER;
                                goto done;
                        }
@@ -916,7 +960,7 @@ int ltdb_modify_internal(struct ldb_module *module,
 
                        if (msg->elements[i].num_values == 0) {
                                /* Delete the whole attribute */
-                               ret = msg_delete_attribute(module, ldb, msg2,
+                               ret = msg_delete_attribute(module, msg2,
                                                           msg->elements[i].name);
                                if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE &&
                                    control_permissive) {
@@ -939,7 +983,7 @@ int ltdb_modify_internal(struct ldb_module *module,
                                        if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE &&
                                            control_permissive) {
                                                ret = LDB_SUCCESS;
-                                       } else {
+                                       } else if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
                                                ldb_asprintf_errstring(ldb,
                                                                       "attribute '%s': no matching attribute value while deleting attribute on '%s'",
                                                                       msg->elements[i].name, dn);
@@ -1025,7 +1069,8 @@ static int ltdb_rename(struct ltdb_context *ctx)
        }
 
        /* we need to fetch the old record to re-add under the new name */
-       ret = ltdb_search_dn1(module, req->op.rename.olddn, msg);
+       ret = ltdb_search_dn1(module, req->op.rename.olddn, msg,
+                             LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC);
        if (ret != LDB_SUCCESS) {
                /* not finding the old record is an error */
                return ret;
@@ -1108,6 +1153,7 @@ static int ltdb_start_trans(struct ldb_module *module)
 
 static int ltdb_prepare_commit(struct ldb_module *module)
 {
+       int ret;
        void *data = ldb_module_get_private(module);
        struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
 
@@ -1115,15 +1161,21 @@ static int ltdb_prepare_commit(struct ldb_module *module)
                return LDB_SUCCESS;
        }
 
-       if (ltdb_index_transaction_commit(module) != 0) {
+       ret = ltdb_index_transaction_commit(module);
+       if (ret != LDB_SUCCESS) {
                tdb_transaction_cancel(ltdb->tdb);
                ltdb->in_transaction--;
-               return ltdb_err_map(tdb_error(ltdb->tdb));
+               return ret;
        }
 
        if (tdb_transaction_prepare_commit(ltdb->tdb) != 0) {
+               ret = ltdb_err_map(tdb_error(ltdb->tdb));
                ltdb->in_transaction--;
-               return ltdb_err_map(tdb_error(ltdb->tdb));
+               ldb_asprintf_errstring(ldb_module_get_ctx(module),
+                                      "Failure during tdb_transaction_prepare_commit(): %s -> %s",
+                                      tdb_errorstr(ltdb->tdb),
+                                      ldb_strerror(ret));
+               return ret;
        }
 
        ltdb->prepared_commit = true;
@@ -1133,11 +1185,12 @@ static int ltdb_prepare_commit(struct ldb_module *module)
 
 static int ltdb_end_trans(struct ldb_module *module)
 {
+       int ret;
        void *data = ldb_module_get_private(module);
        struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
 
        if (!ltdb->prepared_commit) {
-               int ret = ltdb_prepare_commit(module);
+               ret = ltdb_prepare_commit(module);
                if (ret != LDB_SUCCESS) {
                        return ret;
                }
@@ -1147,7 +1200,12 @@ static int ltdb_end_trans(struct ldb_module *module)
        ltdb->prepared_commit = false;
 
        if (tdb_transaction_commit(ltdb->tdb) != 0) {
-               return ltdb_err_map(tdb_error(ltdb->tdb));
+               ret = ltdb_err_map(tdb_error(ltdb->tdb));
+               ldb_asprintf_errstring(ldb_module_get_ctx(module),
+                                      "Failure during tdb_transaction_commit(): %s -> %s",
+                                      tdb_errorstr(ltdb->tdb),
+                                      ldb_strerror(ret));
+               return ret;
        }
 
        return LDB_SUCCESS;
@@ -1224,7 +1282,7 @@ static int ltdb_sequence_number(struct ltdb_context *ctx,
                goto done;
        }
 
-       ret = ltdb_search_dn1(module, dn, msg);
+       ret = ltdb_search_dn1(module, dn, msg, 0);
        if (ret != LDB_SUCCESS) {
                goto done;
        }
@@ -1450,7 +1508,7 @@ static int ltdb_handle_request(struct ldb_module *module,
                return LDB_ERR_TIME_LIMIT_EXCEEDED;
        }
 
-       ev = ldb_get_event_context(ldb);
+       ev = ldb_handle_get_event_context(req->handle);
 
        ac = talloc_zero(ldb, struct ltdb_context);
        if (ac == NULL) {
@@ -1530,6 +1588,13 @@ static int ltdb_connect(struct ldb_context *ldb, const char *url,
        int tdb_flags, open_flags;
        struct ltdb_private *ltdb;
 
+       /*
+        * We hold locks, so we must use a private event context
+        * on each returned handle
+        */
+
+       ldb_set_require_private_event_context(ldb);
+
        /* parse the url */
        if (strchr(url, ':')) {
                if (strncmp(url, "tdb://", 6) != 0) {
@@ -1556,6 +1621,8 @@ static int ltdb_connect(struct ldb_context *ldb, const char *url,
 
        if (flags & LDB_FLG_RDONLY) {
                open_flags = O_RDONLY;
+       } else if (flags & LDB_FLG_DONT_CREATE_DB) {
+               open_flags = O_RDWR;
        } else {
                open_flags = O_CREAT | O_RDWR;
        }