Line data Source code
1 : #include "fd_funk.h"
2 :
3 : /* Provide the actual record map implementation */
4 :
5 : #define MAP_NAME fd_funk_rec_map
6 4918599280 : #define MAP_T fd_funk_rec_t
7 : #define MAP_KEY_T fd_funk_xid_key_pair_t
8 6478461 : #define MAP_KEY pair
9 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1))
10 1264556748 : #define MAP_KEY_HASH(k0,seed) fd_funk_xid_key_pair_hash((k0),(seed))
11 : #define MAP_KEY_COPY(kd,ks) fd_funk_xid_key_pair_copy((kd),(ks))
12 4592679631 : #define MAP_NEXT map_next
13 3968434835 : #define MAP_HASH map_hash
14 110568 : #define MAP_MAGIC (0xf173da2ce77ecdb0UL) /* Firedancer rec db version 0 */
15 : #define MAP_IMPL_STYLE 2
16 : #define MAP_MEMOIZE 1
17 : #include "../util/tmpl/fd_map_giant.c"
18 :
19 : FD_FN_PURE ulong
20 : fd_funk_rec_map_list_idx( fd_funk_rec_t const * join,
21 0 : fd_funk_xid_key_pair_t const * key ) {
22 0 : fd_funk_rec_map_private_t const * map = fd_funk_rec_map_private_const( join );
23 0 : return (fd_funk_xid_key_pair_hash( key, map->seed )) & (map->list_cnt-1UL);
24 0 : }
25 :
26 : void
27 0 : fd_funk_rec_map_set_key_cnt( fd_funk_rec_t * join, ulong key_cnt ) {
28 0 : fd_funk_rec_map_private_t * map = fd_funk_rec_map_private( join );
29 0 : map->key_cnt = key_cnt;
30 0 : }
31 :
32 : fd_funk_rec_t const *
33 : fd_funk_rec_query( fd_funk_t * funk,
34 : fd_funk_txn_t const * txn,
35 592371759 : fd_funk_rec_key_t const * key ) {
36 :
37 592371759 : if( FD_UNLIKELY( (!funk) | (!key) ) ) return NULL;
38 :
39 442379298 : fd_funk_xid_key_pair_t pair[1]; fd_funk_xid_key_pair_init( pair, txn ? fd_funk_txn_xid( txn ) : fd_funk_root( funk ), key );
40 :
41 442379298 : return fd_funk_rec_map_query_const( fd_funk_rec_map( funk, fd_funk_wksp( funk ) ), pair, NULL );
42 592371759 : }
43 :
44 : fd_funk_rec_t const *
45 : fd_funk_rec_query_global( fd_funk_t * funk,
46 : fd_funk_txn_t const * txn,
47 : fd_funk_rec_key_t const * key,
48 213851019 : fd_funk_txn_t const ** txn_out ) {
49 :
50 213851019 : if( FD_UNLIKELY( (!funk) | (!key) ) ) return NULL;
51 :
52 63858558 : fd_wksp_t * wksp = fd_funk_wksp( funk );
53 :
54 63858558 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
55 :
56 63858558 : if( txn ) { /* Query txn and its in-prep ancestors */
57 :
58 57326358 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
59 :
60 57326358 : ulong txn_max = funk->txn_max;
61 :
62 57326358 : ulong txn_idx = (ulong)(txn - txn_map);
63 :
64 57326358 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(txn_map+txn_idx)) /* Bad alignment */ ) )
65 0 : return NULL;
66 :
67 : /* TODO: const correct and/or fortify? */
68 140894055 : do {
69 140894055 : fd_funk_xid_key_pair_t pair[1]; fd_funk_xid_key_pair_init( pair, fd_funk_txn_xid( txn ), key );
70 140894055 : fd_funk_rec_t const * rec = fd_funk_rec_map_query_const( rec_map, pair, NULL );
71 140894055 : if( FD_LIKELY( rec ) ) {
72 8823075 : if( FD_UNLIKELY(NULL != txn_out ) ) {
73 0 : *txn_out = txn;
74 0 : }
75 8823075 : return rec;
76 8823075 : }
77 132070980 : txn = fd_funk_txn_parent( (fd_funk_txn_t *)txn, txn_map );
78 132070980 : } while( FD_UNLIKELY( txn ) );
79 :
80 57326358 : }
81 :
82 : /* Query the last published transaction */
83 :
84 55035483 : fd_funk_xid_key_pair_t pair[1]; fd_funk_xid_key_pair_init( pair, fd_funk_root( funk ), key );
85 55035483 : return fd_funk_rec_map_query_const( rec_map, pair, NULL );
86 63858558 : }
87 :
88 : void *
89 : fd_funk_rec_query_safe( fd_funk_t * funk,
90 : fd_funk_rec_key_t const * key,
91 : fd_valloc_t valloc,
92 0 : ulong * result_len ) {
93 0 : return fd_funk_rec_query_xid_safe( funk, key, fd_funk_root( funk ), valloc, result_len );
94 0 : }
95 :
96 : void *
97 : fd_funk_rec_query_xid_safe( fd_funk_t * funk,
98 : fd_funk_rec_key_t const * key,
99 : fd_funk_txn_xid_t const * xid,
100 : fd_valloc_t valloc,
101 0 : ulong * result_len ) {
102 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
103 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
104 :
105 0 : fd_funk_xid_key_pair_t pair[1];
106 0 : fd_funk_xid_key_pair_init( pair, xid, key );
107 :
108 0 : void * result = NULL;
109 0 : ulong alloc_len = 0;
110 0 : *result_len = 0;
111 0 : for(;;) {
112 0 : ulong lock_start;
113 0 : for(;;) {
114 0 : lock_start = funk->write_lock;
115 0 : if( FD_LIKELY(!(lock_start&1UL)) ) break;
116 : /* Funk is currently write locked */
117 0 : FD_SPIN_PAUSE();
118 0 : }
119 0 : FD_COMPILER_MFENCE();
120 :
121 0 : fd_funk_rec_t const * rec = fd_funk_rec_map_query_safe( rec_map, pair, NULL );
122 0 : if( FD_UNLIKELY( rec == NULL ) ) {
123 0 : FD_COMPILER_MFENCE();
124 0 : if( lock_start == funk->write_lock ) return NULL;
125 0 : } else {
126 0 : uint val_sz = rec->val_sz;
127 0 : if( val_sz ) {
128 0 : if( result == NULL ) {
129 0 : result = fd_valloc_malloc( valloc, FD_FUNK_VAL_ALIGN, val_sz );
130 0 : alloc_len = val_sz;
131 0 : } else if ( val_sz > alloc_len ) {
132 0 : fd_valloc_free( valloc, result );
133 0 : result = fd_valloc_malloc( valloc, FD_FUNK_VAL_ALIGN, val_sz );
134 0 : alloc_len = val_sz;
135 0 : }
136 0 : fd_memcpy( result, fd_wksp_laddr_fast( wksp, rec->val_gaddr ), val_sz );
137 0 : }
138 0 : *result_len = val_sz;
139 0 : FD_COMPILER_MFENCE();
140 0 : if( lock_start == funk->write_lock ) return result;
141 0 : }
142 :
143 : /* else try again */
144 0 : FD_SPIN_PAUSE();
145 0 : }
146 0 : }
147 :
148 : int
149 : fd_funk_rec_test( fd_funk_t * funk,
150 279388104 : fd_funk_rec_t const * rec ) {
151 :
152 279388104 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
153 :
154 179393130 : fd_wksp_t * wksp = fd_funk_wksp( funk );
155 :
156 179393130 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
157 :
158 179393130 : ulong rec_max = funk->rec_max;
159 :
160 179393130 : ulong rec_idx = (ulong)(rec - rec_map);
161 :
162 179393130 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
163 149992461 : return FD_FUNK_ERR_INVAL;
164 :
165 29400669 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) ) return FD_FUNK_ERR_KEY;
166 :
167 28067850 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
168 :
169 28067850 : if( FD_UNLIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) { /* Rec in last published, opt for lots recs */
170 :
171 21903099 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) return FD_FUNK_ERR_FROZEN;
172 :
173 21903099 : } else { /* Rec in in-prep */
174 :
175 6164751 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
176 6164751 : ulong txn_max = funk->txn_max;
177 :
178 6164751 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) return FD_FUNK_ERR_XID; /* TODO: consider LOG_CRIT here? */
179 :
180 6164751 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) ) return FD_FUNK_ERR_FROZEN;
181 :
182 6164751 : }
183 :
184 1456731 : return FD_FUNK_SUCCESS;
185 28067850 : }
186 :
187 : fd_funk_rec_t *
188 : fd_funk_rec_modify( fd_funk_t * funk,
189 486851436 : fd_funk_rec_t const * rec ) {
190 486851436 : if( FD_UNLIKELY( (!funk) | (!rec) ) )
191 149992461 : return NULL;
192 336858975 : fd_funk_check_write( funk );
193 :
194 336858975 : fd_wksp_t * wksp = fd_funk_wksp( funk );
195 :
196 336858975 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
197 :
198 336858975 : ulong rec_max = funk->rec_max;
199 :
200 336858975 : ulong rec_idx = (ulong)(rec - rec_map);
201 :
202 336858975 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
203 99994974 : return NULL;
204 :
205 236864001 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) )
206 1332819 : return NULL; /* Not live */
207 :
208 235531182 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
209 :
210 235531182 : if( fd_funk_txn_idx_is_null( txn_idx ) ) { /* Modifying last published transaction */
211 :
212 117697500 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) )
213 111320703 : return NULL;
214 :
215 117833682 : } else { /* Modifying an in-prep transaction */
216 117833682 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
217 :
218 117833682 : ulong txn_max = funk->txn_max;
219 :
220 117833682 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
221 :
222 117833682 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) )
223 54568209 : return NULL;
224 117833682 : }
225 :
226 69642270 : return (fd_funk_rec_t *)rec;
227 235531182 : }
228 :
229 : FD_FN_PURE int
230 : fd_funk_rec_is_modified( fd_funk_t * funk,
231 0 : fd_funk_rec_t const * rec ) {
232 :
233 0 : if( FD_UNLIKELY( (!funk) | (!rec) ) ) return 0;
234 :
235 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
236 :
237 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
238 0 : ulong rec_max = funk->rec_max;
239 0 : ulong rec_idx = (ulong)(rec - rec_map);
240 0 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
241 0 : FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
242 :
243 0 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
244 0 : if( fd_funk_txn_idx_is_null( txn_idx ) )
245 0 : return -1;
246 0 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
247 0 : ulong txn_max = funk->txn_max;
248 0 : if( FD_UNLIKELY( txn_idx>=txn_max ) )
249 0 : FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
250 0 : fd_funk_txn_t * txn = txn_map + txn_idx;
251 :
252 0 : void * val = fd_funk_val( rec, wksp );
253 :
254 0 : do {
255 : /* Go to the parent transaction */
256 0 : fd_funk_xid_key_pair_t pair[1];
257 0 : txn_idx = fd_funk_txn_idx( txn->parent_cidx );
258 0 : if ( fd_funk_txn_idx_is_null( txn_idx ) ) {
259 0 : txn = NULL;
260 0 : fd_funk_xid_key_pair_init( pair, fd_funk_root( funk ), rec->pair.key );
261 0 : } else {
262 0 : txn = txn_map + txn_idx;
263 0 : fd_funk_xid_key_pair_init( pair, fd_funk_txn_xid( txn ), rec->pair.key );
264 0 : }
265 :
266 0 : fd_funk_rec_t const * rec2 = fd_funk_rec_map_query_const( rec_map, pair, NULL );
267 0 : if ( rec2 ) {
268 0 : if ( rec->val_sz != rec2->val_sz )
269 0 : return 1;
270 0 : void * val2 = fd_funk_val( rec2, wksp );
271 0 : return memcmp(val, val2, rec->val_sz) != 0;
272 0 : }
273 0 : } while (txn);
274 :
275 0 : return 1;
276 0 : }
277 :
278 : fd_funk_rec_t const *
279 : fd_funk_rec_insert( fd_funk_t * funk,
280 : fd_funk_txn_t * txn,
281 : fd_funk_rec_key_t const * key,
282 262537284 : int * opt_err ) {
283 :
284 262537284 : if( FD_UNLIKELY( (!funk) | /* NULL funk */
285 262537284 : (!key ) ) ) { /* NULL key */
286 199989948 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
287 199989948 : return NULL;
288 199989948 : }
289 62547336 : fd_funk_check_write( funk );
290 :
291 62547336 : fd_wksp_t * wksp = fd_funk_wksp( funk );
292 :
293 62547336 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
294 :
295 62547336 : ulong rec_max = funk->rec_max;
296 :
297 62547336 : if( FD_UNLIKELY( fd_funk_rec_map_is_full( rec_map ) ) ) {
298 9705702 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_REC );
299 9705702 : return NULL;
300 9705702 : }
301 :
302 52841634 : ulong txn_idx;
303 52841634 : ulong * _rec_head_idx;
304 52841634 : ulong * _rec_tail_idx;
305 52841634 : fd_funk_xid_key_pair_t pair[1];
306 :
307 52841634 : if( !txn ) { /* Modifying last published */
308 :
309 6398967 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) {
310 5782002 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
311 5782002 : return NULL;
312 5782002 : }
313 :
314 616965 : txn_idx = FD_FUNK_TXN_IDX_NULL;
315 616965 : _rec_head_idx = &funk->rec_head_idx;
316 616965 : _rec_tail_idx = &funk->rec_tail_idx;
317 :
318 616965 : fd_funk_xid_key_pair_init( pair, fd_funk_root( funk ), key );
319 :
320 616965 : fd_funk_rec_t * rec = fd_funk_rec_map_query( rec_map, pair, NULL );
321 :
322 616965 : if( FD_UNLIKELY( rec ) ) { /* Already a record present */
323 100884 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) FD_LOG_CRIT(( "memory corruption detected (bad flags)" ));
324 100884 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_KEY );
325 100884 : return NULL;
326 100884 : }
327 :
328 46442667 : } else { /* Modifying in-prep */
329 :
330 46442667 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
331 :
332 46442667 : ulong txn_max = funk->txn_max;
333 :
334 46442667 : txn_idx = (ulong)(txn - txn_map);
335 46442667 : _rec_head_idx = &txn->rec_head_idx;
336 46442667 : _rec_tail_idx = &txn->rec_tail_idx;
337 :
338 46442667 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(txn_map+txn_idx)) /* Bad alignment */ ) ) {
339 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
340 0 : return NULL;
341 0 : }
342 :
343 46442667 : if( FD_UNLIKELY( !fd_funk_txn_map_query( txn_map, fd_funk_txn_xid( txn ), NULL ) ) ) {
344 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
345 0 : return NULL;
346 0 : }
347 :
348 46442667 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( txn ) ) ) {
349 39236118 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
350 39236118 : return NULL;
351 39236118 : }
352 :
353 7206549 : fd_funk_xid_key_pair_init( pair, fd_funk_txn_xid( txn ), key );
354 :
355 7206549 : fd_funk_rec_t * rec = fd_funk_rec_map_query( rec_map, pair, NULL );
356 :
357 7206549 : if( FD_UNLIKELY( rec ) ) { /* Already a record present */
358 :
359 : /* If this record has erase set, it is supposed to erase its
360 : closest ancestor record on publish. At the time it was marked
361 : erase, any updates it had to the ancestor record value were
362 : flushed. Thus clearing the erase flag will reset the record to
363 : the way it was when it was first inserted into this
364 : transaction.
365 :
366 : Otherwise, the user is trying insert a record update on top of
367 : a pre-existing of record update. We fail with ERR_KEY to
368 : prevent accidentally discarding any previous updates
369 : unintentionally.
370 :
371 : In both cases, it is straightforward to tweak these to have
372 : alternative behaviors as might be convenient for users. */
373 :
374 1498980 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) {
375 45084 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
376 45084 : return rec;
377 45084 : }
378 :
379 1453896 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_KEY );
380 1453896 : return NULL;
381 :
382 1498980 : }
383 :
384 7206549 : }
385 :
386 6223650 : fd_funk_rec_t * rec = fd_funk_rec_map_insert( rec_map, pair );
387 6223650 : ulong rec_idx = (ulong)(rec - rec_map);
388 6223650 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
389 :
390 6223650 : ulong rec_prev_idx = *_rec_tail_idx;
391 :
392 6223650 : int first_born = fd_funk_rec_idx_is_null( rec_prev_idx );
393 6223650 : if( FD_UNLIKELY( !first_born ) ) {
394 4831794 : if( FD_UNLIKELY( rec_prev_idx>=rec_max ) )
395 0 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" ));
396 4831794 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_prev_idx ].txn_cidx!=txn_idx ) ) )
397 0 : FD_LOG_CRIT(( "memory corruption detected (mismatch)" ));
398 4831794 : }
399 :
400 6223650 : rec->prev_idx = rec_prev_idx;
401 6223650 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
402 6223650 : rec->txn_cidx = fd_funk_txn_cidx( txn_idx );
403 6223650 : rec->tag = 0U;
404 6223650 : rec->flags = 0UL;
405 :
406 6223650 : if( first_born ) *_rec_head_idx = rec_idx;
407 4831794 : else rec_map[ rec_prev_idx ].next_idx = rec_idx;
408 :
409 6223650 : *_rec_tail_idx = rec_idx;
410 :
411 6223650 : fd_funk_val_init( rec );
412 6223650 : fd_funk_part_init( rec );
413 :
414 6223650 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_SUCCESS );
415 6223650 : return rec;
416 6223650 : }
417 :
418 : int
419 : fd_funk_rec_remove( fd_funk_t * funk,
420 : fd_funk_rec_t * rec,
421 529277055 : int erase ) {
422 :
423 529277055 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
424 329287107 : fd_funk_check_write( funk );
425 :
426 329287107 : fd_wksp_t * wksp = fd_funk_wksp( funk );
427 :
428 329287107 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
429 :
430 329287107 : ulong rec_max = funk->rec_max;
431 :
432 329287107 : ulong rec_idx = (ulong)(rec - rec_map);
433 :
434 329287107 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
435 299984922 : return FD_FUNK_ERR_INVAL;
436 :
437 29302185 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) ) return FD_FUNK_ERR_KEY;
438 :
439 : /* At this point, rec appears to be a live record. Determine which
440 : list contains the record and if we are allowed to remove it. */
441 :
442 29302185 : ulong * _rec_head_idx;
443 29302185 : ulong * _rec_tail_idx;
444 :
445 29302185 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
446 :
447 29302185 : if( FD_UNLIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) { /* Removing from last published, opt for lots recs, rand remove */
448 :
449 23616726 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) return FD_FUNK_ERR_FROZEN;
450 :
451 615762 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) FD_LOG_CRIT(( "memory corruption detected (bad flags)" ));
452 :
453 615762 : if( FD_UNLIKELY( !erase ) ) return FD_FUNK_ERR_XID;
454 :
455 : /* At this point, we are in last published transaction, it is
456 : unfrozen, the record erase flag is clear and the user explicitly
457 : asked to erase. Remove the record. */
458 :
459 565320 : _rec_head_idx = &funk->rec_head_idx;
460 565320 : _rec_tail_idx = &funk->rec_tail_idx;
461 :
462 5685459 : } else { /* Removing from in-prep transaction */
463 :
464 5685459 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
465 5685459 : ulong txn_max = funk->txn_max;
466 :
467 5685459 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
468 :
469 5685459 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) ) return FD_FUNK_ERR_FROZEN;
470 :
471 1331025 : if( FD_UNLIKELY( erase ) ) {
472 :
473 : /* If this was already marked for erase, we are done (we already
474 : flushed the value when it was first marked for erase) */
475 :
476 971955 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) return FD_FUNK_SUCCESS;
477 :
478 : /* Query our ancestors to see if we need to keep this record
479 : around or if we can just remove it immediately. Though this is
480 : potentially an O(ancestor_cnt) cost, it prevents the
481 : possibility unnecessarily consuming a practically unbounded
482 : number of records by flickering insert / remove-with-erase in
483 : an in-preparation transaction with lots unique keys. */
484 :
485 923913 : ulong tag = funk->cycle_tag++;
486 :
487 923913 : ulong cur_idx = txn_idx;
488 1860732 : for(;;) {
489 :
490 : /* At this point, transaction cur_idx is an in-prep transaction.
491 : Tag it for cycle detection and see if transaction cur_idx's
492 : parent has a record for this and react accordingly. */
493 :
494 1860732 : txn_map[ cur_idx ].tag = tag;
495 :
496 1860732 : ulong parent_idx = fd_funk_txn_idx( txn_map[ cur_idx ].parent_cidx );
497 1860732 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* Parent txn is last published, opt for shallow */
498 :
499 816867 : fd_funk_rec_t const * erase_rec = fd_funk_rec_query( funk, NULL, fd_funk_rec_key( rec ) );
500 816867 : if( FD_UNLIKELY( !erase_rec ) ) break; /* No ancestor has this record, can free immediately, opt no flicker */
501 :
502 : /* Record is available in last published ... this remove
503 : should erase the published record when if and when this txn
504 : is published. We should never see a published record as
505 : flagged for erasure. */
506 :
507 633987 : if( FD_UNLIKELY( erase_rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) FD_LOG_CRIT(( "memory corruption detected (bad flags)" ));
508 :
509 633987 : fd_funk_part_set_intern( fd_funk_get_partvec( funk, wksp ), rec_map, rec, FD_FUNK_PART_NULL );
510 633987 : fd_funk_val_flush( rec, fd_funk_alloc( funk, wksp ), wksp ); /* TODO: consider testing wksp_gaddr has wksp_tag? */
511 :
512 633987 : rec->flags |= FD_FUNK_REC_FLAG_ERASE;
513 :
514 633987 : return FD_FUNK_SUCCESS;
515 :
516 633987 : }
517 :
518 1043865 : if( FD_UNLIKELY( parent_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
519 1043865 : if( FD_UNLIKELY( txn_map[ parent_idx ].tag==tag ) ) FD_LOG_CRIT(( "memory corruption detected (cycle)" ));
520 :
521 1043865 : fd_funk_rec_t const * erase_rec = fd_funk_rec_query( funk, &txn_map[ parent_idx ], fd_funk_rec_key( rec ) );
522 1043865 : if( FD_LIKELY( erase_rec ) ) { /* Opt for shallow */
523 :
524 : /* Record is available in an in-prep ancestor ... this remove
525 : erases that record on publish of this txn (which also
526 : implies an earlier publish of that ancestor).
527 :
528 : If that ancestor record itself was already marked as
529 : erasing a record, we can just free this record.
530 :
531 : (Note, there are some exotic circumstances that can
532 : generate such naturally but they are pretty gross. For
533 : example distant ancestor has this record, unpublished
534 : ancestor has marked it for erase, user reused the record's
535 : key in this txn, and has some proposed updates to the
536 : record's val that the user then decides to discard. It is
537 : arguable that cases should be disallowed. More generally,
538 : it is a good practice to only erase on records that don't
539 : have any proposed updates in them to avoid cases like
540 : this.) */
541 :
542 107046 : if( erase_rec->flags & FD_FUNK_REC_FLAG_ERASE ) break;
543 :
544 : /* Otherwise, we mark this record as erasing that record and
545 : discard any changes we might have made already in this
546 : record. */
547 :
548 103635 : fd_funk_val_flush( rec, fd_funk_alloc( funk, wksp ), wksp ); /* TODO: consider testing wksp_gaddr has wksp_tag? */
549 103635 : fd_funk_part_set_intern( fd_funk_get_partvec( funk, wksp ), rec_map, rec, FD_FUNK_PART_NULL );
550 :
551 103635 : rec->flags |= FD_FUNK_REC_FLAG_ERASE;
552 :
553 103635 : return FD_FUNK_SUCCESS;
554 107046 : }
555 :
556 936819 : cur_idx = parent_idx;
557 936819 : }
558 :
559 923913 : }
560 :
561 : /* At this point, we are in an in-prep transaction, it is unfrozen,
562 : and we are to discard changes to this record done by this
563 : transaction. Note that if rec_erase is set, this will discard
564 : the erase and any value changes that might have been made
565 : previously. */
566 :
567 545361 : _rec_head_idx = &txn_map[ txn_idx ].rec_head_idx;
568 545361 : _rec_tail_idx = &txn_map[ txn_idx ].rec_tail_idx;
569 545361 : }
570 :
571 : /* Flush the value, remove the record from its list, and unmap the
572 : record */
573 :
574 1110681 : fd_funk_val_flush( rec, fd_funk_alloc( funk, wksp ), wksp ); /* TODO: consider testing wksp_gaddr has wksp_tag? */
575 1110681 : fd_funk_part_set_intern( fd_funk_get_partvec( funk, wksp ), rec_map, rec, FD_FUNK_PART_NULL );
576 :
577 1110681 : ulong prev_idx = rec->prev_idx;
578 1110681 : ulong next_idx = rec->next_idx;
579 :
580 1110681 : int prev_null = fd_funk_rec_idx_is_null( prev_idx );
581 1110681 : int next_null = fd_funk_rec_idx_is_null( next_idx );
582 :
583 1110681 : if( !( ((prev_null) | (prev_idx<rec_max)) & ((next_null) | (next_idx<rec_max)) ) )
584 0 : FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
585 :
586 : /* TODO: Consider branchless impl */
587 1110681 : if( prev_null ) *_rec_head_idx = next_idx;
588 878682 : else rec_map[ prev_idx ].next_idx = next_idx;
589 :
590 1110681 : if( next_null ) *_rec_tail_idx = prev_idx;
591 872706 : else rec_map[ next_idx ].prev_idx = prev_idx;
592 :
593 1110681 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( rec ) );
594 :
595 1110681 : return FD_FUNK_SUCCESS;
596 1110681 : }
597 :
598 : fd_funk_rec_t *
599 : fd_funk_rec_write_prepare( fd_funk_t * funk,
600 : fd_funk_txn_t * txn,
601 : fd_funk_rec_key_t const * key,
602 : ulong min_val_size,
603 : int do_create,
604 : fd_funk_rec_t const * irec,
605 10089270 : int * opt_err ) {
606 :
607 10089270 : fd_wksp_t * wksp = fd_funk_wksp( funk );
608 :
609 10089270 : fd_funk_rec_t * rec = NULL;
610 10089270 : fd_funk_rec_t const * rec_con = NULL;
611 10089270 : if ( FD_LIKELY (NULL == irec ) )
612 10089261 : rec_con = fd_funk_rec_query_global( funk, txn, key, NULL );
613 9 : else
614 9 : rec_con = irec;
615 :
616 10089270 : if ( FD_UNLIKELY( rec_con && !(rec_con->flags & FD_FUNK_REC_FLAG_ERASE) ) ) {
617 : /* We have an incarnation of the record */
618 6140493 : if ( txn == fd_funk_rec_txn( rec_con, fd_funk_txn_map( funk, wksp ) ) ) {
619 : /* The record is already in the right transaction */
620 3618213 : rec = fd_funk_rec_modify( funk, rec_con );
621 3618213 : if ( !rec ) {
622 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
623 0 : return NULL;
624 0 : }
625 :
626 3618213 : } else {
627 : /* Copy the record into the transaction */
628 2522280 : rec = fd_funk_rec_modify( funk, fd_funk_rec_insert( funk, txn, key, opt_err ) );
629 2522280 : if ( !rec )
630 0 : return NULL;
631 2522280 : rec = fd_funk_val_copy( rec, fd_funk_val_const(rec_con, wksp), fd_funk_val_sz(rec_con),
632 2522280 : fd_ulong_max( fd_funk_val_sz(rec_con), min_val_size ), fd_funk_alloc( funk, wksp ), wksp, opt_err );
633 2522280 : if ( !rec ) {
634 0 : return NULL;
635 0 : }
636 2522280 : }
637 :
638 6140493 : } else {
639 3948777 : if (!do_create) {
640 1566723 : if( opt_err ) *opt_err = FD_FUNK_ERR_KEY;
641 1566723 : return NULL;
642 1566723 : }
643 :
644 : /* Create a new record */
645 2382054 : rec = fd_funk_rec_modify( funk, fd_funk_rec_insert( funk, txn, key, opt_err ) );
646 2382054 : if ( !rec )
647 0 : return NULL;
648 2382054 : }
649 :
650 : /* Grow the record to the right size */
651 8522547 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
652 8522547 : if ( fd_funk_val_sz( rec ) < min_val_size ) {
653 1354641 : if( funk->speed_load )
654 0 : rec = fd_funk_val_speed_load( funk, rec, min_val_size, wksp, opt_err );
655 1354641 : else
656 1354641 : rec = fd_funk_val_truncate( rec, min_val_size, fd_funk_alloc( funk, wksp ), wksp, opt_err );
657 1354641 : }
658 :
659 8522547 : return rec;
660 10089270 : }
661 :
662 : int
663 22026408 : fd_funk_rec_verify( fd_funk_t * funk ) {
664 22026408 : fd_wksp_t * wksp = fd_funk_wksp( funk ); /* Previously verified */
665 22026408 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp ); /* Previously verified */
666 22026408 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp ); /* Previously verified */
667 22026408 : ulong txn_max = funk->txn_max; /* Previously verified */
668 22026408 : ulong rec_max = funk->rec_max; /* Previously verified */
669 :
670 : /* At this point, txn_map has been extensively verified */
671 :
672 3628543878 : # define TEST(c) do { \
673 3628543878 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
674 3628543878 : } while(0)
675 :
676 22026408 : TEST( !fd_funk_rec_map_verify( rec_map ) );
677 :
678 : /* Iterate over all records in use */
679 :
680 22026408 : for( fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter_init( rec_map );
681 606388173 : !fd_funk_rec_map_iter_done( rec_map, iter );
682 584361765 : iter = fd_funk_rec_map_iter_next( rec_map, iter ) ) {
683 584361765 : fd_funk_rec_t * rec = fd_funk_rec_map_iter_ele( rec_map, iter );
684 :
685 : /* Make sure every record either links up with the last published
686 : transaction or an in-prep transaction and the flags are sane. */
687 :
688 584361765 : fd_funk_txn_xid_t const * txn_xid = fd_funk_rec_xid( rec );
689 584361765 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
690 :
691 584361765 : if( fd_funk_txn_idx_is_null( txn_idx ) ) { /* This is a record from the last published transaction */
692 :
693 329942751 : TEST( fd_funk_txn_xid_eq_root( txn_xid ) );
694 329942751 : TEST( !(rec->flags & FD_FUNK_REC_FLAG_ERASE) );
695 :
696 329942751 : } else { /* This is a record from an in-prep transaction */
697 :
698 254419014 : TEST( txn_idx<txn_max );
699 254419014 : fd_funk_txn_t const * txn = fd_funk_txn_map_query_const( txn_map, txn_xid, NULL );
700 254419014 : TEST( txn );
701 254419014 : TEST( txn==(txn_map+txn_idx) );
702 :
703 254419014 : }
704 584361765 : }
705 :
706 : /* Clear record tags and then verify the forward and reverse linkage */
707 :
708 2953058472 : for( ulong rec_idx=0UL; rec_idx<rec_max; rec_idx++ ) rec_map[ rec_idx ].tag = 0U;
709 :
710 22026408 : ulong rec_cnt = fd_funk_rec_map_key_cnt( rec_map );
711 :
712 22026408 : do {
713 22026408 : ulong cnt = 0UL;
714 :
715 22026408 : ulong txn_idx = FD_FUNK_TXN_IDX_NULL;
716 22026408 : ulong rec_idx = funk->rec_head_idx;
717 351969159 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
718 329942751 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==0U );
719 329942751 : rec_map[ rec_idx ].tag = 1U;
720 329942751 : cnt++;
721 329942751 : ulong next_idx = rec_map[ rec_idx ].next_idx;
722 329942751 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_map[ next_idx ].prev_idx==rec_idx );
723 329942751 : rec_idx = next_idx;
724 329942751 : }
725 22026408 : for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
726 134597451 : !fd_funk_txn_map_iter_done( txn_map, iter );
727 112571043 : iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
728 112571043 : fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
729 :
730 112571043 : ulong txn_idx = (ulong)(txn-txn_map);
731 112571043 : ulong rec_idx = txn->rec_head_idx;
732 366990057 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
733 254419014 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==0U );
734 254419014 : rec_map[ rec_idx ].tag = 1U;
735 254419014 : cnt++;
736 254419014 : ulong next_idx = rec_map[ rec_idx ].next_idx;
737 254419014 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_map[ next_idx ].prev_idx==rec_idx );
738 254419014 : rec_idx = next_idx;
739 254419014 : }
740 112571043 : }
741 :
742 22026408 : TEST( cnt==rec_cnt );
743 22026408 : } while(0);
744 :
745 22026408 : do {
746 22026408 : ulong cnt = 0UL;
747 :
748 22026408 : ulong txn_idx = FD_FUNK_TXN_IDX_NULL;
749 22026408 : ulong rec_idx = funk->rec_tail_idx;
750 351969159 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
751 329942751 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==1U );
752 329942751 : rec_map[ rec_idx ].tag = 2U;
753 329942751 : cnt++;
754 329942751 : ulong prev_idx = rec_map[ rec_idx ].prev_idx;
755 329942751 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_map[ prev_idx ].next_idx==rec_idx );
756 329942751 : rec_idx = prev_idx;
757 329942751 : }
758 :
759 22026408 : for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
760 134597451 : !fd_funk_txn_map_iter_done( txn_map, iter );
761 112571043 : iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
762 112571043 : fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
763 :
764 112571043 : ulong txn_idx = (ulong)(txn-txn_map);
765 112571043 : ulong rec_idx = txn->rec_tail_idx;
766 366990057 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
767 254419014 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==1U );
768 254419014 : rec_map[ rec_idx ].tag = 2U;
769 254419014 : cnt++;
770 254419014 : ulong prev_idx = rec_map[ rec_idx ].prev_idx;
771 254419014 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_map[ prev_idx ].next_idx==rec_idx );
772 254419014 : rec_idx = prev_idx;
773 254419014 : }
774 112571043 : }
775 :
776 22026408 : TEST( cnt==rec_cnt );
777 22026408 : } while(0);
778 :
779 22026408 : # undef TEST
780 :
781 22026408 : return FD_FUNK_SUCCESS;
782 22026408 : }
|
