Line data Source code
1 : #include "ag_votor.h"
2 :
3 : #define QUEUE_NAME vote_events
4 51 : #define QUEUE_T ag_event_vote_t
5 : #include "../../util/tmpl/fd_queue_dynamic.c"
6 :
7 : #define QUEUE_NAME cert_events
8 0 : #define QUEUE_T ag_event_cert_t
9 : #include "../../util/tmpl/fd_queue_dynamic.c"
10 :
11 : #define PARENTS_READY_MAX (AG_SLOTS_PER_WINDOW*AG_NOTAR_FALLBACK_CERT_MAX+1UL)
12 :
13 : struct slot_state_ele {
14 : ulong slot;
15 : ulong next;
16 :
17 : int voted;
18 : int voted_notar;
19 : ag_block_hash_t voted_notar_hash;
20 : int bad_window;
21 : int block_notarized;
22 : ag_block_hash_t block_notarized_hash;
23 : ag_block_id_t parents_ready[ PARENTS_READY_MAX ];
24 : ulong parents_ready_cnt;
25 : int received_shred;
26 : int pending_block;
27 : ag_block_info_t pending_block_info;
28 : int retired;
29 :
30 : long timeout;
31 : long timeout_crashed_leader;
32 :
33 : struct { ulong prev; ulong next; } pending_dlist;
34 : struct { ulong prev; ulong next; } timeout_dlist;
35 : };
36 : typedef struct slot_state_ele slot_state_ele_t;
37 :
38 : #define POOL_NAME slot_state_pool
39 42 : #define POOL_T slot_state_ele_t
40 : #include "../../util/tmpl/fd_pool.c"
41 :
42 : #define MAP_NAME slot_state_map
43 : #define MAP_ELE_T slot_state_ele_t
44 111 : #define MAP_KEY slot
45 : #define MAP_KEY_T ulong
46 435 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
47 675 : #define MAP_KEY_HASH(key,seed) (fd_ulong_hash( (*(key)) ^ (seed) ))
48 156 : #define MAP_NEXT next
49 : #include "../../util/tmpl/fd_map_chain.c"
50 :
51 : #define DLIST_NAME pending_dlist
52 : #define DLIST_ELE_T slot_state_ele_t
53 9 : #define DLIST_PREV pending_dlist.prev
54 15 : #define DLIST_NEXT pending_dlist.next
55 : #include "../../util/tmpl/fd_dlist.c"
56 :
57 : #define DLIST_NAME timeout_dlist
58 : #define DLIST_ELE_T slot_state_ele_t
59 132 : #define DLIST_PREV timeout_dlist.prev
60 132 : #define DLIST_NEXT timeout_dlist.next
61 : #include "../../util/tmpl/fd_dlist.c"
62 :
63 : struct slot_states {
64 : slot_state_ele_t * pool;
65 : slot_state_map_t * map;
66 : };
67 : typedef struct slot_states slot_states_t;
68 :
69 : #define SORT_NAME slot_sort
70 0 : #define SORT_KEY_T ulong
71 0 : #define SORT_BEFORE(a,b) ((a)<(b))
72 : #include "../../util/tmpl/fd_sort.c"
73 :
74 : struct __attribute__((aligned(128UL))) ag_votor {
75 : long now;
76 : ulong seq;
77 : ulong root;
78 : ulong slot_max;
79 : ushort shred_version;
80 : fd_bls_sign_fn bls_sign_fn;
81 : void * bls_sign_ctx;
82 :
83 : slot_states_t * slot_states;
84 : ulong highest_final_cert_slot;
85 :
86 : ulong prev_epoch_rank;
87 : ulong prev_epoch_slot;
88 : ulong curr_epoch_rank;
89 : ulong curr_epoch_slot;
90 : ulong next_epoch_rank;
91 : ulong next_epoch_slot;
92 :
93 : ag_event_vote_t * vote_events;
94 : ag_event_cert_t * cert_events;
95 : pending_dlist_t * pending_dlist;
96 : timeout_dlist_t * timeout_dlist;
97 :
98 : struct {
99 : ulong * slots;
100 : } scratch;
101 : };
102 :
103 : FD_FN_PURE static inline int
104 165 : timer_idle( slot_state_ele_t const * ele ) {
105 165 : return ele->timeout==LONG_MAX && ele->timeout_crashed_leader==LONG_MAX;
106 165 : }
107 :
108 : static slot_state_ele_t *
109 : state_mut( ag_votor_t * self,
110 261 : ulong slot ) {
111 261 : slot_state_ele_t * ele = slot_state_map_ele_query( self->slot_states->map, &slot, NULL, self->slot_states->pool );
112 261 : if( FD_LIKELY( ele ) ) return ele;
113 :
114 111 : FD_TEST( slot_state_pool_free( self->slot_states->pool ) );
115 :
116 111 : ele = slot_state_pool_ele_acquire( self->slot_states->pool );
117 111 : fd_memset( ele, 0, sizeof(slot_state_ele_t) );
118 111 : ele->slot = slot;
119 111 : ele->timeout = LONG_MAX;
120 111 : ele->timeout_crashed_leader = LONG_MAX;
121 111 : slot_state_map_ele_insert( self->slot_states->map, ele, self->slot_states->pool );
122 111 : return ele;
123 111 : }
124 :
125 : static void
126 : set_timeouts( ag_votor_t * self,
127 27 : ulong slot ) {
128 27 : FD_TEST( ag_is_start_of_window( slot ) );
129 :
130 27 : long deadline = self->now + AG_DELTA_TIMEOUT_NS + AG_DELTA_FIRST_SLICE_NS;
131 :
132 27 : slot_state_ele_t * start = state_mut( self, slot );
133 27 : int start_idle = timer_idle( start );
134 27 : start->timeout_crashed_leader = fd_long_min( start->timeout_crashed_leader, deadline );
135 27 : if( FD_UNLIKELY( start_idle ) ) timeout_dlist_ele_push_tail( self->timeout_dlist, start, self->slot_states->pool );
136 :
137 135 : for( ulong s=slot; s<slot+AG_SLOTS_PER_WINDOW; s++ ) {
138 108 : deadline += fd_long_if( ag_is_start_of_window( s ),
139 108 : fd_long_max( AG_DELTA_BLOCK_NS-AG_DELTA_FIRST_SLICE_NS, 0L ),
140 108 : AG_DELTA_BLOCK_NS );
141 108 : slot_state_ele_t * state = state_mut( self, s );
142 108 : int idle = timer_idle( state );
143 108 : state->timeout = fd_long_min( state->timeout, deadline );
144 108 : if( FD_LIKELY( idle ) ) timeout_dlist_ele_push_tail( self->timeout_dlist, state, self->slot_states->pool );
145 108 : }
146 27 : }
147 :
148 : ulong
149 189 : ag_votor_align( void ) {
150 189 : return alignof(ag_votor_t);
151 189 : }
152 :
153 : ulong
154 42 : ag_votor_footprint( ulong slot_max ) {
155 42 : if( FD_UNLIKELY( slot_max<AG_SLOTS_PER_WINDOW ) ) return 0UL;
156 42 : ulong events_max = slot_max*( AG_NOTAR_FALLBACK_CERT_MAX + 1UL /* notar */ + 1UL /* skip */ ); /* a standstill bundle, see ag_pool_footprint */
157 42 : ulong slot_state_chain_cnt = slot_state_map_chain_cnt_est( slot_max );
158 42 : return FD_LAYOUT_FINI(
159 42 : FD_LAYOUT_APPEND(
160 42 : FD_LAYOUT_APPEND(
161 42 : FD_LAYOUT_APPEND(
162 42 : FD_LAYOUT_APPEND(
163 42 : FD_LAYOUT_APPEND(
164 42 : FD_LAYOUT_APPEND(
165 42 : FD_LAYOUT_APPEND(
166 42 : FD_LAYOUT_APPEND(
167 42 : FD_LAYOUT_APPEND(
168 42 : FD_LAYOUT_INIT,
169 42 : alignof(ag_votor_t), sizeof(ag_votor_t) ),
170 42 : alignof(slot_states_t), sizeof(slot_states_t) ),
171 42 : slot_state_pool_align(), slot_state_pool_footprint( slot_max ) ),
172 42 : slot_state_map_align(), slot_state_map_footprint ( slot_state_chain_cnt ) ),
173 42 : pending_dlist_align(), pending_dlist_footprint() ),
174 42 : timeout_dlist_align(), timeout_dlist_footprint() ),
175 42 : vote_events_align(), vote_events_footprint( events_max ) ),
176 42 : cert_events_align(), cert_events_footprint( events_max ) ),
177 42 : alignof(ulong), sizeof(ulong)*slot_max ),
178 42 : ag_votor_align() );
179 42 : }
180 :
181 : void *
182 : ag_votor_new( void * mem,
183 : ulong slot_max,
184 21 : ulong seed ) {
185 21 : if( FD_UNLIKELY( !mem ) ) {
186 0 : FD_LOG_WARNING(( "NULL mem" ));
187 0 : return NULL;
188 0 : }
189 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, ag_votor_align() ) ) ) {
190 0 : FD_LOG_WARNING(( "misaligned mem" ));
191 0 : return NULL;
192 0 : }
193 21 : ulong footprint = ag_votor_footprint( slot_max );
194 21 : if( FD_UNLIKELY( !footprint ) ) {
195 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
196 0 : return NULL;
197 0 : }
198 21 : fd_memset( mem, 0, footprint );
199 :
200 21 : ulong events_max = slot_max*( AG_NOTAR_FALLBACK_CERT_MAX + 1UL /* notar */ + 1UL /* skip */ );
201 21 : ulong slot_state_chain_cnt = slot_state_map_chain_cnt_est( slot_max );
202 :
203 21 : FD_SCRATCH_ALLOC_INIT( l, mem );
204 21 : ag_votor_t * votor = FD_SCRATCH_ALLOC_APPEND( l, alignof(ag_votor_t), sizeof(ag_votor_t) );
205 21 : void * slot_states = FD_SCRATCH_ALLOC_APPEND( l, alignof(slot_states_t), sizeof(slot_states_t) );
206 21 : void * slot_state_pool = FD_SCRATCH_ALLOC_APPEND( l, slot_state_pool_align(), slot_state_pool_footprint( slot_max ) );
207 21 : void * slot_state_map = FD_SCRATCH_ALLOC_APPEND( l, slot_state_map_align(), slot_state_map_footprint ( slot_state_chain_cnt ) );
208 21 : void * pending_dlist = FD_SCRATCH_ALLOC_APPEND( l, pending_dlist_align(), pending_dlist_footprint() );
209 21 : void * timeout_dlist = FD_SCRATCH_ALLOC_APPEND( l, timeout_dlist_align(), timeout_dlist_footprint() );
210 21 : void * vote_events = FD_SCRATCH_ALLOC_APPEND( l, vote_events_align(), vote_events_footprint( events_max ) );
211 21 : void * cert_events = FD_SCRATCH_ALLOC_APPEND( l, cert_events_align(), cert_events_footprint( events_max ) );
212 21 : void * slot_scratch = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), sizeof(ulong)*slot_max );
213 21 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, ag_votor_align() ) == (ulong)mem + footprint );
214 :
215 21 : votor->seq = 0UL;
216 21 : votor->root = ULONG_MAX;
217 21 : votor->slot_max = slot_max;
218 21 : votor->slot_states = (slot_states_t *)slot_states;
219 21 : votor->slot_states->pool = slot_state_pool_join( slot_state_pool_new( slot_state_pool, slot_max ) );
220 21 : votor->slot_states->map = slot_state_map_join ( slot_state_map_new ( slot_state_map, slot_state_chain_cnt, seed ) );
221 21 : votor->highest_final_cert_slot = ULONG_MAX;
222 21 : votor->prev_epoch_rank = USHORT_MAX;
223 21 : votor->prev_epoch_slot = ULONG_MAX;
224 21 : votor->curr_epoch_rank = USHORT_MAX;
225 21 : votor->curr_epoch_slot = ULONG_MAX;
226 21 : votor->next_epoch_rank = USHORT_MAX;
227 21 : votor->next_epoch_slot = ULONG_MAX;
228 21 : votor->vote_events = vote_events_join( vote_events_new( vote_events, events_max ) );
229 21 : votor->cert_events = cert_events_join( cert_events_new( cert_events, events_max ) );
230 21 : votor->pending_dlist = pending_dlist_join( pending_dlist_new( pending_dlist ) );
231 21 : votor->timeout_dlist = timeout_dlist_join( timeout_dlist_new( timeout_dlist ) );
232 21 : votor->scratch.slots = (ulong *)slot_scratch;
233 :
234 21 : return mem;
235 21 : }
236 :
237 : ag_votor_t *
238 21 : ag_votor_join( void * mem ) {
239 21 : ag_votor_t * votor = (ag_votor_t *)mem;
240 21 : if( FD_UNLIKELY( !votor ) ) {
241 0 : FD_LOG_WARNING(( "NULL mem" ));
242 0 : return NULL;
243 0 : }
244 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)votor, ag_votor_align() ) ) ) {
245 0 : FD_LOG_WARNING(( "misaligned mem" ));
246 0 : return NULL;
247 0 : }
248 21 : return votor;
249 21 : }
250 :
251 : void *
252 21 : ag_votor_leave( ag_votor_t const * votor ) {
253 21 : if( FD_UNLIKELY( !votor ) ) {
254 0 : FD_LOG_WARNING(( "NULL votor" ));
255 0 : return NULL;
256 0 : }
257 21 : return (void *)votor;
258 21 : }
259 :
260 : void *
261 21 : ag_votor_delete( void * mem ) {
262 21 : if( FD_UNLIKELY( !mem ) ) {
263 0 : FD_LOG_WARNING(( "NULL mem" ));
264 0 : return NULL;
265 0 : }
266 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, ag_votor_align() ) ) ) {
267 0 : FD_LOG_WARNING(( "misaligned mem" ));
268 0 : return NULL;
269 0 : }
270 21 : return mem;
271 21 : }
272 :
273 : void
274 : ag_votor_init( ag_votor_t * self,
275 : ulong slot,
276 : long now,
277 : ushort shred_version,
278 : fd_bls_sign_fn sign_fn,
279 21 : void * sign_ctx ) {
280 21 : FD_TEST( sign_fn );
281 21 : self->now = now;
282 21 : self->root = slot;
283 21 : self->shred_version = shred_version;
284 21 : self->bls_sign_fn = sign_fn;
285 21 : self->bls_sign_ctx = sign_ctx;
286 21 : self->highest_final_cert_slot = slot;
287 :
288 21 : slot_state_ele_t * state = state_mut( self, slot );
289 21 : state->voted = 1;
290 21 : state->voted_notar = 1;
291 21 : state->block_notarized = 1;
292 21 : state->parents_ready[ 0 ].slot = slot;
293 21 : state->parents_ready_cnt = 1UL;
294 21 : state->retired = 1;
295 :
296 21 : set_timeouts( self, ag_first_slot_in_window( slot ) );
297 21 : }
298 :
299 : void
300 0 : ag_votor_fini( ag_votor_t * self ) {
301 0 : self->root = ULONG_MAX;
302 0 : self->highest_final_cert_slot = ULONG_MAX;
303 0 : }
304 :
305 : static ushort
306 : own_rank( ag_votor_t const * self,
307 57 : ulong slot ) {
308 57 : return (ushort)fd_ulong_if( slot>=self->next_epoch_slot, self->next_epoch_rank, fd_ulong_if( slot>=self->curr_epoch_slot, self->curr_epoch_rank, self->prev_epoch_rank ) );
309 57 : }
310 :
311 : FD_FN_PURE static int
312 : is_retired( ag_votor_t const * self,
313 81 : ulong slot ) {
314 81 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
315 81 : return ele && ele->retired;
316 81 : }
317 :
318 : FD_FN_PURE static int
319 : has_voted( ag_votor_t const * self,
320 117 : ulong slot ) {
321 117 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
322 117 : return ele && ele->voted;
323 117 : }
324 :
325 : FD_FN_PURE static int
326 : received_shred( ag_votor_t const * self,
327 0 : ulong slot ) {
328 0 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
329 0 : return ele && ele->received_shred;
330 0 : }
331 :
332 : FD_FN_PURE static ulong
333 84 : first_unpruned_slot( ag_votor_t const * self ) {
334 84 : return ag_first_slot_in_window( fd_ulong_sat_sub( self->highest_final_cert_slot, AG_REWARD_SLOT_DELTA ) );
335 84 : }
336 :
337 : FD_FN_PURE static ulong
338 15 : pool_event_slot( ag_event_pool_t const * event ) {
339 15 : switch( event->kind ) {
340 3 : case AG_EVENT_POOL_PARENT_READY: return event->parent_ready.slot;
341 3 : case AG_EVENT_POOL_SAFE_TO_NOTAR: return event->safe_to_notar.slot;
342 3 : case AG_EVENT_POOL_SAFE_TO_SKIP: return event->safe_to_skip;
343 6 : case AG_EVENT_POOL_CERT_CREATED: return ag_cert_slot( &event->cert_created );
344 0 : case AG_EVENT_POOL_STANDSTILL: return event->standstill.slot;
345 0 : default: FD_LOG_CRIT(( "unreachable" ));
346 15 : }
347 15 : }
348 :
349 : static int
350 : should_ignore_pool_event( ag_votor_t const * self,
351 15 : ag_event_pool_t const * event ) {
352 15 : ulong slot = pool_event_slot( event );
353 15 : switch( event->kind ) {
354 0 : case AG_EVENT_POOL_STANDSTILL: return 0;
355 6 : case AG_EVENT_POOL_CERT_CREATED: return slot<first_unpruned_slot( self );
356 3 : case AG_EVENT_POOL_PARENT_READY:
357 6 : case AG_EVENT_POOL_SAFE_TO_NOTAR:
358 9 : case AG_EVENT_POOL_SAFE_TO_SKIP: return slot<first_unpruned_slot( self ) || is_retired( self, slot );
359 0 : default: FD_LOG_CRIT(( "unreachable" ));
360 15 : }
361 15 : }
362 :
363 : static void
364 : try_final( ag_votor_t * self,
365 : ulong slot,
366 15 : ag_block_hash_t const hash ) {
367 15 : FD_TEST( slot>=first_unpruned_slot( self ) );
368 :
369 15 : slot_state_ele_t const * state = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
370 15 : int notarized = state && state->block_notarized && !memcmp( state->block_notarized_hash, hash, sizeof(ag_block_hash_t) );
371 15 : int voted_notar = state && state->voted_notar && !memcmp( state->voted_notar_hash, hash, sizeof(ag_block_hash_t) );
372 15 : int not_bad = !( state && state->bad_window );
373 15 : if( FD_LIKELY( notarized && voted_notar && not_bad ) ) {
374 3 : ag_vote_t vote = ag_vote_construct_final( self->bls_sign_fn, self->bls_sign_ctx, slot, own_rank( self, slot ), self->shred_version );
375 3 : FD_TEST( !vote_events_full( self->vote_events ) );
376 3 : vote_events_push( self->vote_events, (ag_event_vote_t){ .seq = self->seq++, .ts = self->now, .vote = vote } );
377 3 : state_mut( self, slot )->retired = 1;
378 3 : }
379 15 : }
380 :
381 : static int
382 : try_notar( ag_votor_t * self,
383 : ulong slot,
384 21 : ag_block_info_t const * block_info ) {
385 21 : FD_TEST( slot>=first_unpruned_slot( self ) );
386 21 : if( FD_UNLIKELY( has_voted( self, slot ) ) ) return 0;
387 :
388 18 : ag_block_hash_t hash;
389 18 : memcpy( hash, block_info->hash, sizeof(ag_block_hash_t) );
390 18 : ag_block_id_t parent = block_info->parent;
391 :
392 18 : if( FD_UNLIKELY( ag_is_start_of_window( slot ) ) ) {
393 3 : slot_state_ele_t const * state = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
394 3 : int valid_parent = 0;
395 3 : if( FD_LIKELY( state ) ) {
396 0 : for( ulong i=0UL; i<state->parents_ready_cnt; i++ ) {
397 0 : if( FD_UNLIKELY( ag_block_id_eq( &state->parents_ready[i], &parent ) ) ) { valid_parent = 1; break; }
398 0 : }
399 0 : }
400 3 : if( FD_UNLIKELY( !valid_parent ) ) return 0;
401 15 : } else {
402 15 : if( FD_UNLIKELY( parent.slot!=slot-1UL ) ) return 0;
403 15 : slot_state_ele_t const * parent_state = slot_state_map_ele_query_const( self->slot_states->map, &parent.slot, NULL, self->slot_states->pool );
404 15 : if( FD_UNLIKELY( !parent_state || !parent_state->voted_notar ) ) return 0;
405 12 : if( FD_UNLIKELY( memcmp( parent_state->voted_notar_hash, parent.hash, sizeof(ag_block_hash_t) )!=0 ) ) return 0;
406 12 : }
407 :
408 12 : ag_vote_t vote = ag_vote_construct_notar( self->bls_sign_fn, self->bls_sign_ctx, slot, hash, own_rank( self, slot ), self->shred_version );
409 12 : FD_TEST( !vote_events_full( self->vote_events ) );
410 12 : vote_events_push( self->vote_events, (ag_event_vote_t){ .seq = self->seq++, .ts = self->now, .vote = vote } );
411 :
412 12 : slot_state_ele_t * state = state_mut( self, slot );
413 12 : if( FD_UNLIKELY( state->pending_block ) ) pending_dlist_ele_remove( self->pending_dlist, state, self->slot_states->pool );
414 12 : state->voted = 1;
415 12 : state->voted_notar = 1;
416 12 : state->pending_block = 0;
417 12 : memcpy( state->voted_notar_hash, hash, sizeof(ag_block_hash_t) );
418 :
419 12 : try_final( self, slot, hash );
420 12 : return 1;
421 12 : }
422 :
423 : static void
424 : try_skip_window( ag_votor_t * self,
425 15 : ulong slot ) {
426 15 : FD_TEST( slot>=first_unpruned_slot( self ) );
427 :
428 15 : ulong window_start = ag_first_slot_in_window( slot );
429 75 : for( ulong s=window_start; s<window_start+AG_SLOTS_PER_WINDOW; s++ ) {
430 60 : if( FD_UNLIKELY( has_voted( self, s ) ) ) continue;
431 :
432 36 : slot_state_ele_t * state = state_mut( self, s );
433 36 : state->voted = 1;
434 36 : state->bad_window = 1;
435 :
436 36 : ag_vote_t vote = ag_vote_construct_skip( self->bls_sign_fn, self->bls_sign_ctx, s, own_rank( self, s ), self->shred_version );
437 36 : FD_TEST( !vote_events_full( self->vote_events ) );
438 36 : vote_events_push( self->vote_events, (ag_event_vote_t){ .seq = self->seq++, .ts = self->now, .vote = vote } );
439 36 : }
440 15 : }
441 :
442 : static void
443 12 : check_pending_blocks( ag_votor_t * self ) {
444 12 : slot_state_map_t * map = self->slot_states->map;
445 12 : slot_state_ele_t * pool = self->slot_states->pool;
446 12 : ulong * slots = self->scratch.slots;
447 12 : ulong cnt = 0UL;
448 :
449 12 : for( pending_dlist_iter_t iter = pending_dlist_iter_fwd_init( self->pending_dlist, pool );
450 18 : !pending_dlist_iter_done( iter, self->pending_dlist, pool );
451 12 : iter = pending_dlist_iter_fwd_next( iter, self->pending_dlist, pool ) ) {
452 6 : slot_state_ele_t const * ele = pending_dlist_iter_ele_const( iter, self->pending_dlist, pool );
453 6 : if( FD_LIKELY( cnt<self->slot_max ) ) slots[ cnt++ ] = ele->slot;
454 6 : }
455 12 : slot_sort_inplace( slots, cnt );
456 :
457 18 : for( ulong i=0UL; i<cnt; i++ ) {
458 6 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( map, &slots[i], NULL, pool );
459 6 : if( FD_LIKELY( ele && ele->pending_block ) ) try_notar( self, slots[i], &ele->pending_block_info );
460 6 : }
461 12 : }
462 :
463 : static void
464 3 : prune( ag_votor_t * self ) {
465 3 : ulong first_unpruned = first_unpruned_slot( self );
466 3 : for( ulong slot=self->root; slot<first_unpruned; slot++ ) {
467 0 : slot_state_ele_t * ele = slot_state_map_ele_remove( self->slot_states->map, &slot, NULL, self->slot_states->pool );
468 0 : if( FD_LIKELY( ele ) ) {
469 0 : if( FD_UNLIKELY( ele->pending_block ) ) pending_dlist_ele_remove( self->pending_dlist, ele, self->slot_states->pool );
470 0 : if( FD_LIKELY ( !timer_idle( ele ) ) ) timeout_dlist_ele_remove( self->timeout_dlist, ele, self->slot_states->pool );
471 0 : slot_state_pool_ele_release( self->slot_states->pool, ele );
472 0 : }
473 0 : }
474 3 : self->root = first_unpruned;
475 3 : }
476 :
477 : static void
478 : handle_cert_created( ag_votor_t * self,
479 6 : ag_cert_t const * cert ) {
480 6 : ulong slot = ag_cert_slot( cert );
481 :
482 6 : switch( cert->kind ) {
483 :
484 3 : case AG_CERT_KIND_FINAL:
485 3 : case AG_CERT_KIND_FAST_FINAL:
486 3 : set_timeouts( self, ag_first_slot_in_window( slot ) );
487 :
488 3 : self->highest_final_cert_slot = fd_ulong_max( self->highest_final_cert_slot, slot );
489 3 : prune( self );
490 3 : break;
491 :
492 3 : case AG_CERT_KIND_NOTAR: {
493 3 : uchar const * hash = ag_cert_block_hash( cert );
494 :
495 3 : slot_state_ele_t * state = state_mut( self, slot );
496 3 : state->block_notarized = 1;
497 3 : memcpy( state->block_notarized_hash, hash, sizeof(ag_block_hash_t) );
498 :
499 3 : try_final( self, slot, hash );
500 3 : break;
501 3 : }
502 :
503 0 : case AG_CERT_KIND_NOTAR_FALLBACK:
504 0 : case AG_CERT_KIND_SKIP:
505 0 : break;
506 :
507 0 : default:
508 0 : FD_LOG_CRIT(( "unreachable" ));
509 6 : }
510 :
511 6 : FD_TEST( !cert_events_full( self->cert_events ) );
512 6 : cert_events_push( self->cert_events, (ag_event_cert_t){ .seq = self->seq++, .ts = self->now, .cert = *cert } );
513 6 : }
514 :
515 : void
516 : ag_votor_advance_epoch( ag_votor_t * self,
517 : ulong epoch_rank,
518 21 : ulong epoch_slot ) {
519 21 : if( FD_UNLIKELY( self->curr_epoch_slot==ULONG_MAX ) ) {
520 21 : self->curr_epoch_rank = epoch_rank;
521 21 : self->curr_epoch_slot = epoch_slot;
522 21 : } else if( FD_UNLIKELY( self->next_epoch_slot==ULONG_MAX ) ) {
523 0 : self->next_epoch_rank = epoch_rank;
524 0 : self->next_epoch_slot = epoch_slot;
525 0 : } else {
526 0 : self->prev_epoch_rank = self->curr_epoch_rank;
527 0 : self->prev_epoch_slot = self->curr_epoch_slot;
528 0 : self->curr_epoch_rank = self->next_epoch_rank;
529 0 : self->curr_epoch_slot = self->next_epoch_slot;
530 0 : self->next_epoch_rank = epoch_rank;
531 0 : self->next_epoch_slot = epoch_slot;
532 0 : }
533 21 : }
534 :
535 : void
536 : ag_votor_handle_pool_event( ag_votor_t * self,
537 : ag_event_pool_t const * event,
538 15 : long now ) {
539 15 : self->now = now;
540 :
541 15 : if( FD_UNLIKELY( should_ignore_pool_event( self, event ) ) ) return;
542 :
543 15 : switch( event->kind ) {
544 :
545 3 : case AG_EVENT_POOL_PARENT_READY: {
546 3 : ulong slot = event->parent_ready.slot;
547 3 : ag_block_id_t const * parent = &event->parent_ready.parent;
548 :
549 3 : slot_state_ele_t * state = state_mut( self, slot );
550 3 : int dup = 0;
551 3 : for( ulong i=0UL; i<state->parents_ready_cnt; i++ ) {
552 0 : if( FD_UNLIKELY( ag_block_id_eq( &state->parents_ready[i], parent ) ) ) { dup = 1; break; }
553 0 : }
554 3 : if( FD_LIKELY( !dup ) ) {
555 3 : FD_TEST( state->parents_ready_cnt<PARENTS_READY_MAX );
556 3 : state->parents_ready[ state->parents_ready_cnt++ ] = *parent;
557 3 : }
558 :
559 3 : check_pending_blocks( self );
560 3 : set_timeouts( self, slot );
561 3 : break;
562 3 : }
563 :
564 3 : case AG_EVENT_POOL_SAFE_TO_NOTAR: {
565 3 : ulong slot = event->safe_to_notar.slot;
566 3 : uchar const * hash = event->safe_to_notar.hash;
567 :
568 3 : ag_vote_t vote = ag_vote_construct_notar_fallback( self->bls_sign_fn, self->bls_sign_ctx, slot, hash, own_rank( self, slot ), self->shred_version );
569 3 : FD_TEST( !vote_events_full( self->vote_events ) );
570 3 : vote_events_push( self->vote_events, (ag_event_vote_t){ .seq = self->seq++, .ts = self->now, .vote = vote } );
571 3 : try_skip_window( self, slot );
572 3 : state_mut( self, slot )->bad_window = 1;
573 3 : break;
574 3 : }
575 :
576 3 : case AG_EVENT_POOL_SAFE_TO_SKIP: {
577 3 : ulong slot = event->safe_to_skip;
578 :
579 3 : ag_vote_t vote = ag_vote_construct_skip_fallback( self->bls_sign_fn, self->bls_sign_ctx, slot, own_rank( self, slot ), self->shred_version );
580 3 : FD_TEST( !vote_events_full( self->vote_events ) );
581 3 : vote_events_push( self->vote_events, (ag_event_vote_t){ .seq = self->seq++, .ts = self->now, .vote = vote } );
582 3 : try_skip_window( self, slot );
583 3 : state_mut( self, slot )->bad_window = 1;
584 3 : break;
585 3 : }
586 :
587 6 : case AG_EVENT_POOL_CERT_CREATED:
588 6 : handle_cert_created( self, &event->cert_created );
589 6 : break;
590 :
591 0 : case AG_EVENT_POOL_STANDSTILL: {
592 0 : ag_standstill_t const * standstill = &event->standstill;
593 0 : FD_TEST( cert_events_avail( self->cert_events )>=standstill->cert_cnt );
594 0 : for( ulong i=0UL; i<standstill->cert_cnt; i++ ) cert_events_push( self->cert_events, (ag_event_cert_t){ .seq = self->seq++, .ts = self->now, .cert = standstill->certs[i] } );
595 0 : FD_TEST( vote_events_avail( self->vote_events )>=standstill->vote_cnt );
596 0 : for( ulong i=0UL; i<standstill->vote_cnt; i++ ) vote_events_push( self->vote_events, (ag_event_vote_t){ .seq = self->seq++, .ts = self->now, .vote = standstill->votes[i] } );
597 0 : break;
598 0 : }
599 :
600 0 : default:
601 0 : FD_LOG_ERR(( "invalid pool event kind %d", event->kind ));
602 15 : }
603 15 : }
604 :
605 : void
606 : ag_votor_handle_block_event( ag_votor_t * self,
607 36 : ag_event_block_t const * event ) {
608 36 : ulong slot = event->slot;
609 36 : if( FD_UNLIKELY( slot<=self->highest_final_cert_slot || is_retired( self, slot ) ) ) return;
610 :
611 36 : switch( event->kind ) {
612 36 : case AG_EVENT_BLOCK_FIRST_SHRED:
613 36 : state_mut( self, slot )->received_shred = 1;
614 36 : break;
615 :
616 0 : case AG_EVENT_BLOCK_INVALID_BLOCK:
617 0 : FD_LOG_WARNING(( "invalid block from leader for slot %lu, skipping window", slot ));
618 0 : try_skip_window( self, slot );
619 0 : break;
620 :
621 0 : default:
622 0 : FD_LOG_ERR(( "invalid block event kind %d", event->kind ));
623 36 : }
624 36 : }
625 :
626 : void
627 : ag_votor_handle_replay_event( ag_votor_t * self,
628 15 : ag_event_replay_t const * event ) {
629 15 : ulong slot = event->slot;
630 15 : if( FD_UNLIKELY( slot<first_unpruned_slot( self ) || is_retired( self, slot ) ) ) return;
631 :
632 15 : switch( event->kind ) {
633 15 : case AG_EVENT_REPLAY_COMPLETED:
634 15 : if( FD_UNLIKELY( has_voted( self, slot ) ) ) {
635 0 : FD_LOG_WARNING(( "not voting for block in slot %lu, already voted", slot ));
636 0 : return;
637 0 : }
638 15 : if( FD_LIKELY( try_notar( self, slot, &event->block_info ) ) ) {
639 9 : check_pending_blocks( self );
640 9 : } else {
641 6 : slot_state_ele_t * state = state_mut( self, slot );
642 6 : if( FD_LIKELY( !state->pending_block ) ) pending_dlist_ele_push_tail( self->pending_dlist, state, self->slot_states->pool );
643 6 : state->pending_block = 1;
644 6 : state->pending_block_info = event->block_info;
645 6 : }
646 15 : break;
647 :
648 0 : case AG_EVENT_REPLAY_DEAD:
649 0 : FD_LOG_WARNING(( "replay marked slot %lu dead, skipping window", slot ));
650 0 : try_skip_window( self, slot );
651 0 : break;
652 :
653 0 : default:
654 0 : FD_LOG_ERR(( "invalid replay event kind %d", event->kind ));
655 15 : }
656 15 : }
657 :
658 : void
659 : ag_votor_handle_timeout_event( ag_votor_t * self,
660 33 : ag_event_timeout_t const * event ) {
661 33 : ulong slot = event->slot;
662 33 : if( FD_UNLIKELY( slot<=self->highest_final_cert_slot || is_retired( self, slot ) ) ) return;
663 :
664 21 : switch( event->kind ) {
665 21 : case AG_EVENT_TIMEOUT:
666 21 : if( FD_UNLIKELY( !has_voted( self, slot ) ) ) try_skip_window( self, slot );
667 21 : break;
668 :
669 0 : case AG_EVENT_TIMEOUT_CRASHED_LEADER:
670 0 : if( FD_UNLIKELY( !received_shred( self, slot ) && !has_voted( self, slot ) ) ) try_skip_window( self, slot );
671 0 : break;
672 :
673 0 : default:
674 0 : FD_LOG_ERR(( "invalid timeout kind %d", event->kind ));
675 21 : }
676 21 : }
677 :
678 : int
679 : ag_votor_poll_timeout_event( ag_votor_t * self,
680 : long now,
681 36 : ag_event_timeout_t * event ) {
682 36 : self->now = now;
683 :
684 36 : slot_state_ele_t * pool = self->slot_states->pool;
685 :
686 36 : for( timeout_dlist_iter_t iter = timeout_dlist_iter_fwd_init( self->timeout_dlist, pool );
687 36 : !timeout_dlist_iter_done( iter, self->timeout_dlist, pool );
688 36 : iter = timeout_dlist_iter_fwd_next( iter, self->timeout_dlist, pool ) ) {
689 30 : slot_state_ele_t * ele = timeout_dlist_iter_ele( iter, self->timeout_dlist, pool );
690 :
691 30 : int kind;
692 30 : if ( FD_UNLIKELY( ele->timeout_crashed_leader<=now ) ) { kind = AG_EVENT_TIMEOUT_CRASHED_LEADER; ele->timeout_crashed_leader = LONG_MAX; }
693 24 : else if( FD_UNLIKELY( ele->timeout <=now ) ) { kind = AG_EVENT_TIMEOUT; ele->timeout = LONG_MAX; }
694 0 : else continue;
695 :
696 30 : event->seq = self->seq++;
697 30 : event->ts = self->now;
698 30 : event->kind = kind;
699 30 : event->slot = ele->slot;
700 30 : if( FD_UNLIKELY( timer_idle( ele ) ) ) timeout_dlist_ele_remove( self->timeout_dlist, ele, pool );
701 30 : return 1;
702 30 : }
703 6 : return 0;
704 36 : }
705 :
706 : int
707 : ag_votor_poll_vote_event( ag_votor_t * self,
708 60 : ag_event_vote_t * event ) {
709 60 : if( FD_LIKELY( vote_events_empty( self->vote_events ) ) ) return 0;
710 51 : *event = vote_events_pop( self->vote_events );
711 51 : return 1;
712 60 : }
713 :
714 : int
715 : ag_votor_poll_cert_event( ag_votor_t * self,
716 0 : ag_event_cert_t * event ) {
717 0 : if( FD_LIKELY( cert_events_empty( self->cert_events ) ) ) return 0;
718 0 : *event = cert_events_pop( self->cert_events );
719 0 : return 1;
720 0 : }
|
