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
36 LDB Index design and choice of TDB key:
37 =======================================
39 LDB has index records held as LDB objects with a special record like:
43 value may be base64 encoded, if it is deemed not printable:
45 dn: @INDEX:attr::base64-value
47 In each record, there is two possible formats:
49 The original format is:
50 -----------------------
52 dn: @INDEX:NAME:DNSUPDATEPROXY
54 @IDX: CN=DnsUpdateProxy,CN=Users,DC=addom,DC=samba,DC=example,DC=com
56 In this format, @IDX is multi-valued, one entry for each match
58 The corrosponding entry is stored in a TDB record with key:
60 DN=CN=DNSUPDATEPROXY,CN=USERS,DC=ADDOM,DC=SAMBA,DC=EXAMPLE,DC=COM
62 (This allows a scope BASE search to directly find the record via
63 a simple casefold of the DN).
65 The original mixed-case DN is stored in the entry iself.
68 The new 'GUID index' format is:
69 -------------------------------
71 dn: @INDEX:NAME:DNSUPDATEPROXY
73 @IDX: <binary GUID>[<binary GUID>[...]]
75 The binary guid is 16 bytes, as bytes and not expanded as hexidecimal
76 or pretty-printed. The GUID is chosen from the message to be stored
77 by the @IDXGUID attribute on @INDEXLIST.
79 If there are multiple values the @IDX value simply becomes longer,
82 The corrosponding entry is stored in a TDB record with key:
86 This allows a very quick translation between the fixed-length index
87 values and the TDB key, while seperating entries from other data
88 in the TDB, should they be unlucky enough to start with the bytes of
91 Additionally, this allows a scope BASE search to directly find the
92 record via a simple match on a GUID= extended DN, controlled via
93 @IDX_DN_GUID on @INDEXLIST
95 Exception for special @ DNs:
97 @BASEINFO, @INDEXLIST and all other special DNs are stored as per the
98 original format, as they are never referenced in an index and are used
99 to bootstrap the database.
102 Control points for choice of index mode
103 ---------------------------------------
105 The choice of index and TDB key mode is made based (for example, from
106 Samba) on entries in the @INDEXLIST DN:
112 By default, the original DN format is used.
115 Control points for choosing indexed attributes
116 ----------------------------------------------
118 @IDXATTR controls if an attribute is indexed
121 @IDXATTR: samAccountName
122 @IDXATTR: nETBIOSName
128 void ldb_schema_set_override_GUID_index(struct ldb_context *ldb,
129 const char *GUID_index_attribute,
130 const char *GUID_index_dn_component)
132 This is used, particularly in combination with the below, instead of
133 the @IDXGUID and @IDX_DN_GUID values in @INDEXLIST.
135 void ldb_schema_set_override_indexlist(struct ldb_context *ldb,
136 bool one_level_indexes);
137 void ldb_schema_attribute_set_override_handler(struct ldb_context *ldb,
138 ldb_attribute_handler_override_fn_t override,
141 When the above two functions are called in combination, the @INDEXLIST
142 values are not read from the DB, so
143 ldb_schema_set_override_GUID_index() must be called.
148 #include "ldb_private.h"
149 #include "lib/util/binsearch.h"
155 * Do not optimise the intersection of this list,
156 * we must never return an entry not in this
157 * list. This allows the index for
158 * SCOPE_ONELEVEL to be trusted.
164 struct tdb_context
*itdb
;
168 static int ltdb_write_index_dn_guid(struct ldb_module
*module
,
169 const struct ldb_message
*msg
,
171 static int ltdb_index_dn_base_dn(struct ldb_module
*module
,
172 struct ltdb_private
*ltdb
,
173 struct ldb_dn
*base_dn
,
174 struct dn_list
*dn_list
);
176 static void ltdb_dn_list_sort(struct ltdb_private
*ltdb
,
177 struct dn_list
*list
);
179 /* we put a @IDXVERSION attribute on index entries. This
180 allows us to tell if it was written by an older version
182 #define LTDB_INDEXING_VERSION 2
184 #define LTDB_GUID_INDEXING_VERSION 3
186 /* enable the idxptr mode when transactions start */
187 int ltdb_index_transaction_start(struct ldb_module
*module
)
189 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
190 ltdb
->idxptr
= talloc_zero(ltdb
, struct ltdb_idxptr
);
191 if (ltdb
->idxptr
== NULL
) {
192 return ldb_oom(ldb_module_get_ctx(module
));
199 see if two ldb_val structures contain exactly the same data
200 return -1 or 1 for a mismatch, 0 for match
202 static int ldb_val_equal_exact_for_qsort(const struct ldb_val
*v1
,
203 const struct ldb_val
*v2
)
205 if (v1
->length
> v2
->length
) {
208 if (v1
->length
< v2
->length
) {
211 return memcmp(v1
->data
, v2
->data
, v1
->length
);
215 see if two ldb_val structures contain exactly the same data
216 return -1 or 1 for a mismatch, 0 for match
218 static int ldb_val_equal_exact_ordered(const struct ldb_val v1
,
219 const struct ldb_val
*v2
)
221 if (v1
.length
> v2
->length
) {
224 if (v1
.length
< v2
->length
) {
227 return memcmp(v1
.data
, v2
->data
, v1
.length
);
232 find a entry in a dn_list, using a ldb_val. Uses a case sensitive
233 binary-safe comparison for the 'dn' returns -1 if not found
235 This is therefore safe when the value is a GUID in the future
237 static int ltdb_dn_list_find_val(struct ltdb_private
*ltdb
,
238 const struct dn_list
*list
,
239 const struct ldb_val
*v
)
242 struct ldb_val
*exact
= NULL
, *next
= NULL
;
244 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
245 for (i
=0; i
<list
->count
; i
++) {
246 if (ldb_val_equal_exact(&list
->dn
[i
], v
) == 1) {
253 BINARY_ARRAY_SEARCH_GTE(list
->dn
, list
->count
,
254 *v
, ldb_val_equal_exact_ordered
,
259 /* Not required, but keeps the compiler quiet */
264 i
= exact
- list
->dn
;
269 find a entry in a dn_list. Uses a case sensitive comparison with the dn
270 returns -1 if not found
272 static int ltdb_dn_list_find_msg(struct ltdb_private
*ltdb
,
273 struct dn_list
*list
,
274 const struct ldb_message
*msg
)
277 const struct ldb_val
*key_val
;
278 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
279 const char *dn_str
= ldb_dn_get_linearized(msg
->dn
);
280 v
.data
= discard_const_p(unsigned char, dn_str
);
281 v
.length
= strlen(dn_str
);
283 key_val
= ldb_msg_find_ldb_val(msg
,
284 ltdb
->cache
->GUID_index_attribute
);
285 if (key_val
== NULL
) {
290 return ltdb_dn_list_find_val(ltdb
, list
, &v
);
294 this is effectively a cast function, but with lots of paranoia
295 checks and also copes with CPUs that are fussy about pointer
298 static struct dn_list
*ltdb_index_idxptr(struct ldb_module
*module
, TDB_DATA rec
, bool check_parent
)
300 struct dn_list
*list
;
301 if (rec
.dsize
!= sizeof(void *)) {
302 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
303 "Bad data size for idxptr %u", (unsigned)rec
.dsize
);
306 /* note that we can't just use a cast here, as rec.dptr may
307 not be aligned sufficiently for a pointer. A cast would cause
308 platforms like some ARM CPUs to crash */
309 memcpy(&list
, rec
.dptr
, sizeof(void *));
310 list
= talloc_get_type(list
, struct dn_list
);
312 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
313 "Bad type '%s' for idxptr",
314 talloc_get_name(list
));
317 if (check_parent
&& list
->dn
&& talloc_parent(list
->dn
) != list
) {
318 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
319 "Bad parent '%s' for idxptr",
320 talloc_get_name(talloc_parent(list
->dn
)));
327 return the @IDX list in an index entry for a dn as a
330 static int ltdb_dn_list_load(struct ldb_module
*module
,
331 struct ltdb_private
*ltdb
,
332 struct ldb_dn
*dn
, struct dn_list
*list
)
334 struct ldb_message
*msg
;
336 struct ldb_message_element
*el
;
338 struct dn_list
*list2
;
344 /* see if we have any in-memory index entries */
345 if (ltdb
->idxptr
== NULL
||
346 ltdb
->idxptr
->itdb
== NULL
) {
350 key
.dptr
= discard_const_p(unsigned char, ldb_dn_get_linearized(dn
));
351 key
.dsize
= strlen((char *)key
.dptr
);
353 rec
= tdb_fetch(ltdb
->idxptr
->itdb
, key
);
354 if (rec
.dptr
== NULL
) {
358 /* we've found an in-memory index entry */
359 list2
= ltdb_index_idxptr(module
, rec
, true);
362 return LDB_ERR_OPERATIONS_ERROR
;
370 msg
= ldb_msg_new(list
);
372 return LDB_ERR_OPERATIONS_ERROR
;
375 ret
= ltdb_search_dn1(module
, dn
, msg
,
376 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
377 |LDB_UNPACK_DATA_FLAG_NO_DN
);
378 if (ret
!= LDB_SUCCESS
) {
383 el
= ldb_msg_find_element(msg
, LTDB_IDX
);
389 version
= ldb_msg_find_attr_as_int(msg
, LTDB_IDXVERSION
, 0);
392 * we avoid copying the strings by stealing the list. We have
393 * to steal msg onto el->values (which looks odd) because we
394 * asked for the memory to be allocated on msg, not on each
395 * value with LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC above
397 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
398 /* check indexing version number */
399 if (version
!= LTDB_INDEXING_VERSION
) {
400 ldb_debug_set(ldb_module_get_ctx(module
),
402 "Wrong DN index version %d "
403 "expected %d for %s",
404 version
, LTDB_INDEXING_VERSION
,
405 ldb_dn_get_linearized(dn
));
407 return LDB_ERR_OPERATIONS_ERROR
;
410 talloc_steal(el
->values
, msg
);
411 list
->dn
= talloc_steal(list
, el
->values
);
412 list
->count
= el
->num_values
;
415 if (version
!= LTDB_GUID_INDEXING_VERSION
) {
416 /* This is quite likely during the DB startup
417 on first upgrade to using a GUID index */
418 ldb_debug_set(ldb_module_get_ctx(module
),
420 "Wrong GUID index version %d "
421 "expected %d for %s",
422 version
, LTDB_GUID_INDEXING_VERSION
,
423 ldb_dn_get_linearized(dn
));
425 return LDB_ERR_OPERATIONS_ERROR
;
428 if (el
->num_values
!= 1) {
430 return LDB_ERR_OPERATIONS_ERROR
;
433 if ((el
->values
[0].length
% LTDB_GUID_SIZE
) != 0) {
435 return LDB_ERR_OPERATIONS_ERROR
;
438 list
->count
= el
->values
[0].length
/ LTDB_GUID_SIZE
;
439 list
->dn
= talloc_array(list
, struct ldb_val
, list
->count
);
440 if (list
->dn
== NULL
) {
442 return LDB_ERR_OPERATIONS_ERROR
;
446 * The actual data is on msg, due to
447 * LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
449 talloc_steal(list
->dn
, msg
);
450 for (i
= 0; i
< list
->count
; i
++) {
452 = &el
->values
[0].data
[i
* LTDB_GUID_SIZE
];
453 list
->dn
[i
].length
= LTDB_GUID_SIZE
;
457 /* We don't need msg->elements any more */
458 talloc_free(msg
->elements
);
462 int ltdb_key_dn_from_idx(struct ldb_module
*module
,
463 struct ltdb_private
*ltdb
,
468 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
470 struct dn_list
*list
= talloc(mem_ctx
, struct dn_list
);
473 return LDB_ERR_OPERATIONS_ERROR
;
476 ret
= ltdb_index_dn_base_dn(module
, ltdb
, dn
, list
);
477 if (ret
!= LDB_SUCCESS
) {
482 if (list
->count
== 0) {
484 return LDB_ERR_NO_SUCH_OBJECT
;
486 if (list
->count
> 1) {
487 const char *dn_str
= ldb_dn_get_linearized(dn
);
488 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
490 ": Failed to read DN index "
491 "against %s for %s: too many "
493 ltdb
->cache
->GUID_index_attribute
,
494 dn_str
, list
->count
);
496 return LDB_ERR_CONSTRAINT_VIOLATION
;
499 /* The tdb_key memory is allocated by the caller */
500 ret
= ltdb_guid_to_key(module
, ltdb
,
501 &list
->dn
[0], tdb_key
);
504 if (ret
!= LDB_SUCCESS
) {
505 return LDB_ERR_OPERATIONS_ERROR
;
514 save a dn_list into a full @IDX style record
516 static int ltdb_dn_list_store_full(struct ldb_module
*module
,
517 struct ltdb_private
*ltdb
,
519 struct dn_list
*list
)
521 struct ldb_message
*msg
;
524 msg
= ldb_msg_new(module
);
526 return ldb_module_oom(module
);
531 if (list
->count
== 0) {
532 ret
= ltdb_delete_noindex(module
, msg
);
533 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
540 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
541 ret
= ldb_msg_add_fmt(msg
, LTDB_IDXVERSION
, "%u",
542 LTDB_INDEXING_VERSION
);
543 if (ret
!= LDB_SUCCESS
) {
545 return ldb_module_oom(module
);
548 ret
= ldb_msg_add_fmt(msg
, LTDB_IDXVERSION
, "%u",
549 LTDB_GUID_INDEXING_VERSION
);
550 if (ret
!= LDB_SUCCESS
) {
552 return ldb_module_oom(module
);
556 if (list
->count
> 0) {
557 struct ldb_message_element
*el
;
559 ret
= ldb_msg_add_empty(msg
, LTDB_IDX
, LDB_FLAG_MOD_ADD
, &el
);
560 if (ret
!= LDB_SUCCESS
) {
562 return ldb_module_oom(module
);
565 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
566 el
->values
= list
->dn
;
567 el
->num_values
= list
->count
;
571 el
->values
= talloc_array(msg
,
573 if (el
->values
== NULL
) {
575 return ldb_module_oom(module
);
578 v
.data
= talloc_array_size(el
->values
,
581 if (v
.data
== NULL
) {
583 return ldb_module_oom(module
);
586 v
.length
= talloc_get_size(v
.data
);
588 for (i
= 0; i
< list
->count
; i
++) {
589 if (list
->dn
[i
].length
!=
592 return ldb_module_operr(module
);
594 memcpy(&v
.data
[LTDB_GUID_SIZE
*i
],
603 ret
= ltdb_store(module
, msg
, TDB_REPLACE
);
609 save a dn_list into the database, in either @IDX or internal format
611 static int ltdb_dn_list_store(struct ldb_module
*module
, struct ldb_dn
*dn
,
612 struct dn_list
*list
)
614 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
617 struct dn_list
*list2
;
619 if (ltdb
->idxptr
== NULL
) {
620 return ltdb_dn_list_store_full(module
, ltdb
,
624 if (ltdb
->idxptr
->itdb
== NULL
) {
625 ltdb
->idxptr
->itdb
= tdb_open(NULL
, 1000, TDB_INTERNAL
, O_RDWR
, 0);
626 if (ltdb
->idxptr
->itdb
== NULL
) {
627 return LDB_ERR_OPERATIONS_ERROR
;
631 key
.dptr
= discard_const_p(unsigned char, ldb_dn_get_linearized(dn
));
632 if (key
.dptr
== NULL
) {
633 return LDB_ERR_OPERATIONS_ERROR
;
635 key
.dsize
= strlen((char *)key
.dptr
);
637 rec
= tdb_fetch(ltdb
->idxptr
->itdb
, key
);
638 if (rec
.dptr
!= NULL
) {
639 list2
= ltdb_index_idxptr(module
, rec
, false);
642 return LDB_ERR_OPERATIONS_ERROR
;
645 list2
->dn
= talloc_steal(list2
, list
->dn
);
646 list2
->count
= list
->count
;
650 list2
= talloc(ltdb
->idxptr
, struct dn_list
);
652 return LDB_ERR_OPERATIONS_ERROR
;
654 list2
->dn
= talloc_steal(list2
, list
->dn
);
655 list2
->count
= list
->count
;
657 rec
.dptr
= (uint8_t *)&list2
;
658 rec
.dsize
= sizeof(void *);
662 * This is not a store into the main DB, but into an in-memory
663 * TDB, so we don't need a guard on ltdb->read_only
665 ret
= tdb_store(ltdb
->idxptr
->itdb
, key
, rec
, TDB_INSERT
);
667 return ltdb_err_map(tdb_error(ltdb
->idxptr
->itdb
));
673 traverse function for storing the in-memory index entries on disk
675 static int ltdb_index_traverse_store(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
677 struct ldb_module
*module
= state
;
678 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
680 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
682 struct dn_list
*list
;
684 list
= ltdb_index_idxptr(module
, data
, true);
686 ltdb
->idxptr
->error
= LDB_ERR_OPERATIONS_ERROR
;
691 v
.length
= strnlen((char *)key
.dptr
, key
.dsize
);
693 dn
= ldb_dn_from_ldb_val(module
, ldb
, &v
);
695 ldb_asprintf_errstring(ldb
, "Failed to parse index key %*.*s as an LDB DN", (int)v
.length
, (int)v
.length
, (const char *)v
.data
);
696 ltdb
->idxptr
->error
= LDB_ERR_OPERATIONS_ERROR
;
700 ltdb
->idxptr
->error
= ltdb_dn_list_store_full(module
, ltdb
,
703 if (ltdb
->idxptr
->error
!= 0) {
709 /* cleanup the idxptr mode when transaction commits */
710 int ltdb_index_transaction_commit(struct ldb_module
*module
)
712 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
715 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
717 ldb_reset_err_string(ldb
);
719 if (ltdb
->idxptr
->itdb
) {
720 tdb_traverse(ltdb
->idxptr
->itdb
, ltdb_index_traverse_store
, module
);
721 tdb_close(ltdb
->idxptr
->itdb
);
724 ret
= ltdb
->idxptr
->error
;
725 if (ret
!= LDB_SUCCESS
) {
726 if (!ldb_errstring(ldb
)) {
727 ldb_set_errstring(ldb
, ldb_strerror(ret
));
729 ldb_asprintf_errstring(ldb
, "Failed to store index records in transaction commit: %s", ldb_errstring(ldb
));
732 talloc_free(ltdb
->idxptr
);
737 /* cleanup the idxptr mode when transaction cancels */
738 int ltdb_index_transaction_cancel(struct ldb_module
*module
)
740 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
741 if (ltdb
->idxptr
&& ltdb
->idxptr
->itdb
) {
742 tdb_close(ltdb
->idxptr
->itdb
);
744 talloc_free(ltdb
->idxptr
);
751 return the dn key to be used for an index
752 the caller is responsible for freeing
754 static struct ldb_dn
*ltdb_index_key(struct ldb_context
*ldb
,
755 struct ltdb_private
*ltdb
,
756 const char *attr
, const struct ldb_val
*value
,
757 const struct ldb_schema_attribute
**ap
)
761 const struct ldb_schema_attribute
*a
= NULL
;
762 char *attr_folded
= NULL
;
763 const char *attr_for_dn
= NULL
;
765 bool should_b64_encode
;
767 if (attr
[0] == '@') {
774 attr_folded
= ldb_attr_casefold(ldb
, attr
);
779 attr_for_dn
= attr_folded
;
781 a
= ldb_schema_attribute_by_name(ldb
, attr
);
785 r
= a
->syntax
->canonicalise_fn(ldb
, ldb
, value
, &v
);
786 if (r
!= LDB_SUCCESS
) {
787 const char *errstr
= ldb_errstring(ldb
);
788 /* canonicalisation can be refused. For
789 example, a attribute that takes wildcards
790 will refuse to canonicalise if the value
791 contains a wildcard */
792 ldb_asprintf_errstring(ldb
,
793 "Failed to create index "
794 "key for attribute '%s':%s%s%s",
795 attr
, ldb_strerror(r
),
798 talloc_free(attr_folded
);
804 * We do not base 64 encode a DN in a key, it has already been
805 * casefold and lineraized, that is good enough. That already
806 * avoids embedded NUL etc.
808 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
809 if (strcmp(attr
, LTDB_IDXDN
) == 0) {
810 should_b64_encode
= false;
811 } else if (strcmp(attr
, LTDB_IDXONE
) == 0) {
813 * We can only change the behaviour for IDXONE
814 * when the GUID index is enabled
816 should_b64_encode
= false;
819 = ldb_should_b64_encode(ldb
, &v
);
822 should_b64_encode
= ldb_should_b64_encode(ldb
, &v
);
825 if (should_b64_encode
) {
826 char *vstr
= ldb_base64_encode(ldb
, (char *)v
.data
, v
.length
);
828 talloc_free(attr_folded
);
831 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s::%s", LTDB_INDEX
,
835 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s:%.*s", LTDB_INDEX
,
837 (int)v
.length
, (char *)v
.data
);
840 if (v
.data
!= value
->data
) {
843 talloc_free(attr_folded
);
849 see if a attribute value is in the list of indexed attributes
851 static bool ltdb_is_indexed(struct ldb_module
*module
,
852 struct ltdb_private
*ltdb
,
855 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
857 struct ldb_message_element
*el
;
859 if ((ltdb
->cache
->GUID_index_attribute
!= NULL
) &&
861 ltdb
->cache
->GUID_index_attribute
) == 0)) {
862 /* Implicity covered, this is the index key */
865 if (ldb
->schema
.index_handler_override
) {
866 const struct ldb_schema_attribute
*a
867 = ldb_schema_attribute_by_name(ldb
, attr
);
873 if (a
->flags
& LDB_ATTR_FLAG_INDEXED
) {
880 if (!ltdb
->cache
->attribute_indexes
) {
884 el
= ldb_msg_find_element(ltdb
->cache
->indexlist
, LTDB_IDXATTR
);
889 /* TODO: this is too expensive! At least use a binary search */
890 for (i
=0; i
<el
->num_values
; i
++) {
891 if (ldb_attr_cmp((char *)el
->values
[i
].data
, attr
) == 0) {
899 in the following logic functions, the return value is treated as
902 LDB_SUCCESS: we found some matching index values
904 LDB_ERR_NO_SUCH_OBJECT: we know for sure that no object matches
906 LDB_ERR_OPERATIONS_ERROR: indexing could not answer the call,
907 we'll need a full search
911 return a list of dn's that might match a simple indexed search (an
912 equality search only)
914 static int ltdb_index_dn_simple(struct ldb_module
*module
,
915 struct ltdb_private
*ltdb
,
916 const struct ldb_parse_tree
*tree
,
917 struct dn_list
*list
)
919 struct ldb_context
*ldb
;
923 ldb
= ldb_module_get_ctx(module
);
928 /* if the attribute isn't in the list of indexed attributes then
929 this node needs a full search */
930 if (!ltdb_is_indexed(module
, ltdb
, tree
->u
.equality
.attr
)) {
931 return LDB_ERR_OPERATIONS_ERROR
;
934 /* the attribute is indexed. Pull the list of DNs that match the
936 dn
= ltdb_index_key(ldb
, ltdb
,
937 tree
->u
.equality
.attr
,
938 &tree
->u
.equality
.value
, NULL
);
939 if (!dn
) return LDB_ERR_OPERATIONS_ERROR
;
941 ret
= ltdb_dn_list_load(module
, ltdb
, dn
, list
);
947 static bool list_union(struct ldb_context
*ldb
,
948 struct ltdb_private
*ltdb
,
949 struct dn_list
*list
, struct dn_list
*list2
);
952 return a list of dn's that might match a leaf indexed search
954 static int ltdb_index_dn_leaf(struct ldb_module
*module
,
955 struct ltdb_private
*ltdb
,
956 const struct ldb_parse_tree
*tree
,
957 struct dn_list
*list
)
959 if (ltdb
->disallow_dn_filter
&&
960 (ldb_attr_cmp(tree
->u
.equality
.attr
, "dn") == 0)) {
961 /* in AD mode we do not support "(dn=...)" search filters */
966 if (tree
->u
.equality
.attr
[0] == '@') {
967 /* Do not allow a indexed search against an @ */
972 if (ldb_attr_dn(tree
->u
.equality
.attr
) == 0) {
974 = ldb_dn_from_ldb_val(list
,
975 ldb_module_get_ctx(module
),
976 &tree
->u
.equality
.value
);
978 /* If we can't parse it, no match */
985 * Re-use the same code we use for a SCOPE_BASE
988 * We can't call TALLOC_FREE(dn) as this must belong
989 * to list for the memory to remain valid.
991 return ltdb_index_dn_base_dn(module
, ltdb
, dn
, list
);
993 } else if ((ltdb
->cache
->GUID_index_attribute
!= NULL
) &&
994 (ldb_attr_cmp(tree
->u
.equality
.attr
,
995 ltdb
->cache
->GUID_index_attribute
) == 0)) {
997 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
998 list
->dn
= talloc_array(list
, struct ldb_val
, 1);
999 if (list
->dn
== NULL
) {
1000 ldb_module_oom(module
);
1001 return LDB_ERR_OPERATIONS_ERROR
;
1004 * We need to go via the canonicalise_fn() to
1005 * ensure we get the index in binary, rather
1008 ret
= ltdb
->GUID_index_syntax
->canonicalise_fn(ldb
,
1010 &tree
->u
.equality
.value
,
1012 if (ret
!= LDB_SUCCESS
) {
1013 return LDB_ERR_OPERATIONS_ERROR
;
1019 return ltdb_index_dn_simple(module
, ltdb
, tree
, list
);
1027 static bool list_intersect(struct ldb_context
*ldb
,
1028 struct ltdb_private
*ltdb
,
1029 struct dn_list
*list
, const struct dn_list
*list2
)
1031 const struct dn_list
*short_list
, *long_list
;
1032 struct dn_list
*list3
;
1035 if (list
->count
== 0) {
1039 if (list2
->count
== 0) {
1046 /* the indexing code is allowed to return a longer list than
1047 what really matches, as all results are filtered by the
1048 full expression at the end - this shortcut avoids a lot of
1049 work in some cases */
1050 if (list
->count
< 2 && list2
->count
> 10 && list2
->strict
== false) {
1053 if (list2
->count
< 2 && list
->count
> 10 && list
->strict
== false) {
1054 list
->count
= list2
->count
;
1055 list
->dn
= list2
->dn
;
1056 /* note that list2 may not be the parent of list2->dn,
1057 as list2->dn may be owned by ltdb->idxptr. In that
1058 case we expect this reparent call to fail, which is
1060 talloc_reparent(list2
, list
, list2
->dn
);
1064 if (list
->count
> list2
->count
) {
1072 list3
= talloc_zero(list
, struct dn_list
);
1073 if (list3
== NULL
) {
1077 list3
->dn
= talloc_array(list3
, struct ldb_val
,
1078 MIN(list
->count
, list2
->count
));
1085 for (i
=0;i
<short_list
->count
;i
++) {
1086 /* For the GUID index case, this is a binary search */
1087 if (ltdb_dn_list_find_val(ltdb
, long_list
,
1088 &short_list
->dn
[i
]) != -1) {
1089 list3
->dn
[list3
->count
] = short_list
->dn
[i
];
1094 list
->strict
|= list2
->strict
;
1095 list
->dn
= talloc_steal(list
, list3
->dn
);
1096 list
->count
= list3
->count
;
1107 static bool list_union(struct ldb_context
*ldb
,
1108 struct ltdb_private
*ltdb
,
1109 struct dn_list
*list
, struct dn_list
*list2
)
1111 struct ldb_val
*dn3
;
1112 unsigned int i
= 0, j
= 0, k
= 0;
1114 if (list2
->count
== 0) {
1119 if (list
->count
== 0) {
1121 list
->count
= list2
->count
;
1122 list
->dn
= list2
->dn
;
1123 /* note that list2 may not be the parent of list2->dn,
1124 as list2->dn may be owned by ltdb->idxptr. In that
1125 case we expect this reparent call to fail, which is
1127 talloc_reparent(list2
, list
, list2
->dn
);
1132 * Sort the lists (if not in GUID DN mode) so we can do
1133 * the de-duplication during the merge
1135 * NOTE: This can sort the in-memory index values, as list or
1136 * list2 might not be a copy!
1138 ltdb_dn_list_sort(ltdb
, list
);
1139 ltdb_dn_list_sort(ltdb
, list2
);
1141 dn3
= talloc_array(list
, struct ldb_val
, list
->count
+ list2
->count
);
1147 while (i
< list
->count
|| j
< list2
->count
) {
1149 if (i
>= list
->count
) {
1151 } else if (j
>= list2
->count
) {
1154 cmp
= ldb_val_equal_exact_ordered(list
->dn
[i
],
1160 dn3
[k
] = list
->dn
[i
];
1163 } else if (cmp
> 0) {
1165 dn3
[k
] = list2
->dn
[j
];
1169 /* Equal, take list */
1170 dn3
[k
] = list
->dn
[i
];
1183 static int ltdb_index_dn(struct ldb_module
*module
,
1184 struct ltdb_private
*ltdb
,
1185 const struct ldb_parse_tree
*tree
,
1186 struct dn_list
*list
);
1190 process an OR list (a union)
1192 static int ltdb_index_dn_or(struct ldb_module
*module
,
1193 struct ltdb_private
*ltdb
,
1194 const struct ldb_parse_tree
*tree
,
1195 struct dn_list
*list
)
1197 struct ldb_context
*ldb
;
1200 ldb
= ldb_module_get_ctx(module
);
1205 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
1206 struct dn_list
*list2
;
1209 list2
= talloc_zero(list
, struct dn_list
);
1210 if (list2
== NULL
) {
1211 return LDB_ERR_OPERATIONS_ERROR
;
1214 ret
= ltdb_index_dn(module
, ltdb
,
1215 tree
->u
.list
.elements
[i
], list2
);
1217 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1223 if (ret
!= LDB_SUCCESS
) {
1229 if (!list_union(ldb
, ltdb
, list
, list2
)) {
1231 return LDB_ERR_OPERATIONS_ERROR
;
1235 if (list
->count
== 0) {
1236 return LDB_ERR_NO_SUCH_OBJECT
;
1244 NOT an index results
1246 static int ltdb_index_dn_not(struct ldb_module
*module
,
1247 struct ltdb_private
*ltdb
,
1248 const struct ldb_parse_tree
*tree
,
1249 struct dn_list
*list
)
1251 /* the only way to do an indexed not would be if we could
1252 negate the not via another not or if we knew the total
1253 number of database elements so we could know that the
1254 existing expression covered the whole database.
1256 instead, we just give up, and rely on a full index scan
1257 (unless an outer & manages to reduce the list)
1259 return LDB_ERR_OPERATIONS_ERROR
;
1263 * These things are unique, so avoid a full scan if this is a search
1264 * by GUID, DN or a unique attribute
1266 static bool ltdb_index_unique(struct ldb_context
*ldb
,
1267 struct ltdb_private
*ltdb
,
1270 const struct ldb_schema_attribute
*a
;
1271 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1272 if (ldb_attr_cmp(attr
, ltdb
->cache
->GUID_index_attribute
) == 0) {
1276 if (ldb_attr_dn(attr
) == 0) {
1280 a
= ldb_schema_attribute_by_name(ldb
, attr
);
1281 if (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
) {
1288 process an AND expression (intersection)
1290 static int ltdb_index_dn_and(struct ldb_module
*module
,
1291 struct ltdb_private
*ltdb
,
1292 const struct ldb_parse_tree
*tree
,
1293 struct dn_list
*list
)
1295 struct ldb_context
*ldb
;
1299 ldb
= ldb_module_get_ctx(module
);
1304 /* in the first pass we only look for unique simple
1305 equality tests, in the hope of avoiding having to look
1307 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
1308 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
1311 if (subtree
->operation
!= LDB_OP_EQUALITY
||
1312 !ltdb_index_unique(ldb
, ltdb
,
1313 subtree
->u
.equality
.attr
)) {
1317 ret
= ltdb_index_dn(module
, ltdb
, subtree
, list
);
1318 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1320 return LDB_ERR_NO_SUCH_OBJECT
;
1322 if (ret
== LDB_SUCCESS
) {
1323 /* a unique index match means we can
1324 * stop. Note that we don't care if we return
1325 * a few too many objects, due to later
1331 /* now do a full intersection */
1334 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
1335 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
1336 struct dn_list
*list2
;
1339 list2
= talloc_zero(list
, struct dn_list
);
1340 if (list2
== NULL
) {
1341 return ldb_module_oom(module
);
1344 ret
= ltdb_index_dn(module
, ltdb
, subtree
, list2
);
1346 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1351 return LDB_ERR_NO_SUCH_OBJECT
;
1354 if (ret
!= LDB_SUCCESS
) {
1355 /* this didn't adding anything */
1361 talloc_reparent(list2
, list
, list
->dn
);
1362 list
->dn
= list2
->dn
;
1363 list
->count
= list2
->count
;
1365 } else if (!list_intersect(ldb
, ltdb
,
1368 return LDB_ERR_OPERATIONS_ERROR
;
1371 if (list
->count
== 0) {
1373 return LDB_ERR_NO_SUCH_OBJECT
;
1376 if (list
->count
< 2) {
1377 /* it isn't worth loading the next part of the tree */
1383 /* none of the attributes were indexed */
1384 return LDB_ERR_OPERATIONS_ERROR
;
1391 return a list of matching objects using a one-level index
1393 static int ltdb_index_dn_attr(struct ldb_module
*module
,
1394 struct ltdb_private
*ltdb
,
1397 struct dn_list
*list
)
1399 struct ldb_context
*ldb
;
1404 ldb
= ldb_module_get_ctx(module
);
1406 /* work out the index key from the parent DN */
1407 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn
));
1408 if (val
.data
== NULL
) {
1409 const char *dn_str
= ldb_dn_get_linearized(dn
);
1410 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
1412 ": Failed to get casefold DN "
1415 return LDB_ERR_OPERATIONS_ERROR
;
1417 val
.length
= strlen((char *)val
.data
);
1418 key
= ltdb_index_key(ldb
, ltdb
, attr
, &val
, NULL
);
1421 return LDB_ERR_OPERATIONS_ERROR
;
1424 ret
= ltdb_dn_list_load(module
, ltdb
, key
, list
);
1426 if (ret
!= LDB_SUCCESS
) {
1430 if (list
->count
== 0) {
1431 return LDB_ERR_NO_SUCH_OBJECT
;
1438 return a list of matching objects using a one-level index
1440 static int ltdb_index_dn_one(struct ldb_module
*module
,
1441 struct ltdb_private
*ltdb
,
1442 struct ldb_dn
*parent_dn
,
1443 struct dn_list
*list
)
1445 /* Ensure we do not shortcut on intersection for this list */
1446 list
->strict
= true;
1447 return ltdb_index_dn_attr(module
, ltdb
,
1448 LTDB_IDXONE
, parent_dn
, list
);
1452 return a list of matching objects using the DN index
1454 static int ltdb_index_dn_base_dn(struct ldb_module
*module
,
1455 struct ltdb_private
*ltdb
,
1456 struct ldb_dn
*base_dn
,
1457 struct dn_list
*dn_list
)
1459 const struct ldb_val
*guid_val
= NULL
;
1460 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
1461 dn_list
->dn
= talloc_array(dn_list
, struct ldb_val
, 1);
1462 if (dn_list
->dn
== NULL
) {
1463 return ldb_module_oom(module
);
1465 dn_list
->dn
[0].data
= discard_const_p(unsigned char,
1466 ldb_dn_get_linearized(base_dn
));
1467 if (dn_list
->dn
[0].data
== NULL
) {
1468 return ldb_module_oom(module
);
1470 dn_list
->dn
[0].length
= strlen((char *)dn_list
->dn
[0].data
);
1476 if (ltdb
->cache
->GUID_index_dn_component
!= NULL
) {
1477 guid_val
= ldb_dn_get_extended_component(base_dn
,
1478 ltdb
->cache
->GUID_index_dn_component
);
1481 if (guid_val
!= NULL
) {
1482 dn_list
->dn
= talloc_array(dn_list
, struct ldb_val
, 1);
1483 if (dn_list
->dn
== NULL
) {
1484 return ldb_module_oom(module
);
1486 dn_list
->dn
[0].data
= guid_val
->data
;
1487 dn_list
->dn
[0].length
= guid_val
->length
;
1493 return ltdb_index_dn_attr(module
, ltdb
,
1494 LTDB_IDXDN
, base_dn
, dn_list
);
1498 return a list of dn's that might match a indexed search or
1499 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
1501 static int ltdb_index_dn(struct ldb_module
*module
,
1502 struct ltdb_private
*ltdb
,
1503 const struct ldb_parse_tree
*tree
,
1504 struct dn_list
*list
)
1506 int ret
= LDB_ERR_OPERATIONS_ERROR
;
1508 switch (tree
->operation
) {
1510 ret
= ltdb_index_dn_and(module
, ltdb
, tree
, list
);
1514 ret
= ltdb_index_dn_or(module
, ltdb
, tree
, list
);
1518 ret
= ltdb_index_dn_not(module
, ltdb
, tree
, list
);
1521 case LDB_OP_EQUALITY
:
1522 ret
= ltdb_index_dn_leaf(module
, ltdb
, tree
, list
);
1525 case LDB_OP_SUBSTRING
:
1526 case LDB_OP_GREATER
:
1528 case LDB_OP_PRESENT
:
1530 case LDB_OP_EXTENDED
:
1531 /* we can't index with fancy bitops yet */
1532 ret
= LDB_ERR_OPERATIONS_ERROR
;
1540 filter a candidate dn_list from an indexed search into a set of results
1541 extracting just the given attributes
1543 static int ltdb_index_filter(struct ltdb_private
*ltdb
,
1544 const struct dn_list
*dn_list
,
1545 struct ltdb_context
*ac
,
1546 uint32_t *match_count
)
1548 struct ldb_context
*ldb
= ldb_module_get_ctx(ac
->module
);
1549 struct ldb_message
*msg
;
1550 struct ldb_message
*filtered_msg
;
1552 unsigned int num_keys
= 0;
1553 uint8_t previous_guid_key
[LTDB_GUID_KEY_SIZE
] = {};
1554 TDB_DATA
*keys
= NULL
;
1557 * We have to allocate the key list (rather than just walk the
1558 * caller supplied list) as the callback could change the list
1559 * (by modifying an indexed attribute hosted in the in-memory
1562 keys
= talloc_array(ac
, TDB_DATA
, dn_list
->count
);
1564 return ldb_module_oom(ac
->module
);
1567 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1569 * We speculate that the keys will be GUID based and so
1570 * pre-fill in enough space for a GUID (avoiding a pile of
1571 * small allocations)
1573 struct guid_tdb_key
{
1574 uint8_t guid_key
[LTDB_GUID_KEY_SIZE
];
1575 } *key_values
= NULL
;
1577 key_values
= talloc_array(keys
,
1578 struct guid_tdb_key
,
1581 if (key_values
== NULL
) {
1583 return ldb_module_oom(ac
->module
);
1585 for (i
= 0; i
< dn_list
->count
; i
++) {
1586 keys
[i
].dptr
= key_values
[i
].guid_key
;
1587 keys
[i
].dsize
= sizeof(key_values
[i
].guid_key
);
1590 for (i
= 0; i
< dn_list
->count
; i
++) {
1591 keys
[i
].dptr
= NULL
;
1596 for (i
= 0; i
< dn_list
->count
; i
++) {
1599 ret
= ltdb_idx_to_key(ac
->module
,
1604 if (ret
!= LDB_SUCCESS
) {
1609 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1611 * If we are in GUID index mode, then the dn_list is
1612 * sorted. If we got a duplicate, forget about it, as
1613 * otherwise we would send the same entry back more
1616 * This is needed in the truncated DN case, or if a
1617 * duplicate was forced in via
1618 * LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK
1621 if (memcmp(previous_guid_key
,
1622 keys
[num_keys
].dptr
,
1623 sizeof(previous_guid_key
)) == 0) {
1627 memcpy(previous_guid_key
,
1628 keys
[num_keys
].dptr
,
1629 sizeof(previous_guid_key
));
1636 * Now that the list is a safe copy, send the callbacks
1638 for (i
= 0; i
< num_keys
; i
++) {
1641 msg
= ldb_msg_new(ac
);
1644 return LDB_ERR_OPERATIONS_ERROR
;
1647 ret
= ltdb_search_key(ac
->module
, ltdb
,
1649 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
|
1650 LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC
);
1651 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1653 * the record has disappeared? yes, this can
1654 * happen if the entry is deleted by something
1655 * operating in the callback (not another
1656 * process, as we have a read lock)
1662 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1663 /* an internal error */
1666 return LDB_ERR_OPERATIONS_ERROR
;
1669 /* We trust the index for SCOPE_ONELEVEL and SCOPE_BASE */
1670 if ((ac
->scope
== LDB_SCOPE_ONELEVEL
1671 && ltdb
->cache
->one_level_indexes
)
1672 || ac
->scope
== LDB_SCOPE_BASE
) {
1673 ret
= ldb_match_message(ldb
, msg
, ac
->tree
,
1674 ac
->scope
, &matched
);
1676 ret
= ldb_match_msg_error(ldb
, msg
,
1678 ac
->scope
, &matched
);
1681 if (ret
!= LDB_SUCCESS
) {
1691 /* filter the attributes that the user wants */
1692 ret
= ltdb_filter_attrs(ac
, msg
, ac
->attrs
, &filtered_msg
);
1698 return LDB_ERR_OPERATIONS_ERROR
;
1701 ret
= ldb_module_send_entry(ac
->req
, filtered_msg
, NULL
);
1702 if (ret
!= LDB_SUCCESS
) {
1703 /* Regardless of success or failure, the msg
1704 * is the callbacks responsiblity, and should
1705 * not be talloc_free()'ed */
1706 ac
->request_terminated
= true;
1721 static void ltdb_dn_list_sort(struct ltdb_private
*ltdb
,
1722 struct dn_list
*list
)
1724 if (list
->count
< 2) {
1728 /* We know the list is sorted when using the GUID index */
1729 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1733 TYPESAFE_QSORT(list
->dn
, list
->count
,
1734 ldb_val_equal_exact_for_qsort
);
1738 search the database with a LDAP-like expression using indexes
1739 returns -1 if an indexed search is not possible, in which
1740 case the caller should call ltdb_search_full()
1742 int ltdb_search_indexed(struct ltdb_context
*ac
, uint32_t *match_count
)
1744 struct ldb_context
*ldb
= ldb_module_get_ctx(ac
->module
);
1745 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(ac
->module
), struct ltdb_private
);
1746 struct dn_list
*dn_list
;
1748 enum ldb_scope index_scope
;
1750 /* see if indexing is enabled */
1751 if (!ltdb
->cache
->attribute_indexes
&&
1752 !ltdb
->cache
->one_level_indexes
&&
1753 ac
->scope
!= LDB_SCOPE_BASE
) {
1754 /* fallback to a full search */
1755 return LDB_ERR_OPERATIONS_ERROR
;
1758 dn_list
= talloc_zero(ac
, struct dn_list
);
1759 if (dn_list
== NULL
) {
1760 return ldb_module_oom(ac
->module
);
1764 * For the purposes of selecting the switch arm below, if we
1765 * don't have a one-level index then treat it like a subtree
1768 if (ac
->scope
== LDB_SCOPE_ONELEVEL
&&
1769 !ltdb
->cache
->one_level_indexes
) {
1770 index_scope
= LDB_SCOPE_SUBTREE
;
1772 index_scope
= ac
->scope
;
1775 switch (index_scope
) {
1776 case LDB_SCOPE_BASE
:
1778 * If we ever start to also load the index values for
1779 * the tree, we must ensure we strictly intersect with
1780 * this list, as we trust the BASE index
1782 ret
= ltdb_index_dn_base_dn(ac
->module
, ltdb
,
1784 if (ret
!= LDB_SUCCESS
) {
1785 talloc_free(dn_list
);
1790 case LDB_SCOPE_ONELEVEL
:
1792 * If we ever start to also load the index values for
1793 * the tree, we must ensure we strictly intersect with
1794 * this list, as we trust the ONELEVEL index
1796 ret
= ltdb_index_dn_one(ac
->module
, ltdb
, ac
->base
, dn_list
);
1797 if (ret
!= LDB_SUCCESS
) {
1798 talloc_free(dn_list
);
1803 * If we have too many matches, running the filter
1804 * tree over the SCOPE_ONELEVEL can be quite expensive
1805 * so we now check the filter tree index as well.
1807 * We only do this in the GUID index mode, which is
1808 * O(n*log(m)) otherwise the intersection below will
1809 * be too costly at O(n*m).
1811 * We don't set a heuristic for 'too many' but instead
1812 * do it always and rely on the index lookup being
1813 * fast enough in the small case.
1815 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1816 struct dn_list
*idx_one_tree_list
1817 = talloc_zero(ac
, struct dn_list
);
1818 if (idx_one_tree_list
== NULL
) {
1819 return ldb_module_oom(ac
->module
);
1822 if (!ltdb
->cache
->attribute_indexes
) {
1823 talloc_free(idx_one_tree_list
);
1824 talloc_free(dn_list
);
1825 return LDB_ERR_OPERATIONS_ERROR
;
1828 * Here we load the index for the tree.
1830 * We only care if this is successful, if the
1831 * index can't trim the result list down then
1832 * the ONELEVEL index is still good enough.
1834 ret
= ltdb_index_dn(ac
->module
, ltdb
, ac
->tree
,
1836 if (ret
== LDB_SUCCESS
) {
1837 if (!list_intersect(ldb
, ltdb
,
1839 idx_one_tree_list
)) {
1840 talloc_free(idx_one_tree_list
);
1841 talloc_free(dn_list
);
1842 return LDB_ERR_OPERATIONS_ERROR
;
1848 case LDB_SCOPE_SUBTREE
:
1849 case LDB_SCOPE_DEFAULT
:
1850 if (!ltdb
->cache
->attribute_indexes
) {
1851 talloc_free(dn_list
);
1852 return LDB_ERR_OPERATIONS_ERROR
;
1855 * Here we load the index for the tree. We have no
1856 * index for the subtree.
1858 ret
= ltdb_index_dn(ac
->module
, ltdb
, ac
->tree
, dn_list
);
1859 if (ret
!= LDB_SUCCESS
) {
1860 talloc_free(dn_list
);
1866 ret
= ltdb_index_filter(ltdb
, dn_list
, ac
, match_count
);
1867 talloc_free(dn_list
);
1872 * @brief Add a DN in the index list of a given attribute name/value pair
1874 * This function will add the DN in the index list for the index for
1875 * the given attribute name and value.
1877 * @param[in] module A ldb_module structure
1879 * @param[in] dn The string representation of the DN as it
1880 * will be stored in the index entry
1882 * @param[in] el A ldb_message_element array, one of the entry
1883 * referred by the v_idx is the attribute name and
1884 * value pair which will be used to construct the
1887 * @param[in] v_idx The index of element in the el array to use
1889 * @return An ldb error code
1891 static int ltdb_index_add1(struct ldb_module
*module
,
1892 struct ltdb_private
*ltdb
,
1893 const struct ldb_message
*msg
,
1894 struct ldb_message_element
*el
, int v_idx
)
1896 struct ldb_context
*ldb
;
1897 struct ldb_dn
*dn_key
;
1899 const struct ldb_schema_attribute
*a
;
1900 struct dn_list
*list
;
1903 ldb
= ldb_module_get_ctx(module
);
1905 list
= talloc_zero(module
, struct dn_list
);
1907 return LDB_ERR_OPERATIONS_ERROR
;
1910 dn_key
= ltdb_index_key(ldb
, ltdb
,
1911 el
->name
, &el
->values
[v_idx
], &a
);
1914 return LDB_ERR_OPERATIONS_ERROR
;
1916 talloc_steal(list
, dn_key
);
1918 ret
= ltdb_dn_list_load(module
, ltdb
, dn_key
, list
);
1919 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1925 * Check for duplicates in the @IDXDN DN -> GUID record
1927 * This is very normal, it just means a duplicate DN creation
1928 * was attempted, so don't set the error string or print scary
1931 if (list
->count
> 0 &&
1932 ldb_attr_cmp(el
->name
, LTDB_IDXDN
) == 0) {
1934 return LDB_ERR_CONSTRAINT_VIOLATION
;
1938 * Check for duplicates in unique indexes
1940 if (list
->count
> 0 &&
1942 && (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
||
1943 (el
->flags
& LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX
))))) {
1945 * We do not want to print info about a possibly
1946 * confidential DN that the conflict was with in the
1947 * user-visible error string
1950 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
1951 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
1953 ": unique index violation on %s in %s, "
1954 "conficts with %*.*s in %s",
1955 el
->name
, ldb_dn_get_linearized(msg
->dn
),
1956 (int)list
->dn
[0].length
,
1957 (int)list
->dn
[0].length
,
1959 ldb_dn_get_linearized(dn_key
));
1961 /* This can't fail, gives a default at worst */
1962 const struct ldb_schema_attribute
*attr
1963 = ldb_schema_attribute_by_name(
1965 ltdb
->cache
->GUID_index_attribute
);
1967 ret
= attr
->syntax
->ldif_write_fn(ldb
, list
,
1969 if (ret
== LDB_SUCCESS
) {
1970 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
1972 ": unique index violation on %s in "
1973 "%s, conficts with %s %*.*s in %s",
1975 ldb_dn_get_linearized(msg
->dn
),
1976 ltdb
->cache
->GUID_index_attribute
,
1980 ldb_dn_get_linearized(dn_key
));
1983 ldb_asprintf_errstring(ldb
,
1984 __location__
": unique index violation "
1987 ldb_dn_get_linearized(msg
->dn
));
1989 return LDB_ERR_CONSTRAINT_VIOLATION
;
1992 /* overallocate the list a bit, to reduce the number of
1993 * realloc trigered copies */
1994 alloc_len
= ((list
->count
+1)+7) & ~7;
1995 list
->dn
= talloc_realloc(list
, list
->dn
, struct ldb_val
, alloc_len
);
1996 if (list
->dn
== NULL
) {
1998 return LDB_ERR_OPERATIONS_ERROR
;
2001 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
2002 const char *dn_str
= ldb_dn_get_linearized(msg
->dn
);
2003 list
->dn
[list
->count
].data
2004 = (uint8_t *)talloc_strdup(list
->dn
, dn_str
);
2005 if (list
->dn
[list
->count
].data
== NULL
) {
2007 return LDB_ERR_OPERATIONS_ERROR
;
2009 list
->dn
[list
->count
].length
= strlen(dn_str
);
2011 const struct ldb_val
*key_val
;
2012 struct ldb_val
*exact
= NULL
, *next
= NULL
;
2013 key_val
= ldb_msg_find_ldb_val(msg
,
2014 ltdb
->cache
->GUID_index_attribute
);
2015 if (key_val
== NULL
) {
2017 return ldb_module_operr(module
);
2020 if (key_val
->length
!= LTDB_GUID_SIZE
) {
2022 return ldb_module_operr(module
);
2025 BINARY_ARRAY_SEARCH_GTE(list
->dn
, list
->count
,
2026 *key_val
, ldb_val_equal_exact_ordered
,
2030 * Give a warning rather than fail, this could be a
2031 * duplicate value in the record allowed by a caller
2032 * forcing in the value with
2033 * LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK
2035 if (exact
!= NULL
) {
2036 /* This can't fail, gives a default at worst */
2037 const struct ldb_schema_attribute
*attr
2038 = ldb_schema_attribute_by_name(
2040 ltdb
->cache
->GUID_index_attribute
);
2042 ret
= attr
->syntax
->ldif_write_fn(ldb
, list
,
2044 if (ret
== LDB_SUCCESS
) {
2045 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2047 ": duplicate attribute value in %s "
2049 "duplicate of %s %*.*s in %s",
2050 ldb_dn_get_linearized(msg
->dn
),
2052 ltdb
->cache
->GUID_index_attribute
,
2056 ldb_dn_get_linearized(dn_key
));
2061 next
= &list
->dn
[list
->count
];
2063 memmove(&next
[1], next
,
2064 sizeof(*next
) * (list
->count
- (next
- list
->dn
)));
2066 *next
= ldb_val_dup(list
->dn
, key_val
);
2067 if (next
->data
== NULL
) {
2069 return ldb_module_operr(module
);
2074 ret
= ltdb_dn_list_store(module
, dn_key
, list
);
2082 add index entries for one elements in a message
2084 static int ltdb_index_add_el(struct ldb_module
*module
,
2085 struct ltdb_private
*ltdb
,
2086 const struct ldb_message
*msg
,
2087 struct ldb_message_element
*el
)
2090 for (i
= 0; i
< el
->num_values
; i
++) {
2091 int ret
= ltdb_index_add1(module
, ltdb
,
2093 if (ret
!= LDB_SUCCESS
) {
2102 add index entries for all elements in a message
2104 static int ltdb_index_add_all(struct ldb_module
*module
,
2105 struct ltdb_private
*ltdb
,
2106 const struct ldb_message
*msg
)
2108 struct ldb_message_element
*elements
= msg
->elements
;
2113 if (ldb_dn_is_special(msg
->dn
)) {
2117 dn_str
= ldb_dn_get_linearized(msg
->dn
);
2118 if (dn_str
== NULL
) {
2119 return LDB_ERR_OPERATIONS_ERROR
;
2122 ret
= ltdb_write_index_dn_guid(module
, msg
, 1);
2123 if (ret
!= LDB_SUCCESS
) {
2127 if (!ltdb
->cache
->attribute_indexes
) {
2128 /* no indexed fields */
2132 for (i
= 0; i
< msg
->num_elements
; i
++) {
2133 if (!ltdb_is_indexed(module
, ltdb
, elements
[i
].name
)) {
2136 ret
= ltdb_index_add_el(module
, ltdb
,
2138 if (ret
!= LDB_SUCCESS
) {
2139 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2140 ldb_asprintf_errstring(ldb
,
2141 __location__
": Failed to re-index %s in %s - %s",
2142 elements
[i
].name
, dn_str
,
2143 ldb_errstring(ldb
));
2153 insert a DN index for a message
2155 static int ltdb_modify_index_dn(struct ldb_module
*module
,
2156 struct ltdb_private
*ltdb
,
2157 const struct ldb_message
*msg
,
2159 const char *index
, int add
)
2161 struct ldb_message_element el
;
2165 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn
));
2166 if (val
.data
== NULL
) {
2167 const char *dn_str
= ldb_dn_get_linearized(dn
);
2168 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
2170 ": Failed to modify %s "
2171 "against %s in %s: failed "
2172 "to get casefold DN",
2174 ltdb
->cache
->GUID_index_attribute
,
2176 return LDB_ERR_OPERATIONS_ERROR
;
2179 val
.length
= strlen((char *)val
.data
);
2185 ret
= ltdb_index_add1(module
, ltdb
, msg
, &el
, 0);
2186 } else { /* delete */
2187 ret
= ltdb_index_del_value(module
, ltdb
, msg
, &el
, 0);
2190 if (ret
!= LDB_SUCCESS
) {
2191 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2192 const char *dn_str
= ldb_dn_get_linearized(dn
);
2193 ldb_asprintf_errstring(ldb
,
2195 ": Failed to modify %s "
2196 "against %s in %s - %s",
2198 ltdb
->cache
->GUID_index_attribute
,
2199 dn_str
, ldb_errstring(ldb
));
2206 insert a one level index for a message
2208 static int ltdb_index_onelevel(struct ldb_module
*module
,
2209 const struct ldb_message
*msg
, int add
)
2211 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
),
2212 struct ltdb_private
);
2216 /* We index for ONE Level only if requested */
2217 if (!ltdb
->cache
->one_level_indexes
) {
2221 pdn
= ldb_dn_get_parent(module
, msg
->dn
);
2223 return LDB_ERR_OPERATIONS_ERROR
;
2225 ret
= ltdb_modify_index_dn(module
, ltdb
,
2226 msg
, pdn
, LTDB_IDXONE
, add
);
2234 insert a one level index for a message
2236 static int ltdb_write_index_dn_guid(struct ldb_module
*module
,
2237 const struct ldb_message
*msg
,
2241 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
),
2242 struct ltdb_private
);
2244 /* We index for DN only if using a GUID index */
2245 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
2249 ret
= ltdb_modify_index_dn(module
, ltdb
, msg
, msg
->dn
,
2252 if (ret
== LDB_ERR_CONSTRAINT_VIOLATION
) {
2253 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
2254 "Entry %s already exists",
2255 ldb_dn_get_linearized(msg
->dn
));
2256 ret
= LDB_ERR_ENTRY_ALREADY_EXISTS
;
2262 add the index entries for a new element in a record
2263 The caller guarantees that these element values are not yet indexed
2265 int ltdb_index_add_element(struct ldb_module
*module
,
2266 struct ltdb_private
*ltdb
,
2267 const struct ldb_message
*msg
,
2268 struct ldb_message_element
*el
)
2270 if (ldb_dn_is_special(msg
->dn
)) {
2273 if (!ltdb_is_indexed(module
, ltdb
, el
->name
)) {
2276 return ltdb_index_add_el(module
, ltdb
, msg
, el
);
2280 add the index entries for a new record
2282 int ltdb_index_add_new(struct ldb_module
*module
,
2283 struct ltdb_private
*ltdb
,
2284 const struct ldb_message
*msg
)
2288 if (ldb_dn_is_special(msg
->dn
)) {
2292 ret
= ltdb_index_add_all(module
, ltdb
, msg
);
2293 if (ret
!= LDB_SUCCESS
) {
2295 * Because we can't trust the caller to be doing
2296 * transactions properly, clean up any index for this
2297 * entry rather than relying on a transaction
2301 ltdb_index_delete(module
, msg
);
2305 ret
= ltdb_index_onelevel(module
, msg
, 1);
2306 if (ret
!= LDB_SUCCESS
) {
2308 * Because we can't trust the caller to be doing
2309 * transactions properly, clean up any index for this
2310 * entry rather than relying on a transaction
2313 ltdb_index_delete(module
, msg
);
2321 delete an index entry for one message element
2323 int ltdb_index_del_value(struct ldb_module
*module
,
2324 struct ltdb_private
*ltdb
,
2325 const struct ldb_message
*msg
,
2326 struct ldb_message_element
*el
, unsigned int v_idx
)
2328 struct ldb_context
*ldb
;
2329 struct ldb_dn
*dn_key
;
2333 struct dn_list
*list
;
2334 struct ldb_dn
*dn
= msg
->dn
;
2336 ldb
= ldb_module_get_ctx(module
);
2338 dn_str
= ldb_dn_get_linearized(dn
);
2339 if (dn_str
== NULL
) {
2340 return LDB_ERR_OPERATIONS_ERROR
;
2343 if (dn_str
[0] == '@') {
2347 dn_key
= ltdb_index_key(ldb
, ltdb
,
2348 el
->name
, &el
->values
[v_idx
], NULL
);
2350 return LDB_ERR_OPERATIONS_ERROR
;
2353 list
= talloc_zero(dn_key
, struct dn_list
);
2355 talloc_free(dn_key
);
2356 return LDB_ERR_OPERATIONS_ERROR
;
2359 ret
= ltdb_dn_list_load(module
, ltdb
, dn_key
, list
);
2360 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
2361 /* it wasn't indexed. Did we have an earlier error? If we did then
2363 talloc_free(dn_key
);
2367 if (ret
!= LDB_SUCCESS
) {
2368 talloc_free(dn_key
);
2372 i
= ltdb_dn_list_find_msg(ltdb
, list
, msg
);
2374 /* nothing to delete */
2375 talloc_free(dn_key
);
2379 j
= (unsigned int) i
;
2380 if (j
!= list
->count
- 1) {
2381 memmove(&list
->dn
[j
], &list
->dn
[j
+1], sizeof(list
->dn
[0])*(list
->count
- (j
+1)));
2384 if (list
->count
== 0) {
2385 talloc_free(list
->dn
);
2388 list
->dn
= talloc_realloc(list
, list
->dn
, struct ldb_val
, list
->count
);
2391 ret
= ltdb_dn_list_store(module
, dn_key
, list
);
2393 talloc_free(dn_key
);
2399 delete the index entries for a element
2400 return -1 on failure
2402 int ltdb_index_del_element(struct ldb_module
*module
,
2403 struct ltdb_private
*ltdb
,
2404 const struct ldb_message
*msg
,
2405 struct ldb_message_element
*el
)
2411 if (!ltdb
->cache
->attribute_indexes
) {
2412 /* no indexed fields */
2416 dn_str
= ldb_dn_get_linearized(msg
->dn
);
2417 if (dn_str
== NULL
) {
2418 return LDB_ERR_OPERATIONS_ERROR
;
2421 if (dn_str
[0] == '@') {
2425 if (!ltdb_is_indexed(module
, ltdb
, el
->name
)) {
2428 for (i
= 0; i
< el
->num_values
; i
++) {
2429 ret
= ltdb_index_del_value(module
, ltdb
, msg
, el
, i
);
2430 if (ret
!= LDB_SUCCESS
) {
2439 delete the index entries for a record
2440 return -1 on failure
2442 int ltdb_index_delete(struct ldb_module
*module
, const struct ldb_message
*msg
)
2444 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
2448 if (ldb_dn_is_special(msg
->dn
)) {
2452 ret
= ltdb_index_onelevel(module
, msg
, 0);
2453 if (ret
!= LDB_SUCCESS
) {
2457 ret
= ltdb_write_index_dn_guid(module
, msg
, 0);
2458 if (ret
!= LDB_SUCCESS
) {
2462 if (!ltdb
->cache
->attribute_indexes
) {
2463 /* no indexed fields */
2467 for (i
= 0; i
< msg
->num_elements
; i
++) {
2468 ret
= ltdb_index_del_element(module
, ltdb
,
2469 msg
, &msg
->elements
[i
]);
2470 if (ret
!= LDB_SUCCESS
) {
2480 traversal function that deletes all @INDEX records in the in-memory
2483 This does not touch the actual DB, that is done at transaction
2484 commit, which in turn greatly reduces DB churn as we will likely
2485 be able to do a direct update into the old record.
2487 static int delete_index(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
2489 struct ldb_module
*module
= state
;
2490 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
2491 const char *dnstr
= "DN=" LTDB_INDEX
":";
2492 struct dn_list list
;
2497 if (strncmp((char *)key
.dptr
, dnstr
, strlen(dnstr
)) != 0) {
2500 /* we need to put a empty list in the internal tdb for this
2505 /* the offset of 3 is to remove the DN= prefix. */
2506 v
.data
= key
.dptr
+ 3;
2507 v
.length
= strnlen((char *)key
.dptr
, key
.dsize
) - 3;
2509 dn
= ldb_dn_from_ldb_val(ltdb
, ldb_module_get_ctx(module
), &v
);
2512 * This does not actually touch the DB quite yet, just
2513 * the in-memory index cache
2515 ret
= ltdb_dn_list_store(module
, dn
, &list
);
2516 if (ret
!= LDB_SUCCESS
) {
2517 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
2518 "Unable to store null index for %s\n",
2519 ldb_dn_get_linearized(dn
));
2527 struct ltdb_reindex_context
{
2528 struct ldb_module
*module
;
2534 traversal function that adds @INDEX records during a re index
2536 static int re_key(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
2538 struct ldb_context
*ldb
;
2539 struct ltdb_reindex_context
*ctx
= (struct ltdb_reindex_context
*)state
;
2540 struct ldb_module
*module
= ctx
->module
;
2541 struct ldb_message
*msg
;
2542 unsigned int nb_elements_in_db
;
2543 const struct ldb_val val
= {
2545 .length
= data
.dsize
,
2551 ldb
= ldb_module_get_ctx(module
);
2553 if (key
.dsize
> 4 &&
2554 memcmp(key
.dptr
, "DN=@", 4) == 0) {
2558 is_record
= ltdb_key_is_record(key
);
2559 if (is_record
== false) {
2563 msg
= ldb_msg_new(module
);
2568 ret
= ldb_unpack_data_only_attr_list_flags(ldb
, &val
,
2571 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
,
2572 &nb_elements_in_db
);
2574 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid data for index %s\n",
2575 ldb_dn_get_linearized(msg
->dn
));
2581 if (msg
->dn
== NULL
) {
2582 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2583 "Refusing to re-index as GUID "
2584 "key %*.*s with no DN\n",
2585 (int)key
.dsize
, (int)key
.dsize
,
2591 /* check if the DN key has changed, perhaps due to the case
2592 insensitivity of an element changing, or a change from DN
2594 key2
= ltdb_key_msg(module
, msg
, msg
);
2595 if (key2
.dptr
== NULL
) {
2596 /* probably a corrupt record ... darn */
2597 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid DN in re_index: %s",
2598 ldb_dn_get_linearized(msg
->dn
));
2602 if (key
.dsize
!= key2
.dsize
||
2603 (memcmp(key
.dptr
, key2
.dptr
, key
.dsize
) != 0)) {
2605 tdb_ret
= tdb_delete(tdb
, key
);
2607 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2608 "Failed to delete %*.*s "
2609 "for rekey as %*.*s: %s",
2610 (int)key
.dsize
, (int)key
.dsize
,
2611 (const char *)key
.dptr
,
2612 (int)key2
.dsize
, (int)key2
.dsize
,
2613 (const char *)key
.dptr
,
2615 ctx
->error
= ltdb_err_map(tdb_error(tdb
));
2618 tdb_ret
= tdb_store(tdb
, key2
, data
, 0);
2620 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2621 "Failed to rekey %*.*s as %*.*s: %s",
2622 (int)key
.dsize
, (int)key
.dsize
,
2623 (const char *)key
.dptr
,
2624 (int)key2
.dsize
, (int)key2
.dsize
,
2625 (const char *)key
.dptr
,
2627 ctx
->error
= ltdb_err_map(tdb_error(tdb
));
2631 talloc_free(key2
.dptr
);
2636 if (ctx
->count
% 10000 == 0) {
2637 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2638 "Reindexing: re-keyed %u records so far",
2646 traversal function that adds @INDEX records during a re index
2648 static int re_index(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
2650 struct ldb_context
*ldb
;
2651 struct ltdb_reindex_context
*ctx
= (struct ltdb_reindex_context
*)state
;
2652 struct ldb_module
*module
= ctx
->module
;
2653 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
),
2654 struct ltdb_private
);
2655 struct ldb_message
*msg
;
2656 unsigned int nb_elements_in_db
;
2657 const struct ldb_val val
= {
2659 .length
= data
.dsize
,
2664 ldb
= ldb_module_get_ctx(module
);
2666 if (key
.dsize
> 4 &&
2667 memcmp(key
.dptr
, "DN=@", 4) == 0) {
2671 is_record
= ltdb_key_is_record(key
);
2672 if (is_record
== false) {
2676 msg
= ldb_msg_new(module
);
2681 ret
= ldb_unpack_data_only_attr_list_flags(ldb
, &val
,
2684 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
,
2685 &nb_elements_in_db
);
2687 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid data for index %s\n",
2688 ldb_dn_get_linearized(msg
->dn
));
2694 if (msg
->dn
== NULL
) {
2695 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2696 "Refusing to re-index as GUID "
2697 "key %*.*s with no DN\n",
2698 (int)key
.dsize
, (int)key
.dsize
,
2704 ret
= ltdb_index_onelevel(module
, msg
, 1);
2705 if (ret
!= LDB_SUCCESS
) {
2706 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2707 "Adding special ONE LEVEL index failed (%s)!",
2708 ldb_dn_get_linearized(msg
->dn
));
2713 ret
= ltdb_index_add_all(module
, ltdb
, msg
);
2715 if (ret
!= LDB_SUCCESS
) {
2724 if (ctx
->count
% 10000 == 0) {
2725 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2726 "Reindexing: re-indexed %u records so far",
2734 force a complete reindex of the database
2736 int ltdb_reindex(struct ldb_module
*module
)
2738 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
2740 struct ltdb_reindex_context ctx
;
2743 * Only triggered after a modification, but make clear we do
2744 * not re-index a read-only DB
2746 if (ltdb
->read_only
) {
2747 return LDB_ERR_UNWILLING_TO_PERFORM
;
2750 if (ltdb_cache_reload(module
) != 0) {
2751 return LDB_ERR_OPERATIONS_ERROR
;
2755 * Ensure we read (and so remove) the entries from the real
2756 * DB, no values stored so far are any use as we want to do a
2759 ltdb_index_transaction_cancel(module
);
2761 ret
= ltdb_index_transaction_start(module
);
2762 if (ret
!= LDB_SUCCESS
) {
2766 /* first traverse the database deleting any @INDEX records by
2767 * putting NULL entries in the in-memory tdb
2769 ret
= tdb_traverse(ltdb
->tdb
, delete_index
, module
);
2771 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2772 ldb_asprintf_errstring(ldb
, "index deletion traverse failed: %s",
2773 ldb_errstring(ldb
));
2774 return LDB_ERR_OPERATIONS_ERROR
;
2777 ctx
.module
= module
;
2781 /* now traverse adding any indexes for normal LDB records */
2782 ret
= tdb_traverse(ltdb
->tdb
, re_key
, &ctx
);
2784 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2785 ldb_asprintf_errstring(ldb
, "key correction traverse failed: %s",
2786 ldb_errstring(ldb
));
2787 return LDB_ERR_OPERATIONS_ERROR
;
2790 if (ctx
.error
!= LDB_SUCCESS
) {
2791 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2792 ldb_asprintf_errstring(ldb
, "reindexing failed: %s", ldb_errstring(ldb
));
2799 /* now traverse adding any indexes for normal LDB records */
2800 ret
= tdb_traverse(ltdb
->tdb
, re_index
, &ctx
);
2802 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2803 ldb_asprintf_errstring(ldb
, "reindexing traverse failed: %s",
2804 ldb_errstring(ldb
));
2805 return LDB_ERR_OPERATIONS_ERROR
;
2808 if (ctx
.error
!= LDB_SUCCESS
) {
2809 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2810 ldb_asprintf_errstring(ldb
, "reindexing failed: %s", ldb_errstring(ldb
));
2814 if (ctx
.count
> 10000) {
2815 ldb_debug(ldb_module_get_ctx(module
),
2816 LDB_DEBUG_WARNING
, "Reindexing: re_index successful on %s, "
2817 "final index write-out will be in transaction commit",
2818 tdb_name(ltdb
->tdb
));