Add DynamicArrayBufferType.

6 files changed, 437 insertions, 0 deletions

diff --git a/vespalib/src/tests/datastore/dynamic_array_buffer_type/CMakeLists.txt b/vespalib/src/tests/datastore/dynamic_array_buffer_type/CMakeLists.txt
new file mode 100644
index 00000000000..02cb0464e7c
--- /dev/null
+++ b/vespalib/src/tests/datastore/dynamic_array_buffer_type/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_dynamic_array_buffer_type_test_app TEST
+    SOURCES
+    dynamic_array_buffer_type_test.cpp
+    DEPENDS
+    vespalib
+    GTest::GTest
+)
+vespa_add_test(NAME vespalib_dynamic_array_buffer_type_test_app COMMAND vespalib_dynamic_array_buffer_type_test_app)
diff --git a/vespalib/src/tests/datastore/dynamic_array_buffer_type/dynamic_array_buffer_type_test.cpp b/vespalib/src/tests/datastore/dynamic_array_buffer_type/dynamic_array_buffer_type_test.cpp
new file mode 100644
index 00000000000..d5244ae56aa
--- /dev/null
+++ b/vespalib/src/tests/datastore/dynamic_array_buffer_type/dynamic_array_buffer_type_test.cpp
@@ -0,0 +1,249 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/datastore/dynamic_array_buffer_type.hpp>
+#include <vespa/vespalib/gtest/gtest.h>
+#include <ostream>
+
+using vespalib::datastore::BufferTypeBase;
+using vespalib::datastore::DynamicArrayBufferType;
+using vespalib::datastore::EntryCount;
+
+namespace {
+
+struct CleanContextBase
+{
+    std::atomic<size_t> _extra_used_bytes;
+    std::atomic<size_t> _extra_hold_bytes;
+    CleanContextBase()
+        : _extra_used_bytes(0),
+          _extra_hold_bytes(0)
+    {
+    }
+};
+
+struct MyCleanContext : public CleanContextBase,
+                        public BufferTypeBase::CleanContext
+{
+    MyCleanContext()
+        : CleanContextBase(),
+          BufferTypeBase::CleanContext(_extra_used_bytes, _extra_hold_bytes)
+    {
+    }
+};
+
+struct Counts {
+    uint32_t _def_constructs;
+    uint32_t _value_constructs;
+    uint32_t _copy_constructs;
+    uint32_t _destructs;
+    uint32_t _assigns;
+
+    Counts(uint32_t def_constructs, uint32_t value_constructs, uint32_t copy_constructs, uint32_t destructs, uint32_t assigns)
+        : _def_constructs(def_constructs),
+          _value_constructs(value_constructs),
+          _copy_constructs(copy_constructs),
+          _destructs(destructs),
+          _assigns(assigns)
+    {
+    }
+
+    Counts()
+        : Counts(0, 0, 0, 0, 0)
+    {
+    }
+    bool operator==(const Counts &rhs) const {
+        return _def_constructs == rhs._def_constructs &&
+            _value_constructs == rhs._value_constructs &&
+            _copy_constructs == rhs._copy_constructs &&
+            _destructs == rhs._destructs &&
+            _assigns == rhs._assigns;
+    }
+};
+
+Counts counts;
+
+std::ostream& operator<<(std::ostream& os, const Counts& c) {
+    os << "{def_constructs=" << c._def_constructs <<
+        ", value_constructs=" << c._value_constructs <<
+        ", copy_constructs=" << c._copy_constructs <<
+        ", destructs=" << c._destructs <<
+        ", assigns=" << c._assigns << "}";
+    return os;
+}
+
+struct WrapInt32 {
+    int32_t _v;
+
+    WrapInt32()
+        : _v(0)
+    {
+        ++counts._def_constructs;
+    }
+    WrapInt32(int v)
+        : _v(v)
+    {
+        ++counts._value_constructs;
+    }
+    WrapInt32(const WrapInt32& rhs)
+        : _v(rhs._v)
+    {
+        ++counts._copy_constructs;
+    }
+    WrapInt32& operator=(const WrapInt32& rhs) {
+        _v = rhs._v;
+        ++counts._assigns;
+        return *this;
+    }
+    ~WrapInt32() {
+        ++counts._destructs;
+    }
+};
+
+}
+
+class DynamicArrayBufferTypeTest : public testing::Test
+{
+protected:
+    DynamicArrayBufferTypeTest();
+    ~DynamicArrayBufferTypeTest() override;
+
+    using BufferType = DynamicArrayBufferType<WrapInt32>;
+
+    template <typename ElemT>
+    uint32_t get_entry_size(uint32_t array_size);
+
+    std::vector<int> get_vector(const void *buffer, uint32_t offset, uint32_t array_size);
+    std::vector<int> get_vector(const void *buffer, uint32_t offset);
+    std::vector<int> get_max_vector(const void *buffer, uint32_t offset);
+    void write_entry1();
+
+    BufferType              _buffer_type;
+    size_t                  _entry_size;
+    size_t                  _buf_size;
+    std::unique_ptr<char[]> _buf;
+};
+
+DynamicArrayBufferTypeTest::DynamicArrayBufferTypeTest()
+    : testing::Test(),
+      _buffer_type(3, 0, 10, 0, 0.2),
+      _entry_size(_buffer_type.entry_size()),
+      _buf_size(2 * _entry_size),
+      _buf(std::make_unique<char[]>(_buf_size))
+{
+    // Call initialize_reserved_entries to force construction of empty element
+    _buffer_type.initialize_reserved_entries(_buf.get(), 1);
+    memset(_buf.get(), 55, _buf_size);
+    // Reset counts after empty element has been constructed
+    counts = Counts();
+}
+
+DynamicArrayBufferTypeTest::~DynamicArrayBufferTypeTest() = default;
+
+template <typename ElemT>
+uint32_t
+DynamicArrayBufferTypeTest::get_entry_size(uint32_t array_size)
+{
+    DynamicArrayBufferType<ElemT> my_buffer_type(array_size, 0, 10, 0, 0.2);
+    return my_buffer_type.entry_size();
+}
+
+std::vector<int>
+DynamicArrayBufferTypeTest::get_vector(const void* buffer, uint32_t offset, uint32_t array_size)
+{
+    auto e = BufferType::get_entry(buffer, offset, _entry_size);
+    std::vector<int> result;
+    for (uint32_t i = 0; i < array_size; ++i) {
+        result.emplace_back(e[i]._v);
+    }
+    return result;
+}
+
+std::vector<int>
+DynamicArrayBufferTypeTest::get_vector(const void* buffer, uint32_t offset)
+{
+    auto e = BufferType::get_entry(buffer, offset, _entry_size);
+    auto array_size = BufferType::get_dynamic_array_size(e, _entry_size);
+    EXPECT_GE(_buffer_type.getArraySize(), array_size);
+    return get_vector(buffer, offset, array_size);
+}
+
+std::vector<int>
+DynamicArrayBufferTypeTest::get_max_vector(const void* buffer, uint32_t offset)
+{
+    auto array_size = _buffer_type.getArraySize();
+    return get_vector(buffer, offset, array_size);
+}
+
+void
+DynamicArrayBufferTypeTest::write_entry1()
+{
+    auto e1 = BufferType::get_entry(_buf.get(), 1, _entry_size);
+    BufferType::set_dynamic_array_size(e1, _entry_size, 2);
+    new (static_cast<void *>(e1)) WrapInt32(42);
+    new (static_cast<void *>(e1 + 1)) WrapInt32(47);
+    new (static_cast<void *>(e1 + 2)) WrapInt32(49); // Not cleaned by clean_hold
+}
+
+TEST_F(DynamicArrayBufferTypeTest, entry_size_is_calculated)
+{
+    EXPECT_EQ(8, get_entry_size<char>(1));
+    EXPECT_EQ(8, get_entry_size<char>(2));
+    EXPECT_EQ(8, get_entry_size<char>(3));
+    EXPECT_EQ(8, get_entry_size<char>(4));
+    EXPECT_EQ(12, get_entry_size<char>(5));
+    EXPECT_EQ(8, get_entry_size<int16_t>(1));
+    EXPECT_EQ(8, get_entry_size<int16_t>(2));
+    EXPECT_EQ(12, get_entry_size<int16_t>(3));
+    EXPECT_EQ(8, get_entry_size<int32_t>(1));
+    EXPECT_EQ(12, get_entry_size<int32_t>(2));
+    EXPECT_EQ(16, get_entry_size<int64_t>(1));
+    EXPECT_EQ(24, get_entry_size<int64_t>(2));
+    EXPECT_EQ(20, get_entry_size<WrapInt32>(4));
+}
+
+TEST_F(DynamicArrayBufferTypeTest, initialize_reserved_entries)
+{
+    _buffer_type.initialize_reserved_entries(_buf.get(), 2);
+    EXPECT_EQ((std::vector<int>{}), get_vector(_buf.get(), 0));
+    EXPECT_EQ((std::vector<int>{}), get_vector(_buf.get(), 1));
+    EXPECT_EQ((std::vector<int>{0, 0, 0}), get_max_vector(_buf.get(), 0));
+    EXPECT_EQ((std::vector<int>{0, 0, 0}), get_max_vector(_buf.get(), 1));
+    EXPECT_EQ(Counts(0, 0, 6, 0, 0), counts);
+}
+
+TEST_F(DynamicArrayBufferTypeTest, fallback_copy)
+{
+    _buffer_type.initialize_reserved_entries(_buf.get(), 1);
+    write_entry1();
+    EXPECT_EQ(Counts(0, 3, 3, 0, 0), counts);
+    auto buf2 = std::make_unique<char[]>(_buf_size);
+    _buffer_type.fallback_copy(buf2.get(), _buf.get(), 2);
+    EXPECT_EQ((std::vector<int>{}), get_vector(buf2.get(), 0));
+    EXPECT_EQ((std::vector<int>{42, 47}), get_vector(buf2.get(), 1));
+    EXPECT_EQ((std::vector<int>{0, 0, 0}), get_max_vector(buf2.get(), 0));
+    EXPECT_EQ((std::vector<int>{42, 47, 49}), get_max_vector(buf2.get(), 1));
+    EXPECT_EQ(Counts(0, 3, 9, 0, 0), counts);
+}
+
+TEST_F(DynamicArrayBufferTypeTest, destroy_entries)
+{
+    _buffer_type.initialize_reserved_entries(_buf.get(), 2);
+    write_entry1();
+    _buffer_type.destroy_entries(_buf.get(), 2);
+    EXPECT_EQ(Counts(0, 3, 6, 6, 0), counts);
+}
+
+TEST_F(DynamicArrayBufferTypeTest, clean_hold)
+{
+    _buffer_type.initialize_reserved_entries(_buf.get(), 1);
+    write_entry1();
+    MyCleanContext clean_context;
+    _buffer_type.clean_hold(_buf.get(), 1, 1, clean_context);
+    EXPECT_EQ((std::vector<int>{0, 0}), get_vector(_buf.get(), 1));
+    EXPECT_EQ((std::vector<int>{0, 0, 49}), get_max_vector(_buf.get(), 1));
+    EXPECT_EQ(Counts(0, 3, 3, 0, 2), counts);
+    _buffer_type.clean_hold(_buf.get(), 0, 2, clean_context);
+    EXPECT_EQ(Counts(0, 3, 3, 0, 4), counts);
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt b/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt
index 1c3b9112dda..8b76c576cf0 100644
--- a/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt
+++ b/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt
@@ -16,6 +16,7 @@ vespa_add_library(vespalib_vespalib_datastore OBJECT
     compaction_strategy.cpp
     datastore.cpp
     datastorebase.cpp
+    dynamic_array_buffer_type.cpp
     entry_ref_filter.cpp
     entryref.cpp
     fixed_size_hash_map.cpp
diff --git a/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.cpp b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.cpp
new file mode 100644
index 00000000000..df2129e8ff2
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.cpp
@@ -0,0 +1,17 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "dynamic_array_buffer_type.hpp"
+
+namespace vespalib::datastore {
+
+template class DynamicArrayBufferType<char>;
+template class DynamicArrayBufferType<int8_t>;
+template class DynamicArrayBufferType<int16_t>;
+template class DynamicArrayBufferType<int32_t>;
+template class DynamicArrayBufferType<int64_t>;
+template class DynamicArrayBufferType<float>;
+template class DynamicArrayBufferType<double>;
+template class DynamicArrayBufferType<AtomicEntryRef>;
+
+}
+
diff --git a/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.h b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.h
new file mode 100644
index 00000000000..7e2c70b2374
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.h
@@ -0,0 +1,57 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "buffer_type.h"
+
+namespace vespalib::datastore {
+
+/**
+ * Concrete class used to manage allocation and de-allocation of
+ * elements of type ElemType in data store buffers.
+ *
+ * Layout of each entry is:
+ *
+ * elements[array_size]                - array of elements in entry
+ * padding                             - to align entries
+ * dynamic_array_size                  - number of array elements that should
+ *                                       be visible to reader.
+ */
+template <typename ElemT>
+class DynamicArrayBufferType : public BufferTypeBase
+{
+public:
+    using ElemType = ElemT;
+protected:
+    static const ElemType& empty_entry() noexcept;
+    ElemType* get_entry(void *buffer, size_t offset) noexcept { return get_entry(buffer, offset, entry_size()); }
+    const ElemType* get_entry(const void *buffer, size_t offset) const noexcept { return get_entry(buffer, offset, entry_size()); }
+public:
+    DynamicArrayBufferType(const DynamicArrayBufferType &rhs) = delete;
+    DynamicArrayBufferType & operator=(const DynamicArrayBufferType &rhs) = delete;
+    DynamicArrayBufferType(DynamicArrayBufferType && rhs) noexcept = default;
+    DynamicArrayBufferType & operator=(DynamicArrayBufferType && rhs) noexcept = default;
+    DynamicArrayBufferType(uint32_t array_size, uint32_t min_entries, uint32_t max_entries,
+                           uint32_t num_entries_for_new_buffer, float allocGrowFactor) noexcept;
+    ~DynamicArrayBufferType() override;
+    void destroy_entries(void* buffer, EntryCount num_entries) override;
+    void fallback_copy(void* new_buffer, const void* old_buffer, EntryCount num_entries) override;
+    void initialize_reserved_entries(void* buffer, EntryCount reserved_entries) override;
+    void clean_hold(void* buffer, size_t offset, EntryCount num_entries, CleanContext cleanCxt) override;
+    static uint32_t calc_entry_size(uint32_t array_size) noexcept;
+    static ElemType* get_entry(void* buffer, size_t offset, uint32_t entry_size) noexcept { return reinterpret_cast<ElemType*>(static_cast<char*>(buffer) + offset * entry_size); }
+    static const ElemType* get_entry(const void* buffer, size_t offset, uint32_t entry_size) noexcept { return reinterpret_cast<const ElemType*>(static_cast<const char*>(buffer) + offset * entry_size); }
+    static uint32_t get_dynamic_array_size(const void *buffer, uint32_t entry_size) noexcept { return *reinterpret_cast<const uint32_t*>(static_cast<const char*>(buffer) + entry_size - sizeof(uint32_t)); }
+    static void set_dynamic_array_size(void *buffer, uint32_t entry_size, uint32_t array_size) noexcept { *reinterpret_cast<uint32_t*>(static_cast<char*>(buffer) + entry_size - sizeof(uint32_t)) = array_size; }
+};
+
+extern template class DynamicArrayBufferType<char>;
+extern template class DynamicArrayBufferType<int8_t>;
+extern template class DynamicArrayBufferType<int16_t>;
+extern template class DynamicArrayBufferType<int32_t>;
+extern template class DynamicArrayBufferType<int64_t>;
+extern template class DynamicArrayBufferType<float>;
+extern template class DynamicArrayBufferType<double>;
+extern template class DynamicArrayBufferType<AtomicEntryRef>;
+
+}
diff --git a/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.hpp b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.hpp
new file mode 100644
index 00000000000..9085e32db6b
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/dynamic_array_buffer_type.hpp
@@ -0,0 +1,104 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "dynamic_array_buffer_type.h"
+#include "aligner.h"
+#include <algorithm>
+#include <cassert>
+
+namespace vespalib::datastore {
+
+template <typename ElemT>
+DynamicArrayBufferType<ElemT>::DynamicArrayBufferType(uint32_t array_size, uint32_t min_entries, uint32_t max_entries,
+                                  uint32_t num_entries_for_new_buffer, float allocGrowFactor) noexcept
+    : BufferTypeBase(calc_entry_size(array_size), array_size, min_entries, max_entries, num_entries_for_new_buffer, allocGrowFactor)
+{ }
+
+template <typename ElemT>
+DynamicArrayBufferType<ElemT>::~DynamicArrayBufferType() = default;
+
+template <typename ElemT>
+uint32_t
+DynamicArrayBufferType<ElemT>::calc_entry_size(uint32_t array_size) noexcept
+{
+    Aligner aligner(std::max(alignof(uint32_t), alignof(ElemType)));
+    return aligner.align(sizeof(ElemType) * array_size + sizeof(uint32_t));
+}
+
+template <typename ElemT>
+void
+DynamicArrayBufferType<ElemT>::destroy_entries(void* buffer, EntryCount num_entries)
+{
+    uint32_t array_size = _arraySize;
+    for (uint32_t entry_idx = 0; entry_idx < num_entries; ++entry_idx) {
+        auto e = get_entry(buffer, entry_idx);
+        for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) {
+            e->~ElemType();
+            ++e;
+        }
+    }
+}
+
+template <typename ElemT>
+void
+DynamicArrayBufferType<ElemT>::fallback_copy(void* new_buffer, const void* old_buffer, EntryCount num_entries)
+{
+    uint32_t array_size = _arraySize;
+    for (uint32_t entry_idx = 0; entry_idx < num_entries; ++entry_idx) {
+        auto d = get_entry(new_buffer, entry_idx);
+        auto s = get_entry(old_buffer, entry_idx);
+        set_dynamic_array_size(d, entry_size(), get_dynamic_array_size(s, entry_size()));
+        for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) {
+            new (static_cast<void*>(d)) ElemType(*s);
+            ++s;
+            ++d;
+        }
+    }
+}
+
+template <typename ElemT>
+void
+DynamicArrayBufferType<ElemT>::initialize_reserved_entries(void* buffer, EntryCount reserved_entries)
+{
+    uint32_t array_size = _arraySize;
+    const auto& empty = empty_entry();
+    for (uint32_t entry_idx = 0; entry_idx < reserved_entries; ++entry_idx) {
+        auto e = get_entry(buffer, entry_idx);
+        set_dynamic_array_size(e, entry_size(), 0);
+        for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) {
+            new (static_cast<void*>(e)) ElemType(empty);
+            ++e;
+        }
+    }
+}
+
+template <typename ElemT>
+void
+DynamicArrayBufferType<ElemT>::clean_hold(void* buffer, size_t offset, EntryCount num_entries, CleanContext)
+{
+    uint32_t max_array_size = _arraySize;
+    const auto& empty = empty_entry();
+    for (uint32_t entry_idx = 0; entry_idx < num_entries; ++entry_idx) {
+        auto e = get_entry(buffer, offset + entry_idx);
+        auto array_size = get_dynamic_array_size(e, entry_size());
+        assert(array_size <= max_array_size);
+        for (uint32_t elem_idx = 0; elem_idx < array_size; ++elem_idx) {
+            *e = empty;
+            ++e;
+        }
+    }
+}
+
+template <typename ElemT>
+const ElemT&
+DynamicArrayBufferType<ElemT>::empty_entry() noexcept
+{
+    // It's possible for ElemType to wrap e.g. an Alloc instance, which has a transitive
+    // dependency on globally constructed allocator object(s). To avoid issues with global
+    // construction order, initialize the sentinel on the first access.
+    static ElemType empty = ElemType();
+    return empty;
+}
+
+}