Document that lhash isn't thread safe under any circumstances and

indicate the level of locking required for various operations.

Remove the lock and atomics from the lhash code.  These we're not complete
or adequate.

Refer to #4418 and #4427 for details.

Reviewed-by: Rich Salz <rsalz@openssl.org>
Reviewed-by: Ben Kaduk <kaduk@mit.edu>
Reviewed-by: Andy Polyakov <appro@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/4429)

diff --git a/crypto/lhash/lh_stats.c b/crypto/lhash/lh_stats.c
index 5586afa0d8b346a79937042b59849883c34835b1..65b91e1ef415e620b68f127f6f5fe6074d23b0ea 100644 (file)
--- a/crypto/lhash/lh_stats.c
+++ b/crypto/lhash/lh_stats.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -61,35 +61,22 @@ void OPENSSL_LH_node_usage_stats(const OPENSSL_LHASH *lh, FILE *fp)
 
 void OPENSSL_LH_stats_bio(const OPENSSL_LHASH *lh, BIO *out)
 {
-    OPENSSL_LHASH *lh_mut = (OPENSSL_LHASH *) lh;
-    int ret;
-
     BIO_printf(out, "num_items             = %lu\n", lh->num_items);
-    BIO_printf(out, "num_nodes             = %u\n", lh->num_nodes);
-    BIO_printf(out, "num_alloc_nodes       = %u\n", lh->num_alloc_nodes);
+    BIO_printf(out, "num_nodes             = %u\n",  lh->num_nodes);
+    BIO_printf(out, "num_alloc_nodes       = %u\n",  lh->num_alloc_nodes);
     BIO_printf(out, "num_expands           = %lu\n", lh->num_expands);
     BIO_printf(out, "num_expand_reallocs   = %lu\n", lh->num_expand_reallocs);
     BIO_printf(out, "num_contracts         = %lu\n", lh->num_contracts);
-    BIO_printf(out, "num_contract_reallocs = %lu\n",
-               lh->num_contract_reallocs);
-    CRYPTO_atomic_add(&lh_mut->num_hash_calls, 0, &ret,
-                      lh->retrieve_stats_lock);
-    BIO_printf(out, "num_hash_calls        = %d\n", ret);
-    CRYPTO_atomic_add(&lh_mut->num_comp_calls, 0, &ret,
-                      lh->retrieve_stats_lock);
-    BIO_printf(out, "num_comp_calls        = %d\n", ret);
+    BIO_printf(out, "num_contract_reallocs = %lu\n", lh->num_contract_reallocs);
+    BIO_printf(out, "num_hash_calls        = %lu\n", lh->num_hash_calls);
+    BIO_printf(out, "num_comp_calls        = %lu\n", lh->num_comp_calls);
     BIO_printf(out, "num_insert            = %lu\n", lh->num_insert);
     BIO_printf(out, "num_replace           = %lu\n", lh->num_replace);
     BIO_printf(out, "num_delete            = %lu\n", lh->num_delete);
     BIO_printf(out, "num_no_delete         = %lu\n", lh->num_no_delete);
-    CRYPTO_atomic_add(&lh_mut->num_retrieve, 0, &ret, lh->retrieve_stats_lock);
-    BIO_printf(out, "num_retrieve          = %d\n", ret);
-    CRYPTO_atomic_add(&lh_mut->num_retrieve_miss, 0, &ret,
-                      lh->retrieve_stats_lock);
-    BIO_printf(out, "num_retrieve_miss     = %d\n", ret);
-    CRYPTO_atomic_add(&lh_mut->num_hash_comps, 0, &ret,
-                      lh->retrieve_stats_lock);
-    BIO_printf(out, "num_hash_comps        = %d\n", ret);
+    BIO_printf(out, "num_retrieve          = %lu\n", lh->num_retrieve);
+    BIO_printf(out, "num_retrieve_miss     = %lu\n", lh->num_retrieve_miss);
+    BIO_printf(out, "num_hash_comps        = %lu\n", lh->num_hash_comps);
 }
 
 void OPENSSL_LH_node_stats_bio(const OPENSSL_LHASH *lh, BIO *out)

diff --git a/crypto/lhash/lhash.c b/crypto/lhash/lhash.c
index 8f28c48c4d1f756c972de313b128fcd839f06809..28528817a1f9ad5411c7637115c280a6e8b834c2 100644 (file)
--- a/crypto/lhash/lhash.c
+++ b/crypto/lhash/lhash.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -32,8 +32,6 @@ OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
         return NULL;
     if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL)
         goto err;
