sh implementation to avoid unwanted resizes during iteration.
This is a port of the following AOSP patch:
https://android-review.googlesource.com/#/c/68853/
It fixes a bug that happens when trying to delete items from
a lhash table while it is being iterated over with a call
to lh_doall or lh_doall_arg.
It looks like the source tree is slightly out-of-sync from
the state of running ./import_from_android.sh, but the differences
are minor / not significant.
This patch tries to fix a P1 bug, so doesn't try to address this
(the differences have been removed for easier reviewing).
BUG=298606
R=agl@chromium.org,rsleevi@chromium.org,wtc@chromium.org
TBR=darin@chromium.org
Review URL: https://codereview.chromium.org/59793002
git-svn-id: http://src.chromium.org/svn/trunk/deps/third_party/openssl@233017 4ff67af0-8c30-449e-8e8b-ad334ec8d88c
diff --git a/README.chromium b/README.chromium
index 552df66..67221e1 100644
--- a/README.chromium
+++ b/README.chromium
@@ -184,6 +184,11 @@
Add API so that channel ID private key can be set only after verifying the
remote server supports channel IDs.
+ fix_lhash_iteration.patch
+ Fix a crash that happens when OpenSSL tries to delete items from a lhash
+ table that is being iterated over. This happens in certain rare cases
+ when SSL_CTX_flush_sessions() is called. See http://crbug.com/298606
+
**************************************************************************
Adding new Chromium patches:
diff --git a/openssl/crypto/conf/conf_api.c b/openssl/crypto/conf/conf_api.c
index f5fcbb9..9a37bd4 100644
--- a/openssl/crypto/conf/conf_api.c
+++ b/openssl/crypto/conf/conf_api.c
@@ -225,9 +225,6 @@
{
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/openssl/crypto/lhash/lhash.c b/openssl/crypto/lhash/lhash.c
index 47f7480..e5b3cdf 100644
--- a/openssl/crypto/lhash/lhash.c
+++ b/openssl/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 @@
#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)
diff --git a/openssl/crypto/lhash/lhash.h b/openssl/crypto/lhash/lhash.h
index e7d8763..75386f2 100644
--- a/openssl/crypto/lhash/lhash.h
+++ b/openssl/crypto/lhash/lhash.h
@@ -163,6 +163,7 @@
unsigned long num_hash_comps;
int error;
+ int iteration_state;
} _LHASH; /* Do not use _LHASH directly, use LHASH_OF
* and friends */
diff --git a/openssl/crypto/objects/o_names.c b/openssl/crypto/objects/o_names.c
index 4a548c2..4e18045 100644
--- a/openssl/crypto/objects/o_names.c
+++ b/openssl/crypto/objects/o_names.c
@@ -350,13 +350,9 @@
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 @@
names_lh=NULL;
name_funcs_stack = NULL;
}
- else
- lh_OBJ_NAME_down_load(names_lh)=down_load;
}
diff --git a/openssl/crypto/objects/obj_dat.c b/openssl/crypto/objects/obj_dat.c
index 8a342ba..ef0512a 100644
--- a/openssl/crypto/objects/obj_dat.c
+++ b/openssl/crypto/objects/obj_dat.c
@@ -227,7 +227,6 @@
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/openssl/include/openssl/lhash.h b/openssl/include/openssl/lhash.h
index e7d8763..75386f2 100644
--- a/openssl/include/openssl/lhash.h
+++ b/openssl/include/openssl/lhash.h
@@ -163,6 +163,7 @@
unsigned long num_hash_comps;
int error;
+ int iteration_state;
} _LHASH; /* Do not use _LHASH directly, use LHASH_OF
* and friends */
diff --git a/openssl/openssl.config b/openssl/openssl.config
index 2088368..fee0a51 100644
--- a/openssl/openssl.config
+++ b/openssl/openssl.config
@@ -997,6 +997,7 @@
fix_clang_build.patch \
x509_hash_name_algorithm_change.patch \
reduce_client_hello_size.patch \
+fix_lhash_iteration.patch \
"
OPENSSL_PATCHES_progs_SOURCES="\
@@ -1060,3 +1061,13 @@
OPENSSL_PATCHES_reduce_client_hello_size_SOURCES="\
ssl/t1_lib.c \
"
+
+OPENSSL_PATCHES_fix_lhash_iteration_SOURCES="\
+crypto/conf/conf_api.c
+crypto/lhash/lhash.c
+crypto/lhash/lhash.h
+crypto/objects/o_names.c
+crypto/objects/obj_dat.c
+include/openssl/lhash.h
+ssl/ssl_sess.c
+"
diff --git a/openssl/ssl/ssl_sess.c b/openssl/ssl/ssl_sess.c
index 85360af..4f6af55 100644
--- a/openssl/ssl/ssl_sess.c
+++ b/openssl/ssl/ssl_sess.c
@@ -999,11 +999,8 @@
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);
}
