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, 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 chainer, 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. */
44 :
45 : /* Max number of pending requests */
46 192 : #define FD_INFLIGHT_REQ_MAX (1<<20)
47 :
48 : struct fd_inflight_key {
49 : ulong slot;
50 : uint idx; /* shred idx (shred kinds) or fec_set_idx (AG_REPAIR_KIND_FEC_ROOT) */
51 : uint nonce; /* rnonce or counter nonce (metadata) */
52 : uint kind; /* FD_REPAIR_KIND_SHRED for every shred request, else AG_REPAIR_KIND_{PARENT_FEC_COUNT,FEC_ROOT} */
53 : /* shred kinds: first FD_SHRED_MERKLE_NODE_SZ bytes of the FEC root a
54 : ShredForBlockId request was issued against, all-zero for a
55 : positional request. All-zero for metadata kinds. */
56 : uchar fec_root[ FD_SHRED_MERKLE_NODE_SZ ];
57 : };
58 : typedef struct fd_inflight_key fd_inflight_key_t;
59 : FD_STATIC_ASSERT( sizeof(fd_inflight_key_t)==40UL, fd_inflight_key_sz );
60 :
61 : /* fd_inflight_key_init fills key. For shred requests fec_root is the
62 : (full or 20-byte-padded) FEC root the request targets, or NULL for a
63 : positional request; only the first FD_SHRED_MERKLE_NODE_SZ bytes are
64 : kept. For metadata kinds pass NULL. */
65 : static inline void
66 : fd_inflight_key_init( fd_inflight_key_t * key,
67 : uint kind,
68 : ulong slot,
69 : ulong idx,
70 : ulong nonce,
71 4047 : fd_hash_t const * fec_root ) {
72 4047 : key->slot = slot;
73 4047 : key->idx = (uint)idx;
74 4047 : key->nonce = (uint)nonce;
75 4047 : key->kind = kind;
76 4047 : if( FD_LIKELY( fec_root ) ) memcpy( key->fec_root, fec_root->uc, FD_SHRED_MERKLE_NODE_SZ );
77 375 : else memset( key->fec_root, 0, FD_SHRED_MERKLE_NODE_SZ );
78 4047 : }
79 :
80 : /* Key equality and hashing. A shred request is identified by the whole
81 : key. A metadata request is identified by its nonce alone -- the
82 : counter nonce is unique -- so its kind, slot and idx are not
83 : considered when matching. */
84 :
85 : static inline int
86 13587 : fd_inflight_key_is_shred( fd_inflight_key_t const * k ) { return k->kind==FD_REPAIR_KIND_SHRED; }
87 :
88 : static inline int
89 : fd_inflight_key_eq( fd_inflight_key_t const * k0,
90 1896 : fd_inflight_key_t const * k1 ) {
91 1896 : if( FD_UNLIKELY( k0->nonce!=k1->nonce ) ) return 0;
92 1896 : if( FD_UNLIKELY( fd_inflight_key_is_shred( k0 )!=fd_inflight_key_is_shred( k1 ) ) ) return 0;
93 1896 : if( FD_UNLIKELY( !fd_inflight_key_is_shred( k0 ) ) ) return 1;
94 1740 : return ( k0->slot==k1->slot ) & ( k0->idx==k1->idx ) & !memcmp( k0->fec_root, k1->fec_root, FD_SHRED_MERKLE_NODE_SZ );
95 1896 : }
96 :
97 : static inline ulong
98 : fd_inflight_key_hash( fd_inflight_key_t const * k,
99 7899 : ulong seed ) {
100 7899 : if( FD_UNLIKELY( !fd_inflight_key_is_shred( k ) ) ) return fd_hash( seed, &k->nonce, sizeof(uint) );
101 7209 : return fd_hash( seed, k, sizeof(fd_inflight_key_t) );
102 7899 : }
103 :
104 : struct __attribute__((aligned(128UL))) fd_inflight {
105 : fd_inflight_key_t key;
106 : uint next; /* reserved for internal use by fd_pool and fd_map_chain */
107 : uint prev; /* for fd_map_chain */
108 : uint prevll; /* for fd_inflight_dlist */
109 : uint nextll;
110 : long timestamp_ns; /* when the request was created (caller's clock, nanoseconds) */
111 :
112 : fd_pubkey_t pubkey; /* peer the request went to (all-zero if parked unsent) */
113 :
114 : /* Version being repaired: the block_id of a ShredForBlockId or
115 : metadata request, all-zero for a positional shred request. */
116 : fd_hash_t block_id;
117 : };
118 : typedef struct fd_inflight fd_inflight_t;
119 : FD_STATIC_ASSERT( sizeof(fd_inflight_t)==128UL, fd_inflight_sz );
120 :
121 : #define POOL_NAME fd_inflight_pool
122 96 : #define POOL_T fd_inflight_t
123 : #define POOL_IDX_T uint
124 : #include "../../util/tmpl/fd_pool.c"
125 :
126 : #define MAP_NAME fd_inflight_map
127 2181 : #define MAP_KEY key
128 33 : #define MAP_ELE_T fd_inflight_t
129 : #define MAP_KEY_T fd_inflight_key_t
130 7983 : #define MAP_IDX_T uint
131 1896 : #define MAP_KEY_EQ(k0, k1) fd_inflight_key_eq( (k0), (k1) )
132 7899 : #define MAP_KEY_HASH(k,s) fd_inflight_key_hash( (k), (s) )
133 : #define MAP_MULTI 1 /* the same shred request within one rnonce time bucket */
134 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
135 : #include "../../util/tmpl/fd_map_chain.c"
136 :
137 : #define DLIST_NAME fd_inflight_dlist
138 : #define DLIST_ELE_T fd_inflight_t
139 : #define DLIST_IDX_T uint
140 4035 : #define DLIST_PREV prevll
141 4068 : #define DLIST_NEXT nextll
142 : #include "../../util/tmpl/fd_dlist.c"
143 :
144 : struct fd_inflights {
145 : fd_inflight_t * pool;
146 : fd_inflight_map_t * map; /* OUTSTANDING */
147 : fd_inflight_map_t * popped_map; /* POPPED */
148 : fd_inflight_dlist_t outstanding_dl[1];
149 : fd_inflight_dlist_t popped_dl[1];
150 : ulong popped_cnt;
151 : };
152 : typedef struct fd_inflights fd_inflights_t;
153 :
154 : FD_FN_CONST static inline ulong
155 432 : fd_inflights_align( void ) { return 128UL; }
156 :
157 : FD_FN_CONST static inline ulong
158 96 : fd_inflights_footprint( void ) {
159 96 : ulong chain_cnt = fd_inflight_map_chain_cnt_est( FD_INFLIGHT_REQ_MAX );
160 96 : return FD_LAYOUT_FINI(
161 96 : FD_LAYOUT_APPEND(
162 96 : FD_LAYOUT_APPEND(
163 96 : FD_LAYOUT_APPEND(
164 96 : FD_LAYOUT_APPEND(
165 96 : FD_LAYOUT_INIT,
166 96 : alignof(fd_inflights_t), sizeof(fd_inflights_t) ),
167 96 : fd_inflight_pool_align(), fd_inflight_pool_footprint( FD_INFLIGHT_REQ_MAX ) ),
168 96 : fd_inflight_map_align(), fd_inflight_map_footprint ( chain_cnt ) ),
169 96 : fd_inflight_map_align(), fd_inflight_map_footprint ( chain_cnt ) ),
170 96 : fd_inflights_align() );
171 96 : }
172 :
173 : void *
174 : fd_inflights_new( void * shmem,
175 : ulong seed );
176 :
177 : fd_inflights_t *
178 : fd_inflights_join( void * shmem );
179 :
180 : /* Timestamps. Every insert and match takes now, the caller's current
181 : time in nanoseconds, rather than reading a clock itself: records are
182 : stamped with it on insert, fd_inflights_shred_match reports RTT
183 : against it, and fd_inflights_should_drain compares against it. All
184 : calls on a table must use the same clock (the tile clock,
185 : fd_clock_tile_now) so age and RTT are consistent. */
186 :
187 : /* fd_inflights_shred_insert records a shred request to pubkey.
188 : block_id is the ShredForBlockId version being repaired and fec_root
189 : the root the chainer holds for that version at the requested FEC set
190 : (the key a response is matched by); both NULL (or all-zero) for a
191 : positional request. */
192 :
193 : void
194 : fd_inflights_shred_insert( fd_inflights_t * table,
195 : ulong nonce,
196 : fd_pubkey_t const * pubkey,
197 : ulong slot,
198 : ulong shred_idx,
199 : fd_hash_t const * block_id,
200 : fd_hash_t const * fec_root,
201 : long now );
202 :
203 : /* fd_inflights_shred_match matches a shred response. fec_root is the
204 : response shred's merkle root (only the first FD_SHRED_MERKLE_NODE_SZ
205 : bytes are keyed on), or NULL to match a positional request. Removes
206 : every record with that key from both the outstanding and popped sets
207 : and credits the response to the oldest: returns its RTT in
208 : nanoseconds relative to now (>0), or 0 if nothing matched. On a
209 : match *peer_out is set, and *block_id_out (if non-NULL) to the
210 : matched request's block_id. */
211 :
212 : long
213 : fd_inflights_shred_match( fd_inflights_t * table,
214 : ulong nonce,
215 : ulong slot,
216 : ulong shred_idx,
217 : fd_hash_t const * fec_root,
218 : fd_pubkey_t * peer_out,
219 : fd_hash_t * block_id_out,
220 : long now );
221 :
222 : /* fd_inflights_meta_insert records a metadata request to pubkey. kind
223 : is AG_REPAIR_KIND_PARENT_FEC_COUNT or AG_REPAIR_KIND_FEC_ROOT;
224 : fec_set_idx is meaningful for the latter only. */
225 :
226 : void
227 : fd_inflights_meta_insert( fd_inflights_t * table,
228 : ulong nonce,
229 : uint kind,
230 : fd_pubkey_t const * pubkey,
231 : ulong slot,
232 : fd_hash_t const * block_id,
233 : uint fec_set_idx,
234 : long now );
235 :
236 : /* fd_inflights_meta_match matches a metadata response by nonce in the
237 : outstanding then the popped set. On a match the record is copied to
238 : *out (out->key.kind is the kind that was requested), removed, and 1
239 : is returned; 0 otherwise. */
240 :
241 : int
242 : fd_inflights_meta_match( fd_inflights_t * table,
243 : ulong nonce,
244 : fd_inflight_t * out );
245 :
246 : /* fd_inflights_should_drain returns 1 if the oldest outstanding request
247 : has aged past FD_REQLIM_DEDUP_TIMEOUT and should be redispatched. */
248 :
249 : static inline int
250 2226 : fd_inflights_should_drain( fd_inflights_t * table, long now ) {
251 2226 : if( FD_UNLIKELY( fd_inflight_dlist_is_empty( table->outstanding_dl, table->pool ) ) ) return 0;
252 2130 : fd_inflight_t * head = fd_inflight_dlist_ele_peek_head( table->outstanding_dl, table->pool );
253 2130 : return head->timestamp_ns + FD_REQLIM_DEDUP_TIMEOUT < now;
254 2226 : }
255 :
256 : /* fd_inflights_pop copies the oldest outstanding request to *out and
257 : moves it to the popped set, so a late response to its nonce still
258 : matches. A record with nonce 0 (parked by the caller, never sent) is
259 : released instead, since nothing can match it. The outstanding set
260 : must be non-empty: only call this after fd_inflights_should_drain
261 : returns 1. */
262 :
263 : void
264 : fd_inflights_pop( fd_inflights_t * table,
265 : fd_inflight_t * out );
266 :
267 : /* fd_inflights_outstanding_free returns how many new requests can be
268 : inserted before an insert would have to evict an OUTSTANDING record
269 : (FREE records plus evictable POPPED ones). */
270 :
271 : static inline ulong
272 2211 : fd_inflights_outstanding_free( fd_inflights_t * table ) {
273 2211 : return fd_inflight_pool_free( table->pool ) + table->popped_cnt;
274 2211 : }
275 :
276 : /* fd_inflights_outstanding_cnt returns the number of OUTSTANDING
277 : records. */
278 :
279 : static inline ulong
280 18 : fd_inflights_outstanding_cnt( fd_inflights_t * table ) {
281 18 : return fd_inflight_pool_used( table->pool ) - table->popped_cnt;
282 18 : }
283 :
284 : void
285 : fd_inflights_print( fd_inflight_dlist_t * dlist, fd_inflight_t * pool );
286 :
287 : #endif /* HEADER_fd_src_discof_repair_fd_inflight_h */
|
