blob: 520f87945697d4714c67a96dfdb823dcfcc56dd5 [file] [log] [blame]
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
#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 {
/** \addtogroup Utility
* @{
* @brief Maintains a fixed number of SharedMutex objects and an interface for
* mapping instances of the template class T to one of the underlying
* SharedMutex's. The mapping is done by calling std::hash<T>::operator()
* on the object.
* @param T The class to map to SharedMutex's.
* @param N The number of SharedMutex's to use in the underlying array.
* @param SharedMutexT The shared mutex class to use for locks.
template <typename T, std::size_t N, typename SharedMutexT = SharedMutex>
class ShardedLockManager {
* @brief Default constructor.
ShardedLockManager() { }
* @brief Get the SharedMutex corresponding to the provided key.
* @param key The key to map to a SharedMutex.
* @param has_collision Whether accessing the given key would result in a
* hash collision. Used in StorageManager::makeRoomForBlock only.
* @return The corresponding SharedMutex if there is no collision; otherwise,
* the collision SharedMutex.
SharedMutexT* get(const T key, bool *has_collision = nullptr) {
const std::size_t shard = hash_(key) % N;
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(shard_count_mutex_);
if (shard_count_.find(shard) != shard_count_.end()) {
*has_collision = true;
return &collision_mutex_;
SpinSharedMutexExclusiveLock<false> write_lock(shard_count_mutex_);
// Check one more time for the evicting block or blob if there is a shard
// collision.
auto it = shard_count_.find(shard);
if (it != shard_count_.end()) {
if (has_collision != nullptr) {
*has_collision = true;
return &collision_mutex_;
} else {
shard_count_.emplace(shard, 1);
return &sharded_mutexes_[shard];
* @brief Release the shard corresponding to the provided key.
* @param key The key to compute the shard.
void release(const T key) {
SpinSharedMutexExclusiveLock<false> write_lock(shard_count_mutex_);
auto it = shard_count_.find(hash_(key) % N);
DCHECK(it != shard_count_.end());
if (--it->second == 0) {
std::hash<T> hash_;
std::array<SharedMutexT, N> sharded_mutexes_;
// The placeholder mutex used whenever there is a hash collision.
SharedMutexT collision_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_;
/** @} */
} // namespace quickstep