Line data Source code
1 : #include "fd_fec_chainer.h"
2 :
3 : void *
4 0 : fd_fec_chainer_new( void * shmem, ulong fec_max, ulong seed ) {
5 :
6 0 : if( FD_UNLIKELY( !shmem ) ) {
7 0 : FD_LOG_WARNING(( "NULL mem" ));
8 0 : return NULL;
9 0 : }
10 :
11 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_fec_chainer_align() ) ) ) {
12 0 : FD_LOG_WARNING(( "misaligned mem" ));
13 0 : return NULL;
14 0 : }
15 :
16 0 : ulong footprint = fd_fec_chainer_footprint( fec_max );
17 0 : if( FD_UNLIKELY( !footprint ) ) {
18 0 : FD_LOG_WARNING(( "bad fec_max (%lu)", fec_max ));
19 0 : return NULL;
20 0 : }
21 :
22 0 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
23 0 : if( FD_UNLIKELY( !wksp ) ) {
24 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
25 0 : return NULL;
26 0 : }
27 :
28 0 : fd_memset( shmem, 0, footprint );
29 :
30 0 : fd_fec_chainer_t * chainer;
31 0 : int lg_fec_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max ) );
32 :
33 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
34 0 : chainer = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_chainer_align(), sizeof( fd_fec_chainer_t ) );
35 0 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_ancestry_align(), fd_fec_ancestry_footprint( fec_max ) );
36 0 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_frontier_align(), fd_fec_frontier_footprint( fec_max ) );
37 0 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_orphaned_align(), fd_fec_orphaned_footprint( fec_max ) );
38 0 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_pool_align(), fd_fec_pool_footprint( fec_max ) );
39 0 : void * parents = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_parents_align(), fd_fec_parents_footprint( lg_fec_max ) );
40 0 : void * children = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_children_align(), fd_fec_children_footprint( lg_fec_max ) );
41 0 : void * queue = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_queue_align(), fd_fec_queue_footprint( fec_max ) );
42 0 : void * out = FD_SCRATCH_ALLOC_APPEND( l, fd_fec_out_align(), fd_fec_out_footprint( fec_max ) );
43 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_fec_chainer_align() ) == (ulong)shmem + footprint );
44 :
45 0 : chainer->ancestry = fd_fec_ancestry_new( ancestry, fec_max, seed );
46 0 : chainer->frontier = fd_fec_frontier_new( frontier, fec_max, seed );
47 0 : chainer->orphaned = fd_fec_orphaned_new( orphaned, fec_max, seed );
48 0 : chainer->pool = fd_fec_pool_new ( pool, fec_max );
49 0 : chainer->parents = fd_fec_parents_new ( parents, lg_fec_max );
50 0 : chainer->children = fd_fec_children_new( children, lg_fec_max );
51 0 : chainer->queue = fd_fec_queue_new ( queue, fec_max );
52 0 : chainer->out = fd_fec_out_new ( out, fec_max );
53 :
54 0 : return shmem;
55 0 : }
56 :
57 : fd_fec_chainer_t *
58 0 : fd_fec_chainer_join( void * shfec_chainer ) {
59 0 : fd_fec_chainer_t * chainer = (fd_fec_chainer_t *)shfec_chainer;
60 :
61 0 : if( FD_UNLIKELY( !chainer ) ) {
62 0 : FD_LOG_WARNING(( "NULL chainer" ));
63 0 : return NULL;
64 0 : }
65 :
66 0 : chainer->ancestry = fd_fec_ancestry_join( chainer->ancestry );
67 0 : chainer->frontier = fd_fec_frontier_join( chainer->frontier );
68 0 : chainer->orphaned = fd_fec_orphaned_join( chainer->orphaned );
69 0 : chainer->pool = fd_fec_pool_join ( chainer->pool );
70 0 : chainer->parents = fd_fec_parents_join ( chainer->parents );
71 0 : chainer->children = fd_fec_children_join( chainer->children );
72 0 : chainer->queue = fd_fec_queue_join ( chainer->queue );
73 0 : chainer->out = fd_fec_out_join ( chainer->out );
74 :
75 0 : return chainer;
76 0 : }
77 :
78 : void *
79 0 : fd_fec_chainer_leave( fd_fec_chainer_t * chainer ) {
80 :
81 0 : if( FD_UNLIKELY( !chainer ) ) {
82 0 : FD_LOG_WARNING(( "NULL chainer" ));
83 0 : return NULL;
84 0 : }
85 :
86 0 : return (void *)chainer;
87 0 : }
88 :
89 : void *
90 0 : fd_fec_chainer_delete( void * shchainer ) {
91 0 : fd_fec_chainer_t * chainer = (fd_fec_chainer_t *)shchainer;
92 :
93 0 : if( FD_UNLIKELY( !chainer ) ) {
94 0 : FD_LOG_WARNING(( "NULL chainer" ));
95 0 : return NULL;
96 0 : }
97 :
98 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)chainer, fd_fec_chainer_align() ) ) ) {
99 0 : FD_LOG_WARNING(( "misaligned chainer" ));
100 0 : return NULL;
101 0 : }
102 :
103 0 : return chainer;
104 0 : }
105 :
106 : fd_fec_ele_t *
107 0 : fd_fec_chainer_init( fd_fec_chainer_t * chainer, ulong slot, uchar merkle_root[static FD_SHRED_MERKLE_ROOT_SZ] ) {
108 0 : FD_TEST( fd_fec_pool_free( chainer->pool ) );
109 0 : fd_fec_ele_t * root = fd_fec_pool_ele_acquire( chainer->pool );
110 0 : FD_TEST( root );
111 0 : root->key = slot << 32 | ( UINT_MAX-1 ); // maintain invariant that no fec_set_idx=UINT_MAX lives in pool_ele
112 0 : root->slot = slot;
113 0 : root->fec_set_idx = UINT_MAX-1;
114 0 : root->data_cnt = 0;
115 0 : root->data_complete = 1;
116 0 : root->slot_complete = 1;
117 0 : root->parent_off = 0;
118 0 : memcpy( root->merkle_root, merkle_root, FD_SHRED_MERKLE_ROOT_SZ );
119 0 : memset( root->chained_merkle_root, 0, FD_SHRED_MERKLE_ROOT_SZ );
120 :
121 : /* For the next slot that chains off the init slot, it will use the
122 : parent_map and key with slot | UINT_MAX to look for its parent, so
123 : we need to provide the artificial parent link between the last
124 : fec_set_idx and UINT_MAX. This way it can query for
125 : UINT_MAX -> UINT_MAX-1 -> get_pool_ele(UINT_MAX-1)*/
126 :
127 0 : fd_fec_parent_t * p = fd_fec_parents_insert( chainer->parents, slot << 32 | UINT_MAX );
128 0 : p->parent_key = (slot << 32) | ( UINT_MAX - 1 );
129 :
130 0 : fd_fec_frontier_ele_insert( chainer->frontier, root, chainer->pool );
131 0 : return root;
132 0 : }
133 :
134 : void *
135 0 : fd_fec_chainer_fini( fd_fec_chainer_t * chainer ) {
136 0 : return (void *)chainer;
137 0 : }
138 :
139 : FD_FN_PURE fd_fec_ele_t *
140 0 : fd_fec_chainer_query( fd_fec_chainer_t * chainer, ulong slot, uint fec_set_idx ) {
141 0 : ulong key = slot << 32 | fec_set_idx;
142 0 : fd_fec_ele_t * fec;
143 0 : fec = fd_fec_frontier_ele_query( chainer->frontier, &key, NULL, chainer->pool );
144 0 : fec = fd_ptr_if( !fec, fd_fec_ancestry_ele_query( chainer->ancestry, &key, NULL, chainer->pool ), fec );
145 0 : fec = fd_ptr_if( !fec, fd_fec_orphaned_ele_query( chainer->orphaned, &key, NULL, chainer->pool ), fec );
146 0 : return fec;
147 0 : }
148 :
149 : static int
150 0 : is_last_fec( ulong key ){
151 0 : return ( (uint)fd_ulong_extract( key, 0, 31 ) & UINT_MAX ) == UINT_MAX; // lol fix
152 0 : }
153 :
154 : static void
155 0 : link_orphans( fd_fec_chainer_t * chainer ) {
156 0 : while( FD_LIKELY( !fd_fec_queue_empty( chainer->queue ) ) ) {
157 0 : ulong key = fd_fec_queue_pop_head( chainer->queue );
158 0 : fd_fec_ele_t * ele = fd_fec_orphaned_ele_query( chainer->orphaned, &key, NULL, chainer->pool );
159 :
160 0 : if( FD_LIKELY( !ele ) ) continue;
161 :
162 : /* Query for the parent_key. */
163 :
164 0 : fd_fec_parent_t * parent_key = fd_fec_parents_query( chainer->parents, key, NULL );
165 0 : if( FD_UNLIKELY( !parent_key ) ) continue; /* still orphaned */
166 :
167 : /* If the parent is in the frontier, remove the parent and insert
168 : into ancestry. Otherwise check for parent in ancestry. */
169 :
170 0 : if( FD_UNLIKELY( is_last_fec( parent_key->parent_key ) ) ) {
171 :
172 : /* If the parent was the last fec of the previous slot, the
173 : parent_key will be UINT_MAX. Need to query for the actual
174 : fec_set_idx of the last FEC. This is the double query */
175 :
176 0 : parent_key = fd_fec_parents_query( chainer->parents, parent_key->parent_key, NULL );
177 0 : if( !parent_key ) continue; /* still orphaned */
178 0 : }
179 :
180 0 : fd_fec_ele_t * parent = fd_fec_frontier_ele_remove( chainer->frontier, &parent_key->parent_key, NULL, chainer->pool );
181 0 : if( FD_LIKELY( parent ) ) fd_fec_ancestry_ele_insert( chainer->ancestry, parent, chainer->pool );
182 0 : else parent = fd_fec_ancestry_ele_query( chainer->ancestry, &parent_key->parent_key, NULL, chainer->pool );
183 :
184 : /* If the parent is not in frontier or ancestry, ele is still
185 : orphaned. Note it is possible to have inserted ele's parent but
186 : have ele still be orphaned, because parent is also orphaned. */
187 :
188 0 : if( FD_UNLIKELY( !parent ) ) continue;
189 :
190 : /* Remove ele from orphaned. */
191 :
192 0 : fd_fec_ele_t * remove = fd_fec_orphaned_ele_remove( chainer->orphaned, &ele->key, NULL, chainer->pool );
193 0 : FD_TEST( remove == ele );
194 :
195 : /* Verify the chained merkle root. */
196 :
197 0 : uchar zeros[ FD_SHRED_MERKLE_ROOT_SZ ] = { 0 }; /* FIXME */
198 0 : if ( FD_UNLIKELY( memcmp( ele->chained_merkle_root, parent->merkle_root, FD_SHRED_MERKLE_ROOT_SZ ) ) &&
199 0 : ( memcmp( ele->chained_merkle_root, zeros, FD_SHRED_MERKLE_ROOT_SZ ) ) ) {
200 : /* FIXME this requires a lot of changes to shred tile without
201 : fixed-32 fec sets, so disabled until then (impending agave 2.3
202 : release). */
203 :
204 : // FD_LOG_NOTICE(( "actual %lu %u %s", ele->slot, ele->fec_set_idx, FD_BASE58_ENC_32_ALLOCA( ele->chained_merkle_root ) ));
205 : // FD_LOG_NOTICE(( "expected %lu %u %s", parent->slot, parent->fec_set_idx, FD_BASE58_ENC_32_ALLOCA( parent->merkle_root ) ));
206 : // fd_fec_out_push_tail( chainer->out, (fd_fec_out_t){ .slot = ele->slot, .parent_off = ele->parent_off, .fec_set_idx = ele->fec_set_idx, .data_cnt = ele->data_cnt, .data_complete = ele->data_complete, .slot_complete = ele->slot_complete, .err = FD_FEC_CHAINER_ERR_MERKLE } );
207 : // continue;
208 0 : }
209 :
210 : /* Insert into frontier (ele is either advancing a fork or starting
211 : a new fork) and deliver to `out`. */
212 :
213 0 : fd_fec_frontier_ele_insert( chainer->frontier, ele, chainer->pool );
214 : // FD_LOG_NOTICE(( "pushing tail %lu %u %u %d %d", ele->slot, ele->fec_set_idx, ele->data_cnt, ele->data_complete, ele->slot_complete ));
215 0 : fd_fec_out_push_tail( chainer->out, (fd_fec_out_t){ .slot = ele->slot, .parent_off = ele->parent_off, .fec_set_idx = ele->fec_set_idx, .data_cnt = ele->data_cnt, .data_complete = ele->data_complete, .slot_complete = ele->slot_complete, .err = FD_FEC_CHAINER_SUCCESS } );
216 :
217 : /* Check whether any of ele's children are orphaned and can be
218 : chained into the frontier. */
219 :
220 : /* TODO this BFS can be structured differently without using any
221 : additional memory by reusing ele->next. */
222 :
223 0 : if( FD_UNLIKELY( ele->slot_complete ) ) {
224 0 : fd_fec_children_t * fec_children = fd_fec_children_query( chainer->children, ele->slot, NULL );
225 0 : if( FD_UNLIKELY( !fec_children ) ) continue;
226 0 : for( ulong off = fd_slot_child_offs_const_iter_init( fec_children->child_offs );
227 0 : !fd_slot_child_offs_const_iter_done( off );
228 0 : off = fd_slot_child_offs_const_iter_next( fec_children->child_offs, off ) ) {
229 0 : ulong child_key = (ele->slot + off) << 32; /* always fec_set_idx 0 */
230 0 : fd_fec_ele_t * child = fd_fec_orphaned_ele_query( chainer->orphaned, &child_key, NULL, chainer->pool );
231 0 : if( FD_LIKELY( child ) ) {
232 0 : fd_fec_queue_push_tail( chainer->queue, child_key );
233 0 : }
234 0 : }
235 0 : } else {
236 0 : ulong child_key = (ele->slot << 32) | (ele->key + ele->data_cnt);
237 0 : fd_fec_queue_push_tail( chainer->queue, child_key );
238 0 : }
239 0 : }
240 0 : }
241 :
242 : fd_fec_ele_t *
243 : fd_fec_chainer_insert( fd_fec_chainer_t * chainer,
244 : ulong slot,
245 : uint fec_set_idx,
246 : ushort data_cnt,
247 : int data_complete,
248 : int slot_complete,
249 : ushort parent_off,
250 : uchar const merkle_root[static FD_SHRED_MERKLE_ROOT_SZ],
251 0 : uchar const chained_merkle_root[static FD_SHRED_MERKLE_ROOT_SZ] ) {
252 0 : ulong key = slot << 32 | fec_set_idx;
253 : // FD_LOG_NOTICE(( "inserting %lu %u %u %d %d", slot, fec_set_idx, data_cnt, data_complete, slot_complete ));
254 :
255 0 : if( FD_UNLIKELY( fd_fec_chainer_query( chainer, slot, fec_set_idx ) ) ) {
256 0 : fd_fec_out_push_tail( chainer->out, (fd_fec_out_t){ slot, parent_off, fec_set_idx, data_cnt, data_complete, slot_complete, .err = FD_FEC_CHAINER_ERR_UNIQUE } );
257 0 : return NULL;
258 0 : }
259 :
260 0 : # if FD_FEC_CHAINER_USE_HANDHOLDING
261 0 : FD_TEST( fd_fec_pool_free( chainer->pool ) ); /* FIXME lru? */
262 0 : FD_TEST( fd_fec_parents_key_cnt( chainer->parents ) < fd_fec_parents_key_max( chainer->parents ) );
263 0 : FD_TEST( fd_fec_children_key_cnt( chainer->children ) < fd_fec_children_key_max( chainer->children ) );
264 0 : # endif
265 :
266 0 : fd_fec_ele_t * ele = fd_fec_pool_ele_acquire( chainer->pool );
267 0 : ele->key = key;
268 0 : ele->slot = slot;
269 0 : ele->fec_set_idx = fec_set_idx;
270 0 : ele->data_cnt = data_cnt;
271 0 : ele->data_complete = data_complete;
272 0 : ele->slot_complete = slot_complete;
273 0 : ele->parent_off = parent_off;
274 0 : memcpy( ele->merkle_root, merkle_root, FD_SHRED_MERKLE_ROOT_SZ );
275 0 : memcpy( ele->chained_merkle_root, chained_merkle_root, FD_SHRED_MERKLE_ROOT_SZ );
276 :
277 : /* If it is the first FEC set, derive and insert parent_key->key into
278 : the parents map and parent_slot->slot into the children map. */
279 :
280 0 : if( FD_UNLIKELY( fec_set_idx == 0 ) ) {
281 0 : ulong parent_slot = slot - parent_off;
282 :
283 0 : fd_fec_parent_t * parent_key = fd_fec_parents_insert( chainer->parents, key );
284 0 : parent_key->parent_key = (parent_slot << 32) | UINT_MAX;
285 :
286 0 : fd_fec_children_t * fec_children = fd_fec_children_query( chainer->children, parent_slot, NULL );
287 0 : if( FD_LIKELY( !fec_children ) ) {
288 0 : fec_children = fd_fec_children_insert( chainer->children, parent_slot );
289 0 : fd_slot_child_offs_null( fec_children->child_offs );
290 0 : }
291 0 : fd_slot_child_offs_insert( fec_children->child_offs, parent_off );
292 0 : }
293 :
294 : /* Derive and insert the child_key->key into the parents map. */
295 :
296 0 : ulong child_key = ( slot << 32 ) | ( fec_set_idx + data_cnt );
297 0 : if( FD_UNLIKELY( slot_complete ) ) {
298 :
299 : /* This is the last FEC set. There is a special case to add
300 : a UINT_MAX -> fec_set_idx link because the child slots will chain
301 : off of UINT_MAX, but the pool_ele will be keyed on fec_set_idx. */
302 :
303 0 : fd_fec_parent_t * parent = fd_fec_parents_insert( chainer->parents, slot << 32 | UINT_MAX );
304 0 : parent->parent_key = key;
305 :
306 0 : } else {
307 :
308 : /* This is not the last FEC set. */
309 : /* Key the child to point to ele (child's parent). */
310 :
311 0 : if( !fd_fec_parents_query( chainer->parents, child_key, NULL ) ) {
312 0 : fd_fec_parent_t * parent = fd_fec_parents_insert( chainer->parents, child_key );
313 0 : parent->parent_key = key;
314 0 : } else {
315 0 : fd_fec_parent_t * parent = fd_fec_parents_query( chainer->parents, child_key, NULL );
316 0 : if( parent->parent_key != key ) {
317 0 : FD_LOG_ERR(( "inconsistent keys %lu %u %lu %u", slot, fec_set_idx, parent->parent_key >> 32, (uint)parent->parent_key ));
318 0 : }
319 0 : }
320 0 : }
321 :
322 : /* Push ele into the BFS deque and the orphaned map for processing. */
323 :
324 0 : fd_fec_queue_push_tail( chainer->queue, key );
325 0 : fd_fec_orphaned_ele_insert( chainer->orphaned, ele, chainer->pool );
326 :
327 0 : link_orphans( chainer );
328 :
329 0 : return ele;
330 0 : }
|