-    if ((ret->retrieve_stats_lock = CRYPTO_THREAD_lock_new()) == NULL)
-        goto err;
     ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
     ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
     ret->num_nodes = MIN_NODES / 2;
@@ -41,7 +39,7 @@ OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
     ret->pmax = MIN_NODES / 2;
     ret->up_load = UP_LOAD;
     ret->down_load = DOWN_LOAD;
-    return (ret);
+    return ret;
 
 err:
     OPENSSL_free(ret->b);
@@ -65,7 +63,6 @@ void OPENSSL_LH_free(OPENSSL_LHASH *lh)
             n = nn;
         }
     }
-    CRYPTO_THREAD_lock_free(lh->retrieve_stats_lock);
     OPENSSL_free(lh->b);
     OPENSSL_free(lh);
 }
@@ -85,7 +82,7 @@ void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
     if (*rn == NULL) {
         if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
             lh->error++;
-            return (NULL);
+            return NULL;
         }
         nn->data = data;
         nn->next = NULL;
@@ -95,12 +92,11 @@ void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
         lh->num_insert++;
         lh->num_items++;
     } else {                    /* replace same key */
-
         ret = (*rn)->data;
         (*rn)->data = data;
         lh->num_replace++;
     }
-    return (ret);
+    return ret;
 }
 
 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
@@ -114,7 +110,7 @@ void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
 
     if (*rn == NULL) {
         lh->num_no_delete++;
-        return (NULL);
+        return NULL;
     } else {
         nn = *rn;
         *rn = nn->next;
@@ -128,7 +124,7 @@ void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
         contract(lh);
 
-    return (ret);
+    return ret;
 }
 
 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
@@ -136,17 +132,16 @@ void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
     unsigned long hash;
     OPENSSL_LH_NODE **rn;
     void *ret;
-    int scratch;
 
     lh->error = 0;
     rn = getrn(lh, data, &hash);
 
     if (*rn == NULL) {
-        CRYPTO_atomic_add(&lh->num_retrieve_miss, 1, &scratch, lh->retrieve_stats_lock);
+        lh->num_retrieve_miss++;
         return NULL;
     } else {
         ret = (*rn)->data;
-        CRYPTO_atomic_add(&lh->num_retrieve, 1, &scratch, lh->retrieve_stats_lock);
+        lh->num_retrieve++;
     }
     return ret;
 }
@@ -274,10 +269,9 @@ static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
     OPENSSL_LH_NODE **ret, *n1;
     unsigned long hash, nn;
     OPENSSL_LH_COMPFUNC cf;
-    int scratch;
 
     hash = (*(lh->hash)) (data);
-    CRYPTO_atomic_add(&lh->num_hash_calls, 1, &scratch, lh->retrieve_stats_lock);
+    lh->num_hash_calls++;
     *rhash = hash;
 
     nn = hash % lh->pmax;
@@ -287,17 +281,17 @@ static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
     cf = lh->comp;
     ret = &(lh->b[(int)nn]);
     for (n1 = *ret; n1 != NULL; n1 = n1->next) {
-        CRYPTO_atomic_add(&lh->num_hash_comps, 1, &scratch, lh->retrieve_stats_lock);
+        lh->num_hash_comps++;
         if (n1->hash != hash) {
             ret = &(n1->next);
             continue;
         }
-        CRYPTO_atomic_add(&lh->num_comp_calls, 1, &scratch, lh->retrieve_stats_lock);
+        lh->num_comp_calls++;
         if (cf(n1->data, data) == 0)
             break;
         ret = &(n1->next);
     }
