Line data Source code
1 : #include "ag_parent_ready_tracker.h"
2 :
3 : ulong
4 0 : ag_parent_ready_tracker_align( void ) {
5 0 : return alignof(ag_parent_ready_tracker_t);
6 0 : }
7 :
8 : ulong
9 0 : ag_parent_ready_tracker_footprint( ulong slot_max ) {
10 0 : ulong chain_cnt = ag_parent_ready_state_map_chain_cnt_est( slot_max );
11 0 : return FD_LAYOUT_FINI(
12 0 : FD_LAYOUT_APPEND(
13 0 : FD_LAYOUT_APPEND(
14 0 : FD_LAYOUT_APPEND(
15 0 : FD_LAYOUT_INIT,
16 0 : alignof(ag_parent_ready_tracker_t), sizeof(ag_parent_ready_tracker_t) ),
17 0 : ag_parent_ready_state_pool_align(), ag_parent_ready_state_pool_footprint( slot_max ) ),
18 0 : ag_parent_ready_state_map_align(), ag_parent_ready_state_map_footprint ( chain_cnt ) ),
19 0 : ag_parent_ready_tracker_align() );
20 0 : }
21 :
22 : void *
23 : ag_parent_ready_tracker_new( void * shmem,
24 : ulong slot_max,
25 0 : ulong seed ) {
26 0 : if( FD_UNLIKELY( !shmem ) ) {
27 0 : FD_LOG_WARNING(( "NULL mem" ));
28 0 : return NULL;
29 0 : }
30 :
31 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, ag_parent_ready_tracker_align() ) ) ) {
32 0 : FD_LOG_WARNING(( "misaligned mem" ));
33 0 : return NULL;
34 0 : }
35 :
36 0 : ulong footprint = ag_parent_ready_tracker_footprint( slot_max );
37 0 : if( FD_UNLIKELY( !footprint ) ) {
38 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
39 0 : return NULL;
40 0 : }
41 :
42 0 : fd_memset( shmem, 0, footprint );
43 :
44 0 : ulong chain_cnt = ag_parent_ready_state_map_chain_cnt_est( slot_max );
45 :
46 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
47 0 : ag_parent_ready_tracker_t * tracker = FD_SCRATCH_ALLOC_APPEND( l, alignof(ag_parent_ready_tracker_t), sizeof(ag_parent_ready_tracker_t) );
48 0 : void * state_pool = FD_SCRATCH_ALLOC_APPEND( l, ag_parent_ready_state_pool_align(), ag_parent_ready_state_pool_footprint( slot_max ) );
49 0 : void * state_map = FD_SCRATCH_ALLOC_APPEND( l, ag_parent_ready_state_map_align(), ag_parent_ready_state_map_footprint ( chain_cnt ) );
50 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, ag_parent_ready_tracker_align() ) == (ulong)shmem + footprint );
51 :
52 0 : tracker->root = ULONG_MAX;
53 0 : tracker->highest_ready = 0UL;
54 0 : tracker->states.pool = ag_parent_ready_state_pool_join( ag_parent_ready_state_pool_new( state_pool, slot_max ) );
55 0 : tracker->states.map = ag_parent_ready_state_map_join ( ag_parent_ready_state_map_new ( state_map, chain_cnt, seed ) );
56 :
57 :
58 0 : return shmem;
59 0 : }
60 :
61 : ag_parent_ready_tracker_t *
62 0 : ag_parent_ready_tracker_join( void * shtracker ) {
63 0 : ag_parent_ready_tracker_t * tracker = (ag_parent_ready_tracker_t *)shtracker;
64 :
65 0 : if( FD_UNLIKELY( !tracker ) ) {
66 0 : FD_LOG_WARNING(( "NULL tracker" ));
67 0 : return NULL;
68 0 : }
69 :
70 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)tracker, ag_parent_ready_tracker_align() ) ) ) {
71 0 : FD_LOG_WARNING(( "misaligned tracker" ));
72 0 : return NULL;
73 0 : }
74 :
75 0 : return tracker;
76 0 : }
77 :
78 : void *
79 0 : ag_parent_ready_tracker_leave( ag_parent_ready_tracker_t const * tracker ) {
80 0 : if( FD_UNLIKELY( !tracker ) ) {
81 0 : FD_LOG_WARNING(( "NULL tracker" ));
82 0 : return NULL;
83 0 : }
84 0 : return (void *)tracker;
85 0 : }
86 :
87 : void *
88 0 : ag_parent_ready_tracker_delete( void * shtracker ) {
89 0 : if( FD_UNLIKELY( !shtracker ) ) {
90 0 : FD_LOG_WARNING(( "NULL tracker" ));
91 0 : return NULL;
92 0 : }
93 :
94 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtracker, ag_parent_ready_tracker_align() ) ) ) {
95 0 : FD_LOG_WARNING(( "misaligned tracker" ));
96 0 : return NULL;
97 0 : }
98 :
99 0 : return shtracker;
100 0 : }
101 :
102 : static ag_parent_ready_state_t *
103 : slot_state( ag_parent_ready_tracker_t * self,
104 0 : ulong slot ) {
105 0 : ag_parent_ready_state_t * state = ag_parent_ready_state_map_ele_query( self->states.map, &slot, NULL, self->states.pool );
106 0 : if( FD_LIKELY( state ) ) return state;
107 :
108 0 : ag_parent_ready_state_t * pool = self->states.pool;
109 0 : if( FD_UNLIKELY( !ag_parent_ready_state_pool_free( pool ) ) ) {
110 0 : FD_LOG_ERR(( "parent_ready_tracker: state pool exhausted (slot_max exceeded) at slot %lu", slot ));
111 0 : }
112 :
113 0 : state = ag_parent_ready_state_pool_ele_acquire( pool );
114 0 : state->slot = slot;
115 0 : state->skip = 0;
116 0 : state->notar_fallbacks_cnt = (uchar)0;
117 0 : state->b_lo = ULONG_MAX;
118 0 : state->parent_ready_lo.slot = ULONG_MAX;
119 0 : state->ready = 0;
120 0 : ag_parent_ready_state_map_ele_insert( self->states.map, state, pool );
121 0 : return state;
122 0 : }
123 :
124 : static void
125 : add_to_ready( ag_parent_ready_tracker_t * self,
126 : ulong slot,
127 : ag_block_id_t const * parent,
128 : ag_parent_ready_t * newly_certified,
129 0 : ulong * newly_certified_cnt ) {
130 0 : ag_parent_ready_state_t * state = slot_state( self, slot );
131 0 : if( FD_LIKELY( state->parent_ready_lo.slot==ULONG_MAX || ag_block_id_lt( parent, &state->parent_ready_lo ) ) ) state->parent_ready_lo = *parent;
132 0 : self->highest_ready = fd_ulong_max( self->highest_ready, slot );
133 0 : if( FD_UNLIKELY( state->ready ) ) return;
134 0 : state->ready = 1;
135 0 : newly_certified[ *newly_certified_cnt ].slot = slot;
136 0 : newly_certified[ *newly_certified_cnt ].parent = state->parent_ready_lo;
137 0 : (*newly_certified_cnt)++;
138 0 : }
139 :
140 : ulong
141 : ag_parent_ready_tracker_mark_notar_fallback( ag_parent_ready_tracker_t * self,
142 : ag_block_id_t const * block_id,
143 0 : ag_parent_ready_t * newly_certified ) {
144 0 : ulong newly_certified_cnt = 0UL;
145 :
146 0 : ulong slot = block_id->slot;
147 0 : uchar const * hash = block_id->hash;
148 :
149 0 : if( FD_UNLIKELY( slot < self->root ) ) return 0UL;
150 :
151 0 : ag_parent_ready_state_t * state = slot_state( self, slot );
152 0 : for( ulong i=0UL; i<state->notar_fallbacks_cnt; i++ ) {
153 0 : if( FD_UNLIKELY( 0==memcmp( state->notar_fallbacks[i], hash, sizeof(ag_block_hash_t) ) ) ) return 0UL;
154 0 : }
155 0 : FD_CHECK_CRIT( state->notar_fallbacks_cnt<AG_NOTAR_FALLBACK_CERT_MAX, "consensus safety violation" ); /* Lemma 48 */
156 0 : memcpy( state->notar_fallbacks[ state->notar_fallbacks_cnt++ ], hash, sizeof(ag_block_hash_t) );
157 :
158 0 : for( ulong s=slot+1UL; ; s++ ) {
159 0 : if( FD_UNLIKELY( ag_is_start_of_window( s ) ) ) add_to_ready( self, s, block_id, newly_certified, &newly_certified_cnt );
160 0 : ag_parent_ready_state_t const * next = ag_parent_ready_state_map_ele_query_const( self->states.map, &s, NULL, self->states.pool );
161 0 : if( FD_LIKELY( !next || !next->skip ) ) break;
162 0 : }
163 0 : return newly_certified_cnt;
164 0 : }
165 :
166 : ulong
167 : ag_parent_ready_tracker_mark_root( ag_parent_ready_tracker_t * self,
168 : ag_block_id_t const * root,
169 0 : ag_parent_ready_t * newly_certified ) {
170 0 : ulong newly_certified_cnt = ag_parent_ready_tracker_mark_notar_fallback( self, root, newly_certified );
171 0 : ag_parent_ready_state_t * next = slot_state( self, root->slot+1UL );
172 0 : if( FD_LIKELY( next->parent_ready_lo.slot==ULONG_MAX ) ) next->parent_ready_lo = *root;
173 0 : return newly_certified_cnt;
174 0 : }
175 :
176 : ulong
177 : ag_parent_ready_tracker_mark_skipped( ag_parent_ready_tracker_t * self,
178 : ulong skipped_slot,
179 0 : ag_parent_ready_t * newly_certified ) {
180 0 : ulong newly_certified_cnt = 0UL;
181 :
182 0 : if( FD_UNLIKELY( skipped_slot < self->root ) ) return 0UL;
183 0 : ag_parent_ready_state_t * state = slot_state( self, skipped_slot );
184 0 : if( FD_UNLIKELY( state->skip ) ) return 0UL;
185 0 : state->skip = 1;
186 :
187 : /* The skip extends every chain ending at skipped_slot down to b_lo,
188 : the highest slot below skipped_slot that is not skipped. The
189 : newly ready parents are the notar fallbacks of [b_lo,skipped_slot).
190 : Setting b_lo makes all of them ready, and parent_ready_lo is set to
191 : their minimum. */
192 :
193 0 : ag_block_id_t parent = { .slot = ULONG_MAX };
194 0 : ulong b_lo = ULONG_MAX;
195 0 : ulong first = ag_first_slot_in_window( skipped_slot );
196 0 : for( ulong slot=skipped_slot; slot>fd_ulong_max( first, self->root ); ) {
197 0 : slot--;
198 0 : ag_parent_ready_state_t const * prev = ag_parent_ready_state_map_ele_query_const( self->states.map, &slot, NULL, self->states.pool );
199 0 : for( ulong i=0UL; prev && i<prev->notar_fallbacks_cnt; i++ ) {
200 0 : ag_block_id_t nf = ag_block_id( slot, prev->notar_fallbacks[i] );
201 0 : if( parent.slot==ULONG_MAX || ag_block_id_lt( &nf, &parent ) ) parent = nf;
202 0 : }
203 0 : if( FD_LIKELY( !prev || !prev->skip ) ) { b_lo = slot; break; }
204 0 : }
205 0 : if( FD_UNLIKELY( b_lo==ULONG_MAX ) ) { /* [first,skipped_slot) all skipped, the window start knows the rest */
206 0 : ag_parent_ready_state_t const * start = ag_parent_ready_state_map_ele_query_const( self->states.map, &first, NULL, self->states.pool );
207 0 : b_lo = ( start && start->b_lo!=ULONG_MAX ) ? start->b_lo : fd_ulong_sat_sub( first, 1UL );
208 0 : if( start && start->parent_ready_lo.slot!=ULONG_MAX && start->parent_ready_lo.slot>=self->root && ( parent.slot==ULONG_MAX || ag_block_id_lt( &start->parent_ready_lo, &parent ) ) ) parent = start->parent_ready_lo;
209 0 : }
210 :
211 0 : for( ulong s=skipped_slot+1UL; ; s++ ) {
212 0 : if( FD_UNLIKELY( ag_is_start_of_window( s ) ) ) {
213 0 : slot_state( self, s )->b_lo = b_lo;
214 0 : if( FD_LIKELY( parent.slot!=ULONG_MAX ) ) add_to_ready( self, s, &parent, newly_certified, &newly_certified_cnt );
215 0 : }
216 0 : ag_parent_ready_state_t const * next = ag_parent_ready_state_map_ele_query_const( self->states.map, &s, NULL, self->states.pool );
217 0 : if( FD_LIKELY( !next || !next->skip ) ) break;
218 0 : }
219 0 : return newly_certified_cnt;
220 0 : }
221 :
222 : ulong
223 : ag_parent_ready_tracker_parents_ready( ag_parent_ready_tracker_t const * self,
224 : ulong slot,
225 : ag_block_id_t * out,
226 0 : ulong out_max ) {
227 0 : if( FD_UNLIKELY( !ag_is_start_of_window( slot ) || slot<=self->root ) ) return 0UL;
228 :
229 0 : ag_parent_ready_state_t const * state = ag_parent_ready_state_map_ele_query_const( self->states.map, &slot, NULL, self->states.pool );
230 0 : ulong b_lo = ( state && state->b_lo!=ULONG_MAX ) ? state->b_lo : slot-1UL;
231 :
232 0 : ulong cnt = 0UL;
233 0 : for( ulong s=fd_ulong_max( b_lo, self->root ); s<slot; s++ ) {
234 0 : ag_parent_ready_state_t const * nf = ag_parent_ready_state_map_ele_query_const( self->states.map, &s, NULL, self->states.pool );
235 0 : for( ulong i=0UL; nf && i<nf->notar_fallbacks_cnt; i++ ) {
236 0 : if( FD_LIKELY( cnt<out_max ) ) out[ cnt ] = ag_block_id( s, nf->notar_fallbacks[i] );
237 0 : cnt++;
238 0 : }
239 0 : }
240 0 : return cnt;
241 0 : }
242 :
243 : int
244 : ag_parent_ready_tracker_is_parent_ready( ag_parent_ready_tracker_t const * self,
245 : ulong slot,
246 0 : ag_block_id_t const * parent ) {
247 0 : if( FD_UNLIKELY( !ag_is_start_of_window( slot ) || parent->slot>=slot || parent->slot<self->root ) ) return 0;
248 :
249 0 : ag_parent_ready_state_t const * state = ag_parent_ready_state_map_ele_query_const( self->states.map, &slot, NULL, self->states.pool );
250 0 : ulong b_lo = ( state && state->b_lo!=ULONG_MAX ) ? state->b_lo : slot-1UL;
251 0 : if( FD_UNLIKELY( parent->slot<b_lo ) ) return 0;
252 :
253 0 : ag_parent_ready_state_t const * nf = ag_parent_ready_state_map_ele_query_const( self->states.map, &parent->slot, NULL, self->states.pool );
254 0 : for( ulong i=0UL; nf && i<nf->notar_fallbacks_cnt; i++ ) {
255 0 : if( FD_UNLIKELY( 0==memcmp( nf->notar_fallbacks[i], parent->hash, sizeof(ag_block_hash_t) ) ) ) return 1;
256 0 : }
257 0 : return 0;
258 0 : }
259 :
260 : ag_block_id_t
261 : ag_parent_ready_tracker_wait_for_parent_ready( ag_parent_ready_tracker_t const * self,
262 0 : ulong slot ) {
263 0 : ag_parent_ready_state_t const * state = ag_parent_ready_state_map_ele_query_const( self->states.map, &slot, NULL, self->states.pool );
264 0 : if( FD_UNLIKELY( !state || state->parent_ready_lo.slot<self->root ) ) return (ag_block_id_t){ .slot = ULONG_MAX };
265 0 : return state->parent_ready_lo;
266 0 : }
267 :
268 : void
269 : ag_parent_ready_tracker_prune( ag_parent_ready_tracker_t * self,
270 0 : ulong new_root ) {
271 0 : ag_parent_ready_state_map_t * map = self->states.map;
272 0 : ag_parent_ready_state_t * pool = self->states.pool;
273 0 : for( ulong slot=self->root; slot<new_root; slot++ ) {
274 0 : ag_parent_ready_state_t * ele = ag_parent_ready_state_map_ele_remove( map, &slot, NULL, pool );
275 0 : if( FD_LIKELY( ele ) ) ag_parent_ready_state_pool_ele_release( pool, ele );
276 0 : }
277 0 : self->root = new_root;
278 :
279 : /* A window start whose lowest ready parent was pruned takes the
280 : lowest of its ready parents [b_lo,slot) still retained. */
281 :
282 0 : for( ag_parent_ready_state_map_iter_t iter = ag_parent_ready_state_map_iter_init( map, pool );
283 0 : !ag_parent_ready_state_map_iter_done( iter, map, pool );
284 0 : iter = ag_parent_ready_state_map_iter_next( iter, map, pool ) ) {
285 0 : ag_parent_ready_state_t * state = ag_parent_ready_state_map_iter_ele( iter, map, pool );
286 0 : if( FD_LIKELY( state->parent_ready_lo.slot==ULONG_MAX || state->parent_ready_lo.slot>=new_root ) ) continue;
287 0 : ulong b_lo = state->b_lo!=ULONG_MAX ? state->b_lo : state->slot-1UL;
288 0 : state->parent_ready_lo.slot = ULONG_MAX;
289 0 : for( ulong s=fd_ulong_max( b_lo, new_root ); s<state->slot; s++ ) {
290 0 : ag_parent_ready_state_t const * nf = ag_parent_ready_state_map_ele_query_const( map, &s, NULL, pool );
291 0 : for( ulong i=0UL; nf && i<nf->notar_fallbacks_cnt; i++ ) {
292 0 : ag_block_id_t id = ag_block_id( s, nf->notar_fallbacks[i] );
293 0 : if( state->parent_ready_lo.slot==ULONG_MAX || ag_block_id_lt( &id, &state->parent_ready_lo ) ) state->parent_ready_lo = id;
294 0 : }
295 0 : }
296 0 : }
297 0 : }
|
