Line data Source code
1 : #ifndef HEADER_fd_src_funk_fd_funk_rec_h
2 : #define HEADER_fd_src_funk_fd_funk_rec_h
3 :
4 : /* fd_funk_rec.h provides APIs for managing funk records */
5 :
6 : #include "fd_funk_txn.h" /* Includes fd_funk_base.h */
7 :
8 : /* FD_FUNK_REC_{ALIGN,FOOTPRINT} describe the alignment and footprint of
9 : a fd_funk_rec_t. ALIGN will be a power of 2, footprint will be a
10 : multiple of align. These are provided to facilitate compile time
11 : declarations. */
12 :
13 : #define FD_FUNK_REC_ALIGN (32UL)
14 :
15 : /* FD_FUNK_REC_IDX_NULL gives the map record idx value used to represent
16 : NULL. This value also set a limit on how large rec_max can be. */
17 :
18 823393578 : #define FD_FUNK_REC_IDX_NULL (UINT_MAX)
19 :
20 : /* A fd_funk_rec_t describes a funk record. */
21 :
22 : struct __attribute__((aligned(FD_FUNK_REC_ALIGN))) fd_funk_rec {
23 :
24 : /* These fields are managed by the funk's rec_map */
25 :
26 : fd_funk_xid_key_pair_t pair; /* Transaction id and record key pair */
27 : uint map_next; /* Internal use by map */
28 :
29 : /* These fields are managed by the user */
30 :
31 : uchar user[ 12 ];
32 :
33 : /* These fields are managed by funk. TODO: Consider using record
34 : index compression here (much more debatable than in txn itself). */
35 :
36 : uint next_idx; /* Record map index of next record in its transaction */
37 : uint prev_idx; /* Record map index of previous record in its transaction */
38 :
39 : /* Note: use of uint here requires FD_FUNK_REC_VAL_MAX to be at most
40 : (1UL<<28)-1. */
41 :
42 : ulong val_sz : 28; /* Num bytes in record value, in [0,val_max] */
43 : ulong val_max : 28; /* Max byte in record value, in [0,FD_FUNK_REC_VAL_MAX], 0 if val_gaddr is 0 */
44 : ulong tag : 1; /* Used for internal validation */
45 : ulong val_gaddr; /* Wksp gaddr on record value if any, 0 if val_max is 0
46 : If non-zero, the region [val_gaddr,val_gaddr+val_max) will be a current fd_alloc allocation (such that it is
47 : has tag wksp_tag) and the owner of the region will be the record. The allocator is
48 : fd_funk_alloc(). IMPORTANT! HAS NO GUARANTEED ALIGNMENT! */
49 :
50 : };
51 :
52 : typedef struct fd_funk_rec fd_funk_rec_t;
53 :
54 : FD_STATIC_ASSERT( sizeof(fd_funk_rec_t) == 3U*FD_FUNK_REC_ALIGN, record size is wrong );
55 :
56 : /* fd_funk_rec_map allows for indexing records by their (xid,key) pair.
57 : It is used to store all records of the last published transaction and
58 : the records being updated for a transaction that is in-preparation.
59 : Published records are stored under the pair (root,key). (This is
60 : done so that publishing a transaction doesn't require updating all
61 : transaction id of all the records that were not updated by the
62 : publish.) */
63 :
64 : #define POOL_NAME fd_funk_rec_pool
65 : #define POOL_ELE_T fd_funk_rec_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_rec_map
72 99510183 : #define MAP_ELE_T fd_funk_rec_t
73 : #define MAP_KEY_T fd_funk_xid_key_pair_t
74 : #define MAP_KEY pair
75 1408174134 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1))
76 701580702 : #define MAP_KEY_HASH(k0,seed) fd_funk_xid_key_pair_hash((k0),(seed))
77 : #define MAP_IDX_T uint
78 99510183 : #define MAP_NEXT map_next
79 : #define MAP_MAGIC (0xf173da2ce77ecdb0UL) /* Firedancer rec db version 0 */
80 : #define MAP_IMPL_STYLE 1
81 : #include "../util/tmpl/fd_map_chain_para.c"
82 :
83 : typedef fd_funk_rec_map_query_t fd_funk_rec_query_t;
84 :
85 : /* fd_funk_rec_prepare_t represents a new record that has been
86 : prepared but not inserted into the map yet. See documentation for
87 : fd_funk_rec_prepare. */
88 :
89 : struct _fd_funk_rec_prepare {
90 : fd_funk_rec_t * rec;
91 : uint * rec_head_idx;
92 : uint * rec_tail_idx;
93 : };
94 :
95 : typedef struct _fd_funk_rec_prepare fd_funk_rec_prepare_t;
96 :
97 : FD_PROTOTYPES_BEGIN
98 :
99 : /* fd_funk_rec_idx_is_null returns 1 if idx is FD_FUNK_REC_IDX_NULL and
100 : 0 otherwise. */
101 :
102 811147290 : FD_FN_CONST static inline int fd_funk_rec_idx_is_null( uint idx ) { return idx==FD_FUNK_REC_IDX_NULL; }
103 :
104 : /* Accessors */
105 :
106 : /* fd_funk_rec_modify attempts to modify the record corresponding to the
107 : given key in the given transaction. If the record does not exist,
108 : NULL will be returned. If the txn is NULL, the query will be done
109 : against funk's last published transaction (the root). On success,
110 : a mutable pointer to the funk record is returned.
111 :
112 : Assumes funk is a current local join (NULL returns NULL), txn is NULL
113 : or points to an in-preparation transaction in the caller's address
114 : space, key points to a record key in the caller's address space (NULL
115 : returns NULL). It is SAFE to do concurrent operations on funk with
116 : fd_funk_rec_modify.
117 :
118 : If there is contention for this record (or any records that are
119 : hashed to same chain as this record), the function will block the
120 : caller until the contention is resolved.
121 :
122 : A call to fd_funk_rec_modify must be followed by a call to
123 : fd_funk_rec_modify_publish.
124 :
125 : The query argument remembers the query for later validity testing.
126 :
127 : Important safety tips:
128 :
129 : 1. This function can encounter records that have the ERASE flag set
130 : (i.e. are tombstones of erased records). fd_funk_rec_query_try will
131 : still return the record in this case, and the application should
132 : check for the flag.
133 :
134 : 2. This function will not error if a caller attempts to modify a
135 : record from a non-current transaction (i.e. any funk transaction
136 : with a child). However, the caller should NEVER do this as it
137 : violates funk's invariants. */
138 :
139 : fd_funk_rec_t *
140 : fd_funk_rec_modify( fd_funk_t * funk,
141 : fd_funk_txn_xid_t const * xid,
142 : fd_funk_rec_key_t const * key,
143 : fd_funk_rec_query_t * query );
144 :
145 : /* fd_funk_rec_modify_publish commits any modifications to the record
146 : done by fd_funk_rec_modify. All notes from fd_funk_rec_modify
147 : apply. Calling fd_funk_rec_modify_publish is required and is
148 : responsible for freeing the lock on the record (and the hash
149 : chain). */
150 :
151 : void
152 : fd_funk_rec_modify_publish( fd_funk_rec_query_t * query );
153 :
154 :
155 : /* fd_funk_rec_query_try queries the in-preparation transaction pointed to
156 : by txn for the record whose key matches the key pointed to by key.
157 : If txn is NULL, the query will be done for the funk's last published
158 : transaction. Returns a pointer to current record on success and NULL
159 : on failure. Reasons for failure include txn is neither NULL nor a
160 : pointer to a in-preparation transaction, key is NULL or not a record
161 : in the given transaction.
162 :
163 : The returned pointer is in the caller's address space if the
164 : return value is non-NULL.
165 :
166 : Assumes funk is a current local join (NULL returns NULL), txn is NULL
167 : or points to an in-preparation transaction in the caller's address
168 : space, key points to a record key in the caller's address space (NULL
169 : returns NULL), and no concurrent operations on funk, txn or key.
170 : funk retains no interest in key. The funk retains ownership of any
171 : returned record.
172 :
173 : The query argument remembers the query for later validity testing.
174 :
175 : This is reasonably fast O(1).
176 :
177 : Important safety tip! This function can encounter records
178 : that have the ERASE flag set (i.e. are tombstones of erased
179 : records). fd_funk_rec_query_try will still return the record in this
180 : case, and the application should check for the flag. */
181 :
182 : fd_funk_rec_t const *
183 : fd_funk_rec_query_try( fd_funk_t * funk,
184 : fd_funk_txn_xid_t const * xid,
185 : fd_funk_rec_key_t const * key,
186 : fd_funk_rec_query_t * query );
187 :
188 : /* fd_funk_rec_query_test returns SUCCESS if a prior query still has a
189 : valid result. The coding pattern is:
190 :
191 : for(;;) {
192 : fd_funk_rec_query_t query[1];
193 : fd_funk_rec_t * rec = fd_funk_rec_query_try( funk, txn, key, query );
194 : ... Optimistically read record value ...
195 : if( fd_funk_rec_query_test( query ) == FD_FUNK_SUCCESS ) break;
196 : ... Clean up and try again ...
197 : }
198 : */
199 :
200 : int fd_funk_rec_query_test( fd_funk_rec_query_t * query );
201 :
202 : /* fd_funk_rec_query_try_global is the same as fd_funk_rec_query_try but
203 : will query txn's ancestors for key from youngest to oldest if key is
204 : not part of txn. As such, the txn of the returned record may not
205 : match txn but will be the txn of most recent ancestor with the key
206 : otherwise. If xid_out!=NULLL, *xid_out is set to the XID in which
207 : the record was created.
208 :
209 : This is reasonably fast O(in_prep_ancestor_cnt).
210 :
211 : Important safety tip! This function can encounter records
212 : that have the ERASE flag set (i.e. are tombstones of erased
213 : records). fd_funk_rec_query_try_global will return a NULL in this case
214 : but still set *txn_out to the relevant transaction. This behavior
215 : differs from fd_funk_rec_query_try. */
216 : fd_funk_rec_t const *
217 : fd_funk_rec_query_try_global( fd_funk_t const * funk,
218 : fd_funk_txn_xid_t const * xid,
219 : fd_funk_rec_key_t const * key,
220 : fd_funk_txn_xid_t * xid_out,
221 : fd_funk_rec_query_t * query );
222 :
223 : /* fd_funk_rec_query_copy queries the in-preparation transaction pointed to
224 : by txn for the record whose key matches the key pointed to by key.
225 :
226 : The contents of the record are safely copied into space allocated
227 : with the valloc, and a pointer to that space is returned. If there
228 : is an error, NULL is returned. The size of the record is returned
229 : in sz_out. */
230 :
231 : fd_funk_rec_t const *
232 : fd_funk_rec_query_copy( fd_funk_t * funk,
233 : fd_funk_txn_xid_t const * xid,
234 : fd_funk_rec_key_t const * key,
235 : fd_valloc_t valloc,
236 : ulong * sz_out );
237 :
238 : /* fd_funk_rec_{pair,xid,key} returns a pointer in the local address
239 : space of the {(transaction id,record key) pair,transaction id,record
240 : key} of a live record. Assumes rec points to a live record in the
241 : caller's address space. The lifetime of the returned pointer is the
242 : same as rec. The value at the pointer will be constant for its
243 : lifetime. */
244 :
245 1924437 : FD_FN_CONST static inline fd_funk_xid_key_pair_t const * fd_funk_rec_pair( fd_funk_rec_t const * rec ) { return &rec->pair; }
246 558670503 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_rec_xid ( fd_funk_rec_t const * rec ) { return rec->pair.xid; }
247 636586455 : FD_FN_CONST static inline fd_funk_rec_key_t const * fd_funk_rec_key ( fd_funk_rec_t const * rec ) { return rec->pair.key; }
248 :
249 : /* fd_funk_rec_prepare creates an unpublished funk record entry. This
250 : is the first step to adding a funk record to a transaction. Record
251 : entry acquisition may fail if the record object pool is exhausted
252 : (FD_FUNK_ERR_REC) or the transaction is not writable
253 : (FD_FUNK_ERR_FROZEN). The returned record entry (located in funk
254 : shared memory) is then either be cancelled or published by the
255 : caller. This record is invisible to funk query or record-iteration
256 : operations until published. Concurrent record preparation is fine. */
257 :
258 : fd_funk_rec_t *
259 : fd_funk_rec_prepare( fd_funk_t * funk,
260 : fd_funk_txn_xid_t const * xid,
261 : fd_funk_rec_key_t const * key,
262 : fd_funk_rec_prepare_t * prepare,
263 : int * opt_err );
264 :
265 : /* fd_funk_rec_publish makes a prepared record globally visible. First,
266 : registers a record with the txn's record list, then inserts it into
267 : the record map. Concurrent record publishing is fine, even to the
268 : same transaction. Crashes the application with FD_LOG_CRIT if the
269 : caller attempts to publish the same (txn,xid) key twice. */
270 :
271 : void
272 : fd_funk_rec_publish( fd_funk_t * funk,
273 : fd_funk_rec_prepare_t * prepare );
274 :
275 : /* fd_funk_rec_cancel returns an unpublished funk record entry back to
276 : the record object pool, invalidating the prepare struct. The caller
277 : cleans up any resources associated with the record (e.g. funk_val)
278 : before calling this function. */
279 :
280 : void
281 : fd_funk_rec_cancel( fd_funk_t * funk,
282 : fd_funk_rec_prepare_t * prepare );
283 :
284 : /* fd_funk_rec_clone copies a record from an ancestor transaction
285 : to create a new record in the given transaction. The record can be
286 : modified afterward and must then be published.
287 :
288 : NOTE: fd_funk_rec_clone is NOT thread safe and should not be used
289 : concurrently with other funk read/write operations. */
290 :
291 : fd_funk_rec_t *
292 : fd_funk_rec_clone( fd_funk_t * funk,
293 : fd_funk_txn_xid_t const * xid,
294 : fd_funk_rec_key_t const * key,
295 : fd_funk_rec_prepare_t * prepare,
296 : int * opt_err );
297 :
298 : /* Misc */
299 :
300 : /* fd_funk_rec_verify verifies the record map. Returns FD_FUNK_SUCCESS
301 : if the record map appears intact and FD_FUNK_ERR_INVAL if not (logs
302 : details). Meant to be called as part of fd_funk_verify. As such, it
303 : assumes funk is non-NULL, fd_funk_{wksp,txn_map,rec_map} have been
304 : verified to work and the txn_map has been verified. */
305 :
306 : int
307 : fd_funk_rec_verify( fd_funk_t * funk );
308 :
309 : FD_PROTOTYPES_END
310 :
311 : #endif /* HEADER_fd_src_funk_fd_funk_rec_h */
|
