Line data Source code
1 : #ifndef HEADER_fd_src_disco_store_fd_store_h
2 : #define HEADER_fd_src_disco_store_fd_store_h
3 :
4 : /* fd_store is a high-performance in-memory storage engine for shreds as
5 : they are received from the network.
6 :
7 : The elements in the store themselves are not shreds, but FEC set
8 : payloads. Briefly, FEC sets are groupings of shreds that encode the
9 : same data but provide redundancy and security. While Firedancer
10 : receives individual shreds over Turbine / Repair (the relevant Solana
11 : protocols), a lot of Firedancer's validation of those shreds can only
12 : be done at the FEC set boundary. Also, there are potential future
13 : protocol changes to encode all shreds in a FEC set so that they can
14 : only be decoded once the entire FEC set is received ("all-coding").
15 :
16 : Therefore, the FEC set becomes the logical unit for the store vs.
17 : individual shreds. Replay will only ever attempt replay of a FEC set
18 : so there is no need to store at the granularity of individual shreds.
19 : The store is essentially a mapping of merkle root->FEC set payload,
20 : in which the merkle root was produced by feeding every shred in a FEC
21 : set into a merkle tree. This uniquely identifies a FEC set, because
22 : if any of the shreds change, the merkle root changes.
23 :
24 : Shreds are coalesced and inserted into the store as bytes. The max
25 : bytes per FEC set is currently variable-length but capped at 63985.
26 : In the future this will be fixed to 31840 bytes, when FEC sets are
27 : enforced to always be 32 shreds.
28 :
29 : The shared memory used by a store instance is within a workspace such
30 : that it is also persistent and remotely inspectable. Store is
31 : designed to be used inter-process (allowing concurrent joins from
32 : multiple tiles), relocated in memory (via wksp operations), and
33 : accessed concurrently (managing conflicts with a lock).
34 :
35 : EQUIVOCATION
36 :
37 : There is a protocol violation called equivocation (also known as
38 : "duplicates") that results in two or more blocks for the same slot.
39 : The actual conflict occurs at the shred level: a leader produces two
40 : or more shreds for the same slot at the same index, with different
41 : data payloads. The result will be two different FEC sets for the
42 : same "logical" FEC set based on (slot, fec_set_idx).
43 :
44 : Unfortunately a naive keying scheme such as (slot, fec_set_idx) is
45 : insufficient as a result of equivocation. As mentioned earlier,
46 : Store instead uses the merkle root as the key for its FEC set
47 : elements, at the cost of some keying performance and complexity.
48 :
49 : ARCHITECTURE
50 :
51 : In the Firedancer topology, Shred tile writes to store and Replay
52 : tile reads from store. Replay tile only reads from the store after
53 : Repair tile (which is downstream of Shred) has notified Replay that a
54 : FEC set is ready. Shred's writes are append-only and Replay is
55 : responsible for publishing once it is done consuming (signaled by a
56 : new Tower root).
57 :
58 : Shred (writes) -> Repair (notif) -> Replay (reads, publishes)
59 :
60 : ORDERING
61 :
62 : In the above architecture, Repair delivers FEC sets to Replay in
63 : partial order. Any given fork will be delivered in-order, but
64 : concurrent forks can be delivered in arbitrary order. Another way to
65 : phrase this is a parent FEC set will always be delivered before the
66 : child (see fd_reasm).
67 :
68 : CONCURRENCY
69 :
70 : It is possible to design Store access in a way that enables parallel
71 : writes and minimizes lock contention between readers and writers.
72 : Store contains a fd_rwlock (read-write lock), but the name is a bit
73 : of a misnomer because writes can actually be concurrent and the only
74 : operation that will actually need the write lock is publish, which
75 : will be done by Replay. It is more appropriate to describe as an
76 : exclusive-shared access lock.
77 :
78 : In this design, writers (Shred tiles) hold the shared lock during
79 : their access. The reader (Replay tile) also holds the shared lock
80 : during its access, and given both Shred and Replay will be taking out
81 : shared locks, they will not contend.
82 :
83 : For parallel writes, the Store's hash function is carefully designed
84 : to partition the keyspace so that the same Shred tile always writes
85 : to the same map slots. This ensures map collisions always happen on
86 : the same Shred tile and cannot happen across tiles. Specifically, if
87 : two different FEC sets hash to the same slot, it is guaranteed that
88 : to be the same Shred tile processing both those FEC sets. This
89 : prevents a data race in which multiple Shred tiles (each with a
90 : handle to the shared lock) write to the same map slot.
91 :
92 : The hash function is defined as follows:
93 : ```
94 : #define MAP_KEY_HASH(key,seed) ((ulong)key->mr.ul[0]%seed + (key)->part*seed)
95 : ```
96 : where `key` is a key type that includes the merkle root (32 bytes)
97 : and the partition index (8 bytes) that is equivalent to the Shred
98 : tile index doing the insertion. seed, on initialization, is the
99 : number of chains/buckets in the map_chain divided by the number of
100 : partitions. In effect, seed is the size of each partition. For
101 : example, if the map_chain is sized to 1024, and there are 4 shred
102 : tiles, then the seed is 1024/4 = 256. Then the map key hash can
103 : bound the chain index of each partition as such: shred tile 0 will
104 : write to chains 0-255, shred tile 1 will write to chains 256-511,
105 : shred tile 2 will write to chains 512-767, and shred tile 3 will
106 : write to chains 768-1023, without overlap. The merkle root is a 32
107 : byte SHA-256 hash, so we can expect a fairly uniform distribution of
108 : hash values even after truncating to the first 8 bytes, without
109 : needing to introduce more randomness. Thus we can repurpose the
110 : `seed` argument to be the number of partitions.
111 :
112 : Essentially, this allows for limited single-producer single-consumer
113 : (SPSC) concurrency, where the producer is a given Shred tile and the
114 : consumer is Replay tile. The SPSC concurrency is limited in that the
115 : Store should 1. only be read by Replay after Repair has notified
116 : Replay it is time to read (ie. Shred has finished writing), and 2. be
117 : written to by Shred(s) in append-only fashion, so Shred never
118 : modifies or removes from the map. Store is backed by fd_map_chain,
119 : which is not thread-safe generally, but does support this particular
120 : SPSC concurrency model in cases where the consumer is guaranteed to
121 : be lagging the producer.
122 :
123 : Analyzing fd_map_chain in gory detail, in the case of a map collision
124 : where Replay tile is reading an element and Shred tile writes a new
125 : element to the same map slot, that new element is prepended to the
126 : hash chain within that slot (which modifies what the head of the
127 : chain points to as well as the now-previous head in the hash chain's
128 : `.next` field, but does not touch application data). With fencing
129 : enabled (MAP_INSERT_FENCE), it is guaranteed the consumer either
130 : reads the head before or after the update. If it reads before, that
131 : is safe, it would just check the key (if no match, iterate down the
132 : chain etc.) If it reads after, it is also safe because the new
133 : element is guaranteed to be before the old element in the chain, so
134 : it would just do one more iteration. Note the consumer should always
135 : use fd_store_query_const to ensure the underlying fd_map_chain is not
136 : modified during querying.
137 :
138 : The exception to the above is publishing. Publishing requires
139 : exclusive access because it involves removing from fd_map_chain,
140 : which is not safe for shared access. So the Replay tile should take
141 : out the exclusive lock. Publishing happens at most once per slot, so
142 : it is a relatively infrequent Store access compared to FEC queries
143 : and inserts (which is good because it is also the most expensive). */
144 :
145 : #include "../../flamenco/fd_rwlock.h"
146 : #include "../../flamenco/types/fd_types_custom.h"
147 : #include "../../util/hist/fd_histf.h"
148 :
149 : /* FD_STORE_USE_HANDHOLDING: Define this to non-zero at compile time
150 : to turn on additional runtime checks and logging. */
151 :
152 : #ifndef FD_STORE_USE_HANDHOLDING
153 : #define FD_STORE_USE_HANDHOLDING 1
154 : #endif
155 :
156 : /* FD_STORE_ALIGN specifies the alignment needed for store. ALIGN is
157 : double x86 cache line to mitigate various kinds of false sharing (eg.
158 : ACLPF adjacent cache line prefetch). */
159 :
160 : #define FD_STORE_ALIGN (128UL)
161 :
162 : /* FD_STORE_MAGIC is a magic number for detecting store corruption. */
163 :
164 9 : #define FD_STORE_MAGIC (0xf17eda2ce75702e0UL) /* firedancer store version 0 */
165 :
166 : /* FD_STORE_DATA_MAX defines a constant for the maximum size of a FEC
167 : set payload. The value is computed from the maximum number
168 : of shreds in a FEC set * the payload bytes per shred.
169 :
170 : 67 shreds per FEC set * 955 payloads per shred = 63985 bytes max. */
171 :
172 0 : #define FD_STORE_DATA_MAX (63985UL) /* TODO fixed-32 */
173 :
174 : /* fd_store_fec describes a store element (FEC set). The pointer fields
175 : implement a left-child, right-sibling n-ary tree. */
176 :
177 : struct __attribute__((packed)) fd_store_key {
178 : fd_hash_t mr;
179 : ulong part; /* partition index of the inserter */
180 : };
181 : typedef struct fd_store_key fd_store_key_t;
182 :
183 : struct __attribute__((aligned(FD_STORE_ALIGN))) fd_store_fec {
184 :
185 : /* Keys */
186 :
187 : fd_store_key_t key; /* map key, merkle root of the FEC set + a partition index */
188 : fd_hash_t cmr; /* parent's map key, chained merkle root of the FEC set */
189 :
190 : /* Pointers. These are internal to the store and callers should not
191 : interface with them directly. */
192 :
193 : ulong next; /* reserved for internal use by fd_pool, fd_map_chain */
194 : ulong parent; /* pool idx of the parent */
195 : ulong child; /* pool idx of the left-child */
196 : ulong sibling; /* pool idx of the right-sibling */
197 :
198 : /* Data */
199 :
200 : ulong data_sz; /* TODO fixed-32. sz of the FEC set payload, guaranteed < FD_STORE_DATA_MAX */
201 : uchar data[FD_STORE_DATA_MAX]; /* FEC set payload = coalesced data shreds (byte array) */
202 : };
203 : typedef struct fd_store_fec fd_store_fec_t;
204 :
205 : #define POOL_NAME fd_store_pool
206 507 : #define POOL_ELE_T fd_store_fec_t
207 : #include "../../util/tmpl/fd_pool_para.c"
208 :
209 : #define MAP_NAME fd_store_map
210 : #define MAP_ELE_T fd_store_fec_t
211 : #define MAP_KEY_T fd_store_key_t
212 51 : #define MAP_KEY key
213 540 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_hash_t)))
214 477 : #define MAP_KEY_HASH(key,seed) ((ulong)key->mr.ul[0]%seed + (key)->part*seed) /* See documentation above for the hash function */
215 : #define MAP_INSERT_FENCE 1
216 : #include "../../util/tmpl/fd_map_chain.c"
217 :
218 : struct fd_store {
219 : ulong magic; /* ==FD_STORE_MAGIC */
220 : ulong fec_max; /* max number of FEC sets that can be stored */
221 : ulong part_cnt; /* number of partitions, also the number of writers */
222 : ulong root; /* pool idx of the root */
223 : ulong slot0; /* FIXME this hack is needed until the block_id is in the bank (manifest) */
224 : ulong store_gaddr; /* wksp gaddr of store in the backing wksp, non-zero gaddr */
225 : ulong map_gaddr; /* wksp gaddr of map of fd_store_key->fd_store_fec */
226 : ulong pool_mem_gaddr; /* wksp gaddr of shmem_t object in pool_para */
227 : ulong pool_ele_gaddr; /* wksp gaddr of first ele_t object in pool_para */
228 : fd_rwlock_t lock; /* rwlock for concurrent access */
229 : };
230 : typedef struct fd_store fd_store_t;
231 :
232 : FD_PROTOTYPES_BEGIN
233 :
234 : /* Constructors */
235 :
236 : /* fd_store_{align,footprint} return the required alignment and
237 : footprint of a memory region suitable for use as store with up to
238 : fec_max elements. fec_max is an integer power-of-two. */
239 :
240 : FD_FN_CONST static inline ulong
241 111 : fd_store_align( void ) {
242 111 : return alignof(fd_store_t);
243 111 : }
244 :
245 : FD_FN_CONST static inline ulong
246 21 : fd_store_footprint( ulong fec_max ) {
247 21 : if( FD_UNLIKELY( !fd_ulong_is_pow2( fec_max ) ) ) return 0UL;
248 21 : return FD_LAYOUT_FINI(
249 21 : FD_LAYOUT_APPEND(
250 21 : FD_LAYOUT_APPEND(
251 21 : FD_LAYOUT_APPEND(
252 21 : FD_LAYOUT_APPEND(
253 21 : FD_LAYOUT_INIT,
254 21 : alignof(fd_store_t), sizeof(fd_store_t) ),
255 21 : fd_store_map_align(), fd_store_map_footprint( fec_max ) ),
256 21 : fd_store_pool_align(), fd_store_pool_footprint() ),
257 21 : alignof(fd_store_fec_t), sizeof(fd_store_fec_t)*fec_max ),
258 21 : fd_store_align() );
259 21 : }
260 :
261 : /* fd_store_new formats an unused memory region for use as a store.
262 : mem is a non-NULL pointer to this region in the local address space
263 : with the required footprint and alignment. fec_max is an integer
264 : power-of-two. */
265 :
266 : void *
267 : fd_store_new( void * shmem, ulong fec_max, ulong part_cnt );
268 :
269 : /* fd_store_join joins the caller to the store. store points to the
270 : first byte of the memory region backing the store in the caller's
271 : address space.
272 :
273 : Returns a pointer in the local address space to store on success. */
274 :
275 : fd_store_t *
276 : fd_store_join( void * store );
277 :
278 : /* fd_store_leave leaves a current local join. Returns a pointer to the
279 : underlying shared memory region on success and NULL on failure (logs
280 : details). Reasons for failure include store is NULL. */
281 :
282 : void *
283 : fd_store_leave( fd_store_t const * store );
284 :
285 : /* fd_store_delete unformats a memory region used as a store.
286 : Assumes only the nobody is joined to the region. Returns a
287 : pointer to the underlying shared memory region or NULL if used
288 : obviously in error (e.g. store is obviously not a store ... logs
289 : details). The ownership of the memory region is transferred to the
290 : caller. */
291 :
292 : void *
293 : fd_store_delete( void * shstore );
294 :
295 : /* Accessors */
296 :
297 : /* fd_store_wksp returns the local join to the wksp backing the store.
298 : The lifetime of the returned pointer is at least as long as the
299 : lifetime of the local join. Assumes store is a current local
300 : join. */
301 :
302 : FD_FN_PURE static inline fd_wksp_t *
303 1734 : fd_store_wksp( fd_store_t const * store ) {
304 1734 : return (fd_wksp_t *)( ( (ulong)store ) - store->store_gaddr );
305 1734 : }
306 :
307 : /* fd_store_pool computes and returns a local join handle to the pool_para. */
308 666 : FD_FN_PURE static inline fd_store_pool_t fd_store_pool( fd_store_t const * store ) {
309 666 : return (fd_store_pool_t){ .pool = fd_wksp_laddr_fast( fd_store_wksp( store ), store->pool_mem_gaddr ),
310 666 : .ele = fd_wksp_laddr_fast( fd_store_wksp( store ), store->pool_ele_gaddr ),
311 666 : .ele_max = store->fec_max };
312 666 : }
313 :
314 : /* fd_store_{map,map_const,fec0,fec0_const,root,root_const} returns a
315 : pointer in the caller's address space to the corresponding store
316 : field. const versions for each are also provided. */
317 :
318 168 : FD_FN_PURE static inline fd_store_map_t * fd_store_map ( fd_store_t * store ) { return fd_wksp_laddr_fast( fd_store_wksp( store ), store->map_gaddr ); }
319 234 : FD_FN_PURE static inline fd_store_map_t const * fd_store_map_const ( fd_store_t const * store ) { return fd_wksp_laddr_fast( fd_store_wksp( store ), store->map_gaddr ); }
320 165 : FD_FN_PURE static inline fd_store_fec_t * fd_store_fec0 ( fd_store_t * store ) { fd_store_pool_t pool = fd_store_pool( store ); return pool.ele; }
321 234 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_fec0_const( fd_store_t const * store ) { fd_store_pool_t pool = fd_store_pool( store ); return pool.ele; }
322 15 : FD_FN_PURE static inline fd_store_fec_t * fd_store_root ( fd_store_t * store ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele ( &pool, store->root); }
323 3 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_root_const( fd_store_t const * store ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, store->root); }
324 :
325 : /* fd_store_{parent,child,sibling} returns a pointer in the caller's
326 : address space to the corresponding {parent,left-child,right-sibling}
327 : of fec. Assumes store is a current local join and fec is a valid
328 : pointer to a pool element inside store. const versions for each are
329 : also provided. */
330 :
331 0 : FD_FN_PURE static inline fd_store_fec_t * fd_store_parent ( fd_store_t * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele ( &pool, fec->parent ); }
332 0 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_parent_const ( fd_store_t const * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, fec->parent ); }
333 0 : FD_FN_PURE static inline fd_store_fec_t * fd_store_child ( fd_store_t * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele ( &pool, fec->child ); }
334 0 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_child_const ( fd_store_t const * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, fec->child ); }
335 0 : FD_FN_PURE static inline fd_store_fec_t * fd_store_sibling ( fd_store_t * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele ( &pool, fec->sibling ); }
336 0 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_sibling_const( fd_store_t const * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, fec->sibling ); }
337 :
338 : /* fd_store_{shacq, shrel, exacq, exrel} acquires / releases the shared
339 : / exclusive lock. Callers should typically use the
340 : FD_STORE_SHARED_LOCK and FD_STORE_EXCLUSIVE_LOCK macros to acquire
341 : and release the lock instead of calling these functions directly. */
342 :
343 0 : static inline void fd_store_shacq( fd_store_t * store ) { fd_rwlock_read ( &store->lock ); }
344 0 : static inline void fd_store_shrel( fd_store_t * store ) { fd_rwlock_unread ( &store->lock ); }
345 0 : static inline void fd_store_exacq( fd_store_t * store ) { fd_rwlock_write ( &store->lock ); }
346 0 : static inline void fd_store_exrel( fd_store_t * store ) { fd_rwlock_unwrite( &store->lock ); }
347 :
348 : struct fd_store_lock_ctx {
349 : fd_store_t * store_;
350 : long * acq_start;
351 : long * acq_end;
352 : long * work_end;
353 : };
354 :
355 : static inline void
356 0 : fd_store_shared_lock_cleanup( struct fd_store_lock_ctx * ctx ) { *(ctx->work_end) = fd_tickcount(); fd_store_shrel( ctx->store_ ); }
357 :
358 0 : #define FD_STORE_SHARED_LOCK(store, shacq_start, shacq_end, shrel_end) do { \
359 0 : struct fd_store_lock_ctx lock_ctx __attribute__((cleanup(fd_store_shared_lock_cleanup))) = \
360 0 : { .store_ = (store), .work_end = &(shrel_end), .acq_start = &(shacq_start), .acq_end = &(shacq_end) }; \
361 0 : shacq_start = fd_tickcount(); \
362 0 : fd_store_shacq( lock_ctx.store_ ); \
363 0 : shacq_end = fd_tickcount(); \
364 0 : do
365 :
366 0 : #define FD_STORE_SHARED_LOCK_END while(0); } while(0)
367 :
368 : static inline void
369 0 : fd_store_exclusive_lock_cleanup( struct fd_store_lock_ctx * ctx ) { *(ctx->work_end) = fd_tickcount(); fd_store_exrel( ctx->store_ ); }
370 :
371 0 : #define FD_STORE_EXCLUSIVE_LOCK(store, exacq_start, exacq_end, exrel_end) do { \
372 0 : struct fd_store_lock_ctx lock_ctx __attribute__((cleanup(fd_store_exclusive_lock_cleanup))) = \
373 0 : { .store_ = (store), .work_end = &(exrel_end), .acq_start = &(exacq_start), .acq_end = &(exacq_end) }; \
374 0 : exacq_start = fd_tickcount(); \
375 0 : fd_store_exacq( lock_ctx.store_ ); \
376 0 : exacq_end = fd_tickcount(); \
377 0 : do
378 0 : #define FD_STORE_EXCLUSIVE_LOCK_END while(0); } while(0)
379 :
380 : struct fd_store_histf {
381 : fd_histf_t * histf;
382 : long ts;
383 : };
384 : typedef struct fd_store_histf fd_store_histf_t;
385 :
386 : static inline void
387 0 : fd_store_histf( fd_store_histf_t * ctx ) {
388 0 : fd_histf_sample( ctx->histf, (ulong)fd_long_max( fd_tickcount() - ctx->ts, 0UL ) );
389 0 : }
390 :
391 : #define FD_STORE_HISTF_BEGIN(metric) do { \
392 : fd_store_histf_t _ctx __attribute__((cleanup(fd_store_histf))) = { .histf = (metric), .ts = fd_tickcount() }; \
393 : do
394 :
395 : #define FD_STORE_HISTF_END while(0); } while(0)
396 :
397 : /* fd_store_{query,query_const} queries the FEC set keyed by merkle.
398 : Returns a pointer to the fd_store_fec_t if found, NULL otherwise.
399 :
400 : Both the const and non-const versions are concurrency safe; as in
401 : they avoid using the non-const map_ele_query that reorders the chain.
402 : fd_store_query gets around this by calling map idx_query_const, which
403 : does not reorder the chain, and then indexes directly into the pool
404 : and returns a non-const pointer to the element of interest.
405 :
406 : Assumes caller has acquired the shared lock via fd_store_shacq.
407 :
408 : IMPORTANT SAFETY TIP! Caller should only call fd_store_shrel when
409 : they no longer retain interest in the returned pointer. */
410 :
411 : FD_FN_PURE static inline fd_store_fec_t *
412 93 : fd_store_query( fd_store_t * store, fd_hash_t const * merkle_root ) {
413 93 : fd_store_key_t key = { .mr = *merkle_root, .part = UINT_MAX };
414 93 : fd_store_pool_t pool = fd_store_pool( store );
415 102 : for( uint i = 0; i < store->part_cnt; i++ ) {
416 102 : key.part = i;
417 102 : ulong idx = fd_store_map_idx_query_const( fd_store_map( store ), &key, ULONG_MAX, fd_store_fec0( store ) );
418 102 : if( idx != ULONG_MAX ) return fd_store_pool_ele( &pool, idx );
419 102 : }
420 0 : return NULL;
421 93 : }
422 :
423 : FD_FN_PURE static inline fd_store_fec_t const *
424 177 : fd_store_query_const( fd_store_t const * store, fd_hash_t * merkle_root ) {
425 177 : fd_store_key_t key = { .mr = *merkle_root, .part = UINT_MAX };
426 285 : for( uint i = 0; i < store->part_cnt; i++ ) {
427 234 : key.part = i;
428 234 : fd_store_fec_t const * fec = fd_store_map_ele_query_const( fd_store_map_const( store ), &key, NULL, fd_store_fec0_const( store ) );
429 234 : if( fec ) return fec;
430 234 : }
431 51 : return NULL;
432 177 : }
433 :
434 : /* Operations */
435 :
436 : /* fd_store_insert inserts a new FEC set keyed by merkle. Returns the
437 : newly inserted fd_store_fec_t. Each fd_store_fec_t can hold at most
438 : FD_STORE_DATA_MAX bytes of data, and caller is responsible for
439 : copying into the region.
440 :
441 : Assumes store is a current local join and has space for another
442 : element. Does additional checks when handholding is enabled and
443 : fails insertion (returning NULL) if checks fail. If this is the
444 : first element being inserted into store, the store root will be set
445 : to this newly inserted element.
446 :
447 : Assumes caller has acquired either the shared or exclusive lock via
448 : fd_store_shacq or fd_store_exacq. See top-level documentation for
449 : why this operation may only require a shared lock vs. exclusive.
450 :
451 : IMPORTANT SAFETY TIP! Caller should only call fd_store_shrel or
452 : fd_store_exrel when they no longer retain interest in the returned
453 : pointer. */
454 :
455 : fd_store_fec_t *
456 : fd_store_insert( fd_store_t * store,
457 : ulong part_idx,
458 : fd_hash_t * merkle_root );
459 :
460 : /* fd_store_link queries for and links the child keyed by merkle_root to
461 : parent keyed by chained_merkle_root. Returns a pointer to the child.
462 : Assumes merkle_root and chained_merkle_root are both non-NULL and key
463 : elements currently in the store.
464 :
465 : Assumes caller has acquired the shared lock via fd_store_shacq.
466 :
467 : IMPORTANT SAFETY TIP! Caller should only call fd_store_shrel when
468 : they no longer retain interest in the returned pointer. */
469 :
470 : fd_store_fec_t *
471 : fd_store_link( fd_store_t * store,
472 : fd_hash_t * merkle_root,
473 : fd_hash_t * chained_merkle_root );
474 :
475 : /* fd_store_publish publishes merkle_root as the new store root, pruning
476 : all elements across branches that do not descend from the new root.
477 : Returns a pointer to the new root. Assumes merkle_root is in the
478 : store and connected to the root (if handholding is enabled does
479 : additional checks and returns NULL on error). Note pruning can
480 : result in store elements greater than the new root slot being
481 : removed. These are elements that become orphaned as a result of the
482 : common ancestor with the new root being removed (the entire branch
483 : ie. fork is pruned).
484 :
485 : For example, in the tree (preorder) [0 1 2 4 3 5 6] publishing 2 will
486 : result in [0 1] being removed given they are ancestors of 2, and
487 : removing 1 will leave [3 5 6] orphaned and also removed.
488 :
489 : Assumes caller has acquired the exclusive lock via fd_store_exacq.
490 :
491 : IMPORTANT SAFETY TIP! Caller should only call fd_store_exrel when
492 : they no longer retain interest in the returned pointer. */
493 :
494 : fd_store_fec_t *
495 : fd_store_publish( fd_store_t * store,
496 : fd_hash_t const * merkle_root );
497 :
498 : /* fd_store_clear clears the store. All elements are removed from the
499 : map and released back into the pool. Does not zero-out fields.
500 :
501 : IMPORTANT SAFETY TIP! the store must be non-empty. */
502 :
503 : fd_store_t *
504 : fd_store_clear( fd_store_t * store );
505 :
506 : /* TODO fd_store_verify */
507 :
508 : /* fd_store_print pretty-prints a formatted store as a tree structure.
509 : Printing begins from the store root and each node is the FEC set key
510 : (merkle root hash). */
511 :
512 : int
513 : fd_store_verify( fd_store_t * store );
514 :
515 : void
516 : fd_store_print( fd_store_t const * store );
517 :
518 : FD_PROTOTYPES_END
519 :
520 : #endif /* HEADER_fd_src_disco_store_fd_store_h */
|
