Merge GH #1864 Use thread pool for XMSS signatures

5 files changed, 48 insertions, 172 deletions

diff --git a/src/lib/pubkey/xmss/xmss_privatekey.cpp b/src/lib/pubkey/xmss/xmss_privatekey.cpp
index 9ef2b5c9c..0cdcc57ce 100644
--- a/src/lib/pubkey/xmss/xmss_privatekey.cpp
+++ b/src/lib/pubkey/xmss/xmss_privatekey.cpp
@@ -11,15 +11,16 @@
  *       draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1
  *
  * (C) 2016,2017 Matthias Gierlings
+ * (C) 2019 Jack Lloyd
  *
  * Botan is released under the Simplified BSD License (see license.txt)
  **/
 
 #include <botan/xmss_privatekey.h>
 #include <botan/internal/xmss_signature_operation.h>
-#include <cmath>
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
-   #include <thread>
+
+#if defined(BOTAN_HAS_THREAD_UTILS)
+   #include <botan/internal/thread_pool.h>
 #endif
 
 namespace Botan {
@@ -30,10 +31,15 @@ XMSS_PrivateKey::XMSS_PrivateKey(const secure_vector<uint8_t>& raw_key)
      m_wots_priv_key(m_wots_params.oid(), m_public_seed),
      m_index_reg(XMSS_Index_Registry::get_instance())
    {
-   BOTAN_ASSERT(sizeof(size_t) >= std::ceil(
-      static_cast<float>(XMSS_PublicKey::m_xmss_params.tree_height()) / 8.f),
-      "System type \"size_t\" not big enough to support"
-      " leaf index.");
+   /*
+   The code requires sizeof(size_t) >= ceil(tree_height / 8)
+
+   Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte
+   size_t is sufficient for all defined parameters, or even a
+   (hypothetical) tree height 32, which would be extremely slow to
+   compute.
+   */
+   static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");
 
    if(raw_key.size() != size())
       {
@@ -92,23 +98,19 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
    BOTAN_ASSERT((start_idx % (1 << target_node_height)) == 0,
                 "Start index must be divisible by 2^{target node height}.");
 
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
+#if defined(BOTAN_HAS_THREAD_UTILS)
    // dertermine number of parallel tasks to split the tree_hashing into.
-   size_t split_level = std::min(
-      {
-      target_node_height,
-      static_cast<size_t>(
-         std::ceil(std::log2(XMSS_Tools::max_threads())))
-      });
+
+   Thread_Pool& thread_pool = Thread_Pool::global_instance();
+
+   const size_t split_level = std::min(target_node_height, thread_pool.worker_count());
 
    // skip parallelization overhead for leaf nodes.
    if(split_level == 0)
       {
-#endif
       secure_vector<uint8_t> result;
       tree_hash_subtree(result, start_idx, target_node_height, adrs);
       return result;
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
       }
 
    const size_t subtrees = static_cast<size_t>(1) << split_level;
@@ -125,8 +127,7 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
        secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));
    std::vector<XMSS_Address> node_addresses(subtrees, adrs);
    std::vector<XMSS_Hash> xmss_hash(subtrees, m_hash);
-   std::vector<std::thread> threads;
-   threads.reserve(subtrees);
+   std::vector<std::future<void>> work;
 
    // Calculate multiple subtrees in parallel.
    for(size_t i = 0; i < subtrees; i++)
@@ -138,24 +139,23 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
                                    XMSS_Address&,
                                    XMSS_Hash&);
 
-      threads.emplace_back(
-         std::thread(
-            static_cast<tree_hash_subtree_fn_t>(
-               &XMSS_PrivateKey::tree_hash_subtree),
-            this,
-            std::ref(nodes[i]),
-            start_idx + i * offs,
-            target_node_height - split_level,
-            std::ref(node_addresses[i]),
-            std::ref(xmss_hash[i])));
+      auto work_fn = static_cast<tree_hash_subtree_fn_t>(&XMSS_PrivateKey::tree_hash_subtree);
+
+      work.push_back(thread_pool.run(
+                        work_fn,
+                        this,
+                        std::ref(nodes[i]),
+                        start_idx + i * offs,
+                        target_node_height - split_level,
+                        std::ref(node_addresses[i]),
+                        std::ref(xmss_hash[i])));
       }
 
