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 20924398686 : #define MAP_T fd_funk_rec_t
7 : #define MAP_KEY_T fd_funk_xid_key_pair_t
8 4018065 : #define MAP_KEY pair
9 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1))
10 1490515107 : #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 20113914522 : #define MAP_NEXT map_next
13 6606334197 : #define MAP_HASH map_hash
14 27 : #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 453671217 : fd_funk_txn_t const ** txn_out ) {
49 453671217 : if( FD_UNLIKELY( (!funk) | (!key) ) ) return NULL;
50 :
51 362035107 : fd_wksp_t * wksp = fd_funk_wksp( funk );
52 :
53 362035107 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
54 362035107 : 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 362035107 : fd_funk_rec_map_private_t * priv = fd_funk_rec_map_private( rec_map );
67 362035107 : ulong hash = fd_funk_rec_key_hash( key, priv->seed );
68 362035107 : ulong * head = fd_funk_rec_map_private_list( priv ) + ( hash & (priv->list_cnt-1UL) );
69 362035107 : ulong * cur = head;
70 :
71 826713966 : for(;;) {
72 826713966 : ulong ele_idx = fd_funk_rec_map_private_unbox_idx( *cur );
73 826713966 : if( fd_funk_rec_map_private_is_null( ele_idx ) ) break;
74 826695693 : fd_funk_rec_t * ele = rec_map + ele_idx;
75 826695693 : 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 739991034 : 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 739991034 : int match = FD_UNLIKELY( cur_txn ) ? /* opt for root find (FIXME: eliminate branch with cmov into txn_xid_eq?) */
85 280263630 : fd_funk_txn_xid_eq( &cur_txn->xid, ele->pair.xid ) :
86 739991034 : fd_funk_txn_xid_eq_root( ele->pair.xid );
87 :
88 739991034 : if( FD_LIKELY( match ) ) {
89 362016834 : if( txn_out ) *txn_out = cur_txn;
90 362016834 : return ( FD_UNLIKELY( ele->flags & FD_FUNK_REC_FLAG_ERASE ) ? NULL : ele );
91 362016834 : }
92 :
93 377974200 : if( cur_txn == NULL ) break;
94 377974200 : }
95 :
96 546190518 : }
97 464678859 : cur = &ele->map_next;
98 464678859 : }
99 :
100 18273 : if( txn_out ) *txn_out = NULL;
101 18273 : return NULL;
102 362035107 : }
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 491588346 : fd_funk_rec_t const * rec ) {
206 491588346 : if( FD_UNLIKELY( (!funk) | (!rec) ) )
207 91636110 : return NULL;
208 399952236 : fd_funk_check_write( funk );
209 :
210 399952236 : fd_wksp_t * wksp = fd_funk_wksp( funk );
211 :
212 399952236 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
213 :
214 399952236 : ulong rec_max = funk->rec_max;
215 :
216 399952236 : ulong rec_idx = (ulong)(rec - rec_map);
217 :
218 399952236 : 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 338861496 : 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 338015337 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
225 :
226 338015337 : if( fd_funk_txn_idx_is_null( txn_idx ) ) { /* Modifying last published transaction */
227 :
228 214354254 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) )
229 206171640 : return NULL;
230 :
231 214354254 : } else { /* Modifying an in-prep transaction */
232 123661083 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
233 :
234 123661083 : ulong txn_max = funk->txn_max;
235 :
236 123661083 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
237 :
238 123661083 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) )
239 64368258 : return NULL;
240 123661083 : }
241 :
242 67475439 : return (fd_funk_rec_t *)rec;
243 338015337 : }
244 :
245 : 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 167801811 : int * opt_err ) {
299 :
300 167801811 : if( FD_UNLIKELY( (!funk) | /* NULL funk */
301 167801811 : (!key ) ) ) { /* NULL key */
302 122181480 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_INVAL );
303 122181480 : return NULL;
304 122181480 : }
305 45620331 : fd_funk_check_write( funk );
306 :
307 45620331 : fd_wksp_t * wksp = fd_funk_wksp( funk );
308 :
309 45620331 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
310 :
311 45620331 : ulong rec_max = funk->rec_max;
312 :
313 45620331 : 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 25409667 : ulong txn_idx;
319 25409667 : ulong * _rec_head_idx;
320 25409667 : ulong * _rec_tail_idx;
321 25409667 : fd_funk_xid_key_pair_t pair[1];
322 :
323 25409667 : if( !txn ) { /* Modifying last published */
324 :
325 5222655 : 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 204213 : txn_idx = FD_FUNK_TXN_IDX_NULL;
331 204213 : _rec_head_idx = &funk->rec_head_idx;
332 204213 : _rec_tail_idx = &funk->rec_tail_idx;
333 :
334 204213 : fd_funk_xid_key_pair_init( pair, fd_funk_root( funk ), key );
335 :
336 204213 : fd_funk_rec_t * rec = fd_funk_rec_map_query( rec_map, pair, NULL );
337 :
338 204213 : 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 203952 : if( rec->flags & FD_FUNK_REC_FLAG_ERASE ) {
343 1242 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
344 1242 : return rec;
345 1242 : }
346 :
347 202710 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_KEY );
348 202710 : return NULL;
349 203952 : }
350 :
351 20187012 : } else { /* Modifying in-prep */
352 :
353 20187012 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
354 :
355 20187012 : ulong txn_max = funk->txn_max;
356 :
357 20187012 : txn_idx = (ulong)(txn - txn_map);
358 20187012 : _rec_head_idx = &txn->rec_head_idx;
359 20187012 : _rec_tail_idx = &txn->rec_tail_idx;
360 :
361 20187012 : 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 20187012 : 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 20187012 : 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 4808970 : fd_funk_xid_key_pair_init( pair, fd_funk_txn_xid( txn ), key );
377 :
378 4808970 : fd_funk_rec_t * rec = fd_funk_rec_map_query( rec_map, pair, NULL );
379 :
380 4808970 : 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 791166 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) {
388 11988 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
389 11988 : return rec;
390 11988 : }
391 :
392 779178 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_KEY );
393 779178 : return NULL;
394 :
395 791166 : }
396 :
397 4808970 : }
398 :
399 4018065 : fd_funk_rec_t * rec = fd_funk_rec_map_insert( rec_map, pair );
400 4018065 : ulong rec_idx = (ulong)(rec - rec_map);
401 4018065 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
402 :
403 4018065 : ulong rec_prev_idx = *_rec_tail_idx;
404 :
405 4018065 : int first_born = fd_funk_rec_idx_is_null( rec_prev_idx );
406 4018065 : if( FD_UNLIKELY( !first_born ) ) {
407 3346824 : if( FD_UNLIKELY( rec_prev_idx>=rec_max ) )
408 0 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" ));
409 3346824 : 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 3346824 : }
412 :
413 4018065 : rec->prev_idx = rec_prev_idx;
414 4018065 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
415 4018065 : rec->txn_cidx = fd_funk_txn_cidx( txn_idx );
416 4018065 : rec->tag = 0U;
417 4018065 : rec->flags = 0UL;
418 :
419 4018065 : if( first_born ) *_rec_head_idx = rec_idx;
420 3346824 : else rec_map[ rec_prev_idx ].next_idx = rec_idx;
421 :
422 4018065 : *_rec_tail_idx = rec_idx;
423 :
424 4018065 : fd_funk_val_init( rec );
425 :
426 4018065 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_SUCCESS );
427 4018065 : return rec;
428 4018065 : }
429 :
430 : int
431 : fd_funk_rec_remove( fd_funk_t * funk,
432 : fd_funk_rec_t * rec,
433 161603520 : ulong erase_data ) {
434 :
435 161603520 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
436 100512780 : fd_funk_check_write( funk );
437 :
438 100512780 : fd_wksp_t * wksp = fd_funk_wksp( funk );
439 :
440 100512780 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
441 :
442 100512780 : ulong rec_max = funk->rec_max;
443 :
444 100512780 : ulong rec_idx = (ulong)(rec - rec_map);
445 :
446 100512780 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
447 91636110 : return FD_FUNK_ERR_INVAL;
448 :
449 8876670 : if( FD_UNLIKELY( rec!=fd_funk_rec_map_query_const( rec_map, fd_funk_rec_pair( rec ), NULL ) ) ) return FD_FUNK_ERR_KEY;
450 :
451 8876670 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
452 :
453 8876670 : if( FD_UNLIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) { /* Removing from last published, opt for lots recs, rand remove */
454 :
455 6683196 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) return FD_FUNK_ERR_FROZEN;
456 :
457 6683196 : } else {
458 :
459 2193474 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
460 2193474 : ulong txn_max = funk->txn_max;
461 :
462 2193474 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
463 :
464 2193474 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( &txn_map[ txn_idx ] ) ) ) return FD_FUNK_ERR_FROZEN;
465 2193474 : }
466 :
467 : /* If this was already marked for erase, we are done (we already
468 : flushed the value when it was first marked for erase) */
469 :
470 1314696 : if( FD_UNLIKELY( rec->flags & FD_FUNK_REC_FLAG_ERASE ) ) return FD_FUNK_SUCCESS;
471 :
472 : /* Flush the value and leave a tombstone behind. In theory, this can
473 : lead to an unbounded number of records, but for application
474 : reasons, we need to remember what was deleted. */
475 :
476 1086780 : fd_funk_val_flush( rec, fd_funk_alloc( funk, wksp ), wksp );
477 1086780 : rec->flags |= FD_FUNK_REC_FLAG_ERASE;
478 :
479 : /* At this point, the 5 most significant bytes should store data about the
480 : transaction that the record was updated in. */
481 :
482 1086780 : fd_funk_rec_set_erase_data( rec, erase_data );
483 :
484 1086780 : return FD_FUNK_SUCCESS;
485 1314696 : }
486 :
487 : int
488 : fd_funk_rec_forget( fd_funk_t * funk,
489 : fd_funk_rec_t ** recs,
490 0 : ulong recs_cnt ) {
491 0 : if( FD_UNLIKELY( !funk ) ) return FD_FUNK_ERR_INVAL;
492 0 : fd_funk_check_write( funk );
493 :
494 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
495 :
496 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
497 :
498 0 : ulong rec_max = funk->rec_max;
499 :
500 0 : for( ulong i = 0; i < recs_cnt; ++i ) {
501 0 : fd_funk_rec_t * rec = recs[i];
502 0 : ulong rec_idx = (ulong)(rec - rec_map);
503 :
504 0 : if( FD_UNLIKELY( (rec_idx>=rec_max) /* Out of map (incl NULL) */ | (rec!=(rec_map+rec_idx)) /* Bad alignment */ ) )
505 0 : return FD_FUNK_ERR_INVAL;
506 :
507 0 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
508 0 : fd_funk_xid_key_pair_t const * key = fd_funk_rec_pair( rec );
509 0 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( txn_idx ) || /* Must be published */
510 0 : !( rec->flags & FD_FUNK_REC_FLAG_ERASE ) || /* Must be removed */
511 0 : rec!=fd_funk_rec_map_query_const( rec_map, key, NULL ) ) ) {
512 0 : return FD_FUNK_ERR_KEY;
513 0 : }
514 :
515 0 : ulong prev_idx = rec->prev_idx;
516 0 : ulong next_idx = rec->next_idx;
517 0 : if( fd_funk_rec_idx_is_null( prev_idx ) ) funk->rec_head_idx = next_idx;
518 0 : else rec_map[ prev_idx ].next_idx = next_idx;
519 0 : if( fd_funk_rec_idx_is_null( next_idx ) ) funk->rec_tail_idx = prev_idx;
520 0 : else rec_map[ next_idx ].prev_idx = prev_idx;
521 :
522 0 : fd_funk_rec_map_remove( rec_map, key );
523 0 : }
524 :
525 0 : return FD_FUNK_SUCCESS;
526 0 : }
527 :
528 : void
529 1086780 : fd_funk_rec_set_erase_data( fd_funk_rec_t * rec, ulong erase_data ) {
530 1086780 : rec->flags |= ((erase_data & 0xFFFFFFFFFFUL) << (sizeof(unsigned long) * 8 - 40));
531 1086780 : }
532 :
533 : ulong
534 0 : fd_funk_rec_get_erase_data( fd_funk_rec_t const * rec ) {
535 0 : return (rec->flags >> (sizeof(unsigned long) * 8 - 40)) & 0xFFFFFFFFFFUL;
536 0 : }
537 :
538 : fd_funk_rec_t *
539 : fd_funk_rec_write_prepare( fd_funk_t * funk,
540 : fd_funk_txn_t * txn,
541 : fd_funk_rec_key_t const * key,
542 : ulong min_val_size,
543 : int do_create,
544 : fd_funk_rec_t const * irec,
545 3150024 : int * opt_err ) {
546 :
547 3150024 : fd_wksp_t * wksp = fd_funk_wksp( funk );
548 :
549 3150024 : fd_funk_rec_t * rec = NULL;
550 3150024 : fd_funk_rec_t const * rec_con = NULL;
551 3150024 : if ( FD_LIKELY (NULL == irec ) )
552 3150015 : rec_con = fd_funk_rec_query_global( funk, txn, key, NULL );
553 9 : else
554 9 : rec_con = irec;
555 :
556 : /* We are able to handle tombstones in this case because we treat an erased
557 : record as not existing. */
558 :
559 3150024 : if ( FD_UNLIKELY( rec_con && !(rec_con->flags & FD_FUNK_REC_FLAG_ERASE) ) ) {
560 : /* We have an incarnation of the record */
561 2462856 : if ( txn == fd_funk_rec_txn( rec_con, fd_funk_txn_map( funk, wksp ) ) ) {
562 : /* The record is already in the right transaction */
563 135045 : rec = fd_funk_rec_modify( funk, rec_con );
564 135045 : if ( !rec ) {
565 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
566 0 : return NULL;
567 0 : }
568 :
569 2327811 : } else {
570 : /* Copy the record into the transaction */
571 2327811 : rec = fd_funk_rec_modify( funk, fd_funk_rec_insert( funk, txn, key, opt_err ) );
572 2327811 : if ( !rec )
573 0 : return NULL;
574 2327811 : rec = fd_funk_val_copy( rec, fd_funk_val_const(rec_con, wksp), fd_funk_val_sz(rec_con),
575 2327811 : fd_ulong_max( fd_funk_val_sz(rec_con), min_val_size ), fd_funk_alloc( funk, wksp ), wksp, opt_err );
576 2327811 : if ( !rec ) {
577 0 : return NULL;
578 0 : }
579 2327811 : }
580 :
581 2462856 : } else {
582 687168 : if (!do_create) {
583 0 : if( opt_err ) *opt_err = FD_FUNK_ERR_KEY;
584 0 : return NULL;
585 0 : }
586 :
587 : /* Create a new record */
588 687168 : rec = fd_funk_rec_modify( funk, fd_funk_rec_insert( funk, txn, key, opt_err ) );
589 687168 : if ( !rec )
590 0 : return NULL;
591 687168 : }
592 :
593 : /* Grow the record to the right size */
594 3150024 : rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
595 3150024 : if ( fd_funk_val_sz( rec ) < min_val_size ) {
596 1682415 : rec = fd_funk_val_truncate( rec, min_val_size, fd_funk_alloc( funk, wksp ), wksp, opt_err );
597 1682415 : }
598 :
599 3150024 : return rec;
600 3150024 : }
601 :
602 : int
603 9692196 : fd_funk_rec_verify( fd_funk_t * funk ) {
604 9692196 : fd_wksp_t * wksp = fd_funk_wksp( funk ); /* Previously verified */
605 9692196 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp ); /* Previously verified */
606 9692196 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp ); /* Previously verified */
607 9692196 : ulong txn_max = funk->txn_max; /* Previously verified */
608 9692196 : ulong rec_max = funk->rec_max; /* Previously verified */
609 :
610 : /* At this point, txn_map has been extensively verified */
611 :
612 4240831200 : # define TEST(c) do { \
613 4240831200 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
614 4240831200 : } while(0)
615 :
616 9692196 : TEST( !fd_funk_rec_map_verify( rec_map ) );
617 :
618 : /* Iterate over all records in use */
619 :
620 9692196 : for( fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter_init( rec_map );
621 657155244 : !fd_funk_rec_map_iter_done( rec_map, iter );
622 647463048 : iter = fd_funk_rec_map_iter_next( rec_map, iter ) ) {
623 647463048 : fd_funk_rec_t * rec = fd_funk_rec_map_iter_ele( rec_map, iter );
624 :
625 : /* Make sure every record either links up with the last published
626 : transaction or an in-prep transaction and the flags are sane. */
627 :
628 647463048 : fd_funk_txn_xid_t const * txn_xid = fd_funk_rec_xid( rec );
629 647463048 : ulong txn_idx = fd_funk_txn_idx( rec->txn_cidx );
630 :
631 647463048 : if( fd_funk_txn_idx_is_null( txn_idx ) ) { /* This is a record from the last published transaction */
632 :
633 427803564 : TEST( fd_funk_txn_xid_eq_root( txn_xid ) );
634 :
635 427803564 : } else { /* This is a record from an in-prep transaction */
636 :
637 219659484 : TEST( txn_idx<txn_max );
638 219659484 : fd_funk_txn_t const * txn = fd_funk_txn_map_query_const( txn_map, txn_xid, NULL );
639 219659484 : TEST( txn );
640 219659484 : TEST( txn==(txn_map+txn_idx) );
641 :
642 219659484 : }
643 647463048 : }
644 :
645 : /* Clear record tags and then verify the forward and reverse linkage */
646 :
647 17628914724 : for( ulong rec_idx=0UL; rec_idx<rec_max; rec_idx++ ) rec_map[ rec_idx ].tag = 0U;
648 :
649 9692196 : ulong rec_cnt = fd_funk_rec_map_key_cnt( rec_map );
650 :
651 9692196 : do {
652 9692196 : ulong cnt = 0UL;
653 :
654 9692196 : ulong txn_idx = FD_FUNK_TXN_IDX_NULL;
655 9692196 : ulong rec_idx = funk->rec_head_idx;
656 437495760 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
657 427803564 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==0U );
658 427803564 : rec_map[ rec_idx ].tag = 1U;
659 427803564 : cnt++;
660 427803564 : fd_funk_rec_t const * rec2 = fd_funk_rec_query_global( funk, NULL, rec_map[ rec_idx ].pair.key, NULL );
661 427803564 : if( FD_UNLIKELY( rec_map[ rec_idx ].flags & FD_FUNK_REC_FLAG_ERASE ) )
662 219914547 : TEST( rec2 == NULL );
663 207889017 : else
664 207889017 : TEST( rec2 = rec_map + rec_idx );
665 427803564 : ulong next_idx = rec_map[ rec_idx ].next_idx;
666 427803564 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_map[ next_idx ].prev_idx==rec_idx );
667 427803564 : rec_idx = next_idx;
668 427803564 : }
669 9692196 : for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
670 92035881 : !fd_funk_txn_map_iter_done( txn_map, iter );
671 82343685 : iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
672 82343685 : fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
673 :
674 82343685 : ulong txn_idx = (ulong)(txn-txn_map);
675 82343685 : ulong rec_idx = txn->rec_head_idx;
676 302003169 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
677 219659484 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==0U );
678 219659484 : rec_map[ rec_idx ].tag = 1U;
679 219659484 : cnt++;
680 219659484 : fd_funk_rec_t const * rec2 = fd_funk_rec_query_global( funk, txn, rec_map[ rec_idx ].pair.key, NULL );
681 219659484 : if( FD_UNLIKELY( rec_map[ rec_idx ].flags & FD_FUNK_REC_FLAG_ERASE ) )
682 62410995 : TEST( rec2 == NULL );
683 157248489 : else
684 157248489 : TEST( rec2 = rec_map + rec_idx );
685 219659484 : ulong next_idx = rec_map[ rec_idx ].next_idx;
686 219659484 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_map[ next_idx ].prev_idx==rec_idx );
687 219659484 : rec_idx = next_idx;
688 219659484 : }
689 82343685 : }
690 :
691 9692196 : TEST( cnt==rec_cnt );
692 9692196 : } while(0);
693 :
694 9692196 : do {
695 9692196 : ulong cnt = 0UL;
696 :
697 9692196 : ulong txn_idx = FD_FUNK_TXN_IDX_NULL;
698 9692196 : ulong rec_idx = funk->rec_tail_idx;
699 437495760 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
700 427803564 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==1U );
701 427803564 : rec_map[ rec_idx ].tag = 2U;
702 427803564 : cnt++;
703 427803564 : ulong prev_idx = rec_map[ rec_idx ].prev_idx;
704 427803564 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_map[ prev_idx ].next_idx==rec_idx );
705 427803564 : rec_idx = prev_idx;
706 427803564 : }
707 :
708 9692196 : for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
709 92035881 : !fd_funk_txn_map_iter_done( txn_map, iter );
710 82343685 : iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
711 82343685 : fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
712 :
713 82343685 : ulong txn_idx = (ulong)(txn-txn_map);
714 82343685 : ulong rec_idx = txn->rec_tail_idx;
715 302003169 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
716 219659484 : TEST( (rec_idx<rec_max) && (fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )==txn_idx) && rec_map[ rec_idx ].tag==1U );
717 219659484 : rec_map[ rec_idx ].tag = 2U;
718 219659484 : cnt++;
719 219659484 : ulong prev_idx = rec_map[ rec_idx ].prev_idx;
720 219659484 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_map[ prev_idx ].next_idx==rec_idx );
721 219659484 : rec_idx = prev_idx;
722 219659484 : }
723 82343685 : }
724 :
725 9692196 : TEST( cnt==rec_cnt );
726 9692196 : } while(0);
727 :
728 9692196 : # undef TEST
729 :
730 9692196 : return FD_FUNK_SUCCESS;
731 9692196 : }
|
