From 08086bd0f0dfbc08d121ccc6fbd27de9eaed55c7 Mon Sep 17 00:00:00 2001 From: "digit@chromium.org" Date: Tue, 5 Nov 2013 17:28:49 +0000 Subject: 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 --- openssl/crypto/conf/conf_api.c | 3 - openssl/crypto/lhash/lhash.c | 139 +++++++++++++++++++++++++++++++++++++-- openssl/crypto/lhash/lhash.h | 1 + openssl/crypto/objects/o_names.c | 6 -- openssl/crypto/objects/obj_dat.c | 1 - openssl/include/openssl/lhash.h | 1 + openssl/openssl.config | 11 ++++ openssl/ssl/ssl_sess.c | 3 - 8 files changed, 145 insertions(+), 20 deletions(-) (limited to 'openssl') 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 @@ 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/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 #include #include #include @@ -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/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 @@ 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/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 @@ 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/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 @@ 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/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 @@ 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/openssl/openssl.config b/openssl/openssl.config index 2088368..fee0a51 100644 --- a/openssl/openssl.config +++ b/openssl/openssl.config @@ -997,6 +997,7 @@ eng_dyn_dirs.patch \ 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 @@ crypto/x509/by_dir.c \ 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 @@ 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); } -- cgit v1.2.3