Line data Source code
1 : #include "fd_rdisp.h"
2 : #include "../../util/fd_hash32.h"
3 : #include <math.h> /* for the EMA */
4 :
5 : /* The conflict graph that this file builds is not a general DAG, but
6 : the union of several special account-conflict graphs. Each
7 : account-conflict graph has special structure:
8 : ---> 3 --
9 : / \
10 : / v
11 : 1 ---> 2 -----> 4 --> 6 ----> 7
12 : \ ^
13 : \ /
14 : ----> 5 --
15 :
16 : That is, the graph is almost a line, but may have fan-out and fan-in
17 : regions. The tricky part about representing a graph like this
18 : without dynamic memory allocation is that nodes may have arbitrary
19 : in-degree and out-degree. Thus, we use a pretty standard trick and
20 : use sibling pointers, denoted below with dotted lines. Each node
21 : maintains at most one successor pointer and at most one sibling
22 : pointer. Although not shown below, the sibling pointers are
23 : circularly linked, so 5's sibling is 3. Additionally, though not
24 : shown below, the child of the last node (7) stores information about
25 : what account address all this is for, which facilitates deleting the
26 : last node in the graph.
27 :
28 :
29 : --> 3 --
30 : / ^ \
31 : / : \
32 : / V v
33 : 1 ---> 2 4 --> 6 ----> 7
34 : ^ ^
35 : : /
36 : V /
37 : 5 --
38 :
39 : The normal edge 2->3 along with the sibling edge 3..>4 implies a
40 : normal edge 2->4. That then transitively implies an edge 2->5.
41 :
42 : We want each node to maintain a count of its in-degree so that we
43 : know when it can be executed. The implied edges also count for the
44 : in-degree. In this example, node 1 has in-degree 0, node 6 has
45 : in-degree 3, and the rest have in-degree 1.
46 :
47 : Maintaining each account-conflict graph is relatively easy given the
48 : operations we want to support. Only the details about sibling edges
49 : are worth mentioning. For example, when deleting node 2, we
50 : decrement the in-degree count for its successor, and then follow the
51 : sibling pointers, decrementing all the in-degree counts as we go to
52 : mark the deletion of the implied edges. Sibling edges also need to
53 : be doubly linked, so that e.g. nodes 3 and 5 can be re-linked in O(1)
54 : if node 4 is deleted. They're also circularly linked as well for
55 : convenience.
56 :
57 : When building the graph, we maintain a map of account to the last
58 : node that references it, whether that was a read or write, and
59 : whether there are any writers to that account in the graph right now.
60 : If the new node reads from an account that was last read, the new
61 : node becomes a sibling of the last read, with in-degree increased if
62 : there are any writers. Otherwise, it becomes a successor of the node
63 : that last referenced the account. */
64 :
65 : /* For a task like this with lots of graph traversal and pointer
66 : chasing, performance is typically limited by memory latency. That
67 : means that the more that can fit in cache, the better the
68 : performance. This implementation uses a lot of bit-packing to
69 : improve cache footprint. */
70 :
71 : /* The following structs are all very local to this compilation unit,
72 : and so they don't have globally acceptable type names (e.g.
73 : fd_rdisp_edge_t). */
74 :
75 155841 : #define MAX_ACCT_PER_TXN FD_TXN_ACCT_ADDR_MAX
76 : FD_STATIC_ASSERT( MAX_ACCT_PER_TXN<=128UL, max_acct_per_txn );
77 :
78 : /* edge_t: Fields typed edge_t represent an edge in one of the parallel
79 : account-conflict DAGs. Each transaction stores a list of all its
80 : outgoing edges. The type is actually a union of bitfield, but C
81 : bitfields are gross, so we just do it manually with macros. If the
82 : high bit is set, that means the transaction storing this edge_t value
83 : is the last in this specific DAG, and the lower 31 bits of the
84 : value are an index in the map_pool for the account pubkey for this
85 : DAG. See the comments about the hidden edge outgoing from node 7 in
86 : the DAG at the top of this file for an example.
87 : If the high bit is not set, then the next 23 bits store the
88 : destination of the edge, represented by its index in the pool of
89 : transactions. Then the lowest 8 bits store the account index within
90 : that transaction of the edge that is part of the same
91 : account-specific DAG as this edge. Because the max depth is 2^23-1,
92 : and each transaction can reference FD_TXN_ACCT_ADDR_MAX accounts,
93 : the max accounts that can be referenced fits in 30 bits.
94 : The proper type would be something like
95 : typedef union {
96 : struct {
97 : uint is_last:1;
98 : uint map_pool_idx:31;
99 : } last;
100 : struct {
101 : uint is_last:1;
102 : uint txn_idx:23;
103 : uint acct_idx:8;
104 : } e;
105 : } edge_t;
106 :
107 : */
108 : typedef uint edge_t;
109 :
110 :
111 : /* fd_rdisp_txn is the representation of a transaction as a node in the
112 : DAG. */
113 : struct fd_rdisp_txn {
114 : /* in_degree: The total number of edges summed across all account DAGs
115 : with this node as their destination. In the worst case, all the
116 : other transactions in the pool read from each of the max number of
117 : accounts that this transaction writes to, so there are
118 : MAX_ACCT_PER_TXN*depth edges that come into this node, which fits in
119 : about 30 bits, so we have some room for special values. If
120 : in_degree is one of the following values, then
121 : the transaction is: */
122 47394837 : #define IN_DEGREE_FREE (UINT_MAX )
123 11532921 : #define IN_DEGREE_UNSTAGED (UINT_MAX-1U)/* unstaged, not dispatched */
124 552843 : #define IN_DEGREE_DISPATCHED (UINT_MAX-2U)/* staged, dispatched */
125 11532603 : #define IN_DEGREE_UNSTAGED_DISPATCHED (UINT_MAX-3U)/* unstaged, dispatched */
126 11532300 : #define IN_DEGREE_ZOMBIE (UINT_MAX-4U)/* zombie */
127 : /* a transaction that is staged and dispatched is must have an
128 : in_degree of 0. in_degree isn't a meaningful concept for unstaged
129 : transactions. */
130 : uint in_degree;
131 :
132 : /* score: integer part stores how many transactions in the block must
133 : have completed before this transaction can be scheduled. This is
134 : useful for transactions marked as serializing. The fractional part
135 : gives some measure of how urgent the transaction is, where lower is
136 : more urgent. This means we can't have more transactions in a block
137 : marked as serializing than the first integer that a float cannot
138 : represent. That value is about 16M, which is much higher than the
139 : maximum number of transactions in a block, so this is not a
140 : problem. If in the very rare case that there are more than just a
141 : few serializing transactions, we will lose a bit of precision for
142 : the fractional portion, which makes total sense; if there's not
143 : much room for parallel execution, having the optimal parallel
144 : execution is not very important. */
145 : float score;
146 :
147 : /* edge_cnt_etc:
148 : 0xFFFF0000 (16 bits) for linear block number,
149 : 0x0000C000 (2 bits) for concurrency lane,
150 : 0x00003F80 (7 bits) for r_cnt
151 : 0x0000007F (7 bits) for w_cnt_1. Transactions have at least one
152 : writable account and at most MAX_ACCT_PER_TXN total accounts, so
153 : storing w_cnt_1 = w_cnt - 1 fits in 7 bits. */
154 : union {
155 : uint edge_cnt_etc;
156 : /* edge_cnt_etc is only used when the transaction is STAGED and
157 : PENDING, READY, or DISPATCHED. If UNSTAGED or FREE, the next
158 : pointer is also here. It can't be UNSTAGED and FREE at the same
159 : time, so there's no conflict with storage there either. */
160 : uint unstaged_next;
161 : uint free_next;
162 : /* If ZOMBIE, pointer back to block is here. No storage conflict
163 : because ZOMBIE is an exclusive state. */
164 : uint block_idx;
165 : };
166 :
167 :
168 : /* When a transaction writes to an account, it only creates one
169 : link. When a transaction reads from an account, we need the full
170 : doubly linked list with its siblings, so it creates 3 edges
171 : (child, next, prev). All edges from writable accounts come first,
172 : and we keep track of how many there are. In the worst case, all
173 : accounts are reads, so we size it appropriately. */
174 : edge_t edges[3UL*MAX_ACCT_PER_TXN]; /* addressed [0, w_cnt_1+1+3*r_cnt) */
175 : };
176 : typedef struct fd_rdisp_txn fd_rdisp_txn_t;
177 :
178 : #define EDGE_IS_LAST(x) ((x)&0x80000000U)
179 :
180 : /* Two more definitions:
181 : An edge index is an array position within the edges array. An
182 : account index is a position within a transaction's account addresses,
183 : reordered so that the writable ones come first. Since writable
184 : accounts use one position in the edges array per account address,
185 : these often coincide. */
186 :
187 :
188 : /* FOLLOW_EDGE and FOLLOW_EDGE_TXN are helper macros for dealing with
189 : edges. Given an edge_t x, and transaction pool base, FOLLOW_EDGE_TXN
190 : returns a pointer to transaction that the edge points to; FOLLOW_EDGE
191 : returns a pointer to the (first) edge_t within that transaction that
192 : is part of the same DAG as this edge. FOLLOW_EDGE and
193 : FOLLOW_EDGE_TXN must not be called if EDGE_IS_LAST is non-zero.
194 :
195 : Then the edge index, i.e. the position in the edges array of the
196 : (first) edge for an account index is:
197 : acct_idx if acct_idx<=w_cnt_1
198 : w_cnt_1+1 + 3*(acct_idx-w_cnt_1-1) else.
199 : Simplifying gives
200 : acct_idx + 2*signed_max( 0, acct_idx-w_cnt_1-1 ).
201 : In doing this calculation, we also basically get for free whether the
202 : edge is for a writable account or a readonly account, so we return
203 : that as well via the w parameter. If the child transaction only reads
204 : the account address for this DAG, then the next and prev pointers can
205 : be accessed using the returned value +1 and +2, respectively. */
206 38507154 : #define FOLLOW_EDGE(base, x, w) (__extension__({ \
207 38507154 : uint __e = (x); \
208 38507154 : fd_rdisp_txn_t * __txn = ((base)+(__e>>8)); \
209 38507154 : uint __w_cnt_1 = __txn->edge_cnt_etc & 0x7FU; \
210 38507154 : uint __idx = (__e & 0xFFU); \
211 38507154 : (w) = __idx<=__w_cnt_1; \
212 38507154 : (void)(w); /* not robust... */ \
213 38507154 : __txn->edges + __idx + 2*fd_int_max( 0, (int)(__idx)-(int)(__w_cnt_1)-1 ); }))
214 31259313 : #define FOLLOW_EDGE_TXN(base, x) ( (base)+((x)>>8) )
215 :
216 : /* The pool and slist are almost the same, but they are used
217 : differently, so keep them as different structures for now. */
218 :
219 : #define POOL_NAME pool
220 297 : #define POOL_T fd_rdisp_txn_t
221 : #define POOL_IDX_T uint
222 1350198 : #define POOL_NEXT free_next
223 : #define POOL_SENTINEL 1
224 : #include "../../util/tmpl/fd_pool.c"
225 :
226 : #define SLIST_NAME unstaged_txn_ll
227 : #define SLIST_ELE_T fd_rdisp_txn_t
228 318 : #define SLIST_IDX_T uint
229 1272 : #define SLIST_NEXT unstaged_next
230 : #include "../../util/tmpl/fd_slist.c"
231 :
232 : #define DLIST_IDX_T uint
233 27 : #define DLIST_PREV edges[0]
234 27 : #define DLIST_NEXT edges[1]
235 : #define DLIST_NAME zombie_dlist
236 : #define DLIST_ELE_T fd_rdisp_txn_t
237 : #include "../../util/tmpl/fd_dlist.c"
238 :
239 :
240 : /* ACCT_INFO_FLAG: It's a bit unfortunate that we have to maintain these
241 : flags, but basically we need to be able to distinguish the case where
242 : there are only readers so that we don't increment in_degree when
243 : adding a new fd_rdisp_txn. If we have any writers, the only way to
244 : transition into a state where there are only readers is to complete
245 : the last writer. We know we are in this case when the completed
246 : node's child doesn't have a child, and the completed node's child is
247 : a reader, as indicated by the LAST_REF_WAS_WRITE bit.
248 : LAST_REF_WAS_WRITE also has the advantage of being easy to
249 : maintain. */
250 6087087 : #define ACCT_INFO_FLAG_LAST_REF_WAS_WRITE(lane) (((uchar)1)<<(2*(lane)))
251 5994870 : #define ACCT_INFO_FLAG_ANY_WRITERS( lane) (((uchar)2)<<(2*(lane)))
252 :
253 : /* acct_info_t is a node in a map_chain that contains the metadata for a
254 : single account address's conflict graph DAG. In particular, it
255 : contains the information needed to know where to insert a node that
256 : reads from or writes to the account. The objects of this type follow
257 : this state machine:
258 :
259 : FREE -----> ACTIVE ----> CACHED
260 : ^ |
261 : |-------------
262 : When FREE, it is in free_acct_dlist only. When ACTIVE, it is in
263 : acct_map only. When CACHED, it is in both free_acct_dlist and
264 : cached_acct_map.
265 : */
266 : struct acct_info {
267 : /* key, next, and prev are the map_chain fields. Used in the ACTIVE
268 : and CACHED states. next and prev set to 0 when in the FREE state.
269 : Element 0 is a sentinel and isn't inserted to the free_acct_dlist,
270 : so this is unambiguous. */
271 : fd_acct_addr_t key;
272 : uint next;
273 : uint prev;
274 :
275 : union {
276 : struct {
277 : /* This is effectively a pointer to the last node in the DAG for
278 : this pubkey, one for each staging lane.
279 : EDGE_IS_LAST(FOLLOW_EDGE(base, last_reference[i])) is non-zero.
280 : */
281 : edge_t last_reference[4];
282 :
283 : }; /* When in the ACTIVE state */
284 : struct {
285 : uint free_ll_next;
286 : uint free_ll_prev;
287 : /* 8 bytes of padding here */
288 : }; /* When not in the ACTIVE state, used by the free_acct_dlist */
289 : };
290 : /* flags: a combination of ACCT_INFO_FLAG_* bitfields above. Used
291 : when ACTIVE. */
292 : uint flags:8;
293 :
294 :
295 : /* We want to dispatch the READY transactions in an order that
296 : maximizes parallelism, but we also want to be able to start
297 : dispatching transactions decently well before we have the full
298 : conflict graph. We can do that because we know that contentious
299 : accounts tend to stay contentious and uncontentious accounts tend
300 : to stay uncontentious.
301 :
302 : To accomplish this, we maintain a special EMA. Let x_i be 1 if
303 : transaction i references it and 0 if not. If we squint and assume
304 : the transactions are independent and all drawn from some
305 : distribution (which is not true, but that's why we squint), an EMA
306 : of x_i estimates the probability that the next transaction
307 : references this account. How we use this value is detailed later.
308 :
309 : We can't update this value for every pubkey for each transaction,
310 : so we maintain it in a lazy way, by applying updates only when we
311 : need to read the value, which also happens to be every time we want
312 : to add a 1 value to the EMA. We then just need to maintain the
313 : last index i at which x_i was updated and the current value. We
314 : only have 24 bits for the index, which means that we can't maintain
315 : it in a fork-aware way, which doesn't seem like a problem. Also,
316 : it's possible it can overflow, and that can result in an incorrect
317 : value, but that means the account is only referenced ~ 1/2^24
318 : transactions, which is also fine.
319 :
320 : last_ref is in the domain of global_inserted_txn_cnt. ema_refs is
321 : in [0, 1]. Both fields are used in ACTIVE and CACHED. Maintaining
322 : these fields is actually the main reason CACHED exists. */
323 : uint last_ref:24;
324 : float ema_refs;
325 : };
326 : typedef struct acct_info acct_info_t;
327 :
328 : FD_STATIC_ASSERT( sizeof(acct_info_t)==64UL, acct_info_t );
329 :
330 : /* For the acct_map and the free_acct_map */
331 : #define MAP_NAME acct_map
332 1759374 : #define MAP_ELE_T acct_info_t
333 119613348 : #define MAP_IDX_T uint
334 : #define MAP_KEY_T fd_acct_addr_t
335 225795531 : #define MAP_KEY_HASH(k,s) fd_hash32( (k)->b, (s) )
336 112970685 : #define MAP_KEY_EQ(k0,k1) (!memcmp( (k0)->b, (k1)->b, 32UL ))
337 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
338 : #include "../../util/tmpl/fd_map_chain.c"
339 :
340 :
341 : #define DLIST_IDX_T uint
342 17769498 : #define DLIST_PREV free_ll_prev
343 17769498 : #define DLIST_NEXT free_ll_next
344 : #define DLIST_NAME free_dlist
345 : #define DLIST_ELE_T acct_info_t
346 : #include "../../util/tmpl/fd_dlist.c"
347 :
348 :
349 : struct pending_prq_ele {
350 : /* lower score means should be scheduled sooner. Integer part has a
351 : special meaning as explained above. */
352 : float score;
353 :
354 : uint linear_block_number;
355 : uint txn_idx;
356 :
357 : /* It seems like we should be able to get this whole struct in 8
358 : bytes, but we're a few bits over.
359 :
360 : 23 bits for txn_idx
361 : 16 bit for linear_block_number
362 : Then the integer part of the score needs to be at least 18 or 19
363 : bits, but we can't use a custom floating point number. */
364 : };
365 :
366 : typedef struct pending_prq_ele pending_prq_ele_t;
367 :
368 :
369 : #define PRQ_NAME pending_prq
370 13532595 : #define PRQ_T pending_prq_ele_t
371 : #define PRQ_EXPLICIT_TIMEOUT 0
372 : /* returns 1 if x is strictly after y */
373 12067920 : #define PRQ_AFTER(x,y) (__extension__( { \
374 12067920 : int cmp0 = (int)(x).linear_block_number - (int)(y).linear_block_number; \
375 12067920 : fd_int_if( cmp0!=0, cmp0>0, (x).score>(y).score ); \
376 12067920 : }))
377 : #include "../../util/tmpl/fd_prq.c"
378 :
379 : /* fd_rdisp_blockinfo_t maintains a little metadata about transactions for each
380 : slot. */
381 : struct fd_rdisp_blockinfo {
382 : FD_RDISP_BLOCK_TAG_T block;
383 : uint linear_block_number;
384 :
385 : uint insert_ready:1;
386 : uint schedule_ready:1;
387 : uint staged:1;
388 : uint staging_lane:2; /* ignored if staged==0 */
389 : uint last_insert_was_serializing:1;
390 :
391 : uint inserted_cnt;
392 : uint dispatched_cnt;
393 : uint completed_cnt;
394 : uint last_serializing;
395 :
396 : uint map_chain_next;
397 : uint ll_next;
398 : unstaged_txn_ll_t ll[ 1 ]; /* used only when unstaged */
399 : zombie_dlist_t zombie_list[ 1 ];
400 : };
401 : typedef struct fd_rdisp_blockinfo fd_rdisp_blockinfo_t;
402 :
403 : #define POOL_NAME block_pool
404 297 : #define POOL_T fd_rdisp_blockinfo_t
405 : #define POOL_IDX_T uint
406 988818 : #define POOL_NEXT ll_next
407 : #define POOL_SENTINEL 1
408 : #include "../../util/tmpl/fd_pool.c"
409 :
410 : #define MAP_NAME block_map
411 : #define MAP_ELE_T fd_rdisp_blockinfo_t
412 : #define MAP_KEY_T FD_RDISP_BLOCK_TAG_T
413 395787 : #define MAP_KEY block
414 4045788 : #define MAP_NEXT map_chain_next
415 5305476 : #define MAP_IDX_T uint
416 : #include "../../util/tmpl/fd_map_chain.c"
417 :
418 : #define SLIST_NAME block_slist
419 : #define SLIST_ELE_T fd_rdisp_blockinfo_t
420 395760 : #define SLIST_IDX_T uint
421 791535 : #define SLIST_NEXT ll_next
422 : #include "../../util/tmpl/fd_slist.c"
423 :
424 : struct fd_rdisp_unstaged {
425 : FD_RDISP_BLOCK_TAG_T block;
426 :
427 : uint writable_cnt;
428 : uint readonly_cnt;
429 : fd_acct_addr_t keys[MAX_ACCT_PER_TXN];
430 : };
431 : typedef struct fd_rdisp_unstaged fd_rdisp_unstaged_t;
432 :
433 : typedef struct {
434 : pending_prq_ele_t * pending;
435 : ulong linear_block_number;
436 : block_slist_t block_ll[1];
437 : ulong inserted_cnt;
438 : ulong dispatched_cnt;
439 : ulong completed_cnt;
440 : } per_lane_info_t;
441 :
442 : /* We maintain two maps from pubkeys to acct_info_t. The first one is
443 : the main acct_map, just called acct_map. All pubkeys in this map
444 : have >0 references in the one of the staging lane DAGs. When an
445 : account goes to 0 references, it gets removed from main map_chain and
446 : moved to free map_chain, called free_acct_map. The free_acct_map
447 : exists to maintain the reference count EMA information lazily.
448 : Unless we need the acct_info_t for something in the DAG, we might as
449 : well maintain the EMA info.
450 :
451 : When we start up, all the acct_info_t structs are in the
452 : free_acct_dlist. Whenever something is added to the free_acct_map,
453 : it's also added to the tail of the free_acct_dlist. When we need an
454 : acct_info_t that's not in the free_acct_map, we pop the head of the
455 : free_acct_dlist. In general, the free_acct_dlist contains everything
456 : in the free_acct_map, potentially plus some elements that have never
457 : been used; all acct_info_t objects are in exactly one of the main
458 : acct_map and the free_acct_dlist (not free_acct_map). See
459 : acct_info_t for more information about this. */
460 :
461 : struct fd_rdisp {
462 : ulong depth;
463 : ulong block_depth;
464 :
465 : ulong global_insert_cnt;
466 : ulong unstaged_lblk_num;
467 :
468 : /* pool: an fd_pool, indexed [0, depth+1), with 0 being a sentinel */
469 : fd_rdisp_txn_t * pool;
470 : fd_rdisp_unstaged_t * unstaged; /* parallel to pool with additional info */
471 :
472 : block_map_t * blockmap; /* map chain */
473 : fd_rdisp_blockinfo_t * block_pool;
474 :
475 : int free_lanes; /* a bitmask */
476 : per_lane_info_t lanes[4];
477 :
478 : acct_map_t * acct_map;
479 : acct_map_t * free_acct_map;
480 : /* acct_pool is not an fd_pool, but is just a flat array, since we
481 : don't need to acquire and release from it because of the dlist. */
482 : acct_info_t * acct_pool;
483 : free_dlist_t free_acct_dlist[1];
484 : };
485 :
486 : typedef struct fd_rdisp fd_rdisp_t;
487 :
488 :
489 : #define ACCT_ITER_TO_PTR( iter ) (__extension__( { \
490 : ulong __idx = fd_txn_acct_iter_idx( iter ); \
491 : fd_ptr_if( __idx<fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ), accts, alt_adj )+__idx; \
492 : }))
493 :
494 :
495 3261 : ulong fd_rdisp_align( void ) { return 128UL; }
496 :
497 : ulong
498 : fd_rdisp_footprint( ulong depth,
499 291 : ulong block_depth ) {
500 291 : if( FD_UNLIKELY( (depth>FD_RDISP_MAX_DEPTH) | (depth<2UL) |
501 291 : (block_depth>FD_RDISP_MAX_BLOCK_DEPTH) | (block_depth<4UL) ) ) return 0UL;
502 :
503 291 : ulong chain_cnt = block_map_chain_cnt_est( block_depth );
504 291 : ulong acct_depth = depth*MAX_ACCT_PER_TXN;
505 291 : ulong acct_chain_cnt = acct_map_chain_cnt_est( acct_depth );
506 :
507 291 : ulong l = FD_LAYOUT_INIT;
508 291 : l = FD_LAYOUT_APPEND( l, fd_rdisp_align(), sizeof(fd_rdisp_t) );
509 291 : l = FD_LAYOUT_APPEND( l, pool_align(), pool_footprint ( depth+1UL ) ); /* pool */
510 291 : l = FD_LAYOUT_APPEND( l, alignof(fd_rdisp_unstaged_t), sizeof(fd_rdisp_unstaged_t)*( depth+1UL ) ); /* unstaged */
511 291 : l = FD_LAYOUT_APPEND( l, block_map_align(), block_map_footprint ( chain_cnt ) ); /* blockmap */
512 291 : l = FD_LAYOUT_APPEND( l, block_pool_align(), block_pool_footprint ( block_depth+1UL ) ); /* block_pool */
513 291 : l = FD_LAYOUT_APPEND( l, pending_prq_align(), 4UL*pending_prq_footprint ( depth ) ); /* pending */
514 291 : l = FD_LAYOUT_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) ); /* acct_map */
515 291 : l = FD_LAYOUT_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) ); /* free_acct_map */
516 291 : l = FD_LAYOUT_APPEND( l, alignof(acct_info_t), (acct_depth+1UL)*sizeof(acct_info_t) ); /* acct_pool */
517 291 : return FD_LAYOUT_FINI( l, fd_rdisp_align() );
518 291 : }
519 :
520 : void *
521 : fd_rdisp_new( void * mem,
522 : ulong depth,
523 : ulong block_depth,
524 99 : ulong seed ) {
525 99 : if( FD_UNLIKELY( (depth>FD_RDISP_MAX_DEPTH) | (depth<2UL) |
526 99 : (block_depth>FD_RDISP_MAX_BLOCK_DEPTH) | (block_depth<4UL) ) ) return NULL;
527 :
528 99 : ulong chain_cnt = block_map_chain_cnt_est( block_depth );
529 99 : ulong acct_depth = depth*MAX_ACCT_PER_TXN;
530 99 : ulong acct_chain_cnt = acct_map_chain_cnt_est( acct_depth );
531 :
532 99 : FD_SCRATCH_ALLOC_INIT( l, mem );
533 99 : fd_rdisp_t * disp = FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_align(), sizeof(fd_rdisp_t) );
534 99 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( depth+1UL ) );
535 99 : void * _unstaged = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_rdisp_unstaged_t), sizeof(fd_rdisp_unstaged_t)*( depth+1UL ) );
536 99 : void * _bmap = FD_SCRATCH_ALLOC_APPEND( l, block_map_align(), block_map_footprint ( chain_cnt ) );
537 99 : void * _bpool = FD_SCRATCH_ALLOC_APPEND( l, block_pool_align(), block_pool_footprint ( block_depth+1UL ) );
538 99 : uchar * _pending = FD_SCRATCH_ALLOC_APPEND( l, pending_prq_align(), 4UL*pending_prq_footprint ( depth ) );
539 99 : void * _acct_map = FD_SCRATCH_ALLOC_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) );
540 99 : void * _freea_map = FD_SCRATCH_ALLOC_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) );
541 99 : acct_info_t * apool = FD_SCRATCH_ALLOC_APPEND( l, alignof(acct_info_t), (acct_depth+1UL)*sizeof(acct_info_t) );
542 99 : FD_SCRATCH_ALLOC_FINI( l, fd_rdisp_align() );
543 :
544 99 : disp->depth = depth;
545 99 : disp->block_depth = block_depth;
546 99 : disp->global_insert_cnt = 0UL;
547 99 : disp->unstaged_lblk_num = 0UL;
548 :
549 99 : fd_rdisp_txn_t * temp_pool_join = pool_join( pool_new( _pool, depth+1UL ) );
550 243879 : for( ulong i=0UL; i<depth+1UL; i++ ) temp_pool_join[ i ].in_degree = IN_DEGREE_FREE;
551 99 : pool_leave( temp_pool_join );
552 :
553 99 : memset( _unstaged, '\0', sizeof(fd_rdisp_unstaged_t)*(depth+1UL) );
554 :
555 99 : block_map_new ( _bmap, chain_cnt, seed );
556 99 : block_pool_new( _bpool, block_depth+1UL );
557 :
558 99 : fd_rdisp_blockinfo_t * bpool_temp_join = block_pool_join( _bpool );
559 197283 : for( ulong i=0UL; i<block_depth+1UL; i++ ) zombie_dlist_new( bpool_temp_join[ i ].zombie_list );
560 99 : block_pool_leave( bpool_temp_join );
561 :
562 99 : disp->free_lanes = 0xF;
563 495 : for( ulong i=0UL; i<4UL; i++ ) {
564 396 : pending_prq_new( _pending, depth );
565 396 : _pending += pending_prq_footprint( depth );
566 :
567 396 : disp->lanes[i].linear_block_number = 0UL;
568 396 : disp->lanes[i].inserted_cnt = 0U;
569 396 : disp->lanes[i].dispatched_cnt = 0U;
570 396 : disp->lanes[i].completed_cnt = 0U;
571 396 : }
572 :
573 99 : acct_map_new( _acct_map, acct_chain_cnt, fd_ulong_hash( seed+1UL ) );
574 99 : acct_map_new( _freea_map, acct_chain_cnt, fd_ulong_hash( seed+2UL ) );
575 :
576 99 : free_dlist_t * temp_join = free_dlist_join( free_dlist_new( disp->free_acct_dlist ) );
577 15595683 : for( ulong i=1UL; i<acct_depth+1UL; i++ ) {
578 15595584 : apool[ i ].next = apool[ i ].prev = 0U;
579 15595584 : free_dlist_idx_push_tail( disp->free_acct_dlist, i, apool );
580 15595584 : }
581 99 : free_dlist_leave( temp_join );
582 :
583 99 : return disp;
584 99 : }
585 :
586 : fd_rdisp_t *
587 99 : fd_rdisp_join( void * mem ) {
588 99 : fd_rdisp_t * disp = (fd_rdisp_t *)mem;
589 :
590 99 : ulong depth = disp->depth;
591 99 : ulong block_depth = disp->block_depth;
592 99 : ulong chain_cnt = block_map_chain_cnt_est( block_depth );
593 99 : ulong acct_depth = depth*MAX_ACCT_PER_TXN;
594 99 : ulong acct_chain_cnt = acct_map_chain_cnt_est( acct_depth );
595 :
596 99 : FD_SCRATCH_ALLOC_INIT( l, mem );
597 99 : /* */ FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_align(), sizeof(fd_rdisp_t) );
598 99 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( depth+1UL ) );
599 99 : void * _unstaged = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_rdisp_unstaged_t), sizeof(fd_rdisp_unstaged_t)*( depth+1UL ) );
600 99 : void * _bmap = FD_SCRATCH_ALLOC_APPEND( l, block_map_align(), block_map_footprint ( chain_cnt ) );
601 99 : void * _bpool = FD_SCRATCH_ALLOC_APPEND( l, block_pool_align(), block_pool_footprint ( block_depth+1UL ) );
602 99 : uchar * _pending = FD_SCRATCH_ALLOC_APPEND( l, pending_prq_align(), 4UL*pending_prq_footprint ( depth ) );
603 99 : void * _acct_map = FD_SCRATCH_ALLOC_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) );
604 99 : void * _freea_map = FD_SCRATCH_ALLOC_APPEND( l, acct_map_align(), acct_map_footprint ( acct_chain_cnt ) );
605 99 : acct_info_t * apool = FD_SCRATCH_ALLOC_APPEND( l, alignof(acct_info_t), (acct_depth+1UL)*sizeof(acct_info_t) );
606 99 : FD_SCRATCH_ALLOC_FINI( l, fd_rdisp_align() );
607 :
608 99 : disp->pool = pool_join( _pool );
609 99 : disp->unstaged = (fd_rdisp_unstaged_t *)_unstaged;
610 99 : disp->blockmap = block_map_join( _bmap );
611 99 : disp->block_pool = block_pool_join( _bpool );
612 :
613 197283 : for( ulong i=0UL; i<block_depth+1UL; i++ ) zombie_dlist_join( disp->block_pool[ i ].zombie_list );
614 :
615 495 : for( ulong i=0UL; i<4UL; i++ ) {
616 396 : disp->lanes[i].pending = pending_prq_join( _pending );
617 396 : _pending += pending_prq_footprint( depth );
618 396 : }
619 :
620 99 : disp->acct_map = acct_map_join( _acct_map );
621 99 : disp->free_acct_map = acct_map_join( _freea_map );
622 99 : disp->acct_pool = apool;
623 99 : free_dlist_join( disp->free_acct_dlist );
624 :
625 99 : return disp;
626 99 : }
627 :
628 : static inline void
629 : free_lane( fd_rdisp_t * disp,
630 2535 : ulong staging_lane ) {
631 2535 : disp->free_lanes |= 1<<staging_lane;
632 2535 : per_lane_info_t * l = disp->lanes+staging_lane;
633 2535 : FD_TEST( pending_prq_cnt( l->pending )==0UL );
634 2535 : l->linear_block_number = 0UL;
635 2535 : l->inserted_cnt = 0UL;
636 2535 : l->dispatched_cnt = 0UL;
637 2535 : l->completed_cnt = 0UL;
638 2535 : block_slist_delete( block_slist_leave( l->block_ll ) );
639 2535 : }
640 :
641 : static inline void
642 : alloc_lane( fd_rdisp_t * disp,
643 2550 : ulong staging_lane ) {
644 2550 : disp->free_lanes &= ~(1<<staging_lane);
645 2550 : block_slist_join( block_slist_new( disp->lanes[staging_lane].block_ll ) );
646 2550 : }
647 :
648 : ulong
649 : fd_rdisp_suggest_staging_lane( fd_rdisp_t const * disp,
650 : FD_RDISP_BLOCK_TAG_T parent_block,
651 0 : int duplicate ) {
652 :
653 : /* 1. If it's a duplicate, suggest FD_RDISP_UNSTAGED */
654 0 : if( FD_UNLIKELY( duplicate ) ) return FD_RDISP_UNSTAGED;
655 :
656 : /* 2. If parent is the last block in any existing staging lane, suggest
657 : that lane */
658 0 : fd_rdisp_blockinfo_t const * block_pool = disp->block_pool;
659 0 : fd_rdisp_blockinfo_t const * block = block_map_ele_query_const( disp->blockmap, &parent_block, NULL, block_pool );
660 0 : if( FD_LIKELY( block && block->insert_ready && block->staged ) ) return block->staging_lane;
661 :
662 : /* 3. If there is at least one free lane, suggest a free lane */
663 0 : if( FD_LIKELY( disp->free_lanes!=0 ) ) return (ulong)fd_uint_find_lsb( (uint)disp->free_lanes );
664 :
665 : /* 4. Else, suggest FD_RDISP_UNSTAGED */
666 0 : return FD_RDISP_UNSTAGED;
667 0 : }
668 :
669 : int
670 : fd_rdisp_add_block( fd_rdisp_t * disp,
671 : FD_RDISP_BLOCK_TAG_T new_block,
672 395787 : ulong staging_lane ) {
673 395787 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
674 :
675 395787 : if( FD_UNLIKELY( !block_pool_free( block_pool ) ) ) return -1;
676 395787 : if( FD_UNLIKELY( ULONG_MAX!=block_map_idx_query_const( disp->blockmap, &new_block, ULONG_MAX, block_pool ) ) ) return -1;
677 395781 : fd_rdisp_blockinfo_t * block = block_pool_ele_acquire( block_pool );
678 395781 : block->block = new_block;
679 395781 : block_map_ele_insert( disp->blockmap, block, block_pool );
680 :
681 395781 : block->insert_ready = 1;
682 395781 : block->staged = staging_lane!=FD_RDISP_UNSTAGED;
683 395781 : block->staging_lane = (uint)(staging_lane & 0x3UL);
684 395781 : block->last_insert_was_serializing = 0U;
685 :
686 395781 : block->inserted_cnt = 0U;
687 395781 : block->dispatched_cnt = 0U;
688 395781 : block->completed_cnt = 0U;
689 395781 : block->last_serializing = 0U;
690 :
691 395781 : if( FD_UNLIKELY( staging_lane==FD_RDISP_UNSTAGED ) ) {
692 18 : block->schedule_ready = 1;
693 18 : block->linear_block_number = (uint)disp->unstaged_lblk_num++;
694 18 : unstaged_txn_ll_join( unstaged_txn_ll_new( block->ll ) );
695 395763 : } else {
696 395763 : block->linear_block_number = (uint)disp->lanes[staging_lane].linear_block_number++;
697 395763 : block->schedule_ready = (uint)(1 & (disp->free_lanes >> staging_lane));
698 :
699 395763 : if( FD_LIKELY( disp->free_lanes & (1<<staging_lane) ) ) alloc_lane( disp, staging_lane );
700 :
701 395763 : block_slist_t * sl = disp->lanes[staging_lane].block_ll;
702 395763 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_tail( sl, block_pool )->insert_ready = 0;
703 395763 : block_slist_ele_push_tail( sl, block, block_pool );
704 395763 : }
705 395781 : return 0;
706 395787 : }
707 :
708 :
709 :
710 : int
711 : fd_rdisp_remove_block( fd_rdisp_t * disp,
712 395694 : FD_RDISP_BLOCK_TAG_T block_tag ) {
713 395694 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
714 :
715 395694 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, block_pool );
716 395694 : if( FD_UNLIKELY( block==NULL ) ) return -1;
717 :
718 395685 : FD_TEST( block->schedule_ready );
719 395685 : FD_TEST( block->completed_cnt==block->inserted_cnt );
720 395685 : FD_TEST( zombie_dlist_is_empty( block->zombie_list, disp->pool ) );
721 :
722 395685 : if( FD_LIKELY( block->staged ) ) {
723 395676 : ulong staging_lane = (ulong)block->staging_lane;
724 395676 : block_slist_t * sl = disp->lanes[staging_lane].block_ll;
725 :
726 395676 : FD_TEST( block==block_slist_ele_peek_head( sl, block_pool ) );
727 395676 : block_slist_idx_pop_head( sl, block_pool );
728 395676 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_head( sl, block_pool )->schedule_ready = 1;
729 2460 : else free_lane( disp, staging_lane );
730 395676 : } else {
731 9 : unstaged_txn_ll_delete( unstaged_txn_ll_leave( block->ll ) );
732 9 : }
733 395685 : block_pool_idx_release( block_pool, block_map_idx_remove( disp->blockmap, &block_tag, ULONG_MAX, block_pool ) );
734 :
735 395685 : return 0;
736 395685 : }
737 :
738 :
739 : int
740 : fd_rdisp_abandon_block( fd_rdisp_t * disp,
741 72 : FD_RDISP_BLOCK_TAG_T block_tag ) {
742 72 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
743 :
744 72 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, disp->block_pool );
745 72 : if( FD_UNLIKELY( block==NULL ) ) return -1;
746 :
747 69 : FD_TEST( block->schedule_ready );
748 69 : FD_TEST( block->dispatched_cnt==block->completed_cnt ); /* TODO: remove this when it can call complete properly */
749 78 : while( block->completed_cnt<block->inserted_cnt ) {
750 : /* because there is nothing DISPATCHED, there has to be something
751 : READY */
752 9 : ulong txn = fd_rdisp_get_next_ready( disp, block_tag );
753 9 : FD_TEST( txn );
754 9 : fd_rdisp_complete_txn( disp, txn, 1 );
755 9 : }
756 69 : while( !zombie_dlist_is_empty( block->zombie_list, disp->pool ) ) {
757 : /* rdisp_complete_txn removes the peeked head */
758 0 : fd_rdisp_complete_txn( disp, zombie_dlist_idx_peek_head( block->zombie_list, disp->pool ), 1 );
759 0 : }
760 :
761 69 : if( FD_LIKELY( block->staged ) ) {
762 69 : ulong staging_lane = (ulong)block->staging_lane;
763 69 : block_slist_t * sl = disp->lanes[staging_lane].block_ll;
764 :
765 69 : FD_TEST( block==block_slist_ele_peek_head( sl, block_pool ) );
766 69 : block_slist_idx_pop_head( sl, block_pool );
767 69 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_head( sl, block_pool )->schedule_ready = 1;
768 60 : else free_lane( disp, staging_lane );
769 69 : } else {
770 0 : unstaged_txn_ll_delete( unstaged_txn_ll_leave( block->ll ) );
771 0 : }
772 69 : block_pool_idx_release( disp->block_pool, block_map_idx_remove( disp->blockmap, &block_tag, ULONG_MAX, disp->block_pool ) );
773 :
774 69 : return 0;
775 69 : }
776 :
777 : static void
778 : add_edges( fd_rdisp_t * disp,
779 : fd_rdisp_txn_t * ele,
780 : fd_acct_addr_t const * addr,
781 : ulong addr_cnt,
782 : uint staging_lane,
783 : int writable,
784 : int update_score );
785 : /* updates in_degree, edge_cnt_etc */
786 :
787 : int
788 : fd_rdisp_promote_block( fd_rdisp_t * disp,
789 : FD_RDISP_BLOCK_TAG_T block_tag,
790 12 : ulong staging_lane ) {
791 12 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
792 12 : per_lane_info_t * lane = disp->lanes + staging_lane;
793 12 : block_slist_t * sl = lane->block_ll;
794 :
795 12 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, block_pool );
796 12 : if( FD_UNLIKELY( block==NULL ) ) return -1;
797 12 : if( FD_UNLIKELY( block->staged ) ) return -1;
798 :
799 12 : block->staged = 1;
800 12 : block->staging_lane = (uint)(staging_lane & 0x3);
801 12 : block->insert_ready = 1;
802 12 : block->schedule_ready = (uint)(1 & (disp->free_lanes >> staging_lane));
803 :
804 12 : if( FD_LIKELY( disp->free_lanes & (1<<staging_lane) ) ) alloc_lane( disp, staging_lane );
805 :
806 12 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_tail( sl, block_pool )->insert_ready = 0;
807 12 : block_slist_ele_push_tail( sl, block, block_pool );
808 12 : uint linear_block_number = (uint)lane->linear_block_number++;
809 12 : block->linear_block_number = linear_block_number;
810 :
811 12 : unstaged_txn_ll_iter_t next;
812 12 : for( unstaged_txn_ll_iter_t iter = unstaged_txn_ll_iter_init( block->ll, disp->pool );
813 330 : !unstaged_txn_ll_iter_done( iter, block->ll, disp->pool );
814 318 : iter = next ) {
815 318 : next = unstaged_txn_ll_iter_next( iter, block->ll, disp->pool );
816 :
817 318 : fd_rdisp_txn_t * ele = unstaged_txn_ll_iter_ele( iter, block->ll, disp->pool );
818 318 : fd_rdisp_unstaged_t * uns = disp->unstaged + unstaged_txn_ll_iter_idx( iter, block->ll, disp->pool );
819 318 : FD_TEST( ele->in_degree==IN_DEGREE_UNSTAGED );
820 :
821 318 : ele->in_degree = 0U;
822 318 : ele->edge_cnt_etc = (uint)(-1); /* set w_cnt_1 to -1 */
823 :
824 318 : add_edges( disp, ele, uns->keys, uns->writable_cnt, (uint)staging_lane, 1, 0 );
825 318 : add_edges( disp, ele, uns->keys+uns->writable_cnt, uns->readonly_cnt, (uint)staging_lane, 0, 0 );
826 :
827 318 : ele->edge_cnt_etc &= 0x3FFFU;
828 318 : ele->edge_cnt_etc |= (uint)staging_lane<<14;
829 318 : ele->edge_cnt_etc |= linear_block_number<<16;
830 :
831 318 : if( FD_UNLIKELY( ele->in_degree==0U ) ) {
832 6 : pending_prq_ele_t temp[1] = {{ .score = ele->score, .linear_block_number = linear_block_number, .txn_idx = (uint)(ele-disp->pool)}};
833 6 : pending_prq_insert( lane->pending, temp );
834 6 : }
835 318 : }
836 12 : unstaged_txn_ll_delete( unstaged_txn_ll_leave( block->ll ) );
837 :
838 12 : lane->inserted_cnt += block->inserted_cnt;
839 12 : lane->dispatched_cnt += block->dispatched_cnt;
840 12 : lane->completed_cnt += block->completed_cnt;
841 :
842 12 : return 0;
843 12 : }
844 :
845 : int
846 : fd_rdisp_demote_block( fd_rdisp_t * disp,
847 15 : FD_RDISP_BLOCK_TAG_T block_tag ) {
848 15 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
849 :
850 15 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &block_tag, NULL, block_pool );
851 15 : if( FD_UNLIKELY( block==NULL ) ) return -1;
852 15 : if( FD_UNLIKELY( !block->staged ) ) return -1;
853 15 : if( FD_UNLIKELY( !block->schedule_ready ) ) return -1;
854 15 : if( FD_UNLIKELY( block->completed_cnt!=block->inserted_cnt ) ) FD_LOG_ERR(( "demote_block called with non-empty block" ));
855 15 : ulong staging_lane = block->staging_lane;
856 15 : block->staged = 0;
857 :
858 15 : per_lane_info_t * lane = disp->lanes + staging_lane;
859 15 : block_slist_t * sl = lane->block_ll;
860 :
861 15 : lane->inserted_cnt -= block->inserted_cnt;
862 15 : lane->dispatched_cnt -= block->dispatched_cnt;
863 15 : lane->completed_cnt -= block->completed_cnt;
864 :
865 15 : block->linear_block_number = (uint)disp->unstaged_lblk_num++;
866 :
867 : /* staged and schedule_ready means it must be the head of the staging lane */
868 15 : FD_TEST( block_slist_ele_peek_head( sl, block_pool )==block );
869 15 : block_slist_idx_pop_head( sl, block_pool );
870 :
871 15 : unstaged_txn_ll_join( unstaged_txn_ll_new( block->ll ) );
872 :
873 15 : if( FD_LIKELY( !block_slist_is_empty( sl, block_pool ) ) ) block_slist_ele_peek_head( sl, block_pool )->schedule_ready = 1;
874 15 : else free_lane( disp, staging_lane );
875 15 : return 0;
876 15 : }
877 :
878 : int
879 : fd_rdisp_rekey_block( fd_rdisp_t * disp,
880 : FD_RDISP_BLOCK_TAG_T new_tag,
881 6 : FD_RDISP_BLOCK_TAG_T old_tag ) {
882 6 : fd_rdisp_blockinfo_t * block_pool = disp->block_pool;
883 :
884 6 : if( FD_UNLIKELY( NULL!= block_map_ele_query_const( disp->blockmap, &new_tag, NULL, block_pool ) ) ) return -1;
885 6 : fd_rdisp_blockinfo_t * block = block_map_ele_query ( disp->blockmap, &old_tag, NULL, block_pool );
886 6 : if( FD_UNLIKELY( NULL== block ) ) return -1;
887 :
888 6 : block_map_idx_remove( disp->blockmap, &old_tag, ULONG_MAX, block_pool );
889 6 : block->block = new_tag;
890 6 : block_map_ele_insert( disp->blockmap, block, block_pool );
891 6 : return 0;
892 6 : }
893 :
894 :
895 : /* "Registers" a reference to the account in info at transaction
896 : global_insert_cnt. Returns the value of the EMA, which is an
897 : estimate of the probability that the next transaction also references
898 : the account. This value does not matter for correctness, other than
899 : that it is in [0, 1), which is why floating point arithmetic is
900 : acceptable here. */
901 : static inline float
902 : update_ema( acct_info_t * info,
903 2940699 : ulong global_insert_cnt ) {
904 : #if FD_RDISP_DISABLE_EMA
905 : (void)info;
906 : (void)global_insert_cnt;
907 : return 0.0f;
908 : #else
909 5881398 : #define ALPHA 0.005f
910 : /* The normal EMA update equation is
911 : e_i = (alpha) * x_i + (1-alpha)*e_{i-1},
912 : where alpha is a constant in (0,1). Let L be the last reference of
913 : the account, and G be the current global_insert_cnt value. We know
914 : that e_L = ema_refs, and that for i in [L+1, G), x_i = 0.
915 : That means
916 : e_{G-1} = (1-alpha)^(G-L-1) * ema_refs
917 : e_G = alpha + (1-alpha)^(G-L) * ema_refs
918 : */
919 : /* last_ref only captures the low 24 bits, so we guess its the highest
920 : value for them that would still make it less than
921 : global_insert_cnt. Turns out, we can calculate that with just an
922 : AND. We need to make sure that in the rare case it is actually
923 : 2^24 away, we don't use a delta of 0. We also want to make sure
924 : that even with inexact float math, we never get to 1.0, so we bias
925 : the exponent up slightly. */
926 2940699 : ulong last_ref = (ulong)info->last_ref;
927 2940699 : ulong delta = fd_ulong_max( (global_insert_cnt - last_ref) & 0xFFFFFFUL, 1UL );
928 2940699 : float ema_refs = ALPHA + powf( 1.0f-ALPHA, 0.05f+(float)delta ) * info->ema_refs;
929 :
930 2940699 : info->ema_refs = ema_refs;
931 2940699 : info->last_ref = (uint)(global_insert_cnt & 0xFFFFFFUL);
932 2940699 : #undef ALPHA
933 :
934 2940699 : return ema_refs;
935 2940699 : #endif
936 2940699 : }
937 :
938 : static void
939 : add_edges( fd_rdisp_t * disp,
940 : fd_rdisp_txn_t * ele,
941 : fd_acct_addr_t const * addrs,
942 : ulong addr_cnt,
943 : uint lane,
944 : int writable,
945 3315756 : int update_score ) {
946 : /* When we first start, the low 14 bits are 0x3FFF, so adding the first
947 : non-empty writable batch wraps them to w_cnt-1 with r_cnt==0.
948 : Thereafter, the low 7 bits store w_cnt_1 and the next 7 bits store
949 : r_cnt. Both counts fit without overflow because their sum is at
950 : most MAX_ACCT_PER_TXN. */
951 :
952 3315756 : ulong w_cnt = (ele->edge_cnt_etc + 1U) & 0x7FU;
953 3315756 : ulong r_cnt = ((ele->edge_cnt_etc + 1U)>>7) & 0x7FU;
954 3315756 : ulong acct_idx = w_cnt + r_cnt;
955 3315756 : ulong edge_idx = w_cnt + 3UL*r_cnt;
956 :
957 6237885 : for( ulong i=0UL; i<addr_cnt; i++ ) {
958 2922129 : fd_acct_addr_t const * addr = addrs+i;
959 2922129 : acct_info_t * ai = NULL;
960 :
961 : /* Step 1: lookup the pubkey */
962 2922129 : ulong idx = acct_map_idx_query( disp->acct_map, addr, ULONG_MAX, disp->acct_pool );
963 2922129 : if( FD_UNLIKELY( idx==ULONG_MAX ) ) {
964 1086957 : idx = acct_map_idx_query( disp->free_acct_map, addr, ULONG_MAX, disp->acct_pool );
965 1086957 : if( FD_UNLIKELY( idx==ULONG_MAX ) ) {
966 : /* The acct pool is sized so that the list cannot be empty at this
967 : point. However, the element at the head might be the free
968 : map with a different pubkey. */
969 597963 : idx = free_dlist_idx_peek_head( disp->free_acct_dlist, disp->acct_pool );
970 597963 : ai = disp->acct_pool+idx;
971 :
972 : /* CACHED -> FREE transition */
973 597963 : if( FD_LIKELY( ai->next!=0U ) ) {
974 183423 : acct_map_idx_remove_fast( disp->free_acct_map, idx, disp->acct_pool );
975 183423 : }
976 :
977 : /* FREE -> ACTIVE transition */
978 597963 : ai->key = *addr;
979 597963 : ai->flags = 0U;
980 597963 : ai->last_ref = 0U;
981 597963 : ai->ema_refs = 0.0f;
982 597963 : } else {
983 : /* CACHED -> ACTIVE transition */
984 488994 : ai = disp->acct_pool+idx;
985 488994 : ai->flags = 0U; /* FIXME: unnecessary */
986 488994 : acct_map_idx_remove_fast( disp->free_acct_map, idx, disp->acct_pool );
987 488994 : }
988 : /* In either case, at this point, the element is not in any map
989 : but is in free_acct_dlist. It has the right key. last_ref, and
990 : ema_refs are valid. flags is 0. */
991 1086957 : free_dlist_idx_remove( disp->free_acct_dlist, idx, disp->acct_pool );
992 1086957 : memset( ai->last_reference, '\0', sizeof(ai->last_reference) );
993 1086957 : acct_map_idx_insert( disp->acct_map, idx, disp->acct_pool );
994 1086957 : }
995 2922129 : ai = disp->acct_pool+idx;
996 : /* At this point, in all cases, the acct_info is now in the ACTIVE
997 : state. It's in acct_map, not in free_acct_map, and not in
998 : free_acct_dlist. */
999 :
1000 : /* Assume that transactions are drawn randomly from some large
1001 : distribution of potential transactions. We want to estimate the
1002 : expected value of the probability that this transaction conflicts
1003 : with the next transaction that is sampled. Two transactions
1004 : conflict if they conflict on any account, and in general, they
1005 : conflict if they both reference the same account, unless both
1006 : this transaction and the next one only read it. We don't have
1007 : read/write info, so the best guess we have is that the next
1008 : transaction does the same thing to the account that this one
1009 : does. That means we only really care about the accounts that
1010 : this transaction writes to. Label those a_1, a_2, ..., a_i, and
1011 : suppose the probability that the next transaction references a_i
1012 : is p_i (determined using the EMA). Now then, assuming accounts
1013 : are independent (which is false, but whatever), then the
1014 : probability that the next transaction does not conflict with this
1015 : account is:
1016 : (1-p_1) * (1-p_2) * (1 - p_i).
1017 :
1018 : Since for the treap, a lower value means we'll schedule it
1019 : earlier, we'll use the probability of non-conflict as the
1020 : fractional part of the score. */
1021 2922129 : if( FD_LIKELY( update_score ) ) {
1022 2902836 : float score_change = 1.0f - update_ema( ai, disp->global_insert_cnt );
1023 2902836 : ele->score *= fd_float_if( writable, score_change, 1.0f );
1024 2902836 : }
1025 :
1026 : /* Step 2: add edge. There are 4 cases depending on whether this is
1027 : a writer or not and whether the previous reference was a writer
1028 : or not. */
1029 2922129 : int _ignore;
1030 :
1031 2922129 : edge_t ref_to_pa = ai->last_reference[ lane ];
1032 2922129 : edge_t ref_to_me = (uint)((ulong)((ele - disp->pool)<<8) | acct_idx);
1033 2922129 : edge_t * pa = FOLLOW_EDGE( disp->pool, ai->last_reference[ lane ], _ignore );
1034 2922129 : edge_t * me = ele->edges + edge_idx;
1035 :
1036 : /* In the case that this is the first txn in the DAG, pa will point
1037 : to edges[0] of the sentinel element, pool[0]. We don't care
1038 : about what is stored there, so just set it up as a dummy element
1039 : to make the rest of the code work properly in this case too. If
1040 : this is a read, we want me->sibli to ref_to_me in case 4; if this
1041 : is a write, we want to set me->sibli to 0 in case 2, but we need
1042 : to make sure pb==pa. */
1043 2922129 : disp->pool->edges[0] = (1U<<31) | (uint)idx;
1044 2922129 : disp->pool->edges[1] = fd_uint_if( writable, 0U, ref_to_me );
1045 2922129 : disp->pool->edges[2] = fd_uint_if( writable, 0U, ref_to_me );
1046 :
1047 2922129 : int flags = ai->flags;
1048 :
1049 2922129 : if( writable ) { /* also should be known at compile time */
1050 1386039 : if( flags & ACCT_INFO_FLAG_LAST_REF_WAS_WRITE( lane ) ) { /* unclear prob */
1051 : /* Case 1: w-w. The parent is the special last pointer. Point
1052 : the parent to me, and set me to the last pointer. */
1053 256695 : *me = *pa;
1054 256695 : *pa = ref_to_me;
1055 1129344 : } else {
1056 : /* Case 2: r-w. This is the tricky case because there could be
1057 : multiple readers. We need to set all the last readers' child
1058 : pointers to me. */
1059 1129344 : *me = *pa;
1060 1129344 : *pa = ref_to_me;
1061 1129344 : edge_t * pb = FOLLOW_EDGE( disp->pool, pa[1], _ignore );
1062 : /* Intentionally skip the first in_degree increment, because it
1063 : will be done later */
1064 1212099 : while( pb!=pa ) {
1065 82755 : *pb = ref_to_me;
1066 82755 : ele->in_degree++;
1067 82755 : pb = FOLLOW_EDGE( disp->pool, pb[1], _ignore );
1068 82755 : }
1069 1129344 : flags |= ACCT_INFO_FLAG_LAST_REF_WAS_WRITE( lane ) | ACCT_INFO_FLAG_ANY_WRITERS( lane );
1070 1129344 : }
1071 1536090 : } else {
1072 1536090 : if( flags & ACCT_INFO_FLAG_LAST_REF_WAS_WRITE( lane ) ) { /* unclear prob */
1073 : /* Case 3: w-r. Similar to case 1, but need to initialize my
1074 : next and prev sibling pointers too. */
1075 92217 : *me = *pa;
1076 92217 : *pa = ref_to_me;
1077 92217 : me[1] = ref_to_me; /* next */
1078 92217 : me[2] = ref_to_me; /* prev */
1079 92217 : flags &= ~(int)ACCT_INFO_FLAG_LAST_REF_WAS_WRITE( lane ); /* clear bit */
1080 1443873 : } else {
1081 : /* Case 4: r-r. Add myself as a sibling instead of a child */
1082 1443873 : *me = *pa;
1083 1443873 : FOLLOW_EDGE( disp->pool, pa[1], _ignore )[2] = ref_to_me; /* prev->next->prev = me */
1084 1443873 : me[1] = pa[1]; /* me->next = prev->next */
1085 1443873 : me[2] = ref_to_pa; /* me->prev = prev */
1086 1443873 : pa[1] = ref_to_me; /* prev->next = me */
1087 1443873 : }
1088 1536090 : }
1089 :
1090 : /* Step 3: Update the final values */
1091 : /* In general, we want to increment the in_degree unless this
1092 : transaction is the first to reference this account. The
1093 : exception is that if this account has only readers, including
1094 : this transaction, we don't want to increment the in_degree
1095 : either. At this point, we can tell if that is the case based on
1096 : ANY_WRITERS. */
1097 2922129 : ele->in_degree += (uint)((ai->last_reference[ lane ]!=0U) & !!(flags & ACCT_INFO_FLAG_ANY_WRITERS( lane )));
1098 2922129 : ai->last_reference[ lane ] = ref_to_me;
1099 2922129 : ai->flags = (uchar)flags;
1100 2922129 : edge_idx += fd_uint_if( writable, 1U, 3U );
1101 2922129 : acct_idx++;
1102 2922129 : }
1103 : /* Can't overflow by construction, except for the intentional overflow on the first time. */
1104 3315756 : ele->edge_cnt_etc += (uint)addr_cnt<<fd_int_if( writable, 0, 7 );
1105 3315756 : }
1106 :
1107 :
1108 : /* should be called with all writable accounts first */
1109 : static void
1110 : add_unstaged_edges( fd_rdisp_t * disp,
1111 : fd_rdisp_txn_t * ele,
1112 : fd_rdisp_unstaged_t * unstaged,
1113 : fd_acct_addr_t const * addr,
1114 : ulong addr_cnt,
1115 : int writable,
1116 3816 : int update_score ) {
1117 3816 : ulong base_idx = unstaged->writable_cnt+unstaged->readonly_cnt;
1118 3816 : FD_TEST( !writable || unstaged->readonly_cnt==0U );
1119 42402 : for( ulong i=0UL; i<addr_cnt; i++ ) {
1120 38586 : unstaged->keys[ base_idx+i ] = addr[i];
1121 38586 : if( FD_LIKELY( update_score ) ) {
1122 38586 : ulong idx = acct_map_idx_query( disp->acct_map, addr+i, ULONG_MAX, disp->acct_pool );
1123 38586 : if( FD_UNLIKELY( idx==ULONG_MAX ) ) idx = acct_map_idx_query( disp->free_acct_map, addr+i, ULONG_MAX, disp->acct_pool );
1124 : /* since these are unstaged, we don't bother moving accounts
1125 : around */
1126 38586 : float score_change = 1.0f;
1127 38586 : if( FD_LIKELY( idx!=ULONG_MAX ) ) score_change = 1.0f - update_ema( disp->acct_pool+idx, disp->global_insert_cnt );
1128 38586 : ele->score *= fd_float_if( writable & update_score, score_change, 1.0f );
1129 38586 : }
1130 38586 : }
1131 3816 : *(fd_ptr_if( writable, &(unstaged->writable_cnt), &(unstaged->readonly_cnt) ) ) += (uint)addr_cnt;
1132 3816 : }
1133 :
1134 : ulong
1135 : fd_rdisp_add_txn( fd_rdisp_t * disp,
1136 : FD_RDISP_BLOCK_TAG_T insert_block,
1137 : fd_txn_t const * txn,
1138 : uchar const * payload,
1139 : fd_acct_addr_t const * alts,
1140 553164 : int serializing ) {
1141 :
1142 553164 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &insert_block, NULL, disp->block_pool );
1143 553164 : if( FD_UNLIKELY( !block || !block->insert_ready ) ) return 0UL;
1144 553161 : if( FD_UNLIKELY( !pool_free( disp->pool ) ) ) return 0UL;
1145 :
1146 553161 : ulong idx = pool_idx_acquire( disp->pool );
1147 553161 : fd_rdisp_txn_t * rtxn = disp->pool + idx;
1148 553161 : if( FD_UNLIKELY( rtxn->in_degree!=IN_DEGREE_FREE ) ) FD_LOG_CRIT(( "pool[%lu].in_degree==%u but free", idx, rtxn->in_degree ));
1149 :
1150 553161 : fd_acct_addr_t const * imm_addrs = fd_txn_get_acct_addrs( txn, payload );
1151 :
1152 553161 : if( FD_UNLIKELY( !block->staged ) ) {
1153 636 : rtxn->in_degree = IN_DEGREE_UNSTAGED;
1154 636 : rtxn->score = 1.0f;
1155 :
1156 636 : fd_rdisp_unstaged_t * unstaged = disp->unstaged + idx;
1157 636 : unstaged->block = insert_block;
1158 636 : unstaged->writable_cnt = 0U;
1159 636 : unstaged->readonly_cnt = 0U;
1160 :
1161 636 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs,
1162 636 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_SIGNER ), 1, 1 );
1163 636 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs+fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER ),
1164 636 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_NONSIGNER_IMM ), 1, 1 );
1165 636 : if( FD_LIKELY( alts ) )
1166 636 : add_unstaged_edges( disp, rtxn, unstaged, alts,
1167 636 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_ALT ), 1, 1 );
1168 636 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs+fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_SIGNER ),
1169 636 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_SIGNER ), 0, 1 );
1170 636 : add_unstaged_edges( disp, rtxn, unstaged, imm_addrs+fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER | FD_TXN_ACCT_CAT_WRITABLE_NONSIGNER_IMM ),
1171 636 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_NONSIGNER_IMM ), 0, 1 );
1172 636 : if( FD_LIKELY( alts ) )
1173 636 : add_unstaged_edges( disp, rtxn, unstaged, alts +fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_ALT ),
1174 636 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_ALT ), 0, 1 );
1175 :
1176 636 : unstaged_txn_ll_ele_push_tail( block->ll, rtxn, disp->pool );
1177 552525 : } else {
1178 552525 : uint lane = block->staging_lane;
1179 :
1180 552525 : rtxn->in_degree = 0U;
1181 552525 : rtxn->score = 1.0f;
1182 : /* There's not a good way to initialize w_cnt_1 to -1, which is what
1183 : it should be at this point, but this is close. We must be sure
1184 : to add at least one writer (which we are assured of because we
1185 : know the transaction passed fd_txn_parse) to correct this value. */
1186 552525 : rtxn->edge_cnt_etc = ((block->linear_block_number<<16) | (lane<<14)) - 1U;
1187 :
1188 552525 : add_edges( disp, rtxn, imm_addrs,
1189 552525 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_SIGNER ), lane, 1, 1 );
1190 552525 : add_edges( disp, rtxn, imm_addrs+fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER ),
1191 552525 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_NONSIGNER_IMM ), lane, 1, 1 );
1192 552525 : if( FD_LIKELY( alts ) )
1193 552510 : add_edges( disp, rtxn, alts,
1194 552510 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_ALT ), lane, 1, 1 );
1195 552525 : add_edges( disp, rtxn, imm_addrs+fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_SIGNER ),
1196 552525 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_SIGNER ), lane, 0, 1 );
1197 552525 : add_edges( disp, rtxn, imm_addrs+fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER | FD_TXN_ACCT_CAT_WRITABLE_NONSIGNER_IMM ),
1198 552525 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_NONSIGNER_IMM ), lane, 0, 1 );
1199 552525 : if( FD_LIKELY( alts ) )
1200 552510 : add_edges( disp, rtxn, alts +fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE_ALT ),
1201 552510 : fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_READONLY_ALT ), lane, 0, 1 );
1202 552525 : }
1203 553161 : if( FD_UNLIKELY( rtxn->score>FD_RDISP_MAX_SCORE ) ) rtxn->score=FD_RDISP_MAX_SCORE;
1204 :
1205 553161 : if( FD_UNLIKELY( serializing | block->last_insert_was_serializing ) ) {
1206 6 : block->last_serializing = block->inserted_cnt;
1207 6 : }
1208 553161 : block->last_insert_was_serializing = (uint)!!serializing;
1209 553161 : rtxn->score += (float)block->last_serializing;
1210 :
1211 553161 : block->inserted_cnt++;
1212 553161 : disp->global_insert_cnt++;
1213 :
1214 553161 : if( FD_LIKELY( (block->staged) & (rtxn->in_degree==0U) ) ) {
1215 433488 : pending_prq_ele_t temp[1] = {{ .score = rtxn->score, .linear_block_number = block->linear_block_number, .txn_idx = (uint)idx }};
1216 433488 : pending_prq_insert( disp->lanes[ block->staging_lane ].pending, temp );
1217 433488 : }
1218 :
1219 553161 : return idx;
1220 553161 : }
1221 :
1222 : ulong
1223 : fd_rdisp_get_next_ready( fd_rdisp_t * disp,
1224 724386 : FD_RDISP_BLOCK_TAG_T schedule_block ) {
1225 724386 : fd_rdisp_blockinfo_t * block = block_map_ele_query( disp->blockmap, &schedule_block, NULL, disp->block_pool );
1226 724386 : if( FD_UNLIKELY( !block || !block->schedule_ready ) ) return 0UL;
1227 :
1228 724371 : ulong idx;
1229 724371 : if( FD_LIKELY( block->staged ) ) {
1230 723744 : ulong staging_lane = block->staging_lane;
1231 723744 : per_lane_info_t * l = disp->lanes + staging_lane;
1232 :
1233 723744 : if( FD_UNLIKELY( !pending_prq_cnt( l->pending ) ) ) return 0UL;
1234 552849 : if( FD_UNLIKELY( l->pending->linear_block_number != block->linear_block_number ) ) return 0UL;
1235 : /* e.g. when completed_cnt==0, we can accept any score below 1.0 */
1236 552843 : if( FD_UNLIKELY( l->pending->score>=(float)(block->completed_cnt+1U) ) ) return 0UL;
1237 552843 : idx = l->pending->txn_idx;
1238 552843 : pending_prq_remove_min( l->pending );
1239 552843 : disp->pool[ idx ].in_degree = IN_DEGREE_DISPATCHED;
1240 552843 : } else {
1241 627 : if( FD_UNLIKELY( block->dispatched_cnt!=block->completed_cnt ) ) return 0UL;
1242 324 : if( FD_UNLIKELY( unstaged_txn_ll_is_empty( block->ll, disp->pool ) ) ) return 0UL;
1243 318 : idx = unstaged_txn_ll_idx_peek_head( block->ll, disp->pool );
1244 318 : disp->pool[ idx ].in_degree = IN_DEGREE_UNSTAGED_DISPATCHED;
1245 318 : }
1246 553161 : block->dispatched_cnt++;
1247 :
1248 553161 : return idx;
1249 724371 : }
1250 :
1251 : void
1252 : fd_rdisp_complete_txn( fd_rdisp_t * disp,
1253 : ulong txn_idx,
1254 553173 : int reclaim ) {
1255 :
1256 553173 : fd_rdisp_txn_t * rtxn = disp->pool + txn_idx;
1257 553173 : fd_rdisp_blockinfo_t * block = NULL;
1258 :
1259 553173 : if( FD_UNLIKELY( rtxn->in_degree==IN_DEGREE_UNSTAGED_DISPATCHED ) ) {
1260 : /* Unstaged */
1261 318 : block = block_map_ele_query( disp->blockmap, &disp->unstaged[ txn_idx ].block, NULL, disp->block_pool );
1262 318 : FD_TEST( rtxn==unstaged_txn_ll_ele_peek_head( block->ll, disp->pool ) );
1263 318 : unstaged_txn_ll_ele_pop_head( block->ll, disp->pool );
1264 318 : block->completed_cnt++;
1265 552855 : } else if( FD_LIKELY( rtxn->in_degree==IN_DEGREE_DISPATCHED ) ) {
1266 : /* Staged */
1267 552843 : ulong w_cnt_1 = (rtxn->edge_cnt_etc ) & 0x7FU;
1268 552843 : ulong r_cnt = (rtxn->edge_cnt_etc>> 7) & 0x7FU;
1269 552843 : ulong lane = (rtxn->edge_cnt_etc>>14) & 0x3U;
1270 552843 : uint tail_linear_block_num = (uint)(disp->lanes[lane].linear_block_number);
1271 552843 : ulong edge_idx = 0UL;
1272 3474972 : for( ulong i=0UL; i<=w_cnt_1+r_cnt; i++ ) {
1273 2922129 : edge_t const * e = rtxn->edges+edge_idx;
1274 2922129 : edge_t const e0 = *e;
1275 2922129 : edge_t ref_to_me = (uint)((txn_idx<<8) | i);
1276 :
1277 : /* To help with explanations, consider the following DAG:
1278 :
1279 : --> B --\ --> E --\
1280 : / V / V
1281 : A D (G)
1282 : \ ^ \ ^
1283 : --> C --/ --> F --/ */
1284 :
1285 2922129 : if( FD_UNLIKELY( EDGE_IS_LAST( e0 ) ) ) {
1286 2378718 : ulong acct_idx = e0 & 0x7FFFFFFFU;
1287 2378718 : acct_info_t * ai = disp->acct_pool + acct_idx;
1288 : /* If this is a writer, e.g. node G above, we know it's the last
1289 : one, so we can clear last_reference.
1290 : If this is a reader, e.g. node E and F above, if node G
1291 : didn't exist, we need to check if it's the last one
1292 : (me==me->next). If so, we can clear last_reference. If not,
1293 : we need to delete this node from the linked list */
1294 2378718 : if( edge_idx<=w_cnt_1 || e[1]==ref_to_me ) {
1295 1543848 : ai->last_reference[ lane ] = 0U;
1296 1543848 : ai->flags = (uchar)(ai->flags & (~(ACCT_INFO_FLAG_ANY_WRITERS( lane ) | ACCT_INFO_FLAG_LAST_REF_WAS_WRITE( lane ))));
1297 1543848 : } else {
1298 834870 : int _ignore;
1299 834870 : FOLLOW_EDGE( disp->pool, e[1], _ignore )[2] = e[2]; /* me->next->prev = me->prev */
1300 834870 : FOLLOW_EDGE( disp->pool, e[2], _ignore )[1] = e[1]; /* me->prev->next = me->next */
1301 834870 : ai->last_reference[ lane ]= fd_uint_if( ai->last_reference[ lane ]==ref_to_me, e[1], ai->last_reference[ lane ] );
1302 834870 : }
1303 :
1304 : /* Potentially transition from ACTIVE -> CACHED */
1305 2378718 : if( FD_UNLIKELY( (ai->last_reference[ 0 ]==0U)&(ai->last_reference[ 1 ]==0U)&
1306 2378718 : (ai->last_reference[ 2 ]==0U)&(ai->last_reference[ 3 ]==0U) ) ) {
1307 1086957 : ai->flags = 0;
1308 1086957 : acct_map_idx_remove_fast( disp->acct_map, acct_idx, disp->acct_pool );
1309 1086957 : acct_map_idx_insert ( disp->free_acct_map, acct_idx, disp->acct_pool );
1310 1086957 : free_dlist_idx_push_tail( disp->free_acct_dlist, acct_idx, disp->acct_pool );
1311 1086957 : }
1312 2378718 : } else {
1313 543411 : int child_is_writer;
1314 :
1315 543411 : edge_t next_e = e0;
1316 543411 : edge_t const * child_edge;
1317 587814 : while( 1 ) {
1318 : /* This loop first traverses the me->child link, and then
1319 : traverses any sibling links. For example, in the case that
1320 : we're completing node D above, the first child_txn is E,
1321 : and the second child_txn is F. */
1322 587814 : /* */ child_edge = FOLLOW_EDGE( disp->pool, next_e, child_is_writer );
1323 587814 : fd_rdisp_txn_t * child_txn = FOLLOW_EDGE_TXN( disp->pool, next_e );
1324 :
1325 : /* Sanity test */
1326 587814 : FD_TEST( child_txn->in_degree>0U );
1327 587814 : FD_TEST( child_txn->in_degree<IN_DEGREE_DISPATCHED );
1328 :
1329 587814 : if( FD_UNLIKELY( 0U==(--(child_txn->in_degree)) ) ) {
1330 : /* We need an operation something like
1331 : fd_frag_meta_ts_decomp. child_txn has the low 16 bits,
1332 : and tail_linear_block_num has the full 32 bits, except
1333 : for tail_linear_block_num refers to a block < block_depth
1334 : later. Since block_depth<2^16, that means we can resolve
1335 : this unambiguously. Basically, we copy the high 16 bits
1336 : frorm tail_linear_block_num unless that would make
1337 : linear_block_num larger than tail_linear_block_num, in
1338 : which case, we subtract 2^16. */
1339 119349 : uint low_16_bits = child_txn->edge_cnt_etc>>16;
1340 119349 : uint linear_block_num = ((tail_linear_block_num & ~0xFFFFU) | low_16_bits) - (uint)((low_16_bits>(tail_linear_block_num&0xFFFFU))<<16);
1341 119349 : pending_prq_ele_t temp[1] = {{ .score = child_txn->score,
1342 119349 : .linear_block_number = linear_block_num,
1343 119349 : .txn_idx = (uint)(child_txn-disp->pool) }};
1344 119349 : pending_prq_insert( disp->lanes[ lane ].pending, temp );
1345 119349 : }
1346 587814 : if( child_is_writer || child_edge[1]==e0 ) break;
1347 44403 : next_e = child_edge[1];
1348 44403 : }
1349 : /* In the case that the completed transaction is a reader, say B
1350 : or C above, it seems like we should need to remove it from
1351 : the doubly linked list, but we actually don't. The times
1352 : that we need to read the sibling pointers are:
1353 : 1. Completing the writer before a reader (e.g. completing A)
1354 : 2. Completing a reader that's the last in the DAG (e.g.
1355 : completing E/F if G didn't exist)
1356 : 3. Adding another reader to the same set of readers (e.g. if
1357 : G were added as a reader instead of a writer)
1358 : 4. Adding a writer after a set of readers (e.g. adding G).
1359 :
1360 : Supposing that the completed transaction is a reader, since
1361 : we checked EDGE_IS_LAST( e0 ), we know that there is at least
1362 : one writer that follows this reader, e.g. D above.
1363 :
1364 : And so none of these reason can apply to this group of readers:
1365 : 1. Completing B or C implies that A has already completed,
1366 : so it can't complete again.
1367 : 2. We know that we're not in that case because we checked
1368 : EDGE_IS_LAST( e0 ), and if we're not last now, we cannot
1369 : become last later, because the growth happens in the
1370 : other direction.
1371 : 3. Similarly, because we checked EDGE_IS_LAST, any future
1372 : additions of readers won't be to this group of readers.
1373 : 4. Similarly, we know that there already is a writer that
1374 : follows this group of readers, so a later writer would
1375 : not read this set of readers.
1376 :
1377 : So then, we don't need to deal with the sibling edges. The
1378 : fact that we only need to do it in one case almost calls into
1379 : question whether we need to maintain the whole circular
1380 : system in the first place, and whether we could get away with
1381 : a reference count or something instead, but it's important in
1382 : one critical case: suppose we add a bunch of readers, then
1383 : some of them complete, and then we add a writer (case 4
1384 : above). We need to be able to enumerate the nodes in the DAG
1385 : that have not yet completed, and we need to be able to remove
1386 : them from that set in O(1). Those two requirements don't
1387 : leave us with many alternatives besides a doubly linked list. */
1388 :
1389 543411 : if( FD_UNLIKELY( EDGE_IS_LAST( *child_edge ) ) ) {
1390 : /* For example, either:
1391 : 1. completing D when if G didn't exist
1392 : 2. completing E or F with G in the DAG
1393 :
1394 : After completing this transaction, there's either 0 writers
1395 : left (case 1) or 1 writer left (case 2) in the DAG. and if
1396 : there is one, it is the last reference.
1397 :
1398 : Either way, we want to set ANY_WRITERS to
1399 : LAST_REF_WAS_WRITE. */
1400 399549 : acct_info_t * ai = disp->acct_pool + (*child_edge & 0x7FFFFFFFU);
1401 399549 : ulong flags = ai->flags;
1402 399549 : flags &= ~(ulong)ACCT_INFO_FLAG_ANY_WRITERS( lane );
1403 399549 : flags |= (flags & (ulong)ACCT_INFO_FLAG_LAST_REF_WAS_WRITE( lane ))<<1;
1404 399549 : ai->flags = (uchar)flags;
1405 399549 : }
1406 543411 : }
1407 2922129 : edge_idx += fd_ulong_if( i<=w_cnt_1, 1UL, 3UL );
1408 2922129 : }
1409 552843 : block = block_slist_ele_peek_head( disp->lanes[ lane ].block_ll, disp->block_pool );
1410 552843 : block->completed_cnt++;
1411 552843 : } else if( FD_LIKELY( rtxn->in_degree==IN_DEGREE_ZOMBIE ) ) {
1412 12 : FD_TEST( reclaim );
1413 12 : block = block_pool_ele( disp->block_pool, rtxn->block_idx );
1414 12 : zombie_dlist_ele_remove( block->zombie_list, rtxn, disp->pool );
1415 : /* Fall through to the pool release branch below. */
1416 12 : } else {
1417 0 : FD_LOG_CRIT(( "completed un-dispatched transaction %lu", txn_idx ));
1418 0 : }
1419 553173 : if( reclaim ) {
1420 : /* For testing purposes, to make sure we don't read a completed
1421 : transaction, we can clobber the memory. */
1422 : /* memset( disp->pool+txn_idx, '\xCC', sizeof(fd_rdisp_txn_t) ); */
1423 553158 : rtxn->in_degree = IN_DEGREE_FREE;
1424 553158 : pool_idx_release( disp->pool, txn_idx );
1425 553158 : } else {
1426 15 : rtxn->in_degree = IN_DEGREE_ZOMBIE;
1427 15 : zombie_dlist_ele_push_tail( block->zombie_list, rtxn, disp->pool );
1428 15 : rtxn->block_idx = (uint)block_pool_idx( disp->block_pool, block );
1429 15 : }
1430 553173 : }
1431 :
1432 :
1433 : ulong
1434 : fd_rdisp_staging_lane_info( fd_rdisp_t const * disp,
1435 45 : fd_rdisp_staging_lane_info_t out_sched[ static 4 ] ) {
1436 225 : for( ulong i=0UL; i<4UL; i++ ) {
1437 180 : if( !(disp->free_lanes & (1<<i) ) ) {
1438 66 : block_slist_t const * sl = disp->lanes[ i ].block_ll;
1439 66 : out_sched[ i ].insert_ready_block = block_slist_ele_peek_tail( sl, disp->block_pool )->block;
1440 66 : out_sched[ i ].schedule_ready_block = block_slist_ele_peek_head( sl, disp->block_pool )->block;
1441 66 : }
1442 180 : }
1443 45 : return 0xFUL & ~(ulong)disp->free_lanes;
1444 45 : }
1445 :
1446 : void
1447 : fd_rdisp_verify( fd_rdisp_t const * disp,
1448 155352 : uint * scratch ) {
1449 155352 : ulong acct_depth = disp->depth*MAX_ACCT_PER_TXN;
1450 155352 : ulong block_depth = disp->block_depth;
1451 155352 : FD_TEST( 0==acct_map_verify ( disp->acct_map, acct_depth+1UL, disp->acct_pool ) );
1452 155352 : FD_TEST( 0==acct_map_verify ( disp->free_acct_map, acct_depth+1UL, disp->acct_pool ) );
1453 155352 : FD_TEST( 0==block_map_verify( disp->blockmap, block_depth+1UL, disp->block_pool ) );
1454 :
1455 : /* Check all the in degree counts are right */
1456 155352 : memset( scratch, '\0', sizeof(uint)*(disp->depth+1UL) );
1457 155352 : scratch[ 0 ] = UINT_MAX;
1458 46753152 : for( ulong j=1UL; j<disp->depth+1UL; j++ ) {
1459 46597800 : fd_rdisp_txn_t const * rtxn = disp->pool+j;
1460 46597800 : if( rtxn->in_degree==IN_DEGREE_FREE ) { scratch[ j ]=UINT_MAX; continue; }
1461 :
1462 11532285 : if( (rtxn->in_degree==IN_DEGREE_UNSTAGED_DISPATCHED) |
1463 11532285 : (rtxn->in_degree==IN_DEGREE_UNSTAGED) |
1464 11532285 : (rtxn->in_degree==IN_DEGREE_ZOMBIE) ) continue;
1465 :
1466 11531658 : ulong w_cnt_1 = (rtxn->edge_cnt_etc ) & 0x7FU;
1467 11531658 : ulong r_cnt = (rtxn->edge_cnt_etc>> 7) & 0x7FU;
1468 11531658 : ulong edge_idx = 0UL;
1469 :
1470 157731339 : for( ulong i=0UL; i<=w_cnt_1+r_cnt; i++ ) {
1471 146199681 : edge_t const * e = rtxn->edges+edge_idx;
1472 146199681 : edge_t const e0 = *e;
1473 :
1474 146199681 : edge_idx += fd_ulong_if( i<=w_cnt_1, 1UL, 3UL );
1475 :
1476 146199681 : if( FD_UNLIKELY( EDGE_IS_LAST( e0 ) ) ) continue;
1477 :
1478 29429448 : edge_t next_e = e0;
1479 29429448 : edge_t const * child_edge;
1480 29429448 : edge_t last_e = 0U;
1481 30671499 : while( 1 ) {
1482 30671499 : int child_is_writer;
1483 : /* This loop first traverses the me->child link, and then
1484 : traverses any sibling links. For example, in the case that
1485 : we're completing node D above, the first child_txn is E,
1486 : and the second child_txn is F. */
1487 30671499 : /* */ child_edge = FOLLOW_EDGE( disp->pool, next_e, child_is_writer );
1488 30671499 : fd_rdisp_txn_t * child_txn = FOLLOW_EDGE_TXN( disp->pool, next_e );
1489 30671499 : scratch[ child_txn - disp->pool ]++;
1490 30671499 : if( child_is_writer || child_edge[1]==e0 ) break;
1491 1242051 : if( last_e!=0U ) FD_TEST( child_edge[2]==last_e );
1492 1242051 : last_e = next_e;
1493 1242051 : next_e = child_edge[1];
1494 1242051 : FD_TEST( next_e>=0x100U );
1495 1242051 : }
1496 29429448 : }
1497 11531658 : }
1498 46753152 : for( ulong i=1UL; i<disp->depth+1UL; i++ ) {
1499 46597800 : FD_TEST( scratch[ i ]==UINT_MAX ||
1500 46597800 : disp->pool[ i ].in_degree==IN_DEGREE_DISPATCHED ||
1501 46597800 : disp->pool[ i ].in_degree==IN_DEGREE_UNSTAGED ||
1502 46597800 : disp->pool[ i ].in_degree==IN_DEGREE_UNSTAGED_DISPATCHED ||
1503 46597800 : disp->pool[ i ].in_degree==IN_DEGREE_ZOMBIE ||
1504 46597800 : disp->pool[ i ].in_degree==scratch[ i ] );
1505 46597800 : }
1506 155352 : }
1507 :
1508 9 : void * fd_rdisp_leave ( fd_rdisp_t * disp ) { return disp; }
1509 9 : void * fd_rdisp_delete( void * mem ) { return mem; }
|
