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