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