Line data Source code
1 : #include "fd_hfork.h"
2 : #include "fd_hfork_private.h"
3 :
4 : static void
5 : check( fd_hfork_t * hfork,
6 : ulong total_stake,
7 : candidate_t * candidate,
8 : int dead,
9 3 : fd_hash_t * our_bank_hash ) {
10 :
11 3 : if( FD_LIKELY( candidate->checked ) ) return; /* already checked this bank hash against our own */
12 3 : double pct = (double)candidate->stake * 100.0 / (double)total_stake;
13 3 : if( FD_LIKELY( pct < 52.0 ) ) return; /* not enough stake to compare */
14 :
15 3 : if( FD_UNLIKELY( dead ) ) {
16 0 : char msg[ 4096UL ];
17 0 : FD_BASE58_ENCODE_32_BYTES( candidate->key.block_id.uc, _block_id );
18 0 : FD_TEST( fd_cstr_printf_check( msg, sizeof( msg ), NULL,
19 0 : "HARD FORK DETECTED: our validator has marked slot %lu with block ID `%s` dead, but %lu validators with %.1f of stake have voted on it",
20 0 : candidate->slot,
21 0 : _block_id,
22 0 : candidate->cnt,
23 0 : pct ) );
24 :
25 0 : if( FD_UNLIKELY( hfork->fatal ) ) FD_LOG_ERR (( "%s", msg ));
26 0 : else FD_LOG_WARNING(( "%s", msg ));
27 3 : } else if( FD_UNLIKELY( 0!=memcmp( our_bank_hash, &candidate->key.bank_hash, 32UL ) ) ) {
28 0 : char msg[ 4096UL ];
29 0 : FD_BASE58_ENCODE_32_BYTES( our_bank_hash->uc, _our_bank_hash );
30 0 : FD_BASE58_ENCODE_32_BYTES( candidate->key.block_id.uc, _block_id );
31 0 : FD_BASE58_ENCODE_32_BYTES( candidate->key.bank_hash.uc, _bank_hash );
32 0 : FD_TEST( fd_cstr_printf_check( msg, sizeof( msg ), NULL,
33 0 : "HARD FORK DETECTED: our validator has produced bank hash `%s` for slot %lu with block ID `%s`, but %lu validators with %.1f of stake have voted on a different bank hash `%s` for the same slot",
34 0 : _our_bank_hash,
35 0 : candidate->slot,
36 0 : _block_id,
37 0 : candidate->cnt,
38 0 : pct,
39 0 : _bank_hash ) );
40 :
41 0 : if( FD_UNLIKELY( hfork->fatal ) ) FD_LOG_ERR (( "%s", msg ));
42 0 : else FD_LOG_WARNING(( "%s", msg ));
43 0 : }
44 3 : candidate->checked = 1;
45 3 : }
46 :
47 : ulong
48 33 : fd_hfork_align( void ) {
49 33 : return 128UL;
50 33 : }
51 :
52 : ulong
53 : fd_hfork_footprint( ulong max_live_slots,
54 6 : ulong max_vote_accounts ) {
55 6 : ulong fork_max = max_live_slots * max_vote_accounts;
56 6 : int lg_blk_max = fd_ulong_find_msb( fd_ulong_pow2_up( fork_max ) ) + 1;
57 6 : int lg_vtr_max = fd_ulong_find_msb( fd_ulong_pow2_up( max_vote_accounts ) ) + 1;
58 :
59 6 : ulong l = FD_LAYOUT_INIT;
60 6 : l = FD_LAYOUT_APPEND( l, alignof(fd_hfork_t), sizeof(fd_hfork_t) );
61 6 : l = FD_LAYOUT_APPEND( l, blk_map_align(), blk_map_footprint( lg_blk_max ) );
62 6 : l = FD_LAYOUT_APPEND( l, vtr_map_align(), vtr_map_footprint( lg_vtr_max ) );
63 6 : l = FD_LAYOUT_APPEND( l, candidate_map_align(), candidate_map_footprint( lg_blk_max ) );
64 6 : l = FD_LAYOUT_APPEND( l, bank_hash_pool_align(), bank_hash_pool_footprint( fork_max ) );
65 54 : for( ulong i = 0UL; i < fd_ulong_pow2( lg_vtr_max ); i++ ) {
66 48 : l = FD_LAYOUT_APPEND( l, votes_align(), votes_footprint( max_live_slots ) );
67 48 : }
68 6 : return FD_LAYOUT_FINI( l, fd_hfork_align() );
69 6 : }
70 :
71 : void *
72 : fd_hfork_new( void * shmem,
73 : ulong max_live_slots,
74 : ulong max_vote_accounts,
75 : ulong seed,
76 3 : int fatal ) {
77 3 : (void)seed; /* TODO map seed */
78 :
79 3 : if( FD_UNLIKELY( !shmem ) ) {
80 0 : FD_LOG_WARNING(( "NULL mem" ));
81 0 : return NULL;
82 0 : }
83 :
84 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_hfork_align() ) ) ) {
85 0 : FD_LOG_WARNING(( "misaligned mem" ));
86 0 : return NULL;
87 0 : }
88 :
89 3 : ulong footprint = fd_hfork_footprint( max_live_slots, max_vote_accounts );
90 3 : if( FD_UNLIKELY( !footprint ) ) {
91 0 : FD_LOG_WARNING(( "bad max_live_slots (%lu) or max_vote_accounts (%lu)", max_live_slots, max_vote_accounts ));
92 0 : return NULL;
93 0 : }
94 :
95 3 : fd_memset( shmem, 0, footprint );
96 :
97 3 : ulong fork_max = max_live_slots * max_vote_accounts;
98 3 : int lg_blk_max = fd_ulong_find_msb( fd_ulong_pow2_up( fork_max ) ) + 1;
99 3 : int lg_vtr_max = fd_ulong_find_msb( fd_ulong_pow2_up( max_vote_accounts ) ) + 1;
100 :
101 3 : FD_SCRATCH_ALLOC_INIT( l, shmem );
102 3 : fd_hfork_t * hfork = FD_SCRATCH_ALLOC_APPEND( l, fd_hfork_align(), sizeof( fd_hfork_t ) );
103 3 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint( lg_blk_max ) );
104 3 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( lg_vtr_max ) );
105 3 : void * candidate_map = FD_SCRATCH_ALLOC_APPEND( l, candidate_map_align(), candidate_map_footprint( lg_blk_max ) );
106 3 : void * bank_hash_pool = FD_SCRATCH_ALLOC_APPEND( l, bank_hash_pool_align(), bank_hash_pool_footprint( fork_max ) );
107 :
108 0 : hfork->blk_map = blk_map_new( blk_map, lg_blk_max, 0UL ); /* FIXME seed */
109 3 : hfork->vtr_map = vtr_map_new( vtr_map, lg_vtr_max, 0UL ); /* FIXME seed */
110 3 : hfork->candidate_map = candidate_map_new( candidate_map, lg_blk_max, 0UL ); /* FIXME seed */
111 3 : hfork->bank_hash_pool = bank_hash_pool_new( bank_hash_pool, fork_max );
112 :
113 3 : vtr_t * vtr_map_ = vtr_map_join( hfork->vtr_map );
114 27 : for( ulong i = 0UL; i < fd_ulong_pow2( lg_vtr_max ); i++ ) {
115 24 : void * votes = FD_SCRATCH_ALLOC_APPEND( l, votes_align(), votes_footprint( max_live_slots ) );
116 0 : vtr_map_[i].votes = votes_new( votes, max_live_slots );
117 24 : }
118 3 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_hfork_align() ) == (ulong)shmem + footprint );
119 3 : hfork->fatal = fatal;
120 3 : return shmem;
121 3 : }
122 :
123 : fd_hfork_t *
124 3 : fd_hfork_join( void * shhfork ) {
125 3 : fd_hfork_t * hfork = (fd_hfork_t *)shhfork;
126 :
127 3 : if( FD_UNLIKELY( !hfork ) ) {
128 0 : FD_LOG_WARNING(( "NULL hfork" ));
129 0 : return NULL;
130 0 : }
131 :
132 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)hfork, fd_hfork_align() ) ) ) {
133 0 : FD_LOG_WARNING(( "misaligned hfork" ));
134 0 : return NULL;
135 0 : }
136 :
137 3 : hfork->blk_map = blk_map_join( hfork->blk_map );
138 3 : hfork->vtr_map = vtr_map_join( hfork->vtr_map );
139 3 : hfork->candidate_map = candidate_map_join( hfork->candidate_map );
140 3 : hfork->bank_hash_pool = bank_hash_pool_join( hfork->bank_hash_pool );
141 27 : for( ulong i = 0UL; i < vtr_map_slot_cnt( hfork->vtr_map ); i++ ) {
142 24 : hfork->vtr_map[i].votes = votes_join( hfork->vtr_map[i].votes );
143 24 : }
144 :
145 3 : return hfork;
146 3 : }
147 :
148 : void *
149 3 : fd_hfork_leave( fd_hfork_t const * hfork ) {
150 :
151 3 : if( FD_UNLIKELY( !hfork ) ) {
152 0 : FD_LOG_WARNING(( "NULL hfork" ));
153 0 : return NULL;
154 0 : }
155 :
156 3 : return (void *)hfork;
157 3 : }
158 :
159 : void *
160 3 : fd_hfork_delete( void * hfork ) {
161 :
162 3 : if( FD_UNLIKELY( !hfork ) ) {
163 0 : FD_LOG_WARNING(( "NULL hfork" ));
164 0 : return NULL;
165 0 : }
166 :
167 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)hfork, fd_hfork_align() ) ) ) {
168 0 : FD_LOG_WARNING(( "misaligned hfork" ));
169 0 : return NULL;
170 0 : }
171 :
172 3 : return hfork;
173 3 : }
174 :
175 : void
176 21 : remove( blk_t * blk, fd_hash_t * bank_hash, bank_hash_t * pool ) {
177 21 : bank_hash_t * prev = NULL;
178 21 : bank_hash_t * curr = blk->bank_hashes;
179 27 : while( FD_LIKELY( curr ) ) {
180 27 : if( FD_LIKELY( 0==memcmp( &curr->bank_hash, bank_hash, 32UL ) ) ) break;
181 6 : prev = curr;
182 6 : curr = bank_hash_pool_ele( pool, curr->next );
183 6 : }
184 21 : FD_TEST( curr ); /* assumes bank_hash in blk->bank_hashes */
185 :
186 : /* In most cases, there is only one bank_hash per blk, so it will be
187 : the first element in blk->bank_hashes and prev will be NULL. */
188 :
189 21 : if( FD_LIKELY( !prev ) ) blk->bank_hashes = bank_hash_pool_ele( pool, curr->next );
190 6 : else prev->next = curr->next;
191 21 : bank_hash_pool_ele_release( pool, curr );
192 21 : }
193 :
194 : void
195 : fd_hfork_count_vote( fd_hfork_t * hfork,
196 : fd_hfork_metrics_t * metrics,
197 : fd_hash_t const * vote_acc,
198 : fd_hash_t const * block_id,
199 : fd_hash_t const * bank_hash,
200 : ulong slot,
201 : ulong stake,
202 48 : ulong total_stake ) {
203 :
204 : /* Get the vtr. */
205 :
206 48 : vtr_t * vtr = vtr_map_query( hfork->vtr_map, *vote_acc, NULL );
207 48 : if( FD_UNLIKELY( !vtr ) ) {
208 12 : FD_TEST( vtr_map_key_cnt( hfork->vtr_map ) < vtr_map_key_max( hfork->vtr_map ) );
209 12 : vtr = vtr_map_insert( hfork->vtr_map, *vote_acc );
210 12 : }
211 :
212 : /* Only process newer votes (by vote slot) from a given voter. */
213 :
214 48 : if( FD_UNLIKELY( !votes_empty( vtr->votes ) && votes_peek_tail_const( vtr->votes )->slot >= slot ) ) return;
215 :
216 : /* Evict the candidate's oldest vote (by vote slot). */
217 :
218 48 : if( FD_UNLIKELY( votes_full( vtr->votes ) ) ) {
219 24 : vote_t vote = votes_pop_head( vtr->votes );
220 24 : candidate_key_t key = { .block_id = vote.block_id, .bank_hash = vote.bank_hash };
221 24 : candidate_t * candidate = candidate_map_query( hfork->candidate_map, key, NULL );
222 24 : candidate->stake -= vote.stake;
223 24 : candidate->cnt--;
224 24 : if( FD_UNLIKELY( candidate->cnt==0 ) ) {
225 21 : candidate_map_remove( hfork->candidate_map, candidate );
226 21 : blk_t * blk = blk_map_query( hfork->blk_map, vote.block_id, NULL );
227 21 : FD_TEST( blk ); /* asumes if this is in candidate_map, it must also be in blk_map */
228 21 : remove( blk, &vote.bank_hash, hfork->bank_hash_pool );
229 21 : if( FD_UNLIKELY( !blk->bank_hashes ) ) {
230 12 : blk_map_remove( hfork->blk_map, blk );
231 12 : if( FD_UNLIKELY( blk->forked ) ) {
232 9 : metrics->active--;
233 9 : metrics->pruned++;
234 9 : }
235 12 : }
236 21 : }
237 24 : }
238 :
239 : /* Push the vote onto the vtr. */
240 :
241 48 : vote_t vote = { .block_id = *block_id, .bank_hash = *bank_hash, .slot = slot, .stake = stake };
242 48 : vtr->votes = votes_push_tail( vtr->votes, vote );
243 :
244 : /* Update the hard fork candidate for this block id. */
245 :
246 48 : candidate_key_t key = { .block_id = *block_id, .bank_hash = *bank_hash };
247 48 : candidate_t * candidate = candidate_map_query( hfork->candidate_map, key, NULL );
248 48 : if( FD_UNLIKELY( !candidate ) ) {
249 27 : candidate = candidate_map_insert( hfork->candidate_map, key );
250 27 : candidate->slot = slot;
251 27 : candidate->stake = 0UL;
252 27 : candidate->cnt = 0UL;
253 27 : }
254 48 : candidate->cnt++;
255 48 : candidate->stake += stake;
256 :
257 : /* Update the list of bank hashes for this block_id. */
258 :
259 48 : blk_t * blk = blk_map_query( hfork->blk_map, *block_id, NULL );
260 48 : if( FD_UNLIKELY( !blk ) ) {
261 18 : FD_TEST( blk_map_key_cnt( hfork->blk_map ) < blk_map_key_max( hfork->blk_map ) ); /* invariant violation: blk_map full */
262 18 : blk = blk_map_insert( hfork->blk_map, *block_id );
263 18 : blk->bank_hashes = NULL;
264 18 : blk->replayed = 0;
265 18 : blk->dead = 0;
266 18 : }
267 48 : int found = 0;
268 48 : ulong cnt = 0;
269 48 : bank_hash_t * prev = NULL;
270 48 : bank_hash_t * curr = blk->bank_hashes;
271 87 : while( FD_LIKELY( curr ) ) {
272 39 : if( FD_LIKELY( 0==memcmp( curr, bank_hash, 32UL ) ) ) found = 1;
273 39 : prev = curr;
274 39 : curr = bank_hash_pool_ele( hfork->bank_hash_pool, curr->next );
275 39 : cnt++;
276 39 : }
277 48 : if( FD_UNLIKELY( !found ) ) {
278 27 : FD_TEST( bank_hash_pool_free( hfork->bank_hash_pool ) );
279 27 : bank_hash_t * ele = bank_hash_pool_ele_acquire( hfork->bank_hash_pool );
280 27 : ele->bank_hash = *bank_hash;
281 27 : ele->next = bank_hash_pool_idx_null( hfork->bank_hash_pool );
282 27 : if( FD_LIKELY( !prev ) ) blk->bank_hashes = ele;
283 9 : else {
284 9 : prev->next = bank_hash_pool_idx( hfork->bank_hash_pool, ele );
285 9 : blk->forked = 1;
286 9 : metrics->seen++;
287 9 : metrics->active++;
288 9 : }
289 27 : cnt++;
290 27 : }
291 48 : metrics->max_width = fd_ulong_max( metrics->max_width, cnt );
292 :
293 : /* Check for hard forks. */
294 :
295 48 : if( FD_LIKELY( blk->replayed ) ) check( hfork, total_stake, candidate, blk->dead, &blk->our_bank_hash );
296 48 : }
297 :
298 : void
299 : fd_hfork_record_our_bank_hash( fd_hfork_t * hfork,
300 : fd_hash_t * block_id,
301 : fd_hash_t * bank_hash,
302 3 : ulong total_stake ) {
303 3 : blk_t * blk = blk_map_query( hfork->blk_map, *block_id, NULL );
304 3 : if( FD_UNLIKELY( !blk ) ) {
305 0 : blk = blk_map_insert( hfork->blk_map, *block_id );
306 0 : blk->replayed = 1;
307 0 : blk->bank_hashes = NULL;
308 0 : }
309 3 : if( FD_LIKELY( bank_hash ) ) { blk->dead = 0; blk->our_bank_hash = *bank_hash; }
310 0 : else blk->dead = 1;
311 :
312 3 : bank_hash_t * curr = blk->bank_hashes;
313 6 : while( FD_LIKELY( curr ) ) {
314 3 : candidate_key_t key = { .block_id = *block_id, .bank_hash = curr->bank_hash };
315 3 : candidate_t * candidate = candidate_map_query( hfork->candidate_map, key, NULL );
316 3 : if( FD_LIKELY( candidate ) ) check( hfork, total_stake, candidate, blk->dead, &blk->our_bank_hash );
317 3 : curr = bank_hash_pool_ele( hfork->bank_hash_pool, curr->next );
318 3 : }
319 3 : }
|
