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