Add free list to mmap file allocator.

11 files changed, 344 insertions, 7 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index c51e42176dc..09a03180fbf 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -131,9 +131,11 @@ vespa_define_module(
     src/tests/tutorial/threads
     src/tests/typify
     src/tests/util/bfloat16
+    src/tests/util/file_area_freelist
     src/tests/util/generationhandler
     src/tests/util/generationhandler_stress
     src/tests/util/md5
+    src/tests/util/mmap_file_allocator
     src/tests/util/mmap_file_allocator_factory
     src/tests/util/rcuvector
     src/tests/util/reusable_set
diff --git a/vespalib/src/tests/util/file_area_freelist/CMakeLists.txt b/vespalib/src/tests/util/file_area_freelist/CMakeLists.txt
new file mode 100644
index 00000000000..a0961adbba8
--- /dev/null
+++ b/vespalib/src/tests/util/file_area_freelist/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_file_area_freelist_test_app TEST
+    SOURCES
+    file_area_freelist_test.cpp
+    DEPENDS
+    vespalib
+    GTest::GTest
+)
+vespa_add_test(NAME vespalib_file_area_freelist_test_app COMMAND vespalib_file_area_freelist_test_app)
diff --git a/vespalib/src/tests/util/file_area_freelist/file_area_freelist_test.cpp b/vespalib/src/tests/util/file_area_freelist/file_area_freelist_test.cpp
new file mode 100644
index 00000000000..aecad4e12cf
--- /dev/null
+++ b/vespalib/src/tests/util/file_area_freelist/file_area_freelist_test.cpp
@@ -0,0 +1,73 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/file_area_freelist.h>
+#include <vespa/vespalib/gtest/gtest.h>
+
+using vespalib::alloc::FileAreaFreeList;
+
+class FileAreaFreeListTest : public ::testing::Test
+{
+protected:
+    FileAreaFreeList _freelist;
+    static constexpr auto bad_offset = FileAreaFreeList::bad_offset;
+
+public:
+    FileAreaFreeListTest();
+    ~FileAreaFreeListTest();
+};
+
+FileAreaFreeListTest::FileAreaFreeListTest()
+    : _freelist()
+{
+}
+
+FileAreaFreeListTest::~FileAreaFreeListTest() = default;
+
+
+TEST_F(FileAreaFreeListTest, empty_freelist_is_ok)
+{
+    EXPECT_EQ(bad_offset, _freelist.alloc(1));
+}
+
+TEST_F(FileAreaFreeListTest, can_reuse_free_area)
+{
+    _freelist.free(4, 1);
+    EXPECT_EQ(4, _freelist.alloc(1));
+    EXPECT_EQ(bad_offset, _freelist.alloc(1));
+}
+
+TEST_F(FileAreaFreeListTest, merge_area_with_next_area)
+{
+    _freelist.free(5, 1);
+    _freelist.free(4, 1);
+    EXPECT_EQ(4, _freelist.alloc(2));
+    EXPECT_EQ(bad_offset, _freelist.alloc(1));
+}
+
+TEST_F(FileAreaFreeListTest, merge_area_with_previous_area)
+{
+    _freelist.free(3, 1);
+    _freelist.free(4, 1);
+    EXPECT_EQ(3, _freelist.alloc(2));
+    EXPECT_EQ(bad_offset, _freelist.alloc(1));
+}
+
+TEST_F(FileAreaFreeListTest, merge_area_with_previous_and_next_area)
+{
+    _freelist.free(5, 1);
+    _freelist.free(3, 1);
+    _freelist.free(4, 1);
+    EXPECT_EQ(3, _freelist.alloc(3));
+    EXPECT_EQ(bad_offset, _freelist.alloc(1));
+}
+
+TEST_F(FileAreaFreeListTest, can_use_part_of_free_area)
+{
+    _freelist.free(4, 2);
+    EXPECT_EQ(4, _freelist.alloc(1));
+    EXPECT_EQ(5, _freelist.alloc(1));
+    EXPECT_EQ(bad_offset, _freelist.alloc(1));
+}
+
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/tests/util/mmap_file_allocator/.gitignore b/vespalib/src/tests/util/mmap_file_allocator/.gitignore
new file mode 100644
index 00000000000..a18e9aac589
--- /dev/null
+++ b/vespalib/src/tests/util/mmap_file_allocator/.gitignore
@@ -0,0 +1 @@
+/mmap-file-allocator-factory-dir
diff --git a/vespalib/src/tests/util/mmap_file_allocator/CMakeLists.txt b/vespalib/src/tests/util/mmap_file_allocator/CMakeLists.txt
new file mode 100644
index 00000000000..00ce5f52fd7
--- /dev/null
+++ b/vespalib/src/tests/util/mmap_file_allocator/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_mmap_file_allocator_test_app TEST
+    SOURCES
+    mmap_file_allocator_test.cpp
+    DEPENDS
+    vespalib
+    GTest::GTest
+)
+vespa_add_test(NAME vespalib_mmap_file_allocator_test_app COMMAND vespalib_mmap_file_allocator_test_app)
diff --git a/vespalib/src/tests/util/mmap_file_allocator/mmap_file_allocator_test.cpp b/vespalib/src/tests/util/mmap_file_allocator/mmap_file_allocator_test.cpp
new file mode 100644
index 00000000000..0d6e7718b86
--- /dev/null
+++ b/vespalib/src/tests/util/mmap_file_allocator/mmap_file_allocator_test.cpp
@@ -0,0 +1,94 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/mmap_file_allocator.h>
+#include <vespa/vespalib/gtest/gtest.h>
+#include <sys/mman.h>
+
+using vespalib::alloc::MemoryAllocator;
+using vespalib::alloc::MmapFileAllocator;
+
+namespace {
+
+vespalib::string basedir("mmap-file-allocator-dir");
+vespalib::string hello("hello");
+
+struct MyAlloc
+{
+    const MemoryAllocator& allocator;
+    void*                  data;
+    size_t                 size;
+
+    MyAlloc(MemoryAllocator& allocator_in, MemoryAllocator::PtrAndSize buf)
+        : allocator(allocator_in),
+          data(buf.first),
+          size(buf.second)
+    {
+    }
+
+    ~MyAlloc()
+    {
+        allocator.free(data, size);
+    }
+
+    MemoryAllocator::PtrAndSize asPair() const noexcept { return std::make_pair(data, size); }
+};
+
+}
+
+class MmapFileAllocatorTest : public ::testing::Test
+{
+protected:
+    MmapFileAllocator _allocator;
+
+public:
+    MmapFileAllocatorTest();
+    ~MmapFileAllocatorTest();
+};
+
+MmapFileAllocatorTest::MmapFileAllocatorTest()
+    : _allocator(basedir)
+{
+}
+
+MmapFileAllocatorTest::~MmapFileAllocatorTest() = default;
+
+TEST_F(MmapFileAllocatorTest, zero_sized_allocation_is_handled)
+{
+    MyAlloc buf(_allocator, _allocator.alloc(0));
+    EXPECT_EQ(nullptr, buf.data);
+    EXPECT_EQ(0u, buf.size);
+}
+
+TEST_F(MmapFileAllocatorTest, mmap_file_allocator_works)
+{
+    MyAlloc buf(_allocator, _allocator.alloc(4));
+    EXPECT_LE(4u, buf.size);
+    EXPECT_TRUE(buf.data != nullptr);
+    memcpy(buf.data, "1st", 4);
+    MyAlloc buf2(_allocator, _allocator.alloc(5));
+    EXPECT_LE(5u, buf2.size);
+    EXPECT_TRUE(buf2.data != nullptr);
+    EXPECT_TRUE(buf.data != buf2.data);
+    memcpy(buf2.data, "fine", 5);
+    EXPECT_EQ(0u, _allocator.resize_inplace(buf.asPair(), 5));
+    EXPECT_EQ(0u, _allocator.resize_inplace(buf.asPair(), 3));
+    EXPECT_NE(0u, _allocator.get_end_offset());
+    int result = msync(buf.data, buf.size, MS_SYNC);
+    EXPECT_EQ(0, result);
+    result = msync(buf2.data, buf2.size, MS_SYNC);
+    EXPECT_EQ(0, result);
+}
+
+TEST_F(MmapFileAllocatorTest, reuse_file_offset_works)
+{
+    {
+        MyAlloc buf(_allocator, _allocator.alloc(hello.size() + 1));
+        memcpy(buf.data, hello.c_str(), hello.size() + 1);
+    }
+    {
+        MyAlloc buf(_allocator, _allocator.alloc(hello.size() + 1));
+        EXPECT_EQ(0, memcmp(buf.data, hello.c_str(), hello.size() + 1));
+    }
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
index 62d642b76b2..934f3d00d6f 100644
--- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt
+++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
@@ -22,6 +22,7 @@ vespa_add_library(vespalib_vespalib_util OBJECT
     error.cpp
     exception.cpp
     exceptions.cpp
+    file_area_freelist.cpp
     gencnt.cpp
     generationhandler.cpp
     generationholder.cpp
diff --git a/vespalib/src/vespa/vespalib/util/file_area_freelist.cpp b/vespalib/src/vespa/vespalib/util/file_area_freelist.cpp
new file mode 100644
index 00000000000..ac6c2263112
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/file_area_freelist.cpp
@@ -0,0 +1,90 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "file_area_freelist.h"
+#include <cassert>
+
+namespace vespalib::alloc {
+
+FileAreaFreeList::FileAreaFreeList()
+    : _free_areas(),
+      _free_sizes()
+{
+}
+
+FileAreaFreeList::~FileAreaFreeList() = default;
+
+void
+FileAreaFreeList::remove_from_size_set(uint64_t offset, size_t size)
+{
+    auto itr = _free_sizes.find(size);
+    assert(itr != _free_sizes.end());
+    auto &offsets = itr->second;
+    auto erased_count = offsets.erase(offset);
+    assert(erased_count != 0u);
+    if (offsets.empty()) {
+        _free_sizes.erase(itr);
+    }
+}
+
+uint64_t
+FileAreaFreeList::alloc(size_t size)
+{
+    auto sitr = _free_sizes.lower_bound(size);
+    if (sitr == _free_sizes.end()) {
+        return bad_offset; // No free areas of sufficient size
+    }
+    auto old_size = sitr->first;
+    assert(old_size >= size);
+    auto &offsets = sitr->second;
+    assert(!offsets.empty());
+    auto oitr = offsets.begin();
+    auto offset = *oitr;
+    offsets.erase(oitr);
+    if (offsets.empty()) {
+        _free_sizes.erase(sitr);
+    }
+    auto fa_itr = _free_areas.find(offset);
+    assert(fa_itr != _free_areas.end());
+    fa_itr = _free_areas.erase(fa_itr);
+    if (old_size > size) {
+        auto ins_res = _free_sizes[old_size - size].insert(offset + size);
+        assert(ins_res.second);
+        _free_areas.emplace_hint(fa_itr, offset + size, old_size - size);
+    }
+    return offset;
+}
+
+void
+FileAreaFreeList::free(uint64_t offset, size_t size)
+{
+    auto itr = _free_areas.lower_bound(offset);
+    if (itr != _free_areas.end() && itr->first <= offset + size) {
+        // Merge with next free area
+        assert(itr->first == offset + size);
+        remove_from_size_set(itr->first, itr->second);
+        size += itr->second;
+        itr = _free_areas.erase(itr);
+    }
+    bool adjusted_prev_area = false;
+    if (itr != _free_areas.begin()) {
+        --itr;
+        if (itr->first + itr->second >= offset) {
+            // Merge with previous free area
+            assert(itr->first + itr->second == offset);
+            remove_from_size_set(itr->first, itr->second);
+            offset = itr->first;
+            size += itr->second;
+            itr->second = size;
+            adjusted_prev_area = true;
+        } else {
+            ++itr;
+        }
+    }
+    if (!adjusted_prev_area) {
+        _free_areas.emplace_hint(itr, offset, size);
+    }
+    auto ins_res = _free_sizes[size].insert(offset);
+    assert(ins_res.second);
+}
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/file_area_freelist.h b/vespalib/src/vespa/vespalib/util/file_area_freelist.h
new file mode 100644
index 00000000000..8b245084585
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/file_area_freelist.h
@@ -0,0 +1,27 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <cstdint>
+#include <limits>
+#include <map>
+#include <set>
+
+namespace vespalib::alloc {
+
+/*
+ * Class that tracks free areas in a file.
+ */
+class FileAreaFreeList {
+    std::map<uint64_t, size_t> _free_areas;
+    std::map<size_t, std::set<uint64_t>> _free_sizes;
+    void remove_from_size_set(uint64_t offset, size_t size);
+public:
+    FileAreaFreeList();
+    ~FileAreaFreeList();
+    uint64_t alloc(size_t size);
+    void free(uint64_t offset, size_t size);
+    static constexpr uint64_t bad_offset = std::numeric_limits<uint64_t>::max();
+};
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/mmap_file_allocator.cpp b/vespalib/src/vespa/vespalib/util/mmap_file_allocator.cpp
index 469a5c366b3..ff11caf31e9 100644
--- a/vespalib/src/vespa/vespalib/util/mmap_file_allocator.cpp
+++ b/vespalib/src/vespa/vespalib/util/mmap_file_allocator.cpp
@@ -12,7 +12,9 @@ namespace vespalib::alloc {
 MmapFileAllocator::MmapFileAllocator(const vespalib::string& dir_name)
     : _dir_name(dir_name),
       _file(_dir_name + "/swapfile"),
-      _end_offset(0)
+      _end_offset(0),
+      _allocations(),
+      _freelist()
 {
     mkdir(_dir_name, true);
     _file.open(O_RDWR | O_CREAT | O_TRUNC, false);
@@ -26,16 +28,27 @@ MmapFileAllocator::~MmapFileAllocator()
     rmdir(_dir_name, true);
 }
 
+uint64_t
+MmapFileAllocator::alloc_area(size_t sz) const
+{
+    uint64_t offset = _freelist.alloc(sz);
+    if (offset != FileAreaFreeList::bad_offset) {
+        return offset;
+    }
+    offset = _end_offset;
+    _end_offset += sz;
+    _file.resize(_end_offset);
+    return offset;
+}
+
 MmapFileAllocator::PtrAndSize
 MmapFileAllocator::alloc(size_t sz) const
 {
     if (sz == 0) {
         return PtrAndSize(nullptr, 0); // empty allocation
     }
-    uint64_t offset = _end_offset;
     sz = round_up_to_page_size(sz);
-    _end_offset += sz;
-    _file.resize(_end_offset);
+    uint64_t offset = alloc_area(sz);
     void *buf = mmap(nullptr, sz,
                      PROT_READ | PROT_WRITE,
                      MAP_SHARED,
@@ -44,7 +57,7 @@ MmapFileAllocator::alloc(size_t sz) const
     assert(buf != MAP_FAILED);
     assert(buf != nullptr);
     // Register allocation
-    auto ins_res = _allocations.insert(std::make_pair(buf, sz));
+    auto ins_res = _allocations.insert(std::make_pair(buf, SizeAndOffset(sz, offset)));
     assert(ins_res.second);
     int retval = madvise(buf, sz, MADV_RANDOM);
     assert(retval == 0);
@@ -64,12 +77,14 @@ MmapFileAllocator::free(PtrAndSize alloc) const
     auto itr = _allocations.find(alloc.first);
     assert(itr != _allocations.end());
     assert(itr->first == alloc.first);
-    assert(itr->second == alloc.second);
+    assert(itr->second.size == alloc.second);
+    auto offset = itr->second.offset;
     _allocations.erase(itr);
     int retval = madvise(alloc.first, alloc.second, MADV_DONTNEED);
     assert(retval == 0);
     retval = munmap(alloc.first, alloc.second);
     assert(retval == 0);
+    _freelist.free(offset, alloc.second);
 }
 
 size_t
diff --git a/vespalib/src/vespa/vespalib/util/mmap_file_allocator.h b/vespalib/src/vespa/vespalib/util/mmap_file_allocator.h
index 308513153c1..0d459bc2134 100644
--- a/vespalib/src/vespa/vespalib/util/mmap_file_allocator.h
+++ b/vespalib/src/vespa/vespalib/util/mmap_file_allocator.h
@@ -3,6 +3,7 @@
 #pragma once
 
 #include "memory_allocator.h"
+#include "file_area_freelist.h"
 #include <vespa/vespalib/io/fileutil.h>
 #include <vespa/vespalib/stllike/hash_map.h>
 #include <vespa/vespalib/stllike/string.h>
@@ -16,10 +17,25 @@ namespace vespalib::alloc {
  * have been freed.
  */
 class MmapFileAllocator : public MemoryAllocator {
+    struct SizeAndOffset {
+        size_t   size;
+        uint64_t offset;
+        SizeAndOffset()
+            : SizeAndOffset(0u, 0u)
+        {
+        }
+        SizeAndOffset(size_t size_in, uint64_t offset_in)
+            : size(size_in),
+              offset(offset_in)
+        {
+        }
+    };
     vespalib::string _dir_name;
     mutable File _file;
     mutable uint64_t _end_offset;
-    mutable hash_map<void *, size_t> _allocations;
+    mutable hash_map<void *, SizeAndOffset> _allocations;
+    mutable FileAreaFreeList _freelist;
+    uint64_t alloc_area(size_t sz) const;
 public:
     MmapFileAllocator(const vespalib::string& dir_name);
     ~MmapFileAllocator();