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