Line data Source code
1 : #define FD_UNALIGNED_ACCESS_STYLE 0
2 : #include "fd_pack.h"
3 :
4 : #define SORT_NAME fd_pack_writer_cost_sort
5 711 : #define SORT_KEY_T fd_pack_addr_use_t
6 447 : #define SORT_BEFORE(a,b) (FD_PACK_TOP_WRITERS_SORT_BEFORE(a,b))
7 : #define SORT_FN_ATTR __attribute__((no_sanitize("address", "undefined"))) /* excessive ASan slowdown */
8 : #include "../../util/tmpl/fd_sort.c"
9 :
10 : #include "fd_pack_cost.h"
11 : #include "fd_pack_bitset.h"
12 : #include "fd_pack_unwritable.h"
13 : #include "fd_chkdup.h"
14 : #include "fd_pack_tip_prog_blacklist.h"
15 : #include <math.h> /* for sqrt */
16 : #include <stddef.h> /* for offsetof */
17 : #include "../metrics/fd_metrics.h"
18 : #include "../../util/fd_hash32.h"
19 :
20 : #define FD_PACK_USE_NON_TEMPORAL_MEMCPY 1
21 :
22 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
23 : #include "../../util/simd/fd_nt_memcpy.h"
24 4504 : #define pack_memcpy_out fd_memcpy_nt_nofence
25 5080 : #define pack_memcpy_fini() _mm_sfence()
26 : #else
27 9008 : #define pack_memcpy_out fd_memcpy
28 : #define pack_memcpy_fini()
29 : #endif
30 :
31 : /* Declare a bunch of helper structs used for pack-internal data
32 : structures. */
33 : typedef struct {
34 : fd_acct_addr_t key;
35 : } wrapped_acct_t;
36 :
37 : /* fd_pack_ord_txn_t: An fd_txn_p_t with information required to order
38 : it by priority. */
39 : struct fd_pack_private_ord_txn {
40 : /* It's important that there be no padding here (asserted below)
41 : because the code casts back and forth from pointers to this element
42 : to pointers to the whole struct. */
43 : union {
44 : fd_txn_p_t txn[1]; /* txn is an alias for txn_e->txnp */
45 : fd_txn_e_t txn_e[1];
46 : fd_txn_e_t _txn_e; /* Non-array type needed for map_chain */
47 : };
48 :
49 : /* Since this struct can be in one of several trees, it's helpful to
50 : store which tree. This should be one of the FD_ORD_TXN_ROOT_*
51 : values. */
52 : int root;
53 :
54 : /* The sig2txn map_chain fields */
55 : ushort sigmap_next;
56 : ushort sigmap_prev;
57 :
58 : /* Each transaction is inserted with an expiration "time." This code
59 : doesn't care about the units (blocks, rdtsc tick, ns, etc.), and
60 : doesn't require transactions to be inserted in expiration date
61 : order. */
62 : ulong expires_at;
63 : /* expq_idx: When this object is part of one of the treaps, it's
64 : also in the expiration priority queue. This field (which is
65 : manipulated behind the scenes by the fd_prq code) stores where so
66 : that if we delete this transaction, we can also delete it from the
67 : expiration priority queue. */
68 : ulong expq_idx;
69 :
70 : /* The noncemap map_chain fields */
71 : ushort noncemap_next;
72 : ushort noncemap_prev;
73 : /* For nonce transactions, we store the provided expires_at value here
74 : for use by the noncemap comparison functionality. The actual
75 : expires_at value for nonce transactions is rewritten */
76 : ulong nonce_expires_at;
77 :
78 : /* We want rewards*compute_est to fit in a ulong so that r1/c1 < r2/c2 can be
79 : computed as r1*c2 < r2*c1, with the product fitting in a ulong.
80 : compute_est has a small natural limit of mid-20 bits. rewards doesn't have
81 : a natural limit, so there is some argument to be made for raising the
82 : limit for rewards to 40ish bits. The struct has better packing with
83 : uint/uint though. */
84 : uint __attribute__((aligned(64))) /* We want the treap fields and the bitsets
85 : to be on the same double cache line pair */
86 : rewards; /* in Lamports */
87 : uint compute_est; /* in compute units */
88 :
89 : /* The treap fields */
90 : ushort left;
91 : ushort right;
92 : ushort parent;
93 : ushort prio;
94 : ushort prev;
95 : ushort next;
96 :
97 : /* skip: if we skip this transaction more than FD_PACK_SKIP_CNT times
98 : for reasons that won't go away until the end of the block, then we
99 : want to skip it very quickly. If skip is in [1, FD_PACK_SKIP_CNT],
100 : then that means we have to skip it `skip` more times before taking
101 : any action. If skip>FD_PACK_SKIP_CNT, then it is a compressed slot
102 : number during which it should be skipped, and we'll skip it until
103 : the compressed slot reaches a new value. skip is never 0. */
104 : ushort skip;
105 :
106 : FD_PACK_BITSET_DECLARE( rw_bitset ); /* all accts this txn references */
107 : FD_PACK_BITSET_DECLARE( w_bitset ); /* accts this txn write-locks */
108 :
109 : };
110 : typedef struct fd_pack_private_ord_txn fd_pack_ord_txn_t;
111 :
112 : /* We require that the payload starts at byte 0 of fd_pack_ord_txn_t,
113 : because we cast back and forth between fd_txn_p_t* and
114 : fd_pack_ord_txn_t*.
115 : GCC and Clang seem to disagree on the rules of offsetof. */
116 : FD_STATIC_ASSERT( offsetof( fd_pack_ord_txn_t, txn )==0UL, fd_pack_ord_txn_t );
117 : #if FD_USING_CLANG
118 : FD_STATIC_ASSERT( offsetof( fd_txn_p_t, payload )==0UL, fd_pack_ord_txn_t );
119 : #else
120 : FD_STATIC_ASSERT( offsetof( fd_pack_ord_txn_t, txn->payload )==0UL, fd_pack_ord_txn_t );
121 : FD_STATIC_ASSERT( offsetof( fd_pack_ord_txn_t, txn_e->txnp )==0UL, fd_pack_ord_txn_t );
122 : #endif
123 :
124 : /* FD_ORD_TXN_ROOT is essentially a small union packed into an int. The low
125 : byte is the "tag". The higher 3 bytes depend on the low byte. */
126 1911642 : #define FD_ORD_TXN_ROOT_TAG_MASK 0xFF
127 3061317 : #define FD_ORD_TXN_ROOT_FREE 0
128 35302 : #define FD_ORD_TXN_ROOT_PENDING 1
129 3766698 : #define FD_ORD_TXN_ROOT_PENDING_BUNDLE 2
130 30067 : #define FD_ORD_TXN_ROOT_PENALTY( idx ) (3 | (idx)<<8)
131 1249 : #define FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( idx ) (4 | (idx)<<8)
132 672 : #define FD_ORD_TXN_ROOT_NEXT_AUCTION 5
133 :
134 : /* if root & TAG_MASK == PENALTY, then PENALTY_ACCT_IDX(root) gives the index
135 : in the transaction's list of account addresses of which penalty treap the
136 : transaction is in. */
137 : #define FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( root ) (((root) & 0xFF00)>>8)
138 : /* if root & TAG_MASK == PRE_ROTATION_BUNDLE, then
139 : PRE_ROTATION_BUNDLE_IDX(root) gives the index in
140 : pre_rotation_bundles of the bundle the transaction is in. */
141 379 : #define FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE_IDX( root ) (((root) & 0xFF00)>>8)
142 :
143 163182 : #define FD_PACK_IN_USE_WRITABLE (0x8000000000000000UL)
144 137908 : #define FD_PACK_IN_USE_BIT_CLEARED (0x4000000000000000UL)
145 :
146 : /* Each non-empty microblock we schedule also has an overhead of 48
147 : bytes that counts towards shed limits. That comes from the 32 byte
148 : hash, the hash count (8 bytes) and the transaction count (8 bytes).
149 : We don't have to pay this overhead if the microblock is empty, since
150 : those microblocks get dropped. */
151 31344 : #define MICROBLOCK_DATA_OVERHEAD 48UL
152 :
153 : FD_STATIC_ASSERT( sizeof(fd_acct_addr_t)==sizeof(fd_pubkey_t), "" );
154 :
155 : /* fd_pack_expq_t: An element of an fd_prq to sort the transactions by
156 : timeout. This structure has several invariants for entries
157 : corresponding to pending transactions:
158 : expires_at == txn->expires_at
159 : txn->exp_prq_idx is the index of this structure
160 : Notice that prq is an array-based heap, which means the indexes of
161 : elements change. The PRQ_TMP_ST macro is hijacked to keep that
162 : invariant up to date.
163 :
164 : Note: this could be easier if fd_heap supported deleting from the
165 : middle, but that's not possible with the current design of fd_heap,
166 : which omits a parent pointer for improved performance. */
167 : struct fd_pack_expq {
168 : ulong expires_at;
169 : fd_pack_ord_txn_t * txn;
170 : };
171 : typedef struct fd_pack_expq fd_pack_expq_t;
172 :
173 :
174 : /* fd_pack_bitset_acct_mapping_t: An element of an fd_map_dynamic that
175 : maps an account address to the number of transactions that are
176 : referencing it and the bit that is reserved to indicate it in the
177 : bitset, if any. */
178 : struct fd_pack_bitset_acct_mapping {
179 : fd_acct_addr_t key; /* account address */
180 : ulong ref_cnt;
181 :
182 : /* first_instance and first_instance_was_write are only valid when
183 : bit==FD_PACK_BITSET_FIRST_INSTANCE, which is set when ref_cnt
184 : transitions from 0 to 1. These just exist to implement the
185 : optimization that accounts referenced a single time aren't
186 : allocated a bit, but this seems to be an important optimization. */
187 : fd_pack_ord_txn_t * first_instance;
188 : int first_instance_was_write;
189 :
190 : /* bit is in [0, FD_PACK_BITSET_MAX) U
191 : { FD_PACK_BITSET_FIRST_INSTANCE, FD_PACK_BITSET_SLOWPATH }. */
192 : ushort bit;
193 : };
194 : typedef struct fd_pack_bitset_acct_mapping fd_pack_bitset_acct_mapping_t;
195 :
196 :
197 : struct fd_pack_wcost_ele {
198 : fd_acct_addr_t key; /* account address */
199 : ulong total_cost;
200 : union {
201 : uint map_next;
202 : uint pool_next;
203 : };
204 : uint map_prev;
205 : uint dlist_next;
206 : uint dlist_prev;
207 : };
208 : typedef struct fd_pack_wcost_ele fd_pack_wcost_ele_t;
209 :
210 :
211 : /* pack maintains a small state machine related to initializer bundles.
212 : See the header file for more details about it, but it's
213 : also summarized here:
214 : * NOT_INITIALIZED: The starting state for each block
215 : * PENDING: an initializer bundle has been scheduled, but pack has
216 : not observed its result yet, so we don't know if it was successful
217 : or not.
218 : * FAILED: the most recently scheduled initializer bundle failed
219 : for reasons other than already being executed. Most commonly, this
220 : could be because of a bug in the code that generated the
221 : initializer bundle, a lack of fee payer balance, or an expired
222 : blockhash.
223 : * READY: the most recently scheduled initialization bundle succeeded
224 : and normal bundles can be scheduled in this slot. */
225 594 : #define FD_PACK_IB_STATE_NOT_INITIALIZED 0
226 6 : #define FD_PACK_IB_STATE_PENDING 1
227 3 : #define FD_PACK_IB_STATE_FAILED 2
228 165 : #define FD_PACK_IB_STATE_READY 3
229 :
230 :
231 : /* Returns 1 if x.rewards/x.compute < y.rewards/y.compute. Not robust. */
232 7638032 : #define COMPARE_WORSE(x,y) ( ((ulong)((x)->rewards)*(ulong)((y)->compute_est)) < ((ulong)((y)->rewards)*(ulong)((x)->compute_est)) )
233 :
234 : /* Declare all the data structures */
235 :
236 :
237 : /* Define the big max-"heap" that we pull transactions off to schedule.
238 : The priority is given by reward/compute. We may want to add in some
239 : additional terms at a later point. In order to cheaply remove nodes,
240 : we actually use a treap. */
241 : #define POOL_NAME trp_pool
242 1728 : #define POOL_T fd_pack_ord_txn_t
243 : #define POOL_IDX_T ushort
244 4451862 : #define POOL_NEXT parent
245 : #include "../../util/tmpl/fd_pool.c"
246 :
247 : #define TREAP_T fd_pack_ord_txn_t
248 : #define TREAP_NAME treap
249 : #define TREAP_QUERY_T void * /* We don't use query ... */
250 : #define TREAP_CMP(a,b) (__extension__({ (void)(a); (void)(b); -1; })) /* which means we don't need to give a real
251 : implementation to cmp either */
252 28666338 : #define TREAP_IDX_T ushort
253 : #define TREAP_OPTIMIZE_ITERATION 1
254 7638032 : #define TREAP_LT COMPARE_WORSE
255 : #include "../../util/tmpl/fd_treap.c"
256 :
257 :
258 : #define MAP_NAME sig2txn
259 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
260 : #define MAP_MULTI 1
261 3795417 : #define MAP_ELE_T fd_pack_ord_txn_t
262 5695097 : #define MAP_PREV sigmap_prev
263 8865361 : #define MAP_NEXT sigmap_next
264 5689466 : #define MAP_IDX_T ushort
265 :
266 : #define MAP_KEY_T fd_txn_e_t
267 3828292 : #define MAP_KEY _txn_e
268 13262092 : #define TXNE_TO_SIG(ptr) (__extension__({ fd_txn_p_t const * __p = (ptr)->txnp; __p->payload + TXN(__p)->signature_off; }))
269 3773148 : #define MAP_KEY_EQ(k0,k1) (!memcmp( TXNE_TO_SIG(k0), TXNE_TO_SIG(k1), FD_TXN_SIGNATURE_SZ) )
270 5715796 : #define MAP_KEY_HASH(key,seed) fd_hash( (seed), TXNE_TO_SIG(key), 64UL )
271 : #include "../../util/tmpl/fd_map_chain.c"
272 :
273 :
274 : /* noncemap: A map from (nonce account, nonce authority) to a durable
275 : nonce transaction containing it. We only want to allow one
276 : transaction in the pool at a time with a given (nonce account, nonce
277 : authority) tuple value, keeping the one with the blockhash value
278 : derived from the newest blockhash, breaking ties by value. The
279 : question is: can adding this limitation cause us to throw out
280 : potentially valuable transaction? The answer is yes, but only very
281 : rarely, and the savings are worth it. Suppose we have durable nonce
282 : transactions t1 and t2 that advance the same nonce account.
283 :
284 : If t1 and t2 have the same recent blockhash value:
285 : - If t1 lands on chain, then it will advance the nonce account, and
286 : t2 certainly cannot land on chain.
287 : - If t1 fails with AlreadyExecuted, that means the nonce account was
288 : advanced when t1 landed in a previous block, so t2 will certainly not
289 : land on chain either.
290 : - If t1 fails with BlockhashNotFound, then the nonce account was
291 : advanced in some previous transaction, so again, t2 will certainly
292 : not land on chain.
293 : - If t1 does not land on chain because of an issue with the fee
294 : payer, it's possible that t2 could land on chain if it used a
295 : different fee payer, but historical data shows this is unlikely.
296 : - If t1 does not land on chain because it is part of a bundle that
297 : fails for an unrelated reason, it's possible that t2 could land on
298 : chain, but again, historical data says this is rare.
299 :
300 : Otherwise, suppose t1's recent blockhash value is the value based on
301 : slot s1's blockhash (which is written to nonce accounts when
302 : executing in slot s1+1) and similarly for s2, and that s1<s2.
303 : Then we'll throw out t1 and only try to pack t2.
304 :
305 : The sender will only send t2 if they think the nonce account contains
306 : (or will contain) the value based on slot s2's blockhash, which means
307 : they think a transaction landed or will land in slot s2+1.
308 : If a transaction updating the nonce account did land in slot s2+1,
309 : then t1 can never land, so throwing it out is safe.
310 : It's possible, but seems unlikely, that the sender could be
311 : speculating and has only seen slot s2 but not s2+1 yet. In that
312 : case, if we are leader for both s2+1, we could pack t1 in s2+1 and t2
313 : in a later slot. Again, this is a case where we'll take the small
314 : hit in exchange for the simplification.
315 :
316 : We need to include the nonce authority in the hash to prevent one
317 : user from being able to DoS another user. */
318 :
319 : typedef struct {
320 : fd_acct_addr_t const * nonce_acct;
321 : fd_acct_addr_t const * nonce_auth;
322 : } noncemap_extract_t;
323 :
324 : /* k must be a valid, durable nonce transaction. No error checking is
325 : done. */
326 : static inline void
327 : noncemap_extract( fd_txn_e_t const * k,
328 3514 : noncemap_extract_t * out ) {
329 3514 : fd_txn_t const * txn = TXN(k->txnp);
330 :
331 3514 : ulong nonce_idx = k->txnp->payload[ txn->instr[ 0 ].acct_off+0 ];
332 3514 : ulong autho_idx = k->txnp->payload[ txn->instr[ 0 ].acct_off+2 ];
333 :
334 3514 : ulong imm_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
335 3514 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, k->txnp->payload );
336 3514 : out->nonce_acct = nonce_idx<imm_cnt ? accts+nonce_idx : k->alt_accts+(nonce_idx-imm_cnt);
337 : /* The nonce authority must be a signer, so it must be an immediate
338 : account. */
339 3514 : out->nonce_auth = accts+autho_idx;
340 3514 : }
341 :
342 : static inline int
343 : noncemap_key_eq_internal( fd_txn_e_t const * k0,
344 192 : fd_txn_e_t const * k1 ) {
345 192 : noncemap_extract_t e0[1], e1[1];
346 192 : noncemap_extract( k0, e0 );
347 192 : noncemap_extract( k1, e1 );
348 :
349 192 : if( FD_UNLIKELY( memcmp( e0->nonce_acct, e1->nonce_acct, 32UL ) ) ) return 0;
350 186 : if( FD_UNLIKELY( memcmp( e0->nonce_auth, e1->nonce_auth, 32UL ) ) ) return 0;
351 186 : return 1;
352 186 : }
353 :
354 : #if FD_HAS_INT128
355 :
356 : /* unrolled xxHash3 */
357 :
358 : static inline ulong
359 : noncemap_key_hash_internal( ulong seed,
360 3130 : fd_txn_e_t const * k ) {
361 3130 : noncemap_extract_t e[1];
362 3130 : noncemap_extract( k, e );
363 :
364 3130 : ulong k0 = FD_LOAD( ulong, e->nonce_acct->b + 0 );
365 3130 : ulong k1 = FD_LOAD( ulong, e->nonce_acct->b + 8 );
366 3130 : ulong k2 = FD_LOAD( ulong, e->nonce_acct->b +16 );
367 3130 : ulong k3 = FD_LOAD( ulong, e->nonce_acct->b +24 );
368 3130 : ulong k4 = FD_LOAD( ulong, e->nonce_auth->b + 0 );
369 3130 : ulong k5 = FD_LOAD( ulong, e->nonce_auth->b + 8 );
370 3130 : ulong k6 = FD_LOAD( ulong, e->nonce_auth->b +16 );
371 3130 : ulong k7 = FD_LOAD( ulong, e->nonce_auth->b +24 );
372 :
373 3130 : ulong acc = 96 * 0x9E3779B185EBCA87ULL;
374 3130 : acc += fd_xxh3_mix16b( k4, k5, 0xcb00c391bb52283cUL, 0xa32e531b8b65d088UL, seed );
375 3130 : acc += fd_xxh3_mix16b( k6, k7, 0x4ef90da297486471UL, 0xd8acdea946ef1938UL, seed );
376 3130 : acc += fd_xxh3_mix16b( k2, k3, 0x78e5c0cc4ee679cbUL, 0x2172ffcc7dd05a82UL, seed );
377 3130 : acc += fd_xxh3_mix16b( k0, k1, 0xbe4ba423396cfeb8UL, 0x1cad21f72c81017cUL, seed );
378 3130 : acc = acc ^ (acc >> 37);
379 3130 : acc *= 0x165667919E3779F9ULL;
380 3130 : acc = acc ^ (acc >> 32);
381 3130 : return acc;
382 3130 : }
383 :
384 : #else
385 :
386 : static inline ulong
387 : noncemap_key_hash_internal( ulong seed,
388 : fd_txn_e_t const * k ) {
389 : noncemap_extract_t e[1];
390 : noncemap_extract( k, e );
391 :
392 : uchar buf[ 64 ];
393 : memcpy( buf, e->nonce_acct->b, 32UL );
394 : memcpy( buf+32UL, e->nonce_auth->b, 32UL );
395 : return fd_hash( seed, buf, 64UL );
396 : }
397 :
398 : #endif
399 :
400 : #define MAP_NAME noncemap
401 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
402 : #define MAP_MULTI 0
403 384 : #define MAP_ELE_T fd_pack_ord_txn_t
404 415 : #define MAP_PREV noncemap_prev
405 979 : #define MAP_NEXT noncemap_next
406 4755 : #define MAP_IDX_T ushort
407 : #define MAP_KEY_T fd_txn_e_t
408 787 : #define MAP_KEY _txn_e
409 192 : #define MAP_KEY_EQ(k0,k1) noncemap_key_eq_internal( (k0), (k1) )
410 3130 : #define MAP_KEY_HASH(key,seed) noncemap_key_hash_internal( (seed), (key) )
411 : #include "../../util/tmpl/fd_map_chain.c"
412 :
413 :
414 : static const fd_acct_addr_t null_addr = { 0 };
415 :
416 : #define MAP_NAME acct_uses
417 2374962 : #define MAP_T fd_pack_addr_use_t
418 2486391 : #define MAP_KEY_T fd_acct_addr_t
419 12137327 : #define MAP_KEY_NULL null_addr
420 : #if FD_HAS_AVX
421 2486391 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
422 : #else
423 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
424 : #endif
425 2264099 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
426 : #define MAP_KEY_EQUAL_IS_SLOW 1
427 : #define MAP_MEMOIZE 0
428 8226542 : #define MAP_KEY_HASH(key,s) ((uint)fd_hash32( (key).b, (s) ))
429 : #include "../../util/tmpl/fd_map_dynamic.c"
430 :
431 : #define MAP_NAME wcost_map
432 4842 : #define MAP_ELE_T fd_pack_wcost_ele_t
433 : #define MAP_KEY_T fd_acct_addr_t
434 191137 : #define MAP_IDX_T uint
435 17232 : #define MAP_NEXT map_next
436 12242 : #define MAP_PREV map_prev
437 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
438 94992 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->b,(k1)->b, FD_TXN_ACCT_ADDR_SZ))
439 135922 : #define MAP_KEY_HASH(key,s) ((uint)fd_hash32( (key)->b, (s) ))
440 : #include "../../util/tmpl/fd_map_chain.c"
441 :
442 : #define POOL_NAME wcost_pool
443 1152 : #define POOL_T fd_pack_wcost_ele_t
444 : #define POOL_IDX_T uint
445 92176915 : #define POOL_NEXT pool_next
446 : #include "../../util/tmpl/fd_pool.c"
447 :
448 : #define DLIST_NAME wcost_dlist
449 : #define DLIST_ELE_T fd_pack_wcost_ele_t
450 : #define DLIST_IDX_T uint
451 16915 : #define DLIST_NEXT dlist_next
452 12076 : #define DLIST_PREV dlist_prev
453 : #include "../../util/tmpl/fd_dlist.c"
454 :
455 : #define MAP_NAME bitset_map
456 9863866 : #define MAP_T fd_pack_bitset_acct_mapping_t
457 11819331 : #define MAP_KEY_T fd_acct_addr_t
458 85646478 : #define MAP_KEY_NULL null_addr
459 : #if FD_HAS_AVX
460 83152707 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
461 : #else
462 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
463 : #endif
464 7897825 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
465 : #define MAP_KEY_EQUAL_IS_SLOW 1
466 : #define MAP_MEMOIZE 0
467 9861544 : #define MAP_KEY_HASH(key,s) ((uint)fd_hash32( (key).b, (s) ))
468 : #include "../../util/tmpl/fd_map_dynamic.c"
469 :
470 :
471 : #define MAP_NAME acct_blocklist
472 5862729 : #define MAP_T wrapped_acct_t
473 : /* Add 1 to the slot cnt to ensure the map is sparse even at capacity */
474 5881362 : #define MAP_LG_SLOT_CNT (FD_PACK_ACCT_BLOCKLIST_LG_MAX+1)
475 5862156 : #define MAP_KEY_T fd_acct_addr_t
476 18624 : #define MAP_KEY_NULL null_addr
477 : #if FD_HAS_AVX
478 11726085 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
479 : #else
480 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
481 : #endif
482 5862093 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
483 : /* It would be nice if this were seeded, but since fd_map doesn't have
484 : any auxiliary data, there's not a clear place to store the seed.
485 : It's okay though, because the insert process is trusted, since it
486 : comes from operator config. */
487 5862147 : #define MAP_KEY_HASH(key) ((uint)fd_ulong_hash( fd_ulong_load_8( (key).b ) ))
488 : #define MAP_KEY_EQUAL_IS_SLOW 1
489 : #define MAP_MEMOIZE 0
490 : #define MAX_QUERY_OPT 2 /* rare hits */
491 : #include "../../util/tmpl/fd_map.c"
492 :
493 : /* Since transactions can also expire, we also maintain a parallel
494 : priority queue. This means elements are simultaneously part of the
495 : treap (ordered by priority) and the expiration queue (ordered by
496 : expiration). It's tempting to use the priority field of the treap
497 : for this purpose, but that can result in degenerate treaps in some
498 : cases. */
499 : #define PRQ_NAME expq
500 3873159 : #define PRQ_T fd_pack_expq_t
501 3829056 : #define PRQ_TIMEOUT_T ulong
502 3829056 : #define PRQ_TIMEOUT expires_at
503 1934544 : #define PRQ_TMP_ST(p,t) do { \
504 1934544 : (p)[0] = (t); \
505 1934544 : t.txn->expq_idx = (ulong)((p)-heap); \
506 1934544 : } while( 0 )
507 : #include "../../util/tmpl/fd_prq.c"
508 :
509 : /* With realistic traffic patterns, we often see many, many transactions
510 : competing for the same writable account. Since only one of these can
511 : execute at a time, we sometimes waste lots of scheduling time going
512 : through them one at a time. To combat that, when a transaction
513 : writes to an account with more than PENALTY_TREAP_THRESHOLD
514 : references (readers or writers), instead of inserting it into the
515 : main treap, we insert it into a penalty treap for that specific hot
516 : account address. These transactions are not immediately available
517 : for scheduling. Then, when a transaction that writes to the hot
518 : address completes, we move the most lucrative transaction from the
519 : penalty treap to the main treap, making it available for scheduling.
520 : This policy may slightly violate the price-time priority scheduling
521 : approach pack normally uses: if the most lucrative transaction
522 : competing for hot state arrives after PENALTY_TREAP_THRESHOLD has
523 : been hit, it may be scheduled second instead of first. However, if
524 : the account is in use at the time the new transaction arrives, it
525 : will be scheduled next, as desired. This minor difference seems
526 : reasonable to reduce complexity.
527 :
528 : fd_pack_penalty_treap is one account-specific penalty treap. All the
529 : transactions in the penalty_treap treap write to key.
530 :
531 : penalty_map is the fd_map_dynamic that maps accounts to their
532 : respective penalty treaps. */
533 : struct fd_pack_penalty_treap {
534 : fd_acct_addr_t key;
535 : treap_t penalty_treap[1];
536 : };
537 : typedef struct fd_pack_penalty_treap fd_pack_penalty_treap_t;
538 :
539 : #define MAP_NAME penalty_map
540 73480 : #define MAP_T fd_pack_penalty_treap_t
541 72343 : #define MAP_KEY_T fd_acct_addr_t
542 1307661 : #define MAP_KEY_NULL null_addr
543 : #if FD_HAS_AVX
544 1186927 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
545 : #else
546 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
547 : #endif
548 72301 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
549 : #define MAP_KEY_EQUAL_IS_SLOW 1
550 : #define MAP_MEMOIZE 0
551 72322 : #define MAP_KEY_HASH(key,s) ((uint)fd_hash32( (key).b, (s) ))
552 : #include "../../util/tmpl/fd_map_dynamic.c"
553 :
554 : /* PENALTY_TREAP_THRESHOLD: How many references to an account do we
555 : allow before subsequent transactions that write to the account go to
556 : the penalty treap. */
557 3929241 : #define PENALTY_TREAP_THRESHOLD 64UL
558 :
559 :
560 : /* FD_PACK_SKIP_CNT: How many times we'll skip a transaction (for
561 : reasons other than account conflicts) before we won't consider it
562 : until the next slot. For performance reasons, this doesn't reset at
563 : the end of a slot, so e.g. we might skip twice in slot 1, then three
564 : times in slot 2, which would be enough to prevent considering it
565 : until slot 3. The main reason this is not 1 is that some skips that
566 : seem permanent until the end of the slot can actually go away based
567 : on rebates. */
568 1917831 : #define FD_PACK_SKIP_CNT 50UL
569 :
570 : /* FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY: the maximum number of the
571 : bundles that arrived before our leader rotation which we execute
572 : during our leader rotation. Any extra pre-rotation bundles are
573 : dropped, in order of their declared tip. */
574 13401 : #define FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY 16UL
575 :
576 : /* fd_pack_pre_rotation_bundle represents a single pre-rotation bundle:
577 : its transactions, in bundle order, in treap, the declared tip, and
578 : the sequence number representing the order of insertion. */
579 : struct fd_pack_pre_rotation_bundle {
580 : treap_t treap[1];
581 : ulong tip;
582 : ulong seq;
583 : };
584 : typedef struct fd_pack_pre_rotation_bundle fd_pack_pre_rotation_bundle_t;
585 :
586 : /* Finally, we can now declare the main pack data structure */
587 : struct fd_pack_private {
588 : ulong pack_depth;
589 : ulong bundle_meta_sz; /* if 0, bundles are disabled */
590 : ulong bank_tile_cnt;
591 :
592 : fd_pack_limits_t lim[1];
593 :
594 : ulong pending_txn_cnt; /* Summed across all treaps */
595 : ulong microblock_cnt; /* How many microblocks have we
596 : generated in this block? */
597 : ulong data_bytes_consumed; /* How much data is in this block so
598 : far ? */
599 : /* There's a limit on the total amount that transactions in a block
600 : can allocate. How much of that limit have we consumed? */
601 : ulong alloc_consumed;
602 :
603 : /* counters / gauge for schedule outcome enums */
604 : ulong sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_CNT ];
605 :
606 : fd_rng_t * rng;
607 :
608 : ulong cumulative_block_cost;
609 :
610 : /* expire_before: Any transactions with expires_at strictly less than
611 : the current expire_before are removed from the available pending
612 : transaction. Here, "expire" is used as a verb: cause all
613 : transactions before this time to expire. */
614 : ulong expire_before;
615 :
616 : /* outstanding_microblock_mask: a bitmask indicating which banking
617 : tiles have outstanding microblocks, i.e. fd_pack has generated a
618 : microblock for that banking tile and the banking tile has not yet
619 : notified fd_pack that it has completed it. */
620 : ulong outstanding_microblock_mask;
621 :
622 : /* The actual footprint for the pool and maps is allocated
623 : in the same order in which they are declared immediately following
624 : the struct. I.e. these pointers point to memory not far after the
625 : struct. The trees are just pointers into the pool so don't take up
626 : more space. */
627 :
628 : fd_pack_ord_txn_t * pool;
629 :
630 : /* Treaps (sorted by priority) of pending transactions. We store the
631 : transactions that come from bundles separately. */
632 : treap_t pending[1];
633 : treap_t pending_bundles[1];
634 :
635 : /* Bundles that arrived before our leader rotation has started are
636 : stored in pre_rotation_bundles, one bundle per treap.
637 : rotation_end_ns stores the timestamp, in ns, of the end of the
638 : last leader rotation, so that we can determine if a bundle arrived
639 : during the start of the leader rotation or not.
640 : pre_rotation_seq stores an incrementing sequence number, which we
641 : use to track the order in which the pre-rotation bundles arrived.
642 :
643 : We could use a more complex data structure to track the best and
644 : worse pre-rotation bundle, but since
645 : FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY is so small it's not worth
646 : the added complexity. */
647 : fd_pack_pre_rotation_bundle_t pre_rotation_bundles[ FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY ];
648 : ulong pre_rotation_bundle_cnt;
649 : ulong pre_rotation_seq;
650 : long rotation_end_ns;
651 :
652 : /* If an auction is running, new transactions are held in
653 : next_auction - they are not eligible to be scheduled. When the
654 : auction ends, these are flushed into either the pending or penalty
655 : treaps. */
656 : treap_t next_auction[1];
657 : int auction_running;
658 :
659 : /* penalty_treaps: an fd_map_dynamic mapping hotly contended account
660 : addresses to treaps of transactions that write to them. We try not
661 : to allow more than roughly PENALTY_TREAP_THRESHOLD transactions in
662 : the main treap that write to each account, though this is not
663 : exact. */
664 : fd_pack_penalty_treap_t * penalty_treaps;
665 :
666 : /* initializer_bundle_state: The current state of the initialization
667 : bundle state machine. One of the FD_PACK_IB_STATE_* values. See
668 : the long comment in the header and the comments attached to the
669 : respective values for a discussion of what each state means and the
670 : transitions between them. */
671 : int initializer_bundle_state;
672 :
673 : /* relative_bundle_idx: the number of bundles that have been inserted
674 : since the last time pending_bundles was empty. See the long
675 : comment about encoding this index in the rewards field of each
676 : transaction in the bundle, and why it is important that this reset
677 : to 0 as frequently as possible. */
678 : ulong relative_bundle_idx;
679 :
680 : /* pending_smallest: keep a conservative estimate of the
681 : smallest transaction (by cost units and by bytes) in the pending
682 : treap. Both CUs and bytes should be set to ULONG_MAX if the treap
683 : is empty. */
684 : fd_pack_smallest_t pending_smallest[1];
685 :
686 : /* expiration_q: At the same time that a transaction is in exactly one
687 : of the above treaps, it is also in the expiration queue, sorted by
688 : its expiration time. This enables deleting all transactions that
689 : have expired, regardless of which treap they are in. */
690 : fd_pack_expq_t * expiration_q;
691 :
692 : /* acct_in_use: Map from account address to bitmask indicating which
693 : bank tiles are using the account and whether that use is read or
694 : write (msb). */
695 : fd_pack_addr_use_t * acct_in_use;
696 :
697 : /* bitset_{w, rw}_in_use stores a subset of the information in
698 : acct_in_use using the compressed set format explained at the top of
699 : this file. rw_in_use stores accounts in use for read or write
700 : while w_in_use stores only those in use for write. */
701 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
702 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
703 :
704 : /* writer_costs: Map (fd_map_chain) from account addresses to the sum
705 : of costs of transactions that write to the account. Used for
706 : enforcing limits on the max write cost per account per block. */
707 : wcost_map_t * writer_costs;
708 :
709 : /* written_list: At the end of every slot, we have to clear out
710 : writer_costs. The map is large, but typically very sparsely
711 : populated. As an optimization, we keep a doubly linked list of the
712 : elements actually used */
713 : wcost_dlist_t written_list[1];
714 :
715 : /* writers: This is the fd_pool that backs writer_costs and
716 : written_list. Each element is either in writers (as a fd_pool) OR
717 : in both writer_costs and written_list. */
718 : fd_pack_wcost_ele_t * writers;
719 :
720 : /* top_writers: A simple max heap of the top 5 writers in the slot,
721 : used by downstream consumers for monitoring purposes. */
722 : fd_pack_addr_use_t top_writers[ FD_PACK_TOP_WRITERS_CNT ];
723 :
724 : /* At initialization time, the caller can configure a blocklist of
725 : accounts. Any transaction that includes one of these accounts will
726 : be rejected. This is an fd_map, and it's effectively const. */
727 : wrapped_acct_t acct_blocklist[ 2*FD_PACK_ACCT_BLOCKLIST_MAX ];
728 :
729 : /* Noncemap is a map_chain that maps from tuples (nonce account,
730 : nonce authority) to a transaction. This
731 : map stores exactly the transactions in pool that have the nonce
732 : flag set. */
733 : noncemap_t * noncemap;
734 :
735 : sig2txn_t * signature_map; /* Stores pointers into pool for deleting by signature */
736 :
737 : /* bundle_temp_map: A fd_map_dynamic (although it could be an fd_map)
738 : used during fd_pack_try_schedule_bundle to store information about
739 : what accounts are used by transactions in the bundle. It's empty
740 : (in a map sense) outside of calls to try_schedule_bundle, and each
741 : call to try_schedule_bundle clears it after use. If bundles are
742 : disabled, this is a valid fd_map_dynamic, but it's as small as
743 : convenient and remains empty. */
744 : fd_pack_addr_use_t * bundle_temp_map;
745 :
746 :
747 : /* use_by_bank: An array of size (max_txn_per_microblock *
748 : FD_TXN_ACCT_ADDR_MAX + 1) for each banking tile. Addressed as
749 : use_by_bank[i][j] where i is in [0, bank_tile_cnt) and j is in
750 : [0, use_by_bank_cnt[i]). Used to release account locks when a
751 : microblock finishes.
752 :
753 : use_by_bank_txn[i][j] stores the cumulative end offset in
754 : use_by_bank[i] for transaction j in the outstanding microblock.
755 : Indexed by i in [0, bank_tile_cnt) and j in
756 : [0, max_txn_per_microblock). */
757 : fd_pack_addr_use_t * use_by_bank [ FD_PACK_MAX_EXECLE_TILES ];
758 : ulong use_by_bank_cnt[ FD_PACK_MAX_EXECLE_TILES ];
759 : ulong * use_by_bank_txn[ FD_PACK_MAX_EXECLE_TILES ];
760 :
761 : fd_histf_t txn_per_microblock[ 1 ];
762 :
763 : fd_histf_t scheduled_cus_per_block[ 1 ];
764 : fd_histf_t rebated_cus_per_block [ 1 ];
765 : fd_histf_t net_cus_per_block [ 1 ];
766 : fd_histf_t pct_cus_per_block [ 1 ];
767 : ulong cumulative_rebated_cus;
768 :
769 :
770 : /* compressed_slot_number: a number in (FD_PACK_SKIP_CNT, USHORT_MAX]
771 : that advances each time we start packing for a new slot. */
772 : ushort compressed_slot_number;
773 :
774 : /* bitset_avail: a stack of which bits are not currently reserved and
775 : can be used to represent an account address.
776 : Indexed [0, bitset_avail_cnt]. Element 0 is fixed at
777 : FD_PACK_BITSET_SLOWPATH. */
778 : ushort bitset_avail[ 1UL+FD_PACK_BITSET_MAX ];
779 : ulong bitset_avail_cnt;
780 :
781 : /* acct_to_bitset: an fd_map_dynamic that maps acct addresses to the
782 : reference count, which bit, etc. */
783 : fd_pack_bitset_acct_mapping_t * acct_to_bitset;
784 :
785 : /* chdkup: scratch memory chkdup needs for its internal processing */
786 : fd_chkdup_t chkdup[ 1 ];
787 :
788 : /* bundle_meta: an array, parallel to the pool, with each element
789 : having size bundle_meta_sz. I.e. if pool[i] has an associated
790 : bundle meta, it's located at bundle_meta[j] for j in
791 : [i*bundle_meta_sz, (i+1)*bundle_meta_sz). */
792 : void * bundle_meta;
793 : };
794 :
795 : typedef struct fd_pack_private fd_pack_t;
796 :
797 : FD_STATIC_ASSERT( offsetof(fd_pack_t, pending_txn_cnt)==FD_PACK_PENDING_TXN_CNT_OFF, txn_cnt_off );
798 :
799 : /* Forward-declare some helper functions */
800 : static ulong delete_transaction( fd_pack_t * pack, fd_pack_ord_txn_t * txn, int delete_full_bundle, int move_from_penalty_treap );
801 : static inline void insert_bundle_impl( fd_pack_t * pack, ulong bundle_idx, ulong txn_cnt, fd_pack_ord_txn_t * * bundle, ulong expires_at );
802 : static inline ulong insert_pre_rotation_bundle_impl( fd_pack_t * pack, ulong txn_cnt, fd_pack_ord_txn_t * * bundle, ulong expires_at, ulong pre_rotation_tip );
803 :
804 : FD_FN_PURE ulong
805 : fd_pack_footprint( ulong pack_depth,
806 : ulong bundle_meta_sz,
807 : ulong bank_tile_cnt,
808 567 : fd_pack_limits_t const * limits ) {
809 567 : if( FD_UNLIKELY( (bank_tile_cnt==0) | (bank_tile_cnt>FD_PACK_MAX_EXECLE_TILES) ) ) return 0UL;
810 567 : if( FD_UNLIKELY( pack_depth<4UL ) ) return 0UL;
811 :
812 567 : int enable_bundles = !!bundle_meta_sz;
813 567 : ulong l;
814 567 : ulong extra_depth = fd_ulong_if( enable_bundles, 1UL+2UL*FD_PACK_MAX_TXN_PER_BUNDLE, 1UL ); /* space for use between init and fini */
815 567 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
816 567 : ulong max_txn_per_mblk = fd_ulong_max( limits->max_txn_per_microblock,
817 567 : fd_ulong_if( enable_bundles, FD_PACK_MAX_TXN_PER_BUNDLE, 0UL ) );
818 567 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * max_txn_per_mblk + 1UL);
819 567 : ulong max_txn_in_flight = bank_tile_cnt * max_txn_per_mblk;
820 :
821 567 : ulong max_w_per_block = fd_ulong_min( limits->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
822 567 : max_txn_per_mblk * limits->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
823 567 : ulong wcost_chain_cnt = wcost_map_chain_cnt_est( max_w_per_block );
824 567 : ulong bundle_temp_accts = fd_ulong_if( enable_bundles, FD_PACK_MAX_TXN_PER_BUNDLE*FD_TXN_ACCT_ADDR_MAX, 1UL );
825 567 : ulong sig_chain_cnt = sig2txn_chain_cnt_est( pack_depth );
826 567 : ulong nonce_chain_cnt = noncemap_chain_cnt_est( pack_depth );
827 :
828 : /* log base 2, but with a 2* so that the hash table stays sparse */
829 567 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
830 567 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
831 567 : int lg_penalty_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap/PENALTY_TREAP_THRESHOLD ) );
832 567 : int lg_bundle_temp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*bundle_temp_accts ) );
833 :
834 567 : l = FD_LAYOUT_INIT;
835 567 : l = FD_LAYOUT_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
836 567 : l = FD_LAYOUT_APPEND( l, trp_pool_align (), trp_pool_footprint ( pack_depth+extra_depth ) ); /* pool */
837 567 : l = FD_LAYOUT_APPEND( l, penalty_map_align(), penalty_map_footprint( lg_penalty_trp ) ); /* penalty_treaps */
838 567 : l = FD_LAYOUT_APPEND( l, expq_align (), expq_footprint ( pack_depth ) ); /* expiration prq */
839 567 : l = FD_LAYOUT_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) ); /* acct_in_use */
840 567 : l = FD_LAYOUT_APPEND( l, wcost_map_align(), wcost_map_footprint( wcost_chain_cnt ) ); /* writer_costs */
841 567 : l = FD_LAYOUT_APPEND( l, wcost_pool_align(), wcost_pool_footprint( max_w_per_block ) ); /* writers */
842 567 : l = FD_LAYOUT_APPEND( l, noncemap_align (), noncemap_footprint ( nonce_chain_cnt ) ); /* noncemap */
843 567 : l = FD_LAYOUT_APPEND( l, sig2txn_align (), sig2txn_footprint ( sig_chain_cnt ) ); /* signature_map */
844 567 : l = FD_LAYOUT_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_bundle_temp ) ); /* bundle_temp_map*/
845 567 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight ); /* use_by_bank */
846 567 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(ulong)*max_txn_in_flight ); /* use_by_bank_txn*/
847 567 : l = FD_LAYOUT_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) ); /* acct_to_bitset */
848 567 : l = FD_LAYOUT_APPEND( l, 64UL, (pack_depth+extra_depth)*bundle_meta_sz ); /* bundle_meta */
849 567 : return FD_LAYOUT_FINI( l, FD_PACK_ALIGN );
850 567 : }
851 :
852 : void *
853 : fd_pack_new( void * mem,
854 : ulong pack_depth,
855 : ulong bundle_meta_sz,
856 : ulong bank_tile_cnt,
857 : fd_pack_limits_t const * limits,
858 : fd_acct_addr_t const * acct_blocklist,
859 : ulong acct_blocklist_cnt,
860 582 : fd_rng_t * rng ) {
861 :
862 582 : int enable_bundles = !!bundle_meta_sz;
863 582 : ulong extra_depth = fd_ulong_if( enable_bundles, 1UL+2UL*FD_PACK_MAX_TXN_PER_BUNDLE, 1UL );
864 582 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
865 582 : ulong max_txn_per_mblk = fd_ulong_max( limits->max_txn_per_microblock,
866 582 : fd_ulong_if( enable_bundles, FD_PACK_MAX_TXN_PER_BUNDLE, 0UL ) );
867 582 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * max_txn_per_mblk + 1UL);
868 582 : ulong max_txn_in_flight = bank_tile_cnt * max_txn_per_mblk;
869 :
870 582 : ulong max_w_per_block = fd_ulong_min( limits->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
871 582 : max_txn_per_mblk * limits->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
872 582 : ulong wcost_chain_cnt = wcost_map_chain_cnt_est( max_w_per_block );
873 582 : ulong bundle_temp_accts = fd_ulong_if( enable_bundles, FD_PACK_MAX_TXN_PER_BUNDLE*FD_TXN_ACCT_ADDR_MAX, 1UL );
874 582 : ulong sig_chain_cnt = sig2txn_chain_cnt_est( pack_depth );
875 582 : ulong nonce_chain_cnt = noncemap_chain_cnt_est( pack_depth );
876 :
877 : /* log base 2, but with a 2* so that the hash table stays sparse */
878 582 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
879 582 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
880 582 : int lg_penalty_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap/PENALTY_TREAP_THRESHOLD ) );
881 582 : int lg_bundle_temp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*bundle_temp_accts ) );
882 :
883 582 : FD_SCRATCH_ALLOC_INIT( l, mem );
884 582 : fd_pack_t * pack = FD_SCRATCH_ALLOC_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
885 : /* The pool has one extra element that is used between insert_init and
886 : cancel/fini. */
887 582 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, trp_pool_align(), trp_pool_footprint ( pack_depth+extra_depth ) );
888 582 : void * _penalty_map = FD_SCRATCH_ALLOC_APPEND( l, penalty_map_align(), penalty_map_footprint( lg_penalty_trp ) );
889 582 : void * _expq = FD_SCRATCH_ALLOC_APPEND( l, expq_align(), expq_footprint ( pack_depth ) );
890 582 : void * _uses = FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) );
891 582 : void * _writer_cost = FD_SCRATCH_ALLOC_APPEND( l, wcost_map_align(), wcost_map_footprint( wcost_chain_cnt ) );
892 582 : void * _written_lst = FD_SCRATCH_ALLOC_APPEND( l, wcost_pool_align(), wcost_pool_footprint( max_w_per_block ) );
893 582 : void * _noncemap = FD_SCRATCH_ALLOC_APPEND( l, noncemap_align(), noncemap_footprint ( nonce_chain_cnt ) );
894 582 : void * _sig_map = FD_SCRATCH_ALLOC_APPEND( l, sig2txn_align(), sig2txn_footprint ( sig_chain_cnt ) );
895 582 : void * _bundle_temp = FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_bundle_temp ) );
896 582 : void * _use_by_bank = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight );
897 582 : void * _use_by_txn = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(ulong)*max_txn_in_flight );
898 582 : void * _acct_bitset = FD_SCRATCH_ALLOC_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) );
899 582 : void * bundle_meta = FD_SCRATCH_ALLOC_APPEND( l, 64UL, (pack_depth+extra_depth)*bundle_meta_sz );
900 :
901 582 : pack->pack_depth = pack_depth;
902 582 : pack->bundle_meta_sz = bundle_meta_sz;
903 582 : pack->bank_tile_cnt = bank_tile_cnt;
904 582 : pack->lim[0] = *limits;
905 582 : pack->pending_txn_cnt = 0UL;
906 582 : pack->microblock_cnt = 0UL;
907 582 : pack->data_bytes_consumed = 0UL;
908 582 : pack->alloc_consumed = 0UL;
909 582 : memset( pack->sched_results, 0, sizeof(pack->sched_results) );
910 582 : pack->rng = rng;
911 582 : pack->cumulative_block_cost = 0UL;
912 582 : pack->expire_before = 0UL;
913 582 : pack->outstanding_microblock_mask = 0UL;
914 582 : pack->cumulative_rebated_cus = 0UL;
915 582 : pack->initializer_bundle_state = FD_PACK_IB_STATE_NOT_INITIALIZED;
916 582 : pack->relative_bundle_idx = 1UL;
917 :
918 582 : acct_blocklist_new( pack->acct_blocklist );
919 582 : int ins_failed = acct_blocklist_cnt>FD_PACK_ACCT_BLOCKLIST_MAX;
920 648 : for( ulong i=0UL; (!ins_failed) & (i<acct_blocklist_cnt); i++ ) {
921 66 : ins_failed |= acct_blocklist_key_inval( acct_blocklist[i] ) ||
922 66 : (NULL==acct_blocklist_insert( pack->acct_blocklist, acct_blocklist[i] ));
923 66 : }
924 582 : if( FD_UNLIKELY( ins_failed ) ) {
925 6 : FD_LOG_WARNING(( "constructing the account blocklist failed. Ensure the list contains no more than %lu "
926 6 : "entries, and does not contain duplicates or the System Program (11...111)", FD_PACK_ACCT_BLOCKLIST_MAX ));
927 6 : return NULL;
928 6 : }
929 :
930 576 : trp_pool_new( _pool, pack_depth+extra_depth );
931 :
932 576 : fd_pack_ord_txn_t * pool = trp_pool_join( _pool );
933 576 : treap_seed( pool, pack_depth+extra_depth, fd_rng_ulong( rng ) );
934 620700 : for( ulong i=0UL; i<pack_depth+extra_depth; i++ ) pool[i].root = FD_ORD_TXN_ROOT_FREE;
935 :
936 576 : (void)trp_pool_leave( pool );
937 :
938 576 : penalty_map_new( _penalty_map, lg_penalty_trp, fd_rng_ulong( rng ) );
939 :
940 : /* These treaps can have at most pack_depth elements at any moment,
941 : but they come from a pool of size pack_depth+extra_depth. */
942 576 : treap_new( (void*)pack->pending, pack_depth+extra_depth );
943 576 : treap_new( (void*)pack->pending_bundles, pack_depth+extra_depth );
944 576 : treap_new( (void*)pack->next_auction, pack_depth+extra_depth );
945 9792 : for( ulong i=0UL; i<FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY; i++ ) {
946 9216 : treap_new( (void*)pack->pre_rotation_bundles[ i ].treap, pack_depth+extra_depth );
947 9216 : }
948 :
949 576 : pack->pre_rotation_bundle_cnt = 0UL;
950 576 : pack->pre_rotation_seq = 0UL;
951 576 : pack->rotation_end_ns = 0L;
952 576 : pack->auction_running = 0;
953 :
954 576 : pack->pending_smallest->cus = ULONG_MAX;
955 576 : pack->pending_smallest->bytes = ULONG_MAX;
956 :
957 576 : expq_new( _expq, pack_depth );
958 :
959 576 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
960 576 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
961 :
962 576 : acct_uses_new( _uses, lg_uses_tbl_sz, fd_rng_ulong( rng ) );
963 576 : acct_uses_new( _bundle_temp, lg_bundle_temp, fd_rng_ulong( rng ) );
964 :
965 576 : wcost_map_new ( _writer_cost, wcost_chain_cnt, fd_rng_ulong( rng ) );
966 576 : wcost_dlist_new( pack->written_list );
967 576 : wcost_pool_new ( _written_lst, max_w_per_block );
968 :
969 576 : noncemap_new( _noncemap, nonce_chain_cnt, fd_rng_ulong( rng ) );
970 :
971 576 : sig2txn_new( _sig_map, sig_chain_cnt, fd_rng_ulong( rng ) );
972 :
973 576 : fd_pack_addr_use_t * use_by_bank = (fd_pack_addr_use_t *)_use_by_bank;
974 576 : ulong * use_by_bank_txn = (ulong *)_use_by_txn;
975 6852 : for( ulong i=0UL; i<bank_tile_cnt; i++ ) {
976 6276 : pack->use_by_bank [i] = use_by_bank + i*(FD_TXN_ACCT_ADDR_MAX*max_txn_per_mblk+1UL);
977 6276 : pack->use_by_bank_cnt[i] = 0UL;
978 6276 : pack->use_by_bank_txn[i] = use_by_bank_txn + i*max_txn_per_mblk;
979 6276 : pack->use_by_bank_txn[i][0] = 0UL;
980 6276 : }
981 30012 : for( ulong i=bank_tile_cnt; i<FD_PACK_MAX_EXECLE_TILES; i++ ) {
982 29436 : pack->use_by_bank [i] = NULL;
983 29436 : pack->use_by_bank_cnt[i] = 0UL;
984 29436 : pack->use_by_bank_txn[i] = NULL;
985 29436 : }
986 :
987 576 : fd_histf_new( pack->txn_per_microblock, FD_MHIST_MIN( PACK, TXN_PER_MICROBLOCK ),
988 576 : FD_MHIST_MAX( PACK, TXN_PER_MICROBLOCK ) );
989 :
990 576 : fd_histf_new( pack->scheduled_cus_per_block, FD_MHIST_MIN( PACK, COST_SCHEDULED_PER_BLOCK ),
991 576 : FD_MHIST_MAX( PACK, COST_SCHEDULED_PER_BLOCK ) );
992 576 : fd_histf_new( pack->rebated_cus_per_block, FD_MHIST_MIN( PACK, CU_REBATED_PER_BLOCK ),
993 576 : FD_MHIST_MAX( PACK, CU_REBATED_PER_BLOCK ) );
994 576 : fd_histf_new( pack->net_cus_per_block, FD_MHIST_MIN( PACK, COST_NET_PER_BLOCK ),
995 576 : FD_MHIST_MAX( PACK, COST_NET_PER_BLOCK ) );
996 576 : fd_histf_new( pack->pct_cus_per_block, FD_MHIST_MIN( PACK, COST_PER_BLOCK_PCT ),
997 576 : FD_MHIST_MAX( PACK, COST_PER_BLOCK_PCT ) );
998 :
999 576 : pack->compressed_slot_number = (ushort)(FD_PACK_SKIP_CNT+1);
1000 :
1001 576 : pack->bitset_avail[ 0 ] = FD_PACK_BITSET_SLOWPATH;
1002 197184 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) pack->bitset_avail[ i+1UL ] = (ushort)i;
1003 576 : pack->bitset_avail_cnt = FD_PACK_BITSET_MAX;
1004 :
1005 576 : bitset_map_new( _acct_bitset, lg_acct_in_trp, fd_rng_ulong( rng ) );
1006 :
1007 576 : fd_chkdup_new( pack->chkdup, rng );
1008 :
1009 576 : pack->bundle_meta = bundle_meta;
1010 :
1011 576 : return mem;
1012 582 : }
1013 :
1014 : fd_pack_t *
1015 576 : fd_pack_join( void * mem ) {
1016 576 : FD_SCRATCH_ALLOC_INIT( l, mem );
1017 576 : fd_pack_t * pack = FD_SCRATCH_ALLOC_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
1018 :
1019 576 : int enable_bundles = !!pack->bundle_meta_sz;
1020 576 : ulong pack_depth = pack->pack_depth;
1021 576 : ulong extra_depth = fd_ulong_if( enable_bundles, 1UL+2UL*FD_PACK_MAX_TXN_PER_BUNDLE, 1UL );
1022 576 : ulong bank_tile_cnt = pack->bank_tile_cnt;
1023 576 : ulong max_txn_per_microblock = fd_ulong_max( pack->lim->max_txn_per_microblock,
1024 576 : fd_ulong_if( enable_bundles, FD_PACK_MAX_TXN_PER_BUNDLE, 0UL ) );
1025 :
1026 576 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
1027 576 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * max_txn_per_microblock + 1UL);
1028 576 : ulong max_txn_in_flight = bank_tile_cnt * max_txn_per_microblock;
1029 576 : ulong max_w_per_block = fd_ulong_min( pack->lim->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
1030 576 : max_txn_per_microblock * pack->lim->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
1031 576 : ulong wcost_chain_cnt = wcost_map_chain_cnt_est( max_w_per_block );
1032 576 : ulong bundle_temp_accts = fd_ulong_if( enable_bundles, FD_PACK_MAX_TXN_PER_BUNDLE*FD_TXN_ACCT_ADDR_MAX, 1UL );
1033 576 : ulong sig_chain_cnt = sig2txn_chain_cnt_est( pack_depth );
1034 576 : ulong nonce_chain_cnt = noncemap_chain_cnt_est( pack_depth );
1035 :
1036 576 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
1037 576 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
1038 576 : int lg_penalty_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap/PENALTY_TREAP_THRESHOLD ) );
1039 576 : int lg_bundle_temp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*bundle_temp_accts ) );
1040 :
1041 :
1042 576 : pack->pool = trp_pool_join( FD_SCRATCH_ALLOC_APPEND( l, trp_pool_align(), trp_pool_footprint ( pack_depth+extra_depth ) ) );
1043 576 : pack->penalty_treaps= penalty_map_join(FD_SCRATCH_ALLOC_APPEND( l, penalty_map_align(),penalty_map_footprint( lg_penalty_trp ) ) );
1044 576 : pack->expiration_q = expq_join ( FD_SCRATCH_ALLOC_APPEND( l, expq_align(), expq_footprint ( pack_depth ) ) );
1045 576 : pack->acct_in_use = acct_uses_join( FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint ( lg_uses_tbl_sz ) ) );
1046 576 : pack->writer_costs = wcost_map_join( FD_SCRATCH_ALLOC_APPEND( l, wcost_map_align(), wcost_map_footprint ( wcost_chain_cnt ) ) );
1047 576 : pack->writers = wcost_pool_join( FD_SCRATCH_ALLOC_APPEND( l, wcost_pool_align(), wcost_pool_footprint( max_w_per_block ) ) );
1048 576 : pack->noncemap = noncemap_join( FD_SCRATCH_ALLOC_APPEND( l, noncemap_align(), noncemap_footprint ( nonce_chain_cnt ) ) );
1049 576 : pack->signature_map = sig2txn_join( FD_SCRATCH_ALLOC_APPEND( l, sig2txn_align(), sig2txn_footprint ( sig_chain_cnt ) ) );
1050 576 : pack->bundle_temp_map=acct_uses_join( FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint ( lg_bundle_temp ) ) );
1051 576 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight );
1052 576 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(ulong)*max_txn_in_flight );
1053 576 : pack->acct_to_bitset= bitset_map_join( FD_SCRATCH_ALLOC_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) ) );
1054 576 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 64UL, (pack_depth+extra_depth)*pack->bundle_meta_sz );
1055 :
1056 576 : wcost_dlist_join( pack->written_list );
1057 :
1058 576 : FD_MGAUGE_SET( PACK, TXN_PENDING_CAPACITY, pack->pack_depth );
1059 576 : memset( pack->top_writers, 0, sizeof(pack->top_writers) );
1060 :
1061 576 : return pack;
1062 576 : }
1063 :
1064 :
1065 : /* Returns 0 on failure, 1 on success. */
1066 : static int
1067 : fd_pack_estimate_rewards_and_compute( fd_txn_e_t * txne,
1068 : fd_pack_ord_txn_t * out,
1069 1917423 : fd_pack_limits_t const * lim ) {
1070 1917423 : fd_txn_t * txn = TXN(txne->txnp);
1071 1917423 : ulong sig_rewards = FD_PACK_FEE_PER_SIGNATURE * txn->signature_cnt; /* Easily in [5000, 635000] */
1072 :
1073 1917423 : ulong requested_execution_cus;
1074 1917423 : ulong priority_rewards;
1075 1917423 : ulong precompile_sigs;
1076 1917423 : ulong requested_loaded_accounts_data_cost;
1077 1917423 : ulong allocated_data;
1078 1917423 : ulong cost_estimate = fd_pack_compute_cost( txn, txne->txnp->payload, &requested_execution_cus, &priority_rewards, &precompile_sigs, &requested_loaded_accounts_data_cost, &allocated_data );
1079 :
1080 1917423 : if( FD_UNLIKELY( !cost_estimate ) ) return 0;
1081 :
1082 1917420 : sig_rewards += FD_PACK_FEE_PER_SIGNATURE * precompile_sigs;
1083 1917420 : sig_rewards = sig_rewards * FD_PACK_TXN_FEE_BURN_PCT / 100UL;
1084 :
1085 : /* No fancy CU estimation in this version of pack
1086 : for( ulong i=0UL; i<(ulong)txn->instr_cnt; i++ ) {
1087 : uchar prog_id_idx = txn->instr[ i ].program_id;
1088 : fd_acct_addr_t const * acct_addr = fd_txn_get_acct_addrs( txn, txnp->payload ) + (ulong)prog_id_idx;
1089 : }
1090 : */
1091 1917420 : out->rewards = (priority_rewards < (UINT_MAX - sig_rewards)) ? (uint)(sig_rewards + priority_rewards) : UINT_MAX;
1092 1917420 : out->compute_est = (uint)cost_estimate;
1093 1917420 : out->txn->pack_cu.requested_exec_plus_acct_data_cus = (uint)(requested_execution_cus + requested_loaded_accounts_data_cost);
1094 1917420 : out->txn->pack_cu.non_execution_cus = (uint)(cost_estimate - requested_execution_cus - requested_loaded_accounts_data_cost);
1095 1917420 : out->txn->pack_alloc = (uint)allocated_data;
1096 :
1097 : /* If a transaction allocates a lot, we want to treat it as if it
1098 : requests more CUs. However, we use compute_est in the block
1099 : limit calculations, so we can't touch it. To have the same
1100 : effect, we decrease rewards.
1101 : divisor is 1 unless
1102 : allocated_data cost_estimate
1103 : ---------------------------- >= ------------------
1104 : max_allocated_data_per_block max_cost_per_block
1105 :
1106 : 0 <=allocated_data <=20 * 1024^2
1107 : 30*10^6 <= max_cost_per_block < 2^32
1108 : 1020 <= cost_estimate < 1.6 * 10^6
1109 : 50*10^6 <= max_allocated_data_per_block <= 100 * 1000^2
1110 : (changes with the slot time duration)
1111 : So the numerator (<2^57) and denominator (<2^48) can't overflow.
1112 : Both cost_estimate and max_allocated_data_per_block non-zero,
1113 : so the denominator is never zero.
1114 : */
1115 1917420 : ulong divisor = 1UL + (allocated_data * lim->max_cost_per_block) / (cost_estimate * lim->max_allocated_data_per_block);
1116 1917420 : out->rewards /= (uint)divisor;
1117 :
1118 1917420 : return 1;
1119 1917423 : }
1120 :
1121 : /* Returns 0 on failure, 1 if not a durable nonce transaction, and 2 if
1122 : it is. FIXME: These return codes are set to harmonize with
1123 : estimate_rewards_and_compute but -1/0/1 makes a lot more sense to me.
1124 : */
1125 : static int
1126 1917420 : fd_pack_validate_durable_nonce( fd_txn_e_t * txne ) {
1127 1917420 : fd_txn_t const * txn = TXN(txne->txnp);
1128 :
1129 : /* First instruction invokes system program with 4 bytes of
1130 : instruction data with the little-endian value 4. It also has 3
1131 : accounts: the nonce account, recent blockhashes sysvar, and the
1132 : nonce authority. It seems like technically the nonce authority may
1133 : not need to be passed in, but we disallow that. We also allow
1134 : trailing data and trailing accounts. We want to organize the
1135 : checks somewhat to minimize cache misses. */
1136 1917420 : if( FD_UNLIKELY( txn->instr_cnt==0 ) ) return 1;
1137 1917420 : if( FD_UNLIKELY( txn->instr[ 0 ].data_sz<4UL ) ) return 1;
1138 1917420 : if( FD_UNLIKELY( txn->instr[ 0 ].acct_cnt<3UL ) ) return 1; /* It seems like technically 2 is allowed, but never used */
1139 5004 : if( FD_LIKELY ( fd_uint_load_4( txne->txnp->payload + txn->instr[ 0 ].data_off )!=4U ) ) return 1;
1140 : /* The program has to be a static account */
1141 1194 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, txne->txnp->payload );
1142 1194 : if( FD_UNLIKELY( !fd_memeq( accts[ txn->instr[ 0 ].program_id ].b, null_addr.b, 32UL ) ) ) return 1;
1143 : /* SIMD-0242 requires the nonce account to be static. */
1144 1194 : if( FD_UNLIKELY( txne->txnp->payload[ txn->instr[ 0 ].acct_off ]>=txn->acct_addr_cnt ) ) return 1;
1145 1191 : if( FD_UNLIKELY( !fd_txn_is_writable( txn, txne->txnp->payload[ txn->instr[ 0 ].acct_off ] ) ) ) return 1;
1146 1182 : if( FD_UNLIKELY( !fd_txn_is_signer( txn, txne->txnp->payload[ txn->instr[ 0 ].acct_off+2 ] ) ) ) return 0;
1147 : /* We could check recent blockhash, but it's not necessary */
1148 1179 : return 2;
1149 1182 : }
1150 :
1151 : /* Can the fee payer afford to pay a transaction with the specified
1152 : price? Returns 1 if so, 0 otherwise. This is just a stub that
1153 : always returns 1 for now, and the real check is deferred to the bank
1154 : tile. In general, this function can't be totally accurate, because
1155 : the transactions immediately prior to this one can affect the balance
1156 : of this fee payer, but a simple check here may be helpful for
1157 : reducing spam. */
1158 : static int
1159 : fd_pack_can_fee_payer_afford( fd_acct_addr_t const * acct_addr,
1160 1917411 : ulong price /* in lamports */) {
1161 1917411 : (void)acct_addr;
1162 1917411 : (void)price;
1163 1917411 : return 1;
1164 1917411 : }
1165 :
1166 :
1167 :
1168 :
1169 :
1170 : fd_txn_e_t *
1171 32943 : fd_pack_insert_txn_init( fd_pack_t * pack ) {
1172 32943 : fd_pack_ord_txn_t * ord = trp_pool_ele_acquire( pack->pool );
1173 : /* fini clears the bitsets; nothing on the way there touches those
1174 : lines and a just-evicted element has them cold. The two sets are
1175 : adjacent and span at most two lines, whatever the bitset mode. */
1176 32943 : __builtin_prefetch( &ord->rw_bitset, 1, 3 );
1177 32943 : __builtin_prefetch( (uchar const *)&ord->w_bitset+sizeof(ord->w_bitset)-1UL, 1, 3 );
1178 32943 : return ord->txn_e;
1179 32943 : }
1180 0 : void fd_pack_insert_txn_cancel( fd_pack_t * pack, fd_txn_e_t * txn ) { trp_pool_ele_release( pack->pool, (fd_pack_ord_txn_t*)txn ); }
1181 :
1182 75 : #define REJECT( reason ) do { \
1183 75 : trp_pool_ele_release( pack->pool, ord ); \
1184 75 : return FD_PACK_INSERT_REJECT_ ## reason; \
1185 75 : } while( 0 )
1186 :
1187 : /* These require txn, accts, and alt to be defined as per usual */
1188 35409679 : #define ACCT_IDX_TO_PTR( idx ) (__extension__( { \
1189 35409679 : ulong __idx = (ulong)(idx); \
1190 35409679 : ulong __imm = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ); \
1191 35409679 : __idx<__imm ? accts+__idx : alt+(__idx-__imm); \
1192 35409679 : }))
1193 35379426 : #define ACCT_ITER_TO_PTR( iter ) ACCT_IDX_TO_PTR( fd_txn_acct_iter_idx( iter ) )
1194 :
1195 :
1196 : /* Tries to find the worst transaction in any treap in pack. If that
1197 : transaction's score is worse than or equal to threshold_score, it
1198 : initiates a delete and returns the number of deleted transactions
1199 : (potentially more than 1 for a bundle). If it's higher than
1200 : threshold_score, it returns 0. To force this function to delete the
1201 : worst transaction if there are any eligible ones, pass FLT_MAX as
1202 : threshold_score. */
1203 : static inline ulong
1204 : delete_worst( fd_pack_t * pack,
1205 3156 : float threshold_score ) {
1206 : /* If the tree is full, we want to see if this is better than the
1207 : worst element in the pool before inserting. If the new transaction
1208 : is better than that one, we'll delete it and insert the new
1209 : transaction. Otherwise, we'll throw away this transaction.
1210 :
1211 : We want to bias the definition of "worst" here to provide better
1212 : quality of service. For example, if the pool is filled with
1213 : transactions that all write to the same account, we want to bias
1214 : towards treating one of those transactions as the worst, even if
1215 : they pay slightly higher fees per computer unit, since we know we
1216 : won't actually be able to schedule them all.
1217 :
1218 : This is a tricky task, however. All our notions of priority and
1219 : better/worse are based on static information about the transaction,
1220 : and there's not an easy way to take into account global
1221 : information, for example, how many other transactions contend with
1222 : this one. One idea is to build a heap (not a treap, since we only
1223 : need pop-min, insert, and delete) with one element for each element
1224 : in the pool, with a "delete me" score that's related but not
1225 : identical to the normal score. This would allow building in some
1226 : global information. The downside is that the global information
1227 : that gets integrated is static. E.g. if you bias a transaction's
1228 : "delete me" score to make it more likely to be deleted because
1229 : there are many conflicting transactions in the pool, the score
1230 : stays biased, even if the global conditions change (unless you come
1231 : up with some complicated re-scoring scheme). This can work, since
1232 : when the pool is full, the global bias factors are unlikely to
1233 : change significantly at the relevant timescales.
1234 :
1235 : However, rather than this, we implement a simpler probabilistic
1236 : scheme. We'll sample M transactions, find the worst transaction in
1237 : each of the M treaps, compute a "delete me" score for those <= M
1238 : transactions, and delete the worst. If one penalty treap is
1239 : starting to get big, then it becomes very likely that the random
1240 : sample will find it and choose to delete a transaction from it.
1241 :
1242 : The exact formula for the "delete me" score should be the matter of
1243 : some more intense quantitative research. For now, we'll just use
1244 : this:
1245 :
1246 : Treap with N transactions Scale Factor
1247 : Pending 1.0
1248 : Next auction same as pending
1249 : Penalty treap 1.0 at <= 100 transactions, then sqrt(100/N)
1250 : Pending bundles inf (since the rewards value is fudged)
1251 :
1252 : We'll also use M=8. */
1253 :
1254 3156 : float worst_score = FLT_MAX;
1255 3156 : fd_pack_ord_txn_t * worst = NULL;
1256 3156 : uint pool_max = (uint)trp_pool_max( pack->pool );
1257 3156 : ulong samples[ 8UL ];
1258 28404 : for( ulong i=0UL; i<8UL; i++ ) {
1259 : /* Roll all 8 first so the root loads (8 cold lines) overlap */
1260 25248 : samples[ i ] = fd_rng_uint_roll( pack->rng, pool_max );
1261 25248 : __builtin_prefetch( &pack->pool[ samples[ i ] ].root, 0, 3 );
1262 25248 : }
1263 28404 : for( ulong i=0UL; i<8UL; i++ ) {
1264 25248 : ulong sample_i = samples[ i ];
1265 :
1266 25248 : fd_pack_ord_txn_t * sample = &pack->pool[ sample_i ];
1267 : /* Presumably if we're calling this, the pool is almost entirely
1268 : full, so the probability of choosing a free one is small. If
1269 : it does happen, find the first one that isn't free. */
1270 28016 : while( FD_UNLIKELY( sample->root==FD_ORD_TXN_ROOT_FREE ) ) sample = &pack->pool[ (++sample_i)%pool_max ];
1271 :
1272 25248 : int root_idx = sample->root;
1273 25248 : float multiplier = 0.0f; /* The smaller this is, the more biased we'll be to deleting it */
1274 25248 : treap_t * treap;
1275 25248 : switch( root_idx & FD_ORD_TXN_ROOT_TAG_MASK ) {
1276 0 : default:
1277 0 : case FD_ORD_TXN_ROOT_FREE: {
1278 0 : FD_LOG_CRIT(( "Double free detected" ));
1279 0 : return ULONG_MAX; /* Can't be hit */
1280 0 : }
1281 3637 : case FD_ORD_TXN_ROOT_PENDING: {
1282 3637 : treap = pack->pending;
1283 3637 : multiplier = 1.0f;
1284 3637 : break;
1285 0 : }
1286 0 : case FD_ORD_TXN_ROOT_NEXT_AUCTION: {
1287 0 : treap = pack->next_auction;
1288 0 : multiplier = 1.0f;
1289 0 : break;
1290 0 : }
1291 0 : case FD_ORD_TXN_ROOT_PENDING_BUNDLE: {
1292 : /* We don't have a way to tell how much these actually pay in
1293 : rewards, so we just assume they are very high. */
1294 0 : treap = pack->pending_bundles;
1295 : /* We cap rewards at UINT_MAX lamports for estimation, and min
1296 : CUs is about 1000, which means rewards/compute < 5e6.
1297 : FLT_MAX is around 3e38. That means, 1e20*rewards/compute is
1298 : much less than FLT_MAX, so we won't have any issues with
1299 : overflow. On the other hand, if rewards==1 lamport and
1300 : compute is 2 million CUs, 1e20*1/2e6 is still higher than any
1301 : normal transaction. */
1302 0 : multiplier = 1e20f;
1303 0 : break;
1304 0 : }
1305 355 : case FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( 0 ): {
1306 355 : treap = pack->pre_rotation_bundles[ FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE_IDX( root_idx ) ].treap;
1307 355 : multiplier = 1e20f;
1308 355 : break;
1309 0 : }
1310 21256 : case FD_ORD_TXN_ROOT_PENALTY( 0 ): {
1311 21256 : fd_txn_t * txn = TXN( sample->txn );
1312 21256 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, sample->txn->payload );
1313 21256 : fd_acct_addr_t const * alt = sample->txn_e->alt_accts;
1314 21256 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( root_idx ) );
1315 21256 : fd_pack_penalty_treap_t * q = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
1316 21256 : FD_TEST( q );
1317 21256 : ulong cnt = treap_ele_cnt( q->penalty_treap );
1318 21256 : treap = q->penalty_treap;
1319 :
1320 21256 : multiplier = sqrtf( 100.0f / (float)fd_ulong_max( 100UL, cnt ) );
1321 21256 : break;
1322 21256 : }
1323 25248 : }
1324 : /* Get the worst from the sampled treap */
1325 25248 : treap_fwd_iter_t _cur=treap_fwd_iter_init( treap, pack->pool );
1326 25248 : FD_TEST( !treap_fwd_iter_done( _cur ) ); /* It can't be empty because we just sampled an element from it. */
1327 25248 : sample = treap_fwd_iter_ele( _cur, pack->pool );
1328 :
1329 25248 : float score = multiplier * (float)sample->rewards / (float)sample->compute_est;
1330 25248 : worst = fd_ptr_if( score<worst_score, sample, worst );
1331 25248 : worst_score = fd_float_if( worst_score<score, worst_score, score );
1332 25248 : }
1333 :
1334 3156 : if( FD_UNLIKELY( !worst ) ) return 0;
1335 3156 : if( FD_UNLIKELY( threshold_score<worst_score ) ) return 0;
1336 :
1337 : /* The next eviction most likely takes worst's in-order successor;
1338 : warm what delete_transaction reads of it: the treap node, the
1339 : payload's account addresses, the metadata and the parsed txn. */
1340 3123 : treap_fwd_iter_t nxt = treap_fwd_iter_next( (treap_fwd_iter_t)treap_idx_fast( worst, pack->pool ), pack->pool );
1341 3123 : if( FD_LIKELY( !treap_fwd_iter_done( nxt ) ) ) {
1342 3123 : fd_pack_ord_txn_t const * n = pack->pool + nxt;
1343 3123 : __builtin_prefetch( &n->root, 0, 3 );
1344 3123 : __builtin_prefetch( &n->rewards, 0, 3 );
1345 3123 : __builtin_prefetch( n->txn->payload+ 64UL, 0, 3 );
1346 3123 : __builtin_prefetch( n->txn->payload+128UL, 0, 3 );
1347 3123 : __builtin_prefetch( &n->txn->payload_sz, 0, 3 );
1348 3123 : __builtin_prefetch( TXN( n->txn ), 0, 3 );
1349 3123 : }
1350 :
1351 3123 : return delete_transaction( pack, worst, 1, 1 );
1352 3156 : }
1353 :
1354 : static inline int
1355 : validate_transaction( fd_pack_t * pack,
1356 : fd_pack_ord_txn_t const * ord,
1357 : fd_txn_t const * txn,
1358 : fd_acct_addr_t const * accts,
1359 : fd_acct_addr_t const * alt,
1360 1917411 : int check_bundle_blacklist ) {
1361 1917411 : int writes_to_sysvar = 0;
1362 1917411 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1363 3886029 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1364 1968618 : writes_to_sysvar |= fd_pack_unwritable_contains( ACCT_ITER_TO_PTR( iter ) );
1365 1968618 : }
1366 :
1367 1917411 : int bundle_blacklist = 0;
1368 1917411 : int acct_blocklist = 0;
1369 1917411 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_ALL );
1370 7781274 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1371 5863863 : bundle_blacklist |= (3==fd_pack_tip_prog_check_blacklist( ACCT_ITER_TO_PTR( iter ) ));
1372 : /* querying for the inval key is a violation of the fd_map
1373 : contract, even though it's actually fine... */
1374 5863863 : acct_blocklist |= (!acct_blocklist_key_inval( *ACCT_ITER_TO_PTR( iter ) )) &&
1375 5863863 : !!acct_blocklist_query( pack->acct_blocklist, *ACCT_ITER_TO_PTR( iter ), NULL );
1376 5863863 : }
1377 :
1378 1917411 : fd_chkdup_t * chkdup = pack->chkdup;
1379 1917411 : ulong imm_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1380 1917411 : ulong alt_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALT );
1381 :
1382 : /* Throw out transactions ... */
1383 : /* ... that are unfunded */
1384 1917411 : if( FD_UNLIKELY( !fd_pack_can_fee_payer_afford( accts, ord->rewards ) ) ) return FD_PACK_INSERT_REJECT_UNAFFORDABLE;
1385 : /* ... that are so big they'll never run */
1386 1917411 : if( FD_UNLIKELY( ord->compute_est >= pack->lim->max_cost_per_block ) ) return FD_PACK_INSERT_REJECT_TOO_LARGE;
1387 : /* ... that load too many accounts (ignoring 9LZdXeKGeBV6hRLdxS1rHbHoEUsKqesCC2ZAPTPKJAbK) */
1388 1917411 : if( FD_UNLIKELY( fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALL )>64UL ) ) return FD_PACK_INSERT_REJECT_ACCOUNT_CNT;
1389 : /* ... that duplicate an account address */
1390 1917408 : if( FD_UNLIKELY( fd_chkdup_check( chkdup, accts, imm_cnt, alt, alt_cnt ) ) ) return FD_PACK_INSERT_REJECT_DUPLICATE_ACCT;
1391 : /* ... that try to write to a sysvar */
1392 1917405 : if( FD_UNLIKELY( writes_to_sysvar ) ) return FD_PACK_INSERT_REJECT_WRITES_SYSVAR;
1393 : /* ... that use an account that violates bundle rules */
1394 1917312 : if( FD_UNLIKELY( bundle_blacklist & !!check_bundle_blacklist ) ) return FD_PACK_INSERT_REJECT_BUNDLE_BLACKLIST;
1395 : /* ... that use a blocklisted account */
1396 1917312 : if( FD_UNLIKELY( acct_blocklist ) ) return FD_PACK_INSERT_REJECT_ACCT_BLOCKLIST;
1397 :
1398 1917297 : return 0;
1399 1917312 : }
1400 :
1401 :
1402 :
1403 : /* returns cumulative penalty "points", i.e. the sum of the populated
1404 : section of penalties (which also tells the caller how much of the
1405 : array is populated. */
1406 : static inline ulong
1407 : populate_bitsets( fd_pack_t * pack,
1408 : fd_pack_ord_txn_t * ord,
1409 : ushort penalties [ static FD_TXN_ACCT_ADDR_MAX ],
1410 1916187 : uchar penalty_idx[ static FD_TXN_ACCT_ADDR_MAX ] ) {
1411 1916187 : FD_PACK_BITSET_CLEAR( ord->rw_bitset );
1412 1916187 : FD_PACK_BITSET_CLEAR( ord->w_bitset );
1413 :
1414 1916187 : fd_txn_t * txn = TXN(ord->txn);
1415 1916187 : uchar * payload = ord->txn->payload;
1416 :
1417 1916187 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, payload );
1418 1916187 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
1419 :
1420 1916187 : ulong cumulative_penalty = 0UL;
1421 1916187 : ulong penalty_i = 0UL;
1422 :
1423 : /* Scheduling this transaction looks every account up in acct_in_use,
1424 : whose slot for a fresh account is a cold line; warm them now. */
1425 1916187 : {
1426 1916187 : ulong uses_seed = acct_uses_seed( pack->acct_in_use );
1427 1916187 : ulong uses_mask = acct_uses_slot_cnt( pack->acct_in_use )-1UL;
1428 1916187 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE|FD_TXN_ACCT_CAT_READONLY );
1429 7769097 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1430 5852910 : ulong slot = acct_uses_key_hash( *ACCT_ITER_TO_PTR( iter ), uses_seed ) & uses_mask;
1431 5852910 : __builtin_prefetch( pack->acct_in_use+slot, 0, 2 );
1432 5852910 : }
1433 1916187 : }
1434 :
1435 1916187 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1436 3879945 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1437 1963758 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1438 1963758 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, acct, NULL );
1439 1963758 : if( FD_UNLIKELY( q==NULL ) ) {
1440 1939732 : q = bitset_map_insert( pack->acct_to_bitset, acct );
1441 1939732 : q->ref_cnt = 0UL;
1442 1939732 : q->first_instance = ord;
1443 1939732 : q->first_instance_was_write = 1;
1444 1939732 : q->bit = FD_PACK_BITSET_FIRST_INSTANCE;
1445 1939732 : } else if( FD_UNLIKELY( q->bit == FD_PACK_BITSET_FIRST_INSTANCE ) ) {
1446 1874 : q->bit = pack->bitset_avail[ pack->bitset_avail_cnt ];
1447 1874 : pack->bitset_avail_cnt = fd_ulong_if( !!pack->bitset_avail_cnt, pack->bitset_avail_cnt-1UL, 0UL );
1448 :
1449 1874 : FD_PACK_BITSET_SETN( q->first_instance->rw_bitset, q->bit );
1450 1874 : if( q->first_instance_was_write ) FD_PACK_BITSET_SETN( q->first_instance->w_bitset, q->bit );
1451 1874 : }
1452 1963758 : ulong penalty = fd_ulong_max( q->ref_cnt, PENALTY_TREAP_THRESHOLD )-PENALTY_TREAP_THRESHOLD;
1453 1963758 : if( FD_UNLIKELY( penalty ) ) {
1454 17667 : penalties [ penalty_i ] = (ushort)penalty;
1455 17667 : penalty_idx[ penalty_i ] = (uchar )fd_txn_acct_iter_idx( iter );
1456 17667 : penalty_i++;
1457 17667 : cumulative_penalty += penalty;
1458 17667 : }
1459 :
1460 1963758 : q->ref_cnt++;
1461 1963758 : FD_PACK_BITSET_SETN( ord->rw_bitset, q->bit );
1462 1963758 : FD_PACK_BITSET_SETN( ord->w_bitset , q->bit );
1463 1963758 : }
1464 :
1465 1916187 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1466 5805339 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1467 :
1468 3889152 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1469 3889152 : if( FD_UNLIKELY( fd_pack_unwritable_contains( &acct ) ) ) continue;
1470 :
1471 1964106 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, acct, NULL );
1472 1964106 : if( FD_UNLIKELY( q==NULL ) ) {
1473 24135 : q = bitset_map_insert( pack->acct_to_bitset, acct );
1474 24135 : q->ref_cnt = 0UL;
1475 24135 : q->first_instance = ord;
1476 24135 : q->first_instance_was_write = 0;
1477 24135 : q->bit = FD_PACK_BITSET_FIRST_INSTANCE;
1478 1939971 : } else if( FD_UNLIKELY( q->bit == FD_PACK_BITSET_FIRST_INSTANCE ) ) {
1479 3729 : q->bit = pack->bitset_avail[ pack->bitset_avail_cnt ];
1480 3729 : pack->bitset_avail_cnt = fd_ulong_if( !!pack->bitset_avail_cnt, pack->bitset_avail_cnt-1UL, 0UL );
1481 :
1482 3729 : FD_PACK_BITSET_SETN( q->first_instance->rw_bitset, q->bit );
1483 3729 : if( q->first_instance_was_write ) FD_PACK_BITSET_SETN( q->first_instance->w_bitset, q->bit );
1484 3729 : }
1485 :
1486 1964106 : q->ref_cnt++;
1487 1964106 : FD_PACK_BITSET_SETN( ord->rw_bitset, q->bit );
1488 1964106 : }
1489 1916187 : return cumulative_penalty;
1490 1916187 : }
1491 :
1492 : static void
1493 : insert_txn( fd_pack_t * pack,
1494 32757 : fd_pack_ord_txn_t * ord ) {
1495 : /* If an auction is running, all incoming transactions should be
1496 : held in next_auction until the auction has ended. */
1497 32757 : if( pack->auction_running ) {
1498 12 : ord->root = FD_ORD_TXN_ROOT_NEXT_AUCTION;
1499 12 : treap_ele_insert( pack->next_auction, ord, pack->pool );
1500 12 : return;
1501 12 : }
1502 :
1503 32745 : fd_txn_t * txn = TXN( ord->txn );
1504 32745 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, ord->txn->payload );
1505 32745 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
1506 :
1507 : /* Since the pool uses ushorts, the size of the pool is < USHORT_MAX.
1508 : Each transaction can reference an account at most once, which means
1509 : that the total number of references for an account is < USHORT_MAX.
1510 : If these were ulongs, the array would be 512B, which is kind of a
1511 : lot to zero out.*/
1512 32745 : ushort penalties[ FD_TXN_ACCT_ADDR_MAX ] = {0};
1513 32745 : uchar penalty_idx[ FD_TXN_ACCT_ADDR_MAX ];
1514 32745 : ulong cumulative_penalty = populate_bitsets( pack, ord, penalties, penalty_idx );
1515 :
1516 32745 : treap_t * insert_into = pack->pending;
1517 :
1518 32745 : if( FD_UNLIKELY( cumulative_penalty ) ) { /* Optimize for high parallelism case */
1519 : /* Compute a weighted random choice */
1520 6159 : ulong roll = (ulong)fd_rng_uint_roll( pack->rng, (uint)cumulative_penalty ); /* cumulative_penalty < USHORT_MAX*64 < UINT_MAX */
1521 6159 : ulong i = 0UL;
1522 : /* Find the right one. This can be done in O(log N), but I imagine
1523 : N is normally so small that doesn't matter. */
1524 11941 : while( roll>=penalties[i] ) roll -= (ulong)penalties[i++];
1525 :
1526 6159 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( penalty_idx[i] );
1527 6159 : fd_pack_penalty_treap_t * q = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
1528 6159 : if( FD_UNLIKELY( q==NULL ) ) {
1529 21 : q = penalty_map_insert( pack->penalty_treaps, penalty_acct );
1530 21 : treap_new( q->penalty_treap, trp_pool_max( pack->pool ) );
1531 21 : }
1532 6159 : insert_into = q->penalty_treap;
1533 6159 : ord->root = FD_ORD_TXN_ROOT_PENALTY( penalty_idx[i] );
1534 26586 : } else {
1535 26586 : ord->root = FD_ORD_TXN_ROOT_PENDING;
1536 :
1537 26586 : pack->pending_smallest->cus = fd_ulong_min( pack->pending_smallest->cus, ord->compute_est );
1538 26586 : pack->pending_smallest->bytes = fd_ulong_min( pack->pending_smallest->bytes, ord->txn->payload_sz );
1539 26586 : }
1540 :
1541 32745 : treap_ele_insert( insert_into, ord, pack->pool );
1542 32745 : }
1543 :
1544 : int
1545 : fd_pack_insert_txn_fini( fd_pack_t * pack,
1546 : fd_txn_e_t * txne,
1547 : ulong expires_at,
1548 32943 : ulong * delete_cnt ) {
1549 32943 : *delete_cnt = 0UL;
1550 :
1551 32943 : fd_pack_ord_txn_t * ord = (fd_pack_ord_txn_t *)txne;
1552 :
1553 32943 : fd_txn_t * txn = TXN(txne->txnp);
1554 32943 : uchar * payload = txne->txnp->payload;
1555 :
1556 32943 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, payload );
1557 32943 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
1558 :
1559 32943 : int est_result = fd_pack_estimate_rewards_and_compute( txne, ord, pack->lim );
1560 32943 : if( FD_UNLIKELY( !est_result ) ) REJECT( ESTIMATION_FAIL );
1561 :
1562 32940 : int nonce_result = fd_pack_validate_durable_nonce( txne );
1563 32940 : if( FD_UNLIKELY( !nonce_result ) ) REJECT( INVALID_NONCE );
1564 32937 : int is_durable_nonce = nonce_result==2;
1565 32937 : ord->txn->flags &= ~FD_TXN_P_FLAGS_DURABLE_NONCE;
1566 32937 : ord->txn->flags |= fd_uint_if( is_durable_nonce, FD_TXN_P_FLAGS_DURABLE_NONCE, 0U );
1567 :
1568 32937 : int validation_result = validate_transaction( pack, ord, txn, accts, alt, !!pack->bundle_meta_sz );
1569 32937 : if( FD_UNLIKELY( validation_result ) ) {
1570 114 : trp_pool_ele_release( pack->pool, ord );
1571 114 : return validation_result;
1572 114 : }
1573 :
1574 : /* Reject any transactions that have already expired */
1575 32823 : if( FD_UNLIKELY( (!is_durable_nonce) & (expires_at<pack->expire_before )) ) REJECT( EXPIRED );
1576 :
1577 32799 : ord->nonce_expires_at = fd_ulong_if( is_durable_nonce, expires_at, 0UL );
1578 :
1579 32799 : int replaces = 0;
1580 : /* If it's a durable nonce and we already have one, delete one or the
1581 : other. */
1582 32799 : if( FD_UNLIKELY( is_durable_nonce ) ) {
1583 135 : fd_pack_ord_txn_t * same_nonce = noncemap_ele_query( pack->noncemap, txne, NULL, pack->pool );
1584 135 : if( FD_LIKELY( same_nonce ) ) { /* Seems like most nonce transactions are effectively duplicates */
1585 111 : if( FD_LIKELY( same_nonce->root == FD_ORD_TXN_ROOT_PENDING_BUNDLE || (same_nonce->root & FD_ORD_TXN_ROOT_TAG_MASK) == FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( 0 ) ||
1586 111 : same_nonce->nonce_expires_at>expires_at ||
1587 111 : (same_nonce->nonce_expires_at==expires_at && COMPARE_WORSE( ord, same_nonce ) ) ) ) REJECT( NONCE_PRIORITY );
1588 99 : ulong _delete_cnt = delete_transaction( pack, same_nonce, 0, 0 ); /* Not a bundle, so delete_full_bundle is 0 */
1589 99 : *delete_cnt += _delete_cnt;
1590 99 : replaces = 1;
1591 99 : }
1592 : /* Replace the expires_at value with a synthetic one to give nonce
1593 : transactions a finite lifetime. */
1594 123 : expires_at = pack->expire_before + FD_PACK_NONCE_SYNTHETIC_LIFETIME;
1595 123 : }
1596 :
1597 32787 : ord->expires_at = expires_at;
1598 :
1599 32787 : if( FD_UNLIKELY( pack->pending_txn_cnt == pack->pack_depth ) ) {
1600 3156 : float threshold_score = (float)ord->rewards/(float)ord->compute_est;
1601 3156 : ulong _delete_cnt = delete_worst( pack, threshold_score );
1602 3156 : *delete_cnt += _delete_cnt;
1603 3156 : if( FD_UNLIKELY( !_delete_cnt ) ) REJECT( PRIORITY );
1604 3123 : replaces = 1;
1605 3123 : }
1606 :
1607 32754 : ord->txn->flags &= ~(FD_TXN_P_FLAGS_BUNDLE | FD_TXN_P_FLAGS_INITIALIZER_BUNDLE);
1608 32754 : ord->skip = FD_PACK_SKIP_CNT;
1609 :
1610 : /* At this point, we know we have space to insert the transaction and
1611 : we've committed to insert it. */
1612 :
1613 32754 : insert_txn( pack, ord );
1614 :
1615 32754 : pack->pending_txn_cnt++;
1616 :
1617 32754 : sig2txn_ele_insert( pack->signature_map, ord, pack->pool );
1618 :
1619 32754 : if( FD_UNLIKELY( is_durable_nonce ) ) noncemap_ele_insert( pack->noncemap, ord, pack->pool );
1620 :
1621 32754 : fd_pack_expq_t temp[ 1 ] = {{ .expires_at = expires_at, .txn = ord }};
1622 32754 : expq_insert( pack->expiration_q, temp );
1623 :
1624 32754 : return (replaces<<1) | (is_durable_nonce<<2);
1625 32787 : }
1626 : #undef REJECT
1627 :
1628 : fd_txn_e_t * const *
1629 : fd_pack_insert_bundle_init( fd_pack_t * pack,
1630 : fd_txn_e_t * * bundle,
1631 1882965 : ulong txn_cnt ) {
1632 1882965 : FD_TEST( txn_cnt<=FD_PACK_MAX_TXN_PER_BUNDLE );
1633 1882965 : FD_TEST( trp_pool_free( pack->pool )>=txn_cnt );
1634 3767475 : for( ulong i=0UL; i<txn_cnt; i++ ) bundle[ i ] = trp_pool_ele_acquire( pack->pool )->txn_e;
1635 1882965 : return bundle;
1636 1882965 : }
1637 :
1638 : void
1639 : fd_pack_insert_bundle_cancel( fd_pack_t * pack,
1640 : fd_txn_e_t * const * bundle,
1641 261 : ulong txn_cnt ) {
1642 : /* There's no real reason these have to be released in reverse, but it
1643 : seems fitting to release them in the opposite order they were
1644 : acquired. */
1645 1329 : for( ulong i=0UL; i<txn_cnt; i++ ) trp_pool_ele_release( pack->pool, (fd_pack_ord_txn_t*)bundle[ txn_cnt-1UL-i ] );
1646 261 : }
1647 :
1648 : /* Explained below */
1649 : #define BUNDLE_L_PRIME 37896771UL
1650 : #define BUNDLE_N 313721UL
1651 1883475 : #define RC_TO_REL_BUNDLE_IDX( r, c ) (BUNDLE_N - ((ulong)(r) * 1UL<<32)/((ulong)(c) * BUNDLE_L_PRIME))
1652 :
1653 : /* bundle_txn_declared_tip returns the tip that this transaction sends
1654 : to the tip accounts using top-level System program transfers.
1655 :
1656 : This does not include tips paid during CPI calls. */
1657 : static ulong
1658 198 : bundle_txn_declared_tip( fd_pack_ord_txn_t const * ord ) {
1659 198 : fd_txn_t const * txn = TXN( ord->txn );
1660 198 : uchar const * payload = ord->txn->payload;
1661 198 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, payload );
1662 198 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
1663 :
1664 198 : ulong tip = 0UL;
1665 618 : for( ulong i=0UL; i<(ulong)txn->instr_cnt; i++ ) {
1666 420 : fd_txn_instr_t const * instr = txn->instr+i;
1667 420 : uchar const * data = payload + instr->data_off;
1668 420 : if( FD_LIKELY( (instr->data_sz<12) | (instr->acct_cnt<2) || FD_LOAD( uint, data )!=2U ) ) continue;
1669 186 : if( FD_LIKELY( memcmp( accts[ instr->program_id ].b, &(uchar[32]){ 0 }, FD_TXN_ACCT_ADDR_SZ ) ) ) continue;
1670 186 : if( fd_pack_tip_is_tip_account( ACCT_IDX_TO_PTR( payload[ instr->acct_off+1UL ] ) ) ) tip = fd_ulong_sat_add( tip, FD_LOAD( ulong, data+4UL ) );
1671 186 : }
1672 198 : return tip;
1673 198 : }
1674 :
1675 : /* pre_rotation_bundle_worse returns 1 if bundle x has a smaller tip,
1676 : or the same tip but arrived later. */
1677 : static inline int
1678 : pre_rotation_bundle_worse( fd_pack_pre_rotation_bundle_t const * x,
1679 621 : fd_pack_pre_rotation_bundle_t const * y ) {
1680 621 : return (x->tip<y->tip) | ((x->tip==y->tip) & (x->seq>y->seq));
1681 621 : }
1682 :
1683 : static inline ulong
1684 90 : pre_rotation_best_bundle_idx( fd_pack_t const * pack ) {
1685 90 : ulong best = ULONG_MAX;
1686 1530 : for( ulong i=0UL; i<FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY; i++ ) {
1687 1440 : if( !treap_ele_cnt( pack->pre_rotation_bundles[ i ].treap ) ) continue;
1688 468 : if( best==ULONG_MAX || pre_rotation_bundle_worse( pack->pre_rotation_bundles+best, pack->pre_rotation_bundles+i ) ) {
1689 417 : best = i;
1690 417 : }
1691 468 : }
1692 90 : return best;
1693 90 : }
1694 :
1695 : static inline ulong
1696 15 : pre_rotation_worst_bundle_idx( fd_pack_t const * pack ) {
1697 15 : ulong worst = ULONG_MAX;
1698 255 : for( ulong i=0UL; i<FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY; i++ ) {
1699 240 : if( !treap_ele_cnt( pack->pre_rotation_bundles[ i ].treap ) ) continue;
1700 240 : if( worst==ULONG_MAX || pre_rotation_bundle_worse( pack->pre_rotation_bundles+i, pack->pre_rotation_bundles+worst ) ) {
1701 60 : worst = i;
1702 60 : }
1703 240 : }
1704 15 : return worst;
1705 15 : }
1706 :
1707 : static inline void
1708 : pre_rotation_bundle_remove( fd_pack_t * pack,
1709 : fd_pack_pre_rotation_bundle_t * pre_rotation_bundle,
1710 108 : ulong idx ) {
1711 108 : treap_idx_remove( pre_rotation_bundle->treap, idx, pack->pool );
1712 108 : if( !treap_ele_cnt( pre_rotation_bundle->treap ) ) {
1713 96 : pack->pre_rotation_bundle_cnt--;
1714 96 : }
1715 108 : }
1716 :
1717 : int
1718 : fd_pack_insert_bundle_fini( fd_pack_t * pack,
1719 : fd_txn_e_t * const * bundle,
1720 : ulong txn_cnt,
1721 : ulong expires_at,
1722 : int initializer_bundle,
1723 : void const * bundle_meta,
1724 1882965 : ulong * delete_cnt ) {
1725 :
1726 1882965 : int err = 0;
1727 1882965 : *delete_cnt = 0UL;
1728 :
1729 1882965 : ulong pending_b_txn_cnt = treap_ele_cnt( pack->pending_bundles );
1730 1882965 : int is_pre_rotation = (bundle[ 0 ]->txnp->scheduler_arrival_time_nanos>=pack->rotation_end_ns) & (!initializer_bundle);
1731 : /* We want to prevent bundles from consuming the whole treap, but in
1732 : general, we assume bundles are lucrative. We'll set the policy
1733 : on capping bundles at half of the pack depth. We assume that the
1734 : bundles are coming in a pre-prioritized order, so it doesn't make
1735 : sense to drop an earlier bundle for this one. That means that
1736 : really, the best thing to do is drop this one. */
1737 1882965 : if( FD_UNLIKELY( (!initializer_bundle)&(pending_b_txn_cnt+txn_cnt>pack->pack_depth/2UL) ) ) err = FD_PACK_INSERT_REJECT_PRIORITY;
1738 :
1739 1882965 : if( FD_UNLIKELY( expires_at<pack->expire_before ) ) err = FD_PACK_INSERT_REJECT_EXPIRED;
1740 :
1741 : /* Before evicting a transaction in favour of a pre-rotation
1742 : bundle, check that the bundle will actually be inserted into the
1743 : pre-rotation treap: it's valid and has a high enough tip.
1744 :
1745 : Otherwise, we could end up discarding a transaction with a
1746 : duplicate nonce, but because the conflicting bundle didn't
1747 : actually make it into the pre-rotation treap we would have
1748 : discarded the transaction unnecessarily. */
1749 1882965 : ulong pre_rotation_tip = 0UL;
1750 1882965 : fd_pack_pre_rotation_bundle_t cand[ 1 ] = {{ .tip = 0UL, .seq = pack->pre_rotation_seq }};
1751 1882965 : if( FD_UNLIKELY( is_pre_rotation & !err ) ) {
1752 378 : for( ulong i=0UL; i<txn_cnt; i++ ) {
1753 198 : pre_rotation_tip = fd_ulong_sat_add( pre_rotation_tip, bundle_txn_declared_tip( (fd_pack_ord_txn_t *)bundle[ i ] ) );
1754 198 : }
1755 180 : cand->tip = pre_rotation_tip;
1756 180 : if( FD_UNLIKELY( pack->pre_rotation_bundle_cnt>=FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY ) ) {
1757 : /* If we have to evict a pre-rotation bundle from the treap,
1758 : check that the new bundle we are inserting does in fact have a
1759 : higher tip than the lowest already in the treap. */
1760 12 : ulong worst = pre_rotation_worst_bundle_idx( pack );
1761 12 : if( FD_UNLIKELY( !pre_rotation_bundle_worse( pack->pre_rotation_bundles+worst, cand ) ) ) {
1762 9 : FD_MCNT_INC( PACK, PRE_ROTATION_BUNDLE_REJECTED, 1UL );
1763 9 : err = FD_PACK_INSERT_REJECT_PRIORITY;
1764 9 : }
1765 12 : }
1766 180 : }
1767 :
1768 1882965 : int replaces = 0;
1769 1882965 : ulong nonce_txn_cnt = 0UL;
1770 :
1771 : /* Collect nonce hashes to detect duplicate nonces.
1772 : Use a constant-time duplicate-detection algorithm -- Vacant entries
1773 : have the MSB set, occupied entries are the noncemap hash, with the
1774 : MSB set to 0. */
1775 1882965 : ulong nonce_hash63[ FD_PACK_MAX_TXN_PER_BUNDLE ];
1776 11297790 : for( ulong i=0UL; i<FD_PACK_MAX_TXN_PER_BUNDLE; i++ ) {
1777 9414825 : nonce_hash63[ i ] = ULONG_MAX-i;
1778 9414825 : }
1779 :
1780 3767439 : for( ulong i=0UL; (i<txn_cnt) && !err; i++ ) {
1781 1884480 : fd_pack_ord_txn_t * ord = (fd_pack_ord_txn_t *)bundle[ i ];
1782 :
1783 1884480 : fd_txn_t const * txn = TXN(bundle[ i ]->txnp);
1784 1884480 : uchar const * payload = bundle[ i ]->txnp->payload;
1785 :
1786 1884480 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, payload );
1787 1884480 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
1788 :
1789 1884480 : int est_result = fd_pack_estimate_rewards_and_compute( bundle[ i ], ord, pack->lim );
1790 1884480 : if( FD_UNLIKELY( est_result==0 ) ) { err = FD_PACK_INSERT_REJECT_ESTIMATION_FAIL; break; }
1791 1884480 : int nonce_result = fd_pack_validate_durable_nonce( ord->txn_e );
1792 1884480 : if( FD_UNLIKELY( !nonce_result ) ) { err = FD_PACK_INSERT_REJECT_INVALID_NONCE; break; }
1793 : /* The expires_at field is interpreted differently for nonce vs.
1794 : non-nonce transactions, but bundles are required to have the same
1795 : value for that field, so we've lost the value we would put in
1796 : nonce_expires_at. Turns out, that's never read for bundles
1797 : though. So for now, we just use the incorrect expires_at.
1798 : If you're already getting revert protection from being a bundle,
1799 : it seems dumb to use a durable nonce as another form of revert
1800 : protection anyway. We're expecting the sender of the bundles to
1801 : do the nonce filtering anyway. */
1802 1884480 : int is_durable_nonce = nonce_result==2;
1803 1884480 : nonce_txn_cnt += !!is_durable_nonce;
1804 :
1805 1884480 : bundle[ i ]->txnp->flags |= FD_TXN_P_FLAGS_BUNDLE;
1806 1884480 : bundle[ i ]->txnp->flags &= ~(FD_TXN_P_FLAGS_INITIALIZER_BUNDLE | FD_TXN_P_FLAGS_DURABLE_NONCE);
1807 1884480 : bundle[ i ]->txnp->flags |= fd_uint_if( initializer_bundle, FD_TXN_P_FLAGS_INITIALIZER_BUNDLE, 0U );
1808 1884480 : bundle[ i ]->txnp->flags |= fd_uint_if( is_durable_nonce, FD_TXN_P_FLAGS_DURABLE_NONCE, 0U );
1809 1884480 : ord->skip = FD_PACK_SKIP_CNT;
1810 1884480 : ord->expires_at = expires_at;
1811 :
1812 1884480 : if( FD_UNLIKELY( is_durable_nonce ) ) {
1813 1044 : ord->nonce_expires_at = expires_at;
1814 1044 : nonce_hash63[ i ] = noncemap_key_hash( ord->txn_e, pack->noncemap->seed ) & 0x7FFFFFFFFFFFFFFFUL;
1815 1044 : fd_pack_ord_txn_t * same_nonce = noncemap_ele_query( pack->noncemap, ord->txn_e, NULL, pack->pool );
1816 1044 : if( FD_LIKELY( same_nonce ) ) {
1817 : /* bundles take priority over non-bundles, and bundles that run
1818 : sooner take priority over bundles that run later.
1819 :
1820 : Fresh bundles take priority over pre-rotation bundles, and
1821 : pre-rotation bundles with higher tips take priority over
1822 : pre-rotation bundles with lower tips. */
1823 15 : int holder_root = same_nonce->root & FD_ORD_TXN_ROOT_TAG_MASK;
1824 15 : int holder_is_fresh = holder_root==FD_ORD_TXN_ROOT_PENDING_BUNDLE;
1825 15 : int holder_is_pre = holder_root==FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( 0 );
1826 15 : int holder_out_tips = (is_pre_rotation & holder_is_pre) && !pre_rotation_bundle_worse( pack->pre_rotation_bundles + FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE_IDX( same_nonce->root ), cand );
1827 15 : if( FD_UNLIKELY( holder_is_fresh | (holder_is_pre & holder_out_tips) ) ) {
1828 6 : err = FD_PACK_INSERT_REJECT_NONCE_PRIORITY;
1829 6 : break;
1830 9 : } else {
1831 9 : ulong _delete_cnt = delete_transaction( pack, same_nonce, 1, 0 );
1832 9 : *delete_cnt += _delete_cnt;
1833 9 : replaces = 1;
1834 9 : }
1835 15 : }
1836 1044 : }
1837 :
1838 1884474 : int validation_result = validate_transaction( pack, ord, txn, accts, alt, !initializer_bundle );
1839 1884474 : if( FD_UNLIKELY( validation_result ) ) { err = validation_result; break; }
1840 1884474 : }
1841 :
1842 1882965 : if( FD_UNLIKELY( err ) ) {
1843 18 : fd_pack_insert_bundle_cancel( pack, bundle, txn_cnt );
1844 18 : return err;
1845 18 : }
1846 :
1847 1882947 : if( FD_UNLIKELY( initializer_bundle && pending_b_txn_cnt>0UL ) ) {
1848 6 : treap_rev_iter_t _cur=treap_rev_iter_init( pack->pending_bundles, pack->pool );
1849 6 : FD_TEST( !treap_rev_iter_done( _cur ) );
1850 6 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pack->pool );
1851 6 : int is_ib = !!(cur->txn->flags & FD_TXN_P_FLAGS_INITIALIZER_BUNDLE);
1852 :
1853 : /* Delete the previous IB if there is one */
1854 6 : if( FD_UNLIKELY( is_ib && 0UL==RC_TO_REL_BUNDLE_IDX( cur->rewards, cur->compute_est ) ) ) {
1855 6 : ulong _delete_cnt = delete_transaction( pack, cur, 1, 0 );
1856 6 : *delete_cnt += _delete_cnt;
1857 6 : }
1858 6 : }
1859 :
1860 1882947 : while( FD_UNLIKELY( pack->pending_txn_cnt+txn_cnt > pack->pack_depth ) ) {
1861 0 : ulong _delete_cnt = delete_worst( pack, FLT_MAX );
1862 0 : *delete_cnt += _delete_cnt;
1863 0 : if( FD_UNLIKELY( !_delete_cnt ) ) {
1864 0 : fd_pack_insert_bundle_cancel( pack, bundle, txn_cnt );
1865 0 : return FD_PACK_INSERT_REJECT_PRIORITY;
1866 0 : }
1867 0 : replaces = 1;
1868 0 : }
1869 :
1870 1882947 : if( FD_UNLIKELY( !pending_b_txn_cnt ) ) {
1871 681 : pack->relative_bundle_idx = 1UL;
1872 681 : }
1873 :
1874 1882947 : if( FD_LIKELY( bundle_meta ) ) {
1875 0 : memcpy( (uchar *)pack->bundle_meta + (ulong)((fd_pack_ord_txn_t *)bundle[0]-pack->pool)*pack->bundle_meta_sz, bundle_meta, pack->bundle_meta_sz );
1876 0 : }
1877 :
1878 1882947 : if( FD_UNLIKELY( nonce_txn_cnt>1UL ) ) {
1879 : /* Do a ILP-friendly duplicate detect, naive O(n^2) algo. With max
1880 : 5 txns per bundle, this requires 10 comparisons. ~ 25 cycle. */
1881 375 : uint conflict_detected = 0u;
1882 1875 : for( ulong i=0UL; i<FD_PACK_MAX_TXN_PER_BUNDLE-1; i++ ) {
1883 5250 : for( ulong j=i+1; j<FD_PACK_MAX_TXN_PER_BUNDLE; j++ ) {
1884 3750 : ulong const ele_i = nonce_hash63[ i ];
1885 3750 : ulong const ele_j = nonce_hash63[ j ];
1886 3750 : conflict_detected |= (ele_i==ele_j);
1887 3750 : }
1888 1500 : }
1889 375 : if( FD_UNLIKELY( conflict_detected ) ) {
1890 243 : fd_pack_insert_bundle_cancel( pack, bundle, txn_cnt );
1891 243 : return FD_PACK_INSERT_REJECT_NONCE_CONFLICT;
1892 243 : }
1893 375 : }
1894 :
1895 : /* If the bundle is a pre-rotation bundle, insert it into the
1896 : pre-rotation treap. */
1897 1882704 : if( FD_UNLIKELY( is_pre_rotation ) ) {
1898 168 : ulong evicted = insert_pre_rotation_bundle_impl( pack, txn_cnt, (fd_pack_ord_txn_t * *)bundle, expires_at, pre_rotation_tip );
1899 168 : *delete_cnt += evicted;
1900 168 : replaces |= evicted>0UL;
1901 168 : return (0) | (replaces<<1) | ((!!nonce_txn_cnt)<<2);
1902 168 : }
1903 :
1904 : /* We put bundles in a treap just like all the other transactions, but
1905 : we actually want to sort them in a very specific order; the order
1906 : within the bundle is determined at bundle creation time, and the
1907 : order among the bundles is FIFO. However, it's going to be a pain
1908 : to use a different sorting function for this treap, since it's
1909 : fixed as part of the treap creation for performance. Don't fear
1910 : though; we can pull a cool math trick out of the bag to shoehorn
1911 : the order we'd like into the sort function we need, and to get even
1912 : more.
1913 :
1914 : Recall that the sort function is r_i/c_i, smallest to largest,
1915 : where r_i is the rewards and c_i is the cost units. r_i and c_i
1916 : are both uints, and the comparison is done by cross-multiplication
1917 : as ulongs. We actually use the c_i value for testing if
1918 : transactions fit, etc. so let's assume that's fixed, and we know
1919 : it's in the range [1020, 1,551,570].
1920 :
1921 : This means, if c_0, c_1, ... c_4 are the CU costs of the
1922 : transactions in the first bundle, we require r_0/c_0 > r_1/c_1 >
1923 : ... > r_4/c_4. Then, if c_5, ... c_9 are the CU costs of the
1924 : transactions in the second bundle, we also require that r_4/c_4 >
1925 : r_5/c_5. For convenience, we'll impose a slightly stronger
1926 : constraint: we want the kth bundle to obey L*(N-k) <= r_i/c_i <
1927 : L*(N+1-k), for fixed constants L and N, real and integer,
1928 : respectively, that we'll determine. For example, this means r_4/c_4
1929 : >= L*N > r_5/c_5. This enables us to group the transactions in the
1930 : same bundle more easily.
1931 :
1932 : For convenience in the math below, we'll set j=N-k and relabel the
1933 : transactions from the jth bundle c_0, ... c_4.
1934 : From above, we know that Lj <= r_4/c_4. We'd like to make it as
1935 : close as possible given that r_4 is an integers. Thus, put
1936 : r_4 = ceil( c_4 * Lj ). r_4 is clearly an integer, and it satisfies
1937 : the required inequality because:
1938 : r_4/c_4 = ceil( c_4 * Lj)/c_4 >= c_4*Lj / c_4 >= Lj.
1939 :
1940 : Following in the same spirit, put r_3 = ceil( c_3 * (r_4+1)/c_4 ).
1941 : Again, r_3 is clearly an integer, and
1942 : r_3/c_3 = ceil(c_3*(r_4+1)/c_4)/c_3
1943 : >= (c_3*(r_4+1))/(c_3 * c_4)
1944 : >= r_4/c_4 + 1/c_4
1945 : > r_4/c_4.
1946 : Following the pattern, we put
1947 : r_2 = ceil( c_2 * (r_3+1)/c_3 )
1948 : r_1 = ceil( c_1 * (r_2+1)/c_2 )
1949 : r_0 = ceil( c_0 * (r_1+1)/c_1 )
1950 : which work for the same reason that as r_3.
1951 :
1952 : We now need for r_0 to satisfy the final inequality with L, and
1953 : we'll use this to guide our choice of L. Theoretically, r_0 can be
1954 : expressed in terms of L, j, and c_0, ... c_4, but that's a truly
1955 : inscrutible expression. Instead, we need some bounds so we can get
1956 : rid of all the ceil using the property that x <= ceil(x) < x+1.
1957 : c_4 * Lj <= r_4 < c_4 * Lj + 1
1958 : The lower bound on r_3 is easy:
1959 : r_3 >= c_3 * (c_4 * Lj + 1)/c_4 = c_3 * Lj + c_3/c_4
1960 : For the upper bound,
1961 : r_3 < 1 + c_3*(r_4+1)/c_4 < 1 + c_3*(c_4*Lj+1 + 1)/c_4
1962 : = 1 + c_3 * Lj + 2*c_3/c_4
1963 : Continuing similarly gives
1964 : c_2*Lj + c_2/c_3 + c_2/c_4 <= r_2
1965 : c_1*Lj + c_1/c_2 + c_1/c_c + c_1/c_4 <= r_1
1966 : c_0*Lj + c_0/c_1 + c_0/c_2 + c_0/c_3 + c_0/c_4 <= r_0
1967 : and
1968 : r_2 < 1 + c_2*Lj + 2c_2/c_3 + 2c_2/c_4
1969 : r_1 < 1 + c_1*Lj + 2c_1/c_2 + 2c_1/c_3 + 2c_1/c_4
1970 : r_0 < 1 + c_0*Lj + 2c_0/c_1 + 2c_0/c_2 + 2c_0/c_3 + 2c_0/c_4.
1971 :
1972 : Setting L(j+1)>=(1 + c_0*Lj+2c_0/c_1+2c_0/c_2+2c_0/c_3+2c_0/c_4)/c_0
1973 : is then sufficient to ensure the whole sequence of 5 fits between Lj
1974 : and L(j+1). Simplifying gives
1975 : L<= 1/c_0 + 2/c_1 + 2/c_2 + 2/c_3 + 2/c_4
1976 : but L must be a constant and not depend on individual values of c_i,
1977 : so, given that c_i >= 1020, we set L = 9/1020.
1978 :
1979 : Now all that remains is to determine N. It's a bit unfortunate
1980 : that we require N, since it limits our capacity, but it's necessary
1981 : in any system that tries to compute priorities to enforce a FIFO
1982 : order. If we've inserted more than N bundles without ever having
1983 : the bundle treap go empty, we renumber the pending bundles to make
1984 : room, since bundles can't share an ordinal.
1985 :
1986 : Thus, we'd like to make N as big as possible, avoiding overflow.
1987 : r_0, ..., r_4 are all uints, and taking the bounds from above,
1988 : given that for any i, i' c_i/c_{i'} <= 1551570/1020 < 1522, we have
1989 : r_i < 1 + 1551570 * Lj + 8*1522.
1990 : To avoid overflow, we assert the right-hand side is < 2^32, which
1991 : implies N <= 313721.
1992 :
1993 : We want to use a fixed point representation for L so that the
1994 : entire computation can be done with integer arithmetic. We can do
1995 : the arithmetic as ulongs, which means defining L' >= L * 2^s, and
1996 : we compute ceil( c_4*Lj ) as floor( (c_4 * L' * j + 2^s - 1)/2^s ),
1997 : so c_4 * L' * j + 2^s should fit in a ulong. With j<=N, this gives
1998 : s<=32, so we set s=32, which means L' = 37896771 >= 9/1020 * 2^32.
1999 : Note that 1 + 1551570 * L' * N + 8*1522 + 2^32 is approximately
2000 : 2^63.999992.
2001 :
2002 : Note that this is all checked by a proof of the code translated
2003 : into Z3. Unfortunately CBMC was too slow to prove this code
2004 : directly. */
2005 1882536 : FD_STATIC_ASSERT( FD_PACK_MIN_TXN_COST== 1020UL, adjust_constants );
2006 1882536 : FD_STATIC_ASSERT( FD_PACK_MAX_TXN_COST==1551570UL, adjust_constants );
2007 3766224 : #define BUNDLE_L_PRIME 37896771UL
2008 3766224 : #define BUNDLE_N 313721UL
2009 :
2010 1882536 : if( FD_UNLIKELY( pack->relative_bundle_idx>BUNDLE_N ) ) {
2011 : /* Walk worst to best, which is last to first within each bundle.
2012 : Only an initializer bundle has ordinal 0, and it keeps it. */
2013 6 : ulong new_ordinal = pack->relative_bundle_idx = pending_b_txn_cnt+1UL;
2014 6 : ulong old_ordinal = ULONG_MAX;
2015 6 : ulong prev_reward = 0UL;
2016 6 : ulong prev_cost = 0UL;
2017 6 : for( treap_fwd_iter_t _cur=treap_fwd_iter_init( pack->pending_bundles, pack->pool );
2018 147 : !treap_fwd_iter_done( _cur ); _cur=treap_fwd_iter_next( _cur, pack->pool ) ) {
2019 141 : fd_pack_ord_txn_t * cur = treap_fwd_iter_ele( _cur, pack->pool );
2020 141 : ulong this_ordinal = RC_TO_REL_BUNDLE_IDX( cur->rewards, cur->compute_est );
2021 141 : if( this_ordinal!=old_ordinal ) {
2022 45 : old_ordinal = this_ordinal;
2023 45 : prev_reward = BUNDLE_L_PRIME * (BUNDLE_N - (this_ordinal ? --new_ordinal : 0UL)) - 1UL;
2024 45 : prev_cost = 1UL<<32;
2025 45 : }
2026 141 : cur->rewards = (uint)(((ulong)cur->compute_est * (prev_reward + 1UL) + prev_cost-1UL)/prev_cost);
2027 141 : prev_reward = cur->rewards;
2028 141 : prev_cost = cur->compute_est;
2029 141 : }
2030 6 : }
2031 1882536 : ulong bundle_idx = fd_ulong_if( initializer_bundle, 0UL, pack->relative_bundle_idx );
2032 1882536 : insert_bundle_impl( pack, bundle_idx, txn_cnt, (fd_pack_ord_txn_t * *)bundle, expires_at );
2033 : /* if IB this is max( 1, x ), which is x. Otherwise, this is max(x,
2034 : x+1) which is x++ */
2035 1882536 : pack->relative_bundle_idx = fd_ulong_max( bundle_idx+1UL, pack->relative_bundle_idx );
2036 :
2037 1882536 : return (0) | (replaces<<1) | ((!!nonce_txn_cnt)<<2);
2038 1882704 : }
2039 : static inline void
2040 : insert_bundle_impl( fd_pack_t * pack,
2041 : ulong bundle_idx,
2042 : ulong txn_cnt,
2043 : fd_pack_ord_txn_t * * bundle,
2044 1882536 : ulong expires_at ) {
2045 1882536 : ulong prev_reward = ((BUNDLE_L_PRIME * (BUNDLE_N - bundle_idx))) - 1UL;
2046 1882536 : ulong prev_cost = 1UL<<32;
2047 :
2048 : /* Assign last to first */
2049 3765795 : for( ulong i=0UL; i<txn_cnt; i++ ) {
2050 1883259 : fd_pack_ord_txn_t * ord = bundle[ txn_cnt-1UL - i ];
2051 1883259 : ord->rewards = (uint)(((ulong)ord->compute_est * (prev_reward + 1UL) + prev_cost-1UL)/prev_cost);
2052 1883259 : ord->root = FD_ORD_TXN_ROOT_PENDING_BUNDLE;
2053 1883259 : prev_reward = ord->rewards;
2054 1883259 : prev_cost = ord->compute_est;
2055 :
2056 : /* The penalty information isn't used for bundles. */
2057 1883259 : ushort penalties [ FD_TXN_ACCT_ADDR_MAX ];
2058 1883259 : uchar penalty_idx[ FD_TXN_ACCT_ADDR_MAX ];
2059 1883259 : populate_bitsets( pack, ord, penalties, penalty_idx );
2060 :
2061 1883259 : treap_ele_insert( pack->pending_bundles, ord, pack->pool );
2062 1883259 : pack->pending_txn_cnt++;
2063 :
2064 1883259 : if( FD_UNLIKELY( ord->txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE ) ) noncemap_ele_insert( pack->noncemap, ord, pack->pool );
2065 1883259 : sig2txn_ele_insert( pack->signature_map, ord, pack->pool );
2066 :
2067 1883259 : fd_pack_expq_t temp[ 1 ] = {{ .expires_at = expires_at, .txn = ord }};
2068 1883259 : expq_insert( pack->expiration_q, temp );
2069 1883259 : }
2070 :
2071 1882536 : }
2072 :
2073 : /* insert_pre_rotation_bundle_impl is like insert_bundle_impl, but puts
2074 : the bundle in a free entry of pre_rotation_bundles. If none is
2075 : free, it first evicts the worst bundle. Returns the number of txns
2076 : evicted. */
2077 : static inline ulong
2078 : insert_pre_rotation_bundle_impl( fd_pack_t * pack,
2079 : ulong txn_cnt,
2080 : fd_pack_ord_txn_t * * bundle,
2081 : ulong expires_at,
2082 168 : ulong pre_rotation_tip ) {
2083 : /* Evict from the pre-rotation treap if we have reached the limit */
2084 168 : ulong evicted = 0UL;
2085 168 : if( FD_UNLIKELY( pack->pre_rotation_bundle_cnt>=FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY ) ) {
2086 3 : treap_t * worst_treap = pack->pre_rotation_bundles[ pre_rotation_worst_bundle_idx( pack ) ].treap;
2087 3 : fd_pack_ord_txn_t * worst = treap_fwd_iter_ele( treap_fwd_iter_init( worst_treap, pack->pool ), pack->pool );
2088 3 : evicted = delete_transaction( pack, worst, 1, 0 );
2089 3 : FD_MCNT_INC( PACK, PRE_ROTATION_BUNDLE_EVICTED, 1UL );
2090 3 : }
2091 :
2092 168 : ulong pre_rotation_bundle_idx = 0UL;
2093 939 : while( treap_ele_cnt( pack->pre_rotation_bundles[ pre_rotation_bundle_idx ].treap ) ) {
2094 771 : pre_rotation_bundle_idx++;
2095 771 : }
2096 168 : fd_pack_pre_rotation_bundle_t * pre_rotation_bundle = pack->pre_rotation_bundles + pre_rotation_bundle_idx;
2097 168 : pre_rotation_bundle->tip = pre_rotation_tip;
2098 168 : pre_rotation_bundle->seq = pack->pre_rotation_seq++;
2099 :
2100 168 : ulong prev_reward = ((BUNDLE_L_PRIME * (BUNDLE_N - 1UL))) - 1UL;
2101 168 : ulong prev_cost = 1UL<<32;
2102 :
2103 : /* Assign last to first */
2104 351 : for( ulong i=0UL; i<txn_cnt; i++ ) {
2105 183 : fd_pack_ord_txn_t * ord = bundle[ txn_cnt-1UL - i ];
2106 183 : ord->rewards = (uint)(((ulong)ord->compute_est * (prev_reward + 1UL) + prev_cost-1UL)/prev_cost);
2107 183 : ord->root = FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( (int)pre_rotation_bundle_idx );
2108 183 : prev_reward = ord->rewards;
2109 183 : prev_cost = ord->compute_est;
2110 :
2111 : /* The penalty information isn't used for bundles. */
2112 183 : ushort penalties [ FD_TXN_ACCT_ADDR_MAX ];
2113 183 : uchar penalty_idx[ FD_TXN_ACCT_ADDR_MAX ];
2114 183 : populate_bitsets( pack, ord, penalties, penalty_idx );
2115 :
2116 183 : treap_ele_insert( pre_rotation_bundle->treap, ord, pack->pool );
2117 183 : pack->pending_txn_cnt++;
2118 :
2119 183 : if( FD_UNLIKELY( ord->txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE ) ) noncemap_ele_insert( pack->noncemap, ord, pack->pool );
2120 183 : sig2txn_ele_insert( pack->signature_map, ord, pack->pool );
2121 :
2122 183 : fd_pack_expq_t temp[ 1 ] = {{ .expires_at = expires_at, .txn = ord }};
2123 183 : expq_insert( pack->expiration_q, temp );
2124 183 : }
2125 :
2126 168 : pack->pre_rotation_bundle_cnt++;
2127 168 : FD_MCNT_INC( PACK, PRE_ROTATION_BUNDLE_INSERTED, 1UL );
2128 168 : return evicted;
2129 168 : }
2130 :
2131 : void const *
2132 6 : fd_pack_peek_bundle_meta( fd_pack_t const * pack ) {
2133 6 : int ib_state = pack->initializer_bundle_state;
2134 6 : if( FD_UNLIKELY( (ib_state==FD_PACK_IB_STATE_PENDING) | (ib_state==FD_PACK_IB_STATE_FAILED) ) ) return NULL;
2135 :
2136 6 : treap_rev_iter_t _cur=treap_rev_iter_init( pack->pending_bundles, pack->pool );
2137 : /* If there are no normal bundles, the pre-rotation bundles will
2138 : be scheduled. */
2139 6 : if( FD_UNLIKELY( treap_rev_iter_done( _cur ) ) ) {
2140 3 : ulong best = pre_rotation_best_bundle_idx( pack );
2141 3 : if( FD_UNLIKELY( best==ULONG_MAX ) ) return NULL;
2142 3 : _cur = treap_rev_iter_init( pack->pre_rotation_bundles[ best ].treap, pack->pool );
2143 3 : }
2144 6 : if( FD_UNLIKELY( treap_rev_iter_done( _cur ) ) ) return NULL; /* empty */
2145 :
2146 6 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pack->pool );
2147 6 : int is_ib = !!(cur->txn->flags & FD_TXN_P_FLAGS_INITIALIZER_BUNDLE);
2148 6 : if( FD_UNLIKELY( is_ib ) ) return NULL;
2149 :
2150 3 : return (void const *)((uchar const *)pack->bundle_meta + (ulong)_cur * pack->bundle_meta_sz);
2151 6 : }
2152 :
2153 : void
2154 162 : fd_pack_set_initializer_bundles_ready( fd_pack_t * pack ) {
2155 162 : pack->initializer_bundle_state = FD_PACK_IB_STATE_READY;
2156 162 : }
2157 :
2158 : void
2159 : fd_pack_set_rotation_end_ns( fd_pack_t * pack,
2160 624 : long end_ns ) {
2161 624 : pack->rotation_end_ns = end_ns;
2162 624 : }
2163 :
2164 : void
2165 63 : fd_pack_metrics_write( fd_pack_t const * pack ) {
2166 63 : ulong pending_regular = treap_ele_cnt( pack->pending );
2167 63 : ulong pending_bundle = treap_ele_cnt( pack->pending_bundles );
2168 1071 : for( ulong i=0UL; i<FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY; i++ ) {
2169 1008 : pending_bundle += treap_ele_cnt( pack->pre_rotation_bundles[ i ].treap );
2170 1008 : }
2171 63 : ulong pending_pre_rotation = pack->pre_rotation_bundle_cnt;
2172 63 : ulong next_auction = treap_ele_cnt( pack->next_auction );
2173 63 : ulong conflicting = pack->pending_txn_cnt - pending_regular - pending_bundle - next_auction;
2174 63 : ulong smallest_cost = fd_ulong_if( pack->pending_smallest->cus==ULONG_MAX, 0UL, pack->pending_smallest->cus );
2175 63 : FD_MGAUGE_SET( PACK, TXN_PENDING_USED_REGULAR, pending_regular );
2176 63 : FD_MGAUGE_SET( PACK, TXN_PENDING_USED_VOTE, 0UL );
2177 63 : FD_MGAUGE_SET( PACK, TXN_PENDING_USED_CONFLICTING, conflicting );
2178 63 : FD_MGAUGE_SET( PACK, TXN_PENDING_USED_BUNDLE, pending_bundle );
2179 63 : FD_MGAUGE_SET( PACK, TXN_PENDING_USED_NEXT_AUCTION, next_auction );
2180 63 : FD_MGAUGE_SET( PACK, PRE_ROTATION_BUNDLE_PENDING, pending_pre_rotation );
2181 63 : FD_MGAUGE_SET( PACK, TXN_PENDING_SMALLEST_COST, smallest_cost );
2182 63 : FD_MGAUGE_SET( PACK, BLOCK_COST, pack->cumulative_block_cost );
2183 :
2184 63 : FD_MCNT_ENUM_COPY( PACK, TXN_SCHEDULE_ATTEMPTED, pack->sched_results );
2185 63 : }
2186 :
2187 : void
2188 0 : fd_pack_get_sched_metrics( fd_pack_t const * pack, ulong * metrics ) {
2189 0 : fd_memcpy( metrics, pack->sched_results, sizeof(pack->sched_results) );
2190 0 : }
2191 :
2192 : typedef struct {
2193 : ushort clear_rw_bit;
2194 : ushort clear_w_bit;
2195 : } release_result_t;
2196 :
2197 : static inline release_result_t
2198 : release_bit_reference( fd_pack_t * pack,
2199 3921195 : fd_acct_addr_t const * acct ) {
2200 :
2201 3921195 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, *acct, NULL );
2202 3921195 : FD_TEST( q ); /* q==NULL not be possible */
2203 :
2204 3921195 : q->ref_cnt--;
2205 :
2206 3921195 : if( FD_UNLIKELY( q->ref_cnt==0UL ) ) {
2207 1957501 : ushort bit = q->bit;
2208 1957501 : bitset_map_remove( pack->acct_to_bitset, q );
2209 1957501 : if( FD_LIKELY( bit<FD_PACK_BITSET_MAX ) ) pack->bitset_avail[ ++(pack->bitset_avail_cnt) ] = bit;
2210 :
2211 1957501 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, *acct, NULL );
2212 1957501 : if( FD_LIKELY( use ) ) {
2213 69886 : use->in_use_by |= FD_PACK_IN_USE_BIT_CLEARED;
2214 69886 : release_result_t ret = { .clear_rw_bit = bit,
2215 69886 : .clear_w_bit = fd_ushort_if( !!(use->in_use_by & FD_PACK_IN_USE_WRITABLE), bit, FD_PACK_BITSET_MAX ) };
2216 69886 : return ret;
2217 69886 : }
2218 1957501 : }
2219 3851309 : release_result_t ret = { .clear_rw_bit = FD_PACK_BITSET_MAX, .clear_w_bit = FD_PACK_BITSET_MAX };
2220 3851309 : return ret;
2221 3921195 : }
2222 :
2223 : typedef struct {
2224 : ulong cus_scheduled;
2225 : ulong txns_scheduled;
2226 : ulong bytes_scheduled;
2227 : ulong alloc_scheduled;
2228 : } sched_return_t;
2229 :
2230 : static inline sched_return_t
2231 : fd_pack_schedule_impl( fd_pack_t * pack,
2232 : treap_t * sched_from,
2233 : ulong cu_limit,
2234 : ulong txn_limit,
2235 : ulong byte_limit,
2236 : ulong alloc_limit,
2237 : ulong bank_tile,
2238 : fd_pack_smallest_t * smallest_in_treap,
2239 : ulong * use_by_bank_txn,
2240 14850 : fd_txn_e_t * out ) {
2241 14850 : if( FD_UNLIKELY( (cu_limit<smallest_in_treap->cus) | (txn_limit==0UL) | (byte_limit<smallest_in_treap->bytes) ) ) {
2242 176 : sched_return_t to_return = { .cus_scheduled = 0UL, .txns_scheduled = 0UL, .bytes_scheduled = 0UL };
2243 176 : return to_return;
2244 176 : }
2245 :
2246 14674 : fd_pack_ord_txn_t * pool = pack->pool;
2247 14674 : fd_pack_addr_use_t * acct_in_use = pack->acct_in_use;
2248 14674 : wcost_map_t * writer_costs = pack->writer_costs;
2249 14674 : fd_pack_wcost_ele_t * writers = pack->writers;
2250 14674 : wcost_dlist_t * written_list = pack->written_list;
2251 :
2252 14674 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
2253 14674 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
2254 14674 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
2255 14674 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
2256 :
2257 14674 : fd_pack_addr_use_t * use_by_bank = pack->use_by_bank [bank_tile];
2258 14674 : ulong use_by_bank_cnt = pack->use_by_bank_cnt[bank_tile];
2259 :
2260 14674 : ulong max_write_cost_per_acct = pack->lim->max_write_cost_per_acct;
2261 :
2262 14674 : ushort compressed_slot_number = pack->compressed_slot_number;
2263 :
2264 14674 : ulong txns_scheduled = 0UL;
2265 14674 : ulong cus_scheduled = 0UL;
2266 14674 : ulong bytes_scheduled = 0UL;
2267 14674 : ulong alloc_scheduled = 0UL;
2268 :
2269 14674 : ulong bank_tile_mask = 1UL << bank_tile;
2270 :
2271 14674 : ulong fast_path = 0UL;
2272 14674 : ulong slow_path = 0UL;
2273 14674 : ulong cu_limit_c = 0UL;
2274 14674 : ulong byte_limit_c = 0UL;
2275 14674 : ulong alloc_limit_c = 0UL;
2276 14674 : ulong write_limit_c = 0UL;
2277 14674 : ulong skip_c = 0UL;
2278 :
2279 14674 : ulong min_cus = ULONG_MAX;
2280 14674 : ulong min_bytes = ULONG_MAX;
2281 :
2282 14674 : treap_rev_iter_t prev = treap_idx_null();
2283 240768 : for( treap_rev_iter_t _cur=treap_rev_iter_init( sched_from, pool ); !treap_rev_iter_done( _cur ); _cur=prev ) {
2284 : /* Capture next so that we can delete while we iterate. */
2285 228907 : prev = treap_rev_iter_next( _cur, pool );
2286 :
2287 228907 : # if FD_HAS_X86
2288 228907 : _mm_prefetch( &(pool[ prev ].prev), _MM_HINT_T0 );
2289 228907 : # endif
2290 :
2291 228907 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pool );
2292 :
2293 228907 : min_cus = fd_ulong_min( min_cus, cur->compute_est );
2294 228907 : min_bytes = fd_ulong_min( min_bytes, cur->txn->payload_sz );
2295 :
2296 228907 : ulong conflicts = 0UL;
2297 :
2298 228907 : if( FD_UNLIKELY( cur->compute_est>cu_limit ) ) {
2299 : /* Too big to be scheduled at the moment, but might be okay for
2300 : the next microblock, so we don't want to delay it. */
2301 0 : cu_limit_c++;
2302 0 : continue;
2303 0 : }
2304 :
2305 228907 : if( FD_UNLIKELY( cur->txn->pack_alloc>alloc_limit ) ) {
2306 : /* We don't want to consider this until the next block, but
2307 : checking alloc is as cheap as checking cur->skip, so there's
2308 : not a big difference. */
2309 18 : alloc_limit_c++;
2310 18 : continue;
2311 18 : }
2312 :
2313 : /* Likely? Unlikely? */
2314 228889 : if( FD_LIKELY( !FD_PACK_BITSET_INTERSECT4_EMPTY( bitset_rw_in_use, bitset_w_in_use, cur->w_bitset, cur->rw_bitset ) ) ) {
2315 202795 : fast_path++;
2316 202795 : continue;
2317 202795 : }
2318 :
2319 26094 : if( FD_UNLIKELY( cur->skip==compressed_slot_number ) ) {
2320 0 : skip_c++;
2321 0 : continue;
2322 0 : }
2323 :
2324 : /* If skip>FD_PACK_MAX_SKIP but not compressed_slot_number, it means
2325 : it's the compressed slot number of a previous slot. We don't
2326 : care unless we're going to update the value though, so we don't
2327 : need to eagerly reset it to FD_PACK_MAX_SKIP.
2328 : compressed_slot_number is a ushort, so it's possible for it to
2329 : roll over, but the transaction lifetime is much shorter than
2330 : that, so it won't be a problem. */
2331 :
2332 26094 : if( FD_UNLIKELY( cur->txn->payload_sz>byte_limit ) ) {
2333 6 : byte_limit_c++;
2334 6 : continue;
2335 6 : }
2336 :
2337 :
2338 26088 : fd_txn_t const * txn = TXN(cur->txn);
2339 26088 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
2340 26088 : fd_acct_addr_t const * alt = cur->txn_e->alt_accts;
2341 : /* Check conflicts between this transaction's writable accounts and
2342 : current readers */
2343 26088 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
2344 84414 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2345 :
2346 58329 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
2347 :
2348 58329 : fd_pack_wcost_ele_t const * in_wcost_table = wcost_map_ele_query_const( writer_costs, &acct, NULL, writers );
2349 58329 : if( FD_UNLIKELY( in_wcost_table && in_wcost_table->total_cost+cur->compute_est > max_write_cost_per_acct ) ) {
2350 : /* Can't be scheduled until the next block */
2351 3 : conflicts = ULONG_MAX;
2352 3 : break;
2353 3 : }
2354 :
2355 58326 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, acct, NULL );
2356 58326 : if( FD_UNLIKELY( use ) ) conflicts |= use->in_use_by; /* break? */
2357 58326 : }
2358 :
2359 26088 : if( FD_UNLIKELY( conflicts==ULONG_MAX ) ) {
2360 : /* The logic for how to adjust skip is a bit complicated, and we
2361 : want to do it branchlessly. Let psc=FD_PACK_SKIP_CNT,
2362 : Before After
2363 : 1 compressed_slot_number
2364 : x in [2, psc] x-1
2365 : x where x>psc psc-1
2366 :
2367 : Set A=min(x, 5), B=min(A-2, compressed_slot_number-1), and
2368 : note that compressed_slot_number is in [psc+1, USHORT_MAX].
2369 : Then:
2370 : x A A-2 B B+1
2371 : 1 1 USHORT_MAX csn-1 csn
2372 : x in [2, psc] x x-2 x-2 x-1
2373 : x where x>psc psc psc-2 psc-2 psc-1
2374 : So B+1 is the desired value. */
2375 3 : cur->skip = (ushort)(1+fd_ushort_min( (ushort)(compressed_slot_number-1),
2376 3 : (ushort)(fd_ushort_min( cur->skip, FD_PACK_SKIP_CNT )-2) ) );
2377 3 : write_limit_c++;
2378 3 : continue;
2379 3 : }
2380 :
2381 26085 : if( FD_UNLIKELY( conflicts ) ) {
2382 6 : slow_path++;
2383 6 : continue;
2384 6 : }
2385 :
2386 : /* Check conflicts between this transaction's readonly accounts and
2387 : current writers */
2388 26079 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
2389 119094 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2390 :
2391 93015 : fd_acct_addr_t const * acct = ACCT_ITER_TO_PTR( iter );
2392 93015 : if( fd_pack_unwritable_contains( acct ) ) continue; /* No need to track sysvars because they can't be writable */
2393 :
2394 65142 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, *acct, NULL );
2395 65142 : if( use ) conflicts |= (use->in_use_by & FD_PACK_IN_USE_WRITABLE) ? use->in_use_by : 0UL;
2396 65142 : }
2397 :
2398 26079 : if( FD_UNLIKELY( conflicts ) ) {
2399 0 : slow_path++;
2400 0 : continue;
2401 0 : }
2402 :
2403 : /* Include this transaction in the microblock! */
2404 26079 : FD_PACK_BITSET_OR( bitset_rw_in_use, cur->rw_bitset );
2405 26079 : FD_PACK_BITSET_OR( bitset_w_in_use, cur->w_bitset );
2406 :
2407 26079 : fd_txn_p_t * out_txnp = out->txnp;
2408 26079 : if( FD_LIKELY( cur->txn->payload_sz>=1024UL ) ) pack_memcpy_out( out_txnp->payload, cur->txn->payload, cur->txn->payload_sz );
2409 13287 : else fd_memcpy ( out_txnp->payload, cur->txn->payload, cur->txn->payload_sz );
2410 :
2411 26079 : out_txnp->payload_sz = cur->txn->payload_sz;
2412 26079 : out_txnp->pack_cu.requested_exec_plus_acct_data_cus = cur->txn->pack_cu.requested_exec_plus_acct_data_cus;
2413 26079 : out_txnp->pack_cu.non_execution_cus = cur->txn->pack_cu.non_execution_cus;
2414 26079 : out_txnp->pack_alloc = cur->txn->pack_alloc;
2415 26079 : out_txnp->scheduler_arrival_time_nanos = cur->txn->scheduler_arrival_time_nanos;
2416 26079 : out_txnp->first_seen_nanos = cur->txn->first_seen_nanos;
2417 26079 : out_txnp->source_tpu = cur->txn->source_tpu;
2418 26079 : out_txnp->source_ipv4 = cur->txn->source_ipv4;
2419 26079 : out_txnp->flags = cur->txn->flags;
2420 26079 : fd_memcpy( TXN(out_txnp), txn, fd_txn_footprint( txn->instr_cnt, txn->addr_table_lookup_cnt ) );
2421 :
2422 : /* Copy the ALT accounts from the source fd_txn_e_t */
2423 26079 : ulong alt_acct_cnt = (ulong)txn->addr_table_adtl_cnt;
2424 26079 : if( FD_UNLIKELY( alt_acct_cnt ) ) pack_memcpy_out( out->alt_accts, cur->txn_e->alt_accts, alt_acct_cnt*sizeof(fd_acct_addr_t) );
2425 26079 : out++;
2426 :
2427 26079 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
2428 84390 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2429 58311 : fd_acct_addr_t acct_addr = *ACCT_ITER_TO_PTR( iter );
2430 :
2431 58311 : fd_pack_wcost_ele_t * in_wcost_table = wcost_map_ele_query( writer_costs, &acct_addr, NULL, writers );
2432 58311 : if( !in_wcost_table ) {
2433 11020 : in_wcost_table = wcost_pool_ele_acquire( writers );
2434 11020 : in_wcost_table->key = acct_addr;
2435 11020 : in_wcost_table->total_cost = 0UL;
2436 11020 : wcost_map_ele_insert ( writer_costs, in_wcost_table, writers );
2437 11020 : wcost_dlist_ele_push_tail( written_list, in_wcost_table, writers );
2438 11020 : }
2439 58311 : in_wcost_table->total_cost += cur->compute_est;
2440 :
2441 58311 : fd_pack_addr_use_t * use = acct_uses_insert( acct_in_use, acct_addr );
2442 58311 : use->in_use_by = bank_tile_mask | FD_PACK_IN_USE_WRITABLE;
2443 :
2444 58311 : use_by_bank[use_by_bank_cnt++] = *use;
2445 :
2446 : /* If there aren't any more references to this account in the
2447 : heap, it can't cause any conflicts. That means we actually
2448 : don't need to record that we are using it, which is good
2449 : because we want to release the bit. */
2450 58311 : release_result_t ret = release_bit_reference( pack, &acct_addr );
2451 58311 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
2452 58311 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
2453 58311 : }
2454 26079 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
2455 119094 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2456 :
2457 93015 : fd_acct_addr_t acct_addr = *ACCT_ITER_TO_PTR( iter );
2458 :
2459 93015 : if( fd_pack_unwritable_contains( &acct_addr ) ) continue; /* No need to track sysvars because they can't be writable */
2460 :
2461 65142 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, acct_addr, NULL );
2462 65142 : if( !use ) { use = acct_uses_insert( acct_in_use, acct_addr ); use->in_use_by = 0UL; }
2463 :
2464 65142 : if( !(use->in_use_by & bank_tile_mask) ) use_by_bank[use_by_bank_cnt++] = *use;
2465 65142 : use->in_use_by |= bank_tile_mask;
2466 65142 : use->in_use_by &= ~FD_PACK_IN_USE_BIT_CLEARED;
2467 :
2468 :
2469 65142 : release_result_t ret = release_bit_reference( pack, &acct_addr );
2470 65142 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
2471 65142 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
2472 65142 : }
2473 :
2474 26079 : txns_scheduled += 1UL; txn_limit -= 1UL;
2475 26079 : cus_scheduled += cur->compute_est; cu_limit -= cur->compute_est;
2476 26079 : bytes_scheduled += cur->txn->payload_sz; byte_limit -= cur->txn->payload_sz;
2477 26079 : alloc_scheduled += cur->txn->pack_alloc; alloc_limit -= cur->txn->pack_alloc;
2478 :
2479 26079 : *(use_by_bank_txn++) = use_by_bank_cnt;
2480 :
2481 26079 : if( FD_UNLIKELY( cur->txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE ) ) noncemap_ele_remove_fast( pack->noncemap, cur, pack->pool );
2482 26079 : sig2txn_ele_remove_fast( pack->signature_map, cur, pool );
2483 :
2484 26079 : cur->root = FD_ORD_TXN_ROOT_FREE;
2485 26079 : expq_remove( pack->expiration_q, cur->expq_idx );
2486 26079 : treap_idx_remove( sched_from, _cur, pool );
2487 26079 : trp_pool_idx_release( pool, _cur );
2488 26079 : pack->pending_txn_cnt--;
2489 :
2490 26079 : if( FD_UNLIKELY( (cu_limit<smallest_in_treap->cus) | (txn_limit==0UL) | (byte_limit<smallest_in_treap->bytes) ) ) break;
2491 26079 : }
2492 :
2493 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_TAKEN_IDX ] += txns_scheduled;
2494 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CU_LIMIT_IDX ] += cu_limit_c;
2495 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CONFLICT_FAST_IDX ] += fast_path;
2496 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_BYTE_LIMIT_IDX ] += byte_limit_c;
2497 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_ALLOC_LIMIT_IDX ] += alloc_limit_c;
2498 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_WRITE_COST_IDX ] += write_limit_c;
2499 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CONFLICT_SLOW_IDX ] += slow_path;
2500 14674 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_WRITE_COST_DEFERRED_IDX ] += skip_c;
2501 :
2502 : /* If we scanned the whole treap and didn't break early, we now have a
2503 : better estimate of the smallest. */
2504 14674 : if( FD_UNLIKELY( treap_rev_iter_done( prev ) ) ) {
2505 14405 : smallest_in_treap->cus = min_cus;
2506 14405 : smallest_in_treap->bytes = min_bytes;
2507 14405 : }
2508 :
2509 14674 : pack->use_by_bank_cnt[bank_tile] = use_by_bank_cnt;
2510 14674 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
2511 14674 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
2512 :
2513 14674 : sched_return_t to_return = { .cus_scheduled=cus_scheduled, .txns_scheduled=txns_scheduled,
2514 14674 : .bytes_scheduled=bytes_scheduled, .alloc_scheduled=alloc_scheduled };
2515 14674 : return to_return;
2516 14850 : }
2517 :
2518 : int
2519 : fd_pack_microblock_complete( fd_pack_t * pack,
2520 14988 : ulong bank_tile ) {
2521 : /* If the account is in use writably, and it's in use by this banking
2522 : tile, then this banking tile must be the sole writer to it, so it's
2523 : always okay to clear the writable bit. */
2524 14988 : ulong clear_mask = ~((1UL<<bank_tile) | FD_PACK_IN_USE_WRITABLE);
2525 :
2526 : /* If nothing outstanding, bail quickly */
2527 14988 : if( FD_UNLIKELY( !(pack->outstanding_microblock_mask & (1UL<<bank_tile)) ) ) return 0;
2528 :
2529 8719 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
2530 8719 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
2531 8719 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
2532 8719 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
2533 :
2534 8719 : fd_pack_addr_use_t * base = pack->use_by_bank[bank_tile];
2535 :
2536 8719 : fd_pack_ord_txn_t * best = NULL;
2537 8719 : fd_pack_penalty_treap_t * best_penalty = NULL;
2538 8719 : ulong txn_cnt = 0UL;
2539 :
2540 113963 : for( ulong i=0UL; i<pack->use_by_bank_cnt[bank_tile]; i++ ) {
2541 105244 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, base[i].key, NULL );
2542 105244 : FD_TEST( use );
2543 105244 : use->in_use_by &= clear_mask;
2544 :
2545 : /* In order to properly bound the size of bitset_map, we need to
2546 : release the "reference" to the account when we schedule it.
2547 : However, that poses a bit of a problem here, because by the time
2548 : we complete the microblock, that account could have been assigned
2549 : a different bit in the bitset. The scheduling step tells us if
2550 : that is the case, and if so, we know that the bits in
2551 : bitset_w_in_use and bitset_rw_in_use were already cleared as
2552 : necessary.
2553 :
2554 : Note that it's possible for BIT_CLEARED to be set and then unset
2555 : by later uses, but then the account would be in use on other
2556 : banks, so we wouldn't try to observe the old value. For example:
2557 : Suppose bit 0->account A, bit 1->account B, and we have two
2558 : transactions that read A, B. We schedule a microblock to bank 0,
2559 : taking both transactions, which sets the counts for A, B to 0,
2560 : and releases the bits, clearing bits 0 and 1, and setting
2561 : BIT_CLEARED. Then we get two more transactions that read
2562 : accounts C, D, A, B, and they get assigned 0->C, 1->D, 2->A,
2563 : 3->B. We try to schedule a microblock to bank 1 that takes one
2564 : of those transactions. This unsets BIT_CLEARED for A, B.
2565 : Finally, the first microblock completes. Even though the bitset
2566 : map has the new bits for A and B which are "wrong" compared to
2567 : when the transaction was initially scheduled, those bits have
2568 : already been cleared and reset properly in the bitset as needed.
2569 : A and B will still be in use by bank 1, so we won't clear any
2570 : bits. If, on the other hand, the microblock scheduled to bank 1
2571 : completes first, bits 0 and 1 will be cleared for accounts C and
2572 : D, while bits 2 and 3 will remain set, which is correct. Then
2573 : when bank 0 completes, bits 2 and 3 will be cleared. */
2574 105244 : if( FD_LIKELY( !use->in_use_by ) ) { /* if in_use_by==0, doesn't include BIT_CLEARED */
2575 39552 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, base[i].key, NULL );
2576 39552 : FD_TEST( q );
2577 39552 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, q->bit );
2578 39552 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, q->bit );
2579 :
2580 : /* Because this account is no longer in use, it might be possible
2581 : to schedule a transaction that writes to it. Check its
2582 : penalty treap if it has one, and potentially move it to the
2583 : main treap. */
2584 39552 : fd_pack_penalty_treap_t * p_trp = penalty_map_query( pack->penalty_treaps, base[i].key, NULL );
2585 39552 : if( FD_UNLIKELY( p_trp ) ) {
2586 5507 : fd_pack_ord_txn_t * best_in_trp = treap_rev_iter_ele( treap_rev_iter_init( p_trp->penalty_treap, pack->pool ), pack->pool );
2587 5507 : if( FD_UNLIKELY( !best || COMPARE_WORSE( best, best_in_trp ) ) ) {
2588 2806 : best = best_in_trp;
2589 2806 : best_penalty = p_trp;
2590 2806 : }
2591 5507 : }
2592 39552 : }
2593 :
2594 105244 : if( FD_LIKELY( !(use->in_use_by & ~FD_PACK_IN_USE_BIT_CLEARED) ) ) acct_uses_remove( pack->acct_in_use, use );
2595 :
2596 105244 : if( FD_UNLIKELY( i+1UL==pack->use_by_bank_txn[ bank_tile ][ txn_cnt ] ) ) {
2597 25473 : txn_cnt++;
2598 25473 : if( FD_LIKELY( best ) ) {
2599 : /* move best to the main treap */
2600 2806 : treap_ele_remove( best_penalty->penalty_treap, best, pack->pool );
2601 2806 : best->root = FD_ORD_TXN_ROOT_PENDING;
2602 2806 : treap_ele_insert( pack->pending, best, pack->pool );
2603 :
2604 2806 : pack->pending_smallest->cus = fd_ulong_min( pack->pending_smallest->cus, best->compute_est );
2605 2806 : pack->pending_smallest->bytes = fd_ulong_min( pack->pending_smallest->bytes, best->txn_e->txnp->payload_sz );
2606 :
2607 2806 : if( FD_UNLIKELY( !treap_ele_cnt( best_penalty->penalty_treap ) ) ) {
2608 12 : treap_delete( treap_leave( best_penalty->penalty_treap ) );
2609 : /* Removal invalidates any pointers we got from
2610 : penalty_map_query, but we immediately set these to NULL, so
2611 : we're not keeping any pointers around. */
2612 12 : penalty_map_remove( pack->penalty_treaps, best_penalty );
2613 12 : }
2614 2806 : best = NULL;
2615 2806 : best_penalty = NULL;
2616 2806 : }
2617 25473 : }
2618 105244 : }
2619 :
2620 8719 : pack->use_by_bank_cnt[bank_tile] = 0UL;
2621 :
2622 8719 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
2623 8719 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
2624 :
2625 : /* outstanding_microblock_mask never has the writable bit set, so we
2626 : don't care about clearing it here either. */
2627 8719 : pack->outstanding_microblock_mask &= clear_mask;
2628 8719 : return 1;
2629 8719 : }
2630 :
2631 14859 : #define TRY_BUNDLE_NO_READY_BUNDLES 0
2632 261 : #define TRY_BUNDLE_HAS_CONFLICTS (-1)
2633 261 : #define TRY_BUNDLE_DOES_NOT_FIT (-2)
2634 261 : #define TRY_BUNDLE_SUCCESS(n) ( n) /* schedule bundle with n transactions */
2635 : static inline int
2636 : fd_pack_try_schedule_bundle( fd_pack_t * pack,
2637 : ulong bank_tile,
2638 15120 : fd_txn_e_t * out ) {
2639 15120 : int state = pack->initializer_bundle_state;
2640 15120 : if( FD_UNLIKELY( (state==FD_PACK_IB_STATE_PENDING) | (state==FD_PACK_IB_STATE_FAILED ) ) ) return TRY_BUNDLE_NO_READY_BUNDLES;
2641 :
2642 15117 : fd_pack_ord_txn_t * pool = pack->pool;
2643 15117 : treap_t * bundles = pack->pending_bundles;
2644 :
2645 15117 : int require_ib;
2646 15117 : if( FD_UNLIKELY( state==FD_PACK_IB_STATE_NOT_INITIALIZED ) ) { require_ib = 1; }
2647 15117 : if( FD_LIKELY ( state==FD_PACK_IB_STATE_READY ) ) { require_ib = 0; }
2648 :
2649 15117 : treap_rev_iter_t _cur = treap_rev_iter_init( bundles, pool );
2650 15117 : ulong bundle_idx = ULONG_MAX;
2651 :
2652 : /* Skip any that we've marked as won't fit in this block */
2653 15117 : while( FD_UNLIKELY( !treap_rev_iter_done( _cur ) && treap_rev_iter_ele( _cur, pool )->skip==pack->compressed_slot_number ) ) {
2654 0 : _cur = treap_rev_iter_next( _cur, pool );
2655 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_WRITE_COST_DEFERRED_IDX ]++;
2656 0 : }
2657 :
2658 : /* If there are no normal bundles to run, then fall back to the
2659 : pre-rotation treap. This is because fresh bundles usually don't
2660 : arrive exactly at the start of our leader rotation, so whilst we
2661 : are waiting for fresh bundles we should try the pre-rotation ones. */
2662 15117 : int is_pre_rotation = 0;
2663 15117 : fd_pack_pre_rotation_bundle_t * pre_rotation_bundle = NULL;
2664 15117 : if( FD_UNLIKELY( treap_rev_iter_done( _cur ) ) ) {
2665 14817 : if( FD_UNLIKELY( require_ib ) ) return TRY_BUNDLE_NO_READY_BUNDLES;
2666 87 : is_pre_rotation = 1;
2667 87 : ulong best = pre_rotation_best_bundle_idx( pack );
2668 87 : if( FD_UNLIKELY( best==ULONG_MAX ) ) return TRY_BUNDLE_NO_READY_BUNDLES;
2669 81 : pre_rotation_bundle = pack->pre_rotation_bundles + best;
2670 81 : _cur = treap_rev_iter_init( pre_rotation_bundle->treap, pool );
2671 81 : }
2672 :
2673 381 : if( FD_UNLIKELY( treap_rev_iter_done( _cur ) ) ) return TRY_BUNDLE_NO_READY_BUNDLES;
2674 :
2675 381 : treap_rev_iter_t _txn0 = _cur;
2676 381 : fd_pack_ord_txn_t * txn0 = treap_rev_iter_ele( _txn0, pool );
2677 381 : int is_ib = !!(txn0->txn->flags & FD_TXN_P_FLAGS_INITIALIZER_BUNDLE);
2678 381 : bundle_idx = RC_TO_REL_BUNDLE_IDX( txn0->rewards, txn0->compute_est );
2679 :
2680 381 : if( FD_UNLIKELY( require_ib & !is_ib ) ) return TRY_BUNDLE_NO_READY_BUNDLES;
2681 :
2682 : /* At this point, we have our candidate bundle, so we'll schedule it
2683 : if we can. If we can't, we won't schedule anything. */
2684 :
2685 :
2686 261 : fd_pack_addr_use_t * bundle_temp_inserted[ FD_PACK_MAX_TXN_PER_BUNDLE * FD_TXN_ACCT_ADDR_MAX ];
2687 261 : ulong bundle_temp_inserted_cnt = 0UL;
2688 :
2689 261 : ulong bank_tile_mask = 1UL << bank_tile;
2690 :
2691 261 : int doesnt_fit = 0;
2692 261 : int has_conflict = 0;
2693 261 : ulong txn_cnt = 0UL;
2694 :
2695 261 : ulong cu_limit = pack->lim->max_cost_per_block - pack->cumulative_block_cost;
2696 261 : ulong byte_limit = pack->lim->max_data_bytes_per_block - pack->data_bytes_consumed;
2697 261 : ulong microblock_limit = pack->lim->max_microblocks_per_block - pack->microblock_cnt;
2698 261 : ulong alloc_limit = pack->lim->max_allocated_data_per_block - pack->alloc_consumed;
2699 :
2700 261 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
2701 261 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
2702 261 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
2703 261 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
2704 :
2705 : /* last_use_in_txn_cnt[i+1] Keeps track of the number of accounts that
2706 : have their last reference in transaction i of the bundle. This
2707 : esoteric value is important for computing use_by_bank_txn.
2708 : last_use_in_txn_cnt[0] is garbage. */
2709 261 : ulong last_use_in_txn_cnt[ 1UL+FD_PACK_MAX_TXN_PER_BUNDLE ] = { 0UL };
2710 :
2711 261 : fd_pack_addr_use_t null_use[1] = {{{{ 0 }}, { 0 }}};
2712 261 : fd_pack_wcost_ele_t null_wcost[1] = { 0 };
2713 :
2714 819 : while( !(doesnt_fit | has_conflict) & !treap_rev_iter_done( _cur ) ) {
2715 591 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pool );
2716 591 : ulong this_bundle_idx = RC_TO_REL_BUNDLE_IDX( cur->rewards, cur->compute_est );
2717 591 : if( FD_UNLIKELY( this_bundle_idx!=bundle_idx ) ) break;
2718 :
2719 561 : if( FD_UNLIKELY( cur->compute_est>cu_limit ) ) {
2720 0 : doesnt_fit = 1;
2721 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CU_LIMIT_IDX ]++;
2722 0 : break;
2723 0 : }
2724 561 : cu_limit -= cur->compute_est;
2725 :
2726 : /* Each transaction in a bundle turns into a microblock */
2727 561 : if( FD_UNLIKELY( microblock_limit==0UL ) ) {
2728 0 : doesnt_fit = 1;
2729 0 : FD_MCNT_INC( PACK, BLOCK_MICROBLOCK_LIMIT_REACHED, 1UL );
2730 0 : break;
2731 0 : }
2732 561 : microblock_limit--;
2733 :
2734 561 : if( FD_UNLIKELY( cur->txn->payload_sz+MICROBLOCK_DATA_OVERHEAD>byte_limit ) ) {
2735 0 : doesnt_fit = 1;
2736 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_BYTE_LIMIT_IDX ]++;
2737 0 : break;
2738 0 : }
2739 561 : byte_limit -= cur->txn->payload_sz + MICROBLOCK_DATA_OVERHEAD;
2740 :
2741 561 : if( FD_UNLIKELY( cur->txn->pack_alloc>alloc_limit ) ) {
2742 0 : doesnt_fit = 1;
2743 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_ALLOC_LIMIT_IDX ]++;
2744 0 : break;
2745 0 : }
2746 561 : alloc_limit -= cur->txn->pack_alloc;
2747 :
2748 561 : if( FD_UNLIKELY( !FD_PACK_BITSET_INTERSECT4_EMPTY( pack->bitset_rw_in_use, pack->bitset_w_in_use, cur->w_bitset, cur->rw_bitset ) ) ) {
2749 0 : has_conflict = 1;
2750 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CONFLICT_FAST_IDX ]++;
2751 0 : break;
2752 0 : }
2753 :
2754 : /* Don't update the actual in-use bitset, because the transactions
2755 : in the bundle are allowed to conflict with each other. */
2756 561 : FD_PACK_BITSET_OR( bitset_rw_in_use, cur->rw_bitset );
2757 561 : FD_PACK_BITSET_OR( bitset_w_in_use, cur->w_bitset );
2758 :
2759 :
2760 561 : fd_txn_t const * txn = TXN(cur->txn);
2761 561 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
2762 561 : fd_acct_addr_t const * alt = cur->txn_e->alt_accts;
2763 :
2764 : /* Check conflicts between this transaction's writable accounts and
2765 : current readers */
2766 561 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
2767 1773 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2768 :
2769 1215 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
2770 :
2771 1215 : fd_pack_addr_use_t * in_bundle_temp = acct_uses_query ( pack->bundle_temp_map, acct, null_use );
2772 1215 : ulong current_cost = wcost_map_ele_query_const( pack->writer_costs, &acct, null_wcost, pack->writers )->total_cost;
2773 1215 : ulong carried_cost = (ulong)in_bundle_temp->carried_cost;
2774 1215 : if( FD_UNLIKELY( current_cost + carried_cost + cur->compute_est > pack->lim->max_write_cost_per_acct ) ) {
2775 0 : doesnt_fit = 1;
2776 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_WRITE_COST_IDX ]++;
2777 0 : break;
2778 0 : }
2779 :
2780 1215 : if( FD_LIKELY( in_bundle_temp==null_use ) ) { /* Not in temp bundle table yet */
2781 1155 : in_bundle_temp = acct_uses_insert( pack->bundle_temp_map, acct );
2782 1155 : in_bundle_temp->_ = 0UL;
2783 1155 : bundle_temp_inserted[ bundle_temp_inserted_cnt++ ] = in_bundle_temp;
2784 1155 : }
2785 1215 : in_bundle_temp->carried_cost += (uint)cur->compute_est; /* < 2^21, but >0 */
2786 1215 : in_bundle_temp->ref_cnt++;
2787 1215 : last_use_in_txn_cnt[ in_bundle_temp->last_use_in ]--;
2788 1215 : in_bundle_temp->last_use_in = (ushort)(txn_cnt+1UL);
2789 1215 : last_use_in_txn_cnt[ in_bundle_temp->last_use_in ]++;
2790 :
2791 1215 : if( FD_UNLIKELY( acct_uses_query( pack->acct_in_use, acct, null_use )->in_use_by ) ) {
2792 3 : has_conflict = 1;
2793 3 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CONFLICT_SLOW_IDX ]++;
2794 3 : break;
2795 3 : }
2796 1215 : }
2797 561 : if( has_conflict | doesnt_fit ) break;
2798 :
2799 : /* Check conflicts between this transaction's readonly accounts and
2800 : current writers */
2801 558 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
2802 2661 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2803 :
2804 2103 : fd_acct_addr_t const * acct = ACCT_ITER_TO_PTR( iter );
2805 2103 : if( fd_pack_unwritable_contains( acct ) ) continue; /* No need to track sysvars because they can't be writable */
2806 :
2807 1401 : fd_pack_addr_use_t * in_bundle_temp = acct_uses_query( pack->bundle_temp_map, *acct, null_use );
2808 1401 : if( FD_LIKELY( in_bundle_temp==null_use ) ) { /* Not in temp bundle table yet */
2809 1080 : in_bundle_temp = acct_uses_insert( pack->bundle_temp_map, *acct );
2810 1080 : in_bundle_temp->_ = 0UL;
2811 1080 : bundle_temp_inserted[ bundle_temp_inserted_cnt++ ] = in_bundle_temp;
2812 1080 : }
2813 1401 : in_bundle_temp->ref_cnt++;
2814 1401 : last_use_in_txn_cnt[ in_bundle_temp->last_use_in ]--;
2815 1401 : in_bundle_temp->last_use_in = (ushort)(txn_cnt+1UL);
2816 1401 : last_use_in_txn_cnt[ in_bundle_temp->last_use_in ]++;
2817 :
2818 1401 : if( FD_UNLIKELY( acct_uses_query( pack->acct_in_use, *acct, null_use )->in_use_by & FD_PACK_IN_USE_WRITABLE ) ) {
2819 0 : has_conflict = 1;
2820 0 : pack->sched_results[ FD_METRICS_ENUM_PACK_TXN_SCHEDULE_RESULT_V_CONFLICT_SLOW_IDX ]++;
2821 0 : break;
2822 0 : }
2823 1401 : }
2824 :
2825 558 : if( has_conflict | doesnt_fit ) break;
2826 :
2827 558 : txn_cnt++;
2828 558 : _cur = treap_rev_iter_next( _cur, pool );
2829 558 : }
2830 261 : int retval = fd_int_if( doesnt_fit, TRY_BUNDLE_DOES_NOT_FIT,
2831 261 : fd_int_if( has_conflict, TRY_BUNDLE_HAS_CONFLICTS, TRY_BUNDLE_SUCCESS( (int)txn_cnt ) ) );
2832 :
2833 261 : if( FD_UNLIKELY( retval<=0 ) ) {
2834 9 : for( ulong i=0UL; i<bundle_temp_inserted_cnt; i++ ) {
2835 6 : acct_uses_remove( pack->bundle_temp_map, bundle_temp_inserted[ bundle_temp_inserted_cnt-i-1UL ] );
2836 6 : }
2837 3 : FD_TEST( acct_uses_key_cnt( pack->bundle_temp_map )==0UL );
2838 :
2839 3 : if( FD_UNLIKELY( retval==TRY_BUNDLE_DOES_NOT_FIT ) ) {
2840 : /* Decrement the skip count for the bundle we just tried. */
2841 :
2842 0 : for( _cur=_txn0; !treap_rev_iter_done( _cur ); _cur=treap_rev_iter_next( _cur, pool ) ) {
2843 0 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pool );
2844 0 : ulong this_bundle_idx = RC_TO_REL_BUNDLE_IDX( cur->rewards, cur->compute_est );
2845 0 : if( FD_UNLIKELY( this_bundle_idx!=bundle_idx ) ) break;
2846 :
2847 : /* See fd_pack_schedule_impl for this line */
2848 0 : cur->skip = (ushort)(1+fd_ushort_min( (ushort)(pack->compressed_slot_number-1),
2849 0 : (ushort)(fd_ushort_min( cur->skip, FD_PACK_SKIP_CNT )-2) ) );
2850 0 : }
2851 0 : }
2852 3 : return retval;
2853 3 : }
2854 :
2855 : /* This bundle passed validation, so now we'll take it! */
2856 258 : pack->outstanding_microblock_mask |= bank_tile_mask;
2857 258 : FD_MCNT_INC( PACK, PRE_ROTATION_BUNDLE_SCHEDULED, (ulong)is_pre_rotation );
2858 :
2859 258 : treap_rev_iter_t _end = _cur;
2860 258 : treap_rev_iter_t _next;
2861 :
2862 : /* We'll carefully incrementally construct use_by_bank and
2863 : use_by_bank_txn based on the contents of bundle_temp and
2864 : last_use_in_txn_cnt. */
2865 258 : fd_pack_addr_use_t * use_by_bank = pack->use_by_bank [bank_tile];
2866 258 : ulong * use_by_bank_txn = pack->use_by_bank_txn[bank_tile];
2867 258 : ulong cum_sum = 0UL;
2868 816 : for( ulong k=0UL; k<txn_cnt; k++ ) { use_by_bank_txn[k] = cum_sum; cum_sum += last_use_in_txn_cnt[ k+1UL ]; }
2869 258 : pack->use_by_bank_cnt[bank_tile] = cum_sum;
2870 :
2871 :
2872 816 : for( _cur=_txn0; _cur!=_end; _cur=_next ) {
2873 558 : _next = treap_rev_iter_next( _cur, pool );
2874 :
2875 558 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pool );
2876 558 : fd_txn_t const * txn = TXN(cur->txn);
2877 558 : fd_txn_p_t * out_txnp = out->txnp;
2878 558 : if( FD_LIKELY( cur->txn->payload_sz>=1024UL ) ) pack_memcpy_out( out_txnp->payload, cur->txn->payload, cur->txn->payload_sz );
2879 198 : else fd_memcpy ( out_txnp->payload, cur->txn->payload, cur->txn->payload_sz );
2880 558 : fd_memcpy( TXN(out_txnp), txn, fd_txn_footprint( txn->instr_cnt, txn->addr_table_lookup_cnt ) );
2881 558 : out_txnp->payload_sz = cur->txn->payload_sz;
2882 558 : out_txnp->pack_cu.requested_exec_plus_acct_data_cus = cur->txn->pack_cu.requested_exec_plus_acct_data_cus;
2883 558 : out_txnp->pack_cu.non_execution_cus = cur->txn->pack_cu.non_execution_cus;
2884 558 : out_txnp->pack_alloc = cur->txn->pack_alloc;
2885 558 : out_txnp->scheduler_arrival_time_nanos = cur->txn->scheduler_arrival_time_nanos;
2886 558 : out_txnp->first_seen_nanos = cur->txn->first_seen_nanos;
2887 558 : out_txnp->source_tpu = cur->txn->source_tpu;
2888 558 : out_txnp->source_ipv4 = cur->txn->source_ipv4;
2889 558 : out_txnp->flags = cur->txn->flags;
2890 : /* Copy the ALT accounts from the source fd_txn_e_t */
2891 558 : ulong alt_acct_cnt = (ulong)txn->addr_table_adtl_cnt;
2892 558 : if( FD_UNLIKELY( alt_acct_cnt ) ) pack_memcpy_out( out->alt_accts, cur->txn_e->alt_accts, alt_acct_cnt*sizeof(fd_acct_addr_t) );
2893 558 : out++;
2894 :
2895 558 : pack->cumulative_block_cost += cur->compute_est;
2896 558 : pack->data_bytes_consumed += cur->txn->payload_sz + MICROBLOCK_DATA_OVERHEAD;
2897 558 : pack->alloc_consumed += cur->txn->pack_alloc;
2898 558 : pack->microblock_cnt += 1UL;
2899 :
2900 558 : if( FD_UNLIKELY( cur->txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE ) ) noncemap_ele_remove_fast( pack->noncemap, cur, pack->pool );
2901 558 : sig2txn_ele_remove_fast( pack->signature_map, cur, pack->pool );
2902 :
2903 558 : cur->root = FD_ORD_TXN_ROOT_FREE;
2904 558 : expq_remove( pack->expiration_q, cur->expq_idx );
2905 558 : if( FD_UNLIKELY( is_pre_rotation ) ) pre_rotation_bundle_remove( pack, pre_rotation_bundle, _cur );
2906 474 : else treap_idx_remove( pack->pending_bundles, _cur, pack->pool );
2907 558 : trp_pool_idx_release( pack->pool, _cur );
2908 558 : pack->pending_txn_cnt--;
2909 558 : }
2910 :
2911 :
2912 2487 : for( ulong i=0UL; i<bundle_temp_inserted_cnt; i++ ) {
2913 : /* In order to clear bundle_temp_map with the typical trick, we need
2914 : to iterate through bundle_temp_inserted backwards. */
2915 2229 : fd_pack_addr_use_t * addr_use = bundle_temp_inserted[ bundle_temp_inserted_cnt-i-1UL ];
2916 :
2917 2229 : int any_writers = addr_use->carried_cost>0U; /* Did any transaction in this bundle write lock this account address? */
2918 :
2919 2229 : if( FD_LIKELY( any_writers ) ) { /* UNLIKELY? */
2920 1149 : fd_pack_wcost_ele_t * in_wcost_table = wcost_map_ele_query( pack->writer_costs, &addr_use->key, NULL, pack->writers );
2921 1149 : if( !in_wcost_table ) {
2922 1053 : in_wcost_table = wcost_pool_ele_acquire( pack->writers );
2923 1053 : in_wcost_table->key = addr_use->key;
2924 1053 : in_wcost_table->total_cost = 0UL;
2925 1053 : wcost_map_ele_insert ( pack->writer_costs, in_wcost_table, pack->writers );
2926 1053 : wcost_dlist_ele_push_tail( pack->written_list, in_wcost_table, pack->writers );
2927 1053 : }
2928 1149 : in_wcost_table->total_cost += (ulong)addr_use->carried_cost;
2929 1149 : }
2930 :
2931 : /* in_use_by must be set before releasing the bit reference */
2932 2229 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, addr_use->key, NULL );
2933 2229 : if( !use ) { use = acct_uses_insert( pack->acct_in_use, addr_use->key ); use->in_use_by = 0UL; }
2934 2229 : use->in_use_by |= bank_tile_mask | fd_ulong_if( any_writers, FD_PACK_IN_USE_WRITABLE, 0UL );
2935 2229 : use->in_use_by &= ~FD_PACK_IN_USE_BIT_CLEARED;
2936 :
2937 2229 : use_by_bank[ use_by_bank_txn[ addr_use->last_use_in-1UL ]++ ] = *use;
2938 :
2939 4839 : for( ulong k=0UL; k<(ulong)addr_use->ref_cnt; k++ ) {
2940 2610 : release_result_t ret = release_bit_reference( pack, &(addr_use->key) );
2941 2610 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
2942 2610 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
2943 2610 : }
2944 :
2945 2229 : acct_uses_remove( pack->bundle_temp_map, addr_use );
2946 2229 : }
2947 :
2948 258 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
2949 258 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
2950 :
2951 258 : if( FD_UNLIKELY( is_ib ) ) {
2952 6 : pack->initializer_bundle_state = FD_PACK_IB_STATE_PENDING;
2953 6 : }
2954 258 : pack_memcpy_fini();
2955 258 : return retval;
2956 261 : }
2957 :
2958 :
2959 : ulong
2960 : fd_pack_schedule_next_microblock( fd_pack_t * pack,
2961 : ulong total_cus,
2962 : ulong bank_tile,
2963 : int schedule_flags,
2964 15243 : fd_txn_e_t * out ) {
2965 :
2966 : /* TODO: Decide if these are exactly how we want to handle limits */
2967 15243 : total_cus = fd_ulong_min( total_cus, pack->lim->max_cost_per_block - pack->cumulative_block_cost );
2968 :
2969 15243 : if( FD_UNLIKELY( (pack->microblock_cnt>=pack->lim->max_microblocks_per_block) ) ) {
2970 0 : FD_MCNT_INC( PACK, BLOCK_MICROBLOCK_LIMIT_REACHED, 1UL );
2971 0 : return 0UL;
2972 0 : }
2973 15243 : if( FD_UNLIKELY( pack->data_bytes_consumed+MICROBLOCK_DATA_OVERHEAD+FD_TXN_MIN_SERIALIZED_SZ>pack->lim->max_data_bytes_per_block) ) {
2974 0 : FD_MCNT_INC( PACK, BLOCK_BYTE_LIMIT_REACHED, 1UL );
2975 0 : return 0UL;
2976 0 : }
2977 :
2978 15243 : ulong * use_by_bank_txn = pack->use_by_bank_txn[ bank_tile ];
2979 :
2980 15243 : #if FD_HAS_X86
2981 : /* out is a cold dcache chunk. Its payload is streamed, but the
2982 : metadata and TXN() lines are regular stores; start those reads for
2983 : ownership under the scheduling work. */
2984 15243 : _mm_prefetch( (uchar *)out+FD_TPU_MTU, _MM_HINT_ET0 );
2985 15243 : _mm_prefetch( (uchar *)out+FD_TPU_MTU+ 64UL, _MM_HINT_ET0 );
2986 15243 : _mm_prefetch( (uchar *)out+FD_TPU_MTU+128UL, _MM_HINT_ET0 );
2987 15243 : #endif
2988 :
2989 15243 : ulong cu_limit = total_cus;
2990 15243 : ulong txn_limit = pack->lim->max_txn_per_microblock;
2991 15243 : ulong scheduled = 0UL;
2992 15243 : ulong byte_limit = pack->lim->max_data_bytes_per_block - pack->data_bytes_consumed - MICROBLOCK_DATA_OVERHEAD;
2993 15243 : ulong alloc_limit = pack->lim->max_allocated_data_per_block - pack->alloc_consumed;
2994 :
2995 15243 : sched_return_t status = {0};
2996 :
2997 15243 : if( FD_UNLIKELY( schedule_flags & FD_PACK_SCHEDULE_BUNDLE ) ) {
2998 15120 : int bundle_result = fd_pack_try_schedule_bundle( pack, bank_tile, out );
2999 15120 : if( FD_UNLIKELY( bundle_result>0 ) ) return (ulong)bundle_result;
3000 14862 : if( FD_UNLIKELY( bundle_result==TRY_BUNDLE_HAS_CONFLICTS ) ) return 0UL;
3001 : /* in the NO_READY_BUNDLES or DOES_NOT_FIT case, we schedule like
3002 : normal. */
3003 : /* We have the early returns here because try_schedule_bundle does
3004 : the bookkeeping internally, since the calculations are a bit
3005 : different in that case. */
3006 14862 : }
3007 :
3008 :
3009 : /* Fill the microblock with transactions, votes included */
3010 14982 : if( FD_LIKELY( schedule_flags & FD_PACK_SCHEDULE_TXN ) ) {
3011 14850 : status = fd_pack_schedule_impl( pack, pack->pending, cu_limit, txn_limit, byte_limit, alloc_limit, bank_tile,
3012 14850 : pack->pending_smallest, use_by_bank_txn, out+scheduled );
3013 :
3014 14850 : scheduled += status.txns_scheduled;
3015 14850 : pack->cumulative_block_cost += status.cus_scheduled;
3016 14850 : pack->data_bytes_consumed += status.bytes_scheduled;
3017 14850 : pack->alloc_consumed += status.alloc_scheduled;
3018 14850 : }
3019 :
3020 14982 : ulong nonempty = (ulong)(scheduled>0UL);
3021 14982 : pack->microblock_cnt += nonempty;
3022 14982 : pack->outstanding_microblock_mask |= nonempty << bank_tile;
3023 14982 : pack->data_bytes_consumed += nonempty * MICROBLOCK_DATA_OVERHEAD;
3024 :
3025 14982 : fd_histf_sample( pack->txn_per_microblock, scheduled );
3026 :
3027 14982 : pack_memcpy_fini();
3028 14982 : return scheduled;
3029 15243 : }
3030 :
3031 274398 : ulong fd_pack_bank_tile_cnt ( fd_pack_t const * pack ) { return pack->bank_tile_cnt; }
3032 0 : ulong fd_pack_current_block_cost ( fd_pack_t const * pack ) { return pack->cumulative_block_cost; }
3033 15 : ulong fd_pack_next_auction_txn_cnt( fd_pack_t const * pack ) { return treap_ele_cnt( pack->next_auction ); }
3034 0 : int fd_pack_auction_running ( fd_pack_t const * pack ) { return pack->auction_running; }
3035 :
3036 : /* fd_pack_auction_begin doesn't actually move any transactions
3037 : between treaps. It just sets the auction_running flag, which means
3038 : that new transactions enter the next_auction treap instead of the
3039 : pending/penalty treaps. These are not eligible for scheduling until
3040 : the auction ends, at which point the transactions in the
3041 : next_auction treap are moved into the pending/penalty treaps.
3042 :
3043 : Transactions already in the pending/penalty treaps, as well as all
3044 : new and already received bundles, are still elegible for scheduling
3045 : throughout the auction period. */
3046 : void
3047 6 : fd_pack_auction_begin( fd_pack_t * pack ) {
3048 6 : pack->auction_running = 1;
3049 6 : }
3050 :
3051 : /* fd_pack_auction_end ends an auction, if there was one running. It
3052 : moves every transaction that was held in next_auction to the
3053 : pending/penalty treaps, making them eligible for scheduling. */
3054 : void
3055 6 : fd_pack_auction_end( fd_pack_t * pack ) {
3056 6 : pack->auction_running = 0;
3057 :
3058 : /* Flush the next_auction treap, as we now hold these transactions
3059 : in either the pending treap or the appropriate penalty treap.
3060 : Note that these won't be executed until the start of the next
3061 : auction. */
3062 6 : fd_pack_ord_txn_t * pool = pack->pool;
3063 6 : treap_rev_iter_t next;
3064 9 : for( treap_rev_iter_t cur=treap_rev_iter_init( pack->next_auction, pool ); !treap_rev_iter_done( cur ); cur=next ) {
3065 3 : next = treap_rev_iter_next( cur, pool );
3066 3 : treap_idx_remove( pack->next_auction, treap_rev_iter_idx( cur ), pool );
3067 3 : insert_txn( pack, treap_rev_iter_ele( cur, pool ) );
3068 3 : }
3069 6 : }
3070 :
3071 :
3072 : void
3073 0 : fd_pack_set_block_limits( fd_pack_t * pack, fd_pack_limits_t const * limits ) {
3074 0 : FD_TEST( limits->max_cost_per_block >= FD_PACK_MAX_COST_PER_BLOCK_LOWER_BOUND );
3075 0 : FD_TEST( limits->max_write_cost_per_acct >= FD_PACK_MAX_WRITE_COST_PER_ACCT_LOWER_BOUND );
3076 :
3077 0 : pack->lim->max_microblocks_per_block = limits->max_microblocks_per_block;
3078 0 : pack->lim->max_data_bytes_per_block = limits->max_data_bytes_per_block;
3079 0 : pack->lim->max_cost_per_block = limits->max_cost_per_block;
3080 0 : pack->lim->max_write_cost_per_acct = limits->max_write_cost_per_acct;
3081 0 : pack->lim->max_allocated_data_per_block = limits->max_allocated_data_per_block;
3082 0 : }
3083 :
3084 : void
3085 0 : fd_pack_get_block_limits( fd_pack_t * pack, fd_pack_limits_usage_t * opt_limits_usage, fd_pack_limits_t * opt_limits ) {
3086 0 : if( FD_LIKELY( opt_limits_usage ) ) {
3087 0 : opt_limits_usage->block_cost = pack->cumulative_block_cost;
3088 0 : opt_limits_usage->block_data_bytes = pack->data_bytes_consumed;
3089 0 : opt_limits_usage->microblocks = pack->microblock_cnt;
3090 0 : opt_limits_usage->alloc = pack->alloc_consumed;
3091 0 : }
3092 0 : if( FD_LIKELY( opt_limits ) ) fd_memcpy( opt_limits, pack->lim, sizeof(fd_pack_limits_t) );
3093 0 : }
3094 :
3095 : void
3096 0 : fd_pack_get_top_writers( fd_pack_t const * pack, fd_pack_addr_use_t top_writers[static FD_PACK_TOP_WRITERS_CNT] ) {
3097 0 : fd_memcpy( top_writers, pack->top_writers, sizeof(pack->top_writers) );
3098 0 : }
3099 :
3100 : void
3101 0 : fd_pack_get_pending_smallest( fd_pack_t * pack, fd_pack_smallest_t * opt_pending_smallest ) {
3102 0 : if( FD_LIKELY( opt_pending_smallest ) ) fd_memcpy( opt_pending_smallest, pack->pending_smallest, sizeof(fd_pack_smallest_t) );
3103 0 : }
3104 :
3105 : void
3106 : fd_pack_rebate_cus( fd_pack_t * pack,
3107 9 : fd_pack_rebate_t const * rebate ) {
3108 9 : if( FD_UNLIKELY( (rebate->ib_result!=0) & (pack->initializer_bundle_state==FD_PACK_IB_STATE_PENDING ) ) ) {
3109 3 : pack->initializer_bundle_state = fd_int_if( rebate->ib_result==1, FD_PACK_IB_STATE_READY, FD_PACK_IB_STATE_FAILED );
3110 3 : }
3111 :
3112 9 : pack->cumulative_block_cost -= rebate->total_cost_rebate;
3113 9 : pack->data_bytes_consumed -= rebate->data_bytes_rebate;
3114 9 : pack->alloc_consumed -= rebate->alloc_rebate;
3115 9 : pack->cumulative_rebated_cus += rebate->total_cost_rebate;
3116 : /* For now, we want to ignore the microblock count rebate. There are
3117 : 3 places the microblock count is kept (here, in the pack tile, and
3118 : in the PoH tile), and they all need to count microblocks that end
3119 : up being empty in the same way. It would be better from a
3120 : DoS-resistance perspective for them all not to count empty
3121 : microblocks towards the total, but there's a race condition:
3122 : suppose pack schedules a microblock containing one transaction that
3123 : doesn't land on chain, the slot ends, and then pack informs PoH of
3124 : the number of microblocks before the final rebate comes through.
3125 : This isn't unsolvable, but it's pretty gross, so it's probably
3126 : better to just not apply the rebate for now. */
3127 9 : (void)rebate->microblock_cnt_rebate;
3128 :
3129 9 : wcost_map_t * writer_costs = pack->writer_costs;
3130 21 : for( ulong i=0UL; i<rebate->writer_cnt; i++ ) {
3131 12 : fd_pack_wcost_ele_t * in_wcost_table = wcost_map_ele_query( writer_costs, &rebate->writer_rebates[i].key, NULL, pack->writers );
3132 12 : if( FD_UNLIKELY( !in_wcost_table ) ) FD_LOG_ERR(( "Rebate to unknown written account" ));
3133 12 : in_wcost_table->total_cost -= rebate->writer_rebates[i].rebate_cus;
3134 : /* If the rebate drops it to zero, return it to the pool */
3135 12 : if( FD_UNLIKELY( !in_wcost_table->total_cost ) ) {
3136 3 : wcost_map_ele_remove_fast( writer_costs, in_wcost_table, pack->writers );
3137 3 : wcost_dlist_ele_remove ( pack->written_list, in_wcost_table, pack->writers );
3138 3 : wcost_pool_ele_release ( pack->writers, in_wcost_table );
3139 3 : }
3140 12 : }
3141 9 : }
3142 :
3143 :
3144 : ulong
3145 : fd_pack_expire_before( fd_pack_t * pack,
3146 27 : ulong expire_before ) {
3147 27 : expire_before = fd_ulong_max( expire_before, pack->expire_before );
3148 27 : ulong deleted_cnt = 0UL;
3149 27 : fd_pack_expq_t * prq = pack->expiration_q;
3150 354 : while( (expq_cnt( prq )>0UL) & (prq->expires_at<expire_before) ) {
3151 327 : fd_pack_ord_txn_t * expired = prq->txn;
3152 :
3153 : /* fd_pack_delete_transaction also removes it from the heap */
3154 : /* All the transactions in the same bundle have the same expiration
3155 : time, so this loop will end up deleting them all, even with
3156 : delete_full_bundle set to 0. */
3157 327 : ulong _delete_cnt = delete_transaction( pack, expired, 0, 1 );
3158 327 : deleted_cnt += _delete_cnt;
3159 327 : FD_TEST( _delete_cnt );
3160 327 : }
3161 :
3162 27 : pack->expire_before = expire_before;
3163 27 : return deleted_cnt;
3164 27 : }
3165 :
3166 : void
3167 12 : fd_pack_end_block( fd_pack_t * pack ) {
3168 : /* rounded division */
3169 12 : ulong pct_cus_per_block = (pack->cumulative_block_cost*100UL + (pack->lim->max_cost_per_block>>1))/pack->lim->max_cost_per_block;
3170 12 : fd_histf_sample( pack->pct_cus_per_block, pct_cus_per_block );
3171 12 : fd_histf_sample( pack->net_cus_per_block, pack->cumulative_block_cost );
3172 12 : fd_histf_sample( pack->rebated_cus_per_block, pack->cumulative_rebated_cus );
3173 12 : fd_histf_sample( pack->scheduled_cus_per_block, pack->cumulative_rebated_cus + pack->cumulative_block_cost );
3174 :
3175 12 : pack->microblock_cnt = 0UL;
3176 12 : pack->data_bytes_consumed = 0UL;
3177 12 : pack->cumulative_block_cost = 0UL;
3178 12 : pack->cumulative_rebated_cus = 0UL;
3179 12 : pack->outstanding_microblock_mask = 0UL;
3180 12 : pack->alloc_consumed = 0UL;
3181 :
3182 12 : pack->initializer_bundle_state = FD_PACK_IB_STATE_NOT_INITIALIZED;
3183 :
3184 12 : acct_uses_clear( pack->acct_in_use );
3185 12 : memset( pack->top_writers, 0, sizeof(pack->top_writers) );
3186 :
3187 12 : fd_pack_addr_use_t * last_top_writer = pack->top_writers + FD_PACK_TOP_WRITERS_CNT-1UL;
3188 :
3189 4836 : while( !wcost_dlist_is_empty( pack->written_list, pack->writers ) ) {
3190 4824 : fd_pack_wcost_ele_t * writer = wcost_dlist_ele_pop_head( pack->written_list, pack->writers );
3191 4824 : if( FD_UNLIKELY( writer->total_cost>last_top_writer->total_cost ) ) {
3192 66 : last_top_writer->key = writer->key;
3193 66 : last_top_writer->total_cost = writer->total_cost;
3194 66 : fd_pack_writer_cost_sort_insert( pack->top_writers, FD_PACK_TOP_WRITERS_CNT );
3195 66 : }
3196 : /* Clearing the cost field here is unnecessary (since it gets
3197 : cleared on insert), but makes debugging a bit easier. */
3198 4824 : writer->total_cost = 0UL;
3199 4824 : wcost_map_ele_remove_fast( pack->writer_costs, writer, pack->writers );
3200 4824 : wcost_pool_ele_release( pack->writers, writer );
3201 4824 : }
3202 :
3203 : /* compressed_slot_number is > FD_PACK_SKIP_CNT, which means +1 is the
3204 : max unless it overflows. */
3205 12 : pack->compressed_slot_number = fd_ushort_max( (ushort)(pack->compressed_slot_number+1), (ushort)(FD_PACK_SKIP_CNT+1) );
3206 :
3207 12 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
3208 12 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
3209 :
3210 24 : for( ulong i=0UL; i<pack->bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i] = 0UL;
3211 :
3212 : /* If our stake is low and we don't become leader often, end_block
3213 : might get called on the order of O(1/hr), which feels too
3214 : infrequent to do anything related to metrics. However, we only
3215 : update the histograms when we are leader, so this is actually a
3216 : good place to copy them. */
3217 12 : FD_MHIST_COPY( PACK, TXN_PER_MICROBLOCK, pack->txn_per_microblock );
3218 :
3219 12 : FD_MGAUGE_SET( PACK, BLOCK_COST, 0UL );
3220 12 : FD_MHIST_COPY( PACK, COST_SCHEDULED_PER_BLOCK, pack->scheduled_cus_per_block );
3221 12 : FD_MHIST_COPY( PACK, CU_REBATED_PER_BLOCK, pack->rebated_cus_per_block );
3222 12 : FD_MHIST_COPY( PACK, COST_NET_PER_BLOCK, pack->net_cus_per_block );
3223 12 : FD_MHIST_COPY( PACK, COST_PER_BLOCK_PCT, pack->pct_cus_per_block );
3224 12 : }
3225 :
3226 : static void
3227 : release_tree( treap_t * treap,
3228 : sig2txn_t * signature_map,
3229 : noncemap_t * noncemap,
3230 114 : fd_pack_ord_txn_t * pool ) {
3231 114 : treap_fwd_iter_t next;
3232 126 : for( treap_fwd_iter_t it=treap_fwd_iter_init( treap, pool ); !treap_fwd_iter_done( it ); it=next ) {
3233 12 : next = treap_fwd_iter_next( it, pool );
3234 12 : ulong idx = treap_fwd_iter_idx( it );
3235 12 : pool[ idx ].root = FD_ORD_TXN_ROOT_FREE;
3236 12 : treap_idx_remove ( treap, idx, pool );
3237 12 : sig2txn_idx_remove_fast( signature_map, idx, pool );
3238 12 : trp_pool_idx_release ( pool, idx );
3239 12 : if( pool[ idx ].txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE ) {
3240 9 : noncemap_idx_remove_fast( noncemap, idx, pool );
3241 9 : }
3242 12 : }
3243 114 : }
3244 :
3245 : void
3246 6 : fd_pack_clear_all( fd_pack_t * pack ) {
3247 6 : pack->pending_txn_cnt = 0UL;
3248 6 : pack->microblock_cnt = 0UL;
3249 6 : pack->cumulative_block_cost = 0UL;
3250 6 : pack->cumulative_rebated_cus = 0UL;
3251 6 : pack->data_bytes_consumed = 0UL;
3252 6 : pack->alloc_consumed = 0UL;
3253 :
3254 6 : pack->pending_smallest->cus = ULONG_MAX;
3255 6 : pack->pending_smallest->bytes = ULONG_MAX;
3256 :
3257 6 : release_tree( pack->pending, pack->signature_map, pack->noncemap, pack->pool );
3258 6 : release_tree( pack->pending_bundles, pack->signature_map, pack->noncemap, pack->pool );
3259 6 : release_tree( pack->next_auction, pack->signature_map, pack->noncemap, pack->pool );
3260 102 : for( ulong i=0UL; i<FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY; i++ ) {
3261 96 : release_tree( pack->pre_rotation_bundles[ i ].treap, pack->signature_map, pack->noncemap, pack->pool );
3262 96 : }
3263 6 : pack->pre_rotation_bundle_cnt = 0UL;
3264 :
3265 6 : ulong const pool_max = trp_pool_max( pack->pool );
3266 3240 : for( ulong i=0UL; i<pool_max; i++ ) {
3267 3234 : if( FD_UNLIKELY( pack->pool[ i ].root!=FD_ORD_TXN_ROOT_FREE ) ) {
3268 0 : fd_pack_ord_txn_t * const del = pack->pool + i;
3269 0 : fd_txn_t * txn = TXN( del->txn );
3270 0 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, del->txn->payload );
3271 0 : fd_acct_addr_t const * alt = del->txn_e->alt_accts;
3272 0 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( del->root ) );
3273 0 : fd_pack_penalty_treap_t * penalty_treap = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
3274 0 : FD_TEST( penalty_treap );
3275 0 : release_tree( penalty_treap->penalty_treap, pack->signature_map, pack->noncemap, pack->pool );
3276 0 : }
3277 3234 : }
3278 :
3279 6 : pack->compressed_slot_number = (ushort)(FD_PACK_SKIP_CNT+1);
3280 :
3281 6 : expq_remove_all( pack->expiration_q );
3282 :
3283 6 : acct_uses_clear( pack->acct_in_use );
3284 :
3285 21 : while( !wcost_dlist_is_empty( pack->written_list, pack->writers ) ) {
3286 15 : fd_pack_wcost_ele_t * writer = wcost_dlist_ele_pop_head( pack->written_list, pack->writers );
3287 15 : writer->total_cost = 0UL;
3288 15 : wcost_map_ele_remove_fast( pack->writer_costs, writer, pack->writers );
3289 15 : wcost_pool_ele_release( pack->writers, writer );
3290 15 : }
3291 :
3292 6 : penalty_map_clear( pack->penalty_treaps );
3293 :
3294 6 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
3295 6 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
3296 6 : bitset_map_clear( pack->acct_to_bitset );
3297 6 : pack->bitset_avail[ 0 ] = FD_PACK_BITSET_SLOWPATH;
3298 2054 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) pack->bitset_avail[ i+1UL ] = (ushort)i;
3299 6 : pack->bitset_avail_cnt = FD_PACK_BITSET_MAX;
3300 :
3301 12 : for( ulong i=0UL; i<pack->bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i] = 0UL;
3302 6 : }
3303 :
3304 :
3305 : /* If delete_full_bundle is non-zero and the transaction to delete is
3306 : part of a bundle, the rest of the bundle it is part of will be
3307 : deleted as well.
3308 : If move_from_penalty_treap is non-zero and the transaction to delete
3309 : is in the pending treap, move the best transaction in any of the
3310 : conflicting penalty treaps to the pending treap (if there is one). */
3311 : static ulong
3312 : delete_transaction( fd_pack_t * pack,
3313 : fd_pack_ord_txn_t * containing,
3314 : int delete_full_bundle,
3315 1886379 : int move_from_penalty_treap ) {
3316 :
3317 1886379 : fd_txn_t * txn = TXN( containing->txn );
3318 1886379 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, containing->txn->payload );
3319 1886379 : fd_acct_addr_t const * alt = containing->txn_e->alt_accts;
3320 :
3321 1886379 : treap_t * root = NULL;
3322 1886379 : int root_idx = containing->root;
3323 1886379 : fd_pack_penalty_treap_t * penalty_treap = NULL;
3324 1886379 : fd_pack_pre_rotation_bundle_t * pre_rotation_bundle = NULL;
3325 1886379 : switch( root_idx & FD_ORD_TXN_ROOT_TAG_MASK ) {
3326 0 : case FD_ORD_TXN_ROOT_FREE: FD_LOG_CRIT(( "Double free detected" ));
3327 921 : case FD_ORD_TXN_ROOT_PENDING: root = pack->pending; break;
3328 1882773 : case FD_ORD_TXN_ROOT_PENDING_BUNDLE: root = pack->pending_bundles; break;
3329 24 : case FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( 0 ): {
3330 24 : pre_rotation_bundle = pack->pre_rotation_bundles + FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE_IDX( root_idx );
3331 24 : root = pre_rotation_bundle->treap;
3332 24 : break;
3333 0 : }
3334 9 : case FD_ORD_TXN_ROOT_NEXT_AUCTION: root = pack->next_auction; break;
3335 2652 : case FD_ORD_TXN_ROOT_PENALTY( 0 ): {
3336 2652 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( root_idx ) );
3337 2652 : penalty_treap = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
3338 2652 : FD_TEST( penalty_treap );
3339 2652 : root = penalty_treap->penalty_treap;
3340 2652 : break;
3341 2652 : }
3342 1886379 : }
3343 :
3344 1886379 : ulong delete_cnt = 0UL;
3345 1886379 : if( FD_UNLIKELY( delete_full_bundle & ((root==pack->pending_bundles) | (!!pre_rotation_bundle)) ) ) {
3346 : /* When we delete, the structure of the treap may move around, but
3347 : pointers to inside the pool will remain valid */
3348 1882362 : fd_pack_ord_txn_t * bundle_ptrs[ FD_PACK_MAX_TXN_PER_BUNDLE-1UL ];
3349 1882362 : fd_pack_ord_txn_t * pool = pack->pool;
3350 1882362 : ulong cnt = 0UL;
3351 1882362 : ulong bundle_idx = RC_TO_REL_BUNDLE_IDX( containing->rewards, containing->compute_est );
3352 :
3353 : /* Iterate in both directions from the current transaction */
3354 1882362 : for( treap_fwd_iter_t _cur=treap_fwd_iter_next( (treap_fwd_iter_t)treap_idx_fast( containing, pool ), pool );
3355 1882674 : !treap_fwd_iter_done( _cur ); _cur=treap_fwd_iter_next( _cur, pool ) ) {
3356 1882536 : fd_pack_ord_txn_t * cur = treap_fwd_iter_ele( _cur, pool );
3357 1882536 : if( FD_LIKELY( bundle_idx==RC_TO_REL_BUNDLE_IDX( cur->rewards, cur->compute_est ) ) ) {
3358 312 : bundle_ptrs[ cnt++ ] = cur;
3359 1882224 : } else {
3360 1882224 : break;
3361 1882224 : }
3362 312 : FD_TEST( cnt<FD_PACK_MAX_TXN_PER_BUNDLE );
3363 312 : }
3364 :
3365 1882362 : for( treap_rev_iter_t _cur=treap_rev_iter_next( (treap_rev_iter_t)treap_idx_fast( containing, pool ), pool );
3366 1882476 : !treap_rev_iter_done( _cur ); _cur=treap_rev_iter_next( _cur, pool ) ) {
3367 123 : fd_pack_ord_txn_t * cur = treap_rev_iter_ele( _cur, pool );
3368 123 : if( FD_LIKELY( bundle_idx==RC_TO_REL_BUNDLE_IDX( cur->rewards, cur->compute_est ) ) ) {
3369 114 : bundle_ptrs[ cnt++ ] = cur;
3370 114 : } else {
3371 9 : break;
3372 9 : }
3373 114 : FD_TEST( cnt<FD_PACK_MAX_TXN_PER_BUNDLE );
3374 114 : }
3375 :
3376 : /* Delete them each, setting delete_full_bundle to 0 to avoid
3377 : infinite recursion. */
3378 1882788 : for( ulong k=0UL; k<cnt; k++ ) delete_cnt += delete_transaction( pack, bundle_ptrs[ k ], 0, 0 );
3379 1882362 : }
3380 :
3381 :
3382 1886379 : if( FD_UNLIKELY( move_from_penalty_treap & (root==pack->pending) ) ) {
3383 :
3384 816 : fd_pack_ord_txn_t * best = NULL;
3385 816 : fd_pack_penalty_treap_t * best_penalty = NULL;
3386 :
3387 816 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
3388 3498 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
3389 2682 : fd_pack_penalty_treap_t * p_trp = penalty_map_query( pack->penalty_treaps, *ACCT_ITER_TO_PTR( iter ), NULL );
3390 2682 : if( FD_UNLIKELY( p_trp ) ) {
3391 1340 : fd_pack_ord_txn_t * best_in_trp = treap_rev_iter_ele( treap_rev_iter_init( p_trp->penalty_treap, pack->pool ), pack->pool );
3392 1340 : if( FD_UNLIKELY( !best || COMPARE_WORSE( best, best_in_trp ) ) ) {
3393 701 : best = best_in_trp;
3394 701 : best_penalty = p_trp;
3395 701 : }
3396 1340 : }
3397 2682 : }
3398 :
3399 816 : if( FD_LIKELY( best ) ) {
3400 : /* move best to the main treap */
3401 701 : treap_ele_remove( best_penalty->penalty_treap, best, pack->pool );
3402 701 : best->root = FD_ORD_TXN_ROOT_PENDING;
3403 701 : treap_ele_insert( pack->pending, best, pack->pool );
3404 :
3405 701 : pack->pending_smallest->cus = fd_ulong_min( pack->pending_smallest->cus, best->compute_est );
3406 701 : pack->pending_smallest->bytes = fd_ulong_min( pack->pending_smallest->bytes, best->txn_e->txnp->payload_sz );
3407 :
3408 701 : if( FD_UNLIKELY( !treap_ele_cnt( best_penalty->penalty_treap ) ) ) {
3409 9 : treap_delete( treap_leave( best_penalty->penalty_treap ) );
3410 9 : penalty_map_remove( pack->penalty_treaps, best_penalty );
3411 9 : }
3412 701 : }
3413 816 : }
3414 :
3415 : /* Transactions which are being held in the next_auction treap never
3416 : acquired their bitset reference, so there is nothing to release
3417 : here. */
3418 1886379 : if( FD_LIKELY( root!=pack->next_auction ) ) {
3419 1886370 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_ALL );
3420 7568601 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
3421 5682231 : if( FD_UNLIKELY( fd_pack_unwritable_contains( ACCT_ITER_TO_PTR( iter ) ) ) ) continue;
3422 :
3423 3795132 : release_result_t ret = release_bit_reference( pack, ACCT_ITER_TO_PTR( iter ) );
3424 3795132 : FD_PACK_BITSET_CLEARN( pack->bitset_rw_in_use, ret.clear_rw_bit );
3425 3795132 : FD_PACK_BITSET_CLEARN( pack->bitset_w_in_use, ret.clear_w_bit );
3426 3795132 : }
3427 1886370 : }
3428 :
3429 1886379 : if( FD_UNLIKELY( containing->txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE ) ) {
3430 354 : noncemap_ele_remove_fast( pack->noncemap, containing, pack->pool );
3431 354 : }
3432 1886379 : expq_remove( pack->expiration_q, containing->expq_idx );
3433 1886379 : if( FD_UNLIKELY( pre_rotation_bundle ) ) pre_rotation_bundle_remove( pack, pre_rotation_bundle, (ulong)(containing-pack->pool) );
3434 1886355 : else treap_ele_remove( root, containing, pack->pool );
3435 1886379 : containing->root = FD_ORD_TXN_ROOT_FREE;
3436 1886379 : sig2txn_ele_remove_fast( pack->signature_map, containing, pack->pool );
3437 1886379 : trp_pool_ele_release( pack->pool, containing );
3438 :
3439 1886379 : delete_cnt += 1UL;
3440 1886379 : pack->pending_txn_cnt--;
3441 :
3442 1886379 : if( FD_UNLIKELY( penalty_treap && treap_ele_cnt( root )==0UL ) ) {
3443 0 : penalty_map_remove( pack->penalty_treaps, penalty_treap );
3444 0 : }
3445 :
3446 1886379 : return delete_cnt;
3447 1886379 : }
3448 :
3449 : ulong
3450 : fd_pack_delete_transaction( fd_pack_t * pack,
3451 1882410 : fd_ed25519_sig_t const * sig0 ) {
3452 1882410 : ulong cnt = 0;
3453 1882410 : ulong next = ULONG_MAX;
3454 :
3455 : /* sig2txn reads only the signature offset and signature bytes. */
3456 1882410 : fd_txn_e_t query_e;
3457 1882410 : TXN(query_e.txnp)->signature_off = 0U;
3458 1882410 : fd_memcpy( query_e.txnp[0].payload, sig0, FD_TXN_SIGNATURE_SZ );
3459 1882410 : for( ulong idx = sig2txn_idx_query_const( pack->signature_map, &query_e, ULONG_MAX, pack->pool );
3460 3764796 : idx!=ULONG_MAX; idx=next ) {
3461 : /* Iterating while deleting, not just this element, but perhaps the
3462 : whole bundle, feels a bit dangerous, but is actually fine because
3463 : a bundle can't contain two transactions with the same signature.
3464 : That means we know next is not part of the same bundle as idx,
3465 : which means that deleting idx will not delete next. */
3466 1882386 : next = sig2txn_idx_next_const( idx, ULONG_MAX, pack->pool );
3467 1882386 : cnt += delete_transaction( pack, pack->pool+idx, 1, 1 );
3468 1882386 : }
3469 :
3470 1882410 : return cnt;
3471 1882410 : }
3472 :
3473 :
3474 : int
3475 : fd_pack_verify( fd_pack_t * pack,
3476 651 : void * scratch ) {
3477 : /* Invariants:
3478 : sig2txn_query has exact same contents as all treaps combined
3479 : root matches treap
3480 : Keys of acct_to_bitset is exactly union of all accounts in all
3481 : transactions in treaps, with ref counted appropriately
3482 : bits in bitset_avail is complement of bits allocated in
3483 : acct_to_bitset
3484 : expires_at consistent between treap, prq
3485 : use_by_bank does not contain duplicates
3486 : use_by_bank consistent with acct_in_use
3487 : elements in pool but not in a treap have root set to free
3488 : all penalty treaps have at least one transaction
3489 : all elements in penalty treaps are in the one that the root indicates
3490 : */
3491 :
3492 : /* TODO:
3493 : bitset_{r}w_in_use = bitset_map_query( everything in acct_in_use that doesn't have FD_PACK_IN_USE_BIT_CLEARED )
3494 : bitset_w_in_use & bitset_rw_in_use == bitset_w_in_use
3495 : */
3496 515033 : #define VERIFY_TEST( cond, ... ) do { \
3497 515033 : if( FD_UNLIKELY( !(cond) ) ) { \
3498 0 : FD_LOG_WARNING(( __VA_ARGS__ )); \
3499 0 : return -(__LINE__); \
3500 0 : } \
3501 515033 : } while( 0 )
3502 :
3503 651 : ulong max_acct_in_treap = pack->pack_depth * FD_TXN_ACCT_ADDR_MAX;
3504 651 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
3505 651 : void * _bitset_map_copy = scratch;
3506 651 : void * _bitset_map_orig = bitset_map_leave( pack->acct_to_bitset );
3507 651 : fd_memcpy( _bitset_map_copy, _bitset_map_orig, bitset_map_footprint( lg_acct_in_trp ) );
3508 :
3509 651 : fd_pack_bitset_acct_mapping_t * bitset_copy = bitset_map_join( _bitset_map_copy );
3510 :
3511 : /* Check that each bit is in exactly one place */
3512 651 : FD_PACK_BITSET_DECLARE( processed ); FD_PACK_BITSET_CLEAR( processed );
3513 651 : FD_PACK_BITSET_DECLARE( bit ); FD_PACK_BITSET_CLEAR( bit );
3514 651 : FD_PACK_BITSET_DECLARE( full ); FD_PACK_BITSET_CLEAR( full );
3515 :
3516 651 : if( FD_UNLIKELY( pack->bitset_avail[0]!=FD_PACK_BITSET_SLOWPATH ) ) return -1;
3517 221893 : for( ulong i=1UL; i<=pack->bitset_avail_cnt; i++ ) {
3518 221242 : FD_PACK_BITSET_CLEAR( bit );
3519 221242 : FD_PACK_BITSET_SETN( bit, pack->bitset_avail[ i ] );
3520 221242 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ),
3521 221242 : "bit %hu in avail set twice", pack->bitset_avail[ i ] );
3522 221242 : FD_PACK_BITSET_OR( processed, bit );
3523 221242 : }
3524 :
3525 651 : ulong total_references = 0UL;
3526 71334027 : for( ulong i=0UL; i<bitset_map_slot_cnt( bitset_copy ); i++ ) {
3527 71333376 : if( !bitset_map_key_inval( bitset_copy[ i ].key ) ) {
3528 4692 : VERIFY_TEST( bitset_copy[ i ].ref_cnt>0UL, "account address in table with 0 ref count" );
3529 :
3530 4692 : total_references += bitset_copy[ i ].ref_cnt;
3531 :
3532 4692 : FD_PACK_BITSET_CLEAR( bit );
3533 4692 : FD_PACK_BITSET_SETN( bit, bitset_copy[ i ].bit );
3534 4692 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ), "bit %hu used twice", bitset_copy[ i ].bit );
3535 4692 : FD_PACK_BITSET_OR( processed, bit );
3536 4692 : }
3537 71333376 : }
3538 222859 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) {
3539 222208 : FD_PACK_BITSET_CLEAR( bit );
3540 222208 : FD_PACK_BITSET_SETN( bit, i );
3541 222208 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ), "bit %lu missing", i );
3542 222208 : FD_PACK_BITSET_SETN( full, i );
3543 222208 : }
3544 :
3545 :
3546 651 : fd_pack_ord_txn_t * pool = pack->pool;
3547 651 : treap_t * treaps [ 3 ] = { pack->pending, pack->pending_bundles, pack->next_auction };
3548 651 : int root_tags[ 3 ] = { FD_ORD_TXN_ROOT_PENDING, FD_ORD_TXN_ROOT_PENDING_BUNDLE, FD_ORD_TXN_ROOT_NEXT_AUCTION };
3549 651 : ulong txn_cnt = 0UL;
3550 :
3551 651 : ulong const pre_rotation_bundle_max = FD_PACK_PRE_ROTATION_BUNDLE_CAPACITY;
3552 651 : ulong pre_rotation_bundle_cnt = 0UL;
3553 11067 : for( ulong i=0UL; i<pre_rotation_bundle_max; i++ ) {
3554 10416 : ulong cnt = treap_ele_cnt( pack->pre_rotation_bundles[ i ].treap );
3555 10416 : pre_rotation_bundle_cnt += (ulong)(cnt>0UL);
3556 10416 : VERIFY_TEST( cnt<=FD_PACK_MAX_TXN_PER_BUNDLE, "pre-rotation bundle %lu holds %lu transactions", i, cnt );
3557 10416 : }
3558 651 : VERIFY_TEST( pre_rotation_bundle_cnt==pack->pre_rotation_bundle_cnt, "pre_rotation_bundle_cnt %lu, found %lu bundles", pack->pre_rotation_bundle_cnt, pre_rotation_bundle_cnt );
3559 :
3560 651 : VERIFY_TEST( pack->auction_running || !treap_ele_cnt( pack->next_auction ), "next_auction not empty outside an auction" );
3561 :
3562 1127604 : for( ulong k=0UL; k<3UL+pre_rotation_bundle_max+penalty_map_slot_cnt( pack->penalty_treaps ); k++ ) {
3563 1126953 : treap_t * treap = NULL;
3564 :
3565 1126953 : if( k<3UL ) treap = treaps[ k ];
3566 1125000 : else if( k<3UL+pre_rotation_bundle_max ) {
3567 10416 : treap = pack->pre_rotation_bundles[ k-3UL ].treap;
3568 10416 : if( !treap_ele_cnt( treap ) ) continue;
3569 10416 : }
3570 1114584 : else if( FD_LIKELY( penalty_map_key_inval( pack->penalty_treaps[ k-3UL-pre_rotation_bundle_max ].key ) ) ) continue;
3571 0 : else {
3572 0 : treap = pack->penalty_treaps[ k-3UL-pre_rotation_bundle_max ].penalty_treap;
3573 0 : VERIFY_TEST( treap_ele_cnt( treap )>0UL, "empty penalty treap in map" );
3574 0 : }
3575 :
3576 5127 : for( treap_rev_iter_t _cur=treap_rev_iter_init( treap, pool ); !treap_rev_iter_done( _cur );
3577 2610 : _cur=treap_rev_iter_next( _cur, pool ) ) {
3578 2517 : txn_cnt++;
3579 2517 : fd_pack_ord_txn_t const * cur = treap_rev_iter_ele_const( _cur, pool );
3580 2517 : fd_txn_t const * txn = TXN(cur->txn);
3581 2517 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
3582 2517 : fd_acct_addr_t const * alt = cur->txn_e->alt_accts;
3583 :
3584 2517 : fd_pack_ord_txn_t const * in_tbl = sig2txn_ele_query_const( pack->signature_map, &cur->_txn_e, NULL, pool );
3585 2517 : VERIFY_TEST( in_tbl, "signature missing from sig2txn" );
3586 :
3587 2517 : ulong expected_root = (k<3UL) ? (ulong)root_tags[ k ] : ((k<3UL+pre_rotation_bundle_max) ? (ulong)FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( 0 ) : (ulong)FD_ORD_TXN_ROOT_PENALTY( 0 ));
3588 2517 : VERIFY_TEST( (ulong)(cur->root & FD_ORD_TXN_ROOT_TAG_MASK)==expected_root, "treap element had bad root" );
3589 2517 : if( FD_UNLIKELY( (cur->root & FD_ORD_TXN_ROOT_TAG_MASK)==FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE( 0 ) ) ) {
3590 672 : VERIFY_TEST( (ulong)FD_ORD_TXN_ROOT_PRE_ROTATION_BUNDLE_IDX( cur->root )==k-3UL, "transaction in wrong pre-rotation bundle" );
3591 672 : }
3592 2517 : if( FD_LIKELY( (cur->root & FD_ORD_TXN_ROOT_TAG_MASK)==FD_ORD_TXN_ROOT_PENALTY(0) ) ) {
3593 0 : fd_acct_addr_t const * penalty_acct = ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( cur->root ) );
3594 0 : VERIFY_TEST( !memcmp( penalty_acct, pack->penalty_treaps[ k-3UL-pre_rotation_bundle_max ].key.b, 32UL ), "transaction in wrong penalty treap" );
3595 0 : }
3596 2517 : VERIFY_TEST( cur->expires_at>=pack->expire_before, "treap element expired" );
3597 :
3598 2517 : fd_pack_expq_t const * eq = pack->expiration_q + cur->expq_idx;
3599 2517 : VERIFY_TEST( eq->txn==cur, "expq inconsistent" );
3600 2517 : VERIFY_TEST( eq->expires_at==cur->expires_at, "expq expires_at inconsistent" );
3601 :
3602 2517 : if( FD_UNLIKELY( (cur->root & FD_ORD_TXN_ROOT_TAG_MASK)==FD_ORD_TXN_ROOT_NEXT_AUCTION ) ) continue;
3603 :
3604 2508 : FD_PACK_BITSET_DECLARE( complement );
3605 2508 : FD_PACK_BITSET_COPY( complement, full );
3606 2508 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
3607 8250 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
3608 5742 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
3609 :
3610 5742 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( bitset_copy, acct, NULL );
3611 5742 : VERIFY_TEST( q, "account in transaction missing from bitset mapping" );
3612 5742 : VERIFY_TEST( q->ref_cnt>0UL, "account in transaction ref_cnt already 0" );
3613 5742 : q->ref_cnt--;
3614 5742 : total_references--;
3615 :
3616 5742 : FD_PACK_BITSET_CLEAR( bit );
3617 5742 : FD_PACK_BITSET_SETN( bit, q->bit );
3618 5742 : if( q->bit<FD_PACK_BITSET_MAX ) {
3619 2073 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->rw_bitset, cur->rw_bitset ), "missing from rw bitset" );
3620 2073 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->w_bitset, cur->w_bitset ), "missing from w bitset" );
3621 2073 : }
3622 5742 : FD_PACK_BITSET_CLEARN( complement, q->bit );
3623 5742 : }
3624 2508 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( complement, complement, cur->w_bitset, cur->w_bitset ), "extra in w bitset" );
3625 :
3626 2508 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
3627 8145 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
3628 :
3629 5637 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
3630 5637 : if( FD_UNLIKELY( fd_pack_unwritable_contains( &acct ) ) ) continue;
3631 2325 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( bitset_copy, acct, NULL );
3632 2325 : VERIFY_TEST( q, "account in transaction missing from bitset mapping" );
3633 2325 : VERIFY_TEST( q->ref_cnt>0UL, "account in transaction ref_cnt already 0" );
3634 2325 : q->ref_cnt--;
3635 2325 : total_references--;
3636 :
3637 2325 : FD_PACK_BITSET_CLEAR( bit );
3638 2325 : FD_PACK_BITSET_SETN( bit, q->bit );
3639 2325 : if( q->bit<FD_PACK_BITSET_MAX ) {
3640 2268 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->rw_bitset, cur->rw_bitset ), "missing from rw bitset" );
3641 2268 : }
3642 2325 : FD_PACK_BITSET_CLEARN( complement, q->bit );
3643 2325 : }
3644 2508 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( complement, complement, cur->rw_bitset, cur->rw_bitset ), "extra in rw bitset" );
3645 2508 : }
3646 2610 : }
3647 :
3648 651 : bitset_map_leave( bitset_copy );
3649 651 : VERIFY_TEST( txn_cnt==pack->pending_txn_cnt, "txn_cnt" );
3650 :
3651 651 : VERIFY_TEST( total_references==0UL, "extra references in bitset mapping" );
3652 651 : ulong sig2txn_key_cnt = 0UL;
3653 651 : for( sig2txn_iter_t iter = sig2txn_iter_init( pack->signature_map, pool );
3654 3168 : !sig2txn_iter_done( iter, pack->signature_map, pool );
3655 2517 : iter = sig2txn_iter_next( iter, pack->signature_map, pool ) ) {
3656 2517 : sig2txn_key_cnt++;
3657 2517 : }
3658 651 : VERIFY_TEST( txn_cnt==sig2txn_key_cnt, "extra signatures in sig2txn" );
3659 651 : VERIFY_TEST( !sig2txn_verify( pack->signature_map, trp_pool_max( pool ), pool ), "sig2txn corrupt" );
3660 :
3661 : /* Count noncemap keys */
3662 651 : ulong noncemap_key_cnt = 0UL;
3663 651 : for( noncemap_iter_t iter = noncemap_iter_init( pack->noncemap, pool );
3664 711 : !noncemap_iter_done( iter, pack->noncemap, pool );
3665 651 : iter = noncemap_iter_next( iter, pack->noncemap, pool ) ) {
3666 60 : noncemap_key_cnt++;
3667 : /* Ensure element is in pool */
3668 60 : fd_pack_ord_txn_t const * ord = noncemap_iter_ele_const( iter, pack->noncemap, pool );
3669 60 : VERIFY_TEST( ord->txn->flags & FD_TXN_P_FLAGS_DURABLE_NONCE, "invalid entry in noncemap" );
3670 :
3671 : /* Although pack allows multiple transactions with the same
3672 : signature in sig2txn (MAP_MULTI==1), the noncemap checks prevent
3673 : multiple nonce transactions with the same signature. */
3674 60 : VERIFY_TEST( ord==sig2txn_ele_query_const( pack->signature_map, &ord->_txn_e, NULL, pool ), "noncemap and sig2txn desynced" );
3675 60 : }
3676 651 : VERIFY_TEST( txn_cnt>=noncemap_key_cnt, "phantom txns in noncemap" );
3677 651 : VERIFY_TEST( !noncemap_verify( pack->noncemap, trp_pool_max( pool ), pool ), "noncemap corrupt" );
3678 :
3679 651 : ulong slots_found = 0UL;
3680 651 : ulong const pool_max = trp_pool_max( pool );
3681 528240 : for( ulong i=0UL; i<pool_max; i++ ) {
3682 527589 : fd_pack_ord_txn_t * ord = pack->pool + i;
3683 527589 : if( ord->root!=FD_ORD_TXN_ROOT_FREE ) slots_found++;
3684 527589 : }
3685 651 : VERIFY_TEST( slots_found==txn_cnt, "phantom slots in pool" );
3686 :
3687 651 : bitset_map_join( _bitset_map_orig );
3688 :
3689 651 : int lg_uses_tbl_sz = acct_uses_lg_slot_cnt( pack->acct_in_use );
3690 :
3691 651 : void * _acct_in_use_copy = scratch;
3692 651 : void * _acct_in_use_orig = acct_uses_leave( pack->acct_in_use );
3693 651 : fd_memcpy( _acct_in_use_copy, _acct_in_use_orig, acct_uses_footprint( lg_uses_tbl_sz ) );
3694 :
3695 651 : fd_pack_addr_use_t * acct_in_use_copy = acct_uses_join( _acct_in_use_copy );
3696 :
3697 651 : FD_PACK_BITSET_DECLARE( w_complement );
3698 651 : FD_PACK_BITSET_DECLARE( rw_complement );
3699 651 : FD_PACK_BITSET_COPY( w_complement, full );
3700 651 : FD_PACK_BITSET_COPY( rw_complement, full );
3701 :
3702 651 : FD_PACK_BITSET_DECLARE( rw_bitset ); FD_PACK_BITSET_COPY( rw_bitset, pack->bitset_rw_in_use );
3703 651 : FD_PACK_BITSET_DECLARE( w_bitset ); FD_PACK_BITSET_COPY( w_bitset, pack->bitset_w_in_use );
3704 :
3705 :
3706 651 : ulong const EMPTY_MASK = ~(FD_PACK_IN_USE_WRITABLE | FD_PACK_IN_USE_BIT_CLEARED);
3707 :
3708 12675 : for( ulong bank=0UL; bank<pack->bank_tile_cnt; bank++ ) {
3709 :
3710 12024 : fd_pack_addr_use_t const * base = pack->use_by_bank[ bank ];
3711 12024 : ulong bank_mask = 1UL << bank;
3712 :
3713 12885 : for( ulong i=0UL; i<pack->use_by_bank_cnt[ bank ]; i++ ) {
3714 861 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use_copy, base[i].key, NULL );
3715 861 : VERIFY_TEST( use, "acct in use by bank not in acct_in_use, or in uses_by_bank twice" );
3716 :
3717 861 : VERIFY_TEST( use->in_use_by & bank_mask, "acct in uses_by_bank doesn't have corresponding bit set in acct_in_use, or it was in the list twice" );
3718 :
3719 861 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, base[i].key, NULL );
3720 : /* The normal case is that the acct->bit mapping is preserved
3721 : while in use by other transactions in the pending list. This
3722 : might not always happen though. It's okay for the mapping to
3723 : get deleted while the acct is in use, which is noted with
3724 : BIT_CLEARED. If that is set, the mapping may not exist, or it
3725 : may have been re-created, perhaps with a different bit. */
3726 861 : if( q==NULL ) VERIFY_TEST( use->in_use_by & FD_PACK_IN_USE_BIT_CLEARED, "acct in use not in acct_to_bitset, but not marked as cleared" );
3727 0 : else if( !(use->in_use_by & FD_PACK_IN_USE_BIT_CLEARED) ) {
3728 0 : FD_PACK_BITSET_CLEAR( bit );
3729 0 : FD_PACK_BITSET_SETN( bit, q->bit );
3730 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
3731 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, rw_bitset, rw_bitset ), "missing from rw bitset" );
3732 0 : if( use->in_use_by & FD_PACK_IN_USE_WRITABLE ) {
3733 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, w_bitset, w_bitset ), "missing from w bitset" );
3734 0 : FD_PACK_BITSET_CLEARN( w_complement, q->bit );
3735 0 : }
3736 0 : }
3737 0 : FD_PACK_BITSET_CLEARN( rw_complement, q->bit );
3738 0 : }
3739 861 : if( use->in_use_by & FD_PACK_IN_USE_WRITABLE ) VERIFY_TEST( (use->in_use_by & EMPTY_MASK)==bank_mask, "writable, but in use by multiple" );
3740 :
3741 861 : use->in_use_by &= ~bank_mask;
3742 861 : if( !(use->in_use_by & EMPTY_MASK) ) acct_uses_remove( acct_in_use_copy, use );
3743 861 : }
3744 12024 : }
3745 651 : VERIFY_TEST( acct_uses_key_cnt( acct_in_use_copy )==0UL, "stray uses in acct_in_use" );
3746 651 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( rw_complement, rw_complement, rw_bitset, rw_bitset ), "extra in rw bitset" );
3747 651 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( w_complement, w_complement, w_bitset, w_bitset ), "extra in w bitset" );
3748 :
3749 651 : acct_uses_leave( acct_in_use_copy );
3750 :
3751 651 : acct_uses_join( _acct_in_use_orig );
3752 651 : return 0;
3753 651 : }
3754 :
3755 246 : void * fd_pack_leave ( fd_pack_t * pack ) { FD_COMPILER_MFENCE(); return (void *)pack; }
3756 246 : void * fd_pack_delete( void * mem ) { FD_COMPILER_MFENCE(); return mem; }
|
