diff options
author | Costa Tsaousis <costa@netdata.cloud> | 2022-07-08 00:09:33 +0300 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-07-08 00:09:33 +0300 |
commit | a6da6beb71f31ed5e89d9ed7a5a7d3242cdd8d8e (patch) | |
tree | 823697f4efceffb661f3080309ae737354c4bf39 /libnetdata | |
parent | 7f144682083bb334d38a527e7c9bd4bc736575eb (diff) |
array allocator for dbengine page descriptors (#13312)
* array allocator for dbengine page descriptors
* full implementation of array allocator with cleanup
* faster deallocations
* eliminate entierely the need for loops during free
* addressed comments
* lower the min number of elements to 10
Diffstat (limited to 'libnetdata')
-rw-r--r-- | libnetdata/Makefile.am | 1 | ||||
-rw-r--r-- | libnetdata/arrayalloc/Makefile.am | 8 | ||||
-rw-r--r-- | libnetdata/arrayalloc/README.md | 7 | ||||
-rw-r--r-- | libnetdata/arrayalloc/arrayalloc.c | 334 | ||||
-rw-r--r-- | libnetdata/arrayalloc/arrayalloc.h | 35 | ||||
-rw-r--r-- | libnetdata/libnetdata.h | 1 | ||||
-rw-r--r-- | libnetdata/onewayalloc/onewayalloc.c | 10 |
7 files changed, 391 insertions, 5 deletions
diff --git a/libnetdata/Makefile.am b/libnetdata/Makefile.am index 167d05caa1..5962323e87 100644 --- a/libnetdata/Makefile.am +++ b/libnetdata/Makefile.am @@ -5,6 +5,7 @@ MAINTAINERCLEANFILES = $(srcdir)/Makefile.in SUBDIRS = \ adaptive_resortable_list \ + arrayalloc \ avl \ buffer \ clocks \ diff --git a/libnetdata/arrayalloc/Makefile.am b/libnetdata/arrayalloc/Makefile.am new file mode 100644 index 0000000000..161784b8f6 --- /dev/null +++ b/libnetdata/arrayalloc/Makefile.am @@ -0,0 +1,8 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in + +dist_noinst_DATA = \ + README.md \ + $(NULL) diff --git a/libnetdata/arrayalloc/README.md b/libnetdata/arrayalloc/README.md new file mode 100644 index 0000000000..2f21bf3ff5 --- /dev/null +++ b/libnetdata/arrayalloc/README.md @@ -0,0 +1,7 @@ +<!-- +title: "Array Allocator" +custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/arrayalloc/README.md +--> + +# Array Allocator + diff --git a/libnetdata/arrayalloc/arrayalloc.c b/libnetdata/arrayalloc/arrayalloc.c new file mode 100644 index 0000000000..9657727313 --- /dev/null +++ b/libnetdata/arrayalloc/arrayalloc.c @@ -0,0 +1,334 @@ +#include "../libnetdata.h" +#include "arrayalloc.h" +#include "daemon/common.h" + +// max file size +#define ARAL_MAX_PAGE_SIZE_MMAP (1*1024*1024*1024) + +// max malloc size +#define ARAL_MAX_PAGE_SIZE_MALLOC (10*1024*1024) + +typedef struct arrayalloc_free { + size_t size; + struct arrayalloc_page *page; + struct arrayalloc_free *next; +} ARAL_FREE; + +typedef struct arrayalloc_page { + const char *filename; + size_t size; // the total size of the page + size_t used_elements; // the total number of used elements on this page + uint8_t *data; + ARAL_FREE *free_list; + struct arrayalloc_page *prev; // the prev page on the list + struct arrayalloc_page *next; // the next page on the list +} ARAL_PAGE; + +#define ARAL_NATURAL_ALIGNMENT (sizeof(uintptr_t) * 2) +static inline size_t natural_alignment(size_t size, size_t alignment) { + if(unlikely(size % alignment)) + size = size + alignment - (size % alignment); + + return size; +} + +static void arrayalloc_init(ARAL *ar) { + static netdata_mutex_t mutex = NETDATA_MUTEX_INITIALIZER; + netdata_mutex_lock(&mutex); + + if(!ar->internal.initialized) { + netdata_mutex_init(&ar->internal.mutex); + + long int page_size = sysconf(_SC_PAGE_SIZE); + if (unlikely(page_size == -1)) + ar->internal.natural_page_size = 4096; + else + ar->internal.natural_page_size = page_size; + + // we need to add a page pointer after the element + // so, first align the element size to the pointer size + ar->internal.element_size = natural_alignment(ar->element_size, sizeof(uintptr_t)); + + // then add the size of a pointer to it + ar->internal.element_size = ar->internal.element_size + sizeof(uintptr_t); + + // make sure it is at least what we need for an ARAL_FREE slot + if (ar->internal.element_size < sizeof(ARAL_FREE)) + ar->internal.element_size = sizeof(ARAL_FREE); + + // and finally align it to the natural alignment + ar->internal.element_size = natural_alignment(ar->element_size, ARAL_NATURAL_ALIGNMENT); + + // this is where we should write the pointer + ar->internal.page_ptr_offset = ar->internal.element_size - sizeof(uintptr_t); + + if(ar->element_size + sizeof(uintptr_t) > ar->internal.element_size) + fatal("ARRAYALLOC: failed to calculate properly page_ptr_offset: element size %zu, sizeof(uintptr_t) %zu, natural alignment %zu, final element size %zu, page_ptr_offset %zu", + ar->element_size, sizeof(uintptr_t), ARAL_NATURAL_ALIGNMENT, ar->internal.element_size, ar->internal.page_ptr_offset); + + //info("ARRAYALLOC: element size %zu, sizeof(uintptr_t) %zu, natural alignment %zu, final element size %zu, page_ptr_offset %zu", + // ar->element_size, sizeof(uintptr_t), ARAL_NATURAL_ALIGNMENT, ar->internal.element_size, ar->internal.page_ptr_offset); + + if (ar->elements < 10) + ar->elements = 10; + + ar->internal.mmap = (ar->use_mmap && ar->cache_dir && *ar->cache_dir) ? true : false; + ar->internal.max_alloc_size = ar->internal.mmap ? ARAL_MAX_PAGE_SIZE_MMAP : ARAL_MAX_PAGE_SIZE_MALLOC; + + if(ar->internal.max_alloc_size % ar->internal.natural_page_size) + ar->internal.max_alloc_size += ar->internal.natural_page_size - (ar->internal.max_alloc_size % ar->internal.natural_page_size) ; + + if(ar->internal.max_alloc_size % ar->internal.element_size) + ar->internal.max_alloc_size -= ar->internal.max_alloc_size % ar->internal.element_size; + + ar->internal.first_page = NULL; + ar->internal.last_page = NULL; + ar->internal.allocation_multiplier = 1; + ar->internal.file_number = 0; + + if(ar->internal.mmap) { + char filename[FILENAME_MAX + 1]; + snprintfz(filename, FILENAME_MAX, "%s/array_alloc.mmap", *ar->cache_dir); + int r = mkdir(filename, 0775); + if (r != 0 && errno != EEXIST) + fatal("Cannot create directory '%s'", filename); + } + + ar->internal.initialized = true; + } + + netdata_mutex_unlock(&mutex); +} + +#ifdef NETDATA_INTERNAL_CHECKS +static inline void arrayalloc_free_checks(ARAL *ar, ARAL_FREE *fr) { + if(fr->size < ar->internal.element_size) + fatal("ARRAYALLOC: free item of size %zu, less than the expected element size %zu", fr->size, ar->internal.element_size); + + if(fr->size % ar->internal.element_size) + fatal("ARRAYALLOC: free item of size %zu is not multiple to element size %zu", fr->size, ar->internal.element_size); +} +#else +#define arrayalloc_free_checks(ar, fr) debug_dummy() +#endif + +static inline void unlink_page(ARAL *ar, ARAL_PAGE *page) { + if(unlikely(!page)) return; + + if(page->next) + page->next->prev = page->prev; + + if(page->prev) + page->prev->next = page->next; + + if(page == ar->internal.first_page) + ar->internal.first_page = page->next; + + if(page == ar->internal.last_page) + ar->internal.last_page = page->prev; +} + +static inline void link_page_first(ARAL *ar, ARAL_PAGE *page) { + page->prev = NULL; + page->next = ar->internal.first_page; + if(page->next) page->next->prev = page; + + ar->internal.first_page = page; + + if(!ar->internal.last_page) + ar->internal.last_page = page; +} + +static inline void link_page_last(ARAL *ar, ARAL_PAGE *page) { + page->next = NULL; + page->prev = ar->internal.last_page; + if(page->prev) page->prev->next = page; + + ar->internal.last_page = page; + + if(!ar->internal.first_page) + ar->internal.first_page = page; +} + +static inline ARAL_PAGE *find_page_with_allocation(ARAL *ar, void *ptr) { + size_t seeking = (size_t)ptr; + ARAL_PAGE *page; + + for(page = ar->internal.first_page; page ; page = page->next) { + if(unlikely(seeking >= (size_t)page->data && seeking < (size_t)page->data + page->size)) + break; + } + + return page; +} + +static void arrayalloc_increase(ARAL *ar) { + if(unlikely(!ar->internal.initialized)) + arrayalloc_init(ar); + + ARAL_PAGE *page = callocz(1, sizeof(ARAL_PAGE)); + page->size = ar->elements * ar->internal.element_size * ar->internal.allocation_multiplier; + if(page->size > ar->internal.max_alloc_size) + page->size = ar->internal.max_alloc_size; + else + ar->internal.allocation_multiplier *= 2; + + if(ar->internal.mmap) { + ar->internal.file_number++; + char filename[FILENAME_MAX + 1]; + snprintfz(filename, FILENAME_MAX, "%s/array_alloc.mmap/%s.%zu", *ar->cache_dir, ar->filename, ar->internal.file_number); + page->filename = strdupz(filename); + page->data = netdata_mmap(page->filename, page->size, MAP_SHARED, 0); + if (unlikely(!page->data)) + fatal("Cannot allocate arrayalloc buffer of size %zu on filename '%s'", page->size, page->filename); + } + else + page->data = mallocz(page->size); + + // link the free space to its page + ARAL_FREE *fr = (ARAL_FREE *)page->data; + fr->size = page->size; + fr->page = page; + fr->next = NULL; + page->free_list = fr; + + // link the new page at the front of the list of pages + link_page_first(ar, page); + + arrayalloc_free_checks(ar, fr); +} + +static void arrayalloc_lock(ARAL *ar) { + if(!ar->internal.lockless) + netdata_mutex_lock(&ar->internal.mutex); +} + +static void arrayalloc_unlock(ARAL *ar) { + if(!ar->internal.lockless) + netdata_mutex_unlock(&ar->internal.mutex); +} + +ARAL *arrayalloc_create(size_t element_size, size_t elements, const char *filename, char **cache_dir) { + ARAL *ar = callocz(1, sizeof(ARAL)); + ar->element_size = element_size; + ar->elements = elements; + ar->filename = filename; + ar->cache_dir = cache_dir; + return ar; +} + +void *arrayalloc_mallocz(ARAL *ar) { + arrayalloc_lock(ar); + + if(unlikely(!ar->internal.first_page || !ar->internal.first_page->free_list)) + arrayalloc_increase(ar); + + ARAL_PAGE *page = ar->internal.first_page; + ARAL_FREE *fr = page->free_list; + + if(unlikely(!fr)) + fatal("ARRAYALLOC: free item cannot be NULL."); + + if(unlikely(fr->size < ar->internal.element_size)) + fatal("ARRAYALLOC: free item size %zu is smaller than %zu", fr->size, ar->internal.element_size); + + if(fr->size - ar->internal.element_size <= ar->internal.element_size) { + // we are done with this page + page->free_list = NULL; + + if(page != ar->internal.last_page) { + unlink_page(ar, page); + link_page_last(ar, page); + } + } + else { + uint8_t *data = (uint8_t *)fr; + ARAL_FREE *fr2 = (ARAL_FREE *)&data[ar->internal.element_size]; + fr2->page = fr->page; + fr2->size = fr->size - ar->internal.element_size; + fr2->next = fr->next; + page->free_list = fr2; + + arrayalloc_free_checks(ar, fr2); + } + + fr->page->used_elements++; + + // put the page pointer after the element + uint8_t *data = (uint8_t *)fr; + ARAL_PAGE **page_ptr = (ARAL_PAGE **)&data[ar->internal.page_ptr_offset]; + *page_ptr = page; + + arrayalloc_unlock(ar); + return (void *)fr; +} + +void arrayalloc_freez(ARAL *ar, void *ptr) { + if(!ptr) return; + arrayalloc_lock(ar); + + // get the page pointer + ARAL_PAGE *page; + { + uint8_t *data = (uint8_t *)ptr; + ARAL_PAGE **page_ptr = (ARAL_PAGE **)&data[ar->internal.page_ptr_offset]; + page = *page_ptr; + +#ifdef NETDATA_INTERNAL_CHECKS + // make it NULL so that we will fail on double free + // do not enable this on production, because the MMAP file + // will need to be saved again! + *page_ptr = NULL; +#endif + } + +#ifdef NETDATA_INTERNAL_CHECKS + { + // find the page ptr belongs + ARAL_PAGE *page2 = find_page_with_allocation(ar, ptr); + + if(unlikely(page != page2)) + fatal("ARRAYALLOC: page pointers do not match!"); + + if (unlikely(!page2)) + fatal("ARRAYALLOC: free of pointer %p is not in arrayalloc address space.", ptr); + } +#endif + + if(unlikely(!page)) + fatal("ARRAYALLOC: possible corruption or double free of pointer %p", ptr); + + if (unlikely(!page->used_elements)) + fatal("ARRAYALLOC: free of pointer %p is inside a page without any active allocations.", ptr); + + page->used_elements--; + + // make this element available + ARAL_FREE *fr = (ARAL_FREE *)ptr; + fr->page = page; + fr->size = ar->internal.element_size; + fr->next = page->free_list; + page->free_list = fr; + + // if the page is empty, release it + if(!page->used_elements) { + unlink_page(ar, page); + + // free it + if(ar->internal.mmap) { + munmap(page->data, page->size); + unlink(page->filename); + freez((void *)page->filename); + } + else + freez(page->data); + + freez(page); + } + else if(page != ar->internal.first_page) { + unlink_page(ar, page); + link_page_first(ar, page); + } + + arrayalloc_unlock(ar); +} diff --git a/libnetdata/arrayalloc/arrayalloc.h b/libnetdata/arrayalloc/arrayalloc.h new file mode 100644 index 0000000000..e0e9e7f9f5 --- /dev/null +++ b/libnetdata/arrayalloc/arrayalloc.h @@ -0,0 +1,35 @@ + +#ifndef ARRAYALLOC_H +#define ARRAYALLOC_H 1 + +#include "../libnetdata.h" + +typedef struct arrayalloc { + size_t element_size; + size_t elements; + const char *filename; + char **cache_dir; + bool use_mmap; + + // private members - do not touch + struct { + bool mmap; + bool lockless; + bool initialized; + size_t element_size; + size_t page_ptr_offset; + size_t file_number; + size_t natural_page_size; + size_t allocation_multiplier; + size_t max_alloc_size; + netdata_mutex_t mutex; + struct arrayalloc_page *first_page; + struct arrayalloc_page *last_page; + } internal; +} ARAL; + +extern ARAL *arrayalloc_create(size_t element_size, size_t elements, const char *filename, char **cache_dir); +extern void *arrayalloc_mallocz(ARAL *ar); +extern void arrayalloc_freez(ARAL *ar, void *ptr); + +#endif // ARRAYALLOC_H diff --git a/libnetdata/libnetdata.h b/libnetdata/libnetdata.h index 8f4178330e..4e0b45426c 100644 --- a/libnetdata/libnetdata.h +++ b/libnetdata/libnetdata.h @@ -345,6 +345,7 @@ extern char *netdata_configured_host_prefix; #include "json/json.h" #include "health/health.h" #include "string/utf8.h" +#include "arrayalloc/arrayalloc.h" #include "onewayalloc/onewayalloc.h" #include "worker_utilization/worker_utilization.h" diff --git a/libnetdata/onewayalloc/onewayalloc.c b/libnetdata/onewayalloc/onewayalloc.c index 8f980f70f2..8d6e0f598f 100644 --- a/libnetdata/onewayalloc/onewayalloc.c +++ b/libnetdata/onewayalloc/onewayalloc.c @@ -1,9 +1,7 @@ #include "onewayalloc.h" -static size_t OWA_NATURAL_PAGE_SIZE = 0; - // https://www.gnu.org/software/libc/manual/html_node/Aligned-Memory-Blocks.html -#define OWA_NATURAL_ALIGNMENT (sizeof(void *) * 2) +#define OWA_NATURAL_ALIGNMENT (sizeof(uintptr_t) * 2) typedef struct owa_page { size_t stats_pages; @@ -30,6 +28,8 @@ static inline size_t natural_alignment(size_t size) { // any number of times, for any amount of memory. static OWA_PAGE *onewayalloc_create_internal(OWA_PAGE *head, size_t size_hint) { + static size_t OWA_NATURAL_PAGE_SIZE = 0; + if(unlikely(!OWA_NATURAL_PAGE_SIZE)) { long int page_size = sysconf(_SC_PAGE_SIZE); if (unlikely(page_size == -1)) @@ -82,11 +82,11 @@ static OWA_PAGE *onewayalloc_create_internal(OWA_PAGE *head, size_t size_hint) { head->stats_pages++; head->stats_pages_size += size; - return (ONEWAYALLOC *)page; + return page; } ONEWAYALLOC *onewayalloc_create(size_t size_hint) { - return onewayalloc_create_internal(NULL, size_hint); + return (ONEWAYALLOC *)onewayalloc_create_internal(NULL, size_hint); } void *onewayalloc_mallocz(ONEWAYALLOC *owa, size_t size) { |