1 files changed, 335 insertions, 0 deletions

diff --git a/libnetdata/arrayalloc/arrayalloc.c b/libnetdata/arrayalloc/arrayalloc.c
new file mode 100644
index 000000000..bdf1384d4
--- /dev/null
+++ b/libnetdata/arrayalloc/arrayalloc.c
@@ -0,0 +1,335 @@
+#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 += 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->internal.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) {
+    uintptr_t seeking = (uintptr_t)ptr;
+    ARAL_PAGE *page;
+
+    for(page = ar->internal.first_page; page ; page = page->next) {
+        if(unlikely(seeking >= (uintptr_t)page->data && seeking < (uintptr_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);
+            if (unlikely(unlink(page->filename) == 1))
+                error("Cannot delete file '%s'", 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);
+}