[PATCH V2 1/2] mempool: fix a bug in page_range_allocator() when handling worst case O(n) scenario

[Waldemar Kozaczuk]

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>
---
core/mempool.cc | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/core/mempool.cc b/core/mempool.cc
index d902eea8..11fd1456 100644
--- a/core/mempool.cc
+++ b/core/mempool.cc
@@ -702,10 +702,13 @@ page_range* page_range_allocator::alloc(size_t size)
for (auto&& pr : _free[exact_order - 1]) {
if (pr.size >= size) {
range = &pr;
+ remove_list(exact_order - 1, *range);
break;
}
}
- return nullptr;
+ if (!range) {
+ return nullptr;
+ }
} else if (order == max_order) {
range = &*_free_huge.rbegin();
if (range->size < size) {
--
2.20.1

[Waldemar Kozaczuk]

This patch addresses the issue #854. In essence it changes malloc_large()
to use mmu::map_anon() if requested memory is greater than size of "huge page"
and it does not have be contiguous in physical memory. Also it makes it fallback
to map_anon() based allocation for requests > 4K and < 2MB that cannot be satisfied
when mamory is fragmented.

It is supposed to help OSv memory allocation behave better when memory
in free_page_ranges is heavily fragmented and large allocations (>=2MB)
cannot be satisfied with single contiguous page range.

Fixes #854

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>
---

core/mempool.cc | 54 +++++++++++++++++++++++++++++++++++++++----------
1 file changed, 43 insertions(+), 11 deletions(-)

diff --git a/core/mempool.cc b/core/mempool.cc
index 11fd1456..f14a6a68 100644
--- a/core/mempool.cc
+++ b/core/mempool.cc
@@ -546,7 +546,7 @@ public:
page_range_allocator() : _deferred_free(nullptr) { }

template<bool UseBitmap = true>
- page_range* alloc(size_t size);
+ page_range* alloc(size_t size, bool contiguous = true);
page_range* alloc_aligned(size_t size, size_t offset, size_t alignment,
bool fill = false);
void free(page_range* pr);
@@ -678,7 +678,7 @@ void page_range_allocator::bitmap_allocator<T>::deallocate(T* p, size_t n)
}

template<bool UseBitmap>
-page_range* page_range_allocator::alloc(size_t size)
+page_range* page_range_allocator::alloc(size_t size, bool contiguous)
{
auto exact_order = ilog2_roundup(size / page_size);
if (exact_order > max_order) {
@@ -692,13 +692,12 @@ page_range* page_range_allocator::alloc(size_t size)

page_range* range = nullptr;
if (!bitset) {
- if (!exact_order || _free[exact_order - 1].empty()) {
+ if (!contiguous || !exact_order || _free[exact_order - 1].empty()) {
return nullptr;
}
- // TODO: This linear search makes worst case complexity of the allocator
- // O(n). It would be better to fall back to non-contiguous allocation
- // and make worst case complexity depend on the size of requested memory
- // block and the logarithm of the number of free huge page ranges.
+ // This linear search makes worst case complexity of the allocator
+ // O(n). Unfortunately we do not have choice for contiguous allocation
+ // so let us hope there is large enough range.

for (auto&& pr : _free[exact_order - 1]) {
if (pr.size >= size) {
range = &pr;

@@ -823,7 +822,16 @@ void page_range_allocator::for_each(unsigned min_order, Func f)
}
}

-static void* malloc_large(size_t size, size_t alignment, bool block = true)
+static void* mapped_malloc_large(size_t size, size_t offset)
+{
+ //TODO: For now pre-populate the memory, in future consider doing lazy population
+ void* obj = mmu::map_anon(nullptr, size, mmu::mmap_populate, mmu::perm_read | mmu::perm_write);
+ size_t* ret_header = reinterpret_cast<size_t*>(obj);
+ *ret_header = size;
+ return obj + offset;
+}
+
+static void* malloc_large(size_t size, size_t alignment, bool block = true, bool contiguous = true)
{
auto requested_size = size;
size_t offset;
@@ -835,6 +843,14 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
size += offset;
size = align_up(size, page_size);

+ // Use mmap if requested memory greater than "huge page" size
+ // and does not need to be contiguous
+ if (size >= mmu::huge_page_size && !contiguous) {
+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
+ }
+
while (true) {
WITH_LOCK(free_page_ranges_lock) {
reclaimer_thread.wait_for_minimum_memory();
@@ -842,7 +858,7 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
if (alignment > page_size) {
ret_header = free_page_ranges.alloc_aligned(size, page_size, alignment);
} else {
- ret_header = free_page_ranges.alloc(size);
+ ret_header = free_page_ranges.alloc(size, contiguous);
}
if (ret_header) {
on_alloc(size);
@@ -850,6 +866,10 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
obj += offset;
trace_memory_malloc_large(obj, requested_size, size, alignment);
return obj;
+ } else if (!contiguous) {
+ // If we failed to get contiguous memory allocation and
+ // the caller does not require one let us use map-based allocation
+ break;
}
if (block)
reclaimer_thread.wait_for_memory(size);
@@ -857,6 +877,10 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
return nullptr;
}
}
+
+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
}

void shrinker::deactivate_shrinker()
@@ -1692,7 +1716,7 @@ static inline void* std_malloc(size_t size, size_t alignment)
memory::alloc_page());
trace_memory_malloc_page(ret, size, mmu::page_size, alignment);
} else {
- ret = memory::malloc_large(size, alignment);
+ ret = memory::malloc_large(size, alignment, true, false);
}
memory::tracker_remember(ret, size);
return ret;
@@ -1763,6 +1787,14 @@ void free(void* object)
return;
}
memory::tracker_forget(object);
+
+ if (!mmu::is_linear_mapped(object, 0)) {
+ object = align_down(object - 1, mmu::page_size);
+ size_t* ret_header = reinterpret_cast<size_t*>(object);
+ mmu::munmap(object, *ret_header);
+ return;
+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::page:
object = mmu::translate_mem_area(mmu::mem_area::page,
@@ -1972,7 +2004,7 @@ void* alloc_phys_contiguous_aligned(size_t size, size_t align, bool block)
assert(is_power_of_two(align));
// make use of the standard large allocator returning properly aligned
// physically contiguous memory:
- auto ret = malloc_large(size, align, block);
+ auto ret = malloc_large(size, align, block, true);
assert (!(reinterpret_cast<uintptr_t>(ret) & (align - 1)));
return ret;
}
--
2.20.1

[Waldek Kozaczuk]

I think I should be using static_cast here (and in other place). But I am not sure it is causing any particular harm.

+    *ret_header = size;
+    return obj + offset;
+}
+
+static void* malloc_large(size_t size, size_t alignment, bool block = true, bool contiguous = true)
 {
     auto requested_size = size;
     size_t offset;
@@ -835,6 +843,14 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
     size += offset;
     size = align_up(size, page_size);
 
+    // Use mmap if requested memory greater than "huge page" size
+    // and does not need to be contiguous
+    if (size >= mmu::huge_page_size && !contiguous) {
+        void* obj = mapped_malloc_large(size, offset);
+        trace_memory_malloc_large(obj, requested_size, size, alignment);
+        return obj;
+    }
+

Not sure if above and below when we call mapped_malloc_large() we need to do something extra  if (alignment > page_size).

[Waldemar Kozaczuk]

This patch addresses the issue #854. In essence it changes malloc_large()
to use mmu::map_anon() if requested memory is greater than size of "huge page"
and it does not have be contiguous in physical memory. Also it makes it fallback
to map_anon() based allocation for requests > 4K and < 2MB that cannot be satisfied
when mamory is fragmented.

It is supposed to help OSv memory allocation behave better when memory
in free_page_ranges is heavily fragmented and large allocations (>=2MB)
cannot be satisfied with single contiguous page range.

Fixes #854

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>
---

core/mempool.cc | 60 ++++++++++++++++++++++++++++++++++++++++---------
1 file changed, 49 insertions(+), 11 deletions(-)

diff --git a/core/mempool.cc b/core/mempool.cc
index 11fd1456..56d65591 100644

+ size_t* ret_header = static_cast<size_t*>(obj);

+ *ret_header = size;
+ return obj + offset;
+}
+
+static void* malloc_large(size_t size, size_t alignment, bool block = true, bool contiguous = true)
{
auto requested_size = size;
size_t offset;
@@ -835,6 +843,14 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
size += offset;
size = align_up(size, page_size);

+ // Use mmap if requested memory greater than "huge page" size
+ // and does not need to be contiguous
+ if (size >= mmu::huge_page_size && !contiguous) {
+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
+ }
+

@@ -1714,6 +1738,12 @@ void* calloc(size_t nmemb, size_t size)

static size_t object_size(void *object)
{

+ if (!mmu::is_linear_mapped(object, 0)) {
+ object = align_down(object - 1, mmu::page_size);

+ size_t* ret_header = static_cast<size_t*>(object);
+ return *ret_header;

+ }
+
switch (mmu::get_mem_area(object)) {

case mmu::mem_area::main:
return memory::large_object_size(object);
@@ -1763,6 +1793,14 @@ void free(void* object)

return;
}
memory::tracker_forget(object);
+
+ if (!mmu::is_linear_mapped(object, 0)) {
+ object = align_down(object - 1, mmu::page_size);

+ size_t* ret_header = static_cast<size_t*>(object);

+ mmu::munmap(object, *ret_header);
+ return;
+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::page:
object = mmu::translate_mem_area(mmu::mem_area::page,

@@ -1972,7 +2010,7 @@ void* alloc_phys_contiguous_aligned(size_t size, size_t align, bool block)

[Waldemar Kozaczuk]

This patch mostly addresses the issue #854. In essence it changes malloc_large()

to use mmu::map_anon() if requested memory is greater than size of "huge page"
and it does not have be contiguous in physical memory. Also it makes it fallback
to map_anon() based allocation for requests > 4K and < 2MB that cannot be satisfied

when memory is heavily fragmented.

It is supposed to help OSv memory allocation behave better when memory
in free_page_ranges is heavily fragmented and large allocations (>=2MB)

cannot be satisfied with single contiguous page range. When working on
this patch it has also become clear, that applications that heavily use realloc()
which allocates new chunks of memory and frees old ones, might very much encounter
heavy fragmentation of memory. Hopefully this patch is going to help
in these scenarios.

It just happens that object_size() and large_object_size() needed to be
adjusted to work with new malloc_large() implementation. It was discovered
that therefore other related issues are fixed by this patch as well.

Fixes #854
Fixed #1077

This patch also potentially addresses realloc() related issue #784.

Lastly this patch adds new test verifying realloc() and malloc_usable_size().

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>
---

core/mempool.cc | 66 +++++++++++++++++++++++------
modules/tests/Makefile | 2 +-
tests/tst-realloc.cc | 94 ++++++++++++++++++++++++++++++++++++++++++
3 files changed, 149 insertions(+), 13 deletions(-)
create mode 100644 tests/tst-realloc.cc

diff --git a/core/mempool.cc b/core/mempool.cc
index 11fd1456..1bf010d6 100644

@@ -1072,9 +1096,11 @@ static void free_large(void* obj)

static unsigned large_object_size(void *obj)
{
+ auto original_obj = obj;
obj = align_down(obj - 1, page_size);
+ size_t offset = reinterpret_cast<uint64_t>(original_obj) - reinterpret_cast<uint64_t>(obj);
auto header = static_cast<page_range*>(obj);
- return header->size;
+ return header->size - offset;
}

namespace page_pool {
@@ -1692,7 +1718,7 @@ static inline void* std_malloc(size_t size, size_t alignment)

memory::alloc_page());
trace_memory_malloc_page(ret, size, mmu::page_size, alignment);
} else {
- ret = memory::malloc_large(size, alignment);
+ ret = memory::malloc_large(size, alignment, true, false);
}
memory::tracker_remember(ret, size);
return ret;

@@ -1714,6 +1740,14 @@ void* calloc(size_t nmemb, size_t size)

static size_t object_size(void *object)
{
+ if (!mmu::is_linear_mapped(object, 0)) {

+ auto original_object = object;

+ object = align_down(object - 1, mmu::page_size);

+ size_t offset = reinterpret_cast<uint64_t>(original_object) - reinterpret_cast<uint64_t>(object);

+ size_t* ret_header = static_cast<size_t*>(object);

+ return *ret_header - offset;

+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::main:
return memory::large_object_size(object);

@@ -1763,6 +1797,14 @@ void free(void* object)

return;
}
memory::tracker_forget(object);
+
+ if (!mmu::is_linear_mapped(object, 0)) {
+ object = align_down(object - 1, mmu::page_size);
+ size_t* ret_header = static_cast<size_t*>(object);
+ mmu::munmap(object, *ret_header);
+ return;
+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::page:
object = mmu::translate_mem_area(mmu::mem_area::page,

@@ -1972,7 +2014,7 @@ void* alloc_phys_contiguous_aligned(size_t size, size_t align, bool block)

assert(is_power_of_two(align));
// make use of the standard large allocator returning properly aligned
// physically contiguous memory:
- auto ret = malloc_large(size, align, block);
+ auto ret = malloc_large(size, align, block, true);
assert (!(reinterpret_cast<uintptr_t>(ret) & (align - 1)));
return ret;
}

diff --git a/modules/tests/Makefile b/modules/tests/Makefile
index ce004339..10df022f 100644
--- a/modules/tests/Makefile
+++ b/modules/tests/Makefile
@@ -129,7 +129,7 @@ tests := tst-pthread.so misc-ramdisk.so tst-vblk.so tst-bsd-evh.so \
tst-sigaltstack.so tst-fread.so tst-tcp-cork.so tst-tcp-v6.so \
tst-calloc.so tst-crypt.so tst-non-fpic.so tst-small-malloc.so \
tst-mmx-fpu.so tst-getopt.so tst-getopt-pie.so tst-non-pie.so tst-semaphore.so \
- tst-elf-init.so
+ tst-elf-init.so tst-realloc.so
# libstatic-thread-variable.so tst-static-thread-variable.so \

tests += testrunner.so
diff --git a/tests/tst-realloc.cc b/tests/tst-realloc.cc
new file mode 100644
index 00000000..49edfb7a
--- /dev/null
+++ b/tests/tst-realloc.cc
@@ -0,0 +1,94 @@
+/*
+* Copyright (C) 2020 Waldemar Kozaczuk
+*
+* This work is open source software, licensed under the terms of the
+* BSD license as described in the LICENSE file in the top-level directory.
+*/
+
+#include <stdlib.h>
+#include <string.h>
+#include <cassert>
+#include <iostream>
+
+extern "C" size_t malloc_usable_size (void *ptr);
+
+static void test_realloc(size_t original_size, size_t new_size)
+{
+ char data[11] = "0123456789";
+
+ void *original_buf = malloc(original_size);
+ assert(original_buf);
+
+ char *buf = static_cast<char*>(original_buf);
+ for (size_t i = 0; i < original_size; i++) {
+ buf[i] = data[i % 10];
+ }
+
+ void *new_buf = realloc(original_buf, new_size);
+ assert(new_buf);
+
+ auto expected_same_data_len = std::min(original_size, new_size);
+ buf = static_cast<char*>(new_buf);
+ for (size_t i = 0; i < expected_same_data_len; i++) {
+ assert(buf[i] == data[i % 10]);
+ }
+
+ free(new_buf);
+
+ std::cerr << "PASSED realloc() for original_size: " << original_size << ", new_size: " << new_size << std::endl;
+}
+
+static void test_usable_size(size_t size, size_t expected_usable_size)
+{
+ void* ptr = malloc(size);
+ assert(expected_usable_size == malloc_usable_size(ptr));
+ free(ptr);
+
+ std::cerr << "PASSED malloc_usable_size() for size: " << size << std::endl;
+}
+
+int main()
+{
+ test_realloc(1,2);
+ test_realloc(2,1);
+
+ test_realloc(4,7);
+ test_realloc(7,4);
+
+ test_realloc(63,128);
+ test_realloc(128,63);
+
+ test_realloc(4000,5000);
+ test_realloc(5000,4000);
+
+ test_realloc(4096,4096);
+
+ test_realloc(0x100000,0x100000);
+ test_realloc(0x100000,0x100900);
+ test_realloc(0x100900,0x100000);
+
+ test_realloc(0x200000,0x200000);
+ test_realloc(0x200000,0x300900);
+ test_realloc(0x300900,0x200000);
+
+ test_realloc(0x600900,0x600000);
+ test_realloc(0x400000,0x600000);
+ test_realloc(0x600000,0x400900);
+
+ void *buf = realloc(nullptr, 0);
+ assert(buf);
+ free(buf);
+
+ buf = malloc(16);
+ assert(!realloc(buf, 0));
+
+ test_usable_size(1, 8);
+ test_usable_size(8, 8);
+ test_usable_size(67, 128);
+ test_usable_size(0x4010, 0x4FC0);
+ test_usable_size(0x100000, 0x100FC0);
+ test_usable_size(0x200000, 0x200FC0);
+
+ std::cerr << "PASSED\n";
+ return 0;
+}
\ No newline at end of file
--
2.20.1

[Nadav Har'El]

Looks very good, I  have several minor suggestions below (inline), but I would have committed this patch anyway,

except that I didn't understand is why this patch is titled "2/2" - where is 1/2? I couldn't find it.

I see you have new realloc() tests - did these tests fail before your patches?

--
Nadav Har'El

n...@scylladb.com

On Thu, Mar 26, 2020 at 8:36 PM Waldemar Kozaczuk <jwkoz...@gmail.com> wrote:

This patch mostly addresses the issue #854. In essence it changes malloc_large()
to use mmu::map_anon() if requested memory is greater than size of "huge page"
and it does not have be contiguous in physical memory. Also it makes it fallback
to map_anon() based allocation for requests > 4K and < 2MB that cannot be satisfied
when memory is heavily fragmented.

It is supposed to help OSv memory allocation behave better when memory
in free_page_ranges is heavily fragmented and large allocations (>=2MB)
cannot be satisfied with single contiguous page range. When working on
this patch it has also become clear, that applications that heavily use realloc()
which allocates new chunks of memory and frees old ones, might very much encounter
heavy fragmentation of memory. Hopefully this patch is going to help
in these scenarios.

It just happens that object_size() and large_object_size() needed to be
adjusted to work with new malloc_large() implementation. It was discovered
that therefore other related issues are fixed by this patch as well.

Fixes #854
Fixed #1077

This patch also potentially addresses realloc() related issue #784.

It seems very likely it does address this as well. Maybe we should just close this issue too, because we're never going to get more information about this issue.

nipick: wouldn't it be clearer to put this code where you have the "break" above (instead of the "break"), instead of here?

 }

 void shrinker::deactivate_shrinker()
@@ -1072,9 +1096,11 @@ static void free_large(void* obj)

 static unsigned large_object_size(void *obj)
 {
+    auto original_obj = obj;
     obj = align_down(obj - 1, page_size);

+    size_t offset = reinterpret_cast<uint64_t>(original_obj) - reinterpret_cast<uint64_t>(obj);

     auto header = static_cast<page_range*>(obj);
-    return header->size;
+    return header->size - offset;

 }

I wonder if just this change explains https://github.com/cloudius-systems/osv/issues/784 and we should close that issue.

But don't feel an expert enough in this issue to say...

 namespace page_pool {
@@ -1692,7 +1718,7 @@ static inline void* std_malloc(size_t size, size_t alignment)
                                        memory::alloc_page());
         trace_memory_malloc_page(ret, size, mmu::page_size, alignment);
     } else {
-        ret = memory::malloc_large(size, alignment);
+        ret = memory::malloc_large(size, alignment, true, false);
     }
     memory::tracker_remember(ret, size);
     return ret;
@@ -1714,6 +1740,14 @@ void* calloc(size_t nmemb, size_t size)

 static size_t object_size(void *object)
 {
+    if (!mmu::is_linear_mapped(object, 0)) {
+        auto original_object = object;
+        object = align_down(object - 1, mmu::page_size);
+        size_t offset = reinterpret_cast<uint64_t>(original_object) - reinterpret_cast<uint64_t>(object);
+        size_t* ret_header = static_cast<size_t*>(object);
+        return *ret_header - offset;

Can you just call large_object_size() here instead of duplicating its code?

Just like you do below in the mmu::mem_area::main case?

 

+    }
+
     switch (mmu::get_mem_area(object)) {
     case mmu::mem_area::main:
         return memory::large_object_size(object);
@@ -1763,6 +1797,14 @@ void free(void* object)
         return;
     }
     memory::tracker_forget(object);
+
+    if (!mmu::is_linear_mapped(object, 0)) {
+        object = align_down(object - 1, mmu::page_size);
+        size_t* ret_header = static_cast<size_t*>(object);
+        mmu::munmap(object, *ret_header);
+        return;

Nitpick:  would be nice to put this code in a function mapped_free_large(), and put this

function next to mapped_malloc_large() which you already have - so a reader can see

the two of them next to each other.

--
You received this message because you are subscribed to the Google Groups "OSv Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to osv-dev+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/20200326183626.12013-1-jwkozaczuk%40gmail.com.

[Waldek Kozaczuk]

On Sunday, March 29, 2020 at 10:04:45 AM UTC-4, Nadav Har'El wrote:

Looks very good, I  have several minor suggestions below (inline), but I would have committed this patch anyway,

except that I didn't understand is why this patch is titled "2/2" - where is 1/2? I couldn't find it.

It is called '[PATCH V2 1/2] mempool: fix a bug in page_range_allocator() when handling worst case O(n) scenario' from Match 24th. It fixes somewhat related bug.

I see you have new realloc() tests - did these tests fail before your patches?

I think one of the previous version of this patch was failing and in any case, it was a way for me to better verify my changes, 

To unsubscribe from this group and stop receiving emails from it, send an email to osv...@googlegroups.com.

[Nadav Har'El]

On Sun, Mar 29, 2020 at 5:37 PM Waldek Kozaczuk <jwkoz...@gmail.com> wrote:

On Sunday, March 29, 2020 at 10:04:45 AM UTC-4, Nadav Har'El wrote:

Looks very good, I  have several minor suggestions below (inline), but I would have committed this patch anyway,

except that I didn't understand is why this patch is titled "2/2" - where is 1/2? I couldn't find it.

It is called '[PATCH V2 1/2] mempool: fix a bug in page_range_allocator() when handling worst case O(n) scenario' from Match 24th. It fixes somewhat related bug.

Ok, I didn't realize I should look for older versions.

Do you want to change anything in v4 based on my comments, or want me to commit your patch as-is and then consider my comments?

If you want to change anything, please send v5 with both patches (or commit them yourself). Thanks!

To unsubscribe from this group and stop receiving emails from it, send an email to osv-dev+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/29288786-0656-4ab7-b068-c6b249e2dfa3%40googlegroups.com.

[Waldek Kozaczuk]

Let me try to address your comments and send V5.

To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/29288786-0656-4ab7-b068-c6b249e2dfa3%40googlegroups.com.

[Waldek Kozaczuk]

On Sunday, March 29, 2020 at 10:04:45 AM UTC-4, Nadav Har'El wrote:

The 3 lines of this code are identical so I will create a separate common function. But  the last 2 are actually different as they reference size_t header vs page_header though it would most likely end up working the same.

To unsubscribe from this group and stop receiving emails from it, send an email to osv...@googlegroups.com.

[Waldemar Kozaczuk]

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>
---

core/mempool.cc | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/core/mempool.cc b/core/mempool.cc
index d902eea8..11fd1456 100644
--- a/core/mempool.cc
+++ b/core/mempool.cc
@@ -702,10 +702,13 @@ page_range* page_range_allocator::alloc(size_t size)

for (auto&& pr : _free[exact_order - 1]) {
if (pr.size >= size) {
range = &pr;

[Waldemar Kozaczuk]

This patch mostly addresses the issue #854. In essence it changes malloc_large()
to use mmu::map_anon() if requested memory is greater than size of "huge page"
and it does not have be contiguous in physical memory. Also it makes it fallback
to map_anon() based allocation for requests > 4K and < 2MB that cannot be satisfied
when memory is heavily fragmented.

It is supposed to help OSv memory allocation behave better when memory
in free_page_ranges is heavily fragmented and large allocations (>=2MB)
cannot be satisfied with single contiguous page range. When working on
this patch it has also become clear, that applications that heavily use realloc()
which allocates new chunks of memory and frees old ones, might very much encounter
heavy fragmentation of memory. Hopefully this patch is going to help
in these scenarios.

It just happens that object_size() and large_object_size() needed to be
adjusted to work with new malloc_large() implementation. It was discovered
that therefore other related issues are fixed by this patch as well.

Lastly this patch adds new test verifying realloc() and malloc_usable_size().

Fixes #784
Fixes #854
Fixes #1077

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>
---

core/mempool.cc | 81 ++++++++++++++++++++++++++++++------

modules/tests/Makefile | 2 +-
tests/tst-realloc.cc | 94 ++++++++++++++++++++++++++++++++++++++++++

3 files changed, 163 insertions(+), 14 deletions(-)
create mode 100644 tests/tst-realloc.cc

diff --git a/core/mempool.cc b/core/mempool.cc
index 11fd1456..50f5e877 100644
--- a/core/mempool.cc
+++ b/core/mempool.cc

@@ -546,7 +546,7 @@ public:
page_range_allocator() : _deferred_free(nullptr) { }

template<bool UseBitmap = true>
- page_range* alloc(size_t size);
+ page_range* alloc(size_t size, bool contiguous = true);
page_range* alloc_aligned(size_t size, size_t offset, size_t alignment,
bool fill = false);
void free(page_range* pr);
@@ -678,7 +678,7 @@ void page_range_allocator::bitmap_allocator<T>::deallocate(T* p, size_t n)
}

template<bool UseBitmap>
-page_range* page_range_allocator::alloc(size_t size)
+page_range* page_range_allocator::alloc(size_t size, bool contiguous)
{
auto exact_order = ilog2_roundup(size / page_size);
if (exact_order > max_order) {

@@ -692,13 +692,12 @@ page_range* page_range_allocator::alloc(size_t size)

page_range* range = nullptr;
if (!bitset) {
- if (!exact_order || _free[exact_order - 1].empty()) {
+ if (!contiguous || !exact_order || _free[exact_order - 1].empty()) {
return nullptr;
}
- // TODO: This linear search makes worst case complexity of the allocator
- // O(n). It would be better to fall back to non-contiguous allocation
- // and make worst case complexity depend on the size of requested memory
- // block and the logarithm of the number of free huge page ranges.
+ // This linear search makes worst case complexity of the allocator
+ // O(n). Unfortunately we do not have choice for contiguous allocation
+ // so let us hope there is large enough range.

for (auto&& pr : _free[exact_order - 1]) {
if (pr.size >= size) {
range = &pr;

@@ -823,7 +822,23 @@ void page_range_allocator::for_each(unsigned min_order, Func f)

}
}

-static void* malloc_large(size_t size, size_t alignment, bool block = true)
+static void* mapped_malloc_large(size_t size, size_t offset)
+{
+ //TODO: For now pre-populate the memory, in future consider doing lazy population
+ void* obj = mmu::map_anon(nullptr, size, mmu::mmap_populate, mmu::perm_read | mmu::perm_write);
+ size_t* ret_header = static_cast<size_t*>(obj);
+ *ret_header = size;
+ return obj + offset;
+}
+

+static void mapped_free_large(void *object)
+{

+ object = align_down(object - 1, mmu::page_size);
+ size_t* ret_header = static_cast<size_t*>(object);
+ mmu::munmap(object, *ret_header);
+}

+
+static void* malloc_large(size_t size, size_t alignment, bool block = true, bool contiguous = true)
{
auto requested_size = size;
size_t offset;

@@ -835,6 +850,14 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)

size += offset;
size = align_up(size, page_size);

+ // Use mmap if requested memory greater than "huge page" size
+ // and does not need to be contiguous
+ if (size >= mmu::huge_page_size && !contiguous) {
+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
+ }
+
while (true) {
WITH_LOCK(free_page_ranges_lock) {
reclaimer_thread.wait_for_minimum_memory();

@@ -842,7 +865,7 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)

if (alignment > page_size) {
ret_header = free_page_ranges.alloc_aligned(size, page_size, alignment);
} else {
- ret_header = free_page_ranges.alloc(size);
+ ret_header = free_page_ranges.alloc(size, contiguous);
}
if (ret_header) {
on_alloc(size);

@@ -850,6 +873,11 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)

obj += offset;
trace_memory_malloc_large(obj, requested_size, size, alignment);
return obj;
+ } else if (!contiguous) {
+ // If we failed to get contiguous memory allocation and
+ // the caller does not require one let us use map-based allocation

+ // which we do after the loop below

+ break;
}
if (block)
reclaimer_thread.wait_for_memory(size);

@@ -857,6 +885,15 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
return nullptr;
}
}
+
+ // We are deliberately executing this code here because doing it
+ // in WITH_LOCK section above, would likely lead to a deadlock,
+ // as map_anon() eventually would be pulling memory from free_page_ranges
+ // to satisfy the request and even worse this method might get
+ // called recursively.

+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
}

void shrinker::deactivate_shrinker()
@@ -1070,11 +1107,18 @@ static void free_large(void* obj)
free_page_range(static_cast<page_range*>(obj));
}

-static unsigned large_object_size(void *obj)
+static size_t large_object_offset(void *&obj)
{
+ void *original_obj = obj;

obj = align_down(obj - 1, page_size);

+ return reinterpret_cast<uint64_t>(original_obj) - reinterpret_cast<uint64_t>(obj);
+}
+
+static size_t large_object_size(void *obj)
+{
+ size_t offset = large_object_offset(obj);

auto header = static_cast<page_range*>(obj);
- return header->size;
+ return header->size - offset;
}

namespace page_pool {
@@ -1692,7 +1736,7 @@ static inline void* std_malloc(size_t size, size_t alignment)

memory::alloc_page());
trace_memory_malloc_page(ret, size, mmu::page_size, alignment);
} else {
- ret = memory::malloc_large(size, alignment);
+ ret = memory::malloc_large(size, alignment, true, false);
}
memory::tracker_remember(ret, size);
return ret;

@@ -1714,6 +1758,12 @@ void* calloc(size_t nmemb, size_t size)

static size_t object_size(void *object)
{
+ if (!mmu::is_linear_mapped(object, 0)) {

+ size_t offset = memory::large_object_offset(object);

+ size_t* ret_header = static_cast<size_t*>(object);
+ return *ret_header - offset;

+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::main:
return memory::large_object_size(object);

@@ -1763,6 +1813,11 @@ void free(void* object)

return;
}
memory::tracker_forget(object);
+
+ if (!mmu::is_linear_mapped(object, 0)) {

+ return memory::mapped_free_large(object);

+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::page:
object = mmu::translate_mem_area(mmu::mem_area::page,

@@ -1972,7 +2027,7 @@ void* alloc_phys_contiguous_aligned(size_t size, size_t align, bool block)

[Waldek Kozaczuk]

I have just sent two new V5 patches. One extra question below in case that might be an issue as well.

Not sure if above and below when we call mapped_malloc_large() we need to do something extra  if (alignment > page_size). What do you think? 

To unsubscribe from this group and stop receiving emails from it, send an email to osv-dev+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/a71c97ed-0dbe-4570-b345-b046532a55aa%40googlegroups.com.

[Commit Bot]

From: Waldemar Kozaczuk <jwkoz...@gmail.com>
Committer: Waldemar Kozaczuk <jwkoz...@gmail.com>
Branch: master

mempool: fix a bug in page_range_allocator() when handling worst case O(n) scenario

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>

---

diff --git a/core/mempool.cc b/core/mempool.cc
--- a/core/mempool.cc
+++ b/core/mempool.cc
@@ -702,10 +702,13 @@ page_range* page_range_allocator::alloc(size_t size)

for (auto&& pr : _free[exact_order - 1]) {
if (pr.size >= size) {
range = &pr;

[Commit Bot]

From: Waldemar Kozaczuk <jwkoz...@gmail.com>
Committer: Waldemar Kozaczuk <jwkoz...@gmail.com>
Branch: master

mempool: use map_anon() for large allocations or when memory is fragmented

This patch mostly addresses the issue #854. In essence it changes malloc_large()
to use mmu::map_anon() if requested memory is greater than size of "huge page"
and it does not have be contiguous in physical memory. Also it makes it fallback
to map_anon() based allocation for requests > 4K and < 2MB that cannot be satisfied
when memory is heavily fragmented.

It is supposed to help OSv memory allocation behave better when memory
in free_page_ranges is heavily fragmented and large allocations (>=2MB)
cannot be satisfied with single contiguous page range. When working on
this patch it has also become clear, that applications that heavily use realloc()
which allocates new chunks of memory and frees old ones, might very much encounter
heavy fragmentation of memory. Hopefully this patch is going to help
in these scenarios.

It just happens that object_size() and large_object_size() needed to be
adjusted to work with new malloc_large() implementation. It was discovered
that therefore other related issues are fixed by this patch as well.

Lastly this patch adds new test verifying realloc() and malloc_usable_size().

Fixes #784
Fixes #854
Fixes #1077

Signed-off-by: Waldemar Kozaczuk <jwkoz...@gmail.com>

---
diff --git a/core/mempool.cc b/core/mempool.cc
--- a/core/mempool.cc
+++ b/core/mempool.cc

@@ -546,7 +546,7 @@ class page_range_allocator {

page_range_allocator() : _deferred_free(nullptr) { }

template<bool UseBitmap = true>
- page_range* alloc(size_t size);
+ page_range* alloc(size_t size, bool contiguous = true);
page_range* alloc_aligned(size_t size, size_t offset, size_t alignment,
bool fill = false);
void free(page_range* pr);
@@ -678,7 +678,7 @@ void page_range_allocator::bitmap_allocator<T>::deallocate(T* p, size_t n)
}

template<bool UseBitmap>
-page_range* page_range_allocator::alloc(size_t size)
+page_range* page_range_allocator::alloc(size_t size, bool contiguous)
{
auto exact_order = ilog2_roundup(size / page_size);
if (exact_order > max_order) {

@@ -692,13 +692,12 @@ page_range* page_range_allocator::alloc(size_t size)

page_range* range = nullptr;
if (!bitset) {
- if (!exact_order || _free[exact_order - 1].empty()) {
+ if (!contiguous || !exact_order || _free[exact_order - 1].empty()) {
return nullptr;
}
- // TODO: This linear search makes worst case complexity of the allocator
- // O(n). It would be better to fall back to non-contiguous allocation
- // and make worst case complexity depend on the size of requested memory
- // block and the logarithm of the number of free huge page ranges.
+ // This linear search makes worst case complexity of the allocator
+ // O(n). Unfortunately we do not have choice for contiguous allocation
+ // so let us hope there is large enough range.

for (auto&& pr : _free[exact_order - 1]) {
if (pr.size >= size) {
range = &pr;

@@ -823,7 +822,23 @@ void page_range_allocator::for_each(unsigned min_order, Func f)

}
}

-static void* malloc_large(size_t size, size_t alignment, bool block = true)
+static void* mapped_malloc_large(size_t size, size_t offset)
+{
+ //TODO: For now pre-populate the memory, in future consider doing lazy population
+ void* obj = mmu::map_anon(nullptr, size, mmu::mmap_populate, mmu::perm_read | mmu::perm_write);
+ size_t* ret_header = static_cast<size_t*>(obj);
+ *ret_header = size;
+ return obj + offset;
+}
+

+static void mapped_free_large(void *object)
+{

+ object = align_down(object - 1, mmu::page_size);
+ size_t* ret_header = static_cast<size_t*>(object);
+ mmu::munmap(object, *ret_header);
+}

+
+static void* malloc_large(size_t size, size_t alignment, bool block = true, bool contiguous = true)
{
auto requested_size = size;
size_t offset;

@@ -835,28 +850,50 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)

size += offset;
size = align_up(size, page_size);

+ // Use mmap if requested memory greater than "huge page" size
+ // and does not need to be contiguous
+ if (size >= mmu::huge_page_size && !contiguous) {
+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
+ }
+

while (true) {
WITH_LOCK(free_page_ranges_lock) {
reclaimer_thread.wait_for_minimum_memory();
page_range* ret_header;

if (alignment > page_size) {
ret_header = free_page_ranges.alloc_aligned(size, page_size, alignment);
} else {
- ret_header = free_page_ranges.alloc(size);
+ ret_header = free_page_ranges.alloc(size, contiguous);
}
if (ret_header) {
on_alloc(size);

void* obj = ret_header;

obj += offset;
trace_memory_malloc_large(obj, requested_size, size, alignment);
return obj;
+ } else if (!contiguous) {
+ // If we failed to get contiguous memory allocation and
+ // the caller does not require one let us use map-based allocation

+ // which we do after the loop below

+ break;
}
if (block)
reclaimer_thread.wait_for_memory(size);

else

return nullptr;
}
}
+
+ // We are deliberately executing this code here because doing it
+ // in WITH_LOCK section above, would likely lead to a deadlock,
+ // as map_anon() eventually would be pulling memory from free_page_ranges
+ // to satisfy the request and even worse this method might get
+ // called recursively.

+ void* obj = mapped_malloc_large(size, offset);
+ trace_memory_malloc_large(obj, requested_size, size, alignment);
+ return obj;
}

void shrinker::deactivate_shrinker()
@@ -1070,11 +1107,18 @@ static void free_large(void* obj)
free_page_range(static_cast<page_range*>(obj));
}

-static unsigned large_object_size(void *obj)
+static size_t large_object_offset(void *&obj)
{

+ void *original_obj = obj;

obj = align_down(obj - 1, page_size);

+ return reinterpret_cast<uint64_t>(original_obj) - reinterpret_cast<uint64_t>(obj);
+}
+
+static size_t large_object_size(void *obj)
+{
+ size_t offset = large_object_offset(obj);

auto header = static_cast<page_range*>(obj);
- return header->size;
+ return header->size - offset;
}

namespace page_pool {
@@ -1692,7 +1736,7 @@ static inline void* std_malloc(size_t size, size_t alignment)

memory::alloc_page());
trace_memory_malloc_page(ret, size, mmu::page_size, alignment);
} else {
- ret = memory::malloc_large(size, alignment);
+ ret = memory::malloc_large(size, alignment, true, false);
}
memory::tracker_remember(ret, size);
return ret;

@@ -1714,6 +1758,12 @@ void* calloc(size_t nmemb, size_t size)

static size_t object_size(void *object)
{
+ if (!mmu::is_linear_mapped(object, 0)) {

+ size_t offset = memory::large_object_offset(object);

+ size_t* ret_header = static_cast<size_t*>(object);
+ return *ret_header - offset;

+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::main:
return memory::large_object_size(object);

@@ -1763,6 +1813,11 @@ void free(void* object)

return;
}
memory::tracker_forget(object);
+
+ if (!mmu::is_linear_mapped(object, 0)) {

+ return memory::mapped_free_large(object);

+ }
+
switch (mmu::get_mem_area(object)) {
case mmu::mem_area::page:
object = mmu::translate_mem_area(mmu::mem_area::page,

@@ -1972,7 +2027,7 @@ void* alloc_phys_contiguous_aligned(size_t size, size_t align, bool block)

assert(is_power_of_two(align));
// make use of the standard large allocator returning properly aligned
// physically contiguous memory:
- auto ret = malloc_large(size, align, block);
+ auto ret = malloc_large(size, align, block, true);
assert (!(reinterpret_cast<uintptr_t>(ret) & (align - 1)));
return ret;
}
diff --git a/modules/tests/Makefile b/modules/tests/Makefile

--- a/modules/tests/Makefile
+++ b/modules/tests/Makefile
@@ -129,7 +129,7 @@ tests := tst-pthread.so misc-ramdisk.so tst-vblk.so tst-bsd-evh.so \
tst-sigaltstack.so tst-fread.so tst-tcp-cork.so tst-tcp-v6.so \
tst-calloc.so tst-crypt.so tst-non-fpic.so tst-small-malloc.so \
tst-mmx-fpu.so tst-getopt.so tst-getopt-pie.so tst-non-pie.so tst-semaphore.so \
- tst-elf-init.so
+ tst-elf-init.so tst-realloc.so
# libstatic-thread-variable.so tst-static-thread-variable.so \

tests += testrunner.so
diff --git a/tests/tst-realloc.cc b/tests/tst-realloc.cc

--- a/tests/tst-realloc.cc

[Nadav Har'El]

On Sun, Mar 29, 2020 at 8:01 PM Waldek Kozaczuk <jwkoz...@gmail.com> wrote:

I have just sent two new V5 patches. One extra question below in case that might be an issue as well.

On Sun, Mar 29, 2020 at 12:28 PM Waldek Kozaczuk <jwkoz...@gmail.com> wrote:

+static void* malloc_large(size_t size, size_t alignment, bool block = true, bool contiguous = true)

 {
     auto requested_size = size;
     size_t offset;
@@ -835,6 +843,14 @@ static void* malloc_large(size_t size, size_t alignment, bool block = true)
     size += offset;
     size = align_up(size, page_size);

+    // Use mmap if requested memory greater than "huge page" size
+    // and does not need to be contiguous
+    if (size >= mmu::huge_page_size && !contiguous) {
+        void* obj = mapped_malloc_large(size, offset);
+        trace_memory_malloc_large(obj, requested_size, size, alignment);
+        return obj;
+    }
+

Not sure if above and below when we call mapped_malloc_large() we need to do something extra  if (alignment > page_size). What do you think? 

It's a good question. You're right, but I don't know if this even worked correctly in the past. However, importantly, in the functions alloc_phys_contiguous_aligned() and posix_memalign(),  we end the function by asserting that whatever underlying functions we called, the returned pointer has the desired alignment. So if we have a bug in this case (and I think we do) it will at least cause an assertion failure - and not silently return wrongly aligned memory.

I'll commit your code with this issue, and we can address it later. I doubt anybody actually need such huge alignments in real-world applications (what's the point?).

 

To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/CAL9cFfPiQRW2RPAM9d6LnpkqE5Yz%2BCdBMrZ6O-vfvu_TXLhHTg%40mail.gmail.com.

[Waldek Kozaczuk]

I have just committed myself :-)

[Nadav Har'El]

Why does this code assume the start of the object has a size_t (by the way, above you used uint64_t, better be consistent) and not

a page_range?

--
You received this message because you are subscribed to the Google Groups "OSv Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to osv-dev+u...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/20200329165640.23961-2-jwkozaczuk%40gmail.com.

[Waldek Kozaczuk]

Because mapped_malloc_large() stores allocated (mapped) size in the size_t field located at the very beginning of the allocated area. Which is different from non-mapped allocation that stores data including size n the page_range struct. I think it would be confusing if we used page_range for both (which is what I did in my very first version of this patch). Also, uint64_t is used in large_object_offset() to calculate an offset - distance between the start of the allocated memory and the object address - so I am not sure how this relates to the size_t field. 

Or maybe my latest version of this patch had made this part less readable -  memory::large_object_offset() calculates offset but also modifies object argument  - see it accepts a reference to a pointer.

I may have made here but I am not sure I clearly see it.

To unsubscribe from this group and stop receiving emails from it, send an email to osv...@googlegroups.com.

[Nadav Har'El]

Oh, I didn't notice that. I remembered (from the first version I reviewed, I guess) that you used the same page_range struct.

 

Also, uint64_t is used in large_object_offset() to calculate an offset - distance between the start of the allocated memory and the object address - so I am not sure how this relates to the size_t field. 

What I meant was that when you calculate difference, or add, pointers, it works in multiples of the pointed-type size. So if you calculated the difference between two uint64_t* pointers, you shouldn't add it to a size_t* pointer. Of course, in practice, it will work (because uint64_t and size_t are the same) but it's strange.

To unsubscribe from this group and stop receiving emails from it, send an email to osv-dev+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/ff0b4296-edbb-42ea-a75c-7a27e71a81dc%40googlegroups.com.