| /** |
| * 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_STORAGE_HASH_TABLE_KEY_MANAGER_HPP_ |
| #define QUICKSTEP_STORAGE_HASH_TABLE_KEY_MANAGER_HPP_ |
| |
| #include <atomic> |
| #include <cstddef> |
| #include <vector> |
| |
| #include "storage/HashTableBase.hpp" |
| #include "storage/StorageConstants.hpp" |
| #include "types/Type.hpp" |
| #include "types/TypedValue.hpp" |
| #include "types/operations/comparisons/ComparisonUtil.hpp" |
| #include "utility/Macros.hpp" |
| |
| #include "glog/logging.h" |
| |
| namespace quickstep { |
| |
| /** \addtogroup Storage |
| * @{ |
| */ |
| |
| /** |
| * @brief Helper object that manages key storage on behalf of a HashTable |
| * implementation. |
| * |
| * @tparam serializable Whether the HashTable can safely be saved to and |
| * loaded from disk. If false, out of band memory may be used to store |
| * variable length keys. |
| * @tparam force_key_copy If true, inserted keys are always copied into |
| * HashTable memory. If false, pointers to external values may be |
| * stored instead. force_key_copy should be true if the hash table will |
| * outlive the external key values which are inserted into it. Note |
| * that if serializable is true and force_key_copy is false, then |
| * relative offsets will be used instead of absolute pointers to keys, |
| * meaning that the pointed-to keys must be serialized and deserialized |
| * in exactly the same relative byte order (e.g. as part of the same |
| * StorageBlock), and keys must not change position relative to the |
| * HashTable (beware TupleStorageSubBlocks that may self-reorganize |
| * when modified). |
| **/ |
| template <bool serializable, bool force_key_copy> |
| class HashTableKeyManager { |
| public: |
| /** |
| * @brief Constructor. |
| * |
| * @param key_types A vector of pointers to the Types of key components for |
| * a HashTable. This is stored as a reference, not copied, so it must |
| * remain valid as long as this HashTableKeyManager will be used. |
| * @param key_start_in_bucket The position in the HashTable's buckets where |
| * storage for keys begins, measured as the number of bytes from the |
| * start of the bucket. |
| **/ |
| HashTableKeyManager(const std::vector<const Type*> &key_types, |
| const std::size_t key_start_in_bucket); |
| |
| /** |
| * @return The size (in bytes) of fixed (in-bucket) key storage. |
| **/ |
| inline std::size_t getFixedKeySize() const { |
| return fixed_key_size_; |
| } |
| |
| /** |
| * @return The total estimated size (in bytes) of variable-length key |
| * components stored out-of-line. |
| **/ |
| inline std::size_t getEstimatedVariableKeySize() const { |
| return estimated_variable_key_size_; |
| } |
| |
| /** |
| * @return A vector of bools indicating which key components are stored |
| * inline in buckets. |
| **/ |
| inline const std::vector<bool>* getKeyInline() const { |
| return &key_inline_; |
| } |
| |
| /** |
| * @brief Set information about out-of-line variable length key storage for |
| * a HashTable. |
| * |
| * @param variable_length_key_storage The location in memory of |
| * variable-length key storage for the HashTable. |
| * @param variable_length_key_storage_size The size (in bytes) of the region |
| * at variable_length_key_storage. |
| * @param variable_length_bytes_allocated A pointer to an atomic variable |
| * that counts how many bytes of variable-length storage have actually |
| * been allocated to store keys. |
| **/ |
| void setVariableLengthStorageInfo( |
| void *variable_length_key_storage, |
| const std::size_t variable_length_key_storage_size, |
| std::atomic<std::size_t> *variable_length_bytes_allocated) { |
| variable_length_key_storage_ = variable_length_key_storage; |
| variable_length_key_storage_size_ = variable_length_key_storage_size; |
| variable_length_bytes_allocated_ = variable_length_bytes_allocated; |
| next_variable_length_key_offset_.store( |
| variable_length_bytes_allocated_->load(std::memory_order_relaxed), |
| std::memory_order_relaxed); |
| } |
| |
| /** |
| * @return A pointer to the variable-length key storage region for the |
| * HashTable. |
| **/ |
| inline const void* getVariableLengthKeyStorage() const { |
| return variable_length_key_storage_; |
| } |
| |
| /** |
| * @return The size (in bytes) of the HashTable's variable-length key storage |
| * region. |
| **/ |
| inline std::size_t getVariableLengthKeyStorageSize() const { |
| return variable_length_key_storage_size_; |
| } |
| |
| /** |
| * @brief Get a pointer to a component of a key in a particular bucket. |
| * |
| * @param bucket A pointer to a bucket in the HashTable. |
| * @param component_idx The index of the desired key component (0 for single |
| * scalar keys). |
| * @return A pointer to the key component specified by component_idx in |
| * bucket. |
| **/ |
| inline const void* getKeyComponent( |
| const void *bucket, |
| const std::size_t component_idx) const; |
| |
| /** |
| * @brief Get a component of a key in a particular bucket as a TypedValue. |
| * |
| * @note Unlike getKeyComponent(), this method also determines the size in |
| * bytes of the key component in order to construct the TypedValue. |
| * |
| * @param bucket A pointer to a bucket in the HashTable. |
| * @param component_idx The index of the desired key component (0 for single |
| * scalar keys). |
| * @return The key component specified by component_idx in bucket as a |
| * TypedValue. |
| **/ |
| inline TypedValue getKeyComponentTyped( |
| const void *bucket, |
| const std::size_t component_idx) const; |
| |
| /** |
| * @brief Check whether a key is actually equal to a scalar key stored in a |
| * HashTable bucket. |
| * |
| * @param key The key to check. |
| * @param bucket The bucket whose key should be checked. |
| * @return Whether the keys are equal. |
| **/ |
| inline bool scalarKeyCollisionCheck(const TypedValue &key, |
| const void *bucket) const; |
| |
| /** |
| * @brief Check whether a composite key is actually equal to the composite |
| * key stored in a HashTable bucket. |
| * |
| * @param key The composite key to check. |
| * @param bucket The bucket whose key should be checked. |
| * @return Whether all the key components are equal. |
| **/ |
| inline bool compositeKeyCollisionCheck(const std::vector<TypedValue> &key, |
| const void *bucket) const; |
| |
| /** |
| * @brief Write a key component into a bucket. |
| * |
| * @note If the key component is variable-length, then |
| * allocateVariableLengthKeyStorage() should have been called first |
| * (either directly or by HashTable::preallocateForBulkInsert()) to |
| * reserve out-of-line variable storage. |
| * |
| * @param component The key component to write. |
| * @param component_idx The index of the key component (0 for single scalar |
| * keys). |
| * @param bucket A pointer to the bucket in the HashTable to write the key |
| * to. |
| * @param prealloc_state If non-null, variable length key components will be |
| * located in preallocated variable-length storage. |
| **/ |
| inline void writeKeyComponentToBucket( |
| const TypedValue &component, |
| const std::size_t component_idx, |
| void *bucket, |
| HashTablePreallocationState *prealloc_state); |
| |
| /** |
| * @brief Reserve storage for variable-length key components. |
| * |
| * @note This can be undone by calling deallocateVariableLengthKeyStorage(). |
| * @note Allocated storage is actually used by calling |
| * writeKeyComponentToBucket() for variable-length key components. |
| * |
| * @param required_bytes The size of the variable-length key storage to |
| * reserve. |
| * @return true if allocation was successful, false if not enough unreserved |
| * space was available. |
| **/ |
| inline bool allocateVariableLengthKeyStorage( |
| const std::size_t required_bytes); |
| |
| /** |
| * @brief Release (undo) a reservation of storage for variable-length key |
| * components previously made by allocateVariableLengthKeyStorage(). |
| * |
| * @param bytes The size of the variable-length key storage reservation to |
| * release. |
| **/ |
| inline void deallocateVariableLengthKeyStorage(const std::size_t bytes); |
| |
| /** |
| * @return The current "next" offset to be used when actually writing |
| * variable-length keys. |
| **/ |
| inline std::size_t getNextVariableLengthKeyOffset() const { |
| return next_variable_length_key_offset_.load(std::memory_order_relaxed); |
| } |
| |
| /** |
| * @brief Increment the "next" offset to be used when writing variable-length |
| * keys. |
| * |
| * @note This is intended mainly for use by preallocateForBulkInsert() to |
| * allocate a contiguous region of variable-length storage all in one |
| * go. |
| * |
| * @param bytes The number of bytes to increment the offset by. |
| * @return The original value of the "next" offset. |
| **/ |
| inline std::size_t incrementNextVariableLengthKeyOffset( |
| const std::size_t bytes) { |
| return next_variable_length_key_offset_.fetch_add( |
| bytes, |
| std::memory_order_relaxed); |
| } |
| |
| /** |
| * @brief Reset the "next" offset for writing variable-length keys to zero. |
| * |
| * @warning This should only be used when clearing a HashTable, as it will |
| * cause any previously written variable-length keys to be |
| * overwritten. |
| **/ |
| inline void zeroNextVariableLengthKeyOffset() { |
| next_variable_length_key_offset_.store(0, std::memory_order_relaxed); |
| } |
| |
| private: |
| const std::vector<const Type*> &key_types_; |
| std::size_t fixed_key_size_; |
| std::size_t estimated_variable_key_size_; |
| std::vector<std::size_t> key_offsets_; |
| std::vector<bool> key_inline_; |
| |
| void *variable_length_key_storage_; |
| std::size_t variable_length_key_storage_size_; |
| std::atomic<std::size_t> *variable_length_bytes_allocated_; |
| // This is separate from '*variable_length_bytes_allocated_', because we |
| // allocate storage for variable-length keys up-front but defer actually |
| // copying them until we find an empty bucket. |
| alignas(kCacheLineBytes) std::atomic<std::size_t> |
| next_variable_length_key_offset_; |
| |
| DISALLOW_COPY_AND_ASSIGN(HashTableKeyManager); |
| }; |
| |
| /** @} */ |
| |
| // ---------------------------------------------------------------------------- |
| // Implementations of template class methods follow. |
| |
| template <bool serializable, bool force_key_copy> |
| HashTableKeyManager<serializable, force_key_copy>::HashTableKeyManager( |
| const std::vector<const Type*> &key_types, |
| const std::size_t key_start_in_bucket) |
| : key_types_(key_types), |
| fixed_key_size_(0), |
| estimated_variable_key_size_(0), |
| variable_length_key_storage_(nullptr), |
| variable_length_key_storage_size_(0), |
| variable_length_bytes_allocated_(nullptr), |
| next_variable_length_key_offset_(0) { |
| DCHECK(!key_types_.empty()); |
| |
| for (const Type *subkey_type : key_types_) { |
| key_offsets_.push_back(key_start_in_bucket + fixed_key_size_); |
| |
| if (force_key_copy) { |
| if (subkey_type->isVariableLength()) { |
| // An offset into the variable length storage region, paired with a length. |
| fixed_key_size_ += sizeof(std::size_t) * 2; |
| estimated_variable_key_size_ += subkey_type->estimateAverageByteLength(); |
| key_inline_.push_back(false); |
| } else { |
| fixed_key_size_ += subkey_type->maximumByteLength(); |
| key_inline_.push_back(true); |
| } |
| } else { |
| constexpr std::size_t ptr_size = serializable ? sizeof(std::ptrdiff_t) |
| : sizeof(const void*); |
| if ((!subkey_type->isVariableLength()) |
| && (subkey_type->maximumByteLength() <= ptr_size + sizeof(std::size_t))) { |
| fixed_key_size_ += subkey_type->maximumByteLength(); |
| key_inline_.push_back(true); |
| } else { |
| // A pointer to external memory, paired with a length. |
| fixed_key_size_ += ptr_size + sizeof(std::size_t); |
| key_inline_.push_back(false); |
| } |
| } |
| } |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline const void* HashTableKeyManager<serializable, force_key_copy> |
| ::getKeyComponent(const void *bucket, |
| const std::size_t component_idx) const { |
| DCHECK_LT(component_idx, key_offsets_.size()); |
| |
| const void *base_key_ptr = static_cast<const char*>(bucket) |
| + key_offsets_[component_idx]; |
| if (key_inline_[component_idx]) { |
| // Component is inline. |
| return base_key_ptr; |
| } else if (force_key_copy) { |
| // Component is copied into variable-length region. |
| DCHECK(key_types_[component_idx]->isVariableLength()); |
| return static_cast<const char*>(variable_length_key_storage_) |
| + *static_cast<const std::size_t*>(base_key_ptr); |
| } else if (serializable) { |
| // Relative pointer. |
| return static_cast<const char*>(base_key_ptr) |
| + *static_cast<const std::ptrdiff_t*>(base_key_ptr); |
| } else { |
| // Absolute pointer. |
| return *static_cast<const void* const*>(base_key_ptr); |
| } |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline TypedValue HashTableKeyManager<serializable, force_key_copy> |
| ::getKeyComponentTyped(const void *bucket, |
| const std::size_t component_idx) const { |
| DCHECK_LT(component_idx, key_offsets_.size()); |
| |
| const Type &key_type = *(key_types_[component_idx]); |
| const void *base_key_ptr = static_cast<const char*>(bucket) |
| + key_offsets_[component_idx]; |
| if (key_inline_[component_idx]) { |
| // Component is inline. |
| DCHECK(!key_type.isVariableLength()); |
| return key_type.makeValue(base_key_ptr, |
| key_type.maximumByteLength()); |
| } else if (force_key_copy) { |
| // Component is copied into variable-length region. |
| DCHECK(key_type.isVariableLength()); |
| return key_type.makeValue(static_cast<const char*>(variable_length_key_storage_) |
| + *static_cast<const std::size_t*>(base_key_ptr), |
| *(static_cast<const std::size_t*>(base_key_ptr) + 1)); |
| } else if (serializable) { |
| // Relative pointer. |
| return key_type.makeValue( |
| static_cast<const char*>(base_key_ptr) |
| + *static_cast<const std::ptrdiff_t*>(base_key_ptr), |
| key_type.isVariableLength() ? *(static_cast<const std::size_t*>(base_key_ptr) + 1) |
| : key_type.maximumByteLength()); |
| } else { |
| // Absolute pointer. |
| return key_type.makeValue( |
| *static_cast<const void* const*>(base_key_ptr), |
| key_type.isVariableLength() ? *(static_cast<const std::size_t*>(base_key_ptr) + 1) |
| : key_type.maximumByteLength()); |
| } |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline bool HashTableKeyManager<serializable, force_key_copy> |
| ::scalarKeyCollisionCheck(const TypedValue &key, |
| const void *bucket) const { |
| return CheckUntypedValuesEqual(*key_types_.front(), |
| key.getDataPtr(), |
| getKeyComponent(bucket, 0)); |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline bool HashTableKeyManager<serializable, force_key_copy> |
| ::compositeKeyCollisionCheck(const std::vector<TypedValue> &key, |
| const void *bucket) const { |
| DCHECK_EQ(key_types_.size(), key.size()); |
| |
| // Check key components one-by-one. |
| for (std::size_t idx = 0; |
| idx < key_types_.size(); |
| ++idx) { |
| if (!CheckUntypedValuesEqual(*key_types_[idx], |
| key[idx].getDataPtr(), |
| getKeyComponent(bucket, idx))) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline void HashTableKeyManager<serializable, force_key_copy> |
| ::writeKeyComponentToBucket(const TypedValue &component, |
| const std::size_t component_idx, |
| void *bucket, |
| HashTablePreallocationState *prealloc_state) { |
| void *key_ptr = static_cast<char*>(bucket) + key_offsets_[component_idx]; |
| if (key_inline_[component_idx]) { |
| // Copy key component directly into bucket. |
| component.copyInto(key_ptr); |
| } else if (force_key_copy) { |
| // Copy key into variable-length storage region and store its offset and |
| // length. |
| DCHECK(key_types_[component_idx]->isVariableLength()); |
| const std::size_t component_size = component.getDataSize(); |
| const std::size_t variable_length_key_pos |
| = (prealloc_state == nullptr) |
| ? next_variable_length_key_offset_.fetch_add(component_size, |
| std::memory_order_relaxed) |
| : prealloc_state->variable_length_key_position; |
| if (prealloc_state != nullptr) { |
| prealloc_state->variable_length_key_position += component_size; |
| } |
| DCHECK_LE(variable_length_key_pos + component_size, |
| variable_length_key_storage_size_); |
| |
| component.copyInto(static_cast<char*>(variable_length_key_storage_) |
| + variable_length_key_pos); |
| *static_cast<std::size_t*>(key_ptr) = variable_length_key_pos; |
| *(static_cast<std::size_t*>(key_ptr) + 1) = component_size; |
| } else if (serializable) { |
| // Store a relative pointer. We assume that we are pointing to memory |
| // that is serialized together with the HashTable, i.e. as part of the same |
| // StorageBlock. See comments regarding the 'force_key_copy' parameter in |
| // storage/HashTable.hpp for more details. |
| DCHECK(component.isReference()); |
| *static_cast<std::ptrdiff_t*>(key_ptr) = static_cast<const char*>(component.getDataPtr()) |
| - static_cast<const char*>(key_ptr); |
| if (key_types_[component_idx]->isVariableLength()) { |
| // Also store length if variable-length. |
| *(static_cast<std::size_t*>(key_ptr) + 1) = component.getDataSize(); |
| } |
| } else { |
| // Store an absolute pointer. |
| *static_cast<const void**>(key_ptr) = component.getDataPtr(); |
| if (key_types_[component_idx]->isVariableLength()) { |
| // Also store length if variable-length. |
| *(static_cast<std::size_t*>(key_ptr) + 1) = component.getDataSize(); |
| } |
| } |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline bool HashTableKeyManager<serializable, force_key_copy> |
| ::allocateVariableLengthKeyStorage(const std::size_t required_bytes) { |
| if (required_bytes == 0) { |
| return true; |
| } |
| |
| const std::size_t original_variable_length_bytes_allocated |
| = variable_length_bytes_allocated_->fetch_add(required_bytes, |
| std::memory_order_relaxed); |
| if (original_variable_length_bytes_allocated + required_bytes |
| > variable_length_key_storage_size_) { |
| // Release the memory we tried to allocate. |
| variable_length_bytes_allocated_->fetch_sub(required_bytes, |
| std::memory_order_relaxed); |
| return false; |
| } else { |
| return true; |
| } |
| } |
| |
| template <bool serializable, bool force_key_copy> |
| inline void HashTableKeyManager<serializable, force_key_copy> |
| ::deallocateVariableLengthKeyStorage(const std::size_t bytes) { |
| if (bytes == 0) { |
| return; |
| } |
| variable_length_bytes_allocated_->fetch_sub(bytes, |
| std::memory_order_relaxed); |
| } |
| |
| } // namespace quickstep |
| |
| #endif // QUICKSTEP_STORAGE_HASH_TABLE_KEY_MANAGER_HPP_ |
