From 6416d83372aa272a72414cd985fab731cde556c7 Mon Sep 17 00:00:00 2001
From: Pierangelo Masarati <ando@openldap.org>
Date: Sun, 22 Oct 2006 20:31:41 +0000
Subject: [PATCH] add ldap_int_discard(); use it in proxies (ITS#4717)

---
 libraries/libldap/abandon.c    | 149 ++++++++++++++++++++++++---------
 libraries/libldap/ldap-int.h   |   8 +-
 libraries/libldap/result.c     | 148 +++++++++++++++++++++-----------
 servers/slapd/back-ldap/bind.c |   2 +-
 servers/slapd/back-meta/bind.c |   2 +-
 5 files changed, 219 insertions(+), 90 deletions(-)

diff --git a/libraries/libldap/abandon.c b/libraries/libldap/abandon.c
index c03d9264d6..30742ea825 100644
--- a/libraries/libldap/abandon.c
+++ b/libraries/libldap/abandon.c
@@ -37,12 +37,13 @@
 
 #include "ldap-int.h"
 
-static int do_abandon LDAP_P((
+static int
+do_abandon(
 	LDAP *ld,
 	ber_int_t origid,
 	ber_int_t msgid,
 	LDAPControl **sctrls,
-	LDAPControl **cctrls));
+	int sendabandon );
 
 /*
  * ldap_abandon_ext - perform an ldap extended abandon operation.
@@ -66,20 +67,24 @@ ldap_abandon_ext(
 	LDAPControl **sctrls,
 	LDAPControl **cctrls )
 {
-	int rc;
+	int	rc;
+
 	Debug( LDAP_DEBUG_TRACE, "ldap_abandon_ext %d\n", msgid, 0, 0 );
 
 	/* check client controls */
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_lock( &ld->ld_req_mutex );
 #endif
+
 	rc = ldap_int_client_controls( ld, cctrls );
-	if( rc == LDAP_SUCCESS )
-		rc = do_abandon( ld, msgid, msgid, sctrls, cctrls );
+	if ( rc == LDAP_SUCCESS ) {
+		rc = do_abandon( ld, msgid, msgid, sctrls, 1 );
+	}
 
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_unlock( &ld->ld_req_mutex );
 #endif
+
 	return rc;
 }
 
@@ -104,25 +109,43 @@ ldap_abandon( LDAP *ld, int msgid )
 }
 
 
+int
+ldap_int_discard(
+	LDAP *ld,
+	ber_int_t msgid )
+{
+	int	rc;
+
+#ifdef LDAP_R_COMPILE
+	ldap_pvt_thread_mutex_lock( &ld->ld_req_mutex );
+#endif
+
+	rc = do_abandon( ld, msgid, msgid, NULL, 0 );
+
+#ifdef LDAP_R_COMPILE
+	ldap_pvt_thread_mutex_unlock( &ld->ld_req_mutex );
+#endif
+
+	return rc;
+}
+
 static int
 do_abandon(
 	LDAP *ld,
 	ber_int_t origid,
 	ber_int_t msgid,
 	LDAPControl **sctrls,
-	LDAPControl **cctrls )
+	int sendabandon )
 {
 	BerElement	*ber;
-	int		i, err, sendabandon;
+	int		i, err;
 	ber_int_t	*old_abandon;
 	Sockbuf		*sb;
 	LDAPRequest	*lr;
 
-	Debug( LDAP_DEBUG_TRACE, "do_abandon origid %d, msgid %d\n",
+	Debug( LDAP_DEBUG_TRACE, "ldap_int_discard origid %d, msgid %d\n",
 		origid, msgid, 0 );
 
-	sendabandon = 1;
-
 	/* find the request that we are abandoning */
 start_again:;
 	lr = ld->ld_requests;
@@ -132,8 +155,8 @@ start_again:;
 		}
 
 		if ( lr->lr_origid == msgid ) {/* child:  abandon it */
-			(void)do_abandon( ld,
-				lr->lr_origid, lr->lr_msgid, sctrls, cctrls );
+			(void)do_abandon( ld, lr->lr_origid, lr->lr_msgid,
+				sctrls, sendabandon );
 
 			/* restart, as lr may now be dangling... */
 			goto start_again;
@@ -154,9 +177,9 @@ start_again:;
 		}
 	}
 
