Line data Source code
1 : #include "fd_rdisp.h"
2 : #include "fd_rdisp_mq.h"
3 : #include "../../util/fd_hash32.h"
4 : #include <math.h> /* for the EMA */
5 :
6 : /* The conflict graph that this file builds is not a general DAG, but
7 : the union of several special account-conflict graphs. Each
8 : account-conflict graph has special structure:
9 : ---> 3 --
10 : / \
11 : / v
12 : 1 ---> 2 -----> 4 --> 6 ----> 7
13 : \ ^
14 : \ /
15 : ----> 5 --
16 :
17 : That is, the graph is almost a line, but may have fan-out and fan-in
18 : regions. The tricky part about representing a graph like this
19 : without dynamic memory allocation is that nodes may have arbitrary
20 : in-degree and out-degree. Thus, we use a pretty standard trick and
21 : use sibling pointers, denoted below with dotted lines. Each node
22 : maintains at most one successor pointer and at most one sibling
23 : pointer. Although not shown below, the sibling pointers are
24 : circularly linked, so 5's sibling is 3. Additionally, though not
25 : shown below, the child of the last node (7) stores information about
26 : what account address all this is for, which facilitates deleting the
27 : last node in the graph.
28 :
29 :
30 : --> 3 --
31 : / ^ \
32 : / : \
33 : / V v
34 : 1 ---> 2 4 --> 6 ----> 7
35 : ^ ^
36 : : /
37 : V /
38 : 5 --
39 :
40 : The normal edge 2->3 along with the sibling edge 3..>4 implies a
41 : normal edge 2->4. That then transitively implies an edge 2->5.
42 :
43 : We want each node to maintain a count of its in-degree so that we
44 : know when it can be executed. The implied edges also count for the
45 : in-degree. In this example, node 1 has in-degree 0, node 6 has
46 : in-degree 3, and the rest have in-degree 1.
47 :
48 : Maintaining each account-conflict graph is relatively easy given the
49 : operations we want to support. Only the details about sibling edges
50 : are worth mentioning. For example, when deleting node 2, we
51 : decrement the in-degree count for its successor, and then follow the
52 : sibling pointers, decrementing all the in-degree counts as we go to
53 : mark the deletion of the implied edges. Sibling edges also need to
54 : be doubly linked, so that e.g. nodes 3 and 5 can be re-linked in O(1)
55 : if node 4 is deleted. They're also circularly linked as well for
56 : convenience.
57 :
58 : When building the graph, we maintain a map of account to the last
59 : node that references it, whether that was a read or write, and
60 : whether there are any writers to that account in the graph right now.
61 : If the new node reads from an account that was last read, the new
62 : node becomes a sibling of the last read, with in-degree increased if
63 : there are any writers. Otherwise, it becomes a successor of the node
64 : that last referenced the account. */
65 :
66 : /* For a task like this with lots of graph traversal and pointer
67 : chasing, performance is typically limited by memory latency. That
68 : means that the more that can fit in cache, the better the
69 : performance. This implementation uses a lot of bit-packing to
70 : improve cache footprint. */
71 :
72 : /* The following structs are all very local to this compilation unit,
73 : and so they don't have globally acceptable type names (e.g.
74 : fd_rdisp_edge_t). */
75 :
76 : #define MAX_ACCT_PER_TXN FD_TXN_ACCT_ADDR_MAX
77 : FD_STATIC_ASSERT( MAX_ACCT_PER_TXN<=128UL, max_acct_per_txn );
78 :
79 : /* edge_t: Fields typed edge_t represent an edge in one of the parallel
80 : account-conflict DAGs. Each transaction stores a list of all its
81 : outgoing edges. The type is actually a union of bitfield, but C
82 : bitfields are gross, so we just do it manually with macros.
83 : If the high bit is not set, then the next 23 bits store the
84 : destination of the edge, represented by its index in the pool of
85 : transactions. Then the lowest 8 bits store the account index within
86 : that transaction of the edge that is part of the same
87 : account-specific DAG as this edge. Because the max depth is 2^23-1,
88 : and each transaction can reference FD_TXN_ACCT_ADDR_MAX accounts,
89 : the max accounts that can be referenced fits in 30 bits.
90 :
91 : If the high bit is set, the second highest bit indicates whether it's
92 : a pseudo transaction or if the transaction storing this edge_t value
93 : is the last in this specific DAG. Either way, the lower 30 bits of
94 : the value are the index. This index is in the map_pool for the
95 : account pubkey for this DAG if it's a final transaction, and an index
96 : into the pseudo transaction pool if it's a pseudo-transaction. See
97 : the comments about the hidden edge outgoing from node 7 in the DAG at
98 : the top of this file for an example.
99 : Because the max depth is 2^23-1, and each transaction can reference
100 : 128 accounts, the max accounts that can be referenced fits in 30
101 : bits.
102 : The proper type would be something like
103 : typedef union {
104 : struct {
105 : uint is_special:1; // == 0
106 : uint txn_idx:23;
107 : uint acct_idx:8;
108 : } e;
109 : struct {
110 : uint is_special:1; // == 1
111 : uint is_last:1; // == 1
112 : uint map_pool_idx:30;
113 : } last;
114 : struct {
115 : uint is_special:1; // == 1
116 : uint is_last:1; // == 0
117 : uint pseudo_txn_idx:30;
118 : } pseudo;
119 : } edge_t;
120 :
121 : */
122 : typedef uint edge_t;
123 :
124 41305 : #define EDGE_SPECIAL_PTXN 0x80000000U
125 4689 : #define EDGE_SPECIAL_LAST 0xC0000000U
126 36616 : #define EDGE_SPECIAL_MASK 0xC0000000U
127 :
128 : #define EDGE_IS_LAST(x) (((x)&EDGE_SPECIAL_MASK)==EDGE_SPECIAL_LAST)
129 36616 : #define EDGE_IS_PTXN(x) (((x)&EDGE_SPECIAL_MASK)==EDGE_SPECIAL_PTXN)
130 0 : #define EDGE_SPECIAL_IDX(x) ((x)&(~EDGE_SPECIAL_MASK))
131 : #define EDGE_SPECIAL_IDX_MAX (~EDGE_SPECIAL_MASK)
132 9378 : #define EDGE_MAKE_SPECIAL(k,x) ((x)|FD_CONCAT2(EDGE_SPECIAL_,k))
133 :
134 : FD_STATIC_ASSERT( MAX_ACCT_PER_TXN<=128UL, max_acct_per_txn );
135 :
136 : /* fd_rdisp_txn is the representation of a transaction as a node in the
137 : DAG. */
138 : struct fd_rdisp_txn {
139 : /* in_degree: The total number of edges summed across all account DAGs
140 : with this node as their destination. In the worst case, all the
141 : other transactions in the pool read from each of the max number of
142 : accounts that this transaction writes to, so there are
143 : FD_RDISP_MAX_ACCT_PER_TXN*depth edges that come into this node,
144 : which fits in about 30 bits, so we have some room for special
145 : values. If in_degree is one of the following values, then the
146 : transaction is: */
147 993267870 : #define IN_DEGREE_FREE (UINT_MAX )
148 0 : #define IN_DEGREE_UNSTAGED (UINT_MAX-1U)/* unstaged, not dispatched */
149 0 : #define IN_DEGREE_DISPATCHED (UINT_MAX-2U)/* staged, dispatched */
150 0 : #define IN_DEGREE_UNSTAGED_DISPATCHED (UINT_MAX-3U)/* unstaged, dispatched */
151 0 : #define IN_DEGREE_ZOMBIE (UINT_MAX-4U)/* zombie */
152 : /* a transaction that is staged and dispatched is must have an
153 : in_degree of 0. in_degree isn't a meaningful concept for unstaged
154 : transactions. */
155 : uint in_degree;
156 :
157 : /* score: integer part stores how many transactions in the block must
158 : have completed before this transaction can be scheduled. This is
159 : useful for transactions marked as serializing. The fractional part
160 : gives some measure of how urgent the transaction is, where lower is
161 : more urgent. This means we can't have more transactions in a block
162 : marked as serializing than the first integer that a float cannot
163 : represent. That value is about 16M, which is much higher than the
164 : maximum number of transactions in a block, so this is not a
165 : problem. If in the very rare case that there are more than just a
166 : few serializing transactions, we will lose a bit of precision for
167 : the fractional portion, which makes total sense; if there's not
168 : much room for parallel execution, having the optimal parallel
169 : execution is not very important. */
170 : float score;
171 :
172 : /* edge_cnt_etc:
173 : 0xFFFF0000 (16 bits) for linear block number,
174 : 0x0000C000 (2 bits) for concurrency lane,
175 : 0x00003F80 (7 bits) for r_cnt
176 : 0x0000007F (7 bits) for w_cnt_1. Transactions have at least one
177 : writable account and at most MAX_ACCT_PER_TXN total accounts, so
178 : storing w_cnt_1 = w_cnt - 1 fits in 7 bits. */
179 : union {
180 : uint edge_cnt_etc;
181 : /* edge_cnt_etc is only used when the transaction is STAGED and
182 : PENDING, READY, or DISPATCHED. If UNSTAGED or FREE, the next
183 : pointer is also here. It can't be UNSTAGED and FREE at the same
184 : time, so there's no conflict with storage there either. */
185 : uint unstaged_next;
186 : uint free_next;
187 : /* If ZOMBIE, pointer back to block is here. No storage conflict
188 : because ZOMBIE is an exclusive state. */
189 : uint block_idx;
190 : };
191 :
192 :
193 : /* When a transaction writes to an account, it only creates one
194 : link. When a transaction reads from an account, we need the full
195 : doubly linked list with its siblings, so it creates 3 edges
196 : (child, next, prev). All edges from writable accounts come first,
197 : and we keep track of how many there are. In the worst case, all
198 : accounts are reads, so we size it appropriately. */
199 : edge_t edges[3UL*FD_RDISP_MAX_ACCT_PER_TXN]; /* addressed [0, w_cnt_1+1+3*r_cnt) */
200 : };
201 : typedef struct fd_rdisp_txn fd_rdisp_txn_t;
202 :
203 : /* To simplify the code, we make fd_rdisp_ptxn_t such that it can be cast
204 : as a fd_rdisp_txn_t * and mostly function. This greatly simplifies
205 : the code but is technically UB. The alias rules say that a write to
206 : a field of a pointer of type T1* and a write to a field of a pointer
207 : of type T2* should be independent. To combat this, we need to be
208 : careful in each function to either use the ptxn_t * pointer or to
209 : immediately cast to txn_t * and only access it via that pointer. */
210 : struct fd_rdisp_ptxn {
211 : /* These fields have the same meaning as in fd_rdisp_txn_t */
212 : uint in_degree;
213 : float score;
214 : union {
215 : uint edge_cnt_etc; /* r_cnt == 1 and w_cnt_1 is 0x7F, but ignored */
216 : uint free_next;
217 : };
218 : /* The whole reason for the difference between a normal transaction
219 : and a pseudo-transaction is that this array can be a lot smaller.
220 : */
221 : edge_t edges[3];
222 : /* last maps back to the account for which this pseudo-transaction is an
223 : LtHash addition task. It's normally the same as edges[0], but if a
224 : writer is added after this pseudo-transaction is added (for
225 : example, in the next block), then edges[0] may have a different
226 : value, but we still need to be able to map back to the account
227 : address. */
228 : edge_t last;
229 : };
230 : typedef struct fd_rdisp_ptxn fd_rdisp_ptxn_t;
231 :
232 : #define POOL_NAME ptxn_pool
233 954282148 : #define POOL_NEXT free_next
234 : #define POOL_IDX_T uint
235 3023 : #define POOL_T fd_rdisp_ptxn_t
236 : #include "../../util/tmpl/fd_pool.c"
237 :
238 : /* Two more definitions:
239 : An edge index is an array position within the edges array. An
240 : account index is a position within a transaction's account addresses,
241 : reordered so that the writable ones come first. Since writable
242 : accounts use one position in the edges array per account address,
243 : these often coincide. */
244 :
245 :
246 : /* FOLLOW_EDGE and FOLLOW_EDGE_TXN are helper macros for dealing with
247 : edges. Given an edge_t x, and rdisp disp, FOLLOW_EDGE_TXN
248 : returns a pointer to transaction that the edge points to; FOLLOW_EDGE
249 : returns a pointer to the (first) edge_t within that transaction that
250 : is part of the same DAG as this edge. FOLLOW_EDGE and
251 : FOLLOW_EDGE_TXN must not be called if EDGE_IS_LAST is non-zero.
252 :
253 : Then the edge index, i.e. the position in the edges array of the
254 : (first) edge for an account index is:
255 : acct_idx if acct_idx<=w_cnt_1
256 : w_cnt_1+1 + 3*(acct_idx-w_cnt_1-1) else.
257 : Simplifying gives
258 : acct_idx + 2*signed_max( 0, acct_idx-w_cnt_1-1 ).
259 : If the edge points to a pseudo-transaction, then __w_cnt_1 is a
260 : garbage value, but __idx is forced to 0, which means its value is not
261 : used.
262 : In doing this calculation, we also basically get for free whether the
263 : edge is for a writable account or a readonly account, so we return
264 : that as well via the w parameter. If the child transaction only reads
265 : the account address for this DAG, then the next and prev pointers can
266 : be accessed using the returned value +1 and +2, respectively. */
267 9154 : #define FOLLOW_EDGE(disp, x, w) (__extension__({ \
268 9154 : fd_rdisp_t const * __disp = (disp); \
269 9154 : uint __e = (x); \
270 9154 : edge_t * __edges = EDGE_IS_PTXN(__e) ? __disp->ptxn_pool[EDGE_SPECIAL_IDX(__e)].edges : __disp->pool[__e>>8].edges; \
271 9154 : uint __w_cnt_1 = EDGE_IS_PTXN(__e) ? 0 : __disp->pool[__e>>8].edge_cnt_etc & 0x7FU; \
272 9154 : uint __idx = fd_uint_if( EDGE_IS_PTXN(__e), 0U, (__e & 0xFFU) ); \
273 9154 : (w) = (!EDGE_IS_PTXN(__e)) & (__idx<=__w_cnt_1); \
274 9154 : (void)(w); /* not robust... */ \
275 9154 : __edges + __idx + 2*fd_int_max( 0, (int)(__idx)-(int)(__w_cnt_1)-1 ); }))
276 :
277 0 : #define FOLLOW_EDGE_TXN(disp, x) (__extension__({ \
278 0 : fd_rdisp_t const * __disp = (disp); \
279 0 : uint __e = (x); \
280 0 : EDGE_IS_PTXN(__e) ? (fd_rdisp_txn_t *)((__disp)->ptxn_pool+EDGE_SPECIAL_IDX(__e)) : \
281 0 : ((__disp)->pool+(__e>>8)); }))
282 :
283 :
284 :
285 : /* The pool and slist are almost the same, but they are used
286 : differently, so keep them as different structures for now. */
287 :
288 : #define POOL_NAME pool
289 3021 : #define POOL_T fd_rdisp_txn_t
290 : #define POOL_IDX_T uint
291 3836089 : #define POOL_NEXT free_next
292 : #define POOL_SENTINEL 1
293 : #include "../../util/tmpl/fd_pool.c"
294 :
295 : #define SLIST_NAME unstaged_txn_ll
296 : #define SLIST_ELE_T fd_rdisp_txn_t
297 0 : #define SLIST_IDX_T uint
298 0 : #define SLIST_NEXT unstaged_next
299 : #include "../../util/tmpl/fd_slist.c"
300 :
301 : #define DLIST_IDX_T uint
302 0 : #define DLIST_PREV edges[0]
303 0 : #define DLIST_NEXT edges[1]
304 : #define DLIST_NAME zombie_dlist
305 : #define DLIST_ELE_T fd_rdisp_txn_t
306 : #include "../../util/tmpl/fd_dlist.c"
307 :
308 :
309 : /* ACCT_INFO_STATE: We need to keep just a little metadata about writers
310 : in the DAG for an account. In particular, for correctness, we need
311 : to be able to distinguish the case where there are only readers so
312 : that we don't increment in_degree when adding a new fd_rdisp_txn. If
313 : we have any writers, the only way to transition into a state where
314 : there are only readers is to complete the last writer. We know we
315 : are in this case when the completed node's child doesn't have a
316 : child, and the completed node's child is a reader, as indicated by
317 : the LAST_REF_WAS_WRITE bit. LAST_REF_WAS_WRITE also has the
318 : advantage of being easy to maintain. You'd think with those two
319 : binary states we'd have used up our 2 bits, but actually, there are
320 : only states there, which means we can almost cram in a little more
321 : information for free. In particular, whether we need to create a
322 : LtHash addition hash is also very related to ANY_WRITERS and
323 : LAST_REF_WAS_WRITE, via the state machine below, which has only 5
324 : accessible states out of 8 possible states (we can add a reader or
325 : writer from any state. If there are any writers, we can complete the
326 : last writer. If it needs an LtHash add pseudo transaction, then we
327 : may add a pseudo transaction).
328 :
329 : add reader
330 : |--------|
331 : V |
332 : 0-----------------
333 : | No writers, |<-------------------------------------------
334 : | which implies | |
335 : | LRWW==0 and |<--------------------------------- |
336 : | NEEDS_LTADD==0 | complete last writer | |
337 : ------------------ | |
338 : | | |
339 : add | complete last writer | |
340 : writer | -----------------------------------+------- |
341 : V | | | |
342 : 1----------------- add writer | | |
343 : | ANY_WRITERS==1 |<---------------------------| | | |
344 : |->| LRWW==1 and |------------------------ | | | |
345 : | | NEEDS_LTADD==1 |<---| add pseudo| | | | |
346 : | ------------------ | add txn | | | | |
347 : | ^ | | | writer V | | | |
348 : | | | |-----| 2*-------------------- | |
349 : | add | | add | Last is pseudo txn | | |
350 : | writer | | reader |-->| ANY_WRITERS==1 | | |
351 : | | V add | | LRWW==0 and | | |
352 : | 2----------------- reader |---| NEEDS_LTADD==0 | | |
353 : | | ANY_WRITERS==1 | ---------------------- | |
354 : | | LRWW==0 and | ^ | |
355 : | | NEEDS_LTADD==1 |------------------------| | |
356 : | ------------------ add pseudo txn | |
357 : | | ^ | | |
358 : | | | | | |
359 : | ---------- | 3------------------ | |
360 : | add reader | | ANY_WRITERS==0 | | |
361 : | ---------------->| LRWW==0 and |<------- |
362 : | complete last | NEEDS_LTADD==1 |-----------
363 : | writer ------------------- add pseudo
364 : | | | ^ txn
365 : | add writer | | |
366 : |------------------------------------ ----------
367 : add reader
368 :
369 : Sadly, we still only have 2 bits, so we collapse the top-left and
370 : bottom right states into one state. The only difference between the
371 : two states is whether it is possible to add a pseudo-txn, and that's
372 : driven by the rdisp_mq anyway. */
373 : /* AW LRWW NLT */
374 0 : #define ACCT_INFO_STATE_NO_WRITERS 0U /*0 0 0 */
375 12266 : #define ACCT_INFO_STATE_LAST_REF_WAS_WRITE 1U /*1 1 1 */
376 4689 : #define ACCT_INFO_STATE_LAST_REF_WAS_READ 2U /*1 0 ? */
377 0 : #define ACCT_INFO_STATE_NEEDS_PTXN 3U /*0 0 1 */
378 :
379 14067 : #define ACCT_INFO_STATE_IS( val, lane, state) ( (((val)>>(2U*(lane)))&3) == FD_CONCAT2(ACCT_INFO_STATE_, state) )
380 2888 : #define ACCT_INFO_STATE_SET(val, lane, state) (((val) & (uchar)(~(3U<<(2U*(lane))))) | (uchar)(FD_CONCAT2(ACCT_INFO_STATE_, state)<<(2U*(lane))) )
381 :
382 :
383 : /* acct_info_t is a node in a map_chain that contains the metadata for a
384 : single account address's conflict graph DAG. In particular, it
385 : contains the information needed to know where to insert a node that
386 : reads from or writes to the account. The objects of this type follow
387 : this state machine:
388 :
389 : FREE -----> ACTIVE ----> CACHED
390 : ^ |
391 : |-------------
392 : When FREE, it is in free_acct_dlist only. When ACTIVE, it is in
393 : acct_map only. When CACHED, it is in both free_acct_dlist and
394 : acct_map, and cached==ACCT_INFO_CACHED.
395 : */
396 0 : #define ACCT_INFO_CACHED UINT_MAX
397 : FD_STATIC_ASSERT( ((FD_RDISP_MAX_DEPTH<<8)|0xFFUL)<(ulong)ACCT_INFO_CACHED, acct_info_cached ); /* no edge_t is the mark */
398 :
399 : struct acct_info {
400 : /* key, next, and prev are the map_chain fields. Used in the ACTIVE
401 : and CACHED states. next and prev set to 0 when in the FREE state.
402 : Element 0 is a sentinel and isn't inserted to the free_acct_dlist,
403 : so this is unambiguous. */
404 : fd_acct_addr_t key;
405 : uint next;
406 : uint prev;
407 :
408 : union {
409 : struct {
410 : /* This is effectively a pointer to the last node in the DAG for
411 : this pubkey, one for each staging lane.
412 : EDGE_IS_LAST(FOLLOW_EDGE(disp, last_reference[i])) is non-zero.
413 : */
414 : edge_t last_reference[4];
415 :
416 : }; /* When in the ACTIVE state */
417 : struct {
418 : uint free_ll_next;
419 : uint free_ll_prev;
420 : /* cached is ACCT_INFO_CACHED in the CACHED state, which tells a
421 : CACHED element in acct_map from an ACTIVE one: it aliases
422 : last_reference[2], an edge_t of a transaction index in the
423 : ACTIVE state, which has its top bit clear. Not maintained in
424 : the FREE state (next and prev tell FREE from CACHED). */
425 : uint cached;
426 : /* 4 bytes of padding here */
427 : }; /* When not in the ACTIVE state, used by the free_acct_dlist */
428 : };
429 : /* states: a combination of ACCT_INFO_STATE fields above. Used when
430 : ACTIVE. */
431 : uint states:8;
432 :
433 :
434 : /* We want to dispatch the READY transactions in an order that
435 : maximizes parallelism, but we also want to be able to start
436 : dispatching transactions decently well before we have the full
437 : conflict graph. We can do that because we know that contentious
438 : accounts tend to stay contentious and uncontentious accounts tend
439 : to stay uncontentious.
440 :
441 : To accomplish this, we maintain a special EMA. Let x_i be 1 if
442 : transaction i references it and 0 if not. If we squint and assume
443 : the transactions are independent and all drawn from some
444 : distribution (which is not true, but that's why we squint), an EMA
445 : of x_i estimates the probability that the next transaction
446 : references this account. How we use this value is detailed later.
447 :
448 : We can't update this value for every pubkey for each transaction,
449 : so we maintain it in a lazy way, by applying updates only when we
450 : need to read the value, which also happens to be every time we want
451 : to add a 1 value to the EMA. We then just need to maintain the
452 : last index i at which x_i was updated and the current value. We
453 : only have 24 bits for the index, which means that we can't maintain
454 : it in a fork-aware way, which doesn't seem like a problem. Also,
455 : it's possible it can overflow, and that can result in an incorrect
456 : value, but that means the account is only referenced ~ 1/2^24
457 : transactions, which is also fine.
458 :
459 : last_ref is in the domain of global_inserted_txn_cnt. ema_refs is
460 : in [0, 1]. Both fields are used in ACTIVE and CACHED. Maintaining
461 : these fields is actually the main reason CACHED exists. */
462 : uint last_ref:24;
463 : float ema_refs;
464 : };
465 : typedef struct acct_info acct_info_t;
466 :
467 : FD_STATIC_ASSERT( sizeof(acct_info_t)==64UL, acct_info_t );
468 :
469 : #define MAP_NAME acct_map
470 0 : #define MAP_ELE_T acct_info_t
471 14329 : #define MAP_IDX_T uint
472 : #define MAP_KEY_T fd_acct_addr_t
473 13318 : #define MAP_KEY_HASH(k,s) fd_hash32( (k)->b, (s) )
474 745 : #define MAP_KEY_EQ(k0,k1) (!memcmp( (k0)->b, (k1)->b, 32UL ))
475 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
476 : #include "../../util/tmpl/fd_map_chain.c"
477 :
478 :
479 : #define DLIST_IDX_T uint
480 820115985 : #define DLIST_PREV free_ll_prev
481 820115985 : #define DLIST_NEXT free_ll_next
482 : #define DLIST_NAME free_dlist
483 : #define DLIST_ELE_T acct_info_t
484 : #include "../../util/tmpl/fd_dlist.c"
485 :
486 :
487 : struct pending_prq_ele {
488 : /* lower score means should be scheduled sooner. Integer part has a
489 : special meaning as explained above. */
490 : float score;
491 :
492 : uint linear_block_number;
493 : uint txn_idx;
494 :
495 : /* It seems like we should be able to get this whole struct in 8
496 : bytes, but we're a few bits over.
497 :
498 : 23 bits for txn_idx
499 : 16 bit for linear_block_number
500 : Then the integer part of the score needs 20 bits. It is bounded by
501 : a block's inserted_cnt, which counts pseudo-transactions as well as
502 : transactions and is budgeted for up to
503 : FD_MAX_TXN_PER_SLOT+2*FD_RDISP_MAX_WRITERS_PER_BLOCK, just over
504 : 2^19. But we can't use a custom floating point number. */
505 : };
506 :
507 : typedef struct pending_prq_ele pending_prq_ele_t;
508 :
509 :
510 : #define PRQ_NAME pending_prq
511 1890 : #define PRQ_T pending_prq_ele_t
512 : #define PRQ_EXPLICIT_TIMEOUT 0
513 : /* returns 1 if x is strictly after y */
514 0 : #define PRQ_AFTER(x,y) (__extension__( { \
515 0 : int cmp0 = (int)(x).linear_block_number - (int)(y).linear_block_number; \
516 0 : fd_int_if( cmp0!=0, cmp0>0, (x).score>(y).score ); \
517 0 : }))
518 : #include "../../util/tmpl/fd_prq.c"
519 :
520 : /* We need yet another data structure to keep track of accounts that
521 : need LtHash addition tasks for unstaged transactions. These are part
522 : of a map keyed by (block, acct), as stored in ustlt_key_t so that we
523 : can quickly query whether the account address is "new" (in the sense
524 : explained in the header). In addition to possibly being part of the
525 : map, these are also part of one of several linked lists: FREE,
526 : NEEDED, CREATED. When in the CREATED state and list, there's a
527 : pseudo-txn with a last field pointing to it. When in the NEEDED
528 : state and list, it's part of the map_chain. Technically FREE could
529 : be an slist/fd_pool, but it's easier to reason about correctness when
530 : each element is in exactly one of three lists at all times. */
531 : typedef struct {
532 : uint block_idx;
533 : fd_acct_addr_t acct;
534 : } ustlt_key_t;
535 :
536 : struct ustlt {
537 : ustlt_key_t key;
538 : uint map_prev;
539 : uint map_next;
540 : uint ll_prev;
541 : uint ll_next;
542 : uint ptxn_idx; /* when CREATED */
543 : };
544 : typedef struct ustlt ustlt_t;
545 :
546 : #define MAP_NAME ustlt_map
547 0 : #define MAP_ELE_T ustlt_t
548 1008 : #define MAP_IDX_T uint
549 : #define MAP_KEY_T ustlt_key_t
550 0 : #define MAP_NEXT map_next
551 0 : #define MAP_PREV map_prev
552 0 : #define MAP_KEY_HASH(k,s) fd_hash32( (k)->acct.b, (s)+((k)->block_idx) )
553 0 : #define MAP_KEY_EQ(a,b) (0==memcmp( (a), (b), sizeof(ustlt_key_t) ))
554 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
555 : #include "../../util/tmpl/fd_map_chain.c"
556 :
557 : #define DLIST_NAME ustlt_dlist
558 : #define DLIST_ELE_T ustlt_t
559 : #define DLIST_IDX_T uint
560 908630161 : #define DLIST_PREV ll_prev
561 908630161 : #define DLIST_NEXT ll_next
562 : #include "../../util/tmpl/fd_dlist.c"
563 :
564 :
565 :
566 : /* fd_rdisp_blockinfo_t maintains a little metadata about transactions for each
567 : slot. */
568 : struct fd_rdisp_blockinfo {
569 : FD_RDISP_BLOCK_TAG_T block;
570 : uint linear_block_number;
571 :
572 : uint insert_ready:1;
573 : uint schedule_ready:1;
574 : uint staged:1;
575 : uint staging_lane:2; /* ignored if staged==0 */
576 : uint last_insert_was_serializing:1;
577 : uint inserted_extra_ptxn:1;
578 :
579 : uint inserted_cnt;
580 : uint dispatched_cnt;
581 : uint completed_cnt;
582 : uint last_serializing;
583 :
584 : uint map_chain_next;
585 : uint ll_next;
586 : zombie_dlist_t zombie_list[ 1 ];
587 : /* When unstaged: */
588 : unstaged_txn_ll_t ll[ 1 ];
589 : ustlt_dlist_t ustlt_needed[ 1 ];
590 : ustlt_dlist_t ustlt_created[ 1 ];
591 : };
592 : typedef struct fd_rdisp_blockinfo fd_rdisp_blockinfo_t;
593 :
594 : #define POOL_NAME block_pool
595 3024 : #define POOL_T fd_rdisp_blockinfo_t
596 : #define POOL_IDX_T uint
597 131915 : #define POOL_NEXT ll_next
598 : #define POOL_SENTINEL 1
599 : #include "../../util/tmpl/fd_pool.c"
600 :
601 : #define MAP_NAME block_map
602 : #define MAP_ELE_T fd_rdisp_blockinfo_t
603 : #define MAP_KEY_T FD_RDISP_BLOCK_TAG_T
604 1001 : #define MAP_KEY block
605 1003 : #define MAP_NEXT map_chain_next
606 6096 : #define MAP_IDX_T uint
607 : #include "../../util/tmpl/fd_map_chain.c"
608 :
609 : #define SLIST_NAME block_slist
610 : #define SLIST_ELE_T fd_rdisp_blockinfo_t
611 2 : #define SLIST_IDX_T uint
612 1003 : #define SLIST_NEXT ll_next
613 : #include "../../util/tmpl/fd_slist.c"
614 :
615 : struct fd_rdisp_unstaged {
616 : uint block_idx;
617 :
618 : uint writable_cnt;
619 : uint readonly_cnt;
620 : fd_acct_addr_t keys[FD_RDISP_MAX_ACCT_PER_TXN];
621 : };
622 : typedef struct fd_rdisp_unstaged fd_rdisp_unstaged_t;
623 :
624 :
625 :
626 : typedef struct {
627 : pending_prq_ele_t * pending;
628 : ulong linear_block_number;
629 : block_slist_t block_ll[1];
630 : ulong inserted_cnt;
631 : ulong dispatched_cnt;
632 : ulong completed_cnt;
633 : } per_lane_info_t;
634 :
635 : /* We maintain one map from pubkeys to acct_info_t, acct_map. The
636 : ACTIVE pubkeys in this map have >0 references in one of the staging
637 : lane DAGs. When an account goes to 0 references it stays in the map
638 : as CACHED, which exists to maintain the reference count EMA
639 : information lazily. Unless we need the acct_info_t for something in
640 : the DAG, we might as well maintain the EMA info.
641 :
642 : When we start up, all the acct_info_t structs are in the
643 : free_acct_dlist. Whenever something becomes CACHED, it's also added
644 : to the tail of the free_acct_dlist. When we need an acct_info_t for
645 : a pubkey that's not in the map, we pop the head of the
646 : free_acct_dlist, evicting it from the map if it was CACHED. In
647 : general, the free_acct_dlist contains everything CACHED, potentially
648 : plus some elements that have never been used; all acct_info_t objects
649 : are in at least one of acct_map and the free_acct_dlist. See
650 : acct_info_t for more information about this. */
651 :
652 : struct fd_rdisp {
653 : ulong depth;
654 : ulong block_depth;
655 : ulong acct_extra;
656 :
657 : ulong global_insert_cnt;
658 : ulong unstaged_lblk_num;
659 :
660 : /* pool: an fd_pool, indexed [0, depth+1), with 0 being a sentinel */
661 : fd_rdisp_txn_t * pool;
662 : fd_rdisp_unstaged_t * unstaged; /* parallel to pool with additional info */
663 : /* ptxn_pool: an fd_pool, also indexed [0, depth*128+1), with 0 as a
664 : sentinel. */
665 : fd_rdisp_ptxn_t * ptxn_pool;
666 : fd_rdisp_mq_t * mq;
667 :
668 : block_map_t * blockmap; /* map chain */
669 : fd_rdisp_blockinfo_t * block_pool;
670 :
671 : float ready_acct_ema_max;
672 :
673 : int free_lanes; /* a bitmask */
674 : per_lane_info_t lanes[4];
675 :
676 : acct_map_t * acct_map;
677 : /* acct_pool is not an fd_pool, but is just a flat array, since we
678 : don't need to acquire and release from it because of the dlist. */
679 : acct_info_t * acct_pool;
680 : free_dlist_t free_acct_dlist[1];
681 :
682 : /* Unfortunately, the LtHash info for unstaged transactions needs to
683 : be stored completely separately. */
684 : ustlt_t * ustlt_pool; /* a flat array, not an fd_pool */
685 : ustlt_map_t * ustlt_map;
686 : ustlt_dlist_t ustlt_free[ 1 ];
687 : };
688 :
689 : typedef struct fd_rdisp fd_rdisp_t;
690 :
691 :
692 : #define ACCT_ITER_TO_PTR( iter ) (__extension__( { \
693 : ulong __idx = fd_txn_acct_iter_idx( iter ); \
694 : fd_ptr_if( __idx<fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ), accts, alt_adj )+__idx; \
695 : }))
696 :
697 6039 : #define MAX_WRITERS_PER_BLOCK FD_RDISP_MAX_WRITERS_PER_BLOCK
698 :
699 34015 : ulong fd_rdisp_align( void ) { return 128UL; }
700 :
701 : ulong
702 : fd_rdisp_footprint( ulong depth,
703 : ulong block_depth,
704 3015 : ulong acct_extra ) {
705 3015 : if( FD_UNLIKELY( (depth>FD_RDISP_MAX_DEPTH) | (depth<2UL) |
706 3015 : (block_depth>FD_RDISP_MAX_BLOCK_DEPTH) | (block_depth<4UL) ) ) return 0UL;
707 3015 : ulong acct_depth = depth*FD_RDISP_MAX_ACCT_PER_TXN+acct_extra;
708 3015 : if( FD_UNLIKELY( acct_depth>EDGE_SPECIAL_IDX_MAX ) ) return 0UL; /* account indices are 30-bit special edges */
709 :
710 3015 : ulong chain_cnt = block_map_chain_cnt_est( block_depth );
711 : /* The map holds at most acct_depth entries, keep load factor at most
712 : 0.5 to speed up chain operations. */
713 3015 : ulong acct_chain_cnt = acct_map_chain_cnt_est( 2UL*acct_depth );
714 3015 : ulong mq_footprint = fd_rdisp_mq_footprint( acct_depth, MAX_WRITERS_PER_BLOCK );
715 3015 : ulong full_depth = depth+acct_depth; /* normal and pseudo transactions */
716 :
717 3015 : ulong l = FD_LAYOUT_INIT;
718 3015 : l = FD_LAYOUT_APPEND( l, fd_rdisp_align(), sizeof(fd_rdisp_t) );
719 3015 : l = FD_LAYOUT_APPEND( l, pool_align(), pool_footprint ( depth+1UL ) ); /* pool */
720 3015 : l = FD_LAYOUT_APPEND( l, alignof(fd_rdisp_unstaged_t), sizeof(fd_rdisp_unstaged_t)*( depth+1UL ) ); /* unstaged */
721 3015 : l = FD_LAYOUT_APPEND( l, ptxn_pool_align(), ptxn_pool_footprint ( acct_depth+1UL ) ); /* ptxn_pool */
722 3015 : l = FD_LAYOUT_APPEND( l, fd_rdisp_mq_align(), mq_footprint ); /* mq */
723 3015 : l = FD_LAYOUT_APPEND( l, block_map_align(), block_map_footprint ( chain_cnt ) ); /* blockmap */
724 3015 : l = FD_LAYOUT_APPEND( l, block_pool_align(), block_pool_footprint ( block_depth+1UL ) ); /* block_pool */
725 3015 : l = FD_LAYOUT_APPEND( l, pending_prq_align(), 4UL*pending_prq_footprint ( full_depth ) ); /* pending */
726 3015 : l = FD_LAYOUT_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) ); /* acct_map */
727 3015 : l = FD_LAYOUT_APPEND( l, alignof(acct_info_t), (acct_depth+1UL)*sizeof(acct_info_t) ); /* acct_pool */
728 3015 : l = FD_LAYOUT_APPEND( l, alignof(ustlt_t), (acct_depth+1UL)*sizeof(ustlt_t) ); /* ustlt_pool */
729 3015 : l = FD_LAYOUT_APPEND( l, ustlt_map_align(), ustlt_map_footprint ( acct_chain_cnt ) ); /* ustlt_map */
730 3015 : return FD_LAYOUT_FINI( l, fd_rdisp_align() );
731 3015 : }
732 :
733 : void *
734 : fd_rdisp_new( void * mem,
735 : ulong depth,
736 : ulong block_depth,
737 : ulong acct_extra,
738 1008 : ulong seed ) {
739 1008 : if( FD_UNLIKELY( (depth>FD_RDISP_MAX_DEPTH) | (depth<2UL) |
740 1008 : (block_depth>FD_RDISP_MAX_BLOCK_DEPTH) | (block_depth<4UL) ) ) return NULL;
741 1008 : ulong acct_depth = depth*FD_RDISP_MAX_ACCT_PER_TXN+acct_extra;
742 1008 : if( FD_UNLIKELY( acct_depth>EDGE_SPECIAL_IDX_MAX ) ) return NULL;
743 :
744 1008 : ulong chain_cnt = block_map_chain_cnt_est( block_depth );
745 1008 : ulong acct_chain_cnt = acct_map_chain_cnt_est( 2UL*acct_depth ); /* see fd_rdisp_footprint */
746 1008 : ulong mq_footprint = fd_rdisp_mq_footprint( acct_depth, MAX_WRITERS_PER_BLOCK );
747 1008 : ulong full_depth = depth+acct_depth;
748 :
749 1008 : FD_SCRATCH_ALLOC_INIT( l, mem );
750 1008 : fd_rdisp_t * disp = FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_align(), sizeof(fd_rdisp_t) );
751 1008 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( depth+1UL ) );
752 1008 : void * _unstaged = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_rdisp_unstaged_t), sizeof(fd_rdisp_unstaged_t)*( depth+1UL ) );
753 1008 : void * _ptxn_pool = FD_SCRATCH_ALLOC_APPEND( l, ptxn_pool_align(), ptxn_pool_footprint ( acct_depth+1UL ) );
754 1008 : void * _mq = FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_mq_align(), mq_footprint );
755 1008 : void * _bmap = FD_SCRATCH_ALLOC_APPEND( l, block_map_align(), block_map_footprint ( chain_cnt ) );
756 1008 : void * _bpool = FD_SCRATCH_ALLOC_APPEND( l, block_pool_align(), block_pool_footprint ( block_depth+1UL ) );
757 1008 : uchar * _pending = FD_SCRATCH_ALLOC_APPEND( l, pending_prq_align(), 4UL*pending_prq_footprint ( full_depth ) );
758 1008 : void * _acct_map = FD_SCRATCH_ALLOC_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) );
759 1008 : acct_info_t * apool = FD_SCRATCH_ALLOC_APPEND( l, alignof(acct_info_t), (acct_depth+1UL)*sizeof(acct_info_t) );
760 1008 : ustlt_t * upool = FD_SCRATCH_ALLOC_APPEND( l, alignof(ustlt_t), (acct_depth+1UL)*sizeof(ustlt_t) );
761 1008 : void * _ustlt_map = FD_SCRATCH_ALLOC_APPEND( l, ustlt_map_align(), ustlt_map_footprint ( acct_chain_cnt ) );
762 1008 : FD_SCRATCH_ALLOC_FINI( l, fd_rdisp_align() );
763 :
764 1008 : disp->depth = depth;
765 1008 : disp->block_depth = block_depth;
766 1008 : disp->acct_extra = acct_extra;
767 1008 : disp->global_insert_cnt = 0UL;
768 1008 : disp->unstaged_lblk_num = 0UL;
769 :
770 1008 : fd_rdisp_txn_t * temp_pool_join = pool_join( pool_new( _pool, depth+1UL ) );
771 3933125 : for( ulong i=0UL; i<depth+1UL; i++ ) temp_pool_join[ i ].in_degree = IN_DEGREE_FREE;
772 1008 : pool_leave( temp_pool_join );
773 :
774 1008 : memset( _unstaged, '\0', sizeof(fd_rdisp_unstaged_t)*(depth+1UL) );
775 :
776 1008 : fd_rdisp_ptxn_t * temp_ppool_join = ptxn_pool_join( ptxn_pool_new( _ptxn_pool, acct_depth+1UL ) );
777 989334745 : for( ulong i=0UL; i<acct_depth+1UL; i++ ) temp_ppool_join[ i ].in_degree = IN_DEGREE_FREE;
778 1008 : ptxn_pool_leave( temp_ppool_join );
779 :
780 1008 : fd_rdisp_mq_new( _mq, acct_depth, MAX_WRITERS_PER_BLOCK );
781 :
782 1008 : block_map_new ( _bmap, chain_cnt, seed );
783 1008 : block_pool_new( _bpool, block_depth+1UL );
784 :
785 1008 : fd_rdisp_blockinfo_t * bpool_temp_join = block_pool_join( _bpool );
786 130461 : for( ulong i=0UL; i<block_depth+1UL; i++ ) zombie_dlist_new( bpool_temp_join[ i ].zombie_list );
787 1008 : block_pool_leave( bpool_temp_join );
788 :
789 1008 : disp->ready_acct_ema_max = FD_RDISP_READY_ACCT_EMA_MAX;
790 :
791 1008 : disp->free_lanes = 0xF;
792 5040 : for( ulong i=0UL; i<4UL; i++ ) {
793 4032 : pending_prq_new( _pending, full_depth );
794 4032 : _pending += pending_prq_footprint( full_depth );
795 :
796 4032 : disp->lanes[i].linear_block_number = 0UL;
797 4032 : disp->lanes[i].inserted_cnt = 0U;
798 4032 : disp->lanes[i].dispatched_cnt = 0U;
799 4032 : disp->lanes[i].completed_cnt = 0U;
800 4032 : }
801 :
802 1008 : acct_map_new( _acct_map, acct_chain_cnt, fd_ulong_hash( seed+1UL ) );
803 :
804 1008 : free_dlist_t * temp_join = free_dlist_join( free_dlist_new( disp->free_acct_dlist ) );
805 807338343 : for( ulong i=1UL; i<acct_depth+1UL; i++ ) {
806 807337335 : apool[ i ].next = apool[ i ].prev = 0U;
807 807337335 : free_dlist_idx_push_tail( disp->free_acct_dlist, i, apool );
808 807337335 : }
809 1008 : free_dlist_leave( temp_join );
810 :
811 1008 : ustlt_map_new( _ustlt_map, acct_chain_cnt, fd_ulong_hash( seed+3UL ) );
812 :
813 1008 : ustlt_dlist_t * temp_join_ustlt = ustlt_dlist_join( ustlt_dlist_new( disp->ustlt_free ) );
814 903644319 : for( ulong i=1UL; i<acct_depth+1UL; i++ ) {
815 903643311 : upool[ i ].ll_next = upool[ i ].ll_prev = 0U;
816 903643311 : ustlt_dlist_idx_push_tail( disp->ustlt_free, i, upool );
817 903643311 : }
818 1008 : ustlt_dlist_leave( temp_join_ustlt );
819 :
820 :
821 1008 : return disp;
822 1008 : }
823 :
824 : fd_rdisp_t *
825 1008 : fd_rdisp_join( void * mem ) {
826 1008 : fd_rdisp_t * disp = (fd_rdisp_t *)mem;
827 :
828 1008 : ulong depth = disp->depth;
829 1008 : ulong block_depth = disp->block_depth;
830 1008 : ulong chain_cnt = block_map_chain_cnt_est( block_depth );
831 1008 : ulong acct_depth = depth*FD_RDISP_MAX_ACCT_PER_TXN+disp->acct_extra;
832 1008 : ulong acct_chain_cnt = acct_map_chain_cnt_est( 2UL*acct_depth ); /* see fd_rdisp_footprint */
833 1008 : ulong mq_footprint = fd_rdisp_mq_footprint( acct_depth, MAX_WRITERS_PER_BLOCK );
834 1008 : ulong full_depth = depth+acct_depth;
835 :
836 1008 : FD_SCRATCH_ALLOC_INIT( l, mem );
837 1008 : /* */ FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_align(), sizeof(fd_rdisp_t) );
838 1008 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( depth+1UL ) );
839 1008 : void * _unstaged = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_rdisp_unstaged_t), sizeof(fd_rdisp_unstaged_t)*( depth+1UL ) );
840 1008 : void * _ptxn_pool = FD_SCRATCH_ALLOC_APPEND( l, ptxn_pool_align(), ptxn_pool_footprint ( acct_depth+1UL ) );
841 1008 : void * _mq = FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_mq_align(), mq_footprint );
842 1008 : void * _bmap = FD_SCRATCH_ALLOC_APPEND( l, block_map_align(), block_map_footprint ( chain_cnt ) );
843 1008 : void * _bpool = FD_SCRATCH_ALLOC_APPEND( l, block_pool_align(), block_pool_footprint ( block_depth+1UL ) );
844 1008 : uchar * _pending = FD_SCRATCH_ALLOC_APPEND( l, pending_prq_align(), 4UL*pending_prq_footprint ( full_depth ) );
845 1008 : void * _acct_map = FD_SCRATCH_ALLOC_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) );
846 1008 : acct_info_t * apool = FD_SCRATCH_ALLOC_APPEND( l, alignof(acct_info_t), (acct_depth+1UL)*sizeof(acct_info_t) );
847 1008 : ustlt_t * upool = FD_SCRATCH_ALLOC_APPEND( l, alignof(ustlt_t), (acct_depth+1UL)*sizeof(ustlt_t) );
848 1008 : void * _ustlt_map = FD_SCRATCH_ALLOC_APPEND( l, ustlt_map_align(), ustlt_map_footprint ( acct_chain_cnt ) );
849 1008 : FD_SCRATCH_ALLOC_FINI( l, fd_rdisp_align() );
850 :
851 1008 : disp->pool = pool_join( _pool );
852 1008 : disp->unstaged = (fd_rdisp_unstaged_t *)_unstaged;
853 1008 : disp->ptxn_pool = ptxn_pool_join( _ptxn_pool );
854 1008 : disp->mq = fd_rdisp_mq_join( _mq );
855 1008 : disp->blockmap = block_map_join( _bmap );
856 1008 : disp->block_pool = block_pool_join( _bpool );
857 :
858 131040 : for( ulong i=0UL; i<block_depth+1UL; i++ ) zombie_dlist_join( disp->block_pool[ i ].zombie_list );
859 :
860 5040 : for( ulong i=0UL; i<4UL; i++ ) {
861 4032 : disp->lanes[i].pending = pending_prq_join( _pending );
862 4032 : _pending += pending_prq_footprint( full_depth );
863 4032 : }
864 :
865 1008 : disp->acct_map = acct_map_join( _acct_map );
866 1008 : disp->acct_pool = apool;
867 1008 : free_dlist_join( disp->free_acct_dlist );
868 :
869 1008 : disp->ustlt_pool = upool;
870 1008 : disp->ustlt_map = ustlt_map_join( _ustlt_map );
871 1008 : ustlt_dlist_join( disp->ustlt_free );
872 :
873 1008 : return disp;
874 1008 : }
875 :
876 : static inline void
877 : free_lane( fd_rdisp_t * disp,
878 2 : ulong staging_lane ) {
879 2 : disp->free_lanes |= 1<<staging_lane;
880 2 : per_lane_info_t * l = disp->lanes+staging_lane;
881 2 : FD_TEST( pending_prq_cnt( l->pending )==0UL );
882 2 : l->linear_block_number = 0UL;
883 2 : l->inserted_cnt = 0UL;
884 2 : l->dispatched_cnt = 0UL;
885 2 : l->completed_cnt = 0UL;
886 2 : block_slist_delete( block_slist_leave( l->block_ll ) );
887 2 : }
888 :
889 : static inline void
890 : alloc_lane( fd_rdisp_t * disp,
891 1001 : ulong staging_lane ) {
892 1001 : disp->free_lanes &= ~(1<<staging_lane);
893 1001 : block_slist_join( block_slist_new( disp->lanes[staging_lane].block_ll ) );
894 1001 : }
895 :
896 : ulong
897 : fd_rdisp_suggest_staging_lane( fd_rdisp_t const * disp,
898 : FD_RDISP_BLOCK_TAG_T parent_block,
899 0 : int duplicate ) {
900 :
901 : /* 1. If it's a duplicate, suggest FD_RDISP_UNSTAGED */
902 0 : if( FD_UNLIKELY( duplicate ) ) return FD_RDISP_UNSTAGED;
903 :
904 : /* 2. If parent is the last block in any existing staging lane, suggest
905 : that lane */
906 0 : fd_rdisp_blockinfo_t const * block_pool = disp->block_pool;
907 0 : fd_rdisp_blockinfo_t const * block = block_map_ele_query_const( disp->blockmap, &parent_block, NULL, block_pool );
908 0 : if( FD_LIKELY( block && block->insert_ready && block->staged ) ) return block->staging_lane;
909 :
910 : /* 3. If there is at least one free lane, suggest a free lane */
911 0 : if( FD_LIKELY( disp->free_lanes!=0 ) ) return (ulong)fd_uint_find_lsb( (uint)disp->free_lanes );
912 :
913 : /* 4. Else, suggest FD_RDISP_UNSTAGED */
914 0 : return FD_RDISP_UNSTAGED;
915 0 : }
916 :
917 : int
918 : fd_rdisp_add_block( fd_rdisp_t * disp,
919 : FD_RDISP_BLOCK_TAG_T new_block,
920 1001 : ulong staging_lane ) {
921 1001 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
922 :
923 1001 : if( FD_UNLIKELY( !block_pool_free( block_pool ) ) ) return -1;
924 1001 : if( FD_UNLIKELY( ULONG_MAX!=block_map_idx_query_const( disp->blockmap, &new_block, ULONG_MAX, block_pool ) ) ) return -1;
925 1001 : fd_rdisp_blockinfo_t * block = block_pool_ele_acquire( block_pool );
926 1001 : block->block = new_block;
927 1001 : block_map_ele_insert( disp->blockmap, block, block_pool );
928 :
929 1001 : block->insert_ready = 1;
930 1001 : block->staged = staging_lane!=FD_RDISP_UNSTAGED;
931 1001 : block->staging_lane = (uint)(staging_lane & 0x3UL);
932 1001 : block->last_insert_was_serializing = 0U;
933 1001 : block->inserted_extra_ptxn = 0U;
934 :
935 1001 : block->inserted_cnt = 0U;
936 1001 : block->dispatched_cnt = 0U;
937 1001 : block->completed_cnt = 0U;
938 1001 : block->last_serializing = 0U;
939 :
940 1001 : if( FD_UNLIKELY( staging_lane==FD_RDISP_UNSTAGED ) ) {
941 0 : block->schedule_ready = 1;
942 0 : block->linear_block_number = (uint)disp->unstaged_lblk_num++;
943 0 : unstaged_txn_ll_join( unstaged_txn_ll_new( block->ll ) );
944 0 : ustlt_dlist_join( ustlt_dlist_new ( block->ustlt_needed ) );
945 0 : ustlt_dlist_join( ustlt_dlist_new ( block->ustlt_created ) );
946 1001 : } else {
947 1001 : block->linear_block_number = (uint)disp->lanes[staging_lane].linear_block_number++;
948 1001 : block->schedule_ready = (uint)(1 & (disp->free_lanes >> staging_lane));
949 :
950 1001 : if( FD_LIKELY( disp->free_lanes & (1<<staging_lane) ) ) alloc_lane( disp, staging_lane );
951 :
952 1001 : block_slist_t * sl = disp->lanes[staging_lane].block_ll;
953 1001 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_tail( sl, block_pool )->insert_ready = 0;
954 1001 : block_slist_ele_push_tail( sl, block, block_pool );
955 1001 : }
956 1001 : return 0;
957 1001 : }
958 :
959 :
960 :
961 : int
962 : fd_rdisp_remove_block( fd_rdisp_t * disp,
963 0 : FD_RDISP_BLOCK_TAG_T block_tag ) {
964 0 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
965 :
966 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, block_pool );
967 0 : if( FD_UNLIKELY( block==NULL ) ) return -1;
968 :
969 0 : FD_TEST( block->schedule_ready );
970 0 : FD_TEST( block->completed_cnt==block->inserted_cnt );
971 0 : FD_TEST( zombie_dlist_is_empty( block->zombie_list, disp->pool ) );
972 :
973 0 : if( FD_LIKELY( block->staged ) ) {
974 0 : ulong staging_lane = (ulong)block->staging_lane;
975 0 : block_slist_t * sl = disp->lanes[staging_lane].block_ll;
976 :
977 0 : FD_TEST( block==block_slist_ele_peek_head( sl, block_pool ) );
978 0 : block_slist_idx_pop_head( sl, block_pool );
979 0 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_head( sl, block_pool )->schedule_ready = 1;
980 0 : else free_lane( disp, staging_lane );
981 0 : } else {
982 0 : FD_TEST( ustlt_dlist_is_empty( block->ustlt_needed, disp->ustlt_pool ) && ustlt_dlist_is_empty( block->ustlt_created, disp->ustlt_pool ) );
983 0 : unstaged_txn_ll_delete( unstaged_txn_ll_leave( block->ll ) );
984 0 : ustlt_dlist_delete ( ustlt_dlist_leave ( block->ustlt_needed ) );
985 0 : ustlt_dlist_delete ( ustlt_dlist_leave ( block->ustlt_created ) );
986 0 : }
987 0 : block_pool_idx_release( block_pool, block_map_idx_remove( disp->blockmap, &block_tag, ULONG_MAX, block_pool ) );
988 :
989 0 : return 0;
990 0 : }
991 :
992 :
993 : int
994 : fd_rdisp_abandon_block( fd_rdisp_t * disp,
995 2 : FD_RDISP_BLOCK_TAG_T block_tag ) {
996 2 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
997 :
998 2 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, disp->block_pool );
999 2 : if( FD_UNLIKELY( block==NULL ) ) return -1;
1000 :
1001 2 : FD_TEST( block->schedule_ready );
1002 2 : FD_TEST( block->dispatched_cnt==block->completed_cnt ); /* TODO: remove this when it can call complete properly */
1003 2 : while( block->completed_cnt<block->inserted_cnt ) {
1004 : /* because there is nothing DISPATCHED, there has to be something
1005 : READY */
1006 0 : ulong txn = fd_rdisp_get_next_ready( disp, block_tag );
1007 0 : FD_TEST( txn );
1008 0 : fd_rdisp_complete_txn( disp, txn, 1 );
1009 0 : }
1010 2 : while( !zombie_dlist_is_empty( block->zombie_list, disp->pool ) ) {
1011 : /* rdisp_complete_txn removes the peeked head */
1012 0 : fd_rdisp_complete_txn( disp, zombie_dlist_idx_peek_head( block->zombie_list, disp->pool ), 1 );
1013 0 : }
1014 :
1015 2 : if( FD_LIKELY( block->staged ) ) {
1016 2 : ulong staging_lane = (ulong)block->staging_lane;
1017 :
1018 2 : block_slist_t * sl = disp->lanes[staging_lane].block_ll;
1019 :
1020 2 : FD_TEST( block==block_slist_ele_peek_head( sl, block_pool ) );
1021 2 : block_slist_idx_pop_head( sl, block_pool );
1022 2 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_head( sl, block_pool )->schedule_ready = 1;
1023 2 : else {
1024 : /* It's schedule-ready, so it's possible there are some accounts
1025 : in the NEEDS_PTXN state (add writer, schedule, complete it).
1026 : However, if it's not insert-ready, then we know the caller
1027 : would already have created the pseudo-transactions if they were
1028 : needed, so we don't need to do anything in that case. */
1029 2 : while( fd_rdisp_mq_cnt( disp->mq, staging_lane ) ) {
1030 0 : ulong acct_idx = fd_rdisp_mq_pop( disp->mq, staging_lane );
1031 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
1032 0 : uint s = ai->states;
1033 0 : if( FD_UNLIKELY( ACCT_INFO_STATE_IS(s, staging_lane, NEEDS_PTXN) ) ) {
1034 0 : ai->states = (uchar)ACCT_INFO_STATE_SET(s, staging_lane, NO_WRITERS);
1035 :
1036 : /* Potentially transition from ACTIVE -> CACHED */
1037 0 : if( FD_UNLIKELY( (ai->states==0)&
1038 0 : (ai->last_reference[ 0 ]==0U)&(ai->last_reference[ 1 ]==0U)&
1039 0 : (ai->last_reference[ 2 ]==0U)&(ai->last_reference[ 3 ]==0U) ) ) {
1040 0 : ai->cached = ACCT_INFO_CACHED;
1041 0 : free_dlist_idx_push_tail( disp->free_acct_dlist, acct_idx, disp->acct_pool );
1042 0 : }
1043 0 : }
1044 0 : }
1045 :
1046 2 : free_lane( disp, staging_lane );
1047 2 : }
1048 2 : } else {
1049 0 : while( !ustlt_dlist_is_empty( block->ustlt_created, disp->ustlt_pool ) ) {
1050 0 : ustlt_t * ele = ustlt_dlist_ele_peek_head( block->ustlt_created, disp->ustlt_pool );
1051 : /* Free the created ones */
1052 0 : fd_rdisp_ptxn_t * ptxn = disp->ptxn_pool + EDGE_SPECIAL_IDX( ele->ptxn_idx );
1053 0 : ptxn->in_degree = IN_DEGREE_FREE;
1054 0 : ptxn_pool_ele_release( disp->ptxn_pool, ptxn );
1055 :
1056 0 : ustlt_dlist_ele_remove ( block->ustlt_created, ele, disp->ustlt_pool );
1057 0 : ustlt_dlist_ele_push_tail( disp->ustlt_free, ele, disp->ustlt_pool );
1058 0 : }
1059 :
1060 0 : while( !ustlt_dlist_is_empty( block->ustlt_needed, disp->ustlt_pool ) ) {
1061 0 : ustlt_t * ele = ustlt_dlist_ele_peek_head( block->ustlt_needed, disp->ustlt_pool );
1062 0 : ustlt_dlist_ele_remove ( block->ustlt_needed, ele, disp->ustlt_pool );
1063 0 : ustlt_map_ele_remove_fast( disp->ustlt_map, ele, disp->ustlt_pool );
1064 0 : ustlt_dlist_ele_push_tail( disp->ustlt_free, ele, disp->ustlt_pool );
1065 0 : }
1066 :
1067 0 : unstaged_txn_ll_delete( unstaged_txn_ll_leave( block->ll ) );
1068 0 : ustlt_dlist_delete ( ustlt_dlist_leave ( block->ustlt_needed ) );
1069 0 : ustlt_dlist_delete ( ustlt_dlist_leave ( block->ustlt_created ) );
1070 0 : }
1071 2 : block_pool_idx_release( disp->block_pool, block_map_idx_remove( disp->blockmap, &block_tag, ULONG_MAX, disp->block_pool ) );
1072 :
1073 2 : return 0;
1074 2 : }
1075 :
1076 : static void
1077 : add_edges( fd_rdisp_t * disp,
1078 : fd_rdisp_txn_t * ele,
1079 : fd_acct_addr_t const * addr,
1080 : ulong addr_cnt,
1081 : uint staging_lane,
1082 : int writable,
1083 : int update_score,
1084 : fd_rdisp_neww_t * new_wr,
1085 : ulong new_wr_offset );
1086 : /* updates in_degree, edge_cnt_etc */
1087 :
1088 :
1089 : static inline ulong
1090 : lookup_pubkey( fd_rdisp_t * disp,
1091 : fd_acct_addr_t const * addr );
1092 :
1093 : static void
1094 : untrack_writer( fd_rdisp_t * disp,
1095 : ulong staging_lane,
1096 0 : ulong acct_idx ) {
1097 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
1098 0 : uint s = ai->states;
1099 0 : if( FD_UNLIKELY( ACCT_INFO_STATE_IS(s, staging_lane, NEEDS_PTXN) ) ) {
1100 0 : ai->states = (uchar)ACCT_INFO_STATE_SET(s, staging_lane, NO_WRITERS);
1101 :
1102 : /* Potentially transition from ACTIVE -> CACHED */
1103 0 : if( FD_UNLIKELY( (ai->states==0)&
1104 0 : (ai->last_reference[ 0 ]==0U)&(ai->last_reference[ 1 ]==0U)&
1105 0 : (ai->last_reference[ 2 ]==0U)&(ai->last_reference[ 3 ]==0U) ) ) {
1106 0 : ai->cached = ACCT_INFO_CACHED;
1107 0 : free_dlist_idx_push_tail( disp->free_acct_dlist, acct_idx, disp->acct_pool );
1108 0 : }
1109 0 : }
1110 0 : }
1111 :
1112 : /* Priority of an account in a lane's writable set. An account whose
1113 : every writer in the block has completed, so that an addition
1114 : pseudo-transaction for it would be READY on creation, is ready and
1115 : sits at priority 0 if its reference EMA is under the threshold.
1116 : Every other account waits at 1 plus its EMA, so the coldest comes out
1117 : first. An account over the threshold is considered hot enough to
1118 : likely be written again before the block ends, so a speculative
1119 : addition on it would likely have to be undone. */
1120 : static inline float
1121 : mq_prio( fd_rdisp_t const * disp,
1122 : acct_info_t const * ai,
1123 2889 : int ready ) {
1124 2889 : return fd_float_if( ready && ai->ema_refs<disp->ready_acct_ema_max, 0.0f, 1.0f+ai->ema_refs );
1125 2889 : }
1126 :
1127 : int
1128 : fd_rdisp_promote_block( fd_rdisp_t * disp,
1129 : FD_RDISP_BLOCK_TAG_T block_tag,
1130 0 : ulong staging_lane ) {
1131 0 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
1132 0 : per_lane_info_t * lane = disp->lanes + staging_lane;
1133 0 : block_slist_t * sl = lane->block_ll;
1134 :
1135 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, block_pool );
1136 0 : if( FD_UNLIKELY( block==NULL ) ) return -1;
1137 0 : if( FD_UNLIKELY( block->staged ) ) return -1;
1138 :
1139 0 : block->staged = 1;
1140 0 : block->staging_lane = (uint)(staging_lane & 0x3);
1141 0 : block->insert_ready = 1;
1142 0 : block->schedule_ready = (uint)(1 & (disp->free_lanes >> staging_lane));
1143 :
1144 0 : if( FD_LIKELY( disp->free_lanes & (1<<staging_lane) ) ) alloc_lane( disp, staging_lane );
1145 :
1146 0 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_tail( sl, block_pool )->insert_ready = 0;
1147 0 : block_slist_ele_push_tail( sl, block, block_pool );
1148 0 : uint linear_block_number = (uint)lane->linear_block_number++;
1149 0 : block->linear_block_number = linear_block_number;
1150 :
1151 0 : unstaged_txn_ll_iter_t next;
1152 0 : for( unstaged_txn_ll_iter_t iter = unstaged_txn_ll_iter_init( block->ll, disp->pool );
1153 0 : !unstaged_txn_ll_iter_done( iter, block->ll, disp->pool );
1154 0 : iter = next ) {
1155 0 : next = unstaged_txn_ll_iter_next( iter, block->ll, disp->pool );
1156 :
1157 0 : fd_rdisp_txn_t * ele = unstaged_txn_ll_iter_ele( iter, block->ll, disp->pool );
1158 0 : fd_rdisp_unstaged_t * uns = disp->unstaged + unstaged_txn_ll_iter_idx( iter, block->ll, disp->pool );
1159 0 : FD_TEST( ele->in_degree==IN_DEGREE_UNSTAGED );
1160 :
1161 0 : ele->in_degree = 0U;
1162 0 : ele->edge_cnt_etc = (uint)(-1); /* set w_cnt_1 to -1 */
1163 :
1164 : /* Ignore LtHash accounts here since we have the precise list in
1165 : ustlt_needed. */
1166 0 : add_edges( disp, ele, uns->keys, uns->writable_cnt, (uint)staging_lane, 1, 0, NULL, 0UL );
1167 0 : add_edges( disp, ele, uns->keys+uns->writable_cnt, uns->readonly_cnt, (uint)staging_lane, 0, 0, NULL, 0UL );
1168 :
1169 0 : ele->edge_cnt_etc &= 0x3FFFU;
1170 0 : ele->edge_cnt_etc |= (uint)staging_lane<<14;
1171 0 : ele->edge_cnt_etc |= linear_block_number<<16;
1172 :
1173 0 : if( FD_UNLIKELY( ele->in_degree==0U ) ) {
1174 0 : pending_prq_ele_t temp[1] = {{ .score = ele->score, .linear_block_number = linear_block_number, .txn_idx = (uint)(ele-disp->pool)}};
1175 0 : pending_prq_insert( lane->pending, temp );
1176 0 : }
1177 0 : }
1178 0 : unstaged_txn_ll_delete( unstaged_txn_ll_leave( block->ll ) );
1179 :
1180 : /* Any pseudo-transactions created while the block was unstaged must
1181 : have completed by now. Freeing them here would invalidate indices
1182 : the caller still holds. */
1183 0 : FD_TEST( ustlt_dlist_is_empty( block->ustlt_created, disp->ustlt_pool ) );
1184 :
1185 0 : while( !ustlt_dlist_is_empty( block->ustlt_needed, disp->ustlt_pool ) ) {
1186 0 : ustlt_t * ele = ustlt_dlist_ele_peek_head( block->ustlt_needed, disp->ustlt_pool );
1187 :
1188 0 : ulong acct_idx = lookup_pubkey( disp, &(ele->key.acct) );
1189 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
1190 : /* If it's NO_WRITERS, we need to transition to NEEDS_PTXN, but
1191 : otherwise it's fine. */
1192 0 : uint s = ai->states;
1193 0 : s = fd_uint_if( ACCT_INFO_STATE_IS(s, staging_lane, NO_WRITERS), ACCT_INFO_STATE_SET(s, staging_lane, NEEDS_PTXN), s );
1194 0 : ai->states = (uchar)s;
1195 :
1196 0 : if( FD_UNLIKELY( fd_rdisp_mq_cnt( disp->mq, staging_lane )>=MAX_WRITERS_PER_BLOCK ) ) FD_LOG_CRIT(( "rdisp lane %lu writable account set full", staging_lane ));
1197 0 : fd_rdisp_mq_insert( disp->mq, acct_idx, staging_lane, mq_prio( disp, ai, ACCT_INFO_STATE_IS( s, staging_lane, NEEDS_PTXN ) ) );
1198 :
1199 0 : ustlt_dlist_ele_remove ( block->ustlt_needed, ele, disp->ustlt_pool );
1200 0 : ustlt_map_ele_remove_fast( disp->ustlt_map, ele, disp->ustlt_pool );
1201 0 : ustlt_dlist_ele_push_tail( disp->ustlt_free, ele, disp->ustlt_pool );
1202 0 : }
1203 :
1204 0 : lane->inserted_cnt += block->inserted_cnt;
1205 0 : lane->dispatched_cnt += block->dispatched_cnt;
1206 0 : lane->completed_cnt += block->completed_cnt;
1207 :
1208 0 : return 0;
1209 0 : }
1210 :
1211 : int
1212 : fd_rdisp_demote_block( fd_rdisp_t * disp,
1213 0 : FD_RDISP_BLOCK_TAG_T block_tag ) {
1214 0 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
1215 :
1216 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, block_pool );
1217 0 : if( FD_UNLIKELY( block==NULL ) ) return -1;
1218 0 : if( FD_UNLIKELY( !block->staged ) ) return -1;
1219 0 : if( FD_UNLIKELY( !block->schedule_ready ) ) return -1;
1220 0 : if( FD_UNLIKELY( block->completed_cnt!=block->inserted_cnt ) ) FD_LOG_ERR(( "demote_block called with non-empty block" ));
1221 0 : ulong staging_lane = block->staging_lane;
1222 0 : block->staged = 0;
1223 :
1224 0 : per_lane_info_t * lane = disp->lanes + staging_lane;
1225 0 : block_slist_t * sl = lane->block_ll;
1226 :
1227 0 : lane->inserted_cnt -= block->inserted_cnt;
1228 0 : lane->dispatched_cnt -= block->dispatched_cnt;
1229 0 : lane->completed_cnt -= block->completed_cnt;
1230 :
1231 0 : block->linear_block_number = (uint)disp->unstaged_lblk_num++;
1232 :
1233 : /* staged and schedule_ready means it must be the head of the staging lane */
1234 0 : FD_TEST( block_slist_ele_peek_head( sl, block_pool )==block );
1235 0 : block_slist_idx_pop_head( sl, block_pool );
1236 :
1237 0 : unstaged_txn_ll_join( unstaged_txn_ll_new( block->ll ) );
1238 0 : ustlt_dlist_join( ustlt_dlist_new ( block->ustlt_needed ) );
1239 0 : ustlt_dlist_join( ustlt_dlist_new ( block->ustlt_created ) );
1240 :
1241 :
1242 0 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_head( sl, block_pool )->schedule_ready = 1;
1243 0 : else {
1244 : /* If it was insert-ready, we need to carry over the LtHash addition
1245 : information. If it wasn't, then that information should have
1246 : been encoded in the created LtHash addition tasks, but the block
1247 : can't contain any PENDING transactions by contract... */
1248 0 : while( fd_rdisp_mq_cnt( disp->mq, staging_lane ) ) {
1249 0 : ulong acct_idx = fd_rdisp_mq_pop( disp->mq, staging_lane );
1250 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
1251 :
1252 0 : if( FD_UNLIKELY( ustlt_dlist_is_empty( disp->ustlt_free, disp->ustlt_pool ) ) ) FD_LOG_CRIT(( "rdisp unstaged LtHash entry pool exhausted" ));
1253 0 : ulong ustlt_idx = ustlt_dlist_idx_pop_head( disp->ustlt_free, disp->ustlt_pool );
1254 0 : disp->ustlt_pool[ ustlt_idx ].key.acct = ai->key;
1255 0 : disp->ustlt_pool[ ustlt_idx ].key.block_idx = (uint)(block-block_pool);
1256 0 : ustlt_map_idx_insert( disp->ustlt_map, ustlt_idx, disp->ustlt_pool );
1257 0 : ustlt_dlist_idx_push_tail( block->ustlt_needed, ustlt_idx, disp->ustlt_pool );
1258 :
1259 0 : untrack_writer( disp, staging_lane, acct_idx );
1260 0 : }
1261 0 : free_lane( disp, staging_lane );
1262 0 : }
1263 0 : return 0;
1264 0 : }
1265 :
1266 : int
1267 : fd_rdisp_clear_writable_set( fd_rdisp_t * disp,
1268 0 : FD_RDISP_BLOCK_TAG_T block_tag ) {
1269 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, disp->block_pool );
1270 0 : if( FD_UNLIKELY( block==NULL ) ) return -1;
1271 0 : if( FD_UNLIKELY( !block->staged ) ) return -1;
1272 0 : if( FD_UNLIKELY( !block->schedule_ready ) ) return -1;
1273 0 : ulong staging_lane = block->staging_lane;
1274 0 : while( fd_rdisp_mq_cnt( disp->mq, staging_lane ) ) untrack_writer( disp, staging_lane, fd_rdisp_mq_pop( disp->mq, staging_lane ) );
1275 0 : return 0;
1276 0 : }
1277 :
1278 : int
1279 : fd_rdisp_rekey_block( fd_rdisp_t * disp,
1280 : FD_RDISP_BLOCK_TAG_T new_tag,
1281 0 : FD_RDISP_BLOCK_TAG_T old_tag ) {
1282 0 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
1283 :
1284 0 : if( FD_UNLIKELY( NULL!= block_map_ele_query_const( disp->blockmap, &new_tag, NULL, block_pool ) ) ) return -1;
1285 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query ( disp->blockmap, &old_tag, NULL, block_pool );
1286 0 : if( FD_UNLIKELY( NULL== block ) ) return -1;
1287 :
1288 0 : block_map_idx_remove( disp->blockmap, &old_tag, ULONG_MAX, block_pool );
1289 0 : block->block = new_tag;
1290 0 : block_map_ele_insert( disp->blockmap, block, block_pool );
1291 0 : return 0;
1292 0 : }
1293 :
1294 :
1295 : /* "Registers" a reference to the account in info at transaction
1296 : global_insert_cnt. Returns the value of the EMA, which is an
1297 : estimate of the probability that the next transaction also references
1298 : the account. This value does not matter for correctness, other than
1299 : that it is in [0, 1), which is why floating point arithmetic is
1300 : acceptable here. */
1301 : static inline float
1302 : update_ema( acct_info_t * info,
1303 4688 : ulong global_insert_cnt ) {
1304 : #if FD_RDISP_DISABLE_EMA
1305 : (void)info;
1306 : (void)global_insert_cnt;
1307 : return 0.0f;
1308 : #else
1309 9376 : #define ALPHA 0.005f
1310 : /* The normal EMA update equation is
1311 : e_i = (alpha) * x_i + (1-alpha)*e_{i-1},
1312 : where alpha is a constant in (0,1). Let L be the last reference of
1313 : the account, and G be the current global_insert_cnt value. We know
1314 : that e_L = ema_refs, and that for i in [L+1, G), x_i = 0.
1315 : That means
1316 : e_{G-1} = (1-alpha)^(G-L-1) * ema_refs
1317 : e_G = alpha + (1-alpha)^(G-L) * ema_refs
1318 : */
1319 : /* last_ref only captures the low 24 bits, so we guess its the highest
1320 : value for them that would still make it less than
1321 : global_insert_cnt. Turns out, we can calculate that with just an
1322 : AND. We need to make sure that in the rare case it is actually
1323 : 2^24 away, we don't use a delta of 0. We also want to make sure
1324 : that even with inexact float math, we never get to 1.0, so we bias
1325 : the exponent up slightly. */
1326 4688 : ulong last_ref = (ulong)info->last_ref;
1327 4688 : ulong delta = fd_ulong_max( (global_insert_cnt - last_ref) & 0xFFFFFFUL, 1UL );
1328 4688 : float ema_refs = ALPHA + powf( 1.0f-ALPHA, 0.05f+(float)delta ) * info->ema_refs;
1329 :
1330 4688 : info->ema_refs = ema_refs;
1331 4688 : info->last_ref = (uint)(global_insert_cnt & 0xFFFFFFUL);
1332 4688 : #undef ALPHA
1333 :
1334 4688 : return ema_refs;
1335 4688 : #endif
1336 4688 : }
1337 :
1338 : /* Finds addr in acct_map, making it ACTIVE if it isn't already */
1339 : static inline ulong
1340 : lookup_pubkey( fd_rdisp_t * disp,
1341 4689 : fd_acct_addr_t const * addr ) {
1342 :
1343 4689 : ulong idx = acct_map_idx_query( disp->acct_map, addr, ULONG_MAX, disp->acct_pool );
1344 4689 : acct_info_t * ai = NULL;
1345 4689 : if( FD_LIKELY( idx!=ULONG_MAX ) ) {
1346 745 : ai = disp->acct_pool+idx;
1347 745 : if( FD_LIKELY( ai->cached!=ACCT_INFO_CACHED ) ) return idx;
1348 :
1349 : /* CACHED -> ACTIVE transition. It has the right key. last_ref,
1350 : and ema_refs are valid. states was zeroed when it was cached. */
1351 0 : free_dlist_idx_remove( disp->free_acct_dlist, idx, disp->acct_pool );
1352 0 : memset( ai->last_reference, '\0', sizeof(ai->last_reference) );
1353 0 : return idx;
1354 745 : }
1355 :
1356 : /* The acct pool is sized so that the list cannot be empty at this
1357 : point. However, the element at the head might be CACHED with
1358 : a different pubkey. */
1359 3944 : if( FD_UNLIKELY( free_dlist_is_empty( disp->free_acct_dlist, disp->acct_pool ) ) ) FD_LOG_CRIT(( "rdisp account pool exhausted" ));
1360 3944 : idx = free_dlist_idx_peek_head( disp->free_acct_dlist, disp->acct_pool );
1361 3944 : ai = disp->acct_pool+idx;
1362 :
1363 : /* CACHED -> FREE transition */
1364 3944 : if( FD_LIKELY( ai->next!=0U ) ) {
1365 0 : acct_map_idx_remove_fast( disp->acct_map, idx, disp->acct_pool );
1366 0 : }
1367 :
1368 : /* FREE -> ACTIVE transition */
1369 3944 : ai->key = *addr;
1370 3944 : ai->states = 0U;
1371 3944 : ai->last_ref = 0U;
1372 3944 : ai->ema_refs = 0.0f;
1373 3944 : free_dlist_idx_remove( disp->free_acct_dlist, idx, disp->acct_pool );
1374 3944 : memset( ai->last_reference, '\0', sizeof(ai->last_reference) );
1375 3944 : acct_map_idx_insert( disp->acct_map, idx, disp->acct_pool );
1376 :
1377 3944 : return idx;
1378 3944 : }
1379 :
1380 : static void
1381 : add_edges( fd_rdisp_t * disp,
1382 : fd_rdisp_txn_t * ele,
1383 : fd_acct_addr_t const * addrs,
1384 : ulong addr_cnt,
1385 : uint lane,
1386 : int writable,
1387 : int update_score,
1388 : fd_rdisp_neww_t * new_wr,
1389 6166 : ulong new_wr_offset ) {
1390 : /* When we first start, the low 14 bits are 0x3FFF, so that gives us
1391 : w_cnt==0, r_cnt==0, as desired. Then otherwise, the low 7 bits are
1392 : w_cnt_1, so adding 1 gives w_cnt. If we've actually added
1393 : MAX_ACCT_PER_TXN writable accounts, then r_cnt will be incorrect,
1394 : but then we actually can't add any more readonly accounts, so the
1395 : function call will be a no-op. */
1396 :
1397 6166 : ulong w_cnt = (ele->edge_cnt_etc + 1U) & 0x7FU;
1398 6166 : ulong r_cnt = ((ele->edge_cnt_etc + 1U)>>7) & 0x7FU;
1399 6166 : ulong acct_idx = w_cnt + r_cnt;
1400 6166 : ulong edge_idx = w_cnt + 3UL*r_cnt;
1401 :
1402 10855 : for( ulong i=0UL; i<addr_cnt; i++ ) {
1403 4689 : fd_acct_addr_t const * addr = addrs+i;
1404 4689 : acct_info_t * ai = NULL;
1405 :
1406 : /* Step 1: lookup the pubkey */
1407 4689 : ulong idx = lookup_pubkey( disp, addr );
1408 4689 : ai = disp->acct_pool+idx;
1409 : /* At this point, in all cases, the acct_info is now in the ACTIVE
1410 : state. It's in acct_map and not in free_acct_dlist. */
1411 :
1412 : /* Assume that transactions are drawn randomly from some large
1413 : distribution of potential transactions. We want to estimate the
1414 : expected value of the probability that this transaction conflicts
1415 : with the next transaction that is sampled. Two transactions
1416 : conflict if they conflict on any account, and in general, they
1417 : conflict if they both reference the same account, unless both
1418 : this transaction and the next one only read it. We don't have
1419 : read/write info, so the best guess we have is that the next
1420 : transaction does the same thing to the account that this one
1421 : does. That means we only really care about the accounts that
1422 : this transaction writes to. Label those a_1, a_2, ..., a_i, and
1423 : suppose the probability that the next transaction references a_i
1424 : is p_i (determined using the EMA). Now then, assuming accounts
1425 : are independent (which is false, but whatever), then the
1426 : probability that the next transaction does not conflict with this
1427 : account is:
1428 : (1-p_1) * (1-p_2) * (1 - p_i).
1429 :
1430 : Since for the treap, a lower value means we'll schedule it
1431 : earlier, we'll use the probability of non-conflict as the
1432 : fractional part of the score. */
1433 4689 : if( FD_LIKELY( update_score ) ) {
1434 4688 : float score_change = 1.0f - update_ema( ai, disp->global_insert_cnt );
1435 4688 : ele->score *= fd_float_if( writable, score_change, 1.0f );
1436 4688 : }
1437 :
1438 : /* Step 2: add edge. There are 4 cases depending on whether this is
1439 : a writer or not and whether the previous reference was a writer
1440 : or not. */
1441 4689 : int _ignore;
1442 :
1443 4689 : edge_t ref_to_pa = ai->last_reference[ lane ];
1444 4689 : ulong displ0 = ((ulong)ele - (ulong)disp->pool )/sizeof(fd_rdisp_txn_t);
1445 4689 : ulong displ1 = ((ulong)ele - (ulong)disp->ptxn_pool)/sizeof(fd_rdisp_ptxn_t);
1446 4689 : edge_t ref_to_me = (uint)fd_ulong_if( displ0>disp->depth, EDGE_MAKE_SPECIAL(PTXN, displ1), (displ0<<8)|acct_idx );
1447 4689 : edge_t * pa = FOLLOW_EDGE( disp, ai->last_reference[ lane ], _ignore );
1448 4689 : edge_t * me = ele->edges + edge_idx;
1449 :
1450 : /* In the case that this is the first txn in the DAG, pa will point
1451 : to edges[0] of the sentinel element, pool[0]. We don't care
1452 : about what is stored there, so just set it up as a dummy element
1453 : to make the rest of the code work properly in this case too. If
1454 : this is a read, we want me->sibli to ref_to_me in case 4; if this
1455 : is a write, we want to set me->sibli to 0 in case 2, but we need
1456 : to make sure pb==pa. */
1457 4689 : disp->pool->edges[0] = EDGE_MAKE_SPECIAL(LAST, (uint)idx);
1458 4689 : disp->pool->edges[1] = fd_uint_if( writable, 0U, ref_to_me );
1459 4689 : disp->pool->edges[2] = fd_uint_if( writable, 0U, ref_to_me );
1460 :
1461 4689 : int states = ai->states;
1462 :
1463 4689 : if( writable ) { /* also should be known at compile time */
1464 3112 : if( ACCT_INFO_STATE_IS( states, lane, LAST_REF_WAS_WRITE ) ) { /* unclear prob */
1465 : /* Case 1: w-w. The parent is the special last pointer. Point
1466 : the parent to me, and set me to the last pointer. */
1467 224 : *me = *pa;
1468 224 : *pa = ref_to_me;
1469 2888 : } else {
1470 : /* Case 2: r-w. This is the tricky case because there could be
1471 : multiple readers. We need to set all the last readers' child
1472 : pointers to me. */
1473 2888 : *me = *pa;
1474 2888 : *pa = ref_to_me;
1475 2888 : edge_t * pb = FOLLOW_EDGE( disp, pa[1], _ignore );
1476 : /* Intentionally skip the first in_degree increment, because it
1477 : will be done later */
1478 2888 : while( pb!=pa ) {
1479 0 : *pb = ref_to_me;
1480 0 : ele->in_degree++;
1481 0 : pb = FOLLOW_EDGE( disp, pb[1], _ignore );
1482 0 : }
1483 2888 : states = ACCT_INFO_STATE_SET( states, lane, LAST_REF_WAS_WRITE );
1484 2888 : }
1485 : /* An account in the ready class is getting rewritten. So we bump
1486 : it out of the ready class. */
1487 3112 : if( fd_rdisp_mq_test( disp->mq, idx, lane ) && fd_rdisp_mq_test_prio0( disp->mq, idx, lane ) ) fd_rdisp_mq_adjust( disp->mq, idx, lane, mq_prio( disp, ai, 0 ) );
1488 3112 : } else {
1489 1577 : if( ACCT_INFO_STATE_IS( states, lane, LAST_REF_WAS_WRITE ) ) { /* unclear prob */
1490 : /* Case 3: w-r. Similar to case 1, but need to initialize my
1491 : next and prev sibling pointers too. */
1492 0 : *me = *pa;
1493 0 : *pa = ref_to_me;
1494 0 : me[1] = ref_to_me; /* next */
1495 0 : me[2] = ref_to_me; /* prev */
1496 0 : states = ACCT_INFO_STATE_SET( states, lane, LAST_REF_WAS_READ );
1497 1577 : } else {
1498 : /* Case 4: r-r. Add myself as a sibling instead of a child */
1499 1577 : *me = *pa;
1500 1577 : FOLLOW_EDGE( disp, pa[1], _ignore )[2] = ref_to_me; /* prev->next->prev = me */
1501 1577 : me[1] = pa[1]; /* me->next = prev->next */
1502 1577 : me[2] = ref_to_pa; /* me->prev = prev */
1503 1577 : pa[1] = ref_to_me; /* prev->next = me */
1504 1577 : }
1505 1577 : }
1506 :
1507 : /* Step 3: Update new_wr */
1508 4689 : if( ((!!writable) & FD_LIKELY( !!new_wr )) && !fd_rdisp_mq_test( disp->mq, idx, lane ) ) {
1509 2889 : if( FD_UNLIKELY( fd_rdisp_mq_cnt( disp->mq, lane )>=MAX_WRITERS_PER_BLOCK ) ) FD_LOG_CRIT(( "rdisp lane %u writable account set full", lane ));
1510 2889 : fd_rdisp_mq_insert( disp->mq, idx, lane, mq_prio( disp, ai, 0 ) );
1511 2889 : fd_rdisp_neww_insert( new_wr, new_wr_offset+i );
1512 2889 : }
1513 :
1514 : /* Step 4: Update the final values */
1515 : /* In general, we want to increment the in_degree unless this
1516 : transaction is the first to reference this account. The
1517 : exception is that if this account has only readers, including
1518 : this transaction, we don't want to increment the in_degree
1519 : either. At this point, we can tell if that is the case based on
1520 : states. */
1521 4689 : int any_write = ACCT_INFO_STATE_IS( states, lane, LAST_REF_WAS_READ ) | ACCT_INFO_STATE_IS( states, lane, LAST_REF_WAS_WRITE );
1522 4689 : ele->in_degree += (uint)((ai->last_reference[ lane ]!=0U) & any_write);
1523 4689 : ai->last_reference[ lane ] = ref_to_me;
1524 4689 : ai->states = (uchar)states;
1525 4689 : edge_idx += fd_uint_if( writable, 1U, 3U );
1526 4689 : acct_idx++;
1527 4689 : }
1528 : /* Can't overflow by construction, except for the intentional overflow on the first time. */
1529 6166 : ele->edge_cnt_etc += (uint)addr_cnt<<fd_int_if( writable, 0, 7 );
1530 6166 : }
1531 :
1532 :
1533 : /* should be called with all writable accounts first */
1534 : static void
1535 : add_unstaged_edges( fd_rdisp_t * disp,
1536 : fd_rdisp_txn_t * ele,
1537 : fd_rdisp_unstaged_t * unstaged,
1538 : fd_acct_addr_t const * addr,
1539 : ulong addr_cnt,
1540 : int writable,
1541 : int update_score,
1542 : fd_rdisp_neww_t * new_wr,
1543 0 : ulong new_wr_offset ) {
1544 0 : ulong base_idx = unstaged->writable_cnt+unstaged->readonly_cnt;
1545 0 : FD_TEST( !writable || unstaged->readonly_cnt==0U );
1546 0 : for( ulong i=0UL; i<addr_cnt; i++ ) {
1547 0 : unstaged->keys[ base_idx+i ] = addr[i];
1548 0 : if( FD_LIKELY( update_score ) ) {
1549 0 : ulong idx = acct_map_idx_query( disp->acct_map, addr+i, ULONG_MAX, disp->acct_pool );
1550 : /* since these are unstaged, we don't bother moving accounts
1551 : around */
1552 0 : float score_change = 1.0f;
1553 0 : if( FD_LIKELY( idx!=ULONG_MAX ) ) score_change = 1.0f - update_ema( disp->acct_pool+idx, disp->global_insert_cnt );
1554 0 : ele->score *= fd_float_if( writable & update_score, score_change, 1.0f );
1555 0 : }
1556 0 : if( ((!!writable) & FD_LIKELY( !!new_wr )) ) {
1557 0 : ustlt_key_t query[1] = {{
1558 0 : .block_idx = unstaged->block_idx,
1559 0 : .acct = addr[i]
1560 0 : }};
1561 0 : int new = (ustlt_map_idx_query( disp->ustlt_map, query, ULONG_MAX, disp->ustlt_pool )==ULONG_MAX);
1562 0 : fd_rdisp_neww_insert_if( new_wr, new, new_wr_offset+i );
1563 0 : if( FD_UNLIKELY( new ) ) {
1564 0 : if( FD_UNLIKELY( ustlt_dlist_is_empty( disp->ustlt_free, disp->ustlt_pool ) ) ) FD_LOG_CRIT(( "rdisp unstaged LtHash entry pool exhausted" ));
1565 0 : ulong ustlt_idx = ustlt_dlist_idx_pop_head( disp->ustlt_free, disp->ustlt_pool );
1566 0 : disp->ustlt_pool[ ustlt_idx ].key = *query;
1567 0 : ustlt_map_idx_insert( disp->ustlt_map, ustlt_idx, disp->ustlt_pool );
1568 0 : ustlt_dlist_idx_push_tail( disp->block_pool[ unstaged->block_idx ].ustlt_needed, ustlt_idx, disp->ustlt_pool );
1569 0 : }
1570 0 : }
1571 0 : }
1572 0 : *(fd_ptr_if( writable, &(unstaged->writable_cnt), &(unstaged->readonly_cnt) ) ) += (uint)addr_cnt;
1573 0 : }
1574 :
1575 : /* prefetch_accts warms what add_edges (or add_unstaged_edges) touches
1576 : first for each of the cnt addresses: the chain head of each account,
1577 : then the element at the head of each chain, which is where the key
1578 : compare of a hit usually lands (queries move the found element to the
1579 : front). The map is large enough that these are otherwise serial
1580 : cache misses, one account at a time. The free list head, which a
1581 : miss takes, is warmed by the caller. Hints only: the queries below
1582 : are unchanged.
1583 :
1584 : always_inline is load bearing: this only loads and prefetches, and
1585 : gcc treats __builtin_prefetch as side effect free, so it finds the
1586 : function to be (looping) pure and deletes the call, prefetches and
1587 : all. Clang keeps the prefetches but only inlines by heuristic. */
1588 :
1589 : static inline __attribute__((always_inline)) void
1590 : prefetch_accts( fd_rdisp_t const * disp,
1591 : fd_acct_addr_t const * addrs,
1592 1541 : ulong cnt ) {
1593 1541 : uint const * heads[ MAX_ACCT_PER_TXN ];
1594 1541 : uint const * chain = acct_map_private_chain_const( disp->acct_map );
1595 1541 : ulong seed = acct_map_seed ( disp->acct_map );
1596 1541 : ulong chain_cnt = acct_map_chain_cnt( disp->acct_map );
1597 6226 : for( ulong i=0UL; i<cnt; i++ ) {
1598 4685 : heads[ i ] = chain + acct_map_private_chain_idx( addrs+i, seed, chain_cnt );
1599 4685 : __builtin_prefetch( heads[ i ], 0, 3 );
1600 4685 : }
1601 6225 : for( ulong i=0UL; i<cnt; i++ ) {
1602 4684 : ulong head = (ulong)*heads[ i ];
1603 4684 : __builtin_prefetch( disp->acct_pool + fd_ulong_if( head==UINT_MAX, 0UL, head ), 0, 3 );
1604 4684 : }
1605 1541 : }
1606 :
1607 : ulong
1608 3084 : fd_rdisp_peek_free_txn( fd_rdisp_t const * disp ) {
1609 3084 : ulong idx = pool_private_meta_const( disp->pool )->free_top;
1610 3084 : return fd_ulong_if( idx==pool_idx_null( disp->pool ), 0UL, idx );
1611 3084 : }
1612 :
1613 : ulong
1614 : fd_rdisp_add_txn( fd_rdisp_t * disp,
1615 : FD_RDISP_BLOCK_TAG_T insert_block,
1616 : fd_txn_t const * txn,
1617 : uchar const * payload,
1618 : fd_acct_addr_t const * alts,
1619 : int serializing,
1620 1540 : fd_rdisp_neww_t * new_writable ) {
1621 1540 : if( FD_LIKELY( new_writable ) ) fd_rdisp_neww_new( new_writable ); /* clear it */
1622 :
1623 1540 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &insert_block, NULL, disp->block_pool );
1624 1540 : if( FD_UNLIKELY( !block || !block->insert_ready ) ) return 0UL;
1625 1540 : if( FD_UNLIKELY( !pool_free( disp->pool ) ) ) return 0UL;
1626 :
1627 1540 : fd_acct_addr_t const * imm_addrs = fd_txn_get_acct_addrs( txn, payload );
1628 :
1629 1540 : /* */ prefetch_accts( disp, imm_addrs, fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ) );
1630 1540 : if( FD_LIKELY( alts ) ) prefetch_accts( disp, alts, fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALT ) );
1631 1540 : __builtin_prefetch( disp->acct_pool + free_dlist_idx_peek_head( disp->free_acct_dlist, disp->acct_pool ), 1, 3 );
1632 :
1633 1540 : ulong idx = pool_idx_acquire( disp->pool );
1634 1540 : fd_rdisp_txn_t * rtxn = disp->pool + idx;
1635 1540 : if( FD_UNLIKELY( rtxn->in_degree!=IN_DEGREE_FREE ) ) FD_LOG_CRIT(( "pool[%lu].in_degree==%u but free", idx, rtxn->in_degree ));
1636 :
1637 : /* The element the next add_txn takes (unless a completion pushes a
1638 : recently touched one first) is the next cold line in this path. */
1639 1540 : __builtin_prefetch( disp->pool + fd_rdisp_peek_free_txn( disp ), 1, 3 );
1640 :
1641 1540 : ulong ws = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_SIGNER );
1642 1540 : ulong rs = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_SIGNER );
1643 1540 : ulong wn = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_NONSIGNER_IMM );
1644 1540 : ulong rn = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_NONSIGNER_IMM );
1645 1540 : ulong wa = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_ALT );
1646 1540 : ulong ra = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_ALT );
1647 :
1648 1540 : if( FD_UNLIKELY( !block->staged ) ) {
1649 0 : rtxn->in_degree = IN_DEGREE_UNSTAGED;
1650 0 : rtxn->score = 1.0f;
1651 :
1652 0 : fd_rdisp_unstaged_t * unstaged = disp->unstaged + idx;
1653 0 : unstaged->block_idx = (uint)(block-disp->block_pool);
1654 0 : unstaged->writable_cnt = 0U;
1655 0 : unstaged->readonly_cnt = 0U;
1656 :
1657 0 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs, ws, 1, 1, new_writable, 0UL );
1658 0 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs+ws+rs, wn, 1, 1, new_writable, ws+rs );
1659 0 : if( FD_LIKELY( alts ) )
1660 0 : add_unstaged_edges( disp, rtxn, unstaged, alts, wa, 1, 1, new_writable, ws+rs+wn+rn );
1661 0 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs+ws, rs, 0, 1, new_writable, ws );
1662 0 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs+ws+rs+wn, rn, 0, 1, new_writable, ws+rs+wn );
1663 0 : if( FD_LIKELY( alts ) )
1664 0 : add_unstaged_edges( disp, rtxn, unstaged, alts+wa, ra, 0, 1, new_writable, ws+rs+wn+rn+wa );
1665 :
1666 0 : unstaged_txn_ll_ele_push_tail( block->ll, rtxn, disp->pool );
1667 1540 : } else {
1668 1540 : uint lane = block->staging_lane;
1669 :
1670 1540 : rtxn->in_degree = 0U;
1671 1540 : rtxn->score = 1.0f;
1672 : /* There's not a good way to initialize w_cnt_1 to -1, which is what
1673 : it should be at this point, but this is close. We must be sure
1674 : to add at least one writer (which we are assured of because we
1675 : know the transaction passed fd_txn_parse) to correct this value. */
1676 1540 : rtxn->edge_cnt_etc = ((block->linear_block_number<<16) | (lane<<14)) - 1U;
1677 :
1678 1540 : add_edges( disp, rtxn, imm_addrs, ws, lane, 1, 1, new_writable, 0UL );
1679 1540 : add_edges( disp, rtxn, imm_addrs+ws+rs, wn, lane, 1, 1, new_writable, ws+rs );
1680 1540 : if( FD_LIKELY( alts ) )
1681 0 : add_edges( disp, rtxn, alts, wa, lane, 1, 1, new_writable, ws+rs+wn+rn );
1682 1540 : add_edges( disp, rtxn, imm_addrs+ws, rs, lane, 0, 1, new_writable, ws );
1683 1540 : add_edges( disp, rtxn, imm_addrs+ws+rs+wn, rn, lane, 0, 1, new_writable, ws+rs+wn );
1684 1540 : if( FD_LIKELY( alts ) )
1685 0 : add_edges( disp, rtxn, alts+wa, ra, lane, 0, 1, new_writable, ws+rs+wn+rn+wa );
1686 1540 : }
1687 1540 : if( FD_UNLIKELY( rtxn->score>FD_RDISP_MAX_SCORE ) ) rtxn->score=FD_RDISP_MAX_SCORE;
1688 :
1689 1540 : if( FD_UNLIKELY( serializing | block->last_insert_was_serializing ) ) {
1690 0 : block->last_serializing = block->inserted_cnt;
1691 0 : }
1692 1540 : block->last_insert_was_serializing = (uint)!!serializing;
1693 1540 : rtxn->score = fd_rdisp_score( rtxn->score, block->last_serializing );
1694 :
1695 1540 : block->inserted_cnt++;
1696 1540 : disp->global_insert_cnt++;
1697 :
1698 1540 : if( FD_LIKELY( (block->staged) & (rtxn->in_degree==0U) ) ) {
1699 1430 : pending_prq_ele_t temp[1] = {{ .score = rtxn->score, .linear_block_number = block->linear_block_number, .txn_idx = (uint)idx }};
1700 1430 : pending_prq_insert( disp->lanes[ block->staging_lane ].pending, temp );
1701 1430 : }
1702 :
1703 1540 : return idx;
1704 1540 : }
1705 :
1706 : ulong
1707 : fd_rdisp_get_next_ready( fd_rdisp_t * disp,
1708 0 : FD_RDISP_BLOCK_TAG_T schedule_block ) {
1709 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &schedule_block, NULL, disp->block_pool );
1710 0 : if( FD_UNLIKELY( !block || !block->schedule_ready ) ) return 0UL;
1711 :
1712 0 : ulong idx;
1713 0 : if( FD_LIKELY( block->staged ) ) {
1714 0 : ulong staging_lane = block->staging_lane;
1715 0 : per_lane_info_t * l = disp->lanes + staging_lane;
1716 :
1717 0 : if( FD_UNLIKELY( !pending_prq_cnt( l->pending ) ) ) return 0UL;
1718 0 : if( FD_UNLIKELY( l->pending->linear_block_number != block->linear_block_number ) ) return 0UL;
1719 : /* e.g. when completed_cnt==0, we can accept any score below 1.0 */
1720 0 : if( FD_UNLIKELY( l->pending->score>=(float)(block->completed_cnt+1U) ) ) return 0UL;
1721 0 : idx = l->pending->txn_idx;
1722 0 : pending_prq_remove_min( l->pending );
1723 0 : if( FD_UNLIKELY( EDGE_IS_PTXN(idx) ) ) disp->ptxn_pool[ EDGE_SPECIAL_IDX( idx ) ].in_degree = IN_DEGREE_DISPATCHED;
1724 0 : else disp->pool [ idx ].in_degree = IN_DEGREE_DISPATCHED;
1725 0 : } else {
1726 0 : if( FD_UNLIKELY( block->dispatched_cnt!=block->completed_cnt ) ) return 0UL;
1727 0 : if( FD_UNLIKELY( !unstaged_txn_ll_is_empty( block->ll, disp->pool ) ) ) {
1728 0 : idx = unstaged_txn_ll_idx_peek_head( block->ll, disp->pool );
1729 0 : disp->pool[ idx ].in_degree = IN_DEGREE_UNSTAGED_DISPATCHED;
1730 0 : } else if( FD_UNLIKELY( !ustlt_dlist_is_empty( block->ustlt_created, disp->ustlt_pool ) ) ) {
1731 0 : idx = ustlt_dlist_ele_peek_head( block->ustlt_created, disp->ustlt_pool )->ptxn_idx;
1732 0 : disp->ptxn_pool[ idx ].in_degree = IN_DEGREE_UNSTAGED_DISPATCHED;
1733 0 : idx = EDGE_MAKE_SPECIAL(PTXN, idx);
1734 0 : } else {
1735 0 : return 0UL;
1736 0 : }
1737 0 : }
1738 0 : block->dispatched_cnt++;
1739 :
1740 0 : return idx;
1741 0 : }
1742 :
1743 : void
1744 : fd_rdisp_complete_txn( fd_rdisp_t * disp,
1745 : ulong txn_idx,
1746 0 : int reclaim ) {
1747 :
1748 0 : int ptxn = EDGE_IS_PTXN( txn_idx );
1749 0 : fd_rdisp_txn_t * rtxn = (!ptxn) ? disp->pool + txn_idx :
1750 0 : (fd_rdisp_txn_t *)fd_type_pun( (disp->ptxn_pool + EDGE_SPECIAL_IDX(txn_idx)) );
1751 0 : fd_rdisp_blockinfo_t * block = NULL;
1752 :
1753 0 : if( FD_UNLIKELY( rtxn->in_degree==IN_DEGREE_UNSTAGED_DISPATCHED ) ) {
1754 : /* Unstaged */
1755 0 : if( FD_UNLIKELY( ptxn ) ) {
1756 0 : fd_rdisp_ptxn_t * ptxn_e = disp->ptxn_pool + EDGE_SPECIAL_IDX(txn_idx); /* == rtxn */
1757 0 : ustlt_t * ustlt_ele = disp->ustlt_pool + ptxn_e->last;
1758 0 : block = disp->block_pool + ustlt_ele->key.block_idx;
1759 0 : FD_TEST( ustlt_ele==ustlt_dlist_ele_pop_head( block->ustlt_created, disp->ustlt_pool ) );
1760 : /* ptxn_e gets freed below */
1761 0 : ustlt_dlist_ele_push_tail( disp->ustlt_free, ustlt_ele, disp->ustlt_pool );
1762 :
1763 0 : } else {
1764 0 : block = disp->block_pool + disp->unstaged[ txn_idx ].block_idx;
1765 0 : FD_TEST( rtxn==unstaged_txn_ll_ele_peek_head( block->ll, disp->pool ) );
1766 0 : unstaged_txn_ll_ele_pop_head( block->ll, disp->pool );
1767 0 : }
1768 0 : block->completed_cnt++;
1769 0 : } else if( FD_LIKELY( rtxn->in_degree==IN_DEGREE_DISPATCHED ) ) {
1770 : /* Staged */
1771 0 : ulong w_cnt = fd_ulong_if( ptxn, 0UL, 1UL + ((rtxn->edge_cnt_etc ) & 0x7FU) );
1772 0 : ulong r_cnt = (rtxn->edge_cnt_etc>> 7) & 0x7FU;
1773 0 : ulong lane = (rtxn->edge_cnt_etc>>14) & 0x3U;
1774 0 : uint tail_linear_block_num = (uint)(disp->lanes[lane].linear_block_number);
1775 0 : ulong edge_idx = 0UL;
1776 0 : for( ulong i=0UL; i<w_cnt+r_cnt; i++ ) {
1777 0 : edge_t const * e = rtxn->edges+edge_idx;
1778 0 : edge_t const e0 = *e;
1779 0 : edge_t ref_to_me = (uint)fd_ulong_if( ptxn, txn_idx, ((txn_idx<<8) | i) );
1780 :
1781 : /* To help with explanations, consider the following DAG:
1782 :
1783 : --> B --\ --> E --\
1784 : / V / V
1785 : A D (G)
1786 : \ ^ \ ^
1787 : --> C --/ --> F --/ */
1788 :
1789 0 : if( FD_UNLIKELY( EDGE_IS_LAST( e0 ) ) ) {
1790 0 : ulong acct_idx = EDGE_SPECIAL_IDX( e0 );
1791 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
1792 : /* If this is a writer, e.g. node G above, we know it's the last
1793 : one, so we can clear last_reference. We know it has to go to
1794 : the NEEDS_PTXN state unless LtHash tracking was disabled for it.
1795 : If this is a reader, e.g. node E and F above, if node G
1796 : didn't exist, we need to check if it's the last one
1797 : (me==me->next). If so, we can clear last_reference. If not,
1798 : we need to delete this node from the linked list. In either
1799 : case, there are only readers or pseudo-transactions, so we're
1800 : either in NO_WRITERS or NEEDS_PTXN states, and we stay in
1801 : that state. */
1802 0 : if( edge_idx<w_cnt ) {
1803 0 : ai->last_reference[ lane ] = 0U;
1804 0 : int needs_ptxn = fd_rdisp_mq_test( disp->mq, acct_idx, lane );
1805 0 : ai->states = fd_uchar_if( needs_ptxn, ACCT_INFO_STATE_SET(ai->states, lane, NEEDS_PTXN), ACCT_INFO_STATE_SET(ai->states, lane, NO_WRITERS) );
1806 : /* The account's last writer is done, so we bump it into the
1807 : ready class, hotness threshold permitting. */
1808 0 : if( needs_ptxn && ai->ema_refs<disp->ready_acct_ema_max ) fd_rdisp_mq_adjust( disp->mq, acct_idx, lane, 0.0f );
1809 0 : } else if( e[1]==ref_to_me ) {
1810 0 : ai->last_reference[ lane ] = 0U;
1811 0 : } else {
1812 0 : int _ignore;
1813 0 : FOLLOW_EDGE( disp, e[1], _ignore )[2] = e[2]; /* me->next->prev = me->prev */
1814 0 : FOLLOW_EDGE( disp, e[2], _ignore )[1] = e[1]; /* me->prev->next = me->next */
1815 0 : ai->last_reference[ lane ]= fd_uint_if( ai->last_reference[ lane ]==ref_to_me, e[1], ai->last_reference[ lane ] );
1816 0 : }
1817 :
1818 : /* Potentially transition from ACTIVE -> CACHED */
1819 0 : if( FD_UNLIKELY( (ai->states==0)&
1820 0 : (ai->last_reference[ 0 ]==0U)&(ai->last_reference[ 1 ]==0U)&
1821 0 : (ai->last_reference[ 2 ]==0U)&(ai->last_reference[ 3 ]==0U) ) ) {
1822 0 : ai->cached = ACCT_INFO_CACHED;
1823 0 : free_dlist_idx_push_tail( disp->free_acct_dlist, acct_idx, disp->acct_pool );
1824 0 : }
1825 0 : } else {
1826 0 : int child_is_writer;
1827 :
1828 0 : edge_t next_e = e0;
1829 0 : edge_t const * child_edge;
1830 0 : while( 1 ) {
1831 : /* This loop first traverses the me->child link, and then
1832 : traverses any sibling links. For example, in the case that
1833 : we're completing node D above, the first child_txn is E,
1834 : and the second child_txn is F. child_txn might be a
1835 : pseudo-transaction. */
1836 0 : /* */ child_edge = FOLLOW_EDGE( disp, next_e, child_is_writer );
1837 0 : fd_rdisp_txn_t * child_txn = FOLLOW_EDGE_TXN( disp, next_e );
1838 :
1839 : /* Sanity test */
1840 0 : FD_TEST( child_txn->in_degree>0U );
1841 0 : FD_TEST( child_txn->in_degree<IN_DEGREE_DISPATCHED );
1842 :
1843 0 : if( FD_UNLIKELY( 0U==(--(child_txn->in_degree)) ) ) {
1844 : /* We need an operation something like
1845 : fd_frag_meta_ts_decomp. child_txn has the low 16 bits,
1846 : and tail_linear_block_num has the full 32 bits, except
1847 : for tail_linear_block_num refers to a block < block_depth
1848 : later. Since block_depth<2^16, that means we can resolve
1849 : this unambiguously. Basically, we copy the high 16 bits
1850 : frorm tail_linear_block_num unless that would make
1851 : linear_block_num larger than tail_linear_block_num, in
1852 : which case, we subtract 2^16. */
1853 0 : uint low_16_bits = child_txn->edge_cnt_etc>>16;
1854 0 : uint linear_block_num = ((tail_linear_block_num & ~0xFFFFU) | low_16_bits) - (uint)((low_16_bits>(tail_linear_block_num&0xFFFFU))<<16);
1855 0 : pending_prq_ele_t temp[1] = {{ .score = child_txn->score,
1856 0 : .linear_block_number = linear_block_num,
1857 0 : .txn_idx = fd_uint_if( EDGE_IS_PTXN(next_e), next_e, next_e>>8 ) }};
1858 0 : pending_prq_insert( disp->lanes[ lane ].pending, temp );
1859 0 : }
1860 0 : if( child_is_writer || child_edge[1]==e0 ) break;
1861 0 : next_e = child_edge[1];
1862 0 : }
1863 : /* In the case that the completed transaction is a reader, say B
1864 : or C above, it seems like we should need to remove it from
1865 : the doubly linked list, but we actually don't. The times
1866 : that we need to read the sibling pointers are:
1867 : 1. Completing the writer before a reader (e.g. completing A)
1868 : 2. Completing a reader that's the last in the DAG (e.g.
1869 : completing E/F if G didn't exist)
1870 : 3. Adding another reader to the same set of readers (e.g. if
1871 : G were added as a reader instead of a writer)
1872 : 4. Adding a writer after a set of readers (e.g. adding G).
1873 :
1874 : Supposing that the completed transaction is a reader, since
1875 : we checked EDGE_IS_LAST( e0 ), we know that there is at least
1876 : one writer that follows this reader, e.g. D above.
1877 :
1878 : And so none of these reason can apply to this group of readers:
1879 : 1. Completing B or C implies that A has already completed,
1880 : so it can't complete again.
1881 : 2. We know that we're not in that case because we checked
1882 : EDGE_IS_LAST( e0 ), and if we're not last now, we cannot
1883 : become last later, because the growth happens in the
1884 : other direction.
1885 : 3. Similarly, because we checked EDGE_IS_LAST, any future
1886 : additions of readers won't be to this group of readers.
1887 : 4. Similarly, we know that there already is a writer that
1888 : follows this group of readers, so a later writer would
1889 : not read this set of readers.
1890 :
1891 : So then, we don't need to deal with the sibling edges. The
1892 : fact that we only need to do it in one case almost calls into
1893 : question whether we need to maintain the whole circular
1894 : system in the first place, and whether we could get away with
1895 : a reference count or something instead, but it's important in
1896 : one critical case: suppose we add a bunch of readers, then
1897 : some of them complete, and then we add a writer (case 4
1898 : above). We need to be able to enumerate the nodes in the DAG
1899 : that have not yet completed, and we need to be able to remove
1900 : them from that set in O(1). Those two requirements don't
1901 : leave us with many alternatives besides a doubly linked list. */
1902 :
1903 0 : if( FD_UNLIKELY( EDGE_IS_LAST( *child_edge ) ) ) {
1904 : /* For example, either:
1905 : 1. completing D if G didn't exist
1906 : 2. completing E or F with G in the DAG
1907 :
1908 : After completing this transaction, there's either 0 writers
1909 : left (case 1) or 1 writer left (case 2) in the DAG. and if
1910 : there is one, it is the last reference. In case 1, we need
1911 : to know if we have a pending LtHash pseudo-transaction to
1912 : determine whether we transition to state NO_WRITERS or
1913 : NEEDS_PTXN. In case 2, we must be in LAST_REF_WAS_WRITE
1914 : and we stay there. */
1915 :
1916 0 : ulong acct_idx = EDGE_SPECIAL_IDX( *child_edge );
1917 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
1918 0 : uint s = ai->states;
1919 0 : if( !ACCT_INFO_STATE_IS( s, lane, LAST_REF_WAS_WRITE ) ) {
1920 0 : int needs_ptxn = fd_rdisp_mq_test( disp->mq, acct_idx, lane );
1921 0 : s = fd_uint_if( needs_ptxn, ACCT_INFO_STATE_SET(s, lane, NEEDS_PTXN), ACCT_INFO_STATE_SET(s, lane, NO_WRITERS) );
1922 0 : ai->states = (uchar)s;
1923 : /* The account's last writer is done, so we bump it into the
1924 : ready class, hotness threshold permitting. */
1925 0 : if( needs_ptxn && ai->ema_refs<disp->ready_acct_ema_max ) fd_rdisp_mq_adjust( disp->mq, acct_idx, lane, 0.0f );
1926 0 : }
1927 0 : }
1928 0 : }
1929 0 : edge_idx += fd_ulong_if( i<w_cnt, 1UL, 3UL );
1930 0 : }
1931 0 : block = block_slist_ele_peek_head( disp->lanes[ lane ].block_ll, disp->block_pool );
1932 0 : block->completed_cnt++;
1933 0 : } else if( FD_LIKELY( rtxn->in_degree==IN_DEGREE_ZOMBIE ) ) {
1934 0 : FD_TEST( reclaim );
1935 0 : FD_TEST( !ptxn );
1936 0 : block = block_pool_ele( disp->block_pool, rtxn->block_idx );
1937 0 : zombie_dlist_ele_remove( block->zombie_list, rtxn, disp->pool );
1938 : /* Fall through to the pool release branch below. */
1939 0 : } else {
1940 0 : FD_LOG_CRIT(( "completed un-dispatched transaction %lu", txn_idx ));
1941 0 : }
1942 0 : if( reclaim|ptxn ) {
1943 : /* For testing purposes, to make sure we don't read a completed
1944 : transaction, we can clobber the memory. */
1945 : /* memset( disp->pool+txn_idx, '\xCC', sizeof(fd_rdisp_txn_t) ); */
1946 0 : rtxn->in_degree = IN_DEGREE_FREE;
1947 0 : if( FD_LIKELY( !ptxn ) ) pool_idx_release ( disp->pool, txn_idx );
1948 0 : else ptxn_pool_idx_release( disp->ptxn_pool, EDGE_SPECIAL_IDX( txn_idx ) );
1949 0 : } else {
1950 0 : rtxn->in_degree = IN_DEGREE_ZOMBIE;
1951 0 : zombie_dlist_ele_push_tail( block->zombie_list, rtxn, disp->pool );
1952 0 : rtxn->block_idx = (uint)block_pool_idx( disp->block_pool, block );
1953 0 : }
1954 0 : }
1955 :
1956 : ulong
1957 : fd_rdisp_staging_lane_info( fd_rdisp_t const * disp,
1958 0 : fd_rdisp_staging_lane_info_t out_sched[ static 4 ] ) {
1959 0 : for( ulong i=0UL; i<4UL; i++ ) {
1960 0 : if( !(disp->free_lanes & (1<<i) ) ) {
1961 0 : block_slist_t const * sl = disp->lanes[ i ].block_ll;
1962 0 : out_sched[ i ].insert_ready_block = block_slist_ele_peek_tail( sl, disp->block_pool )->block;
1963 0 : out_sched[ i ].schedule_ready_block = block_slist_ele_peek_head( sl, disp->block_pool )->block;
1964 0 : }
1965 0 : }
1966 0 : return 0xFUL & ~(ulong)disp->free_lanes;
1967 0 : }
1968 :
1969 : void
1970 : fd_rdisp_pseudo_txn_to_addr( fd_rdisp_t const * disp,
1971 : ulong txn_idx,
1972 0 : fd_acct_addr_t * out ) {
1973 0 : FD_TEST( txn_idx & FD_RDISP_LTHASH_PSEUDO_TXN );
1974 0 : txn_idx ^= FD_RDISP_LTHASH_PSEUDO_TXN;
1975 0 : fd_rdisp_ptxn_t const * ptxn = disp->ptxn_pool + txn_idx;
1976 :
1977 0 : if( FD_LIKELY( (ptxn->in_degree!=IN_DEGREE_UNSTAGED) & (ptxn->in_degree!=IN_DEGREE_UNSTAGED_DISPATCHED) ) ) {
1978 0 : *out = disp->acct_pool[ EDGE_SPECIAL_IDX(ptxn->last) ].key;
1979 0 : } else {
1980 0 : *out = disp->ustlt_pool[ EDGE_SPECIAL_IDX(ptxn->last) ].key.acct;
1981 0 : }
1982 0 : }
1983 :
1984 : void
1985 : fd_rdisp_add_all_pseudo_txn( fd_rdisp_t * disp,
1986 0 : FD_RDISP_BLOCK_TAG_T insert_block ) {
1987 0 : while( fd_rdisp_add_pseudo_txn( disp, insert_block ) );
1988 0 : }
1989 :
1990 : /* Score of a staged pseudo-transaction. It sequences behind every
1991 : real transaction of its serializing class. */
1992 : static inline float
1993 0 : ptxn_score( uint last_serializing ) {
1994 0 : return fd_rdisp_score( FD_RDISP_PTXN_SCORE, last_serializing );
1995 0 : }
1996 :
1997 : static ulong
1998 : add_staged_pseudo_txn( fd_rdisp_t * disp,
1999 0 : fd_rdisp_blockinfo_t * block ) {
2000 0 : uint lane = block->staging_lane;
2001 0 : if( FD_UNLIKELY( !ptxn_pool_free( disp->ptxn_pool ) ) ) FD_LOG_CRIT(( "rdisp pseudo-transaction pool exhausted" ));
2002 0 : fd_rdisp_ptxn_t * ptxn = ptxn_pool_ele_acquire( disp->ptxn_pool );
2003 0 : uint ptxn_idx = EDGE_MAKE_SPECIAL(PTXN, (uint)(ptxn - disp->ptxn_pool));
2004 :
2005 0 : ulong acct_idx = fd_rdisp_mq_pop( disp->mq, lane );
2006 0 : acct_info_t * ai = disp->acct_pool + acct_idx;
2007 :
2008 0 : ptxn->in_degree = 0U;
2009 0 : if( FD_UNLIKELY( block->last_insert_was_serializing ) ) {
2010 0 : block->last_serializing = block->inserted_cnt;
2011 0 : }
2012 0 : block->last_insert_was_serializing = 0U;
2013 0 : ptxn->score = ptxn_score( block->last_serializing );
2014 :
2015 : /* see add_txn for this line */
2016 0 : ptxn->edge_cnt_etc = ((block->linear_block_number<<16) | (lane<<14)) - 1U;
2017 :
2018 : /* add_edges is more general than what we need, but it's better to
2019 : have all the logic in one place. We don't need to pass new_wr
2020 : because it's only a reader, so it won't be accessed anyway. */
2021 0 : add_edges( disp, (fd_rdisp_txn_t *)fd_type_pun( ptxn ), &(ai->key), 1UL, lane, 0, 0, NULL, 0UL );
2022 : /* since we're kind of cheating with edge_cnt_etc, we need to fix it
2023 : here. Additionally, type punning ptxn like that is a bit
2024 : fast-and-loose with the C spec, so add a compiler fence to make
2025 : sure these writes can't be reordered. */
2026 0 : FD_COMPILER_MFENCE();
2027 0 : ptxn->edge_cnt_etc += 1U<<7;
2028 0 : ptxn->last = EDGE_MAKE_SPECIAL(LAST, (uint)acct_idx);
2029 :
2030 : /* add_edge handles most of the state transitions, but it treats the
2031 : pseudo-transaction like a reader, so it needs a little fixing. */
2032 0 : uint states = ai->states;
2033 0 : states = fd_uint_if( ACCT_INFO_STATE_IS( states, lane, NEEDS_PTXN ), ACCT_INFO_STATE_SET( states, lane, NO_WRITERS ), states );
2034 0 : ai->states = (uchar)states;
2035 :
2036 0 : if( FD_LIKELY( ptxn->in_degree==0U ) ) {
2037 0 : pending_prq_ele_t temp[1] = {{ .score = ptxn->score, .linear_block_number = block->linear_block_number, .txn_idx = ptxn_idx }};
2038 0 : pending_prq_insert( disp->lanes[ lane ].pending, temp );
2039 0 : }
2040 0 : block->inserted_cnt++;
2041 0 : return ptxn_idx;
2042 0 : }
2043 :
2044 : ulong
2045 : fd_rdisp_add_ready_pseudo_txn( fd_rdisp_t * disp,
2046 0 : FD_RDISP_BLOCK_TAG_T insert_block ) {
2047 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &insert_block, NULL, disp->block_pool );
2048 0 : if( FD_UNLIKELY( !block || !block->insert_ready || !block->staged ) ) return 0UL;
2049 0 : if( FD_UNLIKELY( !fd_rdisp_mq_prio0_cnt( disp->mq, block->staging_lane ) ) ) return 0UL;
2050 0 : return add_staged_pseudo_txn( disp, block );
2051 0 : }
2052 :
2053 : ulong
2054 : fd_rdisp_add_pseudo_txn( fd_rdisp_t * disp,
2055 0 : FD_RDISP_BLOCK_TAG_T insert_block ) {
2056 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &insert_block, NULL, disp->block_pool );
2057 0 : if( FD_UNLIKELY( !block || !block->insert_ready ) ) return 0UL;
2058 :
2059 0 : fd_rdisp_ptxn_t * ptxn;
2060 0 : uint ptxn_idx;
2061 :
2062 0 : if( FD_LIKELY( block->staged ) ) {
2063 0 : if( FD_UNLIKELY( !fd_rdisp_mq_cnt( disp->mq, block->staging_lane ) ) ) return 0UL;
2064 0 : return add_staged_pseudo_txn( disp, block );
2065 0 : } else {
2066 0 : if( FD_UNLIKELY( ustlt_dlist_is_empty( block->ustlt_needed, disp->ustlt_pool ) ) ) return 0UL;
2067 :
2068 0 : if( FD_UNLIKELY( !ptxn_pool_free( disp->ptxn_pool ) ) ) FD_LOG_CRIT(( "rdisp pseudo-transaction pool exhausted" ));
2069 0 : ptxn = ptxn_pool_ele_acquire( disp->ptxn_pool );
2070 0 : ptxn_idx = EDGE_MAKE_SPECIAL(PTXN, (uint)(ptxn - disp->ptxn_pool));
2071 :
2072 0 : ustlt_t * ustlt_ele = ustlt_dlist_ele_pop_head( block->ustlt_needed, disp->ustlt_pool );
2073 0 : ustlt_map_ele_remove_fast( disp->ustlt_map, ustlt_ele, disp->ustlt_pool );
2074 0 : ptxn->in_degree = IN_DEGREE_UNSTAGED;
2075 0 : ptxn->score = 0.0f;
2076 :
2077 0 : ptxn->edge_cnt_etc = 0U;
2078 :
2079 0 : ptxn->last = (uint)(ustlt_ele - disp->ustlt_pool);
2080 0 : ustlt_ele->ptxn_idx = (uint)(ptxn - disp->ptxn_pool );
2081 :
2082 0 : ustlt_dlist_ele_push_tail( block->ustlt_created, ustlt_ele, disp->ustlt_pool );
2083 0 : }
2084 0 : block->inserted_cnt++;
2085 0 : return ptxn_idx;
2086 0 : }
2087 :
2088 : int
2089 : fd_rdisp_add_writable( fd_rdisp_t * disp,
2090 : FD_RDISP_BLOCK_TAG_T insert_block,
2091 0 : fd_acct_addr_t const * addr ) {
2092 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &insert_block, NULL, disp->block_pool );
2093 0 : if( FD_UNLIKELY( !block || !block->insert_ready ) ) return -1;
2094 :
2095 0 : if( FD_LIKELY( block->staged ) ) {
2096 0 : ulong idx = lookup_pubkey( disp, addr );
2097 0 : ulong lane = block->staging_lane;
2098 0 : if( FD_LIKELY( fd_rdisp_mq_test( disp->mq, idx, block->staging_lane ) ) ) return 0;
2099 :
2100 0 : acct_info_t * ai = disp->acct_pool+idx;
2101 0 : uint states = ai->states;
2102 0 : states = fd_uint_if( ACCT_INFO_STATE_IS( states, lane, NO_WRITERS ), ACCT_INFO_STATE_SET( states, lane, NEEDS_PTXN ), states );
2103 0 : ai->states = (uchar)states;
2104 0 : if( FD_UNLIKELY( fd_rdisp_mq_cnt( disp->mq, lane )>=MAX_WRITERS_PER_BLOCK ) ) FD_LOG_CRIT(( "rdisp lane %lu writable account set full", lane ));
2105 0 : fd_rdisp_mq_insert( disp->mq, idx, lane, mq_prio( disp, ai, ACCT_INFO_STATE_IS( states, lane, NEEDS_PTXN ) ) );
2106 0 : return 1;
2107 0 : } else {
2108 0 : ustlt_key_t query[1] = {{
2109 0 : .block_idx = (uint)(block-disp->block_pool),
2110 0 : .acct = *addr
2111 0 : }};
2112 0 : int new = (ustlt_map_idx_query( disp->ustlt_map, query, ULONG_MAX, disp->ustlt_pool )==ULONG_MAX);
2113 0 : if( FD_LIKELY( !new ) ) return 0;
2114 :
2115 0 : if( FD_UNLIKELY( ustlt_dlist_is_empty( disp->ustlt_free, disp->ustlt_pool ) ) ) FD_LOG_CRIT(( "rdisp unstaged LtHash entry pool exhausted" ));
2116 0 : ulong ustlt_idx = ustlt_dlist_idx_pop_head( disp->ustlt_free, disp->ustlt_pool );
2117 0 : disp->ustlt_pool[ ustlt_idx ].key = *query;
2118 0 : ustlt_map_idx_insert( disp->ustlt_map, ustlt_idx, disp->ustlt_pool );
2119 0 : ustlt_dlist_idx_push_tail( block->ustlt_needed, ustlt_idx, disp->ustlt_pool );
2120 0 : return 1;
2121 0 : }
2122 0 : }
2123 :
2124 : ulong
2125 : fd_rdisp_add_extra_pseudo_txn( fd_rdisp_t * disp,
2126 : FD_RDISP_BLOCK_TAG_T schedule_block,
2127 0 : fd_acct_addr_t const * addr ) {
2128 0 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &schedule_block, NULL, disp->block_pool );
2129 0 : if( FD_UNLIKELY( !block || !block->schedule_ready ) ) return 0UL;
2130 :
2131 0 : uint ptxn_idx;
2132 :
2133 0 : if( FD_LIKELY( block->staged ) ) {
2134 0 : ulong idx = lookup_pubkey( disp, addr );
2135 0 : uint lane = block->staging_lane;
2136 :
2137 0 : acct_info_t * ai = disp->acct_pool+idx;
2138 0 : edge_t last = ai->last_reference[lane];
2139 0 : int insert_inline = 0;
2140 0 : if( FD_UNLIKELY( block->insert_ready ) ) {
2141 0 : insert_inline = 1;
2142 0 : } else if( FD_UNLIKELY( EDGE_IS_PTXN(last) ) ) {
2143 : /* If this is for the right block, we got lucky */
2144 0 : fd_rdisp_ptxn_t const * ptxn = disp->ptxn_pool + EDGE_SPECIAL_IDX(last);
2145 0 : if( FD_UNLIKELY( (ptxn->edge_cnt_etc>>16)==(0xFFFF&block->linear_block_number) ) ) return last;
2146 0 : } else if( FD_UNLIKELY( last==0U ) ) {
2147 0 : insert_inline=1;
2148 0 : } else {
2149 0 : fd_rdisp_txn_t const * txn = FOLLOW_EDGE_TXN( disp, last );
2150 0 : insert_inline = (txn->edge_cnt_etc>>16)==(0xFFFF&block->linear_block_number);
2151 0 : }
2152 :
2153 : /* If we haven't inserted an extra ptxn yet, and we're inserting
2154 : inline, treat this as a normal non-seralizing transaction. ... */
2155 0 : if( FD_UNLIKELY( insert_inline && block->last_insert_was_serializing && !block->inserted_extra_ptxn ) ) {
2156 0 : block->last_serializing = block->inserted_cnt;
2157 0 : block->last_insert_was_serializing = 0U;
2158 0 : } else if( FD_UNLIKELY( !insert_inline && !block->inserted_extra_ptxn ) ) {
2159 : /* Otherwise, if this is the first non-inline one, bump
2160 : last_serializing once and don't touch it again. The block
2161 : can't be insert-ready, so we won't insert any other
2162 : transactions that aren't from this function. */
2163 0 : block->last_serializing = block->inserted_cnt;
2164 0 : block->last_insert_was_serializing = 0U;
2165 0 : block->inserted_extra_ptxn = 1;
2166 0 : }
2167 :
2168 0 : if( FD_UNLIKELY( !ptxn_pool_free( disp->ptxn_pool ) ) ) FD_LOG_CRIT(( "rdisp pseudo-transaction pool exhausted" ));
2169 0 : fd_rdisp_ptxn_t * ptxn = ptxn_pool_ele_acquire( disp->ptxn_pool );
2170 0 : ptxn_idx = EDGE_MAKE_SPECIAL(PTXN, (uint)(ptxn - disp->ptxn_pool));
2171 0 : if( FD_LIKELY( insert_inline ) ) {
2172 : /* What follows below is essentially the same as the normal
2173 : add_pseudo_txn case */
2174 0 : ptxn->in_degree = 0U;
2175 0 : ptxn->score = ptxn_score( block->last_serializing );
2176 0 : ptxn->edge_cnt_etc = ((block->linear_block_number<<16) | (lane<<14)) - 1U;
2177 0 : add_edges( disp, (fd_rdisp_txn_t *)fd_type_pun( ptxn ), &(ai->key), 1UL, lane, 0, 0, NULL, 0UL );
2178 0 : FD_COMPILER_MFENCE();
2179 0 : ptxn->edge_cnt_etc += 1U<<7;
2180 0 : ptxn->last = EDGE_MAKE_SPECIAL(LAST, (uint)idx);
2181 :
2182 0 : uint states = ai->states;
2183 0 : states = fd_uint_if( ACCT_INFO_STATE_IS( states, lane, NEEDS_PTXN ), ACCT_INFO_STATE_SET( states, lane, NO_WRITERS ), states );
2184 0 : ai->states = (uchar)states;
2185 :
2186 0 : if( FD_LIKELY( ptxn->in_degree==0U ) ) {
2187 0 : pending_prq_ele_t temp[1] = {{ .score = ptxn->score, .linear_block_number = block->linear_block_number, .txn_idx = ptxn_idx }};
2188 0 : pending_prq_insert( disp->lanes[ block->staging_lane ].pending, temp );
2189 0 : }
2190 0 : } else {
2191 : /* Otherwise there's already a transaction for a later block in
2192 : the DAG for this account, we insert a hacky 0-edge pseudo-txn
2193 : and make use of the serializing functionality to make sure it
2194 : executes after all the transactions. Since this block is not
2195 : insert-ready, we don't need to worry about preventing later
2196 : transactions from happening before this one. */
2197 :
2198 0 : ptxn->in_degree = 0U;
2199 0 : ptxn->edge_cnt_etc = ((block->linear_block_number<<16) | (lane<<14)); /* r_cnt==0, w_cnt is ignored */
2200 0 : ptxn->score = ptxn_score( block->last_serializing );
2201 0 : ptxn->last = EDGE_MAKE_SPECIAL(LAST, (uint)idx);
2202 : /* We know that there's a transaction that must execute after this
2203 : one in the DAG, so the account info can't get freed until after
2204 : this transaction has completed. That means we don't need to
2205 : touch ai->states. */
2206 0 : pending_prq_ele_t temp[1] = {{ .score = ptxn->score, .linear_block_number = block->linear_block_number, .txn_idx = ptxn_idx }};
2207 0 : pending_prq_insert( disp->lanes[ block->staging_lane ].pending, temp );
2208 0 : }
2209 0 : } else {
2210 0 : if( FD_UNLIKELY( ustlt_dlist_is_empty( disp->ustlt_free, disp->ustlt_pool ) ) ) FD_LOG_CRIT(( "rdisp unstaged LtHash entry pool exhausted" ));
2211 0 : ulong ustlt_idx = ustlt_dlist_idx_pop_head( disp->ustlt_free, disp->ustlt_pool );
2212 0 : disp->ustlt_pool[ ustlt_idx ].key.block_idx = (uint)(block-disp->block_pool);
2213 0 : disp->ustlt_pool[ ustlt_idx ].key.acct = *addr;
2214 :
2215 0 : if( FD_UNLIKELY( !ptxn_pool_free( disp->ptxn_pool ) ) ) FD_LOG_CRIT(( "rdisp pseudo-transaction pool exhausted" ));
2216 0 : fd_rdisp_ptxn_t * ptxn = ptxn_pool_ele_acquire( disp->ptxn_pool );
2217 0 : ptxn_idx = EDGE_MAKE_SPECIAL(PTXN, (uint)(ptxn - disp->ptxn_pool));
2218 :
2219 0 : ptxn->in_degree = IN_DEGREE_UNSTAGED;
2220 0 : ptxn->score = 0.0f;
2221 0 : ptxn->edge_cnt_etc = 0U;
2222 0 : ptxn->last = (uint)ustlt_idx;
2223 :
2224 0 : disp->ustlt_pool[ ustlt_idx ].ptxn_idx = (uint)(ptxn - disp->ptxn_pool);
2225 0 : ustlt_dlist_idx_push_tail( block->ustlt_created, ustlt_idx, disp->ustlt_pool );
2226 0 : }
2227 0 : block->inserted_cnt++;
2228 0 : return ptxn_idx;
2229 0 : }
2230 :
2231 : ulong
2232 : fd_rdisp_lane_writable_cnt( fd_rdisp_t * disp,
2233 0 : ulong staging_lane ) {
2234 0 : FD_TEST( staging_lane<4UL );
2235 0 : return fd_rdisp_mq_cnt( disp->mq, staging_lane );
2236 0 : }
2237 :
2238 : ulong
2239 : fd_rdisp_lane_ready_acct_cnt( fd_rdisp_t * disp,
2240 0 : ulong staging_lane ) {
2241 0 : return fd_rdisp_mq_prio0_cnt( disp->mq, staging_lane );
2242 0 : }
2243 :
2244 : void
2245 : fd_rdisp_set_ready_acct_ema_max( fd_rdisp_t * disp,
2246 0 : float ema_max ) {
2247 0 : disp->ready_acct_ema_max = ema_max;
2248 0 : }
2249 :
2250 : void
2251 : fd_rdisp_verify( fd_rdisp_t const * disp,
2252 0 : uint * scratch ) {
2253 0 : ulong acct_depth = disp->depth*FD_RDISP_MAX_ACCT_PER_TXN+disp->acct_extra;
2254 0 : ulong block_depth = disp->block_depth;
2255 0 : FD_TEST( 0==acct_map_verify ( disp->acct_map, acct_depth +1UL, disp->acct_pool ) );
2256 0 : FD_TEST( 0==block_map_verify( disp->blockmap, block_depth+1UL, disp->block_pool ) );
2257 0 : FD_TEST( 0==ustlt_map_verify( disp->ustlt_map, acct_depth +1UL, disp->ustlt_pool ) );
2258 :
2259 : /* Every element of the free list that is in the map is CACHED under
2260 : its own key, every element in the map is either ACTIVE with a
2261 : reference in some lane or CACHED, and the CACHED ones are exactly
2262 : the mapped elements of the free list. */
2263 0 : ulong cached_cnt = 0UL;
2264 0 : for( free_dlist_iter_t it=free_dlist_iter_fwd_init( disp->free_acct_dlist, disp->acct_pool );
2265 0 : !free_dlist_iter_done( it, disp->free_acct_dlist, disp->acct_pool );
2266 0 : it=free_dlist_iter_fwd_next( it, disp->free_acct_dlist, disp->acct_pool ) ) {
2267 0 : ulong idx = free_dlist_iter_idx( it, disp->free_acct_dlist, disp->acct_pool );
2268 0 : acct_info_t const * ai = disp->acct_pool+idx;
2269 0 : if( !ai->next ) continue; /* FREE */
2270 0 : FD_TEST( ai->cached==ACCT_INFO_CACHED && !ai->states );
2271 0 : FD_TEST( acct_map_idx_query_const( disp->acct_map, &ai->key, ULONG_MAX, disp->acct_pool )==idx );
2272 0 : cached_cnt++;
2273 0 : }
2274 0 : for( acct_map_iter_t it=acct_map_iter_init( disp->acct_map, disp->acct_pool );
2275 0 : !acct_map_iter_done( it, disp->acct_map, disp->acct_pool );
2276 0 : it=acct_map_iter_next( it, disp->acct_map, disp->acct_pool ) ) {
2277 0 : acct_info_t const * ai = acct_map_iter_ele_const( it, disp->acct_map, disp->acct_pool );
2278 0 : if( ai->cached==ACCT_INFO_CACHED ) cached_cnt--;
2279 0 : else FD_TEST( ai->states | ai->last_reference[ 0 ] | ai->last_reference[ 1 ] | ai->last_reference[ 2 ] | ai->last_reference[ 3 ] );
2280 0 : }
2281 0 : FD_TEST( cached_cnt==0UL );
2282 :
2283 : /* Every unstaged LtHash entry is in the free list or in one list of
2284 : one unstaged block. */
2285 0 : ulong ustlt_cnt = 0UL;
2286 0 : for( ustlt_dlist_iter_t it=ustlt_dlist_iter_fwd_init( disp->ustlt_free, disp->ustlt_pool );
2287 0 : !ustlt_dlist_iter_done( it, disp->ustlt_free, disp->ustlt_pool );
2288 0 : it=ustlt_dlist_iter_fwd_next( it, disp->ustlt_free, disp->ustlt_pool ) ) ustlt_cnt++;
2289 0 : for( block_map_iter_t it=block_map_iter_init( disp->blockmap, disp->block_pool );
2290 0 : !block_map_iter_done( it, disp->blockmap, disp->block_pool );
2291 0 : it=block_map_iter_next( it, disp->blockmap, disp->block_pool ) ) {
2292 0 : fd_rdisp_blockinfo_t const * block = block_map_iter_ele_const( it, disp->blockmap, disp->block_pool );
2293 0 : if( block->staged ) continue;
2294 0 : ustlt_dlist_t const * lists[ 2 ] = { block->ustlt_needed, block->ustlt_created };
2295 0 : for( ulong l=0UL; l<2UL; l++ ) {
2296 0 : for( ustlt_dlist_iter_t jt=ustlt_dlist_iter_fwd_init( lists[ l ], disp->ustlt_pool );
2297 0 : !ustlt_dlist_iter_done( jt, lists[ l ], disp->ustlt_pool );
2298 0 : jt=ustlt_dlist_iter_fwd_next( jt, lists[ l ], disp->ustlt_pool ) ) {
2299 0 : FD_TEST( ustlt_dlist_iter_ele_const( jt, lists[ l ], disp->ustlt_pool )->key.block_idx==(uint)(block-disp->block_pool) );
2300 0 : ustlt_cnt++;
2301 0 : }
2302 0 : }
2303 0 : }
2304 0 : FD_TEST( ustlt_cnt==acct_depth );
2305 :
2306 : /* Check all the in degree counts are right */
2307 0 : memset( scratch, '\0', sizeof(uint)*((disp->depth+acct_depth+2UL)) );
2308 0 : scratch[ 0 ] = UINT_MAX;
2309 :
2310 0 : for( ulong j=0UL; j<(disp->depth+acct_depth+2UL); j++ ) {
2311 0 : int ptxn = j>disp->depth;
2312 0 : fd_rdisp_txn_t const * rtxn = !ptxn ? disp->pool+j : (fd_rdisp_txn_t const *)(disp->ptxn_pool+(j-disp->depth-1UL));
2313 0 : if( rtxn->in_degree==IN_DEGREE_FREE ) { scratch[ j ]=UINT_MAX; continue; }
2314 :
2315 0 : if( (rtxn->in_degree==IN_DEGREE_UNSTAGED_DISPATCHED) |
2316 0 : (rtxn->in_degree==IN_DEGREE_UNSTAGED) |
2317 0 : (rtxn->in_degree==IN_DEGREE_ZOMBIE) ) continue;
2318 :
2319 0 : ulong w_cnt = fd_ulong_if( ptxn, 0UL, 1UL + ((rtxn->edge_cnt_etc ) & 0x7FU) );
2320 0 : ulong r_cnt = (rtxn->edge_cnt_etc>> 7) & 0x7FU;
2321 0 : ulong edge_idx = 0UL;
2322 :
2323 0 : for( ulong i=0UL; i<w_cnt+r_cnt; i++ ) {
2324 0 : edge_t const * e = rtxn->edges+edge_idx;
2325 0 : edge_t const e0 = *e;
2326 :
2327 0 : edge_idx += fd_ulong_if( i<w_cnt, 1UL, 3UL );
2328 :
2329 0 : if( FD_UNLIKELY( EDGE_IS_LAST( e0 ) ) ) {
2330 : /* Make sure acct is ACTIVE */
2331 0 : acct_info_t * ai = disp->acct_pool + EDGE_SPECIAL_IDX(e0);
2332 0 : FD_TEST( !( (ai->states==0)&
2333 0 : (ai->last_reference[ 0 ]==0U)&(ai->last_reference[ 1 ]==0U)&
2334 0 : (ai->last_reference[ 2 ]==0U)&(ai->last_reference[ 3 ]==0U) ) );
2335 0 : FD_TEST( EDGE_SPECIAL_IDX(e0)==acct_map_idx_query_const( disp->acct_map, &(ai->key), ULONG_MAX, disp->acct_pool ) );
2336 0 : continue;
2337 0 : }
2338 :
2339 0 : edge_t next_e = e0;
2340 0 : edge_t const * child_edge;
2341 0 : edge_t last_e = 0U;
2342 0 : while( 1 ) {
2343 0 : int child_is_writer;
2344 : /* This loop first traverses the me->child link, and then
2345 : traverses any sibling links. For example, in the case that
2346 : we're completing node D above, the first child_txn is E,
2347 : and the second child_txn is F. */
2348 0 : child_edge = FOLLOW_EDGE( disp, next_e, child_is_writer );
2349 :
2350 0 : scratch[ fd_ulong_if( EDGE_IS_PTXN(next_e), EDGE_SPECIAL_IDX(next_e)+disp->depth+1UL, next_e>>8 ) ]++;
2351 :
2352 0 : if( child_is_writer || child_edge[1]==e0 ) break;
2353 0 : if( last_e!=0U ) FD_TEST( child_edge[2]==last_e );
2354 0 : last_e = next_e;
2355 0 : next_e = child_edge[1];
2356 0 : FD_TEST( next_e>=0x100U );
2357 0 : }
2358 0 : }
2359 0 : }
2360 0 : for( ulong i=0UL; i<(disp->depth+acct_depth+2UL); i++ ) {
2361 0 : fd_rdisp_txn_t const * rtxn = i<=disp->depth ? disp->pool+i : (fd_rdisp_txn_t const *)(disp->ptxn_pool+(i-disp->depth-1UL));
2362 0 : FD_TEST( scratch[ i ]==UINT_MAX ||
2363 0 : rtxn->in_degree==IN_DEGREE_DISPATCHED ||
2364 0 : rtxn->in_degree==IN_DEGREE_UNSTAGED ||
2365 0 : rtxn->in_degree==IN_DEGREE_UNSTAGED_DISPATCHED ||
2366 0 : rtxn->in_degree==IN_DEGREE_ZOMBIE ||
2367 0 : rtxn->in_degree==scratch[ i ] );
2368 0 : }
2369 0 : }
2370 :
2371 0 : void * fd_rdisp_leave ( fd_rdisp_t * disp ) { return disp; }
2372 0 : void * fd_rdisp_delete( void * mem ) { return mem; }
|
