Add common utils to map from bucket key to stripe and calculcate number of stripe bits.

7 files changed, 112 insertions, 12 deletions

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 <vespa/document/bucket/bucketid.h>
+#include <vespa/storage/common/bucket_stripe_utils.h>
+#include <vespa/vespalib/gtest/gtest.h>
+
+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<uint64_t>::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<T>;
     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 <vespa/storage/common/bucket_stripe_utils.h>
 #include <algorithm>
 #include <cassert>
 #include <queue>
 
 namespace storage::bucketdb {
 
-namespace {
-
-constexpr uint8_t used_bits_of(uint64_t key) noexcept {
-    return static_cast<uint8_t>(key & 0b11'1111ULL);
-}
-
-}
-
 template <typename T>
 StripedBTreeLockableMap<T>::StripedBTreeLockableMap(uint8_t n_stripe_bits)
     : _n_stripe_bits(n_stripe_bits),
@@ -37,9 +30,7 @@ StripedBTreeLockableMap<T>::~StripedBTreeLockableMap() = default;
 
 template <typename T>
 size_t StripedBTreeLockableMap<T>::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 <typename T>
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 <vespa/vespalib/util/alloc.h>
+#include <cassert>
+
+namespace storage {
+
+namespace {
+
+constexpr uint8_t used_bits_of(uint64_t key) noexcept {
+    return static_cast<uint8_t>(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 <vespa/persistence/spi/bucket_limits.h>
+#include <cstdint>
+#include <cstdlib>
+
+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;
+
+}
+