Skip to main content

store_io_engine/
space.rs

1//! Space: reservations, hard caps and per-tag accounting.
2//!
3//! A [`Reservation`] sets space aside before it is needed: `reserve` checks
4//! the tag's hard cap and grows the container so that provisioning from the
5//! reservation can never run out of space. It is the only place where a full
6//! file system or quota surfaces as [`Error::NoSpace`], and nothing is ever
7//! poisoned by it.
8//!
9//! The container always holds every region and every outstanding
10//! reservation: `reserve` grows it to keep that true, provisioning from a
11//! reservation turns reserved bytes into used bytes without allocating, and
12//! provisioning without one grows the container past the outstanding
13//! reservations so it can never take space promised to someone else.
14//!
15//! Tags are opaque to store-io (a tenant, a class). Each region records its
16//! tag in the region table, so per-tag usage is derived again on every open;
17//! caps and outstanding reservations live in memory.
18
19use std::sync::{MutexGuard, PoisonError};
20
21use store_io_core::error::{Error, ErrorContext, NotWrittenCause, ReserveTag};
22use store_io_format::meta::{RegionKind, RegionState, TableEntry};
23use store_io_platform::Platform;
24
25use crate::io::not_written;
26use crate::options::RegionOptions;
27use crate::region::{AppendRegion, PageRegion, Slot};
28use crate::store::{Meta, Store, lock_meta};
29
30/// Usage of one tag.
31#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
32pub struct TagSpace {
33    /// The tag.
34    pub tag: u32,
35    /// Data bytes of the tag's ready regions.
36    pub logical: u64,
37    /// Bytes the tag's ready regions occupy in the container, headers
38    /// included, and those its provisionings and growths filling now hold
39    /// (format 2: charged before their commit).
40    pub physical: u64,
41    /// Bytes reserved for the tag and not yet provisioned.
42    pub reserved: u64,
43    /// The tag's hard cap on `physical + reserved`, if any.
44    pub cap: Option<u64>,
45}
46
47/// Where a store's space goes.
48#[derive(Debug, Clone, PartialEq, Eq, Default)]
49pub struct SpaceReport {
50    /// Bytes the container file holds.
51    pub container: u64,
52    /// Bytes held by ready regions, headers included, and by provisionings
53    /// and growths filling now (format 2: marked before their commit).
54    /// Format 2 also counts an unavailable region whose entry passes the
55    /// entry checks, by its capacity and headers (its span stays allocated
56    /// either way).
57    pub regions: u64,
58    /// Format 1: bytes of released regions, reused by a later region of
59    /// exactly the same size. Format 2: free bytes inside the container,
60    /// usable by any region (the complement of everything allocated, less
61    /// what reservations hold).
62    pub released: u64,
63    /// Bytes reserved and not yet provisioned.
64    pub reserved: u64,
65    /// Usage per tag, in tag order.
66    pub tags: Vec<TagSpace>,
67}
68
69/// In-memory accounting, guarded by `Inner::acct`. Lock order: `meta`, then
70/// `acct`.
71#[derive(Debug, Default)]
72pub(crate) struct Accounting {
73    tags: Vec<TagSpace>,
74    reserved: u64,
75}
76
77impl Accounting {
78    /// Usage derived from the ready entries of a region table.
79    pub(crate) fn from_entries(entries: &[TableEntry], block: u64) -> Self {
80        let mut a = Self::default();
81        for e in entries.iter().filter(|e| e.state == RegionState::Ready) {
82            a.add(e, block);
83        }
84        a
85    }
86
87    /// Usage `(tag, logical, physical)` per format-2 entry.
88    /// Sorted first, so many tags cost O(n log n), not an insertion each.
89    pub(crate) fn from_usage(usage: &[(u32, u64, u64)]) -> Self {
90        let mut sorted = usage.to_vec();
91        sorted.sort_unstable_by_key(|u| u.0);
92        let mut a = Self::default();
93        for (tag, logical, physical) in sorted {
94            match a.tags.last_mut() {
95                Some(t) if t.tag == tag => {
96                    t.logical = t.logical.saturating_add(logical);
97                    t.physical = t.physical.saturating_add(physical);
98                }
99                _ => a.tags.push(TagSpace {
100                    tag,
101                    logical,
102                    physical,
103                    ..TagSpace::default()
104                }),
105            }
106        }
107        a
108    }
109
110    fn tag(&mut self, tag: u32) -> &mut TagSpace {
111        let i = match self.tags.binary_search_by_key(&tag, |t| t.tag) {
112            Ok(i) => i,
113            Err(i) => {
114                self.tags.insert(
115                    i,
116                    TagSpace {
117                        tag,
118                        ..TagSpace::default()
119                    },
120                );
121                i
122            }
123        };
124        &mut self.tags[i]
125    }
126
127    /// Counts a newly provisioned format-2 region.
128    pub(crate) fn add_usage(&mut self, tag: u32, logical: u64, physical: u64) {
129        let t = self.tag(tag);
130        t.logical = t.logical.saturating_add(logical);
131        t.physical = t.physical.saturating_add(physical);
132    }
133
134    /// Stops counting a released format-2 region.
135    pub(crate) fn remove_usage(&mut self, tag: u32, logical: u64, physical: u64) {
136        let t = self.tag(tag);
137        t.logical = t.logical.saturating_sub(logical);
138        t.physical = t.physical.saturating_sub(physical);
139    }
140
141    /// Counts a newly ready region.
142    pub(crate) fn add(&mut self, e: &TableEntry, block: u64) {
143        let physical = e.extent_len(block).unwrap_or(u64::MAX);
144        let t = self.tag(e.tag);
145        t.logical = t.logical.saturating_add(e.data_size);
146        t.physical = t.physical.saturating_add(physical);
147    }
148
149    /// Stops counting a released region.
150    pub(crate) fn remove(&mut self, e: &TableEntry, block: u64) {
151        let physical = e.extent_len(block).unwrap_or(0);
152        let t = self.tag(e.tag);
153        t.logical = t.logical.saturating_sub(e.data_size);
154        t.physical = t.physical.saturating_sub(physical);
155    }
156
157    /// Whether `extra` more bytes fit under the tag's cap.
158    pub(crate) fn fits(&mut self, tag: u32, extra: u64) -> bool {
159        let t = self.tag(tag);
160        t.cap.is_none_or(|cap| {
161            t.physical
162                .checked_add(t.reserved)
163                .and_then(|u| u.checked_add(extra))
164                .is_some_and(|u| u <= cap)
165        })
166    }
167
168    /// Bytes reserved and not yet provisioned, all tags.
169    pub(crate) fn reserved(&self) -> u64 {
170        self.reserved
171    }
172
173    /// Moves `bytes` of `tag` from reserved to provisioned (or back to free
174    /// when a reservation is dropped).
175    pub(crate) fn unreserve(&mut self, tag: u32, bytes: u64) {
176        self.reserved = self.reserved.saturating_sub(bytes);
177        let t = self.tag(tag);
178        t.reserved = t.reserved.saturating_sub(bytes);
179    }
180
181    fn reserve(&mut self, tag: u32, bytes: u64) {
182        self.reserved = self.reserved.saturating_add(bytes);
183        let t = self.tag(tag);
184        t.reserved = t.reserved.saturating_add(bytes);
185    }
186}
187
188pub(crate) fn lock_acct(a: &std::sync::Mutex<Accounting>) -> MutexGuard<'_, Accounting> {
189    a.lock().unwrap_or_else(PoisonError::into_inner)
190}
191
192pub(crate) fn no_space(tag: u32) -> Error {
193    Error::NoSpace {
194        tag: ReserveTag::Caller(tag),
195        ctx: ErrorContext::default(),
196    }
197}
198
199/// Space set aside for provisioning under one tag. Regions provisioned from
200/// it can never fail for lack of space; whatever is left when it is dropped
201/// returns to the free pool.
202pub struct Reservation<P: Platform>
203where
204    P::Queue: Send,
205{
206    store: Store<P>,
207    tag: u32,
208    bytes: u64,
209}
210
211impl<P: Platform> core::fmt::Debug for Reservation<P>
212where
213    P::Queue: Send,
214{
215    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
216        f.debug_struct("Reservation")
217            .field("tag", &self.tag)
218            .field("remaining", &self.bytes)
219            .finish()
220    }
221}
222
223impl<P: Platform> Drop for Reservation<P>
224where
225    P::Queue: Send,
226{
227    fn drop(&mut self) {
228        lock_acct(&self.store.inner.acct).unreserve(self.tag, self.bytes);
229    }
230}
231
232impl<P: Platform> Reservation<P>
233where
234    P::Queue: Send,
235{
236    /// The reservation's tag.
237    #[must_use]
238    pub fn tag(&self) -> u32 {
239        self.tag
240    }
241
242    /// Bytes still reserved. A region uses its data size plus two header
243    /// blocks (see [`Store::extent_of`]).
244    #[must_use]
245    pub fn remaining(&self) -> u64 {
246        self.bytes
247    }
248
249    /// Sets `extent` bytes aside for a format-2 provisioning in flight: no
250    /// longer this reservation's to give, still counted reserved in the
251    /// store's accounting until the commit moves them to the region (so
252    /// every placement meanwhile sizes the container past them).
253    pub(crate) fn hold(&mut self, extent: u64) -> Result<(), Error> {
254        if extent > self.bytes {
255            return Err(no_space(self.tag));
256        }
257        self.bytes -= extent;
258        Ok(())
259    }
260
261    /// Gives back `extent` bytes [`Self::hold`] set aside (a provisioning
262    /// that failed before its commit).
263    pub(crate) fn unhold(&mut self, extent: u64) {
264        self.bytes += extent;
265    }
266
267    /// Takes `extent` bytes for a region being provisioned.
268    pub(crate) fn consume(&mut self, extent: u64) -> Result<(), Error> {
269        if extent > self.bytes {
270            return Err(no_space(self.tag));
271        }
272        self.bytes -= extent;
273        lock_acct(&self.store.inner.acct).unreserve(self.tag, extent);
274        Ok(())
275    }
276
277    /// Provisions an append region from this reservation.
278    ///
279    /// # Errors
280    ///
281    /// As [`Store::provision_append_region`]; `NoSpace` if the reservation
282    /// is too small.
283    pub fn provision_append_region(
284        &mut self,
285        name: &str,
286        size: u64,
287    ) -> Result<AppendRegion<P>, Error> {
288        self.provision_append_region_with(name, RegionOptions::default().size(size))
289    }
290
291    /// Provisions an append region from this reservation as `opts` say (a
292    /// capped region takes its whole capacity from it).
293    ///
294    /// # Errors
295    ///
296    /// As [`Store::provision_append_region_with`]; `NoSpace` if the
297    /// reservation is too small.
298    pub fn provision_append_region_with(
299        &mut self,
300        name: &str,
301        opts: RegionOptions,
302    ) -> Result<AppendRegion<P>, Error> {
303        let store = self.store.clone();
304        let state = store.provision(name, RegionKind::Append, opts, Some(self))?;
305        Ok(AppendRegion::from_parts(store, state))
306    }
307
308    /// Provisions a page region from this reservation.
309    ///
310    /// # Errors
311    ///
312    /// As [`Store::provision_page_region`]; `NoSpace` if the reservation is
313    /// too small.
314    pub fn provision_page_region(&mut self, name: &str, size: u64) -> Result<PageRegion<P>, Error> {
315        self.provision_page_region_with(name, RegionOptions::default().size(size))
316    }
317
318    /// Provisions an append region from this reservation with the store's
319    /// [`StoreOptions::region_defaults`](crate::StoreOptions::region_defaults).
320    ///
321    /// # Errors
322    ///
323    /// As [`Store::provision_append_region_default`]; `NoSpace` if the
324    /// reservation is too small.
325    pub fn provision_append_region_default(
326        &mut self,
327        name: &str,
328    ) -> Result<AppendRegion<P>, Error> {
329        let opts = self.store.region_defaults()?;
330        self.provision_append_region_with(name, opts)
331    }
332
333    /// Provisions a page region from this reservation with the store's
334    /// [`StoreOptions::region_defaults`](crate::StoreOptions::region_defaults).
335    ///
336    /// # Errors
337    ///
338    /// As [`Self::provision_append_region_default`].
339    pub fn provision_page_region_default(&mut self, name: &str) -> Result<PageRegion<P>, Error> {
340        let opts = self.store.region_defaults()?;
341        self.provision_page_region_with(name, opts)
342    }
343
344    /// Provisions a page region from this reservation as `opts` say.
345    ///
346    /// # Errors
347    ///
348    /// As [`Self::provision_append_region_with`].
349    pub fn provision_page_region_with(
350        &mut self,
351        name: &str,
352        opts: RegionOptions,
353    ) -> Result<PageRegion<P>, Error> {
354        let store = self.store.clone();
355        let state = store.provision(name, RegionKind::Page, opts, Some(self))?;
356        Ok(PageRegion::from_parts(store, state))
357    }
358
359    /// Provisions a small-object slot from this reservation.
360    ///
361    /// # Errors
362    ///
363    /// As [`Store::provision_slot`]; `NoSpace` if the reservation is too
364    /// small.
365    pub fn provision_slot(&mut self, name: &str) -> Result<Slot<P>, Error> {
366        let store = self.store.clone();
367        let state =
368            store.provision(name, RegionKind::Slot, RegionOptions::default(), Some(self))?;
369        Ok(Slot::from_parts(store, state))
370    }
371}
372
373impl<P: Platform> Store<P>
374where
375    P::Queue: Send,
376{
377    /// Bytes a region of `data_size` data bytes occupies in the container:
378    /// the data size rounded up to the block, plus two header blocks.
379    #[must_use]
380    pub fn extent_of(&self, data_size: u64) -> Option<u64> {
381        let block = self.block();
382        store_io_core::align::align_up(data_size, block).and_then(|d| self.inner.layout.extent(d))
383    }
384
385    /// Sets (or with `None` removes) the hard cap of `tag`: the most bytes
386    /// its regions and reservations may hold together. Caps live in memory;
387    /// set them again after every open.
388    pub fn set_cap(&self, tag: u32, cap: Option<u64>) {
389        lock_acct(&self.inner.acct).tag(tag).cap = cap;
390    }
391
392    /// Reserves `bytes` for later provisioning under `tag`: checks the tag's
393    /// cap and grows the container so that provisioning from the reservation
394    /// cannot run out of space.
395    ///
396    /// # Errors
397    ///
398    /// `NoSpace { tag }` if the cap or the file system is exceeded (nothing
399    /// changes and nothing is poisoned); `NotWritten(ReadOnly)`; `Poisoned`;
400    /// `Io` for other allocation failures.
401    pub fn reserve(&self, bytes: u64, tag: u32) -> Result<Reservation<P>, Error> {
402        self.ready()?;
403        let inner = &self.inner;
404        if inner.frozen.load(std::sync::atomic::Ordering::Acquire) {
405            // Allocation is frozen (spec ยง9 step 2).
406            return Err(not_written(
407                NotWrittenCause::Frozen,
408                ErrorContext::default(),
409            ));
410        }
411        let mut meta = lock_meta(&inner.meta);
412        let mut acct = lock_acct(&inner.acct);
413        if !acct.fits(tag, bytes) {
414            return Err(no_space(tag));
415        }
416        let target = self
417            .tail(&meta)
418            .checked_add(acct.reserved())
419            .and_then(|t| t.checked_add(bytes))
420            .ok_or_else(|| not_written(NotWrittenCause::TooLarge, ErrorContext::default()))?;
421        self.grow_to(&mut meta, target, tag)?;
422        acct.reserve(tag, bytes);
423        Ok(Reservation {
424            store: self.clone(),
425            tag,
426            bytes,
427        })
428    }
429
430    /// Where space goes: the container, regions, released extents,
431    /// reservations, and usage per tag.
432    #[must_use]
433    pub fn space(&self) -> SpaceReport {
434        let inner = &self.inner;
435        let meta = lock_meta(&inner.meta);
436        let acct = lock_acct(&inner.acct);
437        let block = self.block();
438        let sum = |state| {
439            meta.entries
440                .iter()
441                .filter(|e| e.state == state)
442                .filter_map(|e| e.extent_len(block))
443                .sum()
444        };
445        if let Some(v2) = meta.v2.as_deref() {
446            return SpaceReport {
447                container: meta.container_len,
448                // Marked by provisionings and growths filling now: in use.
449                regions: v2.usage.iter().map(|u| u.2).sum::<u64>() + v2.marked,
450                // The trailing free space holds the reservations: not
451                // free for anyone else.
452                released: v2.free.free_bytes().saturating_sub(acct.reserved()),
453                reserved: acct.reserved(),
454                tags: acct.tags.clone(),
455            };
456        }
457        SpaceReport {
458            container: meta.container_len,
459            regions: sum(RegionState::Ready),
460            released: sum(RegionState::Released),
461            reserved: acct.reserved(),
462            tags: acct.tags.clone(),
463        }
464    }
465
466    /// The end of the last extent in the table (the start of free tail
467    /// space).
468    pub(crate) fn tail(&self, meta: &Meta) -> u64 {
469        match meta.v2.as_deref() {
470            Some(v2) => v2.free.end(),
471            None => self.inner.layout.tail(&meta.entries),
472        }
473    }
474
475    /// Grows the container to at least `target` bytes.
476    ///
477    /// Refused with `Corruption(Truncated)` while a region the open found cut
478    /// off by a short container exists: growth would zero-fill that region's
479    /// missing tail, and the next open would find it whole and ready, its
480    /// lost bytes read as zeros (an append region would silently end early).
481    ///
482    /// Only format 2 can have one here: a format-1 store with a region cut
483    /// short opens read-only (from 0.5 every open of format 1 does), and a
484    /// read-only store never grows; a store created as format 1 has none.
485    pub(crate) fn grow_to(&self, meta: &mut Meta, target: u64, tag: u32) -> Result<(), Error> {
486        if target <= meta.container_len {
487            return Ok(());
488        }
489        let inner = &self.inner;
490        // Any format-2 entry past the file's end: one listed as unavailable
491        // (`ContainerShort`) and one whose name does not decode, which has
492        // no listed region. Growing would make zeros of its lost tail.
493        if meta.v2.as_deref().is_some_and(|v| v.cut_short) {
494            return Err(Error::Corruption {
495                kind: store_io_core::error::CorruptionKind::Truncated,
496                ctx: ErrorContext::default(),
497            });
498        }
499        inner
500            .platform
501            .allocate(&inner.file, target)
502            .map_err(|raw| crate::store::space_err(store_io_core::error::Op::Allocate, raw, tag))?;
503        meta.container_len = target;
504        if let Some(v2) = meta.v2.as_deref_mut() {
505            // The new space past the old end is free.
506            v2.rebuild_free(target);
507        }
508        Ok(())
509    }
510}
511
512#[cfg(test)]
513mod tests {
514    #![allow(clippy::unwrap_used)]
515
516    use std::path::Path;
517    use std::time::{Duration, Instant};
518
519    use store_io_sim::{SimConfig, SimPlatform};
520
521    use super::lock_acct;
522    use crate::store::{Store, StoreOptions};
523
524    /// The lock order is metadata, then accounting, everywhere. Checked
525    /// deterministically: with the accounting lock held here, a `reserve`
526    /// on another thread must take the metadata lock first and then wait.
527    /// In the reverse order it would wait on accounting holding nothing,
528    /// and a thread taking them in the documented order could deadlock with
529    /// it (the timing-based test alone missed this on a CI runner).
530    #[test]
531    fn test_reserve_takes_the_metadata_lock_before_the_accounting_lock() {
532        let p = SimPlatform::new(SimConfig::power_safe(42));
533        let s = Store::create(p, Path::new("/db"), StoreOptions::default()).unwrap();
534        let acct = lock_acct(&s.inner.acct);
535        let worker = {
536            let s = s.clone();
537            std::thread::spawn(move || drop(s.reserve(4096, 1)))
538        };
539        let deadline = Instant::now() + Duration::from_secs(30);
540        let mut meta_taken = false;
541        while Instant::now() < deadline {
542            if s.inner.meta.try_lock().is_err() {
543                meta_taken = true;
544                break;
545            }
546            std::thread::sleep(Duration::from_millis(1));
547        }
548        drop(acct);
549        worker.join().unwrap();
550        assert!(
551            meta_taken,
552            "reserve waited for the accounting lock without holding the metadata lock"
553        );
554    }
555}