Back to index

openldap  2.4.31
search.c
Go to the documentation of this file.
00001 /* search.c - search operation */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2000-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 
00017 #include "portable.h"
00018 
00019 #include <stdio.h>
00020 #include <ac/string.h>
00021 
00022 #include "back-bdb.h"
00023 #include "idl.h"
00024 
00025 static int base_candidate(
00026        BackendDB     *be,
00027        Entry  *e,
00028        ID            *ids );
00029 
00030 static int search_candidates(
00031        Operation *op,
00032        SlapReply *rs,
00033        Entry *e,
00034        DB_TXN *txn,
00035        ID     *ids,
00036        ID     *scopes );
00037 
00038 static int parse_paged_cookie( Operation *op, SlapReply *rs );
00039 
00040 static void send_paged_response( 
00041        Operation *op,
00042        SlapReply *rs,
00043        ID  *lastid,
00044        int tentries );
00045 
00046 /* Dereference aliases for a single alias entry. Return the final
00047  * dereferenced entry on success, NULL on any failure.
00048  */
00049 static Entry * deref_base (
00050        Operation *op,
00051        SlapReply *rs,
00052        Entry *e,
00053        Entry **matched,
00054        DB_TXN *txn,
00055        DB_LOCK *lock,
00056        ID     *tmp,
00057        ID     *visited )
00058 {
00059        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00060        struct berval ndn;
00061        EntryInfo *ei;
00062        DB_LOCK lockr;
00063 
00064        rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM;
00065        rs->sr_text = "maximum deref depth exceeded";
00066 
00067        for (;;) {
00068               /* Remember the last entry we looked at, so we can
00069                * report broken links
00070                */
00071               *matched = e;
00072 
00073               if (BDB_IDL_N(tmp) >= op->o_bd->be_max_deref_depth) {
00074                      e = NULL;
00075                      break;
00076               }
00077 
00078               /* If this is part of a subtree or onelevel search,
00079                * have we seen this ID before? If so, quit.
00080                */
00081               if ( visited && bdb_idl_insert( visited, e->e_id ) ) {
00082                      e = NULL;
00083                      break;
00084               }
00085 
00086               /* If we've seen this ID during this deref iteration,
00087                * we've hit a loop.
00088                */
00089               if ( bdb_idl_insert( tmp, e->e_id ) ) {
00090                      rs->sr_err = LDAP_ALIAS_PROBLEM;
00091                      rs->sr_text = "circular alias";
00092                      e = NULL;
00093                      break;
00094               }
00095 
00096               /* If there was a problem getting the aliasedObjectName,
00097                * get_alias_dn will have set the error status.
00098                */
00099               if ( get_alias_dn(e, &ndn, &rs->sr_err, &rs->sr_text) ) {
00100                      e = NULL;
00101                      break;
00102               }
00103 
00104               rs->sr_err = bdb_dn2entry( op, txn, &ndn, &ei,
00105                      0, &lockr );
00106               if ( rs->sr_err == DB_LOCK_DEADLOCK )
00107                      return NULL;
00108 
00109               if ( ei ) {
00110                      e = ei->bei_e;
00111               } else {
00112                      e = NULL;
00113               }
00114 
00115               if (!e) {
00116                      rs->sr_err = LDAP_ALIAS_PROBLEM;
00117                      rs->sr_text = "aliasedObject not found";
00118                      break;
00119               }
00120 
00121               /* Free the previous entry, continue to work with the
00122                * one we just retrieved.
00123                */
00124               bdb_cache_return_entry_r( bdb, *matched, lock);
00125               *lock = lockr;
00126 
00127               /* We found a regular entry. Return this to the caller. The
00128                * entry is still locked for Read.
00129                */
00130               if (!is_entry_alias(e)) {
00131                      rs->sr_err = LDAP_SUCCESS;
00132                      rs->sr_text = NULL;
00133                      break;
00134               }
00135        }
00136        return e;
00137 }
00138 
00139 /* Look for and dereference all aliases within the search scope. Adds
00140  * the dereferenced entries to the "ids" list. Requires "stack" to be
00141  * able to hold 8 levels of DB_SIZE IDLs. Of course we're hardcoded to
00142  * require a minimum of 8 UM_SIZE IDLs so this is never a problem.
00143  */
00144 static int search_aliases(
00145        Operation *op,
00146        SlapReply *rs,
00147        Entry *e,
00148        DB_TXN *txn,
00149        ID *ids,
00150        ID *scopes,
00151        ID *stack )
00152 {
00153        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00154        ID *aliases, *curscop, *subscop, *visited, *newsubs, *oldsubs, *tmp;
00155        ID cursora, ida, cursoro, ido, *subscop2;
00156        Entry *matched, *a;
00157        EntryInfo *ei;
00158        struct berval bv_alias = BER_BVC( "alias" );
00159        AttributeAssertion aa_alias = ATTRIBUTEASSERTION_INIT;
00160        Filter af;
00161        DB_LOCK locka, lockr;
00162        int first = 1;
00163 
00164        aliases = stack;     /* IDL of all aliases in the database */
00165        curscop = aliases + BDB_IDL_DB_SIZE;      /* Aliases in the current scope */
00166        subscop = curscop + BDB_IDL_DB_SIZE;      /* The current scope */
00167        visited = subscop + BDB_IDL_DB_SIZE;      /* IDs we've seen in this search */
00168        newsubs = visited + BDB_IDL_DB_SIZE;      /* New subtrees we've added */
00169        oldsubs = newsubs + BDB_IDL_DB_SIZE;      /* Subtrees added previously */
00170        tmp = oldsubs + BDB_IDL_DB_SIZE;   /* Scratch space for deref_base() */
00171 
00172        /* A copy of subscop, because subscop gets clobbered by
00173         * the bdb_idl_union/intersection routines
00174         */
00175        subscop2 = tmp + BDB_IDL_DB_SIZE;
00176 
00177        af.f_choice = LDAP_FILTER_EQUALITY;
00178        af.f_ava = &aa_alias;
00179        af.f_av_desc = slap_schema.si_ad_objectClass;
00180        af.f_av_value = bv_alias;
00181        af.f_next = NULL;
00182 
00183        /* Find all aliases in database */
00184        BDB_IDL_ZERO( aliases );
00185        rs->sr_err = bdb_filter_candidates( op, txn, &af, aliases,
00186               curscop, visited );
00187        if (rs->sr_err != LDAP_SUCCESS) {
00188               return rs->sr_err;
00189        }
00190        oldsubs[0] = 1;
00191        oldsubs[1] = e->e_id;
00192 
00193        BDB_IDL_ZERO( ids );
00194        BDB_IDL_ZERO( visited );
00195        BDB_IDL_ZERO( newsubs );
00196 
00197        cursoro = 0;
00198        ido = bdb_idl_first( oldsubs, &cursoro );
00199 
00200        for (;;) {
00201               /* Set curscop to only the aliases in the current scope. Start with
00202                * all the aliases, obtain the IDL for the current scope, and then
00203                * get the intersection of these two IDLs. Add the current scope
00204                * to the cumulative list of candidates.
00205                */
00206               BDB_IDL_CPY( curscop, aliases );
00207               rs->sr_err = bdb_dn2idl( op, txn, &e->e_nname, BEI(e), subscop,
00208                      subscop2+BDB_IDL_DB_SIZE );
00209 
00210               if (first) {
00211                      first = 0;
00212               } else {
00213                      bdb_cache_return_entry_r (bdb, e, &locka);
00214               }
00215               if ( rs->sr_err == DB_LOCK_DEADLOCK )
00216                      return rs->sr_err;
00217 
00218               BDB_IDL_CPY(subscop2, subscop);
00219               rs->sr_err = bdb_idl_intersection(curscop, subscop);
00220               bdb_idl_union( ids, subscop2 );
00221 
00222               /* Dereference all of the aliases in the current scope. */
00223               cursora = 0;
00224               for (ida = bdb_idl_first(curscop, &cursora); ida != NOID;
00225                      ida = bdb_idl_next(curscop, &cursora))
00226               {
00227                      ei = NULL;
00228 retry1:
00229                      rs->sr_err = bdb_cache_find_id(op, txn,
00230                             ida, &ei, 0, &lockr );
00231                      if (rs->sr_err != LDAP_SUCCESS) {
00232                             if ( rs->sr_err == DB_LOCK_DEADLOCK )
00233                                    return rs->sr_err;
00234                             if ( rs->sr_err == DB_LOCK_NOTGRANTED )
00235                                    goto retry1;
00236                             continue;
00237                      }
00238                      a = ei->bei_e;
00239 
00240                      /* This should only happen if the curscop IDL has maxed out and
00241                       * turned into a range that spans IDs indiscriminately
00242                       */
00243                      if (!is_entry_alias(a)) {
00244                             bdb_cache_return_entry_r (bdb, a, &lockr);
00245                             continue;
00246                      }
00247 
00248                      /* Actually dereference the alias */
00249                      BDB_IDL_ZERO(tmp);
00250                      a = deref_base( op, rs, a, &matched, txn, &lockr,
00251                             tmp, visited );
00252                      if (a) {
00253                             /* If the target was not already in our current candidates,
00254                              * make note of it in the newsubs list. Also
00255                              * set it in the scopes list so that bdb_search
00256                              * can check it.
00257                              */
00258                             if (bdb_idl_insert(ids, a->e_id) == 0) {
00259                                    bdb_idl_insert(newsubs, a->e_id);
00260                                    bdb_idl_insert(scopes, a->e_id);
00261                             }
00262                             bdb_cache_return_entry_r( bdb, a, &lockr);
00263 
00264                      } else if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
00265                             return rs->sr_err;
00266                      } else if (matched) {
00267                             /* Alias could not be dereferenced, or it deref'd to
00268                              * an ID we've already seen. Ignore it.
00269                              */
00270                             bdb_cache_return_entry_r( bdb, matched, &lockr );
00271                             rs->sr_text = NULL;
00272                      }
00273               }
00274               /* If this is a OneLevel search, we're done; oldsubs only had one
00275                * ID in it. For a Subtree search, oldsubs may be a list of scope IDs.
00276                */
00277               if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) break;
00278 nextido:
00279               ido = bdb_idl_next( oldsubs, &cursoro );
00280               
00281               /* If we're done processing the old scopes, did we add any new
00282                * scopes in this iteration? If so, go back and do those now.
00283                */
00284               if (ido == NOID) {
00285                      if (BDB_IDL_IS_ZERO(newsubs)) break;
00286                      BDB_IDL_CPY(oldsubs, newsubs);
00287                      BDB_IDL_ZERO(newsubs);
00288                      cursoro = 0;
00289                      ido = bdb_idl_first( oldsubs, &cursoro );
00290               }
00291 
00292               /* Find the entry corresponding to the next scope. If it can't
00293                * be found, ignore it and move on. This should never happen;
00294                * we should never see the ID of an entry that doesn't exist.
00295                * Set the name so that the scope's IDL can be retrieved.
00296                */
00297               ei = NULL;
00298 sameido:
00299               rs->sr_err = bdb_cache_find_id(op, txn, ido, &ei,
00300                      0, &locka );
00301               if ( rs->sr_err != LDAP_SUCCESS ) {
00302                      if ( rs->sr_err == DB_LOCK_DEADLOCK )
00303                             return rs->sr_err;
00304                      if ( rs->sr_err == DB_LOCK_NOTGRANTED )
00305                             goto sameido;
00306                      goto nextido;
00307               }
00308               e = ei->bei_e;
00309        }
00310        return rs->sr_err;
00311 }
00312 
00313 /* Get the next ID from the DB. Used if the candidate list is
00314  * a range and simple iteration hits missing entryIDs
00315  */
00316 static int
00317 bdb_get_nextid(struct bdb_info *bdb, DB_TXN *ltid, ID *cursor)
00318 {
00319        DBC *curs;
00320        DBT key, data;
00321        ID id, nid;
00322        int rc;
00323 
00324        id = *cursor + 1;
00325        BDB_ID2DISK( id, &nid );
00326        rc = bdb->bi_id2entry->bdi_db->cursor(
00327               bdb->bi_id2entry->bdi_db, ltid, &curs, bdb->bi_db_opflags );
00328        if ( rc )
00329               return rc;
00330        key.data = &nid;
00331        key.size = key.ulen = sizeof(ID);
00332        key.flags = DB_DBT_USERMEM;
00333        data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
00334        data.dlen = data.ulen = 0;
00335        rc = curs->c_get( curs, &key, &data, DB_SET_RANGE );
00336        curs->c_close( curs );
00337        if ( rc )
00338               return rc;
00339        BDB_DISK2ID( &nid, cursor );
00340        return 0;
00341 }
00342 
00343 int
00344 bdb_search( Operation *op, SlapReply *rs )
00345 {
00346        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
00347        ID            id, cursor;
00348        ID            lastid = NOID;
00349        ID            candidates[BDB_IDL_UM_SIZE];
00350        ID            scopes[BDB_IDL_DB_SIZE];
00351        Entry         *e = NULL, base, *e_root;
00352        Entry         *matched = NULL;
00353        EntryInfo     *ei;
00354        AttributeName *attrs;
00355        struct berval realbase = BER_BVNULL;
00356        slap_mask_t   mask;
00357        time_t        stoptime;
00358        int           manageDSAit;
00359        int           tentries = 0;
00360        unsigned      nentries = 0;
00361        int           idflag = 0;
00362 
00363        DB_LOCK              lock;
00364        struct bdb_op_info   *opinfo = NULL;
00365        DB_TXN               *ltid = NULL;
00366        OpExtra *oex;
00367 
00368        Debug( LDAP_DEBUG_TRACE, "=> " LDAP_XSTRING(bdb_search) "\n", 0, 0, 0);
00369        attrs = op->oq_search.rs_attrs;
00370 
00371        LDAP_SLIST_FOREACH( oex, &op->o_extra, oe_next ) {
00372               if ( oex->oe_key == bdb )
00373                      break;
00374        }
00375        opinfo = (struct bdb_op_info *) oex;
00376 
00377        manageDSAit = get_manageDSAit( op );
00378 
00379        if ( opinfo && opinfo->boi_txn ) {
00380               ltid = opinfo->boi_txn;
00381        } else {
00382               rs->sr_err = bdb_reader_get( op, bdb->bi_dbenv, &ltid );
00383 
00384               switch(rs->sr_err) {
00385               case 0:
00386                      break;
00387               default:
00388                      send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
00389                      return rs->sr_err;
00390               }
00391        }
00392 
00393        e_root = bdb->bi_cache.c_dntree.bei_e;
00394        if ( op->o_req_ndn.bv_len == 0 ) {
00395               /* DIT root special case */
00396               ei = e_root->e_private;
00397               rs->sr_err = LDAP_SUCCESS;
00398        } else {
00399               if ( op->ors_deref & LDAP_DEREF_FINDING ) {
00400                      BDB_IDL_ZERO(candidates);
00401               }
00402 dn2entry_retry:
00403               /* get entry with reader lock */
00404               rs->sr_err = bdb_dn2entry( op, ltid, &op->o_req_ndn, &ei,
00405                      1, &lock );
00406        }
00407 
00408        switch(rs->sr_err) {
00409        case DB_NOTFOUND:
00410               matched = ei->bei_e;
00411               break;
00412        case 0:
00413               e = ei->bei_e;
00414               break;
00415        case DB_LOCK_DEADLOCK:
00416               if ( !opinfo ) {
00417                      ltid->flags &= ~TXN_DEADLOCK;
00418                      goto dn2entry_retry;
00419               }
00420               opinfo->boi_err = rs->sr_err;
00421               /* FALLTHRU */
00422        case LDAP_BUSY:
00423               send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
00424               return LDAP_BUSY;
00425        case DB_LOCK_NOTGRANTED:
00426               goto dn2entry_retry;
00427        default:
00428               send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
00429               return rs->sr_err;
00430        }
00431 
00432        if ( op->ors_deref & LDAP_DEREF_FINDING ) {
00433               if ( matched && is_entry_alias( matched )) {
00434                      struct berval stub;
00435 
00436                      stub.bv_val = op->o_req_ndn.bv_val;
00437                      stub.bv_len = op->o_req_ndn.bv_len - matched->e_nname.bv_len - 1;
00438                      e = deref_base( op, rs, matched, &matched, ltid, &lock,
00439                             candidates, NULL );
00440                      if ( e ) {
00441                             build_new_dn( &op->o_req_ndn, &e->e_nname, &stub,
00442                                    op->o_tmpmemctx );
00443                             bdb_cache_return_entry_r (bdb, e, &lock);
00444                             matched = NULL;
00445                             goto dn2entry_retry;
00446                      }
00447               } else if ( e && is_entry_alias( e )) {
00448                      e = deref_base( op, rs, e, &matched, ltid, &lock,
00449                             candidates, NULL );
00450               }
00451        }
00452 
00453        if ( e == NULL ) {
00454               struct berval matched_dn = BER_BVNULL;
00455 
00456               if ( matched != NULL ) {
00457                      BerVarray erefs = NULL;
00458 
00459                      /* return referral only if "disclose"
00460                       * is granted on the object */
00461                      if ( ! access_allowed( op, matched,
00462                                           slap_schema.si_ad_entry,
00463                                           NULL, ACL_DISCLOSE, NULL ) )
00464                      {
00465                             rs->sr_err = LDAP_NO_SUCH_OBJECT;
00466 
00467                      } else {
00468                             ber_dupbv( &matched_dn, &matched->e_name );
00469 
00470                             erefs = is_entry_referral( matched )
00471                                    ? get_entry_referrals( op, matched )
00472                                    : NULL;
00473                             if ( rs->sr_err == DB_NOTFOUND )
00474                                    rs->sr_err = LDAP_REFERRAL;
00475                             rs->sr_matched = matched_dn.bv_val;
00476                      }
00477 
00478 #ifdef SLAP_ZONE_ALLOC
00479                      slap_zn_runlock(bdb->bi_cache.c_zctx, matched);
00480 #endif
00481                      bdb_cache_return_entry_r (bdb, matched, &lock);
00482                      matched = NULL;
00483 
00484                      if ( erefs ) {
00485                             rs->sr_ref = referral_rewrite( erefs, &matched_dn,
00486                                    &op->o_req_dn, op->oq_search.rs_scope );
00487                             ber_bvarray_free( erefs );
00488                      }
00489 
00490               } else {
00491 #ifdef SLAP_ZONE_ALLOC
00492                      slap_zn_runlock(bdb->bi_cache.c_zctx, matched);
00493 #endif
00494                      rs->sr_ref = referral_rewrite( default_referral,
00495                             NULL, &op->o_req_dn, op->oq_search.rs_scope );
00496                      rs->sr_err = rs->sr_ref != NULL ? LDAP_REFERRAL : LDAP_NO_SUCH_OBJECT;
00497               }
00498 
00499               send_ldap_result( op, rs );
00500 
00501               if ( rs->sr_ref ) {
00502                      ber_bvarray_free( rs->sr_ref );
00503                      rs->sr_ref = NULL;
00504               }
00505               if ( !BER_BVISNULL( &matched_dn ) ) {
00506                      ber_memfree( matched_dn.bv_val );
00507                      rs->sr_matched = NULL;
00508               }
00509               return rs->sr_err;
00510        }
00511 
00512        /* NOTE: __NEW__ "search" access is required
00513         * on searchBase object */
00514        if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry,
00515                             NULL, ACL_SEARCH, NULL, &mask ) )
00516        {
00517               if ( !ACL_GRANT( mask, ACL_DISCLOSE ) ) {
00518                      rs->sr_err = LDAP_NO_SUCH_OBJECT;
00519               } else {
00520                      rs->sr_err = LDAP_INSUFFICIENT_ACCESS;
00521               }
00522 
00523 #ifdef SLAP_ZONE_ALLOC
00524               slap_zn_runlock(bdb->bi_cache.c_zctx, e);
00525 #endif
00526               if ( e != e_root ) {
00527                      bdb_cache_return_entry_r(bdb, e, &lock);
00528               }
00529               send_ldap_result( op, rs );
00530               return rs->sr_err;
00531        }
00532 
00533        if ( !manageDSAit && e != e_root && is_entry_referral( e ) ) {
00534               /* entry is a referral, don't allow add */
00535               struct berval matched_dn = BER_BVNULL;
00536               BerVarray erefs = NULL;
00537               
00538               ber_dupbv( &matched_dn, &e->e_name );
00539               erefs = get_entry_referrals( op, e );
00540 
00541               rs->sr_err = LDAP_REFERRAL;
00542 
00543 #ifdef SLAP_ZONE_ALLOC
00544               slap_zn_runlock(bdb->bi_cache.c_zctx, e);
00545 #endif
00546               bdb_cache_return_entry_r( bdb, e, &lock );
00547               e = NULL;
00548 
00549               if ( erefs ) {
00550                      rs->sr_ref = referral_rewrite( erefs, &matched_dn,
00551                             &op->o_req_dn, op->oq_search.rs_scope );
00552                      ber_bvarray_free( erefs );
00553 
00554                      if ( !rs->sr_ref ) {
00555                             rs->sr_text = "bad_referral object";
00556                      }
00557               }
00558 
00559               Debug( LDAP_DEBUG_TRACE,
00560                      LDAP_XSTRING(bdb_search) ": entry is referral\n",
00561                      0, 0, 0 );
00562 
00563               rs->sr_matched = matched_dn.bv_val;
00564               send_ldap_result( op, rs );
00565 
00566               ber_bvarray_free( rs->sr_ref );
00567               rs->sr_ref = NULL;
00568               ber_memfree( matched_dn.bv_val );
00569               rs->sr_matched = NULL;
00570               return 1;
00571        }
00572 
00573        if ( get_assert( op ) &&
00574               ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE ))
00575        {
00576               rs->sr_err = LDAP_ASSERTION_FAILED;
00577 #ifdef SLAP_ZONE_ALLOC
00578               slap_zn_runlock(bdb->bi_cache.c_zctx, e);
00579 #endif
00580               if ( e != e_root ) {
00581                      bdb_cache_return_entry_r(bdb, e, &lock);
00582               }
00583               send_ldap_result( op, rs );
00584               return 1;
00585        }
00586 
00587        /* compute it anyway; root does not use it */
00588        stoptime = op->o_time + op->ors_tlimit;
00589 
00590        /* need normalized dn below */
00591        ber_dupbv( &realbase, &e->e_nname );
00592 
00593        /* Copy info to base, must free entry before accessing the database
00594         * in search_candidates, to avoid deadlocks.
00595         */
00596        base.e_private = e->e_private;
00597        base.e_nname = realbase;
00598        base.e_id = e->e_id;
00599 
00600 #ifdef SLAP_ZONE_ALLOC
00601        slap_zn_runlock(bdb->bi_cache.c_zctx, e);
00602 #endif
00603        if ( e != e_root ) {
00604               bdb_cache_return_entry_r(bdb, e, &lock);
00605        }
00606        e = NULL;
00607 
00608        /* select candidates */
00609        if ( op->oq_search.rs_scope == LDAP_SCOPE_BASE ) {
00610               rs->sr_err = base_candidate( op->o_bd, &base, candidates );
00611 
00612        } else {
00613 cand_retry:
00614               BDB_IDL_ZERO( candidates );
00615               BDB_IDL_ZERO( scopes );
00616               rs->sr_err = search_candidates( op, rs, &base,
00617                      ltid, candidates, scopes );
00618               if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
00619                      if ( !opinfo ) {
00620                             ltid->flags &= ~TXN_DEADLOCK;
00621                             goto cand_retry;
00622                      }
00623                      opinfo->boi_err = rs->sr_err;
00624                      send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
00625                      return LDAP_BUSY;
00626               }
00627        }
00628 
00629        /* start cursor at beginning of candidates.
00630         */
00631        cursor = 0;
00632 
00633        if ( candidates[0] == 0 ) {
00634               Debug( LDAP_DEBUG_TRACE,
00635                      LDAP_XSTRING(bdb_search) ": no candidates\n",
00636                      0, 0, 0 );
00637 
00638               goto nochange;
00639        }
00640 
00641        /* if not root and candidates exceed to-be-checked entries, abort */
00642        if ( op->ors_limit   /* isroot == FALSE */ &&
00643               op->ors_limit->lms_s_unchecked != -1 &&
00644               BDB_IDL_N(candidates) > (unsigned) op->ors_limit->lms_s_unchecked )
00645        {
00646               rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED;
00647               send_ldap_result( op, rs );
00648               rs->sr_err = LDAP_SUCCESS;
00649               goto done;
00650        }
00651 
00652        if ( op->ors_limit == NULL  /* isroot == TRUE */ ||
00653               !op->ors_limit->lms_s_pr_hide )
00654        {
00655               tentries = BDB_IDL_N(candidates);
00656        }
00657 
00658        if ( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ) {
00659               PagedResultsState *ps = op->o_pagedresults_state;
00660               /* deferred cookie parsing */
00661               rs->sr_err = parse_paged_cookie( op, rs );
00662               if ( rs->sr_err != LDAP_SUCCESS ) {
00663                      send_ldap_result( op, rs );
00664                      goto done;
00665               }
00666 
00667               cursor = (ID) ps->ps_cookie;
00668               if ( cursor && ps->ps_size == 0 ) {
00669                      rs->sr_err = LDAP_SUCCESS;
00670                      rs->sr_text = "search abandoned by pagedResult size=0";
00671                      send_ldap_result( op, rs );
00672                      goto done;
00673               }
00674               id = bdb_idl_first( candidates, &cursor );
00675               if ( id == NOID ) {
00676                      Debug( LDAP_DEBUG_TRACE, 
00677                             LDAP_XSTRING(bdb_search)
00678                             ": no paged results candidates\n",
00679                             0, 0, 0 );
00680                      send_paged_response( op, rs, &lastid, 0 );
00681 
00682                      rs->sr_err = LDAP_OTHER;
00683                      goto done;
00684               }
00685               nentries = ps->ps_count;
00686               if ( id == (ID)ps->ps_cookie )
00687                      id = bdb_idl_next( candidates, &cursor );
00688               goto loop_begin;
00689        }
00690 
00691        for ( id = bdb_idl_first( candidates, &cursor );
00692                 id != NOID ; id = bdb_idl_next( candidates, &cursor ) )
00693        {
00694               int scopeok;
00695 
00696 loop_begin:
00697 
00698               /* check for abandon */
00699               if ( op->o_abandon ) {
00700                      rs->sr_err = SLAPD_ABANDON;
00701                      send_ldap_result( op, rs );
00702                      goto done;
00703               }
00704 
00705               /* mostly needed by internal searches,
00706                * e.g. related to syncrepl, for whom
00707                * abandon does not get set... */
00708               if ( slapd_shutdown ) {
00709                      rs->sr_err = LDAP_UNAVAILABLE;
00710                      send_ldap_disconnect( op, rs );
00711                      goto done;
00712               }
00713 
00714               /* check time limit */
00715               if ( op->ors_tlimit != SLAP_NO_LIMIT
00716                             && slap_get_time() > stoptime )
00717               {
00718                      rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
00719                      rs->sr_ref = rs->sr_v2ref;
00720                      send_ldap_result( op, rs );
00721                      rs->sr_err = LDAP_SUCCESS;
00722                      goto done;
00723               }
00724 
00725               /* If we inspect more entries than will
00726                * fit into the entry cache, stop caching
00727                * any subsequent entries
00728                */
00729               nentries++;
00730               if ( nentries > bdb->bi_cache.c_maxsize && !idflag ) {
00731                      idflag = ID_NOCACHE;
00732               }
00733 
00734 fetch_entry_retry:
00735               /* get the entry with reader lock */
00736               ei = NULL;
00737               rs->sr_err = bdb_cache_find_id( op, ltid,
00738                      id, &ei, idflag, &lock );
00739 
00740               if (rs->sr_err == LDAP_BUSY) {
00741                      rs->sr_text = "ldap server busy";
00742                      send_ldap_result( op, rs );
00743                      goto done;
00744 
00745               } else if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
00746                      if ( !opinfo ) {
00747                             ltid->flags &= ~TXN_DEADLOCK;
00748                             goto fetch_entry_retry;
00749                      }
00750 txnfail:
00751                      opinfo->boi_err = rs->sr_err;
00752                      send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
00753                      goto done;
00754 
00755               } else if ( rs->sr_err == DB_LOCK_NOTGRANTED )
00756               {
00757                      goto fetch_entry_retry;
00758               } else if ( rs->sr_err == LDAP_OTHER ) {
00759                      rs->sr_text = "internal error";
00760                      send_ldap_result( op, rs );
00761                      goto done;
00762               }
00763 
00764               if ( ei && rs->sr_err == LDAP_SUCCESS ) {
00765                      e = ei->bei_e;
00766               } else {
00767                      e = NULL;
00768               }
00769 
00770               if ( e == NULL ) {
00771                      if( !BDB_IDL_IS_RANGE(candidates) ) {
00772                             /* only complain for non-range IDLs */
00773                             Debug( LDAP_DEBUG_TRACE,
00774                                    LDAP_XSTRING(bdb_search)
00775                                    ": candidate %ld not found\n",
00776                                    (long) id, 0, 0 );
00777                      } else {
00778                             /* get the next ID from the DB */
00779 id_retry:
00780                             rs->sr_err = bdb_get_nextid( bdb, ltid, &cursor );
00781                             if ( rs->sr_err == DB_NOTFOUND ) {
00782                                    break;
00783                             } else if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
00784                                    if ( opinfo )
00785                                           goto txnfail;
00786                                    ltid->flags &= ~TXN_DEADLOCK;
00787                                    goto id_retry;
00788                             } else if ( rs->sr_err == DB_LOCK_NOTGRANTED ) {
00789                                    goto id_retry;
00790                             }
00791                             if ( rs->sr_err ) {
00792                                    rs->sr_err = LDAP_OTHER;
00793                                    rs->sr_text = "internal error in get_nextid";
00794                                    send_ldap_result( op, rs );
00795                                    goto done;
00796                             }
00797                             cursor--;
00798                      }
00799 
00800                      goto loop_continue;
00801               }
00802 
00803               if ( is_entry_subentry( e ) ) {
00804                      if( op->oq_search.rs_scope != LDAP_SCOPE_BASE ) {
00805                             if(!get_subentries_visibility( op )) {
00806                                    /* only subentries are visible */
00807                                    goto loop_continue;
00808                             }
00809 
00810                      } else if ( get_subentries( op ) &&
00811                             !get_subentries_visibility( op ))
00812                      {
00813                             /* only subentries are visible */
00814                             goto loop_continue;
00815                      }
00816 
00817               } else if ( get_subentries_visibility( op )) {
00818                      /* only subentries are visible */
00819                      goto loop_continue;
00820               }
00821 
00822               /* Does this candidate actually satisfy the search scope?
00823                *
00824                * Note that we don't lock access to the bei_parent pointer.
00825                * Since only leaf nodes can be deleted, the parent of any
00826                * node will always be a valid node. Also since we have
00827                * a Read lock on the data, it cannot be renamed out of the
00828                * scope while we are looking at it, and unless we're using
00829                * BDB_HIER, its parents cannot be moved either.
00830                */
00831               scopeok = 0;
00832               switch( op->ors_scope ) {
00833               case LDAP_SCOPE_BASE:
00834                      /* This is always true, yes? */
00835                      if ( id == base.e_id ) scopeok = 1;
00836                      break;
00837 
00838               case LDAP_SCOPE_ONELEVEL:
00839                      if ( ei->bei_parent->bei_id == base.e_id ) scopeok = 1;
00840                      break;
00841 
00842 #ifdef LDAP_SCOPE_CHILDREN
00843               case LDAP_SCOPE_CHILDREN:
00844                      if ( id == base.e_id ) break;
00845                      /* Fall-thru */
00846 #endif
00847               case LDAP_SCOPE_SUBTREE: {
00848                      EntryInfo *tmp;
00849                      for ( tmp = BEI(e); tmp; tmp = tmp->bei_parent ) {
00850                             if ( tmp->bei_id == base.e_id ) {
00851                                    scopeok = 1;
00852                                    break;
00853                             }
00854                      }
00855                      } break;
00856               }
00857 
00858               /* aliases were already dereferenced in candidate list */
00859               if ( op->ors_deref & LDAP_DEREF_SEARCHING ) {
00860                      /* but if the search base is an alias, and we didn't
00861                       * deref it when finding, return it.
00862                       */
00863                      if ( is_entry_alias(e) &&
00864                             ((op->ors_deref & LDAP_DEREF_FINDING) ||
00865                                    !bvmatch(&e->e_nname, &op->o_req_ndn)))
00866                      {
00867                             goto loop_continue;
00868                      }
00869 
00870                      /* scopes is only non-empty for onelevel or subtree */
00871                      if ( !scopeok && BDB_IDL_N(scopes) ) {
00872                             unsigned x;
00873                             if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
00874                                    x = bdb_idl_search( scopes, e->e_id );
00875                                    if ( scopes[x] == e->e_id ) scopeok = 1;
00876                             } else {
00877                                    /* subtree, walk up the tree */
00878                                    EntryInfo *tmp = BEI(e);
00879                                    for (;tmp->bei_parent; tmp=tmp->bei_parent) {
00880                                           x = bdb_idl_search( scopes, tmp->bei_id );
00881                                           if ( scopes[x] == tmp->bei_id ) {
00882                                                  scopeok = 1;
00883                                                  break;
00884                                           }
00885                                    }
00886                             }
00887                      }
00888               }
00889 
00890               /* Not in scope, ignore it */
00891               if ( !scopeok )
00892               {
00893                      Debug( LDAP_DEBUG_TRACE,
00894                             LDAP_XSTRING(bdb_search)
00895                             ": %ld scope not okay\n",
00896                             (long) id, 0, 0 );
00897                      goto loop_continue;
00898               }
00899 
00900               /*
00901                * if it's a referral, add it to the list of referrals. only do
00902                * this for non-base searches, and don't check the filter
00903                * explicitly here since it's only a candidate anyway.
00904                */
00905               if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE
00906                      && is_entry_referral( e ) )
00907               {
00908                      struct bdb_op_info bois;
00909                      struct bdb_lock_info blis;
00910                      BerVarray erefs = get_entry_referrals( op, e );
00911                      rs->sr_ref = referral_rewrite( erefs, &e->e_name, NULL,
00912                             op->oq_search.rs_scope == LDAP_SCOPE_ONELEVEL
00913                                    ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE );
00914 
00915                      /* Must set lockinfo so that entry_release will work */
00916                      if (!opinfo) {
00917                             bois.boi_oe.oe_key = bdb;
00918                             bois.boi_txn = NULL;
00919                             bois.boi_err = 0;
00920                             bois.boi_acl_cache = op->o_do_not_cache;
00921                             bois.boi_flag = BOI_DONTFREE;
00922                             bois.boi_locks = &blis;
00923                             blis.bli_next = NULL;
00924                             LDAP_SLIST_INSERT_HEAD( &op->o_extra, &bois.boi_oe,
00925                                    oe_next );
00926                      } else {
00927                             blis.bli_next = opinfo->boi_locks;
00928                             opinfo->boi_locks = &blis;
00929                      }
00930                      blis.bli_id = e->e_id;
00931                      blis.bli_lock = lock;
00932                      blis.bli_flag = BLI_DONTFREE;
00933 
00934                      rs->sr_entry = e;
00935                      rs->sr_flags = REP_ENTRY_MUSTRELEASE;
00936 
00937                      send_search_reference( op, rs );
00938 
00939                      if ( blis.bli_flag ) {
00940 #ifdef SLAP_ZONE_ALLOC
00941                             slap_zn_runlock(bdb->bi_cache.c_zctx, e);
00942 #endif
00943                             bdb_cache_return_entry_r(bdb, e, &lock);
00944                             if ( opinfo ) {
00945                                    opinfo->boi_locks = blis.bli_next;
00946                             } else {
00947                                    LDAP_SLIST_REMOVE( &op->o_extra, &bois.boi_oe,
00948                                           OpExtra, oe_next );
00949                             }
00950                      }
00951                      rs->sr_entry = NULL;
00952                      e = NULL;
00953 
00954                      ber_bvarray_free( rs->sr_ref );
00955                      ber_bvarray_free( erefs );
00956                      rs->sr_ref = NULL;
00957 
00958                      goto loop_continue;
00959               }
00960 
00961               if ( !manageDSAit && is_entry_glue( e )) {
00962                      goto loop_continue;
00963               }
00964 
00965               /* if it matches the filter and scope, send it */
00966               rs->sr_err = test_filter( op, e, op->oq_search.rs_filter );
00967 
00968               if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
00969                      /* check size limit */
00970                      if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
00971                             if ( rs->sr_nentries >= ((PagedResultsState *)op->o_pagedresults_state)->ps_size ) {
00972 #ifdef SLAP_ZONE_ALLOC
00973                                    slap_zn_runlock(bdb->bi_cache.c_zctx, e);
00974 #endif
00975                                    bdb_cache_return_entry_r( bdb, e, &lock );
00976                                    e = NULL;
00977                                    send_paged_response( op, rs, &lastid, tentries );
00978                                    goto done;
00979                             }
00980                             lastid = id;
00981                      }
00982 
00983                      if (e) {
00984                             struct bdb_op_info bois;
00985                             struct bdb_lock_info blis;
00986 
00987                             /* Must set lockinfo so that entry_release will work */
00988                             if (!opinfo) {
00989                                    bois.boi_oe.oe_key = bdb;
00990                                    bois.boi_txn = NULL;
00991                                    bois.boi_err = 0;
00992                                    bois.boi_acl_cache = op->o_do_not_cache;
00993                                    bois.boi_flag = BOI_DONTFREE;
00994                                    bois.boi_locks = &blis;
00995                                    blis.bli_next = NULL;
00996                                    LDAP_SLIST_INSERT_HEAD( &op->o_extra, &bois.boi_oe,
00997                                           oe_next );
00998                             } else {
00999                                    blis.bli_next = opinfo->boi_locks;
01000                                    opinfo->boi_locks = &blis;
01001                             }
01002                             blis.bli_id = e->e_id;
01003                             blis.bli_lock = lock;
01004                             blis.bli_flag = BLI_DONTFREE;
01005 
01006                             /* safe default */
01007                             rs->sr_attrs = op->oq_search.rs_attrs;
01008                             rs->sr_operational_attrs = NULL;
01009                             rs->sr_ctrls = NULL;
01010                             rs->sr_entry = e;
01011                             RS_ASSERT( e->e_private != NULL );
01012                             rs->sr_flags = REP_ENTRY_MUSTRELEASE;
01013                             rs->sr_err = LDAP_SUCCESS;
01014                             rs->sr_err = send_search_entry( op, rs );
01015                             rs->sr_attrs = NULL;
01016                             rs->sr_entry = NULL;
01017 
01018                             /* send_search_entry will usually free it.
01019                              * an overlay might leave its own copy here;
01020                              * bli_flag will be 0 if lock was already released.
01021                              */
01022                             if ( blis.bli_flag ) {
01023 #ifdef SLAP_ZONE_ALLOC
01024                                    slap_zn_runlock(bdb->bi_cache.c_zctx, e);
01025 #endif
01026                                    bdb_cache_return_entry_r(bdb, e, &lock);
01027                                    if ( opinfo ) {
01028                                           opinfo->boi_locks = blis.bli_next;
01029                                    } else {
01030                                           LDAP_SLIST_REMOVE( &op->o_extra, &bois.boi_oe,
01031                                                  OpExtra, oe_next );
01032                                    }
01033                             }
01034                             e = NULL;
01035 
01036                             switch ( rs->sr_err ) {
01037                             case LDAP_SUCCESS:   /* entry sent ok */
01038                                    break;
01039                             default:             /* entry not sent */
01040                                    break;
01041                             case LDAP_UNAVAILABLE:
01042                             case LDAP_SIZELIMIT_EXCEEDED:
01043                                    if ( rs->sr_err == LDAP_SIZELIMIT_EXCEEDED ) {
01044                                           rs->sr_ref = rs->sr_v2ref;
01045                                           send_ldap_result( op, rs );
01046                                           rs->sr_err = LDAP_SUCCESS;
01047 
01048                                    } else {
01049                                           rs->sr_err = LDAP_OTHER;
01050                                    }
01051                                    goto done;
01052                             }
01053                      }
01054 
01055               } else {
01056                      Debug( LDAP_DEBUG_TRACE,
01057                             LDAP_XSTRING(bdb_search)
01058                             ": %ld does not match filter\n",
01059                             (long) id, 0, 0 );
01060               }
01061 
01062 loop_continue:
01063               if( e != NULL ) {
01064                      /* free reader lock */
01065 #ifdef SLAP_ZONE_ALLOC
01066                      slap_zn_runlock(bdb->bi_cache.c_zctx, e);
01067 #endif
01068                      bdb_cache_return_entry_r( bdb, e , &lock );
01069                      RS_ASSERT( rs->sr_entry == NULL );
01070                      e = NULL;
01071                      rs->sr_entry = NULL;
01072               }
01073        }
01074 
01075 nochange:
01076        rs->sr_ctrls = NULL;
01077        rs->sr_ref = rs->sr_v2ref;
01078        rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL;
01079        rs->sr_rspoid = NULL;
01080        if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
01081               send_paged_response( op, rs, NULL, 0 );
01082        } else {
01083               send_ldap_result( op, rs );
01084        }
01085 
01086        rs->sr_err = LDAP_SUCCESS;
01087 
01088 done:
01089        if( rs->sr_v2ref ) {
01090               ber_bvarray_free( rs->sr_v2ref );
01091               rs->sr_v2ref = NULL;
01092        }
01093        if( realbase.bv_val ) ch_free( realbase.bv_val );
01094 
01095        return rs->sr_err;
01096 }
01097 
01098 
01099 static int base_candidate(
01100        BackendDB     *be,
01101        Entry  *e,
01102        ID            *ids )
01103 {
01104        Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
01105               e->e_nname.bv_val, (long) e->e_id, 0);
01106 
01107        ids[0] = 1;
01108        ids[1] = e->e_id;
01109        return 0;
01110 }
01111 
01112 /* Look for "objectClass Present" in this filter.
01113  * Also count depth of filter tree while we're at it.
01114  */
01115 static int oc_filter(
01116        Filter *f,
01117        int cur,
01118        int *max )
01119 {
01120        int rc = 0;
01121 
01122        assert( f != NULL );
01123 
01124        if( cur > *max ) *max = cur;
01125 
01126        switch( f->f_choice ) {
01127        case LDAP_FILTER_PRESENT:
01128               if (f->f_desc == slap_schema.si_ad_objectClass) {
01129                      rc = 1;
01130               }
01131               break;
01132 
01133        case LDAP_FILTER_AND:
01134        case LDAP_FILTER_OR:
01135               cur++;
01136               for ( f=f->f_and; f; f=f->f_next ) {
01137                      (void) oc_filter(f, cur, max);
01138               }
01139               break;
01140 
01141        default:
01142               break;
01143        }
01144        return rc;
01145 }
01146 
01147 static void search_stack_free( void *key, void *data )
01148 {
01149        ber_memfree_x(data, NULL);
01150 }
01151 
01152 static void *search_stack( Operation *op )
01153 {
01154        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
01155        void *ret = NULL;
01156 
01157        if ( op->o_threadctx ) {
01158               ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack,
01159                      &ret, NULL );
01160        } else {
01161               ret = bdb->bi_search_stack;
01162        }
01163 
01164        if ( !ret ) {
01165               ret = ch_malloc( bdb->bi_search_stack_depth * BDB_IDL_UM_SIZE
01166                      * sizeof( ID ) );
01167               if ( op->o_threadctx ) {
01168                      ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack,
01169                             ret, search_stack_free, NULL, NULL );
01170               } else {
01171                      bdb->bi_search_stack = ret;
01172               }
01173        }
01174        return ret;
01175 }
01176 
01177 static int search_candidates(
01178        Operation *op,
01179        SlapReply *rs,
01180        Entry *e,
01181        DB_TXN *txn,
01182        ID     *ids,
01183        ID     *scopes )
01184 {
01185        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
01186        int rc, depth = 1;
01187        Filter        f, rf, xf, nf;
01188        ID            *stack;
01189        AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT;
01190        Filter sf;
01191        AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT;
01192 
01193        /*
01194         * This routine takes as input a filter (user-filter)
01195         * and rewrites it as follows:
01196         *     (&(scope=DN)[(objectClass=subentry)]
01197         *            (|[(objectClass=referral)(objectClass=alias)](user-filter))
01198         */
01199 
01200        Debug(LDAP_DEBUG_TRACE,
01201               "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
01202               e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope );
01203 
01204        xf.f_or = op->oq_search.rs_filter;
01205        xf.f_choice = LDAP_FILTER_OR;
01206        xf.f_next = NULL;
01207 
01208        /* If the user's filter uses objectClass=*,
01209         * these clauses are redundant.
01210         */
01211        if (!oc_filter(op->oq_search.rs_filter, 1, &depth)
01212               && !get_subentries_visibility(op)) {
01213               if( !get_manageDSAit(op) && !get_domainScope(op) ) {
01214                      /* match referral objects */
01215                      struct berval bv_ref = BER_BVC( "referral" );
01216                      rf.f_choice = LDAP_FILTER_EQUALITY;
01217                      rf.f_ava = &aa_ref;
01218                      rf.f_av_desc = slap_schema.si_ad_objectClass;
01219                      rf.f_av_value = bv_ref;
01220                      rf.f_next = xf.f_or;
01221                      xf.f_or = &rf;
01222                      depth++;
01223               }
01224        }
01225 
01226        f.f_next = NULL;
01227        f.f_choice = LDAP_FILTER_AND;
01228        f.f_and = &nf;
01229        /* Dummy; we compute scope separately now */
01230        nf.f_choice = SLAPD_FILTER_COMPUTED;
01231        nf.f_result = LDAP_SUCCESS;
01232        nf.f_next = ( xf.f_or == op->oq_search.rs_filter )
01233               ? op->oq_search.rs_filter : &xf ;
01234        /* Filter depth increased again, adding dummy clause */
01235        depth++;
01236 
01237        if( get_subentries_visibility( op ) ) {
01238               struct berval bv_subentry = BER_BVC( "subentry" );
01239               sf.f_choice = LDAP_FILTER_EQUALITY;
01240               sf.f_ava = &aa_subentry;
01241               sf.f_av_desc = slap_schema.si_ad_objectClass;
01242               sf.f_av_value = bv_subentry;
01243               sf.f_next = nf.f_next;
01244               nf.f_next = &sf;
01245        }
01246 
01247        /* Allocate IDL stack, plus 1 more for former tmp */
01248        if ( depth+1 > bdb->bi_search_stack_depth ) {
01249               stack = ch_malloc( (depth + 1) * BDB_IDL_UM_SIZE * sizeof( ID ) );
01250        } else {
01251               stack = search_stack( op );
01252        }
01253 
01254        if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
01255               rc = search_aliases( op, rs, e, txn, ids, scopes, stack );
01256        } else {
01257               rc = bdb_dn2idl( op, txn, &e->e_nname, BEI(e), ids, stack );
01258        }
01259 
01260        if ( rc == LDAP_SUCCESS ) {
01261               rc = bdb_filter_candidates( op, txn, &f, ids,
01262                      stack, stack+BDB_IDL_UM_SIZE );
01263        }
01264 
01265        if ( depth+1 > bdb->bi_search_stack_depth ) {
01266               ch_free( stack );
01267        }
01268 
01269        if( rc ) {
01270               Debug(LDAP_DEBUG_TRACE,
01271                      "bdb_search_candidates: failed (rc=%d)\n",
01272                      rc, NULL, NULL );
01273 
01274        } else {
01275               Debug(LDAP_DEBUG_TRACE,
01276                      "bdb_search_candidates: id=%ld first=%ld last=%ld\n",
01277                      (long) ids[0],
01278                      (long) BDB_IDL_FIRST(ids),
01279                      (long) BDB_IDL_LAST(ids) );
01280        }
01281 
01282        return rc;
01283 }
01284 
01285 static int
01286 parse_paged_cookie( Operation *op, SlapReply *rs )
01287 {
01288        int           rc = LDAP_SUCCESS;
01289        PagedResultsState *ps = op->o_pagedresults_state;
01290 
01291        /* this function must be invoked only if the pagedResults
01292         * control has been detected, parsed and partially checked
01293         * by the frontend */
01294        assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED );
01295 
01296        /* cookie decoding/checks deferred to backend... */
01297        if ( ps->ps_cookieval.bv_len ) {
01298               PagedResultsCookie reqcookie;
01299               if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) {
01300                      /* bad cookie */
01301                      rs->sr_text = "paged results cookie is invalid";
01302                      rc = LDAP_PROTOCOL_ERROR;
01303                      goto done;
01304               }
01305 
01306               AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie ));
01307 
01308               if ( reqcookie > ps->ps_cookie ) {
01309                      /* bad cookie */
01310                      rs->sr_text = "paged results cookie is invalid";
01311                      rc = LDAP_PROTOCOL_ERROR;
01312                      goto done;
01313 
01314               } else if ( reqcookie < ps->ps_cookie ) {
01315                      rs->sr_text = "paged results cookie is invalid or old";
01316                      rc = LDAP_UNWILLING_TO_PERFORM;
01317                      goto done;
01318               }
01319 
01320        } else {
01321               /* we're going to use ps_cookie */
01322               op->o_conn->c_pagedresults_state.ps_cookie = 0;
01323        }
01324 
01325 done:;
01326 
01327        return rc;
01328 }
01329 
01330 static void
01331 send_paged_response( 
01332        Operation     *op,
01333        SlapReply     *rs,
01334        ID            *lastid,
01335        int           tentries )
01336 {
01337        LDAPControl   *ctrls[2];
01338        BerElementBuffer berbuf;
01339        BerElement    *ber = (BerElement *)&berbuf;
01340        PagedResultsCookie respcookie;
01341        struct berval cookie;
01342 
01343        Debug(LDAP_DEBUG_ARGS,
01344               "send_paged_response: lastid=0x%08lx nentries=%d\n", 
01345               lastid ? *lastid : 0, rs->sr_nentries, NULL );
01346 
01347        ctrls[1] = NULL;
01348 
01349        ber_init2( ber, NULL, LBER_USE_DER );
01350 
01351        if ( lastid ) {
01352               respcookie = ( PagedResultsCookie )(*lastid);
01353               cookie.bv_len = sizeof( respcookie );
01354               cookie.bv_val = (char *)&respcookie;
01355 
01356        } else {
01357               respcookie = ( PagedResultsCookie )0;
01358               BER_BVSTR( &cookie, "" );
01359        }
01360 
01361        op->o_conn->c_pagedresults_state.ps_cookie = respcookie;
01362        op->o_conn->c_pagedresults_state.ps_count =
01363               ((PagedResultsState *)op->o_pagedresults_state)->ps_count +
01364               rs->sr_nentries;
01365 
01366        /* return size of 0 -- no estimate */
01367        ber_printf( ber, "{iO}", 0, &cookie ); 
01368 
01369        ctrls[0] = op->o_tmpalloc( sizeof(LDAPControl), op->o_tmpmemctx );
01370        if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) {
01371               goto done;
01372        }
01373 
01374        ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
01375        ctrls[0]->ldctl_iscritical = 0;
01376 
01377        slap_add_ctrls( op, rs, ctrls );
01378        rs->sr_err = LDAP_SUCCESS;
01379        send_ldap_result( op, rs );
01380 
01381 done:
01382        (void) ber_free_buf( ber );
01383 }