X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=servers%2Fslapd%2Fback-bdb%2Fsearch.c;h=1d7e52fb4e7c1ede5488dfc0e45bab873dd74936;hb=34adb8692935262a09e21c62d9bcd0284a272b0c;hp=c770f8112b2c79cae5abfd5983f31cbfbaa31243;hpb=583242c9a37b8732ba695d347f4c6ef14e737ffe;p=openldap

diff --git a/servers/slapd/back-bdb/search.c b/servers/slapd/back-bdb/search.c
index c770f8112b..1d7e52fb4e 100644
--- a/servers/slapd/back-bdb/search.c
+++ b/servers/slapd/back-bdb/search.c
@@ -2,7 +2,7 @@
 /* $OpenLDAP$ */
 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
  *
- * Copyright 2000-2005 The OpenLDAP Foundation.
+ * Copyright 2000-2011 The OpenLDAP Foundation.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -31,7 +31,7 @@ static int search_candidates(
 	Operation *op,
 	SlapReply *rs,
 	Entry *e,
-	u_int32_t locker,
+	DB_TXN *txn,
 	ID	*ids,
 	ID	*scopes );
 
@@ -43,9 +43,6 @@ static void send_paged_response(
 	ID  *lastid,
 	int tentries );
 
-static int bdb_pfid_cmp( const void *v_id1, const void *v_id2 );
-static ID* bdb_id_dup( Operation *op, ID *id );
-
 /* Dereference aliases for a single alias entry. Return the final
  * dereferenced entry on success, NULL on any failure.
  */
@@ -54,7 +51,7 @@ static Entry * deref_base (
 	SlapReply *rs,
 	Entry *e,
 	Entry **matched,
-	u_int32_t locker,
+	DB_TXN *txn,
 	DB_LOCK *lock,
 	ID	*tmp,
 	ID	*visited )
