diff options
Diffstat (limited to 'libnetdata/aral/aral.c')
| -rw-r--r-- | libnetdata/aral/aral.c | 1089 |
1 files changed, 0 insertions, 1089 deletions
diff --git a/libnetdata/aral/aral.c b/libnetdata/aral/aral.c deleted file mode 100644 index 7223ee35..00000000 --- a/libnetdata/aral/aral.c +++ /dev/null @@ -1,1089 +0,0 @@ -#include "../libnetdata.h" -#include "aral.h" - -#ifdef NETDATA_TRACE_ALLOCATIONS -#define TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS , const char *file, const char *function, size_t line -#define TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS , file, function, line -#else -#define TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS -#define TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS -#endif - -#define ARAL_FREE_PAGES_DELTA_TO_REARRANGE_LIST 5 - -// max file size -#define ARAL_MAX_PAGE_SIZE_MMAP (1*1024*1024*1024) - -// max malloc size -// optimal at current versions of libc is up to 256k -// ideal to have the same overhead as libc is 4k -#define ARAL_MAX_PAGE_SIZE_MALLOC (65*1024) - -typedef struct aral_free { - size_t size; - struct aral_free *next; -} ARAL_FREE; - -typedef struct aral_page { - size_t size; // the allocation size of the page - const char *filename; - uint8_t *data; - - uint32_t free_elements_to_move_first; - uint32_t max_elements; // the number of elements that can fit on this page - - struct { - uint32_t used_elements; // the number of used elements on this page - uint32_t free_elements; // the number of free elements on this page - - struct aral_page *prev; // the prev page on the list - struct aral_page *next; // the next page on the list - } aral_lock; - - struct { - SPINLOCK spinlock; - ARAL_FREE *list; - } free; - -} ARAL_PAGE; - -typedef enum { - ARAL_LOCKLESS = (1 << 0), - ARAL_DEFRAGMENT = (1 << 1), - ARAL_ALLOCATED_STATS = (1 << 2), -} ARAL_OPTIONS; - -struct aral { - struct { - char name[ARAL_MAX_NAME + 1]; - - ARAL_OPTIONS options; - - size_t element_size; // calculated to take into account ARAL overheads - size_t max_allocation_size; // calculated in bytes - size_t max_page_elements; // calculated - size_t page_ptr_offset; // calculated - size_t natural_page_size; // calculated - - size_t initial_page_elements; - size_t requested_element_size; - size_t requested_max_page_size; - - struct { - bool enabled; - const char *filename; - char **cache_dir; - } mmap; - } config; - - struct { - SPINLOCK spinlock; - size_t file_number; // for mmap - struct aral_page *pages; // linked list of pages - - size_t user_malloc_operations; - size_t user_free_operations; - size_t defragment_operations; - size_t defragment_linked_list_traversals; - } aral_lock; - - struct { - SPINLOCK spinlock; - size_t allocating_elements; // currently allocating elements - size_t allocation_size; // current / next allocation size - } adders; - - struct { - size_t allocators; // the number of threads currently trying to allocate memory - } atomic; - - struct aral_statistics *stats; -}; - -size_t aral_structures_from_stats(struct aral_statistics *stats) { - return __atomic_load_n(&stats->structures.allocated_bytes, __ATOMIC_RELAXED); -} - -size_t aral_overhead_from_stats(struct aral_statistics *stats) { - return __atomic_load_n(&stats->malloc.allocated_bytes, __ATOMIC_RELAXED) - - __atomic_load_n(&stats->malloc.used_bytes, __ATOMIC_RELAXED); -} - -size_t aral_overhead(ARAL *ar) { - return aral_overhead_from_stats(ar->stats); -} - -size_t aral_structures(ARAL *ar) { - return aral_structures_from_stats(ar->stats); -} - -struct aral_statistics *aral_statistics(ARAL *ar) { - return ar->stats; -} - -#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 size_t aral_align_alloc_size(ARAL *ar, uint64_t size) { - if(size % ar->config.natural_page_size) - size += ar->config.natural_page_size - (size % ar->config.natural_page_size) ; - - if(size % ar->config.element_size) - size -= size % ar->config.element_size; - - return size; -} - -static inline void aral_lock(ARAL *ar) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - spinlock_lock(&ar->aral_lock.spinlock); -} - -static inline void aral_unlock(ARAL *ar) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - spinlock_unlock(&ar->aral_lock.spinlock); -} - -static inline void aral_page_free_lock(ARAL *ar, ARAL_PAGE *page) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - spinlock_lock(&page->free.spinlock); -} - -static inline void aral_page_free_unlock(ARAL *ar, ARAL_PAGE *page) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - spinlock_unlock(&page->free.spinlock); -} - -static inline bool aral_adders_trylock(ARAL *ar) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - return spinlock_trylock(&ar->adders.spinlock); - - return true; -} - -static inline void aral_adders_lock(ARAL *ar) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - spinlock_lock(&ar->adders.spinlock); -} - -static inline void aral_adders_unlock(ARAL *ar) { - if(likely(!(ar->config.options & ARAL_LOCKLESS))) - spinlock_unlock(&ar->adders.spinlock); -} - -static void aral_delete_leftover_files(const char *name, const char *path, const char *required_prefix) { - DIR *dir = opendir(path); - if(!dir) return; - - char full_path[FILENAME_MAX + 1]; - size_t len = strlen(required_prefix); - - struct dirent *de = NULL; - while((de = readdir(dir))) { - if(de->d_type == DT_DIR) - continue; - - if(strncmp(de->d_name, required_prefix, len) != 0) - continue; - - snprintfz(full_path, FILENAME_MAX, "%s/%s", path, de->d_name); - netdata_log_info("ARAL: '%s' removing left-over file '%s'", name, full_path); - if(unlikely(unlink(full_path) == -1)) - netdata_log_error("ARAL: '%s' cannot delete file '%s'", name, full_path); - } - - closedir(dir); -} - -// ---------------------------------------------------------------------------- -// check a free slot - -#ifdef NETDATA_INTERNAL_CHECKS -static inline void aral_free_validate_internal_check(ARAL *ar, ARAL_FREE *fr) { - if(unlikely(fr->size < ar->config.element_size)) - fatal("ARAL: '%s' free item of size %zu, less than the expected element size %zu", - ar->config.name, fr->size, ar->config.element_size); - - if(unlikely(fr->size % ar->config.element_size)) - fatal("ARAL: '%s' free item of size %zu is not multiple to element size %zu", - ar->config.name, fr->size, ar->config.element_size); -} -#else -#define aral_free_validate_internal_check(ar, fr) debug_dummy() -#endif - -// ---------------------------------------------------------------------------- -// find the page a pointer belongs to - -#ifdef NETDATA_INTERNAL_CHECKS -static inline ARAL_PAGE *find_page_with_allocation_internal_check(ARAL *ar, void *ptr) { - aral_lock(ar); - - uintptr_t seeking = (uintptr_t)ptr; - ARAL_PAGE *page; - - for(page = ar->aral_lock.pages; page ; page = page->aral_lock.next) { - if(unlikely(seeking >= (uintptr_t)page->data && seeking < (uintptr_t)page->data + page->size)) - break; - } - - aral_unlock(ar); - - return page; -} -#endif - -// ---------------------------------------------------------------------------- -// find a page with a free slot (there shouldn't be any) - -#ifdef NETDATA_ARAL_INTERNAL_CHECKS -static inline ARAL_PAGE *find_page_with_free_slots_internal_check___with_aral_lock(ARAL *ar) { - ARAL_PAGE *page; - - for(page = ar->aral_lock.pages; page ; page = page->next) { - if(page->aral_lock.free_elements) - break; - - internal_fatal(page->size - page->aral_lock.used_elements * ar->config.element_size >= ar->config.element_size, - "ARAL: '%s' a page is marked full, but it is not!", ar->config.name); - - internal_fatal(page->size < page->aral_lock.used_elements * ar->config.element_size, - "ARAL: '%s' a page has been overflown!", ar->config.name); - } - - return page; -} -#endif - -size_t aral_next_allocation_size___adders_lock_needed(ARAL *ar) { - size_t size = ar->adders.allocation_size; - - if(size > ar->config.max_allocation_size) - size = ar->config.max_allocation_size; - else - ar->adders.allocation_size = aral_align_alloc_size(ar, (uint64_t)ar->adders.allocation_size * 2); - - return size; -} - -static ARAL_PAGE *aral_create_page___no_lock_needed(ARAL *ar, size_t size TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) { - ARAL_PAGE *page = callocz(1, sizeof(ARAL_PAGE)); - spinlock_init(&page->free.spinlock); - page->size = size; - page->max_elements = page->size / ar->config.element_size; - page->aral_lock.free_elements = page->max_elements; - page->free_elements_to_move_first = page->max_elements / 4; - if(unlikely(page->free_elements_to_move_first < 1)) - page->free_elements_to_move_first = 1; - - __atomic_add_fetch(&ar->stats->structures.allocations, 1, __ATOMIC_RELAXED); - __atomic_add_fetch(&ar->stats->structures.allocated_bytes, sizeof(ARAL_PAGE), __ATOMIC_RELAXED); - - if(unlikely(ar->config.mmap.enabled)) { - ar->aral_lock.file_number++; - char filename[FILENAME_MAX + 1]; - snprintfz(filename, FILENAME_MAX, "%s/array_alloc.mmap/%s.%zu", *ar->config.mmap.cache_dir, ar->config.mmap.filename, ar->aral_lock.file_number); - page->filename = strdupz(filename); - page->data = netdata_mmap(page->filename, page->size, MAP_SHARED, 0, false, NULL); - if (unlikely(!page->data)) - fatal("ARAL: '%s' cannot allocate aral buffer of size %zu on filename '%s'", - ar->config.name, page->size, page->filename); - __atomic_add_fetch(&ar->stats->mmap.allocations, 1, __ATOMIC_RELAXED); - __atomic_add_fetch(&ar->stats->mmap.allocated_bytes, page->size, __ATOMIC_RELAXED); - } - else { -#ifdef NETDATA_TRACE_ALLOCATIONS - page->data = mallocz_int(page->size TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS); -#else - page->data = mallocz(page->size); -#endif - __atomic_add_fetch(&ar->stats->malloc.allocations, 1, __ATOMIC_RELAXED); - __atomic_add_fetch(&ar->stats->malloc.allocated_bytes, page->size, __ATOMIC_RELAXED); - } - - // link the free space to its page - ARAL_FREE *fr = (ARAL_FREE *)page->data; - fr->size = page->size; - fr->next = NULL; - page->free.list = fr; - - aral_free_validate_internal_check(ar, fr); - - return page; -} - -void aral_del_page___no_lock_needed(ARAL *ar, ARAL_PAGE *page TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) { - - // free it - if (ar->config.mmap.enabled) { - netdata_munmap(page->data, page->size); - - if (unlikely(unlink(page->filename) == 1)) - netdata_log_error("Cannot delete file '%s'", page->filename); - - freez((void *)page->filename); - - __atomic_sub_fetch(&ar->stats->mmap.allocations, 1, __ATOMIC_RELAXED); - __atomic_sub_fetch(&ar->stats->mmap.allocated_bytes, page->size, __ATOMIC_RELAXED); - } - else { -#ifdef NETDATA_TRACE_ALLOCATIONS - freez_int(page->data TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS); -#else - freez(page->data); -#endif - __atomic_sub_fetch(&ar->stats->malloc.allocations, 1, __ATOMIC_RELAXED); - __atomic_sub_fetch(&ar->stats->malloc.allocated_bytes, page->size, __ATOMIC_RELAXED); - } - - freez(page); - - __atomic_sub_fetch(&ar->stats->structures.allocations, 1, __ATOMIC_RELAXED); - __atomic_sub_fetch(&ar->stats->structures.allocated_bytes, sizeof(ARAL_PAGE), __ATOMIC_RELAXED); -} - -static inline void aral_insert_not_linked_page_with_free_items_to_proper_position___aral_lock_needed(ARAL *ar, ARAL_PAGE *page) { - ARAL_PAGE *first = ar->aral_lock.pages; - - if (page->aral_lock.free_elements <= page->free_elements_to_move_first || - !first || - !first->aral_lock.free_elements || - page->aral_lock.free_elements <= first->aral_lock.free_elements + ARAL_FREE_PAGES_DELTA_TO_REARRANGE_LIST) { - // first position - DOUBLE_LINKED_LIST_PREPEND_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - } - else { - ARAL_PAGE *second = first->aral_lock.next; - - if (!second || - !second->aral_lock.free_elements || - page->aral_lock.free_elements <= second->aral_lock.free_elements) - // second position - DOUBLE_LINKED_LIST_INSERT_ITEM_AFTER_UNSAFE(ar->aral_lock.pages, first, page, aral_lock.prev, aral_lock.next); - else - // third position - DOUBLE_LINKED_LIST_INSERT_ITEM_AFTER_UNSAFE(ar->aral_lock.pages, second, page, aral_lock.prev, aral_lock.next); - } -} - -static inline ARAL_PAGE *aral_acquire_a_free_slot(ARAL *ar TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) { - __atomic_add_fetch(&ar->atomic.allocators, 1, __ATOMIC_RELAXED); - aral_lock(ar); - - ARAL_PAGE *page = ar->aral_lock.pages; - - while(!page || !page->aral_lock.free_elements) { -#ifdef NETDATA_ARAL_INTERNAL_CHECKS - internal_fatal(find_page_with_free_slots_internal_check___with_aral_lock(ar), "ARAL: '%s' found page with free slot!", ar->config.name); -#endif - aral_unlock(ar); - - if(aral_adders_trylock(ar)) { - if(ar->adders.allocating_elements < __atomic_load_n(&ar->atomic.allocators, __ATOMIC_RELAXED)) { - - size_t size = aral_next_allocation_size___adders_lock_needed(ar); - ar->adders.allocating_elements += size / ar->config.element_size; - aral_adders_unlock(ar); - - page = aral_create_page___no_lock_needed(ar, size TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS); - - aral_lock(ar); - aral_insert_not_linked_page_with_free_items_to_proper_position___aral_lock_needed(ar, page); - - aral_adders_lock(ar); - ar->adders.allocating_elements -= size / ar->config.element_size; - aral_adders_unlock(ar); - - // we have a page that is all empty - // and only aral_lock() is held, so - // break the loop - break; - } - - aral_adders_unlock(ar); - } - - aral_lock(ar); - page = ar->aral_lock.pages; - } - - __atomic_sub_fetch(&ar->atomic.allocators, 1, __ATOMIC_RELAXED); - - // we have a page - // and aral locked - - { - ARAL_PAGE *first = ar->aral_lock.pages; - ARAL_PAGE *second = first->aral_lock.next; - - if (!second || - !second->aral_lock.free_elements || - first->aral_lock.free_elements <= second->aral_lock.free_elements + ARAL_FREE_PAGES_DELTA_TO_REARRANGE_LIST) - page = first; - else { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, second, aral_lock.prev, aral_lock.next); - DOUBLE_LINKED_LIST_PREPEND_ITEM_UNSAFE(ar->aral_lock.pages, second, aral_lock.prev, aral_lock.next); - page = second; - } - } - - internal_fatal(!page || !page->aral_lock.free_elements, - "ARAL: '%s' selected page does not have a free slot in it", - ar->config.name); - - internal_fatal(page->max_elements != page->aral_lock.used_elements + page->aral_lock.free_elements, - "ARAL: '%s' page element counters do not match, " - "page says it can handle %zu elements, " - "but there are %zu used and %zu free items, " - "total %zu items", - ar->config.name, - (size_t)page->max_elements, - (size_t)page->aral_lock.used_elements, (size_t)page->aral_lock.free_elements, - (size_t)page->aral_lock.used_elements + (size_t)page->aral_lock.free_elements - ); - - ar->aral_lock.user_malloc_operations++; - - // acquire a slot for the caller - page->aral_lock.used_elements++; - if(--page->aral_lock.free_elements == 0) { - // we are done with this page - // move the full page last - // so that pages with free items remain first in the list - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - } - - aral_unlock(ar); - - return page; -} - -void *aral_mallocz_internal(ARAL *ar TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) { -#ifdef FSANITIZE_ADDRESS - return mallocz(ar->config.requested_element_size); -#endif - - ARAL_PAGE *page = aral_acquire_a_free_slot(ar TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS); - - aral_page_free_lock(ar, page); - - internal_fatal(!page->free.list, - "ARAL: '%s' free item to use, cannot be NULL.", ar->config.name); - - internal_fatal(page->free.list->size < ar->config.element_size, - "ARAL: '%s' free item size %zu, cannot be smaller than %zu", - ar->config.name, page->free.list->size, ar->config.element_size); - - ARAL_FREE *found_fr = page->free.list; - - // check if the remaining size (after we use this slot) is not enough for another element - if(unlikely(found_fr->size - ar->config.element_size < ar->config.element_size)) { - // we can use the entire free space entry - - page->free.list = found_fr->next; - } - else { - // we can split the free space entry - - uint8_t *data = (uint8_t *)found_fr; - ARAL_FREE *fr = (ARAL_FREE *)&data[ar->config.element_size]; - fr->size = found_fr->size - ar->config.element_size; - - // link the free slot first in the page - fr->next = found_fr->next; - page->free.list = fr; - - aral_free_validate_internal_check(ar, fr); - } - - aral_page_free_unlock(ar, page); - - // put the page pointer after the element - uint8_t *data = (uint8_t *)found_fr; - ARAL_PAGE **page_ptr = (ARAL_PAGE **)&data[ar->config.page_ptr_offset]; - *page_ptr = page; - - if(unlikely(ar->config.mmap.enabled)) - __atomic_add_fetch(&ar->stats->mmap.used_bytes, ar->config.element_size, __ATOMIC_RELAXED); - else - __atomic_add_fetch(&ar->stats->malloc.used_bytes, ar->config.element_size, __ATOMIC_RELAXED); - - return (void *)found_fr; -} - -static inline ARAL_PAGE *aral_ptr_to_page___must_NOT_have_aral_lock(ARAL *ar, void *ptr) { - // given a data pointer we returned before, - // find the ARAL_PAGE it belongs to - - uint8_t *data = (uint8_t *)ptr; - ARAL_PAGE **page_ptr = (ARAL_PAGE **)&data[ar->config.page_ptr_offset]; - ARAL_PAGE *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_ARAL_INTERNAL_CHECKS - { - // find the page ptr belongs - ARAL_PAGE *page2 = find_page_with_allocation_internal_check(ar, ptr); - - internal_fatal(page != page2, - "ARAL: '%s' page pointers do not match!", - ar->name); - - internal_fatal(!page2, - "ARAL: '%s' free of pointer %p is not in ARAL address space.", - ar->name, ptr); - } -#endif - - internal_fatal(!page, - "ARAL: '%s' possible corruption or double free of pointer %p", - ar->config.name, ptr); - - return page; -} - -static void aral_defrag_sorted_page_position___aral_lock_needed(ARAL *ar, ARAL_PAGE *page) { - ARAL_PAGE *tmp; - - int action = 0; (void)action; - size_t move_later = 0, move_earlier = 0; - - for(tmp = page->aral_lock.next ; - tmp && tmp->aral_lock.free_elements && tmp->aral_lock.free_elements < page->aral_lock.free_elements ; - tmp = tmp->aral_lock.next) - move_later++; - - if(!tmp && page->aral_lock.next) { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - action = 1; - } - else if(tmp != page->aral_lock.next) { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - DOUBLE_LINKED_LIST_INSERT_ITEM_BEFORE_UNSAFE(ar->aral_lock.pages, tmp, page, aral_lock.prev, aral_lock.next); - action = 2; - } - else { - for(tmp = (page == ar->aral_lock.pages) ? NULL : page->aral_lock.prev ; - tmp && (!tmp->aral_lock.free_elements || tmp->aral_lock.free_elements > page->aral_lock.free_elements); - tmp = (tmp == ar->aral_lock.pages) ? NULL : tmp->aral_lock.prev) - move_earlier++; - - if(!tmp) { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - DOUBLE_LINKED_LIST_PREPEND_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - action = 3; - } - else if(tmp != page->aral_lock.prev){ - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - DOUBLE_LINKED_LIST_INSERT_ITEM_AFTER_UNSAFE(ar->aral_lock.pages, tmp, page, aral_lock.prev, aral_lock.next); - action = 4; - } - } - - ar->aral_lock.defragment_operations++; - ar->aral_lock.defragment_linked_list_traversals += move_earlier + move_later; - - internal_fatal(page->aral_lock.next && page->aral_lock.next->aral_lock.free_elements && page->aral_lock.next->aral_lock.free_elements < page->aral_lock.free_elements, - "ARAL: '%s' item should be later in the list", ar->config.name); - - internal_fatal(page != ar->aral_lock.pages && (!page->aral_lock.prev->aral_lock.free_elements || page->aral_lock.prev->aral_lock.free_elements > page->aral_lock.free_elements), - "ARAL: '%s' item should be earlier in the list", ar->config.name); -} - -static inline void aral_move_page_with_free_list___aral_lock_needed(ARAL *ar, ARAL_PAGE *page) { - if(unlikely(page == ar->aral_lock.pages)) - // we are the first already - return; - - if(likely(!(ar->config.options & ARAL_DEFRAGMENT))) { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - aral_insert_not_linked_page_with_free_items_to_proper_position___aral_lock_needed(ar, page); - } - else - aral_defrag_sorted_page_position___aral_lock_needed(ar, page); -} - -void aral_freez_internal(ARAL *ar, void *ptr TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) { -#ifdef FSANITIZE_ADDRESS - freez(ptr); - return; -#endif - - if(unlikely(!ptr)) return; - - // get the page pointer - ARAL_PAGE *page = aral_ptr_to_page___must_NOT_have_aral_lock(ar, ptr); - - if(unlikely(ar->config.mmap.enabled)) - __atomic_sub_fetch(&ar->stats->mmap.used_bytes, ar->config.element_size, __ATOMIC_RELAXED); - else - __atomic_sub_fetch(&ar->stats->malloc.used_bytes, ar->config.element_size, __ATOMIC_RELAXED); - - // make this element available - ARAL_FREE *fr = (ARAL_FREE *)ptr; - fr->size = ar->config.element_size; - - aral_page_free_lock(ar, page); - fr->next = page->free.list; - page->free.list = fr; - aral_page_free_unlock(ar, page); - - aral_lock(ar); - - internal_fatal(!page->aral_lock.used_elements, - "ARAL: '%s' pointer %p is inside a page without any active allocations.", - ar->config.name, ptr); - - internal_fatal(page->max_elements != page->aral_lock.used_elements + page->aral_lock.free_elements, - "ARAL: '%s' page element counters do not match, " - "page says it can handle %zu elements, " - "but there are %zu used and %zu free items, " - "total %zu items", - ar->config.name, - (size_t)page->max_elements, - (size_t)page->aral_lock.used_elements, (size_t)page->aral_lock.free_elements, - (size_t)page->aral_lock.used_elements + (size_t)page->aral_lock.free_elements - ); - - page->aral_lock.used_elements--; - page->aral_lock.free_elements++; - - ar->aral_lock.user_free_operations++; - - // if the page is empty, release it - if(unlikely(!page->aral_lock.used_elements)) { - bool is_this_page_the_last_one = ar->aral_lock.pages == page && !page->aral_lock.next; - - if(!is_this_page_the_last_one) - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - - aral_unlock(ar); - - if(!is_this_page_the_last_one) - aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS); - } - else { - aral_move_page_with_free_list___aral_lock_needed(ar, page); - aral_unlock(ar); - } -} - -void aral_destroy_internal(ARAL *ar TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) { - aral_lock(ar); - - ARAL_PAGE *page; - while((page = ar->aral_lock.pages)) { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(ar->aral_lock.pages, page, aral_lock.prev, aral_lock.next); - aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS); - } - - aral_unlock(ar); - - if(ar->config.options & ARAL_ALLOCATED_STATS) - freez(ar->stats); - - freez(ar); -} - -size_t aral_element_size(ARAL *ar) { - return ar->config.requested_element_size; -} - -ARAL *aral_create(const char *name, size_t element_size, size_t initial_page_elements, size_t max_page_size, - struct aral_statistics *stats, const char *filename, char **cache_dir, bool mmap, bool lockless) { - ARAL *ar = callocz(1, sizeof(ARAL)); - ar->config.options = (lockless) ? ARAL_LOCKLESS : 0; - ar->config.requested_element_size = element_size; - ar->config.initial_page_elements = initial_page_elements; - ar->config.requested_max_page_size = max_page_size; - ar->config.mmap.filename = filename; - ar->config.mmap.cache_dir = cache_dir; - ar->config.mmap.enabled = mmap; - strncpyz(ar->config.name, name, ARAL_MAX_NAME); - spinlock_init(&ar->aral_lock.spinlock); - - if(stats) { - ar->stats = stats; - ar->config.options &= ~ARAL_ALLOCATED_STATS; - } - else { - ar->stats = callocz(1, sizeof(struct aral_statistics)); - ar->config.options |= ARAL_ALLOCATED_STATS; - } - - long int page_size = sysconf(_SC_PAGE_SIZE); - if (unlikely(page_size == -1)) - ar->config.natural_page_size = 4096; - else - ar->config.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->config.element_size = natural_alignment(ar->config.requested_element_size, sizeof(uintptr_t)); - - // then add the size of a pointer to it - ar->config.element_size += sizeof(uintptr_t); - - // make sure it is at least what we need for an ARAL_FREE slot - if (ar->config.element_size < sizeof(ARAL_FREE)) - ar->config.element_size = sizeof(ARAL_FREE); - - // and finally align it to the natural alignment - ar->config.element_size = natural_alignment(ar->config.element_size, ARAL_NATURAL_ALIGNMENT); - - ar->config.max_page_elements = ar->config.requested_max_page_size / ar->config.element_size; - - // we write the page pointer just after each element - ar->config.page_ptr_offset = ar->config.element_size - sizeof(uintptr_t); - - if(ar->config.requested_element_size + sizeof(uintptr_t) > ar->config.element_size) - fatal("ARAL: '%s' 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->config.name, ar->config.requested_element_size, sizeof(uintptr_t), ARAL_NATURAL_ALIGNMENT, - ar->config.element_size, ar->config.page_ptr_offset); - - //netdata_log_info("ARAL: 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->config.initial_page_elements < 2) - ar->config.initial_page_elements = 2; - - if(ar->config.mmap.enabled && (!ar->config.mmap.cache_dir || !*ar->config.mmap.cache_dir)) { - netdata_log_error("ARAL: '%s' mmap cache directory is not configured properly, disabling mmap.", ar->config.name); - ar->config.mmap.enabled = false; - internal_fatal(true, "ARAL: '%s' mmap cache directory is not configured properly", ar->config.name); - } - - uint64_t max_alloc_size; - if(!ar->config.max_page_elements) - max_alloc_size = ar->config.mmap.enabled ? ARAL_MAX_PAGE_SIZE_MMAP : ARAL_MAX_PAGE_SIZE_MALLOC; - else - max_alloc_size = ar->config.max_page_elements * ar->config.element_size; - - ar->config.max_allocation_size = aral_align_alloc_size(ar, max_alloc_size); - ar->adders.allocation_size = aral_align_alloc_size(ar, (uint64_t)ar->config.element_size * ar->config.initial_page_elements); - ar->aral_lock.pages = NULL; - ar->aral_lock.file_number = 0; - - if(ar->config.mmap.enabled) { - char directory_name[FILENAME_MAX + 1]; - snprintfz(directory_name, FILENAME_MAX, "%s/array_alloc.mmap", *ar->config.mmap.cache_dir); - int r = mkdir(directory_name, 0775); - if (r != 0 && errno != EEXIST) - fatal("Cannot create directory '%s'", directory_name); - - char file[FILENAME_MAX + 1]; - snprintfz(file, FILENAME_MAX, "%s.", ar->config.mmap.filename); - aral_delete_leftover_files(ar->config.name, directory_name, file); - } - - internal_error(true, - "ARAL: '%s' " - "element size %zu (requested %zu bytes), " - "min elements per page %zu (requested %zu), " - "max elements per page %zu, " - "max page size %zu bytes (requested %zu) " - , ar->config.name - , ar->config.element_size, ar->config.requested_element_size - , ar->adders.allocation_size / ar->config.element_size, ar->config.initial_page_elements - , ar->config.max_allocation_size / ar->config.element_size - , ar->config.max_allocation_size, ar->config.requested_max_page_size - ); - - __atomic_add_fetch(&ar->stats->structures.allocations, 1, __ATOMIC_RELAXED); - __atomic_add_fetch(&ar->stats->structures.allocated_bytes, sizeof(ARAL), __ATOMIC_RELAXED); - return ar; -} - -// ---------------------------------------------------------------------------- -// global aral caching - -#define ARAL_BY_SIZE_MAX_SIZE 1024 - -struct aral_by_size { - ARAL *ar; - int32_t refcount; -}; - -struct { - struct aral_statistics shared_statistics; - SPINLOCK spinlock; - struct aral_by_size array[ARAL_BY_SIZE_MAX_SIZE + 1]; -} aral_by_size_globals = {}; - -struct aral_statistics *aral_by_size_statistics(void) { - return &aral_by_size_globals.shared_statistics; -} - -size_t aral_by_size_structures(void) { - return aral_structures_from_stats(&aral_by_size_globals.shared_statistics); -} - -size_t aral_by_size_overhead(void) { - return aral_overhead_from_stats(&aral_by_size_globals.shared_statistics); -} - -ARAL *aral_by_size_acquire(size_t size) { - spinlock_lock(&aral_by_size_globals.spinlock); - - ARAL *ar = NULL; - - if(size <= ARAL_BY_SIZE_MAX_SIZE && aral_by_size_globals.array[size].ar) { - ar = aral_by_size_globals.array[size].ar; - aral_by_size_globals.array[size].refcount++; - - internal_fatal(aral_element_size(ar) != size, "DICTIONARY: aral has size %zu but we want %zu", - aral_element_size(ar), size); - } - - if(!ar) { - char buf[30 + 1]; - snprintf(buf, 30, "size-%zu", size); - ar = aral_create(buf, - size, - 0, - 65536 * ((size / 150) + 1), - &aral_by_size_globals.shared_statistics, - NULL, NULL, false, false); - - if(size <= ARAL_BY_SIZE_MAX_SIZE) { - aral_by_size_globals.array[size].ar = ar; - aral_by_size_globals.array[size].refcount = 1; - } - } - - spinlock_unlock(&aral_by_size_globals.spinlock); - - return ar; -} - -void aral_by_size_release(ARAL *ar) { - size_t size = aral_element_size(ar); - - if(size <= ARAL_BY_SIZE_MAX_SIZE) { - spinlock_lock(&aral_by_size_globals.spinlock); - - internal_fatal(aral_by_size_globals.array[size].ar != ar, - "ARAL BY SIZE: aral pointers do not match"); - - if(aral_by_size_globals.array[size].refcount <= 0) - fatal("ARAL BY SIZE: double release detected"); - - aral_by_size_globals.array[size].refcount--; -// if(!aral_by_size_globals.array[size].refcount) { -// aral_destroy(aral_by_size_globals.array[size].ar); -// aral_by_size_globals.array[size].ar = NULL; -// } - - spinlock_unlock(&aral_by_size_globals.spinlock); - } - else - aral_destroy(ar); -} - -// ---------------------------------------------------------------------------- -// unittest - -struct aral_unittest_config { - bool single_threaded; - bool stop; - ARAL *ar; - size_t elements; - size_t threads; - int errors; -}; - -static void *aral_test_thread(void *ptr) { - struct aral_unittest_config *auc = ptr; - ARAL *ar = auc->ar; - size_t elements = auc->elements; - - void **pointers = callocz(elements, sizeof(void *)); - - do { - for (size_t i = 0; i < elements; i++) { - pointers[i] = aral_mallocz(ar); - } - - for (size_t div = 5; div >= 2; div--) { - for (size_t i = 0; i < elements / div; i++) { - aral_freez(ar, pointers[i]); - pointers[i] = NULL; - } - - for (size_t i = 0; i < elements / div; i++) { - pointers[i] = aral_mallocz(ar); - } - } - - for (size_t step = 50; step >= 10; step -= 10) { - for (size_t i = 0; i < elements; i += step) { - aral_freez(ar, pointers[i]); - pointers[i] = NULL; - } - - for (size_t i = 0; i < elements; i += step) { - pointers[i] = aral_mallocz(ar); - } - } - - for (size_t i = 0; i < elements; i++) { - aral_freez(ar, pointers[i]); - pointers[i] = NULL; - } - - if (auc->single_threaded && ar->aral_lock.pages && ar->aral_lock.pages->aral_lock.used_elements) { - fprintf(stderr, "\n\nARAL leftovers detected (1)\n\n"); - __atomic_add_fetch(&auc->errors, 1, __ATOMIC_RELAXED); - } - - if(!auc->single_threaded && __atomic_load_n(&auc->stop, __ATOMIC_RELAXED)) - break; - - for (size_t i = 0; i < elements; i++) { - pointers[i] = aral_mallocz(ar); - } - - size_t increment = elements / ar->config.max_page_elements; - for (size_t all = increment; all <= elements / 2; all += increment) { - - size_t to_free = (all % ar->config.max_page_elements) + 1; - size_t step = elements / to_free; - if(!step) step = 1; - - // fprintf(stderr, "all %zu, to free %zu, step %zu\n", all, to_free, step); - - size_t free_list[to_free]; - for (size_t i = 0; i < to_free; i++) { - size_t pos = step * i; - aral_freez(ar, pointers[pos]); - pointers[pos] = NULL; - free_list[i] = pos; - } - - for (size_t i = 0; i < to_free; i++) { - size_t pos = free_list[i]; - pointers[pos] = aral_mallocz(ar); - } - } - - for (size_t i = 0; i < elements; i++) { - aral_freez(ar, pointers[i]); - pointers[i] = NULL; - } - - if (auc->single_threaded && ar->aral_lock.pages && ar->aral_lock.pages->aral_lock.used_elements) { - fprintf(stderr, "\n\nARAL leftovers detected (2)\n\n"); - __atomic_add_fetch(&auc->errors, 1, __ATOMIC_RELAXED); - } - - } while(!auc->single_threaded && !__atomic_load_n(&auc->stop, __ATOMIC_RELAXED)); - - freez(pointers); - - return ptr; -} - -int aral_stress_test(size_t threads, size_t elements, size_t seconds) { - fprintf(stderr, "Running stress test of %zu threads, with %zu elements each, for %zu seconds...\n", - threads, elements, seconds); - - struct aral_unittest_config auc = { - .single_threaded = false, - .threads = threads, - .ar = aral_create("aral-stress-test", 20, 0, 8192, NULL, "aral-stress-test", NULL, false, false), - .elements = elements, - .errors = 0, - }; - - usec_t started_ut = now_monotonic_usec(); - netdata_thread_t thread_ptrs[threads]; - - for(size_t i = 0; i < threads ; i++) { - char tag[NETDATA_THREAD_NAME_MAX + 1]; - snprintfz(tag, NETDATA_THREAD_NAME_MAX, "TH[%zu]", i); - netdata_thread_create(&thread_ptrs[i], tag, - NETDATA_THREAD_OPTION_JOINABLE | NETDATA_THREAD_OPTION_DONT_LOG, - aral_test_thread, &auc); - } - - size_t malloc_done = 0; - size_t free_done = 0; - size_t countdown = seconds; - while(countdown-- > 0) { - sleep_usec(1 * USEC_PER_SEC); - aral_lock(auc.ar); - size_t m = auc.ar->aral_lock.user_malloc_operations; - size_t f = auc.ar->aral_lock.user_free_operations; - aral_unlock(auc.ar); - fprintf(stderr, "ARAL executes %0.2f M malloc and %0.2f M free operations/s\n", - (double)(m - malloc_done) / 1000000.0, (double)(f - free_done) / 1000000.0); - malloc_done = m; - free_done = f; - } - - __atomic_store_n(&auc.stop, true, __ATOMIC_RELAXED); - -// fprintf(stderr, "Cancelling the threads...\n"); -// for(size_t i = 0; i < threads ; i++) { -// netdata_thread_cancel(thread_ptrs[i]); -// } - - fprintf(stderr, "Waiting the threads to finish...\n"); - for(size_t i = 0; i < threads ; i++) { - netdata_thread_join(thread_ptrs[i], NULL); - } - - usec_t ended_ut = now_monotonic_usec(); - - if (auc.ar->aral_lock.pages && auc.ar->aral_lock.pages->aral_lock.used_elements) { - fprintf(stderr, "\n\nARAL leftovers detected (3)\n\n"); - __atomic_add_fetch(&auc.errors, 1, __ATOMIC_RELAXED); - } - - netdata_log_info("ARAL: did %zu malloc, %zu free, " - "using %zu threads, in %"PRIu64" usecs", - auc.ar->aral_lock.user_malloc_operations, - auc.ar->aral_lock.user_free_operations, - threads, - ended_ut - started_ut); - - aral_destroy(auc.ar); - - return auc.errors; -} - -int aral_unittest(size_t elements) { - char *cache_dir = "/tmp/"; - - struct aral_unittest_config auc = { - .single_threaded = true, - .threads = 1, - .ar = aral_create("aral-test", 20, 0, 8192, NULL, "aral-test", &cache_dir, false, false), - .elements = elements, - .errors = 0, - }; - - aral_test_thread(&auc); - - aral_destroy(auc.ar); - - int errors = aral_stress_test(2, elements, 5); - - return auc.errors + errors; -} |