-    return (ret);
+    return ret;
 }
 
 /*
@@ -313,7 +307,7 @@ unsigned long OPENSSL_LH_strhash(const char *c)
     int r;
 
     if ((c == NULL) || (*c == '\0'))
-        return (ret);
+        return ret;
 
     n = 0x100;
     while (*c) {
@@ -325,7 +319,7 @@ unsigned long OPENSSL_LH_strhash(const char *c)
         ret ^= v * v;
         c++;
     }
-    return ((ret >> 16) ^ ret);
+    return (ret >> 16) ^ ret;
 }
 
 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)

diff --git a/crypto/lhash/lhash_lcl.h b/crypto/lhash/lhash_lcl.h
index 64d3134fc108eed7b86563244c65e54487325b85..78691eb622fa7b66d2c941a802d41a6eedcb9809 100644 (file)
--- a/crypto/lhash/lhash_lcl.h
+++ b/crypto/lhash/lhash_lcl.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -18,13 +18,6 @@ struct lhash_st {
     OPENSSL_LH_NODE **b;
     OPENSSL_LH_COMPFUNC comp;
     OPENSSL_LH_HASHFUNC hash;
-    /*
-     * some stats are updated on lookup, which callers aren't expecting to have
-     * to take an exclusive lock around. This lock protects them on platforms
-     * without atomics, and their types are int rather than unsigned long below
-     * so they can be adjusted with CRYPTO_atomic_add.
-     */
-    CRYPTO_RWLOCK *retrieve_stats_lock;
     unsigned int num_nodes;
     unsigned int num_alloc_nodes;
     unsigned int p;
@@ -36,14 +29,14 @@ struct lhash_st {
     unsigned long num_expand_reallocs;
     unsigned long num_contracts;
     unsigned long num_contract_reallocs;
-    int num_hash_calls;
-    int num_comp_calls;
+    unsigned long num_hash_calls;
+    unsigned long num_comp_calls;
     unsigned long num_insert;
     unsigned long num_replace;
     unsigned long num_delete;
     unsigned long num_no_delete;
-    int num_retrieve;
-    int num_retrieve_miss;
-    int num_hash_comps;
+    unsigned long num_retrieve;
+    unsigned long num_retrieve_miss;
+    unsigned long num_hash_comps;
     int error;
 };

diff --git a/doc/man3/OPENSSL_LH_COMPFUNC.pod b/doc/man3/OPENSSL_LH_COMPFUNC.pod
index 1e2e5d594f115e7525df8c299fe702508b3ed13c..06908a49fc8322f106acef54e5dfc4755569e443 100644 (file)
--- a/doc/man3/OPENSSL_LH_COMPFUNC.pod
+++ b/doc/man3/OPENSSL_LH_COMPFUNC.pod
@@ -184,6 +184,13 @@ audit/verify and also opens the window of opportunity for stack
 corruption and other hard-to-find bugs.  It also, apparently, violates
 ANSI-C.
 
+The LHASH code is not thread safe. All updating operations must be
+performed under a write lock. All retrieve operations should be performed
+under a read lock, I<unless> accurate usage statistics are desired.
+In which case, a write lock should be used for retrieve operations
+as well.  For output of the usage statistics, using the functions from
+L<OPENSSL_LH_stats(3)>, a read lock suffices.
+
 The LHASH code regards table entries as constant data.  As such, it
 internally represents lh_insert()'d items with a "const void *"
 pointer type.  This is why callbacks such as those used by lh_doall()
@@ -229,7 +236,7 @@ type checking.
 
 =head1 COPYRIGHT
 
-Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
+Copyright 2000-2017 The OpenSSL Project Authors. All Rights Reserved.
 
 Licensed under the OpenSSL license (the "License").  You may not use
 this file except in compliance with the License.  You can obtain a copy

diff --git a/doc/man3/OPENSSL_LH_stats.pod b/doc/man3/OPENSSL_LH_stats.pod
index 49351f4dcee3b3e2a953037760819273e1d19765..231485ad363fac95dd2d188b262befa17914f2b4 100644 (file)
--- a/doc/man3/OPENSSL_LH_stats.pod
+++ b/doc/man3/OPENSSL_LH_stats.pod
@@ -46,13 +46,19 @@ are the same as the above, except that the output goes to a B<BIO>.
 
 These functions do not return values.
 
+=head1 NOTE
+
+These calls should be made under a read lock. Refer to
+L<OPENSSL_LH_COMPFUNC(3)/NOTE> for more details about the locks required
+when using the LHASH data structure.
+
 =head1 SEE ALSO
 
-L<bio(7)>, L<LHASH(3)>
+L<bio(7)>, L<OPENSSL_LH_COMPFUNC(3)>
 
 =head1 COPYRIGHT
 
-Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
+Copyright 2000-2017 The OpenSSL Project Authors. All Rights Reserved.
 
 Licensed under the OpenSSL license (the "License").  You may not use
 this file except in compliance with the License.  You can obtain a copy