Line data Source code
1 : #include "fd_hfork.h"
2 :
3 : /* fd_hfork maintains four pools and four maps:
4 :
5 : bhm_pool (capacity max = per_vtr_max * vtr_max): pool of bhm_t
6 : elements, where bhm stands for "bank hash matcher". Each
7 : bhm tracks the aggregate stake and vote count for a
8 : particular (block_id, bank_hash) pair.
9 :
10 : bhm_map (capacity max): maps bhm_key_t (block_id, bank_hash) ->
11 : bhm_t for O(1) lookup of a specific bank hash matcher.
12 :
13 : blk_pool (capacity max): pool of blk_t elements. Each blk_t stores
14 : per-block metadata (our_bank_hash, replayed, dead, matched,
15 : mismatched, checked) and owns a bhm_dlist of all bhm entries sharing the
16 : same block_id.
17 :
18 : blk_map (capacity max): maps block_id -> blk_t for O(1) lookup of
19 : per-block metadata.
20 :
21 : vte_pool (capacity max): pool of vte_t elements. Each vte
22 : records a single vote (block_id, bank_hash, slot, stake)
23 : from a voter, stored in that voter's vte_dlist. When a
24 : voter's vte_dlist reaches per_vtr_max entries, the oldest vte
25 : is popped and its stake contribution is subtracted from
26 : the corresponding bhm.
27 :
28 : vte_map (capacity max): maps vte_key_t (vote_acc, block_id) -> vte_t
29 : for O(1) check of whether a voter has already voted for a
30 : given block_id. If they have, the vote is ignored.
31 :
32 : vtr_map (capacity vtr_max): maps vote_acc -> vtr_t, tracking each
33 : known voter. vtr entries are explicitly managed by
34 : fd_hfork_update_voters when the epoch stake set changes.
35 : Each vtr has a pre-allocated vte_dlist that tracks the
36 : voter's recent votes in FIFO order.
37 :
38 : vtr_map blk_map
39 : map[0] +--------------------+ map[0] +--------------------+
40 : | (vtr_t) { | | (blk_t) { |
41 : | .vote_acc = X, | | .block_id = A, |
42 : | ... | | ... |
43 : | .vte_dlist = ... | | .bhm_dlist = ... |
44 : | } | | } |
45 : map[1] +--------------------+ map[1] +--------------------+
46 : | (vtr_t) { | | (blk_t) { |
47 : | .vote_acc = Y, | | .block_id = B |
48 : | ... | | ... |
49 : | .vte_dlist = + | | .bhm_dlist = + |
50 : | } | | | } | |
51 : +----------------|---+ +----------------|---+
52 : | |
53 : | |
54 : | |
55 : | bhm_dlist <------+
56 : | +--------------+--------------+--------------+
57 : | | (bhm_t) { | (bhm_t) { | (bhm_t) { |
58 : | | .key = A0, | .key = A1, | .key = A2, |
59 : | | ... | ... | ... |
60 : | | } | } | } |
61 : | +--------------+--------------+--------------+
62 : |
63 : V
64 : vte_dlist
65 : +------------------------+------------------------+------------------------+
66 : | (vte_t) { | (vte_t) { | (vte_t) { |
67 : | .key.vote_acc = Y, | .key.vote_acc = Y, | .key.vote_acc = Y, |
68 : | .key.block_id = A, | .key.block_id = C, | .key.block_id = B, |
69 : | .bank_hash = A0, | .bank_hash = C0, | .bank_hash = B0, |
70 : | ... | ... | ... |
71 : | } | } | } |
72 : +------------------------+------------------------+------------------------+
73 : oldest newest
74 :
75 : vte_map prevents a voter from voting for the same block_id twice.
76 : The adversary is bounded because when vte_cnt == per_vtr_max, the
77 : oldest vte is popped and its stake is subtracted from the matching
78 : bhm. */
79 :
80 : typedef struct {
81 : fd_hash_t block_id;
82 : fd_hash_t bank_hash;
83 : } bhm_key_t;
84 :
85 : struct bhm {
86 : bhm_key_t key; /* bhm_map key */
87 : ulong next; /* pool next */
88 : struct {
89 : ulong prev;
90 : ulong next;
91 : } map;
92 : struct {
93 : ulong prev;
94 : ulong next;
95 : } dlist;
96 : ulong slot;
97 : ulong stake;
98 : };
99 : typedef struct bhm bhm_t;
100 :
101 : #define POOL_NAME bhm_pool
102 54 : #define POOL_T bhm_t
103 : #include "../../util/tmpl/fd_pool.c"
104 :
105 : #define MAP_NAME bhm_map
106 12 : #define MAP_ELE_T bhm_t
107 : #define MAP_KEY_T bhm_key_t
108 207 : #define MAP_PREV map.prev
109 342 : #define MAP_NEXT map.next
110 246 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->block_id.key,(k1)->block_id.key,32UL) & \
111 246 : !memcmp((k0)->bank_hash.key,(k1)->bank_hash.key,32UL))
112 222 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->block_id.ul[1]^(key)->bank_hash.ul[1]^(seed)))
113 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
114 : #include "../../util/tmpl/fd_map_chain.c"
115 :
116 : #define DLIST_NAME bhm_dlist
117 : #define DLIST_ELE_T bhm_t
118 210 : #define DLIST_PREV dlist.prev
119 213 : #define DLIST_NEXT dlist.next
120 : #include "../../util/tmpl/fd_dlist.c"
121 :
122 : struct blk {
123 : fd_hash_t block_id; /* blk_map key */
124 : ulong prev; /* blk_map prev */
125 : ulong next; /* pool next / blk_map next */
126 : struct {
127 : ulong prev;
128 : ulong next;
129 : } dlist;
130 : fd_hash_t our_bank_hash; /* 0: not replayed, -1: dead, else: our bank hash */
131 : void * bhm_dlist; /* dlist of bank hash objects for this block id */
132 : ulong bhm_cnt; /* number of competing bank hashes for this block id */
133 : };
134 : typedef struct blk blk_t;
135 :
136 : #define POOL_NAME blk_pool
137 81 : #define POOL_T blk_t
138 : #include "../../util/tmpl/fd_pool.c"
139 :
140 : #define MAP_NAME blk_map
141 18 : #define MAP_ELE_T blk_t
142 : #define MAP_KEY_T fd_hash_t
143 114 : #define MAP_KEY block_id
144 249 : #define MAP_PREV prev
145 612 : #define MAP_NEXT next
146 525 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->key,(k1)->key,32UL))
147 330 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->ul[1]^(seed)))
148 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
149 : #include "../../util/tmpl/fd_map_chain.c"
150 :
151 : #define DLIST_NAME blk_dlist
152 : #define DLIST_ELE_T blk_t
153 72 : #define DLIST_PREV dlist.prev
154 78 : #define DLIST_NEXT dlist.next
155 : #include "../../util/tmpl/fd_dlist.c"
156 :
157 : typedef struct {
158 : fd_pubkey_t vote_acc;
159 : fd_hash_t block_id;
160 : } vte_key_t;
161 :
162 : struct vte {
163 : vte_key_t key; /* vte_map key: (vote_acc, block_id) */
164 : ulong next;
165 : struct {
166 : ulong prev;
167 : ulong next;
168 : } vte_map;
169 : struct {
170 : ulong prev;
171 : ulong next;
172 : } dlist;
173 : fd_hash_t bank_hash;
174 : ulong slot;
175 : ulong stake;
176 : };
177 : typedef struct vte vte_t;
178 :
179 : #define POOL_NAME vte_pool
180 54 : #define POOL_T vte_t
181 : #include "../../util/tmpl/fd_pool.c"
182 :
183 : #define MAP_NAME vte_map
184 18 : #define MAP_ELE_T vte_t
185 : #define MAP_KEY_T vte_key_t
186 123 : #define MAP_PREV vte_map.prev
187 192 : #define MAP_NEXT vte_map.next
188 96 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->vote_acc.key,(k1)->vote_acc.key,32UL) & \
189 96 : !memcmp((k0)->block_id.key,(k1)->block_id.key,32UL))
190 150 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->vote_acc.ul[1]^(key)->block_id.ul[1]^(seed)))
191 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
192 : #include "../../util/tmpl/fd_map_chain.c"
193 :
194 : #define DLIST_NAME vte_dlist
195 : #define DLIST_ELE_T vte_t
196 69 : #define DLIST_PREV dlist.prev
197 87 : #define DLIST_NEXT dlist.next
198 : #include "../../util/tmpl/fd_dlist.c"
199 :
200 : struct vtr {
201 : fd_pubkey_t vote_acc;
202 : ulong next; /* pool next; reused as kept flag during update_voters */
203 : struct {
204 : ulong prev;
205 : ulong next;
206 : } map;
207 : struct {
208 : ulong prev;
209 : ulong next;
210 : } dlist;
211 : vte_dlist_t * vte_dlist;
212 : ulong vte_cnt;
213 : };
214 : typedef struct vtr vtr_t;
215 :
216 : #define POOL_NAME vtr_pool
217 81 : #define POOL_T vtr_t
218 : #include "../../util/tmpl/fd_pool.c"
219 :
220 : #define MAP_NAME vtr_map
221 12 : #define MAP_ELE_T vtr_t
222 : #define MAP_KEY_T fd_pubkey_t
223 60 : #define MAP_KEY vote_acc
224 252 : #define MAP_PREV map.prev
225 369 : #define MAP_NEXT map.next
226 249 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->key,(k1)->key,sizeof(fd_pubkey_t)))
227 204 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->ul[1]^(seed)))
228 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
229 : #include "../../util/tmpl/fd_map_chain.c"
230 :
231 : #define DLIST_NAME vtr_dlist
232 : #define DLIST_ELE_T vtr_t
233 75 : #define DLIST_PREV dlist.prev
234 114 : #define DLIST_NEXT dlist.next
235 : #include "../../util/tmpl/fd_dlist.c"
236 :
237 : struct __attribute__((aligned(128UL))) fd_hfork {
238 : ulong max;
239 : ulong per_vtr_max;
240 : ulong vtr_max;
241 : bhm_t * bhm_pool;
242 : bhm_map_t * bhm_map;
243 : blk_t * blk_pool;
244 : blk_map_t * blk_map;
245 : blk_dlist_t * blk_dlist;
246 : vte_t * vte_pool;
247 : vte_map_t * vte_map;
248 : vtr_t * vtr_pool;
249 : vtr_map_t * vtr_map;
250 : vtr_dlist_t * vtr_dlist;
251 : };
252 : typedef struct fd_hfork fd_hfork_t;
253 :
254 :
255 : /* bhm_remove removes a bhm from bhm_map, its owning blk's bhm_dlist,
256 : and releases it back to bhm_pool. If the blk has no remaining bhm
257 : entries, then the blk is also removed and released. */
258 :
259 : static void
260 : bhm_remove( fd_hfork_t * hfork,
261 12 : bhm_t * bhm ) {
262 12 : blk_t * blk = blk_map_ele_query( hfork->blk_map, &bhm->key.block_id, NULL, hfork->blk_pool );
263 12 : FD_TEST( blk );
264 12 : bhm_dlist_ele_remove( blk->bhm_dlist, bhm, hfork->bhm_pool );
265 12 : bhm_map_ele_remove_fast( hfork->bhm_map, bhm, hfork->bhm_pool );
266 12 : bhm_pool_ele_release( hfork->bhm_pool, bhm );
267 12 : blk->bhm_cnt--;
268 12 : if( FD_UNLIKELY( !blk->bhm_cnt ) ) {
269 12 : blk_map_ele_remove_fast( hfork->blk_map, blk, hfork->blk_pool );
270 12 : blk_pool_ele_release( hfork->blk_pool, blk );
271 12 : }
272 12 : }
273 :
274 : static int
275 : compare( blk_t * blk,
276 : bhm_t * bhm,
277 75 : ulong total_stake ) {
278 :
279 75 : if( FD_UNLIKELY( 0==memcmp( &blk->our_bank_hash, &hash_null, sizeof(fd_hash_t) ) ) ) return 0;
280 :
281 18 : double pct = (double)bhm->stake * 100.0 / (double)total_stake;
282 18 : if( FD_UNLIKELY( pct < 52.0 ) ) return 0;
283 :
284 9 : if( FD_UNLIKELY( 0!=memcmp( &blk->our_bank_hash, &bhm->key.bank_hash, sizeof(fd_hash_t) ) ) ) return -1;
285 3 : return 1;
286 9 : }
287 :
288 : ulong
289 270 : fd_hfork_align( void ) {
290 270 : return 128UL;
291 270 : }
292 :
293 : ulong
294 : fd_hfork_footprint( ulong per_vtr_max,
295 54 : ulong vtr_max ) {
296 :
297 54 : vtr_max = fd_ulong_pow2_up( vtr_max );
298 54 : ulong max = fd_ulong_pow2_up( per_vtr_max * vtr_max );
299 :
300 54 : ulong l = FD_LAYOUT_INIT;
301 54 : l = FD_LAYOUT_APPEND( l, alignof(fd_hfork_t), sizeof(fd_hfork_t) );
302 54 : l = FD_LAYOUT_APPEND( l, bhm_pool_align(), bhm_pool_footprint( max ) );
303 54 : l = FD_LAYOUT_APPEND( l, bhm_map_align(), bhm_map_footprint( bhm_map_chain_cnt_est( max ) ) );
304 54 : l = FD_LAYOUT_APPEND( l, blk_pool_align(), blk_pool_footprint( max ) );
305 54 : l = FD_LAYOUT_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( max ) ) );
306 54 : l = FD_LAYOUT_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
307 54 : l = FD_LAYOUT_APPEND( l, vte_pool_align(), vte_pool_footprint( max ) );
308 54 : l = FD_LAYOUT_APPEND( l, vte_map_align(), vte_map_footprint( vte_map_chain_cnt_est( max ) ) );
309 54 : l = FD_LAYOUT_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
310 54 : l = FD_LAYOUT_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
311 54 : l = FD_LAYOUT_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
312 726 : for( ulong i = 0UL; i < max; i++ ) {
313 672 : l = FD_LAYOUT_APPEND( l, bhm_dlist_align(), bhm_dlist_footprint() );
314 672 : }
315 186 : for( ulong i = 0UL; i < vtr_max; i++ ) {
316 132 : l = FD_LAYOUT_APPEND( l, vte_dlist_align(), vte_dlist_footprint() );
317 132 : }
318 54 : return FD_LAYOUT_FINI( l, fd_hfork_align() );
319 54 : }
320 :
321 : void *
322 : fd_hfork_new( void * shmem,
323 : ulong per_vtr_max,
324 : ulong vtr_max,
325 27 : ulong seed ) {
326 :
327 27 : if( FD_UNLIKELY( !shmem ) ) {
328 0 : FD_LOG_WARNING(( "NULL mem" ));
329 0 : return NULL;
330 0 : }
331 :
332 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_hfork_align() ) ) ) {
333 0 : FD_LOG_WARNING(( "misaligned mem" ));
334 0 : return NULL;
335 0 : }
336 :
337 27 : ulong footprint = fd_hfork_footprint( per_vtr_max, vtr_max );
338 27 : if( FD_UNLIKELY( !footprint ) ) {
339 0 : FD_LOG_WARNING(( "bad per_vtr_max (%lu) or vtr_max (%lu)", per_vtr_max, vtr_max ));
340 0 : return NULL;
341 0 : }
342 :
343 27 : fd_memset( shmem, 0, footprint );
344 :
345 27 : vtr_max = fd_ulong_pow2_up( vtr_max );
346 27 : ulong max = fd_ulong_pow2_up( per_vtr_max * vtr_max );
347 :
348 27 : FD_SCRATCH_ALLOC_INIT( l, shmem );
349 27 : fd_hfork_t * hfork = FD_SCRATCH_ALLOC_APPEND( l, fd_hfork_align(), sizeof(fd_hfork_t) );
350 27 : void * bhm_pool = FD_SCRATCH_ALLOC_APPEND( l, bhm_pool_align(), bhm_pool_footprint( max ) );
351 27 : void * bhm_map = FD_SCRATCH_ALLOC_APPEND( l, bhm_map_align(), bhm_map_footprint( bhm_map_chain_cnt_est( max ) ) );
352 27 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( max ) );
353 27 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( max ) ) );
354 27 : void * blk_dlist = FD_SCRATCH_ALLOC_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
355 27 : void * vte_pool = FD_SCRATCH_ALLOC_APPEND( l, vte_pool_align(), vte_pool_footprint( max ) );
356 27 : void * vte_map = FD_SCRATCH_ALLOC_APPEND( l, vte_map_align(), vte_map_footprint( vte_map_chain_cnt_est( max ) ) );
357 27 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
358 27 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
359 27 : void * vtr_dlist = FD_SCRATCH_ALLOC_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
360 :
361 27 : hfork->max = max;
362 27 : hfork->per_vtr_max = per_vtr_max;
363 27 : hfork->vtr_max = vtr_max;
364 27 : hfork->bhm_pool = bhm_pool_new ( bhm_pool, max );
365 27 : hfork->bhm_map = bhm_map_new ( bhm_map, bhm_map_chain_cnt_est( max ), seed );
366 27 : hfork->blk_pool = blk_pool_new ( blk_pool, max );
367 27 : hfork->blk_map = blk_map_new ( blk_map, blk_map_chain_cnt_est( max ), seed );
368 27 : hfork->blk_dlist = blk_dlist_new( blk_dlist );
369 27 : hfork->vte_pool = vte_pool_new ( vte_pool, max );
370 27 : hfork->vte_map = vte_map_new ( vte_map, vte_map_chain_cnt_est( max ), seed );
371 27 : hfork->vtr_pool = vtr_pool_new ( vtr_pool, vtr_max );
372 27 : hfork->vtr_map = vtr_map_new ( vtr_map, vtr_map_chain_cnt_est( vtr_max ), seed );
373 27 : hfork->vtr_dlist = vtr_dlist_new( vtr_dlist );
374 :
375 27 : blk_t * blk_join = blk_pool_join( hfork->blk_pool );
376 363 : for( ulong i = 0UL; i < max; i++ ) {
377 336 : void * bhm_dlist = FD_SCRATCH_ALLOC_APPEND( l, bhm_dlist_align(), bhm_dlist_footprint() );
378 336 : blk_join[i].bhm_cnt = 0;
379 336 : blk_join[i].bhm_dlist = bhm_dlist_new( bhm_dlist );
380 336 : }
381 :
382 27 : vtr_t * vtr_join = vtr_pool_join( hfork->vtr_pool );
383 93 : for( ulong i = 0UL; i < vtr_max; i++ ) {
384 66 : void * vte_dlist = FD_SCRATCH_ALLOC_APPEND( l, vte_dlist_align(), vte_dlist_footprint() );
385 66 : vtr_join[i].vte_cnt = 0;
386 66 : vtr_join[i].vte_dlist = vte_dlist_new( vte_dlist );
387 66 : }
388 27 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_hfork_align() ) == (ulong)shmem + footprint );
389 27 : return shmem;
390 27 : }
391 :
392 : fd_hfork_t *
393 27 : fd_hfork_join( void * shhfork ) {
394 27 : fd_hfork_t * hfork = (fd_hfork_t *)shhfork;
395 :
396 27 : if( FD_UNLIKELY( !hfork ) ) {
397 0 : FD_LOG_WARNING(( "NULL hfork" ));
398 0 : return NULL;
399 0 : }
400 :
401 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)hfork, fd_hfork_align() ) ) ) {
402 0 : FD_LOG_WARNING(( "misaligned hfork" ));
403 0 : return NULL;
404 0 : }
405 :
406 27 : hfork->bhm_pool = bhm_pool_join ( hfork->bhm_pool );
407 27 : hfork->bhm_map = bhm_map_join ( hfork->bhm_map );
408 27 : hfork->blk_pool = blk_pool_join ( hfork->blk_pool );
409 27 : hfork->blk_map = blk_map_join ( hfork->blk_map );
410 27 : hfork->blk_dlist = blk_dlist_join( hfork->blk_dlist );
411 27 : hfork->vte_pool = vte_pool_join ( hfork->vte_pool );
412 27 : hfork->vte_map = vte_map_join ( hfork->vte_map );
413 27 : hfork->vtr_pool = vtr_pool_join ( hfork->vtr_pool );
414 27 : hfork->vtr_map = vtr_map_join ( hfork->vtr_map );
415 27 : hfork->vtr_dlist = vtr_dlist_join( hfork->vtr_dlist );
416 363 : for( ulong i = 0UL; i < hfork->max; i++ ) {
417 336 : hfork->blk_pool[i].bhm_dlist = bhm_dlist_join( hfork->blk_pool[i].bhm_dlist );
418 336 : }
419 93 : for( ulong i = 0UL; i < hfork->vtr_max; i++ ) {
420 66 : hfork->vtr_pool[i].vte_dlist = vte_dlist_join( hfork->vtr_pool[i].vte_dlist );
421 66 : }
422 :
423 27 : return hfork;
424 27 : }
425 :
426 : void *
427 27 : fd_hfork_leave( fd_hfork_t const * hfork ) {
428 :
429 27 : if( FD_UNLIKELY( !hfork ) ) {
430 0 : FD_LOG_WARNING(( "NULL hfork" ));
431 0 : return NULL;
432 0 : }
433 :
434 27 : return (void *)hfork;
435 27 : }
436 :
437 : void *
438 27 : fd_hfork_delete( void * hfork ) {
439 :
440 27 : if( FD_UNLIKELY( !hfork ) ) {
441 0 : FD_LOG_WARNING(( "NULL hfork" ));
442 0 : return NULL;
443 0 : }
444 :
445 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)hfork, fd_hfork_align() ) ) ) {
446 0 : FD_LOG_WARNING(( "misaligned hfork" ));
447 0 : return NULL;
448 0 : }
449 :
450 27 : return hfork;
451 27 : }
452 :
453 : static blk_t *
454 : blk_insert( fd_hfork_t * hfork,
455 105 : fd_hash_t const * block_id ) {
456 105 : if( FD_UNLIKELY( !blk_pool_free( hfork->blk_pool ) ) ) {
457 9 : if( FD_UNLIKELY( blk_dlist_is_empty( hfork->blk_dlist, hfork->blk_pool ) ) ) return NULL;
458 6 : blk_t * evicted = blk_dlist_ele_pop_head( hfork->blk_dlist, hfork->blk_pool );
459 6 : blk_map_ele_remove_fast( hfork->blk_map, evicted, hfork->blk_pool );
460 6 : blk_pool_ele_release( hfork->blk_pool, evicted );
461 6 : }
462 102 : blk_t * blk = blk_pool_ele_acquire( hfork->blk_pool );
463 102 : blk->block_id = *block_id;
464 102 : blk->our_bank_hash = hash_null;
465 102 : blk->bhm_cnt = 0;
466 102 : blk_map_ele_insert( hfork->blk_map, blk, hfork->blk_pool );
467 102 : return blk;
468 105 : }
469 :
470 : int
471 : fd_hfork_count_vote( fd_hfork_t * hfork,
472 : fd_pubkey_t const * vote_acc,
473 : fd_hash_t const * block_id,
474 : fd_hash_t const * bank_hash,
475 : ulong slot,
476 : ulong stake,
477 78 : ulong total_stake ) {
478 :
479 : /* Get the vtr. If not in the voter set, ignore. */
480 :
481 78 : vtr_t * vtr = vtr_map_ele_query( hfork->vtr_map, vote_acc, NULL, hfork->vtr_pool );
482 78 : if( FD_UNLIKELY( !vtr ) ) return FD_HFORK_ERR_UNKNOWN_VTR;
483 :
484 : /* If voter already voted for this block_id, ignore. */
485 :
486 75 : bhm_key_t bhm_key = { .block_id = *block_id, .bank_hash = *bank_hash };
487 75 : vte_key_t vte_key = { .vote_acc = *vote_acc, .block_id = *block_id };
488 75 : if( FD_UNLIKELY( vte_map_ele_query_const( hfork->vte_map, &vte_key, NULL, hfork->vte_pool ) ) ) return FD_HFORK_ERR_ALREADY_VOTED;
489 :
490 : /* Only process newer votes (by vote slot) from a given voter. */
491 :
492 72 : if( FD_UNLIKELY( vtr->vte_cnt && vte_dlist_ele_peek_tail_const( vtr->vte_dlist, hfork->vte_pool )->slot >= slot ) ) return FD_HFORK_ERR_VOTE_TOO_OLD;
493 :
494 : /* Zero-stake votes don't contribute to hard fork detection. */
495 :
496 69 : if( FD_UNLIKELY( !stake ) ) return FD_HFORK_SUCCESS;
497 :
498 : /* If voter has reached their quota, evict their oldest vote. */
499 :
500 69 : if( FD_UNLIKELY( vtr->vte_cnt==hfork->per_vtr_max ) ) {
501 9 : vte_t * evicted_vte = vte_dlist_ele_pop_head( vtr->vte_dlist, hfork->vte_pool );
502 9 : bhm_key_t evicted_bhm_key = { .block_id = evicted_vte->key.block_id, .bank_hash = evicted_vte->bank_hash };
503 9 : ulong evicted_stake = evicted_vte->stake;
504 9 : vte_map_ele_remove_fast( hfork->vte_map, evicted_vte, hfork->vte_pool );
505 9 : vte_pool_ele_release( hfork->vte_pool, evicted_vte );
506 9 : vtr->vte_cnt--;
507 :
508 9 : bhm_t * bhm = bhm_map_ele_query( hfork->bhm_map, &evicted_bhm_key, NULL, hfork->bhm_pool );
509 9 : bhm->stake -= evicted_stake;
510 9 : if( FD_UNLIKELY( !bhm->stake ) ) bhm_remove( hfork, bhm );
511 9 : }
512 :
513 : /* Upsert the blk. */
514 :
515 69 : blk_t * blk = blk_map_ele_query( hfork->blk_map, block_id, NULL, hfork->blk_pool );
516 69 : if ( FD_UNLIKELY( !blk ) ) blk = blk_insert( hfork, block_id );
517 27 : else if( FD_UNLIKELY( !blk->bhm_cnt ) ) blk_dlist_ele_remove( hfork->blk_dlist, blk, hfork->blk_pool ); /* record_our_bank_hash before any count_vote */
518 :
519 : /* Upsert the bhm. */
520 :
521 69 : bhm_t * bhm = bhm_map_ele_query( hfork->bhm_map, &bhm_key, NULL, hfork->bhm_pool );
522 69 : if( FD_UNLIKELY( !bhm ) ) {
523 60 : bhm = bhm_pool_ele_acquire( hfork->bhm_pool );
524 60 : bhm->key = bhm_key;
525 60 : bhm->slot = slot;
526 60 : bhm->stake = 0UL;
527 60 : bhm_map_ele_insert( hfork->bhm_map, bhm, hfork->bhm_pool );
528 60 : bhm_dlist_ele_push_tail( blk->bhm_dlist, bhm, hfork->bhm_pool );
529 60 : blk->bhm_cnt++;
530 60 : }
531 69 : bhm->stake += stake;
532 69 : bhm_dlist_ele_remove( blk->bhm_dlist, bhm, hfork->bhm_pool );
533 69 : bhm_dlist_ele_push_tail( blk->bhm_dlist, bhm, hfork->bhm_pool );
534 :
535 : /* Push the vte onto the vtr. */
536 :
537 69 : vte_t * vte = vte_pool_ele_acquire( hfork->vte_pool );
538 69 : vte->key = vte_key;
539 69 : vte->bank_hash = *bank_hash;
540 69 : vte->slot = slot;
541 69 : vte->stake = stake;
542 69 : vte_map_ele_insert( hfork->vte_map, vte, hfork->vte_pool );
543 69 : vte_dlist_ele_push_tail( vtr->vte_dlist, vte, hfork->vte_pool );
544 69 : vtr->vte_cnt++;
545 :
546 : /* Check for hard forks. */
547 :
548 69 : return compare( blk, bhm, total_stake );
549 69 : }
550 :
551 : int
552 : fd_hfork_record_our_bank_hash( fd_hfork_t * hfork,
553 : fd_hash_t const * block_id,
554 : fd_hash_t const * bank_hash,
555 69 : ulong total_stake ) {
556 :
557 69 : blk_t * blk = blk_map_ele_query( hfork->blk_map, block_id, NULL, hfork->blk_pool );
558 69 : if( FD_LIKELY( !blk ) ) {
559 63 : blk = blk_insert( hfork, block_id );
560 63 : if( FD_UNLIKELY( !blk ) ) return 0;
561 60 : blk_dlist_ele_push_tail( hfork->blk_dlist, blk, hfork->blk_pool );
562 60 : }
563 66 : blk->our_bank_hash = *fd_ptr_if( !!bank_hash, bank_hash, &hash_invalid );
564 :
565 : /* Check all bhm entries for this block_id. */
566 :
567 66 : for( bhm_dlist_iter_t iter = bhm_dlist_iter_fwd_init( blk->bhm_dlist, hfork->bhm_pool );
568 69 : !bhm_dlist_iter_done( iter, blk->bhm_dlist, hfork->bhm_pool );
569 66 : iter = bhm_dlist_iter_fwd_next( iter, blk->bhm_dlist, hfork->bhm_pool ) ) {
570 6 : bhm_t * bhm = bhm_dlist_iter_ele( iter, blk->bhm_dlist, hfork->bhm_pool );
571 6 : int cmp = compare( blk, bhm, total_stake );
572 6 : if( cmp ) return cmp;
573 6 : }
574 63 : return 0;
575 66 : }
576 :
577 : void
578 : fd_hfork_update_voters( fd_hfork_t * hfork,
579 : fd_pubkey_t const * vote_accs,
580 21 : ulong cnt ) {
581 :
582 21 : for( vtr_dlist_iter_t iter = vtr_dlist_iter_fwd_init( hfork->vtr_dlist, hfork->vtr_pool );
583 42 : !vtr_dlist_iter_done( iter, hfork->vtr_dlist, hfork->vtr_pool );
584 21 : iter = vtr_dlist_iter_fwd_next( iter, hfork->vtr_dlist, hfork->vtr_pool ) ) {
585 21 : hfork->vtr_pool[iter].next = 1; /* mark for removal */
586 21 : }
587 :
588 : /* First pass: unmark kept voters from being released. */
589 :
590 42 : for( ulong i=0UL; i<cnt; i++ ) {
591 21 : fd_pubkey_t const * vote_acc = &vote_accs[i];
592 21 : vtr_t * vtr = vtr_map_ele_query( hfork->vtr_map, vote_acc, NULL, hfork->vtr_pool );
593 21 : if( FD_LIKELY( vtr ) ) {
594 9 : vtr_dlist_ele_remove( hfork->vtr_dlist, vtr, hfork->vtr_pool );
595 9 : vtr->next = 0; /* unmark for removal */
596 9 : vtr_dlist_ele_push_tail( hfork->vtr_dlist, vtr, hfork->vtr_pool );
597 9 : }
598 21 : }
599 :
600 : /* Pop and release marked voters until the first unmarked voter. */
601 :
602 33 : while( FD_LIKELY( !vtr_dlist_is_empty( hfork->vtr_dlist, hfork->vtr_pool ) ) ) {
603 18 : vtr_t * vtr = vtr_dlist_ele_pop_head( hfork->vtr_dlist, hfork->vtr_pool );
604 18 : if( FD_UNLIKELY( !vtr->next ) ) { /* can short-circuit since all the existing and new voters were appended */
605 6 : vtr_dlist_ele_push_tail( hfork->vtr_dlist, vtr, hfork->vtr_pool );
606 6 : break;
607 6 : }
608 21 : while( FD_LIKELY( !vte_dlist_is_empty( vtr->vte_dlist, hfork->vte_pool ) ) ) {
609 9 : vte_t * vte = vte_dlist_ele_pop_head( vtr->vte_dlist, hfork->vte_pool );
610 9 : vte_map_ele_remove_fast( hfork->vte_map, vte, hfork->vte_pool );
611 :
612 9 : bhm_key_t vte_xid = { .block_id = vte->key.block_id, .bank_hash = vte->bank_hash };
613 9 : bhm_t * bhm = bhm_map_ele_query( hfork->bhm_map, &vte_xid, NULL, hfork->bhm_pool );
614 9 : if( FD_LIKELY( bhm ) ) {
615 9 : bhm->stake -= vte->stake;
616 9 : if( FD_UNLIKELY( !bhm->stake ) ) bhm_remove( hfork, bhm );
617 9 : }
618 :
619 9 : vte_pool_ele_release( hfork->vte_pool, vte );
620 9 : }
621 12 : vtr_map_ele_remove_fast( hfork->vtr_map, vtr, hfork->vtr_pool );
622 12 : vtr_pool_ele_release( hfork->vtr_pool, vtr );
623 12 : }
624 :
625 : /* Second pass: acquire and insert new voters. */
626 :
627 42 : for( ulong i=0UL; i<cnt; i++ ) {
628 21 : fd_pubkey_t const * vote_acc = &vote_accs[i];
629 21 : if( FD_LIKELY( vtr_map_ele_query( hfork->vtr_map, vote_acc, NULL, hfork->vtr_pool ) ) ) continue;
630 12 : vtr_t * vtr = vtr_pool_ele_acquire( hfork->vtr_pool );
631 12 : vtr->vote_acc = *vote_acc;
632 12 : vtr->vte_cnt = 0;
633 12 : vtr->next = 0;
634 12 : vtr_map_ele_insert( hfork->vtr_map, vtr, hfork->vtr_pool );
635 12 : vtr_dlist_ele_push_tail( hfork->vtr_dlist, vtr, hfork->vtr_pool );
636 12 : }
637 21 : }
|
