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 : #include "../flamenco/fd_rwlock.h"
15 :
16 : /* FD_FUNK_TXN_{ALIGN,FOOTPRINT} describe the alignment and footprint of
17 : a fd_funk_txn_t. ALIGN will be a power of 2, footprint will be a
18 : multiple of align. These are provided to facilitate compile time
19 : declarations. */
20 :
21 : #define FD_FUNK_TXN_ALIGN (32UL)
22 : #define FD_FUNK_TXN_FOOTPRINT (96UL)
23 :
24 : /* FD_FUNK_TXN_IDX_NULL gives the map transaction idx value used to
25 : represent NULL. It also is the maximum value for txn_max in a funk
26 : to support index compression. (E.g. could use ushort / USHORT_MAX
27 : to use more aggressive compression or ulong / ULONG_MAX to disable
28 : index compression.) */
29 :
30 6989763 : #define FD_FUNK_TXN_IDX_NULL ((ulong)UINT_MAX)
31 :
32 : /* A fd_funk_txn_t is an opaque handle of an in-preparation funk
33 : transaction. The details are exposed here to facilitate inlining
34 : various operations. */
35 :
36 : struct __attribute__((aligned(FD_FUNK_TXN_ALIGN))) fd_funk_txn_private {
37 :
38 : /* These fields are managed by the funk's txn_map */
39 :
40 : fd_funk_txn_xid_t xid; /* Transaction id, at a minimum, unique among all in-prepare and the last published transaction,
41 : ideally globally unique */
42 : ulong map_next; /* 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 : fd_rwlock_t lock[1];
60 : };
61 :
62 : typedef struct fd_funk_txn_private fd_funk_txn_t;
63 :
64 : /* fd_funk_txn_map allows for indexing transactions by their xid */
65 :
66 : #define POOL_NAME fd_funk_txn_pool
67 6 : #define POOL_ELE_T fd_funk_txn_t
68 : #define POOL_IDX_T uint
69 : #define POOL_NEXT map_next
70 : #define POOL_IMPL_STYLE 1
71 : #include "../util/tmpl/fd_pool_para.c"
72 :
73 : #define MAP_NAME fd_funk_txn_map
74 1092 : #define MAP_ELE_T fd_funk_txn_t
75 : #define MAP_KEY_T fd_funk_txn_xid_t
76 : #define MAP_KEY xid
77 1676715 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
78 2267880 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
79 1092 : #define MAP_NEXT map_next
80 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
81 : #define MAP_IMPL_STYLE 1
82 : #include "../util/tmpl/fd_map_chain_para.c"
83 : #undef MAP_HASH
84 :
85 : /* Funk transaction states */
86 :
87 2724384 : #define FD_FUNK_TXN_STATE_FREE (0U)
88 895512 : #define FD_FUNK_TXN_STATE_ACTIVE (1U)
89 348846 : #define FD_FUNK_TXN_STATE_CANCEL (2U)
90 224583 : #define FD_FUNK_TXN_STATE_PUBLISH (3U)
91 :
92 : FD_PROTOTYPES_BEGIN
93 :
94 : /* fd_funk_txn_{cidx,idx} convert between an index and a compressed index. */
95 :
96 5084592 : static inline uint fd_funk_txn_cidx( ulong idx ) { return (uint) idx; }
97 3765099 : static inline ulong fd_funk_txn_idx ( uint cidx ) { return (ulong)cidx; }
98 :
99 : /* fd_funk_txn_idx_is_null returns 1 if idx is FD_FUNK_TXN_IDX_NULL and
100 : 0 otherwise. */
101 :
102 4292196 : static inline int fd_funk_txn_idx_is_null( ulong idx ) { return idx==FD_FUNK_TXN_IDX_NULL; }
103 :
104 : /* Accessors */
105 :
106 : /* fd_funk_txn_query returns a pointer to an in-preparation transaction
107 : whose id is pointed to by xid. Returns NULL if xid is not an
108 : in-preparation transaction. Assumes funk is a current local join,
109 : map==fd_funk_txn_map( funk, fd_funk_wksp( funk ) ), xid points to a
110 : transaction id in the caller's address space and there are no
111 : concurrent operations on funk or xid. Retains no interest in xid.
112 :
113 : The returned pointer is in the caller's address space and, if the
114 : return is non-NULL, the lifetime of the returned pointer is the
115 : lesser of the funk join or the transaction is published or canceled
116 : (either directly or indirectly via publish of a descendant, publish
117 : of a competing transaction history or cancel of an ancestor). */
118 :
119 : FD_FN_PURE static inline fd_funk_txn_t *
120 : fd_funk_txn_query( fd_funk_txn_xid_t const * xid,
121 224787 : fd_funk_txn_map_t * map ) {
122 224787 : do {
123 224787 : fd_funk_txn_map_query_t query[1];
124 224787 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( map, xid, NULL, query, 0 ) ) ) return NULL;
125 224787 : fd_funk_txn_t * ele = fd_funk_txn_map_query_ele( query );
126 224787 : if( FD_LIKELY( !fd_funk_txn_map_query_test( query ) ) ) return ele;
127 224787 : } while( 1 );
128 224787 : }
129 :
130 : /* fd_funk_txn_xid returns a pointer in the local address space of the
131 : ID of an in-preparation transaction. Assumes txn points to an
132 : in-preparation transaction in the caller's address space. The
133 : lifetime of the returned pointer is the same as the txn's pointer
134 : lifetime. The value at the pointer will be stable for the lifetime
135 : of the returned pointer. */
136 :
137 225675 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_txn_xid( fd_funk_txn_t const * txn ) { return &txn->xid; }
138 :
139 : /* fd_funk_txn_{parent,child_head,child_tail,sibling_prev,sibling_next}
140 : return a pointer in the caller's address space to the corresponding
141 : relative in-preparation transaction of in-preparation transaction
142 : txn.
143 :
144 : Specifically:
145 :
146 : - parent is the parent transaction. NULL if txn is a child of funk.
147 : - child_head is txn's oldest child. NULL if txn has no children.
148 : - child_tail is txn's youngest child. NULL if txn has no children.
149 : - sibling_prev is txn's closest older sibling. NULL if txn is the
150 : oldest sibling.
151 : - sibling_next is txn's closest younger sibling. NULL if txn is the
152 : youngest sibling.
153 :
154 : E.g. child_head==NULL indicates txn has no children.
155 : child_head!=NULL and child_head==child_tail indicates txn has one
156 : child. child_head!=NULL and child_tail!=NULL and
157 : child_head!=child_tail indicates txn has many children.
158 : sibling_prev==sibling_next==NULL indicate no siblings / locally
159 : competing transactions to txn. If the txn and all its ancestors have
160 : no siblings, there are no transaction histories competing with txn
161 : globally. */
162 :
163 : #define FD_FUNK_ACCESSOR(field) \
164 : FD_FN_PURE static inline fd_funk_txn_t * \
165 : fd_funk_txn_##field( fd_funk_txn_t const * txn, \
166 18 : fd_funk_txn_pool_t const * pool ) { \
167 18 : ulong idx = fd_funk_txn_idx( txn->field##_cidx ); \
168 18 : if( idx==FD_FUNK_TXN_IDX_NULL ) return NULL; \
169 18 : return pool->ele + idx; \
170 18 : }
171 :
172 18 : FD_FUNK_ACCESSOR( parent )
173 : FD_FUNK_ACCESSOR( child_head )
174 : FD_FUNK_ACCESSOR( child_tail )
175 : FD_FUNK_ACCESSOR( sibling_prev )
176 : FD_FUNK_ACCESSOR( sibling_next )
177 :
178 : #undef FD_FUNK_ACCESSOR
179 :
180 : /* fd_funk_txn_frozen returns 1 if the in-preparation transaction is
181 : frozen (i.e. has children) and 0 otherwise (i.e. has no children).
182 : Assumes txn points to an in-preparation transaction in the caller's
183 : address space. */
184 :
185 : FD_FN_PURE static inline int
186 507 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) {
187 507 : return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) );
188 507 : }
189 :
190 : typedef struct fd_funk_rec fd_funk_rec_t;
191 :
192 : /* Operations */
193 : /* fd_funk_txn_prepare starts preparation of a transaction. The
194 : transaction will be a child of the in-preparation transaction pointed
195 : to by parent. A NULL parent means the transaction should be a child
196 : of funk. xid points to transaction id that should be used for the
197 : transaction. This id must be unique over all in-preparation
198 : transactions, the root transaction and the last published
199 : transaction. It is strongly recommended to use globally unique ids
200 : when possible. Returns a pointer in the caller's address space to
201 : the in-preparation transaction on success and NULL on failure. The
202 : lifetime of the returned pointer is as described in
203 : fd_funk_txn_query.
204 :
205 : At start of preparation, the records in the txn are a virtual clone of the
206 : records in its parent transaction. The funk records can be modified
207 : when the funk has no children. Similarly, the records of an
208 : in-preparation transaction can be freely modified when it has
209 : no children.
210 :
211 : Assumes funk is a current local join. Reasons for failure include
212 : funk is NULL, the funk's transaction map is full, the parent is
213 : neither NULL nor points to an in-preparation funk transaction, xid is
214 : NULL, the requested xid is in use (i.e. the last published or matches
215 : another in-preparation transaction).
216 :
217 : This is a reasonably fast O(1) time (theoretical minimum), reasonably
218 : small O(1) space (theoretical minimum), does no allocation, does no
219 : system calls, and produces no garbage to collect (at this layer at
220 : least). That is, we can scalably track forks until we run out of
221 : resources allocated to the funk. */
222 :
223 : void
224 : fd_funk_txn_prepare( fd_funk_t * funk,
225 : fd_funk_txn_xid_t const * parent,
226 : fd_funk_txn_xid_t const * xid );
227 :
228 : /* Misc */
229 :
230 : /* fd_funk_txn_verify verifies a transaction map. Returns
231 : FD_FUNK_SUCCESS if the transaction map appears intact and
232 : FD_FUNK_ERR_INVAL if not (logs details). Meant to be called as part
233 : of fd_funk_verify. */
234 :
235 : int
236 : fd_funk_txn_verify( fd_funk_t * funk );
237 :
238 : FD_FN_UNUSED static char const *
239 1146912 : fd_funk_txn_state_str( uint state ) {
240 1146912 : switch( state ) {
241 573456 : case FD_FUNK_TXN_STATE_FREE: return "free";
242 573456 : case FD_FUNK_TXN_STATE_ACTIVE: return "alive";
243 0 : case FD_FUNK_TXN_STATE_CANCEL: return "cancel";
244 0 : case FD_FUNK_TXN_STATE_PUBLISH: return "publish";
245 0 : default: return "unknown";
246 1146912 : }
247 1146912 : }
248 :
249 : #ifndef __cplusplus
250 :
251 : FD_FN_UNUSED static void
252 : fd_funk_txn_state_assert( fd_funk_txn_t const * txn,
253 317868 : uint want ) {
254 317868 : uint have = FD_VOLATILE_CONST( txn->state );
255 317868 : if( FD_UNLIKELY( want!=have ) ) {
256 0 : FD_LOG_CRIT(( "Invariant violation detected on funk txn: expected state %u-%s, found state %u-%s",
257 0 : want, fd_funk_txn_state_str( want ),
258 0 : have, fd_funk_txn_state_str( have ) ));
259 0 : }
260 317868 : }
261 :
262 : FD_FN_UNUSED static void
263 : fd_funk_txn_xid_assert( fd_funk_txn_t const * txn,
264 4188 : fd_funk_txn_xid_t const * xid ) {
265 4188 : uint found_state = FD_VOLATILE_CONST( txn->state );
266 4188 : fd_funk_txn_xid_t found_xid = FD_VOLATILE_CONST( txn->xid );
267 4188 : int xid_ok = fd_funk_txn_xid_eq( &found_xid, xid );
268 4188 : int state_ok = found_state==FD_FUNK_TXN_STATE_ACTIVE;
269 4188 : if( FD_UNLIKELY( !xid_ok || !state_ok ) ) {
270 0 : if( !xid_ok ) {
271 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu use-after-free",
272 0 : (void *)txn,
273 0 : xid->ul[0], xid->ul[1] ));
274 0 : } else {
275 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu in invalid state %u-%s",
276 0 : (void *)txn,
277 0 : xid->ul[0], xid->ul[1],
278 0 : found_state, fd_funk_txn_state_str( found_state ) ));
279 0 : }
280 0 : }
281 4188 : }
282 :
283 : #endif /* !__cplusplus */
284 :
285 : FD_PROTOTYPES_END
286 :
287 : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */
|
