Avoid deadlocks when loading a block or blob.
diff --git a/storage/StorageManager.cpp b/storage/StorageManager.cpp
index 8932e56..410eeb1 100644
--- a/storage/StorageManager.cpp
+++ b/storage/StorageManager.cpp
@@ -355,7 +355,7 @@
DEBUG_ASSERT(num_slots > 0);
DEBUG_ASSERT(handle != nullptr);
- handle->block_memory = allocateSlots(num_slots, numa_node, kInvalidBlockId);
+ handle->block_memory = allocateSlots(num_slots, numa_node);
handle->block_memory_size = num_slots;
return ++block_index_;
@@ -368,7 +368,7 @@
// already loaded before this function gets called.
size_t num_slots = file_manager_->numSlots(block);
DEBUG_ASSERT(num_slots != 0);
- void* block_buffer = allocateSlots(num_slots, numa_node, block);
+ void* block_buffer = allocateSlots(num_slots, numa_node);
const bool status = file_manager_->readBlockOrBlob(block, block_buffer, kSlotSizeBytes * num_slots);
CHECK(status) << "Failed to read block from persistent storage: " << block;
@@ -388,8 +388,7 @@
}
void* StorageManager::allocateSlots(const std::size_t num_slots,
- const int numa_node,
- const block_id locked_block_id) {
+ const int numa_node) {
#if defined(QUICKSTEP_HAVE_MMAP_LINUX_HUGETLB)
static constexpr int kLargePageMmapFlags
= MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB;
@@ -398,7 +397,7 @@
= MAP_PRIVATE | MAP_ANONYMOUS | MAP_ALIGNED_SUPER;
#endif
- makeRoomForBlock(num_slots, locked_block_id);
+ makeRoomForBlock(num_slots);
void *slots = nullptr;
#if defined(QUICKSTEP_HAVE_MMAP_LINUX_HUGETLB) || defined(QUICKSTEP_HAVE_MMAP_BSD_SUPERPAGE)
@@ -492,6 +491,7 @@
ret = MutableBlockReference(static_cast<StorageBlock*>(it->second.block), eviction_policy_.get());
}
}
+ lock_manager_.release(block);
// Note that there is no way for the block to be evicted between the call to
// loadBlock and the call to EvictionPolicy::blockReferenced from
@@ -511,21 +511,9 @@
}
}
// No other thread loaded the block before us.
- // But going forward be careful as there is a potential self-deadlock
- // situation here -- we are holding an Exclusive lock (io_lock)
- // and getting ready to go into the call chain
- // "MutableBlockReference"/"loadBlock" -> "loadBlockOrBlob"
- // -> "allocateSlots" -> "makeRoomForBlock"
- // In "makeRoomForBlock," we will acquire an exclusive lock via the call
- // "eviction_lock(*lock_manager_.get(block_index))"
- // This situation could lead to a self-deadlock as block_index could
- // hash to the same position in the "ShardedLockManager" as "block."
- // To deal with this case, we pass the block information for "block"
- // though the call chain, and check for a collision in the the
- // "ShardedLockManager" in the function "makeRoomForBlock."
- // If a collision is detected we avoid a self-deadlock.
ret = MutableBlockReference(loadBlock(block, relation, numa_node), eviction_policy_.get());
}
+ lock_manager_.release(block);
return ret;
}
@@ -542,6 +530,7 @@
ret = MutableBlobReference(static_cast<StorageBlob*>(it->second.block), eviction_policy_.get());
}
}
+ lock_manager_.release(blob);
if (!ret.valid()) {
SpinSharedMutexExclusiveLock<false> io_lock(*lock_manager_.get(blob));
@@ -562,47 +551,49 @@
// No other thread loaded the blob before us.
ret = MutableBlobReference(loadBlob(blob, numa_node), eviction_policy_.get());
}
+ lock_manager_.release(blob);
return ret;
}
-void StorageManager::makeRoomForBlock(const size_t slots,
- const block_id locked_block_id) {
+void StorageManager::makeRoomForBlock(const size_t slots) {
while (total_memory_usage_ + slots > max_memory_usage_) {
block_id block_index;
EvictionPolicy::Status status = eviction_policy_->chooseBlockToEvict(&block_index);
- if ((status == EvictionPolicy::Status::kOk) && // Have a valid "block_index."
- (locked_block_id != kInvalidBlockId) &&
- (lock_manager_.get(locked_block_id) == lock_manager_.get(block_index))) {
- // We have a collision in the shared lock manager, where the caller of
- // this function has acquired a lock, and we are trying to evict a block
- // that hashes to the same location. This will cause a self-deadlock.
-
- // For now simply treat this situation as the case where there is not
- // enough memory and we temporarily go over the memory limit.
- // TODO(jmp): find another block to evict, if possible.
- break;
- }
-
if (status == EvictionPolicy::Status::kOk) {
- SpinSharedMutexExclusiveLock<false> eviction_lock(*lock_manager_.get(block_index));
+ bool has_collision = false;
+ SpinSharedMutexExclusiveLock<false> eviction_lock(*lock_manager_.get(block_index, &has_collision));
+ if (has_collision) {
+ // We have a collision in the shared lock manager, where the caller of
+ // this function has acquired a lock, and we are trying to evict a block
+ // that hashes to the same location. This will cause a self-deadlock.
+
+ // For now simply treat this situation as the case where there is not
+ // enough memory and we temporarily go over the memory limit.
+ break;
+ }
+
StorageBlockBase* block;
{
SpinSharedMutexSharedLock<false> read_lock(blocks_shared_mutex_);
if (blocks_.find(block_index) == blocks_.end()) {
// another thread must have jumped in and evicted it before us
+ lock_manager_.release(block_index);
continue;
}
block = blocks_[block_index].block;
}
if (eviction_policy_->getRefCount(block->getID()) > 0) {
// Someone sneaked in and referenced the block before we could evict it.
+ lock_manager_.release(block_index);
continue;
}
if (saveBlockOrBlob(block->getID())) {
evictBlockOrBlob(block->getID());
} // else : Someone sneaked in and evicted the block before we could.
+
+ lock_manager_.release(block_index);
} else {
// If status was not ok, then we must not have been able to evict enough
// blocks; therefore, we return anyway, temporarily going over the memory
diff --git a/storage/StorageManager.hpp b/storage/StorageManager.hpp
index 88004b8..805e885 100644
--- a/storage/StorageManager.hpp
+++ b/storage/StorageManager.hpp
@@ -341,20 +341,8 @@
// Allocate a buffer to hold the specified number of slots. The memory
// returned will be zeroed-out, and mapped using large pages if the system
// supports it.
- // Note if the last parameter "locked_block_id" is set to something other than
- // "kInvalidBlockId," then it means that the caller has acquired
- // a lock in the sharded lock manager for that block. Thus, if a block needs
- // to be evicted by the EvictionPolicy in the "makeRoomForBlock" call, and
- // if the block to be evicted happens to hash to the same entry in the
- // sharded lock manager, then the Eviction policy needs to pick a different
- // block for eviction.
- // The key point is that if "locked_block_id" is not "kInvalidBlockId," then
- // the caller of allocateSlots, e.g. loadBlock, will have acquired a lock
- // in the sharded lock manager for the block "locked_block_id."
void* allocateSlots(const std::size_t num_slots,
- const int numa_node,
- // const block_id locked_block_id = kInvalidBlockId);
- const block_id locked_block_id);
+ const int numa_node);
// Deallocate a buffer allocated by allocateSlots(). This must be used
// instead of free(), because the underlying implementation of
@@ -402,14 +390,8 @@
* requested size.
*
* @param slots Number of slots to make room for.
- * @param locked_block_id Reference to the block id for which room is being made.
- * The parent has a lock in the sharded lock manager for the
- * "locked_block_id," so need to pass this through to the
- * EvictionPolicy to avoid a deadlock if the block that is
- * being cleared out hashes to the same hash entry.
*/
- void makeRoomForBlock(const size_t slots,
- const block_id locked_block_id);
+ void makeRoomForBlock(const size_t slots);
/**
* @brief Load a block from the persistent storage into memory.
diff --git a/utility/ShardedLockManager.hpp b/utility/ShardedLockManager.hpp
index 0248882..550a7ba 100644
--- a/utility/ShardedLockManager.hpp
+++ b/utility/ShardedLockManager.hpp
@@ -1,6 +1,6 @@
/**
* Copyright 2011-2015 Quickstep Technologies LLC.
- * Copyright 2015 Pivotal Software, Inc.
+ * Copyright 2015-2016 Pivotal Software, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -22,6 +22,7 @@
#include <cstddef>
#include <functional>
+#include "storage/StorageConstants.hpp"
#include "threading/SharedMutex.hpp"
#include "utility/Macros.hpp"
@@ -54,14 +55,36 @@
* @param key The key to map to a SharedMutex.
* @return The corresponding SharedMutex.
*/
- SharedMutexT *get(const T key) {
- return &shards[hash_(key) % N];
+ SharedMutexT* get(const T key, bool *has_collision = nullptr) {
+ const std::size_t hashed_value = hash_(key) % N;
+ if (has_collision != nullptr) {
+ SpinSharedMutexSharedLock<false> read_lock(collisions_mutex_);
+ *has_collision =
+ collisions_.find(hashed_value) != collisions_.end();
+ if (*has_collision) {
+ return &dummy_mutex_;
+ }
+ }
+
+ SpinSharedMutexExclusiveLock<false> write_lock(collisions_mutex_);
+ collisions_.insert(hashed_value);
+ return &shards[hashed_value];
+ }
+
+ void release(const T key) {
+ SpinSharedMutexExclusiveLock<false> write_lock(collisions_mutex_);
+ collisions_.erase(hash_(key) % N);
}
private:
std::hash<T> hash_;
std::array<SharedMutexT, N> shards;
+ SharedMutexT dummy_mutex_;
+
+ alignas(kCacheLineBytes) mutable SpinSharedMutex<false> collisions_mutex_;
+ std::unordered_set<std::size_t> collisions_;
+
DISALLOW_COPY_AND_ASSIGN(ShardedLockManager);
};
