Line data Source code
1 : #include "fd_prog_load.h"
2 : #include "fd_progcache_user.h"
3 : #include "fd_progcache_rec.h"
4 : #include "../accdb/fd_accdb_sync.h"
5 : #include "../accdb/fd_accdb_impl_v1.h"
6 : #include "../../util/racesan/fd_racesan_target.h"
7 :
8 : FD_TL fd_progcache_metrics_t fd_progcache_metrics_default;
9 :
10 : fd_progcache_t *
11 : fd_progcache_join( fd_progcache_t * ljoin,
12 : void * shfunk,
13 : uchar * scratch,
14 90 : ulong scratch_sz ) {
15 90 : if( FD_UNLIKELY( !ljoin ) ) {
16 0 : FD_LOG_WARNING(( "NULL ljoin" ));
17 0 : return NULL;
18 0 : }
19 90 : if( FD_UNLIKELY( !shfunk ) ) {
20 0 : FD_LOG_WARNING(( "NULL shfunk" ));
21 0 : return NULL;
22 0 : }
23 90 : if( FD_LIKELY( scratch_sz ) ) {
24 90 : if( FD_UNLIKELY( !scratch ) ) {
25 0 : FD_LOG_WARNING(( "NULL scratch" ));
26 0 : return NULL;
27 0 : }
28 90 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)scratch, FD_PROGCACHE_SCRATCH_ALIGN ) ) ) {
29 0 : FD_LOG_WARNING(( "misaligned scratch" ));
30 0 : return NULL;
31 0 : }
32 90 : }
33 90 : memset( ljoin, 0, sizeof(fd_progcache_t) );
34 90 : if( FD_UNLIKELY( !fd_funk_join( ljoin->funk, shfunk ) ) ) return NULL;
35 :
36 90 : ljoin->metrics = &fd_progcache_metrics_default;
37 90 : ljoin->scratch = scratch;
38 90 : ljoin->scratch_sz = scratch_sz;
39 :
40 90 : return ljoin;
41 90 : }
42 :
43 : void *
44 : fd_progcache_leave( fd_progcache_t * cache,
45 87 : void ** opt_shfunk ) {
46 87 : if( FD_UNLIKELY( !cache ) ) {
47 0 : FD_LOG_WARNING(( "NULL cache" ));
48 0 : return NULL;
49 0 : }
50 87 : if( FD_UNLIKELY( !fd_funk_leave( cache->funk, opt_shfunk ) ) ) return NULL;
51 87 : cache->scratch = NULL;
52 87 : cache->scratch_sz = 0UL;
53 87 : return cache;
54 87 : }
55 :
56 : /* fd_progcache_load_fork pivots the progcache object to the selected
57 : fork (identified by tip XID).
58 :
59 : Populates cache->fork, which is a array-backed list of XIDs sorted
60 : newest to oldest. Cache lookups only respect records with an XID
61 : present in that list.
62 :
63 : For any given xid, the epoch_slot0 is assumed to stay constant. */
64 :
65 : static void
66 : fd_progcache_load_fork_slow( fd_progcache_t * cache,
67 : fd_funk_txn_xid_t const * xid,
68 117 : ulong epoch_slot0 ) {
69 117 : fd_funk_txn_xid_t next_xid = *xid;
70 117 : if( FD_UNLIKELY( next_xid.ul[0]<epoch_slot0 ) ) {
71 0 : FD_LOG_CRIT(( "fd_progcache_load_fork: attempted to load xid=%lu:%lu, which predates first slot of bank's epoch (epoch_slot0=%lu)",
72 0 : next_xid.ul[0], next_xid.ul[1], epoch_slot0 ));
73 0 : }
74 :
75 : /* Walk transaction graph, recovering from overruns on-the-fly */
76 117 : cache->fork_depth = 0UL;
77 :
78 117 : ulong txn_max = fd_funk_txn_pool_ele_max( cache->funk->txn_pool );
79 117 : ulong i;
80 171 : for( i=0UL; i<FD_PROGCACHE_DEPTH_MAX; i++ ) {
81 171 : fd_funk_txn_map_query_t query[1];
82 171 : fd_funk_txn_t const * candidate;
83 171 : fd_funk_txn_xid_t found_xid;
84 171 : ulong parent_idx;
85 171 : fd_funk_txn_xid_t parent_xid;
86 171 : retry:
87 : /* Speculatively look up transaction from map */
88 171 : for(;;) {
89 171 : int query_err = fd_funk_txn_map_query_try( cache->funk->txn_map, &next_xid, NULL, query, 0 );
90 171 : if( FD_UNLIKELY( query_err==FD_MAP_ERR_AGAIN ) ) {
91 : /* FIXME random backoff */
92 0 : FD_SPIN_PAUSE();
93 0 : continue;
94 0 : }
95 171 : if( query_err==FD_MAP_ERR_KEY ) goto done;
96 144 : if( FD_UNLIKELY( query_err!=FD_MAP_SUCCESS ) ) {
97 0 : FD_LOG_CRIT(( "fd_funk_txn_map_query_try failed: %i-%s", query_err, fd_map_strerror( query_err ) ));
98 0 : }
99 144 : break;
100 144 : }
101 :
102 : /* Lookup parent transaction while recovering from overruns
103 : FIXME This would be a lot easier if transactions specified
104 : parent by XID instead of by pointer ... */
105 144 : candidate = fd_funk_txn_map_query_ele_const( query );
106 144 : FD_COMPILER_MFENCE();
107 144 : do {
108 144 : found_xid = FD_VOLATILE_CONST( candidate->xid );
109 144 : parent_idx = fd_funk_txn_idx( FD_VOLATILE_CONST( candidate->parent_cidx ) );
110 144 : if( parent_idx<txn_max ) {
111 54 : FD_COMPILER_MFENCE();
112 54 : fd_funk_txn_t const * parent = &cache->funk->txn_pool->ele[ parent_idx ];
113 54 : parent_xid = FD_VOLATILE_CONST( parent->xid );
114 54 : FD_COMPILER_MFENCE();
115 54 : }
116 144 : parent_idx = fd_funk_txn_idx( FD_VOLATILE_CONST( candidate->parent_cidx ) );
117 144 : } while(0);
118 144 : FD_COMPILER_MFENCE();
119 :
120 : /* Verify speculative loads by ensuring txn still exists in map */
121 144 : if( FD_UNLIKELY( fd_funk_txn_map_query_test( query )!=FD_MAP_SUCCESS ) ) {
122 0 : FD_SPIN_PAUSE();
123 0 : goto retry;
124 0 : }
125 :
126 144 : if( FD_UNLIKELY( !fd_funk_txn_xid_eq( &found_xid, &next_xid ) ) ) {
127 0 : FD_LOG_CRIT(( "fd_progcache_load_fork_slow detected memory corruption: expected xid %lu:%lu at %p, found %lu:%lu",
128 0 : next_xid.ul[0], next_xid.ul[1],
129 0 : (void *)candidate,
130 0 : found_xid.ul[0], found_xid.ul[1] ));
131 0 : }
132 :
133 144 : cache->fork[ i ] = next_xid;
134 144 : if( fd_funk_txn_idx_is_null( parent_idx ) ||
135 144 : next_xid.ul[0]<epoch_slot0 ) {
136 : /* Reached root or fork graph node is from previous epoch */
137 90 : i++;
138 90 : break;
139 90 : }
140 54 : next_xid = parent_xid;
141 54 : }
142 :
143 117 : done:
144 117 : cache->fork_depth = i;
145 :
146 : /* Only include published/rooted records if they include at least one
147 : cache entry from the current epoch. */
148 117 : if( fd_funk_last_publish( cache->funk )->ul[0] >= epoch_slot0 &&
149 117 : cache->fork_depth < FD_PROGCACHE_DEPTH_MAX ) {
150 117 : fd_funk_txn_xid_set_root( &cache->fork[ cache->fork_depth++ ] );
151 117 : }
152 117 : }
153 :
154 : static inline void
155 : fd_progcache_load_fork( fd_progcache_t * cache,
156 : fd_funk_txn_xid_t const * xid,
157 219 : ulong epoch_slot0 ) {
158 : /* Skip if already on the correct fork */
159 219 : if( FD_LIKELY( (!!cache->fork_depth) & (!!fd_funk_txn_xid_eq( &cache->fork[ 0 ], xid ) ) ) ) return;
160 117 : cache->metrics->fork_switch_cnt++;
161 117 : fd_progcache_load_fork_slow( cache, xid, epoch_slot0 ); /* switch fork */
162 117 : }
163 :
164 : /* fd_progcache_query searches for a program cache entry on the current
165 : fork. Stops short of an epoch boundary. */
166 :
167 : static int
168 : fd_progcache_fork_has_xid( fd_progcache_t const * cache,
169 138 : fd_funk_txn_xid_t const * rec_xid ) {
170 : /* FIXME unroll this a little */
171 138 : ulong const fork_depth = cache->fork_depth;
172 240 : for( ulong i=0UL; i<fork_depth; i++ ) {
173 204 : if( fd_funk_txn_xid_eq( &cache->fork[i], rec_xid ) ) return 1;
174 204 : }
175 36 : return 0;
176 138 : }
177 :
178 : static int
179 : fd_progcache_search_chain( fd_progcache_t const * cache,
180 : ulong chain_idx,
181 : fd_funk_rec_key_t const * key,
182 : ulong epoch_slot0,
183 156 : fd_funk_rec_t ** out_rec ) {
184 156 : *out_rec = NULL;
185 :
186 156 : fd_funk_rec_map_shmem_t * shmap = cache->funk->rec_map->map;
187 156 : fd_funk_rec_map_shmem_private_chain_t const * chain_tbl = fd_funk_rec_map_shmem_private_chain_const( shmap, 0UL );
188 156 : fd_funk_rec_map_shmem_private_chain_t const * chain = chain_tbl + chain_idx;
189 156 : fd_funk_rec_t * rec_tbl = cache->funk->rec_pool->ele;
190 156 : ulong rec_max = fd_funk_rec_pool_ele_max( cache->funk->rec_pool );
191 156 : ulong ver_cnt = FD_VOLATILE_CONST( chain->ver_cnt );
192 156 : ulong root_slot = fd_funk_last_publish( cache->funk )->ul[0];
193 :
194 : /* Start a speculative transaction for the chain containing revisions
195 : of the program cache key we are looking for. */
196 156 : ulong cnt = fd_funk_rec_map_private_vcnt_cnt( ver_cnt );
197 156 : if( FD_UNLIKELY( fd_funk_rec_map_private_vcnt_ver( ver_cnt )&1 ) ) {
198 0 : return FD_MAP_ERR_AGAIN; /* chain is locked */
199 0 : }
200 156 : FD_COMPILER_MFENCE();
201 156 : uint ele_idx = chain->head_cidx;
202 :
203 : /* Walk the map chain, remember the best entry */
204 156 : fd_funk_rec_t * best = NULL;
205 156 : long best_slot = -1L;
206 342 : for( ulong i=0UL; i<cnt; i++, ele_idx=rec_tbl[ ele_idx ].map_next ) {
207 186 : fd_funk_rec_t * rec = &rec_tbl[ ele_idx ];
208 :
209 : /* Skip over unrelated records (hash collision) */
210 186 : if( FD_UNLIKELY( !fd_funk_rec_key_eq( rec->pair.key, key ) ) ) continue;
211 :
212 : /* Skip over records from an older epoch (FIXME could bail early
213 : here if the chain is ordered) */
214 186 : ulong found_slot = rec->pair.xid->ul[0];
215 186 : if( found_slot==ULONG_MAX ) found_slot = root_slot;
216 :
217 186 : if( FD_UNLIKELY( found_slot<epoch_slot0 ) ) continue;
218 :
219 : /* Skip over records that are older than what we already have */
220 177 : if( FD_UNLIKELY( (long)found_slot<best_slot ) ) continue;
221 :
222 : /* Confirm that record is part of the current fork
223 : FIXME this has bad performance / pointer-chasing */
224 138 : if( FD_UNLIKELY( !fd_progcache_fork_has_xid( cache, rec->pair.xid ) ) ) continue;
225 :
226 102 : best = rec;
227 102 : best_slot = (long)found_slot;
228 102 : if( FD_UNLIKELY( rec->map_next==ele_idx ) ) {
229 0 : FD_LOG_CRIT(( "fd_progcache_search_chain detected cycle" ));
230 0 : }
231 102 : if( rec->map_next > rec_max ) {
232 63 : if( FD_UNLIKELY( !fd_funk_rec_map_private_idx_is_null( rec->map_next ) ) ) {
233 0 : FD_LOG_CRIT(( "fd_progcache_search_chain detected memory corruption: rec->map_next %u is out of bounds (rec_max %lu)",
234 0 : rec->map_next, rec_max ));
235 0 : }
236 63 : }
237 102 : }
238 :
239 : /* Retry if we were overrun */
240 156 : if( FD_UNLIKELY( FD_VOLATILE_CONST( chain->ver_cnt )!=ver_cnt ) ) {
241 0 : return FD_MAP_ERR_AGAIN;
242 0 : }
243 :
244 156 : *out_rec = best;
245 156 : return FD_MAP_SUCCESS;
246 156 : }
247 :
248 : static fd_funk_rec_t *
249 : fd_progcache_query( fd_progcache_t * cache,
250 : fd_funk_txn_xid_t const * xid,
251 : fd_funk_rec_key_t const * key,
252 156 : ulong epoch_slot0 ) {
253 : /* Hash key to chain */
254 156 : fd_funk_xid_key_pair_t pair[1];
255 156 : fd_funk_txn_xid_copy( pair->xid, xid );
256 156 : fd_funk_rec_key_copy( pair->key, key );
257 156 : fd_funk_rec_map_t const * rec_map = cache->funk->rec_map;
258 156 : ulong hash = fd_funk_rec_map_key_hash( pair, rec_map->map->seed );
259 156 : ulong chain_idx = (hash & (rec_map->map->chain_cnt-1UL) );
260 :
261 : /* Traverse chain for candidate */
262 156 : fd_funk_rec_t * rec = NULL;
263 156 : for(;;) {
264 156 : int err = fd_progcache_search_chain( cache, chain_idx, key, epoch_slot0, &rec );
265 156 : if( FD_LIKELY( err==FD_MAP_SUCCESS ) ) break;
266 0 : FD_SPIN_PAUSE();
267 0 : fd_racesan_hook( "fd_progcache_query_wait" );
268 : /* FIXME backoff */
269 0 : }
270 :
271 156 : return rec;
272 156 : }
273 :
274 : fd_progcache_rec_t const *
275 : fd_progcache_peek( fd_progcache_t * cache,
276 : fd_funk_txn_xid_t const * xid,
277 : void const * prog_addr,
278 156 : ulong epoch_slot0 ) {
279 156 : if( FD_UNLIKELY( !cache || !cache->funk->shmem ) ) FD_LOG_CRIT(( "NULL progcache" ));
280 156 : fd_progcache_load_fork( cache, xid, epoch_slot0 );
281 156 : fd_funk_rec_key_t key[1]; memcpy( key->uc, prog_addr, 32UL );
282 156 : fd_funk_rec_t const * rec = fd_progcache_query( cache, xid, key, epoch_slot0 );
283 156 : if( FD_UNLIKELY( !rec ) ) return NULL;
284 :
285 99 : fd_progcache_rec_t const * entry = fd_funk_val_const( rec, fd_funk_wksp( cache->funk ) );
286 99 : if( entry->slot < epoch_slot0 ) entry = NULL;
287 :
288 99 : cache->metrics->hit_cnt += !!entry;
289 :
290 99 : return entry;
291 156 : }
292 :
293 : static void
294 : fd_funk_rec_push_tail( fd_funk_rec_t * rec_pool,
295 : fd_funk_rec_t * rec,
296 : uint * rec_head_idx,
297 66 : uint * rec_tail_idx ) {
298 66 : uint rec_idx = (uint)( rec - rec_pool );
299 66 : for(;;) {
300 :
301 : /* Doubly linked list append. Robust in the event of concurrent
302 : publishes. Iteration during publish not supported. Sequence:
303 : - Identify tail element
304 : - Set new element's prev and next pointers
305 : - Set tail element's next pointer
306 : - Set tail pointer */
307 :
308 66 : uint rec_prev_idx = FD_VOLATILE_CONST( *rec_tail_idx );
309 66 : rec->prev_idx = rec_prev_idx;
310 66 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
311 66 : FD_COMPILER_MFENCE();
312 :
313 66 : uint * next_idx_p;
314 66 : if( fd_funk_rec_idx_is_null( rec_prev_idx ) ) {
315 66 : next_idx_p = rec_head_idx;
316 66 : } else {
317 0 : next_idx_p = &rec_pool[ rec_prev_idx ].next_idx;
318 0 : }
319 :
320 66 : fd_racesan_hook( "fd_progcache_rec_push_tail_start" );
321 66 : if( FD_UNLIKELY( !__sync_bool_compare_and_swap( next_idx_p, FD_FUNK_REC_IDX_NULL, rec_idx ) ) ) {
322 : /* Another thread beat us to the punch */
323 0 : FD_SPIN_PAUSE();
324 0 : continue;
325 0 : }
326 :
327 66 : if( FD_UNLIKELY( !__sync_bool_compare_and_swap( rec_tail_idx, rec_prev_idx, rec_idx ) ) ) {
328 : /* This CAS is guaranteed to succeed if the previous CAS passed. */
329 0 : FD_LOG_CRIT(( "Irrecoverable data race encountered while appending to txn rec list (invariant violation?): cas(%p,%u,%u)",
330 0 : (void *)rec_tail_idx, rec_prev_idx, rec_idx ));
331 0 : }
332 :
333 66 : break;
334 66 : }
335 66 : }
336 :
337 : __attribute__((warn_unused_result))
338 : static int
339 : fd_progcache_push( fd_progcache_t * cache,
340 : fd_funk_txn_t * txn,
341 : fd_funk_rec_t * rec,
342 : void const * prog_addr,
343 78 : fd_funk_rec_t ** dup_rec ) {
344 78 : fd_funk_t * funk = cache->funk;
345 78 : *dup_rec = NULL;
346 :
347 : /* Phase 1: Determine record's xid-key pair */
348 :
349 78 : rec->tag = 0;
350 78 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
351 78 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
352 78 : memcpy( rec->pair.key, prog_addr, 32UL );
353 78 : if( FD_UNLIKELY( txn ) ) {
354 69 : fd_funk_txn_xid_copy( rec->pair.xid, &txn->xid );
355 69 : } else {
356 9 : fd_funk_txn_xid_set_root( rec->pair.xid );
357 9 : }
358 :
359 : /* Phase 2: Lock rec_map chain, entering critical section */
360 :
361 78 : struct {
362 78 : fd_funk_rec_map_txn_t txn[1];
363 78 : fd_funk_rec_map_txn_private_info_t info[1];
364 78 : } _map_txn;
365 78 : fd_funk_rec_map_txn_t * map_txn = fd_funk_rec_map_txn_init( _map_txn.txn, funk->rec_map, 1UL );
366 78 : fd_funk_rec_map_txn_add( map_txn, &rec->pair, 1 );
367 78 : int txn_err = fd_funk_rec_map_txn_try( map_txn, FD_MAP_FLAG_BLOCKING );
368 78 : if( FD_UNLIKELY( txn_err!=FD_MAP_SUCCESS ) ) {
369 0 : FD_LOG_CRIT(( "Failed to insert progcache record: cannot lock funk rec map chain: %i-%s", txn_err, fd_map_strerror( txn_err ) ));
370 0 : }
371 :
372 : /* Phase 3: Check if record exists */
373 :
374 78 : fd_funk_rec_map_query_t query[1];
375 78 : int query_err = fd_funk_rec_map_txn_query( funk->rec_map, &rec->pair, NULL, query, 0 );
376 78 : if( FD_UNLIKELY( query_err==FD_MAP_SUCCESS ) ) {
377 3 : fd_funk_rec_map_txn_test( map_txn );
378 3 : fd_funk_rec_map_txn_fini( map_txn );
379 3 : *dup_rec = query->ele;
380 3 : return 0; /* another thread was faster */
381 75 : } else if( FD_UNLIKELY( query_err!=FD_MAP_ERR_KEY ) ) {
382 0 : FD_LOG_CRIT(( "fd_funk_rec_map_txn_query failed: %i-%s", query_err, fd_map_strerror( query_err ) ));
383 0 : }
384 :
385 : /* Phase 4: Insert new record */
386 :
387 75 : int insert_err = fd_funk_rec_map_txn_insert( funk->rec_map, rec );
388 75 : if( FD_UNLIKELY( insert_err!=FD_MAP_SUCCESS ) ) {
389 0 : FD_LOG_CRIT(( "fd_funk_rec_map_txn_insert failed: %i-%s", insert_err, fd_map_strerror( insert_err ) ));
390 0 : }
391 :
392 : /* At this point, another thread could aggressively evict this entry.
393 : But this entry is not yet present in rec_map! This is why we hold
394 : a lock on the rec_map chain -- the rec_map_remove executed by the
395 : eviction will be sequenced after completion of phase 5. */
396 :
397 : /* Phase 5: Insert rec into rec_map */
398 :
399 75 : if( txn ) {
400 66 : fd_funk_rec_push_tail( funk->rec_pool->ele,
401 66 : rec,
402 66 : &txn->rec_head_idx,
403 66 : &txn->rec_tail_idx );
404 66 : }
405 :
406 : /* Phase 6: Finish rec_map transaction */
407 :
408 75 : int test_err = fd_funk_rec_map_txn_test( map_txn );
409 75 : if( FD_UNLIKELY( test_err!=FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "fd_funk_rec_map_txn_test failed: %i-%s", test_err, fd_map_strerror( test_err ) ));
410 75 : fd_funk_rec_map_txn_fini( map_txn );
411 75 : return 1;
412 75 : }
413 :
414 : #if FD_HAS_ATOMIC
415 :
416 : static int
417 69 : fd_progcache_txn_try_lock( fd_funk_txn_t * txn ) {
418 69 : for(;;) {
419 69 : ushort * lock = &txn->lock->value;
420 69 : ushort value = FD_VOLATILE_CONST( *lock );
421 69 : if( FD_UNLIKELY( value>=0xFFFE ) ) return 0; /* txn is write-locked */
422 69 : if( FD_LIKELY( FD_ATOMIC_CAS( lock, value, value+1 )==value ) ) {
423 69 : return 1; /* transaction now read-locked */
424 69 : }
425 69 : }
426 69 : }
427 :
428 : #else
429 :
430 : static int
431 : fd_progcache_txn_try_lock( fd_funk_txn_t * txn ) {
432 : ushort * lock = &txn->lock->value;
433 : ushort value = FD_VOLATILE_CONST( *lock );
434 : if( FD_UNLIKELY( value>=0xFFFE ) ) return 0; /* txn is write-locked */
435 : *lock = value + 1;
436 : return 1; /* transaction now read-locked */
437 : }
438 :
439 : #endif
440 :
441 : static void
442 78 : fd_progcache_txn_unlock( fd_funk_txn_t * txn ) {
443 78 : if( !txn ) return;
444 69 : fd_rwlock_unread( txn->lock );
445 69 : }
446 :
447 : /* fd_progcache_lock_best_txn picks a fork graph node close to
448 : target_slot and write locks it for program cache entry insertion.
449 :
450 : The cache entry should be placed as far up the fork graph as
451 : possible (so it can be shared across more downstream forks), but not
452 : too early (or it would cause non-determinism).
453 :
454 : Influenced by a number of things:
455 :
456 : - Program modification time (cannot predate the program modification)
457 : - Epoch boundaries (cannot span across epochs)
458 : - Transaction publishing (cannot create a cache entry at a txn that
459 : is in the process of being published) */
460 :
461 : static fd_funk_txn_t *
462 : fd_progcache_lock_best_txn( fd_progcache_t * cache,
463 45 : ulong target_slot ) {
464 :
465 45 : fd_funk_txn_xid_t last_publish[1];
466 45 : fd_funk_txn_xid_ld_atomic( last_publish, fd_funk_last_publish( cache->funk ) );
467 45 : if( target_slot <= last_publish->ul[0] &&
468 45 : !fd_funk_txn_xid_eq_root( last_publish ) ) {
469 9 : return NULL; /* publishing record immediately */
470 9 : }
471 :
472 : /* Scan fork graph for oldest node >= the target slot. */
473 36 : ulong target_xid_idx = ULONG_MAX;
474 36 : ulong fork_depth = cache->fork_depth;
475 96 : for( ulong xid_idx=0UL; xid_idx<fork_depth && cache->fork[ xid_idx ].ul[0]>=target_slot; xid_idx++ ) {
476 60 : target_xid_idx = xid_idx;
477 60 : }
478 36 : if( FD_UNLIKELY( target_xid_idx==ULONG_MAX ) ) FD_LOG_CRIT(( "no target xid idx found for slot %lu", target_slot ));
479 :
480 : /* Backtrack up to newer fork graph nodes (>= access slot)
481 : Very old slots could have been rooted at this point */
482 60 : do {
483 : /* Locate fork */
484 60 : fd_funk_txn_xid_t const * xid = &cache->fork[ target_xid_idx ];
485 :
486 : /* Speculatively query txn_map (recovering from ongoing rooting),
487 : and lock target transaction */
488 60 : for(;;) {
489 60 : fd_funk_txn_map_query_t query[1];
490 60 : int query_err = fd_funk_txn_map_query_try( cache->funk->txn_map, xid, NULL, query, 0 );
491 60 : if( FD_UNLIKELY( query_err==FD_MAP_ERR_AGAIN ) ) {
492 : /* FIXME random backoff */
493 0 : FD_SPIN_PAUSE();
494 0 : continue;
495 0 : }
496 60 : if( FD_LIKELY( query_err==FD_MAP_SUCCESS ) ) {
497 : /* Attempt to read-lock transaction */
498 36 : fd_funk_txn_t * txn = fd_funk_txn_map_query_ele( query );
499 36 : if( FD_LIKELY( fd_progcache_txn_try_lock( txn ) ) ) {
500 : /* Check for unlikely case we acquired a read-lock _after_ the
501 : transaction object was destroyed (ABA problem) */
502 36 : fd_funk_txn_xid_t found_xid[1];
503 36 : if( FD_UNLIKELY( !fd_funk_txn_xid_eq( fd_funk_txn_xid_ld_atomic( found_xid, &txn->xid ), xid ) ) ) {
504 0 : fd_progcache_txn_unlock( txn );
505 0 : break;
506 0 : }
507 36 : return txn;
508 36 : }
509 : /* currently being rooted */
510 36 : } else if( FD_UNLIKELY( query_err!=FD_MAP_ERR_KEY ) ) {
511 0 : FD_LOG_CRIT(( "fd_funk_txn_map_query_try failed (%i-%s)", query_err, fd_map_strerror( query_err ) ));
512 0 : }
513 24 : break;
514 60 : }
515 :
516 : /* Cannot insert at this fork graph node (already rooted, or
517 : currently being rooted), try one newer */
518 24 : target_xid_idx--;
519 24 : } while( target_xid_idx!=ULONG_MAX );
520 :
521 : /* There is no funk_txn in range [target_slot,load_slot] that we can
522 : create a cache entry at. */
523 0 : FD_LOG_CRIT(( "Could not find program cache fork graph node for target slot %lu", target_slot ));
524 0 : }
525 :
526 : /* account_xid_lower_bound tries to find the oldest XID at which the
527 : given record is exactly present. sample_xid is an arbitrary XID at
528 : which the given record is present. May return a newer XID, if the
529 : oldest XID cannot be determined exactly. */
530 :
531 : static fd_funk_txn_xid_t
532 : account_xid_lower_bound( fd_accdb_user_t * accdb,
533 : fd_accdb_ro_t const * record,
534 45 : fd_funk_txn_xid_t const * sample_xid ) {
535 45 : switch( record->ref->accdb_type ) {
536 45 : case FD_ACCDB_TYPE_V1: { /* possibly rooted */
537 45 : fd_funk_rec_t * rec = (fd_funk_rec_t *)record->ref->user_data;
538 45 : fd_funk_txn_xid_t res;
539 45 : fd_funk_txn_xid_ld_atomic( &res, rec->pair.xid );
540 45 : if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( &res ) ) ) {
541 9 : fd_funk_txn_xid_ld_atomic( &res, fd_funk_last_publish( fd_accdb_user_v1_funk( accdb ) ) );
542 9 : }
543 45 : return res;
544 0 : }
545 0 : case FD_ACCDB_TYPE_V2: { /* rooted */
546 0 : fd_funk_txn_xid_t res;
547 0 : fd_funk_txn_xid_ld_atomic( &res, fd_funk_last_publish( fd_accdb_user_v1_funk( accdb ) ) );
548 0 : return res;
549 0 : }
550 0 : default: /* unknown */
551 0 : return *sample_xid;
552 45 : }
553 45 : }
554 :
555 : static fd_progcache_rec_t const *
556 : fd_progcache_insert( fd_progcache_t * cache,
557 : fd_accdb_user_t * accdb,
558 : fd_funk_txn_xid_t const * load_xid,
559 : void const * prog_addr,
560 : fd_prog_load_env_t const * env,
561 51 : long slot_min ) {
562 :
563 : /* XID overview:
564 :
565 : - load_xid: tip of fork currently being executed
566 : - modify_xid: xid in which program was last modified / deployed
567 : - txn->xid: xid in which program cache entry is inserted
568 :
569 : slot(load_xid) > slot(entry_xid) >= slot(txn->xid) */
570 :
571 : /* Acquire reference to ELF binary data */
572 :
573 51 : fd_accdb_ro_t progdata[1];
574 51 : ulong elf_offset;
575 51 : if( FD_UNLIKELY( !fd_prog_load_elf( accdb, load_xid, progdata, prog_addr, &elf_offset ) ) ) {
576 6 : return NULL;
577 6 : }
578 :
579 45 : uchar const * bin = (uchar const *)fd_accdb_ref_data_const( progdata ) + elf_offset;
580 45 : ulong bin_sz = /* */fd_accdb_ref_data_sz ( progdata ) - elf_offset;
581 :
582 : /* Derive the slot in which the account was modified in */
583 :
584 45 : fd_funk_txn_xid_t modify_xid = account_xid_lower_bound( accdb, progdata, load_xid );
585 45 : ulong target_slot = modify_xid.ul[0];
586 :
587 : /* Prevent cache entry from crossing epoch boundary */
588 :
589 45 : target_slot = fd_ulong_max( target_slot, env->epoch_slot0 );
590 :
591 : /* Prevent cache entry from shadowing invalidation */
592 :
593 45 : target_slot = (ulong)fd_long_max( (long)target_slot, slot_min );
594 :
595 : /* Allocate a funk_rec */
596 :
597 45 : fd_funk_t * funk = cache->funk;
598 45 : fd_funk_rec_t * funk_rec = fd_funk_rec_pool_acquire( funk->rec_pool, NULL, 0, NULL );
599 45 : if( FD_UNLIKELY( !funk_rec ) ) {
600 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_funk_rec_pool_acquire failed (rec_max=%lu)",
601 0 : fd_funk_rec_pool_ele_max( funk->rec_pool ) ));
602 0 : }
603 45 : memset( funk_rec, 0, sizeof(fd_funk_rec_t) );
604 45 : fd_funk_val_init( funk_rec );
605 :
606 : /* Pick and lock a txn in which cache entry is created at */
607 :
608 45 : fd_funk_txn_t * txn = fd_progcache_lock_best_txn( cache, target_slot );
609 :
610 : /* Load program */
611 :
612 45 : fd_features_t const * features = env->features;
613 45 : ulong const load_slot = env->slot;
614 45 : fd_prog_versions_t versions = fd_prog_versions( features, load_slot );
615 45 : fd_sbpf_loader_config_t config = {
616 45 : .sbpf_min_version = versions.min_sbpf_version,
617 45 : .sbpf_max_version = versions.max_sbpf_version,
618 45 : };
619 45 : fd_sbpf_elf_info_t elf_info[1];
620 :
621 45 : fd_progcache_rec_t * rec = NULL;
622 45 : if( FD_LIKELY( fd_sbpf_elf_peek( elf_info, bin, bin_sz, &config )==FD_SBPF_ELF_SUCCESS ) ) {
623 :
624 45 : fd_funk_t * funk = cache->funk;
625 45 : ulong rec_align = fd_progcache_rec_align();
626 45 : ulong rec_footprint = fd_progcache_rec_footprint( elf_info );
627 :
628 45 : void * rec_mem = fd_funk_val_truncate( funk_rec, funk->alloc, funk->wksp, rec_align, rec_footprint, NULL );
629 45 : if( FD_UNLIKELY( !rec_mem ) ) {
630 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_alloc_malloc failed (requested align=%lu sz=%lu)",
631 0 : rec_align, rec_footprint ));
632 0 : }
633 :
634 45 : rec = fd_progcache_rec_new( rec_mem, elf_info, &config, load_slot, features, bin, bin_sz, cache->scratch, cache->scratch_sz );
635 45 : if( !rec ) {
636 3 : fd_funk_val_flush( funk_rec, funk->alloc, funk->wksp );
637 3 : }
638 :
639 45 : }
640 :
641 45 : fd_accdb_close_ro( accdb, progdata );
642 : /* invalidates bin pointer */
643 :
644 : /* Convert to tombstone if load failed */
645 :
646 45 : if( !rec ) { /* load fail */
647 3 : void * rec_mem = fd_funk_val_truncate( funk_rec, funk->alloc, funk->wksp, fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ), NULL );
648 3 : if( FD_UNLIKELY( !rec_mem ) ) {
649 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_alloc_malloc failed (requested align=%lu sz=%lu)",
650 0 : fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ) ));
651 0 : }
652 3 : rec = fd_progcache_rec_new_nx( rec_mem, load_slot );
653 3 : }
654 :
655 : /* Publish cache entry to funk index */
656 :
657 45 : fd_funk_rec_t * dup_rec = NULL;
658 45 : int push_ok = fd_progcache_push( cache, txn, funk_rec, prog_addr, &dup_rec );
659 :
660 : /* Done modifying transaction */
661 :
662 45 : fd_progcache_txn_unlock( txn );
663 :
664 : /* If another thread was faster publishing the same record, use that
665 : one instead. FIXME POSSIBLE RACE CONDITION WHERE THE OTHER REC IS
666 : EVICTED AFTER PEEK? */
667 :
668 45 : if( !push_ok ) {
669 0 : FD_TEST( dup_rec );
670 0 : fd_funk_val_flush( funk_rec, funk->alloc, funk->wksp );
671 0 : fd_funk_rec_pool_release( funk->rec_pool, funk_rec, 1 );
672 0 : cache->metrics->dup_insert_cnt++;
673 0 : return fd_funk_val_const( dup_rec, funk->wksp );
674 0 : }
675 :
676 45 : cache->metrics->fill_cnt++;
677 45 : cache->metrics->fill_tot_sz += rec->rodata_sz;
678 :
679 45 : return rec;
680 45 : }
681 :
682 : fd_progcache_rec_t const *
683 : fd_progcache_pull( fd_progcache_t * cache,
684 : fd_accdb_user_t * accdb,
685 : fd_funk_txn_xid_t const * xid,
686 : void const * prog_addr,
687 63 : fd_prog_load_env_t const * env ) {
688 63 : if( FD_UNLIKELY( !cache || !cache->funk->shmem ) ) FD_LOG_CRIT(( "NULL progcache" ));
689 63 : fd_progcache_load_fork( cache, xid, env->epoch_slot0 );
690 :
691 63 : fd_progcache_rec_t const * found_rec = fd_progcache_peek( cache, xid, prog_addr, env->epoch_slot0 );
692 63 : long slot_min = -1L;
693 63 : if( !found_rec ) goto miss;
694 :
695 : /* Cache invalidation, update next slot */
696 21 : if( found_rec->invalidate ) {
697 9 : slot_min = (long)found_rec->slot+1L;
698 9 : if( FD_UNLIKELY( xid->ul[0] < (ulong)slot_min ) ) {
699 0 : FD_LOG_CRIT(( "Program cache entry %016lx%016lx%016lx%016lx invalidated at slot %lu but loaded at slot %lu",
700 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr ) ),
701 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr+ 8 ) ),
702 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr+16 ) ),
703 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr+24 ) ),
704 0 : found_rec->slot,
705 0 : xid->ul[0] ));
706 0 : }
707 9 : goto miss;
708 9 : }
709 :
710 : /* Passed all checks */
711 12 : cache->metrics->hit_cnt++;
712 12 : cache->metrics->hit_tot_sz += found_rec->rodata_sz;
713 12 : return found_rec;
714 :
715 51 : miss:
716 51 : cache->metrics->miss_cnt++;
717 51 : return fd_progcache_insert( cache, accdb, xid, prog_addr, env, slot_min );
718 21 : }
719 :
720 : fd_progcache_rec_t const *
721 : fd_progcache_invalidate( fd_progcache_t * cache,
722 : fd_funk_txn_xid_t const * xid,
723 : void const * prog_addr,
724 33 : ulong slot ) {
725 33 : fd_funk_t * funk = cache->funk;
726 :
727 33 : if( FD_UNLIKELY( !cache || !funk->shmem ) ) FD_LOG_CRIT(( "NULL progcache" ));
728 :
729 : /* Resolve the fork graph node at xid. Due to (unrelated) ongoing
730 : root operations, recover from temporary lock issues. */
731 :
732 33 : fd_funk_txn_t * txn = NULL;
733 33 : for(;;) {
734 33 : fd_funk_txn_map_query_t query[1];
735 33 : int query_err = fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 );
736 33 : if( FD_UNLIKELY( query_err==FD_MAP_ERR_AGAIN ) ) {
737 : /* FIXME random backoff */
738 0 : FD_SPIN_PAUSE();
739 0 : continue;
740 0 : }
741 33 : if( FD_UNLIKELY( query_err ) ) {
742 0 : FD_LOG_CRIT(( "fd_progcache_invalidate(xid=%lu:%lu) failed: fd_funk_txn_map_query_try returned (%i-%s)",
743 0 : xid->ul[0], xid->ul[1], query_err, fd_map_strerror( query_err ) ));
744 0 : }
745 33 : txn = fd_funk_txn_map_query_ele( query );
746 33 : break;
747 33 : }
748 :
749 : /* Select a fork node to create invalidate record in
750 : Do not create invalidation records at the funk root */
751 :
752 33 : if( FD_UNLIKELY( !fd_progcache_txn_try_lock( txn ) ) ) {
753 0 : FD_LOG_CRIT(( "fd_progcache_invalidate(xid=%lu,...) failed: txn is write-locked", xid->ul[0] ));
754 0 : }
755 :
756 : /* Allocate a funk_rec */
757 :
758 33 : fd_funk_rec_t * funk_rec = fd_funk_rec_pool_acquire( funk->rec_pool, NULL, 0, NULL );
759 33 : if( FD_UNLIKELY( !funk_rec ) ) {
760 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_funk_rec_pool_acquire failed (rec_max=%lu)",
761 0 : fd_funk_rec_pool_ele_max( funk->rec_pool ) ));
762 0 : }
763 33 : memset( funk_rec, 0, sizeof(fd_funk_rec_t) );
764 33 : fd_funk_val_init( funk_rec );
765 :
766 : /* Create a tombstone */
767 :
768 33 : void * rec_mem = fd_funk_val_truncate( funk_rec, funk->alloc, funk->wksp, fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ), NULL );
769 33 : if( FD_UNLIKELY( !rec_mem ) ) {
770 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_alloc_malloc failed (requested align=%lu sz=%lu)",
771 0 : fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ) ));
772 0 : }
773 33 : fd_progcache_rec_t * rec = fd_progcache_rec_new_nx( rec_mem, slot );
774 33 : rec->invalidate = 1;
775 :
776 : /* Publish cache entry to funk index */
777 :
778 33 : fd_funk_rec_t * dup_rec = NULL;
779 33 : int push_ok = fd_progcache_push( cache, txn, funk_rec, prog_addr, &dup_rec );
780 :
781 : /* Done modifying transaction */
782 :
783 33 : fd_progcache_txn_unlock( txn );
784 :
785 : /* If another thread was faster publishing the same record, use that
786 : one instead. FIXME POSSIBLE RACE CONDITION WHERE THE OTHER REC IS
787 : EVICTED AFTER PEEK? */
788 :
789 33 : if( !push_ok ) {
790 3 : FD_TEST( dup_rec );
791 3 : fd_funk_val_flush( funk_rec, funk->alloc, funk->wksp );
792 3 : fd_funk_rec_pool_release( funk->rec_pool, funk_rec, 1 );
793 3 : cache->metrics->dup_insert_cnt++;
794 3 : return fd_funk_val_const( dup_rec, funk->wksp );
795 3 : }
796 :
797 30 : cache->metrics->invalidate_cnt++;
798 :
799 30 : return rec;
800 33 : }
|
