summaryrefslogtreecommitdiffstats
path: root/servers/slapd/back-mdb/search.c
diff options
context:
space:
mode:
Diffstat (limited to 'servers/slapd/back-mdb/search.c')
-rw-r--r--servers/slapd/back-mdb/search.c1512
1 files changed, 1512 insertions, 0 deletions
diff --git a/servers/slapd/back-mdb/search.c b/servers/slapd/back-mdb/search.c
new file mode 100644
index 0000000..1bc4ec0
--- /dev/null
+++ b/servers/slapd/back-mdb/search.c
@@ -0,0 +1,1512 @@
+/* search.c - search operation */
+/* $OpenLDAP$ */
+/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
+ *
+ * Copyright 2000-2021 The OpenLDAP Foundation.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted only as authorized by the OpenLDAP
+ * Public License.
+ *
+ * A copy of this license is available in the file LICENSE in the
+ * top-level directory of the distribution or, alternatively, at
+ * <http://www.OpenLDAP.org/license.html>.
+ */
+
+#include "portable.h"
+
+#include <stdio.h>
+#include <ac/string.h>
+
+#include "back-mdb.h"
+#include "idl.h"
+
+static int base_candidate(
+ BackendDB *be,
+ Entry *e,
+ ID *ids );
+
+static int search_candidates(
+ Operation *op,
+ SlapReply *rs,
+ Entry *e,
+ IdScopes *isc,
+ MDB_cursor *mci,
+ ID *ids,
+ ID *stack );
+
+static int parse_paged_cookie( Operation *op, SlapReply *rs );
+
+static void send_paged_response(
+ Operation *op,
+ SlapReply *rs,
+ ID *lastid,
+ int tentries );
+
+/* Dereference aliases for a single alias entry. Return the final
+ * dereferenced entry on success, NULL on any failure.
+ */
+static Entry * deref_base (
+ Operation *op,
+ SlapReply *rs,
+ Entry *e,
+ Entry **matched,
+ MDB_txn *txn,
+ ID *tmp,
+ ID *visited )
+{
+ struct berval ndn;
+
+ rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM;
+ rs->sr_text = "maximum deref depth exceeded";
+
+ for (;;) {
+ /* Remember the last entry we looked at, so we can
+ * report broken links
+ */
+ *matched = e;
+
+ if (MDB_IDL_N(tmp) >= op->o_bd->be_max_deref_depth) {
+ e = NULL;
+ break;
+ }
+
+ /* If this is part of a subtree or onelevel search,
+ * have we seen this ID before? If so, quit.
+ */
+ if ( visited && mdb_idl_insert( visited, e->e_id ) ) {
+ e = NULL;
+ break;
+ }
+
+ /* If we've seen this ID during this deref iteration,
+ * we've hit a loop.
+ */
+ if ( mdb_idl_insert( tmp, e->e_id ) ) {
+ rs->sr_err = LDAP_ALIAS_PROBLEM;
+ rs->sr_text = "circular alias";
+ e = NULL;
+ break;
+ }
+
+ /* If there was a problem getting the aliasedObjectName,
+ * get_alias_dn will have set the error status.
+ */
+ if ( get_alias_dn(e, &ndn, &rs->sr_err, &rs->sr_text) ) {
+ e = NULL;
+ break;
+ }
+
+ rs->sr_err = mdb_dn2entry( op, txn, NULL, &ndn, &e, NULL, 0 );
+ if (rs->sr_err) {
+ rs->sr_err = LDAP_ALIAS_PROBLEM;
+ rs->sr_text = "aliasedObject not found";
+ break;
+ }
+
+ /* Free the previous entry, continue to work with the
+ * one we just retrieved.
+ */
+ mdb_entry_return( op, *matched );
+
+ /* We found a regular entry. Return this to the caller.
+ */
+ if (!is_entry_alias(e)) {
+ rs->sr_err = LDAP_SUCCESS;
+ rs->sr_text = NULL;
+ break;
+ }
+ }
+ return e;
+}
+
+/* Look for and dereference all aliases within the search scope.
+ * Requires "stack" to be able to hold 6 levels of DB_SIZE IDLs.
+ * Of course we're hardcoded to require a minimum of 8 UM_SIZE
+ * IDLs so this is never a problem.
+ */
+static int search_aliases(
+ Operation *op,
+ SlapReply *rs,
+ ID e_id,
+ IdScopes *isc,
+ MDB_cursor *mci,
+ ID *stack )
+{
+ ID *aliases, *curscop, *visited, *newsubs, *oldsubs, *tmp;
+ ID cursora, ida, cursoro, ido;
+ Entry *matched, *a;
+ struct berval bv_alias = BER_BVC( "alias" );
+ AttributeAssertion aa_alias = ATTRIBUTEASSERTION_INIT;
+ Filter af;
+
+ aliases = stack; /* IDL of all aliases in the database */
+ curscop = aliases + MDB_IDL_DB_SIZE; /* Aliases in the current scope */
+ visited = curscop + MDB_IDL_DB_SIZE; /* IDs we've seen in this search */
+ newsubs = visited + MDB_IDL_DB_SIZE; /* New subtrees we've added */
+ oldsubs = newsubs + MDB_IDL_DB_SIZE; /* Subtrees added previously */
+ tmp = oldsubs + MDB_IDL_DB_SIZE; /* Scratch space for deref_base() */
+
+ af.f_choice = LDAP_FILTER_EQUALITY;
+ af.f_ava = &aa_alias;
+ af.f_av_desc = slap_schema.si_ad_objectClass;
+ af.f_av_value = bv_alias;
+ af.f_next = NULL;
+
+ /* Find all aliases in database */
+ MDB_IDL_ZERO( aliases );
+ rs->sr_err = mdb_filter_candidates( op, isc->mt, &af, aliases,
+ curscop, visited );
+ if (rs->sr_err != LDAP_SUCCESS || MDB_IDL_IS_ZERO( aliases )) {
+ return rs->sr_err;
+ }
+ if ( op->ors_limit /* isroot == FALSE */ &&
+ op->ors_limit->lms_s_unchecked != -1 &&
+ MDB_IDL_N( aliases ) > (unsigned) op->ors_limit->lms_s_unchecked )
+ {
+ return LDAP_ADMINLIMIT_EXCEEDED;
+ }
+ oldsubs[0] = 1;
+ oldsubs[1] = e_id;
+
+ MDB_IDL_ZERO( visited );
+ MDB_IDL_ZERO( newsubs );
+
+ cursoro = 0;
+ ido = mdb_idl_first( oldsubs, &cursoro );
+
+ for (;;) {
+ /* Set curscop to only the aliases in the current scope. Start with
+ * all the aliases, then get the intersection with the scope.
+ */
+ rs->sr_err = mdb_idscope( op, isc->mt, e_id, aliases, curscop );
+
+ /* Dereference all of the aliases in the current scope. */
+ cursora = 0;
+ for (ida = mdb_idl_first(curscop, &cursora); ida != NOID;
+ ida = mdb_idl_next(curscop, &cursora))
+ {
+ rs->sr_err = mdb_id2entry(op, mci, ida, &a);
+ if (rs->sr_err != LDAP_SUCCESS) {
+ continue;
+ }
+
+ /* This should only happen if the curscop IDL has maxed out and
+ * turned into a range that spans IDs indiscriminately
+ */
+ if (!is_entry_alias(a)) {
+ mdb_entry_return(op, a);
+ continue;
+ }
+
+ /* Actually dereference the alias */
+ MDB_IDL_ZERO(tmp);
+ a = deref_base( op, rs, a, &matched, isc->mt,
+ tmp, visited );
+ if (a) {
+ /* If the target was not already in our current scopes,
+ * make note of it in the newsubs list.
+ */
+ ID2 mid;
+ mid.mid = a->e_id;
+ mid.mval.mv_data = NULL;
+ if (op->ors_scope == LDAP_SCOPE_SUBTREE) {
+ isc->id = a->e_id;
+ /* if ID is a child of any of our current scopes,
+ * ignore it, it's already included.
+ */
+ if (mdb_idscopechk(op, isc))
+ goto skip;
+ }
+ if (mdb_id2l_insert(isc->scopes, &mid) == 0) {
+ mdb_idl_insert(newsubs, a->e_id);
+ }
+skip: mdb_entry_return( op, a );
+
+ } else if (matched) {
+ /* Alias could not be dereferenced, or it deref'd to
+ * an ID we've already seen. Ignore it.
+ */
+ mdb_entry_return( op, matched );
+ rs->sr_text = NULL;
+ rs->sr_err = 0;
+ }
+ }
+ /* If this is a OneLevel search, we're done; oldsubs only had one
+ * ID in it. For a Subtree search, oldsubs may be a list of scope IDs.
+ */
+ if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) break;
+nextido:
+ ido = mdb_idl_next( oldsubs, &cursoro );
+
+ /* If we're done processing the old scopes, did we add any new
+ * scopes in this iteration? If so, go back and do those now.
+ */
+ if (ido == NOID) {
+ if (MDB_IDL_IS_ZERO(newsubs)) break;
+ MDB_IDL_CPY(oldsubs, newsubs);
+ MDB_IDL_ZERO(newsubs);
+ cursoro = 0;
+ ido = mdb_idl_first( oldsubs, &cursoro );
+ }
+
+ /* Find the entry corresponding to the next scope. If it can't
+ * be found, ignore it and move on. This should never happen;
+ * we should never see the ID of an entry that doesn't exist.
+ */
+ {
+ MDB_val edata;
+ rs->sr_err = mdb_id2edata(op, mci, ido, &edata);
+ if ( rs->sr_err != MDB_SUCCESS ) {
+ goto nextido;
+ }
+ e_id = ido;
+ }
+ }
+ return rs->sr_err;
+}
+
+/* Get the next ID from the DB. Used if the candidate list is
+ * a range and simple iteration hits missing entryIDs
+ */
+static int
+mdb_get_nextid(MDB_cursor *mci, ID *cursor)
+{
+ MDB_val key;
+ ID id;
+ int rc;
+
+ id = *cursor + 1;
+ key.mv_data = &id;
+ key.mv_size = sizeof(ID);
+ rc = mdb_cursor_get( mci, &key, NULL, MDB_SET_RANGE );
+ if ( rc )
+ return rc;
+ memcpy( cursor, key.mv_data, sizeof(ID));
+ return 0;
+}
+
+static void scope_chunk_free( void *key, void *data )
+{
+ ID2 *p1, *p2;
+ for (p1 = data; p1; p1 = p2) {
+ p2 = p1[0].mval.mv_data;
+ ber_memfree_x(p1, NULL);
+ }
+}
+
+static ID2 *scope_chunk_get( Operation *op )
+{
+ ID2 *ret = NULL;
+
+ ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)scope_chunk_get,
+ (void *)&ret, NULL );
+ if ( !ret ) {
+ ret = ch_malloc( MDB_IDL_UM_SIZE * sizeof( ID2 ));
+ } else {
+ void *r2 = ret[0].mval.mv_data;
+ ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)scope_chunk_get,
+ r2, scope_chunk_free, NULL, NULL );
+ }
+ return ret;
+}
+
+static void scope_chunk_ret( Operation *op, ID2 *scopes )
+{
+ void *ret = NULL;
+
+ ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)scope_chunk_get,
+ &ret, NULL );
+ scopes[0].mval.mv_data = ret;
+ ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)scope_chunk_get,
+ (void *)scopes, scope_chunk_free, NULL, NULL );
+}
+
+static void *search_stack( Operation *op );
+
+typedef struct ww_ctx {
+ MDB_txn *txn;
+ MDB_cursor *mcd; /* if set, save cursor context */
+ ID key;
+ MDB_val data;
+ int flag;
+ unsigned nentries;
+} ww_ctx;
+
+/* ITS#7904 if we get blocked while writing results to client,
+ * release the current reader txn and reacquire it after we
+ * unblock.
+ * Slight problem - if we're doing a scope-based walk (mdb_dn2id_walk)
+ * to return results, we need to remember the state of the mcd cursor.
+ * If the node that cursor was pointing to gets deleted while we're
+ * blocked, we may be unable to restore the cursor position. In that
+ * case return an LDAP_BUSY error - let the client know this search
+ * couldn't succeed, but might succeed on a retry.
+ */
+static void
+mdb_rtxn_snap( Operation *op, ww_ctx *ww )
+{
+ /* save cursor position and release read txn */
+ if ( ww->mcd ) {
+ MDB_val key, data;
+ mdb_cursor_get( ww->mcd, &key, &data, MDB_GET_CURRENT );
+ memcpy( &ww->key, key.mv_data, sizeof(ID) );
+ ww->data.mv_size = data.mv_size;
+ ww->data.mv_data = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
+ memcpy(ww->data.mv_data, data.mv_data, data.mv_size);
+ }
+ mdb_txn_reset( ww->txn );
+ ww->flag = 1;
+}
+
+static void
+mdb_writewait( Operation *op, slap_callback *sc )
+{
+ ww_ctx *ww = sc->sc_private;
+ if ( !ww->flag ) {
+ mdb_rtxn_snap( op, ww );
+ }
+}
+
+static int
+mdb_waitfixup( Operation *op, ww_ctx *ww, MDB_cursor *mci, MDB_cursor *mcd, IdScopes *isc )
+{
+ MDB_val key;
+ int rc = 0;
+ ww->flag = 0;
+ mdb_txn_renew( ww->txn );
+ mdb_cursor_renew( ww->txn, mci );
+ mdb_cursor_renew( ww->txn, mcd );
+
+ key.mv_size = sizeof(ID);
+ if ( ww->mcd ) { /* scope-based search using dn2id_walk */
+ MDB_val data;
+
+ if ( isc->numrdns )
+ mdb_dn2id_wrestore( op, isc );
+
+ key.mv_data = &ww->key;
+ data = ww->data;
+ rc = mdb_cursor_get( mcd, &key, &data, MDB_GET_BOTH );
+ if ( rc == MDB_NOTFOUND ) {
+ data = ww->data;
+ rc = mdb_cursor_get( mcd, &key, &data, MDB_GET_BOTH_RANGE );
+ /* the loop will skip this node using NEXT_DUP but we want it
+ * sent, so go back one space first
+ */
+ if ( rc == MDB_SUCCESS )
+ mdb_cursor_get( mcd, &key, &data, MDB_PREV_DUP );
+ else
+ rc = LDAP_BUSY;
+ } else if ( rc ) {
+ rc = LDAP_OTHER;
+ }
+ op->o_tmpfree( ww->data.mv_data, op->o_tmpmemctx );
+ ww->data.mv_data = NULL;
+ } else if ( isc->scopes[0].mid > 1 ) { /* candidate-based search */
+ int i;
+ for ( i=1; i<isc->scopes[0].mid; i++ ) {
+ if ( !isc->scopes[i].mval.mv_data )
+ continue;
+ key.mv_data = &isc->scopes[i].mid;
+ mdb_cursor_get( mcd, &key, &isc->scopes[i].mval, MDB_SET );
+ }
+ }
+ return rc;
+}
+
+int
+mdb_search( Operation *op, SlapReply *rs )
+{
+ struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
+ ID id, cursor, nsubs, ncand, cscope;
+ ID lastid = NOID;
+ ID candidates[MDB_IDL_UM_SIZE];
+ ID iscopes[MDB_IDL_DB_SIZE];
+ ID2 *scopes;
+ void *stack;
+ Entry *e = NULL, *base = NULL;
+ Entry *matched = NULL;
+ AttributeName *attrs;
+ slap_mask_t mask;
+ time_t stoptime;
+ int manageDSAit;
+ int tentries = 0;
+ IdScopes isc;
+ MDB_cursor *mci, *mcd;
+ ww_ctx wwctx;
+ slap_callback cb = { 0 };
+
+ mdb_op_info opinfo = {{{0}}}, *moi = &opinfo;
+ MDB_txn *ltid = NULL;
+
+ Debug( LDAP_DEBUG_TRACE, "=> " LDAP_XSTRING(mdb_search) "\n", 0, 0, 0);
+ attrs = op->oq_search.rs_attrs;
+
+ manageDSAit = get_manageDSAit( op );
+
+ rs->sr_err = mdb_opinfo_get( op, mdb, 1, &moi );
+ switch(rs->sr_err) {
+ case 0:
+ break;
+ default:
+ send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
+ return rs->sr_err;
+ }
+
+ ltid = moi->moi_txn;
+
+ rs->sr_err = mdb_cursor_open( ltid, mdb->mi_id2entry, &mci );
+ if ( rs->sr_err ) {
+ send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
+ return rs->sr_err;
+ }
+
+ rs->sr_err = mdb_cursor_open( ltid, mdb->mi_dn2id, &mcd );
+ if ( rs->sr_err ) {
+ mdb_cursor_close( mci );
+ send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
+ return rs->sr_err;
+ }
+
+ scopes = scope_chunk_get( op );
+ stack = search_stack( op );
+ isc.mt = ltid;
+ isc.mc = mcd;
+ isc.scopes = scopes;
+ isc.oscope = op->ors_scope;
+ isc.sctmp = stack;
+
+ if ( op->ors_deref & LDAP_DEREF_FINDING ) {
+ MDB_IDL_ZERO(candidates);
+ }
+dn2entry_retry:
+ /* get entry with reader lock */
+ rs->sr_err = mdb_dn2entry( op, ltid, mcd, &op->o_req_ndn, &e, &nsubs, 1 );
+
+ switch(rs->sr_err) {
+ case MDB_NOTFOUND:
+ matched = e;
+ e = NULL;
+ break;
+ case 0:
+ break;
+ case LDAP_BUSY:
+ send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
+ goto done;
+ default:
+ send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
+ goto done;
+ }
+
+ if ( op->ors_deref & LDAP_DEREF_FINDING ) {
+ if ( matched && is_entry_alias( matched )) {
+ struct berval stub;
+
+ stub.bv_val = op->o_req_ndn.bv_val;
+ stub.bv_len = op->o_req_ndn.bv_len - matched->e_nname.bv_len - 1;
+ e = deref_base( op, rs, matched, &matched, ltid,
+ candidates, NULL );
+ if ( e ) {
+ build_new_dn( &op->o_req_ndn, &e->e_nname, &stub,
+ op->o_tmpmemctx );
+ mdb_entry_return(op, e);
+ matched = NULL;
+ goto dn2entry_retry;
+ }
+ } else if ( e && is_entry_alias( e )) {
+ e = deref_base( op, rs, e, &matched, ltid,
+ candidates, NULL );
+ }
+ }
+
+ if ( e == NULL ) {
+ struct berval matched_dn = BER_BVNULL;
+
+ if ( matched != NULL ) {
+ BerVarray erefs = NULL;
+
+ /* return referral only if "disclose"
+ * is granted on the object */
+ if ( ! access_allowed( op, matched,
+ slap_schema.si_ad_entry,
+ NULL, ACL_DISCLOSE, NULL ) )
+ {
+ rs->sr_err = LDAP_NO_SUCH_OBJECT;
+
+ } else {
+ ber_dupbv( &matched_dn, &matched->e_name );
+
+ erefs = is_entry_referral( matched )
+ ? get_entry_referrals( op, matched )
+ : NULL;
+ if ( rs->sr_err == MDB_NOTFOUND )
+ rs->sr_err = LDAP_REFERRAL;
+ rs->sr_matched = matched_dn.bv_val;
+ }
+
+ mdb_entry_return(op, matched);
+ matched = NULL;
+
+ if ( erefs ) {
+ rs->sr_ref = referral_rewrite( erefs, &matched_dn,
+ &op->o_req_dn, op->oq_search.rs_scope );
+ ber_bvarray_free( erefs );
+ }
+
+ } else {
+ rs->sr_ref = referral_rewrite( default_referral,
+ NULL, &op->o_req_dn, op->oq_search.rs_scope );
+ rs->sr_err = rs->sr_ref != NULL ? LDAP_REFERRAL : LDAP_NO_SUCH_OBJECT;
+ }
+
+ send_ldap_result( op, rs );
+
+ if ( rs->sr_ref ) {
+ ber_bvarray_free( rs->sr_ref );
+ rs->sr_ref = NULL;
+ }
+ if ( !BER_BVISNULL( &matched_dn ) ) {
+ ber_memfree( matched_dn.bv_val );
+ rs->sr_matched = NULL;
+ }
+ goto done;
+ }
+
+ /* NOTE: __NEW__ "search" access is required
+ * on searchBase object */
+ if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry,
+ NULL, ACL_SEARCH, NULL, &mask ) )
+ {
+ if ( !ACL_GRANT( mask, ACL_DISCLOSE ) ) {
+ rs->sr_err = LDAP_NO_SUCH_OBJECT;
+ } else {
+ rs->sr_err = LDAP_INSUFFICIENT_ACCESS;
+ }
+
+ mdb_entry_return( op,e);
+ send_ldap_result( op, rs );
+ goto done;
+ }
+
+ if ( !manageDSAit && is_entry_referral( e ) ) {
+ /* entry is a referral */
+ struct berval matched_dn = BER_BVNULL;
+ BerVarray erefs = NULL;
+
+ ber_dupbv( &matched_dn, &e->e_name );
+ erefs = get_entry_referrals( op, e );
+
+ rs->sr_err = LDAP_REFERRAL;
+
+ mdb_entry_return( op, e );
+ e = NULL;
+
+ if ( erefs ) {
+ rs->sr_ref = referral_rewrite( erefs, &matched_dn,
+ &op->o_req_dn, op->oq_search.rs_scope );
+ ber_bvarray_free( erefs );
+
+ if ( !rs->sr_ref ) {
+ rs->sr_text = "bad_referral object";
+ }
+ }
+
+ Debug( LDAP_DEBUG_TRACE,
+ LDAP_XSTRING(mdb_search) ": entry is referral\n",
+ 0, 0, 0 );
+
+ rs->sr_matched = matched_dn.bv_val;
+ send_ldap_result( op, rs );
+
+ ber_bvarray_free( rs->sr_ref );
+ rs->sr_ref = NULL;
+ ber_memfree( matched_dn.bv_val );
+ rs->sr_matched = NULL;
+ goto done;
+ }
+
+ if ( get_assert( op ) &&
+ ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE ))
+ {
+ rs->sr_err = LDAP_ASSERTION_FAILED;
+ mdb_entry_return( op,e);
+ send_ldap_result( op, rs );
+ goto done;
+ }
+
+ /* compute it anyway; root does not use it */
+ stoptime = op->o_time + op->ors_tlimit;
+
+ base = e;
+
+ e = NULL;
+
+ /* select candidates */
+ if ( op->oq_search.rs_scope == LDAP_SCOPE_BASE ) {
+ rs->sr_err = base_candidate( op->o_bd, base, candidates );
+ scopes[0].mid = 0;
+ ncand = 1;
+ } else {
+ if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
+ size_t nkids;
+ MDB_val key, data;
+ key.mv_data = &base->e_id;
+ key.mv_size = sizeof( ID );
+ mdb_cursor_get( mcd, &key, &data, MDB_SET );
+ mdb_cursor_count( mcd, &nkids );
+ nsubs = nkids - 1;
+ } else if ( !base->e_id ) {
+ /* we don't maintain nsubs for entryID 0.
+ * just grab entry count from id2entry stat
+ */
+ MDB_stat ms;
+ mdb_stat( ltid, mdb->mi_id2entry, &ms );
+ nsubs = ms.ms_entries;
+ }
+ MDB_IDL_ZERO( candidates );
+ scopes[0].mid = 1;
+ scopes[1].mid = base->e_id;
+ scopes[1].mval.mv_data = NULL;
+ rs->sr_err = search_candidates( op, rs, base,
+ &isc, mci, candidates, stack );
+
+ if ( rs->sr_err == LDAP_ADMINLIMIT_EXCEEDED )
+ goto adminlimit;
+
+ ncand = MDB_IDL_N( candidates );
+ if ( !base->e_id || ncand == NOID ) {
+ /* grab entry count from id2entry stat
+ */
+ MDB_stat ms;
+ mdb_stat( ltid, mdb->mi_id2entry, &ms );
+ if ( !base->e_id )
+ nsubs = ms.ms_entries;
+ if ( ncand == NOID )
+ ncand = ms.ms_entries;
+ }
+ }
+
+ /* start cursor at beginning of candidates.
+ */
+ cursor = 0;
+
+ if ( candidates[0] == 0 ) {
+ Debug( LDAP_DEBUG_TRACE,
+ LDAP_XSTRING(mdb_search) ": no candidates\n",
+ 0, 0, 0 );
+
+ goto nochange;
+ }
+
+ /* if not root and candidates exceed to-be-checked entries, abort */
+ if ( op->ors_limit /* isroot == FALSE */ &&
+ op->ors_limit->lms_s_unchecked != -1 &&
+ ncand > (unsigned) op->ors_limit->lms_s_unchecked )
+ {
+ rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED;
+adminlimit:
+ send_ldap_result( op, rs );
+ rs->sr_err = LDAP_SUCCESS;
+ goto done;
+ }
+
+ if ( op->ors_limit == NULL /* isroot == TRUE */ ||
+ !op->ors_limit->lms_s_pr_hide )
+ {
+ tentries = ncand;
+ }
+
+ wwctx.flag = 0;
+ wwctx.nentries = 0;
+ /* If we're running in our own read txn */
+ if ( moi == &opinfo ) {
+ cb.sc_writewait = mdb_writewait;
+ cb.sc_private = &wwctx;
+ wwctx.txn = ltid;
+ wwctx.mcd = NULL;
+ cb.sc_next = op->o_callback;
+ op->o_callback = &cb;
+ }
+
+ if ( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ) {
+ PagedResultsState *ps = op->o_pagedresults_state;
+ /* deferred cookie parsing */
+ rs->sr_err = parse_paged_cookie( op, rs );
+ if ( rs->sr_err != LDAP_SUCCESS ) {
+ send_ldap_result( op, rs );
+ goto done;
+ }
+
+ cursor = (ID) ps->ps_cookie;
+ if ( cursor && ps->ps_size == 0 ) {
+ rs->sr_err = LDAP_SUCCESS;
+ rs->sr_text = "search abandoned by pagedResult size=0";
+ send_ldap_result( op, rs );
+ goto done;
+ }
+ id = mdb_idl_first( candidates, &cursor );
+ if ( id == NOID ) {
+ Debug( LDAP_DEBUG_TRACE,
+ LDAP_XSTRING(mdb_search)
+ ": no paged results candidates\n",
+ 0, 0, 0 );
+ send_paged_response( op, rs, &lastid, 0 );
+
+ rs->sr_err = LDAP_OTHER;
+ goto done;
+ }
+ if ( id == (ID)ps->ps_cookie )
+ id = mdb_idl_next( candidates, &cursor );
+ nsubs = ncand; /* always bypass scope'd search */
+ goto loop_begin;
+ }
+ if ( nsubs < ncand ) {
+ int rc;
+ /* Do scope-based search */
+
+ /* if any alias scopes were set, save them */
+ if (scopes[0].mid > 1) {
+ cursor = 1;
+ for (cscope = 1; cscope <= scopes[0].mid; cscope++) {
+ /* Ignore the original base */
+ if (scopes[cscope].mid == base->e_id)
+ continue;
+ iscopes[cursor++] = scopes[cscope].mid;
+ }
+ iscopes[0] = scopes[0].mid - 1;
+ } else {
+ iscopes[0] = 0;
+ }
+
+ wwctx.mcd = mcd;
+ isc.id = base->e_id;
+ isc.numrdns = 0;
+ rc = mdb_dn2id_walk( op, &isc );
+ if ( rc )
+ id = NOID;
+ else
+ id = isc.id;
+ cscope = 0;
+ } else {
+ id = mdb_idl_first( candidates, &cursor );
+ }
+
+ while (id != NOID)
+ {
+ int scopeok;
+ MDB_val edata;
+
+loop_begin:
+
+ /* check for abandon */
+ if ( op->o_abandon ) {
+ rs->sr_err = SLAPD_ABANDON;
+ send_ldap_result( op, rs );
+ goto done;
+ }
+
+ /* mostly needed by internal searches,
+ * e.g. related to syncrepl, for whom
+ * abandon does not get set... */
+ if ( slapd_shutdown ) {
+ rs->sr_err = LDAP_UNAVAILABLE;
+ send_ldap_disconnect( op, rs );
+ goto done;
+ }
+
+ /* check time limit */
+ if ( op->ors_tlimit != SLAP_NO_LIMIT
+ && slap_get_time() > stoptime )
+ {
+ rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
+ rs->sr_ref = rs->sr_v2ref;
+ send_ldap_result( op, rs );
+ rs->sr_err = LDAP_SUCCESS;
+ goto done;
+ }
+
+
+ if ( nsubs < ncand ) {
+ unsigned i;
+ /* Is this entry in the candidate list? */
+ scopeok = 0;
+ if (MDB_IDL_IS_RANGE( candidates )) {
+ if ( id >= MDB_IDL_RANGE_FIRST( candidates ) &&
+ id <= MDB_IDL_RANGE_LAST( candidates ))
+ scopeok = 1;
+ } else {
+ i = mdb_idl_search( candidates, id );
+ if (i <= candidates[0] && candidates[i] == id )
+ scopeok = 1;
+ }
+ if ( scopeok )
+ goto scopeok;
+ goto loop_continue;
+ }
+
+ /* Does this candidate actually satisfy the search scope?
+ */
+ scopeok = 0;
+ isc.numrdns = 0;
+ switch( op->ors_scope ) {
+ case LDAP_SCOPE_BASE:
+ /* This is always true, yes? */
+ if ( id == base->e_id ) scopeok = 1;
+ break;
+
+#ifdef LDAP_SCOPE_CHILDREN
+ case LDAP_SCOPE_CHILDREN:
+ if ( id == base->e_id ) break;
+ /* Fall-thru */
+#endif
+ case LDAP_SCOPE_SUBTREE:
+ if ( id == base->e_id ) {
+ scopeok = 1;
+ break;
+ }
+ /* Fall-thru */
+ case LDAP_SCOPE_ONELEVEL:
+ if ( id == base->e_id ) break;
+ isc.id = id;
+ isc.nscope = 0;
+ rs->sr_err = mdb_idscopes( op, &isc );
+ if ( rs->sr_err == MDB_SUCCESS ) {
+ if ( isc.nscope )
+ scopeok = 1;
+ } else {
+ if ( rs->sr_err == MDB_NOTFOUND )
+ goto notfound;
+ }
+ break;
+ }
+
+ /* Not in scope, ignore it */
+ if ( !scopeok )
+ {
+ Debug( LDAP_DEBUG_TRACE,
+ LDAP_XSTRING(mdb_search)
+ ": %ld scope not okay\n",
+ (long) id, 0, 0 );
+ goto loop_continue;
+ }
+
+scopeok:
+ if ( id == base->e_id ) {
+ e = base;
+ } else {
+
+ /* get the entry */
+ rs->sr_err = mdb_id2edata( op, mci, id, &edata );
+ if ( rs->sr_err == MDB_NOTFOUND ) {
+notfound:
+ if( nsubs < ncand )
+ goto loop_continue;
+
+ if( !MDB_IDL_IS_RANGE(candidates) ) {
+ /* only complain for non-range IDLs */
+ Debug( LDAP_DEBUG_TRACE,
+ LDAP_XSTRING(mdb_search)
+ ": candidate %ld not found\n",
+ (long) id, 0, 0 );
+ } else {
+ /* get the next ID from the DB */
+ rs->sr_err = mdb_get_nextid( mci, &cursor );
+ if ( rs->sr_err == MDB_NOTFOUND ) {
+ break;
+ }
+ if ( rs->sr_err ) {
+ rs->sr_err = LDAP_OTHER;
+ rs->sr_text = "internal error in get_nextid";
+ send_ldap_result( op, rs );
+ goto done;
+ }
+ cursor--;
+ }
+
+ goto loop_continue;
+ } else if ( rs->sr_err ) {
+ rs->sr_err = LDAP_OTHER;
+ rs->sr_text = "internal error in mdb_id2edata";
+ send_ldap_result( op, rs );
+ goto done;
+ }
+
+ rs->sr_err = mdb_entry_decode( op, ltid, &edata, &e );
+ if ( rs->sr_err ) {
+ rs->sr_err = LDAP_OTHER;
+ rs->sr_text = "internal error in mdb_entry_decode";
+ send_ldap_result( op, rs );
+ goto done;
+ }
+ e->e_id = id;
+ e->e_name.bv_val = NULL;
+ e->e_nname.bv_val = NULL;
+ }
+
+ if ( is_entry_subentry( e ) ) {
+ if( op->oq_search.rs_scope != LDAP_SCOPE_BASE ) {
+ if(!get_subentries_visibility( op )) {
+ /* only subentries are visible */
+ goto loop_continue;
+ }
+
+ } else if ( get_subentries( op ) &&
+ !get_subentries_visibility( op ))
+ {
+ /* only subentries are visible */
+ goto loop_continue;
+ }
+
+ } else if ( get_subentries_visibility( op )) {
+ /* only subentries are visible */
+ goto loop_continue;
+ }
+
+ /* aliases were already dereferenced in candidate list */
+ if ( op->ors_deref & LDAP_DEREF_SEARCHING ) {
+ /* but if the search base is an alias, and we didn't
+ * deref it when finding, return it.
+ */
+ if ( is_entry_alias(e) &&
+ ((op->ors_deref & LDAP_DEREF_FINDING) || e != base ))
+ {
+ goto loop_continue;
+ }
+ }
+
+ if ( !manageDSAit && is_entry_glue( e )) {
+ goto loop_continue;
+ }
+
+ if (e != base) {
+ struct berval pdn, pndn;
+ char *d, *n;
+ int i;
+
+ /* child of base, just append RDNs to base->e_name */
+ if ( nsubs < ncand || isc.scopes[isc.nscope].mid == base->e_id ) {
+ pdn = base->e_name;
+ pndn = base->e_nname;
+ } else {
+ mdb_id2name( op, ltid, &isc.mc, scopes[isc.nscope].mid, &pdn, &pndn );
+ }
+ e->e_name.bv_len = pdn.bv_len;
+ e->e_nname.bv_len = pndn.bv_len;
+ for (i=0; i<isc.numrdns; i++) {
+ e->e_name.bv_len += isc.rdns[i].bv_len + 1;
+ e->e_nname.bv_len += isc.nrdns[i].bv_len + 1;
+ }
+ e->e_name.bv_val = op->o_tmpalloc(e->e_name.bv_len + 1, op->o_tmpmemctx);
+ e->e_nname.bv_val = op->o_tmpalloc(e->e_nname.bv_len + 1, op->o_tmpmemctx);
+ d = e->e_name.bv_val;
+ n = e->e_nname.bv_val;
+ if (nsubs < ncand) {
+ /* RDNs are in top-down order */
+ for (i=isc.numrdns-1; i>=0; i--) {
+ memcpy(d, isc.rdns[i].bv_val, isc.rdns[i].bv_len);
+ d += isc.rdns[i].bv_len;
+ *d++ = ',';
+ memcpy(n, isc.nrdns[i].bv_val, isc.nrdns[i].bv_len);
+ n += isc.nrdns[i].bv_len;
+ *n++ = ',';
+ }
+ } else {
+ /* RDNs are in bottom-up order */
+ for (i=0; i<isc.numrdns; i++) {
+ memcpy(d, isc.rdns[i].bv_val, isc.rdns[i].bv_len);
+ d += isc.rdns[i].bv_len;
+ *d++ = ',';
+ memcpy(n, isc.nrdns[i].bv_val, isc.nrdns[i].bv_len);
+ n += isc.nrdns[i].bv_len;
+ *n++ = ',';
+ }
+ }
+
+ if (pdn.bv_len) {
+ memcpy(d, pdn.bv_val, pdn.bv_len+1);
+ memcpy(n, pndn.bv_val, pndn.bv_len+1);
+ } else {
+ *--d = '\0';
+ *--n = '\0';
+ e->e_name.bv_len--;
+ e->e_nname.bv_len--;
+ }
+ if (pndn.bv_val != base->e_nname.bv_val) {
+ op->o_tmpfree(pndn.bv_val, op->o_tmpmemctx);
+ op->o_tmpfree(pdn.bv_val, op->o_tmpmemctx);
+ }
+ }
+
+ /*
+ * if it's a referral, add it to the list of referrals. only do
+ * this for non-base searches, and don't check the filter
+ * explicitly here since it's only a candidate anyway.
+ */
+ if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE
+ && is_entry_referral( e ) )
+ {
+ BerVarray erefs = get_entry_referrals( op, e );
+ rs->sr_ref = referral_rewrite( erefs, &e->e_name, NULL,
+ op->oq_search.rs_scope == LDAP_SCOPE_ONELEVEL
+ ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE );
+
+ rs->sr_entry = e;
+ rs->sr_flags = 0;
+
+ send_search_reference( op, rs );
+
+ if (e != base)
+ mdb_entry_return( op, e );
+ rs->sr_entry = NULL;
+ e = NULL;
+
+ ber_bvarray_free( rs->sr_ref );
+ ber_bvarray_free( erefs );
+ rs->sr_ref = NULL;
+
+ goto loop_continue;
+ }
+
+ /* if it matches the filter and scope, send it */
+ rs->sr_err = test_filter( op, e, op->oq_search.rs_filter );
+
+ if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
+ /* check size limit */
+ if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
+ if ( rs->sr_nentries >= ((PagedResultsState *)op->o_pagedresults_state)->ps_size ) {
+ if (e != base)
+ mdb_entry_return( op, e );
+ e = NULL;
+ send_paged_response( op, rs, &lastid, tentries );
+ goto done;
+ }
+ lastid = id;
+ }
+
+ if (e) {
+ /* safe default */
+ rs->sr_attrs = op->oq_search.rs_attrs;
+ rs->sr_operational_attrs = NULL;
+ rs->sr_ctrls = NULL;
+ rs->sr_entry = e;
+ RS_ASSERT( e->e_private != NULL );
+ rs->sr_flags = 0;
+ rs->sr_err = LDAP_SUCCESS;
+ rs->sr_err = send_search_entry( op, rs );
+ rs->sr_attrs = NULL;
+ rs->sr_entry = NULL;
+ if (e != base)
+ mdb_entry_return( op, e );
+ e = NULL;
+
+ switch ( rs->sr_err ) {
+ case LDAP_SUCCESS: /* entry sent ok */
+ break;
+ default: /* entry not sent */
+ break;
+ case LDAP_BUSY:
+ send_ldap_result( op, rs );
+ goto done;
+ case LDAP_UNAVAILABLE:
+ case LDAP_SIZELIMIT_EXCEEDED:
+ if ( rs->sr_err == LDAP_SIZELIMIT_EXCEEDED ) {
+ rs->sr_ref = rs->sr_v2ref;
+ send_ldap_result( op, rs );
+ rs->sr_err = LDAP_SUCCESS;
+
+ } else {
+ rs->sr_err = LDAP_OTHER;
+ }
+ goto done;
+ }
+ }
+
+ } else {
+ Debug( LDAP_DEBUG_TRACE,
+ LDAP_XSTRING(mdb_search)
+ ": %ld does not match filter\n",
+ (long) id, 0, 0 );
+ }
+
+loop_continue:
+ if ( moi == &opinfo && !wwctx.flag && mdb->mi_rtxn_size ) {
+ wwctx.nentries++;
+ if ( wwctx.nentries >= mdb->mi_rtxn_size ) {
+ MDB_envinfo ei;
+ wwctx.nentries = 0;
+ mdb_env_info(mdb->mi_dbenv, &ei);
+ if ( ei.me_last_txnid > mdb_txn_id( ltid ))
+ mdb_rtxn_snap( op, &wwctx );
+ }
+ }
+ if ( wwctx.flag ) {
+ rs->sr_err = mdb_waitfixup( op, &wwctx, mci, mcd, &isc );
+ if ( rs->sr_err ) {
+ send_ldap_result( op, rs );
+ goto done;
+ }
+ }
+
+ if( e != NULL ) {
+ if ( e != base )
+ mdb_entry_return( op, e );
+ RS_ASSERT( rs->sr_entry == NULL );
+ e = NULL;
+ rs->sr_entry = NULL;
+ }
+
+ if ( nsubs < ncand ) {
+ int rc = mdb_dn2id_walk( op, &isc );
+ if (rc) {
+ id = NOID;
+ /* We got to the end of a subtree. If there are any
+ * alias scopes left, search them too.
+ */
+ while (iscopes[0] && cscope < iscopes[0]) {
+ cscope++;
+ isc.id = iscopes[cscope];
+ if ( base )
+ mdb_entry_return( op, base );
+ rs->sr_err = mdb_id2entry(op, mci, isc.id, &base);
+ if ( !rs->sr_err ) {
+ mdb_id2name( op, ltid, &isc.mc, isc.id, &base->e_name, &base->e_nname );
+ isc.numrdns = 0;
+ if (isc.oscope == LDAP_SCOPE_ONELEVEL)
+ isc.oscope = LDAP_SCOPE_BASE;
+ rc = mdb_dn2id_walk( op, &isc );
+ if ( !rc ) {
+ id = isc.id;
+ break;
+ }
+ }
+ }
+ } else
+ id = isc.id;
+ } else {
+ id = mdb_idl_next( candidates, &cursor );
+ }
+ }
+
+nochange:
+ rs->sr_ctrls = NULL;
+ rs->sr_ref = rs->sr_v2ref;
+ rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL;
+ rs->sr_rspoid = NULL;
+ if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
+ send_paged_response( op, rs, NULL, 0 );
+ } else {
+ send_ldap_result( op, rs );
+ }
+
+ rs->sr_err = LDAP_SUCCESS;
+
+done:
+ if ( cb.sc_private ) {
+ /* remove our writewait callback */
+ slap_callback **scp = &op->o_callback;
+ while ( *scp ) {
+ if ( *scp == &cb ) {
+ *scp = cb.sc_next;
+ cb.sc_private = NULL;
+ break;
+ }
+ }
+ }
+ mdb_cursor_close( mcd );
+ mdb_cursor_close( mci );
+ if ( moi == &opinfo ) {
+ mdb_txn_reset( moi->moi_txn );
+ LDAP_SLIST_REMOVE( &op->o_extra, &moi->moi_oe, OpExtra, oe_next );
+ } else {
+ moi->moi_ref--;
+ }
+ if( rs->sr_v2ref ) {
+ ber_bvarray_free( rs->sr_v2ref );
+ rs->sr_v2ref = NULL;
+ }
+ if (base)
+ mdb_entry_return( op, base );
+ scope_chunk_ret( op, scopes );
+
+ return rs->sr_err;
+}
+
+
+static int base_candidate(
+ BackendDB *be,
+ Entry *e,
+ ID *ids )
+{
+ Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
+ e->e_nname.bv_val, (long) e->e_id, 0);
+
+ ids[0] = 1;
+ ids[1] = e->e_id;
+ return 0;
+}
+
+/* Look for "objectClass Present" in this filter.
+ * Also count depth of filter tree while we're at it.
+ */
+static int oc_filter(
+ Filter *f,
+ int cur,
+ int *max )
+{
+ int rc = 0;
+
+ assert( f != NULL );
+
+ if( cur > *max ) *max = cur;
+
+ switch( f->f_choice ) {
+ case LDAP_FILTER_PRESENT:
+ if (f->f_desc == slap_schema.si_ad_objectClass) {
+ rc = 1;
+ }
+ break;
+
+ case LDAP_FILTER_AND:
+ case LDAP_FILTER_OR:
+ cur++;
+ for ( f=f->f_and; f; f=f->f_next ) {
+ (void) oc_filter(f, cur, max);
+ }
+ break;
+
+ default:
+ break;
+ }
+ return rc;
+}
+
+static void search_stack_free( void *key, void *data )
+{
+ ber_memfree_x(data, NULL);
+}
+
+static void *search_stack( Operation *op )
+{
+ struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
+ void *ret = NULL;
+
+ if ( op->o_threadctx ) {
+ ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack,
+ &ret, NULL );
+ } else {
+ ret = mdb->mi_search_stack;
+ }
+
+ if ( !ret ) {
+ ret = ch_malloc( mdb->mi_search_stack_depth * MDB_IDL_UM_SIZE
+ * sizeof( ID ) );
+ if ( op->o_threadctx ) {
+ ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack,
+ ret, search_stack_free, NULL, NULL );
+ } else {
+ mdb->mi_search_stack = ret;
+ }
+ }
+ return ret;
+}
+
+static int search_candidates(
+ Operation *op,
+ SlapReply *rs,
+ Entry *e,
+ IdScopes *isc,
+ MDB_cursor *mci,
+ ID *ids,
+ ID *stack )
+{
+ struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
+ int rc, depth = 1;
+ Filter *f, rf, xf, nf, sf;
+ AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT;
+ AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT;
+
+ /*
+ * This routine takes as input a filter (user-filter)
+ * and rewrites it as follows:
+ * (&(scope=DN)[(objectClass=subentry)]
+ * (|[(objectClass=referral)](user-filter))
+ */
+
+ Debug(LDAP_DEBUG_TRACE,
+ "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
+ e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope );
+
+ f = op->oq_search.rs_filter;
+
+ /* If the user's filter uses objectClass=*,
+ * these clauses are redundant.
+ */
+ if (!oc_filter(op->oq_search.rs_filter, 1, &depth)
+ && !get_subentries_visibility(op)) {
+ if( !get_manageDSAit(op) && !get_domainScope(op) ) {
+ /* match referral objects */
+ struct berval bv_ref = BER_BVC( "referral" );
+ rf.f_choice = LDAP_FILTER_EQUALITY;
+ rf.f_ava = &aa_ref;
+ rf.f_av_desc = slap_schema.si_ad_objectClass;
+ rf.f_av_value = bv_ref;
+ rf.f_next = f;
+ xf.f_or = &rf;
+ xf.f_choice = LDAP_FILTER_OR;
+ xf.f_next = NULL;
+ f = &xf;
+ depth++;
+ }
+ }
+
+ if( get_subentries_visibility( op ) ) {
+ struct berval bv_subentry = BER_BVC( "subentry" );
+ sf.f_choice = LDAP_FILTER_EQUALITY;
+ sf.f_ava = &aa_subentry;
+ sf.f_av_desc = slap_schema.si_ad_objectClass;
+ sf.f_av_value = bv_subentry;
+ sf.f_next = f;
+ nf.f_choice = LDAP_FILTER_AND;
+ nf.f_and = &sf;
+ nf.f_next = NULL;
+ f = &nf;
+ depth++;
+ }
+
+ /* Allocate IDL stack, plus 1 more for former tmp */
+ if ( depth+1 > mdb->mi_search_stack_depth ) {
+ stack = ch_malloc( (depth + 1) * MDB_IDL_UM_SIZE * sizeof( ID ) );
+ }
+
+ if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
+ rc = search_aliases( op, rs, e->e_id, isc, mci, stack );
+ } else {
+ rc = LDAP_SUCCESS;
+ }
+
+ if ( rc == LDAP_SUCCESS ) {
+ rc = mdb_filter_candidates( op, isc->mt, f, ids,
+ stack, stack+MDB_IDL_UM_SIZE );
+ }
+
+ if ( depth+1 > mdb->mi_search_stack_depth ) {
+ ch_free( stack );
+ }
+
+ if( rc ) {
+ Debug(LDAP_DEBUG_TRACE,
+ "mdb_search_candidates: failed (rc=%d)\n",
+ rc, NULL, NULL );
+
+ } else {
+ Debug(LDAP_DEBUG_TRACE,
+ "mdb_search_candidates: id=%ld first=%ld last=%ld\n",
+ (long) ids[0],
+ (long) MDB_IDL_FIRST(ids),
+ (long) MDB_IDL_LAST(ids) );
+ }
+
+ return rc;
+}
+
+static int
+parse_paged_cookie( Operation *op, SlapReply *rs )
+{
+ int rc = LDAP_SUCCESS;
+ PagedResultsState *ps = op->o_pagedresults_state;
+
+ /* this function must be invoked only if the pagedResults
+ * control has been detected, parsed and partially checked
+ * by the frontend */
+ assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED );
+
+ /* cookie decoding/checks deferred to backend... */
+ if ( ps->ps_cookieval.bv_len ) {
+ PagedResultsCookie reqcookie;
+ if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) {
+ /* bad cookie */
+ rs->sr_text = "paged results cookie is invalid";
+ rc = LDAP_PROTOCOL_ERROR;
+ goto done;
+ }
+
+ AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie ));
+
+ if ( reqcookie > ps->ps_cookie ) {
+ /* bad cookie */
+ rs->sr_text = "paged results cookie is invalid";
+ rc = LDAP_PROTOCOL_ERROR;
+ goto done;
+
+ } else if ( reqcookie < ps->ps_cookie ) {
+ rs->sr_text = "paged results cookie is invalid or old";
+ rc = LDAP_UNWILLING_TO_PERFORM;
+ goto done;
+ }
+
+ } else {
+ /* we're going to use ps_cookie */
+ op->o_conn->c_pagedresults_state.ps_cookie = 0;
+ }
+
+done:;
+
+ return rc;
+}
+
+static void
+send_paged_response(
+ Operation *op,
+ SlapReply *rs,
+ ID *lastid,
+ int tentries )
+{
+ LDAPControl *ctrls[2];
+ BerElementBuffer berbuf;
+ BerElement *ber = (BerElement *)&berbuf;
+ PagedResultsCookie respcookie;
+ struct berval cookie;
+
+ Debug(LDAP_DEBUG_ARGS,
+ "send_paged_response: lastid=0x%08lx nentries=%d\n",
+ lastid ? *lastid : 0, rs->sr_nentries, NULL );
+
+ ctrls[1] = NULL;
+
+ ber_init2( ber, NULL, LBER_USE_DER );
+
+ if ( lastid ) {
+ respcookie = ( PagedResultsCookie )(*lastid);
+ cookie.bv_len = sizeof( respcookie );
+ cookie.bv_val = (char *)&respcookie;
+
+ } else {
+ respcookie = ( PagedResultsCookie )0;
+ BER_BVSTR( &cookie, "" );
+ }
+
+ op->o_conn->c_pagedresults_state.ps_cookie = respcookie;
+ op->o_conn->c_pagedresults_state.ps_count =
+ ((PagedResultsState *)op->o_pagedresults_state)->ps_count +
+ rs->sr_nentries;
+
+ /* return size of 0 -- no estimate */
+ ber_printf( ber, "{iO}", 0, &cookie );
+
+ ctrls[0] = op->o_tmpalloc( sizeof(LDAPControl), op->o_tmpmemctx );
+ if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) {
+ goto done;
+ }
+
+ ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
+ ctrls[0]->ldctl_iscritical = 0;
+
+ slap_add_ctrls( op, rs, ctrls );
+ rs->sr_err = LDAP_SUCCESS;
+ send_ldap_result( op, rs );
+
+done:
+ (void) ber_free_buf( ber );
+}