Line data Source code
1 : #ifndef HEADER_fd_src_tango_fd_tango_base_h
2 : #define HEADER_fd_src_tango_fd_tango_base_h
3 :
4 : /* Tango messaging concepts:
5 :
6 : - Each message comes from a single local origin. Each origin has a
7 : 13-bit id that uniquely identifies it within a set of message
8 : producers and consumers for the lifetime of the set. Origins
9 : typically include a mixture of network receiving devices, local
10 : message publishers, etc. Applications might restrict the set of
11 : origins / add additional context / structure to origins id as
12 : need.
13 :
14 : - Messages are partitioned into one or more disjoint fragments. The
15 : number of message payload bytes in a message fragment is in
16 : [0,2^16). That is, message fragment size is any 16-bit unsigned
17 : int (thus bounded and variable). Zero sized fragments are
18 : legitimate (e.g. one use case for this is heartbeating a stalled
19 : send of a large multi-fragment message). Note that this is large
20 : enough to allow a maximum size UDP payload to be published in a
21 : single message fragment. Applications might choose to impose
22 : additional limitations on message fragmentation.
23 :
24 : - Each fragment has a 64-bit sequence number that is unique over a
25 : (potentially dynamic) set of communicating message producers and
26 : consumers for the lifetime of that set. Note that the use of a
27 : 64-bit sequence number means that sequence number reuse is not an
28 : issue practically (would take hundreds of years even at highly
29 : local unrealistic messaging rates from producers to consumers).
30 : Note also that it is possible to use a smaller sequence number and
31 : deal with the implications of sequence number reuse via a number of
32 : standard techniques (epochs, TCP timestamp style, etc ... possibly
33 : with some minor additional constraints). This is not done here for
34 : code simplicity / robustness / flexibility.
35 :
36 : - Message fragment sequence numbers increase sequentially with no
37 : gaps over the set of all producers for the set's lifetime. As
38 : such, if a consumer encounters a gap in fragment sequence numbers,
39 : it knows it was overrun and has lost a message fragment (but
40 : typically that consumer does not know the origin of the lost
41 : fragment and needs to react accordingly).
42 :
43 : - The message fragment sequence numbers increase monotonically but
44 : not necessarily sequentially as the fragments from messages from
45 : different origins may be interleaved in fragment sequence number.
46 :
47 : - Each fragment is timestamped accordingly to when its origin first
48 : started producing it (tsorig) and when it was made first available
49 : for consumers (tspub). As these are used mostly for monitoring and
50 : diagnostic purposes, they are stored in a temporally and/or
51 : precision compressed representation to free up room for other
52 : metadata.
53 :
54 : - tsorig is measured on the origin's wallclock and the tspub is
55 : measured on the consumer facing publisher's wallclock (these are
56 : often the same wallclock). As such, tsorig from the same origin
57 : will be monotonically increasing and tspub will be monotonically
58 : increasing across all fragments from all origins.
59 :
60 : - The wallclocks used for the timestamping should be reasonably well
61 : synchronized in the sense described in util/log. As such
62 : timestamps measured by the same wallclocks will be exactly
63 : spatially comparable and approximately temporally comparable and
64 : timestamps measured by different wallclocks are both approximately
65 : spatially and temporally comparable. Applications might chose to
66 : use things like preexisting host globally synchronized hardware
67 : tickcounters (e.g. RDTSC) for these instead of the system wallclock
68 : to reduce overheads.
69 :
70 : - Message fragments are distributed strictly in order. There is no
71 : inherent limit to the number of fragments in a message.
72 : Applications might impose additional restrictions as appropriate
73 : for their needs.
74 :
75 : - To facilitate message reassembly, each fragment has a set of
76 : control bits that specify message boundaries and other conditions
77 : that might occur during message distribution.
78 :
79 : * SOM ("start-of-message"): This indicates this fragment starts a
80 : message from the fragment's origin.
81 :
82 : * EOM ("end-of-message"): This indicates this fragment ends a
83 : message from the fragment's origin. If a consumer sees all the
84 : fragment sequence numbers between the sequence number of an SOM
85 : fragment from an origin to the sequence number of an EOM fragment
86 : from that origin inclusive, it knows that it has received all
87 : fragments for that message without loss from that origin.
88 :
89 : * ERR ("error"): This indicates that the _entire_ message to which
90 : the fragment belongs should be considered as corrupt (e.g. CRC
91 : checks that happen at the very end of network packet reception
92 : are the typical reason for this and these inherent cannot be
93 : checked until the last fragment).
94 :
95 : - To facilitate high performance message distribution, each fragment
96 : has a 64-bit message signature. How the signature is used is
97 : application defined. A typical use case is to have the first
98 : fragment of a message signify (in an application dependent way)
99 : which consumers are definitely known a priori to be uninterested in
100 : the message (such that those consumer doesn't have to spend any
101 : bandwidth or compute to reassemble or parse message payloads while
102 : still preserving common sequencing and ordering of all messages
103 : between all consumers).
104 :
105 : - For similar reasons, recent message fragments are typically stored
106 : in two separate caches: A fragment metadata cache ("mcache", which
107 : behaves like a hybrid of a ring and a direct mapped cache ... it
108 : maps recently published fragment sequence numbers to fragment
109 : metadata) and a fragment payload cache (which is more flexibly
110 : allocated at "chunk" granularity as per the capabilities and needs
111 : of the individual origins). */
112 :
113 : #include "../util/fd_util.h"
114 :
115 : #if FD_HAS_SSE /* also covers FD_HAS_AVX */
116 : #include <smmintrin.h>
117 : #endif
118 :
119 : #if FD_HAS_AVX
120 : /* Layout compatible with __m256i without pulling in all of immintrin.h */
121 : typedef long long fd_frag_meta_v256_t __attribute__((__vector_size__(32),__may_alias__));
122 : #endif
123 :
124 : /* FD_CHUNK_{LG_SZ,ALIGN,FOOTPRINT,SZ} describe the granularity of
125 : message fragment payload allocations. ALIGN==FOOTPRINT==SZ==2^LG_SZ
126 : and recommend this to be something like a cache line practically. */
127 :
128 215785 : #define FD_CHUNK_LG_SZ (6)
129 0 : #define FD_CHUNK_ALIGN (64UL) /* == 2^FD_CHUNK_LG_SZ, explicit to workaround compiler limitations */
130 0 : #define FD_CHUNK_FOOTPRINT (64UL) /* " */
131 72130 : #define FD_CHUNK_SZ (64UL) /* " */
132 :
133 : /* FD_CHUNK_{LG_SZ,ALIGN,FOOTPRINT,SZ} describe the coarse layout of
134 : message fragment structures.
135 : sizeof(fd_frag_meta_t)==ALIGN==FOOTPRINT==SZ==2^LG_SZ. Recommend
136 : this to be something like a positive integer multiple or an integer
137 : power of two divisor of a cache line size. */
138 :
139 : #define FD_FRAG_META_LG_SZ (5)
140 : #define FD_FRAG_META_ALIGN (32UL) /* == 2^FD_FRAG_META_LG_SZ, explicit to workaround compiler limitations */
141 : #define FD_FRAG_META_FOOTPRINT (32UL) /* " */
142 : #define FD_FRAG_META_SZ (32UL) /* " */
143 :
144 : /* FD_FRAG_META_ORIG_MAX specifies the maximum number of message origins
145 : that are supported. Origins ids are in [0,FD_FRAG_META_ORIG_MAX). */
146 :
147 : #define FD_FRAG_META_ORIG_MAX (8192UL)
148 :
149 : /* fd_frag_meta_t specifies the message fragment metadata. */
150 :
151 : union __attribute__((aligned(FD_FRAG_META_ALIGN))) fd_frag_meta {
152 :
153 : struct {
154 :
155 : /* First aligned SSE word ... these are strictly updated atomically */
156 :
157 : ulong seq; /* naturally atomic r/w, frag sequence number. */
158 : ulong sig; /* naturally atomic r/w, application defined message signature for fast consumer side filtering
159 : performance is best if this is updated atomically with seq */
160 :
161 : /* Second aligned SSE word ... these are typically updated
162 : atomically but there is no guarantee both SSE words are jointly
163 : updated atomically. */
164 :
165 : uint chunk; /* naturally atomic r/w, compressed relative location of first byte of the frag in data region. */
166 : ushort sz; /* naturally atomic r/w, Frag size in bytes. */
167 : ushort ctl; /* naturally atomic r/w, Message reassembly control bits (origin/clock domain, SOM/EOM/ERR flags) */
168 : uint tsorig; /* naturally atomic r/w, Message diagnostic compressed timestamps */
169 : uint tspub; /* naturally atomic r/w, " */
170 :
171 : };
172 :
173 :
174 : /* Intel architecture manual 3A section 8.1.1 (April 2022):
175 :
176 : Processors that enumerate support for Intel AVX (by setting the
177 : feature flag CPUID.01H:ECX.AVX[bit 28]) guarantee that the
178 : 16-byte memory operations performed by the following instructions
179 : will always be carried out atomically:
180 :
181 : - MOVAPD, MOVAPS, and MOVDQA.
182 : - VMOVAPD, VMOVAPS, and VMOVDQA when encoded with VEX.128.
183 : - VMOVAPD, VMOVAPS, VMOVDQA32, and VMOVDQA64 when encoded with
184 : EVEX.128 and k0 (masking disabled).
185 :
186 : (Note that these instructions require the linear addresses of
187 : their memory operands to be 16-byte aligned.)
188 :
189 : That is accesses to "sse0" and "sse1" below are atomic when AVX
190 : support is available given the overall structure alignment,
191 : appropriate intrinsics and what not. Accesses to avx are likely
192 : atomic on many x86 platforms but this is not guaranteed and such
193 : should not be assumed. */
194 :
195 : # if FD_HAS_SSE
196 : struct {
197 : __m128i sse0; /* naturally atomic r/w, covers seq and sig */
198 : __m128i sse1; /* naturally atomic r/w, covers chunk, sz, ctl, tsorig and tspub */
199 : };
200 : # endif
201 :
202 : # if FD_HAS_AVX
203 : fd_frag_meta_v256_t avx; /* Possibly non-atomic but can hold the metadata in a single register */
204 : # endif
205 :
206 : # if FD_HAS_ARM
207 : ulong ul[4];
208 : # endif
209 :
210 : };
211 :
212 : typedef union fd_frag_meta fd_frag_meta_t;
213 :
214 : FD_PROTOTYPES_BEGIN
215 :
216 : /* fd_seq_{lt,le,eq,ne,ge,gt} compare 64-bit sequence numbers with
217 : proper handling of sequence number wrapping (e.g. if, for example, we
218 : decide to randomize the initial sequence numbers used by an
219 : application for security reasons and by chance pick a sequence number
220 : near 2^64 such that wrapping sequence numbers 0 occurs. That is,
221 : sequence number reuse is not an issue practically in a real world
222 : application but sequence number wrapping is if we want to support
223 : things like initial sequence number randomization for security.
224 :
225 : fd_seq_{inc,dec} returns the result of incrementing/decrementing
226 : sequence number a delta times.
227 :
228 : fd_seq_diff returns the how many sequence numbers a is ahead of b.
229 : Positive/negative values means a is in the future/past of b. Zero
230 : indicates a and b are the same.
231 :
232 : In general operations on sequence numbers are strongly encouraged to
233 : use this macros as such facilitates updating code to accommodate
234 : things like changing the width of a sequence number. */
235 :
236 0 : FD_FN_CONST static inline int fd_seq_lt( ulong a, ulong b ) { return ((long)(a-b))< 0L; }
237 0 : FD_FN_CONST static inline int fd_seq_le( ulong a, ulong b ) { return ((long)(a-b))<=0L; }
238 0 : FD_FN_CONST static inline int fd_seq_eq( ulong a, ulong b ) { return a==b; }
239 0 : FD_FN_CONST static inline int fd_seq_ne( ulong a, ulong b ) { return a!=b; }
240 0 : FD_FN_CONST static inline int fd_seq_ge( ulong a, ulong b ) { return ((long)(a-b))>=0L; }
241 0 : FD_FN_CONST static inline int fd_seq_gt( ulong a, ulong b ) { return ((long)(a-b))> 0L; }
242 :
243 868610 : FD_FN_CONST static inline ulong fd_seq_inc( ulong a, ulong delta ) { return a+delta; }
244 72385 : FD_FN_CONST static inline ulong fd_seq_dec( ulong a, ulong delta ) { return a-delta; }
245 :
246 273735888 : FD_FN_CONST static inline long fd_seq_diff( ulong a, ulong b ) { return (long)(a-b); }
247 :
248 : /* fd_chunk_to_laddr: returns a pointer in the local address space to
249 : the first byte of the chunk with the given compressed relative
250 : address chunk given the pointer in the local address space of the
251 : chunk whose index is 0 (chunk0). fd_chunk_to_laddr_const is for
252 : const-correctness.
253 :
254 : fd_laddr_to_chunk: vice versa. */
255 :
256 : FD_FN_CONST static inline void * /* Will be aligned FD_CHUNK_ALIGN and in [ chunk0, chunk0 + FD_CHUNK_SZ*(UINT_MAX+1) ) */
257 : fd_chunk_to_laddr( void * chunk0, /* Assumed aligned FD_CHUNK_ALIGN */
258 72129 : ulong chunk ) { /* Assumed in [0,UINT_MAX] */
259 72129 : return (void *)(((ulong)chunk0) + (chunk << FD_CHUNK_LG_SZ));
260 72129 : }
261 :
262 : FD_FN_CONST static inline void const *
263 : fd_chunk_to_laddr_const( void const * chunk0,
264 71524 : ulong chunk ) {
265 71524 : return (void const *)(((ulong)chunk0) + (chunk << FD_CHUNK_LG_SZ));
266 71524 : }
267 :
268 : FD_FN_CONST static inline ulong /* Will be in [0,UINT_MAX] */
269 : fd_laddr_to_chunk( void const * chunk0, /* Assumed aligned FD_CHUNK_ALIGN */
270 0 : void const * laddr ) { /* Assumed aligned FD_CHUNK_ALIGN and in [ chunk0, chunk0 + FD_CHUNK_SZ*(UINT_MAX+1) ) */
271 0 : return (((ulong)laddr)-((ulong)chunk0)) >> FD_CHUNK_LG_SZ;
272 0 : }
273 :
274 : /* fd_frag_meta_seq_query returns the sequence number pointed to by meta
275 : as atomically observed at some point of time between when the call
276 : was made and the call returns. Assumes meta is valid. This acts as
277 : a compiler memory fence. */
278 :
279 : static inline ulong
280 256472059 : fd_frag_meta_seq_query( fd_frag_meta_t const * meta ) { /* Assumed non-NULL */
281 256472059 : return __atomic_load_n( &meta->seq, __ATOMIC_ACQUIRE );
282 256472059 : }
283 :
284 : #if FD_HAS_SSE
285 :
286 : /* fd_frag_meta_seq_sig_query returns the sequence number and signature
287 : pointed to by meta in one atomic read, same semantics as
288 : fd_frag_meta_seq_query. */
289 : static inline __m128i
290 0 : fd_frag_meta_seq_sig_query( fd_frag_meta_t const * meta ) { /* Assumed non-NULL */
291 0 : FD_COMPILER_MFENCE();
292 0 : __m128i sse0 = FD_VOLATILE_CONST( meta->sse0 );
293 0 : FD_COMPILER_MFENCE();
294 0 : return sse0;
295 0 : }
296 :
297 : #endif
298 :
299 : /* fd_frag_meta_ctl, fd_frag_meta_ctl_{som,eom,err} pack and unpack the
300 : fd_frag message reassembly control bits. */
301 :
302 : FD_FN_CONST static inline ulong /* In [0,2^16) */
303 : fd_frag_meta_ctl( ulong orig, /* Assumed in [0,FD_FRAG_META_ORIG_MAX) */
304 : int som, /* 0 for false, non-zero for true */
305 : int eom, /* 0 for false, non-zero for true */
306 256 : int err ) { /* 0 for false, non-zero for true */
307 256 : return ((ulong)!!som) | (((ulong)!!eom)<<1) | (((ulong)!!err)<<2) | (orig<<3);
308 256 : }
309 :
310 0 : FD_FN_CONST static inline ulong fd_frag_meta_ctl_orig( ulong ctl ) { return ctl>>3; }
311 0 : FD_FN_CONST static inline int fd_frag_meta_ctl_som ( ulong ctl ) { return (int)( ctl & 1UL); }
312 0 : FD_FN_CONST static inline int fd_frag_meta_ctl_eom ( ulong ctl ) { return (int)((ctl>>1) & 1UL); }
313 0 : FD_FN_CONST static inline int fd_frag_meta_ctl_err ( ulong ctl ) { return (int)((ctl>>2) & 1UL); }
314 :
315 : #if FD_HAS_SSE
316 :
317 : FD_FN_CONST static inline __m128i
318 : fd_frag_meta_sse0( ulong seq,
319 0 : ulong sig ) {
320 0 : return _mm_set_epi64x( (long)sig, (long)seq ); /* Backward Intel ... sigh */
321 0 : }
322 :
323 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse0_seq( __m128i sse0 ) { return (ulong)_mm_extract_epi64( sse0, 0 ); }
324 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse0_sig( __m128i sse0 ) { return (ulong)_mm_extract_epi64( sse0, 1 ); }
325 :
326 : FD_FN_CONST static inline __m128i
327 : fd_frag_meta_sse1( ulong chunk, /* Assumed 32-bit */
328 : ulong sz, /* Assumed 16 bit */
329 : ulong ctl, /* Assumed 16-bit */
330 : ulong tsorig, /* Assumed 32-bit */
331 0 : ulong tspub ) { /* Assumed 32-bit */
332 0 : return _mm_set_epi64x( (long)(tsorig | (tspub<<32)),
333 0 : (long)(chunk | (sz<<32) | (ctl<<48)) ); /* Backward Intel ... sigh */
334 0 : }
335 :
336 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_chunk ( __m128i sse1 ) { return (ulong)(uint )_mm_extract_epi32( sse1, 0 ); }
337 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_sz ( __m128i sse1 ) { return (ulong)(ushort)_mm_extract_epi16( sse1, 2 ); }
338 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_ctl ( __m128i sse1 ) { return (ulong)(ushort)_mm_extract_epi16( sse1, 3 ); }
339 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_tsorig( __m128i sse1 ) { return (ulong)(uint )_mm_extract_epi32( sse1, 2 ); }
340 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_tspub ( __m128i sse1 ) { return (ulong)(uint )_mm_extract_epi32( sse1, 3 ); }
341 :
342 : #endif
343 : #if FD_HAS_AVX
344 :
345 : FD_FN_CONST static inline fd_frag_meta_v256_t
346 : fd_frag_meta_avx( ulong seq,
347 : ulong sig,
348 : ulong chunk, /* Assumed 32-bit */
349 : ulong sz, /* Assumed 16 bit */
350 : ulong ctl, /* Assumed 16-bit */
351 : ulong tsorig, /* Assumed 32-bit */
352 0 : ulong tspub ) { /* Assumed 32-bit */
353 0 : return (fd_frag_meta_v256_t){ (long)seq,
354 0 : (long)sig,
355 0 : (long)(chunk | (sz<<32) | (ctl<<48)),
356 0 : (long)(tsorig | (tspub<<32)) };
357 0 : }
358 :
359 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_seq ( fd_frag_meta_v256_t avx ) { return (ulong) avx[0]; }
360 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_sig ( fd_frag_meta_v256_t avx ) { return (ulong) avx[1]; }
361 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_chunk ( fd_frag_meta_v256_t avx ) { return (ulong)(uint ) avx[2]; }
362 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_sz ( fd_frag_meta_v256_t avx ) { return (ulong)(ushort)(avx[2]>>32); }
363 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_ctl ( fd_frag_meta_v256_t avx ) { return (ulong)(ushort)(avx[2]>>48); }
364 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_tsorig( fd_frag_meta_v256_t avx ) { return (ulong)(uint ) avx[3]; }
365 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_tspub ( fd_frag_meta_v256_t avx ) { return (ulong)(uint )(avx[3]>>32); }
366 :
367 : #endif
368 :
369 : #if FD_HAS_ARM
370 :
371 : FD_FN_CONST static inline ulong
372 : fd_frag_meta_ul2( ulong chunk,
373 : ulong sz,
374 : ulong ctl ) {
375 : return chunk | (sz<<32) | (ctl<<48);
376 : }
377 :
378 : FD_FN_CONST static inline ulong
379 : fd_frag_meta_ul3( ulong tsorig,
380 : ulong tspub ) {
381 : return tsorig | (tspub<<32);
382 : }
383 :
384 : FD_FN_CONST static inline ulong fd_frag_meta_ul2_chunk ( ulong ul2 ) { return (ulong)(uint )( ul2 & 0xFFFFFFFFUL); }
385 : FD_FN_CONST static inline ulong fd_frag_meta_ul2_sz ( ulong ul2 ) { return (ulong)(ushort)((ul2>>32) & 0xFFFFUL); }
386 : FD_FN_CONST static inline ulong fd_frag_meta_ul2_ctl ( ulong ul2 ) { return (ulong)(ushort)((ul2>>48) & 0xFFFFUL); }
387 : FD_FN_CONST static inline ulong fd_frag_meta_ul3_tsorig( ulong ul3 ) { return (ulong)(uint )( ul3 & 0xFFFFFFFFUL); }
388 : FD_FN_CONST static inline ulong fd_frag_meta_ul3_tspub ( ulong ul3 ) { return (ulong)(uint )( ul3>>32 ); }
389 :
390 : #endif /* FD_HAS_ARM */
391 :
392 : /* fd_frag_meta_ts_{comp,decomp}: Given the longs ts and tsref that
393 : are reasonably close to each other (|ts-tsref| < 2^31 ... about
394 : +/-2.1 seconds if ts and tsref are reasonably well synchronized
395 : fd_log_wallclock measurements), this pair of functions can quickly
396 : and losslessly compress / decompress ts by a factor of 2 exactly
397 : using tsref as the compressor / decompressor "state". */
398 :
399 : FD_FN_CONST static inline ulong /* In [0,UINT_MAX] */
400 0 : fd_frag_meta_ts_comp( long ts ) {
401 0 : return (ulong)(uint)ts;
402 0 : }
403 :
404 : FD_FN_CONST static inline long
405 : fd_frag_meta_ts_decomp( ulong tscomp, /* In [0,UINT_MAX] */
406 0 : long tsref ) {
407 0 : ulong msb = ((ulong)tsref) + fd_ulong_mask_lsb(31) - tscomp;
408 0 : return (long)((msb & ~fd_ulong_mask_lsb(32)) | tscomp);
409 0 : }
410 :
411 : FD_PROTOTYPES_END
412 :
413 : #endif /* HEADER_fd_src_tango_fd_tango_base_h */
|
