Line data Source code
1 : #ifndef HEADER_fd_src_disco_gui_fd_gui_store_h
2 : #define HEADER_fd_src_disco_gui_fd_gui_store_h
3 :
4 : /* fd_gui_store is the GUI's historical event *backend*: a single mmap'd
5 : file carved into fixed-size regions that the rings claim and release
6 : on demand (so each ring grows and shrinks dynamically), plus
7 : in-memory indices.
8 :
9 : The store hosts a fixed set of named rings. Each ring is one of two
10 : *kinds*:
11 :
12 : - KEY-VALUE (KV) rings are a generic point store: a record is
13 : uniquely identified by a caller-supplied key and there is exactly
14 : one record per key.
15 :
16 : - TIME-SERIES (TS) rings are an append-only stream of fixed-size
17 : records. Each record carries its own timestamp. The store
18 : derives the record's `window` (an integer time bucket) from it.
19 : Readers query records by a time range scan. Appends must be in
20 : nondecreasing timestamp order.
21 :
22 : ---- ring-buffer backend --------------------------------------------
23 :
24 : fd_gui_store is one mmap'd file plus in-memory indices. The file is
25 : a superblock page followed by a pool of uniform REGION_SZ regions;
26 : regions are claimed/released on demand from a shared LIFO free list
27 : (so a given ring has composite regions that are generally
28 : discontiguous) and the file is allocated up to the highest claimed
29 : region with fallocate as needed, never exceeding size_bytes. Region
30 : ownership and the free list are in-memory; only the superblock
31 : persists.
32 :
33 : file offset 0 data_off
34 : +----------------------------+--------+--------+--------+- -+--------+
35 : | superblock | region | region | region |... | region |
36 : | magic,size,ring[MAX_RINGS] | 0 | 1 | 2 | | cnt-1 |
37 : +----------------------------+--------+--------+--------+- -+--------+
38 : |<-- data_off (page 0..N) -->|<---------- REGION_SZ each ------------>|
39 : (allocated to highest claimed region)
40 :
41 : ---- rings ----------------------------------------------------------
42 :
43 : Both storage shapes are ring buffers addressed by generation cursors
44 : (monotonically increasing). Cursors stay contiguous per ring even
45 : though the regions backing them are physically scattered: cursor
46 : `cur` lives in the (cur/region_capacity)-th region the ring owns, at
47 : slot (cur%region_capacity).
48 :
49 : Each ring keeps an ordered region_ids ring mapping region_idx to
50 : region_id.
51 :
52 : cursor: 0 1 2 | 3 4 5 | 6 7 8
53 : +---+---+---+---+---+---+---+---+---+
54 : slot in region: | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | (cur % region_capacity)
55 : +---+---+---+---+---+---+---+---+---+
56 : logical ord: \___ 0 __/ \___ 1 __/ \___ 2 __/ (cur / region_capacity)
57 : | | |
58 : region_ids[ord]: phys 5 phys 2 phys 9 (physically scattered)
59 :
60 : ---- cursor watermarks ----------------------------------------------
61 :
62 : Three monotonic watermarks (tail_cur <= evict_cur <= head_cur) divide
63 : a ring's cursor line. tail_cur is a physical watermark used by the
64 : eviction policy to free space in the ring. evict_cur is a logical
65 : watermark used by readers to skip entries marked for eviction.
66 :
67 : cursor ---> (older, smaller) (newer, larger)
68 : .................|===============|########################|- - - - - -
69 : reclaimed slots | evicted slots | live records | unwritten
70 : (regions freed) | (below wmark) | (>= evict_cur, alive) | (future)
71 : ^ ^ ^
72 : tail_cur evict_cur head_cur
73 :
74 : KV records do not store the key separately: the key is a
75 : caller-declared sub-field of the value (val + key_off, key_sz bytes),
76 : so a lookup reads and compares it in place via the ring's
77 : key_cmp/key_hash callbacks. */
78 :
79 : #include "../../util/fd_util_base.h"
80 :
81 : struct fd_gui_store_private;
82 : typedef struct fd_gui_store_private fd_gui_store_t;
83 :
84 6702924 : #define FD_GUI_STORE_SUCCESS ( 0)
85 9 : #define FD_GUI_STORE_ERR (-1)
86 983826 : #define FD_GUI_STORE_MAP_FULL ( 1)
87 117 : #define FD_GUI_STORE_RING_FULL ( 2) /* this KV ring's index budget is full */
88 :
89 11637 : #define FD_GUI_STORE_KIND_KV (0)
90 1566 : #define FD_GUI_STORE_KIND_TS (1)
91 :
92 : /* FD_GUI_STORE_REGION_SZ is the fixed size of every region in the pool.
93 : No ring's record stride may exceed it (fd_gui_store_new fails fast
94 : otherwise). The store prepends no per-record header (both kinds embed
95 : their metadata in the value), so FD_GUI_STORE_MAX_REC_SZ is the whole
96 : region size. Callers that know their record types at compile time
97 : should static-assert sizeof(their largest record) <=
98 : FD_GUI_STORE_MAX_REC_SZ. */
99 3948 : #define FD_GUI_STORE_REGION_SZ (40UL<<20)
100 : #define FD_GUI_STORE_MAX_REC_SZ (FD_GUI_STORE_REGION_SZ)
101 :
102 : /* Each ring has a protected rolling base of desc->base_regions (>=1)
103 : regions. Unclaimed base regions are
104 : reserved lazily; other rings can neither allocate them nor pressure-
105 : evict records in the ring's newest base regions. A writer may recycle
106 : its own oldest eligible records when shared capacity is exhausted. */
107 :
108 : /* FD_GUI_STORE_MAX_RINGS is the maximum number of named rings a store
109 : can host. It bounds the per-ring metrics arrays below. */
110 8190 : #define FD_GUI_STORE_MAX_RINGS (64UL)
111 :
112 : struct fd_gui_store_desc {
113 : char const * name; /* the name of the ring. Must be non-NULL and unique within the store */
114 : int kind; /* FD_GUI_STORE_KIND_KV or FD_GUI_STORE_KIND_TS */
115 : ulong key_off; /* byte offset, within the value, of the record's key (pass 0 for TS) */
116 : ulong key_sz; /* key size in bytes */
117 : ulong ( * key_hash )( void const * key ); /* hashes a key to a ulong (pass NULL for TS) */
118 : int ( * key_cmp )( void const * a, void const * b ); /* full-key total order; may treat sentinels as wildcards for get_any/iter (pass NULL for TS) */
119 : ulong val_sz; /* record size in bytes */
120 : ulong val_align; /* record alignment (power of two, >=1; pass 1 for none) */
121 : ulong ts_off; /* byte offset, within the value, of the record's `long` timestamp (TS only; pass 0 for KV) */
122 : ulong granularity; /* TS window divisor: window = (ulong)(*(long*)(val+ts_off)) / granularity (pass 0 for KV) */
123 : ulong max_records; /* enforced KV index budget (0 means 1; ignored for TS) */
124 : ulong base_regions; /* protected base in regions, >=1 */
125 : };
126 :
127 : typedef struct fd_gui_store_desc fd_gui_store_desc_t;
128 :
129 : FD_PROTOTYPES_BEGIN
130 :
131 : FD_FN_CONST ulong
132 : fd_gui_store_align( void );
133 :
134 : FD_FN_CONST ulong
135 : fd_gui_store_footprint( ulong size_bytes,
136 : ulong ring_cnt,
137 : fd_gui_store_desc_t const * descs );
138 :
139 : /* fd_gui_store_new formats the workspace region `mem` and opens the
140 : backing store whose data file is `path`, with a size ceiling of
141 : `size_bytes`. The parent directory of `path` must already exist.
142 : `ring_cnt` named rings are created, one per entry of `descs`. The
143 : `seed+i` initializes KV ring `i`'s index. The store is wiped on open.
144 :
145 : Returns `mem` on success, or NULL on failure (logged at WARNING). */
146 :
147 : void *
148 : fd_gui_store_new( void * mem,
149 : char const * path,
150 : ulong size_bytes,
151 : ulong ring_cnt,
152 : ulong seed,
153 : fd_gui_store_desc_t const * descs );
154 :
155 : fd_gui_store_t *
156 : fd_gui_store_join( void * mem );
157 :
158 : void *
159 : fd_gui_store_leave( fd_gui_store_t * db );
160 :
161 : void *
162 : fd_gui_store_delete( void * mem );
163 :
164 : /* fd_gui_store_cnt returns the number of named rings in the store. */
165 :
166 : ulong
167 : fd_gui_store_cnt( fd_gui_store_t const * db );
168 :
169 : /* ---- space accounting ------------------------------------------------- */
170 :
171 : ulong
172 : fd_gui_store_used_bytes( fd_gui_store_t * db );
173 :
174 : ulong
175 : fd_gui_store_live_bytes( fd_gui_store_t * db );
176 :
177 : ulong
178 : fd_gui_store_size( fd_gui_store_t const * db );
179 :
180 : /* fd_gui_store_file_sz returns the logical allocated length of the
181 : backing file. */
182 :
183 : ulong
184 : fd_gui_store_file_sz( fd_gui_store_t const * db );
185 :
186 : /* fd_gui_store_free_region_cnt returns the number of regions currently
187 : unclaimed on disk. */
188 :
189 : ulong
190 : fd_gui_store_free_region_cnt( fd_gui_store_t const * db );
191 :
192 : /* fd_gui_store_shared_free_region_cnt returns the unclaimed regions
193 : available excluding the base region allocation. */
194 : ulong
195 : fd_gui_store_shared_free_region_cnt( fd_gui_store_t const * db );
196 :
197 : /* fd_gui_store_min_size returns the minimum file size ceiling for
198 : ring_cnt rings described by descs: the superblock plus every ring's
199 : base regions. Zero for an invalid ring count or NULL descs.
200 : new/footprint reject smaller stores before opening a file. */
201 : FD_FN_PURE ulong
202 : fd_gui_store_min_size( ulong ring_cnt,
203 : fd_gui_store_desc_t const * descs );
204 :
205 : /* fd_gui_store_reclaim performs pressure reclamation, removing at most
206 : budget records from one oldest region. ring_idx==ULONG_MAX selects
207 : the oldest eligible excess region across all rings and protects their
208 : newest base_regions regions.
209 : Otherwise only the named writer's own oldest region is considered,
210 : including its base. eligible_cb may be NULL (all records eligible).
211 : A rejected head is never skipped within a ring. Returns records
212 : removed (not regions freed); zero means no eligible candidate.
213 : Explicit kv_evict/ts_evict below are logical deletion operations and
214 : intentionally do not implement the cross-ring pressure policy. */
215 : ulong
216 : fd_gui_store_reclaim( fd_gui_store_t * db,
217 : ulong ring_idx,
218 : ulong budget,
219 : int (*eligible_cb)( ulong, void const *, void * ),
220 : void * ctx );
221 :
222 : int
223 : fd_gui_store_fd( fd_gui_store_t const * db );
224 :
225 : struct fd_gui_store_metrics {
226 : ulong kv_lookups [ FD_GUI_STORE_MAX_RINGS ]; /* KV lookup calls (per call) */
227 : ulong ts_appends [ FD_GUI_STORE_MAX_RINGS ]; /* TS records appended (per rec) */
228 : ulong ts_reads [ FD_GUI_STORE_MAX_RINGS ]; /* TS scan calls (per call) */
229 : ulong ts_read_records[ FD_GUI_STORE_MAX_RINGS ]; /* TS records returned (per rec) */
230 : ulong evict_records[ FD_GUI_STORE_MAX_RINGS ]; /* records physically evicted */
231 : ulong evicts [ FD_GUI_STORE_MAX_RINGS ]; /* kv_evict + ts_evict calls */
232 : ulong region_grows [ FD_GUI_STORE_MAX_RINGS ]; /* regions claimed from the free list */
233 : ulong region_reclaims[ FD_GUI_STORE_MAX_RINGS ]; /* regions returned to the free list */
234 : ulong map_full [ FD_GUI_STORE_MAX_RINGS ]; /* low-level MAP_FULL returns before higher-layer recovery */
235 : };
236 :
237 : typedef struct fd_gui_store_metrics fd_gui_store_metrics_t;
238 :
239 : fd_gui_store_metrics_t const *
240 : fd_gui_store_metrics( fd_gui_store_t const * db );
241 :
242 : /* fd_gui_store_ring_stats computes on-demand space accounting for ring
243 : `ring_idx`. */
244 : void
245 : fd_gui_store_ring_stats( fd_gui_store_t * db,
246 : ulong ring_idx,
247 : ulong * used_bytes,
248 : ulong * cap_bytes,
249 : ulong * free_bytes,
250 : ulong * used_slots,
251 : ulong * cap_slots,
252 : ulong * free_slots );
253 :
254 : /* ---- KV ring -------------------------------------------------------- */
255 :
256 : /* fd_gui_store_kv_get_or_create reserves (creating if absent) the
257 : record for `key` and, on success, hands back a mutable pointer to the
258 : record's value region. Returns RING_FULL if this ring's max_records
259 : budget is exhausted, MAP_FULL if no region is available under the
260 : base reservation policy, or ERR on invalid input / file growth error.
261 : An existing record can be updated even when either resource is full. */
262 :
263 : int
264 : fd_gui_store_kv_get_or_create( fd_gui_store_t * db,
265 : ulong ring_idx,
266 : void const * key,
267 : void ** val_out );
268 :
269 : /* fd_gui_store_kv_get looks up the record for `key` in KV ring
270 : `ring_idx` and returns a mutable pointer to the record's value
271 : region, or NULL if the record is not found. */
272 :
273 : void *
274 : fd_gui_store_kv_get( fd_gui_store_t * db,
275 : ulong ring_idx,
276 : void const * key );
277 :
278 : /* fd_gui_store_kv_get_any looks up the lowest record whose key matches
279 : `key` (per the ring's key_cmp, which may treat sentinel fields in `key`
280 : as wildcards) and returns a mutable pointer to its value region, or
281 : NULL if none. Pass key==NULL to match the lowest record in the ring. */
282 :
283 : void *
284 : fd_gui_store_kv_get_any( fd_gui_store_t * db,
285 : ulong ring_idx,
286 : void const * key );
287 :
288 : struct fd_gui_store_kv_iter {
289 : void const * rec; /* current record value (into the store map); NULL when done */
290 : void const * key; /* current record full key (into rec, at key_off); NULL when done */
291 : ulong val_sz; /* current record value size */
292 : ulong key_sz; /* current record full key size */
293 : /* opaque state */
294 : void * _db; /* backend handle (fd_gui_store_t *) */
295 : ulong _ring_idx;
296 : int _valid;
297 : int _have_prev; /* 1 once at least one record has been emitted */
298 : uchar _key[ 16 ]; /* query key (may hold wildcards); FD_GUI_STORE_KV_KEY_MAX */
299 : uchar _prev_key[ 16 ]; /* last emitted full key (selection cursor) */
300 : };
301 :
302 : typedef struct fd_gui_store_kv_iter fd_gui_store_kv_iter_t;
303 :
304 : fd_gui_store_kv_iter_t *
305 : fd_gui_store_kv_iter_begin( fd_gui_store_t * db,
306 : fd_gui_store_kv_iter_t * iter,
307 : ulong ring_idx,
308 : void const * key );
309 :
310 : FD_FN_PURE static inline int
311 450 : fd_gui_store_kv_iter_done( fd_gui_store_kv_iter_t const * iter ) {
312 450 : return !iter->_valid;
313 450 : }
314 :
315 : int
316 : fd_gui_store_kv_iter_next( fd_gui_store_kv_iter_t * iter );
317 :
318 :
319 : struct fd_gui_store_kv_scan {
320 : void const * rec;
321 : fd_gui_store_t * db;
322 : ulong ring_idx;
323 : ulong cur;
324 : ulong end;
325 : ulong append_capacity;
326 : };
327 : typedef struct fd_gui_store_kv_scan fd_gui_store_kv_scan_t;
328 :
329 : /* fd_gui_store_kv_scan_begin snapshots a KV ring's admission-order end.
330 : scan_next skips evicted records and returns 1 with iter->rec set, or 0
331 : at the snapshot end. No iterator cleanup is required. */
332 :
333 : void
334 : fd_gui_store_kv_scan_begin( fd_gui_store_t * db,
335 : fd_gui_store_kv_scan_t * iter,
336 : ulong ring_idx );
337 :
338 : int
339 : fd_gui_store_kv_scan_next( fd_gui_store_kv_scan_t * iter );
340 :
341 : /* fd_gui_store_kv_scan_seek advances iter past the leading records for
342 : which below_cb(rec,ctx) holds, by binary search. below_cb must be
343 : monotone over the remaining scan range (true on a prefix, then false
344 : for the rest). */
345 :
346 : void
347 : fd_gui_store_kv_scan_seek( fd_gui_store_kv_scan_t * iter,
348 : int (*below_cb)( void const *, void * ),
349 : void * ctx );
350 :
351 : /* fd_gui_store_kv_reclaim_prefix removes up to budget records in admission
352 : order, stopping at the first record rejected by eligible_cb(rec,ctx).
353 : eligible_cb may be NULL (all records eligible). Returns the number
354 : removed. */
355 :
356 : ulong
357 : fd_gui_store_kv_reclaim_prefix( fd_gui_store_t * db,
358 : ulong ring_idx,
359 : ulong budget,
360 : int (*eligible_cb)( void const *, void * ),
361 : void * ctx );
362 :
363 : /* ---- KV ring: eviction ---------------------------------------------- */
364 :
365 : /* fd_gui_store_kv_evict reclaims drained records (up to budget records)
366 : from the `ring_idx` ring, stopping at the hi_key watermark. */
367 :
368 : int
369 : fd_gui_store_kv_evict( fd_gui_store_t * db,
370 : ulong ring_idx,
371 : void const * hi_key,
372 : ulong * budget,
373 : int * drained );
374 :
375 : /* ---- TS ring: append-only stream ------------------------------------ */
376 :
377 : /* fd_gui_store_ts_append appends one fixed-size record to ring
378 : `ring_idx`. Returns FD_GUI_STORE_SUCCESS, FD_GUI_STORE_MAP_FULL,
379 : or FD_GUI_STORE_ERR. A record whose timestamp is lower than the
380 : newest live record's is rejected with FD_GUI_STORE_ERR. */
381 :
382 : int
383 : fd_gui_store_ts_append( fd_gui_store_t * db,
384 : ulong ring_idx,
385 : void const * val );
386 :
387 : /* fd_gui_store_ts_emplace appends one record with timestamp ts to ring
388 : `ring_idx` in place. On success, *val_out points to the stored
389 : record. Same ordering requirement as fd_gui_store_ts_append. */
390 :
391 : int
392 : fd_gui_store_ts_emplace( fd_gui_store_t * db,
393 : ulong ring_idx,
394 : long ts,
395 : void ** val_out );
396 :
397 : /* fd_gui_store_ts_filter_fn is an optional per-record predicate
398 : evaluated during a scan: it returns non-zero to emit the record or
399 : zero to skip it. A NULL filter accepts every record. */
400 :
401 : typedef int (*fd_gui_store_ts_filter_fn)( void const * rec, void * ctx );
402 :
403 : struct fd_gui_store_ts_iter {
404 : void const * rec; /* current record (into the store map); NULL when done */
405 : ulong window; /* current record's window */
406 : /* opaque state */
407 : void * _db; /* backend handle (fd_gui_store_t *) */
408 : void * _cur; /* next ring cursor to examine (value, not ptr) */
409 : int _valid;
410 : ulong _rec_sz; /* ring_idx+1 (0 means uninitialised) */
411 : ulong _window_hi;
412 : ulong _cur_hi; /* ring cursor to stop at (exclusive; head_cur at scan begin) */
413 : fd_gui_store_ts_filter_fn _filter;
414 : void * _filter_ctx;
415 : };
416 :
417 : typedef struct fd_gui_store_ts_iter fd_gui_store_ts_iter_t;
418 :
419 : fd_gui_store_ts_iter_t *
420 : fd_gui_store_ts_scan_begin( fd_gui_store_t * db,
421 : fd_gui_store_ts_iter_t * iter,
422 : ulong ring_idx,
423 : ulong window_lo,
424 : ulong window_hi,
425 : fd_gui_store_ts_filter_fn filter,
426 : void * filter_ctx );
427 :
428 : FD_FN_PURE static inline int
429 310575 : fd_gui_store_ts_scan_done( fd_gui_store_ts_iter_t const * iter ) {
430 310575 : return !iter->_valid;
431 310575 : }
432 :
433 : int
434 : fd_gui_store_ts_scan_next( fd_gui_store_ts_iter_t * iter );
435 :
436 : void
437 : fd_gui_store_ts_scan_end( fd_gui_store_ts_iter_t * iter );
438 :
439 : /* fd_gui_store_ts_live_timestamp_bounds returns the timestamps of the
440 : first and last live records in physical append order in TS ring
441 : `ring_idx`. These are the minimum and maximum live timestamps when
442 : appends have nondecreasing timestamps.
443 :
444 : Returns 1 if the ring holds
445 : any record, 0 if it is empty or not a TS ring. */
446 :
447 : int
448 : fd_gui_store_ts_live_timestamp_bounds( fd_gui_store_t * db,
449 : ulong ring_idx,
450 : long * out_first_timestamp,
451 : long * out_last_timestamp );
452 :
453 : /* ---- TS ring: eviction ---------------------------------------------- */
454 :
455 : /* fd_gui_store_ts_evict reclaims drained records (up to budget records)
456 : from the `ring_idx` ring, stopping at the hi_key watermark. */
457 :
458 : int
459 : fd_gui_store_ts_evict( fd_gui_store_t * db,
460 : ulong ring_idx,
461 : ulong hi_window,
462 : ulong * budget,
463 : int * drained );
464 :
465 : FD_PROTOTYPES_END
466 :
467 : #endif /* HEADER_fd_src_disco_gui_fd_gui_store_h */
|
