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 and logging. */
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 :
214 : ulong dup_map_gaddr; /* wksp gaddr of the map (for fast O(1) querying, non-zero gaddr */
215 : /* version fseq. query pre & post read. if value is ULONG_MAX, ghost
216 : is uninitialized or invalid.
217 :
218 : odd: if either pre or post is odd, discard read.
219 : even: if pre == post, read is consistent. */
220 :
221 : ulong ver_gaddr;
222 : };
223 : typedef struct fd_ghost fd_ghost_t;
224 :
225 : FD_PROTOTYPES_BEGIN
226 :
227 : /* Constructors */
228 :
229 : /* fd_ghost_{align,footprint} return the required alignment and
230 : footprint of a memory region suitable for use as ghost with up to
231 : ele_max eles and vote_max votes. */
232 :
233 : FD_FN_CONST static inline ulong
234 735 : fd_ghost_align( void ) {
235 735 : return alignof(fd_ghost_t);
236 735 : }
237 :
238 : FD_FN_CONST static inline ulong
239 114 : fd_ghost_footprint( ulong ele_max ) {
240 114 : int lg_ele_max = fd_ulong_find_msb( fd_ulong_pow2_up( ele_max ) );
241 114 : return FD_LAYOUT_FINI(
242 114 : FD_LAYOUT_APPEND(
243 114 : FD_LAYOUT_APPEND(
244 114 : FD_LAYOUT_APPEND(
245 114 : FD_LAYOUT_APPEND(
246 114 : FD_LAYOUT_APPEND(
247 114 : FD_LAYOUT_APPEND(
248 114 : FD_LAYOUT_INIT,
249 114 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
250 114 : fd_fseq_align(), fd_fseq_footprint() ),
251 114 : fd_ghost_pool_align(), fd_ghost_pool_footprint ( ele_max ) ),
252 114 : fd_ghost_hash_map_align(), fd_ghost_hash_map_footprint( ele_max ) ),
253 114 : fd_ghost_slot_map_align(), fd_ghost_slot_map_footprint( ele_max ) ),
254 114 : fd_dup_seen_map_align(), fd_dup_seen_map_footprint ( lg_ele_max ) ),
255 114 : fd_ghost_align() );
256 114 : }
257 :
258 : /* fd_ghost_new formats an unused memory region for use as a ghost.
259 : mem is a non-NULL pointer to this region in the local address space
260 : with the required footprint and alignment. */
261 :
262 : void *
263 : fd_ghost_new( void * shmem, ulong ele_max, ulong seed );
264 :
265 : /* fd_ghost_join joins the caller to the ghost. ghost points to the
266 : first byte of the memory region backing the ghost in the caller's
267 : address space.
268 :
269 : Returns a pointer in the local address space to ghost on success. */
270 :
271 : fd_ghost_t *
272 : fd_ghost_join( void * ghost );
273 :
274 : /* fd_ghost_leave leaves a current local join. Returns a pointer to the
275 : underlying shared memory region on success and NULL on failure (logs
276 : details). Reasons for failure include ghost is NULL. */
277 :
278 : void *
279 : fd_ghost_leave( fd_ghost_t const * ghost );
280 :
281 : /* fd_ghost_delete unformats a memory region used as a ghost.
282 : Assumes only the nobody is joined to the region. Returns a
283 : pointer to the underlying shared memory region or NULL if used
284 : obviously in error (e.g. ghost is obviously not a ghost ... logs
285 : details). The ownership of the memory region is transferred to the
286 : caller. */
287 :
288 : void *
289 : fd_ghost_delete( void * ghost );
290 :
291 : /* fd_ghost_init initializes a ghost. Assumes ghost is a valid local
292 : join and no one else is joined. root is the initial root ghost will
293 : use. This is the snapshot slot if booting from a snapshot, 0 if the
294 : genesis slot. hash is the hash_id of the initial root.
295 :
296 : In general, this should be called by the same process that formatted
297 : ghost's memory, ie. the caller of fd_ghost_new. */
298 :
299 : void
300 : fd_ghost_init( fd_ghost_t * ghost, ulong root, fd_hash_t * hash );
301 :
302 : /* Accessors */
303 :
304 : /* fd_ghost_wksp returns the local join to the wksp backing the ghost.
305 : The lifetime of the returned pointer is at least as long as the
306 : lifetime of the local join. Assumes ghost is a current local
307 : join. */
308 :
309 : FD_FN_PURE static inline fd_wksp_t *
310 8880 : fd_ghost_wksp( fd_ghost_t const * ghost ) {
311 8880 : return (fd_wksp_t *)( ( (ulong)ghost ) - ghost->ghost_gaddr );
312 8880 : }
313 :
314 : /* fd_ghost_{ver,pool,map,root} returns a pointer in the caller's
315 : address space to the corresponding ghost field. const versions for
316 : each are also provided. */
317 :
318 579 : FD_FN_PURE static inline ulong * fd_ghost_ver ( fd_ghost_t * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->ver_gaddr ); }
319 102 : FD_FN_PURE static inline ulong const * fd_ghost_ver_const ( fd_ghost_t const * ghost ) { return fd_wksp_laddr_fast( fd_ghost_wksp( ghost ), ghost->ver_gaddr ); }
320 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 ); }
321 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 ); }
322 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 ); }
323 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 ); }
324 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 ); }
325 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 ); }
326 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 ); }
327 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 ); }
328 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 ); }
329 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 ); }
330 :
331 : /* fd_ghost_{parent,child,sibling} returns a pointer in the caller's
332 : address space to the corresponding {parent,left-child,right-sibling}
333 : of fec. Assumes ghost is a current local join and fec is a valid
334 : pointer to a pool element inside ghost. const versions for each are
335 : also provided. */
336 :
337 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 ); }
338 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 ); }
339 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 ); }
340 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 ); }
341 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 ); }
342 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 ); }
343 :
344 : /* fd_ghost_{query,query_const} returns the ele keyed by `hash_id`,
345 : NULL if not found. */
346 :
347 : FD_FN_PURE static inline fd_ghost_ele_t *
348 1251 : fd_ghost_query( fd_ghost_t * ghost, fd_hash_t const * hash ) {
349 1251 : if( FD_UNLIKELY( !hash ) ) { return NULL; }
350 1251 : fd_ghost_hash_map_t * map = fd_ghost_hash_map( ghost );
351 1251 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
352 1251 : return fd_ghost_hash_map_ele_query( map, hash, NULL, pool );
353 1251 : }
354 :
355 : FD_FN_PURE static inline fd_ghost_ele_t const *
356 360 : fd_ghost_query_const( fd_ghost_t const * ghost, fd_hash_t const * hash ) {
357 360 : if( FD_UNLIKELY( !hash ) ) { return NULL; }
358 360 : fd_ghost_hash_map_t const * map = fd_ghost_hash_map_const ( ghost );
359 360 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
360 360 : return fd_ghost_hash_map_ele_query_const( map, hash, NULL, pool );
361 360 : }
362 :
363 : /* fd_ghost_hash returns the hash_id of the ele keyed by `slot`.
364 : NULL if the slot is not found. */
365 :
366 : FD_FN_PURE static inline fd_hash_t const *
367 87 : fd_ghost_hash( fd_ghost_t const * ghost, ulong slot ) {
368 87 : fd_ghost_slot_map_t const * maps = fd_ghost_slot_map_const( ghost );
369 87 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
370 87 : fd_ghost_ele_t const * ele = fd_ghost_slot_map_ele_query_const( maps, &slot, NULL, pool );
371 87 : return ele ? &ele->key : NULL;
372 87 : }
373 :
374 : /* fd_ghost_head greedily traverses the ghost beginning from `root` (not
375 : necessarily the root of the ghost tree) and returns the heaviest leaf
376 : of the traversal (see top-level documentation for traversal details).
377 : Assumes ghost is a current local join and has been initialized with
378 : fd_ghost_init and is therefore non-empty. */
379 :
380 : fd_ghost_ele_t const *
381 : fd_ghost_head( fd_ghost_t const * ghost, fd_ghost_ele_t const * root );
382 :
383 : /* fd_ghost_gca returns the greatest common ancestor of block1, block2
384 : in ghost. Assumes block1 or block2 are present in ghost (warns and
385 : returns NULL with handholding enabled). This is guaranteed to be
386 : non-NULL if block1 and block2 are both present. */
387 :
388 : fd_ghost_ele_t const *
389 : fd_ghost_gca( fd_ghost_t const * ghost, fd_hash_t const * bid1, fd_hash_t const * bid2 );
390 :
391 : /* fd_ghost_is_ancestor returns 1 if `ancestor` is `slot`'s ancestor, 0
392 : otherwise. Also returns 0 if either `ancestor` or `slot` are not in
393 : ghost. */
394 :
395 : int
396 : fd_ghost_is_ancestor( fd_ghost_t const * ghost, fd_hash_t const * ancestor, fd_hash_t const * slot );
397 :
398 : /* Operations */
399 :
400 : /* fd_ghost_insert inserts a new ele keyed by `hash_id`, for the slot
401 : `slot` into the ghost. Inserts an ele keyed by `slot` into the slot
402 : map if one doesn't already exist as well. Assumes slot >= ghost->smr,
403 : parent_hash_id is already in ghost, and the ele pool has a free
404 : element (if handholding is enabled, explicitly checks and errors).
405 : Returns the inserted ghost ele. */
406 :
407 : /* FIXME: total_stake as an arg is a little unwieldy. is there a better
408 : way to design this API? ghost->total_stake runs the risk of forgetting
409 : to update*/
410 :
411 : fd_ghost_ele_t *
412 : fd_ghost_insert( fd_ghost_t * ghost, fd_hash_t const * parent_hash, ulong slot, fd_hash_t const * hash_id, ulong total_stake );
413 :
414 : /* fd_ghost_replay_vote votes for hash_id, adding pubkey's stake to the
415 : `stake` field for slot and to the `weight` field for both slot and
416 : slot's ancestors. If pubkey has previously voted, pubkey's stake is
417 : also subtracted from `weight` for its previous vote slot and its
418 : ancestors.
419 :
420 : Assumes slot is present in ghost (if handholding is enabled,
421 : explicitly checks and errors).
422 :
423 : TODO the implementation can be made more efficient by
424 : short-circuiting and doing fewer traversals. Currently this is
425 : bounded to O(h), where h is the height of ghost. */
426 :
427 : void
428 : fd_ghost_replay_vote( fd_ghost_t * ghost, fd_voter_t * voter, fd_hash_t const * hash_id );
429 :
430 : /* fd_ghost_gossip_vote adds stake amount to the gossip_stake field of
431 : slot.
432 :
433 : Assumes slot is present in ghost (if handholding is enabled,
434 : explicitly checks and errors). Returns the ghost ele keyed by slot.
435 :
436 : Unlike fd_ghost_replay_vote, this stake is not propagated to
437 : the weight field for slot and slot's ancestors. It is only counted
438 : towards slot itself, as gossip votes are only used for optimistic
439 : confirmation and not fork choice. */
440 :
441 : void
442 : fd_ghost_gossip_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong slot );
443 :
444 : /* fd_ghost_rooted_vote adds stake amount to the rooted_stake field of
445 : slot.
446 :
447 : Assumes slot is present in ghost (if handholding is enabled,
448 : explicitly checks and errors). Returns the ghost ele keyed by slot.
449 :
450 : Note rooting a slot implies rooting its ancestor, but ghost does not
451 : explicitly track this. */
452 :
453 : void
454 : fd_ghost_rooted_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong root );
455 :
456 : /* fd_ghost_publish publishes slot as the new ghost root, setting the
457 : subtree beginning from slot as the new ghost tree (ie. slot and all
458 : its descendants). Prunes all eles not in slot's ancestry. Assumes
459 : slot is present in ghost. Returns the new root. */
460 :
461 : fd_ghost_ele_t const *
462 : fd_ghost_publish( fd_ghost_t * ghost, fd_hash_t const * hash_id );
463 :
464 : /* Misc */
465 :
466 : /* fd_ghost_verify checks the ghost is not obviously corrupt, as well as
467 : that ghost invariants are being preserved ie. the weight of every
468 : ele is >= the sum of weights of its direct children. Returns 0 if
469 : verify succeeds, -1 otherwise. */
470 :
471 : int
472 : fd_ghost_verify( fd_ghost_t const * ghost );
473 :
474 : /* fd_ghost_print pretty-prints a formatted ghost tree. Printing begins
475 : from `ele` (it will appear as the root in the print output).
476 :
477 : The most straightforward and commonly used printing pattern is:
478 : `fd_ghost_print( ghost, fd_ghost_root( ghost ) )`
479 :
480 : This would print ghost beginning from the root.
481 :
482 : Alternatively, caller can print a more localized view, for example
483 : starting from the grandparent of the most recently executed slot:
484 :
485 : ```
486 : fd_ghost_ele_t const * ele = fd_ghost_query( slot );
487 : fd_ghost_print( ghost, fd_ghost_parent( fd_ghost_parent( ele ) ) )
488 : ```
489 :
490 : Callers should add null-checks as appropriate in actual usage. */
491 :
492 : void
493 : fd_ghost_print( fd_ghost_t const * ghost, ulong total_stake, fd_ghost_ele_t const * ele );
494 :
495 : static int FD_FN_UNUSED
496 48 : is_duplicate_confirmed( fd_ghost_t * ghost, fd_hash_t const * hash, ulong total_stake ) {
497 48 : fd_ghost_ele_t const * ele = fd_ghost_query( ghost, hash );
498 48 : if( FD_UNLIKELY( !ele ) ) {
499 0 : FD_LOG_WARNING(( "[%s] slot %s was not in ghost", __func__, FD_BASE58_ENC_32_ALLOCA(hash) ));
500 0 : return 0;
501 0 : }
502 48 : double pct = (double)( ele->weight + ele->gossip_stake ) / (double)total_stake; /* TODO make gossip weight a field as well */
503 48 : return pct > FD_EQVOCSAFE_PCT;
504 48 : }
505 :
506 : /* Duplicate confirmed signal */
507 :
508 : void
509 : process_duplicate_confirmed( fd_ghost_t * ghost, fd_hash_t const * hash, ulong slot );
510 :
511 : void
512 : process_duplicate( fd_ghost_t * ghost, ulong slot, ulong total_stake );
513 :
514 :
515 : FD_PROTOTYPES_END
516 :
517 : #endif /* HEADER_fd_src_choreo_ghost_fd_ghost_h */
|
