From 437f21b16e162342e046e27b69a32f6ac8b0ef9e Mon Sep 17 00:00:00 2001
From: Howard Chu <hyc@openldap.org>
Date: Thu, 15 May 2014 20:46:20 -0700
Subject: [PATCH] ITS#7705,#7800 fix back-mdb pagedResults search

mdb_idscopes was remembering the IDs of every entry it checked;
it should only have been saving the IDs of entries that were
actually in the search scope. The extra entries filled the scopes
array, causing a loop searching for a parent entry that was
never inserted.
---
 servers/slapd/back-mdb/dn2id.c  | 18 ++++++++++++++++--
 servers/slapd/back-mdb/idl.h    |  1 +
 servers/slapd/back-mdb/search.c | 16 ++++++++++------
 3 files changed, 27 insertions(+), 8 deletions(-)

diff --git a/servers/slapd/back-mdb/dn2id.c b/servers/slapd/back-mdb/dn2id.c
index ceacb1796f..b0e6905c7b 100644
--- a/servers/slapd/back-mdb/dn2id.c
+++ b/servers/slapd/back-mdb/dn2id.c
@@ -703,7 +703,7 @@ mdb_idscopes(
 	ID2 id2;
 	char	*ptr;
 	int		rc = 0;
-	unsigned int x;
+	unsigned int x, y;
 	unsigned int nrlen, rlen;
 	diskNode *d;
 
@@ -723,6 +723,7 @@ mdb_idscopes(
 		return MDB_SUCCESS;
 	}
 
+	isc->sctmp[0].mid = 0;
 	while (id) {
 		if ( !rc ) {
 			key.mv_data = &id;
@@ -742,21 +743,34 @@ mdb_idscopes(
 		isc->numrdns++;
 
 		if (!rc && id != isc->id) {
+			/* remember our chain of parents */
 			id2.mid = id;
 			id2.mval = data;
-			mdb_id2l_insert( isc->scopes, &id2 );
+			mdb_id2l_insert( isc->sctmp, &id2 );
 		}
 		ptr = data.mv_data;
 		ptr += data.mv_size - sizeof(ID);
 		memcpy( &id, ptr, sizeof(ID) );
+		y = x;
 		x = mdb_id2l_search( isc->scopes, id );
 		if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
 			if ( !isc->scopes[x].mval.mv_data ) {
+				/* This node is in scope, add parent chain to scope */
+				int i = isc->sctmp[0].mid;
+				for ( i = 1; i <= isc->sctmp[0].mid; i++ )
+					mdb_id2l_insert( isc->scopes, &isc->sctmp[i] );
+				/* check id again since inserts may have changed its position */
+				if ( isc->scopes[x].mid != id )
+					x = mdb_id2l_search( isc->scopes, id );
 				isc->nscope = x;
 				return MDB_SUCCESS;
 			}
 			data = isc->scopes[x].mval;
 			rc = 1;
+		} else {
+			/* If we didn't advance, some parent is missing */
+			if ( x == y )
+				return MDB_NOTFOUND;
 		}
 		if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 			break;
diff --git a/servers/slapd/back-mdb/idl.h b/servers/slapd/back-mdb/idl.h
index d614b5bff9..ea862f2148 100644
--- a/servers/slapd/back-mdb/idl.h
+++ b/servers/slapd/back-mdb/idl.h
@@ -88,6 +88,7 @@ typedef struct IdScopes {
 	MDB_cursor *mc;
 	ID id;
 	ID2L scopes;
+	ID2L sctmp;
 	int numrdns;
 	int nscope;
 	int oscope;
diff --git a/servers/slapd/back-mdb/search.c b/servers/slapd/back-mdb/search.c
index fd48762529..9872c52205 100644
--- a/servers/slapd/back-mdb/search.c
+++ b/servers/slapd/back-mdb/search.c
@@ -34,7 +34,8 @@ static int search_candidates(
 	MDB_txn *txn,
 	MDB_cursor *mci,
 	ID	*ids,
-	ID2L	scopes );
+	ID2L	scopes,
+	ID *stack );
 
 static int parse_paged_cookie( Operation *op, SlapReply *rs );
 
@@ -313,6 +314,8 @@ static void scope_chunk_ret( Operation *op, ID2 *scopes )
 			(void *)scopes, scope_chunk_free, NULL, NULL );
 }
 
+static void *search_stack( Operation *op );
+
 int
 mdb_search( Operation *op, SlapReply *rs )
 {
@@ -322,6 +325,7 @@ mdb_search( Operation *op, SlapReply *rs )
 	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;
@@ -365,10 +369,12 @@ mdb_search( Operation *op, SlapReply *rs )
 	}
 
 	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);
@@ -562,7 +568,7 @@ dn2entry_retry:
 		scopes[1].mid = base->e_id;
 		scopes[1].mval.mv_data = NULL;
 		rs->sr_err = search_candidates( op, rs, base,
-			ltid, mci, candidates, scopes );
+			ltid, mci, candidates, scopes, stack );
 		ncand = MDB_IDL_N( candidates );
 		if ( !base->e_id || ncand == NOID ) {
 			/* grab entry count from id2entry stat
@@ -1161,12 +1167,12 @@ static int search_candidates(
 	MDB_txn *txn,
 	MDB_cursor *mci,
 	ID	*ids,
-	ID2L	scopes )
+	ID2L	scopes,
+	ID *stack )
 {
 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 	int rc, depth = 1;
 	Filter		*f, rf, xf, nf, sf;
-	ID		*stack;
 	AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT;
 	AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT;
 
@@ -1221,8 +1227,6 @@ static int search_candidates(
 	/* 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 ) );
-	} else {
-		stack = search_stack( op );
 	}
 
 	if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
-- 
2.39.5