Merge pull request #1432 from yahoo/geirst/support-shrinking-underlying-memory-allocation-in-rcuvector-shrink

Geirst/support shrinking underlying memory allocation in rcuvector shrink

3 files changed, 86 insertions, 61 deletions

diff --git a/vespalib/src/tests/array/array_test.cpp b/vespalib/src/tests/array/array_test.cpp
index fb4a824ec00..13e46111bfb 100644
--- a/vespalib/src/tests/array/array_test.cpp
+++ b/vespalib/src/tests/array/array_test.cpp
@@ -7,22 +7,6 @@
 
 using namespace vespalib;
 
-class Test : public TestApp
-{
-public:
-    int Main();
-private:
-    template <typename T>
-    void testArray(const T & a, const T & b);
-    void testComplicated();
-    void testBeginEnd();
-    void testThatOrganicGrowthIsBy2InNAndReserveResizeAreExact();
-    template<class T>
-    void testBeginEnd(T & v);
-    void testMoveConstructor();
-    void testMoveAssignment();
-};
-
 namespace vespalib {
 
 template <typename T>
@@ -80,10 +64,38 @@ std::ostream & operator << (std::ostream & os, const Clever & clever)
     return os;
 }
 
-int
-Test::Main()
+template <typename T>
+void
+testArray(const T & a, const T & b)
+{
+    Array<T> array;
+
+    ASSERT_EQUAL(sizeof(array), 32u);
+    ASSERT_EQUAL(array.size(), 0u);
+    ASSERT_EQUAL(array.capacity(), 0u);
+    for(size_t i(0); i < 5; i++) {
+        array.push_back(a);
+        array.push_back(b);
+        for (size_t j(0); j <= i; j++) {
+            ASSERT_EQUAL(array[j*2 + 0], a);
+            ASSERT_EQUAL(array[j*2 + 1], b);
+        }
+    }
+    ASSERT_EQUAL(array.size(), 10u);
+    ASSERT_EQUAL(array.capacity(), 16u);
+    for (size_t i(array.size()), m(array.capacity()); i < m; i+=2) {
+        array.push_back(a);
+        array.push_back(b);
+        for (size_t j(0); j <= (i/2); j++) {
+            ASSERT_EQUAL(array[j*2 + 0], a);
+            ASSERT_EQUAL(array[j*2 + 1], b);
+        }
+    }
+    ASSERT_EQUAL(array.size(), array.capacity());
+}
+
+TEST("test basic array functionality")
 {
-    TEST_INIT("array_test");
     testArray<int>(7, 9);
     testArray<vespalib::string>("7", "9");
     const char * longS1 = "more than 48 bytes bytes that are needed to avoid the small string optimisation in vespalib::string";
@@ -105,15 +117,9 @@ Test::Main()
     size_t counter(0);
     testArray(Clever(&counter),  Clever(&counter));
     EXPECT_EQUAL(0ul, counter);
-    testComplicated();
-    testBeginEnd();
-    testThatOrganicGrowthIsBy2InNAndReserveResizeAreExact();
-    testMoveConstructor();
-    testMoveAssignment();
-    TEST_DONE();
 }
 
-void Test::testThatOrganicGrowthIsBy2InNAndReserveResizeAreExact()
+TEST("test that organic growth is by 2 in N and reserve resize are exact")
 {
     Array<char> c(256);
     EXPECT_EQUAL(256u, c.size());
@@ -149,38 +155,9 @@ void Test::testThatOrganicGrowthIsBy2InNAndReserveResizeAreExact()
     EXPECT_EQUAL(2048u, c.capacity());
 }
 
-template <typename T>
-void Test::testArray(const T & a, const T & b)
-{
-    Array<T> array;
-
-    ASSERT_EQUAL(sizeof(array), 32u);
-    ASSERT_EQUAL(array.size(), 0u);
-    ASSERT_EQUAL(array.capacity(), 0u);
-    for(size_t i(0); i < 5; i++) {
-        array.push_back(a);
-        array.push_back(b);
-        for (size_t j(0); j <= i; j++) {
-            ASSERT_EQUAL(array[j*2 + 0], a);
-            ASSERT_EQUAL(array[j*2 + 1], b);
-        }
-    }
-    ASSERT_EQUAL(array.size(), 10u);
-    ASSERT_EQUAL(array.capacity(), 16u);
-    for (size_t i(array.size()), m(array.capacity()); i < m; i+=2) {
-        array.push_back(a);
-        array.push_back(b);
-        for (size_t j(0); j <= (i/2); j++) {
-            ASSERT_EQUAL(array[j*2 + 0], a);
-            ASSERT_EQUAL(array[j*2 + 1], b);
-        }
-    }
-    ASSERT_EQUAL(array.size(), array.capacity());
-}
-
 size_t Clever::_global = 0;
 
