Fix lhash implementation to avoid unwanted resizes during iteration.

openssl/crypto/lhash/lhash.c

 /* crypto/lhash/lhash.c */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
  * This package is an SSL implementation written
  * by Eric Young (eay@cryptsoft.com).
  * The implementation was written so as to conform with Netscapes SSL.
  * 
  * This library is free for commercial and non-commercial use as long as
  * the following conditions are aheared to.  The following conditions
@@ skipping 76 matching lines @@
  * 1.4 eay - Fixed lh_doall so the function can call lh_delete 28/05/91
  *
  * 1.3 eay - Fixed a few lint problems 19/3/1991
  *
  * 1.2 eay - Fixed lh_doall problem 13/3/1991
  *
  * 1.1 eay - Added lh_doall
  *
  * 1.0 eay - First version
  */
+#include <limits.h>
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <openssl/crypto.h>
 #include <openssl/lhash.h>
 
 const char lh_version[]="lhash" OPENSSL_VERSION_PTEXT;
 
 #undef MIN_NODES 
 #define MIN_NODES       16
 #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 macros 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 the exact division operation):

[agl, 2013/11/04 17:29:30]

(I've reviewed this code in https://android-review.googlesource.com/68853)

+ *
+ *      (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);
 
 _LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
         {
         _LHASH *ret;
         int i;
 
         if ((ret=OPENSSL_malloc(sizeof(_LHASH))) == NULL)
@@ skipping 20 matching lines @@
         ret->num_comp_calls=0;
         ret->num_insert=0;
         ret->num_replace=0;
         ret->num_delete=0;
         ret->num_no_delete=0;
         ret->num_retrieve=0;
         ret->num_retrieve_miss=0;
         ret->num_hash_comps=0;
 
         ret->error=0;
+        LH_ITERATION_RESET(ret);
         return(ret);
 err1:
         OPENSSL_free(ret);
 err0:
         return(NULL);
         }
 
 void lh_free(_LHASH *lh)
         {
         unsigned int i;
@@ skipping 16 matching lines @@
         OPENSSL_free(lh);
         }
 
 void *lh_insert(_LHASH *lh, void *data)
         {
         unsigned long hash;
         LHASH_NODE *nn,**rn;
         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);
 
         if (*rn == NULL)
                 {
                 if ((nn=(LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL)
                         {
                         lh->error++;
                         return(NULL);
@@ skipping 34 matching lines @@
         else
                 {
                 nn= *rn;
                 *rn=nn->next;
                 ret=nn->data;
                 OPENSSL_free(nn);
                 lh->num_delete++;
                 }
 
         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);
         }
 
 void *lh_retrieve(_LHASH *lh, const void *data)
         {
         unsigned long hash;
         LHASH_NODE **rn;
         void *ret;
@@ skipping 16 matching lines @@
 
 static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
                           LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg)
         {
         int i;
         LHASH_NODE *a,*n;
 
         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--)
                 {
                 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 */
                         n=a->next;
                         if(use_arg)
                                 func_arg(a->data,arg);
                         else
                                 func(a->data);
                         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)
         {
         doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
         }
 
 void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
         {
         doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
@@ skipping 158 matching lines @@
                 ret^=v*v;
                 c++;
                 }
         return((ret>>16)^ret);
         }
 
 unsigned long lh_num_items(const _LHASH *lh)
         {
         return lh ? lh->num_items : 0;
         }