[3/3] kudu git commit: KUDU-1992. striped64: don't heap-allocate the threadlocal hashcode

[to...@apache.org]

KUDU-1992. striped64: don't heap-allocate the threadlocal hashcode

KUDU-1992 describes a bug in which the destructor of one threadlocal
object ended up referring to another threadlocal object. Specifically, a
threadlocal cached block destructor ended up incrementing a metric which
was implemented by a LongAdder (inheriting from Striped64). The
LongAdder uses a threadlocal hashcode to avoid contention.

In the crash described in the bug, the striped64's TLS hashcode was
destructed before the other destructor ran, causing a
heap-use-after-free.

This patch should fix the issue by making the threadlocal hashcode be a
POD threadlocal rather than a pointer to a heap-allocated object. Thus
there is no destructor to run, and no chance that the destruction order
can cause this crash.

This fix seemed simpler than trying to ensure some specific ordering of
threadlocal destructors (eg by assigning destructor priorities or adding
some kind of dependency graph).

Before the patch, I was able to reproduce the crash 2/1000 times running
RaftConsensusITest.TestAutoCreateReplica. After the patch, I ran it 5000
times with no failures.

Change-Id: I2d4e5264134c70ced434c3ae8da5866a151464d5
Reviewed-on: http://gerrit.cloudera.org:8080/6791
Reviewed-by: Adar Dembo <ad...@cloudera.com>
Tested-by: Kudu Jenkins


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/579cb0b1
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/579cb0b1
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/579cb0b1

Branch: refs/heads/master
Commit: 579cb0b145ad141cd3b49324406c85fe2ca96b15
Parents: d07ecd6
Author: Todd Lipcon <to...@apache.org>
Authored: Wed May 3 14:33:50 2017 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Thu May 4 00:30:09 2017 +0000

----------------------------------------------------------------------
 src/kudu/util/striped64.cc | 40 +++++++++++++++++++++-------------------
 src/kudu/util/striped64.h  | 14 +++++---------
 2 files changed, 26 insertions(+), 28 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/579cb0b1/src/kudu/util/striped64.cc
----------------------------------------------------------------------
diff --git a/src/kudu/util/striped64.cc b/src/kudu/util/striped64.cc
index a0951c7..8343177 100644
--- a/src/kudu/util/striped64.cc
+++ b/src/kudu/util/striped64.cc
@@ -15,27 +15,18 @@
 // specific language governing permissions and limitations
 // under the License.
 
+#include "kudu/util/striped64.h"
+
 #include "kudu/util/monotime.h"
 #include "kudu/util/random.h"
-#include "kudu/util/striped64.h"
 #include "kudu/util/threadlocal.h"
 
