4 Copyright (C) Andrew Tridgell 2004-2009
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
35 #include "ldb_private.h"
43 struct tdb_context
*itdb
;
47 /* we put a @IDXVERSION attribute on index entries. This
48 allows us to tell if it was written by an older version
50 #define LTDB_INDEXING_VERSION 2
52 /* enable the idxptr mode when transactions start */
53 int ltdb_index_transaction_start(struct ldb_module
*module
)
55 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
56 ltdb
->idxptr
= talloc_zero(ltdb
, struct ltdb_idxptr
);
60 /* compare two DN entries in a dn_list. Take account of possible
61 * differences in string termination */
62 static int dn_list_cmp(const struct ldb_val
*v1
, const struct ldb_val
*v2
)
64 if (v1
->length
> v2
->length
&& v1
->data
[v2
->length
] != 0) {
67 if (v1
->length
< v2
->length
&& v2
->data
[v1
->length
] != 0) {
70 return strncmp((char *)v1
->data
, (char *)v2
->data
, v1
->length
);
75 find a entry in a dn_list, using a ldb_val. Uses a case sensitive
76 comparison with the dn returns -1 if not found
78 static int ltdb_dn_list_find_val(const struct dn_list
*list
, const struct ldb_val
*v
)
81 for (i
=0; i
<list
->count
; i
++) {
82 if (dn_list_cmp(&list
->dn
[i
], v
) == 0) return i
;
88 find a entry in a dn_list. Uses a case sensitive comparison with the dn
89 returns -1 if not found
91 static int ltdb_dn_list_find_str(struct dn_list
*list
, const char *dn
)
94 v
.data
= discard_const_p(unsigned char, dn
);
95 v
.length
= strlen(dn
);
96 return ltdb_dn_list_find_val(list
, &v
);
100 this is effectively a cast function, but with lots of paranoia
101 checks and also copes with CPUs that are fussy about pointer
104 static struct dn_list
*ltdb_index_idxptr(struct ldb_module
*module
, TDB_DATA rec
, bool check_parent
)
106 struct dn_list
*list
;
107 if (rec
.dsize
!= sizeof(void *)) {
108 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
109 "Bad data size for idxptr %u", (unsigned)rec
.dsize
);
112 /* note that we can't just use a cast here, as rec.dptr may
113 not be aligned sufficiently for a pointer. A cast would cause
114 platforms like some ARM CPUs to crash */
115 memcpy(&list
, rec
.dptr
, sizeof(void *));
116 list
= talloc_get_type(list
, struct dn_list
);
118 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
119 "Bad type '%s' for idxptr",
120 talloc_get_name(list
));
123 if (check_parent
&& list
->dn
&& talloc_parent(list
->dn
) != list
) {
124 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
125 "Bad parent '%s' for idxptr",
126 talloc_get_name(talloc_parent(list
->dn
)));
133 return the @IDX list in an index entry for a dn as a
136 static int ltdb_dn_list_load(struct ldb_module
*module
,
137 struct ldb_dn
*dn
, struct dn_list
*list
)
139 struct ldb_message
*msg
;
141 struct ldb_message_element
*el
;
142 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
144 struct dn_list
*list2
;
150 /* see if we have any in-memory index entries */
151 if (ltdb
->idxptr
== NULL
||
152 ltdb
->idxptr
->itdb
== NULL
) {
156 key
.dptr
= discard_const_p(unsigned char, ldb_dn_get_linearized(dn
));
157 key
.dsize
= strlen((char *)key
.dptr
);
159 rec
= tdb_fetch(ltdb
->idxptr
->itdb
, key
);
160 if (rec
.dptr
== NULL
) {
164 /* we've found an in-memory index entry */
165 list2
= ltdb_index_idxptr(module
, rec
, true);
168 return LDB_ERR_OPERATIONS_ERROR
;
176 msg
= ldb_msg_new(list
);
178 return LDB_ERR_OPERATIONS_ERROR
;
181 ret
= ltdb_search_dn1(module
, dn
, msg
);
182 if (ret
!= LDB_SUCCESS
) {
187 /* TODO: check indexing version number */
189 el
= ldb_msg_find_element(msg
, LTDB_IDX
);
195 /* we avoid copying the strings by stealing the list */
196 list
->dn
= talloc_steal(list
, el
->values
);
197 list
->count
= el
->num_values
;
204 save a dn_list into a full @IDX style record
206 static int ltdb_dn_list_store_full(struct ldb_module
*module
, struct ldb_dn
*dn
,
207 struct dn_list
*list
)
209 struct ldb_message
*msg
;
212 if (list
->count
== 0) {
213 ret
= ltdb_delete_noindex(module
, dn
);
214 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
220 msg
= ldb_msg_new(module
);
222 return ldb_module_oom(module
);
225 ret
= ldb_msg_add_fmt(msg
, LTDB_IDXVERSION
, "%u", LTDB_INDEXING_VERSION
);
226 if (ret
!= LDB_SUCCESS
) {
228 return ldb_module_oom(module
);
232 if (list
->count
> 0) {
233 struct ldb_message_element
*el
;
235 ret
= ldb_msg_add_empty(msg
, LTDB_IDX
, LDB_FLAG_MOD_ADD
, &el
);
236 if (ret
!= LDB_SUCCESS
) {
238 return ldb_module_oom(module
);
240 el
->values
= list
->dn
;
241 el
->num_values
= list
->count
;
244 ret
= ltdb_store(module
, msg
, TDB_REPLACE
);
250 save a dn_list into the database, in either @IDX or internal format
252 static int ltdb_dn_list_store(struct ldb_module
*module
, struct ldb_dn
*dn
,
253 struct dn_list
*list
)
255 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
258 struct dn_list
*list2
;
260 if (ltdb
->idxptr
== NULL
) {
261 return ltdb_dn_list_store_full(module
, dn
, list
);
264 if (ltdb
->idxptr
->itdb
== NULL
) {
265 ltdb
->idxptr
->itdb
= tdb_open(NULL
, 1000, TDB_INTERNAL
, O_RDWR
, 0);
266 if (ltdb
->idxptr
->itdb
== NULL
) {
267 return LDB_ERR_OPERATIONS_ERROR
;
271 key
.dptr
= discard_const_p(unsigned char, ldb_dn_get_linearized(dn
));
272 key
.dsize
= strlen((char *)key
.dptr
);
274 rec
= tdb_fetch(ltdb
->idxptr
->itdb
, key
);
275 if (rec
.dptr
!= NULL
) {
276 list2
= ltdb_index_idxptr(module
, rec
, false);
279 return LDB_ERR_OPERATIONS_ERROR
;
282 list2
->dn
= talloc_steal(list2
, list
->dn
);
283 list2
->count
= list
->count
;
287 list2
= talloc(ltdb
->idxptr
, struct dn_list
);
289 return LDB_ERR_OPERATIONS_ERROR
;
291 list2
->dn
= talloc_steal(list2
, list
->dn
);
292 list2
->count
= list
->count
;
294 rec
.dptr
= (uint8_t *)&list2
;
295 rec
.dsize
= sizeof(void *);
297 ret
= tdb_store(ltdb
->idxptr
->itdb
, key
, rec
, TDB_INSERT
);
299 return ltdb_err_map(tdb_error(ltdb
->idxptr
->itdb
));
305 traverse function for storing the in-memory index entries on disk
307 static int ltdb_index_traverse_store(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
309 struct ldb_module
*module
= state
;
310 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
312 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
314 struct dn_list
*list
;
316 list
= ltdb_index_idxptr(module
, data
, true);
318 ltdb
->idxptr
->error
= LDB_ERR_OPERATIONS_ERROR
;
323 v
.length
= strnlen((char *)key
.dptr
, key
.dsize
);
325 dn
= ldb_dn_from_ldb_val(module
, ldb
, &v
);
327 ldb_asprintf_errstring(ldb
, "Failed to parse index key %*.*s as an LDB DN", (int)v
.length
, (int)v
.length
, (const char *)v
.data
);
328 ltdb
->idxptr
->error
= LDB_ERR_OPERATIONS_ERROR
;
332 ltdb
->idxptr
->error
= ltdb_dn_list_store_full(module
, dn
, list
);
334 if (ltdb
->idxptr
->error
!= 0) {
340 /* cleanup the idxptr mode when transaction commits */
341 int ltdb_index_transaction_commit(struct ldb_module
*module
)
343 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
346 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
348 ldb_reset_err_string(ldb
);
350 if (ltdb
->idxptr
->itdb
) {
351 tdb_traverse(ltdb
->idxptr
->itdb
, ltdb_index_traverse_store
, module
);
352 tdb_close(ltdb
->idxptr
->itdb
);
355 ret
= ltdb
->idxptr
->error
;
356 if (ret
!= LDB_SUCCESS
) {
357 if (!ldb_errstring(ldb
)) {
358 ldb_set_errstring(ldb
, ldb_strerror(ret
));
360 ldb_asprintf_errstring(ldb
, "Failed to store index records in transaction commit: %s", ldb_errstring(ldb
));
363 talloc_free(ltdb
->idxptr
);
368 /* cleanup the idxptr mode when transaction cancels */
369 int ltdb_index_transaction_cancel(struct ldb_module
*module
)
371 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
372 if (ltdb
->idxptr
&& ltdb
->idxptr
->itdb
) {
373 tdb_close(ltdb
->idxptr
->itdb
);
375 talloc_free(ltdb
->idxptr
);
382 return the dn key to be used for an index
383 the caller is responsible for freeing
385 static struct ldb_dn
*ltdb_index_key(struct ldb_context
*ldb
,
386 const char *attr
, const struct ldb_val
*value
,
387 const struct ldb_schema_attribute
**ap
)
391 const struct ldb_schema_attribute
*a
;
395 attr_folded
= ldb_attr_casefold(ldb
, attr
);
400 a
= ldb_schema_attribute_by_name(ldb
, attr
);
404 r
= a
->syntax
->canonicalise_fn(ldb
, ldb
, value
, &v
);
405 if (r
!= LDB_SUCCESS
) {
406 const char *errstr
= ldb_errstring(ldb
);
407 /* canonicalisation can be refused. For example,
408 a attribute that takes wildcards will refuse to canonicalise
409 if the value contains a wildcard */
410 ldb_asprintf_errstring(ldb
, "Failed to create index key for attribute '%s':%s%s%s",
411 attr
, ldb_strerror(r
), (errstr
?":":""), (errstr
?errstr
:""));
412 talloc_free(attr_folded
);
415 if (ldb_should_b64_encode(ldb
, &v
)) {
416 char *vstr
= ldb_base64_encode(ldb
, (char *)v
.data
, v
.length
);
418 talloc_free(attr_folded
);
421 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s::%s", LTDB_INDEX
, attr_folded
, vstr
);
424 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s:%.*s", LTDB_INDEX
, attr_folded
, (int)v
.length
, (char *)v
.data
);
427 if (v
.data
!= value
->data
) {
430 talloc_free(attr_folded
);
436 see if a attribute value is in the list of indexed attributes
438 static bool ltdb_is_indexed(const struct ldb_message
*index_list
, const char *attr
)
441 struct ldb_message_element
*el
;
443 el
= ldb_msg_find_element(index_list
, LTDB_IDXATTR
);
448 /* TODO: this is too expensive! At least use a binary search */
449 for (i
=0; i
<el
->num_values
; i
++) {
450 if (ldb_attr_cmp((char *)el
->values
[i
].data
, attr
) == 0) {
458 in the following logic functions, the return value is treated as
461 LDB_SUCCESS: we found some matching index values
463 LDB_ERR_NO_SUCH_OBJECT: we know for sure that no object matches
465 LDB_ERR_OPERATIONS_ERROR: indexing could not answer the call,
466 we'll need a full search
470 return a list of dn's that might match a simple indexed search (an
471 equality search only)
473 static int ltdb_index_dn_simple(struct ldb_module
*module
,
474 const struct ldb_parse_tree
*tree
,
475 const struct ldb_message
*index_list
,
476 struct dn_list
*list
)
478 struct ldb_context
*ldb
;
482 ldb
= ldb_module_get_ctx(module
);
487 /* if the attribute isn't in the list of indexed attributes then
488 this node needs a full search */
489 if (!ltdb_is_indexed(index_list
, tree
->u
.equality
.attr
)) {
490 return LDB_ERR_OPERATIONS_ERROR
;
493 /* the attribute is indexed. Pull the list of DNs that match the
495 dn
= ltdb_index_key(ldb
, tree
->u
.equality
.attr
, &tree
->u
.equality
.value
, NULL
);
496 if (!dn
) return LDB_ERR_OPERATIONS_ERROR
;
498 ret
= ltdb_dn_list_load(module
, dn
, list
);
504 static bool list_union(struct ldb_context
*, struct dn_list
*, const struct dn_list
*);
507 return a list of dn's that might match a leaf indexed search
509 static int ltdb_index_dn_leaf(struct ldb_module
*module
,
510 const struct ldb_parse_tree
*tree
,
511 const struct ldb_message
*index_list
,
512 struct dn_list
*list
)
514 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
),
515 struct ltdb_private
);
516 if (ltdb
->disallow_dn_filter
&&
517 (ldb_attr_cmp(tree
->u
.equality
.attr
, "dn") == 0)) {
518 /* in AD mode we do not support "(dn=...)" search filters */
523 if (ldb_attr_dn(tree
->u
.equality
.attr
) == 0) {
524 list
->dn
= talloc_array(list
, struct ldb_val
, 1);
525 if (list
->dn
== NULL
) {
526 ldb_module_oom(module
);
527 return LDB_ERR_OPERATIONS_ERROR
;
529 list
->dn
[0] = tree
->u
.equality
.value
;
533 return ltdb_index_dn_simple(module
, tree
, index_list
, list
);
541 static bool list_intersect(struct ldb_context
*ldb
,
542 struct dn_list
*list
, const struct dn_list
*list2
)
544 struct dn_list
*list3
;
547 if (list
->count
== 0) {
551 if (list2
->count
== 0) {
558 /* the indexing code is allowed to return a longer list than
559 what really matches, as all results are filtered by the
560 full expression at the end - this shortcut avoids a lot of
561 work in some cases */
562 if (list
->count
< 2 && list2
->count
> 10) {
565 if (list2
->count
< 2 && list
->count
> 10) {
566 list
->count
= list2
->count
;
567 list
->dn
= list2
->dn
;
568 /* note that list2 may not be the parent of list2->dn,
569 as list2->dn may be owned by ltdb->idxptr. In that
570 case we expect this reparent call to fail, which is
572 talloc_reparent(list2
, list
, list2
->dn
);
576 list3
= talloc_zero(list
, struct dn_list
);
581 list3
->dn
= talloc_array(list3
, struct ldb_val
, list
->count
);
588 for (i
=0;i
<list
->count
;i
++) {
589 if (ltdb_dn_list_find_val(list2
, &list
->dn
[i
]) != -1) {
590 list3
->dn
[list3
->count
] = list
->dn
[i
];
595 list
->dn
= talloc_steal(list
, list3
->dn
);
596 list
->count
= list3
->count
;
607 static bool list_union(struct ldb_context
*ldb
,
608 struct dn_list
*list
, const struct dn_list
*list2
)
612 if (list2
->count
== 0) {
617 if (list
->count
== 0) {
619 list
->count
= list2
->count
;
620 list
->dn
= list2
->dn
;
621 /* note that list2 may not be the parent of list2->dn,
622 as list2->dn may be owned by ltdb->idxptr. In that
623 case we expect this reparent call to fail, which is
625 talloc_reparent(list2
, list
, list2
->dn
);
629 dn3
= talloc_array(list
, struct ldb_val
, list
->count
+ list2
->count
);
635 /* we allow for duplicates here, and get rid of them later */
636 memcpy(dn3
, list
->dn
, sizeof(list
->dn
[0])*list
->count
);
637 memcpy(dn3
+list
->count
, list2
->dn
, sizeof(list2
->dn
[0])*list2
->count
);
640 list
->count
+= list2
->count
;
645 static int ltdb_index_dn(struct ldb_module
*module
,
646 const struct ldb_parse_tree
*tree
,
647 const struct ldb_message
*index_list
,
648 struct dn_list
*list
);
652 process an OR list (a union)
654 static int ltdb_index_dn_or(struct ldb_module
*module
,
655 const struct ldb_parse_tree
*tree
,
656 const struct ldb_message
*index_list
,
657 struct dn_list
*list
)
659 struct ldb_context
*ldb
;
662 ldb
= ldb_module_get_ctx(module
);
667 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
668 struct dn_list
*list2
;
671 list2
= talloc_zero(list
, struct dn_list
);
673 return LDB_ERR_OPERATIONS_ERROR
;
676 ret
= ltdb_index_dn(module
, tree
->u
.list
.elements
[i
], index_list
, list2
);
678 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
684 if (ret
!= LDB_SUCCESS
) {
690 if (!list_union(ldb
, list
, list2
)) {
692 return LDB_ERR_OPERATIONS_ERROR
;
696 if (list
->count
== 0) {
697 return LDB_ERR_NO_SUCH_OBJECT
;
707 static int ltdb_index_dn_not(struct ldb_module
*module
,
708 const struct ldb_parse_tree
*tree
,
709 const struct ldb_message
*index_list
,
710 struct dn_list
*list
)
712 /* the only way to do an indexed not would be if we could
713 negate the not via another not or if we knew the total
714 number of database elements so we could know that the
715 existing expression covered the whole database.
717 instead, we just give up, and rely on a full index scan
718 (unless an outer & manages to reduce the list)
720 return LDB_ERR_OPERATIONS_ERROR
;
724 static bool ltdb_index_unique(struct ldb_context
*ldb
,
727 const struct ldb_schema_attribute
*a
;
728 a
= ldb_schema_attribute_by_name(ldb
, attr
);
729 if (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
) {
736 process an AND expression (intersection)
738 static int ltdb_index_dn_and(struct ldb_module
*module
,
739 const struct ldb_parse_tree
*tree
,
740 const struct ldb_message
*index_list
,
741 struct dn_list
*list
)
743 struct ldb_context
*ldb
;
747 ldb
= ldb_module_get_ctx(module
);
752 /* in the first pass we only look for unique simple
753 equality tests, in the hope of avoiding having to look
755 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
756 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
759 if (subtree
->operation
!= LDB_OP_EQUALITY
||
760 !ltdb_index_unique(ldb
, subtree
->u
.equality
.attr
)) {
764 ret
= ltdb_index_dn(module
, subtree
, index_list
, list
);
765 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
767 return LDB_ERR_NO_SUCH_OBJECT
;
769 if (ret
== LDB_SUCCESS
) {
770 /* a unique index match means we can
771 * stop. Note that we don't care if we return
772 * a few too many objects, due to later
778 /* now do a full intersection */
781 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
782 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
783 struct dn_list
*list2
;
786 list2
= talloc_zero(list
, struct dn_list
);
788 return ldb_module_oom(module
);
791 ret
= ltdb_index_dn(module
, subtree
, index_list
, list2
);
793 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
798 return LDB_ERR_NO_SUCH_OBJECT
;
801 if (ret
!= LDB_SUCCESS
) {
802 /* this didn't adding anything */
808 talloc_reparent(list2
, list
, list
->dn
);
809 list
->dn
= list2
->dn
;
810 list
->count
= list2
->count
;
812 } else if (!list_intersect(ldb
, list
, list2
)) {
814 return LDB_ERR_OPERATIONS_ERROR
;
817 if (list
->count
== 0) {
819 return LDB_ERR_NO_SUCH_OBJECT
;
822 if (list
->count
< 2) {
823 /* it isn't worth loading the next part of the tree */
829 /* none of the attributes were indexed */
830 return LDB_ERR_OPERATIONS_ERROR
;
837 return a list of matching objects using a one-level index
839 static int ltdb_index_dn_one(struct ldb_module
*module
,
840 struct ldb_dn
*parent_dn
,
841 struct dn_list
*list
)
843 struct ldb_context
*ldb
;
848 ldb
= ldb_module_get_ctx(module
);
850 /* work out the index key from the parent DN */
851 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(parent_dn
));
852 val
.length
= strlen((char *)val
.data
);
853 key
= ltdb_index_key(ldb
, LTDB_IDXONE
, &val
, NULL
);
856 return LDB_ERR_OPERATIONS_ERROR
;
859 ret
= ltdb_dn_list_load(module
, key
, list
);
861 if (ret
!= LDB_SUCCESS
) {
865 if (list
->count
== 0) {
866 return LDB_ERR_NO_SUCH_OBJECT
;
873 return a list of dn's that might match a indexed search or
874 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
876 static int ltdb_index_dn(struct ldb_module
*module
,
877 const struct ldb_parse_tree
*tree
,
878 const struct ldb_message
*index_list
,
879 struct dn_list
*list
)
881 int ret
= LDB_ERR_OPERATIONS_ERROR
;
883 switch (tree
->operation
) {
885 ret
= ltdb_index_dn_and(module
, tree
, index_list
, list
);
889 ret
= ltdb_index_dn_or(module
, tree
, index_list
, list
);
893 ret
= ltdb_index_dn_not(module
, tree
, index_list
, list
);
896 case LDB_OP_EQUALITY
:
897 ret
= ltdb_index_dn_leaf(module
, tree
, index_list
, list
);
900 case LDB_OP_SUBSTRING
:
905 case LDB_OP_EXTENDED
:
906 /* we can't index with fancy bitops yet */
907 ret
= LDB_ERR_OPERATIONS_ERROR
;
915 filter a candidate dn_list from an indexed search into a set of results
916 extracting just the given attributes
918 static int ltdb_index_filter(const struct dn_list
*dn_list
,
919 struct ltdb_context
*ac
,
920 uint32_t *match_count
)
922 struct ldb_context
*ldb
;
923 struct ldb_message
*msg
;
926 ldb
= ldb_module_get_ctx(ac
->module
);
928 for (i
= 0; i
< dn_list
->count
; i
++) {
933 msg
= ldb_msg_new(ac
);
935 return LDB_ERR_OPERATIONS_ERROR
;
938 dn
= ldb_dn_from_ldb_val(msg
, ldb
, &dn_list
->dn
[i
]);
941 return LDB_ERR_OPERATIONS_ERROR
;
944 ret
= ltdb_search_dn1(ac
->module
, dn
, msg
);
946 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
947 /* the record has disappeared? yes, this can happen */
952 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
953 /* an internal error */
955 return LDB_ERR_OPERATIONS_ERROR
;
958 ret
= ldb_match_msg_error(ldb
, msg
,
959 ac
->tree
, ac
->base
, ac
->scope
, &matched
);
960 if (ret
!= LDB_SUCCESS
) {
969 /* filter the attributes that the user wants */
970 ret
= ltdb_filter_attrs(msg
, ac
->attrs
);
974 return LDB_ERR_OPERATIONS_ERROR
;
977 ret
= ldb_module_send_entry(ac
->req
, msg
, NULL
);
978 if (ret
!= LDB_SUCCESS
) {
979 /* Regardless of success or failure, the msg
980 * is the callbacks responsiblity, and should
981 * not be talloc_free()'ed */
982 ac
->request_terminated
= true;
993 remove any duplicated entries in a indexed result
995 static void ltdb_dn_list_remove_duplicates(struct dn_list
*list
)
997 unsigned int i
, new_count
;
999 if (list
->count
< 2) {
1003 TYPESAFE_QSORT(list
->dn
, list
->count
, dn_list_cmp
);
1006 for (i
=1; i
<list
->count
; i
++) {
1007 if (dn_list_cmp(&list
->dn
[i
], &list
->dn
[new_count
-1]) != 0) {
1008 if (new_count
!= i
) {
1009 list
->dn
[new_count
] = list
->dn
[i
];
1015 list
->count
= new_count
;
1019 search the database with a LDAP-like expression using indexes
1020 returns -1 if an indexed search is not possible, in which
1021 case the caller should call ltdb_search_full()
1023 int ltdb_search_indexed(struct ltdb_context
*ac
, uint32_t *match_count
)
1025 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(ac
->module
), struct ltdb_private
);
1026 struct dn_list
*dn_list
;
1029 /* see if indexing is enabled */
1030 if (!ltdb
->cache
->attribute_indexes
&&
1031 !ltdb
->cache
->one_level_indexes
&&
1032 ac
->scope
!= LDB_SCOPE_BASE
) {
1033 /* fallback to a full search */
1034 return LDB_ERR_OPERATIONS_ERROR
;
1037 dn_list
= talloc_zero(ac
, struct dn_list
);
1038 if (dn_list
== NULL
) {
1039 return ldb_module_oom(ac
->module
);
1042 switch (ac
->scope
) {
1043 case LDB_SCOPE_BASE
:
1044 dn_list
->dn
= talloc_array(dn_list
, struct ldb_val
, 1);
1045 if (dn_list
->dn
== NULL
) {
1046 talloc_free(dn_list
);
1047 return ldb_module_oom(ac
->module
);
1049 dn_list
->dn
[0].data
= discard_const_p(unsigned char, ldb_dn_get_linearized(ac
->base
));
1050 if (dn_list
->dn
[0].data
== NULL
) {
1051 talloc_free(dn_list
);
1052 return ldb_module_oom(ac
->module
);
1054 dn_list
->dn
[0].length
= strlen((char *)dn_list
->dn
[0].data
);
1058 case LDB_SCOPE_ONELEVEL
:
1059 if (!ltdb
->cache
->one_level_indexes
) {
1060 talloc_free(dn_list
);
1061 return LDB_ERR_OPERATIONS_ERROR
;
1063 ret
= ltdb_index_dn_one(ac
->module
, ac
->base
, dn_list
);
1064 if (ret
!= LDB_SUCCESS
) {
1065 talloc_free(dn_list
);
1070 case LDB_SCOPE_SUBTREE
:
1071 case LDB_SCOPE_DEFAULT
:
1072 if (!ltdb
->cache
->attribute_indexes
) {
1073 talloc_free(dn_list
);
1074 return LDB_ERR_OPERATIONS_ERROR
;
1076 ret
= ltdb_index_dn(ac
->module
, ac
->tree
, ltdb
->cache
->indexlist
, dn_list
);
1077 if (ret
!= LDB_SUCCESS
) {
1078 talloc_free(dn_list
);
1081 ltdb_dn_list_remove_duplicates(dn_list
);
1085 ret
= ltdb_index_filter(dn_list
, ac
, match_count
);
1086 talloc_free(dn_list
);
1091 add an index entry for one message element
1093 static int ltdb_index_add1(struct ldb_module
*module
, const char *dn
,
1094 struct ldb_message_element
*el
, int v_idx
)
1096 struct ldb_context
*ldb
;
1097 struct ldb_dn
*dn_key
;
1099 const struct ldb_schema_attribute
*a
;
1100 struct dn_list
*list
;
1103 ldb
= ldb_module_get_ctx(module
);
1105 list
= talloc_zero(module
, struct dn_list
);
1107 return LDB_ERR_OPERATIONS_ERROR
;
1110 dn_key
= ltdb_index_key(ldb
, el
->name
, &el
->values
[v_idx
], &a
);
1113 return LDB_ERR_OPERATIONS_ERROR
;
1115 talloc_steal(list
, dn_key
);
1117 ret
= ltdb_dn_list_load(module
, dn_key
, list
);
1118 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1123 if (ltdb_dn_list_find_str(list
, dn
) != -1) {
1128 if (list
->count
> 0 &&
1129 a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
) {
1131 ldb_asprintf_errstring(ldb
, __location__
": unique index violation on %s in %s",
1133 return LDB_ERR_ENTRY_ALREADY_EXISTS
;
1136 /* overallocate the list a bit, to reduce the number of
1137 * realloc trigered copies */
1138 alloc_len
= ((list
->count
+1)+7) & ~7;
1139 list
->dn
= talloc_realloc(list
, list
->dn
, struct ldb_val
, alloc_len
);
1140 if (list
->dn
== NULL
) {
1142 return LDB_ERR_OPERATIONS_ERROR
;
1144 list
->dn
[list
->count
].data
= (uint8_t *)talloc_strdup(list
->dn
, dn
);
1145 list
->dn
[list
->count
].length
= strlen(dn
);
1148 ret
= ltdb_dn_list_store(module
, dn_key
, list
);
1156 add index entries for one elements in a message
1158 static int ltdb_index_add_el(struct ldb_module
*module
, const char *dn
,
1159 struct ldb_message_element
*el
)
1162 for (i
= 0; i
< el
->num_values
; i
++) {
1163 int ret
= ltdb_index_add1(module
, dn
, el
, i
);
1164 if (ret
!= LDB_SUCCESS
) {
1173 add index entries for all elements in a message
1175 static int ltdb_index_add_all(struct ldb_module
*module
, const char *dn
,
1176 struct ldb_message_element
*elements
, int num_el
)
1178 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1185 if (ltdb
->cache
->indexlist
->num_elements
== 0) {
1186 /* no indexed fields */
1190 for (i
= 0; i
< num_el
; i
++) {
1192 if (!ltdb_is_indexed(ltdb
->cache
->indexlist
, elements
[i
].name
)) {
1195 ret
= ltdb_index_add_el(module
, dn
, &elements
[i
]);
1196 if (ret
!= LDB_SUCCESS
) {
1197 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
1198 ldb_asprintf_errstring(ldb
,
1199 __location__
": Failed to re-index %s in %s - %s",
1200 elements
[i
].name
, dn
, ldb_errstring(ldb
));
1210 insert a one level index for a message
1212 static int ltdb_index_onelevel(struct ldb_module
*module
, const struct ldb_message
*msg
, int add
)
1214 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1215 struct ldb_message_element el
;
1221 /* We index for ONE Level only if requested */
1222 if (!ltdb
->cache
->one_level_indexes
) {
1226 pdn
= ldb_dn_get_parent(module
, msg
->dn
);
1228 return LDB_ERR_OPERATIONS_ERROR
;
1231 dn
= ldb_dn_get_linearized(msg
->dn
);
1234 return LDB_ERR_OPERATIONS_ERROR
;
1237 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn
));
1238 if (val
.data
== NULL
) {
1240 return LDB_ERR_OPERATIONS_ERROR
;
1243 val
.length
= strlen((char *)val
.data
);
1244 el
.name
= LTDB_IDXONE
;
1249 ret
= ltdb_index_add1(module
, dn
, &el
, 0);
1250 } else { /* delete */
1251 ret
= ltdb_index_del_value(module
, msg
->dn
, &el
, 0);
1260 add the index entries for a new element in a record
1261 The caller guarantees that these element values are not yet indexed
1263 int ltdb_index_add_element(struct ldb_module
*module
, struct ldb_dn
*dn
,
1264 struct ldb_message_element
*el
)
1266 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1267 if (ldb_dn_is_special(dn
)) {
1270 if (!ltdb_is_indexed(ltdb
->cache
->indexlist
, el
->name
)) {
1273 return ltdb_index_add_el(module
, ldb_dn_get_linearized(dn
), el
);
1277 add the index entries for a new record
1279 int ltdb_index_add_new(struct ldb_module
*module
, const struct ldb_message
*msg
)
1284 if (ldb_dn_is_special(msg
->dn
)) {
1288 dn
= ldb_dn_get_linearized(msg
->dn
);
1290 return LDB_ERR_OPERATIONS_ERROR
;
1293 ret
= ltdb_index_add_all(module
, dn
, msg
->elements
, msg
->num_elements
);
1294 if (ret
!= LDB_SUCCESS
) {
1298 return ltdb_index_onelevel(module
, msg
, 1);
1303 delete an index entry for one message element
1305 int ltdb_index_del_value(struct ldb_module
*module
, struct ldb_dn
*dn
,
1306 struct ldb_message_element
*el
, unsigned int v_idx
)
1308 struct ldb_context
*ldb
;
1309 struct ldb_dn
*dn_key
;
1313 struct dn_list
*list
;
1315 ldb
= ldb_module_get_ctx(module
);
1317 dn_str
= ldb_dn_get_linearized(dn
);
1318 if (dn_str
== NULL
) {
1319 return LDB_ERR_OPERATIONS_ERROR
;
1322 if (dn_str
[0] == '@') {
1326 dn_key
= ltdb_index_key(ldb
, el
->name
, &el
->values
[v_idx
], NULL
);
1328 return LDB_ERR_OPERATIONS_ERROR
;
1331 list
= talloc_zero(dn_key
, struct dn_list
);
1333 talloc_free(dn_key
);
1334 return LDB_ERR_OPERATIONS_ERROR
;
1337 ret
= ltdb_dn_list_load(module
, dn_key
, list
);
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 if (ret
!= LDB_SUCCESS
) {
1346 talloc_free(dn_key
);
1350 i
= ltdb_dn_list_find_str(list
, dn_str
);
1352 /* nothing to delete */
1353 talloc_free(dn_key
);
1357 j
= (unsigned int) i
;
1358 if (j
!= list
->count
- 1) {
1359 memmove(&list
->dn
[j
], &list
->dn
[j
+1], sizeof(list
->dn
[0])*(list
->count
- (j
+1)));
1362 list
->dn
= talloc_realloc(list
, list
->dn
, struct ldb_val
, list
->count
);
1364 ret
= ltdb_dn_list_store(module
, dn_key
, list
);
1366 talloc_free(dn_key
);
1372 delete the index entries for a element
1373 return -1 on failure
1375 int ltdb_index_del_element(struct ldb_module
*module
, struct ldb_dn
*dn
,
1376 struct ldb_message_element
*el
)
1378 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1383 if (!ltdb
->cache
->attribute_indexes
) {
1384 /* no indexed fields */
1388 dn_str
= ldb_dn_get_linearized(dn
);
1389 if (dn_str
== NULL
) {
1390 return LDB_ERR_OPERATIONS_ERROR
;
1393 if (dn_str
[0] == '@') {
1397 if (!ltdb_is_indexed(ltdb
->cache
->indexlist
, el
->name
)) {
1400 for (i
= 0; i
< el
->num_values
; i
++) {
1401 ret
= ltdb_index_del_value(module
, dn
, el
, i
);
1402 if (ret
!= LDB_SUCCESS
) {
1411 delete the index entries for a record
1412 return -1 on failure
1414 int ltdb_index_delete(struct ldb_module
*module
, const struct ldb_message
*msg
)
1416 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1420 if (ldb_dn_is_special(msg
->dn
)) {
1424 ret
= ltdb_index_onelevel(module
, msg
, 0);
1425 if (ret
!= LDB_SUCCESS
) {
1429 if (!ltdb
->cache
->attribute_indexes
) {
1430 /* no indexed fields */
1434 for (i
= 0; i
< msg
->num_elements
; i
++) {
1435 ret
= ltdb_index_del_element(module
, msg
->dn
, &msg
->elements
[i
]);
1436 if (ret
!= LDB_SUCCESS
) {
1446 traversal function that deletes all @INDEX records
1448 static int delete_index(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
1450 struct ldb_module
*module
= state
;
1451 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1452 const char *dnstr
= "DN=" LTDB_INDEX
":";
1453 struct dn_list list
;
1458 if (strncmp((char *)key
.dptr
, dnstr
, strlen(dnstr
)) != 0) {
1461 /* we need to put a empty list in the internal tdb for this
1466 /* the offset of 3 is to remove the DN= prefix. */
1467 v
.data
= key
.dptr
+ 3;
1468 v
.length
= strnlen((char *)key
.dptr
, key
.dsize
) - 3;
1470 dn
= ldb_dn_from_ldb_val(ltdb
, ldb_module_get_ctx(module
), &v
);
1471 ret
= ltdb_dn_list_store(module
, dn
, &list
);
1472 if (ret
!= LDB_SUCCESS
) {
1473 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
1474 "Unable to store null index for %s\n",
1475 ldb_dn_get_linearized(dn
));
1483 struct ltdb_reindex_context
{
1484 struct ldb_module
*module
;
1489 traversal function that adds @INDEX records during a re index
1491 static int re_index(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
1493 struct ldb_context
*ldb
;
1494 struct ltdb_reindex_context
*ctx
= (struct ltdb_reindex_context
*)state
;
1495 struct ldb_module
*module
= ctx
->module
;
1496 struct ldb_message
*msg
;
1497 const char *dn
= NULL
;
1501 ldb
= ldb_module_get_ctx(module
);
1503 if (strncmp((char *)key
.dptr
, "DN=@", 4) == 0 ||
1504 strncmp((char *)key
.dptr
, "DN=", 3) != 0) {
1508 msg
= ldb_msg_new(module
);
1513 ret
= ldb_unpack_data(ldb
, (struct ldb_val
*)&data
, msg
);
1515 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid data for index %s\n",
1516 ldb_dn_get_linearized(msg
->dn
));
1521 /* check if the DN key has changed, perhaps due to the
1522 case insensitivity of an element changing */
1523 key2
= ltdb_key(module
, msg
->dn
);
1524 if (key2
.dptr
== NULL
) {
1525 /* probably a corrupt record ... darn */
1526 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid DN in re_index: %s",
1527 ldb_dn_get_linearized(msg
->dn
));
1531 if (strcmp((char *)key2
.dptr
, (char *)key
.dptr
) != 0) {
1532 tdb_delete(tdb
, key
);
1533 tdb_store(tdb
, key2
, data
, 0);
1535 talloc_free(key2
.dptr
);
1537 if (msg
->dn
== NULL
) {
1538 dn
= (char *)key
.dptr
+ 3;
1540 dn
= ldb_dn_get_linearized(msg
->dn
);
1543 ret
= ltdb_index_onelevel(module
, msg
, 1);
1544 if (ret
!= LDB_SUCCESS
) {
1545 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
1546 "Adding special ONE LEVEL index failed (%s)!",
1547 ldb_dn_get_linearized(msg
->dn
));
1552 ret
= ltdb_index_add_all(module
, dn
, msg
->elements
, msg
->num_elements
);
1554 if (ret
!= LDB_SUCCESS
) {
1566 force a complete reindex of the database
1568 int ltdb_reindex(struct ldb_module
*module
)
1570 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
1572 struct ltdb_reindex_context ctx
;
1574 if (ltdb_cache_reload(module
) != 0) {
1575 return LDB_ERR_OPERATIONS_ERROR
;
1578 /* first traverse the database deleting any @INDEX records by
1579 * putting NULL entries in the in-memory tdb
1581 ret
= tdb_traverse(ltdb
->tdb
, delete_index
, module
);
1583 return LDB_ERR_OPERATIONS_ERROR
;
1586 /* if we don't have indexes we have nothing todo */
1587 if (ltdb
->cache
->indexlist
->num_elements
== 0) {
1591 ctx
.module
= module
;
1594 /* now traverse adding any indexes for normal LDB records */
1595 ret
= tdb_traverse(ltdb
->tdb
, re_index
, &ctx
);
1597 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
1598 ldb_asprintf_errstring(ldb
, "reindexing traverse failed: %s", ldb_errstring(ldb
));
1599 return LDB_ERR_OPERATIONS_ERROR
;
1602 if (ctx
.error
!= LDB_SUCCESS
) {
1603 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
1604 ldb_asprintf_errstring(ldb
, "reindexing failed: %s", ldb_errstring(ldb
));