Let me try to address your comments and send V5. On Sunday, March 29, 2020 at 11:21:00 AM UTC-4, Nadav Har'El wrote: > > > On Sun, Mar 29, 2020 at 5:37 PM Waldek Kozaczuk <[email protected] > <javascript:>> 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! > > >>> 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, >> >>> >>> -- >>> Nadav Har'El >>> [email protected] >>> >>> >>> On Thu, Mar 26, 2020 at 8:36 PM Waldemar Kozaczuk <[email protected]> >>> 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. >>> >>> >>>> Lastly this patch adds new test verifying realloc() and >>>> malloc_usable_size(). >>>> >>>> Signed-off-by: Waldemar Kozaczuk <[email protected]> >>>> --- >>>> 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 >>>> --- 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 = ≺ >>>> @@ -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 = 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; >>>> + } >>>> + >>>> 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; >>>> >>> >>> 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. >>> >>> + } >>>> + >>>> 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 >>>> >>>> -- >>>> 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 [email protected]. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msgid/osv-dev/20200326183626.12013-1-jwkozaczuk%40gmail.com >>>> . >>>> >>> -- >> 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 [email protected] <javascript:>. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/osv-dev/29288786-0656-4ab7-b068-c6b249e2dfa3%40googlegroups.com >> >> <https://groups.google.com/d/msgid/osv-dev/29288786-0656-4ab7-b068-c6b249e2dfa3%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> >
-- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/osv-dev/4f353577-06bf-4ca8-b708-c5ed4c1d7bc8%40googlegroups.com.
