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 51 : ulong scratch_sz ) {
15 51 : if( FD_UNLIKELY( !ljoin ) ) {
16 0 : FD_LOG_WARNING(( "NULL ljoin" ));
17 0 : return NULL;
18 0 : }
19 51 : if( FD_UNLIKELY( !shfunk ) ) {
20 0 : FD_LOG_WARNING(( "NULL shfunk" ));
21 0 : return NULL;
22 0 : }
23 51 : if( FD_LIKELY( scratch_sz ) ) {
24 51 : if( FD_UNLIKELY( !scratch ) ) {
25 0 : FD_LOG_WARNING(( "NULL scratch" ));
26 0 : return NULL;
27 0 : }
28 51 : 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 51 : }
33 51 : memset( ljoin, 0, sizeof(fd_progcache_t) );
34 51 : if( FD_UNLIKELY( !fd_funk_join( ljoin->funk, shfunk ) ) ) return NULL;
35 :
36 51 : ljoin->metrics = &fd_progcache_metrics_default;
37 51 : ljoin->scratch = scratch;
38 51 : ljoin->scratch_sz = scratch_sz;
39 :
40 51 : return ljoin;
41 51 : }
42 :
43 : void *
44 : fd_progcache_leave( fd_progcache_t * cache,
45 48 : void ** opt_shfunk ) {
46 48 : if( FD_UNLIKELY( !cache ) ) {
47 0 : FD_LOG_WARNING(( "NULL cache" ));
48 0 : return NULL;
49 0 : }
50 48 : if( FD_UNLIKELY( !fd_funk_leave( cache->funk, opt_shfunk ) ) ) return NULL;
51 48 : cache->scratch = NULL;
52 48 : cache->scratch_sz = 0UL;
53 48 : return cache;
54 48 : }
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 105 : ulong epoch_slot0 ) {
69 105 : fd_funk_txn_xid_t next_xid = *xid;
70 105 : 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 105 : cache->fork_depth = 0UL;
77 :
78 105 : ulong txn_max = fd_funk_txn_pool_ele_max( cache->funk->txn_pool );
79 105 : ulong i;
80 159 : for( i=0UL; i<FD_PROGCACHE_DEPTH_MAX; i++ ) {
81 159 : fd_funk_txn_map_query_t query[1];
82 159 : fd_funk_txn_t const * candidate;
83 159 : fd_funk_txn_xid_t found_xid;
84 159 : ulong parent_idx;
85 159 : fd_funk_txn_xid_t parent_xid;
86 159 : retry:
87 : /* Speculatively look up transaction from map */
88 159 : for(;;) {
89 159 : int query_err = fd_funk_txn_map_query_try( cache->funk->txn_map, &next_xid, NULL, query, 0 );
90 159 : if( FD_UNLIKELY( query_err==FD_MAP_ERR_AGAIN ) ) {
91 : /* FIXME random backoff */
92 0 : FD_SPIN_PAUSE();
93 0 : continue;
94 0 : }
95 159 : 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 105 : done:
144 105 : 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 105 : if( fd_funk_last_publish( cache->funk )->ul[0] >= epoch_slot0 &&
149 105 : cache->fork_depth < FD_PROGCACHE_DEPTH_MAX ) {
150 105 : fd_funk_txn_xid_set_root( &cache->fork[ cache->fork_depth++ ] );
151 105 : }
152 105 : }
153 :
154 : static inline void
155 : fd_progcache_load_fork( fd_progcache_t * cache,
156 : fd_funk_txn_xid_t const * xid,
157 207 : ulong epoch_slot0 ) {
158 : /* Skip if already on the correct fork */
159 207 : if( FD_LIKELY( (!!cache->fork_depth) & (!!fd_funk_txn_xid_eq( &cache->fork[ 0 ], xid ) ) ) ) return;
160 105 : cache->metrics->fork_switch_cnt++;
161 105 : fd_progcache_load_fork_slow( cache, xid, epoch_slot0 ); /* switch fork */
162 105 : }
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 132 : fd_funk_txn_xid_t const * rec_xid ) {
170 : /* FIXME unroll this a little */
171 132 : ulong const fork_depth = cache->fork_depth;
172 234 : for( ulong i=0UL; i<fork_depth; i++ ) {
173 198 : if( fd_funk_txn_xid_eq( &cache->fork[i], rec_xid ) ) return 1;
174 198 : }
175 36 : return 0;
176 132 : }
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 150 : fd_funk_rec_t ** out_rec ) {
184 150 : *out_rec = NULL;
185 :
186 150 : fd_funk_rec_map_shmem_t * shmap = cache->funk->rec_map->map;
187 150 : fd_funk_rec_map_shmem_private_chain_t const * chain_tbl = fd_funk_rec_map_shmem_private_chain_const( shmap, 0UL );
188 150 : fd_funk_rec_map_shmem_private_chain_t const * chain = chain_tbl + chain_idx;
189 150 : fd_funk_rec_t * rec_tbl = cache->funk->rec_pool->ele;
190 150 : ulong rec_max = fd_funk_rec_pool_ele_max( cache->funk->rec_pool );
191 150 : ulong ver_cnt = FD_VOLATILE_CONST( chain->ver_cnt );
192 150 : 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 150 : ulong cnt = fd_funk_rec_map_private_vcnt_cnt( ver_cnt );
197 150 : 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 150 : FD_COMPILER_MFENCE();
201 150 : uint ele_idx = chain->head_cidx;
202 :
203 : /* Walk the map chain, remember the best entry */
204 150 : fd_funk_rec_t * best = NULL;
205 150 : long best_slot = -1L;
206 330 : for( ulong i=0UL; i<cnt; i++, ele_idx=rec_tbl[ ele_idx ].map_next ) {
207 180 : fd_funk_rec_t * rec = &rec_tbl[ ele_idx ];
208 :
209 : /* Skip over unrelated records (hash collision) */
210 180 : 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 180 : ulong found_slot = rec->pair.xid->ul[0];
215 180 : if( found_slot==ULONG_MAX ) found_slot = root_slot;
216 :
217 180 : if( FD_UNLIKELY( found_slot<epoch_slot0 ) ) continue;
218 :
219 : /* Skip over records that are older than what we already have */
220 171 : 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 132 : if( FD_UNLIKELY( !fd_progcache_fork_has_xid( cache, rec->pair.xid ) ) ) continue;
225 :
226 96 : best = rec;
227 96 : best_slot = (long)found_slot;
228 96 : if( FD_UNLIKELY( rec->map_next==ele_idx ) ) {
229 0 : FD_LOG_CRIT(( "fd_progcache_search_chain detected cycle" ));
230 0 : }
231 96 : if( rec->map_next > rec_max ) {
232 57 : 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 57 : }
237 96 : }
238 :
239 : /* Retry if we were overrun */
240 150 : if( FD_UNLIKELY( FD_VOLATILE_CONST( chain->ver_cnt )!=ver_cnt ) ) {
241 0 : return FD_MAP_ERR_AGAIN;
242 0 : }
243 :
244 150 : *out_rec = best;
245 150 : return FD_MAP_SUCCESS;
246 150 : }
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 150 : ulong epoch_slot0 ) {
253 : /* Hash key to chain */
254 150 : fd_funk_xid_key_pair_t pair[1];
255 150 : fd_funk_txn_xid_copy( pair->xid, xid );
256 150 : fd_funk_rec_key_copy( pair->key, key );
257 150 : fd_funk_rec_map_t const * rec_map = cache->funk->rec_map;
258 150 : ulong hash = fd_funk_rec_map_key_hash( pair, rec_map->map->seed );
259 150 : ulong chain_idx = (hash & (rec_map->map->chain_cnt-1UL) );
260 :
261 : /* Traverse chain for candidate */
262 150 : fd_funk_rec_t * rec = NULL;
263 150 : for(;;) {
264 150 : int err = fd_progcache_search_chain( cache, chain_idx, key, epoch_slot0, &rec );
265 150 : 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 150 : return rec;
272 150 : }
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 150 : ulong epoch_slot0 ) {
279 150 : if( FD_UNLIKELY( !cache || !cache->funk->shmem ) ) FD_LOG_CRIT(( "NULL progcache" ));
280 150 : fd_progcache_load_fork( cache, xid, epoch_slot0 );
281 150 : fd_funk_rec_key_t key[1]; memcpy( key->uc, prog_addr, 32UL );
282 150 : fd_funk_rec_t const * rec = fd_progcache_query( cache, xid, key, epoch_slot0 );
283 150 : if( FD_UNLIKELY( !rec ) ) return NULL;
284 :
285 93 : fd_progcache_rec_t const * entry = fd_funk_val_const( rec, fd_funk_wksp( cache->funk ) );
286 93 : if( entry->slot < epoch_slot0 ) entry = NULL;
287 :
288 93 : cache->metrics->hit_cnt += !!entry;
289 :
290 93 : return entry;
291 150 : }
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: canont 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 (>= program update slot) */
473 36 : ulong target_xid_idx;
474 36 : ulong fork_depth = cache->fork_depth;
475 36 : for( target_xid_idx=0UL; target_xid_idx<fork_depth; target_xid_idx++ ) {
476 36 : if( cache->fork[ target_xid_idx ].ul[0]<=target_slot ) break;
477 36 : }
478 :
479 : /* Backtrack up to newer fork graph nodes (>= access slot)
480 : Very old slots could have been rooted at this point */
481 36 : do {
482 : /* Locate fork */
483 36 : fd_funk_txn_xid_t const * xid = &cache->fork[ target_xid_idx ];
484 :
485 : /* Speculatively query txn_map (recovering from ongoing rooting),
486 : and lock target transaction */
487 36 : for(;;) {
488 36 : fd_funk_txn_map_query_t query[1];
489 36 : int query_err = fd_funk_txn_map_query_try( cache->funk->txn_map, xid, NULL, query, 0 );
490 36 : if( FD_UNLIKELY( query_err==FD_MAP_ERR_AGAIN ) ) {
491 : /* FIXME random backoff */
492 0 : FD_SPIN_PAUSE();
493 0 : continue;
494 0 : }
495 36 : if( FD_LIKELY( query_err==FD_MAP_SUCCESS ) ) {
496 : /* Attempt to read-lock transaction */
497 36 : fd_funk_txn_t * txn = fd_funk_txn_map_query_ele( query );
498 36 : if( FD_LIKELY( fd_progcache_txn_try_lock( txn ) ) ) {
499 : /* Check for unlikely case we acquired a read-lock _after_ the
500 : transaction object was destroyed (ABA problem) */
501 36 : fd_funk_txn_xid_t found_xid[1];
502 36 : if( FD_UNLIKELY( !fd_funk_txn_xid_eq( fd_funk_txn_xid_ld_atomic( found_xid, &txn->xid ), xid ) ) ) {
503 0 : fd_progcache_txn_unlock( txn );
504 0 : break;
505 0 : }
506 36 : return txn;
507 36 : }
508 : /* currently being rooted */
509 36 : } else if( FD_UNLIKELY( query_err!=FD_MAP_ERR_KEY ) ) {
510 0 : FD_LOG_CRIT(( "fd_funk_txn_map_query_try failed (%i-%s)", query_err, fd_map_strerror( query_err ) ));
511 0 : }
512 0 : break;
513 36 : }
514 :
515 : /* Cannot insert at this fork graph node (already rooted, or
516 : currently being rooted), try one newer */
517 0 : target_xid_idx--;
518 0 : } while( target_xid_idx!=ULONG_MAX );
519 :
520 : /* There is no funk_txn in range [target_slot,load_slot] that we can
521 : create a cache entry at. */
522 0 : FD_LOG_CRIT(( "Could not find program cache fork graph node for target slot %lu", target_slot ));
523 0 : }
524 :
525 : /* account_xid_lower_bound tries to find the oldest XID at which the
526 : given record is exactly present. sample_xid is an arbitrary XID at
527 : which the given record is present. May return a newer XID, if the
528 : oldest XID cannot be determined exactly. */
529 :
530 : static fd_funk_txn_xid_t
531 : account_xid_lower_bound( fd_accdb_user_t * accdb,
532 : fd_accdb_ro_t const * record,
533 45 : fd_funk_txn_xid_t const * sample_xid ) {
534 45 : switch( record->ref->accdb_type ) {
535 45 : case FD_ACCDB_TYPE_V1: { /* possibly rooted */
536 45 : fd_funk_rec_t * rec = (fd_funk_rec_t *)record->ref->user_data;
537 45 : fd_funk_txn_xid_t res;
538 45 : fd_funk_txn_xid_ld_atomic( &res, rec->pair.xid );
539 45 : if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( &res ) ) ) {
540 9 : fd_funk_txn_xid_ld_atomic( &res, fd_funk_last_publish( fd_accdb_user_v1_funk( accdb ) ) );
541 9 : }
542 45 : return res;
543 0 : }
544 0 : case FD_ACCDB_TYPE_V2: { /* rooted */
545 0 : fd_funk_txn_xid_t res;
546 0 : fd_funk_txn_xid_ld_atomic( &res, fd_funk_last_publish( fd_accdb_user_v1_funk( accdb ) ) );
547 0 : return res;
548 0 : }
549 0 : default: /* unknown */
550 0 : return *sample_xid;
551 45 : }
552 45 : }
553 :
554 : static fd_progcache_rec_t const *
555 : fd_progcache_insert( fd_progcache_t * cache,
556 : fd_accdb_user_t * accdb,
557 : fd_funk_txn_xid_t const * load_xid,
558 : void const * prog_addr,
559 : fd_prog_load_env_t const * env,
560 51 : long slot_min ) {
561 :
562 : /* XID overview:
563 :
564 : - load_xid: tip of fork currently being executed
565 : - modify_xid: xid in which program was last modified / deployed
566 : - txn->xid: xid in which program cache entry is inserted
567 :
568 : slot(load_xid) > slot(entry_xid) >= slot(txn->xid) */
569 :
570 : /* Acquire reference to ELF binary data */
571 :
572 51 : fd_accdb_ro_t progdata[1];
573 51 : ulong elf_offset;
574 51 : if( FD_UNLIKELY( !fd_prog_load_elf( accdb, load_xid, progdata, prog_addr, &elf_offset ) ) ) {
575 6 : return NULL;
576 6 : }
577 :
578 45 : uchar const * bin = (uchar const *)fd_accdb_ref_data_const( progdata ) + elf_offset;
579 45 : ulong bin_sz = /* */fd_accdb_ref_data_sz ( progdata ) - elf_offset;
580 :
581 : /* Derive the slot in which the account was modified in */
582 :
583 45 : fd_funk_txn_xid_t modify_xid = account_xid_lower_bound( accdb, progdata, load_xid );
584 45 : ulong target_slot = modify_xid.ul[0];
585 :
586 : /* Prevent cache entry from crossing epoch boundary */
587 :
588 45 : target_slot = fd_ulong_max( target_slot, env->epoch_slot0 );
589 :
590 : /* Prevent cache entry from shadowing invalidation */
591 :
592 45 : target_slot = (ulong)fd_long_max( (long)target_slot, slot_min );
593 :
594 : /* Allocate a funk_rec */
595 :
596 45 : fd_funk_t * funk = cache->funk;
597 45 : fd_funk_rec_t * funk_rec = fd_funk_rec_pool_acquire( funk->rec_pool, NULL, 0, NULL );
598 45 : if( FD_UNLIKELY( !funk_rec ) ) {
599 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_funk_rec_pool_acquire failed (rec_max=%lu)",
600 0 : fd_funk_rec_pool_ele_max( funk->rec_pool ) ));
601 0 : }
602 45 : memset( funk_rec, 0, sizeof(fd_funk_rec_t) );
603 45 : fd_funk_val_init( funk_rec );
604 :
605 : /* Pick and lock a txn in which cache entry is created at */
606 :
607 45 : fd_funk_txn_t * txn = fd_progcache_lock_best_txn( cache, target_slot );
608 :
609 : /* Load program */
610 :
611 45 : fd_features_t const * features = env->features;
612 45 : ulong const load_slot = env->slot;
613 45 : fd_prog_versions_t versions = fd_prog_versions( features, load_slot );
614 45 : fd_sbpf_loader_config_t config = {
615 45 : .sbpf_min_version = versions.min_sbpf_version,
616 45 : .sbpf_max_version = versions.max_sbpf_version,
617 45 : };
618 45 : fd_sbpf_elf_info_t elf_info[1];
619 :
620 45 : fd_progcache_rec_t * rec = NULL;
621 45 : if( FD_LIKELY( fd_sbpf_elf_peek( elf_info, bin, bin_sz, &config )==FD_SBPF_ELF_SUCCESS ) ) {
622 :
623 45 : fd_funk_t * funk = cache->funk;
624 45 : ulong rec_align = fd_progcache_rec_align();
625 45 : ulong rec_footprint = fd_progcache_rec_footprint( elf_info );
626 :
627 45 : void * rec_mem = fd_funk_val_truncate( funk_rec, funk->alloc, funk->wksp, rec_align, rec_footprint, NULL );
628 45 : if( FD_UNLIKELY( !rec_mem ) ) {
629 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_alloc_malloc failed (requested align=%lu sz=%lu)",
630 0 : rec_align, rec_footprint ));
631 0 : }
632 :
633 45 : rec = fd_progcache_rec_new( rec_mem, elf_info, &config, load_slot, features, bin, bin_sz, cache->scratch, cache->scratch_sz );
634 45 : if( !rec ) {
635 3 : fd_funk_val_flush( funk_rec, funk->alloc, funk->wksp );
636 3 : }
637 :
638 45 : }
639 :
640 45 : fd_accdb_close_ro( accdb, progdata );
641 : /* invalidates bin pointer */
642 :
643 : /* Convert to tombstone if load failed */
644 :
645 45 : if( !rec ) { /* load fail */
646 3 : void * rec_mem = fd_funk_val_truncate( funk_rec, funk->alloc, funk->wksp, fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ), NULL );
647 3 : if( FD_UNLIKELY( !rec_mem ) ) {
648 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_alloc_malloc failed (requested align=%lu sz=%lu)",
649 0 : fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ) ));
650 0 : }
651 3 : rec = fd_progcache_rec_new_nx( rec_mem, load_slot );
652 3 : }
653 :
654 : /* Publish cache entry to funk index */
655 :
656 45 : fd_funk_rec_t * dup_rec = NULL;
657 45 : int push_ok = fd_progcache_push( cache, txn, funk_rec, prog_addr, &dup_rec );
658 :
659 : /* Done modifying transaction */
660 :
661 45 : fd_progcache_txn_unlock( txn );
662 :
663 : /* If another thread was faster publishing the same record, use that
664 : one instead. FIXME POSSIBLE RACE CONDITION WHERE THE OTHER REC IS
665 : EVICTED AFTER PEEK? */
666 :
667 45 : if( !push_ok ) {
668 0 : FD_TEST( dup_rec );
669 0 : fd_funk_val_flush( funk_rec, funk->alloc, funk->wksp );
670 0 : fd_funk_rec_pool_release( funk->rec_pool, funk_rec, 1 );
671 0 : cache->metrics->dup_insert_cnt++;
672 0 : return fd_funk_val_const( dup_rec, funk->wksp );
673 0 : }
674 :
675 45 : cache->metrics->fill_cnt++;
676 45 : cache->metrics->fill_tot_sz += rec->rodata_sz;
677 :
678 45 : return rec;
679 45 : }
680 :
681 : fd_progcache_rec_t const *
682 : fd_progcache_pull( fd_progcache_t * cache,
683 : fd_accdb_user_t * accdb,
684 : fd_funk_txn_xid_t const * xid,
685 : void const * prog_addr,
686 57 : fd_prog_load_env_t const * env ) {
687 57 : if( FD_UNLIKELY( !cache || !cache->funk->shmem ) ) FD_LOG_CRIT(( "NULL progcache" ));
688 57 : fd_progcache_load_fork( cache, xid, env->epoch_slot0 );
689 :
690 57 : fd_progcache_rec_t const * found_rec = fd_progcache_peek( cache, xid, prog_addr, env->epoch_slot0 );
691 57 : long slot_min = -1L;
692 57 : if( !found_rec ) goto miss;
693 :
694 : /* Cache invalidation, update next slot */
695 15 : if( found_rec->invalidate ) {
696 9 : slot_min = (long)found_rec->slot+1L;
697 9 : if( FD_UNLIKELY( xid->ul[0] < (ulong)slot_min ) ) {
698 0 : FD_LOG_CRIT(( "Program cache entry %016lx%016lx%016lx%016lx invalidated at slot %lu but loaded at slot %lu",
699 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr ) ),
700 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr+ 8 ) ),
701 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr+16 ) ),
702 0 : fd_ulong_bswap( FD_LOAD( ulong, (uchar const *)prog_addr+24 ) ),
703 0 : found_rec->slot,
704 0 : xid->ul[0] ));
705 0 : }
706 9 : goto miss;
707 9 : }
708 :
709 : /* Passed all checks */
710 6 : cache->metrics->hit_cnt++;
711 6 : cache->metrics->hit_tot_sz += found_rec->rodata_sz;
712 6 : return found_rec;
713 :
714 51 : miss:
715 51 : cache->metrics->miss_cnt++;
716 51 : return fd_progcache_insert( cache, accdb, xid, prog_addr, env, slot_min );
717 15 : }
718 :
719 : fd_progcache_rec_t const *
720 : fd_progcache_invalidate( fd_progcache_t * cache,
721 : fd_funk_txn_xid_t const * xid,
722 : void const * prog_addr,
723 33 : ulong slot ) {
724 33 : fd_funk_t * funk = cache->funk;
725 :
726 33 : if( FD_UNLIKELY( !cache || !funk->shmem ) ) FD_LOG_CRIT(( "NULL progcache" ));
727 :
728 : /* Resolve the fork graph node at xid. Due to (unrelated) ongoing
729 : root operations, recover from temporary lock issues. */
730 :
731 33 : fd_funk_txn_t * txn = NULL;
732 33 : for(;;) {
733 33 : fd_funk_txn_map_query_t query[1];
734 33 : int query_err = fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 );
735 33 : if( FD_UNLIKELY( query_err==FD_MAP_ERR_AGAIN ) ) {
736 : /* FIXME random backoff */
737 0 : FD_SPIN_PAUSE();
738 0 : continue;
739 0 : }
740 33 : if( FD_UNLIKELY( query_err ) ) {
741 0 : FD_LOG_CRIT(( "fd_progcache_invalidate(xid=%lu:%lu) failed: fd_funk_txn_map_query_try returned (%i-%s)",
742 0 : xid->ul[0], xid->ul[1], query_err, fd_map_strerror( query_err ) ));
743 0 : }
744 33 : txn = fd_funk_txn_map_query_ele( query );
745 33 : break;
746 33 : }
747 :
748 : /* Select a fork node to create invalidate record in
749 : Do not create invalidation records at the funk root */
750 :
751 33 : if( FD_UNLIKELY( !fd_progcache_txn_try_lock( txn ) ) ) {
752 0 : FD_LOG_CRIT(( "fd_progcache_invalidate(xid=%lu,...) failed: txn is write-locked", xid->ul[0] ));
753 0 : }
754 :
755 : /* Allocate a funk_rec */
756 :
757 33 : fd_funk_rec_t * funk_rec = fd_funk_rec_pool_acquire( funk->rec_pool, NULL, 0, NULL );
758 33 : if( FD_UNLIKELY( !funk_rec ) ) {
759 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_funk_rec_pool_acquire failed (rec_max=%lu)",
760 0 : fd_funk_rec_pool_ele_max( funk->rec_pool ) ));
761 0 : }
762 33 : memset( funk_rec, 0, sizeof(fd_funk_rec_t) );
763 33 : fd_funk_val_init( funk_rec );
764 :
765 : /* Create a tombstone */
766 :
767 33 : void * rec_mem = fd_funk_val_truncate( funk_rec, funk->alloc, funk->wksp, fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ), NULL );
768 33 : if( FD_UNLIKELY( !rec_mem ) ) {
769 0 : FD_LOG_ERR(( "Program cache is out of memory: fd_alloc_malloc failed (requested align=%lu sz=%lu)",
770 0 : fd_progcache_rec_align(), fd_progcache_rec_footprint( NULL ) ));
771 0 : }
772 33 : fd_progcache_rec_t * rec = fd_progcache_rec_new_nx( rec_mem, slot );
773 33 : rec->invalidate = 1;
774 :
775 : /* Publish cache entry to funk index */
776 :
777 33 : fd_funk_rec_t * dup_rec = NULL;
778 33 : int push_ok = fd_progcache_push( cache, txn, funk_rec, prog_addr, &dup_rec );
779 :
780 : /* Done modifying transaction */
781 :
782 33 : fd_progcache_txn_unlock( txn );
783 :
784 : /* If another thread was faster publishing the same record, use that
785 : one instead. FIXME POSSIBLE RACE CONDITION WHERE THE OTHER REC IS
786 : EVICTED AFTER PEEK? */
787 :
788 33 : if( !push_ok ) {
789 3 : FD_TEST( dup_rec );
790 3 : fd_funk_val_flush( funk_rec, funk->alloc, funk->wksp );
791 3 : fd_funk_rec_pool_release( funk->rec_pool, funk_rec, 1 );
792 3 : cache->metrics->dup_insert_cnt++;
793 3 : return fd_funk_val_const( dup_rec, funk->wksp );
794 3 : }
795 :
796 30 : cache->metrics->invalidate_cnt++;
797 :
798 30 : return rec;
799 33 : }
|
