Line data Source code
1 : #ifndef HEADER_fd_src_funk_fd_funkier_rec_h
2 : #define HEADER_fd_src_funk_fd_funkier_rec_h
3 :
4 : /* This provides APIs for managing funk records. It is generally not
5 : meant to be included directly. Use fd_funkier.h instead.
6 :
7 : The following APIs are thread safe and can be interleaved arbirarily
8 : across threads:
9 : fd_funkier_rec_query_try
10 : fd_funkier_rec_query_test
11 : fd_funkier_rec_query_try_global
12 : fd_funkier_rec_prepare
13 : fd_funkier_rec_publish
14 : fd_funkier_rec_cancel
15 : fd_funkier_rec_remove
16 : */
17 :
18 : #include "fd_funkier_txn.h" /* Includes fd_funkier_base.h */
19 :
20 : /* FD_FUNKIER_REC_{ALIGN,FOOTPRINT} describe the alignment and footprint of
21 : a fd_funkier_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_FUNKIER_REC_ALIGN (64UL)
26 :
27 : /* FD_FUNKIER_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 0 : #define FD_FUNKIER_REC_FLAG_ERASE (1UL<<0)
37 :
38 : /* FD_FUNKIER_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 0 : #define FD_FUNKIER_REC_IDX_NULL (ULONG_MAX)
42 :
43 : /* A fd_funkier_rec_t describes a funk record. */
44 :
45 : struct __attribute__((aligned(FD_FUNKIER_REC_ALIGN))) fd_funkier_rec {
46 :
47 : /* These fields are managed by the funk's rec_map */
48 :
49 : fd_funkier_xid_key_pair_t pair; /* Transaction id and record key pair */
50 : ulong 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 : ulong prev_idx; /* Record map index of previous record in its transaction */
57 : ulong next_idx; /* Record map index of next record in its transaction */
58 : uint txn_cidx; /* Compressed transaction map index (or compressed FD_FUNKIER_TXN_IDX if this is in the last published) */
59 : uint tag; /* Internal use only */
60 : ulong flags; /* Flags that indicate how to interpret a record */
61 :
62 : /* Note: use of uint here requires FD_FUNKIER_REC_VAL_MAX to be at most
63 : UINT_MAX. */
64 :
65 : uint val_sz; /* Num bytes in record value, in [0,val_max] */
66 : uint val_max; /* Max byte in record value, in [0,FD_FUNKIER_REC_VAL_MAX], 0 if erase flag set or val_gaddr is 0 */
67 : ulong val_gaddr; /* Wksp gaddr on record value if any, 0 if erase flag set or val_max is 0
68 : If non-zero, the region [val_gaddr,val_gaddr+val_max) will be a current fd_alloc allocation (such that it is
69 : has tag wksp_tag) and the owner of the region will be the record. The allocator is
70 : fd_funkier_alloc(). IMPORTANT! HAS NO GUARANTEED ALIGNMENT! */
71 :
72 :
73 : /* Padding to FD_FUNKIER_REC_ALIGN here */
74 : };
75 :
76 : typedef struct fd_funkier_rec fd_funkier_rec_t;
77 :
78 : FD_STATIC_ASSERT( sizeof(fd_funkier_rec_t) == 2U*FD_FUNKIER_REC_ALIGN, record size is wrong );
79 :
80 : /* fd_funkier_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_funkier_rec_pool
89 : #define POOL_ELE_T fd_funkier_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_funkier_rec_map
96 0 : #define MAP_ELE_T fd_funkier_rec_t
97 : #define MAP_KEY_T fd_funkier_xid_key_pair_t
98 : #define MAP_KEY pair
99 0 : #define MAP_KEY_EQ(k0,k1) fd_funkier_xid_key_pair_eq((k0),(k1))
100 0 : #define MAP_KEY_HASH(k0,seed) fd_funkier_xid_key_pair_hash((k0),(seed))
101 0 : #define MAP_NEXT map_next
102 : #define MAP_MEMO map_hash
103 : #define MAP_MAGIC (0xf173da2ce77ecdb0UL) /* Firedancer rec db version 0 */
104 : #define MAP_MEMOIZE 1
105 : #define MAP_IMPL_STYLE 1
106 : #include "../util/tmpl/fd_map_para.c"
107 : #undef MAP_MEMOIZE
108 : #undef MAP_HASH
109 :
110 : typedef fd_funkier_rec_map_query_t fd_funkier_rec_query_t;
111 :
112 : /* fd_funkier_rec_prepare_t represents a new record that has been
113 : prepared but not inserted into the map yet. See documentation for
114 : fd_funkier_rec_prepare. */
115 :
116 : struct _fd_funkier_rec_prepare {
117 : fd_funkier_t * funk;
118 : fd_wksp_t * wksp;
119 : fd_funkier_rec_t * rec;
120 : ulong * rec_head_idx;
121 : ulong * rec_tail_idx;
122 : };
123 :
124 : typedef struct _fd_funkier_rec_prepare fd_funkier_rec_prepare_t;
125 :
126 : FD_PROTOTYPES_BEGIN
127 :
128 : /* fd_funkier_rec_idx_is_null returns 1 if idx is FD_FUNKIER_REC_IDX_NULL and
129 : 0 otherwise. */
130 :
131 0 : FD_FN_CONST static inline int fd_funkier_rec_idx_is_null( ulong idx ) { return idx==FD_FUNKIER_REC_IDX_NULL; }
132 :
133 : /* Accessors */
134 :
135 : /* fd_funkier_rec_query_try queries the in-preparation transaction pointed to
136 : by txn for the record whose key matches the key pointed to by key.
137 : If txn is NULL, the query will be done for the funk's last published
138 : transaction. Returns a pointer to current record on success and NULL
139 : on failure. Reasons for failure include txn is neither NULL nor a
140 : pointer to a in-preparation transaction, key is NULL or not a record
141 : in the given transaction.
142 :
143 : The returned pointer is in the caller's address space if the
144 : return value is non-NULL.
145 :
146 : Assumes funk is a current local join (NULL returns NULL), txn is NULL
147 : or points to an in-preparation transaction in the caller's address
148 : space, key points to a record key in the caller's address space (NULL
149 : returns NULL), and no concurrent operations on funk, txn or key.
150 : funk retains no interest in key. The funk retains ownership of any
151 : returned record.
152 :
153 : The query argument remembers the query for later validity testing.
154 :
155 : This is reasonably fast O(1).
156 :
157 : Important safety tip! This function can encounter records
158 : that have the ERASE flag set (i.e. are tombstones of erased
159 : records). fd_funkier_rec_query_try will still return the record in this
160 : case, and the application should check for the flag. */
161 :
162 : fd_funkier_rec_t const *
163 : fd_funkier_rec_query_try( fd_funkier_t * funk,
164 : fd_funkier_txn_t const * txn,
165 : fd_funkier_rec_key_t const * key,
166 : fd_funkier_rec_query_t * query );
167 :
168 : /* fd_funkier_rec_query_test returns SUCCESS if a prior query still has a
169 : valid result. The coding pattern is:
170 :
171 : for(;;) {
172 : fd_funkier_rec_query_t query[1];
173 : fd_funkier_rec_t * rec = fd_funkier_rec_query_try( funk, txn, key, query );
174 : ... Optimistically read record value ...
175 : if( fd_funkier_rec_query_test( query ) == FD_FUNKIER_SUCCESS ) break;
176 : ... Clean up and try again ...
177 : }
178 : */
179 :
180 : int fd_funkier_rec_query_test( fd_funkier_rec_query_t * query );
181 :
182 : /* fd_funkier_rec_query_try_global is the same as fd_funkier_rec_query_try but will
183 : query txn's ancestors for key from youngest to oldest if key is not
184 : part of txn. As such, the txn of the returned record may not match
185 : txn but will be the txn of most recent ancestor with the key
186 : otherwise. *txn_out is set to the transaction where the record was
187 : found.
188 :
189 : This is reasonably fast O(in_prep_ancestor_cnt).
190 :
191 : Important safety tip! This function can encounter records
192 : that have the ERASE flag set (i.e. are tombstones of erased
193 : records). fd_funkier_rec_query_try_global will return a NULL in this case
194 : but still set *txn_out to the relevant transaction. This behavior
195 : differs from fd_funkier_rec_query_try. */
196 : fd_funkier_rec_t const *
197 : fd_funkier_rec_query_try_global( fd_funkier_t * funk,
198 : fd_funkier_txn_t const * txn,
199 : fd_funkier_rec_key_t const * key,
200 : fd_funkier_txn_t const ** txn_out,
201 : fd_funkier_rec_query_t * query );
202 :
203 : /* fd_funkier_rec_{pair,xid,key} returns a pointer in the local address
204 : space of the {(transaction id,record key) pair,transaction id,record
205 : key} of a live record. Assumes rec points to a live record in the
206 : caller's address space. The lifetime of the returned pointer is the
207 : same as rec. The value at the pointer will be constant for its
208 : lifetime. */
209 :
210 0 : FD_FN_CONST static inline fd_funkier_xid_key_pair_t const * fd_funkier_rec_pair( fd_funkier_rec_t const * rec ) { return &rec->pair; }
211 0 : FD_FN_CONST static inline fd_funkier_txn_xid_t const * fd_funkier_rec_xid ( fd_funkier_rec_t const * rec ) { return rec->pair.xid; }
212 0 : FD_FN_CONST static inline fd_funkier_rec_key_t const * fd_funkier_rec_key ( fd_funkier_rec_t const * rec ) { return rec->pair.key; }
213 :
214 : /* fd_funkier_rec_prepare prepares to insert a new record. This call just
215 : allocates a record from the pool and initializes it.
216 : The application should then fill in the new
217 : value. fd_funkier_rec_publish actually does the map insert and
218 : should be called once the value is correct. */
219 :
220 : fd_funkier_rec_t *
221 : fd_funkier_rec_prepare( fd_funkier_t * funk,
222 : fd_funkier_txn_t * txn,
223 : fd_funkier_rec_key_t const * key,
224 : fd_funkier_rec_prepare_t * prepare,
225 : int * opt_err );
226 :
227 : /* fd_funkier_rec_publish inserts a prepared record into the record map. */
228 :
229 : void
230 : fd_funkier_rec_publish( fd_funkier_rec_prepare_t * prepare );
231 :
232 : /* fd_funkier_rec_cancel returns a prepared record to the pool without
233 : inserting it. */
234 :
235 : void
236 : fd_funkier_rec_cancel( fd_funkier_rec_prepare_t * prepare );
237 :
238 : /* fd_funkier_rec_clone copies a record from an ancestor transaction
239 : to create a new record in the given transaction. The record can be
240 : modified afterward and must then be published. */
241 :
242 : fd_funkier_rec_t *
243 : fd_funkier_rec_clone( fd_funkier_t * funk,
244 : fd_funkier_txn_t * txn,
245 : fd_funkier_rec_key_t const * key,
246 : fd_funkier_rec_prepare_t * prepare,
247 : int * opt_err );
248 :
249 : /* fd_funkier_rec_is_full returns true if no more records can be
250 : allocated. */
251 :
252 : int
253 : fd_funkier_rec_is_full( fd_funkier_t * funk );
254 :
255 : /* fd_funkier_rec_remove removes the live record with the
256 : given (xid,key) from funk. Returns FD_FUNKIER_SUCCESS (0) on
257 : success and a FD_FUNKIER_ERR_* (negative) on failure. Reasons for
258 : failure include:
259 :
260 : FD_FUNKIER_ERR_INVAL - bad inputs (NULL funk, NULL xid)
261 :
262 : FD_FUNKIER_ERR_KEY - the record did not appear to be a live record.
263 : Specifically, a record query of funk for rec's (xid,key) pair did
264 : not return rec.
265 :
266 : The record will cease to exist in that transaction and any of
267 : transaction's subsequently created descendants (again, assuming no
268 : subsequent insert of key). This type of remove can be done on a
269 : published record (assuming the last published transaction is
270 : unfrozen). A tombstone is left in funk to track removals as they
271 : are published or cancelled.
272 :
273 : Any information in an erased record is lost.
274 :
275 : This is a reasonably fast O(1) and fortified against memory
276 : corruption. */
277 :
278 : int
279 : fd_funkier_rec_remove( fd_funkier_t * funk,
280 : fd_funkier_txn_t * txn,
281 : fd_funkier_rec_key_t const * key,
282 : fd_funkier_rec_t ** rec_out,
283 : ulong erase_data );
284 :
285 :
286 : /* When a record is erased there is metadata stored in the five most
287 : significant bytes of record flags. These are helpers to make setting
288 : and getting these values simple. The caller is responsible for doing
289 : a check on the flag of the record before using the value of the erase
290 : data. The 5 least significant bytes of the erase data parameter will
291 : be used and set into the erase flag. */
292 :
293 : void
294 : fd_funkier_rec_set_erase_data( fd_funkier_rec_t * rec, ulong erase_data );
295 :
296 : ulong
297 : fd_funkier_rec_get_erase_data( fd_funkier_rec_t const * rec );
298 :
299 : /* Iterator which walks all records in all transactions. Usage is:
300 :
301 : fd_funkier_all_iter_t iter[1];
302 : for( fd_funkier_all_iter_new( funk, iter ); !fd_funkier_all_iter_done( iter ); fd_funkier_all_iter_next( iter ) ) {
303 : fd_funkier_rec_t const * rec = fd_funkier_all_iter_ele_const( iter );
304 : ...
305 : }
306 : */
307 :
308 : struct fd_funkier_all_iter {
309 : fd_funkier_rec_map_t rec_map;
310 : ulong chain_cnt;
311 : ulong chain_idx;
312 : fd_funkier_rec_map_iter_t rec_map_iter;
313 : };
314 :
315 : typedef struct fd_funkier_all_iter fd_funkier_all_iter_t;
316 :
317 : void fd_funkier_all_iter_new( fd_funkier_t * funk, fd_funkier_all_iter_t * iter );
318 :
319 : int fd_funkier_all_iter_done( fd_funkier_all_iter_t * iter );
320 :
321 : void fd_funkier_all_iter_next( fd_funkier_all_iter_t * iter );
322 :
323 : fd_funkier_rec_t const * fd_funkier_all_iter_ele_const( fd_funkier_all_iter_t * iter );
324 :
325 : /* Misc */
326 :
327 : #ifdef FD_FUNKIER_HANDHOLDING
328 : /* fd_funkier_rec_verify verifies the record map. Returns FD_FUNKIER_SUCCESS
329 : if the record map appears intact and FD_FUNKIER_ERR_INVAL if not (logs
330 : details). Meant to be called as part of fd_funkier_verify. As such, it
331 : assumes funk is non-NULL, fd_funkier_{wksp,txn_map,rec_map} have been
332 : verified to work and the txn_map has been verified. */
333 :
334 : int
335 : fd_funkier_rec_verify( fd_funkier_t * funk );
336 : #endif
337 :
338 : FD_PROTOTYPES_END
339 :
340 : #endif /* HEADER_fd_src_funk_fd_funkier_rec_h */
|
