Line data Source code
1 : #ifndef HEADER_fd_src_util_wksp_fd_wksp_private_h
2 : #define HEADER_fd_src_util_wksp_fd_wksp_private_h
3 :
4 : #include "fd_wksp.h"
5 :
6 : /* If FD_WKSP_LOCK_RECLAIM==0, do not try to recover the lock from
7 : dead processes. This is useful, for example, if we know that the
8 : lock will not get acquired by another process, or that if another
9 : acquiring process dies that all potential users will get exited. It
10 : prevents a syscall on various common workspace paths (eg, alloc). */
11 :
12 : #ifndef FD_WKSP_LOCK_RECLAIM
13 : #define FD_WKSP_LOCK_RECLAIM 0
14 : #endif
15 :
16 : /* FD_WKSP_PRIVATE_PINFO_IDX_NULL is the pinfo index value used to
17 : indicate NULL */
18 :
19 8854556898 : #define FD_WKSP_PRIVATE_PINFO_IDX_NULL ((ulong)UINT_MAX)
20 :
21 : /* A fd_wksp_private_pinfo_t specifies details about a partition in a
22 : workspace and its relationship to other partitions in that workspace.
23 :
24 : FD_WKSP_PRIVATE_PINFO_ALIGN is an integer power of 2 and
25 : FD_WKSP_PRIVATE_PINFO_FOOTPRINT will be a multiple of align.
26 :
27 : If a partition is not idle:
28 :
29 : - [gaddr_lo,gaddr_hi) specify the range of offsets covered by this
30 : partition.
31 :
32 : wksp_gaddr_lo <= gaddr_lo < gaddr_hi <= wksp_gaddr_hi
33 :
34 : such that partitions always have at least 1 byte and are contained
35 : within the workspace's data region.
36 :
37 : - tag==0 indicates this partition is space in the workspace free
38 : for use and the partition is in the free treap, fast findable by
39 : its size. Otherwise, this partition is allocated and the partition
40 : is in the used treap, fast O(1) findable by any in range gaddr.
41 :
42 : - prev_cidx, next_cidx give the index (in compressed form) of the
43 : previous / next partition if present or IDX_NULL if this is the
44 : workspace partition head / tail partition (in which case gaddr_lo /
45 : gaddr_hi will be wksp->gaddr_lo / wksp->gaddr_hi). That is, for
46 : partition idx where idx is in [0,wksp->part_max):
47 :
48 : ulong prev_idx = fd_wksp_private_pinfo_idx( pinfo[ idx ].prev_cidx );
49 : if( fd_wksp_private_pinfo_idx_is_null( prev_idx ) ) {
50 : ... at this point:
51 : ... idx == fd_wksp_private_pinfo_idx( wksp->part_head_cidx ) );
52 : ... pinfo[ idx ].gaddr_lo == wksp->gaddr_lo );
53 : } else {
54 : ... at this point:
55 : ... idx ==_fd_wksp_private_pinfo_idx( pinfo[ prev_idx ].next_cidx );
56 : ... pinfo[ idx ].gaddr_lo == pinfo[ prev_idx ].gaddr_hi;
57 : }
58 :
59 : and:
60 :
61 : ulong next_idx = fd_wksp_private_pinfo_idx( pinfo[ idx ].next_cidx );
62 : if( fd_wksp_private_pinfo_idx_is_null( next_idx ) ) {
63 : ... at this point:
64 : ... idx == fd_wksp_private_pinfo_idx( wksp->part_tail_cidx ) );
65 : ... pinfo[ idx ].gaddr_hi == wksp->gaddr_hi );
66 : } else {
67 : ... at this point:
68 : ... idx ==_fd_wksp_private_pinfo_idx( pinfo[ next_idx ].prev_cidx );
69 : ... pinfo[ idx ].gaddr_hi == pinfo[ next_idx ].gaddr_lo;
70 : }
71 :
72 : - If partition idx is in the used treap, {left,right}_cidx specify
73 : the partition indices of the root of the left and right subtrees.
74 :
75 : The used treap obeys the binary search tree property that all
76 : partitions in the left/right subtree (if any) cover a range of
77 : offsets strictly lower/higher than range covered by idx.
78 :
79 : parent_cidx specifies idx's parent tree (if any). If idx is the
80 : wksp used tree root, parent_cidx will specify IDX_NULL and
81 : wksp->part_used_cidx will specify idx.
82 :
83 : The used treap also obeys the heap property to make it well
84 : balanced on average. Specifically, the idx's parent's heap
85 : priority will be at least idx's heap priority.
86 :
87 : in_same will be 0 and same_cidx will specify IDX_NULL as no used
88 : partitions can overlap.
89 :
90 : - If partition idx is in the free treap, if partition idx is not
91 : in a list of same sized partitions, in_same will be 0 and
92 : {left,right}_cidx specify the partition indices of the root of the
93 : left and right subtrees.
94 :
95 : The free treap obeys the binary search tree property that all
96 : partitions in the left/right subtree (if any) have partition sizes
97 : strictly lower/higher than partition idx's size.
98 :
99 : parent_cidx specifies idx's parent tree (if any). If idx is the
100 : wksp free tree root, parent_cidx will specify IDX_NULL and
101 : wksp->part_free_cidx will specify idx.
102 :
103 : The free treap also obeys the heap property to make it well
104 : balanced on average. Specifically, the idx's parent's heap
105 : priority will be at least idx's heap priority.
106 :
107 : If there are additional partitions of the same size to partition
108 : idx, same_cidx will refer to the next partition of the same size.
109 :
110 : If partition idx is in a list of same sized partitions, in_same
111 : will be 1 and parent_cidx / same_cidx will specify the prev / next
112 : index of additional partitions of the same size. same_cidx will
113 : specify IDX_NULL if no more.
114 :
115 : - heap_prio is a random value used as described above.
116 :
117 : - stack_cidx and cycle_tag are for internal use */
118 :
119 : /* TODO: Consider align 32/ footprint 96 without compressed indices if
120 : ever needing more than ~4B partitions. */
121 :
122 : #define FD_WKSP_PRIVATE_PINFO_ALIGN (64UL) /* At most FD_WKSP_ALIGN */
123 0 : #define FD_WKSP_PRIVATE_PINFO_FOOTPRINT (64UL)
124 :
125 : struct __attribute__((aligned(FD_WKSP_PRIVATE_PINFO_ALIGN))) fd_wksp_private_pinfo {
126 : ulong gaddr_lo; /* If in idle stack, 0 */
127 : ulong gaddr_hi; /* ", 0 */
128 : ulong tag; /* ", 0 */
129 : uint heap_prio : 31; /* 30 bit priority and 1 bit free to use for infinite priority bulk tree ops */
130 : uint in_same : 1; /* 1 if in a same list and 0 otherwise */
131 : uint prev_cidx; /* ", fd_wksp_private_pinfo_cidx( FD_WKSP_INFO_IDX_NULL ) */
132 : uint next_cidx; /* ", fd_wksp_private_pinfo_cidx( FD_WKSP_INFO_IDX_NULL ) */
133 : uint left_cidx; /* ", fd_wksp_private_pinfo_cidx( FD_WKSP_INFO_IDX_NULL ) */
134 : uint right_cidx; /* ", fd_wksp_private_pinfo_cidx( FD_WKSP_INFO_IDX_NULL ) */
135 : uint parent_cidx; /* ", cidx of next idle or fd_wksp_private_pinfo_cidx( FD_WKSP_INFO_IDX_NULL ) if no more */
136 : uint same_cidx; /* ", fd_wksp_private_pinfo_cidx( FD_WKSP_INFO_IDX_NULL ) */
137 : uint stack_cidx; /* internal use */
138 : ulong cycle_tag; /* internal use */
139 : };
140 :
141 : typedef struct fd_wksp_private_pinfo fd_wksp_private_pinfo_t;
142 :
143 : /* FD_WKSP_MAGIC is an ideally unique number that specifies the precise
144 : memory layout of a fd_wksp. */
145 :
146 255 : #define FD_WKSP_MAGIC (0xF17EDA2C3731C591UL) /* F17E=FIRE,DA2C/3R<>DANCER,31/C59<>WKSP,0<>0 --> FIRE DANCER WKSP VERSION 1 */
147 :
148 : /* fd_wksp_private specifies the detailed layout of the internals of a
149 : fd_wksp_t */
150 :
151 : struct fd_wksp_private {
152 :
153 : /* This point is FD_WKSP_ALIGN aligned */
154 :
155 : /* This fields are static and mostly in the first cache line */
156 :
157 : ulong magic; /* ==FD_WKSP_MAGIC */
158 : ulong part_max; /* Max wksp partitions */
159 : ulong data_max; /* Data region */
160 : ulong gaddr_lo; /* ==fd_wksp_private_data_off( part_max ), data region covers offsets [gaddr_lo,gaddr_hi) */
161 : ulong gaddr_hi; /* ==gaddr_lo + data_max, offset gaddr_hi is to 1 byte footer */
162 : char name[ FD_SHMEM_NAME_MAX ]; /* (Convenience) backing fd_shmem region cstr name */
163 : uint seed; /* Heap priority random number seed, arbitrary */
164 :
165 : /* These fields are dynamic and in the adjacent cache line */
166 :
167 : uint idle_top_cidx; /* Stack of partition infos not in use, parent_idx is next pointer */
168 : uint part_head_cidx; /* Index for info about the leftmost partition */
169 : uint part_tail_cidx; /* Index for info about the rightmost partition */
170 : uint part_used_cidx; /* Treap of partitions that are currently used (tag!=0), searchable by gaddr */
171 : uint part_free_cidx; /* Treap of partitions that are currently free (tag==0), searchable by size */
172 : ulong cycle_tag; /* Used for cycle detection */
173 : ulong owner; /* thread group id of the owner or NULL otherwise */
174 :
175 : /* IMPORTANT! The "single-source-of-truth" for what is currently
176 : used (and its tags) is the set of non-zero tagged partitions in the
177 : partition info array. The idle stack, partition list, used treap
178 : and free treap are auxiliary data structuring that can be
179 : reconstructed at any time from this single source of truth.
180 :
181 : Conversely, if there accidental or deliberate data corruption of
182 : the wksp metadata resulting in a conflict between what is stored
183 : in the partition info array and the auxiliary data structures,
184 : the partition info array governs. */
185 :
186 : /* Padding to FD_WKSP_PRIVATE_PINFO_ALIGN here */
187 :
188 : /* part_max pinfo here */
189 : /* data_max byte data region here */
190 : /* 1 footer byte here */
191 : /* Padding to FD_WKSP_ALIGN here */
192 : };
193 :
194 : FD_PROTOTYPES_BEGIN
195 :
196 : /* fd_wksp_private_pinfo_sz returns the size of a partition in bytes.
197 : Assumes pinfo points to the pinfo of a partition in a current local
198 : join. Will be positive. */
199 :
200 : FD_FN_PURE static inline ulong
201 1414515729 : fd_wksp_private_pinfo_sz( fd_wksp_private_pinfo_t const * pinfo ) {
202 1414515729 : return pinfo->gaddr_hi - pinfo->gaddr_lo;
203 1414515729 : }
204 :
205 : /* fd_wksp_private_{part,data}_off return the wksp offset of the
206 : pinfo array and the data region. data_off assumes part_max is a
207 : value that will not overflow. */
208 :
209 : FD_FN_CONST static inline ulong
210 60397029 : fd_wksp_private_pinfo_off( void ) {
211 60397029 : return 128UL; /* fd_ulong_align_up( sizeof(fd_wksp_t), FD_WKSP_PRIVATE_PINFO_ALIGN ); */
212 60397029 : }
213 :
214 : FD_FN_CONST static inline ulong
215 2625 : fd_wksp_private_data_off( ulong part_max ) {
216 2625 : return fd_wksp_private_pinfo_off() + part_max*sizeof(fd_wksp_private_pinfo_t);
217 2625 : }
218 :
219 : /* fd_wksp_private_pinfo returns the location of wksp pinfo array in the
220 : caller's address space. Assumes wksp is a current local join.
221 : fd_wksp_private_pinfo_const is a const-correct version. */
222 :
223 : FD_FN_CONST static inline fd_wksp_private_pinfo_t *
224 60392280 : fd_wksp_private_pinfo( fd_wksp_t * wksp ) {
225 60392280 : return (fd_wksp_private_pinfo_t *)(((ulong)wksp) + fd_wksp_private_pinfo_off());
226 60392280 : }
227 :
228 : FD_FN_CONST static inline fd_wksp_private_pinfo_t const *
229 0 : fd_wksp_private_pinfo_const( fd_wksp_t const * wksp ) {
230 0 : return (fd_wksp_private_pinfo_t const *)(((ulong)wksp) + fd_wksp_private_pinfo_off());
231 0 : }
232 :
233 : #if FD_HAS_DEEPASAN
234 :
235 : /* fd_wksp_private_asan_poison_data poisons everything after wksp's
236 : pinfo array, i.e. marks every partition free. The wksp header and
237 : pinfo array are left unpoisoned. Assumes wksp is a local join. */
238 :
239 : static inline void
240 : fd_wksp_private_asan_poison_data( fd_wksp_t * wksp ) {
241 : ulong footprint = fd_wksp_footprint( wksp->part_max, wksp->data_max ); /* includes the trailing guard region */
242 : fd_asan_poison( fd_wksp_laddr_fast( wksp, wksp->gaddr_lo ), footprint - wksp->gaddr_lo );
243 : }
244 :
245 : /* fd_wksp_private_asan_sync makes wksp's poison state match its current
246 : partitioning, i.e. all free space poisoned and allocated partitions
247 : not. Assumes wksp is a local join with a rebuilt partitioning. */
248 :
249 : static inline void
250 : fd_wksp_private_asan_sync( fd_wksp_t * wksp ) {
251 : fd_wksp_private_asan_poison_data( wksp );
252 : fd_wksp_private_pinfo_t * pinfo = fd_wksp_private_pinfo( wksp );
253 : for( ulong i=0UL; i<wksp->part_max; i++ ) {
254 : if( !pinfo[ i ].tag ) continue; /* idle or free */
255 : fd_asan_unpoison( fd_wksp_laddr_fast( wksp, pinfo[ i ].gaddr_lo ), pinfo[ i ].gaddr_hi - pinfo[ i ].gaddr_lo );
256 : }
257 : }
258 :
259 : #endif
260 :
261 : /* fd_wksp_private_pinfo_{cidx,idx} compresses / uncompresses a pinfo index */
262 :
263 2365429767 : static inline uint fd_wksp_private_pinfo_cidx( ulong idx ) { return (uint) idx; }
264 5956442322 : static inline ulong fd_wksp_private_pinfo_idx ( uint cidx ) { return (ulong)cidx; }
265 :
266 : /* fd_wksp_private_pinfo_idx_is_null returns 1 if idx is
267 : FD_WKSP_PRIVATE_PINFO_IDX_NULL and 0 otherwise */
268 :
269 7773500883 : static inline int fd_wksp_private_pinfo_idx_is_null( ulong idx ) { return idx==FD_WKSP_PRIVATE_PINFO_IDX_NULL; }
270 :
271 : /* pinfo idle stack APIs **********************************************/
272 :
273 : /* fd_wksp_private_idle_stack_is_empty returns 1 if there are no idle
274 : partitions and 0 otherwise. Also returns 1 if corruption is
275 : detected. Assumes wksp is a current local join. */
276 :
277 : static inline int
278 2001 : fd_wksp_private_idle_stack_is_empty( fd_wksp_t * wksp ) {
279 2001 : return fd_wksp_private_pinfo_idx( wksp->idle_top_cidx ) >= wksp->part_max;
280 2001 : }
281 :
282 : /* fd_wksp_private_idle_stack_pop pops an idle partition off wksp's idle
283 : stack. Assumes the caller knows idle stack is not empty. The caller
284 : is promised that the popped partition has [gaddr_lo,gaddr_hi) = [0,0)
285 : tag 0, {prev, next, left, right, same, parent}_cidx specify IDX_NULL.
286 : Further, heap_prio should have been assigned a random value.
287 : stack_idx and cycle_tag are for internal use. */
288 :
289 : static inline ulong /* Assumes in [0,part_max) */
290 : fd_wksp_private_idle_stack_pop( fd_wksp_t * wksp, /* Assumes current local join */
291 21907344 : fd_wksp_private_pinfo_t * pinfo ) { /* == fd_wksp_private_pinfo( wksp ) */
292 21907344 : ulong i = fd_wksp_private_pinfo_idx( wksp->idle_top_cidx );
293 21907344 : wksp->idle_top_cidx = pinfo[ i ].parent_cidx;
294 21907344 : pinfo[ i ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
295 21907344 : return i;
296 21907344 : }
297 :
298 : /* fd_wksp_private_idle_stack_push pushes partition i onto the idle
299 : stack. Assumes the caller knows i is not currently in the idle
300 : stack, partitioning, used treap or free treap. */
301 :
302 : static inline void
303 : fd_wksp_private_idle_stack_push( ulong i, /* Assumes in [0,part_max) */
304 : fd_wksp_t * wksp, /* Assumes current local join */
305 33950751 : fd_wksp_private_pinfo_t * pinfo ) { /* == fd_wksp_private_pinfo( wksp ) */
306 33950751 : pinfo[ i ].gaddr_lo = 0UL;
307 33950751 : pinfo[ i ].gaddr_hi = 0UL;
308 33950751 : pinfo[ i ].tag = 0U;
309 33950751 : pinfo[ i ].in_same = 0U;
310 33950751 : pinfo[ i ].prev_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
311 33950751 : pinfo[ i ].next_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
312 33950751 : pinfo[ i ].left_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
313 33950751 : pinfo[ i ].right_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
314 33950751 : pinfo[ i ].same_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
315 33950751 : pinfo[ i ].parent_cidx = wksp->idle_top_cidx;
316 33950751 : wksp->idle_top_cidx = fd_wksp_private_pinfo_cidx( i );
317 33950751 : }
318 :
319 : /* pinfo used treap APIs **********************************************/
320 :
321 : /* fd_wksp_private_used_treap_query queries wksp's used treap for the
322 : used partition that holds gaddr. On success, returns the requested
323 : partition idx, in [0,part_max), and, on failure, returns IDX_NULL.
324 : Reasons for failure include gaddr is not in a used partition and
325 : internal treap corruption detected. Might consume a wksp cycle tag
326 : and clobber partition cycle tags. Reasonably fast O(lg N) where N is
327 : the number of used partitions. */
328 :
329 : ulong
330 : fd_wksp_private_used_treap_query( ulong gaddr,
331 : fd_wksp_t * wksp,
332 : fd_wksp_private_pinfo_t * pinfo );
333 :
334 : /* fd_wksp_private_used_treap_insert inserts partition n into wksp's
335 : used treap. Assumes n is not in the idle stack, used treap or free
336 : treap. Does not care if n is in the partitioning or not. Reasonably
337 : fast O(lg N) where N is the number of used partitions.
338 :
339 : Partition n should have [gaddr_lo,gaddr_hi) and heap_prio initialized
340 : on entry (heap_prio should be a random value). tag need not be
341 : initialized but it is assumed that the caller will set the tag to its
342 : final value on success to make the partition officially used. This
343 : will initialize {in_same, left, right, same, parent}_cidx. This will
344 : ignore {prev,next}_cidx. This might consume a wksp cycle tag and
345 : clobber partition stack_cidx and cycle_tag fields.
346 :
347 : Returns FD_WKSP_SUCCESS (zero) on success and a FD_WKSP_ERR_*
348 : (negative) on failure (logs details for failure). Reasons for
349 : failure include n is not in [0,part_max), n's range is not in wksp
350 : data region, n was detected as already inserted (this detection is
351 : not guaranteed), treap internal connectivity issues were detected
352 : (complete detection not guaranteed), and n overlaps with at least one
353 : element already inserted into the treap.
354 :
355 : On failure n and the treap itself were not modified (except possibly
356 : clobbering of stack_cidx and cycle_tag). Note that failure reasons
357 : are either user error or memory corruption. This cannot fail in
358 : normal operating circumstances. */
359 :
360 : int
361 : fd_wksp_private_used_treap_insert( ulong n,
362 : fd_wksp_t * wksp, /* Assumes current local join */
363 : fd_wksp_private_pinfo_t * pinfo ); /* == fd_wksp_private_pinfo( wksp ) */
364 :
365 : /* fd_wksp_private_used_treap_remove removes partition d from wksp's
366 : used treap. Assumes d in the used treap, not in the free treap, not
367 : in the idle stack. Does not care if d is in the partitioning.
368 : Reasonably fast O(lg N) where N is the number of used partitions.
369 : This might consume a wksp cycle tag and clobber partition stack_cidx
370 : and cycle_tag fields.
371 :
372 : Returns FD_WKSP_SUCCESS (zero) on success and a FD_WKSP_ERR_*
373 : (negative) on failure (logs details for failure). Reasons for
374 : failure include d is not in [0,part_max) and treap internal
375 : connectivity issues were detected (complete detection not
376 : guaranteed).
377 :
378 : Note that failure reasons are either user error or memory corruption.
379 : This cannot fail in normal operating circumstances. */
380 :
381 : int
382 : fd_wksp_private_used_treap_remove( ulong d,
383 : fd_wksp_t * wksp, /* Assumes current local join */
384 : fd_wksp_private_pinfo_t * pinfo ); /* == fd_wksp_private_pinfo( wksp ) */
385 :
386 : /* pinfo free treap APIs **********************************************/
387 :
388 : /* fd_wksp_private_free_treap_query queries wksp's free treap for the
389 : smallest partition of at least sz. On success, returns the index of
390 : a partition in the free treap suitable for sz, in [0,part_max), and,
391 : on failure, returns IDX_NULL. Reasons for failure include sz zero,
392 : sz is larger than any free partition, and internal treap corruption
393 : was detected. Might consume a wksp cycle tag and clobber partition
394 : cycle tags. Reasonably fast O(lg N) where N is the number of used
395 : partitions. */
396 :
397 : ulong
398 : fd_wksp_private_free_treap_query( ulong sz,
399 : fd_wksp_t * wksp, /* Assumes current local join */
400 : fd_wksp_private_pinfo_t * pinfo ); /* == fd_wksp_private_pinfo( wksp ) */
401 :
402 : /* fd_wksp_private_free_treap_insert inserts partition n into wksp's
403 : free treap. Assumes n is not in the idle stack, used treap or free
404 : treap. Does not care if n is in the partitioning or not. Reasonably
405 : fast O(lg N) where N is the number of partitions in the free treap.
406 :
407 : Partition n should have [gaddr_lo,gaddr_hi) and heap_prio initialized
408 : on entry (heap_prio should be a random value). tag need not be
409 : initialized but it is assumed that the caller will zero the tag
410 : beforehand to make the partition officially free. This will
411 : initialize {in_same, left, right, same, parent}_cidx. This will
412 : ignore {prev,next}_cidx. This might consume a wksp cycle tag and
413 : clobber the partition stack_cidx and cycle_tag fields.
414 :
415 : Returns FD_WKSP_SUCCESS (zero) on success and a FD_WKSP_ERR_*
416 : (negative) on failure (logs details for failure). Reasons for
417 : failure include n is not in [0,part_max), n's range is not in wksp
418 : data region, n's tag is not zero, n was detected as already inserted
419 : (this detection is not guaranteed), treap internal connectivity
420 : issues were detected (complete detection not guaranteed).
421 :
422 : If n's size exactly matches the size of partition already in the
423 : treap, n will be pushed onto that partition's same stack rather than
424 : inserted into the treap.
425 :
426 : On failure n and the treap itself were not modified (except possibly
427 : clobbering of stack_cidx and cycle_tag). Note that failures reasons
428 : are either user error or memory corruption. This has no failures in
429 : normal operating circumstances. */
430 :
431 : int
432 : fd_wksp_private_free_treap_insert( ulong n,
433 : fd_wksp_t * wksp, /* Assumes current local join */
434 : fd_wksp_private_pinfo_t * pinfo ); /* == fd_wksp_private_pinfo( wksp ) */
435 :
436 : /* fd_wksp_private_free_treap_same_is_empty returns 1 if the same list
437 : for d is empty and 0 if not. Returns 1 if corruption in detected.
438 : Assumes d is in the free treap. */
439 :
440 : static inline int
441 : fd_wksp_private_free_treap_same_is_empty( ulong d,
442 : fd_wksp_t * wksp, /* Assumes current local join */
443 15197934 : fd_wksp_private_pinfo_t * pinfo ) { /* == fd_wksp_private_pinfo( wksp ) */
444 15197934 : ulong part_max = wksp->part_max;
445 15197934 : return fd_wksp_private_pinfo_idx( pinfo[ d ].same_cidx )>=part_max;
446 15197934 : }
447 :
448 : /* fd_wksp_private_free_treap_same_remove removes the first partition
449 : from d's same list. Assumes the caller knows d's same list is not
450 : empty. The caller is promised that returned partition has the same
451 : size as d. */
452 :
453 : static inline ulong
454 : fd_wksp_private_free_treap_same_remove( ulong d,
455 : fd_wksp_t * wksp, /* Assumes current local join */
456 712356 : fd_wksp_private_pinfo_t * pinfo ) { /* == fd_wksp_private_pinfo( wksp ) */
457 712356 : ulong part_max = wksp->part_max;
458 712356 : ulong i = fd_wksp_private_pinfo_idx( pinfo[ d ].same_cidx );
459 712356 : ulong j = fd_wksp_private_pinfo_idx( pinfo[ i ].same_cidx );
460 712356 : /**/ pinfo[ d ].same_cidx = fd_wksp_private_pinfo_cidx( j );
461 712356 : if( j<part_max ) pinfo[ j ].parent_cidx = fd_wksp_private_pinfo_cidx( d );
462 712356 : pinfo[ i ].in_same = 0U;
463 712356 : pinfo[ i ].same_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
464 712356 : pinfo[ i ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
465 712356 : return i;
466 712356 : }
467 :
468 : /* fd_wksp_private_free_treap_remove removes partition d from wksp's
469 : free treap. Assumes d in the free treap, not in the used treap, not
470 : in the idle stack. Does not care if d is in the partitioning.
471 : Reasonably fast O(lg N) where N is the number of free partitions.
472 : This might consume a wksp cycle tag and clobber partition stack_cidx
473 : and cycle_tag fields. There is an edge case where d's can be swapped
474 : with another same sized partition.
475 :
476 : Returns FD_WKSP_SUCCESS (zero) on success and a FD_WKSP_ERR_*
477 : (negative) on failure (logs details for failure). Reasons for
478 : failure include d is not in [0,part_max) and treap internal
479 : connectivity issues were detected (complete detection not
480 : guaranteed).
481 :
482 : Note that failure reasons are either user error or memory corruption.
483 : This cannot fail in normal operating circumstances. */
484 :
485 : int
486 : fd_wksp_private_free_treap_remove( ulong d,
487 : fd_wksp_t * wksp, /* Assumes current local join */
488 : fd_wksp_private_pinfo_t * pinfo ); /* == fd_wksp_private_pinfo( wksp ) */
489 :
490 : /* private admin APIs *************************************************/
491 :
492 : /* fd_wksp_private_lock locks wksp. Assumes wksp is a current local
493 : join. If wksp is already locked, this will wait for the caller. If
494 : this detects that the caller died while holding the lock, it will try
495 : to steal the lock from the dead caller and cleanup any incomplete
496 : operation the caller was doing. Returns FD_WKSP_SUCCESS (0) if the
497 : lock was acquired or FD_WKSP_ERR_CORRUPT if the lock could not be
498 : obtained because memory corruption was detected while trying to
499 : recover from a dead caller that corrupted the wksp memory. */
500 :
501 : int
502 : fd_wksp_private_lock( fd_wksp_t * wksp );
503 :
504 : /* fd_wksp_private_unlock unlocks a locked wksp. Assumes wksp is a
505 : current local join and the caller has the lock */
506 :
507 : static inline void
508 60392286 : fd_wksp_private_unlock( fd_wksp_t * wksp ) {
509 60392286 : FD_COMPILER_MFENCE();
510 60392286 : FD_VOLATILE( wksp->owner ) = ULONG_MAX;
511 60392286 : FD_COMPILER_MFENCE();
512 60392286 : }
513 :
514 : /* private checkpt/restore APIs ***************************************/
515 : /* FIXME: MOVE THIS TO PUBLIC HEADER? */
516 :
517 : /* FD_WKSP_CHECKPT_{V1,V2}_{BINFO,UINFO}_MAX give the maximum byte size
518 : (including the terminating '\0') of a decompressed {v1,v2} checkpt
519 : {build,user} info cstr. */
520 :
521 9 : #define FD_WKSP_CHECKPT_V1_BINFO_MAX (16384UL)
522 9 : #define FD_WKSP_CHECKPT_V1_UINFO_MAX (16384UL)
523 :
524 : #define FD_WKSP_CHECKPT_V2_BINFO_MAX (16384UL)
525 : #define FD_WKSP_CHECKPT_V2_UINFO_MAX (16384UL)
526 :
527 : /* A fd_wksp_checkpt_v2_hdr_t gives the byte layout of frame 0 of a wksp
528 : v2 checkpt. This frame contains the style, compression algo used for
529 : the info, cgroup and appendix frames and fd_wksp_preview information
530 : uncompressed. */
531 :
532 : struct fd_wksp_checkpt_v2_hdr {
533 : ulong magic; /* Must be first, ==FD_WKSP_MAGIC */
534 : int style; /* Must be second, wksp checkpt style */
535 : int frame_style_compressed; /* frame style used for compressed frames */
536 : uint reserved; /* header padding */
537 : char name[ FD_SHMEM_NAME_MAX ]; /* cstr holding the original wksp name (note: FD_SHMEM_NAME_MAX==FD_LOG_NAME_MAX==40) */
538 : uint seed; /* wksp seed when checkpointed (probably same used to construct) */
539 : ulong part_max; /* part_max used to construct the wksp */
540 : ulong data_max; /* data_max used to construct the wksp */
541 : };
542 :
543 : typedef struct fd_wksp_checkpt_v2_hdr fd_wksp_checkpt_v2_hdr_t;
544 :
545 : /* A fd_wksp_checkpt_v2_info_t gives the byte layout of frame 1 of a
546 : wksp v2 checkpt. frame 1 immediately follows frame 0 and this frame
547 : contains the info structure followed compactly by the corresponding
548 : cstr (including the terminating '\0') stored consecutively in the
549 : same order. The size fields indicate the buffer layout. This frame
550 : is compressed according hdr/ftr specification. */
551 :
552 : struct fd_wksp_checkpt_v2_info {
553 : ulong mode;
554 : long wallclock;
555 : ulong app_id;
556 : ulong thread_id;
557 : ulong host_id;
558 : ulong cpu_id;
559 : ulong group_id;
560 : ulong tid;
561 : ulong user_id;
562 : /* FIXME: CONSIDER MAKING THESE ALL UCHAR / USHORT / 4 BYTE RESERVED */
563 : ulong sz_app; /* in [1,FD_LOG_NAME_MAX ~ 40B] */
564 : ulong sz_thread; /* " */
565 : ulong sz_host; /* " */
566 : ulong sz_cpu; /* " */
567 : ulong sz_group; /* " */
568 : ulong sz_user; /* " */
569 : ulong sz_path; /* in [1,PATH_MAX ~ 4KiB] */
570 : ulong sz_binfo; /* in [1,FD_WKSP_CHECKPT_V2_BINFO_MAX ~ 16KiB] */
571 : ulong sz_uinfo; /* in [1,FD_WKSP_CHECKPT_V2_UINFO_MAX ~ 16KiB] */
572 : };
573 :
574 : typedef struct fd_wksp_checkpt_v2_info fd_wksp_checkpt_v2_info_t;
575 :
576 : /* A v2 info frame is followed by zero or more volumes. A volume
577 : consists of zero or more cgroup frames and an appendix frame.
578 : Volumes are followed by a frame with a footer command and then an
579 : uncompressed footer frame.
580 :
581 : A cgroup frame starts with a zero or more meta commands that describe
582 : the allocations it contains followed by a data command that indicates
583 : the cgroup data section follows.
584 :
585 : An appendix frame starts with an appendix command, giving the number
586 : of cgroup frames it covers and the offset to the previous appendix
587 : frame (0 if the first appendix frame). This is followed by a ulong
588 : array with checkpt offsets to those cgroup frames followed a ulong
589 : array with the number of allocations in each cgroup frame. An
590 : appendix covers all cgroup frames between it and the previous
591 : appendix frame (or info frame if the first appendix).
592 :
593 : The last volume is followed by a compressed frame with a sole volumes
594 : command. The volumes command gives the offset of the appendix of the
595 : last volume (or 0 if there are no volumes). (This allows the final
596 : frame to be uncompressed while all the volumes can be compressed.)
597 :
598 : An uncompressed footer frame follows indicating the v2 checkpt is
599 : done. The command gives the total number of cgroup frames in the
600 : checkpt and the offset to the last volume's appendix (or 0 if no
601 : volumes).
602 :
603 : A fd_wksp_checkpt_v2_cmd_t supports writing an arbitrarily large
604 : checkpt single pass with only small upfront bounded allocation while
605 : supporting both streaming and parallel restore of those frames. */
606 :
607 : union fd_wksp_checkpt_v2_cmd {
608 : struct { ulong tag; /* > 0 */ ulong gaddr_lo; ulong gaddr_hi; } meta;
609 : struct { ulong tag; /* ==0 */ ulong cgroup_cnt; /* ==ULONG_MAX */ ulong frame_off; /* ==ULONG_MAX */ } data;
610 : struct { ulong tag; /* ==0 */ ulong cgroup_cnt; /* < ULONG_MAX */ ulong frame_off; /* < ULONG_MAX */ } appendix;
611 : struct { ulong tag; /* ==0 */ ulong cgroup_cnt; /* ==ULONG_MAX */ ulong frame_off; /* < ULONG_MAX */ } volumes;
612 : };
613 :
614 : typedef union fd_wksp_checkpt_v2_cmd fd_wksp_checkpt_v2_cmd_t;
615 :
616 : FD_FN_PURE static inline int
617 75 : fd_wksp_checkpt_v2_cmd_is_meta( fd_wksp_checkpt_v2_cmd_t const * cmd ) {
618 75 : return cmd->meta.tag > 0UL;
619 75 : }
620 :
621 : FD_FN_PURE static inline int
622 21 : fd_wksp_checkpt_v2_cmd_is_data( fd_wksp_checkpt_v2_cmd_t const * cmd ) {
623 21 : return (cmd->data.tag==0UL) & (cmd->data.cgroup_cnt==ULONG_MAX) & (cmd->data.frame_off==ULONG_MAX);
624 21 : }
625 :
626 : FD_FN_PURE static inline int
627 63 : fd_wksp_checkpt_v2_cmd_is_appendix( fd_wksp_checkpt_v2_cmd_t const * cmd ) {
628 63 : return (cmd->appendix.tag==0UL) & (cmd->appendix.cgroup_cnt<ULONG_MAX) & (cmd->appendix.frame_off<ULONG_MAX);
629 63 : }
630 :
631 : FD_FN_PURE static inline int
632 0 : fd_wksp_checkpt_v2_cmd_is_volumes( fd_wksp_checkpt_v2_cmd_t const * cmd ) {
633 0 : return (cmd->volumes.tag==0UL) & (cmd->volumes.cgroup_cnt==ULONG_MAX) & (cmd->volumes.frame_off<ULONG_MAX);
634 0 : }
635 :
636 : /* A fd_wksp_checkpt_v2_ftr_t gives the byte layout of the final frame
637 : of a wksp v2 checkpt. This frame contains this footer uncompressed.
638 : This is wksp checkpt header backwards plus some additional
639 : information to allow users to seek from the end of the checkpt to the
640 : header (checkpt_sz), to the appendix frame (frame_off_appendix) and
641 : do any allocations upfront necessary to completely unpack the
642 : checkpt. */
643 :
644 : struct fd_wksp_checkpt_v2_ftr {
645 : ulong alloc_cnt; /* total number of allocations in checkpt */
646 : ulong cgroup_cnt; /* total number of cgroups in checkpt */
647 : ulong volume_cnt; /* total number of volumes in checkpt */
648 : ulong frame_off; /* byte offset (relative to header initial byte) of the volumes command */
649 : ulong checkpt_sz; /* checkpt byte size, from header initial byte to the footer final byte inclusive (note that
650 : this can be used to convert offsets relative to header initial byte to offsets relative to
651 : the end-of-file / the one past the final footer byte) */
652 : ulong data_max; /* should match header */
653 : ulong part_max; /* " */
654 : uint seed; /* " */
655 : char name[ FD_SHMEM_NAME_MAX ]; /* " */
656 : uint reserved; /* " */
657 : int frame_style_compressed; /* " */
658 : int style; /* " */
659 : ulong unmagic; /* ==~FD_WKSP_MAGIC */
660 : };
661 :
662 : typedef struct fd_wksp_checkpt_v2_ftr fd_wksp_checkpt_v2_ftr_t;
663 :
664 : /* fd_wksp_private_{checkpt,restore,printf}_v1 provide the v1
665 : implementations of {checkpt,restore,printf}. That is, checkpt_v1
666 : will only write a v1 style checkpt while the {restore,printt}_v1 can
667 : assume that the path exclusively contains a v1 style checkpt. These
668 : can assume that the input arguments have been validated by their
669 : caller. The printf implementation can further assume verbose is
670 : positive and the verbose 0 information has already been printed. For
671 : checkpt/restore, if tpool is non-NULL, the operation will be
672 : parallelized over tpool threads [t0,t1). Assumes the caller is
673 : thread t0 and threads (t0,t1) are available for thread dispatch. */
674 :
675 : int
676 : fd_wksp_private_checkpt_v1( fd_tpool_t * tpool,
677 : ulong t0,
678 : ulong t1,
679 : fd_wksp_t * wksp,
680 : char const * path,
681 : ulong mode,
682 : char const * uinfo );
683 :
684 : int
685 : fd_wksp_private_restore_v1( fd_tpool_t * tpool,
686 : ulong t0,
687 : ulong t1,
688 : fd_wksp_t * wksp,
689 : char const * path,
690 : uint new_seed );
691 :
692 : int
693 : fd_wksp_private_printf_v1( int fd,
694 : char const * path,
695 : int verbose );
696 :
697 : /* Similarly for v2. Note that style==FD_WKSP_CHECKPT_STYLE_V3 in the
698 : fd_wksp_checkpt function becomes a FD_WKSP_CHECKPT_STYLE_V2 with a
699 : FD_CHECKPT_FRAME_STYLE_LZ4 cgroup frames in the checkpt itself. */
700 :
701 : int
702 : fd_wksp_private_checkpt_v2( fd_tpool_t * tpool,
703 : ulong t0,
704 : ulong t1,
705 : fd_wksp_t * wksp,
706 : char const * path,
707 : ulong mode,
708 : char const * uinfo,
709 : int frame_style_compresed );
710 :
711 : int
712 : fd_wksp_private_restore_v2( fd_tpool_t * tpool,
713 : ulong t0,
714 : ulong t1,
715 : fd_wksp_t * wksp,
716 : char const * path,
717 : uint new_seed );
718 :
719 : int
720 : fd_wksp_private_printf_v2( int fd,
721 : char const * path,
722 : int verbose );
723 :
724 : FD_PROTOTYPES_END
725 :
726 : #endif /* HEADER_fd_src_util_wksp_fd_wksp_private_h */
|
