Line data Source code
1 : #include "fd_store.h"
2 : #include "../../flamenco/fd_flamenco_base.h"
3 :
4 : static const fd_hash_t hash_null = { 0 };
5 :
6 303 : #define null fd_store_pool_idx_null()
7 :
8 90 : #define BLOCKING 1
9 :
10 : void *
11 9 : fd_store_new( void * shmem, ulong fec_max, ulong part_cnt ) {
12 :
13 9 : if( FD_UNLIKELY( part_cnt==0UL ) ) {
14 0 : FD_LOG_WARNING(( "partition count must be greater than 0, should match the number of writers/shred tiles" ));
15 0 : return NULL;
16 0 : }
17 :
18 9 : if( FD_UNLIKELY( !shmem ) ) {
19 0 : FD_LOG_WARNING(( "NULL mem" ));
20 0 : return NULL;
21 0 : }
22 :
23 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_store_align() ) ) ) {
24 0 : FD_LOG_WARNING(( "misaligned mem" ));
25 0 : return NULL;
26 0 : }
27 :
28 9 : ulong footprint = fd_store_footprint( fec_max );
29 9 : if( FD_UNLIKELY( !footprint ) ) {
30 0 : FD_LOG_WARNING(( "bad fec_max (%lu)", fec_max ));
31 0 : return NULL;
32 0 : }
33 :
34 9 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
35 9 : if( FD_UNLIKELY( !wksp ) ) {
36 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
37 0 : return NULL;
38 0 : }
39 :
40 : /* This seed value is very important. We have fec_max chains in the
41 : map, which means the size of each partition of buckets should be
42 : fec_max / part_cnt. When inserting into the map, we use the
43 : partition_slot_cnt as the seed, so that the modified hash function
44 : can use the seed/partition_slot_cnt to hash the key into the
45 : correct partition. */
46 :
47 9 : ulong part_slot_cnt = fec_max / part_cnt;
48 9 : ulong seed = part_slot_cnt;
49 :
50 9 : FD_SCRATCH_ALLOC_INIT( l, shmem );
51 9 : fd_store_t * store = FD_SCRATCH_ALLOC_APPEND( l, fd_store_align(), sizeof(fd_store_t) );
52 9 : void * map = FD_SCRATCH_ALLOC_APPEND( l, fd_store_map_align(), fd_store_map_footprint ( fec_max ) );
53 9 : void * shpool = FD_SCRATCH_ALLOC_APPEND( l, fd_store_pool_align(), fd_store_pool_footprint() );
54 9 : void * shele = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_store_fec_t), sizeof(fd_store_fec_t)*fec_max );
55 9 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_store_align() ) == (ulong)shmem + footprint );
56 :
57 9 : fd_memset( store, 0, sizeof(fd_store_t) );
58 9 : store->store_gaddr = fd_wksp_gaddr_fast( wksp, store );
59 9 : store->pool_mem_gaddr = fd_wksp_gaddr_fast( wksp, shpool );
60 9 : store->pool_ele_gaddr = fd_wksp_gaddr_fast( wksp, shele );
61 9 : store->map_gaddr = fd_wksp_gaddr_fast( wksp, fd_store_map_join( fd_store_map_new ( map, fec_max, seed ) ) );
62 :
63 9 : store->part_cnt = part_cnt;
64 9 : store->fec_max = fec_max;
65 9 : store->root = null;
66 :
67 9 : fd_store_pool_t pool = fd_store_pool( store );
68 9 : if( FD_UNLIKELY( !fd_store_pool_new( shpool ) ) ) {
69 0 : FD_LOG_WARNING(( "fd_store_pool_new failed" ));
70 0 : return NULL;
71 0 : }
72 9 : fd_store_pool_reset( &pool, 0 );
73 :
74 9 : FD_COMPILER_MFENCE();
75 9 : FD_VOLATILE( store->magic ) = FD_STORE_MAGIC;
76 9 : FD_COMPILER_MFENCE();
77 :
78 9 : return shmem;
79 9 : }
80 :
81 : fd_store_t *
82 9 : fd_store_join( void * shstore ) {
83 :
84 9 : if( FD_UNLIKELY( !shstore ) ) {
85 0 : FD_LOG_WARNING(( "NULL store" ));
86 0 : return NULL;
87 0 : }
88 :
89 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)shstore, fd_store_align() ) ) ) {
90 0 : FD_LOG_WARNING(( "misaligned store" ));
91 0 : return NULL;
92 0 : }
93 :
94 9 : fd_wksp_t * wksp = fd_wksp_containing( shstore );
95 9 : if( FD_UNLIKELY( !wksp ) ) {
96 0 : FD_LOG_WARNING(( "store must be part of a workspace" ));
97 0 : return NULL;
98 0 : }
99 :
100 9 : fd_store_t * store = (fd_store_t *)shstore;
101 9 : if( FD_UNLIKELY( store->magic!=FD_STORE_MAGIC ) ) {
102 0 : FD_LOG_WARNING(( "bad magic" ));
103 0 : return NULL;
104 0 : }
105 :
106 9 : return store;
107 9 : }
108 :
109 : void *
110 3 : fd_store_leave( fd_store_t const * store ) {
111 :
112 3 : if( FD_UNLIKELY( !store ) ) {
113 0 : FD_LOG_WARNING(( "NULL store" ));
114 0 : return NULL;
115 0 : }
116 :
117 3 : return (void *)store;
118 3 : }
119 :
120 : void *
121 3 : fd_store_delete( void * shstore ) {
122 :
123 3 : if( FD_UNLIKELY( !shstore ) ) {
124 0 : FD_LOG_WARNING(( "NULL store" ));
125 0 : return NULL;
126 0 : }
127 :
128 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)shstore, fd_store_align() ) ) ) {
129 0 : FD_LOG_WARNING(( "misaligned store" ));
130 0 : return NULL;
131 0 : }
132 :
133 3 : fd_store_t * store = (fd_store_t *)shstore;
134 3 : if( FD_UNLIKELY( store->magic!=FD_STORE_MAGIC ) ) {
135 0 : FD_LOG_WARNING(( "bad magic" ));
136 0 : return NULL;
137 0 : }
138 :
139 3 : FD_COMPILER_MFENCE();
140 3 : FD_VOLATILE( store->magic ) = 0UL;
141 3 : FD_COMPILER_MFENCE();
142 :
143 3 : return shstore;
144 3 : }
145 :
146 : fd_store_fec_t *
147 : fd_store_insert( fd_store_t * store,
148 : ulong part_idx,
149 54 : fd_hash_t * merkle_root ) {
150 54 : if( FD_UNLIKELY( fd_store_query_const( store, merkle_root ) ) ) {
151 3 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
152 3 : FD_LOG_WARNING(( "Merkle root %s already in store. Ignoring insert.", merkle_root_b58 ));
153 3 : return NULL;
154 3 : }
155 :
156 51 : int err;
157 51 : fd_store_pool_t pool = fd_store_pool( store );
158 51 : fd_store_fec_t * fec = fd_store_pool_acquire( &pool, NULL, BLOCKING, &err );
159 :
160 51 : if( FD_UNLIKELY( err == FD_POOL_ERR_EMPTY ) ) { FD_LOG_WARNING(( "store full %s", fd_store_pool_strerror( err ) )); return NULL; } /* FIXME: eviction? max bound guaranteed for worst-case? */
161 51 : if( FD_UNLIKELY( err == FD_POOL_ERR_CORRUPT ) ) { FD_LOG_CRIT (( "store corrupt %s", fd_store_pool_strerror( err ) )); }
162 51 : FD_TEST( fec );
163 :
164 51 : fec->key.mr = *merkle_root;
165 51 : fec->key.part = part_idx;
166 51 : fec->cmr = hash_null;
167 51 : fec->next = null;
168 51 : fec->parent = null;
169 51 : fec->child = null;
170 51 : fec->sibling = null;
171 51 : fec->data_sz = 0UL;
172 51 : if( FD_UNLIKELY( store->root == null ) ) store->root = fd_store_pool_idx( &pool, fec );
173 51 : fd_store_map_ele_insert( fd_store_map( store ), fec, fd_store_fec0( store ) );
174 :
175 51 : return fec;
176 51 : }
177 :
178 : fd_store_fec_t *
179 39 : fd_store_link( fd_store_t * store, fd_hash_t * merkle_root, fd_hash_t * chained_merkle_root ) {
180 :
181 39 : # if FD_STORE_USE_HANDHOLDING
182 39 : if( FD_UNLIKELY( !fd_store_query_const( store, merkle_root ) ) ) {
183 0 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
184 0 : FD_LOG_WARNING(( "missing merkle root %s", merkle_root_b58 ) );
185 0 : return NULL;
186 0 : }
187 39 : if( FD_UNLIKELY( !fd_store_query_const( store, chained_merkle_root ) ) ) {
188 0 : FD_BASE58_ENCODE_32_BYTES( chained_merkle_root->key, chained_merkle_root_b58 );
189 0 : FD_LOG_WARNING(( "missing chained merkle root %s", chained_merkle_root_b58 ) );
190 0 : return NULL;
191 0 : }
192 39 : # endif
193 :
194 39 : fd_store_pool_t pool = fd_store_pool( store );
195 39 : fd_store_fec_t * parent = fd_store_query( store, chained_merkle_root );
196 39 : fd_store_fec_t * child = fd_store_query( store, merkle_root );
197 :
198 39 : if( FD_UNLIKELY( child->parent != null ) ) return child; /* already linked */
199 39 : child->parent = fd_store_pool_idx( &pool, parent );
200 39 : if( FD_LIKELY( parent->child == null ) ) {
201 36 : parent->child = fd_store_pool_idx( &pool, child ); /* set as left-child. */
202 36 : } else {
203 3 : fd_store_fec_t * curr = fd_store_pool_ele( &pool, parent->child );
204 3 : while( curr->sibling != null ) curr = fd_store_pool_ele( &pool, curr->sibling );
205 3 : curr->sibling = fd_store_pool_idx( &pool, child ); /* set as right-sibling. */
206 3 : }
207 39 : return child;
208 39 : }
209 :
210 : fd_store_fec_t *
211 : fd_store_publish( fd_store_t * store,
212 3 : fd_hash_t const * merkle_root ) {
213 :
214 3 : # if FD_STORE_USE_HANDHOLDING
215 3 : if( FD_UNLIKELY( !fd_store_query( store, merkle_root ) ) ) {
216 0 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
217 0 : FD_LOG_WARNING(( "merkle root %s not found", merkle_root_b58 ));
218 0 : return NULL;
219 0 : }
220 3 : # endif
221 :
222 3 : fd_store_map_t * map = fd_store_map ( store );
223 3 : fd_store_pool_t pool = fd_store_pool( store );
224 3 : fd_store_fec_t * fec0 = fd_store_fec0( store );
225 3 : fd_store_fec_t * oldr = fd_store_root( store );
226 3 : fd_store_fec_t * newr = fd_store_query( store, merkle_root );
227 :
228 : /* First, remove the previous root, and push it as the first element
229 : of the BFS queue. */
230 :
231 3 : fd_store_fec_t * head = fd_store_map_ele_remove( map, &oldr->key, NULL, fec0 );
232 3 : head->next = null; /* clear map next */
233 3 : fd_store_fec_t * tail = head; /* tail of BFS queue */
234 :
235 : /* Second, BFS down the tree, pruning all of root's ancestors and also
236 : any descendants of those ancestors. */
237 :
238 42 : while( FD_LIKELY( head ) ) {
239 39 : fd_store_fec_t * child = fd_store_pool_ele( &pool, head->child ); /* left-child */
240 78 : while( FD_LIKELY( child ) ) { /* iterate over children */
241 39 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
242 36 : tail->next = fd_store_map_idx_remove( map, &child->key, null, fec0 ); /* remove node from map to reuse `.next` */
243 36 : tail = fd_store_pool_ele( &pool, tail->next ); /* push onto BFS queue (so descendants can be pruned) */
244 36 : tail->next = null; /* clear map next */
245 36 : }
246 39 : child = fd_store_pool_ele( &pool, child->sibling ); /* right-sibling */
247 39 : }
248 39 : fd_store_fec_t * next = fd_store_pool_ele( &pool, head->next ); /* pophead */
249 39 : int err = fd_store_pool_release( &pool, head, BLOCKING ); /* release */
250 39 : if( FD_UNLIKELY( err ) ) FD_LOG_CRIT(( "failed to release fec %s", fd_store_pool_strerror( err ) ));
251 39 : head = next; /* advance */
252 39 : }
253 3 : newr->parent = null; /* unlink old root */
254 3 : store->root = fd_store_pool_idx( &pool, newr ); /* replace with new root */
255 3 : return newr;
256 3 : }
257 :
258 : fd_store_t *
259 3 : fd_store_clear( fd_store_t * store ) {
260 :
261 3 : # if FD_STORE_USE_HANDHOLDING
262 3 : if( FD_UNLIKELY( !fd_store_root( store ) ) ) { FD_LOG_WARNING(( "calling clear on an empty store" )); return NULL; }
263 3 : # endif
264 :
265 3 : fd_store_map_t * map = fd_store_map( store );
266 3 : fd_store_pool_t pool = fd_store_pool( store );
267 3 : fd_store_fec_t * fec0 = fd_store_fec0( store );
268 :
269 3 : fd_store_fec_t * head = fd_store_root( store );
270 3 : fd_store_fec_t * tail = head;
271 :
272 3 : for( fd_store_map_iter_t iter = fd_store_map_iter_init( map, fec0 );
273 6 : !fd_store_map_iter_done( iter, map, fec0 );
274 3 : iter = fd_store_map_iter_next( iter, map, fec0 ) ) {
275 3 : ulong idx = fd_store_map_iter_idx( iter, map, fec0 );
276 3 : if( FD_UNLIKELY( idx == fd_store_pool_idx( &pool, head ) ) ) continue;
277 0 : tail->sibling = idx;
278 0 : tail = fd_store_pool_ele( &pool, tail->sibling );
279 0 : }
280 3 : tail->sibling = null;
281 3 : for( ulong idx = fd_store_pool_idx( &pool, head );
282 6 : FD_LIKELY( idx != null );
283 3 : idx = fd_store_pool_ele( &pool, idx )->sibling ) {
284 3 : fd_store_fec_t * fec = fd_store_pool_ele( &pool, idx );
285 3 : fd_store_map_idx_remove( map, &fec->key, null, fec0 );
286 3 : fd_store_pool_release( &pool, fec, 1 );
287 3 : }
288 3 : store->root = null;
289 3 : return store;
290 3 : }
291 :
292 : int
293 3 : fd_store_verify( fd_store_t * store ) {
294 :
295 3 : fd_store_map_t * map = fd_store_map( store );
296 3 : fd_store_fec_t * fec0 = fd_store_fec0( store );
297 :
298 3 : ulong part_sz = store->fec_max / store->part_cnt;
299 3 : if( part_sz != map->seed ) {
300 0 : FD_LOG_WARNING(( "part_sz (%lu) != map->seed (%lu)", part_sz, map->seed ));
301 0 : return -1;
302 0 : }
303 :
304 : /* iter the map, check that the partitions are correct */
305 :
306 3 : for( fd_store_map_iter_t iter = fd_store_map_iter_init( map, fec0 ); !fd_store_map_iter_done( iter, map, fec0 ); iter = fd_store_map_iter_next( iter, map, fec0 ) ) {
307 0 : fd_store_fec_t const * fec = fd_store_map_iter_ele_const( iter, map, fec0 );
308 0 : if( FD_UNLIKELY( !fec ) ) {
309 0 : FD_LOG_WARNING(( "NULL ele" ));
310 0 : return -1;
311 0 : }
312 0 : ulong chain_idx = fd_store_map_private_chain_idx( &fec->key, map->seed, map->chain_cnt );
313 : /* the chain_idx should be in the range of the partition */
314 0 : if( FD_UNLIKELY( chain_idx < part_sz * fec->key.part || chain_idx >= part_sz * (fec->key.part + 1) ) ) {
315 0 : FD_LOG_WARNING(( "chain_idx %lu not in range %lu-%lu", chain_idx, part_sz * fec->key.part, part_sz * (fec->key.part + 1) ) );
316 0 : return -1;
317 0 : }
318 0 : }
319 3 : fd_store_pool_t pool = fd_store_pool( store );
320 3 : if( FD_UNLIKELY( fd_store_pool_verify( &pool )==-1 ) ) return -1;
321 3 : return fd_store_map_verify( map, store->fec_max, fec0 );
322 3 : }
323 :
324 : #include <stdio.h>
325 :
326 : static void
327 42 : print( fd_store_t const * store, fd_store_fec_t const * fec, int space, const char * prefix ) {
328 :
329 42 : if( fec == NULL ) return;
330 42 : if( space > 0 ) printf( "\n" );
331 798 : for( int i = 0; i < space; i++ ) printf( " " );
332 42 : FD_BASE58_ENCODE_32_BYTES( fec->key.mr.key, key_mr_b58 );
333 42 : printf( "%s%s", prefix, key_mr_b58 );
334 :
335 42 : fd_store_pool_t pool = fd_store_pool( store );
336 42 : fd_store_fec_t const * curr = fd_store_pool_ele_const( &pool, fec->child );
337 42 : char new_prefix[1024]; /* FIXME size this correctly */
338 81 : while( curr ) {
339 39 : if( fd_store_pool_ele_const( &pool, curr->sibling ) ) {
340 3 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
341 3 : print( store, curr, space + 4, new_prefix );
342 36 : } else {
343 36 : sprintf( new_prefix, "└── " ); /* end branch */
344 36 : print( store, curr, space + 4, new_prefix );
345 36 : }
346 39 : curr = fd_store_pool_ele_const( &pool, curr->sibling );
347 39 : }
348 42 : }
349 :
350 : void
351 3 : fd_store_print( fd_store_t const * store ) {
352 3 : FD_LOG_NOTICE( ( "\n\n[Store]" ) );
353 3 : print( store, fd_store_root_const( store ), 0, "" );
354 : printf( "\n\n" );
355 3 : }
|
