Line data Source code
1 : #include "fd_txncache.h"
2 : #include "../fd_rwlock.h"
3 :
4 : #define SORT_NAME sort_slot_ascend
5 : #define SORT_KEY_T ulong
6 : #define SORT_BEFORE(a,b) (a)<(b)
7 : #include "../../util/tmpl/fd_sort.c"
8 :
9 : /* TODO: This data structure needs a careful audit and testing. It may need
10 : to be reworked to support better fork-aware behavior. */
11 :
12 : /* The number of transactions in each page. This needs to be high
13 : enough to amoritze the cost of caller code reserving pages from,
14 : and returning pages to the pool, but not so high that the memory
15 : wasted from blockhashes with only one transaction is significant. */
16 :
17 0 : #define FD_TXNCACHE_TXNS_PER_PAGE (16384UL)
18 :
19 : /* The number of unique entries in the hash lookup table for each
20 : blockhash. A higher value here uses more memory but enables faster
21 : lookups. */
22 :
23 0 : #define FD_TXNCACHE_BLOCKCACHE_MAP_CNT (524288UL)
24 :
25 : /* The number of unique entries in the hash lookup table for each
26 : (slot, blockhash). This prevents all the entries needing to be in
27 : one slotcache list, so insertions can happen concurrently. */
28 :
29 0 : #define FD_TXNCACHE_SLOTCACHE_MAP_CNT (1024UL)
30 :
31 : /* Value for an empty blockcache `max_slot` or empty slotcache
32 : `slot` entry. When the entries are set to this value, we can insert
33 : to the entry, but stop iterating while running queries. */
34 :
35 0 : #define FD_TXNCACHE_EMPTY_ENTRY (ULONG_MAX)
36 :
37 : /* Value for a deleted cache entry. We can insert to such entries,
38 : and keep iterating while running queries. */
39 :
40 0 : #define FD_TXNCACHE_TOMBSTONE_ENTRY (ULONG_MAX-1UL)
41 :
42 : /* Placeholder value used for critical sections. */
43 :
44 : #define FD_TXNCACHE_TEMP_ENTRY (ULONG_MAX-2UL)
45 :
46 : struct fd_txncache_private_txn {
47 : uint blockcache_next; /* Pointer to the next element in the blockcache hash chain containing this entry from the pool. */
48 : uint slotblockcache_next; /* Pointer to the next element in the slotcache hash chain containing this entry from the pool. */
49 :
50 : ulong slot; /* Slot that the transaction was executed. A transaction might be in the cache
51 : multiple times if it was executed in a different slot on different forks. The
52 : same slot will not appear multiple times however. */
53 : uchar txnhash[ 20 ]; /* The transaction hash, truncated to 20 bytes. The hash is not always the first 20
54 : bytes, but is 20 bytes starting at some arbitrary offset given by the key_offset value
55 : of the containing by_blockhash entry. */
56 : uchar result; /* The result of executing the transaction. This is the discriminant of the transaction
57 : result type. 0 means success. */
58 : };
59 :
60 : typedef struct fd_txncache_private_txn fd_txncache_private_txn_t;
61 :
62 : struct fd_txncache_private_txnpage {
63 : ushort free; /* The number of free txn entries in this page. */
64 : fd_txncache_private_txn_t txns[ FD_TXNCACHE_TXNS_PER_PAGE][ 1 ]; /* The transactions in the page. */
65 : };
66 :
67 : typedef struct fd_txncache_private_txnpage fd_txncache_private_txnpage_t;
68 :
69 : struct fd_txncache_private_blockcache {
70 : uchar blockhash[ 32 ]; /* The actual blockhash of these transactions. */
71 : ulong max_slot; /* The max slot we have seen that contains a transaction referencing this blockhash.
72 : The blockhash entry will not be purged until the lowest rooted slot is greater than this. */
73 : ulong txnhash_offset; /* To save memory, the Agave validator decided to truncate the hash of transactions stored in
74 : this memory to 20 bytes rather than 32 bytes. The bytes used are not the first 20 as you
75 : might expect, but instead the first 20 starting at some random offset into the transaction
76 : hash (starting between 0 and len(hash)-20, a/k/a 44 for signatures, and 12 for hashes).
77 :
78 : In an unfortunate turn, the offset is also propogated to peers via. snapshot responses,
79 : which only communicate the offset and the respective 20 bytes. To make sure we are
80 : deduplicating incoming transactions correctly, we must replicate this system even though
81 : it would be easier to just always take the first 20 bytes. For transactions that we
82 : insert into the cache ourselves, we do just always use a key_offset of zero, so this is
83 : only nonzero when constructed form a peer snapshot. */
84 :
85 : uint heads[ FD_TXNCACHE_BLOCKCACHE_MAP_CNT ]; /* The hash table for the blockhash. Each entry is a pointer to the head of a
86 : linked list of transactions that reference this blockhash. As we add
87 : transactions to the bucket, the head pointer is updated to the new item, and
88 : the new item is pointed to the previous head. */
89 :
90 : ushort pages_cnt; /* The number of txnpages currently in use to store the transactions in this blockcache. */
91 : uint * pages; /* A list of the txnpages containing the transactions for this blockcache. */
92 : };
93 :
94 : typedef struct fd_txncache_private_blockcache fd_txncache_private_blockcache_t;
95 :
96 : struct fd_txncache_private_slotblockcache {
97 : uchar blockhash[ 32 ]; /* The actual blockhash of these transactions. */
98 : ulong txnhash_offset; /* As described above. */
99 : uint heads[ FD_TXNCACHE_SLOTCACHE_MAP_CNT ]; /* A map of the head of a linked list of tansactions in this slot and blockhash */
100 : };
101 :
102 : typedef struct fd_txncache_private_slotblockcache fd_txncache_private_slotblockcache_t;
103 :
104 : struct fd_txncache_private_slotcache {
105 : ulong slot; /* The slot that this slotcache is for. */
106 : fd_txncache_private_slotblockcache_t blockcache[ 300UL ];
107 : };
108 :
109 : typedef struct fd_txncache_private_slotcache fd_txncache_private_slotcache_t;
110 :
111 : struct __attribute__((aligned(FD_TXNCACHE_ALIGN))) fd_txncache_private {
112 : fd_rwlock_t lock[ 1 ]; /* The txncache is a concurrent structure and will be accessed by multiple threads
113 : concurrently. Insertion and querying only take a read lock as they can be done
114 : lockless but all other operations will take a write lock internally. */
115 :
116 : ulong root_slots_max;
117 : ulong live_slots_max;
118 : ulong constipated_slots_max; /* The max number of constipated slots that the txncache will support
119 : while in a constipated mode. If this gets exceeded, this means
120 : that the txncache was in a constipated state for too long without
121 : being flushed. */
122 : ushort txnpages_per_blockhash_max;
123 : uint txnpages_max;
124 :
125 : ulong root_slots_cnt; /* The number of root slots being tracked in the below array. */
126 : ulong root_slots_off; /* The highest N slots that have been rooted. These slots are
127 : used to determine which transactions should be kept around to
128 : be queried and served to snapshot requests. The actual
129 : footprint for this data (and other data below) are declared
130 : immediately following the struct. I.e. these pointers point to
131 : memory not far after the struct. */
132 :
133 : ulong blockcache_off; /* The actual cache of transactions. This is a linear probed hash
134 : table that maps blockhashes to the transactions that reference them.
135 : The depth of the hash table is live_slots_max, since this is the
136 : maximum number of blockhashes that can be alive. The loading factor
137 : if they were all alive would be 1.0, but this is rare because we
138 : will almost never fork repeatedly to hit this limit. These
139 : blockcaches are just pointers to pages from the txnpages below, so
140 : they don't take up much memory. */
141 :
142 : ulong slotcache_off; /* The cache of transactions by slot instead of by blockhash, so we
143 : can quickly serialize the slot deltas for the root slots which are
144 : served to peers in snapshots. Similar to the above, it uses the
145 : same underlying transaction storage, but different lookup tables. */
146 :
147 : uint txnpages_free_cnt; /* The number of pages in the txnpages that are not currently in use. */
148 : ulong txnpages_free_off; /* The index in the txnpages array that is free, for each of the free pages. */
149 :
150 : ulong txnpages_off; /* The actual storage for the transactions. The blockcache points to these
151 : pages when storing transactions. Transaction are grouped into pages of
152 : size 16384 to make certain allocation and deallocation operations faster
153 : (just the pages are acquired/released, rather than each txn). */
154 :
155 : ulong blockcache_pages_off; /* The pages for the blockcache entries. */
156 :
157 : ulong probed_entries_off; /* The map of index to number of entries which oveflowed over this index.
158 : Overflow for index i is defined as every entry j > i where j should have
159 : been inserted at k < i. */
160 :
161 : ulong constipated_slots_cnt; /* The number of constipated root slots that can be supported and
162 : that are tracked in the below array. */
163 : ulong constipated_slots_off; /* The highest N slots that should be rooted will be in this
164 : array, assuming that the latest slots were constipated
165 : and not flushed. */
166 :
167 : /* Constipation is used here in the same way Funk is constipated. The reason
168 : this exists is to ensure that the set of rooted slots doesn't change while
169 : the snapshot service is serializing the status cache into a snapshot. This
170 : operation is usually very fast and only takes a few seconds.
171 : TODO: Another implementation of this might be to continue rooting slots
172 : to the same data structure but to temporarily stop evictions. Right now
173 : this is implemented such that we maintain a seperate array of all slots
174 : that should be rooted. Once the constipation is removed, all of the
175 : constipated slots will be registered en masse. */
176 : int is_constipated; /* Is the status cache in a constipated state.*/
177 : ulong is_constipated_off;
178 :
179 : ulong magic; /* ==FD_TXNCACHE_MAGIC */
180 : };
181 :
182 : FD_FN_PURE static ulong *
183 0 : fd_txncache_get_root_slots( fd_txncache_t * tc ) {
184 0 : return (ulong *)( (uchar *)tc + tc->root_slots_off );
185 0 : }
186 :
187 : FD_FN_PURE static ulong *
188 0 : fd_txncache_get_constipated_slots( fd_txncache_t * tc ) {
189 0 : return (ulong *)( (uchar *)tc + tc->constipated_slots_off );
190 0 : }
191 :
192 : FD_FN_PURE static fd_txncache_private_blockcache_t *
193 0 : fd_txncache_get_blockcache( fd_txncache_t * tc ) {
194 0 : return (fd_txncache_private_blockcache_t *)( (uchar *)tc + tc->blockcache_off );
195 0 : }
196 :
197 : FD_FN_PURE static fd_txncache_private_blockcache_t *
198 0 : fd_txncache_get_blockcache_const( fd_txncache_t const * tc ) {
199 0 : return (fd_txncache_private_blockcache_t *)( (uchar const *)tc + tc->blockcache_off );
200 0 : }
201 :
202 : FD_FN_PURE static fd_txncache_private_slotcache_t *
203 0 : fd_txncache_get_slotcache( fd_txncache_t * tc ) {
204 0 : return (fd_txncache_private_slotcache_t *)( (uchar *)tc + tc->slotcache_off );
205 0 : }
206 :
207 : FD_FN_PURE static fd_txncache_private_slotcache_t *
208 0 : fd_txncache_get_slotcache_const( fd_txncache_t const * tc ) {
209 0 : return (fd_txncache_private_slotcache_t *)( (uchar const *)tc + tc->slotcache_off );
210 0 : }
211 :
212 : FD_FN_PURE static uint *
213 0 : fd_txncache_get_txnpages_free( fd_txncache_t * tc ) {
214 0 : return (uint *)( (uchar *)tc + tc->txnpages_free_off );
215 0 : }
216 :
217 : FD_FN_PURE static fd_txncache_private_txnpage_t *
218 0 : fd_txncache_get_txnpages( fd_txncache_t * tc ) {
219 0 : return (fd_txncache_private_txnpage_t *)( (uchar *)tc + tc->txnpages_off );
220 0 : }
221 :
222 : FD_FN_PURE static ulong *
223 0 : fd_txncache_get_probed_entries( fd_txncache_t * tc ) {
224 0 : return (ulong *)( (uchar *)tc + tc->probed_entries_off );
225 0 : }
226 :
227 : FD_FN_PURE static ulong *
228 0 : fd_txncache_get_probed_entries_const( fd_txncache_t const * tc ) {
229 0 : return (ulong *)( (uchar const *)tc + tc->probed_entries_off );
230 0 : }
231 :
232 : FD_FN_CONST static ushort
233 0 : fd_txncache_max_txnpages_per_blockhash( ulong max_txn_per_slot ) {
234 : /* The maximum number of transaction pages we might need to store all
235 : the transactions that could be seen in a blockhash.
236 :
237 : In the worst case, every transaction in every slot refers to
238 : the same blockhash for as long as it is possible (150 slots
239 : following the slot where the blockhash is produced). So there
240 : could be up to
241 :
242 : 524,288 * 150 = 78,643,200
243 :
244 : Note that the blockcaches store txns for forks, and the same txn
245 : might appear multiple times in one block, but if there's a fork,
246 : the fork has to have skipped slots (had 0 txns in them), so it
247 : cannot cause this limit to go higher.
248 :
249 : Transactions referenced by a particular blockhash.
250 : Transactions are stored in pages of 16,384, so we might need up
251 : to 4,800 of these pages to store all the transactions in a
252 : slot. */
253 :
254 0 : ulong result = 1UL+(max_txn_per_slot*150UL-1UL)/FD_TXNCACHE_TXNS_PER_PAGE;
255 0 : if( FD_UNLIKELY( result>USHORT_MAX ) ) return 0;
256 0 : return (ushort)result;
257 0 : }
258 :
259 : FD_FN_CONST static uint
260 : fd_txncache_max_txnpages( ulong max_live_slots,
261 0 : ulong max_txn_per_slot ) {
262 : /* We need to be able to store potentially every slot that is live
263 : being completely full of transactions. This would be
264 :
265 : max_live_slots*max_txn_per_slot
266 :
267 : transactions, except that we are counting pages here, not
268 : transactions. It's not enough to divide by the page size, because
269 : pages might be wasted. The maximum page wastage occurs when all
270 : the blockhashes except one have one transaction in them, and the
271 : remaining blockhash has all other transactions. In that case, the
272 : full blockhash needs
273 :
274 : (max_live_slots*max_txn_per_slot)/FD_TXNCACHE_TXNS_PER_PAGE
275 :
276 : pages, and the other blockhashes need 1 page each. */
277 :
278 0 : ulong result = max_live_slots-1UL+max_live_slots*(1UL+(max_txn_per_slot-1UL)/FD_TXNCACHE_TXNS_PER_PAGE);
279 0 : if( FD_UNLIKELY( result>UINT_MAX ) ) return 0;
280 0 : return (uint)result;
281 0 : }
282 :
283 : FD_FN_CONST ulong
284 0 : fd_txncache_align( void ) {
285 0 : return FD_TXNCACHE_ALIGN;
286 0 : }
287 :
288 : FD_FN_CONST ulong
289 : fd_txncache_footprint( ulong max_rooted_slots,
290 : ulong max_live_slots,
291 : ulong max_txn_per_slot,
292 0 : ulong max_constipated_slots ) {
293 0 : if( FD_UNLIKELY( max_rooted_slots<1UL || max_live_slots<1UL ) ) return 0UL;
294 0 : if( FD_UNLIKELY( max_live_slots<max_rooted_slots ) ) return 0UL;
295 0 : if( FD_UNLIKELY( max_txn_per_slot<1UL ) ) return 0UL;
296 0 : if( FD_UNLIKELY( !fd_ulong_is_pow2( max_live_slots ) || !fd_ulong_is_pow2( max_txn_per_slot ) ) ) return 0UL;
297 :
298 : /* To save memory, txnpages are referenced as uint which is enough
299 : to support mainnet parameters without overflow. */
300 0 : uint max_txnpages = fd_txncache_max_txnpages( max_live_slots, max_txn_per_slot );
301 0 : if( FD_UNLIKELY( !max_txnpages ) ) return 0UL;
302 :
303 0 : ulong max_txnpages_per_blockhash = fd_txncache_max_txnpages_per_blockhash( max_txn_per_slot );
304 0 : if( FD_UNLIKELY( !max_txnpages_per_blockhash ) ) return 0UL;
305 :
306 0 : ulong l;
307 0 : l = FD_LAYOUT_INIT;
308 0 : l = FD_LAYOUT_APPEND( l, FD_TXNCACHE_ALIGN, sizeof(fd_txncache_t) );
309 0 : l = FD_LAYOUT_APPEND( l, alignof(ulong), max_rooted_slots*sizeof(ulong) ); /* root_slots */
310 0 : l = FD_LAYOUT_APPEND( l, alignof(fd_txncache_private_blockcache_t), max_live_slots*sizeof(fd_txncache_private_blockcache_t) ); /* blockcache */
311 0 : l = FD_LAYOUT_APPEND( l, alignof(uint), max_live_slots*max_txnpages_per_blockhash*sizeof(uint) ); /* blockcache->pages */
312 0 : l = FD_LAYOUT_APPEND( l, alignof(fd_txncache_private_slotcache_t), max_live_slots*sizeof(fd_txncache_private_slotcache_t ) ); /* slotcache */
313 0 : l = FD_LAYOUT_APPEND( l, alignof(uint), max_txnpages*sizeof(uint) ); /* txnpages_free */
314 0 : l = FD_LAYOUT_APPEND( l, alignof(fd_txncache_private_txnpage_t), max_txnpages*sizeof(fd_txncache_private_txnpage_t) ); /* txnpages */
315 0 : l = FD_LAYOUT_APPEND( l, alignof(ulong), max_live_slots*sizeof(ulong) ); /* probed entries */
316 0 : l = FD_LAYOUT_APPEND( l, alignof(ulong), max_constipated_slots*sizeof(ulong) ); /* constipated slots */
317 0 : return FD_LAYOUT_FINI( l, FD_TXNCACHE_ALIGN );
318 0 : }
319 :
320 : void *
321 : fd_txncache_new( void * shmem,
322 : ulong max_rooted_slots,
323 : ulong max_live_slots,
324 : ulong max_txn_per_slot,
325 0 : ulong max_constipated_slots ) {
326 0 : fd_txncache_t * tc = (fd_txncache_t *)shmem;
327 :
328 0 : if( FD_UNLIKELY( !shmem ) ) {
329 0 : FD_LOG_WARNING(( "NULL shmem" ));
330 0 : return NULL;
331 0 : }
332 :
333 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_txncache_align() ) ) ) {
334 0 : FD_LOG_WARNING(( "misaligned shmem" ));
335 0 : return NULL;
336 0 : }
337 :
338 0 : if( FD_UNLIKELY( !max_rooted_slots ) ) return NULL;
339 0 : if( FD_UNLIKELY( !max_live_slots ) ) return NULL;
340 0 : if( FD_UNLIKELY( max_live_slots<max_rooted_slots ) ) return NULL;
341 0 : if( FD_UNLIKELY( !max_txn_per_slot ) ) return NULL;
342 0 : if( FD_UNLIKELY( !fd_ulong_is_pow2( max_live_slots ) || !fd_ulong_is_pow2( max_txn_per_slot ) ) ) return NULL;
343 :
344 0 : uint max_txnpages = fd_txncache_max_txnpages( max_live_slots, max_txn_per_slot );
345 0 : ushort max_txnpages_per_blockhash = fd_txncache_max_txnpages_per_blockhash( max_txn_per_slot );
346 :
347 0 : if( FD_UNLIKELY( !max_txnpages ) ) return NULL;
348 0 : if( FD_UNLIKELY( !max_txnpages_per_blockhash ) ) return NULL;
349 :
350 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
351 0 : fd_txncache_t * txncache = FD_SCRATCH_ALLOC_APPEND( l, FD_TXNCACHE_ALIGN, sizeof(fd_txncache_t) );
352 0 : void * _root_slots = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_rooted_slots*sizeof(ulong) );
353 0 : void * _blockcache = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_txncache_private_blockcache_t), max_live_slots*sizeof(fd_txncache_private_blockcache_t) );
354 0 : void * _blockcache_pages = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint), max_live_slots*max_txnpages_per_blockhash*sizeof(uint) );
355 0 : void * _slotcache = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_txncache_private_slotcache_t), max_live_slots*sizeof(fd_txncache_private_slotcache_t ) );
356 0 : void * _txnpages_free = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint), max_txnpages*sizeof(uint) );
357 0 : void * _txnpages = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_txncache_private_txnpage_t), max_txnpages*sizeof(fd_txncache_private_txnpage_t) );
358 0 : void * _probed_entries = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_live_slots*sizeof(ulong) );
359 0 : void * _constipated_slots = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_constipated_slots*sizeof(ulong) );
360 :
361 : /* We calculate and store the offsets for these allocations. */
362 0 : txncache->root_slots_off = (ulong)_root_slots - (ulong)txncache;
363 0 : txncache->blockcache_off = (ulong)_blockcache - (ulong)txncache;
364 0 : txncache->slotcache_off = (ulong)_slotcache - (ulong)txncache;
365 0 : txncache->txnpages_free_off = (ulong)_txnpages_free - (ulong)txncache;
366 0 : txncache->txnpages_off = (ulong)_txnpages - (ulong)txncache;
367 0 : txncache->blockcache_pages_off = (ulong)_blockcache_pages - (ulong)txncache;
368 0 : txncache->probed_entries_off = (ulong)_probed_entries - (ulong)txncache;
369 0 : txncache->constipated_slots_off = (ulong)_constipated_slots - (ulong)txncache;
370 :
371 0 : tc->lock->value = 0;
372 0 : tc->root_slots_cnt = 0UL;
373 0 : tc->constipated_slots_cnt = 0UL;
374 :
375 0 : tc->root_slots_max = max_rooted_slots;
376 0 : tc->live_slots_max = max_live_slots;
377 0 : tc->constipated_slots_max = max_constipated_slots;
378 0 : tc->txnpages_per_blockhash_max = max_txnpages_per_blockhash;
379 0 : tc->txnpages_max = max_txnpages;
380 :
381 0 : ulong * root_slots = (ulong *)_root_slots;
382 0 : memset( root_slots, 0xFF, max_rooted_slots*sizeof(ulong) );
383 :
384 0 : ulong * constipated_slots = (ulong *)_constipated_slots;
385 0 : memset( constipated_slots, 0xFF, max_constipated_slots*sizeof(ulong) );
386 :
387 0 : fd_txncache_private_blockcache_t * blockcache = (fd_txncache_private_blockcache_t *)_blockcache;
388 0 : fd_txncache_private_slotcache_t * slotcache = (fd_txncache_private_slotcache_t *)_slotcache;
389 0 : ulong * probed_entries = (ulong *)_probed_entries;
390 0 : for( ulong i=0UL; i<max_live_slots; i++ ) {
391 0 : blockcache[ i ].max_slot = FD_TXNCACHE_EMPTY_ENTRY;
392 0 : slotcache[ i ].slot = FD_TXNCACHE_EMPTY_ENTRY;
393 0 : probed_entries[ i ] = 0UL;
394 0 : }
395 :
396 0 : tc->txnpages_free_cnt = max_txnpages;
397 0 : uint * txnpages_free = _txnpages_free;
398 0 : for( uint i=0; i<max_txnpages; i++ ) txnpages_free[ i ] = i;
399 :
400 0 : FD_COMPILER_MFENCE();
401 0 : FD_VOLATILE( tc->magic ) = FD_TXNCACHE_MAGIC;
402 0 : FD_COMPILER_MFENCE();
403 :
404 0 : return (void *)tc;
405 0 : }
406 :
407 : fd_txncache_t *
408 0 : fd_txncache_join( void * shtc ) {
409 0 : if( FD_UNLIKELY( !shtc ) ) {
410 0 : FD_LOG_WARNING(( "NULL shtc" ));
411 0 : return NULL;
412 0 : }
413 :
414 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtc, fd_txncache_align() ) ) ) {
415 0 : FD_LOG_WARNING(( "misaligned shtc" ));
416 0 : return NULL;
417 0 : }
418 :
419 0 : fd_txncache_t * tc = (fd_txncache_t *)shtc;
420 :
421 0 : if( FD_UNLIKELY( tc->magic!=FD_TXNCACHE_MAGIC ) ) {
422 0 : FD_LOG_WARNING(( "bad magic" ));
423 0 : return NULL;
424 0 : }
425 :
426 0 : uchar * base = (uchar *)tc;
427 0 : fd_txncache_private_blockcache_t * blockcache = (fd_txncache_private_blockcache_t *)( base + tc->blockcache_off );
428 :
429 0 : void * _blockcache_pages = base + tc->blockcache_pages_off;
430 0 : for( ulong i=0UL; i<tc->live_slots_max; i++ ) {
431 0 : blockcache[ i ].pages = (uint *)_blockcache_pages + i*tc->txnpages_per_blockhash_max;
432 0 : }
433 0 : return tc;
434 0 : }
435 :
436 : void *
437 0 : fd_txncache_leave( fd_txncache_t * tc ) {
438 0 : if( FD_UNLIKELY( !tc ) ) {
439 0 : FD_LOG_WARNING(( "NULL tc" ));
440 0 : return NULL; }
441 :
442 0 : return (void *)tc;
443 0 : }
444 :
445 : void *
446 0 : fd_txncache_delete( void * shtc ) {
447 0 : if( FD_UNLIKELY( !shtc ) ) {
448 0 : FD_LOG_WARNING(( "NULL shtc" ));
449 0 : return NULL;
450 0 : }
451 :
452 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtc, fd_txncache_align() ) ) ) {
453 0 : FD_LOG_WARNING(( "misaligned shtc" ));
454 0 : return NULL;
455 0 : }
456 :
457 0 : fd_txncache_t * tc = (fd_txncache_t *)shtc;
458 :
459 0 : if( FD_UNLIKELY( tc->magic!=FD_TXNCACHE_MAGIC ) ) {
460 0 : FD_LOG_WARNING(( "bad magic" ));
461 0 : return NULL;
462 0 : }
463 :
464 0 : FD_COMPILER_MFENCE();
465 0 : FD_VOLATILE( tc->magic ) = 0UL;
466 0 : FD_COMPILER_MFENCE();
467 :
468 0 : return (void *)tc;
469 0 : }
470 :
471 : static void
472 : fd_txncache_remove_blockcache_idx( fd_txncache_t * tc,
473 0 : ulong idx ) {
474 0 : fd_txncache_private_blockcache_t * blockcache = fd_txncache_get_blockcache( tc );
475 0 : ulong * probed_entries = fd_txncache_get_probed_entries( tc );
476 0 : uint * txnpages_free = fd_txncache_get_txnpages_free( tc );
477 :
478 : /* Check if removing this element caused there to be no overflow for a hash index. */
479 0 : ulong hash_idx = FD_LOAD( ulong, blockcache[ idx ].blockhash )%tc->live_slots_max;
480 :
481 0 : ulong j = hash_idx;
482 0 : while( j != idx ) {
483 0 : probed_entries[ j ]--;
484 : /* If there is no overflow and the slot is a tombstone, mark it as free. */
485 0 : if( probed_entries[ j ] == 0 && blockcache[ j ].max_slot == FD_TXNCACHE_TOMBSTONE_ENTRY ) {
486 0 : blockcache[ j ].max_slot = FD_TXNCACHE_EMPTY_ENTRY;
487 0 : }
488 0 : j = (j+1)%tc->live_slots_max;
489 0 : }
490 :
491 : /* Remove from block cache. */
492 0 : blockcache[ idx ].max_slot = (probed_entries[ idx ] == 0 ? FD_TXNCACHE_EMPTY_ENTRY : FD_TXNCACHE_TOMBSTONE_ENTRY);
493 :
494 : /* Free pages. */
495 0 : memcpy( txnpages_free+tc->txnpages_free_cnt, blockcache[ idx ].pages, blockcache[ idx ].pages_cnt*sizeof(uint) );
496 0 : tc->txnpages_free_cnt += blockcache[ idx ].pages_cnt;
497 0 : }
498 :
499 : static void
500 : fd_txncache_remove_slotcache_idx( fd_txncache_t * tc,
501 0 : ulong idx ) {
502 0 : fd_txncache_private_slotcache_t * slotcache = fd_txncache_get_slotcache( tc );
503 0 : slotcache[ idx ].slot = FD_TXNCACHE_TOMBSTONE_ENTRY;
504 0 : }
505 :
506 : static void
507 : fd_txncache_purge_slot( fd_txncache_t * tc,
508 0 : ulong slot ) {
509 0 : ulong not_purged_cnt = 0;
510 0 : ulong purged_cnt = 0;
511 0 : ulong max_distance = 0;
512 0 : ulong sum_distance = 0;
513 0 : ulong empty_entry_cnt = 0;
514 0 : ulong tombstone_entry_cnt = 0;
515 0 : fd_txncache_private_blockcache_t * blockcache = fd_txncache_get_blockcache( tc );
516 0 : for( ulong i=0UL; i<tc->live_slots_max; i++ ) {
517 0 : if( FD_LIKELY( blockcache[ i ].max_slot==FD_TXNCACHE_EMPTY_ENTRY || blockcache[ i ].max_slot==FD_TXNCACHE_TOMBSTONE_ENTRY || (blockcache[ i ].max_slot)>slot ) ) {
518 0 : if( blockcache[ i ].max_slot==FD_TXNCACHE_EMPTY_ENTRY ) {
519 0 : empty_entry_cnt++;
520 0 : } else if ( blockcache[ i ].max_slot==FD_TXNCACHE_TOMBSTONE_ENTRY ) {
521 0 : tombstone_entry_cnt++;
522 0 : } else {
523 0 : not_purged_cnt++;
524 0 : ulong dist = blockcache[ i ].max_slot-slot;
525 0 : max_distance = fd_ulong_max( max_distance, dist );
526 0 : sum_distance += blockcache[ i ].max_slot-slot;
527 0 : }
528 0 : continue;
529 0 : }
530 0 : fd_txncache_remove_blockcache_idx( tc, i );
531 0 : purged_cnt++;
532 0 : }
533 0 : ulong avg_distance = (not_purged_cnt==0) ? ULONG_MAX : (sum_distance/not_purged_cnt);
534 0 : FD_LOG_INFO(( "not purging cnt - purge_slot: %lu, purged_cnt: %lu, not_purged_cnt: %lu, empty_entry_cnt: %lu, tombstone_entry_cnt: %lu, max_distance: %lu, avg_distance: %lu",
535 0 : slot, purged_cnt, not_purged_cnt, empty_entry_cnt, tombstone_entry_cnt, max_distance, avg_distance ));
536 :
537 : /* TODO: figure out how to make slotcache purging work with the max_slot purge for blockcache.
538 : The blockcache and slotcache share txnpages and the aggressive purging from the blockcache
539 : can lead to corruption in the slotcache. Does it make sense to generate the delta map (as
540 : generated by Agave) from the blockcache when producing snapshots? TBD. */
541 0 : fd_txncache_private_slotcache_t * slotcache = fd_txncache_get_slotcache( tc );
542 0 : for( ulong i=0UL; i<tc->live_slots_max; i++ ) {
543 0 : if( FD_LIKELY( slotcache[ i ].slot==FD_TXNCACHE_EMPTY_ENTRY || slotcache[ i ].slot==FD_TXNCACHE_TOMBSTONE_ENTRY || slotcache[ i ].slot>slot ) ) continue;
544 0 : fd_txncache_remove_slotcache_idx( tc, i );
545 0 : }
546 0 : }
547 :
548 : /* fd_txncache_register_root_slot_private is a helper function that
549 : actually registers the root. This function assumes that the
550 : caller has already obtained a lock to the status cache. */
551 :
552 : static void
553 : fd_txncache_register_root_slot_private( fd_txncache_t * tc,
554 0 : ulong slot ) {
555 :
556 0 : ulong * root_slots = fd_txncache_get_root_slots( tc );
557 0 : ulong idx;
558 0 : for( idx=0UL; idx<tc->root_slots_cnt; idx++ ) {
559 0 : if( FD_UNLIKELY( root_slots[ idx ]==slot ) ) return;
560 0 : if( FD_UNLIKELY( root_slots[ idx ]>slot ) ) break;
561 0 : }
562 :
563 0 : if( FD_UNLIKELY( tc->root_slots_cnt>=tc->root_slots_max ) ) {
564 0 : if( FD_LIKELY( idx ) ) {
565 0 : fd_txncache_purge_slot( tc, root_slots[ 0 ] );
566 0 : memmove( root_slots, root_slots+1UL, (idx-1UL)*sizeof(ulong) );
567 0 : root_slots[ (idx-1UL) ] = slot;
568 0 : } else {
569 0 : fd_txncache_purge_slot( tc, slot );
570 0 : }
571 0 : } else {
572 0 : if( FD_UNLIKELY( idx<tc->root_slots_cnt ) ) {
573 0 : memmove( root_slots+idx+1UL, root_slots+idx, (tc->root_slots_cnt-idx)*sizeof(ulong) );
574 0 : }
575 0 : root_slots[ idx ] = slot;
576 0 : tc->root_slots_cnt++;
577 0 : }
578 0 : }
579 :
580 : void
581 : fd_txncache_register_root_slot( fd_txncache_t * tc,
582 0 : ulong slot ) {
583 :
584 0 : fd_rwlock_write( tc->lock );
585 :
586 0 : fd_txncache_register_root_slot_private( tc, slot );
587 :
588 0 : fd_rwlock_unwrite( tc->lock );
589 0 : }
590 :
591 : void
592 : fd_txncache_register_constipated_slot( fd_txncache_t * tc,
593 0 : ulong slot ) {
594 :
595 0 : fd_rwlock_write( tc->lock );
596 :
597 0 : if( FD_UNLIKELY( tc->constipated_slots_cnt>=tc->constipated_slots_max ) ) {
598 0 : FD_LOG_ERR(( "Status cache has exceeded constipated max slot count" ));
599 0 : }
600 :
601 0 : ulong * constipated_slots = fd_txncache_get_constipated_slots( tc );
602 0 : constipated_slots[ tc->constipated_slots_cnt++ ] = slot;
603 :
604 0 : fd_rwlock_unwrite( tc->lock );
605 :
606 0 : }
607 :
608 : void
609 0 : fd_txncache_flush_constipated_slots( fd_txncache_t * tc ) {
610 :
611 : /* Register all previously constipated slots and unconstipate registration
612 : into the status cache. */
613 :
614 0 : fd_rwlock_write( tc->lock );
615 :
616 0 : ulong * constipated_slots = fd_txncache_get_constipated_slots( tc );
617 0 : for( ulong i=0UL; i<tc->constipated_slots_cnt; i++ ) {
618 0 : fd_txncache_register_root_slot_private( tc, constipated_slots[ i ] );
619 0 : }
620 0 : tc->constipated_slots_cnt = 0UL;
621 :
622 0 : tc->is_constipated = 0;
623 :
624 0 : fd_rwlock_unwrite( tc->lock );
625 :
626 0 : }
627 :
628 : void
629 : fd_txncache_root_slots( fd_txncache_t * tc,
630 0 : ulong * out_slots ) {
631 0 : fd_rwlock_write( tc->lock );
632 0 : ulong * root_slots = fd_txncache_get_root_slots( tc );
633 0 : memcpy( out_slots, root_slots, tc->root_slots_max*sizeof(ulong) );
634 0 : fd_rwlock_unwrite( tc->lock );
635 0 : }
636 :
637 0 : #define FD_TXNCACHE_FIND_FOUND (0)
638 0 : #define FD_TXNCACHE_FIND_FOUNDEMPTY (1)
639 0 : #define FD_TXNCACHE_FIND_FULL (2)
640 :
641 : static int
642 : fd_txncache_find_blockhash( fd_txncache_t const * tc,
643 : uchar const blockhash[ static 32 ],
644 : uint is_insert,
645 0 : fd_txncache_private_blockcache_t ** out_blockcache ) {
646 0 : ulong hash = FD_LOAD( ulong, blockhash );
647 0 : fd_txncache_private_blockcache_t * tc_blockcache = fd_txncache_get_blockcache_const( tc );
648 0 : ulong * probed_entries = fd_txncache_get_probed_entries_const( tc );
649 0 : ulong first_tombstone = ULONG_MAX;
650 :
651 0 : for( ulong i=0UL; i<tc->live_slots_max; i++ ) {
652 0 : ulong blockcache_idx = (hash+i)%tc->live_slots_max;
653 0 : fd_txncache_private_blockcache_t * blockcache = &tc_blockcache[ blockcache_idx ];
654 :
655 0 : if( FD_UNLIKELY( blockcache->max_slot==FD_TXNCACHE_EMPTY_ENTRY ) ) {
656 0 : if( first_tombstone != ULONG_MAX ) {
657 0 : *out_blockcache = &tc_blockcache[ first_tombstone ];
658 0 : return FD_TXNCACHE_FIND_FOUNDEMPTY;
659 0 : }
660 0 : *out_blockcache = blockcache;
661 0 : return FD_TXNCACHE_FIND_FOUNDEMPTY;
662 0 : } else if ( blockcache->max_slot==FD_TXNCACHE_TOMBSTONE_ENTRY ) {
663 0 : if( is_insert && first_tombstone == ULONG_MAX ) {
664 0 : first_tombstone = blockcache_idx;
665 0 : }
666 0 : continue;
667 0 : }
668 :
669 0 : while( FD_UNLIKELY( blockcache->max_slot==FD_TXNCACHE_TEMP_ENTRY ) ) {
670 0 : FD_SPIN_PAUSE();
671 0 : }
672 0 : FD_COMPILER_MFENCE(); /* Prevent reordering of the blockhash read to before the atomic lock
673 : (highest_slot) has been fully released by the writer. */
674 0 : if( FD_LIKELY( !memcmp( blockcache->blockhash, blockhash, 32UL ) ) ) {
675 0 : *out_blockcache = blockcache;
676 0 : if( is_insert ) {
677 : /* Undo the probed entry changes since we found the blockhash. */
678 0 : for( ulong j=hash%tc->live_slots_max; j!=fd_ulong_min(first_tombstone, blockcache_idx); ) {
679 0 : probed_entries[ j ]--;
680 0 : j = (j+1)%tc->live_slots_max;
681 0 : }
682 0 : }
683 0 : return FD_TXNCACHE_FIND_FOUND;
684 0 : }
685 : /* If the entry we are passing is full and we haven't seen tombstones,
686 : there is an overflow. */
687 0 : if( is_insert && first_tombstone == ULONG_MAX ) {
688 0 : probed_entries[ blockcache_idx ]++;
689 0 : }
690 0 : }
691 :
692 0 : if( first_tombstone != ULONG_MAX ) {
693 0 : *out_blockcache = &tc_blockcache[ first_tombstone ];
694 0 : return FD_TXNCACHE_FIND_FOUNDEMPTY;
695 0 : }
696 0 : return FD_TXNCACHE_FIND_FULL;
697 0 : }
698 :
699 : static int
700 : fd_txncache_find_slot( fd_txncache_t const * tc,
701 : ulong slot,
702 : uint is_insert,
703 0 : fd_txncache_private_slotcache_t ** out_slotcache ) {
704 0 : fd_txncache_private_slotcache_t * tc_slotcache = fd_txncache_get_slotcache_const( tc );
705 0 : for( ulong i=0UL; i<tc->live_slots_max; i++ ) {
706 0 : ulong slotcache_idx = (slot+i)%tc->live_slots_max;
707 0 : fd_txncache_private_slotcache_t * slotcache = &tc_slotcache[ slotcache_idx ];
708 0 : if( FD_UNLIKELY( slotcache->slot==FD_TXNCACHE_EMPTY_ENTRY ) ) {
709 0 : *out_slotcache = slotcache;
710 0 : return FD_TXNCACHE_FIND_FOUNDEMPTY;
711 0 : } else if( FD_UNLIKELY( slotcache->slot==FD_TXNCACHE_TOMBSTONE_ENTRY ) ) {
712 0 : if( is_insert ) {
713 0 : *out_slotcache = slotcache;
714 0 : return FD_TXNCACHE_FIND_FOUNDEMPTY;
715 0 : }
716 0 : continue;
717 0 : }
718 0 : while( FD_UNLIKELY( slotcache->slot==FD_TXNCACHE_TEMP_ENTRY ) ) {
719 0 : FD_SPIN_PAUSE();
720 0 : }
721 0 : FD_COMPILER_MFENCE(); /* Prevent reordering of the slot read to before the atomic lock
722 : (slot) has been fully released by the writer. */
723 0 : if( FD_LIKELY( slotcache->slot==slot ) ) {
724 0 : *out_slotcache = slotcache;
725 0 : return FD_TXNCACHE_FIND_FOUND;
726 0 : }
727 0 : }
728 0 : return FD_TXNCACHE_FIND_FULL;
729 0 : }
730 :
731 : static int
732 : fd_txncache_find_slot_blockhash( fd_txncache_private_slotcache_t * slotcache,
733 : uchar const blockhash[ static 32 ],
734 0 : fd_txncache_private_slotblockcache_t ** out_slotblockcache ) {
735 0 : ulong hash = FD_LOAD( ulong, blockhash );
736 0 : for( ulong i=0UL; i<300UL; i++ ) {
737 0 : ulong slotblockcache_idx = (hash+i)%300UL;
738 0 : fd_txncache_private_slotblockcache_t * slotblockcache = &slotcache->blockcache[ slotblockcache_idx ];
739 0 : if( FD_UNLIKELY( slotblockcache->txnhash_offset==ULONG_MAX ) ) {
740 0 : *out_slotblockcache = slotblockcache;
741 0 : return FD_TXNCACHE_FIND_FOUNDEMPTY;
742 0 : }
743 0 : while( FD_UNLIKELY( slotblockcache->txnhash_offset==ULONG_MAX-1UL ) ) {
744 0 : FD_SPIN_PAUSE();
745 0 : }
746 0 : FD_COMPILER_MFENCE(); /* Prevent reordering of the blockhash read to before the atomic lock
747 : (txnhash_offset) has been fully released by the writer. */
748 0 : if( FD_LIKELY( !memcmp( slotblockcache->blockhash, blockhash, 32UL ) ) ) {
749 0 : *out_slotblockcache = slotblockcache;
750 0 : return FD_TXNCACHE_FIND_FOUND;
751 0 : }
752 0 : }
753 0 : return FD_TXNCACHE_FIND_FULL;
754 0 : }
755 :
756 : static int
757 : fd_txncache_ensure_blockcache( fd_txncache_t * tc,
758 : uchar const blockhash[ static 32 ],
759 0 : fd_txncache_private_blockcache_t ** out_blockcache ) {
760 0 : for(;;) {
761 0 : int blockcache_find = fd_txncache_find_blockhash( tc, blockhash, 1, out_blockcache );
762 0 : if( FD_LIKELY( blockcache_find==FD_TXNCACHE_FIND_FOUND ) ) return 1;
763 0 : else if( FD_UNLIKELY( blockcache_find==FD_TXNCACHE_FIND_FULL ) ) return 0;
764 :
765 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &(*out_blockcache)->max_slot, FD_TXNCACHE_EMPTY_ENTRY, FD_TXNCACHE_TEMP_ENTRY ) ||
766 0 : FD_ATOMIC_CAS( &(*out_blockcache)->max_slot, FD_TXNCACHE_TOMBSTONE_ENTRY, FD_TXNCACHE_TEMP_ENTRY ) ) ) {
767 0 : memcpy( (*out_blockcache)->blockhash, blockhash, 32UL );
768 0 : memset( (*out_blockcache)->heads, 0xFF, FD_TXNCACHE_BLOCKCACHE_MAP_CNT*sizeof(uint) );
769 0 : (*out_blockcache)->pages_cnt = 0;
770 0 : (*out_blockcache)->txnhash_offset = 0UL;
771 0 : memset( (*out_blockcache)->pages, 0xFF, tc->txnpages_per_blockhash_max*sizeof(uint) );
772 0 : FD_COMPILER_MFENCE();
773 : /* Set it to max unreserved value possible */
774 0 : (*out_blockcache)->max_slot = ULONG_MAX-3UL;
775 0 : return 1;
776 0 : }
777 0 : FD_SPIN_PAUSE();
778 0 : }
779 0 : }
780 :
781 : static int
782 : fd_txncache_ensure_slotcache( fd_txncache_t * tc,
783 : ulong slot,
784 0 : fd_txncache_private_slotcache_t ** out_slotcache ) {
785 0 : for(;;) {
786 0 : int slotcache_find = fd_txncache_find_slot( tc, slot, 1, out_slotcache );
787 0 : if( FD_LIKELY( slotcache_find==FD_TXNCACHE_FIND_FOUND ) ) return 1;
788 0 : else if( FD_UNLIKELY( slotcache_find==FD_TXNCACHE_FIND_FULL ) ) return 0;
789 :
790 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &(*out_slotcache)->slot, FD_TXNCACHE_EMPTY_ENTRY, FD_TXNCACHE_TEMP_ENTRY ) ||
791 0 : FD_ATOMIC_CAS( &(*out_slotcache)->slot, FD_TXNCACHE_TOMBSTONE_ENTRY, FD_TXNCACHE_TEMP_ENTRY ) ) ) {
792 0 : for( ulong i=0UL; i<300UL; i++ ) {
793 0 : (*out_slotcache)->blockcache[ i ].txnhash_offset = ULONG_MAX;
794 0 : }
795 0 : FD_COMPILER_MFENCE();
796 0 : (*out_slotcache)->slot = slot;
797 0 : return 1;
798 0 : }
799 0 : FD_SPIN_PAUSE();
800 0 : }
801 0 : }
802 :
803 : static int
804 : fd_txncache_ensure_slotblockcache( fd_txncache_private_slotcache_t * slotcache,
805 : uchar const blockhash[ static 32 ],
806 0 : fd_txncache_private_slotblockcache_t ** out_slotblockcache ) {
807 0 : for(;;) {
808 0 : int slotblockcache_find = fd_txncache_find_slot_blockhash( slotcache, blockhash, out_slotblockcache );
809 0 : if( FD_LIKELY( slotblockcache_find==FD_TXNCACHE_FIND_FOUND ) ) return 1;
810 0 : else if( FD_UNLIKELY( slotblockcache_find==FD_TXNCACHE_FIND_FULL ) ) return 0;
811 :
812 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &(*out_slotblockcache)->txnhash_offset, ULONG_MAX, ULONG_MAX-1UL ) ) ) {
813 0 : memcpy( (*out_slotblockcache)->blockhash, blockhash, 32UL );
814 0 : memset( (*out_slotblockcache)->heads, 0xFF, FD_TXNCACHE_SLOTCACHE_MAP_CNT*sizeof(uint) );
815 0 : FD_COMPILER_MFENCE();
816 0 : (*out_slotblockcache)->txnhash_offset = 0UL;
817 0 : return 1;
818 0 : }
819 0 : FD_SPIN_PAUSE();
820 0 : }
821 0 : }
822 :
823 : static fd_txncache_private_txnpage_t *
824 : fd_txncache_ensure_txnpage( fd_txncache_t * tc,
825 0 : fd_txncache_private_blockcache_t * blockcache ) {
826 0 : ushort page_cnt = blockcache->pages_cnt;
827 0 : if( FD_UNLIKELY( page_cnt>tc->txnpages_per_blockhash_max ) ) return NULL;
828 0 : fd_txncache_private_txnpage_t * txnpages = fd_txncache_get_txnpages( tc );
829 :
830 0 : if( FD_LIKELY( page_cnt ) ) {
831 0 : uint txnpage_idx = blockcache->pages[ page_cnt-1 ];
832 0 : ushort txnpage_free = txnpages[ txnpage_idx ].free;
833 0 : if( FD_LIKELY( txnpage_free ) ) return &txnpages[ txnpage_idx ];
834 0 : }
835 :
836 0 : if( FD_UNLIKELY( page_cnt==tc->txnpages_per_blockhash_max ) ) return NULL;
837 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &blockcache->pages[ page_cnt ], UINT_MAX, UINT_MAX-1UL )==UINT_MAX ) ) {
838 0 : ulong txnpages_free_cnt = tc->txnpages_free_cnt;
839 0 : for(;;) {
840 0 : if( FD_UNLIKELY( !txnpages_free_cnt ) ) return NULL;
841 0 : ulong old_txnpages_free_cnt = FD_ATOMIC_CAS( &tc->txnpages_free_cnt, (uint)txnpages_free_cnt, (uint)(txnpages_free_cnt-1UL) );
842 0 : if( FD_LIKELY( old_txnpages_free_cnt==txnpages_free_cnt ) ) break;
843 0 : txnpages_free_cnt = old_txnpages_free_cnt;
844 0 : FD_SPIN_PAUSE();
845 0 : }
846 0 : uint * txnpages_free = fd_txncache_get_txnpages_free( tc );
847 :
848 0 : uint txnpage_idx = txnpages_free[ txnpages_free_cnt-1UL ];
849 0 : fd_txncache_private_txnpage_t * txnpage = &txnpages[ txnpage_idx ];
850 0 : txnpage->free = FD_TXNCACHE_TXNS_PER_PAGE;
851 0 : FD_COMPILER_MFENCE();
852 0 : blockcache->pages[ page_cnt ] = txnpage_idx;
853 0 : FD_COMPILER_MFENCE();
854 0 : blockcache->pages_cnt = (ushort)(page_cnt+1);
855 0 : return txnpage;
856 0 : } else {
857 0 : uint txnpage_idx = blockcache->pages[ page_cnt ];
858 0 : while( FD_UNLIKELY( txnpage_idx>=UINT_MAX-1UL ) ) {
859 0 : txnpage_idx = blockcache->pages[ page_cnt ];
860 0 : FD_SPIN_PAUSE();
861 0 : }
862 0 : return &txnpages[ txnpage_idx ];
863 0 : }
864 0 : }
865 :
866 : static int
867 : fd_txncache_insert_txn( fd_txncache_t * tc,
868 : fd_txncache_private_blockcache_t * blockcache,
869 : fd_txncache_private_slotblockcache_t * slotblockcache,
870 : fd_txncache_private_txnpage_t * txnpage,
871 0 : fd_txncache_insert_t const * txn ) {
872 0 : fd_txncache_private_txnpage_t * txnpages = fd_txncache_get_txnpages( tc );
873 0 : ulong txnpage_idx = (ulong)(txnpage - txnpages);
874 :
875 0 : for(;;) {
876 0 : ushort txnpage_free = txnpage->free;
877 0 : if( FD_UNLIKELY( !txnpage_free ) ) return 0;
878 0 : if( FD_UNLIKELY( FD_ATOMIC_CAS( &txnpage->free, txnpage_free, txnpage_free-1UL )!=txnpage_free ) ) continue;
879 :
880 0 : ulong txn_idx = FD_TXNCACHE_TXNS_PER_PAGE-txnpage_free;
881 0 : ulong txnhash_offset = blockcache->txnhash_offset;
882 0 : ulong txnhash = FD_LOAD( ulong, txn->txnhash+txnhash_offset );
883 0 : memcpy( txnpage->txns[ txn_idx ]->txnhash, txn->txnhash+txnhash_offset, 20UL );
884 0 : txnpage->txns[ txn_idx ]->result = *txn->result;
885 0 : txnpage->txns[ txn_idx ]->slot = txn->slot;
886 0 : FD_COMPILER_MFENCE();
887 :
888 0 : for(;;) {
889 0 : ulong txn_bucket = txnhash%FD_TXNCACHE_BLOCKCACHE_MAP_CNT;
890 0 : uint head = blockcache->heads[ txn_bucket ];
891 0 : txnpage->txns[ txn_idx ]->blockcache_next = head;
892 0 : FD_COMPILER_MFENCE();
893 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &blockcache->heads[ txn_bucket ], head, (uint)(FD_TXNCACHE_TXNS_PER_PAGE*txnpage_idx+txn_idx) )==head ) ) break;
894 0 : FD_SPIN_PAUSE();
895 0 : }
896 :
897 0 : for(;;) {
898 0 : ulong txn_bucket = txnhash%FD_TXNCACHE_SLOTCACHE_MAP_CNT;
899 0 : uint head = slotblockcache->heads[ txn_bucket ];
900 0 : txnpage->txns[ txn_idx ]->slotblockcache_next = head;
901 0 : FD_COMPILER_MFENCE();
902 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &slotblockcache->heads[ txn_bucket ], head, (uint)(FD_TXNCACHE_TXNS_PER_PAGE*txnpage_idx+txn_idx) )==head ) ) break;
903 0 : FD_SPIN_PAUSE();
904 0 : }
905 :
906 0 : for(;;) {
907 0 : ulong max_slot = blockcache->max_slot;
908 :
909 0 : if( FD_UNLIKELY( txn->slot<=max_slot && max_slot != ULONG_MAX-3UL) ) break;
910 0 : if( FD_LIKELY( FD_ATOMIC_CAS( &blockcache->max_slot, max_slot, txn->slot )==max_slot ) ) break;
911 0 : FD_SPIN_PAUSE();
912 0 : }
913 0 : return 1;
914 0 : }
915 0 : }
916 :
917 : int
918 : fd_txncache_insert_batch( fd_txncache_t * tc,
919 : fd_txncache_insert_t const * txns,
920 0 : ulong txns_cnt ) {
921 0 : fd_rwlock_read( tc->lock );
922 :
923 0 : for( ulong i=0UL; i<txns_cnt; i++ ) {
924 0 : fd_txncache_private_blockcache_t * blockcache;
925 0 : if( FD_UNLIKELY( !fd_txncache_ensure_blockcache( tc, txns[ i ].blockhash, &blockcache ) ) ) {
926 0 : FD_LOG_WARNING(( "no blockcache found" ));
927 0 : goto unlock_fail;
928 0 : }
929 :
930 0 : fd_txncache_private_slotcache_t * slotcache;
931 0 : if( FD_UNLIKELY( !fd_txncache_ensure_slotcache( tc, txns[ i ].slot, &slotcache ) ) ) {
932 0 : FD_LOG_WARNING(( "no slotcache found" ));
933 0 : goto unlock_fail;
934 0 : }
935 :
936 0 : fd_txncache_private_slotblockcache_t * slotblockcache;
937 0 : if( FD_UNLIKELY( !fd_txncache_ensure_slotblockcache( slotcache, txns[ i ].blockhash, &slotblockcache ) ) ) {
938 0 : FD_LOG_WARNING(( "no slotblockcache found" ));
939 0 : goto unlock_fail;
940 0 : }
941 :
942 0 : for(;;) {
943 0 : fd_txncache_private_txnpage_t * txnpage = fd_txncache_ensure_txnpage( tc, blockcache );
944 0 : if( FD_UNLIKELY( !txnpage ) ) {
945 0 : goto unlock_fail;
946 0 : FD_LOG_WARNING(( "no txnpage found" ));
947 0 : }
948 :
949 0 : int success = fd_txncache_insert_txn( tc, blockcache, slotblockcache, txnpage, &txns[ i ] );
950 0 : if( FD_LIKELY( success ) ) break;
951 0 : FD_SPIN_PAUSE();
952 0 : }
953 0 : }
954 :
955 0 : fd_rwlock_unread( tc->lock );
956 0 : return 1;
957 :
958 0 : unlock_fail:
959 0 : fd_rwlock_unread( tc->lock );
960 0 : return 0;
961 0 : }
962 :
963 : void
964 : fd_txncache_query_batch( fd_txncache_t * tc,
965 : fd_txncache_query_t const * queries,
966 : ulong queries_cnt,
967 : void * query_func_ctx,
968 : int ( * query_func )( ulong slot, void * ctx ),
969 0 : int * out_results ) {
970 0 : fd_rwlock_read( tc->lock );
971 0 : fd_txncache_private_txnpage_t * txnpages = fd_txncache_get_txnpages( tc );
972 0 : for( ulong i=0UL; i<queries_cnt; i++ ) {
973 0 : out_results[ i ] = 0;
974 :
975 0 : fd_txncache_query_t const * query = &queries[ i ];
976 0 : fd_txncache_private_blockcache_t * blockcache;
977 0 : int result = fd_txncache_find_blockhash( tc, query->blockhash, 0, &blockcache );
978 :
979 0 : if( FD_UNLIKELY( result!=FD_TXNCACHE_FIND_FOUND ) ) {
980 0 : continue;
981 0 : }
982 :
983 0 : ulong txnhash_offset = blockcache->txnhash_offset;
984 0 : ulong head_hash = FD_LOAD( ulong, query->txnhash+txnhash_offset ) % FD_TXNCACHE_BLOCKCACHE_MAP_CNT;
985 0 : for( uint head=blockcache->heads[ head_hash ]; head!=UINT_MAX; head=txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ]->blockcache_next ) {
986 0 : fd_txncache_private_txn_t * txn = txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ];
987 0 : if( FD_LIKELY( !memcmp( query->txnhash+txnhash_offset, txn->txnhash, 20UL ) ) ) {
988 0 : if( FD_LIKELY( !query_func || query_func( txn->slot, query_func_ctx ) ) ) {
989 0 : out_results[ i ] = 1;
990 0 : break;
991 0 : }
992 0 : }
993 0 : }
994 0 : }
995 :
996 0 : fd_rwlock_unread( tc->lock );
997 0 : }
998 :
999 : int
1000 : fd_txncache_snapshot( fd_txncache_t * tc,
1001 : void * ctx,
1002 0 : int ( * write )( uchar const * data, ulong data_sz, void * ctx ) ) {
1003 0 : if( !write ) {
1004 0 : FD_LOG_WARNING(("No write method provided to snapshotter"));
1005 0 : return 1;
1006 0 : }
1007 0 : fd_rwlock_read( tc->lock );
1008 :
1009 0 : fd_txncache_private_txnpage_t * txnpages = fd_txncache_get_txnpages( tc );
1010 0 : ulong * root_slots = fd_txncache_get_root_slots( tc );
1011 0 : for( ulong i=0UL; i<tc->root_slots_cnt; i++ ) {
1012 0 : ulong slot = root_slots[ i ];
1013 :
1014 0 : fd_txncache_private_slotcache_t * slotcache;
1015 0 : if( FD_UNLIKELY( FD_TXNCACHE_FIND_FOUND!=fd_txncache_find_slot( tc, slot, 0, &slotcache ) ) ) continue;
1016 :
1017 0 : for( ulong j=0UL; j<300UL; j++ ) {
1018 0 : fd_txncache_private_slotblockcache_t * slotblockcache = &slotcache->blockcache[ j ];
1019 0 : if( FD_UNLIKELY( slotblockcache->txnhash_offset>=ULONG_MAX-1UL ) ) continue;
1020 :
1021 0 : for( ulong k=0UL; k<FD_TXNCACHE_SLOTCACHE_MAP_CNT; k++ ) {
1022 0 : uint head = slotblockcache->heads[ k ];
1023 0 : for( ; head!=UINT_MAX; head=txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ]->slotblockcache_next ) {
1024 0 : fd_txncache_private_txn_t * txn = txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ];
1025 :
1026 0 : fd_txncache_snapshot_entry_t entry = {
1027 0 : .slot = slot,
1028 0 : .txn_idx = slotblockcache->txnhash_offset,
1029 0 : .result = txn->result
1030 0 : };
1031 0 : fd_memcpy( entry.blockhash, slotblockcache->blockhash, 32 );
1032 0 : fd_memcpy( entry.txnhash, txn->txnhash, 20 );
1033 0 : int err = write( (uchar*)&entry, sizeof(fd_txncache_snapshot_entry_t), ctx );
1034 0 : if( err ) {
1035 0 : fd_rwlock_unread( tc->lock );
1036 0 : return err;
1037 0 : }
1038 0 : }
1039 0 : }
1040 0 : }
1041 0 : }
1042 :
1043 0 : fd_rwlock_unread( tc->lock );
1044 0 : return 0;
1045 0 : }
1046 :
1047 : int
1048 : fd_txncache_set_txnhash_offset( fd_txncache_t * tc,
1049 : ulong slot,
1050 : uchar blockhash[ 32 ],
1051 0 : ulong txnhash_offset ) {
1052 0 : fd_rwlock_read( tc->lock );
1053 0 : fd_txncache_private_blockcache_t * blockcache;
1054 0 : if( FD_UNLIKELY( !fd_txncache_ensure_blockcache( tc, blockhash, &blockcache ) ) ) goto unlock_fail;
1055 :
1056 0 : blockcache->txnhash_offset = txnhash_offset;
1057 0 : fd_txncache_private_slotcache_t * slotcache;
1058 0 : if( FD_UNLIKELY( !fd_txncache_ensure_slotcache( tc, slot, &slotcache ) ) ) goto unlock_fail;
1059 :
1060 0 : fd_txncache_private_slotblockcache_t * slotblockcache;
1061 0 : if( FD_UNLIKELY( !fd_txncache_ensure_slotblockcache( slotcache, blockhash, &slotblockcache ) ) ) goto unlock_fail;
1062 0 : slotblockcache->txnhash_offset = txnhash_offset;
1063 :
1064 0 : fd_rwlock_unread( tc->lock );
1065 0 : return 0;
1066 :
1067 0 : unlock_fail:
1068 0 : fd_rwlock_unread( tc->lock );
1069 0 : return 1;
1070 0 : }
1071 :
1072 : int
1073 : fd_txncache_is_rooted_slot( fd_txncache_t * tc,
1074 0 : ulong slot ) {
1075 0 : fd_rwlock_read( tc->lock );
1076 :
1077 0 : ulong * root_slots = fd_txncache_get_root_slots( tc );
1078 0 : for( ulong idx=0UL; idx<tc->root_slots_cnt; idx++ ) {
1079 0 : if( FD_UNLIKELY( root_slots[ idx ]==slot ) ) {
1080 0 : fd_rwlock_unread( tc->lock );
1081 0 : return 1;
1082 0 : }
1083 0 : if( FD_UNLIKELY( root_slots[ idx ]>slot ) ) break;
1084 0 : }
1085 :
1086 0 : fd_rwlock_unread( tc->lock );
1087 0 : return 0;
1088 0 : }
1089 :
1090 : int
1091 : fd_txncache_get_entries( fd_txncache_t * tc,
1092 0 : fd_bank_slot_deltas_t * slot_deltas ) {
1093 :
1094 0 : fd_rwlock_read( tc->lock );
1095 :
1096 0 : slot_deltas->slot_deltas_len = tc->root_slots_cnt;
1097 0 : slot_deltas->slot_deltas = fd_scratch_alloc( FD_SLOT_DELTA_ALIGN, tc->root_slots_cnt * sizeof(fd_slot_delta_t) );
1098 :
1099 0 : fd_txncache_private_txnpage_t * txnpages = fd_txncache_get_txnpages( tc );
1100 0 : ulong * root_slots = fd_txncache_get_root_slots( tc );
1101 :
1102 0 : for( ulong i=0UL; i<tc->root_slots_cnt; i++ ) {
1103 0 : ulong slot = root_slots[ i ];
1104 :
1105 0 : slot_deltas->slot_deltas[ i ].slot = slot;
1106 0 : slot_deltas->slot_deltas[ i ].is_root = 1;
1107 0 : slot_deltas->slot_deltas[ i ].slot_delta_vec = fd_scratch_alloc( FD_STATUS_PAIR_ALIGN, FD_TXNCACHE_DEFAULT_MAX_ROOTED_SLOTS * sizeof(fd_status_pair_t) );
1108 0 : slot_deltas->slot_deltas[ i ].slot_delta_vec_len = 0UL;
1109 0 : ulong slot_delta_vec_len = 0UL;
1110 :
1111 0 : fd_txncache_private_slotcache_t * slotcache;
1112 0 : if( FD_UNLIKELY( FD_TXNCACHE_FIND_FOUND!=fd_txncache_find_slot( tc, slot, 0, &slotcache ) ) ) {
1113 0 : continue;
1114 0 : }
1115 :
1116 0 : for( ulong j=0UL; j<FD_TXNCACHE_DEFAULT_MAX_ROOTED_SLOTS; j++ ) {
1117 0 : fd_txncache_private_slotblockcache_t * slotblockcache = &slotcache->blockcache[ j ];
1118 0 : if( FD_UNLIKELY( slotblockcache->txnhash_offset>=ULONG_MAX-1UL ) ) {
1119 0 : continue;
1120 0 : }
1121 0 : fd_status_pair_t * status_pair = &slot_deltas->slot_deltas[ i ].slot_delta_vec[ slot_delta_vec_len++ ];
1122 0 : fd_memcpy( &status_pair->hash, slotblockcache->blockhash, sizeof(fd_hash_t) );
1123 0 : status_pair->value.txn_idx = slotblockcache->txnhash_offset;
1124 :
1125 : /* First count through the number of etnries you expect to encounter
1126 : and size out the data structure to store them. */
1127 :
1128 0 : ulong num_statuses = 0UL;
1129 0 : for( ulong k=0UL; k<FD_TXNCACHE_SLOTCACHE_MAP_CNT; k++ ) {
1130 0 : uint head = slotblockcache->heads[ k ];
1131 0 : for( ; head!=UINT_MAX; head=txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ]->slotblockcache_next ) {
1132 0 : num_statuses++;
1133 0 : }
1134 0 : }
1135 :
1136 0 : status_pair->value.statuses_len = num_statuses;
1137 0 : status_pair->value.statuses = fd_scratch_alloc( FD_CACHE_STATUS_ALIGN, num_statuses * sizeof(fd_cache_status_t) );
1138 0 : fd_memset( status_pair->value.statuses, 0, num_statuses * sizeof(fd_cache_status_t) );
1139 :
1140 : /* Copy over every entry for the given slot into the slot deltas. */
1141 :
1142 0 : num_statuses = 0UL;
1143 0 : for( ulong k=0UL; k<FD_TXNCACHE_SLOTCACHE_MAP_CNT; k++ ) {
1144 0 : uint head = slotblockcache->heads[ k ];
1145 0 : for( ; head!=UINT_MAX; head=txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ]->slotblockcache_next ) {
1146 0 : fd_txncache_private_txn_t * txn = txnpages[ head/FD_TXNCACHE_TXNS_PER_PAGE ].txns[ head%FD_TXNCACHE_TXNS_PER_PAGE ];
1147 0 : fd_memcpy( status_pair->value.statuses[ num_statuses ].key_slice, txn->txnhash, 20 );
1148 0 : status_pair->value.statuses[ num_statuses++ ].result.discriminant = txn->result;
1149 0 : }
1150 0 : }
1151 0 : }
1152 0 : slot_deltas->slot_deltas[ i ].slot_delta_vec_len = slot_delta_vec_len;
1153 0 : }
1154 :
1155 0 : fd_rwlock_unread( tc->lock );
1156 :
1157 0 : return 0;
1158 :
1159 0 : }
1160 :
1161 : int
1162 0 : fd_txncache_get_is_constipated( fd_txncache_t * tc ) {
1163 0 : fd_rwlock_read( tc->lock );
1164 :
1165 0 : int is_constipated = tc->is_constipated;
1166 :
1167 0 : fd_rwlock_unread( tc->lock );
1168 :
1169 0 : return is_constipated;
1170 0 : }
1171 :
1172 : int
1173 0 : fd_txncache_set_is_constipated( fd_txncache_t * tc, int is_constipated ) {
1174 0 : fd_rwlock_read( tc->lock );
1175 :
1176 0 : tc->is_constipated = is_constipated;
1177 :
1178 0 : fd_rwlock_unread( tc->lock );
1179 :
1180 0 : return 0;
1181 0 : }
|
