Document that lhash isn't thread safe under any circumstances and
authorPauli <paul.dale@oracle.com>
Thu, 28 Sep 2017 00:09:18 +0000 (10:09 +1000)
committerPauli <paul.dale@oracle.com>
Sun, 8 Oct 2017 21:50:18 +0000 (07:50 +1000)
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)

crypto/lhash/lh_stats.c
crypto/lhash/lhash.c
crypto/lhash/lhash_lcl.h
doc/man3/OPENSSL_LH_COMPFUNC.pod
doc/man3/OPENSSL_LH_stats.pod

index 5586afa..65b91e1 100644 (file)
@@ -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)
index 8f28c48..2852881 100644 (file)
@@ -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)
index 64d3134..78691eb 100644 (file)
@@ -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;
 };
index 1e2e5d5..06908a4 100644 (file)
@@ -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
index 49351f4..231485a 100644 (file)
@@ -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