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 enum key_truncation
{
173 static int ltdb_write_index_dn_guid(struct ldb_module
*module
,
174 const struct ldb_message
*msg
,
176 static int ltdb_index_dn_base_dn(struct ldb_module
*module
,
177 struct ltdb_private
*ltdb
,
178 struct ldb_dn
*base_dn
,
179 struct dn_list
*dn_list
,
180 enum key_truncation
*truncation
);
182 static void ltdb_dn_list_sort(struct ltdb_private
*ltdb
,
183 struct dn_list
*list
);
185 /* we put a @IDXVERSION attribute on index entries. This
186 allows us to tell if it was written by an older version
188 #define LTDB_INDEXING_VERSION 2
190 #define LTDB_GUID_INDEXING_VERSION 3
192 static unsigned ltdb_max_key_length(struct ltdb_private
*ltdb
) {
193 if (ltdb
->max_key_length
== 0){
196 return ltdb
->max_key_length
;
199 /* enable the idxptr mode when transactions start */
200 int ltdb_index_transaction_start(struct ldb_module
*module
)
202 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
203 ltdb
->idxptr
= talloc_zero(ltdb
, struct ltdb_idxptr
);
204 if (ltdb
->idxptr
== NULL
) {
205 return ldb_oom(ldb_module_get_ctx(module
));
212 see if two ldb_val structures contain exactly the same data
213 return -1 or 1 for a mismatch, 0 for match
215 static int ldb_val_equal_exact_for_qsort(const struct ldb_val
*v1
,
216 const struct ldb_val
*v2
)
218 if (v1
->length
> v2
->length
) {
221 if (v1
->length
< v2
->length
) {
224 return memcmp(v1
->data
, v2
->data
, v1
->length
);
228 see if two ldb_val structures contain exactly the same data
229 return -1 or 1 for a mismatch, 0 for match
231 static int ldb_val_equal_exact_ordered(const struct ldb_val v1
,
232 const struct ldb_val
*v2
)
234 if (v1
.length
> v2
->length
) {
237 if (v1
.length
< v2
->length
) {
240 return memcmp(v1
.data
, v2
->data
, v1
.length
);
245 find a entry in a dn_list, using a ldb_val. Uses a case sensitive
246 binary-safe comparison for the 'dn' returns -1 if not found
248 This is therefore safe when the value is a GUID in the future
250 static int ltdb_dn_list_find_val(struct ltdb_private
*ltdb
,
251 const struct dn_list
*list
,
252 const struct ldb_val
*v
)
255 struct ldb_val
*exact
= NULL
, *next
= NULL
;
257 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
258 for (i
=0; i
<list
->count
; i
++) {
259 if (ldb_val_equal_exact(&list
->dn
[i
], v
) == 1) {
266 BINARY_ARRAY_SEARCH_GTE(list
->dn
, list
->count
,
267 *v
, ldb_val_equal_exact_ordered
,
272 /* Not required, but keeps the compiler quiet */
277 i
= exact
- list
->dn
;
282 find a entry in a dn_list. Uses a case sensitive comparison with the dn
283 returns -1 if not found
285 static int ltdb_dn_list_find_msg(struct ltdb_private
*ltdb
,
286 struct dn_list
*list
,
287 const struct ldb_message
*msg
)
290 const struct ldb_val
*key_val
;
291 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
292 const char *dn_str
= ldb_dn_get_linearized(msg
->dn
);
293 v
.data
= discard_const_p(unsigned char, dn_str
);
294 v
.length
= strlen(dn_str
);
296 key_val
= ldb_msg_find_ldb_val(msg
,
297 ltdb
->cache
->GUID_index_attribute
);
298 if (key_val
== NULL
) {
303 return ltdb_dn_list_find_val(ltdb
, list
, &v
);
307 this is effectively a cast function, but with lots of paranoia
308 checks and also copes with CPUs that are fussy about pointer
311 static struct dn_list
*ltdb_index_idxptr(struct ldb_module
*module
, TDB_DATA rec
, bool check_parent
)
313 struct dn_list
*list
;
314 if (rec
.dsize
!= sizeof(void *)) {
315 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
316 "Bad data size for idxptr %u", (unsigned)rec
.dsize
);
319 /* note that we can't just use a cast here, as rec.dptr may
320 not be aligned sufficiently for a pointer. A cast would cause
321 platforms like some ARM CPUs to crash */
322 memcpy(&list
, rec
.dptr
, sizeof(void *));
323 list
= talloc_get_type(list
, struct dn_list
);
325 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
326 "Bad type '%s' for idxptr",
327 talloc_get_name(list
));
330 if (check_parent
&& list
->dn
&& talloc_parent(list
->dn
) != list
) {
331 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
332 "Bad parent '%s' for idxptr",
333 talloc_get_name(talloc_parent(list
->dn
)));
340 return the @IDX list in an index entry for a dn as a
343 static int ltdb_dn_list_load(struct ldb_module
*module
,
344 struct ltdb_private
*ltdb
,
345 struct ldb_dn
*dn
, struct dn_list
*list
)
347 struct ldb_message
*msg
;
349 struct ldb_message_element
*el
;
351 struct dn_list
*list2
;
357 /* see if we have any in-memory index entries */
358 if (ltdb
->idxptr
== NULL
||
359 ltdb
->idxptr
->itdb
== NULL
) {
363 key
.dptr
= discard_const_p(unsigned char, ldb_dn_get_linearized(dn
));
364 key
.dsize
= strlen((char *)key
.dptr
);
366 rec
= tdb_fetch(ltdb
->idxptr
->itdb
, key
);
367 if (rec
.dptr
== NULL
) {
371 /* we've found an in-memory index entry */
372 list2
= ltdb_index_idxptr(module
, rec
, true);
375 return LDB_ERR_OPERATIONS_ERROR
;
383 msg
= ldb_msg_new(list
);
385 return LDB_ERR_OPERATIONS_ERROR
;
388 ret
= ltdb_search_dn1(module
, dn
, msg
,
389 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
390 |LDB_UNPACK_DATA_FLAG_NO_DN
);
391 if (ret
!= LDB_SUCCESS
) {
396 el
= ldb_msg_find_element(msg
, LTDB_IDX
);
402 version
= ldb_msg_find_attr_as_int(msg
, LTDB_IDXVERSION
, 0);
405 * we avoid copying the strings by stealing the list. We have
406 * to steal msg onto el->values (which looks odd) because we
407 * asked for the memory to be allocated on msg, not on each
408 * value with LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC above
410 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
411 /* check indexing version number */
412 if (version
!= LTDB_INDEXING_VERSION
) {
413 ldb_debug_set(ldb_module_get_ctx(module
),
415 "Wrong DN index version %d "
416 "expected %d for %s",
417 version
, LTDB_INDEXING_VERSION
,
418 ldb_dn_get_linearized(dn
));
420 return LDB_ERR_OPERATIONS_ERROR
;
423 talloc_steal(el
->values
, msg
);
424 list
->dn
= talloc_steal(list
, el
->values
);
425 list
->count
= el
->num_values
;
428 if (version
!= LTDB_GUID_INDEXING_VERSION
) {
429 /* This is quite likely during the DB startup
430 on first upgrade to using a GUID index */
431 ldb_debug_set(ldb_module_get_ctx(module
),
433 "Wrong GUID index version %d "
434 "expected %d for %s",
435 version
, LTDB_GUID_INDEXING_VERSION
,
436 ldb_dn_get_linearized(dn
));
438 return LDB_ERR_OPERATIONS_ERROR
;
441 if (el
->num_values
== 0) {
443 return LDB_ERR_OPERATIONS_ERROR
;
446 if ((el
->values
[0].length
% LTDB_GUID_SIZE
) != 0) {
448 return LDB_ERR_OPERATIONS_ERROR
;
451 list
->count
= el
->values
[0].length
/ LTDB_GUID_SIZE
;
452 list
->dn
= talloc_array(list
, struct ldb_val
, list
->count
);
453 if (list
->dn
== NULL
) {
455 return LDB_ERR_OPERATIONS_ERROR
;
459 * The actual data is on msg, due to
460 * LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
462 talloc_steal(list
->dn
, msg
);
463 for (i
= 0; i
< list
->count
; i
++) {
465 = &el
->values
[0].data
[i
* LTDB_GUID_SIZE
];
466 list
->dn
[i
].length
= LTDB_GUID_SIZE
;
470 /* We don't need msg->elements any more */
471 talloc_free(msg
->elements
);
475 int ltdb_key_dn_from_idx(struct ldb_module
*module
,
476 struct ltdb_private
*ltdb
,
481 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
484 enum key_truncation truncation
= KEY_NOT_TRUNCATED
;
485 struct dn_list
*list
= talloc(mem_ctx
, struct dn_list
);
488 return LDB_ERR_OPERATIONS_ERROR
;
492 ret
= ltdb_index_dn_base_dn(module
, ltdb
, dn
, list
, &truncation
);
493 if (ret
!= LDB_SUCCESS
) {
498 if (list
->count
== 0) {
500 return LDB_ERR_NO_SUCH_OBJECT
;
503 if (list
->count
> 1 && truncation
== KEY_NOT_TRUNCATED
) {
504 const char *dn_str
= ldb_dn_get_linearized(dn
);
505 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
507 ": Failed to read DN index "
508 "against %s for %s: too many "
510 ltdb
->cache
->GUID_index_attribute
,
511 dn_str
, list
->count
);
513 return LDB_ERR_CONSTRAINT_VIOLATION
;
516 if (list
->count
> 0 && truncation
== KEY_TRUNCATED
) {
518 * DN key has been truncated, need to inspect the actual
519 * records to locate the actual DN
523 for (i
=0; i
< list
->count
; i
++) {
524 uint8_t guid_key
[LTDB_GUID_KEY_SIZE
];
527 .dsize
= sizeof(guid_key
)
529 const int flags
= LDB_UNPACK_DATA_FLAG_NO_ATTRS
;
530 struct ldb_message
*rec
= ldb_msg_new(ldb
);
533 return LDB_ERR_OPERATIONS_ERROR
;
536 ret
= ltdb_idx_to_key(module
, ltdb
,
539 if (ret
!= LDB_SUCCESS
) {
545 ret
= ltdb_search_key(module
, ltdb
, key
,
547 if (key
.dptr
!= guid_key
) {
548 TALLOC_FREE(key
.dptr
);
550 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
552 * the record has disappeared?
553 * yes, this can happen
559 if (ret
!= LDB_SUCCESS
) {
560 /* an internal error */
563 return LDB_ERR_OPERATIONS_ERROR
;
567 * We found the actual DN that we wanted from in the
568 * multiple values that matched the index
569 * (due to truncation), so return that.
572 if (ldb_dn_compare(dn
, rec
->dn
) == 0) {
580 * We matched the index but the actual DN we wanted
585 return LDB_ERR_NO_SUCH_OBJECT
;
589 /* The tdb_key memory is allocated by the caller */
590 ret
= ltdb_guid_to_key(module
, ltdb
,
591 &list
->dn
[index
], tdb_key
);
594 if (ret
!= LDB_SUCCESS
) {
595 return LDB_ERR_OPERATIONS_ERROR
;
604 save a dn_list into a full @IDX style record
606 static int ltdb_dn_list_store_full(struct ldb_module
*module
,
607 struct ltdb_private
*ltdb
,
609 struct dn_list
*list
)
611 struct ldb_message
*msg
;
614 msg
= ldb_msg_new(module
);
616 return ldb_module_oom(module
);
621 if (list
->count
== 0) {
622 ret
= ltdb_delete_noindex(module
, msg
);
623 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
630 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
631 ret
= ldb_msg_add_fmt(msg
, LTDB_IDXVERSION
, "%u",
632 LTDB_INDEXING_VERSION
);
633 if (ret
!= LDB_SUCCESS
) {
635 return ldb_module_oom(module
);
638 ret
= ldb_msg_add_fmt(msg
, LTDB_IDXVERSION
, "%u",
639 LTDB_GUID_INDEXING_VERSION
);
640 if (ret
!= LDB_SUCCESS
) {
642 return ldb_module_oom(module
);
646 if (list
->count
> 0) {
647 struct ldb_message_element
*el
;
649 ret
= ldb_msg_add_empty(msg
, LTDB_IDX
, LDB_FLAG_MOD_ADD
, &el
);
650 if (ret
!= LDB_SUCCESS
) {
652 return ldb_module_oom(module
);
655 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
656 el
->values
= list
->dn
;
657 el
->num_values
= list
->count
;
661 el
->values
= talloc_array(msg
,
663 if (el
->values
== NULL
) {
665 return ldb_module_oom(module
);
668 v
.data
= talloc_array_size(el
->values
,
671 if (v
.data
== NULL
) {
673 return ldb_module_oom(module
);
676 v
.length
= talloc_get_size(v
.data
);
678 for (i
= 0; i
< list
->count
; i
++) {
679 if (list
->dn
[i
].length
!=
682 return ldb_module_operr(module
);
684 memcpy(&v
.data
[LTDB_GUID_SIZE
*i
],
693 ret
= ltdb_store(module
, msg
, TDB_REPLACE
);
699 save a dn_list into the database, in either @IDX or internal format
701 static int ltdb_dn_list_store(struct ldb_module
*module
, struct ldb_dn
*dn
,
702 struct dn_list
*list
)
704 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
707 struct dn_list
*list2
;
709 if (ltdb
->idxptr
== NULL
) {
710 return ltdb_dn_list_store_full(module
, ltdb
,
714 if (ltdb
->idxptr
->itdb
== NULL
) {
715 ltdb
->idxptr
->itdb
= tdb_open(NULL
, 1000, TDB_INTERNAL
, O_RDWR
, 0);
716 if (ltdb
->idxptr
->itdb
== NULL
) {
717 return LDB_ERR_OPERATIONS_ERROR
;
721 key
.dptr
= discard_const_p(unsigned char, ldb_dn_get_linearized(dn
));
722 if (key
.dptr
== NULL
) {
723 return LDB_ERR_OPERATIONS_ERROR
;
725 key
.dsize
= strlen((char *)key
.dptr
);
727 rec
= tdb_fetch(ltdb
->idxptr
->itdb
, key
);
728 if (rec
.dptr
!= NULL
) {
729 list2
= ltdb_index_idxptr(module
, rec
, false);
732 return LDB_ERR_OPERATIONS_ERROR
;
735 list2
->dn
= talloc_steal(list2
, list
->dn
);
736 list2
->count
= list
->count
;
740 list2
= talloc(ltdb
->idxptr
, struct dn_list
);
742 return LDB_ERR_OPERATIONS_ERROR
;
744 list2
->dn
= talloc_steal(list2
, list
->dn
);
745 list2
->count
= list
->count
;
747 rec
.dptr
= (uint8_t *)&list2
;
748 rec
.dsize
= sizeof(void *);
752 * This is not a store into the main DB, but into an in-memory
753 * TDB, so we don't need a guard on ltdb->read_only
755 ret
= tdb_store(ltdb
->idxptr
->itdb
, key
, rec
, TDB_INSERT
);
757 return ltdb_err_map(tdb_error(ltdb
->idxptr
->itdb
));
763 traverse function for storing the in-memory index entries on disk
765 static int ltdb_index_traverse_store(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
767 struct ldb_module
*module
= state
;
768 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
770 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
772 struct dn_list
*list
;
774 list
= ltdb_index_idxptr(module
, data
, true);
776 ltdb
->idxptr
->error
= LDB_ERR_OPERATIONS_ERROR
;
781 v
.length
= strnlen((char *)key
.dptr
, key
.dsize
);
783 dn
= ldb_dn_from_ldb_val(module
, ldb
, &v
);
785 ldb_asprintf_errstring(ldb
, "Failed to parse index key %*.*s as an LDB DN", (int)v
.length
, (int)v
.length
, (const char *)v
.data
);
786 ltdb
->idxptr
->error
= LDB_ERR_OPERATIONS_ERROR
;
790 ltdb
->idxptr
->error
= ltdb_dn_list_store_full(module
, ltdb
,
793 if (ltdb
->idxptr
->error
!= 0) {
799 /* cleanup the idxptr mode when transaction commits */
800 int ltdb_index_transaction_commit(struct ldb_module
*module
)
802 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
805 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
807 ldb_reset_err_string(ldb
);
809 if (ltdb
->idxptr
->itdb
) {
810 tdb_traverse(ltdb
->idxptr
->itdb
, ltdb_index_traverse_store
, module
);
811 tdb_close(ltdb
->idxptr
->itdb
);
814 ret
= ltdb
->idxptr
->error
;
815 if (ret
!= LDB_SUCCESS
) {
816 if (!ldb_errstring(ldb
)) {
817 ldb_set_errstring(ldb
, ldb_strerror(ret
));
819 ldb_asprintf_errstring(ldb
, "Failed to store index records in transaction commit: %s", ldb_errstring(ldb
));
822 talloc_free(ltdb
->idxptr
);
827 /* cleanup the idxptr mode when transaction cancels */
828 int ltdb_index_transaction_cancel(struct ldb_module
*module
)
830 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
831 if (ltdb
->idxptr
&& ltdb
->idxptr
->itdb
) {
832 tdb_close(ltdb
->idxptr
->itdb
);
834 talloc_free(ltdb
->idxptr
);
841 return the dn key to be used for an index
842 the caller is responsible for freeing
844 static struct ldb_dn
*ltdb_index_key(struct ldb_context
*ldb
,
845 struct ltdb_private
*ltdb
,
846 const char *attr
, const struct ldb_val
*value
,
847 const struct ldb_schema_attribute
**ap
,
848 enum key_truncation
*truncation
)
852 const struct ldb_schema_attribute
*a
= NULL
;
853 char *attr_folded
= NULL
;
854 const char *attr_for_dn
= NULL
;
856 bool should_b64_encode
;
858 unsigned int max_key_length
= ltdb_max_key_length(ltdb
);
861 const size_t indx_len
= sizeof(LTDB_INDEX
) - 1;
862 unsigned frmt_len
= 0;
863 const size_t additional_key_length
= 4;
864 unsigned int num_separators
= 3; /* Estimate for overflow check */
865 const size_t min_data
= 1;
866 const size_t min_key_length
= additional_key_length
867 + indx_len
+ num_separators
+ min_data
;
869 if (attr
[0] == '@') {
876 attr_folded
= ldb_attr_casefold(ldb
, attr
);
881 attr_for_dn
= attr_folded
;
883 a
= ldb_schema_attribute_by_name(ldb
, attr
);
887 r
= a
->syntax
->canonicalise_fn(ldb
, ldb
, value
, &v
);
888 if (r
!= LDB_SUCCESS
) {
889 const char *errstr
= ldb_errstring(ldb
);
890 /* canonicalisation can be refused. For
891 example, a attribute that takes wildcards
892 will refuse to canonicalise if the value
893 contains a wildcard */
894 ldb_asprintf_errstring(ldb
,
895 "Failed to create index "
896 "key for attribute '%s':%s%s%s",
897 attr
, ldb_strerror(r
),
900 talloc_free(attr_folded
);
904 attr_len
= strlen(attr_for_dn
);
907 * Check if there is any hope this will fit into the DB.
908 * Overflow here is not actually critical the code below
909 * checks again to make the printf and the DB does another
910 * check for too long keys
912 if (max_key_length
- attr_len
< min_key_length
) {
913 ldb_asprintf_errstring(
915 __location__
": max_key_length "
916 "is too small (%u) < (%u)",
918 (unsigned)(min_key_length
+ attr_len
));
919 talloc_free(attr_folded
);
924 * ltdb_key_dn() makes something 4 bytes longer, it adds a leading
925 * "DN=" and a trailing string terminator
927 max_key_length
-= additional_key_length
;
930 * We do not base 64 encode a DN in a key, it has already been
931 * casefold and lineraized, that is good enough. That already
932 * avoids embedded NUL etc.
934 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
935 if (strcmp(attr
, LTDB_IDXDN
) == 0) {
936 should_b64_encode
= false;
937 } else if (strcmp(attr
, LTDB_IDXONE
) == 0) {
939 * We can only change the behaviour for IDXONE
940 * when the GUID index is enabled
942 should_b64_encode
= false;
945 = ldb_should_b64_encode(ldb
, &v
);
948 should_b64_encode
= ldb_should_b64_encode(ldb
, &v
);
951 if (should_b64_encode
) {
953 char *vstr
= ldb_base64_encode(ldb
, (char *)v
.data
, v
.length
);
955 talloc_free(attr_folded
);
958 vstr_len
= strlen(vstr
);
960 * Overflow here is not critical as we only use this
961 * to choose the printf truncation
963 key_len
= num_separators
+ indx_len
+ attr_len
+ vstr_len
;
964 if (key_len
> max_key_length
) {
965 size_t excess
= key_len
- max_key_length
;
966 frmt_len
= vstr_len
- excess
;
967 *truncation
= KEY_TRUNCATED
;
969 * Truncated keys are placed in a separate key space
970 * from the non truncated keys
971 * Note: the double hash "##" is not a typo and
972 * indicates that the following value is base64 encoded
974 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s#%s##%.*s",
975 LTDB_INDEX
, attr_for_dn
,
979 *truncation
= KEY_NOT_TRUNCATED
;
981 * Note: the double colon "::" is not a typo and
982 * indicates that the following value is base64 encoded
984 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s::%.*s",
985 LTDB_INDEX
, attr_for_dn
,
990 /* Only need two seperators */
994 * Overflow here is not critical as we only use this
995 * to choose the printf truncation
997 key_len
= num_separators
+ indx_len
+ attr_len
+ (int)v
.length
;
998 if (key_len
> max_key_length
) {
999 size_t excess
= key_len
- max_key_length
;
1000 frmt_len
= v
.length
- excess
;
1001 *truncation
= KEY_TRUNCATED
;
1003 * Truncated keys are placed in a separate key space
1004 * from the non truncated keys
1006 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s#%s#%.*s",
1007 LTDB_INDEX
, attr_for_dn
,
1008 frmt_len
, (char *)v
.data
);
1010 frmt_len
= v
.length
;
1011 *truncation
= KEY_NOT_TRUNCATED
;
1012 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s:%.*s",
1013 LTDB_INDEX
, attr_for_dn
,
1014 frmt_len
, (char *)v
.data
);
1018 if (v
.data
!= value
->data
) {
1019 talloc_free(v
.data
);
1021 talloc_free(attr_folded
);
1027 see if a attribute value is in the list of indexed attributes
1029 static bool ltdb_is_indexed(struct ldb_module
*module
,
1030 struct ltdb_private
*ltdb
,
1033 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
1035 struct ldb_message_element
*el
;
1037 if ((ltdb
->cache
->GUID_index_attribute
!= NULL
) &&
1039 ltdb
->cache
->GUID_index_attribute
) == 0)) {
1040 /* Implicity covered, this is the index key */
1043 if (ldb
->schema
.index_handler_override
) {
1044 const struct ldb_schema_attribute
*a
1045 = ldb_schema_attribute_by_name(ldb
, attr
);
1051 if (a
->flags
& LDB_ATTR_FLAG_INDEXED
) {
1058 if (!ltdb
->cache
->attribute_indexes
) {
1062 el
= ldb_msg_find_element(ltdb
->cache
->indexlist
, LTDB_IDXATTR
);
1067 /* TODO: this is too expensive! At least use a binary search */
1068 for (i
=0; i
<el
->num_values
; i
++) {
1069 if (ldb_attr_cmp((char *)el
->values
[i
].data
, attr
) == 0) {
1077 in the following logic functions, the return value is treated as
1080 LDB_SUCCESS: we found some matching index values
1082 LDB_ERR_NO_SUCH_OBJECT: we know for sure that no object matches
1084 LDB_ERR_OPERATIONS_ERROR: indexing could not answer the call,
1085 we'll need a full search
1089 return a list of dn's that might match a simple indexed search (an
1090 equality search only)
1092 static int ltdb_index_dn_simple(struct ldb_module
*module
,
1093 struct ltdb_private
*ltdb
,
1094 const struct ldb_parse_tree
*tree
,
1095 struct dn_list
*list
)
1097 struct ldb_context
*ldb
;
1100 enum key_truncation truncation
= KEY_NOT_TRUNCATED
;
1102 ldb
= ldb_module_get_ctx(module
);
1107 /* if the attribute isn't in the list of indexed attributes then
1108 this node needs a full search */
1109 if (!ltdb_is_indexed(module
, ltdb
, tree
->u
.equality
.attr
)) {
1110 return LDB_ERR_OPERATIONS_ERROR
;
1113 /* the attribute is indexed. Pull the list of DNs that match the
1115 dn
= ltdb_index_key(ldb
, ltdb
,
1116 tree
->u
.equality
.attr
,
1117 &tree
->u
.equality
.value
, NULL
, &truncation
);
1119 * We ignore truncation here and allow multi-valued matches
1120 * as ltdb_search_indexed will filter out the wrong one in
1121 * ltdb_index_filter() which calls ldb_match_message().
1123 if (!dn
) return LDB_ERR_OPERATIONS_ERROR
;
1125 ret
= ltdb_dn_list_load(module
, ltdb
, dn
, list
);
1131 static bool list_union(struct ldb_context
*ldb
,
1132 struct ltdb_private
*ltdb
,
1133 struct dn_list
*list
, struct dn_list
*list2
);
1136 return a list of dn's that might match a leaf indexed search
1138 static int ltdb_index_dn_leaf(struct ldb_module
*module
,
1139 struct ltdb_private
*ltdb
,
1140 const struct ldb_parse_tree
*tree
,
1141 struct dn_list
*list
)
1143 if (ltdb
->disallow_dn_filter
&&
1144 (ldb_attr_cmp(tree
->u
.equality
.attr
, "dn") == 0)) {
1145 /* in AD mode we do not support "(dn=...)" search filters */
1150 if (tree
->u
.equality
.attr
[0] == '@') {
1151 /* Do not allow a indexed search against an @ */
1156 if (ldb_attr_dn(tree
->u
.equality
.attr
) == 0) {
1157 enum key_truncation truncation
= KEY_NOT_TRUNCATED
;
1159 = ldb_dn_from_ldb_val(list
,
1160 ldb_module_get_ctx(module
),
1161 &tree
->u
.equality
.value
);
1163 /* If we can't parse it, no match */
1170 * Re-use the same code we use for a SCOPE_BASE
1173 * We can't call TALLOC_FREE(dn) as this must belong
1174 * to list for the memory to remain valid.
1176 return ltdb_index_dn_base_dn(module
, ltdb
, dn
, list
,
1179 * We ignore truncation here and allow multi-valued matches
1180 * as ltdb_search_indexed will filter out the wrong one in
1181 * ltdb_index_filter() which calls ldb_match_message().
1184 } else if ((ltdb
->cache
->GUID_index_attribute
!= NULL
) &&
1185 (ldb_attr_cmp(tree
->u
.equality
.attr
,
1186 ltdb
->cache
->GUID_index_attribute
) == 0)) {
1188 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
1189 list
->dn
= talloc_array(list
, struct ldb_val
, 1);
1190 if (list
->dn
== NULL
) {
1191 ldb_module_oom(module
);
1192 return LDB_ERR_OPERATIONS_ERROR
;
1195 * We need to go via the canonicalise_fn() to
1196 * ensure we get the index in binary, rather
1199 ret
= ltdb
->GUID_index_syntax
->canonicalise_fn(ldb
,
1201 &tree
->u
.equality
.value
,
1203 if (ret
!= LDB_SUCCESS
) {
1204 return LDB_ERR_OPERATIONS_ERROR
;
1210 return ltdb_index_dn_simple(module
, ltdb
, tree
, list
);
1218 static bool list_intersect(struct ldb_context
*ldb
,
1219 struct ltdb_private
*ltdb
,
1220 struct dn_list
*list
, const struct dn_list
*list2
)
1222 const struct dn_list
*short_list
, *long_list
;
1223 struct dn_list
*list3
;
1226 if (list
->count
== 0) {
1230 if (list2
->count
== 0) {
1237 /* the indexing code is allowed to return a longer list than
1238 what really matches, as all results are filtered by the
1239 full expression at the end - this shortcut avoids a lot of
1240 work in some cases */
1241 if (list
->count
< 2 && list2
->count
> 10 && list2
->strict
== false) {
1244 if (list2
->count
< 2 && list
->count
> 10 && list
->strict
== false) {
1245 list
->count
= list2
->count
;
1246 list
->dn
= list2
->dn
;
1247 /* note that list2 may not be the parent of list2->dn,
1248 as list2->dn may be owned by ltdb->idxptr. In that
1249 case we expect this reparent call to fail, which is
1251 talloc_reparent(list2
, list
, list2
->dn
);
1255 if (list
->count
> list2
->count
) {
1263 list3
= talloc_zero(list
, struct dn_list
);
1264 if (list3
== NULL
) {
1268 list3
->dn
= talloc_array(list3
, struct ldb_val
,
1269 MIN(list
->count
, list2
->count
));
1276 for (i
=0;i
<short_list
->count
;i
++) {
1277 /* For the GUID index case, this is a binary search */
1278 if (ltdb_dn_list_find_val(ltdb
, long_list
,
1279 &short_list
->dn
[i
]) != -1) {
1280 list3
->dn
[list3
->count
] = short_list
->dn
[i
];
1285 list
->strict
|= list2
->strict
;
1286 list
->dn
= talloc_steal(list
, list3
->dn
);
1287 list
->count
= list3
->count
;
1298 static bool list_union(struct ldb_context
*ldb
,
1299 struct ltdb_private
*ltdb
,
1300 struct dn_list
*list
, struct dn_list
*list2
)
1302 struct ldb_val
*dn3
;
1303 unsigned int i
= 0, j
= 0, k
= 0;
1305 if (list2
->count
== 0) {
1310 if (list
->count
== 0) {
1312 list
->count
= list2
->count
;
1313 list
->dn
= list2
->dn
;
1314 /* note that list2 may not be the parent of list2->dn,
1315 as list2->dn may be owned by ltdb->idxptr. In that
1316 case we expect this reparent call to fail, which is
1318 talloc_reparent(list2
, list
, list2
->dn
);
1323 * Sort the lists (if not in GUID DN mode) so we can do
1324 * the de-duplication during the merge
1326 * NOTE: This can sort the in-memory index values, as list or
1327 * list2 might not be a copy!
1329 ltdb_dn_list_sort(ltdb
, list
);
1330 ltdb_dn_list_sort(ltdb
, list2
);
1332 dn3
= talloc_array(list
, struct ldb_val
, list
->count
+ list2
->count
);
1338 while (i
< list
->count
|| j
< list2
->count
) {
1340 if (i
>= list
->count
) {
1342 } else if (j
>= list2
->count
) {
1345 cmp
= ldb_val_equal_exact_ordered(list
->dn
[i
],
1351 dn3
[k
] = list
->dn
[i
];
1354 } else if (cmp
> 0) {
1356 dn3
[k
] = list2
->dn
[j
];
1360 /* Equal, take list */
1361 dn3
[k
] = list
->dn
[i
];
1374 static int ltdb_index_dn(struct ldb_module
*module
,
1375 struct ltdb_private
*ltdb
,
1376 const struct ldb_parse_tree
*tree
,
1377 struct dn_list
*list
);
1381 process an OR list (a union)
1383 static int ltdb_index_dn_or(struct ldb_module
*module
,
1384 struct ltdb_private
*ltdb
,
1385 const struct ldb_parse_tree
*tree
,
1386 struct dn_list
*list
)
1388 struct ldb_context
*ldb
;
1391 ldb
= ldb_module_get_ctx(module
);
1396 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
1397 struct dn_list
*list2
;
1400 list2
= talloc_zero(list
, struct dn_list
);
1401 if (list2
== NULL
) {
1402 return LDB_ERR_OPERATIONS_ERROR
;
1405 ret
= ltdb_index_dn(module
, ltdb
,
1406 tree
->u
.list
.elements
[i
], list2
);
1408 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1414 if (ret
!= LDB_SUCCESS
) {
1420 if (!list_union(ldb
, ltdb
, list
, list2
)) {
1422 return LDB_ERR_OPERATIONS_ERROR
;
1426 if (list
->count
== 0) {
1427 return LDB_ERR_NO_SUCH_OBJECT
;
1435 NOT an index results
1437 static int ltdb_index_dn_not(struct ldb_module
*module
,
1438 struct ltdb_private
*ltdb
,
1439 const struct ldb_parse_tree
*tree
,
1440 struct dn_list
*list
)
1442 /* the only way to do an indexed not would be if we could
1443 negate the not via another not or if we knew the total
1444 number of database elements so we could know that the
1445 existing expression covered the whole database.
1447 instead, we just give up, and rely on a full index scan
1448 (unless an outer & manages to reduce the list)
1450 return LDB_ERR_OPERATIONS_ERROR
;
1454 * These things are unique, so avoid a full scan if this is a search
1455 * by GUID, DN or a unique attribute
1457 static bool ltdb_index_unique(struct ldb_context
*ldb
,
1458 struct ltdb_private
*ltdb
,
1461 const struct ldb_schema_attribute
*a
;
1462 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1463 if (ldb_attr_cmp(attr
, ltdb
->cache
->GUID_index_attribute
) == 0) {
1467 if (ldb_attr_dn(attr
) == 0) {
1471 a
= ldb_schema_attribute_by_name(ldb
, attr
);
1472 if (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
) {
1479 process an AND expression (intersection)
1481 static int ltdb_index_dn_and(struct ldb_module
*module
,
1482 struct ltdb_private
*ltdb
,
1483 const struct ldb_parse_tree
*tree
,
1484 struct dn_list
*list
)
1486 struct ldb_context
*ldb
;
1490 ldb
= ldb_module_get_ctx(module
);
1495 /* in the first pass we only look for unique simple
1496 equality tests, in the hope of avoiding having to look
1498 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
1499 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
1502 if (subtree
->operation
!= LDB_OP_EQUALITY
||
1503 !ltdb_index_unique(ldb
, ltdb
,
1504 subtree
->u
.equality
.attr
)) {
1508 ret
= ltdb_index_dn(module
, ltdb
, subtree
, list
);
1509 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1511 return LDB_ERR_NO_SUCH_OBJECT
;
1513 if (ret
== LDB_SUCCESS
) {
1514 /* a unique index match means we can
1515 * stop. Note that we don't care if we return
1516 * a few too many objects, due to later
1522 /* now do a full intersection */
1525 for (i
=0; i
<tree
->u
.list
.num_elements
; i
++) {
1526 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
1527 struct dn_list
*list2
;
1530 list2
= talloc_zero(list
, struct dn_list
);
1531 if (list2
== NULL
) {
1532 return ldb_module_oom(module
);
1535 ret
= ltdb_index_dn(module
, ltdb
, subtree
, list2
);
1537 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1542 return LDB_ERR_NO_SUCH_OBJECT
;
1545 if (ret
!= LDB_SUCCESS
) {
1546 /* this didn't adding anything */
1552 talloc_reparent(list2
, list
, list
->dn
);
1553 list
->dn
= list2
->dn
;
1554 list
->count
= list2
->count
;
1556 } else if (!list_intersect(ldb
, ltdb
,
1559 return LDB_ERR_OPERATIONS_ERROR
;
1562 if (list
->count
== 0) {
1564 return LDB_ERR_NO_SUCH_OBJECT
;
1567 if (list
->count
< 2) {
1568 /* it isn't worth loading the next part of the tree */
1574 /* none of the attributes were indexed */
1575 return LDB_ERR_OPERATIONS_ERROR
;
1582 return a list of matching objects using a one-level index
1584 static int ltdb_index_dn_attr(struct ldb_module
*module
,
1585 struct ltdb_private
*ltdb
,
1588 struct dn_list
*list
,
1589 enum key_truncation
*truncation
)
1591 struct ldb_context
*ldb
;
1596 ldb
= ldb_module_get_ctx(module
);
1598 /* work out the index key from the parent DN */
1599 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn
));
1600 val
.length
= strlen((char *)val
.data
);
1601 key
= ltdb_index_key(ldb
, ltdb
, attr
, &val
, NULL
, truncation
);
1604 return LDB_ERR_OPERATIONS_ERROR
;
1607 ret
= ltdb_dn_list_load(module
, ltdb
, key
, list
);
1609 if (ret
!= LDB_SUCCESS
) {
1613 if (list
->count
== 0) {
1614 return LDB_ERR_NO_SUCH_OBJECT
;
1621 return a list of matching objects using a one-level index
1623 static int ltdb_index_dn_one(struct ldb_module
*module
,
1624 struct ltdb_private
*ltdb
,
1625 struct ldb_dn
*parent_dn
,
1626 struct dn_list
*list
,
1627 enum key_truncation
*truncation
)
1629 /* Ensure we do not shortcut on intersection for this list */
1630 list
->strict
= true;
1631 return ltdb_index_dn_attr(module
, ltdb
,
1632 LTDB_IDXONE
, parent_dn
, list
, truncation
);
1637 return a list of matching objects using the DN index
1639 static int ltdb_index_dn_base_dn(struct ldb_module
*module
,
1640 struct ltdb_private
*ltdb
,
1641 struct ldb_dn
*base_dn
,
1642 struct dn_list
*dn_list
,
1643 enum key_truncation
*truncation
)
1645 const struct ldb_val
*guid_val
= NULL
;
1646 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
1647 dn_list
->dn
= talloc_array(dn_list
, struct ldb_val
, 1);
1648 if (dn_list
->dn
== NULL
) {
1649 return ldb_module_oom(module
);
1651 dn_list
->dn
[0].data
= discard_const_p(unsigned char,
1652 ldb_dn_get_linearized(base_dn
));
1653 if (dn_list
->dn
[0].data
== NULL
) {
1654 return ldb_module_oom(module
);
1656 dn_list
->dn
[0].length
= strlen((char *)dn_list
->dn
[0].data
);
1662 if (ltdb
->cache
->GUID_index_dn_component
!= NULL
) {
1663 guid_val
= ldb_dn_get_extended_component(base_dn
,
1664 ltdb
->cache
->GUID_index_dn_component
);
1667 if (guid_val
!= NULL
) {
1668 dn_list
->dn
= talloc_array(dn_list
, struct ldb_val
, 1);
1669 if (dn_list
->dn
== NULL
) {
1670 return ldb_module_oom(module
);
1672 dn_list
->dn
[0].data
= guid_val
->data
;
1673 dn_list
->dn
[0].length
= guid_val
->length
;
1679 return ltdb_index_dn_attr(module
, ltdb
,
1680 LTDB_IDXDN
, base_dn
, dn_list
, truncation
);
1684 return a list of dn's that might match a indexed search or
1685 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
1687 static int ltdb_index_dn(struct ldb_module
*module
,
1688 struct ltdb_private
*ltdb
,
1689 const struct ldb_parse_tree
*tree
,
1690 struct dn_list
*list
)
1692 int ret
= LDB_ERR_OPERATIONS_ERROR
;
1694 switch (tree
->operation
) {
1696 ret
= ltdb_index_dn_and(module
, ltdb
, tree
, list
);
1700 ret
= ltdb_index_dn_or(module
, ltdb
, tree
, list
);
1704 ret
= ltdb_index_dn_not(module
, ltdb
, tree
, list
);
1707 case LDB_OP_EQUALITY
:
1708 ret
= ltdb_index_dn_leaf(module
, ltdb
, tree
, list
);
1711 case LDB_OP_SUBSTRING
:
1712 case LDB_OP_GREATER
:
1714 case LDB_OP_PRESENT
:
1716 case LDB_OP_EXTENDED
:
1717 /* we can't index with fancy bitops yet */
1718 ret
= LDB_ERR_OPERATIONS_ERROR
;
1726 filter a candidate dn_list from an indexed search into a set of results
1727 extracting just the given attributes
1729 static int ltdb_index_filter(struct ltdb_private
*ltdb
,
1730 const struct dn_list
*dn_list
,
1731 struct ltdb_context
*ac
,
1732 uint32_t *match_count
,
1733 enum key_truncation scope_one_truncation
)
1735 struct ldb_context
*ldb
= ldb_module_get_ctx(ac
->module
);
1736 struct ldb_message
*msg
;
1737 struct ldb_message
*filtered_msg
;
1739 unsigned int num_keys
= 0;
1740 uint8_t previous_guid_key
[LTDB_GUID_KEY_SIZE
] = {};
1741 TDB_DATA
*keys
= NULL
;
1744 * We have to allocate the key list (rather than just walk the
1745 * caller supplied list) as the callback could change the list
1746 * (by modifying an indexed attribute hosted in the in-memory
1749 keys
= talloc_array(ac
, TDB_DATA
, dn_list
->count
);
1751 return ldb_module_oom(ac
->module
);
1754 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1756 * We speculate that the keys will be GUID based and so
1757 * pre-fill in enough space for a GUID (avoiding a pile of
1758 * small allocations)
1760 struct guid_tdb_key
{
1761 uint8_t guid_key
[LTDB_GUID_KEY_SIZE
];
1762 } *key_values
= NULL
;
1764 key_values
= talloc_array(keys
,
1765 struct guid_tdb_key
,
1768 if (key_values
== NULL
) {
1770 return ldb_module_oom(ac
->module
);
1772 for (i
= 0; i
< dn_list
->count
; i
++) {
1773 keys
[i
].dptr
= key_values
[i
].guid_key
;
1774 keys
[i
].dsize
= sizeof(key_values
[i
].guid_key
);
1777 for (i
= 0; i
< dn_list
->count
; i
++) {
1778 keys
[i
].dptr
= NULL
;
1783 for (i
= 0; i
< dn_list
->count
; i
++) {
1786 ret
= ltdb_idx_to_key(ac
->module
,
1791 if (ret
!= LDB_SUCCESS
) {
1796 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1798 * If we are in GUID index mode, then the dn_list is
1799 * sorted. If we got a duplicate, forget about it, as
1800 * otherwise we would send the same entry back more
1803 * This is needed in the truncated DN case, or if a
1804 * duplicate was forced in via
1805 * LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK
1808 if (memcmp(previous_guid_key
,
1809 keys
[num_keys
].dptr
,
1810 sizeof(previous_guid_key
)) == 0) {
1814 memcpy(previous_guid_key
,
1815 keys
[num_keys
].dptr
,
1816 sizeof(previous_guid_key
));
1823 * Now that the list is a safe copy, send the callbacks
1825 for (i
= 0; i
< num_keys
; i
++) {
1828 msg
= ldb_msg_new(ac
);
1831 return LDB_ERR_OPERATIONS_ERROR
;
1834 ret
= ltdb_search_key(ac
->module
, ltdb
,
1836 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
|
1837 LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC
);
1838 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1840 * the record has disappeared? yes, this can
1841 * happen if the entry is deleted by something
1842 * operating in the callback (not another
1843 * process, as we have a read lock)
1849 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1850 /* an internal error */
1853 return LDB_ERR_OPERATIONS_ERROR
;
1857 * We trust the index for LDB_SCOPE_ONELEVEL
1858 * unless the index key has been truncated.
1860 * LDB_SCOPE_BASE is not passed in by our only caller.
1862 if (ac
->scope
== LDB_SCOPE_ONELEVEL
1863 && ltdb
->cache
->one_level_indexes
1864 && scope_one_truncation
== KEY_NOT_TRUNCATED
) {
1865 ret
= ldb_match_message(ldb
, msg
, ac
->tree
,
1866 ac
->scope
, &matched
);
1868 ret
= ldb_match_msg_error(ldb
, msg
,
1870 ac
->scope
, &matched
);
1873 if (ret
!= LDB_SUCCESS
) {
1883 /* filter the attributes that the user wants */
1884 ret
= ltdb_filter_attrs(ac
, msg
, ac
->attrs
, &filtered_msg
);
1890 return LDB_ERR_OPERATIONS_ERROR
;
1893 ret
= ldb_module_send_entry(ac
->req
, filtered_msg
, NULL
);
1894 if (ret
!= LDB_SUCCESS
) {
1895 /* Regardless of success or failure, the msg
1896 * is the callbacks responsiblity, and should
1897 * not be talloc_free()'ed */
1898 ac
->request_terminated
= true;
1913 static void ltdb_dn_list_sort(struct ltdb_private
*ltdb
,
1914 struct dn_list
*list
)
1916 if (list
->count
< 2) {
1920 /* We know the list is sorted when using the GUID index */
1921 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
1925 TYPESAFE_QSORT(list
->dn
, list
->count
,
1926 ldb_val_equal_exact_for_qsort
);
1930 search the database with a LDAP-like expression using indexes
1931 returns -1 if an indexed search is not possible, in which
1932 case the caller should call ltdb_search_full()
1934 int ltdb_search_indexed(struct ltdb_context
*ac
, uint32_t *match_count
)
1936 struct ldb_context
*ldb
= ldb_module_get_ctx(ac
->module
);
1937 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(ac
->module
), struct ltdb_private
);
1938 struct dn_list
*dn_list
;
1940 enum ldb_scope index_scope
;
1941 enum key_truncation scope_one_truncation
= KEY_NOT_TRUNCATED
;
1943 /* see if indexing is enabled */
1944 if (!ltdb
->cache
->attribute_indexes
&&
1945 !ltdb
->cache
->one_level_indexes
&&
1946 ac
->scope
!= LDB_SCOPE_BASE
) {
1947 /* fallback to a full search */
1948 return LDB_ERR_OPERATIONS_ERROR
;
1951 dn_list
= talloc_zero(ac
, struct dn_list
);
1952 if (dn_list
== NULL
) {
1953 return ldb_module_oom(ac
->module
);
1957 * For the purposes of selecting the switch arm below, if we
1958 * don't have a one-level index then treat it like a subtree
1961 if (ac
->scope
== LDB_SCOPE_ONELEVEL
&&
1962 !ltdb
->cache
->one_level_indexes
) {
1963 index_scope
= LDB_SCOPE_SUBTREE
;
1965 index_scope
= ac
->scope
;
1968 switch (index_scope
) {
1969 case LDB_SCOPE_BASE
:
1971 * The only caller will have filtered the operation out
1972 * so we should never get here
1974 return ldb_operr(ldb
);
1976 case LDB_SCOPE_ONELEVEL
:
1978 * If we ever start to also load the index values for
1979 * the tree, we must ensure we strictly intersect with
1980 * this list, as we trust the ONELEVEL index
1982 ret
= ltdb_index_dn_one(ac
->module
, ltdb
, ac
->base
, dn_list
,
1983 &scope_one_truncation
);
1984 if (ret
!= LDB_SUCCESS
) {
1985 talloc_free(dn_list
);
1990 * If we have too many matches, running the filter
1991 * tree over the SCOPE_ONELEVEL can be quite expensive
1992 * so we now check the filter tree index as well.
1994 * We only do this in the GUID index mode, which is
1995 * O(n*log(m)) otherwise the intersection below will
1996 * be too costly at O(n*m).
1998 * We don't set a heuristic for 'too many' but instead
1999 * do it always and rely on the index lookup being
2000 * fast enough in the small case.
2002 if (ltdb
->cache
->GUID_index_attribute
!= NULL
) {
2003 struct dn_list
*idx_one_tree_list
2004 = talloc_zero(ac
, struct dn_list
);
2005 if (idx_one_tree_list
== NULL
) {
2006 return ldb_module_oom(ac
->module
);
2009 if (!ltdb
->cache
->attribute_indexes
) {
2010 talloc_free(idx_one_tree_list
);
2011 talloc_free(dn_list
);
2012 return LDB_ERR_OPERATIONS_ERROR
;
2015 * Here we load the index for the tree.
2017 * We only care if this is successful, if the
2018 * index can't trim the result list down then
2019 * the ONELEVEL index is still good enough.
2021 ret
= ltdb_index_dn(ac
->module
, ltdb
, ac
->tree
,
2023 if (ret
== LDB_SUCCESS
) {
2024 if (!list_intersect(ldb
, ltdb
,
2026 idx_one_tree_list
)) {
2027 talloc_free(idx_one_tree_list
);
2028 talloc_free(dn_list
);
2029 return LDB_ERR_OPERATIONS_ERROR
;
2035 case LDB_SCOPE_SUBTREE
:
2036 case LDB_SCOPE_DEFAULT
:
2037 if (!ltdb
->cache
->attribute_indexes
) {
2038 talloc_free(dn_list
);
2039 return LDB_ERR_OPERATIONS_ERROR
;
2042 * Here we load the index for the tree. We have no
2043 * index for the subtree.
2045 ret
= ltdb_index_dn(ac
->module
, ltdb
, ac
->tree
, dn_list
);
2046 if (ret
!= LDB_SUCCESS
) {
2047 talloc_free(dn_list
);
2054 * It is critical that this function do the re-filter even
2055 * on things found by the index as the index can over-match
2056 * in cases of truncation (as well as when it decides it is
2057 * not worth further filtering)
2059 * If this changes, then the index code above would need to
2060 * pass up a flag to say if any index was truncated during
2061 * processing as the truncation here refers only to the
2062 * SCOPE_ONELEVEL index.
2064 ret
= ltdb_index_filter(ltdb
, dn_list
, ac
, match_count
,
2065 scope_one_truncation
);
2066 talloc_free(dn_list
);
2071 * @brief Add a DN in the index list of a given attribute name/value pair
2073 * This function will add the DN in the index list for the index for
2074 * the given attribute name and value.
2076 * @param[in] module A ldb_module structure
2078 * @param[in] dn The string representation of the DN as it
2079 * will be stored in the index entry
2081 * @param[in] el A ldb_message_element array, one of the entry
2082 * referred by the v_idx is the attribute name and
2083 * value pair which will be used to construct the
2086 * @param[in] v_idx The index of element in the el array to use
2088 * @return An ldb error code
2090 static int ltdb_index_add1(struct ldb_module
*module
,
2091 struct ltdb_private
*ltdb
,
2092 const struct ldb_message
*msg
,
2093 struct ldb_message_element
*el
, int v_idx
)
2095 struct ldb_context
*ldb
;
2096 struct ldb_dn
*dn_key
;
2098 const struct ldb_schema_attribute
*a
;
2099 struct dn_list
*list
;
2101 enum key_truncation truncation
= KEY_TRUNCATED
;
2104 ldb
= ldb_module_get_ctx(module
);
2106 list
= talloc_zero(module
, struct dn_list
);
2108 return LDB_ERR_OPERATIONS_ERROR
;
2111 dn_key
= ltdb_index_key(ldb
, ltdb
,
2112 el
->name
, &el
->values
[v_idx
], &a
, &truncation
);
2115 return LDB_ERR_OPERATIONS_ERROR
;
2118 * Samba only maintains unique indexes on the objectSID and objectGUID
2119 * so if a unique index key exceeds the maximum length there is a
2122 if ((truncation
== KEY_TRUNCATED
) && (a
!= NULL
&&
2123 (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
||
2124 (el
->flags
& LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX
)))) {
2126 ldb_asprintf_errstring(
2128 __location__
": unique index key on %s in %s, "
2129 "exceeds maximum key length of %u (encoded).",
2131 ldb_dn_get_linearized(msg
->dn
),
2132 ltdb
->max_key_length
);
2134 return LDB_ERR_CONSTRAINT_VIOLATION
;
2136 talloc_steal(list
, dn_key
);
2138 ret
= ltdb_dn_list_load(module
, ltdb
, dn_key
, list
);
2139 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
2145 * Check for duplicates in the @IDXDN DN -> GUID record
2147 * This is very normal, it just means a duplicate DN creation
2148 * was attempted, so don't set the error string or print scary
2151 if (list
->count
> 0 &&
2152 ldb_attr_cmp(el
->name
, LTDB_IDXDN
) == 0 &&
2153 truncation
== KEY_NOT_TRUNCATED
) {
2156 return LDB_ERR_CONSTRAINT_VIOLATION
;
2158 } else if (list
->count
> 0
2159 && ldb_attr_cmp(el
->name
, LTDB_IDXDN
) == 0) {
2162 * At least one existing entry in the DN->GUID index, which
2163 * arises when the DN indexes have been truncated
2165 * So need to pull the DN's to check if it's really a duplicate
2168 for (i
=0; i
< list
->count
; i
++) {
2169 uint8_t guid_key
[LTDB_GUID_KEY_SIZE
];
2172 .dsize
= sizeof(guid_key
)
2174 const int flags
= LDB_UNPACK_DATA_FLAG_NO_ATTRS
;
2175 struct ldb_message
*rec
= ldb_msg_new(ldb
);
2177 return LDB_ERR_OPERATIONS_ERROR
;
2180 ret
= ltdb_idx_to_key(module
, ltdb
,
2183 if (ret
!= LDB_SUCCESS
) {
2189 ret
= ltdb_search_key(module
, ltdb
, key
,
2191 if (key
.dptr
!= guid_key
) {
2192 TALLOC_FREE(key
.dptr
);
2194 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
2196 * the record has disappeared?
2197 * yes, this can happen
2203 if (ret
!= LDB_SUCCESS
) {
2204 /* an internal error */
2207 return LDB_ERR_OPERATIONS_ERROR
;
2210 * The DN we are trying to add to the DB and index
2211 * is already here, so we must deny the addition
2213 if (ldb_dn_compare(msg
->dn
, rec
->dn
) == 0) {
2216 return LDB_ERR_CONSTRAINT_VIOLATION
;
2222 * Check for duplicates in unique indexes
2224 * We don't need to do a loop test like the @IDXDN case
2225 * above as we have a ban on long unique index values
2226 * at the start of this function.
2228 if (list
->count
> 0 &&
2230 && (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
||
2231 (el
->flags
& LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX
))))) {
2233 * We do not want to print info about a possibly
2234 * confidential DN that the conflict was with in the
2235 * user-visible error string
2238 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
2239 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2241 ": unique index violation on %s in %s, "
2242 "conficts with %*.*s in %s",
2243 el
->name
, ldb_dn_get_linearized(msg
->dn
),
2244 (int)list
->dn
[0].length
,
2245 (int)list
->dn
[0].length
,
2247 ldb_dn_get_linearized(dn_key
));
2249 /* This can't fail, gives a default at worst */
2250 const struct ldb_schema_attribute
*attr
2251 = ldb_schema_attribute_by_name(
2253 ltdb
->cache
->GUID_index_attribute
);
2255 ret
= attr
->syntax
->ldif_write_fn(ldb
, list
,
2257 if (ret
== LDB_SUCCESS
) {
2258 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2260 ": unique index violation on %s in "
2261 "%s, conficts with %s %*.*s in %s",
2263 ldb_dn_get_linearized(msg
->dn
),
2264 ltdb
->cache
->GUID_index_attribute
,
2268 ldb_dn_get_linearized(dn_key
));
2271 ldb_asprintf_errstring(ldb
,
2272 __location__
": unique index violation "
2275 ldb_dn_get_linearized(msg
->dn
));
2277 return LDB_ERR_CONSTRAINT_VIOLATION
;
2280 /* overallocate the list a bit, to reduce the number of
2281 * realloc trigered copies */
2282 alloc_len
= ((list
->count
+1)+7) & ~7;
2283 list
->dn
= talloc_realloc(list
, list
->dn
, struct ldb_val
, alloc_len
);
2284 if (list
->dn
== NULL
) {
2286 return LDB_ERR_OPERATIONS_ERROR
;
2289 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
2290 const char *dn_str
= ldb_dn_get_linearized(msg
->dn
);
2291 list
->dn
[list
->count
].data
2292 = (uint8_t *)talloc_strdup(list
->dn
, dn_str
);
2293 if (list
->dn
[list
->count
].data
== NULL
) {
2295 return LDB_ERR_OPERATIONS_ERROR
;
2297 list
->dn
[list
->count
].length
= strlen(dn_str
);
2299 const struct ldb_val
*key_val
;
2300 struct ldb_val
*exact
= NULL
, *next
= NULL
;
2301 key_val
= ldb_msg_find_ldb_val(msg
,
2302 ltdb
->cache
->GUID_index_attribute
);
2303 if (key_val
== NULL
) {
2305 return ldb_module_operr(module
);
2308 if (key_val
->length
!= LTDB_GUID_SIZE
) {
2310 return ldb_module_operr(module
);
2313 BINARY_ARRAY_SEARCH_GTE(list
->dn
, list
->count
,
2314 *key_val
, ldb_val_equal_exact_ordered
,
2318 * Give a warning rather than fail, this could be a
2319 * duplicate value in the record allowed by a caller
2320 * forcing in the value with
2321 * LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK
2323 if (exact
!= NULL
&& truncation
== KEY_NOT_TRUNCATED
) {
2324 /* This can't fail, gives a default at worst */
2325 const struct ldb_schema_attribute
*attr
2326 = ldb_schema_attribute_by_name(
2328 ltdb
->cache
->GUID_index_attribute
);
2330 ret
= attr
->syntax
->ldif_write_fn(ldb
, list
,
2332 if (ret
== LDB_SUCCESS
) {
2333 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2335 ": duplicate attribute value in %s "
2337 "duplicate of %s %*.*s in %s",
2338 ldb_dn_get_linearized(msg
->dn
),
2340 ltdb
->cache
->GUID_index_attribute
,
2344 ldb_dn_get_linearized(dn_key
));
2349 next
= &list
->dn
[list
->count
];
2351 memmove(&next
[1], next
,
2352 sizeof(*next
) * (list
->count
- (next
- list
->dn
)));
2354 *next
= ldb_val_dup(list
->dn
, key_val
);
2355 if (next
->data
== NULL
) {
2357 return ldb_module_operr(module
);
2362 ret
= ltdb_dn_list_store(module
, dn_key
, list
);
2370 add index entries for one elements in a message
2372 static int ltdb_index_add_el(struct ldb_module
*module
,
2373 struct ltdb_private
*ltdb
,
2374 const struct ldb_message
*msg
,
2375 struct ldb_message_element
*el
)
2378 for (i
= 0; i
< el
->num_values
; i
++) {
2379 int ret
= ltdb_index_add1(module
, ltdb
,
2381 if (ret
!= LDB_SUCCESS
) {
2390 add index entries for all elements in a message
2392 static int ltdb_index_add_all(struct ldb_module
*module
,
2393 struct ltdb_private
*ltdb
,
2394 const struct ldb_message
*msg
)
2396 struct ldb_message_element
*elements
= msg
->elements
;
2401 if (ldb_dn_is_special(msg
->dn
)) {
2405 dn_str
= ldb_dn_get_linearized(msg
->dn
);
2406 if (dn_str
== NULL
) {
2407 return LDB_ERR_OPERATIONS_ERROR
;
2410 ret
= ltdb_write_index_dn_guid(module
, msg
, 1);
2411 if (ret
!= LDB_SUCCESS
) {
2415 if (!ltdb
->cache
->attribute_indexes
) {
2416 /* no indexed fields */
2420 for (i
= 0; i
< msg
->num_elements
; i
++) {
2421 if (!ltdb_is_indexed(module
, ltdb
, elements
[i
].name
)) {
2424 ret
= ltdb_index_add_el(module
, ltdb
,
2426 if (ret
!= LDB_SUCCESS
) {
2427 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2428 ldb_asprintf_errstring(ldb
,
2429 __location__
": Failed to re-index %s in %s - %s",
2430 elements
[i
].name
, dn_str
,
2431 ldb_errstring(ldb
));
2441 insert a DN index for a message
2443 static int ltdb_modify_index_dn(struct ldb_module
*module
,
2444 struct ltdb_private
*ltdb
,
2445 const struct ldb_message
*msg
,
2447 const char *index
, int add
)
2449 struct ldb_message_element el
;
2453 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn
));
2454 if (val
.data
== NULL
) {
2455 const char *dn_str
= ldb_dn_get_linearized(dn
);
2456 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
2458 ": Failed to modify %s "
2459 "against %s in %s: failed "
2460 "to get casefold DN",
2462 ltdb
->cache
->GUID_index_attribute
,
2464 return LDB_ERR_OPERATIONS_ERROR
;
2467 val
.length
= strlen((char *)val
.data
);
2473 ret
= ltdb_index_add1(module
, ltdb
, msg
, &el
, 0);
2474 } else { /* delete */
2475 ret
= ltdb_index_del_value(module
, ltdb
, msg
, &el
, 0);
2478 if (ret
!= LDB_SUCCESS
) {
2479 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
2480 const char *dn_str
= ldb_dn_get_linearized(dn
);
2481 ldb_asprintf_errstring(ldb
,
2483 ": Failed to modify %s "
2484 "against %s in %s - %s",
2486 ltdb
->cache
->GUID_index_attribute
,
2487 dn_str
, ldb_errstring(ldb
));
2494 insert a one level index for a message
2496 static int ltdb_index_onelevel(struct ldb_module
*module
,
2497 const struct ldb_message
*msg
, int add
)
2499 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
),
2500 struct ltdb_private
);
2504 /* We index for ONE Level only if requested */
2505 if (!ltdb
->cache
->one_level_indexes
) {
2509 pdn
= ldb_dn_get_parent(module
, msg
->dn
);
2511 return LDB_ERR_OPERATIONS_ERROR
;
2513 ret
= ltdb_modify_index_dn(module
, ltdb
,
2514 msg
, pdn
, LTDB_IDXONE
, add
);
2522 insert a one level index for a message
2524 static int ltdb_write_index_dn_guid(struct ldb_module
*module
,
2525 const struct ldb_message
*msg
,
2529 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
),
2530 struct ltdb_private
);
2532 /* We index for DN only if using a GUID index */
2533 if (ltdb
->cache
->GUID_index_attribute
== NULL
) {
2537 ret
= ltdb_modify_index_dn(module
, ltdb
, msg
, msg
->dn
,
2540 if (ret
== LDB_ERR_CONSTRAINT_VIOLATION
) {
2541 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
2542 "Entry %s already exists",
2543 ldb_dn_get_linearized(msg
->dn
));
2544 ret
= LDB_ERR_ENTRY_ALREADY_EXISTS
;
2550 add the index entries for a new element in a record
2551 The caller guarantees that these element values are not yet indexed
2553 int ltdb_index_add_element(struct ldb_module
*module
,
2554 struct ltdb_private
*ltdb
,
2555 const struct ldb_message
*msg
,
2556 struct ldb_message_element
*el
)
2558 if (ldb_dn_is_special(msg
->dn
)) {
2561 if (!ltdb_is_indexed(module
, ltdb
, el
->name
)) {
2564 return ltdb_index_add_el(module
, ltdb
, msg
, el
);
2568 add the index entries for a new record
2570 int ltdb_index_add_new(struct ldb_module
*module
,
2571 struct ltdb_private
*ltdb
,
2572 const struct ldb_message
*msg
)
2576 if (ldb_dn_is_special(msg
->dn
)) {
2580 ret
= ltdb_index_add_all(module
, ltdb
, msg
);
2581 if (ret
!= LDB_SUCCESS
) {
2583 * Because we can't trust the caller to be doing
2584 * transactions properly, clean up any index for this
2585 * entry rather than relying on a transaction
2589 ltdb_index_delete(module
, msg
);
2593 ret
= ltdb_index_onelevel(module
, msg
, 1);
2594 if (ret
!= LDB_SUCCESS
) {
2596 * Because we can't trust the caller to be doing
2597 * transactions properly, clean up any index for this
2598 * entry rather than relying on a transaction
2601 ltdb_index_delete(module
, msg
);
2609 delete an index entry for one message element
2611 int ltdb_index_del_value(struct ldb_module
*module
,
2612 struct ltdb_private
*ltdb
,
2613 const struct ldb_message
*msg
,
2614 struct ldb_message_element
*el
, unsigned int v_idx
)
2616 struct ldb_context
*ldb
;
2617 struct ldb_dn
*dn_key
;
2621 struct dn_list
*list
;
2622 struct ldb_dn
*dn
= msg
->dn
;
2623 enum key_truncation truncation
= KEY_NOT_TRUNCATED
;
2625 ldb
= ldb_module_get_ctx(module
);
2627 dn_str
= ldb_dn_get_linearized(dn
);
2628 if (dn_str
== NULL
) {
2629 return LDB_ERR_OPERATIONS_ERROR
;
2632 if (dn_str
[0] == '@') {
2636 dn_key
= ltdb_index_key(ldb
, ltdb
,
2637 el
->name
, &el
->values
[v_idx
],
2640 * We ignore key truncation in ltdb_index_add1() so
2641 * match that by ignoring it here as well
2643 * Multiple values are legitimate and accepted
2646 return LDB_ERR_OPERATIONS_ERROR
;
2649 list
= talloc_zero(dn_key
, struct dn_list
);
2651 talloc_free(dn_key
);
2652 return LDB_ERR_OPERATIONS_ERROR
;
2655 ret
= ltdb_dn_list_load(module
, ltdb
, dn_key
, list
);
2656 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
2657 /* it wasn't indexed. Did we have an earlier error? If we did then
2659 talloc_free(dn_key
);
2663 if (ret
!= LDB_SUCCESS
) {
2664 talloc_free(dn_key
);
2669 * Find one of the values matching this message to remove
2671 i
= ltdb_dn_list_find_msg(ltdb
, list
, msg
);
2673 /* nothing to delete */
2674 talloc_free(dn_key
);
2678 j
= (unsigned int) i
;
2679 if (j
!= list
->count
- 1) {
2680 memmove(&list
->dn
[j
], &list
->dn
[j
+1], sizeof(list
->dn
[0])*(list
->count
- (j
+1)));
2683 if (list
->count
== 0) {
2684 talloc_free(list
->dn
);
2687 list
->dn
= talloc_realloc(list
, list
->dn
, struct ldb_val
, list
->count
);
2690 ret
= ltdb_dn_list_store(module
, dn_key
, list
);
2692 talloc_free(dn_key
);
2698 delete the index entries for a element
2699 return -1 on failure
2701 int ltdb_index_del_element(struct ldb_module
*module
,
2702 struct ltdb_private
*ltdb
,
2703 const struct ldb_message
*msg
,
2704 struct ldb_message_element
*el
)
2710 if (!ltdb
->cache
->attribute_indexes
) {
2711 /* no indexed fields */
2715 dn_str
= ldb_dn_get_linearized(msg
->dn
);
2716 if (dn_str
== NULL
) {
2717 return LDB_ERR_OPERATIONS_ERROR
;
2720 if (dn_str
[0] == '@') {
2724 if (!ltdb_is_indexed(module
, ltdb
, el
->name
)) {
2727 for (i
= 0; i
< el
->num_values
; i
++) {
2728 ret
= ltdb_index_del_value(module
, ltdb
, msg
, el
, i
);
2729 if (ret
!= LDB_SUCCESS
) {
2738 delete the index entries for a record
2739 return -1 on failure
2741 int ltdb_index_delete(struct ldb_module
*module
, const struct ldb_message
*msg
)
2743 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
2747 if (ldb_dn_is_special(msg
->dn
)) {
2751 ret
= ltdb_index_onelevel(module
, msg
, 0);
2752 if (ret
!= LDB_SUCCESS
) {
2756 ret
= ltdb_write_index_dn_guid(module
, msg
, 0);
2757 if (ret
!= LDB_SUCCESS
) {
2761 if (!ltdb
->cache
->attribute_indexes
) {
2762 /* no indexed fields */
2766 for (i
= 0; i
< msg
->num_elements
; i
++) {
2767 ret
= ltdb_index_del_element(module
, ltdb
,
2768 msg
, &msg
->elements
[i
]);
2769 if (ret
!= LDB_SUCCESS
) {
2779 traversal function that deletes all @INDEX records in the in-memory
2782 This does not touch the actual DB, that is done at transaction
2783 commit, which in turn greatly reduces DB churn as we will likely
2784 be able to do a direct update into the old record.
2786 static int delete_index(struct ltdb_private
*ltdb
, struct ldb_val key
, struct ldb_val data
, void *state
)
2788 struct ldb_module
*module
= state
;
2789 const char *dnstr
= "DN=" LTDB_INDEX
":";
2790 struct dn_list list
;
2795 if (strncmp((char *)key
.data
, dnstr
, strlen(dnstr
)) != 0) {
2798 /* we need to put a empty list in the internal tdb for this
2803 /* the offset of 3 is to remove the DN= prefix. */
2804 v
.data
= key
.data
+ 3;
2805 v
.length
= strnlen((char *)key
.data
, key
.length
) - 3;
2807 dn
= ldb_dn_from_ldb_val(ltdb
, ldb_module_get_ctx(module
), &v
);
2810 * This does not actually touch the DB quite yet, just
2811 * the in-memory index cache
2813 ret
= ltdb_dn_list_store(module
, dn
, &list
);
2814 if (ret
!= LDB_SUCCESS
) {
2815 ldb_asprintf_errstring(ldb_module_get_ctx(module
),
2816 "Unable to store null index for %s\n",
2817 ldb_dn_get_linearized(dn
));
2826 traversal function that adds @INDEX records during a re index TODO wrong comment
2828 static int re_key(struct ltdb_private
*ltdb
, struct ldb_val ldb_key
, struct ldb_val val
, void *state
)
2830 struct ldb_context
*ldb
;
2831 struct ltdb_reindex_context
*ctx
= (struct ltdb_reindex_context
*)state
;
2832 struct ldb_module
*module
= ctx
->module
;
2833 struct ldb_message
*msg
;
2834 unsigned int nb_elements_in_db
;
2839 .dptr
= ldb_key
.data
,
2840 .dsize
= ldb_key
.length
2843 ldb
= ldb_module_get_ctx(module
);
2845 if (key
.dsize
> 4 &&
2846 memcmp(key
.dptr
, "DN=@", 4) == 0) {
2850 is_record
= ltdb_key_is_record(key
);
2851 if (is_record
== false) {
2855 msg
= ldb_msg_new(module
);
2860 ret
= ldb_unpack_data_only_attr_list_flags(ldb
, &val
,
2863 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
,
2864 &nb_elements_in_db
);
2866 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid data for index %s\n",
2867 ldb_dn_get_linearized(msg
->dn
));
2873 if (msg
->dn
== NULL
) {
2874 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2875 "Refusing to re-index as GUID "
2876 "key %*.*s with no DN\n",
2877 (int)key
.dsize
, (int)key
.dsize
,
2883 /* check if the DN key has changed, perhaps due to the case
2884 insensitivity of an element changing, or a change from DN
2886 key2
= ltdb_key_msg(module
, msg
, msg
);
2887 if (key2
.dptr
== NULL
) {
2888 /* probably a corrupt record ... darn */
2889 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid DN in re_index: %s",
2890 ldb_dn_get_linearized(msg
->dn
));
2894 if (key
.dsize
!= key2
.dsize
||
2895 (memcmp(key
.dptr
, key2
.dptr
, key
.dsize
) != 0)) {
2896 struct ldb_val ldb_key2
= {
2898 .length
= key2
.dsize
2900 ltdb
->kv_ops
->update_in_iterate(ltdb
, ldb_key
, ldb_key2
, val
, ctx
);
2902 talloc_free(key2
.dptr
);
2907 if (ctx
->count
% 10000 == 0) {
2908 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2909 "Reindexing: re-keyed %u records so far",
2917 traversal function that adds @INDEX records during a re index
2919 static int re_index(struct ltdb_private
*ltdb
, struct ldb_val ldb_key
, struct ldb_val val
, void *state
)
2921 struct ldb_context
*ldb
;
2922 struct ltdb_reindex_context
*ctx
= (struct ltdb_reindex_context
*)state
;
2923 struct ldb_module
*module
= ctx
->module
;
2924 struct ldb_message
*msg
;
2925 unsigned int nb_elements_in_db
;
2927 .dptr
= ldb_key
.data
,
2928 .dsize
= ldb_key
.length
2933 ldb
= ldb_module_get_ctx(module
);
2935 if (key
.dsize
> 4 &&
2936 memcmp(key
.dptr
, "DN=@", 4) == 0) {
2940 is_record
= ltdb_key_is_record(key
);
2941 if (is_record
== false) {
2945 msg
= ldb_msg_new(module
);
2950 ret
= ldb_unpack_data_only_attr_list_flags(ldb
, &val
,
2953 LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
,
2954 &nb_elements_in_db
);
2956 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid data for index %s\n",
2957 ldb_dn_get_linearized(msg
->dn
));
2963 if (msg
->dn
== NULL
) {
2964 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2965 "Refusing to re-index as GUID "
2966 "key %*.*s with no DN\n",
2967 (int)key
.dsize
, (int)key
.dsize
,
2973 ret
= ltdb_index_onelevel(module
, msg
, 1);
2974 if (ret
!= LDB_SUCCESS
) {
2975 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
2976 "Adding special ONE LEVEL index failed (%s)!",
2977 ldb_dn_get_linearized(msg
->dn
));
2982 ret
= ltdb_index_add_all(module
, ltdb
, msg
);
2984 if (ret
!= LDB_SUCCESS
) {
2993 if (ctx
->count
% 10000 == 0) {
2994 ldb_debug(ldb
, LDB_DEBUG_WARNING
,
2995 "Reindexing: re-indexed %u records so far",
3003 force a complete reindex of the database
3005 int ltdb_reindex(struct ldb_module
*module
)
3007 struct ltdb_private
*ltdb
= talloc_get_type(ldb_module_get_private(module
), struct ltdb_private
);
3009 struct ltdb_reindex_context ctx
;
3012 * Only triggered after a modification, but make clear we do
3013 * not re-index a read-only DB
3015 if (ltdb
->read_only
) {
3016 return LDB_ERR_UNWILLING_TO_PERFORM
;
3019 if (ltdb_cache_reload(module
) != 0) {
3020 return LDB_ERR_OPERATIONS_ERROR
;
3024 * Ensure we read (and so remove) the entries from the real
3025 * DB, no values stored so far are any use as we want to do a
3028 ltdb_index_transaction_cancel(module
);
3030 ret
= ltdb_index_transaction_start(module
);
3031 if (ret
!= LDB_SUCCESS
) {
3035 /* first traverse the database deleting any @INDEX records by
3036 * putting NULL entries in the in-memory tdb
3038 ret
= ltdb
->kv_ops
->iterate(ltdb
, delete_index
, module
);
3040 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
3041 ldb_asprintf_errstring(ldb
, "index deletion traverse failed: %s",
3042 ldb_errstring(ldb
));
3043 return LDB_ERR_OPERATIONS_ERROR
;
3046 ctx
.module
= module
;
3050 ret
= ltdb
->kv_ops
->iterate(ltdb
, re_key
, &ctx
);
3052 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
3053 ldb_asprintf_errstring(ldb
, "key correction traverse failed: %s",
3054 ldb_errstring(ldb
));
3055 return LDB_ERR_OPERATIONS_ERROR
;
3058 if (ctx
.error
!= LDB_SUCCESS
) {
3059 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
3060 ldb_asprintf_errstring(ldb
, "reindexing failed: %s", ldb_errstring(ldb
));
3067 /* now traverse adding any indexes for normal LDB records */
3068 ret
= ltdb
->kv_ops
->iterate(ltdb
, re_index
, &ctx
);
3070 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
3071 ldb_asprintf_errstring(ldb
, "reindexing traverse failed: %s",
3072 ldb_errstring(ldb
));
3073 return LDB_ERR_OPERATIONS_ERROR
;
3076 if (ctx
.error
!= LDB_SUCCESS
) {
3077 struct ldb_context
*ldb
= ldb_module_get_ctx(module
);
3078 ldb_asprintf_errstring(ldb
, "reindexing failed: %s", ldb_errstring(ldb
));
3082 if (ctx
.count
> 10000) {
3083 ldb_debug(ldb_module_get_ctx(module
),
3084 LDB_DEBUG_WARNING
, "Reindexing: re_index successful on %s, "
3085 "final index write-out will be in transaction commit",
3086 ltdb
->kv_ops
->name(ltdb
));