Line data Source code
1 : #include "fd_notar.h"
2 :
3 : #define PRO_CONF (1./3) /* propagation confirmed */
4 : #define DUP_CONF (0.52) /* duplicate confirmed */
5 : #define OPT_CONF (2./3) /* optimistically confirmed */
6 :
7 : void *
8 0 : fd_notar_new( void * shmem, ulong blk_max ) {
9 :
10 0 : if( FD_UNLIKELY( !shmem ) ) {
11 0 : FD_LOG_WARNING(( "NULL mem" ));
12 0 : return NULL;
13 0 : }
14 :
15 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_notar_align() ) ) ) {
16 0 : FD_LOG_WARNING(( "misaligned mem" ));
17 0 : return NULL;
18 0 : }
19 :
20 0 : ulong footprint = fd_notar_footprint( blk_max );
21 0 : if( FD_UNLIKELY( !footprint ) ) {
22 0 : FD_LOG_WARNING(( "bad ele_max (%lu)", blk_max ));
23 0 : return NULL;
24 0 : }
25 :
26 0 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
27 0 : if( FD_UNLIKELY( !wksp ) ) {
28 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
29 0 : return NULL;
30 0 : }
31 :
32 0 : fd_memset( shmem, 0, footprint );
33 :
34 0 : int lg_blk_max = fd_ulong_find_msb( fd_ulong_pow2_up( blk_max ) );
35 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
36 0 : fd_notar_t * notar = FD_SCRATCH_ALLOC_APPEND( l, fd_notar_align(), sizeof(fd_notar_t) );
37 0 : void * blks = FD_SCRATCH_ALLOC_APPEND( l, fd_notar_blk_align(), fd_notar_blk_footprint( lg_blk_max ) );
38 0 : void * vtrs = FD_SCRATCH_ALLOC_APPEND( l, fd_notar_vtr_align(), fd_notar_vtr_footprint( lg_blk_max ) );
39 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_notar_align() ) == (ulong)shmem + footprint );
40 :
41 0 : notar->blks = fd_notar_blk_new( blks, lg_blk_max );
42 0 : notar->vtrs = fd_notar_blk_new( vtrs, lg_blk_max );
43 :
44 0 : return shmem;
45 0 : }
46 :
47 : fd_notar_t *
48 0 : fd_notar_join( void * shnotar ) {
49 0 : fd_notar_t * notar = (fd_notar_t *)shnotar;
50 :
51 0 : if( FD_UNLIKELY( !notar ) ) {
52 0 : FD_LOG_WARNING(( "NULL notar" ));
53 0 : return NULL;
54 0 : }
55 :
56 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)notar, fd_notar_align() ) ) ) {
57 0 : FD_LOG_WARNING(( "misaligned notar" ));
58 0 : return NULL;
59 0 : }
60 :
61 0 : fd_wksp_t * wksp = fd_wksp_containing( notar );
62 0 : if( FD_UNLIKELY( !wksp ) ) {
63 0 : FD_LOG_WARNING(( "notar must be part of a workspace" ));
64 0 : return NULL;
65 0 : }
66 :
67 0 : return notar;
68 0 : }
69 :
70 : void *
71 0 : fd_notar_leave( fd_notar_t const * notar ) {
72 :
73 0 : if( FD_UNLIKELY( !notar ) ) {
74 0 : FD_LOG_WARNING(( "NULL notar" ));
75 0 : return NULL;
76 0 : }
77 :
78 0 : return (void *)notar;
79 0 : }
80 :
81 : void *
82 0 : fd_notar_delete( void * notar ) {
83 :
84 0 : if( FD_UNLIKELY( !notar ) ) {
85 0 : FD_LOG_WARNING(( "NULL notar" ));
86 0 : return NULL;
87 0 : }
88 :
89 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)notar, fd_notar_align() ) ) ) {
90 0 : FD_LOG_WARNING(( "misaligned notar" ));
91 0 : return NULL;
92 0 : }
93 :
94 0 : return notar;
95 0 : }
96 :
97 : void
98 : fd_notar_vote( fd_notar_t * notar,
99 : fd_pubkey_t const * pubkey,
100 : ulong stake,
101 : fd_tower_t const * vote_tower,
102 0 : fd_hash_t const * vote_hash ) {
103 :
104 : /* Return early if the pubkey is not part of the set of voters we know
105 : from this epoch. Because these votes can come from gossip (and
106 : therefore have not been successfully validated and executed by the
107 : vote program), it's possible the vote itself is just invalid. */
108 :
109 0 : fd_notar_vtr_t const * vtr = fd_notar_vtr_query( notar->vtrs, *pubkey, NULL );
110 0 : if( FD_UNLIKELY( !vtr ) ) { FD_LOG_WARNING(( "unknown voter" )); return; };
111 :
112 : /* Return early if the tower is empty. As above, the vote could simply
113 : be invalid. */
114 :
115 0 : fd_tower_vote_t const * last_vote = fd_tower_votes_peek_tail_const( vote_tower );
116 0 : if( FD_UNLIKELY( !last_vote ) ) { FD_LOG_WARNING(( "empty tower" )); return; }
117 :
118 : /* It's possible we haven't yet replayed this slot being voted on.
119 : Even though votes can come from gossip (and therefore can be for
120 : slots ahead of what we've replayed), Agave verifies a vote's bank
121 : hash matches their own before counting it towards the confirmation
122 : thresholds.
123 :
124 : Therefore, only votes for slots we've already replayed (including
125 : gossip votes) can be counted.
126 :
127 : https://github.com/anza-xyz/agave/blob/v2.3.7/runtime/src/bank_hash_cache.rs#L68-L71 */
128 :
129 0 : fd_notar_blk_t * last_blk = fd_notar_blk_query( notar->blks, last_vote->slot, NULL );
130 0 : if( FD_UNLIKELY( !last_blk ) ) { FD_LOG_WARNING(( "haven't replayed slot %lu", last_vote->slot )); return; };
131 :
132 : /* Agave does a weird thing where they always count the last vote slot
133 : in the tower towards confirmation, regardless of whether the bank
134 : hash matches. However, "intermediate slots" in the tower are not
135 : counted when the bank hash doesn't match.
136 :
137 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/cluster_info_vote_listener.rs#L476-L487 */
138 :
139 0 : if( FD_LIKELY( last_blk->vtrs[ vtr->bit ] ) ) return; /* already counted */
140 0 : fd_notar_blk_vtrs_insert( last_blk->vtrs, vtr->bit ); /* count the voter */
141 0 : last_blk->stake += stake;
142 :
143 : /* Don't count remaining votes in tower if bank hash doesn't match. */
144 :
145 0 : if( FD_UNLIKELY( memcmp( &last_blk->bank_hash, vote_hash, sizeof(fd_hash_t) ) ) ) return;
146 :
147 : /* The voter's bank hash matches our own so we expect that all the
148 : slots in their tower towards the propagation threshold for that slot. */
149 :
150 0 : int skip = 1;
151 0 : for( fd_tower_votes_iter_t iter = fd_tower_votes_iter_init_rev( vote_tower );
152 0 : !fd_tower_votes_iter_done_rev( vote_tower, iter );
153 0 : iter = fd_tower_votes_iter_prev ( vote_tower, iter ) ) {
154 :
155 0 : if( FD_UNLIKELY( skip ) ) { skip = 0; continue; } /* skip the last vote (iter rev), we've already counted it */
156 :
157 0 : fd_tower_vote_t const * vote = fd_tower_votes_iter_ele_const( vote_tower, iter );
158 0 : if( FD_UNLIKELY( !vote ) ) continue;
159 0 : if( FD_UNLIKELY( vote->slot < notar->root ) ) continue;
160 :
161 : /* By definition every vote slot in the tower is an ancestor of the
162 : next vote slot. */
163 :
164 0 : fd_notar_blk_t * vote_blk = fd_notar_blk_query( notar->blks, vote->slot, NULL );
165 :
166 : /* Check this tower vote slot is in notar. If it's not, then the
167 : vote txn is invalid. We silently skip the vote the same way Agave
168 : does.
169 :
170 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/cluster_info_vote_listener.rs#L513-L518 */
171 :
172 0 : if( FD_UNLIKELY( !vote_blk ) ) continue;
173 :
174 : /* Check if we've already counted this voter's stake. */
175 :
176 0 : if( FD_LIKELY( vote_blk->vtrs[ vtr->bit ] ) ) continue;
177 :
178 : /* Count this voter's stake towards the confirmation thresholds. */
179 :
180 0 : fd_notar_blk_vtrs_insert( vote_blk->vtrs, vtr->bit );
181 0 : vote_blk->stake += stake;
182 :
183 : /* If a slot reaches propagation conf, then it's implied its
184 : ancestors are confirmed too because they're on the same fork. */
185 :
186 0 : double r = (double)vote_blk->stake / (double)notar->stake;
187 0 : if( FD_UNLIKELY( !vote_blk->pro_conf && r >= PRO_CONF ) ) for( fd_notar_blk_t * anc_blk = vote_blk; FD_LIKELY( anc_blk ); anc_blk = fd_notar_blk_query( notar->blks, anc_blk->parent_slot, NULL ) ) anc_blk->pro_conf = 1;
188 0 : }
189 0 : }
190 :
191 : void
192 : fd_notar_publish( fd_notar_t * notar,
193 0 : ulong root ) {
194 0 : for( ulong slot = notar->root; slot < root; slot++ ) {
195 0 : fd_notar_blk_t * blk = fd_notar_blk_query( notar->blks, slot, NULL );
196 0 : if( FD_LIKELY( blk ) ) fd_notar_blk_remove( notar->blks, blk );
197 0 : }
198 0 : notar->root = root;
199 0 : }
|
