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 :
151 54 : # if FD_STORE_USE_HANDHOLDING
152 54 : if( FD_UNLIKELY( fd_store_query_const( store, merkle_root ) ) ) { FD_LOG_WARNING(( "merkle root %s already in store", FD_BASE58_ENC_32_ALLOCA( merkle_root ) )); return NULL; }
153 51 : # endif
154 51 : int err;
155 :
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_WARNING(( "store corrupt %s", fd_store_pool_strerror( err ) )); return NULL; }
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 ) ) ) { FD_LOG_WARNING(( "missing merkle root %s", FD_BASE58_ENC_32_ALLOCA( merkle_root ) ) ); return NULL; }
182 39 : if( FD_UNLIKELY( !fd_store_query_const( store, chained_merkle_root ) ) ) { FD_LOG_WARNING(( "missing chained merkle root %s", FD_BASE58_ENC_32_ALLOCA( chained_merkle_root ) ) ); return NULL; }
183 39 : # endif
184 :
185 39 : fd_store_pool_t pool = fd_store_pool( store );
186 39 : fd_store_fec_t * parent = fd_store_query( store, chained_merkle_root );
187 39 : fd_store_fec_t * child = fd_store_query( store, merkle_root );
188 :
189 39 : child->parent = fd_store_pool_idx( &pool, parent );
190 39 : if( FD_LIKELY( parent->child == null ) ) {
191 36 : parent->child = fd_store_pool_idx( &pool, child ); /* set as left-child. */
192 36 : } else {
193 3 : fd_store_fec_t * curr = fd_store_pool_ele( &pool, parent->child );
194 3 : while( curr->sibling != null ) curr = fd_store_pool_ele( &pool, curr->sibling );
195 3 : curr->sibling = fd_store_pool_idx( &pool, child ); /* set as right-sibling. */
196 3 : }
197 39 : return child;
198 39 : }
199 :
200 : fd_store_fec_t *
201 : fd_store_publish( fd_store_t * store,
202 3 : fd_hash_t const * merkle_root ) {
203 :
204 3 : # if FD_STORE_USE_HANDHOLDING
205 3 : if( FD_UNLIKELY( !fd_store_query( store, merkle_root ) ) ) { FD_LOG_WARNING(( "merkle root %s not found", FD_BASE58_ENC_32_ALLOCA( merkle_root ) )); return NULL; }
206 3 : # endif
207 :
208 3 : fd_store_map_t * map = fd_store_map ( store );
209 3 : fd_store_pool_t pool = fd_store_pool( store );
210 3 : fd_store_fec_t * fec0 = fd_store_fec0( store );
211 3 : fd_store_fec_t * oldr = fd_store_root( store );
212 3 : fd_store_fec_t * newr = fd_store_query( store, merkle_root );
213 :
214 : /* First, remove the previous root, and push it as the first element
215 : of the BFS queue. */
216 :
217 3 : fd_store_fec_t * head = fd_store_map_ele_remove( map, &oldr->key, NULL, fec0 );
218 3 : head->next = null; /* clear map next */
219 3 : fd_store_fec_t * tail = head; /* tail of BFS queue */
220 :
221 : /* Second, BFS down the tree, pruning all of root's ancestors and also
222 : any descendants of those ancestors. */
223 :
224 42 : while( FD_LIKELY( head ) ) {
225 39 : fd_store_fec_t * child = fd_store_pool_ele( &pool, head->child ); /* left-child */
226 78 : while( FD_LIKELY( child ) ) { /* iterate over children */
227 39 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
228 36 : tail->next = fd_store_map_idx_remove( map, &child->key, null, fec0 ); /* remove node from map to reuse `.next` */
229 36 : tail = fd_store_pool_ele( &pool, tail->next ); /* push onto BFS queue (so descendants can be pruned) */
230 36 : tail->next = null; /* clear map next */
231 36 : }
232 39 : child = fd_store_pool_ele( &pool, child->sibling ); /* right-sibling */
233 39 : }
234 39 : fd_store_fec_t * next = fd_store_pool_ele( &pool, head->next ); /* pophead */
235 39 : int err = fd_store_pool_release( &pool, head, BLOCKING ); /* release */
236 39 : if( FD_UNLIKELY( err != FD_POOL_SUCCESS ) ) {
237 0 : FD_LOG_WARNING(( "failed to release fec %s", fd_store_pool_strerror( err ) ));
238 0 : return NULL;
239 0 : }
240 39 : head = next; /* advance */
241 39 : }
242 3 : newr->parent = null; /* unlink old root */
243 3 : store->root = fd_store_pool_idx( &pool, newr ); /* replace with new root */
244 3 : return newr;
245 3 : }
246 :
247 : fd_store_t *
248 3 : fd_store_clear( fd_store_t * store ) {
249 :
250 3 : # if FD_STORE_USE_HANDHOLDING
251 3 : if( FD_UNLIKELY( !fd_store_root( store ) ) ) { FD_LOG_WARNING(( "calling clear on an empty store" )); return NULL; }
252 3 : # endif
253 :
254 3 : fd_store_map_t * map = fd_store_map( store );
255 3 : fd_store_pool_t pool = fd_store_pool( store );
256 3 : fd_store_fec_t * fec0 = fd_store_fec0( store );
257 :
258 3 : fd_store_fec_t * head = fd_store_root( store );
259 3 : fd_store_fec_t * tail = head;
260 :
261 3 : for( fd_store_map_iter_t iter = fd_store_map_iter_init( map, fec0 );
262 6 : !fd_store_map_iter_done( iter, map, fec0 );
263 3 : iter = fd_store_map_iter_next( iter, map, fec0 ) ) {
264 3 : ulong idx = fd_store_map_iter_idx( iter, map, fec0 );
265 3 : if( FD_UNLIKELY( idx == fd_store_pool_idx( &pool, head ) ) ) continue;
266 0 : tail->sibling = idx;
267 0 : tail = fd_store_pool_ele( &pool, tail->sibling );
268 0 : }
269 3 : tail->sibling = null;
270 3 : for( ulong idx = fd_store_pool_idx( &pool, head );
271 6 : FD_LIKELY( idx != null );
272 3 : idx = fd_store_pool_ele( &pool, idx )->sibling ) {
273 3 : fd_store_fec_t * fec = fd_store_pool_ele( &pool, idx );
274 3 : fd_store_map_idx_remove( map, &fec->key, null, fec0 );
275 3 : fd_store_pool_release( &pool, fec, 1 );
276 3 : }
277 3 : store->root = null;
278 3 : return store;
279 3 : }
280 :
281 : int
282 3 : fd_store_verify( fd_store_t * store ) {
283 :
284 3 : fd_store_map_t * map = fd_store_map( store );
285 3 : fd_store_fec_t * fec0 = fd_store_fec0( store );
286 :
287 3 : ulong part_sz = store->fec_max / store->part_cnt;
288 3 : if( part_sz != map->seed ) {
289 0 : FD_LOG_WARNING(( "part_sz (%lu) != map->seed (%lu)", part_sz, map->seed ));
290 0 : return -1;
291 0 : }
292 :
293 : /* iter the map, check that the partitions are correct */
294 :
295 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 ) ) {
296 0 : fd_store_fec_t const * fec = fd_store_map_iter_ele_const( iter, map, fec0 );
297 0 : if( FD_UNLIKELY( !fec ) ) {
298 0 : FD_LOG_WARNING(( "NULL ele" ));
299 0 : return -1;
300 0 : }
301 0 : ulong chain_idx = fd_store_map_private_chain_idx( &fec->key, map->seed, map->chain_cnt );
302 : /* the chain_idx should be in the range of the partition */
303 0 : if( FD_UNLIKELY( chain_idx < part_sz * fec->key.part || chain_idx >= part_sz * (fec->key.part + 1) ) ) {
304 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) ) );
305 0 : return -1;
306 0 : }
307 0 : }
308 3 : fd_store_pool_t pool = fd_store_pool_const( store );
309 3 : if( FD_UNLIKELY( fd_store_pool_verify( &pool )==-1 ) ) return -1;
310 3 : return fd_store_map_verify( map, store->fec_max, fec0 );
311 3 : }
312 :
313 : #include <stdio.h>
314 :
315 : static void
316 42 : print( fd_store_t const * store, fd_store_fec_t const * fec, int space, const char * prefix ) {
317 :
318 42 : if( fec == NULL ) return;
319 42 : if( space > 0 ) printf( "\n" );
320 798 : for( int i = 0; i < space; i++ ) printf( " " );
321 42 : printf( "%s%s", prefix, FD_BASE58_ENC_32_ALLOCA( &fec->key.mr ) );
322 :
323 0 : fd_store_pool_t pool = fd_store_pool_const( store );
324 42 : fd_store_fec_t const * curr = fd_store_pool_ele_const( &pool, fec->child );
325 42 : char new_prefix[1024]; /* FIXME size this correctly */
326 81 : while( curr ) {
327 39 : if( fd_store_pool_ele_const( &pool, curr->sibling ) ) {
328 3 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
329 3 : print( store, curr, space + 4, new_prefix );
330 36 : } else {
331 36 : sprintf( new_prefix, "└── " ); /* end branch */
332 36 : print( store, curr, space + 4, new_prefix );
333 36 : }
334 39 : curr = fd_store_pool_ele_const( &pool, curr->sibling );
335 39 : }
336 42 : }
337 :
338 : void
339 3 : fd_store_print( fd_store_t const * store ) {
340 3 : FD_LOG_NOTICE( ( "\n\n[Store]" ) );
341 3 : print( store, fd_store_root_const( store ), 0, "" );
342 : printf( "\n\n" );
343 3 : }
|
