diff options
Diffstat (limited to 'libnetdata/dictionary/dictionary.c')
| -rw-r--r-- | libnetdata/dictionary/dictionary.c | 3686 |
1 files changed, 2450 insertions, 1236 deletions
diff --git a/libnetdata/dictionary/dictionary.c b/libnetdata/dictionary/dictionary.c index c1325ecb..f03da25a 100644 --- a/libnetdata/dictionary/dictionary.c +++ b/libnetdata/dictionary/dictionary.c @@ -1,64 +1,137 @@ // SPDX-License-Identifier: GPL-3.0-or-later -// NOT TO BE USED BY USERS -#define DICTIONARY_FLAG_EXCLUSIVE_ACCESS (1 << 29) // there is only one thread accessing the dictionary -#define DICTIONARY_FLAG_DESTROYED (1 << 30) // this dictionary has been destroyed -#define DICTIONARY_FLAG_DEFER_ALL_DELETIONS (1 << 31) // defer all deletions of items in the dictionary - -// our reserved flags that cannot be set by users -#define DICTIONARY_FLAGS_RESERVED (DICTIONARY_FLAG_EXCLUSIVE_ACCESS|DICTIONARY_FLAG_DESTROYED|DICTIONARY_FLAG_DEFER_ALL_DELETIONS) - -typedef struct dictionary DICTIONARY; #define DICTIONARY_INTERNALS #include "../libnetdata.h" +#include <Judy.h> -#ifndef ENABLE_DBENGINE -#define DICTIONARY_WITH_AVL -#warning Compiling DICTIONARY with an AVL index -#else -#define DICTIONARY_WITH_JUDYHS -#endif +// runtime flags of the dictionary - must be checked with atomics +typedef enum { + DICT_FLAG_NONE = 0, + DICT_FLAG_DESTROYED = (1 << 0), // this dictionary has been destroyed +} DICT_FLAGS; -#ifdef DICTIONARY_WITH_JUDYHS -#include <Judy.h> -#endif +#define dict_flag_check(dict, flag) (__atomic_load_n(&((dict)->flags), __ATOMIC_SEQ_CST) & (flag)) +#define dict_flag_set(dict, flag) __atomic_or_fetch(&((dict)->flags), flag, __ATOMIC_SEQ_CST) +#define dict_flag_clear(dict, flag) __atomic_and_fetch(&((dict)->flags), ~(flag), __ATOMIC_SEQ_CST) + +// 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 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 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_SEQ_CST) & (flag)) +#define item_flag_set(item, flag) __atomic_or_fetch(&((item)->flags), flag, __ATOMIC_SEQ_CST) +#define item_flag_clear(item, flag) __atomic_and_fetch(&((item)->flags), ~(flag), __ATOMIC_SEQ_CST) + +#define item_shared_flag_check(item, flag) (__atomic_load_n(&((item)->shared->flags), __ATOMIC_SEQ_CST) & (flag)) +#define item_shared_flag_set(item, flag) __atomic_or_fetch(&((item)->shared->flags), flag, __ATOMIC_SEQ_CST) +#define item_shared_flag_clear(item, flag) __atomic_and_fetch(&((item)->shared->flags), ~(flag), __ATOMIC_SEQ_CST) -typedef enum name_value_flags { - NAME_VALUE_FLAG_NONE = 0, - NAME_VALUE_FLAG_NAME_IS_ALLOCATED = (1 << 0), // the name pointer is a STRING - NAME_VALUE_FLAG_DELETED = (1 << 1), // this item is deleted, so it is not available for traversal - NAME_VALUE_FLAG_NEW_OR_UPDATED = (1 << 2), // this item is new or just updated (used by the react callback) +#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) - // IMPORTANT: IF YOU ADD ANOTHER FLAG, YOU NEED TO ALLOCATE ANOTHER BIT TO FLAGS IN NAME_VALUE !!! -} NAME_VALUE_FLAGS; /* * Every item in the dictionary has the following structure. */ -typedef struct name_value { -#ifdef DICTIONARY_WITH_AVL - avl_t avl_node; -#endif +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 - struct name_value *next; // a double linked list to allow fast insertions and deletions - struct name_value *prev; + DICTIONARY_ITEM_SHARED *shared; - uint32_t refcount; // the reference counter - uint32_t value_len:29; // the size of the value (assumed binary) - uint8_t flags:3; // the flags for this item + struct dictionary_item *next; // a double linked list to allow fast insertions and deletions + struct dictionary_item *prev; - void *value; // the value of the dictionary item union { - STRING *string_name; // the name of the dictionary item - char *caller_name; // the user supplied string pointer + STRING *string_name; // the name of the dictionary item + char *caller_name; // the user supplied string pointer +// void *key_ptr; // binary key pointer }; -} NAME_VALUE; + + // 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; + + void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data); + void *ins_callback_data; + + bool (*conflict_callback)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data); + void *conflict_callback_data; + + void (*react_callback)(const DICTIONARY_ITEM *item, void *value, void *data); + void *react_callback_data; + + void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data); + void *del_callback_data; +}; + +struct dictionary_stats dictionary_stats_category_other = { + .name = "other", +}; struct dictionary { #ifdef NETDATA_INTERNAL_CHECKS @@ -67,331 +140,685 @@ struct dictionary { size_t creation_line; #endif - DICTIONARY_FLAGS flags; // the flags of the dictionary + 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) + + struct { // support for multiple indexing engines + Pvoid_t JudyHSArray; // the hash table + netdata_rwlock_t rwlock; // protect the index + } index; + + struct { + DICTIONARY_ITEM *list; // the double linked list of all items in the dictionary + netdata_rwlock_t rwlock; // protect the linked-list + pid_t writer_pid; // the gettid() of the writer + size_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 - NAME_VALUE *first_item; // the double linked list base pointers - NAME_VALUE *last_item; + DICTIONARY *master; // the master dictionary + DICTIONARY *next; // linked list for delayed destruction (garbage collection of whole dictionaries) -#ifdef DICTIONARY_WITH_AVL - avl_tree_type values_index; - NAME_VALUE *hash_base; - void *(*get_thread_static_name_value)(const char *name); + size_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 + + long int entries; // how many items are currently in the index (the linked list may have more) + long int referenced_items; // how many items of the dictionary are currently being used by 3rd parties + long int pending_deletion_items; // how many items of the dictionary have been deleted, but have not been removed yet + +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_t global_pointer_registry_mutex; + Pvoid_t global_pointer_registry; #endif +}; + +// forward definitions of functions used in reverse order in the code +static 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, void *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 DICTIONARY_WITH_JUDYHS - Pvoid_t JudyHSArray; // the hash table +static inline void pointer_index_init(DICTIONARY *dict __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_init(&dict->global_pointer_registry_mutex); +#else + ; #endif +} - netdata_rwlock_t rwlock; // the r/w lock when DICTIONARY_FLAG_SINGLE_THREADED is not set +static inline void pointer_destroy_index(DICTIONARY *dict __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + netdata_mutex_lock(&dict->global_pointer_registry_mutex); + JudyHSFreeArray(&dict->global_pointer_registry, PJE0); + netdata_mutex_unlock(&dict->global_pointer_registry_mutex); +#else + ; +#endif +} +static inline void pointer_add(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + 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); +#else + ; +#endif +} - void (*ins_callback)(const char *name, void *value, void *data); - void *ins_callback_data; +static inline void pointer_check(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + 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); +#else + ; +#endif +} - void (*react_callback)(const char *name, void *value, void *data); - void *react_callback_data; +static inline void pointer_del(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) { +#ifdef NETDATA_INTERNAL_CHECKS + 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 + ; +#endif +} - void (*del_callback)(const char *name, void *value, void *data); - void *del_callback_data; +// ---------------------------------------------------------------------------- +// memory statistics - void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data); - void *conflict_callback_data; +static inline void DICTIONARY_STATS_PLUS_MEMORY(DICTIONARY *dict, size_t key_size, size_t item_size, size_t value_size) { + if(key_size) + __atomic_fetch_add(&dict->stats->memory.indexed, (long)key_size, __ATOMIC_RELAXED); - size_t version; // the current version of the dictionary - size_t inserts; // how many index insertions have been performed - size_t deletes; // how many index deletions have been performed - size_t searches; // how many index searches have been performed - size_t resets; // how many times items have reset their values - size_t walkthroughs; // how many walkthroughs have been done - long int memory; // how much memory the dictionary has currently allocated - long int entries; // how many items are currently in the index (the linked list may have more) - long int referenced_items; // how many items of the dictionary are currently being used by 3rd parties - long int pending_deletion_items; // how many items of the dictionary have been deleted, but have not been removed yet - int readers; // how many readers are currently using the dictionary - int writers; // how many writers are currently using the dictionary - - size_t scratchpad_size; // the size of the scratchpad in bytes - uint8_t scratchpad[]; // variable size scratchpad requested by the caller -}; + if(item_size) + __atomic_fetch_add(&dict->stats->memory.dict, (long)item_size, __ATOMIC_RELAXED); + + if(value_size) + __atomic_fetch_add(&dict->stats->memory.values, (long)value_size, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_MINUS_MEMORY(DICTIONARY *dict, size_t key_size, size_t item_size, size_t value_size) { + if(key_size) + __atomic_fetch_sub(&dict->stats->memory.indexed, (long)key_size, __ATOMIC_RELAXED); -static inline void linkedlist_namevalue_unlink_unsafe(DICTIONARY *dict, NAME_VALUE *nv); -static size_t namevalue_destroy_unsafe(DICTIONARY *dict, NAME_VALUE *nv); -static inline const char *namevalue_get_name(NAME_VALUE *nv); + if(item_size) + __atomic_fetch_sub(&dict->stats->memory.dict, (long)item_size, __ATOMIC_RELAXED); + + if(value_size) + __atomic_fetch_sub(&dict->stats->memory.values, (long)value_size, __ATOMIC_RELAXED); +} // ---------------------------------------------------------------------------- // callbacks registration -void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const char *name, void *value, void *data), void *data) { - dict->ins_callback = ins_callback; - dict->ins_callback_data = data; -} +static inline void dictionary_hooks_allocate(DICTIONARY *dict) { + if(dict->hooks) return; -void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const char *name, void *value, void *data), void *data) { - dict->del_callback = del_callback; - dict->del_callback_data = data; -} + dict->hooks = callocz(1, sizeof(struct dictionary_hooks)); + dict->hooks->links = 1; -void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data), void *data) { - dict->conflict_callback = conflict_callback; - dict->conflict_callback_data = data; + DICTIONARY_STATS_PLUS_MEMORY(dict, 0, sizeof(struct dictionary_hooks), 0); } -void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const char *name, void *value, void *data), void *data) { - dict->react_callback = react_callback; - dict->react_callback_data = data; +static inline size_t dictionary_hooks_free(DICTIONARY *dict) { + if(!dict->hooks) return 0; + + REFCOUNT links = __atomic_sub_fetch(&dict->hooks->links, 1, __ATOMIC_SEQ_CST); + if(links == 0) { + freez(dict->hooks); + dict->hooks = NULL; + + DICTIONARY_STATS_MINUS_MEMORY(dict, 0, sizeof(struct dictionary_hooks), 0); + return sizeof(struct dictionary_hooks); + } + + return 0; } -// ---------------------------------------------------------------------------- -// dictionary statistics maintenance +void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); -long int dictionary_stats_allocated_memory(DICTIONARY *dict) { - return dict->memory; + dictionary_hooks_allocate(dict); + dict->hooks->ins_callback = ins_callback; + dict->hooks->ins_callback_data = data; } -long int dictionary_stats_entries(DICTIONARY *dict) { - return dict->entries; + +void dictionary_register_conflict_callback(DICTIONARY *dict, bool (*conflict_callback)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + internal_error(!(dict->options & DICT_OPTION_DONT_OVERWRITE_VALUE), "DICTIONARY: registering conflict callback without DICT_OPTION_DONT_OVERWRITE_VALUE"); + dict->options |= DICT_OPTION_DONT_OVERWRITE_VALUE; + + dictionary_hooks_allocate(dict); + dict->hooks->conflict_callback = conflict_callback; + dict->hooks->conflict_callback_data = data; } -size_t dictionary_stats_version(DICTIONARY *dict) { - return dict->version; + +void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + dictionary_hooks_allocate(dict); + dict->hooks->react_callback = react_callback; + dict->hooks->react_callback_data = data; } -size_t dictionary_stats_searches(DICTIONARY *dict) { - return dict->searches; + +void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); + + dictionary_hooks_allocate(dict); + dict->hooks->del_callback = del_callback; + dict->hooks->del_callback_data = data; } -size_t dictionary_stats_inserts(DICTIONARY *dict) { - return dict->inserts; + +// ---------------------------------------------------------------------------- +// dictionary statistics API + +size_t dictionary_version(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + + // this is required for views to return the right number + garbage_collect_pending_deletes(dict); + + return __atomic_load_n(&dict->version, __ATOMIC_SEQ_CST); } -size_t dictionary_stats_deletes(DICTIONARY *dict) { - return dict->deletes; +size_t dictionary_entries(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + + // this is required for views to return the right number + garbage_collect_pending_deletes(dict); + + long int entries = __atomic_load_n(&dict->entries, __ATOMIC_SEQ_CST); + if(entries < 0) + fatal("DICTIONARY: entries is negative: %ld", entries); + + return entries; } -size_t dictionary_stats_resets(DICTIONARY *dict) { - return dict->resets; +size_t dictionary_referenced_items(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + + long int referenced_items = __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); + if(referenced_items < 0) + fatal("DICTIONARY: referenced items is negative: %ld", referenced_items); + + return referenced_items; } -size_t dictionary_stats_walkthroughs(DICTIONARY *dict) { - return dict->walkthroughs; + +long int dictionary_stats_for_registry(DICTIONARY *dict) { + if(unlikely(!dict)) return 0; + return (dict->stats->memory.indexed + dict->stats->memory.dict); } -size_t dictionary_stats_referenced_items(DICTIONARY *dict) { - return __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); +void dictionary_version_increment(DICTIONARY *dict) { + __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); } +// ---------------------------------------------------------------------------- +// internal statistics API + static inline void DICTIONARY_STATS_SEARCHES_PLUS1(DICTIONARY *dict) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->searches++; - } - else { - __atomic_fetch_add(&dict->searches, 1, __ATOMIC_RELAXED); - } + __atomic_fetch_add(&dict->stats->ops.searches, 1, __ATOMIC_RELAXED); } -static inline void DICTIONARY_STATS_ENTRIES_PLUS1(DICTIONARY *dict, size_t size) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { +static inline void DICTIONARY_ENTRIES_PLUS1(DICTIONARY *dict) { + // statistics + __atomic_fetch_add(&dict->stats->items.entries, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->items.referenced, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->ops.inserts, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) { dict->version++; - dict->inserts++; dict->entries++; - dict->memory += (long)size; + dict->referenced_items++; + } else { __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); - __atomic_fetch_add(&dict->inserts, 1, __ATOMIC_RELAXED); - __atomic_fetch_add(&dict->entries, 1, __ATOMIC_RELAXED); - __atomic_fetch_add(&dict->memory, (long)size, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->entries, 1, __ATOMIC_SEQ_CST); + __atomic_fetch_add(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); } } -static inline void DICTIONARY_STATS_ENTRIES_MINUS1(DICTIONARY *dict) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { +static inline void DICTIONARY_ENTRIES_MINUS1(DICTIONARY *dict) { + // statistics + __atomic_fetch_add(&dict->stats->ops.deletes, 1, __ATOMIC_RELAXED); + __atomic_fetch_sub(&dict->stats->items.entries, 1, __ATOMIC_RELAXED); + + size_t entries; (void)entries; + if(unlikely(is_dictionary_single_threaded(dict))) { dict->version++; - dict->deletes++; - dict->entries--; + entries = dict->entries++; } else { __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); - __atomic_fetch_add(&dict->deletes, 1, __ATOMIC_RELAXED); - __atomic_fetch_sub(&dict->entries, 1, __ATOMIC_RELAXED); - } -} -static inline void DICTIONARY_STATS_ENTRIES_MINUS_MEMORY(DICTIONARY *dict, size_t size) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->memory -= (long)size; - } - else { - __atomic_fetch_sub(&dict->memory, (long)size, __ATOMIC_RELAXED); + entries = __atomic_fetch_sub(&dict->entries, 1, __ATOMIC_SEQ_CST); } + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(entries == 0)) + fatal("DICT: negative number of entries in dictionary created from %s() (%zu@%s)", + dict->creation_function, + dict->creation_line, + dict->creation_file); +#endif } -static inline void DICTIONARY_STATS_VALUE_RESETS_PLUS1(DICTIONARY *dict, size_t oldsize, size_t newsize) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { +static inline void DICTIONARY_VALUE_RESETS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.resets, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) dict->version++; - dict->resets++; - dict->memory += (long)newsize; - dict->memory -= (long)oldsize; - } - else { + else __atomic_fetch_add(&dict->version, 1, __ATOMIC_SEQ_CST); - __atomic_fetch_add(&dict->resets, 1, __ATOMIC_RELAXED); - __atomic_fetch_add(&dict->memory, (long)newsize, __ATOMIC_RELAXED); - __atomic_fetch_sub(&dict->memory, (long)oldsize, __ATOMIC_RELAXED); - } } - +static inline void DICTIONARY_STATS_TRAVERSALS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.traversals, 1, __ATOMIC_RELAXED); +} static inline void DICTIONARY_STATS_WALKTHROUGHS_PLUS1(DICTIONARY *dict) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->walkthroughs++; - } - else { - __atomic_fetch_add(&dict->walkthroughs, 1, __ATOMIC_RELAXED); - } + __atomic_fetch_add(&dict->stats->ops.walkthroughs, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CHECK_SPINS_PLUS(DICTIONARY *dict, size_t count) { + __atomic_fetch_add(&dict->stats->spin_locks.use_spins, count, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_INSERT_SPINS_PLUS(DICTIONARY *dict, size_t count) { + __atomic_fetch_add(&dict->stats->spin_locks.insert_spins, count, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DELETE_SPINS_PLUS(DICTIONARY *dict, size_t count) { + __atomic_fetch_add(&dict->stats->spin_locks.delete_spins, count, __ATOMIC_RELAXED); } +static inline void DICTIONARY_STATS_SEARCH_IGNORES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->spin_locks.search_spins, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_INSERTS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.inserts, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_CONFLICTS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.conflicts, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_REACTS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.reacts, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_CALLBACK_DELETES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->callbacks.deletes, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_GARBAGE_COLLECTIONS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.garbage_collections, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_CREATIONS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->dictionaries.active, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->ops.creations, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_DESTRUCTIONS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->dictionaries.active, 1, __ATOMIC_RELAXED); + __atomic_fetch_add(&dict->stats->ops.destructions, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_DESTROY_QUEUED_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->dictionaries.deleted, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_DESTROY_QUEUED_MINUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->dictionaries.deleted, 1, __ATOMIC_RELAXED); +} +static inline void DICTIONARY_STATS_DICT_FLUSHES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->ops.flushes, 1, __ATOMIC_RELAXED); +} + +static inline long int DICTIONARY_REFERENCED_ITEMS_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->items.referenced, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) + return ++dict->referenced_items; + else + return __atomic_add_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); +} + +static inline long int DICTIONARY_REFERENCED_ITEMS_MINUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->items.referenced, 1, __ATOMIC_RELAXED); + + long int referenced_items; + if(unlikely(is_dictionary_single_threaded(dict))) + referenced_items = --dict->referenced_items; + else + referenced_items = __atomic_sub_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(referenced_items < 0)) + fatal("DICT: negative number of referenced items (%ld) in dictionary created from %s() (%zu@%s)", + referenced_items, + dict->creation_function, + dict->creation_line, + dict->creation_file); +#endif -static inline size_t DICTIONARY_STATS_REFERENCED_ITEMS_PLUS1(DICTIONARY *dict) { - return __atomic_add_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); + return referenced_items; } -static inline size_t DICTIONARY_STATS_REFERENCED_ITEMS_MINUS1(DICTIONARY *dict) { - return __atomic_sub_fetch(&dict->referenced_items, 1, __ATOMIC_SEQ_CST); +static inline long int DICTIONARY_PENDING_DELETES_PLUS1(DICTIONARY *dict) { + __atomic_fetch_add(&dict->stats->items.pending_deletion, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) + return ++dict->pending_deletion_items; + else + return __atomic_add_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); } -static inline size_t DICTIONARY_STATS_PENDING_DELETES_PLUS1(DICTIONARY *dict) { - return __atomic_add_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); +static inline long int DICTIONARY_PENDING_DELETES_MINUS1(DICTIONARY *dict) { + __atomic_fetch_sub(&dict->stats->items.pending_deletion, 1, __ATOMIC_RELAXED); + + if(unlikely(is_dictionary_single_threaded(dict))) + return --dict->pending_deletion_items; + else + return __atomic_sub_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); } -static inline size_t DICTIONARY_STATS_PENDING_DELETES_MINUS1(DICTIONARY *dict) { - return __atomic_sub_fetch(&dict->pending_deletion_items, 1, __ATOMIC_SEQ_CST); +static inline long int DICTIONARY_PENDING_DELETES_GET(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return dict->pending_deletion_items; + else + return __atomic_load_n(&dict->pending_deletion_items, __ATOMIC_SEQ_CST); } -static inline size_t DICTIONARY_STATS_PENDING_DELETES_GET(DICTIONARY *dict) { - return __atomic_load_n(&dict->pending_deletion_items, __ATOMIC_SEQ_CST); +static inline REFCOUNT DICTIONARY_ITEM_REFCOUNT_GET(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(unlikely(dict && is_dictionary_single_threaded(dict))) // this is an exception, dict can be null + return item->refcount; + else + return (REFCOUNT)__atomic_load_n(&item->refcount, __ATOMIC_SEQ_CST); } -static inline int DICTIONARY_NAME_VALUE_REFCOUNT_GET(NAME_VALUE *nv) { - return __atomic_load_n(&nv->refcount, __ATOMIC_SEQ_CST); +static inline REFCOUNT DICTIONARY_ITEM_REFCOUNT_GET_SOLE(DICTIONARY_ITEM *item) { + return (REFCOUNT)__atomic_load_n(&item->refcount, __ATOMIC_SEQ_CST); } // ---------------------------------------------------------------------------- -// garbage collector -// it is called every time someone gets a write lock to the dictionary +// callbacks execution -static void garbage_collect_pending_deletes_unsafe(DICTIONARY *dict) { - if(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS)) return; +static void dictionary_execute_insert_callback(DICTIONARY *dict, DICTIONARY_ITEM *item, void *constructor_data) { + if(likely(!dict->hooks || !dict->hooks->ins_callback)) + return; - if(likely(!DICTIONARY_STATS_PENDING_DELETES_GET(dict))) return; + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: called %s() on a view.", __FUNCTION__ ); - NAME_VALUE *nv = dict->first_item; - while(nv) { - if((nv->flags & NAME_VALUE_FLAG_DELETED) && DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv) == 0) { - NAME_VALUE *nv_next = nv->next; + 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); - linkedlist_namevalue_unlink_unsafe(dict, nv); - namevalue_destroy_unsafe(dict, nv); + DICTIONARY_STATS_CALLBACK_INSERTS_PLUS1(dict); + dict->hooks->ins_callback(item, item->shared->value, constructor_data?constructor_data:dict->hooks->ins_callback_data); +} - size_t pending = DICTIONARY_STATS_PENDING_DELETES_MINUS1(dict); - if(!pending) break; +static 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; - nv = nv_next; - } - else - nv = nv->next; - } + 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); + + DICTIONARY_STATS_CALLBACK_CONFLICTS_PLUS1(dict); + return dict->hooks->conflict_callback( + item, item->shared->value, new_value, + constructor_data ? constructor_data : dict->hooks->conflict_callback_data); } -// ---------------------------------------------------------------------------- -// dictionary locks +static 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); + + DICTIONARY_STATS_CALLBACK_REACTS_PLUS1(dict); + dict->hooks->react_callback(item, item->shared->value, + constructor_data?constructor_data:dict->hooks->react_callback_data); +} -static inline size_t dictionary_lock_init(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - netdata_rwlock_init(&dict->rwlock); +static void dictionary_execute_delete_callback(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(likely(!dict->hooks || !dict->hooks->del_callback)) + return; + + // We may execute the 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. - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) - dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + 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); + + DICTIONARY_STATS_CALLBACK_DELETES_PLUS1(dict); + dict->hooks->del_callback(item, item->shared->value, dict->hooks->del_callback_data); +} + +// ---------------------------------------------------------------------------- +// dictionary locks +static inline size_t dictionary_locks_init(DICTIONARY *dict) { + if(likely(!is_dictionary_single_threaded(dict))) { + netdata_rwlock_init(&dict->index.rwlock); + netdata_rwlock_init(&dict->items.rwlock); return 0; } - - // we are single threaded - dict->flags |= DICTIONARY_FLAG_EXCLUSIVE_ACCESS; return 0; } -static inline size_t dictionary_lock_free(DICTIONARY *dict) { - if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) { - netdata_rwlock_destroy(&dict->rwlock); +static inline size_t dictionary_locks_destroy(DICTIONARY *dict) { + if(likely(!is_dictionary_single_threaded(dict))) { + netdata_rwlock_destroy(&dict->index.rwlock); + netdata_rwlock_destroy(&dict->items.rwlock); return 0; } return 0; } -static void dictionary_lock(DICTIONARY *dict, char rw) { - if(rw == 'u' || rw == 'U') return; +static inline void ll_recursive_lock_set_thread_as_writer(DICTIONARY *dict) { + pid_t expected = 0, desired = gettid(); + if(!__atomic_compare_exchange_n(&dict->items.writer_pid, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) + fatal("DICTIONARY: Cannot set thread %d as exclusive writer, expected %d, desired %d, found %d.", gettid(), expected, desired, __atomic_load_n(&dict->items.writer_pid, __ATOMIC_SEQ_CST)); +} - if(rw == 'r' || rw == 'R') { - // read lock - __atomic_add_fetch(&dict->readers, 1, __ATOMIC_RELAXED); - } - else { - // write lock - __atomic_add_fetch(&dict->writers, 1, __ATOMIC_RELAXED); - } +static inline void ll_recursive_unlock_unset_thread_writer(DICTIONARY *dict) { + pid_t expected = gettid(), desired = 0; + if(!__atomic_compare_exchange_n(&dict->items.writer_pid, &expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) + fatal("DICTIONARY: Cannot unset thread %d as exclusive writer, expected %d, desired %d, found %d.", gettid(), expected, desired, __atomic_load_n(&dict->items.writer_pid, __ATOMIC_SEQ_CST)); +} + +static inline bool ll_recursive_lock_is_thread_the_writer(DICTIONARY *dict) { + pid_t tid = gettid(); + return tid > 0 && tid == __atomic_load_n(&dict->items.writer_pid, __ATOMIC_SEQ_CST); +} - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) +static void ll_recursive_lock(DICTIONARY *dict, char rw) { + if(unlikely(is_dictionary_single_threaded(dict))) return; - if(rw == 'r' || rw == 'R') { - // read lock - netdata_rwlock_rdlock(&dict->rwlock); + if(ll_recursive_lock_is_thread_the_writer(dict)) { + dict->items.writer_depth++; + return; + } - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - internal_error(true, "DICTIONARY: left-over exclusive access to dictionary created by %s (%zu@%s) found", dict->creation_function, dict->creation_line, dict->creation_file); - dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; - } + if(rw == DICTIONARY_LOCK_READ || rw == DICTIONARY_LOCK_REENTRANT || rw == 'R') { + // read lock + netdata_rwlock_rdlock(&dict->items.rwlock); } else { // write lock - netdata_rwlock_wrlock(&dict->rwlock); - - dict->flags |= DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + netdata_rwlock_wrlock(&dict->items.rwlock); + ll_recursive_lock_set_thread_as_writer(dict); } } -static void dictionary_unlock(DICTIONARY *dict, char rw) { - if(rw == 'u' || rw == 'U') return; +static void ll_recursive_unlock(DICTIONARY *dict, char rw) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; - if(rw == 'r' || rw == 'R') { + if(ll_recursive_lock_is_thread_the_writer(dict) && dict->items.writer_depth > 0) { + dict->items.writer_depth--; + return; + } + + if(rw == DICTIONARY_LOCK_READ || rw == DICTIONARY_LOCK_REENTRANT || rw == 'R') { // read unlock - __atomic_sub_fetch(&dict->readers, 1, __ATOMIC_RELAXED); + + netdata_rwlock_unlock(&dict->items.rwlock); } else { // write unlock - garbage_collect_pending_deletes_unsafe(dict); - __atomic_sub_fetch(&dict->writers, 1, __ATOMIC_RELAXED); + + ll_recursive_unlock_unset_thread_writer(dict); + + netdata_rwlock_unlock(&dict->items.rwlock); } +} - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) +void dictionary_write_lock(DICTIONARY *dict) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); +} +void dictionary_write_unlock(DICTIONARY *dict) { + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); +} + +static inline void dictionary_index_lock_rdlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) return; - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) - dict->flags &= ~DICTIONARY_FLAG_EXCLUSIVE_ACCESS; + netdata_rwlock_rdlock(&dict->index.rwlock); +} + +static inline void dictionary_index_rdlock_unlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; - netdata_rwlock_unlock(&dict->rwlock); + netdata_rwlock_unlock(&dict->index.rwlock); } -// ---------------------------------------------------------------------------- -// deferred deletions +static inline void dictionary_index_lock_wrlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; -void dictionary_defer_all_deletions_unsafe(DICTIONARY *dict, char rw) { - if(rw == 'r' || rw == 'R') { - // read locked - no need to defer deletions - ; - } - else { - // write locked - defer deletions - dict->flags |= DICTIONARY_FLAG_DEFER_ALL_DELETIONS; - } + netdata_rwlock_wrlock(&dict->index.rwlock); } +static inline void dictionary_index_wrlock_unlock(DICTIONARY *dict) { + if(unlikely(is_dictionary_single_threaded(dict))) + return; -void dictionary_restore_all_deletions_unsafe(DICTIONARY *dict, char rw) { - if(rw == 'r' || rw == 'R') { - // read locked - no need to defer deletions - internal_error(dict->flags & DICTIONARY_FLAG_DEFER_ALL_DELETIONS, "DICTIONARY: deletions are deferred on a read lock"); - } - else { - // write locked - defer deletions - if(dict->flags & DICTIONARY_FLAG_DEFER_ALL_DELETIONS) - dict->flags &= ~DICTIONARY_FLAG_DEFER_ALL_DELETIONS; + netdata_rwlock_unlock(&dict->index.rwlock); +} + +// ---------------------------------------------------------------------------- +// items garbage collector + +static void garbage_collect_pending_deletes(DICTIONARY *dict) { + usec_t last_master_deletion_us = dict->hooks?__atomic_load_n(&dict->hooks->last_master_deletion_us, __ATOMIC_SEQ_CST):0; + usec_t last_gc_run_us = __atomic_load_n(&dict->last_gc_run_us, __ATOMIC_SEQ_CST); + + bool is_view = is_view_dictionary(dict); + + if(likely(!( + DICTIONARY_PENDING_DELETES_GET(dict) > 0 || + (is_view && last_master_deletion_us > last_gc_run_us) + ))) + return; + + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + __atomic_store_n(&dict->last_gc_run_us, now_realtime_usec(), __ATOMIC_SEQ_CST); + + if(is_view) + dictionary_index_lock_wrlock(dict); + + DICTIONARY_STATS_GARBAGE_COLLECTIONS_PLUS1(dict); + + size_t deleted = 0, pending = 0, examined = 0; + DICTIONARY_ITEM *item = dict->items.list, *item_next; + while(item) { + examined++; + + // this will cleanup + item_next = item->next; + int rc = item_check_and_acquire_advanced(dict, item, is_view); + + if(rc == RC_ITEM_MARKED_FOR_DELETION) { + // we didn't get a reference + + if(item_is_not_referenced_and_can_be_removed(dict, item)) { + DOUBLE_LINKED_LIST_REMOVE_UNSAFE(dict->items.list, item, prev, next); + dict_item_free_with_hooks(dict, item); + deleted++; + + pending = DICTIONARY_PENDING_DELETES_MINUS1(dict); + if (!pending) + break; + } + } + else if(rc == RC_ITEM_IS_CURRENTLY_BEING_DELETED) + ; // do not touch this item (we didn't get a reference) + + else if(rc == RC_ITEM_OK) + item_release(dict, item); + + item = item_next; } + + if(is_view) + dictionary_index_wrlock_unlock(dict); + + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + + (void)deleted; + (void)examined; + + internal_error(false, "DICTIONARY: garbage collected dictionary created by %s (%zu@%s), examined %zu items, deleted %zu items, still pending %zu items", + dict->creation_function, dict->creation_line, dict->creation_file, examined, deleted, pending); + } // ---------------------------------------------------------------------------- @@ -413,144 +840,248 @@ static inline size_t reference_counter_free(DICTIONARY *dict) { return 0; } -static int reference_counter_increase(NAME_VALUE *nv) { - int refcount = __atomic_add_fetch(&nv->refcount, 1, __ATOMIC_SEQ_CST); - if(refcount == 1) - fatal("DICTIONARY: request to dup item '%s' but its reference counter was zero", namevalue_get_name(nv)); - return refcount; -} +static void item_acquire(DICTIONARY *dict, DICTIONARY_ITEM *item) { + REFCOUNT refcount; -static int reference_counter_acquire(DICTIONARY *dict, NAME_VALUE *nv) { - int refcount; - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) - refcount = ++nv->refcount; - else - refcount = __atomic_add_fetch(&nv->refcount, 1, __ATOMIC_SEQ_CST); + if(unlikely(is_dictionary_single_threaded(dict))) { + refcount = ++item->refcount; + } + else { + // increment the refcount + refcount = __atomic_add_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST); + } + + if(refcount <= 0) { + internal_error( + true, + "DICTIONARY: attempted to acquire item which is deleted (refcount = %d): " + "'%s' on dictionary created by %s() (%zu@%s)", + refcount - 1, + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + fatal( + "DICTIONARY: request to acquire item '%s', which is deleted (refcount = %d)!", + item_get_name(item), + refcount - 1); + } if(refcount == 1) { // referenced items counts number of unique items referenced // so, we increase it only when refcount == 1 - DICTIONARY_STATS_REFERENCED_ITEMS_PLUS1(dict); + DICTIONARY_REFERENCED_ITEMS_PLUS1(dict); // if this is a deleted item, but the counter increased to 1 // we need to remove it from the pending items to delete - if (nv->flags & NAME_VALUE_FLAG_DELETED) - DICTIONARY_STATS_PENDING_DELETES_MINUS1(dict); + if(item_flag_check(item, ITEM_FLAG_DELETED)) + DICTIONARY_PENDING_DELETES_MINUS1(dict); } - - return refcount; } -static uint32_t reference_counter_release(DICTIONARY *dict, NAME_VALUE *nv, bool can_get_write_lock) { +static void item_release(DICTIONARY *dict, DICTIONARY_ITEM *item) { // this function may be called without any lock on the dictionary - // or even when someone else has a write lock on the dictionary - // so, we cannot check for EXCLUSIVE ACCESS + // or even when someone else has write lock on the dictionary - uint32_t refcount; - if(likely(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED)) - refcount = nv->refcount--; - else - refcount = __atomic_fetch_sub(&nv->refcount, 1, __ATOMIC_SEQ_CST); + bool is_deleted; + REFCOUNT refcount; - if(refcount == 0) { - internal_error(true, "DICTIONARY: attempted to release item without references: '%s' on dictionary created by %s() (%zu@%s)", namevalue_get_name(nv), dict->creation_function, dict->creation_line, dict->creation_file); - fatal("DICTIONARY: attempted to release item without references: '%s'", namevalue_get_name(nv)); + if(unlikely(is_dictionary_single_threaded(dict))) { + is_deleted = item->flags & ITEM_FLAG_DELETED; + refcount = --item->refcount; } + else { + // get the flags before decrementing any reference counters + // (the other way around may lead to use-after-free) + is_deleted = item_flag_check(item, ITEM_FLAG_DELETED); - if(refcount == 1) { - if((nv->flags & NAME_VALUE_FLAG_DELETED)) - DICTIONARY_STATS_PENDING_DELETES_PLUS1(dict); + // decrement the refcount + refcount = __atomic_sub_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST); + } + + if(refcount < 0) { + internal_error( + true, + "DICTIONARY: attempted to release item without references (refcount = %d): " + "'%s' on dictionary created by %s() (%zu@%s)", + refcount + 1, + item_get_name(item), + dict->creation_function, + dict->creation_line, + dict->creation_file); + + fatal( + "DICTIONARY: attempted to release item '%s' without references (refcount = %d)", + item_get_name(item), + refcount + 1); + } + + if(refcount == 0) { + + if(is_deleted) + DICTIONARY_PENDING_DELETES_PLUS1(dict); // referenced items counts number of unique items referenced // so, we decrease it only when refcount == 0 - DICTIONARY_STATS_REFERENCED_ITEMS_MINUS1(dict); + DICTIONARY_REFERENCED_ITEMS_MINUS1(dict); } +} + +static int item_check_and_acquire_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item, bool having_index_lock) { + size_t spins = 0; + REFCOUNT refcount, desired; + + int ret = RC_ITEM_OK; + + do { + spins++; + + refcount = DICTIONARY_ITEM_REFCOUNT_GET(dict, item); + + if(refcount < 0) { + // we can't use this item + ret = RC_ITEM_IS_CURRENTLY_BEING_DELETED; + break; + } + + if(item_flag_check(item, ITEM_FLAG_DELETED)) { + // we can't use this item + ret = RC_ITEM_MARKED_FOR_DELETION; + break; + } + + desired = refcount + 1; + + } while(!__atomic_compare_exchange_n(&item->refcount, &refcount, desired, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)); + + // if ret == ITEM_OK, we acquired the item + + if(ret == RC_ITEM_OK) { + if (is_view_dictionary(dict) && + item_shared_flag_check(item, ITEM_FLAG_DELETED) && + !item_flag_check(item, ITEM_FLAG_DELETED)) { + // but, we can't use this item + + if (having_index_lock) { + // delete it from the hashtable + if(hashtable_delete_unsafe(dict, item_get_name(item), item->key_len, item) == 0) + error("DICTIONARY: INTERNAL ERROR VIEW: tried to delete item with name '%s', name_len %u that is not in the index", item_get_name(item), (KEY_LEN_TYPE)(item->key_len - 1)); + else + pointer_del(dict, item); + + // mark it in our dictionary as deleted too + // this is safe to be done here, because we have got + // a reference counter on item + dict_item_set_deleted(dict, item); + + // decrement the refcount we incremented above + if (__atomic_sub_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST) == 0) { + // this is a deleted item, and we are the last one + DICTIONARY_PENDING_DELETES_PLUS1(dict); + } + + // do not touch the item below this point + } else { + // this is traversal / walkthrough + // decrement the refcount we incremented above + __atomic_sub_fetch(&item->refcount, 1, __ATOMIC_SEQ_CST); + } - if(can_get_write_lock && DICTIONARY_STATS_PENDING_DELETES_GET(dict)) { - // we can garbage collect now + return RC_ITEM_MARKED_FOR_DELETION; + } - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - garbage_collect_pending_deletes_unsafe(dict); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + if(desired == 1) + DICTIONARY_REFERENCED_ITEMS_PLUS1(dict); } - return refcount; + + if(unlikely(spins > 1 && dict->stats)) + DICTIONARY_STATS_CHECK_SPINS_PLUS(dict, spins - 1); + + return ret; } -// ---------------------------------------------------------------------------- -// hash table +// if a dictionary item can be deleted, return true, otherwise return false +// we use the private reference counter +static inline int item_is_not_referenced_and_can_be_removed_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item) { + // if we can set refcount to REFCOUNT_DELETING, we can delete this item -#ifdef DICTIONARY_WITH_AVL -static inline const char *namevalue_get_name(NAME_VALUE *nv); + size_t spins = 0; + REFCOUNT refcount, desired = REFCOUNT_DELETING; -static int name_value_compare(void* a, void* b) { - return strcmp(namevalue_get_name((NAME_VALUE *)a), namevalue_get_name((NAME_VALUE *)b)); -} + int ret = RC_ITEM_OK; -static void *get_thread_static_name_value(const char *name) { - static __thread NAME_VALUE tmp = { 0 }; - tmp.flags = NAME_VALUE_FLAG_NONE; - tmp.caller_name = (char *)name; - return &tmp; -} + do { + spins++; -static void hashtable_init_unsafe(DICTIONARY *dict) { - avl_init(&dict->values_index, name_value_compare); - dict->get_thread_static_name_value = get_thread_static_name_value; -} + refcount = DICTIONARY_ITEM_REFCOUNT_GET(dict, item); -static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { - (void)dict; - return 0; -} + if(refcount < 0) { + // we can't use this item + ret = RC_ITEM_IS_CURRENTLY_BEING_DELETED; + break; + } -static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *nv) { - (void)name; - (void)name_len; + if(refcount > 0) { + // we can't delete this + ret = RC_ITEM_IS_REFERENCED; + break; + } - if(unlikely(avl_remove(&(dict->values_index), (avl_t *)(nv)) != (avl_t *)nv)) - return 0; + if(item_flag_check(item, ITEM_FLAG_BEING_CREATED)) { + // we can't use this item + ret = RC_ITEM_IS_CURRENTLY_BEING_CREATED; + break; + } + } while(!__atomic_compare_exchange_n(&item->refcount, &refcount, desired, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)); - return 1; -} +#ifdef NETDATA_INTERNAL_CHECKS + if(ret == RC_ITEM_OK) + item->deleter_pid = gettid(); +#endif -static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - (void)name_len; + if(unlikely(spins > 1 && dict->stats)) + DICTIONARY_STATS_DELETE_SPINS_PLUS(dict, spins - 1); - void *tmp = dict->get_thread_static_name_value(name); - return (NAME_VALUE *)avl_search(&(dict->values_index), (avl_t *)tmp); + return ret; } -static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - // AVL needs a NAME_VALUE to insert into the dictionary but we don't have it yet. - // So, the only thing we can do, is return an existing one if it is already there. - // Returning NULL will make the caller thing we added it, will allocate one - // and will call hashtable_inserted_name_value_unsafe(), at which we will do - // the actual indexing. +// if a dictionary item can be freed, return true, otherwise return false +// we use the shared reference counter +static inline bool item_shared_release_and_check_if_it_can_be_freed(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item) { + // if we can set refcount to REFCOUNT_DELETING, we can delete this item - dict->hash_base = hashtable_get_unsafe(dict, name, name_len); - return &dict->hash_base; -} + REFCOUNT links = __atomic_sub_fetch(&item->shared->links, 1, __ATOMIC_SEQ_CST); + if(links == 0 && __atomic_compare_exchange_n(&item->shared->links, &links, REFCOUNT_DELETING, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { -static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, void *nv) { - // we have our new NAME_VALUE object. - // Let's index it. + // we can delete it + return true; + } - if(unlikely(avl_insert(&((dict)->values_index), (avl_t *)(nv)) != (avl_t *)nv)) - error("dictionary: INTERNAL ERROR: duplicate insertion to dictionary."); + // we can't delete it + return false; } -#endif -#ifdef DICTIONARY_WITH_JUDYHS -static void hashtable_init_unsafe(DICTIONARY *dict) { - dict->JudyHSArray = NULL; + +// ---------------------------------------------------------------------------- +// hash table operations + +static size_t hashtable_init_unsafe(DICTIONARY *dict) { + dict->index.JudyHSArray = NULL; + return 0; } static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { - if(unlikely(!dict->JudyHSArray)) return 0; + if(unlikely(!dict->index.JudyHSArray)) return 0; + + pointer_destroy_index(dict); JError_t J_Error; - Word_t ret = JudyHSFreeArray(&dict->JudyHSArray, &J_Error); + Word_t ret = JudyHSFreeArray(&dict->index.JudyHSArray, &J_Error); if(unlikely(ret == (Word_t) JERR)) { error("DICTIONARY: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); @@ -558,17 +1089,15 @@ static size_t hashtable_destroy_unsafe(DICTIONARY *dict) { debug(D_DICTIONARY, "Dictionary: hash table freed %lu bytes", ret); - dict->JudyHSArray = NULL; + dict->index.JudyHSArray = NULL; return (size_t)ret; } -static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: inserting item from the index without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); - +static inline void **hashtable_insert_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { JError_t J_Error; - Pvoid_t *Rc = JudyHSIns(&dict->JudyHSArray, (void *)name, name_len, &J_Error); + Pvoid_t *Rc = JudyHSIns(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); if (unlikely(Rc == PJERR)) { - fatal("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", + error("DICTIONARY: Cannot insert entry with name '%s' to JudyHS, JU_ERRNO_* == %u, ID == %d", name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); } @@ -579,17 +1108,15 @@ static inline NAME_VALUE **hashtable_insert_unsafe(DICTIONARY *dict, const char // 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 (NAME_VALUE **)Rc; + return Rc; } -static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *nv) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: deleting item from the index without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); - - (void)nv; - if(unlikely(!dict->JudyHSArray)) return 0; +static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *item) { + (void)item; + if(unlikely(!dict->index.JudyHSArray)) return 0; JError_t J_Error; - int ret = JudyHSDel(&dict->JudyHSArray, (void *)name, name_len, &J_Error); + int ret = JudyHSDel(&dict->index.JudyHSArray, (void *)name, name_len, &J_Error); if(unlikely(ret == JERR)) { error("DICTIONARY: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d", name, JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); @@ -609,16 +1136,17 @@ static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, si } } -static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { - if(unlikely(!dict->JudyHSArray)) return NULL; +static inline DICTIONARY_ITEM *hashtable_get_unsafe(DICTIONARY *dict, const char *name, size_t name_len) { + if(unlikely(!dict->index.JudyHSArray)) return NULL; DICTIONARY_STATS_SEARCHES_PLUS1(dict); Pvoid_t *Rc; - Rc = JudyHSGet(dict->JudyHSArray, (void *)name, name_len); + Rc = JudyHSGet(dict->index.JudyHSArray, (void *)name, name_len); if(likely(Rc)) { // found in the hash table - return (NAME_VALUE *)*Rc; + pointer_check(dict, (DICTIONARY_ITEM *)*Rc); + return (DICTIONARY_ITEM *)*Rc; } else { // not found in the hash table @@ -626,345 +1154,419 @@ static inline NAME_VALUE *hashtable_get_unsafe(DICTIONARY *dict, const char *nam } } -static inline void hashtable_inserted_name_value_unsafe(DICTIONARY *dict, void *nv) { +static inline void hashtable_inserted_item_unsafe(DICTIONARY *dict, void *item) { (void)dict; - (void)nv; + (void)item; + + // this is called just after an item is successfully inserted to the hashtable + // we don't need this for judy, but we may need it if we integrate more hash tables + ; } -#endif // DICTIONARY_WITH_JUDYHS - // ---------------------------------------------------------------------------- // linked list management -static inline void linkedlist_namevalue_link_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: adding item to the linked-list without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); +static inline void item_linked_list_add(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); - if (unlikely(!dict->first_item)) { - // we are the only ones here - nv->next = NULL; - nv->prev = NULL; - dict->first_item = dict->last_item = nv; - return; - } + if(dict->options & DICT_OPTION_ADD_IN_FRONT) + DOUBLE_LINKED_LIST_PREPEND_UNSAFE(dict->items.list, item, prev, next); + else + DOUBLE_LINKED_LIST_APPEND_UNSAFE(dict->items.list, item, prev, next); - if(dict->flags & DICTIONARY_FLAG_ADD_IN_FRONT) { - // add it at the beginning - nv->prev = NULL; - nv->next = dict->first_item; +#ifdef NETDATA_INTERNAL_CHECKS + item->ll_adder_pid = gettid(); +#endif - if (likely(nv->next)) nv->next->prev = nv; - dict->first_item = nv; - } - else { - // add it at the end - nv->next = NULL; - nv->prev = dict->last_item; + // clear the BEING created flag, + // after it has been inserted into the linked list + item_flag_clear(item, ITEM_FLAG_BEING_CREATED); - if (likely(nv->prev)) nv->prev->next = nv; - dict->last_item = nv; - } + garbage_collect_pending_deletes(dict); + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); } -static inline void linkedlist_namevalue_unlink_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: removing item from the linked-list without exclusive access to the dictionary created by %s() (%zu@%s)", dict->creation_function, dict->creation_line, dict->creation_file); +static inline void item_linked_list_remove(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + DOUBLE_LINKED_LIST_REMOVE_UNSAFE(dict->items.list, item, prev, next); - if(nv->next) nv->next->prev = nv->prev; - if(nv->prev) nv->prev->next = nv->next; - if(dict->first_item == nv) dict->first_item = nv->next; - if(dict->last_item == nv) dict->last_item = nv->prev; +#ifdef NETDATA_INTERNAL_CHECKS + item->ll_remover_pid = gettid(); +#endif + + garbage_collect_pending_deletes(dict); + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); } // ---------------------------------------------------------------------------- -// NAME_VALUE methods +// ITEM initialization and updates -static inline size_t namevalue_set_name(DICTIONARY *dict, NAME_VALUE *nv, const char *name, size_t name_len) { - if(likely(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE)) { - nv->caller_name = (char *)name; - return 0; +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) + 1; + item->options |= ITEM_OPTION_ALLOCATED_NAME; } - nv->string_name = string_strdupz(name); - nv->flags |= NAME_VALUE_FLAG_NAME_IS_ALLOCATED; - return name_len; + return item->key_len; } -static inline size_t namevalue_free_name(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE))) - string_freez(nv->string_name); +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 0; + return item->key_len; } -static inline const char *namevalue_get_name(NAME_VALUE *nv) { - if(nv->flags & NAME_VALUE_FLAG_NAME_IS_ALLOCATED) - return string2str(nv->string_name); +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 nv->caller_name; + return item->caller_name; } -static NAME_VALUE *namevalue_create_unsafe(DICTIONARY *dict, const char *name, size_t name_len, void *value, size_t value_len) { - debug(D_DICTIONARY, "Creating name value entry for name '%s'.", 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); +} - size_t size = sizeof(NAME_VALUE); - NAME_VALUE *nv = mallocz(size); - size_t allocated = size; +static 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 = callocz(1, size); #ifdef NETDATA_INTERNAL_CHECKS - nv->dict = dict; + item->creator_pid = gettid(); #endif - nv->refcount = 0; - nv->flags = NAME_VALUE_FLAG_NONE; - nv->value_len = value_len; + item->refcount = 1; + item->flags = ITEM_FLAG_BEING_CREATED; + + *allocated_bytes += size; - allocated += namevalue_set_name(dict, nv, name, name_len); + if(master_item) { + item->shared = master_item->shared; - if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) - nv->value = value; + if(unlikely(__atomic_add_fetch(&item->shared->links, 1, __ATOMIC_SEQ_CST) <= 1)) + fatal("DICTIONARY: attempted to link to a shared item structure that had zero references"); + } else { - if(likely(value_len)) { - if (value) { - // a value has been supplied - // copy it - nv->value = mallocz(value_len); - memcpy(nv->value, value, value_len); - } - else { - // no value has been supplied - // allocate a clear memory block - nv->value = callocz(1, value_len); - } + size = sizeof(DICTIONARY_ITEM_SHARED); + item->shared = callocz(1, size); + item->shared->links = 1; + *allocated_bytes += size; + } + +#ifdef NETDATA_INTERNAL_CHECKS + item->dict = dict; +#endif + return item; +} + +static void *dict_item_value_create(void *value, size_t value_len) { + void *ptr = NULL; + + if(likely(value_len)) { + if (likely(value)) { + // a value has been supplied + // copy it + ptr = mallocz(value_len); + memcpy(ptr, value, value_len); } else { - // the caller wants an item without any value - nv->value = NULL; + // no value has been supplied + // allocate a clear memory block + ptr = callocz(1, value_len); } + } + // else + // the caller wants an item without any value + + return ptr; +} + +static 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 - allocated += value_len; + 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 - DICTIONARY_STATS_ENTRIES_PLUS1(dict, allocated); + if(unlikely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) + item->shared->value = value; + else + item->shared->value = dict_item_value_create(value, value_len); + + item->shared->value_len = value_len; + value_size += value_len; + + dictionary_execute_insert_callback(dict, item, constructor_data); + } - if(dict->ins_callback) - dict->ins_callback(namevalue_get_name(nv), nv->value, dict->ins_callback_data); + DICTIONARY_ENTRIES_PLUS1(dict); + DICTIONARY_STATS_PLUS_MEMORY(dict, key_size, item_size, value_size); - return nv; + return item; } -static void namevalue_reset_unsafe(DICTIONARY *dict, NAME_VALUE *nv, void *value, size_t value_len) { - debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", namevalue_get_name(nv)); +static void dict_item_reset_value_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item, void *value, size_t value_len, void *constructor_data) { + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: %s() should never be called on views.", __FUNCTION__ ); + + debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", item_get_name(item)); + + DICTIONARY_VALUE_RESETS_PLUS1(dict); - DICTIONARY_STATS_VALUE_RESETS_PLUS1(dict, nv->value_len, value_len); + if(item->shared->value_len != value_len) { + DICTIONARY_STATS_PLUS_MEMORY(dict, 0, 0, value_len); + DICTIONARY_STATS_MINUS_MEMORY(dict, 0, 0, item->shared->value_len); + } - if(dict->del_callback) - dict->del_callback(namevalue_get_name(nv), nv->value, dict->del_callback_data); + dictionary_execute_delete_callback(dict, item); - if(likely(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) { - debug(D_DICTIONARY, "Dictionary: linking value to '%s'", namevalue_get_name(nv)); - nv->value = value; - nv->value_len = value_len; + if(likely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) { + debug(D_DICTIONARY, "Dictionary: linking value to '%s'", item_get_name(item)); + item->shared->value = value; + item->shared->value_len = value_len; } else { - debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", namevalue_get_name(nv)); + debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", item_get_name(item)); - void *oldvalue = nv->value; - void *newvalue = NULL; + void *old_value = item->shared->value; + void *new_value = NULL; if(value_len) { - newvalue = mallocz(value_len); - if(value) memcpy(newvalue, value, value_len); - else memset(newvalue, 0, value_len); + new_value = mallocz(value_len); + if(value) memcpy(new_value, value, value_len); + else memset(new_value, 0, value_len); } - nv->value = newvalue; - nv->value_len = value_len; + item->shared->value = new_value; + item->shared->value_len = value_len; - debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", namevalue_get_name(nv)); - freez(oldvalue); + debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", item_get_name(item)); + freez(old_value); } - if(dict->ins_callback) - dict->ins_callback(namevalue_get_name(nv), nv->value, dict->ins_callback_data); + dictionary_execute_insert_callback(dict, item, constructor_data); } -static size_t namevalue_destroy_unsafe(DICTIONARY *dict, NAME_VALUE *nv) { - debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", namevalue_get_name(nv)); +static size_t dict_item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item) { + debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", item_get_name(item)); - if(dict->del_callback) - dict->del_callback(namevalue_get_name(nv), nv->value, dict->del_callback_data); + if(!item_flag_check(item, ITEM_FLAG_DELETED)) + DICTIONARY_ENTRIES_MINUS1(dict); - size_t freed = 0; + size_t item_size = 0, key_size = 0, value_size = 0; - if(unlikely(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE))) { - debug(D_DICTIONARY, "Dictionary freeing value of '%s'", namevalue_get_name(nv)); - freez(nv->value); - freed += nv->value_len; - } + key_size += item->key_len; + if(unlikely(!(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE))) + item_free_name(dict, item); - if(unlikely(!(dict->flags & DICTIONARY_FLAG_NAME_LINK_DONT_CLONE))) { - debug(D_DICTIONARY, "Dictionary freeing name '%s'", namevalue_get_name(nv)); - freed += namevalue_free_name(dict, nv); + if(item_shared_release_and_check_if_it_can_be_freed(dict, item)) { + dictionary_execute_delete_callback(dict, item); + + if(unlikely(!(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE))) { + debug(D_DICTIONARY, "Dictionary freeing value of '%s'", item_get_name(item)); + freez(item->shared->value); + item->shared->value = NULL; + } + value_size += item->shared->value_len; + + freez(item->shared); + item->shared = NULL; + item_size += sizeof(DICTIONARY_ITEM_SHARED); } - freez(nv); - freed += sizeof(NAME_VALUE); + freez(item); + item_size += sizeof(DICTIONARY_ITEM); - DICTIONARY_STATS_ENTRIES_MINUS_MEMORY(dict, freed); + DICTIONARY_STATS_MINUS_MEMORY(dict, key_size, item_size, value_size); - return freed; + // we return the memory we actually freed + return item_size + ((dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE) ? 0 : value_size); } -// if a dictionary item can be deleted, return true, otherwise return false -static bool name_value_can_be_deleted(DICTIONARY *dict, NAME_VALUE *nv) { - if(unlikely(dict->flags & DICTIONARY_FLAG_DEFER_ALL_DELETIONS)) - return false; +// ---------------------------------------------------------------------------- +// item operations - if(unlikely(DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv) > 0)) - return false; +static void dict_item_shared_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(is_master_dictionary(dict)) { + item_shared_flag_set(item, ITEM_FLAG_DELETED); - return true; + if(dict->hooks) + __atomic_store_n(&dict->hooks->last_master_deletion_us, now_realtime_usec(), __ATOMIC_SEQ_CST); + } } -// ---------------------------------------------------------------------------- -// API - dictionary management -#ifdef NETDATA_INTERNAL_CHECKS -DICTIONARY *dictionary_create_advanced_with_trace(DICTIONARY_FLAGS flags, size_t scratchpad_size, const char *function, size_t line, const char *file) { -#else -DICTIONARY *dictionary_create_advanced(DICTIONARY_FLAGS flags, size_t scratchpad_size) { -#endif - debug(D_DICTIONARY, "Creating dictionary."); +// returns true if we set the deleted flag on this item +static bool dict_item_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ITEM_FLAGS expected, desired; - if(unlikely(flags & DICTIONARY_FLAGS_RESERVED)) - flags &= ~DICTIONARY_FLAGS_RESERVED; + do { + expected = __atomic_load_n(&item->flags, __ATOMIC_SEQ_CST); - DICTIONARY *dict = callocz(1, sizeof(DICTIONARY) + scratchpad_size); - size_t allocated = sizeof(DICTIONARY) + scratchpad_size; + if (expected & ITEM_FLAG_DELETED) + return false; - dict->scratchpad_size = scratchpad_size; - dict->flags = flags; - dict->first_item = dict->last_item = NULL; + desired = expected | ITEM_FLAG_DELETED; - allocated += dictionary_lock_init(dict); - allocated += reference_counter_init(dict); - dict->memory = (long)allocated; + } while(!__atomic_compare_exchange_n(&item->flags, &expected, desired, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)); - hashtable_init_unsafe(dict); + DICTIONARY_ENTRIES_MINUS1(dict); + return true; +} -#ifdef NETDATA_INTERNAL_CHECKS - dict->creation_function = function; - dict->creation_file = file; - dict->creation_line = line; -#endif +static inline void dict_item_free_or_mark_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + int rc = item_is_not_referenced_and_can_be_removed_advanced(dict, item); + switch(rc) { + case RC_ITEM_OK: + // the item is ours, refcount set to -100 + dict_item_shared_set_deleted(dict, item); + item_linked_list_remove(dict, item); + dict_item_free_with_hooks(dict, item); + break; - return (DICTIONARY *)dict; -} + case RC_ITEM_IS_REFERENCED: + case RC_ITEM_IS_CURRENTLY_BEING_CREATED: + // the item is currently referenced by others + dict_item_shared_set_deleted(dict, item); + dict_item_set_deleted(dict, item); + // after this point do not touch the item + break; -void *dictionary_scratchpad(DICTIONARY *dict) { - return &dict->scratchpad; -} + case RC_ITEM_IS_CURRENTLY_BEING_DELETED: + // an item that is currently being deleted by someone else - don't touch it + break; -size_t dictionary_destroy(DICTIONARY *dict) { - if(!dict) return 0; + default: + internal_error(true, "Hey dev! You forgot to add the new condition here!"); + break; + } +} - NAME_VALUE *nv; +// this is used by traversal functions to remove the current item +// if it is deleted and it has zero references. This will eliminate +// the need for the garbage collector to kick-in later. +// Most deletions happen during traversal, so this is a nice hack +// to speed up everything! +static inline void dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(DICTIONARY *dict, DICTIONARY_ITEM *item, char rw) { + if(rw == DICTIONARY_LOCK_WRITE) { + bool should_be_deleted = item_flag_check(item, ITEM_FLAG_DELETED); - debug(D_DICTIONARY, "Destroying dictionary."); + item_release(dict, item); - long referenced_items = 0; - size_t retries = 0; - do { - referenced_items = __atomic_load_n(&dict->referenced_items, __ATOMIC_SEQ_CST); - if (referenced_items) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - - // there are referenced items - // delete all items individually, so that only the referenced will remain - NAME_VALUE *nv_next; - for (nv = dict->first_item; nv; nv = nv_next) { - nv_next = nv->next; - size_t refcount = DICTIONARY_NAME_VALUE_REFCOUNT_GET(nv); - if (!refcount && !(nv->flags & NAME_VALUE_FLAG_DELETED)) - dictionary_del_unsafe(dict, namevalue_get_name(nv)); - } + if(should_be_deleted && item_is_not_referenced_and_can_be_removed(dict, item)) { + // this has to be before removing from the linked list, + // otherwise the garbage collector will also kick in! + DICTIONARY_PENDING_DELETES_MINUS1(dict); - internal_error( - retries == 0, - "DICTIONARY: waiting (try %zu) for destruction of dictionary created from %s() %zu@%s, because it has %ld referenced items in it (%ld total).", - retries + 1, - dict->creation_function, - dict->creation_line, - dict->creation_file, - referenced_items, - dict->entries); - - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - sleep_usec(10000); + item_linked_list_remove(dict, item); + dict_item_free_with_hooks(dict, item); } - } while(referenced_items > 0 && ++retries < 10); - - if(referenced_items) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); + } + else { + // we can't do anything under this mode + item_release(dict, item); + } +} - dict->flags |= DICTIONARY_FLAG_DESTROYED; +static bool dict_item_del(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!name || !*name)) { internal_error( true, - "DICTIONARY: delaying destruction of dictionary created from %s() %zu@%s after %zu retries, because it has %ld referenced items in it (%ld total).", + "DICTIONARY: attempted to %s() without a name on a dictionary created from %s() %zu@%s.", + __FUNCTION__, dict->creation_function, dict->creation_line, - dict->creation_file, - retries, - referenced_items, - dict->entries); + dict->creation_file); + return false; + } - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - return 0; + if(unlikely(is_dictionary_destroyed(dict))) { + internal_error(true, "DICTIONARY: attempted to dictionary_del() on a destroyed dictionary"); + return false; } - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); + if(name_len == -1) + name_len = (ssize_t)strlen(name) + 1; // we need the terminating null too - size_t freed = 0; - nv = dict->first_item; - while (nv) { - // cache nv->next - // because we are going to free nv - NAME_VALUE *nv_next = nv->next; - freed += namevalue_destroy_unsafe(dict, nv); - nv = nv_next; - // to speed up destruction, we don't - // unlink nv from the linked-list here - } + debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); - dict->first_item = NULL; - dict->last_item = NULL; + // Unfortunately, the JudyHSDel() does not return the value of the + // item that was deleted, so we have to find it before we delete it, + // since we need to release our structures too. - // destroy the dictionary - freed += hashtable_destroy_unsafe(dict); + dictionary_index_lock_wrlock(dict); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - freed += dictionary_lock_free(dict); - freed += reference_counter_free(dict); - freed += sizeof(DICTIONARY) + dict->scratchpad_size; - freez(dict); + int ret; + DICTIONARY_ITEM *item = hashtable_get_unsafe(dict, name, name_len); + if(unlikely(!item)) { + dictionary_index_wrlock_unlock(dict); + ret = false; + } + else { + if(hashtable_delete_unsafe(dict, name, name_len, item) == 0) + error("DICTIONARY: INTERNAL ERROR: tried to delete item with name '%s', name_len %zd that is not in the index", name, name_len - 1); + else + pointer_del(dict, item); - return freed; -} + dictionary_index_wrlock_unlock(dict); -// ---------------------------------------------------------------------------- -// helpers + dict_item_free_or_mark_deleted(dict, item); + ret = true; + } -static NAME_VALUE *dictionary_set_name_value_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - if(unlikely(!name)) { - internal_error(true, "DICTIONARY: attempted to dictionary_set() a dictionary item without a name"); + return ret; +} + +static DICTIONARY_ITEM *dict_item_add_or_reset_value_and_acquire(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data, DICTIONARY_ITEM *master_item) { + if(unlikely(!name || !*name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() without a name on a dictionary created from %s() %zu@%s.", + __FUNCTION__, + dict->creation_function, + dict->creation_line, + dict->creation_file); return NULL; } - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_set() on a destroyed dictionary"); return NULL; } - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: inserting dictionary item '%s' without exclusive access to dictionary", name); - - size_t name_len = strlen(name) + 1; // we need the terminating null too + if(name_len == -1) + name_len = (ssize_t)strlen(name) + 1; // we need the terminating null too debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); @@ -979,264 +1581,618 @@ static NAME_VALUE *dictionary_set_name_value_unsafe(DICTIONARY *dict, const char // But the caller has the option to do this on his/her own. // So, let's do the fastest here and let the caller decide the flow of calls. - NAME_VALUE *nv, **pnv = hashtable_insert_unsafe(dict, name, name_len); - if(likely(*pnv == 0)) { - // a new item added to the index - nv = *pnv = namevalue_create_unsafe(dict, name, name_len, value, value_len); - hashtable_inserted_name_value_unsafe(dict, nv); - linkedlist_namevalue_link_unsafe(dict, nv); - nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; - } - else { - // the item is already in the index - // so, either we will return the old one - // or overwrite the value, depending on dictionary flags + dictionary_index_lock_wrlock(dict); - nv = *pnv; + bool added_or_updated = false; + size_t spins = 0; + DICTIONARY_ITEM *item = NULL; + do { + DICTIONARY_ITEM **item_pptr = (DICTIONARY_ITEM **)hashtable_insert_unsafe(dict, name, name_len); + if (likely(*item_pptr == NULL)) { + // a new item added to the index - if(!(dict->flags & DICTIONARY_FLAG_DONT_OVERWRITE_VALUE)) { - namevalue_reset_unsafe(dict, nv, value, value_len); - nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; - } + // create the dictionary item + item = *item_pptr = + dict_item_create_with_hooks(dict, name, name_len, value, value_len, constructor_data, master_item); - else if(dict->conflict_callback) { - dict->conflict_callback(namevalue_get_name(nv), nv->value, value, dict->conflict_callback_data); - nv->flags |= NAME_VALUE_FLAG_NEW_OR_UPDATED; - } + pointer_add(dict, item); + + // call the hashtable react + hashtable_inserted_item_unsafe(dict, item); + + // unlock the index lock, before we add it to the linked list + // DONT DO IT THE OTHER WAY AROUND - DO NOT CROSS THE LOCKS! + dictionary_index_wrlock_unlock(dict); + + item_linked_list_add(dict, item); + added_or_updated = true; + } else { - // make sure this flag is not set - nv->flags &= ~NAME_VALUE_FLAG_NEW_OR_UPDATED; + pointer_check(dict, *item_pptr); + + if(item_check_and_acquire_advanced(dict, *item_pptr, true) != RC_ITEM_OK) { + spins++; + continue; + } + + // the item is already in the index + // so, either we will return the old one + // or overwrite the value, depending on dictionary flags + + // We should not compare the values here! + // even if they are the same, we have to do the whole job + // so that the callbacks will be called. + + item = *item_pptr; + + if(is_view_dictionary(dict)) { + // view dictionary + // the item is already there and can be used + if(item->shared != master_item->shared) + error("DICTIONARY: changing the master item on a view is not supported. The previous item will remain. To change the key of an item in a view, delete it and add it again."); + } + else { + // master dictionary + // the user wants to reset its value + + if (!(dict->options & DICT_OPTION_DONT_OVERWRITE_VALUE)) { + dict_item_reset_value_with_hooks(dict, item, value, value_len, constructor_data); + added_or_updated = true; + } + + else if (dictionary_execute_conflict_callback(dict, item, value, constructor_data)) { + dictionary_version_increment(dict); + added_or_updated = true; + } + + else { + // conflict callback returned false + // we did really nothing! + ; + } + } + + dictionary_index_wrlock_unlock(dict); } - } + } while(!item); + + + if(unlikely(spins > 0 && dict->stats)) + DICTIONARY_STATS_INSERT_SPINS_PLUS(dict, spins); - return nv; + if(is_master_dictionary(dict) && added_or_updated) + dictionary_execute_react_callback(dict, item, constructor_data); + + return item; } -static NAME_VALUE *dictionary_get_name_value_unsafe(DICTIONARY *dict, const char *name) { - if(unlikely(!name)) { - internal_error(true, "attempted to dictionary_get() without a name"); +static DICTIONARY_ITEM *dict_item_find_and_acquire(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!name || !*name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() without a name on a dictionary created from %s() %zu@%s.", + __FUNCTION__, + dict->creation_function, + dict->creation_line, + dict->creation_file); return NULL; } - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_get() on a destroyed dictionary"); return NULL; } - size_t name_len = strlen(name) + 1; // we need the terminating null too + if(name_len == -1) + name_len = (ssize_t)strlen(name) + 1; // we need the terminating null too debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name); - NAME_VALUE *nv = hashtable_get_unsafe(dict, name, name_len); - if(unlikely(!nv)) { - debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); - return NULL; + dictionary_index_lock_rdlock(dict); + + DICTIONARY_ITEM *item = hashtable_get_unsafe(dict, name, name_len); + if(unlikely(item && !item_check_and_acquire(dict, item))) { + item = NULL; + DICTIONARY_STATS_SEARCH_IGNORES_PLUS1(dict); } - debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); - return nv; + dictionary_index_rdlock_unlock(dict); + + return item; } // ---------------------------------------------------------------------------- -// API - items management +// delayed destruction of dictionaries + +static bool dictionary_free_all_resources(DICTIONARY *dict, size_t *mem, bool force) { + if(mem) + *mem = 0; + + if(!force && dictionary_referenced_items(dict)) + return false; + + size_t dict_size = 0, counted_items = 0, item_size = 0, index_size = 0; + (void)counted_items; + +#ifdef NETDATA_INTERNAL_CHECKS + long int entries = dict->entries; + long int referenced_items = dict->referenced_items; + long int pending_deletion_items = dict->pending_deletion_items; + const char *creation_function = dict->creation_function; + const char *creation_file = dict->creation_file; + size_t creation_line = dict->creation_line; +#endif + + // destroy the index + dictionary_index_lock_wrlock(dict); + index_size += hashtable_destroy_unsafe(dict); + dictionary_index_wrlock_unlock(dict); + + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + DICTIONARY_ITEM *item = dict->items.list; + while (item) { + // cache item->next + // because we are going to free item + DICTIONARY_ITEM *item_next = item->next; -void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); + item_size += dict_item_free_with_hooks(dict, item); + item = item_next; - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - // we need to call the react callback with a reference counter on nv - reference_counter_acquire(dict, nv); - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); - reference_counter_release(dict, nv, false); + // to speed up destruction, we don't + // unlink item from the linked-list here + + counted_items++; } + dict->items.list = NULL; + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + + dict_size += dictionary_locks_destroy(dict); + dict_size += reference_counter_free(dict); + dict_size += dictionary_hooks_free(dict); + dict_size += sizeof(DICTIONARY); + DICTIONARY_STATS_MINUS_MEMORY(dict, 0, sizeof(DICTIONARY), 0); + + freez(dict); + + internal_error( + false, + "DICTIONARY: Freed dictionary created from %s() %zu@%s, having %ld (counted %zu) entries, %ld referenced, %ld pending deletion, total freed memory: %zu bytes (sizeof(dict) = %zu, sizeof(item) = %zu).", + creation_function, + creation_line, + creation_file, + entries, counted_items, referenced_items, pending_deletion_items, + dict_size + item_size, sizeof(DICTIONARY), sizeof(DICTIONARY_ITEM) + sizeof(DICTIONARY_ITEM_SHARED)); + + if(mem) + *mem = dict_size + item_size + index_size; - return nv ? nv->value : NULL; + return true; } -void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); +netdata_mutex_t dictionaries_waiting_to_be_destroyed_mutex = NETDATA_MUTEX_INITIALIZER; +static DICTIONARY *dictionaries_waiting_to_be_destroyed = NULL; + +void dictionary_queue_for_destruction(DICTIONARY *dict) { + if(is_dictionary_destroyed(dict)) + return; - // we need to get a reference counter for the react callback - // before we unlock the dictionary - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) - reference_counter_acquire(dict, nv); + DICTIONARY_STATS_DICT_DESTROY_QUEUED_PLUS1(dict); + dict_flag_set(dict, DICT_FLAG_DESTROYED); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + netdata_mutex_lock(&dictionaries_waiting_to_be_destroyed_mutex); - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - // we got the reference counter we need, above - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); - reference_counter_release(dict, nv, false); - } + dict->next = dictionaries_waiting_to_be_destroyed; + dictionaries_waiting_to_be_destroyed = dict; - return nv ? nv->value : NULL; + netdata_mutex_unlock(&dictionaries_waiting_to_be_destroyed_mutex); } -DICTIONARY_ITEM *dictionary_set_and_acquire_item_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); +void cleanup_destroyed_dictionaries(void) { + if(!dictionaries_waiting_to_be_destroyed) + return; - if(unlikely(!nv)) - return NULL; + netdata_mutex_lock(&dictionaries_waiting_to_be_destroyed_mutex); + + DICTIONARY *dict, *last = NULL, *next = NULL; + for(dict = dictionaries_waiting_to_be_destroyed; dict ; dict = next) { + next = dict->next; - reference_counter_acquire(dict, nv); +#ifdef NETDATA_INTERNAL_CHECKS + size_t line = dict->creation_line; + const char *file = dict->creation_file; + const char *function = dict->creation_function; +#endif - if(unlikely(dict->react_callback && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); + DICTIONARY_STATS_DICT_DESTROY_QUEUED_MINUS1(dict); + if(dictionary_free_all_resources(dict, NULL, false)) { + + internal_error( + true, + "DICTIONARY: freed dictionary with delayed destruction, created from %s() %zu@%s.", + function, line, file); + + if(last) last->next = next; + else dictionaries_waiting_to_be_destroyed = next; + } + else { + DICTIONARY_STATS_DICT_DESTROY_QUEUED_PLUS1(dict); + last = dict; + } } - return (DICTIONARY_ITEM *)nv; + netdata_mutex_unlock(&dictionaries_waiting_to_be_destroyed_mutex); } -DICTIONARY_ITEM *dictionary_set_and_acquire_item(DICTIONARY *dict, const char *name, void *value, size_t value_len) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - NAME_VALUE *nv = dictionary_set_name_value_unsafe(dict, name, value, value_len); +// ---------------------------------------------------------------------------- +// API internal checks - // we need to get the reference counter before we unlock - if(nv) reference_counter_acquire(dict, nv); +#ifdef NETDATA_INTERNAL_CHECKS +#define api_internal_check(dict, item, allow_null_dict, allow_null_item) api_internal_check_with_trace(dict, item, __FUNCTION__, allow_null_dict, allow_null_item) +static inline void api_internal_check_with_trace(DICTIONARY *dict, DICTIONARY_ITEM *item, const char *function, bool allow_null_dict, bool allow_null_item) { + if(!allow_null_dict && !dict) { + internal_error( + item, + "DICTIONARY: attempted to %s() with a NULL dictionary, passing an item created from %s() %zu@%s.", + function, + item->dict->creation_function, + item->dict->creation_line, + item->dict->creation_file); + fatal("DICTIONARY: attempted to %s() but dict is NULL", function); + } - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); + if(!allow_null_item && !item) { + internal_error( + true, + "DICTIONARY: attempted to %s() without an item on a dictionary created from %s() %zu@%s.", + function, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + fatal("DICTIONARY: attempted to %s() but item is NULL", function); + } - if(unlikely(dict->react_callback && nv && (nv->flags & NAME_VALUE_FLAG_NEW_OR_UPDATED))) { - // we already have a reference counter, for the caller, no need for another one - dict->react_callback(namevalue_get_name(nv), nv->value, dict->react_callback_data); + if(dict && item && dict != item->dict) { + internal_error( + true, + "DICTIONARY: attempted to %s() an item on a dictionary created from %s() %zu@%s, but the item belongs to the dictionary created from %s() %zu@%s.", + function, + dict->creation_function, + dict->creation_line, + dict->creation_file, + item->dict->creation_function, + item->dict->creation_line, + item->dict->creation_file + ); + fatal("DICTIONARY: %s(): item does not belong to this dictionary.", function); } - return (DICTIONARY_ITEM *)nv; + if(item) { + REFCOUNT refcount = DICTIONARY_ITEM_REFCOUNT_GET(dict, item); + if (unlikely(refcount <= 0)) { + internal_error( + true, + "DICTIONARY: attempted to %s() of an item with reference counter = %d on a dictionary created from %s() %zu@%s", + function, + refcount, + item->dict->creation_function, + item->dict->creation_line, + item->dict->creation_file); + fatal("DICTIONARY: attempted to %s but item is having refcount = %d", function, refcount); + } + } } +#else +#define api_internal_check(dict, item, allow_null_dict, allow_null_item) debug_dummy() +#endif -void *dictionary_get_unsafe(DICTIONARY *dict, const char *name) { - NAME_VALUE *nv = dictionary_get_name_value_unsafe(dict, name); +#define api_is_name_good(dict, name, name_len) api_is_name_good_with_trace(dict, name, name_len, __FUNCTION__) +static bool api_is_name_good_with_trace(DICTIONARY *dict __maybe_unused, const char *name, ssize_t name_len __maybe_unused, const char *function __maybe_unused) { + if(unlikely(!name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() with name = NULL on a dictionary created from %s() %zu@%s.", + function, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + return false; + } - if(unlikely(!nv)) - return NULL; + if(unlikely(!*name)) { + internal_error( + true, + "DICTIONARY: attempted to %s() with empty name on a dictionary created from %s() %zu@%s.", + function, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + return false; + } - return nv->value; -} + internal_error( + name_len > 0 && name_len != (ssize_t)(strlen(name) + 1), + "DICTIONARY: attempted to %s() with a name of '%s', having length of %zu (incl. '\\0'), but the supplied name_len = %ld, on a dictionary created from %s() %zu@%s.", + function, + name, + strlen(name) + 1, + (long int) name_len, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); + + internal_error( + name_len <= 0 && name_len != -1, + "DICTIONARY: attempted to %s() with a name of '%s', having length of %zu (incl. '\\0'), but the supplied name_len = %ld, on a dictionary created from %s() %zu@%s.", + function, + name, + strlen(name) + 1, + (long int) name_len, + dict?dict->creation_function:"unknown", + dict?dict->creation_line:0, + dict?dict->creation_file:"unknown"); -void *dictionary_get(DICTIONARY *dict, const char *name) { - dictionary_lock(dict, DICTIONARY_LOCK_READ); - void *ret = dictionary_get_unsafe(dict, name); - dictionary_unlock(dict, DICTIONARY_LOCK_READ); - return ret; + return true; } -DICTIONARY_ITEM *dictionary_get_and_acquire_item_unsafe(DICTIONARY *dict, const char *name) { - NAME_VALUE *nv = dictionary_get_name_value_unsafe(dict, name); +// ---------------------------------------------------------------------------- +// API - dictionary management - if(unlikely(!nv)) - return NULL; +static DICTIONARY *dictionary_create_internal(DICT_OPTIONS options, struct dictionary_stats *stats) { + cleanup_destroyed_dictionaries(); - reference_counter_acquire(dict, nv); - return (DICTIONARY_ITEM *)nv; -} + DICTIONARY *dict = callocz(1, sizeof(DICTIONARY)); + dict->options = options; + dict->stats = stats; -DICTIONARY_ITEM *dictionary_get_and_acquire_item(DICTIONARY *dict, const char *name) { - dictionary_lock(dict, DICTIONARY_LOCK_READ); - void *ret = dictionary_get_and_acquire_item_unsafe(dict, name); - dictionary_unlock(dict, DICTIONARY_LOCK_READ); - return ret; -} + size_t dict_size = 0; + dict_size += sizeof(DICTIONARY); + dict_size += dictionary_locks_init(dict); + dict_size += reference_counter_init(dict); + dict_size += hashtable_init_unsafe(dict); -DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY_ITEM *item) { - if(unlikely(!item)) return NULL; - reference_counter_increase((NAME_VALUE *)item); - return item; -} + pointer_index_init(dict); -const char *dictionary_acquired_item_name(DICTIONARY_ITEM *item) { - if(unlikely(!item)) return NULL; - return namevalue_get_name((NAME_VALUE *)item); -} + DICTIONARY_STATS_PLUS_MEMORY(dict, 0, dict_size, 0); -void *dictionary_acquired_item_value(DICTIONARY_ITEM *item) { - if(unlikely(!item)) return NULL; - return ((NAME_VALUE *)item)->value; + return dict; } -void dictionary_acquired_item_release_unsafe(DICTIONARY *dict, DICTIONARY_ITEM *item) { - if(unlikely(!item)) return; +#ifdef NETDATA_INTERNAL_CHECKS +DICTIONARY *dictionary_create_advanced_with_trace(DICT_OPTIONS options, struct dictionary_stats *stats, const char *function, size_t line, const char *file) { +#else +DICTIONARY *dictionary_create_advanced(DICT_OPTIONS options, struct dictionary_stats *stats) { +#endif + + DICTIONARY *dict = dictionary_create_internal(options, stats?stats:&dictionary_stats_category_other); #ifdef NETDATA_INTERNAL_CHECKS - if(((NAME_VALUE *)item)->dict != dict) - fatal("DICTIONARY: %s(): name_value item with name '%s' does not belong to this dictionary", __FUNCTION__, namevalue_get_name((NAME_VALUE *)item)); + dict->creation_function = function; + dict->creation_file = file; + dict->creation_line = line; #endif - reference_counter_release(dict, (NAME_VALUE *)item, false); + DICTIONARY_STATS_DICT_CREATIONS_PLUS1(dict); + return dict; } -void dictionary_acquired_item_release(DICTIONARY *dict, DICTIONARY_ITEM *item) { - if(unlikely(!item)) return; +#ifdef NETDATA_INTERNAL_CHECKS +DICTIONARY *dictionary_create_view_with_trace(DICTIONARY *master, const char *function, size_t line, const char *file) { +#else +DICTIONARY *dictionary_create_view(DICTIONARY *master) { +#endif + + DICTIONARY *dict = dictionary_create_internal(master->options, master->stats); + dict->master = master; + + dictionary_hooks_allocate(master); + + if(unlikely(__atomic_load_n(&master->hooks->links, __ATOMIC_SEQ_CST)) < 1) + fatal("DICTIONARY: attempted to create a view that has %d links", master->hooks->links); + + dict->hooks = master->hooks; + __atomic_add_fetch(&master->hooks->links, 1, __ATOMIC_SEQ_CST); #ifdef NETDATA_INTERNAL_CHECKS - if(((NAME_VALUE *)item)->dict != dict) - fatal("DICTIONARY: %s(): name_value item with name '%s' does not belong to this dictionary", __FUNCTION__, namevalue_get_name((NAME_VALUE *)item)); + dict->creation_function = function; + dict->creation_file = file; + dict->creation_line = line; #endif - // no need to get a lock here - // we pass the last parameter to reference_counter_release() as true - // so that the release may get a write-lock if required to clean up + DICTIONARY_STATS_DICT_CREATIONS_PLUS1(dict); + return dict; +} - reference_counter_release(dict, (NAME_VALUE *)item, true); +void dictionary_flush(DICTIONARY *dict) { + if(unlikely(!dict)) + return; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) - dictionary_destroy(dict); + void *value; + dfe_start_write(dict, value) { + dictionary_del_advanced(dict, item_get_name(value_dfe.item), (ssize_t)item_get_name_len(value_dfe.item) + 1); + } + dfe_done(value); + + DICTIONARY_STATS_DICT_FLUSHES_PLUS1(dict); } -int dictionary_del_unsafe(DICTIONARY *dict, const char *name) { - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { - internal_error(true, "DICTIONARY: attempted to dictionary_del() on a destroyed dictionary"); - return -1; +size_t dictionary_destroy(DICTIONARY *dict) { + cleanup_destroyed_dictionaries(); + + if(!dict) return 0; + + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + dict_flag_set(dict, DICT_FLAG_DESTROYED); + DICTIONARY_STATS_DICT_DESTRUCTIONS_PLUS1(dict); + + size_t referenced_items = dictionary_referenced_items(dict); + if(referenced_items) { + dictionary_flush(dict); + dictionary_queue_for_destruction(dict); + + internal_error( + true, + "DICTIONARY: delaying destruction of dictionary created from %s() %zu@%s, because it has %ld referenced items in it (%ld total).", + dict->creation_function, + dict->creation_line, + dict->creation_file, + dict->referenced_items, + dict->entries); + + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + return 0; } - if(unlikely(!name || !*name)) { - internal_error(true, "DICTIONARY: attempted to dictionary_del() without a name"); - return -1; + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); + + size_t freed; + dictionary_free_all_resources(dict, &freed, true); + + return freed; +} + +// ---------------------------------------------------------------------------- +// SET an item to the dictionary + +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return NULL; + + api_internal_check(dict, NULL, false, true); + + if(unlikely(is_view_dictionary(dict))) + fatal("DICTIONARY: this dictionary is a view, you cannot add items other than the ones from the master dictionary."); + + DICTIONARY_ITEM *item = + dict_item_add_or_reset_value_and_acquire(dict, name, name_len, value, value_len, constructor_data, NULL); + api_internal_check(dict, item, false, false); + return item; +} + +void *dictionary_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data) { + DICTIONARY_ITEM *item = dictionary_set_and_acquire_item_advanced(dict, name, name_len, value, value_len, constructor_data); + + if(likely(item)) { + void *v = item->shared->value; + item_release(dict, item); + return v; } - internal_error(!(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS), "DICTIONARY: INTERNAL ERROR: deleting dictionary item '%s' without exclusive access to dictionary", name); + return NULL; +} + +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_view_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICTIONARY_ITEM *master_item) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return NULL; - size_t name_len = strlen(name) + 1; // we need the terminating null too + api_internal_check(dict, NULL, false, true); - debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); + if(unlikely(is_master_dictionary(dict))) + fatal("DICTIONARY: this dictionary is a master, you cannot add items from other dictionaries."); - // Unfortunately, the JudyHSDel() does not return the value of the - // item that was deleted, so we have to find it before we delete it, - // since we need to release our structures too. + dictionary_acquired_item_dup(dict->master, master_item); + DICTIONARY_ITEM *item = dict_item_add_or_reset_value_and_acquire(dict, name, name_len, NULL, 0, NULL, master_item); + dictionary_acquired_item_release(dict->master, master_item); - int ret; - NAME_VALUE *nv = hashtable_get_unsafe(dict, name, name_len); - if(unlikely(!nv)) { - debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); - ret = -1; + api_internal_check(dict, item, false, false); + return item; +} + +void *dictionary_view_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICTIONARY_ITEM *master_item) { + DICTIONARY_ITEM *item = dictionary_view_set_and_acquire_item_advanced(dict, name, name_len, master_item); + + if(likely(item)) { + void *v = item->shared->value; + item_release(dict, item); + return v; } - else { - debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); - if(hashtable_delete_unsafe(dict, name, name_len, nv) == 0) - error("DICTIONARY: INTERNAL ERROR: tried to delete item with name '%s' that is not in the index", name); + return NULL; +} - if(name_value_can_be_deleted(dict, nv)) { - linkedlist_namevalue_unlink_unsafe(dict, nv); - namevalue_destroy_unsafe(dict, nv); - } - else - nv->flags |= NAME_VALUE_FLAG_DELETED; +// ---------------------------------------------------------------------------- +// GET an item from the dictionary - ret = 0; +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_get_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return NULL; - DICTIONARY_STATS_ENTRIES_MINUS1(dict); + api_internal_check(dict, NULL, false, true); + DICTIONARY_ITEM *item = dict_item_find_and_acquire(dict, name, name_len); + api_internal_check(dict, item, false, true); + return item; +} + +void *dictionary_get_advanced(DICTIONARY *dict, const char *name, ssize_t name_len) { + DICTIONARY_ITEM *item = dictionary_get_and_acquire_item_advanced(dict, name, name_len); + if(likely(item)) { + void *v = item->shared->value; + item_release(dict, item); + return v; } - return ret; + + return NULL; } -int dictionary_del(DICTIONARY *dict, const char *name) { - dictionary_lock(dict, DICTIONARY_LOCK_WRITE); - int ret = dictionary_del_unsafe(dict, name); - dictionary_unlock(dict, DICTIONARY_LOCK_WRITE); - return ret; +// ---------------------------------------------------------------------------- +// DUP/REL an item (increase/decrease its reference counter) + +DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item) { + // we allow the item to be NULL here + api_internal_check(dict, item, false, true); + + if(likely(item)) { + item_acquire(dict, item); + api_internal_check(dict, item, false, false); + } + + return item; +} + +void dictionary_acquired_item_release(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item) { + // we allow the item to be NULL here + api_internal_check(dict, item, false, true); + + // no need to get a lock here + // we pass the last parameter to reference_counter_release() as true + // so that the release may get a write-lock if required to clean up + + if(likely(item)) + item_release(dict, item); +} + +// ---------------------------------------------------------------------------- +// get the name/value of an item + +const char *dictionary_acquired_item_name(DICT_ITEM_CONST DICTIONARY_ITEM *item) { + return item_get_name(item); +} + +void *dictionary_acquired_item_value(DICT_ITEM_CONST DICTIONARY_ITEM *item) { + if(likely(item)) + return item->shared->value; + + return NULL; +} + +size_t dictionary_acquired_item_references(DICT_ITEM_CONST DICTIONARY_ITEM *item) { + if(likely(item)) + return DICTIONARY_ITEM_REFCOUNT_GET_SOLE(item); + + return 0; +} + +// ---------------------------------------------------------------------------- +// DEL an item + +bool dictionary_del_advanced(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(unlikely(!api_is_name_good(dict, name, name_len))) + return false; + + api_internal_check(dict, NULL, false, true); + return dict_item_del(dict, name, name_len); } // ---------------------------------------------------------------------------- @@ -1245,150 +2201,165 @@ int dictionary_del(DICTIONARY *dict, const char *name) { void *dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw) { if(unlikely(!dfe || !dict)) return NULL; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_foreach_start_rw() on a destroyed dictionary"); - dfe->last_item = NULL; + dfe->counter = 0; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; return NULL; } + dfe->counter = 0; dfe->dict = dict; dfe->rw = rw; - dfe->started_ut = now_realtime_usec(); - dictionary_lock(dict, dfe->rw); + ll_recursive_lock(dict, dfe->rw); - DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); + DICTIONARY_STATS_TRAVERSALS_PLUS1(dict); // get the first item from the list - NAME_VALUE *nv = dict->first_item; + DICTIONARY_ITEM *item = dict->items.list; // skip all the deleted items - while(nv && (nv->flags & NAME_VALUE_FLAG_DELETED)) - nv = nv->next; + while(item && !item_check_and_acquire(dict, item)) + item = item->next; - if(likely(nv)) { - dfe->last_item = nv; - dfe->name = (char *)namevalue_get_name(nv); - dfe->value = nv->value; - reference_counter_acquire(dict, nv); + if(likely(item)) { + dfe->item = item; + dfe->name = (char *)item_get_name(item); + dfe->value = item->shared->value; } else { - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; } + if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dfe->dict, dfe->rw); + return dfe->value; } void *dictionary_foreach_next(DICTFE *dfe) { if(unlikely(!dfe || !dfe->dict)) return NULL; - if(unlikely(dfe->dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dfe->dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary"); - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; return NULL; } + if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_lock(dfe->dict, dfe->rw); + // the item we just did - NAME_VALUE *nv = (NAME_VALUE *)dfe->last_item; + DICTIONARY_ITEM *item = dfe->item; // get the next item from the list - NAME_VALUE *nv_next = (nv) ? nv->next : NULL; + DICTIONARY_ITEM *item_next = (item) ? item->next : NULL; - // skip all the deleted items - while(nv_next && (nv_next->flags & NAME_VALUE_FLAG_DELETED)) - nv_next = nv_next->next; + // skip all the deleted items until one that can be acquired is found + while(item_next && !item_check_and_acquire(dfe->dict, item_next)) + item_next = item_next->next; - // release the old, so that it can possibly be deleted - if(likely(nv)) - reference_counter_release(dfe->dict, nv, false); + if(likely(item)) { + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dfe->dict, item, dfe->rw); + // item_release(dfe->dict, item); + } - if(likely(nv = nv_next)) { - dfe->last_item = nv; - dfe->name = (char *)namevalue_get_name(nv); - dfe->value = nv->value; - reference_counter_acquire(dfe->dict, nv); + item = item_next; + if(likely(item)) { + dfe->item = item; + dfe->name = (char *)item_get_name(item); + dfe->value = item->shared->value; + dfe->counter++; } else { - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; } + if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dfe->dict, dfe->rw); + return dfe->value; } -usec_t dictionary_foreach_done(DICTFE *dfe) { - if(unlikely(!dfe || !dfe->dict)) return 0; +void dictionary_foreach_done(DICTFE *dfe) { + if(unlikely(!dfe || !dfe->dict)) return; - if(unlikely(dfe->dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dfe->dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary"); - return 0; + return; } // the item we just did - NAME_VALUE *nv = (NAME_VALUE *)dfe->last_item; + DICTIONARY_ITEM *item = dfe->item; // release it, so that it can possibly be deleted - if(likely(nv)) - reference_counter_release(dfe->dict, nv, false); + if(likely(item)) { + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dfe->dict, item, dfe->rw); + // item_release(dfe->dict, item); + } + + if(likely(dfe->rw != DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dfe->dict, dfe->rw); - dictionary_unlock(dfe->dict, dfe->rw); dfe->dict = NULL; - dfe->last_item = NULL; + dfe->item = NULL; dfe->name = NULL; dfe->value = NULL; - - usec_t usec = now_realtime_usec() - dfe->started_ut; - dfe->started_ut = 0; - - return usec; + dfe->counter = 0; } // ---------------------------------------------------------------------------- -// API - walk through the dictionary -// the dictionary is locked for reading while this happens +// API - walk through the dictionary. +// The dictionary is locked for reading while this happens // do not use other dictionary calls while walking the dictionary - deadlock! -int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *entry, void *data), void *data) { - if(unlikely(!dict)) return 0; +int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *entry, void *data), void *data) { + if(unlikely(!dict || !callback)) return 0; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_walkthrough_rw() on a destroyed dictionary"); return 0; } - dictionary_lock(dict, rw); + ll_recursive_lock(dict, rw); DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); // written in such a way, that the callback can delete the active element int ret = 0; - NAME_VALUE *nv = dict->first_item, *nv_next; - while(nv) { + DICTIONARY_ITEM *item = dict->items.list, *item_next; + while(item) { // skip the deleted items - if(unlikely(nv->flags & NAME_VALUE_FLAG_DELETED)) { - nv = nv->next; + if(unlikely(!item_check_and_acquire(dict, item))) { + item = item->next; continue; } - // get a reference counter, so that our item will not be deleted - // while we are using it - reference_counter_acquire(dict, nv); + if(unlikely(rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_unlock(dict, rw); - int r = callback(namevalue_get_name(nv), nv->value, data); + int r = callback(item, item->shared->value, data); + + if(unlikely(rw == DICTIONARY_LOCK_REENTRANT)) + ll_recursive_lock(dict, rw); // since we have a reference counter, this item cannot be deleted // until we release the reference counter, so the pointers are there - nv_next = nv->next; - reference_counter_release(dict, nv, false); + item_next = item->next; + + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dict, item, rw); + // item_release(dict, item); if(unlikely(r < 0)) { ret = r; @@ -1397,10 +2368,10 @@ int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const c ret += r; - nv = nv_next; + item = item_next; } - dictionary_unlock(dict, rw); + ll_recursive_unlock(dict, rw); return ret; } @@ -1408,238 +2379,114 @@ int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const c // ---------------------------------------------------------------------------- // sorted walkthrough -static int dictionary_sort_compar(const void *nv1, const void *nv2) { - return strcmp(namevalue_get_name((*(NAME_VALUE **)nv1)), namevalue_get_name((*(NAME_VALUE **)nv2))); +typedef int (*qsort_compar)(const void *item1, const void *item2); + +static int dictionary_sort_compar(const void *item1, const void *item2) { + return strcmp(item_get_name((*(DICTIONARY_ITEM **)item1)), item_get_name((*(DICTIONARY_ITEM **)item2))); } -int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const char *name, void *entry, void *data), void *data) { - if(unlikely(!dict || !dict->entries)) return 0; +int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *entry, void *data), void *data, dictionary_sorted_compar compar) { + if(unlikely(!dict || !callback)) return 0; - if(unlikely(dict->flags & DICTIONARY_FLAG_DESTROYED)) { + if(unlikely(is_dictionary_destroyed(dict))) { internal_error(true, "DICTIONARY: attempted to dictionary_sorted_walkthrough_rw() on a destroyed dictionary"); return 0; } - dictionary_lock(dict, rw); - dictionary_defer_all_deletions_unsafe(dict, rw); - DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict); - size_t count = dict->entries; - NAME_VALUE **array = mallocz(sizeof(NAME_VALUE *) * count); + ll_recursive_lock(dict, rw); + size_t entries = __atomic_load_n(&dict->entries, __ATOMIC_SEQ_CST); + DICTIONARY_ITEM **array = mallocz(sizeof(DICTIONARY_ITEM *) * entries); size_t i; - NAME_VALUE *nv; - for(nv = dict->first_item, i = 0; nv && i < count ;nv = nv->next) { - if(likely(!(nv->flags & NAME_VALUE_FLAG_DELETED))) - array[i++] = nv; + DICTIONARY_ITEM *item; + for(item = dict->items.list, i = 0; item && i < entries; item = item->next) { + if(likely(item_check_and_acquire(dict, item))) + array[i++] = item; } + ll_recursive_unlock(dict, rw); - internal_error(nv != NULL, "DICTIONARY: during sorting expected to have %zu items in dictionary, but there are more. Sorted results may be incomplete. Dictionary fails to maintain an accurate number of the number of entries it has.", count); + if(unlikely(i != entries)) + entries = i; - if(unlikely(i != count)) { - internal_error(true, "DICTIONARY: during sorting expected to have %zu items in dictionary, but there are %zu. Sorted results may be incomplete. Dictionary fails to maintain an accurate number of the number of entries it has.", count, i); - count = i; - } + if(compar) + qsort(array, entries, sizeof(DICTIONARY_ITEM *), (qsort_compar)compar); + else + qsort(array, entries, sizeof(DICTIONARY_ITEM *), dictionary_sort_compar); - qsort(array, count, sizeof(NAME_VALUE *), dictionary_sort_compar); + bool callit = true; + int ret = 0, r; + for(i = 0; i < entries ;i++) { + item = array[i]; - int ret = 0; - for(i = 0; i < count ;i++) { - nv = array[i]; - if(likely(!(nv->flags & NAME_VALUE_FLAG_DELETED))) { - reference_counter_acquire(dict, nv); - int r = callback(namevalue_get_name(nv), nv->value, data); - reference_counter_release(dict, nv, false); - if (r < 0) { - ret = r; - break; - } - ret += r; + if(callit) + r = callback(item, item->shared->value, data); + + dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dict, item, rw); + // item_release(dict, item); + + if(r < 0) { + ret = r; + r = 0; + + // stop calling the callback, + // but we have to continue, to release all the reference counters + callit = false; } + else + ret += r; } - dictionary_restore_all_deletions_unsafe(dict, rw); - dictionary_unlock(dict, rw); freez(array); return ret; } // ---------------------------------------------------------------------------- -// STRING implementation - dedup all STRINGs +// THREAD_CACHE -typedef struct string_entry { -#ifdef DICTIONARY_WITH_AVL - avl_t avl_node; -#endif - uint32_t length; // the string length with the terminating '\0' - uint32_t refcount; // how many times this string is used - const char str[]; // the string itself -} STRING_ENTRY; +static __thread Pvoid_t thread_cache_judy_array = NULL; -#ifdef DICTIONARY_WITH_AVL -static int string_entry_compare(void* a, void* b) { - return strcmp(((STRING_ENTRY *)a)->str, ((STRING_ENTRY *)b)->str); -} - -static void *get_thread_static_string_entry(const char *name) { - static __thread size_t _length = 0; - static __thread STRING_ENTRY *_tmp = NULL; +void *thread_cache_entry_get_or_set(void *key, + ssize_t key_length, + void *value, + void *(*transform_the_value_before_insert)(void *key, size_t key_length, void *value) + ) { + if(unlikely(!key || !key_length)) return NULL; - size_t size = sizeof(STRING_ENTRY) + strlen(name) + 1; - if(likely(_tmp && _length < size)) { - freez(_tmp); - _tmp = NULL; - _length = 0; - } + if(key_length == -1) + key_length = (ssize_t)strlen((char *)key) + 1; - if(unlikely(!_tmp)) { - _tmp = callocz(1, size); - _length = size; + JError_t J_Error; + Pvoid_t *Rc = JudyHSIns(&thread_cache_judy_array, key, key_length, &J_Error); + if (unlikely(Rc == PJERR)) { + fatal("THREAD_CACHE: Cannot insert entry to JudyHS, JU_ERRNO_* == %u, ID == %d", + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); } - strcpy((char *)&_tmp->str[0], name); - return _tmp; -} -#endif - -DICTIONARY string_dictionary = { -#ifdef DICTIONARY_WITH_AVL - .values_index = { - .root = NULL, - .compar = string_entry_compare - }, - .get_thread_static_name_value = get_thread_static_string_entry, -#endif - - .flags = DICTIONARY_FLAG_EXCLUSIVE_ACCESS, - .rwlock = NETDATA_RWLOCK_INITIALIZER -}; - -static netdata_mutex_t string_mutex = NETDATA_MUTEX_INITIALIZER; - -STRING *string_dup(STRING *string) { - if(unlikely(!string)) return NULL; - - STRING_ENTRY *se = (STRING_ENTRY *)string; - netdata_mutex_lock(&string_mutex); - se->refcount++; - netdata_mutex_unlock(&string_mutex); - return string; -} - -STRING *string_strdupz(const char *str) { - if(unlikely(!str || !*str)) return NULL; + if(*Rc == 0) { + // new item added - netdata_mutex_lock(&string_mutex); - - size_t length = strlen(str) + 1; - STRING_ENTRY *se; - STRING_ENTRY **ptr = (STRING_ENTRY **)hashtable_insert_unsafe(&string_dictionary, str, length); - if(unlikely(*ptr == 0)) { - // a new item added to the index - size_t mem_size = sizeof(STRING_ENTRY) + length; - se = mallocz(mem_size); - strcpy((char *)se->str, str); - se->length = length; - se->refcount = 1; - *ptr = se; - hashtable_inserted_name_value_unsafe(&string_dictionary, se); - string_dictionary.version++; - string_dictionary.inserts++; - string_dictionary.entries++; - string_dictionary.memory += (long)mem_size; - } - else { - // the item is already in the index - se = *ptr; - se->refcount++; - string_dictionary.searches++; + *Rc = (transform_the_value_before_insert) ? transform_the_value_before_insert(key, key_length, value) : value; } - netdata_mutex_unlock(&string_mutex); - return (STRING *)se; + return *Rc; } -void string_freez(STRING *string) { - if(unlikely(!string)) return; - netdata_mutex_lock(&string_mutex); - - STRING_ENTRY *se = (STRING_ENTRY *)string; +void thread_cache_destroy(void) { + if(unlikely(!thread_cache_judy_array)) return; - if(se->refcount == 0) - fatal("STRING: tried to free string that has zero references."); - - se->refcount--; - if(unlikely(se->refcount == 0)) { - if(hashtable_delete_unsafe(&string_dictionary, se->str, se->length, se) == 0) - error("STRING: INTERNAL ERROR: tried to delete '%s' that is not in the index", se->str); - - size_t mem_size = sizeof(STRING_ENTRY) + se->length; - freez(se); - string_dictionary.version++; - string_dictionary.deletes++; - string_dictionary.entries--; - string_dictionary.memory -= (long)mem_size; - } - - netdata_mutex_unlock(&string_mutex); -} - -size_t string_length(STRING *string) { - if(unlikely(!string)) return 0; - return ((STRING_ENTRY *)string)->length - 1; -} - -const char *string2str(STRING *string) { - if(unlikely(!string)) return ""; - return ((STRING_ENTRY *)string)->str; -} - -STRING *string_2way_merge(STRING *a, STRING *b) { - static STRING *X = NULL; - - if(unlikely(!X)) { - X = string_strdupz("[x]"); + JError_t J_Error; + Word_t ret = JudyHSFreeArray(&thread_cache_judy_array, &J_Error); + if(unlikely(ret == (Word_t) JERR)) { + error("THREAD_CACHE: Cannot destroy JudyHS, JU_ERRNO_* == %u, ID == %d", + JU_ERRNO(&J_Error), JU_ERRID(&J_Error)); } - if(unlikely(a == b)) return string_dup(a); - if(unlikely(a == X)) return string_dup(a); - if(unlikely(b == X)) return string_dup(b); - if(unlikely(!a)) return string_dup(X); - if(unlikely(!b)) return string_dup(X); - - size_t alen = string_length(a); - size_t blen = string_length(b); - size_t length = alen + blen + string_length(X) + 1; - char buf1[length + 1], buf2[length + 1], *dst1; - const char *s1, *s2; - - s1 = string2str(a); - s2 = string2str(b); - dst1 = buf1; - for( ; *s1 && *s2 && *s1 == *s2 ;s1++, s2++) - *dst1++ = *s1; - - *dst1 = '\0'; + internal_error(true, "THREAD_CACHE: hash table freed %lu bytes", ret); - if(*s1 != '\0' || *s2 != '\0') { - *dst1++ = '['; - *dst1++ = 'x'; - *dst1++ = ']'; - - s1 = &(string2str(a))[alen - 1]; - s2 = &(string2str(b))[blen - 1]; - char *dst2 = &buf2[length]; - *dst2 = '\0'; - for (; *s1 && *s2 && *s1 == *s2; s1--, s2--) - *(--dst2) = *s1; - - strcpy(dst1, dst2); - } - - return string_strdupz(buf1); + thread_cache_judy_array = NULL; } // ---------------------------------------------------------------------------- @@ -1656,7 +2503,7 @@ static char **dictionary_unittest_generate_names(size_t entries) { char **names = mallocz(sizeof(char *) * entries); for(size_t i = 0; i < entries ;i++) { char buf[25 + 1] = ""; - snprintfz(buf, 25, "name.%zu.0123456789.%zu \t !@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i); + snprintfz(buf, 25, "name.%zu.0123456789.%zu!@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i); names[i] = strdupz(buf); } return names; @@ -1686,12 +2533,12 @@ static size_t dictionary_unittest_set_clone(DICTIONARY *dict, char **names, char static size_t dictionary_unittest_set_null(DICTIONARY *dict, char **names, char **values, size_t entries) { (void)values; size_t errors = 0; - long i = 0; - for(; i < (long)entries ;i++) { + size_t i = 0; + for(; i < entries ;i++) { void *val = dictionary_set(dict, names[i], NULL, 0); if(val != NULL) { fprintf(stderr, ">>> %s() returns a non NULL value\n", __FUNCTION__); errors++; } } - if(dictionary_stats_entries(dict) != i) { + if(dictionary_entries(dict) != i) { fprintf(stderr, ">>> %s() dictionary items do not match\n", __FUNCTION__); errors++; } @@ -1743,8 +2590,8 @@ static size_t dictionary_unittest_del_nonexisting(DICTIONARY *dict, char **names (void)names; size_t errors = 0; for(size_t i = 0; i < entries ;i++) { - int ret = dictionary_del(dict, values[i]); - if(ret != -1) { fprintf(stderr, ">>> %s() deleted non-existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, values[i]); + if(ret) { fprintf(stderr, ">>> %s() deleted non-existing item\n", __FUNCTION__); errors++; } } return errors; } @@ -1758,18 +2605,18 @@ static size_t dictionary_unittest_del_existing(DICTIONARY *dict, char **names, c size_t backward_from = middle_to, backward_to = entries; for(size_t i = forward_from; i < forward_to ;i++) { - int ret = dictionary_del(dict, names[i]); - if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (forward) existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, names[i]); + if(!ret) { fprintf(stderr, ">>> %s() didn't delete (forward) existing item\n", __FUNCTION__); errors++; } } for(size_t i = middle_to - 1; i >= middle_from ;i--) { - int ret = dictionary_del(dict, names[i]); - if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (middle) existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, names[i]); + if(!ret) { fprintf(stderr, ">>> %s() didn't delete (middle) existing item\n", __FUNCTION__); errors++; } } for(size_t i = backward_to - 1; i >= backward_from ;i--) { - int ret = dictionary_del(dict, names[i]); - if(ret == -1) { fprintf(stderr, ">>> %s() didn't delete (backward) existing item\n", __FUNCTION__); errors++; } + bool ret = dictionary_del(dict, names[i]); + if(!ret) { fprintf(stderr, ">>> %s() didn't delete (backward) existing item\n", __FUNCTION__); errors++; } } return errors; @@ -1812,10 +2659,7 @@ static size_t dictionary_unittest_reset_dont_overwrite_nonclone(DICTIONARY *dict return errors; } -static int dictionary_unittest_walkthrough_callback(const char *name, void *value, void *data) { - (void)name; - (void)value; - (void)data; +static int dictionary_unittest_walkthrough_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) { return 1; } @@ -1827,10 +2671,10 @@ static size_t dictionary_unittest_walkthrough(DICTIONARY *dict, char **names, ch else return sum - entries; } -static int dictionary_unittest_walkthrough_delete_this_callback(const char *name, void *value, void *data) { - (void)value; +static int dictionary_unittest_walkthrough_delete_this_callback(const DICTIONARY_ITEM *item, void *value __maybe_unused, void *data) { + const char *name = dictionary_acquired_item_name((DICTIONARY_ITEM *)item); - if(dictionary_del_having_write_lock((DICTIONARY *)data, name) == -1) + if(!dictionary_del((DICTIONARY *)data, name)) return 0; return 1; @@ -1844,10 +2688,7 @@ static size_t dictionary_unittest_walkthrough_delete_this(DICTIONARY *dict, char else return sum - entries; } -static int dictionary_unittest_walkthrough_stop_callback(const char *name, void *value, void *data) { - (void)name; - (void)value; - (void)data; +static int dictionary_unittest_walkthrough_stop_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) { return -1; } @@ -1881,7 +2722,7 @@ static size_t dictionary_unittest_foreach_delete_this(DICTIONARY *dict, char **n size_t count = 0; char *item; dfe_start_write(dict, item) - if(dictionary_del_having_write_lock(dict, item_name) != -1) count++; + if(dictionary_del(dict, item_dfe.name)) count++; dfe_done(item); if(count > entries) return count - entries; @@ -1907,7 +2748,22 @@ static usec_t dictionary_unittest_run_and_measure_time(DICTIONARY *dict, char *m if(callback == dictionary_unittest_destroy) dict = NULL; - fprintf(stderr, " %zu errors, %ld items in dictionary, %llu usec \n", errs, dict? dictionary_stats_entries(dict):0, dt); + long int found_ok = 0, found_deleted = 0, found_referenced = 0; + if(dict) { + DICTIONARY_ITEM *item; + DOUBLE_LINKED_LIST_FOREACH_FORWARD(dict->items.list, item, prev, next) { + if(item->refcount >= 0 && !(item ->flags & ITEM_FLAG_DELETED)) + found_ok++; + else + found_deleted++; + + if(item->refcount > 0) + found_referenced++; + } + } + + fprintf(stderr, " %zu errors, %ld (found %ld) items in dictionary, %ld (found %ld) referenced, %ld (found %ld) deleted, %llu usec \n", + errs, dict?dict->entries:0, found_ok, dict?dict->referenced_items:0, found_referenced, dict?dict->pending_deletion_items:0, found_deleted, dt); *errors += errs; return dt; } @@ -1943,23 +2799,24 @@ static void dictionary_unittest_nonclone(DICTIONARY *dict, char **names, char ** } struct dictionary_unittest_sorting { - const char *oldname; - const char *oldvalue; + const char *old_name; + const char *old_value; size_t count; }; -static int dictionary_unittest_sorting_callback(const char *name, void *value, void *data) { +static int dictionary_unittest_sorting_callback(const DICTIONARY_ITEM *item, void *value, void *data) { + const char *name = dictionary_acquired_item_name((DICTIONARY_ITEM *)item); struct dictionary_unittest_sorting *t = (struct dictionary_unittest_sorting *)data; const char *v = (const char *)value; int ret = 0; - if(t->oldname && strcmp(t->oldname, name) > 0) { - fprintf(stderr, "name '%s' should be after '%s'\n", t->oldname, name); + if(t->old_name && strcmp(t->old_name, name) > 0) { + fprintf(stderr, "name '%s' should be after '%s'\n", t->old_name, name); ret = 1; } t->count++; - t->oldname = name; - t->oldvalue = v; + t->old_name = name; + t->old_value = v; return ret; } @@ -1967,7 +2824,7 @@ static int dictionary_unittest_sorting_callback(const char *name, void *value, v static size_t dictionary_unittest_sorted_walkthrough(DICTIONARY *dict, char **names, char **values, size_t entries) { (void)names; (void)values; - struct dictionary_unittest_sorting tmp = { .oldname = NULL, .oldvalue = NULL, .count = 0 }; + struct dictionary_unittest_sorting tmp = { .old_name = NULL, .old_value = NULL, .count = 0 }; size_t errors; errors = dictionary_sorted_walkthrough_read(dict, dictionary_unittest_sorting_callback, &tmp); @@ -1989,62 +2846,94 @@ static void dictionary_unittest_null_dfe(DICTIONARY *dict, char **names, char ** } -static int check_dictionary_callback(const char *name, void *value, void *data) { - (void)name; - (void)value; - (void)data; +static int unittest_check_dictionary_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value __maybe_unused, void *data __maybe_unused) { return 1; } -static size_t check_dictionary(DICTIONARY *dict, size_t entries, size_t linked_list_members) { +static size_t unittest_check_dictionary(const char *label, DICTIONARY *dict, size_t traversable, size_t active_items, size_t deleted_items, size_t referenced_items, size_t pending_deletion) { size_t errors = 0; - fprintf(stderr, "dictionary entries %ld, expected %zu...\t\t\t\t\t", dictionary_stats_entries(dict), entries); - if (dictionary_stats_entries(dict) != (long)entries) { + size_t ll = 0; + void *t; + dfe_start_read(dict, t) + ll++; + dfe_done(t); + + fprintf(stderr, "DICT %-20s: dictionary foreach entries %zu, expected %zu...\t\t\t\t\t", + label, ll, traversable); + if(ll != traversable) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - size_t ll = 0; - void *t; - dfe_start_read(dict, t) - ll++; - dfe_done(t); + ll = dictionary_walkthrough_read(dict, unittest_check_dictionary_callback, NULL); + fprintf(stderr, "DICT %-20s: dictionary walkthrough entries %zu, expected %zu...\t\t\t\t", + label, ll, traversable); + if(ll != traversable) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); - fprintf(stderr, "dictionary foreach entries %zu, expected %zu...\t\t\t\t", ll, entries); - if(ll != entries) { + ll = dictionary_sorted_walkthrough_read(dict, unittest_check_dictionary_callback, NULL); + fprintf(stderr, "DICT %-20s: dictionary sorted walkthrough entries %zu, expected %zu...\t\t\t", + label, ll, traversable); + if(ll != traversable) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - ll = dictionary_walkthrough_read(dict, check_dictionary_callback, NULL); - fprintf(stderr, "dictionary walkthrough entries %zu, expected %zu...\t\t\t\t", ll, entries); - if(ll != entries) { + DICTIONARY_ITEM *item; + size_t active = 0, deleted = 0, referenced = 0, pending = 0; + for(item = dict->items.list; item; item = item->next) { + if(!(item->flags & ITEM_FLAG_DELETED) && !(item->shared->flags & ITEM_FLAG_DELETED)) + active++; + else { + deleted++; + + if(item->refcount == 0) + pending++; + } + + if(item->refcount > 0) + referenced++; + } + + fprintf(stderr, "DICT %-20s: dictionary active items reported %ld, counted %zu, expected %zu...\t\t\t", + label, dict->entries, active, active_items); + if(active != active_items || active != (size_t)dict->entries) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - ll = dictionary_sorted_walkthrough_read(dict, check_dictionary_callback, NULL); - fprintf(stderr, "dictionary sorted walkthrough entries %zu, expected %zu...\t\t\t", ll, entries); - if(ll != entries) { + fprintf(stderr, "DICT %-20s: dictionary deleted items counted %zu, expected %zu...\t\t\t\t", + label, deleted, deleted_items); + if(deleted != deleted_items) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - NAME_VALUE *nv; - for(ll = 0, nv = dict->first_item; nv ;nv = nv->next) - ll++; + fprintf(stderr, "DICT %-20s: dictionary referenced items reported %ld, counted %zu, expected %zu...\t\t", + label, dict->referenced_items, referenced, referenced_items); + if(referenced != referenced_items || dict->referenced_items != (long int)referenced) { + fprintf(stderr, "FAILED\n"); + errors++; + } + else + fprintf(stderr, "OK\n"); - fprintf(stderr, "dictionary linked list entries %zu, expected %zu...\t\t\t\t", ll, linked_list_members); - if(ll != linked_list_members) { + fprintf(stderr, "DICT %-20s: dictionary pending deletion items reported %ld, counted %zu, expected %zu...\t", + label, dict->pending_deletion_items, pending, pending_deletion); + if(pending != pending_deletion || pending != (size_t)dict->pending_deletion_items) { fprintf(stderr, "FAILED\n"); errors++; } @@ -2054,40 +2943,44 @@ static size_t check_dictionary(DICTIONARY *dict, size_t entries, size_t linked_l return errors; } -static int check_name_value_callback(const char *name, void *value, void *data) { - (void)name; +static int check_item_callback(const DICTIONARY_ITEM *item __maybe_unused, void *value, void *data) { return value == data; } -static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, const char *name, const char *value, unsigned refcount, NAME_VALUE_FLAGS deleted_flags, bool searchable, bool browsable, bool linked) { +static size_t unittest_check_item(const char *label, DICTIONARY *dict, + DICTIONARY_ITEM *item, const char *name, const char *value, int refcount, + ITEM_FLAGS deleted_flags, bool searchable, bool browsable, bool linked) { size_t errors = 0; - fprintf(stderr, "NAME_VALUE name is '%s', expected '%s'...\t\t\t\t", namevalue_get_name(nv), name); - if(strcmp(namevalue_get_name(nv), name) != 0) { + fprintf(stderr, "ITEM %-20s: name is '%s', expected '%s'...\t\t\t\t\t\t", label, item_get_name(item), name); + if(strcmp(item_get_name(item), name) != 0) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - fprintf(stderr, "NAME_VALUE value is '%s', expected '%s'...\t\t\t", (const char *)nv->value, value); - if(strcmp((const char *)nv->value, value) != 0) { + fprintf(stderr, "ITEM %-20s: value is '%s', expected '%s'...\t\t\t\t\t", label, (const char *)item->shared->value, value); + if(strcmp((const char *)item->shared->value, value) != 0) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - fprintf(stderr, "NAME_VALUE refcount is %u, expected %u...\t\t\t\t\t", nv->refcount, refcount); - if (nv->refcount != refcount) { + fprintf(stderr, "ITEM %-20s: refcount is %d, expected %d...\t\t\t\t\t\t\t", label, item->refcount, refcount); + if (item->refcount != refcount) { fprintf(stderr, "FAILED\n"); errors++; } else fprintf(stderr, "OK\n"); - fprintf(stderr, "NAME_VALUE deleted flag is %s, expected %s...\t\t\t", (nv->flags & NAME_VALUE_FLAG_DELETED)?"TRUE":"FALSE", (deleted_flags & NAME_VALUE_FLAG_DELETED)?"TRUE":"FALSE"); - if ((nv->flags & NAME_VALUE_FLAG_DELETED) != (deleted_flags & NAME_VALUE_FLAG_DELETED)) { + fprintf(stderr, "ITEM %-20s: deleted flag is %s, expected %s...\t\t\t\t\t", label, + (item->flags & ITEM_FLAG_DELETED || item->shared->flags & ITEM_FLAG_DELETED)?"true":"false", + (deleted_flags & ITEM_FLAG_DELETED)?"true":"false"); + + if ((item->flags & ITEM_FLAG_DELETED || item->shared->flags & ITEM_FLAG_DELETED) != (deleted_flags & ITEM_FLAG_DELETED)) { fprintf(stderr, "FAILED\n"); errors++; } @@ -2095,8 +2988,9 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co fprintf(stderr, "OK\n"); void *v = dictionary_get(dict, name); - bool found = v == nv->value; - fprintf(stderr, "NAME_VALUE searchable %5s, expected %5s...\t\t\t\t", found?"true":"false", searchable?"true":"false"); + bool found = v == item->shared->value; + fprintf(stderr, "ITEM %-20s: searchable %5s, expected %5s...\t\t\t\t\t\t", label, + found?"true":"false", searchable?"true":"false"); if(found != searchable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2107,11 +3001,12 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co found = false; void *t; dfe_start_read(dict, t) { - if(t == nv->value) found = true; + if(t == item->shared->value) found = true; } dfe_done(t); - fprintf(stderr, "NAME_VALUE dfe browsable %5s, expected %5s...\t\t\t", found?"true":"false", browsable?"true":"false"); + fprintf(stderr, "ITEM %-20s: dfe browsable %5s, expected %5s...\t\t\t\t\t", label, + found?"true":"false", browsable?"true":"false"); if(found != browsable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2119,8 +3014,9 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co else fprintf(stderr, "OK\n"); - found = dictionary_walkthrough_read(dict, check_name_value_callback, nv->value); - fprintf(stderr, "NAME_VALUE walkthrough browsable %5s, expected %5s...\t\t", found?"true":"false", browsable?"true":"false"); + found = dictionary_walkthrough_read(dict, check_item_callback, item->shared->value); + fprintf(stderr, "ITEM %-20s: walkthrough browsable %5s, expected %5s...\t\t\t\t", label, + found?"true":"false", browsable?"true":"false"); if(found != browsable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2128,8 +3024,9 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co else fprintf(stderr, "OK\n"); - found = dictionary_sorted_walkthrough_read(dict, check_name_value_callback, nv->value); - fprintf(stderr, "NAME_VALUE sorted walkthrough browsable %5s, expected %5s...\t", found?"true":"false", browsable?"true":"false"); + found = dictionary_sorted_walkthrough_read(dict, check_item_callback, item->shared->value); + fprintf(stderr, "ITEM %-20s: sorted walkthrough browsable %5s, expected %5s...\t\t\t", label, + found?"true":"false", browsable?"true":"false"); if(found != browsable) { fprintf(stderr, "FAILED\n"); errors++; @@ -2138,11 +3035,12 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co fprintf(stderr, "OK\n"); found = false; - NAME_VALUE *n; - for(n = dict->first_item; n ;n = n->next) - if(n == nv) found = true; + DICTIONARY_ITEM *n; + for(n = dict->items.list; n ;n = n->next) + if(n == item) found = true; - fprintf(stderr, "NAME_VALUE linked %5s, expected %5s...\t\t\t\t", found?"true":"false", linked?"true":"false"); + fprintf(stderr, "ITEM %-20s: linked %5s, expected %5s...\t\t\t\t\t\t", label, + found?"true":"false", linked?"true":"false"); if(found != linked) { fprintf(stderr, "FAILED\n"); errors++; @@ -2153,6 +3051,423 @@ static size_t check_name_value_deleted_flag(DICTIONARY *dict, NAME_VALUE *nv, co return errors; } +struct thread_unittest { + int join; + DICTIONARY *dict; + int dups; +}; + +static void *unittest_dict_thread(void *arg) { + struct thread_unittest *tu = arg; + for(; 1 ;) { + if(__atomic_load_n(&tu->join, __ATOMIC_RELAXED)) + break; + + DICT_ITEM_CONST DICTIONARY_ITEM *item = + dictionary_set_and_acquire_item_advanced(tu->dict, "dict thread checking 1234567890", + -1, NULL, 0, NULL); + + + dictionary_get(tu->dict, dictionary_acquired_item_name(item)); + + void *t1; + dfe_start_write(tu->dict, t1) { + + // this should delete the referenced item + dictionary_del(tu->dict, t1_dfe.name); + + void *t2; + dfe_start_write(tu->dict, t2) { + // this should add another + dictionary_set(tu->dict, t2_dfe.name, NULL, 0); + + dictionary_get(tu->dict, dictionary_acquired_item_name(item)); + + // and this should delete it again + dictionary_del(tu->dict, t2_dfe.name); + } + dfe_done(t2); + + // this should fail to add it + dictionary_set(tu->dict, t1_dfe.name, NULL, 0); + dictionary_del(tu->dict, t1_dfe.name); + } + dfe_done(t1); + + for(int i = 0; i < tu->dups ; i++) { + dictionary_acquired_item_dup(tu->dict, item); + dictionary_get(tu->dict, dictionary_acquired_item_name(item)); + } + + for(int i = 0; i < tu->dups ; i++) { + dictionary_acquired_item_release(tu->dict, item); + dictionary_del(tu->dict, dictionary_acquired_item_name(item)); + } + + dictionary_acquired_item_release(tu->dict, item); + dictionary_del(tu->dict, "dict thread checking 1234567890"); + + // test concurrent deletions and flushes + { + if(gettid() % 2) { + char buf [256 + 1]; + + for (int i = 0; i < 1000; i++) { + snprintfz(buf, 256, "del/flush test %d", i); + dictionary_set(tu->dict, buf, NULL, 0); + } + + for (int i = 0; i < 1000; i++) { + snprintfz(buf, 256, "del/flush test %d", i); + dictionary_del(tu->dict, buf); + } + } + else { + for (int i = 0; i < 10; i++) { + dictionary_flush(tu->dict); + } + } + } + } + + return arg; +} + +static int dictionary_unittest_threads() { + + struct thread_unittest tu = { + .join = 0, + .dict = NULL, + .dups = 1, + }; + + // threads testing of dictionary + tu.dict = dictionary_create(DICT_OPTION_DONT_OVERWRITE_VALUE); + time_t seconds_to_run = 5; + int threads_to_create = 2; + fprintf( + stderr, + "\nChecking dictionary concurrency with %d threads for %lld seconds...\n", + threads_to_create, + (long long)seconds_to_run); + + netdata_thread_t threads[threads_to_create]; + tu.join = 0; + for (int i = 0; i < threads_to_create; i++) { + char buf[100 + 1]; + snprintf(buf, 100, "dict%d", i); + netdata_thread_create( + &threads[i], + buf, + NETDATA_THREAD_OPTION_DONT_LOG | NETDATA_THREAD_OPTION_JOINABLE, + unittest_dict_thread, + &tu); + } + sleep_usec(seconds_to_run * USEC_PER_SEC); + + __atomic_store_n(&tu.join, 1, __ATOMIC_RELAXED); + for (int i = 0; i < threads_to_create; i++) { + void *retval; + netdata_thread_join(threads[i], &retval); + } + + fprintf(stderr, + "inserts %zu" + ", deletes %zu" + ", searches %zu" + ", resets %zu" + ", flushes %zu" + ", entries %ld" + ", referenced_items %ld" + ", pending deletions %ld" + ", check spins %zu" + ", insert spins %zu" + ", delete spins %zu" + ", search ignores %zu" + "\n", + tu.dict->stats->ops.inserts, + tu.dict->stats->ops.deletes, + tu.dict->stats->ops.searches, + tu.dict->stats->ops.resets, + tu.dict->stats->ops.flushes, + tu.dict->entries, + tu.dict->referenced_items, + tu.dict->pending_deletion_items, + tu.dict->stats->spin_locks.use_spins, + tu.dict->stats->spin_locks.insert_spins, + tu.dict->stats->spin_locks.delete_spins, + tu.dict->stats->spin_locks.search_spins + ); + dictionary_destroy(tu.dict); + tu.dict = NULL; + + return 0; +} + +struct thread_view_unittest { + int join; + DICTIONARY *master; + DICTIONARY *view; + DICTIONARY_ITEM *item_master; + int dups; +}; + +static void *unittest_dict_master_thread(void *arg) { + struct thread_view_unittest *tv = arg; + + DICTIONARY_ITEM *item = NULL; + int loops = 0; + while(!__atomic_load_n(&tv->join, __ATOMIC_SEQ_CST)) { + + if(!item) + item = dictionary_set_and_acquire_item(tv->master, "ITEM1", "123", strlen("123") + 1); + + if(__atomic_load_n(&tv->item_master, __ATOMIC_SEQ_CST) != NULL) { + dictionary_acquired_item_release(tv->master, item); + dictionary_del(tv->master, "ITEM1"); + item = NULL; + loops++; + continue; + } + + dictionary_acquired_item_dup(tv->master, item); // for the view thread + __atomic_store_n(&tv->item_master, item, __ATOMIC_SEQ_CST); + dictionary_del(tv->master, "ITEM1"); + + + for(int i = 0; i < tv->dups + loops ; i++) { + dictionary_acquired_item_dup(tv->master, item); + } + + for(int i = 0; i < tv->dups + loops ; i++) { + dictionary_acquired_item_release(tv->master, item); + } + + dictionary_acquired_item_release(tv->master, item); + + item = NULL; + loops = 0; + } + + return arg; +} + +static void *unittest_dict_view_thread(void *arg) { + struct thread_view_unittest *tv = arg; + + DICTIONARY_ITEM *m_item = NULL; + + while(!__atomic_load_n(&tv->join, __ATOMIC_SEQ_CST)) { + if(!(m_item = __atomic_load_n(&tv->item_master, __ATOMIC_SEQ_CST))) + continue; + + DICTIONARY_ITEM *v_item = dictionary_view_set_and_acquire_item(tv->view, "ITEM2", m_item); + dictionary_acquired_item_release(tv->master, m_item); + __atomic_store_n(&tv->item_master, NULL, __ATOMIC_SEQ_CST); + + for(int i = 0; i < tv->dups ; i++) { + dictionary_acquired_item_dup(tv->view, v_item); + } + + for(int i = 0; i < tv->dups ; i++) { + dictionary_acquired_item_release(tv->view, v_item); + } + + dictionary_del(tv->view, "ITEM2"); + + while(!__atomic_load_n(&tv->join, __ATOMIC_SEQ_CST) && !(m_item = __atomic_load_n(&tv->item_master, __ATOMIC_SEQ_CST))) { + dictionary_acquired_item_dup(tv->view, v_item); + dictionary_acquired_item_release(tv->view, v_item); + } + + dictionary_acquired_item_release(tv->view, v_item); + } + + return arg; +} + +static int dictionary_unittest_view_threads() { + + struct thread_view_unittest tv = { + .join = 0, + .master = NULL, + .view = NULL, + .item_master = NULL, + .dups = 1, + }; + + // threads testing of dictionary + struct dictionary_stats stats_master = {}; + struct dictionary_stats stats_view = {}; + tv.master = dictionary_create_advanced(DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE, &stats_master); + tv.view = dictionary_create_view(tv.master); + tv.view->stats = &stats_view; + + time_t seconds_to_run = 5; + fprintf( + stderr, + "\nChecking dictionary concurrency with 1 master and 1 view threads for %lld seconds...\n", + (long long)seconds_to_run); + + netdata_thread_t master_thread, view_thread; + tv.join = 0; + + netdata_thread_create( + &master_thread, + "master", + NETDATA_THREAD_OPTION_DONT_LOG | NETDATA_THREAD_OPTION_JOINABLE, + unittest_dict_master_thread, + &tv); + + netdata_thread_create( + &view_thread, + "view", + NETDATA_THREAD_OPTION_DONT_LOG | NETDATA_THREAD_OPTION_JOINABLE, + unittest_dict_view_thread, + &tv); + + sleep_usec(seconds_to_run * USEC_PER_SEC); + + __atomic_store_n(&tv.join, 1, __ATOMIC_RELAXED); + void *retval; + netdata_thread_join(view_thread, &retval); + netdata_thread_join(master_thread, &retval); + + fprintf(stderr, + "MASTER: inserts %zu" + ", deletes %zu" + ", searches %zu" + ", resets %zu" + ", entries %ld" + ", referenced_items %ld" + ", pending deletions %ld" + ", check spins %zu" + ", insert spins %zu" + ", delete spins %zu" + ", search ignores %zu" + "\n", + stats_master.ops.inserts, + stats_master.ops.deletes, + stats_master.ops.searches, + stats_master.ops.resets, + tv.master->entries, + tv.master->referenced_items, + tv.master->pending_deletion_items, + stats_master.spin_locks.use_spins, + stats_master.spin_locks.insert_spins, + stats_master.spin_locks.delete_spins, + stats_master.spin_locks.search_spins + ); + fprintf(stderr, + "VIEW : inserts %zu" + ", deletes %zu" + ", searches %zu" + ", resets %zu" + ", entries %ld" + ", referenced_items %ld" + ", pending deletions %ld" + ", check spins %zu" + ", insert spins %zu" + ", delete spins %zu" + ", search ignores %zu" + "\n", + stats_view.ops.inserts, + stats_view.ops.deletes, + stats_view.ops.searches, + stats_view.ops.resets, + tv.view->entries, + tv.view->referenced_items, + tv.view->pending_deletion_items, + stats_view.spin_locks.use_spins, + stats_view.spin_locks.insert_spins, + stats_view.spin_locks.delete_spins, + stats_view.spin_locks.search_spins + ); + dictionary_destroy(tv.master); + dictionary_destroy(tv.view); + + return 0; +} + +size_t dictionary_unittest_views(void) { + size_t errors = 0; + struct dictionary_stats stats = {}; + DICTIONARY *master = dictionary_create_advanced(DICT_OPTION_NONE, &stats); + DICTIONARY *view = dictionary_create_view(master); + + fprintf(stderr, "\n\nChecking dictionary views...\n"); + + // Add an item to both master and view, then remove the view first and the master second + fprintf(stderr, "\nPASS 1: Adding 1 item to master:\n"); + DICTIONARY_ITEM *item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Adding master item to view:\n"); + DICTIONARY_ITEM *item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master); + errors += unittest_check_dictionary("view", view, 1, 1, 0, 1, 0); + errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Deleting view item:\n"); + dictionary_del(view, "KEY 1 ON VIEW"); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true); + + fprintf(stderr, "\nPASS 1: Releasing the deleted view item:\n"); + dictionary_acquired_item_release(view, item1_on_view); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Releasing the acquired master item:\n"); + dictionary_acquired_item_release(master, item1_on_master); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 0, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 0, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 1: Deleting the released master item:\n"); + dictionary_del(master, "KEY 1"); + errors += unittest_check_dictionary("master", master, 0, 0, 0, 0, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + + // The other way now: + // Add an item to both master and view, then remove the master first and verify it is deleted on the view also + fprintf(stderr, "\nPASS 2: Adding 1 item to master:\n"); + item1_on_master = dictionary_set_and_acquire_item(master, "KEY 1", "VALUE1", strlen("VALUE1") + 1); + errors += unittest_check_dictionary("master", master, 1, 1, 0, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 2: Adding master item to view:\n"); + item1_on_view = dictionary_view_set_and_acquire_item(view, "KEY 1 ON VIEW", item1_on_master); + errors += unittest_check_dictionary("view", view, 1, 1, 0, 1, 0); + errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_NONE, true, true, true); + + fprintf(stderr, "\nPASS 2: Deleting master item:\n"); + dictionary_del(master, "KEY 1"); + dictionary_version(view); + errors += unittest_check_dictionary("master", master, 0, 0, 1, 1, 0); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0); + errors += unittest_check_item("master", master, item1_on_master, "KEY 1", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true); + errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true); + + fprintf(stderr, "\nPASS 2: Releasing the acquired master item:\n"); + dictionary_acquired_item_release(master, item1_on_master); + errors += unittest_check_dictionary("master", master, 0, 0, 1, 0, 1); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 1, 0); + errors += unittest_check_item("view", view, item1_on_view, "KEY 1 ON VIEW", item1_on_master->shared->value, 1, ITEM_FLAG_DELETED, false, false, true); + + fprintf(stderr, "\nPASS 2: Releasing the deleted view item:\n"); + dictionary_acquired_item_release(view, item1_on_view); + errors += unittest_check_dictionary("master", master, 0, 0, 1, 0, 1); + errors += unittest_check_dictionary("view", view, 0, 0, 1, 0, 1); + + dictionary_destroy(master); + dictionary_destroy(view); + return errors; +} + int dictionary_unittest(size_t entries) { if(entries < 10) entries = 10; @@ -2164,23 +3479,28 @@ int dictionary_unittest(size_t entries) { char **values = dictionary_unittest_generate_values(entries); fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED); dictionary_unittest_clone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary multi threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NONE); + dict = dictionary_create(DICT_OPTION_NONE); dictionary_unittest_clone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary single threaded, non-clone, add-in-front options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dict = dictionary_create( + DICT_OPTION_SINGLE_THREADED | DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | + DICT_OPTION_ADD_IN_FRONT); dictionary_unittest_nonclone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary multi threaded, non-clone, add-in-front options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_ADD_IN_FRONT); + dict = dictionary_create( + DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_ADD_IN_FRONT); dictionary_unittest_nonclone(dict, names, values, entries, &errors); fprintf(stderr, "\nCreating dictionary single-threaded, non-clone, don't overwrite options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create( + DICT_OPTION_SINGLE_THREADED | DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | + DICT_OPTION_DONT_OVERWRITE_VALUE); dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "resetting non-overwrite entries", names, values, entries, &errors, dictionary_unittest_reset_dont_overwrite_nonclone); dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop", names, values, entries, &errors, dictionary_unittest_foreach); @@ -2189,13 +3509,15 @@ int dictionary_unittest(size_t entries) { dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create( + DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE); dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "walkthrough write delete this", names, values, entries, &errors, dictionary_unittest_walkthrough_delete_this); dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary multi-threaded, non-clone, don't overwrite options, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_NAME_LINK_DONT_CLONE|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE|DICTIONARY_FLAG_DONT_OVERWRITE_VALUE); + dict = dictionary_create( + DICT_OPTION_NAME_LINK_DONT_CLONE | DICT_OPTION_VALUE_LINK_DONT_CLONE | DICT_OPTION_DONT_OVERWRITE_VALUE); dictionary_unittest_run_and_measure_time(dict, "adding entries", names, values, entries, &errors, dictionary_unittest_set_nonclone); dictionary_unittest_run_and_measure_time(dict, "foreach write delete this", names, values, entries, &errors, dictionary_unittest_foreach_delete_this); dictionary_unittest_run_and_measure_time(dict, "traverse foreach read loop empty", names, values, 0, &errors, dictionary_unittest_foreach); @@ -2203,208 +3525,100 @@ int dictionary_unittest(size_t entries) { dictionary_unittest_run_and_measure_time(dict, "destroying empty dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED); dictionary_unittest_sorting(dict, names, values, entries, &errors); dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary single threaded, clone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED); dictionary_unittest_null_dfe(dict, names, values, entries, &errors); dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); fprintf(stderr, "\nCreating dictionary single threaded, noclone, %zu items\n", entries); - dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED|DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE); + dict = dictionary_create(DICT_OPTION_SINGLE_THREADED | DICT_OPTION_VALUE_LINK_DONT_CLONE); dictionary_unittest_null_dfe(dict, names, values, entries, &errors); dictionary_unittest_run_and_measure_time(dict, "destroying full dictionary", names, values, entries, &errors, dictionary_unittest_destroy); // check reference counters { fprintf(stderr, "\nTesting reference counters:\n"); - dict = dictionary_create(DICTIONARY_FLAG_NONE|DICTIONARY_FLAG_NAME_LINK_DONT_CLONE); - errors += check_dictionary(dict, 0, 0); + dict = dictionary_create(DICT_OPTION_NONE | DICT_OPTION_NAME_LINK_DONT_CLONE); + errors += unittest_check_dictionary("", dict, 0, 0, 0, 0, 0); fprintf(stderr, "\nAdding test item to dictionary and acquiring it\n"); dictionary_set(dict, "test", "ITEM1", 6); - NAME_VALUE *nv = (NAME_VALUE *)dictionary_get_and_acquire_item(dict, "test"); + DICTIONARY_ITEM *item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test"); - errors += check_dictionary(dict, 1, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("ACQUIRED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nChecking that reference counters are increased:\n"); void *t; dfe_start_read(dict, t) { - errors += check_dictionary(dict, 1, 1); - errors += - check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 2, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("ACQUIRED TRAVERSAL", dict, item, "test", "ITEM1", 2, ITEM_FLAG_NONE, true, true, true); } dfe_done(t); fprintf(stderr, "\nChecking that reference counters are decreased:\n"); - errors += check_dictionary(dict, 1, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("ACQUIRED TRAVERSAL 2", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nDeleting the item we have acquired:\n"); dictionary_del(dict, "test"); - errors += check_dictionary(dict, 0, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); + errors += unittest_check_dictionary("", dict, 0, 0, 1, 1, 0); + errors += unittest_check_item("DELETED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); fprintf(stderr, "\nAdding another item with the same name of the item we deleted, while being acquired:\n"); dictionary_set(dict, "test", "ITEM2", 6); - errors += check_dictionary(dict, 1, 2); + errors += unittest_check_dictionary("", dict, 1, 1, 1, 1, 0); fprintf(stderr, "\nAcquiring the second item:\n"); - NAME_VALUE *nv2 = (NAME_VALUE *)dictionary_get_and_acquire_item(dict, "test"); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); - errors += check_name_value_deleted_flag(dict, nv2, "test", "ITEM2", 1, NAME_VALUE_FLAG_NONE, true, true, true); + DICTIONARY_ITEM *item2 = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test"); + errors += unittest_check_item("FIRST", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); + errors += unittest_check_item("SECOND", dict, item2, "test", "ITEM2", 1, ITEM_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 1, 2, 0); fprintf(stderr, "\nReleasing the second item (the first is still acquired):\n"); - dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)nv2); - errors += check_dictionary(dict, 1, 2); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); - errors += check_name_value_deleted_flag(dict, nv2, "test", "ITEM2", 0, NAME_VALUE_FLAG_NONE, true, true, true); + dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item2); + errors += unittest_check_dictionary("", dict, 1, 1, 1, 1, 0); + errors += unittest_check_item("FIRST", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); + errors += unittest_check_item("SECOND RELEASED", dict, item2, "test", "ITEM2", 0, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nDeleting the second item (the first is still acquired):\n"); dictionary_del(dict, "test"); - errors += check_dictionary(dict, 0, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_DELETED, false, false, true); + errors += unittest_check_dictionary("", dict, 0, 0, 1, 1, 0); + errors += unittest_check_item("ACQUIRED DELETED", dict, item, "test", "ITEM1", 1, ITEM_FLAG_DELETED, false, false, true); fprintf(stderr, "\nReleasing the first item (which we have already deleted):\n"); - dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)nv); - errors += check_dictionary(dict, 0, 0); + dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item); + dfe_start_write(dict, item) ; dfe_done(item); + errors += unittest_check_dictionary("", dict, 0, 0, 1, 0, 1); fprintf(stderr, "\nAdding again the test item to dictionary and acquiring it\n"); dictionary_set(dict, "test", "ITEM1", 6); - nv = (NAME_VALUE *)dictionary_get_and_acquire_item(dict, "test"); + item = (DICTIONARY_ITEM *)dictionary_get_and_acquire_item(dict, "test"); - errors += check_dictionary(dict, 1, 1); - errors += check_name_value_deleted_flag(dict, nv, "test", "ITEM1", 1, NAME_VALUE_FLAG_NONE, true, true, true); + errors += unittest_check_dictionary("", dict, 1, 1, 0, 1, 0); + errors += unittest_check_item("RE-ADDITION", dict, item, "test", "ITEM1", 1, ITEM_FLAG_NONE, true, true, true); fprintf(stderr, "\nDestroying the dictionary while we have acquired an item\n"); dictionary_destroy(dict); fprintf(stderr, "Releasing the item (on a destroyed dictionary)\n"); - dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)nv); - nv = NULL; + dictionary_acquired_item_release(dict, (DICTIONARY_ITEM *)item); + item = NULL; dict = NULL; } - // check string - { - long string_entries_starting = dictionary_stats_entries(&string_dictionary); - - fprintf(stderr, "\nChecking strings...\n"); - - STRING *s1 = string_strdupz("hello unittest"); - STRING *s2 = string_strdupz("hello unittest"); - if(s1 != s2) { - errors++; - fprintf(stderr, "ERROR: duplicating strings are not deduplicated\n"); - } - else - fprintf(stderr, "OK: duplicating string are deduplicated\n"); - - STRING *s3 = string_dup(s1); - if(s3 != s1) { - errors++; - fprintf(stderr, "ERROR: cloning strings are not deduplicated\n"); - } - else - fprintf(stderr, "OK: cloning string are deduplicated\n"); - - STRING_ENTRY *se = (STRING_ENTRY *)s1; - if(se->refcount != 3) { - errors++; - fprintf(stderr, "ERROR: string refcount is not 3\n"); - } - else - fprintf(stderr, "OK: string refcount is 3\n"); - - STRING *s4 = string_strdupz("world unittest"); - if(s4 == s1) { - errors++; - fprintf(stderr, "ERROR: string is sharing pointers on different strings\n"); - } - else - fprintf(stderr, "OK: string is properly handling different strings\n"); - - usec_t start_ut, end_ut; - STRING **strings = mallocz(entries * sizeof(STRING *)); - - start_ut = now_realtime_usec(); - for(size_t i = 0; i < entries ;i++) { - strings[i] = string_strdupz(names[i]); - } - end_ut = now_realtime_usec(); - fprintf(stderr, "Created %zu strings in %llu usecs\n", entries, end_ut - start_ut); - - start_ut = now_realtime_usec(); - for(size_t i = 0; i < entries ;i++) { - strings[i] = string_dup(strings[i]); - } - end_ut = now_realtime_usec(); - fprintf(stderr, "Cloned %zu strings in %llu usecs\n", entries, end_ut - start_ut); - - start_ut = now_realtime_usec(); - for(size_t i = 0; i < entries ;i++) { - string_freez(strings[i]); - string_freez(strings[i]); - } - end_ut = now_realtime_usec(); - fprintf(stderr, "Freed %zu strings in %llu usecs\n", entries, end_ut - start_ut); - - freez(strings); - - if(dictionary_stats_entries(&string_dictionary) != string_entries_starting + 2) { - errors++; - fprintf(stderr, "ERROR: strings dictionary should have %ld items but it has %ld\n", string_entries_starting + 2, dictionary_stats_entries(&string_dictionary)); - } - else - fprintf(stderr, "OK: strings dictionary has 2 items\n"); - } - - // check 2-way merge - { - struct testcase { - char *src1; char *src2; char *expected; - } tests[] = { - { "", "", ""}, - { "a", "", "[x]"}, - { "", "a", "[x]"}, - { "a", "a", "a"}, - { "abcd", "abcd", "abcd"}, - { "foo_cs", "bar_cs", "[x]_cs"}, - { "cp_UNIQUE_INFIX_cs", "cp_unique_infix_cs", "cp_[x]_cs"}, - { "cp_UNIQUE_INFIX_ci_unique_infix_cs", "cp_unique_infix_ci_UNIQUE_INFIX_cs", "cp_[x]_cs"}, - { "foo[1234]", "foo[4321]", "foo[[x]]"}, - { NULL, NULL, NULL }, - }; - - for (struct testcase *tc = &tests[0]; tc->expected != NULL; tc++) { - STRING *src1 = string_strdupz(tc->src1); - STRING *src2 = string_strdupz(tc->src2); - STRING *expected = string_strdupz(tc->expected); - - STRING *result = string_2way_merge(src1, src2); - if (string_cmp(result, expected) != 0) { - fprintf(stderr, "string_2way_merge(\"%s\", \"%s\") -> \"%s\" (expected=\"%s\")\n", - string2str(src1), - string2str(src2), - string2str(result), - string2str(expected)); - errors++; - } - - string_freez(src1); - string_freez(src2); - string_freez(expected); - string_freez(result); - } - } - dictionary_unittest_free_char_pp(names, entries); dictionary_unittest_free_char_pp(values, entries); + errors += dictionary_unittest_views(); + errors += dictionary_unittest_threads(); + errors += dictionary_unittest_view_threads(); + fprintf(stderr, "\n%zu errors found\n", errors); return errors ? 1 : 0; } |