Line data Source code
1 : #include "fd_funk.h"
2 : #include <stdio.h>
3 :
4 : ulong
5 18 : fd_funk_align( void ) {
6 18 : return alignof(fd_funk_t);
7 18 : }
8 :
9 : ulong
10 18 : fd_funk_footprint( void ) {
11 18 : return sizeof(fd_funk_t);
12 18 : }
13 :
14 : /* TODO: Consider letter user just passing a join of alloc to use,
15 : inferring the backing wksp and cgroup_hint from that and then
16 : allocating exclusively from that? */
17 :
18 : void *
19 : fd_funk_new( void * shmem,
20 : ulong wksp_tag,
21 : ulong seed,
22 : ulong txn_max,
23 48 : ulong rec_max ) {
24 48 : fd_funk_t * funk = (fd_funk_t *)shmem;
25 :
26 48 : if( FD_UNLIKELY( !funk ) ) {
27 3 : FD_LOG_WARNING(( "NULL funk" ));
28 3 : return NULL;
29 3 : }
30 :
31 45 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)funk, fd_funk_align() ) ) ) {
32 3 : FD_LOG_WARNING(( "misaligned funk" ));
33 3 : return NULL;
34 3 : }
35 :
36 42 : if( FD_UNLIKELY( !wksp_tag ) ) {
37 3 : FD_LOG_WARNING(( "bad wksp_tag" ));
38 3 : return NULL;
39 3 : }
40 :
41 39 : fd_wksp_t * wksp = fd_wksp_containing( funk );
42 39 : if( FD_UNLIKELY( !wksp ) ) {
43 3 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
44 3 : return NULL;
45 3 : }
46 :
47 36 : if( txn_max>FD_FUNK_TXN_IDX_NULL ) { /* See note in fd_funk.h about this limit */
48 3 : FD_LOG_WARNING(( "txn_max too large for index compression" ));
49 3 : return NULL;
50 3 : }
51 :
52 33 : void * txn_shmem = fd_wksp_alloc_laddr( wksp, fd_funk_txn_map_align(), fd_funk_txn_map_footprint( txn_max ), wksp_tag );
53 33 : if( FD_UNLIKELY( !txn_shmem ) ) {
54 3 : FD_LOG_WARNING(( "txn_max too large for workspace" ));
55 3 : return NULL;
56 3 : }
57 :
58 30 : void * txn_shmap = fd_funk_txn_map_new( txn_shmem, txn_max, seed );
59 30 : if( FD_UNLIKELY( !txn_shmap ) ) {
60 0 : FD_LOG_WARNING(( "fd_funk_txn_map_new failed" ));
61 0 : fd_wksp_free_laddr( txn_shmem );
62 0 : return NULL;
63 0 : }
64 :
65 30 : fd_funk_txn_t * txn_map = fd_funk_txn_map_join( txn_shmap );
66 30 : if( FD_UNLIKELY( !txn_map ) ) {
67 0 : FD_LOG_WARNING(( "fd_funk_txn_map_join failed" ));
68 0 : fd_wksp_free_laddr( fd_funk_txn_map_delete( txn_shmap ) );
69 0 : return NULL;
70 0 : }
71 :
72 30 : void * rec_shmem = fd_wksp_alloc_laddr( wksp, fd_funk_rec_map_align(), fd_funk_rec_map_footprint( rec_max ), wksp_tag );
73 30 : if( FD_UNLIKELY( !rec_shmem ) ) {
74 3 : FD_LOG_WARNING(( "rec_max too large for workspace" ));
75 3 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( txn_map ) ) );
76 3 : return NULL;
77 3 : }
78 :
79 27 : void * rec_shmap = fd_funk_rec_map_new( rec_shmem, rec_max, seed );
80 27 : if( FD_UNLIKELY( !rec_shmap ) ) {
81 0 : FD_LOG_WARNING(( "fd_funk_rec_map_new failed" ));
82 0 : fd_wksp_free_laddr( rec_shmem );
83 0 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( txn_map ) ) );
84 0 : return NULL;
85 0 : }
86 :
87 27 : fd_funk_rec_t * rec_map = fd_funk_rec_map_join( rec_shmap );
88 27 : if( FD_UNLIKELY( !rec_map ) ) {
89 0 : FD_LOG_WARNING(( "fd_funk_rec_map_join failed" ));
90 0 : fd_wksp_free_laddr( fd_funk_rec_map_delete( rec_shmap ) );
91 0 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( txn_map ) ) );
92 0 : return NULL;
93 0 : }
94 :
95 27 : void * alloc_shmem = fd_wksp_alloc_laddr( wksp, fd_alloc_align(), fd_alloc_footprint(), wksp_tag );
96 27 : if( FD_UNLIKELY( !alloc_shmem ) ) {
97 0 : FD_LOG_WARNING(( "fd_alloc too large for workspace" ));
98 0 : fd_wksp_free_laddr( fd_funk_rec_map_delete( fd_funk_rec_map_leave( rec_map ) ) );
99 0 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( txn_map ) ) );
100 0 : return NULL;
101 0 : }
102 :
103 27 : void * alloc_shalloc = fd_alloc_new( alloc_shmem, wksp_tag );
104 27 : if( FD_UNLIKELY( !alloc_shalloc ) ) {
105 0 : FD_LOG_WARNING(( "fd_alloc_new failed" ));
106 0 : fd_wksp_free_laddr( fd_funk_rec_map_delete( fd_funk_rec_map_leave( rec_map ) ) );
107 0 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( txn_map ) ) );
108 0 : return NULL;
109 0 : }
110 :
111 27 : fd_alloc_t * alloc = fd_alloc_join( alloc_shalloc, 0UL ); /* TODO: Consider letting user pass the cgroup hint? */
112 27 : if( FD_UNLIKELY( !alloc ) ) {
113 0 : FD_LOG_WARNING(( "fd_alloc_join failed" ));
114 0 : fd_wksp_free_laddr( fd_alloc_delete( alloc_shalloc ) );
115 0 : fd_wksp_free_laddr( fd_funk_rec_map_delete( fd_funk_rec_map_leave( rec_map ) ) );
116 0 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( txn_map ) ) );
117 0 : return NULL;
118 0 : }
119 :
120 27 : fd_memset( funk, 0, fd_funk_footprint() );
121 :
122 27 : funk->funk_gaddr = fd_wksp_gaddr_fast( wksp, funk );
123 27 : funk->wksp_tag = wksp_tag;
124 27 : funk->seed = seed;
125 27 : funk->cycle_tag = 3UL; /* various verify functions use tags 0-2 */
126 :
127 27 : funk->txn_max = txn_max;
128 27 : funk->txn_map_gaddr = fd_wksp_gaddr_fast( wksp, txn_map ); /* Note that this persists the join until delete */
129 27 : funk->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
130 27 : funk->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
131 :
132 27 : fd_funk_txn_xid_set_root( funk->root );
133 27 : fd_funk_txn_xid_set_root( funk->last_publish );
134 :
135 27 : funk->rec_max = rec_max;
136 27 : funk->rec_map_gaddr = fd_wksp_gaddr_fast( wksp, rec_map ); /* Note that this persists the join until delete */
137 27 : funk->rec_head_idx = FD_FUNK_REC_IDX_NULL;
138 27 : funk->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
139 :
140 27 : funk->alloc_gaddr = fd_wksp_gaddr_fast( wksp, alloc ); /* Note that this persists the join until delete */
141 :
142 27 : funk->write_lock = 0UL;
143 :
144 27 : FD_COMPILER_MFENCE();
145 27 : FD_VOLATILE( funk->magic ) = FD_FUNK_MAGIC;
146 27 : FD_COMPILER_MFENCE();
147 :
148 27 : return (void *)funk;
149 27 : }
150 :
151 : fd_funk_t *
152 39 : fd_funk_join( void * shfunk ) {
153 39 : fd_funk_t * funk = (fd_funk_t *)shfunk;
154 :
155 39 : if( FD_UNLIKELY( !funk ) ) {
156 3 : FD_LOG_WARNING(( "NULL shfunk" ));
157 3 : return NULL;
158 3 : }
159 :
160 36 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)funk, fd_funk_align() ) ) ) {
161 3 : FD_LOG_WARNING(( "misaligned shfunk" ));
162 3 : return NULL;
163 3 : }
164 :
165 33 : fd_wksp_t * wksp = fd_wksp_containing( funk );
166 33 : if( FD_UNLIKELY( !wksp ) ) {
167 3 : FD_LOG_WARNING(( "shfunk must be part of a workspace" ));
168 3 : return NULL;
169 3 : }
170 :
171 30 : if( FD_UNLIKELY( funk->magic!=FD_FUNK_MAGIC ) ) {
172 3 : FD_LOG_WARNING(( "bad magic" ));
173 3 : return NULL;
174 3 : }
175 :
176 : #ifdef FD_FUNK_WKSP_PROTECT
177 : fd_wksp_mprotect( wksp, 1 );
178 : #endif
179 :
180 27 : return funk;
181 30 : }
182 :
183 : void *
184 27 : fd_funk_leave( fd_funk_t * funk ) {
185 :
186 27 : if( FD_UNLIKELY( !funk ) ) {
187 3 : FD_LOG_WARNING(( "NULL funk" ));
188 3 : return NULL;
189 3 : }
190 :
191 24 : return (void *)funk;
192 27 : }
193 :
194 : void *
195 36 : fd_funk_delete( void * shfunk ) {
196 36 : fd_funk_t * funk = (fd_funk_t *)shfunk;
197 :
198 36 : if( FD_UNLIKELY( !funk ) ) {
199 3 : FD_LOG_WARNING(( "NULL shfunk" ));
200 3 : return NULL;
201 3 : }
202 :
203 33 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)funk, fd_funk_align() ) ) ) {
204 3 : FD_LOG_WARNING(( "misaligned shfunk" ));
205 3 : return NULL;
206 3 : }
207 :
208 30 : fd_wksp_t * wksp = fd_wksp_containing( funk );
209 30 : if( FD_UNLIKELY( !wksp ) ) {
210 3 : FD_LOG_WARNING(( "shfunk must be part of a workspace" ));
211 3 : return NULL;
212 3 : }
213 :
214 27 : if( FD_UNLIKELY( funk->magic!=FD_FUNK_MAGIC ) ) {
215 3 : FD_LOG_WARNING(( "bad magic" ));
216 3 : return NULL;
217 3 : }
218 :
219 24 : fd_wksp_free_laddr( fd_alloc_delete ( fd_alloc_leave ( fd_funk_alloc ( funk, wksp ) ) ) );
220 24 : fd_wksp_free_laddr( fd_funk_rec_map_delete( fd_funk_rec_map_leave( fd_funk_rec_map( funk, wksp ) ) ) );
221 24 : fd_wksp_free_laddr( fd_funk_txn_map_delete( fd_funk_txn_map_leave( fd_funk_txn_map( funk, wksp ) ) ) );
222 :
223 24 : FD_COMPILER_MFENCE();
224 24 : FD_VOLATILE( funk->magic ) = 0UL;
225 24 : FD_COMPILER_MFENCE();
226 :
227 24 : return funk;
228 27 : }
229 :
230 : int
231 9692196 : fd_funk_verify( fd_funk_t * funk ) {
232 :
233 319842468 : # define TEST(c) do { \
234 319842468 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
235 319842468 : } while(0)
236 :
237 9692196 : TEST( funk );
238 :
239 : /* Test metadata */
240 :
241 9692196 : TEST( funk->magic==FD_FUNK_MAGIC );
242 :
243 9692196 : ulong funk_gaddr = funk->funk_gaddr;
244 9692196 : TEST( funk_gaddr );
245 9692196 : fd_wksp_t * wksp = fd_funk_wksp( funk );
246 9692196 : TEST( wksp );
247 9692196 : TEST( fd_wksp_laddr_fast( wksp, funk_gaddr )==(void *)funk );
248 9692196 : TEST( fd_wksp_gaddr_fast( wksp, funk )==funk_gaddr );
249 :
250 9692196 : ulong wksp_tag = fd_funk_wksp_tag( funk );
251 9692196 : TEST( !!wksp_tag );
252 :
253 9692196 : ulong seed = funk->seed; /* seed can be anything */
254 :
255 9692196 : TEST( funk->cycle_tag>2UL );
256 :
257 : /* Test transaction map */
258 :
259 9692196 : ulong txn_max = funk->txn_max;
260 9692196 : TEST( txn_max<=FD_FUNK_TXN_IDX_NULL );
261 :
262 9692196 : ulong txn_map_gaddr = funk->txn_map_gaddr;
263 9692196 : TEST( txn_map_gaddr );
264 9692196 : TEST( fd_wksp_tag( wksp, txn_map_gaddr-1UL )==wksp_tag ); /* When txn_max is 0, txn_map_gaddr can be first byte after alloc */
265 9692196 : fd_funk_txn_t * txn_map = fd_funk_txn_map( funk, wksp );
266 9692196 : TEST( txn_map );
267 9692196 : TEST( txn_max==fd_funk_txn_map_key_max( txn_map ) );
268 9692196 : TEST( seed ==fd_funk_txn_map_seed ( txn_map ) );
269 :
270 9692196 : ulong child_head_idx = fd_funk_txn_idx( funk->child_head_cidx );
271 9692196 : ulong child_tail_idx = fd_funk_txn_idx( funk->child_tail_cidx );
272 :
273 9692196 : int null_child_head = fd_funk_txn_idx_is_null( child_head_idx );
274 9692196 : int null_child_tail = fd_funk_txn_idx_is_null( child_tail_idx );
275 :
276 9692196 : if( !txn_max ) TEST( null_child_head & null_child_tail );
277 9692190 : else {
278 9692190 : if( null_child_head ) TEST( null_child_tail );
279 8283987 : else TEST( child_head_idx<txn_max );
280 :
281 9692190 : if( null_child_tail ) TEST( null_child_head );
282 8283987 : else TEST( child_tail_idx<txn_max );
283 9692190 : }
284 :
285 9692196 : if( !txn_max ) TEST( fd_funk_txn_idx_is_null( child_tail_idx ) );
286 :
287 9692196 : fd_funk_txn_xid_t const * root = fd_funk_root( funk );
288 9692196 : TEST( root ); /* Practically guaranteed */
289 9692196 : TEST( fd_funk_txn_xid_eq_root( root ) );
290 :
291 9692196 : fd_funk_txn_xid_t * last_publish = funk->last_publish;
292 9692196 : TEST( last_publish ); /* Practically guaranteed */
293 : /* (*last_publish) only be root at creation and anything but root post
294 : creation. But we don't know which situation applies here so this
295 : could be anything. */
296 :
297 9692196 : TEST( !fd_funk_txn_verify( funk ) );
298 :
299 : /* Test record map */
300 :
301 9692196 : ulong rec_max = funk->rec_max;
302 9692196 : TEST( rec_max<=FD_FUNK_TXN_IDX_NULL );
303 :
304 9692196 : ulong rec_map_gaddr = funk->rec_map_gaddr;
305 9692196 : TEST( rec_map_gaddr );
306 9692196 : TEST( fd_wksp_tag( wksp, rec_map_gaddr-1UL )==wksp_tag ); /* When rec_max is zero, rec_map_gaddr can be first byte after alloc */
307 9692196 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
308 9692196 : TEST( rec_map );
309 9692196 : TEST( rec_max==fd_funk_rec_map_key_max( rec_map ) );
310 9692196 : TEST( seed ==fd_funk_rec_map_seed ( rec_map ) );
311 :
312 9692196 : ulong rec_head_idx = funk->rec_head_idx;
313 9692196 : ulong rec_tail_idx = funk->rec_tail_idx;
314 :
315 9692196 : int null_rec_head = fd_funk_rec_idx_is_null( rec_head_idx );
316 9692196 : int null_rec_tail = fd_funk_rec_idx_is_null( rec_tail_idx );
317 :
318 9692196 : if( !rec_max ) TEST( null_rec_head & null_rec_tail );
319 9692190 : else {
320 9692190 : if( null_rec_head ) TEST( null_rec_tail );
321 6546444 : else TEST( rec_head_idx<rec_max );
322 :
323 9692190 : if( null_rec_tail ) TEST( null_rec_head );
324 6546444 : else TEST( rec_tail_idx<rec_max );
325 9692190 : }
326 :
327 9692196 : if( !rec_max ) TEST( fd_funk_rec_idx_is_null( rec_tail_idx ) );
328 :
329 9692196 : TEST( !fd_funk_rec_verify( funk ) );
330 :
331 : /* Test values */
332 :
333 9692196 : ulong alloc_gaddr = funk->alloc_gaddr;
334 9692196 : TEST( alloc_gaddr );
335 9692196 : TEST( fd_wksp_tag( wksp, alloc_gaddr )==wksp_tag );
336 9692196 : fd_alloc_t * alloc = fd_funk_alloc( funk, wksp );
337 9692196 : TEST( alloc );
338 :
339 9692196 : TEST( !fd_funk_val_verify( funk ) );
340 :
341 9692196 : # undef TEST
342 :
343 9692196 : return FD_FUNK_SUCCESS;
344 9692196 : }
345 :
346 : static char *
347 0 : fd_smart_size( ulong sz, char * tmp, size_t tmpsz ) {
348 0 : if( sz <= (1UL<<7) )
349 0 : snprintf( tmp, tmpsz, "%lu B", sz );
350 0 : else if( sz <= (1UL<<17) )
351 0 : snprintf( tmp, tmpsz, "%.3f KB", ((double)sz/((double)(1UL<<10))) );
352 0 : else if( sz <= (1UL<<27) )
353 0 : snprintf( tmp, tmpsz, "%.3f MB", ((double)sz/((double)(1UL<<20))) );
354 0 : else
355 0 : snprintf( tmp, tmpsz, "%.3f GB", ((double)sz/((double)(1UL<<30))) );
356 0 : return tmp;
357 0 : }
358 :
359 : void
360 0 : fd_funk_log_mem_usage( fd_funk_t * funk ) {
361 0 : char tmp1[100];
362 0 : char tmp2[100];
363 :
364 0 : FD_LOG_NOTICE(( "funk base footprint: %s",
365 0 : fd_smart_size( fd_funk_footprint(), tmp1, sizeof(tmp1) ) ));
366 0 : fd_wksp_t * wksp = fd_funk_wksp( funk );
367 0 : fd_funk_txn_t const * txn_map = fd_funk_txn_map( funk, wksp );
368 0 : FD_LOG_NOTICE(( "txn table footprint: %s (%lu entries used out of %lu, %lu%%)",
369 0 : fd_smart_size( fd_funk_txn_map_footprint( funk->txn_max ), tmp1, sizeof(tmp1) ),
370 0 : fd_funk_txn_map_key_cnt( txn_map ),
371 0 : fd_funk_txn_map_key_max( txn_map ),
372 0 : (100U*fd_funk_txn_map_key_cnt( txn_map )) / fd_funk_txn_map_key_max( txn_map ) ));
373 0 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
374 0 : FD_LOG_NOTICE(( "rec table footprint: %s (%lu entries used out of %lu, %lu%%)",
375 0 : fd_smart_size( fd_funk_rec_map_footprint( funk->rec_max ), tmp1, sizeof(tmp1) ),
376 0 : fd_funk_rec_map_key_cnt( rec_map ),
377 0 : fd_funk_rec_map_key_max( rec_map ),
378 0 : (100U*fd_funk_rec_map_key_cnt( rec_map )) / fd_funk_rec_map_key_max( rec_map ) ));
379 0 : ulong val_cnt = 0;
380 0 : ulong val_min = ULONG_MAX;
381 0 : ulong val_max = 0;
382 0 : ulong val_used = 0;
383 0 : ulong val_alloc = 0;
384 0 : for( fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter_init( rec_map );
385 0 : !fd_funk_rec_map_iter_done( rec_map, iter );
386 0 : iter = fd_funk_rec_map_iter_next( rec_map, iter ) ) {
387 0 : fd_funk_rec_t * rec = fd_funk_rec_map_iter_ele( rec_map, iter );
388 0 : val_cnt ++;
389 0 : val_min = fd_ulong_min( val_min, rec->val_sz );
390 0 : val_max = fd_ulong_max( val_max, rec->val_sz );
391 0 : val_used += rec->val_sz;
392 0 : val_alloc += rec->val_max;
393 0 : }
394 0 : ulong avg_size = val_cnt ? (val_used / val_cnt) : 0;
395 0 : FD_LOG_NOTICE(( " rec count: %lu, min size: %lu, avg_size: %lu, max_size: %lu, total_size: %s, total_allocated: %s",
396 0 : val_cnt, val_min, avg_size, val_max,
397 0 : fd_smart_size( val_used, tmp1, sizeof(tmp1) ),
398 0 : fd_smart_size( val_alloc, tmp2, sizeof(tmp2) ) ));
399 0 : }
400 :
401 : #include "../flamenco/fd_rwlock.h"
402 : static fd_rwlock_t lock[ 1 ] = {0};
403 :
404 : void
405 5272857 : fd_funk_start_write( fd_funk_t * funk ) {
406 5272857 : fd_rwlock_write( lock );
407 : #ifdef FD_FUNK_WKSP_PROTECT
408 : fd_wksp_mprotect( fd_funk_wksp( funk ), 0 );
409 : #endif
410 5272857 : # if FD_HAS_THREADS
411 5272857 : register ulong oldval;
412 5272857 : for(;;) {
413 5272857 : oldval = funk->write_lock;
414 5272857 : if( FD_LIKELY( FD_ATOMIC_CAS( &funk->write_lock, oldval, oldval+1U) == oldval ) ) break;
415 0 : FD_SPIN_PAUSE();
416 0 : }
417 5272857 : if( FD_UNLIKELY(oldval&1UL) ) {
418 0 : FD_LOG_CRIT(( "attempt to lock funky when it is already locked" ));
419 0 : }
420 5272857 : FD_COMPILER_MFENCE();
421 : # else
422 : (void)funk;
423 : # endif
424 5272857 : }
425 :
426 : void
427 5272857 : fd_funk_end_write( fd_funk_t * funk ) {
428 5272857 : # if FD_HAS_THREADS
429 5272857 : FD_COMPILER_MFENCE();
430 5272857 : register ulong oldval;
431 5272857 : for(;;) {
432 5272857 : oldval = funk->write_lock;
433 5272857 : if( FD_LIKELY( FD_ATOMIC_CAS( &funk->write_lock, oldval, oldval+1U) == oldval ) ) break;
434 0 : FD_SPIN_PAUSE();
435 0 : }
436 5272857 : if( FD_UNLIKELY(!(oldval&1UL)) ) {
437 0 : FD_LOG_CRIT(( "attempt to unlock funky when it is already unlocked" ));
438 0 : }
439 : # else
440 : (void)funk;
441 : # endif
442 : #ifdef FD_FUNK_WKSP_PROTECT
443 : fd_wksp_mprotect( fd_funk_wksp( funk ), 1 );
444 : #endif
445 5272857 : fd_rwlock_unwrite( lock );
446 5272857 : }
447 :
448 : void
449 550310652 : fd_funk_check_write( fd_funk_t * funk ) {
450 550310652 : ulong val = funk->write_lock;
451 550310652 : if( FD_UNLIKELY(!(val&1UL)) ) FD_LOG_CRIT(( "missing call to fd_funk_start_write" ));
452 550310652 : }
|
