You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by zu...@apache.org on 2016/05/16 20:55:53 UTC
[16/46] incubator-quickstep git commit: Fixed the deadlock when
loading while evicting. (#196)
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/7ac1d22e
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/7ac1d22e
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/7ac1d22e
Branch: refs/heads/master
Commit: 7ac1d22e0ae156730d14b86855df76bc10cefc47
Parents: d353a64
Author: Zuyu ZHANG <zu...@users.noreply.github.com>
Authored: Wed Apr 27 22:59:25 2016 -0700
Committer: Jignesh Patel <pa...@users.noreply.github.com>
Committed: Thu Apr 28 00:59:25 2016 -0500
----------------------------------------------------------------------
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/7ac1d22e/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/7ac1d22e/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/7ac1d22e/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);
};