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