Line data Source code
1 : #define _GNU_SOURCE
2 : #include "fd_gui_store.h"
3 :
4 : #include <errno.h> /* errno */
5 : #include <unistd.h> /* close, fallocate */
6 : #include <fcntl.h> /* open, O_RDWR/O_CREAT/O_TRUNC */
7 : #include <sys/mman.h> /* mmap, munmap, PROT_*, MAP_* */
8 :
9 0 : #define FD_GUI_STORE_MAGIC (0xf17e6d0c0117db04UL)
10 :
11 0 : #define FD_GUI_STORE_PAGE_SZ (4096UL)
12 :
13 : struct fd_gui_store_ring {
14 : ulong stride; /* align_up( hdr + val_sz, val_align ) */
15 : ulong region_capacity; /* whole slots per region (REGION_SZ/stride) */
16 : ulong key_off; /* KV key offset within val (0 for TS) */
17 : ulong key_sz; /* KV key width (0 for TS) */
18 : ulong val_sz; /* stored record size */
19 : ulong val_align; /* slot/record alignment */
20 : ulong ts_off; /* TS timestamp offset within val (0 for KV) */
21 : ulong granularity; /* TS window granularity (0 for KV) */
22 : int kind; /* FD_GUI_STORE_KIND_* */
23 : ulong head_cur; /* next cursor to write */
24 : ulong evict_cur; /* logical low-watermark */
25 : ulong tail_cur; /* oldest physically-present slot */
26 : };
27 : typedef struct fd_gui_store_ring fd_gui_store_ring_t;
28 :
29 0 : #define FD_GUI_STORE_SUPER_MAGIC (0xf17e6d0c0117db06UL) /* fd_gui_store regions, versioned */
30 :
31 : struct fd_gui_store_super {
32 : ulong magic;
33 : ulong size_bytes; /* configured ceiling (max file size) */
34 : ulong data_off; /* byte offset of region 0 within the file */
35 : ulong region_sz; /* bytes per region */
36 : ulong region_cnt; /* total regions in the pool */
37 : ulong ring_cnt;
38 : fd_gui_store_ring_t ring[ FD_GUI_STORE_MAX_RINGS ];
39 : };
40 : typedef struct fd_gui_store_super fd_gui_store_super_t;
41 :
42 : struct fd_gui_store_kv_idx_node {
43 : uint key; /* MAP_KEY: low 32 bits of ring->key_hash of the record's key */
44 : uint cur; /* low 32 bits of the ring slot's generation cursor */
45 : uint next; /* MAP_NEXT (chain link) */
46 : union {
47 : uint prev; /* MAP_PREV while acquired */
48 : uint pool_next; /* POOL_NEXT while free */
49 : };
50 : };
51 : typedef struct fd_gui_store_kv_idx_node fd_gui_store_kv_idx_node_t;
52 : FD_STATIC_ASSERT( sizeof(fd_gui_store_kv_idx_node_t)==16UL, fd_gui_store_kv_idx_node );
53 :
54 : #define MAP_NAME fd_gui_store_kv_idx
55 0 : #define MAP_KEY key
56 : #define MAP_KEY_T uint
57 0 : #define MAP_IDX_T uint
58 0 : #define MAP_ELE_T fd_gui_store_kv_idx_node_t
59 0 : #define MAP_NEXT next
60 0 : #define MAP_PREV prev
61 0 : #define MAP_KEY_EQ(k0,k1) ( *(k0)==*(k1) )
62 0 : #define MAP_KEY_HASH(k,s) fd_ulong_hash( (ulong)*(k) ^ (s) )
63 : #define MAP_MULTI 1
64 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
65 : #include "../../util/tmpl/fd_map_chain.c"
66 :
67 : #define POOL_NAME fd_gui_store_kv_pool
68 0 : #define POOL_T fd_gui_store_kv_idx_node_t
69 0 : #define POOL_NEXT pool_next
70 : #define POOL_IDX_T uint
71 : #include "../../util/tmpl/fd_pool.c"
72 :
73 : #define STACK_NAME fd_gui_store_freelist
74 : #define STACK_T ulong
75 : #include "../../util/tmpl/fd_stack.c"
76 :
77 : struct fd_gui_store_ring_rt {
78 : ulong reg_base; /* logical ordinal of oldest owned region */
79 : ulong reg_cnt; /* number of regions owned */
80 : ulong max_records; /* private KV index allowance */
81 : ulong base; /* protected base region count */
82 : };
83 : typedef struct fd_gui_store_ring_rt fd_gui_store_ring_rt_t;
84 :
85 : struct fd_gui_store_private {
86 : ulong magic; /* ==FD_GUI_STORE_MAGIC after fd_gui_store_new */
87 : ulong size; /* configured size ceiling in bytes */
88 : ulong ring_cnt;
89 : int fd; /* backing-file fd, or -1 */
90 : void * mapped; /* mmap base (the file) */
91 : ulong mapped_sz; /* size of `mapped` in bytes */
92 : ulong file_sz; /* current allocated file length */
93 : fd_gui_store_super_t * super; /* == mapped (page 0) */
94 : fd_gui_store_kv_idx_t * kv_idx[ FD_GUI_STORE_MAX_RINGS ]; /* per-KV-ring index (RAM); NULL for TS rings */
95 : fd_gui_store_kv_idx_node_t * kv_pool; /* shared KV index node pool (RAM) */
96 : ulong ( * kv_key_hash[ FD_GUI_STORE_MAX_RINGS ] )( void const * key ); /* RAM: per-KV-ring key hash */
97 : int ( * kv_key_cmp [ FD_GUI_STORE_MAX_RINGS ] )( void const * a, void const * b ); /* RAM: per-KV-ring key compare */
98 : ulong * freelist; /* region free list (RAM) */
99 : fd_gui_store_ring_rt_t * ring_rt; /* per-ring region ownership (RAM): ring_cnt rows */
100 : ulong * region_ids; /* per-ring region-id rings (RAM): ring_cnt rows of region_cnt ulongs */
101 : ulong * region_age; /* allocation order per physical region */
102 : ulong next_age;
103 : ulong reserved; /* sum(max(base-reg_cnt,0)) */
104 : ulong region_cnt; /* total regions in the pool (== super->region_cnt; ring divisor) */
105 : fd_gui_store_metrics_t metrics[ 1 ]; /* cumulative per-ring metrics */
106 : };
107 :
108 : /* fd_gui_store_region_ring returns `ring_idx` ring's region_id. */
109 : static inline ulong *
110 0 : fd_gui_store_region_ring( fd_gui_store_t * db, ulong ring_idx ) {
111 0 : return db->region_ids + ring_idx*db->region_cnt;
112 0 : }
113 :
114 : FD_FN_CONST ulong
115 0 : fd_gui_store_align( void ) {
116 0 : return 128UL;
117 0 : }
118 :
119 : /* fd_gui_store_ring_stride returns the align-padded slot stride.
120 : Neither kind has a store-added header. */
121 : static inline ulong
122 : fd_gui_store_ring_stride( int kind,
123 : ulong val_sz,
124 0 : ulong val_align ) {
125 0 : (void)kind;
126 0 : return fd_ulong_align_up( val_sz, fd_ulong_max( val_align, 1UL ) );
127 0 : }
128 :
129 : FD_FN_PURE ulong
130 : fd_gui_store_min_size( ulong ring_cnt,
131 0 : fd_gui_store_desc_t const * descs ) {
132 0 : if( FD_UNLIKELY( !ring_cnt || ring_cnt>FD_GUI_STORE_MAX_RINGS || !descs ) ) return 0UL;
133 0 : ulong base = 0UL;
134 0 : for( ulong i=0UL; i<ring_cnt; i++ ) base += descs[ i ].base_regions;
135 0 : return fd_ulong_align_up( sizeof(fd_gui_store_super_t), FD_GUI_STORE_PAGE_SZ )
136 0 : + base*FD_GUI_STORE_REGION_SZ;
137 0 : }
138 :
139 : static ulong
140 : fd_gui_store_file_footprint( ulong size_bytes,
141 : ulong ring_cnt,
142 : fd_gui_store_desc_t const * descs,
143 : ulong * region_sz_out,
144 0 : ulong * data_off_out ) {
145 0 : if( FD_UNLIKELY( !ring_cnt || ring_cnt>FD_GUI_STORE_MAX_RINGS || !descs ) ) return 0UL;
146 :
147 0 : ulong data_off = fd_ulong_align_up( sizeof(fd_gui_store_super_t), FD_GUI_STORE_PAGE_SZ );
148 0 : ulong region_sz = FD_GUI_STORE_REGION_SZ;
149 0 : if( FD_UNLIKELY( size_bytes<fd_gui_store_min_size( ring_cnt, descs ) ) ) return 0UL;
150 0 : ulong avail = size_bytes - data_off;
151 :
152 : /* Every ring must fit at least one slot in a region. */
153 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
154 0 : if( FD_UNLIKELY( !descs[ i ].base_regions ) ) return 0UL;
155 0 : ulong stride = fd_gui_store_ring_stride( descs[ i ].kind, descs[ i ].val_sz, descs[ i ].val_align );
156 0 : if( FD_UNLIKELY( !stride || stride>region_sz ) ) return 0UL; /* record does not fit a region */
157 0 : }
158 :
159 0 : ulong region_cnt = avail / region_sz;
160 0 : if( FD_UNLIKELY( !region_cnt ) ) return 0UL;
161 :
162 0 : if( region_sz_out ) *region_sz_out = region_sz;
163 0 : if( data_off_out ) *data_off_out = data_off;
164 0 : return region_cnt;
165 0 : }
166 :
167 : static inline ulong
168 0 : fd_gui_store_kv_idx_max( fd_gui_store_desc_t const * desc ) {
169 0 : if( desc->kind!=FD_GUI_STORE_KIND_KV ) return 0UL;
170 0 : return fd_ulong_max( desc->max_records, 1UL );
171 0 : }
172 :
173 : FD_FN_CONST ulong
174 : fd_gui_store_footprint( ulong size_bytes,
175 : ulong ring_cnt,
176 0 : fd_gui_store_desc_t const * descs ) {
177 0 : if( FD_UNLIKELY( ring_cnt>FD_GUI_STORE_MAX_RINGS ) ) return 0UL;
178 :
179 0 : ulong region_cnt = fd_gui_store_file_footprint( size_bytes, ring_cnt, descs, NULL, NULL );
180 0 : if( FD_UNLIKELY( !region_cnt ) ) return 0UL;
181 :
182 0 : ulong pool_max = 0UL;
183 0 : for( ulong i=0UL; i<ring_cnt; i++ ) pool_max += fd_gui_store_kv_idx_max( &descs[ i ] );
184 0 : pool_max = fd_ulong_max( pool_max, 1UL );
185 :
186 0 : ulong l = FD_LAYOUT_INIT;
187 0 : l = FD_LAYOUT_APPEND( l, fd_gui_store_align(), sizeof(fd_gui_store_t) );
188 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
189 0 : if( descs[ i ].kind!=FD_GUI_STORE_KIND_KV ) continue;
190 0 : ulong chain_cnt = fd_gui_store_kv_idx_chain_cnt_est( fd_gui_store_kv_idx_max( &descs[ i ] ) );
191 0 : l = FD_LAYOUT_APPEND( l, fd_gui_store_kv_idx_align(), fd_gui_store_kv_idx_footprint( chain_cnt ) );
192 0 : }
193 0 : l = FD_LAYOUT_APPEND( l, fd_gui_store_kv_pool_align(), fd_gui_store_kv_pool_footprint( pool_max ) );
194 0 : l = FD_LAYOUT_APPEND( l, fd_gui_store_freelist_align(), fd_gui_store_freelist_footprint( region_cnt ) );
195 0 : l = FD_LAYOUT_APPEND( l, alignof(fd_gui_store_ring_rt_t), fd_ulong_max( ring_cnt, 1UL )*sizeof(fd_gui_store_ring_rt_t) );
196 0 : l = FD_LAYOUT_APPEND( l, alignof(ulong), fd_ulong_max( ring_cnt, 1UL )*region_cnt*sizeof(ulong) );
197 0 : l = FD_LAYOUT_APPEND( l, alignof(ulong), region_cnt*sizeof(ulong) );
198 0 : return FD_LAYOUT_FINI( l, fd_gui_store_align() );
199 0 : }
200 :
201 : void *
202 : fd_gui_store_new( void * mem,
203 : char const * path,
204 : ulong size_bytes,
205 : ulong ring_cnt,
206 : ulong seed,
207 0 : fd_gui_store_desc_t const * descs ) {
208 :
209 0 : if( FD_UNLIKELY( !mem ) ) { FD_LOG_WARNING(( "fd_gui_store_new: null mem" )); return NULL; }
210 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_gui_store_align() ) ) ) { FD_LOG_WARNING(( "fd_gui_store_new: misaligned mem" )); return NULL; }
211 0 : if( FD_UNLIKELY( !path || !path[ 0 ] ) ) { FD_LOG_WARNING(( "fd_gui_store_new: null path" )); return NULL; }
212 0 : if( FD_UNLIKELY( !size_bytes ) ) { FD_LOG_WARNING(( "fd_gui_store_new: zero size" )); return NULL; }
213 0 : if( FD_UNLIKELY( !ring_cnt || ring_cnt>FD_GUI_STORE_MAX_RINGS ) ) { FD_LOG_WARNING(( "fd_gui_store_new: bad ring_cnt %lu", ring_cnt )); return NULL; }
214 0 : if( FD_UNLIKELY( !descs ) ) { FD_LOG_WARNING(( "fd_gui_store_new: null descs" )); return NULL; }
215 :
216 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
217 0 : if( FD_UNLIKELY( !descs[ i ].name ) ) { FD_LOG_WARNING(( "fd_gui_store_new: null descs[%lu].name", i )); return NULL; }
218 0 : if( FD_UNLIKELY( descs[ i ].kind!=FD_GUI_STORE_KIND_KV && descs[ i ].kind!=FD_GUI_STORE_KIND_TS ) ) {
219 0 : FD_LOG_WARNING(( "fd_gui_store_new: bad descs[%lu].kind %d", i, descs[ i ].kind )); return NULL;
220 0 : }
221 0 : if( FD_UNLIKELY( !descs[ i ].val_sz ) ) {
222 0 : FD_LOG_WARNING(( "fd_gui_store_new: descs[%lu] has zero val_sz", i )); return NULL;
223 0 : }
224 0 : if( FD_UNLIKELY( !descs[ i ].base_regions ) ) {
225 0 : FD_LOG_WARNING(( "fd_gui_store_new: descs[%lu] has zero base_regions", i )); return NULL;
226 0 : }
227 0 : if( FD_UNLIKELY( descs[ i ].kind==FD_GUI_STORE_KIND_KV && !descs[ i ].key_sz ) ) {
228 0 : FD_LOG_WARNING(( "fd_gui_store_new: KV descs[%lu] has zero key_sz", i )); return NULL;
229 0 : }
230 0 : if( FD_UNLIKELY( descs[ i ].kind==FD_GUI_STORE_KIND_KV && ( !descs[ i ].key_hash || !descs[ i ].key_cmp ) ) ) {
231 0 : FD_LOG_WARNING(( "fd_gui_store_new: KV descs[%lu] missing key_hash/key_cmp", i )); return NULL;
232 0 : }
233 0 : if( FD_UNLIKELY( descs[ i ].kind==FD_GUI_STORE_KIND_KV && descs[ i ].key_off+descs[ i ].key_sz>descs[ i ].val_sz ) ) {
234 0 : FD_LOG_WARNING(( "fd_gui_store_new: KV descs[%lu] key (off %lu sz %lu) exceeds val_sz %lu", i, descs[ i ].key_off, descs[ i ].key_sz, descs[ i ].val_sz )); return NULL;
235 0 : }
236 0 : }
237 :
238 0 : ulong region_sz, data_off;
239 0 : ulong region_cnt = fd_gui_store_file_footprint( size_bytes, ring_cnt, descs, ®ion_sz, &data_off );
240 0 : if( FD_UNLIKELY( !region_cnt ) ) {
241 0 : FD_LOG_WARNING(( "fd_gui_store_new: store size %lu too small for %lu rings", size_bytes, ring_cnt ));
242 0 : return NULL;
243 0 : }
244 :
245 : /* Shared KV node pool sized to the sum of per-ring max_records. */
246 0 : ulong pool_max = 0UL;
247 0 : for( ulong i=0UL; i<ring_cnt; i++ ) pool_max += fd_gui_store_kv_idx_max( &descs[ i ] );
248 0 : pool_max = fd_ulong_max( pool_max, 1UL );
249 :
250 0 : fd_memset( mem, 0, sizeof(fd_gui_store_t) );
251 0 : FD_SCRATCH_ALLOC_INIT( l, mem );
252 0 : fd_gui_store_t * db = FD_SCRATCH_ALLOC_APPEND( l, fd_gui_store_align(), sizeof(fd_gui_store_t) );
253 0 : void * kv_idx_mem[ FD_GUI_STORE_MAX_RINGS ];
254 0 : ulong kv_idx_chains[ FD_GUI_STORE_MAX_RINGS ];
255 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
256 0 : if( descs[ i ].kind!=FD_GUI_STORE_KIND_KV ) { kv_idx_mem[ i ] = NULL; kv_idx_chains[ i ] = 0UL; continue; }
257 0 : kv_idx_chains[ i ] = fd_gui_store_kv_idx_chain_cnt_est( fd_gui_store_kv_idx_max( &descs[ i ] ) );
258 0 : kv_idx_mem[ i ] = FD_SCRATCH_ALLOC_APPEND( l, fd_gui_store_kv_idx_align(), fd_gui_store_kv_idx_footprint( kv_idx_chains[ i ] ) );
259 0 : }
260 0 : void * kv_pool_mem= FD_SCRATCH_ALLOC_APPEND( l, fd_gui_store_kv_pool_align(), fd_gui_store_kv_pool_footprint( pool_max ) );
261 0 : void * freelist_mem= FD_SCRATCH_ALLOC_APPEND( l, fd_gui_store_freelist_align(), fd_gui_store_freelist_footprint( region_cnt ) );
262 0 : fd_gui_store_ring_rt_t * ring_rt_mem = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_gui_store_ring_rt_t), ring_cnt*sizeof(fd_gui_store_ring_rt_t) );
263 0 : ulong * region_ids_mem = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), ring_cnt*region_cnt*sizeof(ulong) );
264 0 : ulong * region_age_mem = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), region_cnt*sizeof(ulong) );
265 0 : FD_SCRATCH_ALLOC_FINI( l, fd_gui_store_align() );
266 :
267 0 : db->fd = -1;
268 0 : db->mapped = NULL;
269 0 : db->ring_cnt = ring_cnt;
270 0 : db->size = size_bytes;
271 0 : db->ring_rt = ring_rt_mem;
272 0 : db->region_ids = region_ids_mem;
273 0 : db->region_age = region_age_mem;
274 0 : db->reserved = 0UL;
275 0 : db->region_cnt = region_cnt;
276 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
277 0 : ring_rt_mem[ i ].reg_base = 0UL;
278 0 : ring_rt_mem[ i ].reg_cnt = 0UL;
279 0 : ring_rt_mem[ i ].max_records = fd_gui_store_kv_idx_max( &descs[ i ] );
280 0 : ring_rt_mem[ i ].base = descs[ i ].base_regions;
281 0 : db->reserved += ring_rt_mem[ i ].base;
282 0 : }
283 :
284 : /* Shared node pool + one ulong-keyed index per KV ring. */
285 0 : if( FD_UNLIKELY( !fd_gui_store_kv_pool_new( kv_pool_mem, pool_max ) ) ) { FD_LOG_WARNING(( "fd_gui_store_new: ent_pool_new failed" )); return NULL; }
286 0 : db->kv_pool = fd_gui_store_kv_pool_join( kv_pool_mem );
287 0 : if( FD_UNLIKELY( !db->kv_pool ) ) { FD_LOG_WARNING(( "fd_gui_store_new: kv_pool join failed" )); return NULL; }
288 0 : for( ulong i=0UL; i<FD_GUI_STORE_MAX_RINGS; i++ ) db->kv_idx[ i ] = NULL;
289 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
290 0 : if( !kv_idx_mem[ i ] ) continue;
291 0 : if( FD_UNLIKELY( !fd_gui_store_kv_idx_new( kv_idx_mem[ i ], kv_idx_chains[ i ], seed+i ) ) ) { FD_LOG_WARNING(( "fd_gui_store_new: kv_idx_new[%lu] failed", i )); return NULL; }
292 0 : db->kv_idx[ i ] = fd_gui_store_kv_idx_join( kv_idx_mem[ i ] );
293 0 : if( FD_UNLIKELY( !db->kv_idx[ i ] ) ) { FD_LOG_WARNING(( "fd_gui_store_new: kv_idx join[%lu] failed", i )); return NULL; }
294 0 : }
295 :
296 0 : if( FD_UNLIKELY( !fd_gui_store_freelist_new( freelist_mem, region_cnt ) ) ) { FD_LOG_WARNING(( "fd_gui_store_new: freelist_new failed" )); return NULL; }
297 0 : db->freelist = fd_gui_store_freelist_join( freelist_mem );
298 0 : if( FD_UNLIKELY( !db->freelist ) ) { FD_LOG_WARNING(( "fd_gui_store_new: freelist join failed" )); return NULL; }
299 0 : for( ulong i=region_cnt; i-->0UL; ) fd_gui_store_freelist_push( db->freelist, i );
300 :
301 : /* Wipe + (re)create the backing file. */
302 0 : ulong map_sz = data_off + region_cnt*region_sz;
303 0 : int fd = open( path, O_RDWR | O_CREAT | O_TRUNC, (mode_t)0600 );
304 0 : if( FD_UNLIKELY( fd<0 ) ) { FD_LOG_WARNING(( "fd_gui_store_new: open(%s) failed (%d-%s)", path, errno, fd_io_strerror( errno ) )); return NULL; }
305 0 : if( FD_UNLIKELY( fallocate( fd, 0, 0, (off_t)data_off ) ) ) {
306 0 : FD_LOG_WARNING(( "fd_gui_store_new: fallocate(%s, %lu) failed (%d-%s)", path, data_off, errno, fd_io_strerror( errno ) ));
307 0 : close( fd ); return NULL;
308 0 : }
309 0 : void * mapped = mmap( NULL, map_sz, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 );
310 0 : if( FD_UNLIKELY( mapped==MAP_FAILED ) ) {
311 0 : FD_LOG_WARNING(( "fd_gui_store_new: mmap(%s, %lu) failed (%d-%s)", path, map_sz, errno, fd_io_strerror( errno ) ));
312 0 : close( fd ); return NULL;
313 0 : }
314 :
315 0 : db->fd = fd;
316 0 : db->mapped = mapped;
317 0 : db->mapped_sz = map_sz;
318 0 : db->file_sz = data_off;
319 0 : db->super = (fd_gui_store_super_t *)mapped;
320 :
321 0 : fd_gui_store_super_t * super = db->super;
322 0 : fd_memset( super, 0, sizeof(fd_gui_store_super_t) );
323 0 : super->size_bytes = size_bytes;
324 0 : super->data_off = data_off;
325 0 : super->region_sz = region_sz;
326 0 : super->region_cnt = region_cnt;
327 0 : super->ring_cnt = ring_cnt;
328 :
329 0 : for( ulong i=0UL; i<ring_cnt; i++ ) {
330 0 : fd_gui_store_ring_t * p = &super->ring[ i ];
331 0 : p->stride = fd_gui_store_ring_stride( descs[ i ].kind, descs[ i ].val_sz, descs[ i ].val_align );
332 0 : p->region_capacity = region_sz / p->stride; /* >=1 by layout */
333 0 : p->key_off = descs[ i ].key_off;
334 0 : p->key_sz = descs[ i ].key_sz;
335 0 : p->val_sz = descs[ i ].val_sz;
336 0 : p->val_align = descs[ i ].val_align;
337 0 : p->ts_off = descs[ i ].ts_off;
338 0 : p->granularity = descs[ i ].granularity;
339 0 : p->kind = descs[ i ].kind;
340 0 : p->head_cur = 0UL;
341 0 : p->evict_cur = 0UL;
342 0 : p->tail_cur = 0UL;
343 0 : db->kv_key_hash[ i ] = descs[ i ].key_hash; /* NULL for TS rings */
344 0 : db->kv_key_cmp [ i ] = descs[ i ].key_cmp; /* NULL for TS rings */
345 0 : }
346 :
347 0 : FD_COMPILER_MFENCE();
348 0 : super->magic = FD_GUI_STORE_SUPER_MAGIC;
349 0 : db->magic = FD_GUI_STORE_MAGIC;
350 0 : FD_COMPILER_MFENCE();
351 :
352 0 : memset( db->metrics, 0, sizeof(fd_gui_store_metrics_t) );
353 :
354 0 : FD_LOG_INFO(( "fd_gui_store: opened %s (ceiling %lu MiB, %lu regions x %lu MiB, %lu rings)",
355 0 : path, size_bytes>>20, region_cnt, region_sz>>20, ring_cnt ));
356 0 : return mem;
357 0 : }
358 :
359 : fd_gui_store_t *
360 0 : fd_gui_store_join( void * mem ) {
361 0 : if( FD_UNLIKELY( !mem ) ) return NULL;
362 0 : fd_gui_store_t * db = (fd_gui_store_t *)mem;
363 0 : if( FD_UNLIKELY( db->magic!=FD_GUI_STORE_MAGIC ) ) { FD_LOG_WARNING(( "fd_gui_store_join: bad magic" )); return NULL; }
364 0 : return db;
365 0 : }
366 :
367 : void *
368 0 : fd_gui_store_leave( fd_gui_store_t * db ) {
369 0 : return (void *)db;
370 0 : }
371 :
372 : void *
373 0 : fd_gui_store_delete( void * mem ) {
374 0 : if( FD_UNLIKELY( !mem ) ) return NULL;
375 0 : fd_gui_store_t * db = (fd_gui_store_t *)mem;
376 0 : if( db->mapped ) munmap( db->mapped, db->mapped_sz );
377 0 : if( db->fd>=0 ) close( db->fd );
378 0 : db->mapped = NULL;
379 0 : db->fd = -1;
380 0 : db->super = NULL;
381 0 : db->magic = 0UL;
382 0 : return mem;
383 0 : }
384 :
385 : ulong
386 0 : fd_gui_store_cnt( fd_gui_store_t const * db ) {
387 0 : return db->ring_cnt;
388 0 : }
389 :
390 : static inline ulong
391 0 : fd_gui_store_committed_bytes( fd_gui_store_t const * db ) {
392 0 : ulong used = db->super->data_off;
393 0 : for( ulong i=0UL; i<db->ring_cnt; i++ ) used += db->ring_rt[ i ].reg_cnt * db->super->region_sz;
394 0 : return used;
395 0 : }
396 :
397 : ulong
398 0 : fd_gui_store_used_bytes( fd_gui_store_t * db ) {
399 0 : if( FD_UNLIKELY( !db->super ) ) return 0UL;
400 0 : return fd_gui_store_committed_bytes( db );
401 0 : }
402 :
403 : ulong
404 0 : fd_gui_store_live_bytes( fd_gui_store_t * db ) {
405 0 : if( FD_UNLIKELY( !db->super ) ) return 0UL;
406 0 : ulong live = 0UL;
407 0 : for( ulong i=0UL; i<db->ring_cnt; i++ ) {
408 0 : fd_gui_store_ring_t const * p = &db->super->ring[ i ];
409 0 : live += ( p->head_cur - p->evict_cur ) * p->stride;
410 0 : }
411 0 : return live;
412 0 : }
413 :
414 : fd_gui_store_metrics_t const *
415 0 : fd_gui_store_metrics( fd_gui_store_t const * db ) {
416 0 : return db->metrics;
417 0 : }
418 :
419 : void
420 : fd_gui_store_ring_stats( fd_gui_store_t * db,
421 : ulong ring_idx,
422 : ulong * used_bytes,
423 : ulong * cap_bytes,
424 : ulong * free_bytes,
425 : ulong * used_slots,
426 : ulong * cap_slots,
427 0 : ulong * free_slots ) {
428 0 : if( FD_LIKELY( db->super && ring_idx<db->ring_cnt ) ) {
429 0 : fd_gui_store_ring_t const * p = &db->super->ring[ ring_idx ];
430 0 : fd_gui_store_ring_rt_t const * rt = &db->ring_rt[ ring_idx ];
431 :
432 0 : ulong free_cnt = fd_gui_store_freelist_cnt( db->freelist ) - db->reserved
433 0 : + ( rt->reg_cnt<rt->base ? rt->base-rt->reg_cnt : 0UL );
434 :
435 0 : *used_slots = p->head_cur - p->tail_cur;
436 0 : *cap_slots = rt->reg_cnt * p->region_capacity;
437 0 : *free_slots = free_cnt * p->region_capacity;
438 0 : *used_bytes = *used_slots * p->stride;
439 0 : *cap_bytes = rt->reg_cnt * db->super->region_sz;
440 0 : *free_bytes = free_cnt * db->super->region_sz;
441 0 : }
442 0 : }
443 :
444 : ulong
445 0 : fd_gui_store_size( fd_gui_store_t const * db ) {
446 0 : return db->size;
447 0 : }
448 :
449 : ulong
450 0 : fd_gui_store_file_sz( fd_gui_store_t const * db ) {
451 0 : if( FD_UNLIKELY( !db ) ) return 0UL;
452 0 : return db->file_sz;
453 0 : }
454 :
455 : ulong
456 0 : fd_gui_store_free_region_cnt( fd_gui_store_t const * db ) {
457 0 : if( FD_UNLIKELY( !db->super ) ) return 0UL;
458 0 : return fd_gui_store_freelist_cnt( db->freelist );
459 0 : }
460 :
461 : ulong
462 0 : fd_gui_store_shared_free_region_cnt( fd_gui_store_t const * db ) {
463 0 : if( FD_UNLIKELY( !db->super ) ) return 0UL;
464 0 : return fd_gui_store_freelist_cnt( db->freelist ) - db->reserved;
465 0 : }
466 :
467 : int
468 0 : fd_gui_store_fd( fd_gui_store_t const * db ) {
469 0 : if( FD_UNLIKELY( !db ) ) return -1;
470 0 : return db->fd;
471 0 : }
472 :
473 : static inline ulong
474 : fd_gui_store_ring_head_limit( fd_gui_store_t const * db,
475 : ulong ring_idx,
476 0 : fd_gui_store_ring_t const * p ) {
477 0 : fd_gui_store_ring_rt_t const * rt = &db->ring_rt[ ring_idx ];
478 0 : return ( rt->reg_base + rt->reg_cnt )*p->region_capacity;
479 0 : }
480 :
481 : static int
482 0 : fd_gui_store_region_grow( fd_gui_store_t * db, ulong ring_idx ) {
483 0 : fd_gui_store_ring_rt_t * rt = &db->ring_rt[ ring_idx ];
484 0 : ulong * region_ring = fd_gui_store_region_ring( db, ring_idx );
485 0 : ulong free_cnt = fd_gui_store_freelist_cnt( db->freelist );
486 0 : if( FD_UNLIKELY( !free_cnt || (rt->reg_cnt>=rt->base && free_cnt<=db->reserved) ) ) return 0;
487 :
488 0 : ulong region_id = fd_gui_store_freelist_pop( db->freelist );
489 0 : ulong ordinal = rt->reg_base + rt->reg_cnt;
490 0 : region_ring[ ordinal % db->region_cnt ] = region_id;
491 0 : rt->reg_cnt++;
492 :
493 0 : ulong region_end = db->super->data_off + ( region_id + 1UL )*db->super->region_sz;
494 0 : if( region_end>db->file_sz ) {
495 0 : ulong grow_sz = region_end - db->file_sz;
496 0 : if( FD_UNLIKELY( fallocate( db->fd, 0, (off_t)db->file_sz, (off_t)grow_sz ) ) ) {
497 : /* roll back the claim */
498 0 : rt->reg_cnt--;
499 0 : fd_gui_store_freelist_push( db->freelist, region_id );
500 0 : FD_LOG_WARNING(( "fd_gui_store: fallocate grow to %lu failed (%d-%s)", region_end, errno, fd_io_strerror( errno ) ));
501 0 : return 0;
502 0 : }
503 0 : db->file_sz = region_end;
504 0 : }
505 : /* Claiming a base region consumes one outstanding entitlement. */
506 0 : db->reserved -= rt->reg_cnt<=rt->base;
507 0 : db->region_age[ region_id ] = db->next_age++;
508 0 : db->metrics->region_grows[ ring_idx ]++;
509 0 : return 1;
510 0 : }
511 :
512 : static void
513 : fd_gui_store_region_reclaim( fd_gui_store_t * db, ulong ring_idx,
514 0 : fd_gui_store_ring_t * p ) {
515 0 : fd_gui_store_ring_rt_t * rt = &db->ring_rt[ ring_idx ];
516 0 : ulong * region_ring = fd_gui_store_region_ring( db, ring_idx );
517 0 : ulong cap = p->region_capacity;
518 0 : while( rt->reg_cnt && p->tail_cur >= ( rt->reg_base + 1UL )*cap ) {
519 0 : ulong region_id = region_ring[ rt->reg_base % db->region_cnt ];
520 0 : fd_gui_store_freelist_push( db->freelist, region_id );
521 0 : rt->reg_base++;
522 0 : rt->reg_cnt--;
523 : /* The owner's base entitlement survives returning a region. */
524 0 : db->reserved += rt->reg_cnt<rt->base;
525 0 : db->metrics->region_reclaims[ ring_idx ]++;
526 0 : }
527 0 : }
528 :
529 : static inline void *
530 : fd_gui_store_slot( fd_gui_store_t * db,
531 : ulong ring_idx,
532 : fd_gui_store_ring_t const * p,
533 0 : ulong cur ) {
534 0 : ulong cap = p->region_capacity;
535 0 : ulong ordinal = cur / cap;
536 0 : ulong region_id = fd_gui_store_region_ring( db, ring_idx )[ ordinal % db->region_cnt ];
537 0 : ulong off = db->super->data_off + region_id*db->super->region_sz + ( cur % cap )*p->stride;
538 0 : return (uchar *)db->mapped + off;
539 0 : }
540 :
541 : static inline ulong
542 : fd_gui_store_ts_window( fd_gui_store_ring_t const * p,
543 0 : void const * val ) {
544 0 : long ts = *(long const *)( (uchar const *)val + p->ts_off );
545 0 : ulong gran = fd_ulong_max( p->granularity, 1UL );
546 0 : return (ulong)fd_long_max( ts, 0L ) / gran;
547 0 : }
548 :
549 : static inline uchar const *
550 : fd_gui_store_kv_slot_key( fd_gui_store_t * db,
551 : ulong ring_idx,
552 : fd_gui_store_ring_t const * p,
553 0 : ulong cur ) {
554 0 : return (uchar const *)fd_gui_store_slot( db, ring_idx, p, cur ) + p->key_off;
555 0 : }
556 :
557 : /* fd_gui_store_kv_node_cur returns the full cursor of node. Indexed
558 : records lie in [evict_cur,head_cur) and head_cur-evict_cur is bounded
559 : by max_records, which the uint pool index keeps below 2^32. */
560 : static inline ulong
561 : fd_gui_store_kv_node_cur( fd_gui_store_ring_t const * p,
562 0 : fd_gui_store_kv_idx_node_t const * node ) {
563 0 : return p->head_cur - (ulong)(uint)( (uint)p->head_cur - node->cur );
564 0 : }
565 :
566 : static fd_gui_store_kv_idx_node_t *
567 : fd_gui_store_kv_find_node( fd_gui_store_t * db,
568 : fd_gui_store_ring_t const * p,
569 : ulong ring_idx,
570 0 : void const * key ) {
571 0 : uint ik = (uint)db->kv_key_hash[ ring_idx ]( key );
572 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_idx_ele_query( db->kv_idx[ ring_idx ], &ik, NULL, db->kv_pool );
573 0 : while( node ) {
574 0 : fd_gui_store_kv_idx_node_t * next = (fd_gui_store_kv_idx_node_t *)fd_gui_store_kv_idx_ele_next_const( node, NULL, db->kv_pool );
575 0 : ulong cur = fd_gui_store_kv_node_cur( p, node );
576 0 : if( FD_UNLIKELY( cur<p->evict_cur ) ) {
577 : /* stale: the slot was evicted; lazily drop the dead index node */
578 0 : fd_gui_store_kv_idx_ele_remove_fast( db->kv_idx[ ring_idx ], node, db->kv_pool );
579 0 : fd_gui_store_kv_pool_ele_release( db->kv_pool, node );
580 0 : } else {
581 0 : uchar const * slot_key = fd_gui_store_kv_slot_key( db, ring_idx, p, cur );
582 0 : if( FD_LIKELY( 0==db->kv_key_cmp[ ring_idx ]( slot_key, key ) ) ) return node;
583 0 : }
584 0 : node = next;
585 0 : }
586 0 : return NULL;
587 0 : }
588 :
589 : int
590 : fd_gui_store_kv_get_or_create( fd_gui_store_t * db,
591 : ulong ring_idx,
592 : void const * key,
593 0 : void ** val_out ) {
594 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_get_or_create: bad ring_idx %lu", ring_idx )); return FD_GUI_STORE_ERR; }
595 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
596 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_KV ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_get_or_create: ring_idx %lu is not a KV ring", ring_idx )); return FD_GUI_STORE_ERR; }
597 :
598 : /* Existing key: hand back the live value region for in-place population. */
599 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_find_node( db, p, ring_idx, key );
600 0 : if( FD_LIKELY( node ) ) {
601 0 : uchar * slot = fd_gui_store_slot( db, ring_idx, p, fd_gui_store_kv_node_cur( p, node ) );
602 0 : if( val_out ) *val_out = slot;
603 0 : return FD_GUI_STORE_SUCCESS;
604 0 : }
605 :
606 0 : if( FD_UNLIKELY( p->head_cur-p->evict_cur>=db->ring_rt[ ring_idx ].max_records ) ) return FD_GUI_STORE_RING_FULL;
607 : /* Per-ring limits sum to the pool capacity: one ring cannot consume
608 : another ring's index allowance. */
609 0 : FD_TEST( fd_gui_store_kv_pool_free( db->kv_pool ) );
610 0 : if( FD_UNLIKELY( p->head_cur >= fd_gui_store_ring_head_limit( db, ring_idx, p ) ) ) {
611 0 : if( FD_UNLIKELY( !fd_gui_store_region_grow( db, ring_idx ) ) ) { db->metrics->map_full[ ring_idx ]++; return FD_GUI_STORE_MAP_FULL; }
612 0 : }
613 :
614 0 : ulong cur = p->head_cur;
615 0 : uchar * slot = fd_gui_store_slot( db, ring_idx, p, cur );
616 : /* Seed the key inside the value so the stored record always carries a
617 : consistent key; the caller fills the remaining value bytes. */
618 0 : fd_memcpy( slot + p->key_off, key, p->key_sz );
619 :
620 0 : fd_gui_store_kv_idx_node_t * n = fd_gui_store_kv_pool_ele_acquire( db->kv_pool );
621 0 : n->key = (uint)db->kv_key_hash[ ring_idx ]( key );
622 0 : n->cur = (uint)cur;
623 0 : fd_gui_store_kv_idx_ele_insert( db->kv_idx[ ring_idx ], n, db->kv_pool );
624 :
625 0 : p->head_cur = cur + 1UL;
626 0 : if( val_out ) *val_out = slot;
627 0 : return FD_GUI_STORE_SUCCESS;
628 0 : }
629 :
630 : void *
631 : fd_gui_store_kv_get( fd_gui_store_t * db,
632 : ulong ring_idx,
633 0 : void const * key ) {
634 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_get: bad ring_idx %lu", ring_idx )); return NULL; }
635 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
636 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_KV ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_get: ring_idx %lu is not a KV ring", ring_idx )); return NULL; }
637 :
638 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_find_node( db, p, ring_idx, key );
639 0 : db->metrics->kv_lookups[ ring_idx ]++;
640 0 : if( FD_UNLIKELY( !node ) ) return NULL;
641 0 : return (uchar *)fd_gui_store_slot( db, ring_idx, p, fd_gui_store_kv_node_cur( p, node ) );
642 0 : }
643 :
644 : static uchar const *
645 : fd_gui_store_kv_lowest_gt( fd_gui_store_t * db,
646 : ulong ring_idx,
647 : fd_gui_store_ring_t const * p,
648 : void const * key,
649 0 : uchar const * gt ) {
650 0 : int ( * key_cmp )( void const *, void const * ) = db->kv_key_cmp[ ring_idx ];
651 0 : uchar const * best = NULL;
652 0 : uchar const * best_key = NULL;
653 :
654 0 : if( FD_LIKELY( key ) ) {
655 : /* Fast path: walk the query key's index bucket (records sharing its
656 : hashed leading field), tracking the lowest full key still > gt that
657 : matches `key`. */
658 0 : uint ik = (uint)db->kv_key_hash[ ring_idx ]( key );
659 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_idx_ele_query( db->kv_idx[ ring_idx ], &ik, NULL, db->kv_pool );
660 0 : while( node ) {
661 0 : fd_gui_store_kv_idx_node_t * next = (fd_gui_store_kv_idx_node_t *)fd_gui_store_kv_idx_ele_next_const( node, NULL, db->kv_pool );
662 0 : ulong cur = fd_gui_store_kv_node_cur( p, node );
663 0 : if( FD_UNLIKELY( cur<p->evict_cur ) ) {
664 0 : fd_gui_store_kv_idx_ele_remove_fast( db->kv_idx[ ring_idx ], node, db->kv_pool );
665 0 : fd_gui_store_kv_pool_ele_release( db->kv_pool, node );
666 0 : } else {
667 0 : uchar const * val = (uchar const *)fd_gui_store_slot( db, ring_idx, p, cur );
668 0 : uchar const * k = val + p->key_off;
669 0 : if( FD_LIKELY( 0==key_cmp( k, key ) ) ) {
670 0 : if( ( !gt || key_cmp( k, gt )>0 ) &&
671 0 : ( !best || key_cmp( k, best_key )<0 ) ) { best = val; best_key = k; }
672 0 : }
673 0 : }
674 0 : node = next;
675 0 : }
676 0 : } else {
677 : /* Slow path: no query key, find the lowest key across the ring. */
678 0 : for( ulong cur=p->evict_cur; cur<p->head_cur; cur++ ) {
679 0 : uchar const * val = (uchar const *)fd_gui_store_slot( db, ring_idx, p, cur );
680 0 : uchar const * k = val + p->key_off;
681 0 : if( ( !gt || key_cmp( k, gt )>0 ) &&
682 0 : ( !best || key_cmp( k, best_key )<0 ) ) { best = val; best_key = k; }
683 0 : }
684 0 : }
685 0 : return best;
686 0 : }
687 :
688 : void *
689 : fd_gui_store_kv_get_any( fd_gui_store_t * db,
690 : ulong ring_idx,
691 0 : void const * key ) {
692 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_get_any: bad ring_idx %lu", ring_idx )); return NULL; }
693 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
694 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_KV ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_get_any: ring_idx %lu is not a KV ring", ring_idx )); return NULL; }
695 :
696 0 : db->metrics->kv_lookups[ ring_idx ]++;
697 0 : return (void *)fd_gui_store_kv_lowest_gt( db, ring_idx, p, key, NULL );
698 0 : }
699 :
700 : fd_gui_store_kv_iter_t *
701 : fd_gui_store_kv_iter_begin( fd_gui_store_t * db,
702 : fd_gui_store_kv_iter_t * iter,
703 : ulong ring_idx,
704 0 : void const * key ) {
705 0 : memset( iter, 0, sizeof(fd_gui_store_kv_iter_t) );
706 0 : iter->_db = db;
707 :
708 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_iter_begin: bad ring_idx %lu", ring_idx )); return iter; }
709 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
710 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_KV ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_iter_begin: ring_idx %lu is not a KV ring", ring_idx )); return iter; }
711 0 : if( FD_UNLIKELY( !key || p->key_sz>sizeof(iter->_key) ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_iter_begin: null key or key_sz %lu too large", p->key_sz )); return iter; }
712 :
713 0 : iter->_ring_idx = ring_idx;
714 0 : fd_memcpy( iter->_key, key, p->key_sz );
715 :
716 0 : db->metrics->kv_lookups[ ring_idx ]++;
717 0 : uchar const * best = fd_gui_store_kv_lowest_gt( db, ring_idx, p, iter->_key, NULL );
718 0 : if( FD_UNLIKELY( !best ) ) return iter; /* empty: _valid stays 0 */
719 :
720 0 : fd_memcpy( iter->_prev_key, best + p->key_off, p->key_sz );
721 0 : iter->_have_prev = 1;
722 0 : iter->_valid = 1;
723 0 : iter->rec = best;
724 0 : iter->key = best + p->key_off;
725 0 : iter->key_sz = p->key_sz;
726 0 : iter->val_sz = p->val_sz;
727 0 : return iter;
728 0 : }
729 :
730 : int
731 0 : fd_gui_store_kv_iter_next( fd_gui_store_kv_iter_t * iter ) {
732 0 : if( FD_UNLIKELY( !iter->_valid ) ) return 0;
733 0 : fd_gui_store_t * db = (fd_gui_store_t *)iter->_db;
734 0 : fd_gui_store_ring_t * p = &db->super->ring[ iter->_ring_idx ];
735 :
736 0 : uchar const * best = fd_gui_store_kv_lowest_gt( db, iter->_ring_idx, p,
737 0 : iter->_key,
738 0 : iter->_have_prev ? iter->_prev_key : NULL );
739 0 : if( FD_UNLIKELY( !best ) ) {
740 0 : iter->_valid = 0;
741 0 : iter->rec = NULL;
742 0 : iter->key = NULL;
743 0 : return 0;
744 0 : }
745 :
746 0 : fd_memcpy( iter->_prev_key, best + p->key_off, p->key_sz );
747 0 : iter->rec = best;
748 0 : iter->key = best + p->key_off;
749 0 : return 1;
750 0 : }
751 :
752 : void
753 : fd_gui_store_kv_scan_begin( fd_gui_store_t * db,
754 : fd_gui_store_kv_scan_t * iter,
755 0 : ulong ring_idx ) {
756 0 : memset( iter, 0, sizeof(*iter) );
757 0 : if( FD_UNLIKELY( !db || ring_idx>=db->ring_cnt || db->super->ring[ ring_idx ].kind!=FD_GUI_STORE_KIND_KV ) ) return;
758 0 : iter->db = db;
759 0 : iter->ring_idx = ring_idx;
760 0 : iter->cur = db->super->ring[ ring_idx ].evict_cur;
761 0 : iter->end = db->super->ring[ ring_idx ].head_cur;
762 0 : iter->append_capacity = fd_gui_store_ring_head_limit( db, ring_idx, &db->super->ring[ ring_idx ] ) - iter->end;
763 0 : }
764 :
765 : int
766 0 : fd_gui_store_kv_scan_next( fd_gui_store_kv_scan_t * iter ) {
767 0 : iter->rec = NULL;
768 0 : if( FD_UNLIKELY( !iter->db ) ) return 0;
769 0 : fd_gui_store_ring_t const * p = &iter->db->super->ring[ iter->ring_idx ];
770 0 : iter->cur = fd_ulong_max( iter->cur, p->evict_cur );
771 0 : if( iter->cur>=iter->end ) return 0;
772 0 : iter->rec = fd_gui_store_slot( iter->db, iter->ring_idx, p, iter->cur++ );
773 0 : return 1;
774 0 : }
775 :
776 : void
777 : fd_gui_store_kv_scan_seek( fd_gui_store_kv_scan_t * iter,
778 : int (*below_cb)( void const *, void * ),
779 0 : void * ctx ) {
780 0 : if( FD_UNLIKELY( !iter->db ) ) return;
781 0 : fd_gui_store_ring_t const * p = &iter->db->super->ring[ iter->ring_idx ];
782 0 : ulong lo = fd_ulong_max( iter->cur, p->evict_cur );
783 0 : ulong hi = fd_ulong_max( lo, iter->end );
784 0 : while( lo<hi ) {
785 0 : ulong mid = lo + (hi-lo)/2UL;
786 0 : if( below_cb( fd_gui_store_slot( iter->db, iter->ring_idx, p, mid ), ctx ) ) lo = mid + 1UL;
787 0 : else hi = mid;
788 0 : }
789 0 : iter->cur = lo;
790 0 : }
791 :
792 : ulong
793 : fd_gui_store_kv_reclaim_prefix( fd_gui_store_t * db,
794 : ulong ring_idx,
795 : ulong budget,
796 : int (*eligible_cb)( void const *, void * ),
797 0 : void * ctx ) {
798 0 : if( FD_UNLIKELY( !db || ring_idx>=db->ring_cnt ) ) return 0UL;
799 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
800 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_KV ) ) return 0UL;
801 0 : ulong first = p->evict_cur;
802 0 : while( budget && p->evict_cur<p->head_cur ) {
803 0 : uchar const * rec = fd_gui_store_slot( db, ring_idx, p, p->evict_cur );
804 0 : if( eligible_cb && !eligible_cb( rec, ctx ) ) break;
805 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_find_node( db, p, ring_idx, rec+p->key_off );
806 0 : FD_TEST( node );
807 0 : fd_gui_store_kv_idx_ele_remove_fast( db->kv_idx[ ring_idx ], node, db->kv_pool );
808 0 : fd_gui_store_kv_pool_ele_release( db->kv_pool, node );
809 0 : p->evict_cur++;
810 0 : budget--;
811 0 : }
812 0 : ulong count = p->evict_cur - first;
813 0 : if( count ) db->metrics->evicts[ ring_idx ]++;
814 0 : db->metrics->evict_records[ ring_idx ] += count;
815 0 : p->tail_cur = p->evict_cur;
816 0 : fd_gui_store_region_reclaim( db, ring_idx, p );
817 0 : return count;
818 0 : }
819 :
820 : int
821 : fd_gui_store_kv_evict( fd_gui_store_t * db,
822 : ulong ring_idx,
823 : void const * hi_key,
824 : ulong * budget,
825 0 : int * drained ) {
826 0 : *drained = 1;
827 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_evict: bad ring_idx %lu", ring_idx )); return FD_GUI_STORE_ERR; }
828 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
829 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_KV ) ) { FD_LOG_WARNING(( "fd_gui_store_kv_evict: ring_idx %lu is not a KV ring", ring_idx )); return FD_GUI_STORE_ERR; }
830 :
831 0 : ulong evict_cur0 = p->evict_cur;
832 :
833 0 : while( p->evict_cur<p->head_cur ) {
834 0 : uchar const * slot = (uchar const *)fd_gui_store_slot( db, ring_idx, p, p->evict_cur );
835 0 : uchar const * k = slot + p->key_off;
836 :
837 : /* Reached the boundary key. Inserts are not ordered, so we may miss
838 : some entires after this within the eviction range. They will get
839 : caught in a subsequent eviction. Replay slots are inserted in
840 : roughly sorted order so this is acceptable. */
841 0 : if( db->kv_key_cmp[ ring_idx ]( k, hi_key )>=0 ) break;
842 0 : if( !*budget ) { *drained = 0; break; }
843 :
844 : /* Free the index node backing this record */
845 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_find_node( db, p, ring_idx, k );
846 0 : if( FD_LIKELY( node ) ) {
847 0 : fd_gui_store_kv_idx_ele_remove_fast( db->kv_idx[ ring_idx ], node, db->kv_pool );
848 0 : fd_gui_store_kv_pool_ele_release( db->kv_pool, node );
849 0 : }
850 :
851 0 : p->evict_cur++;
852 0 : (*budget)--;
853 0 : db->metrics->evict_records[ ring_idx ]++;
854 0 : }
855 :
856 0 : if( p->evict_cur!=evict_cur0 ) db->metrics->evicts[ ring_idx ]++;
857 :
858 0 : p->tail_cur = p->evict_cur; /* clean prefix: reclaim chases the watermark */
859 0 : fd_gui_store_region_reclaim( db, ring_idx, p );
860 0 : return FD_GUI_STORE_SUCCESS;
861 0 : }
862 :
863 : int
864 : fd_gui_store_ts_emplace( fd_gui_store_t * db,
865 : ulong ring_idx,
866 : long ts,
867 0 : void ** val_out ) {
868 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_emplace: bad ring_idx %lu", ring_idx )); return FD_GUI_STORE_ERR; }
869 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
870 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_TS ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_emplace: ring_idx %lu is not a TS ring", ring_idx )); return FD_GUI_STORE_ERR; }
871 :
872 : /* Scans binary search for their first record, so live records must
873 : be in nondecreasing timestamp order. */
874 0 : if( FD_LIKELY( p->evict_cur<p->head_cur ) ) {
875 0 : long last_ts = *(long const *)( (uchar const *)fd_gui_store_slot( db, ring_idx, p, p->head_cur-1UL ) + p->ts_off );
876 0 : if( FD_UNLIKELY( ts<last_ts ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_emplace: ring_idx %lu timestamp decreased from %ld to %ld", ring_idx, last_ts, ts )); return FD_GUI_STORE_ERR; }
877 0 : }
878 :
879 0 : if( FD_UNLIKELY( p->head_cur >= fd_gui_store_ring_head_limit( db, ring_idx, p ) ) ) {
880 0 : if( FD_UNLIKELY( !fd_gui_store_region_grow( db, ring_idx ) ) ) { db->metrics->map_full[ ring_idx ]++; return FD_GUI_STORE_MAP_FULL; }
881 0 : }
882 :
883 : /* Window is derived from the timestamp embedded in the value; the
884 : value is stored verbatim with no store-added header. Seed the
885 : timestamp so the stored record is consistent with its window. */
886 0 : ulong cur = p->head_cur;
887 0 : uchar * slot = fd_gui_store_slot( db, ring_idx, p, cur );
888 0 : fd_memcpy( slot + p->ts_off, &ts, sizeof(ts) );
889 0 : p->head_cur = cur + 1UL;
890 0 : db->metrics->ts_appends[ ring_idx ]++;
891 0 : *val_out = slot;
892 0 : return FD_GUI_STORE_SUCCESS;
893 0 : }
894 :
895 : int
896 : fd_gui_store_ts_append( fd_gui_store_t * db,
897 : ulong ring_idx,
898 0 : void const * val ) {
899 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_append: bad ring_idx %lu", ring_idx )); return FD_GUI_STORE_ERR; }
900 0 : fd_gui_store_ring_t const * p = &db->super->ring[ ring_idx ];
901 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_TS ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_append: ring_idx %lu is not a TS ring", ring_idx )); return FD_GUI_STORE_ERR; }
902 0 : long ts;
903 0 : fd_memcpy( &ts, (uchar const *)val + p->ts_off, sizeof(ts) );
904 0 : void * slot = NULL;
905 0 : int rc = fd_gui_store_ts_emplace( db, ring_idx, ts, &slot );
906 0 : if( FD_LIKELY( rc==FD_GUI_STORE_SUCCESS ) ) fd_memcpy( slot, val, p->val_sz );
907 0 : return rc;
908 0 : }
909 :
910 : int
911 : fd_gui_store_ts_live_timestamp_bounds( fd_gui_store_t * db,
912 : ulong ring_idx,
913 : long * out_first_timestamp,
914 0 : long * out_last_timestamp ) {
915 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) return 0;
916 0 : fd_gui_store_ring_t const * p = &db->super->ring[ ring_idx ];
917 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_TS ) ) return 0;
918 0 : if( FD_UNLIKELY( p->evict_cur>=p->head_cur ) ) return 0; /* empty */
919 :
920 0 : uchar const * first = (uchar const *)fd_gui_store_slot( db, ring_idx, p, p->evict_cur );
921 0 : uchar const * last = (uchar const *)fd_gui_store_slot( db, ring_idx, p, p->head_cur-1UL );
922 0 : *out_first_timestamp = *(long const *)( first + p->ts_off );
923 0 : *out_last_timestamp = *(long const *)( last + p->ts_off );
924 0 : return 1;
925 0 : }
926 :
927 : /* fd_gui_store_ts_lower_bound returns the lowest live cursor whose
928 : record window is >= window, or head_cur if there is none. */
929 :
930 : static ulong
931 : fd_gui_store_ts_lower_bound( fd_gui_store_t * db,
932 : ulong ring_idx,
933 0 : ulong window ) {
934 0 : fd_gui_store_ring_t const * p = &db->super->ring[ ring_idx ];
935 0 : ulong lo = p->evict_cur;
936 0 : ulong hi = p->head_cur;
937 0 : while( lo<hi ) {
938 0 : ulong mid = lo + (hi-lo)/2UL;
939 0 : if( fd_gui_store_ts_window( p, fd_gui_store_slot( db, ring_idx, p, mid ) )<window ) lo = mid + 1UL;
940 0 : else hi = mid;
941 0 : }
942 0 : return lo;
943 0 : }
944 :
945 : static void
946 0 : fd_gui_store_ts_scan_advance( fd_gui_store_ts_iter_t * iter ) {
947 0 : fd_gui_store_t * db = (fd_gui_store_t *)iter->_db;
948 0 : ulong ring_idx = iter->_rec_sz - 1UL;
949 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
950 :
951 0 : ulong cur = fd_ulong_max( (ulong)iter->_cur, p->evict_cur );
952 0 : for( ; cur<iter->_cur_hi; cur++ ) {
953 0 : uchar const * slot = (uchar const *)fd_gui_store_slot( db, ring_idx, p, cur );
954 0 : ulong window = fd_gui_store_ts_window( p, slot );
955 0 : if( window>iter->_window_hi ) { cur = iter->_cur_hi; break; } /* sorted: nothing further is in range */
956 0 : if( iter->_filter && !iter->_filter( slot, iter->_filter_ctx ) ) continue;
957 0 : iter->_valid = 1;
958 0 : iter->window = window;
959 0 : iter->rec = (void *)slot;
960 0 : iter->_cur = (void *)( cur + 1UL ); /* resume past this record */
961 0 : db->metrics->ts_read_records[ ring_idx ]++;
962 0 : return;
963 0 : }
964 0 : iter->_valid = 0;
965 0 : iter->rec = NULL;
966 0 : iter->_cur = (void *)cur;
967 0 : }
968 :
969 : fd_gui_store_ts_iter_t *
970 : fd_gui_store_ts_scan_begin( fd_gui_store_t * db,
971 : fd_gui_store_ts_iter_t * iter,
972 : ulong ring_idx,
973 : ulong window_lo,
974 : ulong window_hi,
975 : fd_gui_store_ts_filter_fn filter,
976 0 : void * filter_ctx ) {
977 0 : memset( iter, 0, sizeof(fd_gui_store_ts_iter_t) );
978 0 : iter->_filter = filter;
979 0 : iter->_filter_ctx = filter_ctx;
980 :
981 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_scan_begin: bad ring_idx %lu", ring_idx )); return iter; }
982 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
983 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_TS ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_scan_begin: ring_idx %lu is not a TS ring", ring_idx )); return iter; }
984 :
985 0 : iter->_db = (void *)db;
986 0 : iter->_rec_sz = ring_idx + 1UL; /* ring_idx, biased so 0 means uninitialised */
987 0 : db->metrics->ts_reads[ ring_idx ]++;
988 :
989 0 : ulong lo_cur = window_lo<=window_hi ? fd_gui_store_ts_lower_bound( db, ring_idx, window_lo ) : p->head_cur;
990 0 : iter->_window_hi = window_hi;
991 0 : iter->_cur = (void *)lo_cur;
992 0 : iter->_cur_hi = p->head_cur;
993 0 : fd_gui_store_ts_scan_advance( iter );
994 0 : return iter;
995 0 : }
996 :
997 : int
998 0 : fd_gui_store_ts_scan_next( fd_gui_store_ts_iter_t * iter ) {
999 0 : if( FD_UNLIKELY( !iter->_valid ) ) return 0;
1000 0 : fd_gui_store_ts_scan_advance( iter );
1001 0 : return iter->_valid;
1002 0 : }
1003 :
1004 : void
1005 0 : fd_gui_store_ts_scan_end( fd_gui_store_ts_iter_t * iter ) {
1006 0 : iter->_valid = 0;
1007 0 : iter->rec = NULL;
1008 0 : iter->_db = NULL;
1009 0 : }
1010 :
1011 : int
1012 : fd_gui_store_ts_evict( fd_gui_store_t * db,
1013 : ulong ring_idx,
1014 : ulong hi_window,
1015 : ulong * budget,
1016 0 : int * drained ) {
1017 0 : *drained = 1;
1018 0 : if( FD_UNLIKELY( ring_idx>=db->ring_cnt ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_evict: bad ring_idx %lu", ring_idx )); return FD_GUI_STORE_ERR; }
1019 0 : fd_gui_store_ring_t * p = &db->super->ring[ ring_idx ];
1020 0 : if( FD_UNLIKELY( p->kind!=FD_GUI_STORE_KIND_TS ) ) { FD_LOG_WARNING(( "fd_gui_store_ts_evict: ring_idx %lu is not a TS ring", ring_idx )); return FD_GUI_STORE_ERR; }
1021 :
1022 0 : ulong evict_cur0 = p->evict_cur;
1023 :
1024 0 : while( p->evict_cur<p->head_cur ) {
1025 0 : uchar const * slot = (uchar const *)fd_gui_store_slot( db, ring_idx, p, p->evict_cur );
1026 0 : ulong window = fd_gui_store_ts_window( p, slot );
1027 :
1028 : /* reached the watermark window. We may miss some entries in-window
1029 : above this, they will get reclaimed in a subsequent eviction. */
1030 0 : if( window>=hi_window ) break;
1031 0 : if( !*budget ) { *drained = 0; break; }
1032 0 : p->evict_cur++;
1033 0 : (*budget)--;
1034 0 : db->metrics->evict_records[ ring_idx ]++;
1035 0 : }
1036 :
1037 0 : if( p->evict_cur!=evict_cur0 ) db->metrics->evicts[ ring_idx ]++;
1038 :
1039 0 : p->tail_cur = p->evict_cur;
1040 0 : fd_gui_store_region_reclaim( db, ring_idx, p );
1041 0 : return FD_GUI_STORE_SUCCESS;
1042 0 : }
1043 :
1044 : ulong
1045 : fd_gui_store_reclaim( fd_gui_store_t * db,
1046 : ulong ring_idx,
1047 : ulong budget,
1048 : int (*eligible_cb)( ulong, void const *, void * ),
1049 0 : void * ctx ) {
1050 0 : if( FD_UNLIKELY( !db || !budget || (ring_idx!=ULONG_MAX && ring_idx>=db->ring_cnt) ) ) return 0UL;
1051 0 : ulong best = ULONG_MAX;
1052 0 : ulong age = ULONG_MAX;
1053 0 : for( ulong i=0UL; i<db->ring_cnt; i++ ) {
1054 0 : fd_gui_store_ring_rt_t const * rt = &db->ring_rt[ i ];
1055 0 : fd_gui_store_ring_t const * p = &db->super->ring[ i ];
1056 0 : if( ring_idx==ULONG_MAX ? rt->reg_cnt<=rt->base : i!=ring_idx ) continue;
1057 0 : if( p->evict_cur==p->head_cur ) continue;
1058 0 : void const * rec = fd_gui_store_slot( db, i, p, p->evict_cur );
1059 0 : if( eligible_cb && !eligible_cb( i, rec, ctx ) ) continue;
1060 0 : ulong id = fd_gui_store_region_ring( db, i )[ rt->reg_base % db->region_cnt ];
1061 0 : if( db->region_age[ id ]<age ) { best = i; age = db->region_age[ id ]; }
1062 0 : }
1063 0 : if( best==ULONG_MAX ) return 0UL;
1064 :
1065 0 : fd_gui_store_ring_t * p = &db->super->ring[ best ];
1066 : /* Do not cross into the next region: after releasing an excess region
1067 : that next region can become part of the protected base. */
1068 0 : ulong stop = fd_ulong_min( p->head_cur, (db->ring_rt[ best ].reg_base+1UL)*p->region_capacity );
1069 0 : ulong first = p->evict_cur;
1070 0 : while( budget && p->evict_cur<stop ) {
1071 0 : uchar const * rec = fd_gui_store_slot( db, best, p, p->evict_cur );
1072 0 : if( eligible_cb && !eligible_cb( best, rec, ctx ) ) break;
1073 0 : if( p->kind==FD_GUI_STORE_KIND_KV ) {
1074 0 : fd_gui_store_kv_idx_node_t * node = fd_gui_store_kv_find_node( db, p, best, rec+p->key_off );
1075 0 : FD_TEST( node );
1076 0 : fd_gui_store_kv_idx_ele_remove_fast( db->kv_idx[ best ], node, db->kv_pool );
1077 0 : fd_gui_store_kv_pool_ele_release( db->kv_pool, node );
1078 0 : }
1079 0 : p->evict_cur++;
1080 0 : budget--;
1081 0 : }
1082 0 : ulong count = p->evict_cur-first;
1083 0 : db->metrics->evicts[ best ] += !!count;
1084 0 : db->metrics->evict_records[ best ] += count;
1085 0 : p->tail_cur = p->evict_cur;
1086 0 : fd_gui_store_region_reclaim( db, best, p );
1087 0 : return count;
1088 0 : }
|
