quickstep-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From zu...@apache.org
Subject [18/30] incubator-quickstep git commit: Fixed the deadlock when loading while evicting. (#196)
Date Thu, 05 May 2016 06:16:54 GMT
Fixed the deadlock when loading while evicting. (#196)

Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/30a15776
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/30a15776
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/30a15776

Branch: refs/heads/master
Commit: 30a157769406f76fc91ccd619b14db24bcd6e585
Parents: 9372b94
Author: Zuyu ZHANG <zuyu@users.noreply.github.com>
Authored: Wed Apr 27 22:59:25 2016 -0700
Committer: Zuyu Zhang <zzhang@pivotal.io>
Committed: Wed May 4 23:15:35 2016 -0700

----------------------------------------------------------------------
 storage/StorageManager.cpp     | 20 ++++++++++++------
 utility/CMakeLists.txt         |  2 ++
 utility/ShardedLockManager.hpp | 41 +++++++++++++++++++++++++------------
 3 files changed, 44 insertions(+), 19 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30a15776/storage/StorageManager.cpp
----------------------------------------------------------------------
diff --git a/storage/StorageManager.cpp b/storage/StorageManager.cpp
index a3f265d..b98a28c 100644
--- a/storage/StorageManager.cpp
+++ b/storage/StorageManager.cpp
@@ -494,12 +494,16 @@ MutableBlockReference StorageManager::getBlockInternal(
   // To be safe, release the block's shard after 'eviction_lock' destructs.
   lock_manager_.release(block);
 
+  if (ret.valid()) {
+    return ret;
+  }
+
   // Note that there is no way for the block to be evicted between the call to
   // loadBlock and the call to EvictionPolicy::blockReferenced from
   // MutableBlockReference's constructor; this is because EvictionPolicy
   // doesn't know about the block until blockReferenced is called, so
   // chooseBlockToEvict shouldn't return the block.
-  if (!ret.valid()) {
+  do {
     SpinSharedMutexExclusiveLock<false> io_lock(*lock_manager_.get(block));
     {
       // Check one more time if the block got loaded in memory by someone else.
@@ -508,12 +512,12 @@ MutableBlockReference StorageManager::getBlockInternal(
       if (it != blocks_.end()) {
         DEBUG_ASSERT(!it->second.block->isBlob());
         ret = MutableBlockReference(static_cast<StorageBlock*>(it->second.block),
eviction_policy_.get());
-        return ret;
+        break;
       }
     }
     // No other thread loaded the block before us.
     ret = MutableBlockReference(loadBlock(block, relation, numa_node), eviction_policy_.get());
-  }
+  } while (false);
   // To be safe, release the block's shard after 'io_lock' destructs.
   lock_manager_.release(block);
 
@@ -535,7 +539,11 @@ MutableBlobReference StorageManager::getBlobInternal(const block_id blob,
   // To be safe, release the blob's shard after 'eviction_lock' destructs.
   lock_manager_.release(blob);
 
-  if (!ret.valid()) {
+  if (ret.valid()) {
+    return ret;
+  }
+
+  do {
     SpinSharedMutexExclusiveLock<false> io_lock(*lock_manager_.get(blob));
     // Note that there is no way for the block to be evicted between the call to
     // loadBlob and the call to EvictionPolicy::blockReferenced from
@@ -548,12 +556,12 @@ MutableBlobReference StorageManager::getBlobInternal(const block_id
blob,
       if (it != blocks_.end()) {
         DEBUG_ASSERT(it->second.block->isBlob());
         ret = MutableBlobReference(static_cast<StorageBlob*>(it->second.block),
eviction_policy_.get());
-        return ret;
+        break;
       }
     }
     // No other thread loaded the blob before us.
     ret = MutableBlobReference(loadBlob(blob, numa_node), eviction_policy_.get());
-  }
+  } while (false);
   // To be safe, release the blob's shard after 'io_lock' destructs.
   lock_manager_.release(blob);
 

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30a15776/utility/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt
index 4ff9254..bb59f65 100644
--- a/utility/CMakeLists.txt
+++ b/utility/CMakeLists.txt
@@ -244,7 +244,9 @@ target_link_libraries(quickstep_utility_SortConfiguration_proto
                       ${PROTOBUF_LIBRARY})
 target_link_libraries(quickstep_utility_ShardedLockManager
                       quickstep_storage_StorageConstants
+                      quickstep_threading_Mutex
                       quickstep_threading_SharedMutex
+                      quickstep_threading_SpinSharedMutex
                       quickstep_utility_Macros)
 target_link_libraries(quickstep_utility_StringUtil
                       glog)

http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30a15776/utility/ShardedLockManager.hpp
----------------------------------------------------------------------
diff --git a/utility/ShardedLockManager.hpp b/utility/ShardedLockManager.hpp
index 1d59acb..e3eba85 100644
--- a/utility/ShardedLockManager.hpp
+++ b/utility/ShardedLockManager.hpp
@@ -21,9 +21,12 @@
 #include <array>
 #include <cstddef>
 #include <functional>
+#include <unordered_map>
 
 #include "storage/StorageConstants.hpp"
+#include "threading/Mutex.hpp"
 #include "threading/SharedMutex.hpp"
+#include "threading/SpinSharedMutex.hpp"
 #include "utility/Macros.hpp"
 
 namespace quickstep {
@@ -64,24 +67,29 @@ class ShardedLockManager {
     if (has_collision != nullptr) {
       // In StorageManager::makeRoomForBlock, check whether the evicting block
       // or blob has a shard collision with existing referenced shards.
-      SpinSharedMutexSharedLock<false> read_lock(shards_mutex_);
-      if (shards_.find(shard) != shards_.end()) {
+      SpinSharedMutexSharedLock<false> read_lock(shard_count_mutex_);
+      if (shard_count_.find(shard) != shard_count_.end()) {
         *has_collision = true;
         return &collision_mutex_;
       }
     }
 
     {
-      SpinSharedMutexExclusiveLock<false> write_lock(shards_mutex_);
+      SpinSharedMutexExclusiveLock<false> write_lock(shard_count_mutex_);
 
       // Check one more time for the evicting block or blob if there is a shard
       // collision.
-      if (has_collision != nullptr && shards_.find(shard) != shards_.end()) {
-        *has_collision = true;
-        return &collision_mutex_;
+      auto it = shard_count_.find(shard);
+      if (it != shard_count_.end()) {
+        if (has_collision != nullptr) {
+          *has_collision = true;
+          return &collision_mutex_;
+        }
+
+        ++it->second;
+      } else {
+        shard_count_.emplace(shard, 1);
       }
-
-      shards_.insert(shard);
     }
     return &sharded_mutexes_[shard];
   }
@@ -91,8 +99,13 @@ class ShardedLockManager {
    * @param key The key to compute the shard.
    */
   void release(const T key) {
-    SpinSharedMutexExclusiveLock<false> write_lock(shards_mutex_);
-    shards_.erase(hash_(key) % N);
+    SpinSharedMutexExclusiveLock<false> write_lock(shard_count_mutex_);
+    auto it = shard_count_.find(hash_(key) % N);
+    DCHECK(it != shard_count_.end());
+
+    if (--it->second == 0) {
+      shard_count_.erase(it);
+    }
   }
 
  private:
@@ -102,9 +115,11 @@ class ShardedLockManager {
   // The placeholder mutex used whenever there is a hash collision.
   SharedMutexT collision_mutex_;
 
-  // Bookkeep all shards referenced by StorageManager in multiple threads.
-  std::unordered_set<std::size_t> shards_;
-  alignas(kCacheLineBytes) mutable SpinSharedMutex<false> shards_mutex_;
+  // Count all shards referenced by StorageManager in multiple threads.
+  // The key is the shard, while the value is the count. If the count equals to
+  // zero, we delete the shard entry.
+  std::unordered_map<std::size_t, std::size_t> shard_count_;
+  alignas(kCacheLineBytes) mutable SpinSharedMutex<false> shard_count_mutex_;
 
   DISALLOW_COPY_AND_ASSIGN(ShardedLockManager);
 };


Mime
View raw message