Fix lhash implementation to avoid unwanted resizes during iteration.

openssl/patches/fix_lhash_iteration.patch

Index: openssl/patches/fix_lhash_iteration.patch
diff --git a/openssl/patches/fix_lhash_iteration.patch b/openssl/patches/fix_lhash_iteration.patch
new file mode 100644
index 0000000000000000000000000000000000000000..3bcf79bbf6744fbe5d049641258d8d5953b76828
--- /dev/null
+++ b/openssl/patches/fix_lhash_iteration.patch
@@ -0,0 +1,291 @@
+diff --git a/crypto/conf/conf_api.c b/crypto/conf/conf_api.c
+index f5fcbb9..9a37bd4 100644
+--- a/crypto/conf/conf_api.c
++++ b/crypto/conf/conf_api.c
+@@ -225,9 +225,6 @@ void _CONF_free_data(CONF *conf)
+ 	{
+ 	if (conf == NULL || conf->data == NULL) return;
+ 
+-	lh_CONF_VALUE_down_load(conf->data)=0; /* evil thing to make
+-				  * sure the 'OPENSSL_free()' works as
+-				  * expected */
+ 	lh_CONF_VALUE_doall_arg(conf->data,
+ 				LHASH_DOALL_ARG_FN(value_free_hash),
+ 				LHASH_OF(CONF_VALUE), conf->data);
+diff --git a/crypto/lhash/lhash.c b/crypto/lhash/lhash.c
+index 47f7480..e5b3cdf 100644
+--- a/crypto/lhash/lhash.c
++++ b/crypto/lhash/lhash.c
+@@ -94,6 +94,7 @@
+  *
+  * 1.0 eay - First version
+  */
++#include <limits.h>
+ #include <stdio.h>
+ #include <string.h>
+ #include <stdlib.h>
+@@ -107,6 +108,113 @@ const char lh_version[]="lhash" OPENSSL_VERSION_PTEXT;
+ #define UP_LOAD		(2*LH_LOAD_MULT) /* load times 256  (default 2) */
+ #define DOWN_LOAD	(LH_LOAD_MULT)   /* load times 256  (default 1) */
+ 
++/* Maximum number of nodes to guarantee the load computations don't overflow */
++#define MAX_LOAD_ITEMS   (UINT_MAX / LH_LOAD_MULT)
++
++/* The field 'iteration_state' is used to hold data to ensure that a hash
++ * table is not resized during an 'insert' or 'delete' operation performed
++ * within a lh_doall/lh_doall_arg call.
++ *
++ * Conceptually, this records two things:
++ *
++ *   - A 'depth' count, which is incremented at the start of lh_doall*,
++ *     and decremented just before it returns.
++ *
++ *   - A 'mutated' boolean flag, which is set in lh_insert() or lh_delete()
++ *     when the operation is performed with a non-0 depth.
++ *
++ * The following are helper macros to handle this state in a more explicit
++ * way.
++ */
++
++/* Reset the iteration state to its defaults. */
++#define LH_ITERATION_RESET(lh) do { \
++	(lh)->iteration_state = 0; \
++	} while (0)
++
++/* Returns 1 if the hash table is currently being iterated on, 0 otherwise. */
++#define LH_ITERATION_IS_ACTIVE(lh)  ((lh)->iteration_state >= 2)
++
++/* Increment iteration depth. This should always be followed by a paired call
++ * to LH_ITERATION_DECREMENT_DEPTH(). */
++#define LH_ITERATION_INCREMENT_DEPTH(lh) do { \
++	(lh)->iteration_state += 2; \
++	} while (0)
++
++/* Decrement iteration depth. This should always be called after a paired call
++ * to LH_ITERATION_INCREMENT_DEPTH(). */
++#define LH_ITERATION_DECREMENT_DEPTH(lh) do { \
++	(lh)->iteration_state -= 2; \
++	} while (0)
++
++/* Return 1 if the iteration 'mutated' flag is set, 0 otherwise. */
++#define LH_ITERATION_IS_MUTATED(lh) (((lh)->iteration_state & 1) != 0)
++
++/* Set the iteration 'mutated' flag to 1. LH_ITERATION_RESET() to reset it. */
++#define LH_ITERATION_SET_MUTATED(lh) do { \
++	(lh)->iteration_state |= 1; \
++	} while (0)
++
++/* This macro returns 1 if the hash table should be expanded due to its current
++ * load, or 0 otherwise. The exact comparison to be performed is expressed by
++ * the mathematical expression (where '//' denotes division over real numbers):
++ *
++ *      (num_items // num_nodes) >= (up_load // LOAD_MULT)    or
++ *      (num_items * LOAD_MULT // num_nodes) >= up_load.
++ *
++ * Given that the C language operator '/' implements integer division, i.e:
++ *     a // b == (a / b) + epsilon  (with 0 <= epsilon < 1, for positive a & b)
++ *
++ * This can be rewritten as:
++ *     (num_items * LOAD_MULT / num_nodes) + epsilon >= up_load
++ *     (num_items * LOAD_MULT / num_nodes) - up_load >= - epsilon
++ *
++ * Let's call 'A' the left-hand side of the equation above, it is an integer
++ * and:
++ *     - If A >= 0, the expression is true for any value of epsilon.
++ *     - If A <= -1, the expression is also true for any value of epsilon.
++ *
++ * In other words, this is equivalent to 'A >= 0', or:
++ *     (num_items * LOAD_MULT / num_nodes) >= up_load
++ */
++#define LH_SHOULD_EXPAND(lh) \
++	((lh)->num_items < MAX_LOAD_ITEMS && \
++	 (((lh)->num_items*LH_LOAD_MULT/(lh)->num_nodes) >= (lh)->up_load))
++
++/* This macro returns 1 if the hash table should be contracted due to its
++ * current load, or 0 otherwise. Abbreviated computations are:
++ *
++ *    (num_items // num_nodes) <= (down_load // LOAD_MULT)
++ *    (num_items * LOAD_MULT // num_nodes) <= down_load
++ *    (num_items * LOAD_MULT / num_nodes) + epsilon <= down_load
++ *    (num_items * LOAD_MULT / num_nodes) - down_load <= -epsilon
++ *
++ * Let's call 'B' the left-hand side of the equation above:
++ *    - If B <= -1, the expression is true for any value of epsilon.
++ *    - If B >= 1, the expression is false for any value of epsilon.
++ *    - If B == 0, the expression is true for 'epsilon == 0', and false
++ *      otherwise, which is problematic.
++ *
++ * To work around this problem, while keeping the code simple, just change
++ * the initial expression to use a strict inequality, i.e.:
++ *
++ *    (num_items // num_nodes) < (down_load // LOAD_MULT)
++ *
++ * Which leads to:
++ *    (num_items * LOAD_MULT / num_nodes) - down_load < -epsilon
++ *
++ * Then:
++ *    - If 'B <= -1', the expression is true for any value of epsilon.
++ *    - If 'B' >= 0, the expression is false for any value of epsilon,
++ *
++ * In other words, this is equivalent to 'B < 0', or:
++ *     (num_items * LOAD_MULT / num_nodes) < down_load
++ */
++#define LH_SHOULD_CONTRACT(lh) \
++	(((lh)->num_nodes > MIN_NODES) && \
++	 ((lh)->num_items < MAX_LOAD_ITEMS && \
++	 ((lh)->num_items*LH_LOAD_MULT/(lh)->num_nodes) < (lh)->down_load))
++
+ static void expand(_LHASH *lh);
+ static void contract(_LHASH *lh);
+ static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash);
+@@ -147,6 +255,7 @@ _LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
+ 	ret->num_hash_comps=0;
+ 
+ 	ret->error=0;
++	LH_ITERATION_RESET(ret);
+ 	return(ret);
+ err1:
+ 	OPENSSL_free(ret);
+@@ -183,7 +292,10 @@ void *lh_insert(_LHASH *lh, void *data)
+ 	void *ret;
+ 
+ 	lh->error=0;
+-	if (lh->up_load <= (lh->num_items*LH_LOAD_MULT/lh->num_nodes))
++	/* Do not expand the array if the table is being iterated on. */
++	if (LH_ITERATION_IS_ACTIVE(lh))
++		LH_ITERATION_SET_MUTATED(lh);
++	else if (LH_SHOULD_EXPAND(lh))
+ 		expand(lh);
+ 
+ 	rn=getrn(lh,data,&hash);
+@@ -238,8 +350,10 @@ void *lh_delete(_LHASH *lh, const void *data)
+ 		}
+ 
+ 	lh->num_items--;
+-	if ((lh->num_nodes > MIN_NODES) &&
+-		(lh->down_load >= (lh->num_items*LH_LOAD_MULT/lh->num_nodes)))
++	/* Do not contract the array if the table is being iterated on. */
++	if (LH_ITERATION_IS_ACTIVE(lh))
++		LH_ITERATION_SET_MUTATED(lh);
++	else if (LH_SHOULD_CONTRACT(lh))
+ 		contract(lh);
+ 
+ 	return(ret);
+@@ -276,6 +390,7 @@ static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
+ 	if (lh == NULL)
+ 		return;
+ 
++	LH_ITERATION_INCREMENT_DEPTH(lh);
+ 	/* reverse the order so we search from 'top to bottom'
+ 	 * We were having memory leaks otherwise */
+ 	for (i=lh->num_nodes-1; i>=0; i--)
+@@ -283,10 +398,7 @@ static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
+ 		a=lh->b[i];
+ 		while (a != NULL)
+ 			{
+-			/* 28/05/91 - eay - n added so items can be deleted
+-			 * via lh_doall */
+-			/* 22/05/08 - ben - eh? since a is not passed,
+-			 * this should not be needed */
++			/* note that 'a' can be deleted by the callback */
+ 			n=a->next;
+ 			if(use_arg)
+ 				func_arg(a->data,arg);
+@@ -295,6 +407,19 @@ static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
+ 			a=n;
+ 			}
+ 		}
++
++	LH_ITERATION_DECREMENT_DEPTH(lh);
++	if (!LH_ITERATION_IS_ACTIVE(lh) && LH_ITERATION_IS_MUTATED(lh))
++		{
++		LH_ITERATION_RESET(lh);
++		/* Resize the buckets array if necessary. Each expand() or
++		 * contract() call will double/halve the size of the array,
++		 * respectively, so call them in a loop. */
++		while (LH_SHOULD_EXPAND(lh))
++			expand(lh);
++		while (LH_SHOULD_CONTRACT(lh))
++			contract(lh);
++		}
+ 	}
+ 
+ void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func)
+diff --git a/crypto/lhash/lhash.h b/crypto/lhash/lhash.h
+index e7d8763..75386f2 100644
+--- a/crypto/lhash/lhash.h
++++ b/crypto/lhash/lhash.h
+@@ -163,6 +163,7 @@ typedef struct lhash_st
+ 	unsigned long num_hash_comps;
+ 
+ 	int error;
++	int iteration_state;
+ 	} _LHASH;	/* Do not use _LHASH directly, use LHASH_OF
+ 			 * and friends */
+ 
+diff --git a/crypto/objects/o_names.c b/crypto/objects/o_names.c
+index 4a548c2..4e18045 100644
+--- a/crypto/objects/o_names.c
++++ b/crypto/objects/o_names.c
+@@ -350,13 +350,9 @@ static void name_funcs_free(NAME_FUNCS *ptr)
+ 
+ void OBJ_NAME_cleanup(int type)
+ 	{
+-	unsigned long down_load;
+-
+ 	if (names_lh == NULL) return;
+ 
+ 	free_type=type;
+-	down_load=lh_OBJ_NAME_down_load(names_lh);
+-	lh_OBJ_NAME_down_load(names_lh)=0;
+ 
+ 	lh_OBJ_NAME_doall(names_lh,LHASH_DOALL_FN(names_lh_free));
+ 	if (type < 0)
+@@ -366,7 +362,5 @@ void OBJ_NAME_cleanup(int type)
+ 		names_lh=NULL;
+ 		name_funcs_stack = NULL;
+ 		}
+-	else
+-		lh_OBJ_NAME_down_load(names_lh)=down_load;
+ 	}
+ 
+diff --git a/crypto/objects/obj_dat.c b/crypto/objects/obj_dat.c
+index 8a342ba..ef0512a 100644
+--- a/crypto/objects/obj_dat.c
++++ b/crypto/objects/obj_dat.c
+@@ -227,7 +227,6 @@ void OBJ_cleanup(void)
+ 		return ;
+ 		}
+ 	if (added == NULL) return;
+-	lh_ADDED_OBJ_down_load(added) = 0;
+ 	lh_ADDED_OBJ_doall(added,LHASH_DOALL_FN(cleanup1)); /* zero counters */
+ 	lh_ADDED_OBJ_doall(added,LHASH_DOALL_FN(cleanup2)); /* set counters */
+ 	lh_ADDED_OBJ_doall(added,LHASH_DOALL_FN(cleanup3)); /* free objects */
+diff --git a/include/openssl/lhash.h b/include/openssl/lhash.h
+index e7d8763..75386f2 100644
+--- a/include/openssl/lhash.h
++++ b/include/openssl/lhash.h
+@@ -163,6 +163,7 @@ typedef struct lhash_st
+ 	unsigned long num_hash_comps;
+ 
+ 	int error;
++	int iteration_state;
+ 	} _LHASH;	/* Do not use _LHASH directly, use LHASH_OF
+ 			 * and friends */
+ 
+diff --git a/ssl/ssl_sess.c b/ssl/ssl_sess.c
+index 920b763..447a37e 100644
+--- a/ssl/ssl_sess.c
++++ b/ssl/ssl_sess.c
+@@ -999,11 +999,8 @@ void SSL_CTX_flush_sessions(SSL_CTX *s, long t)
+ 	if (tp.cache == NULL) return;
+ 	tp.time=t;
+ 	CRYPTO_w_lock(CRYPTO_LOCK_SSL_CTX);
+-	i=CHECKED_LHASH_OF(SSL_SESSION, tp.cache)->down_load;
+-	CHECKED_LHASH_OF(SSL_SESSION, tp.cache)->down_load=0;
+ 	lh_SSL_SESSION_doall_arg(tp.cache, LHASH_DOALL_ARG_FN(timeout),
+ 				 TIMEOUT_PARAM, &tp);
+-	CHECKED_LHASH_OF(SSL_SESSION, tp.cache)->down_load=i;
+ 	CRYPTO_w_unlock(CRYPTO_LOCK_SSL_CTX);
+ 	}
+