Line data Source code
1 : #ifndef HEADER_fd_src_flamenco_runtime_fd_txncache_private_h
2 : #define HEADER_fd_src_flamenco_runtime_fd_txncache_private_h
3 :
4 : #include "fd_txncache_shmem.h"
5 : #include "../fd_flamenco_base.h"
6 : #include "../fd_rwlock.h"
7 :
8 : /* The number of transactions in each page. This needs to be high
9 : enough to amoritze the cost of caller code reserving pages from,
10 : and returning pages to the pool, but not so high that the memory
11 : wasted from blockhashes with only one transaction is significant. */
12 :
13 215691689 : #define FD_TXNCACHE_TXNS_PER_PAGE (8192UL)
14 :
15 : /* The maximum distance a transaction blockhash reference can be
16 : (inclusive). For example, if no slots were skipped, and the value is
17 : 151, slot 300 is allowed to reference blockhashes from slots
18 : [149, 300). */
19 933 : #define FD_TXNCACHE_MAX_BLOCKHASH_DISTANCE (151UL)
20 :
21 : /* The global txn index (page*FD_TXNCACHE_TXNS_PER_PAGE+txn) is a uint
22 : with UINT_MAX as the null link, which bounds the txnpage pool. */
23 :
24 : #define FD_TXNCACHE_MAX_TXNPAGES (UINT_MAX/FD_TXNCACHE_TXNS_PER_PAGE)
25 :
26 : struct __attribute__((packed)) fd_txncache_single_txn {
27 : uint blockcache_next; /* Pointer to the next element in the blockcache hash chain containing this entry from the pool. */
28 : uint generation; /* The generation of the fork when this transaction was inserted. Used to
29 : determine if the transaction is still valid for a fork that might have
30 : advanced since insertion. */
31 :
32 : fd_txncache_fork_id_t fork_id; /* Fork that the transaction was executed on. A transaction might be in the cache
33 : multiple times if it was executed on multiple forks. */
34 : uchar txnhash[ 20UL ]; /* The transaction message hash, truncated to 20 bytes. The hash is not always the first 20
35 : bytes, but is 20 bytes starting at some arbitrary offset given by the txnhash_offset value
36 : of the containing blockcache entry. */
37 : };
38 :
39 : typedef struct fd_txncache_single_txn fd_txncache_single_txn_t;
40 :
41 : FD_STATIC_ASSERT( sizeof(fd_txncache_single_txn_t)==30UL, fd_txncache_single_txn );
42 :
43 : struct fd_txncache_txnpage {
44 : ushort free; /* The number of free txn entries in this page. */
45 : fd_txncache_single_txn_t txns[ FD_TXNCACHE_TXNS_PER_PAGE][ 1 ]; /* The transactions in the page. */
46 : };
47 :
48 : typedef struct fd_txncache_txnpage fd_txncache_txnpage_t;
49 :
50 : struct fd_txncache_blockcache_shmem {
51 : fd_txncache_fork_id_t parent_id;
52 : fd_txncache_fork_id_t child_id;
53 : fd_txncache_fork_id_t sibling_id;
54 :
55 : int frozen; /* This is used to enforce invariants on the caller of the txncache.
56 : -1: invalid
57 : 0: active
58 : 1: semi frozen, only happens during snapshot load
59 : 2: frozen, should not be modified */
60 :
61 : uint generation;
62 :
63 : fd_hash_t blockhash; /* The blockhash that this entry is for. */
64 : ulong txnhash_offset; /* To save memory, the Agave validator decided to truncate the hash of transactions stored in
65 : this memory to 20 bytes rather than 32 bytes. The bytes used are not the first 20 as you
66 : might expect, but instead the first 20 starting at some random offset into the transaction
67 : hash (starting between 0 and len(hash)-20, a/k/a 44 for signatures, and 12 for hashes).
68 :
69 : In an unfortunate turn, the offset is also propagated to peers via. snapshot responses,
70 : which only communicate the offset and the respective 20 bytes. To make sure we are
71 : deduplicating incoming transactions correctly, we must replicate this system even though
72 : it would be easier to just always take the first 20 bytes. For transactions that we
73 : insert into the cache ourselves, we do just always use a key_offset of zero, so this is
74 : only nonzero when constructed form a peer snapshot. */
75 :
76 : ulong pages_cnt; /* The number of txnpages currently in use to store the transactions in this blockcache. */
77 :
78 : struct {
79 : ulong next;
80 : } pool;
81 :
82 : struct {
83 : ulong next;
84 : } slist;
85 :
86 : struct {
87 : ulong next;
88 : ulong prev;
89 : } blockhash_map;
90 : };
91 :
92 : typedef struct fd_txncache_blockcache_shmem fd_txncache_blockcache_shmem_t;
93 :
94 : #define POOL_NAME blockcache_pool
95 : #define POOL_T fd_txncache_blockcache_shmem_t
96 : #define POOL_IDX_T ulong
97 29862 : #define POOL_NEXT pool.next
98 : #define POOL_IMPL_STYLE 1
99 : #include "../../util/tmpl/fd_pool.c"
100 :
101 : #define MAP_NAME blockhash_map
102 : #define MAP_KEY blockhash
103 : #define MAP_ELE_T fd_txncache_blockcache_shmem_t
104 : #define MAP_KEY_T fd_hash_t
105 : #define MAP_PREV blockhash_map.prev
106 0 : #define MAP_NEXT blockhash_map.next
107 12772482 : #define MAP_KEY_EQ(k0,k1) fd_hash_eq( k0, k1 )
108 12780651 : #define MAP_KEY_HASH(key,seed) (__extension__({ (void)(seed); fd_ulong_load_8_fast( (key)->uc ); }))
109 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
110 : #define MAP_MULTI 1
111 : #define MAP_IMPL_STYLE 1
112 : #include "../../util/tmpl/fd_map_chain.c"
113 :
114 : #define SLIST_NAME root_slist
115 : #define SLIST_ELE_T fd_txncache_blockcache_shmem_t
116 906 : #define SLIST_IDX_T ulong
117 65261 : #define SLIST_NEXT slist.next
118 : #define SLIST_IMPL_STYLE 1
119 : #include "../../util/tmpl/fd_slist.c"
120 :
121 : #define SET_NAME descends_set
122 : #include "../../util/tmpl/fd_set_dynamic.c"
123 :
124 : struct __attribute__((aligned(FD_TXNCACHE_SHMEM_ALIGN))) fd_txncache_shmem_private {
125 : /* The txncache is a concurrent structure and will be accessed by multiple threads
126 : concurrently. Insertion and querying only take a read lock as they can be done
127 : lockless but all other operations will take a write lock internally.
128 :
129 : The lock needs to be aligned to 128 bytes to avoid false sharing with other
130 : data that might be on the same cache line. */
131 : fd_rwlock_t lock[ 1 ] __attribute__((aligned(128UL)));
132 :
133 : ulong txn_per_slot_max;
134 : ulong active_slots_max;
135 : ulong bucket_cnt; /* Hash buckets per blockcache. Decoupled from txn_per_slot_max (load
136 : factor 8) to reduce the heads arrays' memory footprint. */
137 : ulong txnpages_per_blockhash_max;
138 : ulong max_txnpages;
139 : ulong txnpage_idx_sz; /* Element size of every txnpage index array (blockcache->pages,
140 : txnpages_free, scratch_pages), see fd_txncache_txnpage_idx_sz. */
141 :
142 : uint blockcache_generation; /* Incremented for every blockcache. */
143 : ulong txnpages_free_cnt; /* The number of pages in the txnpages that are not currently in use. */
144 :
145 : /* Helps the snapshot producer walk the txncache lock-free and detect
146 : relevant changes to the txncache. mutation_gen covers transaction
147 : storage, and root_gen covers the root history. mutation_gen is odd
148 : when the storage is being modified in ways that could affect the
149 : snapshot, such as during reset, root advancement, and compaction,
150 : and bumped once the mutation is done. root_gen increments on root
151 : advancement and reset.
152 :
153 : For the snapshot producer, fd_txncache_writer, mutation_gen changes
154 : trigger retry in the writer, and root_gen changes are treated as
155 : fatal invariant violation because the replay tile is expected to
156 : pause root history changes while a snapshot is in progress.
157 :
158 : Note that attach/cancel of the unrooted frontier does not bump
159 : mutation_gen. Suppose an unrooted child executed transaction T
160 : referencing an old rooted blockhash. Before cancellation, T is
161 : unrooted, so the writer skips it. After cancellation, T is stale,
162 : so the writer still skips it. So the desired snapshot did not
163 : change.
164 :
165 : A note on concurrency ... Accesses to the two generation numbers
166 : are race free under C11. Every store after initialization is
167 : atomic and pairs with an atomic load in the snapshot producer tile.
168 : The loads in the write locked mutators need no atomicity because
169 : every store is made under the write lock so said loads are already
170 : ordered properly with respect to the writes. In contrast, the
171 : transaction entries the snapshot walker loads and the txncache
172 : stores are plain on both sides, and the blockcache bucket heads are
173 : stored plainly by compaction while the walker loads them with an
174 : acquire load. Both are data races under C11. The walker is
175 : nevertheless correct, given that the compiler emits the plain entry
176 : accesses as ordinary loads and stores. FD_HW_MFENCE_ST in
177 : fd_txncache_mutation_begin orders the odd store before the entry
178 : stores and FD_HW_MFENCE_LD in the walker orders the entry loads
179 : before the generation re-check, so an entry load that observed a
180 : store made inside a mutation section is followed by a re-check that
181 : fails, and whatever was read, torn or otherwise, is discarded. */
182 : ulong mutation_gen;
183 : ulong root_gen;
184 :
185 : ulong root_cnt;
186 : root_slist_t root_ll[1]; /* A singly linked list of the forks that are roots of fork chains. The tail is the
187 : most recently added root, the head is the oldest root. This is used to identify
188 : which forks can be pruned when a new root is added. */
189 :
190 : ulong seed;
191 : ulong magic; /* ==FD_TXNCACHE_SHMEM_MAGIC */
192 : };
193 :
194 : struct blockcache {
195 : fd_txncache_blockcache_shmem_t * shmem;
196 :
197 : uint * heads; /* The hash table for the blockhash. Each entry is a pointer to the head of a linked list of
198 : transactions that reference this blockhash. As we add transactions to the bucket, the head
199 : pointer is updated to the new item, and the new item is pointed to the previous head. */
200 : void * pages; /* A list of the txnpages containing the transactions for this blockcache, elements of
201 : shmem->txnpage_idx_sz bytes (see fd_txncache_txnpage_idx_ld). */
202 :
203 : descends_set_t * descends; /* Each fork can descend from other forks in the txncache, and this bit vector contains one
204 : value for each fork in the txncache. If this fork descends from some other fork F, then
205 : the bit at index F in descends[] is set. */
206 : };
207 :
208 : typedef struct blockcache blockcache_t;
209 :
210 : struct fd_txncache_private {
211 : fd_txncache_shmem_t * shmem;
212 :
213 : fd_txncache_blockcache_shmem_t * blockcache_shmem_pool;
214 : blockcache_t * blockcache_pool;
215 : blockhash_map_t * blockhash_map;
216 :
217 : void * txnpages_free; /* The index in the txnpages array that is free, for each of the free pages.
218 : Elements are shmem->txnpage_idx_sz bytes, as are scratch_pages below. */
219 :
220 : fd_txncache_txnpage_t * txnpages; /* The actual storage for the transactions. The blockcache points to these
221 : pages when storing transactions. Transaction are grouped into pages of
222 : size 16384 to make certain allocation and deallocation operations faster
223 : (just the pages are acquired/released, rather than each txn). */
224 :
225 : void * scratch_pages;
226 : uint * scratch_heads;
227 : fd_txncache_txnpage_t * scratch_txnpage;
228 : };
229 :
230 : FD_PROTOTYPES_BEGIN
231 :
232 : /* Use these to bracket a write locked change that is visible to the
233 : lock-free snapshot chain walker (fd_txncache_writer). mutation_gen
234 : is odd while a change is in progress. The walker uses an acquire
235 : load of the generation before starting its chain reads and a LoadLoad
236 : barrier before each re-check. */
237 :
238 : static inline void
239 8373 : fd_txncache_mutation_begin( fd_txncache_shmem_t * shmem ) {
240 : /* Plain load is fine because the write lock holder is the only writer. */
241 8373 : ulong gen = shmem->mutation_gen;
242 8373 : FD_TEST_CRIT( !(gen&1UL) );
243 8373 : __atomic_store_n( &shmem->mutation_gen, gen+1UL, __ATOMIC_RELAXED );
244 :
245 : /* The walker does not write/publish any shared state visible to the
246 : txncache. So no need for a StoreLoad barrier here. Just
247 : StoreStore. */
248 8373 : FD_HW_MFENCE_ST();
249 8373 : }
250 :
251 : static inline void
252 8373 : fd_txncache_mutation_end( fd_txncache_shmem_t * shmem ) {
253 : /* Plain load is fine because the write lock holder is the only writer. */
254 8373 : ulong gen = shmem->mutation_gen;
255 8373 : FD_TEST_CRIT( gen&1UL );
256 8373 : __atomic_store_n( &shmem->mutation_gen, gen+1UL, __ATOMIC_RELEASE );
257 8373 : }
258 :
259 : /* fd_txncache_max_txnpages{,_per_blockhash} return the txnpage pool
260 : size and the per blockcache page cap for the given parameters. The
261 : result is not bounded; callers compare against
262 : FD_TXNCACHE_MAX_TXNPAGES. */
263 :
264 : FD_FN_CONST ulong
265 : fd_txncache_max_txnpages_per_blockhash( ulong max_active_slots,
266 : ulong max_txn_per_slot );
267 :
268 : FD_FN_CONST ulong
269 : fd_txncache_max_txnpages( ulong max_active_slots,
270 : ulong max_txn_per_slot );
271 :
272 : FD_FN_CONST static inline ulong
273 372 : fd_txncache_bucket_cnt( ulong max_txn_per_slot ) {
274 372 : return fd_ulong_max( 1UL, (max_txn_per_slot+7UL)/8UL );
275 372 : }
276 :
277 : /* Txnpage indices are stored as ushort, which covers production
278 : parameters, and widen to uint only when the pool exceeds the ushort
279 : range (development.bench sizing), keeping the production footprint
280 : unchanged. The all-ones value of the width is the null index and
281 : all-ones minus one is the allocation-in-progress flag, so memset 0xFF
282 : nulls an array of either width. ld/st access an index array of the
283 : given element size. */
284 :
285 : FD_FN_CONST static inline ulong
286 372 : fd_txncache_txnpage_idx_sz( ulong max_txnpages ) {
287 372 : return max_txnpages>USHORT_MAX-2UL ? sizeof(uint) : sizeof(ushort);
288 372 : }
289 :
290 : static inline ulong
291 : fd_txncache_txnpage_idx_ld( ulong idx_sz,
292 : void const * idx,
293 12778011 : ulong i ) {
294 12778011 : return idx_sz==sizeof(uint) ? (ulong)((uint const *)idx)[ i ] : (ulong)((ushort const *)idx)[ i ];
295 12778011 : }
296 :
297 : static inline void
298 : fd_txncache_txnpage_idx_st( ulong idx_sz,
299 : void * idx,
300 : ulong i,
301 1236999 : ulong val ) {
302 1236999 : if( idx_sz==sizeof(uint) ) ((uint *)idx)[ i ] = (uint)val;
303 1236999 : else ((ushort *)idx)[ i ] = (ushort)val;
304 1236999 : }
305 :
306 : FD_PROTOTYPES_END
307 :
308 : #endif /* HEADER_fd_src_flamenco_runtime_fd_txncache_private_h */
|
