Line data Source code
1 : #include "fd_funk_private.h"
2 : #include "../util/racesan/fd_racesan_target.h"
3 :
4 : /* Provide the actual record map implementation */
5 :
6 : #define POOL_NAME fd_funk_rec_pool
7 2558718 : #define POOL_ELE_T fd_funk_rec_t
8 : #define POOL_IDX_T uint
9 2566482 : #define POOL_NEXT map_next
10 : #define POOL_IMPL_STYLE 2
11 : #define POOL_LAZY 1
12 : #include "../util/tmpl/fd_pool_para.c"
13 :
14 : #define MAP_NAME fd_funk_rec_map
15 1380453 : #define MAP_ELE_T fd_funk_rec_t
16 12237 : #define MAP_KEY_T fd_funk_xid_key_pair_t
17 1290045 : #define MAP_KEY pair
18 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1))
19 : #define MAP_KEY_HASH(k0,seed) fd_funk_xid_key_pair_hash((k0),(seed))
20 1379739 : #define MAP_IDX_T uint
21 3284649 : #define MAP_NEXT map_next
22 162 : #define MAP_MAGIC (0xf173da2ce77ecdb0UL) /* Firedancer rec db version 0 */
23 5217900 : #define MAP_CNT_WIDTH FD_FUNK_REC_MAP_CNT_WIDTH
24 : #define MAP_IMPL_STYLE 2
25 : #define MAP_PEDANTIC 1
26 : #include "../util/tmpl/fd_map_chain_para.c"
27 :
28 : static fd_funk_txn_t *
29 : fd_funk_rec_txn_borrow( fd_funk_t const * funk,
30 : fd_funk_txn_xid_t const * xid,
31 1276974 : fd_funk_txn_map_query_t * query ) {
32 1276974 : memset( query, 0, sizeof(fd_funk_txn_map_query_t) );
33 1276974 : if( fd_funk_txn_xid_eq( xid, funk->shmem->last_publish ) ) return NULL;
34 :
35 1276974 : fd_funk_txn_map_query_t txn_query[1];
36 1276974 : for(;;) {
37 1276974 : int txn_query_err = fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, txn_query, 0 );
38 1276974 : if( FD_UNLIKELY( txn_query_err==FD_MAP_ERR_AGAIN ) ) continue;
39 1276974 : if( FD_UNLIKELY( txn_query_err!=FD_MAP_SUCCESS ) ) {
40 0 : FD_LOG_CRIT(( "fd_funk_rec op failed: txn_map_query_try(%lu:%lu) error %i-%s",
41 0 : xid->ul[0], xid->ul[1],
42 0 : txn_query_err, fd_map_strerror( txn_query_err ) ));
43 0 : }
44 1276974 : break;
45 1276974 : }
46 1276974 : fd_funk_txn_t * txn = fd_funk_txn_map_query_ele( txn_query );
47 1276974 : uint txn_state = FD_VOLATILE_CONST( txn->state );
48 1276974 : if( FD_UNLIKELY( txn_state!=FD_FUNK_TXN_STATE_ACTIVE ) ) {
49 0 : FD_LOG_CRIT(( "fd_funk_rec op failed: txn %p %lu:%lu state is %u-%s",
50 0 : (void *)txn, xid->ul[0], xid->ul[1],
51 0 : txn_state, fd_funk_txn_state_str( txn_state ) ));
52 0 : }
53 1276974 : return txn;
54 1276974 : }
55 :
56 : static void
57 1276974 : fd_funk_rec_txn_release( fd_funk_txn_map_query_t const * query ) {
58 1276974 : if( !query->ele ) return;
59 0 : if( FD_UNLIKELY( fd_funk_txn_map_query_test( query )!=FD_MAP_SUCCESS ) ) {
60 0 : FD_LOG_CRIT(( "fd_funk_rec_txn_release: fd_funk_txn_map_query_test failed (data race detected?)" ));
61 0 : }
62 0 : }
63 :
64 : fd_funk_rec_t *
65 : fd_funk_rec_query_try( fd_funk_t * funk,
66 : fd_funk_txn_xid_t const * xid,
67 : fd_funk_rec_key_t const * key,
68 1032 : fd_funk_rec_query_t * query ) {
69 1032 : if( FD_UNLIKELY( !funk ) ) FD_LOG_CRIT(( "NULL funk" ));
70 1032 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "NULL xid" ));
71 1032 : if( FD_UNLIKELY( !key ) ) FD_LOG_CRIT(( "NULL key" ));
72 1032 : if( FD_UNLIKELY( !query ) ) FD_LOG_CRIT(( "NULL query" ));
73 :
74 1032 : fd_funk_xid_key_pair_t pair[1];
75 1032 : if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid, funk->shmem->last_publish ) ) ) {
76 0 : fd_funk_txn_xid_set_root( pair->xid );
77 1032 : } else {
78 1032 : fd_funk_txn_xid_copy( pair->xid, xid );
79 1032 : }
80 1032 : fd_funk_rec_key_copy( pair->key, key );
81 :
82 1032 : for(;;) {
83 1032 : int err = fd_funk_rec_map_query_try( funk->rec_map, pair, NULL, query, 0 );
84 1032 : if( err == FD_MAP_SUCCESS ) break;
85 24 : if( err == FD_MAP_ERR_KEY ) return NULL;
86 0 : if( err == FD_MAP_ERR_AGAIN ) continue;
87 0 : FD_LOG_CRIT(( "query returned err %d", err ));
88 0 : }
89 1008 : return fd_funk_rec_map_query_ele( query );
90 1032 : }
91 :
92 : fd_funk_rec_t *
93 : fd_funk_rec_prepare( fd_funk_t * funk,
94 : fd_funk_txn_xid_t const * xid,
95 : fd_funk_rec_key_t const * key,
96 : fd_funk_rec_prepare_t * prepare,
97 1276974 : int * opt_err ) {
98 1276974 : if( FD_UNLIKELY( !funk ) ) FD_LOG_CRIT(( "NULL funk" ));
99 1276974 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "NULL xid" ));
100 1276974 : if( FD_UNLIKELY( !prepare ) ) FD_LOG_CRIT(( "NULL prepare" ));
101 :
102 1276974 : fd_funk_txn_map_query_t txn_query[1];
103 1276974 : fd_funk_txn_t * txn = fd_funk_rec_txn_borrow( funk, xid, txn_query );
104 :
105 1276974 : memset( prepare, 0, sizeof(fd_funk_rec_prepare_t) );
106 :
107 1276974 : if( !txn ) { /* Modifying last published */
108 0 : if( FD_UNLIKELY( fd_funk_last_publish_is_frozen( funk ) ) ) {
109 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
110 0 : fd_funk_rec_txn_release( txn_query );
111 0 : return NULL;
112 0 : }
113 1276974 : } else {
114 1276974 : if( FD_UNLIKELY( fd_funk_txn_is_frozen( txn ) ) ) {
115 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_FROZEN );
116 0 : fd_funk_rec_txn_release( txn_query );
117 0 : return NULL;
118 0 : }
119 1276974 : }
120 :
121 1276974 : fd_funk_rec_t * rec = prepare->rec = fd_funk_rec_pool_acquire( funk->rec_pool, NULL, 1, opt_err );
122 1276974 : if( opt_err && *opt_err == FD_POOL_ERR_CORRUPT ) {
123 0 : FD_LOG_CRIT(( "corrupt element returned from funk rec pool" ));
124 0 : }
125 1276974 : if( FD_UNLIKELY( !rec ) ) {
126 0 : fd_int_store_if( !!opt_err, opt_err, FD_FUNK_ERR_REC );
127 0 : fd_funk_rec_txn_release( txn_query );
128 0 : return rec;
129 0 : }
130 :
131 1276974 : fd_funk_val_init( rec );
132 1276974 : if( txn == NULL ) {
133 0 : fd_funk_txn_xid_set_root( rec->pair.xid );
134 1276974 : } else {
135 1276974 : fd_funk_txn_xid_copy( rec->pair.xid, &txn->xid );
136 1276974 : prepare->rec_head_idx = &txn->rec_head_idx;
137 1276974 : prepare->rec_tail_idx = &txn->rec_tail_idx;
138 1276974 : }
139 1276974 : fd_funk_rec_key_copy( rec->pair.key, key );
140 1276974 : rec->tag = 0;
141 1276974 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
142 1276974 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
143 1276974 : fd_funk_rec_txn_release( txn_query );
144 1276974 : return rec;
145 1276974 : }
146 :
147 : #if FD_HAS_ATOMIC
148 :
149 : static void
150 : fd_funk_rec_push_tail( fd_funk_t * funk,
151 1277718 : fd_funk_rec_prepare_t * prepare ) {
152 1277718 : fd_funk_rec_t * rec = prepare->rec;
153 1277718 : uint rec_idx = (uint)( rec - funk->rec_pool->ele );
154 1277718 : uint * rec_head_idx = prepare->rec_head_idx;
155 1277718 : uint * rec_tail_idx = prepare->rec_tail_idx;
156 :
157 1277718 : for(;;) {
158 :
159 : /* Doubly linked list append. Robust in the event of concurrent
160 : publishes. Iteration during publish not supported. Sequence:
161 : - Identify tail element
162 : - Set new element's prev and next pointers
163 : - Set tail element's next pointer
164 : - Set tail pointer */
165 :
166 1277718 : uint rec_prev_idx = FD_VOLATILE_CONST( *rec_tail_idx );
167 1277718 : rec->prev_idx = rec_prev_idx;
168 1277718 : FD_COMPILER_MFENCE();
169 :
170 1277718 : uint * next_idx_p;
171 1277718 : if( fd_funk_rec_idx_is_null( rec_prev_idx ) ) {
172 395979 : next_idx_p = rec_head_idx;
173 881739 : } else {
174 881739 : next_idx_p = &funk->rec_pool->ele[ rec_prev_idx ].next_idx;
175 881739 : }
176 :
177 1277718 : fd_racesan_hook( "funk_rec_push_tail:next_cas" );
178 1277718 : if( FD_UNLIKELY( !__sync_bool_compare_and_swap( next_idx_p, FD_FUNK_REC_IDX_NULL, rec_idx ) ) ) {
179 : /* Another thread beat us to the punch */
180 0 : FD_SPIN_PAUSE();
181 0 : continue;
182 0 : }
183 :
184 1277718 : fd_racesan_hook( "funk_rec_push_tail:tail_cas" );
185 1277718 : if( FD_UNLIKELY( !__sync_bool_compare_and_swap( rec_tail_idx, rec_prev_idx, rec_idx ) ) ) {
186 : /* This CAS is guaranteed to succeed if the previous CAS passed. */
187 0 : FD_LOG_CRIT(( "Irrecoverable data race encountered while appending to txn rec list (invariant violation?): cas(%p,%u,%u)",
188 0 : (void *)rec_tail_idx, rec_prev_idx, rec_idx ));
189 0 : }
190 :
191 1277718 : break;
192 1277718 : }
193 1277718 : }
194 :
195 : #else
196 :
197 : static void
198 : fd_funk_rec_push_tail( fd_funk_t * funk,
199 : fd_funk_rec_prepare_t * prepare ) {
200 : fd_funk_rec_t * rec = prepare->rec;
201 : uint rec_idx = (uint)( rec - funk->rec_pool->ele );
202 : uint * rec_head_idx = prepare->rec_head_idx;
203 : uint * rec_tail_idx = prepare->rec_tail_idx;
204 : uint rec_prev_idx = *rec_tail_idx;
205 : *rec_tail_idx = rec_idx;
206 : rec->prev_idx = rec_prev_idx;
207 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
208 : if( fd_funk_rec_idx_is_null( rec_prev_idx ) ) {
209 : *rec_head_idx = rec_idx;
210 : } else {
211 : funk->rec_pool->ele[ rec_prev_idx ].next_idx = rec_idx;
212 : }
213 : }
214 :
215 : #endif
216 :
217 : void
218 : fd_funk_rec_publish( fd_funk_t * funk,
219 1277718 : fd_funk_rec_prepare_t * prepare ) {
220 1277718 : fd_funk_rec_t * rec = prepare->rec;
221 1277718 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
222 1277718 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
223 :
224 1277718 : if( prepare->rec_head_idx ) {
225 1277718 : fd_funk_rec_push_tail( funk, prepare );
226 1277718 : }
227 :
228 1277718 : fd_racesan_hook( "funk_rec_publish:map_insert" );
229 1277718 : int insert_err = fd_funk_rec_map_insert( funk->rec_map, rec, FD_MAP_FLAG_BLOCKING );
230 1277718 : if( insert_err ) {
231 0 : FD_LOG_CRIT(( "fd_funk_rec_map_insert failed (%i-%s)", insert_err, fd_map_strerror( insert_err ) ));
232 0 : }
233 1277718 : }
234 :
235 : int
236 243 : fd_funk_rec_verify( fd_funk_t * funk ) {
237 243 : fd_funk_rec_map_t * rec_map = funk->rec_map;
238 243 : fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
239 243 : ulong rec_max = fd_funk_rec_pool_ele_max( rec_pool );
240 :
241 495348 : # define TEST(c) do { \
242 495348 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
243 495348 : } while(0)
244 :
245 243 : TEST( !fd_funk_rec_map_verify( rec_map ) );
246 243 : TEST( !fd_funk_rec_pool_verify( rec_pool ) );
247 :
248 : /* Iterate (again) over all records in use */
249 :
250 243 : fd_funk_rec_map_shmem_private_chain_t * chain_tbl =
251 243 : fd_funk_rec_map_shmem_private_chain( rec_map->map, 0UL );
252 243 : ulong chain_cnt = fd_funk_rec_map_chain_cnt( rec_map );
253 444819 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
254 444576 : ulong chain_ele_cnt = fd_funk_rec_map_private_vcnt_cnt( chain_tbl[ chain_idx ].ver_cnt );
255 444576 : ulong chain_ele_idx = 0UL;
256 444576 : for( fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter( rec_map, chain_idx );
257 456813 : !fd_funk_rec_map_iter_done( iter );
258 444576 : iter = fd_funk_rec_map_iter_next( iter ), chain_ele_idx++ ) {
259 12237 : fd_funk_rec_t const * rec = fd_funk_rec_map_iter_ele_const( iter );
260 :
261 : /* Make sure every record either links up with the last published
262 : transaction or an in-prep transaction and the flags are sane. */
263 :
264 12237 : fd_funk_txn_xid_t const * xid = fd_funk_rec_xid( rec );
265 :
266 12237 : if( fd_funk_txn_xid_eq_root( xid ) ) { /* This is a record from the last published transaction */
267 :
268 11232 : TEST( fd_funk_txn_xid_eq_root( xid ) );
269 : /* No record linked list at the root txn */
270 11232 : TEST( fd_funk_rec_idx_is_null( rec->prev_idx ) );
271 11232 : TEST( fd_funk_rec_idx_is_null( rec->next_idx ) );
272 :
273 11232 : } else { /* This is a record from an in-prep transaction */
274 :
275 1005 : fd_funk_txn_map_query_t query[1];
276 1005 : TEST( fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 )==FD_MAP_SUCCESS );
277 :
278 1005 : }
279 12237 : }
280 444576 : TEST( chain_ele_idx==chain_ele_cnt );
281 444576 : }
282 :
283 : /* Clear record tags and then verify membership */
284 :
285 889395 : for( ulong rec_idx=0UL; rec_idx<rec_max; rec_idx++ ) rec_pool->ele[ rec_idx ].tag = 0;
286 :
287 243 : do {
288 243 : fd_funk_all_iter_t iter[1];
289 12480 : for( fd_funk_all_iter_new( funk, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
290 12237 : fd_funk_rec_t * rec = fd_funk_all_iter_ele( iter );
291 12237 : if( fd_funk_txn_xid_eq_root( rec->pair.xid ) ) {
292 11232 : TEST( !rec->tag );
293 11232 : rec->tag = 1;
294 11232 : }
295 12237 : }
296 :
297 243 : fd_funk_txn_all_iter_t txn_iter[1];
298 834 : for( fd_funk_txn_all_iter_new( funk, txn_iter ); !fd_funk_txn_all_iter_done( txn_iter ); fd_funk_txn_all_iter_next( txn_iter ) ) {
299 591 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
300 :
301 591 : uint rec_idx = txn->rec_head_idx;
302 1596 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
303 1005 : TEST( (rec_idx<rec_max) && !rec_pool->ele[ rec_idx ].tag );
304 1005 : rec_pool->ele[ rec_idx ].tag = 1;
305 1005 : fd_funk_rec_query_t query[1];
306 1005 : fd_funk_rec_t const * rec2 = fd_funk_rec_query_try( funk, &txn->xid, rec_pool->ele[ rec_idx ].pair.key, query );
307 1005 : TEST( rec2 == rec_pool->ele + rec_idx );
308 1005 : uint next_idx = rec_pool->ele[ rec_idx ].next_idx;
309 1005 : if( !fd_funk_rec_idx_is_null( next_idx ) ) TEST( rec_pool->ele[ next_idx ].prev_idx==rec_idx );
310 1005 : rec_idx = next_idx;
311 1005 : }
312 591 : }
313 243 : } while(0);
314 :
315 243 : do {
316 243 : fd_funk_txn_all_iter_t txn_iter[1];
317 834 : for( fd_funk_txn_all_iter_new( funk, txn_iter ); !fd_funk_txn_all_iter_done( txn_iter ); fd_funk_txn_all_iter_next( txn_iter ) ) {
318 591 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
319 :
320 591 : uint rec_idx = txn->rec_tail_idx;
321 1596 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
322 1005 : TEST( (rec_idx<rec_max) && rec_pool->ele[ rec_idx ].tag );
323 1005 : rec_pool->ele[ rec_idx ].tag = 0;
324 1005 : uint prev_idx = rec_pool->ele[ rec_idx ].prev_idx;
325 1005 : if( !fd_funk_rec_idx_is_null( prev_idx ) ) TEST( rec_pool->ele[ prev_idx ].next_idx==rec_idx );
326 1005 : rec_idx = prev_idx;
327 1005 : }
328 591 : }
329 243 : } while(0);
330 :
331 243 : fd_funk_all_iter_t iter[1];
332 12480 : for( fd_funk_all_iter_new( funk, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
333 12237 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele( iter );
334 12237 : FD_TEST( rec->tag == fd_funk_txn_xid_eq_root( rec->pair.xid ) );
335 12237 : }
336 :
337 243 : # undef TEST
338 :
339 243 : return FD_FUNK_SUCCESS;
340 243 : }
|