-using kudu::striped64::internal::HashCode;
 using kudu::striped64::internal::Cell;
 
 namespace kudu {
 
 namespace striped64 {
 namespace internal {
-//
-// HashCode
-//
-
-HashCode::HashCode() {
-  Random r((MonoTime::Now() - MonoTime::Min()).ToNanoseconds());
-  const uint64_t hash = r.Next64();
-  code_ = (hash == 0) ? 1 : hash;  // Avoid zero to allow xorShift rehash
-}
 
 //
 // Cell
@@ -50,8 +41,8 @@ Cell::Cell()
 //
 // Striped64
 //
+__thread uint64_t Striped64::tls_hashcode_ = 0;
 const uint32_t Striped64::kNumCpus = sysconf(_SC_NPROCESSORS_ONLN);
-DEFINE_STATIC_THREAD_LOCAL(HashCode, Striped64, hashcode_);
 
 Striped64::Striped64()
     : busy_(false),
@@ -60,13 +51,25 @@ Striped64::Striped64()
       num_cells_(0) {
 }
 
+uint64_t Striped64::get_tls_hashcode() {
+  if (PREDICT_FALSE(tls_hashcode_ == 0)) {
+    Random r((MonoTime::Now() - MonoTime::Min()).ToNanoseconds());
+    const uint64_t hash = r.Next64();
+    // Avoid zero to allow xorShift rehash, and because 0 indicates an unset
+    // hashcode above.
+    tls_hashcode_ = (hash == 0) ? 1 : hash;
+  }
+  return tls_hashcode_;
+}
+
+
 Striped64::~Striped64() {
   // Cell is a POD, so no need to destruct each one.
   free(cell_buffer_);
 }
 
-void Striped64::RetryUpdate(int64_t x, Rehash contention) {
-  uint64_t h = hashcode_->code_;
+void Striped64::RetryUpdate(int64_t x, Rehash to_rehash) {
+  uint64_t h = get_tls_hashcode();
   // There are three operations in this loop.
   //
   // 1. Try to add to the Cell hash table entry for the thread if the table exists.
@@ -79,9 +82,9 @@ void Striped64::RetryUpdate(int64_t x, Rehash contention) {
   while (true) {
     int32_t n = base::subtle::Acquire_Load(&num_cells_);
     if (n > 0) {
-      if (contention == kRehash) {
+      if (to_rehash == kRehash) {
         // CAS failed already, rehash before trying to increment.
-        contention = kNoRehash;
+        to_rehash = kNoRehash;
       } else {
         Cell *cell = &(cells_[(n - 1) & h]);
         int64_t v = cell->value_.Load();
@@ -124,7 +127,7 @@ void Striped64::RetryUpdate(int64_t x, Rehash contention) {
     }
   }
   // Record index for next time
-  hashcode_->code_ = h;
+  tls_hashcode_ = h;
 }
 
 void Striped64::InternalReset(int64_t initialValue) {
@@ -136,12 +139,11 @@ void Striped64::InternalReset(int64_t initialValue) {
 }
 
 void LongAdder::IncrementBy(int64_t x) {
-  INIT_STATIC_THREAD_LOCAL(HashCode, hashcode_);
   // Use hash table if present. If that fails, call RetryUpdate to rehash and retry.
   // If no hash table, try to CAS the base counter. If that fails, RetryUpdate to init the table.
   const int32_t n = base::subtle::Acquire_Load(&num_cells_);
   if (n > 0) {
-    Cell *cell = &(cells_[(n - 1) & hashcode_->code_]);
+    Cell *cell = &(cells_[(n - 1) & get_tls_hashcode()]);
     DCHECK_EQ(0, reinterpret_cast<const uintptr_t>(cell) & (sizeof(Cell) - 1))
         << " unaligned Cell not allowed for Striped64" << std::endl;
     const int64_t old = cell->value_.Load();

http://git-wip-us.apache.org/repos/asf/kudu/blob/579cb0b1/src/kudu/util/striped64.h
----------------------------------------------------------------------
diff --git a/src/kudu/util/striped64.h b/src/kudu/util/striped64.h
index a7ffec7..a3b829b 100644
--- a/src/kudu/util/striped64.h
+++ b/src/kudu/util/striped64.h
@@ -29,12 +29,6 @@ class Striped64;
 namespace striped64 {
 namespace internal {
 
-struct HashCode {
- public:
-  HashCode();
-  uint64_t code_;
-};
-
 #define ATOMIC_INT_SIZE sizeof(AtomicInt<int64_t>)
 // Padded POD container for AtomicInt. This prevents false sharing of cache lines.
 class Cell {
@@ -137,12 +131,14 @@ class Striped64 {
   striped64::internal::Cell* cells_;
   int32_t num_cells_;
 
+ protected:
+  static uint64_t get_tls_hashcode();
+
+ private:
   // Static hash code per-thread. Shared across all instances to limit thread-local pollution.
   // Also, if a thread hits a collision on one Striped64, it's also likely to collide on
   // other Striped64s too.
-  DECLARE_STATIC_THREAD_LOCAL(striped64::internal::HashCode, hashcode_);
-
- private:
+  static __thread uint64_t tls_hashcode_;
 
   // Number of CPUs, to place bound on table size.
   static const uint32_t kNumCpus;