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