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 : /* This provides APIs for managing funk records. It is generally not
5 : meant to be included directly. Use fd_funk.h instead.
6 :
7 : The following APIs are thread safe and can be interleaved arbirarily
8 : across threads:
9 : fd_funk_rec_query_try
10 : fd_funk_rec_query_test
11 : fd_funk_rec_query_try_global
12 : fd_funk_rec_prepare
13 : fd_funk_rec_publish
14 : fd_funk_rec_cancel
15 : fd_funk_rec_remove
16 : */
17 :
18 : #include "fd_funk_txn.h" /* Includes fd_funk_base.h */
19 :
20 : /* FD_FUNK_REC_{ALIGN,FOOTPRINT} describe the alignment and footprint of
21 : a fd_funk_rec_t. ALIGN will be a power of 2, footprint will be a
22 : multiple of align. These are provided to facilitate compile time
23 : declarations. */
24 :
25 : #define FD_FUNK_REC_ALIGN (64UL)
26 :
27 : /* FD_FUNK_REC_FLAG_* are flags that can be bit-ored together to specify
28 : how records are to be interpreted. The 5 most significant bytes of a
29 : rec's flag are reserved to be used in conjunction with the ERASE flag.
30 :
31 : - ERASE indicates a record in an in-preparation transaction should be
32 : erased if and when the in-preparation transaction is published. If
33 : set on a published record, it serves as a tombstone.
34 : If set, there will be no value resources used by this record. */
35 :
36 18806709 : #define FD_FUNK_REC_FLAG_ERASE (1UL<<0)
37 :
38 : /* FD_FUNK_REC_IDX_NULL gives the map record idx value used to represent
39 : NULL. This value also set a limit on how large rec_max can be. */
40 :
41 821207910 : #define FD_FUNK_REC_IDX_NULL (UINT_MAX)
42 :
43 : /* A fd_funk_rec_t describes a funk record. */
44 :
45 : struct __attribute__((aligned(FD_FUNK_REC_ALIGN))) fd_funk_rec {
46 :
47 : /* These fields are managed by the funk's rec_map */
48 :
49 : fd_funk_xid_key_pair_t pair; /* Transaction id and record key pair */
50 : uint map_next; /* Internal use by map */
51 : ulong map_hash; /* Internal use by map */
52 :
53 : /* These fields are managed by funk. TODO: Consider using record
54 : index compression here (much more debatable than in txn itself). */
55 :
56 : uint prev_idx; /* Record map index of previous record in its transaction */
57 : uint next_idx; /* Record map index of next record in its transaction */
58 :
59 : uint txn_cidx; /* Compressed transaction map index (or compressed FD_FUNK_TXN_IDX if this is in the last published) */
60 : uint tag; /* Internal use only */
61 : ulong flags; /* Flags that indicate how to interpret a record */
62 :
63 : /* Note: use of uint here requires FD_FUNK_REC_VAL_MAX to be at most
64 : UINT_MAX. */
65 :
66 : uint val_sz; /* Num bytes in record value, in [0,val_max] */
67 : uint val_max; /* Max byte in record value, in [0,FD_FUNK_REC_VAL_MAX], 0 if erase flag set or val_gaddr is 0 */
68 : ulong val_gaddr; /* Wksp gaddr on record value if any, 0 if erase flag set or val_max is 0
69 : If non-zero, the region [val_gaddr,val_gaddr+val_max) will be a current fd_alloc allocation (such that it is
70 : has tag wksp_tag) and the owner of the region will be the record. The allocator is
71 : fd_funk_alloc(). IMPORTANT! HAS NO GUARANTEED ALIGNMENT! */
72 :
73 : /* Padding to FD_FUNK_REC_ALIGN here */
74 : };
75 :
76 : typedef struct fd_funk_rec fd_funk_rec_t;
77 :
78 : FD_STATIC_ASSERT( sizeof(fd_funk_rec_t) == 2U*FD_FUNK_REC_ALIGN, record size is wrong );
79 :
80 : /* fd_funk_rec_map allows for indexing records by their (xid,key) pair.
81 : It is used to store all records of the last published transaction and
82 : the records being updated for a transaction that is in-preparation.
83 : Published records are stored under the pair (root,key). (This is
84 : done so that publishing a transaction doesn't require updating all
85 : transaction id of all the records that were not updated by the
86 : publish.) */
87 :
88 : #define POOL_NAME fd_funk_rec_pool
89 : #define POOL_ELE_T fd_funk_rec_t
90 : #define POOL_IDX_T uint
91 : #define POOL_NEXT map_next
92 : #define POOL_IMPL_STYLE 1
93 : #include "../util/tmpl/fd_pool_para.c"
94 :
95 : #define MAP_NAME fd_funk_rec_map
96 108951618 : #define MAP_ELE_T fd_funk_rec_t
97 : #define MAP_KEY_T fd_funk_xid_key_pair_t
98 : #define MAP_KEY pair
99 705495510 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1))
100 387592995 : #define MAP_KEY_HASH(k0,seed) fd_funk_xid_key_pair_hash((k0),(seed))
101 : #define MAP_IDX_T uint
102 108951618 : #define MAP_NEXT map_next
103 : #define MAP_MEMO map_hash
104 : #define MAP_MAGIC (0xf173da2ce77ecdb0UL) /* Firedancer rec db version 0 */
105 : #define MAP_MEMOIZE 1
106 : #define MAP_IMPL_STYLE 1
107 : #include "../util/tmpl/fd_map_chain_para.c"
108 : #undef MAP_MEMOIZE
109 : #undef MAP_HASH
110 :
111 : typedef fd_funk_rec_map_query_t fd_funk_rec_query_t;
112 :
113 : /* fd_funk_rec_prepare_t represents a new record that has been
114 : prepared but not inserted into the map yet. See documentation for
115 : fd_funk_rec_prepare. */
116 :
117 : struct _fd_funk_rec_prepare {
118 : fd_funk_rec_t * rec;
119 : uint * rec_head_idx;
120 : uint * rec_tail_idx;
121 : uchar * txn_lock;
122 : };
123 :
124 : typedef struct _fd_funk_rec_prepare fd_funk_rec_prepare_t;
125 :
126 : FD_PROTOTYPES_BEGIN
127 :
128 : /* fd_funk_rec_idx_is_null returns 1 if idx is FD_FUNK_REC_IDX_NULL and
129 : 0 otherwise. */
130 :
131 813084177 : FD_FN_CONST static inline int fd_funk_rec_idx_is_null( uint idx ) { return idx==FD_FUNK_REC_IDX_NULL; }
132 :
133 : /* Accessors */
134 :
135 : /* fd_funk_rec_modify attempts to modify the record corresponding to the
136 : given key in the given transaction. If the record does not exist,
137 : NULL will be returned. If the txn is NULL, the query will be done
138 : against funk's last published transaction (the root). On success,
139 : a mutable pointer to the funk record is returned.
140 :
141 : Assumes funk is a current local join (NULL returns NULL), txn is NULL
142 : or points to an in-preparation transaction in the caller's address
143 : space, key points to a record key in the caller's address space (NULL
144 : returns NULL). It is SAFE to do concurrent operations on funk with
145 : fd_funk_rec_modify.
146 :
147 : If there is contention for this record (or any records that are
148 : hashed to same chain as this record), the function will block the
149 : caller until the contention is resolved.
150 :
151 : A call to fd_funk_rec_modify must be followed by a call to
152 : fd_funk_rec_modify_publish.
153 :
154 : The query argument remembers the query for later validity testing.
155 :
156 : Important safety tips:
157 :
158 : 1. This function can encounter records that have the ERASE flag set
159 : (i.e. are tombstones of erased records). fd_funk_rec_query_try will
160 : still return the record in this case, and the application should
161 : check for the flag.
162 :
163 : 2. This function will not error if a caller attempts to modify a
164 : record from a non-current transaction (i.e. any funk transaction
165 : with a child). However, the caller should NEVER do this as it
166 : violates funk's invariants. */
167 :
168 : fd_funk_rec_t *
169 : fd_funk_rec_modify( fd_funk_t * funk,
170 : fd_funk_txn_t const * txn,
171 : fd_funk_rec_key_t const * key,
172 : fd_funk_rec_query_t * query );
173 :
174 : /* fd_funk_rec_modify_publish commits any modifications to the record
175 : done by fd_funk_rec_modify. All notes from fd_funk_rec_modify
176 : apply. Calling fd_funk_rec_modify_publish is required and is
177 : responsible for freeing the lock on the record (and the hash
178 : chain). */
179 :
180 : void
181 : fd_funk_rec_modify_publish( fd_funk_rec_query_t * query );
182 :
183 :
184 : /* fd_funk_rec_query_try queries the in-preparation transaction pointed to
185 : by txn for the record whose key matches the key pointed to by key.
186 : If txn is NULL, the query will be done for the funk's last published
187 : transaction. Returns a pointer to current record on success and NULL
188 : on failure. Reasons for failure include txn is neither NULL nor a
189 : pointer to a in-preparation transaction, key is NULL or not a record
190 : in the given transaction.
191 :
192 : The returned pointer is in the caller's address space if the
193 : return value is non-NULL.
194 :
195 : Assumes funk is a current local join (NULL returns NULL), txn is NULL
196 : or points to an in-preparation transaction in the caller's address
197 : space, key points to a record key in the caller's address space (NULL
198 : returns NULL), and no concurrent operations on funk, txn or key.
199 : funk retains no interest in key. The funk retains ownership of any
200 : returned record.
201 :
202 : The query argument remembers the query for later validity testing.
203 :
204 : This is reasonably fast O(1).
205 :
206 : Important safety tip! This function can encounter records
207 : that have the ERASE flag set (i.e. are tombstones of erased
208 : records). fd_funk_rec_query_try will still return the record in this
209 : case, and the application should check for the flag. */
210 :
211 : fd_funk_rec_t const *
212 : fd_funk_rec_query_try( fd_funk_t * funk,
213 : fd_funk_txn_t const * txn,
214 : fd_funk_rec_key_t const * key,
215 : fd_funk_rec_query_t * query );
216 :
217 : /* fd_funk_rec_query_test returns SUCCESS if a prior query still has a
218 : valid result. The coding pattern is:
219 :
220 : for(;;) {
221 : fd_funk_rec_query_t query[1];
222 : fd_funk_rec_t * rec = fd_funk_rec_query_try( funk, txn, key, query );
223 : ... Optimistically read record value ...
224 : if( fd_funk_rec_query_test( query ) == FD_FUNK_SUCCESS ) break;
225 : ... Clean up and try again ...
226 : }
227 : */
228 :
229 : int fd_funk_rec_query_test( fd_funk_rec_query_t * query );
230 :
231 : /* fd_funk_rec_query_try_global is the same as fd_funk_rec_query_try but
232 : will query txn's ancestors for key from youngest to oldest if key is
233 : not part of txn. As such, the txn of the returned record may not
234 : match txn but will be the txn of most recent ancestor with the key
235 : otherwise. *txn_out is set to the transaction where the record was
236 : found.
237 :
238 : This is reasonably fast O(in_prep_ancestor_cnt).
239 :
240 : Important safety tip! This function can encounter records
241 : that have the ERASE flag set (i.e. are tombstones of erased
242 : records). fd_funk_rec_query_try_global will return a NULL in this case
243 : but still set *txn_out to the relevant transaction. This behavior
244 : differs from fd_funk_rec_query_try.
245 :
246 : TODO: This function should be renamed to fd_funk_rec_query_try
247 : and fd_funk_rec_query_try should be renamed to
248 : fd_funk_rec_query_try_strict. */
249 : fd_funk_rec_t const *
250 : fd_funk_rec_query_try_global( fd_funk_t const * funk,
251 : fd_funk_txn_t const * txn,
252 : fd_funk_rec_key_t const * key,
253 : fd_funk_txn_t const ** txn_out,
254 : fd_funk_rec_query_t * query );
255 :
256 : /* fd_funk_rec_query_copy queries the in-preparation transaction pointed to
257 : by txn for the record whose key matches the key pointed to by key.
258 :
259 : The contents of the record are safely copied into space allocated
260 : with the valloc, and a pointer to that space is returned. If there
261 : is an error, NULL is returned. The size of the record is returned
262 : in sz_out. */
263 :
264 : fd_funk_rec_t const *
265 : fd_funk_rec_query_copy( fd_funk_t * funk,
266 : fd_funk_txn_t const * txn,
267 : fd_funk_rec_key_t const * key,
268 : fd_valloc_t valloc,
269 : ulong * sz_out );
270 :
271 : /* fd_funk_rec_{pair,xid,key} returns a pointer in the local address
272 : space of the {(transaction id,record key) pair,transaction id,record
273 : key} of a live record. Assumes rec points to a live record in the
274 : caller's address space. The lifetime of the returned pointer is the
275 : same as rec. The value at the pointer will be constant for its
276 : lifetime. */
277 :
278 1541577 : 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; }
279 541372653 : 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; }
280 644353608 : 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; }
281 :
282 : /* fd_funk_rec_prepare prepares to insert a new record. This call just
283 : allocates a record from the pool and initializes it.
284 : The application should then fill in the new
285 : value. fd_funk_rec_publish actually does the map insert and
286 : should be called once the value is correct. */
287 :
288 : fd_funk_rec_t *
289 : fd_funk_rec_prepare( fd_funk_t * funk,
290 : fd_funk_txn_t * txn,
291 : fd_funk_rec_key_t const * key,
292 : fd_funk_rec_prepare_t * prepare,
293 : int * opt_err );
294 :
295 : /* fd_funk_rec_publish inserts a prepared record into the record map. */
296 :
297 : void
298 : fd_funk_rec_publish( fd_funk_t * funk,
299 : fd_funk_rec_prepare_t * prepare );
300 :
301 : /* fd_funk_rec_cancel returns a prepared record to the pool without
302 : inserting it. */
303 :
304 : void
305 : fd_funk_rec_cancel( fd_funk_t * funk,
306 : fd_funk_rec_prepare_t * prepare );
307 :
308 : /* fd_funk_rec_clone copies a record from an ancestor transaction
309 : to create a new record in the given transaction. The record can be
310 : modified afterward and must then be published.
311 :
312 : NOTE: fd_funk_rec_clone is NOT thread safe and should not be used
313 : concurrently with other funk read/write operations. */
314 :
315 : fd_funk_rec_t *
316 : fd_funk_rec_clone( fd_funk_t * funk,
317 : fd_funk_txn_t * txn,
318 : fd_funk_rec_key_t const * key,
319 : fd_funk_rec_prepare_t * prepare,
320 : int * opt_err );
321 :
322 : /* fd_funk_rec_insert_para does thread-safe insertion of a funk record.
323 :
324 : Detailed Behavior:
325 :
326 : More specifically, first this function will query the transaction
327 : stack to identify what the youngest transaction with the key is. If
328 : a record is found in the current transaction then it will exit.
329 : In the case where a record is found in some ancestor txn or if the
330 : record doesn't exist, the function will then acquire a lock on the
331 : keypair of the youngest ancestor account (if it exists) and the
332 : keypair of the account we want to create. These two keys are
333 : guaranteed to be on the same hash chain so in practice we will just
334 : be locking the hash chain for the key.
335 :
336 : Once this lock is acquired, we will query the keypair for the keypair
337 : we are going to create to make sure that it wasn't added in the time
338 : that we were attempting to acquire the lock. If a keypair is found,
339 : we will free the lock and exit the function.
340 :
341 : Otherwise, we will allocate a new account record. Now we will add
342 : this into the record map. At this point, we can now free the lock on
343 : the hash chain. */
344 :
345 : void
346 : fd_funk_rec_insert_para( fd_funk_t * funk,
347 : fd_funk_txn_t * txn,
348 : fd_funk_rec_key_t const * key );
349 :
350 : /* fd_funk_rec_remove removes the live record with the
351 : given (xid,key) from funk. Returns FD_FUNK_SUCCESS (0) on
352 : success and an FD_FUNK_ERR_* (negative) on failure. Reasons for
353 : failure include:
354 :
355 : FD_FUNK_ERR_INVAL - bad inputs (NULL funk, NULL xid)
356 :
357 : FD_FUNK_ERR_KEY - the record did not appear to be a live record.
358 : Specifically, a record query of funk for rec's (xid,key) pair did
359 : not return rec.
360 :
361 : The record will cease to exist in that transaction and any of
362 : transaction's subsequently created descendants (again, assuming no
363 : subsequent insert of key). This type of remove can be done on a
364 : published record (assuming the last published transaction is
365 : unfrozen). A tombstone is left in funk to track removals as they
366 : are published or cancelled.
367 :
368 : Any information in an erased record is lost.
369 :
370 : This is a reasonably fast O(1) and fortified against memory
371 : corruption. */
372 :
373 : int
374 : fd_funk_rec_remove( fd_funk_t * funk,
375 : fd_funk_txn_t * txn,
376 : fd_funk_rec_key_t const * key,
377 : fd_funk_rec_t ** rec_out );
378 :
379 : /* fd_funk_all_iter_t iterators over all funk record objects in all funk
380 : transactions.
381 :
382 : Assumes that no other join is doing funk write accesses during the
383 : lifetime of the iterator object. This API is not optimized for
384 : performance and has a high fixed cost (slow even for empty DBs).
385 :
386 : Usage is:
387 :
388 : fd_funk_all_iter_t iter[1];
389 : for( fd_funk_all_iter_new( funk, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
390 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
391 : ...
392 : } */
393 :
394 : struct fd_funk_all_iter {
395 : fd_funk_rec_map_t rec_map;
396 : ulong chain_cnt;
397 : ulong chain_idx;
398 : fd_funk_rec_map_iter_t rec_map_iter;
399 : };
400 :
401 : typedef struct fd_funk_all_iter fd_funk_all_iter_t;
402 :
403 : void fd_funk_all_iter_new( fd_funk_t * funk, fd_funk_all_iter_t * iter );
404 :
405 : int fd_funk_all_iter_done( fd_funk_all_iter_t * iter );
406 :
407 : void fd_funk_all_iter_next( fd_funk_all_iter_t * iter );
408 :
409 : fd_funk_rec_t const * fd_funk_all_iter_ele_const( fd_funk_all_iter_t * iter );
410 :
411 : fd_funk_rec_t * fd_funk_all_iter_ele( fd_funk_all_iter_t * iter );
412 :
413 : /* Misc */
414 :
415 : /* fd_funk_rec_verify verifies the record map. Returns FD_FUNK_SUCCESS
416 : if the record map appears intact and FD_FUNK_ERR_INVAL if not (logs
417 : details). Meant to be called as part of fd_funk_verify. As such, it
418 : assumes funk is non-NULL, fd_funk_{wksp,txn_map,rec_map} have been
419 : verified to work and the txn_map has been verified. */
420 :
421 : int
422 : fd_funk_rec_verify( fd_funk_t * funk );
423 :
424 : int
425 : fd_funk_rec_purify( fd_funk_t * funk );
426 :
427 : FD_PROTOTYPES_END
428 :
429 : #endif /* HEADER_fd_src_funk_fd_funk_rec_h */
|
