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 27 : for( ulong i = 0UL; i < fd_ulong_pow2( lg_vtr_max ); i++ ) {
113 24 : void * votes = FD_SCRATCH_ALLOC_APPEND( l, votes_align(), votes_footprint( max_live_slots ) );
114 0 : vtr_t * join = vtr_map_join( hfork->vtr_map );
115 24 : join[i].votes = votes_new( votes, max_live_slots );
116 24 : }
117 3 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_hfork_align() ) == (ulong)shmem + footprint );
118 3 : hfork->fatal = fatal;
119 3 : return shmem;
120 3 : }
121 :
122 : fd_hfork_t *
123 3 : fd_hfork_join( void * shhfork ) {
124 3 : fd_hfork_t * hfork = (fd_hfork_t *)shhfork;
125 :
126 3 : if( FD_UNLIKELY( !hfork ) ) {
127 0 : FD_LOG_WARNING(( "NULL hfork" ));
128 0 : return NULL;
129 0 : }
130 :
131 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)hfork, fd_hfork_align() ) ) ) {
132 0 : FD_LOG_WARNING(( "misaligned hfork" ));
133 0 : return NULL;
134 0 : }
135 :
136 3 : hfork->blk_map = blk_map_join( hfork->blk_map );
137 3 : hfork->vtr_map = vtr_map_join( hfork->vtr_map );
138 3 : hfork->candidate_map = candidate_map_join( hfork->candidate_map );
139 3 : hfork->bank_hash_pool = bank_hash_pool_join( hfork->bank_hash_pool );
140 27 : for( ulong i = 0UL; i < vtr_map_slot_cnt( hfork->vtr_map ); i++ ) {
141 24 : hfork->vtr_map[i].votes = votes_join( hfork->vtr_map[i].votes );
142 24 : }
143 :
144 3 : return hfork;
145 3 : }
146 :
147 : void *
148 3 : fd_hfork_leave( fd_hfork_t const * hfork ) {
149 :
150 3 : if( FD_UNLIKELY( !hfork ) ) {
151 0 : FD_LOG_WARNING(( "NULL hfork" ));
152 0 : return NULL;
153 0 : }
154 :
155 3 : return (void *)hfork;
156 3 : }
157 :
158 : void *
159 3 : fd_hfork_delete( void * hfork ) {
160 :
161 3 : if( FD_UNLIKELY( !hfork ) ) {
162 0 : FD_LOG_WARNING(( "NULL hfork" ));
163 0 : return NULL;
164 0 : }
165 :
166 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)hfork, fd_hfork_align() ) ) ) {
167 0 : FD_LOG_WARNING(( "misaligned hfork" ));
168 0 : return NULL;
169 0 : }
170 :
171 3 : return hfork;
172 3 : }
173 :
174 : void
175 21 : remove( blk_t * blk, fd_hash_t * bank_hash, bank_hash_t * pool ) {
176 21 : bank_hash_t * prev = NULL;
177 21 : bank_hash_t * curr = blk->bank_hashes;
178 27 : while( FD_LIKELY( curr ) ) {
179 27 : if( FD_LIKELY( 0==memcmp( &curr->bank_hash, bank_hash, 32UL ) ) ) break;
180 6 : prev = curr;
181 6 : curr = bank_hash_pool_ele( pool, curr->next );
182 6 : }
183 21 : FD_TEST( curr ); /* assumes bank_hash in blk->bank_hashes */
184 :
185 : /* In most cases, there is only one bank_hash per blk, so it will be
186 : the first element in blk->bank_hashes and prev will be NULL. */
187 :
188 21 : if( FD_LIKELY( !prev ) ) blk->bank_hashes = bank_hash_pool_ele( pool, curr->next );
189 6 : else prev->next = curr->next;
190 21 : bank_hash_pool_ele_release( pool, curr );
191 21 : }
192 :
193 : void
194 : fd_hfork_count_vote( fd_hfork_t * hfork,
195 : fd_hash_t const * vote_acc,
196 : fd_hash_t const * block_id,
197 : fd_hash_t const * bank_hash,
198 : ulong slot,
199 : ulong stake,
200 : ulong total_stake,
201 48 : fd_hfork_metrics_t * metrics ) {
202 :
203 : /* Get the vtr. */
204 :
205 48 : vtr_t * vtr = vtr_map_query( hfork->vtr_map, *vote_acc, NULL );
206 48 : if( FD_UNLIKELY( !vtr ) ) {
207 12 : FD_TEST( vtr_map_key_cnt( hfork->vtr_map ) < vtr_map_key_max( hfork->vtr_map ) );
208 12 : vtr = vtr_map_insert( hfork->vtr_map, *vote_acc );
209 12 : }
210 :
211 : /* Ignore out of order or duplicate votes. */
212 :
213 48 : if( FD_UNLIKELY( !votes_empty( vtr->votes ) ) ) {
214 36 : vote_t const * tail = votes_peek_tail_const( vtr->votes );
215 36 : if( FD_UNLIKELY( tail && tail->slot >= slot ) ) return;
216 36 : }
217 :
218 : /* Evict the candidate's oldest vote (by vote slot). */
219 :
220 48 : if( FD_UNLIKELY( votes_full( vtr->votes ) ) ) {
221 24 : vote_t vote = votes_pop_head( vtr->votes );
222 24 : candidate_key_t key = { .block_id = vote.block_id, .bank_hash = vote.bank_hash };
223 24 : candidate_t * candidate = candidate_map_query( hfork->candidate_map, key, NULL );
224 24 : candidate->stake -= vote.stake;
225 24 : candidate->cnt--;
226 24 : if( FD_UNLIKELY( candidate->cnt==0 ) ) {
227 21 : candidate_map_remove( hfork->candidate_map, candidate );
228 21 : blk_t * blk = blk_map_query( hfork->blk_map, vote.block_id, NULL );
229 21 : FD_TEST( blk ); /* asumes if this is in candidate_map, it must also be in blk_map */
230 21 : remove( blk, &vote.bank_hash, hfork->bank_hash_pool );
231 21 : if( FD_UNLIKELY( !blk->bank_hashes ) ) {
232 12 : blk_map_remove( hfork->blk_map, blk );
233 12 : if( FD_UNLIKELY( blk->forked ) ) {
234 9 : metrics->active--;
235 9 : metrics->pruned++;
236 9 : }
237 12 : }
238 21 : }
239 24 : }
240 :
241 : /* Push the vote onto the vtr. */
242 :
243 48 : vote_t vote = { .block_id = *block_id, .bank_hash = *bank_hash, .slot = slot, .stake = stake };
244 48 : vtr->votes = votes_push_tail( vtr->votes, vote );
245 :
246 : /* Update the hard fork candidate for this block id. */
247 :
248 48 : candidate_key_t key = { .block_id = *block_id, .bank_hash = *bank_hash };
249 48 : candidate_t * candidate = candidate_map_query( hfork->candidate_map, key, NULL );
250 48 : if( FD_UNLIKELY( !candidate ) ) {
251 27 : candidate = candidate_map_insert( hfork->candidate_map, key );
252 27 : candidate->slot = slot;
253 27 : candidate->stake = 0UL;
254 27 : candidate->cnt = 0UL;
255 27 : }
256 48 : candidate->cnt++;
257 48 : candidate->stake += stake;
258 :
259 : /* Update the list of bank hashes for this block_id. */
260 :
261 48 : blk_t * blk = blk_map_query( hfork->blk_map, *block_id, NULL );
262 48 : if( FD_UNLIKELY( !blk ) ) {
263 18 : FD_TEST( blk_map_key_cnt( hfork->blk_map ) < blk_map_key_max( hfork->blk_map ) ); /* invariant violation: blk_map full */
264 18 : blk = blk_map_insert( hfork->blk_map, *block_id );
265 18 : blk->bank_hashes = NULL;
266 18 : blk->replayed = 0;
267 18 : blk->dead = 0;
268 18 : }
269 48 : int found = 0;
270 48 : ulong cnt = 0;
271 48 : bank_hash_t * prev = NULL;
272 48 : bank_hash_t * curr = blk->bank_hashes;
273 87 : while( FD_LIKELY( curr ) ) {
274 39 : if( FD_LIKELY( 0==memcmp( curr, bank_hash, 32UL ) ) ) found = 1;
275 39 : prev = curr;
276 39 : curr = bank_hash_pool_ele( hfork->bank_hash_pool, curr->next );
277 39 : cnt++;
278 39 : }
279 48 : if( FD_UNLIKELY( !found ) ) {
280 27 : FD_TEST( bank_hash_pool_free( hfork->bank_hash_pool ) );
281 27 : bank_hash_t * ele = bank_hash_pool_ele_acquire( hfork->bank_hash_pool );
282 27 : ele->bank_hash = *bank_hash;
283 27 : ele->next = bank_hash_pool_idx_null( hfork->bank_hash_pool );
284 27 : if( FD_LIKELY( !prev ) ) blk->bank_hashes = ele;
285 9 : else {
286 9 : prev->next = bank_hash_pool_idx( hfork->bank_hash_pool, ele );
287 9 : blk->forked = 1;
288 9 : metrics->seen++;
289 9 : metrics->active++;
290 9 : }
291 27 : cnt++;
292 27 : }
293 48 : metrics->max_width = fd_ulong_max( metrics->max_width, cnt );
294 :
295 : /* Check for hard forks. */
296 :
297 48 : if( FD_LIKELY( blk->replayed ) ) check( hfork, total_stake, candidate, blk->dead, &blk->our_bank_hash );
298 48 : }
299 :
300 : void
301 : fd_hfork_record_our_bank_hash( fd_hfork_t * hfork,
302 : fd_hash_t * block_id,
303 : fd_hash_t * bank_hash,
304 3 : ulong total_stake ) {
305 3 : blk_t * blk = blk_map_query( hfork->blk_map, *block_id, NULL );
306 3 : if( FD_UNLIKELY( !blk ) ) {
307 0 : blk = blk_map_insert( hfork->blk_map, *block_id );
308 0 : blk->replayed = 1;
309 0 : blk->bank_hashes = NULL;
310 0 : }
311 3 : if( FD_LIKELY( bank_hash ) ) { blk->dead = 0; blk->our_bank_hash = *bank_hash; }
312 0 : else blk->dead = 1;
313 :
314 3 : bank_hash_t * curr = blk->bank_hashes;
315 6 : while( FD_LIKELY( curr ) ) {
316 3 : candidate_key_t key = { .block_id = *block_id, .bank_hash = curr->bank_hash };
317 3 : candidate_t * candidate = candidate_map_query( hfork->candidate_map, key, NULL );
318 3 : if( FD_LIKELY( candidate ) ) check( hfork, total_stake, candidate, blk->dead, &blk->our_bank_hash );
319 3 : curr = bank_hash_pool_ele( hfork->bank_hash_pool, curr->next );
320 3 : }
321 3 : }
|
