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