@@ -67,12 +64,17 @@ static Entry * deref_base (
 	rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM;
 	rs->sr_text = "maximum deref depth exceeded";
 
-	while (BDB_IDL_N(tmp) < op->o_bd->be_max_deref_depth) {
+	for (;;) {
 		/* Remember the last entry we looked at, so we can
 		 * report broken links
 		 */
 		*matched = e;
 
+		if (BDB_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.
 		 */
@@ -99,8 +101,10 @@ static Entry * deref_base (
 			break;
 		}
 
-		rs->sr_err = bdb_dn2entry( op, NULL, &ndn, &ei,
-			0, locker, &lockr );
+		rs->sr_err = bdb_dn2entry( op, txn, &ndn, &ei,
+			0, &lockr );
+		if ( rs->sr_err == DB_LOCK_DEADLOCK )
+			return NULL;
 
 		if ( ei ) {
 			e = ei->bei_e;
@@ -117,8 +121,7 @@ static Entry * deref_base (
 		/* Free the previous entry, continue to work with the
 		 * one we just retrieved.
 		 */
-		bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache,
-			*matched, lock);
+		bdb_cache_return_entry_r( bdb, *matched, lock);
 		*lock = lockr;
 
 		/* We found a regular entry. Return this to the caller. The
@@ -142,7 +145,7 @@ static int search_aliases(
 	Operation *op,
 	SlapReply *rs,
 	Entry *e,
-	u_int32_t locker,
+	DB_TXN *txn,
 	ID *ids,
 	ID *scopes,
 	ID *stack )
@@ -153,7 +156,7 @@ static int search_aliases(
 	Entry *matched, *a;
 	EntryInfo *ei;
 	struct berval bv_alias = BER_BVC( "alias" );
-	AttributeAssertion aa_alias = { NULL, BER_BVNULL, NULL };
+	AttributeAssertion aa_alias = ATTRIBUTEASSERTION_INIT;
 	Filter	af;
 	DB_LOCK locka, lockr;
 	int first = 1;
@@ -179,7 +182,7 @@ static int search_aliases(
 
 	/* Find all aliases in database */
 	BDB_IDL_ZERO( aliases );
-	rs->sr_err = bdb_filter_candidates( op, &af, aliases,
+	rs->sr_err = bdb_filter_candidates( op, txn, &af, aliases,
 		curscop, visited );
 	if (rs->sr_err != LDAP_SUCCESS) {
 		return rs->sr_err;
@@ -201,13 +204,17 @@ static int search_aliases(
 		 * to the cumulative list of candidates.
 		 */
 		BDB_IDL_CPY( curscop, aliases );
-		rs->sr_err = bdb_dn2idl( op, e, subscop,
+		rs->sr_err = bdb_dn2idl( op, txn, &e->e_nname, BEI(e), subscop,
 			subscop2+BDB_IDL_DB_SIZE );
+
 		if (first) {
 			first = 0;
 		} else {
-			bdb_cache_return_entry_r (bdb->bi_dbenv, &bdb->bi_cache, e, &locka);
+			bdb_cache_return_entry_r (bdb, e, &locka);
 		}
+		if ( rs->sr_err == DB_LOCK_DEADLOCK )
+			return rs->sr_err;
+
 		BDB_IDL_CPY(subscop2, subscop);
 		rs->sr_err = bdb_idl_intersection(curscop, subscop);
 		bdb_idl_union( ids, subscop2 );
@@ -219,11 +226,13 @@ static int search_aliases(
 		{
 			ei = NULL;
 retry1:
-			rs->sr_err = bdb_cache_find_id(op, NULL,
-				ida, &ei, 0, locker, &lockr );
+			rs->sr_err = bdb_cache_find_id(op, txn,
+				ida, &ei, 0, &lockr );
 			if (rs->sr_err != LDAP_SUCCESS) {
-				if ( rs->sr_err == DB_LOCK_DEADLOCK ||
-					rs->sr_err == DB_LOCK_NOTGRANTED ) goto retry1;
+				if ( rs->sr_err == DB_LOCK_DEADLOCK )
+					return rs->sr_err;
+				if ( rs->sr_err == DB_LOCK_NOTGRANTED )
+					goto retry1;
 				continue;
 			}
 			a = ei->bei_e;
@@ -232,14 +241,13 @@ retry1:
 			 * turned into a range that spans IDs indiscriminately
 			 */
 			if (!is_entry_alias(a)) {
-				bdb_cache_return_entry_r (bdb->bi_dbenv, &bdb->bi_cache,
-					a, &lockr);
+				bdb_cache_return_entry_r (bdb, a, &lockr);
 				continue;
 			}
 
 			/* Actually dereference the alias */
 			BDB_IDL_ZERO(tmp);
-			a = deref_base( op, rs, a, &matched, locker, &lockr,
+			a = deref_base( op, rs, a, &matched, txn, &lockr,
 				tmp, visited );
 			if (a) {
 				/* If the target was not already in our current candidates,
@@ -251,15 +259,15 @@ retry1:
 					bdb_idl_insert(newsubs, a->e_id);
 					bdb_idl_insert(scopes, a->e_id);
 				}
-				bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache,
-					a, &lockr);
+				bdb_cache_return_entry_r( bdb, a, &lockr);
 
+			} else if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
+				return rs->sr_err;
 			} else if (matched) {
 				/* Alias could not be dereferenced, or it deref'd to
 				 * an ID we've already seen. Ignore it.
 				 */
-				bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache,
-					matched, &lockr );
+				bdb_cache_return_entry_r( bdb, matched, &lockr );
 				rs->sr_text = NULL;
 			}
 		}
@@ -288,11 +296,12 @@ nextido:
 		 */
 		ei = NULL;
 sameido:
-		rs->sr_err = bdb_cache_find_id(op, NULL, ido, &ei,
-			0, locker, &locka );
+		rs->sr_err = bdb_cache_find_id(op, txn, ido, &ei,
+			0, &locka );
 		if ( rs->sr_err != LDAP_SUCCESS ) {
-			if ( rs->sr_err == DB_LOCK_DEADLOCK ||
-				rs->sr_err == DB_LOCK_NOTGRANTED )
+			if ( rs->sr_err == DB_LOCK_DEADLOCK )
+				return rs->sr_err;
+			if ( rs->sr_err == DB_LOCK_NOTGRANTED )
 				goto sameido;
 			goto nextido;
 		}
@@ -301,41 +310,76 @@ sameido:
 	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
+bdb_get_nextid(struct bdb_info *bdb, DB_TXN *ltid, ID *cursor)
+{
+	DBC *curs;
+	DBT key, data;
+	ID id, nid;
+	int rc;
+
+	id = *cursor + 1;
+	BDB_ID2DISK( id, &nid );
+	rc = bdb->bi_id2entry->bdi_db->cursor(
+		bdb->bi_id2entry->bdi_db, ltid, &curs, bdb->bi_db_opflags );
+	if ( rc )
+		return rc;
+	key.data = &nid;
+	key.size = key.ulen = sizeof(ID);
+	key.flags = DB_DBT_USERMEM;
+	data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
+	data.dlen = data.ulen = 0;
+	rc = curs->c_get( curs, &key, &data, DB_SET_RANGE );
+	curs->c_close( curs );
+	if ( rc )
+		return rc;
+	BDB_DISK2ID( &nid, cursor );
+	return 0;
+}
+
 int
 bdb_search( Operation *op, SlapReply *rs )
 {
 	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
-	time_t		stoptime;
 	ID		id, cursor;
+	ID		lastid = NOID;
 	ID		candidates[BDB_IDL_UM_SIZE];
 	ID		scopes[BDB_IDL_DB_SIZE];
-	Entry		*e = NULL, base, e_root = {0};
+	Entry		*e = NULL, base, *e_root;
 	Entry		*matched = NULL;
-	EntryInfo	*ei, ei_root = {0};
+	EntryInfo	*ei;
+	AttributeName	*attrs;
 	struct berval	realbase = BER_BVNULL;
 	slap_mask_t	mask;
+	time_t		stoptime;
 	int		manageDSAit;
 	int		tentries = 0;
-	ID		lastid = NOID;
-	AttributeName	*attrs;
+	unsigned	nentries = 0;
+	int		idflag = 0;
 
-	u_int32_t	locker = 0;
 	DB_LOCK		lock;
 	struct	bdb_op_info	*opinfo = NULL;
 	DB_TXN			*ltid = NULL;
+	OpExtra *oex;
 
 	Debug( LDAP_DEBUG_TRACE, "=> " LDAP_XSTRING(bdb_search) "\n", 0, 0, 0);
 	attrs = op->oq_search.rs_attrs;
 
-	opinfo = (struct bdb_op_info *) op->o_private;
+	LDAP_SLIST_FOREACH( oex, &op->o_extra, oe_next ) {
+		if ( oex->oe_key == bdb )
+			break;
+	}
+	opinfo = (struct bdb_op_info *) oex;
 
 	manageDSAit = get_manageDSAit( op );
 
 	if ( opinfo && opinfo->boi_txn ) {
 		ltid = opinfo->boi_txn;
-		locker = TXN_ID( ltid );
 	} else {
-		rs->sr_err = LOCK_ID( bdb->bi_dbenv, &locker );
+		rs->sr_err = bdb_reader_get( op, bdb->bi_dbenv, &ltid );
 
 		switch(rs->sr_err) {
 		case 0:
@@ -346,21 +390,19 @@ bdb_search( Operation *op, SlapReply *rs )
 		}
 	}
 
+	e_root = bdb->bi_cache.c_dntree.bei_e;
 	if ( op->o_req_ndn.bv_len == 0 ) {
 		/* DIT root special case */
-		ei_root.bei_e = &e_root;
-		ei_root.bei_parent = &ei_root;
-		e_root.e_private = &ei_root;
-		e_root.e_id = 0;
-		BER_BVSTR( &e_root.e_nname, "" );
-		BER_BVSTR( &e_root.e_name, "" );
-		ei = &ei_root;
+		ei = e_root->e_private;
 		rs->sr_err = LDAP_SUCCESS;
 	} else {
+		if ( op->ors_deref & LDAP_DEREF_FINDING ) {
+			BDB_IDL_ZERO(candidates);
+		}
 dn2entry_retry:
 		/* get entry with reader lock */
 		rs->sr_err = bdb_dn2entry( op, ltid, &op->o_req_ndn, &ei,
-			1, locker, &lock );
+			1, &lock );
 	}
 
 	switch(rs->sr_err) {
@@ -370,25 +412,42 @@ dn2entry_retry:
 	case 0:
 		e = ei->bei_e;
 		break;
+	case DB_LOCK_DEADLOCK:
+		if ( !opinfo ) {
+			ltid->flags &= ~TXN_DEADLOCK;
+			goto dn2entry_retry;
+		}
+		opinfo->boi_err = rs->sr_err;
+		/* FALLTHRU */
 	case LDAP_BUSY:
 		send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
-		if ( !opinfo )
-			LOCK_ID_FREE (bdb->bi_dbenv, locker );
 		return LDAP_BUSY;
-	case DB_LOCK_DEADLOCK:
 	case DB_LOCK_NOTGRANTED:
 		goto dn2entry_retry;
 	default:
 		send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
-		if ( !opinfo )
-			LOCK_ID_FREE (bdb->bi_dbenv, locker );
 		return rs->sr_err;
 	}
 
-	if ( e && (op->ors_deref & LDAP_DEREF_FINDING) && is_entry_alias(e) ) {
-		BDB_IDL_ZERO(candidates);
-		e = deref_base( op, rs, e, &matched, locker, &lock,
-			candidates, NULL );
+	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, &lock,
+				candidates, NULL );
+			if ( e ) {
+				build_new_dn( &op->o_req_ndn, &e->e_nname, &stub,
+					op->o_tmpmemctx );
+				bdb_cache_return_entry_r (bdb, e, &lock);
+				matched = NULL;
+				goto dn2entry_retry;
+			}
+		} else if ( e && is_entry_alias( e )) {
+			e = deref_base( op, rs, e, &matched, ltid, &lock,
+				candidates, NULL );
+		}
 	}
 
 	if ( e == NULL ) {
@@ -397,7 +456,6 @@ dn2entry_retry:
 		if ( matched != NULL ) {
 			BerVarray erefs = NULL;
 
-#ifdef SLAP_ACL_HONOR_DISCLOSE
 			/* return referral only if "disclose"
 			 * is granted on the object */
 			if ( ! access_allowed( op, matched,
@@ -406,23 +464,21 @@ dn2entry_retry:
 			{
 				rs->sr_err = LDAP_NO_SUCH_OBJECT;
 
-			} else
-#endif /* SLAP_ACL_HONOR_DISCLOSE */
-			{
+			} else {
 				ber_dupbv( &matched_dn, &matched->e_name );
 
 				erefs = is_entry_referral( matched )
 					? get_entry_referrals( op, matched )
 					: NULL;
-				rs->sr_err = LDAP_REFERRAL;
+				if ( rs->sr_err == DB_NOTFOUND )
+					rs->sr_err = LDAP_REFERRAL;
 				rs->sr_matched = matched_dn.bv_val;
 			}
 
 #ifdef SLAP_ZONE_ALLOC
 			slap_zn_runlock(bdb->bi_cache.c_zctx, matched);
 #endif
-			bdb_cache_return_entry_r (bdb->bi_dbenv, &bdb->bi_cache,
-				matched, &lock);
+			bdb_cache_return_entry_r (bdb, matched, &lock);
 			matched = NULL;
 
 			if ( erefs ) {
@@ -437,13 +493,11 @@ dn2entry_retry:
 #endif
 			rs->sr_ref = referral_rewrite( default_referral,
 				NULL, &op->o_req_dn, op->oq_search.rs_scope );
-			rs->sr_err = LDAP_REFERRAL;
+			rs->sr_err = rs->sr_ref != NULL ? LDAP_REFERRAL : LDAP_NO_SUCH_OBJECT;
 		}
 
 		send_ldap_result( op, rs );
 
-		if ( !opinfo )
-			LOCK_ID_FREE (bdb->bi_dbenv, locker );
 		if ( rs->sr_ref ) {
 			ber_bvarray_free( rs->sr_ref );
 			rs->sr_ref = NULL;
@@ -455,7 +509,6 @@ dn2entry_retry:
 		return rs->sr_err;
 	}
 
-#ifdef SLAP_ACL_HONOR_DISCLOSE
 	/* NOTE: __NEW__ "search" access is required
 	 * on searchBase object */
 	if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry,
@@ -470,15 +523,14 @@ dn2entry_retry:
 #ifdef SLAP_ZONE_ALLOC
 		slap_zn_runlock(bdb->bi_cache.c_zctx, e);
 #endif
-		if ( e != &e_root ) {
-			bdb_cache_return_entry_r(bdb->bi_dbenv, &bdb->bi_cache, e, &lock);
+		if ( e != e_root ) {
+			bdb_cache_return_entry_r(bdb, e, &lock);
 		}
 		send_ldap_result( op, rs );
-		return 1;
+		return rs->sr_err;
 	}
-#endif /* SLAP_ACL_HONOR_DISCLOSE */
 
-	if ( !manageDSAit && e != &e_root && is_entry_referral( e ) ) {
+	if ( !manageDSAit && e != e_root && is_entry_referral( e ) ) {
 		/* entry is a referral, don't allow add */
 		struct berval matched_dn = BER_BVNULL;
 		BerVarray erefs = NULL;
@@ -491,7 +543,7 @@ dn2entry_retry:
 #ifdef SLAP_ZONE_ALLOC
 		slap_zn_runlock(bdb->bi_cache.c_zctx, e);
 #endif
-		bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache, e, &lock );
+		bdb_cache_return_entry_r( bdb, e, &lock );
 		e = NULL;
 
 		if ( erefs ) {
@@ -511,9 +563,6 @@ dn2entry_retry:
 		rs->sr_matched = matched_dn.bv_val;
 		send_ldap_result( op, rs );
 
-		if ( !opinfo ) {
-			LOCK_ID_FREE (bdb->bi_dbenv, locker );
-		}
 		ber_bvarray_free( rs->sr_ref );
 		rs->sr_ref = NULL;
 		ber_memfree( matched_dn.bv_val );
@@ -528,8 +577,8 @@ dn2entry_retry:
 #ifdef SLAP_ZONE_ALLOC
 		slap_zn_runlock(bdb->bi_cache.c_zctx, e);
 #endif
-		if ( e != &e_root ) {
-			bdb_cache_return_entry_r(bdb->bi_dbenv, &bdb->bi_cache, e, &lock);
+		if ( e != e_root ) {
+			bdb_cache_return_entry_r(bdb, e, &lock);
 		}
 		send_ldap_result( op, rs );
 		return 1;
@@ -551,8 +600,8 @@ dn2entry_retry:
 #ifdef SLAP_ZONE_ALLOC
 	slap_zn_runlock(bdb->bi_cache.c_zctx, e);
 #endif
-	if ( e != &e_root ) {
-		bdb_cache_return_entry_r(bdb->bi_dbenv, &bdb->bi_cache, e, &lock);
+	if ( e != e_root ) {
+		bdb_cache_return_entry_r(bdb, e, &lock);
 	}
 	e = NULL;
 
@@ -561,10 +610,20 @@ dn2entry_retry:
 		rs->sr_err = base_candidate( op->o_bd, &base, candidates );
 
 	} else {
+cand_retry:
 		BDB_IDL_ZERO( candidates );
 		BDB_IDL_ZERO( scopes );
 		rs->sr_err = search_candidates( op, rs, &base,
-			locker, candidates, scopes );
+			ltid, candidates, scopes );
+		if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
+			if ( !opinfo ) {
+				ltid->flags &= ~TXN_DEADLOCK;
+				goto cand_retry;
+			}
+			opinfo->boi_err = rs->sr_err;
+			send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
+			return LDAP_BUSY;
+		}
 	}
 
 	/* start cursor at beginning of candidates.
@@ -605,26 +664,15 @@ dn2entry_retry:
 			goto done;
 		}
 
-		if ( (ID)( ps->ps_cookie ) == 0 ) {
-			id = bdb_idl_first( candidates, &cursor );
-
-		} else {
-			if ( 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;
-			}
-			for ( id = bdb_idl_first( candidates, &cursor );
-				id != NOID &&
-					id <= (ID)( ps->ps_cookie );
-				id = bdb_idl_next( candidates, &cursor ) )
-			{
-				/* empty */;
-			}
+		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;
 		}
-
-		if ( cursor == NOID ) {
+		id = bdb_idl_first( candidates, &cursor );
+		if ( id == NOID ) {
 			Debug( LDAP_DEBUG_TRACE, 
 				LDAP_XSTRING(bdb_search)
 				": no paged results candidates\n",
@@ -634,22 +682,32 @@ dn2entry_retry:
 			rs->sr_err = LDAP_OTHER;
 			goto done;
 		}
+		nentries = ps->ps_count;
+		if ( id == (ID)ps->ps_cookie )
+			id = bdb_idl_next( candidates, &cursor );
 		goto loop_begin;
 	}
 
-loop_start:
-
 	for ( id = bdb_idl_first( candidates, &cursor );
 		  id != NOID ; id = bdb_idl_next( candidates, &cursor ) )
 	{
-		int scopeok = 0;
-		ID* idhole = NULL;
+		int scopeok;
 
 loop_begin:
 
 		/* check for abandon */
 		if ( op->o_abandon ) {
-			rs->sr_err = LDAP_SUCCESS;
+			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;
 		}
 
@@ -664,65 +722,102 @@ loop_begin:
 			goto done;
 		}
 
+		/* If we inspect more entries than will
+		 * fit into the entry cache, stop caching
+		 * any subsequent entries
+		 */
+		nentries++;
+		if ( nentries > bdb->bi_cache.c_maxsize && !idflag ) {
+			idflag = ID_NOCACHE;
+		}
+
 fetch_entry_retry:
-			/* get the entry with reader lock */
-			ei = NULL;
-			rs->sr_err = bdb_cache_find_id( op, ltid,
-				id, &ei, 0, locker, &lock );
+		/* get the entry with reader lock */
+		ei = NULL;
+		rs->sr_err = bdb_cache_find_id( op, ltid,
+			id, &ei, idflag, &lock );
 
-			if (rs->sr_err == LDAP_BUSY) {
-				rs->sr_text = "ldap server busy";
-				send_ldap_result( op, rs );
-				goto done;
+		if (rs->sr_err == LDAP_BUSY) {
+			rs->sr_text = "ldap server busy";
+			send_ldap_result( op, rs );
+			goto done;
 
-			} else if ( rs->sr_err == DB_LOCK_DEADLOCK
-				|| rs->sr_err == DB_LOCK_NOTGRANTED )
-			{
+		} else if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
+			if ( !opinfo ) {
+				ltid->flags &= ~TXN_DEADLOCK;
 				goto fetch_entry_retry;
 			}
+txnfail:
+			opinfo->boi_err = rs->sr_err;
+			send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
+			goto done;
 
-			if ( ei && rs->sr_err == LDAP_SUCCESS ) {
-				e = ei->bei_e;
-			} else {
-				e = NULL;
-			}
+		} else if ( rs->sr_err == DB_LOCK_NOTGRANTED )
+		{
+			goto fetch_entry_retry;
+		} else if ( rs->sr_err == LDAP_OTHER ) {
+			rs->sr_text = "internal error";
+			send_ldap_result( op, rs );
+			goto done;
+		}
 
-			if ( e == NULL ) {
-				if( !BDB_IDL_IS_RANGE(candidates) ) {
-					/* only complain for non-range IDLs */
-					Debug( LDAP_DEBUG_TRACE,
-						LDAP_XSTRING(bdb_search)
-						": candidate %ld not found\n",
-						(long) id, 0, 0 );
-				}
+		if ( ei && rs->sr_err == LDAP_SUCCESS ) {
+			e = ei->bei_e;
+		} else {
+			e = NULL;
+		}
 
-				goto loop_continue;
+		if ( e == NULL ) {
+			if( !BDB_IDL_IS_RANGE(candidates) ) {
+				/* only complain for non-range IDLs */
+				Debug( LDAP_DEBUG_TRACE,
+					LDAP_XSTRING(bdb_search)
+					": candidate %ld not found\n",
+					(long) id, 0, 0 );
+			} else {
+				/* get the next ID from the DB */
+id_retry:
+				rs->sr_err = bdb_get_nextid( bdb, ltid, &cursor );
+				if ( rs->sr_err == DB_NOTFOUND ) {
+					break;
+				} else if ( rs->sr_err == DB_LOCK_DEADLOCK ) {
+					if ( opinfo )
+						goto txnfail;
+					ltid->flags &= ~TXN_DEADLOCK;
+					goto id_retry;
+				} else if ( rs->sr_err == DB_LOCK_NOTGRANTED ) {
+					goto id_retry;
+				}
+				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--;
 			}
 
-		rs->sr_entry = e;
-
-#ifdef BDB_SUBENTRIES
-		{
-			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;
-					}
+			goto loop_continue;
+		}
 
-				} else if ( get_subentries( op ) &&
-					!get_subentries_visibility( op ))
-				{
+		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_visibility( op )) {
+			} 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;
 		}
-#endif /* BDB_SUBENTRIES */
 
 		/* Does this candidate actually satisfy the search scope?
 		 *
@@ -733,6 +828,7 @@ fetch_entry_retry:
 		 * scope while we are looking at it, and unless we're using
 		 * BDB_HIER, its parents cannot be moved either.
 		 */
+		scopeok = 0;
 		switch( op->ors_scope ) {
 		case LDAP_SCOPE_BASE:
 			/* This is always true, yes? */
@@ -809,13 +905,52 @@ fetch_entry_retry:
 		if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE
 			&& is_entry_referral( e ) )
 		{
+			struct bdb_op_info bois;
+			struct bdb_lock_info blis;
 			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 );
 
+			/* Must set lockinfo so that entry_release will work */
+			if (!opinfo) {
+				bois.boi_oe.oe_key = bdb;
+				bois.boi_txn = NULL;
+				bois.boi_err = 0;
+				bois.boi_acl_cache = op->o_do_not_cache;
+				bois.boi_flag = BOI_DONTFREE;
+				bois.boi_locks = &blis;
+				blis.bli_next = NULL;
+				LDAP_SLIST_INSERT_HEAD( &op->o_extra, &bois.boi_oe,
+					oe_next );
+			} else {
+				blis.bli_next = opinfo->boi_locks;
+				opinfo->boi_locks = &blis;
+			}
+			blis.bli_id = e->e_id;
+			blis.bli_lock = lock;
+			blis.bli_flag = BLI_DONTFREE;
+
+			rs->sr_entry = e;
+			rs->sr_flags = REP_ENTRY_MUSTRELEASE;
+
 			send_search_reference( op, rs );
 
+			if ( blis.bli_flag ) {
+#ifdef SLAP_ZONE_ALLOC
+				slap_zn_runlock(bdb->bi_cache.c_zctx, e);
+#endif
+				bdb_cache_return_entry_r(bdb, e, &lock);
+				if ( opinfo ) {
+					opinfo->boi_locks = blis.bli_next;
+				} else {
+					LDAP_SLIST_REMOVE( &op->o_extra, &bois.boi_oe,
+						OpExtra, oe_next );
+				}
+			}
+			rs->sr_entry = NULL;
+			e = NULL;
+
 			ber_bvarray_free( rs->sr_ref );
 			ber_bvarray_free( erefs );
 			rs->sr_ref = NULL;
@@ -828,27 +963,17 @@ fetch_entry_retry:
 		}
 
 		/* if it matches the filter and scope, send it */
-		rs->sr_err = test_filter( op, rs->sr_entry, op->oq_search.rs_filter );
+		rs->sr_err = test_filter( op, e, op->oq_search.rs_filter );
 
 		if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
 			/* check size limit */
-			if ( --op->ors_slimit == -1) {
-#ifdef SLAP_ZONE_ALLOC
-				slap_zn_runlock(bdb->bi_cache.c_zctx, e);
-#endif
-				bdb_cache_return_entry_r( bdb->bi_dbenv,
-						&bdb->bi_cache, e, &lock );
-				e = NULL;
-				rs->sr_entry = NULL;
-				rs->sr_err = LDAP_SIZELIMIT_EXCEEDED;
-				rs->sr_ref = rs->sr_v2ref;
-				send_ldap_result( op, rs );
-				rs->sr_err = LDAP_SUCCESS;
-				goto done;
-			}
-
 			if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
 				if ( rs->sr_nentries >= ((PagedResultsState *)op->o_pagedresults_state)->ps_size ) {
+#ifdef SLAP_ZONE_ALLOC
+					slap_zn_runlock(bdb->bi_cache.c_zctx, e);
+#endif
+					bdb_cache_return_entry_r( bdb, e, &lock );
+					e = NULL;
 					send_paged_response( op, rs, &lastid, tentries );
 					goto done;
 				}
@@ -856,29 +981,73 @@ fetch_entry_retry:
 			}
 
 			if (e) {
+				struct bdb_op_info bois;
+				struct bdb_lock_info blis;
+
+				/* Must set lockinfo so that entry_release will work */
+				if (!opinfo) {
+					bois.boi_oe.oe_key = bdb;
+					bois.boi_txn = NULL;
+					bois.boi_err = 0;
+					bois.boi_acl_cache = op->o_do_not_cache;
+					bois.boi_flag = BOI_DONTFREE;
+					bois.boi_locks = &blis;
+					blis.bli_next = NULL;
+					LDAP_SLIST_INSERT_HEAD( &op->o_extra, &bois.boi_oe,
+						oe_next );
+				} else {
+					blis.bli_next = opinfo->boi_locks;
+					opinfo->boi_locks = &blis;
+				}
+				blis.bli_id = e->e_id;
+				blis.bli_lock = lock;
+				blis.bli_flag = BLI_DONTFREE;
+
 				/* safe default */
-				int result = -1;
 				rs->sr_attrs = op->oq_search.rs_attrs;
 				rs->sr_operational_attrs = NULL;
 				rs->sr_ctrls = NULL;
-				rs->sr_flags = 0;
+				rs->sr_entry = e;
+				RS_ASSERT( e->e_private != NULL );
+				rs->sr_flags = REP_ENTRY_MUSTRELEASE;
 				rs->sr_err = LDAP_SUCCESS;
-				result = send_search_entry( op, rs );
+				rs->sr_err = send_search_entry( op, rs );
+				rs->sr_attrs = NULL;
+				rs->sr_entry = NULL;
 
-				switch (result) {
-				case 0:		/* entry sent ok */
-					break;
-				case 1:		/* entry not sent */
-					break;
-				case -1:	/* connection closed */
+				/* send_search_entry will usually free it.
+				 * an overlay might leave its own copy here;
+				 * bli_flag will be 0 if lock was already released.
+				 */
+				if ( blis.bli_flag ) {
 #ifdef SLAP_ZONE_ALLOC
 					slap_zn_runlock(bdb->bi_cache.c_zctx, e);
 #endif
-					bdb_cache_return_entry_r(bdb->bi_dbenv,
-						&bdb->bi_cache, e, &lock);
-					e = NULL;
-					rs->sr_entry = NULL;
-					rs->sr_err = LDAP_OTHER;
+					bdb_cache_return_entry_r(bdb, e, &lock);
+					if ( opinfo ) {
+						opinfo->boi_locks = blis.bli_next;
+					} else {
+						LDAP_SLIST_REMOVE( &op->o_extra, &bois.boi_oe,
+							OpExtra, oe_next );
+					}
+				}
+				e = NULL;
+
+				switch ( rs->sr_err ) {
+				case LDAP_SUCCESS:	/* entry sent ok */
+					break;
+				default:		/* entry not sent */
+					break;
+				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;
 				}
 			}
@@ -896,13 +1065,11 @@ loop_continue:
 #ifdef SLAP_ZONE_ALLOC
 			slap_zn_runlock(bdb->bi_cache.c_zctx, e);
 #endif
-			bdb_cache_return_entry_r( bdb->bi_dbenv,
-				&bdb->bi_cache, e , &lock );
+			bdb_cache_return_entry_r( bdb, e , &lock );
+			RS_ASSERT( rs->sr_entry == NULL );
 			e = NULL;
 			rs->sr_entry = NULL;
 		}
-		
-		ldap_pvt_thread_yield();
 	}
 
 nochange:
@@ -919,9 +1086,6 @@ nochange:
 	rs->sr_err = LDAP_SUCCESS;
 
 done:
-	if ( !opinfo )
-		LOCK_ID_FREE( bdb->bi_dbenv, locker );
-
 	if( rs->sr_v2ref ) {
 		ber_bvarray_free( rs->sr_v2ref );
 		rs->sr_v2ref = NULL;
@@ -955,7 +1119,7 @@ static int oc_filter(
 {
 	int rc = 0;
 
-	assert( f );
+	assert( f != NULL );
 
 	if( cur > *max ) *max = cur;
 
@@ -991,7 +1155,7 @@ static void *search_stack( Operation *op )
 	void *ret = NULL;
 
 	if ( op->o_threadctx ) {
-		ldap_pvt_thread_pool_getkey( op->o_threadctx, search_stack,
+		ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack,
 			&ret, NULL );
 	} else {
 		ret = bdb->bi_search_stack;
@@ -1001,8 +1165,8 @@ static void *search_stack( Operation *op )
 		ret = ch_malloc( bdb->bi_search_stack_depth * BDB_IDL_UM_SIZE
 			* sizeof( ID ) );
 		if ( op->o_threadctx ) {
-			ldap_pvt_thread_pool_setkey( op->o_threadctx, search_stack,
-				ret, search_stack_free );
+			ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack,
+				ret, search_stack_free, NULL, NULL );
 		} else {
 			bdb->bi_search_stack = ret;
 		}
@@ -1014,7 +1178,7 @@ static int search_candidates(
 	Operation *op,
 	SlapReply *rs,
 	Entry *e,
-	u_int32_t locker,
+	DB_TXN *txn,
 	ID	*ids,
 	ID	*scopes )
 {
@@ -1022,11 +1186,9 @@ static int search_candidates(
 	int rc, depth = 1;
 	Filter		f, rf, xf, nf;
 	ID		*stack;
-	AttributeAssertion aa_ref = { NULL, BER_BVNULL, NULL };
-#ifdef BDB_SUBENTRIES
+	AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT;
 	Filter	sf;
-	AttributeAssertion aa_subentry = { NULL, BER_BVNULL, NULL };
-#endif
+	AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT;
 
 	/*
 	 * This routine takes as input a filter (user-filter)
@@ -1072,7 +1234,6 @@ static int search_candidates(
 	/* Filter depth increased again, adding dummy clause */
 	depth++;
 
-#ifdef BDB_SUBENTRIES
 	if( get_subentries_visibility( op ) ) {
 		struct berval bv_subentry = BER_BVC( "subentry" );
 		sf.f_choice = LDAP_FILTER_EQUALITY;
@@ -1082,7 +1243,6 @@ static int search_candidates(
 		sf.f_next = nf.f_next;
 		nf.f_next = &sf;
 	}
-#endif
 
 	/* Allocate IDL stack, plus 1 more for former tmp */
 	if ( depth+1 > bdb->bi_search_stack_depth ) {
@@ -1092,13 +1252,13 @@ static int search_candidates(
 	}
 
 	if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
-		rc = search_aliases( op, rs, e, locker, ids, scopes, stack );
+		rc = search_aliases( op, rs, e, txn, ids, scopes, stack );
 	} else {
-		rc = bdb_dn2idl( op, e, ids, stack );
+		rc = bdb_dn2idl( op, txn, &e->e_nname, BEI(e), ids, stack );
 	}
 
 	if ( rc == LDAP_SUCCESS ) {
-		rc = bdb_filter_candidates( op, &f, ids,
+		rc = bdb_filter_candidates( op, txn, &f, ids,
 			stack, stack+BDB_IDL_UM_SIZE );
 	}
 
@@ -1125,12 +1285,7 @@ static int search_candidates(
 static int
 parse_paged_cookie( Operation *op, SlapReply *rs )
 {
-	LDAPControl	**c;
 	int		rc = LDAP_SUCCESS;
-	ber_tag_t	tag;
-	ber_int_t	size;
-	BerElement	*ber;
-	struct berval	cookie = BER_BVNULL;
 	PagedResultsState *ps = op->o_pagedresults_state;
 
 	/* this function must be invoked only if the pagedResults
@@ -1138,53 +1293,17 @@ parse_paged_cookie( Operation *op, SlapReply *rs )
 	 * by the frontend */
 	assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED );
 
-	/* look for the appropriate ctrl structure */
-	for ( c = op->o_ctrls; c[0] != NULL; c++ ) {
-		if ( strcmp( c[0]->ldctl_oid, LDAP_CONTROL_PAGEDRESULTS ) == 0 )
-		{
-			break;
-		}
-	}
-
-	if ( c[0] == NULL ) {
-		rs->sr_text = "missing pagedResults control";
-		return LDAP_PROTOCOL_ERROR;
-	}
-
-	/* Tested by frontend */
-	assert( c[0]->ldctl_value.bv_len > 0 );
-
-	/* Parse the control value
-	 *	realSearchControlValue ::= SEQUENCE {
-	 *		size	INTEGER (0..maxInt),
-	 *				-- requested page size from client
-	 *				-- result set size estimate from server
-	 *		cookie	OCTET STRING
-	 * }
-	 */
-	ber = ber_init( &c[0]->ldctl_value );
-	if ( ber == NULL ) {
-		rs->sr_text = "internal error";
-		return LDAP_OTHER;
-	}
-
-	tag = ber_scanf( ber, "{im}", &size, &cookie );
-
-	/* Tested by frontend */
-	assert( tag != LBER_ERROR );
-	assert( size >= 0 );
-
 	/* cookie decoding/checks deferred to backend... */
-	if ( cookie.bv_len ) {
+	if ( ps->ps_cookieval.bv_len ) {
 		PagedResultsCookie reqcookie;
-		if( cookie.bv_len != sizeof( 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, cookie.bv_val, sizeof( reqcookie ));
+		AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie ));
 
 		if ( reqcookie > ps->ps_cookie ) {
 			/* bad cookie */
@@ -1199,23 +1318,11 @@ parse_paged_cookie( Operation *op, SlapReply *rs )
 		}
 
 	} else {
-		/* Initial request.  Initialize state. */
-#if 0
-		if ( op->o_conn->c_pagedresults_state.ps_cookie != 0 ) {
-			/* There's another pagedResults control on the
-			 * same connection; reject new pagedResults controls 
-			 * (allowed by RFC2696) */
-			rs->sr_text = "paged results cookie unavailable; try later";
-			rc = LDAP_UNWILLING_TO_PERFORM;
-			goto done;
-		}
-#endif
-		ps->ps_cookie = 0;
-		ps->ps_count = 0;
+		/* we're going to use ps_cookie */
+		op->o_conn->c_pagedresults_state.ps_cookie = 0;
 	}
 
 done:;
-	(void)ber_free( ber, 1 );
 
 	return rc;
 }
@@ -1227,7 +1334,7 @@ send_paged_response(
 	ID		*lastid,
 	int		tentries )
 {
-	LDAPControl	ctrl, *ctrls[2];
+	LDAPControl	*ctrls[2];
 	BerElementBuffer berbuf;
 	BerElement	*ber = (BerElement *)&berbuf;
 	PagedResultsCookie respcookie;
@@ -1237,8 +1344,6 @@ send_paged_response(
 		"send_paged_response: lastid=0x%08lx nentries=%d\n", 
 		lastid ? *lastid : 0, rs->sr_nentries, NULL );
 
-	BER_BVZERO( &ctrl.ldctl_value );
-	ctrls[0] = &ctrl;
 	ctrls[1] = NULL;
 
 	ber_init2( ber, NULL, LBER_USE_DER );
@@ -1255,11 +1360,13 @@ send_paged_response(
 
 	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;
+		((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;
 	}
@@ -1267,27 +1374,10 @@ send_paged_response(
 	ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
 	ctrls[0]->ldctl_iscritical = 0;
 
-	rs->sr_ctrls = ctrls;
+	slap_add_ctrls( op, rs, ctrls );
 	rs->sr_err = LDAP_SUCCESS;
 	send_ldap_result( op, rs );
-	rs->sr_ctrls = NULL;
 
 done:
 	(void) ber_free_buf( ber );
 }
-
-static int
-bdb_pfid_cmp( const void *v_id1, const void *v_id2 )
-{
-    const ID *p1 = v_id1, *p2 = v_id2;
-	return *p1 - *p2;
-}
-
-static ID*
-bdb_id_dup( Operation *op, ID *id )
-{
-	ID *new;
-	new = ch_malloc( sizeof(ID) );
-	*new = *id;
-	return new;
-}