diff options
Diffstat (limited to 'src/libnetdata/dictionary/dictionary-item.h')
| -rw-r--r-- | src/libnetdata/dictionary/dictionary-item.h | 555 |
1 files changed, 555 insertions, 0 deletions
diff --git a/src/libnetdata/dictionary/dictionary-item.h b/src/libnetdata/dictionary/dictionary-item.h new file mode 100644 index 000000000..f7c6e47a7 --- /dev/null +++ b/src/libnetdata/dictionary/dictionary-item.h @@ -0,0 +1,555 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_DICTIONARY_ITEM_H +#define NETDATA_DICTIONARY_ITEM_H + +#include "dictionary-internals.h" + +// ---------------------------------------------------------------------------- +// ITEM initialization and updates + +static inline size_t item_set_name(DICTIONARY *dict, DICTIONARY_ITEM *item, const char *name, size_t name_len) { + if(likely(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE)) { + item->caller_name = (char *)name; + item->key_len = name_len; + } + else { + item->string_name = string_strdupz(name); + item->key_len = string_strlen(item->string_name); + item->options |= ITEM_OPTION_ALLOCATED_NAME; + } + + return item->key_len; +} + +static inline size_t item_free_name(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(likely(!(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE))) + string_freez(item->string_name); + + return item->key_len; +} + +static inline const char *item_get_name(const DICTIONARY_ITEM *item) { + if(item->options & ITEM_OPTION_ALLOCATED_NAME) + return string2str(item->string_name); + else + return item->caller_name; +} + +static inline size_t item_get_name_len(const DICTIONARY_ITEM *item) { + if(item->options & ITEM_OPTION_ALLOCATED_NAME) + return string_strlen(item->string_name); + else + return strlen(item->caller_name); +} + +// ---------------------------------------------------------------------------- + +static inline DICTIONARY_ITEM *dict_item_create(DICTIONARY *dict __maybe_unused, size_t *allocated_bytes, DICTIONARY_ITEM *master_item) { + DICTIONARY_ITEM *item; + + size_t size = sizeof(DICTIONARY_ITEM); + item = aral_mallocz(dict_items_aral); + memset(item, 0, sizeof(DICTIONARY_ITEM)); + +#ifdef NETDATA_INTERNAL_CHECKS + item->creator_pid = gettid_cached(); +#endif + + item->refcount = 1; + item->flags = ITEM_FLAG_BEING_CREATED; + + *allocated_bytes += size; + + if(master_item) { + item->shared = master_item->shared; + + if(unlikely(__atomic_add_fetch(&item->shared->links, 1, __ATOMIC_ACQUIRE) <= 1)) + fatal("DICTIONARY: attempted to link to a shared item structure that had zero references"); + } + else { + size = sizeof(DICTIONARY_ITEM_SHARED); + item->shared = aral_mallocz(dict_shared_items_aral); + memset(item->shared, 0, sizeof(DICTIONARY_ITEM_SHARED)); + + item->shared->links = 1; + *allocated_bytes += size; + } + +#ifdef NETDATA_INTERNAL_CHECKS + item->dict = dict; +#endif + return item; +} + +static inline void *dict_item_value_mallocz(DICTIONARY *dict, size_t value_len) { + if(dict->value_aral) { + internal_fatal(aral_element_size(dict->value_aral) != value_len, + "DICTIONARY: item value size %zu does not match the configured fixed one %zu", + value_len, aral_element_size(dict->value_aral)); + return aral_mallocz(dict->value_aral); + } + else + return mallocz(value_len); +} + +static inline void dict_item_value_freez(DICTIONARY *dict, void *ptr) { + if(dict->value_aral) + aral_freez(dict->value_aral, ptr); + else + freez(ptr); +} + +static inline void *dict_item_value_create(DICTIONARY *dict, void *value, size_t value_len) { + void *ptr = NULL; + + if(likely(value_len)) { + if (likely(value)) { + // a value has been supplied + // copy it + ptr = dict_item_value_mallocz(dict, value_len); + memcpy(ptr, value, value_len); + } + else { + // no value has been supplied + // allocate a clear memory block + ptr = dict_item_value_mallocz(dict, value_len); + memset(ptr, 0, value_len); + } + } + // else + // the caller wants an item without any value + + return ptr; +} + +static inline DICTIONARY_ITEM *dict_item_create_with_hooks(DICTIONARY *dict, const char *name, size_t name_len, void *value, size_t value_len, void *constructor_data, DICTIONARY_ITEM *master_item) { +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(name_len > KEY_LEN_MAX)) + fatal("DICTIONARY: tried to index a key of size %zu, but the maximum acceptable is %zu", name_len, (size_t)KEY_LEN_MAX); + + if(unlikely(value_len > VALUE_LEN_MAX)) + fatal("DICTIONARY: tried to add an item of size %zu, but the maximum acceptable is %zu", value_len, (size_t)VALUE_LEN_MAX); +#endif + + size_t item_size = 0, key_size = 0, value_size = 0; + + DICTIONARY_ITEM *item = dict_item_create(dict, &item_size, master_item); + key_size += item_set_name(dict, item, name, name_len); + + if(unlikely(is_view_dictionary(dict))) { + // we are on a view dictionary + // do not touch the value + ; + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(!master_item)) + fatal("DICTIONARY: cannot add an item to a view without a master item."); +#endif + } + else { + // we are on the master dictionary + + if(unlikely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) + item->shared->value = value; + else + item->shared->value = dict_item_value_create(dict, value, value_len); + + item->shared->value_len = value_len; + value_size += value_len; + + dictionary_execute_insert_callback(dict, item, constructor_data); + } + + DICTIONARY_ENTRIES_PLUS1(dict); + DICTIONARY_STATS_PLUS_MEMORY(dict, key_size, item_size, value_size); + + return item; +} + +static inline void dict_item_reset_value_with_hooks(DICTIONARY *dict, 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__ ); + + netdata_log_debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", item_get_name(item)); + + DICTIONARY_VALUE_RESETS_PLUS1(dict); + + 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); + } + + dictionary_execute_delete_callback(dict, item); + + if(likely(dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE)) { + netdata_log_debug(D_DICTIONARY, "Dictionary: linking value to '%s'", item_get_name(item)); + item->shared->value = value; + item->shared->value_len = value_len; + } + else { + netdata_log_debug(D_DICTIONARY, "Dictionary: cloning value to '%s'", item_get_name(item)); + + void *old_value = item->shared->value; + void *new_value = NULL; + if(value_len) { + new_value = dict_item_value_mallocz(dict, value_len); + if(value) memcpy(new_value, value, value_len); + else memset(new_value, 0, value_len); + } + item->shared->value = new_value; + item->shared->value_len = value_len; + + netdata_log_debug(D_DICTIONARY, "Dictionary: freeing old value of '%s'", item_get_name(item)); + dict_item_value_freez(dict, old_value); + } + + dictionary_execute_insert_callback(dict, item, constructor_data); +} + +static inline size_t dict_item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item) { + netdata_log_debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", item_get_name(item)); + + if(!item_flag_check(item, ITEM_FLAG_DELETED)) + DICTIONARY_ENTRIES_MINUS1(dict); + + size_t item_size = 0, key_size = 0, value_size = 0; + + key_size += item->key_len; + if(unlikely(!(dict->options & DICT_OPTION_NAME_LINK_DONT_CLONE))) + item_free_name(dict, item); + + 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))) { + netdata_log_debug(D_DICTIONARY, "Dictionary freeing value of '%s'", item_get_name(item)); + dict_item_value_freez(dict, item->shared->value); + item->shared->value = NULL; + } + value_size += item->shared->value_len; + + aral_freez(dict_shared_items_aral, item->shared); + item->shared = NULL; + item_size += sizeof(DICTIONARY_ITEM_SHARED); + } + + aral_freez(dict_items_aral, item); + + item_size += sizeof(DICTIONARY_ITEM); + + DICTIONARY_STATS_MINUS_MEMORY(dict, key_size, item_size, value_size); + + // we return the memory we actually freed + return item_size + ((dict->options & DICT_OPTION_VALUE_LINK_DONT_CLONE) ? 0 : value_size); +} + +// ---------------------------------------------------------------------------- +// linked list management + +static inline void item_linked_list_add(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + if(dict->options & DICT_OPTION_ADD_IN_FRONT) + DOUBLE_LINKED_LIST_PREPEND_ITEM_UNSAFE(dict->items.list, item, prev, next); + else + DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(dict->items.list, item, prev, next); + +#ifdef NETDATA_INTERNAL_CHECKS + item->ll_adder_pid = gettid_cached(); +#endif + + // clear the BEING created flag, + // after it has been inserted into the linked list + item_flag_clear(item, ITEM_FLAG_BEING_CREATED); + + garbage_collect_pending_deletes(dict); + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); +} + +static inline void item_linked_list_remove(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ll_recursive_lock(dict, DICTIONARY_LOCK_WRITE); + + DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(dict->items.list, item, prev, next); + +#ifdef NETDATA_INTERNAL_CHECKS + item->ll_remover_pid = gettid_cached(); +#endif + + garbage_collect_pending_deletes(dict); + ll_recursive_unlock(dict, DICTIONARY_LOCK_WRITE); +} + +// ---------------------------------------------------------------------------- +// item operations + +static inline void dict_item_shared_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + if(is_master_dictionary(dict)) { + item_shared_flag_set(item, ITEM_FLAG_DELETED); + + if(dict->hooks) + __atomic_store_n(&dict->hooks->last_master_deletion_us, now_realtime_usec(), __ATOMIC_RELAXED); + } +} + +// returns true if we set the deleted flag on this item +static inline bool dict_item_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item) { + ITEM_FLAGS expected, desired; + + expected = __atomic_load_n(&item->flags, __ATOMIC_RELAXED); + + do { + + if (expected & ITEM_FLAG_DELETED) + return false; + + desired = expected | ITEM_FLAG_DELETED; + + } while(!__atomic_compare_exchange_n(&item->flags, &expected, desired, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)); + + DICTIONARY_ENTRIES_MINUS1(dict); + return true; +} + +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; + + 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; + + case RC_ITEM_IS_CURRENTLY_BEING_DELETED: + // an item that is currently being deleted by someone else - don't touch it + break; + + default: + internal_error(true, "Hey dev! You forgot to add the new condition here!"); + break; + } +} + +// 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); + + item_release(dict, item); + + 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); + + item_linked_list_remove(dict, item); + dict_item_free_with_hooks(dict, item); + } + } + else { + // we can't do anything under this mode + item_release(dict, item); + } +} + +static inline bool dict_item_del(DICTIONARY *dict, const char *name, ssize_t name_len) { + if(name_len == -1) + name_len = (ssize_t)strlen(name); + + netdata_log_debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); + + // 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_index_lock_wrlock(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) + netdata_log_error("DICTIONARY: INTERNAL ERROR: tried to delete item with name '%s', " + "name_len %zd that is not in the index", + name, name_len); + else + pointer_del(dict, item); + + dictionary_index_wrlock_unlock(dict); + + dict_item_free_or_mark_deleted(dict, item); + ret = true; + } + + return ret; +} + +static inline 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(is_dictionary_destroyed(dict))) { + internal_error(true, "DICTIONARY: attempted to dictionary_set() on a destroyed dictionary"); + return NULL; + } + + if(name_len == -1) + name_len = (ssize_t)strlen(name); + + netdata_log_debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); + + // DISCUSSION: + // Is it better to gain a read-lock and do a hashtable_get_unsafe() + // before we write lock to do hashtable_insert_unsafe()? + // + // Probably this depends on the use case. + // For statsd for example that does dictionary_set() to update received values, + // it could be beneficial to do a get() before we insert(). + // + // 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. + + dictionary_index_lock_wrlock(dict); + + bool added_or_updated = false; + size_t spins = 0; + DICTIONARY_ITEM *item = NULL; + do { + void *handle = hashtable_insert_unsafe(dict, name, name_len); + item = hashtable_insert_handle_to_item_unsafe(dict, handle); + if (likely(item == NULL)) { + // a new item added to the index + + // create the dictionary item + item = dict_item_create_with_hooks(dict, name, name_len, value, value_len, constructor_data, master_item); + + pointer_add(dict, item); + + hashtable_set_item_unsafe(dict, handle, item); + + // unlock the index lock, before we add it to the linked list + // DON'T 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 { + pointer_check(dict, item); + + if(item_check_and_acquire_advanced(dict, item, 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. + + if(is_view_dictionary(dict)) { + // view dictionary + // the item is already there and can be used + if(item->shared != master_item->shared) + netdata_log_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)) + DICTIONARY_STATS_INSERT_SPINS_PLUS(dict, spins); + + if(is_master_dictionary(dict) && added_or_updated) + dictionary_execute_react_callback(dict, item, constructor_data); + + return item; +} + +static inline 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(is_dictionary_destroyed(dict))) { + internal_error(true, "DICTIONARY: attempted to dictionary_get() on a destroyed dictionary"); + return NULL; + } + + if(name_len == -1) + name_len = (ssize_t)strlen(name); + + netdata_log_debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name); + + 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); + } + + dictionary_index_rdlock_unlock(dict); + + return item; +} + + +#endif //NETDATA_DICTIONARY_ITEM_H |