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 22663485911 : #define MAP_T fd_funk_rec_t
7 : #define MAP_KEY_T fd_funk_xid_key_pair_t
8 7856379 : #define MAP_KEY pair
9 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1))
10 1585140066 : #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 22427219811 : #define MAP_NEXT map_next
13 6858627955 : #define MAP_HASH map_hash
14 408480 : #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 704641509 : fd_funk_rec_key_t const * key ) {
36 :
37 704641509 : if( FD_UNLIKELY( (!funk) | (!key) ) ) return NULL;
38 :
39 613005399 : 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 613005399 : return fd_funk_rec_map_query_const( fd_funk_rec_map( funk, fd_funk_wksp( funk ) ), pair, NULL );
42 704641509 : }
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 541456566 : fd_funk_txn_t const ** txn_out ) {
49 541456566 : if( FD_UNLIKELY( (!funk) | (!key) ) ) return NULL;
50 :
51 449820456 : fd_wksp_t * wksp = fd_funk_wksp( funk );
52 :
53 449820456 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
54 449820456 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
55 :
56 : /* For record ele in all records in chain that match key. (This
57 : code was adapted from the map_giant template ... ideally would
58 : use a map chain iterator ala map_para template). */
59 :
60 : /* Note: the iteration order will be such that the record
61 : for a key in a descendent of a transaction will be presented
62 : before a record for that key in that transaction. This allows us
63 : to succeed on the first hit (the newest transaction). It is
64 : NECESSARY that fd_funk_rec_map_insert preserve this property. */
65 :
66 449820456 : fd_funk_rec_map_private_t * priv = fd_funk_rec_map_private( rec_map );
67 449820456 : ulong hash = fd_funk_rec_key_hash( key, priv->seed );
68 449820456 : ulong * head = fd_funk_rec_map_private_list( priv ) + ( hash & (priv->list_cnt-1UL) );
69 449820456 : ulong * cur = head;
70 :
71 940902067 : for(;;) {
72 940902067 : ulong ele_idx = fd_funk_rec_map_private_unbox_idx( *cur );
73 940902067 : if( fd_funk_rec_map_private_is_null( ele_idx ) ) break;
74 935751868 : fd_funk_rec_t * ele = rec_map + ele_idx;
75 935751868 : if( FD_LIKELY( hash == ele->map_hash ) && FD_LIKELY( fd_funk_rec_key_eq( key, ele->pair.key ) ) ) {
76 :
77 : /* For cur_txn in path from [txn] to [root] where root is NULL */
78 :
79 837257319 : for( fd_funk_txn_t const * cur_txn = txn; ; cur_txn = fd_funk_txn_parent( cur_txn, txn_map ) ) {
80 : /* If record ele is part of transaction cur_txn, we have a
81 : match. According to the property above, this will be the
82 : youngest descendent in the transaction stack. */
83 :
84 837257319 : int match = FD_UNLIKELY( cur_txn ) ? /* opt for root find (FIXME: eliminate branch with cmov into txn_xid_eq?) */
85 296980062 : fd_funk_txn_xid_eq( &cur_txn->xid, ele->pair.xid ) :
86 837257319 : fd_funk_txn_xid_eq_root( ele->pair.xid );
87 :
88 837257319 : if( FD_LIKELY( match ) ) {
89 444670257 : if( txn_out ) *txn_out = cur_txn;
90 444670257 : return ( FD_UNLIKELY( ele->flags & FD_FUNK_REC_FLAG_ERASE ) ? NULL : ele );
91 444670257 : }
92 :
93 392587062 : if( cur_txn == NULL ) break;
94 392587062 : }
95 :
96 635690388 : }
97 491081611 : cur = &ele->map_next;
98 491081611 : }
99 :
100 5150199 : if( txn_out ) *txn_out = NULL;
101 5150199 : return NULL;
102 449820456 : }
103 :
104 : void *
105 : fd_funk_rec_query_safe( fd_funk_t * funk,
106 : fd_funk_rec_key_t const * key,
107 : fd_valloc_t valloc,
108 0 : ulong * result_len ) {
109 0 : return fd_funk_rec_query_xid_safe( funk, key, fd_funk_root( funk ), valloc, result_len );
110 0 : }
111 :
112 : void *
113 : fd_funk_rec_query_xid_safe( fd_funk_t * funk,
114 : fd_funk_rec_key_t const * key,
115 : fd_funk_txn_xid_t const * xid,
116 : fd_valloc_t valloc,
117 0 : ulong * result_len ) {
118 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
119 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
120 :
121 0 : fd_funk_xid_key_pair_t pair[1];
122 0 : fd_funk_xid_key_pair_init( pair, xid, key );
123 :
124 0 : void * result = NULL;
125 0 : ulong alloc_len = 0;
126 0 : *result_len = 0;
127 0 : for(;;) {
128 0 : ulong lock_start;
129 0 : for(;;) {
130 0 : lock_start = funk->write_lock;
131 0 : if( FD_LIKELY(!(lock_start&1UL)) ) break;
132 : /* Funk is currently write locked */
133 0 : FD_SPIN_PAUSE();
134 0 : }
135 0 : FD_COMPILER_MFENCE();
136 :
137 0 : fd_funk_rec_t const * rec = fd_funk_rec_map_query_safe( rec_map, pair, NULL );
138 0 : if( FD_UNLIKELY( rec == NULL ) ) {
139 0 : FD_COMPILER_MFENCE();
140 0 : if( lock_start == funk->write_lock ) return NULL;
141 0 : } else {
142 0 : uint val_sz = rec->val_sz;
143 0 : if( val_sz ) {
144 0 : if( result == NULL ) {
145 0 : result = fd_valloc_malloc( valloc, FD_FUNK_VAL_ALIGN, val_sz );
146 0 : alloc_len = val_sz;
147 0 : } else if ( val_sz > alloc_len ) {
148 0 : fd_valloc_free( valloc, result );
149 0 : result = fd_valloc_malloc( valloc, FD_FUNK_VAL_ALIGN, val_sz );
150 0 : alloc_len = val_sz;
151 0 : }
152 0 : fd_memcpy( result, fd_wksp_laddr_fast( wksp, rec->val_gaddr ), val_sz );
153 0 : }
154 0 : *result_len = val_sz;
155 0 : FD_COMPILER_MFENCE();
156 0 : if( lock_start == funk->write_lock ) return result;
157 0 : }
158 :
159 : /* else try again */
160 0 : FD_SPIN_PAUSE();
161 0 : }
162 0 : }
163 :
164 : int
165 : fd_funk_rec_test( fd_funk_t * funk,
166 169741080 : fd_funk_rec_t const * rec ) {
167 :
168 169741080 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
169 :
170 108650340 : fd_wksp_t * wksp = fd_funk_wksp( funk );
171 :
172 108650340 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
173 :
174 108650340 : ulong rec_max = funk->rec_max;
175 :
176 108650340 : ulong rec_idx = (ulong)(rec - rec_map);
177 :
178 108650340 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
179 91636110 : return FD_FUNK_ERR_INVAL;
180 :
181 17014230 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) ) return FD_FUNK_ERR_KEY;
182 :
183 16168071 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
184 :
185 16168071 : if( FD_UNLIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) { /* Rec in last published, opt for lots recs */
186 :
187 13044636 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) return FD_FUNK_ERR_FROZEN;
188 :
189 13044636 : } else { /* Rec in in-prep */
190 :
191 3123435 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
192 3123435 : ulong txn_max = funk->txn_max;
193 :
194 3123435 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) return FD_FUNK_ERR_XID; /* TODO: consider LOG_CRIT here? */
195 :
196 3123435 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) ) return FD_FUNK_ERR_FROZEN;
197 :
198 3123435 : }
199 :
200 904707 : return FD_FUNK_SUCCESS;
201 16168071 : }
202 :
203 : fd_funk_rec_t *
204 : fd_funk_rec_modify( fd_funk_t * funk,
205 499575084 : fd_funk_rec_t const * rec ) {
206 499575084 : if( FD_UNLIKELY( (!funk) | (!rec) ) )
207 91636110 : return NULL;
208 407938974 : fd_funk_check_write( funk );
209 :
210 407938974 : fd_wksp_t * wksp = fd_funk_wksp( funk );
211 :
212 407938974 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
213 :
214 407938974 : ulong rec_max = funk->rec_max;
215 :
216 407938974 : ulong rec_idx = (ulong)(rec - rec_map);
217 :
218 407938974 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
219 61090740 : return NULL;
220 :
221 346848234 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) )
222 846159 : return NULL; /* Not live */
223 :
224 346002075 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
225 :
226 346002075 : if( fd_funk_txn_idx_is_null( txn_idx ) ) { /* Modifying last published transaction */
227 :
228 217054056 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) )
229 206171640 : return NULL;
230 :
231 217054056 : } else { /* Modifying an in-prep transaction */
232 128948019 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
233 :
234 128948019 : ulong txn_max = funk->txn_max;
235 :
236 128948019 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
237 :
238 128948019 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) )
239 64368258 : return NULL;
240 128948019 : }
241 :
242 75462177 : return (fd_funk_rec_t *)rec;
243 346002075 : }
244 :
245 : FD_FN_PURE int
246 : fd_funk_rec_is_modified( fd_funk_t * funk,
247 0 : fd_funk_rec_t const * rec ) {
248 :
249 0 : if( FD_UNLIKELY( (!funk) | (!rec) ) ) return 0;
250 :
251 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
252 :
253 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
254 0 : ulong rec_max = funk->rec_max;
255 0 : ulong rec_idx = (ulong)(rec - rec_map);
256 0 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
257 0 : FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
258 :
259 0 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
260 0 : if( fd_funk_txn_idx_is_null( txn_idx ) )
261 0 : return -1;
262 0 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
263 0 : ulong txn_max = funk->txn_max;
264 0 : if( FD_UNLIKELY( txn_idx>=txn_max ) )
265 0 : FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
266 0 : fd_funk_txn_t * txn = txn_map + txn_idx;
267 :
268 0 : void * val = fd_funk_val( rec, wksp );
269 :
270 0 : do {
271 : /* Go to the parent transaction */
272 0 : fd_funk_xid_key_pair_t pair[1];
273 0 : txn_idx = fd_funk_txn_idx( txn->parent_cidx );
274 0 : if ( fd_funk_txn_idx_is_null( txn_idx ) ) {
275 0 : txn = NULL;
276 0 : fd_funk_xid_key_pair_init( pair, fd_funk_root( funk ), rec->pair.key );
277 0 : } else {
278 0 : txn = txn_map + txn_idx;
279 0 : fd_funk_xid_key_pair_init( pair, fd_funk_txn_xid( txn ), rec->pair.key );
280 0 : }
281 :
282 0 : fd_funk_rec_t const * rec2 = fd_funk_rec_map_query_const( rec_map, pair, NULL );
283 0 : if ( rec2 ) {
284 0 : if ( rec->val_sz != rec2->val_sz )
285 0 : return 1;
286 0 : void * val2 = fd_funk_val( rec2, wksp );
287 0 : return memcmp(val, val2, rec->val_sz) != 0;
288 0 : }
289 0 : } while (txn);
290 :
291 0 : return 1;
292 0 : }
293 :
294 : fd_funk_rec_t const *
295 : fd_funk_rec_insert( fd_funk_t * funk,
296 : fd_funk_txn_t * txn,
297 : fd_funk_rec_key_t const * key,
298 172135473 : int * opt_err ) {
299 :
300 172135473 : if( FD_UNLIKELY( (!funk) | /* NULL funk */
301 172135473 : (!key ) ) ) { /* NULL key */
302 122181480 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
303 122181480 : return NULL;
304 122181480 : }
305 49953993 : fd_funk_check_write( funk );
306 :
307 49953993 : fd_wksp_t * wksp = fd_funk_wksp( funk );
308 :
309 49953993 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
310 :
311 49953993 : ulong rec_max = funk->rec_max;
312 :
313 49953993 : if( FD_UNLIKELY( fd_funk_rec_map_is_full( rec_map ) ) ) {
314 20210664 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_REC );
315 20210664 : return NULL;
316 20210664 : }
317 :
318 29743329 : ulong txn_idx;
319 29743329 : ulong * _rec_head_idx;
320 29743329 : ulong * _rec_tail_idx;
321 29743329 : fd_funk_xid_key_pair_t pair[1];
322 :
323 29743329 : if( !txn ) { /* Modifying last published */
324 :
325 5671542 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) {
326 5018442 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
327 5018442 : return NULL;
328 5018442 : }
329 :
330 653100 : txn_idx = FD_FUNK_TXN_IDX_NULL;
331 653100 : _rec_head_idx = &funk->rec_head_idx;
332 653100 : _rec_tail_idx = &funk->rec_tail_idx;
333 :
334 653100 : fd_funk_xid_key_pair_init( pair, fd_funk_root( funk ), key );
335 :
336 653100 : fd_funk_rec_t * rec = fd_funk_rec_map_query( rec_map, pair, NULL );
337 :
338 653100 : if( FD_UNLIKELY( rec ) ) { /* Already a record present */
339 :
340 : /* However, if the record is marked for erasure, reset the flag and
341 : return the record. */
342 652803 : if( rec->flags & FD_FUNK_REC_FLAG_ERASE ) {
343 450093 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
344 450093 : return rec;
345 450093 : }
346 :
347 202710 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_KEY );
348 202710 : return NULL;
349 652803 : }
350 :
351 24071787 : } else { /* Modifying in-prep */
352 :
353 24071787 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
354 :
355 24071787 : ulong txn_max = funk->txn_max;
356 :
357 24071787 : txn_idx = (ulong)(txn - txn_map);
358 24071787 : _rec_head_idx = &txn->rec_head_idx;
359 24071787 : _rec_tail_idx = &txn->rec_tail_idx;
360 :
361 24071787 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(txn_map+txn_idx)) /* Bad alignment */ ) ) {
362 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
363 0 : return NULL;
364 0 : }
365 :
366 24071787 : if( FD_UNLIKELY( !fd_funk_txn_map_query( txn_map, fd_funk_txn_xid( txn ), NULL ) ) ) {
367 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
368 0 : return NULL;
369 0 : }
370 :
371 24071787 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( txn ) ) ) {
372 15378042 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
373 15378042 : return NULL;
374 15378042 : }
375 :
376 8693745 : fd_funk_xid_key_pair_init( pair, fd_funk_txn_xid( txn ), key );
377 :
378 8693745 : fd_funk_rec_t * rec = fd_funk_rec_map_query( rec_map, pair, NULL );
379 :
380 8693745 : if( FD_UNLIKELY( rec ) ) { /* Already a record present */
381 :
382 : /* The user is trying insert a record update on top of
383 : a pre-existing of record update. We fail with ERR_KEY to
384 : prevent accidentally discarding any previous updates
385 : unintentionally. */
386 :
387 837663 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) {
388 58485 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
389 58485 : return rec;
390 58485 : }
391 :
392 779178 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_KEY );
393 779178 : return NULL;
394 :
395 837663 : }
396 :
397 8693745 : }
398 :
399 7856379 : fd_funk_rec_t * rec = fd_funk_rec_map_insert( rec_map, pair );
400 7856379 : ulong rec_idx = (ulong)(rec - rec_map);
401 7856379 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
402 :
403 7856379 : ulong rec_prev_idx = *_rec_tail_idx;
404 :
405 7856379 : int first_born = fd_funk_rec_idx_is_null( rec_prev_idx );
406 7856379 : if( FD_UNLIKELY( !first_born ) ) {
407 6127602 : if( FD_UNLIKELY( rec_prev_idx>=rec_max ) )
408 0 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" ));
409 6127602 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_prev_idx ].txn_cidx )!=txn_idx ) )
410 0 : FD_LOG_CRIT(( "memory corruption detected (mismatch)" ));
411 6127602 : }
412 :
413 7856379 : rec->prev_idx = rec_prev_idx;
414 7856379 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
415 7856379 : rec->txn_cidx = fd_funk_txn_cidx( txn_idx );
416 7856379 : rec->tag = 0U;
417 7856379 : rec->flags = 0UL;
418 :
419 7856379 : if( first_born ) *_rec_head_idx = rec_idx;
420 6127602 : else rec_map[ rec_prev_idx ].next_idx = rec_idx;
421 :
422 7856379 : *_rec_tail_idx = rec_idx;
423 :
424 7856379 : fd_funk_val_init( rec );
425 7856379 : fd_funk_part_init( rec );
426 :
427 7856379 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_SUCCESS );
428 7856379 : return rec;
429 7856379 : }
430 :
431 : int
432 : fd_funk_rec_remove( fd_funk_t * funk,
433 : fd_funk_rec_t * rec,
434 162652122 : ulong erase_data ) {
435 :
436 162652122 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
437 101561382 : fd_funk_check_write( funk );
438 :
439 101561382 : fd_wksp_t * wksp = fd_funk_wksp( funk );
440 :
441 101561382 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
442 :
443 101561382 : ulong rec_max = funk->rec_max;
444 :
445 101561382 : ulong rec_idx = (ulong)(rec - rec_map);
446 :
447 101561382 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
448 91636110 : return FD_FUNK_ERR_INVAL;
449 :
450 9925272 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) ) return FD_FUNK_ERR_KEY;
451 :
452 9925272 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
453 :
454 9925272 : if( FD_UNLIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) { /* Removing from last published, opt for lots recs, rand remove */
455 :
456 7132596 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) return FD_FUNK_ERR_FROZEN;
457 :
458 7132596 : } else {
459 :
460 2792676 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
461 2792676 : ulong txn_max = funk->txn_max;
462 :
463 2792676 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
464 :
465 2792676 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) ) return FD_FUNK_ERR_FROZEN;
466 2792676 : }
467 :
468 : /* If this was already marked for erase, we are done (we already
469 : flushed the value when it was first marked for erase) */
470 :
471 2363298 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) return FD_FUNK_SUCCESS;
472 :
473 : /* Flush the value and leave a tombstone behind. In theory, this can
474 : lead to an unbounded number of records, but for application
475 : reasons, we need to remember what was deleted. */
476 :
477 2135382 : fd_funk_val_flush( rec, fd_funk_alloc( funk, wksp ), wksp );
478 2135382 : fd_funk_part_set_intern( fd_funk_get_partvec( funk, wksp ), rec_map, rec, FD_FUNK_PART_NULL );
479 2135382 : rec->flags |= FD_FUNK_REC_FLAG_ERASE;
480 :
481 : /* At this point, the 5 most significant bytes should store data about the
482 : transaction that the record was updated in. */
483 :
484 2135382 : fd_funk_rec_set_erase_data( rec, erase_data );
485 :
486 2135382 : return FD_FUNK_SUCCESS;
487 2363298 : }
488 :
489 : int
490 : fd_funk_rec_forget( fd_funk_t * funk,
491 : fd_funk_rec_t ** recs,
492 0 : ulong recs_cnt ) {
493 0 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
494 0 : fd_funk_check_write( funk );
495 :
496 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
497 :
498 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
499 :
500 0 : ulong rec_max = funk->rec_max;
501 :
502 0 : for( ulong i = 0; i < recs_cnt; ++i ) {
503 0 : fd_funk_rec_t * rec = recs[i];
504 0 : ulong rec_idx = (ulong)(rec - rec_map);
505 :
506 0 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
507 0 : return FD_FUNK_ERR_INVAL;
508 :
509 0 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
510 0 : fd_funk_xid_key_pair_t const * key = fd_funk_rec_pair( rec );
511 0 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( txn_idx ) || /* Must be published */
512 0 : !( rec->flags & FD_FUNK_REC_FLAG_ERASE ) || /* Must be removed */
513 0 : rec!=fd_funk_rec_map_query_const( rec_map, key, NULL ) ) ) {
514 0 : return FD_FUNK_ERR_KEY;
515 0 : }
516 :
517 0 : ulong prev_idx = rec->prev_idx;
518 0 : ulong next_idx = rec->next_idx;
519 0 : if( fd_funk_rec_idx_is_null( prev_idx ) ) funk->rec_head_idx = next_idx;
520 0 : else rec_map[ prev_idx ].next_idx = next_idx;
521 0 : if( fd_funk_rec_idx_is_null( next_idx ) ) funk->rec_tail_idx = prev_idx;
522 0 : else rec_map[ next_idx ].prev_idx = prev_idx;
523 :
524 0 : fd_funk_rec_map_remove( rec_map, key );
525 0 : }
526 :
527 0 : return FD_FUNK_SUCCESS;
528 0 : }
529 :
530 : void
531 2135382 : fd_funk_rec_set_erase_data( fd_funk_rec_t * rec, ulong erase_data ) {
532 2135382 : rec->flags |= ((erase_data & 0xFFFFFFFFFFUL) << (sizeof(unsigned long) * 8 - 40));
533 2135382 : }
534 :
535 : ulong
536 0 : fd_funk_rec_get_erase_data( fd_funk_rec_t const * rec ) {
537 0 : return (rec->flags >> (sizeof(unsigned long) * 8 - 40)) & 0xFFFFFFFFFFUL;
538 0 : }
539 :
540 : fd_funk_rec_t *
541 : fd_funk_rec_write_prepare( fd_funk_t * funk,
542 : fd_funk_txn_t * txn,
543 : fd_funk_rec_key_t const * key,
544 : ulong min_val_size,
545 : int do_create,
546 : fd_funk_rec_t const * irec,
547 12703485 : int * opt_err ) {
548 :
549 12703485 : fd_wksp_t * wksp = fd_funk_wksp( funk );
550 :
551 12703485 : fd_funk_rec_t * rec = NULL;
552 12703485 : fd_funk_rec_t const * rec_con = NULL;
553 12703485 : if ( FD_LIKELY (NULL == irec ) )
554 12703476 : rec_con = fd_funk_rec_query_global( funk, txn, key, NULL );
555 9 : else
556 9 : rec_con = irec;
557 :
558 : /* We are able to handle tombstones in this case because we treat an erased
559 : record as not existing. */
560 :
561 12703485 : if ( FD_UNLIKELY( rec_con && !(rec_con->flags & FD_FUNK_REC_FLAG_ERASE) ) ) {
562 : /* We have an incarnation of the record */
563 8596071 : if ( txn == fd_funk_rec_txn( rec_con, fd_funk_txn_map( funk, wksp ) ) ) {
564 : /* The record is already in the right transaction */
565 3788121 : rec = fd_funk_rec_modify( funk, rec_con );
566 3788121 : if ( !rec ) {
567 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
568 0 : return NULL;
569 0 : }
570 :
571 4807950 : } else {
572 : /* Copy the record into the transaction */
573 4807950 : rec = fd_funk_rec_modify( funk, fd_funk_rec_insert( funk, txn, key, opt_err ) );
574 4807950 : if ( !rec )
575 0 : return NULL;
576 4807950 : rec = fd_funk_val_copy( rec, fd_funk_val_const(rec_con, wksp), fd_funk_val_sz(rec_con),
577 4807950 : fd_ulong_max( fd_funk_val_sz(rec_con), min_val_size ), fd_funk_alloc( funk, wksp ), wksp, opt_err );
578 4807950 : if ( !rec ) {
579 0 : return NULL;
580 0 : }
581 4807950 : }
582 :
583 8596071 : } else {
584 4107414 : if (!do_create) {
585 1566723 : if( opt_err ) *opt_err = FD_FUNK_ERR_KEY;
586 1566723 : return NULL;
587 1566723 : }
588 :
589 : /* Create a new record */
590 2540691 : rec = fd_funk_rec_modify( funk, fd_funk_rec_insert( funk, txn, key, opt_err ) );
591 2540691 : if ( !rec )
592 0 : return NULL;
593 2540691 : }
594 :
595 : /* Grow the record to the right size */
596 11136762 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
597 11136762 : if ( fd_funk_val_sz( rec ) < min_val_size ) {
598 2488917 : rec = fd_funk_val_truncate( rec, min_val_size, fd_funk_alloc( funk, wksp ), wksp, opt_err );
599 2488917 : }
600 :
601 11136762 : return rec;
602 12703485 : }
603 :
604 : int
605 22275108 : fd_funk_rec_verify( fd_funk_t * funk ) {
606 22275108 : fd_wksp_t * wksp = fd_funk_wksp( funk ); /* Previously verified */
607 22275108 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp ); /* Previously verified */
608 22275108 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp ); /* Previously verified */
609 22275108 : ulong txn_max = funk->txn_max; /* Previously verified */
610 22275108 : ulong rec_max = funk->rec_max; /* Previously verified */
611 :
612 : /* At this point, txn_map has been extensively verified */
613 :
614 5699238888 : # define TEST(c) do { \
615 5699238888 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
616 5699238888 : } while(0)
617 :
618 22275108 : TEST( !fd_funk_rec_map_verify( rec_map ) );
619 :
620 : /* Iterate over all records in use */
621 :
622 22275108 : for( fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter_init( rec_map );
623 903401892 : !fd_funk_rec_map_iter_done( rec_map, iter );
624 881126784 : iter = fd_funk_rec_map_iter_next( rec_map, iter ) ) {
625 881126784 : fd_funk_rec_t * rec = fd_funk_rec_map_iter_ele( rec_map, iter );
626 :
627 : /* Make sure every record either links up with the last published
628 : transaction or an in-prep transaction and the flags are sane. */
629 :
630 881126784 : fd_funk_txn_xid_t const * txn_xid = fd_funk_rec_xid( rec );
631 881126784 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
632 :
633 881126784 : if( fd_funk_txn_idx_is_null( txn_idx ) ) { /* This is a record from the last published transaction */
634 :
635 629124942 : TEST( fd_funk_txn_xid_eq_root( txn_xid ) );
636 :
637 629124942 : } else { /* This is a record from an in-prep transaction */
638 :
639 252001842 : TEST( txn_idx<txn_max );
640 252001842 : fd_funk_txn_t const * txn = fd_funk_txn_map_query_const( txn_map, txn_xid, NULL );
641 252001842 : TEST( txn );
642 252001842 : TEST( txn==(txn_map+txn_idx) );
643 :
644 252001842 : }
645 881126784 : }
646 :
647 : /* Clear record tags and then verify the forward and reverse linkage */
648 :
649 19252110372 : for( ulong rec_idx=0UL; rec_idx<rec_max; rec_idx++ ) rec_map[ rec_idx ].tag = 0U;
650 :
651 22275108 : ulong rec_cnt = fd_funk_rec_map_key_cnt( rec_map );
652 :
653 22275108 : do {
654 22275108 : ulong cnt = 0UL;
655 :
656 22275108 : ulong txn_idx = FD_FUNK_TXN_IDX_NULL;
657 22275108 : ulong rec_idx = funk->rec_head_idx;
658 651400050 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
659 629124942 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==0U );
660 629124942 : rec_map[ rec_idx ].tag = 1U;
661 629124942 : cnt++;
662 629124942 : fd_funk_rec_t const * rec2 = fd_funk_rec_query_global( funk, NULL, rec_map[ rec_idx ].pair.key, NULL );
663 629124942 : if( FD_UNLIKELY( rec_map[ rec_idx ].flags & FD_FUNK_REC_FLAG_ERASE ) )
664 286851630 : TEST( rec2 == NULL );
665 342273312 : else
666 342273312 : TEST( rec2 = rec_map + rec_idx );
667 629124942 : ulong next_idx = rec_map[ rec_idx ].next_idx;
668 629124942 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_map[ next_idx ].prev_idx==rec_idx );
669 629124942 : rec_idx = next_idx;
670 629124942 : }
671 22275108 : for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
672 119006091 : !fd_funk_txn_map_iter_done( txn_map, iter );
673 96730983 : iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
674 96730983 : fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
675 :
676 96730983 : ulong txn_idx = (ulong)(txn-txn_map);
677 96730983 : ulong rec_idx = txn->rec_head_idx;
678 348732825 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
679 252001842 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==0U );
680 252001842 : rec_map[ rec_idx ].tag = 1U;
681 252001842 : cnt++;
682 252001842 : fd_funk_rec_t const * rec2 = fd_funk_rec_query_global( funk, txn, rec_map[ rec_idx ].pair.key, NULL );
683 252001842 : if( FD_UNLIKELY( rec_map[ rec_idx ].flags & FD_FUNK_REC_FLAG_ERASE ) )
684 68301585 : TEST( rec2 == NULL );
685 183700257 : else
686 183700257 : TEST( rec2 = rec_map + rec_idx );
687 252001842 : ulong next_idx = rec_map[ rec_idx ].next_idx;
688 252001842 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_map[ next_idx ].prev_idx==rec_idx );
689 252001842 : rec_idx = next_idx;
690 252001842 : }
691 96730983 : }
692 :
693 22275108 : TEST( cnt==rec_cnt );
694 22275108 : } while(0);
695 :
696 22275108 : do {
697 22275108 : ulong cnt = 0UL;
698 :
699 22275108 : ulong txn_idx = FD_FUNK_TXN_IDX_NULL;
700 22275108 : ulong rec_idx = funk->rec_tail_idx;
701 651400050 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
702 629124942 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==1U );
703 629124942 : rec_map[ rec_idx ].tag = 2U;
704 629124942 : cnt++;
705 629124942 : ulong prev_idx = rec_map[ rec_idx ].prev_idx;
706 629124942 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_map[ prev_idx ].next_idx==rec_idx );
707 629124942 : rec_idx = prev_idx;
708 629124942 : }
709 :
710 22275108 : for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
711 119006091 : !fd_funk_txn_map_iter_done( txn_map, iter );
712 96730983 : iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
713 96730983 : fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
714 :
715 96730983 : ulong txn_idx = (ulong)(txn-txn_map);
716 96730983 : ulong rec_idx = txn->rec_tail_idx;
717 348732825 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
718 252001842 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==1U );
719 252001842 : rec_map[ rec_idx ].tag = 2U;
720 252001842 : cnt++;
721 252001842 : ulong prev_idx = rec_map[ rec_idx ].prev_idx;
722 252001842 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_map[ prev_idx ].next_idx==rec_idx );
723 252001842 : rec_idx = prev_idx;
724 252001842 : }
725 96730983 : }
726 :
727 22275108 : TEST( cnt==rec_cnt );
728 22275108 : } while(0);
729 :
730 22275108 : # undef TEST
731 :
732 22275108 : return FD_FUNK_SUCCESS;
733 22275108 : }
|