-   for(auto& t : threads)
+   for(auto& w : work)
       {
-      t.join();
+      w.get();
       }
-
-   threads.clear();
+   work.clear();
 
    // Parallelize the top tree levels horizontally
    while(level-- > 1)
@@ -165,6 +165,8 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
 
       for(size_t i = 0; i < (1U << level); i++)
          {
+         BOTAN_ASSERT_NOMSG(xmss_hash.size() > i);
+
          node_addresses[i].set_tree_height(target_node_height - (level + 1));
          node_addresses[i].set_tree_index(
             (node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);
@@ -176,10 +178,10 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
                                       const secure_vector<uint8_t>&,
                                       XMSS_Hash&);
 
-         threads.emplace_back(
-            std::thread(
-               static_cast<rnd_tree_hash_fn_t>(
-                  &XMSS_PrivateKey::randomize_tree_hash),
+         auto work_fn = static_cast<rnd_tree_hash_fn_t>(&XMSS_PrivateKey::randomize_tree_hash);
+
+         work.push_back(thread_pool.run(
+               work_fn,
                this,
                std::ref(nodes[i]),
                std::ref(ro_nodes[2 * i]),
@@ -188,11 +190,12 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
                std::ref(this->public_seed()),
                std::ref(xmss_hash[i])));
          }
-      for(auto &t : threads)
+
+      for(auto &w : work)
          {
-         t.join();
+         w.get();
          }
-      threads.clear();
+      work.clear();
       }
 
    // Avoid creation an extra thread to calculate root node.
@@ -205,6 +208,10 @@ XMSS_PrivateKey::tree_hash(size_t start_idx,
                        node_addresses[0],
                        this->public_seed());
    return nodes[0];
+#else
+   secure_vector<uint8_t> result;
+   tree_hash_subtree(result, start_idx, target_node_height, adrs);
+   return result;
 #endif
    }
 
diff --git a/src/lib/pubkey/xmss/xmss_signature.cpp b/src/lib/pubkey/xmss/xmss_signature.cpp
index 2ba8a1965..7e194a0eb 100644
--- a/src/lib/pubkey/xmss/xmss_signature.cpp
+++ b/src/lib/pubkey/xmss/xmss_signature.cpp
@@ -6,7 +6,6 @@
  **/
 
 #include <botan/internal/xmss_signature.h>
