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. The scan order is
20 : insertion 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 ftruncate'd up to the highest claimed
29 : region as needed, never exceeding size_bytes. Region ownership, the
30 : free list and the TS window index 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 : (ftruncate'd 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 1805901 : #define FD_GUI_STORE_SUCCESS ( 0)
85 0 : #define FD_GUI_STORE_ERR (-1)
86 442374 : #define FD_GUI_STORE_MAP_FULL ( 1)
87 :
88 1668 : #define FD_GUI_STORE_KIND_KV (0)
89 24 : #define FD_GUI_STORE_KIND_TS (1)
90 :
91 : /* FD_GUI_STORE_REGION_SZ is the fixed size of every region in the pool.
92 : No ring's record stride may exceed it (fd_gui_store_new fails fast
93 : otherwise). The store prepends no per-record header (both kinds embed
94 : their metadata in the value), so FD_GUI_STORE_MAX_REC_SZ is the whole
95 : region size. Callers that know their record types at compile time
96 : should static-assert sizeof(their largest record) <=
97 : FD_GUI_STORE_MAX_REC_SZ. */
98 123 : #define FD_GUI_STORE_REGION_SZ (36UL<<20)
99 : #define FD_GUI_STORE_MAX_REC_SZ (FD_GUI_STORE_REGION_SZ)
100 :
101 : /* FD_GUI_STORE_MAX_RINGS is the maximum number of named rings a store
102 : can host. It bounds the per-ring metrics arrays below. */
103 3315 : #define FD_GUI_STORE_MAX_RINGS (64UL)
104 :
105 : /* FD_GUI_STORE_TS_IDX_DEPTH is the depth of the time-series index
106 : array, measured in one second window buckets. */
107 855366642 : #define FD_GUI_STORE_TS_IDX_DEPTH (30UL*24UL*60UL*60UL) /* 30 days of 1s windows */
108 :
109 : struct fd_gui_store_desc {
110 : char const * name; /* the name of the ring. Must be non-NULL and unique within the store */
111 : int kind; /* FD_GUI_STORE_KIND_KV or FD_GUI_STORE_KIND_TS */
112 : ulong key_off; /* byte offset, within the value, of the record's key (pass 0 for TS) */
113 : ulong key_sz; /* key size in bytes */
114 : ulong ( * key_hash )( void const * key ); /* hashes a key to a ulong (pass NULL for TS) */
115 : 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) */
116 : ulong val_sz; /* record size in bytes */
117 : ulong val_align; /* record alignment (power of two, >=1; pass 1 for none) */
118 : ulong ts_off; /* byte offset, within the value, of the record's `long` timestamp (TS only; pass 0 for KV) */
119 : ulong granularity; /* TS window divisor: window = (ulong)(*(long*)(val+ts_off)) / granularity (pass 0 for KV) */
120 : ulong max_records; /* The maximum number of distinct live records this ring can ever hold (pass 0 for TS) */
121 : };
122 :
123 : typedef struct fd_gui_store_desc fd_gui_store_desc_t;
124 :
125 : FD_PROTOTYPES_BEGIN
126 :
127 : FD_FN_CONST ulong
128 : fd_gui_store_align( void );
129 :
130 : FD_FN_CONST ulong
131 : fd_gui_store_footprint( ulong size_bytes,
132 : ulong ring_cnt,
133 : fd_gui_store_desc_t const * descs );
134 :
135 : /* fd_gui_store_new formats the workspace region `mem` and opens the
136 : backing store whose data file is `path`, with a size ceiling of
137 : `size_bytes`. The parent directory of `path` must already exist.
138 : `ring_cnt` named rings are created, one per entry of `descs`. The
139 : store is wiped on open.
140 :
141 : Returns `mem` on success, or NULL on failure (logged at WARNING). */
142 :
143 : void *
144 : fd_gui_store_new( void * mem,
145 : char const * path,
146 : ulong size_bytes,
147 : ulong ring_cnt,
148 : fd_gui_store_desc_t const * descs );
149 :
150 : fd_gui_store_t *
151 : fd_gui_store_join( void * mem );
152 :
153 : void *
154 : fd_gui_store_leave( fd_gui_store_t * db );
155 :
156 : void *
157 : fd_gui_store_delete( void * mem );
158 :
159 : /* fd_gui_store_cnt returns the number of named rings in the store. */
160 :
161 : ulong
162 : fd_gui_store_cnt( fd_gui_store_t const * db );
163 :
164 : /* ---- space accounting ------------------------------------------------- */
165 :
166 : ulong
167 : fd_gui_store_used_bytes( fd_gui_store_t * db );
168 :
169 : ulong
170 : fd_gui_store_live_bytes( fd_gui_store_t * db );
171 :
172 : ulong
173 : fd_gui_store_size( fd_gui_store_t const * db );
174 :
175 : /* fd_gui_store_free_region_cnt returns the number of regions currently
176 : unclaimed on disk. */
177 :
178 : ulong
179 : fd_gui_store_free_region_cnt( fd_gui_store_t const * db );
180 :
181 : int
182 : fd_gui_store_fd( fd_gui_store_t const * db );
183 :
184 : /* fd_gui_store_min_overhead_bytes returns the fixed byte overhead a
185 : store adds on top of usable record space: the superblock page plus
186 : one region. A store whose size_bytes ceiling is at least this large
187 : plus the caller's desired usable capacity is guaranteed to lay out
188 : with at least one region. */
189 :
190 : FD_FN_CONST ulong
191 : fd_gui_store_min_overhead_bytes( void );
192 :
193 : struct fd_gui_store_metrics {
194 : ulong kv_lookups [ FD_GUI_STORE_MAX_RINGS ]; /* KV lookup calls (per call) */
195 : ulong ts_appends [ FD_GUI_STORE_MAX_RINGS ]; /* TS records appended (per rec) */
196 : ulong ts_reads [ FD_GUI_STORE_MAX_RINGS ]; /* TS scan calls (per call) */
197 : ulong ts_read_records[ FD_GUI_STORE_MAX_RINGS ]; /* TS records returned (per rec) */
198 : ulong evict_records[ FD_GUI_STORE_MAX_RINGS ]; /* records physically evicted */
199 : ulong evicts [ FD_GUI_STORE_MAX_RINGS ]; /* kv_evict + ts_evict calls */
200 : ulong region_grows [ FD_GUI_STORE_MAX_RINGS ]; /* regions claimed from the free list */
201 : ulong region_reclaims[ FD_GUI_STORE_MAX_RINGS ]; /* regions returned to the free list */
202 : ulong map_full [ FD_GUI_STORE_MAX_RINGS ]; /* low-level MAP_FULL returns before higher-layer recovery */
203 : };
204 :
205 : typedef struct fd_gui_store_metrics fd_gui_store_metrics_t;
206 :
207 : fd_gui_store_metrics_t const *
208 : fd_gui_store_metrics( fd_gui_store_t const * db );
209 :
210 : /* fd_gui_store_ring_stats computes on-demand space accounting for ring
211 : `ring_idx`. */
212 : void
213 : fd_gui_store_ring_stats( fd_gui_store_t * db,
214 : ulong ring_idx,
215 : ulong * used_bytes,
216 : ulong * cap_bytes,
217 : ulong * free_bytes,
218 : ulong * used_slots,
219 : ulong * cap_slots,
220 : ulong * free_slots );
221 :
222 : /* ---- KV ring -------------------------------------------------------- */
223 :
224 : /* fd_gui_store_kv_get_or_create reserves (creating if absent) the
225 : record for `key` and, on success, hands back a mutable pointer to the
226 : record's value region. */
227 :
228 : int
229 : fd_gui_store_kv_get_or_create( fd_gui_store_t * db,
230 : ulong ring_idx,
231 : void const * key,
232 : void ** val_out );
233 :
234 : /* fd_gui_store_kv_get looks up the record for `key` in KV ring
235 : `ring_idx` and returns a mutable pointer to the record's value
236 : region, or NULL if the record is not found. */
237 :
238 : void *
239 : fd_gui_store_kv_get( fd_gui_store_t * db,
240 : ulong ring_idx,
241 : void const * key );
242 :
243 : /* fd_gui_store_kv_get_any looks up the lowest record whose key matches
244 : `key` (per the ring's key_cmp, which may treat sentinel fields in `key`
245 : as wildcards) and returns a mutable pointer to its value region, or
246 : NULL if none. Pass key==NULL to match the lowest record in the ring. */
247 :
248 : void *
249 : fd_gui_store_kv_get_any( fd_gui_store_t * db,
250 : ulong ring_idx,
251 : void const * key );
252 :
253 : struct fd_gui_store_kv_iter {
254 : void const * rec; /* current record value (into the store map); NULL when done */
255 : void const * key; /* current record full key (into rec, at key_off); NULL when done */
256 : ulong val_sz; /* current record value size */
257 : ulong key_sz; /* current record full key size */
258 : /* opaque state */
259 : void * _db; /* backend handle (fd_gui_store_t *) */
260 : ulong _ring_idx;
261 : int _valid;
262 : int _have_prev; /* 1 once at least one record has been emitted */
263 : uchar _key[ 16 ]; /* query key (may hold wildcards); FD_GUI_STORE_KV_KEY_MAX */
264 : uchar _prev_key[ 16 ]; /* last emitted full key (selection cursor) */
265 : };
266 :
267 : typedef struct fd_gui_store_kv_iter fd_gui_store_kv_iter_t;
268 :
269 : fd_gui_store_kv_iter_t *
270 : fd_gui_store_kv_iter_begin( fd_gui_store_t * db,
271 : fd_gui_store_kv_iter_t * iter,
272 : ulong ring_idx,
273 : void const * key );
274 :
275 : FD_FN_PURE static inline int
276 18 : fd_gui_store_kv_iter_done( fd_gui_store_kv_iter_t const * iter ) {
277 18 : return !iter->_valid;
278 18 : }
279 :
280 : int
281 : fd_gui_store_kv_iter_next( fd_gui_store_kv_iter_t * iter );
282 :
283 :
284 : /* ---- KV ring: eviction ---------------------------------------------- */
285 :
286 : /* fd_gui_store_kv_evict reclaims drained records (up to budget records)
287 : from the `ring_idx` ring, stopping at the hi_key watermark. */
288 :
289 : int
290 : fd_gui_store_kv_evict( fd_gui_store_t * db,
291 : ulong ring_idx,
292 : void const * hi_key,
293 : ulong * budget,
294 : int * drained );
295 :
296 : /* ---- TS ring: append-only stream ------------------------------------ */
297 :
298 : /* fd_gui_store_ts_append appends one fixed-size record to ring
299 : `ring_idx`. Returns FD_GUI_STORE_SUCCESS, FD_GUI_STORE_MAP_FULL,
300 : or FD_GUI_STORE_ERR. */
301 :
302 : int
303 : fd_gui_store_ts_append( fd_gui_store_t * db,
304 : ulong ring_idx,
305 : void const * val );
306 :
307 : /* fd_gui_store_ts_filter_fn is an optional per-record predicate
308 : evaluated during a scan: it returns non-zero to emit the record or
309 : zero to skip it. A NULL filter accepts every record. */
310 :
311 : typedef int (*fd_gui_store_ts_filter_fn)( void const * rec, void * ctx );
312 :
313 : struct fd_gui_store_ts_iter {
314 : void const * rec; /* current record (into the store map); NULL when done */
315 : ulong window; /* current record's window */
316 : /* opaque state */
317 : void * _db; /* backend handle (fd_gui_store_t *) */
318 : void * _cur; /* next ring cursor to examine (value, not ptr) */
319 : int _valid;
320 : ulong _rec_sz; /* ring_idx+1 (0 means uninitialised) */
321 : ulong _window_lo;
322 : ulong _window_hi;
323 : ulong _cur_hi; /* ring cursor to stop at (exclusive; from the window index) */
324 : fd_gui_store_ts_filter_fn _filter;
325 : void * _filter_ctx;
326 : };
327 :
328 : typedef struct fd_gui_store_ts_iter fd_gui_store_ts_iter_t;
329 :
330 : fd_gui_store_ts_iter_t *
331 : fd_gui_store_ts_scan_begin( fd_gui_store_t * db,
332 : fd_gui_store_ts_iter_t * iter,
333 : ulong ring_idx,
334 : ulong window_lo,
335 : ulong window_hi,
336 : fd_gui_store_ts_filter_fn filter,
337 : void * filter_ctx );
338 :
339 : FD_FN_PURE static inline int
340 3819 : fd_gui_store_ts_scan_done( fd_gui_store_ts_iter_t const * iter ) {
341 3819 : return !iter->_valid;
342 3819 : }
343 :
344 : int
345 : fd_gui_store_ts_scan_next( fd_gui_store_ts_iter_t * iter );
346 :
347 : void
348 : fd_gui_store_ts_scan_end( fd_gui_store_ts_iter_t * iter );
349 :
350 : /* fd_gui_store_ts_oldest_window returns, in *out_window, the time
351 : window for the oldest record in TS ring `ring_idx`. Returns 1 if the
352 : ring holds any record, 0 if it is empty or not a TS ring. */
353 :
354 : int
355 : fd_gui_store_ts_oldest_window( fd_gui_store_t * db,
356 : ulong ring_idx,
357 : ulong * out_window );
358 :
359 : /* ---- TS ring: eviction ---------------------------------------------- */
360 :
361 : /* fd_gui_store_ts_evict reclaims drained records (up to budget records)
362 : from the `ring_idx` ring, stopping at the hi_key watermark. */
363 :
364 : int
365 : fd_gui_store_ts_evict( fd_gui_store_t * db,
366 : ulong ring_idx,
367 : ulong hi_window,
368 : ulong * budget,
369 : int * drained );
370 :
371 : FD_PROTOTYPES_END
372 :
373 : #endif /* HEADER_fd_src_disco_gui_fd_gui_store_h */
|
