Line data Source code
1 : #ifndef HEADER_fd_src_funk_fd_funkier_txn_h
2 : #define HEADER_fd_src_funk_fd_funkier_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_funkier.h instead. */
7 :
8 : #include "fd_funkier_base.h"
9 :
10 : /* FD_FUNKIER_TXN_{ALIGN,FOOTPRINT} describe the alignment and footprint of
11 : a fd_funkier_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_FUNKIER_TXN_ALIGN (32UL)
16 : #define FD_FUNKIER_TXN_FOOTPRINT (96UL)
17 :
18 : /* FD_FUNKIER_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 0 : #define FD_FUNKIER_TXN_IDX_NULL ((ulong)UINT_MAX)
25 :
26 : /* A fd_funkier_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_FUNKIER_TXN_ALIGN))) fd_funkier_txn_private {
31 :
32 : /* These fields are managed by the funk's txn_map */
33 :
34 : fd_funkier_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_FUNKIER_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 : ulong rec_head_idx; /* Record map index of the first record, FD_FUNKIER_REC_IDX_NULL if none (from oldest to youngest) */
50 : ulong rec_tail_idx; /* " last " */
51 : };
52 :
53 : typedef struct fd_funkier_txn_private fd_funkier_txn_t;
54 :
55 : /* fd_funkier_txn_map allows for indexing transactions by their xid */
56 :
57 : #define POOL_NAME fd_funkier_txn_pool
58 : #define POOL_ELE_T fd_funkier_txn_t
59 : #define POOL_IDX_T uint
60 : #define POOL_NEXT map_next
61 : #define POOL_IMPL_STYLE 1
62 : #include "../util/tmpl/fd_pool_para.c"
63 :
64 : #define MAP_NAME fd_funkier_txn_map
65 0 : #define MAP_ELE_T fd_funkier_txn_t
66 : #define MAP_KEY_T fd_funkier_txn_xid_t
67 : #define MAP_KEY xid
68 0 : #define MAP_KEY_EQ(k0,k1) fd_funkier_txn_xid_eq((k0),(k1))
69 0 : #define MAP_KEY_HASH(k0,seed) fd_funkier_txn_xid_hash((k0),(seed))
70 0 : #define MAP_NEXT map_next
71 : #define MAP_HASH map_hash
72 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
73 : #define MAP_IMPL_STYLE 1
74 : #include "../util/tmpl/fd_map_para.c"
75 : #undef MAP_HASH
76 :
77 : FD_PROTOTYPES_BEGIN
78 :
79 : /* fd_funkier_txn_{cidx,idx} convert between an index and a compressed index. */
80 :
81 0 : static inline uint fd_funkier_txn_cidx( ulong idx ) { return (uint) idx; }
82 0 : static inline ulong fd_funkier_txn_idx ( uint idx ) { return (ulong)idx; }
83 :
84 : /* fd_funkier_txn_idx_is_null returns 1 if idx is FD_FUNKIER_TXN_IDX_NULL and
85 : 0 otherwise. */
86 :
87 0 : static inline int fd_funkier_txn_idx_is_null( ulong idx ) { return idx==FD_FUNKIER_TXN_IDX_NULL; }
88 :
89 : /* Generate a globally unique pseudo-random xid */
90 : fd_funkier_txn_xid_t fd_funkier_generate_xid(void);
91 :
92 : /* Accessors */
93 :
94 : /* fd_funkier_txn_query returns a pointer to an in-preparation transaction
95 : whose id is pointed to by xid. Returns NULL if xid is not an
96 : in-preparation transaction. Assumes funk is a current local join,
97 : map==fd_funkier_txn_map( funk, fd_funkier_wksp( funk ) ), xid points to a
98 : transaction id in the caller's address space and there are no
99 : concurrent operations on funk or xid. Retains no interest in xid.
100 :
101 : The returned pointer is in the caller's address space and, if the
102 : return is non-NULL, the lifetime of the returned pointer is the
103 : lesser of the funk join or the transaction is published or canceled
104 : (either directly or indirectly via publish of a descendant, publish
105 : of a competing transaction history or cancel of an ancestor). */
106 :
107 : FD_FN_PURE static inline fd_funkier_txn_t *
108 : fd_funkier_txn_query( fd_funkier_txn_xid_t const * xid,
109 0 : fd_funkier_txn_map_t * map ) {
110 0 : fd_funkier_txn_map_query_t query[1];
111 0 : do {
112 0 : if( FD_UNLIKELY( fd_funkier_txn_map_query_try( map, xid, NULL, query ) ) ) return NULL;
113 0 : fd_funkier_txn_t * ele = fd_funkier_txn_map_query_ele( query );
114 0 : if( FD_LIKELY( !fd_funkier_txn_map_query_test( query ) ) ) return ele;
115 0 : } while( 1 );
116 0 : }
117 :
118 : /* fd_funkier_txn_xid returns a pointer in the local address space of the
119 : ID of an in-preparation transaction. Assumes txn points to an
120 : in-preparation transaction in the caller's address space. The
121 : lifetime of the returned pointer is the same as the txn's pointer
122 : lifetime. The value at the pointer will be stable for the lifetime
123 : of the returned pointer. */
124 :
125 0 : FD_FN_CONST static inline fd_funkier_txn_xid_t const * fd_funkier_txn_xid( fd_funkier_txn_t const * txn ) { return &txn->xid; }
126 :
127 : /* fd_funkier_txn_{parent,child_head,child_tail,sibling_prev,sibling_next}
128 : return a pointer in the caller's address space to the corresponding
129 : relative in-preparation transaction of in-preparation transaction
130 : txn.
131 :
132 : Specifically:
133 :
134 : - parent is the parent transaction. NULL if txn is a child of funk.
135 : - child_head is txn's oldest child. NULL if txn has no children.
136 : - child_tail is txn's youngest child. NULL if txn has no children.
137 : - sibling_prev is txn's closest older sibling. NULL if txn is the
138 : oldest sibling.
139 : - sibling_next is txn's closest younger sibling. NULL if txn is the
140 : youngest sibling.
141 :
142 : E.g. child_head==NULL indicates txn has no children.
143 : child_head!=NULL and child_head==child_tail indicates txn has one
144 : child. child_head!=NULL and child_tail!=NULL and
145 : child_head!=child_tail indicates txn has many children.
146 : sibling_prev==sibling_next==NULL indicate no siblings / locally
147 : competing transactions to txn. If the txn and all its ancestors have
148 : no siblings, there are no transaction histories competing with txn
149 : globally. */
150 :
151 : #define FD_FUNKIER_ACCESSOR(field) \
152 : FD_FN_PURE static inline fd_funkier_txn_t * \
153 : fd_funkier_txn_##field( fd_funkier_txn_t const * txn, \
154 0 : fd_funkier_txn_pool_t * pool ) { \
155 0 : ulong idx = fd_funkier_txn_idx( txn->field##_cidx ); \
156 0 : if( idx==FD_FUNKIER_TXN_IDX_NULL ) return NULL; \
157 0 : return pool->ele + idx; \
158 0 : }
159 :
160 : FD_FUNKIER_ACCESSOR( parent )
161 : FD_FUNKIER_ACCESSOR( child_head )
162 : FD_FUNKIER_ACCESSOR( child_tail )
163 : FD_FUNKIER_ACCESSOR( sibling_prev )
164 : FD_FUNKIER_ACCESSOR( sibling_next )
165 :
166 : #undef FD_FUNKIER_ACCESSOR
167 :
168 : /* fd_funkier_txn_frozen returns 1 if the in-preparation transaction is
169 : frozen (i.e. has children) and 0 otherwise (i.e. has no children).
170 : Assumes txn points to an in-preparation transaction in the caller's
171 : address space. */
172 :
173 : FD_FN_PURE static inline int
174 0 : fd_funkier_txn_is_frozen( fd_funkier_txn_t const * txn ) {
175 0 : return !fd_funkier_txn_idx_is_null( fd_funkier_txn_idx( txn->child_head_cidx ) );
176 0 : }
177 :
178 : /* fd_funkier_txn_is_only_child returns 1 if the in-preparation transaction
179 : txn if is any only child and 0 if it has one or more siblings.
180 : Assumes txn points to an in-preparation transaction in the caller's
181 : address space. */
182 :
183 : FD_FN_PURE static inline int
184 0 : fd_funkier_txn_is_only_child( fd_funkier_txn_t const * txn ) {
185 0 : return ( fd_funkier_txn_idx_is_null( fd_funkier_txn_idx( txn->sibling_prev_cidx ) ) ) &
186 0 : ( fd_funkier_txn_idx_is_null( fd_funkier_txn_idx( txn->sibling_next_cidx ) ) );
187 0 : }
188 :
189 : typedef struct fd_funkier_rec fd_funkier_rec_t;
190 :
191 : /* Return the first (oldest) record in a transaction. Returns NULL if the
192 : transaction has no records yet. */
193 :
194 : fd_funkier_rec_t const *
195 : fd_funkier_txn_first_rec( fd_funkier_t * funk,
196 : fd_funkier_txn_t const * txn );
197 :
198 : /* Return the last (newest) record in a transaction. Returns NULL if the
199 : transaction has no records yet. */
200 :
201 : fd_funkier_rec_t const *
202 : fd_funkier_txn_last_rec( fd_funkier_t * funk,
203 : fd_funkier_txn_t const * txn );
204 :
205 : /* Return the next record in a transaction. Returns NULL if the
206 : transaction has no more records. */
207 :
208 : FD_FN_PURE fd_funkier_rec_t const *
209 : fd_funkier_txn_next_rec( fd_funkier_t * funk,
210 : fd_funkier_rec_t const * rec );
211 :
212 : /* Return the previous record in a transaction. Returns NULL if the
213 : transaction has no more records. */
214 :
215 : FD_FN_PURE fd_funkier_rec_t const *
216 : fd_funkier_txn_prev_rec( fd_funkier_t * funk,
217 : fd_funkier_rec_t const * rec );
218 :
219 : /* Operations */
220 :
221 : /* fd_funkier_txn_ancestor returns a pointer in the caller's address space
222 : to the youngest transaction among in-preparation transaction txn and
223 : its ancestors that currently has siblings. Returns NULL if all
224 : transactions back to the root transaction have no siblings (e.g.
225 : there are no competing transaction histories and thus publishing
226 : transaction txn will not require canceling any other competing
227 : transactions). This is a reasonably fast O(length of ancestor
228 : history) time (theoretical minimum) and a reasonably small O(1) space
229 : (theoretical minimum). This is not fortified against transaction map
230 : data corruption.
231 :
232 : fd_funkier_txn_descendant returns a pointer in the caller's address
233 : space to the first transaction among txn and its youngest direct
234 : descendant inclusive that currently either has no children or has
235 : multiple children. Returns NULL if txn is not an only child. This
236 : is a reasonably fast O(length of descendant history) time
237 : (theoretical minimum) and a reasonably small O(1) space (theoretical
238 : minimum). This is not fortified against transaction map data
239 : corruption.
240 :
241 : That is, if txn's ancestor is NULL, all transactions up to and
242 : including txn's descendant (which will be non-NULL) can be published
243 : without cancelling any competing transactions. Further, if the
244 : descendant has a child, it has multiple children. And if has no
245 : children, all transactions in preparation are linear from the root to
246 : the descendant.
247 :
248 : In code:
249 :
250 : if( !fd_funkier_txn_ancestor( txn, map ) )
251 : fd_funkier_publish( funk, fd_funkier_txn_descendant( funk, map ) );
252 :
253 : would publish as much currently uncontested transaction history as
254 : possible around txn. */
255 :
256 : FD_FN_PURE static inline fd_funkier_txn_t *
257 : fd_funkier_txn_ancestor( fd_funkier_txn_t * txn,
258 0 : fd_funkier_txn_pool_t * pool ) {
259 0 : for(;;) {
260 0 : if( !fd_funkier_txn_is_only_child( txn ) ) break;
261 0 : fd_funkier_txn_t * parent = fd_funkier_txn_parent( txn, pool );
262 0 : if( !parent ) return NULL;
263 0 : txn = parent;
264 0 : }
265 0 : return txn;
266 0 : }
267 :
268 : FD_FN_PURE static inline fd_funkier_txn_t *
269 : fd_funkier_txn_descendant( fd_funkier_txn_t * txn,
270 0 : fd_funkier_txn_pool_t * pool ) {
271 0 : if( !fd_funkier_txn_is_only_child( txn ) ) return NULL;
272 0 : for(;;) { /* txn is an only child at this point */
273 0 : fd_funkier_txn_t * child = fd_funkier_txn_child_head( txn, pool );
274 0 : if( !child || !fd_funkier_txn_is_only_child( child ) ) break;
275 0 : txn = child;
276 0 : }
277 0 : return txn;
278 0 : }
279 :
280 : /* IMPORTANT SAFETY TIP! **********************************************/
281 :
282 : /* fd_funkier_txn_{prepare,publish,cancel,cancel_siblings,cancel_children}
283 : are the pointy end of the stick practically. As such, these are
284 : fortified against transaction map memory corruption. Since any such
285 : corruption would be prima facie evidence of a hardware fault,
286 : security compromise or software bug, these will FD_LOG_CRIT if
287 : corruption is detected to contain the blast radius and get as much
288 : ultra detailed diagnostic information to user (stack backtrace and
289 : core) as possible. (This behavior is straightforward to disable in
290 : fd_funkier_txn.c.) */
291 :
292 : /**********************************************************************/
293 :
294 : /* fd_funkier_txn_prepare starts preparation of a transaction. The
295 : transaction will be a child of the in-preparation transaction pointed
296 : to by parent. A NULL parent means the transaction should be a child
297 : of funk. xid points to transaction id that should be used for the
298 : transaction. This id must be unique over all in-preparation
299 : transactions, the root transaction and the last published
300 : transaction. It is strongly recommended to use globally unique ids
301 : when possible. Returns a pointer in the caller's address space to
302 : the in-preparation transaction on success and NULL on failure. The
303 : lifetime of the returned pointer is as described in
304 : fd_funkier_txn_query.
305 :
306 : At start of preparation, the records in the txn are a virtual clone of the
307 : records in its parent transaction. The funk records can be modified
308 : when the funk has no children. Similarly, the records of an
309 : in-preparation transaction can be freely modified when it has
310 : no children.
311 :
312 : Assumes funk is a current local join. Reasons for failure include
313 : funk is NULL, the funk's transaction map is full, the parent is
314 : neither NULL nor points to an in-preparation funk transaction, xid is
315 : NULL, the requested xid is in use (i.e. the last published or matches
316 : another in-preparation transaction). If verbose is non-zero, these
317 : will FD_LOG_WARNING details about the reason for failure.
318 :
319 : This is a reasonably fast O(1) time (theoretical minimum), reasonably
320 : small O(1) space (theoretical minimum), does no allocation, does no
321 : system calls, and produces no garbage to collect (at this layer at
322 : least). That is, we can scalably track forks until we run out of
323 : resources allocated to the funk. */
324 :
325 : fd_funkier_txn_t *
326 : fd_funkier_txn_prepare( fd_funkier_t * funk,
327 : fd_funkier_txn_t * parent,
328 : fd_funkier_txn_xid_t const * xid,
329 : int verbose );
330 :
331 : /* fd_funkier_txn_is_full returns true if the transaction map is
332 : full. No more in-preparation transactions are allowed. */
333 :
334 : int
335 : fd_funkier_txn_is_full( fd_funkier_t * funk );
336 :
337 : /* fd_funkier_txn_cancel cancels in-preparation transaction txn and any of
338 : its in-preparation descendants. On success, returns the number of
339 : transactions cancelled and 0 on failure. The state of records in the
340 : cancelled transactions will be lost and all resources used under the
341 : hood are available for reuse. If this makes the txn's parent
342 : childless, this will unfreeze the parent.
343 :
344 : fd_funkier_txn_cancel_siblings cancels txn's siblings and their
345 : descendants.
346 :
347 : fd_funkier_txn_cancel_children cancels txn's children and their
348 : descendants. If txn is NULL, all children of funk will be cancelled
349 : (such that the number of transactions in preparation afterward will
350 : be zero).
351 :
352 : Cancellations proceed from youngest to oldest in a tree depth first
353 : sense.
354 :
355 : Assumes funk is a current local join. Reasons for failure include
356 : NULL funk or txn does not point to an in-preparation funk
357 : transaction. If verbose is non-zero, these will FD_LOG_WARNING level
358 : details about the reason for failure.
359 :
360 : These are a reasonably fast O(number of cancelled transactions) time
361 : (the theoretical minimum), reasonably small O(1) space (the
362 : theoretical minimum), does no allocation, does no system calls, and
363 : produces no garbage to collect (at this layer at least). That is, we
364 : can scalably track forks until we run out of resources allocated to
365 : the funk. */
366 :
367 : ulong
368 : fd_funkier_txn_cancel( fd_funkier_t * funk,
369 : fd_funkier_txn_t * txn,
370 : int verbose );
371 :
372 : ulong
373 : fd_funkier_txn_cancel_siblings( fd_funkier_t * funk,
374 : fd_funkier_txn_t * txn,
375 : int verbose );
376 :
377 : ulong
378 : fd_funkier_txn_cancel_children( fd_funkier_t * funk,
379 : fd_funkier_txn_t * txn,
380 : int verbose );
381 :
382 : /* fd_funkier_txn_cancel_all cancels all in-preparation
383 : transactions. Only the last published transaction remains. */
384 :
385 : ulong
386 : fd_funkier_txn_cancel_all( fd_funkier_t * funk,
387 : int verbose );
388 :
389 : /* fd_funkier_txn_publish publishes in-preparation transaction txn and any
390 : of txn's in-preparation ancestors. Returns the number of
391 : transactions published. Any competing histories to this chain will
392 : be cancelled.
393 :
394 : Assumes funk is a current local join. Reasons for failure include
395 : NULL funk, txn does not point to an in-preparation funk transaction.
396 : If verbose is non-zero, these will FD_LOG_WARNING the details about
397 : the reason for failure.
398 :
399 : This is a reasonably fast O(number of published transactions) +
400 : O(number of cancelled transactions) time (theoretical minimum),
401 : reasonably small O(1) space (theoretical minimum), does no allocation
402 : does no system calls, and produces no garbage to collect (at this
403 : layer at least). That is, we can scalably track forks until we run
404 : out of resources allocated to the funk. */
405 :
406 : ulong
407 : fd_funkier_txn_publish( fd_funkier_t * funk,
408 : fd_funkier_txn_t * txn,
409 : int verbose );
410 :
411 : /* This version of publish just combines the transaction with its
412 : immediate parent. Ancestors will remain unpublished. Any competing
413 : histories (siblings of the given transaction) are still cancelled.
414 :
415 : Returns FD_FUNKIER_SUCCESS on success or an error code on failure. */
416 : int
417 : fd_funkier_txn_publish_into_parent( fd_funkier_t * funk,
418 : fd_funkier_txn_t * txn,
419 : int verbose );
420 :
421 : /* Iterator which walks all in-preparation transactions. Usage is:
422 :
423 : fd_funkier_txn_all_iter_t txn_iter[1];
424 : for( fd_funkier_txn_all_iter_new( funk, txn_iter ); !fd_funkier_txn_all_iter_done( txn_iter ); fd_funkier_txn_all_iter_next( txn_iter ) ) {
425 : fd_funkier_txn_t const * txn = fd_funkier_txn_all_iter_ele_const( txn_iter );
426 : ...
427 : }
428 : */
429 :
430 : struct fd_funkier_txn_all_iter {
431 : fd_funkier_txn_map_t txn_map;
432 : ulong chain_cnt;
433 : ulong chain_idx;
434 : fd_funkier_txn_map_iter_t txn_map_iter;
435 : };
436 :
437 : typedef struct fd_funkier_txn_all_iter fd_funkier_txn_all_iter_t;
438 :
439 : void fd_funkier_txn_all_iter_new( fd_funkier_t * funk, fd_funkier_txn_all_iter_t * iter );
440 :
441 : int fd_funkier_txn_all_iter_done( fd_funkier_txn_all_iter_t * iter );
442 :
443 : void fd_funkier_txn_all_iter_next( fd_funkier_txn_all_iter_t * iter );
444 :
445 : fd_funkier_txn_t const * fd_funkier_txn_all_iter_ele_const( fd_funkier_txn_all_iter_t * iter );
446 : fd_funkier_txn_t * fd_funkier_txn_all_iter_ele( fd_funkier_txn_all_iter_t * iter );
447 :
448 : /* Misc */
449 :
450 : #ifdef FD_FUNKIER_HANDHOLDING
451 :
452 : /* fd_funkier_txn_verify verifies a transaction map. Returns
453 : FD_FUNKIER_SUCCESS if the transaction map appears intact and
454 : FD_FUNKIER_ERR_INVAL if not (logs details). Meant to be called as part
455 : of fd_funkier_verify. */
456 :
457 : int
458 : fd_funkier_txn_verify( fd_funkier_t * funk );
459 :
460 : /* fd_funkier_txn_valid returns true if txn appears to be a pointer to
461 : a valid in-prep transaction. */
462 :
463 : int
464 : fd_funkier_txn_valid( fd_funkier_t * funk, fd_funkier_txn_t const * txn );
465 :
466 : #endif
467 :
468 : FD_PROTOTYPES_END
469 :
470 : #endif /* HEADER_fd_src_funk_fd_funkier_txn_h */
|
