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