Line data Source code
1 : #ifndef HEADER_fd_src_util_alloc_fd_alloc_h
2 : #define HEADER_fd_src_util_alloc_fd_alloc_h
3 :
4 : /* fd_alloc is a high performance lockfree fast O(1) (typically)
5 : allocator.
6 :
7 : It is optimized for high concurrency use and small-ish clustered /
8 : multi-modal distributed allocation sizes. It is further optimized
9 : for single-threaded use cases and/or when malloc-free pairs have have
10 : good thread affinity (i.e. frees done by the same thread that did the
11 : corresponding malloc). It can also be used optimally in more complex
12 : threading use cases (e.g. malloc in one or more producer threads,
13 : free in one or more consumer threads). It behaves well with
14 : irregular sizes and exploits ultra fine grained alignment for good
15 : packing (e.g. reasonable low memory overhead packing of byte strings
16 : with irregular small-ish sizes).
17 :
18 : A fd_alloc stores its state in a wksp in a persistent way and backs
19 : its allocations by that same wksp. This avoids many of the severe
20 : performance and reliability issues of malloc
21 :
22 : Critically, it _doesn't_ _lie_ and it _doesn't_ _blow_ _up_.
23 :
24 : fd_alloc_malloc will not stall your program behind your back, calling
25 : the OS to grow or shrink the program's memory footprint during the
26 : call; it will never use more memory than has already be procured for
27 : the underlying wksp. And, if fd_alloc_malloc succeeds, the returned
28 : memory is real and is ready for use.
29 :
30 : Obligatory dynamic allocation rant *********************************
31 :
32 : That is, fd_alloc is not the absolute unforgivable garbage of
33 : Linux/libc malloc. malloc often just reserves page table entries and
34 : returns, irrespective of whether or not the request can be satisfied
35 : (on the apparent belief that the malloc call was a bluff and the user
36 : is probably a bad dev who doesn't bother with error trapping anyway),
37 : in hopes that that a later glacially slow page fault to the OS will
38 : actually reserve the memory.
39 :
40 : Which, even when it does work, it will by its very nature will be at
41 : the worst possible times (e.g. in the middle of incoming line rate
42 : network traffic bursts ... data structures try to grow to accommodate
43 : but slowing down throughput faster than they are growing at a time
44 : when keeping up is critical to surviving ... and then on a
45 : ridiculously awful normal page by normal page basis), exposing the
46 : caller to non-deterministic performance and reduced throughput.
47 :
48 : Unfortunately, getting overrun by DoS-like traffic patterns is the
49 : least of the worries. When Linux can't back one of the page by DRAM
50 : on a page fault (skipping over some additional TLB and NUMA
51 : dubiousness that goes on under the hood), it goes from glacial
52 : performance to continental drift levels of performance. It will try
53 : to honor the request by shuffling things to swap, exacerbating the
54 : above. Suddenly it is a feat to even keep up with a 1980s modem.
55 :
56 : But that's not the end of the horror. Because Linux thinks it cool
57 : to overcommit beyond physical limits for no discernible reason and
58 : gets flaky if you try to disable swap and/or overcommit, the page
59 : fault might not be able honor the commitment. Finding itself caught
60 : in a lie (it can't go back in time and rescind the success that
61 : malloc already returned to the unsuspecting developer), the Linux
62 : kernel goes full HAL-9000 and starts randomly killing things. A dead
63 : process can't complain about malloc lying to it after all. And,
64 : cherry on top, the victims of the oom killer are frequently not even
65 : the culprits.
66 :
67 : Sigh ... all completely unacceptable behaviors in any situation, much
68 : less mission critical ones.
69 :
70 : TL;DR Friends don't let friends malloc.
71 :
72 : If you truly need malloc-free semantics, use fd_alloc. This at least
73 : eliminates the most egregious horrors above. It can't help the
74 : intrinsic horrors though.
75 :
76 : (Though it is ingrained in CS teaching and languages to the extent
77 : there's rarely even recognition of the faintest possibility of the
78 : existence of alternatives, people rarely truly need malloc/free
79 : semantics. But, after they convince themselves they still do because
80 : of the brainwashing, they need to remind themselves that computers
81 : don't work remotely like malloc/free suggest and then should try to
82 : think about resource acquisition more fundamentally. And, after they
83 : still manage to talk themselves back into needing it because of the
84 : teaching and linguistic traps, repeat ... at least if they want to
85 : make something fast and robust. Even if they can prove dynamic
86 : allocation requests have an attainable worst level at all points in
87 : time, they still have to prove that heap fragmentation over time will
88 : never cause malloc to fail. Good luck with that.)
89 :
90 : The above rant applies to any paired dynamic memory strategies,
91 : including non-placement new, implicit copy constructors, dynamic
92 : resizing containers, etc. Real world computers aren't just funky
93 : implementations of infinite tape Turing machines. This make-believe
94 : that they are in code that interacts with the real world is a recipe
95 : for real world disaster.
96 :
97 : End of obligatory dynamic allocation rant **************************
98 :
99 : Since it is backed by a wksp, allocations have the same NUMA, TLB,
100 : IPC and persistence properties of the underlying wksp. This allows
101 : fd_alloc to go far beyond the capabilities of a typical allocator
102 : Allocations done by fd_alloc can be shared between processes (can
103 : even malloc in one process, translate the pointer into the address
104 : space of another process, and free it there, even after the first
105 : process has terminated), a process can be stopped and then other
106 : processes can still find the stopped process's allocations and use
107 : them / free them / etc.
108 :
109 : Regarding time efficiency and concurrency, large allocations are
110 : passed through to the underlying wksp allocator (which is neither
111 : O(1) and only "quasi"-lockfree in the sense described in fd_wksp.h).
112 : But the allocation strategies used under the hood (loosely inspired
113 : by Hoard-style lockfree allocators but with a lot of optimizations
114 : and tweaks for the above) are such that, in the common case of not
115 : needing to fall back to the underlying wksp allocator, the allocator
116 : is lockfree O(1).
117 :
118 : Regarding spatial efficiency, it is reasonably space efficient
119 : (overhead for a cstr-style allocation is ~4 bytes) and adapts over
120 : time to try to bound the amount of pre-allocation for small requests. */
121 :
122 : #include "../wksp/fd_wksp.h"
123 : #include "../sanitize/fd_asan.h"
124 :
125 : /* FD_ALLOC_{ALIGN,FOOTPRINT} give the required alignment and footprint
126 : needed for a wksp allocation to be suitable as a fd_alloc. ALIGN is
127 : an integer power of 2 and FOOTPRINT is an integer multiple of
128 : ALIGN. These are provided to facilitate compile time declarations. */
129 :
130 : #define FD_ALLOC_ALIGN (128UL)
131 3 : #define FD_ALLOC_FOOTPRINT sizeof(fd_alloc_t)
132 :
133 : /* FD_ALLOC_MALLOC_ALIGN_DEFAULT gives the alignment that will be used
134 : when the user does not specify an alignment. This will be an integer
135 : power of 2 of at least 16 for C/C++ allocator alignment conformance.
136 : (16 instead of 8 on the grounds that 128-bit is a primitive type on
137 : platforms with FD_HAS_INT128.) */
138 :
139 700683 : #define FD_ALLOC_MALLOC_ALIGN_DEFAULT (16UL)
140 :
141 : /* FD_ALLOC_JOIN_CGROUP_HINT_MAX is maximum value for a cgroup hint.
142 : This is an integer power of 2 minus 1 of at most FD_ALLOC_ALIGN. */
143 :
144 2188185 : #define FD_ALLOC_JOIN_CGROUP_HINT_MAX (15UL)
145 :
146 : /* A fd_alloc_t is a quasi-opaque handle of a fd_alloc (sizeof and
147 : alignof work but the internals should not be used directly). */
148 :
149 : struct fd_alloc_private;
150 : typedef struct fd_alloc_private fd_alloc_t;
151 :
152 : /* fd_alloc private API ***********************************************/
153 :
154 : /* FD_ALLOC_MAGIC is an ideally unique number that specifies the precise
155 : memory layout of a fd_alloc */
156 :
157 156 : #define FD_ALLOC_MAGIC (0xF17EDA2C37A110C2UL) /* FIRE DANCER ALLOC version 2 */
158 :
159 : /* FD_ALLOC_SIZECLASS_MAX is the maximum number of sizeclasses supported
160 : by fd_alloc. */
161 :
162 835488 : #define FD_ALLOC_SIZECLASS_MAX (240UL)
163 :
164 : struct __attribute__((aligned(FD_ALLOC_ALIGN))) fd_alloc_private {
165 :
166 : ulong magic; /* ==FD_ALLOC_MAGIC */
167 : ulong wksp_off; /* Offset of the first byte of this structure from the start of the wksp */
168 : ulong tag; /* tag that will be used by this allocator. Positive. */
169 :
170 : uchar _[ FD_ALLOC_ALIGN - 3UL*sizeof(ulong) ]; /* Padding to FD_ALLOC_ALIGN */
171 :
172 : /* active_slot[ sizeclass + FD_ALLOC_SIZECLASS_MAX*cgroup ] is the
173 : global address of the superblock in circulation that is preferred
174 : for sizeclass allocations done by a caller in concurrency group
175 : cgroup. 0 if there is no active superblock currently for
176 : (sizeclass,cgroup). Note that this is stored compactly but
177 : organized such that concurrent operations from different cgroups
178 : are unlikely to create false sharing. */
179 :
180 : ulong active_slot[ FD_ALLOC_SIZECLASS_MAX*(FD_ALLOC_JOIN_CGROUP_HINT_MAX+1UL) ];
181 :
182 : /* inactive_stack[ sizeclass ] gives the top of stack of inactive
183 : superblocks in circulation stack for sizeclass or 0 if the stack is
184 : empty. This is versioned global address with a 17-bit version
185 : number in the least significant bits and a 50-bit gaddr encoded in
186 : 47-bits in the most significant bits (the 3 least significant bits
187 : of a superblock gaddr are zero given FD_ALLOC_SUPERBLOCK_ALIGN is
188 : at least 8). This means that fd_alloc can be backed by wksp up to
189 : ~1 PiB in size. */
190 :
191 : ulong inactive_stack[ FD_ALLOC_SIZECLASS_MAX ];
192 :
193 : /* Padding to FD_ALLOC_ALIGN here */
194 :
195 : };
196 :
197 : FD_PROTOTYPES_BEGIN
198 :
199 : /* fd_alloc_private_join_alloc returns the local address of the alloc
200 : for a join. */
201 :
202 : FD_FN_CONST static inline fd_alloc_t *
203 1468656 : fd_alloc_private_join_alloc( fd_alloc_t * join ) {
204 1468656 : return (fd_alloc_t *)(((ulong)join) & ~FD_ALLOC_JOIN_CGROUP_HINT_MAX);
205 1468656 : }
206 :
207 : /* fd_alloc_private_wksp returns the wksp backing alloc. Assumes alloc
208 : is a non-NULL pointer in the caller's address space to the fd_alloc
209 : (not a join handle). */
210 :
211 : FD_FN_PURE static inline fd_wksp_t *
212 823005 : fd_alloc_private_wksp( fd_alloc_t * alloc ) {
213 823005 : return (fd_wksp_t *)(((ulong)alloc) - alloc->wksp_off);
214 823005 : }
215 :
216 : /* fd_alloc_private_delete allows fine grained control over how much
217 : cleanup of the underlying wksp is done.
218 :
219 : - level<=0 indicates to do no wksp cleanup (the user can manually
220 : cleanup left over allocations and so forth with APIs like
221 : fd_wksp_tag_free).
222 :
223 : - level==1 indicates to do a quick cleanup (assuming the application
224 : freed all allocations done by this allocator, all wksp usage
225 : _except_ the shalloc itself will be freed). fd_alloc_delete is a
226 : thin wrapper to this with level==1.
227 :
228 : - level>1 indicates to do a deep cleanup. This will free all wksp
229 : locations that match fd_alloc's wksp tag. IMPORTANT SAFETY TIP!
230 : If shalloc was allocated with the same tag, this will also free
231 : shalloc too! IMPORTANT SAFETY TIP! If any other wksp allocations
232 : used this tag, this will also free all those allocations too! */
233 :
234 : void *
235 : fd_alloc_private_delete( void * shalloc,
236 : int level );
237 :
238 : FD_PROTOTYPES_END
239 :
240 : /* End of private API *************************************************/
241 :
242 : FD_PROTOTYPES_BEGIN
243 :
244 : /* fd_alloc_{align,footprint} return FD_ALLOC_{ALIGN,FOOTPRINT}. */
245 :
246 : FD_FN_CONST ulong
247 : fd_alloc_align( void );
248 :
249 : FD_FN_CONST ulong
250 : fd_alloc_footprint( void );
251 :
252 : /* fd_alloc_new formats an unused wksp allocation with the appropriate
253 : alignment and footprint as a fd_alloc. Caller is not joined on
254 : return. Returns shmem on success and NULL on failure (shmem NULL,
255 : shmem misaligned, shmem is not backed by a wksp ... logs details). A
256 : workspace can have multiple fd_alloc created for it. They will
257 : dynamically share the underlying workspace along with any other
258 : non-fd_alloc usage but will otherwise act as completely separate
259 : non-conflicting arenas (useful for logical grouping and improved
260 : concurrency). To help with various diagnostics, garbage collection
261 : and what not, all allocations to the underlying wksp are tagged with
262 : the given tag, positive. Ideally, the tag used here should be
263 : distinct from all other tags used by this workspace. */
264 :
265 : void *
266 : fd_alloc_new( void * shmem,
267 : ulong tag );
268 :
269 : /* fd_alloc_join joins the caller to a fd_alloc. shalloc points to the
270 : first byte of the memory region backing the alloc in the caller's
271 : address space. Returns an opaque handle of the join on success
272 : (IMPORTANT! THIS IS NOT JUST A CAST OF SHALLOC) and NULL on failure
273 : (NULL shalloc, misaligned shalloc, bad magic, ... logs details).
274 : Every successful join should have a matching leave. The lifetime of
275 : the join is until the matching leave or the thread group is
276 : terminated (joins are local to a thread group).
277 :
278 : cgroup_hint is a concurrency hint used to optimize parallel and
279 : persistent use cases. Ideally each thread (regardless of thread
280 : group) should join the allocator with a different cgroup_hint system
281 : wide (note that joins are practically free). And if using a fd_alloc
282 : in a persistent way, logical streams of execution would ideally
283 : preserve the cgroup_hint address starts and stops of that stream for
284 : the most optimal affinity behaviors. 0 is fine in single threaded
285 : use cases and 0 and/or collisions are fine in more general cases
286 : though concurrent performance might be reduced due to additional
287 : contention between threads that share the same cgroup_hint. If
288 : cgroup_hint is not in [0,FD_ALLOC_JOIN_CGROUP_HINT_MAX], it will be
289 : wrapped to be in that range.
290 :
291 : TL;DR A cgroup_hint of 0 is often a practical choice single threaded.
292 : A cgroup_hint of fd_tile_idx() or just uniform random 64-bit value
293 : choice in more general situations. */
294 :
295 : fd_alloc_t *
296 : fd_alloc_join( void * shalloc,
297 : ulong cgroup_hint );
298 :
299 : /* fd_alloc_leave leaves an existing join. Returns the underlying
300 : shalloc (IMPORTANT! THIS IS NOT A SIMPLE CAST OF JOIN) on success and
301 : NULL on failure. Reasons for failure include join is NULL (logs
302 : details). */
303 :
304 : void *
305 : fd_alloc_leave( fd_alloc_t * join );
306 :
307 : /* fd_alloc_delete unformats a wksp allocation used as a fd_alloc.
308 : Assumes nobody is or will be joined to the fd_alloc. The caller
309 : further promises there are no allocations outstanding. If there are
310 : still some outstanding allocations, it will try to clean up as many
311 : as it can find but it is not guaranteed to find all of them (those
312 : will continue to consume wksp space but could be theoretically be
313 : cleaned up in an application specific way by operating directly on
314 : the underlying workspace ... of course, if the application could do
315 : that, it probably such just clean up after itself before calling
316 : delete). Returns shmem on success and NULL on failure (logs
317 : details). Reasons for failure include shalloc is NULL, misaligned
318 : fd_alloc, bad magic, etc. */
319 :
320 : void *
321 : fd_alloc_delete( void * shalloc );
322 :
323 : /* fd_alloc_join_cgroup_hint returns the cgroup_hint of the current
324 : join. Assumes join is a current local join. The return will be in
325 : [0,FD_ALLOC_JOIN_CGROUP_HINT_MAX].
326 :
327 : fd_alloc_join_cgroup_hint_set returns join with the cgroup_hint
328 : updated to provided cgroup_hint. If cgroup hint is not in
329 : [0,FD_ALLOC_JOIN_CGROUP_HINT_MAX], it will be wrapped into this
330 : range. Assumes join is a current local join. The return value is
331 : not a new join. */
332 :
333 : FD_FN_CONST static inline ulong
334 718185 : fd_alloc_join_cgroup_hint( fd_alloc_t * join ) {
335 718185 : return ((ulong)join) & FD_ALLOC_JOIN_CGROUP_HINT_MAX;
336 718185 : }
337 :
338 : FD_FN_CONST static inline fd_alloc_t *
339 : fd_alloc_join_cgroup_hint_set( fd_alloc_t * join,
340 672 : ulong cgroup_hint ) {
341 672 : return (fd_alloc_t *)((((ulong)join) & (~FD_ALLOC_JOIN_CGROUP_HINT_MAX)) | (cgroup_hint & FD_ALLOC_JOIN_CGROUP_HINT_MAX));
342 672 : }
343 :
344 : /* fd_alloc_wksp returns a pointer to a local wksp join of the wksp
345 : backing the fd_alloc with the current local join. Caller should not
346 : call fd_alloc_leave on the returned value. Lifetime of the returned
347 : wksp handle is as long as the shalloc used on the fd_alloc_join is
348 : still mapped into the caller's address space.
349 :
350 : fd_alloc_tag returns the tag that will be used for allocations from
351 : this workspace. */
352 :
353 : FD_FN_PURE static inline fd_wksp_t * // NULL indicates NULL join
354 42 : fd_alloc_wksp( fd_alloc_t * join ) {
355 42 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
356 42 : return FD_LIKELY( alloc ) ? fd_alloc_private_wksp( alloc ) : NULL;
357 42 : }
358 :
359 : FD_FN_PURE static inline ulong // Positive, 0 indicates NULL join
360 15 : fd_alloc_tag( fd_alloc_t * join ) {
361 15 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
362 15 : return FD_LIKELY( alloc ) ? alloc->tag : 0UL;
363 15 : }
364 :
365 : /* fd_alloc_malloc_at_least allocates at least sz bytes with alignment
366 : of at least align from the wksp backing the fd_alloc. join is a
367 : current local join to the fd_alloc. align should be an integer power
368 : of 2 or 0.
369 :
370 : An align of 0 indicates to use FD_ALLOC_MALLOC_DEFAULT_ALIGN for the
371 : request alignment. This will be large enough such that
372 : fd_alloc_malloc is conformant with C/C++ alignment specifications
373 : (i.e. can trivially wrap fd_alloc_malloc to use as a drop in
374 : replacement for malloc).
375 :
376 : Small values of align will NOT be rounded up to some minimum (e.g.
377 : allocating lots of 1 byte aligned short strings is fine and
378 : relatively space and time efficient ... the overhead is ~4 bytes per
379 : allocation). fd_alloc is not particularly optimized when align>~sz
380 : and/or large alignments (>~4096B). While large values for align are
381 : supported by fd_alloc_malloc, directly using fd_wksp_alloc is
382 : recommended in such cases.
383 :
384 : If an allocation is "large" (align + sz >~ 64KiB for the current
385 : implementation), it will be handled by fd_wksp_alloc under the hood.
386 : Otherwise, it will be handled by fd_alloc_malloc algorithms (which
387 : are ultimately backed by fd_wksp_alloc). As such, if a small
388 : allocation is "new" (e.g. first allocation of a size around sz, an
389 : allocation that can't be packed near other existing allocations
390 : around that sz, etc), this might also fallback on fd_wksp_alloc.
391 : Typically though, after initial allocation and/or program warmup,
392 : fd_alloc_malloc calls will be a reasonably fast O(1) lockfree.
393 :
394 : Returns a pointer to the allocation in the local address space on
395 : success. Note that this pointer will a wksp laddr. As such, it can
396 : be converted to a gaddr, passed to other threads in other thread
397 : groups, and converted to a wksp laddr in their address spaces, freed
398 : via a join to the fd_alloc in that thread group, persisted beyond the
399 : lifetime of the calling thread, etc.
400 :
401 : Returns NULL on failure (silent to support HPC usage) or when sz is
402 : 0. Reasons for failure include NULL join, invalid align, sz overflow
403 : (sz+align>~2^64), no memory available for request (e.g. workspace has
404 : insufficient room or is too fragmented).
405 :
406 : On return, *max will contain the number actual number of bytes
407 : available at the returned gaddr. On success, this will be at least
408 : sz and it is not guaranteed to be a multiple of align. On failure,
409 : *max will be zero.
410 :
411 : fd_alloc_malloc is a simple wrapper around fd_alloc_malloc_at_least
412 : for use when applications do not care about the actual size of their
413 : allocation. */
414 :
415 : void *
416 : fd_alloc_malloc_at_least( fd_alloc_t * join,
417 : ulong align,
418 : ulong sz,
419 : ulong * max );
420 :
421 : static inline void *
422 : fd_alloc_malloc( fd_alloc_t * join,
423 : ulong align,
424 263058 : ulong sz ) {
425 263058 : ulong max[1];
426 263058 : void * laddr = fd_alloc_malloc_at_least( join, align, sz, max );
427 :
428 : #if FD_HAS_DEEPASAN
429 : if( FD_LIKELY( laddr ) ) fd_asan_poison( (uchar *)laddr + sz, (*max) - sz );
430 : #endif
431 :
432 263058 : return laddr;
433 263058 : }
434 :
435 : /* FIXME: consider a fd_alloc_avail API that returns the max bytes avail
436 : at an allocation? */
437 :
438 : /* fd_alloc_free frees the outstanding allocation whose first byte is
439 : pointed to by laddr in the caller's local address space. join is a
440 : current local join to the fd_alloc. The caller promises laddr was
441 : allocated by the underlying fd_alloc (but not necessarily on the
442 : calling thread or even in this calling process or even by a thread /
443 : process that is still running). Silent for HPC usage (NULL join and
444 : NULL laddr are a no-op).
445 :
446 : Like fd_alloc_malloc, if the allocation was large, this will be
447 : handled by fd_wksp_free under the hood, which is neither lockfree nor
448 : O(1). If the allocation was small, this will typically be lockfree
449 : O(1). It is possible that, if the amount of outstanding small
450 : allocations has reduced significantly, fd_alloc_free on a small
451 : allocation might trigger a fd_wksp_free to free up wksp space for
452 : other usage (including uses not through this fd_alloc).
453 :
454 : (It would be possible to implement this less efficiently in space and
455 : time such that join didn't need to be passed. The current design has
456 : picked efficiency and consistency with other APIs though.)
457 :
458 : Note that this will implicitly optimize the freed memory to be
459 : preferentially reused by the join's concurrency group. Thus the
460 : caller should have at least one join for each concurrency group to
461 : which it might want to return memory for reuse and then call free
462 : with the appropriate join. */
463 :
464 : void
465 : fd_alloc_free( fd_alloc_t * join,
466 : void * laddr );
467 :
468 : /* fd_alloc_compact frees all wksp allocations that are not required
469 : for any outstanding user mallocs (note that fd_alloc_free lazily
470 : returns unused memory from the underlying wksp to accelerate
471 : potential future allocations). join is a current local join to the
472 : alloc. This cannot fail from a user's POV but logs any wonkiness
473 : detected.
474 :
475 : fd_alloc_compact has the property that it minimizes the amount of
476 : wksp utilization for the set of outstanding user mallocs when there
477 : is no other concurrent alloc usage. As such, if there is no
478 : concurrent alloc usage _and_ there are no outstanding mallocs, on
479 : return, all wksp allocations (except the user provided memory region
480 : that holds the state of the allocator) will be returned to the wksp.
481 : This can be then be used to reset the alloc and/or implement robust
482 : leak detection at program teardown.
483 :
484 : This function is safe to use even when there is other concurrent
485 : alloc usage. It t is best effort in that case; it is not guaranteed
486 : that there was some point in time between call and return when the
487 : wksp utilization was minimized for the contemporaneous set of
488 : outstanding user mallocs.
489 :
490 : Also note that this function is not O(1) and the fd_alloc_free lazy
491 : return mechanism does not permit unbounded growth of unreturned free
492 : memory. So this should be used sparingly at best (e.g. in teardown
493 : leak detection or rare non-critical path housekeeping). */
494 :
495 : void
496 : fd_alloc_compact( fd_alloc_t * join );
497 :
498 : /* fd_alloc_is_empty returns 1 if the alloc has no outstanding mallocs
499 : and 0 otherwise. join is a current local join to the alloc. NULL
500 : join silently returns 0.
501 :
502 : Important safety tip! This should only be run when there is no
503 : concurrent alloc usage. It is not algorithmically fast. This might
504 : temporarily lock the underlying wksp while running and might call
505 : fd_alloc_compact under the hood. It assumes the user provided memory
506 : region holding the alloc state is contained within a region returned
507 : by a single fd_wksp_alloc call (it would be hard to create an alloc
508 : where that isn't the case). It assumes alloc is the only user of the
509 : alloc's tag in the wksp. As such this should be used carefully and
510 : sparingly (e.g. at program teardown for leak detection).
511 :
512 : It will "work" with concurrent alloc usage in that the return value
513 : will be in 0 or 1 and it will not corrupt the alloc or underlying
514 : wksp. But the return value will not be well-defined (e.g. it is not
515 : guaranteed to correspond the state of the alloc at some point in time
516 : between when this was called and it when it returned). */
517 :
518 : int
519 : fd_alloc_is_empty( fd_alloc_t * join );
520 :
521 : /* fd_alloc_max_expand computes a recommended value to use for max when
522 : needing to dynamically resize structures. The below is very subtle
523 : and fixes a lot of pervasive errors with dynamic resizing
524 : implementations (either explicit or implicitly done under the hood).
525 : It doesn't fix the main error with dynamic resizing though. The main
526 : error being deciding to use anything with dynamic resizing (outside
527 : of, maybe, initialization at program start).
528 :
529 : Consider an all too common case of an initially too small dynamically
530 : sized array that is getting elements appended to it one at a time.
531 : E.g. without proper error trapping, overflow handling and the like:
532 :
533 : foo_t * foo = NULL;
534 : ulong foo_max = 0UL;
535 : ulong foo_cnt = 0UL;
536 : ulong foo_delta = ... some reasonable increment ...;
537 :
538 : while( ... still appending ... ) {
539 :
540 : if( foo_cnt==foo_max ) { // Need to resize
541 : foo_max += foo_delta;
542 : foo = (foo_t *)realloc( foo, foo_max*sizeof(foo_t) );
543 : }
544 :
545 : foo[ foo_cnt++ ] = ... next val to append ...;
546 : }
547 :
548 : This is terrible theoretically and practically and yet it looks like
549 : it does everything right.
550 :
551 : The theoretical issue is that, if the realloc can't be done in-place
552 : (which is more common than most realize ... depends on how the
553 : underlying realloc implementation details), the memory will have to
554 : be copied from the original location to the resized location with a
555 : typical cost of final_foo_max/2 -> O(final_foo_cnt). Because max is
556 : increased by fixed absolute amount each resizing, there will be
557 : final_foo_cnt/foo_delta -> O(final_foo_cnt) such resizes.
558 :
559 : That is, we've accidentally written a method that has a slow
560 : O(final_foo_cnt^2) worst case even though it superficially looks like
561 : a fast O(final_foo_cnt) method. Worse still, this behavior might
562 : appear suddenly in previously fine code if realloc implementation
563 : changes or, yet again worse, because a larger problem size was used
564 : in the wild than used in testing.
565 :
566 : The practical issue is realloc is painfully slow and it gets worse
567 : for large sizes because large sizes are usually handled by operating
568 : system calls (e.g. mmap or sbrk under the hood). We've also now done
569 : O(final_foo_cnt) slow operating system calls in our already
570 : algorithmically slow O(final_foo_cnt^2) worst case algorithm that
571 : still superficially looks like a fast O(final_foo_cnt). (And throw
572 : in the other issues with malloc described above about TLB and NUMA
573 : inefficiency, the gaslighting the kernel does "clearly the crash had
574 : nothing to do with the OOM killer shooting processes randomly in the
575 : head, your program probably just had a bug ... yeah ... that's the
576 : ticket" ... for good measure).
577 :
578 : We can get an algorithmic improvement if we change the above to
579 : increase max by a fixed relative amount each resize. Since we are
580 : dealing with integers though, we should make sure that we always
581 : increase max by some minimal amount. Instead of:
582 :
583 : foo_max += foo_delta;
584 :
585 : we can use something like:
586 :
587 : foo_max = fd_ulong_max( foo_max*gamma, foo_max + foo_delta );
588 :
589 : If gamma>1, asymptotically, we will only do O(lg cnt) resizes.
590 : Theoretically, we've gone from an O(final_foo_cnt^2) worst case
591 : method to an O(final_foo_cnt lg final_foo_cnt) worst case method. It
592 : is still irritating that it looks superficially like a fast
593 : O(final_foo_cnt) method but this is amongst the many reasons why
594 : dynamic resizing is gross and wrong and to be avoided when possible.
595 :
596 : The larger gamma is, the smaller the leading coefficient is in the
597 : O(final_foo_cnt lg final_foo_cnt) and thus the better this
598 : approximates the fast O(final_foo_cnt) method that it superficially
599 : seems to be. But using a very large gamma is clearly absurd. There
600 : are obvious memory footprint limitations for large sizes and each
601 : resize would trigger an ever larger amount of OS work. This raises
602 : the question:
603 :
604 : What is the optimal gamma?
605 :
606 : Suppose we have worst case realloc implementation (alloc new memory,
607 : copy, free old memory and, when no free fragment large enough is
608 : available, use sbrk like semantics to get memory from the O/S ...
609 : not uncommon as it is trivial to implement and often works "good
610 : enough" in lab settings). It always works out-of-place and it always
611 : just appends new memory at the end of the heap when the heap runs out
612 : of space. Then, while doing the above, asymptotically, we expect the
613 : heap to look something like:
614 :
615 : other allocs | M foo_t alloc | padding free | unmapped
616 :
617 : On the next resize, we'd request space for M gamma foo_t. Since
618 : there are no free fragments large enough for this, realloc is going
619 : to have to map some space from the operating system, copy our memory
620 : into it and free up the original space for reuse. Post resize, we
621 : expect the heap to look like:
622 :
623 : other allocs | M foo_t free | M gamma foo_t alloc | padding free | unmapped
624 :
625 : On the next resize, we'd request space for M gamma^2 foo_t. This
626 : also can't fit within any free fragment above for gamma>1 (noting
627 : that, in this worst case realloc, we have to allocate the memory
628 : first and then copy and then free the old). So we end up with:
629 :
630 : other allocs | M (1+gamma) foo_t free | M gamma^2 foo_t alloc | padding free | unmapped
631 :
632 : On the next resize, we'd request space for M gamma^3 foo_t. If we
633 : have:
634 :
635 : gamma^3 < 1 + gamma
636 :
637 : we can fit this request in the hole left by the two previous resizes.
638 : This implies we need gamma<1.32471... where the magic number is the
639 : positive real root of:
640 :
641 : x^3 - x - 1 = 0
642 :
643 : This is the "silver ratio" in the sense that the positive real root
644 : of x^2 - x - 1 is the "golden ratio" of 1.61803... (Note that the
645 : golden ratio would apply if we had a more sophisticated realloc under
646 : the hood that aliased the resized allocation over top the M foo_t
647 : free and the existing M gamma foo_t alloc and then moved the aliased
648 : memory. Presumably such a sophisticated realloc would also just
649 : append to the end of the heap without any move or copy at all but
650 : that eventually leads to a question about how much overallocation and
651 : operating system overhead is acceptable on resize discussed further
652 : below).
653 :
654 : After a resize with something near but smaller than the silver ratio,
655 : we expect the heap to look like:
656 :
657 : other allocs | M gamma^3 foo_t alloc | padding free | unmapped
658 :
659 : which is back to where we started, except with a larger allocation.
660 :
661 : We don't want to be doing floating point math in methods like this.
662 : Noting that gamma = 1 + 1/4 + 1/16 = 1.3125 is very close to the
663 : silver yields the very practical:
664 :
665 : new_max = fd_ulong_max( max + (max>>2) + (max>>4), max + delta );
666 :
667 : This is friendly with even the worst case realloc behaviors under the
668 : hood. It also works will in similar situations with linear storage
669 : media (e.g. disk storage). The limit also means that the worst case
670 : overallocation for cases like the above at most ~32% and on average
671 : ~16%. This is a comparable level of overallocation that already
672 : happens under the hood (e.g. on par with the level of waste that
673 : naturally happens in allocators for metadata and padding and much
674 : less waste than the golden ratio or larger growth rates if we
675 : dubiously trust that the realloc method under the hood).
676 :
677 : In cases where we might need to resize to even larger than this, we
678 : just resize to the caller's requested amount and keep our fingers
679 : crossed that the caller realized by this time dynamic resizing was a
680 : mistake and is allocating the correct size this time.
681 :
682 : Adding arithmetic overflow handling then yields the below.
683 :
684 : TL;DR Example usage (ignoring size calculation overflow handling and
685 : allocation error trapping):
686 :
687 : ulong foo_cnt = 0UL;
688 : ulong foo_max = ... good estimate the actual amount needed;
689 : ulong foo_delta = ... reasonable minimum resizing increment;
690 : foo_t * foo = (foo_t *)malloc( foo_max*sizeof(foo_t) );
691 :
692 : while( ... still appending ... ) {
693 :
694 : if( FD_UNLIKELY( foo_cnt==foo_max ) ) {
695 : foo_max = fd_alloc_max_expand( foo_max, foo_delta, foo_cnt + foo_delta );
696 : foo = (foo_t *)realloc( foo, foo_max*sizeof(foo_t) );
697 : }
698 :
699 : foo[ foo_cnt++ ] = ... next val to append ...;
700 :
701 : }
702 :
703 : ... at this point
704 : ... - foo has foo_cnt elements initialized
705 : ... - foo has room for foo_max elements total
706 : ... - when the initial foo_max estimate was correct or oversized,
707 : ... no resizing was done
708 : ... - when the initial foo_max was undersized, asymptotically,
709 : ... foo_max is at most ~32% larger worst case (~16% larger
710 : ... average case) than foo_cnt with at most O(lg foo_cnt)
711 : ... reallocs needed to initialize foo.
712 : ... - the resizing test branch is highly predictable
713 : ... - the underlying heap shouldn't be too fragmented or
714 : ... overallocated regardless of the allocator implementation
715 : ... details. */
716 :
717 : FD_FN_CONST static inline ulong /* new_max, new_max>=max(needed,max), if max<ULONG_MAX, will be new_max>max */
718 : fd_alloc_max_expand( ulong max,
719 : ulong delta, /* Assumed > 0 */
720 3000000 : ulong needed ) {
721 3000000 : ulong t0 = max + delta; t0 = fd_ulong_if( t0<max, ULONG_MAX, t0 ); /* Handle overflow */
722 : ulong t1 = max + (max>>2) + (max>>4); t1 = fd_ulong_if( t1<max, ULONG_MAX, t1 ); /* Handle overflow */
723 3000000 : return fd_ulong_max( fd_ulong_max( t0, t1 ), needed );
724 3000000 : }
725 :
726 : FD_PROTOTYPES_END
727 :
728 : #endif /* HEADER_fd_src_util_alloc_fd_alloc_h */
|
