// 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