diff options
author | Costa Tsaousis <costa@netdata.cloud> | 2022-09-19 23:46:13 +0300 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-09-19 23:46:13 +0300 |
commit | cb7af25c09d8775d1967cb0553268075cda868d4 (patch) | |
tree | 9e86bc359bb2b1ec72d3a1382236703dc633ad63 /libnetdata | |
parent | 62246029160025a8d6503d9fbb617c7b029b9126 (diff) |
RRD structures managed by dictionaries (#13646)
* rrdset - in progress
* rrdset optimal constructor; rrdset conflict
* rrdset final touches
* re-organization of rrdset object members
* prevent use-after-free
* dictionary dfe supports also counting of iterations
* rrddim managed by dictionary
* rrd.h cleanup
* DICTIONARY_ITEM now is referencing actual dictionary items in the code
* removed rrdset linked list
* Revert "removed rrdset linked list"
This reverts commit 690d6a588b4b99619c2c5e10f84e8f868ae6def5.
* removed rrdset linked list
* added comments
* Switch chart uuid to static allocation in rrdset
Remove unused functions
* rrdset_archive() and friends...
* always create rrdfamily
* enable ml_free_dimension
* rrddim_foreach done with dfe
* most custom rrddim loops replaced with rrddim_foreach
* removed accesses to rrddim->dimensions
* removed locks that are no longer needed
* rrdsetvar is now managed by the dictionary
* set rrdset is rrdsetvar, fixes https://github.com/netdata/netdata/pull/13646#issuecomment-1242574853
* conflict callback of rrdsetvar now properly checks if it has to reset the variable
* dictionary registered callbacks accept as first parameter the DICTIONARY_ITEM
* dictionary dfe now uses internal counter to report; avoided excess variables defined with dfe
* dictionary walkthrough callbacks get dictionary acquired items
* dictionary reference counters that can be dupped from zero
* added advanced functions for get and del
* rrdvar managed by dictionaries
* thread safety for rrdsetvar
* faster rrdvar initialization
* rrdvar string lengths should match in all add, del, get functions
* rrdvar internals hidden from the rest of the world
* rrdvar is now acquired throughout netdata
* hide the internal structures of rrdsetvar
* rrdsetvar is now acquired through out netdata
* rrddimvar managed by dictionary; rrddimvar linked list removed; rrddimvar structures hidden from the rest of netdata
* better error handling
* dont create variables if not initialized for health
* dont create variables if not initialized for health again
* rrdfamily is now managed by dictionaries; references of it are acquired dictionary items
* type checking on acquired objects
* rrdcalc renaming of functions
* type checking for rrdfamily_acquired
* rrdcalc managed by dictionaries
* rrdcalc double free fix
* host rrdvars is always needed
* attempt to fix deadlock 1
* attempt to fix deadlock 2
* Remove unused variable
* attempt to fix deadlock 3
* snprintfz
* rrdcalc index in rrdset fix
* Stop storing active charts and computing chart hashes
* Remove store active chart function
* Remove compute chart hash function
* Remove sql_store_chart_hash function
* Remove store_active_dimension function
* dictionary delayed destruction
* formatting and cleanup
* zero dictionary base on rrdsetvar
* added internal error to log delayed destructions of dictionaries
* typo in rrddimvar
* added debugging info to dictionary
* debug info
* fix for rrdcalc keys being empty
* remove forgotten unlock
* remove deadlock
* Switch to metadata version 5 and drop
chart_hash
chart_hash_map
chart_active
dimension_active
v_chart_hash
* SQL cosmetic changes
* do not busy wait while destroying a referenced dictionary
* remove deadlock
* code cleanup; re-organization;
* fast cleanup and flushing of dictionaries
* number formatting fixes
* do not delete configured alerts when archiving a chart
* rrddim obsolete linked list management outside dictionaries
* removed duplicate contexts call
* fix crash when rrdfamily is not initialized
* dont keep rrddimvar referenced
* properly cleanup rrdvar
* removed some locks
* Do not attempt to cleanup chart_hash / chart_hash_map
* rrdcalctemplate managed by dictionary
* register callbacks on the right dictionary
* removed some more locks
* rrdcalc secondary index replaced with linked-list; rrdcalc labels updates are now executed by health thread
* when looking up for an alarm look using both chart id and chart name
* host initialization a bit more modular
* init rrdlabels on host update
* preparation for dictionary views
* improved comment
* unused variables without internal checks
* service threads isolation and worker info
* more worker info in service thread
* thread cancelability debugging with internal checks
* strings data races addressed; fixes https://github.com/netdata/netdata/issues/13647
* dictionary modularization
* Remove unused SQL statement definition
* unit-tested thread safety of dictionaries; removed data race conditions on dictionaries and strings; dictionaries now can detect if the caller is holds a write lock and automatically all the calls become their unsafe versions; all direct calls to unsafe version is eliminated
* remove worker_is_idle() from the exit of service functions, because we lose the lock time between loops
* rewritten dictionary to have 2 separate locks, one for indexing and another for traversal
* Update collectors/cgroups.plugin/sys_fs_cgroup.c
Co-authored-by: Vladimir Kobal <vlad@prokk.net>
* Update collectors/cgroups.plugin/sys_fs_cgroup.c
Co-authored-by: Vladimir Kobal <vlad@prokk.net>
* Update collectors/proc.plugin/proc_net_dev.c
Co-authored-by: Vladimir Kobal <vlad@prokk.net>
* fix memory leak in rrdset cache_dir
* minor dictionary changes
* dont use index locks in single threaded
* obsolete dict option
* rrddim options and flags separation; rrdset_done() optimization to keep array of reference pointers to rrddim;
* fix jump on uninitialized value in dictionary; remove double free of cache_dir
* addressed codacy findings
* removed debugging code
* use the private refcount on dictionaries
* make dictionary item desctructors work on dictionary destruction; strictier control on dictionary API; proper cleanup sequence on rrddim;
* more dictionary statistics
* global statistics about dictionary operations, memory, items, callbacks
* dictionary support for views - missing the public API
* removed warning about unused parameter
* chart and context name for cloud
* chart and context name for cloud, again
* dictionary statistics fixed; first implementation of dictionary views - not currently used
* only the master can globally delete an item
* context needs netdata prefix
* fix context and chart it of spins
* fix for host variables when health is not enabled
* run garbage collector on item insert too
* Fix info message; remove extra "using"
* update dict unittest for new placement of garbage collector
* we need RRDHOST->rrdvars for maintaining custom host variables
* Health initialization needs the host->host_uuid
* split STRING to its own files; no code changes other than that
* initialize health unconditionally
* unit tests do not pollute the global scope with their variables
* Skip initialization when creating archived hosts on startup. When a child connects it will initialize properly
Co-authored-by: Stelios Fragkakis <52996999+stelfrag@users.noreply.github.com>
Co-authored-by: Vladimir Kobal <vlad@prokk.net>
Diffstat (limited to 'libnetdata')
-rw-r--r-- | libnetdata/Makefile.am | 1 | ||||
-rw-r--r-- | libnetdata/dictionary/README.md | 18 | ||||
-rw-r--r-- | libnetdata/dictionary/dictionary.c | 3539 | ||||
-rw-r--r-- | libnetdata/dictionary/dictionary.h | 283 | ||||
-rw-r--r-- | libnetdata/libnetdata.h | 1 | ||||
-rw-r--r-- | libnetdata/locks/README.md | 6 | ||||
-rw-r--r-- | libnetdata/log/log.c | 11 | ||||
-rw-r--r-- | libnetdata/required_dummies.h | 2 | ||||
-rw-r--r-- | libnetdata/string/Makefile.am | 8 | ||||
-rw-r--r-- | libnetdata/string/README.md | 20 | ||||
-rw-r--r-- | libnetdata/string/string.c | 595 | ||||
-rw-r--r-- | libnetdata/string/string.h | 30 | ||||
-rw-r--r-- | libnetdata/threads/threads.c | 29 | ||||
-rw-r--r-- | libnetdata/threads/threads.h | 7 |
14 files changed, 2979 insertions, 1571 deletions
diff --git a/libnetdata/Makefile.am b/libnetdata/Makefile.am index 5962323e87..1208d16c21 100644 --- a/libnetdata/Makefile.am +++ b/libnetdata/Makefile.am @@ -25,6 +25,7 @@ SUBDIRS = \ socket \ statistical \ storage_number \ + string \ threads \ url \ worker_utilization \ diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md index 879c1bcc1c..bcd78ea262 100644 --- a/libnetdata/dictionary/README.md +++ b/libnetdata/dictionary/README.md @@ -18,7 +18,7 @@ Dictionaries provide an interface to: - **Delete** an item from the dictionary (provided its `name`) - **Traverse** the list of items in the dictionary -Dictionaries are **ordered**, meaning that the order they have been added is preserved while traversing them. The caller may reverse this order by passing the flag `DICTIONARY_FLAG_ADD_IN_FRONT` when creating the dictionary. +Dictionaries are **ordered**, meaning that the order they have been added is preserved while traversing them. The caller may reverse this order by passing the flag `DICT_OPTION_ADD_IN_FRONT` when creating the dictionary. Dictionaries guarantee **uniqueness** of all items added to them, meaning that only one item with a given name can exist in the dictionary at any given time. @@ -35,21 +35,21 @@ In **clone** mode, the dictionary guarantees that all operations on the dictiona 1.`dictionary_register_insert_callback()` that will be called just after the insertion of an item to the dictionary, or after the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled). 2. `dictionary_register_delete_callback()` that will be called just prior to the deletion of an item from the dictionary, or prior to the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled). - 3. `dictionary_register_conflict_callback()` that will be called when `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` is set and another value is attempted to be inserted for the same key. + 3. `dictionary_register_conflict_callback()` that will be called when `DICT_OPTION_DONT_OVERWRITE_VALUE` is set and another value is attempted to be inserted for the same key. In **link** mode, the name and/or the value are just linked to the dictionary item, and it is the user's responsibility to free the memory they use after an item is deleted from the dictionary or when the dictionary is destroyed. By default, **clone** mode is used for both the name and the value. -To use **link** mode for names, add `DICTIONARY_FLAG_NAME_LINK_DONT_CLONE` to the flags when creating the dictionary. +To use **link** mode for names, add `DICT_OPTION_NAME_LINK_DONT_CLONE` to the flags when creating the dictionary. -To use **link** mode for values, add `DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE` to the flags when creating the dictionary. +To use **link** mode for values, add `DICT_OPTION_VALUE_LINK_DONT_CLONE` to the flags when creating the dictionary. ## Locks The dictionary allows both **single-threaded** operation (no locks - faster) and **multi-threaded** operation utilizing a read-write lock. -The default is **multi-threaded**. To enable **single-threaded** add `DICTIONARY_FLAG_SINGLE_THREADED` to the flags when creating the dictionary. +The default is **multi-threaded**. To enable **single-threaded** add `DICT_OPTION_SINGLE_THREADED` to the flags when creating the dictionary. ## Hash table operations @@ -72,7 +72,7 @@ This call is used to: - **add** an item to the dictionary. - **reset** the value of an existing item in the dictionary. -If **resetting** is not desired, add `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored. Optionally a conflict callback function can be registered, to manipulate (probably merge or extend) the original value, based on the new value attempted to be added to the dictionary. +If **resetting** is not desired, add `DICT_OPTION_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored. Optionally a conflict callback function can be registered, to manipulate (probably merge or extend) the original value, based on the new value attempted to be added to the dictionary. For **multi-threaded** operation, the `dictionary_set()` calls get an exclusive write lock on the dictionary. @@ -143,7 +143,7 @@ Example: ```c // create the dictionary -DICTIONARY *dict = dictionary_create(DICTIONARY_FLAGS_NONE); +DICTIONARY *dict = dictionary_create(DICT_OPTION_NONE); // add an item to it dictionary_set(dict, "name", "value", 6); @@ -189,7 +189,7 @@ There are 4 calls: - `dictionary_walkthrough_read()` and `dictionary_sorted_walkthrough_read()` that acquire a shared read lock, and they call a callback function for every item of the dictionary. The callback function may use the unsafe versions of the `dictionary_get()` calls to lookup other items in the dictionary, but it should not attempt to add or remove items to/from the dictionary. - `dictionary_walkthrough_write()` and `dictionary_sorted_walkthrough_write()` that acquire an exclusive write lock, and they call a callback function for every item of the dictionary. This is to be used when items need to be added to or removed from the dictionary. The `write` versions can be used to delete any or all the items from the dictionary, including the currently working one. For the `sorted` version, all items in the dictionary maintain a reference counter, so all deletions are deferred until the sorted walkthrough finishes.** -The non sorted versions traverse the items in the same order they have been added to the dictionary (or the reverse order if the flag `DICTIONARY_FLAG_ADD_IN_FRONT` is set during dictionary creation). The sorted versions sort alphabetically the items based on their name, and then they traverse them in the sorted order. +The non sorted versions traverse the items in the same order they have been added to the dictionary (or the reverse order if the flag `DICT_OPTION_ADD_IN_FRONT` is set during dictionary creation). The sorted versions sort alphabetically the items based on their name, and then they traverse them in the sorted order. The callback function returns an `int`. If this value is negative, traversal of the dictionary is stopped immediately and the negative value is returned to the caller. If the returned value of all callback calls is zero or positive, the walkthrough functions return the sum of the return values of all callbacks. So, if you are just interested to know how many items fall into some condition, write a callback function that returns 1 when the item satisfies that condition and 0 when it does not and the walkthrough function will return how many tested positive. @@ -241,5 +241,5 @@ Since the dictionary uses a hash table and a double linked list, if the contract This is currently used in statsd: -- the data collection thread uses only `get` and `set`. It never uses `del`. New items are added at the front of the linked list (`DICTIONARY_FLAG_ADD_IN_FRONT`). +- the data collection thread uses only `get` and `set`. It never uses `del`. New items are added at the front of the linked list (`DICT_OPTION_ADD_IN_FRONT`). - the flushing thread is only traversing the dictionary up to the point it last traversed it (it uses a flag for that to know where it stopped last time). It never uses `get`, `set` or `del`. diff --git a/libnetdata/dictionary/dictionary.c b/libnetdata/dictionary/dictionary.c index 259462e8b5..bec84f87a4 100644 --- a/libnetdata/dictionary/dictionary.c +++ b/libnetdata/dictionary/dictionary.c @@ -1,383 +1,708 @@ // SPDX-License-Identifier: GPL-3.0-or-later -// NOT TO BE USED BY USERS -#define DICTIONARY_FLAG_EXCLUSIVE_ACCESS (1 << 28) // there is only one thread accessing the dictionary -#define DICTIONARY_FLAG_DESTROYED (1 << 29) // this dictionary has been destroyed -#define DICTIONARY_FLAG_DEFER_ALL_DELETIONS (1 << 30) // 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) - #define DICTIONARY_INTERNALS #include "../libnetdata.h" #include <Judy.h> -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) +// 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; + +#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 deleted, so it is not available for traversal + + // 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) + +#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 { +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; #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; -struct dictionary { -#ifdef NETDATA_INTERNAL_CHECKS - const char *creation_function; - const char *creation_file; - size_t creation_line; -#endif + // the order of the following items is important! + // The total of their storage should be 64-bits - DICTIONARY_FLAGS flags; // the flags of the dictionary + REFCOUNT refcount; // the private reference counter - NAME_VALUE *first_item; // the double linked list base pointers - NAME_VALUE *last_item; + 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. - Pvoid_t JudyHSArray; // the hash table + ITEM_OPTIONS options:ITEM_OPTIONS_BITS; // permanent configuration options + // (no atomic operations on this - they never change) - netdata_rwlock_t rwlock; // the r/w lock when DICTIONARY_FLAG_SINGLE_THREADED is not set + 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 char *name, void *value, void *data); + void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data); void *ins_callback_data; - void (*react_callback)(const char *name, void *value, void *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 char *name, void *value, void *data); + void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data); void *del_callback_data; +}; - void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data); - void *conflict_callback_data; +struct dictionary_stats dictionary_stats_category_other = { + .name = "other", +}; + +struct dictionary { +#ifdef NETDATA_INTERNAL_CHECKS + const char *creation_function; + const char *creation_file; + size_t creation_line; +#endif - 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 + 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 + + DICTIONARY *master; // the master dictionary + DICTIONARY *next; // linked list for delayed destruction (garbage collection of whole dictionaries) + + 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 }; -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); +// 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 item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item); +static inline const char *item_get_name(const DICTIONARY_ITEM *item); +static bool item_is_not_referenced_and_can_be_removed(DICTIONARY *dict, 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); + +#define ITEM_OK 0 +#define ITEM_MARKED_FOR_DELETION (-1) // the item is marked for deletion +#define ITEM_IS_CURRENTLY_BEING_DELETED (-2) // the item is currently being deleted +#define item_check_and_acquire(dict, item) (item_check_and_acquire_advanced(dict, item, false) == ITEM_OK) +static int item_check_and_acquire_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item, bool having_index_lock); // ---------------------------------------------------------------------------- -// callbacks registration +// memory statistics + +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); + + if(item_size) + __atomic_fetch_add(&dict->stats->memory.dict, (long)item_size, __ATOMIC_RELAXED); -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; + 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); -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; + 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); } -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; +// ---------------------------------------------------------------------------- +// callbacks registration + +static inline void dictionary_hooks_allocate(DICTIONARY *dict) { + if(dict->hooks) return; + + dict->hooks = callocz(1, sizeof(struct dictionary_hooks)); + dict->hooks->links = 1; + + 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) { - if(unlikely(!dict)) return 0; - 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) { - if(unlikely(!dict)) return 0; - 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__ ); + + dictionary_hooks_allocate(dict); + dict->hooks->conflict_callback = conflict_callback; + dict->hooks->conflict_callback_data = data; } -size_t dictionary_stats_version(DICTIONARY *dict) { - if(unlikely(!dict)) return 0; - 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) { - if(unlikely(!dict)) return 0; - 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) { + +// ---------------------------------------------------------------------------- +// dictionary statistics API + +size_t dictionary_version(DICTIONARY *dict) { if(unlikely(!dict)) return 0; - return dict->inserts; + + // 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) { +size_t dictionary_entries(DICTIONARY *dict) { if(unlikely(!dict)) return 0; - return dict->deletes; + + // 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) { +size_t dictionary_referenced_items(DICTIONARY *dict) { if(unlikely(!dict)) return 0; - return dict->resets; + + 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) { + +long int dictionary_stats_for_registry(DICTIONARY *dict) { if(unlikely(!dict)) return 0; - return dict->walkthroughs; + return (dict->stats->memory.indexed + dict->stats->memory.dict); } -size_t dictionary_stats_referenced_items(DICTIONARY *dict) { - if(unlikely(!dict)) return 0; - 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); + + if(unlikely(is_dictionary_single_threaded(dict))) { dict->version++; - dict->deletes++; 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); + __atomic_fetch_sub(&dict->entries, 1, __ATOMIC_SEQ_CST); } } -static inline void DICTIONARY_STATS_ENTRIES_MINUS_MEMORY(DICTIONARY *dict, size_t size) { - if(dict->flags & DICTIONARY_FLAG_EXCLUSIVE_ACCESS) { - dict->memory -= (long)size; - } < |