-/* ldap_msgdelete locks the res_mutex. Give up the req_mutex
- * while we're in there.
- */
+	/* ldap_msgdelete locks the res_mutex. Give up the req_mutex
+	 * while we're in there.
+	 */
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_unlock( &ld->ld_req_mutex );
 #endif
@@ -172,7 +195,8 @@ start_again:;
 	/* fetch again the request that we are abandoning */
 	if ( lr != NULL ) {
 		for ( lr = ld->ld_requests; lr != NULL; lr = lr->lr_next ) {
-			if ( lr->lr_msgid == msgid ) {	/* this message */
+			/* this message */
+			if ( lr->lr_msgid == msgid ) {
 				break;
 			}
 		}
@@ -180,22 +204,23 @@ start_again:;
 
 	err = 0;
 	if ( sendabandon ) {
-		if( ber_sockbuf_ctrl( ld->ld_sb, LBER_SB_OPT_GET_FD, NULL ) == -1 ) {
+		if ( ber_sockbuf_ctrl( ld->ld_sb, LBER_SB_OPT_GET_FD, NULL ) == -1 ) {
 			/* not connected */
 			err = -1;
 			ld->ld_errno = LDAP_SERVER_DOWN;
 
-		} else if ( (ber = ldap_alloc_ber_with_options( ld )) == NULL ) {
-			/* BER element alocation failed */
+		} else if ( ( ber = ldap_alloc_ber_with_options( ld ) ) == NULL ) {
+			/* BER element allocation failed */
 			err = -1;
 			ld->ld_errno = LDAP_NO_MEMORY;
 
 		} else {
-	/*
-	 * We already have the mutex in LDAP_R_COMPILE, so
-	 * don't try to get it again.
-	 *		LDAP_NEXT_MSGID(ld, i);
-	 */
+			/*
+			 * We already have the mutex in LDAP_R_COMPILE, so
+			 * don't try to get it again.
+			 *		LDAP_NEXT_MSGID(ld, i);
+			 */
+
 			i = ++(ld)->ld_msgid;
 #ifdef LDAP_CONNECTIONLESS
 			if ( LDAP_IS_UDP(ld) ) {
@@ -219,7 +244,7 @@ start_again:;
 					LDAP_REQ_ABANDON, msgid );
 			}
 
-			if( err == -1 ) {
+			if ( err == -1 ) {
 				/* encoding error */
 				ld->ld_errno = LDAP_ENCODING_ERROR;
 
@@ -234,7 +259,7 @@ start_again:;
 					/* close '{' */
 					err = ber_printf( ber, /*{*/ "N}" );
 
-					if( err == -1 ) {
+					if ( err == -1 ) {
 						/* encoding error */
 						ld->ld_errno = LDAP_ENCODING_ERROR;
 					}
@@ -267,6 +292,7 @@ start_again:;
 		if ( sendabandon || lr->lr_status == LDAP_REQST_WRITING ) {
 			ldap_free_connection( ld, lr->lr_conn, 0, 1 );
 		}
+
 		if ( origid == msgid ) {
 			ldap_free_request( ld, lr );
 		}
@@ -278,25 +304,70 @@ start_again:;
 	ldap_pvt_thread_mutex_unlock( &ld->ld_req_mutex );
 	ldap_pvt_thread_mutex_lock( &ld->ld_res_mutex );
 #endif
+
+	/* use bisection */
 	i = 0;
 	if ( ld->ld_abandoned != NULL ) {
-		for ( ; ld->ld_abandoned[i] != -1; i++ )
-			;	/* NULL */
-	}
+		int		begin,
+				end;
+
+		assert( ld->ld_nabandoned >= 0 );
+
+		begin = 0;
+		end = ld->ld_nabandoned - 1;
 
-	old_abandon = ld->ld_abandoned;
+		if ( ld->ld_nabandoned == 0 || ld->ld_abandoned[ begin ] > msgid ) {
+			i = 0;
 
-	ld->ld_abandoned = (ber_int_t *) LDAP_REALLOC( (char *)
-		ld->ld_abandoned, (i + 2) * sizeof(ber_int_t) );
-		
-	if ( ld->ld_abandoned == NULL ) {
-		ld->ld_abandoned = old_abandon;
-		ld->ld_errno = LDAP_NO_MEMORY;
-		goto done;
+		} else if ( ld->ld_abandoned[ end ] < msgid ) {
+			i = ld->ld_nabandoned;
+
+		} else {
+			int	pos, curid;
+
+			while ( end >= begin ) {
+				pos = (begin + end)/2;
+				curid = ld->ld_abandoned[ pos ];
+
+				if ( msgid < curid ) {
+					end = pos - 1;
+
+				} else if ( msgid > curid ) {
+					begin = pos + 1;
+
+				} else {
+					/* already abandoned? */
+					i = -1;
+					break;
+				}
+			}
+
+			if ( i == 0 ) {
+				i = pos;
+			}
+		}
 	}
 
-	ld->ld_abandoned[i] = msgid;
-	ld->ld_abandoned[i + 1] = -1;
+	if ( i != -1 ) {
+		int	pos = i;
+
+		old_abandon = ld->ld_abandoned;
+
+		ld->ld_abandoned = (ber_int_t *) LDAP_REALLOC( (char *)ld->ld_abandoned,
+			( ld->ld_nabandoned + 1 ) * sizeof( ber_int_t ) );
+
+		if ( ld->ld_abandoned == NULL ) {
+			ld->ld_abandoned = old_abandon;
+			ld->ld_errno = LDAP_NO_MEMORY;
+			goto done;
+		}
+
+		for ( i = ld->ld_nabandoned; i > pos; i-- ) {
+			ld->ld_abandoned[ i ] = ld->ld_abandoned[ i - 1 ];
+		}
+		ld->ld_abandoned[ pos ] = msgid;
+		++ld->ld_nabandoned;
+	}
 
 	if ( err != -1 ) {
 		ld->ld_errno = LDAP_SUCCESS;
diff --git a/libraries/libldap/ldap-int.h b/libraries/libldap/ldap-int.h
index e4997b0259..5a1ba5e0f8 100644
--- a/libraries/libldap/ldap-int.h
+++ b/libraries/libldap/ldap-int.h
@@ -365,7 +365,8 @@ struct ldap {
 	ldap_pvt_thread_mutex_t	ld_res_mutex;
 #endif
 
-	ber_int_t		*ld_abandoned;	/* array of abandoned requests */
+	ber_len_t	ld_nabandoned;
+	ber_int_t	*ld_abandoned;	/* array of abandoned requests */
 
 	LDAPCache	*ld_cache;	/* non-null if cache is initialized */
 
@@ -396,6 +397,11 @@ LDAP_V( ldap_pvt_thread_mutex_t ) ldap_int_sasl_mutex;
 #define	LDAP_NEXT_MSGID(ld, id)	id = ++(ld)->ld_msgid
 #endif
 
+LDAP_F ( int )
+ldap_int_discard LDAP_P((
+	LDAP *ld,
+	ber_int_t msgid ));
+
 /*
  * in init.c
  */
diff --git a/libraries/libldap/result.c b/libraries/libldap/result.c
index 1720b85df9..f1ed0d91d2 100644
--- a/libraries/libldap/result.c
+++ b/libraries/libldap/result.c
@@ -68,7 +68,8 @@
 #include "ldap-int.h"
 #include "ldap_log.h"
 
-static int ldap_abandoned LDAP_P(( LDAP *ld, ber_int_t msgid ));
+static int ldap_abandoned_idx LDAP_P(( LDAP *ld, ber_int_t msgid ));
+#define ldap_abandoned(ld, msgid)	( ldap_abandoned_idx((ld), (msgid)) > -1 )
 static int ldap_mark_abandoned LDAP_P(( LDAP *ld, ber_int_t msgid ));
 static int wait4msg LDAP_P(( LDAP *ld, ber_int_t msgid, int all, struct timeval *timeout,
 	LDAPMessage **result ));
@@ -107,8 +108,8 @@ ldap_result(
 	struct timeval *timeout,
 	LDAPMessage **result )
 {
-	LDAPMessage	*lm;
-	int	rc;
+	LDAPMessage	*lm = NULL;
+	int		rc;
 
 	assert( ld != NULL );
 	assert( result != NULL );
@@ -118,19 +119,26 @@ ldap_result(
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_lock( &ld->ld_res_mutex );
 #endif
-	lm = chkResponseList(ld, msgid, all);
+
+#if 0
+	/* this is already done inside wait4msg(), right?... */
+	lm = chkResponseList( ld, msgid, all );
+#endif
 
 	if ( lm == NULL ) {
 		rc = wait4msg( ld, msgid, all, timeout, result );
+
 	} else {
 		*result = lm;
 		ld->ld_errno = LDAP_SUCCESS;
 		rc = lm->lm_msgtype;
 	}
+
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_unlock( &ld->ld_res_mutex );
 #endif
-	return( rc );
+
+	return rc;
 }
 
 static LDAPMessage *
@@ -140,6 +148,7 @@ chkResponseList(
 	int all)
 {
 	LDAPMessage	*lm, **lastlm, *nextlm;
+	int		cnt = 0;
 
 	/*
 	 * Look through the list of responses we have received on
@@ -159,11 +168,12 @@ chkResponseList(
 	lastlm = &ld->ld_responses;
 	for ( lm = ld->ld_responses; lm != NULL; lm = nextlm ) {
 		nextlm = lm->lm_next;
+		++cnt;
 
 		if ( ldap_abandoned( ld, lm->lm_msgid ) ) {
 			Debug( LDAP_DEBUG_TRACE,
 				"ldap_chkResponseList msg abandoned, msgid %d\n",
-			    msgid, 0, 0 );
+				msgid, 0, 0 );
 			ldap_mark_abandoned( ld, lm->lm_msgid );
 
 			/* Remove this entry from list */
@@ -178,14 +188,16 @@ chkResponseList(
 			LDAPMessage	*tmp;
 
 			if ( all == LDAP_MSG_ONE || all == LDAP_MSG_RECEIVED ||
-				msgid == LDAP_RES_UNSOLICITED ) {
+				msgid == LDAP_RES_UNSOLICITED )
+			{
 				break;
 			}
 
 			tmp = lm->lm_chain_tail;
-			if ((tmp->lm_msgtype == LDAP_RES_SEARCH_ENTRY) ||
+			if ( (tmp->lm_msgtype == LDAP_RES_SEARCH_ENTRY) ||
 				(tmp->lm_msgtype == LDAP_RES_SEARCH_REFERENCE) ||
-				(tmp->lm_msgtype == LDAP_RES_INTERMEDIATE)) {
+				(tmp->lm_msgtype == LDAP_RES_INTERMEDIATE) )
+			{
 				tmp = NULL;
 			}
 
@@ -198,28 +210,38 @@ chkResponseList(
 		lastlm = &lm->lm_next;
 	}
 
-    if ( lm != NULL ) {
+#if 0
+	{
+		char	buf[ BUFSIZ ];
+
+		snprintf( buf, sizeof( buf ), "ld=%p msgid=%d%s cnt=%d",
+			ld, msgid, all ? " all" : "", cnt );
+		Debug( LDAP_DEBUG_TRACE, "+++ chkResponseList %s\n", buf, 0, 0 );
+	}
+#endif
+
+	if ( lm != NULL ) {
 		/* Found an entry, remove it from the list */
-	    if ( all == LDAP_MSG_ONE && lm->lm_chain != NULL ) {
+		if ( all == LDAP_MSG_ONE && lm->lm_chain != NULL ) {
 			*lastlm = lm->lm_chain;
 			lm->lm_chain->lm_next = lm->lm_next;
 			lm->lm_chain->lm_chain_tail = ( lm->lm_chain_tail != lm ) ? lm->lm_chain_tail : lm->lm_chain;
 			lm->lm_chain = NULL;
 			lm->lm_chain_tail = NULL;
-	    } else {
+		} else {
 			*lastlm = lm->lm_next;
 		}
-	    lm->lm_next = NULL;
-    }
+		lm->lm_next = NULL;
+	}
 
 #ifdef LDAP_DEBUG
-	if( lm == NULL) {
+	if ( lm == NULL) {
 		Debug( LDAP_DEBUG_TRACE,
 			"ldap_chkResponseList returns ld %p NULL\n", (void *)ld, 0, 0);
 	} else {
 		Debug( LDAP_DEBUG_TRACE,
 			"ldap_chkResponseList returns ld %p msgid %d, type 0x%02lu\n",
-			(void *)ld, lm->lm_msgid, (unsigned long) lm->lm_msgtype);
+			(void *)ld, lm->lm_msgid, (unsigned long) lm->lm_msgtype );
 	}
 #endif
     return lm;
@@ -1158,7 +1180,7 @@ ldap_msgfree( LDAPMessage *lm )
 		LDAP_FREE( (char *) lm );
 	}
 
-	return( type );
+	return type;
 }
 
 /*
@@ -1174,62 +1196,95 @@ ldap_msgdelete( LDAP *ld, int msgid )
 
 	assert( ld != NULL );
 
-	Debug( LDAP_DEBUG_TRACE, "ldap_msgdelete\n", 0, 0, 0 );
+	Debug( LDAP_DEBUG_TRACE, "ldap_msgdelete ld=%p msgid=%d\n",
+		(void *)ld, msgid, 0 );
 
-	prev = NULL;
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_lock( &ld->ld_res_mutex );
 #endif
+	prev = NULL;
 	for ( lm = ld->ld_responses; lm != NULL; lm = lm->lm_next ) {
-		if ( lm->lm_msgid == msgid )
+		if ( lm->lm_msgid == msgid ) {
 			break;
+		}
 		prev = lm;
 	}
 
 	if ( lm == NULL ) {
 		rc = -1;
+
 	} else {
-		if ( prev == NULL )
+		if ( prev == NULL ) {
 			ld->ld_responses = lm->lm_next;
-		else
+		} else {
 			prev->lm_next = lm->lm_next;
+		}
 	}
 #ifdef LDAP_R_COMPILE
 	ldap_pvt_thread_mutex_unlock( &ld->ld_res_mutex );
 #endif
-	if ( lm && ldap_msgfree( lm ) == LDAP_RES_SEARCH_ENTRY )
+	if ( lm && ldap_msgfree( lm ) == LDAP_RES_SEARCH_ENTRY ) {
 		rc = -1;
+	}
 
-	return( rc );
+	return rc;
 }
 
 
 /*
- * ldap_abandoned
+ * ldap_abandoned_idx
  *
- * return 1 if message msgid is waiting to be abandoned, 0 otherwise
+ * return the location of the message id in the array of abandoned
+ * message ids, or -1
  *
  * expects ld_res_mutex to be locked
  */
 static int
-ldap_abandoned( LDAP *ld, ber_int_t msgid )
+ldap_abandoned_idx( LDAP *ld, ber_int_t msgid )
 {
-	int	i;
+	int	begin,
+		end;
 
 #ifdef LDAP_R_COMPILE
 	LDAP_PVT_THREAD_ASSERT_MUTEX_OWNER( &ld->ld_res_mutex );
 #endif
 
-	if ( ld->ld_abandoned == NULL )
-		return( 0 );
+	assert( ld->ld_nabandoned >= 0 );
 
-	for ( i = 0; ld->ld_abandoned[i] != -1; i++ )
-		if ( ld->ld_abandoned[i] == msgid )
-			return( 1 );
+	if ( ld->ld_abandoned == NULL || ld->ld_nabandoned == 0 ) {
+		return -1;
+	}
 
-	return( 0 );
-}
+	begin = 0;
+	end = ld->ld_nabandoned - 1;
 
+	/* use bisection */
+	if ( msgid < ld->ld_abandoned[ begin ] ) {
+		return -1;
+	}
+
+	if ( msgid > ld->ld_abandoned[ end ] ) {
+		return -1;
+	}
+
+	while ( end >= begin ) {
+		int	pos = (begin + end)/2;
+		int	curid = ld->ld_abandoned[ pos ];
+
+		if ( msgid < curid ) {
+			end = pos - 1;
+
+		} else if ( msgid > curid ) {
+			begin = pos + 1;
+
+		} else {
+			return pos;
+		}
+	}
+
+	/* not abandoned */
+	return -1;
+}
 
 /*
  * ldap_mark_abandoned
@@ -1239,25 +1294,22 @@ ldap_abandoned( LDAP *ld, ber_int_t msgid )
 static int
 ldap_mark_abandoned( LDAP *ld, ber_int_t msgid )
 {
-	int	i;
+	int	i, idx;
 
 #ifdef LDAP_R_COMPILE
 	LDAP_PVT_THREAD_ASSERT_MUTEX_OWNER( &ld->ld_res_mutex );
 #endif
 
-	if ( ld->ld_abandoned == NULL )
-		return( -1 );
-
-	for ( i = 0; ld->ld_abandoned[i] != -1; i++ )
-		if ( ld->ld_abandoned[i] == msgid )
-			break;
-
-	if ( ld->ld_abandoned[i] == -1 )
-		return( -1 );
+	idx = ldap_abandoned_idx( ld, msgid );
+	if ( idx == -1 ) {
+		return -1;
+	}
 
-	for ( ; ld->ld_abandoned[i] != -1; i++ ) {
-		ld->ld_abandoned[i] = ld->ld_abandoned[i + 1];
+	--ld->ld_nabandoned;
+	assert( ld->ld_nabandoned >= 0 );
+	for ( i = idx; i < ld->ld_nabandoned; i++ ) {
+		ld->ld_abandoned[ i ] = ld->ld_abandoned[ i + 1 ];
 	}
 
-	return( 0 );
+	return 0;
 }
diff --git a/servers/slapd/back-ldap/bind.c b/servers/slapd/back-ldap/bind.c
index 2f62b40c99..92cb4ea8c1 100644
--- a/servers/slapd/back-ldap/bind.c
+++ b/servers/slapd/back-ldap/bind.c
@@ -1342,7 +1342,7 @@ ldap_back_cancel(
 	}
 
 	if ( LDAP_BACK_IGNORE( li ) ) {
-		return LDAP_SUCCESS;
+		return ldap_int_discard( lc->lc_ld, msgid );
 	}
 
 	if ( LDAP_BACK_CANCEL( li ) ) {
diff --git a/servers/slapd/back-meta/bind.c b/servers/slapd/back-meta/bind.c
index faf0526026..d2d9cb02d6 100644
--- a/servers/slapd/back-meta/bind.c
+++ b/servers/slapd/back-meta/bind.c
@@ -865,7 +865,7 @@ meta_back_cancel(
 		rc = ldap_abandon_ext( msc->msc_ld, msgid, NULL, NULL );
 
 	} else if ( META_BACK_TGT_IGNORE( mt ) ) {
-		rc = LDAP_SUCCESS;
+		rc = ldap_int_discard( msc->msc_ld, msgid );
 
 	} else if ( META_BACK_TGT_CANCEL( mt ) ) {
 		rc = ldap_cancel_s( msc->msc_ld, msgid, NULL, NULL );
-- 
2.39.5