Line data Source code
1 : #ifndef HEADER_fd_src_choreo_ghost_fd_ghost_h
2 : #define HEADER_fd_src_choreo_ghost_fd_ghost_h
3 :
4 : /* fd_ghost implements Solana's LMD-GHOST ("latest message-driven greedy
5 : heaviest-observed subtree") fork choice rule.
6 :
7 : Protocol details:
8 :
9 : - LMD is an acronym for "latest message-driven". It describes how
10 : votes are counted when picking the best fork. In this scheme, only
11 : a validator's latest vote counts. So if a validator votes for slot
12 : 3 and then slot 5, the vote for 5 overwrites the vote for 3.
13 :
14 : - GHOST is an acronym for "greedy heaviest-observed subtree":
15 :
16 : greedy: for each depth of the tree, pick the locally optimal
17 : child / subtree / fork. This will result in the global
18 : optimal choice.
19 :
20 : heaviest: pick based on the highest stake weight.
21 :
22 : observed: this is the validator's local view, and other validators
23 : may have differing views because they've observed
24 : different votes.
25 :
26 : subtree: pick based on the weight of an entire subtree, not just
27 : an individual ele. For example, if slot 3 has 10 stake
28 : and slot 5 has 5 stake, but slot 5 has two children 6
29 : and 7 that each have 3 stake, our weights are
30 :
31 : slot 3 subtree [3] = 10
32 : slot 5 subtree [5, 6, 7] = 11 (5+3+3)
33 :
34 : Therefore slot 5 would be the heaviest.
35 :
36 : In-memory representation:
37 :
38 : There are two maps, both indexing the same pool of tree elements.
39 :
40 : - One map is keyed by slot number, and one map is keyed by hash_id
41 : (currently the block id, which is the merkle root of the last FEC
42 : set in the slot).
43 :
44 : - The elements in the slot map are a subset of the elements in the
45 : hash_id map.
46 :
47 : - Each tree ele tracks the amount of stake (`stake`) that has voted
48 : for its slot, as well as the recursive sum of stake for the subtree
49 : rooted at that ele (`weight`).
50 :
51 : The map keyed by slot is the "happy tree." i.e. the first version of
52 : a block we see and replay is going to be the version visible in the
53 : slot map. This is also the version of the slot that our tower is
54 : referring to. The map keyed by hash_id maintains every block that
55 : we've seen evidence of, including the equivocating blocks.
56 :
57 : both equivocating blocks seen only one block seen
58 :
59 : 0 0
60 : / \ /
61 : 1 1' (both invalid) 1' (valid)
62 : / \ /
63 : 2 3 3
64 :
65 : The first version of block 1 we see / replay is going to be the
66 : version visible in the slot map. Block 1' will be available in the
67 : hash-keyed tree, but not in the slot map. Block 3 will also be
68 : available in the slot-keyed tree, despite being a descendant of
69 : something not existing in the slot map.
70 :
71 : Thus in ghost,
72 :
73 : both equivocating blocks seen only one block seen
74 : slot_map: [0, 1, 2, 3] slot_map: [0, 1', 3]
75 : hash_map: [1'] hash_map: []
76 :
77 : Whatever is in the slot map is the slot referenced to by tower. Tower
78 : is *pure* and has no notion of duplicitness. So tower just needs to
79 : worry about querying ghost_slot_map for the proper hash_id.
80 :
81 : Slot 4 arrives, chained off of 1. In the right case where we didn't
82 : see block 1, block 4 now provides evidence for 1. We mark 1' as
83 : invalid for fork choice, and we repair the parent of 4 (getting 1').
84 : Then we replay down 1' and then replay down 4. Now the maps in this
85 : case look like:
86 :
87 : both equivocating blocks seen only one block seen
88 :
89 : 0 0
90 : / \ / \
91 : 1 1' (both invalid) 1' 1 (both invalid)
92 : / \ \ / \
93 : 2 4 3 3 4
94 :
95 : both equivocating blocks seen only one block seen
96 : slot_map: [0, 1, 2, 3, 4] slot_map: [0, 1', 3, 4]
97 : hash_map: [1'] hash_map: [1']
98 :
99 : Let's say 1' get's duplicate confirmed. Then the left case needs to
100 : switch forks in tower. Then ghost will need to itself swap the
101 : corresponding ghost hash_id in the slot_map to the hash_map and vice
102 : versa.
103 :
104 : both equivocating blocks seen only one block seen
105 : slot_map: [0, 1', 2, 3, 4] slot_map: [0, 1', 3, 4]
106 : hash_map: [1] hash_map: [1']
107 : (no change)
108 :
109 : 1' is marked as valid for fork choice. 1 remains invalid.
110 :
111 : Link to original GHOST paper: https://eprint.iacr.org/2013/881.pdf.
112 : This is simply a reference for those curious about the etymology, and
113 : not prerequisite reading for understanding this implementation. */
114 :
115 : #include "../fd_choreo_base.h"
116 : #include "../epoch/fd_epoch.h"
117 : #include "../../tango/fseq/fd_fseq.h"
118 :
119 : /* FD_GHOST_USE_HANDHOLDING: Define this to non-zero at compile time
120 : to turn on additional runtime checks. */
121 :
122 : #ifndef FD_GHOST_USE_HANDHOLDING
123 : #define FD_GHOST_USE_HANDHOLDING 1
124 : #endif
125 :
126 : /* fd_ghost_ele_t implements a left-child, right-sibling n-ary tree.
127 : Each ele maintains the `pool` index of its left-most child
128 : (`child_idx`), its immediate-right sibling (`sibling_idx`), and its
129 : parent (`parent_idx`).
130 :
131 : This tree structure is gaddr-safe and supports accesses and
132 : operations from processes with separate local ghost joins. */
133 :
134 : struct __attribute__((aligned(128UL))) fd_ghost_ele {
135 : fd_hash_t key; /* hash_id (merkle root of the last FEC set in the slot) */
136 : ulong slot; /* slot this ele is tracking */
137 : ulong next; /* reserved for internal use by fd_pool, hash_map fd_map_chain and fd_ghost_publish */
138 : ulong nexts; /* reserved for internal use by slot_map fd_map_chain */
139 : ulong eqvoc; /* pool idx of a duplicate of this slot */
140 : ulong parent; /* pool idx of the parent */
141 : ulong child; /* pool idx of the left-child */
142 : ulong sibling; /* pool idx of the right-sibling */
143 : ulong weight; /* total stake from replay votes for this slot or any of its descendants */
144 : ulong replay_stake; /* total stake from replay votes for this slot */
145 : ulong gossip_stake; /* total stake from gossip votes for this slot */
146 : ulong rooted_stake; /* replay stake that has rooted this slot */
147 : int valid; /* whether this ele is valid for fork choice */
148 : };
149 : typedef struct fd_ghost_ele fd_ghost_ele_t;
150 :
151 : #define POOL_NAME fd_ghost_pool
152 114 : #define POOL_T fd_ghost_ele_t
153 : #include "../../util/tmpl/fd_pool.c"
154 :
155 : #define MAP_NAME fd_ghost_hash_map
156 : #define MAP_ELE_T fd_ghost_ele_t
157 : #define MAP_KEY_T fd_hash_t
158 2112 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_hash_t)))
159 3225 : #define MAP_KEY_HASH(key,seed) (fd_hash((seed),(key),sizeof(fd_hash_t)))
160 1929 : #define MAP_NEXT next
161 : #include "../../util/tmpl/fd_map_chain.c"
162 :
163 : #define MAP_NAME fd_ghost_slot_map
164 : #define MAP_ELE_T fd_ghost_ele_t
165 321 : #define MAP_KEY slot
166 561 : #define MAP_NEXT nexts
167 : #include "../../util/tmpl/fd_map_chain.c"
168 :
169 : struct fd_dup_seen {
170 : ulong slot;
171 : };
172 : typedef struct fd_dup_seen fd_dup_seen_t;
173 :
174 : #define MAP_NAME fd_dup_seen_map
175 426 : #define MAP_T fd_dup_seen_t
176 1104 : #define MAP_KEY slot
177 : #define MAP_MEMOIZE 0
178 : #include "../../util/tmpl/fd_map_dynamic.c"
179 :
180 : /* fd_ghost_t is the top-level structure that holds the root of the
181 : tree, as well as the memory pools and map structures for tracking
182 : ghost eles and votes.
183 :
184 : These structures are bump-allocated and laid out contiguously in
185 : memory from the fd_ghost_t * pointer which points to the beginning of
186 : the memory region.
187 :
188 : ---------------------- <- fd_ghost_t *
189 : | metadata |
190 : ----------------------
191 : | pool |
192 : ----------------------
193 : | map |
194 : ----------------------
195 :
196 : A valid, initialized ghost is always non-empty. After
197 : `fd_ghost_init` the ghost will always have a root ele unless
198 : modified improperly out of ghost's API. */
199 :
200 57 : #define FD_GHOST_MAGIC (0xf17eda2ce7940570UL) /* firedancer ghost version 0 */
201 :
202 : struct __attribute__((aligned(128UL))) fd_ghost {
203 :
204 : /* Metadata */
205 :
206 : ulong magic; /* ==FD_GHOST_MAGIC */
207 : ulong ghost_gaddr; /* wksp gaddr of this in the backing wksp, non-zero gaddr */
208 : ulong seed; /* seed for various hashing function used under the hood, arbitrary */
209 : ulong root; /* pool idx of the root */
210 : ulong pool_gaddr; /* wksp gaddr of the pool backing this ghost, non-zero gaddr */
211 : ulong hash_map_gaddr; /* wksp gaddr of the map (for fast O(1) querying by hash) backing this ghost, non-zero gaddr */
212 : ulong slot_map_gaddr; /* wksp gaddr of the map (for fast O(1) querying by slot) backing this ghost, non-zero gaddr */
213 : ulong dup_map_gaddr; /* wksp gaddr of the map (for fast O(1) querying, non-zero gaddr */
214 : };
215 : typedef struct fd_ghost fd_ghost_t;
216 :
217 : FD_PROTOTYPES_BEGIN
218 :
219 : /* Constructors */
220 :
221 : /* fd_ghost_{align,footprint} return the required alignment and
222 : footprint of a memory region suitable for use as ghost with up to
223 : ele_max eles and vote_max votes. */
224 :
225 : FD_FN_CONST static inline ulong
226 735 : fd_ghost_align( void ) {
227 735 : return alignof(fd_ghost_t);
228 735 : }
229 :
230 : FD_FN_CONST static inline ulong
231 114 : fd_ghost_footprint( ulong ele_max ) {
232 114 : int lg_ele_max = fd_ulong_find_msb( fd_ulong_pow2_up( ele_max ) );
233 114 : return FD_LAYOUT_FINI(
234 114 : FD_LAYOUT_APPEND(
235 114 : FD_LAYOUT_APPEND(
236 114 : FD_LAYOUT_APPEND(
237 114 : FD_LAYOUT_APPEND(
238 114 : FD_LAYOUT_APPEND(
239 114 : FD_LAYOUT_INIT,
240 114 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
241 114 : fd_ghost_pool_align(), fd_ghost_pool_footprint ( ele_max ) ),
242 114 : fd_ghost_hash_map_align(), fd_ghost_hash_map_footprint( ele_max ) ),
243 114 : fd_ghost_slot_map_align(), fd_ghost_slot_map_footprint( ele_max ) ),
244 114 : fd_dup_seen_map_align(), fd_dup_seen_map_footprint ( lg_ele_max ) ),
245 114 : fd_ghost_align() );
246 114 : }
247 :
248 : /* fd_ghost_new formats an unused memory region for use as a ghost.
249 : mem is a non-NULL pointer to this region in the local address space
250 : with the required footprint and alignment. */
251 :
252 : void *
253 : fd_ghost_new( void * shmem, ulong ele_max, ulong seed );
254 :
255 : /* fd_ghost_join joins the caller to the ghost. ghost points to the
256 : first byte of the memory region backing the ghost in the caller's
257 : address space.
258 :
259 : Returns a pointer in the local address space to ghost on success. */
260 :
261 : fd_ghost_t *
262 : fd_ghost_join( void * ghost );
263 :
264 : /* fd_ghost_leave leaves a current local join. Returns a pointer to the
265 : underlying shared memory region on success and NULL on failure (logs
266 : details). Reasons for failure include ghost is NULL. */
267 :
268 : void *
269 : fd_ghost_leave( fd_ghost_t const * ghost );
270 :
271 : /* fd_ghost_delete unformats a memory region used as a ghost.
272 : Assumes only the nobody is joined to the region. Returns a
273 : pointer to the underlying shared memory region or NULL if used
274 : obviously in error (e.g. ghost is obviously not a ghost ... logs
275 : details). The ownership of the memory region is transferred to the
276 : caller. */
277 :
278 : void *
279 : fd_ghost_delete( void * ghost );
280 :
281 : /* fd_ghost_init initializes a ghost. Assumes ghost is a valid local
282 : join and no one else is joined. root is the initial root ghost will
283 : use. This is the snapshot slot if booting from a snapshot, 0 if the
284 : genesis slot. hash is the hash_id of the initial root.
285 :
286 : In general, this should be called by the same process that formatted
287 : ghost's memory, ie. the caller of fd_ghost_new. */
288 :
289 : void
290 : fd_ghost_init( fd_ghost_t * ghost, ulong root, fd_hash_t * hash );
291 :
292 : /* Accessors */
293 :
294 : /* fd_ghost_wksp returns the local join to the wksp backing the ghost.
295 : The lifetime of the returned pointer is at least as long as the
296 : lifetime of the local join. Assumes ghost is a current local
297 : join. */
298 :
299 : FD_FN_PURE static inline fd_wksp_t *
300 8199 : fd_ghost_wksp( fd_ghost_t const * ghost ) {
301 8199 : return (fd_wksp_t *)( ( (ulong)ghost ) - ghost->ghost_gaddr );
302 8199 : }
303 :
304 : /* fd_ghost_{pool,map,root} returns a pointer in the caller's address
305 : space to the corresponding ghost field. const versions for each are
306 : also provided. */
307 :
308 3555 : FD_FN_PURE static inline fd_ghost_ele_t * fd_ghost_pool ( fd_ghost_t * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->pool_gaddr ); }
309 1725 : FD_FN_PURE static inline fd_ghost_ele_t const * fd_ghost_pool_const ( fd_ghost_t const * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->pool_gaddr ); }
310 1653 : FD_FN_PURE static inline fd_ghost_hash_map_t * fd_ghost_hash_map ( fd_ghost_t * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->hash_map_gaddr ); }
311 462 : FD_FN_PURE static inline fd_ghost_hash_map_t const * fd_ghost_hash_map_const( fd_ghost_t const * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->hash_map_gaddr ); }
312 405 : FD_FN_PURE static inline fd_ghost_slot_map_t * fd_ghost_slot_map ( fd_ghost_t * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->slot_map_gaddr ); }
313 87 : FD_FN_PURE static inline fd_ghost_slot_map_t const * fd_ghost_slot_map_const( fd_ghost_t const * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->slot_map_gaddr ); }
314 312 : FD_FN_PURE static inline fd_dup_seen_t * fd_ghost_dup_map ( fd_ghost_t * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->dup_map_gaddr ); }
315 0 : FD_FN_PURE static inline fd_dup_seen_t const * fd_ghost_dup_map_const ( fd_ghost_t const * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->dup_map_gaddr ); }
316 :
317 : /* fd_ghost_{parent,child,sibling} returns a pointer in the caller's
318 : address space to the corresponding {parent,left-child,right-sibling}
319 : of fec. Assumes ghost is a current local join and fec is a valid
320 : pointer to a pool element inside ghost. const versions for each are
321 : also provided. */
322 :
323 756 : FD_FN_PURE static inline fd_ghost_ele_t * fd_ghost_root ( fd_ghost_t * ghost ) { return fd_ghost_pool_ele ( fd_ghost_pool ( ghost ), ghost->root ); }
324 114 : FD_FN_PURE static inline fd_ghost_ele_t const * fd_ghost_root_const ( fd_ghost_t const * ghost ) { return fd_ghost_pool_ele_const( fd_ghost_pool_const( ghost ), ghost->root ); }
325 540 : FD_FN_PURE static inline fd_ghost_ele_t * fd_ghost_parent ( fd_ghost_t * ghost, fd_ghost_ele_t * ele ) { return fd_ghost_pool_ele ( fd_ghost_pool ( ghost ), ele->parent ); }
326 45 : FD_FN_PURE static inline fd_ghost_ele_t const * fd_ghost_parent_const ( fd_ghost_t const * ghost, fd_ghost_ele_t const * ele ) { return fd_ghost_pool_ele_const( fd_ghost_pool_const( ghost ), ele->parent ); }
327 6 : FD_FN_PURE static inline fd_ghost_ele_t * fd_ghost_child ( fd_ghost_t * ghost, fd_ghost_ele_t * ele ) { return fd_ghost_pool_ele ( fd_ghost_pool ( ghost ), ele->child ); }
328 237 : FD_FN_PURE static inline fd_ghost_ele_t const * fd_ghost_child_const ( fd_ghost_t const * ghost, fd_ghost_ele_t const * ele ) { return fd_ghost_pool_ele_const( fd_ghost_pool_const( ghost ), ele->child ); }
329 0 : FD_FN_PURE static inline fd_ghost_ele_t * fd_ghost_sibling ( fd_ghost_t * ghost, fd_ghost_ele_t * ele ) { return fd_ghost_pool_ele ( fd_ghost_pool ( ghost ), ele->sibling ); }
330 225 : FD_FN_PURE static inline fd_ghost_ele_t const * fd_ghost_sibling_const( fd_ghost_t const * ghost, fd_ghost_ele_t const * ele ) { return fd_ghost_pool_ele_const( fd_ghost_pool_const( ghost ), ele->sibling ); }
331 :
332 : /* fd_ghost_{query,query_const} returns the ele keyed by `hash_id`,
333 : NULL if not found. */
334 :
335 : FD_FN_PURE static inline fd_ghost_ele_t *
336 1251 : fd_ghost_query( fd_ghost_t * ghost, fd_hash_t const * hash ) {
337 1251 : if( FD_UNLIKELY( !hash ) ) { return NULL; }
338 1251 : fd_ghost_hash_map_t * map = fd_ghost_hash_map( ghost );
339 1251 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
340 1251 : return fd_ghost_hash_map_ele_query( map, hash, NULL, pool );
341 1251 : }
342 :
343 : FD_FN_PURE static inline fd_ghost_ele_t const *
344 360 : fd_ghost_query_const( fd_ghost_t const * ghost, fd_hash_t const * hash ) {
345 360 : if( FD_UNLIKELY( !hash ) ) { return NULL; }
346 360 : fd_ghost_hash_map_t const * map = fd_ghost_hash_map_const ( ghost );
347 360 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
348 360 : return fd_ghost_hash_map_ele_query_const( map, hash, NULL, pool );
349 360 : }
350 :
351 : /* fd_ghost_hash returns the hash_id of the ele keyed by `slot`.
352 : NULL if the slot is not found. */
353 :
354 : FD_FN_PURE static inline fd_hash_t const *
355 87 : fd_ghost_hash( fd_ghost_t const * ghost, ulong slot ) {
356 87 : fd_ghost_slot_map_t const * maps = fd_ghost_slot_map_const( ghost );
357 87 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
358 87 : fd_ghost_ele_t const * ele = fd_ghost_slot_map_ele_query_const( maps, &slot, NULL, pool );
359 87 : return ele ? &ele->key : NULL;
360 87 : }
361 :
362 : /* fd_ghost_head greedily traverses down the ghost beginning from root,
363 : recursively picking the child with most `weight` on each level of the
364 : tree, terminating once it reaches a leaf (see top-level documentation
365 : for more traversal details). Assumes ghost is a current local join
366 : and has been initialized with fd_ghost_init and is therefore
367 : non-empty. */
368 :
369 : fd_ghost_ele_t const *
370 : fd_ghost_head( fd_ghost_t const * ghost, fd_ghost_ele_t const * root );
371 :
372 : /* fd_ghost_gca returns the greatest common ancestor of block1, block2
373 : in ghost. Assumes block1 or block2 are present in ghost (warns and
374 : returns NULL with handholding enabled). This is guaranteed to be
375 : non-NULL if block1 and block2 are both present. */
376 :
377 : fd_ghost_ele_t const *
378 : fd_ghost_gca( fd_ghost_t const * ghost, fd_hash_t const * bid1, fd_hash_t const * bid2 );
379 :
380 : /* fd_ghost_is_ancestor returns 1 if `ancestor` is `slot`'s ancestor, 0
381 : otherwise. Also returns 0 if either `ancestor` or `slot` are not in
382 : ghost. */
383 :
384 : int
385 : fd_ghost_is_ancestor( fd_ghost_t const * ghost, fd_hash_t const * ancestor, fd_hash_t const * slot );
386 :
387 : /* fd_ghost_anc_eqvoc. */
388 :
389 : int
390 : fd_ghost_invalid( fd_ghost_t const * ghost, fd_ghost_ele_t const * ele );
391 :
392 : /* Operations */
393 :
394 : /* fd_ghost_insert inserts a new ele keyed by `hash_id`, for the slot
395 : `slot` into the ghost. Inserts an ele keyed by `slot` into the slot
396 : map if one doesn't already exist as well. Assumes slot >= ghost->smr,
397 : parent_hash_id is already in ghost, and the ele pool has a free
398 : element (if handholding is enabled, explicitly checks and errors).
399 : Returns the inserted ghost ele. */
400 :
401 : /* FIXME: total_stake as an arg is a little unwieldy. is there a better
402 : way to design this API? ghost->total_stake runs the risk of forgetting
403 : to update*/
404 :
405 : fd_ghost_ele_t *
406 : fd_ghost_insert( fd_ghost_t * ghost, fd_hash_t const * parent_hash, ulong slot, fd_hash_t const * hash_id, ulong total_stake );
407 :
408 : /* fd_ghost_replay_vote votes for hash_id, adding pubkey's stake to the
409 : `stake` field for slot and to the `weight` field for both slot and
410 : slot's ancestors. If pubkey has previously voted, pubkey's stake is
411 : also subtracted from `weight` for its previous vote slot and its
412 : ancestors.
413 :
414 : Assumes slot is present in ghost (if handholding is enabled,
415 : explicitly checks and errors).
416 :
417 : TODO the implementation can be made more efficient by
418 : short-circuiting and doing fewer traversals. Currently this is
419 : bounded to O(h), where h is the height of ghost. */
420 :
421 : void
422 : fd_ghost_replay_vote( fd_ghost_t * ghost, fd_voter_t * voter, fd_hash_t const * hash_id );
423 :
424 : /* fd_ghost_gossip_vote adds stake amount to the gossip_stake field of
425 : slot.
426 :
427 : Assumes slot is present in ghost (if handholding is enabled,
428 : explicitly checks and errors). Returns the ghost ele keyed by slot.
429 :
430 : Unlike fd_ghost_replay_vote, this stake is not propagated to
431 : the weight field for slot and slot's ancestors. It is only counted
432 : towards slot itself, as gossip votes are only used for optimistic
433 : confirmation and not fork choice. */
434 :
435 : void
436 : fd_ghost_gossip_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong slot );
437 :
438 : /* fd_ghost_rooted_vote adds stake amount to the rooted_stake field of
439 : slot.
440 :
441 : Assumes slot is present in ghost (if handholding is enabled,
442 : explicitly checks and errors). Returns the ghost ele keyed by slot.
443 :
444 : Note rooting a slot implies rooting its ancestor, but ghost does not
445 : explicitly track this. */
446 :
447 : void
448 : fd_ghost_rooted_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong root );
449 :
450 : /* fd_ghost_publish publishes slot as the new ghost root, setting the
451 : subtree beginning from slot as the new ghost tree (ie. slot and all
452 : its descendants). Prunes all eles not in slot's ancestry. Assumes
453 : slot is present in ghost. Returns the new root. */
454 :
455 : fd_ghost_ele_t const *
456 : fd_ghost_publish( fd_ghost_t * ghost, fd_hash_t const * hash_id );
457 :
458 : /* Misc */
459 :
460 : /* fd_ghost_verify checks the ghost is not obviously corrupt, as well as
461 : that ghost invariants are being preserved ie. the weight of every
462 : ele is >= the sum of weights of its direct children. Returns 0 if
463 : verify succeeds, -1 otherwise. */
464 :
465 : int
466 : fd_ghost_verify( fd_ghost_t const * ghost );
467 :
468 : /* fd_ghost_print pretty-prints a formatted ghost tree. Printing begins
469 : from `ele` (it will appear as the root in the print output).
470 :
471 : The most straightforward and commonly used printing pattern is:
472 : `fd_ghost_print( ghost, fd_ghost_root( ghost ) )`
473 :
474 : This would print ghost beginning from the root.
475 :
476 : Alternatively, caller can print a more localized view, for example
477 : starting from the grandparent of the most recently executed slot:
478 :
479 : ```
480 : fd_ghost_ele_t const * ele = fd_ghost_query( slot );
481 : fd_ghost_print( ghost, fd_ghost_parent( fd_ghost_parent( ele ) ) )
482 : ```
483 :
484 : Callers should add null-checks as appropriate in actual usage. */
485 :
486 : void
487 : fd_ghost_print( fd_ghost_t const * ghost, ulong total_stake, fd_ghost_ele_t const * ele );
488 :
489 : static int FD_FN_UNUSED
490 48 : is_duplicate_confirmed( fd_ghost_t * ghost, fd_hash_t const * hash, ulong total_stake ) {
491 48 : fd_ghost_ele_t const * ele = fd_ghost_query( ghost, hash );
492 48 : if( FD_UNLIKELY( !ele ) ) {
493 0 : FD_LOG_WARNING(( "[%s] slot %s was not in ghost", __func__, FD_BASE58_ENC_32_ALLOCA(hash) ));
494 0 : return 0;
495 0 : }
496 48 : double pct = (double)( ele->weight + ele->gossip_stake ) / (double)total_stake; /* TODO make gossip weight a field as well */
497 48 : return pct > FD_EQVOCSAFE_PCT;
498 48 : }
499 :
500 : /* Duplicate confirmed signal */
501 :
502 : void
503 : process_duplicate_confirmed( fd_ghost_t * ghost, fd_hash_t const * hash, ulong slot );
504 :
505 : void
506 : process_duplicate( fd_ghost_t * ghost, ulong slot, ulong total_stake );
507 :
508 :
509 : FD_PROTOTYPES_END
510 :
511 : #endif /* HEADER_fd_src_choreo_ghost_fd_ghost_h */
|
