LCOV - code coverage report
Current view: top level - disco/pack - fd_pack.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 1515 1634 92.7 %
Date: 2025-10-13 04:42:14 Functions: 49 55 89.1 %

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

Generated by: LCOV version 1.14