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