Line data Source code
1 : /*
2 : ldb database library
3 :
4 : Copyright (C) Andrew Tridgell 2004-2009
5 :
6 : ** NOTE! The following LGPL license applies to the ldb
7 : ** library. This does NOT imply that all of Samba is released
8 : ** under the LGPL
9 :
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.
14 :
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.
19 :
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/>.
22 : */
23 :
24 : /*
25 : * Name: ldb
26 : *
27 : * Component: ldb key value backend - indexing
28 : *
29 : * Description: indexing routines for ldb key value backend
30 : *
31 : * Author: Andrew Tridgell
32 : */
33 :
34 : /*
35 :
36 : LDB Index design and choice of key:
37 : =======================================
38 :
39 : LDB has index records held as LDB objects with a special record like:
40 :
41 : dn: @INDEX:attr:value
42 :
43 : value may be base64 encoded, if it is deemed not printable:
44 :
45 : dn: @INDEX:attr::base64-value
46 :
47 : In each record, there is two possible formats:
48 :
49 : The original format is:
50 : -----------------------
51 :
52 : dn: @INDEX:NAME:DNSUPDATEPROXY
53 : @IDXVERSION: 2
54 : @IDX: CN=DnsUpdateProxy,CN=Users,DC=addom,DC=samba,DC=example,DC=com
55 :
56 : In this format, @IDX is multi-valued, one entry for each match
57 :
58 : The corresponding entry is stored in a TDB record with key:
59 :
60 : DN=CN=DNSUPDATEPROXY,CN=USERS,DC=ADDOM,DC=SAMBA,DC=EXAMPLE,DC=COM
61 :
62 : (This allows a scope BASE search to directly find the record via
63 : a simple casefold of the DN).
64 :
65 : The original mixed-case DN is stored in the entry itself.
66 :
67 :
68 : The new 'GUID index' format is:
69 : -------------------------------
70 :
71 : dn: @INDEX:NAME:DNSUPDATEPROXY
72 : @IDXVERSION: 3
73 : @IDX: <binary GUID>[<binary GUID>[...]]
74 :
75 : The binary guid is 16 bytes, as bytes and not expanded as hexadecimal
76 : or pretty-printed. The GUID is chosen from the message to be stored
77 : by the @IDXGUID attribute on @INDEXLIST.
78 :
79 : If there are multiple values the @IDX value simply becomes longer,
80 : in multiples of 16.
81 :
82 : The corresponding entry is stored in a TDB record with key:
83 :
84 : GUID=<binary GUID>
85 :
86 : This allows a very quick translation between the fixed-length index
87 : values and the TDB key, while separating entries from other data
88 : in the TDB, should they be unlucky enough to start with the bytes of
89 : the 'DN=' prefix.
90 :
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
94 :
95 : Exception for special @ DNs:
96 :
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.
100 :
101 :
102 : Control points for choice of index mode
103 : ---------------------------------------
104 :
105 : The choice of index and TDB key mode is made based (for example, from
106 : Samba) on entries in the @INDEXLIST DN:
107 :
108 : dn: @INDEXLIST
109 : @IDXGUID: objectGUID
110 : @IDX_DN_GUID: GUID
111 :
112 : By default, the original DN format is used.
113 :
114 :
115 : Control points for choosing indexed attributes
116 : ----------------------------------------------
117 :
118 : @IDXATTR controls if an attribute is indexed
119 :
120 : dn: @INDEXLIST
121 : @IDXATTR: samAccountName
122 : @IDXATTR: nETBIOSName
123 :
124 :
125 : C Override functions
126 : --------------------
127 :
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)
131 :
132 : This is used, particularly in combination with the below, instead of
133 : the @IDXGUID and @IDX_DN_GUID values in @INDEXLIST.
134 :
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,
139 : void *private_data);
140 :
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.
144 :
145 : */
146 :
147 : #include "ldb_kv.h"
148 : #include "../ldb_tdb/ldb_tdb.h"
149 : #include "ldb_private.h"
150 : #include "lib/util/binsearch.h"
151 : #include "lib/util/attr.h"
152 :
153 : struct dn_list {
154 : unsigned int count;
155 : struct ldb_val *dn;
156 : /*
157 : * Do not optimise the intersection of this list,
158 : * we must never return an entry not in this
159 : * list. This allows the index for
160 : * SCOPE_ONELEVEL to be trusted.
161 : */
162 : bool strict;
163 : };
164 :
165 : struct ldb_kv_idxptr {
166 : /*
167 : * In memory tdb to cache the index updates performed during a
168 : * transaction. This improves the performance of operations like
169 : * re-index and join
170 : */
171 : struct tdb_context *itdb;
172 : int error;
173 : };
174 :
175 : enum key_truncation {
176 : KEY_NOT_TRUNCATED,
177 : KEY_TRUNCATED,
178 : };
179 :
180 : static int ldb_kv_write_index_dn_guid(struct ldb_module *module,
181 : const struct ldb_message *msg,
182 : int add);
183 : static int ldb_kv_index_dn_base_dn(struct ldb_module *module,
184 : struct ldb_kv_private *ldb_kv,
185 : struct ldb_dn *base_dn,
186 : struct dn_list *dn_list,
187 : enum key_truncation *truncation);
188 :
189 : static void ldb_kv_dn_list_sort(struct ldb_kv_private *ldb_kv,
190 : struct dn_list *list);
191 :
192 : /* we put a @IDXVERSION attribute on index entries. This
193 : allows us to tell if it was written by an older version
194 : */
195 : #define LDB_KV_INDEXING_VERSION 2
196 :
197 : #define LDB_KV_GUID_INDEXING_VERSION 3
198 :
199 151915777 : static unsigned ldb_kv_max_key_length(struct ldb_kv_private *ldb_kv)
200 : {
201 151915777 : if (ldb_kv->max_key_length == 0) {
202 94263847 : return UINT_MAX;
203 : }
204 55447618 : return ldb_kv->max_key_length;
205 : }
206 :
207 : /* enable the idxptr mode when transactions start */
208 2193400 : int ldb_kv_index_transaction_start(
209 : struct ldb_module *module,
210 : size_t cache_size)
211 : {
212 2193400 : struct ldb_kv_private *ldb_kv = talloc_get_type(
213 : ldb_module_get_private(module), struct ldb_kv_private);
214 2193400 : ldb_kv->idxptr = talloc_zero(ldb_kv, struct ldb_kv_idxptr);
215 2193400 : if (ldb_kv->idxptr == NULL) {
216 0 : return ldb_oom(ldb_module_get_ctx(module));
217 : }
218 :
219 2193400 : ldb_kv->idxptr->itdb = tdb_open(
220 : NULL,
221 : cache_size,
222 : TDB_INTERNAL,
223 : O_RDWR,
224 : 0);
225 2193400 : if (ldb_kv->idxptr->itdb == NULL) {
226 0 : return LDB_ERR_OPERATIONS_ERROR;
227 : }
228 :
229 2173774 : return LDB_SUCCESS;
230 : }
231 :
232 : /*
233 : see if two ldb_val structures contain exactly the same data
234 : return -1 or 1 for a mismatch, 0 for match
235 : */
236 4874414 : static int ldb_val_equal_exact_for_qsort(const struct ldb_val *v1,
237 : const struct ldb_val *v2)
238 : {
239 4874414 : if (v1->length > v2->length) {
240 138479 : return -1;
241 : }
242 4622397 : if (v1->length < v2->length) {
243 93693 : return 1;
244 : }
245 4441762 : return memcmp(v1->data, v2->data, v1->length);
246 : }
247 :
248 : /*
249 : see if two ldb_val structures contain exactly the same data
250 : return -1 or 1 for a mismatch, 0 for match
251 : */
252 184797842 : static int ldb_val_equal_exact_ordered(const struct ldb_val v1,
253 : const struct ldb_val *v2)
254 : {
255 184797842 : if (v1.length > v2->length) {
256 36530 : return -1;
257 : }
258 184730010 : if (v1.length < v2->length) {
259 1388 : return 1;
260 : }
261 184728488 : return memcmp(v1.data, v2->data, v1.length);
262 : }
263 :
264 :
265 : /*
266 : find a entry in a dn_list, using a ldb_val. Uses a case sensitive
267 : binary-safe comparison for the 'dn' returns -1 if not found
268 :
269 : This is therefore safe when the value is a GUID in the future
270 : */
271 5105514 : static int ldb_kv_dn_list_find_val(struct ldb_kv_private *ldb_kv,
272 : const struct dn_list *list,
273 : const struct ldb_val *v)
274 : {
275 85000 : unsigned int i;
276 5105514 : struct ldb_val *exact = NULL, *next = NULL;
277 :
278 5105514 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
279 20167 : for (i=0; i<list->count; i++) {
280 19523 : if (ldb_val_equal_exact(&list->dn[i], v) == 1) {
281 3297 : return i;
282 : }
283 : }
284 640 : return -1;
285 : }
286 :
287 29279567 : BINARY_ARRAY_SEARCH_GTE(list->dn, list->count,
288 : *v, ldb_val_equal_exact_ordered,
289 : exact, next);
290 5101573 : if (exact == NULL) {
291 416638 : return -1;
292 : }
293 : /* Not required, but keeps the compiler quiet */
294 4684935 : if (next != NULL) {
295 0 : return -1;
296 : }
297 :
298 4684935 : i = exact - list->dn;
299 4684935 : return i;
300 : }
301 :
302 : /*
303 : find a entry in a dn_list. Uses a case sensitive comparison with the dn
304 : returns -1 if not found
305 : */
306 1773925 : static int ldb_kv_dn_list_find_msg(struct ldb_kv_private *ldb_kv,
307 : struct dn_list *list,
308 : const struct ldb_message *msg)
309 : {
310 18105 : struct ldb_val v;
311 18105 : const struct ldb_val *key_val;
312 1773925 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
313 2738 : const char *dn_str = ldb_dn_get_linearized(msg->dn);
314 2738 : v.data = discard_const_p(unsigned char, dn_str);
315 2738 : v.length = strlen(dn_str);
316 : } else {
317 1771187 : key_val = ldb_msg_find_ldb_val(
318 1753364 : msg, ldb_kv->cache->GUID_index_attribute);
319 1771187 : if (key_val == NULL) {
320 0 : return -1;
321 : }
322 1771187 : v = *key_val;
323 : }
324 1773925 : return ldb_kv_dn_list_find_val(ldb_kv, list, &v);
325 : }
326 :
327 : /*
328 : this is effectively a cast function, but with lots of paranoia
329 : checks and also copes with CPUs that are fussy about pointer
330 : alignment
331 : */
332 68870303 : static struct dn_list *ldb_kv_index_idxptr(struct ldb_module *module,
333 : TDB_DATA rec)
334 : {
335 5289755 : struct dn_list *list;
336 68870303 : if (rec.dsize != sizeof(void *)) {
337 0 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
338 0 : "Bad data size for idxptr %u", (unsigned)rec.dsize);
339 0 : return NULL;
340 : }
341 : /* note that we can't just use a cast here, as rec.dptr may
342 : not be aligned sufficiently for a pointer. A cast would cause
343 : platforms like some ARM CPUs to crash */
344 68870303 : memcpy(&list, rec.dptr, sizeof(void *));
345 68870303 : list = talloc_get_type(list, struct dn_list);
346 68870303 : if (list == NULL) {
347 0 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
348 : "Bad type '%s' for idxptr",
349 : talloc_get_name(list));
350 0 : return NULL;
351 : }
352 63580548 : return list;
353 : }
354 :
355 : enum dn_list_will_be_read_only {
356 : DN_LIST_MUTABLE = 0,
357 : DN_LIST_WILL_BE_READ_ONLY = 1,
358 : };
359 :
360 : /*
361 : return the @IDX list in an index entry for a dn as a
362 : struct dn_list
363 : */
364 151910061 : static int ldb_kv_dn_list_load(struct ldb_module *module,
365 : struct ldb_kv_private *ldb_kv,
366 : struct ldb_dn *dn,
367 : struct dn_list *list,
368 : enum dn_list_will_be_read_only read_only)
369 : {
370 6249985 : struct ldb_message *msg;
371 6249985 : int ret, version;
372 6249985 : struct ldb_message_element *el;
373 151910061 : TDB_DATA rec = {0};
374 6249985 : struct dn_list *list2;
375 151910061 : bool from_primary_cache = false;
376 151910061 : TDB_DATA key = {0};
377 :
378 151910061 : list->dn = NULL;
379 151910061 : list->count = 0;
380 151910061 : list->strict = false;
381 :
382 : /*
383 : * See if we have an in memory index cache
384 : */
385 151910061 : if (ldb_kv->idxptr == NULL) {
386 71906869 : goto normal_index;
387 : }
388 :
389 80003192 : key.dptr = discard_const_p(unsigned char, ldb_dn_get_linearized(dn));
390 80003192 : key.dsize = strlen((char *)key.dptr);
391 :
392 : /*
393 : * Have we cached this index record?
394 : * If we have a nested transaction cache try that first.
395 : * then try the transaction cache.
396 : * if the record is not cached it will need to be read from disk.
397 : */
398 80003192 : if (ldb_kv->nested_idx_ptr != NULL) {
399 10833500 : rec = tdb_fetch(ldb_kv->nested_idx_ptr->itdb, key);
400 : }
401 80003192 : if (rec.dptr == NULL) {
402 79139500 : from_primary_cache = true;
403 79139500 : rec = tdb_fetch(ldb_kv->idxptr->itdb, key);
404 : }
405 80003192 : if (rec.dptr == NULL) {
406 48984715 : goto normal_index;
407 : }
408 :
409 : /* we've found an in-memory index entry */
410 31018477 : list2 = ldb_kv_index_idxptr(module, rec);
411 31018477 : if (list2 == NULL) {
412 0 : free(rec.dptr);
413 0 : return LDB_ERR_OPERATIONS_ERROR;
414 : }
415 31018477 : free(rec.dptr);
416 :
417 : /*
418 : * If this is a read only transaction the indexes will not be
419 : * changed so we don't need a copy in the event of a rollback
420 : *
421 : * In this case make an early return
422 : */
423 31018477 : if (read_only == DN_LIST_WILL_BE_READ_ONLY) {
424 13129939 : *list = *list2;
425 13129939 : return LDB_SUCCESS;
426 : }
427 :
428 : /*
429 : * record was read from the sub transaction cache, so we have
430 : * already copied the primary cache record
431 : */
432 17888538 : if (!from_primary_cache) {
433 863692 : *list = *list2;
434 863692 : return LDB_SUCCESS;
435 : }
436 :
437 : /*
438 : * No index sub transaction active, so no need to cache a copy
439 : */
440 17024846 : if (ldb_kv->nested_idx_ptr == NULL) {
441 13074835 : *list = *list2;
442 13074835 : return LDB_SUCCESS;
443 : }
444 :
445 : /*
446 : * There is an active index sub transaction, and the record was
447 : * found in the primary index transaction cache. A copy of the
448 : * record needs be taken to prevent the original entry being
449 : * altered, until the index sub transaction is committed.
450 : */
451 :
452 : {
453 3950011 : struct ldb_val *dns = NULL;
454 3950011 : size_t x = 0;
455 :
456 3950011 : dns = talloc_array(
457 : list,
458 : struct ldb_val,
459 : list2->count);
460 3950011 : if (dns == NULL) {
461 0 : return LDB_ERR_OPERATIONS_ERROR;
462 : }
463 2487477405 : for (x = 0; x < list2->count; x++) {
464 2483527394 : dns[x].length = list2->dn[x].length;
465 2483527394 : dns[x].data = talloc_memdup(
466 : dns,
467 : list2->dn[x].data,
468 : list2->dn[x].length);
469 2483527394 : if (dns[x].data == NULL) {
470 0 : TALLOC_FREE(dns);
471 0 : return LDB_ERR_OPERATIONS_ERROR;
472 : }
473 : }
474 3950011 : list->dn = dns;
475 3950011 : list->count = list2->count;
476 : }
477 3950011 : return LDB_SUCCESS;
478 :
479 : /*
480 : * Index record not found in the caches, read it from the
481 : * database.
482 : */
483 120891584 : normal_index:
484 120891584 : msg = ldb_msg_new(list);
485 120891584 : if (msg == NULL) {
486 0 : return LDB_ERR_OPERATIONS_ERROR;
487 : }
488 :
489 120891584 : ret = ldb_kv_search_dn1(module,
490 : dn,
491 : msg,
492 : LDB_UNPACK_DATA_FLAG_NO_DN |
493 : /*
494 : * The entry point ldb_kv_search_indexed is
495 : * only called from the read-locked
496 : * ldb_kv_search.
497 : */
498 : LDB_UNPACK_DATA_FLAG_READ_LOCKED);
499 120891584 : if (ret != LDB_SUCCESS) {
500 16511885 : talloc_free(msg);
501 16511885 : return ret;
502 : }
503 :
504 104379699 : el = ldb_msg_find_element(msg, LDB_KV_IDX);
505 104379699 : if (!el) {
506 0 : talloc_free(msg);
507 0 : return LDB_SUCCESS;
508 : }
509 :
510 104379699 : version = ldb_msg_find_attr_as_int(msg, LDB_KV_IDXVERSION, 0);
511 :
512 : /*
513 : * we avoid copying the strings by stealing the list. We have
514 : * to steal msg onto el->values (which looks odd) because
515 : * the memory is allocated on msg, not on each value.
516 : */
517 104379699 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
518 : /* check indexing version number */
519 249005 : if (version != LDB_KV_INDEXING_VERSION) {
520 0 : ldb_debug_set(ldb_module_get_ctx(module),
521 : LDB_DEBUG_ERROR,
522 : "Wrong DN index version %d "
523 : "expected %d for %s",
524 : version, LDB_KV_INDEXING_VERSION,
525 : ldb_dn_get_linearized(dn));
526 0 : talloc_free(msg);
527 0 : return LDB_ERR_OPERATIONS_ERROR;
528 : }
529 :
530 249005 : talloc_steal(el->values, msg);
531 249005 : list->dn = talloc_steal(list, el->values);
532 249005 : list->count = el->num_values;
533 : } else {
534 2769043 : unsigned int i;
535 104130694 : if (version != LDB_KV_GUID_INDEXING_VERSION) {
536 : /* This is quite likely during the DB startup
537 : on first upgrade to using a GUID index */
538 0 : ldb_debug_set(ldb_module_get_ctx(module),
539 : LDB_DEBUG_ERROR,
540 : "Wrong GUID index version %d "
541 : "expected %d for %s",
542 : version, LDB_KV_GUID_INDEXING_VERSION,
543 : ldb_dn_get_linearized(dn));
544 0 : talloc_free(msg);
545 0 : return LDB_ERR_OPERATIONS_ERROR;
546 : }
547 :
548 104130694 : if (el->num_values == 0) {
549 0 : talloc_free(msg);
550 0 : return LDB_ERR_OPERATIONS_ERROR;
551 : }
552 :
553 104130694 : if ((el->values[0].length % LDB_KV_GUID_SIZE) != 0) {
554 0 : talloc_free(msg);
555 0 : return LDB_ERR_OPERATIONS_ERROR;
556 : }
557 :
558 104130694 : list->count = el->values[0].length / LDB_KV_GUID_SIZE;
559 104130694 : list->dn = talloc_array(list, struct ldb_val, list->count);
560 104130694 : if (list->dn == NULL) {
561 0 : talloc_free(msg);
562 0 : return LDB_ERR_OPERATIONS_ERROR;
563 : }
564 :
565 : /*
566 : * The actual data is on msg.
567 : */
568 104130694 : talloc_steal(list->dn, msg);
569 1038114823 : for (i = 0; i < list->count; i++) {
570 931215086 : list->dn[i].data
571 931215086 : = &el->values[0].data[i * LDB_KV_GUID_SIZE];
572 931215086 : list->dn[i].length = LDB_KV_GUID_SIZE;
573 : }
574 : }
575 :
576 : /* We don't need msg->elements any more */
577 104379699 : talloc_free(msg->elements);
578 104379699 : return LDB_SUCCESS;
579 : }
580 :
581 127123694 : int ldb_kv_key_dn_from_idx(struct ldb_module *module,
582 : struct ldb_kv_private *ldb_kv,
583 : TALLOC_CTX *mem_ctx,
584 : struct ldb_dn *dn,
585 : struct ldb_val *ldb_key)
586 : {
587 127123694 : struct ldb_context *ldb = ldb_module_get_ctx(module);
588 4080736 : int ret;
589 127123694 : int index = 0;
590 127123694 : enum key_truncation truncation = KEY_NOT_TRUNCATED;
591 127123694 : struct dn_list *list = talloc(mem_ctx, struct dn_list);
592 127123694 : if (list == NULL) {
593 0 : ldb_oom(ldb);
594 0 : return LDB_ERR_OPERATIONS_ERROR;
595 : }
596 :
597 127123694 : ret = ldb_kv_index_dn_base_dn(module, ldb_kv, dn, list, &truncation);
598 127123694 : if (ret != LDB_SUCCESS) {
599 2255864 : TALLOC_FREE(list);
600 2255864 : return ret;
601 : }
602 :
603 124867830 : if (list->count == 0) {
604 0 : TALLOC_FREE(list);
605 0 : return LDB_ERR_NO_SUCH_OBJECT;
606 : }
607 :
608 124867830 : if (list->count > 1 && truncation == KEY_NOT_TRUNCATED) {
609 0 : const char *dn_str = ldb_dn_get_linearized(dn);
610 0 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
611 : __location__
612 : ": Failed to read DN index "
613 : "against %s for %s: too many "
614 : "values (%u > 1)",
615 0 : ldb_kv->cache->GUID_index_attribute,
616 : dn_str,
617 : list->count);
618 0 : TALLOC_FREE(list);
619 0 : return LDB_ERR_CONSTRAINT_VIOLATION;
620 : }
621 :
622 124867830 : if (list->count > 0 && truncation == KEY_TRUNCATED) {
623 : /*
624 : * DN key has been truncated, need to inspect the actual
625 : * records to locate the actual DN
626 : */
627 : unsigned int i;
628 152 : index = -1;
629 152 : for (i=0; i < list->count; i++) {
630 136 : uint8_t guid_key[LDB_KV_GUID_KEY_SIZE];
631 136 : struct ldb_val key = {
632 : .data = guid_key,
633 : .length = sizeof(guid_key)
634 : };
635 136 : const int flags = LDB_UNPACK_DATA_FLAG_NO_ATTRS;
636 136 : struct ldb_message *rec = ldb_msg_new(ldb);
637 136 : if (rec == NULL) {
638 0 : TALLOC_FREE(list);
639 0 : return LDB_ERR_OPERATIONS_ERROR;
640 : }
641 :
642 272 : ret = ldb_kv_idx_to_key(
643 136 : module, ldb_kv, ldb, &list->dn[i], &key);
644 136 : if (ret != LDB_SUCCESS) {
645 0 : TALLOC_FREE(list);
646 0 : TALLOC_FREE(rec);
647 0 : return ret;
648 : }
649 :
650 136 : ret =
651 136 : ldb_kv_search_key(module, ldb_kv, key, rec, flags);
652 136 : if (key.data != guid_key) {
653 0 : TALLOC_FREE(key.data);
654 : }
655 136 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
656 : /*
657 : * the record has disappeared?
658 : * yes, this can happen
659 : */
660 0 : TALLOC_FREE(rec);
661 0 : continue;
662 : }
663 :
664 136 : if (ret != LDB_SUCCESS) {
665 : /* an internal error */
666 0 : TALLOC_FREE(rec);
667 0 : TALLOC_FREE(list);
668 0 : return LDB_ERR_OPERATIONS_ERROR;
669 : }
670 :
671 : /*
672 : * We found the actual DN that we wanted from in the
673 : * multiple values that matched the index
674 : * (due to truncation), so return that.
675 : *
676 : */
677 136 : if (ldb_dn_compare(dn, rec->dn) == 0) {
678 76 : index = i;
679 76 : TALLOC_FREE(rec);
680 76 : break;
681 : }
682 : }
683 :
684 : /*
685 : * We matched the index but the actual DN we wanted
686 : * was not here.
687 : */
688 92 : if (index == -1) {
689 16 : TALLOC_FREE(list);
690 16 : return LDB_ERR_NO_SUCH_OBJECT;
691 : }
692 : }
693 :
694 : /* The ldb_key memory is allocated by the caller */
695 124867814 : ret = ldb_kv_guid_to_key(&list->dn[index], ldb_key);
696 124867814 : TALLOC_FREE(list);
697 :
698 124867814 : if (ret != LDB_SUCCESS) {
699 0 : return LDB_ERR_OPERATIONS_ERROR;
700 : }
701 :
702 121129246 : return LDB_SUCCESS;
703 : }
704 :
705 :
706 :
707 : /*
708 : save a dn_list into a full @IDX style record
709 : */
710 10452833 : static int ldb_kv_dn_list_store_full(struct ldb_module *module,
711 : struct ldb_kv_private *ldb_kv,
712 : struct ldb_dn *dn,
713 : struct dn_list *list)
714 : {
715 827385 : struct ldb_message *msg;
716 827385 : int ret;
717 :
718 10452833 : msg = ldb_msg_new(module);
719 10452833 : if (!msg) {
720 0 : return ldb_module_oom(module);
721 : }
722 :
723 10452833 : msg->dn = dn;
724 :
725 10452833 : if (list->count == 0) {
726 838121 : ret = ldb_kv_delete_noindex(module, msg);
727 838121 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
728 96638 : ret = LDB_SUCCESS;
729 : }
730 838121 : TALLOC_FREE(msg);
731 838121 : return ret;
732 : }
733 :
734 9614712 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
735 95955 : ret = ldb_msg_add_fmt(msg, LDB_KV_IDXVERSION, "%u",
736 : LDB_KV_INDEXING_VERSION);
737 95955 : if (ret != LDB_SUCCESS) {
738 0 : TALLOC_FREE(msg);
739 0 : return ldb_module_oom(module);
740 : }
741 : } else {
742 9518757 : ret = ldb_msg_add_fmt(msg, LDB_KV_IDXVERSION, "%u",
743 : LDB_KV_GUID_INDEXING_VERSION);
744 9518757 : if (ret != LDB_SUCCESS) {
745 0 : TALLOC_FREE(msg);
746 0 : return ldb_module_oom(module);
747 : }
748 : }
749 :
750 9614712 : if (list->count > 0) {
751 709511 : struct ldb_message_element *el;
752 :
753 9614712 : ret = ldb_msg_add_empty(msg, LDB_KV_IDX, LDB_FLAG_MOD_ADD, &el);
754 9614712 : if (ret != LDB_SUCCESS) {
755 0 : TALLOC_FREE(msg);
756 0 : return ldb_module_oom(module);
757 : }
758 :
759 9614712 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
760 95955 : el->values = list->dn;
761 95955 : el->num_values = list->count;
762 : } else {
763 669503 : struct ldb_val v;
764 669503 : unsigned int i;
765 9518757 : el->values = talloc_array(msg,
766 : struct ldb_val, 1);
767 9518757 : if (el->values == NULL) {
768 0 : TALLOC_FREE(msg);
769 0 : return ldb_module_oom(module);
770 : }
771 :
772 9518757 : v.data = talloc_array_size(el->values,
773 : list->count,
774 : LDB_KV_GUID_SIZE);
775 9518757 : if (v.data == NULL) {
776 0 : TALLOC_FREE(msg);
777 0 : return ldb_module_oom(module);
778 : }
779 :
780 9518757 : v.length = talloc_get_size(v.data);
781 :
782 771983372 : for (i = 0; i < list->count; i++) {
783 761795112 : if (list->dn[i].length !=
784 : LDB_KV_GUID_SIZE) {
785 0 : TALLOC_FREE(msg);
786 0 : return ldb_module_operr(module);
787 : }
788 761795112 : memcpy(&v.data[LDB_KV_GUID_SIZE*i],
789 761795112 : list->dn[i].data,
790 : LDB_KV_GUID_SIZE);
791 : }
792 9518757 : el->values[0] = v;
793 9518757 : el->num_values = 1;
794 : }
795 : }
796 :
797 9614712 : ret = ldb_kv_store(module, msg, TDB_REPLACE);
798 9614712 : TALLOC_FREE(msg);
799 9614712 : return ret;
800 : }
801 :
802 : /*
803 : save a dn_list into the database, in either @IDX or internal format
804 : */
805 31170730 : static int ldb_kv_dn_list_store(struct ldb_module *module,
806 : struct ldb_dn *dn,
807 : struct dn_list *list)
808 : {
809 31170730 : struct ldb_kv_private *ldb_kv = talloc_get_type(
810 : ldb_module_get_private(module), struct ldb_kv_private);
811 31170730 : TDB_DATA rec = {0};
812 31170730 : TDB_DATA key = {0};
813 :
814 31170730 : int ret = LDB_SUCCESS;
815 31170730 : struct dn_list *list2 = NULL;
816 31170730 : struct ldb_kv_idxptr *idxptr = NULL;
817 :
818 31170730 : key.dptr = discard_const_p(unsigned char, ldb_dn_get_linearized(dn));
819 31170730 : if (key.dptr == NULL) {
820 0 : return LDB_ERR_OPERATIONS_ERROR;
821 : }
822 31170730 : key.dsize = strlen((char *)key.dptr);
823 :
824 : /*
825 : * If there is an index sub transaction active, update the
826 : * sub transaction index cache. Otherwise update the
827 : * primary index cache
828 : */
829 31170730 : if (ldb_kv->nested_idx_ptr != NULL) {
830 9452063 : idxptr = ldb_kv->nested_idx_ptr;
831 : } else {
832 20796461 : idxptr = ldb_kv->idxptr;
833 : }
834 : /*
835 : * Get the cache entry for the index
836 : *
837 : * As the value in the cache is a pointer to a dn_list we update
838 : * the dn_list directly.
839 : *
840 : */
841 31170730 : rec = tdb_fetch(idxptr->itdb, key);
842 31170730 : if (rec.dptr != NULL) {
843 13938515 : list2 = ldb_kv_index_idxptr(module, rec);
844 13938515 : if (list2 == NULL) {
845 0 : free(rec.dptr);
846 0 : return LDB_ERR_OPERATIONS_ERROR;
847 : }
848 13938515 : free(rec.dptr);
849 : /* Now put the updated pointer back in the cache */
850 13938515 : if (list->dn == NULL) {
851 43445 : list2->dn = NULL;
852 43445 : list2->count = 0;
853 : } else {
854 13895070 : list2->dn = talloc_steal(list2, list->dn);
855 13895070 : list2->count = list->count;
856 : }
857 13938515 : return LDB_SUCCESS;
858 : }
859 :
860 17232215 : list2 = talloc(idxptr, struct dn_list);
861 17232215 : if (list2 == NULL) {
862 0 : return LDB_ERR_OPERATIONS_ERROR;
863 : }
864 17232215 : list2->dn = talloc_steal(list2, list->dn);
865 17232215 : list2->count = list->count;
866 :
867 17232215 : rec.dptr = (uint8_t *)&list2;
868 17232215 : rec.dsize = sizeof(void *);
869 :
870 :
871 : /*
872 : * This is not a store into the main DB, but into an in-memory
873 : * TDB, so we don't need a guard on ltdb->read_only
874 : *
875 : * Also as we directly update the in memory dn_list for existing
876 : * cache entries we must be adding a new entry to the cache.
877 : */
878 17232215 : ret = tdb_store(idxptr->itdb, key, rec, TDB_INSERT);
879 17232215 : if (ret != 0) {
880 0 : return ltdb_err_map( tdb_error(idxptr->itdb));
881 : }
882 15510178 : return LDB_SUCCESS;
883 : }
884 :
885 : /*
886 : traverse function for storing the in-memory index entries on disk
887 : */
888 10452833 : static int ldb_kv_index_traverse_store(_UNUSED_ struct tdb_context *tdb,
889 : TDB_DATA key,
890 : TDB_DATA data,
891 : void *state)
892 : {
893 10452833 : struct ldb_module *module = state;
894 10452833 : struct ldb_kv_private *ldb_kv = talloc_get_type(
895 : ldb_module_get_private(module), struct ldb_kv_private);
896 827385 : struct ldb_dn *dn;
897 10452833 : struct ldb_context *ldb = ldb_module_get_ctx(module);
898 827385 : struct ldb_val v;
899 827385 : struct dn_list *list;
900 :
901 10452833 : list = ldb_kv_index_idxptr(module, data);
902 10452833 : if (list == NULL) {
903 0 : ldb_kv->idxptr->error = LDB_ERR_OPERATIONS_ERROR;
904 0 : return -1;
905 : }
906 :
907 10452833 : v.data = key.dptr;
908 10452833 : v.length = strnlen((char *)key.dptr, key.dsize);
909 :
910 10452833 : dn = ldb_dn_from_ldb_val(module, ldb, &v);
911 10452833 : if (dn == NULL) {
912 0 : ldb_asprintf_errstring(ldb, "Failed to parse index key %*.*s as an LDB DN", (int)v.length, (int)v.length, (const char *)v.data);
913 0 : ldb_kv->idxptr->error = LDB_ERR_OPERATIONS_ERROR;
914 0 : return -1;
915 : }
916 :
917 20905666 : ldb_kv->idxptr->error =
918 10452833 : ldb_kv_dn_list_store_full(module, ldb_kv, dn, list);
919 10452833 : talloc_free(dn);
920 10452833 : if (ldb_kv->idxptr->error != 0) {
921 0 : return -1;
922 : }
923 9625448 : return 0;
924 : }
925 :
926 : /* cleanup the idxptr mode when transaction commits */
927 1914050 : int ldb_kv_index_transaction_commit(struct ldb_module *module)
928 : {
929 1914050 : struct ldb_kv_private *ldb_kv = talloc_get_type(
930 : ldb_module_get_private(module), struct ldb_kv_private);
931 17433 : int ret;
932 :
933 1914050 : struct ldb_context *ldb = ldb_module_get_ctx(module);
934 :
935 1914050 : ldb_reset_err_string(ldb);
936 :
937 1914050 : if (ldb_kv->idxptr->itdb) {
938 1914050 : tdb_traverse(
939 1896617 : ldb_kv->idxptr->itdb, ldb_kv_index_traverse_store, module);
940 1914050 : tdb_close(ldb_kv->idxptr->itdb);
941 : }
942 :
943 1914050 : ret = ldb_kv->idxptr->error;
944 1914050 : if (ret != LDB_SUCCESS) {
945 0 : if (!ldb_errstring(ldb)) {
946 0 : ldb_set_errstring(ldb, ldb_strerror(ret));
947 : }
948 0 : ldb_asprintf_errstring(ldb, "Failed to store index records in transaction commit: %s", ldb_errstring(ldb));
949 : }
950 :
951 1914050 : talloc_free(ldb_kv->idxptr);
952 1914050 : ldb_kv->idxptr = NULL;
953 1914050 : return ret;
954 : }
955 :
956 : /* cleanup the idxptr mode when transaction cancels */
957 279355 : int ldb_kv_index_transaction_cancel(struct ldb_module *module)
958 : {
959 279355 : struct ldb_kv_private *ldb_kv = talloc_get_type(
960 : ldb_module_get_private(module), struct ldb_kv_private);
961 279355 : if (ldb_kv->idxptr && ldb_kv->idxptr->itdb) {
962 279332 : tdb_close(ldb_kv->idxptr->itdb);
963 : }
964 279355 : TALLOC_FREE(ldb_kv->idxptr);
965 279355 : if (ldb_kv->nested_idx_ptr && ldb_kv->nested_idx_ptr->itdb) {
966 11414 : tdb_close(ldb_kv->nested_idx_ptr->itdb);
967 : }
968 279355 : TALLOC_FREE(ldb_kv->nested_idx_ptr);
969 279355 : return LDB_SUCCESS;
970 : }
971 :
972 :
973 : /*
974 : return the dn key to be used for an index
975 : the caller is responsible for freeing
976 : */
977 151915777 : static struct ldb_dn *ldb_kv_index_key(struct ldb_context *ldb,
978 : TALLOC_CTX *mem_ctx,
979 : struct ldb_kv_private *ldb_kv,
980 : const char *attr,
981 : const struct ldb_val *value,
982 : const struct ldb_schema_attribute **ap,
983 : enum key_truncation *truncation)
984 : {
985 6250181 : struct ldb_dn *ret;
986 6250181 : struct ldb_val v;
987 151915777 : const struct ldb_schema_attribute *a = NULL;
988 151915777 : char *attr_folded = NULL;
989 151915777 : const char *attr_for_dn = NULL;
990 6250181 : int r;
991 6250181 : bool should_b64_encode;
992 :
993 151915777 : unsigned int max_key_length = ldb_kv_max_key_length(ldb_kv);
994 151915777 : size_t key_len = 0;
995 151915777 : size_t attr_len = 0;
996 151915777 : const size_t indx_len = sizeof(LDB_KV_INDEX) - 1;
997 151915777 : unsigned frmt_len = 0;
998 151915777 : const size_t additional_key_length = 4;
999 151915777 : unsigned int num_separators = 3; /* Estimate for overflow check */
1000 151915777 : const size_t min_data = 1;
1001 151915777 : const size_t min_key_length = additional_key_length
1002 145665596 : + indx_len + num_separators + min_data;
1003 6250181 : struct ldb_val empty;
1004 :
1005 : /*
1006 : * Accept a NULL value as a request for a key with no value. This is
1007 : * different from passing an empty value, which might be given
1008 : * significance by some canonicalise functions.
1009 : */
1010 151915777 : bool empty_val = value == NULL;
1011 151915777 : if (empty_val) {
1012 2856 : empty.length = 0;
1013 2856 : empty.data = discard_const_p(unsigned char, "");
1014 2856 : value = ∅
1015 : }
1016 :
1017 151915777 : if (attr[0] == '@') {
1018 120793132 : attr_for_dn = attr;
1019 120793132 : v = *value;
1020 120793132 : if (ap != NULL) {
1021 4381862 : *ap = NULL;
1022 : }
1023 : } else {
1024 31122645 : attr_folded = ldb_attr_casefold(ldb, attr);
1025 31122645 : if (!attr_folded) {
1026 0 : return NULL;
1027 : }
1028 :
1029 31122645 : attr_for_dn = attr_folded;
1030 :
1031 31122645 : a = ldb_schema_attribute_by_name(ldb, attr);
1032 31122645 : if (ap) {
1033 19412351 : *ap = a;
1034 : }
1035 :
1036 31122645 : if (empty_val) {
1037 2856 : v = *value;
1038 : } else {
1039 2177248 : ldb_attr_handler_t fn;
1040 31119789 : if (a->syntax->index_format_fn &&
1041 5776841 : ldb_kv->cache->GUID_index_attribute != NULL) {
1042 5347996 : fn = a->syntax->index_format_fn;
1043 : } else {
1044 25365840 : fn = a->syntax->canonicalise_fn;
1045 : }
1046 31119789 : r = fn(ldb, ldb, value, &v);
1047 31119789 : if (r != LDB_SUCCESS) {
1048 0 : const char *errstr = ldb_errstring(ldb);
1049 : /* canonicalisation can be refused. For
1050 : example, a attribute that takes wildcards
1051 : will refuse to canonicalise if the value
1052 : contains a wildcard */
1053 0 : ldb_asprintf_errstring(ldb,
1054 : "Failed to create "
1055 : "index key for "
1056 : "attribute '%s':%s%s%s",
1057 : attr, ldb_strerror(r),
1058 : (errstr?":":""),
1059 : (errstr?errstr:""));
1060 0 : talloc_free(attr_folded);
1061 0 : return NULL;
1062 : }
1063 : }
1064 : }
1065 151915777 : attr_len = strlen(attr_for_dn);
1066 :
1067 : /*
1068 : * Check if there is any hope this will fit into the DB.
1069 : * Overflow here is not actually critical the code below
1070 : * checks again to make the printf and the DB does another
1071 : * check for too long keys
1072 : */
1073 151915777 : if (max_key_length - attr_len < min_key_length) {
1074 0 : ldb_asprintf_errstring(
1075 : ldb,
1076 : __location__ ": max_key_length "
1077 : "is too small (%u) < (%u)",
1078 : max_key_length,
1079 : (unsigned)(min_key_length + attr_len));
1080 0 : talloc_free(attr_folded);
1081 0 : return NULL;
1082 : }
1083 :
1084 : /*
1085 : * ltdb_key_dn() makes something 4 bytes longer, it adds a leading
1086 : * "DN=" and a trailing string terminator
1087 : */
1088 151915777 : max_key_length -= additional_key_length;
1089 :
1090 : /*
1091 : * We do not base 64 encode a DN in a key, it has already been
1092 : * casefolded and linearized, that is good enough. That already
1093 : * avoids embedded NUL etc.
1094 : */
1095 151915777 : if (ldb_kv->cache->GUID_index_attribute != NULL) {
1096 150876969 : if (strcmp(attr, LDB_KV_IDXDN) == 0) {
1097 113230772 : should_b64_encode = false;
1098 33807403 : } else if (strcmp(attr, LDB_KV_IDXONE) == 0) {
1099 : /*
1100 : * We can only change the behaviour for IDXONE
1101 : * when the GUID index is enabled
1102 : */
1103 3465803 : should_b64_encode = false;
1104 : } else {
1105 1991882 : should_b64_encode
1106 30119029 : = ldb_should_b64_encode(ldb, &v);
1107 : }
1108 : } else {
1109 1038808 : should_b64_encode = ldb_should_b64_encode(ldb, &v);
1110 : }
1111 :
1112 147854412 : if (should_b64_encode) {
1113 8759029 : size_t vstr_len = 0;
1114 8759029 : char *vstr = ldb_base64_encode(mem_ctx, (char *)v.data, v.length);
1115 8759029 : if (!vstr) {
1116 0 : talloc_free(attr_folded);
1117 0 : return NULL;
1118 : }
1119 8759029 : vstr_len = strlen(vstr);
1120 : /*
1121 : * Overflow here is not critical as we only use this
1122 : * to choose the printf truncation
1123 : */
1124 8759029 : key_len = num_separators + indx_len + attr_len + vstr_len;
1125 8759029 : if (key_len > max_key_length) {
1126 4 : size_t excess = key_len - max_key_length;
1127 4 : frmt_len = vstr_len - excess;
1128 4 : *truncation = KEY_TRUNCATED;
1129 : /*
1130 : * Truncated keys are placed in a separate key space
1131 : * from the non truncated keys
1132 : * Note: the double hash "##" is not a typo and
1133 : * indicates that the following value is base64 encoded
1134 : */
1135 4 : ret = ldb_dn_new_fmt(mem_ctx, ldb, "%s#%s##%.*s",
1136 : LDB_KV_INDEX, attr_for_dn,
1137 : frmt_len, vstr);
1138 : } else {
1139 8759025 : frmt_len = vstr_len;
1140 8759025 : *truncation = KEY_NOT_TRUNCATED;
1141 : /*
1142 : * Note: the double colon "::" is not a typo and
1143 : * indicates that the following value is base64 encoded
1144 : */
1145 8759025 : ret = ldb_dn_new_fmt(mem_ctx, ldb, "%s:%s::%.*s",
1146 : LDB_KV_INDEX, attr_for_dn,
1147 : frmt_len, vstr);
1148 : }
1149 8759029 : talloc_free(vstr);
1150 : } else {
1151 : /* Only need two separators */
1152 143156748 : num_separators = 2;
1153 :
1154 : /*
1155 : * Overflow here is not critical as we only use this
1156 : * to choose the printf truncation
1157 : */
1158 143156748 : key_len = num_separators + indx_len + attr_len + (int)v.length;
1159 143156748 : if (key_len > max_key_length) {
1160 723 : size_t excess = key_len - max_key_length;
1161 723 : frmt_len = v.length - excess;
1162 723 : *truncation = KEY_TRUNCATED;
1163 : /*
1164 : * Truncated keys are placed in a separate key space
1165 : * from the non truncated keys
1166 : */
1167 723 : ret = ldb_dn_new_fmt(mem_ctx, ldb, "%s#%s#%.*s",
1168 : LDB_KV_INDEX, attr_for_dn,
1169 723 : frmt_len, (char *)v.data);
1170 : } else {
1171 143156025 : frmt_len = v.length;
1172 143156025 : *truncation = KEY_NOT_TRUNCATED;
1173 143156025 : ret = ldb_dn_new_fmt(mem_ctx, ldb, "%s:%s:%.*s",
1174 : LDB_KV_INDEX, attr_for_dn,
1175 143156025 : frmt_len, (char *)v.data);
1176 : }
1177 : }
1178 :
1179 151915777 : if (value != NULL && v.data != value->data && !empty_val) {
1180 31119789 : talloc_free(v.data);
1181 : }
1182 151915777 : talloc_free(attr_folded);
1183 :
1184 151915777 : return ret;
1185 : }
1186 :
1187 : /*
1188 : see if a attribute value is in the list of indexed attributes
1189 : */
1190 59508982 : static bool ldb_kv_is_indexed(struct ldb_module *module,
1191 : struct ldb_kv_private *ldb_kv,
1192 : const char *attr)
1193 : {
1194 59508982 : struct ldb_context *ldb = ldb_module_get_ctx(module);
1195 4698451 : unsigned int i;
1196 4698451 : struct ldb_message_element *el;
1197 :
1198 59508982 : if ((ldb_kv->cache->GUID_index_attribute != NULL) &&
1199 58181458 : (ldb_attr_cmp(attr, ldb_kv->cache->GUID_index_attribute) == 0)) {
1200 : /* Implicitly covered, this is the index key */
1201 2073367 : return false;
1202 : }
1203 57247248 : if (ldb->schema.index_handler_override) {
1204 4346386 : const struct ldb_schema_attribute *a
1205 55879238 : = ldb_schema_attribute_by_name(ldb, attr);
1206 :
1207 55879238 : if (a == NULL) {
1208 0 : return false;
1209 : }
1210 :
1211 55879238 : if (a->flags & LDB_ATTR_FLAG_INDEXED) {
1212 25505461 : return true;
1213 : } else {
1214 28510148 : return false;
1215 : }
1216 : }
1217 :
1218 1368010 : if (!ldb_kv->cache->attribute_indexes) {
1219 3124 : return false;
1220 : }
1221 :
1222 1364544 : el = ldb_msg_find_element(ldb_kv->cache->indexlist, LDB_KV_IDXATTR);
1223 1364544 : if (el == NULL) {
1224 0 : return false;
1225 : }
1226 :
1227 : /* TODO: this is too expensive! At least use a binary search */
1228 11928940 : for (i=0; i<el->num_values; i++) {
1229 11628594 : if (ldb_attr_cmp((char *)el->values[i].data, attr) == 0) {
1230 955519 : return true;
1231 : }
1232 : }
1233 245669 : return false;
1234 : }
1235 :
1236 : /*
1237 : in the following logic functions, the return value is treated as
1238 : follows:
1239 :
1240 : LDB_SUCCESS: we found some matching index values
1241 :
1242 : LDB_ERR_NO_SUCH_OBJECT: we know for sure that no object matches
1243 :
1244 : LDB_ERR_OPERATIONS_ERROR: indexing could not answer the call,
1245 : we'll need a full search
1246 : */
1247 :
1248 : /*
1249 : return a list of dn's that might match a simple indexed search (an
1250 : equality search only)
1251 : */
1252 10207540 : static int ldb_kv_index_dn_simple(struct ldb_module *module,
1253 : struct ldb_kv_private *ldb_kv,
1254 : const struct ldb_parse_tree *tree,
1255 : struct dn_list *list)
1256 : {
1257 436184 : struct ldb_context *ldb;
1258 436184 : struct ldb_dn *dn;
1259 436184 : int ret;
1260 10207540 : enum key_truncation truncation = KEY_NOT_TRUNCATED;
1261 :
1262 10207540 : ldb = ldb_module_get_ctx(module);
1263 :
1264 10207540 : list->count = 0;
1265 10207540 : list->dn = NULL;
1266 :
1267 : /* if the attribute isn't in the list of indexed attributes then
1268 : this node needs a full search */
1269 10207540 : if (!ldb_kv_is_indexed(module, ldb_kv, tree->u.equality.attr)) {
1270 132416 : return LDB_ERR_OPERATIONS_ERROR;
1271 : }
1272 :
1273 : /*
1274 : * the attribute is indexed. Pull the list of DNs that match the
1275 : * search criterion
1276 : *
1277 : * list is used as a memory context as it has a shorter life
1278 : * than 'ldb'. Regardless we talloc_free() 'dn' below.
1279 : */
1280 10502010 : dn = ldb_kv_index_key(ldb,
1281 : list,
1282 : ldb_kv,
1283 10070475 : tree->u.equality.attr,
1284 : &tree->u.equality.value,
1285 : NULL,
1286 : &truncation);
1287 : /*
1288 : * We ignore truncation here and allow multi-valued matches
1289 : * as ltdb_search_indexed will filter out the wrong one in
1290 : * ltdb_index_filter() which calls ldb_match_message().
1291 : */
1292 10070475 : if (!dn) {
1293 0 : return LDB_ERR_OPERATIONS_ERROR;
1294 : }
1295 :
1296 10070475 : ret = ldb_kv_dn_list_load(module, ldb_kv, dn, list,
1297 : DN_LIST_WILL_BE_READ_ONLY);
1298 10070475 : talloc_free(dn);
1299 10070475 : return ret;
1300 : }
1301 :
1302 : static bool list_union(struct ldb_context *ldb,
1303 : struct ldb_kv_private *ldb_kv,
1304 : struct dn_list *list,
1305 : struct dn_list *list2);
1306 :
1307 : /*
1308 : return a list of dn's that might match a leaf indexed search
1309 : */
1310 95906810 : static int ldb_kv_index_dn_leaf(struct ldb_module *module,
1311 : struct ldb_kv_private *ldb_kv,
1312 : const struct ldb_parse_tree *tree,
1313 : struct dn_list *list)
1314 : {
1315 95906810 : if (ldb_kv->disallow_dn_filter &&
1316 94628743 : (ldb_attr_cmp(tree->u.equality.attr, "dn") == 0)) {
1317 : /* in AD mode we do not support "(dn=...)" search filters */
1318 47 : list->dn = NULL;
1319 47 : list->count = 0;
1320 47 : return LDB_SUCCESS;
1321 : }
1322 95906763 : if (tree->u.equality.attr[0] == '@') {
1323 : /* Do not allow a indexed search against an @ */
1324 84 : list->dn = NULL;
1325 84 : list->count = 0;
1326 84 : return LDB_SUCCESS;
1327 : }
1328 95906679 : if (ldb_attr_dn(tree->u.equality.attr) == 0) {
1329 256532 : enum key_truncation truncation = KEY_NOT_TRUNCATED;
1330 256532 : bool valid_dn = false;
1331 4460 : struct ldb_dn *dn
1332 256532 : = ldb_dn_from_ldb_val(list,
1333 : ldb_module_get_ctx(module),
1334 : &tree->u.equality.value);
1335 256532 : if (dn == NULL) {
1336 : /* If we can't parse it, no match */
1337 0 : list->dn = NULL;
1338 0 : list->count = 0;
1339 0 : return LDB_SUCCESS;
1340 : }
1341 :
1342 256532 : valid_dn = ldb_dn_validate(dn);
1343 256532 : if (valid_dn == false) {
1344 : /* If we can't parse it, no match */
1345 62 : list->dn = NULL;
1346 62 : list->count = 0;
1347 62 : return LDB_SUCCESS;
1348 : }
1349 :
1350 : /*
1351 : * Re-use the same code we use for a SCOPE_BASE
1352 : * search
1353 : *
1354 : * We can't call TALLOC_FREE(dn) as this must belong
1355 : * to list for the memory to remain valid.
1356 : */
1357 256470 : return ldb_kv_index_dn_base_dn(
1358 : module, ldb_kv, dn, list, &truncation);
1359 : /*
1360 : * We ignore truncation here and allow multi-valued matches
1361 : * as ltdb_search_indexed will filter out the wrong one in
1362 : * ltdb_index_filter() which calls ldb_match_message().
1363 : */
1364 :
1365 95650147 : } else if ((ldb_kv->cache->GUID_index_attribute != NULL) &&
1366 94848604 : (ldb_attr_cmp(tree->u.equality.attr,
1367 : ldb_kv->cache->GUID_index_attribute) == 0)) {
1368 1906343 : int ret;
1369 85442607 : struct ldb_context *ldb = ldb_module_get_ctx(module);
1370 85442607 : list->dn = talloc_array(list, struct ldb_val, 1);
1371 85442607 : if (list->dn == NULL) {
1372 0 : ldb_module_oom(module);
1373 0 : return LDB_ERR_OPERATIONS_ERROR;
1374 : }
1375 : /*
1376 : * We need to go via the canonicalise_fn() to
1377 : * ensure we get the index in binary, rather
1378 : * than a string
1379 : */
1380 85442607 : ret = ldb_kv->GUID_index_syntax->canonicalise_fn(
1381 83536264 : ldb, list->dn, &tree->u.equality.value, &list->dn[0]);
1382 85442607 : if (ret != LDB_SUCCESS) {
1383 0 : return LDB_ERR_OPERATIONS_ERROR;
1384 : }
1385 85442607 : list->count = 1;
1386 85442607 : return LDB_SUCCESS;
1387 : }
1388 :
1389 10207540 : return ldb_kv_index_dn_simple(module, ldb_kv, tree, list);
1390 : }
1391 :
1392 :
1393 : /*
1394 : list intersection
1395 : list = list & list2
1396 : */
1397 792887 : static bool list_intersect(struct ldb_kv_private *ldb_kv,
1398 : struct dn_list *list,
1399 : const struct dn_list *list2)
1400 : {
1401 25021 : const struct dn_list *short_list, *long_list;
1402 25021 : struct dn_list *list3;
1403 25021 : unsigned int i;
1404 :
1405 792887 : if (list->count == 0) {
1406 : /* 0 & X == 0 */
1407 0 : return true;
1408 : }
1409 792887 : if (list2->count == 0) {
1410 : /* X & 0 == 0 */
1411 72 : list->count = 0;
1412 72 : list->dn = NULL;
1413 72 : return true;
1414 : }
1415 :
1416 : /*
1417 : * In both of the below we check for strict and in that
1418 : * case do not optimise the intersection of this list,
1419 : * we must never return an entry not in this
1420 : * list. This allows the index for
1421 : * SCOPE_ONELEVEL to be trusted.
1422 : */
1423 :
1424 : /* the indexing code is allowed to return a longer list than
1425 : what really matches, as all results are filtered by the
1426 : full expression at the end - this shortcut avoids a lot of
1427 : work in some cases */
1428 792815 : if (list->count < 2 && list2->count > 10 && list2->strict == false) {
1429 122 : return true;
1430 : }
1431 792693 : if (list2->count < 2 && list->count > 10 && list->strict == false) {
1432 13008 : list->count = list2->count;
1433 13008 : list->dn = list2->dn;
1434 : /* note that list2 may not be the parent of list2->dn,
1435 : as list2->dn may be owned by ltdb->idxptr. In that
1436 : case we expect this reparent call to fail, which is
1437 : OK */
1438 13008 : talloc_reparent(list2, list, list2->dn);
1439 13008 : return true;
1440 : }
1441 :
1442 779685 : if (list->count > list2->count) {
1443 641933 : short_list = list2;
1444 641933 : long_list = list;
1445 : } else {
1446 114945 : short_list = list;
1447 114945 : long_list = list2;
1448 : }
1449 :
1450 779685 : list3 = talloc_zero(list, struct dn_list);
1451 779685 : if (list3 == NULL) {
1452 0 : return false;
1453 : }
1454 :
1455 779685 : list3->dn = talloc_array(list3, struct ldb_val,
1456 : MIN(list->count, list2->count));
1457 779685 : if (!list3->dn) {
1458 0 : talloc_free(list3);
1459 0 : return false;
1460 : }
1461 779685 : list3->count = 0;
1462 :
1463 4111274 : for (i=0;i<short_list->count;i++) {
1464 : /* For the GUID index case, this is a binary search */
1465 3331589 : if (ldb_kv_dn_list_find_val(
1466 3331589 : ldb_kv, long_list, &short_list->dn[i]) != -1) {
1467 2917358 : list3->dn[list3->count] = short_list->dn[i];
1468 2917358 : list3->count++;
1469 : }
1470 : }
1471 :
1472 779685 : list->strict |= list2->strict;
1473 779685 : list->dn = talloc_steal(list, list3->dn);
1474 779685 : list->count = list3->count;
1475 779685 : talloc_free(list3);
1476 :
1477 779685 : return true;
1478 : }
1479 :
1480 :
1481 : /*
1482 : list union
1483 : list = list | list2
1484 : */
1485 256813 : static bool list_union(struct ldb_context *ldb,
1486 : struct ldb_kv_private *ldb_kv,
1487 : struct dn_list *list,
1488 : struct dn_list *list2)
1489 : {
1490 6459 : struct ldb_val *dn3;
1491 256813 : unsigned int i = 0, j = 0, k = 0;
1492 :
1493 256813 : if (list2->count == 0) {
1494 : /* X | 0 == X */
1495 0 : return true;
1496 : }
1497 :
1498 256813 : if (list->count == 0) {
1499 : /* 0 | X == X */
1500 174408 : list->count = list2->count;
1501 174408 : list->dn = list2->dn;
1502 : /* note that list2 may not be the parent of list2->dn,
1503 : as list2->dn may be owned by ltdb->idxptr. In that
1504 : case we expect this reparent call to fail, which is
1505 : OK */
1506 174408 : talloc_reparent(list2, list, list2->dn);
1507 174408 : return true;
1508 : }
1509 :
1510 : /*
1511 : * Sort the lists (if not in GUID DN mode) so we can do
1512 : * the de-duplication during the merge
1513 : *
1514 : * NOTE: This can sort the in-memory index values, as list or
1515 : * list2 might not be a copy!
1516 : */
1517 82405 : ldb_kv_dn_list_sort(ldb_kv, list);
1518 82405 : ldb_kv_dn_list_sort(ldb_kv, list2);
1519 :
1520 82405 : dn3 = talloc_array(list, struct ldb_val, list->count + list2->count);
1521 82405 : if (!dn3) {
1522 0 : ldb_oom(ldb);
1523 0 : return false;
1524 : }
1525 :
1526 92224964 : while (i < list->count || j < list2->count) {
1527 1066011 : int cmp;
1528 92142559 : if (i >= list->count) {
1529 12365 : cmp = 1;
1530 92130139 : } else if (j >= list2->count) {
1531 26213185 : cmp = -1;
1532 : } else {
1533 67627927 : cmp = ldb_val_equal_exact_ordered(list->dn[i],
1534 65722175 : &list2->dn[j]);
1535 : }
1536 :
1537 91916289 : if (cmp < 0) {
1538 : /* Take list */
1539 84749352 : dn3[k] = list->dn[i];
1540 84749352 : i++;
1541 84749352 : k++;
1542 7393207 : } else if (cmp > 0) {
1543 : /* Take list2 */
1544 7371582 : dn3[k] = list2->dn[j];
1545 7371582 : j++;
1546 7371582 : k++;
1547 : } else {
1548 : /* Equal, take list */
1549 21625 : dn3[k] = list->dn[i];
1550 21625 : i++;
1551 21625 : j++;
1552 21625 : k++;
1553 : }
1554 : }
1555 :
1556 82405 : list->dn = dn3;
1557 82405 : list->count = k;
1558 :
1559 82405 : return true;
1560 : }
1561 :
1562 : static int ldb_kv_index_dn(struct ldb_module *module,
1563 : struct ldb_kv_private *ldb_kv,
1564 : const struct ldb_parse_tree *tree,
1565 : struct dn_list *list);
1566 :
1567 : /*
1568 : process an OR list (a union)
1569 : */
1570 247425 : static int ldb_kv_index_dn_or(struct ldb_module *module,
1571 : struct ldb_kv_private *ldb_kv,
1572 : const struct ldb_parse_tree *tree,
1573 : struct dn_list *list)
1574 : {
1575 6740 : struct ldb_context *ldb;
1576 6740 : unsigned int i;
1577 :
1578 247425 : ldb = ldb_module_get_ctx(module);
1579 :
1580 247425 : list->dn = NULL;
1581 247425 : list->count = 0;
1582 :
1583 635155 : for (i=0; i<tree->u.list.num_elements; i++) {
1584 12371 : struct dn_list *list2;
1585 12371 : int ret;
1586 :
1587 461661 : list2 = talloc_zero(list, struct dn_list);
1588 461661 : if (list2 == NULL) {
1589 0 : return LDB_ERR_OPERATIONS_ERROR;
1590 : }
1591 :
1592 474032 : ret = ldb_kv_index_dn(
1593 461661 : module, ldb_kv, tree->u.list.elements[i], list2);
1594 :
1595 461661 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1596 : /* X || 0 == X */
1597 130917 : talloc_free(list2);
1598 130917 : continue;
1599 : }
1600 :
1601 330744 : if (ret != LDB_SUCCESS) {
1602 : /* X || * == * */
1603 73931 : talloc_free(list2);
1604 73931 : return ret;
1605 : }
1606 :
1607 256813 : if (!list_union(ldb, ldb_kv, list, list2)) {
1608 0 : talloc_free(list2);
1609 0 : return LDB_ERR_OPERATIONS_ERROR;
1610 : }
1611 : }
1612 :
1613 173494 : if (list->count == 0) {
1614 464 : return LDB_ERR_NO_SUCH_OBJECT;
1615 : }
1616 :
1617 167779 : return LDB_SUCCESS;
1618 : }
1619 :
1620 :
1621 : /*
1622 : NOT an index results
1623 : */
1624 8384849 : static int ldb_kv_index_dn_not(_UNUSED_ struct ldb_module *module,
1625 : _UNUSED_ struct ldb_kv_private *ldb_kv,
1626 : _UNUSED_ const struct ldb_parse_tree *tree,
1627 : _UNUSED_ struct dn_list *list)
1628 : {
1629 : /* the only way to do an indexed not would be if we could
1630 : negate the not via another not or if we knew the total
1631 : number of database elements so we could know that the
1632 : existing expression covered the whole database.
1633 :
1634 : instead, we just give up, and rely on a full index scan
1635 : (unless an outer & manages to reduce the list)
1636 : */
1637 8384849 : return LDB_ERR_OPERATIONS_ERROR;
1638 : }
1639 :
1640 : /*
1641 : * These things are unique, so avoid a full scan if this is a search
1642 : * by GUID, DN or a unique attribute
1643 : */
1644 26634300 : static bool ldb_kv_index_unique(struct ldb_context *ldb,
1645 : struct ldb_kv_private *ldb_kv,
1646 : const char *attr)
1647 : {
1648 808505 : const struct ldb_schema_attribute *a;
1649 26634300 : if (ldb_kv->cache->GUID_index_attribute != NULL) {
1650 26405002 : if (ldb_attr_cmp(attr, ldb_kv->cache->GUID_index_attribute) ==
1651 : 0) {
1652 16297171 : return true;
1653 : }
1654 : }
1655 9905473 : if (ldb_attr_dn(attr) == 0) {
1656 251865 : return true;
1657 : }
1658 :
1659 9649182 : a = ldb_schema_attribute_by_name(ldb, attr);
1660 9649182 : if (a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX) {
1661 460 : return true;
1662 : }
1663 9276539 : return false;
1664 : }
1665 :
1666 : /*
1667 : process an AND expression (intersection)
1668 : */
1669 26893921 : static int ldb_kv_index_dn_and(struct ldb_module *module,
1670 : struct ldb_kv_private *ldb_kv,
1671 : const struct ldb_parse_tree *tree,
1672 : struct dn_list *list)
1673 : {
1674 821217 : struct ldb_context *ldb;
1675 821217 : unsigned int i;
1676 821217 : bool found;
1677 :
1678 26893921 : ldb = ldb_module_get_ctx(module);
1679 :
1680 26893921 : list->dn = NULL;
1681 26893921 : list->count = 0;
1682 :
1683 : /* in the first pass we only look for unique simple
1684 : equality tests, in the hope of avoiding having to look
1685 : at any others */
1686 63981710 : for (i=0; i<tree->u.list.num_elements; i++) {
1687 54073367 : const struct ldb_parse_tree *subtree = tree->u.list.elements[i];
1688 1651621 : int ret;
1689 :
1690 54881872 : if (subtree->operation != LDB_OP_EQUALITY ||
1691 26634300 : !ldb_kv_index_unique(
1692 26634300 : ldb, ldb_kv, subtree->u.equality.attr)) {
1693 37087789 : continue;
1694 : }
1695 :
1696 16985578 : ret = ldb_kv_index_dn(module, ldb_kv, subtree, list);
1697 16985578 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1698 : /* 0 && X == 0 */
1699 89939 : return LDB_ERR_NO_SUCH_OBJECT;
1700 : }
1701 16895447 : if (ret == LDB_SUCCESS) {
1702 : /* a unique index match means we can
1703 : * stop. Note that we don't care if we return
1704 : * a few too many objects, due to later
1705 : * filtering */
1706 16459317 : return LDB_SUCCESS;
1707 : }
1708 : }
1709 :
1710 : /* now do a full intersection */
1711 9523448 : found = false;
1712 :
1713 20484770 : for (i=0; i<tree->u.list.num_elements; i++) {
1714 19581930 : const struct ldb_parse_tree *subtree = tree->u.list.elements[i];
1715 753572 : struct dn_list *list2;
1716 753572 : int ret;
1717 :
1718 19581930 : list2 = talloc_zero(list, struct dn_list);
1719 19581930 : if (list2 == NULL) {
1720 0 : return ldb_module_oom(module);
1721 : }
1722 :
1723 19581930 : ret = ldb_kv_index_dn(module, ldb_kv, subtree, list2);
1724 :
1725 19581930 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
1726 : /* X && 0 == 0 */
1727 6936062 : list->dn = NULL;
1728 6936062 : list->count = 0;
1729 6936062 : talloc_free(list2);
1730 6936062 : return LDB_ERR_NO_SUCH_OBJECT;
1731 : }
1732 :
1733 12645868 : if (ret != LDB_SUCCESS) {
1734 : /* this didn't adding anything */
1735 9272558 : talloc_free(list2);
1736 9272558 : continue;
1737 : }
1738 :
1739 3373310 : if (!found) {
1740 3010451 : talloc_reparent(list2, list, list->dn);
1741 3010451 : list->dn = list2->dn;
1742 3010451 : list->count = list2->count;
1743 3010451 : found = true;
1744 362859 : } else if (!list_intersect(ldb_kv, list, list2)) {
1745 0 : talloc_free(list2);
1746 0 : return LDB_ERR_OPERATIONS_ERROR;
1747 : }
1748 :
1749 3373310 : if (list->count == 0) {
1750 7631 : list->dn = NULL;
1751 7631 : return LDB_ERR_NO_SUCH_OBJECT;
1752 : }
1753 :
1754 3365679 : if (list->count < 2) {
1755 : /* it isn't worth loading the next part of the tree */
1756 1983633 : return LDB_SUCCESS;
1757 : }
1758 : }
1759 :
1760 902840 : if (!found) {
1761 : /* none of the attributes were indexed */
1762 153455 : return LDB_ERR_OPERATIONS_ERROR;
1763 : }
1764 :
1765 727911 : return LDB_SUCCESS;
1766 : }
1767 :
1768 : struct ldb_kv_ordered_index_context {
1769 : struct ldb_module *module;
1770 : int error;
1771 : struct dn_list *dn_list;
1772 : };
1773 :
1774 442506 : static int traverse_range_index(_UNUSED_ struct ldb_kv_private *ldb_kv,
1775 : _UNUSED_ struct ldb_val key,
1776 : struct ldb_val data,
1777 : void *state)
1778 : {
1779 :
1780 417 : struct ldb_context *ldb;
1781 442506 : struct ldb_kv_ordered_index_context *ctx =
1782 : (struct ldb_kv_ordered_index_context *)state;
1783 442506 : struct ldb_module *module = ctx->module;
1784 442506 : struct ldb_message_element *el = NULL;
1785 442506 : struct ldb_message *msg = NULL;
1786 417 : int version;
1787 417 : size_t dn_array_size, additional_length;
1788 417 : unsigned int i;
1789 :
1790 442506 : ldb = ldb_module_get_ctx(module);
1791 :
1792 442506 : msg = ldb_msg_new(module);
1793 :
1794 442506 : ctx->error = ldb_unpack_data_flags(ldb, &data, msg,
1795 : LDB_UNPACK_DATA_FLAG_NO_DN);
1796 :
1797 442506 : if (ctx->error != LDB_SUCCESS) {
1798 0 : talloc_free(msg);
1799 0 : return ctx->error;
1800 : }
1801 :
1802 442506 : el = ldb_msg_find_element(msg, LDB_KV_IDX);
1803 442506 : if (!el) {
1804 0 : talloc_free(msg);
1805 0 : return LDB_SUCCESS;
1806 : }
1807 :
1808 442506 : version = ldb_msg_find_attr_as_int(msg, LDB_KV_IDXVERSION, 0);
1809 :
1810 : /*
1811 : * we avoid copying the strings by stealing the list. We have
1812 : * to steal msg onto el->values (which looks odd) because
1813 : * the memory is allocated on msg, not on each value.
1814 : */
1815 442506 : if (version != LDB_KV_GUID_INDEXING_VERSION) {
1816 : /* This is quite likely during the DB startup
1817 : on first upgrade to using a GUID index */
1818 0 : ldb_debug_set(ldb_module_get_ctx(module),
1819 : LDB_DEBUG_ERROR, __location__
1820 : ": Wrong GUID index version %d expected %d",
1821 : version, LDB_KV_GUID_INDEXING_VERSION);
1822 0 : talloc_free(msg);
1823 0 : ctx->error = LDB_ERR_OPERATIONS_ERROR;
1824 0 : return ctx->error;
1825 : }
1826 :
1827 442506 : if (el->num_values == 0) {
1828 0 : talloc_free(msg);
1829 0 : ctx->error = LDB_ERR_OPERATIONS_ERROR;
1830 0 : return ctx->error;
1831 : }
1832 :
1833 442506 : if ((el->values[0].length % LDB_KV_GUID_SIZE) != 0
1834 442506 : || el->values[0].length == 0) {
1835 0 : talloc_free(msg);
1836 0 : ctx->error = LDB_ERR_OPERATIONS_ERROR;
1837 0 : return ctx->error;
1838 : }
1839 :
1840 442506 : dn_array_size = talloc_array_length(ctx->dn_list->dn);
1841 :
1842 442506 : additional_length = el->values[0].length / LDB_KV_GUID_SIZE;
1843 :
1844 442506 : if (ctx->dn_list->count + additional_length < ctx->dn_list->count) {
1845 0 : talloc_free(msg);
1846 0 : ctx->error = LDB_ERR_OPERATIONS_ERROR;
1847 0 : return ctx->error;
1848 : }
1849 :
1850 442506 : if ((ctx->dn_list->count + additional_length) >= dn_array_size) {
1851 108 : size_t new_array_length;
1852 :
1853 3964 : if (dn_array_size * 2 < dn_array_size) {
1854 0 : talloc_free(msg);
1855 0 : ctx->error = LDB_ERR_OPERATIONS_ERROR;
1856 0 : return ctx->error;
1857 : }
1858 :
1859 3964 : new_array_length = MAX(ctx->dn_list->count + additional_length,
1860 : dn_array_size * 2);
1861 :
1862 3964 : ctx->dn_list->dn = talloc_realloc(ctx->dn_list,
1863 : ctx->dn_list->dn,
1864 : struct ldb_val,
1865 : new_array_length);
1866 : }
1867 :
1868 442506 : if (ctx->dn_list->dn == NULL) {
1869 0 : talloc_free(msg);
1870 0 : ctx->error = LDB_ERR_OPERATIONS_ERROR;
1871 0 : return ctx->error;
1872 : }
1873 :
1874 : /*
1875 : * The actual data is on msg.
1876 : */
1877 442506 : talloc_steal(ctx->dn_list->dn, msg);
1878 885762 : for (i = 0; i < additional_length; i++) {
1879 442839 : ctx->dn_list->dn[i + ctx->dn_list->count].data
1880 442839 : = &el->values[0].data[i * LDB_KV_GUID_SIZE];
1881 442839 : ctx->dn_list->dn[i + ctx->dn_list->count].length = LDB_KV_GUID_SIZE;
1882 :
1883 : }
1884 :
1885 442506 : ctx->dn_list->count += additional_length;
1886 :
1887 442506 : talloc_free(msg->elements);
1888 :
1889 442506 : return LDB_SUCCESS;
1890 : }
1891 :
1892 : /*
1893 : * >= and <= indexing implemented using lexicographically sorted keys
1894 : *
1895 : * We only run this in GUID indexing mode and when there is no write
1896 : * transaction (only implicit read locks are being held). Otherwise, we would
1897 : * have to deal with the in-memory index cache.
1898 : *
1899 : * We rely on the implementation of index_format_fn on a schema syntax which
1900 : * will can help us to construct keys which can be ordered correctly, and we
1901 : * terminate using schema agnostic start and end keys.
1902 : *
1903 : * index_format_fn must output values which can be memcmp-able to produce the
1904 : * correct ordering as defined by the schema syntax class.
1905 : */
1906 3474 : static int ldb_kv_index_dn_ordered(struct ldb_module *module,
1907 : struct ldb_kv_private *ldb_kv,
1908 : const struct ldb_parse_tree *tree,
1909 : struct dn_list *list, bool ascending)
1910 : {
1911 3474 : enum key_truncation truncation = KEY_NOT_TRUNCATED;
1912 3474 : struct ldb_context *ldb = ldb_module_get_ctx(module);
1913 :
1914 3474 : struct ldb_val ldb_key = { 0 }, ldb_key2 = { 0 };
1915 96 : struct ldb_val start_key, end_key;
1916 3474 : struct ldb_dn *key_dn = NULL;
1917 3474 : const struct ldb_schema_attribute *a = NULL;
1918 :
1919 96 : struct ldb_kv_ordered_index_context ctx;
1920 96 : int ret;
1921 :
1922 3474 : TALLOC_CTX *tmp_ctx = NULL;
1923 :
1924 3474 : if (!ldb_kv_is_indexed(module, ldb_kv, tree->u.comparison.attr)) {
1925 605 : return LDB_ERR_OPERATIONS_ERROR;
1926 : }
1927 :
1928 2869 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
1929 0 : return LDB_ERR_OPERATIONS_ERROR;
1930 : }
1931 :
1932 : /* bail out if we're in a transaction, full search instead. */
1933 2869 : if (ldb_kv->kv_ops->transaction_active(ldb_kv)) {
1934 0 : return LDB_ERR_OPERATIONS_ERROR;
1935 : }
1936 :
1937 2869 : if (ldb_kv->disallow_dn_filter &&
1938 2773 : (ldb_attr_cmp(tree->u.comparison.attr, "dn") == 0)) {
1939 : /* in AD mode we do not support "(dn=...)" search filters */
1940 0 : list->dn = NULL;
1941 0 : list->count = 0;
1942 0 : return LDB_SUCCESS;
1943 : }
1944 2869 : if (tree->u.comparison.attr[0] == '@') {
1945 : /* Do not allow a indexed search against an @ */
1946 0 : list->dn = NULL;
1947 0 : list->count = 0;
1948 0 : return LDB_SUCCESS;
1949 : }
1950 :
1951 2869 : a = ldb_schema_attribute_by_name(ldb, tree->u.comparison.attr);
1952 :
1953 : /*
1954 : * If there's no index format function defined for this attr, then
1955 : * the lexicographic order in the database doesn't correspond to the
1956 : * attr's ordering, so we can't use the iterate_range op.
1957 : */
1958 2869 : if (a->syntax->index_format_fn == NULL) {
1959 13 : return LDB_ERR_OPERATIONS_ERROR;
1960 : }
1961 :
1962 2856 : tmp_ctx = talloc_new(NULL);
1963 2856 : if (tmp_ctx == NULL) {
1964 0 : return ldb_module_oom(module);
1965 : }
1966 :
1967 2856 : key_dn = ldb_kv_index_key(ldb, tmp_ctx, ldb_kv, tree->u.comparison.attr,
1968 : &tree->u.comparison.value,
1969 : NULL, &truncation);
1970 2856 : if (!key_dn) {
1971 0 : TALLOC_FREE(tmp_ctx);
1972 0 : return LDB_ERR_OPERATIONS_ERROR;
1973 2856 : } else if (truncation == KEY_TRUNCATED) {
1974 0 : ldb_debug(ldb, LDB_DEBUG_WARNING,
1975 : __location__
1976 : ": ordered index violation: key dn truncated: %s\n",
1977 : ldb_dn_get_linearized(key_dn));
1978 0 : TALLOC_FREE(tmp_ctx);
1979 0 : return LDB_ERR_OPERATIONS_ERROR;
1980 : }
1981 2856 : ldb_key = ldb_kv_key_dn(tmp_ctx, key_dn);
1982 2856 : talloc_free(key_dn);
1983 2856 : if (ldb_key.data == NULL) {
1984 0 : TALLOC_FREE(tmp_ctx);
1985 0 : return LDB_ERR_OPERATIONS_ERROR;
1986 : }
1987 :
1988 2952 : key_dn = ldb_kv_index_key(ldb, tmp_ctx,
1989 2856 : ldb_kv, tree->u.comparison.attr,
1990 : NULL, NULL, &truncation);
1991 2856 : if (!key_dn) {
1992 0 : TALLOC_FREE(tmp_ctx);
1993 0 : return LDB_ERR_OPERATIONS_ERROR;
1994 2856 : } else if (truncation == KEY_TRUNCATED) {
1995 0 : ldb_debug(ldb, LDB_DEBUG_WARNING,
1996 : __location__
1997 : ": ordered index violation: key dn truncated: %s\n",
1998 : ldb_dn_get_linearized(key_dn));
1999 0 : TALLOC_FREE(tmp_ctx);
2000 0 : return LDB_ERR_OPERATIONS_ERROR;
2001 : }
2002 :
2003 2856 : ldb_key2 = ldb_kv_key_dn(tmp_ctx, key_dn);
2004 2856 : talloc_free(key_dn);
2005 2856 : if (ldb_key2.data == NULL) {
2006 0 : TALLOC_FREE(tmp_ctx);
2007 0 : return LDB_ERR_OPERATIONS_ERROR;
2008 : }
2009 :
2010 : /*
2011 : * In order to avoid defining a start and end key for the search, we
2012 : * notice that each index key is of the form:
2013 : *
2014 : * DN=@INDEX:<ATTRIBUTE>:<VALUE>\0.
2015 : *
2016 : * We can simply make our start key DN=@INDEX:<ATTRIBUTE>: and our end
2017 : * key DN=@INDEX:<ATTRIBUTE>; to return all index entries for a
2018 : * particular attribute.
2019 : *
2020 : * Our LMDB backend uses the default memcmp for key comparison.
2021 : */
2022 :
2023 : /* Eliminate NUL byte at the end of the empty key */
2024 2856 : ldb_key2.length--;
2025 :
2026 2856 : if (ascending) {
2027 : /* : becomes ; for pseudo end-key */
2028 2805 : ldb_key2.data[ldb_key2.length-1]++;
2029 2805 : start_key = ldb_key;
2030 2805 : end_key = ldb_key2;
2031 : } else {
2032 51 : start_key = ldb_key2;
2033 51 : end_key = ldb_key;
2034 : }
2035 :
2036 2856 : ctx.module = module;
2037 2856 : ctx.error = 0;
2038 2856 : ctx.dn_list = list;
2039 2856 : ctx.dn_list->count = 0;
2040 2856 : ctx.dn_list->dn = talloc_zero_array(ctx.dn_list, struct ldb_val, 2);
2041 :
2042 2856 : ret = ldb_kv->kv_ops->iterate_range(ldb_kv, start_key, end_key,
2043 : traverse_range_index, &ctx);
2044 :
2045 2856 : if (ret != LDB_SUCCESS || ctx.error != LDB_SUCCESS) {
2046 1847 : TALLOC_FREE(tmp_ctx);
2047 1847 : return LDB_ERR_OPERATIONS_ERROR;
2048 : }
2049 :
2050 1009 : TYPESAFE_QSORT(ctx.dn_list->dn, ctx.dn_list->count,
2051 : ldb_val_equal_exact_for_qsort);
2052 :
2053 1009 : TALLOC_FREE(tmp_ctx);
2054 :
2055 1009 : return LDB_SUCCESS;
2056 : }
2057 :
2058 3051 : static int ldb_kv_index_dn_greater(struct ldb_module *module,
2059 : struct ldb_kv_private *ldb_kv,
2060 : const struct ldb_parse_tree *tree,
2061 : struct dn_list *list)
2062 : {
2063 3051 : return ldb_kv_index_dn_ordered(module,
2064 : ldb_kv,
2065 : tree,
2066 : list, true);
2067 : }
2068 :
2069 423 : static int ldb_kv_index_dn_less(struct ldb_module *module,
2070 : struct ldb_kv_private *ldb_kv,
2071 : const struct ldb_parse_tree *tree,
2072 : struct dn_list *list)
2073 : {
2074 423 : return ldb_kv_index_dn_ordered(module,
2075 : ldb_kv,
2076 : tree,
2077 : list, false);
2078 : }
2079 :
2080 : /*
2081 : return a list of matching objects using a one-level index
2082 : */
2083 116248585 : static int ldb_kv_index_dn_attr(struct ldb_module *module,
2084 : struct ldb_kv_private *ldb_kv,
2085 : const char *attr,
2086 : struct ldb_dn *dn,
2087 : struct dn_list *list,
2088 : enum key_truncation *truncation)
2089 : {
2090 3684292 : struct ldb_context *ldb;
2091 3684292 : struct ldb_dn *key;
2092 3684292 : struct ldb_val val;
2093 3684292 : int ret;
2094 :
2095 116248585 : ldb = ldb_module_get_ctx(module);
2096 :
2097 : /* work out the index key from the parent DN */
2098 116248585 : val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn));
2099 116248585 : if (val.data == NULL) {
2100 0 : const char *dn_str = ldb_dn_get_linearized(dn);
2101 0 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
2102 : __location__
2103 : ": Failed to get casefold DN "
2104 : "from: %s",
2105 : dn_str);
2106 0 : return LDB_ERR_OPERATIONS_ERROR;
2107 : }
2108 116248585 : val.length = strlen((char *)val.data);
2109 :
2110 : /*
2111 : * We use list as a TALLOC_CTX to provide a shorter-lived
2112 : * memory context than ldb, even as the result is freed with
2113 : * the talloc_free(key) below.
2114 : */
2115 116248585 : key = ldb_kv_index_key(ldb, list, ldb_kv, attr, &val, NULL, truncation);
2116 116248585 : if (!key) {
2117 0 : ldb_oom(ldb);
2118 0 : return LDB_ERR_OPERATIONS_ERROR;
2119 : }
2120 :
2121 116248585 : ret = ldb_kv_dn_list_load(module, ldb_kv, key, list,
2122 : DN_LIST_WILL_BE_READ_ONLY);
2123 116248585 : talloc_free(key);
2124 116248585 : if (ret != LDB_SUCCESS) {
2125 2895580 : return ret;
2126 : }
2127 :
2128 112994167 : if (list->count == 0) {
2129 3152 : return LDB_ERR_NO_SUCH_OBJECT;
2130 : }
2131 :
2132 109665568 : return LDB_SUCCESS;
2133 : }
2134 :
2135 : /*
2136 : return a list of matching objects using a one-level index
2137 : */
2138 1449682 : static int ldb_kv_index_dn_one(struct ldb_module *module,
2139 : struct ldb_kv_private *ldb_kv,
2140 : struct ldb_dn *parent_dn,
2141 : struct dn_list *list,
2142 : enum key_truncation *truncation)
2143 : {
2144 1483887 : int ret = ldb_kv_index_dn_attr(
2145 : module, ldb_kv, LDB_KV_IDXONE, parent_dn, list, truncation);
2146 1449682 : if (ret == LDB_SUCCESS) {
2147 : /*
2148 : * Ensure we do not shortcut on intersection for this
2149 : * list. We must never be lazy and return an entry
2150 : * not in this list. This allows the index for
2151 : * SCOPE_ONELEVEL to be trusted.
2152 : */
2153 :
2154 537747 : list->strict = true;
2155 : }
2156 1449682 : return ret;
2157 : }
2158 :
2159 : /*
2160 : return a list of matching objects using the DN index
2161 : */
2162 127380164 : static int ldb_kv_index_dn_base_dn(struct ldb_module *module,
2163 : struct ldb_kv_private *ldb_kv,
2164 : struct ldb_dn *base_dn,
2165 : struct dn_list *dn_list,
2166 : enum key_truncation *truncation)
2167 : {
2168 127380164 : const struct ldb_val *guid_val = NULL;
2169 127380164 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
2170 121 : dn_list->dn = talloc_array(dn_list, struct ldb_val, 1);
2171 121 : if (dn_list->dn == NULL) {
2172 0 : return ldb_module_oom(module);
2173 : }
2174 121 : dn_list->dn[0].data = discard_const_p(unsigned char,
2175 : ldb_dn_get_linearized(base_dn));
2176 121 : if (dn_list->dn[0].data == NULL) {
2177 0 : talloc_free(dn_list->dn);
2178 0 : return ldb_module_oom(module);
2179 : }
2180 121 : dn_list->dn[0].length = strlen((char *)dn_list->dn[0].data);
2181 121 : dn_list->count = 1;
2182 :
2183 121 : return LDB_SUCCESS;
2184 : }
2185 :
2186 127380043 : if (ldb_kv->cache->GUID_index_dn_component != NULL) {
2187 127380043 : guid_val = ldb_dn_get_extended_component(
2188 123294857 : base_dn, ldb_kv->cache->GUID_index_dn_component);
2189 : }
2190 :
2191 127380043 : if (guid_val != NULL) {
2192 12581140 : dn_list->dn = talloc_array(dn_list, struct ldb_val, 1);
2193 12581140 : if (dn_list->dn == NULL) {
2194 0 : return ldb_module_oom(module);
2195 : }
2196 12581140 : dn_list->dn[0].data = guid_val->data;
2197 12581140 : dn_list->dn[0].length = guid_val->length;
2198 12581140 : dn_list->count = 1;
2199 :
2200 12581140 : return LDB_SUCCESS;
2201 : }
2202 :
2203 114798903 : return ldb_kv_index_dn_attr(
2204 : module, ldb_kv, LDB_KV_IDXDN, base_dn, dn_list, truncation);
2205 : }
2206 :
2207 : /*
2208 : return a list of dn's that might match a indexed search or
2209 : an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
2210 : */
2211 132167427 : static int ldb_kv_index_dn(struct ldb_module *module,
2212 : struct ldb_kv_private *ldb_kv,
2213 : const struct ldb_parse_tree *tree,
2214 : struct dn_list *list)
2215 : {
2216 132167427 : int ret = LDB_ERR_OPERATIONS_ERROR;
2217 :
2218 132167427 : switch (tree->operation) {
2219 26893921 : case LDB_OP_AND:
2220 26893921 : ret = ldb_kv_index_dn_and(module, ldb_kv, tree, list);
2221 26893921 : break;
2222 :
2223 247425 : case LDB_OP_OR:
2224 247425 : ret = ldb_kv_index_dn_or(module, ldb_kv, tree, list);
2225 247425 : break;
2226 :
2227 8384849 : case LDB_OP_NOT:
2228 8384849 : ret = ldb_kv_index_dn_not(module, ldb_kv, tree, list);
2229 8384849 : break;
2230 :
2231 95906810 : case LDB_OP_EQUALITY:
2232 95906810 : ret = ldb_kv_index_dn_leaf(module, ldb_kv, tree, list);
2233 95906810 : break;
2234 :
2235 3003 : case LDB_OP_GREATER:
2236 3051 : ret = ldb_kv_index_dn_greater(module, ldb_kv, tree, list);
2237 3051 : break;
2238 :
2239 375 : case LDB_OP_LESS:
2240 423 : ret = ldb_kv_index_dn_less(module, ldb_kv, tree, list);
2241 423 : break;
2242 :
2243 379681 : case LDB_OP_SUBSTRING:
2244 : case LDB_OP_PRESENT:
2245 : case LDB_OP_APPROX:
2246 : case LDB_OP_EXTENDED:
2247 : /* we can't index with fancy bitops yet */
2248 379681 : ret = LDB_ERR_OPERATIONS_ERROR;
2249 379681 : break;
2250 : }
2251 :
2252 132167427 : return ret;
2253 : }
2254 :
2255 : /*
2256 : filter a candidate dn_list from an indexed search into a set of results
2257 : extracting just the given attributes
2258 : */
2259 87903542 : static int ldb_kv_index_filter(struct ldb_kv_private *ldb_kv,
2260 : const struct dn_list *dn_list,
2261 : struct ldb_kv_context *ac,
2262 : uint32_t *match_count,
2263 : enum key_truncation scope_one_truncation)
2264 : {
2265 87903542 : struct ldb_context *ldb = ldb_module_get_ctx(ac->module);
2266 2037932 : struct ldb_message *msg;
2267 2037932 : unsigned int i;
2268 87903542 : unsigned int num_keys = 0;
2269 87903542 : uint8_t previous_guid_key[LDB_KV_GUID_KEY_SIZE] = {0};
2270 87903542 : struct ldb_val *keys = NULL;
2271 :
2272 : /*
2273 : * We have to allocate the key list (rather than just walk the
2274 : * caller supplied list) as the callback could change the list
2275 : * (by modifying an indexed attribute hosted in the in-memory
2276 : * index cache!)
2277 : */
2278 87903542 : keys = talloc_array(ac, struct ldb_val, dn_list->count);
2279 87903542 : if (keys == NULL) {
2280 0 : return ldb_module_oom(ac->module);
2281 : }
2282 :
2283 87903542 : if (ldb_kv->cache->GUID_index_attribute != NULL) {
2284 : /*
2285 : * We speculate that the keys will be GUID based and so
2286 : * pre-fill in enough space for a GUID (avoiding a pile of
2287 : * small allocations)
2288 : */
2289 1977628 : struct guid_tdb_key {
2290 : uint8_t guid_key[LDB_KV_GUID_KEY_SIZE];
2291 87661387 : } *key_values = NULL;
2292 :
2293 87661387 : key_values = talloc_array(keys,
2294 : struct guid_tdb_key,
2295 : dn_list->count);
2296 :
2297 87661387 : if (key_values == NULL) {
2298 0 : talloc_free(keys);
2299 0 : return ldb_module_oom(ac->module);
2300 : }
2301 230435423 : for (i = 0; i < dn_list->count; i++) {
2302 142774036 : keys[i].data = key_values[i].guid_key;
2303 142774036 : keys[i].length = sizeof(key_values[i].guid_key);
2304 : }
2305 : } else {
2306 550754 : for (i = 0; i < dn_list->count; i++) {
2307 308599 : keys[i].data = NULL;
2308 308599 : keys[i].length = 0;
2309 : }
2310 : }
2311 :
2312 230986177 : for (i = 0; i < dn_list->count; i++) {
2313 2623655 : int ret;
2314 :
2315 145706290 : ret = ldb_kv_idx_to_key(
2316 143082635 : ac->module, ldb_kv, keys, &dn_list->dn[i], &keys[num_keys]);
2317 143082635 : if (ret != LDB_SUCCESS) {
2318 0 : talloc_free(keys);
2319 0 : return ret;
2320 : }
2321 :
2322 143082635 : if (ldb_kv->cache->GUID_index_attribute != NULL) {
2323 : /*
2324 : * If we are in GUID index mode, then the dn_list is
2325 : * sorted. If we got a duplicate, forget about it, as
2326 : * otherwise we would send the same entry back more
2327 : * than once.
2328 : *
2329 : * This is needed in the truncated DN case, or if a
2330 : * duplicate was forced in via
2331 : * LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK
2332 : */
2333 :
2334 142774060 : if (memcmp(previous_guid_key,
2335 142774036 : keys[num_keys].data,
2336 : sizeof(previous_guid_key)) == 0) {
2337 24 : continue;
2338 : }
2339 :
2340 145397651 : memcpy(previous_guid_key,
2341 142774012 : keys[num_keys].data,
2342 : sizeof(previous_guid_key));
2343 : }
2344 143082611 : num_keys++;
2345 : }
2346 :
2347 :
2348 : /*
2349 : * Now that the list is a safe copy, send the callbacks
2350 : */
2351 230930165 : for (i = 0; i < num_keys; i++) {
2352 2623639 : int ret;
2353 2623639 : bool matched;
2354 :
2355 : /*
2356 : * Check the time every 64 records, to reduce calls to
2357 : * gettimeofday(). This is a compromise, not all
2358 : * calls to ldb_match_message() will take the same
2359 : * time, most will run quickly but by luck it might be
2360 : * possible to have 64 records that are slow, doing a
2361 : * recursive search via LDAP_MATCHING_RULE_IN_CHAIN.
2362 : *
2363 : * Thankfully this is after index processing so only
2364 : * on the subset that matches some index (but still
2365 : * possibly a big one like objectclass=user)
2366 : */
2367 143080380 : if (i % 64 == 0) {
2368 88702635 : struct timeval now = tevent_timeval_current();
2369 88702635 : int timeval_cmp = tevent_timeval_compare(&ac->timeout_timeval,
2370 : &now);
2371 :
2372 : /*
2373 : * The search has taken too long. This is the
2374 : * most likely place for our time to expire,
2375 : * as we are checking the records after the
2376 : * index set intersection. This is now the
2377 : * slow process of checking if the records
2378 : * actually match.
2379 : *
2380 : * The tevent based timeout is not likely to
2381 : * be hit, sadly, as we don't run an event
2382 : * loop.
2383 : *
2384 : * While we are indexed and most of the work
2385 : * should have been done already, the
2386 : * ldb_match_* calls can be quite expensive if
2387 : * the caller uses LDAP_MATCHING_RULE_IN_CHAIN
2388 : */
2389 88702635 : if (timeval_cmp <= 0) {
2390 0 : talloc_free(keys);
2391 0 : return LDB_ERR_TIME_LIMIT_EXCEEDED;
2392 : }
2393 : }
2394 :
2395 143080380 : msg = ldb_msg_new(ac);
2396 143080380 : if (!msg) {
2397 0 : talloc_free(keys);
2398 0 : return LDB_ERR_OPERATIONS_ERROR;
2399 : }
2400 :
2401 2623639 : ret =
2402 145704019 : ldb_kv_search_key(ac->module,
2403 : ldb_kv,
2404 143080380 : keys[i],
2405 : msg,
2406 : LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC |
2407 : /*
2408 : * The entry point ldb_kv_search_indexed is
2409 : * only called from the read-locked
2410 : * ldb_kv_search.
2411 : */
2412 : LDB_UNPACK_DATA_FLAG_READ_LOCKED);
2413 143080380 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
2414 : /*
2415 : * the record has disappeared? yes, this can
2416 : * happen if the entry is deleted by something
2417 : * operating in the callback (not another
2418 : * process, as we have a read lock)
2419 : */
2420 66343486 : talloc_free(msg);
2421 74128154 : continue;
2422 : }
2423 :
2424 76736894 : if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
2425 : /* an internal error */
2426 0 : talloc_free(keys);
2427 0 : talloc_free(msg);
2428 0 : return LDB_ERR_OPERATIONS_ERROR;
2429 : }
2430 :
2431 : /*
2432 : * We trust the index for LDB_SCOPE_ONELEVEL
2433 : * unless the index key has been truncated.
2434 : *
2435 : * LDB_SCOPE_BASE is not passed in by our only caller.
2436 : */
2437 76736894 : if (ac->scope != LDB_SCOPE_ONELEVEL ||
2438 4353013 : !ldb_kv->cache->one_level_indexes ||
2439 : scope_one_truncation != KEY_NOT_TRUNCATED)
2440 : {
2441 : /*
2442 : * The redaction callback may be expensive to call if it
2443 : * fetches a security descriptor. Check the DN early and
2444 : * bail out if it doesn't match the base.
2445 : */
2446 72385867 : if (!ldb_match_scope(ldb, ac->base, msg->dn, ac->scope)) {
2447 314834 : talloc_free(msg);
2448 314834 : continue;
2449 : }
2450 : }
2451 :
2452 76422060 : if (ldb->redact.callback != NULL) {
2453 76172621 : ret = ldb->redact.callback(ldb->redact.module, ac->req, msg);
2454 76172621 : if (ret != LDB_SUCCESS) {
2455 0 : talloc_free(msg);
2456 0 : return ret;
2457 : }
2458 : }
2459 :
2460 76422060 : ret = ldb_match_message(ldb, msg, ac->tree,
2461 : ac->scope, &matched);
2462 76422060 : if (ret != LDB_SUCCESS) {
2463 0 : talloc_free(keys);
2464 0 : talloc_free(msg);
2465 0 : return ret;
2466 : }
2467 76422060 : if (!matched) {
2468 7469834 : talloc_free(msg);
2469 7469834 : continue;
2470 : }
2471 :
2472 68952226 : ret = ldb_msg_add_distinguished_name(msg);
2473 68952226 : if (ret == -1) {
2474 0 : talloc_free(msg);
2475 0 : return LDB_ERR_OPERATIONS_ERROR;
2476 : }
2477 :
2478 : /* filter the attributes that the user wants */
2479 68952226 : ret = ldb_kv_filter_attrs_in_place(msg, ac->attrs);
2480 68952226 : if (ret != LDB_SUCCESS) {
2481 0 : talloc_free(keys);
2482 0 : talloc_free(msg);
2483 0 : return LDB_ERR_OPERATIONS_ERROR;
2484 : }
2485 :
2486 68952226 : ldb_msg_shrink_to_fit(msg);
2487 :
2488 : /* Ensure the message elements are all talloc'd. */
2489 68952226 : ret = ldb_msg_elements_take_ownership(msg);
2490 68952226 : if (ret != LDB_SUCCESS) {
2491 0 : talloc_free(keys);
2492 0 : talloc_free(msg);
2493 0 : return LDB_ERR_OPERATIONS_ERROR;
2494 : }
2495 :
2496 68952226 : ret = ldb_module_send_entry(ac->req, msg, NULL);
2497 68952226 : if (ret != LDB_SUCCESS) {
2498 : /* Regardless of success or failure, the msg
2499 : * is the callbacks responsibility, and should
2500 : * not be talloc_free()'ed */
2501 53757 : ac->request_terminated = true;
2502 53757 : talloc_free(keys);
2503 53757 : return ret;
2504 : }
2505 :
2506 68898469 : (*match_count)++;
2507 : }
2508 :
2509 87849785 : TALLOC_FREE(keys);
2510 87849785 : return LDB_SUCCESS;
2511 : }
2512 :
2513 : /*
2514 : sort a DN list
2515 : */
2516 164810 : static void ldb_kv_dn_list_sort(struct ldb_kv_private *ltdb,
2517 : struct dn_list *list)
2518 : {
2519 164810 : if (list->count < 2) {
2520 74609 : return;
2521 : }
2522 :
2523 : /* We know the list is sorted when using the GUID index */
2524 88746 : if (ltdb->cache->GUID_index_attribute != NULL) {
2525 86982 : return;
2526 : }
2527 :
2528 862 : TYPESAFE_QSORT(list->dn, list->count,
2529 : ldb_val_equal_exact_for_qsort);
2530 : }
2531 :
2532 : /*
2533 : search the database with a LDAP-like expression using indexes
2534 : returns -1 if an indexed search is not possible, in which
2535 : case the caller should call ltdb_search_full()
2536 : */
2537 96062974 : int ldb_kv_search_indexed(struct ldb_kv_context *ac, uint32_t *match_count)
2538 : {
2539 96062974 : struct ldb_context *ldb = ldb_module_get_ctx(ac->module);
2540 96062974 : struct ldb_kv_private *ldb_kv = talloc_get_type(
2541 : ldb_module_get_private(ac->module), struct ldb_kv_private);
2542 2341374 : struct dn_list *dn_list;
2543 2341374 : int ret;
2544 2341374 : enum ldb_scope index_scope;
2545 96062974 : enum key_truncation scope_one_truncation = KEY_NOT_TRUNCATED;
2546 :
2547 : /* see if indexing is enabled */
2548 96062974 : if (!ldb_kv->cache->attribute_indexes &&
2549 12480 : !ldb_kv->cache->one_level_indexes && ac->scope != LDB_SCOPE_BASE) {
2550 : /* fallback to a full search */
2551 11548 : return LDB_ERR_OPERATIONS_ERROR;
2552 : }
2553 :
2554 96050831 : dn_list = talloc_zero(ac, struct dn_list);
2555 96050831 : if (dn_list == NULL) {
2556 0 : return ldb_module_oom(ac->module);
2557 : }
2558 :
2559 : /*
2560 : * For the purposes of selecting the switch arm below, if we
2561 : * don't have a one-level index then treat it like a subtree
2562 : * search
2563 : */
2564 96050831 : if (ac->scope == LDB_SCOPE_ONELEVEL &&
2565 1450593 : !ldb_kv->cache->one_level_indexes) {
2566 888 : index_scope = LDB_SCOPE_SUBTREE;
2567 : } else {
2568 96049920 : index_scope = ac->scope;
2569 : }
2570 :
2571 96050808 : switch (index_scope) {
2572 0 : case LDB_SCOPE_BASE:
2573 : /*
2574 : * The only caller will have filtered the operation out
2575 : * so we should never get here
2576 : */
2577 0 : return ldb_operr(ldb);
2578 :
2579 1449682 : case LDB_SCOPE_ONELEVEL:
2580 :
2581 : /*
2582 : * First, load all the one-level child objects (regardless of
2583 : * whether they match the search filter or not). The database
2584 : * maintains a one-level index, so retrieving this is quick.
2585 : */
2586 1449682 : ret = ldb_kv_index_dn_one(ac->module,
2587 : ldb_kv,
2588 : ac->base,
2589 : dn_list,
2590 : &scope_one_truncation);
2591 1449682 : if (ret != LDB_SUCCESS) {
2592 911935 : talloc_free(dn_list);
2593 911935 : return ret;
2594 : }
2595 :
2596 : /*
2597 : * If we have too many children, running ldb_kv_index_filter()
2598 : * over all the child objects can be quite expensive. So next
2599 : * we do a separate indexed query using the search filter.
2600 : *
2601 : * This should be quick, but it may return objects that are not
2602 : * the direct one-level child objects we're interested in.
2603 : *
2604 : * We only do this in the GUID index mode, which is
2605 : * O(n*log(m)) otherwise the intersection below will
2606 : * be too costly at O(n*m).
2607 : *
2608 : * We don't set a heuristic for 'too many' but instead
2609 : * do it always and rely on the index lookup being
2610 : * fast enough in the small case.
2611 : */
2612 537747 : if (ldb_kv->cache->GUID_index_attribute != NULL) {
2613 17503 : struct dn_list *indexed_search_result
2614 537438 : = talloc_zero(ac, struct dn_list);
2615 537438 : if (indexed_search_result == NULL) {
2616 0 : talloc_free(dn_list);
2617 0 : return ldb_module_oom(ac->module);
2618 : }
2619 :
2620 537438 : if (!ldb_kv->cache->attribute_indexes) {
2621 94 : talloc_free(indexed_search_result);
2622 94 : talloc_free(dn_list);
2623 94 : return LDB_ERR_OPERATIONS_ERROR;
2624 : }
2625 :
2626 : /*
2627 : * Try to do an indexed database search
2628 : */
2629 537344 : ret = ldb_kv_index_dn(
2630 : ac->module, ldb_kv, ac->tree,
2631 : indexed_search_result);
2632 :
2633 : /*
2634 : * We can stop if we're sure the object doesn't exist
2635 : */
2636 537344 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
2637 18860 : talloc_free(indexed_search_result);
2638 18860 : talloc_free(dn_list);
2639 18860 : return LDB_ERR_NO_SUCH_OBJECT;
2640 : }
2641 :
2642 : /*
2643 : * Once we have a successful search result, we
2644 : * intersect it with the one-level children (dn_list).
2645 : * This should give us exactly the result we're after
2646 : * (we still need to run ldb_kv_index_filter() to
2647 : * handle potential index truncation cases).
2648 : *
2649 : * The indexed search may fail because we don't support
2650 : * indexing on that type of search operation, e.g.
2651 : * matching against '*'. In which case we fall through
2652 : * and run ldb_kv_index_filter() over all the one-level
2653 : * children (which is still better than bailing out here
2654 : * and falling back to a full DB scan).
2655 : */
2656 518484 : if (ret == LDB_SUCCESS) {
2657 430028 : if (!list_intersect(ldb_kv,
2658 : dn_list,
2659 : indexed_search_result)) {
2660 0 : talloc_free(indexed_search_result);
2661 0 : talloc_free(dn_list);
2662 0 : return LDB_ERR_OPERATIONS_ERROR;
2663 : }
2664 : }
2665 : }
2666 501917 : break;
2667 :
2668 94601149 : case LDB_SCOPE_SUBTREE:
2669 : case LDB_SCOPE_DEFAULT:
2670 94601149 : if (!ldb_kv->cache->attribute_indexes) {
2671 235 : talloc_free(dn_list);
2672 235 : return LDB_ERR_OPERATIONS_ERROR;
2673 : }
2674 : /*
2675 : * Here we load the index for the tree. We have no
2676 : * index for the subtree.
2677 : */
2678 94600914 : ret = ldb_kv_index_dn(ac->module, ldb_kv, ac->tree, dn_list);
2679 94600914 : if (ret != LDB_SUCCESS) {
2680 7216165 : talloc_free(dn_list);
2681 7216165 : return ret;
2682 : }
2683 85363693 : break;
2684 : }
2685 :
2686 : /*
2687 : * It is critical that this function do the re-filter even
2688 : * on things found by the index as the index can over-match
2689 : * in cases of truncation (as well as when it decides it is
2690 : * not worth further filtering)
2691 : *
2692 : * If this changes, then the index code above would need to
2693 : * pass up a flag to say if any index was truncated during
2694 : * processing as the truncation here refers only to the
2695 : * SCOPE_ONELEVEL index.
2696 : */
2697 87903542 : ret = ldb_kv_index_filter(
2698 : ldb_kv, dn_list, ac, match_count, scope_one_truncation);
2699 87903542 : talloc_free(dn_list);
2700 87903542 : return ret;
2701 : }
2702 :
2703 : /**
2704 : * @brief Add a DN in the index list of a given attribute name/value pair
2705 : *
2706 : * This function will add the DN in the index list for the index for
2707 : * the given attribute name and value.
2708 : *
2709 : * @param[in] module A ldb_module structure
2710 : *
2711 : * @param[in] dn The string representation of the DN as it
2712 : * will be stored in the index entry
2713 : *
2714 : * @param[in] el A ldb_message_element array, one of the entry
2715 : * referred by the v_idx is the attribute name and
2716 : * value pair which will be used to construct the
2717 : * index name
2718 : *
2719 : * @param[in] v_idx The index of element in the el array to use
2720 : *
2721 : * @return An ldb error code
2722 : */
2723 23794213 : static int ldb_kv_index_add1(struct ldb_module *module,
2724 : struct ldb_kv_private *ldb_kv,
2725 : const struct ldb_message *msg,
2726 : struct ldb_message_element *el,
2727 : int v_idx)
2728 : {
2729 2115796 : struct ldb_context *ldb;
2730 2115796 : struct ldb_dn *dn_key;
2731 2115796 : int ret;
2732 2115796 : const struct ldb_schema_attribute *a;
2733 2115796 : struct dn_list *list;
2734 2115796 : unsigned alloc_len;
2735 23794213 : enum key_truncation truncation = KEY_TRUNCATED;
2736 :
2737 :
2738 23794213 : ldb = ldb_module_get_ctx(module);
2739 :
2740 23794213 : list = talloc_zero(module, struct dn_list);
2741 23794213 : if (list == NULL) {
2742 0 : return LDB_ERR_OPERATIONS_ERROR;
2743 : }
2744 :
2745 25910009 : dn_key = ldb_kv_index_key(ldb,
2746 : list,
2747 : ldb_kv,
2748 : el->name,
2749 23794213 : &el->values[v_idx],
2750 : &a,
2751 : &truncation);
2752 23794213 : if (!dn_key) {
2753 0 : talloc_free(list);
2754 0 : return LDB_ERR_OPERATIONS_ERROR;
2755 : }
2756 : /*
2757 : * Samba only maintains unique indexes on the objectSID and objectGUID
2758 : * so if a unique index key exceeds the maximum length there is a
2759 : * problem.
2760 : */
2761 23794213 : if ((truncation == KEY_TRUNCATED) && (a != NULL &&
2762 100 : (a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX ||
2763 96 : (el->flags & LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX)))) {
2764 :
2765 4 : ldb_asprintf_errstring(
2766 : ldb,
2767 : __location__ ": unique index key on %s in %s, "
2768 : "exceeds maximum key length of %u (encoded).",
2769 : el->name,
2770 4 : ldb_dn_get_linearized(msg->dn),
2771 : ldb_kv->max_key_length);
2772 4 : talloc_free(list);
2773 4 : return LDB_ERR_CONSTRAINT_VIOLATION;
2774 : }
2775 :
2776 23794209 : ret = ldb_kv_dn_list_load(module, ldb_kv, dn_key, list,
2777 : DN_LIST_MUTABLE);
2778 23794209 : if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
2779 0 : talloc_free(list);
2780 0 : return ret;
2781 : }
2782 :
2783 : /*
2784 : * Check for duplicates in the @IDXDN DN -> GUID record
2785 : *
2786 : * This is very normal, it just means a duplicate DN creation
2787 : * was attempted, so don't set the error string or print scary
2788 : * messages.
2789 : */
2790 23794209 : if (list->count > 0 &&
2791 12284361 : ldb_attr_cmp(el->name, LDB_KV_IDXDN) == 0 &&
2792 423 : truncation == KEY_NOT_TRUNCATED) {
2793 :
2794 323 : talloc_free(list);
2795 323 : return LDB_ERR_CONSTRAINT_VIOLATION;
2796 :
2797 23793886 : } else if (list->count > 0
2798 12284038 : && ldb_attr_cmp(el->name, LDB_KV_IDXDN) == 0) {
2799 :
2800 : /*
2801 : * At least one existing entry in the DN->GUID index, which
2802 : * arises when the DN indexes have been truncated
2803 : *
2804 : * So need to pull the DN's to check if it's really a duplicate
2805 : */
2806 : unsigned int i;
2807 216 : for (i=0; i < list->count; i++) {
2808 128 : uint8_t guid_key[LDB_KV_GUID_KEY_SIZE];
2809 128 : struct ldb_val key = {
2810 : .data = guid_key,
2811 : .length = sizeof(guid_key)
2812 : };
2813 128 : const int flags = LDB_UNPACK_DATA_FLAG_NO_ATTRS;
2814 128 : struct ldb_message *rec = ldb_msg_new(ldb);
2815 128 : if (rec == NULL) {
2816 12 : return LDB_ERR_OPERATIONS_ERROR;
2817 : }
2818 :
2819 256 : ret = ldb_kv_idx_to_key(
2820 128 : module, ldb_kv, ldb, &list->dn[i], &key);
2821 128 : if (ret != LDB_SUCCESS) {
2822 0 : TALLOC_FREE(list);
2823 0 : TALLOC_FREE(rec);
2824 0 : return ret;
2825 : }
2826 :
2827 128 : ret =
2828 128 : ldb_kv_search_key(module, ldb_kv, key, rec, flags);
2829 128 : if (key.data != guid_key) {
2830 0 : TALLOC_FREE(key.data);
2831 : }
2832 128 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
2833 : /*
2834 : * the record has disappeared?
2835 : * yes, this can happen
2836 : */
2837 0 : talloc_free(rec);
2838 0 : continue;
2839 : }
2840 :
2841 128 : if (ret != LDB_SUCCESS) {
2842 : /* an internal error */
2843 0 : TALLOC_FREE(rec);
2844 0 : TALLOC_FREE(list);
2845 0 : return LDB_ERR_OPERATIONS_ERROR;
2846 : }
2847 : /*
2848 : * The DN we are trying to add to the DB and index
2849 : * is already here, so we must deny the addition
2850 : */
2851 128 : if (ldb_dn_compare(msg->dn, rec->dn) == 0) {
2852 12 : TALLOC_FREE(rec);
2853 12 : TALLOC_FREE(list);
2854 12 : return LDB_ERR_CONSTRAINT_VIOLATION;
2855 : }
2856 : }
2857 : }
2858 :
2859 : /*
2860 : * Check for duplicates in unique indexes
2861 : *
2862 : * We don't need to do a loop test like the @IDXDN case
2863 : * above as we have a ban on long unique index values
2864 : * at the start of this function.
2865 : */
2866 23793874 : if (list->count > 0 &&
2867 12284026 : ((a != NULL
2868 10155416 : && (a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX ||
2869 10155383 : (el->flags & LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX))))) {
2870 : /*
2871 : * We do not want to print info about a possibly
2872 : * confidential DN that the conflict was with in the
2873 : * user-visible error string
2874 : */
2875 :
2876 37 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
2877 34 : ldb_debug(ldb, LDB_DEBUG_WARNING,
2878 : __location__
2879 : ": unique index violation on %s in %s, "
2880 : "conflicts with %*.*s in %s",
2881 17 : el->name, ldb_dn_get_linearized(msg->dn),
2882 14 : (int)list->dn[0].length,
2883 17 : (int)list->dn[0].length,
2884 17 : list->dn[0].data,
2885 : ldb_dn_get_linearized(dn_key));
2886 : } else {
2887 : /* This can't fail, gives a default at worst */
2888 7 : const struct ldb_schema_attribute *attr =
2889 20 : ldb_schema_attribute_by_name(
2890 13 : ldb, ldb_kv->cache->GUID_index_attribute);
2891 7 : struct ldb_val v;
2892 27 : ret = attr->syntax->ldif_write_fn(ldb, list,
2893 20 : &list->dn[0], &v);
2894 20 : if (ret == LDB_SUCCESS) {
2895 40 : ldb_debug(ldb,
2896 : LDB_DEBUG_WARNING,
2897 : __location__
2898 : ": unique index violation on %s in "
2899 : "%s, conflicts with %s %*.*s in %s",
2900 : el->name,
2901 20 : ldb_dn_get_linearized(msg->dn),
2902 20 : ldb_kv->cache->GUID_index_attribute,
2903 13 : (int)v.length,
2904 20 : (int)v.length,
2905 : v.data,
2906 : ldb_dn_get_linearized(dn_key));
2907 : }
2908 : }
2909 37 : ldb_asprintf_errstring(ldb,
2910 : __location__ ": unique index violation "
2911 : "on %s in %s",
2912 : el->name,
2913 37 : ldb_dn_get_linearized(msg->dn));
2914 37 : talloc_free(list);
2915 37 : return LDB_ERR_CONSTRAINT_VIOLATION;
2916 : }
2917 :
2918 : /* overallocate the list a bit, to reduce the number of
2919 : * realloc triggered copies */
2920 23793837 : alloc_len = ((list->count+1)+7) & ~7;
2921 23793837 : list->dn = talloc_realloc(list, list->dn, struct ldb_val, alloc_len);
2922 23793837 : if (list->dn == NULL) {
2923 0 : talloc_free(list);
2924 0 : return LDB_ERR_OPERATIONS_ERROR;
2925 : }
2926 :
2927 23793837 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
2928 279682 : const char *dn_str = ldb_dn_get_linearized(msg->dn);
2929 279682 : list->dn[list->count].data
2930 279682 : = (uint8_t *)talloc_strdup(list->dn, dn_str);
2931 279682 : if (list->dn[list->count].data == NULL) {
2932 0 : talloc_free(list);
2933 0 : return LDB_ERR_OPERATIONS_ERROR;
2934 : }
2935 279682 : list->dn[list->count].length = strlen(dn_str);
2936 : } else {
2937 1993112 : const struct ldb_val *key_val;
2938 23514155 : struct ldb_val *exact = NULL, *next = NULL;
2939 23514155 : key_val = ldb_msg_find_ldb_val(
2940 21521043 : msg, ldb_kv->cache->GUID_index_attribute);
2941 23514155 : if (key_val == NULL) {
2942 0 : talloc_free(list);
2943 0 : return ldb_module_operr(module);
2944 : }
2945 :
2946 23514155 : if (key_val->length != LDB_KV_GUID_SIZE) {
2947 0 : talloc_free(list);
2948 0 : return ldb_module_operr(module);
2949 : }
2950 :
2951 126778619 : BINARY_ARRAY_SEARCH_GTE(list->dn, list->count,
2952 : *key_val, ldb_val_equal_exact_ordered,
2953 : exact, next);
2954 :
2955 : /*
2956 : * Give a warning rather than fail, this could be a
2957 : * duplicate value in the record allowed by a caller
2958 : * forcing in the value with
2959 : * LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK
2960 : */
2961 22589738 : if (exact != NULL && truncation == KEY_NOT_TRUNCATED) {
2962 : /* This can't fail, gives a default at worst */
2963 0 : const struct ldb_schema_attribute *attr =
2964 8 : ldb_schema_attribute_by_name(
2965 8 : ldb, ldb_kv->cache->GUID_index_attribute);
2966 0 : struct ldb_val v;
2967 8 : ret = attr->syntax->ldif_write_fn(ldb, list,
2968 : exact, &v);
2969 8 : if (ret == LDB_SUCCESS) {
2970 16 : ldb_debug(ldb,
2971 : LDB_DEBUG_WARNING,
2972 : __location__
2973 : ": duplicate attribute value in %s "
2974 : "for index on %s, "
2975 : "duplicate of %s %*.*s in %s",
2976 8 : ldb_dn_get_linearized(msg->dn),
2977 : el->name,
2978 8 : ldb_kv->cache->GUID_index_attribute,
2979 8 : (int)v.length,
2980 8 : (int)v.length,
2981 : v.data,
2982 : ldb_dn_get_linearized(dn_key));
2983 : }
2984 : }
2985 :
2986 23514155 : if (next == NULL) {
2987 13845291 : next = &list->dn[list->count];
2988 : } else {
2989 11661976 : memmove(&next[1], next,
2990 9668864 : sizeof(*next) * (list->count - (next - list->dn)));
2991 : }
2992 23514155 : *next = ldb_val_dup(list->dn, key_val);
2993 23514155 : if (next->data == NULL) {
2994 0 : talloc_free(list);
2995 0 : return ldb_module_operr(module);
2996 : }
2997 : }
2998 23793837 : list->count++;
2999 :
3000 23793837 : ret = ldb_kv_dn_list_store(module, dn_key, list);
3001 :
3002 23793837 : talloc_free(list);
3003 :
3004 23793837 : return ret;
3005 : }
3006 :
3007 : /*
3008 : add index entries for one elements in a message
3009 : */
3010 15377584 : static int ldb_kv_index_add_el(struct ldb_module *module,
3011 : struct ldb_kv_private *ldb_kv,
3012 : const struct ldb_message *msg,
3013 : struct ldb_message_element *el)
3014 : {
3015 : unsigned int i;
3016 36313706 : for (i = 0; i < el->num_values; i++) {
3017 19412351 : int ret = ldb_kv_index_add1(module, ldb_kv, msg, el, i);
3018 19412351 : if (ret != LDB_SUCCESS) {
3019 27 : return ret;
3020 : }
3021 : }
3022 :
3023 15377557 : return LDB_SUCCESS;
3024 : }
3025 :
3026 : /*
3027 : add index entries for all elements in a message
3028 : */
3029 2325254 : static int ldb_kv_index_add_all(struct ldb_module *module,
3030 : struct ldb_kv_private *ldb_kv,
3031 : const struct ldb_message *msg)
3032 : {
3033 2325254 : struct ldb_message_element *elements = msg->elements;
3034 203843 : unsigned int i;
3035 203843 : const char *dn_str;
3036 203843 : int ret;
3037 :
3038 2325254 : if (ldb_dn_is_special(msg->dn)) {
3039 0 : return LDB_SUCCESS;
3040 : }
3041 :
3042 2325254 : dn_str = ldb_dn_get_linearized(msg->dn);
3043 2325254 : if (dn_str == NULL) {
3044 0 : return LDB_ERR_OPERATIONS_ERROR;
3045 : }
3046 :
3047 2325254 : ret = ldb_kv_write_index_dn_guid(module, msg, 1);
3048 2325254 : if (ret != LDB_SUCCESS) {
3049 315 : return ret;
3050 : }
3051 :
3052 2324919 : if (!ldb_kv->cache->attribute_indexes) {
3053 : /* no indexed fields */
3054 76853 : return LDB_SUCCESS;
3055 : }
3056 :
3057 45708111 : for (i = 0; i < msg->num_elements; i++) {
3058 43462727 : if (!ldb_kv_is_indexed(module, ldb_kv, elements[i].name)) {
3059 27183268 : continue;
3060 : }
3061 16279459 : ret = ldb_kv_index_add_el(module, ldb_kv, msg, &elements[i]);
3062 16279459 : if (ret != LDB_SUCCESS) {
3063 41 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3064 41 : ldb_asprintf_errstring(ldb,
3065 : __location__ ": Failed to re-index %s in %s - %s",
3066 27 : elements[i].name, dn_str,
3067 : ldb_errstring(ldb));
3068 41 : return ret;
3069 : }
3070 : }
3071 :
3072 2044216 : return LDB_SUCCESS;
3073 : }
3074 :
3075 :
3076 : /*
3077 : insert a DN index for a message
3078 : */
3079 4544547 : static int ldb_kv_modify_index_dn(struct ldb_module *module,
3080 : struct ldb_kv_private *ldb_kv,
3081 : const struct ldb_message *msg,
3082 : struct ldb_dn *dn,
3083 : const char *index,
3084 : int add)
3085 : {
3086 388545 : struct ldb_message_element el;
3087 388545 : struct ldb_val val;
3088 388545 : int ret;
3089 :
3090 4544547 : val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn));
3091 4544547 : if (val.data == NULL) {
3092 0 : const char *dn_str = ldb_dn_get_linearized(dn);
3093 0 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
3094 : __location__ ": Failed to modify %s "
3095 : "against %s in %s: failed "
3096 : "to get casefold DN",
3097 : index,
3098 0 : ldb_kv->cache->GUID_index_attribute,
3099 : dn_str);
3100 0 : return LDB_ERR_OPERATIONS_ERROR;
3101 : }
3102 :
3103 4544547 : val.length = strlen((char *)val.data);
3104 4544547 : el.name = index;
3105 4544547 : el.values = &val;
3106 4544547 : el.num_values = 1;
3107 :
3108 4544547 : if (add) {
3109 4381862 : ret = ldb_kv_index_add1(module, ldb_kv, msg, &el, 0);
3110 : } else { /* delete */
3111 162685 : ret = ldb_kv_index_del_value(module, ldb_kv, msg, &el, 0);
3112 : }
3113 :
3114 4544547 : if (ret != LDB_SUCCESS) {
3115 335 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3116 335 : const char *dn_str = ldb_dn_get_linearized(dn);
3117 335 : ldb_asprintf_errstring(ldb,
3118 : __location__ ": Failed to modify %s "
3119 : "against %s in %s - %s",
3120 : index,
3121 335 : ldb_kv->cache->GUID_index_attribute,
3122 : dn_str,
3123 : ldb_errstring(ldb));
3124 335 : return ret;
3125 : }
3126 4155687 : return ret;
3127 : }
3128 :
3129 : /*
3130 : insert a one level index for a message
3131 : */
3132 2412523 : static int ldb_kv_index_onelevel(struct ldb_module *module,
3133 : const struct ldb_message *msg,
3134 : int add)
3135 : {
3136 2412523 : struct ldb_kv_private *ldb_kv = talloc_get_type(
3137 : ldb_module_get_private(module), struct ldb_kv_private);
3138 204450 : struct ldb_dn *pdn;
3139 204450 : int ret;
3140 :
3141 : /* We index for ONE Level only if requested */
3142 2412523 : if (!ldb_kv->cache->one_level_indexes) {
3143 134027 : return LDB_SUCCESS;
3144 : }
3145 :
3146 2273884 : pdn = ldb_dn_get_parent(module, msg->dn);
3147 2273884 : if (pdn == NULL) {
3148 0 : return LDB_ERR_OPERATIONS_ERROR;
3149 : }
3150 199838 : ret =
3151 2273884 : ldb_kv_modify_index_dn(module, ldb_kv, msg, pdn, LDB_KV_IDXONE, add);
3152 :
3153 2273884 : talloc_free(pdn);
3154 :
3155 2273884 : return ret;
3156 : }
3157 :
3158 : /*
3159 : insert a one level index for a message
3160 : */
3161 2412887 : static int ldb_kv_write_index_dn_guid(struct ldb_module *module,
3162 : const struct ldb_message *msg,
3163 : int add)
3164 : {
3165 204484 : int ret;
3166 2412887 : struct ldb_kv_private *ldb_kv = talloc_get_type(
3167 : ldb_module_get_private(module), struct ldb_kv_private);
3168 :
3169 : /* We index for DN only if using a GUID index */
3170 2412887 : if (ldb_kv->cache->GUID_index_attribute == NULL) {
3171 126447 : return LDB_SUCCESS;
3172 : }
3173 :
3174 2459370 : ret = ldb_kv_modify_index_dn(
3175 2270663 : module, ldb_kv, msg, msg->dn, LDB_KV_IDXDN, add);
3176 :
3177 2270663 : if (ret == LDB_ERR_CONSTRAINT_VIOLATION) {
3178 335 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
3179 : "Entry %s already exists",
3180 335 : ldb_dn_get_linearized(msg->dn));
3181 335 : ret = LDB_ERR_ENTRY_ALREADY_EXISTS;
3182 : }
3183 2081956 : return ret;
3184 : }
3185 :
3186 : /*
3187 : add the index entries for a new element in a record
3188 : The caller guarantees that these element values are not yet indexed
3189 : */
3190 4928877 : int ldb_kv_index_add_element(struct ldb_module *module,
3191 : struct ldb_kv_private *ldb_kv,
3192 : const struct ldb_message *msg,
3193 : struct ldb_message_element *el)
3194 : {
3195 4928877 : if (ldb_dn_is_special(msg->dn)) {
3196 2709960 : return LDB_SUCCESS;
3197 : }
3198 2088424 : if (!ldb_kv_is_indexed(module, ldb_kv, el->name)) {
3199 1419434 : return LDB_SUCCESS;
3200 : }
3201 799483 : return ldb_kv_index_add_el(module, ldb_kv, msg, el);
3202 : }
3203 :
3204 : /*
3205 : add the index entries for a new record
3206 : */
3207 1152300 : int ldb_kv_index_add_new(struct ldb_module *module,
3208 : struct ldb_kv_private *ldb_kv,
3209 : const struct ldb_message *msg)
3210 : {
3211 89826 : int ret;
3212 :
3213 1152300 : if (ldb_dn_is_special(msg->dn)) {
3214 14039 : return LDB_SUCCESS;
3215 : }
3216 :
3217 1136872 : ret = ldb_kv_index_add_all(module, ldb_kv, msg);
3218 1136872 : if (ret != LDB_SUCCESS) {
3219 : /*
3220 : * Because we can't trust the caller to be doing
3221 : * transactions properly, clean up any index for this
3222 : * entry rather than relying on a transaction
3223 : * cleanup
3224 : */
3225 :
3226 364 : ldb_kv_index_delete(module, msg);
3227 364 : return ret;
3228 : }
3229 :
3230 1136508 : ret = ldb_kv_index_onelevel(module, msg, 1);
3231 1136508 : if (ret != LDB_SUCCESS) {
3232 : /*
3233 : * Because we can't trust the caller to be doing
3234 : * transactions properly, clean up any index for this
3235 : * entry rather than relying on a transaction
3236 : * cleanup
3237 : */
3238 0 : ldb_kv_index_delete(module, msg);
3239 0 : return ret;
3240 : }
3241 1048105 : return ret;
3242 : }
3243 :
3244 :
3245 : /*
3246 : delete an index entry for one message element
3247 : */
3248 1796793 : int ldb_kv_index_del_value(struct ldb_module *module,
3249 : struct ldb_kv_private *ldb_kv,
3250 : const struct ldb_message *msg,
3251 : struct ldb_message_element *el,
3252 : unsigned int v_idx)
3253 : {
3254 18367 : struct ldb_context *ldb;
3255 18367 : struct ldb_dn *dn_key;
3256 18367 : const char *dn_str;
3257 18367 : int ret, i;
3258 18367 : unsigned int j;
3259 18367 : struct dn_list *list;
3260 1796793 : struct ldb_dn *dn = msg->dn;
3261 1796793 : enum key_truncation truncation = KEY_NOT_TRUNCATED;
3262 :
3263 1796793 : ldb = ldb_module_get_ctx(module);
3264 :
3265 1796793 : dn_str = ldb_dn_get_linearized(dn);
3266 1796793 : if (dn_str == NULL) {
3267 0 : return LDB_ERR_OPERATIONS_ERROR;
3268 : }
3269 :
3270 1796793 : if (dn_str[0] == '@') {
3271 0 : return LDB_SUCCESS;
3272 : }
3273 :
3274 : /*
3275 : * ldb is being used as the memory context to ldb_kv_index_key
3276 : * as dn_key itself is also used as the TALLOC_CTX for the
3277 : * rest of this function.
3278 : */
3279 1815158 : dn_key = ldb_kv_index_key(ldb,
3280 : ldb,
3281 : ldb_kv,
3282 : el->name,
3283 1796792 : &el->values[v_idx],
3284 : NULL,
3285 : &truncation);
3286 : /*
3287 : * We ignore key truncation in ltdb_index_add1() so
3288 : * match that by ignoring it here as well
3289 : *
3290 : * Multiple values are legitimate and accepted
3291 : */
3292 1796792 : if (!dn_key) {
3293 0 : return LDB_ERR_OPERATIONS_ERROR;
3294 : }
3295 :
3296 1796792 : list = talloc_zero(dn_key, struct dn_list);
3297 1796792 : if (list == NULL) {
3298 0 : talloc_free(dn_key);
3299 0 : return LDB_ERR_OPERATIONS_ERROR;
3300 : }
3301 :
3302 1796792 : ret = ldb_kv_dn_list_load(module, ldb_kv, dn_key, list,
3303 : DN_LIST_MUTABLE);
3304 1796792 : if (ret == LDB_ERR_NO_SUCH_OBJECT) {
3305 : /* it wasn't indexed. Did we have an earlier error? If we did then
3306 : its gone now */
3307 22867 : talloc_free(dn_key);
3308 22867 : return LDB_SUCCESS;
3309 : }
3310 :
3311 1773925 : if (ret != LDB_SUCCESS) {
3312 0 : talloc_free(dn_key);
3313 0 : return ret;
3314 : }
3315 :
3316 : /*
3317 : * Find one of the values matching this message to remove
3318 : */
3319 1773925 : i = ldb_kv_dn_list_find_msg(ldb_kv, list, msg);
3320 1773925 : if (i == -1) {
3321 : /* nothing to delete */
3322 3051 : talloc_free(dn_key);
3323 3051 : return LDB_SUCCESS;
3324 : }
3325 :
3326 1770874 : j = (unsigned int) i;
3327 1770874 : ARRAY_DEL_ELEMENT(list->dn, j, list->count);
3328 1770874 : list->count--;
3329 1770874 : if (list->count == 0) {
3330 1039463 : talloc_free(list->dn);
3331 1039463 : list->dn = NULL;
3332 : } else {
3333 731411 : list->dn = talloc_realloc(list, list->dn, struct ldb_val, list->count);
3334 : }
3335 :
3336 1770874 : ret = ldb_kv_dn_list_store(module, dn_key, list);
3337 :
3338 1770874 : talloc_free(dn_key);
3339 :
3340 1770874 : return ret;
3341 : }
3342 :
3343 : /*
3344 : delete the index entries for a element
3345 : return -1 on failure
3346 : */
3347 6578905 : int ldb_kv_index_del_element(struct ldb_module *module,
3348 : struct ldb_kv_private *ldb_kv,
3349 : const struct ldb_message *msg,
3350 : struct ldb_message_element *el)
3351 : {
3352 192072 : const char *dn_str;
3353 192072 : int ret;
3354 192072 : unsigned int i;
3355 :
3356 6578905 : if (!ldb_kv->cache->attribute_indexes) {
3357 : /* no indexed fields */
3358 89800 : return LDB_SUCCESS;
3359 : }
3360 :
3361 6485323 : dn_str = ldb_dn_get_linearized(msg->dn);
3362 6485323 : if (dn_str == NULL) {
3363 0 : return LDB_ERR_OPERATIONS_ERROR;
3364 : }
3365 :
3366 6485323 : if (dn_str[0] == '@') {
3367 2612672 : return LDB_SUCCESS;
3368 : }
3369 :
3370 3746817 : if (!ldb_kv_is_indexed(module, ldb_kv, el->name)) {
3371 2242678 : return LDB_SUCCESS;
3372 : }
3373 3070432 : for (i = 0; i < el->num_values; i++) {
3374 1611884 : ret = ldb_kv_index_del_value(module, ldb_kv, msg, el, i);
3375 1611884 : if (ret != LDB_SUCCESS) {
3376 0 : return ret;
3377 : }
3378 : }
3379 :
3380 1441683 : return LDB_SUCCESS;
3381 : }
3382 :
3383 : /*
3384 : delete the index entries for a record
3385 : return -1 on failure
3386 : */
3387 87696 : int ldb_kv_index_delete(struct ldb_module *module,
3388 : const struct ldb_message *msg)
3389 : {
3390 87696 : struct ldb_kv_private *ldb_kv = talloc_get_type(
3391 : ldb_module_get_private(module), struct ldb_kv_private);
3392 701 : int ret;
3393 701 : unsigned int i;
3394 :
3395 87696 : if (ldb_dn_is_special(msg->dn)) {
3396 3 : return LDB_SUCCESS;
3397 : }
3398 :
3399 87633 : ret = ldb_kv_index_onelevel(module, msg, 0);
3400 87633 : if (ret != LDB_SUCCESS) {
3401 0 : return ret;
3402 : }
3403 :
3404 87633 : ret = ldb_kv_write_index_dn_guid(module, msg, 0);
3405 87633 : if (ret != LDB_SUCCESS) {
3406 0 : return ret;
3407 : }
3408 :
3409 87633 : if (!ldb_kv->cache->attribute_indexes) {
3410 : /* no indexed fields */
3411 4304 : return LDB_SUCCESS;
3412 : }
3413 :
3414 1687137 : for (i = 0; i < msg->num_elements; i++) {
3415 1609446 : ret = ldb_kv_index_del_element(
3416 1604092 : module, ldb_kv, msg, &msg->elements[i]);
3417 1604092 : if (ret != LDB_SUCCESS) {
3418 0 : return ret;
3419 : }
3420 : }
3421 :
3422 82688 : return LDB_SUCCESS;
3423 : }
3424 :
3425 :
3426 : /*
3427 : traversal function that deletes all @INDEX records in the in-memory
3428 : TDB.
3429 :
3430 : This does not touch the actual DB, that is done at transaction
3431 : commit, which in turn greatly reduces DB churn as we will likely
3432 : be able to do a direct update into the old record.
3433 : */
3434 6832638 : static int delete_index(struct ldb_kv_private *ldb_kv,
3435 : struct ldb_val key,
3436 : _UNUSED_ struct ldb_val data,
3437 : void *state)
3438 : {
3439 6832638 : struct ldb_module *module = state;
3440 6832638 : const char *dnstr = "DN=" LDB_KV_INDEX ":";
3441 673911 : struct dn_list list;
3442 673911 : struct ldb_dn *dn;
3443 673911 : struct ldb_val v;
3444 673911 : int ret;
3445 :
3446 6832638 : if (strncmp((char *)key.data, dnstr, strlen(dnstr)) != 0) {
3447 1107635 : return 0;
3448 : }
3449 : /* we need to put a empty list in the internal tdb for this
3450 : * index entry */
3451 5606019 : list.dn = NULL;
3452 5606019 : list.count = 0;
3453 :
3454 : /* the offset of 3 is to remove the DN= prefix. */
3455 5606019 : v.data = key.data + 3;
3456 5606019 : v.length = strnlen((char *)key.data, key.length) - 3;
3457 :
3458 5606019 : dn = ldb_dn_from_ldb_val(ldb_kv, ldb_module_get_ctx(module), &v);
3459 :
3460 : /*
3461 : * This does not actually touch the DB quite yet, just
3462 : * the in-memory index cache
3463 : */
3464 5606019 : ret = ldb_kv_dn_list_store(module, dn, &list);
3465 5606019 : if (ret != LDB_SUCCESS) {
3466 0 : ldb_asprintf_errstring(ldb_module_get_ctx(module),
3467 : "Unable to store null index for %s\n",
3468 : ldb_dn_get_linearized(dn));
3469 0 : talloc_free(dn);
3470 0 : return -1;
3471 : }
3472 5606019 : talloc_free(dn);
3473 5606019 : return 0;
3474 : }
3475 :
3476 : /*
3477 : traversal function that adds @INDEX records during a re index TODO wrong comment
3478 : */
3479 6868568 : static int re_key(struct ldb_kv_private *ldb_kv,
3480 : struct ldb_val key,
3481 : struct ldb_val val,
3482 : void *state)
3483 : {
3484 691095 : struct ldb_context *ldb;
3485 6868568 : struct ldb_kv_reindex_context *ctx =
3486 : (struct ldb_kv_reindex_context *)state;
3487 6868568 : struct ldb_module *module = ldb_kv->module;
3488 691095 : struct ldb_message *msg;
3489 691095 : int ret;
3490 691095 : struct ldb_val key2;
3491 691095 : bool is_record;
3492 :
3493 6868568 : ldb = ldb_module_get_ctx(module);
3494 :
3495 6868568 : is_record = ldb_kv_key_is_normal_record(key);
3496 6868568 : if (is_record == false) {
3497 5085739 : return 0;
3498 : }
3499 :
3500 1224324 : msg = ldb_msg_new(module);
3501 1224324 : if (msg == NULL) {
3502 0 : return -1;
3503 : }
3504 :
3505 1224324 : ret = ldb_unpack_data(ldb, &val, msg);
3506 1224324 : if (ret != 0) {
3507 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid data for index %s\n",
3508 : ldb_dn_get_linearized(msg->dn));
3509 0 : ctx->error = ret;
3510 0 : talloc_free(msg);
3511 0 : return -1;
3512 : }
3513 :
3514 1224324 : if (msg->dn == NULL) {
3515 0 : ldb_debug(ldb, LDB_DEBUG_ERROR,
3516 : "Refusing to re-index as GUID "
3517 : "key %*.*s with no DN\n",
3518 0 : (int)key.length, (int)key.length,
3519 0 : (char *)key.data);
3520 0 : talloc_free(msg);
3521 0 : return -1;
3522 : }
3523 :
3524 : /* check if the DN key has changed, perhaps due to the case
3525 : insensitivity of an element changing, or a change from DN
3526 : to GUID keys */
3527 1224324 : key2 = ldb_kv_key_msg(module, msg, msg);
3528 1224324 : if (key2.data == NULL) {
3529 : /* probably a corrupt record ... darn */
3530 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s",
3531 : ldb_dn_get_linearized(msg->dn));
3532 0 : talloc_free(msg);
3533 0 : return 0;
3534 : }
3535 1224324 : if (key.length != key2.length ||
3536 1151917 : (memcmp(key.data, key2.data, key.length) != 0)) {
3537 72408 : ldb_kv->kv_ops->update_in_iterate(
3538 : ldb_kv, key, key2, val, ctx);
3539 : }
3540 1224324 : talloc_free(key2.data);
3541 :
3542 1224324 : talloc_free(msg);
3543 :
3544 1224324 : ctx->count++;
3545 1224324 : if (ctx->count % 10000 == 0) {
3546 0 : ldb_debug(ldb, LDB_DEBUG_WARNING,
3547 : "Reindexing: re-keyed %u records so far",
3548 : ctx->count);
3549 : }
3550 :
3551 1091734 : return 0;
3552 : }
3553 :
3554 : /*
3555 : traversal function that adds @INDEX records during a re index
3556 : */
3557 6832618 : static int re_index(struct ldb_kv_private *ldb_kv,
3558 : struct ldb_val key,
3559 : struct ldb_val val,
3560 : void *state)
3561 : {
3562 673911 : struct ldb_context *ldb;
3563 6832618 : struct ldb_kv_reindex_context *ctx =
3564 : (struct ldb_kv_reindex_context *)state;
3565 6832618 : struct ldb_module *module = ldb_kv->module;
3566 673911 : struct ldb_message *msg;
3567 673911 : int ret;
3568 673911 : bool is_record;
3569 :
3570 6832618 : ldb = ldb_module_get_ctx(module);
3571 :
3572 6832618 : is_record = ldb_kv_key_is_normal_record(key);
3573 6832618 : if (is_record == false) {
3574 5085731 : return 0;
3575 : }
3576 :
3577 1188382 : msg = ldb_msg_new(module);
3578 1188382 : if (msg == NULL) {
3579 0 : return -1;
3580 : }
3581 :
3582 1188382 : ret = ldb_unpack_data(ldb, &val, msg);
3583 1188382 : if (ret != 0) {
3584 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid data for index %s\n",
3585 : ldb_dn_get_linearized(msg->dn));
3586 0 : ctx->error = ret;
3587 0 : talloc_free(msg);
3588 0 : return -1;
3589 : }
3590 :
3591 1188382 : if (msg->dn == NULL) {
3592 0 : ldb_debug(ldb, LDB_DEBUG_ERROR,
3593 : "Refusing to re-index as GUID "
3594 : "key %*.*s with no DN\n",
3595 0 : (int)key.length, (int)key.length,
3596 0 : (char *)key.data);
3597 0 : talloc_free(msg);
3598 0 : return -1;
3599 : }
3600 :
3601 1188382 : ret = ldb_kv_index_onelevel(module, msg, 1);
3602 1188382 : if (ret != LDB_SUCCESS) {
3603 0 : ldb_debug(ldb, LDB_DEBUG_ERROR,
3604 : "Adding special ONE LEVEL index failed (%s)!",
3605 : ldb_dn_get_linearized(msg->dn));
3606 0 : talloc_free(msg);
3607 0 : return -1;
3608 : }
3609 :
3610 1188382 : ret = ldb_kv_index_add_all(module, ldb_kv, msg);
3611 :
3612 1188382 : if (ret != LDB_SUCCESS) {
3613 12 : ctx->error = ret;
3614 12 : talloc_free(msg);
3615 12 : return -1;
3616 : }
3617 :
3618 1188370 : talloc_free(msg);
3619 :
3620 1188370 : ctx->count++;
3621 1188370 : if (ctx->count % 10000 == 0) {
3622 0 : ldb_debug(ldb, LDB_DEBUG_WARNING,
3623 : "Reindexing: re-indexed %u records so far",
3624 : ctx->count);
3625 : }
3626 :
3627 1072964 : return 0;
3628 : }
3629 :
3630 : /*
3631 : * Convert the 4-byte pack format version to a number that's slightly
3632 : * more intelligible to a user e.g. version 0, 1, 2, etc.
3633 : */
3634 2216 : static uint32_t displayable_pack_version(uint32_t version) {
3635 2216 : if (version < LDB_PACKING_FORMAT_NODN) {
3636 0 : return version; /* unknown - can't convert */
3637 : }
3638 :
3639 2216 : return (version - LDB_PACKING_FORMAT_NODN);
3640 : }
3641 :
3642 5239252 : static int re_pack(struct ldb_kv_private *ldb_kv,
3643 : _UNUSED_ struct ldb_val key,
3644 : struct ldb_val val,
3645 : void *state)
3646 : {
3647 696905 : struct ldb_context *ldb;
3648 696905 : struct ldb_message *msg;
3649 5239252 : struct ldb_module *module = ldb_kv->module;
3650 5239252 : struct ldb_kv_repack_context *ctx =
3651 : (struct ldb_kv_repack_context *)state;
3652 696905 : int ret;
3653 :
3654 5239252 : ldb = ldb_module_get_ctx(module);
3655 :
3656 5239252 : msg = ldb_msg_new(module);
3657 5239252 : if (msg == NULL) {
3658 0 : return -1;
3659 : }
3660 :
3661 5239252 : ret = ldb_unpack_data(ldb, &val, msg);
3662 5239252 : if (ret != 0) {
3663 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Repack: unpack failed: %s\n",
3664 : ldb_dn_get_linearized(msg->dn));
3665 0 : ctx->error = ret;
3666 0 : talloc_free(msg);
3667 0 : return -1;
3668 : }
3669 :
3670 5239252 : ret = ldb_kv_store(module, msg, TDB_MODIFY);
3671 5239252 : if (ret != LDB_SUCCESS) {
3672 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Repack: store failed: %s\n",
3673 : ldb_dn_get_linearized(msg->dn));
3674 0 : ctx->error = ret;
3675 0 : talloc_free(msg);
3676 0 : return -1;
3677 : }
3678 :
3679 : /*
3680 : * Warn the user that we're repacking the first time we see a normal
3681 : * record. This means we never warn if we're repacking a database with
3682 : * only @ records. This is because during database initialisation,
3683 : * we might repack as initial settings are written out, and we don't
3684 : * want to spam the log.
3685 : */
3686 5239252 : if ((!ctx->normal_record_seen) && (!ldb_dn_is_special(msg->dn))) {
3687 1484 : ldb_debug(ldb, LDB_DEBUG_ALWAYS_LOG,
3688 : "Repacking database from v%u to v%u format "
3689 : "(first record %s)",
3690 : displayable_pack_version(ctx->old_version),
3691 : displayable_pack_version(ldb_kv->pack_format_version),
3692 : ldb_dn_get_linearized(msg->dn));
3693 1108 : ctx->normal_record_seen = true;
3694 : }
3695 :
3696 5239252 : ctx->count++;
3697 5239252 : if (ctx->count % 10000 == 0) {
3698 255 : ldb_debug(ldb, LDB_DEBUG_WARNING,
3699 : "Repack: re-packed %u records so far",
3700 : ctx->count);
3701 : }
3702 :
3703 5239252 : talloc_free(msg);
3704 5239252 : return 0;
3705 : }
3706 :
3707 3266 : int ldb_kv_repack(struct ldb_module *module)
3708 : {
3709 3266 : struct ldb_kv_private *ldb_kv = talloc_get_type(
3710 : ldb_module_get_private(module), struct ldb_kv_private);
3711 3266 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3712 460 : struct ldb_kv_repack_context ctx;
3713 460 : int ret;
3714 :
3715 3266 : ctx.old_version = ldb_kv->pack_format_version;
3716 3266 : ctx.count = 0;
3717 3266 : ctx.error = LDB_SUCCESS;
3718 3266 : ctx.normal_record_seen = false;
3719 :
3720 3266 : ldb_kv->pack_format_version = ldb_kv->target_pack_format_version;
3721 :
3722 : /* Iterate all database records and repack them in the new format */
3723 3266 : ret = ldb_kv->kv_ops->iterate(ldb_kv, re_pack, &ctx);
3724 3266 : if (ret < 0) {
3725 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Repack traverse failed: %s",
3726 : ldb_errstring(ldb));
3727 0 : return LDB_ERR_OPERATIONS_ERROR;
3728 : }
3729 :
3730 3266 : if (ctx.error != LDB_SUCCESS) {
3731 0 : ldb_debug(ldb, LDB_DEBUG_ERROR, "Repack failed: %s",
3732 : ldb_errstring(ldb));
3733 0 : return ctx.error;
3734 : }
3735 :
3736 2806 : return LDB_SUCCESS;
3737 : }
3738 :
3739 : /*
3740 : force a complete reindex of the database
3741 : */
3742 12138 : int ldb_kv_reindex(struct ldb_module *module)
3743 : {
3744 12138 : struct ldb_kv_private *ldb_kv = talloc_get_type(
3745 : ldb_module_get_private(module), struct ldb_kv_private);
3746 1127 : int ret;
3747 1127 : struct ldb_kv_reindex_context ctx;
3748 12138 : size_t index_cache_size = 0;
3749 :
3750 : /*
3751 : * Only triggered after a modification, but make clear we do
3752 : * not re-index a read-only DB
3753 : */
3754 12138 : if (ldb_kv->read_only) {
3755 0 : return LDB_ERR_UNWILLING_TO_PERFORM;
3756 : }
3757 :
3758 12138 : if (ldb_kv_cache_reload(module) != 0) {
3759 0 : return LDB_ERR_OPERATIONS_ERROR;
3760 : }
3761 :
3762 : /*
3763 : * Ensure we read (and so remove) the entries from the real
3764 : * DB, no values stored so far are any use as we want to do a
3765 : * re-index
3766 : */
3767 12136 : ldb_kv_index_transaction_cancel(module);
3768 12136 : if (ldb_kv->nested_idx_ptr != NULL) {
3769 0 : ldb_kv_index_sub_transaction_cancel(ldb_kv);
3770 : }
3771 :
3772 : /*
3773 : * Calculate the size of the index cache needed for
3774 : * the re-index. If specified always use the
3775 : * ldb_kv->index_transaction_cache_size otherwise use the maximum
3776 : * of the size estimate or the DEFAULT_INDEX_CACHE_SIZE
3777 : */
3778 12136 : if (ldb_kv->index_transaction_cache_size > 0) {
3779 11011 : index_cache_size = ldb_kv->index_transaction_cache_size;
3780 : } else {
3781 2 : index_cache_size = ldb_kv->kv_ops->get_size(ldb_kv);
3782 2 : if (index_cache_size < DEFAULT_INDEX_CACHE_SIZE) {
3783 0 : index_cache_size = DEFAULT_INDEX_CACHE_SIZE;
3784 : }
3785 : }
3786 :
3787 : /*
3788 : * Note that we don't start an index sub transaction for re-indexing
3789 : */
3790 12136 : ret = ldb_kv_index_transaction_start(module, index_cache_size);
3791 12136 : if (ret != LDB_SUCCESS) {
3792 0 : return ret;
3793 : }
3794 :
3795 : /* first traverse the database deleting any @INDEX records by
3796 : * putting NULL entries in the in-memory tdb
3797 : */
3798 12136 : ret = ldb_kv->kv_ops->iterate(ldb_kv, delete_index, module);
3799 12136 : if (ret < 0) {
3800 0 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3801 0 : ldb_asprintf_errstring(ldb, "index deletion traverse failed: %s",
3802 : ldb_errstring(ldb));
3803 0 : return LDB_ERR_OPERATIONS_ERROR;
3804 : }
3805 :
3806 12136 : ctx.error = 0;
3807 12136 : ctx.count = 0;
3808 :
3809 12136 : ret = ldb_kv->kv_ops->iterate(ldb_kv, re_key, &ctx);
3810 12136 : if (ret < 0) {
3811 0 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3812 0 : ldb_asprintf_errstring(ldb, "key correction traverse failed: %s",
3813 : ldb_errstring(ldb));
3814 0 : return LDB_ERR_OPERATIONS_ERROR;
3815 : }
3816 :
3817 12136 : if (ctx.error != LDB_SUCCESS) {
3818 0 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3819 0 : ldb_asprintf_errstring(ldb, "reindexing failed: %s", ldb_errstring(ldb));
3820 0 : return ctx.error;
3821 : }
3822 :
3823 12136 : ctx.error = 0;
3824 12136 : ctx.count = 0;
3825 :
3826 : /* now traverse adding any indexes for normal LDB records */
3827 12136 : ret = ldb_kv->kv_ops->iterate(ldb_kv, re_index, &ctx);
3828 12136 : if (ret < 0) {
3829 0 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3830 0 : ldb_asprintf_errstring(ldb, "reindexing traverse failed: %s",
3831 : ldb_errstring(ldb));
3832 0 : return LDB_ERR_OPERATIONS_ERROR;
3833 : }
3834 :
3835 12136 : if (ctx.error != LDB_SUCCESS) {
3836 12 : struct ldb_context *ldb = ldb_module_get_ctx(module);
3837 12 : ldb_asprintf_errstring(ldb, "reindexing failed: %s", ldb_errstring(ldb));
3838 12 : return ctx.error;
3839 : }
3840 :
3841 12124 : if (ctx.count > 10000) {
3842 0 : ldb_debug(ldb_module_get_ctx(module),
3843 : LDB_DEBUG_WARNING,
3844 : "Reindexing: re_index successful on %s, "
3845 : "final index write-out will be in transaction commit",
3846 0 : ldb_kv->kv_ops->name(ldb_kv));
3847 : }
3848 10999 : return LDB_SUCCESS;
3849 : }
3850 :
3851 : /*
3852 : * Copy the contents of the nested transaction index cache record to the
3853 : * transaction index cache.
3854 : *
3855 : * During this 'commit' of the subtransaction to the main transaction
3856 : * (cache), care must be taken to free any existing index at the top
3857 : * level because otherwise we would leak memory.
3858 : */
3859 9510541 : static int ldb_kv_sub_transaction_traverse(
3860 : struct tdb_context *tdb,
3861 : TDB_DATA key,
3862 : TDB_DATA data,
3863 : void *state)
3864 : {
3865 9510541 : struct ldb_module *module = state;
3866 9510541 : struct ldb_kv_private *ldb_kv = talloc_get_type(
3867 : ldb_module_get_private(module), struct ldb_kv_private);
3868 9510541 : TDB_DATA rec = {0};
3869 9510541 : struct dn_list *index_in_subtransaction = NULL;
3870 9510541 : struct dn_list *index_in_top_level = NULL;
3871 9510541 : int ret = 0;
3872 :
3873 : /*
3874 : * This unwraps the pointer in the DB into a pointer in
3875 : * memory, we are abusing TDB as a hash map, not a linearised
3876 : * database store
3877 : */
3878 9510541 : index_in_subtransaction = ldb_kv_index_idxptr(module, data);
3879 9510541 : if (index_in_subtransaction == NULL) {
3880 0 : ldb_kv->idxptr->error = LDB_ERR_OPERATIONS_ERROR;
3881 0 : return -1;
3882 : }
3883 :
3884 : /*
3885 : * Do we already have an entry in the primary transaction cache
3886 : * If so free it's dn_list and replace it with the dn_list from
3887 : * the secondary cache
3888 : *
3889 : * The TDB and so the fetched rec contains NO DATA, just a
3890 : * pointer to data held in memory.
3891 : */
3892 9510541 : rec = tdb_fetch(ldb_kv->idxptr->itdb, key);
3893 9510541 : if (rec.dptr != NULL) {
3894 3949937 : index_in_top_level = ldb_kv_index_idxptr(module, rec);
3895 3949937 : free(rec.dptr);
3896 3949937 : if (index_in_top_level == NULL) {
3897 0 : abort();
3898 : }
3899 : /*
3900 : * We had this key at the top level. However we made a copy
3901 : * at the sub-transaction level so that we could possibly
3902 : * roll back. We have to free the top level index memory
3903 : * otherwise we would leak
3904 : */
3905 3949937 : if (index_in_top_level->count > 0) {
3906 3948377 : TALLOC_FREE(index_in_top_level->dn);
3907 : }
3908 4432048 : index_in_top_level->dn
3909 3949937 : = talloc_steal(index_in_top_level,
3910 : index_in_subtransaction->dn);
3911 3949937 : index_in_top_level->count = index_in_subtransaction->count;
3912 3949937 : return 0;
3913 : }
3914 :
3915 5560604 : index_in_top_level = talloc(ldb_kv->idxptr, struct dn_list);
3916 5560604 : if (index_in_top_level == NULL) {
3917 0 : ldb_kv->idxptr->error = LDB_ERR_OPERATIONS_ERROR;
3918 0 : return -1;
3919 : }
3920 5996540 : index_in_top_level->dn
3921 5560604 : = talloc_steal(index_in_top_level,
3922 : index_in_subtransaction->dn);
3923 5560604 : index_in_top_level->count = index_in_subtransaction->count;
3924 :
3925 5560604 : rec.dptr = (uint8_t *)&index_in_top_level;
3926 5560604 : rec.dsize = sizeof(void *);
3927 :
3928 :
3929 : /*
3930 : * This is not a store into the main DB, but into an in-memory
3931 : * TDB, so we don't need a guard on ltdb->read_only
3932 : */
3933 5560604 : ret = tdb_store(ldb_kv->idxptr->itdb, key, rec, TDB_INSERT);
3934 5560604 : if (ret != 0) {
3935 0 : ldb_kv->idxptr->error = ltdb_err_map(
3936 0 : tdb_error(ldb_kv->idxptr->itdb));
3937 0 : return -1;
3938 : }
3939 5124668 : return 0;
3940 : }
3941 :
3942 : /*
3943 : * Initialise the index cache for a sub transaction.
3944 : */
3945 2061191 : int ldb_kv_index_sub_transaction_start(struct ldb_kv_private *ldb_kv)
3946 : {
3947 2061191 : ldb_kv->nested_idx_ptr = talloc_zero(ldb_kv, struct ldb_kv_idxptr);
3948 2061191 : if (ldb_kv->nested_idx_ptr == NULL) {
3949 0 : return LDB_ERR_OPERATIONS_ERROR;
3950 : }
3951 :
3952 : /*
3953 : * We use a tiny hash size for the sub-database (11).
3954 : *
3955 : * The sub-transaction is only for one record at a time, we
3956 : * would use a linked list but that would make the code even
3957 : * more complex when manipulating the index, as it would have
3958 : * to know if we were in a nested transaction (normal
3959 : * operations) or the top one (a reindex).
3960 : */
3961 4122382 : ldb_kv->nested_idx_ptr->itdb =
3962 2061191 : tdb_open(NULL, 11, TDB_INTERNAL, O_RDWR, 0);
3963 2061191 : if (ldb_kv->nested_idx_ptr->itdb == NULL) {
3964 0 : return LDB_ERR_OPERATIONS_ERROR;
3965 : }
3966 1938480 : return LDB_SUCCESS;
3967 : }
3968 :
3969 : /*
3970 : * Clear the contents of the nested transaction index cache when the nested
3971 : * transaction is cancelled.
3972 : */
3973 12923 : int ldb_kv_index_sub_transaction_cancel(struct ldb_kv_private *ldb_kv)
3974 : {
3975 12923 : if (ldb_kv->nested_idx_ptr != NULL) {
3976 12911 : tdb_close(ldb_kv->nested_idx_ptr->itdb);
3977 12911 : TALLOC_FREE(ldb_kv->nested_idx_ptr);
3978 : }
3979 12923 : return LDB_SUCCESS;
3980 : }
3981 :
3982 : /*
3983 : * Commit a nested transaction,
3984 : * Copy the contents of the nested transaction index cache to the
3985 : * transaction index cache.
3986 : */
3987 2048268 : int ldb_kv_index_sub_transaction_commit(struct ldb_kv_private *ldb_kv)
3988 : {
3989 2048268 : int ret = 0;
3990 :
3991 2048268 : if (ldb_kv->nested_idx_ptr == NULL) {
3992 10279 : return LDB_SUCCESS;
3993 : }
3994 2036866 : if (ldb_kv->nested_idx_ptr->itdb == NULL) {
3995 0 : return LDB_SUCCESS;
3996 : }
3997 2036866 : tdb_traverse(
3998 1916578 : ldb_kv->nested_idx_ptr->itdb,
3999 : ldb_kv_sub_transaction_traverse,
4000 2036866 : ldb_kv->module);
4001 2036866 : tdb_close(ldb_kv->nested_idx_ptr->itdb);
4002 2036866 : ldb_kv->nested_idx_ptr->itdb = NULL;
4003 :
4004 2036866 : ret = ldb_kv->nested_idx_ptr->error;
4005 2036866 : if (ret != LDB_SUCCESS) {
4006 0 : struct ldb_context *ldb = ldb_module_get_ctx(ldb_kv->module);
4007 0 : if (!ldb_errstring(ldb)) {
4008 0 : ldb_set_errstring(ldb, ldb_strerror(ret));
4009 : }
4010 0 : ldb_asprintf_errstring(
4011 : ldb,
4012 : __location__": Failed to update index records in "
4013 : "sub transaction commit: %s",
4014 : ldb_errstring(ldb));
4015 : }
4016 2036866 : TALLOC_FREE(ldb_kv->nested_idx_ptr);
4017 1916578 : return ret;
4018 : }
|
