1/* $NetBSD: search.c,v 1.1.1.3 2010/12/12 15:23:00 adam Exp $ */ 2 3/* search.c - search operation */ 4/* OpenLDAP: pkg/ldap/servers/slapd/back-bdb/search.c,v 1.246.2.28 2010/04/15 20:15:19 quanah 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 27static int base_candidate( 28 BackendDB *be, 29 Entry *e, 30 ID *ids ); 31 32static int search_candidates( 33 Operation *op, 34 SlapReply *rs, 35 Entry *e, 36 DB_TXN *txn, 37 ID *ids, 38 ID *scopes ); 39 40static int parse_paged_cookie( Operation *op, SlapReply *rs ); 41 42static void send_paged_response( 43 Operation *op, 44 SlapReply *rs, 45 ID *lastid, 46 int tentries ); 47 48/* Dereference aliases for a single alias entry. Return the final 49 * dereferenced entry on success, NULL on any failure. 50 */ 51static Entry * deref_base ( 52 Operation *op, 53 SlapReply *rs, 54 Entry *e, 55 Entry **matched, 56 DB_TXN *txn, 57 DB_LOCK *lock, 58 ID *tmp, 59 ID *visited ) 60{ 61 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 62 struct berval ndn; 63 EntryInfo *ei; 64 DB_LOCK lockr; 65 66 rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM; 67 rs->sr_text = "maximum deref depth exceeded"; 68 69 for (;;) { 70 /* Remember the last entry we looked at, so we can 71 * report broken links 72 */ 73 *matched = e; 74 75 if (BDB_IDL_N(tmp) >= op->o_bd->be_max_deref_depth) { 76 e = NULL; 77 break; 78 } 79 80 /* If this is part of a subtree or onelevel search, 81 * have we seen this ID before? If so, quit. 82 */ 83 if ( visited && bdb_idl_insert( visited, e->e_id ) ) { 84 e = NULL; 85 break; 86 } 87 88 /* If we've seen this ID during this deref iteration, 89 * we've hit a loop. 90 */ 91 if ( bdb_idl_insert( tmp, e->e_id ) ) { 92 rs->sr_err = LDAP_ALIAS_PROBLEM; 93 rs->sr_text = "circular alias"; 94 e = NULL; 95 break; 96 } 97 98 /* If there was a problem getting the aliasedObjectName, 99 * get_alias_dn will have set the error status. 100 */ 101 if ( get_alias_dn(e, &ndn, &rs->sr_err, &rs->sr_text) ) { 102 e = NULL; 103 break; 104 } 105 106 rs->sr_err = bdb_dn2entry( op, txn, &ndn, &ei, 107 0, &lockr ); 108 if ( rs->sr_err == DB_LOCK_DEADLOCK ) 109 return NULL; 110 111 if ( ei ) { 112 e = ei->bei_e; 113 } else { 114 e = NULL; 115 } 116 117 if (!e) { 118 rs->sr_err = LDAP_ALIAS_PROBLEM; 119 rs->sr_text = "aliasedObject not found"; 120 break; 121 } 122 123 /* Free the previous entry, continue to work with the 124 * one we just retrieved. 125 */ 126 bdb_cache_return_entry_r( bdb, *matched, lock); 127 *lock = lockr; 128 129 /* We found a regular entry. Return this to the caller. The 130 * entry is still locked for Read. 131 */ 132 if (!is_entry_alias(e)) { 133 rs->sr_err = LDAP_SUCCESS; 134 rs->sr_text = NULL; 135 break; 136 } 137 } 138 return e; 139} 140 141/* Look for and dereference all aliases within the search scope. Adds 142 * the dereferenced entries to the "ids" list. Requires "stack" to be 143 * able to hold 8 levels of DB_SIZE IDLs. Of course we're hardcoded to 144 * require a minimum of 8 UM_SIZE IDLs so this is never a problem. 145 */ 146static int search_aliases( 147 Operation *op, 148 SlapReply *rs, 149 Entry *e, 150 DB_TXN *txn, 151 ID *ids, 152 ID *scopes, 153 ID *stack ) 154{ 155 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 156 ID *aliases, *curscop, *subscop, *visited, *newsubs, *oldsubs, *tmp; 157 ID cursora, ida, cursoro, ido, *subscop2; 158 Entry *matched, *a; 159 EntryInfo *ei; 160 struct berval bv_alias = BER_BVC( "alias" ); 161 AttributeAssertion aa_alias = ATTRIBUTEASSERTION_INIT; 162 Filter af; 163 DB_LOCK locka, lockr; 164 int first = 1; 165 166 aliases = stack; /* IDL of all aliases in the database */ 167 curscop = aliases + BDB_IDL_DB_SIZE; /* Aliases in the current scope */ 168 subscop = curscop + BDB_IDL_DB_SIZE; /* The current scope */ 169 visited = subscop + BDB_IDL_DB_SIZE; /* IDs we've seen in this search */ 170 newsubs = visited + BDB_IDL_DB_SIZE; /* New subtrees we've added */ 171 oldsubs = newsubs + BDB_IDL_DB_SIZE; /* Subtrees added previously */ 172 tmp = oldsubs + BDB_IDL_DB_SIZE; /* Scratch space for deref_base() */ 173 174 /* A copy of subscop, because subscop gets clobbered by 175 * the bdb_idl_union/intersection routines 176 */ 177 subscop2 = tmp + BDB_IDL_DB_SIZE; 178 179 af.f_choice = LDAP_FILTER_EQUALITY; 180 af.f_ava = &aa_alias; 181 af.f_av_desc = slap_schema.si_ad_objectClass; 182 af.f_av_value = bv_alias; 183 af.f_next = NULL; 184 185 /* Find all aliases in database */ 186 BDB_IDL_ZERO( aliases ); 187 rs->sr_err = bdb_filter_candidates( op, txn, &af, aliases, 188 curscop, visited ); 189 if (rs->sr_err != LDAP_SUCCESS) { 190 return rs->sr_err; 191 } 192 oldsubs[0] = 1; 193 oldsubs[1] = e->e_id; 194 195 BDB_IDL_ZERO( ids ); 196 BDB_IDL_ZERO( visited ); 197 BDB_IDL_ZERO( newsubs ); 198 199 cursoro = 0; 200 ido = bdb_idl_first( oldsubs, &cursoro ); 201 202 for (;;) { 203 /* Set curscop to only the aliases in the current scope. Start with 204 * all the aliases, obtain the IDL for the current scope, and then 205 * get the intersection of these two IDLs. Add the current scope 206 * to the cumulative list of candidates. 207 */ 208 BDB_IDL_CPY( curscop, aliases ); 209 rs->sr_err = bdb_dn2idl( op, txn, &e->e_nname, BEI(e), subscop, 210 subscop2+BDB_IDL_DB_SIZE ); 211 212 if (first) { 213 first = 0; 214 } else { 215 bdb_cache_return_entry_r (bdb, e, &locka); 216 } 217 if ( rs->sr_err == DB_LOCK_DEADLOCK ) 218 return rs->sr_err; 219 220 BDB_IDL_CPY(subscop2, subscop); 221 rs->sr_err = bdb_idl_intersection(curscop, subscop); 222 bdb_idl_union( ids, subscop2 ); 223 224 /* Dereference all of the aliases in the current scope. */ 225 cursora = 0; 226 for (ida = bdb_idl_first(curscop, &cursora); ida != NOID; 227 ida = bdb_idl_next(curscop, &cursora)) 228 { 229 ei = NULL; 230retry1: 231 rs->sr_err = bdb_cache_find_id(op, txn, 232 ida, &ei, 0, &lockr ); 233 if (rs->sr_err != LDAP_SUCCESS) { 234 if ( rs->sr_err == DB_LOCK_DEADLOCK ) 235 return rs->sr_err; 236 if ( rs->sr_err == DB_LOCK_NOTGRANTED ) 237 goto retry1; 238 continue; 239 } 240 a = ei->bei_e; 241 242 /* This should only happen if the curscop IDL has maxed out and 243 * turned into a range that spans IDs indiscriminately 244 */ 245 if (!is_entry_alias(a)) { 246 bdb_cache_return_entry_r (bdb, a, &lockr); 247 continue; 248 } 249 250 /* Actually dereference the alias */ 251 BDB_IDL_ZERO(tmp); 252 a = deref_base( op, rs, a, &matched, txn, &lockr, 253 tmp, visited ); 254 if (a) { 255 /* If the target was not already in our current candidates, 256 * make note of it in the newsubs list. Also 257 * set it in the scopes list so that bdb_search 258 * can check it. 259 */ 260 if (bdb_idl_insert(ids, a->e_id) == 0) { 261 bdb_idl_insert(newsubs, a->e_id); 262 bdb_idl_insert(scopes, a->e_id); 263 } 264 bdb_cache_return_entry_r( bdb, a, &lockr); 265 266 } else if ( rs->sr_err == DB_LOCK_DEADLOCK ) { 267 return rs->sr_err; 268 } else if (matched) { 269 /* Alias could not be dereferenced, or it deref'd to 270 * an ID we've already seen. Ignore it. 271 */ 272 bdb_cache_return_entry_r( bdb, matched, &lockr ); 273 rs->sr_text = NULL; 274 } 275 } 276 /* If this is a OneLevel search, we're done; oldsubs only had one 277 * ID in it. For a Subtree search, oldsubs may be a list of scope IDs. 278 */ 279 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) break; 280nextido: 281 ido = bdb_idl_next( oldsubs, &cursoro ); 282 283 /* If we're done processing the old scopes, did we add any new 284 * scopes in this iteration? If so, go back and do those now. 285 */ 286 if (ido == NOID) { 287 if (BDB_IDL_IS_ZERO(newsubs)) break; 288 BDB_IDL_CPY(oldsubs, newsubs); 289 BDB_IDL_ZERO(newsubs); 290 cursoro = 0; 291 ido = bdb_idl_first( oldsubs, &cursoro ); 292 } 293 294 /* Find the entry corresponding to the next scope. If it can't 295 * be found, ignore it and move on. This should never happen; 296 * we should never see the ID of an entry that doesn't exist. 297 * Set the name so that the scope's IDL can be retrieved. 298 */ 299 ei = NULL; 300sameido: 301 rs->sr_err = bdb_cache_find_id(op, txn, ido, &ei, 302 0, &locka ); 303 if ( rs->sr_err != LDAP_SUCCESS ) { 304 if ( rs->sr_err == DB_LOCK_DEADLOCK ) 305 return rs->sr_err; 306 if ( rs->sr_err == DB_LOCK_NOTGRANTED ) 307 goto sameido; 308 goto nextido; 309 } 310 e = ei->bei_e; 311 } 312 return rs->sr_err; 313} 314 315int 316bdb_search( Operation *op, SlapReply *rs ) 317{ 318 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 319 ID id, cursor; 320 ID lastid = NOID; 321 ID candidates[BDB_IDL_UM_SIZE]; 322 ID scopes[BDB_IDL_DB_SIZE]; 323 Entry *e = NULL, base, *e_root; 324 Entry *matched = NULL; 325 EntryInfo *ei; 326 AttributeName *attrs; 327 struct berval realbase = BER_BVNULL; 328 slap_mask_t mask; 329 time_t stoptime; 330 int manageDSAit; 331 int tentries = 0; 332 unsigned nentries = 0; 333 int idflag = 0; 334 335 DB_LOCK lock; 336 struct bdb_op_info *opinfo = NULL; 337 DB_TXN *ltid = NULL; 338 OpExtra *oex; 339 340 Debug( LDAP_DEBUG_TRACE, "=> " LDAP_XSTRING(bdb_search) "\n", 0, 0, 0); 341 attrs = op->oq_search.rs_attrs; 342 343 LDAP_SLIST_FOREACH( oex, &op->o_extra, oe_next ) { 344 if ( oex->oe_key == bdb ) 345 break; 346 } 347 opinfo = (struct bdb_op_info *) oex; 348 349 manageDSAit = get_manageDSAit( op ); 350 351 if ( opinfo && opinfo->boi_txn ) { 352 ltid = opinfo->boi_txn; 353 } else { 354 rs->sr_err = bdb_reader_get( op, bdb->bi_dbenv, <id ); 355 356 switch(rs->sr_err) { 357 case 0: 358 break; 359 default: 360 send_ldap_error( op, rs, LDAP_OTHER, "internal error" ); 361 return rs->sr_err; 362 } 363 } 364 365 e_root = bdb->bi_cache.c_dntree.bei_e; 366 if ( op->o_req_ndn.bv_len == 0 ) { 367 /* DIT root special case */ 368 ei = e_root->e_private; 369 rs->sr_err = LDAP_SUCCESS; 370 } else { 371 if ( op->ors_deref & LDAP_DEREF_FINDING ) { 372 BDB_IDL_ZERO(candidates); 373 } 374dn2entry_retry: 375 /* get entry with reader lock */ 376 rs->sr_err = bdb_dn2entry( op, ltid, &op->o_req_ndn, &ei, 377 1, &lock ); 378 } 379 380 switch(rs->sr_err) { 381 case DB_NOTFOUND: 382 matched = ei->bei_e; 383 break; 384 case 0: 385 e = ei->bei_e; 386 break; 387 case DB_LOCK_DEADLOCK: 388 if ( !opinfo ) { 389 ltid->flags &= ~TXN_DEADLOCK; 390 goto dn2entry_retry; 391 } 392 opinfo->boi_err = rs->sr_err; 393 /* FALLTHRU */ 394 case LDAP_BUSY: 395 send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" ); 396 return LDAP_BUSY; 397 case DB_LOCK_NOTGRANTED: 398 goto dn2entry_retry; 399 default: 400 send_ldap_error( op, rs, LDAP_OTHER, "internal error" ); 401 return rs->sr_err; 402 } 403 404 if ( op->ors_deref & LDAP_DEREF_FINDING ) { 405 if ( matched && is_entry_alias( matched )) { 406 struct berval stub; 407 408 stub.bv_val = op->o_req_ndn.bv_val; 409 stub.bv_len = op->o_req_ndn.bv_len - matched->e_nname.bv_len - 1; 410 e = deref_base( op, rs, matched, &matched, ltid, &lock, 411 candidates, NULL ); 412 if ( e ) { 413 build_new_dn( &op->o_req_ndn, &e->e_nname, &stub, 414 op->o_tmpmemctx ); 415 bdb_cache_return_entry_r (bdb, e, &lock); 416 matched = NULL; 417 goto dn2entry_retry; 418 } 419 } else if ( e && is_entry_alias( e )) { 420 e = deref_base( op, rs, e, &matched, ltid, &lock, 421 candidates, NULL ); 422 } 423 } 424 425 if ( e == NULL ) { 426 struct berval matched_dn = BER_BVNULL; 427 428 if ( matched != NULL ) { 429 BerVarray erefs = NULL; 430 431 /* return referral only if "disclose" 432 * is granted on the object */ 433 if ( ! access_allowed( op, matched, 434 slap_schema.si_ad_entry, 435 NULL, ACL_DISCLOSE, NULL ) ) 436 { 437 rs->sr_err = LDAP_NO_SUCH_OBJECT; 438 439 } else { 440 ber_dupbv( &matched_dn, &matched->e_name ); 441 442 erefs = is_entry_referral( matched ) 443 ? get_entry_referrals( op, matched ) 444 : NULL; 445 if ( rs->sr_err == DB_NOTFOUND ) 446 rs->sr_err = LDAP_REFERRAL; 447 rs->sr_matched = matched_dn.bv_val; 448 } 449 450#ifdef SLAP_ZONE_ALLOC 451 slap_zn_runlock(bdb->bi_cache.c_zctx, matched); 452#endif 453 bdb_cache_return_entry_r (bdb, matched, &lock); 454 matched = NULL; 455 456 if ( erefs ) { 457 rs->sr_ref = referral_rewrite( erefs, &matched_dn, 458 &op->o_req_dn, op->oq_search.rs_scope ); 459 ber_bvarray_free( erefs ); 460 } 461 462 } else { 463#ifdef SLAP_ZONE_ALLOC 464 slap_zn_runlock(bdb->bi_cache.c_zctx, matched); 465#endif 466 rs->sr_ref = referral_rewrite( default_referral, 467 NULL, &op->o_req_dn, op->oq_search.rs_scope ); 468 rs->sr_err = rs->sr_ref != NULL ? LDAP_REFERRAL : LDAP_NO_SUCH_OBJECT; 469 } 470 471 send_ldap_result( op, rs ); 472 473 if ( rs->sr_ref ) { 474 ber_bvarray_free( rs->sr_ref ); 475 rs->sr_ref = NULL; 476 } 477 if ( !BER_BVISNULL( &matched_dn ) ) { 478 ber_memfree( matched_dn.bv_val ); 479 rs->sr_matched = NULL; 480 } 481 return rs->sr_err; 482 } 483 484 /* NOTE: __NEW__ "search" access is required 485 * on searchBase object */ 486 if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry, 487 NULL, ACL_SEARCH, NULL, &mask ) ) 488 { 489 if ( !ACL_GRANT( mask, ACL_DISCLOSE ) ) { 490 rs->sr_err = LDAP_NO_SUCH_OBJECT; 491 } else { 492 rs->sr_err = LDAP_INSUFFICIENT_ACCESS; 493 } 494 495#ifdef SLAP_ZONE_ALLOC 496 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 497#endif 498 if ( e != e_root ) { 499 bdb_cache_return_entry_r(bdb, e, &lock); 500 } 501 send_ldap_result( op, rs ); 502 return rs->sr_err; 503 } 504 505 if ( !manageDSAit && e != e_root && is_entry_referral( e ) ) { 506 /* entry is a referral, don't allow add */ 507 struct berval matched_dn = BER_BVNULL; 508 BerVarray erefs = NULL; 509 510 ber_dupbv( &matched_dn, &e->e_name ); 511 erefs = get_entry_referrals( op, e ); 512 513 rs->sr_err = LDAP_REFERRAL; 514 515#ifdef SLAP_ZONE_ALLOC 516 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 517#endif 518 bdb_cache_return_entry_r( bdb, e, &lock ); 519 e = NULL; 520 521 if ( erefs ) { 522 rs->sr_ref = referral_rewrite( erefs, &matched_dn, 523 &op->o_req_dn, op->oq_search.rs_scope ); 524 ber_bvarray_free( erefs ); 525 526 if ( !rs->sr_ref ) { 527 rs->sr_text = "bad_referral object"; 528 } 529 } 530 531 Debug( LDAP_DEBUG_TRACE, 532 LDAP_XSTRING(bdb_search) ": entry is referral\n", 533 0, 0, 0 ); 534 535 rs->sr_matched = matched_dn.bv_val; 536 send_ldap_result( op, rs ); 537 538 ber_bvarray_free( rs->sr_ref ); 539 rs->sr_ref = NULL; 540 ber_memfree( matched_dn.bv_val ); 541 rs->sr_matched = NULL; 542 return 1; 543 } 544 545 if ( get_assert( op ) && 546 ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE )) 547 { 548 rs->sr_err = LDAP_ASSERTION_FAILED; 549#ifdef SLAP_ZONE_ALLOC 550 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 551#endif 552 if ( e != e_root ) { 553 bdb_cache_return_entry_r(bdb, e, &lock); 554 } 555 send_ldap_result( op, rs ); 556 return 1; 557 } 558 559 /* compute it anyway; root does not use it */ 560 stoptime = op->o_time + op->ors_tlimit; 561 562 /* need normalized dn below */ 563 ber_dupbv( &realbase, &e->e_nname ); 564 565 /* Copy info to base, must free entry before accessing the database 566 * in search_candidates, to avoid deadlocks. 567 */ 568 base.e_private = e->e_private; 569 base.e_nname = realbase; 570 base.e_id = e->e_id; 571 572#ifdef SLAP_ZONE_ALLOC 573 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 574#endif 575 if ( e != e_root ) { 576 bdb_cache_return_entry_r(bdb, e, &lock); 577 } 578 e = NULL; 579 580 /* select candidates */ 581 if ( op->oq_search.rs_scope == LDAP_SCOPE_BASE ) { 582 rs->sr_err = base_candidate( op->o_bd, &base, candidates ); 583 584 } else { 585cand_retry: 586 BDB_IDL_ZERO( candidates ); 587 BDB_IDL_ZERO( scopes ); 588 rs->sr_err = search_candidates( op, rs, &base, 589 ltid, candidates, scopes ); 590 if ( rs->sr_err == DB_LOCK_DEADLOCK ) { 591 if ( !opinfo ) { 592 ltid->flags &= ~TXN_DEADLOCK; 593 goto cand_retry; 594 } 595 opinfo->boi_err = rs->sr_err; 596 send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" ); 597 return LDAP_BUSY; 598 } 599 } 600 601 /* start cursor at beginning of candidates. 602 */ 603 cursor = 0; 604 605 if ( candidates[0] == 0 ) { 606 Debug( LDAP_DEBUG_TRACE, 607 LDAP_XSTRING(bdb_search) ": no candidates\n", 608 0, 0, 0 ); 609 610 goto nochange; 611 } 612 613 /* if not root and candidates exceed to-be-checked entries, abort */ 614 if ( op->ors_limit /* isroot == FALSE */ && 615 op->ors_limit->lms_s_unchecked != -1 && 616 BDB_IDL_N(candidates) > (unsigned) op->ors_limit->lms_s_unchecked ) 617 { 618 rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED; 619 send_ldap_result( op, rs ); 620 rs->sr_err = LDAP_SUCCESS; 621 goto done; 622 } 623 624 if ( op->ors_limit == NULL /* isroot == TRUE */ || 625 !op->ors_limit->lms_s_pr_hide ) 626 { 627 tentries = BDB_IDL_N(candidates); 628 } 629 630 if ( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ) { 631 PagedResultsState *ps = op->o_pagedresults_state; 632 /* deferred cookie parsing */ 633 rs->sr_err = parse_paged_cookie( op, rs ); 634 if ( rs->sr_err != LDAP_SUCCESS ) { 635 send_ldap_result( op, rs ); 636 goto done; 637 } 638 639 cursor = (ID) ps->ps_cookie; 640 if ( cursor && ps->ps_size == 0 ) { 641 rs->sr_err = LDAP_SUCCESS; 642 rs->sr_text = "search abandoned by pagedResult size=0"; 643 send_ldap_result( op, rs ); 644 goto done; 645 } 646 id = bdb_idl_first( candidates, &cursor ); 647 if ( id == NOID ) { 648 Debug( LDAP_DEBUG_TRACE, 649 LDAP_XSTRING(bdb_search) 650 ": no paged results candidates\n", 651 0, 0, 0 ); 652 send_paged_response( op, rs, &lastid, 0 ); 653 654 rs->sr_err = LDAP_OTHER; 655 goto done; 656 } 657 nentries = ps->ps_count; 658 if ( id == (ID)ps->ps_cookie ) 659 id = bdb_idl_next( candidates, &cursor ); 660 goto loop_begin; 661 } 662 663 for ( id = bdb_idl_first( candidates, &cursor ); 664 id != NOID ; id = bdb_idl_next( candidates, &cursor ) ) 665 { 666 int scopeok; 667 668loop_begin: 669 670 /* check for abandon */ 671 if ( op->o_abandon ) { 672 rs->sr_err = SLAPD_ABANDON; 673 send_ldap_result( op, rs ); 674 goto done; 675 } 676 677 /* mostly needed by internal searches, 678 * e.g. related to syncrepl, for whom 679 * abandon does not get set... */ 680 if ( slapd_shutdown ) { 681 rs->sr_err = LDAP_UNAVAILABLE; 682 send_ldap_disconnect( op, rs ); 683 goto done; 684 } 685 686 /* check time limit */ 687 if ( op->ors_tlimit != SLAP_NO_LIMIT 688 && slap_get_time() > stoptime ) 689 { 690 rs->sr_err = LDAP_TIMELIMIT_EXCEEDED; 691 rs->sr_ref = rs->sr_v2ref; 692 send_ldap_result( op, rs ); 693 rs->sr_err = LDAP_SUCCESS; 694 goto done; 695 } 696 697 /* If we inspect more entries than will 698 * fit into the entry cache, stop caching 699 * any subsequent entries 700 */ 701 nentries++; 702 if ( nentries > bdb->bi_cache.c_maxsize && !idflag ) { 703 idflag = ID_NOCACHE; 704 } 705 706fetch_entry_retry: 707 /* get the entry with reader lock */ 708 ei = NULL; 709 rs->sr_err = bdb_cache_find_id( op, ltid, 710 id, &ei, idflag, &lock ); 711 712 if (rs->sr_err == LDAP_BUSY) { 713 rs->sr_text = "ldap server busy"; 714 send_ldap_result( op, rs ); 715 goto done; 716 717 } else if ( rs->sr_err == DB_LOCK_DEADLOCK ) { 718 if ( !opinfo ) { 719 ltid->flags &= ~TXN_DEADLOCK; 720 goto fetch_entry_retry; 721 } 722 opinfo->boi_err = rs->sr_err; 723 send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" ); 724 goto done; 725 726 } else if ( rs->sr_err == DB_LOCK_NOTGRANTED ) 727 { 728 goto fetch_entry_retry; 729 } else if ( rs->sr_err == LDAP_OTHER ) { 730 rs->sr_text = "internal error"; 731 send_ldap_result( op, rs ); 732 goto done; 733 } 734 735 if ( ei && rs->sr_err == LDAP_SUCCESS ) { 736 e = ei->bei_e; 737 } else { 738 e = NULL; 739 } 740 741 if ( e == NULL ) { 742 if( !BDB_IDL_IS_RANGE(candidates) ) { 743 /* only complain for non-range IDLs */ 744 Debug( LDAP_DEBUG_TRACE, 745 LDAP_XSTRING(bdb_search) 746 ": candidate %ld not found\n", 747 (long) id, 0, 0 ); 748 } 749 750 goto loop_continue; 751 } 752 753 rs->sr_entry = e; 754 755 if ( is_entry_subentry( e ) ) { 756 if( op->oq_search.rs_scope != LDAP_SCOPE_BASE ) { 757 if(!get_subentries_visibility( op )) { 758 /* only subentries are visible */ 759 goto loop_continue; 760 } 761 762 } else if ( get_subentries( op ) && 763 !get_subentries_visibility( op )) 764 { 765 /* only subentries are visible */ 766 goto loop_continue; 767 } 768 769 } else if ( get_subentries_visibility( op )) { 770 /* only subentries are visible */ 771 goto loop_continue; 772 } 773 774 /* Does this candidate actually satisfy the search scope? 775 * 776 * Note that we don't lock access to the bei_parent pointer. 777 * Since only leaf nodes can be deleted, the parent of any 778 * node will always be a valid node. Also since we have 779 * a Read lock on the data, it cannot be renamed out of the 780 * scope while we are looking at it, and unless we're using 781 * BDB_HIER, its parents cannot be moved either. 782 */ 783 scopeok = 0; 784 switch( op->ors_scope ) { 785 case LDAP_SCOPE_BASE: 786 /* This is always true, yes? */ 787 if ( id == base.e_id ) scopeok = 1; 788 break; 789 790 case LDAP_SCOPE_ONELEVEL: 791 if ( ei->bei_parent->bei_id == base.e_id ) scopeok = 1; 792 break; 793 794#ifdef LDAP_SCOPE_CHILDREN 795 case LDAP_SCOPE_CHILDREN: 796 if ( id == base.e_id ) break; 797 /* Fall-thru */ 798#endif 799 case LDAP_SCOPE_SUBTREE: { 800 EntryInfo *tmp; 801 for ( tmp = BEI(e); tmp; tmp = tmp->bei_parent ) { 802 if ( tmp->bei_id == base.e_id ) { 803 scopeok = 1; 804 break; 805 } 806 } 807 } break; 808 } 809 810 /* aliases were already dereferenced in candidate list */ 811 if ( op->ors_deref & LDAP_DEREF_SEARCHING ) { 812 /* but if the search base is an alias, and we didn't 813 * deref it when finding, return it. 814 */ 815 if ( is_entry_alias(e) && 816 ((op->ors_deref & LDAP_DEREF_FINDING) || 817 !bvmatch(&e->e_nname, &op->o_req_ndn))) 818 { 819 goto loop_continue; 820 } 821 822 /* scopes is only non-empty for onelevel or subtree */ 823 if ( !scopeok && BDB_IDL_N(scopes) ) { 824 unsigned x; 825 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) { 826 x = bdb_idl_search( scopes, e->e_id ); 827 if ( scopes[x] == e->e_id ) scopeok = 1; 828 } else { 829 /* subtree, walk up the tree */ 830 EntryInfo *tmp = BEI(e); 831 for (;tmp->bei_parent; tmp=tmp->bei_parent) { 832 x = bdb_idl_search( scopes, tmp->bei_id ); 833 if ( scopes[x] == tmp->bei_id ) { 834 scopeok = 1; 835 break; 836 } 837 } 838 } 839 } 840 } 841 842 /* Not in scope, ignore it */ 843 if ( !scopeok ) 844 { 845 Debug( LDAP_DEBUG_TRACE, 846 LDAP_XSTRING(bdb_search) 847 ": %ld scope not okay\n", 848 (long) id, 0, 0 ); 849 goto loop_continue; 850 } 851 852 /* 853 * if it's a referral, add it to the list of referrals. only do 854 * this for non-base searches, and don't check the filter 855 * explicitly here since it's only a candidate anyway. 856 */ 857 if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE 858 && is_entry_referral( e ) ) 859 { 860 struct bdb_op_info bois; 861 struct bdb_lock_info blis; 862 BerVarray erefs = get_entry_referrals( op, e ); 863 rs->sr_ref = referral_rewrite( erefs, &e->e_name, NULL, 864 op->oq_search.rs_scope == LDAP_SCOPE_ONELEVEL 865 ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE ); 866 867 /* Must set lockinfo so that entry_release will work */ 868 if (!opinfo) { 869 bois.boi_oe.oe_key = bdb; 870 bois.boi_txn = NULL; 871 bois.boi_err = 0; 872 bois.boi_acl_cache = op->o_do_not_cache; 873 bois.boi_flag = BOI_DONTFREE; 874 bois.boi_locks = &blis; 875 blis.bli_next = NULL; 876 LDAP_SLIST_INSERT_HEAD( &op->o_extra, &bois.boi_oe, 877 oe_next ); 878 } else { 879 blis.bli_next = opinfo->boi_locks; 880 opinfo->boi_locks = &blis; 881 } 882 blis.bli_id = e->e_id; 883 blis.bli_lock = lock; 884 blis.bli_flag = BLI_DONTFREE; 885 886 rs->sr_flags = REP_ENTRY_MUSTRELEASE; 887 888 send_search_reference( op, rs ); 889 890 if ( blis.bli_flag ) { 891#ifdef SLAP_ZONE_ALLOC 892 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 893#endif 894 bdb_cache_return_entry_r(bdb, e, &lock); 895 if ( opinfo ) { 896 opinfo->boi_locks = blis.bli_next; 897 } else { 898 LDAP_SLIST_REMOVE( &op->o_extra, &bois.boi_oe, 899 OpExtra, oe_next ); 900 } 901 } 902 rs->sr_entry = NULL; 903 e = NULL; 904 905 ber_bvarray_free( rs->sr_ref ); 906 ber_bvarray_free( erefs ); 907 rs->sr_ref = NULL; 908 909 goto loop_continue; 910 } 911 912 if ( !manageDSAit && is_entry_glue( e )) { 913 goto loop_continue; 914 } 915 916 /* if it matches the filter and scope, send it */ 917 rs->sr_err = test_filter( op, rs->sr_entry, op->oq_search.rs_filter ); 918 919 if ( rs->sr_err == LDAP_COMPARE_TRUE ) { 920 /* check size limit */ 921 if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) { 922 if ( rs->sr_nentries >= ((PagedResultsState *)op->o_pagedresults_state)->ps_size ) { 923#ifdef SLAP_ZONE_ALLOC 924 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 925#endif 926 bdb_cache_return_entry_r( bdb, e, &lock ); 927 e = NULL; 928 send_paged_response( op, rs, &lastid, tentries ); 929 goto done; 930 } 931 lastid = id; 932 } 933 934 if (e) { 935 struct bdb_op_info bois; 936 struct bdb_lock_info blis; 937 938 /* Must set lockinfo so that entry_release will work */ 939 if (!opinfo) { 940 bois.boi_oe.oe_key = bdb; 941 bois.boi_txn = NULL; 942 bois.boi_err = 0; 943 bois.boi_acl_cache = op->o_do_not_cache; 944 bois.boi_flag = BOI_DONTFREE; 945 bois.boi_locks = &blis; 946 blis.bli_next = NULL; 947 LDAP_SLIST_INSERT_HEAD( &op->o_extra, &bois.boi_oe, 948 oe_next ); 949 } else { 950 blis.bli_next = opinfo->boi_locks; 951 opinfo->boi_locks = &blis; 952 } 953 blis.bli_id = e->e_id; 954 blis.bli_lock = lock; 955 blis.bli_flag = BLI_DONTFREE; 956 957 /* safe default */ 958 rs->sr_attrs = op->oq_search.rs_attrs; 959 rs->sr_operational_attrs = NULL; 960 rs->sr_ctrls = NULL; 961 rs->sr_flags = REP_ENTRY_MUSTRELEASE; 962 rs->sr_err = LDAP_SUCCESS; 963 rs->sr_err = send_search_entry( op, rs ); 964 965 /* send_search_entry will usually free it. 966 * an overlay might leave its own copy here; 967 * bli_flag will be 0 if lock was already released. 968 */ 969 if ( blis.bli_flag ) { 970#ifdef SLAP_ZONE_ALLOC 971 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 972#endif 973 bdb_cache_return_entry_r(bdb, e, &lock); 974 if ( opinfo ) { 975 opinfo->boi_locks = blis.bli_next; 976 } else { 977 LDAP_SLIST_REMOVE( &op->o_extra, &bois.boi_oe, 978 OpExtra, oe_next ); 979 } 980 } 981 rs->sr_entry = NULL; 982 e = NULL; 983 984 switch ( rs->sr_err ) { 985 case LDAP_SUCCESS: /* entry sent ok */ 986 break; 987 default: /* entry not sent */ 988 break; 989 case LDAP_UNAVAILABLE: 990 case LDAP_SIZELIMIT_EXCEEDED: 991 if ( rs->sr_err == LDAP_SIZELIMIT_EXCEEDED ) { 992 rs->sr_ref = rs->sr_v2ref; 993 send_ldap_result( op, rs ); 994 rs->sr_err = LDAP_SUCCESS; 995 996 } else { 997 rs->sr_err = LDAP_OTHER; 998 } 999 goto done; 1000 } 1001 } 1002 1003 } else { 1004 Debug( LDAP_DEBUG_TRACE, 1005 LDAP_XSTRING(bdb_search) 1006 ": %ld does not match filter\n", 1007 (long) id, 0, 0 ); 1008 } 1009 1010loop_continue: 1011 if( e != NULL ) { 1012 /* free reader lock */ 1013#ifdef SLAP_ZONE_ALLOC 1014 slap_zn_runlock(bdb->bi_cache.c_zctx, e); 1015#endif 1016 bdb_cache_return_entry_r( bdb, e , &lock ); 1017 e = NULL; 1018 rs->sr_entry = NULL; 1019 } 1020 } 1021 1022nochange: 1023 rs->sr_ctrls = NULL; 1024 rs->sr_ref = rs->sr_v2ref; 1025 rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL; 1026 rs->sr_rspoid = NULL; 1027 if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) { 1028 send_paged_response( op, rs, NULL, 0 ); 1029 } else { 1030 send_ldap_result( op, rs ); 1031 } 1032 1033 rs->sr_err = LDAP_SUCCESS; 1034 1035done: 1036 if( rs->sr_v2ref ) { 1037 ber_bvarray_free( rs->sr_v2ref ); 1038 rs->sr_v2ref = NULL; 1039 } 1040 if( realbase.bv_val ) ch_free( realbase.bv_val ); 1041 1042 return rs->sr_err; 1043} 1044 1045 1046static int base_candidate( 1047 BackendDB *be, 1048 Entry *e, 1049 ID *ids ) 1050{ 1051 Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n", 1052 e->e_nname.bv_val, (long) e->e_id, 0); 1053 1054 ids[0] = 1; 1055 ids[1] = e->e_id; 1056 return 0; 1057} 1058 1059/* Look for "objectClass Present" in this filter. 1060 * Also count depth of filter tree while we're at it. 1061 */ 1062static int oc_filter( 1063 Filter *f, 1064 int cur, 1065 int *max ) 1066{ 1067 int rc = 0; 1068 1069 assert( f != NULL ); 1070 1071 if( cur > *max ) *max = cur; 1072 1073 switch( f->f_choice ) { 1074 case LDAP_FILTER_PRESENT: 1075 if (f->f_desc == slap_schema.si_ad_objectClass) { 1076 rc = 1; 1077 } 1078 break; 1079 1080 case LDAP_FILTER_AND: 1081 case LDAP_FILTER_OR: 1082 cur++; 1083 for ( f=f->f_and; f; f=f->f_next ) { 1084 (void) oc_filter(f, cur, max); 1085 } 1086 break; 1087 1088 default: 1089 break; 1090 } 1091 return rc; 1092} 1093 1094static void search_stack_free( void *key, void *data ) 1095{ 1096 ber_memfree_x(data, NULL); 1097} 1098 1099static void *search_stack( Operation *op ) 1100{ 1101 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 1102 void *ret = NULL; 1103 1104 if ( op->o_threadctx ) { 1105 ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack, 1106 &ret, NULL ); 1107 } else { 1108 ret = bdb->bi_search_stack; 1109 } 1110 1111 if ( !ret ) { 1112 ret = ch_malloc( bdb->bi_search_stack_depth * BDB_IDL_UM_SIZE 1113 * sizeof( ID ) ); 1114 if ( op->o_threadctx ) { 1115 ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack, 1116 ret, search_stack_free, NULL, NULL ); 1117 } else { 1118 bdb->bi_search_stack = ret; 1119 } 1120 } 1121 return ret; 1122} 1123 1124static int search_candidates( 1125 Operation *op, 1126 SlapReply *rs, 1127 Entry *e, 1128 DB_TXN *txn, 1129 ID *ids, 1130 ID *scopes ) 1131{ 1132 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 1133 int rc, depth = 1; 1134 Filter f, rf, xf, nf; 1135 ID *stack; 1136 AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT; 1137 Filter sf; 1138 AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT; 1139 1140 /* 1141 * This routine takes as input a filter (user-filter) 1142 * and rewrites it as follows: 1143 * (&(scope=DN)[(objectClass=subentry)] 1144 * (|[(objectClass=referral)(objectClass=alias)](user-filter)) 1145 */ 1146 1147 Debug(LDAP_DEBUG_TRACE, 1148 "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n", 1149 e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope ); 1150 1151 xf.f_or = op->oq_search.rs_filter; 1152 xf.f_choice = LDAP_FILTER_OR; 1153 xf.f_next = NULL; 1154 1155 /* If the user's filter uses objectClass=*, 1156 * these clauses are redundant. 1157 */ 1158 if (!oc_filter(op->oq_search.rs_filter, 1, &depth) 1159 && !get_subentries_visibility(op)) { 1160 if( !get_manageDSAit(op) && !get_domainScope(op) ) { 1161 /* match referral objects */ 1162 struct berval bv_ref = BER_BVC( "referral" ); 1163 rf.f_choice = LDAP_FILTER_EQUALITY; 1164 rf.f_ava = &aa_ref; 1165 rf.f_av_desc = slap_schema.si_ad_objectClass; 1166 rf.f_av_value = bv_ref; 1167 rf.f_next = xf.f_or; 1168 xf.f_or = &rf; 1169 depth++; 1170 } 1171 } 1172 1173 f.f_next = NULL; 1174 f.f_choice = LDAP_FILTER_AND; 1175 f.f_and = &nf; 1176 /* Dummy; we compute scope separately now */ 1177 nf.f_choice = SLAPD_FILTER_COMPUTED; 1178 nf.f_result = LDAP_SUCCESS; 1179 nf.f_next = ( xf.f_or == op->oq_search.rs_filter ) 1180 ? op->oq_search.rs_filter : &xf ; 1181 /* Filter depth increased again, adding dummy clause */ 1182 depth++; 1183 1184 if( get_subentries_visibility( op ) ) { 1185 struct berval bv_subentry = BER_BVC( "subentry" ); 1186 sf.f_choice = LDAP_FILTER_EQUALITY; 1187 sf.f_ava = &aa_subentry; 1188 sf.f_av_desc = slap_schema.si_ad_objectClass; 1189 sf.f_av_value = bv_subentry; 1190 sf.f_next = nf.f_next; 1191 nf.f_next = &sf; 1192 } 1193 1194 /* Allocate IDL stack, plus 1 more for former tmp */ 1195 if ( depth+1 > bdb->bi_search_stack_depth ) { 1196 stack = ch_malloc( (depth + 1) * BDB_IDL_UM_SIZE * sizeof( ID ) ); 1197 } else { 1198 stack = search_stack( op ); 1199 } 1200 1201 if( op->ors_deref & LDAP_DEREF_SEARCHING ) { 1202 rc = search_aliases( op, rs, e, txn, ids, scopes, stack ); 1203 } else { 1204 rc = bdb_dn2idl( op, txn, &e->e_nname, BEI(e), ids, stack ); 1205 } 1206 1207 if ( rc == LDAP_SUCCESS ) { 1208 rc = bdb_filter_candidates( op, txn, &f, ids, 1209 stack, stack+BDB_IDL_UM_SIZE ); 1210 } 1211 1212 if ( depth+1 > bdb->bi_search_stack_depth ) { 1213 ch_free( stack ); 1214 } 1215 1216 if( rc ) { 1217 Debug(LDAP_DEBUG_TRACE, 1218 "bdb_search_candidates: failed (rc=%d)\n", 1219 rc, NULL, NULL ); 1220 1221 } else { 1222 Debug(LDAP_DEBUG_TRACE, 1223 "bdb_search_candidates: id=%ld first=%ld last=%ld\n", 1224 (long) ids[0], 1225 (long) BDB_IDL_FIRST(ids), 1226 (long) BDB_IDL_LAST(ids) ); 1227 } 1228 1229 return rc; 1230} 1231 1232static int 1233parse_paged_cookie( Operation *op, SlapReply *rs ) 1234{ 1235 int rc = LDAP_SUCCESS; 1236 PagedResultsState *ps = op->o_pagedresults_state; 1237 1238 /* this function must be invoked only if the pagedResults 1239 * control has been detected, parsed and partially checked 1240 * by the frontend */ 1241 assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ); 1242 1243 /* cookie decoding/checks deferred to backend... */ 1244 if ( ps->ps_cookieval.bv_len ) { 1245 PagedResultsCookie reqcookie; 1246 if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) { 1247 /* bad cookie */ 1248 rs->sr_text = "paged results cookie is invalid"; 1249 rc = LDAP_PROTOCOL_ERROR; 1250 goto done; 1251 } 1252 1253 AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie )); 1254 1255 if ( reqcookie > ps->ps_cookie ) { 1256 /* bad cookie */ 1257 rs->sr_text = "paged results cookie is invalid"; 1258 rc = LDAP_PROTOCOL_ERROR; 1259 goto done; 1260 1261 } else if ( reqcookie < ps->ps_cookie ) { 1262 rs->sr_text = "paged results cookie is invalid or old"; 1263 rc = LDAP_UNWILLING_TO_PERFORM; 1264 goto done; 1265 } 1266 1267 } else { 1268 /* we're going to use ps_cookie */ 1269 op->o_conn->c_pagedresults_state.ps_cookie = 0; 1270 } 1271 1272done:; 1273 1274 return rc; 1275} 1276 1277static void 1278send_paged_response( 1279 Operation *op, 1280 SlapReply *rs, 1281 ID *lastid, 1282 int tentries ) 1283{ 1284 LDAPControl *ctrls[2]; 1285 BerElementBuffer berbuf; 1286 BerElement *ber = (BerElement *)&berbuf; 1287 PagedResultsCookie respcookie; 1288 struct berval cookie; 1289 1290 Debug(LDAP_DEBUG_ARGS, 1291 "send_paged_response: lastid=0x%08lx nentries=%d\n", 1292 lastid ? *lastid : 0, rs->sr_nentries, NULL ); 1293 1294 ctrls[1] = NULL; 1295 1296 ber_init2( ber, NULL, LBER_USE_DER ); 1297 1298 if ( lastid ) { 1299 respcookie = ( PagedResultsCookie )(*lastid); 1300 cookie.bv_len = sizeof( respcookie ); 1301 cookie.bv_val = (char *)&respcookie; 1302 1303 } else { 1304 respcookie = ( PagedResultsCookie )0; 1305 BER_BVSTR( &cookie, "" ); 1306 } 1307 1308 op->o_conn->c_pagedresults_state.ps_cookie = respcookie; 1309 op->o_conn->c_pagedresults_state.ps_count = 1310 ((PagedResultsState *)op->o_pagedresults_state)->ps_count + 1311 rs->sr_nentries; 1312 1313 /* return size of 0 -- no estimate */ 1314 ber_printf( ber, "{iO}", 0, &cookie ); 1315 1316 ctrls[0] = op->o_tmpalloc( sizeof(LDAPControl), op->o_tmpmemctx ); 1317 if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) { 1318 goto done; 1319 } 1320 1321 ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS; 1322 ctrls[0]->ldctl_iscritical = 0; 1323 1324 slap_add_ctrls( op, rs, ctrls ); 1325 rs->sr_err = LDAP_SUCCESS; 1326 send_ldap_result( op, rs ); 1327 1328done: 1329 (void) ber_free_buf( ber ); 1330} 1331 1332