Line data Source code
1 : #include "fd_funk_txn.h"
2 : #include "fd_funk.h"
3 :
4 : /* Provide the actual transaction map implementation */
5 :
6 : #define POOL_NAME fd_funk_txn_pool
7 1144320 : #define POOL_ELE_T fd_funk_txn_t
8 : #define POOL_IDX_T uint
9 2723124 : #define POOL_NEXT map_next
10 : #define POOL_IMPL_STYLE 2
11 : #include "../util/tmpl/fd_pool_para.c"
12 :
13 : #define MAP_NAME fd_funk_txn_map
14 2965668 : #define MAP_ELE_T fd_funk_txn_t
15 588 : #define MAP_KEY_T fd_funk_txn_xid_t
16 572532 : #define MAP_KEY xid
17 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
18 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
19 1879812 : #define MAP_NEXT map_next
20 57 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
21 : #define MAP_IMPL_STYLE 2
22 : #include "../util/tmpl/fd_map_chain_para.c"
23 :
24 571944 : #define fd_funk_txn_state_transition(txn, before, after) do { \
25 571944 : if( FD_HAS_ATOMIC ) { \
26 571944 : if( FD_LIKELY( __sync_bool_compare_and_swap( &(txn)->state, before, after ) ) ) break; \
27 571944 : } else { \
28 0 : if( FD_LIKELY( (txn)->state == (before) ) ) { \
29 0 : (txn)->state = (after); \
30 0 : break; \
31 0 : } \
32 0 : } \
33 571944 : uint have_ = FD_VOLATILE_CONST( (txn)->state ); \
34 0 : FD_LOG_CRIT(( "Detected data race on funk txn %p: expected state %u-%s, found %u-%s, while transitioning to %u-%s", \
35 0 : (void *)(txn), \
36 0 : (before), fd_funk_txn_state_str( before ), \
37 0 : have_, fd_funk_txn_state_str( have_ ), \
38 0 : (after), fd_funk_txn_state_str( after ) )); \
39 0 : } while(0)
40 :
41 : #define fd_funk_last_publish_transition(funk_shmem, after) do { \
42 : fd_funk_shmem_t * _shmem = (funk_shmem); \
43 : fd_funk_txn_xid_t * _last_pub = _shmem->last_publish; \
44 : fd_funk_txn_xid_t _prev_pub[1]; fd_funk_txn_xid_copy( _prev_pub, _last_pub ); \
45 : fd_funk_txn_xid_copy( _last_pub, (after) ); \
46 : FD_LOG_INFO(( "funk last_publish (%lu:%lu) -> (%lu:%lu)", \
47 : _prev_pub->ul[0], _prev_pub->ul[1], \
48 : _last_pub->ul[0], _last_pub->ul[1] )); \
49 : } while(0)
50 :
51 : void
52 : fd_funk_txn_prepare( fd_funk_t * funk,
53 : fd_funk_txn_xid_t const * parent_xid,
54 571944 : fd_funk_txn_xid_t const * xid ) {
55 :
56 571944 : if( FD_UNLIKELY( !funk ) ) FD_LOG_CRIT(( "NULL funk" ));
57 571944 : if( FD_UNLIKELY( !parent_xid ) ) FD_LOG_CRIT(( "NULL parent_xid" ));
58 571944 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "NULL xid" ));
59 571944 : if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( xid ) ) ) FD_LOG_CRIT(( "xid is root" ));
60 :
61 571944 : if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid, funk->shmem->last_publish ) ) ) {
62 0 : FD_LOG_ERR(( "fd_funk_txn_prepare failed: xid %lu:%lu is the last published",
63 0 : xid->ul[0], xid->ul[1] ));
64 0 : }
65 :
66 571944 : fd_funk_txn_map_query_t query[1];
67 571944 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 ) != FD_MAP_ERR_KEY ) ) {
68 0 : FD_LOG_ERR(( "fd_funk_txn_prepare failed: xid %lu:%lu already in use",
69 0 : xid->ul[0], xid->ul[1] ));
70 0 : }
71 :
72 571944 : ulong parent_idx;
73 571944 : uint * _child_head_cidx;
74 571944 : uint * _child_tail_cidx;
75 :
76 571944 : if( FD_UNLIKELY( fd_funk_txn_xid_eq( parent_xid, funk->shmem->last_publish ) ) ) {
77 :
78 254598 : parent_idx = FD_FUNK_TXN_IDX_NULL;
79 :
80 254598 : _child_head_cidx = &funk->shmem->child_head_cidx;
81 254598 : _child_tail_cidx = &funk->shmem->child_tail_cidx;
82 :
83 317346 : } else {
84 :
85 317346 : int query_err = fd_funk_txn_map_query_try( funk->txn_map, parent_xid, NULL, query, 0 );
86 317346 : if( FD_UNLIKELY( query_err!=FD_MAP_SUCCESS ) ) {
87 0 : FD_LOG_CRIT(( "fd_funk_txn_prepare failed: user provided invalid parent XID %lu:%lu (err %i-%s)",
88 0 : parent_xid->ul[0], parent_xid->ul[1],
89 0 : query_err, fd_map_strerror( query_err ) ));
90 0 : }
91 :
92 317346 : fd_funk_txn_t * parent = fd_funk_txn_map_query_ele( query );
93 317346 : fd_funk_txn_state_assert( parent, FD_FUNK_TXN_STATE_ACTIVE );
94 317346 : parent_idx = (ulong)(parent - funk->txn_pool->ele);
95 :
96 317346 : _child_head_cidx = &parent->child_head_cidx;
97 317346 : _child_tail_cidx = &parent->child_tail_cidx;
98 :
99 317346 : }
100 :
101 : /* Get a new transaction from the map */
102 :
103 571944 : fd_funk_txn_t * txn = fd_funk_txn_pool_acquire( funk->txn_pool, NULL, 1, NULL );
104 571944 : if( FD_UNLIKELY( !txn ) ) FD_LOG_ERR(( "fd_funk_txn_prepare failed: transaction object pool out of memory" ));
105 571944 : fd_funk_txn_xid_copy( &txn->xid, xid );
106 571944 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
107 :
108 : /* Join the family */
109 :
110 571944 : ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
111 :
112 571944 : int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
113 :
114 571944 : txn->parent_cidx = fd_funk_txn_cidx( parent_idx );
115 571944 : txn->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
116 571944 : txn->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
117 571944 : txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
118 571944 : txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
119 571944 : txn->stack_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
120 571944 : txn->tag = 0UL;
121 :
122 571944 : fd_funk_txn_state_transition( txn, FD_FUNK_TXN_STATE_FREE, FD_FUNK_TXN_STATE_ACTIVE );
123 571944 : txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
124 571944 : txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
125 :
126 : /* TODO: consider branchless impl */
127 571944 : if( FD_LIKELY( first_born ) ) *_child_head_cidx = fd_funk_txn_cidx( txn_idx ); /* opt for non-compete */
128 223980 : else funk->txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( txn_idx );
129 :
130 571944 : *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
131 :
132 571944 : if( FD_UNLIKELY( fd_funk_txn_map_query_test( query )!=FD_MAP_SUCCESS ) ) {
133 0 : FD_LOG_CRIT(( "Detected data race while preparing a funk txn" ));
134 0 : }
135 :
136 571944 : fd_funk_txn_map_insert( funk->txn_map, txn, FD_MAP_FLAG_BLOCKING );
137 571944 : }
138 :
139 : int
140 201 : fd_funk_txn_verify( fd_funk_t * funk ) {
141 201 : fd_funk_txn_map_t * txn_map = funk->txn_map;
142 201 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
143 201 : ulong txn_max = fd_funk_txn_pool_ele_max( txn_pool );
144 :
145 201 : ulong funk_child_head_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* Previously verified */
146 201 : ulong funk_child_tail_idx = fd_funk_txn_idx( funk->shmem->child_tail_cidx ); /* Previously verified */
147 :
148 201 : fd_funk_txn_xid_t const * last_publish = funk->shmem->last_publish; /* Previously verified */
149 :
150 4320 : # define TEST(c) do { \
151 4320 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
152 4320 : } while(0)
153 :
154 201 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
155 201 : ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &txn_pool->ele[idx] ), last_publish ))) )
156 :
157 201 : TEST( !fd_funk_txn_map_verify( txn_map ) );
158 201 : TEST( !fd_funk_txn_pool_verify( txn_pool ) );
159 :
160 : /* Tag all transactions as not visited yet */
161 :
162 792969 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) txn_pool->ele[ txn_idx ].tag = 0UL;
163 :
164 : /* Visit all transactions in preparation, traversing from oldest to
165 : youngest. */
166 :
167 201 : do {
168 :
169 : /* Push all children of funk to the stack */
170 :
171 201 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
172 201 : ulong child_idx = funk_child_head_idx;
173 489 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
174 :
175 : /* Make sure valid idx, not tagged (detects cycles) and child
176 : knows it is a child of funk. Then tag as visited / in-prep,
177 : push to stack and update prep_cnt */
178 :
179 288 : TEST( IS_VALID( child_idx ) );
180 288 : TEST( !txn_pool->ele[ child_idx ].tag );
181 288 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
182 288 : txn_pool->ele[ child_idx ].tag = 1UL;
183 288 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
184 288 : stack_idx = child_idx;
185 :
186 288 : ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
187 288 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
188 288 : child_idx = next_idx;
189 288 : }
190 :
191 789 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
192 :
193 : /* Pop the next transaction to traverse */
194 :
195 588 : ulong txn_idx = stack_idx;
196 588 : stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
197 :
198 : /* Push all children of txn to the stack */
199 :
200 588 : ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_head_cidx );
201 888 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
202 :
203 : /* Make sure valid idx, not tagged (detects cycles) and child
204 : knows it is a child of txn_idx. Then tag as visited /
205 : in-prep, push to stack and update prep_cnt */
206 :
207 300 : TEST( IS_VALID( child_idx ) );
208 300 : TEST( !txn_pool->ele[ child_idx ].tag );
209 300 : TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
210 300 : txn_pool->ele[ child_idx ].tag = 1UL;
211 300 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
212 300 : stack_idx = child_idx;
213 :
214 300 : ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
215 300 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
216 300 : child_idx = next_idx;
217 300 : }
218 588 : }
219 :
220 201 : } while(0);
221 :
222 : /* Do it again with a youngest to oldest traversal to test reverse
223 : link integrity */
224 :
225 201 : do {
226 :
227 : /* Push all children of funk to the stack */
228 :
229 201 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
230 201 : ulong child_idx = funk_child_tail_idx;
231 489 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
232 :
233 : /* Make sure valid idx, tagged as visited above (detects cycles)
234 : and child knows it is a child of funk. Then tag as visited /
235 : in-prep, push to stack and update prep_cnt */
236 :
237 288 : TEST( IS_VALID( child_idx ) );
238 288 : TEST( txn_pool->ele[ child_idx ].tag==1UL );
239 288 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
240 288 : txn_pool->ele[ child_idx ].tag = 2UL;
241 288 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
242 288 : stack_idx = child_idx;
243 :
244 288 : ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
245 288 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
246 288 : child_idx = prev_idx;
247 288 : }
248 :
249 789 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
250 :
251 : /* Pop the next transaction to traverse */
252 :
253 588 : ulong txn_idx = stack_idx;
254 588 : stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
255 :
256 : /* Push all children of txn to the stack */
257 :
258 588 : ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_tail_cidx );
259 888 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
260 :
261 : /* Make sure valid idx, tagged as visited above (detects cycles)
262 : and child knows it is a child of txn_idx. Then, tag as
263 : visited / in-prep, push to stack and update prep_cnt */
264 :
265 300 : TEST( IS_VALID( child_idx ) );
266 300 : TEST( txn_pool->ele[ child_idx ].tag==1UL );
267 300 : TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
268 300 : txn_pool->ele[ child_idx ].tag = 2UL;
269 300 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
270 300 : stack_idx = child_idx;
271 :
272 300 : ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
273 300 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
274 300 : child_idx = prev_idx;
275 300 : }
276 588 : }
277 201 : } while(0);
278 :
279 201 : # undef IS_VALID
280 201 : # undef TEST
281 :
282 201 : return FD_FUNK_SUCCESS;
283 201 : }
|
