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 0 : #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 0 : #define MAP_ELE_T blk_t
68 : #define MAP_KEY_T fd_votes_blk_key_t
69 0 : #define MAP_KEY key
70 0 : #define MAP_PREV map.prev
71 0 : #define MAP_NEXT map.next
72 0 : #define MAP_IDX_T uint
73 0 : #define MAP_KEY_EQ(k0,k1) ((k0)->slot==(k1)->slot && !memcmp((k0)->block_id.key,(k1)->block_id.key,32UL))
74 0 : #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 0 : #define DLIST_PREV dlist.prev
81 0 : #define DLIST_NEXT dlist.next
82 : #define DLIST_IDX_T uint
83 : #include "../../util/tmpl/fd_dlist.c"
84 :
85 : struct fd_votes_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 fd_votes_vtr vtr_t;
99 :
100 : #define POOL_NAME vtr_pool
101 : #define POOL_LAZY 1
102 0 : #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 0 : #define MAP_ELE_T vtr_t
108 : #define MAP_KEY_T fd_pubkey_t
109 0 : #define MAP_KEY vote_acc
110 0 : #define MAP_PREV map.prev
111 0 : #define MAP_NEXT map.next
112 0 : #define MAP_IDX_T uint
113 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->key,(k1)->key,sizeof(fd_pubkey_t)))
114 0 : #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 0 : #define DLIST_PREV dlist.prev
121 0 : #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 0 : #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 0 : #define MAP_ELE_T slot_t
150 : #define MAP_KEY_T ulong
151 0 : #define MAP_KEY slot
152 0 : #define MAP_PREV map.prev
153 0 : #define MAP_NEXT map.next
154 0 : #define MAP_IDX_T uint
155 0 : #define MAP_KEY_EQ(k0,k1) (*(k0)==*(k1))
156 0 : #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 0 : #define DLIST_PREV dlist.prev
163 0 : #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 0 : ulong vtr_max ) {
186 0 : if( FD_UNLIKELY( !slot_max || !vtr_max ) ) return 0UL;
187 0 : slot_max = fd_ulong_pow2_up( slot_max );
188 0 : vtr_max = fd_ulong_pow2_up( vtr_max );
189 0 : if( FD_UNLIKELY( !slot_max || !vtr_max || slot_max>UINT_MAX/vtr_max ) ) return 0UL;
190 0 : ulong blk_max = fd_ulong_pow2_up( slot_max*vtr_max );
191 0 : return fd_ulong_if( blk_max<=UINT_MAX, blk_max, 0UL );
192 0 : }
193 :
194 : ulong
195 0 : fd_votes_align( void ) {
196 0 : return 128UL;
197 0 : }
198 :
199 : ulong
200 : fd_votes_footprint( ulong slot_max,
201 0 : ulong vtr_max ) {
202 :
203 0 : ulong blk_max = fd_votes_blk_max( slot_max, vtr_max );
204 0 : if( FD_UNLIKELY( !blk_max ) ) return 0UL;
205 0 : slot_max = fd_ulong_pow2_up( slot_max );
206 0 : vtr_max = fd_ulong_pow2_up( vtr_max );
207 :
208 0 : ulong l = FD_LAYOUT_INIT;
209 0 : l = FD_LAYOUT_APPEND( l, 128UL, sizeof(fd_votes_t) );
210 0 : l = FD_LAYOUT_APPEND( l, slot_pool_align(), slot_pool_footprint( slot_max ) );
211 0 : l = FD_LAYOUT_APPEND( l, slot_map_align(), slot_map_footprint( slot_map_chain_cnt_est( slot_max ) ) );
212 0 : l = FD_LAYOUT_APPEND( l, slot_dlist_align(), slot_dlist_footprint() );
213 0 : l = FD_LAYOUT_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
214 0 : l = FD_LAYOUT_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( blk_max ) ) );
215 0 : l = FD_LAYOUT_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
216 0 : l = FD_LAYOUT_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
217 0 : l = FD_LAYOUT_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
218 0 : l = FD_LAYOUT_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
219 0 : for( ulong i = 0UL; i < slot_max; i++ ) {
220 0 : l = FD_LAYOUT_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
221 0 : l = FD_LAYOUT_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
222 0 : }
223 0 : return FD_LAYOUT_FINI( l, fd_votes_align() );
224 0 : }
225 :
226 : void *
227 : fd_votes_new( void * shmem,
228 : ulong slot_max,
229 : ulong vtr_max,
230 0 : ulong seed ) {
231 :
232 0 : if( FD_UNLIKELY( !shmem ) ) {
233 0 : FD_LOG_WARNING(( "NULL mem" ));
234 0 : return NULL;
235 0 : }
236 :
237 0 : 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 0 : ulong footprint = fd_votes_footprint( slot_max, vtr_max );
243 0 : 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 0 : slot_max = fd_ulong_pow2_up( slot_max );
249 0 : vtr_max = fd_ulong_pow2_up( vtr_max );
250 0 : ulong blk_max = fd_votes_blk_max( slot_max, vtr_max );
251 :
252 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
253 0 : fd_votes_t * votes = FD_SCRATCH_ALLOC_APPEND( l, 128UL, sizeof(fd_votes_t) );
254 0 : void * slot_pool = FD_SCRATCH_ALLOC_APPEND( l, slot_pool_align(), slot_pool_footprint( slot_max ) );
255 0 : void * slot_map = FD_SCRATCH_ALLOC_APPEND( l, slot_map_align(), slot_map_footprint( slot_map_chain_cnt_est( slot_max ) ) );
256 0 : void * slot_dlist = FD_SCRATCH_ALLOC_APPEND( l, slot_dlist_align(), slot_dlist_footprint() );
257 0 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
258 0 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint( blk_map_chain_cnt_est( blk_max ) ) );
259 0 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
260 0 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
261 0 : void * vtr_dlist = FD_SCRATCH_ALLOC_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
262 0 : void * vtr_set = FD_SCRATCH_ALLOC_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
263 :
264 0 : votes->root = ULONG_MAX;
265 0 : votes->slot_max = slot_max;
266 0 : votes->vtr_max = vtr_max;
267 0 : votes->blk_max = blk_max;
268 0 : votes->slot_pool = slot_pool_new ( slot_pool, slot_max );
269 0 : votes->slot_map = slot_map_new ( slot_map, slot_map_chain_cnt_est( slot_max ), seed );
270 0 : votes->slot_dlist = slot_dlist_new( slot_dlist );
271 0 : votes->blk_pool = blk_pool_new ( blk_pool, blk_max );
272 0 : votes->blk_map = blk_map_new ( blk_map, blk_map_chain_cnt_est( blk_max ), seed );
273 0 : votes->vtr_pool = vtr_pool_new ( vtr_pool, vtr_max );
274 0 : votes->vtr_map = vtr_map_new ( vtr_map, vtr_map_chain_cnt_est( vtr_max ), seed );
275 0 : votes->vtr_dlist = vtr_dlist_new ( vtr_dlist );
276 0 : 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 0 : slot_t * slot_join = slot_pool_join( votes->slot_pool );
281 0 : for( ulong i = 0UL; i < slot_max; i++ ) {
282 0 : void * vtrs = FD_SCRATCH_ALLOC_APPEND( l, slot_vtrs_align(), slot_vtrs_footprint( vtr_max ) );
283 0 : void * blk_dlist = FD_SCRATCH_ALLOC_APPEND( l, blk_dlist_align(), blk_dlist_footprint() );
284 0 : slot_join[i].vtrs = slot_vtrs_new( vtrs, vtr_max );
285 0 : slot_join[i].blks = blk_dlist_new( blk_dlist );
286 0 : slot_join[i].blk_cnt = 0;
287 0 : }
288 0 : slot_pool_leave( slot_join );
289 :
290 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_votes_align() ) == (ulong)shmem + footprint );
291 0 : return shmem;
292 0 : }
293 :
294 : fd_votes_t *
295 0 : fd_votes_join( void * shvotes ) {
296 0 : fd_votes_t * votes = (fd_votes_t *)shvotes;
297 :
298 0 : if( FD_UNLIKELY( !votes ) ) {
299 0 : FD_LOG_WARNING(( "NULL votes" ));
300 0 : return NULL;
301 0 : }
302 :
303 0 : 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 0 : votes->slot_pool = slot_pool_join ( votes->slot_pool );
309 0 : votes->slot_map = slot_map_join ( votes->slot_map );
310 0 : votes->slot_dlist = slot_dlist_join( votes->slot_dlist );
311 0 : votes->blk_pool = blk_pool_join ( votes->blk_pool );
312 0 : votes->blk_map = blk_map_join ( votes->blk_map );
313 0 : votes->vtr_pool = vtr_pool_join ( votes->vtr_pool );
314 0 : votes->vtr_map = vtr_map_join ( votes->vtr_map );
315 0 : votes->vtr_dlist = vtr_dlist_join ( votes->vtr_dlist );
316 0 : votes->vtr_set = slot_vtrs_join ( votes->vtr_set );
317 :
318 : /* Re-join vtrs sets and blk_dlists per slot pool position. */
319 :
320 0 : for( ulong i = 0UL; i < votes->slot_max; i++ ) {
321 0 : votes->slot_pool[i].vtrs = slot_vtrs_join( votes->slot_pool[i].vtrs );
322 0 : votes->slot_pool[i].blks = blk_dlist_join( votes->slot_pool[i].blks );
323 0 : }
324 :
325 0 : return votes;
326 0 : }
327 :
328 : void *
329 0 : fd_votes_leave( fd_votes_t const * votes ) {
330 :
331 0 : if( FD_UNLIKELY( !votes ) ) {
332 0 : FD_LOG_WARNING(( "NULL votes" ));
333 0 : return NULL;
334 0 : }
335 :
336 0 : return (void *)votes;
337 0 : }
338 :
339 : void *
340 0 : fd_votes_delete( void * votes ) {
341 :
342 0 : if( FD_UNLIKELY( !votes ) ) {
343 0 : FD_LOG_WARNING(( "NULL votes" ));
344 0 : return NULL;
345 0 : }
346 :
347 0 : 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 0 : return votes;
353 0 : }
354 :
355 : fd_votes_vtr_t *
356 : fd_votes_vtr_query( fd_votes_t * votes,
357 0 : fd_pubkey_t const * vote_acc ) {
358 0 : return vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool );
359 0 : }
360 :
361 : int
362 : fd_votes_count_vote( fd_votes_t * votes,
363 : fd_pubkey_t const * vote_acc,
364 : ulong stake,
365 : ulong vote_slot,
366 0 : fd_hash_t const * vote_block_id ) {
367 : /* Bound check before the voter lookup, as before: a too-new vote
368 : never pays for the map query. */
369 0 : if( FD_UNLIKELY( vote_slot >= votes->root + votes->slot_max ) ) return FD_VOTES_ERR_VOTE_TOO_NEW;
370 0 : return fd_votes_count_vote_vtr( votes, fd_votes_vtr_query( votes, vote_acc ), stake, vote_slot, vote_block_id );
371 0 : }
372 :
373 : int
374 : fd_votes_count_vote_vtr( fd_votes_t * votes,
375 : fd_votes_vtr_t * vtr,
376 : ulong stake,
377 : ulong vote_slot,
378 0 : fd_hash_t const * vote_block_id ) {
379 :
380 0 : if( FD_UNLIKELY( vote_slot >= votes->root + votes->slot_max ) ) return FD_VOTES_ERR_VOTE_TOO_NEW;
381 0 : if( FD_UNLIKELY( !vtr ) ) return FD_VOTES_ERR_UNKNOWN_VTR;
382 :
383 : /* Check we haven't already counted the voter's stake for this slot.
384 : If a voter votes for multiple block ids for the same slot, we only
385 : count their first one. Honest voters never vote more than once for
386 : the same slot so the percentage of stake doing this should be small
387 : as only malicious voters would equivocate votes this way. */
388 :
389 0 : slot_t * slot = slot_map_ele_query( votes->slot_map, &vote_slot, NULL, votes->slot_pool );
390 0 : if( FD_UNLIKELY( !slot ) ) {
391 0 : slot = slot_pool_ele_acquire( votes->slot_pool );
392 0 : slot->slot = vote_slot;
393 0 : slot->blk_cnt = 0;
394 0 : slot_vtrs_null( slot->vtrs );
395 0 : slot_map_ele_insert( votes->slot_map, slot, votes->slot_pool );
396 0 : slot_dlist_ele_push_tail( votes->slot_dlist, slot, votes->slot_pool );
397 0 : }
398 0 : if( FD_UNLIKELY( slot_vtrs_test( slot->vtrs, vtr->bit ) ) ) return FD_VOTES_ERR_ALREADY_VOTED;
399 0 : slot_vtrs_insert( slot->vtrs, vtr->bit );
400 :
401 0 : fd_votes_blk_key_t blk_key = { .slot = vote_slot, .block_id = *vote_block_id };
402 0 : blk_t * blk = blk_map_ele_query( votes->blk_map, &blk_key, NULL, votes->blk_pool );
403 0 : if( FD_UNLIKELY( !blk ) ) {
404 0 : blk = blk_pool_ele_acquire( votes->blk_pool );
405 0 : blk->key = blk_key;
406 0 : blk->stake = 0;
407 0 : blk->flags = 0;
408 0 : blk_map_ele_insert( votes->blk_map, blk, votes->blk_pool );
409 0 : blk_dlist_ele_push_tail( slot->blks, blk, votes->blk_pool );
410 0 : slot->blk_cnt++;
411 0 : }
412 0 : blk->stake += stake;
413 0 : return FD_VOTES_SUCCESS;
414 0 : }
415 :
416 : fd_votes_blk_t *
417 : fd_votes_query( fd_votes_t * votes,
418 : ulong slot,
419 0 : fd_hash_t const * block_id ) {
420 :
421 0 : if( FD_LIKELY( block_id ) ) {
422 0 : fd_votes_blk_key_t key = { .slot = slot, .block_id = *block_id };
423 0 : return blk_map_ele_query( votes->blk_map, &key, NULL, votes->blk_pool );
424 0 : }
425 :
426 : /* NULL block_id: search all block_ids for this slot, return the one
427 : with the highest forward confirmation level. */
428 :
429 0 : slot_t * votes_slot = slot_map_ele_query( votes->slot_map, &slot, NULL, votes->slot_pool );
430 0 : if( FD_UNLIKELY( !votes_slot ) ) return NULL;
431 :
432 0 : blk_t * best = NULL;
433 0 : for( blk_dlist_iter_t iter = blk_dlist_iter_fwd_init( votes_slot->blks, votes->blk_pool );
434 0 : !blk_dlist_iter_done( iter, votes_slot->blks, votes->blk_pool );
435 0 : iter = blk_dlist_iter_fwd_next( iter, votes_slot->blks, votes->blk_pool ) ) {
436 0 : blk_t * blk = blk_dlist_iter_ele( iter, votes_slot->blks, votes->blk_pool );
437 0 : if( FD_UNLIKELY( ( blk->flags >> 4 ) > ( best ? best->flags >> 4 : 0 ) ) ) best = blk;
438 0 : }
439 0 : return best;
440 0 : }
441 :
442 : void
443 : fd_votes_publish( fd_votes_t * votes,
444 0 : ulong root ) {
445 0 : if( FD_UNLIKELY( votes->root==ULONG_MAX ) ) { votes->root = root; return; }
446 0 : for( ulong slot = votes->root; slot < root; slot++ ) {
447 0 : slot_t * votes_slot = slot_map_ele_query( votes->slot_map, &slot, NULL, votes->slot_pool );
448 0 : if( FD_LIKELY( votes_slot ) ) {
449 0 : while( FD_LIKELY( !blk_dlist_is_empty( votes_slot->blks, votes->blk_pool ) ) ) {
450 0 : blk_t * blk = blk_dlist_ele_pop_head( votes_slot->blks, votes->blk_pool );
451 0 : blk_map_ele_remove_fast( votes->blk_map, blk, votes->blk_pool );
452 0 : blk_pool_ele_release( votes->blk_pool, blk );
453 0 : }
454 0 : slot_dlist_ele_remove( votes->slot_dlist, votes_slot, votes->slot_pool );
455 0 : slot_map_ele_remove_fast( votes->slot_map, votes_slot, votes->slot_pool );
456 0 : slot_pool_ele_release( votes->slot_pool, votes_slot );
457 0 : }
458 0 : }
459 0 : votes->root = root;
460 0 : }
461 :
462 : void
463 : fd_votes_update_voters( fd_votes_t * votes,
464 : fd_pubkey_t const * vote_accs,
465 0 : ulong cnt ) {
466 :
467 : /* Mark all existing voters for removal. */
468 :
469 0 : for( vtr_dlist_iter_t iter = vtr_dlist_iter_fwd_init( votes->vtr_dlist, votes->vtr_pool );
470 0 : !vtr_dlist_iter_done( iter, votes->vtr_dlist, votes->vtr_pool );
471 0 : iter = vtr_dlist_iter_fwd_next( iter, votes->vtr_dlist, votes->vtr_pool ) ) {
472 0 : votes->vtr_pool[iter].next = 1; /* mark for removal */
473 0 : }
474 :
475 : /* First pass: unmark kept voters from being released. Build a set
476 : of kept old bit positions. Existing voters keep their old bit
477 : positions (no compaction). */
478 :
479 0 : slot_vtrs_null( votes->vtr_set );
480 :
481 0 : for( ulong i=0UL; i<cnt; i++ ) {
482 0 : fd_pubkey_t const * vote_acc = &vote_accs[i];
483 0 : vtr_t * vtr = vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool );
484 0 : if( FD_LIKELY( vtr ) ) {
485 0 : vtr_dlist_ele_remove( votes->vtr_dlist, vtr, votes->vtr_pool );
486 0 : slot_vtrs_insert( votes->vtr_set, vtr->bit );
487 0 : vtr->next = 0; /* unmark for removal */
488 0 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
489 0 : }
490 0 : }
491 :
492 : /* Pop and release marked voters until the first unmarked voter. */
493 :
494 0 : while( FD_LIKELY( !vtr_dlist_is_empty( votes->vtr_dlist, votes->vtr_pool ) ) ) {
495 0 : vtr_t * vtr = vtr_dlist_ele_pop_head( votes->vtr_dlist, votes->vtr_pool );
496 0 : if( FD_UNLIKELY( !vtr->next ) ) { /* can short-circuit since all the existing and new voters were appended */
497 0 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
498 0 : break;
499 0 : }
500 0 : vtr_map_ele_remove_fast( votes->vtr_map, vtr, votes->vtr_pool );
501 0 : vtr_pool_ele_release( votes->vtr_pool, vtr );
502 0 : }
503 :
504 : /* Clear removed voters' bits from all existing slots' vtrs by
505 : intersecting with the kept set. */
506 :
507 0 : for( slot_dlist_iter_t iter = slot_dlist_iter_fwd_init( votes->slot_dlist, votes->slot_pool );
508 0 : !slot_dlist_iter_done( iter, votes->slot_dlist, votes->slot_pool );
509 0 : iter = slot_dlist_iter_fwd_next( iter, votes->slot_dlist, votes->slot_pool ) ) {
510 0 : slot_t * votes_slot = &votes->slot_pool[iter];
511 0 : slot_vtrs_intersect( votes_slot->vtrs, votes_slot->vtrs, votes->vtr_set );
512 0 : }
513 :
514 : /* Second pass: acquire and insert new voters, assigning bit positions
515 : from freed positions. */
516 :
517 0 : ulong free_bit = 0;
518 0 : for( ulong i=0UL; i<cnt; i++ ) {
519 0 : fd_pubkey_t const * vote_acc = &vote_accs[i];
520 0 : if( FD_LIKELY( vtr_map_ele_query( votes->vtr_map, vote_acc, NULL, votes->vtr_pool ) ) ) continue;
521 0 : vtr_t * vtr = vtr_pool_ele_acquire( votes->vtr_pool );
522 0 : vtr->vote_acc = *vote_acc;
523 0 : vtr->next = 0;
524 0 : while( slot_vtrs_test( votes->vtr_set, free_bit ) ) free_bit++;
525 0 : vtr->bit = free_bit;
526 0 : slot_vtrs_insert( votes->vtr_set, free_bit );
527 0 : free_bit++;
528 0 : vtr_map_ele_insert( votes->vtr_map, vtr, votes->vtr_pool );
529 0 : vtr_dlist_ele_push_tail( votes->vtr_dlist, vtr, votes->vtr_pool );
530 0 : }
531 0 : }
|
