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