Line data Source code
1 : #ifndef HEADER_fd_src_funk_fd_funk_txn_h
2 : #define HEADER_fd_src_funk_fd_funk_txn_h
3 :
4 : /* This provides APIs for managing forks (preparing, publishing and
5 : cancelling funk transactions). It is generally not meant to be
6 : included directly. Use fd_funk.h instead.
7 :
8 : Funk transaction-level operations are not thread-safe. External
9 : synchronization (e.g. mutex) is required when doing txn operations
10 : when other txn or rec operations may be concurrently running on other
11 : threads. */
12 :
13 : #include "fd_funk_base.h"
14 :
15 : /* FD_FUNK_TXN_{ALIGN,FOOTPRINT} describe the alignment and footprint of
16 : a fd_funk_txn_t. ALIGN will be a power of 2, footprint will be a
17 : multiple of align. These are provided to facilitate compile time
18 : declarations. */
19 :
20 : #define FD_FUNK_TXN_ALIGN (32UL)
21 : #define FD_FUNK_TXN_FOOTPRINT (96UL)
22 :
23 : /* FD_FUNK_TXN_IDX_NULL gives the map transaction idx value used to
24 : represent NULL. It also is the maximum value for txn_max in a funk
25 : to support index compression. (E.g. could use ushort / USHORT_MAX
26 : to use more aggressive compression or ulong / ULONG_MAX to disable
27 : index compression.) */
28 :
29 792751113 : #define FD_FUNK_TXN_IDX_NULL ((ulong)UINT_MAX)
30 :
31 : /* A fd_funk_txn_t is an opaque handle of an in-preparation funk
32 : transaction. The details are exposed here to facilitate inlining
33 : various operations. */
34 :
35 : struct __attribute__((aligned(FD_FUNK_TXN_ALIGN))) fd_funk_txn_private {
36 :
37 : /* These fields are managed by the funk's txn_map */
38 :
39 : fd_funk_txn_xid_t xid; /* Transaction id, at a minimum, unique among all in-prepare and the last published transaction,
40 : ideally globally unique */
41 : ulong map_next; /* Internal use by map */
42 : ulong map_hash; /* Internal use by map */
43 :
44 : /* These fields are managed by the funk */
45 :
46 : uint parent_cidx; /* compr map index of the in-prep parent txn, compr FD_FUNK_TXN_IDX_NULL if a funk child */
47 : uint child_head_cidx; /* " oldest child " childless */
48 : uint child_tail_cidx; /* " youngest child childless */
49 : uint sibling_prev_cidx; /* " older sibling oldest sibling */
50 : uint sibling_next_cidx; /* " younger sibling youngest sibling */
51 : uint stack_cidx; /* Internal use by funk */
52 : ulong tag; /* Internal use by funk */
53 :
54 : uint rec_head_idx; /* Record map index of the first record, FD_FUNK_REC_IDX_NULL if none (from oldest to youngest) */
55 : uint rec_tail_idx; /* " last " */
56 :
57 : uint state; /* one of FD_FUNK_TXN_STATE_* */
58 : };
59 :
60 : typedef struct fd_funk_txn_private fd_funk_txn_t;
61 :
62 : /* fd_funk_txn_map allows for indexing transactions by their xid */
63 :
64 : #define POOL_NAME fd_funk_txn_pool
65 450750 : #define POOL_ELE_T fd_funk_txn_t
66 : #define POOL_IDX_T uint
67 : #define POOL_NEXT map_next
68 : #define POOL_IMPL_STYLE 1
69 : #include "../util/tmpl/fd_pool_para.c"
70 :
71 : #define MAP_NAME fd_funk_txn_map
72 1343880 : #define MAP_ELE_T fd_funk_txn_t
73 : #define MAP_KEY_T fd_funk_txn_xid_t
74 : #define MAP_KEY xid
75 233596502 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
76 317137572 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
77 1343880 : #define MAP_NEXT map_next
78 : #define MAP_HASH map_hash
79 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
80 : #define MAP_IMPL_STYLE 1
81 : #include "../util/tmpl/fd_map_chain_para.c"
82 : #undef MAP_HASH
83 :
84 : /* Funk transaction states */
85 :
86 4017114 : #define FD_FUNK_TXN_STATE_FREE (0U)
87 51656571 : #define FD_FUNK_TXN_STATE_ACTIVE (1U)
88 3458382 : #define FD_FUNK_TXN_STATE_CANCEL (2U)
89 722655 : #define FD_FUNK_TXN_STATE_PUBLISH (3U)
90 :
91 : FD_PROTOTYPES_BEGIN
92 :
93 : /* fd_funk_txn_{cidx,idx} convert between an index and a compressed index. */
94 :
95 16285119 : static inline uint fd_funk_txn_cidx( ulong idx ) { return (uint) idx; }
96 788788632 : static inline ulong fd_funk_txn_idx ( uint cidx ) { return (ulong)cidx; }
97 :
98 : /* fd_funk_txn_idx_is_null returns 1 if idx is FD_FUNK_TXN_IDX_NULL and
99 : 0 otherwise. */
100 :
101 347937867 : static inline int fd_funk_txn_idx_is_null( ulong idx ) { return idx==FD_FUNK_TXN_IDX_NULL; }
102 :
103 : /* Generate a globally unique pseudo-random xid */
104 : fd_funk_txn_xid_t fd_funk_generate_xid(void);
105 :
106 : /* Accessors */
107 :
108 : /* fd_funk_txn_query returns a pointer to an in-preparation transaction
109 : whose id is pointed to by xid. Returns NULL if xid is not an
110 : in-preparation transaction. Assumes funk is a current local join,
111 : map==fd_funk_txn_map( funk, fd_funk_wksp( funk ) ), xid points to a
112 : transaction id in the caller's address space and there are no
113 : concurrent operations on funk or xid. Retains no interest in xid.
114 :
115 : The returned pointer is in the caller's address space and, if the
116 : return is non-NULL, the lifetime of the returned pointer is the
117 : lesser of the funk join or the transaction is published or canceled
118 : (either directly or indirectly via publish of a descendant, publish
119 : of a competing transaction history or cancel of an ancestor). */
120 :
121 : FD_FN_PURE static inline fd_funk_txn_t *
122 : fd_funk_txn_query( fd_funk_txn_xid_t const * xid,
123 261105081 : fd_funk_txn_map_t * map ) {
124 261105081 : do {
125 261105081 : fd_funk_txn_map_query_t query[1];
126 261105081 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( map, xid, NULL, query, 0 ) ) ) return NULL;
127 58698168 : fd_funk_txn_t * ele = fd_funk_txn_map_query_ele( query );
128 58698168 : if( FD_LIKELY( !fd_funk_txn_map_query_test( query ) ) ) return ele;
129 58698168 : } while( 1 );
130 261105081 : }
131 :
132 : /* fd_funk_txn_xid returns a pointer in the local address space of the
133 : ID of an in-preparation transaction. Assumes txn points to an
134 : in-preparation transaction in the caller's address space. The
135 : lifetime of the returned pointer is the same as the txn's pointer
136 : lifetime. The value at the pointer will be stable for the lifetime
137 : of the returned pointer. */
138 :
139 211320402 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_txn_xid( fd_funk_txn_t const * txn ) { return &txn->xid; }
140 :
141 : /* fd_funk_txn_{parent,child_head,child_tail,sibling_prev,sibling_next}
142 : return a pointer in the caller's address space to the corresponding
143 : relative in-preparation transaction of in-preparation transaction
144 : txn.
145 :
146 : Specifically:
147 :
148 : - parent is the parent transaction. NULL if txn is a child of funk.
149 : - child_head is txn's oldest child. NULL if txn has no children.
150 : - child_tail is txn's youngest child. NULL if txn has no children.
151 : - sibling_prev is txn's closest older sibling. NULL if txn is the
152 : oldest sibling.
153 : - sibling_next is txn's closest younger sibling. NULL if txn is the
154 : youngest sibling.
155 :
156 : E.g. child_head==NULL indicates txn has no children.
157 : child_head!=NULL and child_head==child_tail indicates txn has one
158 : child. child_head!=NULL and child_tail!=NULL and
159 : child_head!=child_tail indicates txn has many children.
160 : sibling_prev==sibling_next==NULL indicate no siblings / locally
161 : competing transactions to txn. If the txn and all its ancestors have
162 : no siblings, there are no transaction histories competing with txn
163 : globally. */
164 :
165 : #define FD_FUNK_ACCESSOR(field) \
166 : FD_FN_PURE static inline fd_funk_txn_t * \
167 : fd_funk_txn_##field( fd_funk_txn_t const * txn, \
168 435171708 : fd_funk_txn_pool_t const * pool ) { \
169 435171708 : ulong idx = fd_funk_txn_idx( txn->field##_cidx ); \
170 435171708 : if( idx==FD_FUNK_TXN_IDX_NULL ) return NULL; \
171 435171708 : return pool->ele + idx; \
172 435171708 : }
173 :
174 249775788 : FD_FUNK_ACCESSOR( parent )
175 57758346 : FD_FUNK_ACCESSOR( child_head )
176 42539550 : FD_FUNK_ACCESSOR( child_tail )
177 42548934 : FD_FUNK_ACCESSOR( sibling_prev )
178 42549090 : FD_FUNK_ACCESSOR( sibling_next )
179 :
180 : #undef FD_FUNK_ACCESSOR
181 :
182 : /* fd_funk_txn_frozen returns 1 if the in-preparation transaction is
183 : frozen (i.e. has children) and 0 otherwise (i.e. has no children).
184 : Assumes txn points to an in-preparation transaction in the caller's
185 : address space. */
186 :
187 : FD_FN_PURE static inline int
188 44715609 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) {
189 44715609 : return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) );
190 44715609 : }
191 :
192 : /* fd_funk_txn_is_only_child returns 1 if the in-preparation transaction
193 : txn if is any only child and 0 if it has one or more siblings.
194 : Assumes txn points to an in-preparation transaction in the caller's
195 : address space. */
196 :
197 : FD_FN_PURE static inline int
198 146977614 : fd_funk_txn_is_only_child( fd_funk_txn_t const * txn ) {
199 146977614 : return ( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->sibling_prev_cidx ) ) ) &
200 146977614 : ( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->sibling_next_cidx ) ) );
201 146977614 : }
202 :
203 : typedef struct fd_funk_rec fd_funk_rec_t;
204 :
205 : /* fd_funk_txn_{first,last}_rec return the {first,last} record in a
206 : transaction. Returns NULL if the transaction has no records yet, or
207 : if txn is NULL (root txn). */
208 :
209 : fd_funk_rec_t const *
210 : fd_funk_txn_first_rec( fd_funk_t * funk,
211 : fd_funk_txn_t const * txn );
212 :
213 : fd_funk_rec_t const *
214 : fd_funk_txn_last_rec( fd_funk_t * funk,
215 : fd_funk_txn_t const * txn );
216 :
217 : /* Return the next record in a transaction. Returns NULL if the
218 : transaction has no more records. */
219 :
220 : fd_funk_rec_t const *
221 : fd_funk_txn_next_rec( fd_funk_t * funk,
222 : fd_funk_rec_t const * rec );
223 :
224 : /* Return the previous record in a transaction. Returns NULL if the
225 : transaction has no more records. */
226 :
227 : fd_funk_rec_t const *
228 : fd_funk_txn_prev_rec( fd_funk_t * funk,
229 : fd_funk_rec_t const * rec );
230 :
231 : /* Operations */
232 :
233 : /* fd_funk_txn_ancestor returns a pointer in the caller's address space
234 : to the youngest transaction among in-preparation transaction txn and
235 : its ancestors that currently has siblings. Returns NULL if all
236 : transactions back to the root transaction have no siblings (e.g.
237 : there are no competing transaction histories and thus publishing
238 : transaction txn will not require canceling any other competing
239 : transactions). This is a reasonably fast O(length of ancestor
240 : history) time (theoretical minimum) and a reasonably small O(1) space
241 : (theoretical minimum). This is not fortified against transaction map
242 : data corruption.
243 :
244 : fd_funk_txn_descendant returns a pointer in the caller's address
245 : space to the first transaction among txn and its youngest direct
246 : descendant inclusive that currently either has no children or has
247 : multiple children. Returns NULL if txn is not an only child. This
248 : is a reasonably fast O(length of descendant history) time
249 : (theoretical minimum) and a reasonably small O(1) space (theoretical
250 : minimum). This is not fortified against transaction map data
251 : corruption.
252 :
253 : That is, if txn's ancestor is NULL, all transactions up to and
254 : including txn's descendant (which will be non-NULL) can be published
255 : without cancelling any competing transactions. Further, if the
256 : descendant has a child, it has multiple children. And if has no
257 : children, all transactions in preparation are linear from the root to
258 : the descendant.
259 :
260 : In code:
261 :
262 : if( !fd_funk_txn_ancestor( txn, map ) )
263 : fd_funk_publish( funk, fd_funk_txn_descendant( funk, map ) );
264 :
265 : would publish as much currently uncontested transaction history as
266 : possible around txn. */
267 :
268 : FD_FN_PURE static inline fd_funk_txn_t *
269 : fd_funk_txn_ancestor( fd_funk_txn_t * txn,
270 42528654 : fd_funk_txn_pool_t * pool ) {
271 56997111 : for(;;) {
272 56997111 : if( !fd_funk_txn_is_only_child( txn ) ) break;
273 15218796 : fd_funk_txn_t * parent = fd_funk_txn_parent( txn, pool );
274 15218796 : if( !parent ) return NULL;
275 14468457 : txn = parent;
276 14468457 : }
277 41778315 : return txn;
278 42528654 : }
279 :
280 : FD_FN_PURE static inline fd_funk_txn_t *
281 : fd_funk_txn_descendant( fd_funk_txn_t * txn,
282 42528654 : fd_funk_txn_pool_t * pool ) {
283 42528654 : if( !fd_funk_txn_is_only_child( txn ) ) return NULL;
284 15218796 : for(;;) { /* txn is an only child at this point */
285 15218796 : fd_funk_txn_t * child = fd_funk_txn_child_head( txn, pool );
286 15218796 : if( !child || !fd_funk_txn_is_only_child( child ) ) break;
287 3350406 : txn = child;
288 3350406 : }
289 11868390 : return txn;
290 42528654 : }
291 :
292 : /* IMPORTANT SAFETY TIP! **********************************************/
293 :
294 : /* fd_funk_txn_{prepare,publish,cancel,cancel_siblings,cancel_children}
295 : are the pointy end of the stick practically. As such, these are
296 : fortified against transaction map memory corruption. Since any such
297 : corruption would be prima facie evidence of a hardware fault,
298 : security compromise or software bug, these will FD_LOG_CRIT if
299 : corruption is detected to contain the blast radius and get as much
300 : ultra detailed diagnostic information to user (stack backtrace and
301 : core) as possible. (This behavior is straightforward to disable in
302 : fd_funk_txn.c.) */
303 :
304 : /**********************************************************************/
305 :
306 : /* fd_funk_txn_prepare starts preparation of a transaction. The
307 : transaction will be a child of the in-preparation transaction pointed
308 : to by parent. A NULL parent means the transaction should be a child
309 : of funk. xid points to transaction id that should be used for the
310 : transaction. This id must be unique over all in-preparation
311 : transactions, the root transaction and the last published
312 : transaction. It is strongly recommended to use globally unique ids
313 : when possible. Returns a pointer in the caller's address space to
314 : the in-preparation transaction on success and NULL on failure. The
315 : lifetime of the returned pointer is as described in
316 : fd_funk_txn_query.
317 :
318 : At start of preparation, the records in the txn are a virtual clone of the
319 : records in its parent transaction. The funk records can be modified
320 : when the funk has no children. Similarly, the records of an
321 : in-preparation transaction can be freely modified when it has
322 : no children.
323 :
324 : Assumes funk is a current local join. Reasons for failure include
325 : funk is NULL, the funk's transaction map is full, the parent is
326 : neither NULL nor points to an in-preparation funk transaction, xid is
327 : NULL, the requested xid is in use (i.e. the last published or matches
328 : another in-preparation transaction).
329 :
330 : This is a reasonably fast O(1) time (theoretical minimum), reasonably
331 : small O(1) space (theoretical minimum), does no allocation, does no
332 : system calls, and produces no garbage to collect (at this layer at
333 : least). That is, we can scalably track forks until we run out of
334 : resources allocated to the funk. */
335 :
336 : void
337 : fd_funk_txn_prepare( fd_funk_t * funk,
338 : fd_funk_txn_xid_t const * parent,
339 : fd_funk_txn_xid_t const * xid );
340 :
341 : /* fd_funk_txn_cancel cancels in-preparation transaction txn and any of
342 : its in-preparation descendants. On success, returns the number of
343 : transactions cancelled and 0 on failure. The state of records in the
344 : cancelled transactions will be lost and all resources used under the
345 : hood are available for reuse. If this makes the txn's parent
346 : childless, this will unfreeze the parent.
347 :
348 : fd_funk_txn_cancel_children cancels txn's children and their
349 : descendants. If txn is NULL, all children of funk will be cancelled
350 : (such that the number of transactions in preparation afterward will
351 : be zero).
352 :
353 : Cancellations proceed from youngest to oldest in a tree depth first
354 : sense.
355 :
356 : These are a reasonably fast O(number of cancelled transactions) time
357 : (the theoretical minimum), reasonably small O(1) space (the
358 : theoretical minimum), does no allocation, does no system calls, and
359 : produces no garbage to collect (at this layer at least). That is, we
360 : can scalably track forks until we run out of resources allocated to
361 : the funk. */
362 :
363 : ulong
364 : fd_funk_txn_cancel( fd_funk_t * funk,
365 : fd_funk_txn_xid_t const * xid );
366 :
367 : /* fd_funk_txn_cancel_all cancels all in-preparation
368 : transactions. Only the last published transaction remains. */
369 :
370 : ulong
371 : fd_funk_txn_cancel_all( fd_funk_t * funk );
372 :
373 : /* fd_funk_txn_publish publishes in-preparation transaction txn and any
374 : of txn's in-preparation ancestors. Returns the number of
375 : transactions published. Any competing histories to this chain will
376 : be cancelled.
377 :
378 : This is a reasonably fast O(number of published transactions) +
379 : O(number of cancelled transactions) time (theoretical minimum),
380 : reasonably small O(1) space (theoretical minimum), does no allocation
381 : does no system calls, and produces no garbage to collect (at this
382 : layer at least). That is, we can scalably track forks until we run
383 : out of resources allocated to the funk. */
384 :
385 : ulong
386 : fd_funk_txn_publish( fd_funk_t * funk,
387 : fd_funk_txn_xid_t const * xid );
388 :
389 : /* This version of publish just combines the transaction with its
390 : immediate parent. Ancestors will remain unpublished. Any competing
391 : histories (siblings of the given transaction) are still cancelled. */
392 : void
393 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
394 : fd_funk_txn_xid_t const * xid );
395 :
396 : /* fd_funk_txn_remove_published removes all published transactions.
397 : Funk instance must not have any funk transactions in preparation.
398 : On return, all records are freed, and the last published transaction
399 : is the root XID. */
400 :
401 : void
402 : fd_funk_txn_remove_published( fd_funk_t * funk );
403 :
404 : /* Misc */
405 :
406 : /* fd_funk_txn_verify verifies a transaction map. Returns
407 : FD_FUNK_SUCCESS if the transaction map appears intact and
408 : FD_FUNK_ERR_INVAL if not (logs details). Meant to be called as part
409 : of fd_funk_verify. */
410 :
411 : int
412 : fd_funk_txn_verify( fd_funk_t * funk );
413 :
414 : /* fd_funk_txn_valid returns true if txn appears to be a pointer to
415 : a valid in-prep transaction. */
416 :
417 : int
418 : fd_funk_txn_valid( fd_funk_t const * funk, fd_funk_txn_t const * txn );
419 :
420 : FD_FN_UNUSED static char const *
421 7311930 : fd_funk_txn_state_str( uint state ) {
422 7311930 : switch( state ) {
423 2437377 : case FD_FUNK_TXN_STATE_FREE: return "free";
424 2437377 : case FD_FUNK_TXN_STATE_ACTIVE: return "alive";
425 1955406 : case FD_FUNK_TXN_STATE_CANCEL: return "cancel";
426 481770 : case FD_FUNK_TXN_STATE_PUBLISH: return "publish";
427 0 : default: return "unknown";
428 7311930 : }
429 7311930 : }
430 :
431 : #ifndef __cplusplus
432 :
433 : FD_FN_UNUSED static void
434 : fd_funk_txn_state_assert( fd_funk_txn_t const * txn,
435 2488998 : uint want ) {
436 2488998 : uint have = FD_VOLATILE_CONST( txn->state );
437 2488998 : if( FD_UNLIKELY( want!=have ) ) {
438 0 : FD_LOG_CRIT(( "Invariant violation detected on funk txn: expected state %u-%s, found state %u-%s",
439 0 : want, fd_funk_txn_state_str( want ),
440 0 : have, fd_funk_txn_state_str( have ) ));
441 0 : }
442 2488998 : }
443 :
444 : FD_FN_UNUSED static void
445 : fd_funk_txn_xid_assert( fd_funk_txn_t const * txn,
446 48474057 : fd_funk_txn_xid_t const * xid ) {
447 48474057 : uint found_state = FD_VOLATILE_CONST( txn->state );
448 48474057 : fd_funk_txn_xid_t found_xid = FD_VOLATILE_CONST( txn->xid );
449 48474057 : int xid_ok = fd_funk_txn_xid_eq( &found_xid, xid );
450 48474057 : int state_ok = found_state==FD_FUNK_TXN_STATE_ACTIVE;
451 48474057 : if( FD_UNLIKELY( !xid_ok || !state_ok ) ) {
452 0 : if( !xid_ok ) {
453 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu use-after-free",
454 0 : (void *)txn,
455 0 : xid->ul[0], xid->ul[1] ));
456 0 : } else {
457 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu in invalid state %u-%s",
458 0 : (void *)txn,
459 0 : xid->ul[0], xid->ul[1],
460 0 : found_state, fd_funk_txn_state_str( found_state ) ));
461 0 : }
462 0 : }
463 48474057 : }
464 :
465 : #endif /* !__cplusplus */
466 :
467 : FD_PROTOTYPES_END
468 :
469 : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */
|
