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 : /* FD_ORD_TXN_ROOT is essentially a small union packed into an int. The low
83 : byte is the "tag". The higher 3 bytes depend on the low byte. */
84 4451358 : #define FD_ORD_TXN_ROOT_TAG_MASK 0xFF
85 2671692 : #define FD_ORD_TXN_ROOT_FREE 0
86 17998959 : #define FD_ORD_TXN_ROOT_PENDING 1
87 13314177 : #define FD_ORD_TXN_ROOT_PENDING_VOTE 2
88 : #define FD_ORD_TXN_ROOT_BUNDLE 3
89 280418 : #define FD_ORD_TXN_ROOT_PENALTY( idx ) (4 | (idx)<<8)
90 :
91 : /* if root & TAG_MASK == PENALTY, then PENALTY_ACCT_IDX(root) gives the index
92 : in the transaction's list of account addresses of which penalty treap the
93 : transaction is in. */
94 : #define FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( root ) (((root) & 0xFF00)>>8)
95 :
96 :
97 28372164 : #define FD_PACK_IN_USE_WRITABLE (0x8000000000000000UL)
98 15345687 : #define FD_PACK_IN_USE_BIT_CLEARED (0x4000000000000000UL)
99 :
100 : /* Each non-empty microblock we schedule also has an overhead of 48
101 : bytes that counts towards shed limits. That comes from the 32 byte
102 : hash, the hash count (8 bytes) and the transaction count (8 bytes).
103 : We don't have to pay this overhead if the microblock is empty, since
104 : those microblocks get dropped. */
105 1476432 : #define MICROBLOCK_DATA_OVERHEAD 48UL
106 :
107 : /* Keep track of accounts that are written to in each block so that we
108 : can reset the writer costs to 0. If the number of accounts that are
109 : written to is above or equal to this, we'll just clear the whole
110 : writer cost map instead of only removing the elements we increased. */
111 1344 : #define DEFAULT_WRITTEN_LIST_MAX 16384UL
112 :
113 : /* fd_pack_addr_use_t: Used for two distinct purposes:
114 : - to record that an address is in use and can't be used again until
115 : certain microblocks finish execution
116 : - to keep track of the cost of all transactions that write to the
117 : specified account.
118 : Making these separate structs might make it more clear, but then
119 : they'd have identical shape and result in two fd_map_dynamic sets of
120 : functions with identical code. It doesn't seem like the compiler is
121 : very good at merging code like that, so in order to reduce code
122 : bloat, we'll just combine them. */
123 : struct fd_pack_private_addr_use_record {
124 : fd_acct_addr_t key; /* account address */
125 : union {
126 : ulong in_use_by; /* Bitmask indicating which banks */
127 : ulong total_cost; /* In cost units/CUs */
128 : };
129 : };
130 : typedef struct fd_pack_private_addr_use_record fd_pack_addr_use_t;
131 :
132 :
133 : /* fd_pack_sig_to_entry_t: An element of an fd_map that maps the first
134 : transaction signature to the corresponding fd_pack_ord_txn_t so that
135 : pending transactions can be deleted by signature. Note: this
136 : implicitly relies on the fact that for Solana transactions the
137 : signature_offset is always 1. If that fact changes, this will need
138 : to become a real struct. */
139 : struct fd_pack_sig_to_txn {
140 : fd_ed25519_sig_t const * key;
141 : };
142 : typedef struct fd_pack_sig_to_txn fd_pack_sig_to_txn_t;
143 :
144 : /* fd_pack_expq_t: An element of an fd_prq to sort the transactions by
145 : timeout. This structure has several invariants for entries
146 : corresponding to pending transactions:
147 : expires_at == txn->expires_at
148 : txn->exp_prq_idx is the index of this structure
149 : Notice that prq is an array-based heap, which means the indexes of
150 : elements change. The PRQ_TMP_ST macro is hijacked to keep that
151 : invariant up to date.
152 :
153 : Note: this could be easier if fd_heap supported deleting from the
154 : middle, but that's not possible with the current design of fd_heap,
155 : which omits a parent pointer for improved performance. */
156 : struct fd_pack_expq {
157 : ulong expires_at;
158 : fd_pack_ord_txn_t * txn;
159 : };
160 : typedef struct fd_pack_expq fd_pack_expq_t;
161 :
162 :
163 : /* fd_pack_bitset_acct_mapping_t: An element of an fd_map_dynamic that
164 : maps an account address to the number of transactions that are
165 : referencing it and the bit that is reserved to indicate it in the
166 : bitset, if any. */
167 : struct fd_pack_bitset_acct_mapping {
168 : fd_acct_addr_t key; /* account address */
169 : ulong ref_cnt;
170 :
171 : /* first_instance and first_instance_was_write are only valid when
172 : bit==FD_PACK_BITSET_FIRST_INSTANCE, which is set when ref_cnt
173 : transitions from 0 to 1. These just exist to implement the
174 : optimization that accounts referenced a single time aren't
175 : allocated a bit, but this seems to be an important optimization. */
176 : fd_pack_ord_txn_t * first_instance;
177 : int first_instance_was_write;
178 :
179 : /* bit is in [0, FD_PACK_BITSET_MAX) U
180 : { FD_PACK_BITSET_FIRST_INSTANCE, FD_PACK_BITSET_SLOWPATH }. */
181 : ushort bit;
182 : };
183 : typedef struct fd_pack_bitset_acct_mapping fd_pack_bitset_acct_mapping_t;
184 :
185 : /* Table of special addresses that are not allowed to be written to. We
186 : immediately reject and refuse to pack any transaction that tries to
187 : write to one of these accounts. Because we reject any writes to any
188 : of these accounts, we actually don't need to track reads of them
189 : either. This is nice, because fd_map_dynamic requires a null address
190 : that we promise never to insert. The zero address is a sysvar, so
191 : now we meet that part of the fd_map_dynamic contract. */
192 : #define MAP_PERFECT_NAME fd_pack_unwritable
193 : #define MAP_PERFECT_LG_TBL_SZ 5
194 : #define MAP_PERFECT_T fd_acct_addr_t
195 27378819 : #define MAP_PERFECT_HASH_C 1227063708U
196 : #define MAP_PERFECT_KEY b
197 : #define MAP_PERFECT_KEY_T fd_acct_addr_t const *
198 : #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)
199 : #define MAP_PERFECT_COMPLEX_KEY 1
200 27378819 : #define MAP_PERFECT_KEYS_EQUAL(k1,k2) (!memcmp( (k1), (k2), 32UL ))
201 :
202 27378819 : #define PERFECT_HASH( u ) (((MAP_PERFECT_HASH_C*(u))>>27)&0x1FU)
203 :
204 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
205 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
206 : PERFECT_HASH( (a08 | (a09<<8) | (a10<<16) | (a11<<24)) )
207 27378819 : #define MAP_PERFECT_HASH_R( ptr ) PERFECT_HASH( fd_uint_load_4( (uchar const *)ptr->b + 8UL ) )
208 :
209 : /* This list is a superset of what Lab's is_builtin_key_or_sysvar checks. */
210 : /* Sysvars */
211 : #define MAP_PERFECT_0 ( SYSVAR_CLOCK_ID ),
212 : #define MAP_PERFECT_1 ( SYSVAR_EPOCH_SCHED_ID ),
213 : #define MAP_PERFECT_2 ( SYSVAR_FEES_ID ),
214 : #define MAP_PERFECT_3 ( SYSVAR_RECENT_BLKHASH_ID ),
215 : #define MAP_PERFECT_4 ( SYSVAR_RENT_ID ),
216 : #define MAP_PERFECT_5 ( SYSVAR_REWARDS_ID ),
217 : #define MAP_PERFECT_6 ( SYSVAR_SLOT_HASHES_ID ),
218 : #define MAP_PERFECT_7 ( SYSVAR_SLOT_HIST_ID ),
219 : #define MAP_PERFECT_8 ( SYSVAR_STAKE_HIST_ID ),
220 : #define MAP_PERFECT_9 ( SYSVAR_INSTRUCTIONS_ID ),
221 : #define MAP_PERFECT_10 ( SYSVAR_EPOCH_REWARDS_ID ),
222 : #define MAP_PERFECT_11 ( SYSVAR_LAST_RESTART_ID ),
223 : /* Programs */
224 : #define MAP_PERFECT_12 ( CONFIG_PROG_ID ),
225 : #define MAP_PERFECT_13 ( FEATURE_ID ),
226 : #define MAP_PERFECT_14 ( NATIVE_LOADER_ID ),
227 : #define MAP_PERFECT_15 ( STAKE_PROG_ID ),
228 : #define MAP_PERFECT_16 ( STAKE_CONFIG_PROG_ID ),
229 : #define MAP_PERFECT_17 ( VOTE_PROG_ID ),
230 : #define MAP_PERFECT_18 ( SYS_PROG_ID ), /* Do not remove. See above. */
231 : #define MAP_PERFECT_19 ( BPF_LOADER_1_PROG_ID ),
232 : #define MAP_PERFECT_20 ( BPF_LOADER_2_PROG_ID ),
233 : #define MAP_PERFECT_21 ( BPF_UPGRADEABLE_PROG_ID ),
234 : /* Extras */
235 : #define MAP_PERFECT_22 ( ED25519_SV_PROG_ID ),
236 : #define MAP_PERFECT_23 ( KECCAK_SECP_PROG_ID ),
237 : #define MAP_PERFECT_24 ( COMPUTE_BUDGET_PROG_ID ),
238 : #define MAP_PERFECT_25 ( ADDR_LUT_PROG_ID ),
239 : #define MAP_PERFECT_26 ( NATIVE_MINT_ID ),
240 : #define MAP_PERFECT_27 ( TOKEN_PROG_ID ),
241 : #define MAP_PERFECT_28 ( SECP256R1_PROG_ID ),
242 :
243 : #include "../../util/tmpl/fd_map_perfect.c"
244 :
245 :
246 : /* Returns 1 if x.rewards/x.compute < y.rewards/y.compute. Not robust. */
247 87351100 : #define COMPARE_WORSE(x,y) ( ((ulong)((x)->rewards)*(ulong)((y)->compute_est)) < ((ulong)((y)->rewards)*(ulong)((x)->compute_est)) )
248 :
249 : /* Declare all the data structures */
250 :
251 :
252 : /* Define the big max-"heap" that we pull transactions off to schedule.
253 : The priority is given by reward/compute. We may want to add in some
254 : additional terms at a later point. In order to cheaply remove nodes,
255 : we actually use a treap. */
256 : #define POOL_NAME trp_pool
257 1557 : #define POOL_T fd_pack_ord_txn_t
258 : #define POOL_IDX_T ushort
259 29566008 : #define POOL_NEXT parent
260 : #include "../../util/tmpl/fd_pool.c"
261 :
262 : #define TREAP_T fd_pack_ord_txn_t
263 : #define TREAP_NAME treap
264 : #define TREAP_QUERY_T void * /* We don't use query ... */
265 : #define TREAP_CMP(a,b) (__extension__({ (void)(a); (void)(b); -1; })) /* which means we don't need to give a real
266 : implementation to cmp either */
267 179859686 : #define TREAP_IDX_T ushort
268 : #define TREAP_OPTIMIZE_ITERATION 1
269 87351100 : #define TREAP_LT COMPARE_WORSE
270 : #include "../../util/tmpl/fd_treap.c"
271 :
272 :
273 : /* Define a strange map where key and value are kind of the same
274 : variable. Essentially, it maps the contents to which the pointer
275 : points to the value of the pointer. */
276 : #define MAP_NAME sig2txn
277 40717962 : #define MAP_T fd_pack_sig_to_txn_t
278 171452122 : #define MAP_KEY_T fd_ed25519_sig_t const *
279 36964170 : #define MAP_KEY_NULL NULL
280 171452122 : #define MAP_KEY_INVAL(k) !(k)
281 : #define MAP_MEMOIZE 0
282 118171367 : #define MAP_KEY_EQUAL(k0,k1) (((!!(k0))&(!!(k1)))&&(!memcmp((k0),(k1), FD_TXN_SIGNATURE_SZ)))
283 : #define MAP_KEY_EQUAL_IS_SLOW 1
284 66853244 : #define MAP_KEY_HASH(key) fd_uint_load_4( (key) ) /* first 4 bytes of signature */
285 : #include "../../util/tmpl/fd_map_dynamic.c"
286 :
287 :
288 : static const fd_acct_addr_t null_addr = { 0 };
289 :
290 : #define MAP_NAME acct_uses
291 94277589 : #define MAP_T fd_pack_addr_use_t
292 111242472 : #define MAP_KEY_T fd_acct_addr_t
293 294536167 : #define MAP_KEY_NULL null_addr
294 : #if FD_HAS_AVX
295 111242472 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
296 : #else
297 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
298 : #endif
299 77297652 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
300 : #define MAP_KEY_EQUAL_IS_SLOW 1
301 : #define MAP_MEMOIZE 0
302 94286028 : #define MAP_KEY_HASH(key) ((uint)fd_ulong_hash( fd_ulong_load_8( (key).b ) ))
303 : #include "../../util/tmpl/fd_map_dynamic.c"
304 :
305 :
306 : #define MAP_NAME bitset_map
307 52297803 : #define MAP_T fd_pack_bitset_acct_mapping_t
308 65613759 : #define MAP_KEY_T fd_acct_addr_t
309 872336525 : #define MAP_KEY_NULL null_addr
310 : #if FD_HAS_AVX
311 65613759 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
312 : #else
313 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
314 : #endif
315 39021783 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
316 : #define MAP_KEY_EQUAL_IS_SLOW 1
317 : #define MAP_MEMOIZE 0
318 52324767 : #define MAP_KEY_HASH(key) ((uint)fd_ulong_hash( fd_ulong_load_8( (key).b ) ))
319 : #include "../../util/tmpl/fd_map_dynamic.c"
320 :
321 :
322 : /* Since transactions can also expire, we also maintain a parallel
323 : priority queue. This means elements are simultaneously part of the
324 : treap (ordered by priority) and the expiration queue (ordered by
325 : expiration). It's tempting to use the priority field of the treap
326 : for this purpose, but that can result in degenerate treaps in some
327 : cases. */
328 : #define PRQ_NAME expq
329 31794824 : #define PRQ_T fd_pack_expq_t
330 27128895 : #define PRQ_TIMEOUT_T ulong
331 27128895 : #define PRQ_TIMEOUT expires_at
332 15389927 : #define PRQ_TMP_ST(p,t) do { \
333 15389927 : (p)[0] = (t); \
334 15389927 : t.txn->expq_idx = (ulong)((p)-heap); \
335 15389927 : } while( 0 )
336 : #include "../../util/tmpl/fd_prq.c"
337 :
338 : /* fd_pack_smallest: We want to keep track of the smallest transaction
339 : in each treap. That way, if we know the amount of space left in the
340 : block is less than the smallest transaction in the heap, we can just
341 : skip the heap. Since transactions can be deleted, etc. maintaining
342 : this precisely is hard, but we can maintain a conservative value
343 : fairly cheaply. Since the CU limit or the byte limit can be the one
344 : that matters, we keep track of the smallest by both. */
345 : struct fd_pack_smallest {
346 : ulong cus;
347 : ulong bytes;
348 : };
349 : typedef struct fd_pack_smallest fd_pack_smallest_t;
350 :
351 :
352 : /* With realistic traffic patterns, we often see many, many transactions
353 : competing for the same writable account. Since only one of these can
354 : execute at a time, we sometimes waste lots of scheduling time going
355 : through them one at a time. To combat that, when a transaction
356 : writes to an account with more than PENALTY_TREAP_THRESHOLD
357 : references (readers or writers), instead of inserting it into the
358 : main treap, we insert it into a penalty treap for that specific hot
359 : account address. These transactions are not immediately available
360 : for scheduling. Then, when a transaction that writes to the hot
361 : address completes, we move the most lucrative transaction from the
362 : penalty treap to the main treap, making it available for scheduling.
363 : This policy may slightly violate the price-time priority scheduling
364 : approach pack normally uses: if the most lucrative transaction
365 : competing for hot state arrives after PENALTY_TREAP_THRESHOLD has
366 : been hit, it may be scheduled second instead of first. However, if
367 : the account is in use at the time the new transaction arrives, it
368 : will be scheduled next, as desired. This minor difference seems
369 : reasonable to reduce complexity.
370 :
371 : fd_pack_penalty_treap is one account-specific penalty treap. All the
372 : transactions in the penalty_treap treap write to key.
373 :
374 : penalty_map is the fd_map_dynamic that maps accounts to their
375 : respective penalty treaps. */
376 : struct fd_pack_penalty_treap {
377 : fd_acct_addr_t key;
378 : treap_t penalty_treap[1];
379 : };
380 : typedef struct fd_pack_penalty_treap fd_pack_penalty_treap_t;
381 :
382 : #define MAP_NAME penalty_map
383 3685625 : #define MAP_T fd_pack_penalty_treap_t
384 3686768 : #define MAP_KEY_T fd_acct_addr_t
385 6713541 : #define MAP_KEY_NULL null_addr
386 : #if FD_HAS_AVX
387 3686768 : # define MAP_KEY_INVAL(k) _mm256_testz_si256( wb_ldu( (k).b ), wb_ldu( (k).b ) )
388 : #else
389 : # define MAP_KEY_INVAL(k) MAP_KEY_EQUAL(k, null_addr)
390 : #endif
391 3682406 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp((k0).b,(k1).b, FD_TXN_ACCT_ADDR_SZ))
392 : #define MAP_KEY_EQUAL_IS_SLOW 1
393 : #define MAP_MEMOIZE 0
394 3684587 : #define MAP_KEY_HASH(key) ((uint)fd_ulong_hash( fd_ulong_load_8( (key).b ) ))
395 : #include "../../util/tmpl/fd_map_dynamic.c"
396 :
397 : /* PENALTY_TREAP_THRESHOLD: How many references to an account do we
398 : allow before subsequent transactions that write to the account go to
399 : the penalty treap. */
400 29488278 : #define PENALTY_TREAP_THRESHOLD 128UL
401 :
402 : /* Finally, we can now declare the main pack data structure */
403 : struct fd_pack_private {
404 : ulong pack_depth;
405 : ulong bank_tile_cnt;
406 :
407 : fd_pack_limits_t lim[1];
408 :
409 : ulong pending_txn_cnt;
410 : ulong microblock_cnt; /* How many microblocks have we
411 : generated in this block? */
412 : ulong data_bytes_consumed; /* How much data is in this block so
413 : far ? */
414 : fd_rng_t * rng;
415 :
416 : ulong cumulative_block_cost;
417 : ulong cumulative_vote_cost;
418 :
419 : /* expire_before: Any transactions with expires_at strictly less than
420 : the current expire_before are removed from the available pending
421 : transaction. Here, "expire" is used as a verb: cause all
422 : transactions before this time to expire. */
423 : ulong expire_before;
424 :
425 : /* outstanding_microblock_mask: a bitmask indicating which banking
426 : tiles have outstanding microblocks, i.e. fd_pack has generated a
427 : microblock for that banking tile and the banking tile has not yet
428 : notified fd_pack that it has completed it. */
429 : ulong outstanding_microblock_mask;
430 :
431 : /* The actual footprint for the pool and maps is allocated
432 : in the same order in which they are declared immediately following
433 : the struct. I.e. these pointers point to memory not far after the
434 : struct. The trees are just pointers into the pool so don't take up
435 : more space. */
436 :
437 : fd_pack_ord_txn_t * pool;
438 :
439 : /* Treaps (sorted by priority) of pending transactions. We store the
440 : pending simple votes separately. */
441 : treap_t pending[1];
442 : treap_t pending_votes[1];
443 :
444 : /* penalty_treaps: an fd_map_dynamic mapping hotly contended account
445 : addresses to treaps of transactions that write to them. We try not
446 : to allow more than roughly PENALTY_TREAP_THRESHOLD transactions in
447 : the main treap that write to each account, though this is not
448 : exact. */
449 : fd_pack_penalty_treap_t * penalty_treaps;
450 :
451 : /* pending{_votes}_smallest: keep a conservative estimate of the
452 : smallest transaction (by cost units and by bytes) in each heap.
453 : Both CUs and bytes should be set to ULONG_MAX is the treap is
454 : empty. */
455 : fd_pack_smallest_t pending_smallest[1];
456 : fd_pack_smallest_t pending_votes_smallest[1];
457 :
458 : /* expiration_q: At the same time that a transaction is in exactly one
459 : of the above treaps, it is also in the expiration queue, sorted by
460 : its expiration time. This enables deleting all transactions that
461 : have expired, regardless of which treap they are in. */
462 : fd_pack_expq_t * expiration_q;
463 :
464 : /* acct_in_use: Map from account address to bitmask indicating which
465 : bank tiles are using the account and whether that use is read or
466 : write (msb). */
467 : fd_pack_addr_use_t * acct_in_use;
468 :
469 : /* bitset_{w, rw}_in_use stores a subset of the information in
470 : acct_in_use using the compressed set format explained at the top of
471 : this file. rw_in_use stores accounts in use for read or write
472 : while w_in_use stores only those in use for write. */
473 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
474 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
475 :
476 : /* writer_costs: Map from account addresses to the sum of costs of
477 : transactions that write to the account. Used for enforcing limits
478 : on the max write cost per account per block. */
479 : fd_pack_addr_use_t * writer_costs;
480 :
481 : /* At the end of every slot, we have to clear out writer_costs. The
482 : map is large, but typically very sparsely populated. As an
483 : optimization, we keep track of the elements of the map that we've
484 : actually used, up to a maximum. If we use more than the maximum,
485 : we revert to the old way of just clearing the whole map.
486 :
487 : written_list indexed [0, written_list_cnt).
488 : written_list_cnt in [0, written_list_max).
489 :
490 : written_list_cnt==written_list_max-1 means that the list may be
491 : incomplete and should be ignored. */
492 : fd_pack_addr_use_t * * written_list;
493 : ulong written_list_cnt;
494 : ulong written_list_max;
495 :
496 :
497 : fd_pack_sig_to_txn_t * signature_map; /* Stores pointers into pool for deleting by signature */
498 :
499 : /* use_by_bank: An array of size (max_txn_per_microblock *
500 : FD_TXN_ACCT_ADDR_MAX) for each banking tile. Only the MSB of
501 : in_use_by is relevant. Addressed use_by_bank[i][j] where i is in
502 : [0, bank_tile_cnt) and j is in [0, use_by_bank_cnt[i]). Used
503 : mostly for clearing the proper bits of acct_in_use when a
504 : microblock finishes.
505 :
506 : use_by_bank_txn: indexed [i][j], where i is in [0, bank_tile_cnt)
507 : and j is in [0, max_txn_per_microblock). Transaction j in the
508 : microblock currently scheduled to bank i uses account addresses in
509 : use_by_bank[i][k] where k is in [0, use_by_bank[i][j]). For
510 : example, if use_by_bank[i][0] = 2 and use_by_bank[i][1] = 3, then
511 : all the accounts that the first transaction in the outstanding
512 : microblock for bank 0 uses are contained in the set
513 : { use_by_bank[i][0], use_by_bank[i][1] },
514 : and all the accounts in the second transaction in the microblock
515 : are in the set
516 : { use_by_bank[i][0], use_by_bank[i][1], use_by_bank[i][2] }.
517 : Each transaction writes to at least one account (the fee payer)
518 : that no other transaction scheduled to the bank uses, which means
519 : that use_by_bank_txn[i][j] - use_by_bank_txn[i][j-1] >= 1 (with 0
520 : for use_by_bank_txn[i][-1]). This means we can stop iterating when
521 : use_by_bank_txn[i][j] == use_by_bank_cnt[i]. */
522 : fd_pack_addr_use_t * use_by_bank [ FD_PACK_MAX_BANK_TILES ];
523 : ulong use_by_bank_cnt[ FD_PACK_MAX_BANK_TILES ];
524 : ulong * use_by_bank_txn[ FD_PACK_MAX_BANK_TILES ];
525 :
526 : fd_histf_t txn_per_microblock [ 1 ];
527 : fd_histf_t vote_per_microblock[ 1 ];
528 :
529 : fd_histf_t scheduled_cus_per_block[ 1 ];
530 : fd_histf_t rebated_cus_per_block [ 1 ];
531 : fd_histf_t net_cus_per_block [ 1 ];
532 : ulong cumulative_rebated_cus;
533 :
534 : /* use_bundles: if true (non-zero), allows the use of bundles, groups
535 : of transactions that are executed atomically with high priority */
536 : int use_bundles;
537 :
538 : /* bitset_avail: a stack of which bits are not currently reserved and
539 : can be used to represent an account address.
540 : Indexed [0, bitset_avail_cnt]. Element 0 is fixed at
541 : FD_PACK_BITSET_SLOWPATH. */
542 : ushort bitset_avail[ 1UL+FD_PACK_BITSET_MAX ];
543 : ulong bitset_avail_cnt;
544 :
545 : /* acct_to_bitset: an fd_map_dynamic that maps acct addresses to the
546 : reference count, which bit, etc. */
547 : fd_pack_bitset_acct_mapping_t * acct_to_bitset;
548 :
549 : /* chdkup: scratch memory chkdup needs for its internal processing */
550 : fd_chkdup_t chkdup[ 1 ];
551 : };
552 :
553 : typedef struct fd_pack_private fd_pack_t;
554 :
555 : FD_STATIC_ASSERT( offsetof(fd_pack_t, pending_txn_cnt)==FD_PACK_PENDING_TXN_CNT_OFF, txn_cnt_off );
556 :
557 : ulong
558 : fd_pack_footprint( ulong pack_depth,
559 : ulong bank_tile_cnt,
560 306 : fd_pack_limits_t const * limits ) {
561 306 : if( FD_UNLIKELY( (bank_tile_cnt==0) | (bank_tile_cnt>FD_PACK_MAX_BANK_TILES) ) ) return 0UL;
562 306 : if( FD_UNLIKELY( pack_depth<4UL ) ) return 0UL;
563 :
564 306 : ulong l;
565 306 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
566 306 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * limits->max_txn_per_microblock + 1UL);
567 306 : ulong max_txn_in_flight = bank_tile_cnt * limits->max_txn_per_microblock;
568 :
569 306 : ulong max_w_per_block = fd_ulong_min( limits->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
570 306 : limits->max_txn_per_microblock * limits->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
571 306 : ulong written_list_max = fd_ulong_min( max_w_per_block>>1, DEFAULT_WRITTEN_LIST_MAX );
572 :
573 : /* log base 2, but with a 2* so that the hash table stays sparse */
574 306 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
575 306 : int lg_max_writers = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_w_per_block ) );
576 306 : int lg_depth = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*pack_depth ) );
577 306 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
578 306 : int lg_penalty_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap/PENALTY_TREAP_THRESHOLD ) );
579 :
580 306 : l = FD_LAYOUT_INIT;
581 306 : l = FD_LAYOUT_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
582 306 : l = FD_LAYOUT_APPEND( l, trp_pool_align (), trp_pool_footprint ( pack_depth+1UL ) ); /* pool */
583 306 : l = FD_LAYOUT_APPEND( l, penalty_map_align(), penalty_map_footprint( lg_penalty_trp ) ); /* penalty_treaps */
584 306 : l = FD_LAYOUT_APPEND( l, expq_align (), expq_footprint ( pack_depth+1UL ) ); /* expiration prq */
585 306 : l = FD_LAYOUT_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) ); /* acct_in_use */
586 306 : l = FD_LAYOUT_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_max_writers ) ); /* writer_costs */
587 306 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t*)*written_list_max ); /* written_list */
588 306 : l = FD_LAYOUT_APPEND( l, sig2txn_align (), sig2txn_footprint ( lg_depth ) ); /* signature_map */
589 306 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight ); /* use_by_bank */
590 306 : l = FD_LAYOUT_APPEND( l, 32UL, sizeof(ulong)*max_txn_in_flight ); /* use_by_bank_txn*/
591 306 : l = FD_LAYOUT_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) ); /* acct_to_bitset */
592 306 : return FD_LAYOUT_FINI( l, FD_PACK_ALIGN );
593 306 : }
594 :
595 : void *
596 : fd_pack_new( void * mem,
597 : ulong pack_depth,
598 : ulong bank_tile_cnt,
599 : fd_pack_limits_t const * limits,
600 519 : fd_rng_t * rng ) {
601 :
602 519 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
603 519 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * limits->max_txn_per_microblock + 1UL);
604 519 : ulong max_txn_in_flight = bank_tile_cnt * limits->max_txn_per_microblock;
605 519 : ulong max_w_per_block = fd_ulong_min( limits->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
606 519 : limits->max_txn_per_microblock * limits->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
607 519 : ulong written_list_max = fd_ulong_min( max_w_per_block>>1, DEFAULT_WRITTEN_LIST_MAX );
608 :
609 : /* log base 2, but with a 2* so that the hash table stays sparse */
610 519 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
611 519 : int lg_max_writers = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_w_per_block ) );
612 519 : int lg_depth = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*pack_depth ) );
613 519 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
614 519 : int lg_penalty_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap/PENALTY_TREAP_THRESHOLD ) );
615 :
616 519 : FD_SCRATCH_ALLOC_INIT( l, mem );
617 519 : fd_pack_t * pack = FD_SCRATCH_ALLOC_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
618 : /* The pool has one extra element that is used between insert_init and
619 : cancel/fini. */
620 519 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, trp_pool_align(), trp_pool_footprint ( pack_depth+1UL ) );
621 519 : void * _penalty_map = FD_SCRATCH_ALLOC_APPEND( l, penalty_map_align(), penalty_map_footprint( lg_penalty_trp ) );
622 519 : void * _expq = FD_SCRATCH_ALLOC_APPEND( l, expq_align(), expq_footprint ( pack_depth+1UL ) );
623 519 : void * _uses = FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) );
624 519 : void * _writer_cost = FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_max_writers ) );
625 519 : void * _written_lst = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t*)*written_list_max );
626 519 : void * _sig_map = FD_SCRATCH_ALLOC_APPEND( l, sig2txn_align(), sig2txn_footprint ( lg_depth ) );
627 519 : void * _use_by_bank = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight );
628 519 : void * _use_by_txn = FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(ulong)*max_txn_in_flight );
629 519 : void * _acct_bitset = FD_SCRATCH_ALLOC_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp ) );
630 :
631 0 : pack->pack_depth = pack_depth;
632 519 : pack->bank_tile_cnt = bank_tile_cnt;
633 519 : pack->lim[0] = *limits;
634 519 : pack->pending_txn_cnt = 0UL;
635 519 : pack->microblock_cnt = 0UL;
636 519 : pack->data_bytes_consumed = 0UL;
637 519 : pack->rng = rng;
638 519 : pack->cumulative_block_cost = 0UL;
639 519 : pack->cumulative_vote_cost = 0UL;
640 519 : pack->expire_before = 0UL;
641 519 : pack->outstanding_microblock_mask = 0UL;
642 519 : pack->cumulative_rebated_cus = 0UL;
643 :
644 :
645 519 : trp_pool_new( _pool, pack_depth+1UL );
646 :
647 519 : fd_pack_ord_txn_t * pool = trp_pool_join( _pool );
648 519 : treap_seed( pool, pack_depth+1UL, fd_rng_ulong( rng ) );
649 2177070 : for( ulong i=0UL; i<pack_depth+1UL; i++ ) pool[i].root = FD_ORD_TXN_ROOT_FREE;
650 519 : (void)trp_pool_leave( pool );
651 :
652 519 : penalty_map_new( _penalty_map, lg_penalty_trp );
653 :
654 519 : treap_new( (void*)pack->pending, pack_depth );
655 519 : treap_new( (void*)pack->pending_votes, pack_depth );
656 :
657 519 : pack->pending_smallest->cus = ULONG_MAX;
658 519 : pack->pending_smallest->bytes = ULONG_MAX;
659 519 : pack->pending_votes_smallest->cus = ULONG_MAX;
660 519 : pack->pending_votes_smallest->bytes = ULONG_MAX;
661 :
662 519 : expq_new( _expq, pack_depth+1UL );
663 :
664 519 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
665 519 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
666 :
667 519 : acct_uses_new( _uses, lg_uses_tbl_sz );
668 519 : acct_uses_new( _writer_cost, lg_max_writers );
669 :
670 519 : pack->written_list = _written_lst;
671 519 : pack->written_list_cnt = 0UL;
672 519 : pack->written_list_max = written_list_max;
673 :
674 519 : sig2txn_new( _sig_map, lg_depth );
675 :
676 519 : fd_pack_addr_use_t * use_by_bank = (fd_pack_addr_use_t *)_use_by_bank;
677 519 : ulong * use_by_bank_txn = (ulong *)_use_by_txn;
678 6765 : for( ulong i=0UL; i<bank_tile_cnt; i++ ) {
679 6246 : pack->use_by_bank [i] = use_by_bank + i*(FD_TXN_ACCT_ADDR_MAX*limits->max_txn_per_microblock+1UL);
680 6246 : pack->use_by_bank_cnt[i] = 0UL;
681 6246 : pack->use_by_bank_txn[i] = use_by_bank_txn + i*limits->max_txn_per_microblock;
682 6246 : pack->use_by_bank_txn[i][0] = 0UL;
683 6246 : }
684 26451 : for( ulong i=bank_tile_cnt; i<FD_PACK_MAX_BANK_TILES; i++ ) {
685 25932 : pack->use_by_bank [i] = NULL;
686 25932 : pack->use_by_bank_cnt[i] = 0UL;
687 25932 : pack->use_by_bank_txn[i] = NULL;
688 25932 : }
689 :
690 519 : fd_histf_new( pack->txn_per_microblock, FD_MHIST_MIN( PACK, TOTAL_TRANSACTIONS_PER_MICROBLOCK_COUNT ),
691 519 : FD_MHIST_MAX( PACK, TOTAL_TRANSACTIONS_PER_MICROBLOCK_COUNT ) );
692 519 : fd_histf_new( pack->vote_per_microblock, FD_MHIST_MIN( PACK, VOTES_PER_MICROBLOCK_COUNT ),
693 519 : FD_MHIST_MAX( PACK, VOTES_PER_MICROBLOCK_COUNT ) );
694 :
695 519 : fd_histf_new( pack->scheduled_cus_per_block, FD_MHIST_MIN( PACK, CUS_SCHEDULED ),
696 519 : FD_MHIST_MAX( PACK, CUS_SCHEDULED ) );
697 519 : fd_histf_new( pack->rebated_cus_per_block, FD_MHIST_MIN( PACK, CUS_REBATED ),
698 519 : FD_MHIST_MAX( PACK, CUS_REBATED ) );
699 519 : fd_histf_new( pack->net_cus_per_block, FD_MHIST_MIN( PACK, CUS_NET ),
700 519 : FD_MHIST_MAX( PACK, CUS_NET ) );
701 :
702 519 : pack->use_bundles = 0;
703 :
704 519 : pack->bitset_avail[ 0 ] = FD_PACK_BITSET_SLOWPATH;
705 177671 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) pack->bitset_avail[ i+1UL ] = (ushort)i;
706 519 : pack->bitset_avail_cnt = FD_PACK_BITSET_MAX;
707 :
708 519 : bitset_map_new( _acct_bitset, lg_acct_in_trp );
709 :
710 519 : fd_chkdup_new( pack->chkdup, rng );
711 :
712 519 : return mem;
713 519 : }
714 :
715 : fd_pack_t *
716 519 : fd_pack_join( void * mem ) {
717 519 : FD_SCRATCH_ALLOC_INIT( l, mem );
718 519 : fd_pack_t * pack = FD_SCRATCH_ALLOC_APPEND( l, FD_PACK_ALIGN, sizeof(fd_pack_t) );
719 :
720 0 : ulong pack_depth = pack->pack_depth;
721 519 : ulong bank_tile_cnt = pack->bank_tile_cnt;
722 :
723 519 : ulong max_acct_in_treap = pack_depth * FD_TXN_ACCT_ADDR_MAX;
724 519 : ulong max_acct_in_flight = bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * pack->lim->max_txn_per_microblock + 1UL);
725 519 : ulong max_txn_in_flight = bank_tile_cnt * pack->lim->max_txn_per_microblock;
726 519 : ulong max_w_per_block = fd_ulong_min( pack->lim->max_cost_per_block / FD_PACK_COST_PER_WRITABLE_ACCT,
727 519 : pack->lim->max_txn_per_microblock * pack->lim->max_microblocks_per_block * FD_TXN_ACCT_ADDR_MAX );
728 519 : ulong written_list_max = fd_ulong_min( max_w_per_block>>1, DEFAULT_WRITTEN_LIST_MAX );
729 :
730 519 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
731 519 : int lg_max_writers = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_w_per_block ) );
732 519 : int lg_depth = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*pack_depth ) );
733 519 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
734 519 : int lg_penalty_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap/PENALTY_TREAP_THRESHOLD ) );
735 :
736 :
737 519 : pack->pool = trp_pool_join( FD_SCRATCH_ALLOC_APPEND( l, trp_pool_align(), trp_pool_footprint ( pack_depth+1UL ) ) );
738 519 : pack->penalty_treaps= penalty_map_join(FD_SCRATCH_ALLOC_APPEND( l, penalty_map_align(),penalty_map_footprint( lg_penalty_trp )));
739 519 : pack->expiration_q = expq_join ( FD_SCRATCH_ALLOC_APPEND( l, expq_align(), expq_footprint ( pack_depth+1UL ) ) );
740 519 : pack->acct_in_use = acct_uses_join( FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_uses_tbl_sz ) ) );
741 519 : pack->writer_costs = acct_uses_join( FD_SCRATCH_ALLOC_APPEND( l, acct_uses_align(), acct_uses_footprint( lg_max_writers ) ) );
742 519 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t*)*written_list_max );
743 519 : pack->signature_map = sig2txn_join( FD_SCRATCH_ALLOC_APPEND( l, sig2txn_align(), sig2txn_footprint ( lg_depth ) ) );
744 519 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(fd_pack_addr_use_t)*max_acct_in_flight );
745 519 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 32UL, sizeof(ulong)*max_txn_in_flight );
746 519 : pack->acct_to_bitset= bitset_map_join( FD_SCRATCH_ALLOC_APPEND( l, bitset_map_align(), bitset_map_footprint( lg_acct_in_trp) ) );
747 :
748 519 : FD_MGAUGE_SET( PACK, PENDING_TRANSACTIONS_HEAP_SIZE, pack_depth );
749 519 : return pack;
750 519 : }
751 :
752 :
753 : /* Returns 0 on failure, 1 on success for a vote, 2 on success for a
754 : non-vote. */
755 : static int
756 : fd_pack_estimate_rewards_and_compute( fd_txn_e_t * txne,
757 13572561 : fd_pack_ord_txn_t * out ) {
758 13572561 : fd_txn_t * txn = TXN(txne->txnp);
759 13572561 : ulong sig_rewards = FD_PACK_FEE_PER_SIGNATURE * txn->signature_cnt; /* Easily in [5000, 635000] */
760 :
761 13572561 : ulong execution_cus;
762 13572561 : ulong adtl_rewards;
763 13572561 : ulong precompile_sigs;
764 13572561 : ulong cost = fd_pack_compute_cost( txn, txne->txnp->payload, &txne->txnp->flags, &execution_cus, &adtl_rewards, &precompile_sigs );
765 :
766 13572561 : if( FD_UNLIKELY( !cost ) ) return 0;
767 :
768 : /* precompile_sigs <= 16320, so after the addition,
769 : sig_rewards < 83,000,000 */
770 13572558 : sig_rewards += FD_PACK_FEE_PER_SIGNATURE * precompile_sigs;
771 :
772 : /* No fancy CU estimation in this version of pack
773 : for( ulong i=0UL; i<(ulong)txn->instr_cnt; i++ ) {
774 : uchar prog_id_idx = txn->instr[ i ].program_id;
775 : fd_acct_addr_t const * acct_addr = fd_txn_get_acct_addrs( txn, txnp->payload ) + (ulong)prog_id_idx;
776 : }
777 : */
778 13572558 : out->rewards = (adtl_rewards < (UINT_MAX - sig_rewards)) ? (uint)(sig_rewards + adtl_rewards) : UINT_MAX;
779 13572558 : out->compute_est = (uint)cost;
780 13572558 : out->txn->pack_cu.requested_execution_cus = (uint)execution_cus;
781 13572558 : out->txn->pack_cu.non_execution_cus = (uint)(cost - execution_cus);
782 :
783 : #if DETAILED_LOGGING
784 : FD_LOG_NOTICE(( "TXN estimated compute %lu+-%f. Rewards: %lu + %lu", compute_expected, (double)compute_variance, sig_rewards, adtl_rewards ));
785 : #endif
786 :
787 13572558 : return fd_int_if( txne->txnp->flags & FD_TXN_P_FLAGS_IS_SIMPLE_VOTE, 1, 2 );
788 13572561 : }
789 :
790 : /* Can the fee payer afford to pay a transaction with the specified
791 : price? Returns 1 if so, 0 otherwise. This is just a stub that
792 : always returns 1 for now. In general, this function can't be totally
793 : accurate, because the transactions immediately prior to this one can
794 : affect the balance of this fee payer, but a simple check here may be
795 : helpful for reducing spam. */
796 : static int
797 : fd_pack_can_fee_payer_afford( fd_acct_addr_t const * acct_addr,
798 13572558 : ulong price /* in lamports */) {
799 13572558 : (void)acct_addr;
800 13572558 : (void)price;
801 13572558 : return 1;
802 13572558 : }
803 :
804 :
805 :
806 :
807 :
808 13694961 : fd_txn_e_t * fd_pack_insert_txn_init( fd_pack_t * pack ) { return trp_pool_ele_acquire( pack->pool )->txn_e; }
809 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 ); }
810 :
811 111 : #define REJECT( reason ) do { \
812 111 : trp_pool_ele_release( pack->pool, ord ); \
813 111 : return FD_PACK_INSERT_REJECT_ ## reason; \
814 111 : } while( 0 )
815 :
816 280418 : #define ACCT_IDX_TO_PTR( idx ) (__extension__( { \
817 280418 : ulong __idx = (idx); \
818 280418 : fd_ptr_if( __idx<fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ), accts, alt_adj )+__idx; \
819 280418 : }))
820 70608888 : #define ACCT_ITER_TO_PTR( iter ) (__extension__( { \
821 70608888 : ulong __idx = fd_txn_acct_iter_idx( iter ); \
822 70608888 : fd_ptr_if( __idx<fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM ), accts, alt_adj )+__idx; \
823 70608888 : }))
824 :
825 : int
826 : fd_pack_insert_txn_fini( fd_pack_t * pack,
827 : fd_txn_e_t * txne,
828 13572561 : ulong expires_at ) {
829 :
830 13572561 : fd_pack_ord_txn_t * ord = (fd_pack_ord_txn_t *)txne;
831 :
832 13572561 : fd_txn_t * txn = TXN(txne->txnp);
833 13572561 : uchar * payload = txne->txnp->payload;
834 :
835 13572561 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, payload );
836 : /* alt_adj is the pointer to the ALT expansion, adjusted so that if
837 : account address n is the first that comes from the ALT, it can be
838 : accessed with adj_lut[n]. */
839 13572561 : fd_acct_addr_t const * alt = ord->txn_e->alt_accts;
840 13572561 : fd_acct_addr_t const * alt_adj = ord->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
841 13572561 : ulong imm_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
842 13572561 : ulong alt_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALT );
843 :
844 13572561 : int est_result = fd_pack_estimate_rewards_and_compute( txne, ord );
845 13572561 : if( FD_UNLIKELY( !est_result ) ) REJECT( ESTIMATION_FAIL );
846 :
847 13572558 : ord->expires_at = expires_at;
848 13572558 : int is_vote = est_result==1;
849 :
850 13572558 : int writes_to_sysvar = 0;
851 13572558 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
852 28316307 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
853 14743749 : writes_to_sysvar |= fd_pack_unwritable_contains( ACCT_ITER_TO_PTR( iter ) );
854 14743749 : }
855 :
856 13572558 : int bundle_blacklist = 0;
857 13572558 : if( FD_UNLIKELY( pack->use_bundles ) ) {
858 0 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_ALL );
859 0 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
860 0 : bundle_blacklist |= fd_pack_tip_prog_check_blacklist( ACCT_ITER_TO_PTR( iter ) );
861 0 : }
862 0 : }
863 :
864 13572558 : fd_ed25519_sig_t const * sig = fd_txn_get_signatures( txn, payload );
865 13572558 : fd_chkdup_t * chkdup = pack->chkdup;
866 :
867 : /* Throw out transactions ... */
868 : /* ... that are unfunded */
869 13572558 : if( FD_UNLIKELY( !fd_pack_can_fee_payer_afford( accts, ord->rewards ) ) ) REJECT( UNAFFORDABLE );
870 : /* ... that are so big they'll never run */
871 13572558 : if( FD_UNLIKELY( ord->compute_est >= pack->lim->max_cost_per_block ) ) REJECT( TOO_LARGE );
872 : /* ... that load too many accounts (ignoring 9LZdXeKGeBV6hRLdxS1rHbHoEUsKqesCC2ZAPTPKJAbK) */
873 13572558 : if( FD_UNLIKELY( fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALL )>64UL ) ) REJECT( ACCOUNT_CNT );
874 : /* ... that duplicate an account address */
875 13572555 : if( FD_UNLIKELY( fd_chkdup_check( chkdup, accts, imm_cnt, alt, alt_cnt ) ) ) REJECT( DUPLICATE_ACCT );
876 : /* ... that try to write to a sysvar */
877 13572552 : if( FD_UNLIKELY( writes_to_sysvar ) ) REJECT( WRITES_SYSVAR );
878 : /* ... that we already know about */
879 13572465 : if( FD_UNLIKELY( sig2txn_query( pack->signature_map, sig, NULL ) ) ) REJECT( DUPLICATE );
880 : /* ... that have already expired */
881 13572462 : if( FD_UNLIKELY( expires_at<pack->expire_before ) ) REJECT( EXPIRED );
882 : /* ... that use an account that violates bundle rules */
883 13572450 : if( FD_UNLIKELY( bundle_blacklist & 1 ) ) REJECT( BUNDLE_BLACKLIST );
884 :
885 :
886 13572450 : int replaces = 0;
887 13572450 : if( FD_UNLIKELY( pack->pending_txn_cnt == pack->pack_depth ) ) {
888 : /* If the tree is full, we want to see if this is better than the
889 : worst element in the pool before inserting. If the new
890 : transaction is better than that one, we'll delete it and insert
891 : the new transaction. Otherwise, we'll throw away this
892 : transaction.
893 :
894 : We want to bias the definition of "worst" here to provide better
895 : quality of service. For example, if the pool is filled with
896 : transactions that all write to the same account or are all votes,
897 : we want to bias towards treating one of those transactions as the
898 : worst, even if they pay slightly higher fees per computer unit,
899 : since we know we won't actually be able to schedule them all.
900 :
901 : This is a tricky task, however. All our notions of priority and
902 : better/worse are based on static information about the
903 : transaction, and there's not an easy way to take into account
904 : global information, for example, how many other transactions
905 : contend with this one. One idea is to build a heap (not a treap,
906 : since we only need pop-min, insert, and delete) with one element
907 : for each element in the pool, with a "delete me" score that's
908 : related but not identical to the normal score. This would allow
909 : building in some global information. The downside is that the
910 : global information that gets integrated is static. E.g. if you
911 : bias a transaction's "delete me" score to make it more likely to
912 : be deleted because there are many conflicting transactions in the
913 : pool, the score stays biased, even if the global conditions
914 : change (unless you come up with some complicated re-scoring
915 : scheme). This can work, since when the pool is full, the global
916 : bias factors are unlikely to change significantly at the relevant
917 : timescales.
918 :
919 : However, rather than this, we implement a simpler probabilistic
920 : scheme. We'll sample M transactions, find the worst transaction
921 : in each of the M treaps, compute a "delete me" score for those
922 : <= M transactions, and delete the worst. If one penalty treap is
923 : starting to get big, then it becomes very likely that the random
924 : sample will find it and choose to delete a transaction from it.
925 :
926 : The exact formula for the "delete me" score should be the matter
927 : of some more intense quantitative research. For now, we'll just
928 : use this:
929 :
930 : Treap with N transactions Scale Factor
931 : Pending 1.0 unless inserting a vote and votes < 25%
932 : Pending votes 1.0 until 75% of depth, then 0
933 : Penalty treap 1.0 at <= 100 transactions, then sqrt(100/N)
934 :
935 : We'll also use M=8. */
936 494592 : float worst_score = FLT_MAX;
937 494592 : fd_pack_ord_txn_t * worst = NULL;
938 4451328 : for( ulong i=0UL; i<8UL; i++ ) {
939 3956736 : ulong sample_i = fd_rng_uint_roll( pack->rng, (uint)(pack->pack_depth+1UL) );
940 :
941 3956736 : fd_pack_ord_txn_t * sample = &pack->pool[ sample_i ];
942 : /* There is exactly one free one, the one that's currently being
943 : inserted, so we can choose it with probability 1/(depth+1),
944 : which is small. If it does happen, just take the previous one,
945 : unless there isn't one. */
946 3956736 : if( FD_UNLIKELY( sample->root==FD_ORD_TXN_ROOT_FREE ) ) sample += fd_int_if( sample_i==0UL, 1, -1 );
947 :
948 3956736 : int root_idx = sample->root;
949 3956736 : float score = 0.0f;
950 3956736 : switch( root_idx & FD_ORD_TXN_ROOT_TAG_MASK ) {
951 0 : case FD_ORD_TXN_ROOT_FREE: {
952 0 : FD_TEST( 0 );
953 0 : break;
954 0 : }
955 3937295 : case FD_ORD_TXN_ROOT_PENDING: {
956 3937295 : ulong vote_cnt = treap_ele_cnt( pack->pending_votes );
957 3937295 : if( FD_LIKELY( !is_vote || (vote_cnt>=pack->pack_depth/4UL ) ) ) score = (float)sample->rewards / (float)sample->compute_est;
958 3937295 : break;
959 0 : }
960 0 : case FD_ORD_TXN_ROOT_PENDING_VOTE: {
961 0 : ulong vote_cnt = treap_ele_cnt( pack->pending_votes );
962 0 : if( FD_LIKELY( is_vote || (vote_cnt<=3UL*pack->pack_depth/4UL ) ) ) score = (float)sample->rewards / (float)sample->compute_est;
963 0 : break;
964 0 : }
965 19441 : case FD_ORD_TXN_ROOT_PENALTY( 0 ): {
966 19441 : fd_txn_t * txn = TXN( sample->txn );
967 19441 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, sample->txn->payload );
968 19441 : fd_acct_addr_t const * alt_adj = sample->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
969 19441 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( root_idx ) );
970 19441 : fd_pack_penalty_treap_t * q = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
971 19441 : FD_TEST( q );
972 19441 : ulong cnt = treap_ele_cnt( q->penalty_treap );
973 19441 : score = (float)sample->rewards / (float)sample->compute_est * sqrtf( 100.0f / (float)cnt );
974 19441 : break;
975 19441 : }
976 3956736 : }
977 3956736 : worst = fd_ptr_if( score<worst_score, sample, worst );
978 3956736 : worst_score = fd_float_if( worst_score<score, worst_score, score );
979 3956736 : }
980 :
981 494592 : float incoming_score = (float)ord->rewards / (float)ord->compute_est;
982 494592 : if( FD_UNLIKELY( incoming_score<worst_score ) ) REJECT( PRIORITY );
983 :
984 494592 : replaces = 1;
985 494592 : fd_ed25519_sig_t const * worst_sig = fd_txn_get_signatures( TXN( worst->txn ), worst->txn->payload );
986 494592 : fd_pack_delete_transaction( pack, worst_sig );
987 494592 : }
988 :
989 :
990 : /* At this point, we know we have space to insert the transaction and
991 : we've committed to insert it. */
992 :
993 13572450 : FD_PACK_BITSET_CLEAR( ord->rw_bitset );
994 13572450 : FD_PACK_BITSET_CLEAR( ord->w_bitset );
995 :
996 13572450 : ulong cumulative_penalty = 0UL;
997 13572450 : ulong penalty_i = 0UL;
998 : /* Since the pool uses ushorts, the size of the pool is < USHORT_MAX.
999 : Each transaction can reference an account at most once, which means
1000 : that the total number of references for an account is < USHORT_MAX.
1001 : If these were ulongs, the array would be 512B, which is kind of a
1002 : lot to zero out.*/
1003 13572450 : ushort penalties[ FD_TXN_ACCT_ADDR_MAX ] = {0};
1004 13572450 : uchar penalty_idx[ FD_TXN_ACCT_ADDR_MAX ];
1005 :
1006 13572450 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1007 28315917 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1008 14743467 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1009 14743467 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, acct, NULL );
1010 14743467 : if( FD_UNLIKELY( q==NULL ) ) {
1011 13258728 : q = bitset_map_insert( pack->acct_to_bitset, acct );
1012 13258728 : q->ref_cnt = 0UL;
1013 13258728 : q->first_instance = ord;
1014 13258728 : q->first_instance_was_write = 1;
1015 13258728 : q->bit = FD_PACK_BITSET_FIRST_INSTANCE;
1016 13258728 : } else if( FD_UNLIKELY( q->bit == FD_PACK_BITSET_FIRST_INSTANCE ) ) {
1017 5979 : q->bit = pack->bitset_avail[ pack->bitset_avail_cnt ];
1018 5979 : pack->bitset_avail_cnt = fd_ulong_if( !!pack->bitset_avail_cnt, pack->bitset_avail_cnt-1UL, 0UL );
1019 :
1020 5979 : FD_PACK_BITSET_SETN( q->first_instance->rw_bitset, q->bit );
1021 5979 : if( q->first_instance_was_write ) FD_PACK_BITSET_SETN( q->first_instance->w_bitset, q->bit );
1022 5979 : }
1023 14743467 : ulong penalty = fd_ulong_max( q->ref_cnt, PENALTY_TREAP_THRESHOLD )-PENALTY_TREAP_THRESHOLD;
1024 14743467 : if( FD_UNLIKELY( penalty ) ) {
1025 1030398 : penalties [ penalty_i ] = (ushort)penalty;
1026 1030398 : penalty_idx[ penalty_i ] = (uchar )fd_txn_acct_iter_idx( iter );
1027 1030398 : penalty_i++;
1028 1030398 : cumulative_penalty += penalty;
1029 1030398 : }
1030 :
1031 14743467 : q->ref_cnt++;
1032 14743467 : FD_PACK_BITSET_SETN( ord->rw_bitset, q->bit );
1033 14743467 : FD_PACK_BITSET_SETN( ord->w_bitset , q->bit );
1034 14743467 : }
1035 :
1036 13572450 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1037 18118134 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1038 :
1039 4545684 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1040 4545684 : if( FD_UNLIKELY( fd_pack_unwritable_contains( &acct ) ) ) continue;
1041 :
1042 3063162 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, acct, NULL );
1043 3063162 : if( FD_UNLIKELY( q==NULL ) ) {
1044 23727 : q = bitset_map_insert( pack->acct_to_bitset, acct );
1045 23727 : q->ref_cnt = 0UL;
1046 23727 : q->first_instance = ord;
1047 23727 : q->first_instance_was_write = 0;
1048 23727 : q->bit = FD_PACK_BITSET_FIRST_INSTANCE;
1049 3039435 : } else if( FD_UNLIKELY( q->bit == FD_PACK_BITSET_FIRST_INSTANCE ) ) {
1050 10632 : q->bit = pack->bitset_avail[ pack->bitset_avail_cnt ];
1051 10632 : pack->bitset_avail_cnt = fd_ulong_if( !!pack->bitset_avail_cnt, pack->bitset_avail_cnt-1UL, 0UL );
1052 :
1053 10632 : FD_PACK_BITSET_SETN( q->first_instance->rw_bitset, q->bit );
1054 10632 : if( q->first_instance_was_write ) FD_PACK_BITSET_SETN( q->first_instance->w_bitset, q->bit );
1055 10632 : }
1056 :
1057 3063162 : q->ref_cnt++;
1058 3063162 : FD_PACK_BITSET_SETN( ord->rw_bitset, q->bit );
1059 3063162 : }
1060 :
1061 13572450 : treap_t * insert_into = pack->pending;
1062 :
1063 13572450 : if( FD_UNLIKELY( cumulative_penalty && !is_vote ) ) { /* Optimize for high parallelism case */
1064 : /* Compute a weighted random choice */
1065 258273 : ulong roll = (ulong)fd_rng_uint_roll( pack->rng, (uint)cumulative_penalty ); /* cumulative_penalty < USHORT_MAX*64 < UINT_MAX */
1066 258273 : ulong i = 0UL;
1067 : /* Find the right one. This can be done in O(log N), but I imagine
1068 : N is normally so small that doesn't matter. */
1069 643976 : while( roll>=penalties[i] ) roll -= (ulong)penalties[i++];
1070 :
1071 258273 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( penalty_idx[i] );
1072 258273 : fd_pack_penalty_treap_t * q = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
1073 258273 : if( FD_UNLIKELY( q==NULL ) ) {
1074 2181 : q = penalty_map_insert( pack->penalty_treaps, penalty_acct );
1075 2181 : treap_new( q->penalty_treap, pack->pack_depth );
1076 2181 : }
1077 258273 : insert_into = q->penalty_treap;
1078 258273 : ord->root = FD_ORD_TXN_ROOT_PENALTY( penalty_idx[i] );
1079 13314177 : } else {
1080 13314177 : ord->root = fd_int_if( is_vote, FD_ORD_TXN_ROOT_PENDING_VOTE, FD_ORD_TXN_ROOT_PENDING );
1081 :
1082 13314177 : fd_pack_smallest_t * smallest = fd_ptr_if( is_vote, &pack->pending_votes_smallest[0], pack->pending_smallest );
1083 13314177 : smallest->cus = fd_ulong_min( smallest->cus, ord->compute_est );
1084 13314177 : smallest->bytes = fd_ulong_min( smallest->bytes, txne->txnp->payload_sz );
1085 13314177 : }
1086 :
1087 13572450 : pack->pending_txn_cnt++;
1088 :
1089 13572450 : sig2txn_insert( pack->signature_map, fd_txn_get_signatures( txn, payload ) );
1090 :
1091 13572450 : fd_pack_expq_t temp[ 1 ] = {{ .expires_at = expires_at, .txn = ord }};
1092 13572450 : expq_insert( pack->expiration_q, temp );
1093 :
1094 13572450 : if( FD_LIKELY( is_vote ) ) {
1095 37596 : treap_ele_insert( pack->pending_votes, ord, pack->pool );
1096 37596 : return replaces ? FD_PACK_INSERT_ACCEPT_VOTE_REPLACE : FD_PACK_INSERT_ACCEPT_VOTE_ADD;
1097 13534854 : } else {
1098 13534854 : treap_ele_insert( insert_into, ord, pack->pool );
1099 13534854 : return replaces ? FD_PACK_INSERT_ACCEPT_NONVOTE_REPLACE : FD_PACK_INSERT_ACCEPT_NONVOTE_ADD;
1100 13534854 : }
1101 13572450 : }
1102 : #undef REJECT
1103 :
1104 : void
1105 0 : fd_pack_metrics_write( fd_pack_t const * pack ) {
1106 0 : ulong pending_votes = treap_ele_cnt( pack->pending_votes );
1107 0 : FD_MGAUGE_SET( PACK, AVAILABLE_TRANSACTIONS, pack->pending_txn_cnt );
1108 0 : FD_MGAUGE_SET( PACK, AVAILABLE_VOTE_TRANSACTIONS, pending_votes );
1109 0 : FD_MGAUGE_SET( PACK, CONFLICTING_TRANSACTIONS, pack->pending_txn_cnt - treap_ele_cnt( pack->pending ) - pending_votes );
1110 0 : FD_MGAUGE_SET( PACK, SMALLEST_PENDING_TRANSACTION, pack->pending_smallest->cus );
1111 0 : }
1112 :
1113 : typedef struct {
1114 : ushort clear_rw_bit;
1115 : ushort clear_w_bit;
1116 : } release_result_t;
1117 :
1118 : static inline release_result_t
1119 : release_bit_reference( fd_pack_t * pack,
1120 17805693 : fd_acct_addr_t const * acct ) {
1121 :
1122 17805693 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, *acct, NULL );
1123 17805693 : FD_TEST( q ); /* q==NULL not be possible */
1124 :
1125 17805693 : q->ref_cnt--;
1126 :
1127 17805693 : if( FD_UNLIKELY( q->ref_cnt==0UL ) ) {
1128 13281519 : ushort bit = q->bit;
1129 13281519 : bitset_map_remove( pack->acct_to_bitset, q );
1130 13281519 : if( FD_LIKELY( bit<FD_PACK_BITSET_MAX ) ) pack->bitset_avail[ ++(pack->bitset_avail_cnt) ] = bit;
1131 :
1132 13281519 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, *acct, NULL );
1133 13281519 : if( FD_LIKELY( use ) ) {
1134 12787101 : use->in_use_by |= FD_PACK_IN_USE_BIT_CLEARED;
1135 12787101 : release_result_t ret = { .clear_rw_bit = bit,
1136 12787101 : .clear_w_bit = fd_ushort_if( !!(use->in_use_by & FD_PACK_IN_USE_WRITABLE), bit, FD_PACK_BITSET_MAX ) };
1137 12787101 : return ret;
1138 12787101 : }
1139 13281519 : }
1140 5018592 : release_result_t ret = { .clear_rw_bit = FD_PACK_BITSET_MAX, .clear_w_bit = FD_PACK_BITSET_MAX };
1141 5018592 : return ret;
1142 17805693 : }
1143 :
1144 : typedef struct {
1145 : ulong cus_scheduled;
1146 : ulong txns_scheduled;
1147 : ulong bytes_scheduled;
1148 : } sched_return_t;
1149 :
1150 : static inline sched_return_t
1151 : fd_pack_schedule_impl( fd_pack_t * pack,
1152 : treap_t * sched_from,
1153 : ulong cu_limit,
1154 : ulong txn_limit,
1155 : ulong byte_limit,
1156 : ulong bank_tile,
1157 : fd_pack_smallest_t * smallest_in_treap,
1158 : ulong * use_by_bank_txn,
1159 1476432 : fd_txn_p_t * out ) {
1160 :
1161 1476432 : fd_pack_ord_txn_t * pool = pack->pool;
1162 1476432 : fd_pack_addr_use_t * acct_in_use = pack->acct_in_use;
1163 1476432 : fd_pack_addr_use_t * writer_costs = pack->writer_costs;
1164 :
1165 1476432 : fd_pack_addr_use_t ** written_list = pack->written_list;
1166 1476432 : ulong written_list_cnt = pack->written_list_cnt;
1167 1476432 : ulong written_list_max = pack->written_list_max;
1168 :
1169 1476432 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
1170 1476432 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
1171 1476432 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
1172 1476432 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
1173 :
1174 1476432 : fd_pack_addr_use_t * use_by_bank = pack->use_by_bank [bank_tile];
1175 1476432 : ulong use_by_bank_cnt = pack->use_by_bank_cnt[bank_tile];
1176 :
1177 1476432 : ulong max_write_cost_per_acct = pack->lim->max_write_cost_per_acct;
1178 :
1179 1476432 : ulong txns_scheduled = 0UL;
1180 1476432 : ulong cus_scheduled = 0UL;
1181 1476432 : ulong bytes_scheduled = 0UL;
1182 :
1183 1476432 : ulong bank_tile_mask = 1UL << bank_tile;
1184 :
1185 1476432 : ulong fast_path = 0UL;
1186 1476432 : ulong slow_path = 0UL;
1187 1476432 : ulong cu_limit_c = 0UL;
1188 1476432 : ulong byte_limit_c = 0UL;
1189 1476432 : ulong write_limit_c = 0UL;
1190 :
1191 1476432 : ulong min_cus = ULONG_MAX;
1192 1476432 : ulong min_bytes = ULONG_MAX;
1193 :
1194 1476432 : if( FD_UNLIKELY( (cu_limit<smallest_in_treap->cus) | (txn_limit==0UL) | (byte_limit<smallest_in_treap->bytes) ) ) {
1195 799653 : sched_return_t to_return = { .cus_scheduled = 0UL, .txns_scheduled = 0UL, .bytes_scheduled = 0UL };
1196 799653 : return to_return;
1197 799653 : }
1198 :
1199 676779 : treap_rev_iter_t prev = treap_idx_null();
1200 32887362 : for( treap_rev_iter_t _cur=treap_rev_iter_init( sched_from, pool ); !treap_rev_iter_done( _cur ); _cur=prev ) {
1201 : /* Capture next so that we can delete while we iterate. */
1202 32804988 : prev = treap_rev_iter_next( _cur, pool );
1203 :
1204 32804988 : # if FD_HAS_X86
1205 32804988 : _mm_prefetch( &(pool[ prev ].prev), _MM_HINT_T0 );
1206 32804988 : # endif
1207 :
1208 32804988 : fd_pack_ord_txn_t const * cur = treap_rev_iter_ele_const( _cur, pool );
1209 :
1210 32804988 : min_cus = fd_ulong_min( min_cus, cur->compute_est );
1211 32804988 : min_bytes = fd_ulong_min( min_bytes, cur->txn->payload_sz );
1212 :
1213 32804988 : ulong conflicts = 0UL;
1214 :
1215 32804988 : if( FD_UNLIKELY( cur->compute_est>cu_limit ) ) {
1216 : /* Too big to be scheduled at the moment, but might be okay for
1217 : the next microblock, so we don't want to delay it. */
1218 0 : cu_limit_c++;
1219 0 : continue;
1220 0 : }
1221 :
1222 : /* Likely? Unlikely? */
1223 32804988 : if( FD_LIKELY( !FD_PACK_BITSET_INTERSECT4_EMPTY( bitset_rw_in_use, bitset_w_in_use, cur->w_bitset, cur->rw_bitset ) ) ) {
1224 19727613 : fast_path++;
1225 19727613 : continue;
1226 19727613 : }
1227 :
1228 13077375 : if( FD_UNLIKELY( cur->txn->payload_sz>byte_limit ) ) {
1229 0 : byte_limit_c++;
1230 0 : continue;
1231 0 : }
1232 :
1233 13077375 : fd_txn_t const * txn = TXN(cur->txn);
1234 13077375 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
1235 13077375 : fd_acct_addr_t const * alt_adj = cur->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1236 : /* Check conflicts between this transaction's writable accounts and
1237 : current readers */
1238 13077375 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1239 27316056 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1240 :
1241 14238687 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1242 :
1243 14238687 : fd_pack_addr_use_t * in_wcost_table = acct_uses_query( writer_costs, acct, NULL );
1244 14238687 : if( FD_UNLIKELY( in_wcost_table && in_wcost_table->total_cost+cur->compute_est > max_write_cost_per_acct ) ) {
1245 : /* Can't be scheduled until the next block */
1246 6 : conflicts = ULONG_MAX;
1247 6 : break;
1248 6 : }
1249 :
1250 14238681 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, acct, NULL );
1251 14238681 : if( FD_UNLIKELY( use ) ) conflicts |= use->in_use_by; /* break? */
1252 14238681 : }
1253 :
1254 13077375 : if( FD_UNLIKELY( conflicts==ULONG_MAX ) ) {
1255 6 : write_limit_c++;
1256 6 : continue;
1257 6 : }
1258 :
1259 13077369 : if( FD_UNLIKELY( conflicts ) ) {
1260 6 : slow_path++;
1261 6 : continue;
1262 6 : }
1263 :
1264 : /* Check conflicts between this transaction's readonly accounts and
1265 : current writers */
1266 13077363 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1267 16622460 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1268 :
1269 3545097 : fd_acct_addr_t const * acct = ACCT_ITER_TO_PTR( iter );
1270 3545097 : if( fd_pack_unwritable_contains( acct ) ) continue; /* No need to track sysvars because they can't be writable */
1271 :
1272 2558586 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, *acct, NULL );
1273 2558586 : if( use ) conflicts |= (use->in_use_by & FD_PACK_IN_USE_WRITABLE) ? use->in_use_by : 0UL;
1274 2558586 : }
1275 :
1276 13077363 : if( FD_UNLIKELY( conflicts ) ) {
1277 0 : slow_path++;
1278 0 : continue;
1279 0 : }
1280 :
1281 : /* Include this transaction in the microblock! */
1282 13077363 : FD_PACK_BITSET_OR( bitset_rw_in_use, cur->rw_bitset );
1283 13077363 : FD_PACK_BITSET_OR( bitset_w_in_use, cur->w_bitset );
1284 :
1285 13077363 : if(
1286 4359121 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
1287 4359121 : FD_LIKELY( cur->txn->payload_sz>=1024UL )
1288 : #else
1289 8718242 : 0
1290 8718242 : #endif
1291 13077363 : ) {
1292 4225 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
1293 4225 : _mm512_stream_si512( (void*)(out->payload+ 0UL), _mm512_load_epi64( cur->txn->payload+ 0UL ) );
1294 4225 : _mm512_stream_si512( (void*)(out->payload+ 64UL), _mm512_load_epi64( cur->txn->payload+ 64UL ) );
1295 4225 : _mm512_stream_si512( (void*)(out->payload+ 128UL), _mm512_load_epi64( cur->txn->payload+ 128UL ) );
1296 4225 : _mm512_stream_si512( (void*)(out->payload+ 192UL), _mm512_load_epi64( cur->txn->payload+ 192UL ) );
1297 4225 : _mm512_stream_si512( (void*)(out->payload+ 256UL), _mm512_load_epi64( cur->txn->payload+ 256UL ) );
1298 4225 : _mm512_stream_si512( (void*)(out->payload+ 320UL), _mm512_load_epi64( cur->txn->payload+ 320UL ) );
1299 4225 : _mm512_stream_si512( (void*)(out->payload+ 384UL), _mm512_load_epi64( cur->txn->payload+ 384UL ) );
1300 4225 : _mm512_stream_si512( (void*)(out->payload+ 448UL), _mm512_load_epi64( cur->txn->payload+ 448UL ) );
1301 4225 : _mm512_stream_si512( (void*)(out->payload+ 512UL), _mm512_load_epi64( cur->txn->payload+ 512UL ) );
1302 4225 : _mm512_stream_si512( (void*)(out->payload+ 576UL), _mm512_load_epi64( cur->txn->payload+ 576UL ) );
1303 4225 : _mm512_stream_si512( (void*)(out->payload+ 640UL), _mm512_load_epi64( cur->txn->payload+ 640UL ) );
1304 4225 : _mm512_stream_si512( (void*)(out->payload+ 704UL), _mm512_load_epi64( cur->txn->payload+ 704UL ) );
1305 4225 : _mm512_stream_si512( (void*)(out->payload+ 768UL), _mm512_load_epi64( cur->txn->payload+ 768UL ) );
1306 4225 : _mm512_stream_si512( (void*)(out->payload+ 832UL), _mm512_load_epi64( cur->txn->payload+ 832UL ) );
1307 4225 : _mm512_stream_si512( (void*)(out->payload+ 896UL), _mm512_load_epi64( cur->txn->payload+ 896UL ) );
1308 4225 : _mm512_stream_si512( (void*)(out->payload+ 960UL), _mm512_load_epi64( cur->txn->payload+ 960UL ) );
1309 4225 : _mm512_stream_si512( (void*)(out->payload+1024UL), _mm512_load_epi64( cur->txn->payload+1024UL ) );
1310 4225 : _mm512_stream_si512( (void*)(out->payload+1088UL), _mm512_load_epi64( cur->txn->payload+1088UL ) );
1311 4225 : _mm512_stream_si512( (void*)(out->payload+1152UL), _mm512_load_epi64( cur->txn->payload+1152UL ) );
1312 4225 : _mm512_stream_si512( (void*)(out->payload+1216UL), _mm512_load_epi64( cur->txn->payload+1216UL ) );
1313 : /* Copied out to 1280 bytes, which copies some other fields we needed to
1314 : copy anyway. */
1315 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, payload_sz )+sizeof(((fd_txn_p_t*)NULL)->payload_sz )<=1280UL, nt_memcpy );
1316 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, blockhash_slot )+sizeof(((fd_txn_p_t*)NULL)->blockhash_slot)<=1280UL, nt_memcpy );
1317 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, flags )+sizeof(((fd_txn_p_t*)NULL)->flags )<=1280UL, nt_memcpy );
1318 4225 : FD_STATIC_ASSERT( offsetof(fd_txn_p_t, _ ) <=1280UL, nt_memcpy );
1319 4225 : const ulong offset_into_txn = 1280UL - offsetof(fd_txn_p_t, _ );
1320 4225 : fd_memcpy( offset_into_txn+(uchar *)TXN(out), offset_into_txn+(uchar const *)txn,
1321 4225 : fd_ulong_max( offset_into_txn, fd_txn_footprint( txn->instr_cnt, txn->addr_table_lookup_cnt ) )-offset_into_txn );
1322 4225 : #endif
1323 13073138 : } else {
1324 13073138 : fd_memcpy( out->payload, cur->txn->payload, cur->txn->payload_sz );
1325 13073138 : fd_memcpy( TXN(out), txn, fd_txn_footprint( txn->instr_cnt, txn->addr_table_lookup_cnt ) );
1326 13073138 : out->payload_sz = cur->txn->payload_sz;
1327 13073138 : out->pack_cu.requested_execution_cus = cur->txn->pack_cu.requested_execution_cus;
1328 13073138 : out->pack_cu.non_execution_cus = cur->txn->pack_cu.non_execution_cus;
1329 13073138 : out->flags = cur->txn->flags;
1330 13073138 : }
1331 13077363 : out++;
1332 :
1333 13077363 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1334 27316032 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1335 14238669 : fd_acct_addr_t acct_addr = *ACCT_ITER_TO_PTR( iter );
1336 :
1337 14238669 : fd_pack_addr_use_t * in_wcost_table = acct_uses_query( writer_costs, acct_addr, NULL );
1338 14238669 : if( !in_wcost_table ) {
1339 788031 : in_wcost_table = acct_uses_insert( writer_costs, acct_addr );
1340 788031 : in_wcost_table->total_cost = 0UL;
1341 788031 : written_list[ written_list_cnt ] = in_wcost_table;
1342 788031 : written_list_cnt = fd_ulong_min( written_list_cnt+1UL, written_list_max-1UL );
1343 788031 : }
1344 14238669 : in_wcost_table->total_cost += cur->compute_est;
1345 :
1346 14238669 : fd_pack_addr_use_t * use = acct_uses_insert( acct_in_use, acct_addr );
1347 14238669 : use->in_use_by = bank_tile_mask | FD_PACK_IN_USE_WRITABLE;
1348 :
1349 14238669 : use_by_bank[use_by_bank_cnt++] = *use;
1350 :
1351 : /* If there aren't any more references to this account in the
1352 : heap, it can't cause any conflicts. That means we actually
1353 : don't need to record that we are using it, which is good
1354 : because we want to release the bit. */
1355 14238669 : release_result_t ret = release_bit_reference( pack, &acct_addr );
1356 14238669 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
1357 14238669 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
1358 14238669 : }
1359 13077363 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1360 16622460 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1361 :
1362 3545097 : fd_acct_addr_t acct_addr = *ACCT_ITER_TO_PTR( iter );
1363 :
1364 3545097 : if( fd_pack_unwritable_contains( &acct_addr ) ) continue; /* No need to track sysvars because they can't be writable */
1365 :
1366 2558586 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use, acct_addr, NULL );
1367 2558586 : if( !use ) { use = acct_uses_insert( acct_in_use, acct_addr ); use->in_use_by = 0UL; }
1368 :
1369 2558586 : if( !(use->in_use_by & bank_tile_mask) ) use_by_bank[use_by_bank_cnt++] = *use;
1370 2558586 : use->in_use_by |= bank_tile_mask;
1371 2558586 : use->in_use_by &= ~FD_PACK_IN_USE_BIT_CLEARED;
1372 :
1373 :
1374 2558586 : release_result_t ret = release_bit_reference( pack, &acct_addr );
1375 2558586 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, ret.clear_rw_bit );
1376 2558586 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, ret.clear_w_bit );
1377 2558586 : }
1378 :
1379 13077363 : txns_scheduled += 1UL; txn_limit -= 1UL;
1380 13077363 : cus_scheduled += cur->compute_est; cu_limit -= cur->compute_est;
1381 13077363 : bytes_scheduled += cur->txn->payload_sz; byte_limit -= cur->txn->payload_sz;
1382 :
1383 13077363 : *(use_by_bank_txn++) = use_by_bank_cnt;
1384 :
1385 13077363 : fd_ed25519_sig_t const * sig0 = fd_txn_get_signatures( txn, cur->txn->payload );
1386 :
1387 13077363 : fd_pack_sig_to_txn_t * in_tbl = sig2txn_query( pack->signature_map, sig0, NULL );
1388 13077363 : sig2txn_remove( pack->signature_map, in_tbl );
1389 :
1390 13077363 : expq_remove( pack->expiration_q, cur->expq_idx );
1391 13077363 : treap_idx_remove( sched_from, _cur, pool );
1392 13077363 : trp_pool_idx_release( pool, _cur );
1393 13077363 : pack->pending_txn_cnt--;
1394 :
1395 13077363 : if( FD_UNLIKELY( (cu_limit<smallest_in_treap->cus) | (txn_limit==0UL) | (byte_limit<smallest_in_treap->bytes) ) ) break;
1396 13077363 : }
1397 :
1398 676779 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_TAKEN, txns_scheduled );
1399 676779 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_CU_LIMIT, cu_limit_c );
1400 676779 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_FAST_PATH, fast_path );
1401 676779 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_BYTE_LIMIT, byte_limit_c );
1402 676779 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_WRITE_COST, write_limit_c );
1403 676779 : FD_MCNT_INC( PACK, TRANSACTION_SCHEDULE_SLOW_PATH, slow_path );
1404 :
1405 : #if DETAILED_LOGGING
1406 : FD_LOG_NOTICE(( "cu_limit: %lu, fast_path: %lu, slow_path: %lu", cu_limit_c, fast_path, slow_path ));
1407 : #endif
1408 :
1409 : /* If we scanned the whole treap and didn't break early, we now have a
1410 : better estimate of the smallest. */
1411 676779 : if( FD_UNLIKELY( treap_rev_iter_done( prev ) ) ) {
1412 85419 : smallest_in_treap->cus = min_cus;
1413 85419 : smallest_in_treap->bytes = min_bytes;
1414 85419 : }
1415 :
1416 676779 : pack->use_by_bank_cnt[bank_tile] = use_by_bank_cnt;
1417 676779 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
1418 676779 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
1419 :
1420 676779 : pack->written_list_cnt = written_list_cnt;
1421 :
1422 676779 : sched_return_t to_return = { .cus_scheduled=cus_scheduled, .txns_scheduled=txns_scheduled, .bytes_scheduled=bytes_scheduled };
1423 676779 : return to_return;
1424 1476432 : }
1425 :
1426 : int
1427 : fd_pack_microblock_complete( fd_pack_t * pack,
1428 738216 : ulong bank_tile ) {
1429 : /* If the account is in use writably, and it's in use by this banking
1430 : tile, then this banking tile must be the sole writer to it, so it's
1431 : always okay to clear the writable bit. */
1432 738216 : ulong clear_mask = ~((1UL<<bank_tile) | FD_PACK_IN_USE_WRITABLE);
1433 :
1434 : /* If nothing outstanding, bail quickly */
1435 738216 : if( FD_UNLIKELY( !(pack->outstanding_microblock_mask & (1UL<<bank_tile)) ) ) return 0;
1436 :
1437 670812 : FD_PACK_BITSET_DECLARE( bitset_rw_in_use );
1438 670812 : FD_PACK_BITSET_DECLARE( bitset_w_in_use );
1439 670812 : FD_PACK_BITSET_COPY( bitset_rw_in_use, pack->bitset_rw_in_use );
1440 670812 : FD_PACK_BITSET_COPY( bitset_w_in_use, pack->bitset_w_in_use );
1441 :
1442 670812 : fd_pack_addr_use_t * base = pack->use_by_bank[bank_tile];
1443 :
1444 670812 : fd_pack_ord_txn_t * best = NULL;
1445 670812 : fd_pack_penalty_treap_t * best_penalty = NULL;
1446 670812 : ulong txn_cnt = 0UL;
1447 :
1448 16851819 : for( ulong i=0UL; i<pack->use_by_bank_cnt[bank_tile]; i++ ) {
1449 16181007 : fd_pack_addr_use_t * use = acct_uses_query( pack->acct_in_use, base[i].key, NULL );
1450 16181007 : FD_TEST( use );
1451 16181007 : use->in_use_by &= clear_mask;
1452 :
1453 : /* In order to properly bound the size of bitset_map, we need to
1454 : release the "reference" to the account when we schedule it.
1455 : However, that poses a bit of a problem here, because by the time
1456 : we complete the microblock, that account could have been assigned
1457 : a different bit in the bitset. The scheduling step tells us if
1458 : that is the case, and if so, we know that the bits in
1459 : bitset_w_in_use and bitset_rw_in_use were already cleared as
1460 : necessary.
1461 :
1462 : Note that it's possible for BIT_CLEARED to be set and then unset
1463 : by later uses, but then the account would be in use on other
1464 : banks, so we wouldn't try to observe the old value. For example:
1465 : Suppose bit 0->account A, bit 1->account B, and we have two
1466 : transactions that read A, B. We schedule a microblock to bank 0,
1467 : taking both transactions, which sets the counts for A, B to 0,
1468 : and releases the bits, clearing bits 0 and 1, and setting
1469 : BIT_CLEARED. Then we get two more transactions that read
1470 : accounts C, D, A, B, and they get assigned 0->C, 1->D, 2->A,
1471 : 3->B. We try to schedule a microblock to bank 1 that takes one
1472 : of those transactions. This unsets BIT_CLEARED for A, B.
1473 : Finally, the first microblock completes. Even though the bitset
1474 : map has the new bits for A and B which are "wrong" compared to
1475 : when the transaction was initially scheduled, those bits have
1476 : already been cleared and reset properly in the bitset as needed.
1477 : A and B will still be in use by bank 1, so we won't clear any
1478 : bits. If, on the other hand, the microblock scheduled to bank 1
1479 : completes first, bits 0 and 1 will be cleared for accounts C and
1480 : D, while bits 2 and 3 will remain set, which is correct. Then
1481 : when bank 0 completes, bits 2 and 3 will be cleared. */
1482 16181007 : if( FD_LIKELY( !use->in_use_by ) ) { /* if in_use_by==0, doesn't include BIT_CLEARED */
1483 3401988 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, base[i].key, NULL );
1484 3401988 : FD_TEST( q );
1485 3401988 : FD_PACK_BITSET_CLEARN( bitset_w_in_use, q->bit );
1486 3401988 : FD_PACK_BITSET_CLEARN( bitset_rw_in_use, q->bit );
1487 :
1488 : /* Because this account is no longer in use, it might be possible
1489 : to schedule a transaction that writes to it. Check it's
1490 : penalty treap if it has one, and potentially move it to the
1491 : main treap. */
1492 3401988 : fd_pack_penalty_treap_t * p_trp = penalty_map_query( pack->penalty_treaps, base[i].key, NULL );
1493 3401988 : if( FD_UNLIKELY( p_trp ) ) {
1494 639208 : fd_pack_ord_txn_t * best_in_trp = treap_rev_iter_ele( treap_rev_iter_init( p_trp->penalty_treap, pack->pool ), pack->pool );
1495 639208 : if( FD_UNLIKELY( !best || COMPARE_WORSE( best, best_in_trp ) ) ) {
1496 255569 : best = best_in_trp;
1497 255569 : best_penalty = p_trp;
1498 255569 : }
1499 639208 : }
1500 3401988 : }
1501 :
1502 16181007 : if( FD_LIKELY( !(use->in_use_by & ~FD_PACK_IN_USE_BIT_CLEARED) ) ) acct_uses_remove( pack->acct_in_use, use );
1503 :
1504 16181007 : if( FD_UNLIKELY( i+1UL==pack->use_by_bank_txn[ bank_tile ][ txn_cnt ] ) ) {
1505 13073553 : txn_cnt++;
1506 13073553 : if( FD_LIKELY( best ) ) {
1507 : /* move best to the main treap */
1508 255569 : treap_ele_remove( best_penalty->penalty_treap, best, pack->pool );
1509 255569 : best->root = FD_ORD_TXN_ROOT_PENDING;
1510 255569 : treap_ele_insert( pack->pending, best, pack->pool );
1511 :
1512 255569 : pack->pending_smallest->cus = fd_ulong_min( pack->pending_smallest->cus, best->compute_est );
1513 255569 : pack->pending_smallest->bytes = fd_ulong_min( pack->pending_smallest->bytes, best->txn_e->txnp->payload_sz );
1514 :
1515 255569 : if( FD_UNLIKELY( !treap_ele_cnt( best_penalty->penalty_treap ) ) ) {
1516 2181 : treap_delete( treap_leave( best_penalty->penalty_treap ) );
1517 : /* Removal invalidates any pointers we got from
1518 : penalty_map_query, but we immediately set these to NULL, so
1519 : we're not keeping any pointers around. */
1520 2181 : penalty_map_remove( pack->penalty_treaps, best_penalty );
1521 2181 : }
1522 255569 : best = NULL;
1523 255569 : best_penalty = NULL;
1524 255569 : }
1525 13073553 : }
1526 16181007 : }
1527 :
1528 670812 : pack->use_by_bank_cnt[bank_tile] = 0UL;
1529 :
1530 670812 : FD_PACK_BITSET_COPY( pack->bitset_rw_in_use, bitset_rw_in_use );
1531 670812 : FD_PACK_BITSET_COPY( pack->bitset_w_in_use, bitset_w_in_use );
1532 :
1533 : /* outstanding_microblock_mask never has the writable bit set, so we
1534 : don't care about clearing it here either. */
1535 670812 : pack->outstanding_microblock_mask &= clear_mask;
1536 670812 : return 1;
1537 670812 : }
1538 :
1539 :
1540 : ulong
1541 : fd_pack_schedule_next_microblock( fd_pack_t * pack,
1542 : ulong total_cus,
1543 : float vote_fraction,
1544 : ulong bank_tile,
1545 738216 : fd_txn_p_t * out ) {
1546 :
1547 : /* TODO: Decide if these are exactly how we want to handle limits */
1548 738216 : total_cus = fd_ulong_min( total_cus, pack->lim->max_cost_per_block - pack->cumulative_block_cost );
1549 738216 : ulong vote_cus = fd_ulong_min( (ulong)((float)total_cus * vote_fraction),
1550 738216 : pack->lim->max_vote_cost_per_block - pack->cumulative_vote_cost );
1551 738216 : ulong vote_reserved_txns = fd_ulong_min( vote_cus/FD_PACK_TYPICAL_VOTE_COST,
1552 738216 : (ulong)((float)pack->lim->max_txn_per_microblock * vote_fraction) );
1553 :
1554 :
1555 738216 : if( FD_UNLIKELY( (pack->microblock_cnt>=pack->lim->max_microblocks_per_block) ) ) {
1556 0 : FD_MCNT_INC( PACK, MICROBLOCK_PER_BLOCK_LIMIT, 1UL );
1557 0 : return 0UL;
1558 0 : }
1559 738216 : if( FD_UNLIKELY( pack->data_bytes_consumed+MICROBLOCK_DATA_OVERHEAD+FD_TXN_MIN_SERIALIZED_SZ>pack->lim->max_data_bytes_per_block) ) {
1560 0 : FD_MCNT_INC( PACK, DATA_PER_BLOCK_LIMIT, 1UL );
1561 0 : return 0UL;
1562 0 : }
1563 :
1564 738216 : ulong * use_by_bank_txn = pack->use_by_bank_txn[ bank_tile ];
1565 :
1566 738216 : ulong cu_limit = total_cus - vote_cus;
1567 738216 : ulong txn_limit = pack->lim->max_txn_per_microblock - vote_reserved_txns;
1568 738216 : ulong scheduled = 0UL;
1569 738216 : ulong byte_limit = pack->lim->max_data_bytes_per_block - pack->data_bytes_consumed - MICROBLOCK_DATA_OVERHEAD;
1570 :
1571 738216 : sched_return_t status, status1;
1572 :
1573 : /* Schedule vote transactions */
1574 738216 : 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 );
1575 :
1576 738216 : scheduled += status1.txns_scheduled;
1577 738216 : pack->cumulative_vote_cost += status1.cus_scheduled;
1578 738216 : pack->cumulative_block_cost += status1.cus_scheduled;
1579 738216 : pack->data_bytes_consumed += status1.bytes_scheduled;
1580 738216 : byte_limit -= status1.bytes_scheduled;
1581 738216 : use_by_bank_txn += status1.txns_scheduled;
1582 : /* Add any remaining CUs/txns to the non-vote limits */
1583 738216 : txn_limit += vote_reserved_txns - status1.txns_scheduled;
1584 738216 : cu_limit += vote_cus - status1.cus_scheduled;
1585 :
1586 :
1587 : /* Fill any remaining space with non-vote transactions */
1588 738216 : 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 );
1589 :
1590 738216 : scheduled += status.txns_scheduled;
1591 738216 : pack->cumulative_block_cost += status.cus_scheduled;
1592 738216 : pack->data_bytes_consumed += status.bytes_scheduled;
1593 :
1594 738216 : ulong nonempty = (ulong)(scheduled>0UL);
1595 738216 : pack->microblock_cnt += nonempty;
1596 738216 : pack->outstanding_microblock_mask |= nonempty << bank_tile;
1597 738216 : pack->data_bytes_consumed += nonempty * MICROBLOCK_DATA_OVERHEAD;
1598 :
1599 : /* Update metrics counters */
1600 738216 : FD_MGAUGE_SET( PACK, AVAILABLE_TRANSACTIONS, pack->pending_txn_cnt );
1601 738216 : FD_MGAUGE_SET( PACK, AVAILABLE_VOTE_TRANSACTIONS, treap_ele_cnt( pack->pending_votes ) );
1602 738216 : FD_MGAUGE_SET( PACK, CUS_CONSUMED_IN_BLOCK, pack->cumulative_block_cost );
1603 :
1604 738216 : fd_histf_sample( pack->txn_per_microblock, scheduled );
1605 738216 : fd_histf_sample( pack->vote_per_microblock, status1.txns_scheduled );
1606 :
1607 246072 : #if FD_HAS_AVX512 && FD_PACK_USE_NON_TEMPORAL_MEMCPY
1608 246072 : _mm_sfence();
1609 246072 : #endif
1610 :
1611 738216 : return scheduled;
1612 738216 : }
1613 :
1614 268194 : ulong fd_pack_bank_tile_cnt ( fd_pack_t const * pack ) { return pack->bank_tile_cnt; }
1615 0 : ulong fd_pack_current_block_cost( fd_pack_t const * pack ) { return pack->cumulative_block_cost; }
1616 :
1617 :
1618 : void
1619 : fd_pack_set_block_limits( fd_pack_t * pack,
1620 : ulong max_microblocks_per_block,
1621 0 : ulong max_data_bytes_per_block ) {
1622 0 : pack->lim->max_microblocks_per_block = max_microblocks_per_block;
1623 0 : pack->lim->max_data_bytes_per_block = max_data_bytes_per_block;
1624 0 : }
1625 :
1626 : void
1627 : fd_pack_rebate_cus( fd_pack_t * pack,
1628 : fd_txn_p_t const * txns,
1629 6 : ulong txn_cnt ) {
1630 6 : fd_pack_addr_use_t * writer_costs = pack->writer_costs;
1631 :
1632 6 : ulong cumulative_vote_cost = pack->cumulative_vote_cost;
1633 6 : ulong cumulative_block_cost = pack->cumulative_block_cost;
1634 6 : ulong data_bytes_consumed = pack->data_bytes_consumed;
1635 6 : ulong cumulative_rebated_cus = pack->cumulative_rebated_cus;
1636 :
1637 18 : for( ulong i=0UL; i<txn_cnt; i++ ) {
1638 12 : fd_txn_p_t const * txn = txns+i;
1639 12 : ulong rebated_cus = txn->bank_cu.rebated_cus;
1640 12 : int in_block = !!(txn->flags & FD_TXN_P_FLAGS_EXECUTE_SUCCESS);
1641 :
1642 12 : cumulative_block_cost -= rebated_cus;
1643 12 : cumulative_vote_cost -= fd_ulong_if( txn->flags & FD_TXN_P_FLAGS_IS_SIMPLE_VOTE, rebated_cus, 0UL );
1644 12 : data_bytes_consumed -= fd_ulong_if( !in_block, txn->payload_sz, 0UL );
1645 12 : cumulative_rebated_cus += rebated_cus;
1646 :
1647 12 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( TXN(txn), txn->payload );
1648 : /* TODO: For now, we don't have a way to rebate writer costs for ALT
1649 : accounts. We've thrown away the ALT expansion at this point.
1650 : The rebate system is going to be rewritten soon for performance,
1651 : so it's okay. */
1652 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 );
1653 36 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1654 :
1655 24 : ulong i=fd_txn_acct_iter_idx( iter );
1656 :
1657 24 : fd_pack_addr_use_t * in_wcost_table = acct_uses_query( writer_costs, accts[i], NULL );
1658 24 : if( FD_UNLIKELY( !in_wcost_table ) ) FD_LOG_ERR(( "Rebate to unknown written account" ));
1659 24 : in_wcost_table->total_cost -= rebated_cus;
1660 : /* Important: Even if this is 0, don't delete it from the table so
1661 : that the insert order doesn't get messed up. */
1662 24 : }
1663 12 : }
1664 :
1665 6 : pack->cumulative_vote_cost = cumulative_vote_cost;
1666 6 : pack->cumulative_block_cost = cumulative_block_cost;
1667 6 : pack->data_bytes_consumed = data_bytes_consumed;
1668 6 : pack->cumulative_rebated_cus = cumulative_rebated_cus;
1669 6 : }
1670 :
1671 :
1672 : ulong
1673 : fd_pack_expire_before( fd_pack_t * pack,
1674 9 : ulong expire_before ) {
1675 9 : expire_before = fd_ulong_max( expire_before, pack->expire_before );
1676 9 : ulong deleted_cnt = 0UL;
1677 9 : fd_pack_expq_t * prq = pack->expiration_q;
1678 18 : while( (expq_cnt( prq )>0UL) & (prq->expires_at<expire_before) ) {
1679 9 : fd_pack_ord_txn_t * expired = prq->txn;
1680 :
1681 9 : fd_ed25519_sig_t const * expired_sig = fd_txn_get_signatures( TXN( expired->txn ), expired->txn->payload );
1682 : /* fd_pack_delete_transaction also removes it from the heap */
1683 9 : fd_pack_delete_transaction( pack, expired_sig );
1684 9 : deleted_cnt++;
1685 9 : }
1686 :
1687 9 : pack->expire_before = expire_before;
1688 9 : return deleted_cnt;
1689 9 : }
1690 :
1691 : void
1692 2646 : fd_pack_end_block( fd_pack_t * pack ) {
1693 2646 : fd_histf_sample( pack->net_cus_per_block, pack->cumulative_block_cost );
1694 2646 : fd_histf_sample( pack->rebated_cus_per_block, pack->cumulative_rebated_cus );
1695 2646 : fd_histf_sample( pack->scheduled_cus_per_block, pack->cumulative_rebated_cus + pack->cumulative_block_cost );
1696 :
1697 2646 : pack->microblock_cnt = 0UL;
1698 2646 : pack->data_bytes_consumed = 0UL;
1699 2646 : pack->cumulative_block_cost = 0UL;
1700 2646 : pack->cumulative_vote_cost = 0UL;
1701 2646 : pack->cumulative_rebated_cus = 0UL;
1702 :
1703 2646 : acct_uses_clear( pack->acct_in_use );
1704 :
1705 2646 : if( FD_LIKELY( pack->written_list_cnt<pack->written_list_max-1UL ) ) {
1706 : /* The less dangerous way of doing this is to instead record the
1707 : keys we inserted and do a query followed by a delete for each
1708 : key. The downside of that is that keys are 32 bytes and a
1709 : pointer is only 8 bytes, plus the computational cost for the
1710 : query.
1711 :
1712 : However, if we're careful, we can pull this off. We require two
1713 : things. First, we started from an empty map and did nothing but
1714 : insert and update. In particular, no deletions. Second, we have
1715 : to be careful to delete in the opposite order that we inserted.
1716 : This is essentially like unwinding the inserts we did. The
1717 : common case is that the element after the one we delete will be
1718 : empty, so we'll hit that case. It's possible that there's
1719 : another independent probe sequence that will be entirely intact
1720 : starting in the element after, but we'll never hit the MAP_MOVE
1721 : case. */
1722 776193 : for( ulong i=0UL; i<pack->written_list_cnt; i++ ) {
1723 773547 : acct_uses_remove( pack->writer_costs, pack->written_list[ pack->written_list_cnt - 1UL - i ] );
1724 773547 : }
1725 2646 : } else {
1726 0 : acct_uses_clear( pack->writer_costs );
1727 0 : }
1728 2646 : pack->written_list_cnt = 0UL;
1729 :
1730 2646 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
1731 2646 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
1732 :
1733 9234 : for( ulong i=0UL; i<pack->bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i] = 0UL;
1734 :
1735 : /* If our stake is low and we don't become leader often, end_block
1736 : might get called on the order of O(1/hr), which feels too
1737 : infrequent to do anything related to metrics. However, we only
1738 : update the histograms when we are leader, so this is actually a
1739 : good place to copy them. */
1740 2646 : FD_MHIST_COPY( PACK, TOTAL_TRANSACTIONS_PER_MICROBLOCK_COUNT, pack->txn_per_microblock );
1741 2646 : FD_MHIST_COPY( PACK, VOTES_PER_MICROBLOCK_COUNT, pack->vote_per_microblock );
1742 :
1743 2646 : FD_MGAUGE_SET( PACK, CUS_CONSUMED_IN_BLOCK, 0UL );
1744 2646 : FD_MHIST_COPY( PACK, CUS_SCHEDULED, pack->scheduled_cus_per_block );
1745 2646 : FD_MHIST_COPY( PACK, CUS_REBATED, pack->rebated_cus_per_block );
1746 2646 : FD_MHIST_COPY( PACK, CUS_NET, pack->net_cus_per_block );
1747 2646 : }
1748 :
1749 : static void
1750 : release_tree( treap_t * treap,
1751 0 : fd_pack_ord_txn_t * pool ) {
1752 0 : treap_fwd_iter_t next;
1753 0 : for( treap_fwd_iter_t it=treap_fwd_iter_init( treap, pool ); !treap_fwd_iter_idx( it ); it=next ) {
1754 0 : next = treap_fwd_iter_next( it, pool );
1755 0 : ulong idx = treap_fwd_iter_idx( it );
1756 0 : pool[ idx ].root = FD_ORD_TXN_ROOT_FREE;
1757 0 : treap_idx_remove ( treap, idx, pool );
1758 0 : trp_pool_idx_release( pool, idx );
1759 0 : }
1760 0 : }
1761 :
1762 : void
1763 0 : fd_pack_clear_all( fd_pack_t * pack ) {
1764 0 : pack->pending_txn_cnt = 0UL;
1765 0 : pack->microblock_cnt = 0UL;
1766 0 : pack->cumulative_block_cost = 0UL;
1767 0 : pack->cumulative_vote_cost = 0UL;
1768 0 : pack->cumulative_rebated_cus = 0UL;
1769 :
1770 0 : pack->pending_smallest->cus = ULONG_MAX;
1771 0 : pack->pending_smallest->bytes = ULONG_MAX;
1772 0 : pack->pending_votes_smallest->cus = ULONG_MAX;
1773 0 : pack->pending_votes_smallest->bytes = ULONG_MAX;
1774 :
1775 0 : release_tree( pack->pending, pack->pool );
1776 0 : release_tree( pack->pending_votes, pack->pool );
1777 0 : for( ulong i=0UL; i<pack->pack_depth+1UL; i++ ) {
1778 0 : if( FD_UNLIKELY( pack->pool[ i ].root!=FD_ORD_TXN_ROOT_FREE ) ) {
1779 0 : fd_pack_ord_txn_t * const del = pack->pool + i;
1780 0 : fd_txn_t * txn = TXN( del->txn );
1781 0 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, del->txn->payload );
1782 0 : fd_acct_addr_t const * alt_adj = del->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1783 0 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( del->root ) );
1784 0 : fd_pack_penalty_treap_t * penalty_treap = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
1785 0 : FD_TEST( penalty_treap );
1786 0 : release_tree( penalty_treap->penalty_treap, pack->pool );
1787 0 : }
1788 0 : }
1789 :
1790 0 : expq_remove_all( pack->expiration_q );
1791 :
1792 0 : acct_uses_clear( pack->acct_in_use );
1793 0 : acct_uses_clear( pack->writer_costs );
1794 :
1795 0 : sig2txn_clear( pack->signature_map );
1796 :
1797 0 : penalty_map_clear( pack->penalty_treaps );
1798 :
1799 0 : FD_PACK_BITSET_CLEAR( pack->bitset_rw_in_use );
1800 0 : FD_PACK_BITSET_CLEAR( pack->bitset_w_in_use );
1801 0 : bitset_map_clear( pack->acct_to_bitset );
1802 0 : pack->bitset_avail[ 0 ] = FD_PACK_BITSET_SLOWPATH;
1803 0 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) pack->bitset_avail[ i+1UL ] = (ushort)i;
1804 0 : pack->bitset_avail_cnt = FD_PACK_BITSET_MAX;
1805 :
1806 0 : for( ulong i=0UL; i<pack->bank_tile_cnt; i++ ) pack->use_by_bank_cnt[i] = 0UL;
1807 0 : }
1808 :
1809 : int
1810 : fd_pack_delete_transaction( fd_pack_t * pack,
1811 494646 : fd_ed25519_sig_t const * sig0 ) {
1812 494646 : fd_pack_sig_to_txn_t * in_tbl = sig2txn_query( pack->signature_map, sig0, NULL );
1813 :
1814 494646 : if( !in_tbl )
1815 24 : return 0;
1816 :
1817 : /* The static asserts enforce that the payload of the transaction is
1818 : the first element of the fd_pack_ord_txn_t struct. The signature
1819 : we insert is 1 byte into the start of the payload. */
1820 494622 : fd_pack_ord_txn_t * containing = (fd_pack_ord_txn_t *)( (uchar*)in_tbl->key - 1UL );
1821 :
1822 494622 : fd_txn_t * txn = TXN( containing->txn );
1823 494622 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, containing->txn->payload );
1824 494622 : fd_acct_addr_t const * alt_adj = containing->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1825 :
1826 494622 : treap_t * root = NULL;
1827 494622 : int root_idx = containing->root;
1828 494622 : fd_pack_penalty_treap_t * penalty_treap = NULL;
1829 494622 : switch( root_idx & FD_ORD_TXN_ROOT_TAG_MASK ) {
1830 0 : case FD_ORD_TXN_ROOT_FREE: /* Should be impossible */ return 0;
1831 491918 : case FD_ORD_TXN_ROOT_PENDING: root = pack->pending; break;
1832 0 : case FD_ORD_TXN_ROOT_PENDING_VOTE: root = pack->pending_votes; break;
1833 2704 : case FD_ORD_TXN_ROOT_PENALTY( 0 ): {
1834 2704 : fd_acct_addr_t penalty_acct = *ACCT_IDX_TO_PTR( FD_ORD_TXN_ROOT_PENALTY_ACCT_IDX( root_idx ) );
1835 2704 : penalty_treap = penalty_map_query( pack->penalty_treaps, penalty_acct, NULL );
1836 2704 : FD_TEST( penalty_treap );
1837 2704 : root = penalty_treap->penalty_treap;
1838 2704 : break;
1839 2704 : }
1840 494622 : }
1841 :
1842 494622 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1843 998490 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1844 :
1845 503868 : release_result_t ret = release_bit_reference( pack, ACCT_ITER_TO_PTR( iter ) );
1846 503868 : FD_PACK_BITSET_CLEARN( pack->bitset_rw_in_use, ret.clear_rw_bit );
1847 503868 : FD_PACK_BITSET_CLEARN( pack->bitset_w_in_use, ret.clear_w_bit );
1848 503868 : }
1849 :
1850 494622 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1851 1493814 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1852 999192 : if( FD_UNLIKELY( fd_pack_unwritable_contains( ACCT_ITER_TO_PTR( iter ) ) ) ) continue;
1853 :
1854 504570 : release_result_t ret = release_bit_reference( pack, ACCT_ITER_TO_PTR( iter ) );
1855 504570 : FD_PACK_BITSET_CLEARN( pack->bitset_rw_in_use, ret.clear_rw_bit );
1856 504570 : FD_PACK_BITSET_CLEARN( pack->bitset_w_in_use, ret.clear_w_bit );
1857 504570 : }
1858 494622 : expq_remove( pack->expiration_q, containing->expq_idx );
1859 494622 : containing->root = FD_ORD_TXN_ROOT_FREE;
1860 494622 : treap_ele_remove( root, containing, pack->pool );
1861 494622 : trp_pool_ele_release( pack->pool, containing );
1862 494622 : sig2txn_remove( pack->signature_map, in_tbl );
1863 494622 : pack->pending_txn_cnt--;
1864 :
1865 494622 : if( FD_UNLIKELY( penalty_treap && treap_ele_cnt( root )==0UL ) ) {
1866 0 : penalty_map_remove( pack->penalty_treaps, penalty_treap );
1867 0 : }
1868 :
1869 494622 : return 1;
1870 494622 : }
1871 :
1872 :
1873 : int
1874 : fd_pack_verify( fd_pack_t * pack,
1875 0 : void * scratch ) {
1876 : /* Invariants:
1877 : sig2txn_query has exact same contents as all treaps combined
1878 : root matches treap
1879 : Keys of acct_to_bitset is exactly union of all accounts in all
1880 : transactions in treaps, with ref counted appropriately
1881 : bits in bitset_avail is complement of bits allocated in
1882 : acct_to_bitset
1883 : expires_at consistent between treap, prq */
1884 :
1885 : /* TODO:
1886 : bitset_{r}w_in_use = bitset_map_query( everything in acct_in_use that doesn't have FD_PACK_IN_USE_BIT_CLEARED )
1887 : use_by_bank does not contain duplicates
1888 : use_by_bank consistent with acct_in_use
1889 : bitset_w_in_use & bitset_rw_in_use == bitset_w_in_use
1890 : elements in pool but not in a treap have root set to free
1891 : all penalty treaps have at least one transaction */
1892 0 : #define VERIFY_TEST( cond, ... ) do { \
1893 0 : if( FD_UNLIKELY( !(cond) ) ) { \
1894 0 : FD_LOG_WARNING(( __VA_ARGS__ )); \
1895 0 : return -(__LINE__); \
1896 0 : } \
1897 0 : } while( 0 )
1898 :
1899 0 : ulong max_acct_in_treap = pack->pack_depth * FD_TXN_ACCT_ADDR_MAX;
1900 0 : int lg_acct_in_trp = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_treap ) );
1901 0 : void * _bitset_map_copy = scratch;
1902 0 : void * _bitset_map_orig = bitset_map_leave( pack->acct_to_bitset );
1903 0 : fd_memcpy( _bitset_map_copy, _bitset_map_orig, bitset_map_footprint( lg_acct_in_trp ) );
1904 :
1905 0 : fd_pack_bitset_acct_mapping_t * bitset_copy = bitset_map_join( _bitset_map_copy );
1906 :
1907 : /* Check that each bit is in exactly one place */
1908 0 : FD_PACK_BITSET_DECLARE( processed ); FD_PACK_BITSET_CLEAR( processed );
1909 0 : FD_PACK_BITSET_DECLARE( bit ); FD_PACK_BITSET_CLEAR( bit );
1910 0 : FD_PACK_BITSET_DECLARE( full ); FD_PACK_BITSET_CLEAR( full );
1911 :
1912 0 : if( FD_UNLIKELY( pack->bitset_avail[0]!=FD_PACK_BITSET_SLOWPATH ) ) return -1;
1913 0 : for( ulong i=1UL; i<=pack->bitset_avail_cnt; i++ ) {
1914 0 : FD_PACK_BITSET_CLEAR( bit );
1915 0 : FD_PACK_BITSET_SETN( bit, pack->bitset_avail[ i ] );
1916 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ),
1917 0 : "bit %hu in avail set twice", pack->bitset_avail[ i ] );
1918 0 : FD_PACK_BITSET_OR( processed, bit );
1919 0 : }
1920 :
1921 0 : ulong total_references = 0UL;
1922 0 : for( ulong i=0UL; i<bitset_map_slot_cnt( bitset_copy ); i++ ) {
1923 0 : if( !bitset_map_key_inval( bitset_copy[ i ].key ) ) {
1924 0 : VERIFY_TEST( bitset_copy[ i ].ref_cnt>0UL, "account address in table with 0 ref count" );
1925 :
1926 0 : total_references += bitset_copy[ i ].ref_cnt;
1927 :
1928 0 : FD_PACK_BITSET_CLEAR( bit );
1929 0 : FD_PACK_BITSET_SETN( bit, bitset_copy[ i ].bit );
1930 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ), "bit %hu used twice", bitset_copy[ i ].bit );
1931 0 : FD_PACK_BITSET_OR( processed, bit );
1932 0 : }
1933 0 : }
1934 0 : for( ulong i=0UL; i<FD_PACK_BITSET_MAX; i++ ) {
1935 0 : FD_PACK_BITSET_CLEAR( bit );
1936 0 : FD_PACK_BITSET_SETN( bit, i );
1937 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, processed, processed ), "bit %lu missing", i );
1938 0 : FD_PACK_BITSET_SETN( full, i );
1939 0 : }
1940 :
1941 :
1942 0 : fd_pack_ord_txn_t * pool = pack->pool;
1943 0 : treap_t * treaps[ 2 ] = { pack->pending, pack->pending_votes };
1944 0 : ulong txn_cnt = 0UL;
1945 :
1946 0 : for( ulong k=0UL; k<2; k++ ) {
1947 0 : treap_t * treap = treaps[ k ];
1948 :
1949 0 : for( treap_rev_iter_t _cur=treap_rev_iter_init( treap, pool ); !treap_rev_iter_done( _cur );
1950 0 : _cur=treap_rev_iter_next( _cur, pool ) ) {
1951 0 : txn_cnt++;
1952 0 : fd_pack_ord_txn_t const * cur = treap_rev_iter_ele_const( _cur, pool );
1953 0 : fd_txn_t const * txn = TXN(cur->txn);
1954 0 : fd_acct_addr_t const * accts = fd_txn_get_acct_addrs( txn, cur->txn->payload );
1955 0 : fd_acct_addr_t const * alt_adj = cur->txn_e->alt_accts - fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
1956 :
1957 0 : fd_ed25519_sig_t const * sig0 = fd_txn_get_signatures( txn, cur->txn->payload );
1958 :
1959 0 : fd_pack_sig_to_txn_t * in_tbl = sig2txn_query( pack->signature_map, sig0, NULL );
1960 0 : VERIFY_TEST( in_tbl, "signature missing from sig2txn" );
1961 0 : VERIFY_TEST( in_tbl->key==sig0, "signature in sig2txn inconsistent" );
1962 0 : VERIFY_TEST( (ulong)(cur->root)==k+1, "treap element had bad root" );
1963 0 : VERIFY_TEST( cur->expires_at>=pack->expire_before, "treap element expired" );
1964 :
1965 0 : fd_pack_expq_t const * eq = pack->expiration_q + cur->expq_idx;
1966 0 : VERIFY_TEST( eq->txn==cur, "expq inconsistent" );
1967 0 : VERIFY_TEST( eq->expires_at==cur->expires_at, "expq expires_at inconsistent" );
1968 :
1969 0 : FD_PACK_BITSET_DECLARE( complement );
1970 0 : FD_PACK_BITSET_COPY( complement, full );
1971 0 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE );
1972 0 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1973 0 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1974 :
1975 0 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( bitset_copy, acct, NULL );
1976 0 : VERIFY_TEST( q, "account in transaction missing from bitset mapping" );
1977 0 : VERIFY_TEST( q->ref_cnt>0UL, "account in transaction ref_cnt already 0" );
1978 0 : q->ref_cnt--;
1979 0 : total_references--;
1980 :
1981 0 : FD_PACK_BITSET_CLEAR( bit );
1982 0 : FD_PACK_BITSET_SETN( bit, q->bit );
1983 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
1984 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->rw_bitset, cur->rw_bitset ), "missing from rw bitset" );
1985 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->w_bitset, cur->w_bitset ), "missing from w bitset" );
1986 0 : }
1987 0 : FD_PACK_BITSET_CLEARN( complement, q->bit );
1988 0 : }
1989 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( complement, complement, cur->w_bitset, cur->w_bitset ), "extra in w bitset" );
1990 :
1991 0 : for( fd_txn_acct_iter_t iter=fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_READONLY );
1992 0 : iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
1993 :
1994 0 : fd_acct_addr_t acct = *ACCT_ITER_TO_PTR( iter );
1995 0 : if( FD_UNLIKELY( fd_pack_unwritable_contains( &acct ) ) ) continue;
1996 0 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( bitset_copy, acct, NULL );
1997 0 : VERIFY_TEST( q, "account in transaction missing from bitset mapping" );
1998 0 : VERIFY_TEST( q->ref_cnt>0UL, "account in transaction ref_cnt already 0" );
1999 0 : q->ref_cnt--;
2000 0 : total_references--;
2001 :
2002 0 : FD_PACK_BITSET_CLEAR( bit );
2003 0 : FD_PACK_BITSET_SETN( bit, q->bit );
2004 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
2005 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, cur->rw_bitset, cur->rw_bitset ), "missing from rw bitset" );
2006 0 : }
2007 0 : FD_PACK_BITSET_CLEARN( complement, q->bit );
2008 0 : }
2009 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( complement, complement, cur->rw_bitset, cur->rw_bitset ), "extra in rw bitset" );
2010 0 : }
2011 0 : }
2012 :
2013 0 : bitset_map_leave( bitset_copy );
2014 :
2015 0 : VERIFY_TEST( total_references==0UL, "extra references in bitset mapping" );
2016 0 : VERIFY_TEST( txn_cnt==sig2txn_key_cnt( pack->signature_map ), "extra signatures in sig2txn" );
2017 :
2018 0 : bitset_map_join( _bitset_map_orig );
2019 :
2020 0 : ulong max_acct_in_flight = pack->bank_tile_cnt * (FD_TXN_ACCT_ADDR_MAX * pack->lim->max_txn_per_microblock + 1UL);
2021 0 : int lg_uses_tbl_sz = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*max_acct_in_flight ) );
2022 :
2023 0 : void * _acct_in_use_copy = scratch;
2024 0 : void * _acct_in_use_orig = acct_uses_leave( pack->acct_in_use );
2025 0 : fd_memcpy( _acct_in_use_copy, _acct_in_use_orig, acct_uses_footprint( lg_uses_tbl_sz ) );
2026 :
2027 0 : fd_pack_addr_use_t * acct_in_use_copy = acct_uses_join( _acct_in_use_copy );
2028 :
2029 0 : FD_PACK_BITSET_DECLARE( w_complement );
2030 0 : FD_PACK_BITSET_DECLARE( rw_complement );
2031 0 : FD_PACK_BITSET_COPY( w_complement, full );
2032 0 : FD_PACK_BITSET_COPY( rw_complement, full );
2033 :
2034 0 : FD_PACK_BITSET_DECLARE( rw_bitset ); FD_PACK_BITSET_COPY( rw_bitset, pack->bitset_rw_in_use );
2035 0 : FD_PACK_BITSET_DECLARE( w_bitset ); FD_PACK_BITSET_COPY( w_bitset, pack->bitset_w_in_use );
2036 :
2037 :
2038 0 : ulong const EMPTY_MASK = ~(FD_PACK_IN_USE_WRITABLE | FD_PACK_IN_USE_BIT_CLEARED);
2039 :
2040 0 : for( ulong bank=0UL; bank<pack->bank_tile_cnt; bank++ ) {
2041 :
2042 0 : fd_pack_addr_use_t const * base = pack->use_by_bank[ bank ];
2043 0 : ulong bank_mask = 1UL << bank;
2044 :
2045 0 : for( ulong i=0UL; i<pack->use_by_bank_cnt[ bank ]; i++ ) {
2046 0 : fd_pack_addr_use_t * use = acct_uses_query( acct_in_use_copy, base[i].key, NULL );
2047 0 : VERIFY_TEST( use, "acct in use by bank not in acct_in_use, or in uses_by_bank twice" );
2048 :
2049 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" );
2050 :
2051 0 : fd_pack_bitset_acct_mapping_t * q = bitset_map_query( pack->acct_to_bitset, base[i].key, NULL );
2052 : /* The normal case is that the acct->bit mapping is preserved
2053 : while in use by other transactions in the pending list. This
2054 : might not always happen though. It's okay for the mapping to
2055 : get deleted while the acct is in use, which is noted with
2056 : BIT_CLEARED. If that is set, the mapping may not exist, or it
2057 : may have been re-created, perhaps with a different bit. */
2058 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" );
2059 0 : else if( !(use->in_use_by & FD_PACK_IN_USE_BIT_CLEARED) ) {
2060 0 : FD_PACK_BITSET_CLEAR( bit );
2061 0 : FD_PACK_BITSET_SETN( bit, q->bit );
2062 0 : if( q->bit<FD_PACK_BITSET_MAX ) {
2063 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, rw_bitset, rw_bitset ), "missing from rw bitset" );
2064 0 : if( use->in_use_by & FD_PACK_IN_USE_WRITABLE ) {
2065 0 : VERIFY_TEST( !FD_PACK_BITSET_INTERSECT4_EMPTY( bit, bit, w_bitset, w_bitset ), "missing from w bitset" );
2066 0 : FD_PACK_BITSET_CLEARN( w_complement, q->bit );
2067 0 : }
2068 0 : }
2069 0 : FD_PACK_BITSET_CLEARN( rw_complement, q->bit );
2070 0 : }
2071 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" );
2072 :
2073 0 : use->in_use_by &= ~bank_mask;
2074 0 : if( !(use->in_use_by & EMPTY_MASK) ) acct_uses_remove( acct_in_use_copy, use );
2075 0 : }
2076 0 : }
2077 0 : VERIFY_TEST( acct_uses_key_cnt( acct_in_use_copy )==0UL, "stray uses in acct_in_use" );
2078 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( rw_complement, rw_complement, rw_bitset, rw_bitset ), "extra in rw bitset" );
2079 0 : VERIFY_TEST( FD_PACK_BITSET_INTERSECT4_EMPTY( w_complement, w_complement, w_bitset, w_bitset ), "extra in w bitset" );
2080 :
2081 0 : acct_uses_leave( acct_in_use_copy );
2082 :
2083 0 : acct_uses_join( _acct_in_use_orig );
2084 0 : return 0;
2085 0 : }
2086 :
2087 0 : void * fd_pack_leave ( fd_pack_t * pack ) { FD_COMPILER_MFENCE(); return (void *)pack; }
2088 0 : void * fd_pack_delete( void * mem ) { FD_COMPILER_MFENCE(); return mem; }
|
