Add CuckooCache implementation and replace the sigcache map_type with it

SQUASHME: Change cuckoocache to only work for powers of two, to avoid mod operator
SQUASHME: Update Documentation and simplify logarithm logic
SQUASHME: OSX Build Errors
SQUASHME: minor Feedback from sipa + bluematt
SQUASHME: DOCONLY: Clarify a few comments.

2 files changed, 45 insertions, 41 deletions

diff --git a/src/script/sigcache.cpp b/src/script/sigcache.cpp
index bdc0bfdc1c..b78d7b607f 100644
--- a/src/script/sigcache.cpp
+++ b/src/script/sigcache.cpp
@@ -11,20 +11,29 @@
 #include "uint256.h"
 #include "util.h"
 
+#include "cuckoocache.h"
 #include <boost/thread.hpp>
-#include <boost/unordered_set.hpp>
 
 namespace {
 
 /**
  * We're hashing a nonce into the entries themselves, so we don't need extra
  * blinding in the set hash computation.
+ *
+ * This may exhibit platform endian dependent behavior but because these are
+ * nonced hashes (random) and this state is only ever used locally it is safe.
+ * All that matters is local consistency.
  */
-class CSignatureCacheHasher
+class SignatureCacheHasher
 {
 public:
-    size_t operator()(const uint256& key) const {
-        return key.GetCheapHash();
+    template <uint8_t hash_select>
+    uint32_t operator()(const uint256& key) const
+    {
+        static_assert(hash_select <8, "SignatureCacheHasher only has 8 hashes available.");
+        uint32_t u;
+        std::memcpy(&u, key.begin()+4*hash_select, 4);
+        return u;
     }
 };
 
@@ -38,11 +47,10 @@ class CSignatureCache
 private:
      //! Entries are SHA256(nonce || signature hash || public key || signature):
     uint256 nonce;
-    typedef boost::unordered_set<uint256, CSignatureCacheHasher> map_type;
+    typedef CuckooCache::cache<uint256, SignatureCacheHasher> map_type;
     map_type setValid;
     boost::shared_mutex cs_sigcache;
 
-
 public:
     CSignatureCache()
     {
@@ -56,58 +64,51 @@ public:
     }
 
     bool
-    Get(const uint256& entry)
+    Get(const uint256& entry, const bool erase)
     {
         boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
-        return setValid.count(entry);
+        return setValid.contains(entry, erase);
     }
 
-    void Erase(const uint256& entry)
+    void Set(uint256& entry)
     {
         boost::unique_lock<boost::shared_mutex> lock(cs_sigcache);
-        setValid.erase(entry);
+        setValid.insert(entry);
     }
-
-    void Set(const uint256& entry)
+    uint32_t setup_bytes(size_t n)
     {
-        size_t nMaxCacheSize = GetArg("-maxsigcachesize", DEFAULT_MAX_SIG_CACHE_SIZE) * ((size_t) 1 << 20);
-        if (nMaxCacheSize <= 0) return;
-
-        boost::unique_lock<boost::shared_mutex> lock(cs_sigcache);
-        while (memusage::DynamicUsage(setValid) > nMaxCacheSize)
-        {
-            map_type::size_type s = GetRand(setValid.bucket_count());
-            map_type::local_iterator it = setValid.begin(s);
-            if (it != setValid.end(s)) {
-                setValid.erase(*it);
-            }
-        }
-
-        setValid.insert(entry);
+        return setValid.setup_bytes(n);
     }
 };
 
+/* In previous versions of this code, signatureCache was a local static variable
+ * in CachingTransactionSignatureChecker::VerifySignature.  We initialize
+ * signatureCache outside of VerifySignature to avoid the atomic operation per
+ * call overhead associated with local static variables even though
+ * signatureCache could be made local to VerifySignature.
+*/
+static CSignatureCache signatureCache;
 }
 
-bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const
+// To be called once in AppInit2/TestingSetup to initialize the signatureCache
+void InitSignatureCache()
 {
-    static CSignatureCache signatureCache;
+    size_t nMaxCacheSize = GetArg("-maxsigcachesize", DEFAULT_MAX_SIG_CACHE_SIZE) * ((size_t) 1 << 20);
+    if (nMaxCacheSize <= 0) return;
+    size_t nElems = signatureCache.setup_bytes(nMaxCacheSize);
+    LogPrintf("Using %zu MiB out of %zu requested for signature cache, able to store %zu elements\n",
+            (nElems*sizeof(uint256)) >>20, nMaxCacheSize>>20, nElems);
+}
 
+bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const
+{
     uint256 entry;
     signatureCache.ComputeEntry(entry, sighash, vchSig, pubkey);
-
-    if (signatureCache.Get(entry)) {
-        if (!store) {
-            signatureCache.Erase(entry);
-        }
+    if (signatureCache.Get(entry, !store))
         return true;
-    }
-
     if (!TransactionSignatureChecker::VerifySignature(vchSig, pubkey, sighash))
         return false;
-
-    if (store) {
+    if (store)
         signatureCache.Set(entry);
-    }
     return true;
 }
diff --git a/src/script/sigcache.h b/src/script/sigcache.h
index 44551ec2bc..5243fc0a42 100644
--- a/src/script/sigcache.h
+++ b/src/script/sigcache.h
@@ -10,9 +10,10 @@
 
 #include <vector>
 
-// DoS prevention: limit cache size to less than 40MB (over 500000
-// entries on 64-bit systems).
-static const unsigned int DEFAULT_MAX_SIG_CACHE_SIZE = 40;
+// DoS prevention: limit cache size to 32MB (over 1000000 entries on 64-bit
+// systems). Due to how we count cache size, actual memory usage is slightly
+// more (~32.25 MB)
+static const unsigned int DEFAULT_MAX_SIG_CACHE_SIZE = 32;
 
 class CPubKey;
 
@@ -27,4 +28,6 @@ public:
     bool VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const;
 };
 
+void InitSignatureCache();
+
 #endif // BITCOIN_SCRIPT_SIGCACHE_H