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-mdb.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        MDB_txn *txn,
00035        MDB_cursor *mci,
00036        ID     *ids,
00037        ID2L   scopes );
00038 
00039 static int parse_paged_cookie( Operation *op, SlapReply *rs );
00040 
00041 static void send_paged_response( 
00042        Operation *op,
00043        SlapReply *rs,
00044        ID  *lastid,
00045        int tentries );
00046 
00047 /* Dereference aliases for a single alias entry. Return the final
00048  * dereferenced entry on success, NULL on any failure.
00049  */
00050 static Entry * deref_base (
00051        Operation *op,
00052        SlapReply *rs,
00053        Entry *e,
00054        Entry **matched,
00055        MDB_txn *txn,
00056        ID     *tmp,
00057        ID     *visited )
00058 {
00059        struct berval ndn;
00060 
00061        rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM;
00062        rs->sr_text = "maximum deref depth exceeded";
00063 
00064        for (;;) {
00065               /* Remember the last entry we looked at, so we can
00066                * report broken links
00067                */
00068               *matched = e;
00069 
00070               if (MDB_IDL_N(tmp) >= op->o_bd->be_max_deref_depth) {
00071                      e = NULL;
00072                      break;
00073               }
00074 
00075               /* If this is part of a subtree or onelevel search,
00076                * have we seen this ID before? If so, quit.
00077                */
00078               if ( visited && mdb_idl_insert( visited, e->e_id ) ) {
00079                      e = NULL;
00080                      break;
00081               }
00082 
00083               /* If we've seen this ID during this deref iteration,
00084                * we've hit a loop.
00085                */
00086               if ( mdb_idl_insert( tmp, e->e_id ) ) {
00087                      rs->sr_err = LDAP_ALIAS_PROBLEM;
00088                      rs->sr_text = "circular alias";
00089                      e = NULL;
00090                      break;
00091               }
00092 
00093               /* If there was a problem getting the aliasedObjectName,
00094                * get_alias_dn will have set the error status.
00095                */
00096               if ( get_alias_dn(e, &ndn, &rs->sr_err, &rs->sr_text) ) {
00097                      e = NULL;
00098                      break;
00099               }
00100 
00101               rs->sr_err = mdb_dn2entry( op, txn, NULL, &ndn, &e, 0 );
00102               if (rs->sr_err) {
00103                      rs->sr_err = LDAP_ALIAS_PROBLEM;
00104                      rs->sr_text = "aliasedObject not found";
00105                      break;
00106               }
00107 
00108               /* Free the previous entry, continue to work with the
00109                * one we just retrieved.
00110                */
00111               mdb_entry_return( op, *matched );
00112 
00113               /* We found a regular entry. Return this to the caller.
00114                */
00115               if (!is_entry_alias(e)) {
00116                      rs->sr_err = LDAP_SUCCESS;
00117                      rs->sr_text = NULL;
00118                      break;
00119               }
00120        }
00121        return e;
00122 }
00123 
00124 /* Look for and dereference all aliases within the search scope.
00125  * Requires "stack" to be able to hold 6 levels of DB_SIZE IDLs.
00126  * Of course we're hardcoded to require a minimum of 8 UM_SIZE
00127  * IDLs so this is never a problem.
00128  */
00129 static int search_aliases(
00130        Operation *op,
00131        SlapReply *rs,
00132        Entry *e,
00133        MDB_txn *txn,
00134        MDB_cursor *mci,
00135        ID2L scopes,
00136        ID *stack )
00137 {
00138        ID *aliases, *curscop, *visited, *newsubs, *oldsubs, *tmp;
00139        ID cursora, ida, cursoro, ido;
00140        Entry *matched, *a;
00141        struct berval bv_alias = BER_BVC( "alias" );
00142        AttributeAssertion aa_alias = ATTRIBUTEASSERTION_INIT;
00143        Filter af;
00144        int first = 1;
00145 
00146        aliases = stack;     /* IDL of all aliases in the database */
00147        curscop = aliases + MDB_IDL_DB_SIZE;      /* Aliases in the current scope */
00148        visited = curscop + MDB_IDL_DB_SIZE;      /* IDs we've seen in this search */
00149        newsubs = visited + MDB_IDL_DB_SIZE;      /* New subtrees we've added */
00150        oldsubs = newsubs + MDB_IDL_DB_SIZE;      /* Subtrees added previously */
00151        tmp = oldsubs + MDB_IDL_DB_SIZE;   /* Scratch space for deref_base() */
00152 
00153        af.f_choice = LDAP_FILTER_EQUALITY;
00154        af.f_ava = &aa_alias;
00155        af.f_av_desc = slap_schema.si_ad_objectClass;
00156        af.f_av_value = bv_alias;
00157        af.f_next = NULL;
00158 
00159        /* Find all aliases in database */
00160        MDB_IDL_ZERO( aliases );
00161        rs->sr_err = mdb_filter_candidates( op, txn, &af, aliases,
00162               curscop, visited );
00163        if (rs->sr_err != LDAP_SUCCESS) {
00164               return rs->sr_err;
00165        }
00166        oldsubs[0] = 1;
00167        oldsubs[1] = e->e_id;
00168 
00169        MDB_IDL_ZERO( visited );
00170        MDB_IDL_ZERO( newsubs );
00171 
00172        cursoro = 0;
00173        ido = mdb_idl_first( oldsubs, &cursoro );
00174 
00175        for (;;) {
00176               /* Set curscop to only the aliases in the current scope. Start with
00177                * all the aliases, then get the intersection with the scope.
00178                */
00179               rs->sr_err = mdb_idscope( op, txn, e->e_id, aliases, curscop );
00180 
00181               if (first) {
00182                      first = 0;
00183               } else {
00184                      mdb_entry_return( op, e );
00185               }
00186 
00187               /* Dereference all of the aliases in the current scope. */
00188               cursora = 0;
00189               for (ida = mdb_idl_first(curscop, &cursora); ida != NOID;
00190                      ida = mdb_idl_next(curscop, &cursora))
00191               {
00192                      rs->sr_err = mdb_id2entry(op, mci, ida, &a);
00193                      if (rs->sr_err != LDAP_SUCCESS) {
00194                             continue;
00195                      }
00196 
00197                      /* This should only happen if the curscop IDL has maxed out and
00198                       * turned into a range that spans IDs indiscriminately
00199                       */
00200                      if (!is_entry_alias(a)) {
00201                             mdb_entry_return(op, a);
00202                             continue;
00203                      }
00204 
00205                      /* Actually dereference the alias */
00206                      MDB_IDL_ZERO(tmp);
00207                      a = deref_base( op, rs, a, &matched, txn,
00208                             tmp, visited );
00209                      if (a) {
00210                             /* If the target was not already in our current scopes,
00211                              * make note of it in the newsubs list.
00212                              */
00213                             ID2 mid;
00214                             mid.mid = a->e_id;
00215                             mid.mval.mv_data = NULL;
00216                             if (mdb_id2l_insert(scopes, &mid) == 0) {
00217                                    mdb_idl_insert(newsubs, a->e_id);
00218                             }
00219                             mdb_entry_return( op, a );
00220 
00221                      } else if (matched) {
00222                             /* Alias could not be dereferenced, or it deref'd to
00223                              * an ID we've already seen. Ignore it.
00224                              */
00225                             mdb_entry_return( op, matched );
00226                             rs->sr_text = NULL;
00227                      }
00228               }
00229               /* If this is a OneLevel search, we're done; oldsubs only had one
00230                * ID in it. For a Subtree search, oldsubs may be a list of scope IDs.
00231                */
00232               if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) break;
00233 nextido:
00234               ido = mdb_idl_next( oldsubs, &cursoro );
00235               
00236               /* If we're done processing the old scopes, did we add any new
00237                * scopes in this iteration? If so, go back and do those now.
00238                */
00239               if (ido == NOID) {
00240                      if (MDB_IDL_IS_ZERO(newsubs)) break;
00241                      MDB_IDL_CPY(oldsubs, newsubs);
00242                      MDB_IDL_ZERO(newsubs);
00243                      cursoro = 0;
00244                      ido = mdb_idl_first( oldsubs, &cursoro );
00245               }
00246 
00247               /* Find the entry corresponding to the next scope. If it can't
00248                * be found, ignore it and move on. This should never happen;
00249                * we should never see the ID of an entry that doesn't exist.
00250                */
00251               rs->sr_err = mdb_id2entry(op, mci, ido, &e);
00252               if ( rs->sr_err != LDAP_SUCCESS ) {
00253                      goto nextido;
00254               }
00255        }
00256        return rs->sr_err;
00257 }
00258 
00259 /* Get the next ID from the DB. Used if the candidate list is
00260  * a range and simple iteration hits missing entryIDs
00261  */
00262 static int
00263 mdb_get_nextid(MDB_cursor *mci, ID *cursor)
00264 {
00265        MDB_val key;
00266        ID id;
00267        int rc;
00268 
00269        id = *cursor + 1;
00270        key.mv_data = &id;
00271        key.mv_size = sizeof(ID);
00272        rc = mdb_cursor_get( mci, &key, NULL, MDB_SET_RANGE );
00273        if ( rc )
00274               return rc;
00275        memcpy( cursor, key.mv_data, sizeof(ID));
00276        return 0;
00277 }
00278 
00279 static void scope_chunk_free( void *key, void *data )
00280 {
00281        ID2 *p1, *p2;
00282        for (p1 = data; p1; p1 = p2) {
00283               p2 = p1[0].mval.mv_data;
00284               ber_memfree_x(p1, NULL);
00285        }
00286 }
00287 
00288 static ID2 *scope_chunk_get( Operation *op )
00289 {
00290        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00291        ID2 *ret = NULL;
00292 
00293        ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)scope_chunk_get,
00294                      (void *)&ret, NULL );
00295        if ( !ret ) {
00296               ret = ch_malloc( MDB_IDL_UM_SIZE * sizeof( ID2 ));
00297        } else {
00298               void *r2 = ret[0].mval.mv_data;
00299               ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)scope_chunk_get,
00300                      r2, scope_chunk_free, NULL, NULL );
00301        }
00302        return ret;
00303 }
00304 
00305 static void scope_chunk_ret( Operation *op, ID2 *scopes )
00306 {
00307        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00308        void *ret = NULL;
00309 
00310        ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)scope_chunk_get,
00311                      &ret, NULL );
00312        scopes[0].mval.mv_data = ret;
00313        ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)scope_chunk_get,
00314                      (void *)scopes, scope_chunk_free, NULL, NULL );
00315 }
00316 
00317 int
00318 mdb_search( Operation *op, SlapReply *rs )
00319 {
00320        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00321        ID            id, cursor;
00322        ID            lastid = NOID;
00323        ID            candidates[MDB_IDL_UM_SIZE];
00324        ID2           *scopes;
00325        Entry         *e = NULL, *base = NULL;
00326        Entry         *matched = NULL;
00327        AttributeName *attrs;
00328        slap_mask_t   mask;
00329        time_t        stoptime;
00330        int           manageDSAit;
00331        int           tentries = 0;
00332        IdScopes      isc;
00333        MDB_cursor    *mci;
00334 
00335        mdb_op_info   opinfo = {{{0}}}, *moi = &opinfo;
00336        MDB_txn                     *ltid = NULL;
00337 
00338        Debug( LDAP_DEBUG_TRACE, "=> " LDAP_XSTRING(mdb_search) "\n", 0, 0, 0);
00339        attrs = op->oq_search.rs_attrs;
00340 
00341        manageDSAit = get_manageDSAit( op );
00342 
00343        rs->sr_err = mdb_opinfo_get( op, mdb, 1, &moi );
00344        switch(rs->sr_err) {
00345        case 0:
00346               break;
00347        default:
00348               send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
00349               return rs->sr_err;
00350        }
00351 
00352        ltid = moi->moi_txn;
00353 
00354        rs->sr_err = mdb_cursor_open( ltid, mdb->mi_id2entry, &mci );
00355        if ( rs->sr_err ) {
00356               send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
00357               return rs->sr_err;
00358        }
00359 
00360        scopes = scope_chunk_get( op );
00361        isc.mt = ltid;
00362        isc.mc = NULL;
00363        isc.scopes = scopes;
00364 
00365        if ( op->ors_deref & LDAP_DEREF_FINDING ) {
00366               MDB_IDL_ZERO(candidates);
00367        }
00368 dn2entry_retry:
00369        /* get entry with reader lock */
00370        rs->sr_err = mdb_dn2entry( op, ltid, NULL, &op->o_req_ndn, &e, 1 );
00371 
00372        switch(rs->sr_err) {
00373        case MDB_NOTFOUND:
00374               matched = e;
00375               e = NULL;
00376               break;
00377        case 0:
00378               break;
00379        case LDAP_BUSY:
00380               send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
00381               goto done;
00382        default:
00383               send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
00384               goto done;
00385        }
00386 
00387        if ( op->ors_deref & LDAP_DEREF_FINDING ) {
00388               if ( matched && is_entry_alias( matched )) {
00389                      struct berval stub;
00390 
00391                      stub.bv_val = op->o_req_ndn.bv_val;
00392                      stub.bv_len = op->o_req_ndn.bv_len - matched->e_nname.bv_len - 1;
00393                      e = deref_base( op, rs, matched, &matched, ltid,
00394                             candidates, NULL );
00395                      if ( e ) {
00396                             build_new_dn( &op->o_req_ndn, &e->e_nname, &stub,
00397                                    op->o_tmpmemctx );
00398                             mdb_entry_return(op, e);
00399                             matched = NULL;
00400                             goto dn2entry_retry;
00401                      }
00402               } else if ( e && is_entry_alias( e )) {
00403                      e = deref_base( op, rs, e, &matched, ltid,
00404                             candidates, NULL );
00405               }
00406        }
00407 
00408        if ( e == NULL ) {
00409               struct berval matched_dn = BER_BVNULL;
00410 
00411               if ( matched != NULL ) {
00412                      BerVarray erefs = NULL;
00413 
00414                      /* return referral only if "disclose"
00415                       * is granted on the object */
00416                      if ( ! access_allowed( op, matched,
00417                                           slap_schema.si_ad_entry,
00418                                           NULL, ACL_DISCLOSE, NULL ) )
00419                      {
00420                             rs->sr_err = LDAP_NO_SUCH_OBJECT;
00421 
00422                      } else {
00423                             ber_dupbv( &matched_dn, &matched->e_name );
00424 
00425                             erefs = is_entry_referral( matched )
00426                                    ? get_entry_referrals( op, matched )
00427                                    : NULL;
00428                             if ( rs->sr_err == MDB_NOTFOUND )
00429                                    rs->sr_err = LDAP_REFERRAL;
00430                             rs->sr_matched = matched_dn.bv_val;
00431                      }
00432 
00433                      mdb_entry_return(op, matched);
00434                      matched = NULL;
00435 
00436                      if ( erefs ) {
00437                             rs->sr_ref = referral_rewrite( erefs, &matched_dn,
00438                                    &op->o_req_dn, op->oq_search.rs_scope );
00439                             ber_bvarray_free( erefs );
00440                      }
00441 
00442               } else {
00443                      rs->sr_ref = referral_rewrite( default_referral,
00444                             NULL, &op->o_req_dn, op->oq_search.rs_scope );
00445                      rs->sr_err = rs->sr_ref != NULL ? LDAP_REFERRAL : LDAP_NO_SUCH_OBJECT;
00446               }
00447 
00448               send_ldap_result( op, rs );
00449 
00450               if ( rs->sr_ref ) {
00451                      ber_bvarray_free( rs->sr_ref );
00452                      rs->sr_ref = NULL;
00453               }
00454               if ( !BER_BVISNULL( &matched_dn ) ) {
00455                      ber_memfree( matched_dn.bv_val );
00456                      rs->sr_matched = NULL;
00457               }
00458               goto done;
00459        }
00460 
00461        /* NOTE: __NEW__ "search" access is required
00462         * on searchBase object */
00463        if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry,
00464                             NULL, ACL_SEARCH, NULL, &mask ) )
00465        {
00466               if ( !ACL_GRANT( mask, ACL_DISCLOSE ) ) {
00467                      rs->sr_err = LDAP_NO_SUCH_OBJECT;
00468               } else {
00469                      rs->sr_err = LDAP_INSUFFICIENT_ACCESS;
00470               }
00471 
00472               mdb_entry_return( op,e);
00473               send_ldap_result( op, rs );
00474               goto done;
00475        }
00476 
00477        if ( !manageDSAit && is_entry_referral( e ) ) {
00478               /* entry is a referral */
00479               struct berval matched_dn = BER_BVNULL;
00480               BerVarray erefs = NULL;
00481               
00482               ber_dupbv( &matched_dn, &e->e_name );
00483               erefs = get_entry_referrals( op, e );
00484 
00485               rs->sr_err = LDAP_REFERRAL;
00486 
00487               mdb_entry_return( op, e );
00488               e = NULL;
00489 
00490               if ( erefs ) {
00491                      rs->sr_ref = referral_rewrite( erefs, &matched_dn,
00492                             &op->o_req_dn, op->oq_search.rs_scope );
00493                      ber_bvarray_free( erefs );
00494 
00495                      if ( !rs->sr_ref ) {
00496                             rs->sr_text = "bad_referral object";
00497                      }
00498               }
00499 
00500               Debug( LDAP_DEBUG_TRACE,
00501                      LDAP_XSTRING(mdb_search) ": entry is referral\n",
00502                      0, 0, 0 );
00503 
00504               rs->sr_matched = matched_dn.bv_val;
00505               send_ldap_result( op, rs );
00506 
00507               ber_bvarray_free( rs->sr_ref );
00508               rs->sr_ref = NULL;
00509               ber_memfree( matched_dn.bv_val );
00510               rs->sr_matched = NULL;
00511               goto done;
00512        }
00513 
00514        if ( get_assert( op ) &&
00515               ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE ))
00516        {
00517               rs->sr_err = LDAP_ASSERTION_FAILED;
00518               mdb_entry_return( op,e);
00519               send_ldap_result( op, rs );
00520               goto done;
00521        }
00522 
00523        /* compute it anyway; root does not use it */
00524        stoptime = op->o_time + op->ors_tlimit;
00525 
00526        base = e;
00527 
00528        e = NULL;
00529 
00530        /* select candidates */
00531        if ( op->oq_search.rs_scope == LDAP_SCOPE_BASE ) {
00532               rs->sr_err = base_candidate( op->o_bd, base, candidates );
00533 
00534        } else {
00535               MDB_IDL_ZERO( candidates );
00536               scopes[0].mid = 1;
00537               scopes[1].mid = base->e_id;
00538               scopes[1].mval.mv_data = NULL;
00539               rs->sr_err = search_candidates( op, rs, base,
00540                      ltid, mci, candidates, scopes );
00541        }
00542 
00543        /* start cursor at beginning of candidates.
00544         */
00545        cursor = 0;
00546 
00547        if ( candidates[0] == 0 ) {
00548               Debug( LDAP_DEBUG_TRACE,
00549                      LDAP_XSTRING(mdb_search) ": no candidates\n",
00550                      0, 0, 0 );
00551 
00552               goto nochange;
00553        }
00554 
00555        /* if not root and candidates exceed to-be-checked entries, abort */
00556        if ( op->ors_limit   /* isroot == FALSE */ &&
00557               op->ors_limit->lms_s_unchecked != -1 &&
00558               MDB_IDL_N(candidates) > (unsigned) op->ors_limit->lms_s_unchecked )
00559        {
00560               rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED;
00561               send_ldap_result( op, rs );
00562               rs->sr_err = LDAP_SUCCESS;
00563               goto done;
00564        }
00565 
00566        if ( op->ors_limit == NULL  /* isroot == TRUE */ ||
00567               !op->ors_limit->lms_s_pr_hide )
00568        {
00569               tentries = MDB_IDL_N(candidates);
00570        }
00571 
00572        if ( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ) {
00573               PagedResultsState *ps = op->o_pagedresults_state;
00574               /* deferred cookie parsing */
00575               rs->sr_err = parse_paged_cookie( op, rs );
00576               if ( rs->sr_err != LDAP_SUCCESS ) {
00577                      send_ldap_result( op, rs );
00578                      goto done;
00579               }
00580 
00581               cursor = (ID) ps->ps_cookie;
00582               if ( cursor && ps->ps_size == 0 ) {
00583                      rs->sr_err = LDAP_SUCCESS;
00584                      rs->sr_text = "search abandoned by pagedResult size=0";
00585                      send_ldap_result( op, rs );
00586                      goto done;
00587               }
00588               id = mdb_idl_first( candidates, &cursor );
00589               if ( id == NOID ) {
00590                      Debug( LDAP_DEBUG_TRACE, 
00591                             LDAP_XSTRING(mdb_search)
00592                             ": no paged results candidates\n",
00593                             0, 0, 0 );
00594                      send_paged_response( op, rs, &lastid, 0 );
00595 
00596                      rs->sr_err = LDAP_OTHER;
00597                      goto done;
00598               }
00599               if ( id == (ID)ps->ps_cookie )
00600                      id = mdb_idl_next( candidates, &cursor );
00601               goto loop_begin;
00602        }
00603 
00604        for ( id = mdb_idl_first( candidates, &cursor );
00605                 id != NOID ; id = mdb_idl_next( candidates, &cursor ) )
00606        {
00607               int scopeok;
00608 
00609 loop_begin:
00610 
00611               /* check for abandon */
00612               if ( op->o_abandon ) {
00613                      rs->sr_err = SLAPD_ABANDON;
00614                      send_ldap_result( op, rs );
00615                      goto done;
00616               }
00617 
00618               /* mostly needed by internal searches,
00619                * e.g. related to syncrepl, for whom
00620                * abandon does not get set... */
00621               if ( slapd_shutdown ) {
00622                      rs->sr_err = LDAP_UNAVAILABLE;
00623                      send_ldap_disconnect( op, rs );
00624                      goto done;
00625               }
00626 
00627               /* check time limit */
00628               if ( op->ors_tlimit != SLAP_NO_LIMIT
00629                             && slap_get_time() > stoptime )
00630               {
00631                      rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
00632                      rs->sr_ref = rs->sr_v2ref;
00633                      send_ldap_result( op, rs );
00634                      rs->sr_err = LDAP_SUCCESS;
00635                      goto done;
00636               }
00637 
00638               if ( id == base->e_id ) {
00639                      e = base;
00640               } else {
00641 
00642                      /* get the entry */
00643                      rs->sr_err = mdb_id2entry( op, mci, id, &e );
00644 
00645                      if (rs->sr_err == LDAP_BUSY) {
00646                             rs->sr_text = "ldap server busy";
00647                             send_ldap_result( op, rs );
00648                             goto done;
00649 
00650                      } else if ( rs->sr_err == LDAP_OTHER ) {
00651                             rs->sr_text = "internal error";
00652                             send_ldap_result( op, rs );
00653                             goto done;
00654                      }
00655 
00656                      if ( e == NULL ) {
00657                             if( !MDB_IDL_IS_RANGE(candidates) ) {
00658                                    /* only complain for non-range IDLs */
00659                                    Debug( LDAP_DEBUG_TRACE,
00660                                           LDAP_XSTRING(mdb_search)
00661                                           ": candidate %ld not found\n",
00662                                           (long) id, 0, 0 );
00663                             } else {
00664                                    /* get the next ID from the DB */
00665                                    rs->sr_err = mdb_get_nextid( mci, &cursor );
00666                                    if ( rs->sr_err == MDB_NOTFOUND ) {
00667                                           break;
00668                                    }
00669                                    if ( rs->sr_err ) {
00670                                           rs->sr_err = LDAP_OTHER;
00671                                           rs->sr_text = "internal error in get_nextid";
00672                                           send_ldap_result( op, rs );
00673                                           goto done;
00674                                    }
00675                                    cursor--;
00676                             }
00677 
00678                             goto loop_continue;
00679                      }
00680               }
00681 
00682               if ( is_entry_subentry( e ) ) {
00683                      if( op->oq_search.rs_scope != LDAP_SCOPE_BASE ) {
00684                             if(!get_subentries_visibility( op )) {
00685                                    /* only subentries are visible */
00686                                    goto loop_continue;
00687                             }
00688 
00689                      } else if ( get_subentries( op ) &&
00690                             !get_subentries_visibility( op ))
00691                      {
00692                             /* only subentries are visible */
00693                             goto loop_continue;
00694                      }
00695 
00696               } else if ( get_subentries_visibility( op )) {
00697                      /* only subentries are visible */
00698                      goto loop_continue;
00699               }
00700 
00701               /* Does this candidate actually satisfy the search scope?
00702                */
00703               scopeok = 0;
00704               isc.numrdns = 0;
00705               switch( op->ors_scope ) {
00706               case LDAP_SCOPE_BASE:
00707                      /* This is always true, yes? */
00708                      if ( id == base->e_id ) scopeok = 1;
00709                      break;
00710 
00711 #ifdef LDAP_SCOPE_CHILDREN
00712               case LDAP_SCOPE_CHILDREN:
00713                      if ( id == base->e_id ) break;
00714                      /* Fall-thru */
00715 #endif
00716               case LDAP_SCOPE_SUBTREE:
00717                      if ( id == base->e_id ) {
00718                             scopeok = 1;
00719                             break;
00720                      }
00721                      /* Fall-thru */
00722               case LDAP_SCOPE_ONELEVEL:
00723                      isc.id = id;
00724                      if ( mdb_idscopes( op, &isc ) == MDB_SUCCESS ) scopeok = 1;
00725                      break;
00726               }
00727 
00728               /* aliases were already dereferenced in candidate list */
00729               if ( op->ors_deref & LDAP_DEREF_SEARCHING ) {
00730                      /* but if the search base is an alias, and we didn't
00731                       * deref it when finding, return it.
00732                       */
00733                      if ( is_entry_alias(e) &&
00734                             ((op->ors_deref & LDAP_DEREF_FINDING) ||
00735                                    !bvmatch(&e->e_nname, &op->o_req_ndn)))
00736                      {
00737                             goto loop_continue;
00738                      }
00739               }
00740 
00741               /* Not in scope, ignore it */
00742               if ( !scopeok )
00743               {
00744                      Debug( LDAP_DEBUG_TRACE,
00745                             LDAP_XSTRING(mdb_search)
00746                             ": %ld scope not okay\n",
00747                             (long) id, 0, 0 );
00748                      goto loop_continue;
00749               }
00750 
00751               if ( !manageDSAit && is_entry_glue( e )) {
00752                      goto loop_continue;
00753               }
00754 
00755               if (e != base) {
00756                      struct berval pdn, pndn;
00757                      char *d, *n;
00758                      int i;
00759                      /* child of base, just append RDNs to base->e_name */
00760                      if ( isc.nscope == 1 ) {
00761                             pdn = base->e_name;
00762                             pndn = base->e_nname;
00763                      } else {
00764                             mdb_id2name( op, ltid, &isc.mc, scopes[isc.nscope].mid, &pdn, &pndn );
00765                      }
00766                      e->e_name.bv_len = pdn.bv_len;
00767                      e->e_nname.bv_len = pndn.bv_len;
00768                      for (i=0; i<isc.numrdns; i++) {
00769                             e->e_name.bv_len += isc.rdns[i].bv_len + 1;
00770                             e->e_nname.bv_len += isc.nrdns[i].bv_len + 1;
00771                      }
00772                      e->e_name.bv_val = op->o_tmpalloc(e->e_name.bv_len + 1, op->o_tmpmemctx);
00773                      e->e_nname.bv_val = op->o_tmpalloc(e->e_nname.bv_len + 1, op->o_tmpmemctx);
00774                      d = e->e_name.bv_val;
00775                      n = e->e_nname.bv_val;
00776                      for (i=0; i<isc.numrdns; i++) {
00777                             memcpy(d, isc.rdns[i].bv_val, isc.rdns[i].bv_len);
00778                             d += isc.rdns[i].bv_len;
00779                             *d++ = ',';
00780                             memcpy(n, isc.nrdns[i].bv_val, isc.nrdns[i].bv_len);
00781                             n += isc.nrdns[i].bv_len;
00782                             *n++ = ',';
00783                      }
00784                      if (pdn.bv_len) {
00785                             memcpy(d, pdn.bv_val, pdn.bv_len+1);
00786                             memcpy(n, pndn.bv_val, pndn.bv_len+1);
00787                      } else {
00788                             *--d = '\0';
00789                             *--n = '\0';
00790                             e->e_name.bv_len--;
00791                             e->e_nname.bv_len--;
00792                      }
00793                      if (isc.nscope != 1) {
00794                             op->o_tmpfree(pndn.bv_val, op->o_tmpmemctx);
00795                             op->o_tmpfree(pdn.bv_val, op->o_tmpmemctx);
00796                      }
00797               }
00798 
00799               /*
00800                * if it's a referral, add it to the list of referrals. only do
00801                * this for non-base searches, and don't check the filter
00802                * explicitly here since it's only a candidate anyway.
00803                */
00804               if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE
00805                      && is_entry_referral( e ) )
00806               {
00807                      BerVarray erefs = get_entry_referrals( op, e );
00808                      rs->sr_ref = referral_rewrite( erefs, &e->e_name, NULL,
00809                             op->oq_search.rs_scope == LDAP_SCOPE_ONELEVEL
00810                                    ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE );
00811 
00812                      rs->sr_entry = e;
00813                      rs->sr_flags = 0;
00814 
00815                      send_search_reference( op, rs );
00816 
00817                      mdb_entry_return( op, e );
00818                      rs->sr_entry = NULL;
00819                      e = NULL;
00820 
00821                      ber_bvarray_free( rs->sr_ref );
00822                      ber_bvarray_free( erefs );
00823                      rs->sr_ref = NULL;
00824 
00825                      goto loop_continue;
00826               }
00827 
00828               /* if it matches the filter and scope, send it */
00829               rs->sr_err = test_filter( op, e, op->oq_search.rs_filter );
00830 
00831               if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
00832                      /* check size limit */
00833                      if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
00834                             if ( rs->sr_nentries >= ((PagedResultsState *)op->o_pagedresults_state)->ps_size ) {
00835                                    mdb_entry_return( op, e );
00836                                    e = NULL;
00837                                    send_paged_response( op, rs, &lastid, tentries );
00838                                    goto done;
00839                             }
00840                             lastid = id;
00841                      }
00842 
00843                      if (e) {
00844                             /* safe default */
00845                             rs->sr_attrs = op->oq_search.rs_attrs;
00846                             rs->sr_operational_attrs = NULL;
00847                             rs->sr_ctrls = NULL;
00848                             rs->sr_entry = e;
00849                             RS_ASSERT( e->e_private != NULL );
00850                             rs->sr_flags = 0;
00851                             rs->sr_err = LDAP_SUCCESS;
00852                             rs->sr_err = send_search_entry( op, rs );
00853                             rs->sr_attrs = NULL;
00854                             rs->sr_entry = NULL;
00855                             if (e != base)
00856                                    mdb_entry_return( op, e );
00857                             e = NULL;
00858 
00859                             switch ( rs->sr_err ) {
00860                             case LDAP_SUCCESS:   /* entry sent ok */
00861                                    break;
00862                             default:             /* entry not sent */
00863                                    break;
00864                             case LDAP_UNAVAILABLE:
00865                             case LDAP_SIZELIMIT_EXCEEDED:
00866                                    if ( rs->sr_err == LDAP_SIZELIMIT_EXCEEDED ) {
00867                                           rs->sr_ref = rs->sr_v2ref;
00868                                           send_ldap_result( op, rs );
00869                                           rs->sr_err = LDAP_SUCCESS;
00870 
00871                                    } else {
00872                                           rs->sr_err = LDAP_OTHER;
00873                                    }
00874                                    goto done;
00875                             }
00876                      }
00877 
00878               } else {
00879                      Debug( LDAP_DEBUG_TRACE,
00880                             LDAP_XSTRING(mdb_search)
00881                             ": %ld does not match filter\n",
00882                             (long) id, 0, 0 );
00883               }
00884 
00885 loop_continue:
00886               if( e != NULL ) {
00887                      if ( e != base )
00888                             mdb_entry_return( op, e );
00889                      RS_ASSERT( rs->sr_entry == NULL );
00890                      e = NULL;
00891                      rs->sr_entry = NULL;
00892               }
00893        }
00894 
00895 nochange:
00896        rs->sr_ctrls = NULL;
00897        rs->sr_ref = rs->sr_v2ref;
00898        rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL;
00899        rs->sr_rspoid = NULL;
00900        if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
00901               send_paged_response( op, rs, NULL, 0 );
00902        } else {
00903               send_ldap_result( op, rs );
00904        }
00905 
00906        rs->sr_err = LDAP_SUCCESS;
00907 
00908 done:
00909        if( isc.mc )
00910               mdb_cursor_close( isc.mc );
00911        if (mci)
00912               mdb_cursor_close( mci );
00913        if ( moi == &opinfo ) {
00914               mdb_txn_reset( moi->moi_txn );
00915               LDAP_SLIST_REMOVE( &op->o_extra, &moi->moi_oe, OpExtra, oe_next );
00916        }
00917        if( rs->sr_v2ref ) {
00918               ber_bvarray_free( rs->sr_v2ref );
00919               rs->sr_v2ref = NULL;
00920        }
00921        if (base)
00922               mdb_entry_return( op,base);
00923        scope_chunk_ret( op, scopes );
00924 
00925        return rs->sr_err;
00926 }
00927 
00928 
00929 static int base_candidate(
00930        BackendDB     *be,
00931        Entry  *e,
00932        ID            *ids )
00933 {
00934        Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
00935               e->e_nname.bv_val, (long) e->e_id, 0);
00936 
00937        ids[0] = 1;
00938        ids[1] = e->e_id;
00939        return 0;
00940 }
00941 
00942 /* Look for "objectClass Present" in this filter.
00943  * Also count depth of filter tree while we're at it.
00944  */
00945 static int oc_filter(
00946        Filter *f,
00947        int cur,
00948        int *max )
00949 {
00950        int rc = 0;
00951 
00952        assert( f != NULL );
00953 
00954        if( cur > *max ) *max = cur;
00955 
00956        switch( f->f_choice ) {
00957        case LDAP_FILTER_PRESENT:
00958               if (f->f_desc == slap_schema.si_ad_objectClass) {
00959                      rc = 1;
00960               }
00961               break;
00962 
00963        case LDAP_FILTER_AND:
00964        case LDAP_FILTER_OR:
00965               cur++;
00966               for ( f=f->f_and; f; f=f->f_next ) {
00967                      (void) oc_filter(f, cur, max);
00968               }
00969               break;
00970 
00971        default:
00972               break;
00973        }
00974        return rc;
00975 }
00976 
00977 static void search_stack_free( void *key, void *data )
00978 {
00979        ber_memfree_x(data, NULL);
00980 }
00981 
00982 static void *search_stack( Operation *op )
00983 {
00984        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00985        void *ret = NULL;
00986 
00987        if ( op->o_threadctx ) {
00988               ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack,
00989                      &ret, NULL );
00990        } else {
00991               ret = mdb->mi_search_stack;
00992        }
00993 
00994        if ( !ret ) {
00995               ret = ch_malloc( mdb->mi_search_stack_depth * MDB_IDL_UM_SIZE
00996                      * sizeof( ID ) );
00997               if ( op->o_threadctx ) {
00998                      ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack,
00999                             ret, search_stack_free, NULL, NULL );
01000               } else {
01001                      mdb->mi_search_stack = ret;
01002               }
01003        }
01004        return ret;
01005 }
01006 
01007 static int search_candidates(
01008        Operation *op,
01009        SlapReply *rs,
01010        Entry *e,
01011        MDB_txn *txn,
01012        MDB_cursor *mci,
01013        ID     *ids,
01014        ID2L   scopes )
01015 {
01016        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
01017        int rc, depth = 1;
01018        Filter        *f, rf, xf, nf, sf;
01019        ID            *stack;
01020        AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT;
01021        AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT;
01022 
01023        /*
01024         * This routine takes as input a filter (user-filter)
01025         * and rewrites it as follows:
01026         *     (&(scope=DN)[(objectClass=subentry)]
01027         *            (|[(objectClass=referral)](user-filter))
01028         */
01029 
01030        Debug(LDAP_DEBUG_TRACE,
01031               "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
01032               e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope );
01033 
01034        f = op->oq_search.rs_filter;
01035 
01036        /* If the user's filter uses objectClass=*,
01037         * these clauses are redundant.
01038         */
01039        if (!oc_filter(op->oq_search.rs_filter, 1, &depth)
01040               && !get_subentries_visibility(op)) {
01041               if( !get_manageDSAit(op) && !get_domainScope(op) ) {
01042                      /* match referral objects */
01043                      struct berval bv_ref = BER_BVC( "referral" );
01044                      rf.f_choice = LDAP_FILTER_EQUALITY;
01045                      rf.f_ava = &aa_ref;
01046                      rf.f_av_desc = slap_schema.si_ad_objectClass;
01047                      rf.f_av_value = bv_ref;
01048                      rf.f_next = f;
01049                      xf.f_or = &rf;
01050                      xf.f_choice = LDAP_FILTER_OR;
01051                      xf.f_next = NULL;
01052                      f = &xf;
01053                      depth++;
01054               }
01055        }
01056 
01057        if( get_subentries_visibility( op ) ) {
01058               struct berval bv_subentry = BER_BVC( "subentry" );
01059               sf.f_choice = LDAP_FILTER_EQUALITY;
01060               sf.f_ava = &aa_subentry;
01061               sf.f_av_desc = slap_schema.si_ad_objectClass;
01062               sf.f_av_value = bv_subentry;
01063               sf.f_next = f;
01064               nf.f_choice = LDAP_FILTER_AND;
01065               nf.f_and = &sf;
01066               nf.f_next = NULL;
01067               f = &nf;
01068               depth++;
01069        }
01070 
01071        /* Allocate IDL stack, plus 1 more for former tmp */
01072        if ( depth+1 > mdb->mi_search_stack_depth ) {
01073               stack = ch_malloc( (depth + 1) * MDB_IDL_UM_SIZE * sizeof( ID ) );
01074        } else {
01075               stack = search_stack( op );
01076        }
01077 
01078        if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
01079               rc = search_aliases( op, rs, e, txn, mci, scopes, stack );
01080        } else {
01081               rc = LDAP_SUCCESS;
01082        }
01083 
01084        if ( rc == LDAP_SUCCESS ) {
01085               rc = mdb_filter_candidates( op, txn, f, ids,
01086                      stack, stack+MDB_IDL_UM_SIZE );
01087        }
01088 
01089        if ( depth+1 > mdb->mi_search_stack_depth ) {
01090               ch_free( stack );
01091        }
01092 
01093        if( rc ) {
01094               Debug(LDAP_DEBUG_TRACE,
01095                      "mdb_search_candidates: failed (rc=%d)\n",
01096                      rc, NULL, NULL );
01097 
01098        } else {
01099               Debug(LDAP_DEBUG_TRACE,
01100                      "mdb_search_candidates: id=%ld first=%ld last=%ld\n",
01101                      (long) ids[0],
01102                      (long) MDB_IDL_FIRST(ids),
01103                      (long) MDB_IDL_LAST(ids) );
01104        }
01105 
01106        return rc;
01107 }
01108 
01109 static int
01110 parse_paged_cookie( Operation *op, SlapReply *rs )
01111 {
01112        int           rc = LDAP_SUCCESS;
01113        PagedResultsState *ps = op->o_pagedresults_state;
01114 
01115        /* this function must be invoked only if the pagedResults
01116         * control has been detected, parsed and partially checked
01117         * by the frontend */
01118        assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED );
01119 
01120        /* cookie decoding/checks deferred to backend... */
01121        if ( ps->ps_cookieval.bv_len ) {
01122               PagedResultsCookie reqcookie;
01123               if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) {
01124                      /* bad cookie */
01125                      rs->sr_text = "paged results cookie is invalid";
01126                      rc = LDAP_PROTOCOL_ERROR;
01127                      goto done;
01128               }
01129 
01130               AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie ));
01131 
01132               if ( reqcookie > ps->ps_cookie ) {
01133                      /* bad cookie */
01134                      rs->sr_text = "paged results cookie is invalid";
01135                      rc = LDAP_PROTOCOL_ERROR;
01136                      goto done;
01137 
01138               } else if ( reqcookie < ps->ps_cookie ) {
01139                      rs->sr_text = "paged results cookie is invalid or old";
01140                      rc = LDAP_UNWILLING_TO_PERFORM;
01141                      goto done;
01142               }
01143 
01144        } else {
01145               /* we're going to use ps_cookie */
01146               op->o_conn->c_pagedresults_state.ps_cookie = 0;
01147        }
01148 
01149 done:;
01150 
01151        return rc;
01152 }
01153 
01154 static void
01155 send_paged_response( 
01156        Operation     *op,
01157        SlapReply     *rs,
01158        ID            *lastid,
01159        int           tentries )
01160 {
01161        LDAPControl   *ctrls[2];
01162        BerElementBuffer berbuf;
01163        BerElement    *ber = (BerElement *)&berbuf;
01164        PagedResultsCookie respcookie;
01165        struct berval cookie;
01166 
01167        Debug(LDAP_DEBUG_ARGS,
01168               "send_paged_response: lastid=0x%08lx nentries=%d\n", 
01169               lastid ? *lastid : 0, rs->sr_nentries, NULL );
01170 
01171        ctrls[1] = NULL;
01172 
01173        ber_init2( ber, NULL, LBER_USE_DER );
01174 
01175        if ( lastid ) {
01176               respcookie = ( PagedResultsCookie )(*lastid);
01177               cookie.bv_len = sizeof( respcookie );
01178               cookie.bv_val = (char *)&respcookie;
01179 
01180        } else {
01181               respcookie = ( PagedResultsCookie )0;
01182               BER_BVSTR( &cookie, "" );
01183        }
01184 
01185        op->o_conn->c_pagedresults_state.ps_cookie = respcookie;
01186        op->o_conn->c_pagedresults_state.ps_count =
01187               ((PagedResultsState *)op->o_pagedresults_state)->ps_count +
01188               rs->sr_nentries;
01189 
01190        /* return size of 0 -- no estimate */
01191        ber_printf( ber, "{iO}", 0, &cookie ); 
01192 
01193        ctrls[0] = op->o_tmpalloc( sizeof(LDAPControl), op->o_tmpmemctx );
01194        if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) {
01195               goto done;
01196        }
01197 
01198        ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
01199        ctrls[0]->ldctl_iscritical = 0;
01200 
01201        slap_add_ctrls( op, rs, ctrls );
01202        rs->sr_err = LDAP_SUCCESS;
01203        send_ldap_result( op, rs );
01204 
01205 done:
01206        (void) ber_free_buf( ber );
01207 }