Line data Source code
1 : #ifndef HEADER_fd_src_discof_repair_fd_inflight_h
2 : #define HEADER_fd_src_discof_repair_fd_inflight_h
3 :
4 : #include "fd_policy.h"
5 : #include "../../ballet/shred/fd_shred.h"
6 :
7 : /* fd_inflight tracks repair requests that are inflight to other
8 : validators, so that a response can be credited to the request (and
9 : peer) that solicited it and a request that gets no response can be
10 : redispatched after a timeout. Request kinds:
11 :
12 : - Shred requests -- positional FD_REPAIR_KIND_SHRED and Alpenglow
13 : ShredForBlockId, which are indistinguishable on response -- are
14 : keyed by (slot, shred_idx, nonce, kind, fec_root). fec_root is
15 : all zero for a positional request (i.e., we didnt know the FEC
16 : root when the request was issued). For a ShredForBlockId request,
17 : it is the 20-byte prefix of the known FEC root.
18 :
19 : - Metadata requests -- getParentAndFecSetCount and getFecSetRoot --
20 : are matched by nonce alone. Their kind, slot and FEC set index
21 : ride in the key for redispatch (and so the caller can reject a
22 : response of the wrong kind) but do not participate in matching.
23 :
24 : Exact updates of shred requests are critical: the repair policy does
25 : not request any shred twice, so re-requests come only from this
26 : table. Whether a shred belongs to a version is decided structurally
27 : by the rotor, which keys FECs by root; this table is request
28 : accounting only.
29 :
30 : Each record is FREE, OUTSTANDING, or POPPED:
31 :
32 : insert pop
33 : FREE --------> OUTSTANDING -----------> POPPED
34 : ^ | |
35 : | match | match, or evicted |
36 : -------------------------------------------
37 :
38 : OUTSTANDING records are in map and outstanding_dl (insertion order,
39 : oldest at head). A record that ages past FD_REQLIM_DEDUP_TIMEOUT is
40 : popped: the caller redispatches it under a fresh nonce and the record
41 : moves to popped_map / popped_dl rather than being released, so a late
42 : response to the old nonce still matches. When the pool is exhausted
43 : the oldest POPPED record is evicted first. A caller that does not
44 : redispatch from the table releases aged records with
45 : fd_inflights_expire instead of popping them. */
46 :
47 : /* Max number of pending requests */
48 0 : #define FD_INFLIGHT_REQ_MAX (1<<20)
49 :
50 : struct fd_inflight_key {
51 : ulong slot;
52 : uint idx; /* shred idx (shred kinds) or fec_set_idx (AG_REPAIR_KIND_FEC_ROOT) */
53 : uint nonce; /* rnonce or counter nonce (metadata) */
54 : uint kind; /* FD_REPAIR_KIND_SHRED, AG_REPAIR_KIND_SHRED_FOR_BLOCK_ID, AG_REPAIR_KIND_PARENT_FEC_COUNT or AG_REPAIR_KIND_FEC_ROOT */
55 : /* shred kinds: first FD_SHRED_MERKLE_NODE_SZ bytes of the FEC root a
56 : ShredForBlockId request was issued against, all-zero for a
57 : positional request. All-zero for metadata kinds. */
58 : uchar fec_root[ FD_SHRED_MERKLE_NODE_SZ ];
59 : };
60 : typedef struct fd_inflight_key fd_inflight_key_t;
61 : FD_STATIC_ASSERT( sizeof(fd_inflight_key_t)==40UL, fd_inflight_key_sz );
62 :
63 : /* fd_inflight_key_init fills key. For shred requests fec_root is the
64 : (full or 20-byte-padded) FEC root the request targets, or NULL for a
65 : positional request; only the first FD_SHRED_MERKLE_NODE_SZ bytes are
66 : kept. For metadata kinds pass NULL. */
67 : static inline void
68 : fd_inflight_key_init( fd_inflight_key_t * key,
69 : uint kind,
70 : ulong slot,
71 : ulong idx,
72 : ulong nonce,
73 0 : fd_hash_t const * fec_root ) {
74 0 : key->slot = slot;
75 0 : key->idx = (uint)idx;
76 0 : key->nonce = (uint)nonce;
77 0 : key->kind = kind;
78 0 : if( FD_LIKELY( fec_root ) ) memcpy( key->fec_root, fec_root->uc, FD_SHRED_MERKLE_NODE_SZ );
79 0 : else memset( key->fec_root, 0, FD_SHRED_MERKLE_NODE_SZ );
80 0 : }
81 :
82 : /* Key equality and hashing. A shred request is identified by the whole
83 : key. A metadata request is identified by its nonce alone -- the
84 : counter nonce is unique -- so its kind, slot and idx are not
85 : considered when matching. */
86 :
87 : static inline int
88 0 : fd_inflight_key_is_shred( fd_inflight_key_t const * k ) {
89 0 : return k->kind==FD_REPAIR_KIND_SHRED || k->kind==AG_REPAIR_KIND_SHRED_FOR_BLOCK_ID;
90 0 : }
91 :
92 : static inline int
93 : fd_inflight_key_eq( fd_inflight_key_t const * k0,
94 0 : fd_inflight_key_t const * k1 ) {
95 0 : if( FD_UNLIKELY( k0->nonce!=k1->nonce ) ) return 0;
96 0 : if( FD_UNLIKELY( fd_inflight_key_is_shred( k0 )!=fd_inflight_key_is_shred( k1 ) ) ) return 0;
97 0 : if( FD_UNLIKELY( !fd_inflight_key_is_shred( k0 ) ) ) return 1;
98 0 : return ( k0->slot==k1->slot ) & ( k0->idx==k1->idx ) & ( k0->kind==k1->kind ) & !memcmp( k0->fec_root, k1->fec_root, FD_SHRED_MERKLE_NODE_SZ );
99 0 : }
100 :
101 : static inline ulong
102 : fd_inflight_key_hash( fd_inflight_key_t const * k,
103 0 : ulong seed ) {
104 0 : if( FD_UNLIKELY( !fd_inflight_key_is_shred( k ) ) ) return fd_hash( seed, &k->nonce, sizeof(uint) );
105 0 : return fd_hash( seed, k, sizeof(fd_inflight_key_t) );
106 0 : }
107 :
108 : struct __attribute__((aligned(128UL))) fd_inflight {
109 : fd_inflight_key_t key;
110 : uint next; /* reserved for internal use by fd_pool and fd_map_chain */
111 : uint prev; /* for fd_map_chain */
112 : uint prevll; /* for fd_inflight_dlist */
113 : uint nextll;
114 : long timestamp_ns; /* when the request was created (caller's clock, nanoseconds) */
115 :
116 : fd_pubkey_t pubkey; /* peer the request went to (all-zero if parked unsent) */
117 :
118 : /* Version being repaired: the block_id of a ShredForBlockId or
119 : metadata request, all-zero for a positional shred request. */
120 : fd_hash_t block_id;
121 : };
122 : typedef struct fd_inflight fd_inflight_t;
123 : FD_STATIC_ASSERT( sizeof(fd_inflight_t)==128UL, fd_inflight_sz );
124 :
125 : #define POOL_NAME fd_inflight_pool
126 0 : #define POOL_T fd_inflight_t
127 : #define POOL_IDX_T uint
128 : #include "../../util/tmpl/fd_pool.c"
129 :
130 : #define MAP_NAME fd_inflight_map
131 0 : #define MAP_KEY key
132 0 : #define MAP_ELE_T fd_inflight_t
133 : #define MAP_KEY_T fd_inflight_key_t
134 0 : #define MAP_IDX_T uint
135 0 : #define MAP_KEY_EQ(k0, k1) fd_inflight_key_eq( (k0), (k1) )
136 0 : #define MAP_KEY_HASH(k,s) fd_inflight_key_hash( (k), (s) )
137 : #define MAP_MULTI 1 /* the same shred request within one rnonce time bucket */
138 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
139 : #include "../../util/tmpl/fd_map_chain.c"
140 :
141 : #define DLIST_NAME fd_inflight_dlist
142 : #define DLIST_ELE_T fd_inflight_t
143 : #define DLIST_IDX_T uint
144 0 : #define DLIST_PREV prevll
145 0 : #define DLIST_NEXT nextll
146 : #include "../../util/tmpl/fd_dlist.c"
147 :
148 : struct fd_inflights {
149 : fd_inflight_t * pool;
150 : fd_inflight_map_t * map; /* OUTSTANDING */
151 : fd_inflight_map_t * popped_map; /* POPPED */
152 : fd_inflight_dlist_t outstanding_dl[1];
153 : fd_inflight_dlist_t popped_dl[1];
154 : ulong popped_cnt;
155 : };
156 : typedef struct fd_inflights fd_inflights_t;
157 :
158 : FD_FN_CONST static inline ulong
159 0 : fd_inflights_align( void ) { return 128UL; }
160 :
161 : FD_FN_CONST static inline ulong
162 0 : fd_inflights_footprint( void ) {
163 0 : ulong chain_cnt = fd_inflight_map_chain_cnt_est( FD_INFLIGHT_REQ_MAX );
164 0 : return FD_LAYOUT_FINI(
165 0 : FD_LAYOUT_APPEND(
166 0 : FD_LAYOUT_APPEND(
167 0 : FD_LAYOUT_APPEND(
168 0 : FD_LAYOUT_APPEND(
169 0 : FD_LAYOUT_INIT,
170 0 : alignof(fd_inflights_t), sizeof(fd_inflights_t) ),
171 0 : fd_inflight_pool_align(), fd_inflight_pool_footprint( FD_INFLIGHT_REQ_MAX ) ),
172 0 : fd_inflight_map_align(), fd_inflight_map_footprint ( chain_cnt ) ),
173 0 : fd_inflight_map_align(), fd_inflight_map_footprint ( chain_cnt ) ),
174 0 : fd_inflights_align() );
175 0 : }
176 :
177 : void *
178 : fd_inflights_new( void * shmem,
179 : ulong seed );
180 :
181 : fd_inflights_t *
182 : fd_inflights_join( void * shmem );
183 :
184 : /* Timestamps. Every insert and match takes now, the caller's current
185 : time in nanoseconds, rather than reading a clock itself: records are
186 : stamped with it on insert, fd_inflights_shred_match reports RTT
187 : against it, and fd_inflights_should_drain compares against it. All
188 : calls on a table must use the same clock (the tile clock,
189 : fd_clock_tile_now) so age and RTT are consistent. */
190 :
191 : /* fd_inflights_shred_insert records a shred request of kind
192 : FD_REPAIR_KIND_SHRED (positional) or AG_REPAIR_KIND_SHRED_FOR_BLOCK_ID
193 : to pubkey. block_id is the ShredForBlockId version being repaired
194 : and fec_root the root the rotor holds for that version at the
195 : requested FEC set (the key a response is matched by); both NULL (or
196 : all-zero) for a positional request. */
197 :
198 : void
199 : fd_inflights_shred_insert( fd_inflights_t * table,
200 : uint kind,
201 : ulong nonce,
202 : fd_pubkey_t const * pubkey,
203 : ulong slot,
204 : ulong shred_idx,
205 : fd_hash_t const * block_id,
206 : fd_hash_t const * fec_root,
207 : long now );
208 :
209 : /* fd_inflights_shred_match matches a shred response against requests
210 : of kind (FD_REPAIR_KIND_SHRED or AG_REPAIR_KIND_SHRED_FOR_BLOCK_ID).
211 : fec_root is the response shred's merkle root (only the first
212 : FD_SHRED_MERKLE_NODE_SZ bytes are keyed on), or NULL to match a
213 : positional request. Removes
214 : every record with that key from both the outstanding and popped sets
215 : and credits the response to the oldest: returns its RTT in
216 : nanoseconds relative to now (>0), or 0 if nothing matched. On a
217 : match *peer_out is set, and *block_id_out (if non-NULL) to the
218 : matched request's block_id. */
219 :
220 : long
221 : fd_inflights_shred_match( fd_inflights_t * table,
222 : uint kind,
223 : ulong nonce,
224 : ulong slot,
225 : ulong shred_idx,
226 : fd_hash_t const * fec_root,
227 : fd_pubkey_t * peer_out,
228 : fd_hash_t * block_id_out,
229 : long now );
230 :
231 : /* fd_inflights_meta_insert records a metadata request to pubkey. kind
232 : is AG_REPAIR_KIND_PARENT_FEC_COUNT or AG_REPAIR_KIND_FEC_ROOT;
233 : fec_set_idx is meaningful for the latter only. */
234 :
235 : void
236 : fd_inflights_meta_insert( fd_inflights_t * table,
237 : ulong nonce,
238 : uint kind,
239 : fd_pubkey_t const * pubkey,
240 : ulong slot,
241 : fd_hash_t const * block_id,
242 : uint fec_set_idx,
243 : long now );
244 :
245 : /* fd_inflights_meta_match matches a metadata response by nonce in the
246 : outstanding then the popped set. On a match the record is copied to
247 : *out (out->key.kind is the kind that was requested), removed, and 1
248 : is returned; 0 otherwise. */
249 :
250 : int
251 : fd_inflights_meta_match( fd_inflights_t * table,
252 : ulong nonce,
253 : fd_inflight_t * out );
254 :
255 : /* fd_inflights_should_drain returns 1 if the oldest outstanding request
256 : has aged past FD_REQLIM_DEDUP_TIMEOUT and should be redispatched. */
257 :
258 : static inline int
259 0 : fd_inflights_should_drain( fd_inflights_t * table, long now ) {
260 0 : if( FD_UNLIKELY( fd_inflight_dlist_is_empty( table->outstanding_dl, table->pool ) ) ) return 0;
261 0 : fd_inflight_t * head = fd_inflight_dlist_ele_peek_head( table->outstanding_dl, table->pool );
262 0 : return head->timestamp_ns + FD_REQLIM_DEDUP_TIMEOUT < now;
263 0 : }
264 :
265 : /* fd_inflights_pop copies the oldest outstanding request to *out and
266 : moves it to the popped set, so a late response to its nonce still
267 : matches. A record with nonce 0 (parked by the caller, never sent) is
268 : released instead, since nothing can match it. The outstanding set
269 : must be non-empty: only call this after fd_inflights_should_drain
270 : returns 1. */
271 :
272 : void
273 : fd_inflights_pop( fd_inflights_t * table,
274 : fd_inflight_t * out );
275 :
276 : /* fd_inflights_expire releases, oldest first, up to max OUTSTANDING or
277 : POPPED records inserted before cutoff and returns how many. For
278 : callers that never redispatch from the table. */
279 :
280 : ulong
281 : fd_inflights_expire( fd_inflights_t * table,
282 : long cutoff,
283 : ulong max );
284 :
285 : /* fd_inflights_oldest_ts returns the insert time of the oldest
286 : OUTSTANDING or POPPED record (the next one fd_inflights_expire
287 : releases), LONG_MAX if there is none. */
288 :
289 : static inline long
290 0 : fd_inflights_oldest_ts( fd_inflights_t * table ) {
291 0 : long ts = LONG_MAX;
292 0 : if( FD_LIKELY( !fd_inflight_dlist_is_empty( table->outstanding_dl, table->pool ) ) ) ts = fd_inflight_dlist_ele_peek_head( table->outstanding_dl, table->pool )->timestamp_ns;
293 0 : if( FD_UNLIKELY( !fd_inflight_dlist_is_empty( table->popped_dl, table->pool ) ) ) ts = fd_long_min( ts, fd_inflight_dlist_ele_peek_head( table->popped_dl, table->pool )->timestamp_ns );
294 0 : return ts;
295 0 : }
296 :
297 : /* fd_inflights_outstanding_free returns how many new requests can be
298 : inserted before an insert would have to evict an OUTSTANDING record
299 : (FREE records plus evictable POPPED ones). */
300 :
301 : static inline ulong
302 0 : fd_inflights_outstanding_free( fd_inflights_t * table ) {
303 0 : return fd_inflight_pool_free( table->pool ) + table->popped_cnt;
304 0 : }
305 :
306 : /* fd_inflights_outstanding_cnt returns the number of OUTSTANDING
307 : records. */
308 :
309 : static inline ulong
310 0 : fd_inflights_outstanding_cnt( fd_inflights_t * table ) {
311 0 : return fd_inflight_pool_used( table->pool ) - table->popped_cnt;
312 0 : }
313 :
314 : void
315 : fd_inflights_print( fd_inflight_dlist_t * dlist, fd_inflight_t * pool );
316 :
317 : #endif /* HEADER_fd_src_discof_repair_fd_inflight_h */
|
