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