Line data Source code
1 : #ifndef HEADER_fd_src_tango_mcache_fd_mcache_h
2 : #define HEADER_fd_src_tango_mcache_fd_mcache_h
3 :
4 : #include "../fd_tango_base.h"
5 :
6 : /* FD_MCACHE_{ALIGN,FOOTPRINT} specify the alignment and footprint
7 : needed for a mcache with depth entries and an application region of
8 : size app_sz. ALIGN is at least FD_FRAG_META_ALIGN and recommended to
9 : be at least double cache line to mitigate various kinds of false
10 : sharing. depth and app_sz are assumed to be valid (i.e. depth is an
11 : integer power of 2 of at least FD_MCACHE_BLOCK and the combination
12 : will not require a footprint larger than ULONG_MAX). These are
13 : provided to facilitate compile time mcache declarations. */
14 :
15 6 : #define FD_MCACHE_ALIGN (128UL)
16 : #define FD_MCACHE_FOOTPRINT( depth, app_sz ) \
17 1 : FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_INIT, \
18 1 : FD_MCACHE_ALIGN, 128UL ), /* hdr */ \
19 1 : FD_MCACHE_ALIGN, FD_MCACHE_SEQ_CNT*sizeof(ulong) ), /* seq */ \
20 1 : FD_MCACHE_ALIGN, (depth)*sizeof(fd_frag_meta_t) ), /* meta */ \
21 1 : FD_MCACHE_ALIGN, (app_sz) ), /* app */ \
22 1 : FD_MCACHE_ALIGN )
23 :
24 : /* FD_MCACHE_SEQ_CNT specifies the number of entries in the mcache's seq
25 : storage region. It is aligned FD_MCACHE_ALIGN. Multiples of 16 have
26 : good Feng Shui. seq[0] has special meaning; see below for details. */
27 :
28 0 : #define FD_MCACHE_SEQ_CNT (16UL)
29 :
30 : /* FD_MCACHE_{LG_BLOCK,LG_INTERLEAVE,BLOCK} specifies how recent
31 : fragment meta data should be packed into mcaches. LG_BLOCK should be
32 : in [1,64). LG_INTERLEAVE should be in [0,FD_MCACHE_BLOCK). BLOCK ==
33 : 2^LG_BLOCK. See below for more details. */
34 :
35 : #define FD_MCACHE_LG_BLOCK (0)
36 : #define FD_MCACHE_LG_INTERLEAVE (0)
37 0 : #define FD_MCACHE_BLOCK (1UL) /* == 2^FD_MCACHE_LG_BLOCK, explicit to workaround compiler limitations */
38 :
39 : FD_PROTOTYPES_BEGIN
40 :
41 : /* Construction API */
42 :
43 : /* fd_mcache_{align,footprint} return the required alignment and
44 : footprint of a memory region suitable for use as mcache with depth
45 : entries. align returns FD_MCACHE_ALIGN. If depth is invalid (e.g.
46 : not an integer power-of-2 >= FD_MCACHE_BLOCK or the footprint is
47 : larger than ULONG_MAX), footprint will silently return 0 (and thus
48 : can be used by the caller to validate mcache configuration
49 : parameters). */
50 :
51 : FD_FN_CONST ulong
52 : fd_mcache_align( void );
53 :
54 : FD_FN_CONST ulong
55 : fd_mcache_footprint( ulong depth,
56 : ulong app_sz );
57 :
58 : /* fd_mcache_new formats an unused memory region for use as a mcache.
59 : shmem is a non-NULL pointer to this region in the local address space
60 : with the required footprint and alignment. depth is the number of
61 : cache entries (should be an integer power of 2 >= FD_MCACHE_BLOCK).
62 : The mcache will also have an app_sz byte application region for
63 : application specific usage. seq0 is the initial fragment sequence
64 : number a producer should use for this mcache.
65 :
66 : The cache entries will be initialized such all queries for any
67 : sequence number will fail immediately after creation. They will
68 : further be initialized such that for any consumer initialized to
69 : start receiving a sequence number at or after seq0 will think it is
70 : ahead of the producer (such that it will wait for its sequence number
71 : cleanly instead of immediately trying to recover a gap). Conversely,
72 : consumers initialized to start receiving a sequence number before
73 : seq0 will think they are behind the producer (thus realize it is been
74 : incorrectly initialized and can recover appropriately). Anybody who
75 : looks at the mcache entries directly will also see the entries are
76 : initialized to have zero sz (such that they shouldn't try deference
77 : any fragment payloads), have the SOM and EOM bits set (so they
78 : shouldn't try to interpret the entry as part of some message spread
79 : over multiple fragments) and have the ERR bit set (so they don't
80 : think there is any validity to the meta data or payload).
81 :
82 : The application region will be initialized to zero.
83 :
84 : Returns shmem (and the memory region it points to will be formatted
85 : as a mcache, caller is not joined) on success and NULL on failure
86 : (logs details). Reasons for failure include obviously bad shmem or
87 : bad depth. */
88 :
89 : void *
90 : fd_mcache_new( void * shmem,
91 : ulong depth,
92 : ulong app_sz,
93 : ulong seq0 );
94 :
95 : /* fd_mcache_join joins the caller to the mcache. shmcache points to
96 : the first byte of the memory region backing the mcache in the
97 : caller's address space.
98 :
99 : Returns a pointer in the local address space to the mcache's entries
100 : on success (IMPORTANT! THIS IS NOT JUST A CAST OF SHMCACHE) and NULL
101 : on failure (logs details). Reasons for failure are that shmcache is
102 : obviously not a pointer to memory region holding a mcache. Every
103 : successful join should have a matching leave. The lifetime of the
104 : join is until the matching leave or thread group is terminated.
105 :
106 : Entries are indexed [0,depth) and the mapping from sequence number to
107 : depth is nontrivial (see below for accessors and mapping functions).
108 : There is no restrictions on the number of joins overall and a single
109 : thread can join multiple times (all joins to the same shmcache laddr
110 : will return same mcache laddr). */
111 :
112 : fd_frag_meta_t *
113 : fd_mcache_join( void * shmcache );
114 :
115 : /* fd_mcache_leave leaves a current local join. Returns a pointer to
116 : the underlying shared memory region on success (IMPORTANT! THIS IS
117 : NOT JUST A CAST OF MCACHE) and NULL on failure (logs details).
118 : Reasons for failure include mcache is NULL. */
119 :
120 : void *
121 : fd_mcache_leave( fd_frag_meta_t const * mcache );
122 :
123 : /* fd_mcache_delete unformats a memory region used as a mcache. Assumes
124 : nobody is joined to the region. Returns a pointer to the underlying
125 : shared memory region or NULL if used obviously in error (e.g.
126 : shmcache is obviously not a mcache ... logs details). The ownership
127 : of the memory region is transferred to the caller. */
128 :
129 : void *
130 : fd_mcache_delete( void * shmcache );
131 :
132 : /* Accessor API */
133 :
134 : /* fd_mcache_{depth,seq0} return the values corresponding to those use
135 : at the mcache's construction. Assume mcache is a current local join. */
136 :
137 : FD_FN_PURE ulong fd_mcache_depth ( fd_frag_meta_t const * mcache );
138 : FD_FN_PURE ulong fd_mcache_app_sz( fd_frag_meta_t const * mcache );
139 : FD_FN_PURE ulong fd_mcache_seq0 ( fd_frag_meta_t const * mcache );
140 :
141 : /* fd_mcache_seq_laddr returns location in the caller's local address
142 : space of mcache's sequence array. This array is indexed
143 : [0,FD_MCACHE_SEQ_CNT) with FD_MCACHE_ALIGN alignment (double cache
144 : line). laddr_const is a const correct version. Assumes mcache is a
145 : current local join. The lifetime of the returned pointer is the same
146 : as the underlying join.
147 :
148 : seq[0] has special meaning. Specifically, sequence numbers in
149 : [seq0,seq[0]) cyclic are guaranteed to have been published. seq[0]
150 : is not strictly atomically updated by the producer when it publishes
151 : so seq[0] can lag the most recently published sequence number
152 : somewhat. As seq[0] is moderately to aggressively frequently updated
153 : by the mcache's producer (depending on the application), this is on
154 : its own cache line pair to avoid false sharing. seq[0] is mostly
155 : used for monitoring, initialization and support for some methods for
156 : unreliable consumer overrun handling.
157 :
158 : The meaning of the remaining sequence numbers is application
159 : dependent. Application should try to restrict any use of these to
160 : ones that are seq[0] cache-friendly (e.g. use for producer write
161 : oriented cases or use for rarely used cases). */
162 :
163 : FD_FN_CONST ulong const * fd_mcache_seq_laddr_const( fd_frag_meta_t const * mcache );
164 : FD_FN_CONST ulong * fd_mcache_seq_laddr ( fd_frag_meta_t * mcache );
165 :
166 : /* fd_mcache_app_laddr returns location in the caller's local address
167 : space of memory set aside for application specific usage. Assumes
168 : mcache is a current local join. The lifetime of the returned pointer
169 : is the same as the underlying join. This region has FD_MCACHE_ALIGN
170 : alignment (double cache line) and is fd_mcache_app_sz( mcache ) in
171 : size. laddr_const is a const-correct version. */
172 :
173 : FD_FN_PURE uchar const * fd_mcache_app_laddr_const( fd_frag_meta_t const * mcache );
174 : FD_FN_PURE uchar * fd_mcache_app_laddr ( fd_frag_meta_t * mcache );
175 :
176 : /* fd_mcache_seq_query atomically reads the mcache's seq[0] (e.g. from
177 : fd_mcache_seq_laddr_const) to get a lower bound of where the producer
178 : is at in sequence space (in the sense that the producer guarantees it
179 : has produced all sequence numbers strictly before the return value
180 : cyclic). This is usually done at consumer startup and, for some
181 : unreliable consumer overrun handling, during consumer overrun
182 : recovery. It is strongly recommended for consumers to avoid using
183 : this as much as possible to limit cache line ping-ponging with the
184 : producer. */
185 :
186 : static inline ulong
187 1 : fd_mcache_seq_query( ulong const * _seq ) {
188 1 : return __atomic_load_n( _seq, __ATOMIC_ACQUIRE );
189 1 : }
190 :
191 : /* fd_mcache_seq_update updates the mcache's seq[0] (e.g. from
192 : fd_mcache_seq_laddr) above where the producer a lower bound of where
193 : the producer is currently at (in the sense that the producer has
194 : produced all sequence numbers strictly before seq cyclic). This
195 : should be monotonically non-decreasing. This should be done
196 : moderately frequently (e.g. in background housekeeping) after the
197 : producer has moved forward in sequence space since the last update.
198 : Even more aggressively is usually fine. This should also be done
199 : when the producer is shutdown to facilitate cleanly restarting a
200 : producer and what not. This also serves as a compiler memory fence
201 : to ensure the sequence number is updated at a well defined point in
202 : the instruction stream (e.g. so that compiler doesn't move any stores
203 : from before the update to after the above). */
204 :
205 : static inline void
206 : fd_mcache_seq_update( ulong * _seq,
207 1 : ulong seq ) {
208 1 : __atomic_store_n( _seq, seq, __ATOMIC_RELEASE );
209 1 : }
210 :
211 : /* fd_mcache_line_idx returns the index of the cache line in a depth
212 : entry mcache (depth is assumed to be a power of 2) where the
213 : metadata for the frag with sequence number seq will be stored when it
214 : is in cache. Outside of startup transients, a mcache is guaranteed
215 : to exactly hold the depth most recently sequence numbers (the act of
216 : publishing a new sequence number atomically unpublishes the oldest
217 : sequence number implicitly).
218 :
219 : FD_MCACHE_LG_INTERLEAVE is in [0,FD_MCACHE_LG_BLOCK) and controls the
220 : details of this mapping. LG_INTERLEAVE 0 indicates no interleaving.
221 : Values from 1 to LG_BLOCK space out sequential frag meta data in
222 : memory to avoid false sharing between producers and fast consumers to
223 : keep fast consumers low latency while keeping frag meta data storage
224 : compact in memory to help throughput of slow consumers.
225 :
226 : Specifically, at a LG_INTERLEAVE of i with s byte frag meta data,
227 : meta data storage for sequential frags is typically s*2^i bytes
228 : apart. To avoid wasting memory and bandwidth, the interleaving is
229 : implemented by doing a rotation of the least LG_BLOCK bits of the lg
230 : depth bits of the sequence number (NOTE: this imposes a requirement
231 : that mcaches have at least a depth of 2^LG_BLOCK fragments). This
232 : yields a frag sequence number to line idx mapping that avoids false
233 : sharing for fast consumers and maintains compactness, avoids TLB
234 : thrashing (even if meta data is backed by normal pages) and exploits
235 : CPU data and TLB prefetching behavior for slow consumers.
236 :
237 : How useful block interleaving is somewhat application dependent.
238 : Different values have different trade offs between optimizing for
239 : fast and slow consumers and for different sizes of meta data and
240 : different page size backing memory.
241 :
242 : Using 0 / B for FD_MCACHE_LG_INTERLEAVE / LG_BLOCK will disable meta
243 : data interleaving while still requiring mcaches be at least 2^B in
244 : size. This implicitly optimizes for slow consumers. Something like
245 : 2 / 7 (with a 32-byte size 32-byte aligned fd_frag_meta_t and a
246 : mcache that is at least normal page aligned) will access cached meta
247 : data in sequential blocks of 128 message fragments that are normal
248 : page size and aligned while meta data within those blocks will
249 : typically be strided at double DRAM cache line granularity. As such,
250 : fast consumers (e.g. those within 32 of the producers) will rarely
251 : have false sharing with the producers as nearby sequence numbers are
252 : on different DRAM cache line pairs. And slow consumers (e.g. ones
253 : that fall more than 128 fragments behind) will access meta data in a
254 : very DRAM cache friendly / data prefetcher / TLB friendly / bandwidth
255 : efficient manner (and without needing to load any prefilterable
256 : payload data while completely avoiding memory being written by the
257 : producer). That is, it typically has good balance of performance for
258 : both fast and slow consumers simultaneously. */
259 :
260 : #if FD_MCACHE_LG_INTERLEAVE==0
261 :
262 : FD_FN_CONST static inline ulong /* Will be in [0,depth) */
263 : fd_mcache_line_idx( ulong seq,
264 257062174 : ulong depth ) { /* Assumed power of 2 >= BLOCK */
265 257062174 : return seq & (depth-1UL);
266 257062174 : }
267 :
268 : #else
269 :
270 : FD_FN_CONST static inline ulong /* Will be in [0,depth) */
271 : fd_mcache_line_idx( ulong seq,
272 : ulong depth ) { /* Assumed power of 2 >= BLOCK */
273 : ulong block_mask = FD_MCACHE_BLOCK - 1UL; /* Compile time */
274 : ulong page_mask = (depth-1UL) & (~block_mask); /* Typically compile time or loop invariant */
275 : ulong page = seq & page_mask;
276 : ulong bank = (seq << FD_MCACHE_LG_INTERLEAVE) & block_mask;
277 : ulong idx = (seq & block_mask) >> (FD_MCACHE_LG_BLOCK-FD_MCACHE_LG_INTERLEAVE);
278 : return page | bank | idx;
279 : }
280 :
281 : #endif
282 :
283 : /* fd_mcache_publish inserts the metadata for frag seq into the given
284 : depth entry mcache in a way compatible with FD_MCACHE_WAIT and
285 : FD_MCACHE_WAIT_SSE (but not FD_MCACHE_WAIT_AVX ... see FD_MCACHE_WAIT
286 : for more details). This implicitly evicts the metadata for the
287 : sequence number currently stored at fd_mcache_line_idx( seq, depth ).
288 : In the typical case where sequence numbers are published into the
289 : mcache sequentially, the evicted metadata is typically for frag
290 : seq-depth (cyclic). This does no error checking or the like as it is
291 : frequently used in ultra high performance contexts. This operation
292 : implies a compiler mfence to the caller. */
293 :
294 : static inline void
295 : fd_mcache_publish( fd_frag_meta_t * mcache, /* Assumed a current local join */
296 : ulong depth, /* Assumed an integer power-of-2 >= BLOCK */
297 : ulong seq,
298 : ulong sig,
299 : ulong chunk, /* Assumed in [0,UINT_MAX] */
300 : ulong sz, /* Assumed in [0,USHORT_MAX] */
301 : ulong ctl, /* Assumed in [0,USHORT_MAX] */
302 : ulong tsorig, /* Assumed in [0,UINT_MAX] */
303 72129 : ulong tspub ) { /* Assumed in [0,UINT_MAX] */
304 72129 : fd_frag_meta_t * meta = mcache + fd_mcache_line_idx( seq, depth );
305 : #if FD_HAS_ARM || FD_HAS_RISCV
306 : __atomic_store_n( &meta->seq, fd_seq_dec( seq, 1UL ), __ATOMIC_RELAXED );
307 : FD_HW_MFENCE_ST();
308 : meta->sig = sig;
309 : meta->chunk = (uint )chunk;
310 : meta->sz = (ushort)sz;
311 : meta->ctl = (ushort)ctl;
312 : meta->tsorig = (uint )tsorig;
313 : meta->tspub = (uint )tspub;
314 : __atomic_store_n( &meta->seq, seq, __ATOMIC_RELEASE );
315 : FD_HW_MFENCE_ST();
316 : #else
317 72129 : FD_COMPILER_MFENCE();
318 72129 : meta->seq = fd_seq_dec( seq, 1UL );
319 72129 : FD_COMPILER_MFENCE();
320 72129 : meta->sig = sig;
321 72129 : meta->chunk = (uint )chunk;
322 72129 : meta->sz = (ushort)sz;
323 72129 : meta->ctl = (ushort)ctl;
324 72129 : meta->tsorig = (uint )tsorig;
325 72129 : meta->tspub = (uint )tspub;
326 72129 : FD_COMPILER_MFENCE();
327 72129 : meta->seq = seq;
328 72129 : FD_COMPILER_MFENCE();
329 72129 : #endif
330 72129 : }
331 :
332 : #if FD_HAS_SSE
333 :
334 : /* fd_mcache_publish_sse is a SSE implementation of fd_mcache_publish.
335 : It is compatible with FD_MCACHE_WAIT and FD_MCACHE_WAIT_SSE. */
336 :
337 : static inline void
338 : fd_mcache_publish_sse( fd_frag_meta_t * mcache, /* Assumed a current local join */
339 : ulong depth, /* Assumed an integer power-of-2 >= BLOCK */
340 : ulong seq,
341 : ulong sig,
342 : ulong chunk, /* Assumed in [0,UINT_MAX] */
343 : ulong sz, /* Assumed in [0,USHORT_MAX] */
344 : ulong ctl, /* Assumed in [0,USHORT_MAX] */
345 : ulong tsorig, /* Assumed in [0,UINT_MAX] */
346 0 : ulong tspub ) { /* Assumed in [0,UINT_MAX] */
347 0 : fd_frag_meta_t * meta = mcache + fd_mcache_line_idx( seq, depth );
348 0 : __m128i meta_sse0 = fd_frag_meta_sse0( fd_seq_dec( seq, 1UL ), sig );
349 0 : __m128i meta_sse1 = fd_frag_meta_sse1( chunk, sz, ctl, tsorig, tspub );
350 0 : FD_COMPILER_MFENCE();
351 0 : FD_VOLATILE( meta->sse0 ) = meta_sse0;
352 0 : FD_COMPILER_MFENCE();
353 0 : FD_VOLATILE( meta->sse1 ) = meta_sse1;
354 0 : FD_COMPILER_MFENCE();
355 0 : meta->seq = seq;
356 0 : FD_COMPILER_MFENCE();
357 0 : }
358 :
359 : #endif
360 :
361 : #if FD_HAS_AVX
362 :
363 : /* fd_mcache_publish_avx is an AVX implementation of fd_mcache_publish.
364 : It is compatible with FD_MCACHE_WAIT, FD_MCACHE_WAIT_SSE and
365 : FD_MCACHE_WAIT_AVX. It requires a target for which aligned AVX
366 : stores are guaranteed atomic under the hood (see below for more
367 : details). */
368 :
369 : static inline void
370 : fd_mcache_publish_avx( fd_frag_meta_t * mcache, /* Assumed a current local join */
371 : ulong depth, /* Assumed an integer power-of-2 >= BLOCK */
372 : ulong seq,
373 : ulong sig,
374 : ulong chunk, /* Assumed in [0,UINT_MAX] */
375 : ulong sz, /* Assumed in [0,USHORT_MAX] */
376 : ulong ctl, /* Assumed in [0,USHORT_MAX] */
377 : ulong tsorig, /* Assumed in [0,UINT_MAX] */
378 0 : ulong tspub ) { /* Assumed in [0,UINT_MAX] */
379 0 : fd_frag_meta_t * meta = mcache + fd_mcache_line_idx( seq, depth );
380 0 : fd_frag_meta_v256_t meta_avx = fd_frag_meta_avx( seq, sig, chunk, sz, ctl, tsorig, tspub );
381 0 : FD_COMPILER_MFENCE();
382 : /* Volatile rather than a 256-bit store intrinsic: some versions of
383 : Clang break the intrinsic into two non-atomic 128-bit stores. */
384 0 : FD_VOLATILE( meta->avx ) = meta_avx;
385 0 : FD_COMPILER_MFENCE();
386 0 : }
387 :
388 : #endif
389 :
390 : #if FD_HAS_ARM
391 :
392 : static inline void
393 : fd_mcache_publish_arm( fd_frag_meta_t * mcache, /* Assumed a current local join */
394 : ulong depth, /* Assumed an integer power-of-2 >= BLOCK */
395 : ulong seq,
396 : ulong sig,
397 : ulong chunk, /* Assumed in [0,UINT_MAX] */
398 : ulong sz, /* Assumed in [0,USHORT_MAX] */
399 : ulong ctl, /* Assumed in [0,USHORT_MAX] */
400 : ulong tsorig, /* Assumed in [0,UINT_MAX] */
401 : ulong tspub ) { /* Assumed in [0,UINT_MAX] */
402 : /* str seq-1, [meta]
403 : dmb ishst
404 : str sig, [meta, #8]
405 : stp ul2, ul3, [meta, #16]
406 : stlr seq, [meta] */
407 : fd_frag_meta_t * meta = mcache + fd_mcache_line_idx( seq, depth );
408 : ulong ul2 = fd_frag_meta_ul2( chunk, sz, ctl );
409 : ulong ul3 = fd_frag_meta_ul3( tsorig, tspub );
410 : __atomic_store_n( &meta->seq, fd_seq_dec( seq, 1UL ), __ATOMIC_RELAXED );
411 : FD_HW_MFENCE_ST();
412 : meta->sig = sig;
413 : fd_arm_stp16( meta->ul+2, ul2, ul3 );
414 : __atomic_store_n( &meta->seq, seq, __ATOMIC_RELEASE );
415 : FD_HW_MFENCE_ST();
416 : }
417 :
418 : #endif
419 :
420 : /* FD_MCACHE_WAIT does a bounded wait for a producer to transmit a
421 : particular frag.
422 :
423 : meta (fd_frag_meta_t * compatible) is the location on the caller
424 : where the wait should save the found metadata. This typically
425 : points to a stack temporary.
426 :
427 : mline (fd_frag_meta_t const * compatible) will be
428 : mcache + fd_mcache_line_idx( seq_expected, depth )
429 : when the wait does not time out. This is the location where the
430 : caller can verify (after any speculative processing of seq_expected)
431 : the producer did not clobber the consumer during the processing.
432 :
433 : seq_found (ulong compatible) will be the sequence number found at
434 : mline when the wait does not time out. This will be seq_expected
435 : on a successful wait.
436 :
437 : seq_diff (long compatible) will be how many sequence numbers ahead
438 : of seq_expected when the wait does not time out
439 : fd_seq_diff( seq_found, seq_expected )
440 : This will be zero on a successful wait. This will be positive
441 : otherwise and a lower bound of how far behind the consumer is from
442 : the producer (and seq_found will typically be a reasonably recently
443 : produced sequence number).
444 :
445 : poll_max (ulong compatible) is the number of times FD_MCACHE_WAIT
446 : will poll the mcache of the given depth for seq_expected before
447 : timing out. poll_max should be positive on input. (Note: using
448 : ULONG_MAX for poll_max practically turns this into a blocking wait as
449 : this take hundreds of years to complete on realistic platforms.)
450 : If poll max is zero on completion of the, the wait timed out.
451 :
452 : mcache (fd_frag_meta_t const * compatible) is a current local join to
453 : the mcache the producer uses to cache metadata for the frags it is
454 : producing.
455 :
456 : depth (a ulong compatible power of two of at least FD_MCACHE_BLOCK)
457 : is the number of entries in mcache.
458 :
459 : seq_expected (ulong compatible) is the sequence number to wait to be
460 : produced.
461 :
462 : On completion of the WAIT, if poll_max is zero, the WAIT timed out
463 : and none of the other outputs (meta, mline, seq_found, seq_diff)
464 : should be trusted. If poll_max is non-zero, it will be the original
465 : poll_max value decremented by the number of polls it took for the
466 : WAIT to complete and the WAIT did not timeout.
467 :
468 : When the WAIT did not timeout, mline, seq_found and seq_diff can be
469 : trusted. If seq_diff is positive, the caller has fallen more than
470 : depth behind the producer such that metadata for frag seq_expected is
471 : no longer available via the mcache. IMPORTANT! *META MIGHT NOT BE
472 : VALID FOR SEQ_FOUND WHEN CONSUMER HAS FALLEN BEHIND (e.g. if the
473 : producer is paused after it starts writing metadata but before it has
474 : completed writing it ... an unreliable overrun consumer that reads
475 : the metadata while the producer is paused will observe metadata that
476 : is a mix of the new metadata and old metadata with a bogus sequence
477 : number on it). seq_diff is a lower bound of how far the caller has
478 : fallen behind the producer and seq_found is a lower bound of where
479 : producer is currently at.
480 :
481 : Otherwise, the caller is within depth of the producer and *meta will
482 : be a local copy of the desired metadata.
483 :
484 : TL;DR Typical usage:
485 :
486 : ... Example HPC receiver run loop setup
487 :
488 : ulong poll_max = ... number of polls until next housekeeping (positive)
489 : fd_frag_meta_t const * mcache = ... local join to producer's mcache
490 : ulong depth = ... producer's mcache depth
491 : ulong rx_seq = ... next sequence number to receive from producer
492 :
493 : ... Example HPC receiver run loop structure
494 :
495 : for(;;) {
496 :
497 : fd_frag_meta_t meta[1];
498 : fd_frag_meta_t const * mline;
499 : ulong tx_seq;
500 : long seq_diff;
501 : FD_MCACHE_WAIT( meta, mline, tx_seq, seq_diff, poll_max, mcache, depth, rx_seq );
502 :
503 : ... At this point, poll_max can be trusted and has been
504 : ... decremented the number of polls that were done by the wait
505 : ... from its value at the start of the wait. We either timed
506 : ... out waiting, detected we've been overrun or received the
507 : ... desired meta data.
508 :
509 : if( FD_UNLIKELY( !poll_max ) ) {
510 :
511 : ... We timed out. Do background housekeeping.
512 :
513 : poll_max = ... Reload for the next housekeeping (positive and
514 : ... ideally somewhat randomized each time). Value
515 : ... depends on how aggressively the run loop needs
516 : ... to do background tasks such as
517 : ... command-and-control interactions, monitoring
518 : ... diagnostics, maintenance, etc).
519 :
520 : continue;
521 : }
522 :
523 : ... At this point, poll_max, mline, tx_seq and seq_diff can be
524 : ... trusted. We either have been overrun or received the desired
525 : ... metadata. poll_max>0 and seq_diff==fd_seq_diff(tx_seq,rx_seq).
526 :
527 : if( FD_UNLIKELY( seq_diff ) ) {
528 :
529 : ... We got overrun by the producer. tx_seq is an estimate
530 : ... (typically within depth and often much closer) of where the
531 : ... producer currently is at. Technically, this branch should
532 : ... never be exercised on reliable consumers but is a generally
533 : ... good idea regardless to detect / protect against flow
534 : ... control misconfigurations, bugs in the consumer, etc.
535 : ... Overrun handling could be as simple as "rx_seq = tx_seq;"
536 : ... here (but applications will typically do more elaborate
537 : ... application specific handling)
538 :
539 : continue;
540 : }
541 :
542 : ... We received meta data for frag rx_seq. At this point, meta,
543 : ... tx_seq, seq_diff and poll_max can be trusted. poll_max>=0UL,
544 : ... tx_seq==rx_seq and seq_diff==0L.
545 :
546 : ... Process meta->* at the run loop's leisure and speculatively
547 : ... process actual frag data as necessary here.
548 :
549 : tx_seq = fd_frag_meta_seq_query( mline );
550 : if( FD_UNLIKELY( fd_seq_ne( tx_seq, rx_seq ) ) ) {
551 :
552 : ... We got overrun by the producer while speculatively
553 : ... processing data pointed to by meta. Same considerations
554 : ... as above for overrun handling.
555 :
556 : continue;
557 : }
558 :
559 : ... Advance to the producer's next sequence number.
560 :
561 : rx_seq = fd_seq_inc( rx_seq, 1UL );
562 : }
563 :
564 : This assumes the producer either writes the entire metadata cache
565 : line atomically (on targets where aligned AVX writes are in fact
566 : atomic) or writes the metadata cache line in a particular order:
567 :
568 : FD_COMPILER_MFENCE();
569 : mcache_line->seq = fd_seq_dec( seq, 1UL ); // atomically marks cache line as in the process of writing seq
570 : // This implicitly atomically evicts frag metadata for cache line
571 : // seq-depth cycle
572 : FD_COMPILER_MFENCE();
573 : ... update the actual cache line body without changing mcache_line->seq ...
574 : FD_COMPILER_MFENCE();
575 : mcache_line->seq = seq; // atomically marks metadata for frag seq as available for consumers
576 : FD_COMPILER_MFENCE();
577 :
578 : Note that above writes can be SSE accelerated on AVX platforms (where
579 : aligned SSE writes are guaranteed to be atomic) as:
580 :
581 : FD_COMPILER_MFENCE();
582 : _mm_store_si128( &mcache_line->sse0, fd_frag_meta_sse0( fd_seq_dec( seq, 1UL ), sig );
583 : FD_COMPILER_MFENCE();
584 : _mm_store_si128( &mcache_line->sse1, fd_frag_meta_sse1( chunk, sz, ctl, tsorig, tspub );
585 : FD_COMPILER_MFENCE();
586 : mcache_line->seq = seq;
587 : FD_COMPILER_MFENCE();
588 :
589 : Note that the above uses no expensive atomic operations or hardware
590 : memory fences under the hood as these are not required for x86-style
591 : cache coherency. Specifically, Intel Architecture Software Developer
592 : Manual 3A-8-9:
593 :
594 : "Reads are not reordered with other reads."
595 :
596 : and 3A-8-10:
597 :
598 : "Writes by a single processor are observed in the same order by all
599 : processors."
600 :
601 : This makes heavy use of compiler memory fences though to insure that
602 : compiler optimizations do not reorder how the operations are issued
603 : to CPUs (and thus also imply the operation acts as a compiler memory
604 : fence overall).
605 :
606 : Non-x86 platforms that use different cache coherency models may
607 : require modification of the below to use more explicit fencing or
608 : what not.
609 :
610 : The below is implemented as a macro to facilitate use in ultra high
611 : performance run loops and support multiple return values. This macro
612 : is robust (e.g. it evaluates its argument a minimal number of times). */
613 :
614 0 : #define FD_MCACHE_WAIT( meta, mline, seq_found, seq_diff, poll_max, mcache, depth, seq_expected ) do { \
615 0 : ulong _fd_mcache_wait_seq_expected = (seq_expected); \
616 0 : fd_frag_meta_t const * _fd_mcache_wait_mline = (mcache) \
617 0 : + fd_mcache_line_idx( _fd_mcache_wait_seq_expected, (depth) ); \
618 0 : fd_frag_meta_t * _fd_mcache_wait_meta = (meta); \
619 0 : ulong _fd_mcache_wait_seq_found; \
620 0 : long _fd_mcache_wait_seq_diff; \
621 0 : ulong _fd_mcache_wait_poll_max = (poll_max); \
622 0 : for(;;) { \
623 0 : _fd_mcache_wait_seq_found = __atomic_load_n( &_fd_mcache_wait_mline->seq, __ATOMIC_ACQUIRE ); \
624 0 : *_fd_mcache_wait_meta = *_fd_mcache_wait_mline; /* probably non-atomic, typically fast L1 cache hit */ \
625 0 : FD_HW_MFENCE_LD(); \
626 0 : ulong _fd_mcache_wait_seq_test = __atomic_load_n( &_fd_mcache_wait_mline->seq, __ATOMIC_RELAXED ); \
627 0 : _fd_mcache_wait_seq_diff = fd_seq_diff( _fd_mcache_wait_seq_found, _fd_mcache_wait_seq_expected ); \
628 0 : int _fd_mcache_wait_done = ((_fd_mcache_wait_seq_found==_fd_mcache_wait_seq_test) & (_fd_mcache_wait_seq_diff>=0L)) \
629 0 : | (!--_fd_mcache_wait_poll_max); \
630 0 : FD_COMPILER_FORGET( _fd_mcache_wait_done ); /* inhibit compiler from turning this into branch nest */ \
631 0 : if( FD_LIKELY( _fd_mcache_wait_done ) ) break; /* opt for exit, single exit to help spin_pause cpu hinting */ \
632 0 : FD_SPIN_PAUSE(); \
633 0 : } \
634 0 : (mline) = _fd_mcache_wait_mline; \
635 0 : (seq_found) = _fd_mcache_wait_seq_found; \
636 0 : (seq_diff) = _fd_mcache_wait_seq_diff; \
637 0 : (poll_max) = _fd_mcache_wait_poll_max; \
638 0 : } while(0)
639 :
640 : /* FD_MCACHE_WAIT_REG: similar to FD_MCACHE_WAIT but uses (nominally)
641 : registers to hold the metadata instead of a local buffer. */
642 :
643 : #define FD_MCACHE_WAIT_REG( _sig, _chunk, _sz, _ctl, _tsorig, _tspub, mline, seq_found, seq_diff, poll_max, \
644 0 : mcache, depth, seq_expected ) do { \
645 0 : ulong _fd_mcache_wait_seq_expected = (seq_expected); \
646 0 : fd_frag_meta_t const * _fd_mcache_wait_mline = (mcache) \
647 0 : + fd_mcache_line_idx( _fd_mcache_wait_seq_expected, (depth) ); \
648 0 : ulong _fd_mcache_wait_poll_max = (poll_max); \
649 0 : ulong _fd_mcache_wait_sig; \
650 0 : ulong _fd_mcache_wait_chunk; \
651 0 : ulong _fd_mcache_wait_sz; \
652 0 : ulong _fd_mcache_wait_ctl; \
653 0 : ulong _fd_mcache_wait_tsorig; \
654 0 : ulong _fd_mcache_wait_tspub; \
655 0 : ulong _fd_mcache_wait_seq_found; \
656 0 : long _fd_mcache_wait_seq_diff; \
657 0 : for(;;) { \
658 0 : _fd_mcache_wait_seq_found = __atomic_load_n( &_fd_mcache_wait_mline->seq, __ATOMIC_ACQUIRE ); \
659 0 : _fd_mcache_wait_sig = _fd_mcache_wait_mline->sig; \
660 0 : _fd_mcache_wait_chunk = (ulong)_fd_mcache_wait_mline->chunk; \
661 0 : _fd_mcache_wait_sz = (ulong)_fd_mcache_wait_mline->sz; \
662 0 : _fd_mcache_wait_ctl = (ulong)_fd_mcache_wait_mline->ctl; \
663 0 : _fd_mcache_wait_tsorig = (ulong)_fd_mcache_wait_mline->tsorig; \
664 0 : _fd_mcache_wait_tspub = (ulong)_fd_mcache_wait_mline->tspub; \
665 0 : FD_HW_MFENCE_LD(); \
666 0 : ulong _fd_mcache_wait_seq_test = __atomic_load_n( &_fd_mcache_wait_mline->seq, __ATOMIC_RELAXED ); \
667 0 : _fd_mcache_wait_seq_diff = fd_seq_diff( _fd_mcache_wait_seq_found, _fd_mcache_wait_seq_expected ); \
668 0 : int _fd_mcache_wait_done = ((_fd_mcache_wait_seq_found==_fd_mcache_wait_seq_test) & (_fd_mcache_wait_seq_diff>=0L)) \
669 0 : | (!--_fd_mcache_wait_poll_max); \
670 0 : FD_COMPILER_FORGET( _fd_mcache_wait_done ); /* inhibit compiler from turning this into branch nest */ \
671 0 : if( FD_LIKELY( _fd_mcache_wait_done ) ) break; /* opt for exit, single exit to help spin_pause cpu hinting */ \
672 0 : FD_SPIN_PAUSE(); \
673 0 : } \
674 0 : (_sig) = _fd_mcache_wait_sig; \
675 0 : (_chunk) = _fd_mcache_wait_chunk; \
676 0 : (_sz) = _fd_mcache_wait_sz; \
677 0 : (_ctl) = _fd_mcache_wait_ctl; \
678 0 : (_tsorig) = _fd_mcache_wait_tsorig; \
679 0 : (_tspub) = _fd_mcache_wait_tspub; \
680 0 : (mline) = _fd_mcache_wait_mline; \
681 0 : (seq_found) = _fd_mcache_wait_seq_found; \
682 0 : (seq_diff) = _fd_mcache_wait_seq_diff; \
683 0 : (poll_max) = _fd_mcache_wait_poll_max; \
684 0 : } while(0)
685 :
686 : #if FD_HAS_AVX
687 :
688 : /* FD_MCACHE_WAIT_SSE: similar to FD_MCACHE_WAIT but uses a pair of SSE
689 : registers to hold the metadata instead of a local buffer. This is
690 : only valid on targets with the FD_HAS_AVX capability (see
691 : fd_tango_base.h for details on Intel's atomicity guarantees). */
692 :
693 : #define FD_MCACHE_WAIT_SSE( meta_sse0, meta_sse1, mline, seq_found, seq_diff, poll_max, mcache, depth, seq_expected ) do { \
694 : ulong _fd_mcache_wait_seq_expected = (seq_expected); \
695 : fd_frag_meta_t const * _fd_mcache_wait_mline = (mcache) \
696 : + fd_mcache_line_idx( _fd_mcache_wait_seq_expected, (depth) ); \
697 : __m128i _fd_mcache_wait_meta_sse0; \
698 : __m128i _fd_mcache_wait_meta_sse1; \
699 : ulong _fd_mcache_wait_seq_found; \
700 : long _fd_mcache_wait_seq_diff; \
701 : ulong _fd_mcache_wait_poll_max = (poll_max); \
702 : for(;;) { \
703 : FD_COMPILER_MFENCE(); \
704 : _fd_mcache_wait_meta_sse0 = _mm_load_si128( &_fd_mcache_wait_mline->sse0 ); /* atomic */ \
705 : FD_COMPILER_MFENCE(); \
706 : _fd_mcache_wait_meta_sse1 = _mm_load_si128( &_fd_mcache_wait_mline->sse1 ); /* atomic, typ fast L1 hit */ \
707 : FD_COMPILER_MFENCE(); \
708 : ulong _fd_mcache_wait_seq_test = _fd_mcache_wait_mline->seq; /* atomic, typically fast L1 cache hit */ \
709 : FD_COMPILER_MFENCE(); \
710 : _fd_mcache_wait_seq_found = fd_frag_meta_sse0_seq( _fd_mcache_wait_meta_sse0 ); \
711 : _fd_mcache_wait_seq_diff = fd_seq_diff( _fd_mcache_wait_seq_found, _fd_mcache_wait_seq_expected ); \
712 : int _fd_mcache_wait_done = ((_fd_mcache_wait_seq_found==_fd_mcache_wait_seq_test) & (_fd_mcache_wait_seq_diff>=0L)) \
713 : | (!--_fd_mcache_wait_poll_max); \
714 : FD_COMPILER_FORGET( _fd_mcache_wait_done ); /* inhibit compiler from turning this into branch nest */ \
715 : if( FD_LIKELY( _fd_mcache_wait_done ) ) break; /* opt for exit, single exit to help spin_pause cpu hinting */ \
716 : FD_SPIN_PAUSE(); \
717 : } \
718 : (meta_sse0) = _fd_mcache_wait_meta_sse0; \
719 : (meta_sse1) = _fd_mcache_wait_meta_sse1; \
720 : (mline) = _fd_mcache_wait_mline; \
721 : (seq_found) = _fd_mcache_wait_seq_found; \
722 : (seq_diff) = _fd_mcache_wait_seq_diff; \
723 : (poll_max) = _fd_mcache_wait_poll_max; \
724 : } while(0)
725 :
726 : /* FD_MCACHE_WAIT_AVX: similar to FD_MCACHE_WAIT_SSE but uses a single
727 : AVX register to hold the found metadata instead of a local buffer.
728 : This is only valid for targets that have atomic AVX load / stores
729 : (not guaranteed across all AVX supporting CPUs and Intel is
730 : deliberately vague about which ones do have it) and a producer that
731 : similarly uses atomic AVX writes for metadata publication. On the
732 : overrun case here, meta_avx will in fact be the metadata for the
733 : overrun sequence number. */
734 :
735 : #define FD_MCACHE_WAIT_AVX( meta_avx, mline, seq_found, seq_diff, poll_max, mcache, depth, seq_expected ) do { \
736 : ulong _fd_mcache_wait_seq_expected = (seq_expected); \
737 : fd_frag_meta_t const * _fd_mcache_wait_mline = (mcache) \
738 : + fd_mcache_line_idx( _fd_mcache_wait_seq_expected, (depth) ); \
739 : fd_frag_meta_v256_t _fd_mcache_wait_meta_avx; \
740 : ulong _fd_mcache_wait_seq_found; \
741 : long _fd_mcache_wait_seq_diff; \
742 : ulong _fd_mcache_wait_poll_max = (poll_max); \
743 : for(;;) { \
744 : FD_COMPILER_MFENCE(); \
745 : _fd_mcache_wait_meta_avx = FD_VOLATILE_CONST( _fd_mcache_wait_mline->avx ); /* atomic (aligned 32B load) */ \
746 : FD_COMPILER_MFENCE(); \
747 : _fd_mcache_wait_seq_found = fd_frag_meta_avx_seq( _fd_mcache_wait_meta_avx ); \
748 : _fd_mcache_wait_seq_diff = fd_seq_diff( _fd_mcache_wait_seq_found, _fd_mcache_wait_seq_expected ); \
749 : int _fd_mcache_wait_done = (_fd_mcache_wait_seq_diff>=0L) | (!--_fd_mcache_wait_poll_max); \
750 : FD_COMPILER_FORGET( _fd_mcache_wait_done ); /* inhibit compiler from turning this into branch nest */ \
751 : if( FD_LIKELY( _fd_mcache_wait_done ) ) break; /* opt for exit, single exit to help spin_pause cpu hinting */ \
752 : FD_SPIN_PAUSE(); \
753 : } \
754 : (meta_avx) = _fd_mcache_wait_meta_avx; \
755 : (mline) = _fd_mcache_wait_mline; \
756 : (seq_found) = _fd_mcache_wait_seq_found; \
757 : (seq_diff) = _fd_mcache_wait_seq_diff; \
758 : (poll_max) = _fd_mcache_wait_poll_max; \
759 : } while(0)
760 :
761 : #endif
762 :
763 : /* fd_mcache_query returns seq_query if seq_query is still in the mcache
764 : (assumed to be a current local mcache join) with depth entries (depth
765 : is assumed to be an integer power of two of at least
766 : FD_MCACHE_BLOCK). It will return a sequence number before seq_query
767 : if the seq_query has not yet been published. It will return a
768 : sequence after seq_query if seq_query is no longer available in the
769 : mcache. In this last case, seq_query will be typically be within
770 : depth of the most recently published sequence number as of some point
771 : in time between when the call was made and the call returned (in many
772 : common uses, this is typically very very close to most recently
773 : published sequence number). This acts as a compiler memory fence. */
774 :
775 : static inline ulong
776 : fd_mcache_query( fd_frag_meta_t const * mcache,
777 : ulong depth,
778 0 : ulong seq_query ) {
779 0 : return fd_frag_meta_seq_query( mcache + fd_mcache_line_idx( seq_query, depth ) );
780 0 : }
781 :
782 : FD_PROTOTYPES_END
783 :
784 : #endif /* HEADER_fd_src_tango_mcache_fd_mcache_h */
|
