| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #include "../libnetdata.h" |
| 4 | #include <Judy.h> |
| 5 | |
| 6 | // ---------------------------------------------------------------------------- |
| 7 | // STRING implementation - dedup all STRING |
| 8 | |
| 9 | #define STRING_PARTITION_SHIFTS (0) |
| 10 | #define STRING_PARTITIONS (256 >> STRING_PARTITION_SHIFTS) |
| 11 | #define string_partition_str(str) ((uint8_t)((str)[0]) >> STRING_PARTITION_SHIFTS) |
| 12 | #define string_partition(string) (string_partition_str((string)->str)) |
| 13 | |
| 14 | struct netdata_string { |
| 15 | uint32_t length; // the string length including the terminating '\0' |
| 16 | |
| 17 | REFCOUNT refcount; // how many times this string is used |
| 18 | // We use a signed number to be able to detect duplicate frees of a string. |
| 19 | // If at any point this goes below zero, we have a duplicate free. |
| 20 | |
| 21 | #ifdef FSANITIZE_ADDRESS |
| 22 | STACKTRACE_ARRAY stacktraces; // stack traces from all acquisition points |
| 23 | #endif |
| 24 | |
| 25 | const char str[]; // the string itself, is appended to this structure |
| 26 | }; |
| 27 | |
| 28 | static struct string_partition { |
| 29 | RW_SPINLOCK spinlock; // the R/W spinlock to protect the Judy array |
| 30 | |
| 31 | Pvoid_t JudyHSArray; // the Judy array - hashtable |
| 32 | |
| 33 | size_t inserts; // the number of successful inserts to the index |
| 34 | size_t deletes; // the number of successful deleted from the index |
| 35 | |
| 36 | long int entries; // the number of entries in the index |
| 37 | long int memory; // the memory used |
| 38 | long int memory_index; // JudyHS (accurate) |
| 39 | |
| 40 | #ifdef FSANITIZE_ADDRESS |
| 41 | Pvoid_t JudyLPointers; // JudyL array to keep track of all string pointers for traversal |
| 42 | #endif |
| 43 | |
| 44 | #ifdef NETDATA_INTERNAL_CHECKS |
| 45 | // internal statistics |
| 46 | struct { |
| 47 | size_t searches; // the number of successful searches in the index |
| 48 | size_t releases; // when a string is unreferenced |
| 49 | size_t duplications; // when a string is referenced |
| 50 | long int active_references; // the number of active references alive |
| 51 | } atomic; |
| 52 | |
| 53 | size_t found_deleted_on_search; |
| 54 | size_t found_available_on_search; |
| 55 | size_t found_deleted_on_insert; |
| 56 | size_t found_available_on_insert; |
| 57 | size_t spins; |
| 58 | #endif |
| 59 | |
| 60 | } string_base[STRING_PARTITIONS] = { 0 }; |
| 61 | |
| 62 | #ifdef NETDATA_INTERNAL_CHECKS |
| 63 | #define string_stats_atomic_increment(partition, var) __atomic_add_fetch(&string_base[partition].atomic.var, 1, __ATOMIC_RELAXED) |
| 64 | #define string_stats_atomic_decrement(partition, var) __atomic_sub_fetch(&string_base[partition].atomic.var, 1, __ATOMIC_RELAXED) |
| 65 | #define string_internal_stats_add(partition, var, val) __atomic_add_fetch(&string_base[partition].var, val, __ATOMIC_RELAXED) |
| 66 | #else |
| 67 | #define string_stats_atomic_increment(partition, var) do {;} while(0) |
| 68 | #define string_stats_atomic_decrement(partition, var) do {;} while(0) |
| 69 | #define string_internal_stats_add(partition, var, val) do {;} while(0) |
| 70 | #endif |
| 71 | |
| 72 | void string_statistics(size_t *inserts, size_t *deletes, size_t *searches, size_t *entries, size_t *references, size_t *memory, size_t *memory_index, size_t *duplications, size_t *releases) { |
| 73 | if (inserts) *inserts = 0; |
| 74 | if (deletes) *deletes = 0; |
| 75 | if (searches) *searches = 0; |
| 76 | if (entries) *entries = 0; |
| 77 | if (references) *references = 0; |
| 78 | if (memory) *memory = 0; |
| 79 | if (memory_index) *memory_index = 0; |
| 80 | if (duplications) *duplications = 0; |
| 81 | if (releases) *releases = 0; |
| 82 | |
| 83 | for(size_t i = 0; i < STRING_PARTITIONS ;i++) { |
| 84 | if (inserts) *inserts += string_base[i].inserts; |
| 85 | if (deletes) *deletes += string_base[i].deletes; |
| 86 | if (entries) *entries += (size_t) string_base[i].entries; |
| 87 | if (memory) *memory += (size_t) string_base[i].memory; |
| 88 | if (memory_index) *memory_index += (string_base[i].memory_index > 0) ? string_base[i].memory_index : 0; |
| 89 | |
| 90 | #ifdef NETDATA_INTERNAL_CHECKS |
| 91 | if (searches) *searches += string_base[i].atomic.searches; |
| 92 | if (references) *references += (size_t) string_base[i].atomic.active_references; |
| 93 | if (duplications) *duplications += string_base[i].atomic.duplications; |
| 94 | if (releases) *releases += string_base[i].atomic.releases; |
| 95 | #endif |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | static inline bool string_entry_check_and_acquire(STRING *se) { |
| 100 | #ifdef NETDATA_INTERNAL_CHECKS |
| 101 | uint8_t partition = string_partition(se); |
| 102 | #endif |
| 103 | |
| 104 | if(!refcount_acquire(&se->refcount)) |
| 105 | return false; |
| 106 | |
| 107 | // statistics |
| 108 | // string_base.active_references is altered at the in string_strdupz() and string_freez() |
| 109 | string_stats_atomic_increment(partition, duplications); |
| 110 | |
| 111 | return true; |
| 112 | } |
| 113 | |
| 114 | ALWAYS_INLINE |
| 115 | STRING *string_dup(STRING *string) { |
| 116 | if(unlikely(!string)) return NULL; |
| 117 | |
| 118 | if(!refcount_acquire(&string->refcount)) |
| 119 | fatal("STRING: tried to %s() a string that is deleted (refcount %d).", __FUNCTION__, string->refcount); |
| 120 | |
| 121 | #ifdef NETDATA_INTERNAL_CHECKS |
| 122 | uint8_t partition = string_partition(string); |
| 123 | #endif |
| 124 | |
| 125 | #ifdef FSANITIZE_ADDRESS |
| 126 | stacktrace_array_add(&string->stacktraces, 0); |
| 127 | #endif |
| 128 | |
| 129 | // statistics |
| 130 | string_stats_atomic_increment(partition, active_references); |
| 131 | string_stats_atomic_increment(partition, duplications); |
| 132 | |
| 133 | return string; |
| 134 | } |
| 135 | |
| 136 | // Search the index and return an ACQUIRED string entry, or NULL |
| 137 | static STRING *string_index_search(const char *str, size_t length, uint8_t partition) { |
| 138 | STRING *string; |
| 139 | |
| 140 | // Find the string in the index |
| 141 | // With a read-lock so that multiple readers can use the index concurrently. |
| 142 | |
| 143 | rw_spinlock_read_lock(&string_base[partition].spinlock); |
| 144 | |
| 145 | Pvoid_t *Rc; |
| 146 | Rc = JudyHSGet(string_base[partition].JudyHSArray, (void *)str, length - 1); |
| 147 | if(likely(Rc)) { |
| 148 | // found in the hash table |
| 149 | string = *Rc; |
| 150 | |
| 151 | if(string_entry_check_and_acquire(string)) { |
| 152 | // we can use this entry |
| 153 | string_internal_stats_add(partition, found_available_on_search, 1); |
| 154 | } |
| 155 | else { |
| 156 | // this entry is about to be deleted by another thread |
| 157 | // do not touch it, let it go... |
| 158 | string = NULL; |
| 159 | string_internal_stats_add(partition, found_deleted_on_search, 1); |
| 160 | } |
| 161 | } |
| 162 | else { |
| 163 | // not found in the hash table |
| 164 | string = NULL; |
| 165 | } |
| 166 | |
| 167 | string_stats_atomic_increment(partition, searches); |
| 168 | rw_spinlock_read_unlock(&string_base[partition].spinlock); |
| 169 | |
| 170 | return string; |
| 171 | } |
| 172 | |
| 173 | // Insert a string to the index and return an ACQUIRED string entry, |
| 174 | // or NULL if the call needs to be retried (a deleted entry with the same key is still in the index) |
| 175 | // The returned entry is ACQUIRED, and it can either be: |
| 176 | // 1. a new item inserted, or |
| 177 | // 2. an item found in the index that is not currently deleted |
| 178 | static STRING *string_index_insert(const char *str, size_t length, uint8_t partition) { |
| 179 | STRING *string; |
| 180 | |
| 181 | rw_spinlock_write_lock(&string_base[partition].spinlock); |
| 182 | |
| 183 | int64_t judy_mem = 0; |
| 184 | |
| 185 | STRING **ptr; |
| 186 | { |
| 187 | JError_t J_Error; |
| 188 | |
| 189 | JudyAllocThreadPulseReset(); |
| 190 | |
| 191 | Pvoid_t *Rc = JudyHSIns(&string_base[partition].JudyHSArray, (void *)str, length - 1, &J_Error); |
| 192 | |
| 193 | judy_mem = JudyAllocThreadPulseGetAndReset(); |
| 194 | |
| 195 | if (unlikely(Rc == PJERR)) { |
| 196 | fatal( |
| 197 | "STRING: Cannot insert entry to JudyHS, JU_ERRNO_* == %u, ID == %d", |
| 198 | JU_ERRNO(&J_Error), |
| 199 | JU_ERRID(&J_Error)); |
| 200 | } |
| 201 | ptr = (STRING **)Rc; |
| 202 | } |
| 203 | |
| 204 | if (likely(*ptr == 0)) { |
| 205 | // a new item added to the index |
| 206 | long mem_size = (long)sizeof(STRING) + (long)length; |
| 207 | string = mallocz(mem_size); |
| 208 | memcpy((char *)string->str, str, length - 1); |
| 209 | ((char *)string->str)[length - 1] = '\0'; |
| 210 | string->length = length; |
| 211 | string->refcount = 1; |
| 212 | |
| 213 | #ifdef FSANITIZE_ADDRESS |
| 214 | // Initialize stacktrace tracking |
| 215 | stacktrace_array_init(&string->stacktraces); |
| 216 | |
| 217 | // Add to JudyL array for tracking strings by pointer |
| 218 | Pvoid_t *PValue; |
| 219 | PValue = JudyLIns(&string_base[partition].JudyLPointers, (Word_t)string, PJE0); |
| 220 | if (PValue != PJERR) |
| 221 | *PValue = (void *)1; // Use a simple value of 1 for now |
| 222 | #endif |
| 223 | |
| 224 | *ptr = string; |
| 225 | string_base[partition].inserts++; |
| 226 | string_base[partition].entries++; |
| 227 | string_base[partition].memory += mem_size; |
| 228 | string_base[partition].memory_index += judy_mem; |
| 229 | } |
| 230 | else { |
| 231 | // the item is already in the index |
| 232 | string = *ptr; |
| 233 | |
| 234 | if(string_entry_check_and_acquire(string)) { |
| 235 | // we can use this entry |
| 236 | string_internal_stats_add(partition, found_available_on_insert, 1); |
| 237 | } |
| 238 | else { |
| 239 | // this entry is about to be deleted by another thread |
| 240 | // do not touch it, let it go... |
| 241 | string = NULL; |
| 242 | string_internal_stats_add(partition, found_deleted_on_insert, 1); |
| 243 | } |
| 244 | |
| 245 | string_stats_atomic_increment(partition, searches); |
| 246 | } |
| 247 | |
| 248 | rw_spinlock_write_unlock(&string_base[partition].spinlock); |
| 249 | return string; |
| 250 | } |
| 251 | |
| 252 | // delete an entry from the index |
| 253 | static void string_index_delete(STRING *string) { |
| 254 | uint8_t partition = string_partition(string); |
| 255 | |
| 256 | rw_spinlock_write_lock(&string_base[partition].spinlock); |
| 257 | |
| 258 | bool deleted = false; |
| 259 | int64_t judy_mem = 0; |
| 260 | |
| 261 | if (likely(string_base[partition].JudyHSArray)) { |
| 262 | JError_t J_Error; |
| 263 | |
| 264 | JudyAllocThreadPulseReset(); |
| 265 | |
| 266 | int ret = JudyHSDel(&string_base[partition].JudyHSArray, (void *)string->str, string->length - 1, &J_Error); |
| 267 | |
| 268 | judy_mem = JudyAllocThreadPulseGetAndReset(); |
| 269 | |
| 270 | if (unlikely(ret == JERR)) { |
| 271 | netdata_log_error( |
| 272 | "STRING: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d", |
| 273 | string->str, |
| 274 | JU_ERRNO(&J_Error), |
| 275 | JU_ERRID(&J_Error)); |
| 276 | } else |
| 277 | deleted = true; |
| 278 | } |
| 279 | |
| 280 | if (unlikely(!deleted)) |
| 281 | netdata_log_error("STRING: tried to delete '%s' that is not in the index. Ignoring it.", string->str); |
| 282 | else { |
| 283 | long mem_size = (long)sizeof(STRING) + (long)string->length; |
| 284 | string_base[partition].deletes++; |
| 285 | string_base[partition].entries--; |
| 286 | string_base[partition].memory -= mem_size; |
| 287 | string_base[partition].memory_index += judy_mem; |
| 288 | |
| 289 | #ifdef FSANITIZE_ADDRESS |
| 290 | // Remove from the JudyL array if it exists |
| 291 | if (string_base[partition].JudyLPointers) |
| 292 | JudyLDel(&string_base[partition].JudyLPointers, (Word_t)string, PJE0); |
| 293 | #endif |
| 294 | |
| 295 | freez(string); |
| 296 | } |
| 297 | |
| 298 | rw_spinlock_write_unlock(&string_base[partition].spinlock); |
| 299 | } |
| 300 | |
| 301 | ALWAYS_INLINE |
| 302 | STRING *string_strdupz(const char *str) { |
| 303 | size_t length = 0; |
| 304 | if(likely(str)) |
| 305 | length = strlen(str); |
| 306 | |
| 307 | if(unlikely(!length)) return NULL; |
| 308 | |
| 309 | length++; |
| 310 | uint8_t partition = string_partition_str(str); |
| 311 | STRING *string = string_index_search(str, length, partition); |
| 312 | |
| 313 | while(!string) { |
| 314 | // The search above did not find anything, |
| 315 | // We loop here, because during insert we may find an entry that is being deleted by another thread. |
| 316 | // So, we have to let it go and retry to insert it again. |
| 317 | |
| 318 | string = string_index_insert(str, length, partition); |
| 319 | } |
| 320 | |
| 321 | // statistics |
| 322 | string_stats_atomic_increment(partition, active_references); |
| 323 | |
| 324 | #ifdef FSANITIZE_ADDRESS |
| 325 | // Add a stacktrace for this acquisition point too |
| 326 | stacktrace_array_add(&string->stacktraces, 0); |
| 327 | #endif |
| 328 | |
| 329 | return string; |
| 330 | } |
| 331 | |
| 332 | ALWAYS_INLINE |
| 333 | STRING *string_strndupz(const char *str, size_t len) { |
| 334 | if(unlikely(!str || !*str || !len)) return NULL; |
| 335 | |
| 336 | uint8_t partition = string_partition_str(str); |
| 337 | |
| 338 | STRING *string = string_index_search(str, len + 1, partition); |
| 339 | while(!string) |
| 340 | string = string_index_insert(str, len + 1, partition); |
| 341 | |
| 342 | string_stats_atomic_increment(partition, active_references); |
| 343 | |
| 344 | #ifdef FSANITIZE_ADDRESS |
| 345 | // Add a stacktrace for this acquisition point too |
| 346 | stacktrace_array_add(&string->stacktraces, 0); |
| 347 | #endif |
| 348 | |
| 349 | return string; |
| 350 | } |
| 351 | |
| 352 | ALWAYS_INLINE |
| 353 | void string_freez(STRING *string) { |
| 354 | if(unlikely(!string)) return; |
| 355 | |
| 356 | #ifdef NETDATA_INTERNAL_CHECKS |
| 357 | uint8_t partition = string_partition(string); |
| 358 | #endif |
| 359 | |
| 360 | if(unlikely(refcount_release_and_acquire_for_deletion(&string->refcount))) |
| 361 | string_index_delete(string); |
| 362 | |
| 363 | // statistics |
| 364 | string_stats_atomic_decrement(partition, active_references); |
| 365 | string_stats_atomic_increment(partition, releases); |
| 366 | } |
| 367 | |
| 368 | ALWAYS_INLINE |
| 369 | size_t string_strlen(const STRING *string) { |
| 370 | if(unlikely(!string)) return 0; |
| 371 | return string->length - 1; |
| 372 | } |
| 373 | |
| 374 | ALWAYS_INLINE |
| 375 | const char *string2str(const STRING *string) { |
| 376 | if(unlikely(!string)) return ""; |
| 377 | return string->str; |
| 378 | } |
| 379 | |
| 380 | ALWAYS_INLINE |
| 381 | bool string_ends_with_string(const STRING *whole, const STRING *end) { |
| 382 | if(whole == end) return true; |
| 383 | if(!whole || !end) return false; |
| 384 | if(end->length > whole->length) return false; |
| 385 | if(end->length == whole->length) return strcmp(string2str(whole), string2str(end)) == 0; |
| 386 | const char *we = string2str(whole); |
| 387 | we = &we[string_strlen(whole) - string_strlen(end)]; |
| 388 | return strncmp(we, end->str, string_strlen(end)) == 0; |
| 389 | } |
| 390 | |
| 391 | ALWAYS_INLINE |
| 392 | bool string_ends_with_string_nocase(const STRING *whole, const STRING *end) { |
| 393 | if(whole == end) return true; |
| 394 | if(!whole || !end) return false; |
| 395 | if(end->length > whole->length) return false; |
| 396 | if(end->length == whole->length) return strcasecmp(string2str(whole), string2str(end)) == 0; |
| 397 | const char *we = string2str(whole); |
| 398 | we = &we[string_strlen(whole) - string_strlen(end)]; |
| 399 | return strncasecmp(we, end->str, string_strlen(end)) == 0; |
| 400 | } |
| 401 | |
| 402 | ALWAYS_INLINE |
| 403 | bool string_starts_with_string(const STRING *whole, const STRING *end) { |
| 404 | if(whole == end) return true; |
| 405 | if(!whole || !end) return false; |
| 406 | if(end->length > whole->length) return false; |
| 407 | if(end->length == whole->length) return strcmp(string2str(whole), string2str(end)) == 0; |
| 408 | return strncmp(string2str(whole), string2str(end), string_strlen(end)) == 0; |
| 409 | } |
| 410 | |
| 411 | ALWAYS_INLINE |
| 412 | bool string_starts_with_string_nocase(const STRING *whole, const STRING *prefix) { |
| 413 | if(whole == prefix) return true; |
| 414 | if(!whole || !prefix) return false; |
| 415 | if(prefix->length > whole->length) return false; |
| 416 | if(prefix->length == whole->length) return strcasecmp(string2str(whole), string2str(prefix)) == 0; |
| 417 | return strncasecmp(string2str(whole), string2str(prefix), string_strlen(prefix)) == 0; |
| 418 | } |
| 419 | |
| 420 | ALWAYS_INLINE |
| 421 | bool string_equals_string_nocase(const STRING *a, const STRING *b) { |
| 422 | if(a == b) return true; |
| 423 | if(!a || !b) return false; |
| 424 | if(a->length != b->length) return false; |
| 425 | return strcasecmp(string2str(a), string2str(b)) == 0; |
| 426 | } |
| 427 | |
| 428 | // Static X used by string_2way_merge |
| 429 | static STRING *string_2way_merge_X = NULL; |
| 430 | |
| 431 | STRING *string_2way_merge(STRING *a, STRING *b) { |
| 432 | if(unlikely(!string_2way_merge_X)) |
| 433 | string_2way_merge_X = string_strdupz("[x]"); |
| 434 | |
| 435 | if(unlikely(a == b)) return string_dup(a); |
| 436 | if(unlikely(a == string_2way_merge_X)) return string_dup(a); |
| 437 | if(unlikely(b == string_2way_merge_X)) return string_dup(b); |
| 438 | if(unlikely(!a)) return string_dup(string_2way_merge_X); |
| 439 | if(unlikely(!b)) return string_dup(string_2way_merge_X); |
| 440 | |
| 441 | size_t alen = string_strlen(a); |
| 442 | size_t blen = string_strlen(b); |
| 443 | size_t length = alen + blen + string_strlen(string_2way_merge_X) + 1; |
| 444 | CLEAN_CHAR_P *buf1 = mallocz(length + 1); |
| 445 | CLEAN_CHAR_P *buf2 = mallocz(length + 1); |
| 446 | char *dst1; |
| 447 | const char *s1, *s2; |
| 448 | |
| 449 | s1 = string2str(a); |
| 450 | s2 = string2str(b); |
| 451 | dst1 = buf1; |
| 452 | for( ; *s1 && *s2 && *s1 == *s2 ;s1++, s2++) |
| 453 | *dst1++ = *s1; |
| 454 | |
| 455 | *dst1 = '\0'; |
| 456 | |
| 457 | if(*s1 != '\0' || *s2 != '\0') { |
| 458 | *dst1++ = '['; |
| 459 | *dst1++ = 'x'; |
| 460 | *dst1++ = ']'; |
| 461 | |
| 462 | s1 = &(string2str(a))[alen - 1]; |
| 463 | s2 = &(string2str(b))[blen - 1]; |
| 464 | char *dst2 = &buf2[length]; |
| 465 | *dst2 = '\0'; |
| 466 | for (; *s1 && *s2 && *s1 == *s2; s1--, s2--) |
| 467 | *(--dst2) = *s1; |
| 468 | |
| 469 | strcpy(dst1, dst2); |
| 470 | } |
| 471 | |
| 472 | return string_strdupz(buf1); |
| 473 | } |
| 474 | |
| 475 | // ---------------------------------------------------------------------------- |
| 476 | // STRING unit test |
| 477 | |
| 478 | struct thread_unittest { |
| 479 | int join; |
| 480 | int dups; |
| 481 | }; |
| 482 | |
| 483 | static void string_thread(void *arg) { |
| 484 | struct thread_unittest *tu = arg; |
| 485 | |
| 486 | for(; 1 ;) { |
| 487 | if(__atomic_load_n(&tu->join, __ATOMIC_RELAXED)) |
| 488 | break; |
| 489 | |
| 490 | STRING *s = string_strdupz("string thread checking 1234567890"); |
| 491 | |
| 492 | for(int i = 0; i < tu->dups ; i++) |
| 493 | string_dup(s); |
| 494 | |
| 495 | for(int i = 0; i < tu->dups ; i++) |
| 496 | string_freez(s); |
| 497 | |
| 498 | string_freez(s); |
| 499 | } |
| 500 | } |
| 501 | |
| 502 | static char **string_unittest_generate_names(size_t entries) { |
| 503 | char **names = mallocz(sizeof(char *) * entries); |
| 504 | for(size_t i = 0; i < entries ;i++) { |
| 505 | char buf[25 + 1] = ""; |
| 506 | snprintfz(buf, sizeof(buf) - 1, "name.%zu.0123456789.%zu \t !@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i); |
| 507 | names[i] = strdupz(buf); |
| 508 | } |
| 509 | return names; |
| 510 | } |
| 511 | |
| 512 | static void string_unittest_free_char_pp(char **pp, size_t entries) { |
| 513 | for(size_t i = 0; i < entries ;i++) |
| 514 | freez(pp[i]); |
| 515 | |
| 516 | freez(pp); |
| 517 | } |
| 518 | |
| 519 | static long unittest_string_entries(void) { |
| 520 | long entries = 0; |
| 521 | for(size_t p = 0; p < STRING_PARTITIONS ;p++) |
| 522 | entries += string_base[p].entries; |
| 523 | |
| 524 | return entries; |
| 525 | } |
| 526 | |
| 527 | // returns the number of strings that were freed, but were still referenced |
| 528 | size_t string_destroy(void) { |
| 529 | size_t referenced = 0; |
| 530 | |
| 531 | // Free the static X string used by string_2way_merge |
| 532 | string_freez(string_2way_merge_X); |
| 533 | string_2way_merge_X = NULL; |
| 534 | |
| 535 | #ifdef FSANITIZE_ADDRESS |
| 536 | // Create JudyL array for tracking stats by stacktrace |
| 537 | Pvoid_t string_counts = NULL; // JudyL array to count strings per stacktrace |
| 538 | |
| 539 | BUFFER *wb = buffer_create(16384, NULL); |
| 540 | |
| 541 | fprintf(stderr, "\n========= STRINGS GROUPED BY CREATION STACKTRACE =========\n"); |
| 542 | size_t total_strings = 0; |
| 543 | #endif |
| 544 | |
| 545 | // Traverse all partitions |
| 546 | for (size_t partition = 0; partition < STRING_PARTITIONS; partition++) { |
| 547 | // Lock the partition to prevent new entries while we're cleaning up |
| 548 | rw_spinlock_write_lock(&string_base[partition].spinlock); |
| 549 | |
| 550 | #ifdef FSANITIZE_ADDRESS |
| 551 | // First, collect statistics about remaining strings |
| 552 | if (string_base[partition].JudyLPointers) { |
| 553 | // Traverse the JudyL array to count strings by stacktrace |
| 554 | Word_t string_idx = 0; |
| 555 | Pvoid_t *PValue; |
| 556 | |
| 557 | PValue = JudyLFirst(string_base[partition].JudyLPointers, &string_idx, PJE0); |
| 558 | while (PValue) { |
| 559 | STRING *string = (STRING *)string_idx; |
| 560 | if(string) { |
| 561 | fprintf(stderr, " > STRING REMAINING No %zu: %d references on: '%s'\n", |
| 562 | ++total_strings, string->refcount, string2str(string)); |
| 563 | |
| 564 | for (int i = 0; i < string->stacktraces.num_stacktraces; i++) { |
| 565 | if (string->stacktraces.stacktraces[i]) { |
| 566 | Word_t key = (Word_t)string->stacktraces.stacktraces[i]; |
| 567 | PValue = JudyLGet(string_counts, key, PJE0); |
| 568 | if (PValue) { |
| 569 | // Increment existing count |
| 570 | size_t count = (size_t)(uintptr_t)*PValue; |
| 571 | count++; |
| 572 | *PValue = (Pvoid_t)(uintptr_t)count; |
| 573 | } else { |
| 574 | // Insert new count |
| 575 | PValue = JudyLIns(&string_counts, key, PJE0); |
| 576 | if (PValue != PJERR) |
| 577 | *PValue = (Pvoid_t)(uintptr_t)1; |
| 578 | } |
| 579 | } |
| 580 | } |
| 581 | } |
| 582 | |
| 583 | PValue = JudyLNext(string_base[partition].JudyLPointers, &string_idx, PJE0); |
| 584 | } |
| 585 | |
| 586 | // Free the JudyL pointers array |
| 587 | JudyLFreeArray(&string_base[partition].JudyLPointers, PJE0); |
| 588 | string_base[partition].JudyLPointers = NULL; |
| 589 | } |
| 590 | #endif |
| 591 | |
| 592 | // Since JudyHS doesn't have simple traversal functions, |
| 593 | // we'll free the entire array at once. |
| 594 | if (string_base[partition].JudyHSArray) { |
| 595 | // We'll count all entries as "referenced" since we can't check them individually |
| 596 | referenced += string_base[partition].entries; |
| 597 | |
| 598 | // Free the JudyHS array |
| 599 | JudyHSFreeArray(&string_base[partition].JudyHSArray, PJE0); |
| 600 | string_base[partition].JudyHSArray = NULL; |
| 601 | } |
| 602 | |
| 603 | // Reset partition statistics |
| 604 | string_base[partition].inserts = 0; |
| 605 | string_base[partition].deletes = 0; |
| 606 | string_base[partition].entries = 0; |
| 607 | string_base[partition].memory = 0; |
| 608 | string_base[partition].memory_index = 0; |
| 609 | |
| 610 | #ifdef NETDATA_INTERNAL_CHECKS |
| 611 | string_base[partition].atomic.searches = 0; |
| 612 | string_base[partition].atomic.releases = 0; |
| 613 | string_base[partition].atomic.duplications = 0; |
| 614 | string_base[partition].atomic.active_references = 0; |
| 615 | string_base[partition].found_deleted_on_search = 0; |
| 616 | string_base[partition].found_available_on_search = 0; |
| 617 | string_base[partition].found_deleted_on_insert = 0; |
| 618 | string_base[partition].found_available_on_insert = 0; |
| 619 | string_base[partition].spins = 0; |
| 620 | #endif |
| 621 | |
| 622 | rw_spinlock_write_unlock(&string_base[partition].spinlock); |
| 623 | } |
| 624 | |
| 625 | #ifdef FSANITIZE_ADDRESS |
| 626 | // Collect stacktraces into an array for sorting |
| 627 | typedef struct { |
| 628 | STACKTRACE st; |
| 629 | size_t count; |
| 630 | } StacktraceEntry; |
| 631 | |
| 632 | // First, count the number of unique stacktraces |
| 633 | Word_t Index = 0; |
| 634 | Pvoid_t *PValue; |
| 635 | size_t unique_stacktraces = 0; |
| 636 | |
| 637 | if (string_counts) { |
| 638 | PValue = JudyLFirst(string_counts, &Index, PJE0); |
| 639 | while (PValue) { |
| 640 | unique_stacktraces++; |
| 641 | PValue = JudyLNext(string_counts, &Index, PJE0); |
| 642 | } |
| 643 | } |
| 644 | |
| 645 | // Allocate an array for sorting |
| 646 | StacktraceEntry *entries = mallocz(sizeof(StacktraceEntry) * unique_stacktraces); |
| 647 | size_t entry_count = 0; |
| 648 | |
| 649 | // Populate the array with stacktraces and counts |
| 650 | if (string_counts && unique_stacktraces > 0) { |
| 651 | Index = 0; |
| 652 | PValue = JudyLFirst(string_counts, &Index, PJE0); |
| 653 | while (PValue) { |
| 654 | entries[entry_count].st = (STACKTRACE)Index; |
| 655 | entries[entry_count].count = (size_t)(uintptr_t)*PValue; |
| 656 | entry_count++; |
| 657 | PValue = JudyLNext(string_counts, &Index, PJE0); |
| 658 | } |
| 659 | } |
| 660 | |
| 661 | // Sort by count in descending order |
| 662 | // Simple insertion sort is sufficient for a small number of entries |
| 663 | for (size_t i = 1; i < entry_count; i++) { |
| 664 | StacktraceEntry key = entries[i]; |
| 665 | ssize_t j = i - 1; |
| 666 | |
| 667 | // Move elements that are greater than key to one position ahead of their current position |
| 668 | while (j >= 0 && entries[j].count < key.count) { |
| 669 | entries[j + 1] = entries[j]; |
| 670 | j--; |
| 671 | } |
| 672 | entries[j + 1] = key; |
| 673 | } |
| 674 | |
| 675 | // Print sorted stacktraces |
| 676 | fprintf(stderr, "\nTop string creation stacktraces by count:\n"); |
| 677 | |
| 678 | for (size_t i = 0; i < entry_count; i++) { |
| 679 | // Format stacktrace to buffer |
| 680 | buffer_flush(wb); |
| 681 | stacktrace_to_buffer(entries[i].st, wb); |
| 682 | |
| 683 | fprintf(stderr, "\n > STRINGS BACKTRACE %zu: %zu strings created from:\n%s\n", |
| 684 | i + 1, entries[i].count, buffer_tostring(wb)); |
| 685 | } |
| 686 | |
| 687 | fprintf(stderr, "==================================================================\n\n"); |
| 688 | |
| 689 | // Clean up |
| 690 | freez(entries); |
| 691 | if (string_counts) |
| 692 | JudyLFreeArray(&string_counts, PJE0); |
| 693 | buffer_free(wb); |
| 694 | #endif |
| 695 | |
| 696 | memset(&string_base, 0, sizeof(string_base)); |
| 697 | return referenced; |
| 698 | } |
| 699 | |
| 700 | #ifdef NETDATA_INTERNAL_CHECKS |
| 701 | |
| 702 | static size_t unittest_string_found_deleted_on_search(void) { |
| 703 | size_t entries = 0; |
| 704 | for(size_t p = 0; p < STRING_PARTITIONS ;p++) |
| 705 | entries += string_base[p].found_deleted_on_search; |
| 706 | |
| 707 | return entries; |
| 708 | } |
| 709 | static size_t unittest_string_found_available_on_search(void) { |
| 710 | size_t entries = 0; |
| 711 | for(size_t p = 0; p < STRING_PARTITIONS ;p++) |
| 712 | entries += string_base[p].found_available_on_search; |
| 713 | |
| 714 | return entries; |
| 715 | } |
| 716 | static size_t unittest_string_found_deleted_on_insert(void) { |
| 717 | size_t entries = 0; |
| 718 | for(size_t p = 0; p < STRING_PARTITIONS ;p++) |
| 719 | entries += string_base[p].found_deleted_on_insert; |
| 720 | |
| 721 | return entries; |
| 722 | } |
| 723 | static size_t unittest_string_found_available_on_insert(void) { |
| 724 | size_t entries = 0; |
| 725 | for(size_t p = 0; p < STRING_PARTITIONS ;p++) |
| 726 | entries += string_base[p].found_available_on_insert; |
| 727 | |
| 728 | return entries; |
| 729 | } |
| 730 | static size_t unittest_string_spins(void) { |
| 731 | size_t entries = 0; |
| 732 | for(size_t p = 0; p < STRING_PARTITIONS ;p++) |
| 733 | entries += string_base[p].spins; |
| 734 | |
| 735 | return entries; |
| 736 | } |
| 737 | |
| 738 | #endif // NETDATA_INTERNAL_CHECKS |
| 739 | |
| 740 | int string_unittest(size_t entries) { |
| 741 | size_t errors = 0; |
| 742 | |
| 743 | fprintf(stderr, "Generating %zu names and values...\n", entries); |
| 744 | char **names = string_unittest_generate_names(entries); |
| 745 | |
| 746 | // check string |
| 747 | { |
| 748 | long entries_starting = unittest_string_entries(); |
| 749 | |
| 750 | fprintf(stderr, "\nChecking strings...\n"); |
| 751 | |
| 752 | STRING *s1 = string_strdupz("hello unittest"); |
| 753 | STRING *s2 = string_strdupz("hello unittest"); |
| 754 | if(s1 != s2) { |
| 755 | errors++; |
| 756 | fprintf(stderr, "ERROR: duplicating strings are not deduplicated\n"); |
| 757 | } |
| 758 | else |
| 759 | fprintf(stderr, "OK: duplicating string are deduplicated\n"); |
| 760 | |
| 761 | STRING *s3 = string_dup(s1); |
| 762 | if(s3 != s1) { |
| 763 | errors++; |
| 764 | fprintf(stderr, "ERROR: cloning strings are not deduplicated\n"); |
| 765 | } |
| 766 | else |
| 767 | fprintf(stderr, "OK: cloning string are deduplicated\n"); |
| 768 | |
| 769 | if(s1->refcount != 3) { |
| 770 | errors++; |
| 771 | fprintf(stderr, "ERROR: string refcount is not 3\n"); |
| 772 | } |
| 773 | else |
| 774 | fprintf(stderr, "OK: string refcount is 3\n"); |
| 775 | |
| 776 | STRING *s4 = string_strdupz("world unittest"); |
| 777 | if(s4 == s1) { |
| 778 | errors++; |
| 779 | fprintf(stderr, "ERROR: string is sharing pointers on different strings\n"); |
| 780 | } |
| 781 | else |
| 782 | fprintf(stderr, "OK: string is properly handling different strings\n"); |
| 783 | |
| 784 | STRING *s_null = string_strdupz(NULL); |
| 785 | if(s_null != NULL) { |
| 786 | errors++; |
| 787 | fprintf(stderr, "ERROR: NULL string input should return NULL\n"); |
| 788 | } |
| 789 | else |
| 790 | fprintf(stderr, "OK: NULL string input returns NULL\n"); |
| 791 | |
| 792 | STRING *s_empty = string_strdupz(""); |
| 793 | if(s_empty != NULL) { |
| 794 | errors++; |
| 795 | fprintf(stderr, "ERROR: empty string input should return NULL\n"); |
| 796 | } |
| 797 | else |
| 798 | fprintf(stderr, "OK: empty string input returns NULL\n"); |
| 799 | |
| 800 | usec_t start_ut, end_ut; |
| 801 | STRING **strings = mallocz(entries * sizeof(STRING *)); |
| 802 | |
| 803 | start_ut = now_realtime_usec(); |
| 804 | for(size_t i = 0; i < entries ;i++) { |
| 805 | strings[i] = string_strdupz(names[i]); |
| 806 | } |
| 807 | end_ut = now_realtime_usec(); |
| 808 | fprintf(stderr, "Created %zu strings in %"PRIu64" usecs\n", entries, end_ut - start_ut); |
| 809 | |
| 810 | start_ut = now_realtime_usec(); |
| 811 | for(size_t i = 0; i < entries ;i++) { |
| 812 | strings[i] = string_dup(strings[i]); |
| 813 | } |
| 814 | end_ut = now_realtime_usec(); |
| 815 | fprintf(stderr, "Cloned %zu strings in %"PRIu64" usecs\n", entries, end_ut - start_ut); |
| 816 | |
| 817 | start_ut = now_realtime_usec(); |
| 818 | for(size_t i = 0; i < entries ;i++) { |
| 819 | strings[i] = string_strdupz(string2str(strings[i])); |
| 820 | } |
| 821 | end_ut = now_realtime_usec(); |
| 822 | fprintf(stderr, "Found %zu existing strings in %"PRIu64" usecs\n", entries, end_ut - start_ut); |
| 823 | |
| 824 | start_ut = now_realtime_usec(); |
| 825 | for(size_t i = 0; i < entries ;i++) { |
| 826 | string_freez(strings[i]); |
| 827 | } |
| 828 | end_ut = now_realtime_usec(); |
| 829 | fprintf(stderr, "Released %zu referenced strings in %"PRIu64" usecs\n", entries, end_ut - start_ut); |
| 830 | |
| 831 | start_ut = now_realtime_usec(); |
| 832 | for(size_t i = 0; i < entries ;i++) { |
| 833 | string_freez(strings[i]); |
| 834 | } |
| 835 | end_ut = now_realtime_usec(); |
| 836 | fprintf(stderr, "Released (again) %zu referenced strings in %"PRIu64" usecs\n", entries, end_ut - start_ut); |
| 837 | |
| 838 | start_ut = now_realtime_usec(); |
| 839 | for(size_t i = 0; i < entries ;i++) { |
| 840 | string_freez(strings[i]); |
| 841 | } |
| 842 | end_ut = now_realtime_usec(); |
| 843 | fprintf(stderr, "Freed %zu strings in %"PRIu64" usecs\n", entries, end_ut - start_ut); |
| 844 | |
| 845 | freez(strings); |
| 846 | |
| 847 | if(unittest_string_entries() != entries_starting + 2) { |
| 848 | errors++; |
| 849 | fprintf(stderr, "ERROR: strings dictionary should have %ld items but it has %ld\n", |
| 850 | entries_starting + 2, unittest_string_entries()); |
| 851 | } |
| 852 | else |
| 853 | fprintf(stderr, "OK: strings dictionary has 2 items\n"); |
| 854 | } |
| 855 | |
| 856 | // check 2-way merge |
| 857 | { |
| 858 | struct testcase { |
| 859 | char *src1; char *src2; char *expected; |
| 860 | } tests[] = { |
| 861 | { "", "", ""}, |
| 862 | { "a", "", "[x]"}, |
| 863 | { "", "a", "[x]"}, |
| 864 | { "a", "a", "a"}, |
| 865 | { "abcd", "abcd", "abcd"}, |
| 866 | { "foo_cs", "bar_cs", "[x]_cs"}, |
| 867 | { "cp_UNIQUE_INFIX_cs", "cp_unique_infix_cs", "cp_[x]_cs"}, |
| 868 | { "cp_UNIQUE_INFIX_ci_unique_infix_cs", "cp_unique_infix_ci_UNIQUE_INFIX_cs", "cp_[x]_cs"}, |
| 869 | { "foo[1234]", "foo[4321]", "foo[[x]]"}, |
| 870 | { NULL, NULL, NULL }, |
| 871 | }; |
| 872 | |
| 873 | for (struct testcase *tc = &tests[0]; tc->expected != NULL; tc++) { |
| 874 | STRING *src1 = string_strdupz(tc->src1); |
| 875 | STRING *src2 = string_strdupz(tc->src2); |
| 876 | STRING *expected = string_strdupz(tc->expected); |
| 877 | |
| 878 | STRING *result = string_2way_merge(src1, src2); |
| 879 | if (string_cmp(result, expected) != 0) { |
| 880 | fprintf(stderr, "string_2way_merge(\"%s\", \"%s\") -> \"%s\" (expected=\"%s\")\n", |
| 881 | string2str(src1), |
| 882 | string2str(src2), |
| 883 | string2str(result), |
| 884 | string2str(expected)); |
| 885 | errors++; |
| 886 | } |
| 887 | |
| 888 | string_freez(src1); |
| 889 | string_freez(src2); |
| 890 | string_freez(expected); |
| 891 | string_freez(result); |
| 892 | } |
| 893 | } |
| 894 | |
| 895 | // threads testing of string |
| 896 | { |
| 897 | struct thread_unittest tu = { |
| 898 | .dups = 1, |
| 899 | .join = 0, |
| 900 | }; |
| 901 | |
| 902 | #ifdef NETDATA_INTERNAL_CHECKS |
| 903 | size_t ofound_deleted_on_search = unittest_string_found_deleted_on_search(), |
| 904 | ofound_available_on_search = unittest_string_found_available_on_search(), |
| 905 | ofound_deleted_on_insert = unittest_string_found_deleted_on_insert(), |
| 906 | ofound_available_on_insert = unittest_string_found_available_on_insert(), |
| 907 | ospins = unittest_string_spins(); |
| 908 | #endif |
| 909 | |
| 910 | size_t oinserts, odeletes, osearches, oentries, oreferences, omemory, omemory_index, oduplications, oreleases; |
| 911 | string_statistics(&oinserts, &odeletes, &osearches, &oentries, &oreferences, &omemory, &omemory_index, &oduplications, &oreleases); |
| 912 | |
| 913 | time_t seconds_to_run = 5; |
| 914 | enum { STRING_UNITTEST_THREADS = 2 }; |
| 915 | fprintf( |
| 916 | stderr, |
| 917 | "Checking string concurrency with %d threads for %lld seconds...\n", |
| 918 | STRING_UNITTEST_THREADS, |
| 919 | (long long)seconds_to_run); |
| 920 | // check string concurrency |
| 921 | ND_THREAD *threads[STRING_UNITTEST_THREADS]; |
| 922 | tu.join = 0; |
| 923 | for (int i = 0; i < STRING_UNITTEST_THREADS; i++) { |
| 924 | char buf[100 + 1]; |
| 925 | snprintf(buf, 100, "string%d", i); |
| 926 | threads[i] = nd_thread_create(buf, NETDATA_THREAD_OPTION_DONT_LOG, string_thread, &tu); |
| 927 | } |
| 928 | sleep_usec(seconds_to_run * USEC_PER_SEC); |
| 929 | |
| 930 | __atomic_store_n(&tu.join, 1, __ATOMIC_RELAXED); |
| 931 | for (int i = 0; i < STRING_UNITTEST_THREADS; i++) |
| 932 | nd_thread_join(threads[i]); |
| 933 | |
| 934 | size_t inserts, deletes, searches, sentries, references, memory, memory_index, duplications, releases; |
| 935 | string_statistics(&inserts, &deletes, &searches, &sentries, &references, &memory, &memory_index, &duplications, &releases); |
| 936 | |
| 937 | fprintf(stderr, "inserts %zu, deletes %zu, searches %zu, entries %zu, references %zu, memory %zu, duplications %zu, releases %zu\n", |
| 938 | inserts - oinserts, deletes - odeletes, searches - osearches, sentries - oentries, references - oreferences, memory - omemory, duplications - oduplications, releases - oreleases); |
| 939 | |
| 940 | #ifdef NETDATA_INTERNAL_CHECKS |
| 941 | size_t found_deleted_on_search = unittest_string_found_deleted_on_search(), |
| 942 | found_available_on_search = unittest_string_found_available_on_search(), |
| 943 | found_deleted_on_insert = unittest_string_found_deleted_on_insert(), |
| 944 | found_available_on_insert = unittest_string_found_available_on_insert(), |
| 945 | spins = unittest_string_spins(); |
| 946 | |
| 947 | fprintf(stderr, "on insert: %zu ok + %zu deleted\non search: %zu ok + %zu deleted\nspins: %zu\n", |
| 948 | found_available_on_insert - ofound_available_on_insert, |
| 949 | found_deleted_on_insert - ofound_deleted_on_insert, |
| 950 | found_available_on_search - ofound_available_on_search, |
| 951 | found_deleted_on_search - ofound_deleted_on_search, |
| 952 | spins - ospins |
| 953 | ); |
| 954 | #endif |
| 955 | } |
| 956 | |
| 957 | string_unittest_free_char_pp(names, entries); |
| 958 | |
| 959 | fprintf(stderr, "\n%zu errors found\n", errors); |
| 960 | return errors ? 1 : 0; |
| 961 | } |
| 962 | |
| 963 | void string_init(void) { |
| 964 | for (size_t i = 0; i != STRING_PARTITIONS; i++) { |
| 965 | rw_spinlock_init(&string_base[i].spinlock); |
| 966 | |
| 967 | #ifdef FSANITIZE_ADDRESS |
| 968 | // Initialize the JudyL pointers array to NULL |
| 969 | string_base[i].JudyLPointers = NULL; |
| 970 | #endif |
| 971 | } |
| 972 | } |