1 /* $NetBSD: filterindex.c,v 1.2 2021/08/14 16:15:02 christos Exp $ */
2
3 /* OpenLDAP WiredTiger backend */
4 /* $OpenLDAP$ */
5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 2002-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 /* ACKNOWLEDGEMENTS:
19 * This work was developed by HAMANO Tsukasa <hamano@osstech.co.jp>
20 * based on back-bdb for inclusion in OpenLDAP Software.
21 * WiredTiger is a product of MongoDB Inc.
22 */
23
24 #include <sys/cdefs.h>
25 __RCSID("$NetBSD: filterindex.c,v 1.2 2021/08/14 16:15:02 christos Exp $");
26
27 #include "portable.h"
28
29 #include <stdio.h>
30 #include <ac/string.h>
31 #include "back-wt.h"
32 #include "idl.h"
33
34 static int
presence_candidates(Operation * op,wt_ctx * wc,AttributeDescription * desc,ID * ids)35 presence_candidates(
36 Operation *op,
37 wt_ctx *wc,
38 AttributeDescription *desc,
39 ID *ids )
40 {
41 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private;
42 slap_mask_t mask;
43 struct berval prefix = {0, NULL};
44 int rc;
45 WT_CURSOR *cursor = NULL;
46
47 Debug( LDAP_DEBUG_TRACE, "=> wt_presence_candidates (%s)\n",
48 desc->ad_cname.bv_val );
49
50 WT_IDL_ALL( wi, ids );
51
52 if( desc == slap_schema.si_ad_objectClass ) {
53 return 0;
54 }
55
56 rc = wt_index_param( op->o_bd, desc, LDAP_FILTER_PRESENT,
57 &mask, &prefix );
58
59 if( rc == LDAP_INAPPROPRIATE_MATCHING ) {
60 /* not indexed */
61 Debug( LDAP_DEBUG_FILTER,
62 "<= wt_presence_candidates: (%s) not indexed\n",
63 desc->ad_cname.bv_val );
64 return 0;
65 }
66
67 if( rc != LDAP_SUCCESS ) {
68 Debug( LDAP_DEBUG_TRACE,
69 "<= wt_presence_candidates: (%s) index_param "
70 "returned=%d\n",
71 desc->ad_cname.bv_val, rc );
72 return 0;
73 }
74
75 if( prefix.bv_val == NULL ) {
76 Debug( LDAP_DEBUG_TRACE,
77 "<= wt_presence_candidates: (%s) no prefix\n",
78 desc->ad_cname.bv_val );
79 return -1;
80 }
81
82 /* open index cursor */
83 cursor = wt_ctx_index_cursor(wc, &desc->ad_type->sat_cname, 0);
84 if( !cursor ) {
85 Debug( LDAP_DEBUG_ANY,
86 "<= wt_presence_candidates: open index cursor failed: %s\n",
87 desc->ad_type->sat_cname.bv_val );
88 return 0;
89 }
90
91 rc = wt_key_read( op->o_bd, cursor, &prefix, ids, NULL, 0 );
92
93 if(cursor){
94 cursor->close(cursor);
95 }
96 Debug(LDAP_DEBUG_TRACE,
97 "<= wt_presence_candidates: id=%ld first=%ld last=%ld\n",
98 (long) ids[0],
99 (long) WT_IDL_FIRST(ids),
100 (long) WT_IDL_LAST(ids) );
101
102 return 0;
103 }
104
105 static int
equality_candidates(Operation * op,wt_ctx * wc,AttributeAssertion * ava,ID * ids,ID * tmp)106 equality_candidates(
107 Operation *op,
108 wt_ctx *wc,
109 AttributeAssertion *ava,
110 ID *ids,
111 ID *tmp)
112 {
113 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private;
114 slap_mask_t mask;
115 struct berval prefix = {0, NULL};
116 struct berval *keys = NULL;
117 int i;
118 int rc;
119 MatchingRule *mr;
120 WT_CURSOR *cursor = NULL;
121
122 Debug( LDAP_DEBUG_TRACE, "=> wt_equality_candidates (%s)\n",
123 ava->aa_desc->ad_cname.bv_val );
124
125 if ( ava->aa_desc == slap_schema.si_ad_entryDN ) {
126 ID id = NOID;
127 rc = wt_dn2id(op, wc->session, &ava->aa_value, &id);
128 if( rc == 0 ){
129 wt_idl_append_one(ids, id);
130 }else if ( rc == WT_NOTFOUND ) {
131 WT_IDL_ZERO( ids );
132 rc = 0;
133 }
134 return rc;
135 }
136
137 WT_IDL_ALL( wi, ids );
138
139 rc = wt_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY,
140 &mask, &prefix );
141
142 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
143 Debug( LDAP_DEBUG_FILTER,
144 "<= wt_equality_candidates: (%s) not indexed\n",
145 ava->aa_desc->ad_cname.bv_val );
146 return 0;
147 }
148
149 if( rc != LDAP_SUCCESS ) {
150 Debug( LDAP_DEBUG_ANY,
151 "<= wt_equality_candidates: (%s) index_param failed (%d)\n",
152 ava->aa_desc->ad_cname.bv_val, rc );
153 return 0;
154 }
155
156 mr = ava->aa_desc->ad_type->sat_equality;
157 if( !mr ) {
158 return 0;
159 }
160
161 if( !mr->smr_filter ) {
162 return 0;
163 }
164
165 rc = (mr->smr_filter)(
166 LDAP_FILTER_EQUALITY,
167 mask,
168 ava->aa_desc->ad_type->sat_syntax,
169 mr,
170 &prefix,
171 &ava->aa_value,
172 &keys, op->o_tmpmemctx );
173
174 if( rc != LDAP_SUCCESS ) {
175 Debug( LDAP_DEBUG_TRACE,
176 "<= wt_equality_candidates: (%s, %s) "
177 "MR filter failed (%d)\n",
178 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
179 return 0;
180 }
181
182 if( keys == NULL ) {
183 Debug( LDAP_DEBUG_TRACE,
184 "<= wt_equality_candidates: (%s) no keys\n",
185 ava->aa_desc->ad_cname.bv_val );
186 return 0;
187 }
188
189 /* open index cursor */
190 cursor = wt_ctx_index_cursor(wc, &ava->aa_desc->ad_type->sat_cname, 0);
191 if( !cursor ) {
192 Debug( LDAP_DEBUG_ANY,
193 "<= wt_equality_candidates: open index cursor failed: %s\n",
194 ava->aa_desc->ad_type->sat_cname.bv_val );
195 return 0;
196 }
197
198 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
199 rc = wt_key_read( op->o_bd, cursor, &keys[i], tmp, NULL, 0 );
200 if( rc == WT_NOTFOUND ) {
201 WT_IDL_ZERO( ids );
202 rc = 0;
203 break;
204 } else if( rc != LDAP_SUCCESS ) {
205 Debug( LDAP_DEBUG_TRACE,
206 "<= wt_equality_candidates: (%s) "
207 "key read failed (%d)\n",
208 ava->aa_desc->ad_cname.bv_val, rc );
209 break;
210 }
211 if ( i == 0 ) {
212 WT_IDL_CPY( ids, tmp );
213 } else {
214 wt_idl_intersection( ids, tmp );
215 }
216
217 if( WT_IDL_IS_ZERO( ids ) )
218 break;
219 }
220
221 ber_bvarray_free_x( keys, op->o_tmpmemctx );
222
223 if(cursor){
224 cursor->close(cursor);
225 }
226
227 Debug( LDAP_DEBUG_TRACE,
228 "<= wt_equality_candidates: id=%ld, first=%ld, last=%ld\n",
229 (long) ids[0],
230 (long) WT_IDL_FIRST(ids),
231 (long) WT_IDL_LAST(ids) );
232
233 return rc;
234 }
235
236 static int
approx_candidates(Operation * op,wt_ctx * wc,AttributeAssertion * ava,ID * ids,ID * tmp)237 approx_candidates(
238 Operation *op,
239 wt_ctx *wc,
240 AttributeAssertion *ava,
241 ID *ids,
242 ID *tmp )
243 {
244 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private;
245 int i;
246 int rc;
247 slap_mask_t mask;
248 struct berval prefix = {0, NULL};
249 struct berval *keys = NULL;
250 MatchingRule *mr;
251 WT_CURSOR *cursor = NULL;
252
253 Debug( LDAP_DEBUG_TRACE, "=> wt_approx_candidates (%s)\n",
254 ava->aa_desc->ad_cname.bv_val );
255
256 WT_IDL_ALL( wi, ids );
257
258 rc = wt_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_APPROX,
259 &mask, &prefix );
260
261 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
262 Debug( LDAP_DEBUG_FILTER,
263 "<= wt_approx_candidates: (%s) not indexed\n",
264 ava->aa_desc->ad_cname.bv_val );
265 return 0;
266 }
267
268 if( rc != LDAP_SUCCESS ) {
269 Debug( LDAP_DEBUG_ANY,
270 "<= wt_approx_candidates: (%s) index_param failed (%d)\n",
271 ava->aa_desc->ad_cname.bv_val, rc );
272 return 0;
273 }
274
275 mr = ava->aa_desc->ad_type->sat_approx;
276 if( !mr ) {
277 /* no approx matching rule, try equality matching rule */
278 mr = ava->aa_desc->ad_type->sat_equality;
279 }
280
281 if( !mr ) {
282 return 0;
283 }
284
285 if( !mr->smr_filter ) {
286 return 0;
287 }
288
289 rc = (mr->smr_filter)(
290 LDAP_FILTER_APPROX,
291 mask,
292 ava->aa_desc->ad_type->sat_syntax,
293 mr,
294 &prefix,
295 &ava->aa_value,
296 &keys, op->o_tmpmemctx );
297
298 if( rc != LDAP_SUCCESS ) {
299 Debug( LDAP_DEBUG_TRACE,
300 "<= wt_approx_candidates: (%s, %s) MR filter failed (%d)\n",
301 prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc );
302 return 0;
303 }
304
305 if( keys == NULL ) {
306 Debug( LDAP_DEBUG_TRACE,
307 "<= wt_approx_candidates: (%s) no keys (%s)\n",
308 prefix.bv_val, ava->aa_desc->ad_cname.bv_val );
309 return 0;
310 }
311
312 /* open index cursor */
313 cursor = wt_ctx_index_cursor(wc, &ava->aa_desc->ad_type->sat_cname, 0);
314 if( !cursor ) {
315 Debug( LDAP_DEBUG_ANY,
316 "<= wt_approx_candidates: open index cursor failed: %s\n",
317 ava->aa_desc->ad_type->sat_cname.bv_val );
318 return 0;
319 }
320
321 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
322 rc = wt_key_read( op->o_bd, cursor, &keys[i], tmp, NULL, 0 );
323 if( rc == WT_NOTFOUND ) {
324 WT_IDL_ZERO( ids );
325 rc = 0;
326 break;
327 } else if( rc != LDAP_SUCCESS ) {
328 Debug( LDAP_DEBUG_TRACE,
329 "<= wt_approx_candidates: (%s) key read failed (%d)\n",
330 ava->aa_desc->ad_cname.bv_val, rc );
331 break;
332 }
333
334 if( WT_IDL_IS_ZERO( tmp ) ) {
335 Debug( LDAP_DEBUG_TRACE,
336 "<= wt_approx_candidates: (%s) NULL\n",
337 ava->aa_desc->ad_cname.bv_val );
338 WT_IDL_ZERO( ids );
339 break;
340 }
341
342 if ( i == 0 ) {
343 WT_IDL_CPY( ids, tmp );
344 } else {
345 wt_idl_intersection( ids, tmp );
346 }
347
348 if( WT_IDL_IS_ZERO( ids ) )
349 break;
350 }
351
352 ber_bvarray_free_x( keys, op->o_tmpmemctx );
353
354 if(cursor){
355 cursor->close(cursor);
356 }
357
358 Debug( LDAP_DEBUG_TRACE,
359 "<= wt_approx_candidates %ld, first=%ld, last=%ld\n",
360 (long) ids[0],
361 (long) WT_IDL_FIRST(ids),
362 (long) WT_IDL_LAST(ids) );
363
364 return rc;
365 }
366
367 static int
substring_candidates(Operation * op,wt_ctx * wc,SubstringsAssertion * sub,ID * ids,ID * tmp)368 substring_candidates(
369 Operation *op,
370 wt_ctx *wc,
371 SubstringsAssertion *sub,
372 ID *ids,
373 ID *tmp )
374 {
375 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private;
376 int i;
377 int rc;
378 slap_mask_t mask;
379 struct berval prefix = {0, NULL};
380 struct berval *keys = NULL;
381 MatchingRule *mr;
382 WT_CURSOR *cursor = NULL;
383
384 Debug( LDAP_DEBUG_TRACE, "=> wt_substring_candidates (%s)\n",
385 sub->sa_desc->ad_cname.bv_val );
386
387 WT_IDL_ALL( wi, ids );
388
389 rc = wt_index_param( op->o_bd, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
390 &mask, &prefix );
391
392 if ( rc == LDAP_INAPPROPRIATE_MATCHING ) {
393 Debug( LDAP_DEBUG_FILTER,
394 "<= wt_substring_candidates: (%s) not indexed\n",
395 sub->sa_desc->ad_cname.bv_val );
396 return 0;
397 }
398
399 if( rc != LDAP_SUCCESS ) {
400 Debug( LDAP_DEBUG_ANY,
401 "<= wt_substring_candidates: (%s) "
402 "index_param failed (%d)\n",
403 sub->sa_desc->ad_cname.bv_val, rc );
404 return 0;
405 }
406
407 mr = sub->sa_desc->ad_type->sat_substr;
408
409 if( !mr ) {
410 return 0;
411 }
412
413 if( !mr->smr_filter ) {
414 return 0;
415 }
416
417 rc = (mr->smr_filter)(
418 LDAP_FILTER_SUBSTRINGS,
419 mask,
420 sub->sa_desc->ad_type->sat_syntax,
421 mr,
422 &prefix,
423 sub,
424 &keys, op->o_tmpmemctx );
425
426 if( rc != LDAP_SUCCESS ) {
427 Debug( LDAP_DEBUG_TRACE,
428 "<= wt_substring_candidates: (%s) MR filter failed (%d)\n",
429 sub->sa_desc->ad_cname.bv_val, rc );
430 return 0;
431 }
432
433 if( keys == NULL ) {
434 Debug( LDAP_DEBUG_TRACE,
435 "<= wt_substring_candidates: (0x%04lx) no keys (%s)\n",
436 mask, sub->sa_desc->ad_cname.bv_val );
437 return 0;
438 }
439
440 /* open index cursor */
441 cursor = wt_ctx_index_cursor(wc, &sub->sa_desc->ad_cname, 0);
442 if( !cursor ) {
443 Debug( LDAP_DEBUG_ANY,
444 "<= wt_substring_candidates: open index cursor failed: %s\n",
445 sub->sa_desc->ad_cname.bv_val );
446 return 0;
447 }
448
449 for ( i= 0; keys[i].bv_val != NULL; i++ ) {
450 rc = wt_key_read( op->o_bd, cursor, &keys[i], tmp, NULL, 0 );
451
452 if( rc == WT_NOTFOUND ) {
453 WT_IDL_ZERO( ids );
454 rc = 0;
455 break;
456 } else if( rc != LDAP_SUCCESS ) {
457 Debug( LDAP_DEBUG_TRACE,
458 "<= wt_substring_candidates: (%s) key read failed (%d)\n",
459 sub->sa_desc->ad_cname.bv_val, rc );
460 break;
461 }
462
463 if( WT_IDL_IS_ZERO( tmp ) ) {
464 Debug( LDAP_DEBUG_TRACE,
465 "<= wt_substring_candidates: (%s) NULL\n",
466 sub->sa_desc->ad_cname.bv_val );
467 WT_IDL_ZERO( ids );
468 break;
469 }
470
471 if ( i == 0 ) {
472 WT_IDL_CPY( ids, tmp );
473 } else {
474 wt_idl_intersection( ids, tmp );
475 }
476
477 if( WT_IDL_IS_ZERO( ids ) )
478 break;
479 }
480
481 ber_bvarray_free_x( keys, op->o_tmpmemctx );
482
483 if(cursor){
484 cursor->close(cursor);
485 }
486
487 Debug( LDAP_DEBUG_TRACE,
488 "<= wt_substring_candidates: %ld, first=%ld, last=%ld\n",
489 (long) ids[0],
490 (long) WT_IDL_FIRST(ids),
491 (long) WT_IDL_LAST(ids));
492 return rc;
493 }
494
495
496 static int
list_candidates(Operation * op,wt_ctx * wc,Filter * flist,int ftype,ID * ids,ID * tmp,ID * save)497 list_candidates(
498 Operation *op,
499 wt_ctx *wc,
500 Filter *flist,
501 int ftype,
502 ID *ids,
503 ID *tmp,
504 ID *save )
505 {
506 int rc = 0;
507 Filter *f;
508
509 Debug( LDAP_DEBUG_FILTER, "=> wt_list_candidates 0x%x\n", ftype );
510 for ( f = flist; f != NULL; f = f->f_next ) {
511 /* ignore precomputed scopes */
512 if ( f->f_choice == SLAPD_FILTER_COMPUTED &&
513 f->f_result == LDAP_SUCCESS ) {
514 continue;
515 }
516 WT_IDL_ZERO( save );
517 rc = wt_filter_candidates( op, wc, f, save, tmp,
518 save+WT_IDL_UM_SIZE );
519
520 if ( rc != 0 ) {
521 /* TODO: error handling */
522 /*
523 if ( rc == DB_LOCK_DEADLOCK )
524 return rc;
525 */
526 if ( ftype == LDAP_FILTER_AND ) {
527 rc = 0;
528 continue;
529 }
530 break;
531 }
532
533
534 if ( ftype == LDAP_FILTER_AND ) {
535 if ( f == flist ) {
536 WT_IDL_CPY( ids, save );
537 } else {
538 wt_idl_intersection( ids, save );
539 }
540 if( WT_IDL_IS_ZERO( ids ) )
541 break;
542 } else {
543 if ( f == flist ) {
544 WT_IDL_CPY( ids, save );
545 } else {
546 wt_idl_union( ids, save );
547 }
548 }
549 }
550
551 if( rc == LDAP_SUCCESS ) {
552 Debug( LDAP_DEBUG_FILTER,
553 "<= wt_list_candidates: id=%ld first=%ld last=%ld\n",
554 (long) ids[0],
555 (long) WT_IDL_FIRST(ids),
556 (long) WT_IDL_LAST(ids) );
557
558 } else {
559 Debug( LDAP_DEBUG_FILTER,
560 "<= wt_list_candidates: undefined rc=%d\n",
561 rc );
562 }
563
564 return 0;
565 }
566
567 int
wt_filter_candidates(Operation * op,wt_ctx * wc,Filter * f,ID * ids,ID * tmp,ID * stack)568 wt_filter_candidates(
569 Operation *op,
570 wt_ctx *wc,
571 Filter *f,
572 ID *ids,
573 ID *tmp,
574 ID *stack )
575 {
576 struct wt_info *wi = (struct wt_info *)op->o_bd->be_private;
577 int rc = 0;
578 Debug( LDAP_DEBUG_FILTER, "=> wt_filter_candidates\n" );
579
580 if ( f->f_choice & SLAPD_FILTER_UNDEFINED ) {
581 WT_IDL_ZERO( ids );
582 goto done;
583 }
584
585 switch ( f->f_choice ) {
586 case SLAPD_FILTER_COMPUTED:
587 switch( f->f_result ) {
588 case SLAPD_COMPARE_UNDEFINED:
589 /* This technically is not the same as FALSE, but it
590 * certainly will produce no matches.
591 */
592 /* FALL THRU */
593 case LDAP_COMPARE_FALSE:
594 WT_IDL_ZERO( ids );
595 break;
596 case LDAP_COMPARE_TRUE: {
597
598 WT_IDL_ALL( wi, ids );
599 } break;
600 case LDAP_SUCCESS:
601 /* this is a pre-computed scope, leave it alone */
602 break;
603 }
604 break;
605 case LDAP_FILTER_PRESENT:
606 Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n" );
607 rc = presence_candidates( op, wc, f->f_desc, ids );
608 break;
609
610 case LDAP_FILTER_EQUALITY:
611 Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n" );
612 rc = equality_candidates( op, wc, f->f_ava, ids, tmp );
613 break;
614
615 case LDAP_FILTER_APPROX:
616 Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n" );
617 rc = approx_candidates( op, wc, f->f_ava, ids, tmp );
618 break;
619
620 case LDAP_FILTER_SUBSTRINGS:
621 Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n" );
622 rc = substring_candidates( op, wc, f->f_sub, ids, tmp );
623 break;
624
625 case LDAP_FILTER_GE:
626 /* if no GE index, use pres */
627 /* TODO: not implement yet */
628 rc = presence_candidates( op, wc, f->f_ava->aa_desc, ids );
629 break;
630
631 case LDAP_FILTER_LE:
632 /* if no LE index, use pres */
633 /* TODO: not implement yet */
634 Debug( LDAP_DEBUG_FILTER, "\tLE\n" );
635 rc = presence_candidates( op, wc, f->f_ava->aa_desc, ids );
636 break;
637
638 case LDAP_FILTER_NOT:
639 /* no indexing to support NOT filters */
640 Debug( LDAP_DEBUG_FILTER, "\tNOT\n" );
641 WT_IDL_ALL( wi, ids );
642 break;
643
644 case LDAP_FILTER_AND:
645 Debug( LDAP_DEBUG_FILTER, "\tAND\n" );
646 rc = list_candidates( op, wc,
647 f->f_and, LDAP_FILTER_AND, ids, tmp, stack );
648 break;
649
650 case LDAP_FILTER_OR:
651 Debug( LDAP_DEBUG_FILTER, "\tOR\n" );
652 rc = list_candidates( op, wc,
653 f->f_or, LDAP_FILTER_OR, ids, tmp, stack );
654 break;
655
656 case LDAP_FILTER_EXT:
657 /* TODO: not implement yet */
658 Debug( LDAP_DEBUG_FILTER, "\tEXT\n" );
659 rc = presence_candidates( op, wc, f->f_ava->aa_desc, ids );
660 break;
661
662 default:
663 Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %lu\n",
664 (unsigned long) f->f_choice );
665 /* Must not return NULL, otherwise extended filters break */
666 WT_IDL_ALL( wi, ids );
667 }
668
669 done:
670 Debug( LDAP_DEBUG_FILTER,
671 "<= wt_filter_candidates: id=%ld first=%ld last=%ld\n",
672 (long) ids[0],
673 (long) WT_IDL_FIRST( ids ),
674 (long) WT_IDL_LAST( ids ) );
675 return 0;
676 }
677
678 /*
679 * Local variables:
680 * indent-tabs-mode: t
681 * tab-width: 4
682 * c-basic-offset: 4
683 * End:
684 */
685