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 34static int 35presence_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 105static int 106equality_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 236static int 237approx_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 367static int 368substring_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 496static int 497list_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 567int 568wt_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 669done: 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