Line data Source code
1 : #ifndef HEADER_fd_src_discof_repair_fd_store_h
2 : #define HEADER_fd_src_discof_repair_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 :
148 : /* FD_STORE_USE_HANDHOLDING: Define this to non-zero at compile time
149 : to turn on additional runtime checks and logging. */
150 :
151 : #ifndef FD_STORE_USE_HANDHOLDING
152 : #define FD_STORE_USE_HANDHOLDING 1
153 : #endif
154 :
155 : /* FD_STORE_ALIGN specifies the alignment needed for store. ALIGN is
156 : double x86 cache line to mitigate various kinds of false sharing (eg.
157 : ACLPF adjacent cache line prefetch). */
158 :
159 : #define FD_STORE_ALIGN (128UL)
160 :
161 : /* FD_STORE_MAGIC is a magic number for detecting store corruption. */
162 :
163 9 : #define FD_STORE_MAGIC (0xf17eda2ce75702e0UL) /* firedancer store version 0 */
164 :
165 : /* FD_STORE_DATA_MAX defines a constant for the maximum size of a FEC
166 : set payload. The value is computed from the maximum number
167 : of shreds in a FEC set * the payload bytes per shred.
168 :
169 : 67 shreds per FEC set * 955 payloads per shred = 63985 bytes max. */
170 :
171 0 : #define FD_STORE_DATA_MAX (63985UL) /* TODO fixed-32 */
172 :
173 : /* fd_store_fec describes a store element (FEC set). The pointer fields
174 : implement a left-child, right-sibling n-ary tree. */
175 :
176 : struct __attribute__((packed)) fd_store_key {
177 : fd_hash_t mr;
178 : ulong part; /* partition index of the inserter */
179 : };
180 : typedef struct fd_store_key fd_store_key_t;
181 :
182 : struct __attribute__((aligned(FD_STORE_ALIGN))) fd_store_fec {
183 :
184 : /* Keys */
185 :
186 : fd_store_key_t key; /* map key, merkle root of the FEC set + a partition index */
187 : fd_hash_t cmr; /* parent's map key, chained merkle root of the FEC set */
188 :
189 : /* Pointers */
190 :
191 : ulong next; /* reserved for internal use by fd_pool, fd_map_chain */
192 : ulong parent; /* pool idx of the parent */
193 : ulong child; /* pool idx of the left-child */
194 : ulong sibling; /* pool idx of the right-sibling */
195 :
196 : /* Data */
197 :
198 : ulong data_sz; /* TODO fixed-32. sz of the FEC set payload, guaranteed < FD_STORE_DATA_MAX */
199 : uchar data[FD_STORE_DATA_MAX]; /* FEC set payload = coalesced data shreds (byte array) */
200 : };
201 : typedef struct fd_store_fec fd_store_fec_t;
202 :
203 : #define POOL_NAME fd_store_pool
204 507 : #define POOL_ELE_T fd_store_fec_t
205 : #include "../../util/tmpl/fd_pool_para.c"
206 :
207 : #define MAP_NAME fd_store_map
208 : #define MAP_ELE_T fd_store_fec_t
209 : #define MAP_KEY_T fd_store_key_t
210 51 : #define MAP_KEY key
211 540 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_hash_t)))
212 477 : #define MAP_KEY_HASH(key,seed) ((ulong)key->mr.ul[0]%seed + (key)->part*seed) /* See documentation above for the hash function */
213 : #define MAP_INSERT_FENCE 1
214 : #include "../../util/tmpl/fd_map_chain.c"
215 :
216 : struct fd_store {
217 : ulong magic; /* ==FD_STORE_MAGIC */
218 : ulong fec_max; /* max number of FEC sets that can be stored */
219 : ulong part_cnt; /* number of partitions, also the number of writers */
220 : ulong root; /* pool idx of the root */
221 : ulong slot0; /* FIXME this hack is needed until the block_id is in the bank (manifest) */
222 : ulong store_gaddr; /* wksp gaddr of store in the backing wksp, non-zero gaddr */
223 : ulong map_gaddr; /* wksp gaddr of map of fd_store_key->fd_store_fec */
224 : ulong pool_mem_gaddr; /* wksp gaddr of shmem_t object in pool_para */
225 : ulong pool_ele_gaddr; /* wksp gaddr of first ele_t object in pool_para */
226 : fd_rwlock_t lock; /* rwlock for concurrent access */
227 : };
228 : typedef struct fd_store fd_store_t;
229 :
230 : FD_PROTOTYPES_BEGIN
231 :
232 : /* Constructors */
233 :
234 : /* fd_store_{align,footprint} return the required alignment and
235 : footprint of a memory region suitable for use as store with up to
236 : fec_max elements. fec_max is an integer power-of-two. */
237 :
238 : FD_FN_CONST static inline ulong
239 111 : fd_store_align( void ) {
240 111 : return alignof(fd_store_t);
241 111 : }
242 :
243 : FD_FN_CONST static inline ulong
244 21 : fd_store_footprint( ulong fec_max ) {
245 21 : if( FD_UNLIKELY( !fd_ulong_is_pow2( fec_max ) ) ) return 0UL;
246 21 : return FD_LAYOUT_FINI(
247 21 : FD_LAYOUT_APPEND(
248 21 : FD_LAYOUT_APPEND(
249 21 : FD_LAYOUT_APPEND(
250 21 : FD_LAYOUT_APPEND(
251 21 : FD_LAYOUT_INIT,
252 21 : alignof(fd_store_t), sizeof(fd_store_t) ),
253 21 : fd_store_map_align(), fd_store_map_footprint( fec_max ) ),
254 21 : fd_store_pool_align(), fd_store_pool_footprint() ),
255 21 : alignof(fd_store_fec_t), sizeof(fd_store_fec_t)*fec_max ),
256 21 : fd_store_align() );
257 21 : }
258 :
259 : /* fd_store_new formats an unused memory region for use as a store.
260 : mem is a non-NULL pointer to this region in the local address space
261 : with the required footprint and alignment. fec_max is an integer
262 : power-of-two. */
263 :
264 : void *
265 : fd_store_new( void * shmem, ulong fec_max, ulong part_cnt );
266 :
267 : /* fd_store_join joins the caller to the store. store points to the
268 : first byte of the memory region backing the store in the caller's
269 : address space.
270 :
271 : Returns a pointer in the local address space to store on success. */
272 :
273 : fd_store_t *
274 : fd_store_join( void * store );
275 :
276 : /* fd_store_leave leaves a current local join. Returns a pointer to the
277 : underlying shared memory region on success and NULL on failure (logs
278 : details). Reasons for failure include store is NULL. */
279 :
280 : void *
281 : fd_store_leave( fd_store_t const * store );
282 :
283 : /* fd_store_delete unformats a memory region used as a store.
284 : Assumes only the nobody is joined to the region. Returns a
285 : pointer to the underlying shared memory region or NULL if used
286 : obviously in error (e.g. store is obviously not a store ... logs
287 : details). The ownership of the memory region is transferred to the
288 : caller. */
289 :
290 : void *
291 : fd_store_delete( void * shstore );
292 :
293 : /* Accessors */
294 :
295 : /* fd_store_wksp returns the local join to the wksp backing the store.
296 : The lifetime of the returned pointer is at least as long as the
297 : lifetime of the local join. Assumes store is a current local
298 : join. */
299 :
300 : FD_FN_PURE static inline fd_wksp_t *
301 1734 : fd_store_wksp( fd_store_t const * store ) {
302 1734 : return (fd_wksp_t *)( ( (ulong)store ) - store->store_gaddr );
303 1734 : }
304 :
305 : /* fd_store_pool returns a local join to the pool_t object of the store. */
306 666 : FD_FN_PURE static inline fd_store_pool_t fd_store_pool_const( fd_store_t const * store ) {
307 666 : return (fd_store_pool_t){ .pool = fd_wksp_laddr_fast( fd_store_wksp( store ), store->pool_mem_gaddr ),
308 666 : .ele = fd_wksp_laddr_fast( fd_store_wksp( store ), store->pool_ele_gaddr ),
309 666 : .ele_max = store->fec_max };
310 666 : }
311 :
312 : /* fd_store_{map,map_const,pool,fec0,fec0_const,root,root_const} returns a pointer in the
313 : caller's address space to the corresponding store field. const
314 : versions for each are also provided. */
315 :
316 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 ); }
317 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 ); }
318 384 : FD_FN_PURE static inline fd_store_pool_t fd_store_pool ( fd_store_t * store ) { return fd_store_pool_const( store ); }
319 :
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_const( 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_const( 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_const( 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_const( 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_const( store ); return fd_store_pool_ele_const( &pool, fec->sibling ); }
337 :
338 : /* fd_store_{shacq, shrel, exacq, exrel} acquires / releases the
339 : shared / 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 : FD_FN_PURE static inline void fd_store_shacq( fd_store_t * store ) { fd_rwlock_read ( &store->lock ); }
344 0 : FD_FN_PURE static inline void fd_store_shrel( fd_store_t * store ) { fd_rwlock_unread ( &store->lock ); }
345 0 : FD_FN_PURE static inline void fd_store_exacq( fd_store_t * store ) { fd_rwlock_write ( &store->lock ); }
346 0 : FD_FN_PURE 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 : /* fd_store_{query,query_const} queries the FEC set keyed by merkle.
381 : Returns a pointer to the fd_store_fec_t if found, NULL otherwise.
382 :
383 : Both the const and non-const versions are concurrency safe; as in
384 : they avoid using the non-const map_ele_query that reorders the chain.
385 : fd_store_query gets around this by calling map idx_query_const, which
386 : does not reorder the chain, and then indexes directly into the pool
387 : and returns a non-const pointer to the element of interest.
388 :
389 : Assumes caller has acquired the shared lock via fd_store_shacq.
390 :
391 : IMPORTANT SAFETY TIP! Caller should only call fd_store_shrel when
392 : they no longer retain interest in the returned pointer. */
393 :
394 : FD_FN_PURE static inline fd_store_fec_t *
395 93 : fd_store_query( fd_store_t * store, fd_hash_t const * merkle_root ) {
396 93 : fd_store_key_t key = { .mr = *merkle_root, .part = UINT_MAX };
397 93 : fd_store_pool_t pool = fd_store_pool( store );
398 102 : for( uint i = 0; i < store->part_cnt; i++ ) {
399 102 : key.part = i;
400 102 : ulong idx = fd_store_map_idx_query_const( fd_store_map( store ), &key, ULONG_MAX, fd_store_fec0( store ) );
401 102 : if( idx != ULONG_MAX ) return fd_store_pool_ele( &pool, idx );
402 102 : }
403 0 : return NULL;
404 93 : }
405 :
406 : FD_FN_PURE static inline fd_store_fec_t const *
407 177 : fd_store_query_const( fd_store_t const * store, fd_hash_t * merkle_root ) {
408 177 : fd_store_key_t key = { .mr = *merkle_root, .part = UINT_MAX };
409 285 : for( uint i = 0; i < store->part_cnt; i++ ) {
410 234 : key.part = i;
411 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 ) );
412 234 : if( fec ) return fec;
413 234 : }
414 51 : return NULL;
415 177 : }
416 :
417 : /* Operations */
418 :
419 : /* fd_store_insert inserts a new FEC set keyed by merkle. Returns the
420 : newly inserted fd_store_fec_t. Each fd_store_fec_t can hold at most
421 : FD_STORE_DATA_MAX bytes of data, and caller is responsible for
422 : copying into the region.
423 :
424 : Assumes store is a current local join and has space for another
425 : element. Does additional checks when handholding is enabled and
426 : fails insertion (returning NULL) if checks fail. If this is the
427 : first element being inserted into store, the store root will be set
428 : to this newly inserted element.
429 :
430 : Assumes caller has acquired either the shared or exclusive lock via
431 : fd_store_shacq or fd_store_exacq. See top-level documentation for
432 : why this operation may only require a shared lock vs. exclusive.
433 :
434 : IMPORTANT SAFETY TIP! Caller should only call fd_store_shrel or
435 : fd_store_exrel when they no longer retain interest in the returned
436 : pointer. */
437 :
438 : fd_store_fec_t *
439 : fd_store_insert( fd_store_t * store,
440 : ulong part_idx,
441 : fd_hash_t * merkle_root );
442 :
443 : /* fd_store_link queries for and links the child keyed by merkle_root to
444 : parent keyed by chained_merkle_root. Returns a pointer to the child.
445 : Assumes merkle_root and chained_merkle_root are both non-NULL and key
446 : elements currently in the store.
447 :
448 : Assumes caller has acquired the shared lock via fd_store_shacq.
449 :
450 : IMPORTANT SAFETY TIP! Caller should only call fd_store_shrel when
451 : they no longer retain interest in the returned pointer. */
452 :
453 : fd_store_fec_t *
454 : fd_store_link( fd_store_t * store,
455 : fd_hash_t * merkle_root,
456 : fd_hash_t * chained_merkle_root );
457 :
458 : /* fd_store_publish publishes merkle_root as the new store root, pruning
459 : all elements across branches that do not descend from the new root.
460 : Returns a pointer to the new root. Assumes merkle_root is in the
461 : store and connected to the root (if handholding is enabled does
462 : additional checks and returns NULL on error). Note pruning can
463 : result in store elements greater than the new root slot being
464 : removed. These are elements that become orphaned as a result of the
465 : common ancestor with the new root being removed (the entire branch
466 : ie. fork is pruned).
467 :
468 : For example, in the tree (preorder) [0 1 2 4 3 5 6] publishing 2 will
469 : result in [0 1] being removed given they are ancestors of 2, and
470 : removing 1 will leave [3 5 6] orphaned and also removed.
471 :
472 : Assumes caller has acquired the exclusive lock via fd_store_exacq.
473 :
474 : IMPORTANT SAFETY TIP! Caller should only call fd_store_exrel when
475 : they no longer retain interest in the returned pointer. */
476 :
477 : fd_store_fec_t *
478 : fd_store_publish( fd_store_t * store,
479 : fd_hash_t const * merkle_root );
480 :
481 : /* fd_store_clear clears the store. All elements are removed from the
482 : map and released back into the pool. Does not zero-out fields.
483 :
484 : IMPORTANT SAFETY TIP! the store must be non-empty. */
485 :
486 : fd_store_t *
487 : fd_store_clear( fd_store_t * store );
488 :
489 : /* TODO fd_store_verify */
490 :
491 : /* fd_store_print pretty-prints a formatted store as a tree structure.
492 : Printing begins from the store root and each node is the FEC set key
493 : (merkle root hash). */
494 :
495 : int
496 : fd_store_verify( fd_store_t * store );
497 :
498 : void
499 : fd_store_print( fd_store_t const * store );
500 :
501 : FD_PROTOTYPES_END
502 :
503 : #endif /* HEADER_fd_src_discof_repair_fd_store_h */
|
