Line data Source code
1 : #include "ag_votor.h"
2 :
3 : struct vote_event {
4 : uchar reason;
5 : ag_vote_t vote;
6 : };
7 : typedef struct vote_event vote_event_t;
8 :
9 : #define QUEUE_NAME vote_events
10 0 : #define QUEUE_T vote_event_t
11 : #include "../../util/tmpl/fd_queue_dynamic.c"
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 : int pending_block;
24 : ag_block_info_t pending_block_info;
25 : int retired;
26 :
27 : long timeout;
28 :
29 : struct { ulong prev; ulong next; } pending_dlist;
30 : struct { ulong prev; ulong next; } timeout_dlist;
31 : };
32 : typedef struct slot_state_ele slot_state_ele_t;
33 :
34 : #define POOL_NAME slot_state_pool
35 0 : #define POOL_T slot_state_ele_t
36 : #include "../../util/tmpl/fd_pool.c"
37 :
38 : #define MAP_NAME slot_state_map
39 : #define MAP_ELE_T slot_state_ele_t
40 0 : #define MAP_KEY slot
41 : #define MAP_KEY_T ulong
42 0 : #define MAP_KEY_EQ(k0,k1) ((*(k0))==(*(k1)))
43 0 : #define MAP_KEY_HASH(key,seed) (fd_ulong_hash( (*(key)) ^ (seed) ))
44 0 : #define MAP_NEXT next
45 : #include "../../util/tmpl/fd_map_chain.c"
46 :
47 : #define DLIST_NAME pending_dlist
48 : #define DLIST_ELE_T slot_state_ele_t
49 0 : #define DLIST_PREV pending_dlist.prev
50 0 : #define DLIST_NEXT pending_dlist.next
51 : #include "../../util/tmpl/fd_dlist.c"
52 :
53 : #define DLIST_NAME timeout_dlist
54 : #define DLIST_ELE_T slot_state_ele_t
55 0 : #define DLIST_PREV timeout_dlist.prev
56 0 : #define DLIST_NEXT timeout_dlist.next
57 : #include "../../util/tmpl/fd_dlist.c"
58 :
59 : struct slot_states {
60 : slot_state_ele_t * pool;
61 : slot_state_map_t * map;
62 : };
63 : typedef struct slot_states slot_states_t;
64 :
65 : #define SORT_NAME slot_sort
66 0 : #define SORT_KEY_T ulong
67 0 : #define SORT_BEFORE(a,b) ((a)<(b))
68 : #include "../../util/tmpl/fd_sort.c"
69 :
70 : struct epoch_bls_key {
71 : ulong start_slot;
72 : ulong rank;
73 : long ns_per_slot;
74 : uchar bls_key[ FD_BLS_PUB_COMPRESSED_SZ ];
75 : int has_bls_key;
76 : };
77 : typedef struct epoch_bls_key epoch_bls_key_t;
78 :
79 : struct __attribute__((aligned(128UL))) ag_votor {
80 : ulong slot_max;
81 : long now;
82 : ulong root;
83 : ushort shred_version;
84 : long ns_per_slot;
85 :
86 : slot_states_t * slot_states;
87 : ag_parent_ready_tracker_t * parent_ready_tracker; /* Definition 15 over the certs received */
88 : ulong highest_final_cert_slot;
89 : ulong catchup_vote_slot; /* first slot worth a vote while catching up, 0 if none */
90 :
91 : fd_bls_sign_fn bls_sign_fn;
92 : void * bls_sign_ctx;
93 :
94 : epoch_bls_key_t prev_epoch;
95 : epoch_bls_key_t curr_epoch;
96 : epoch_bls_key_t next_epoch;
97 :
98 : vote_event_t * vote_events;
99 : pending_dlist_t * pending_dlist;
100 : timeout_dlist_t * timeout_dlist[ AG_SLOTS_PER_WINDOW ];
101 :
102 : struct {
103 : ulong * slots;
104 : ag_parent_ready_t * parent_readys;
105 : } scratch;
106 : };
107 :
108 : static slot_state_ele_t *
109 : state_mut( ag_votor_t * self,
110 0 : ulong slot ) {
111 0 : slot_state_ele_t * ele = slot_state_map_ele_query( self->slot_states->map, &slot, NULL, self->slot_states->pool );
112 0 : if( FD_LIKELY( ele ) ) return ele;
113 :
114 0 : FD_TEST( slot_state_pool_free( self->slot_states->pool ) );
115 :
116 0 : ele = slot_state_pool_ele_acquire( self->slot_states->pool );
117 0 : fd_memset( ele, 0, sizeof(slot_state_ele_t) );
118 0 : ele->slot = slot;
119 0 : ele->timeout = LONG_MAX;
120 0 : slot_state_map_ele_insert( self->slot_states->map, ele, self->slot_states->pool );
121 0 : return ele;
122 0 : }
123 :
124 : static void
125 : push_vote( ag_votor_t * self,
126 : ag_vote_t vote,
127 0 : uchar reason ) {
128 0 : FD_TEST( !vote_events_full( self->vote_events ) );
129 0 : vote_events_push( self->vote_events, (vote_event_t){ .reason = reason, .vote = vote } );
130 0 : }
131 :
132 : FD_FN_PURE static epoch_bls_key_t const *
133 : own_epoch( ag_votor_t const * self,
134 0 : ulong slot ) {
135 0 : if( FD_UNLIKELY( slot>=self->next_epoch.start_slot ) ) return &self->next_epoch;
136 0 : if( FD_LIKELY( slot>=self->curr_epoch.start_slot ) ) return &self->curr_epoch;
137 0 : return &self->prev_epoch;
138 0 : }
139 :
140 : /* No crashed-leader timeout. Agave tracks one, but with
141 : delta_first_fec_set = delta_block its deadline lands on the first
142 : slot's timeout, so it never skips a window earlier. */
143 :
144 : static void
145 : set_timeouts( ag_votor_t * self,
146 0 : ulong slot ) {
147 0 : FD_TEST( ag_is_start_of_window( slot ) );
148 :
149 0 : long ns_per_slot = own_epoch( self, slot )->ns_per_slot; /* the window's own epoch, not the latest one announced */
150 0 : if( FD_UNLIKELY( !ns_per_slot ) ) ns_per_slot = self->ns_per_slot;
151 0 : long deadline = self->now + AG_DELTA_TIMEOUT_NS + ns_per_slot;
152 :
153 0 : for( ulong s=slot; s<slot+AG_SLOTS_PER_WINDOW; s++ ) {
154 0 : deadline += fd_long_if( ag_is_start_of_window( s ), 0L, ns_per_slot );
155 :
156 : /* A slot's deadline is now plus an offset fixed by its position in the
157 : window, so each position's list fills in deadline order and its head
158 : is its earliest timer. The walk back from the tail only runs if the
159 : slot length changed (block duration feature activation), or the clock
160 : stepped back. */
161 :
162 0 : slot_state_ele_t * ele = state_mut( self, s );
163 0 : timeout_dlist_t * list = self->timeout_dlist[ s%AG_SLOTS_PER_WINDOW ];
164 0 : slot_state_ele_t * pool = self->slot_states->pool;
165 0 : if( FD_LIKELY( ele->timeout!=LONG_MAX ) ) {
166 0 : if( FD_LIKELY( ele->timeout<=deadline ) ) continue;
167 0 : timeout_dlist_ele_remove( list, ele, pool );
168 0 : }
169 0 : ele->timeout = deadline;
170 :
171 0 : timeout_dlist_iter_t iter = timeout_dlist_iter_rev_init( list, pool );
172 0 : while( FD_UNLIKELY( !timeout_dlist_iter_done( iter, list, pool ) && timeout_dlist_iter_ele( iter, list, pool )->timeout>deadline ) ) {
173 0 : iter = timeout_dlist_iter_rev_next( iter, list, pool );
174 0 : }
175 0 : if( FD_LIKELY( !timeout_dlist_iter_done( iter, list, pool ) ) ) timeout_dlist_ele_insert_after( list, ele, timeout_dlist_iter_ele( iter, list, pool ), pool );
176 0 : else timeout_dlist_ele_push_head ( list, ele, pool );
177 0 : }
178 0 : }
179 :
180 : static slot_state_ele_t *
181 0 : next_timeout( ag_votor_t const * self ) {
182 0 : slot_state_ele_t * pool = self->slot_states->pool;
183 0 : slot_state_ele_t * head = NULL;
184 0 : for( ulong k=0UL; k<AG_SLOTS_PER_WINDOW; k++ ) {
185 0 : if( FD_LIKELY( timeout_dlist_is_empty( self->timeout_dlist[ k ], pool ) ) ) continue;
186 0 : slot_state_ele_t * ele = timeout_dlist_ele_peek_head( self->timeout_dlist[ k ], pool );
187 0 : if( !head || ele->timeout<head->timeout ) head = ele;
188 0 : }
189 0 : return head;
190 0 : }
191 :
192 : ulong
193 0 : ag_votor_align( void ) {
194 0 : return alignof(ag_votor_t);
195 0 : }
196 :
197 : ulong
198 0 : ag_votor_footprint( ulong slot_max ) {
199 0 : if( FD_UNLIKELY( slot_max<AG_SLOTS_PER_WINDOW ) ) return 0UL;
200 0 : ulong events_max = slot_max*( AG_NOTAR_FALLBACK_CERT_MAX + 1UL /* notar */ + 1UL /* skip */ );
201 0 : ulong slot_state_chain_cnt = slot_state_map_chain_cnt_est( slot_max );
202 0 : ulong ready_max = slot_max + 2UL*AG_SLOTS_PER_WINDOW + 1UL; /* see ag_pool_footprint, plus the window below first_unpruned_slot */
203 0 : return FD_LAYOUT_FINI(
204 0 : FD_LAYOUT_APPEND(
205 0 : FD_LAYOUT_APPEND(
206 0 : FD_LAYOUT_APPEND(
207 0 : FD_LAYOUT_APPEND(
208 0 : FD_LAYOUT_APPEND(
209 0 : FD_LAYOUT_APPEND(
210 0 : FD_LAYOUT_APPEND(
211 0 : FD_LAYOUT_APPEND(
212 0 : FD_LAYOUT_APPEND(
213 0 : FD_LAYOUT_APPEND(
214 0 : FD_LAYOUT_INIT,
215 0 : alignof(ag_votor_t), sizeof(ag_votor_t) ),
216 0 : alignof(slot_states_t), sizeof(slot_states_t) ),
217 0 : slot_state_pool_align(), slot_state_pool_footprint( slot_max ) ),
218 0 : slot_state_map_align(), slot_state_map_footprint ( slot_state_chain_cnt ) ),
219 0 : pending_dlist_align(), pending_dlist_footprint() ),
220 0 : timeout_dlist_align(), timeout_dlist_footprint()*AG_SLOTS_PER_WINDOW ),
221 0 : vote_events_align(), vote_events_footprint( events_max ) ),
222 0 : alignof(ulong), sizeof(ulong)*slot_max ),
223 0 : ag_parent_ready_tracker_align(), ag_parent_ready_tracker_footprint( ready_max ) ),
224 0 : alignof(ag_parent_ready_t), sizeof(ag_parent_ready_t)*slot_max ),
225 0 : ag_votor_align() );
226 0 : }
227 :
228 : void *
229 : ag_votor_new( void * mem,
230 : ulong slot_max,
231 0 : ulong seed ) {
232 0 : if( FD_UNLIKELY( !mem ) ) {
233 0 : FD_LOG_WARNING(( "NULL mem" ));
234 0 : return NULL;
235 0 : }
236 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, ag_votor_align() ) ) ) {
237 0 : FD_LOG_WARNING(( "misaligned mem" ));
238 0 : return NULL;
239 0 : }
240 0 : ulong footprint = ag_votor_footprint( slot_max );
241 0 : if( FD_UNLIKELY( !footprint ) ) {
242 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
243 0 : return NULL;
244 0 : }
245 0 : fd_memset( mem, 0, footprint );
246 :
247 0 : ulong events_max = slot_max*( AG_NOTAR_FALLBACK_CERT_MAX + 1UL /* notar */ + 1UL /* skip */ );
248 0 : ulong slot_state_chain_cnt = slot_state_map_chain_cnt_est( slot_max );
249 0 : ulong ready_max = slot_max + 2UL*AG_SLOTS_PER_WINDOW + 1UL;
250 :
251 0 : FD_SCRATCH_ALLOC_INIT( l, mem );
252 0 : ag_votor_t * votor = FD_SCRATCH_ALLOC_APPEND( l, alignof(ag_votor_t), sizeof(ag_votor_t) );
253 0 : void * slot_states = FD_SCRATCH_ALLOC_APPEND( l, alignof(slot_states_t), sizeof(slot_states_t) );
254 0 : void * slot_state_pool = FD_SCRATCH_ALLOC_APPEND( l, slot_state_pool_align(), slot_state_pool_footprint( slot_max ) );
255 0 : void * slot_state_map = FD_SCRATCH_ALLOC_APPEND( l, slot_state_map_align(), slot_state_map_footprint ( slot_state_chain_cnt ) );
256 0 : void * pending_dlist = FD_SCRATCH_ALLOC_APPEND( l, pending_dlist_align(), pending_dlist_footprint() );
257 0 : uchar * timeout_dlist = FD_SCRATCH_ALLOC_APPEND( l, timeout_dlist_align(), timeout_dlist_footprint()*AG_SLOTS_PER_WINDOW );
258 0 : void * vote_events = FD_SCRATCH_ALLOC_APPEND( l, vote_events_align(), vote_events_footprint( events_max ) );
259 0 : void * slot_scratch = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), sizeof(ulong)*slot_max );
260 0 : void * ready_tracker = FD_SCRATCH_ALLOC_APPEND( l, ag_parent_ready_tracker_align(), ag_parent_ready_tracker_footprint( ready_max ) );
261 0 : void * ready_scratch = FD_SCRATCH_ALLOC_APPEND( l, alignof(ag_parent_ready_t), sizeof(ag_parent_ready_t)*slot_max );
262 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, ag_votor_align() ) == (ulong)mem + footprint );
263 :
264 0 : votor->slot_max = slot_max;
265 0 : votor->now = 0L;
266 0 : votor->root = ULONG_MAX;
267 0 : votor->shred_version = 0;
268 0 : votor->ns_per_slot = 0L;
269 0 : votor->bls_sign_fn = NULL;
270 0 : votor->bls_sign_ctx = NULL;
271 0 : votor->slot_states = (slot_states_t *)slot_states;
272 0 : votor->slot_states->pool = slot_state_pool_join( slot_state_pool_new( slot_state_pool, slot_max ) );
273 0 : votor->slot_states->map = slot_state_map_join ( slot_state_map_new ( slot_state_map, slot_state_chain_cnt, seed ) );
274 0 : votor->highest_final_cert_slot = ULONG_MAX;
275 0 : votor->catchup_vote_slot = 0UL;
276 0 : votor->prev_epoch = (epoch_bls_key_t){ .start_slot = ULONG_MAX, .rank = USHORT_MAX };
277 0 : votor->curr_epoch = (epoch_bls_key_t){ .start_slot = ULONG_MAX, .rank = USHORT_MAX };
278 0 : votor->next_epoch = (epoch_bls_key_t){ .start_slot = ULONG_MAX, .rank = USHORT_MAX };
279 0 : votor->vote_events = vote_events_join( vote_events_new( vote_events, events_max ) );
280 0 : votor->pending_dlist = pending_dlist_join( pending_dlist_new( pending_dlist ) );
281 0 : for( ulong k=0UL; k<AG_SLOTS_PER_WINDOW; k++ ) votor->timeout_dlist[ k ] = timeout_dlist_join( timeout_dlist_new( timeout_dlist+k*timeout_dlist_footprint() ) );
282 0 : votor->scratch.slots = (ulong *)slot_scratch;
283 0 : votor->parent_ready_tracker = ag_parent_ready_tracker_join( ag_parent_ready_tracker_new( ready_tracker, ready_max, seed ) );
284 0 : votor->scratch.parent_readys = (ag_parent_ready_t *)ready_scratch;
285 :
286 0 : return mem;
287 0 : }
288 :
289 : ag_votor_t *
290 0 : ag_votor_join( void * mem ) {
291 0 : ag_votor_t * votor = (ag_votor_t *)mem;
292 0 : if( FD_UNLIKELY( !votor ) ) {
293 0 : FD_LOG_WARNING(( "NULL mem" ));
294 0 : return NULL;
295 0 : }
296 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)votor, ag_votor_align() ) ) ) {
297 0 : FD_LOG_WARNING(( "misaligned mem" ));
298 0 : return NULL;
299 0 : }
300 0 : return votor;
301 0 : }
302 :
303 : void *
304 0 : ag_votor_leave( ag_votor_t const * votor ) {
305 0 : if( FD_UNLIKELY( !votor ) ) {
306 0 : FD_LOG_WARNING(( "NULL votor" ));
307 0 : return NULL;
308 0 : }
309 0 : return (void *)votor;
310 0 : }
311 :
312 : void *
313 0 : ag_votor_delete( void * mem ) {
314 0 : if( FD_UNLIKELY( !mem ) ) {
315 0 : FD_LOG_WARNING(( "NULL mem" ));
316 0 : return NULL;
317 0 : }
318 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, ag_votor_align() ) ) ) {
319 0 : FD_LOG_WARNING(( "misaligned mem" ));
320 0 : return NULL;
321 0 : }
322 0 : return mem;
323 0 : }
324 :
325 : void
326 : ag_votor_init( ag_votor_t * self,
327 : ag_block_id_t const * root,
328 : long now,
329 : long ns_per_slot,
330 : ushort shred_version,
331 : fd_bls_sign_fn sign_fn,
332 0 : void * sign_ctx ) {
333 0 : FD_TEST( sign_fn );
334 0 : self->now = now;
335 0 : self->root = root->slot;
336 0 : self->shred_version = shred_version;
337 0 : self->ns_per_slot = ns_per_slot;
338 0 : self->bls_sign_fn = sign_fn;
339 0 : self->bls_sign_ctx = sign_ctx;
340 :
341 0 : slot_state_ele_t * state = state_mut( self, root->slot );
342 0 : state->voted = 1;
343 0 : state->voted_notar = 1;
344 0 : state->block_notarized = 1;
345 0 : state->retired = 1;
346 0 : memcpy( state->voted_notar_hash, root->hash, sizeof(ag_block_hash_t) );
347 0 : memcpy( state->block_notarized_hash, root->hash, sizeof(ag_block_hash_t) );
348 :
349 0 : for( ulong s=ag_first_slot_in_window( root->slot ); s<root->slot; s++ ) {
350 0 : slot_state_ele_t * below = state_mut( self, s );
351 0 : below->voted = 1;
352 0 : below->retired = 1;
353 0 : }
354 :
355 0 : self->highest_final_cert_slot = root->slot;
356 :
357 0 : ulong ready_cnt;
358 0 : self->parent_ready_tracker->root = fd_ulong_sat_sub( ag_first_slot_in_window( fd_ulong_sat_sub( root->slot, AG_REWARD_SLOT_DELTA ) ), AG_SLOTS_PER_WINDOW );
359 0 : ready_cnt = ag_parent_ready_tracker_mark_notar_fallback( self->parent_ready_tracker, root, self->scratch.parent_readys );
360 0 : for( ulong i=0UL; i<ready_cnt; i++ ) ag_parent_ready_state_map_ele_query( self->parent_ready_tracker->states.map, &self->scratch.parent_readys[i].slot, NULL, self->parent_ready_tracker->states.pool )->ready = 0;
361 0 : }
362 :
363 : void
364 : ag_votor_arm_skip_timeouts( ag_votor_t * self,
365 0 : long now ) {
366 0 : FD_TEST( self->root!=ULONG_MAX );
367 0 : self->now = fd_long_max( self->now, now );
368 0 : set_timeouts( self, ag_first_slot_in_window( self->root ) );
369 0 : }
370 :
371 : void
372 0 : ag_votor_fini( ag_votor_t * self ) {
373 0 : self->root = ULONG_MAX;
374 0 : self->highest_final_cert_slot = ULONG_MAX;
375 0 : }
376 :
377 : FD_FN_PURE ag_votor_metrics_t
378 0 : ag_votor_metrics( ag_votor_t const * self ) {
379 0 : return (ag_votor_metrics_t){
380 0 : .slot_state_pool_used = slot_state_pool_used( self->slot_states->pool ),
381 0 : .slot_state_pool_free = slot_state_pool_free( self->slot_states->pool ),
382 0 : .highest_final_cert_slot = self->highest_final_cert_slot,
383 0 : .vote_events_cnt = vote_events_cnt( self->vote_events )
384 0 : };
385 0 : }
386 :
387 : FD_FN_PURE static int
388 : is_retired( ag_votor_t const * self,
389 0 : ulong slot ) {
390 0 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
391 0 : return ele && ele->retired;
392 0 : }
393 :
394 : FD_FN_PURE static int
395 : has_voted( ag_votor_t const * self,
396 0 : ulong slot ) {
397 0 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
398 0 : return ele && ele->voted;
399 0 : }
400 :
401 : FD_FN_PURE static ulong
402 0 : first_unpruned_slot( ag_votor_t const * self ) {
403 0 : return ag_first_slot_in_window( fd_ulong_sat_sub( self->highest_final_cert_slot, AG_REWARD_SLOT_DELTA ) );
404 0 : }
405 :
406 : static int
407 : should_ignore_pool_event( ag_votor_t const * self,
408 0 : ag_pool_event_t const * event ) {
409 0 : ulong slot;
410 0 : switch( event->kind ) {
411 0 : case AG_POOL_EVENT_PARENT_READY: slot = event->parent_ready.slot; break;
412 0 : case AG_POOL_EVENT_SAFE_TO_NOTAR: slot = event->safe_to_notar.slot; break;
413 0 : case AG_POOL_EVENT_SAFE_TO_SKIP: slot = event->safe_to_skip; break;
414 0 : case AG_POOL_EVENT_CERT_CREATED: slot = ag_cert_slot( &event->cert_created ); break;
415 0 : default: FD_LOG_CRIT(( "unreachable" ));
416 0 : }
417 0 : switch( event->kind ) {
418 0 : case AG_POOL_EVENT_CERT_CREATED: return slot<first_unpruned_slot( self );
419 0 : case AG_POOL_EVENT_PARENT_READY:
420 0 : case AG_POOL_EVENT_SAFE_TO_NOTAR:
421 0 : case AG_POOL_EVENT_SAFE_TO_SKIP: return slot<first_unpruned_slot( self ) || is_retired( self, slot );
422 0 : default: FD_LOG_CRIT(( "unreachable" ));
423 0 : }
424 0 : }
425 :
426 : static void
427 : try_final( ag_votor_t * self,
428 : ulong slot,
429 0 : ag_block_hash_t const hash ) {
430 0 : FD_TEST( slot>=first_unpruned_slot( self ) );
431 0 : epoch_bls_key_t const * epoch = own_epoch( self, slot );
432 :
433 0 : slot_state_ele_t const * state = slot_state_map_ele_query_const( self->slot_states->map, &slot, NULL, self->slot_states->pool );
434 0 : int notarized = state && state->block_notarized && !memcmp( state->block_notarized_hash, hash, sizeof(ag_block_hash_t) );
435 0 : int voted_notar = state && state->voted_notar && !memcmp( state->voted_notar_hash, hash, sizeof(ag_block_hash_t) );
436 0 : int not_bad = !( state && state->bad_window );
437 0 : if( FD_LIKELY( notarized && voted_notar && not_bad ) ) {
438 0 : state_mut( self, slot )->retired = 1;
439 0 : if( FD_UNLIKELY( !epoch->has_bls_key || slot<self->catchup_vote_slot ) ) return;
440 0 : ag_vote_t vote = ag_vote_construct_final( self->bls_sign_fn, self->bls_sign_ctx, epoch->bls_key, slot, (ushort)epoch->rank, self->shred_version );
441 0 : push_vote( self, vote, AG_VOTOR_REASON_BLOCK_NOTARIZED );
442 0 : }
443 0 : }
444 :
445 : static int
446 : try_notar( ag_votor_t * self,
447 : ulong slot,
448 : ag_block_info_t const * block_info,
449 0 : uchar reason ) {
450 0 : FD_TEST( slot>=first_unpruned_slot( self ) );
451 0 : epoch_bls_key_t const * epoch = own_epoch( self, slot );
452 0 : if( FD_UNLIKELY( has_voted( self, slot ) ) ) return 0;
453 :
454 0 : ag_block_hash_t hash;
455 0 : memcpy( hash, block_info->hash, sizeof(ag_block_hash_t) );
456 0 : ag_block_id_t parent = block_info->parent;
457 :
458 0 : if( FD_UNLIKELY( ag_is_start_of_window( slot ) ) ) {
459 0 : if( FD_UNLIKELY( !ag_parent_ready_tracker_is_parent_ready( self->parent_ready_tracker, slot, &parent ) ) ) return 0;
460 0 : } else {
461 0 : if( FD_UNLIKELY( parent.slot!=slot-1UL ) ) return 0;
462 0 : slot_state_ele_t const * parent_state = slot_state_map_ele_query_const( self->slot_states->map, &parent.slot, NULL, self->slot_states->pool );
463 0 : if( FD_UNLIKELY( !parent_state || !parent_state->voted_notar ) ) return 0;
464 0 : if( FD_UNLIKELY( memcmp( parent_state->voted_notar_hash, parent.hash, sizeof(ag_block_hash_t) )!=0 ) ) return 0;
465 0 : }
466 :
467 0 : if( FD_LIKELY( epoch->has_bls_key && slot>=self->catchup_vote_slot ) ) {
468 0 : ag_vote_t vote = ag_vote_construct_notar( self->bls_sign_fn, self->bls_sign_ctx, epoch->bls_key, slot, hash, (ushort)epoch->rank, self->shred_version );
469 0 : push_vote( self, vote, reason );
470 0 : }
471 :
472 0 : slot_state_ele_t * state = state_mut( self, slot );
473 0 : if( FD_UNLIKELY( state->pending_block ) ) pending_dlist_ele_remove( self->pending_dlist, state, self->slot_states->pool );
474 0 : state->voted = 1;
475 0 : state->voted_notar = 1;
476 0 : state->pending_block = 0;
477 0 : memcpy( state->voted_notar_hash, hash, sizeof(ag_block_hash_t) );
478 :
479 0 : try_final( self, slot, hash );
480 0 : return 1;
481 0 : }
482 :
483 : static void
484 : try_skip_window( ag_votor_t * self,
485 : ulong slot,
486 0 : uchar reason ) {
487 0 : FD_TEST( slot>=first_unpruned_slot( self ) );
488 :
489 0 : ulong window_start = ag_first_slot_in_window( slot );
490 0 : for( ulong s=window_start; s<window_start+AG_SLOTS_PER_WINDOW; s++ ) {
491 0 : if( FD_UNLIKELY( has_voted( self, s ) ) ) continue;
492 :
493 0 : slot_state_ele_t * state = state_mut( self, s );
494 0 : state->voted = 1;
495 0 : state->bad_window = 1;
496 :
497 0 : epoch_bls_key_t const * epoch = own_epoch( self, s );
498 0 : if( FD_UNLIKELY( !epoch->has_bls_key || s<self->catchup_vote_slot ) ) continue;
499 :
500 0 : ag_vote_t vote = ag_vote_construct_skip( self->bls_sign_fn, self->bls_sign_ctx, epoch->bls_key, s, (ushort)epoch->rank, self->shred_version );
501 0 : push_vote( self, vote, reason );
502 0 : }
503 0 : }
504 :
505 : static void
506 : check_pending_blocks( ag_votor_t * self,
507 0 : uchar reason ) {
508 0 : slot_state_map_t * map = self->slot_states->map;
509 0 : slot_state_ele_t * pool = self->slot_states->pool;
510 0 : ulong * slots = self->scratch.slots;
511 0 : ulong cnt = 0UL;
512 :
513 0 : for( pending_dlist_iter_t iter = pending_dlist_iter_fwd_init( self->pending_dlist, pool );
514 0 : !pending_dlist_iter_done( iter, self->pending_dlist, pool );
515 0 : iter = pending_dlist_iter_fwd_next( iter, self->pending_dlist, pool ) ) {
516 0 : slot_state_ele_t const * ele = pending_dlist_iter_ele_const( iter, self->pending_dlist, pool );
517 0 : if( FD_LIKELY( cnt<self->slot_max ) ) slots[ cnt++ ] = ele->slot;
518 0 : }
519 0 : slot_sort_inplace( slots, cnt );
520 :
521 0 : for( ulong i=0UL; i<cnt; i++ ) {
522 0 : slot_state_ele_t const * ele = slot_state_map_ele_query_const( map, &slots[i], NULL, pool );
523 0 : if( FD_LIKELY( ele && ele->pending_block ) ) try_notar( self, slots[i], &ele->pending_block_info, reason );
524 0 : }
525 0 : }
526 :
527 : static void
528 0 : prune( ag_votor_t * self ) {
529 0 : ulong first_unpruned = first_unpruned_slot( self );
530 0 : for( ulong slot=self->root; slot<first_unpruned; slot++ ) {
531 0 : slot_state_ele_t * ele = slot_state_map_ele_remove( self->slot_states->map, &slot, NULL, self->slot_states->pool );
532 0 : if( FD_LIKELY( ele ) ) {
533 0 : if( FD_UNLIKELY( ele->pending_block ) ) pending_dlist_ele_remove( self->pending_dlist, ele, self->slot_states->pool );
534 0 : if( FD_LIKELY ( ele->timeout!=LONG_MAX ) ) timeout_dlist_ele_remove( self->timeout_dlist[ slot%AG_SLOTS_PER_WINDOW ], ele, self->slot_states->pool );
535 0 : slot_state_pool_ele_release( self->slot_states->pool, ele );
536 0 : }
537 0 : }
538 0 : self->root = first_unpruned;
539 0 : ag_parent_ready_tracker_prune( self->parent_ready_tracker, fd_ulong_sat_sub( first_unpruned, AG_SLOTS_PER_WINDOW ) ); /* parents of the window at first_unpruned */
540 0 : }
541 :
542 : static ag_cert_t const *
543 : handle_cert_created( ag_votor_t * self,
544 0 : ag_cert_t const * cert ) {
545 0 : ulong slot = ag_cert_slot( cert );
546 :
547 0 : switch( cert->kind ) {
548 :
549 0 : case AG_CERT_KIND_FINAL:
550 0 : case AG_CERT_KIND_FAST_FINAL:
551 0 : set_timeouts( self, ag_first_slot_in_window( slot ) );
552 :
553 0 : self->highest_final_cert_slot = fd_ulong_max( self->highest_final_cert_slot, slot );
554 0 : prune( self );
555 0 : break;
556 :
557 0 : case AG_CERT_KIND_NOTAR: {
558 0 : uchar const * hash = ag_cert_block_hash( cert );
559 :
560 0 : slot_state_ele_t * state = state_mut( self, slot );
561 0 : state->block_notarized = 1;
562 0 : memcpy( state->block_notarized_hash, hash, sizeof(ag_block_hash_t) );
563 :
564 0 : try_final( self, slot, hash );
565 0 : break;
566 0 : }
567 :
568 0 : case AG_CERT_KIND_NOTAR_FALLBACK:
569 0 : case AG_CERT_KIND_SKIP:
570 0 : break;
571 :
572 0 : default:
573 0 : FD_LOG_CRIT(( "unreachable" ));
574 0 : }
575 :
576 0 : return fd_ptr_if( slot>=self->catchup_vote_slot, cert, NULL );
577 0 : }
578 :
579 : void
580 : ag_votor_advance_epoch( ag_votor_t * self,
581 : long ns_per_slot,
582 : ulong epoch_rank,
583 : ulong epoch_slot,
584 0 : ag_bls_key_t const bls_key ) {
585 0 : epoch_bls_key_t epoch = { .start_slot = epoch_slot, .rank = epoch_rank, .ns_per_slot = ns_per_slot, .has_bls_key = !!bls_key };
586 0 : if( FD_LIKELY( bls_key ) ) memcpy( epoch.bls_key, bls_key, FD_BLS_PUB_COMPRESSED_SZ );
587 :
588 0 : if( FD_UNLIKELY( self->curr_epoch.start_slot==ULONG_MAX ) ) {
589 0 : self->curr_epoch = epoch;
590 0 : } else if( FD_UNLIKELY( self->next_epoch.start_slot==ULONG_MAX ) ) {
591 0 : self->next_epoch = epoch;
592 0 : } else {
593 0 : self->prev_epoch = self->curr_epoch;
594 0 : self->curr_epoch = self->next_epoch;
595 0 : self->next_epoch = epoch;
596 0 : }
597 0 : }
598 :
599 : static epoch_bls_key_t *
600 : epoch_starting_at( ag_votor_t * self,
601 0 : ulong epoch_slot ) {
602 0 : if( epoch_slot==self->prev_epoch.start_slot ) return &self->prev_epoch;
603 0 : if( epoch_slot==self->curr_epoch.start_slot ) return &self->curr_epoch;
604 0 : if( epoch_slot==self->next_epoch.start_slot ) return &self->next_epoch;
605 0 : FD_LOG_CRIT(( "no epoch starts at slot %lu", epoch_slot ));
606 0 : }
607 :
608 : void
609 : ag_votor_set_bls_key( ag_votor_t * self,
610 : ulong epoch_slot,
611 0 : ag_bls_key_t const bls_key ) {
612 0 : epoch_bls_key_t * epoch = epoch_starting_at( self, epoch_slot );
613 0 : epoch->has_bls_key = !!bls_key;
614 0 : if( FD_LIKELY( bls_key ) ) memcpy( epoch->bls_key, bls_key, FD_BLS_PUB_COMPRESSED_SZ );
615 0 : }
616 :
617 : void
618 : ag_votor_set_rank( ag_votor_t * self,
619 : ulong epoch_slot,
620 0 : ulong epoch_rank ) {
621 0 : epoch_starting_at( self, epoch_slot )->rank = epoch_rank;
622 0 : }
623 :
624 : ag_cert_t const *
625 : ag_votor_handle_pool_event( ag_votor_t * self,
626 : ag_pool_event_t const * event,
627 0 : long now ) {
628 0 : self->now = now;
629 :
630 : /* Definition 15 over the certs received, a fast-finalization cert is
631 : a notarization cert (Table 6). Ahead of the ignore filter, a cert
632 : just below first_unpruned_slot can still ready its window start. A
633 : window start that gains a ready parent may unblock a pending block. */
634 :
635 0 : if( FD_UNLIKELY( event->kind==AG_POOL_EVENT_CERT_CREATED ) ) {
636 0 : ag_cert_t const * cert = &event->cert_created;
637 0 : ulong ready_cnt = 0UL;
638 0 : switch( cert->kind ) {
639 0 : case AG_CERT_KIND_FINAL: break;
640 0 : case AG_CERT_KIND_FAST_FINAL:
641 0 : case AG_CERT_KIND_NOTAR:
642 0 : case AG_CERT_KIND_NOTAR_FALLBACK: {
643 0 : ag_block_id_t block_id = ag_block_id( ag_cert_slot( cert ), ag_cert_block_hash( cert ) );
644 0 : ready_cnt = ag_parent_ready_tracker_mark_notar_fallback( self->parent_ready_tracker, &block_id, self->scratch.parent_readys );
645 0 : break;
646 0 : }
647 0 : case AG_CERT_KIND_SKIP: ready_cnt = ag_parent_ready_tracker_mark_skipped( self->parent_ready_tracker, ag_cert_slot( cert ), self->scratch.parent_readys ); break;
648 0 : default: FD_LOG_CRIT(( "unreachable" ));
649 0 : }
650 0 : for( ulong i=0UL; i<ready_cnt; i++ ) ag_parent_ready_state_map_ele_query( self->parent_ready_tracker->states.map, &self->scratch.parent_readys[i].slot, NULL, self->parent_ready_tracker->states.pool )->ready = 0;
651 0 : if( FD_UNLIKELY( ready_cnt ) ) check_pending_blocks( self, AG_VOTOR_REASON_PARENT_READY );
652 0 : }
653 :
654 0 : if( FD_UNLIKELY( should_ignore_pool_event( self, event ) ) ) return NULL;
655 :
656 0 : switch( event->kind ) {
657 :
658 0 : case AG_POOL_EVENT_PARENT_READY: {
659 0 : check_pending_blocks( self, AG_VOTOR_REASON_PARENT_READY );
660 0 : set_timeouts( self, event->parent_ready.slot );
661 0 : break;
662 0 : }
663 :
664 0 : case AG_POOL_EVENT_SAFE_TO_NOTAR: {
665 0 : ulong slot = event->safe_to_notar.slot;
666 0 : uchar const * hash = event->safe_to_notar.hash;
667 0 : epoch_bls_key_t const * epoch = own_epoch( self, slot );
668 0 : if( FD_LIKELY( epoch->has_bls_key && slot>=self->catchup_vote_slot ) ) {
669 0 : ag_vote_t vote = ag_vote_construct_notar_fallback( self->bls_sign_fn, self->bls_sign_ctx, epoch->bls_key, slot, hash, (ushort)epoch->rank, self->shred_version );
670 0 : push_vote( self, vote, AG_VOTOR_REASON_SAFE_TO_NOTAR );
671 0 : }
672 0 : try_skip_window( self, slot, AG_VOTOR_REASON_SAFE_TO_NOTAR );
673 0 : state_mut( self, slot )->bad_window = 1;
674 0 : break;
675 0 : }
676 :
677 0 : case AG_POOL_EVENT_SAFE_TO_SKIP: {
678 0 : ulong slot = event->safe_to_skip;
679 0 : epoch_bls_key_t const * epoch = own_epoch( self, slot );
680 0 : if( FD_LIKELY( epoch->has_bls_key && slot>=self->catchup_vote_slot ) ) {
681 0 : ag_vote_t vote = ag_vote_construct_skip_fallback( self->bls_sign_fn, self->bls_sign_ctx, epoch->bls_key, slot, (ushort)epoch->rank, self->shred_version );
682 0 : push_vote( self, vote, AG_VOTOR_REASON_SAFE_TO_SKIP );
683 0 : }
684 0 : try_skip_window( self, slot, AG_VOTOR_REASON_SAFE_TO_SKIP );
685 0 : state_mut( self, slot )->bad_window = 1;
686 0 : break;
687 0 : }
688 :
689 0 : case AG_POOL_EVENT_CERT_CREATED:
690 0 : return handle_cert_created( self, &event->cert_created );
691 :
692 0 : default:
693 0 : FD_LOG_ERR(( "invalid pool event kind %d", event->kind ));
694 0 : }
695 0 : return NULL;
696 0 : }
697 :
698 : void
699 : ag_votor_process_replay( ag_votor_t * self,
700 : ulong slot,
701 0 : ag_block_info_t const * block_info ) {
702 0 : if( FD_UNLIKELY( slot<first_unpruned_slot( self ) || is_retired( self, slot ) ) ) return;
703 :
704 0 : if( FD_UNLIKELY( has_voted( self, slot ) ) ) {
705 0 : FD_LOG_WARNING(( "not voting for block in slot %lu, already voted", slot ));
706 0 : return;
707 0 : }
708 0 : if( FD_LIKELY( try_notar( self, slot, block_info, AG_VOTOR_REASON_BLOCK_REPLAYED ) ) ) {
709 0 : check_pending_blocks( self, AG_VOTOR_REASON_BLOCK_REPLAYED );
710 0 : } else {
711 0 : slot_state_ele_t * state = state_mut( self, slot );
712 0 : if( FD_LIKELY( !state->pending_block ) ) pending_dlist_ele_push_tail( self->pending_dlist, state, self->slot_states->pool );
713 0 : state->pending_block = 1;
714 0 : state->pending_block_info = *block_info;
715 0 : }
716 0 : }
717 :
718 : void
719 : ag_votor_set_catchup_vote_slot( ag_votor_t * self,
720 0 : ulong slot ) {
721 0 : self->catchup_vote_slot = fd_ulong_max( self->catchup_vote_slot, slot );
722 0 : }
723 :
724 : void
725 : ag_votor_handle_skip_timeout( ag_votor_t * self,
726 0 : ulong slot ) {
727 0 : if( FD_UNLIKELY( slot<first_unpruned_slot( self ) || is_retired( self, slot ) ) ) return;
728 :
729 0 : if( FD_UNLIKELY( !has_voted( self, slot ) ) ) try_skip_window( self, slot, AG_VOTOR_REASON_TIMEOUT );
730 0 : }
731 :
732 : int
733 : ag_votor_poll_skip_timeout( ag_votor_t * self,
734 : long now,
735 0 : ulong * slot ) {
736 0 : self->now = now;
737 :
738 0 : slot_state_ele_t * ele = next_timeout( self );
739 0 : if( FD_LIKELY( !ele || ele->timeout>now ) ) return 0;
740 0 : timeout_dlist_ele_remove( self->timeout_dlist[ ele->slot%AG_SLOTS_PER_WINDOW ], ele, self->slot_states->pool );
741 0 : ele->timeout = LONG_MAX;
742 :
743 0 : *slot = ele->slot;
744 0 : return 1;
745 0 : }
746 :
747 : FD_FN_PURE long
748 0 : ag_votor_next_skip_timeout( ag_votor_t const * self ) {
749 0 : slot_state_ele_t const * head = next_timeout( self );
750 0 : return head ? head->timeout : LONG_MAX;
751 0 : }
752 :
753 : int
754 : ag_votor_poll_vote( ag_votor_t * self,
755 : ag_vote_t * vote,
756 0 : uchar * reason ) {
757 0 : if( FD_LIKELY( vote_events_empty( self->vote_events ) ) ) return 0;
758 0 : vote_event_t event = vote_events_pop( self->vote_events );
759 0 : *vote = event.vote;
760 0 : *reason = event.reason;
761 0 : return 1;
762 0 : }
763 :
|
