diff options
Diffstat (limited to '')
| -rw-r--r-- | servers/slapd/back-mdb/search.c | 1512 |
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 ); +} |