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