Merge pull request #9516 from vespa-engine/vekterli/move-rcuvector-to-vespalib

Move RcuVector and relevant support classes to vespalib

10 files changed, 823 insertions, 0 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index a395e3aab45..8cd83866a8e 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -120,6 +120,7 @@ vespa_define_module(
     src/tests/util/generationhandler
     src/tests/util/generationhandler_stress
     src/tests/util/md5
+    src/tests/util/rcuvector
     src/tests/valgrind
     src/tests/websocket
     src/tests/zcurve
diff --git a/vespalib/src/tests/util/rcuvector/.gitignore b/vespalib/src/tests/util/rcuvector/.gitignore
new file mode 100644
index 00000000000..2c1661a8461
--- /dev/null
+++ b/vespalib/src/tests/util/rcuvector/.gitignore
@@ -0,0 +1,5 @@
+.depend	
+Makefile	
+rcuvector_test	
+vespalib_rcuvector_test_app
+
diff --git a/vespalib/src/tests/util/rcuvector/CMakeLists.txt b/vespalib/src/tests/util/rcuvector/CMakeLists.txt
new file mode 100644
index 00000000000..77900b8422d
--- /dev/null
+++ b/vespalib/src/tests/util/rcuvector/CMakeLists.txt
@@ -0,0 +1,8 @@
+# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_rcuvector_test_app TEST
+    SOURCES
+    rcuvector_test.cpp
+    DEPENDS
+    searchlib
+)
+vespa_add_test(NAME vespalib_rcuvector_test_app COMMAND vespalib_rcuvector_test_app)
diff --git a/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp b/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp
new file mode 100644
index 00000000000..4cbfbfebd3c
--- /dev/null
+++ b/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp
@@ -0,0 +1,296 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/testkit/testapp.h>
+#include <vespa/vespalib/util/rcuvector.h>
+
+using namespace vespalib;
+
+bool
+assertUsage(const MemoryUsage & exp, const MemoryUsage & act)
+{
+    bool retval = true;
+    if (!EXPECT_EQUAL(exp.allocatedBytes(), act.allocatedBytes())) retval = false;
+    if (!EXPECT_EQUAL(exp.usedBytes(), act.usedBytes())) retval = false;
+    if (!EXPECT_EQUAL(exp.deadBytes(), act.deadBytes())) retval = false;
+    if (!EXPECT_EQUAL(exp.allocatedBytesOnHold(), act.allocatedBytesOnHold())) retval = false;
+    return retval;
+}
+
+TEST("test generation holder")
+{
+    typedef std::unique_ptr<int32_t> IntPtr;
+    GenerationHolder gh;
+    gh.hold(GenerationHeldBase::UP(new RcuVectorHeld<int32_t>(sizeof(int32_t),
+                                           IntPtr(new int32_t(0)))));
+    gh.transferHoldLists(0);
+    gh.hold(GenerationHeldBase::UP(new RcuVectorHeld<int32_t>(sizeof(int32_t),
+                                           IntPtr(new int32_t(1)))));
+    gh.transferHoldLists(1);
+    gh.hold(GenerationHeldBase::UP(new RcuVectorHeld<int32_t>(sizeof(int32_t),
+                                           IntPtr(new int32_t(2)))));
+    gh.transferHoldLists(2);
+    gh.hold(GenerationHeldBase::UP(new RcuVectorHeld<int32_t>(sizeof(int32_t),
+                                           IntPtr(new int32_t(4)))));
+    gh.transferHoldLists(4);
+    EXPECT_EQUAL(4u * sizeof(int32_t), gh.getHeldBytes());
+    gh.trimHoldLists(0);
+    EXPECT_EQUAL(4u * sizeof(int32_t), gh.getHeldBytes());
+    gh.trimHoldLists(1);
+    EXPECT_EQUAL(3u * sizeof(int32_t), gh.getHeldBytes());
+    gh.trimHoldLists(2);
+    EXPECT_EQUAL(2u * sizeof(int32_t), gh.getHeldBytes());
+    gh.hold(GenerationHeldBase::UP(new RcuVectorHeld<int32_t>(sizeof(int32_t),
+                                       IntPtr(new int32_t(6)))));
+    gh.transferHoldLists(6);
+    EXPECT_EQUAL(3u * sizeof(int32_t), gh.getHeldBytes());
+    gh.trimHoldLists(6);
+    EXPECT_EQUAL(1u * sizeof(int32_t), gh.getHeldBytes());
+    gh.trimHoldLists(7);
+    EXPECT_EQUAL(0u * sizeof(int32_t), gh.getHeldBytes());
+    gh.trimHoldLists(7);
+    EXPECT_EQUAL(0u * sizeof(int32_t), gh.getHeldBytes());
+}
+
+TEST("test basic")
+{
+    { // insert
+        RcuVector<int32_t> v(4, 0, 4);
+        for (int32_t i = 0; i < 100; ++i) {
+            v.push_back(i);
+            EXPECT_EQUAL(i, v[i]);
+            EXPECT_EQUAL((size_t)i + 1, v.size());
+        }
+        for (int32_t i = 0; i < 100; ++i) {
+            v[i] = i + 1;
+            EXPECT_EQUAL(i + 1, v[i]);
+            EXPECT_EQUAL(100u, v.size());
+        }
+    }
+}
+
+TEST("test resize")
+{
+    { // resize percent
+        RcuVector<int32_t> v(2, 50, 0);
+        EXPECT_EQUAL(2u, v.capacity());
+        v.push_back(0);
+        EXPECT_EQUAL(2u, v.capacity());
+        v.push_back(0);
+        EXPECT_EQUAL(2u, v.capacity());
+        EXPECT_TRUE(v.isFull());
+        v.push_back(0);
+        EXPECT_EQUAL(3u, v.capacity());
+        EXPECT_TRUE(v.isFull());
+    }
+    { // resize delta
+        RcuVector<int32_t> v(1, 0, 3);
+        EXPECT_EQUAL(1u, v.capacity());
+        v.push_back(0);
+        EXPECT_EQUAL(1u, v.capacity());
+        EXPECT_TRUE(v.isFull());
+        v.push_back(0);
+        EXPECT_EQUAL(4u, v.capacity());
+        EXPECT_TRUE(!v.isFull());
+    }
+    { // resize both
+        RcuVector<int32_t> v(2, 200, 3);
+        EXPECT_EQUAL(2u, v.capacity());
+        v.push_back(0);
+        EXPECT_EQUAL(2u, v.capacity());
+        v.push_back(0);
+        EXPECT_EQUAL(2u, v.capacity());
+        EXPECT_TRUE(v.isFull());
+        v.push_back(0);
+        EXPECT_EQUAL(9u, v.capacity());
+        EXPECT_TRUE(!v.isFull());
+    }
+    { // reserve
+        RcuVector<int32_t> v(2, 0, 0);
+        EXPECT_EQUAL(2u, v.capacity());
+        v.unsafe_reserve(8);
+        EXPECT_EQUAL(8u, v.capacity());
+    }
+    { // explicit resize
+        GenerationHolder g;
+        RcuVectorBase<int8_t> v(g);
+        v.push_back(1);
+        v.push_back(2);
+        g.transferHoldLists(0);
+        g.trimHoldLists(1);
+        const int8_t *old = &v[0];
+        EXPECT_EQUAL(16u, v.capacity());
+        EXPECT_EQUAL(2u, v.size());
+        v.ensure_size(32, 3);
+        v[0] = 3;
+        v[1] = 3;
+        g.transferHoldLists(1);
+        EXPECT_EQUAL(1, old[0]);
+        EXPECT_EQUAL(2, old[1]);
+        EXPECT_EQUAL(3, v[0]);
+        EXPECT_EQUAL(3, v[1]);
+        EXPECT_EQUAL(3, v[2]);
+        EXPECT_EQUAL(3, v[31]);
+        EXPECT_EQUAL(64u, v.capacity());
+        EXPECT_EQUAL(32u, v.size());
+        g.trimHoldLists(2);
+    }
+}
+
+TEST("test generation handling")
+{
+    RcuVector<int32_t> v(2, 0, 2);
+    v.push_back(0);
+    v.push_back(10);
+    EXPECT_EQUAL(0u, v.getMemoryUsage().allocatedBytesOnHold());
+    v.push_back(20); // new array
+    EXPECT_EQUAL(8u, v.getMemoryUsage().allocatedBytesOnHold());
+
+    v.setGeneration(1);
+    v.push_back(30);
+    EXPECT_EQUAL(8u, v.getMemoryUsage().allocatedBytesOnHold());
+    v.push_back(40); // new array
+    EXPECT_EQUAL(24u, v.getMemoryUsage().allocatedBytesOnHold());
+
+    v.setGeneration(2);
+    v.push_back(50);
+    v.removeOldGenerations(3);
+    EXPECT_EQUAL(0u, v.getMemoryUsage().allocatedBytesOnHold());
+    v.push_back(60); // new array
+    EXPECT_EQUAL(24u, v.getMemoryUsage().allocatedBytesOnHold());
+}
+
+TEST("test reserve") {
+    RcuVector<int32_t> v(2, 0, 2);
+    EXPECT_EQUAL(2u, v.capacity());
+    EXPECT_EQUAL(0u, v.size());
+    v.push_back(0);
+    v.push_back(10);
+    EXPECT_EQUAL(2u, v.size());
+    EXPECT_EQUAL(2u, v.capacity());
+    EXPECT_EQUAL(0u, v.getMemoryUsage().allocatedBytesOnHold());
+    v.reserve(30);
+    EXPECT_EQUAL(2u, v.size());
+    EXPECT_EQUAL(32u, v.capacity());
+    EXPECT_EQUAL(8u, v.getMemoryUsage().allocatedBytesOnHold());
+    v.reserve(32);
+    EXPECT_EQUAL(2u, v.size());
+    EXPECT_EQUAL(32u, v.capacity());
+    EXPECT_EQUAL(8u, v.getMemoryUsage().allocatedBytesOnHold());
+    v.reserve(100);
+    EXPECT_EQUAL(2u, v.size());
+    EXPECT_EQUAL(102u, v.capacity());
+    EXPECT_EQUAL(8u + 32u*4u, v.getMemoryUsage().allocatedBytesOnHold());
+}
+
+TEST("test memory usage")
+{
+    RcuVector<int8_t> v(2, 0, 2);
+    EXPECT_TRUE(assertUsage(MemoryUsage(2,0,0,0), v.getMemoryUsage()));
+    v.push_back(0);
+    EXPECT_TRUE(assertUsage(MemoryUsage(2,1,0,0), v.getMemoryUsage()));
+    v.push_back(1);
+    EXPECT_TRUE(assertUsage(MemoryUsage(2,2,0,0), v.getMemoryUsage()));
+    v.push_back(2);
+    EXPECT_TRUE(assertUsage(MemoryUsage(6,5,0,2), v.getMemoryUsage()));
+    v.push_back(3);
+    EXPECT_TRUE(assertUsage(MemoryUsage(6,6,0,2), v.getMemoryUsage()));
+    v.push_back(4);
+    EXPECT_TRUE(assertUsage(MemoryUsage(12,11,0,6), v.getMemoryUsage()));
+    v.removeOldGenerations(1);
+    EXPECT_TRUE(assertUsage(MemoryUsage(6,5,0,0), v.getMemoryUsage()));
+}
+
+TEST("test shrink() with buffer copying")
+{
+    GenerationHolder g;
+    RcuVectorBase<int8_t> v(16, 100, 0, g);
+    v.push_back(1);
+    v.push_back(2);
+    v.push_back(3);
+    v.push_back(4);
+    g.transferHoldLists(0);
+    g.trimHoldLists(1);
+    MemoryUsage mu;
+    mu = v.getMemoryUsage();
+    mu.incAllocatedBytesOnHold(g.getHeldBytes());
+    EXPECT_TRUE(assertUsage(MemoryUsage(16, 4, 0, 0), mu));
+    EXPECT_EQUAL(4u, v.size());
+    EXPECT_EQUAL(16u, v.capacity());
+    EXPECT_EQUAL(1, v[0]);
+    EXPECT_EQUAL(2, v[1]);
+    EXPECT_EQUAL(3, v[2]);
+    EXPECT_EQUAL(4, v[3]);
+    const int8_t *old = &v[0];
+    v.shrink(2);
+    g.transferHoldLists(1);
+    EXPECT_EQUAL(2u, v.size());
+    EXPECT_EQUAL(4u, v.capacity());
+    EXPECT_EQUAL(1, v[0]);
+    EXPECT_EQUAL(2, v[1]);
+    EXPECT_EQUAL(1, old[0]);
+    EXPECT_EQUAL(2, old[1]);
+    g.trimHoldLists(2);
+    EXPECT_EQUAL(1, v[0]);
+    EXPECT_EQUAL(2, v[1]);
+    mu = v.getMemoryUsage();
+    mu.incAllocatedBytesOnHold(g.getHeldBytes());
+    EXPECT_TRUE(assertUsage(MemoryUsage(4, 2, 0, 0), mu));
+}
+
+struct ShrinkFixture {
+    GenerationHolder g;
+    RcuVectorBase<int> vec;
+    int *oldPtr;
+    ShrinkFixture() : g(), vec(4096, 50, 0, g, alloc::Alloc::allocMMap()), oldPtr()
+    {
+        for (size_t i = 0; i < 4000; ++i) {
+            vec.push_back(7);
+        }
+        EXPECT_EQUAL(4000u, vec.size());
+        EXPECT_EQUAL(4096u, vec.capacity());
+        assertEmptyHoldList();
+        oldPtr = &vec[0];
+    }
+    void assertOldEqualNewBuffer() {
+        EXPECT_EQUAL(oldPtr, &vec[0]);
+    }
+    void assertEmptyHoldList() {
+        EXPECT_EQUAL(0u, g.getHeldBytes());
+    }
+};
+
+TEST_F("require that shrink() does not increase allocated memory", ShrinkFixture)
+{
+    f.vec.shrink(2732);
+    EXPECT_EQUAL(2732u, f.vec.size());
+    EXPECT_EQUAL(4096u, f.vec.capacity());
+    TEST_DO(f.assertOldEqualNewBuffer());
+    TEST_DO(f.assertEmptyHoldList());
+}
+
+TEST_F("require that shrink() can shrink mmap allocation", ShrinkFixture)
+{
+    f.vec.shrink(2048);
+    EXPECT_EQUAL(2048u, f.vec.size());
+    EXPECT_EQUAL(3072u, f.vec.capacity());
+    TEST_DO(f.assertOldEqualNewBuffer());
+    TEST_DO(f.assertEmptyHoldList());
+}
+
+TEST("test small expand")
+{
+    GenerationHolder g;
+    RcuVectorBase<int8_t> v(1, 50, 0, g);
+    EXPECT_EQUAL(1u, v.capacity());
+    EXPECT_EQUAL(0u, v.size());
+    v.push_back(1);
+    EXPECT_EQUAL(1u, v.capacity());
+    EXPECT_EQUAL(1u, v.size());
+    v.push_back(2);
+    EXPECT_EQUAL(2u, v.capacity());
+    EXPECT_EQUAL(2u, v.size());
+    g.transferHoldLists(1);
+    g.trimHoldLists(2);
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }
diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
index 2f64e01d79c..f8e06751c2a 100644
--- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt
+++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
@@ -31,6 +31,7 @@ vespa_add_library(vespalib_vespalib_util OBJECT
     printable.cpp
     priority_queue.cpp
     random.cpp
+    rcuvector.cpp
     regexp.cpp
     runnable.cpp
     runnable_pair.cpp
diff --git a/vespalib/src/vespa/vespalib/util/growstrategy.h b/vespalib/src/vespa/vespalib/util/growstrategy.h
new file mode 100644
index 00000000000..bb3b9196997
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/growstrategy.h
@@ -0,0 +1,47 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <cstdint>
+
+namespace vespalib {
+
+class GrowStrategy {
+private:
+    size_t _initialCapacity;
+    float  _growFactor;
+    size_t _growDelta;
+public:
+    GrowStrategy() noexcept
+        : GrowStrategy(1024, 0.5, 0)
+    {}
+    GrowStrategy(size_t initialCapacity, float growPercent, size_t growDelta) noexcept
+        : _initialCapacity(initialCapacity),
+          _growFactor(growPercent),
+          _growDelta(growDelta)
+    {
+    }
+
+    static GrowStrategy make(size_t initialCapacity, float growFactor, size_t growDelta) noexcept {
+        return GrowStrategy(initialCapacity, growFactor, growDelta);
+    }
+
+    size_t getInitialCapacity() const noexcept { return _initialCapacity; }
+    size_t     getGrowPercent() const noexcept { return _growFactor*100; }
+    float       getGrowFactor() const noexcept { return _growFactor; }
+    size_t       getGrowDelta() const noexcept { return _growDelta; }
+    void setInitialCapacity(size_t v) noexcept { _initialCapacity = v; }
+    void       setGrowDelta(size_t v) noexcept { _growDelta = v; }
+
+    bool operator==(const GrowStrategy & rhs) const noexcept {
+        return (_initialCapacity == rhs._initialCapacity &&
+                _growFactor == rhs._growFactor &&
+                _growDelta == rhs._growDelta);
+    }
+    bool operator!=(const GrowStrategy & rhs) const noexcept {
+        return !(operator==(rhs));
+    }
+};
+
+}
+
diff --git a/vespalib/src/vespa/vespalib/util/memoryusage.h b/vespalib/src/vespa/vespalib/util/memoryusage.h
new file mode 100644
index 00000000000..84bf39fde10
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/memoryusage.h
@@ -0,0 +1,60 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <cstddef>
+
+namespace vespalib {
+
+class MemoryUsage {
+private:
+    size_t _allocatedBytes;
+    size_t _usedBytes;
+    size_t _deadBytes;
+    size_t _allocatedBytesOnHold;
+
+public:
+    MemoryUsage()
+        : _allocatedBytes(0),
+          _usedBytes(0),
+          _deadBytes(0),
+          _allocatedBytesOnHold(0)
+    { }
+
+    MemoryUsage(size_t allocated, size_t used, size_t dead, size_t onHold)
+        : _allocatedBytes(allocated),
+          _usedBytes(used),
+          _deadBytes(dead),
+          _allocatedBytesOnHold(onHold)
+    { }
+
+    size_t allocatedBytes() const { return _allocatedBytes; }
+    size_t usedBytes() const { return _usedBytes; }
+    size_t deadBytes() const { return _deadBytes; }
+    size_t allocatedBytesOnHold() const { return _allocatedBytesOnHold; }
+    void incAllocatedBytes(size_t inc) { _allocatedBytes += inc; }
+    void decAllocatedBytes(size_t dec) { _allocatedBytes -= dec; }
+    void incUsedBytes(size_t inc) { _usedBytes += inc; }
+    void incDeadBytes(size_t inc) { _deadBytes += inc; }
+    void incAllocatedBytesOnHold(size_t inc) { _allocatedBytesOnHold += inc; }
+    void decAllocatedBytesOnHold(size_t inc) { _allocatedBytesOnHold -= inc; }
+    void setAllocatedBytes(size_t alloc) { _allocatedBytes = alloc; }
+    void setUsedBytes(size_t used) { _usedBytes = used; }
+    void setDeadBytes(size_t dead) { _deadBytes = dead; }
+    void setAllocatedBytesOnHold(size_t onHold) { _allocatedBytesOnHold = onHold; }
+
+    void mergeGenerationHeldBytes(size_t inc) {
+        _allocatedBytes += inc;
+        _usedBytes += inc;
+        _allocatedBytesOnHold += inc;
+    }
+
+    void merge(const MemoryUsage & rhs) {
+        _allocatedBytes += rhs._allocatedBytes;
+        _usedBytes += rhs._usedBytes;
+        _deadBytes += rhs._deadBytes;
+        _allocatedBytesOnHold += rhs._allocatedBytesOnHold;
+    }
+};
+
+} // namespace vespalib
diff --git a/vespalib/src/vespa/vespalib/util/rcuvector.cpp b/vespalib/src/vespa/vespalib/util/rcuvector.cpp
new file mode 100644
index 00000000000..4c3c7e45709
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/rcuvector.cpp
@@ -0,0 +1,37 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "rcuvector.hpp"
+
+namespace vespalib {
+
+template class RcuVectorBase<uint8_t>;
+template class RcuVectorBase<uint16_t>;
+template class RcuVectorBase<uint32_t>;
+template class RcuVectorBase<int8_t>;
+template class RcuVectorBase<int16_t>;
+template class RcuVectorBase<int32_t>;
+template class RcuVectorBase<int64_t>;
+template class RcuVectorBase<float>;
+template class RcuVectorBase<double>;
+
+template class RcuVector<uint8_t>;
+template class RcuVector<uint16_t>;
+template class RcuVector<uint32_t>;
+template class RcuVector<int8_t>;
+template class RcuVector<int16_t>;
+template class RcuVector<int32_t>;
+template class RcuVector<int64_t>;
+template class RcuVector<float>;
+template class RcuVector<double>;
+
+template class RcuVectorHeld<uint8_t>;
+template class RcuVectorHeld<uint16_t>;
+template class RcuVectorHeld<uint32_t>;
+template class RcuVectorHeld<int8_t>;
+template class RcuVectorHeld<int16_t>;
+template class RcuVectorHeld<int32_t>;
+template class RcuVectorHeld<int64_t>;
+template class RcuVectorHeld<float>;
+template class RcuVectorHeld<double>;
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/rcuvector.h b/vespalib/src/vespa/vespalib/util/rcuvector.h
new file mode 100644
index 00000000000..1ccfba2bb23
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/rcuvector.h
@@ -0,0 +1,163 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "alloc.h"
+#include "array.h"
+#include "generationholder.h"
+#include "growstrategy.h"
+#include "memoryusage.h"
+
+namespace vespalib {
+
+template <typename T>
+class RcuVectorHeld : public GenerationHeldBase
+{
+    std::unique_ptr<T> _data;
+
+public:
+    RcuVectorHeld(size_t size, std::unique_ptr<T> data);
+
+    ~RcuVectorHeld();
+};
+
+
+/**
+ * Vector class for elements of type T using the read-copy-update
+ * mechanism to ensure that reader threads will have a consistent view
+ * of the vector while the update thread is inserting new elements.
+ * The update thread is also responsible for updating the current
+ * generation of the vector, and initiating removing of old underlying
+ * data vectors.
+ **/
+template <typename T>
+class RcuVectorBase
+{
+private:
+    static_assert(std::is_trivially_destructible<T>::value,
+                  "Value type must be trivially destructible");
+
+    using ArrayType = Array<T>;
+    using Alloc = alloc::Alloc;
+protected:
+    using generation_t = GenerationHandler::generation_t;
+    using GenerationHolderType = GenerationHolder;
+private:
+    ArrayType             _data;
+    size_t                _growPercent;
+    size_t                _growDelta;
+    GenerationHolderType &_genHolder;
+
+    size_t calcNewSize(size_t baseSize) const {
+        size_t delta = (baseSize * _growPercent / 100) + _growDelta;
+        return baseSize + std::max(delta, static_cast<size_t>(1));
+    }
+    size_t calcNewSize() const {
+        return calcNewSize(_data.capacity());
+    }
+    void expand(size_t newCapacity);
+    void expandAndInsert(const T & v);
+    virtual void onReallocation();
+
+public:
+    using ValueType = T;
+    RcuVectorBase(GenerationHolderType &genHolder,
+                  const Alloc &initialAlloc = Alloc::alloc());
+
+    /**
+     * Construct a new vector with the given initial capacity and grow
+     * parameters.
+     *
+     * New capacity is calculated based on old capacity and grow parameters:
+     * nc = oc + (oc * growPercent / 100) + growDelta.
+     **/
+    RcuVectorBase(size_t initialCapacity, size_t growPercent, size_t growDelta,
+                  GenerationHolderType &genHolder,
+                  const Alloc &initialAlloc = Alloc::alloc());
+
+    RcuVectorBase(GrowStrategy growStrategy,
+                  GenerationHolderType &genHolder,
+                  const Alloc &initialAlloc = Alloc::alloc());
+
+    virtual ~RcuVectorBase();
+
+    /**
+     * Return whether all capacity has been used.  If true the next
+     * call to push_back() will cause an expand of the underlying
+     * data.
+     **/
+    bool isFull() const { return _data.size() == _data.capacity(); }
+
+    /**
+     * Return the combined memory usage for this instance.
+     **/
+    virtual MemoryUsage getMemoryUsage() const;
+
+    // vector interface
+    // no swap method, use reset() to forget old capacity and holds
+    // NOTE: Unsafe resize/reserve may invalidate data references held by readers!
+    void unsafe_resize(size_t n);
+    void unsafe_reserve(size_t n);
+    void ensure_size(size_t n, T fill = T());
+    void reserve(size_t n) {
+        if (n > capacity()) {
+            expand(calcNewSize(n));
+        }
+    }
+    void push_back(const T & v) {
+        if (_data.size() < _data.capacity()) {
+            _data.push_back(v);
+        } else {
+            expandAndInsert(v);
+        }
+    }
+
+    bool empty() const { return _data.empty(); }
+    size_t size() const { return _data.size(); }
+    size_t capacity() const { return _data.capacity(); }
+    void clear() { _data.clear(); }
+    T & operator[](size_t i) { return _data[i]; }
+    const T & operator[](size_t i) const { return _data[i]; }
+
+    void reset();
+    void shrink(size_t newSize) __attribute__((noinline));
+    void replaceVector(std::unique_ptr<ArrayType> replacement);
+};
+
+template <typename T>
+class RcuVector : public RcuVectorBase<T>
+{
+private:
+    using generation_t         = typename RcuVectorBase<T>::generation_t;
+    using GenerationHolderType = typename RcuVectorBase<T>::GenerationHolderType;
+    generation_t         _generation;
+    GenerationHolderType _genHolderStore;
+
+    void onReallocation() override;
+
+public:
+    RcuVector();
+
+    /**
+     * Construct a new vector with the given initial capacity and grow
+     * parameters.
+     *
+     * New capacity is calculated based on old capacity and grow parameters:
+     * nc = oc + (oc * growPercent / 100) + growDelta.
+     **/
+    RcuVector(size_t initialCapacity, size_t growPercent, size_t growDelta);
+    RcuVector(GrowStrategy growStrategy);
+    ~RcuVector();
+
+    generation_t getGeneration() const { return _generation; }
+    void setGeneration(generation_t generation) { _generation = generation; }
+
+    /**
+     * Remove all old data vectors where generation < firstUsed.
+     **/
+    void removeOldGenerations(generation_t firstUsed);
+
+    MemoryUsage getMemoryUsage() const override;
+};
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/rcuvector.hpp b/vespalib/src/vespa/vespalib/util/rcuvector.hpp
new file mode 100644
index 00000000000..f2324c654a4
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/rcuvector.hpp
@@ -0,0 +1,205 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "rcuvector.h"
+#include <vespa/vespalib/util/array.hpp>
+
+namespace vespalib {
+
+template <typename T>
+RcuVectorHeld<T>::RcuVectorHeld(size_t size, std::unique_ptr<T> data)
+    : GenerationHeldBase(size),
+      _data(std::move(data))
+{ }
+
+template <typename T>
+RcuVectorHeld<T>::~RcuVectorHeld() = default;
+
+template <typename T>
+void
+RcuVectorBase<T>::unsafe_resize(size_t n) {
+    _data.resize(n);
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::unsafe_reserve(size_t n) {
+    _data.reserve(n);
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::ensure_size(size_t n, T fill) {
+    reserve(n);
+    while (size() < n) {
+        _data.push_back(fill);
+    }
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::reset() {
+    // Assumes no readers at this moment
+    ArrayType().swap(_data);
+    _data.reserve(16);
+}
+
+template <typename T>
+RcuVectorBase<T>::~RcuVectorBase() = default;
+
+template <typename T>
+void
+RcuVectorBase<T>::expand(size_t newCapacity) {
+    std::unique_ptr<ArrayType> tmpData(new ArrayType());
+    tmpData->reserve(newCapacity);
+    for (const T & v : _data) {
+        tmpData->push_back_fast(v);
+    }
+    replaceVector(std::move(tmpData));
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::replaceVector(std::unique_ptr<ArrayType> replacement) {
+    replacement->swap(_data); // atomic switch of underlying data
+    size_t holdSize = replacement->capacity() * sizeof(T);
+    GenerationHeldBase::UP hold(new RcuVectorHeld<ArrayType>(holdSize, std::move(replacement)));
+    _genHolder.hold(std::move(hold));
+    onReallocation();
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::expandAndInsert(const T & v)
+{
+    expand(calcNewSize());
+    assert(_data.size() < _data.capacity());
+    _data.push_back(v);
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::shrink(size_t newSize)
+{
+    assert(newSize <= _data.size());
+    _data.resize(newSize);
+    size_t wantedCapacity = calcNewSize(newSize);
+    if (wantedCapacity >= _data.capacity()) {
+        return;
+    }
+    if (!_data.try_unreserve(wantedCapacity)) {
+        std::unique_ptr<ArrayType> tmpData(new ArrayType());
+        tmpData->reserve(wantedCapacity);
+        tmpData->resize(newSize);
+        for (uint32_t i = 0; i < newSize; ++i) {
+            (*tmpData)[i] = _data[i];
+        }
+        // Users of RCU vector must ensure that no readers use old size
+        // after swap.  Attribute vectors uses _committedDocIdLimit for this.
+        tmpData->swap(_data); // atomic switch of underlying data
+        size_t holdSize = tmpData->capacity() * sizeof(T);
+        GenerationHeldBase::UP hold(new RcuVectorHeld<ArrayType>(holdSize, std::move(tmpData)));
+        _genHolder.hold(std::move(hold));
+        onReallocation();
+    }
+}
+
+template <typename T>
+RcuVectorBase<T>::RcuVectorBase(GenerationHolderType &genHolder,
+                                const Alloc &initialAlloc)
+    : _data(initialAlloc),
+      _growPercent(100),
+      _growDelta(0),
+      _genHolder(genHolder)
+{
+    _data.reserve(16);
+}
+
+template <typename T>
+RcuVectorBase<T>::RcuVectorBase(size_t initialCapacity,
+                                size_t growPercent,
+                                size_t growDelta,
+                                GenerationHolderType &genHolder,
+                                const Alloc &initialAlloc)
+    : _data(initialAlloc),
+      _growPercent(growPercent),
+      _growDelta(growDelta),
+      _genHolder(genHolder)
+{
+    _data.reserve(initialCapacity);
+}
+
+template <typename T>
+RcuVectorBase<T>::RcuVectorBase(GrowStrategy growStrategy,
+                                GenerationHolderType &genHolder,
+                                const Alloc &initialAlloc)
+    : RcuVectorBase(growStrategy.getInitialCapacity(), growStrategy.getGrowPercent(),
+                    growStrategy.getGrowDelta(), genHolder, initialAlloc)
+{
+}
+
+template <typename T>
+MemoryUsage
+RcuVectorBase<T>::getMemoryUsage() const
+{
+    MemoryUsage retval;
+    retval.incAllocatedBytes(_data.capacity() * sizeof(T));
+    retval.incUsedBytes(_data.size() * sizeof(T));
+    return retval;
+}
+
+template <typename T>
+void
+RcuVectorBase<T>::onReallocation() { }
+
+template <typename T>
+void
+RcuVector<T>::onReallocation() {
+    _genHolderStore.transferHoldLists(_generation);
+}
+
+template <typename T>
+RcuVector<T>::RcuVector()
+    : RcuVectorBase<T>(_genHolderStore),
+      _generation(0),
+      _genHolderStore()
+{ }
+
+template <typename T>
+RcuVector<T>::RcuVector(size_t initialCapacity, size_t growPercent, size_t growDelta)
+    : RcuVectorBase<T>(initialCapacity, growPercent, growDelta, _genHolderStore),
+      _generation(0),
+      _genHolderStore()
+{ }
+
+template <typename T>
+RcuVector<T>::RcuVector(GrowStrategy growStrategy)
+    : RcuVectorBase<T>(growStrategy, _genHolderStore),
+      _generation(0),
+      _genHolderStore()
+{ }
+
+template <typename T>
+RcuVector<T>::~RcuVector()
+{
+    _genHolderStore.clearHoldLists();
+}
+
+template <typename T>
+void
+RcuVector<T>::removeOldGenerations(generation_t firstUsed)
+{
+    _genHolderStore.trimHoldLists(firstUsed);
+}
+
+template <typename T>
+MemoryUsage
+RcuVector<T>::getMemoryUsage() const
+{
+    MemoryUsage retval(RcuVectorBase<T>::getMemoryUsage());
+    retval.mergeGenerationHeldBytes(_genHolderStore.getHeldBytes());
+    return retval;
+}
+
+}