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 <[email protected]> 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. >> >> I see you have new realloc() tests - did these tests fail before your >> patches? >> >> -- >> 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; >>> + } >>> + >>> >> 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? > 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? >> > 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. > >> >> >>> + } >>> + >>> 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]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/osv-dev/a71c97ed-0dbe-4570-b345-b046532a55aa%40googlegroups.com > <https://groups.google.com/d/msgid/osv-dev/a71c97ed-0dbe-4570-b345-b046532a55aa%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/CAL9cFfPiQRW2RPAM9d6LnpkqE5Yz%2BCdBMrZ6O-vfvu_TXLhHTg%40mail.gmail.com.
