1 /* $NetBSD: filterindex.c,v 1.3 2021/08/14 16:15:00 christos Exp $ */
2
3 /* filterindex.c - generate the list of candidate entries from a filter */
4 /* $OpenLDAP$ */
5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 2000-2021 The OpenLDAP Foundation.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted only as authorized by the OpenLDAP
12 * Public License.
13 *
14 * A copy of this license is available in the file LICENSE in the
15 * top-level directory of the distribution or, alternatively, at
16 * <http://www.OpenLDAP.org/license.html>.
17 */
18
19 #include <sys/cdefs.h>
20 __RCSID("$NetBSD: filterindex.c,v 1.3 2021/08/14 16:15:00 christos Exp $");
21
22 #include "portable.h"
23
24 #include <stdio.h>
25 #include <ac/string.h>
26
27 #include "back-mdb.h"
28 #include "idl.h"
29 #ifdef LDAP_COMP_MATCH
30 #include <component.h>
31 #endif
32
33 static int presence_candidates(
34 Operation *op,
35 MDB_txn *rtxn,
36 AttributeDescription *desc,
37 ID *ids );
38
39 static int equality_candidates(
40 Operation *op,
41 MDB_txn *rtxn,
42 AttributeAssertion *ava,
43 ID *ids,
44 ID *tmp );
45 static int inequality_candidates(
46 Operation *op,
47 MDB_txn *rtxn,
48 AttributeAssertion *ava,
49 ID *ids,
50 ID *tmp,
51 int gtorlt );
52 static int approx_candidates(
53 Operation *op,
54 MDB_txn *rtxn,
55 AttributeAssertion *ava,
56 ID *ids,
57 ID *tmp );
58 static int substring_candidates(
59 Operation *op,
60 MDB_txn *rtxn,
61 SubstringsAssertion *sub,
62 ID *ids,
63 ID *tmp );
64
65 static int list_candidates(
66 Operation *op,
67 MDB_txn *rtxn,
68 Filter *flist,
69 int ftype,
70 ID *ids,
71 ID *tmp,
72 ID *stack );
73
74 static int
75 ext_candidates(
76 Operation *op,
77 MDB_txn *rtxn,
78 MatchingRuleAssertion *mra,
79 ID *ids,
80 ID *tmp,
81 ID *stack);
82
83 #ifdef LDAP_COMP_MATCH
84 static int
85 comp_candidates (
86 Operation *op,
87 MDB_txn *rtxn,
88 MatchingRuleAssertion *mra,
89 ComponentFilter *f,
90 ID *ids,
91 ID *tmp,
92 ID *stack);
93
94 static int
95 ava_comp_candidates (
96 Operation *op,
97 MDB_txn *rtxn,
98 AttributeAssertion *ava,
99 AttributeAliasing *aa,
100 ID *ids,
101 ID *tmp,
102 ID *stack);
103 #endif
104
105 int
mdb_filter_candidates(Operation * op,MDB_txn * rtxn,Filter * f,ID * ids,ID * tmp,ID * stack)106 mdb_filter_candidates(
107 Operation *op,
108 MDB_txn *rtxn,
109 Filter *f,
110 ID *ids,
111 ID *tmp,
112 ID *stack )
113 {
114 int rc = 0;
115 #ifdef LDAP_COMP_MATCH
116 AttributeAliasing *aa;
117 #endif
118 Debug( LDAP_DEBUG_FILTER, "=> mdb_filter_candidates\n" );
119
120 if ( f->f_choice & SLAPD_FILTER_UNDEFINED ) {
121 MDB_IDL_ZERO( ids );
122 goto out;
123 }
124
125 switch ( f->f_choice ) {
126 case SLAPD_FILTER_COMPUTED:
127 switch( f->f_result ) {
128 case SLAPD_COMPARE_UNDEFINED:
129 /* This technically is not the same as FALSE, but it
130 * certainly will produce no matches.
131 */
132 /* FALL THRU */
133 case LDAP_COMPARE_FALSE:
134 MDB_IDL_ZERO( ids );
135 break;
136 case LDAP_COMPARE_TRUE:
137 MDB_IDL_ALL( ids );
138 break;
139 case LDAP_SUCCESS:
140 /* this is a pre-computed scope, leave it alone */
141 break;
142 }
143 break;
144 case LDAP_FILTER_PRESENT:
145 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n" );
146 rc = presence_candidates( op, rtxn, f->f_desc, ids );
147 break;
148
149 case LDAP_FILTER_EQUALITY:
150 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n" );
151 #ifdef LDAP_COMP_MATCH
152 if ( is_aliased_attribute && ( aa = is_aliased_attribute ( f->f_ava->aa_desc ) ) ) {
153 rc = ava_comp_candidates ( op, rtxn, f->f_ava, aa, ids, tmp, stack );
154 }
155 else
156 #endif
157 {
158 rc = equality_candidates( op, rtxn, f->f_ava, ids, tmp );
159 }
160 break;
161
162 case LDAP_FILTER_APPROX:
163 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n" );
164 rc = approx_candidates( op, rtxn, f->f_ava, ids, tmp );
165 break;
166
167 case LDAP_FILTER_SUBSTRINGS:
168 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n" );
169 rc = substring_candidates( op, rtxn, f->f_sub, ids, tmp );
170 break;
171
172 case LDAP_FILTER_GE:
173 /* if no GE index, use pres */
174 Debug( LDAP_DEBUG_FILTER, "\tGE\n" );
175 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
176 ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
177 rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_GE );
178 else
179 rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
180 break;
181
182 case LDAP_FILTER_LE:
183 /* if no LE index, use pres */
184 Debug( LDAP_DEBUG_FILTER, "\tLE\n" );
185 if( f->f_ava->aa_desc->ad_type->sat_ordering &&
186 ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage & SLAP_MR_ORDERED_INDEX ) )
187 rc = inequality_candidates( op, rtxn, f->f_ava, ids, tmp, LDAP_FILTER_LE );
188 else
189 rc = presence_candidates( op, rtxn, f->f_ava->aa_desc, ids );
190 break;
191
192 case LDAP_FILTER_NOT:
193 /* no indexing to support NOT filters */
194 Debug( LDAP_DEBUG_FILTER, "\tNOT\n" );
195 MDB_IDL_ALL( ids );
196 break;
197
198 case LDAP_FILTER_AND:
199 Debug( LDAP_DEBUG_FILTER, "\tAND\n" );
200 rc = list_candidates( op, rtxn,
201 f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
202 break;
203
204 case LDAP_FILTER_OR:
205 Debug( LDAP_DEBUG_FILTER, "\tOR\n" );
206 rc = list_candidates( op, rtxn,
207 f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
208 break;
209 case LDAP_FILTER_EXT:
210 Debug( LDAP_DEBUG_FILTER, "\tEXT\n" );
211 rc = ext_candidates( op, rtxn, f->f_mra, ids, tmp, stack );
212 break;
213 default:
214 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
215 (unsigned long) f->f_choice );
216 /* Must not return NULL, otherwise extended filters break */
217 MDB_IDL_ALL( ids );
218 }
219 if ( ids[2] == NOID && MDB_IDL_IS_RANGE( ids )) {
220 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
221 ID last;
222
223 if ( mdb->mi_nextid ) {
224 last = mdb->mi_nextid;
225 } else {
226 MDB_cursor *mc;
227 MDB_val key;
228
229 last = 0;
230 rc = mdb_cursor_open( rtxn, mdb->mi_id2entry, &mc );
231 if ( !rc ) {
232 rc = mdb_cursor_get( mc, &key, NULL, MDB_LAST );
233 if ( !rc )
234 memcpy( &last, key.mv_data, sizeof( last ));
235 mdb_cursor_close( mc );
236 }
237 }
238 if ( last ) {
239 ids[2] = last;
240 } else {
241 MDB_IDL_ZERO( ids );
242 }
243 }
244
245 out:
246 Debug( LDAP_DEBUG_FILTER,
247 "<= mdb_filter_candidates: id=%ld first=%ld last=%ld\n",
248 (long) ids[0],
249 (long) MDB_IDL_FIRST( ids ),
250 (long) MDB_IDL_LAST( ids ) );
251
252 return rc;
253 }
254
255 #ifdef LDAP_COMP_MATCH
256 static int
comp_list_candidates(Operation * op,MDB_txn * rtxn,MatchingRuleAssertion * mra,ComponentFilter * flist,int ftype,ID * ids,ID * tmp,ID * save)257 comp_list_candidates(
258 Operation *op,
259 MDB_txn *rtxn,
260 MatchingRuleAssertion* mra,
261 ComponentFilter *flist,
262 int ftype,
263 ID *ids,
264 ID *tmp,
265 ID *save )
266 {
267 int rc = 0;
268 ComponentFilter *f;
269
270 Debug( LDAP_DEBUG_FILTER, "=> comp_list_candidates 0x%x\n", ftype );
271 for ( f = flist; f != NULL; f = f->cf_next ) {
272 /* ignore precomputed scopes */
273 if ( f->cf_choice == SLAPD_FILTER_COMPUTED &&
274 f->cf_result == LDAP_SUCCESS ) {
275 continue;
276 }
277 MDB_IDL_ZERO( save );
278 rc = comp_candidates( op, rtxn, mra, f, save, tmp, save+MDB_idl_um_size );
279
280 if ( rc != 0 ) {
281 if ( ftype == LDAP_COMP_FILTER_AND ) {
282 rc = 0;
283 continue;
284 }
285 break;
286 }
287
288 if ( ftype == LDAP_COMP_FILTER_AND ) {
289 if ( f == flist ) {
290 MDB_IDL_CPY( ids, save );
291 } else {
292 mdb_idl_intersection( ids, save );
293 }
294 if( MDB_IDL_IS_ZERO( ids ) )
295 break;
296 } else {
297 if ( f == flist ) {
298 MDB_IDL_CPY( ids, save );
299 } else {
300 mdb_idl_union( ids, save );
301 }
302 }
303 }
304
305 if( rc == LDAP_SUCCESS ) {
306 Debug( LDAP_DEBUG_FILTER,
307 "<= comp_list_candidates: id=%ld first=%ld last=%ld\n",
308 (long) ids[0],
309 (long) MDB_IDL_FIRST(ids),
310 (long) MDB_IDL_LAST(ids) );
311
312 } else {
313 Debug( LDAP_DEBUG_FILTER,
314 "<= comp_list_candidates: undefined rc=%d\n",
315 rc );
316 }
317
318 return rc;
319 }
320
321 static int
comp_equality_candidates(Operation * op,MDB_txn * rtxn,MatchingRuleAssertion * mra,ComponentAssertion * ca,ID * ids,ID * tmp,ID * stack)322 comp_equality_candidates (
323 Operation *op,
324 MDB_txn *rtxn,
325 MatchingRuleAssertion *mra,
326 ComponentAssertion *ca,
327 ID *ids,
328 ID *tmp,
329 ID *stack)
330 {
331 MDB_dbi dbi;
332 int i;
333 int rc;
334 slap_mask_t mask;
335 struct berval prefix = {0, NULL};
336 struct berval *keys = NULL;
337 MatchingRule *mr = mra->ma_rule;
338 Syntax *sat_syntax;
339 ComponentReference* cr_list, *cr;
340 AttrInfo *ai;
341
342 MDB_IDL_ALL( ids );
343
344 if ( !ca->ca_comp_ref )
345 return 0;
346
347 ai = mdb_attr_mask( op->o_bd->be_private, mra->ma_desc );
348 if( ai ) {
349 cr_list = ai->ai_cr;
350 }
351 else {
352 return 0;
353 }
354 /* find a component reference to be indexed */
355 sat_syntax = ca->ca_ma_rule->smr_syntax;
356 for ( cr = cr_list ; cr ; cr = cr->cr_next ) {
357 if ( cr->cr_string.bv_len == ca->ca_comp_ref->cr_string.bv_len &&
358 strncmp( cr->cr_string.bv_val, ca->ca_comp_ref->cr_string.bv_val,cr->cr_string.bv_len ) == 0 )
359 break;
360 }
361
362 if ( !cr )
363 return 0;
364
365 rc = mdb_index_param( op->o_bd, mra->ma_desc, LDAP_FILTER_EQUALITY,
366 &dbi, &mask, &prefix );
367
368 if( rc != LDAP_SUCCESS ) {
369 return 0;
370 }
371
372 if( !mr ) {
373 return 0;
374 }
375
376 if( !mr->smr_filter ) {
377 return 0;
378 }
379
380 rc = (ca->ca_ma_rule->smr_filter)(
381 LDAP_FILTER_EQUALITY,
382 cr->cr_indexmask,
383 sat_syntax,
384 ca->ca_ma_rule,
385 &prefix,
386 &ca->ca_ma_value,
387 &keys, op->o_tmpmemctx );
388
389 if( rc != LDAP_SUCCESS ) {
390 return 0;
391 }
392
393 if( keys == NULL ) {
394 return 0;
395 }
396 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
397 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
398
399 if( rc == MDB_NOTFOUND ) {
400 MDB_IDL_ZERO( ids );
401 rc = 0;
402 break;
403 } else if( rc != LDAP_SUCCESS ) {
404 break;
405 }
406
407 if( MDB_IDL_IS_ZERO( tmp ) ) {
408 MDB_IDL_ZERO( ids );
409 break;
410 }
411
412 if ( i == 0 ) {
413 MDB_IDL_CPY( ids, tmp );
414 } else {
415 mdb_idl_intersection( ids, tmp );
416 }
417
418 if( MDB_IDL_IS_ZERO( ids ) )
419 break;
420 }
421 ber_bvarray_free_x( keys, op->o_tmpmemctx );
422
423 Debug( LDAP_DEBUG_TRACE,
424 "<= comp_equality_candidates: id=%ld, first=%ld, last=%ld\n",
425 (long) ids[0],
426 (long) MDB_IDL_FIRST(ids),
427 (long) MDB_IDL_LAST(ids) );
428 return( rc );
429 }
430
431 static int
ava_comp_candidates(Operation * op,MDB_txn * rtxn,AttributeAssertion * ava,AttributeAliasing * aa,ID * ids,ID * tmp,ID * stack)432 ava_comp_candidates (
433 Operation *op,
434 MDB_txn *rtxn,
435 AttributeAssertion *ava,
436 AttributeAliasing *aa,
437 ID *ids,
438 ID *tmp,
439 ID *stack )
440 {
441 MatchingRuleAssertion mra;
442
443 mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
444 if ( !mra.ma_rule ) {
445 MDB_IDL_ALL( ids );
446 return 0;
447 }
448 mra.ma_desc = aa->aa_aliased_ad;
449 mra.ma_rule = ava->aa_desc->ad_type->sat_equality;
450
451 return comp_candidates ( op, rtxn, &mra, ava->aa_cf, ids, tmp, stack );
452 }
453
454 static int
comp_candidates(Operation * op,MDB_txn * rtxn,MatchingRuleAssertion * mra,ComponentFilter * f,ID * ids,ID * tmp,ID * stack)455 comp_candidates (
456 Operation *op,
457 MDB_txn *rtxn,
458 MatchingRuleAssertion *mra,
459 ComponentFilter *f,
460 ID *ids,
461 ID *tmp,
462 ID *stack)
463 {
464 int rc;
465
466 if ( !f ) return LDAP_PROTOCOL_ERROR;
467
468 Debug( LDAP_DEBUG_FILTER, "comp_candidates\n" );
469 switch ( f->cf_choice ) {
470 case SLAPD_FILTER_COMPUTED:
471 rc = f->cf_result;
472 break;
473 case LDAP_COMP_FILTER_AND:
474 rc = comp_list_candidates( op, rtxn, mra, f->cf_and, LDAP_COMP_FILTER_AND, ids, tmp, stack );
475 break;
476 case LDAP_COMP_FILTER_OR:
477 rc = comp_list_candidates( op, rtxn, mra, f->cf_or, LDAP_COMP_FILTER_OR, ids, tmp, stack );
478 break;
479 case LDAP_COMP_FILTER_NOT:
480 /* No component indexing supported for NOT filter */
481 Debug( LDAP_DEBUG_FILTER, "\tComponent NOT\n" );
482 MDB_IDL_ALL( ids );
483 rc = LDAP_PROTOCOL_ERROR;
484 break;
485 case LDAP_COMP_FILTER_ITEM:
486 rc = comp_equality_candidates( op, rtxn, mra, f->cf_ca, ids, tmp, stack );
487 break;
488 default:
489 MDB_IDL_ALL( ids );
490 rc = LDAP_PROTOCOL_ERROR;
491 }
492
493 return( rc );
494 }
495 #endif
496
497 static int
ext_candidates(Operation * op,MDB_txn * rtxn,MatchingRuleAssertion * mra,ID * ids,ID * tmp,ID * stack)498 ext_candidates(
499 Operation *op,
500 MDB_txn *rtxn,
501 MatchingRuleAssertion *mra,
502 ID *ids,
503 ID *tmp,
504 ID *stack)
505 {
506 #ifdef LDAP_COMP_MATCH
507 /*
508 * Currently Only Component Indexing for componentFilterMatch is supported
509 * Indexing for an extensible filter is not supported yet
510 */
511 if ( mra->ma_cf ) {
512 return comp_candidates ( op, rtxn, mra, mra->ma_cf, ids, tmp, stack);
513 }
514 #endif
515 if ( mra->ma_desc == slap_schema.si_ad_entryDN ) {
516 int rc;
517 ID id;
518
519 MDB_IDL_ZERO( ids );
520 if ( mra->ma_rule == slap_schema.si_mr_distinguishedNameMatch ) {
521 base:
522 rc = mdb_dn2id( op, rtxn, NULL, &mra->ma_value, &id, NULL, NULL, NULL );
523 if ( rc == MDB_SUCCESS ) {
524 mdb_idl_insert( ids, id );
525 }
526 return 0;
527 } else if ( mra->ma_rule && mra->ma_rule->smr_match ==
528 dnRelativeMatch && dnIsSuffix( &mra->ma_value,
529 op->o_bd->be_nsuffix )) {
530 int scope;
531 if ( mra->ma_rule == slap_schema.si_mr_dnSuperiorMatch ) {
532 mdb_dn2sups( op, rtxn, &mra->ma_value, ids );
533 return 0;
534 }
535 if ( mra->ma_rule == slap_schema.si_mr_dnSubtreeMatch )
536 scope = LDAP_SCOPE_SUBTREE;
537 else if ( mra->ma_rule == slap_schema.si_mr_dnOneLevelMatch )
538 scope = LDAP_SCOPE_ONELEVEL;
539 else if ( mra->ma_rule == slap_schema.si_mr_dnSubordinateMatch )
540 scope = LDAP_SCOPE_SUBORDINATE;
541 else
542 goto base; /* scope = LDAP_SCOPE_BASE; */
543 #if 0
544 if ( scope > LDAP_SCOPE_BASE ) {
545 ei = NULL;
546 rc = mdb_cache_find_ndn( op, rtxn, &mra->ma_value, &ei );
547 if ( ei )
548 mdb_cache_entryinfo_unlock( ei );
549 if ( rc == LDAP_SUCCESS ) {
550 int sc = op->ors_scope;
551 op->ors_scope = scope;
552 rc = mdb_dn2idl( op, rtxn, &mra->ma_value, ei, ids,
553 stack );
554 op->ors_scope = sc;
555 }
556 return 0;
557 }
558 #endif
559 }
560 }
561
562 MDB_IDL_ALL( ids );
563 return 0;
564 }
565
566 static int
list_candidates(Operation * op,MDB_txn * rtxn,Filter * flist,int ftype,ID * ids,ID * tmp,ID * save)567 list_candidates(
568 Operation *op,
569 MDB_txn *rtxn,
570 Filter *flist,
571 int ftype,
572 ID *ids,
573 ID *tmp,
574 ID *save )
575 {
576 int rc = 0;
577 Filter *f;
578
579 Debug( LDAP_DEBUG_FILTER, "=> mdb_list_candidates 0x%x\n", ftype );
580 for ( f = flist; f != NULL; f = f->f_next ) {
581 /* ignore precomputed scopes */
582 if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
583 f->f_result == LDAP_SUCCESS ) {
584 continue;
585 }
586 MDB_IDL_ZERO( save );
587 rc = mdb_filter_candidates( op, rtxn, f, save, tmp,
588 save+MDB_idl_um_size );
589
590 if ( rc != 0 ) {
591 if ( ftype == LDAP_FILTER_AND ) {
592 rc = 0;
593 continue;
594 }
595 break;
596 }
597
598
599 if ( ftype == LDAP_FILTER_AND ) {
600 if ( f == flist ) {
601 MDB_IDL_CPY( ids, save );
602 } else {
603 mdb_idl_intersection( ids, save );
604 }
605 if( MDB_IDL_IS_ZERO( ids ) )
606 break;
607 } else {
608 if ( f == flist ) {
609 MDB_IDL_CPY( ids, save );
610 } else {
611 mdb_idl_union( ids, save );
612 }
613 }
614 }
615
616 if( rc == LDAP_SUCCESS ) {
617 Debug( LDAP_DEBUG_FILTER,
618 "<= mdb_list_candidates: id=%ld first=%ld last=%ld\n",
619 (long) ids[0],
620 (long) MDB_IDL_FIRST(ids),
621 (long) MDB_IDL_LAST(ids) );
622
623 } else {
624 Debug( LDAP_DEBUG_FILTER,
625 "<= mdb_list_candidates: undefined rc=%d\n",
626 rc );
627 }
628
629 return rc;
630 }
631
632 static int
presence_candidates(Operation * op,MDB_txn * rtxn,AttributeDescription * desc,ID * ids)633 presence_candidates(
634 Operation *op,
635 MDB_txn *rtxn,
636 AttributeDescription *desc,
637 ID *ids )
638 {
639 MDB_dbi dbi;
640 int rc;
641 slap_mask_t mask;
642 struct berval prefix = {0, NULL};
643
644 Debug( LDAP_DEBUG_TRACE, "=> mdb_presence_candidates (%s)\n",
645 desc->ad_cname.bv_val );
646
647 MDB_IDL_ALL( ids );
648
649 if( desc == slap_schema.si_ad_objectClass ) {
650 return 0;
651 }
652
653 rc = mdb_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
654 &dbi, &mask, &prefix );
655
656 if( rc == LDAP_INAPPROPRIATE_MATCHING ) {
657 /* not indexed */
658 Debug( LDAP_DEBUG_FILTER,
659 "<= mdb_presence_candidates: (%s) not indexed\n",
660 desc->ad_cname.bv_val );
661 return 0;
662 }
663
664 if( rc != LDAP_SUCCESS ) {
665 Debug( LDAP_DEBUG_TRACE,
666 "<= mdb_presence_candidates: (%s) index_param "
667 "returned=%d\n",
668 desc->ad_cname.bv_val, rc );
669 return 0;
670 }
671
672 if( prefix.bv_val == NULL ) {
673 Debug( LDAP_DEBUG_TRACE,
674 "<= mdb_presence_candidates: (%s) no prefix\n",
675 desc->ad_cname.bv_val );
676 return -1;
677 }
678
679 rc = mdb_key_read( op->o_bd, rtxn, dbi, &prefix, ids, NULL, 0 );
680
681 if( rc == MDB_NOTFOUND ) {
682 MDB_IDL_ZERO( ids );
683 rc = 0;
684 } else if( rc != LDAP_SUCCESS ) {
685 Debug( LDAP_DEBUG_TRACE,
686 "<= mdb_presense_candidates: (%s) "
687 "key read failed (%d)\n",
688 desc->ad_cname.bv_val, rc );
689 goto done;
690 }
691
692 Debug(LDAP_DEBUG_TRACE,
693 "<= mdb_presence_candidates: id=%ld first=%ld last=%ld\n",
694 (long) ids[0],
695 (long) MDB_IDL_FIRST(ids),
696 (long) MDB_IDL_LAST(ids) );
697
698 done:
699 return rc;
700 }
701
702 static int
equality_candidates(Operation * op,MDB_txn * rtxn,AttributeAssertion * ava,ID * ids,ID * tmp)703 equality_candidates(
704 Operation *op,
705 MDB_txn *rtxn,
706 AttributeAssertion *ava,
707 ID *ids,
708 ID *tmp )
709 {
710 MDB_dbi dbi;
711 int i;
712 int rc;
713 slap_mask_t mask;
714 struct berval prefix = {0, NULL};
715 struct berval *keys = NULL;
716 MatchingRule *mr;
717
718 Debug( LDAP_DEBUG_TRACE, "=> mdb_equality_candidates (%s)\n",
719 ava->aa_desc->ad_cname.bv_val );
720
721 if ( ava->aa_desc == slap_schema.si_ad_entryDN ) {
722 ID id;
723 rc = mdb_dn2id( op, rtxn, NULL, &ava->aa_value, &id, NULL, NULL, NULL );
724 if ( rc == LDAP_SUCCESS ) {
725 /* exactly one ID can match */
726 ids[0] = 1;
727 ids[1] = id;
728 }
729 if ( rc == MDB_NOTFOUND ) {
730 MDB_IDL_ZERO( ids );
731 rc = 0;
732 }
733 return rc;
734 }
735
736 MDB_IDL_ALL( ids );
737
738 rc = mdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
739 &dbi, &mask, &prefix );
740
741 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
742 Debug( LDAP_DEBUG_FILTER,
743 "<= mdb_equality_candidates: (%s) not indexed\n",
744 ava->aa_desc->ad_cname.bv_val );
745 return 0;
746 }
747
748 if( rc != LDAP_SUCCESS ) {
749 Debug( LDAP_DEBUG_ANY,
750 "<= mdb_equality_candidates: (%s) "
751 "index_param failed (%d)\n",
752 ava->aa_desc->ad_cname.bv_val, rc );
753 return 0;
754 }
755
756 mr = ava->aa_desc->ad_type->sat_equality;
757 if( !mr ) {
758 return 0;
759 }
760
761 if( !mr->smr_filter ) {
762 return 0;
763 }
764
765 rc = (mr->smr_filter)(
766 LDAP_FILTER_EQUALITY,
767 mask,
768 ava->aa_desc->ad_type->sat_syntax,
769 mr,
770 &prefix,
771 &ava->aa_value,
772 &keys, op->o_tmpmemctx );
773
774 if( rc != LDAP_SUCCESS ) {
775 Debug( LDAP_DEBUG_TRACE,
776 "<= mdb_equality_candidates: (%s, %s) "
777 "MR filter failed (%d)\n",
778 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
779 return 0;
780 }
781
782 if( keys == NULL ) {
783 Debug( LDAP_DEBUG_TRACE,
784 "<= mdb_equality_candidates: (%s) no keys\n",
785 ava->aa_desc->ad_cname.bv_val );
786 return 0;
787 }
788
789 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
790 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
791
792 if( rc == MDB_NOTFOUND ) {
793 MDB_IDL_ZERO( ids );
794 rc = 0;
795 break;
796 } else if( rc != LDAP_SUCCESS ) {
797 Debug( LDAP_DEBUG_TRACE,
798 "<= mdb_equality_candidates: (%s) "
799 "key read failed (%d)\n",
800 ava->aa_desc->ad_cname.bv_val, rc );
801 break;
802 }
803
804 if( MDB_IDL_IS_ZERO( tmp ) ) {
805 Debug( LDAP_DEBUG_TRACE,
806 "<= mdb_equality_candidates: (%s) NULL\n",
807 ava->aa_desc->ad_cname.bv_val );
808 MDB_IDL_ZERO( ids );
809 break;
810 }
811
812 if ( i == 0 ) {
813 MDB_IDL_CPY( ids, tmp );
814 } else {
815 mdb_idl_intersection( ids, tmp );
816 }
817
818 if( MDB_IDL_IS_ZERO( ids ) )
819 break;
820 }
821
822 ber_bvarray_free_x( keys, op->o_tmpmemctx );
823
824 Debug( LDAP_DEBUG_TRACE,
825 "<= mdb_equality_candidates: id=%ld, first=%ld, last=%ld\n",
826 (long) ids[0],
827 (long) MDB_IDL_FIRST(ids),
828 (long) MDB_IDL_LAST(ids) );
829 return( rc );
830 }
831
832
833 static int
approx_candidates(Operation * op,MDB_txn * rtxn,AttributeAssertion * ava,ID * ids,ID * tmp)834 approx_candidates(
835 Operation *op,
836 MDB_txn *rtxn,
837 AttributeAssertion *ava,
838 ID *ids,
839 ID *tmp )
840 {
841 MDB_dbi dbi;
842 int i;
843 int rc;
844 slap_mask_t mask;
845 struct berval prefix = {0, NULL};
846 struct berval *keys = NULL;
847 MatchingRule *mr;
848
849 Debug( LDAP_DEBUG_TRACE, "=> mdb_approx_candidates (%s)\n",
850 ava->aa_desc->ad_cname.bv_val );
851
852 MDB_IDL_ALL( ids );
853
854 rc = mdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
855 &dbi, &mask, &prefix );
856
857 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
858 Debug( LDAP_DEBUG_FILTER,
859 "<= mdb_approx_candidates: (%s) not indexed\n",
860 ava->aa_desc->ad_cname.bv_val );
861 return 0;
862 }
863
864 if( rc != LDAP_SUCCESS ) {
865 Debug( LDAP_DEBUG_ANY,
866 "<= mdb_approx_candidates: (%s) "
867 "index_param failed (%d)\n",
868 ava->aa_desc->ad_cname.bv_val, rc );
869 return 0;
870 }
871
872 mr = ava->aa_desc->ad_type->sat_approx;
873 if( !mr ) {
874 /* no approx matching rule, try equality matching rule */
875 mr = ava->aa_desc->ad_type->sat_equality;
876 }
877
878 if( !mr ) {
879 return 0;
880 }
881
882 if( !mr->smr_filter ) {
883 return 0;
884 }
885
886 rc = (mr->smr_filter)(
887 LDAP_FILTER_APPROX,
888 mask,
889 ava->aa_desc->ad_type->sat_syntax,
890 mr,
891 &prefix,
892 &ava->aa_value,
893 &keys, op->o_tmpmemctx );
894
895 if( rc != LDAP_SUCCESS ) {
896 Debug( LDAP_DEBUG_TRACE,
897 "<= mdb_approx_candidates: (%s, %s) "
898 "MR filter failed (%d)\n",
899 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
900 return 0;
901 }
902
903 if( keys == NULL ) {
904 Debug( LDAP_DEBUG_TRACE,
905 "<= mdb_approx_candidates: (%s) no keys (%s)\n",
906 prefix.bv_val, ava->aa_desc->ad_cname.bv_val );
907 return 0;
908 }
909
910 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
911 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
912
913 if( rc == MDB_NOTFOUND ) {
914 MDB_IDL_ZERO( ids );
915 rc = 0;
916 break;
917 } else if( rc != LDAP_SUCCESS ) {
918 Debug( LDAP_DEBUG_TRACE,
919 "<= mdb_approx_candidates: (%s) "
920 "key read failed (%d)\n",
921 ava->aa_desc->ad_cname.bv_val, rc );
922 break;
923 }
924
925 if( MDB_IDL_IS_ZERO( tmp ) ) {
926 Debug( LDAP_DEBUG_TRACE,
927 "<= mdb_approx_candidates: (%s) NULL\n",
928 ava->aa_desc->ad_cname.bv_val );
929 MDB_IDL_ZERO( ids );
930 break;
931 }
932
933 if ( i == 0 ) {
934 MDB_IDL_CPY( ids, tmp );
935 } else {
936 mdb_idl_intersection( ids, tmp );
937 }
938
939 if( MDB_IDL_IS_ZERO( ids ) )
940 break;
941 }
942
943 ber_bvarray_free_x( keys, op->o_tmpmemctx );
944
945 Debug( LDAP_DEBUG_TRACE, "<= mdb_approx_candidates %ld, first=%ld, last=%ld\n",
946 (long) ids[0],
947 (long) MDB_IDL_FIRST(ids),
948 (long) MDB_IDL_LAST(ids) );
949 return( rc );
950 }
951
952 static int
substring_candidates(Operation * op,MDB_txn * rtxn,SubstringsAssertion * sub,ID * ids,ID * tmp)953 substring_candidates(
954 Operation *op,
955 MDB_txn *rtxn,
956 SubstringsAssertion *sub,
957 ID *ids,
958 ID *tmp )
959 {
960 MDB_dbi dbi;
961 int i;
962 int rc;
963 slap_mask_t mask;
964 struct berval prefix = {0, NULL};
965 struct berval *keys = NULL;
966 MatchingRule *mr;
967
968 Debug( LDAP_DEBUG_TRACE, "=> mdb_substring_candidates (%s)\n",
969 sub->sa_desc->ad_cname.bv_val );
970
971 MDB_IDL_ALL( ids );
972
973 rc = mdb_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
974 &dbi, &mask, &prefix );
975
976 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
977 Debug( LDAP_DEBUG_FILTER,
978 "<= mdb_substring_candidates: (%s) not indexed\n",
979 sub->sa_desc->ad_cname.bv_val );
980 return 0;
981 }
982
983 if( rc != LDAP_SUCCESS ) {
984 Debug( LDAP_DEBUG_ANY,
985 "<= mdb_substring_candidates: (%s) "
986 "index_param failed (%d)\n",
987 sub->sa_desc->ad_cname.bv_val, rc );
988 return 0;
989 }
990
991 mr = sub->sa_desc->ad_type->sat_substr;
992
993 if( !mr ) {
994 return 0;
995 }
996
997 if( !mr->smr_filter ) {
998 return 0;
999 }
1000
1001 rc = (mr->smr_filter)(
1002 LDAP_FILTER_SUBSTRINGS,
1003 mask,
1004 sub->sa_desc->ad_type->sat_syntax,
1005 mr,
1006 &prefix,
1007 sub,
1008 &keys, op->o_tmpmemctx );
1009
1010 if( rc != LDAP_SUCCESS ) {
1011 Debug( LDAP_DEBUG_TRACE,
1012 "<= mdb_substring_candidates: (%s) "
1013 "MR filter failed (%d)\n",
1014 sub->sa_desc->ad_cname.bv_val, rc );
1015 return 0;
1016 }
1017
1018 if( keys == NULL ) {
1019 Debug( LDAP_DEBUG_TRACE,
1020 "<= mdb_substring_candidates: (0x%04lx) no keys (%s)\n",
1021 mask, sub->sa_desc->ad_cname.bv_val );
1022 return 0;
1023 }
1024
1025 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
1026 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[i], tmp, NULL, 0 );
1027
1028 if( rc == MDB_NOTFOUND ) {
1029 MDB_IDL_ZERO( ids );
1030 rc = 0;
1031 break;
1032 } else if( rc != LDAP_SUCCESS ) {
1033 Debug( LDAP_DEBUG_TRACE,
1034 "<= mdb_substring_candidates: (%s) "
1035 "key read failed (%d)\n",
1036 sub->sa_desc->ad_cname.bv_val, rc );
1037 break;
1038 }
1039
1040 if( MDB_IDL_IS_ZERO( tmp ) ) {
1041 Debug( LDAP_DEBUG_TRACE,
1042 "<= mdb_substring_candidates: (%s) NULL\n",
1043 sub->sa_desc->ad_cname.bv_val );
1044 MDB_IDL_ZERO( ids );
1045 break;
1046 }
1047
1048 if ( i == 0 ) {
1049 MDB_IDL_CPY( ids, tmp );
1050 } else {
1051 mdb_idl_intersection( ids, tmp );
1052 }
1053
1054 if( MDB_IDL_IS_ZERO( ids ) )
1055 break;
1056 }
1057
1058 ber_bvarray_free_x( keys, op->o_tmpmemctx );
1059
1060 Debug( LDAP_DEBUG_TRACE, "<= mdb_substring_candidates: %ld, first=%ld, last=%ld\n",
1061 (long) ids[0],
1062 (long) MDB_IDL_FIRST(ids),
1063 (long) MDB_IDL_LAST(ids) );
1064 return( rc );
1065 }
1066
1067 static int
inequality_candidates(Operation * op,MDB_txn * rtxn,AttributeAssertion * ava,ID * ids,ID * tmp,int gtorlt)1068 inequality_candidates(
1069 Operation *op,
1070 MDB_txn *rtxn,
1071 AttributeAssertion *ava,
1072 ID *ids,
1073 ID *tmp,
1074 int gtorlt )
1075 {
1076 MDB_dbi dbi;
1077 int rc;
1078 slap_mask_t mask;
1079 struct berval prefix = {0, NULL};
1080 struct berval *keys = NULL;
1081 MatchingRule *mr;
1082 MDB_cursor *cursor = NULL;
1083
1084 Debug( LDAP_DEBUG_TRACE, "=> mdb_inequality_candidates (%s)\n",
1085 ava->aa_desc->ad_cname.bv_val );
1086
1087 MDB_IDL_ALL( ids );
1088
1089 rc = mdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
1090 &dbi, &mask, &prefix );
1091
1092 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
1093 Debug( LDAP_DEBUG_FILTER,
1094 "<= mdb_inequality_candidates: (%s) not indexed\n",
1095 ava->aa_desc->ad_cname.bv_val );
1096 return 0;
1097 }
1098
1099 if( rc != LDAP_SUCCESS ) {
1100 Debug( LDAP_DEBUG_ANY,
1101 "<= mdb_inequality_candidates: (%s) "
1102 "index_param failed (%d)\n",
1103 ava->aa_desc->ad_cname.bv_val, rc );
1104 return 0;
1105 }
1106
1107 mr = ava->aa_desc->ad_type->sat_equality;
1108 if( !mr ) {
1109 return 0;
1110 }
1111
1112 if( !mr->smr_filter ) {
1113 return 0;
1114 }
1115
1116 rc = (mr->smr_filter)(
1117 LDAP_FILTER_EQUALITY,
1118 mask,
1119 ava->aa_desc->ad_type->sat_syntax,
1120 mr,
1121 &prefix,
1122 &ava->aa_value,
1123 &keys, op->o_tmpmemctx );
1124
1125 if( rc != LDAP_SUCCESS ) {
1126 Debug( LDAP_DEBUG_TRACE,
1127 "<= mdb_inequality_candidates: (%s, %s) "
1128 "MR filter failed (%d)\n",
1129 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
1130 return 0;
1131 }
1132
1133 if( keys == NULL ) {
1134 Debug( LDAP_DEBUG_TRACE,
1135 "<= mdb_inequality_candidates: (%s) no keys\n",
1136 ava->aa_desc->ad_cname.bv_val );
1137 return 0;
1138 }
1139
1140 MDB_IDL_ZERO( ids );
1141 while(1) {
1142 rc = mdb_key_read( op->o_bd, rtxn, dbi, &keys[0], tmp, &cursor, gtorlt );
1143
1144 if( rc == MDB_NOTFOUND ) {
1145 rc = 0;
1146 break;
1147 } else if( rc != LDAP_SUCCESS ) {
1148 Debug( LDAP_DEBUG_TRACE,
1149 "<= mdb_inequality_candidates: (%s) "
1150 "key read failed (%d)\n",
1151 ava->aa_desc->ad_cname.bv_val, rc );
1152 break;
1153 }
1154
1155 if( MDB_IDL_IS_ZERO( tmp ) ) {
1156 Debug( LDAP_DEBUG_TRACE,
1157 "<= mdb_inequality_candidates: (%s) NULL\n",
1158 ava->aa_desc->ad_cname.bv_val );
1159 break;
1160 }
1161
1162 mdb_idl_union( ids, tmp );
1163
1164 if( op->ors_limit && op->ors_limit->lms_s_unchecked != -1 &&
1165 MDB_IDL_N( ids ) >= (unsigned) op->ors_limit->lms_s_unchecked ) {
1166 mdb_cursor_close( cursor );
1167 break;
1168 }
1169 }
1170 ber_bvarray_free_x( keys, op->o_tmpmemctx );
1171
1172 Debug( LDAP_DEBUG_TRACE,
1173 "<= mdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n",
1174 (long) ids[0],
1175 (long) MDB_IDL_FIRST(ids),
1176 (long) MDB_IDL_LAST(ids) );
1177 return( rc );
1178 }
1179