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_compute_budget_program.h"
5 : #include "fd_pack_bitset.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 "../../disco/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 :
17 : /* fd_pack_ord_txn_t: An fd_txn_p_t with information required to order
18 : it by priority. */
19 : struct fd_pack_private_ord_txn {
20 : /* It's important that there be no padding here (asserted below)
21 : because the code casts back and forth from pointers to this element
22 : to pointers to the whole struct. */
23 : union {
24 : fd_txn_p_t txn[1]; /* txn is an alias for txn_e->txnp */
25 : fd_txn_e_t txn_e[1];
26 : };
27 :
28 : /* Since this struct can be in one of several trees, it's helpful to
29 : store which tree. This should be one of the FD_ORD_TXN_ROOT_*
30 : values. */
31 : int root;
32 :
33 : /* Each transaction is inserted with an expiration "time." This code
34 : doesn't care about the units (blocks, rdtsc tick, ns, etc.), and
35 : doesn't require transactions to be inserted in expiration date
36 : order. */
37 : ulong expires_at;
38 : /* expq_idx: When this object is part of one of the treaps, it's
39 : also in the expiration priority queue. This field (which is
40 : manipulated behind the scenes by the fd_prq code) stores where so
41 : that if we delete this transaction, we can also delete it from the
42 : expiration priority queue. */
43 : ulong expq_idx;
44 :
45 : /* We want rewards*compute_est to fit in a ulong so that r1/c1 < r2/c2 can be
46 : computed as r1*c2 < r2*c1, with the product fitting in a ulong.
47 : compute_est has a small natural limit of mid-20 bits. rewards doesn't have
48 : a natural limit, so there is some argument to be made for raising the
49 : limit for rewards to 40ish bits. The struct has better packing with
50 : uint/uint though. */
51 : uint __attribute__((aligned(64))) /* We want the treap fields and the bitsets
52 : to be on the same double cache line pair */
53 : rewards; /* in Lamports */
54 : uint compute_est; /* in compute units */
55 :
56 : /* The treap fields */
57 : ushort left;
58 : ushort right;
59 : ushort parent;
60 : ushort prio;
61 : ushort prev;
62 : ushort next;
63 :
64 : FD_PACK_BITSET_DECLARE( rw_bitset ); /* all accts this txn references */
65 : FD_PACK_BITSET_DECLARE( w_bitset ); /* accts this txn write-locks */
66 :
67 : };
68 : typedef struct fd_pack_private_ord_txn fd_pack_ord_txn_t;
69 :
70 : /* What we want is that the payload starts at byte 0 of
71 : fd_pack_ord_txn_t so that the trick with the signature map works
72 : properly. GCC and Clang seem to disagree on the rules of offsetof.
73 : */
74 : FD_STATIC_ASSERT( offsetof( fd_pack_ord_txn_t, txn )==0UL, fd_pack_ord_txn_t );
75 : #if FD_USING_CLANG
76 : FD_STATIC_ASSERT( offsetof( fd_txn_p_t, payload )==0UL, fd_pack_ord_txn_t );
77 : #else
78 : FD_STATIC_ASSERT( offsetof( fd_pack_ord_txn_t, txn->payload )==0UL, fd_pack_ord_txn_t );
79 : FD_STATIC_ASSERT( offsetof( fd_pack_ord_txn_t, txn_e->txnp )==0UL, fd_pack_ord_txn_t );
80 : #endif
81 :
82 0 : #define FD_ORD_TXN_ROOT_FREE 0
83 27110796 : #define FD_ORD_TXN_ROOT_PENDING 1
84 13610346 : #define FD_ORD_TXN_ROOT_PENDING_VOTE 2
85 :
86 28371678 : #define FD_PACK_IN_USE_WRITABLE (0x8000000000000000UL)
87 15346137 : #define FD_PACK_IN_USE_BIT_CLEARED (0x4000000000000000UL)
88 :
89 : /* Each non-empty microblock we schedule also has an overhead of 48
90 : bytes that counts towards shed limits. That comes from the 32 byte
91 : hash, the hash count (8 bytes) and the transaction count (8 bytes).
92 : We don't have to pay this overhead if the microblock is empty, since
93 : those microblocks get dropped. */
94 1476432 : #define MICROBLOCK_DATA_OVERHEAD 48UL
95 :
96 : /* Keep track of accounts that are written to in each block so that we
97 : can reset the writer costs to 0. If the number of accounts that are
98 : written to is above or equal to this, we'll just clear the whole
99 : writer cost map instead of only removing the elements we increased. */
100 1353 : #define DEFAULT_WRITTEN_LIST_MAX 16384UL
101 :
102 : /* fd_pack_addr_use_t: Used for two distinct purposes:
103 : - to record that an address is in use and can't be used again until
104 : certain microblocks finish execution
105 : - to keep track of the cost of all transactions that write to the
106 : specified account.
107 : Making these separate structs might make it more clear, but then
108 : they'd have identical shape and result in two fd_map_dynamic sets of
109 : functions with identical code. It doesn't seem like the compiler is
110 : very good at merging code like that, so in order to reduce code
111 : bloat, we'll just combine them. */
112 : struct fd_pack_private_addr_use_record {
113 : fd_acct_addr_t key; /* account address */
114 : union {
115 : ulong in_use_by; /* Bitmask indicating which banks */
116 : ulong total_cost; /* In cost units/CUs */
117 : };
118 : };
119 : typedef struct fd_pack_private_addr_use_record fd_pack_addr_use_t;
120 :
121 :
122 : /* fd_pack_sig_to_entry_t: An element of an fd_map that maps the first
123 : transaction signature to the corresponding fd_pack_ord_txn_t so that
124 : pending transactions can be deleted by signature. Note: this
125 : implicitly relies on the fact that for Solana transactions the
126 : signature_offset is always 1. If that fact changes, this will need
127 : to become a real struct. */
128 : struct fd_pack_sig_to_txn {
129 : fd_ed25519_sig_t const * key;
130 : };
131 : typedef struct fd_pack_sig_to_txn fd_pack_sig_to_txn_t;
132 :
133 : /* fd_pack_expq_t: An element of an fd_prq to sort the transactions by
134 : timeout. This structure has several invariants for entries
135 : corresponding to pending transactions:
136 : expires_at == txn->expires_at
137 : txn->exp_prq_idx is the index of this structure
138 : Notice that prq is an array-based heap, which means the indexes of
139 : elements change. The PRQ_TMP_ST macro is hijacked to keep that
140 : invariant up to date.
141 :
142 : Note: this could be easier if fd_heap supported deleting from the
143 : middle, but that's not possible with the current design of fd_heap,
144 : which omits a parent pointer for improved performance. */
145 : struct fd_pack_expq {
146 : ulong expires_at;
147 : fd_pack_ord_txn_t * txn;
148 : };
149 : typedef struct fd_pack_expq fd_pack_expq_t;
150 :
151 :
152 : /* fd_pack_bitset_acct_mapping_t: An element of an fd_map_dynamic that
153 : maps an account address to the number of transactions that are
154 : referencing it and the bit that is reserved to indicate it in the
155 : bitset, if any. */
156 : struct fd_pack_bitset_acct_mapping {
157 : fd_acct_addr_t key; /* account address */
158 : ulong ref_cnt;
159 :
160 : /* first_instance and first_instance_was_write are only valid when
161 : bit==FD_PACK_BITSET_FIRST_INSTANCE, which is set when ref_cnt
162 : transitions from 0 to 1. These just exist to implement the
163 : optimization that accounts referenced a single time aren't
164 : allocated a bit, but this seems to be an important optimization. */
165 : fd_pack_ord_txn_t * first_instance;
166 : int first_instance_was_write;
167 :
168 : /* bit is in [0, FD_PACK_BITSET_MAX) U
169 : { FD_PACK_BITSET_FIRST_INSTANCE, FD_PACK_BITSET_SLOWPATH }. */
170 : ushort bit;
171 : };
172 : typedef struct fd_pack_bitset_acct_mapping fd_pack_bitset_acct_mapping_t;
173 :
174 : /* Table of special addresses that are not allowed to be written to. We
175 : immediately reject and refuse to pack any transaction that tries to
176 : write to one of these accounts. Because we reject any writes to any
177 : of these accounts, we actually don't need to track reads of them
178 : either. This is nice, because fd_map_dynamic requires a null address
179 : that we promise never to insert. The zero address is a sysvar, so
180 : now we meet that part of the fd_map_dynamic contract. */
181 : #define MAP_PERFECT_NAME fd_pack_unwritable
182 : #define MAP_PERFECT_LG_TBL_SZ 5
183 : #define MAP_PERFECT_T fd_acct_addr_t
184 25414101 : #define MAP_PERFECT_HASH_C 1402126759U
185 : #define MAP_PERFECT_KEY b
186 : #define MAP_PERFECT_KEY_T fd_acct_addr_t const *
187 : #define MAP_PERFECT_ZERO_KEY (0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0)
188 : #define MAP_PERFECT_COMPLEX_KEY 1
189 25414101 : #define MAP_PERFECT_KEYS_EQUAL(k1,k2) (!memcmp( (k1), (k2), 32UL ))
190 :
191 25414101 : #define PERFECT_HASH( u ) (((MAP_PERFECT_HASH_C*(u))>>27)&0x1FU)
192 :
193 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
194 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
195 : PERFECT_HASH( (a08 | (a09<<8) | (a10<<16) | (a11<<24)) )
196 25414101 : #define MAP_PERFECT_HASH_R( ptr ) PERFECT_HASH( fd_uint_load_4( (uchar const *)ptr->b + 8UL ) )
197 :
198 : /* This list is a superset of what Lab's is_builtin_key_or_sysvar checks. */
199 : /* Sysvars */
200 : #define MAP_PERFECT_0 ( SYSVAR_CLOCK_ID ),
201 : #define MAP_PERFECT_1 ( SYSVAR_EPOCH_SCHED_ID ),
202 : #define MAP_PERFECT_2 ( SYSVAR_FEES_ID ),
203 : #define MAP_PERFECT_3 ( SYSVAR_RECENT_BLKHASH_ID ),
204 : #define MAP_PERFECT_4 ( SYSVAR_RENT_ID ),
205 : #define MAP_PERFECT_5 ( SYSVAR_REWARDS_ID ),
206 : #define MAP_PERFECT_6 ( SYSVAR_SLOT_HASHES_ID ),
207 : #define MAP_PERFECT_7 ( SYSVAR_SLOT_HIST_ID ),
208 : #define MAP_PERFECT_8 ( SYSVAR_STAKE_HIST_ID ),
209 : #define MAP_PERFECT_9 ( SYSVAR_INSTRUCTIONS_ID ),
210 : #define MAP_PERFECT_10 ( SYSVAR_EPOCH_REWARDS_ID ),
211 : #define MAP_PERFECT_11 ( SYSVAR_LAST_RESTART_ID ),
212 : /* Programs */
213 : #define MAP_PERFECT_12 ( CONFIG_PROG_ID ),
214 : #define MAP_PERFECT_13 ( FEATURE_ID ),
215 : #define MAP_PERFECT_14 ( NATIVE_LOADER_ID ),
216 : #define MAP_PERFECT_15 ( STAKE_PROG_ID ),
217 : #define MAP_PERFECT_16 ( STAKE_CONFIG_PROG_ID ),
218 : #define MAP_PERFECT_17 ( VOTE_PROG_ID ),
219 : #define MAP_PERFECT_18 ( SYS_PROG_ID ), /* Do not remove. See above. */
220 : #define MAP_PERFECT_19 ( BPF_LOADER_1_PROG_ID ),
221 : #define MAP_PERFECT_20 ( BPF_LOADER_2_PROG_ID ),
222 : #define MAP_PERFECT_21 ( BPF_UPGRADEABLE_PROG_ID ),
223 : /* Extras */
224 : #define MAP_PERFECT_22 ( ED25519_SV_PROG_ID ),
225 : #define MAP_PERFECT_23 ( KECCAK_SECP_PROG_ID ),
226 : #define MAP_PERFECT_24 ( COMPUTE_BUDGET_PROG_ID ),
227 : #define MAP_PERFECT_25 ( ADDR_LUT_PROG_ID ),
228 : #define MAP_PERFECT_26 ( NATIVE_MINT_ID ),
229 : #define MAP_PERFECT_27 ( TOKEN_PROG_ID ),
230 : #define MAP_PERFECT_28 ( SYSVAR_PROG_ID ),
231 :
232 : #include "../../util/tmpl/fd_map_perfect.c"
233 :
234 :
235 : /* Returns 1 if x.rewards/x.compute < y.rewards/y.compute. Not robust. */
236 86128137 : #define COMPARE_WORSE(x,y) ( ((ulong)((x)->rewards)*(ulong)((y)->compute_est)) < ((ulong)((y)->rewards)*(ulong)((x)->compute_est)) )
237 :
238 : /* Declare all the data structures */
239 :
240 :
241 : /* Define the big max-"heap" that we pull transactions off to schedule.
242 : The priority is given by reward/compute. We may want to add in some
243 : additional terms at a later point. In order to cheaply remove nodes,
244 : we actually use a treap. */
245 : #define POOL_NAME trp_pool
246 1566 : #define POOL_T fd_pack_ord_txn_t
247 : #define POOL_IDX_T ushort
248 29566221 : #define POOL_NEXT parent
249 : #include "../../util/tmpl/fd_pool.c"
250 :
251 : #define TREAP_T fd_pack_ord_txn_t
252 : #define TREAP_NAME treap
253 : #define TREAP_QUERY_T void * /* We don't use query ... */
254 : #define TREAP_CMP(a,b) (__extension__({ (void)(a); (void)(b); -1; })) /* which means we don't need to give a real
255 : implementation to cmp either */
256 170175306 : #define TREAP_IDX_T ushort
257 : #define TREAP_OPTIMIZE_ITERATION 1
258 86128137 : #define TREAP_LT COMPARE_WORSE
259 : #include "../../util/tmpl/fd_treap.c"
260 :
261 :
262 : /* Define a strange map where key and value are kind of the same
263 : variable. Essentially, it maps the contents to which the pointer
264 : points to the value of the pointer. */
265 : #define MAP_NAME sig2txn
266 39735195 : #define MAP_T fd_pack_sig_to_txn_t
267 349774296 : #define MAP_KEY_T fd_ed25519_sig_t const *
268 19858191 : #define MAP_KEY_NULL NULL
269 349774296 : #define MAP_KEY_INVAL(k) !(k)
270 : #define MAP_MEMOIZE 0
271 321622941 : #define MAP_KEY_EQUAL(k0,k1) (((!!(k0))&(!!(k1)))&&(!memcmp((k0),(k1), FD_TXN_SIGNATURE_SZ)))
272 : #define MAP_KEY_EQUAL_IS_SLOW 1
273 41723961 : #define MAP_KEY_HASH(key) fd_uint_load_4( (key) ) /* first 4 bytes of signature */
274 : #include "../../util/tmpl/fd_map_dynamic.c"
275 :
276 :
277 : static const fd_acct_addr_t null_addr = { 0 };
278 :
279 : #define MAP_NAME acct_uses
280 93789201 : #define MAP_T fd_pack_addr_use_t
281 110755050 : #define MAP_KEY_T fd_acct_addr_t
282 296306571 : #define MAP_KEY_NULL null_addr
283 : #if FD_HAS_AVX
284 110755050 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
285 : #else
286 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
287 : #endif
288 76808547 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
289 : #define MAP_KEY_EQUAL_IS_SLOW 1
290 : #define MAP_MEMOIZE 0
291 93797715 : #define MAP_KEY_HASH(key) ((uint)fd_ulong_hash( fd_ulong_load_8( (key).b ) ))
292 : #include "../../util/tmpl/fd_map_dynamic.c"
293 :
294 :
295 : #define MAP_NAME bitset_map
296 49841979 : #define MAP_T fd_pack_bitset_acct_mapping_t
297 62658843 : #define MAP_KEY_T fd_acct_addr_t
298 871856457 : #define MAP_KEY_NULL null_addr
299 : #if FD_HAS_AVX
300 62658843 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
301 : #else
302 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
303 : #endif
304 37052535 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
305 : #define MAP_KEY_EQUAL_IS_SLOW 1
306 : #define MAP_MEMOIZE 0
307 49866063 : #define MAP_KEY_HASH(key) ((uint)fd_ulong_hash( fd_ulong_load_8( (key).b ) ))
308 : #include "../../util/tmpl/fd_map_dynamic.c"
309 :
310 :
311 : /* Since transactions can also expire, we also maintain a parallel
312 : priority queue. This means elements are simultaneously part of the
313 : treap (ordered by priority) and the expiration queue (ordered by
314 : expiration). It's tempting to use the priority field of the treap
315 : for this purpose, but that can result in degenerate treaps in some
316 : cases. */
317 : #define PRQ_NAME expq
318 26781675 : #define PRQ_T fd_pack_expq_t
319 26146050 : #define PRQ_TIMEOUT_T ulong
320 26146050 : #define PRQ_TIMEOUT expires_at
321 13335402 : #define PRQ_TMP_ST(p,t) do { \
322 13335402 : (p)[0] = (t); \
323 13335402 : t.txn->expq_idx = (ulong)((p)-heap); \
324 13335402 : } while( 0 )
325 : #include "../../util/tmpl/fd_prq.c"
326 :
327 : /* fd_pack_smallest: We want to keep track of the smallest transaction
328 : in each treap. That way, if we know the amount of space left in the
329 : block is less than the smallest transaction in the heap, we can just
330 : skip the heap. Since transactions can be deleted, etc. maintaining
331 : this precisely is hard, but we can maintain a conservative value
332 : fairly cheaply. Since the CU limit or the byte limit can be the one
333 : that matters, we keep track of the smallest by both. */
334 : struct fd_pack_smallest {
335 : ulong cus;
336 : ulong bytes;
337 : };
338 : typedef struct fd_pack_smallest fd_pack_smallest_t;
339 :
340 : /* Finally, we can now declare the main pack data structure */
341 : struct fd_pack_private {
342 : ulong pack_depth;
343 : ulong bank_tile_cnt;
344 :
345 : fd_pack_limits_t lim[1];
346 :
347 : ulong pending_txn_cnt;
348 : ulong microblock_cnt; /* How many microblocks have we
349 : generated in this block? */
350 : ulong data_bytes_consumed; /* How much data is in this block so
351 : far ? */
352 : fd_rng_t * rng;
353 :
354 : ulong cumulative_block_cost;
355 : ulong cumulative_vote_cost;
356 :
357 : /* expire_before: Any transactions with expires_at strictly less than
358 : the current expire_before are removed from the available pending
359 : transaction. Here, "expire" is used as a verb: cause all
360 : transactions before this time to expire. */
361 : ulong expire_before;
362 :
363 : /* outstanding_microblock_mask: a bitmask indicating which banking
364 : tiles have outstanding microblocks, i.e. fd_pack has generated a
365 : microblock for that banking tile and the banking tile has not yet
366 : notified fd_pack that it has completed it. */
367 : ulong outstanding_microblock_mask;
368 :
369 : /* The actual footprint for the pool and maps is allocated
370 : in the same order in which they are declared immediately following
371 : the struct. I.e. these pointers point to memory not far after the
372 : struct. The trees are just pointers into the pool so don't take up
373 : more space. */
374 :
375 : fd_pack_ord_txn_t * pool;
376 :
377 : /* Treaps (sorted by priority) of pending transactions. We store the
378 : pending simple votes separately. */
379 : treap_t pending[1];
380 : treap_t pending_votes[1];
381 :
382 : /* pending{_votes}_smallest: keep a conservative estimate of the
383 : smallest transaction (by cost units and by bytes) in each heap.
384 : Both CUs and bytes should be set to ULONG_MAX is the treap is
385 : empty. */
386 : fd_pack_smallest_t pending_smallest[1];
387 : fd_pack_smallest_t pending_votes_smallest[1];
388 :
389 : /* expiration_q: At the same time that a transaction is in exactly one
390 : of the above treaps, it is also in the expiration queue, sorted by
391 : its expiration time. This enables deleting all transactions that
392 : have expired, regardless of which treap they are in. */
393 : fd_pack_expq_t * expiration_q;
394 :
395 : /* acct_in_use: Map from account address to bitmask indicating which
396 : bank tiles are using the account and whether that use is read or
397 : write (msb). */
398 : fd_pack_addr_use_t * acct_in_use;
399 :
400 : /* bitset_{w, rw}_in_use stores a subset of the information in
401 : acct_in_use using the compressed set format explained at the top of
402 : this file. rw_in_use stores accounts in use for read or write
403 : while w_in_use stores only those in use for write. */
404 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
405 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
406 :
407 : /* writer_costs: Map from account addresses to the sum of costs of
408 : transactions that write to the account. Used for enforcing limits
409 : on the max write cost per account per block. */
410 : fd_pack_addr_use_t * writer_costs;
411 :
412 : /* At the end of every slot, we have to clear out writer_costs. The
413 : map is large, but typically very sparsely populated. As an
414 : optimization, we keep track of the elements of the map that we've
415 : actually used, up to a maximum. If we use more than the maximum,
416 : we revert to the old way of just clearing the whole map.
417 :
418 : written_list indexed [0, written_list_cnt).
419 : written_list_cnt in [0, written_list_max).
420 :
421 : written_list_cnt==written_list_max-1 means that the list may be
422 : incomplete and should be ignored. */
423 : fd_pack_addr_use_t * * written_list;
424 : ulong written_list_cnt;
425 : ulong written_list_max;
426 :
427 :
428 : fd_pack_sig_to_txn_t * signature_map; /* Stores pointers into pool for deleting by signature */
429 :
430 : /* use_by_bank: An array of size (max_txn_per_microblock *
431 : FD_TXN_ACCT_ADDR_MAX) for each banking tile. Only the MSB of
432 : in_use_by is relevant. Addressed use_by_bank[i][j] where i is in
433 : [0, bank_tile_cnt) and j is in [0, use_by_bank_cnt[i]). Used
434 : mostly for clearing the proper bits of acct_in_use when a
435 : microblock finishes. */
436 : fd_pack_addr_use_t * use_by_bank [ FD_PACK_MAX_BANK_TILES ];
437 : ulong use_by_bank_cnt[ FD_PACK_MAX_BANK_TILES ];
438 :
439 : fd_histf_t txn_per_microblock [ 1 ];
440 : fd_histf_t vote_per_microblock[ 1 ];
441 :
442 : fd_histf_t scheduled_cus_per_block[ 1 ];
443 : fd_histf_t rebated_cus_per_block [ 1 ];
444 : fd_histf_t net_cus_per_block [ 1 ];
445 : ulong cumulative_rebated_cus;
446 :
447 : /* use_bundles: if true (non-zero), allows the use of bundles, groups
448 : of transactions that are executed atomically with high priority */
449 : int use_bundles;
450 :
451 : /* bitset_avail: a stack of which bits are not currently reserved and
452 : can be used to represent an account address.
453 : Indexed [0, bitset_avail_cnt]. Element 0 is fixed at
454 : FD_PACK_BITSET_SLOWPATH. */
455 : ushort bitset_avail[ 1UL+FD_PACK_BITSET_MAX ];
456 : ulong bitset_avail_cnt;
457 :
458 : /* acct_to_bitset: an fd_map_dynamic that maps acct addresses to the
459 : reference count, which bit, etc. */
460 : fd_pack_bitset_acct_mapping_t * acct_to_bitset;
461 :
462 : /* chdkup: scratch memory chkdup needs for its internal processing */
463 : fd_chkdup_t chkdup[ 1 ];
464 : };
465 :
466 : typedef struct fd_pack_private fd_pack_t;
467 :
468 : FD_STATIC_ASSERT( offsetof(fd_pack_t, pending_txn_cnt)==FD_PACK_PENDING_TXN_CNT_OFF, txn_cnt_off );
469 :
470 : ulong
471 : fd_pack_footprint( ulong pack_depth,
472 : ulong bank_tile_cnt,
473 309 : fd_pack_limits_t const * limits ) {
474 309 : if( FD_UNLIKELY( (bank_tile_cnt==0) | (bank_tile_cnt>FD_PACK_MAX_BANK_TILES) ) ) return 0UL;
475 309 : if( FD_UNLIKELY( pack_depth<4UL ) ) return 0UL;
476 :
477 309 : ulong l;
478 309 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
479 309 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * limits->max_txn_per_microblock + 1UL);
480 :
481 309 : ulong max_w_per_block = fd_ulong_min( limits->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
482 309 : limits->max_txn_per_microblock * limits->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
483 309 : ulong written_list_max = fd_ulong_min( max_w_per_block>>1, DEFAULT_WRITTEN_LIST_MAX );
484 :
485 : /* log base 2, but with a 2* so that the hash table stays sparse */
486 309 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
487 309 : int lg_max_writers = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_w_per_block ) );
488 309 : int lg_depth = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*pack_depth ) );
489 309 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
490 :
491 309 : l = FD_LAYOUT_INIT;
492 309 : l = FD_LAYOUT_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
493 309 : l = FD_LAYOUT_APPEND( l, trp_pool_align (), trp_pool_footprint ( pack_depth+1UL ) ); /* pool */
494 309 : l = FD_LAYOUT_APPEND( l, expq_align (), expq_footprint ( pack_depth+1UL ) ); /* expiration prq */
495 309 : l = FD_LAYOUT_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) ); /* acct_in_use */
496 309 : l = FD_LAYOUT_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_max_writers ) ); /* writer_costs */
497 309 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t*)*written_list_max ); /* written_list */
498 309 : l = FD_LAYOUT_APPEND( l, sig2txn_align (), sig2txn_footprint ( lg_depth ) ); /* signature_map */
499 309 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight ); /* use_by_bank */
500 309 : l = FD_LAYOUT_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) ); /* acct_to_bitset */
501 309 : return FD_LAYOUT_FINI( l, FD_PACK_ALIGN );
502 309 : }
503 :
504 : void *
505 : fd_pack_new( void * mem,
506 : ulong pack_depth,
507 : ulong bank_tile_cnt,
508 : fd_pack_limits_t const * limits,
509 522 : fd_rng_t * rng ) {
510 :
511 522 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
512 522 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * limits->max_txn_per_microblock + 1UL);
513 522 : ulong max_w_per_block = fd_ulong_min( limits->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
514 522 : limits->max_txn_per_microblock * limits->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
515 522 : ulong written_list_max = fd_ulong_min( max_w_per_block>>1, DEFAULT_WRITTEN_LIST_MAX );
516 :
517 : /* log base 2, but with a 2* so that the hash table stays sparse */
518 522 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
519 522 : int lg_max_writers = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_w_per_block ) );
520 522 : int lg_depth = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*pack_depth ) );
521 522 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
522 :
523 522 : FD_SCRATCH_ALLOC_INIT( l, mem );
524 522 : fd_pack_t * pack = FD_SCRATCH_ALLOC_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
525 : /* The pool has one extra element that is used between insert_init and
526 : cancel/fini. */
527 522 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, trp_pool_align(), trp_pool_footprint ( pack_depth+1UL ) );
528 522 : void * _expq = FD_SCRATCH_ALLOC_APPEND( l, expq_align(), expq_footprint ( pack_depth+1UL ) );
529 522 : void * _uses = FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) );
530 522 : void * _writer_cost = FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_max_writers ) );
531 522 : void * _written_lst = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t*)*written_list_max );
532 522 : void * _sig_map = FD_SCRATCH_ALLOC_APPEND( l, sig2txn_align(), sig2txn_footprint ( lg_depth ) );
533 522 : void * _use_by_bank = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight );
534 522 : void * _acct_bitset = FD_SCRATCH_ALLOC_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) );
535 :
536 0 : pack->pack_depth = pack_depth;
537 522 : pack->bank_tile_cnt = bank_tile_cnt;
538 522 : pack->lim[0] = *limits;
539 522 : pack->pending_txn_cnt = 0UL;
540 522 : pack->microblock_cnt = 0UL;
541 522 : pack->data_bytes_consumed = 0UL;
542 522 : pack->rng = rng;
543 522 : pack->cumulative_block_cost = 0UL;
544 522 : pack->cumulative_vote_cost = 0UL;
545 522 : pack->expire_before = 0UL;
546 522 : pack->outstanding_microblock_mask = 0UL;
547 522 : pack->cumulative_rebated_cus = 0UL;
548 :
549 :
550 522 : trp_pool_new( _pool, pack_depth+1UL );
551 :
552 522 : fd_pack_ord_txn_t * pool = trp_pool_join( _pool );
553 522 : treap_seed( pool, pack_depth+1UL, fd_rng_ulong( rng ) );
554 522 : (void)trp_pool_leave( pool );
555 :
556 :
557 522 : treap_new( (void*)pack->pending, pack_depth );
558 522 : treap_new( (void*)pack->pending_votes, pack_depth );
559 :
560 522 : pack->pending_smallest->cus = ULONG_MAX;
561 522 : pack->pending_smallest->bytes = ULONG_MAX;
562 522 : pack->pending_votes_smallest->cus = ULONG_MAX;
563 522 : pack->pending_votes_smallest->bytes = ULONG_MAX;
564 :
565 522 : expq_new( _expq, pack_depth+1UL );
566 :
567 522 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
568 522 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
569 :
570 522 : acct_uses_new( _uses, lg_uses_tbl_sz );
571 522 : acct_uses_new( _writer_cost, lg_max_writers );
572 :
573 522 : pack->written_list = _written_lst;
574 522 : pack->written_list_cnt = 0UL;
575 522 : pack->written_list_max = written_list_max;
576 :
577 522 : sig2txn_new( _sig_map, lg_depth );
578 :
579 522 : fd_pack_addr_use_t * use_by_bank = (fd_pack_addr_use_t *)_use_by_bank;
580 6771 : for( ulong i=0UL; i<bank_tile_cnt; i++ ) pack->use_by_bank[i]=use_by_bank + i*(FD_TXN_ACCT_ADDR_MAX*limits->max_txn_per_microblock+1UL);
581 6771 : for( ulong i=0UL; i<bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i]=0UL;
582 :
583 522 : fd_histf_new( pack->txn_per_microblock, FD_MHIST_MIN( PACK, TOTAL_TRANSACTIONS_PER_MICROBLOCK_COUNT ),
584 522 : FD_MHIST_MAX( PACK, TOTAL_TRANSACTIONS_PER_MICROBLOCK_COUNT ) );
585 522 : fd_histf_new( pack->vote_per_microblock, FD_MHIST_MIN( PACK, VOTES_PER_MICROBLOCK_COUNT ),
586 522 : FD_MHIST_MAX( PACK, VOTES_PER_MICROBLOCK_COUNT ) );
587 :
588 522 : fd_histf_new( pack->scheduled_cus_per_block, FD_MHIST_MIN( PACK, CUS_SCHEDULED ),
589 522 : FD_MHIST_MAX( PACK, CUS_SCHEDULED ) );
590 522 : fd_histf_new( pack->rebated_cus_per_block, FD_MHIST_MIN( PACK, CUS_REBATED ),
591 522 : FD_MHIST_MAX( PACK, CUS_REBATED ) );
592 522 : fd_histf_new( pack->net_cus_per_block, FD_MHIST_MIN( PACK, CUS_NET ),
593 522 : FD_MHIST_MAX( PACK, CUS_NET ) );
594 :
595 522 : pack->use_bundles = 0;
596 :
597 522 : pack->bitset_avail[ 0 ] = FD_PACK_BITSET_SLOWPATH;
598 178698 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) pack->bitset_avail[ i+1UL ] = (ushort)i;
599 522 : pack->bitset_avail_cnt = FD_PACK_BITSET_MAX;
600 :
601 522 : bitset_map_new( _acct_bitset, lg_acct_in_trp );
602 :
603 522 : fd_chkdup_new( pack->chkdup, rng );
604 :
605 522 : return mem;
606 522 : }
607 :
608 : fd_pack_t *
609 522 : fd_pack_join( void * mem ) {
610 522 : FD_SCRATCH_ALLOC_INIT( l, mem );
611 522 : fd_pack_t * pack = FD_SCRATCH_ALLOC_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
612 :
613 0 : ulong pack_depth = pack->pack_depth;
614 522 : ulong bank_tile_cnt = pack->bank_tile_cnt;
615 :
616 522 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
617 522 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * pack->lim->max_txn_per_microblock + 1UL);
618 522 : ulong max_w_per_block = fd_ulong_min( pack->lim->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
619 522 : pack->lim->max_txn_per_microblock * pack->lim->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
620 522 : ulong written_list_max = fd_ulong_min( max_w_per_block>>1, DEFAULT_WRITTEN_LIST_MAX );
621 :
622 522 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
623 522 : int lg_max_writers = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_w_per_block ) );
624 522 : int lg_depth = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*pack_depth ) );
625 522 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
626 :
627 :
628 522 : pack->pool = trp_pool_join( FD_SCRATCH_ALLOC_APPEND( l, trp_pool_align(), trp_pool_footprint ( pack_depth+1UL ) ) );
629 522 : pack->expiration_q = expq_join ( FD_SCRATCH_ALLOC_APPEND( l, expq_align(), expq_footprint ( pack_depth+1UL ) ) );
630 522 : pack->acct_in_use = acct_uses_join( FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) ) );
631 522 : pack->writer_costs = acct_uses_join( FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_max_writers ) ) );
632 522 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t*)*written_list_max );
633 522 : pack->signature_map = sig2txn_join( FD_SCRATCH_ALLOC_APPEND( l, sig2txn_align(), sig2txn_footprint ( lg_depth ) ) );
634 522 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight );
635 522 : pack->acct_to_bitset= bitset_map_join( FD_SCRATCH_ALLOC_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp) ) );
636 :
637 522 : FD_MGAUGE_SET( PACK, PENDING_TRANSACTIONS_HEAP_SIZE, pack_depth );
638 522 : return pack;
639 522 : }
640 :
641 :
642 :
643 : static int
644 : fd_pack_estimate_rewards_and_compute( fd_txn_e_t * txne,
645 13572666 : fd_pack_ord_txn_t * out ) {
646 13572666 : fd_txn_t * txn = TXN(txne->txnp);
647 13572666 : ulong sig_rewards = FD_PACK_FEE_PER_SIGNATURE * txn->signature_cnt; /* Easily in [5000, 635000] */
648 :
649 13572666 : ulong execution_cus;
650 13572666 : ulong adtl_rewards;
651 13572666 : ulong precompile_sigs;
652 13572666 : ulong cost = fd_pack_compute_cost( txn, txne->txnp->payload, &txne->txnp->flags, &execution_cus, &adtl_rewards, &precompile_sigs );
653 :
654 13572666 : if( FD_UNLIKELY( !cost ) ) return 0;
655 :
656 : /* precompile_sigs <= 16320, so after the addition,
657 : sig_rewards < 83,000,000 */
658 13572663 : sig_rewards += FD_PACK_FEE_PER_SIGNATURE * precompile_sigs;
659 :
660 : /* No fancy CU estimation in this version of pack
661 : for( ulong i=0UL; i<(ulong)txn->instr_cnt; i++ ) {
662 : uchar prog_id_idx = txn->instr[ i ].program_id;
663 : fd_acct_addr_t const * acct_addr = fd_txn_get_acct_addrs( txn, txnp->payload ) + (ulong)prog_id_idx;
664 : }
665 : */
666 13572663 : out->rewards = (adtl_rewards < (UINT_MAX - sig_rewards)) ? (uint)(sig_rewards + adtl_rewards) : UINT_MAX;
667 13572663 : out->compute_est = (uint)cost;
668 13572663 : out->txn->pack_cu.requested_execution_cus = (uint)execution_cus;
669 13572663 : out->txn->pack_cu.non_execution_cus = (uint)(cost - execution_cus);
670 :
671 13572663 : out->root = (txne->txnp->flags & FD_TXN_P_FLAGS_IS_SIMPLE_VOTE) ? FD_ORD_TXN_ROOT_PENDING_VOTE : FD_ORD_TXN_ROOT_PENDING;
672 :
673 : #if DETAILED_LOGGING
674 : FD_LOG_NOTICE(( "TXN estimated compute %lu+-%f. Rewards: %lu + %lu", compute_expected, (double)compute_variance, sig_rewards, adtl_rewards ));
675 : #endif
676 :
677 13572663 : return 1;
678 13572666 : }
679 :
680 : /* Can the fee payer afford to pay a transaction with the specified
681 : price? Returns 1 if so, 0 otherwise. This is just a stub that
682 : always returns 1 for now. In general, this function can't be totally
683 : accurate, because the transactions immediately prior to this one can
684 : affect the balance of this fee payer, but a simple check here may be
685 : helpful for reducing spam. */
686 : static int
687 : fd_pack_can_fee_payer_afford( fd_acct_addr_t const * acct_addr,
688 13572663 : ulong price /* in lamports */) {
689 13572663 : (void)acct_addr;
690 13572663 : (void)price;
691 13572663 : return 1;
692 13572663 : }
693 :
694 :
695 :
696 :
697 :
698 13695066 : fd_txn_e_t * fd_pack_insert_txn_init( fd_pack_t * pack ) { return trp_pool_ele_acquire( pack->pool )->txn_e; }
699 122400 : 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 ); }
700 :
701 491637 : #define REJECT( reason ) do { \
702 491637 : trp_pool_ele_release( pack->pool, ord ); \
703 491637 : return FD_PACK_INSERT_REJECT_ ## reason; \
704 491637 : } while( 0 )
705 :
706 68152839 : #define ACCT_ITER_TO_PTR( iter ) (__extension__( { \
707 68152839 : ulong __idx = fd_txn_acct_iter_idx( iter ); \
708 68152839 : fd_ptr_if( __idx<fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ), accts, alt_adj )+__idx; \
709 68152839 : }))
710 :
711 : int
712 : fd_pack_insert_txn_fini( fd_pack_t * pack,
713 : fd_txn_e_t * txne,
714 13572666 : ulong expires_at ) {
715 :
716 13572666 : fd_pack_ord_txn_t * ord = (fd_pack_ord_txn_t *)txne;
717 :
718 13572666 : fd_txn_t * txn = TXN(txne->txnp);
719 13572666 : uchar * payload = txne->txnp->payload;
720 :
721 13572666 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, payload );
722 : /* alt_adj is the pointer to the ALT expansion, adjusted so that if
723 : account address n is the first that comes from the ALT, it can be
724 : accessed with adj_lut[n]. */
725 13572666 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
726 13572666 : fd_acct_addr_t const * alt_adj = ord->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
727 13572666 : ulong imm_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
728 13572666 : ulong alt_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALT );
729 :
730 13572666 : if( FD_UNLIKELY( !fd_pack_estimate_rewards_and_compute( txne, ord ) ) ) REJECT( ESTIMATION_FAIL );
731 :
732 13572663 : ord->expires_at = expires_at;
733 13572663 : int is_vote = ord->root==FD_ORD_TXN_ROOT_PENDING_VOTE;
734 :
735 13572663 : int writes_to_sysvar = 0;
736 13572663 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
737 28316622 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
738 14743959 : writes_to_sysvar |= fd_pack_unwritable_contains( ACCT_ITER_TO_PTR( iter ) );
739 14743959 : }
740 :
741 13572663 : int bundle_blacklist = 0;
742 13572663 : if( FD_UNLIKELY( pack->use_bundles ) ) {
743 0 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_ALL );
744 0 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
745 0 : bundle_blacklist |= fd_pack_tip_prog_check_blacklist( ACCT_ITER_TO_PTR( iter ) );
746 0 : }
747 0 : }
748 :
749 13572663 : fd_ed25519_sig_t const * sig = fd_txn_get_signatures( txn, payload );
750 13572663 : fd_chkdup_t * chkdup = pack->chkdup;
751 :
752 : /* Throw out transactions ... */
753 : /* ... that are unfunded */
754 13572663 : if( FD_UNLIKELY( !fd_pack_can_fee_payer_afford( accts, ord->rewards ) ) ) REJECT( UNAFFORDABLE );
755 : /* ... that are so big they'll never run */
756 13572663 : if( FD_UNLIKELY( ord->compute_est >= pack->lim->max_cost_per_block ) ) REJECT( TOO_LARGE );
757 : /* ... that load too many accounts (ignoring 9LZdXeKGeBV6hRLdxS1rHbHoEUsKqesCC2ZAPTPKJAbK) */
758 13572663 : if( FD_UNLIKELY( fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALL )>64UL ) ) REJECT( ACCOUNT_CNT );
759 : /* ... that duplicate an account address */
760 13572660 : if( FD_UNLIKELY( fd_chkdup_check( chkdup, accts, imm_cnt, alt, alt_cnt ) ) ) REJECT( DUPLICATE_ACCT );
761 : /* ... that try to write to a sysvar */
762 13572657 : if( FD_UNLIKELY( writes_to_sysvar ) ) REJECT( WRITES_SYSVAR );
763 : /* ... that we already know about */
764 13572570 : if( FD_UNLIKELY( sig2txn_query( pack->signature_map, sig, NULL ) ) ) REJECT( DUPLICATE );
765 : /* ... that have already expired */
766 13572567 : if( FD_UNLIKELY( expires_at<pack->expire_before ) ) REJECT( EXPIRED );
767 : /* ... that use an account that violates bundle rules */
768 13572555 : if( FD_UNLIKELY( bundle_blacklist & 1 ) ) REJECT( BUNDLE_BLACKLIST );
769 :
770 :
771 13572555 : int replaces = 0;
772 13572555 : if( FD_UNLIKELY( pack->pending_txn_cnt == pack->pack_depth ) ) {
773 : /* If the tree is full, we want to see if this is better than the
774 : worst element in the treap before inserting. If the new
775 : transaction is better than that one, we'll delete it and insert
776 : the new transaction. Otherwise, we'll throw away this
777 : transaction. We want to make sure we provide reasonable quality
778 : of service for votes based on what fraction of the treap is votes
779 : though, so we'll employ the following policy:
780 :
781 : Case New Vote New Non-vote
782 : Votes < 25% Replace worst non-vote If better, replace worst
783 : with it non-vote with it
784 :
785 : Votes > 75% If better, replace Replace worst vote with
786 : worst vote with it it
787 :
788 : Else If better, replace worse of worst non-vote and
789 : worst vote */
790 494649 : ulong vote_cnt = treap_ele_cnt( pack->pending_votes ); int low_votes = (vote_cnt <(pack->pack_depth>>2));
791 494649 : ulong non_vote_cnt = treap_ele_cnt( pack->pending ); int low_nonvotes = (non_vote_cnt<(pack->pack_depth>>2));
792 494649 : int pool_imbalanced = low_votes | low_nonvotes;
793 494649 : int improves_balance = (low_votes & is_vote) | (low_nonvotes & !is_vote);
794 :
795 : /* Need to check that corresponding treap was not empty before dereferencing
796 : these two pointers. */
797 494649 : fd_pack_ord_txn_t * worst_vote = treap_fwd_iter_ele( treap_fwd_iter_init( pack->pending_votes, pack->pool ), pack->pool );
798 494649 : fd_pack_ord_txn_t * worst_nonvote = treap_fwd_iter_ele( treap_fwd_iter_init( pack->pending, pack->pool ), pack->pool );
799 494649 : fd_pack_ord_txn_t * worst = NULL;
800 :
801 : /* In the imbalanced case, there are two symmetric cases.
802 : Considering just the first one, low_nonvotes==true implies
803 : vote_cnt > pack_depth - (pack_depth>>2)
804 : Which means vote_cnt>0. In the imbalanced case when
805 : low_nonvotes==false, we know low_votes must be true, so similar
806 : logic applies.
807 : In the balanced case, vote_cnt and non_vote_cnt are both at least
808 : as large as (pack_depth>>2) >= 1, since pack_depth>=4 so
809 : worst_vote and worst_nonvote are safe, implying worst is safe. */
810 494649 : if( pool_imbalanced ) worst = fd_ptr_if( low_nonvotes, worst_vote, worst_nonvote );
811 42 : else worst = fd_ptr_if( COMPARE_WORSE( worst_vote, worst_nonvote ), worst_vote, worst_nonvote );
812 :
813 494649 : if( FD_LIKELY( improves_balance || COMPARE_WORSE( worst, ord ) ) ) {
814 3123 : replaces = 1;
815 3123 : fd_ed25519_sig_t const * worst_sig = fd_txn_get_signatures( TXN( worst->txn ), worst->txn->payload );
816 3123 : fd_pack_delete_transaction( pack, worst_sig );
817 491526 : } else {
818 491526 : REJECT( PRIORITY );
819 491526 : }
820 494649 : }
821 :
822 : /* At this point, we know we have space to insert the transaction and
823 : we've committed to insert it. */
824 :
825 13081029 : FD_PACK_BITSET_CLEAR( ord->rw_bitset );
826 13081029 : FD_PACK_BITSET_CLEAR( ord->w_bitset );
827 :
828 13081029 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
829 27333174 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
830 14252145 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
831 14252145 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, acct, NULL );
832 14252145 : if( FD_UNLIKELY( q==NULL ) ) {
833 12767358 : q = bitset_map_insert( pack->acct_to_bitset, acct );
834 12767358 : q->ref_cnt = 0UL;
835 12767358 : q->first_instance = ord;
836 12767358 : q->first_instance_was_write = 1;
837 12767358 : q->bit = FD_PACK_BITSET_FIRST_INSTANCE;
838 12767358 : } else if( FD_UNLIKELY( q->bit == FD_PACK_BITSET_FIRST_INSTANCE ) ) {
839 5982 : q->bit = pack->bitset_avail[ pack->bitset_avail_cnt ];
840 5982 : pack->bitset_avail_cnt = fd_ulong_if( !!pack->bitset_avail_cnt, pack->bitset_avail_cnt-1UL, 0UL );
841 :
842 5982 : FD_PACK_BITSET_SETN( q->first_instance->rw_bitset, q->bit );
843 5982 : if( q->first_instance_was_write ) FD_PACK_BITSET_SETN( q->first_instance->w_bitset, q->bit );
844 5982 : }
845 :
846 14252145 : q->ref_cnt++;
847 14252145 : FD_PACK_BITSET_SETN( ord->rw_bitset, q->bit );
848 14252145 : FD_PACK_BITSET_SETN( ord->w_bitset , q->bit );
849 14252145 : }
850 :
851 13081029 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
852 16643970 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
853 :
854 3562941 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
855 3562941 : if( FD_UNLIKELY( fd_pack_unwritable_contains( &acct ) ) ) continue;
856 :
857 2571744 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, acct, NULL );
858 2571744 : if( FD_UNLIKELY( q==NULL ) ) {
859 23733 : q = bitset_map_insert( pack->acct_to_bitset, acct );
860 23733 : q->ref_cnt = 0UL;
861 23733 : q->first_instance = ord;
862 23733 : q->first_instance_was_write = 0;
863 23733 : q->bit = FD_PACK_BITSET_FIRST_INSTANCE;
864 2548011 : } else if( FD_UNLIKELY( q->bit == FD_PACK_BITSET_FIRST_INSTANCE ) ) {
865 10638 : q->bit = pack->bitset_avail[ pack->bitset_avail_cnt ];
866 10638 : pack->bitset_avail_cnt = fd_ulong_if( !!pack->bitset_avail_cnt, pack->bitset_avail_cnt-1UL, 0UL );
867 :
868 10638 : FD_PACK_BITSET_SETN( q->first_instance->rw_bitset, q->bit );
869 10638 : if( q->first_instance_was_write ) FD_PACK_BITSET_SETN( q->first_instance->w_bitset, q->bit );
870 10638 : }
871 :
872 2571744 : q->ref_cnt++;
873 2571744 : FD_PACK_BITSET_SETN( ord->rw_bitset, q->bit );
874 2571744 : }
875 :
876 13081029 : pack->pending_txn_cnt++;
877 :
878 13081029 : sig2txn_insert( pack->signature_map, fd_txn_get_signatures( txn, payload ) );
879 :
880 13081029 : fd_pack_expq_t temp[ 1 ] = {{ .expires_at = expires_at, .txn = ord }};
881 13081029 : expq_insert( pack->expiration_q, temp );
882 :
883 13081029 : fd_pack_smallest_t * smallest = fd_ptr_if( is_vote, &pack->pending_votes_smallest[0], pack->pending_smallest );
884 13081029 : smallest->cus = fd_ulong_min( smallest->cus, ord->compute_est );
885 13081029 : smallest->bytes = fd_ulong_min( smallest->bytes, txne->txnp->payload_sz );
886 :
887 13081029 : if( FD_LIKELY( is_vote ) ) {
888 37644 : treap_ele_insert( pack->pending_votes, ord, pack->pool );
889 37644 : return replaces ? FD_PACK_INSERT_ACCEPT_VOTE_REPLACE : FD_PACK_INSERT_ACCEPT_VOTE_ADD;
890 13043385 : } else {
891 13043385 : treap_ele_insert( pack->pending, ord, pack->pool );
892 13043385 : return replaces ? FD_PACK_INSERT_ACCEPT_NONVOTE_REPLACE : FD_PACK_INSERT_ACCEPT_NONVOTE_ADD;
893 13043385 : }
894 13081029 : }
895 : #undef REJECT
896 :
897 : void
898 0 : fd_pack_metrics_write( fd_pack_t const * pack ) {
899 0 : FD_MGAUGE_SET( PACK, AVAILABLE_TRANSACTIONS, pack->pending_txn_cnt );
900 0 : FD_MGAUGE_SET( PACK, AVAILABLE_VOTE_TRANSACTIONS, treap_ele_cnt( pack->pending_votes ) );
901 0 : }
902 :
903 : typedef struct {
904 : ushort clear_rw_bit;
905 : ushort clear_w_bit;
906 : } release_result_t;
907 :
908 : static inline release_result_t
909 : release_bit_reference( fd_pack_t * pack,
910 16822779 : fd_acct_addr_t const * acct ) {
911 :
912 16822779 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, *acct, NULL );
913 16822779 : FD_TEST( q ); /* q==NULL not be possible */
914 :
915 16822779 : q->ref_cnt--;
916 :
917 16822779 : if( FD_UNLIKELY( q->ref_cnt==0UL ) ) {
918 12790089 : ushort bit = q->bit;
919 12790089 : bitset_map_remove( pack->acct_to_bitset, q );
920 12790089 : if( FD_LIKELY( bit<FD_PACK_BITSET_MAX ) ) pack->bitset_avail[ ++(pack->bitset_avail_cnt) ] = bit;
921 :
922 12790089 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, *acct, NULL );
923 12790089 : if( FD_LIKELY( use ) ) {
924 12786849 : use->in_use_by |= FD_PACK_IN_USE_BIT_CLEARED;
925 12786849 : release_result_t ret = { .clear_rw_bit = bit,
926 12786849 : .clear_w_bit = fd_ushort_if( !!(use->in_use_by & FD_PACK_IN_USE_WRITABLE), bit, FD_PACK_BITSET_MAX ) };
927 12786849 : return ret;
928 12786849 : }
929 12790089 : }
930 4035930 : release_result_t ret = { .clear_rw_bit = FD_PACK_BITSET_MAX, .clear_w_bit = FD_PACK_BITSET_MAX };
931 4035930 : return ret;
932 16822779 : }
933 :
934 : typedef struct {
935 : ulong cus_scheduled;
936 : ulong txns_scheduled;
937 : ulong bytes_scheduled;
938 : } sched_return_t;
939 :
940 : static inline sched_return_t
941 : fd_pack_schedule_impl( fd_pack_t * pack,
942 : treap_t * sched_from,
943 : ulong cu_limit,
944 : ulong txn_limit,
945 : ulong byte_limit,
946 : ulong bank_tile,
947 : fd_pack_smallest_t * smallest_in_treap,
948 2214648 : fd_txn_p_t * out ) {
949 :
950 2214648 : fd_pack_ord_txn_t * pool = pack->pool;
951 2214648 : fd_pack_addr_use_t * acct_in_use = pack->acct_in_use;
952 2214648 : fd_pack_addr_use_t * writer_costs = pack->writer_costs;
953 :
954 2214648 : fd_pack_addr_use_t ** written_list = pack->written_list;
955 2214648 : ulong written_list_cnt = pack->written_list_cnt;
956 2214648 : ulong written_list_max = pack->written_list_max;
957 :
958 2214648 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
959 2214648 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
960 2214648 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
961 2214648 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
962 :
963 2214648 : fd_pack_addr_use_t * use_by_bank = pack->use_by_bank [bank_tile];
964 2214648 : ulong use_by_bank_cnt = pack->use_by_bank_cnt[bank_tile];
965 :
966 2214648 : ulong max_write_cost_per_acct = pack->lim->max_write_cost_per_acct;
967 :
968 2214648 : ulong txns_scheduled = 0UL;
969 2214648 : ulong cus_scheduled = 0UL;
970 2214648 : ulong bytes_scheduled = 0UL;
971 :
972 2214648 : ulong bank_tile_mask = 1UL << bank_tile;
973 :
974 2214648 : ulong fast_path = 0UL;
975 2214648 : ulong slow_path = 0UL;
976 2214648 : ulong cu_limit_c = 0UL;
977 2214648 : ulong byte_limit_c = 0UL;
978 2214648 : ulong write_limit_c = 0UL;
979 :
980 2214648 : ulong min_cus = ULONG_MAX;
981 2214648 : ulong min_bytes = ULONG_MAX;
982 :
983 2214648 : if( FD_UNLIKELY( (cu_limit<smallest_in_treap->cus) | (txn_limit==0UL) | (byte_limit<smallest_in_treap->bytes) ) ) {
984 1454805 : sched_return_t to_return = { .cus_scheduled = 0UL, .txns_scheduled = 0UL, .bytes_scheduled = 0UL };
985 1454805 : return to_return;
986 1454805 : }
987 :
988 759843 : treap_rev_iter_t prev = treap_idx_null();
989 121100577 : for( treap_rev_iter_t _cur=treap_rev_iter_init( sched_from, pool ); !treap_rev_iter_done( _cur ); _cur=prev ) {
990 : /* Capture next so that we can delete while we iterate. */
991 120934905 : prev = treap_rev_iter_next( _cur, pool );
992 :
993 120934905 : # if FD_HAS_X86
994 120934905 : _mm_prefetch( &(pool[ prev ].prev), _MM_HINT_T0 );
995 120934905 : # endif
996 :
997 120934905 : fd_pack_ord_txn_t const * cur = treap_rev_iter_ele_const( _cur, pool );
998 :
999 120934905 : min_cus = fd_ulong_min( min_cus, cur->compute_est );
1000 120934905 : min_bytes = fd_ulong_min( min_bytes, cur->txn->payload_sz );
1001 :
1002 120934905 : ulong conflicts = 0UL;
1003 :
1004 120934905 : if( FD_UNLIKELY( cur->compute_est>cu_limit ) ) {
1005 : /* Too big to be scheduled at the moment, but might be okay for
1006 : the next microblock, so we don't want to delay it. */
1007 0 : cu_limit_c++;
1008 0 : continue;
1009 0 : }
1010 :
1011 : /* Likely? Unlikely? */
1012 120934905 : if( FD_LIKELY( !FD_PACK_BITSET_INTERSECT4_EMPTY( bitset_rw_in_use, bitset_w_in_use, cur->w_bitset, cur->rw_bitset ) ) ) {
1013 107857518 : fast_path++;
1014 107857518 : continue;
1015 107857518 : }
1016 :
1017 13077387 : if( FD_UNLIKELY( cur->txn->payload_sz>byte_limit ) ) {
1018 0 : byte_limit_c++;
1019 0 : continue;
1020 0 : }
1021 :
1022 13077387 : fd_txn_t const * txn = TXN(cur->txn);
1023 13077387 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
1024 13077387 : fd_acct_addr_t const * alt_adj = cur->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1025 : /* Check conflicts between this transaction's writable accounts and
1026 : current readers */
1027 13077387 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1028 27316080 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1029 :
1030 14238705 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1031 :
1032 14238705 : fd_pack_addr_use_t * in_wcost_table = acct_uses_query( writer_costs, acct, NULL );
1033 14238705 : if( FD_UNLIKELY( in_wcost_table && in_wcost_table->total_cost+cur->compute_est > max_write_cost_per_acct ) ) {
1034 : /* Can't be scheduled until the next block */
1035 12 : conflicts = ULONG_MAX;
1036 12 : break;
1037 12 : }
1038 :
1039 14238693 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, acct, NULL );
1040 14238693 : if( FD_UNLIKELY( use ) ) conflicts |= use->in_use_by; /* break? */
1041 14238693 : }
1042 :
1043 13077387 : if( FD_UNLIKELY( conflicts==ULONG_MAX ) ) {
1044 12 : write_limit_c++;
1045 12 : continue;
1046 12 : }
1047 :
1048 13077375 : if( FD_UNLIKELY( conflicts ) ) {
1049 12 : slow_path++;
1050 12 : continue;
1051 12 : }
1052 :
1053 : /* Check conflicts between this transaction's readonly accounts and
1054 : current writers */
1055 13077363 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1056 16623162 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1057 :
1058 3545799 : fd_acct_addr_t const * acct = ACCT_ITER_TO_PTR( iter );
1059 3545799 : if( fd_pack_unwritable_contains( acct ) ) continue; /* No need to track sysvars because they can't be writable */
1060 :
1061 2559288 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, *acct, NULL );
1062 2559288 : if( use ) conflicts |= (use->in_use_by & FD_PACK_IN_USE_WRITABLE) ? use->in_use_by : 0UL;
1063 2559288 : }
1064 :
1065 13077363 : if( FD_UNLIKELY( conflicts ) ) {
1066 0 : slow_path++;
1067 0 : continue;
1068 0 : }
1069 :
1070 : /* Include this transaction in the microblock! */
1071 13077363 : FD_PACK_BITSET_OR( bitset_rw_in_use, cur->rw_bitset );
1072 13077363 : FD_PACK_BITSET_OR( bitset_w_in_use, cur->w_bitset );
1073 :
1074 13077363 : if(
1075 4359121 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
1076 4359121 : FD_LIKELY( cur->txn->payload_sz>=1024UL )
1077 : #else
1078 8718242 : 0
1079 8718242 : #endif
1080 13077363 : ) {
1081 4225 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
1082 4225 : _mm512_stream_si512( (void*)(out->payload+ 0UL), _mm512_load_epi64( cur->txn->payload+ 0UL ) );
1083 4225 : _mm512_stream_si512( (void*)(out->payload+ 64UL), _mm512_load_epi64( cur->txn->payload+ 64UL ) );
1084 4225 : _mm512_stream_si512( (void*)(out->payload+ 128UL), _mm512_load_epi64( cur->txn->payload+ 128UL ) );
1085 4225 : _mm512_stream_si512( (void*)(out->payload+ 192UL), _mm512_load_epi64( cur->txn->payload+ 192UL ) );
1086 4225 : _mm512_stream_si512( (void*)(out->payload+ 256UL), _mm512_load_epi64( cur->txn->payload+ 256UL ) );
1087 4225 : _mm512_stream_si512( (void*)(out->payload+ 320UL), _mm512_load_epi64( cur->txn->payload+ 320UL ) );
1088 4225 : _mm512_stream_si512( (void*)(out->payload+ 384UL), _mm512_load_epi64( cur->txn->payload+ 384UL ) );
1089 4225 : _mm512_stream_si512( (void*)(out->payload+ 448UL), _mm512_load_epi64( cur->txn->payload+ 448UL ) );
1090 4225 : _mm512_stream_si512( (void*)(out->payload+ 512UL), _mm512_load_epi64( cur->txn->payload+ 512UL ) );
1091 4225 : _mm512_stream_si512( (void*)(out->payload+ 576UL), _mm512_load_epi64( cur->txn->payload+ 576UL ) );
1092 4225 : _mm512_stream_si512( (void*)(out->payload+ 640UL), _mm512_load_epi64( cur->txn->payload+ 640UL ) );
1093 4225 : _mm512_stream_si512( (void*)(out->payload+ 704UL), _mm512_load_epi64( cur->txn->payload+ 704UL ) );
1094 4225 : _mm512_stream_si512( (void*)(out->payload+ 768UL), _mm512_load_epi64( cur->txn->payload+ 768UL ) );
1095 4225 : _mm512_stream_si512( (void*)(out->payload+ 832UL), _mm512_load_epi64( cur->txn->payload+ 832UL ) );
1096 4225 : _mm512_stream_si512( (void*)(out->payload+ 896UL), _mm512_load_epi64( cur->txn->payload+ 896UL ) );
1097 4225 : _mm512_stream_si512( (void*)(out->payload+ 960UL), _mm512_load_epi64( cur->txn->payload+ 960UL ) );
1098 4225 : _mm512_stream_si512( (void*)(out->payload+1024UL), _mm512_load_epi64( cur->txn->payload+1024UL ) );
1099 4225 : _mm512_stream_si512( (void*)(out->payload+1088UL), _mm512_load_epi64( cur->txn->payload+1088UL ) );
1100 4225 : _mm512_stream_si512( (void*)(out->payload+1152UL), _mm512_load_epi64( cur->txn->payload+1152UL ) );
1101 4225 : _mm512_stream_si512( (void*)(out->payload+1216UL), _mm512_load_epi64( cur->txn->payload+1216UL ) );
1102 : /* Copied out to 1280 bytes, which copies some other fields we needed to
1103 : copy anyway. */
1104 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, payload_sz )+sizeof(((fd_txn_p_t*)NULL)->payload_sz )<=1280UL, nt_memcpy );
1105 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, blockhash_slot )+sizeof(((fd_txn_p_t*)NULL)->blockhash_slot)<=1280UL, nt_memcpy );
1106 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, flags )+sizeof(((fd_txn_p_t*)NULL)->flags )<=1280UL, nt_memcpy );
1107 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, _ ) <=1280UL, nt_memcpy );
1108 4225 : const ulong offset_into_txn = 1280UL - offsetof(fd_txn_p_t, _ );
1109 4225 : fd_memcpy( offset_into_txn+(uchar *)TXN(out), offset_into_txn+(uchar const *)txn,
1110 4225 : fd_ulong_max( offset_into_txn, fd_txn_footprint( txn->instr_cnt, txn->addr_table_lookup_cnt ) )-offset_into_txn );
1111 4225 : #endif
1112 13073138 : } else {
1113 13073138 : fd_memcpy( out->payload, cur->txn->payload, cur->txn->payload_sz );
1114 13073138 : fd_memcpy( TXN(out), txn, fd_txn_footprint( txn->instr_cnt, txn->addr_table_lookup_cnt ) );
1115 13073138 : out->payload_sz = cur->txn->payload_sz;
1116 13073138 : out->pack_cu.requested_execution_cus = cur->txn->pack_cu.requested_execution_cus;
1117 13073138 : out->pack_cu.non_execution_cus = cur->txn->pack_cu.non_execution_cus;
1118 13073138 : out->flags = cur->txn->flags;
1119 13073138 : }
1120 13077363 : out++;
1121 :
1122 13077363 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1123 27316032 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1124 14238669 : fd_acct_addr_t acct_addr = *ACCT_ITER_TO_PTR( iter );
1125 :
1126 14238669 : fd_pack_addr_use_t * in_wcost_table = acct_uses_query( writer_costs, acct_addr, NULL );
1127 14238669 : if( !in_wcost_table ) {
1128 787788 : in_wcost_table = acct_uses_insert( writer_costs, acct_addr );
1129 787788 : in_wcost_table->total_cost = 0UL;
1130 787788 : written_list[ written_list_cnt ] = in_wcost_table;
1131 787788 : written_list_cnt = fd_ulong_min( written_list_cnt+1UL, written_list_max-1UL );
1132 787788 : }
1133 14238669 : in_wcost_table->total_cost += cur->compute_est;
1134 :
1135 14238669 : fd_pack_addr_use_t * use = acct_uses_insert( acct_in_use, acct_addr );
1136 14238669 : use->in_use_by = bank_tile_mask | FD_PACK_IN_USE_WRITABLE;
1137 :
1138 14238669 : use_by_bank[use_by_bank_cnt++] = *use;
1139 :
1140 : /* If there aren't any more references to this account in the
1141 : heap, it can't cause any conflicts. That means we actually
1142 : don't need to record that we are using it, which is good
1143 : because we want to release the bit. */
1144 14238669 : release_result_t ret = release_bit_reference( pack, &acct_addr );
1145 14238669 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
1146 14238669 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
1147 14238669 : }
1148 13077363 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1149 16623162 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1150 :
1151 3545799 : fd_acct_addr_t acct_addr = *ACCT_ITER_TO_PTR( iter );
1152 :
1153 3545799 : if( fd_pack_unwritable_contains( &acct_addr ) ) continue; /* No need to track sysvars because they can't be writable */
1154 :
1155 2559288 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, acct_addr, NULL );
1156 2559288 : if( !use ) { use = acct_uses_insert( acct_in_use, acct_addr ); use->in_use_by = 0UL; }
1157 :
1158 2559288 : if( !(use->in_use_by & bank_tile_mask) ) use_by_bank[use_by_bank_cnt++] = *use;
1159 2559288 : use->in_use_by |= bank_tile_mask;
1160 2559288 : use->in_use_by &= ~FD_PACK_IN_USE_BIT_CLEARED;
1161 :
1162 :
1163 2559288 : release_result_t ret = release_bit_reference( pack, &acct_addr );
1164 2559288 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
1165 2559288 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
1166 2559288 : }
1167 :
1168 13077363 : txns_scheduled += 1UL; txn_limit -= 1UL;
1169 13077363 : cus_scheduled += cur->compute_est; cu_limit -= cur->compute_est;
1170 13077363 : bytes_scheduled += cur->txn->payload_sz; byte_limit -= cur->txn->payload_sz;
1171 :
1172 13077363 : fd_ed25519_sig_t const * sig0 = fd_txn_get_signatures( txn, cur->txn->payload );
1173 :
1174 13077363 : fd_pack_sig_to_txn_t * in_tbl = sig2txn_query( pack->signature_map, sig0, NULL );
1175 13077363 : sig2txn_remove( pack->signature_map, in_tbl );
1176 :
1177 13077363 : expq_remove( pack->expiration_q, cur->expq_idx );
1178 13077363 : treap_idx_remove( sched_from, _cur, pool );
1179 13077363 : trp_pool_idx_release( pool, _cur );
1180 13077363 : pack->pending_txn_cnt--;
1181 :
1182 13077363 : if( FD_UNLIKELY( (cu_limit<smallest_in_treap->cus) | (txn_limit==0UL) | (byte_limit<smallest_in_treap->bytes) ) ) break;
1183 13077363 : }
1184 :
1185 759843 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_TAKEN, txns_scheduled );
1186 759843 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_CU_LIMIT, cu_limit_c );
1187 759843 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_FAST_PATH, fast_path );
1188 759843 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_BYTE_LIMIT, byte_limit_c );
1189 759843 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_WRITE_COST, write_limit_c );
1190 759843 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_SLOW_PATH, slow_path );
1191 :
1192 : #if DETAILED_LOGGING
1193 : FD_LOG_NOTICE(( "cu_limit: %lu, fast_path: %lu, slow_path: %lu", cu_limit_c, fast_path, slow_path ));
1194 : #endif
1195 :
1196 : /* If we scanned the whole treap and didn't break early, we now have a
1197 : better estimate of the smallest. */
1198 759843 : if( FD_UNLIKELY( treap_rev_iter_done( prev ) ) ) {
1199 168714 : smallest_in_treap->cus = min_cus;
1200 168714 : smallest_in_treap->bytes = min_bytes;
1201 168714 : }
1202 :
1203 759843 : pack->use_by_bank_cnt[bank_tile] = use_by_bank_cnt;
1204 759843 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
1205 759843 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
1206 :
1207 759843 : pack->written_list_cnt = written_list_cnt;
1208 :
1209 759843 : sched_return_t to_return = { .cus_scheduled=cus_scheduled, .txns_scheduled=txns_scheduled, .bytes_scheduled=bytes_scheduled };
1210 759843 : return to_return;
1211 2214648 : }
1212 :
1213 : void
1214 : fd_pack_microblock_complete( fd_pack_t * pack,
1215 738216 : ulong bank_tile ) {
1216 : /* If the account is in use writably, and it's in use by this banking
1217 : tile, then this banking tile must be the sole writer to it, so it's
1218 : always okay to clear the writable bit. */
1219 738216 : ulong clear_mask = ~((1UL<<bank_tile) | FD_PACK_IN_USE_WRITABLE);
1220 :
1221 738216 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
1222 738216 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
1223 738216 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
1224 738216 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
1225 :
1226 738216 : fd_pack_addr_use_t * base = pack->use_by_bank[bank_tile];
1227 16920126 : for( ulong i=0UL; i<pack->use_by_bank_cnt[bank_tile]; i++ ) {
1228 16181910 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, base[i].key, NULL );
1229 16181910 : FD_TEST( use );
1230 16181910 : use->in_use_by &= clear_mask;
1231 :
1232 : /* In order to properly bound the size of bitset_map, we need to
1233 : release the "reference" to the account when we schedule it.
1234 : However, that poses a bit of a problem here, because by the time
1235 : we complete the microblock, that account could have been assigned
1236 : a different bit in the bitset. The scheduling step tells us if
1237 : that is the case, and if so, we know that the bits in
1238 : bitset_w_in_use and bitset_rw_in_use were already cleared as
1239 : necessary.
1240 :
1241 : Note that it's possible for BIT_CLEARED to be set and then unset
1242 : by later uses, but then the account would be in use on other
1243 : banks, so we wouldn't try to observe the old value. For example:
1244 : Suppose bit 0->account A, bit 1->account B, and we have two
1245 : transactions that read A, B. We schedule a microblock to bank 0,
1246 : taking both transactions, which sets the counts for A, B to 0,
1247 : and releases the bits, clearing bits 0 and 1, and setting
1248 : BIT_CLEARED. Then we get two more transactions that read
1249 : accounts C, D, A, B, and they get assigned 0->C, 1->D, 2->A,
1250 : 3->B. We try to schedule a microblock to bank 1 that takes one
1251 : of those transactions. This unsets BIT_CLEARED for A, B.
1252 : Finally, the first microblock completes. Even though the bitset
1253 : map has the new bits for A and B which are "wrong" compared to
1254 : when the transaction was initially scheduled, those bits have
1255 : already been cleared and reset properly in the bitset as needed.
1256 : A and B will still be in use by bank 1, so we won't clear any
1257 : bits. If, on the other hand, the microblock scheduled to bank 1
1258 : completes first, bits 0 and 1 will be cleared for accounts C and
1259 : D, while bits 2 and 3 will remain set, which is correct. Then
1260 : when bank 0 completes, bits 2 and 3 will be cleared. */
1261 16181910 : if( FD_LIKELY( !use->in_use_by ) ) { /* if in_use_by==0, doesn't include BIT_CLEARED */
1262 3403176 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, base[i].key, NULL );
1263 3403176 : FD_TEST( q );
1264 3403176 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, q->bit );
1265 3403176 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, q->bit );
1266 3403176 : }
1267 16181910 : if( FD_LIKELY( !(use->in_use_by & ~FD_PACK_IN_USE_BIT_CLEARED) ) ) acct_uses_remove( pack->acct_in_use, use );
1268 16181910 : }
1269 :
1270 738216 : pack->use_by_bank_cnt[bank_tile] = 0UL;
1271 :
1272 738216 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
1273 738216 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
1274 :
1275 : /* outstanding_microblock_mask never has the writable bit set, so we
1276 : don't care about clearing it here either. */
1277 738216 : pack->outstanding_microblock_mask &= clear_mask;
1278 738216 : }
1279 :
1280 :
1281 : ulong
1282 : fd_pack_schedule_next_microblock( fd_pack_t * pack,
1283 : ulong total_cus,
1284 : float vote_fraction,
1285 : ulong bank_tile,
1286 738216 : fd_txn_p_t * out ) {
1287 :
1288 : /* TODO: Decide if these are exactly how we want to handle limits */
1289 738216 : total_cus = fd_ulong_min( total_cus, pack->lim->max_cost_per_block - pack->cumulative_block_cost );
1290 738216 : ulong vote_cus = fd_ulong_min( (ulong)((float)total_cus * vote_fraction),
1291 738216 : pack->lim->max_vote_cost_per_block - pack->cumulative_vote_cost );
1292 738216 : ulong vote_reserved_txns = fd_ulong_min( vote_cus/FD_PACK_TYPICAL_VOTE_COST,
1293 738216 : (ulong)((float)pack->lim->max_txn_per_microblock * vote_fraction) );
1294 :
1295 :
1296 738216 : if( FD_UNLIKELY( (pack->microblock_cnt>=pack->lim->max_microblocks_per_block) ) ) {
1297 0 : FD_MCNT_INC( PACK, MICROBLOCK_PER_BLOCK_LIMIT, 1UL );
1298 0 : return 0UL;
1299 0 : }
1300 738216 : if( FD_UNLIKELY( pack->data_bytes_consumed+MICROBLOCK_DATA_OVERHEAD+FD_TXN_MIN_SERIALIZED_SZ>pack->lim->max_data_bytes_per_block) ) {
1301 0 : FD_MCNT_INC( PACK, DATA_PER_BLOCK_LIMIT, 1UL );
1302 0 : return 0UL;
1303 0 : }
1304 :
1305 738216 : ulong cu_limit = total_cus - vote_cus;
1306 738216 : ulong txn_limit = pack->lim->max_txn_per_microblock - vote_reserved_txns;
1307 738216 : ulong scheduled = 0UL;
1308 738216 : ulong byte_limit = pack->lim->max_data_bytes_per_block - pack->data_bytes_consumed - MICROBLOCK_DATA_OVERHEAD;
1309 :
1310 738216 : sched_return_t status, status1;
1311 :
1312 : /* Try to schedule non-vote transactions */
1313 738216 : status = fd_pack_schedule_impl( pack, pack->pending, cu_limit, txn_limit, byte_limit, bank_tile, pack->pending_smallest, out+scheduled );
1314 :
1315 738216 : scheduled += status.txns_scheduled; txn_limit -= status.txns_scheduled;
1316 738216 : pack->cumulative_block_cost += status.cus_scheduled; cu_limit -= status.cus_scheduled;
1317 738216 : pack->data_bytes_consumed += status.bytes_scheduled; byte_limit -= status.bytes_scheduled;
1318 :
1319 :
1320 : /* Schedule vote transactions */
1321 738216 : status1= fd_pack_schedule_impl( pack, pack->pending_votes, vote_cus, vote_reserved_txns, byte_limit, bank_tile, pack->pending_votes_smallest, out+scheduled );
1322 :
1323 738216 : scheduled += status1.txns_scheduled;
1324 738216 : pack->cumulative_vote_cost += status1.cus_scheduled;
1325 738216 : pack->cumulative_block_cost += status1.cus_scheduled;
1326 738216 : pack->data_bytes_consumed += status1.bytes_scheduled;
1327 738216 : byte_limit -= status1.bytes_scheduled;
1328 : /* Add any remaining CUs/txns to the non-vote limits */
1329 738216 : txn_limit += vote_reserved_txns - status1.txns_scheduled;
1330 738216 : cu_limit += vote_cus - status1.cus_scheduled;
1331 :
1332 :
1333 : /* Fill any remaining space with non-vote transactions */
1334 738216 : status = fd_pack_schedule_impl( pack, pack->pending, cu_limit, txn_limit, byte_limit, bank_tile, pack->pending_smallest, out+scheduled );
1335 :
1336 738216 : scheduled += status.txns_scheduled;
1337 738216 : pack->cumulative_block_cost += status.cus_scheduled;
1338 738216 : pack->data_bytes_consumed += status.bytes_scheduled;
1339 :
1340 738216 : ulong nonempty = (ulong)(scheduled>0UL);
1341 738216 : pack->microblock_cnt += nonempty;
1342 738216 : pack->outstanding_microblock_mask |= nonempty << bank_tile;
1343 738216 : pack->data_bytes_consumed += nonempty * MICROBLOCK_DATA_OVERHEAD;
1344 :
1345 : /* Update metrics counters */
1346 738216 : FD_MGAUGE_SET( PACK, AVAILABLE_TRANSACTIONS, pack->pending_txn_cnt );
1347 738216 : FD_MGAUGE_SET( PACK, AVAILABLE_VOTE_TRANSACTIONS, treap_ele_cnt( pack->pending_votes ) );
1348 738216 : FD_MGAUGE_SET( PACK, CUS_CONSUMED_IN_BLOCK, pack->cumulative_block_cost );
1349 :
1350 738216 : fd_histf_sample( pack->txn_per_microblock, scheduled );
1351 738216 : fd_histf_sample( pack->vote_per_microblock, status1.txns_scheduled );
1352 :
1353 246072 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
1354 246072 : _mm_sfence();
1355 246072 : #endif
1356 :
1357 738216 : return scheduled;
1358 738216 : }
1359 :
1360 268194 : ulong fd_pack_bank_tile_cnt( fd_pack_t const * pack ) { return pack->bank_tile_cnt; }
1361 :
1362 :
1363 : void
1364 : fd_pack_set_block_limits( fd_pack_t * pack,
1365 : ulong max_microblocks_per_block,
1366 0 : ulong max_data_bytes_per_block ) {
1367 0 : pack->lim->max_microblocks_per_block = max_microblocks_per_block;
1368 0 : pack->lim->max_data_bytes_per_block = max_data_bytes_per_block;
1369 0 : }
1370 :
1371 : void
1372 : fd_pack_rebate_cus( fd_pack_t * pack,
1373 : fd_txn_p_t const * txns,
1374 6 : ulong txn_cnt ) {
1375 6 : fd_pack_addr_use_t * writer_costs = pack->writer_costs;
1376 :
1377 6 : ulong cumulative_vote_cost = pack->cumulative_vote_cost;
1378 6 : ulong cumulative_block_cost = pack->cumulative_block_cost;
1379 6 : ulong data_bytes_consumed = pack->data_bytes_consumed;
1380 6 : ulong cumulative_rebated_cus = pack->cumulative_rebated_cus;
1381 :
1382 18 : for( ulong i=0UL; i<txn_cnt; i++ ) {
1383 12 : fd_txn_p_t const * txn = txns+i;
1384 12 : ulong rebated_cus = txn->bank_cu.rebated_cus;
1385 12 : int in_block = !!(txn->flags & FD_TXN_P_FLAGS_EXECUTE_SUCCESS);
1386 :
1387 12 : cumulative_block_cost -= rebated_cus;
1388 12 : cumulative_vote_cost -= fd_ulong_if( txn->flags & FD_TXN_P_FLAGS_IS_SIMPLE_VOTE, rebated_cus, 0UL );
1389 12 : data_bytes_consumed -= fd_ulong_if( !in_block, txn->payload_sz, 0UL );
1390 12 : cumulative_rebated_cus += rebated_cus;
1391 :
1392 12 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( TXN(txn), txn->payload );
1393 : /* TODO: For now, we don't have a way to rebate writer costs for ALT
1394 : accounts. We've thrown away the ALT expansion at this point.
1395 : The rebate system is going to be rewritten soon for performance,
1396 : so it's okay. */
1397 12 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( TXN(txn), FD_TXN_ACCT_CAT_WRITABLE & FD_TXN_ACCT_CAT_IMM );
1398 36 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1399 :
1400 24 : ulong i=fd_txn_acct_iter_idx( iter );
1401 :
1402 24 : fd_pack_addr_use_t * in_wcost_table = acct_uses_query( writer_costs, accts[i], NULL );
1403 24 : if( FD_UNLIKELY( !in_wcost_table ) ) FD_LOG_ERR(( "Rebate to unknown written account" ));
1404 24 : in_wcost_table->total_cost -= rebated_cus;
1405 : /* Important: Even if this is 0, don't delete it from the table so
1406 : that the insert order doesn't get messed up. */
1407 24 : }
1408 12 : }
1409 :
1410 6 : pack->cumulative_vote_cost = cumulative_vote_cost;
1411 6 : pack->cumulative_block_cost = cumulative_block_cost;
1412 6 : pack->data_bytes_consumed = data_bytes_consumed;
1413 6 : pack->cumulative_rebated_cus = cumulative_rebated_cus;
1414 6 : }
1415 :
1416 :
1417 : ulong
1418 : fd_pack_expire_before( fd_pack_t * pack,
1419 9 : ulong expire_before ) {
1420 9 : expire_before = fd_ulong_max( expire_before, pack->expire_before );
1421 9 : ulong deleted_cnt = 0UL;
1422 9 : fd_pack_expq_t * prq = pack->expiration_q;
1423 18 : while( (expq_cnt( prq )>0UL) & (prq->expires_at<expire_before) ) {
1424 9 : fd_pack_ord_txn_t * expired = prq->txn;
1425 :
1426 9 : fd_ed25519_sig_t const * expired_sig = fd_txn_get_signatures( TXN( expired->txn ), expired->txn->payload );
1427 : /* fd_pack_delete_transaction also removes it from the heap */
1428 9 : fd_pack_delete_transaction( pack, expired_sig );
1429 9 : deleted_cnt++;
1430 9 : }
1431 :
1432 9 : pack->expire_before = expire_before;
1433 9 : return deleted_cnt;
1434 9 : }
1435 :
1436 : void
1437 2646 : fd_pack_end_block( fd_pack_t * pack ) {
1438 2646 : fd_histf_sample( pack->net_cus_per_block, pack->cumulative_block_cost );
1439 2646 : fd_histf_sample( pack->rebated_cus_per_block, pack->cumulative_rebated_cus );
1440 2646 : fd_histf_sample( pack->scheduled_cus_per_block, pack->cumulative_rebated_cus + pack->cumulative_block_cost );
1441 :
1442 2646 : pack->microblock_cnt = 0UL;
1443 2646 : pack->data_bytes_consumed = 0UL;
1444 2646 : pack->cumulative_block_cost = 0UL;
1445 2646 : pack->cumulative_vote_cost = 0UL;
1446 2646 : pack->cumulative_rebated_cus = 0UL;
1447 :
1448 2646 : acct_uses_clear( pack->acct_in_use );
1449 :
1450 2646 : if( FD_LIKELY( pack->written_list_cnt<pack->written_list_max-1UL ) ) {
1451 : /* The less dangerous way of doing this is to instead record the
1452 : keys we inserted and do a query followed by a delete for each
1453 : key. The downside of that is that keys are 32 bytes and a
1454 : pointer is only 8 bytes, plus the computational cost for the
1455 : query.
1456 :
1457 : However, if we're careful, we can pull this off. We require two
1458 : things. First, we started from an empty map and did nothing but
1459 : insert and update. In particular, no deletions. Second, we have
1460 : to be careful to delete in the opposite order that we inserted.
1461 : This is essentially like unwinding the inserts we did. The
1462 : common case is that the element after the one we delete will be
1463 : empty, so we'll hit that case. It's possible that there's
1464 : another independent probe sequence that will be entirely intact
1465 : starting in the element after, but we'll never hit the MAP_MOVE
1466 : case. */
1467 776193 : for( ulong i=0UL; i<pack->written_list_cnt; i++ ) {
1468 773547 : acct_uses_remove( pack->writer_costs, pack->written_list[ pack->written_list_cnt - 1UL - i ] );
1469 773547 : }
1470 2646 : } else {
1471 0 : acct_uses_clear( pack->writer_costs );
1472 0 : }
1473 2646 : pack->written_list_cnt = 0UL;
1474 :
1475 2646 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
1476 2646 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
1477 :
1478 9234 : for( ulong i=0UL; i<pack->bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i] = 0UL;
1479 :
1480 : /* If our stake is low and we don't become leader often, end_block
1481 : might get called on the order of O(1/hr), which feels too
1482 : infrequent to do anything related to metrics. However, we only
1483 : update the histograms when we are leader, so this is actually a
1484 : good place to copy them. */
1485 2646 : FD_MHIST_COPY( PACK, TOTAL_TRANSACTIONS_PER_MICROBLOCK_COUNT, pack->txn_per_microblock );
1486 2646 : FD_MHIST_COPY( PACK, VOTES_PER_MICROBLOCK_COUNT, pack->vote_per_microblock );
1487 :
1488 2646 : FD_MGAUGE_SET( PACK, CUS_CONSUMED_IN_BLOCK, 0UL );
1489 2646 : FD_MHIST_COPY( PACK, CUS_SCHEDULED, pack->scheduled_cus_per_block );
1490 2646 : FD_MHIST_COPY( PACK, CUS_REBATED, pack->rebated_cus_per_block );
1491 2646 : FD_MHIST_COPY( PACK, CUS_NET, pack->net_cus_per_block );
1492 2646 : }
1493 :
1494 : static void
1495 : release_tree( treap_t * treap,
1496 0 : fd_pack_ord_txn_t * pool ) {
1497 0 : treap_fwd_iter_t next;
1498 0 : for( treap_fwd_iter_t it=treap_fwd_iter_init( treap, pool ); !treap_fwd_iter_idx( it ); it=next ) {
1499 0 : next = treap_fwd_iter_next( it, pool );
1500 0 : ulong idx = treap_fwd_iter_idx( it );
1501 0 : treap_idx_remove ( treap, idx, pool );
1502 0 : trp_pool_idx_release( pool, idx );
1503 0 : }
1504 0 : }
1505 :
1506 : void
1507 0 : fd_pack_clear_all( fd_pack_t * pack ) {
1508 0 : pack->pending_txn_cnt = 0UL;
1509 0 : pack->microblock_cnt = 0UL;
1510 0 : pack->cumulative_block_cost = 0UL;
1511 0 : pack->cumulative_vote_cost = 0UL;
1512 0 : pack->cumulative_rebated_cus = 0UL;
1513 :
1514 0 : pack->pending_smallest->cus = ULONG_MAX;
1515 0 : pack->pending_smallest->bytes = ULONG_MAX;
1516 0 : pack->pending_votes_smallest->cus = ULONG_MAX;
1517 0 : pack->pending_votes_smallest->bytes = ULONG_MAX;
1518 :
1519 0 : release_tree( pack->pending, pack->pool );
1520 0 : release_tree( pack->pending_votes, pack->pool );
1521 :
1522 0 : expq_remove_all( pack->expiration_q );
1523 :
1524 0 : acct_uses_clear( pack->acct_in_use );
1525 0 : acct_uses_clear( pack->writer_costs );
1526 :
1527 0 : sig2txn_clear( pack->signature_map );
1528 :
1529 0 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
1530 0 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
1531 0 : bitset_map_clear( pack->acct_to_bitset );
1532 0 : pack->bitset_avail[ 0 ] = FD_PACK_BITSET_SLOWPATH;
1533 0 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) pack->bitset_avail[ i+1UL ] = (ushort)i;
1534 0 : pack->bitset_avail_cnt = FD_PACK_BITSET_MAX;
1535 :
1536 0 : for( ulong i=0UL; i<pack->bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i] = 0UL;
1537 0 : }
1538 :
1539 : int
1540 : fd_pack_delete_transaction( fd_pack_t * pack,
1541 3189 : fd_ed25519_sig_t const * sig0 ) {
1542 3189 : fd_pack_sig_to_txn_t * in_tbl = sig2txn_query( pack->signature_map, sig0, NULL );
1543 :
1544 3189 : if( !in_tbl )
1545 36 : return 0;
1546 :
1547 : /* The static asserts enforce that the payload of the transaction is
1548 : the first element of the fd_pack_ord_txn_t struct. The signature
1549 : we insert is 1 byte into the start of the payload. */
1550 3153 : fd_pack_ord_txn_t * containing = (fd_pack_ord_txn_t *)( (uchar*)in_tbl->key - 1UL );
1551 3153 : treap_t * root = NULL;
1552 3153 : int root_idx = containing->root;
1553 3153 : switch( root_idx ) {
1554 0 : case FD_ORD_TXN_ROOT_FREE: /* Should be impossible */ return 0;
1555 3114 : case FD_ORD_TXN_ROOT_PENDING: root = pack->pending; break;
1556 39 : case FD_ORD_TXN_ROOT_PENDING_VOTE: root = pack->pending_votes; break;
1557 3153 : }
1558 :
1559 3153 : fd_txn_t * txn = TXN( containing->txn );
1560 3153 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, containing->txn->payload );
1561 3153 : fd_acct_addr_t const * alt_adj = containing->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1562 3153 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1563 15603 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1564 :
1565 12450 : release_result_t ret = release_bit_reference( pack, ACCT_ITER_TO_PTR( iter ) );
1566 12450 : FD_PACK_BITSET_CLEARN( pack->bitset_rw_in_use, ret.clear_rw_bit );
1567 12450 : FD_PACK_BITSET_CLEARN( pack->bitset_w_in_use, ret.clear_w_bit );
1568 12450 : }
1569 :
1570 3153 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1571 18756 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1572 15603 : if( FD_UNLIKELY( fd_pack_unwritable_contains( ACCT_ITER_TO_PTR( iter ) ) ) ) continue;
1573 :
1574 12372 : release_result_t ret = release_bit_reference( pack, ACCT_ITER_TO_PTR( iter ) );
1575 12372 : FD_PACK_BITSET_CLEARN( pack->bitset_rw_in_use, ret.clear_rw_bit );
1576 12372 : FD_PACK_BITSET_CLEARN( pack->bitset_w_in_use, ret.clear_w_bit );
1577 12372 : }
1578 3153 : expq_remove( pack->expiration_q, containing->expq_idx );
1579 3153 : treap_ele_remove( root, containing, pack->pool );
1580 3153 : trp_pool_ele_release( pack->pool, containing );
1581 3153 : sig2txn_remove( pack->signature_map, in_tbl );
1582 3153 : pack->pending_txn_cnt--;
1583 :
1584 3153 : return 1;
1585 3153 : }
1586 :
1587 :
1588 : int
1589 : fd_pack_verify( fd_pack_t * pack,
1590 0 : void * scratch ) {
1591 : /* Invariants:
1592 : sig2txn_query has exact same contents as all treaps combined
1593 : root matches treap
1594 : Keys of acct_to_bitset is exactly union of all accounts in all
1595 : transactions in treaps, with ref counted appropriately
1596 : bits in bitset_avail is complement of bits allocated in
1597 : acct_to_bitset
1598 : expires_at consistent between treap, prq */
1599 :
1600 : /* TODO:
1601 : bitset_{r}w_in_use = bitset_map_query( everything in acct_in_use that doesn't have FD_PACK_IN_USE_BIT_CLEARED )
1602 : use_by_bank does not contain duplicates
1603 : use_by_bank consistent with acct_in_use
1604 : bitset_w_in_use & bitset_rw_in_use == bitset_w_in_use */
1605 0 : #define VERIFY_TEST( cond, ... ) do { \
1606 0 : if( FD_UNLIKELY( !(cond) ) ) { \
1607 0 : FD_LOG_WARNING(( __VA_ARGS__ )); \
1608 0 : return -(__LINE__); \
1609 0 : } \
1610 0 : } while( 0 )
1611 :
1612 0 : ulong max_acct_in_treap = pack->pack_depth * FD_TXN_ACCT_ADDR_MAX;
1613 0 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
1614 0 : void * _bitset_map_copy = scratch;
1615 0 : void * _bitset_map_orig = bitset_map_leave( pack->acct_to_bitset );
1616 0 : fd_memcpy( _bitset_map_copy, _bitset_map_orig, bitset_map_footprint( lg_acct_in_trp ) );
1617 :
1618 0 : fd_pack_bitset_acct_mapping_t * bitset_copy = bitset_map_join( _bitset_map_copy );
1619 :
1620 : /* Check that each bit is in exactly one place */
1621 0 : FD_PACK_BITSET_DECLARE( processed ); FD_PACK_BITSET_CLEAR( processed );
1622 0 : FD_PACK_BITSET_DECLARE( bit ); FD_PACK_BITSET_CLEAR( bit );
1623 0 : FD_PACK_BITSET_DECLARE( full ); FD_PACK_BITSET_CLEAR( full );
1624 :
1625 0 : if( FD_UNLIKELY( pack->bitset_avail[0]!=FD_PACK_BITSET_SLOWPATH ) ) return -1;
1626 0 : for( ulong i=1UL; i<=pack->bitset_avail_cnt; i++ ) {
1627 0 : FD_PACK_BITSET_CLEAR( bit );
1628 0 : FD_PACK_BITSET_SETN( bit, pack->bitset_avail[ i ] );
1629 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ),
1630 0 : "bit %hu in avail set twice", pack->bitset_avail[ i ] );
1631 0 : FD_PACK_BITSET_OR( processed, bit );
1632 0 : }
1633 :
1634 0 : ulong total_references = 0UL;
1635 0 : for( ulong i=0UL; i<bitset_map_slot_cnt( bitset_copy ); i++ ) {
1636 0 : if( !bitset_map_key_inval( bitset_copy[ i ].key ) ) {
1637 0 : VERIFY_TEST( bitset_copy[ i ].ref_cnt>0UL, "account address in table with 0 ref count" );
1638 :
1639 0 : total_references += bitset_copy[ i ].ref_cnt;
1640 :
1641 0 : FD_PACK_BITSET_CLEAR( bit );
1642 0 : FD_PACK_BITSET_SETN( bit, bitset_copy[ i ].bit );
1643 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ), "bit %hu used twice", bitset_copy[ i ].bit );
1644 0 : FD_PACK_BITSET_OR( processed, bit );
1645 0 : }
1646 0 : }
1647 0 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) {
1648 0 : FD_PACK_BITSET_CLEAR( bit );
1649 0 : FD_PACK_BITSET_SETN( bit, i );
1650 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ), "bit %lu missing", i );
1651 0 : FD_PACK_BITSET_SETN( full, i );
1652 0 : }
1653 :
1654 :
1655 0 : fd_pack_ord_txn_t * pool = pack->pool;
1656 0 : treap_t * treaps[ 2 ] = { pack->pending, pack->pending_votes };
1657 0 : ulong txn_cnt = 0UL;
1658 :
1659 0 : for( ulong k=0UL; k<2; k++ ) {
1660 0 : treap_t * treap = treaps[ k ];
1661 :
1662 0 : for( treap_rev_iter_t _cur=treap_rev_iter_init( treap, pool ); !treap_rev_iter_done( _cur );
1663 0 : _cur=treap_rev_iter_next( _cur, pool ) ) {
1664 0 : txn_cnt++;
1665 0 : fd_pack_ord_txn_t const * cur = treap_rev_iter_ele_const( _cur, pool );
1666 0 : fd_txn_t const * txn = TXN(cur->txn);
1667 0 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
1668 0 : fd_acct_addr_t const * alt_adj = cur->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1669 :
1670 0 : fd_ed25519_sig_t const * sig0 = fd_txn_get_signatures( txn, cur->txn->payload );
1671 :
1672 0 : fd_pack_sig_to_txn_t * in_tbl = sig2txn_query( pack->signature_map, sig0, NULL );
1673 0 : VERIFY_TEST( in_tbl, "signature missing from sig2txn" );
1674 0 : VERIFY_TEST( in_tbl->key==sig0, "signature in sig2txn inconsistent" );
1675 0 : VERIFY_TEST( (ulong)(cur->root)==k+1, "treap element had bad root" );
1676 0 : VERIFY_TEST( cur->expires_at>=pack->expire_before, "treap element expired" );
1677 :
1678 0 : fd_pack_expq_t const * eq = pack->expiration_q + cur->expq_idx;
1679 0 : VERIFY_TEST( eq->txn==cur, "expq inconsistent" );
1680 0 : VERIFY_TEST( eq->expires_at==cur->expires_at, "expq expires_at inconsistent" );
1681 :
1682 0 : FD_PACK_BITSET_DECLARE( complement );
1683 0 : FD_PACK_BITSET_COPY( complement, full );
1684 0 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1685 0 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1686 0 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1687 :
1688 0 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( bitset_copy, acct, NULL );
1689 0 : VERIFY_TEST( q, "account in transaction missing from bitset mapping" );
1690 0 : VERIFY_TEST( q->ref_cnt>0UL, "account in transaction ref_cnt already 0" );
1691 0 : q->ref_cnt--;
1692 0 : total_references--;
1693 :
1694 0 : FD_PACK_BITSET_CLEAR( bit );
1695 0 : FD_PACK_BITSET_SETN( bit, q->bit );
1696 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
1697 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->rw_bitset, cur->rw_bitset ), "missing from rw bitset" );
1698 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->w_bitset, cur->w_bitset ), "missing from w bitset" );
1699 0 : }
1700 0 : FD_PACK_BITSET_CLEARN( complement, q->bit );
1701 0 : }
1702 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( complement, complement, cur->w_bitset, cur->w_bitset ), "extra in w bitset" );
1703 :
1704 0 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1705 0 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1706 :
1707 0 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1708 0 : if( FD_UNLIKELY( fd_pack_unwritable_contains( &acct ) ) ) continue;
1709 0 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( bitset_copy, acct, NULL );
1710 0 : VERIFY_TEST( q, "account in transaction missing from bitset mapping" );
1711 0 : VERIFY_TEST( q->ref_cnt>0UL, "account in transaction ref_cnt already 0" );
1712 0 : q->ref_cnt--;
1713 0 : total_references--;
1714 :
1715 0 : FD_PACK_BITSET_CLEAR( bit );
1716 0 : FD_PACK_BITSET_SETN( bit, q->bit );
1717 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
1718 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->rw_bitset, cur->rw_bitset ), "missing from rw bitset" );
1719 0 : }
1720 0 : FD_PACK_BITSET_CLEARN( complement, q->bit );
1721 0 : }
1722 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( complement, complement, cur->rw_bitset, cur->rw_bitset ), "extra in rw bitset" );
1723 0 : }
1724 0 : }
1725 :
1726 0 : bitset_map_leave( bitset_copy );
1727 :
1728 0 : VERIFY_TEST( total_references==0UL, "extra references in bitset mapping" );
1729 0 : VERIFY_TEST( txn_cnt==sig2txn_key_cnt( pack->signature_map ), "extra signatures in sig2txn" );
1730 :
1731 0 : bitset_map_join( _bitset_map_orig );
1732 :
1733 0 : ulong max_acct_in_flight = pack->bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * pack->lim->max_txn_per_microblock + 1UL);
1734 0 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
1735 :
1736 0 : void * _acct_in_use_copy = scratch;
1737 0 : void * _acct_in_use_orig = acct_uses_leave( pack->acct_in_use );
1738 0 : fd_memcpy( _acct_in_use_copy, _acct_in_use_orig, acct_uses_footprint( lg_uses_tbl_sz ) );
1739 :
1740 0 : fd_pack_addr_use_t * acct_in_use_copy = acct_uses_join( _acct_in_use_copy );
1741 :
1742 0 : FD_PACK_BITSET_DECLARE( w_complement );
1743 0 : FD_PACK_BITSET_DECLARE( rw_complement );
1744 0 : FD_PACK_BITSET_COPY( w_complement, full );
1745 0 : FD_PACK_BITSET_COPY( rw_complement, full );
1746 :
1747 0 : FD_PACK_BITSET_DECLARE( rw_bitset ); FD_PACK_BITSET_COPY( rw_bitset, pack->bitset_rw_in_use );
1748 0 : FD_PACK_BITSET_DECLARE( w_bitset ); FD_PACK_BITSET_COPY( w_bitset, pack->bitset_w_in_use );
1749 :
1750 :
1751 0 : ulong const EMPTY_MASK = ~(FD_PACK_IN_USE_WRITABLE | FD_PACK_IN_USE_BIT_CLEARED);
1752 :
1753 0 : for( ulong bank=0UL; bank<pack->bank_tile_cnt; bank++ ) {
1754 :
1755 0 : fd_pack_addr_use_t const * base = pack->use_by_bank[ bank ];
1756 0 : ulong bank_mask = 1UL << bank;
1757 :
1758 0 : for( ulong i=0UL; i<pack->use_by_bank_cnt[ bank ]; i++ ) {
1759 0 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use_copy, base[i].key, NULL );
1760 0 : VERIFY_TEST( use, "acct in use by bank not in acct_in_use, or in uses_by_bank twice" );
1761 :
1762 0 : 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" );
1763 :
1764 0 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, base[i].key, NULL );
1765 : /* The normal case is that the acct->bit mapping is preserved
1766 : while in use by other transactions in the pending list. This
1767 : might not always happen though. It's okay for the mapping to
1768 : get deleted while the acct is in use, which is noted with
1769 : BIT_CLEARED. If that is set, the mapping may not exist, or it
1770 : may have been re-created, perhaps with a different bit. */
1771 0 : 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" );
1772 0 : else if( !(use->in_use_by & FD_PACK_IN_USE_BIT_CLEARED) ) {
1773 0 : FD_PACK_BITSET_CLEAR( bit );
1774 0 : FD_PACK_BITSET_SETN( bit, q->bit );
1775 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
1776 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, rw_bitset, rw_bitset ), "missing from rw bitset" );
1777 0 : if( use->in_use_by & FD_PACK_IN_USE_WRITABLE ) {
1778 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, w_bitset, w_bitset ), "missing from w bitset" );
1779 0 : FD_PACK_BITSET_CLEARN( w_complement, q->bit );
1780 0 : }
1781 0 : }
1782 0 : FD_PACK_BITSET_CLEARN( rw_complement, q->bit );
1783 0 : }
1784 0 : 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" );
1785 :
1786 0 : use->in_use_by &= ~bank_mask;
1787 0 : if( !(use->in_use_by & EMPTY_MASK) ) acct_uses_remove( acct_in_use_copy, use );
1788 0 : }
1789 0 : }
1790 0 : VERIFY_TEST( acct_uses_key_cnt( acct_in_use_copy )==0UL, "stray uses in acct_in_use" );
1791 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( rw_complement, rw_complement, rw_bitset, rw_bitset ), "extra in rw bitset" );
1792 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( w_complement, w_complement, w_bitset, w_bitset ), "extra in w bitset" );
1793 :
1794 0 : acct_uses_leave( acct_in_use_copy );
1795 :
1796 0 : acct_uses_join( _acct_in_use_orig );
1797 0 : return 0;
1798 0 : }
1799 :
1800 0 : void * fd_pack_leave ( fd_pack_t * pack ) { FD_COMPILER_MFENCE(); return (void *)pack; }
1801 0 : void * fd_pack_delete( void * mem ) { FD_COMPILER_MFENCE(); return mem; }
|