-void Test::testComplicated()
+TEST("test complicated")
 {
     volatile size_t counter(0);
     {
@@ -226,7 +203,8 @@ void Test::testComplicated()
 }
 
 template<class T>
-void Test::testBeginEnd(T & v)
+void
+testBeginEnd(T & v)
 {
     EXPECT_EQUAL(0u, v.end() - v.begin());
     EXPECT_EQUAL(0u, v.rend() - v.rbegin());
@@ -288,7 +266,7 @@ void Test::testBeginEnd(T & v)
     EXPECT_EQUAL(3u, v.rend() - v.rbegin());
 }
 
-void Test::testBeginEnd()
+TEST("test begin end")
 {
     std::vector<size_t> v;
     Array<size_t> a;
@@ -296,7 +274,7 @@ void Test::testBeginEnd()
     testBeginEnd(a);
 }
 
-void Test::testMoveConstructor()
+TEST("test move constructor")
 {
     Array<size_t> orig;
     orig.push_back(42);
@@ -318,7 +296,7 @@ void Test::testMoveConstructor()
     }
 }
 
-void Test::testMoveAssignment()
+TEST("test move assignment")
 {
     Array<size_t> orig;
     orig.push_back(44);
@@ -342,4 +320,33 @@ void Test::testMoveAssignment()
     }
 }
 
-TEST_APPHOOK(Test)
+struct UnreserveFixture {
+    Array<int> arr;
+    UnreserveFixture() : arr(1025, 7, alloc::Alloc::allocMMap(0))
+    {
+        EXPECT_EQUAL(1025u, arr.size());
+        EXPECT_EQUAL(2048u, arr.capacity());
+    }
+};
+
+TEST_F("require that try_unreserve() fails if wanted capacity >= current capacity", UnreserveFixture)
+{
+    EXPECT_FALSE(f.arr.try_unreserve(2048));
+}
+
+TEST_F("require that try_unreserve() fails if wanted capacity < current size", UnreserveFixture)
+{
+    EXPECT_FALSE(f.arr.try_unreserve(1024));
+}
+
+TEST_F("require that try_unreserve() succeedes if mmap can be shrinked", UnreserveFixture)
+{
+    int *oldPtr = &f.arr[0];
+    f.arr.resize(512);
+    EXPECT_TRUE(f.arr.try_unreserve(1023));
+    EXPECT_EQUAL(1024u, f.arr.capacity());
+    int *newPtr = &f.arr[0];
+    EXPECT_EQUAL(oldPtr, newPtr);
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }
diff --git a/vespalib/src/vespa/vespalib/util/array.h b/vespalib/src/vespa/vespalib/util/array.h
index 269bf67bc26..4ca09bd093a 100644
--- a/vespalib/src/vespa/vespalib/util/array.h
+++ b/vespalib/src/vespa/vespalib/util/array.h
@@ -106,6 +106,12 @@ public:
     void resize(size_t n);
     void assign(const_iterator begin_, const_iterator end_);
     void reserve(size_t n);
+    /**
+     * Try to unreserve memory from the underlying memory buffer inplace down to the given limit.
+     * The existing memory buffer is unmodified up to the new size (no copying occurs).
+     * Returns true if it was possible to unreserve memory, false if not.
+     */
+    bool try_unreserve(size_t n);
     void push_back(const T & v)             { std::_Construct(push_back(), v); }
     iterator push_back()                    { extend(size()+1); return array(_sz++); }
     iterator push_back_fast()               { return array(_sz++); }
diff --git a/vespalib/src/vespa/vespalib/util/array.hpp b/vespalib/src/vespa/vespalib/util/array.hpp
index dbdda73ad66..ec418d7d566 100644
--- a/vespalib/src/vespa/vespalib/util/array.hpp
+++ b/vespalib/src/vespa/vespalib/util/array.hpp
@@ -94,6 +94,18 @@ void Array<T>::reserve(size_t n) {
 }
 
 template <typename T>
+bool Array<T>::try_unreserve(size_t n)
+{
+    if (n >= capacity()) {
+        return false;
+    }
+    if (n < size()) {
+        return false;
+    }
+    return _array.resize_inplace(n * sizeof(T));
+}
+
+template <typename T>
 void Array<T>::resize(size_t n)
 {
     if (n > capacity()) {