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 0 : #define FD_GUI_STORE_SUCCESS ( 0)
85 0 : #define FD_GUI_STORE_ERR (-1)
86 0 : #define FD_GUI_STORE_MAP_FULL ( 1)
87 0 : #define FD_GUI_STORE_RING_FULL ( 2) /* this KV ring's index budget is full */
88 :
89 0 : #define FD_GUI_STORE_KIND_KV (0)
90 0 : #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 0 : #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. Unclaimed base regions are
103 : reserved lazily; other rings can neither allocate them nor pressure-
104 : evict records in the newest BASE_REGIONS regions. A writer may recycle
105 : its own oldest eligible records when shared capacity is exhausted. */
106 0 : #define FD_GUI_STORE_BASE_REGIONS (3UL)
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 0 : #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 : };
125 :
126 : typedef struct fd_gui_store_desc fd_gui_store_desc_t;
127 :
128 : FD_PROTOTYPES_BEGIN
129 :
130 : FD_FN_CONST ulong
131 : fd_gui_store_align( void );
132 :
133 : FD_FN_CONST ulong
134 : fd_gui_store_footprint( ulong size_bytes,
135 : ulong ring_cnt,
136 : fd_gui_store_desc_t const * descs );
137 :
138 : /* fd_gui_store_new formats the workspace region `mem` and opens the
139 : backing store whose data file is `path`, with a size ceiling of
140 : `size_bytes`. The parent directory of `path` must already exist.
141 : `ring_cnt` named rings are created, one per entry of `descs`. The
142 : `seed+i` initializes KV ring `i`'s index. The store is wiped on open.
143 :
144 : Returns `mem` on success, or NULL on failure (logged at WARNING). */
145 :
146 : void *
147 : fd_gui_store_new( void * mem,
148 : char const * path,
149 : ulong size_bytes,
150 : ulong ring_cnt,
151 : ulong seed,
152 : fd_gui_store_desc_t const * descs );
153 :
154 : fd_gui_store_t *
155 : fd_gui_store_join( void * mem );
156 :
157 : void *
158 : fd_gui_store_leave( fd_gui_store_t * db );
159 :
160 : void *
161 : fd_gui_store_delete( void * mem );
162 :
163 : /* fd_gui_store_cnt returns the number of named rings in the store. */
164 :
165 : ulong
166 : fd_gui_store_cnt( fd_gui_store_t const * db );
167 :
168 : /* ---- space accounting ------------------------------------------------- */
169 :
170 : ulong
171 : fd_gui_store_used_bytes( fd_gui_store_t * db );
172 :
173 : ulong
174 : fd_gui_store_live_bytes( fd_gui_store_t * db );
175 :
176 : ulong
177 : fd_gui_store_size( fd_gui_store_t const * db );
178 :
179 : /* fd_gui_store_file_sz returns the logical allocated length of the
180 : backing file. */
181 :
182 : ulong
183 : fd_gui_store_file_sz( fd_gui_store_t const * db );
184 :
185 : /* fd_gui_store_free_region_cnt returns the number of regions currently
186 : unclaimed on disk. */
187 :
188 : ulong
189 : fd_gui_store_free_region_cnt( fd_gui_store_t const * db );
190 :
191 : /* fd_gui_store_shared_free_region_cnt returns the unclaimed regions
192 : available excluding the base region allocation. */
193 : ulong
194 : fd_gui_store_shared_free_region_cnt( fd_gui_store_t const * db );
195 :
196 : /* fd_gui_store_min_size returns the minimum file size ceiling for
197 : ring_cnt rings; zero for an invalid ring count. new/footprint
198 : reject smaller stores before opening a file. */
199 : FD_FN_CONST ulong
200 : fd_gui_store_min_size( ulong ring_cnt );
201 :
202 : /* fd_gui_store_reclaim performs pressure reclamation, removing at most
203 : budget records from one oldest region. ring_idx==ULONG_MAX selects
204 : the oldest eligible excess region across all rings and protects their
205 : newest BASE_REGIONS regions.
206 : Otherwise only the named writer's own oldest region is considered,
207 : including its base. eligible may be NULL (all records eligible).
208 : A rejected head is never skipped within a ring. Returns records
209 : removed (not regions freed); zero means no eligible candidate.
210 : Explicit kv_evict/ts_evict below are logical deletion operations and
211 : intentionally do not implement the cross-ring pressure policy. */
212 : ulong
213 : fd_gui_store_reclaim( fd_gui_store_t * db,
214 : ulong ring_idx,
215 : ulong budget,
216 : int (*eligible)( ulong, void const *, void * ),
217 : void * ctx );
218 :
219 : int
220 : fd_gui_store_fd( fd_gui_store_t const * db );
221 :
222 : struct fd_gui_store_metrics {
223 : ulong kv_lookups [ FD_GUI_STORE_MAX_RINGS ]; /* KV lookup calls (per call) */
224 : ulong ts_appends [ FD_GUI_STORE_MAX_RINGS ]; /* TS records appended (per rec) */
225 : ulong ts_reads [ FD_GUI_STORE_MAX_RINGS ]; /* TS scan calls (per call) */
226 : ulong ts_read_records[ FD_GUI_STORE_MAX_RINGS ]; /* TS records returned (per rec) */
227 : ulong evict_records[ FD_GUI_STORE_MAX_RINGS ]; /* records physically evicted */
228 : ulong evicts [ FD_GUI_STORE_MAX_RINGS ]; /* kv_evict + ts_evict calls */
229 : ulong region_grows [ FD_GUI_STORE_MAX_RINGS ]; /* regions claimed from the free list */
230 : ulong region_reclaims[ FD_GUI_STORE_MAX_RINGS ]; /* regions returned to the free list */
231 : ulong map_full [ FD_GUI_STORE_MAX_RINGS ]; /* low-level MAP_FULL returns before higher-layer recovery */
232 : };
233 :
234 : typedef struct fd_gui_store_metrics fd_gui_store_metrics_t;
235 :
236 : fd_gui_store_metrics_t const *
237 : fd_gui_store_metrics( fd_gui_store_t const * db );
238 :
239 : /* fd_gui_store_ring_stats computes on-demand space accounting for ring
240 : `ring_idx`. */
241 : void
242 : fd_gui_store_ring_stats( fd_gui_store_t * db,
243 : ulong ring_idx,
244 : ulong * used_bytes,
245 : ulong * cap_bytes,
246 : ulong * free_bytes,
247 : ulong * used_slots,
248 : ulong * cap_slots,
249 : ulong * free_slots );
250 :
251 : /* ---- KV ring -------------------------------------------------------- */
252 :
253 : /* fd_gui_store_kv_get_or_create reserves (creating if absent) the
254 : record for `key` and, on success, hands back a mutable pointer to the
255 : record's value region. Returns RING_FULL if this ring's max_records
256 : budget is exhausted, MAP_FULL if no region is available under the
257 : base reservation policy, or ERR on invalid input / file growth error.
258 : An existing record can be updated even when either resource is full. */
259 :
260 : int
261 : fd_gui_store_kv_get_or_create( fd_gui_store_t * db,
262 : ulong ring_idx,
263 : void const * key,
264 : void ** val_out );
265 :
266 : /* fd_gui_store_kv_get looks up the record for `key` in KV ring
267 : `ring_idx` and returns a mutable pointer to the record's value
268 : region, or NULL if the record is not found. */
269 :
270 : void *
271 : fd_gui_store_kv_get( fd_gui_store_t * db,
272 : ulong ring_idx,
273 : void const * key );
274 :
275 : /* fd_gui_store_kv_get_any looks up the lowest record whose key matches
276 : `key` (per the ring's key_cmp, which may treat sentinel fields in `key`
277 : as wildcards) and returns a mutable pointer to its value region, or
278 : NULL if none. Pass key==NULL to match the lowest record in the ring. */
279 :
280 : void *
281 : fd_gui_store_kv_get_any( fd_gui_store_t * db,
282 : ulong ring_idx,
283 : void const * key );
284 :
285 : struct fd_gui_store_kv_iter {
286 : void const * rec; /* current record value (into the store map); NULL when done */
287 : void const * key; /* current record full key (into rec, at key_off); NULL when done */
288 : ulong val_sz; /* current record value size */
289 : ulong key_sz; /* current record full key size */
290 : /* opaque state */
291 : void * _db; /* backend handle (fd_gui_store_t *) */
292 : ulong _ring_idx;
293 : int _valid;
294 : int _have_prev; /* 1 once at least one record has been emitted */
295 : uchar _key[ 16 ]; /* query key (may hold wildcards); FD_GUI_STORE_KV_KEY_MAX */
296 : uchar _prev_key[ 16 ]; /* last emitted full key (selection cursor) */
297 : };
298 :
299 : typedef struct fd_gui_store_kv_iter fd_gui_store_kv_iter_t;
300 :
301 : fd_gui_store_kv_iter_t *
302 : fd_gui_store_kv_iter_begin( fd_gui_store_t * db,
303 : fd_gui_store_kv_iter_t * iter,
304 : ulong ring_idx,
305 : void const * key );
306 :
307 : FD_FN_PURE static inline int
308 0 : fd_gui_store_kv_iter_done( fd_gui_store_kv_iter_t const * iter ) {
309 0 : return !iter->_valid;
310 0 : }
311 :
312 : int
313 : fd_gui_store_kv_iter_next( fd_gui_store_kv_iter_t * iter );
314 :
315 :
316 : struct fd_gui_store_kv_scan {
317 : void const * rec;
318 : fd_gui_store_t * db;
319 : ulong ring_idx;
320 : ulong cur;
321 : ulong end;
322 : ulong append_capacity;
323 : };
324 : typedef struct fd_gui_store_kv_scan fd_gui_store_kv_scan_t;
325 :
326 : /* fd_gui_store_kv_scan_begin snapshots a KV ring's admission-order end.
327 : scan_next skips evicted records and returns 1 with iter->rec set, or 0
328 : at the snapshot end. No iterator cleanup is required. */
329 :
330 : void
331 : fd_gui_store_kv_scan_begin( fd_gui_store_t * db,
332 : fd_gui_store_kv_scan_t * iter,
333 : ulong ring_idx );
334 :
335 : int
336 : fd_gui_store_kv_scan_next( fd_gui_store_kv_scan_t * iter );
337 :
338 : /* fd_gui_store_kv_reclaim_prefix removes up to budget records in admission
339 : order, stopping at the first record rejected by eligible(rec,ctx).
340 : Returns the number removed. */
341 :
342 : ulong
343 : fd_gui_store_kv_reclaim_prefix( fd_gui_store_t * db,
344 : ulong ring_idx,
345 : ulong budget,
346 : int (*eligible)( void const *, void * ),
347 : void * ctx );
348 :
349 : /* ---- KV ring: eviction ---------------------------------------------- */
350 :
351 : /* fd_gui_store_kv_evict reclaims drained records (up to budget records)
352 : from the `ring_idx` ring, stopping at the hi_key watermark. */
353 :
354 : int
355 : fd_gui_store_kv_evict( fd_gui_store_t * db,
356 : ulong ring_idx,
357 : void const * hi_key,
358 : ulong * budget,
359 : int * drained );
360 :
361 : /* ---- TS ring: append-only stream ------------------------------------ */
362 :
363 : /* fd_gui_store_ts_append appends one fixed-size record to ring
364 : `ring_idx`. Returns FD_GUI_STORE_SUCCESS, FD_GUI_STORE_MAP_FULL,
365 : or FD_GUI_STORE_ERR. A record whose timestamp is lower than the
366 : newest live record's is rejected with FD_GUI_STORE_ERR. */
367 :
368 : int
369 : fd_gui_store_ts_append( fd_gui_store_t * db,
370 : ulong ring_idx,
371 : void const * val );
372 :
373 : /* fd_gui_store_ts_emplace appends one record with timestamp ts to ring
374 : `ring_idx` in place. On success, *val_out points to the stored
375 : record. Same ordering requirement as fd_gui_store_ts_append. */
376 :
377 : int
378 : fd_gui_store_ts_emplace( fd_gui_store_t * db,
379 : ulong ring_idx,
380 : long ts,
381 : void ** val_out );
382 :
383 : /* fd_gui_store_ts_filter_fn is an optional per-record predicate
384 : evaluated during a scan: it returns non-zero to emit the record or
385 : zero to skip it. A NULL filter accepts every record. */
386 :
387 : typedef int (*fd_gui_store_ts_filter_fn)( void const * rec, void * ctx );
388 :
389 : struct fd_gui_store_ts_iter {
390 : void const * rec; /* current record (into the store map); NULL when done */
391 : ulong window; /* current record's window */
392 : /* opaque state */
393 : void * _db; /* backend handle (fd_gui_store_t *) */
394 : void * _cur; /* next ring cursor to examine (value, not ptr) */
395 : int _valid;
396 : ulong _rec_sz; /* ring_idx+1 (0 means uninitialised) */
397 : ulong _window_hi;
398 : ulong _cur_hi; /* ring cursor to stop at (exclusive; head_cur at scan begin) */
399 : fd_gui_store_ts_filter_fn _filter;
400 : void * _filter_ctx;
401 : };
402 :
403 : typedef struct fd_gui_store_ts_iter fd_gui_store_ts_iter_t;
404 :
405 : fd_gui_store_ts_iter_t *
406 : fd_gui_store_ts_scan_begin( fd_gui_store_t * db,
407 : fd_gui_store_ts_iter_t * iter,
408 : ulong ring_idx,
409 : ulong window_lo,
410 : ulong window_hi,
411 : fd_gui_store_ts_filter_fn filter,
412 : void * filter_ctx );
413 :
414 : FD_FN_PURE static inline int
415 0 : fd_gui_store_ts_scan_done( fd_gui_store_ts_iter_t const * iter ) {
416 0 : return !iter->_valid;
417 0 : }
418 :
419 : int
420 : fd_gui_store_ts_scan_next( fd_gui_store_ts_iter_t * iter );
421 :
422 : void
423 : fd_gui_store_ts_scan_end( fd_gui_store_ts_iter_t * iter );
424 :
425 : /* fd_gui_store_ts_live_timestamp_bounds returns the timestamps of the
426 : first and last live records in physical append order in TS ring
427 : `ring_idx`. These are the minimum and maximum live timestamps when
428 : appends have nondecreasing timestamps.
429 :
430 : Returns 1 if the ring holds
431 : any record, 0 if it is empty or not a TS ring. */
432 :
433 : int
434 : fd_gui_store_ts_live_timestamp_bounds( fd_gui_store_t * db,
435 : ulong ring_idx,
436 : long * out_first_timestamp,
437 : long * out_last_timestamp );
438 :
439 : /* ---- TS ring: eviction ---------------------------------------------- */
440 :
441 : /* fd_gui_store_ts_evict reclaims drained records (up to budget records)
442 : from the `ring_idx` ring, stopping at the hi_key watermark. */
443 :
444 : int
445 : fd_gui_store_ts_evict( fd_gui_store_t * db,
446 : ulong ring_idx,
447 : ulong hi_window,
448 : ulong * budget,
449 : int * drained );
450 :
451 : FD_PROTOTYPES_END
452 :
453 : #endif /* HEADER_fd_src_disco_gui_fd_gui_store_h */
|
