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