4 Copyright (C) Andrew Tridgell 2004
6 ** NOTE! The following LGPL license applies to the ldb
7 ** library. This does NOT imply that all of Samba is released
10 This library is free software; you can redistribute it and/or
11 modify it under the terms of the GNU Lesser General Public
12 License as published by the Free Software Foundation; either
13 version 3 of the License, or (at your option) any later version.
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
20 You should have received a copy of the GNU Lesser General Public
21 License along with this library; if not, see <http://www.gnu.org/licenses/>.
27 * Component: ldb tdb backend - indexing
29 * Description: indexing routines for ldb tdb backend
31 * Author: Andrew Tridgell
34 #include "ldb_includes.h"
39 the idxptr code is a bit unusual. The way it works is to replace
40 @IDX elements in records during a transaction with @IDXPTR
41 elements. The @IDXPTR elements don't contain the actual index entry
42 values, but contain a pointer to a linked list of values.
44 This means we are storing pointers in a database, which is normally
45 not allowed, but in this case we are storing them only for the
46 duration of a transaction, and re-writing them into the normal @IDX
47 format at the end of the transaction. That means no other processes
48 are ever exposed to the @IDXPTR values.
50 The advantage is that the linked list doesn't cause huge
51 fragmentation during a transaction. Without the @IDXPTR method we
52 often ended up with a ldb that was between 10x and 100x larger then
53 it needs to be due to massive fragmentation caused by re-writing
54 @INDEX records many times during indexing.
56 struct ldb_index_pointer {
57 struct ldb_index_pointer *next, *prev;
68 add to the list of DNs that need to be fixed on transaction end
70 static int ltdb_idxptr_add(struct ldb_module *module, const struct ldb_message *msg)
72 struct ltdb_private *ltdb =
73 talloc_get_type(module->private_data, struct ltdb_private);
74 ltdb->idxptr->dn_list = talloc_realloc(ltdb->idxptr, ltdb->idxptr->dn_list,
75 const char *, ltdb->idxptr->num_dns+1);
76 if (ltdb->idxptr->dn_list == NULL) {
77 ltdb->idxptr->num_dns = 0;
78 return LDB_ERR_OPERATIONS_ERROR;
80 ltdb->idxptr->dn_list[ltdb->idxptr->num_dns] =
81 talloc_strdup(ltdb->idxptr->dn_list, ldb_dn_get_linearized(msg->dn));
82 if (ltdb->idxptr->dn_list[ltdb->idxptr->num_dns] == NULL) {
83 return LDB_ERR_OPERATIONS_ERROR;
85 ltdb->idxptr->num_dns++;
89 /* free an idxptr record */
90 static int ltdb_free_idxptr(struct ldb_module *module, struct ldb_message_element *el)
93 struct ldb_index_pointer *ptr;
95 if (el->num_values != 1) {
96 return LDB_ERR_OPERATIONS_ERROR;
100 if (val.length != sizeof(void *)) {
101 return LDB_ERR_OPERATIONS_ERROR;
104 ptr = *(struct ldb_index_pointer **)val.data;
105 if (talloc_get_type(ptr, struct ldb_index_pointer) != ptr) {
106 return LDB_ERR_OPERATIONS_ERROR;
110 struct ldb_index_pointer *tmp = ptr;
111 DLIST_REMOVE(ptr, ptr);
119 /* convert from the IDXPTR format to a ldb_message_element format */
120 static int ltdb_convert_from_idxptr(struct ldb_module *module, struct ldb_message_element *el)
123 struct ldb_index_pointer *ptr, *tmp;
125 struct ldb_val *val2;
127 if (el->num_values != 1) {
128 return LDB_ERR_OPERATIONS_ERROR;
132 if (val.length != sizeof(void *)) {
133 return LDB_ERR_OPERATIONS_ERROR;
136 ptr = *(struct ldb_index_pointer **)val.data;
137 if (talloc_get_type(ptr, struct ldb_index_pointer) != ptr) {
138 return LDB_ERR_OPERATIONS_ERROR;
141 /* count the length of the list */
142 for (i=0, tmp = ptr; tmp; tmp=tmp->next) {
146 /* allocate the new values array */
147 val2 = talloc_realloc(NULL, el->values, struct ldb_val, i);
149 return LDB_ERR_OPERATIONS_ERROR;
154 /* populate the values array */
155 for (i=0, tmp = ptr; tmp; tmp=tmp->next, i++) {
156 el->values[i].length = tmp->value.length;
157 /* we need to over-allocate here as there are still some places
158 in ldb that rely on null termination. */
159 el->values[i].data = talloc_size(el->values, tmp->value.length+1);
160 if (el->values[i].data == NULL) {
161 return LDB_ERR_OPERATIONS_ERROR;
163 memcpy(el->values[i].data, tmp->value.data, tmp->value.length);
164 el->values[i].data[tmp->value.length] = 0;
167 /* update the name */
174 /* convert to the IDXPTR format from a ldb_message_element format */
175 static int ltdb_convert_to_idxptr(struct ldb_module *module, struct ldb_message_element *el)
177 struct ldb_index_pointer *ptr, *tmp;
179 struct ldb_val *val2;
180 struct ltdb_private *ltdb =
181 talloc_get_type(module->private_data, struct ltdb_private);
185 for (i=0;i<el->num_values;i++) {
186 tmp = talloc(ltdb->idxptr, struct ldb_index_pointer);
188 return LDB_ERR_OPERATIONS_ERROR;
190 tmp->value = el->values[i];
191 tmp->value.data = talloc_memdup(tmp, tmp->value.data, tmp->value.length);
192 if (tmp->value.data == NULL) {
193 return LDB_ERR_OPERATIONS_ERROR;
198 /* allocate the new values array */
199 val2 = talloc_realloc(NULL, el->values, struct ldb_val, 1);
201 return LDB_ERR_OPERATIONS_ERROR;
206 el->values[0].data = talloc_memdup(el->values, &ptr, sizeof(ptr));
207 el->values[0].length = sizeof(ptr);
209 /* update the name */
210 el->name = LTDB_IDXPTR;
216 /* enable the idxptr mode when transactions start */
217 int ltdb_index_transaction_start(struct ldb_module *module)
219 struct ltdb_private *ltdb =
220 talloc_get_type(module->private_data, struct ltdb_private);
221 ltdb->idxptr = talloc_zero(module, struct ltdb_idxptr);
226 a wrapper around ltdb_search_dn1() which translates pointer based index records
227 and maps them into normal ldb message structures
229 static int ltdb_search_dn1_wrap(struct ldb_module *module,
230 struct ldb_dn *dn, struct ldb_message *msg)
233 ret = ltdb_search_dn1(module, dn, msg);
234 if (ret != LDB_SUCCESS) {
238 /* if this isn't a @INDEX record then don't munge it */
239 if (strncmp(ldb_dn_get_linearized(msg->dn), LTDB_INDEX ":", strlen(LTDB_INDEX) + 1) != 0) {
243 for (i=0;i<msg->num_elements;i++) {
244 struct ldb_message_element *el = &msg->elements[i];
245 if (strcmp(el->name, LTDB_IDXPTR) == 0) {
246 ret = ltdb_convert_from_idxptr(module, el);
247 if (ret != LDB_SUCCESS) {
259 fixup the idxptr for one DN
261 static int ltdb_idxptr_fix_dn(struct ldb_module *module, const char *strdn)
264 struct ldb_message *msg = ldb_msg_new(module);
267 dn = ldb_dn_new(msg, module->ldb, strdn);
268 if (ltdb_search_dn1_wrap(module, dn, msg) == LDB_SUCCESS) {
269 ret = ltdb_store(module, msg, TDB_REPLACE);
275 /* cleanup the idxptr mode when transaction commits */
276 int ltdb_index_transaction_commit(struct ldb_module *module)
279 struct ltdb_private *ltdb =
280 talloc_get_type(module->private_data, struct ltdb_private);
282 /* fix all the DNs that we have modified */
284 for (i=0;i<ltdb->idxptr->num_dns;i++) {
285 ltdb_idxptr_fix_dn(module, ltdb->idxptr->dn_list[i]);
288 if (ltdb->idxptr->repack) {
289 tdb_repack(ltdb->tdb);
293 talloc_free(ltdb->idxptr);
298 /* cleanup the idxptr mode when transaction cancels */
299 int ltdb_index_transaction_cancel(struct ldb_module *module)
301 struct ltdb_private *ltdb =
302 talloc_get_type(module->private_data, struct ltdb_private);
303 talloc_free(ltdb->idxptr);
310 /* a wrapper around ltdb_store() for the index code which
311 stores in IDXPTR format when idxptr mode is enabled
313 WARNING: This modifies the msg which is passed in
315 int ltdb_store_idxptr(struct ldb_module *module, const struct ldb_message *msg, int flgs)
317 struct ltdb_private *ltdb =
318 talloc_get_type(module->private_data, struct ltdb_private);
323 struct ldb_message *msg2 = ldb_msg_new(module);
325 /* free any old pointer */
326 ret = ltdb_search_dn1(module, msg->dn, msg2);
328 for (i=0;i<msg2->num_elements;i++) {
329 struct ldb_message_element *el = &msg2->elements[i];
330 if (strcmp(el->name, LTDB_IDXPTR) == 0) {
331 ret = ltdb_free_idxptr(module, el);
332 if (ret != LDB_SUCCESS) {
340 for (i=0;i<msg->num_elements;i++) {
341 struct ldb_message_element *el = &msg->elements[i];
342 if (strcmp(el->name, LTDB_IDX) == 0) {
343 ret = ltdb_convert_to_idxptr(module, el);
344 if (ret != LDB_SUCCESS) {
350 if (ltdb_idxptr_add(module, msg) != 0) {
351 return LDB_ERR_OPERATIONS_ERROR;
355 ret = ltdb_store(module, msg, flgs);
361 find an element in a list, using the given comparison function and
362 assuming that the list is already sorted using comp_fn
364 return -1 if not found, or the index of the first occurance of needle if found
366 static int ldb_list_find(const void *needle,
367 const void *base, size_t nmemb, size_t size,
368 comparison_fn_t comp_fn)
370 const char *base_p = (const char *)base;
371 size_t min_i, max_i, test_i;
380 while (min_i < max_i) {
383 test_i = (min_i + max_i) / 2;
384 /* the following cast looks strange, but is
385 correct. The key to understanding it is that base_p
386 is a pointer to an array of pointers, so we have to
387 dereference it after casting to void **. The strange
388 const in the middle gives us the right type of pointer
389 after the dereference (tridge) */
390 r = comp_fn(needle, *(void * const *)(base_p + (size * test_i)));
392 /* scan back for first element */
394 comp_fn(needle, *(void * const *)(base_p + (size * (test_i-1)))) == 0) {
410 if (comp_fn(needle, *(void * const *)(base_p + (size * min_i))) == 0) {
423 return the dn key to be used for an index
426 static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
427 const char *attr, const struct ldb_val *value)
431 const struct ldb_schema_attribute *a;
435 attr_folded = ldb_attr_casefold(ldb, attr);
440 a = ldb_schema_attribute_by_name(ldb, attr);
441 r = a->syntax->canonicalise_fn(ldb, ldb, value, &v);
442 if (r != LDB_SUCCESS) {
443 const char *errstr = ldb_errstring(ldb);
444 /* canonicalisation can be refused. For example,
445 a attribute that takes wildcards will refuse to canonicalise
446 if the value contains a wildcard */
447 ldb_asprintf_errstring(ldb, "Failed to create index key for attribute '%s':%s%s%s",
448 attr, ldb_strerror(r), (errstr?":":""), (errstr?errstr:""));
449 talloc_free(attr_folded);
452 if (ldb_should_b64_encode(&v)) {
453 char *vstr = ldb_base64_encode(ldb, (char *)v.data, v.length);
454 if (!vstr) return NULL;
455 ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
458 ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX, attr_folded, (int)v.length, (char *)v.data);
461 if (v.data != value->data) {
464 talloc_free(attr_folded);
470 see if a attribute value is in the list of indexed attributes
472 static int ldb_msg_find_idx(const struct ldb_message *msg, const char *attr,
473 unsigned int *v_idx, const char *key)
476 for (i=0;i<msg->num_elements;i++) {
477 if (ldb_attr_cmp(msg->elements[i].name, key) == 0) {
478 const struct ldb_message_element *el = &msg->elements[i];
481 /* in this case we are just looking to see if key is present,
482 we are not spearching for a specific index */
486 for (j=0;j<el->num_values;j++) {
487 if (ldb_attr_cmp((char *)el->values[j].data, attr) == 0) {
499 /* used in sorting dn lists */
500 static int list_cmp(const char **s1, const char **s2)
502 return strcmp(*s1, *s2);
506 return a list of dn's that might match a simple indexed search or
508 static int ltdb_index_dn_simple(struct ldb_module *module,
509 const struct ldb_parse_tree *tree,
510 const struct ldb_message *index_list,
511 struct dn_list *list)
513 struct ldb_context *ldb = module->ldb;
517 struct ldb_message *msg;
522 /* if the attribute isn't in the list of indexed attributes then
523 this node needs a full search */
524 if (ldb_msg_find_idx(index_list, tree->u.equality.attr, NULL, LTDB_IDXATTR) == -1) {
525 return LDB_ERR_OPERATIONS_ERROR;
528 /* the attribute is indexed. Pull the list of DNs that match the
530 dn = ltdb_index_key(ldb, tree->u.equality.attr, &tree->u.equality.value);
531 if (!dn) return LDB_ERR_OPERATIONS_ERROR;
533 msg = talloc(list, struct ldb_message);
535 return LDB_ERR_OPERATIONS_ERROR;
538 ret = ltdb_search_dn1_wrap(module, dn, msg);
540 if (ret != LDB_SUCCESS) {
544 for (i=0;i<msg->num_elements;i++) {
545 struct ldb_message_element *el;
547 if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
551 el = &msg->elements[i];
553 list->dn = talloc_array(list, char *, el->num_values);
556 return LDB_ERR_OPERATIONS_ERROR;
559 for (j=0;j<el->num_values;j++) {
560 list->dn[list->count] =
561 talloc_strdup(list->dn, (char *)el->values[j].data);
562 if (!list->dn[list->count]) {
564 return LDB_ERR_OPERATIONS_ERROR;
572 if (list->count > 1) {
573 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t) list_cmp);
580 static int list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
583 return a list of dn's that might match a leaf indexed search
585 static int ltdb_index_dn_leaf(struct ldb_module *module,
586 const struct ldb_parse_tree *tree,
587 const struct ldb_message *index_list,
588 struct dn_list *list)
590 if (ldb_attr_dn(tree->u.equality.attr) == 0) {
591 list->dn = talloc_array(list, char *, 1);
592 if (list->dn == NULL) {
593 ldb_oom(module->ldb);
594 return LDB_ERR_OPERATIONS_ERROR;
596 list->dn[0] = talloc_strdup(list->dn, (char *)tree->u.equality.value.data);
597 if (list->dn[0] == NULL) {
598 ldb_oom(module->ldb);
599 return LDB_ERR_OPERATIONS_ERROR;
604 return ltdb_index_dn_simple(module, tree, index_list, list);
611 relies on the lists being sorted
613 static int list_intersect(struct ldb_context *ldb,
614 struct dn_list *list, const struct dn_list *list2)
616 struct dn_list *list3;
619 if (list->count == 0 || list2->count == 0) {
621 return LDB_ERR_NO_SUCH_OBJECT;
624 list3 = talloc(ldb, struct dn_list);
626 return LDB_ERR_OPERATIONS_ERROR;
629 list3->dn = talloc_array(list3, char *, list->count);
632 return LDB_ERR_OPERATIONS_ERROR;
636 for (i=0;i<list->count;i++) {
637 if (ldb_list_find(list->dn[i], list2->dn, list2->count,
638 sizeof(char *), (comparison_fn_t)strcmp) != -1) {
639 list3->dn[list3->count] = talloc_move(list3->dn, &list->dn[i]);
642 talloc_free(list->dn[i]);
646 talloc_free(list->dn);
647 list->dn = talloc_move(list, &list3->dn);
648 list->count = list3->count;
651 return LDB_ERR_NO_SUCH_OBJECT;
658 relies on the lists being sorted
660 static int list_union(struct ldb_context *ldb,
661 struct dn_list *list, const struct dn_list *list2)
665 unsigned int count = list->count;
667 if (list->count == 0 && list2->count == 0) {
669 return LDB_ERR_NO_SUCH_OBJECT;
672 d = talloc_realloc(list, list->dn, char *, list->count + list2->count);
674 return LDB_ERR_OPERATIONS_ERROR;
678 for (i=0;i<list2->count;i++) {
679 if (ldb_list_find(list2->dn[i], list->dn, count,
680 sizeof(char *), (comparison_fn_t)strcmp) == -1) {
681 list->dn[list->count] = talloc_strdup(list->dn, list2->dn[i]);
682 if (!list->dn[list->count]) {
683 return LDB_ERR_OPERATIONS_ERROR;
689 if (list->count != count) {
690 qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t)list_cmp);
693 return LDB_ERR_NO_SUCH_OBJECT;
696 static int ltdb_index_dn(struct ldb_module *module,
697 const struct ldb_parse_tree *tree,
698 const struct ldb_message *index_list,
699 struct dn_list *list);
705 static int ltdb_index_dn_or(struct ldb_module *module,
706 const struct ldb_parse_tree *tree,
707 const struct ldb_message *index_list,
708 struct dn_list *list)
710 struct ldb_context *ldb = module->ldb;
714 ret = LDB_ERR_OPERATIONS_ERROR;
718 for (i=0;i<tree->u.list.num_elements;i++) {
719 struct dn_list *list2;
722 list2 = talloc(module, struct dn_list);
724 return LDB_ERR_OPERATIONS_ERROR;
727 v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
729 if (v == LDB_ERR_NO_SUCH_OBJECT) {
731 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
738 if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
740 talloc_free(list->dn);
745 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
747 list->dn = talloc_move(list, &list2->dn);
748 list->count = list2->count;
750 if (list_union(ldb, list, list2) == -1) {
752 return LDB_ERR_OPERATIONS_ERROR;
759 if (list->count == 0) {
760 return LDB_ERR_NO_SUCH_OBJECT;
770 static int ltdb_index_dn_not(struct ldb_module *module,
771 const struct ldb_parse_tree *tree,
772 const struct ldb_message *index_list,
773 struct dn_list *list)
775 /* the only way to do an indexed not would be if we could
776 negate the not via another not or if we knew the total
777 number of database elements so we could know that the
778 existing expression covered the whole database.
780 instead, we just give up, and rely on a full index scan
781 (unless an outer & manages to reduce the list)
783 return LDB_ERR_OPERATIONS_ERROR;
787 AND two index results
789 static int ltdb_index_dn_and(struct ldb_module *module,
790 const struct ldb_parse_tree *tree,
791 const struct ldb_message *index_list,
792 struct dn_list *list)
794 struct ldb_context *ldb = module->ldb;
798 ret = LDB_ERR_OPERATIONS_ERROR;
802 for (i=0;i<tree->u.list.num_elements;i++) {
803 struct dn_list *list2;
806 list2 = talloc(module, struct dn_list);
808 return LDB_ERR_OPERATIONS_ERROR;
811 v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
813 if (v == LDB_ERR_NO_SUCH_OBJECT) {
815 talloc_free(list->dn);
817 return LDB_ERR_NO_SUCH_OBJECT;
820 if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
825 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
827 talloc_free(list->dn);
828 list->dn = talloc_move(list, &list2->dn);
829 list->count = list2->count;
831 if (list_intersect(ldb, list, list2) == -1) {
833 return LDB_ERR_OPERATIONS_ERROR;
839 if (list->count == 0) {
840 talloc_free(list->dn);
841 return LDB_ERR_NO_SUCH_OBJECT;
849 AND index results and ONE level special index
851 static int ltdb_index_dn_one(struct ldb_module *module,
852 struct ldb_dn *parent_dn,
853 struct dn_list *list)
855 struct ldb_context *ldb = module->ldb;
856 struct dn_list *list2;
857 struct ldb_message *msg;
863 list2 = talloc_zero(module, struct dn_list);
865 return LDB_ERR_OPERATIONS_ERROR;
868 /* the attribute is indexed. Pull the list of DNs that match the
870 val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(parent_dn));
871 val.length = strlen((char *)val.data);
872 key = ltdb_index_key(ldb, LTDB_IDXONE, &val);
875 return LDB_ERR_OPERATIONS_ERROR;
878 msg = talloc(list2, struct ldb_message);
881 return LDB_ERR_OPERATIONS_ERROR;
884 ret = ltdb_search_dn1_wrap(module, key, msg);
886 if (ret != LDB_SUCCESS) {
890 for (i = 0; i < msg->num_elements; i++) {
891 struct ldb_message_element *el;
893 if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
897 el = &msg->elements[i];
899 list2->dn = talloc_array(list2, char *, el->num_values);
902 return LDB_ERR_OPERATIONS_ERROR;
905 for (j = 0; j < el->num_values; j++) {
906 list2->dn[list2->count] = talloc_strdup(list2->dn, (char *)el->values[j].data);
907 if (!list2->dn[list2->count]) {
909 return LDB_ERR_OPERATIONS_ERROR;
915 if (list2->count == 0) {
917 return LDB_ERR_NO_SUCH_OBJECT;
920 if (list2->count > 1) {
921 qsort(list2->dn, list2->count, sizeof(char *), (comparison_fn_t) list_cmp);
924 if (list->count > 0) {
925 if (list_intersect(ldb, list, list2) == -1) {
927 return LDB_ERR_OPERATIONS_ERROR;
930 if (list->count == 0) {
931 talloc_free(list->dn);
933 return LDB_ERR_NO_SUCH_OBJECT;
936 list->dn = talloc_move(list, &list2->dn);
937 list->count = list2->count;
946 return a list of dn's that might match a indexed search or
947 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
949 static int ltdb_index_dn(struct ldb_module *module,
950 const struct ldb_parse_tree *tree,
951 const struct ldb_message *index_list,
952 struct dn_list *list)
954 int ret = LDB_ERR_OPERATIONS_ERROR;
956 switch (tree->operation) {
958 ret = ltdb_index_dn_and(module, tree, index_list, list);
962 ret = ltdb_index_dn_or(module, tree, index_list, list);
966 ret = ltdb_index_dn_not(module, tree, index_list, list);
969 case LDB_OP_EQUALITY:
970 ret = ltdb_index_dn_leaf(module, tree, index_list, list);
973 case LDB_OP_SUBSTRING:
978 case LDB_OP_EXTENDED:
979 /* we can't index with fancy bitops yet */
980 ret = LDB_ERR_OPERATIONS_ERROR;
988 filter a candidate dn_list from an indexed search into a set of results
989 extracting just the given attributes
991 static int ltdb_index_filter(const struct dn_list *dn_list,
992 struct ltdb_context *ac)
994 struct ldb_message *msg;
997 for (i = 0; i < dn_list->count; i++) {
1001 msg = ldb_msg_new(ac);
1003 return LDB_ERR_OPERATIONS_ERROR;
1006 dn = ldb_dn_new(msg, ac->module->ldb, dn_list->dn[i]);
1009 return LDB_ERR_OPERATIONS_ERROR;
1012 ret = ltdb_search_dn1_wrap(ac->module, dn, msg);
1014 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1015 /* the record has disappeared? yes, this can happen */
1020 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1021 /* an internal error */
1023 return LDB_ERR_OPERATIONS_ERROR;
1026 if (!ldb_match_msg(ac->module->ldb, msg,
1027 ac->tree, ac->base, ac->scope)) {
1032 /* filter the attributes that the user wants */
1033 ret = ltdb_filter_attrs(msg, ac->attrs);
1037 return LDB_ERR_OPERATIONS_ERROR;
1040 ret = ldb_module_send_entry(ac->req, msg);
1041 if (ret != LDB_SUCCESS) {
1042 ac->callback_failed = true;
1051 search the database with a LDAP-like expression using indexes
1052 returns -1 if an indexed search is not possible, in which
1053 case the caller should call ltdb_search_full()
1055 int ltdb_search_indexed(struct ltdb_context *ac)
1057 struct ltdb_private *ltdb = talloc_get_type(ac->module->private_data, struct ltdb_private);
1058 struct dn_list *dn_list;
1059 int ret, idxattr, idxone;
1061 idxattr = idxone = 0;
1062 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXATTR);
1067 /* We do one level indexing only if requested */
1068 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
1073 if ((ac->scope == LDB_SCOPE_ONELEVEL && (idxattr+idxone == 0)) ||
1074 (ac->scope == LDB_SCOPE_SUBTREE && idxattr == 0)) {
1075 /* no indexes? must do full search */
1076 return LDB_ERR_OPERATIONS_ERROR;
1079 ret = LDB_ERR_OPERATIONS_ERROR;
1081 dn_list = talloc_zero(ac, struct dn_list);
1082 if (dn_list == NULL) {
1083 return LDB_ERR_OPERATIONS_ERROR;
1086 if (ac->scope == LDB_SCOPE_BASE) {
1087 /* with BASE searches only one DN can match */
1088 dn_list->dn = talloc_array(dn_list, char *, 1);
1089 if (dn_list->dn == NULL) {
1090 ldb_oom(ac->module->ldb);
1091 return LDB_ERR_OPERATIONS_ERROR;
1093 dn_list->dn[0] = ldb_dn_alloc_linearized(dn_list, ac->base);
1094 if (dn_list->dn[0] == NULL) {
1095 ldb_oom(ac->module->ldb);
1096 return LDB_ERR_OPERATIONS_ERROR;
1102 if (ac->scope != LDB_SCOPE_BASE && idxattr == 1) {
1103 ret = ltdb_index_dn(ac->module, ac->tree, ltdb->cache->indexlist, dn_list);
1105 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1106 talloc_free(dn_list);
1111 if (ac->scope == LDB_SCOPE_ONELEVEL && idxone == 1) {
1112 ret = ltdb_index_dn_one(ac->module, ac->base, dn_list);
1115 if (ret == LDB_SUCCESS) {
1116 /* we've got a candidate list - now filter by the full tree
1117 and extract the needed attributes */
1118 ret = ltdb_index_filter(dn_list, ac);
1121 talloc_free(dn_list);
1127 add a index element where this is the first indexed DN for this value
1129 static int ltdb_index_add1_new(struct ldb_context *ldb,
1130 struct ldb_message *msg,
1133 struct ldb_message_element *el;
1135 /* add another entry */
1136 el = talloc_realloc(msg, msg->elements,
1137 struct ldb_message_element, msg->num_elements+1);
1139 return LDB_ERR_OPERATIONS_ERROR;
1143 msg->elements[msg->num_elements].name = talloc_strdup(msg->elements, LTDB_IDX);
1144 if (!msg->elements[msg->num_elements].name) {
1145 return LDB_ERR_OPERATIONS_ERROR;
1147 msg->elements[msg->num_elements].num_values = 0;
1148 msg->elements[msg->num_elements].values = talloc(msg->elements, struct ldb_val);
1149 if (!msg->elements[msg->num_elements].values) {
1150 return LDB_ERR_OPERATIONS_ERROR;
1152 msg->elements[msg->num_elements].values[0].length = strlen(dn);
1153 msg->elements[msg->num_elements].values[0].data = discard_const_p(uint8_t, dn);
1154 msg->elements[msg->num_elements].num_values = 1;
1155 msg->num_elements++;
1162 add a index element where this is not the first indexed DN for this
1165 static int ltdb_index_add1_add(struct ldb_context *ldb,
1166 struct ldb_message *msg,
1173 /* for multi-valued attributes we can end up with repeats */
1174 for (i=0;i<msg->elements[idx].num_values;i++) {
1175 if (strcmp(dn, (char *)msg->elements[idx].values[i].data) == 0) {
1180 v2 = talloc_realloc(msg->elements, msg->elements[idx].values,
1182 msg->elements[idx].num_values+1);
1184 return LDB_ERR_OPERATIONS_ERROR;
1186 msg->elements[idx].values = v2;
1188 msg->elements[idx].values[msg->elements[idx].num_values].length = strlen(dn);
1189 msg->elements[idx].values[msg->elements[idx].num_values].data = discard_const_p(uint8_t, dn);
1190 msg->elements[idx].num_values++;
1196 add an index entry for one message element
1198 static int ltdb_index_add1(struct ldb_module *module, const char *dn,
1199 struct ldb_message_element *el, int v_idx)
1201 struct ldb_context *ldb = module->ldb;
1202 struct ldb_message *msg;
1203 struct ldb_dn *dn_key;
1207 msg = talloc(module, struct ldb_message);
1210 return LDB_ERR_OPERATIONS_ERROR;
1213 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
1216 return LDB_ERR_OPERATIONS_ERROR;
1218 talloc_steal(msg, dn_key);
1220 ret = ltdb_search_dn1_wrap(module, dn_key, msg);
1221 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1226 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1228 msg->num_elements = 0;
1229 msg->elements = NULL;
1232 for (i=0;i<msg->num_elements;i++) {
1233 if (strcmp(LTDB_IDX, msg->elements[i].name) == 0) {
1238 if (i == msg->num_elements) {
1239 ret = ltdb_index_add1_new(ldb, msg, dn);
1241 ret = ltdb_index_add1_add(ldb, msg, i, dn);
1244 if (ret == LDB_SUCCESS) {
1245 ret = ltdb_store_idxptr(module, msg, TDB_REPLACE);
1253 static int ltdb_index_add0(struct ldb_module *module, const char *dn,
1254 struct ldb_message_element *elements, int num_el)
1256 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1264 if (ltdb->cache->indexlist->num_elements == 0) {
1265 /* no indexed fields */
1269 for (i = 0; i < num_el; i++) {
1270 ret = ldb_msg_find_idx(ltdb->cache->indexlist, elements[i].name,
1271 NULL, LTDB_IDXATTR);
1275 for (j = 0; j < elements[i].num_values; j++) {
1276 ret = ltdb_index_add1(module, dn, &elements[i], j);
1277 if (ret != LDB_SUCCESS) {
1287 add the index entries for a new record
1289 int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
1294 dn = ldb_dn_get_linearized(msg->dn);
1296 return LDB_ERR_OPERATIONS_ERROR;
1299 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1306 delete an index entry for one message element
1308 int ltdb_index_del_value(struct ldb_module *module, const char *dn,
1309 struct ldb_message_element *el, int v_idx)
1311 struct ldb_context *ldb = module->ldb;
1312 struct ldb_message *msg;
1313 struct ldb_dn *dn_key;
1321 dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
1323 return LDB_ERR_OPERATIONS_ERROR;
1326 msg = talloc(dn_key, struct ldb_message);
1328 talloc_free(dn_key);
1329 return LDB_ERR_OPERATIONS_ERROR;
1332 ret = ltdb_search_dn1_wrap(module, dn_key, msg);
1333 if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
1334 talloc_free(dn_key);
1338 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1339 /* it wasn't indexed. Did we have an earlier error? If we did then
1341 talloc_free(dn_key);
1345 i = ldb_msg_find_idx(msg, dn, &j, LTDB_IDX);
1347 struct ldb_ldif ldif;
1349 ldb_debug(ldb, LDB_DEBUG_ERROR,
1350 "ERROR: dn %s not found in %s\n", dn,
1351 ldb_dn_get_linearized(dn_key));
1352 ldif.changetype = LDB_CHANGETYPE_NONE;
1354 ldb_ldif_write_file(module->ldb, stdout, &ldif);
1356 /* it ain't there. hmmm */
1357 talloc_free(dn_key);
1361 if (j != msg->elements[i].num_values - 1) {
1362 memmove(&msg->elements[i].values[j],
1363 &msg->elements[i].values[j+1],
1364 (msg->elements[i].num_values-(j+1)) *
1365 sizeof(msg->elements[i].values[0]));
1367 msg->elements[i].num_values--;
1369 if (msg->elements[i].num_values == 0) {
1370 ret = ltdb_delete_noindex(module, dn_key);
1372 ret = ltdb_store_idxptr(module, msg, TDB_REPLACE);
1375 talloc_free(dn_key);
1381 delete the index entries for a record
1382 return -1 on failure
1384 int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg)
1386 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1391 /* find the list of indexed fields */
1392 if (ltdb->cache->indexlist->num_elements == 0) {
1393 /* no indexed fields */
1397 if (ldb_dn_is_special(msg->dn)) {
1401 dn = ldb_dn_get_linearized(msg->dn);
1403 return LDB_ERR_OPERATIONS_ERROR;
1406 for (i = 0; i < msg->num_elements; i++) {
1407 ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name,
1408 NULL, LTDB_IDXATTR);
1412 for (j = 0; j < msg->elements[i].num_values; j++) {
1413 ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
1414 if (ret != LDB_SUCCESS) {
1424 handle special index for one level searches
1426 int ltdb_index_one(struct ldb_module *module, const struct ldb_message *msg, int add)
1428 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1429 struct ldb_message_element el;
1435 /* We index for ONE Level only if requested */
1436 ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
1441 pdn = ldb_dn_get_parent(module, msg->dn);
1443 return LDB_ERR_OPERATIONS_ERROR;
1446 dn = ldb_dn_get_linearized(msg->dn);
1449 return LDB_ERR_OPERATIONS_ERROR;
1452 val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn));
1453 if (val.data == NULL) {
1455 return LDB_ERR_OPERATIONS_ERROR;
1458 val.length = strlen((char *)val.data);
1459 el.name = LTDB_IDXONE;
1464 ret = ltdb_index_add1(module, dn, &el, 0);
1465 } else { /* delete */
1466 ret = ltdb_index_del_value(module, dn, &el, 0);
1476 traversal function that deletes all @INDEX records
1478 static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1480 const char *dn = "DN=" LTDB_INDEX ":";
1481 if (strncmp((char *)key.dptr, dn, strlen(dn)) == 0) {
1482 return tdb_delete(tdb, key);
1488 traversal function that adds @INDEX records during a re index
1490 static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
1492 struct ldb_module *module = (struct ldb_module *)state;
1493 struct ldb_message *msg;
1494 const char *dn = NULL;
1498 if (strncmp((char *)key.dptr, "DN=@", 4) == 0 ||
1499 strncmp((char *)key.dptr, "DN=", 3) != 0) {
1503 msg = talloc(module, struct ldb_message);
1508 ret = ltdb_unpack_data(module, &data, msg);
1514 /* check if the DN key has changed, perhaps due to the
1515 case insensitivity of an element changing */
1516 key2 = ltdb_key(module, msg->dn);
1517 if (key2.dptr == NULL) {
1518 /* probably a corrupt record ... darn */
1519 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n",
1520 ldb_dn_get_linearized(msg->dn));
1524 if (strcmp((char *)key2.dptr, (char *)key.dptr) != 0) {
1525 tdb_delete(tdb, key);
1526 tdb_store(tdb, key2, data, 0);
1528 talloc_free(key2.dptr);
1530 if (msg->dn == NULL) {
1531 dn = (char *)key.dptr + 3;
1533 dn = ldb_dn_get_linearized(msg->dn);
1536 ret = ltdb_index_one(module, msg, 1);
1537 if (ret == LDB_SUCCESS) {
1538 ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
1540 ldb_debug(module->ldb, LDB_DEBUG_ERROR,
1541 "Adding special ONE LEVEL index failed (%s)!\n",
1542 ldb_dn_get_linearized(msg->dn));
1547 if (ret != LDB_SUCCESS) return -1;
1553 force a complete reindex of the database
1555 int ltdb_reindex(struct ldb_module *module)
1557 struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
1560 if (ltdb_cache_reload(module) != 0) {
1561 return LDB_ERR_OPERATIONS_ERROR;
1564 /* first traverse the database deleting any @INDEX records */
1565 ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
1567 return LDB_ERR_OPERATIONS_ERROR;
1570 /* if we don't have indexes we have nothing todo */
1571 if (ltdb->cache->indexlist->num_elements == 0) {
1575 /* now traverse adding any indexes for normal LDB records */
1576 ret = tdb_traverse(ltdb->tdb, re_index, module);
1578 return LDB_ERR_OPERATIONS_ERROR;
1582 ltdb->idxptr->repack = true;