-#include <cmath>
 
 namespace Botan {
 
diff --git a/src/lib/pubkey/xmss/xmss_tools.cpp b/src/lib/pubkey/xmss/xmss_tools.cpp
deleted file mode 100644
index 585e14f2e..000000000
--- a/src/lib/pubkey/xmss/xmss_tools.cpp
+++ /dev/null
@@ -1,90 +0,0 @@
-/*
- * XMSS Tools
- * (C) 2017 Matthias Gierlings
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- **/
-
-#include <botan/xmss_tools.h>
-
-namespace Botan {
-
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
-
-size_t XMSS_Tools::max_threads()
-   {
-   static const size_t threads { bench_threads() };
-   return threads;
-   }
-
-size_t XMSS_Tools::bench_threads()
-   {
-   const size_t hardware_concurrency = std::thread::hardware_concurrency();
-
-   if(hardware_concurrency <= 1)
-      {
-      return 1;
-      }
-   const size_t BENCH_ITERATIONS = 1000;
-   std::vector<std::thread> threads;
-   threads.reserve(hardware_concurrency);
-   std::vector<std::chrono::nanoseconds> durations;
-
-   std::vector<size_t> concurrency { hardware_concurrency,
-                                     hardware_concurrency / 2 };
-
-   for(const auto& cc : concurrency)
-      {
-      std::vector<XMSS_Hash> hash(hardware_concurrency,
-                                  XMSS_Hash("SHA-256"));
-
-      const std::vector<uint8_t> buffer(hash[0].output_length());
-      std::vector<secure_vector<uint8_t>> data(
-          hardware_concurrency,
-          secure_vector<uint8_t>(hash[0].output_length()));
-      auto start = std::chrono::high_resolution_clock::now();
-      for(size_t i = 0; i < cc; ++i)
-         {
-         auto& hs = hash[i];
-         auto& d = data[i];
-
-         const size_t n_iters = BENCH_ITERATIONS * (hardware_concurrency / cc);
-         threads.emplace_back(std::thread([n_iters, &hs, &d]()
-               {
-               for(size_t n = 0; n < n_iters; n++)
-                  {
-                  hs.h(d, d, d);
-                  }
-               }
-            ));
-         }
-      durations.emplace_back(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - start));
-      for(auto& t : threads)
-         {
-         t.join();
-         }
-      threads.clear();
-      }
-
-      if(durations[0].count() < durations[1].count())
-         {
-#if defined(BOTAN_TEST_MODE)
-         return 4;
-#else
-         return concurrency[0];
-#endif
-         }
-      else
-         {
-#if defined(BOTAN_TEST_MODE)
-         return 4;
-#else
-         return concurrency[1];
-#endif
-         }
-  }
-
-#endif
-
-}
-
diff --git a/src/lib/pubkey/xmss/xmss_tools.h b/src/lib/pubkey/xmss/xmss_tools.h
index 65c4a83a7..bbd31fd9f 100644
--- a/src/lib/pubkey/xmss/xmss_tools.h
+++ b/src/lib/pubkey/xmss/xmss_tools.h
@@ -13,12 +13,6 @@
 #include <iterator>
 #include <type_traits>
 
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
-   #include <thread>
-   #include <chrono>
-   #include <botan/xmss_hash.h>
-#endif
-
 namespace Botan {
 
 /**
@@ -59,44 +53,8 @@ class XMSS_Tools final
                 void>::type>
       static void concat(secure_vector<uint8_t>& target, const T& src, size_t len);
 
-      /**
-       * Not a public API function - will be removed in a future release.
-       *
-       * Determines the maximum number of threads to be used
-       * efficiently, based on runtime timining measurements. Ideally the
-       * result will correspond to the physical number of cores. On systems
-       * supporting simultaneous multi threading (SMT)
-       * std::thread::hardware_concurrency() usually reports a supported
-       * number of threads which is bigger (typically by a factor of 2) than
-       * the number of physical cores available. Using more threads than
-       * physically available cores for computationally intesive tasks
-       * resulted in slowdowns compared to using a number of threads equal to
-       * the number of physical cores on test systems. This function is a
-       * temporary workaround to prevent performance degradation due to
-       * overstressing the CPU with too many threads.
-       *
-       * @return Presumed number of physical cores based on timing measurements.
-       **/
-      static size_t max_threads(); // TODO: Remove max_threads() and use
-                                   // Botan::CPUID once proper plattform
-                                   // independent detection of physical cores is
-                                   // available.
-
    private:
       XMSS_Tools();
-      /**
-       * Measures the time t1 it takes to calculate hashes using
-       * std::thread::hardware_concurrency() many threads and the time t2
-       * calculating the same number of hashes using
-       * std::thread::hardware_concurrency() / 2 threads.
-       *
-       * @return std::thread::hardware_concurrency() if t1 < t2
-       *         std::thread::hardware_concurrency() / 2 otherwise.
-       **/
-      static size_t bench_threads(); // TODO: Remove bench_threads() and use
-                                     // Botan::CPUID once proper plattform
-                                     // independent detection of physical cores
-                                     // is //available.
    };
 
 template <typename T, typename U>
diff --git a/src/lib/utils/thread_utils/thread_pool.h b/src/lib/utils/thread_utils/thread_pool.h
index d48975090..974b62d79 100644
--- a/src/lib/utils/thread_utils/thread_pool.h
+++ b/src/lib/utils/thread_utils/thread_pool.h
@@ -40,6 +40,8 @@ class BOTAN_TEST_API Thread_Pool
 
       void shutdown();
 
+      size_t worker_count() const { return m_workers.size(); }
+
       Thread_Pool(const Thread_Pool&) = delete;
       Thread_Pool& operator=(const Thread_Pool&) = delete;