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 4741681057 : #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 386218 : #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 3511763862 : #define MAP_ELE_T fd_funk_txn_t
67 : #define MAP_KEY_T fd_funk_txn_xid_t
68 : #define MAP_KEY xid
69 344393252 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
70 388482216 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
71 3511763862 : #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 58085899 : static inline uint fd_funk_txn_cidx( ulong idx ) { return (uint) idx; }
83 4738195911 : 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 4098897030 : 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 385054842 : fd_funk_txn_map_t * map ) {
146 385054842 : do {
147 385054842 : fd_funk_txn_map_query_t query[1];
148 385054842 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( map, xid, NULL, query, 0 ) ) ) return NULL;
149 180254469 : fd_funk_txn_t * ele = fd_funk_txn_map_query_ele( query );
150 180254469 : if( FD_LIKELY( !fd_funk_txn_map_query_test( query ) ) ) return ele;
151 180254469 : } while( 1 );
152 385054842 : }
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 211299096 : 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 439983612 : fd_funk_txn_pool_t const * pool ) { \
191 439983612 : ulong idx = fd_funk_txn_idx( txn->field##_cidx ); \
192 439983612 : if( idx==FD_FUNK_TXN_IDX_NULL ) return NULL; \
193 439983612 : return pool->ele + idx; \
194 439983612 : }
195 :
196 : FD_FUNK_ACCESSOR( parent )
197 : FD_FUNK_ACCESSOR( child_head )
198 : FD_FUNK_ACCESSOR( child_tail )
199 : FD_FUNK_ACCESSOR( sibling_prev )
200 : 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 3796961125 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) {
211 3796961125 : return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) );
212 3796961125 : }
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 : /* Return the first (oldest) record in a transaction. Returns NULL if the
228 : transaction has no records yet. */
229 :
230 : fd_funk_rec_t const *
231 : fd_funk_txn_first_rec( fd_funk_t * funk,
232 : fd_funk_txn_t const * txn );
233 :
234 : /* Return the last (newest) record in a transaction. Returns NULL if the
235 : transaction has no records yet. */
236 :
237 : fd_funk_rec_t const *
238 : fd_funk_txn_last_rec( fd_funk_t * funk,
239 : fd_funk_txn_t const * txn );
240 :
241 : /* Return the next record in a transaction. Returns NULL if the
242 : transaction has no more records. */
243 :
244 : fd_funk_rec_t const *
245 : fd_funk_txn_next_rec( fd_funk_t * funk,
246 : fd_funk_rec_t const * rec );
247 :
248 : /* Return the previous record in a transaction. Returns NULL if the
249 : transaction has no more records. */
250 :
251 : fd_funk_rec_t const *
252 : fd_funk_txn_prev_rec( fd_funk_t * funk,
253 : fd_funk_rec_t const * rec );
254 :
255 : /* Operations */
256 :
257 : /* fd_funk_txn_ancestor returns a pointer in the caller's address space
258 : to the youngest transaction among in-preparation transaction txn and
259 : its ancestors that currently has siblings. Returns NULL if all
260 : transactions back to the root transaction have no siblings (e.g.
261 : there are no competing transaction histories and thus publishing
262 : transaction txn will not require canceling any other competing
263 : transactions). This is a reasonably fast O(length of ancestor
264 : history) time (theoretical minimum) and a reasonably small O(1) space
265 : (theoretical minimum). This is not fortified against transaction map
266 : data corruption.
267 :
268 : fd_funk_txn_descendant returns a pointer in the caller's address
269 : space to the first transaction among txn and its youngest direct
270 : descendant inclusive that currently either has no children or has
271 : multiple children. Returns NULL if txn is not an only child. This
272 : is a reasonably fast O(length of descendant history) time
273 : (theoretical minimum) and a reasonably small O(1) space (theoretical
274 : minimum). This is not fortified against transaction map data
275 : corruption.
276 :
277 : That is, if txn's ancestor is NULL, all transactions up to and
278 : including txn's descendant (which will be non-NULL) can be published
279 : without cancelling any competing transactions. Further, if the
280 : descendant has a child, it has multiple children. And if has no
281 : children, all transactions in preparation are linear from the root to
282 : the descendant.
283 :
284 : In code:
285 :
286 : if( !fd_funk_txn_ancestor( txn, map ) )
287 : fd_funk_publish( funk, fd_funk_txn_descendant( funk, map ) );
288 :
289 : would publish as much currently uncontested transaction history as
290 : possible around txn. */
291 :
292 : FD_FN_PURE static inline fd_funk_txn_t *
293 : fd_funk_txn_ancestor( fd_funk_txn_t * txn,
294 42528654 : fd_funk_txn_pool_t * pool ) {
295 56997111 : for(;;) {
296 56997111 : if( !fd_funk_txn_is_only_child( txn ) ) break;
297 15218796 : fd_funk_txn_t * parent = fd_funk_txn_parent( txn, pool );
298 15218796 : if( !parent ) return NULL;
299 14468457 : txn = parent;
300 14468457 : }
301 41778315 : return txn;
302 42528654 : }
303 :
304 : FD_FN_PURE static inline fd_funk_txn_t *
305 : fd_funk_txn_descendant( fd_funk_txn_t * txn,
306 42528654 : fd_funk_txn_pool_t * pool ) {
307 42528654 : if( !fd_funk_txn_is_only_child( txn ) ) return NULL;
308 15218796 : for(;;) { /* txn is an only child at this point */
309 15218796 : fd_funk_txn_t * child = fd_funk_txn_child_head( txn, pool );
310 15218796 : if( !child || !fd_funk_txn_is_only_child( child ) ) break;
311 3350406 : txn = child;
312 3350406 : }
313 11868390 : return txn;
314 42528654 : }
315 :
316 : /* IMPORTANT SAFETY TIP! **********************************************/
317 :
318 : /* fd_funk_txn_{prepare,publish,cancel,cancel_siblings,cancel_children}
319 : are the pointy end of the stick practically. As such, these are
320 : fortified against transaction map memory corruption. Since any such
321 : corruption would be prima facie evidence of a hardware fault,
322 : security compromise or software bug, these will FD_LOG_CRIT if
323 : corruption is detected to contain the blast radius and get as much
324 : ultra detailed diagnostic information to user (stack backtrace and
325 : core) as possible. (This behavior is straightforward to disable in
326 : fd_funk_txn.c.) */
327 :
328 : /**********************************************************************/
329 :
330 : /* fd_funk_txn_prepare starts preparation of a transaction. The
331 : transaction will be a child of the in-preparation transaction pointed
332 : to by parent. A NULL parent means the transaction should be a child
333 : of funk. xid points to transaction id that should be used for the
334 : transaction. This id must be unique over all in-preparation
335 : transactions, the root transaction and the last published
336 : transaction. It is strongly recommended to use globally unique ids
337 : when possible. Returns a pointer in the caller's address space to
338 : the in-preparation transaction on success and NULL on failure. The
339 : lifetime of the returned pointer is as described in
340 : fd_funk_txn_query.
341 :
342 : At start of preparation, the records in the txn are a virtual clone of the
343 : records in its parent transaction. The funk records can be modified
344 : when the funk has no children. Similarly, the records of an
345 : in-preparation transaction can be freely modified when it has
346 : no children.
347 :
348 : Assumes funk is a current local join. Reasons for failure include
349 : funk is NULL, the funk's transaction map is full, the parent is
350 : neither NULL nor points to an in-preparation funk transaction, xid is
351 : NULL, the requested xid is in use (i.e. the last published or matches
352 : another in-preparation transaction). If verbose is non-zero, these
353 : will FD_LOG_WARNING details about the reason for failure.
354 :
355 : This is a reasonably fast O(1) time (theoretical minimum), reasonably
356 : small O(1) space (theoretical minimum), does no allocation, does no
357 : system calls, and produces no garbage to collect (at this layer at
358 : least). That is, we can scalably track forks until we run out of
359 : resources allocated to the funk. */
360 :
361 : fd_funk_txn_t *
362 : fd_funk_txn_prepare( fd_funk_t * funk,
363 : fd_funk_txn_t * parent,
364 : fd_funk_txn_xid_t const * xid,
365 : int verbose );
366 :
367 : /* fd_funk_txn_cancel cancels in-preparation transaction txn and any of
368 : its in-preparation descendants. On success, returns the number of
369 : transactions cancelled and 0 on failure. The state of records in the
370 : cancelled transactions will be lost and all resources used under the
371 : hood are available for reuse. If this makes the txn's parent
372 : childless, this will unfreeze the parent.
373 :
374 : fd_funk_txn_cancel_siblings cancels txn's siblings and their
375 : descendants.
376 :
377 : fd_funk_txn_cancel_children cancels txn's children and their
378 : descendants. If txn is NULL, all children of funk will be cancelled
379 : (such that the number of transactions in preparation afterward will
380 : be zero).
381 :
382 : Cancellations proceed from youngest to oldest in a tree depth first
383 : sense.
384 :
385 : Assumes funk is a current local join. Reasons for failure include
386 : NULL funk or txn does not point to an in-preparation funk
387 : transaction. If verbose is non-zero, these will FD_LOG_WARNING level
388 : details about the reason for failure.
389 :
390 : These are a reasonably fast O(number of cancelled transactions) time
391 : (the theoretical minimum), reasonably small O(1) space (the
392 : theoretical minimum), does no allocation, does no system calls, and
393 : produces no garbage to collect (at this layer at least). That is, we
394 : can scalably track forks until we run out of resources allocated to
395 : the funk. */
396 :
397 : ulong
398 : fd_funk_txn_cancel( fd_funk_t * funk,
399 : fd_funk_txn_t * txn,
400 : int verbose );
401 :
402 : ulong
403 : fd_funk_txn_cancel_siblings( fd_funk_t * funk,
404 : fd_funk_txn_t * txn,
405 : int verbose );
406 :
407 : ulong
408 : fd_funk_txn_cancel_children( fd_funk_t * funk,
409 : fd_funk_txn_t * txn,
410 : int verbose );
411 :
412 : /* fd_funk_txn_cancel_all cancels all in-preparation
413 : transactions. Only the last published transaction remains. */
414 :
415 : ulong
416 : fd_funk_txn_cancel_all( fd_funk_t * funk,
417 : int verbose );
418 :
419 : /* fd_funk_txn_publish publishes in-preparation transaction txn and any
420 : of txn's in-preparation ancestors. Returns the number of
421 : transactions published. Any competing histories to this chain will
422 : be cancelled.
423 :
424 : Assumes funk is a current local join. Reasons for failure include
425 : NULL funk, txn does not point to an in-preparation funk transaction.
426 : If verbose is non-zero, these will FD_LOG_WARNING the details about
427 : the reason for failure.
428 :
429 : This is a reasonably fast O(number of published transactions) +
430 : O(number of cancelled transactions) time (theoretical minimum),
431 : reasonably small O(1) space (theoretical minimum), does no allocation
432 : does no system calls, and produces no garbage to collect (at this
433 : layer at least). That is, we can scalably track forks until we run
434 : out of resources allocated to the funk. */
435 :
436 : ulong
437 : fd_funk_txn_publish( fd_funk_t * funk,
438 : fd_funk_txn_t * txn,
439 : int verbose );
440 :
441 : /* This version of publish just combines the transaction with its
442 : immediate parent. Ancestors will remain unpublished. Any competing
443 : histories (siblings of the given transaction) are still cancelled.
444 :
445 : Returns FD_FUNK_SUCCESS on success or an error code on failure. */
446 : int
447 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
448 : fd_funk_txn_t * txn,
449 : int verbose );
450 :
451 : /* fd_funk_txn_all_iter_t iterators over all funk transaction objects.
452 : Usage is:
453 :
454 : fd_funk_txn_all_iter_t txn_iter[1];
455 : 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 ) ) {
456 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
457 : ...
458 : }
459 : */
460 :
461 : struct fd_funk_txn_all_iter {
462 : fd_funk_txn_map_t txn_map;
463 : ulong chain_cnt;
464 : ulong chain_idx;
465 : fd_funk_txn_map_iter_t txn_map_iter;
466 : };
467 :
468 : typedef struct fd_funk_txn_all_iter fd_funk_txn_all_iter_t;
469 :
470 : void fd_funk_txn_all_iter_new( fd_funk_t * funk, fd_funk_txn_all_iter_t * iter );
471 :
472 : int fd_funk_txn_all_iter_done( fd_funk_txn_all_iter_t * iter );
473 :
474 : void fd_funk_txn_all_iter_next( fd_funk_txn_all_iter_t * iter );
475 :
476 : fd_funk_txn_t const * fd_funk_txn_all_iter_ele_const( fd_funk_txn_all_iter_t * iter );
477 : fd_funk_txn_t * fd_funk_txn_all_iter_ele( fd_funk_txn_all_iter_t * iter );
478 :
479 : /* Misc */
480 :
481 : /* fd_funk_txn_verify verifies a transaction map. Returns
482 : FD_FUNK_SUCCESS if the transaction map appears intact and
483 : FD_FUNK_ERR_INVAL if not (logs details). Meant to be called as part
484 : of fd_funk_verify. */
485 :
486 : int
487 : fd_funk_txn_verify( fd_funk_t * funk );
488 :
489 : /* fd_funk_txn_valid returns true if txn appears to be a pointer to
490 : a valid in-prep transaction. */
491 :
492 : int
493 : fd_funk_txn_valid( fd_funk_t const * funk, fd_funk_txn_t const * txn );
494 :
495 : FD_PROTOTYPES_END
496 :
497 : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */
|
