utility/ShardedLockManager.hpp

/**
 * 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
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 **/

#ifndef QUICKSTEP_UTILITY_SHARDED_LOCK_MANAGER_HPP_
#define QUICKSTEP_UTILITY_SHARDED_LOCK_MANAGER_HPP_

#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 {
 public:
  /**
   * @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_;
        }

        ++it->second;
      } 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) {
      shard_count_.erase(it);
    }
  }

 private:
  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_;

  DISALLOW_COPY_AND_ASSIGN(ShardedLockManager);
};

/** @} */

}  // namespace quickstep

#endif  // QUICKSTEP_UTILITY_SHARDED_LOCK_MANAGER_HPP_