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