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