[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[tor-commits] [tor/master] scan-build: limit hashtable size so it always fits in SSIZE_MAX



commit 4d51dcda2fa75a3841e041ab7c3de325d73e2850
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date:   Sat Apr 19 12:39:14 2014 -0400

    scan-build: limit hashtable size so it always fits in SSIZE_MAX
    
    scan-build recognizes that in theory there could be a numeric overflow
    here.
    
    This can't numeric overflow can't trigger IRL, since in order to fill a
    hash table with more than P=402653189 buckets with a reasonable load
    factor of 0.5, we'd first have P/2 malloced objects to put in it--- and
    each of those would have to take take at least sizeof(void*) worth of
    malloc overhead plus sizeof(void*) content, which would run you out of
    address space anyway on a 32-bit system.
---
 src/ext/ht.h |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/src/ext/ht.h b/src/ext/ht.h
index e76b4aa..4a68673 100644
--- a/src/ext/ht.h
+++ b/src/ext/ht.h
@@ -303,14 +303,16 @@ ht_string_hash(const char *s)
 
 #define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn,    \
                     reallocfn, freefn)                                  \
+  /* Primes that aren't too far from powers of two. We stop at */       \
+  /* P=402653189 because P*sizeof(void*) is less than SSIZE_MAX */      \
+  /* even on a 32-bit platform. */                                      \
   static unsigned name##_PRIMES[] = {                                   \
     53, 97, 193, 389,                                                   \
     769, 1543, 3079, 6151,                                              \
     12289, 24593, 49157, 98317,                                         \
     196613, 393241, 786433, 1572869,                                    \
     3145739, 6291469, 12582917, 25165843,                               \
-    50331653, 100663319, 201326611, 402653189,                          \
-    805306457, 1610612741                                               \
+    50331653, 100663319, 201326611, 402653189                           \
   };                                                                    \
   static unsigned name##_N_PRIMES =                                     \
     (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0]));         \



_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits