Index: openssl/crypto/lhash/lhash.c |
=================================================================== |
--- openssl/crypto/lhash/lhash.c (revision 232952) |
+++ openssl/crypto/lhash/lhash.c (working copy) |
@@ -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 @@ |
#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 @@ |
ret->num_hash_comps=0; |
ret->error=0; |
+ LH_ITERATION_RESET(ret); |
return(ret); |
err1: |
OPENSSL_free(ret); |
@@ -183,7 +292,10 @@ |
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 @@ |
} |
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 @@ |
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 @@ |
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 @@ |
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) |