Line data Source code
1 : #include "fd_votes.h"
2 :
3 : /* fd_votes tracks blks, vtrs, and slots.
4 :
5 : blk_pool / blk_map (capacity blk_max = slot_max * vtr_max):
6 :
7 : Each blk tracks the aggregate stake voted for a particular block_id.
8 :
9 : vtr_pool / vtr_map / vtr_dlist / vtr_set (capacity vtr_max):
10 :
11 : Each vtr corresponds to a vote account address and has a bit position
12 : in the slot vtrs bitset. vtr entries are explicitly managed by
13 : fd_votes_update_voters when the epoch stake set changes.
14 : dlist of all active voters, used for mark-sweep in
15 : fd_votes_update_voters.
16 :
17 : slot_pool / slot_map / blk_dlist (capacity slot_max):
18 :
19 : Each slot corresponds to a slot and tracks which voters have voted
20 : for that slot and all the blks that are associated for that slot.
21 : Each slot also tracks all the blks associated with that slot in
22 : blk_dlist.
23 :
24 : slot_map vtr_map
25 : map[0] +--------------------+ map[0] +--------------------+
26 : | (slot_t) { | | (vtr_t) { |
27 : | .slot = 100, | | .vote_acc = X, |
28 : | .vtrs = ..., | | .bit = 0, |
29 : | .blk_dlist = ... | | } |
30 : | } | | |
31 : map[1] +--------------------+ map[1] +--------------------+
32 : | (slot_t) { | | (vtr_t) { |
33 : | .slot = 101, | | .vote_acc = Y, |
34 : | .vtrs = ..., | | .bit = 1, |
35 : | .blk_dlist = + | | } |
36 : | } | | | |
37 : +----------------|---+ +--------------------+
38 : |
39 : V
40 : blk_dlist
41 : +------------------+------------------+
42 : | (blk_t) { | (blk_t) { |
43 : | .block_id = A, | .block_id = B, |
44 : | .stake = 10, | .stake = 51, |
45 : | ... | ... |
46 : | } | } |
47 : +------------------+------------------+
48 :
49 : When a vote is counted, the voter's bit is set in the slot's vtrs
50 : bitset. If the voter already voted for this slot (bit already set),
51 : the vote is ignored. The vote's stake is added to both the slot's
52 : aggregate stake and the blk's stake. blk entries are also in the
53 : global blk_map for O(1) lookup by block_id. */
54 :
55 : typedef fd_votes_blk_t blk_t;
56 :
57 : #define POOL_NAME blk_pool
58 : #define POOL_LAZY 1
59 24 : #define POOL_T blk_t
60 : #define POOL_IDX_T uint
61 : #include "../../util/tmpl/fd_pool.c"
62 :
63 : #define MAP_NAME blk_map
64 102 : #define MAP_ELE_T blk_t
65 : #define MAP_KEY_T fd_votes_blk_key_t
66 141 : #define MAP_KEY key
67 522 : #define MAP_PREV map.prev
68 5088 : #define MAP_NEXT map.next
69 1539 : #define MAP_IDX_T uint
70 5022 : #define MAP_KEY_EQ(k0,k1) ((k0)->slot==(k1)->slot && !memcmp((k0)->block_id.key,(k1)->block_id.key,32UL))
71 837 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->block_id.ul[1]^(key)->slot^(seed)))
72 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
73 : #include "../../util/tmpl/fd_map_chain.c"
74 :
75 : #define DLIST_NAME blk_dlist
76 : #define DLIST_ELE_T blk_t
77 135 : #define DLIST_PREV dlist.prev
78 237 : #define DLIST_NEXT dlist.next
79 : #define DLIST_IDX_T uint
80 : #include "../../util/tmpl/fd_dlist.c"
81 :
82 : struct vtr {
83 : fd_pubkey_t vote_acc; /* vtr_map key */
84 : uint next; /* pool next */
85 : struct {
86 : uint prev;
87 : uint next;
88 : } map;
89 : struct {
90 : uint prev;
91 : uint next;
92 : } dlist;
93 : ulong bit;
94 : };
95 : typedef struct vtr vtr_t;
96 :
97 : #define POOL_NAME vtr_pool
98 : #define POOL_LAZY 1
99 24 : #define POOL_T vtr_t
100 : #define POOL_IDX_T uint
101 : #include "../../util/tmpl/fd_pool.c"
102 :
103 : #define MAP_NAME vtr_map
104 9 : #define MAP_ELE_T vtr_t
105 : #define MAP_KEY_T fd_pubkey_t
106 261 : #define MAP_KEY vote_acc
107 1491 : #define MAP_PREV map.prev
108 16968 : #define MAP_NEXT map.next
109 1095 : #define MAP_IDX_T uint
110 16221 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->key,(k1)->key,sizeof(fd_pubkey_t)))
111 675 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->ul[1]^(seed)))
112 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
113 : #include "../../util/tmpl/fd_map_chain.c"
114 :
115 : #define DLIST_NAME vtr_dlist
116 : #define DLIST_ELE_T vtr_t
117 279 : #define DLIST_PREV dlist.prev
118 312 : #define DLIST_NEXT dlist.next
119 : #define DLIST_IDX_T uint
120 : #include "../../util/tmpl/fd_dlist.c"
121 :
122 : struct slot {
123 : ulong slot; /* map key, vote slot */
124 : uint next; /* pool next */
125 : struct {
126 : uint prev;
127 : uint next;
128 : } map;
129 : struct {
130 : uint prev;
131 : uint next;
132 : } dlist;
133 : blk_dlist_t * blks;
134 : ulong blk_cnt; /* number of distinct block ids for this slot */
135 : slot_vtrs_t * vtrs; /* who has voted for this slot, curr epoch */
136 : };
137 : typedef struct slot slot_t;
138 :
139 : #define POOL_NAME slot_pool
140 : #define POOL_LAZY 1
141 36 : #define POOL_T slot_t
142 : #define POOL_IDX_T uint
143 : #include "../../util/tmpl/fd_pool.c"
144 :
145 : #define MAP_NAME slot_map
146 6 : #define MAP_ELE_T slot_t
147 : #define MAP_KEY_T ulong
148 42 : #define MAP_KEY slot
149 45 : #define MAP_PREV map.prev
150 51 : #define MAP_NEXT map.next
151 786 : #define MAP_IDX_T uint
152 336 : #define MAP_KEY_EQ(k0,k1) (*(k0)==*(k1))
153 411 : #define MAP_KEY_HASH(key,seed) ((*key)^(seed))
154 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
155 : #include "../../util/tmpl/fd_map_chain.c"
156 :
157 : #define DLIST_NAME slot_dlist
158 : #define DLIST_ELE_T slot_t
159 42 : #define DLIST_PREV dlist.prev
160 57 : #define DLIST_NEXT dlist.next
161 : #define DLIST_IDX_T uint
162 : #include "../../util/tmpl/fd_dlist.c"
163 :
164 : struct __attribute__((aligned(128UL))) fd_votes {
165 : ulong root;
166 : ulong slot_max;
167 : ulong vtr_max;
168 : ulong blk_max;
169 : slot_t * slot_pool;
170 : slot_map_t * slot_map;
171 : slot_dlist_t * slot_dlist;
172 : blk_t * blk_pool;
173 : blk_map_t * blk_map;
174 : vtr_t * vtr_pool;
175 : vtr_map_t * vtr_map;
176 : vtr_dlist_t * vtr_dlist;
177 : slot_vtrs_t * vtr_set;
178 : };
179 :
180 : FD_FN_CONST static inline ulong
181 : fd_votes_blk_max( ulong slot_max,
182 39 : ulong vtr_max ) {
183 39 : if( FD_UNLIKELY( !slot_max || !vtr_max ) ) return 0UL;
184 39 : slot_max = fd_ulong_pow2_up( slot_max );
185 39 : vtr_max = fd_ulong_pow2_up( vtr_max );
186 39 : if( FD_UNLIKELY( !slot_max || !vtr_max || slot_max>UINT_MAX/vtr_max ) ) return 0UL;
187 36 : ulong blk_max = fd_ulong_pow2_up( slot_max*vtr_max );
188 36 : return fd_ulong_if( blk_max<=UINT_MAX, blk_max, 0UL );
189 39 : }
190 :
191 : ulong
192 108 : fd_votes_align( void ) {
193 108 : return 128UL;
194 108 : }
195 :
196 : ulong
197 : fd_votes_footprint( ulong slot_max,
198 27 : ulong vtr_max ) {
199 :
200 27 : ulong blk_max = fd_votes_blk_max( slot_max, vtr_max );
201 27 : if( FD_UNLIKELY( !blk_max ) ) return 0UL;
202 24 : slot_max = fd_ulong_pow2_up( slot_max );
203 24 : vtr_max = fd_ulong_pow2_up( vtr_max );
204 :
205 24 : ulong l = FD_LAYOUT_INIT;
206 24 : l = FD_LAYOUT_APPEND( l, 128UL, sizeof(fd_votes_t) );
207 24 : l = FD_LAYOUT_APPEND( l, slot_pool_align(), slot_pool_footprint( slot_max ) );
208 24 : l = FD_LAYOUT_APPEND( l, slot_map_align(), slot_map_footprint( slot_map_chain_cnt_est( slot_max ) ) );
209 24 : l = FD_LAYOUT_APPEND( l, slot_dlist_align(), slot_dlist_footprint() );
210 24 : l = FD_LAYOUT_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
211 24 : l = FD_LAYOUT_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( blk_max ) ) );
212 24 : l = FD_LAYOUT_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
213 24 : l = FD_LAYOUT_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
214 24 : l = FD_LAYOUT_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
215 24 : l = FD_LAYOUT_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
216 216 : for( ulong i = 0UL; i < slot_max; i++ ) {
217 192 : l = FD_LAYOUT_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
218 192 : l = FD_LAYOUT_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
219 192 : }
220 24 : return FD_LAYOUT_FINI( l, fd_votes_align() );
221 27 : }
222 :
223 : void *
224 : fd_votes_new( void * shmem,
225 : ulong slot_max,
226 : ulong vtr_max,
227 12 : ulong seed ) {
228 :
229 12 : if( FD_UNLIKELY( !shmem ) ) {
230 0 : FD_LOG_WARNING(( "NULL mem" ));
231 0 : return NULL;
232 0 : }
233 :
234 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_votes_align() ) ) ) {
235 0 : FD_LOG_WARNING(( "misaligned mem" ));
236 0 : return NULL;
237 0 : }
238 :
239 12 : ulong footprint = fd_votes_footprint( slot_max, vtr_max );
240 12 : if( FD_UNLIKELY( !footprint ) ) {
241 0 : FD_LOG_WARNING(( "bad slot_max (%lu) or vtr_max (%lu)", slot_max, vtr_max ));
242 0 : return NULL;
243 0 : }
244 :
245 12 : slot_max = fd_ulong_pow2_up( slot_max );
246 12 : vtr_max = fd_ulong_pow2_up( vtr_max );
247 12 : ulong blk_max = fd_votes_blk_max( slot_max, vtr_max );
248 :
249 12 : FD_SCRATCH_ALLOC_INIT( l, shmem );
250 12 : fd_votes_t * votes = FD_SCRATCH_ALLOC_APPEND( l, 128UL, sizeof(fd_votes_t) );
251 12 : void * slot_pool = FD_SCRATCH_ALLOC_APPEND( l, slot_pool_align(), slot_pool_footprint( slot_max ) );
252 12 : void * slot_map = FD_SCRATCH_ALLOC_APPEND( l, slot_map_align(), slot_map_footprint( slot_map_chain_cnt_est( slot_max ) ) );
253 12 : void * slot_dlist = FD_SCRATCH_ALLOC_APPEND( l, slot_dlist_align(), slot_dlist_footprint() );
254 12 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
255 12 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( blk_max ) ) );
256 12 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
257 12 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
258 12 : void * vtr_dlist = FD_SCRATCH_ALLOC_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
259 12 : void * vtr_set = FD_SCRATCH_ALLOC_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
260 :
261 12 : votes->root = ULONG_MAX;
262 12 : votes->slot_max = slot_max;
263 12 : votes->vtr_max = vtr_max;
264 12 : votes->blk_max = blk_max;
265 12 : votes->slot_pool = slot_pool_new ( slot_pool, slot_max );
266 12 : votes->slot_map = slot_map_new ( slot_map, slot_map_chain_cnt_est( slot_max ), seed );
267 12 : votes->slot_dlist = slot_dlist_new( slot_dlist );
268 12 : votes->blk_pool = blk_pool_new ( blk_pool, blk_max );
269 12 : votes->blk_map = blk_map_new ( blk_map, blk_map_chain_cnt_est( blk_max ), seed );
270 12 : votes->vtr_pool = vtr_pool_new ( vtr_pool, vtr_max );
271 12 : votes->vtr_map = vtr_map_new ( vtr_map, vtr_map_chain_cnt_est( vtr_max ), seed );
272 12 : votes->vtr_dlist = vtr_dlist_new ( vtr_dlist );
273 12 : votes->vtr_set = slot_vtrs_new ( vtr_set, vtr_max );
274 :
275 : /* Pre-allocate a vtrs set and blk_dlist per slot pool position. */
276 :
277 12 : slot_t * slot_join = slot_pool_join( votes->slot_pool );
278 108 : for( ulong i = 0UL; i < slot_max; i++ ) {
279 96 : void * vtrs = FD_SCRATCH_ALLOC_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
280 96 : void * blk_dlist = FD_SCRATCH_ALLOC_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
281 96 : slot_join[i].vtrs = slot_vtrs_new( vtrs, vtr_max );
282 96 : slot_join[i].blks = blk_dlist_new( blk_dlist );
283 96 : slot_join[i].blk_cnt = 0;
284 96 : }
285 12 : slot_pool_leave( slot_join );
286 :
287 12 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_votes_align() ) == (ulong)shmem + footprint );
288 12 : return shmem;
289 12 : }
290 :
291 : fd_votes_t *
292 12 : fd_votes_join( void * shvotes ) {
293 12 : fd_votes_t * votes = (fd_votes_t *)shvotes;
294 :
295 12 : if( FD_UNLIKELY( !votes ) ) {
296 0 : FD_LOG_WARNING(( "NULL votes" ));
297 0 : return NULL;
298 0 : }
299 :
300 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)votes, fd_votes_align() ) ) ) {
301 0 : FD_LOG_WARNING(( "misaligned votes" ));
302 0 : return NULL;
303 0 : }
304 :
305 12 : votes->slot_pool = slot_pool_join ( votes->slot_pool );
306 12 : votes->slot_map = slot_map_join ( votes->slot_map );
307 12 : votes->slot_dlist = slot_dlist_join( votes->slot_dlist );
308 12 : votes->blk_pool = blk_pool_join ( votes->blk_pool );
309 12 : votes->blk_map = blk_map_join ( votes->blk_map );
310 12 : votes->vtr_pool = vtr_pool_join ( votes->vtr_pool );
311 12 : votes->vtr_map = vtr_map_join ( votes->vtr_map );
312 12 : votes->vtr_dlist = vtr_dlist_join ( votes->vtr_dlist );
313 12 : votes->vtr_set = slot_vtrs_join ( votes->vtr_set );
314 :
315 : /* Re-join vtrs sets and blk_dlists per slot pool position. */
316 :
317 108 : for( ulong i = 0UL; i < votes->slot_max; i++ ) {
318 96 : votes->slot_pool[i].vtrs = slot_vtrs_join( votes->slot_pool[i].vtrs );
319 96 : votes->slot_pool[i].blks = blk_dlist_join( votes->slot_pool[i].blks );
320 96 : }
321 :
322 12 : return votes;
323 12 : }
324 :
325 : void *
326 12 : fd_votes_leave( fd_votes_t const * votes ) {
327 :
328 12 : if( FD_UNLIKELY( !votes ) ) {
329 0 : FD_LOG_WARNING(( "NULL votes" ));
330 0 : return NULL;
331 0 : }
332 :
333 12 : return (void *)votes;
334 12 : }
335 :
336 : void *
337 12 : fd_votes_delete( void * votes ) {
338 :
339 12 : if( FD_UNLIKELY( !votes ) ) {
340 0 : FD_LOG_WARNING(( "NULL votes" ));
341 0 : return NULL;
342 0 : }
343 :
344 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)votes, fd_votes_align() ) ) ) {
345 0 : FD_LOG_WARNING(( "misaligned votes" ));
346 0 : return NULL;
347 0 : }
348 :
349 12 : return votes;
350 12 : }
351 :
352 : int
353 : fd_votes_count_vote( fd_votes_t * votes,
354 : fd_pubkey_t const * vote_acc,
355 : ulong stake,
356 : ulong vote_slot,
357 390 : fd_hash_t const * vote_block_id ) {
358 :
359 390 : if( FD_UNLIKELY( vote_slot >= votes->root + votes->slot_max ) ) return FD_VOTES_ERR_VOTE_TOO_NEW;
360 :
361 363 : vtr_t * vtr = vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool );
362 363 : if( FD_UNLIKELY( !vtr ) ) return FD_VOTES_ERR_UNKNOWN_VTR;
363 :
364 : /* Check we haven't already counted the voter's stake for this slot.
365 : If a voter votes for multiple block ids for the same slot, we only
366 : count their first one. Honest voters never vote more than once for
367 : the same slot so the percentage of stake doing this should be small
368 : as only malicious voters would equivocate votes this way. */
369 :
370 357 : slot_t * slot = slot_map_ele_query( votes->slot_map, &vote_slot, NULL, votes->slot_pool );
371 357 : if( FD_UNLIKELY( !slot ) ) {
372 36 : slot = slot_pool_ele_acquire( votes->slot_pool );
373 36 : slot->slot = vote_slot;
374 36 : slot->blk_cnt = 0;
375 36 : slot_vtrs_null( slot->vtrs );
376 36 : slot_map_ele_insert( votes->slot_map, slot, votes->slot_pool );
377 36 : slot_dlist_ele_push_tail( votes->slot_dlist, slot, votes->slot_pool );
378 36 : }
379 357 : if( FD_UNLIKELY( slot_vtrs_test( slot->vtrs, vtr->bit ) ) ) return FD_VOTES_ERR_ALREADY_VOTED;
380 258 : slot_vtrs_insert( slot->vtrs, vtr->bit );
381 :
382 258 : fd_votes_blk_key_t blk_key = { .slot = vote_slot, .block_id = *vote_block_id };
383 258 : blk_t * blk = blk_map_ele_query( votes->blk_map, &blk_key, NULL, votes->blk_pool );
384 258 : if( FD_UNLIKELY( !blk ) ) {
385 135 : blk = blk_pool_ele_acquire( votes->blk_pool );
386 135 : blk->key = blk_key;
387 135 : blk->stake = 0;
388 135 : blk->flags = 0;
389 135 : blk_map_ele_insert( votes->blk_map, blk, votes->blk_pool );
390 135 : blk_dlist_ele_push_tail( slot->blks, blk, votes->blk_pool );
391 135 : slot->blk_cnt++;
392 135 : }
393 258 : blk->stake += stake;
394 258 : return FD_VOTES_SUCCESS;
395 357 : }
396 :
397 : fd_votes_blk_t *
398 : fd_votes_query( fd_votes_t * votes,
399 : ulong slot,
400 0 : fd_hash_t const * block_id ) {
401 :
402 0 : if( FD_LIKELY( block_id ) ) {
403 0 : fd_votes_blk_key_t key = { .slot = slot, .block_id = *block_id };
404 0 : return blk_map_ele_query( votes->blk_map, &key, NULL, votes->blk_pool );
405 0 : }
406 :
407 : /* NULL block_id: search all block_ids for this slot, return the one
408 : with the highest forward confirmation level. */
409 :
410 0 : slot_t * votes_slot = slot_map_ele_query( votes->slot_map, &slot, NULL, votes->slot_pool );
411 0 : if( FD_UNLIKELY( !votes_slot ) ) return NULL;
412 :
413 0 : blk_t * best = NULL;
414 0 : for( blk_dlist_iter_t iter = blk_dlist_iter_fwd_init( votes_slot->blks, votes->blk_pool );
415 0 : !blk_dlist_iter_done( iter, votes_slot->blks, votes->blk_pool );
416 0 : iter = blk_dlist_iter_fwd_next( iter, votes_slot->blks, votes->blk_pool ) ) {
417 0 : blk_t * blk = blk_dlist_iter_ele( iter, votes_slot->blks, votes->blk_pool );
418 0 : if( FD_UNLIKELY( ( blk->flags >> 4 ) > ( best ? best->flags >> 4 : 0 ) ) ) best = blk;
419 0 : }
420 0 : return best;
421 0 : }
422 :
423 : void
424 : fd_votes_publish( fd_votes_t * votes,
425 18 : ulong root ) {
426 18 : if( FD_UNLIKELY( votes->root==ULONG_MAX ) ) { votes->root = root; return; }
427 18 : for( ulong slot = votes->root; slot < root; slot++ ) {
428 12 : slot_t * votes_slot = slot_map_ele_query( votes->slot_map, &slot, NULL, votes->slot_pool );
429 12 : if( FD_LIKELY( votes_slot ) ) {
430 108 : while( FD_LIKELY( !blk_dlist_is_empty( votes_slot->blks, votes->blk_pool ) ) ) {
431 102 : blk_t * blk = blk_dlist_ele_pop_head( votes_slot->blks, votes->blk_pool );
432 102 : blk_map_ele_remove_fast( votes->blk_map, blk, votes->blk_pool );
433 102 : blk_pool_ele_release( votes->blk_pool, blk );
434 102 : }
435 6 : slot_dlist_ele_remove( votes->slot_dlist, votes_slot, votes->slot_pool );
436 6 : slot_map_ele_remove_fast( votes->slot_map, votes_slot, votes->slot_pool );
437 6 : slot_pool_ele_release( votes->slot_pool, votes_slot );
438 6 : }
439 12 : }
440 6 : votes->root = root;
441 6 : }
442 :
443 : void
444 : fd_votes_update_voters( fd_votes_t * votes,
445 : fd_pubkey_t const * vote_accs,
446 12 : ulong cnt ) {
447 :
448 : /* Mark all existing voters for removal. */
449 :
450 12 : for( vtr_dlist_iter_t iter = vtr_dlist_iter_fwd_init( votes->vtr_dlist, votes->vtr_pool );
451 30 : !vtr_dlist_iter_done( iter, votes->vtr_dlist, votes->vtr_pool );
452 18 : iter = vtr_dlist_iter_fwd_next( iter, votes->vtr_dlist, votes->vtr_pool ) ) {
453 18 : votes->vtr_pool[iter].next = 1; /* mark for removal */
454 18 : }
455 :
456 : /* First pass: unmark kept voters from being released. Build a set
457 : of kept old bit positions. Existing voters keep their old bit
458 : positions (no compaction). */
459 :
460 12 : slot_vtrs_null( votes->vtr_set );
461 :
462 30 : for( ulong i=0UL; i<cnt; i++ ) {
463 18 : fd_pubkey_t const * vote_acc = &vote_accs[i];
464 18 : vtr_t * vtr = vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool );
465 18 : if( FD_LIKELY( vtr ) ) {
466 9 : vtr_dlist_ele_remove( votes->vtr_dlist, vtr, votes->vtr_pool );
467 9 : slot_vtrs_insert( votes->vtr_set, vtr->bit );
468 9 : vtr->next = 0; /* unmark for removal */
469 9 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
470 9 : }
471 18 : }
472 :
473 : /* Pop and release marked voters until the first unmarked voter. */
474 :
475 21 : while( FD_LIKELY( !vtr_dlist_is_empty( votes->vtr_dlist, votes->vtr_pool ) ) ) {
476 15 : vtr_t * vtr = vtr_dlist_ele_pop_head( votes->vtr_dlist, votes->vtr_pool );
477 15 : if( FD_UNLIKELY( !vtr->next ) ) { /* can short-circuit since all the existing and new voters were appended */
478 6 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
479 6 : break;
480 6 : }
481 9 : vtr_map_ele_remove_fast( votes->vtr_map, vtr, votes->vtr_pool );
482 9 : vtr_pool_ele_release( votes->vtr_pool, vtr );
483 9 : }
484 :
485 : /* Clear removed voters' bits from all existing slots' vtrs by
486 : intersecting with the kept set. */
487 :
488 12 : for( slot_dlist_iter_t iter = slot_dlist_iter_fwd_init( votes->slot_dlist, votes->slot_pool );
489 27 : !slot_dlist_iter_done( iter, votes->slot_dlist, votes->slot_pool );
490 15 : iter = slot_dlist_iter_fwd_next( iter, votes->slot_dlist, votes->slot_pool ) ) {
491 15 : slot_t * votes_slot = &votes->slot_pool[iter];
492 15 : slot_vtrs_intersect( votes_slot->vtrs, votes_slot->vtrs, votes->vtr_set );
493 15 : }
494 :
495 : /* Second pass: acquire and insert new voters, assigning bit positions
496 : from freed positions. */
497 :
498 12 : ulong free_bit = 0;
499 30 : for( ulong i=0UL; i<cnt; i++ ) {
500 18 : fd_pubkey_t const * vote_acc = &vote_accs[i];
501 18 : if( FD_LIKELY( vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool ) ) ) continue;
502 9 : vtr_t * vtr = vtr_pool_ele_acquire( votes->vtr_pool );
503 9 : vtr->vote_acc = *vote_acc;
504 9 : vtr->next = 0;
505 9 : while( slot_vtrs_test( votes->vtr_set, free_bit ) ) free_bit++;
506 9 : vtr->bit = free_bit;
507 9 : slot_vtrs_insert( votes->vtr_set, free_bit );
508 9 : free_bit++;
509 9 : vtr_map_ele_insert( votes->vtr_map, vtr, votes->vtr_pool );
510 9 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
511 9 : }
512 12 : }
|
