aral.c · cryptotaxi247/netdata · siGit Code & Deploy

Code Commits Issues Pulls Sessions CI/CD

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	}