diff options
author | Costa Tsaousis <costa@netdata.cloud> | 2024-02-03 20:09:28 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-02-03 18:09:28 +0000 |
commit | 43c4a8a83df4f223023de79069e82fcca5e25e7b (patch) | |
tree | 59d1879342e8d61fb4b82e2b2aee6674f7522aae /src | |
parent | c86f21b621246512a8f865d42377e370378e6184 (diff) |
split dictionary into multiple files (#16920)
* split dictionary into multiple files
* rename to hashtable
* dictionaries now support SIMPLE_HASHTABLE indexing, with user selection via a dictionary option
Diffstat (limited to 'src')
-rw-r--r-- | src/libnetdata/dictionary/dictionary-callbacks.h | 93 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-hashtable.h | 263 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-internals.h | 259 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-item.h | 555 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-locks.h | 112 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-refcount.h | 247 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-statistics.h | 246 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-traversal.c | 268 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary-unittest.c | 1195 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary.c | 3073 | ||||
-rw-r--r-- | src/libnetdata/dictionary/dictionary.h | 12 | ||||
-rw-r--r-- | src/libnetdata/dictionary/thread-cache.c | 47 | ||||
-rw-r--r-- | src/libnetdata/dictionary/thread-cache.h | 15 | ||||
-rw-r--r-- | src/libnetdata/libnetdata.h | 1 |
14 files changed, 3318 insertions, 3068 deletions
diff --git a/src/libnetdata/dictionary/dictionary-callbacks.h b/src/libnetdata/dictionary/dictionary-callbacks.h new file mode 100644 index 0000000000..38da3df099 --- /dev/null +++ b/src/libnetdata/dictionary/dictionary-callbacks.h @@ -0,0 +1,93 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_DICTIONARY_CALLBACKS_H +#define NETDATA_DICTIONARY_CALLBACKS_H + +#include "dictionary-internals.h" + +// ---------------------------------------------------------------------------- +// callbacks execution + +static inline void dictionary_execute_insert_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->insert_callback)) + return; + + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(false, + "DICTIONARY: Running insert callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + dict->hooks->insert_callback(item, item->shared->value, constructor_data?constructor_data:dict->hooks->insert_callback_data); + DICTIONARY_STATS_CALLBACK_INSERTS_PLUS1(dict); +} + +static inline bool dictionary_execute_conflict_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *new_value, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->conflict_callback)) + return false; + + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(false, + "DICTIONARY: Running conflict callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + bool ret = dict->hooks->conflict_callback( + item, item->shared->value, new_value, + constructor_data ? constructor_data : dict->hooks->conflict_callback_data); + + DICTIONARY_STATS_CALLBACK_CONFLICTS_PLUS1(dict); + + return ret; +} + +static inline void dictionary_execute_react_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->react_callback)) + return; + + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(false, + "DICTIONARY: Running react callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + dict->hooks->react_callback(item, item->shared->value, + constructor_data?constructor_data:dict->hooks->react_callback_data); + + DICTIONARY_STATS_CALLBACK_REACTS_PLUS1(dict); +} + +static inline void dictionary_execute_delete_callback(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(likely(!dict->hooks || !dict->hooks->delete_callback)) + return; + + // We may execute delete callback on items deleted from a view, + // because we may have references to it, after the master is gone + // so, the shared structure will remain until the last reference is released. + + internal_error(false, + "DICTIONARY: Running delete callback on item '%s' of dictionary created from %s() %zu@%s.", + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + dict->hooks->delete_callback(item, item->shared->value, dict->hooks->delelte_callback_data); + + DICTIONARY_STATS_CALLBACK_DELETES_PLUS1(dict); +} + + +#endif //NETDATA_DICTIONARY_CALLBACKS_H diff --git a/src/libnetdata/dictionary/dictionary-hashtable.h b/src/libnetdata/dictionary/dictionary-hashtable.h new file mode 100644 index 0000000000..ace22d91de --- /dev/null +++ b/src/libnetdata/dictionary/dictionary-hashtable.h @@ -0,0 +1,263 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_DICTIONARY_HASHTABLE_H +#define NETDATA_DICTIONARY_HASHTABLE_H + +#include "dictionary-internals.h" + +// ---------------------------------------------------------------------------- +// hashtable operations with simple hashtable + +static inline bool compare_keys(void *key1, void *key2) { + const char *k1 = key1; + const char *k2 = key2; + return strcmp(k1, k2) == 0; +} + +static inline void *item_to_key(DICTIONARY_ITEM *item) { + return (void *)item_get_name(item); +} + +#define SIMPLE_HASHTABLE_VALUE_TYPE DICTIONARY_ITEM +#define SIMPLE_HASHTABLE_NAME _DICTIONARY +#define SIMPLE_HASHTABLE_VALUE2KEY_FUNCTION item_to_key +#define SIMPLE_HASHTABLE_COMPARE_KEYS_FUNCTION compare_keys +#include "..//simple_hashtable.h" + +static inline size_t hashtable_init_hashtable(DICTIONARY *dict) { + SIMPLE_HASHTABLE_DICTIONARY *ht = callocz(1, sizeof(*ht)); + simple_hashtable_init_DICTIONARY(ht, 4); + dict->index.JudyHSArray = ht; + return 0; +} + +static inline size_t hashtable_destroy_hashtable(DICTIONARY *dict) { + SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; + if(unlikely(!ht)) return 0; + + size_t mem = sizeof(*ht) + ht->size * sizeof(SIMPLE_HASHTABLE_SLOT_DICTIONARY); + simple_hashtable_destroy_DICTIONARY(ht); + freez(ht); + dict->index.JudyHSArray = NULL; + + return mem; +} + +static inline void *hashtable_insert_hashtable(DICTIONARY *dict, const char *name, size_t name_len) { + SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; + + char key[name_len+1]; + memcpy(key, name, name_len); + key[name_len] = '\0'; + + XXH64_hash_t hash = XXH3_64bits(name, name_len); + SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = simple_hashtable_get_slot_DICTIONARY(ht, hash, key, true); + sl->hash = hash; // we will need it in insert later - it is ok to overwrite - it is the same already + return sl; +} + +static inline DICTIONARY_ITEM *hashtable_insert_handle_to_item_hashtable(DICTIONARY *dict, void *handle) { + (void)dict; + SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = handle; + DICTIONARY_ITEM *item = SIMPLE_HASHTABLE_SLOT_DATA(sl); + return item; +} + +static inline void hashtable_set_item_hashtable(DICTIONARY *dict, void *handle, DICTIONARY_ITEM *item) { + SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; + SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = handle; + simple_hashtable_set_slot_DICTIONARY(ht, sl, sl->hash, item); +} + +static inline int hashtable_delete_hashtable(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item_to_delete) { + (void)item_to_delete; + SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; + + char key[name_len+1]; + memcpy(key, name, name_len); + key[name_len] = '\0'; + + XXH64_hash_t hash = XXH3_64bits(name, name_len); + SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = simple_hashtable_get_slot_DICTIONARY(ht, hash, key, false); + DICTIONARY_ITEM *item = SIMPLE_HASHTABLE_SLOT_DATA(sl); + if(!item) return 0; // return not-found + + simple_hashtable_del_slot_DICTIONARY(ht, sl); + return 1; // return deleted +} + +static inline DICTIONARY_ITEM *hashtable_get_hashtable(DICTIONARY *dict, const char *name, size_t name_len) { + SIMPLE_HASHTABLE_DICTIONARY *ht = dict->index.JudyHSArray; + if(unlikely(!ht)) return NULL; + + char key[name_len+1]; + memcpy(key, name, name_len); + key[name_len] = '\0'; + + XXH64_hash_t hash = XXH3_64bits(name, name_len); + SIMPLE_HASHTABLE_SLOT_DICTIONARY *sl = simple_hashtable_get_slot_DICTIONARY(ht, hash, key, false); + return SIMPLE_HASHTABLE_SLOT_DATA(sl); +} + +// ---------------------------------------------------------------------------- +// hashtable operations with Judy + +static inline size_t hashtable_init_judy(DICTIONARY *dict) { + dict->index.JudyHSArray = NULL; + return 0; +} + +static inline size_t hashtable_destroy_judy(DICTIONARY *dict) { + if(unlikely(!dict->index.JudyHSArray)) return 0; + + pointer_destroy_index(dict); + + JError_t J_Error; + Word_t ret = JudyHSFreeArray(&dict->index.JudyHSArray, &J_Error); + if(unlikely(ret == (Word_t) JERR)) { + netdata_log_error("DICTIONARY: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); + } + + netdata_log_debug(D_DICTIONARY, "Dictionary: hash table freed %lu bytes", ret); + + dict->index.JudyHSArray = NULL; + return (size_t)ret; +} + +static inline void *hashtable_insert_judy(DICTIONARY *dict, const char *name, size_t name_len) { + JError_t J_Error; + Pvoid_t *Rc = JudyHSIns(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); + if (unlikely(Rc == PJERR)) { + netdata_log_error("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", + name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); + } + + // if *Rc == 0, new item added to the array + // otherwise the existing item value is returned in *Rc + + // we return a pointer to a pointer, so that the caller can + // put anything needed at the value of the index. + // The pointer to pointer we return has to be used before + // any other operation that may change the index (insert/delete). + return (void *)Rc; +} + +static inline DICTIONARY_ITEM *hashtable_insert_handle_to_item_judy(DICTIONARY *dict, void *handle) { + (void)dict; + DICTIONARY_ITEM **item_pptr = handle; + return *item_pptr; +} + +static inline void hashtable_set_item_judy(DICTIONARY *dict, void *handle, DICTIONARY_ITEM *item) { + (void)dict; + DICTIONARY_ITEM **item_pptr = handle; + *item_pptr = item; +} + +static inline int hashtable_delete_judy(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item) { + (void)item; + if(unlikely(!dict->index.JudyHSArray)) return 0; + + JError_t J_Error; + int ret = JudyHSDel(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); + if(unlikely(ret == JERR)) { + netdata_log_error("DICTIONARY: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d", + name, + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); + return 0; + } + + // Hey, this is problematic! We need the value back, not just an int with a status! + // https://sourceforge.net/p/judy/feature-requests/23/ + + if(unlikely(ret == 0)) { + // not found in the dictionary + return 0; + } + else { + // found and deleted from the dictionary + return 1; + } +} + +static inline DICTIONARY_ITEM *hashtable_get_judy(DICTIONARY *dict, const char *name, size_t name_len) { + if(unlikely(!dict->index.JudyHSArray)) return NULL; + + Pvoid_t *Rc; + Rc = JudyHSGet(dict->index.JudyHSArray, (void *)name, name_len); + if(likely(Rc)) { + // found in the hash table + pointer_check(dict, (DICTIONARY_ITEM *)*Rc); + return (DICTIONARY_ITEM *)*Rc; + } + else { + // not found in the hash table + return NULL; + } +} + +// -------------------------------------------------------------------------------------------------------------------- +// select the right hashtable + +static inline size_t hashtable_init_unsafe(DICTIONARY *dict) { + if(dict->options & DICT_OPTION_INDEX_JUDY) + return hashtable_init_judy(dict); + else + return hashtable_init_hashtable(dict); +} + +static inline size_t hashtable_destroy_unsafe(DICTIONARY *dict) { + pointer_destroy_index(dict); + + if(dict->options & DICT_OPTION_INDEX_JUDY) + return hashtable_destroy_judy(dict); + else + return hashtable_destroy_hashtable(dict); +} + +static inline void *hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + if(dict->options & DICT_OPTION_INDEX_JUDY) + return hashtable_insert_judy(dict, name, name_len); + else + return hashtable_insert_hashtable(dict, name, name_len); +} + +static inline DICTIONARY_ITEM *hashtable_insert_handle_to_item_unsafe(DICTIONARY *dict, void *handle) { + if(dict->options & DICT_OPTION_INDEX_JUDY) + return hashtable_insert_handle_to_item_judy(dict, handle); + else + return hashtable_insert_handle_to_item_hashtable(dict, handle); +} + +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item) { + if(dict->options & DICT_OPTION_INDEX_JUDY) + return hashtable_delete_judy(dict, name, name_len, item); + else + return hashtable_delete_hashtable(dict, name, name_len, item); +} + +static inline DICTIONARY_ITEM *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + DICTIONARY_STATS_SEARCHES_PLUS1(dict); + + DICTIONARY_ITEM *item; + + if(dict->options & DICT_OPTION_INDEX_JUDY) + item = hashtable_get_judy(dict, name, name_len); + else + item = hashtable_get_hashtable(dict, name, name_len); + + if(item) + pointer_check(dict, item); + + return item; +} + +static inline void hashtable_set_item_unsafe(DICTIONARY *dict, void *handle, DICTIONARY_ITEM *item) { + if(dict->options & DICT_OPTION_INDEX_JUDY) + hashtable_set_item_judy(dict, handle, item); + else + hashtable_set_item_hashtable(dict, handle, item); +} + +#endif //NETDATA_DICTIONARY_HASHTABLE_H diff --git a/src/libnetdata/dictionary/dictionary-internals.h b/src/libnetdata/dictionary/dictionary-internals.h new file mode 100644 index 0000000000..54e59564f1 --- /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 diff --git a/src/libnetdata/dictionary/dictionary-item.h b/src/libnetdata/dictionary/dictionary-item.h new file mode 100644 index 0000000000..d9c67bcb51 --- /dev/null +++ b/src/libnetdata/dictionary/dictionary-item.h @@ -0,0 +1,555 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_DICTIONARY_ITEM_H +#define NETDATA_DICTIONARY_ITEM_H + +#include "dictionary-internals.h" + +// ---------------------------------------------------------------------------- +// ITEM initialization and updates + +static inline size_t item_set_name(DICTIONARY *dict, DICTIONARY_ITEM *item, const char *name, size_t name_len) { + if(likely(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE)) { + item->caller_name = (char *)name; + item->key_len = name_len; + } + else { + item->string_name = string_strdupz(name); + item->key_len = string_strlen(item->string_name); + item->options |= ITEM_OPTION_ALLOCATED_NAME; + } + + return item->key_len; +} + +static inline size_t item_free_name(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(likely(!(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE))) + string_freez(item->string_name); + + return item->key_len; +} + +static inline const char *item_get_name(const DICTIONARY_ITEM *item) { + if(item->options & ITEM_OPTION_ALLOCATED_NAME) + return string2str(item->string_name); + else + return item->caller_name; +} + +static inline size_t item_get_name_len(const DICTIONARY_ITEM *item) { + if(item->options & ITEM_OPTION_ALLOCATED_NAME) + return string_strlen(item->string_name); + else + return strlen(item->caller_name); +} + +// ---------------------------------------------------------------------------- + +static inline DICTIONARY_ITEM *dict_item_create(DICTIONARY *dict __maybe_unused, size_t *allocated_bytes, DICTIONARY_ITEM *master_item) { + DICTIONARY_ITEM *item; + + size_t size = sizeof(DICTIONARY_ITEM); + item = aral_mallocz(dict_items_aral); + memset(item, 0, sizeof(DICTIONARY_ITEM)); + +#ifdef NETDATA_INTERNAL_CHECKS + item->creator_pid = gettid(); +#endif + + item->refcount = 1; + item->flags = ITEM_FLAG_BEING_CREATED; + + *allocated_bytes += size; + + if(master_item) { + item->shared = master_item->shared; + + if(unlikely(__atomic_add_fetch(&item->shared->links, 1, __ATOMIC_ACQUIRE) <= 1)) + fatal("DICTIONARY: attempted to link to a shared item structure that had zero references"); + } + else { + size = sizeof(DICTIONARY_ITEM_SHARED); + item->shared = aral_mallocz(dict_shared_items_aral); + memset(item->shared, 0, sizeof(DICTIONARY_ITEM_SHARED)); + + item->shared->links = 1; + *allocated_bytes += size; + } + +#ifdef NETDATA_INTERNAL_CHECKS + item->dict = dict; +#endif + return item; +} + +static inline void *dict_item_value_mallocz(DICTIONARY *dict, size_t value_len) { + if(dict->value_aral) { + internal_fatal(aral_element_size(dict->value_aral) != value_len, + "DICTIONARY: item value size %zu does not match the configured fixed one %zu", + value_len, aral_element_size(dict->value_aral)); + return aral_mallocz(dict->value_aral); + } + else + return mallocz(value_len); +} + +static inline void dict_item_value_freez(DICTIONARY *dict, void *ptr) { + if(dict->value_aral) + aral_freez(dict->value_aral, ptr); + else + freez(ptr); +} + +static inline void *dict_item_value_create(DICTIONARY *dict, void *value, size_t value_len) { + void *ptr = NULL; + + if(likely(value_len)) { + if (likely(value)) { + // a value has been supplied + // copy it + ptr = dict_item_value_mallocz(dict, value_len); + memcpy(ptr, value, value_len); + } + else { + // no value has been supplied + // allocate a clear memory block + ptr = dict_item_value_mallocz(dict, value_len); + memset(ptr, 0, value_len); + } + } + // else + // the caller wants an item without any value + + return ptr; +} + +static inline DICTIONARY_ITEM *dict_item_create_with_hooks(DICTIONARY *dict, const char *name, size_t name_len, void *value, size_t value_len, void *constructor_data, DICTIONARY_ITEM *master_item) { +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(name_len > KEY_LEN_MAX)) + fatal("DICTIONARY: tried to index a key of size %zu, but the maximum acceptable is %zu", name_len, (size_t)KEY_LEN_MAX); + + if(unlikely(value_len > VALUE_LEN_MAX)) + fatal("DICTIONARY: tried to add an item of size %zu, but the maximum acceptable is %zu", value_len, (size_t)VALUE_LEN_MAX); +#endif + + size_t item_size = 0, key_size = 0, value_size = 0; + + DICTIONARY_ITEM *item = dict_item_create(dict, &item_size, master_item); + key_size += item_set_name(dict, item, name, name_len); + + if(unlikely(is_view_dictionary(dict))) { + // we are on a view dictionary + // do not touch the value + ; + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(!master_item)) + fatal("DICTIONARY: cannot add an item to a view without a master item."); +#endif + } + else { + // we are on the master dictionary + + if(unlikely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) + item->shared->value = value; + else + item->shared->value = dict_item_value_create(dict, value, value_len); + + item->shared->value_len = value_len; + value_size += value_len; + + dictionary_execute_insert_callback(dict, item, constructor_data); + } + + DICTIONARY_ENTRIES_PLUS1(dict); + DICTIONARY_STATS_PLUS_MEMORY(dict, key_size, item_size, value_size); + + return item; +} + +static inline void dict_item_reset_value_with_hooks(DICTIONARY *dict, |