Line data Source code
1 : #include "fd_backup_cache.h"
2 : #include "fd_backup.h"
3 :
4 : fd_backup_cache_t *
5 : fd_backup_cache_init( fd_backup_cache_t * backup,
6 : uchar const * const cache [ FD_ACCDB_CACHE_CLASS_CNT ],
7 : ulong const cache_max[ FD_ACCDB_CACHE_CLASS_CNT ],
8 0 : fd_backup_accidx_t const * idx ) {
9 0 : FD_TEST( idx->epoch_slot );
10 0 : FD_TEST( idx->epoch );
11 0 : *backup = (fd_backup_cache_t) {
12 0 : .idx = *idx,
13 0 : .cache_class = 0UL,
14 0 : .cache_idx = 0UL
15 0 : };
16 0 : backup->idx.root_generation = 0U;
17 0 : FD_VOLATILE( *idx->epoch_slot ) = ULONG_MAX; /* idle until first section */
18 0 : for( ulong i=0UL; i<FD_ACCDB_CACHE_CLASS_CNT; i++ ) {
19 0 : backup->cache [ i ] = cache [ i ];
20 0 : backup->cache_max[ i ] = cache_max[ i ];
21 0 : }
22 0 : return backup;
23 0 : }
24 :
25 : fd_backup_cache_t *
26 : fd_backup_cache_join( fd_backup_cache_t * backup,
27 : fd_accdb_shmem_t * accdb,
28 0 : ulong * epoch_fseq ) {
29 0 : ulong max_live_slots = accdb->max_live_slots;
30 0 : ulong max_accounts = accdb->max_accounts;
31 :
32 0 : ulong chain_cnt = fd_ulong_pow2_up( (max_accounts>>1) + (max_accounts&1UL) );
33 :
34 0 : FD_SCRATCH_ALLOC_INIT( l, accdb );
35 0 : /* */FD_SCRATCH_ALLOC_APPEND( l, FD_ACCDB_SHMEM_ALIGN, sizeof(fd_accdb_shmem_t) );
36 0 : /* */FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_accdb_fork_shmem_t), max_live_slots*sizeof(fd_accdb_fork_shmem_t) );
37 0 : /* */FD_SCRATCH_ALLOC_APPEND( l, descends_set_align(), max_live_slots*descends_set_footprint( max_live_slots ) );
38 0 : void * _acc_map = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint), chain_cnt*sizeof(uint) );
39 0 : void * _acc_pool_ele = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_accdb_accmeta_t), max_accounts*sizeof(fd_accdb_accmeta_t) );
40 :
41 0 : uchar const * cache[ FD_ACCDB_CACHE_CLASS_CNT ];
42 0 : for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
43 0 : cache[ c ] = (uchar const *)accdb + accdb->cache_region_off[ c ];
44 0 : }
45 :
46 0 : fd_backup_accidx_t idx = {
47 0 : .acc_map = _acc_map,
48 0 : .acc_pool = _acc_pool_ele,
49 0 : .max_accounts = max_accounts,
50 0 : .seed = accdb->seed,
51 0 : .chain_mask = (uint)( chain_cnt-1UL ),
52 0 : .epoch_slot = epoch_fseq,
53 0 : .epoch = &accdb->epoch
54 0 : };
55 :
56 0 : return fd_backup_cache_init( backup, cache, accdb->cache_class_max, &idx );
57 0 : }
58 :
59 : static inline fd_accdb_cache_line_t *
60 : cache_line( fd_backup_cache_t * backup,
61 : ulong cls,
62 0 : ulong idx ) {
63 0 : return (fd_accdb_cache_line_t *)( backup->cache[ cls ] + idx * fd_accdb_cache_slot_sz[ cls ] );
64 0 : }
65 :
66 :
67 : /* filter_batch is called with arbitrary acc_idx found in cache.
68 : Filter out acc_idx that:
69 : - are not rooted (generation too new)
70 : - have been freed since then (not visible in map) -- these are
71 : guaranteed to have not been rooted, since rooted acc_idx are stable
72 : while compaction and advance_root is disabled */
73 :
74 : #define SET_NAME found_set
75 : #define SET_MAX FD_BACKUP_CACHE_PARA
76 : #include "../../util/tmpl/fd_set.c"
77 :
78 : static void
79 : filter_batch( fd_backup_cache_t * backup,
80 0 : fd_backup_cache_msg_t * frag ) {
81 0 : fd_backup_accidx_t const * idx = &backup->idx;
82 0 : fd_accdb_accmeta_t const * acc_pool = idx->acc_pool;
83 :
84 : /* filter out non-rooted accounts and tombstones */
85 0 : static fd_accdb_accmeta_t const dead_meta = { .key = { .generation = UINT_MAX } };
86 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
87 0 : uint acc_idx = frag->acc_idx[ i ];
88 0 : fd_accdb_accmeta_t const * m = acc_idx!=UINT_MAX ? &acc_pool[ acc_idx ] : &dead_meta;
89 0 : int keep = fd_backup_accidx_rooted( idx,
90 0 : FD_VOLATILE_CONST( m->key.generation ),
91 0 : FD_VOLATILE_CONST( m->lamports ) );
92 0 : fd_uint_store_if( !keep, &frag->acc_idx[ i ], UINT_MAX );
93 0 : }
94 :
95 : /* filter out invisible accounts */
96 0 : found_set_t found[ found_set_word_cnt ];
97 0 : found_set_new( found );
98 :
99 0 : uint head[ FD_BACKUP_CACHE_PARA ];
100 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
101 0 : head[ i ] = frag->acc_idx[ i ]!=UINT_MAX ? idx->acc_map[ backup->chain_idx[ i ] ] : UINT_MAX;
102 0 : }
103 :
104 : /* sentinel to assist with branchless code */
105 0 : static fd_accdb_accmeta_t const dead = {
106 0 : .map = { .next = UINT_MAX }
107 0 : };
108 :
109 : /* parallel walk map chains */
110 0 : for(;;) {
111 :
112 : /* check for matches */
113 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
114 0 : found_set_insert_if( found, frag->acc_idx[ i ]==head[ i ], i );
115 0 : }
116 :
117 : /* convert acc_idx to pointers */
118 0 : fd_accdb_accmeta_t const * gather[ FD_BACKUP_CACHE_PARA ];
119 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
120 0 : uint acc_idx = head[ i ];
121 0 : FD_DCHECK_CRIT( fd_backup_accidx_valid( idx, acc_idx ) || acc_idx==UINT_MAX, "acc_idx out of bounds" );
122 0 : gather[ i ] = acc_idx!=UINT_MAX ? &acc_pool[ acc_idx ] : &dead;
123 0 : }
124 :
125 : /* wide gather */
126 0 : fd_accdb_accmeta_t * meta = backup->meta;
127 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
128 0 : meta[ i ] = *gather[ i ];
129 0 : }
130 :
131 : /* next */
132 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
133 0 : head[ i ] = meta[ i ].map.next;
134 0 : }
135 :
136 : /* done? */
137 0 : int done = 1;
138 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
139 0 : if( head[ i ]!=UINT_MAX ) done = 0;
140 0 : }
141 0 : if( done ) break;
142 :
143 0 : }
144 :
145 : /* filter out dead elements */
146 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
147 0 : if( FD_UNLIKELY( !found_set_test( found, i ) ) ) {
148 0 : frag->acc_idx[ i ] = UINT_MAX;
149 0 : memset( frag->pubkey[ i ].uc, 0, sizeof(fd_pubkey_t) );
150 0 : }
151 0 : }
152 :
153 0 : }
154 :
155 : fd_backup_cache_msg_t *
156 : fd_backup_cache_scan( fd_backup_cache_t * backup,
157 0 : fd_backup_cache_msg_t * frag ) {
158 0 : fd_backup_accidx_t * accidx = &backup->idx;
159 :
160 0 : ulong cls = backup->cache_class;
161 0 : if( FD_UNLIKELY( cls >= FD_ACCDB_CACHE_CLASS_CNT ) ) {
162 0 : return NULL;
163 0 : }
164 :
165 0 : FD_COMPILER_MFENCE();
166 0 : FD_VOLATILE( *accidx->epoch_slot ) = FD_VOLATILE_CONST( *accidx->epoch );
167 0 : FD_HW_MFENCE();
168 :
169 : /* Scan through cache lines (sequentially)
170 : This discovers any cached account (rooted or not), therefore may
171 : produce account indices that become invalid. These are filtered
172 : out below. */
173 :
174 0 : long rem = (long)backup->cache_max[ cls ] - (long)backup->cache_idx;
175 0 : ulong idx = backup->cache_idx;
176 0 : if( FD_LIKELY( rem >= (long)FD_BACKUP_CACHE_PARA ) ) {
177 : /* fast path */
178 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++, idx++ ) {
179 0 : fd_accdb_cache_line_t const * line = cache_line( backup, cls, idx );
180 0 : frag->acc_idx[ i ] = line->acc_idx;
181 0 : fd_memcpy( frag->pubkey[ i ].uc, line->key.pubkey, sizeof(fd_pubkey_t) );
182 0 : backup->chain_idx[ i ] = fd_backup_accidx_chain( accidx, line->key.pubkey );
183 0 : }
184 0 : } else {
185 : /* slow path */
186 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
187 0 : frag->acc_idx[ i ] = UINT_MAX;
188 0 : memset( frag->pubkey[ i ].uc, 0, sizeof(fd_pubkey_t) );
189 0 : backup->chain_idx[ i ] = UINT_MAX; /* deliberately not ULONG_MAX */
190 0 : }
191 0 : for( ulong i=0UL; rem--; i++, idx++ ) {
192 0 : fd_accdb_cache_line_t const * line = cache_line( backup, cls, idx );
193 0 : frag->acc_idx[ i ] = line->acc_idx;
194 0 : fd_memcpy( frag->pubkey[ i ].uc, line->key.pubkey, sizeof(fd_pubkey_t) );
195 0 : backup->chain_idx[ i ] = fd_backup_accidx_chain( accidx, line->key.pubkey );
196 0 : }
197 0 : if( FD_UNLIKELY( idx >= backup->cache_max[ cls ] ) ) {
198 0 : backup->cache_class++;
199 0 : idx = 0UL;
200 0 : }
201 0 : }
202 0 : backup->cache_idx = idx;
203 :
204 : /* Filter out account indices that cannot index acc_pool */
205 :
206 0 : for( ulong i=0UL; i<FD_BACKUP_CACHE_PARA; i++ ) {
207 0 : if( !fd_backup_accidx_valid( accidx, frag->acc_idx[ i ] ) ) {
208 0 : frag->acc_idx[ i ] = UINT_MAX;
209 0 : memset( frag->pubkey[ i ].uc, 0, sizeof(fd_pubkey_t) );
210 0 : backup->chain_idx[ i ] = UINT_MAX;
211 0 : }
212 0 : }
213 :
214 : /* Filter out freed/invisible and non-rooted accounts */
215 :
216 0 : filter_batch( backup, frag );
217 :
218 0 : FD_COMPILER_MFENCE();
219 0 : FD_VOLATILE( *accidx->epoch_slot ) = ULONG_MAX;
220 0 : return frag;
221 0 : }
222 :
223 : int
224 : fd_backup_cache_read( fd_backup_cache_t * ctx,
225 : fd_pubkey_t const * pubkey,
226 : uint acc_idx,
227 : uchar * out,
228 : ulong * out_sz,
229 0 : ulong out_max ) {
230 0 : FD_TEST( pubkey );
231 :
232 0 : fd_backup_accidx_t const * accidx = &ctx->idx;
233 :
234 0 : FD_DCHECK_CRIT( FD_VOLATILE_CONST( *accidx->epoch_slot )!=ULONG_MAX, "caller must publish epoch" );
235 :
236 0 : if( FD_UNLIKELY( !fd_backup_accidx_valid( accidx, acc_idx ) ) ) {
237 0 : return FD_BACKUP_CACHE_ERR_MISS;
238 0 : }
239 :
240 0 : if( FD_UNLIKELY( *out_sz + sizeof(snap_acc_hdr_t) > out_max ) ) {
241 0 : return FD_BACKUP_CACHE_ERR_SPACE;
242 0 : }
243 :
244 : /* This is a partial copy of read_one_nocopy */
245 0 : fd_accdb_accmeta_t const * accmeta = &accidx->acc_pool[ acc_idx ];
246 0 : if( FD_UNLIKELY( memcmp( accmeta->key.pubkey, pubkey->uc, sizeof(fd_pubkey_t) ) ) ) {
247 0 : return FD_BACKUP_CACHE_ERR_MISS;
248 0 : }
249 :
250 : /// STEP 1.
251 : /// Walk the hash chain at acc_map[hash(pubkey)] using the same
252 : /// visibility test as fd_accdb_acquire_inner. See that function
253 : /// for the detailed safety argument under concurrent prepend.
254 0 : ulong chain_idx = fd_backup_accidx_chain( accidx, pubkey->uc );
255 0 : uint acc_idx2 = FD_VOLATILE_CONST( accidx->acc_map[ chain_idx ] );
256 0 : _Bool found = 0;
257 0 : while( acc_idx2!=UINT_MAX ) {
258 0 : FD_DCHECK_CRIT( fd_backup_accidx_valid( accidx, acc_idx2 ), "acc_idx out of bounds" );
259 0 : fd_accdb_accmeta_t const * candidate = &accidx->acc_pool[ acc_idx2 ];
260 0 : found |= acc_idx==acc_idx2;
261 0 : acc_idx2 = FD_VOLATILE_CONST( candidate->map.next );
262 0 : }
263 0 : if( !found ) return FD_BACKUP_CACHE_ERR_MISS;
264 :
265 : /// STEP 2.
266 : /// Snapshot acc fields. The acc element's metadata is effectively
267 : /// immutable from the perspective of cross-fork readers (see the
268 : /// comment block in fd_accdb.h about cross-fork reads). */
269 0 : uint snap_es = FD_VOLATILE_CONST( accmeta->executable_size );
270 0 : uint snap_gen = accmeta->key.generation;
271 0 : ulong snap_lamports = accmeta->lamports;
272 0 : uint snap_cidx = FD_VOLATILE_CONST( accmeta->cache_idx );
273 0 : ulong data_len = (ulong)FD_ACCDB_SIZE_DATA( snap_es );
274 0 : int executable = FD_ACCDB_SIZE_EXEC( snap_es );
275 0 : ulong rec_sz = sizeof(snap_acc_hdr_t) + fd_ulong_align_up( data_len, 8UL );
276 0 : ulong data_pad = fd_ulong_align_up( data_len, 8UL ) - data_len;
277 0 : if( FD_UNLIKELY( *out_sz + rec_sz > out_max ) ) {
278 0 : return FD_BACKUP_CACHE_ERR_SPACE;
279 0 : }
280 :
281 : /// STEP 3.
282 : /// Cache hit fast path with try-read-test (ABA) loop. Same
283 : /// primitives as cache_try_pin: re-check key.generation + pubkey
284 : /// before and after the bulk copy, and bail to the disk path if the
285 : /// line was claimed for eviction (refcnt ==
286 : /// FD_ACCDB_EVICT_SENTINEL). No CAS on refcnt, we never pin the
287 : /// line.
288 0 : if( !FD_ACCDB_SIZE_CACHE_VALID( snap_es ) ) {
289 0 : return FD_BACKUP_CACHE_ERR_MISS;
290 0 : }
291 0 : if( snap_cidx==FD_ACCDB_ACC_CIDX_INVAL ) {
292 0 : return FD_BACKUP_CACHE_ERR_MISS;
293 0 : }
294 :
295 0 : ulong cls = FD_ACCDB_ACC_CIDX_CLASS( snap_cidx );
296 0 : ulong idx = FD_ACCDB_ACC_CIDX_IDX ( snap_cidx );
297 0 : fd_accdb_cache_line_t * line = cache_line( ctx, cls, idx );
298 :
299 0 : snap_acc_hdr_t * hdr = (snap_acc_hdr_t *)( out + *out_sz );
300 0 : memset( hdr, 0, sizeof(snap_acc_hdr_t) );
301 0 : memcpy( hdr->pubkey.uc, pubkey->uc, sizeof(fd_pubkey_t) );
302 :
303 0 : uint gen0 = FD_VOLATILE_CONST( line->key.generation );
304 0 : uint rc0 = FD_VOLATILE_CONST( line->refcnt );
305 0 : uint ai0 = FD_VOLATILE_CONST( line->acc_idx );
306 0 : if( FD_UNLIKELY( rc0==FD_ACCDB_EVICT_SENTINEL ) ) return FD_BACKUP_CACHE_ERR_MISS;
307 0 : if( FD_UNLIKELY( gen0!=snap_gen ) ) return FD_BACKUP_CACHE_ERR_MISS;
308 0 : if( FD_UNLIKELY( memcmp( line->key.pubkey, pubkey->uc, sizeof(fd_pubkey_t) ) ) ) return FD_BACKUP_CACHE_ERR_MISS;
309 : /* acc_idx==UINT_MAX is the "loading" sentinel set by cold_load_acc
310 : before the preadv2 fills the line. CACHE_VALID can be observed
311 : set while the bytes are still stale, so fall to the disk path
312 : (which spins on offset_fork and reads from the file) rather
313 : than copying garbage. */
314 0 : if( FD_UNLIKELY( ai0==UINT_MAX ) ) return FD_BACKUP_CACHE_ERR_MISS;
315 :
316 0 : FD_COMPILER_MFENCE();
317 0 : memcpy( hdr->owner.uc, line->owner, 32UL );
318 0 : uchar * d = (uchar *)hdr + sizeof(snap_acc_hdr_t);
319 0 : memcpy( d, (uchar const *)(line+1UL), data_len );
320 0 : if( data_pad ) memset( d + data_len, 0, data_pad );
321 0 : FD_COMPILER_MFENCE();
322 :
323 0 : uint gen1 = FD_VOLATILE_CONST( line->key.generation );
324 0 : uint rc1 = FD_VOLATILE_CONST( line->refcnt );
325 0 : uint ai1 = FD_VOLATILE_CONST( line->acc_idx );
326 0 : if( FD_UNLIKELY( rc1==FD_ACCDB_EVICT_SENTINEL ) ) return FD_BACKUP_CACHE_ERR_MISS;
327 0 : if( FD_UNLIKELY( gen1!=snap_gen ) ) return FD_BACKUP_CACHE_ERR_MISS;
328 0 : if( FD_UNLIKELY( memcmp( line->key.pubkey, pubkey->uc, sizeof(fd_pubkey_t) ) ) ) return FD_BACKUP_CACHE_ERR_MISS;
329 0 : if( FD_UNLIKELY( ai1==UINT_MAX ) ) return FD_BACKUP_CACHE_ERR_MISS;
330 :
331 0 : hdr->lamports = snap_lamports;
332 0 : hdr->executable = !!executable;
333 0 : hdr->data_len = data_len;
334 0 : *out_sz += rec_sz;
335 0 : return FD_BACKUP_CACHE_SUCCESS;
336 0 : }
|
