4 Copyright (C) Andrew Tridgell 2004
6 ** NOTE! The following LGPL license applies to the ldb
7 ** library. This does NOT imply that all of Samba is released
10 This library is free software; you can redistribute it and/or
11 modify it under the terms of the GNU Lesser General Public
12 License as published by the Free Software Foundation; either
13 version 3 of the License, or (at your option) any later version.
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
20 You should have received a copy of the GNU Lesser General Public
21 License along with this library; if not, see <http://www.gnu.org/licenses/>.
27 * Component: ldb tdb backend - indexing
29 * Description: indexing routines for ldb tdb backend
31 * Author: Andrew Tridgell
35 #include "dlinklist.h"
38 the idxptr code is a bit unusual. The way it works is to replace
39 @IDX elements in records during a transaction with @IDXPTR
40 elements. The @IDXPTR elements don't contain the actual index entry
41 values, but contain a pointer to a linked list of values.
43 This means we are storing pointers in a database, which is normally
44 not allowed, but in this case we are storing them only for the
45 duration of a transaction, and re-writing them into the normal @IDX
46 format at the end of the transaction. That means no other processes
47 are ever exposed to the @IDXPTR values.
49 The advantage is that the linked list doesn't cause huge
50 fragmentation during a transaction. Without the @IDXPTR method we
51 often ended up with a ldb that was between 10x and 100x larger then
52 it needs to be due to massive fragmentation caused by re-writing
53 @INDEX records many times during indexing.
55 struct ldb_index_pointer
{
56 struct ldb_index_pointer
*next
, *prev
;
67 add to the list of DNs that need to be fixed on transaction end
69 static int ltdb_idxptr_add(struct ldb_module
*module
, const struct ldb_message
*msg
)
71 void *data
= ldb_module_get_private(module
);
72 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
73 ltdb
->idxptr
->dn_list
= talloc_realloc(ltdb
->idxptr
, ltdb
->idxptr
->dn_list
,
74 const char *, ltdb
->idxptr
->num_dns
+1);
75 if (ltdb
->idxptr
->dn_list
== NULL
) {
76 ltdb
->idxptr
->num_dns
= 0;
77 return LDB_ERR_OPERATIONS_ERROR
;
79 ltdb
->idxptr
->dn_list
[ltdb
->idxptr
->num_dns
] =
80 talloc_strdup(ltdb
->idxptr
->dn_list
, ldb_dn_get_linearized(msg
->dn
));
81 if (ltdb
->idxptr
->dn_list
[ltdb
->idxptr
->num_dns
] == NULL
) {
82 return LDB_ERR_OPERATIONS_ERROR
;
84 ltdb
->idxptr
->num_dns
++;
88 /* free an idxptr record */
89 static int ltdb_free_idxptr(struct ldb_module
*module
, struct ldb_message_element
*el
)
92 struct ldb_index_pointer
*ptr
;
94 if (el
->num_values
!= 1) {
95 return LDB_ERR_OPERATIONS_ERROR
;
99 if (val
.length
!= sizeof(void *)) {
100 return LDB_ERR_OPERATIONS_ERROR
;
103 ptr
= *(struct ldb_index_pointer
**)val
.data
;
104 if (talloc_get_type(ptr
, struct ldb_index_pointer
) != ptr
) {
105 return LDB_ERR_OPERATIONS_ERROR
;
109 struct ldb_index_pointer
*tmp
= ptr
;
110 DLIST_REMOVE(ptr
, ptr
);
118 /* convert from the IDXPTR format to a ldb_message_element format */
119 static int ltdb_convert_from_idxptr(struct ldb_module
*module
, struct ldb_message_element
*el
)
122 struct ldb_index_pointer
*ptr
, *tmp
;
124 struct ldb_val
*val2
;
126 if (el
->num_values
!= 1) {
127 return LDB_ERR_OPERATIONS_ERROR
;
131 if (val
.length
!= sizeof(void *)) {
132 return LDB_ERR_OPERATIONS_ERROR
;
135 ptr
= *(struct ldb_index_pointer
**)val
.data
;
136 if (talloc_get_type(ptr
, struct ldb_index_pointer
) != ptr
) {
137 return LDB_ERR_OPERATIONS_ERROR
;
140 /* count the length of the list */
141 for (i
=0, tmp
= ptr
; tmp
; tmp
=tmp
->next
) {
145 /* allocate the new values array */
146 val2
= talloc_realloc(NULL
, el
->values
, struct ldb_val
, i
);
148 return LDB_ERR_OPERATIONS_ERROR
;
153 /* populate the values array */
154 for (i
=0, tmp
= ptr
; tmp
; tmp
=tmp
->next
, i
++) {
155 el
->values
[i
].length
= tmp
->value
.length
;
156 /* we need to over-allocate here as there are still some places
157 in ldb that rely on null termination. */
158 el
->values
[i
].data
= talloc_size(el
->values
, tmp
->value
.length
+1);
159 if (el
->values
[i
].data
== NULL
) {
160 return LDB_ERR_OPERATIONS_ERROR
;
162 memcpy(el
->values
[i
].data
, tmp
->value
.data
, tmp
->value
.length
);
163 el
->values
[i
].data
[tmp
->value
.length
] = 0;
166 /* update the name */
173 /* convert to the IDXPTR format from a ldb_message_element format */
174 static int ltdb_convert_to_idxptr(struct ldb_module
*module
, struct ldb_message_element
*el
)
176 struct ldb_index_pointer
*ptr
, *tmp
;
178 struct ldb_val
*val2
;
179 void *data
= ldb_module_get_private(module
);
180 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
184 for (i
=0;i
<el
->num_values
;i
++) {
185 tmp
= talloc(ltdb
->idxptr
, struct ldb_index_pointer
);
187 return LDB_ERR_OPERATIONS_ERROR
;
189 tmp
->value
= el
->values
[i
];
190 tmp
->value
.data
= talloc_memdup(tmp
, tmp
->value
.data
, tmp
->value
.length
);
191 if (tmp
->value
.data
== NULL
) {
192 return LDB_ERR_OPERATIONS_ERROR
;
197 /* allocate the new values array */
198 val2
= talloc_realloc(NULL
, el
->values
, struct ldb_val
, 1);
200 return LDB_ERR_OPERATIONS_ERROR
;
205 el
->values
[0].data
= talloc_memdup(el
->values
, &ptr
, sizeof(ptr
));
206 el
->values
[0].length
= sizeof(ptr
);
208 /* update the name */
209 el
->name
= LTDB_IDXPTR
;
215 /* enable the idxptr mode when transactions start */
216 int ltdb_index_transaction_start(struct ldb_module
*module
)
218 void *data
= ldb_module_get_private(module
);
219 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
220 ltdb
->idxptr
= talloc_zero(module
, struct ltdb_idxptr
);
225 a wrapper around ltdb_search_dn1() which translates pointer based index records
226 and maps them into normal ldb message structures
228 static int ltdb_search_dn1_index(struct ldb_module
*module
,
229 struct ldb_dn
*dn
, struct ldb_message
*msg
)
232 ret
= ltdb_search_dn1(module
, dn
, msg
);
233 if (ret
!= LDB_SUCCESS
) {
237 /* if this isn't a @INDEX record then don't munge it */
238 if (strncmp(ldb_dn_get_linearized(msg
->dn
), LTDB_INDEX
":", strlen(LTDB_INDEX
) + 1) != 0) {
239 return LDB_ERR_OPERATIONS_ERROR
;
242 for (i
=0;i
<msg
->num_elements
;i
++) {
243 struct ldb_message_element
*el
= &msg
->elements
[i
];
244 if (strcmp(el
->name
, LTDB_IDXPTR
) == 0) {
245 ret
= ltdb_convert_from_idxptr(module
, el
);
246 if (ret
!= LDB_SUCCESS
) {
258 fixup the idxptr for one DN
260 static int ltdb_idxptr_fix_dn(struct ldb_module
*module
, const char *strdn
)
262 struct ldb_context
*ldb
;
264 struct ldb_message
*msg
= ldb_msg_new(module
);
267 ldb
= ldb_module_get_ctx(module
);
269 dn
= ldb_dn_new(msg
, ldb
, strdn
);
270 if (ltdb_search_dn1_index(module
, dn
, msg
) == LDB_SUCCESS
) {
271 ret
= ltdb_store(module
, msg
, TDB_REPLACE
);
277 /* cleanup the idxptr mode when transaction commits */
278 int ltdb_index_transaction_commit(struct ldb_module
*module
)
281 void *data
= ldb_module_get_private(module
);
282 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
284 /* fix all the DNs that we have modified */
286 for (i
=0;i
<ltdb
->idxptr
->num_dns
;i
++) {
287 ltdb_idxptr_fix_dn(module
, ltdb
->idxptr
->dn_list
[i
]);
290 if (ltdb
->idxptr
->repack
) {
291 tdb_repack(ltdb
->tdb
);
295 talloc_free(ltdb
->idxptr
);
300 /* cleanup the idxptr mode when transaction cancels */
301 int ltdb_index_transaction_cancel(struct ldb_module
*module
)
303 void *data
= ldb_module_get_private(module
);
304 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
305 talloc_free(ltdb
->idxptr
);
312 /* a wrapper around ltdb_store() for the index code which
313 stores in IDXPTR format when idxptr mode is enabled
315 WARNING: This modifies the msg which is passed in
317 int ltdb_store_idxptr(struct ldb_module
*module
, const struct ldb_message
*msg
, int flgs
)
319 void *data
= ldb_module_get_private(module
);
320 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
325 struct ldb_message
*msg2
= ldb_msg_new(module
);
327 /* free any old pointer */
328 ret
= ltdb_search_dn1(module
, msg
->dn
, msg2
);
330 for (i
=0;i
<msg2
->num_elements
;i
++) {
331 struct ldb_message_element
*el
= &msg2
->elements
[i
];
332 if (strcmp(el
->name
, LTDB_IDXPTR
) == 0) {
333 ret
= ltdb_free_idxptr(module
, el
);
334 if (ret
!= LDB_SUCCESS
) {
342 for (i
=0;i
<msg
->num_elements
;i
++) {
343 struct ldb_message_element
*el
= &msg
->elements
[i
];
344 if (strcmp(el
->name
, LTDB_IDX
) == 0) {
345 ret
= ltdb_convert_to_idxptr(module
, el
);
346 if (ret
!= LDB_SUCCESS
) {
352 if (ltdb_idxptr_add(module
, msg
) != 0) {
353 return LDB_ERR_OPERATIONS_ERROR
;
357 ret
= ltdb_store(module
, msg
, flgs
);
363 find an element in a list, using the given comparison function and
364 assuming that the list is already sorted using comp_fn
366 return -1 if not found, or the index of the first occurance of needle if found
368 static int ldb_list_find(const void *needle
,
369 const void *base
, size_t nmemb
, size_t size
,
370 comparison_fn_t comp_fn
)
372 const char *base_p
= (const char *)base
;
373 size_t min_i
, max_i
, test_i
;
382 while (min_i
< max_i
) {
385 test_i
= (min_i
+ max_i
) / 2;
386 /* the following cast looks strange, but is
387 correct. The key to understanding it is that base_p
388 is a pointer to an array of pointers, so we have to
389 dereference it after casting to void **. The strange
390 const in the middle gives us the right type of pointer
391 after the dereference (tridge) */
392 r
= comp_fn(needle
, *(void * const *)(base_p
+ (size
* test_i
)));
394 /* scan back for first element */
396 comp_fn(needle
, *(void * const *)(base_p
+ (size
* (test_i
-1)))) == 0) {
412 if (comp_fn(needle
, *(void * const *)(base_p
+ (size
* min_i
))) == 0) {
425 return the dn key to be used for an index
428 static struct ldb_dn
*ltdb_index_key(struct ldb_context
*ldb
,
429 const char *attr
, const struct ldb_val
*value
,
430 const struct ldb_schema_attribute
**ap
)
434 const struct ldb_schema_attribute
*a
;
438 attr_folded
= ldb_attr_casefold(ldb
, attr
);
443 a
= ldb_schema_attribute_by_name(ldb
, attr
);
447 r
= a
->syntax
->canonicalise_fn(ldb
, ldb
, value
, &v
);
448 if (r
!= LDB_SUCCESS
) {
449 const char *errstr
= ldb_errstring(ldb
);
450 /* canonicalisation can be refused. For example,
451 a attribute that takes wildcards will refuse to canonicalise
452 if the value contains a wildcard */
453 ldb_asprintf_errstring(ldb
, "Failed to create index key for attribute '%s':%s%s%s",
454 attr
, ldb_strerror(r
), (errstr
?":":""), (errstr
?errstr
:""));
455 talloc_free(attr_folded
);
458 if (ldb_should_b64_encode(ldb
, &v
)) {
459 char *vstr
= ldb_base64_encode(ldb
, (char *)v
.data
, v
.length
);
460 if (!vstr
) return NULL
;
461 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s::%s", LTDB_INDEX
, attr_folded
, vstr
);
464 ret
= ldb_dn_new_fmt(ldb
, ldb
, "%s:%s:%.*s", LTDB_INDEX
, attr_folded
, (int)v
.length
, (char *)v
.data
);
467 if (v
.data
!= value
->data
) {
470 talloc_free(attr_folded
);
476 see if a attribute value is in the list of indexed attributes
478 static int ldb_msg_find_idx(const struct ldb_message
*msg
, const char *attr
,
479 unsigned int *v_idx
, const char *key
)
482 for (i
=0;i
<msg
->num_elements
;i
++) {
483 if (ldb_attr_cmp(msg
->elements
[i
].name
, key
) == 0) {
484 const struct ldb_message_element
*el
= &msg
->elements
[i
];
487 /* in this case we are just looking to see if key is present,
488 we are not spearching for a specific index */
492 for (j
=0;j
<el
->num_values
;j
++) {
493 if (ldb_attr_cmp((char *)el
->values
[j
].data
, attr
) == 0) {
505 /* used in sorting dn lists */
506 static int list_cmp(const char **s1
, const char **s2
)
508 return strcmp(*s1
, *s2
);
512 return a list of dn's that might match a simple indexed search or
514 static int ltdb_index_dn_simple(struct ldb_module
*module
,
515 const struct ldb_parse_tree
*tree
,
516 const struct ldb_message
*index_list
,
517 struct dn_list
*list
)
519 struct ldb_context
*ldb
;
523 struct ldb_message
*msg
;
525 ldb
= ldb_module_get_ctx(module
);
530 /* if the attribute isn't in the list of indexed attributes then
531 this node needs a full search */
532 if (ldb_msg_find_idx(index_list
, tree
->u
.equality
.attr
, NULL
, LTDB_IDXATTR
) == -1) {
533 return LDB_ERR_OPERATIONS_ERROR
;
536 /* the attribute is indexed. Pull the list of DNs that match the
538 dn
= ltdb_index_key(ldb
, tree
->u
.equality
.attr
, &tree
->u
.equality
.value
, NULL
);
539 if (!dn
) return LDB_ERR_OPERATIONS_ERROR
;
541 msg
= talloc(list
, struct ldb_message
);
543 return LDB_ERR_OPERATIONS_ERROR
;
546 ret
= ltdb_search_dn1_index(module
, dn
, msg
);
548 if (ret
!= LDB_SUCCESS
) {
552 for (i
=0;i
<msg
->num_elements
;i
++) {
553 struct ldb_message_element
*el
;
555 if (strcmp(msg
->elements
[i
].name
, LTDB_IDX
) != 0) {
559 el
= &msg
->elements
[i
];
561 list
->dn
= talloc_array(list
, char *, el
->num_values
);
564 return LDB_ERR_OPERATIONS_ERROR
;
567 for (j
=0;j
<el
->num_values
;j
++) {
568 list
->dn
[list
->count
] =
569 talloc_strdup(list
->dn
, (char *)el
->values
[j
].data
);
570 if (!list
->dn
[list
->count
]) {
572 return LDB_ERR_OPERATIONS_ERROR
;
580 if (list
->count
> 1) {
581 qsort(list
->dn
, list
->count
, sizeof(char *), (comparison_fn_t
) list_cmp
);
588 static int list_union(struct ldb_context
*, struct dn_list
*, const struct dn_list
*);
591 return a list of dn's that might match a leaf indexed search
593 static int ltdb_index_dn_leaf(struct ldb_module
*module
,
594 const struct ldb_parse_tree
*tree
,
595 const struct ldb_message
*index_list
,
596 struct dn_list
*list
)
598 struct ldb_context
*ldb
;
599 ldb
= ldb_module_get_ctx(module
);
601 if (ldb_attr_dn(tree
->u
.equality
.attr
) == 0) {
602 list
->dn
= talloc_array(list
, char *, 1);
603 if (list
->dn
== NULL
) {
605 return LDB_ERR_OPERATIONS_ERROR
;
607 list
->dn
[0] = talloc_strdup(list
->dn
, (char *)tree
->u
.equality
.value
.data
);
608 if (list
->dn
[0] == NULL
) {
610 return LDB_ERR_OPERATIONS_ERROR
;
615 return ltdb_index_dn_simple(module
, tree
, index_list
, list
);
622 relies on the lists being sorted
624 static int list_intersect(struct ldb_context
*ldb
,
625 struct dn_list
*list
, const struct dn_list
*list2
)
627 struct dn_list
*list3
;
630 if (list
->count
== 0 || list2
->count
== 0) {
632 return LDB_ERR_NO_SUCH_OBJECT
;
635 list3
= talloc(ldb
, struct dn_list
);
637 return LDB_ERR_OPERATIONS_ERROR
;
640 list3
->dn
= talloc_array(list3
, char *, list
->count
);
643 return LDB_ERR_OPERATIONS_ERROR
;
647 for (i
=0;i
<list
->count
;i
++) {
648 if (ldb_list_find(list
->dn
[i
], list2
->dn
, list2
->count
,
649 sizeof(char *), (comparison_fn_t
)strcmp
) != -1) {
650 list3
->dn
[list3
->count
] = talloc_move(list3
->dn
, &list
->dn
[i
]);
653 talloc_free(list
->dn
[i
]);
657 talloc_free(list
->dn
);
658 list
->dn
= talloc_move(list
, &list3
->dn
);
659 list
->count
= list3
->count
;
662 return LDB_ERR_NO_SUCH_OBJECT
;
669 relies on the lists being sorted
671 static int list_union(struct ldb_context
*ldb
,
672 struct dn_list
*list
, const struct dn_list
*list2
)
676 unsigned int count
= list
->count
;
678 if (list
->count
== 0 && list2
->count
== 0) {
680 return LDB_ERR_NO_SUCH_OBJECT
;
683 d
= talloc_realloc(list
, list
->dn
, char *, list
->count
+ list2
->count
);
685 return LDB_ERR_OPERATIONS_ERROR
;
689 for (i
=0;i
<list2
->count
;i
++) {
690 if (ldb_list_find(list2
->dn
[i
], list
->dn
, count
,
691 sizeof(char *), (comparison_fn_t
)strcmp
) == -1) {
692 list
->dn
[list
->count
] = talloc_strdup(list
->dn
, list2
->dn
[i
]);
693 if (!list
->dn
[list
->count
]) {
694 return LDB_ERR_OPERATIONS_ERROR
;
700 if (list
->count
!= count
) {
701 qsort(list
->dn
, list
->count
, sizeof(char *), (comparison_fn_t
)list_cmp
);
704 return LDB_ERR_NO_SUCH_OBJECT
;
707 static int ltdb_index_dn(struct ldb_module
*module
,
708 const struct ldb_parse_tree
*tree
,
709 const struct ldb_message
*index_list
,
710 struct dn_list
*list
);
716 static int ltdb_index_dn_or(struct ldb_module
*module
,
717 const struct ldb_parse_tree
*tree
,
718 const struct ldb_message
*index_list
,
719 struct dn_list
*list
)
721 struct ldb_context
*ldb
;
725 ldb
= ldb_module_get_ctx(module
);
727 ret
= LDB_ERR_OPERATIONS_ERROR
;
731 for (i
=0;i
<tree
->u
.list
.num_elements
;i
++) {
732 struct dn_list
*list2
;
735 list2
= talloc(module
, struct dn_list
);
737 return LDB_ERR_OPERATIONS_ERROR
;
740 v
= ltdb_index_dn(module
, tree
->u
.list
.elements
[i
], index_list
, list2
);
742 if (v
== LDB_ERR_NO_SUCH_OBJECT
) {
744 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
751 if (v
!= LDB_SUCCESS
&& v
!= LDB_ERR_NO_SUCH_OBJECT
) {
753 talloc_free(list
->dn
);
758 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
760 list
->dn
= talloc_move(list
, &list2
->dn
);
761 list
->count
= list2
->count
;
763 if (list_union(ldb
, list
, list2
) == -1) {
765 return LDB_ERR_OPERATIONS_ERROR
;
772 if (list
->count
== 0) {
773 return LDB_ERR_NO_SUCH_OBJECT
;
783 static int ltdb_index_dn_not(struct ldb_module
*module
,
784 const struct ldb_parse_tree
*tree
,
785 const struct ldb_message
*index_list
,
786 struct dn_list
*list
)
788 /* the only way to do an indexed not would be if we could
789 negate the not via another not or if we knew the total
790 number of database elements so we could know that the
791 existing expression covered the whole database.
793 instead, we just give up, and rely on a full index scan
794 (unless an outer & manages to reduce the list)
796 return LDB_ERR_OPERATIONS_ERROR
;
800 static bool ltdb_index_unique(struct ldb_context
*ldb
,
803 const struct ldb_schema_attribute
*a
;
804 a
= ldb_schema_attribute_by_name(ldb
, attr
);
805 if (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
) {
812 AND two index results
814 static int ltdb_index_dn_and(struct ldb_module
*module
,
815 const struct ldb_parse_tree
*tree
,
816 const struct ldb_message
*index_list
,
817 struct dn_list
*list
)
819 struct ldb_context
*ldb
;
823 ldb
= ldb_module_get_ctx(module
);
825 ret
= LDB_ERR_OPERATIONS_ERROR
;
829 for (pass
=0;pass
<=1;pass
++) {
830 /* in the first pass we only look for unique simple
831 equality tests, in the hope of avoiding having to look
833 bool only_unique
= pass
==0?true:false;
835 for (i
=0;i
<tree
->u
.list
.num_elements
;i
++) {
836 struct dn_list
*list2
;
838 bool is_unique
= false;
839 const struct ldb_parse_tree
*subtree
= tree
->u
.list
.elements
[i
];
841 if (subtree
->operation
== LDB_OP_EQUALITY
&&
842 ltdb_index_unique(ldb
, subtree
->u
.equality
.attr
)) {
845 if (is_unique
!= only_unique
) continue;
847 list2
= talloc(module
, struct dn_list
);
849 return LDB_ERR_OPERATIONS_ERROR
;
852 v
= ltdb_index_dn(module
, subtree
, index_list
, list2
);
854 if (v
== LDB_ERR_NO_SUCH_OBJECT
) {
856 talloc_free(list
->dn
);
858 return LDB_ERR_NO_SUCH_OBJECT
;
861 if (v
!= LDB_SUCCESS
&& v
!= LDB_ERR_NO_SUCH_OBJECT
) {
866 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
868 talloc_free(list
->dn
);
869 list
->dn
= talloc_move(list
, &list2
->dn
);
870 list
->count
= list2
->count
;
872 if (list_intersect(ldb
, list
, list2
) == -1) {
874 return LDB_ERR_OPERATIONS_ERROR
;
880 if (list
->count
== 0) {
881 talloc_free(list
->dn
);
882 return LDB_ERR_NO_SUCH_OBJECT
;
885 if (list
->count
== 1) {
886 /* it isn't worth loading the next part of the tree */
895 AND index results and ONE level special index
897 static int ltdb_index_dn_one(struct ldb_module
*module
,
898 struct ldb_dn
*parent_dn
,
899 struct dn_list
*list
)
901 struct ldb_context
*ldb
;
902 struct dn_list
*list2
;
903 struct ldb_message
*msg
;
909 ldb
= ldb_module_get_ctx(module
);
911 list2
= talloc_zero(module
, struct dn_list
);
913 return LDB_ERR_OPERATIONS_ERROR
;
916 /* the attribute is indexed. Pull the list of DNs that match the
918 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(parent_dn
));
919 val
.length
= strlen((char *)val
.data
);
920 key
= ltdb_index_key(ldb
, LTDB_IDXONE
, &val
, NULL
);
923 return LDB_ERR_OPERATIONS_ERROR
;
926 msg
= talloc(list2
, struct ldb_message
);
929 return LDB_ERR_OPERATIONS_ERROR
;
932 ret
= ltdb_search_dn1_index(module
, key
, msg
);
934 if (ret
!= LDB_SUCCESS
) {
938 for (i
= 0; i
< msg
->num_elements
; i
++) {
939 struct ldb_message_element
*el
;
941 if (strcmp(msg
->elements
[i
].name
, LTDB_IDX
) != 0) {
945 el
= &msg
->elements
[i
];
947 list2
->dn
= talloc_array(list2
, char *, el
->num_values
);
950 return LDB_ERR_OPERATIONS_ERROR
;
953 for (j
= 0; j
< el
->num_values
; j
++) {
954 list2
->dn
[list2
->count
] = talloc_strdup(list2
->dn
, (char *)el
->values
[j
].data
);
955 if (!list2
->dn
[list2
->count
]) {
957 return LDB_ERR_OPERATIONS_ERROR
;
963 if (list2
->count
== 0) {
965 return LDB_ERR_NO_SUCH_OBJECT
;
968 if (list2
->count
> 1) {
969 qsort(list2
->dn
, list2
->count
, sizeof(char *), (comparison_fn_t
) list_cmp
);
972 if (list
->count
> 0) {
973 if (list_intersect(ldb
, list
, list2
) == -1) {
975 return LDB_ERR_OPERATIONS_ERROR
;
978 if (list
->count
== 0) {
979 talloc_free(list
->dn
);
981 return LDB_ERR_NO_SUCH_OBJECT
;
984 list
->dn
= talloc_move(list
, &list2
->dn
);
985 list
->count
= list2
->count
;
994 return a list of dn's that might match a indexed search or
995 an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
997 static int ltdb_index_dn(struct ldb_module
*module
,
998 const struct ldb_parse_tree
*tree
,
999 const struct ldb_message
*index_list
,
1000 struct dn_list
*list
)
1002 int ret
= LDB_ERR_OPERATIONS_ERROR
;
1004 switch (tree
->operation
) {
1006 ret
= ltdb_index_dn_and(module
, tree
, index_list
, list
);
1010 ret
= ltdb_index_dn_or(module
, tree
, index_list
, list
);
1014 ret
= ltdb_index_dn_not(module
, tree
, index_list
, list
);
1017 case LDB_OP_EQUALITY
:
1018 ret
= ltdb_index_dn_leaf(module
, tree
, index_list
, list
);
1021 case LDB_OP_SUBSTRING
:
1022 case LDB_OP_GREATER
:
1024 case LDB_OP_PRESENT
:
1026 case LDB_OP_EXTENDED
:
1027 /* we can't index with fancy bitops yet */
1028 ret
= LDB_ERR_OPERATIONS_ERROR
;
1036 filter a candidate dn_list from an indexed search into a set of results
1037 extracting just the given attributes
1039 static int ltdb_index_filter(const struct dn_list
*dn_list
,
1040 struct ltdb_context
*ac
,
1041 uint32_t *match_count
)
1043 struct ldb_context
*ldb
;
1044 struct ldb_message
*msg
;
1047 ldb
= ldb_module_get_ctx(ac
->module
);
1049 for (i
= 0; i
< dn_list
->count
; i
++) {
1053 msg
= ldb_msg_new(ac
);
1055 return LDB_ERR_OPERATIONS_ERROR
;
1058 dn
= ldb_dn_new(msg
, ldb
, dn_list
->dn
[i
]);
1061 return LDB_ERR_OPERATIONS_ERROR
;
1064 ret
= ltdb_search_dn1(ac
->module
, dn
, msg
);
1066 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1067 /* the record has disappeared? yes, this can happen */
1072 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1073 /* an internal error */
1075 return LDB_ERR_OPERATIONS_ERROR
;
1078 if (!ldb_match_msg(ldb
, msg
,
1079 ac
->tree
, ac
->base
, ac
->scope
)) {
1084 /* filter the attributes that the user wants */
1085 ret
= ltdb_filter_attrs(msg
, ac
->attrs
);
1089 return LDB_ERR_OPERATIONS_ERROR
;
1092 ret
= ldb_module_send_entry(ac
->req
, msg
, NULL
);
1093 if (ret
!= LDB_SUCCESS
) {
1094 ac
->request_terminated
= true;
1105 search the database with a LDAP-like expression using indexes
1106 returns -1 if an indexed search is not possible, in which
1107 case the caller should call ltdb_search_full()
1109 int ltdb_search_indexed(struct ltdb_context
*ac
, uint32_t *match_count
)
1111 struct ldb_context
*ldb
;
1112 void *data
= ldb_module_get_private(ac
->module
);
1113 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
1114 struct dn_list
*dn_list
;
1115 int ret
, idxattr
, idxone
;
1117 ldb
= ldb_module_get_ctx(ac
->module
);
1119 idxattr
= idxone
= 0;
1120 ret
= ldb_msg_find_idx(ltdb
->cache
->indexlist
, NULL
, NULL
, LTDB_IDXATTR
);
1125 /* We do one level indexing only if requested */
1126 ret
= ldb_msg_find_idx(ltdb
->cache
->indexlist
, NULL
, NULL
, LTDB_IDXONE
);
1131 if ((ac
->scope
== LDB_SCOPE_ONELEVEL
&& (idxattr
+idxone
== 0)) ||
1132 (ac
->scope
== LDB_SCOPE_SUBTREE
&& idxattr
== 0)) {
1133 /* no indexes? must do full search */
1134 return LDB_ERR_OPERATIONS_ERROR
;
1137 ret
= LDB_ERR_OPERATIONS_ERROR
;
1139 dn_list
= talloc_zero(ac
, struct dn_list
);
1140 if (dn_list
== NULL
) {
1141 return LDB_ERR_OPERATIONS_ERROR
;
1144 if (ac
->scope
== LDB_SCOPE_BASE
) {
1145 /* with BASE searches only one DN can match */
1146 dn_list
->dn
= talloc_array(dn_list
, char *, 1);
1147 if (dn_list
->dn
== NULL
) {
1149 return LDB_ERR_OPERATIONS_ERROR
;
1151 dn_list
->dn
[0] = ldb_dn_alloc_linearized(dn_list
, ac
->base
);
1152 if (dn_list
->dn
[0] == NULL
) {
1154 return LDB_ERR_OPERATIONS_ERROR
;
1160 if (ac
->scope
!= LDB_SCOPE_BASE
&& idxattr
== 1) {
1161 ret
= ltdb_index_dn(ac
->module
, ac
->tree
, ltdb
->cache
->indexlist
, dn_list
);
1164 if (ret
== LDB_ERR_OPERATIONS_ERROR
&&
1165 ac
->scope
== LDB_SCOPE_ONELEVEL
&& idxone
== 1) {
1166 ret
= ltdb_index_dn_one(ac
->module
, ac
->base
, dn_list
);
1169 if (ret
== LDB_SUCCESS
) {
1170 /* we've got a candidate list - now filter by the full tree
1171 and extract the needed attributes */
1172 ret
= ltdb_index_filter(dn_list
, ac
, match_count
);
1175 talloc_free(dn_list
);
1181 add a index element where this is the first indexed DN for this value
1183 static int ltdb_index_add1_new(struct ldb_context
*ldb
,
1184 struct ldb_message
*msg
,
1187 struct ldb_message_element
*el
;
1189 /* add another entry */
1190 el
= talloc_realloc(msg
, msg
->elements
,
1191 struct ldb_message_element
, msg
->num_elements
+1);
1193 return LDB_ERR_OPERATIONS_ERROR
;
1197 msg
->elements
[msg
->num_elements
].name
= talloc_strdup(msg
->elements
, LTDB_IDX
);
1198 if (!msg
->elements
[msg
->num_elements
].name
) {
1199 return LDB_ERR_OPERATIONS_ERROR
;
1201 msg
->elements
[msg
->num_elements
].num_values
= 0;
1202 msg
->elements
[msg
->num_elements
].values
= talloc(msg
->elements
, struct ldb_val
);
1203 if (!msg
->elements
[msg
->num_elements
].values
) {
1204 return LDB_ERR_OPERATIONS_ERROR
;
1206 msg
->elements
[msg
->num_elements
].values
[0].length
= strlen(dn
);
1207 msg
->elements
[msg
->num_elements
].values
[0].data
= discard_const_p(uint8_t, dn
);
1208 msg
->elements
[msg
->num_elements
].num_values
= 1;
1209 msg
->num_elements
++;
1216 add a index element where this is not the first indexed DN for this
1219 static int ltdb_index_add1_add(struct ldb_context
*ldb
,
1220 struct ldb_message
*msg
,
1223 const struct ldb_schema_attribute
*a
)
1228 /* for multi-valued attributes we can end up with repeats */
1229 for (i
=0;i
<msg
->elements
[idx
].num_values
;i
++) {
1230 if (strcmp(dn
, (char *)msg
->elements
[idx
].values
[i
].data
) == 0) {
1235 if (a
->flags
& LDB_ATTR_FLAG_UNIQUE_INDEX
) {
1236 return LDB_ERR_ENTRY_ALREADY_EXISTS
;
1239 v2
= talloc_realloc(msg
->elements
, msg
->elements
[idx
].values
,
1241 msg
->elements
[idx
].num_values
+1);
1243 return LDB_ERR_OPERATIONS_ERROR
;
1245 msg
->elements
[idx
].values
= v2
;
1247 msg
->elements
[idx
].values
[msg
->elements
[idx
].num_values
].length
= strlen(dn
);
1248 msg
->elements
[idx
].values
[msg
->elements
[idx
].num_values
].data
= discard_const_p(uint8_t, dn
);
1249 msg
->elements
[idx
].num_values
++;
1255 add an index entry for one message element
1257 static int ltdb_index_add1(struct ldb_module
*module
, const char *dn
,
1258 struct ldb_message_element
*el
, int v_idx
)
1260 struct ldb_context
*ldb
;
1261 struct ldb_message
*msg
;
1262 struct ldb_dn
*dn_key
;
1265 const struct ldb_schema_attribute
*a
;
1267 ldb
= ldb_module_get_ctx(module
);
1269 msg
= talloc(module
, struct ldb_message
);
1272 return LDB_ERR_OPERATIONS_ERROR
;
1275 dn_key
= ltdb_index_key(ldb
, el
->name
, &el
->values
[v_idx
], &a
);
1278 return LDB_ERR_OPERATIONS_ERROR
;
1280 talloc_steal(msg
, dn_key
);
1282 ret
= ltdb_search_dn1_index(module
, dn_key
, msg
);
1283 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1288 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1290 msg
->num_elements
= 0;
1291 msg
->elements
= NULL
;
1294 for (i
=0;i
<msg
->num_elements
;i
++) {
1295 if (strcmp(LTDB_IDX
, msg
->elements
[i
].name
) == 0) {
1300 if (i
== msg
->num_elements
) {
1301 ret
= ltdb_index_add1_new(ldb
, msg
, dn
);
1303 ret
= ltdb_index_add1_add(ldb
, msg
, i
, dn
, a
);
1306 if (ret
== LDB_SUCCESS
) {
1307 ret
= ltdb_store_idxptr(module
, msg
, TDB_REPLACE
);
1315 static int ltdb_index_add0(struct ldb_module
*module
, const char *dn
,
1316 struct ldb_message_element
*elements
, int num_el
)
1318 void *data
= ldb_module_get_private(module
);
1319 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
1327 if (ltdb
->cache
->indexlist
->num_elements
== 0) {
1328 /* no indexed fields */
1332 for (i
= 0; i
< num_el
; i
++) {
1333 ret
= ldb_msg_find_idx(ltdb
->cache
->indexlist
, elements
[i
].name
,
1334 NULL
, LTDB_IDXATTR
);
1338 for (j
= 0; j
< elements
[i
].num_values
; j
++) {
1339 ret
= ltdb_index_add1(module
, dn
, &elements
[i
], j
);
1340 if (ret
!= LDB_SUCCESS
) {
1350 add the index entries for a new record
1352 int ltdb_index_add(struct ldb_module
*module
, const struct ldb_message
*msg
)
1357 dn
= ldb_dn_get_linearized(msg
->dn
);
1359 return LDB_ERR_OPERATIONS_ERROR
;
1362 ret
= ltdb_index_add0(module
, dn
, msg
->elements
, msg
->num_elements
);
1369 delete an index entry for one message element
1371 int ltdb_index_del_value(struct ldb_module
*module
, const char *dn
,
1372 struct ldb_message_element
*el
, int v_idx
)
1374 struct ldb_context
*ldb
;
1375 struct ldb_message
*msg
;
1376 struct ldb_dn
*dn_key
;
1380 ldb
= ldb_module_get_ctx(module
);
1386 dn_key
= ltdb_index_key(ldb
, el
->name
, &el
->values
[v_idx
], NULL
);
1388 return LDB_ERR_OPERATIONS_ERROR
;
1391 msg
= talloc(dn_key
, struct ldb_message
);
1393 talloc_free(dn_key
);
1394 return LDB_ERR_OPERATIONS_ERROR
;
1397 ret
= ltdb_search_dn1_index(module
, dn_key
, msg
);
1398 if (ret
!= LDB_SUCCESS
&& ret
!= LDB_ERR_NO_SUCH_OBJECT
) {
1399 talloc_free(dn_key
);
1403 if (ret
== LDB_ERR_NO_SUCH_OBJECT
) {
1404 /* it wasn't indexed. Did we have an earlier error? If we did then
1406 talloc_free(dn_key
);
1410 i
= ldb_msg_find_idx(msg
, dn
, &j
, LTDB_IDX
);
1412 struct ldb_ldif ldif
;
1414 ldif
.changetype
= LDB_CHANGETYPE_NONE
;
1416 ldif_string
= ldb_ldif_write_string(ldb
, NULL
, &ldif
);
1417 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
1418 "ERROR: dn %s not found in %s", dn
,
1420 talloc_free(ldif_string
);
1421 /* it ain't there. hmmm */
1422 talloc_free(dn_key
);
1426 if (j
!= msg
->elements
[i
].num_values
- 1) {
1427 memmove(&msg
->elements
[i
].values
[j
],
1428 &msg
->elements
[i
].values
[j
+1],
1429 (msg
->elements
[i
].num_values
-(j
+1)) *
1430 sizeof(msg
->elements
[i
].values
[0]));
1432 msg
->elements
[i
].num_values
--;
1434 if (msg
->elements
[i
].num_values
== 0) {
1435 ret
= ltdb_delete_noindex(module
, dn_key
);
1437 ret
= ltdb_store_idxptr(module
, msg
, TDB_REPLACE
);
1440 talloc_free(dn_key
);
1446 delete the index entries for a record
1447 return -1 on failure
1449 int ltdb_index_del(struct ldb_module
*module
, const struct ldb_message
*msg
)
1451 void *data
= ldb_module_get_private(module
);
1452 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
1457 /* find the list of indexed fields */
1458 if (ltdb
->cache
->indexlist
->num_elements
== 0) {
1459 /* no indexed fields */
1463 if (ldb_dn_is_special(msg
->dn
)) {
1467 dn
= ldb_dn_get_linearized(msg
->dn
);
1469 return LDB_ERR_OPERATIONS_ERROR
;
1472 for (i
= 0; i
< msg
->num_elements
; i
++) {
1473 ret
= ldb_msg_find_idx(ltdb
->cache
->indexlist
, msg
->elements
[i
].name
,
1474 NULL
, LTDB_IDXATTR
);
1478 for (j
= 0; j
< msg
->elements
[i
].num_values
; j
++) {
1479 ret
= ltdb_index_del_value(module
, dn
, &msg
->elements
[i
], j
);
1480 if (ret
!= LDB_SUCCESS
) {
1490 handle special index for one level searches
1492 int ltdb_index_one(struct ldb_module
*module
, const struct ldb_message
*msg
, int add
)
1494 void *data
= ldb_module_get_private(module
);
1495 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
1496 struct ldb_message_element el
;
1502 if (ldb_dn_is_special(msg
->dn
)) {
1506 /* We index for ONE Level only if requested */
1507 ret
= ldb_msg_find_idx(ltdb
->cache
->indexlist
, NULL
, NULL
, LTDB_IDXONE
);
1512 pdn
= ldb_dn_get_parent(module
, msg
->dn
);
1514 return LDB_ERR_OPERATIONS_ERROR
;
1517 dn
= ldb_dn_get_linearized(msg
->dn
);
1520 return LDB_ERR_OPERATIONS_ERROR
;
1523 val
.data
= (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn
));
1524 if (val
.data
== NULL
) {
1526 return LDB_ERR_OPERATIONS_ERROR
;
1529 val
.length
= strlen((char *)val
.data
);
1530 el
.name
= LTDB_IDXONE
;
1535 ret
= ltdb_index_add1(module
, dn
, &el
, 0);
1536 } else { /* delete */
1537 ret
= ltdb_index_del_value(module
, dn
, &el
, 0);
1547 traversal function that deletes all @INDEX records
1549 static int delete_index(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
1551 const char *dn
= "DN=" LTDB_INDEX
":";
1552 if (strncmp((char *)key
.dptr
, dn
, strlen(dn
)) == 0) {
1553 return tdb_delete(tdb
, key
);
1559 traversal function that adds @INDEX records during a re index
1561 static int re_index(struct tdb_context
*tdb
, TDB_DATA key
, TDB_DATA data
, void *state
)
1563 struct ldb_context
*ldb
;
1564 struct ldb_module
*module
= (struct ldb_module
*)state
;
1565 struct ldb_message
*msg
;
1566 const char *dn
= NULL
;
1570 ldb
= ldb_module_get_ctx(module
);
1572 if (strncmp((char *)key
.dptr
, "DN=@", 4) == 0 ||
1573 strncmp((char *)key
.dptr
, "DN=", 3) != 0) {
1577 msg
= talloc(module
, struct ldb_message
);
1582 ret
= ltdb_unpack_data(module
, &data
, msg
);
1584 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid data for index %s\n",
1585 ldb_dn_get_linearized(msg
->dn
));
1590 /* check if the DN key has changed, perhaps due to the
1591 case insensitivity of an element changing */
1592 key2
= ltdb_key(module
, msg
->dn
);
1593 if (key2
.dptr
== NULL
) {
1594 /* probably a corrupt record ... darn */
1595 ldb_debug(ldb
, LDB_DEBUG_ERROR
, "Invalid DN in re_index: %s",
1596 ldb_dn_get_linearized(msg
->dn
));
1600 if (strcmp((char *)key2
.dptr
, (char *)key
.dptr
) != 0) {
1601 tdb_delete(tdb
, key
);
1602 tdb_store(tdb
, key2
, data
, 0);
1604 talloc_free(key2
.dptr
);
1606 if (msg
->dn
== NULL
) {
1607 dn
= (char *)key
.dptr
+ 3;
1609 dn
= ldb_dn_get_linearized(msg
->dn
);
1612 ret
= ltdb_index_one(module
, msg
, 1);
1613 if (ret
== LDB_SUCCESS
) {
1614 ret
= ltdb_index_add0(module
, dn
, msg
->elements
, msg
->num_elements
);
1616 ldb_debug(ldb
, LDB_DEBUG_ERROR
,
1617 "Adding special ONE LEVEL index failed (%s)!",
1618 ldb_dn_get_linearized(msg
->dn
));
1623 if (ret
!= LDB_SUCCESS
) return -1;
1629 force a complete reindex of the database
1631 int ltdb_reindex(struct ldb_module
*module
)
1633 void *data
= ldb_module_get_private(module
);
1634 struct ltdb_private
*ltdb
= talloc_get_type(data
, struct ltdb_private
);
1637 if (ltdb_cache_reload(module
) != 0) {
1638 return LDB_ERR_OPERATIONS_ERROR
;
1641 /* first traverse the database deleting any @INDEX records */
1642 ret
= tdb_traverse(ltdb
->tdb
, delete_index
, NULL
);
1644 return LDB_ERR_OPERATIONS_ERROR
;
1647 /* if we don't have indexes we have nothing todo */
1648 if (ltdb
->cache
->indexlist
->num_elements
== 0) {
1652 /* now traverse adding any indexes for normal LDB records */
1653 ret
= tdb_traverse(ltdb
->tdb
, re_index
, module
);
1655 return LDB_ERR_OPERATIONS_ERROR
;
1659 ltdb
->idxptr
->repack
= true;