Line data Source code
1 : #include "fd_eqvoc.h"
2 : #include "../fd_choreo_base.h"
3 : #include "../../ballet/shred/fd_shred.h"
4 : #include "../../disco/shred/fd_fec_set.h"
5 :
6 : /* fd_eqvoc maintains four bounded maps:
7 :
8 : dup_map (capacity dup_max): maps slot -> equivocation result,
9 : recording slots we've already verified are duplicates
10 : (equivocations). LRU-evicts when at capacity: querying an
11 : entry moves it to the tail of the recency list; when an
12 : insert is needed and the map is full, the head
13 : (least-recently-used) entry is evicted.
14 :
15 : fec_map (capacity fec_max): maps (slot, fec_set_idx) -> shred,
16 : storing the first shred seen in each FEC set so it can be
17 : compared against later siblings for equivocation. Same LRU
18 : eviction policy as dup_map. Entries are also explicitly
19 : removed when equivocation is confirmed (proof constructed).
20 :
21 : prf_map (capacity per_vtr_max * vtr_max): maps (slot, voter index)
22 : -> in-progress proof ("chunks") assembly state, tracking
23 : proofs per voter per slot. The voter index refers into
24 : vtr_pool; all of a voter's proofs are removed before that
25 : index is reused. Entries are LRU-evicted per voter when
26 : that voter's in-progress proof count reaches per_vtr_max.
27 : Entries are also removed when proof assembly completes (all
28 : chunks received), regardless of verification outcome, or
29 : when the corresponding voter is removed from vtr_map.
30 :
31 : vtr_map (capacity vtr_max): maps voter pubkey -> per-voter proof-
32 : assembly state. vtr entries are not evicted automatically;
33 : they are explicitly inserted and removed by
34 : fd_eqvoc_update_voters when the epoch stake set changes.
35 : Each vtr has a pre-allocated prf_dlist that tracks
36 : in-progress proofs for that voter. Each voter's in-progress
37 : proof count is bounded by per_vtr_max; when that limit is
38 : reached, the oldest proof for that voter is evicted.
39 :
40 : dup_map fec_map
41 : map[0] +--------------------+ map[0] +--------------------+
42 : | (dup_t) { | | (fec_t) { |
43 : | .slot = 1, | | .key = 5|0, |
44 : | ... | | ... |
45 : | } | | } |
46 : map[1] +--------------------+ map[1] +--------------------+
47 : | (dup_t) { | | (fec_t) { |
48 : | .slot = 2, | | .key = 6|0, |
49 : | ... | | ... |
50 : | } | | } |
51 : +--------------------+ +--------------------+
52 :
53 : vtr_map prf_map
54 : map[0] +--------------------+ map[0] +--------------------+
55 : | (vtr_t) { | | (prf_t) { |
56 : | .from = X, | | .key.slot = 5, |
57 : | ... | | .key.vtr_idx = 1,|<-----+
58 : | ... | | ... | |
59 : | } | | } | |
60 : map[1] +--------------------+ map[1] +--------------------+ |
61 : | (vtr_t) { | | (prf_t) { | |
62 : | .from = Y, | | .key.slot = 6, | |
63 : | ... | | .key.vtr_idx = 1,|<--+ |
64 : | .prf_dlist = + | | ... | | |
65 : | } | | | } | | |
66 : +----------------|---+ +--------------------+ | |
67 : | | |
68 : | | |
69 : | +------------------------+ |
70 : | | |
71 : V | +------------------+
72 : prf_dlist | |
73 : +---------+---------+---------+
74 : | (prf_t) | (prf_t) | (prf_t) |
75 : | ... | ... | ... |
76 : | } | } | } |
77 : +---------+---------+---------+
78 : oldest newest
79 :
80 : Each vtr_t owns a prf_dlist of in-progress proofs (prf_t).
81 : prf_t elements are also in the global prf_map for lookup by
82 : (slot, vtr_idx). When prf_dlist_cnt == per_vtr_max, the oldest
83 : prf is evicted from both prf_dlist and prf_map. */
84 :
85 : typedef struct {
86 : ulong slot;
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 : } dup_t;
97 :
98 : #define POOL_NAME dup_pool
99 : #define POOL_LAZY 1
100 156 : #define POOL_T dup_t
101 : #define POOL_IDX_T uint
102 : #include "../../util/tmpl/fd_pool.c"
103 :
104 : #define MAP_NAME dup_map
105 0 : #define MAP_ELE_T dup_t
106 60 : #define MAP_KEY slot
107 60 : #define MAP_PREV map.prev
108 60 : #define MAP_NEXT map.next
109 864 : #define MAP_IDX_T uint
110 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
111 : #include "../../util/tmpl/fd_map_chain.c"
112 :
113 : #define DLIST_NAME dup_dlist
114 : #define DLIST_ELE_T dup_t
115 180 : #define DLIST_PREV dlist.prev
116 180 : #define DLIST_NEXT dlist.next
117 : #define DLIST_IDX_T uint
118 : #include "../../util/tmpl/fd_dlist.c"
119 :
120 : typedef struct {
121 : ulong key; /* 32 bits = slot | 32 lsb = fec_set_idx */
122 : uint next; /* pool next */
123 : struct {
124 : uint prev;
125 : uint next;
126 : } map;
127 : struct {
128 : uint prev;
129 : uint next;
130 : } dlist;
131 : union {
132 : fd_shred_t sample_shred; /* highest shred seen so far, by index */
133 : uchar sample_bytes[FD_SHRED_MAX_SZ]; /* entire shred, both header and payload */
134 : };
135 : } fec_t;
136 :
137 : #define POOL_NAME fec_pool
138 : #define POOL_LAZY 1
139 156 : #define POOL_T fec_t
140 : #define POOL_IDX_T uint
141 : #include "../../util/tmpl/fd_pool.c"
142 :
143 : #define MAP_NAME fec_map
144 48 : #define MAP_ELE_T fec_t
145 168 : #define MAP_PREV map.prev
146 315 : #define MAP_NEXT map.next
147 336 : #define MAP_IDX_T uint
148 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
149 : #include "../../util/tmpl/fd_map_chain.c"
150 :
151 : #define DLIST_NAME fec_dlist
152 : #define DLIST_ELE_T fec_t
153 66 : #define DLIST_PREV dlist.prev
154 114 : #define DLIST_NEXT dlist.next
155 : #define DLIST_IDX_T uint
156 : #include "../../util/tmpl/fd_dlist.c"
157 :
158 : typedef struct {
159 : ulong slot;
160 : uint vtr_idx;
161 : } xid_t;
162 :
163 : struct prf {
164 : xid_t key;
165 : uint next;
166 : struct {
167 : uint prev;
168 : uint next;
169 : } map;
170 : struct {
171 : uint prev;
172 : uint next;
173 : } dlist;
174 : uchar chunk_cnt;
175 : uchar chunk_idx[ FD_EQVOC_CHUNK_CNT - 1 ];
176 : ushort chunk_len[ FD_EQVOC_CHUNK_CNT - 1 ];
177 : uchar chunks [ FD_EQVOC_CHUNK_CNT - 1 ][ FD_EQVOC_CHUNK_SZ ];
178 : };
179 : typedef struct prf prf_t;
180 :
181 : #define POOL_NAME prf_pool
182 : #define POOL_LAZY 1
183 156 : #define POOL_T prf_t
184 : #define POOL_IDX_T uint
185 : #include "../../util/tmpl/fd_pool.c"
186 :
187 : #define MAP_NAME prf_map
188 90 : #define MAP_ELE_T prf_t
189 : #define MAP_KEY_T xid_t
190 144 : #define MAP_PREV map.prev
191 240 : #define MAP_NEXT map.next
192 825 : #define MAP_IDX_T uint
193 201 : #define MAP_KEY_EQ(k0,k1) ((((k0)->slot)==((k1)->slot)) & (((k0)->vtr_idx)==((k1)->vtr_idx)))
194 519 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( ((key)->slot) ^ ((key)->vtr_idx) ^ (seed) )
195 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
196 : #include "../../util/tmpl/fd_map_chain.c"
197 :
198 : #define DLIST_NAME prf_dlist
199 : #define DLIST_ELE_T prf_t
200 495 : #define DLIST_PREV dlist.prev
201 519 : #define DLIST_NEXT dlist.next
202 : #define DLIST_IDX_T uint
203 : #include "../../util/tmpl/fd_dlist.c"
204 :
205 : struct vtr {
206 : fd_pubkey_t from;
207 : uint next; /* pool next; reused as kept flag during update_voters */
208 : struct {
209 : uint prev;
210 : uint next;
211 : } map;
212 : struct {
213 : uint prev;
214 : uint next;
215 : } dlist;
216 : ulong prf_dlist_cnt;
217 : prf_dlist_t * prf_dlist;
218 : };
219 : typedef struct vtr vtr_t;
220 :
221 : #define POOL_NAME vtr_pool
222 : #define POOL_LAZY 1
223 234 : #define POOL_T vtr_t
224 : #define POOL_IDX_T uint
225 : #include "../../util/tmpl/fd_pool.c"
226 :
227 : #define MAP_NAME vtr_map
228 15 : #define MAP_ELE_T vtr_t
229 : #define MAP_KEY_T fd_pubkey_t
230 96 : #define MAP_KEY from
231 303 : #define MAP_PREV map.prev
232 558 : #define MAP_NEXT map.next
233 1239 : #define MAP_IDX_T uint
234 639 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->key,(k1)->key,sizeof(fd_pubkey_t)))
235 630 : #define MAP_KEY_HASH(key,seed) ((ulong)((key)->ul[1]^(seed)))
236 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
237 : #include "../../util/tmpl/fd_map_chain.c"
238 :
239 : #define DLIST_NAME vtr_dlist
240 : #define DLIST_ELE_T vtr_t
241 153 : #define DLIST_PREV dlist.prev
242 219 : #define DLIST_NEXT dlist.next
243 : #define DLIST_IDX_T uint
244 : #include "../../util/tmpl/fd_dlist.c"
245 :
246 : struct fd_eqvoc {
247 :
248 : /* copy */
249 :
250 : ulong dup_max;
251 : ulong fec_max;
252 : ulong per_vtr_max;
253 : ulong vtr_max;
254 :
255 : /* owned */
256 :
257 : fd_sha512_t * sha512;
258 : void * bmtree_mem;
259 : dup_t * dup_pool;
260 : dup_map_t * dup_map;
261 : dup_dlist_t * dup_dlist;
262 : fec_t * fec_pool;
263 : fec_map_t * fec_map;
264 : fec_dlist_t * fec_dlist;
265 : prf_t * prf_pool;
266 : prf_map_t * prf_map;
267 : vtr_t * vtr_pool;
268 : vtr_map_t * vtr_map;
269 : vtr_dlist_t * vtr_dlist;
270 : };
271 : typedef struct fd_eqvoc fd_eqvoc_t;
272 :
273 : ulong
274 702 : fd_eqvoc_align( void ) {
275 702 : return 128UL;
276 702 : }
277 :
278 : ulong
279 : fd_eqvoc_footprint( ulong dup_max,
280 : ulong fec_max,
281 : ulong per_vtr_max,
282 165 : ulong vtr_max ) {
283 :
284 165 : dup_max = fd_ulong_pow2_up( dup_max );
285 165 : fec_max = fd_ulong_pow2_up( fec_max );
286 165 : per_vtr_max = fd_ulong_pow2_up( per_vtr_max );
287 165 : vtr_max = fd_ulong_pow2_up( vtr_max );
288 165 : if( FD_UNLIKELY( !dup_max || dup_max>UINT_MAX ||
289 165 : !fec_max || fec_max>UINT_MAX ||
290 165 : !per_vtr_max || !vtr_max || vtr_max>UINT_MAX ||
291 165 : per_vtr_max>UINT_MAX/vtr_max ) ) return 0UL;
292 156 : ulong prf_max = per_vtr_max * vtr_max;
293 :
294 156 : ulong l = FD_LAYOUT_INIT;
295 156 : l = FD_LAYOUT_APPEND( l, alignof(fd_eqvoc_t), sizeof(fd_eqvoc_t) );
296 156 : l = FD_LAYOUT_APPEND( l, fd_sha512_align(), fd_sha512_footprint() );
297 156 : l = FD_LAYOUT_APPEND( l, FD_BMTREE_COMMIT_ALIGN, FD_BMTREE_COMMIT_FOOTPRINT( FD_SHRED_MERKLE_LAYER_CNT ) );
298 156 : l = FD_LAYOUT_APPEND( l, dup_pool_align(), dup_pool_footprint( dup_max ) );
299 156 : l = FD_LAYOUT_APPEND( l, dup_map_align(), dup_map_footprint( dup_map_chain_cnt_est( dup_max ) ) );
300 156 : l = FD_LAYOUT_APPEND( l, dup_dlist_align(), dup_dlist_footprint() );
301 156 : l = FD_LAYOUT_APPEND( l, fec_pool_align(), fec_pool_footprint( fec_max ) );
302 156 : l = FD_LAYOUT_APPEND( l, fec_map_align(), fec_map_footprint( fec_map_chain_cnt_est( fec_max ) ) );
303 156 : l = FD_LAYOUT_APPEND( l, fec_dlist_align(), fec_dlist_footprint() );
304 156 : l = FD_LAYOUT_APPEND( l, prf_pool_align(), prf_pool_footprint( prf_max ) );
305 156 : l = FD_LAYOUT_APPEND( l, prf_map_align(), prf_map_footprint( prf_map_chain_cnt_est( prf_max ) ) );
306 156 : l = FD_LAYOUT_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
307 156 : l = FD_LAYOUT_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
308 156 : l = FD_LAYOUT_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
309 780 : for( ulong i = 0UL; i < vtr_max; i++ ) {
310 624 : l = FD_LAYOUT_APPEND( l, prf_dlist_align(), prf_dlist_footprint() );
311 624 : }
312 156 : return FD_LAYOUT_FINI( l, fd_eqvoc_align() );
313 165 : }
314 :
315 : void *
316 : fd_eqvoc_new( void * shmem,
317 : ulong dup_max,
318 : ulong fec_max,
319 : ulong per_vtr_max,
320 : ulong vtr_max,
321 78 : ulong seed ) {
322 :
323 78 : if( FD_UNLIKELY( !shmem ) ) {
324 0 : FD_LOG_WARNING(( "NULL mem" ));
325 0 : return NULL;
326 0 : }
327 :
328 78 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_eqvoc_align() ) ) ) {
329 0 : FD_LOG_WARNING(( "misaligned mem" ));
330 0 : return NULL;
331 0 : }
332 :
333 78 : ulong footprint = fd_eqvoc_footprint( dup_max, fec_max, per_vtr_max, vtr_max );
334 78 : if( FD_UNLIKELY( !footprint ) ) {
335 0 : FD_LOG_WARNING(( "bad dup_max (%lu), fec_max (%lu), or vtr_max (%lu)", dup_max, fec_max, vtr_max ));
336 0 : return NULL;
337 0 : }
338 :
339 78 : dup_max = fd_ulong_pow2_up( dup_max );
340 78 : fec_max = fd_ulong_pow2_up( fec_max );
341 78 : per_vtr_max = fd_ulong_pow2_up( per_vtr_max );
342 78 : vtr_max = fd_ulong_pow2_up( vtr_max );
343 78 : ulong prf_max = per_vtr_max * vtr_max;
344 :
345 78 : FD_SCRATCH_ALLOC_INIT( l, shmem );
346 78 : void * eqvoc_mem = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_eqvoc_t), sizeof(fd_eqvoc_t) );
347 78 : void * sha512 = FD_SCRATCH_ALLOC_APPEND( l, fd_sha512_align(), fd_sha512_footprint() );
348 78 : void * bmtree_mem = FD_SCRATCH_ALLOC_APPEND( l, FD_BMTREE_COMMIT_ALIGN, FD_BMTREE_COMMIT_FOOTPRINT( FD_SHRED_MERKLE_LAYER_CNT ) );
349 78 : void * dup_pool = FD_SCRATCH_ALLOC_APPEND( l, dup_pool_align(), dup_pool_footprint( dup_max ) );
350 78 : void * dup_map = FD_SCRATCH_ALLOC_APPEND( l, dup_map_align(), dup_map_footprint( dup_map_chain_cnt_est( dup_max ) ) );
351 78 : void * dup_dlist = FD_SCRATCH_ALLOC_APPEND( l, dup_dlist_align(), dup_dlist_footprint() );
352 78 : void * fec_pool = FD_SCRATCH_ALLOC_APPEND( l, fec_pool_align(), fec_pool_footprint( fec_max ) );
353 78 : void * fec_map = FD_SCRATCH_ALLOC_APPEND( l, fec_map_align(), fec_map_footprint( fec_map_chain_cnt_est( fec_max ) ) );
354 78 : void * fec_dlist = FD_SCRATCH_ALLOC_APPEND( l, fec_dlist_align(), fec_dlist_footprint() );
355 78 : void * prf_pool = FD_SCRATCH_ALLOC_APPEND( l, prf_pool_align(), prf_pool_footprint( prf_max ) );
356 78 : void * prf_map = FD_SCRATCH_ALLOC_APPEND( l, prf_map_align(), prf_map_footprint( prf_map_chain_cnt_est( prf_max ) ) );
357 78 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
358 78 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( vtr_map_chain_cnt_est( vtr_max ) ) );
359 78 : void * vtr_dlist = FD_SCRATCH_ALLOC_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() );
360 :
361 78 : fd_eqvoc_t * eqvoc = (fd_eqvoc_t *)eqvoc_mem;
362 78 : eqvoc->dup_max = dup_max;
363 78 : eqvoc->fec_max = fec_max;
364 78 : eqvoc->per_vtr_max = per_vtr_max;
365 78 : eqvoc->vtr_max = vtr_max;
366 :
367 78 : eqvoc->sha512 = fd_sha512_new( sha512 );
368 78 : eqvoc->bmtree_mem = bmtree_mem;
369 78 : eqvoc->dup_pool = dup_pool_new ( dup_pool, dup_max );
370 78 : eqvoc->dup_map = dup_map_new ( dup_map, dup_map_chain_cnt_est( dup_max ), seed );
371 78 : eqvoc->dup_dlist = dup_dlist_new( dup_dlist );
372 78 : eqvoc->fec_pool = fec_pool_new ( fec_pool, fec_max );
373 78 : eqvoc->fec_map = fec_map_new ( fec_map, fec_map_chain_cnt_est( fec_max ), seed );
374 78 : eqvoc->fec_dlist = fec_dlist_new( fec_dlist );
375 78 : eqvoc->prf_pool = prf_pool_new ( prf_pool, prf_max );
376 78 : eqvoc->prf_map = prf_map_new ( prf_map, prf_map_chain_cnt_est( prf_max ), seed );
377 78 : eqvoc->vtr_pool = vtr_pool_new ( vtr_pool, vtr_max );
378 78 : eqvoc->vtr_map = vtr_map_new ( vtr_map, vtr_map_chain_cnt_est( vtr_max ), seed );
379 78 : eqvoc->vtr_dlist = vtr_dlist_new( vtr_dlist );
380 :
381 78 : vtr_t * pool_join = vtr_pool_join( eqvoc->vtr_pool );
382 390 : for( ulong i = 0UL; i < vtr_max; i++ ) {
383 312 : void * prf_dlist = FD_SCRATCH_ALLOC_APPEND( l, prf_dlist_align(), prf_dlist_footprint() );
384 312 : pool_join[i].prf_dlist_cnt = 0;
385 312 : pool_join[i].prf_dlist = prf_dlist_new( prf_dlist );
386 312 : }
387 78 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_eqvoc_align() )==(ulong)shmem + footprint );
388 :
389 78 : return shmem;
390 78 : }
391 :
392 : fd_eqvoc_t *
393 78 : fd_eqvoc_join( void * sheqvoc ) {
394 :
395 78 : if( FD_UNLIKELY( !sheqvoc ) ) {
396 0 : FD_LOG_WARNING(( "NULL eqvoc" ));
397 0 : return NULL;
398 0 : }
399 :
400 78 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)sheqvoc, fd_eqvoc_align() ) ) ) {
401 0 : FD_LOG_WARNING(( "misaligned eqvoc" ));
402 0 : return NULL;
403 0 : }
404 :
405 78 : fd_eqvoc_t * eqvoc = (fd_eqvoc_t *)sheqvoc;
406 78 : eqvoc->sha512 = fd_sha512_join( eqvoc->sha512 );
407 : /* bmtree */
408 78 : eqvoc->dup_pool = dup_pool_join ( eqvoc->dup_pool );
409 78 : eqvoc->dup_map = dup_map_join ( eqvoc->dup_map );
410 78 : eqvoc->dup_dlist = dup_dlist_join( eqvoc->dup_dlist );
411 78 : eqvoc->fec_pool = fec_pool_join ( eqvoc->fec_pool );
412 78 : eqvoc->fec_map = fec_map_join ( eqvoc->fec_map );
413 78 : eqvoc->fec_dlist = fec_dlist_join( eqvoc->fec_dlist );
414 78 : eqvoc->prf_pool = prf_pool_join ( eqvoc->prf_pool );
415 78 : eqvoc->prf_map = prf_map_join ( eqvoc->prf_map );
416 78 : eqvoc->vtr_pool = vtr_pool_join ( eqvoc->vtr_pool );
417 78 : eqvoc->vtr_map = vtr_map_join ( eqvoc->vtr_map );
418 78 : eqvoc->vtr_dlist = vtr_dlist_join( eqvoc->vtr_dlist );
419 390 : for( ulong i = 0UL; i < eqvoc->vtr_max; i++ ) {
420 312 : eqvoc->vtr_pool[i].prf_dlist = prf_dlist_join( eqvoc->vtr_pool[i].prf_dlist );
421 312 : }
422 :
423 78 : return (fd_eqvoc_t *)sheqvoc;
424 78 : }
425 :
426 : void *
427 78 : fd_eqvoc_leave( fd_eqvoc_t const * eqvoc ) {
428 :
429 78 : if( FD_UNLIKELY( !eqvoc ) ) {
430 0 : FD_LOG_WARNING(( "NULL eqvoc" ));
431 0 : return NULL;
432 0 : }
433 :
434 78 : return (void *)eqvoc;
435 78 : }
436 :
437 : void *
438 78 : fd_eqvoc_delete( void * eqvoc ) {
439 :
440 78 : if( FD_UNLIKELY( !eqvoc ) ) {
441 0 : FD_LOG_WARNING(( "NULL eqvoc" ));
442 0 : return NULL;
443 0 : }
444 :
445 78 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)eqvoc, fd_eqvoc_align() ) ) ) {
446 0 : FD_LOG_WARNING(( "misaligned eqvoc" ));
447 0 : return NULL;
448 0 : }
449 :
450 78 : return eqvoc;
451 78 : }
452 :
453 : static dup_t *
454 : dup_query( fd_eqvoc_t * eqvoc,
455 363 : ulong slot ) {
456 363 : dup_t * dup = dup_map_ele_query( eqvoc->dup_map, &slot, NULL, eqvoc->dup_pool );
457 363 : if( FD_LIKELY( dup ) ) {
458 60 : dup_dlist_ele_remove( eqvoc->dup_dlist, dup, eqvoc->dup_pool );
459 60 : dup_dlist_ele_push_tail( eqvoc->dup_dlist, dup, eqvoc->dup_pool );
460 60 : }
461 363 : return dup;
462 363 : }
463 :
464 : static fec_t *
465 : fec_query( fd_eqvoc_t * eqvoc,
466 : ulong slot,
467 66 : ulong fec_set_idx ) {
468 66 : ulong key = slot << 32 | fec_set_idx;
469 66 : fec_t * fec = fec_map_ele_query( eqvoc->fec_map, &key, NULL, eqvoc->fec_pool );
470 66 : if( FD_LIKELY( fec ) ) {
471 0 : fec_dlist_ele_remove( eqvoc->fec_dlist, fec, eqvoc->fec_pool );
472 0 : fec_dlist_ele_push_tail( eqvoc->fec_dlist, fec, eqvoc->fec_pool );
473 0 : }
474 66 : return fec;
475 66 : }
476 :
477 : static prf_t *
478 : prf_query( fd_eqvoc_t * eqvoc,
479 : vtr_t * vtr,
480 276 : ulong slot ) {
481 276 : xid_t key = { .slot = slot, .vtr_idx = (uint)vtr_pool_idx( eqvoc->vtr_pool, vtr ) };
482 276 : prf_t * prf = prf_map_ele_query( eqvoc->prf_map, &key, NULL, eqvoc->prf_pool );
483 276 : if( FD_LIKELY( prf ) ) {
484 156 : prf_dlist_ele_remove( vtr->prf_dlist, prf, eqvoc->prf_pool );
485 156 : prf_dlist_ele_push_tail( vtr->prf_dlist, prf, eqvoc->prf_pool );
486 156 : }
487 276 : return prf;
488 276 : }
489 :
490 : static dup_t *
491 : dup_insert( fd_eqvoc_t * eqvoc,
492 60 : ulong slot ) {
493 :
494 : /* FIFO evict if full. Invariant: iff in dlist then in map / pool. */
495 :
496 60 : if( FD_UNLIKELY( !dup_pool_free( eqvoc->dup_pool ) ) ) {
497 0 : dup_t * dup = dup_dlist_ele_pop_head( eqvoc->dup_dlist, eqvoc->dup_pool );
498 0 : dup_map_ele_remove_fast( eqvoc->dup_map, dup, eqvoc->dup_pool );
499 0 : dup_pool_ele_release( eqvoc->dup_pool, dup );
500 0 : }
501 :
502 : /* Insert. Invariant: pool free => map / dlist free. */
503 :
504 60 : dup_t * dup = dup_pool_ele_acquire( eqvoc->dup_pool );
505 60 : dup->slot = slot;
506 60 : dup_map_ele_insert( eqvoc->dup_map, dup, eqvoc->dup_pool );
507 60 : dup_dlist_ele_push_tail( eqvoc->dup_dlist, dup, eqvoc->dup_pool );
508 60 : return dup;
509 60 : }
510 :
511 : static fec_t *
512 : fec_insert( fd_eqvoc_t * eqvoc,
513 : ulong slot,
514 66 : uint fec_set_idx ) {
515 :
516 66 : ulong key = slot << 32 | fec_set_idx;
517 :
518 : /* FIFO evict if full. Invariant: iff in dlist then in map / pool. */
519 :
520 66 : if( FD_UNLIKELY( !fec_pool_free( eqvoc->fec_pool ) ) ) {
521 48 : fec_t * fec = fec_dlist_ele_pop_head( eqvoc->fec_dlist, eqvoc->fec_pool );
522 48 : fec_map_ele_remove_fast( eqvoc->fec_map, fec, eqvoc->fec_pool );
523 48 : fec_pool_ele_release( eqvoc->fec_pool, fec );
524 48 : }
525 :
526 : /* Insert. Invariant: pool free => map / dlist free. */
527 :
528 66 : fec_t * fec = fec_pool_ele_acquire( eqvoc->fec_pool );
529 66 : fec->key = key;
530 66 : fec_map_ele_insert( eqvoc->fec_map, fec, eqvoc->fec_pool );
531 66 : fec_dlist_ele_push_tail( eqvoc->fec_dlist, fec, eqvoc->fec_pool );
532 66 : return fec;
533 66 : }
534 :
535 : static prf_t *
536 : prf_insert( fd_eqvoc_t * eqvoc,
537 : vtr_t * vtr,
538 117 : ulong slot ) {
539 :
540 : /* Each from pubkey in gossip is limited to per_vtr_max proofs.
541 : If we receive more than per_vtr_max from one pubkey, FIFO evict.
542 : We group by pubkey to prevent a single pubkey from spamming
543 : junk proofs. */
544 :
545 117 : if( FD_UNLIKELY( vtr->prf_dlist_cnt==eqvoc->per_vtr_max ) ) {
546 6 : prf_t * evict = prf_dlist_ele_pop_head( vtr->prf_dlist, eqvoc->prf_pool );
547 6 : prf_map_ele_remove_fast( eqvoc->prf_map, evict, eqvoc->prf_pool );
548 6 : prf_pool_ele_release( eqvoc->prf_pool, evict );
549 6 : vtr->prf_dlist_cnt--;
550 6 : }
551 :
552 117 : xid_t key = { .slot = slot, .vtr_idx = (uint)vtr_pool_idx( eqvoc->vtr_pool, vtr ) };
553 117 : prf_t * prf = prf_pool_ele_acquire( eqvoc->prf_pool );
554 117 : prf->key = key;
555 117 : prf->chunk_cnt = 0;
556 117 : prf_map_ele_insert( eqvoc->prf_map, prf, eqvoc->prf_pool );
557 117 : prf_dlist_ele_push_tail( vtr->prf_dlist, prf, eqvoc->prf_pool );
558 117 : vtr->prf_dlist_cnt++;
559 117 : return prf;
560 117 : }
561 :
562 : static int
563 0 : is_last_shred( fd_shred_t const * shred ) {
564 0 : return fd_shred_is_data( fd_shred_type( shred->variant ) ) && shred->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE;
565 0 : }
566 :
567 : /* construct_proof constructs a DuplicateShred proof from shred1 and
568 : shred2. Assumes shred1 and shred2 have already been verified via
569 : verify_proof. On return, chunks_out will be populated with the
570 : serialized format of the proof.
571 :
572 : [ shred1_sz (8 bytes) | shred1 | shred2_sz (8 bytes) | shred2 ]
573 :
574 : Caller supplies `chunks_out`, which is an array that MUST contain
575 : FD_EQVOC_CHUNK_CNT elements. */
576 :
577 : static void
578 : construct_proof( fd_shred_t const * shred1,
579 : fd_shred_t const * shred2,
580 111 : fd_gossip_duplicate_shred_t chunks_out[static FD_EQVOC_CHUNK_CNT] ) {
581 :
582 444 : for (uchar i = 0; i < FD_EQVOC_CHUNK_CNT; i++ ) {
583 333 : chunks_out[i].index = i;
584 333 : chunks_out[i].slot = shred1->slot;
585 333 : chunks_out[i].num_chunks = FD_EQVOC_CHUNK_CNT;
586 333 : chunks_out[i].chunk_index = i;
587 333 : }
588 :
589 111 : ulong shred1_sz = fd_shred_sz( shred1 );
590 111 : ulong shred2_sz = fd_shred_sz( shred2 );
591 :
592 : /* Populate chunk0 */
593 :
594 111 : FD_STORE( ulong, chunks_out[0].chunk, shred1_sz );
595 111 : memcpy( chunks_out[0].chunk + sizeof(ulong), shred1, FD_EQVOC_CHUNK_SZ - sizeof(ulong) );
596 111 : chunks_out[0].chunk_len = FD_EQVOC_CHUNK_SZ;
597 :
598 : /* Populate chunk1 */
599 :
600 111 : ulong shred1_off = FD_EQVOC_CHUNK_SZ - sizeof(ulong);
601 111 : ulong shred1_rem = shred1_sz - shred1_off;
602 111 : memcpy( chunks_out[1].chunk, (uchar *)shred1 + shred1_off, shred1_rem );
603 111 : FD_STORE( ulong, chunks_out[1].chunk + shred1_rem, shred2_sz );
604 111 : ulong chunk1_off = shred1_rem + sizeof(ulong);
605 111 : ulong chunk1_rem = FD_EQVOC_CHUNK_SZ - chunk1_off;
606 111 : memcpy( chunks_out[1].chunk + chunk1_off, shred2, chunk1_rem );
607 111 : chunks_out[1].chunk_len = FD_EQVOC_CHUNK_SZ;
608 :
609 : /* Populate chunk2 */
610 :
611 111 : ulong shred2_off = chunk1_rem;
612 111 : ulong shred2_rem = shred2_sz - shred2_off;
613 111 : memcpy( chunks_out[2].chunk, (uchar *)shred2 + shred2_off, shred2_rem );
614 111 : chunks_out[2].chunk_len = shred2_rem;
615 111 : }
616 :
617 : /* verify_proof verifies that the two shreds contained in `proof` do in
618 : fact equivocate. The two shreds came from untrusted gossip msgs, so
619 : it needs validation.
620 :
621 : Returns: FD_EQVOC_SUCCESS (1) if equivocation detected,
622 : FD_EQVOC_IGNORED (0) if not, or FD_EQVOC_ERR_{...} (<0) if
623 : the shreds were not valid inputs (untrusted path only).
624 :
625 : The implementation mirrors the Agave version very closely. See:
626 : https://github.com/anza-xyz/agave/blob/v3.1/gossip/src/duplicate_shred.rs#L137-L142
627 :
628 : Two shreds equivocate if they satisfy any of the following:
629 :
630 : 1. Both shreds specify the same index and shred type, however their
631 : payloads differ.
632 : 2. Both shreds specify the same FEC set, however their merkle roots
633 : differ.
634 : 3. Both shreds specify the same FEC set and are coding shreds,
635 : however their erasure configs conflict.
636 : 4. The shreds specify different FEC sets, the lower index shred is a
637 : coding shred, and its erasure meta indicates an FEC set overlap.
638 : 5. The shreds specify different FEC sets, the lower index shred has a
639 : merkle root that is not equal to the chained merkle root of the
640 : higher index shred.
641 : 6. The shreds are data shreds with different indices and the shred
642 : with the lower index has the LAST_SHRED_IN_SLOT flag set.
643 :
644 : Ref:
645 : https://github.com/solana-foundation/solana-improvement-documents/blob/main/proposals/0204-slashable-event-verification.md#proof-verification
646 :
647 : Note: two shreds are in the same FEC set if they have the same
648 : verified and FEC set index.
649 :
650 : To prevent false positives, this function also performs the following
651 : input validation on the shreds:
652 :
653 : 1. shred1 and shred2 are for the same verified.
654 : 2. shred1 and shred2 are both the expected shred_version.
655 : 3. shred1 and shred2 are either chained merkle or chained resigned
656 : merkle variants.
657 : 4. shred1 and shred2 contain valid signatures signed by the same
658 : producer pubkey.
659 :
660 : If any of the above input validation fails, this function returns
661 : FD_EQVOC_ERR_{...}. */
662 :
663 : static int
664 : verify_proof( fd_eqvoc_t * eqvoc,
665 : ushort shred_version,
666 : fd_epoch_leaders_t const * leader_schedule,
667 : fd_shred_t const * shred1,
668 54 : fd_shred_t const * shred2 ) {
669 :
670 : /* Must be same slot. */
671 :
672 54 : if( FD_UNLIKELY( shred1->slot != shred2->slot ) ) return FD_EQVOC_ERR_SLOT;
673 :
674 : /* Must be same shred version. */
675 :
676 54 : if( FD_UNLIKELY( shred1->version != shred_version ) ) return FD_EQVOC_ERR_VERSION;
677 54 : if( FD_UNLIKELY( shred2->version != shred_version ) ) return FD_EQVOC_ERR_VERSION;
678 :
679 : /* Must be chained merkle shreds. */
680 :
681 54 : if( FD_UNLIKELY( !fd_shred_is_chained ( fd_shred_type( shred1->variant ) ) ) ) return FD_EQVOC_ERR_TYPE;
682 54 : if( FD_UNLIKELY( !fd_shred_is_chained ( fd_shred_type( shred2->variant ) ) ) ) return FD_EQVOC_ERR_TYPE;
683 :
684 : /* Must have valid merkle roots. */
685 :
686 54 : fd_bmtree_node_t mr1;
687 54 : fd_bmtree_node_t mr2;
688 54 : if( FD_UNLIKELY( !fd_shred_merkle_root( shred1, eqvoc->bmtree_mem, &mr1 ) ) ) return FD_EQVOC_ERR_MERKLE;
689 54 : if( FD_UNLIKELY( !fd_shred_merkle_root( shred2, eqvoc->bmtree_mem, &mr2 ) ) ) return FD_EQVOC_ERR_MERKLE;
690 :
691 : /* Must sigverify (if leader_schedule provided). */
692 :
693 54 : if( FD_LIKELY( leader_schedule ) ) {
694 0 : fd_pubkey_t const * leader = fd_epoch_leaders_get( leader_schedule, shred1->slot );
695 0 : if( FD_UNLIKELY( !leader ) ) return FD_EQVOC_ERR_SIG;
696 0 : fd_sha512_t _sha512[1];
697 0 : fd_sha512_t * sha512 = fd_sha512_join( fd_sha512_new( _sha512 ) );
698 0 : if( FD_UNLIKELY( FD_ED25519_SUCCESS != fd_ed25519_verify( mr1.hash, 32UL, shred1->signature, leader->uc, sha512 ) ||
699 0 : FD_ED25519_SUCCESS != fd_ed25519_verify( mr2.hash, 32UL, shred2->signature, leader->uc, sha512 ) ) ) {
700 0 : return FD_EQVOC_ERR_SIG;
701 0 : }
702 0 : }
703 :
704 : /* If both are data shreds, then check for last shred conflicts. */
705 :
706 54 : if( FD_LIKELY( fd_shred_is_data( fd_shred_type( shred1->variant ) ) && fd_shred_is_data( fd_shred_type( shred2->variant ) ) ) ) {
707 18 : if( FD_LIKELY( ( shred1->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE && shred2->idx > shred1->idx ) ||
708 18 : ( shred2->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE && shred1->idx > shred2->idx ) ) ) {
709 0 : return FD_EQVOC_SUCCESS;
710 0 : }
711 18 : }
712 :
713 : /* If both shreds are in the same FEC set, then check for merkle root
714 : conflicts. */
715 :
716 54 : if( FD_UNLIKELY( shred1->fec_set_idx == shred2->fec_set_idx ) ) {
717 54 : if( FD_LIKELY( 0!=memcmp( mr1.hash, mr2.hash, sizeof(mr1.hash)) ) ) {
718 54 : return FD_EQVOC_SUCCESS;
719 54 : }
720 54 : }
721 :
722 0 : return FD_EQVOC_IGNORED;
723 54 : }
724 :
725 : int
726 : fd_eqvoc_shred_insert( fd_eqvoc_t * eqvoc,
727 : int shred_hint,
728 : fd_shred_t const * shred,
729 36 : fd_gossip_duplicate_shred_t chunks_out[static FD_EQVOC_CHUNK_CNT] ) {
730 :
731 36 : ulong slot = shred->slot;
732 36 : dup_t * dup = dup_query( eqvoc, slot );
733 36 : if( FD_UNLIKELY( dup ) ) return 0; /* no proof constructed */
734 :
735 33 : if( FD_UNLIKELY( shred_hint ) ) {
736 :
737 : /* shred tile has hinted to us that this shred equivocates */
738 :
739 0 : fec_t * fec = fec_query( eqvoc, shred->slot, shred->fec_set_idx );
740 0 : if( FD_UNLIKELY( !fec ) ) return 0; /* it's possible we already evicted this FEC set */
741 0 : construct_proof( &fec->sample_shred, shred, chunks_out );
742 0 : dup_insert( eqvoc, slot );
743 0 : fec_dlist_ele_remove( eqvoc->fec_dlist, fec, eqvoc->fec_pool );
744 0 : fec_map_ele_remove_fast( eqvoc->fec_map, fec, eqvoc->fec_pool );
745 0 : fec_pool_ele_release( eqvoc->fec_pool, fec );
746 0 : return 1; /* proof constructed */
747 :
748 33 : } else {
749 :
750 : /* last index conflicts are not hinted by shred */
751 :
752 33 : fec_t * last = fec_query( eqvoc, shred->slot, UINT_MAX );
753 33 : if( FD_UNLIKELY( !last ) ) {
754 33 : last = fec_insert( eqvoc, slot, UINT_MAX ); /* specially index the last shred in a slot */
755 33 : fd_memcpy( &last->sample_shred, shred, fd_shred_sz( shred ) );
756 33 : } else if( FD_UNLIKELY( ( is_last_shred( shred ) && shred->idx < last->sample_shred.idx ) ||
757 0 : ( is_last_shred( &last->sample_shred ) && shred->idx > last->sample_shred.idx ) ) ) {
758 0 : construct_proof( shred, &last->sample_shred, chunks_out );
759 0 : dup_insert( eqvoc, slot );
760 0 : return 1;
761 0 : } else if( FD_UNLIKELY( shred->idx > last->sample_shred.idx ) ) {
762 0 : fd_memcpy( &last->sample_shred, shred, fd_shred_sz( shred ) );
763 0 : }
764 :
765 33 : fec_t * fec = fec_query( eqvoc, shred->slot, shred->fec_set_idx );
766 33 : if( FD_UNLIKELY( !fec ) ) {
767 33 : fec = fec_insert( eqvoc, shred->slot, shred->fec_set_idx );
768 33 : fd_memcpy( &fec->sample_shred, shred, fd_shred_sz( shred ) );
769 33 : }
770 :
771 33 : return 0;
772 33 : }
773 33 : }
774 :
775 : int
776 : fd_eqvoc_chunk_insert( fd_eqvoc_t * eqvoc,
777 : ulong root,
778 : ushort shred_version,
779 : fd_epoch_leaders_t const * leader_schedule,
780 : fd_pubkey_t const * from,
781 : fd_gossip_duplicate_shred_t const * chunk,
782 315 : fd_gossip_duplicate_shred_t chunks_out[static FD_EQVOC_CHUNK_CNT] ) {
783 :
784 315 : if( FD_UNLIKELY( chunk->slot <= root ) ) return FD_EQVOC_ERR_CHUNK_SLOT;
785 :
786 312 : vtr_t * vtr = vtr_map_ele_query( eqvoc->vtr_map, from, NULL, eqvoc->vtr_pool );
787 312 : if( FD_UNLIKELY( !vtr ) ) return FD_EQVOC_ERR_CHUNK_FROM;
788 :
789 276 : if( FD_UNLIKELY( chunk->num_chunks !=FD_EQVOC_CHUNK_CNT ) ) return FD_EQVOC_ERR_CHUNK_CNT;
790 273 : if( FD_UNLIKELY( chunk->chunk_index>=FD_EQVOC_CHUNK_CNT ) ) return FD_EQVOC_ERR_CHUNK_IDX;
791 :
792 270 : if( FD_UNLIKELY( chunk->chunk_index==0 && chunk->chunk_len!=FD_EQVOC_CHUNK0_LEN ) ) return FD_EQVOC_ERR_CHUNK_LEN;
793 267 : if( FD_UNLIKELY( chunk->chunk_index==1 && chunk->chunk_len!=FD_EQVOC_CHUNK1_LEN ) ) return FD_EQVOC_ERR_CHUNK_LEN;
794 264 : if( FD_UNLIKELY( chunk->chunk_index==2 && chunk->chunk_len!=FD_EQVOC_CHUNK2_LEN_CC &&
795 264 : chunk->chunk_len!=FD_EQVOC_CHUNK2_LEN_DD &&
796 264 : chunk->chunk_len!=FD_EQVOC_CHUNK2_LEN_DC &&
797 264 : chunk->chunk_len!=FD_EQVOC_CHUNK2_LEN_CD ) ) return FD_EQVOC_ERR_CHUNK_LEN;
798 :
799 261 : if( FD_UNLIKELY( dup_query( eqvoc, chunk->slot ) ) ) return FD_EQVOC_IGNORED; /* already verified an equivocation proof for this slot */
800 :
801 261 : prf_t * prf = prf_query( eqvoc, vtr, chunk->slot );
802 261 : if( FD_UNLIKELY( !prf ) ) prf = prf_insert( eqvoc, vtr, chunk->slot );
803 465 : for( uchar i = 0U; i < prf->chunk_cnt; i++ ) {
804 213 : if( FD_UNLIKELY( prf->chunk_idx[ i ]==chunk->chunk_index ) ) return FD_EQVOC_IGNORED;
805 213 : }
806 :
807 252 : if( FD_LIKELY( prf->chunk_cnt<FD_EQVOC_CHUNK_CNT-1 ) ) {
808 186 : uchar i = prf->chunk_cnt++;
809 186 : prf->chunk_idx[ i ] = chunk->chunk_index;
810 186 : prf->chunk_len[ i ] = (ushort)chunk->chunk_len;
811 186 : fd_memcpy( prf->chunks[ i ], chunk->chunk, chunk->chunk_len );
812 186 : return FD_EQVOC_IGNORED;
813 186 : }
814 :
815 66 : uchar buf[ 2 * FD_SHRED_MAX_SZ + 2 * sizeof(ulong) ] __attribute__((aligned(8)));
816 66 : fd_memcpy( buf + chunk->chunk_index * FD_EQVOC_CHUNK_SZ, chunk->chunk, chunk->chunk_len );
817 66 : ulong buf_sz = chunk->chunk_len;
818 198 : for( uchar i = 0U; i < prf->chunk_cnt; i++ ) {
819 132 : fd_memcpy( buf + prf->chunk_idx[ i ] * FD_EQVOC_CHUNK_SZ, prf->chunks[ i ], prf->chunk_len[ i ] );
820 132 : buf_sz += prf->chunk_len[ i ];
821 132 : }
822 :
823 66 : int err = FD_EQVOC_ERR_SERDE; ulong off = 0;
824 :
825 66 : if( FD_UNLIKELY( buf_sz - off < sizeof(ulong) ) ) goto cleanup;
826 66 : ulong shred1_sz = fd_ulong_load_8( buf );
827 66 : off += sizeof(ulong);
828 :
829 66 : if( FD_UNLIKELY( buf_sz - off < shred1_sz ) ) goto cleanup;
830 : /* We use FD_SHRED_BLK_MAX as max_shred_idx because that is what
831 : Agave does here (Shred::new_from_serialized_shred in into_shreds):
832 : https://github.com/anza-xyz/agave/blob/v4.2/gossip/src/duplicate_shred.rs#L350-L351 */
833 66 : fd_shred_t const * shred1 = fd_shred_parse( buf + off, shred1_sz, FD_SHRED_BLK_MAX );
834 66 : if( FD_UNLIKELY( !shred1 || fd_shred_sz( shred1 )!=shred1_sz ) ) goto cleanup; /* check the sz matches parsed shred's type */
835 57 : off += shred1_sz;
836 :
837 57 : if( FD_UNLIKELY( buf_sz - off < sizeof(ulong) ) ) goto cleanup;
838 57 : ulong shred2_sz = fd_ulong_load_8( buf + off );
839 57 : off += sizeof(ulong);
840 :
841 57 : if( FD_UNLIKELY( buf_sz - off < shred2_sz ) ) goto cleanup;
842 57 : fd_shred_t const * shred2 = fd_shred_parse( buf + off, shred2_sz, FD_SHRED_BLK_MAX );
843 57 : if( FD_UNLIKELY( !shred2 || fd_shred_sz( shred2 )!=shred2_sz ) ) goto cleanup; /* check the sz matches parsed shred's type */
844 57 : off += shred2_sz;
845 :
846 57 : if( FD_UNLIKELY( off!=buf_sz ) ) goto cleanup;
847 :
848 57 : if( FD_UNLIKELY( shred1->slot != chunk->slot || shred2->slot != chunk->slot ) ) goto cleanup;
849 :
850 54 : err = verify_proof( eqvoc, shred_version, leader_schedule, shred1, shred2 );
851 54 : if( FD_UNLIKELY( err==FD_EQVOC_SUCCESS ) ) {
852 54 : construct_proof( shred1, shred2, chunks_out );
853 54 : dup_insert( eqvoc, chunk->slot );
854 54 : }
855 :
856 66 : cleanup:;
857 66 : prf_dlist_ele_remove( vtr->prf_dlist, prf, eqvoc->prf_pool );
858 66 : prf_map_ele_remove_fast( eqvoc->prf_map, prf, eqvoc->prf_pool );
859 66 : prf_pool_ele_release( eqvoc->prf_pool, prf );
860 66 : vtr->prf_dlist_cnt--;
861 66 : return err;
862 54 : }
863 :
864 : int
865 : fd_eqvoc_proof_verified( fd_eqvoc_t * eqvoc,
866 66 : ulong slot ) {
867 66 : return !!dup_query( eqvoc, slot );
868 66 : }
869 :
870 : void
871 : fd_eqvoc_update_voters( fd_eqvoc_t * eqvoc,
872 : fd_pubkey_t const * id_keys,
873 27 : ulong cnt ) {
874 :
875 27 : for( vtr_dlist_iter_t iter = vtr_dlist_iter_fwd_init( eqvoc->vtr_dlist, eqvoc->vtr_pool );
876 66 : !vtr_dlist_iter_done( iter, eqvoc->vtr_dlist, eqvoc->vtr_pool );
877 39 : iter = vtr_dlist_iter_fwd_next( iter, eqvoc->vtr_dlist, eqvoc->vtr_pool ) ) {
878 39 : eqvoc->vtr_pool[iter].next = 1; /* mark for removal */
879 39 : }
880 :
881 : /* First pass: unmark kept voters from being released. */
882 :
883 87 : for( ulong i=0UL; i<cnt; i++ ) {
884 60 : fd_pubkey_t const * id = &id_keys[i];
885 60 : vtr_t * vtr = vtr_map_ele_query( eqvoc->vtr_map, id, NULL, eqvoc->vtr_pool );
886 60 : if( FD_LIKELY( vtr ) ) {
887 24 : vtr_dlist_ele_remove( eqvoc->vtr_dlist, vtr, eqvoc->vtr_pool );
888 24 : vtr->next = 0; /* unmark for removal */
889 24 : vtr_dlist_ele_push_tail( eqvoc->vtr_dlist, vtr, eqvoc->vtr_pool );
890 24 : }
891 60 : }
892 :
893 : /* Pop and release marked voters until the first unmarked voter. */
894 :
895 42 : while( FD_LIKELY( !vtr_dlist_is_empty( eqvoc->vtr_dlist, eqvoc->vtr_pool ) ) ) {
896 27 : vtr_t * vtr = vtr_dlist_ele_pop_head( eqvoc->vtr_dlist, eqvoc->vtr_pool );
897 27 : if( FD_UNLIKELY( !vtr->next ) ) { /* can short-circuit since all the existing and new voters were appended */
898 12 : vtr_dlist_ele_push_tail( eqvoc->vtr_dlist, vtr, eqvoc->vtr_pool );
899 12 : break;
900 12 : }
901 33 : while( FD_LIKELY( !prf_dlist_is_empty( vtr->prf_dlist, eqvoc->prf_pool ) ) ) {
902 18 : prf_t * prf = prf_dlist_ele_pop_head( vtr->prf_dlist, eqvoc->prf_pool );
903 18 : prf_map_ele_remove_fast( eqvoc->prf_map, prf, eqvoc->prf_pool );
904 18 : prf_pool_ele_release( eqvoc->prf_pool, prf );
905 18 : }
906 15 : vtr_map_ele_remove_fast( eqvoc->vtr_map, vtr, eqvoc->vtr_pool );
907 15 : vtr_pool_ele_release( eqvoc->vtr_pool, vtr );
908 15 : }
909 :
910 : /* Second pass: acquire and insert new voters. */
911 :
912 87 : for( ulong i=0UL; i<cnt; i++ ) {
913 60 : fd_pubkey_t const * id = &id_keys[i];
914 60 : if( FD_LIKELY( vtr_map_ele_query( eqvoc->vtr_map, id, NULL, eqvoc->vtr_pool ) ) ) continue;
915 36 : vtr_t * vtr = vtr_pool_ele_acquire( eqvoc->vtr_pool );
916 36 : vtr->from = *id;
917 36 : vtr->prf_dlist_cnt = 0;
918 36 : vtr->next = 0;
919 36 : vtr_map_ele_insert( eqvoc->vtr_map, vtr, eqvoc->vtr_pool );
920 36 : vtr_dlist_ele_push_tail( eqvoc->vtr_dlist, vtr, eqvoc->vtr_pool );
921 36 : }
922 27 : }
|
