From 91c8ae2272d653027f4618f9d367a312aac6fb98 Mon Sep 17 00:00:00 2001 From: Geir Storli Date: Thu, 27 May 2021 13:03:27 +0000 Subject: Add common utils to map from bucket key to stripe and calculcate number of stripe bits. --- storage/src/tests/common/CMakeLists.txt | 1 + .../src/tests/common/bucket_stripe_utils_test.cpp | 37 +++++++++++++++++++ .../storage/bucketdb/striped_btree_lockable_map.h | 1 - .../bucketdb/striped_btree_lockable_map.hpp | 13 +------ storage/src/vespa/storage/common/CMakeLists.txt | 1 + .../vespa/storage/common/bucket_stripe_utils.cpp | 43 ++++++++++++++++++++++ .../src/vespa/storage/common/bucket_stripe_utils.h | 28 ++++++++++++++ 7 files changed, 112 insertions(+), 12 deletions(-) create mode 100644 storage/src/tests/common/bucket_stripe_utils_test.cpp create mode 100644 storage/src/vespa/storage/common/bucket_stripe_utils.cpp create mode 100644 storage/src/vespa/storage/common/bucket_stripe_utils.h (limited to 'storage') diff --git a/storage/src/tests/common/CMakeLists.txt b/storage/src/tests/common/CMakeLists.txt index 400255964d6..4e7cecb9d9f 100644 --- a/storage/src/tests/common/CMakeLists.txt +++ b/storage/src/tests/common/CMakeLists.txt @@ -12,6 +12,7 @@ vespa_add_library(storage_testcommon TEST vespa_add_executable(storage_common_gtest_runner_app TEST SOURCES + bucket_stripe_utils_test.cpp bucket_utils_test.cpp global_bucket_space_distribution_converter_test.cpp gtest_runner.cpp diff --git a/storage/src/tests/common/bucket_stripe_utils_test.cpp b/storage/src/tests/common/bucket_stripe_utils_test.cpp new file mode 100644 index 00000000000..ae9f656e4d7 --- /dev/null +++ b/storage/src/tests/common/bucket_stripe_utils_test.cpp @@ -0,0 +1,37 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include +#include +#include + +using document::BucketId; +using storage::calc_num_stripe_bits; +using storage::stripe_of_bucket_key; +constexpr uint8_t MUB = storage::spi::BucketLimits::MinUsedBits; + +TEST(BucketStripeUtilsTest, stripe_of_bucket_key) +{ + BucketId id(MUB, std::numeric_limits::max()); + uint64_t key = id.stripUnused().toKey(); + EXPECT_EQ(0, stripe_of_bucket_key(key, 0)); + EXPECT_EQ(1, stripe_of_bucket_key(key, 1)); + EXPECT_EQ(3, stripe_of_bucket_key(key, 2)); + EXPECT_EQ(127, stripe_of_bucket_key(key, 7)); + EXPECT_EQ(255, stripe_of_bucket_key(key, 8)); +} + +TEST(BucketStripeUtilsTest, calc_num_stripe_bits) +{ + EXPECT_EQ(0, calc_num_stripe_bits(1)); + EXPECT_EQ(1, calc_num_stripe_bits(2)); + EXPECT_EQ(2, calc_num_stripe_bits(4)); + EXPECT_EQ(7, calc_num_stripe_bits(128)); + EXPECT_EQ(8, calc_num_stripe_bits(256)); +} + +TEST(BucketStripeUtilsTest, max_stripe_values) +{ + EXPECT_EQ(8, storage::MaxStripeBits); + EXPECT_EQ(256, storage::MaxStripes); +} + diff --git a/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.h b/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.h index b01f06c2b3f..73b5c37ab8b 100644 --- a/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.h +++ b/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.h @@ -27,7 +27,6 @@ public: using Decision = typename ParentType::Decision; using BucketId = document::BucketId; - constexpr static uint8_t MaxStripeBits = 8; private: using StripedDBType = BTreeLockableMap; uint8_t _n_stripe_bits; diff --git a/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.hpp b/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.hpp index e4f6efa30a3..310a9d5154b 100644 --- a/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.hpp +++ b/storage/src/vespa/storage/bucketdb/striped_btree_lockable_map.hpp @@ -3,20 +3,13 @@ #include "striped_btree_lockable_map.h" #include "btree_lockable_map.hpp" +#include #include #include #include namespace storage::bucketdb { -namespace { - -constexpr uint8_t used_bits_of(uint64_t key) noexcept { - return static_cast(key & 0b11'1111ULL); -} - -} - template StripedBTreeLockableMap::StripedBTreeLockableMap(uint8_t n_stripe_bits) : _n_stripe_bits(n_stripe_bits), @@ -37,9 +30,7 @@ StripedBTreeLockableMap::~StripedBTreeLockableMap() = default; template size_t StripedBTreeLockableMap::stripe_of(key_type key) const noexcept { - assert(used_bits_of(key) >= _n_stripe_bits); - // Since bucket keys have count-bits at the LSB positions, we want to look at the MSBs instead. - return (key >> (64 - _n_stripe_bits)); + return stripe_of_bucket_key(key, _n_stripe_bits); } template diff --git a/storage/src/vespa/storage/common/CMakeLists.txt b/storage/src/vespa/storage/common/CMakeLists.txt index 741d97f78ef..ae428929946 100644 --- a/storage/src/vespa/storage/common/CMakeLists.txt +++ b/storage/src/vespa/storage/common/CMakeLists.txt @@ -1,6 +1,7 @@ # Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. vespa_add_library(storage_common OBJECT SOURCES + bucket_stripe_utils.cpp bucketmessages.cpp content_bucket_space.cpp content_bucket_space_repo.cpp diff --git a/storage/src/vespa/storage/common/bucket_stripe_utils.cpp b/storage/src/vespa/storage/common/bucket_stripe_utils.cpp new file mode 100644 index 00000000000..f1454403153 --- /dev/null +++ b/storage/src/vespa/storage/common/bucket_stripe_utils.cpp @@ -0,0 +1,43 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "bucket_stripe_utils.h" +#include +#include + +namespace storage { + +namespace { + +constexpr uint8_t used_bits_of(uint64_t key) noexcept { + return static_cast(key & 0b11'1111ULL); +} + +} + +size_t +stripe_of_bucket_key(uint64_t key, uint8_t n_stripe_bits) noexcept +{ + if (n_stripe_bits == 0) { + return 0; + } + assert(used_bits_of(key) >= n_stripe_bits); + // Since bucket keys have count-bits at the LSB positions, we want to look at the MSBs instead. + return (key >> (64 - n_stripe_bits)); +} + +uint8_t +calc_num_stripe_bits(size_t n_stripes) noexcept +{ + assert(n_stripes > 0); + if (n_stripes == 1) { + return 0; + } + assert(n_stripes <= MaxStripes); + assert(n_stripes == vespalib::roundUp2inN(n_stripes)); + + auto result = vespalib::Optimized::msbIdx(n_stripes); + assert(result <= MaxStripeBits); + return result; +} + +} diff --git a/storage/src/vespa/storage/common/bucket_stripe_utils.h b/storage/src/vespa/storage/common/bucket_stripe_utils.h new file mode 100644 index 00000000000..b4052a893a2 --- /dev/null +++ b/storage/src/vespa/storage/common/bucket_stripe_utils.h @@ -0,0 +1,28 @@ +// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#pragma once + +#include +#include +#include + +namespace storage { + +constexpr static uint8_t MaxStripeBits = spi::BucketLimits::MinUsedBits; +constexpr static size_t MaxStripes = (1ULL << MaxStripeBits); + +/** + * Returns the stripe in which the given bucket key belongs, + * when using the given number of stripe bits. + */ +size_t stripe_of_bucket_key(uint64_t key, uint8_t n_stripe_bits) noexcept; + +/** + * Returns the number of stripe bits used to represent the given number of stripes. + * + * This also asserts that the number of stripes is valid (power of 2 and within MaxStripes boundary). + */ +uint8_t calc_num_stripe_bits(size_t n_stripes) noexcept; + +} + -- cgit v1.2.3