@cryptotaxi247 / netdata-1
Code Commits Issues Pulls Sessions CI/CD
master
master
c 2,541 lines 98 KB
Raw
1 #include "../libnetdata.h"
2 #include "aral.h"
3
4 // #define NETDATA_ARAL_INTERNAL_CHECKS 1
5
6 #ifdef NETDATA_TRACE_ALLOCATIONS
7 #define TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS , const char *file, const char *function, size_t line
8 #define TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS , file, function, line
9 #else
10 #define TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS
11 #define TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS
12 #endif
13
14 // max mapped file size
15 #define ARAL_MAX_PAGE_SIZE_MMAP (1ULL * 1024 * 1024 * 1024)
16
17 // max malloc size
18 // optimal at current versions of libc is up to 256k
19 // ideal to have the same overhead as libc is 4k
20 #define ARAL_MAX_PAGE_SIZE_MALLOC (64ULL * 1024)
21
22 // in malloc mode, when the page is bigger than this
23 // use anonymous private mmap pages
24 #define ARAL_MALLOC_USE_MMAP_ABOVE (16ULL * 1024)
25
26 // do not allocate pages smaller than this
27 #define ARAL_MIN_PAGE_SIZE (16ULL * 1024)
28
29 #define ARAL_PAGE_INCOMING_PARTITIONS 4 // up to 32 (32-bits bitmap)
30
31 typedef struct aral_free {
32 size_t size;
33 struct aral_free *next;
34 } ARAL_FREE;
35
36 typedef struct aral_page {
37 REFCOUNT refcount;
38
39 const char *filename;
40 uint8_t *data;
41
42 bool started_marked;
43 bool mapped;
44 uint32_t size; // the allocation size of the page
45 uint32_t max_elements; // the number of elements that can fit on this page
46 uint64_t elements_segmented; // fast path for acquiring new elements in this page
47
48 struct {
49 bool marked;
50 struct aral_page **head_ptr;
51 struct aral_page *prev; // the prev page on the list
52 struct aral_page *next; // the next page on the list
53 } aral_lock;
54
55 struct {
56 SPINLOCK spinlock;
57 uint32_t used_elements; // the number of used elements on this page
58 uint32_t free_elements; // the number of free elements on this page
59 uint32_t marked_elements;
60 char pad[32];
61 } page_lock;
62
63 struct {
64 SPINLOCK spinlock;
65 ARAL_FREE *list;
66 char pad[40];
67 } available;
68
69 struct {
70 SPINLOCK spinlock;
71 ARAL_FREE *list;
72 char pad[48];
73 } incoming[ARAL_PAGE_INCOMING_PARTITIONS];
74
75 uint32_t incoming_partition_bitmap; // atomic
76
77 } ARAL_PAGE;
78
79 typedef enum {
80 ARAL_LOCKLESS = (1 << 0),
81 ARAL_ALLOCATED_STATS = (1 << 1),
82 ARAL_DONT_DUMP = (1 << 2),
83 } ARAL_OPTIONS;
84
85 struct aral_ops {
86 struct {
87 PAD64(size_t) allocators; // the number of threads currently trying to allocate memory
88 PAD64(size_t) deallocators; // the number of threads currently trying to deallocate memory
89 PAD64(bool) last_allocated_page; // stability detector, true when was last allocated
90 } atomic;
91
92 struct {
93 SPINLOCK spinlock;
94 size_t allocating_elements; // currently allocating elements
95 size_t allocation_size; // current / next allocation size
96 } adders;
97 };
98
99 struct aral {
100 struct {
101 SPINLOCK spinlock;
102 size_t file_number; // for mmap
103
104 ARAL_PAGE *pages_free; // pages with free items
105 ARAL_PAGE *pages_full; // pages that are completely full
106
107 ARAL_PAGE *pages_marked_free; // pages with marked items and free slots
108 ARAL_PAGE *pages_marked_full; // pages with marked items completely full
109 } aral_lock;
110
111 struct {
112 char name[ARAL_MAX_NAME + 1];
113
114 ARAL_OPTIONS options;
115
116 size_t element_size; // calculated to take into account ARAL overheads
117 size_t element_ptr_offset; // calculated
118 size_t system_page_size; // calculated
119
120 size_t initial_page_elements;
121 size_t requested_element_size;
122 size_t requested_max_page_size;
123
124 size_t min_required_page_size;
125
126 struct {
127 bool enabled;
128 const char *filename;
129 const char **cache_dir;
130 } mmap;
131 } config;
132
133 struct {
134 PAD64(size_t) user_malloc_operations;
135 PAD64(size_t) user_free_operations;
136 } atomic;
137
138 struct aral_ops ops[2];
139
140 struct aral_statistics *stats;
141 };
142
143 #define mark_to_idx(marked) (marked ? 1 : 0)
144 #define aral_pages_head_free(ar, marked) (marked ? &ar->aral_lock.pages_marked_free : &ar->aral_lock.pages_free)
145 #define aral_pages_head_full(ar, marked) (marked ? &ar->aral_lock.pages_marked_full : &ar->aral_lock.pages_full)
146
147 static size_t aral_max_allocation_size(ARAL *ar);
148
149 static inline bool aral_malloc_use_mmap(ARAL *ar __maybe_unused, size_t size) {
150 unsigned long long mmap_limit = os_mmap_limit();
151
152 if(mmap_limit > 256 * 1000 && size >= ARAL_MALLOC_USE_MMAP_ABOVE)
153 return true;
154
155 return false;
156 }
157
158 const char *aral_name(ARAL *ar) {
159 return ar->config.name;
160 }
161
162 static ALWAYS_INLINE void aral_element_given(ARAL *ar, ARAL_PAGE *page) {
163 if(ar->config.mmap.enabled || page->mapped)
164 __atomic_add_fetch(&ar->stats->mmap.used_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
165 else
166 __atomic_add_fetch(&ar->stats->malloc.used_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
167 }
168
169 static ALWAYS_INLINE void aral_element_returned(ARAL *ar, ARAL_PAGE *page) {
170 if(ar->config.mmap.enabled || page->mapped)
171 __atomic_sub_fetch(&ar->stats->mmap.used_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
172 else
173 __atomic_sub_fetch(&ar->stats->malloc.used_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
174 }
175
176 size_t aral_structures_bytes_from_stats(struct aral_statistics *stats) {
177 if(!stats) return 0;
178 return __atomic_load_n(&stats->structures.allocated_bytes, __ATOMIC_RELAXED);
179 }
180
181 size_t aral_free_bytes_from_stats(struct aral_statistics *stats) {
182 if(!stats) return 0;
183
184 size_t allocated = __atomic_load_n(&stats->malloc.allocated_bytes, __ATOMIC_RELAXED) +
185 __atomic_load_n(&stats->mmap.allocated_bytes, __ATOMIC_RELAXED);
186
187 size_t used = __atomic_load_n(&stats->malloc.used_bytes, __ATOMIC_RELAXED) +
188 __atomic_load_n(&stats->mmap.used_bytes, __ATOMIC_RELAXED);
189
190 return (allocated > used) ? allocated - used : 0;
191 }
192
193 size_t aral_used_bytes_from_stats(struct aral_statistics *stats) {
194 size_t used = __atomic_load_n(&stats->malloc.used_bytes, __ATOMIC_RELAXED) +
195 __atomic_load_n(&stats->mmap.used_bytes, __ATOMIC_RELAXED);
196 return used;
197 }
198
199 size_t aral_padding_bytes_from_stats(struct aral_statistics *stats) {
200 size_t padding = __atomic_load_n(&stats->malloc.padding_bytes, __ATOMIC_RELAXED) +
201 __atomic_load_n(&stats->mmap.padding_bytes, __ATOMIC_RELAXED);
202 return padding;
203 }
204
205 size_t aral_used_bytes(ARAL *ar) {
206 return aral_used_bytes_from_stats(ar->stats);
207 }
208
209 size_t aral_free_bytes(ARAL *ar) {
210 return aral_free_bytes_from_stats(ar->stats);
211 }
212
213 size_t aral_structures_bytes(ARAL *ar) {
214 return aral_structures_bytes_from_stats(ar->stats);
215 }
216
217 size_t aral_padding_bytes(ARAL *ar) {
218 return aral_padding_bytes_from_stats(ar->stats);
219 }
220
221 size_t aral_free_structures_padding_from_stats(struct aral_statistics *stats) {
222 return aral_free_bytes_from_stats(stats) + aral_structures_bytes_from_stats(stats) + aral_padding_bytes_from_stats(stats);
223 }
224
225 struct aral_statistics *aral_get_statistics(ARAL *ar) {
226 return ar->stats;
227 }
228
229 static ALWAYS_INLINE void aral_lock_with_trace(ARAL *ar, const char *func) {
230 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
231 spinlock_lock_with_trace(&ar->aral_lock.spinlock, func);
232 }
233
234 static ALWAYS_INLINE void aral_unlock_with_trace(ARAL *ar, const char *func) {
235 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
236 spinlock_unlock_with_trace(&ar->aral_lock.spinlock, func);
237 }
238
239 #define aral_lock(ar) aral_lock_with_trace(ar, __FUNCTION__)
240 #define aral_unlock(ar) aral_unlock_with_trace(ar, __FUNCTION__)
241
242 static ALWAYS_INLINE void aral_page_lock(ARAL *ar, ARAL_PAGE *page) {
243 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
244 spinlock_lock(&page->page_lock.spinlock);
245 }
246
247 static ALWAYS_INLINE void aral_page_unlock(ARAL *ar, ARAL_PAGE *page) {
248 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
249 spinlock_unlock(&page->page_lock.spinlock);
250 }
251
252 static ALWAYS_INLINE void aral_page_available_lock(ARAL *ar, ARAL_PAGE *page) {
253 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
254 spinlock_lock(&page->available.spinlock);
255 }
256
257 static ALWAYS_INLINE void aral_page_available_unlock(ARAL *ar, ARAL_PAGE *page) {
258 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
259 spinlock_unlock(&page->available.spinlock);
260 }
261
262 static ALWAYS_INLINE bool aral_page_incoming_trylock(ARAL *ar, ARAL_PAGE *page, size_t partition) {
263 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
264 return spinlock_trylock(&page->incoming[partition].spinlock);
265
266 return true;
267 }
268
269 static ALWAYS_INLINE void aral_page_incoming_lock(ARAL *ar, ARAL_PAGE *page, size_t partition) {
270 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
271 spinlock_lock(&page->incoming[partition].spinlock);
272 }
273
274 static ALWAYS_INLINE void aral_page_incoming_unlock(ARAL *ar, ARAL_PAGE *page, size_t partition) {
275 if(likely(!(ar->config.options & ARAL_LOCKLESS)))
276 spinlock_unlock(&page->incoming[partition].spinlock);
277 }
278
279 #ifdef NETDATA_INTERNAL_CHECKS
280 struct aral_race_unittest_hook {
281 ARAL *ar;
282 ARAL_PAGE *page;
283 struct aral_unittest_entry *forced_entry;
284 bool enabled;
285 bool first_allocator_waiting;
286 bool release_first_allocator;
287 bool first_allocator_claimed;
288 bool page_force_fully_used;
289 };
290
291 static struct aral_race_unittest_hook aral_race_unittest_hook = { 0 };
292
293 static ALWAYS_INLINE void aral_unittest_wait_for_race_window(ARAL *ar, ARAL_PAGE *page) {
294 if(unlikely(__atomic_load_n(&aral_race_unittest_hook.enabled, __ATOMIC_RELAXED) &&
295 aral_race_unittest_hook.ar == ar)) {
296 bool expected = false;
297 if(__atomic_compare_exchange_n(&aral_race_unittest_hook.first_allocator_claimed, &expected, true, false,
298 __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) {
299 aral_race_unittest_hook.page = page;
300 __atomic_store_n(&aral_race_unittest_hook.first_allocator_waiting, true, __ATOMIC_RELEASE);
301 while(!__atomic_load_n(&aral_race_unittest_hook.release_first_allocator, __ATOMIC_ACQUIRE))
302 tinysleep();
303 }
304 }
305 }
306
307 // Pause-point hook for the unmark/freez state-machine concurrency tests.
308 // Distinct from aral_race_unittest_hook above; fires only on a (ar, ptr, stage)
309 // match so the two test families do not interfere.
310 enum aral_concurrency_race_stage {
311 ARAL_CONCURRENCY_RACE_NONE = 0,
312 ARAL_CONCURRENCY_RACE_UNMARK_BEFORE_CAS, // unmark entry, before reading the trailer
313 ARAL_CONCURRENCY_RACE_UNMARK_AFTER_CAS, // unmark after CAS to UNMARKING, before page_lock
314 ARAL_CONCURRENCY_RACE_FREEZ_BEFORE_CLAIM, // freez entry, before atomic-exchange
315 };
316
317 struct aral_concurrency_race_hook {
318 ARAL *ar;
319 void *target_ptr;
320 enum aral_concurrency_race_stage stage;
321 bool enabled;
322 bool waiting;
323 bool release;
324 };
325
326 static struct aral_concurrency_race_hook aral_concurrency_race_hook = { 0 };
327
328 // Counter incremented every time aral_claim_page_pointer_after_element___wait_for_unmark
329 // enters the cold path (i.e. observed UNMARKING in the trailer). Tests poll
330 // this to verify they actually exercised the cold path before completing.
331 static size_t aral_freez_unmarking_observed_count = 0;
332
333 // Arm the concurrency race hook for a (ar, ptr, stage) match.
334 // Sets the match fields first, then publishes `enabled = true` with a
335 // release-store. Paired with the acquire-load in aral_concurrency_race_pause,
336 // this guarantees a reader that observes enabled==true sees fully-published
337 // match fields. Without this ordering the compiler is free to publish
338 // `enabled` before the other fields, causing the pause to miss.
339 static inline void aral_concurrency_race_hook_arm(ARAL *ar, void *target_ptr,
340 enum aral_concurrency_race_stage stage) {
341 aral_concurrency_race_hook.ar = ar;
342 aral_concurrency_race_hook.target_ptr = target_ptr;
343 aral_concurrency_race_hook.stage = stage;
344 aral_concurrency_race_hook.waiting = false;
345 aral_concurrency_race_hook.release = false;
346 __atomic_store_n(&aral_concurrency_race_hook.enabled, true, __ATOMIC_RELEASE);
347 }
348
349 // Reset the hook. Callers should only invoke this after every concurrent
350 // reader is known to have stopped (i.e. all racing threads have been joined).
351 static inline void aral_concurrency_race_hook_reset(void) {
352 __atomic_store_n(&aral_concurrency_race_hook.enabled, false, __ATOMIC_RELEASE);
353 aral_concurrency_race_hook = (struct aral_concurrency_race_hook){ 0 };
354 }
355
356 static ALWAYS_INLINE void aral_concurrency_race_pause(ARAL *ar, void *ptr, enum aral_concurrency_race_stage stage) {
357 // Acquire-load on `enabled` pairs with the release-store in
358 // aral_concurrency_race_hook_arm so that if we observe enabled==true,
359 // the other match fields are fully published.
360 if(unlikely(__atomic_load_n(&aral_concurrency_race_hook.enabled, __ATOMIC_ACQUIRE) &&
361 aral_concurrency_race_hook.ar == ar &&
362 aral_concurrency_race_hook.target_ptr == ptr &&
363 aral_concurrency_race_hook.stage == stage)) {
364 __atomic_store_n(&aral_concurrency_race_hook.waiting, true, __ATOMIC_RELEASE);
365 while(!__atomic_load_n(&aral_concurrency_race_hook.release, __ATOMIC_ACQUIRE))
366 tinysleep();
367 }
368 }
369 #endif
370
371 static ALWAYS_INLINE bool aral_adders_trylock(ARAL *ar, bool marked) {
372 if(likely(!(ar->config.options & ARAL_LOCKLESS))) {
373 size_t idx = mark_to_idx(marked);
374 return spinlock_trylock(&ar->ops[idx].adders.spinlock);
375 }
376
377 return true;
378 }
379
380 static ALWAYS_INLINE void aral_adders_lock(ARAL *ar, bool marked) {
381 if(likely(!(ar->config.options & ARAL_LOCKLESS))) {
382 size_t idx = mark_to_idx(marked);
383 spinlock_lock(&ar->ops[idx].adders.spinlock);
384 }
385 }
386
387 static ALWAYS_INLINE void aral_adders_unlock(ARAL *ar, bool marked) {
388 if(likely(!(ar->config.options & ARAL_LOCKLESS))) {
389 size_t idx = mark_to_idx(marked);
390 spinlock_unlock(&ar->ops[idx].adders.spinlock);
391 }
392 }
393
394 static void aral_delete_leftover_files(const char *name, const char *path, const char *required_prefix) {
395 DIR *dir = opendir(path);
396 if(!dir) return;
397
398 char full_path[FILENAME_MAX + 1];
399 size_t len = strlen(required_prefix);
400
401 struct dirent *de = NULL;
402 while((de = readdir(dir))) {
403 if(de->d_type == DT_DIR)
404 continue;
405
406 if(strncmp(de->d_name, required_prefix, len) != 0)
407 continue;
408
409 snprintfz(full_path, FILENAME_MAX, "%s/%s", path, de->d_name);
410 netdata_log_info("ARAL: '%s' removing left-over file '%s'", name, full_path);
411 if(unlikely(unlink(full_path) == -1))
412 netdata_log_error("ARAL: '%s' cannot delete file '%s'", name, full_path);
413 }
414
415 closedir(dir);
416 }
417
418 // --------------------------------------------------------------------------------------------------------------------
419
420 #ifdef NETDATA_ARAL_INTERNAL_CHECKS
421 struct free_space {
422 size_t pages;
423 size_t pages_with_free_elements;
424 size_t max_free_elements_on_a_page;
425 size_t free_elements;
426 size_t max_page_elements;
427 ARAL_PAGE *p, *lp;
428 };
429
430 static inline struct free_space check_free_space___aral_lock_needed(ARAL *ar, ARAL_PAGE *my_page, bool marked) {
431 struct free_space f = { 0 };
432
433 f.max_page_elements = aral_max_allocation_size(ar) / ar->config.element_size;
434 for(f.p = *aral_pages_head_free(ar, marked); f.p ; f.lp = f.p, f.p = f.p->aral_lock.next) {
435 f.pages++;
436 internal_fatal(!f.p->page_lock.free_elements, "page is in the free list, but does not have any elements free");
437 internal_fatal(f.p->aral_lock.marked != marked, "page is in the wrong mark list");
438
439 if(f.p != my_page && f.max_free_elements_on_a_page < f.p->page_lock.free_elements)
440 f.max_free_elements_on_a_page = f.p->page_lock.free_elements;
441
442 f.free_elements += f.p->page_lock.free_elements;
443 f.pages_with_free_elements++;
444 }
445
446 for(f.p = *aral_pages_head_full(ar, marked); f.p ; f.lp = f.p, f.p = f.p->aral_lock.next) {
447 f.pages++;
448 internal_fatal(f.p->page_lock.free_elements, "found page with free items in a full page");
449 internal_fatal(f.p->aral_lock.marked != marked, "page is in the wrong mark list");
450 }
451
452 return f;
453 }
454 static inline bool is_page_in_list(ARAL_PAGE *head, ARAL_PAGE *page) {
455 for(ARAL_PAGE *p = head; p ; p = p->aral_lock.next)
456 if(p == page) return true;
457 return false;
458 }
459 #else
460
461 #define is_page_in_list(head, page) true
462
463 #endif
464
465
466 // --------------------------------------------------------------------------------------------------------------------
467 // find the page a pointer belongs to
468
469 #ifdef NETDATA_ARAL_INTERNAL_CHECKS
470 static inline ARAL_PAGE *find_page_with_allocation_internal_check(ARAL *ar, void *ptr, bool marked) {
471 aral_lock(ar);
472
473 uintptr_t seeking = (uintptr_t)ptr;
474 ARAL_PAGE *page;
475
476 for (page = *aral_pages_head_full(ar, marked); page; page = page->aral_lock.next) {
477 if (unlikely(seeking >= (uintptr_t)page->data && seeking < (uintptr_t)page->data + page->size))
478 break;
479 }
480
481 if(!page) {
482 for(page = *aral_pages_head_free(ar, marked); page ; page = page->aral_lock.next) {
483 if(unlikely(seeking >= (uintptr_t)page->data && seeking < (uintptr_t)page->data + page->size))
484 break;
485 }
486 }
487
488 aral_unlock(ar);
489
490 return page;
491 }
492 #endif
493
494 // --------------------------------------------------------------------------------------------------------------------
495 // Tagging the pointer with the 'marked' flag
496 //
497 // Trailer state machine (the low bits of the per-slot trailer word):
498 // 0 = freed / on the free list
499 // page = allocated, unmarked
500 // page | ARAL_TRAILER_MARKED = allocated, marked
501 // page | ARAL_TRAILER_UNMARKING = allocated, unmark in progress
502 // (page counters not yet updated)
503 //
504 // Page pointers must be aligned such that the low 2 bits are always 0,
505 // otherwise the tag bits would collide with real address bits. The static
506 // assert below enforces this at compile time on every supported platform.
507 //
508 // The UNMARKING state is set by aral_unmark_allocation() before it takes the
509 // page lock to decrement page->page_lock.marked_elements, and is cleared
510 // after the decrement is complete (still under page lock). While UNMARKING
511 // is visible, aral_freez_internal() observes it and waits, so:
512 // - the slot's refcount contribution remains in place, keeping the page
513 // alive across our trailer transition (no UAF on aral_page_lock())
514 // - freez never sees an unmarked trailer with a stale marked_elements
515 // counter (no spurious "marked > used" assertion)
516
517 #define ARAL_TRAILER_MARKED ((uintptr_t)0x1)
518 #define ARAL_TRAILER_UNMARKING ((uintptr_t)0x2)
519 #define ARAL_TRAILER_TAG_MASK (ARAL_TRAILER_MARKED | ARAL_TRAILER_UNMARKING)
520
521 _Static_assert((SYSTEM_REQUIRED_ALIGNMENT & ARAL_TRAILER_TAG_MASK) == 0,
522 "ARAL trailer tag bits collide with page pointer alignment");
523
524 static ALWAYS_INLINE ARAL_PAGE *aral_decode_page_pointer_after_element___do_NOT_have_aral_lock(ARAL *ar, void *ptr, uintptr_t tagged_page, bool *marked) {
525 *marked = (tagged_page & ARAL_TRAILER_MARKED) != 0;
526 ARAL_PAGE *page = (ARAL_PAGE *)(tagged_page & ~ARAL_TRAILER_TAG_MASK);
527
528 internal_fatal(!page,
529 "ARAL: '%s' possible corruption or double free of pointer %p",
530 ar->config.name, ptr);
531
532 #ifdef NETDATA_ARAL_INTERNAL_CHECKS
533 {
534 // find the page ptr belongs
535 ARAL_PAGE *page2 = find_page_with_allocation_internal_check(ar, ptr, *marked);
536 if(!page2) {
537 page2 = find_page_with_allocation_internal_check(ar, ptr, !(*marked));
538 internal_fatal(page2 && (*marked) && !page2->marked, "ARAL: '%s' page pointer is in different mark index",
539 ar->config.name);
540 }
541
542 internal_fatal(page != page2,
543 "ARAL: '%s' page pointers do not match!",
544 ar->config.name);
545
546 internal_fatal(!page2,
547 "ARAL: '%s' free of pointer %p is not in ARAL address space.",
548 ar->config.name, ptr);
549 }
550 #endif
551
552 internal_fatal((uintptr_t)page % SYSTEM_REQUIRED_ALIGNMENT != 0, "Pointer is not aligned properly");
553
554 return page;
555 }
556
557 // Retrieving the pointer and the 'marked' flag
558 static ALWAYS_INLINE ARAL_PAGE *aral_get_page_pointer_after_element___do_NOT_have_aral_lock(ARAL *ar, void *ptr, bool *marked) {
559 uint8_t *data = ptr;
560 uintptr_t *page_ptr = (uintptr_t *)&data[ar->config.element_ptr_offset];
561 uintptr_t tagged_page = __atomic_load_n(page_ptr, __ATOMIC_ACQUIRE); // Atomically load the tagged pointer
562
563 return aral_decode_page_pointer_after_element___do_NOT_have_aral_lock(ar, ptr, tagged_page, marked);
564 }
565
566 // Atomically claims an allocated slot for freeing.
567 //
568 // Hot path: single atomic-exchange to 0 (same primitive as before the unmark
569 // protocol existed - no extra load, no CAS).
570 //
571 // Cold path: if the exchange returned a value with UNMARKING set, we
572 // accidentally claimed a slot mid-unmark. Best-effort restore the UNMARKING
573 // state so unmark can finish, yield briefly, and retry. The restore CAS only
574 // succeeds if the trailer is still 0 (i.e. nothing else touched it since our
575 // exchange); if it fails, the next iteration's exchange picks up whatever
576 // settled value the other writer left behind.
577 //
578 // Returns NULL on a concurrent double-free or stale free.
579 static ALWAYS_INLINE ARAL_PAGE *aral_claim_page_pointer_after_element___wait_for_unmark(ARAL *ar, void *ptr, bool *marked) {
580 uint8_t *data = ptr;
581 uintptr_t *page_ptr = (uintptr_t *)&data[ar->config.element_ptr_offset];
582
583 while(true) {
584 uintptr_t prior = __atomic_exchange_n(page_ptr, 0, __ATOMIC_ACQ_REL);
585
586 if(unlikely(!prior)) {
587 *marked = false;
588 return NULL;
589 }
590
591 if(likely(!(prior & ARAL_TRAILER_UNMARKING)))
592 return aral_decode_page_pointer_after_element___do_NOT_have_aral_lock(ar, ptr, prior, marked);
593
594 // Cold path: we exchanged with the UNMARKING transition. Put it back
595 // (only succeeds if the trailer is still 0) and retry once unmark has
596 // had a chance to publish the final state.
597 uintptr_t zero = 0;
598 __atomic_compare_exchange_n(page_ptr, &zero, prior,
599 false, __ATOMIC_RELEASE, __ATOMIC_RELAXED);
600 #ifdef NETDATA_INTERNAL_CHECKS
601 __atomic_add_fetch(&aral_freez_unmarking_observed_count, 1, __ATOMIC_RELAXED);
602 #endif
603 tinysleep();
604 }
605 }
606
607 static ALWAYS_INLINE void aral_set_page_pointer_after_element___do_NOT_have_aral_lock(ARAL *ar, void *page, void *ptr, bool marked) {
608 uint8_t *data = ptr;
609 uintptr_t *page_ptr = (uintptr_t *)&data[ar->config.element_ptr_offset];
610 uintptr_t tagged_page = (uintptr_t)page;
611 if (marked) tagged_page |= ARAL_TRAILER_MARKED;
612 __atomic_store_n(page_ptr, tagged_page, __ATOMIC_RELEASE);
613 }
614
615 // --------------------------------------------------------------------------------------------------------------------
616 // check a free slot
617
618 #ifdef NETDATA_INTERNAL_CHECKS
619 static inline void aral_free_validate_internal_check(ARAL *ar, ARAL_FREE *fr) {
620 if(unlikely(fr->size < ar->config.element_size))
621 fatal("ARAL: '%s' free item of size %zu, less than the expected element size %zu",
622 ar->config.name, fr->size, ar->config.element_size);
623
624 if(unlikely(fr->size % ar->config.element_size))
625 fatal("ARAL: '%s' free item of size %zu is not multiple to element size %zu",
626 ar->config.name, fr->size, ar->config.element_size);
627 }
628 #else
629 #define aral_free_validate_internal_check(ar, fr) debug_dummy()
630 #endif
631
632 // --------------------------------------------------------------------------------------------------------------------
633 // page size management
634
635 static ALWAYS_INLINE size_t aral_element_slot_size(size_t requested_element_size, bool usable) {
636 // we need to add a page pointer after the element
637 // so, first align the element size to the pointer size
638 size_t element_size = memory_alignment(requested_element_size, sizeof(uintptr_t));
639
640 // then add the size of a pointer to it
641 element_size += sizeof(uintptr_t);
642
643 // make sure it is at least what we need for an ARAL_FREE slot
644 if (element_size < sizeof(ARAL_FREE))
645 element_size = sizeof(ARAL_FREE);
646
647 // and finally align it to the natural alignment
648 element_size = memory_alignment(element_size, SYSTEM_REQUIRED_ALIGNMENT);
649
650 if(usable)
651 return element_size - sizeof(uintptr_t);
652
653 return element_size;
654 }
655
656 static ALWAYS_INLINE size_t aral_elements_in_page_size(ARAL *ar, size_t page_size) {
657 if(ar->config.mmap.enabled)
658 return page_size / ar->config.element_size;
659
660 size_t aral_page_size = memory_alignment(sizeof(ARAL_PAGE), SYSTEM_REQUIRED_ALIGNMENT);
661 size_t remaining = page_size - aral_page_size;
662 return remaining / ar->config.element_size;
663 }
664
665 static ALWAYS_INLINE size_t aral_next_allocation_size___adders_lock_needed(ARAL *ar, bool marked) {
666 size_t idx = mark_to_idx(marked);
667 size_t size = ar->ops[idx].adders.allocation_size;
668
669 bool last_allocated_page = __atomic_load_n(&ar->ops[idx].atomic.last_allocated_page, __ATOMIC_RELAXED);
670 if(last_allocated_page) {
671 // we are growing, double the size
672
673 size *= 2;
674
675 size_t max = aral_max_allocation_size(ar);
676 if(size > max)
677 size = max;
678 ar->ops[idx].adders.allocation_size = size;
679 }
680
681 if(!ar->config.mmap.enabled && aral_malloc_use_mmap(ar, size)) {
682 // when doing malloc, don't allocate entire pages, but only what needed
683 size =
684 aral_elements_in_page_size(ar, size) * ar->config.element_size +
685 memory_alignment(sizeof(ARAL_PAGE), SYSTEM_REQUIRED_ALIGNMENT);
686 }
687
688 __atomic_store_n(&ar->ops[idx].atomic.last_allocated_page, true, __ATOMIC_RELAXED);
689
690 return size;
691 }
692
693 // --------------------------------------------------------------------------------------------------------------------
694
695 static ARAL_PAGE *aral_create_page___no_lock_needed(ARAL *ar, size_t size TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
696 struct aral_page_type_stats *stats;
697 ARAL_PAGE *page;
698
699 size_t total_size = size;
700
701 if(ar->config.mmap.enabled) {
702 page = callocz(1, sizeof(ARAL_PAGE));
703 ar->aral_lock.file_number++;
704
705 char filename[FILENAME_MAX + 1];
706 snprintfz(filename, FILENAME_MAX, "%s/array_alloc.mmap/%s.%zu", *ar->config.mmap.cache_dir, ar->config.mmap.filename, ar->aral_lock.file_number);
707 page->filename = strdupz(filename);
708 page->mapped = true;
709
710 page->data =
711 nd_mmap_advanced(page->filename, size, MAP_SHARED, 0, false, ar->config.options & ARAL_DONT_DUMP, NULL);
712 if (unlikely(!page->data))
713 out_of_memory(__FUNCTION__, size, page->filename);
714
715 total_size = size + sizeof(ARAL_PAGE);
716 stats = &ar->stats->mmap;
717 }
718 #ifdef NETDATA_TRACE_ALLOCATIONS
719 else {
720 page = callocz(1, sizeof(ARAL_PAGE));
721 page->data = mallocz_int(size TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
722 page->mapped = false;
723 __atomic_add_fetch(&ar->stats->malloc.allocations, 1, __ATOMIC_RELAXED);
724 __atomic_add_fetch(&ar->stats->malloc.allocated_bytes, size, __ATOMIC_RELAXED);
725 }
726 #else
727 else {
728 size_t ARAL_PAGE_size = memory_alignment(sizeof(ARAL_PAGE), SYSTEM_REQUIRED_ALIGNMENT);
729
730 if (aral_malloc_use_mmap(ar, size)) {
731 bool mapped;
732 uint8_t *ptr =
733 nd_mmap_advanced(NULL, size, MAP_ANONYMOUS | MAP_PRIVATE, 1, false, ar->config.options & ARAL_DONT_DUMP, NULL);
734 if (ptr) {
735 mapped = true;
736 stats = &ar->stats->mmap;
737 }
738 else {
739 ptr = mallocz(size);
740 mapped = false;
741 stats = &ar->stats->malloc;
742 }
743 page = (ARAL_PAGE *)ptr;
744 memset(page, 0, ARAL_PAGE_size);
745 page->data = &ptr[ARAL_PAGE_size];
746 page->mapped = mapped;
747 }
748 else {
749 uint8_t *ptr = mallocz(size);
750 page = (ARAL_PAGE *)ptr;
751 memset(page, 0, ARAL_PAGE_size);
752 page->data = &ptr[ARAL_PAGE_size];
753 page->mapped = false;
754
755 stats = &ar->stats->malloc;
756 }
757 }
758 #endif
759
760 spinlock_init(&page->available.spinlock);
761
762 for(size_t p = 0; p < ARAL_PAGE_INCOMING_PARTITIONS ;p++)
763 spinlock_init(&page->incoming[p].spinlock);
764
765 page->size = size;
766 page->max_elements = aral_elements_in_page_size(ar, page->size);
767 page->page_lock.free_elements = page->max_elements;
768 spinlock_init(&page->page_lock.spinlock);
769 page->refcount = 1;
770
771 size_t structures_size = sizeof(ARAL_PAGE) + page->max_elements * sizeof(void *);
772 size_t data_size = page->max_elements * ar->config.requested_element_size;
773 size_t padding_size = total_size - data_size - structures_size;
774
775 __atomic_add_fetch(&stats->allocations, 1, __ATOMIC_RELAXED);
776 __atomic_add_fetch(&stats->allocated_bytes, data_size, __ATOMIC_RELAXED);
777 __atomic_add_fetch(&stats->padding_bytes, padding_size, __ATOMIC_RELAXED);
778
779 __atomic_add_fetch(&ar->stats->structures.allocations, 1, __ATOMIC_RELAXED);
780 __atomic_add_fetch(&ar->stats->structures.allocated_bytes, structures_size, __ATOMIC_RELAXED);
781
782 // Initialize elements_segmented last with RELEASE
783 __atomic_store_n(&page->elements_segmented, 0, __ATOMIC_RELEASE);
784
785 return page;
786 }
787
788 static void aral_del_page___no_lock_needed(ARAL *ar, ARAL_PAGE *page TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
789 size_t idx = mark_to_idx(page->started_marked);
790 __atomic_store_n(&ar->ops[idx].atomic.last_allocated_page, false, __ATOMIC_RELAXED);
791
792 struct aral_page_type_stats *stats;
793 size_t max_elements = page->max_elements;
794 size_t size = page->size;
795 size_t total_size = size;
796
797 // free it
798 if (ar->config.mmap.enabled) {
799 stats = &ar->stats->mmap;
800 total_size = size + sizeof(ARAL_PAGE);
801
802 nd_munmap(page->data, page->size);
803
804 if (unlikely(unlink(page->filename) == 1))
805 netdata_log_error("Cannot delete file '%s'", page->filename);
806
807 freez((void *)page->filename);
808 freez(page);
809 }
810 else {
811 #ifdef NETDATA_TRACE_ALLOCATIONS
812 __atomic_sub_fetch(&ar->stats->malloc.allocations, 1, __ATOMIC_RELAXED);
813 __atomic_sub_fetch(&ar->stats->malloc.allocated_bytes, page->size - sizeof(ARAL_PAGE), __ATOMIC_RELAXED);
814
815 freez_int(page->data TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
816 freez(page);
817 #else
818 if(page->mapped) {
819 stats = &ar->stats->mmap;
820 nd_munmap(page, page->size);
821 }
822 else {
823 stats = &ar->stats->malloc;
824 freez(page);
825 }
826 #endif
827 }
828
829 size_t structures_size = sizeof(ARAL_PAGE) + max_elements * sizeof(void *);
830 size_t data_size = max_elements * ar->config.requested_element_size;
831 size_t padding_size = total_size - data_size - structures_size;
832
833 __atomic_sub_fetch(&stats->allocations, 1, __ATOMIC_RELAXED);
834 __atomic_sub_fetch(&stats->allocated_bytes, data_size, __ATOMIC_RELAXED);
835 __atomic_sub_fetch(&stats->padding_bytes, padding_size, __ATOMIC_RELAXED);
836
837 __atomic_sub_fetch(&ar->stats->structures.allocations, 1, __ATOMIC_RELAXED);
838 __atomic_sub_fetch(&ar->stats->structures.allocated_bytes, structures_size, __ATOMIC_RELAXED);
839 }
840
841 ALWAYS_INLINE WARNUNUSED
842 static bool aral_page_acquire(ARAL_PAGE *page) {
843 REFCOUNT rf = __atomic_add_fetch(&page->refcount, 1, __ATOMIC_ACQUIRE);
844 if(rf <= 0) {
845 __atomic_sub_fetch(&page->refcount, 1, __ATOMIC_RELAXED);
846 return false;
847 }
848
849 if(rf > (REFCOUNT)page->max_elements) {
850 __atomic_sub_fetch(&page->refcount, 1, __ATOMIC_RELAXED);
851 return false;
852 }
853
854 return true;
855 }
856
857 ALWAYS_INLINE WARNUNUSED
858 static ARAL_PAGE *aral_acquire_first_page(ARAL *ar, bool marked) {
859 aral_lock(ar);
860
861 ARAL_PAGE **head_ptr_free = aral_pages_head_free(ar, marked);
862 ARAL_PAGE *page = *head_ptr_free;
863
864 if(page && !aral_page_acquire(page))
865 page = NULL;
866
867 aral_unlock(ar);
868 return page;
869 }
870
871 ALWAYS_INLINE WARNUNUSED
872 static bool aral_page_release(ARAL_PAGE *page) {
873 REFCOUNT rf = __atomic_sub_fetch(&page->refcount, 1, __ATOMIC_RELEASE);
874 if(rf == 0) {
875 REFCOUNT expected = rf;
876 REFCOUNT desired = REFCOUNT_DELETED;
877 if (__atomic_compare_exchange_n(&page->refcount, &expected, desired, false, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
878 return true;
879 }
880
881 return false;
882 }
883
884 static ALWAYS_INLINE ARAL_PAGE *aral_get_first_page_with_a_free_slot(ARAL *ar, bool marked TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
885 size_t idx = mark_to_idx(marked);
886 __atomic_add_fetch(&ar->ops[idx].atomic.allocators, 1, __ATOMIC_RELAXED);
887
888 ARAL_PAGE *page = NULL;
889
890 retry_acquisition:
891
892 while(!(page = aral_acquire_first_page(ar, marked))) {
893 #ifdef NETDATA_ARAL_INTERNAL_CHECKS
894 (void)check_free_space___aral_lock_needed(ar, NULL, marked);
895 #endif
896
897 bool can_add = false;
898 size_t page_allocation_size = 0;
899 if(aral_adders_trylock(ar, marked)) {
900 // we can add a page - let's see it is really needed
901 size_t threads_currently_allocating = __atomic_load_n(&ar->ops[idx].atomic.allocators, __ATOMIC_RELAXED);
902 size_t threads_currently_deallocating = __atomic_load_n(&ar->ops[idx].atomic.deallocators, __ATOMIC_RELAXED);
903
904 // we will allocate a page, only if the number of elements required is more than the
905 // sum of all new allocations under their way plus the pages currently being deallocated
906 if(ar->ops[idx].adders.allocating_elements + threads_currently_deallocating < threads_currently_allocating) {
907 can_add = true;
908 page_allocation_size = aral_next_allocation_size___adders_lock_needed(ar, marked);
909 ar->ops[idx].adders.allocating_elements += aral_elements_in_page_size(ar, page_allocation_size);
910 }
911 aral_adders_unlock(ar, marked);
912 }
913
914 if(can_add) {
915 page = aral_create_page___no_lock_needed(ar, page_allocation_size TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
916 page->aral_lock.marked = page->started_marked = marked;
917
918 ARAL_PAGE **head_ptr_free = aral_pages_head_free(ar, marked);
919 aral_lock(ar);
920 DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(*head_ptr_free, page, aral_lock.prev, aral_lock.next);
921 page->aral_lock.head_ptr = head_ptr_free;
922 aral_unlock(ar);
923
924 aral_adders_lock(ar, marked);
925 ar->ops[idx].adders.allocating_elements -= aral_elements_in_page_size(ar, page_allocation_size);
926 aral_adders_unlock(ar, marked);
927
928 // we have a page that is all empty
929 // break the loop
930 break;
931 }
932 else {
933 // let the adders/deallocators do it
934 sched_yield();
935 tinysleep();
936 }
937 }
938
939 // we have a page
940 // it is acquired
941 // and aral is NOT locked
942
943 internal_fatal(!page,
944 "ARAL: '%s' failed to find a page with a free element",
945 ar->config.name);
946
947 #ifdef NETDATA_INTERNAL_CHECKS
948 aral_unittest_wait_for_race_window(ar, page);
949 #endif
950
951 aral_page_lock(ar, page);
952
953 if(unlikely(!page->page_lock.free_elements)) {
954 aral_page_unlock(ar, page);
955 bool deleted = aral_page_release(page);
956 (void)deleted;
957 page = NULL;
958 goto retry_acquisition;
959 }
960
961 internal_fatal(page->max_elements != page->page_lock.used_elements + page->page_lock.free_elements,
962 "ARAL: '%s' page element counters do not match, "
963 "page says it can handle %zu elements, "
964 "but there are %zu used and %zu free items, "
965 "total %zu items",
966 ar->config.name,
967 (size_t)page->max_elements,
968 (size_t)page->page_lock.used_elements, (size_t)page->page_lock.free_elements,
969 (size_t)page->page_lock.used_elements + (size_t)page->page_lock.free_elements);
970
971 internal_fatal(page->page_lock.marked_elements > page->page_lock.used_elements,
972 "page has more marked elements than the used ones");
973
974 page->page_lock.used_elements++;
975 page->page_lock.free_elements--;
976
977 if(marked)
978 page->page_lock.marked_elements++;
979
980 if(unlikely(page->page_lock.used_elements == page->max_elements)) {
981 aral_lock(ar);
982 ARAL_PAGE **head_ptr_full = aral_pages_head_full(ar, marked);
983 internal_fatal(!is_page_in_list(*page->aral_lock.head_ptr, page), "Page is not in this list");
984 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*page->aral_lock.head_ptr, page, aral_lock.prev, aral_lock.next);
985 DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(*head_ptr_full, page, aral_lock.prev, aral_lock.next);
986 page->aral_lock.head_ptr = head_ptr_full;
987 aral_unlock(ar);
988 }
989
990 aral_page_unlock(ar, page);
991
992 __atomic_sub_fetch(&ar->ops[idx].atomic.allocators, 1, __ATOMIC_RELAXED);
993 __atomic_add_fetch(&ar->atomic.user_malloc_operations, 1, __ATOMIC_RELAXED);
994
995 return page;
996 }
997
998 static ALWAYS_INLINE void *aral_get_free_slot___no_lock_required(ARAL *ar, ARAL_PAGE *page, bool marked) {
999 // Try fast path first
1000 uint64_t slot = __atomic_fetch_add(&page->elements_segmented, 1, __ATOMIC_ACQUIRE);
1001 if (slot < page->max_elements) {
1002 // Fast path - we got a valid slot
1003 uint8_t *data = page->data + (slot * ar->config.element_size);
1004
1005 // Set the page pointer after the element
1006 aral_set_page_pointer_after_element___do_NOT_have_aral_lock(ar, page, data, marked);
1007
1008 aral_element_given(ar, page);
1009 return data;
1010 }
1011
1012 // Fall back to existing mechanism for reused memory
1013 aral_page_available_lock(ar, page);
1014
1015 while(!page->available.list) {
1016 uint32_t bitmap = __atomic_load_n(&page->incoming_partition_bitmap, __ATOMIC_ACQUIRE);
1017 if (!bitmap)
1018 fatal("ARAL: bitmap of incoming free elements cannot be empty at this point");
1019
1020 while(bitmap) {
1021 size_t partition = __builtin_ffs((int)bitmap) - 1;
1022 // for(partition = 0; partition < ARAL_PAGE_INCOMING_PARTITIONS ; partition++) {
1023 // if (bitmap & (1U << partition))
1024 // break;
1025 // }
1026
1027 if (partition >= ARAL_PAGE_INCOMING_PARTITIONS)
1028 fatal("ARAL: partition %zu must be smaller than %d", partition, ARAL_PAGE_INCOMING_PARTITIONS);
1029
1030 if (aral_page_incoming_trylock(ar, page, partition)) {
1031 page->available.list = page->incoming[partition].list;
1032 page->incoming[partition].list = NULL;
1033 __atomic_fetch_and(&page->incoming_partition_bitmap, ~(1U << partition), __ATOMIC_RELEASE);
1034 aral_page_incoming_unlock(ar, page, partition);
1035 break;
1036 }
1037 else
1038 bitmap &= ~(1U << partition);
1039 }
1040 }
1041
1042 ARAL_FREE *found_fr = page->available.list;
1043 internal_fatal(!found_fr, "ARAL: '%s' incoming free list, cannot be NULL.", ar->config.name);
1044 page->available.list = found_fr->next;
1045
1046 aral_page_available_unlock(ar, page);
1047
1048 // Set the page pointer after the element
1049 aral_set_page_pointer_after_element___do_NOT_have_aral_lock(ar, page, found_fr, marked);
1050
1051 aral_element_given(ar, page);
1052
1053 return found_fr;
1054 }
1055
1056 static inline void aral_add_free_slot___no_lock_required(ARAL *ar, ARAL_PAGE *page, void *ptr) {
1057 ARAL_FREE *fr = (ARAL_FREE *)ptr;
1058 fr->size = ar->config.element_size;
1059
1060 // use the slot id of the item to be freed to determine the partition number
1061 size_t start = (((uint8_t *)ptr - page->data) / ar->config.element_size) % ARAL_PAGE_INCOMING_PARTITIONS;
1062
1063 while (true) {
1064 for (size_t partition = start; partition < ARAL_PAGE_INCOMING_PARTITIONS; partition++) {
1065 if (aral_page_incoming_trylock(ar, page, partition)) {
1066 fr->next = page->incoming[partition].list;
1067 page->incoming[partition].list = fr;
1068 __atomic_fetch_or(&page->incoming_partition_bitmap, 1U << partition, __ATOMIC_RELEASE);
1069 aral_page_incoming_unlock(ar, page, partition);
1070 return;
1071 }
1072 }
1073
1074 start = 0;
1075 }
1076 }
1077
1078 ALWAYS_INLINE void *aral_callocz_internal(ARAL *ar, bool marked TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
1079 void *r = aral_mallocz_internal(ar, marked TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1080 memset(r, 0, ar->config.requested_element_size);
1081 return r;
1082 }
1083
1084 void *aral_mallocz_internal(ARAL *ar, bool marked TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
1085 #if defined(FSANITIZE_ADDRESS)
1086 if(ar->stats) {
1087 __atomic_add_fetch(&ar->stats->malloc.allocations, 1, __ATOMIC_RELAXED);
1088 __atomic_add_fetch(&ar->stats->malloc.allocated_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
1089 __atomic_add_fetch(&ar->stats->malloc.used_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
1090 }
1091 return mallocz(ar->config.requested_element_size);
1092 #endif
1093
1094 // reserve a slot on a free page
1095 ARAL_PAGE *page = aral_get_first_page_with_a_free_slot(ar, marked TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1096 // the page returned has reserved a slot for us
1097
1098 void *data = aral_get_free_slot___no_lock_required(ar, page, marked);
1099
1100 internal_fatal((uintptr_t)data % SYSTEM_REQUIRED_ALIGNMENT != 0, "Pointer is not aligned properly");
1101
1102 return data;
1103 }
1104
1105 void aral_unmark_allocation(ARAL *ar, void *ptr) {
1106 #if defined(FSANITIZE_ADDRESS)
1107 return;
1108 #endif
1109
1110 if(unlikely(!ptr)) return;
1111
1112 #ifdef NETDATA_INTERNAL_CHECKS
1113 aral_concurrency_race_pause(ar, ptr, ARAL_CONCURRENCY_RACE_UNMARK_BEFORE_CAS);
1114 #endif
1115
1116 uint8_t *data = ptr;
1117 uintptr_t *page_ptr = (uintptr_t *)&data[ar->config.element_ptr_offset];
1118
1119 // Stage 1: claim the unmark transition.
1120 // CAS the trailer from (page, MARKED) to (page, UNMARKING). On failure
1121 // (slot was freed, already unmarked, another unmark won), bail without
1122 // touching counters.
1123 //
1124 // Holding the UNMARKING state has two crucial effects:
1125 // - aral_freez_internal observes UNMARKING and waits, so the slot's
1126 // refcount contribution stays in place and the page cannot be
1127 // destroyed under us.
1128 // - freez never observes the slot as unmarked while marked_elements
1129 // is still high, so the "marked > used" invariant is preserved.
1130 uintptr_t initial = __atomic_load_n(page_ptr, __ATOMIC_ACQUIRE);
1131 if((initial & ARAL_TRAILER_TAG_MASK) != ARAL_TRAILER_MARKED)
1132 return;
1133 uintptr_t desired = (initial & ~ARAL_TRAILER_TAG_MASK) | ARAL_TRAILER_UNMARKING;
1134 if(!__atomic_compare_exchange_n(page_ptr, &initial, desired,
1135 false, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE))
1136 return;
1137
1138 #ifdef NETDATA_INTERNAL_CHECKS
1139 aral_concurrency_race_pause(ar, ptr, ARAL_CONCURRENCY_RACE_UNMARK_AFTER_CAS);
1140 #endif
1141
1142 // Stage 2: under page_lock, decrement counters and update page lists.
1143 bool was_marked;
1144 ARAL_PAGE *page = aral_decode_page_pointer_after_element___do_NOT_have_aral_lock(ar, ptr, initial, &was_marked);
1145 (void)was_marked;
1146
1147 aral_page_lock(ar, page);
1148 internal_fatal(!page->page_lock.marked_elements, "Marked counter going negative.");
1149 bool unmark = (--page->page_lock.marked_elements == 0) && page->page_lock.used_elements;
1150
1151 if(unmark) {
1152 aral_lock(ar);
1153 internal_fatal(!is_page_in_list(*page->aral_lock.head_ptr, page), "Page is not in this list");
1154
1155 ARAL_PAGE **head_ptr_to = (page->page_lock.free_elements) ? aral_pages_head_free(ar, false) : aral_pages_head_full(ar, false);
1156 if(page->aral_lock.head_ptr != head_ptr_to) {
1157 internal_fatal(!is_page_in_list(*page->aral_lock.head_ptr, page), "Page is not in this list");
1158 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*page->aral_lock.head_ptr, page, aral_lock.prev, aral_lock.next);
1159 DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(*head_ptr_to, page, aral_lock.prev, aral_lock.next);
1160 page->aral_lock.head_ptr = head_ptr_to;
1161 page->aral_lock.marked = false;
1162 }
1163
1164 internal_fatal(page->page_lock.marked_elements > page->page_lock.used_elements,
1165 "page has more marked elements than the used ones");
1166 aral_unlock(ar);
1167 }
1168
1169 // Stage 3: publish the final UNMARKED state.
1170 // Atomic store transitions the trailer from (page, UNMARKING) to (page, UNMARKED).
1171 // Done under page_lock so any waiting freez observes a settled trailer
1172 // only after our counter update is committed.
1173 __atomic_store_n(page_ptr, (uintptr_t)page, __ATOMIC_RELEASE);
1174
1175 aral_page_unlock(ar, page);
1176 }
1177
1178 void aral_freez_internal(ARAL *ar, void *ptr TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
1179 #if defined(FSANITIZE_ADDRESS)
1180 if(ptr && ar->stats) {
1181 __atomic_sub_fetch(&ar->stats->malloc.allocations, 1, __ATOMIC_RELAXED);
1182 __atomic_sub_fetch(&ar->stats->malloc.allocated_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
1183 __atomic_sub_fetch(&ar->stats->malloc.used_bytes, ar->config.requested_element_size, __ATOMIC_RELAXED);
1184 }
1185 freez(ptr);
1186 return;
1187 #endif
1188
1189 if(unlikely(!ptr)) return;
1190
1191 #ifdef NETDATA_INTERNAL_CHECKS
1192 aral_concurrency_race_pause(ar, ptr, ARAL_CONCURRENCY_RACE_FREEZ_BEFORE_CLAIM);
1193 #endif
1194
1195 // Atomically claim the trailer:
1196 // - On a concurrent double-free or stale-free, the loser observes a
1197 // NULL pointer and fatal()s here.
1198 // - If aral_unmark_allocation has CAS'd the trailer to UNMARKING, we
1199 // wait until it publishes the final UNMARKED state, so we never see
1200 // the slot as unmarked while marked_elements is still high.
1201 bool marked;
1202 ARAL_PAGE *page = aral_claim_page_pointer_after_element___wait_for_unmark(ar, ptr, &marked);
1203 if(unlikely(!page))
1204 fatal("ARAL: '%s' double free, stale free, or corrupted pointer %p", ar->config.name, ptr);
1205
1206 size_t idx = mark_to_idx(marked);
1207 __atomic_add_fetch(&ar->ops[idx].atomic.deallocators, 1, __ATOMIC_RELAXED);
1208
1209 // make this element available
1210 aral_add_free_slot___no_lock_required(ar, page, ptr);
1211
1212 // statistic, outside the lock
1213 aral_element_returned(ar, page);
1214 __atomic_add_fetch(&ar->atomic.user_free_operations, 1, __ATOMIC_RELAXED);
1215
1216 aral_page_lock(ar, page);
1217 internal_fatal(!page->page_lock.used_elements,
1218 "ARAL: '%s' pointer %p is inside a page without any active allocations.",
1219 ar->config.name, ptr);
1220
1221 internal_fatal(page->max_elements != page->page_lock.used_elements + page->page_lock.free_elements,
1222 "ARAL: '%s' page element counters do not match, "
1223 "page says it can handle %zu elements, "
1224 "but there are %zu used and %zu free items, "
1225 "total %zu items",
1226 ar->config.name,
1227 (size_t)page->max_elements,
1228 (size_t)page->page_lock.used_elements, (size_t)page->page_lock.free_elements,
1229 (size_t)page->page_lock.used_elements + (size_t)page->page_lock.free_elements
1230 );
1231
1232 page->page_lock.used_elements--;
1233 page->page_lock.free_elements++;
1234
1235 internal_fatal(marked && !page->page_lock.marked_elements, "Marked counter going negative.");
1236 bool unmark = marked && --page->page_lock.marked_elements == 0 && page->page_lock.used_elements;
1237
1238 internal_fatal(page->max_elements != page->page_lock.used_elements + page->page_lock.free_elements,
1239 "ARAL: '%s' page element counters do not match, "
1240 "page says it can handle %zu elements, "
1241 "but there are %zu used and %zu free items, "
1242 "total %zu items",
1243 ar->config.name,
1244 (size_t)page->max_elements,
1245 (size_t)page->page_lock.used_elements, (size_t)page->page_lock.free_elements,
1246 (size_t)page->page_lock.used_elements + (size_t)page->page_lock.free_elements);
1247
1248 internal_fatal(page->page_lock.marked_elements > page->page_lock.used_elements,
1249 "page has more marked elements than the used ones");
1250
1251 // release it
1252 if(unlikely(aral_page_release(page))) {
1253 internal_fatal(page->page_lock.used_elements, "page has used elements but has been acquired for deletion");
1254 internal_fatal(page->page_lock.marked_elements, "page has marked elements but not used ones");
1255
1256 aral_lock(ar);
1257 internal_fatal(!is_page_in_list(*page->aral_lock.head_ptr, page), "Page is not in this list");
1258
1259 if(*page->aral_lock.head_ptr != page || page->aral_lock.prev != page || page->aral_lock.next != NULL) {
1260 // there are more pages with free items - delete it
1261 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*page->aral_lock.head_ptr, page, aral_lock.prev, aral_lock.next);
1262 aral_unlock(ar);
1263 aral_page_unlock(ar, page);
1264 __atomic_sub_fetch(&ar->ops[idx].atomic.deallocators, 1, __ATOMIC_RELAXED);
1265 aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1266 return;
1267 }
1268
1269 // this is the last page with free items - keep it
1270 // Reset elements_segmented first to prevent new fast-path allocations
1271 __atomic_store_n(&page->elements_segmented, 0, __ATOMIC_RELEASE);
1272
1273 // Clear available list under its lock
1274 aral_page_available_lock(ar, page);
1275 page->available.list = NULL;
1276 aral_page_available_unlock(ar, page);
1277
1278 // Clear incoming partition lists under their respective locks
1279 // to synchronize with allocators in aral_get_free_slot___no_lock_required
1280 for(size_t p = 0; p < ARAL_PAGE_INCOMING_PARTITIONS; p++) {
1281 aral_page_incoming_lock(ar, page, p);
1282 page->incoming[p].list = NULL;
1283 aral_page_incoming_unlock(ar, page, p);
1284 }
1285
1286 // Clear bitmap last with atomic operation to ensure visibility
1287 __atomic_store_n(&page->incoming_partition_bitmap, 0, __ATOMIC_RELEASE);
1288 __atomic_store_n(&page->refcount, 0, __ATOMIC_RELAXED);
1289 aral_unlock(ar);
1290 }
1291 else if(unlikely(unmark)) {
1292 aral_lock(ar);
1293
1294 ARAL_PAGE **head_ptr_to = aral_pages_head_free(ar, false);
1295 if(page->aral_lock.head_ptr != head_ptr_to) {
1296 internal_fatal(!is_page_in_list(*page->aral_lock.head_ptr, page), "Page is not in this list");
1297 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*page->aral_lock.head_ptr, page, aral_lock.prev, aral_lock.next);
1298 DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(*head_ptr_to, page, aral_lock.prev, aral_lock.next);
1299 page->aral_lock.head_ptr = head_ptr_to;
1300 page->aral_lock.marked = false;
1301 }
1302 aral_unlock(ar);
1303 }
1304 else if(unlikely(page->page_lock.used_elements == page->max_elements - 1)) {
1305 aral_lock(ar);
1306 ARAL_PAGE **head_ptr_to = aral_pages_head_free(ar, page->aral_lock.marked);
1307 if(page->aral_lock.head_ptr != head_ptr_to) {
1308 internal_fatal(!is_page_in_list(*page->aral_lock.head_ptr, page), "Page is not in this list");
1309 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*page->aral_lock.head_ptr, page, aral_lock.prev, aral_lock.next);
1310 DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(*head_ptr_to, page, aral_lock.prev, aral_lock.next);
1311 page->aral_lock.head_ptr = head_ptr_to;
1312 }
1313 aral_unlock(ar);
1314 }
1315
1316 aral_page_unlock(ar, page);
1317 __atomic_sub_fetch(&ar->ops[idx].atomic.deallocators, 1, __ATOMIC_RELAXED);
1318 }
1319
1320 void aral_destroy_internal(ARAL *ar TRACE_ALLOCATIONS_FUNCTION_DEFINITION_PARAMS) {
1321 aral_lock(ar);
1322
1323 ARAL_PAGE **head_ptr = aral_pages_head_free(ar, false);
1324 ARAL_PAGE *page;
1325 while((page = *head_ptr)) {
1326 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*head_ptr, page, aral_lock.prev, aral_lock.next);
1327 aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1328 }
1329
1330 head_ptr = aral_pages_head_free(ar, true);
1331 while((page = *head_ptr)) {
1332 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*head_ptr, page, aral_lock.prev, aral_lock.next);
1333 aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1334 }
1335
1336 head_ptr = aral_pages_head_full(ar, false);
1337 while((page = *head_ptr)) {
1338 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*head_ptr, page, aral_lock.prev, aral_lock.next);
1339 aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1340 }
1341
1342 head_ptr = aral_pages_head_full(ar, true);
1343 while((page = *head_ptr)) {
1344 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*head_ptr, page, aral_lock.prev, aral_lock.next);
1345 aral_del_page___no_lock_needed(ar, page TRACE_ALLOCATIONS_FUNCTION_CALL_PARAMS);
1346 }
1347
1348 aral_unlock(ar);
1349
1350 if(ar->config.options & ARAL_ALLOCATED_STATS)
1351 freez(ar->stats);
1352
1353 freez(ar);
1354 }
1355
1356 size_t aral_requested_element_size(ARAL *ar) {
1357 return ar->config.requested_element_size;
1358 }
1359
1360 size_t aral_actual_element_size(ARAL *ar) {
1361 return ar->config.element_size;
1362 }
1363
1364 static size_t aral_max_page_size_malloc = ARAL_MAX_PAGE_SIZE_MALLOC;
1365 size_t aral_optimal_malloc_page_size(void) {
1366 return aral_max_page_size_malloc;
1367 }
1368
1369 void aral_optimal_malloc_page_size_set(size_t size) {
1370 aral_max_page_size_malloc = size < ARAL_MIN_PAGE_SIZE ? ARAL_MIN_PAGE_SIZE : size;
1371 }
1372
1373 static size_t aral_requested_max_page_size(ARAL *ar) {
1374 if(!ar->config.requested_max_page_size)
1375 return ar->config.mmap.enabled ? ARAL_MAX_PAGE_SIZE_MMAP : aral_optimal_malloc_page_size();
1376 else
1377 return ar->config.requested_max_page_size;
1378 }
1379
1380 static size_t aral_max_allocation_size(ARAL *ar) {
1381 size_t size = memory_alignment(aral_requested_max_page_size(ar), ar->config.system_page_size);
1382 if(size < ar->config.min_required_page_size)
1383 size = ar->config.min_required_page_size;
1384
1385 return size;
1386 }
1387
1388 ARAL *aral_create(const char *name, size_t element_size, size_t initial_page_elements, size_t max_page_size,
1389 struct aral_statistics *stats, const char *filename, const char **cache_dir,
1390 bool mmap, bool lockless, bool dont_dump) {
1391 ARAL *ar = callocz(1, sizeof(ARAL));
1392 ar->config.options = ((lockless) ? ARAL_LOCKLESS : 0) | ((dont_dump) ? ARAL_DONT_DUMP : 0);
1393 ar->config.requested_element_size = element_size;
1394 ar->config.initial_page_elements = initial_page_elements;
1395 ar->config.requested_max_page_size = max_page_size;
1396 ar->config.mmap.filename = filename;
1397 ar->config.mmap.cache_dir = cache_dir;
1398 ar->config.mmap.enabled = mmap;
1399 strncpyz(ar->config.name, name, ARAL_MAX_NAME);
1400 spinlock_init(&ar->aral_lock.spinlock);
1401 spinlock_init(&ar->ops[0].adders.spinlock);
1402 spinlock_init(&ar->ops[1].adders.spinlock);
1403
1404 if(stats) {
1405 ar->stats = stats;
1406 ar->config.options &= ~ARAL_ALLOCATED_STATS;
1407 }
1408 else {
1409 ar->stats = callocz(1, sizeof(struct aral_statistics));
1410 ar->config.options |= ARAL_ALLOCATED_STATS;
1411 }
1412
1413 // ----------------------------------------------------------------------------------------------------------------
1414 // disable mmap if the directories are not given
1415
1416 if(ar->config.mmap.enabled && (!ar->config.mmap.cache_dir || !*ar->config.mmap.cache_dir)) {
1417 netdata_log_error("ARAL: '%s' mmap cache directory is not configured properly, disabling mmap.", ar->config.name);
1418 ar->config.mmap.enabled = false;
1419 internal_fatal(true, "ARAL: '%s' mmap cache directory is not configured properly", ar->config.name);
1420 }
1421
1422 // ----------------------------------------------------------------------------------------------------------------
1423 // calculate element size, after adding our pointer
1424
1425 ar->config.element_size = aral_element_slot_size(ar->config.requested_element_size, false);
1426
1427 // we write the page pointer just after each element
1428 ar->config.element_ptr_offset = ar->config.element_size - sizeof(uintptr_t);
1429
1430 if(ar->config.requested_element_size + sizeof(uintptr_t) > ar->config.element_size)
1431 fatal("ARAL: '%s' failed to calculate properly page_ptr_offset: "
1432 "element size %zu, sizeof(uintptr_t) %zu, natural alignment %zu, "
1433 "final element size %zu, page_ptr_offset %zu",
1434 ar->config.name, ar->config.requested_element_size, sizeof(uintptr_t),
1435 SYSTEM_REQUIRED_ALIGNMENT,
1436 ar->config.element_size, ar->config.element_ptr_offset);
1437
1438 // ----------------------------------------------------------------------------------------------------------------
1439 // calculate allocation sizes
1440
1441 ar->config.system_page_size = os_get_system_page_size();
1442
1443 if (ar->config.initial_page_elements < 2)
1444 ar->config.initial_page_elements = 2;
1445
1446 // find the minimum page size we will use
1447 ar->config.min_required_page_size = memory_alignment(sizeof(ARAL_PAGE), SYSTEM_REQUIRED_ALIGNMENT) + 2 * ar->config.element_size;
1448
1449 if(ar->config.min_required_page_size < ARAL_MIN_PAGE_SIZE)
1450 ar->config.min_required_page_size = ARAL_MIN_PAGE_SIZE;
1451
1452 ar->config.min_required_page_size = memory_alignment(ar->config.min_required_page_size, ar->config.system_page_size);
1453
1454 // set the starting allocation size for both marked and unmarked partitions
1455 ar->ops[0].adders.allocation_size = ar->ops[1].adders.allocation_size = ar->config.min_required_page_size;
1456
1457 // ----------------------------------------------------------------------------------------------------------------
1458
1459 ar->aral_lock.pages_free = NULL;
1460 ar->aral_lock.pages_marked_free = NULL;
1461 ar->aral_lock.file_number = 0;
1462
1463 // ----------------------------------------------------------------------------------------------------------------
1464
1465 if(ar->config.mmap.enabled) {
1466 char directory_name[FILENAME_MAX + 1];
1467 snprintfz(directory_name, FILENAME_MAX, "%s/array_alloc.mmap", *ar->config.mmap.cache_dir);
1468 int r = mkdir(directory_name, 0775);
1469 if (r != 0 && errno != EEXIST)
1470 fatal("Cannot create directory '%s'", directory_name);
1471
1472 char file[FILENAME_MAX + 1];
1473 snprintfz(file, FILENAME_MAX, "%s.", ar->config.mmap.filename);
1474 aral_delete_leftover_files(ar->config.name, directory_name, file);
1475 }
1476
1477 errno_clear();
1478 internal_error(true,
1479 "ARAL: '%s' "
1480 "element size %zu (requested %zu bytes), "
1481 "min elements per page %zu (requested %zu), "
1482 "max elements per page %zu, "
1483 "max page size %zu bytes (requested %zu) "
1484 , ar->config.name
1485 , ar->config.element_size, ar->config.requested_element_size
1486 , ar->ops[0].adders.allocation_size / ar->config.element_size, ar->config.initial_page_elements
1487 , aral_max_allocation_size(ar) / ar->config.element_size
1488 , aral_max_allocation_size(ar), ar->config.requested_max_page_size
1489 );
1490
1491 __atomic_add_fetch(&ar->stats->structures.allocations, 1, __ATOMIC_RELAXED);
1492 __atomic_add_fetch(&ar->stats->structures.allocated_bytes, sizeof(ARAL), __ATOMIC_RELAXED);
1493 return ar;
1494 }
1495
1496 // --------------------------------------------------------------------------------------------------------------------
1497 // global aral caching
1498
1499 #define ARAL_BY_SIZE_MAX_SIZE 1024
1500
1501 struct aral_by_size {
1502 ARAL *ar;
1503 int32_t refcount;
1504 };
1505
1506 struct {
1507 struct aral_statistics shared_statistics;
1508 SPINLOCK spinlock;
1509 struct aral_by_size array[ARAL_BY_SIZE_MAX_SIZE + 1];
1510 } aral_by_size_globals = {};
1511
1512 struct aral_statistics *aral_by_size_statistics(void) {
1513 return &aral_by_size_globals.shared_statistics;
1514 }
1515
1516 size_t aral_by_size_structures_bytes(void) {
1517 return aral_structures_bytes_from_stats(&aral_by_size_globals.shared_statistics);
1518 }
1519
1520 size_t aral_by_size_free_bytes(void) {
1521 return aral_free_bytes_from_stats(&aral_by_size_globals.shared_statistics);
1522 }
1523
1524 size_t aral_by_size_used_bytes(void) {
1525 return aral_used_bytes_from_stats(&aral_by_size_globals.shared_statistics);
1526 }
1527
1528 size_t aral_by_size_padding_bytes(void) {
1529 return aral_padding_bytes_from_stats(&aral_by_size_globals.shared_statistics);
1530 }
1531
1532 ARAL *aral_by_size_acquire(size_t size) {
1533 spinlock_lock(&aral_by_size_globals.spinlock);
1534
1535 ARAL *ar = NULL;
1536
1537 if(size <= ARAL_BY_SIZE_MAX_SIZE && aral_by_size_globals.array[size].ar) {
1538 ar = aral_by_size_globals.array[size].ar;
1539 aral_by_size_globals.array[size].refcount++;
1540
1541 internal_fatal(
1542 aral_requested_element_size(ar) != size, "ARAL BY SIZE: aral has size %zu but we want %zu",
1543 aral_requested_element_size(ar), size);
1544 }
1545
1546 if(!ar) {
1547 char buf[30 + 1];
1548 snprintf(buf, 30, "size-%zu", size);
1549 ar = aral_create(buf,
1550 size,
1551 0,
1552 0,
1553 &aral_by_size_globals.shared_statistics,
1554 NULL, NULL, false, false, false);
1555
1556 if(size <= ARAL_BY_SIZE_MAX_SIZE) {
1557 aral_by_size_globals.array[size].ar = ar;
1558 aral_by_size_globals.array[size].refcount = 1;
1559 }
1560 }
1561
1562 spinlock_unlock(&aral_by_size_globals.spinlock);
1563
1564 return ar;
1565 }
1566
1567 void aral_by_size_release(ARAL *ar) {
1568 size_t size = aral_requested_element_size(ar);
1569
1570 if(size <= ARAL_BY_SIZE_MAX_SIZE) {
1571 spinlock_lock(&aral_by_size_globals.spinlock);
1572
1573 internal_fatal(aral_by_size_globals.array[size].ar != ar,
1574 "ARAL BY SIZE: aral pointers do not match");
1575
1576 if(aral_by_size_globals.array[size].refcount <= 0)
1577 fatal("ARAL BY SIZE: double release detected");
1578
1579 aral_by_size_globals.array[size].refcount--;
1580 // if(!aral_by_size_globals.array[size].refcount) {
1581 // aral_destroy(aral_by_size_globals.array[size].ar);
1582 // aral_by_size_globals.array[size].ar = NULL;
1583 // }
1584
1585 spinlock_unlock(&aral_by_size_globals.spinlock);
1586 }
1587 else
1588 aral_destroy(ar);
1589 }
1590
1591 // --------------------------------------------------------------------------------------------------------------------
1592 // unittest
1593
1594 struct aral_unittest_config {
1595 bool single_threaded;
1596 bool stop;
1597 ARAL *ar;
1598 size_t elements;
1599 size_t threads;
1600 int errors;
1601 };
1602
1603 struct aral_unittest_entry {
1604 char TXT[27];
1605 char txt[27];
1606 char nnn[10];
1607 };
1608
1609 #define UNITTEST_ITEM (struct aral_unittest_entry){ \
1610 .TXT = "ABCDEFGHIJKLMNOPQRSTUVWXYZ", \
1611 .txt = "abcdefghijklmnopqrstuvwxyz", \
1612 .nnn = "123456789", \
1613 }
1614
1615 static inline struct aral_unittest_entry *unittest_aral_malloc(ARAL *ar, bool marked) {
1616 struct aral_unittest_entry *t;
1617 if(marked)
1618 t = aral_mallocz_marked(ar);
1619 else
1620 t = aral_mallocz(ar);
1621
1622 *t = UNITTEST_ITEM;
1623 return t;
1624 }
1625
1626 #ifdef NETDATA_INTERNAL_CHECKS
1627
1628 struct aral_race_unittest_allocator {
1629 ARAL *ar;
1630 struct aral_unittest_entry *entry;
1631 };
1632 static bool aral_unittest_wait_for_flag(bool *flag, usec_t timeout_ut) {
1633 usec_t started_ut = now_monotonic_usec();
1634
1635 while(!__atomic_load_n(flag, __ATOMIC_ACQUIRE)) {
1636 if(now_monotonic_usec() - started_ut > timeout_ut)
1637 return false;
1638
1639 tinysleep();
1640 }
1641
1642 return true;
1643 }
1644
1645 static void aral_race_unittest_allocator_thread(void *ptr) {
1646 struct aral_race_unittest_allocator *ctx = ptr;
1647 ctx->entry = unittest_aral_malloc(ctx->ar, false);
1648 }
1649
1650 static struct aral_unittest_entry *aral_race_unittest_force_page_full(ARAL *ar, ARAL_PAGE *page) {
1651 struct aral_unittest_entry *entry;
1652 aral_page_lock(ar, page);
1653
1654 internal_fatal(!page->page_lock.free_elements,
1655 "ARAL race unittest: target page unexpectedly has no free elements");
1656
1657 uint64_t slot = __atomic_fetch_add(&page->elements_segmented, 1, __ATOMIC_ACQUIRE);
1658 internal_fatal(slot >= page->max_elements,
1659 "ARAL race unittest: failed to reserve the last free slot");
1660
1661 entry = (struct aral_unittest_entry *)(page->data + (slot * ar->config.element_size));
1662 aral_set_page_pointer_after_element___do_NOT_have_aral_lock(ar, page, entry, false);
1663 *entry = UNITTEST_ITEM;
1664 aral_element_given(ar, page);
1665
1666 page->page_lock.used_elements++;
1667 page->page_lock.free_elements--;
1668
1669 REFCOUNT rf = __atomic_add_fetch(&page->refcount, 1, __ATOMIC_RELAXED);
1670 internal_fatal(rf < (REFCOUNT)page->max_elements || rf > (REFCOUNT)page->max_elements + 1,
1671 "ARAL race unittest: invalid forced refcount %d for max_elements %u",
1672 rf, page->max_elements);
1673
1674 aral_lock(ar);
1675 if(page->aral_lock.head_ptr == aral_pages_head_free(ar, false)) {
1676 DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(*page->aral_lock.head_ptr, page, aral_lock.prev, aral_lock.next);
1677
1678 ARAL_PAGE **head_ptr_full = aral_pages_head_full(ar, false);
1679 DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(*head_ptr_full, page, aral_lock.prev, aral_lock.next);
1680 page->aral_lock.head_ptr = head_ptr_full;
1681 }
1682 aral_unlock(ar);
1683
1684 aral_race_unittest_hook.forced_entry = entry;
1685 __atomic_store_n(&aral_race_unittest_hook.page_force_fully_used, true, __ATOMIC_RELEASE);
1686
1687 aral_page_unlock(ar, page);
1688 return entry;
1689 }
1690
1691 static int aral_detect_acquire_to_page_lock_race(void) {
1692 int errors = 0;
1693 bool allocator_entry_marked = false;
1694 ARAL_PAGE *allocator_page = NULL;
1695 ARAL *ar = aral_create("aral-race-test",
1696 sizeof(struct aral_unittest_entry),
1697 0,
1698 0,
1699 NULL,
1700 "aral-race-test",
1701 NULL, false, false, false);
1702
1703 size_t page_elements = aral_elements_in_page_size(ar, ar->ops[0].adders.allocation_size);
1704 struct aral_unittest_entry **filled = callocz(page_elements, sizeof(*filled));
1705 struct aral_race_unittest_allocator allocator = {
1706 .ar = ar,
1707 .entry = NULL,
1708 };
1709
1710 for(size_t i = 0; i < page_elements - 1; i++)
1711 filled[i] = unittest_aral_malloc(ar, false);
1712
1713 aral_race_unittest_hook = (struct aral_race_unittest_hook) {
1714 .ar = ar,
1715 .enabled = true,
1716 };
1717
1718 ND_THREAD *thread = nd_thread_create("ARALRACE", NETDATA_THREAD_OPTION_DONT_LOG,
1719 aral_race_unittest_allocator_thread, &allocator);
1720
1721 if(!thread) {
1722 fprintf(stderr, "ARAL race unittest: failed to create allocator thread.\n");
1723 errors++;
1724 }
1725
1726 if(thread && !aral_unittest_wait_for_flag(&aral_race_unittest_hook.first_allocator_waiting, 5 * USEC_PER_SEC)) {
1727 fprintf(stderr, "ARAL race unittest: timed out waiting for the first allocator to pause.\n");
1728 errors++;
1729 }
1730 else if(thread) {
1731 if(!aral_race_unittest_hook.page) {
1732 fprintf(stderr, "ARAL race unittest: paused allocator did not publish its target page.\n");
1733 errors++;
1734 }
1735 else
1736 aral_race_unittest_force_page_full(ar, aral_race_unittest_hook.page);
1737 }
1738
1739 __atomic_store_n(&aral_race_unittest_hook.release_first_allocator, true, __ATOMIC_RELEASE);
1740 if(thread)
1741 nd_thread_join(thread);
1742 __atomic_store_n(&aral_race_unittest_hook.enabled, false, __ATOMIC_RELEASE);
1743
1744 if(!allocator.entry) {
1745 fprintf(stderr, "ARAL race unittest: paused allocator failed to complete its allocation.\n");
1746 errors++;
1747 }
1748 else
1749 allocator_page = aral_get_page_pointer_after_element___do_NOT_have_aral_lock(ar, allocator.entry, &allocator_entry_marked);
1750
1751 (void)allocator_entry_marked;
1752
1753 if(ar->aral_lock.pages_full == NULL) {
1754 fprintf(stderr, "ARAL race unittest: expected the original page to become full during the race.\n");
1755 errors++;
1756 }
1757
1758 if(!__atomic_load_n(&aral_race_unittest_hook.page_force_fully_used, __ATOMIC_ACQUIRE)) {
1759 fprintf(stderr, "ARAL race unittest: failed to force the page into the fully-used state.\n");
1760 errors++;
1761 }
1762
1763 if(errors == 0 && allocator_page == aral_race_unittest_hook.page) {
1764 fprintf(stderr, "ARAL race unittest: allocator retried on the forced-full page instead of a new page.\n");
1765 errors++;
1766 }
1767
1768 if(aral_race_unittest_hook.forced_entry)
1769 aral_freez(ar, aral_race_unittest_hook.forced_entry);
1770
1771 if(allocator.entry)
1772 aral_freez(ar, allocator.entry);
1773
1774 for(size_t i = 0; i < page_elements - 1; i++) {
1775 if(filled[i])
1776 aral_freez(ar, filled[i]);
1777 }
1778
1779 freez(filled);
1780 aral_destroy(ar);
1781 aral_race_unittest_hook = (struct aral_race_unittest_hook) { 0 };
1782
1783 return errors;
1784 }
1785
1786 // --------------------------------------------------------------------------------------------------------------------
1787 // Concurrency tests for the unmark / freez state machine.
1788 //
1789 // Each scenario uses the aral_concurrency_race_hook to deterministically pause
1790 // one operation at a known point so a second operation can race it. Tests 4-6
1791 // drive both sides through the trailer transition concurrently and verify
1792 // that page counters end consistent and no assertion fires; tests 1-3 are
1793 // bug-independent sanity checks for the unmark / freez API contract.
1794
1795 struct aral_concurrency_test_args {
1796 ARAL *ar;
1797 void *ptr;
1798 };
1799
1800 static void aral_concurrency_test_unmark_thread(void *arg) {
1801 struct aral_concurrency_test_args *a = arg;
1802 aral_unmark_allocation(a->ar, a->ptr);
1803 }
1804
1805 static void aral_concurrency_test_freez_thread(void *arg) {
1806 struct aral_concurrency_test_args *a = arg;
1807 aral_freez(a->ar, a->ptr);
1808 }
1809
1810 static ARAL_PAGE *aral_concurrency_test_decode(ARAL *ar, void *ptr, bool *marked) {
1811 uint8_t *data = ptr;
1812 uintptr_t *page_ptr = (uintptr_t *)&data[ar->config.element_ptr_offset];
1813 uintptr_t tagged = __atomic_load_n(page_ptr, __ATOMIC_ACQUIRE);
1814 return aral_decode_page_pointer_after_element___do_NOT_have_aral_lock(ar, ptr, tagged, marked);
1815 }
1816
1817 // Common setup for tests that need a marked guard and a marked test entry on
1818 // the same page. Captures used/marked counters at setup time so each test can
1819 // verify the expected delta after its scenario runs.
1820 struct aral_concurrency_test_fixture {
1821 ARAL *ar;
1822 struct aral_unittest_entry *guard;
1823 struct aral_unittest_entry *entry;
1824 ARAL_PAGE *page;
1825 uint32_t used0;
1826 uint32_t marked0;
1827 };
1828
1829 // Initialize the fixture. Returns true on success. On failure (guard/entry
1830 // landed on different pages), the aral and allocations are torn down and
1831 // false is returned; the caller should bubble up an error.
1832 static bool aral_concurrency_test_fixture_init(struct aral_concurrency_test_fixture *f, const char *name) {
1833 f->ar = aral_create(name, sizeof(struct aral_unittest_entry),
1834 0, 0, NULL, name, NULL, false, false, false);
1835
1836 // Guard is allocated marked so it lives on the same (marked) page as the
1837 // test entry. Marked and unmarked allocations use separate page lists.
1838 f->guard = aral_mallocz_marked(f->ar);
1839 *f->guard = UNITTEST_ITEM;
1840
1841 f->entry = aral_mallocz_marked(f->ar);
1842 *f->entry = UNITTEST_ITEM;
1843
1844 bool m = false;
1845 f->page = aral_concurrency_test_decode(f->ar, f->entry, &m);
1846 bool gm = false;
1847 ARAL_PAGE *guard_page = aral_concurrency_test_decode(f->ar, f->guard, &gm);
1848 if(guard_page != f->page) {
1849 fprintf(stderr, " setup: guard and entry are not on the same page (guard=%p entry=%p)\n",
1850 (void*)guard_page, (void*)f->page);
1851 aral_freez(f->ar, f->entry);
1852 aral_freez(f->ar, f->guard);
1853 aral_destroy(f->ar);
1854 return false;
1855 }
1856 f->used0 = f->page->page_lock.used_elements;
1857 f->marked0 = f->page->page_lock.marked_elements;
1858 return true;
1859 }
1860
1861 // Teardown when the test entry was already freed by the scenario.
1862 // Frees the guard, destroys the aral, resets the concurrency hook.
1863 static void aral_concurrency_test_fixture_teardown(struct aral_concurrency_test_fixture *f) {
1864 aral_freez(f->ar, f->guard);
1865 aral_destroy(f->ar);
1866 aral_concurrency_race_hook_reset();
1867 }
1868
1869 // Teardown when the test entry is still allocated (e.g. failure path before
1870 // the scenario could free it). Frees both entry and guard.
1871 static void aral_concurrency_test_fixture_teardown_with_entry(struct aral_concurrency_test_fixture *f) {
1872 aral_freez(f->ar, f->entry);
1873 aral_freez(f->ar, f->guard);
1874 aral_destroy(f->ar);
1875 aral_concurrency_race_hook_reset();
1876 }
1877
1878 // Verify the page counters reflect exactly one freez of the test entry:
1879 // used and marked each decremented by 1. Returns the error count to add.
1880 static int aral_concurrency_test_check_counters_after_one_freez(struct aral_concurrency_test_fixture *f) {
1881 int errors = 0;
1882 if(f->page->page_lock.used_elements != f->used0 - 1) {
1883 fprintf(stderr, " used_elements: %u -> %u (expected %u)\n",
1884 f->used0, f->page->page_lock.used_elements, f->used0 - 1);
1885 errors++;
1886 }
1887 if(f->page->page_lock.marked_elements != f->marked0 - 1) {
1888 fprintf(stderr, " marked_elements: %u -> %u (expected %u)\n",
1889 f->marked0, f->page->page_lock.marked_elements, f->marked0 - 1);
1890 errors++;
1891 }
1892 return errors;
1893 }
1894
1895 // Test 1: clean unmark on a marked allocation. No concurrency.
1896 // Expects: marked counter -1, used counter unchanged, slot trailer becomes UNMARKED.
1897 static int aral_concurrency_test_clean_unmark(void) {
1898 int errors = 0;
1899 fprintf(stderr, " test 1: clean unmark on a marked allocation\n");
1900
1901 ARAL *ar = aral_create("aral-conc-1", sizeof(struct aral_unittest_entry),
1902 0, 0, NULL, "aral-conc-1", NULL, false, false, false);
1903
1904 struct aral_unittest_entry *entry = aral_mallocz_marked(ar);
1905 *entry = UNITTEST_ITEM;
1906
1907 bool m = false;
1908 ARAL_PAGE *page = aral_concurrency_test_decode(ar, entry, &m);
1909 if(!m) { fprintf(stderr, " setup: not marked\n"); errors++; }
1910 uint32_t used0 = page->page_lock.used_elements;
1911 uint32_t marked0 = page->page_lock.marked_elements;
1912
1913 aral_unmark_allocation(ar, entry);
1914
1915 bool m_after = true;
1916 ARAL_PAGE *p_after = aral_concurrency_test_decode(ar, entry, &m_after);
1917 if(p_after != page || m_after) {
1918 fprintf(stderr, " trailer state wrong after unmark (page=%p marked=%d)\n", (void*)p_after, (int)m_after);
1919 errors++;
1920 }
1921 if(page->page_lock.used_elements != used0) {
1922 fprintf(stderr, " used_elements changed (%u -> %u)\n", used0, page->page_lock.used_elements);
1923 errors++;
1924 }
1925 if(page->page_lock.marked_elements != marked0 - 1) {
1926 fprintf(stderr, " marked_elements: %u -> %u (expected %u)\n",
1927 marked0, page->page_lock.marked_elements, marked0 - 1);
1928 errors++;
1929 }
1930
1931 aral_freez(ar, entry);
1932 aral_destroy(ar);
1933 return errors;
1934 }
1935
1936 // Test 2: unmark on an already-unmarked allocation. Should bail without changing counters.
1937 static int aral_concurrency_test_unmark_on_unmarked(void) {
1938 int errors = 0;
1939 fprintf(stderr, " test 2: unmark on an already-unmarked allocation (should bail)\n");
1940
1941 ARAL *ar = aral_create("aral-conc-2", sizeof(struct aral_unittest_entry),
1942 0, 0, NULL, "aral-conc-2", NULL, false, false, false);
1943
1944 // allocate UNMARKED (regular mallocz)
1945 struct aral_unittest_entry *entry = aral_mallocz(ar);
1946 *entry = UNITTEST_ITEM;
1947
1948 bool m = true;
1949 ARAL_PAGE *page = aral_concurrency_test_decode(ar, entry, &m);
1950 if(m) { fprintf(stderr, " setup: unexpectedly marked\n"); errors++; }
1951 uint32_t used0 = page->page_lock.used_elements;
1952 uint32_t marked0 = page->page_lock.marked_elements;
1953
1954 aral_unmark_allocation(ar, entry);
1955
1956 if(page->page_lock.used_elements != used0 || page->page_lock.marked_elements != marked0) {
1957 fprintf(stderr, " counters changed after no-op unmark (used %u->%u, marked %u->%u)\n",
1958 used0, page->page_lock.used_elements, marked0, page->page_lock.marked_elements);
1959 errors++;
1960 }
1961
1962 aral_freez(ar, entry);
1963 aral_destroy(ar);
1964 return errors;
1965 }
1966
1967 // Test 3: clean freez on a marked allocation. No concurrency.
1968 // Expects: used -1, marked -1, slot returns to free pool.
1969 //
1970 // A marked guard is kept alive on the same page so the page is not destroyed
1971 // (or otherwise has its counters reset) by freezing the only allocation.
1972 static int aral_concurrency_test_clean_freez_marked(void) {
1973 int errors = 0;
1974 fprintf(stderr, " test 3: clean freez of a marked allocation\n");
1975
1976 struct aral_concurrency_test_fixture f;
1977 if(!aral_concurrency_test_fixture_init(&f, "aral-conc-3"))
1978 return 1;
1979
1980 aral_freez(f.ar, f.entry);
1981
1982 errors += aral_concurrency_test_check_counters_after_one_freez(&f);
1983
1984 aral_concurrency_test_fixture_teardown(&f);
1985 return errors;
1986 }
1987
1988 // Test 4: race - freez wins claim before unmark gets to its CAS.
1989 // Pause unmark at entry, run freez to completion, release unmark.
1990 // On master (no fix): unmark loads trailer=0, decode produces page=NULL,
1991 // triggers "possible corruption or double free" internal_fatal under
1992 // NETDATA_INTERNAL_CHECKS, OR aral_set_page_pointer with NULL page,
1993 // then aral_page_lock(NULL) SEGV.
1994 // On v2: unmark loads 0, the (initial & TAG_MASK) != MARKED check bails
1995 // without touching counters or pointers.
1996 // Either outcome is captured: master crashes, v2 passes counter checks.
1997 //
1998 // A guard allocation is kept alive on the same page so the page is never
1999 // destroyed mid-test (refcount stays > 0), making it safe to read page
2000 // counters after the racing freez completes.
2001 static int aral_concurrency_test_freez_wins(void) {
2002 int errors = 0;
2003 fprintf(stderr, " test 4: race - freez wins claim before unmark CAS\n");
2004
2005 struct aral_concurrency_test_fixture f;
2006 if(!aral_concurrency_test_fixture_init(&f, "aral-conc-4"))
2007 return 1;
2008
2009 aral_concurrency_race_hook_arm(f.ar, f.entry, ARAL_CONCURRENCY_RACE_UNMARK_BEFORE_CAS);
2010
2011 struct aral_concurrency_test_args ctx = { f.ar, f.entry };
2012 ND_THREAD *unmark_thread = nd_thread_create("UNMARK", NETDATA_THREAD_OPTION_DONT_LOG,
2013 aral_concurrency_test_unmark_thread, &ctx);
2014 if(!unmark_thread) {
2015 fprintf(stderr, " failed to create unmark thread\n");
2016 aral_concurrency_test_fixture_teardown_with_entry(&f);
2017 return errors + 1;
2018 }
2019
2020 if(!aral_unittest_wait_for_flag(&aral_concurrency_race_hook.waiting, 5 * USEC_PER_SEC)) {
2021 fprintf(stderr, " unmark thread did not pause\n");
2022 errors++;
2023 }
2024
2025 // The hook is armed for an UNMARK_* stage, so the freez we are about to
2026 // run will not match (its only pause point is FREEZ_BEFORE_CLAIM). Just
2027 // freez and let unmark resume on the release flag below.
2028 aral_freez(f.ar, f.entry);
2029
2030 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2031 nd_thread_join(unmark_thread);
2032
2033 if(f.page->page_lock.used_elements != f.used0 - 1) {
2034 fprintf(stderr, " used_elements: %u -> %u (expected %u)\n",
2035 f.used0, f.page->page_lock.used_elements, f.used0 - 1);
2036 errors++;
2037 }
2038 if(f.page->page_lock.marked_elements != f.marked0 - 1) {
2039 fprintf(stderr, " marked_elements: %u -> %u (expected %u; %u would mean unmark double-decremented)\n",
2040 f.marked0, f.page->page_lock.marked_elements, f.marked0 - 1, f.marked0 - 2);
2041 errors++;
2042 }
2043
2044 aral_concurrency_test_fixture_teardown(&f);
2045 return errors;
2046 }
2047
2048 // Tests 5 and 6: race - unmark wins the trailer transition, then freez runs.
2049 // Pause unmark AFTER its trailer transition (UNMARKING on v2, UNMARKED on
2050 // master) but BEFORE the page-lock counter update. Run freez concurrently:
2051 // on v2 it should observe UNMARKING, restore, and spin until unmark publishes
2052 // the final state; on master it observes UNMARKED, captures marked=false,
2053 // then races on page_lock with unmark.
2054 //
2055 // Master under NETDATA_INTERNAL_CHECKS: if freez wins page_lock first, the
2056 // "marked > used" assertion at aral_freez_internal fires (or the deletion
2057 // path's "page has marked elements but not used ones" fires). This is the
2058 // exact race the v2 protocol closes.
2059 //
2060 // v2: counters end consistent: used -1, marked -1.
2061 //
2062 // Test 5 sleeps 10ms before releasing unmark to let freez settle into its
2063 // cold-path spin; test 6 releases immediately to also catch regressions in
2064 // the very first iteration of the cold path.
2065 static int aral_concurrency_test_unmark_wins_impl(const char *aral_name, usec_t grace_us) {
2066 int errors = 0;
2067
2068 struct aral_concurrency_test_fixture f;
2069 if(!aral_concurrency_test_fixture_init(&f, aral_name))
2070 return 1;
2071
2072 aral_concurrency_race_hook_arm(f.ar, f.entry, ARAL_CONCURRENCY_RACE_UNMARK_AFTER_CAS);
2073
2074 struct aral_concurrency_test_args ctx = { f.ar, f.entry };
2075 ND_THREAD *unmark_thread = nd_thread_create("UNMARK", NETDATA_THREAD_OPTION_DONT_LOG,
2076 aral_concurrency_test_unmark_thread, &ctx);
2077 if(!unmark_thread) {
2078 fprintf(stderr, " failed to create unmark thread\n");
2079 aral_concurrency_test_fixture_teardown_with_entry(&f);
2080 return errors + 1;
2081 }
2082
2083 if(!aral_unittest_wait_for_flag(&aral_concurrency_race_hook.waiting, 5 * USEC_PER_SEC)) {
2084 fprintf(stderr, " unmark thread did not pause after trailer transition\n");
2085 errors++;
2086 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2087 nd_thread_join(unmark_thread);
2088 aral_concurrency_test_fixture_teardown_with_entry(&f);
2089 return errors;
2090 }
2091
2092 // Hook is armed for UNMARK_AFTER_CAS - freez's FREEZ_BEFORE_CLAIM pause
2093 // point will not match, so the freez thread proceeds without pausing.
2094 ND_THREAD *freez_thread = nd_thread_create("FREEZ", NETDATA_THREAD_OPTION_DONT_LOG,
2095 aral_concurrency_test_freez_thread, &ctx);
2096 if(!freez_thread) {
2097 fprintf(stderr, " failed to create freez thread\n");
2098 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2099 nd_thread_join(unmark_thread);
2100 // unmark completed - it transitioned the slot to UNMARKED but did not
2101 // free it. We must free entry too.
2102 aral_concurrency_test_fixture_teardown_with_entry(&f);
2103 return errors + 1;
2104 }
2105
2106 if(grace_us > 0)
2107 sleep_usec(grace_us);
2108
2109 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2110 nd_thread_join(unmark_thread);
2111 nd_thread_join(freez_thread);
2112
2113 errors += aral_concurrency_test_check_counters_after_one_freez(&f);
2114
2115 aral_concurrency_test_fixture_teardown(&f);
2116 return errors;
2117 }
2118
2119 static int aral_concurrency_test_unmark_wins_transition(void) {
2120 fprintf(stderr, " test 5: race - unmark transitions trailer, freez races counter update\n");
2121 return aral_concurrency_test_unmark_wins_impl("aral-conc-5", 10 * USEC_PER_MS);
2122 }
2123
2124 static int aral_concurrency_test_unmark_wins_no_grace(void) {
2125 fprintf(stderr, " test 6: race - same as test 5, no grace period before release\n");
2126 return aral_concurrency_test_unmark_wins_impl("aral-conc-6", 0);
2127 }
2128
2129 // Test 7: unmark of the last marked element on a page triggers a list move
2130 // from the marked-pages list to the unmarked-pages list. This is the
2131 // "if(unmark)" branch of aral_unmark_allocation that takes aral_lock and
2132 // moves the page between linked lists.
2133 static int aral_concurrency_test_unmark_last_marked_on_page(void) {
2134 int errors = 0;
2135 fprintf(stderr, " test 7: unmark of last marked element triggers list move\n");
2136
2137 ARAL *ar = aral_create("aral-conc-7", sizeof(struct aral_unittest_entry),
2138 0, 0, NULL, "aral-conc-7", NULL, false, false, false);
2139
2140 // Single marked allocation. After unmarking, marked_elements drops to 0
2141 // while used_elements stays at 1 (unmarking does not free the slot), which
2142 // triggers the unmark branch in aral_unmark_allocation that takes
2143 // aral_lock and moves the page from the marked-pages list to the
2144 // unmarked-pages list.
2145 struct aral_unittest_entry *m1 = aral_mallocz_marked(ar);
2146 *m1 = UNITTEST_ITEM;
2147
2148 bool m = false;
2149 ARAL_PAGE *marked_page = aral_concurrency_test_decode(ar, m1, &m);
2150 if(!m) { fprintf(stderr, " setup: not marked\n"); errors++; }
2151 if(!marked_page->aral_lock.marked) {
2152 fprintf(stderr, " setup: page not on marked list before unmark\n");
2153 errors++;
2154 }
2155
2156 aral_unmark_allocation(ar, m1);
2157
2158 if(marked_page->page_lock.marked_elements != 0) {
2159 fprintf(stderr, " marked_elements not 0 after unmark of last marked: %u\n",
2160 marked_page->page_lock.marked_elements);
2161 errors++;
2162 }
2163 if(marked_page->aral_lock.marked) {
2164 fprintf(stderr, " page still on marked list after unmarking last marked\n");
2165 errors++;
2166 }
2167
2168 aral_freez(ar, m1);
2169 aral_destroy(ar);
2170 return errors;
2171 }
2172
2173 // Test 8: coordinated per-pointer race stress.
2174 // For every pointer in the pool, deterministically force the racing window:
2175 // 1. Arm the hook to pause unmark at the UNMARKING transition.
2176 // 2. Spawn an unmark thread - it CAS's to UNMARKING and pauses at the hook.
2177 // 3. Spawn a freez thread on the same pointer - it observes UNMARKING and
2178 // enters the cold path (restore + retry) of the claim helper.
2179 // 4. Release unmark - it finishes its counter update and publishes UNMARKED.
2180 // 5. Freez's retry exchange picks up UNMARKED, claims, decrements only used.
2181 // 6. Both threads complete; the slot is fully freed.
2182 //
2183 // This exercises every interesting transition for every pointer:
2184 // - unmark wins the trailer transition
2185 // - freez observes UNMARKING (cold path of the claim helper)
2186 // - the published UNMARKED value lets freez proceed
2187 // Plus, because the pool spans multiple pages, the freezes near the end of
2188 // each page exercise the "last marked element triggers list move" branch and
2189 // the page deletion path.
2190 //
2191 // Final state is verified via aral_used_bytes(): must be 0 after every slot
2192 // is freed.
2193 static int aral_concurrency_test_stress(void) {
2194 int errors = 0;
2195 const size_t pool_size = 256; // large enough to span multiple pages
2196 fprintf(stderr, " test 8: coordinated race stress - %zu pointers, deterministic UNMARKING for each\n", pool_size);
2197
2198 ARAL *ar = aral_create("aral-conc-stress", sizeof(struct aral_unittest_entry),
2199 0, 0, NULL, "aral-conc-stress", NULL, false, false, false);
2200
2201 struct aral_unittest_entry **pool = callocz(pool_size, sizeof(*pool));
2202 for(size_t i = 0; i < pool_size; i++) {
2203 pool[i] = aral_mallocz_marked(ar);
2204 *pool[i] = UNITTEST_ITEM;
2205 }
2206
2207 size_t cold_path_hits = 0;
2208 size_t i;
2209 for(i = 0; i < pool_size; i++) {
2210 // Arm the hook to pause unmark just after its CAS to UNMARKING.
2211 aral_concurrency_race_hook_arm(ar, pool[i], ARAL_CONCURRENCY_RACE_UNMARK_AFTER_CAS);
2212
2213 struct aral_concurrency_test_args ctx = { ar, pool[i] };
2214
2215 ND_THREAD *unmark_thread = nd_thread_create("UNMARK", NETDATA_THREAD_OPTION_DONT_LOG,
2216 aral_concurrency_test_unmark_thread, &ctx);
2217 if(!unmark_thread) {
2218 fprintf(stderr, " iter %zu: failed to create unmark thread\n", i);
2219 errors++;
2220 break;
2221 }
2222
2223 if(!aral_unittest_wait_for_flag(&aral_concurrency_race_hook.waiting, 5 * USEC_PER_SEC)) {
2224 fprintf(stderr, " iter %zu: unmark did not reach pause\n", i);
2225 errors++;
2226 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2227 nd_thread_join(unmark_thread);
2228 break;
2229 }
2230
2231 // Hook is armed for UNMARK_AFTER_CAS - freez's FREEZ_BEFORE_CLAIM
2232 // pause point will not match, so the freez we are about to spawn
2233 // proceeds without pausing.
2234
2235 // Snapshot the UNMARKING-cold-path counter before spawning freez.
2236 size_t cold_before = __atomic_load_n(&aral_freez_unmarking_observed_count, __ATOMIC_ACQUIRE);
2237
2238 ND_THREAD *freez_thread = nd_thread_create("FREEZ", NETDATA_THREAD_OPTION_DONT_LOG,
2239 aral_concurrency_test_freez_thread, &ctx);
2240 if(!freez_thread) {
2241 fprintf(stderr, " iter %zu: failed to create freez thread\n", i);
2242 errors++;
2243 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2244 nd_thread_join(unmark_thread);
2245 break;
2246 }
2247
2248 // Wait until freez actually enters the UNMARKING cold path, i.e. its
2249 // exchange returned a value with the UNMARKING bit set. Without this
2250 // synchronization the test could release unmark before freez has
2251 // even reached the exchange, never exercising the cold path we are
2252 // here to validate.
2253 usec_t deadline = now_monotonic_usec() + 5 * USEC_PER_SEC;
2254 while(__atomic_load_n(&aral_freez_unmarking_observed_count, __ATOMIC_ACQUIRE) == cold_before) {
2255 if(now_monotonic_usec() > deadline) {
2256 fprintf(stderr, " iter %zu: freez did not observe UNMARKING within timeout\n", i);
2257 errors++;
2258 break;
2259 }
2260 tinysleep();
2261 }
2262 if(__atomic_load_n(&aral_freez_unmarking_observed_count, __ATOMIC_ACQUIRE) > cold_before)
2263 cold_path_hits++;
2264
2265 // Now release unmark; freez (still spinning in its cold path) will
2266 // observe the published UNMARKED and proceed.
2267 __atomic_store_n(&aral_concurrency_race_hook.release, true, __ATOMIC_RELEASE);
2268
2269 nd_thread_join(unmark_thread);
2270 nd_thread_join(freez_thread);
2271
2272 // Reset the hook for the next iteration.
2273 aral_concurrency_race_hook_reset();
2274 }
2275
2276 // Defensive reset: any early break above could have left the hook armed.
2277 aral_concurrency_race_hook_reset();
2278
2279 // Free pool entries that were not freed by a successful loop iteration.
2280 // On normal completion i == pool_size and this loop is empty. On early
2281 // break, pool[i] may be in any allocated state (MARKED or UNMARKED) but
2282 // is always still allocated; aral_freez handles both.
2283 for(size_t j = i; j < pool_size; j++)
2284 aral_freez(ar, pool[j]);
2285
2286 if(cold_path_hits != pool_size) {
2287 fprintf(stderr, " cold path was exercised %zu/%zu times (expected all)\n",
2288 cold_path_hits, pool_size);
2289 errors++;
2290 }
2291
2292 if(aral_used_bytes(ar) != 0) {
2293 fprintf(stderr, " aral has %zu used bytes after stress test (expected 0)\n",
2294 aral_used_bytes(ar));
2295 errors++;
2296 }
2297
2298 freez(pool);
2299 aral_destroy(ar);
2300 return errors;
2301 }
2302
2303 int aral_unittest_concurrency(void) {
2304 #if defined(FSANITIZE_ADDRESS)
2305 // Under address sanitizer ARAL is bypassed entirely: mallocz/callocz/
2306 // freez delegate straight to glibc and aral_unmark_allocation() is a
2307 // no-op. There is no trailer protocol to test, so skip cleanly.
2308 fprintf(stderr, "ARAL concurrency tests: SKIPPED (ARAL is disabled under FSANITIZE_ADDRESS)\n");
2309 return 0;
2310 #else
2311 fprintf(stderr, "Running ARAL concurrency tests (unmark/freez state machine)...\n");
2312 int errors = 0;
2313 errors += aral_concurrency_test_clean_unmark();
2314 errors += aral_concurrency_test_unmark_on_unmarked();
2315 errors += aral_concurrency_test_clean_freez_marked();
2316 errors += aral_concurrency_test_freez_wins();
2317 errors += aral_concurrency_test_unmark_wins_transition();
2318 errors += aral_concurrency_test_unmark_wins_no_grace();
2319 errors += aral_concurrency_test_unmark_last_marked_on_page();
2320 errors += aral_concurrency_test_stress();
2321 fprintf(stderr, "ARAL concurrency tests: %s (%d errors)\n",
2322 errors ? "FAILED" : "PASSED", errors);
2323 return errors;
2324 #endif
2325 }
2326
2327 #endif
2328
2329 static void aral_test_thread(void *ptr) {
2330 struct aral_unittest_config *auc = ptr;
2331 ARAL *ar = auc->ar;
2332 size_t elements = auc->elements;
2333
2334 bool marked = os_random(2);
2335 struct aral_unittest_entry **pointers = callocz(elements, sizeof(struct aral_unittest_entry *));
2336
2337 size_t iterations = 0;
2338 do {
2339 iterations++;
2340
2341 for (size_t i = 0; i < elements; i++) {
2342 pointers[i] = unittest_aral_malloc(ar, marked);
2343 }
2344
2345 if(marked) {
2346 for (size_t i = 0; i < elements; i++) {
2347 aral_unmark_allocation(ar, pointers[i]);
2348 }
2349 }
2350
2351 for (size_t div = 5; div >= 2; div--) {
2352 for (size_t i = 0; i < elements / div; i++) {
2353 aral_freez(ar, pointers[i]);
2354 pointers[i] = NULL;
2355 }
2356
2357 for (size_t i = 0; i < elements / div; i++) {
2358 pointers[i] = unittest_aral_malloc(ar, marked);
2359 }
2360 }
2361
2362 for (size_t step = 50; step >= 10; step -= 10) {
2363 for (size_t i = 0; i < elements; i += step) {
2364 aral_freez(ar, pointers[i]);
2365 pointers[i] = NULL;
2366 }
2367
2368 for (size_t i = 0; i < elements; i += step) {
2369 pointers[i] = unittest_aral_malloc(ar, marked);
2370 }
2371 }
2372
2373 for (size_t i = 0; i < elements; i++) {
2374 aral_freez(ar, pointers[i]);
2375 pointers[i] = NULL;
2376 }
2377
2378 if (auc->single_threaded && ar->aral_lock.pages_free && ar->aral_lock.pages_free->page_lock.used_elements) {
2379 fprintf(stderr, "\n\nARAL leftovers detected (1)\n\n");
2380 __atomic_add_fetch(&auc->errors, 1, __ATOMIC_RELAXED);
2381 }
2382
2383 if(!auc->single_threaded && __atomic_load_n(&auc->stop, __ATOMIC_RELAXED))
2384 break;
2385
2386 for (size_t i = 0; i < elements; i++) {
2387 pointers[i] = unittest_aral_malloc(ar, marked);
2388 }
2389
2390 size_t max_page_elements = aral_elements_in_page_size(ar, aral_max_allocation_size(ar));
2391 size_t increment = elements / max_page_elements;
2392 for (size_t all = increment; all <= elements / 2; all += increment) {
2393
2394 size_t to_free = (all % max_page_elements) + 1;
2395 size_t step = elements / to_free;
2396 if(!step) step = 1;
2397
2398 // fprintf(stderr, "all %zu, to free %zu, step %zu\n", all, to_free, step);
2399
2400 size_t *free_list = mallocz(to_free * sizeof(*free_list));
2401 for (size_t i = 0; i < to_free; i++) {
2402 size_t pos = step * i;
2403 aral_freez(ar, pointers[pos]);
2404 pointers[pos] = NULL;
2405 free_list[i] = pos;
2406 }
2407
2408 for (size_t i = 0; i < to_free; i++) {
2409 size_t pos = free_list[i];
2410 pointers[pos] = unittest_aral_malloc(ar, marked);
2411 }
2412
2413 freez(free_list);
2414 }
2415
2416 for (size_t i = 0; i < elements; i++) {
2417 aral_freez(ar, pointers[i]);
2418 pointers[i] = NULL;
2419 }
2420
2421 if (auc->single_threaded && ar->aral_lock.pages_free && ar->aral_lock.pages_free->page_lock.used_elements) {
2422 fprintf(stderr, "\n\nARAL leftovers detected (2)\n\n");
2423 __atomic_add_fetch(&auc->errors, 1, __ATOMIC_RELAXED);
2424 }
2425
2426 } while(!auc->single_threaded && !__atomic_load_n(&auc->stop, __ATOMIC_RELAXED));
2427
2428 freez(pointers);
2429 }
2430
2431 int aral_stress_test(size_t threads, size_t elements, size_t seconds) {
2432 fprintf(stderr, "Running stress test of %zu threads, with %zu elements each, for %zu seconds...\n",
2433 threads, elements, seconds);
2434
2435 struct aral_unittest_config auc = {
2436 .single_threaded = false,
2437 .threads = threads,
2438 .ar = aral_create("aral-stress-test",
2439 sizeof(struct aral_unittest_entry),
2440 0,
2441 16384,
2442 NULL,
2443 "aral-stress-test",
2444 NULL, false, false, false),
2445 .elements = elements,
2446 .errors = 0,
2447 };
2448
2449 usec_t started_ut = now_monotonic_usec();
2450 ND_THREAD **thread_ptrs = callocz(threads, sizeof(*thread_ptrs));
2451
2452 for(size_t i = 0; i < threads ; i++) {
2453 char tag[ND_THREAD_TAG_MAX + 1];
2454 snprintfz(tag, ND_THREAD_TAG_MAX, "TH[%zu]", i);
2455 thread_ptrs[i] = nd_thread_create(tag, NETDATA_THREAD_OPTION_DONT_LOG, aral_test_thread, &auc);
2456 }
2457
2458 size_t malloc_done = 0;
2459 size_t free_done = 0;
2460 size_t countdown = seconds;
2461 while(countdown-- > 0) {
2462 sleep_usec(1 * USEC_PER_SEC);
2463 size_t m = __atomic_load_n(&auc.ar->atomic.user_malloc_operations, __ATOMIC_RELAXED);
2464 size_t f = __atomic_load_n(&auc.ar->atomic.user_free_operations, __ATOMIC_RELAXED);
2465 fprintf(stderr, "ARAL executes %0.2f M malloc and %0.2f M free operations/s\n",
2466 (double)(m - malloc_done) / 1000000.0, (double)(f - free_done) / 1000000.0);
2467 malloc_done = m;
2468 free_done = f;
2469 }
2470
2471 __atomic_store_n(&auc.stop, true, __ATOMIC_RELAXED);
2472
2473 // fprintf(stderr, "Cancelling the threads...\n");
2474 // for(size_t i = 0; i < threads ; i++) {
2475 // nd_thread_signal_cancel(thread_ptrs[i]);
2476 // }
2477
2478 fprintf(stderr, "Waiting the threads to finish...\n");
2479 for(size_t i = 0; i < threads ; i++) {
2480 nd_thread_join(thread_ptrs[i]);
2481 }
2482
2483 freez(thread_ptrs);
2484
2485 usec_t ended_ut = now_monotonic_usec();
2486
2487 if (auc.ar->aral_lock.pages_free && auc.ar->aral_lock.pages_free->page_lock.used_elements) {
2488 fprintf(stderr, "\n\nARAL leftovers detected (3)\n\n");
2489 __atomic_add_fetch(&auc.errors, 1, __ATOMIC_RELAXED);
2490 }
2491
2492 fprintf(stderr, "ARAL: did %zu malloc, %zu free, using %zu threads, in %"PRIu64" usecs\n",
2493 __atomic_load_n(&auc.ar->atomic.user_malloc_operations, __ATOMIC_RELAXED),
2494 __atomic_load_n(&auc.ar->atomic.user_free_operations, __ATOMIC_RELAXED),
2495 threads,
2496 ended_ut - started_ut);
2497
2498 aral_destroy(auc.ar);
2499
2500 return auc.errors;
2501 }
2502
2503 int aral_unittest(size_t elements) {
2504 const char *cache_dir = "/tmp/";
2505 #ifdef NETDATA_INTERNAL_CHECKS
2506 int errors = aral_detect_acquire_to_page_lock_race();
2507
2508 if(errors) {
2509 fprintf(stderr, "ARAL unittest: FAILED (%d errors)\n", errors);
2510 return errors;
2511 }
2512 #else
2513 int errors = 0;
2514 #endif
2515
2516 struct aral_unittest_config auc = {
2517 .single_threaded = true,
2518 .threads = 1,
2519 .ar = aral_create("aral-test",
2520 sizeof(struct aral_unittest_entry),
2521 0,
2522 65536,
2523 NULL,
2524 "aral-test",
2525 &cache_dir,
2526 false, false, false),
2527 .elements = elements,
2528 .errors = 0,
2529 };
2530
2531 aral_test_thread(&auc);
2532
2533 aral_destroy(auc.ar);
2534
2535 errors += aral_stress_test(2, elements, 10);
2536
2537 int total_errors = auc.errors + errors;
2538 fprintf(stderr, "ARAL unittest: %s (%d errors)\n", total_errors ? "FAILED" : "PASSED", total_errors);
2539
2540 return total_errors;
2541 }