Merging upstream version 1.38.0.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 515 insertions, 0 deletions

diff --git a/libnetdata/july/Makefile.am b/libnetdata/july/Makefile.am
new file mode 100644
index 000000000..161784b8f
--- /dev/null
+++ b/libnetdata/july/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/july/README.md b/libnetdata/july/README.md
new file mode 100644
index 000000000..df2a3d38c
--- /dev/null
+++ b/libnetdata/july/README.md
@@ -0,0 +1,14 @@
+<!--
+custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/july/README.md
+sidebar_label: "July interface"
+learn_status: "Published"
+learn_topic_type: "Tasks"
+learn_rel_path: "Developers/libnetdata libraries"
+-->
+
+
+# July
+
+An interface similar to `Judy` that uses minimal allocations (that can be cached)
+for items that are mainly appended (just a few insertions in the middle)
+
diff --git a/libnetdata/july/july.c b/libnetdata/july/july.c
new file mode 100644
index 000000000..0ad5f13e5
--- /dev/null
+++ b/libnetdata/july/july.c
@@ -0,0 +1,453 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "july.h"
+
+#define JULYL_MIN_ENTRIES 10
+
+struct JulyL_item {
+    Word_t index;
+    void *value;
+};
+
+struct JulyL {
+    size_t entries;
+    size_t used;
+
+    // statistics
+    size_t bytes;
+    size_t bytes_moved;
+    size_t reallocs;
+
+    struct {
+        struct JulyL *prev;
+        struct JulyL *next;
+    } cache;
+
+    struct JulyL_item array[];
+};
+
+// ----------------------------------------------------------------------------
+// JulyL cache
+
+static struct {
+    struct {
+        SPINLOCK spinlock;
+        struct JulyL *available_items;
+        size_t available;
+    } protected;
+
+    struct {
+        size_t bytes;
+        size_t allocated;
+        size_t bytes_moved;
+        size_t reallocs;
+    } atomics;
+} julyl_globals = {
+        .protected = {
+                .spinlock = NETDATA_SPINLOCK_INITIALIZER,
+                .available_items = NULL,
+                .available = 0,
+        },
+        .atomics = {
+                .bytes = 0,
+                .allocated = 0,
+                .bytes_moved = 0,
+                .reallocs = 0,
+        },
+};
+
+void julyl_cleanup1(void) {
+    struct JulyL *item = NULL;
+
+    if(!netdata_spinlock_trylock(&julyl_globals.protected.spinlock))
+        return;
+
+    if(julyl_globals.protected.available_items && julyl_globals.protected.available > 10) {
+        item = julyl_globals.protected.available_items;
+        DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(julyl_globals.protected.available_items, item, cache.prev, cache.next);
+        julyl_globals.protected.available--;
+    }
+
+    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
+
+    if(item) {
+        size_t bytes = item->bytes;
+        freez(item);
+        __atomic_sub_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED);
+        __atomic_sub_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED);
+    }
+}
+
+struct JulyL *julyl_get(void) {
+    struct JulyL *j;
+
+    netdata_spinlock_lock(&julyl_globals.protected.spinlock);
+
+    j = julyl_globals.protected.available_items;
+    if(likely(j)) {
+        DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next);
+        julyl_globals.protected.available--;
+    }
+
+    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
+
+    if(unlikely(!j)) {
+        size_t bytes = sizeof(struct JulyL) + JULYL_MIN_ENTRIES * sizeof(struct JulyL_item);
+        j = mallocz(bytes);
+        j->bytes = bytes;
+        j->entries = JULYL_MIN_ENTRIES;
+        __atomic_add_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED);
+        __atomic_add_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED);
+    }
+
+    j->used = 0;
+    j->bytes_moved = 0;
+    j->reallocs = 0;
+    j->cache.next = j->cache.prev = NULL;
+    return j;
+}
+
+static void julyl_release(struct JulyL *j) {
+    if(unlikely(!j)) return;
+
+    __atomic_add_fetch(&julyl_globals.atomics.bytes_moved, j->bytes_moved, __ATOMIC_RELAXED);
+    __atomic_add_fetch(&julyl_globals.atomics.reallocs, j->reallocs, __ATOMIC_RELAXED);
+
+    netdata_spinlock_lock(&julyl_globals.protected.spinlock);
+    DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next);
+    julyl_globals.protected.available++;
+    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
+}
+
+size_t julyl_cache_size(void) {
+    return __atomic_load_n(&julyl_globals.atomics.bytes, __ATOMIC_RELAXED);
+}
+
+size_t julyl_bytes_moved(void) {
+    return __atomic_load_n(&julyl_globals.atomics.bytes_moved, __ATOMIC_RELAXED);
+}
+
+// ----------------------------------------------------------------------------
+// JulyL
+
+size_t JulyLGet_binary_search_position_of_index(const struct JulyL *July, Word_t Index) {
+    // return the position of the first item >= Index
+
+    size_t left = 0;
+    size_t right = July->used;
+    while(left < right) {
+        size_t middle = (left + right) >> 1;
+
+        if(July->array[middle].index > Index)
+            right = middle;
+
+        else
+            left = middle + 1;
+    }
+
+    internal_fatal(left > July->used, "JULY: invalid position returned");
+
+    if(left > 0 && July->array[left - 1].index == Index)
+        return left - 1;
+
+    internal_fatal( (left < July->used && July->array[left].index < Index) ||
+                    (left > 0 && July->array[left - 1].index >= Index)
+                   , "JULY: wrong item returned");
+
+    return left;
+}
+
+PPvoid_t JulyLGet(Pcvoid_t PArray, Word_t Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, Index);
+
+    if(unlikely(pos >= July->used || July->array[pos].index != Index))
+        return NULL;
+
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLIns(PPvoid_t PPArray, Word_t Index, PJError_t PJError __maybe_unused) {
+    struct JulyL *July = *PPArray;
+    if(unlikely(!July)) {
+        July = julyl_get();
+        July->used = 0;
+        *PPArray = July;
+    }
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, Index);
+
+    if((pos == July->used || July->array[pos].index != Index)) {
+        // we have to add this entry
+
+        if (unlikely(July->used == July->entries)) {
+            // we have to expand the array
+            size_t bytes = sizeof(struct JulyL) + July->entries * 2 * sizeof(struct JulyL_item);
+            __atomic_add_fetch(&julyl_globals.atomics.bytes, bytes - July->bytes, __ATOMIC_RELAXED);
+            July = reallocz(July, bytes);
+            July->bytes = bytes;
+            July->entries *= 2;
+            July->reallocs++;
+            *PPArray = July;
+        }
+
+        if (unlikely(pos != July->used)) {
+            // we have to shift some members to make room
+            size_t size = (July->used - pos) * sizeof(struct JulyL_item);
+            memmove(&July->array[pos + 1], &July->array[pos], size);
+            July->bytes_moved += size;
+        }
+
+        July->used++;
+        July->array[pos].value = NULL;
+        July->array[pos].index = Index;
+    }
+
+    return &July->array[pos].value;
+}
+
+PPvoid_t JulyLFirst(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(unlikely(pos == July->used))
+        return NULL;
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLNext(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(unlikely(pos == July->used))
+        return NULL;
+
+    if(July->array[pos].index == *Index) {
+        pos++;
+
+        if(unlikely(pos == July->used))
+            return NULL;
+    }
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLLast(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(pos > 0 && (pos == July->used || July->array[pos].index > *Index))
+        pos--;
+
+    if(unlikely(pos == 0 && July->array[0].index > *Index))
+        return NULL;
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+PPvoid_t JulyLPrev(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) {
+    const struct JulyL *July = PArray;
+    if(!July)
+        return NULL;
+
+    size_t pos = JulyLGet_binary_search_position_of_index(July, *Index);
+    // pos is >= Index
+
+    if(unlikely(pos == 0 || July->used == 0))
+        return NULL;
+
+    // get the previous one
+    pos--;
+
+    *Index = July->array[pos].index;
+    return (PPvoid_t)&July->array[pos].value;
+}
+
+Word_t JulyLFreeArray(PPvoid_t PPArray, PJError_t PJError __maybe_unused) {
+    struct JulyL *July = *PPArray;
+    if(unlikely(!July))
+        return 0;
+
+    size_t bytes = July->bytes;
+    julyl_release(July);
+    *PPArray = NULL;
+    return bytes;
+}
+
+// ----------------------------------------------------------------------------
+// unittest
+
+#define item_index(i) (((i) * 2) + 100)
+
+int julytest(void) {
+    Word_t entries = 10000;
+    Pvoid_t array = NULL;
+
+    // test additions
+    for(Word_t i = 0; i < entries ;i++) {
+        Pvoid_t *PValue = JulyLIns(&array, item_index(i), PJE0);
+        if(!PValue)
+            fatal("JULY: cannot insert item %lu", item_index(i));
+
+        *PValue = (void *)(item_index(i));
+    }
+
+    // test successful finds
+    for(Word_t i = 0; i < entries ;i++) {
+        Pvoid_t *PValue = JulyLGet(array, item_index(i), PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+    }
+
+    // test finding the first item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLFirst(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find first item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    // test finding the next item
+    for(Word_t i = 0; i < entries - 1 ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLNext(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find next item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i + 1)))
+            fatal("JULY: item %lu next has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i + 1))
+            fatal("JULY: item %lu next has index %lu", item_index(i), index);
+    }
+
+    // test finding the last item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLLast(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find last item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    // test finding the prev item
+    for(Word_t i = 1; i < entries ;i++) {
+        Word_t index = item_index(i);
+        Pvoid_t *PValue = JulyLPrev(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find prev item %lu", item_index(i));
+
+        if(*PValue != (void *)(item_index(i - 1)))
+            fatal("JULY: item %lu prev has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i - 1))
+            fatal("JULY: item %lu prev has index %lu", item_index(i), index);
+    }
+
+    // test full traversal forward
+    {
+        Word_t i = 0;
+        Word_t index = 0;
+        bool first = true;
+        Pvoid_t *PValue;
+        while((PValue = JulyLFirstThenNext(array, &index, &first))) {
+            if(*PValue != (void *)(item_index(i)))
+                fatal("JULY: item %lu traversal has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+            if(index != item_index(i))
+                fatal("JULY: item %lu traversal has index %lu", item_index(i), index);
+
+            i++;
+        }
+
+        if(i != entries)
+            fatal("JULY: expected to forward traverse %lu entries, but traversed %lu", entries, i);
+    }
+
+    // test full traversal backward
+    {
+        Word_t i = 0;
+        Word_t index = (Word_t)(-1);
+        bool first = true;
+        Pvoid_t *PValue;
+        while((PValue = JulyLLastThenPrev(array, &index, &first))) {
+            if(*PValue != (void *)(item_index(entries - i - 1)))
+                fatal("JULY: item %lu traversal has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+            if(index != item_index(entries - i - 1))
+                fatal("JULY: item %lu traversal has index %lu", item_index(i), index);
+
+            i++;
+        }
+
+        if(i != entries)
+            fatal("JULY: expected to back traverse %lu entries, but traversed %lu", entries, i);
+    }
+
+    // test finding non-existing first item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i) - 1;
+        Pvoid_t *PValue = JulyLFirst(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find first item %lu", item_index(i) - 1);
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    // test finding non-existing last item
+    for(Word_t i = 0; i < entries ;i++) {
+        Word_t index = item_index(i) + 1;
+        Pvoid_t *PValue = JulyLLast(array, &index, PJE0);
+        if(!PValue)
+            fatal("JULY: cannot find last item %lu", item_index(i) + 1);
+
+        if(*PValue != (void *)(item_index(i)))
+            fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue));
+
+        if(index != item_index(i))
+            fatal("JULY: item %lu has index %lu", item_index(i), index);
+    }
+
+    JulyLFreeArray(&array, PJE0);
+
+    return 0;
+}
+
+
diff --git a/libnetdata/july/july.h b/libnetdata/july/july.h
new file mode 100644
index 000000000..672ed44e4
--- /dev/null
+++ b/libnetdata/july/july.h
@@ -0,0 +1,40 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef NETDATA_JULY_H
+#define NETDATA_JULY_H 1
+
+#include "../libnetdata.h"
+
+// #define PDC_USE_JULYL 1
+
+PPvoid_t JulyLGet(Pcvoid_t PArray, Word_t Index, PJError_t PJError);
+PPvoid_t JulyLIns(PPvoid_t PPArray, Word_t Index, PJError_t PJError);
+PPvoid_t JulyLFirst(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLNext(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLLast(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLPrev(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+Word_t JulyLFreeArray(PPvoid_t PPArray, PJError_t PJError);
+
+static inline PPvoid_t JulyLFirstThenNext(Pcvoid_t PArray, Word_t * PIndex, bool *first) {
+    if(unlikely(*first)) {
+        *first = false;
+        return JulyLFirst(PArray, PIndex, PJE0);
+    }
+
+    return JulyLNext(PArray, PIndex, PJE0);
+}
+
+static inline PPvoid_t JulyLLastThenPrev(Pcvoid_t PArray, Word_t * PIndex, bool *first) {
+    if(unlikely(*first)) {
+        *first = false;
+        return JulyLLast(PArray, PIndex, PJE0);
+    }
+
+    return JulyLPrev(PArray, PIndex, PJE0);
+}
+
+void julyl_cleanup1(void);
+size_t julyl_cache_size(void);
+size_t julyl_bytes_moved(void);
+
+#endif // NETDATA_JULY_H