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 532408242 : #define FD_CHUNK_LG_SZ (6)
129 102 : #define FD_CHUNK_ALIGN (64UL) /* == 2^FD_CHUNK_LG_SZ, explicit to workaround compiler limitations */
130 27 : #define FD_CHUNK_FOOTPRINT (64UL) /* " */
131 30142358 : #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 3076520799 : 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 3073425600 : FD_FN_CONST static inline int fd_seq_eq( ulong a, ulong b ) { return a==b; }
239 9691363136 : FD_FN_CONST static inline int fd_seq_ne( ulong a, ulong b ) { return a!=b; }
240 3000000 : FD_FN_CONST static inline int fd_seq_ge( ulong a, ulong b ) { return ((long)(a-b))>=0L; }
241 3071759514 : FD_FN_CONST static inline int fd_seq_gt( ulong a, ulong b ) { return ((long)(a-b))> 0L; }
242 :
243 15959021750 : FD_FN_CONST static inline ulong fd_seq_inc( ulong a, ulong delta ) { return a+delta; }
244 410188267 : FD_FN_CONST static inline ulong fd_seq_dec( ulong a, ulong delta ) { return a-delta; }
245 :
246 25307281486 : 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 29541494 : ulong chunk ) { /* Assumed in [0,UINT_MAX] */
259 29541494 : return (void *)(((ulong)chunk0) + (chunk << FD_CHUNK_LG_SZ));
260 29541494 : }
261 :
262 : FD_FN_CONST static inline void const *
263 : fd_chunk_to_laddr_const( void const * chunk0,
264 472657769 : ulong chunk ) {
265 472657769 : return (void const *)(((ulong)chunk0) + (chunk << FD_CHUNK_LG_SZ));
266 472657769 : }
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 65841 : void const * laddr ) { /* Assumed aligned FD_CHUNK_ALIGN and in [ chunk0, chunk0 + FD_CHUNK_SZ*(UINT_MAX+1) ) */
271 65841 : return (((ulong)laddr)-((ulong)chunk0)) >> FD_CHUNK_LG_SZ;
272 65841 : }
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 481657664 : fd_frag_meta_seq_query( fd_frag_meta_t const * meta ) { /* Assumed non-NULL */
281 481657664 : FD_COMPILER_MFENCE();
282 481657664 : ulong seq = FD_VOLATILE_CONST( meta->seq );
283 481657664 : FD_COMPILER_MFENCE();
284 481657664 : return seq;
285 481657664 : }
286 :
287 : #if FD_HAS_SSE
288 :
289 : /* fd_frag_meta_seq_sig_query returns the sequence number and signature
290 : pointed to by meta in one atomic read, same semantics as
291 : fd_frag_meta_seq_query. */
292 : static inline __m128i
293 0 : fd_frag_meta_seq_sig_query( fd_frag_meta_t const * meta ) { /* Assumed non-NULL */
294 0 : FD_COMPILER_MFENCE();
295 0 : __m128i sse0 = FD_VOLATILE_CONST( meta->sse0 );
296 0 : FD_COMPILER_MFENCE();
297 0 : return sse0;
298 0 : }
299 :
300 : #endif
301 :
302 : /* fd_frag_meta_ctl, fd_frag_meta_ctl_{som,eom,err} pack and unpack the
303 : fd_frag message reassembly control bits. */
304 :
305 : FD_FN_CONST static inline ulong /* In [0,2^16) */
306 : fd_frag_meta_ctl( ulong orig, /* Assumed in [0,FD_FRAG_META_ORIG_MAX) */
307 : int som, /* 0 for false, non-zero for true */
308 : int eom, /* 0 for false, non-zero for true */
309 396751312 : int err ) { /* 0 for false, non-zero for true */
310 396751312 : return ((ulong)!!som) | (((ulong)!!eom)<<1) | (((ulong)!!err)<<2) | (orig<<3);
311 396751312 : }
312 :
313 0 : FD_FN_CONST static inline ulong fd_frag_meta_ctl_orig( ulong ctl ) { return ctl>>3; }
314 3000000 : FD_FN_CONST static inline int fd_frag_meta_ctl_som ( ulong ctl ) { return (int)( ctl & 1UL); }
315 3000000 : FD_FN_CONST static inline int fd_frag_meta_ctl_eom ( ulong ctl ) { return (int)((ctl>>1) & 1UL); }
316 3000000 : FD_FN_CONST static inline int fd_frag_meta_ctl_err ( ulong ctl ) { return (int)((ctl>>2) & 1UL); }
317 :
318 : #if FD_HAS_SSE
319 :
320 : FD_FN_CONST static inline __m128i
321 : fd_frag_meta_sse0( ulong seq,
322 15 : ulong sig ) {
323 15 : return _mm_set_epi64x( (long)sig, (long)seq ); /* Backward Intel ... sigh */
324 15 : }
325 :
326 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse0_seq( __m128i sse0 ) { return (ulong)_mm_extract_epi64( sse0, 0 ); }
327 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse0_sig( __m128i sse0 ) { return (ulong)_mm_extract_epi64( sse0, 1 ); }
328 :
329 : FD_FN_CONST static inline __m128i
330 : fd_frag_meta_sse1( ulong chunk, /* Assumed 32-bit */
331 : ulong sz, /* Assumed 16 bit */
332 : ulong ctl, /* Assumed 16-bit */
333 : ulong tsorig, /* Assumed 32-bit */
334 15 : ulong tspub ) { /* Assumed 32-bit */
335 15 : return _mm_set_epi64x( (long)(tsorig | (tspub<<32)),
336 15 : (long)(chunk | (sz<<32) | (ctl<<48)) ); /* Backward Intel ... sigh */
337 15 : }
338 :
339 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_chunk ( __m128i sse1 ) { return (ulong)(uint )_mm_extract_epi32( sse1, 0 ); }
340 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_sz ( __m128i sse1 ) { return (ulong)(ushort)_mm_extract_epi16( sse1, 2 ); }
341 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_ctl ( __m128i sse1 ) { return (ulong)(ushort)_mm_extract_epi16( sse1, 3 ); }
342 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_tsorig( __m128i sse1 ) { return (ulong)(uint )_mm_extract_epi32( sse1, 2 ); }
343 0 : FD_FN_CONST static inline ulong fd_frag_meta_sse1_tspub ( __m128i sse1 ) { return (ulong)(uint )_mm_extract_epi32( sse1, 3 ); }
344 :
345 : #endif
346 : #if FD_HAS_AVX
347 :
348 : FD_FN_CONST static inline fd_frag_meta_v256_t
349 : fd_frag_meta_avx( ulong seq,
350 : ulong sig,
351 : ulong chunk, /* Assumed 32-bit */
352 : ulong sz, /* Assumed 16 bit */
353 : ulong ctl, /* Assumed 16-bit */
354 : ulong tsorig, /* Assumed 32-bit */
355 65922 : ulong tspub ) { /* Assumed 32-bit */
356 65922 : return (fd_frag_meta_v256_t){ (long)seq,
357 65922 : (long)sig,
358 65922 : (long)(chunk | (sz<<32) | (ctl<<48)),
359 65922 : (long)(tsorig | (tspub<<32)) };
360 65922 : }
361 :
362 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_seq ( fd_frag_meta_v256_t avx ) { return (ulong) avx[0]; }
363 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_sig ( fd_frag_meta_v256_t avx ) { return (ulong) avx[1]; }
364 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_chunk ( fd_frag_meta_v256_t avx ) { return (ulong)(uint ) avx[2]; }
365 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_sz ( fd_frag_meta_v256_t avx ) { return (ulong)(ushort)(avx[2]>>32); }
366 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_ctl ( fd_frag_meta_v256_t avx ) { return (ulong)(ushort)(avx[2]>>48); }
367 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_tsorig( fd_frag_meta_v256_t avx ) { return (ulong)(uint ) avx[3]; }
368 0 : FD_FN_CONST static inline ulong fd_frag_meta_avx_tspub ( fd_frag_meta_v256_t avx ) { return (ulong)(uint )(avx[3]>>32); }
369 :
370 : #endif
371 :
372 : #if FD_HAS_ARM
373 :
374 : FD_FN_CONST static inline ulong
375 : fd_frag_meta_ul2( ulong chunk,
376 : ulong sz,
377 : ulong ctl ) {
378 : return chunk | (sz<<32) | (ctl<<48);
379 : }
380 :
381 : FD_FN_CONST static inline ulong
382 : fd_frag_meta_ul3( ulong tsorig,
383 : ulong tspub ) {
384 : return tsorig | (tspub<<32);
385 : }
386 :
387 : FD_FN_CONST static inline ulong fd_frag_meta_ul2_chunk ( ulong ul2 ) { return (ulong)(uint )( ul2 & 0xFFFFFFFFUL); }
388 : FD_FN_CONST static inline ulong fd_frag_meta_ul2_sz ( ulong ul2 ) { return (ulong)(ushort)((ul2>>32) & 0xFFFFUL); }
389 : FD_FN_CONST static inline ulong fd_frag_meta_ul2_ctl ( ulong ul2 ) { return (ulong)(ushort)((ul2>>48) & 0xFFFFUL); }
390 : FD_FN_CONST static inline ulong fd_frag_meta_ul3_tsorig( ulong ul3 ) { return (ulong)(uint )( ul3 & 0xFFFFFFFFUL); }
391 : FD_FN_CONST static inline ulong fd_frag_meta_ul3_tspub ( ulong ul3 ) { return (ulong)(uint )( ul3>>32 ); }
392 :
393 : #endif /* FD_HAS_ARM */
394 :
395 : /* fd_frag_meta_ts_{comp,decomp}: Given the longs ts and tsref that
396 : are reasonably close to each other (|ts-tsref| < 2^31 ... about
397 : +/-2.1 seconds if ts and tsref are reasonably well synchronized
398 : fd_log_wallclock measurements), this pair of functions can quickly
399 : and losslessly compress / decompress ts by a factor of 2 exactly
400 : using tsref as the compressor / decompressor "state". */
401 :
402 : FD_FN_CONST static inline ulong /* In [0,UINT_MAX] */
403 415383203 : fd_frag_meta_ts_comp( long ts ) {
404 415383203 : return (ulong)(uint)ts;
405 415383203 : }
406 :
407 : FD_FN_CONST static inline long
408 : fd_frag_meta_ts_decomp( ulong tscomp, /* In [0,UINT_MAX] */
409 0 : long tsref ) {
410 0 : ulong msb = ((ulong)tsref) + fd_ulong_mask_lsb(31) - tscomp;
411 0 : return (long)((msb & ~fd_ulong_mask_lsb(32)) | tscomp);
412 0 : }
413 :
414 : FD_PROTOTYPES_END
415 :
416 : #endif /* HEADER_fd_src_tango_fd_tango_base_h */
417 :
|
