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