Merging upstream version 1.46.3.

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

1 files changed, 259 insertions, 0 deletions

diff --git a/src/libnetdata/dictionary/dictionary-internals.h b/src/libnetdata/dictionary/dictionary-internals.h
new file mode 100644
index 000000000..54e59564f
--- /dev/null
+++ b/src/libnetdata/dictionary/dictionary-internals.h
@@ -0,0 +1,259 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef NETDATA_DICTIONARY_INTERNALS_H
+#define NETDATA_DICTIONARY_INTERNALS_H
+
+#define DICTIONARY_INTERNALS
+#include "../libnetdata.h"
+
+// runtime flags of the dictionary - must be checked with atomics
+typedef enum __attribute__ ((__packed__)) {
+    DICT_FLAG_NONE                  = 0,
+    DICT_FLAG_DESTROYED             = (1 << 0), // this dictionary has been destroyed
+} DICT_FLAGS;
+
+#define dict_flag_check(dict, flag) (__atomic_load_n(&((dict)->flags), __ATOMIC_RELAXED) & (flag))
+#define dict_flag_set(dict, flag)   __atomic_or_fetch(&((dict)->flags), flag, __ATOMIC_RELAXED)
+#define dict_flag_clear(dict, flag) __atomic_and_fetch(&((dict)->flags), ~(flag), __ATOMIC_RELAXED)
+
+// flags macros
+#define is_dictionary_destroyed(dict) dict_flag_check(dict, DICT_FLAG_DESTROYED)
+
+// configuration options macros
+#define is_dictionary_single_threaded(dict) ((dict)->options & DICT_OPTION_SINGLE_THREADED)
+#define is_view_dictionary(dict) ((dict)->master)
+#define is_master_dictionary(dict) (!is_view_dictionary(dict))
+
+typedef enum __attribute__ ((__packed__)) item_options {
+    ITEM_OPTION_NONE            = 0,
+    ITEM_OPTION_ALLOCATED_NAME  = (1 << 0), // the name pointer is a STRING
+
+    // IMPORTANT: This is 1-bit - to add more change ITEM_OPTIONS_BITS
+} ITEM_OPTIONS;
+
+typedef enum __attribute__ ((__packed__)) item_flags {
+    ITEM_FLAG_NONE              = 0,
+    ITEM_FLAG_DELETED           = (1 << 0), // this item is marked deleted, so it is not available for traversal (deleted from the index too)
+    ITEM_FLAG_BEING_CREATED     = (1 << 1), // this item is currently being created - this flag is removed when construction finishes
+
+    // IMPORTANT: This is 8-bit
+} ITEM_FLAGS;
+
+#define item_flag_check(item, flag) (__atomic_load_n(&((item)->flags), __ATOMIC_RELAXED) & (flag))
+#define item_flag_set(item, flag)   __atomic_or_fetch(&((item)->flags), flag, __ATOMIC_RELAXED)
+#define item_flag_clear(item, flag) __atomic_and_fetch(&((item)->flags), ~(flag), __ATOMIC_RELAXED)
+
+#define item_shared_flag_check(item, flag) (__atomic_load_n(&((item)->shared->flags), __ATOMIC_RELAXED) & (flag))
+#define item_shared_flag_set(item, flag)   __atomic_or_fetch(&((item)->shared->flags), flag, __ATOMIC_RELAXED)
+#define item_shared_flag_clear(item, flag) __atomic_and_fetch(&((item)->shared->flags), ~(flag), __ATOMIC_RELAXED)
+
+#define REFCOUNT_DELETING         (-100)
+
+#define ITEM_FLAGS_TYPE uint8_t
+#define KEY_LEN_TYPE    uint32_t
+#define VALUE_LEN_TYPE  uint32_t
+
+#define ITEM_OPTIONS_BITS 1
+#define KEY_LEN_BITS ((sizeof(KEY_LEN_TYPE) * 8) - (sizeof(ITEM_FLAGS_TYPE) * 8) - ITEM_OPTIONS_BITS)
+#define KEY_LEN_MAX ((1 << KEY_LEN_BITS) - 1)
+
+#define VALUE_LEN_BITS ((sizeof(VALUE_LEN_TYPE) * 8) - (sizeof(ITEM_FLAGS_TYPE) * 8))
+#define VALUE_LEN_MAX ((1 << VALUE_LEN_BITS) - 1)
+
+
+/*
+ * Every item in the dictionary has the following structure.
+ */
+
+typedef int32_t REFCOUNT;
+
+typedef struct dictionary_item_shared {
+    void *value;                            // the value of the dictionary item
+
+    // the order of the following items is important!
+    // The total of their storage should be 64-bits
+
+    REFCOUNT links;                         // how many links this item has
+    VALUE_LEN_TYPE value_len:VALUE_LEN_BITS; // the size of the value
+    ITEM_FLAGS_TYPE flags;                  // shared flags
+} DICTIONARY_ITEM_SHARED;
+
+struct dictionary_item {
+#ifdef NETDATA_INTERNAL_CHECKS
+    DICTIONARY *dict;
+    pid_t creator_pid;
+    pid_t deleter_pid;
+    pid_t ll_adder_pid;
+    pid_t ll_remover_pid;
+#endif
+
+    DICTIONARY_ITEM_SHARED *shared;
+
+    struct dictionary_item *next;           // a double linked list to allow fast insertions and deletions
+    struct dictionary_item *prev;
+
+    union {
+        STRING *string_name;                // the name of the dictionary item
+        char *caller_name;                  // the user supplied string pointer
+                             //        void *key_ptr;                      // binary key pointer
+    };
+
+    // the order of the following items is important!
+    // The total of their storage should be 64-bits
+
+    REFCOUNT refcount;                      // the private reference counter
+
+    KEY_LEN_TYPE key_len:KEY_LEN_BITS;      // the size of key indexed (for strings, including the null terminator)
+                                         // this is (2^23 - 1) = 8.388.607 bytes max key length.
+
+    ITEM_OPTIONS options:ITEM_OPTIONS_BITS; // permanent configuration options
+                                              // (no atomic operations on this - they never change)
+
+    ITEM_FLAGS_TYPE flags;                  // runtime changing flags for this item (atomic operations on this)
+                           // cannot be a bit field because of atomics.
+};
+
+struct dictionary_hooks {
+    REFCOUNT links;
+    usec_t last_master_deletion_us;
+
+    dict_cb_insert_t insert_callback;
+    void *insert_callback_data;
+
+    dict_cb_conflict_t conflict_callback;
+    void *conflict_callback_data;
+
+    dict_cb_react_t react_callback;
+    void *react_callback_data;
+
+    dict_cb_delete_t delete_callback;
+    void *delelte_callback_data;
+};
+
+struct dictionary {
+#ifdef NETDATA_INTERNAL_CHECKS
+    const char *creation_function;
+    const char *creation_file;
+    size_t creation_line;
+    pid_t creation_tid;
+#endif
+
+    usec_t last_gc_run_us;
+    DICT_OPTIONS options;               // the configuration flags of the dictionary (they never change - no atomics)
+    DICT_FLAGS flags;                   // run time flags for the dictionary (they change all the time - atomics needed)
+
+    ARAL *value_aral;
+
+    struct {                            // support for multiple indexing engines
+        Pvoid_t JudyHSArray;        // the hash table
+        RW_SPINLOCK rw_spinlock;        // protect the index
+    } index;
+
+    struct {
+        DICTIONARY_ITEM *list;          // the double linked list of all items in the dictionary
+        RW_SPINLOCK rw_spinlock;        // protect the linked-list
+        pid_t writer_pid;               // the gettid() of the writer
+        uint32_t writer_depth;          // nesting of write locks
+    } items;
+
+    struct dictionary_hooks *hooks;     // pointer to external function callbacks to be called at certain points
+    struct dictionary_stats *stats;     // statistics data, when DICT_OPTION_STATS is set
+
+    DICTIONARY *master;                 // the master dictionary
+    DICTIONARY *next;                   // linked list for delayed destruction (garbage collection of whole dictionaries)
+
+    uint32_t version;                   // the current version of the dictionary
+                      // it is incremented when:
+                      //   - item added
+                      //   - item removed
+                      //   - item value reset
+                      //   - conflict callback returns true
+                      //   - function dictionary_version_increment() is called
+
+    int32_t entries;                   // how many items are currently in the index (the linked list may have more)
+    int32_t referenced_items;          // how many items of the dictionary are currently being used by 3rd parties
+    int32_t pending_deletion_items;    // how many items of the dictionary have been deleted, but have not been removed yet
+
+#ifdef NETDATA_DICTIONARY_VALIDATE_POINTERS
+    netdata_mutex_t global_pointer_registry_mutex;
+    Pvoid_t global_pointer_registry;
+#endif
+};
+
+// ----------------------------------------------------------------------------
+// forward definitions of functions used in reverse order in the code
+
+void garbage_collect_pending_deletes(DICTIONARY *dict);
+static inline void item_linked_list_remove(DICTIONARY *dict, DICTIONARY_ITEM *item);
+static size_t dict_item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item);
+static inline const char *item_get_name(const DICTIONARY_ITEM *item);
+static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item);
+static void item_release(DICTIONARY *dict, DICTIONARY_ITEM *item);
+static bool dict_item_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item);
+
+#define RC_ITEM_OK                         ( 0)
+#define RC_ITEM_MARKED_FOR_DELETION        (-1) // the item is marked for deletion
+#define RC_ITEM_IS_CURRENTLY_BEING_DELETED (-2) // the item is currently being deleted
+#define RC_ITEM_IS_CURRENTLY_BEING_CREATED (-3) // the item is currently being deleted
+#define RC_ITEM_IS_REFERENCED              (-4) // the item is currently referenced
+#define item_check_and_acquire(dict, item) (item_check_and_acquire_advanced(dict, item, false) == RC_ITEM_OK)
+static int item_check_and_acquire_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item, bool having_index_lock);
+#define item_is_not_referenced_and_can_be_removed(dict, item) (item_is_not_referenced_and_can_be_removed_advanced(dict, item) == RC_ITEM_OK)
+static inline int item_is_not_referenced_and_can_be_removed_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item);
+
+// ----------------------------------------------------------------------------
+// validate each pointer is indexed once - internal checks only
+
+#ifdef NETDATA_DICTIONARY_VALIDATE_POINTERS
+static inline void pointer_index_init(DICTIONARY *dict __maybe_unused) {
+    netdata_mutex_init(&dict->global_pointer_registry_mutex);
+}
+
+static inline void pointer_destroy_index(DICTIONARY *dict __maybe_unused) {
+    netdata_mutex_lock(&dict->global_pointer_registry_mutex);
+    JudyHSFreeArray(&dict->global_pointer_registry, PJE0);
+    netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
+}
+static inline void pointer_add(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) {
+    netdata_mutex_lock(&dict->global_pointer_registry_mutex);
+    Pvoid_t *PValue = JudyHSIns(&dict->global_pointer_registry, &item, sizeof(void *), PJE0);
+    if(*PValue != NULL)
+        fatal("pointer already exists in registry");
+    *PValue = item;
+    netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
+}
+
+static inline void pointer_check(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) {
+    netdata_mutex_lock(&dict->global_pointer_registry_mutex);
+    Pvoid_t *PValue = JudyHSGet(dict->global_pointer_registry, &item, sizeof(void *));
+    if(PValue == NULL)
+        fatal("pointer is not found in registry");
+    netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
+}
+
+static inline void pointer_del(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) {
+    netdata_mutex_lock(&dict->global_pointer_registry_mutex);
+    int ret = JudyHSDel(&dict->global_pointer_registry, &item, sizeof(void *), PJE0);
+    if(!ret)
+        fatal("pointer to be deleted does not exist in registry");
+    netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
+}
+#else // !NETDATA_DICTIONARY_VALIDATE_POINTERS
+#define pointer_index_init(dict) debug_dummy()
+#define pointer_destroy_index(dict) debug_dummy()
+#define pointer_add(dict, item) debug_dummy()
+#define pointer_check(dict, item) debug_dummy()
+#define pointer_del(dict, item) debug_dummy()
+#endif // !NETDATA_DICTIONARY_VALIDATE_POINTERS
+
+extern ARAL *dict_items_aral;
+extern ARAL *dict_shared_items_aral;
+
+#include "dictionary-statistics.h"
+#include "dictionary-locks.h"
+#include "dictionary-refcount.h"
+#include "dictionary-hashtable.h"
+#include "dictionary-callbacks.h"
+#include "dictionary-item.h"
+
+#endif //NETDATA_DICTIONARY_INTERNALS_H