Line data Source code
1 : #include "ag_parent_ready_tracker.h"
2 :
3 : ulong
4 2232 : ag_parent_ready_tracker_align( void ) {
5 2232 : return alignof(ag_parent_ready_tracker_t);
6 2232 : }
7 :
8 : ulong
9 522 : ag_parent_ready_tracker_footprint( ulong slot_max ) {
10 522 : slot_max = fd_ulong_pow2_up( slot_max );
11 522 : ulong chain_cnt = ag_parent_ready_state_map_chain_cnt_est( slot_max );
12 522 : return FD_LAYOUT_FINI(
13 522 : FD_LAYOUT_APPEND(
14 522 : FD_LAYOUT_APPEND(
15 522 : FD_LAYOUT_APPEND(
16 522 : FD_LAYOUT_INIT,
17 522 : alignof(ag_parent_ready_tracker_t), sizeof(ag_parent_ready_tracker_t) ),
18 522 : ag_parent_ready_state_pool_align(), ag_parent_ready_state_pool_footprint( slot_max ) ),
19 522 : ag_parent_ready_state_map_align(), ag_parent_ready_state_map_footprint ( chain_cnt ) ),
20 522 : ag_parent_ready_tracker_align() );
21 522 : }
22 :
23 : void *
24 : ag_parent_ready_tracker_new( void * shmem,
25 : ulong slot_max,
26 147 : ulong seed ) {
27 147 : if( FD_UNLIKELY( !shmem ) ) {
28 0 : FD_LOG_WARNING(( "NULL mem" ));
29 0 : return NULL;
30 0 : }
31 :
32 147 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, ag_parent_ready_tracker_align() ) ) ) {
33 0 : FD_LOG_WARNING(( "misaligned mem" ));
34 0 : return NULL;
35 0 : }
36 :
37 147 : ulong footprint = ag_parent_ready_tracker_footprint( slot_max );
38 147 : if( FD_UNLIKELY( !footprint ) ) {
39 0 : FD_LOG_WARNING(( "bad slot_max (%lu)", slot_max ));
40 0 : return NULL;
41 0 : }
42 :
43 147 : slot_max = fd_ulong_pow2_up( slot_max );
44 :
45 147 : fd_memset( shmem, 0, footprint );
46 :
47 147 : ulong chain_cnt = ag_parent_ready_state_map_chain_cnt_est( slot_max );
48 :
49 147 : FD_SCRATCH_ALLOC_INIT( l, shmem );
50 147 : ag_parent_ready_tracker_t * tracker = FD_SCRATCH_ALLOC_APPEND( l, alignof(ag_parent_ready_tracker_t), sizeof(ag_parent_ready_tracker_t) );
51 147 : void * state_pool = FD_SCRATCH_ALLOC_APPEND( l, ag_parent_ready_state_pool_align(), ag_parent_ready_state_pool_footprint( slot_max ) );
52 147 : void * state_map = FD_SCRATCH_ALLOC_APPEND( l, ag_parent_ready_state_map_align(), ag_parent_ready_state_map_footprint ( chain_cnt ) );
53 147 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, ag_parent_ready_tracker_align() ) == (ulong)shmem + footprint );
54 :
55 147 : tracker->root = ULONG_MAX;
56 147 : tracker->states.pool = ag_parent_ready_state_pool_join( ag_parent_ready_state_pool_new( state_pool, slot_max ) );
57 147 : tracker->states.map = ag_parent_ready_state_map_join ( ag_parent_ready_state_map_new ( state_map, chain_cnt, seed ) );
58 :
59 :
60 147 : return shmem;
61 147 : }
62 :
63 : ag_parent_ready_tracker_t *
64 147 : ag_parent_ready_tracker_join( void * shtracker ) {
65 147 : ag_parent_ready_tracker_t * tracker = (ag_parent_ready_tracker_t *)shtracker;
66 :
67 147 : if( FD_UNLIKELY( !tracker ) ) {
68 0 : FD_LOG_WARNING(( "NULL tracker" ));
69 0 : return NULL;
70 0 : }
71 :
72 147 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)tracker, ag_parent_ready_tracker_align() ) ) ) {
73 0 : FD_LOG_WARNING(( "misaligned tracker" ));
74 0 : return NULL;
75 0 : }
76 :
77 147 : return tracker;
78 147 : }
79 :
80 : void *
81 30 : ag_parent_ready_tracker_leave( ag_parent_ready_tracker_t const * tracker ) {
82 30 : if( FD_UNLIKELY( !tracker ) ) {
83 0 : FD_LOG_WARNING(( "NULL tracker" ));
84 0 : return NULL;
85 0 : }
86 30 : return (void *)tracker;
87 30 : }
88 :
89 : void *
90 30 : ag_parent_ready_tracker_delete( void * shtracker ) {
91 30 : if( FD_UNLIKELY( !shtracker ) ) {
92 0 : FD_LOG_WARNING(( "NULL tracker" ));
93 0 : return NULL;
94 0 : }
95 :
96 30 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtracker, ag_parent_ready_tracker_align() ) ) ) {
97 0 : FD_LOG_WARNING(( "misaligned tracker" ));
98 0 : return NULL;
99 0 : }
100 :
101 30 : return shtracker;
102 30 : }
103 :
104 : static void
105 : add_to_ready( ag_parent_ready_state_t * state,
106 180 : ag_block_id_t const * id ) {
107 180 : if( FD_LIKELY( !state->is_ready ) ) {
108 171 : state->ready_ids[ 0 ] = *id;
109 171 : state->ready_id_cnt = 1UL;
110 171 : state->is_ready = 1;
111 171 : } else {
112 9 : state->ready_ids[ state->ready_id_cnt++ ] = *id;
113 9 : }
114 180 : }
115 :
116 : static ag_block_id_t
117 30 : wait_for_parent_ready( ag_parent_ready_state_t * state ) {
118 30 : if( FD_UNLIKELY( state->is_ready ) ) {
119 27 : ag_block_id_t arg_min = state->ready_ids[0];
120 36 : for( ulong i=1; i<state->ready_id_cnt; i++ ) {
121 9 : ag_block_id_t const * id = &state->ready_ids[i];
122 9 : if( FD_UNLIKELY( id->slot<arg_min.slot ) || ( id->slot==arg_min.slot && 0>memcmp( id->hash, arg_min.hash, sizeof(ag_block_hash_t) ) ) ) {
123 6 : arg_min = *id;
124 6 : }
125 9 : }
126 27 : return arg_min;
127 27 : } else {
128 3 : return (ag_block_id_t){ .slot = ULONG_MAX };
129 3 : }
130 30 : }
131 :
132 : static ag_parent_ready_state_t *
133 : slot_state( ag_parent_ready_tracker_t * self,
134 2448 : ulong slot ) {
135 2448 : ag_parent_ready_state_t * state = ag_parent_ready_state_map_ele_query( self->states.map, &slot, NULL, self->states.pool );
136 2448 : if( FD_LIKELY( state ) ) return state;
137 :
138 822 : ag_parent_ready_state_t * pool = self->states.pool;
139 822 : if( FD_UNLIKELY( !ag_parent_ready_state_pool_free( pool ) ) ) {
140 0 : FD_LOG_ERR(( "parent_ready_tracker: state pool exhausted (slot_max exceeded) at slot %lu", slot ));
141 0 : }
142 :
143 822 : state = ag_parent_ready_state_pool_ele_acquire( pool );
144 822 : state->slot = slot;
145 822 : state->skip = 0;
146 822 : state->notar_fallbacks_cnt = (uchar)0;
147 822 : state->is_ready = 0;
148 822 : state->ready_id_cnt = 0UL;
149 822 : ag_parent_ready_state_map_ele_insert( self->states.map, state, pool );
150 822 : return state;
151 822 : }
152 :
153 : void
154 : ag_parent_ready_tracker_mark_notar_fallback( ag_parent_ready_tracker_t * self,
155 : ag_block_id_t const * id,
156 : ag_parent_ready_t * newly_certified,
157 1137 : ulong * newly_certified_cnt ) {
158 1137 : *newly_certified_cnt = 0UL;
159 :
160 1137 : ulong slot = id->slot;
161 1137 : uchar const * hash = id->hash;
162 :
163 1137 : if( FD_UNLIKELY( slot < self->root ) ) return;
164 :
165 1134 : ag_parent_ready_state_t * state = slot_state( self, slot );
166 1134 : for( ulong i=0UL; i<state->notar_fallbacks_cnt; i++ ) {
167 612 : if( FD_UNLIKELY( 0==memcmp( state->notar_fallbacks[i], hash, sizeof(ag_block_hash_t) ) ) ) return;
168 612 : }
169 522 : memcpy( state->notar_fallbacks[ state->notar_fallbacks_cnt++ ], hash, sizeof(ag_block_hash_t) );
170 :
171 540 : for( ulong slot_=slot+1; ; slot_++ ) {
172 540 : ag_parent_ready_state_t * state_ = slot_state( self, slot_ );
173 540 : if( FD_UNLIKELY( ag_is_start_of_window( slot_ ) ) ) {
174 126 : add_to_ready( state_, id );
175 126 : newly_certified[ *newly_certified_cnt ].slot = slot_;
176 126 : newly_certified[ *newly_certified_cnt ].parent = *id;
177 126 : (*newly_certified_cnt)++;
178 126 : }
179 540 : if( FD_LIKELY( !state_->skip ) ) break;
180 540 : }
181 522 : return;
182 1134 : }
183 :
184 : void
185 : ag_parent_ready_tracker_mark_skipped( ag_parent_ready_tracker_t * self,
186 : ulong marked_slot,
187 : ag_parent_ready_t * newly_certified,
188 165 : ulong * newly_certified_cnt ) {
189 165 : *newly_certified_cnt = 0UL;
190 :
191 165 : if( FD_UNLIKELY( marked_slot < self->root ) ) return;
192 165 : ag_parent_ready_state_t * state = slot_state( self, marked_slot );
193 165 : if( FD_UNLIKELY( state->skip ) ) return;
194 165 : state->skip = 1;
195 :
196 165 : ag_block_id_t potential_parents[ AG_SLOTS_PER_WINDOW*AG_NOTAR_FALLBACK_CERT_MAX ];
197 165 : ulong potential_cnt = 0UL;
198 :
199 492 : for( ulong slot=marked_slot; slot>=fd_ulong_max( ag_first_slot_in_window( marked_slot ), self->root ); slot-- ) {
200 429 : ag_parent_ready_state_t * state = slot_state( self, slot );
201 :
202 429 : if( FD_LIKELY( slot!=marked_slot ) ) {
203 336 : for( ulong i=0UL; i<state->notar_fallbacks_cnt; i++ ) {
204 72 : FD_TEST( potential_cnt < AG_SLOTS_PER_WINDOW*AG_NOTAR_FALLBACK_CERT_MAX );
205 72 : potential_parents[ potential_cnt ] = ag_block_id( slot, state->notar_fallbacks[i] );
206 72 : potential_cnt++;
207 72 : }
208 264 : }
209 :
210 429 : if( FD_LIKELY( !state->skip ) ) break;
211 :
212 390 : for( ulong i=0UL; i<state->ready_id_cnt; i++ ) {
213 63 : FD_TEST( potential_cnt < AG_SLOTS_PER_WINDOW*AG_NOTAR_FALLBACK_CERT_MAX );
214 63 : potential_parents[ potential_cnt ] = state->ready_ids[i];
215 63 : potential_cnt++;
216 63 : }
217 327 : }
218 :
219 180 : for( ulong s=marked_slot+1UL; ; s++ ) {
220 180 : ag_parent_ready_state_t * fstate = slot_state( self, s );
221 180 : if( FD_UNLIKELY( ag_is_start_of_window( s ) ) ) {
222 105 : for( ulong i=0UL; i<potential_cnt; i++ ) {
223 48 : add_to_ready( fstate, &potential_parents[i] );
224 48 : FD_TEST( *newly_certified_cnt < ag_parent_ready_state_pool_max( self->states.pool ) ); /* caller sized for slot_max */
225 48 : newly_certified[ *newly_certified_cnt ].slot = s;
226 48 : newly_certified[ *newly_certified_cnt ].parent = potential_parents[i];
227 48 : (*newly_certified_cnt)++;
228 48 : }
229 57 : }
230 180 : if( FD_LIKELY( !fstate->skip ) ) break;
231 180 : }
232 165 : return;
233 165 : }
234 :
235 : static void
236 : keep_highest( ag_parent_ready_t * best,
237 : ag_parent_ready_t const * ready,
238 405 : ulong ready_cnt ) {
239 441 : for( ulong i=0UL; i<ready_cnt; i++ ) {
240 36 : if( FD_LIKELY( best->slot==ULONG_MAX || ready[i].slot>=best->slot ) ) *best = ready[i];
241 36 : }
242 405 : }
243 :
244 : ag_parent_ready_t
245 : ag_parent_ready_tracker_handle_finalization( ag_parent_ready_tracker_t * self,
246 : ag_finalization_event_t const * event,
247 : ag_parent_ready_t * newly_certified,
248 756 : ulong * newly_certified_cnt ) {
249 756 : ag_parent_ready_t best;
250 756 : fd_memset( &best, 0, sizeof(ag_parent_ready_t) );
251 756 : best.slot = ULONG_MAX;
252 :
253 756 : if( FD_LIKELY( event->finalized.slot!=ULONG_MAX ) ) {
254 369 : ag_parent_ready_tracker_mark_notar_fallback( self, &event->finalized, newly_certified, newly_certified_cnt );
255 369 : keep_highest( &best, newly_certified, *newly_certified_cnt );
256 369 : }
257 :
258 780 : for( ulong j=0UL; j<event->implicitly_finalized_cnt; j++ ) {
259 24 : ag_parent_ready_tracker_mark_notar_fallback( self, &event->implicitly_finalized[j], newly_certified, newly_certified_cnt );
260 24 : keep_highest( &best, newly_certified, *newly_certified_cnt );
261 24 : }
262 :
263 768 : for( ulong j=0UL; j<event->implicitly_skipped_cnt; j++ ) {
264 12 : ag_parent_ready_tracker_mark_skipped( self, event->implicitly_skipped[j], newly_certified, newly_certified_cnt );
265 12 : keep_highest( &best, newly_certified, *newly_certified_cnt );
266 12 : }
267 :
268 756 : return best;
269 756 : }
270 :
271 : ag_block_id_t const *
272 : ag_parent_ready_tracker_parents_ready( ag_parent_ready_tracker_t * self,
273 : ulong slot,
274 48 : ulong * cnt ) {
275 48 : ag_parent_ready_state_t * state = ag_parent_ready_state_map_ele_query( self->states.map, &slot, NULL, self->states.pool );
276 48 : if( FD_UNLIKELY( !state ) ) { *cnt = 0UL; return NULL; }
277 39 : *cnt = state->ready_id_cnt;
278 39 : return state->ready_ids;
279 48 : }
280 :
281 : ag_block_id_t
282 : ag_parent_ready_tracker_wait_for_parent_ready( ag_parent_ready_tracker_t * self,
283 21 : ulong slot ) {
284 21 : ag_parent_ready_state_t * state = ag_parent_ready_state_map_ele_query( self->states.map, &slot, NULL, self->states.pool );
285 21 : if( FD_UNLIKELY( !state ) ) return (ag_block_id_t){ .slot = ULONG_MAX };
286 12 : return wait_for_parent_ready( state );
287 21 : }
288 :
289 : void
290 : ag_parent_ready_tracker_prune( ag_parent_ready_tracker_t * self,
291 723 : ulong new_root ) {
292 723 : ag_parent_ready_state_map_t * map = self->states.map;
293 723 : ag_parent_ready_state_t * pool = self->states.pool;
294 1083 : for( ulong slot=self->root; slot<new_root; slot++ ) {
295 360 : ag_parent_ready_state_t * ele = ag_parent_ready_state_map_ele_remove( map, &slot, NULL, pool );
296 360 : if( FD_LIKELY( ele ) ) ag_parent_ready_state_pool_ele_release( pool, ele );
297 360 : }
298 723 : self->root = new_root;
299 723 : }
|
