/* $NetBSD: search.c,v 1.1.1.3.6.1 2019/08/10 06:17:18 martin Exp $ */ /* search.c - search operation */ /* $OpenLDAP$ */ /* This work is part of OpenLDAP Software . * * Copyright 2000-2019 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 * . */ #include __RCSID("$NetBSD: search.c,v 1.1.1.3.6.1 2019/08/10 06:17:18 martin Exp $"); #include "portable.h" #include #include #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; } 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; int 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; iscopes[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 ); 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; 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; /* 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; ie_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; ie_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 ); }