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