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.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 amortize 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 0 : #define FD_TXNCACHE_TXNS_PER_PAGE (8192UL)
14 : #define FD_TXNCACHE_TXNPAGE_ALIGN (4096UL)
15 :
16 : /* The maximum distance a transaction blockhash reference can be
17 : (inclusive). For example, if no slots were skipped, and the value is
18 : 151, slot 300 is allowed to reference blockhashes from slots
19 : [149, 300). */
20 0 : #define FD_TXNCACHE_MAX_BLOCKHASH_DISTANCE (151UL)
21 :
22 : /* The most roots the txncache holds. root_cnt does not count the
23 : initial root. */
24 : #define FD_TXNCACHE_MAX_ROOTS (FD_TXNCACHE_MAX_BLOCKHASH_DISTANCE+1UL)
25 :
26 : /* The global txn index (page*FD_TXNCACHE_TXNS_PER_PAGE+txn) is a uint
27 : with UINT_MAX as the null link, which bounds the txnpage pool. */
28 :
29 : #define FD_TXNCACHE_MAX_TXNPAGES (UINT_MAX/FD_TXNCACHE_TXNS_PER_PAGE)
30 :
31 : struct __attribute__((packed)) fd_txncache_single_txn {
32 : uint blockcache_next; /* Global txn index of the next element in this blockcache hash chain, or UINT_MAX. */
33 : uint generation; /* The generation of the fork when this transaction was inserted. Used to
34 : determine if the transaction is still valid for a fork that might have
35 : advanced since insertion. */
36 :
37 : fd_txncache_fork_id_t fork_id; /* Fork that the transaction was executed on. A transaction might be in the cache
38 : multiple times if it was executed on multiple forks. */
39 : uchar txnhash[ 20UL ]; /* The transaction message hash, truncated to 20 bytes. The hash is not always the first 20
40 : bytes, but is 20 bytes starting at some arbitrary offset given by the txnhash_offset value
41 : of the containing blockcache entry. */
42 : };
43 : typedef struct fd_txncache_single_txn fd_txncache_single_txn_t;
44 :
45 : FD_STATIC_ASSERT( sizeof(fd_txncache_single_txn_t)==30UL, fd_txncache_single_txn );
46 :
47 : struct __attribute__((aligned(FD_TXNCACHE_TXNPAGE_ALIGN))) fd_txncache_txnpage {
48 : ushort free; /* The number of free txn entries in this page. */
49 : fd_txncache_single_txn_t txns[ FD_TXNCACHE_TXNS_PER_PAGE][ 1 ]; /* The transactions in the page. */
50 : };
51 : typedef struct fd_txncache_txnpage fd_txncache_txnpage_t;
52 :
53 : struct fd_txncache_page_meta {
54 : uint frame; /* UINT_MAX if not resident. */
55 : uint dirty; /* Resident contents changed since the last writeback. */
56 : int disk_valid; /* A complete page has been written to its disk slot. */
57 : uint next; /* Next older txnpage of the owning blockcache, or UINT_MAX. */
58 : uint ref; /* Resident and accessed since the eviction sweep last passed its frame. */
59 : uint io; /* A fetch is loading or writing back the page without the lock. */
60 : };
61 : typedef struct fd_txncache_page_meta fd_txncache_page_meta_t;
62 :
63 : struct fd_txncache_blockcache_shmem {
64 : fd_txncache_fork_id_t parent_id;
65 : fd_txncache_fork_id_t child_id;
66 : fd_txncache_fork_id_t sibling_id;
67 :
68 : int frozen; /* This is used to enforce invariants on the caller of the txncache.
69 : -1: invalid
70 : 0: active
71 : 1: semi frozen, only happens during snapshot load
72 : 2: frozen, should not be modified */
73 :
74 : uint generation;
75 :
76 : fd_hash_t blockhash; /* The blockhash that this entry is for. */
77 : ulong txnhash_offset; /* To save memory, the Agave validator decided to truncate the hash of transactions stored in
78 : this memory to 20 bytes rather than 32 bytes. The bytes used are not the first 20 as you
79 : might expect, but instead the first 20 starting at some random offset into the transaction
80 : hash (starting between 0 and len(hash)-20, a/k/a 44 for signatures, and 12 for hashes).
81 :
82 : In an unfortunate turn, the offset is also propagated to peers via. snapshot responses,
83 : which only communicate the offset and the respective 20 bytes. To make sure we are
84 : deduplicating incoming transactions correctly, we must replicate this system even though
85 : it would be easier to just always take the first 20 bytes. For transactions that we
86 : insert into the cache ourselves, we do just always use a txnhash_offset of zero, so this is
87 : only nonzero when constructed from a peer snapshot. */
88 :
89 : ulong pages_cnt; /* The number of txnpages currently in use to store the transactions in this blockcache. */
90 : uint page_head; /* Newest logical page, or UINT_MAX. Older pages follow page_meta[ page ].next. */
91 :
92 : struct {
93 : ulong next;
94 : } pool;
95 :
96 : struct {
97 : ulong next;
98 : } slist;
99 :
100 : struct {
101 : ulong next;
102 : ulong prev;
103 : } blockhash_map;
104 : };
105 :
106 : typedef struct fd_txncache_blockcache_shmem fd_txncache_blockcache_shmem_t;
107 :
108 : #define POOL_NAME blockcache_pool
109 : #define POOL_T fd_txncache_blockcache_shmem_t
110 : #define POOL_IDX_T ulong
111 0 : #define POOL_NEXT pool.next
112 : #define POOL_IMPL_STYLE 1
113 : #include "../../util/tmpl/fd_pool.c"
114 :
115 : #define MAP_NAME blockhash_map
116 : #define MAP_KEY blockhash
117 : #define MAP_ELE_T fd_txncache_blockcache_shmem_t
118 : #define MAP_KEY_T fd_hash_t
119 : #define MAP_PREV blockhash_map.prev
120 0 : #define MAP_NEXT blockhash_map.next
121 0 : #define MAP_KEY_EQ(k0,k1) fd_hash_eq( k0, k1 )
122 0 : #define MAP_KEY_HASH(key,seed) (__extension__({ (void)(seed); fd_ulong_load_8_fast( (key)->uc ); }))
123 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
124 : #define MAP_MULTI 1
125 : #define MAP_IMPL_STYLE 1
126 : #include "../../util/tmpl/fd_map_chain.c"
127 :
128 : #define SLIST_NAME root_slist
129 : #define SLIST_ELE_T fd_txncache_blockcache_shmem_t
130 0 : #define SLIST_IDX_T ulong
131 0 : #define SLIST_NEXT slist.next
132 : #define SLIST_IMPL_STYLE 1
133 : #include "../../util/tmpl/fd_slist.c"
134 :
135 : #define SET_NAME descends_set
136 : #include "../../util/tmpl/fd_set_dynamic.c"
137 :
138 : struct __attribute__((aligned(FD_TXNCACHE_SHMEM_ALIGN))) fd_txncache_shmem_private {
139 : /* The txncache is a concurrent structure and will be accessed by
140 : multiple threads concurrently. Resident queries and inserts take
141 : a read lock. Structural operations take a write lock. A cache
142 : miss takes the write lock only to reserve a frame and does its
143 : spill I/O without the lock, marking the pages it moves busy (see
144 : page_meta io) until it publishes them. If fetched pages are
145 : evicted before use, it loads under the write lock instead. The
146 : lock prevents eviction while a reader uses a frame.
147 :
148 : The lock needs to be aligned to 128 bytes to avoid false sharing
149 : with other data that might be on the same cache line. */
150 : fd_rwlock_t lock[ 1 ] __attribute__((aligned(128UL)));
151 :
152 : ulong txn_per_slot_max;
153 : ulong active_slots_max;
154 : ulong bucket_cnt; /* Hash buckets per blockcache, txn_per_slot_max/32 (load factor 16, as live forks hold at most txn_per_slot_max/2). */
155 : ulong txnpages_per_blockhash_max;
156 : ulong txnpages_max;
157 : ulong frames_max;
158 :
159 : uint blockcache_generation; /* Incremented for every blockcache. */
160 : ulong txnpages_free_cnt; /* Number of unallocated logical pages. */
161 : ulong frames_free_cnt; /* Free in-memory resident frames. */
162 : ulong evict_next; /* CLOCK hand: next frame the eviction sweep checks. */
163 : ulong release_seq; /* Incremented whenever a logical page is released, under the write lock. */
164 : fd_rwlock_t alloc_lock[ 1 ]; /* Lock for allocating new logical page + frame. */
165 :
166 : /* Metrics. page_miss_cnt, lock_read_wait_ticks and the spill
167 : counters are updated atomically, the rest under the write lock. */
168 : ulong page_miss_cnt; /* Read-locked lookups that found their page not resident. */
169 : ulong page_spilled_cnt; /* Dirty pages written to the spill file. */
170 : ulong page_spill_read_cnt; /* Pages read back from the spill file. */
171 : ulong frame_evicted_cnt; /* Frames evicted to load another page. */
172 : ulong spill_ticks; /* Ticks spent in spill file I/O. */
173 : ulong lock_read_wait_ticks; /* Ticks spent waiting to take the read lock. */
174 : ulong lock_write_wait_ticks; /* Ticks spent waiting to take the write lock. */
175 :
176 : ulong root_cnt;
177 : root_slist_t root_ll[1]; /* A singly linked list of the forks that are roots of fork chains. The tail is the
178 : most recently added root, the head is the oldest root. This is used to identify
179 : which forks can be pruned when a new root is added. */
180 :
181 : ulong seed;
182 : ulong magic; /* ==FD_TXNCACHE_SHMEM_MAGIC */
183 : };
184 :
185 : struct blockcache {
186 : fd_txncache_blockcache_shmem_t * shmem;
187 :
188 : uint * heads; /* The hash table for the blockhash. Each entry is the global txn index of the head of a linked list of
189 : transactions that reference this blockhash. As we add transactions to the bucket, the head
190 : pointer is updated to the new item, and the new item is pointed to the previous head. */
191 :
192 : descends_set_t * descends; /* Each fork can descend from other forks in the txncache, and this bit vector contains one
193 : value for each fork in the txncache. If this fork descends from some other fork F, then
194 : the bit at index F in descends[] is set. */
195 : };
196 :
197 : typedef struct blockcache blockcache_t;
198 :
199 : struct fd_txncache_private {
200 : fd_txncache_shmem_t * shmem;
201 :
202 : fd_txncache_blockcache_shmem_t * blockcache_shmem_pool;
203 : blockcache_t * blockcache_pool;
204 : blockhash_map_t * blockhash_map;
205 :
206 : int spill_fd;
207 :
208 : fd_txncache_page_meta_t * page_meta; /* Metadata for each logical page */
209 : uint * txnpages_free; /* Stack of free logical pages */
210 : uint * frame_page; /* Array mapping frame to logical page */
211 : uint * frames_free; /* Stack of unused frame indices. */
212 :
213 : fd_txncache_txnpage_t * txnpages; /* Aligned resident frames, indexed through page_meta. */
214 :
215 : /* Scratch space used for cleaning up stale entries for compaction. */
216 : uint * scratch_heads;
217 : fd_txncache_txnpage_t * scratch_txnpage;
218 : fd_txncache_txnpage_t * scratch_input;
219 :
220 : fd_txncache_join_metrics_t metrics[1];
221 : };
222 :
223 : FD_PROTOTYPES_BEGIN
224 :
225 : /* fd_txncache_max_txnpages{,_per_blockhash} return the txnpage pool
226 : size and the per blockcache page cap for the given parameters. The
227 : result is not bounded; callers compare against
228 : FD_TXNCACHE_MAX_TXNPAGES. */
229 :
230 : FD_FN_CONST ulong
231 : fd_txncache_max_txnpages_per_blockhash( ulong max_active_slots,
232 : ulong max_txn_per_slot );
233 :
234 : FD_FN_CONST ulong
235 : fd_txncache_max_txnpages( ulong max_active_slots,
236 : ulong max_txn_per_slot );
237 :
238 : FD_FN_CONST static inline ulong
239 0 : fd_txncache_bucket_cnt( ulong max_txn_per_slot ) {
240 0 : return fd_ulong_max( 1UL, (max_txn_per_slot+31UL)/32UL );
241 0 : }
242 :
243 : /* Snapshot support. These let the snapshot writer read the rooted part
244 : of the txncache without knowing its locking or paging. */
245 :
246 : struct fd_txncache_root {
247 : ulong blockcache_idx;
248 : ulong txnhash_offset;
249 : uint generation;
250 : uchar blockhash[ 32UL ];
251 : };
252 :
253 : typedef struct fd_txncache_root fd_txncache_root_t;
254 :
255 : /* fd_txncache_snapshot_roots copies every root, oldest first, to out
256 : and returns the count. out must have room for
257 : FD_TXNCACHE_MAX_ROOTS roots. The caller must keep the
258 : root from advancing, so the newest root is the snapshot root. */
259 :
260 : ulong
261 : fd_txncache_snapshot_roots( fd_txncache_t * tc,
262 : fd_txncache_root_t * out );
263 :
264 : /* fd_txncache_blockcache_iter_t iterates the transactions of a
265 : blockcache. It visits one hash chain at a time and holds the
266 : txncache lock for that chain, so the chain cannot be compacted,
267 : freed, or evicted underneath it. Concurrent inserts only prepend to
268 : a chain, so the entries reachable from the head loaded when the chain
269 : is opened do not change while it is held. The lock is released
270 : between chains.
271 :
272 : For each chain, the iterator holds the read lock once every page of
273 : the chain is resident, fetching missing pages without the lock.
274 : After min(pages, frames) fetches it holds the write lock instead,
275 : under which it loads pages on demand.
276 :
277 : fd_txncache_blockcache_iter_init locks tc and positions iter at the
278 : first transaction of blockcache blockcache_idx. Returns iter. init
279 : must be paired with fd_txncache_blockcache_iter_fini. The caller
280 : must not call into the txncache between init and fini.
281 :
282 : fd_txncache_blockcache_iter_ele returns the current transaction,
283 : valid until the next call to fd_txncache_blockcache_iter_next or
284 : fd_txncache_blockcache_iter_fini.
285 :
286 : Typical usage:
287 :
288 : fd_txncache_blockcache_iter_t iter[1];
289 : for( fd_txncache_blockcache_iter_init( iter, tc, blockcache_idx );
290 : !fd_txncache_blockcache_iter_done( iter );
291 : fd_txncache_blockcache_iter_next( iter ) ) {
292 : fd_txncache_single_txn_t const * txn = fd_txncache_blockcache_iter_ele( iter );
293 : ...
294 : }
295 : fd_txncache_blockcache_iter_fini( iter ); */
296 :
297 : struct fd_txncache_blockcache_iter {
298 : fd_txncache_t * tc;
299 : fd_txncache_single_txn_t const * txn; /* NULL once done */
300 : ulong blockcache_idx;
301 : ulong bucket;
302 : int write_lock;
303 : };
304 :
305 : typedef struct fd_txncache_blockcache_iter fd_txncache_blockcache_iter_t;
306 :
307 : fd_txncache_blockcache_iter_t *
308 : fd_txncache_blockcache_iter_init( fd_txncache_blockcache_iter_t * iter,
309 : fd_txncache_t * tc,
310 : ulong blockcache_idx );
311 :
312 : void
313 : fd_txncache_blockcache_iter_next( fd_txncache_blockcache_iter_t * iter );
314 :
315 : void
316 : fd_txncache_blockcache_iter_fini( fd_txncache_blockcache_iter_t * iter );
317 :
318 : FD_FN_PURE static inline int
319 0 : fd_txncache_blockcache_iter_done( fd_txncache_blockcache_iter_t const * iter ) {
320 0 : return !iter->txn;
321 0 : }
322 :
323 : FD_FN_PURE static inline fd_txncache_single_txn_t const *
324 0 : fd_txncache_blockcache_iter_ele( fd_txncache_blockcache_iter_t const * iter ) {
325 0 : return iter->txn;
326 0 : }
327 :
328 : FD_PROTOTYPES_END
329 :
330 : #endif /* HEADER_fd_src_flamenco_runtime_fd_txncache_private_h */
|
