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