@cryptotaxi247 / netdata
Code Commits Issues Pulls Sessions CI/CD
master
master
h 261 lines 11.5 KB
Raw
1 // SPDX-License-Identifier: GPL-3.0-or-later
2
3 #ifndef NETDATA_DICTIONARY_INTERNALS_H
4 #define NETDATA_DICTIONARY_INTERNALS_H
5
6 #define DICTIONARY_INTERNALS
7 #include "../libnetdata.h"
8
9 // runtime flags of the dictionary - must be checked with atomics
10 typedef enum __attribute__ ((__packed__)) {
11 DICT_FLAG_NONE = 0,
12 DICT_FLAG_DESTROYED = (1 << 0), // this dictionary has been destroyed
13 DICT_FLAG_QUEUED_FOR_DESTRUCTION = (1 << 1), // this dictionary is queued for delayed destruction
14 } DICT_FLAGS;
15
16 #define dict_flag_check(dict, flag) (__atomic_load_n(&((dict)->flags), __ATOMIC_RELAXED) & (flag))
17 #define dict_flag_set(dict, flag) __atomic_or_fetch(&((dict)->flags), flag, __ATOMIC_RELAXED)
18 #define dict_flag_clear(dict, flag) __atomic_and_fetch(&((dict)->flags), ~(flag), __ATOMIC_RELAXED)
19
20 // flags macros
21 #define is_dictionary_destroyed(dict) dict_flag_check(dict, DICT_FLAG_DESTROYED)
22
23 // configuration options macros
24 #define is_dictionary_single_threaded(dict) ((dict)->options & DICT_OPTION_SINGLE_THREADED)
25 #define is_view_dictionary(dict) ((dict)->master)
26 #define is_master_dictionary(dict) (!is_view_dictionary(dict))
27
28 typedef enum __attribute__ ((__packed__)) item_options {
29 ITEM_OPTION_NONE = 0,
30 ITEM_OPTION_ALLOCATED_NAME = (1 << 0), // the name pointer is a STRING
31
32 // IMPORTANT: This is 1-bit - to add more change ITEM_OPTIONS_BITS
33 } ITEM_OPTIONS;
34
35 typedef enum __attribute__ ((__packed__)) item_flags {
36 ITEM_FLAG_NONE = 0,
37 ITEM_FLAG_DELETED = (1 << 0), // this item is marked deleted, so it is not available for traversal (deleted from the index too)
38 ITEM_FLAG_BEING_CREATED = (1 << 1), // this item is currently being created - this flag is removed when construction finishes
39
40 // IMPORTANT: This is 8-bit
41 } ITEM_FLAGS;
42
43 #define item_flag_check(item, flag) (__atomic_load_n(&((item)->flags), __ATOMIC_RELAXED) & (flag))
44 #define item_flag_set(item, flag) __atomic_or_fetch(&((item)->flags), flag, __ATOMIC_RELAXED)
45 #define item_flag_clear(item, flag) __atomic_and_fetch(&((item)->flags), ~(flag), __ATOMIC_RELAXED)
46
47 #define item_shared_flag_check(item, flag) (__atomic_load_n(&((item)->shared->flags), __ATOMIC_RELAXED) & (flag))
48 #define item_shared_flag_set(item, flag) __atomic_or_fetch(&((item)->shared->flags), flag, __ATOMIC_RELAXED)
49 #define item_shared_flag_clear(item, flag) __atomic_and_fetch(&((item)->shared->flags), ~(flag), __ATOMIC_RELAXED)
50
51 #define ITEM_FLAGS_TYPE uint8_t
52 #define KEY_LEN_TYPE uint32_t
53 #define VALUE_LEN_TYPE uint32_t
54
55 #define ITEM_OPTIONS_BITS 1
56 #define KEY_LEN_BITS ((sizeof(KEY_LEN_TYPE) * 8) - (sizeof(ITEM_FLAGS_TYPE) * 8) - ITEM_OPTIONS_BITS)
57 #define KEY_LEN_MAX ((1 << KEY_LEN_BITS) - 1)
58
59 #define VALUE_LEN_BITS ((sizeof(VALUE_LEN_TYPE) * 8) - (sizeof(ITEM_FLAGS_TYPE) * 8))
60 #define VALUE_LEN_MAX ((1 << VALUE_LEN_BITS) - 1)
61
62
63 /*
64 * Every item in the dictionary has the following structure.
65 */
66
67 typedef struct dictionary_item_shared {
68 void *value; // the value of the dictionary item
69
70 // the order of the following items is important!
71 // The total of their storage should be 64-bits
72
73 REFCOUNT links; // how many links this item has
74 VALUE_LEN_TYPE value_len:VALUE_LEN_BITS; // the size of the value
75 ITEM_FLAGS_TYPE flags; // shared flags
76 } DICTIONARY_ITEM_SHARED;
77
78 struct dictionary_item {
79 #ifdef FSANITIZE_ADDRESS
80 STACKTRACE_ARRAY stacktraces; // stack traces from all acquisition points
81 #endif
82 #if defined(FSANITIZE_ADDRESS) || defined(NETDATA_INTERNAL_CHECKS)
83 DICTIONARY *dict; // the dictionary this item belongs to
84 #endif
85 #ifdef NETDATA_INTERNAL_CHECKS
86 pid_t creator_pid;
87 pid_t deleter_pid;
88 pid_t ll_adder_pid;
89 pid_t ll_remover_pid;
90 #endif
91
92 DICTIONARY_ITEM_SHARED *shared;
93
94 struct dictionary_item *next; // a double linked list to allow fast insertions and deletions
95 struct dictionary_item *prev;
96
97 union {
98 STRING *string_name; // the name of the dictionary item
99 char *caller_name; // the user supplied string pointer
100 // void *key_ptr; // binary key pointer
101 };
102
103 // the order of the following items is important!
104 // The total of their storage should be 64-bits
105
106 REFCOUNT refcount; // the private reference counter
107
108 KEY_LEN_TYPE key_len:KEY_LEN_BITS; // the size of key indexed (for strings, including the null terminator)
109 // this is (2^23 - 1) = 8.388.607 bytes max key length.
110
111 ITEM_OPTIONS options:ITEM_OPTIONS_BITS; // permanent configuration options
112 // (no atomic operations on this - they never change)
113
114 ITEM_FLAGS_TYPE flags; // runtime changing flags for this item (atomic operations on this)
115 // cannot be a bit field because of atomics.
116 };
117
118 struct dictionary_hooks {
119 REFCOUNT links;
120 usec_t last_master_deletion_us;
121
122 dict_cb_insert_t insert_callback;
123 void *insert_callback_data;
124
125 dict_cb_conflict_t conflict_callback;
126 void *conflict_callback_data;
127
128 dict_cb_react_t react_callback;
129 void *react_callback_data;
130
131 dict_cb_delete_t delete_callback;
132 void *delelte_callback_data;
133 };
134
135 struct dictionary {
136 #ifdef FSANITIZE_ADDRESS
137 STACKTRACE_ARRAY stacktraces; // stack traces from all acquisition points
138 #endif
139
140 usec_t last_gc_run_us;
141 DICT_OPTIONS options; // the configuration flags of the dictionary (they never change - no atomics)
142 DICT_FLAGS flags; // run time flags for the dictionary (they change all the time - atomics needed)
143
144 ARAL *value_aral;
145
146 struct { // support for multiple indexing engines
147 Pvoid_t JudyHSArray; // the hash table
148 RW_SPINLOCK rw_spinlock; // protect the index
149 } index;
150
151 struct {
152 DICTIONARY_ITEM *list; // the double linked list of all items in the dictionary
153 RW_SPINLOCK rw_spinlock; // protect the linked-list
154 pid_t writer_pid; // the gettid() of the writer
155 uint32_t writer_depth; // nesting of write locks
156 } items;
157
158 struct dictionary_hooks *hooks; // pointer to external function callbacks to be called at certain points
159 struct dictionary_stats *stats; // statistics data, when DICT_OPTION_STATS is set
160
161 DICTIONARY *master; // the master dictionary
162 DICTIONARY *next; // linked list for delayed destruction (garbage collection of whole dictionaries)
163
164 uint32_t version; // the current version of the dictionary
165 // it is incremented when:
166 // - item added
167 // - item removed
168 // - item value reset
169 // - conflict callback returns true
170 // - function dictionary_version_increment() is called
171
172 int32_t entries; // how many items are currently in the index (the linked list may have more)
173 int32_t referenced_items; // how many items of the dictionary are currently being used by 3rd parties
174 int32_t pending_deletion_items; // how many items of the dictionary have been deleted, but have not been removed yet
175
176 #ifdef NETDATA_DICTIONARY_VALIDATE_POINTERS
177 netdata_mutex_t global_pointer_registry_mutex;
178 Pvoid_t global_pointer_registry;
179 #endif
180 };
181
182 // ----------------------------------------------------------------------------
183 // forward definitions of functions used in reverse order in the code
184
185 void garbage_collect_pending_deletes(DICTIONARY *dict);
186 static inline void item_linked_list_remove(DICTIONARY *dict, DICTIONARY_ITEM *item);
187 static size_t dict_item_free_with_hooks(DICTIONARY *dict, DICTIONARY_ITEM *item);
188 static inline const char *item_get_name(const DICTIONARY_ITEM *item);
189 static inline int hashtable_delete_unsafe(DICTIONARY *dict, const char *name, size_t name_len, DICTIONARY_ITEM *item);
190 static void item_release(DICTIONARY *dict, DICTIONARY_ITEM *item);
191 static bool dict_item_set_deleted(DICTIONARY *dict, DICTIONARY_ITEM *item);
192
193 #define RC_ITEM_OK ( 0)
194 #define RC_ITEM_MARKED_FOR_DELETION (-1) // the item is marked for deletion
195 #define RC_ITEM_IS_CURRENTLY_BEING_DELETED (-2) // the item is currently being deleted
196 #define RC_ITEM_IS_CURRENTLY_BEING_CREATED (-3) // the item is currently being deleted
197 #define RC_ITEM_IS_REFERENCED (-4) // the item is currently referenced
198 #define item_check_and_acquire(dict, item) (item_check_and_acquire_advanced(dict, item, false) == RC_ITEM_OK)
199 static int item_check_and_acquire_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item, bool having_index_lock);
200 #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)
201 static inline int item_is_not_referenced_and_can_be_removed_advanced(DICTIONARY *dict, DICTIONARY_ITEM *item);
202
203 // ----------------------------------------------------------------------------
204 // validate each pointer is indexed once - internal checks only
205
206 #ifdef NETDATA_DICTIONARY_VALIDATE_POINTERS
207 static inline void pointer_index_init(DICTIONARY *dict __maybe_unused) {
208 netdata_mutex_init(&dict->global_pointer_registry_mutex);
209 }
210
211 static inline void pointer_destroy_index(DICTIONARY *dict __maybe_unused) {
212 netdata_mutex_lock(&dict->global_pointer_registry_mutex);
213 JudyHSFreeArray(&dict->global_pointer_registry, PJE0);
214 netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
215 }
216 static inline void pointer_add(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) {
217 netdata_mutex_lock(&dict->global_pointer_registry_mutex);
218 Pvoid_t *PValue = JudyHSIns(&dict->global_pointer_registry, &item, sizeof(void *), PJE0);
219 if(*PValue != NULL)
220 fatal("pointer already exists in registry");
221 *PValue = item;
222 netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
223 }
224
225 static inline void pointer_check(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) {
226 netdata_mutex_lock(&dict->global_pointer_registry_mutex);
227 Pvoid_t *PValue = JudyHSGet(dict->global_pointer_registry, &item, sizeof(void *));
228 if(PValue == NULL)
229 fatal("pointer is not found in registry");
230 netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
231 }
232
233 static inline void pointer_del(DICTIONARY *dict __maybe_unused, DICTIONARY_ITEM *item __maybe_unused) {
234 netdata_mutex_lock(&dict->global_pointer_registry_mutex);
235 int ret = JudyHSDel(&dict->global_pointer_registry, &item, sizeof(void *), PJE0);
236 if(!ret)
237 fatal("pointer to be deleted does not exist in registry");
238 netdata_mutex_unlock(&dict->global_pointer_registry_mutex);
239 }
240 #else // !NETDATA_DICTIONARY_VALIDATE_POINTERS
241 #define pointer_index_init(dict) debug_dummy()
242 #define pointer_destroy_index(dict) debug_dummy()
243 #define pointer_add(dict, item) debug_dummy()
244 #define pointer_check(dict, item) debug_dummy()
245 #define pointer_del(dict, item) debug_dummy()
246 #endif // !NETDATA_DICTIONARY_VALIDATE_POINTERS
247
248 extern ARAL *dict_items_aral;
249 extern ARAL *dict_shared_items_aral;
250
251 size_t dictionary_destroy_delayed_count(void);
252
253 #include "dictionary-debug.h"
254 #include "dictionary-statistics.h"
255 #include "dictionary-locks.h"
256 #include "dictionary-refcount.h"
257 #include "dictionary-hashtable.h"
258 #include "dictionary-callbacks.h"
259 #include "dictionary-item.h"
260
261 #endif //NETDATA_DICTIONARY_INTERNALS_H