Skip to main content

store_io_engine/
v2.rs

1//! Container format 2 (`docs/FORMAT.md`, Part I): the paged region
2//! table's metadata, create, the open's tear judgement, region checks
3//! (`open2`) and healing, and the clean close. Built beside format 1 (D-116
4//! makes format 1 read-only once creation switches, v0.5 E5).
5
6use store_io_core::error::{Capability, Error, ErrorContext, Op};
7use store_io_core::id::{RegionId, VolumeId};
8use store_io_format::judge::{self, PairVerdict, SlotVerdict, Standing};
9use store_io_format::meta::VolumeMeta;
10use store_io_format::meta2::{
11    PageHeader, RawEntry, VOLUME_META2_LEN, VolumeMeta2, decode_page, encode_page, entries_per_page,
12};
13use store_io_format::slot::{FORMAT_2, SlotIndex, SlotStatus};
14use store_io_platform::Platform;
15
16use crate::domain::Domain;
17use crate::exec::Lane;
18use crate::layout::Layout;
19use crate::slots::{PairAt, PairRead, plan_next, read_pair, read_pairs, reread_failed, write_slot};
20use crate::store::*;
21
22/// The most regions a format-2 store can be created for (a table of
23/// 24,819 pages, two copies each: 776 MiB at 16 KiB pages, all read at
24/// every open); a larger `region_capacity` is
25/// clamped, and [`StoreReport::table_capacity`] says what was made.
26pub const MAX_REGION_CAPACITY: u32 = 1 << 22;
27
28/// What an open made of a damaged metadata slot
29/// ([`MetadataReport::damaged_slots`], spec §7).
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
31#[non_exhaustive]
32pub enum SlotDamage {
33    /// The winner's predecessor, damaged: reported only (its pair stands).
34    Older,
35    /// The one write a crash left torn: a writable open heals it
36    /// ([`MetadataReport::healed`]; a read-only open leaves it).
37    InFlight,
38    /// Damage a crash cannot explain: its pair stale or lost.
39    Damage,
40}
41
42/// A metadata slot an open found damaged.
43#[derive(Debug, Clone, Copy, PartialEq, Eq)]
44#[non_exhaustive]
45pub struct DamagedSlot {
46    /// The pair: `None` for the volume record, `Some(p)` for table page `p`.
47    pub page: Option<u32>,
48    /// Slot B (`true`) or slot A.
49    pub slot_b: bool,
50    /// What the judgement made of it.
51    pub damage: SlotDamage,
52}
53
54/// What a format-2 open found in its metadata pairs (the volume record and
55/// the table pages).
56#[derive(Debug, Clone, Default, PartialEq, Eq)]
57#[non_exhaustive]
58pub struct MetadataReport {
59    /// The last writer closed cleanly: its final volume record is intact
60    /// and says so (a damaged or in-flight volume record voids it).
61    pub clean_close: bool,
62    /// Pages whose newest copy is damaged (Unconfirmed): their regions are
63    /// read-only and allocation is frozen.
64    pub stale_pages: Vec<u32>,
65    /// Pages with no usable copy (Lost), or whose copy fails the page
66    /// checks: their regions are unknown and allocation is frozen.
67    pub lost_pages: Vec<u32>,
68    /// The volume record's newest copy was damaged (a writable open
69    /// replaces it).
70    pub volume_stale: bool,
71    /// The one metadata write a crash left torn, which this open rewrote.
72    pub healed: Option<Healed>,
73    /// Allocation is frozen: some page is stale or lost (as the open found
74    /// it; now: `Store::frozen`).
75    pub frozen: bool,
76    /// Why a writable open was made read-only, if it was.
77    pub read_only_reason: Option<&'static str>,
78    /// Metadata pairs read a second time because a slot read failed
79    /// (each failed read is retried once).
80    pub retried_reads: u32,
81    /// Every candidate and every damaged slot of the volume record and the
82    /// table pages (spec §9), in pair order, slot A first. A lost pair's
83    /// slots are all damage; a page whose winner fails the page checks
84    /// counts its winner as damage too.
85    pub damaged_slots: Vec<DamagedSlot>,
86    /// Table entries whose kind or name do not decode, as `(page, seq)`:
87    /// unavailable, their spans reserved (the regions with a readable name
88    /// are in `StoreReport::unavailable`).
89    pub invalid_entries: Vec<(u32, u32)>,
90    /// Extents a region header lists past its entry's count (a growth
91    /// beyond capacity cut short): not part of the region; allocated while
92    /// the region's page is stale.
93    pub extra_extents: Vec<(RegionId, (u64, u64))>,
94    /// Regions that may read another region's bytes (spec §9 step 4): an
95    /// unavailable region with a newer footprint overlaps them. Read-only.
96    pub superseded: Vec<RegionId>,
97    /// Regions an unavailable region's span overlaps (those bytes stay
98    /// reserved).
99    pub shares_reserved: Vec<RegionId>,
100    /// For each stale page, whether every region header on it agrees with
101    /// its entry. Agreement does not prove nothing was lost (spec §9): a
102    /// growth within capacity changes only the entry, and a lost release
103    /// can leave a Ready header over reused space.
104    pub stale_page_agreement: Vec<(u32, bool)>,
105    /// Regions whose header pair shows a newer, unreadable version than the
106    /// one the open uses (spec §8): a recycle, slot commit or growth's
107    /// header possibly lost to a crash. The older version is served. After
108    /// a clean close also a pair whose other copy was written and no longer
109    /// verifies, unless it is provably the served version's predecessor
110    /// (D-162): damage since, or a torn write an earlier crash left that no
111    /// later write of the pair replaced (listed until the region's next
112    /// header write). Either way the served version may not be the newest
113    /// written (a slot's last commit); a damaged older copy whose header CRC
114    /// cannot be read is listed too.
115    pub lost_header_writes: Vec<RegionId>,
116    /// A list above was cut at its limit (256 items).
117    pub truncated: bool,
118}
119
120/// Which metadata write a format-2 open healed.
121#[derive(Debug, Clone, Copy, PartialEq, Eq)]
122#[non_exhaustive]
123pub enum Healed {
124    /// The volume record.
125    VolumeRecord,
126    /// Table page `p`.
127    Page(u32),
128}
129
130impl core::fmt::Display for MetadataReport {
131    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
132        let yes = |b: bool| if b { "yes" } else { "no" };
133        writeln!(f, "clean close      {}", yes(self.clean_close))?;
134        if self.volume_stale {
135            writeln!(f, "volume record    stale")?;
136        }
137        if !self.stale_pages.is_empty() {
138            writeln!(f, "stale pages      {:?}", self.stale_pages)?;
139        }
140        if !self.lost_pages.is_empty() {
141            writeln!(f, "lost pages       {:?}", self.lost_pages)?;
142        }
143        if let Some(h) = self.healed {
144            writeln!(f, "healed           {h:?}")?;
145        }
146        if self.frozen {
147            writeln!(f, "allocation       frozen")?;
148        }
149        if let Some(r) = self.read_only_reason {
150            writeln!(f, "read-only        {r}")?;
151        }
152        if self.retried_reads > 0 {
153            writeln!(f, "retried reads    {}", self.retried_reads)?;
154        }
155        for d in &self.damaged_slots {
156            let pair = d
157                .page
158                .map_or_else(|| "volume record".to_owned(), |p| format!("page {p}"));
159            let slot = if d.slot_b { 'B' } else { 'A' };
160            let what = match d.damage {
161                SlotDamage::Older => "an older copy, damaged",
162                SlotDamage::InFlight => "the write in flight",
163                SlotDamage::Damage => "damage",
164            };
165            writeln!(f, "damaged slot     {pair} {slot}: {what}")?;
166        }
167        if !self.invalid_entries.is_empty() {
168            writeln!(f, "invalid entries  {:?}", self.invalid_entries)?;
169        }
170        for (id, (off, len)) in &self.extra_extents {
171            writeln!(f, "extra extent     region {id}: {len} bytes at {off}")?;
172        }
173        if !self.superseded.is_empty() {
174            writeln!(f, "superseded       {:?}", self.superseded)?;
175        }
176        if !self.shares_reserved.is_empty() {
177            writeln!(f, "shares reserved  {:?}", self.shares_reserved)?;
178        }
179        for (p, agrees) in &self.stale_page_agreement {
180            let word = if *agrees { "agree" } else { "disagree" };
181            writeln!(f, "stale page {p}     headers {word} with entries")?;
182        }
183        if !self.lost_header_writes.is_empty() {
184            writeln!(f, "lost header      {:?}", self.lost_header_writes)?;
185        }
186        if self.truncated {
187            writeln!(f, "(lists cut at 256 items)")?;
188        }
189        Ok(())
190    }
191}
192
193/// Object id of table page `p`.
194pub(crate) const fn page_object(p: u32) -> u64 {
195    (1u64 << 61) | p as u64
196}
197
198/// Where page `p`'s pair lives.
199pub(crate) fn pair_page(volume: VolumeId, l: &Layout, p: u32) -> PairAt {
200    let (a, b) = l.page_slots(p);
201    PairAt {
202        volume: *volume.as_bytes(),
203        object: page_object(p),
204        a,
205        b,
206        log2: l.log2_table,
207        format: FORMAT_2,
208        numbered: true,
209    }
210}
211
212/// One table page as the open found it.
213#[derive(Debug, Clone)]
214pub(crate) struct Page2 {
215    pub(crate) pair: PairRead,
216    pub(crate) standing: Standing,
217    /// The winner's page header (none when Lost).
218    pub(crate) header: Option<PageHeader>,
219    /// The winner's entries, unchecked (none yet in E2a).
220    pub(crate) entries: Vec<RawEntry>,
221}
222
223/// Format 2's metadata state.
224#[derive(Debug, Clone)]
225pub(crate) struct Meta2 {
226    pub(crate) volume: VolumeMeta2,
227    pub(crate) pages: Vec<Page2>,
228    /// Free space past the table area, rebuilt as a complement on every
229    /// change (spec §9 step 6).
230    pub(crate) free: crate::footprint::FreeMap,
231    /// Per-tag usage `(tag, logical, physical)` found at open.
232    pub(crate) usage: Vec<(u32, u64, u64)>,
233    /// Names of entries that failed the entry checks with a kind this
234    /// version does not know (not in `StoreReport::unavailable`): reserved
235    /// all the same.
236    pub(crate) reserved_names: Vec<store_io_format::meta::RegionName>,
237    /// An entry names space past the file's end: growth is refused (it
238    /// would make zeros of the lost tail).
239    pub(crate) cut_short: bool,
240    /// Every allocated range: free space is rebuilt from it (never by
241    /// adding a range back).
242    pub(crate) allocated: Vec<(u64, u64)>,
243    /// Provisionings between their placement and their commit: the name
244    /// and the table slot each holds (v0.5 E4 C13).
245    pub(crate) claims: Vec<Claim>,
246    /// Bytes marked allocated by provisionings and growths not yet
247    /// committed (in `allocated`, not yet in `usage`).
248    pub(crate) marked: u64,
249    /// What each unavailable entry (and each of a kind this version does
250    /// not know) holds: exactly what the open added for it, so
251    /// `repair_unavailable` takes away no more and no less (v0.5 E6).
252    pub(crate) holds: Vec<Hold>,
253    /// The extra extents counted allocated because their page is stale
254    /// (spec §9 step 3): `(page, region id, range)`, freed when the page is
255    /// accepted (and copied with its region by `copy_store` when it
256    /// overlaps nothing else).
257    pub(crate) stale_extra: Vec<(usize, u64, (u64, u64))>,
258}
259
260/// How far the open raises a page's `next_seq`, in memory, on every stale
261/// page and every page whose pair may carry an accepted rollback
262/// ([`PairRead::possibly_accepted`]): an
263/// accepted page's lost commit may have handed out seqs past its winner's
264/// `next_seq` (a provisioning's claim takes one past every claim held), and
265/// the region ids it gave out are never handed out again unless more than
266/// this many provisionings failed on that page between its last two
267/// commits. The page's next commit writes the raised value.
268pub(crate) const SEQ_MARGIN: u32 = 1 << 12;
269
270impl Page2 {
271    /// Raises the page's `next_seq` past what a lost commit may have given
272    /// out (see [`SEQ_MARGIN`]).
273    pub(crate) fn raise_next_seq(&mut self) {
274        if let Some(h) = self.header.as_mut() {
275            h.next_seq = h.next_seq.saturating_add(SEQ_MARGIN);
276        }
277    }
278
279    /// The `meta_seq` of the page's winning copy (0 when none).
280    pub(crate) fn meta_seq(&self) -> u64 {
281        self.pair
282            .report
283            .winner_info()
284            .and_then(|(i, _)| self.pair.facts[usize::from(i.as_u8())])
285            .and_then(|f| f.numbered)
286            .map_or(0, |n| n.meta_seq)
287    }
288
289    /// Entries whose `footprint_seq` is past the page's own write (only
290    /// damage writes one): the open counts them newest of all (spec §9
291    /// step 4). A rewrite of the page at a later `meta_seq` would count
292    /// them otherwise, changing the verdicts that rest on them, so a page
293    /// holding one is written only to remove it.
294    pub(crate) fn ahead(&self) -> impl Iterator<Item = (u32, u64)> + '_ {
295        let ms = self.meta_seq();
296        self.entries
297            .iter()
298            .filter(move |e| e.footprint_seq > ms)
299            .map(|e| (e.seq, e.footprint_seq))
300    }
301}
302
303/// What an unavailable table entry holds (see [`Meta2::holds`]).
304#[derive(Debug, Clone)]
305pub(crate) struct Hold {
306    pub(crate) page: usize,
307    pub(crate) seq: u32,
308    /// Its range in `allocated` (its reserved span, as the open found it),
309    /// if it has one.
310    pub(crate) span: Option<(u64, u64)>,
311    /// Its usage in `usage` (an entry that passed the entry checks).
312    pub(crate) usage: Option<(u32, u64, u64)>,
313    /// Its name in `reserved_names` (an entry of an unknown kind).
314    pub(crate) name: Option<store_io_format::meta::RegionName>,
315    /// It names space past the file's end (`cut_short`).
316    pub(crate) short: bool,
317    /// Its `footprint_seq` as settled (spec §9 step 4) and what its writes
318    /// may have touched (its header blocks and extents when its header
319    /// decoded, else its span; none for a region demoted by an overlap).
320    pub(crate) footprint_seq: u64,
321    pub(crate) own: Vec<(u64, u64)>,
322    /// A region that passed step 3 and was demoted in step 4 (by an
323    /// overlap or a name): its name and footprint, for judging it again.
324    pub(crate) demoted: Option<(store_io_format::meta::RegionName, Vec<(u64, u64)>)>,
325    /// Its entry's name, when that decodes (it counts for names in step 4).
326    pub(crate) entry_name: Option<store_io_format::meta::RegionName>,
327}
328
329impl Hold {
330    /// The region id of the entry (`page << 32 | seq`).
331    pub(crate) fn id(&self) -> u64 {
332        ((self.page as u64) << 32) | u64::from(self.seq)
333    }
334}
335
336/// A provisioning's hold, from its placement to its commit or its undo:
337/// no other provisioning takes its name or its table slot meanwhile.
338#[derive(Debug, Clone)]
339pub(crate) struct Claim {
340    pub(crate) page: usize,
341    pub(crate) seq: u32,
342    pub(crate) name: store_io_format::meta::RegionName,
343}
344
345impl Meta2 {
346    /// Marks `ranges` allocated for a provisioning or a growth that fills
347    /// them outside the metadata lock (spec §12: "choose and mark"): no
348    /// other placement takes them; free space is the complement again in a
349    /// container of `len` bytes.
350    pub(crate) fn mark(&mut self, ranges: &[(u64, u64)], len: u64) {
351        self.allocated.extend_from_slice(ranges);
352        self.marked += ranges.iter().map(|r| r.1).sum::<u64>();
353        self.rebuild_free(len);
354    }
355
356    /// Undoes [`Self::mark`] of exactly `ranges` (an operation that failed
357    /// before its commit).
358    pub(crate) fn unmark(&mut self, ranges: &[(u64, u64)], len: u64) {
359        for r in ranges {
360            if let Some(i) = self.allocated.iter().position(|a| a == r) {
361                let _gone = self.allocated.swap_remove(i);
362            }
363        }
364        let bytes = ranges.iter().map(|r| r.1).sum::<u64>();
365        debug_assert!(self.marked >= bytes, "unmarked more than was marked");
366        self.marked = self.marked.saturating_sub(bytes);
367        self.rebuild_free(len);
368    }
369
370    /// A marked operation committed: its `bytes` are now a footprint (they
371    /// stay in `allocated`).
372    pub(crate) fn settle(&mut self, bytes: u64) {
373        debug_assert!(self.marked >= bytes, "settled more than was marked");
374        self.marked = self.marked.saturating_sub(bytes);
375    }
376
377    /// Free space again, as the complement of `allocated` in a container
378    /// of `len` bytes.
379    pub(crate) fn rebuild_free(&mut self, len: u64) {
380        let mut all = self.allocated.clone();
381        self.free = crate::footprint::FreeMap::complement(self.volume.table_end(), len, &mut all);
382    }
383}
384
385/// The next `meta_seq` of the store's metadata (overflow refused).
386pub(crate) fn next_meta_seq_of(meta: &Meta) -> Result<u64, Error> {
387    let v2 = meta.v2.as_deref().ok_or_else(corrupt)?;
388    next_meta_seq(&meta.volume_pair, &v2.pages, None)
389}
390
391/// Writes table page `p`'s next copy, `payload` at `meta_seq` (chosen by
392/// the caller first, so the entries it carries can name it), durably; only
393/// a Confirmed page is ever written (spec §9 step 2). The page's state in
394/// `meta` follows once the write is durable.
395#[allow(clippy::too_many_arguments)]
396pub(crate) fn write_page<P: Platform>(
397    q: &mut Lane<P::Queue>,
398    file: &P::File,
399    pool: &store_io_buf::BufPool,
400    layout: &Layout,
401    volume: VolumeId,
402    policy: &Policy,
403    domain: &Domain,
404    meta: &mut Meta,
405    p: usize,
406    payload: &[u8],
407    meta_seq: u64,
408    owner_generation: u64,
409) -> Result<(), Error> {
410    let v2 = meta.v2.as_deref_mut().ok_or_else(corrupt)?;
411    let page = v2.pages.get_mut(p).ok_or_else(corrupt)?;
412    if page.standing != Standing::Confirmed {
413        return Err(Error::NotWritten {
414            cause: store_io_core::error::NotWrittenCause::Frozen,
415            ctx: ErrorContext::default(),
416        });
417    }
418    let pi = u32::try_from(p).map_err(|_| corrupt())?;
419    let decoded = decode_page(payload, pi, entries_per_page(layout.log2_table))
420        .map(|d| (d.header, d.entries().collect::<Vec<_>>()))
421        .map_err(|_| corrupt())?;
422    // An entry past the page's write, kept as it is, would read as an older
423    // one after this write (see `Page2::ahead`): refused before any I/O.
424    let ahead: Vec<(u32, u64)> = page.ahead().collect();
425    if let Some(kept) = decoded
426        .1
427        .iter()
428        .find(|e| ahead.contains(&(e.seq, e.footprint_seq)))
429    {
430        // Named: the entry to repair first.
431        return Err(Error::NotWritten {
432            cause: store_io_core::error::NotWrittenCause::Frozen,
433            ctx: ErrorContext {
434                region: Some(store_io_core::id::RegionId::from_raw(
435                    (u64::from(pi) << 32) | u64::from(kept.seq),
436                )),
437                ..ErrorContext::default()
438            },
439        });
440    }
441    let mut next = plan_next(&page.pair, payload, owner_generation)?;
442    next.meta_seq = meta_seq;
443    let at = pair_page(volume, layout, pi);
444    page.pair = durable_slot::<P>(q, file, pool, &at, &page.pair, &next, policy, domain)?;
445    page.header = Some(decoded.0);
446    page.entries = decoded.1;
447    Ok(())
448}
449
450/// The `meta_seq` a slot of `pair` counts for (`Valid`, or `BadPayloadCrc`
451/// with a numbered header).
452fn numbered(pair: &PairRead, slot: SlotIndex) -> Option<u64> {
453    let i = usize::from(slot.as_u8());
454    let status = if slot == SlotIndex::A {
455        pair.report.a
456    } else {
457        pair.report.b
458    };
459    match status {
460        SlotStatus::Valid(info) => Some(info.meta_seq),
461        SlotStatus::BadPayloadCrc => pair.facts[i].and_then(|f| f.numbered).map(|n| n.meta_seq),
462        _ => None,
463    }
464}
465
466/// One above every numbered slot of the volume record and the pages, except
467/// the slot `over` (pair 0 the volume record, `p + 1` page `p`) the write
468/// replaces (spec §7).
469fn next_meta_seq(
470    volume: &PairRead,
471    pages: &[Page2],
472    over: Option<(usize, SlotIndex)>,
473) -> Result<u64, Error> {
474    let pairs = core::iter::once(volume).chain(pages.iter().map(|p| &p.pair));
475    let mut max = 0u64;
476    for (i, pair) in pairs.enumerate() {
477        for slot in [SlotIndex::A, SlotIndex::B] {
478            if over == Some((i, slot)) {
479                continue;
480            }
481            if let Some(v) = numbered(pair, slot) {
482                max = max.max(v);
483            }
484        }
485    }
486    max.checked_add(1).ok_or(Error::Unsupported {
487        what: Capability::FormatVersion,
488    })
489}
490
491fn page_payload(p: u32) -> Result<Vec<u8>, Error> {
492    let mut buf = vec![0u8; store_io_format::meta2::PAGE_HEADER_LEN];
493    let n = encode_page(
494        &mut buf,
495        &PageHeader {
496            page_index: p,
497            next_seq: 0,
498            count: 0,
499        },
500        &[],
501    )
502    .map_err(|_| meta_err())?;
503    buf.truncate(n);
504    Ok(buf)
505}
506
507fn volume_payload(vm: &VolumeMeta2) -> Result<[u8; VOLUME_META2_LEN], Error> {
508    let mut buf = [0u8; VOLUME_META2_LEN];
509    let _n = vm.encode(&mut buf).map_err(|_| meta_err())?;
510    Ok(buf)
511}
512
513/// The format-2 layout for a container with blocks of `1 << log2_block`,
514/// table pages of `1 << log2_table` and room for `capacity` regions.
515pub(crate) fn layout_for(log2_block: u8, log2_table: u8, capacity: u32) -> Layout {
516    let e = u32::from(entries_per_page(log2_table)).max(1);
517    let pages = capacity
518        .min(MAX_REGION_CAPACITY)
519        .div_ceil(e)
520        .clamp(1, store_io_format::meta2::MAX_TABLE_PAGES - 1);
521    Layout {
522        log2_block,
523        log2_table,
524        format: FORMAT_2,
525        pages,
526    }
527}
528
529/// Writes a fresh format-2 container's metadata (spec §12, create): the
530/// file sized to the end of page 0's slot A (a one-page table: the whole
531/// table), page 0's slot A (generation 1, `meta_seq` 1, empty), for P > 1
532/// a full flush, the file sized for the whole table and every other page's
533/// slot A (`meta_seq` 2..P), then a full flush, the volume record's slot A (`meta_seq`
534/// P + 1), a full flush. The caller flushes the directory. Growing the file
535/// only once page 0 is durable means a crash never leaves a file past
536/// format 1's size bound without a page a later create recognises.
537#[allow(clippy::too_many_arguments)]
538pub(crate) fn create_metadata<P: Platform>(
539    platform: &P,
540    file: &P::File,
541    q: &mut Lane<P::Queue>,
542    pool: &store_io_buf::BufPool,
543    layout: &Layout,
544    volume: VolumeId,
545    created_unix_s: u64,
546) -> Result<Meta, Error> {
547    let allocate = |len: u64| {
548        platform
549            .allocate(file, len)
550            .map_err(|e| space_err(Op::Allocate, e, 0))
551    };
552    // Page 0's slot A; a one-page table is within format 1's bound whole.
553    allocate(if layout.pages == 1 {
554        layout.data_start()
555    } else {
556        layout.page_slots(0).1
557    })?;
558    let mut pages = Vec::with_capacity(layout.pages as usize);
559    for p in 0..layout.pages {
560        if p == 1 {
561            full_flush(platform, file)?;
562            allocate(layout.data_start())?;
563        }
564        let payload = page_payload(p)?;
565        let mut next = plan_next(&PairRead::blank(), &payload, 1)?;
566        next.meta_seq = u64::from(p) + 1;
567        let w = write_slot(q, file, pool, &pair_page(volume, layout, p), &next, false)?;
568        pages.push(Page2 {
569            pair: PairRead::blank().after(w),
570            standing: Standing::Confirmed,
571            header: Some(PageHeader {
572                page_index: p,
573                next_seq: 0,
574                count: 0,
575            }),
576            entries: Vec::new(),
577        });
578    }
579    full_flush(platform, file)?;
580    let vm = VolumeMeta2 {
581        base: VolumeMeta {
582            log2_block_size: layout.log2_block,
583            log2_table_slot_size: layout.log2_table,
584            device_index: 0,
585            owner_generation: 1,
586            table_offset: 2 * layout.block(),
587            created_unix_s,
588            features: 0,
589        },
590        table_pages: layout.pages,
591        entries_per_page: entries_per_page(layout.log2_table),
592        clean_close: false,
593        flags: 0,
594    };
595    let vbuf = volume_payload(&vm)?;
596    let mut next = plan_next(&PairRead::blank(), &vbuf, 1)?;
597    next.meta_seq = u64::from(layout.pages) + 1;
598    let w = write_slot(q, file, pool, &pair_volume(volume, layout), &next, false)?;
599    full_flush(platform, file)?;
600    Ok(Meta {
601        volume: vm.base,
602        volume_pair: PairRead::blank().after(w),
603        table_pair: PairRead::blank(),
604        next_region_id: 0,
605        entries: Vec::new(),
606        container_len: layout.data_start(),
607        v2: Some(Box::new(Meta2 {
608            volume: vm,
609            pages,
610            free: crate::footprint::FreeMap::complement(
611                layout.data_start(),
612                layout.data_start(),
613                &mut [],
614            ),
615            usage: Vec::new(),
616            reserved_names: Vec::new(),
617            cut_short: false,
618            allocated: Vec::new(),
619            claims: Vec::new(),
620            marked: 0,
621            holds: Vec::new(),
622            stale_extra: Vec::new(),
623        })),
624        unavailable: Vec::new(),
625        repairs: Vec::new(),
626    })
627}
628
629fn full_flush<P: Platform>(platform: &P, file: &P::File) -> Result<(), Error> {
630    platform
631        .flush_all(file)
632        .map_err(|e| Error::DurabilityUnknown {
633            op: Op::FlushAll,
634            raw: Some(e),
635            ctx: ErrorContext::default(),
636        })
637}
638
639/// What a format-2 open decided.
640pub(crate) struct Opened {
641    pub(crate) meta: Meta,
642    pub(crate) owner_generation: u64,
643    pub(crate) read_only: bool,
644    pub(crate) report: MetadataReport,
645    pub(crate) regions: Vec<std::sync::Arc<LiveRegion>>,
646    pub(crate) unavailable: Vec<UnavailableRegion>,
647}
648
649/// Decodes a format-2 volume record: a longer record, or a `features` or
650/// `flags` bit this version does not know, is a newer format (refused);
651/// anything else that fails is corruption.
652pub(crate) fn decode_volume(bytes: &[u8]) -> Result<VolumeMeta2, Error> {
653    if bytes.len() > VOLUME_META2_LEN {
654        // A longer record is a newer layout (spec §14).
655        return Err(Error::Unsupported {
656            what: Capability::FormatVersion,
657        });
658    }
659    let vm = VolumeMeta2::decode(bytes).map_err(|e| match e {
660        store_io_format::meta::MetaError::Field("features" | "flags") => Error::Unsupported {
661            what: Capability::FormatVersion,
662        },
663        _ => corrupt(),
664    })?;
665    // More pages than any store of this version can have: a later version's
666    // larger table, or a hostile record, refused before the open reads or
667    // holds anything per page (the format admits up to 2^30, and a sparse
668    // file of that length costs nothing). Unsupported, not corrupt: a
669    // caller must never be invited to recreate a store over it.
670    if vm.table_pages > max_table_pages(vm.base.log2_table_slot_size) {
671        return Err(Error::Unsupported {
672            what: Capability::FormatVersion,
673        });
674    }
675    Ok(vm)
676}
677
678/// The most table pages a store with table slots of `1 << log2_table` can
679/// have: what a create for [`MAX_REGION_CAPACITY`] makes.
680pub(crate) fn max_table_pages(log2_table: u8) -> u32 {
681    layout_for(12, log2_table, MAX_REGION_CAPACITY).pages
682}
683
684/// Reads a metadata pair, each slot whose read failed again once (spec
685/// §7), counting the retries.
686pub(crate) fn read_retried<Q: store_io_platform::Queue>(
687    q: &mut Lane<Q>,
688    file: &Q::File,
689    pool: &store_io_buf::BufPool,
690    at: &PairAt,
691    retried: &mut u32,
692) -> Result<PairRead, Error> {
693    let first = read_pair(q, file, pool, at)?;
694    let (pair, again) = reread_failed(q, file, pool, at, first)?;
695    *retried += u32::from(again);
696    Ok(pair)
697}
698
699/// As [`read_retried`] for every pair in `ats`, many reads in flight at
700/// once (the re-reads, rare, one at a time); in `ats`'s order.
701pub(crate) fn read_all_retried<Q: store_io_platform::Queue>(
702    q: &mut Lane<Q>,
703    file: &Q::File,
704    pool: &store_io_buf::BufPool,
705    ats: &[PairAt],
706    retried: &mut u32,
707) -> Result<Vec<PairRead>, Error> {
708    let first = read_pairs(q, file, pool, ats, usize::MAX)?;
709    let mut out = Vec::with_capacity(first.len());
710    for (at, pair) in ats.iter().zip(first) {
711        let (pair, again) = reread_failed(q, file, pool, at, pair)?;
712        *retried += u32::from(again);
713        out.push(pair);
714    }
715    Ok(out)
716}
717
718fn judge_read(p: &PairRead) -> judge::PairRead {
719    judge::PairRead {
720        a: judge::SlotRead {
721            status: p.report.a,
722            facts: p.facts[0],
723        },
724        b: judge::SlotRead {
725            status: p.report.b,
726            facts: p.facts[1],
727        },
728    }
729}
730
731/// The format-2 open after the volume record was found (spec §9): reads
732/// every page, judges the metadata, checks every region (`open2`), and only
733/// then, when writable, heals the one torn write and writes the volume
734/// record with the next owner generation: a read-only verdict from the
735/// region checks comes before anything is written.
736#[allow(clippy::too_many_arguments)]
737pub(crate) fn open_metadata<P: Platform>(
738    file: &P::File,
739    q: &mut Lane<P::Queue>,
740    pool: &store_io_buf::BufPool,
741    layout: &Layout,
742    volume: VolumeId,
743    mut vm: VolumeMeta2,
744    mut volume_pair: PairRead,
745    container_len: u64,
746    read_only: bool,
747    policy: &Policy,
748    append_window: u64,
749    header_queue: &mut dyn FnMut() -> Option<(P::Queue, usize)>,
750) -> Result<Opened, Error> {
751    if layout.data_start() > container_len {
752        return Err(corrupt());
753    }
754    let mut retried = 0u32;
755    let (again, reread) = reread_failed(q, file, pool, &pair_volume(volume, layout), volume_pair)?;
756    volume_pair = again;
757    if reread {
758        // A slot read again may be the newer winner: the record is read from
759        // it then, and must describe the same table.
760        retried += 1;
761        // A newer copy read the second time is refused, not corrupt.
762        vm = decode_volume(&crate::open::winner_payload(&volume_pair)?)?;
763        if vm.table_pages != layout.pages
764            || vm.base.log2_block_size != layout.log2_block
765            || vm.base.log2_table_slot_size != layout.log2_table
766        {
767            return Err(corrupt());
768        }
769    }
770    let mut pages = Vec::with_capacity(layout.pages as usize);
771    for p in 0..layout.pages {
772        let at = pair_page(volume, layout, p);
773        let pair = read_retried(q, file, pool, &at, &mut retried)?;
774        pages.push(Page2 {
775            pair,
776            standing: Standing::Lost,
777            header: None,
778            entries: Vec::new(),
779        });
780    }
781    let reads: Vec<judge::PairRead> = core::iter::once(&volume_pair)
782        .chain(pages.iter().map(|p| &p.pair))
783        .map(judge_read)
784        .collect();
785    let mut verdicts = vec![
786        PairVerdict {
787            standing: Standing::Lost,
788            winner: None,
789            a: SlotVerdict::Damage,
790            b: SlotVerdict::Damage,
791        };
792        reads.len()
793    ];
794    let j = judge::judge(&reads, vm.clean_close, &mut verdicts).map_err(|_| corrupt())?;
795    if j.refused {
796        return Err(Error::Unsupported {
797            what: Capability::FormatVersion,
798        });
799    }
800    let mut report = MetadataReport {
801        clean_close: j.clean,
802        volume_stale: verdicts[0].standing != Standing::Confirmed,
803        retried_reads: retried,
804        ..MetadataReport::default()
805    };
806    let mut decode_lost = false;
807    for (i, page) in pages.iter_mut().enumerate() {
808        let p = i as u32;
809        let mut standing = verdicts[i + 1].standing;
810        if standing != Standing::Lost {
811            match page.pair.payload.as_deref().map(|b| {
812                decode_page(b, p, entries_per_page(layout.log2_table))
813                    .map(|d| (d.header, d.entries().collect::<Vec<_>>()))
814            }) {
815                Some(Ok((h, entries))) => {
816                    page.header = Some(h);
817                    page.entries = entries;
818                    // A stale page (it may be accepted: its newer copy may
819                    // even read Blank), or one possibly accepted already:
820                    // ids its lost commit gave out stay given (see
821                    // `SEQ_MARGIN`).
822                    if standing == Standing::Unconfirmed || page.pair.possibly_accepted() {
823                        page.raise_next_seq();
824                    }
825                }
826                _ => {
827                    standing = Standing::Lost;
828                    decode_lost = true;
829                }
830            }
831        }
832        page.standing = standing;
833    }
834    // A page that fails the page checks is Lost, which the judgement could
835    // not see: a page's torn write is healed only when nothing else is
836    // lost (spec §7), so the heal is dropped and the torn copy is damage.
837    // Likewise for a page holding an entry past its own write: the heal's
838    // later `meta_seq` would change how the next open counts that entry
839    // (see `Page2::ahead`), so the page is left stale, never written.
840    let mut to_heal = j.heal;
841    if let Some((pair, _)) = to_heal {
842        if pair > 0 && (decode_lost || pages[pair - 1].ahead().next().is_some()) {
843            to_heal = None;
844            if pages[pair - 1].standing == Standing::Confirmed {
845                pages[pair - 1].standing = Standing::Unconfirmed;
846                // The verdicts agree with the pages from here on.
847                verdicts[pair].standing = Standing::Unconfirmed;
848            }
849        }
850    }
851    // Every candidate and damage, by slot (spec §9), from the final
852    // standings: a heal dropped above leaves damage, and a page failing the
853    // page checks its winner too.
854    for (i, v) in verdicts.iter().enumerate() {
855        let page = i.checked_sub(1).map(|p| p as u32);
856        let lost_late = page.is_some_and(|p| pages[p as usize].standing == Standing::Lost)
857            && v.standing != Standing::Lost;
858        for (slot_b, verdict) in [(false, v.a), (true, v.b)] {
859            let damage = match verdict {
860                SlotVerdict::OlderDamaged => SlotDamage::Older,
861                SlotVerdict::InFlight if to_heal.is_some_and(|(h, _)| h == i) => {
862                    SlotDamage::InFlight
863                }
864                SlotVerdict::InFlight | SlotVerdict::Damage => SlotDamage::Damage,
865                SlotVerdict::Winner if lost_late => SlotDamage::Damage,
866                SlotVerdict::Winner | SlotVerdict::Nothing => continue,
867            };
868            report.damaged_slots.push(DamagedSlot {
869                page,
870                slot_b,
871                damage,
872            });
873        }
874    }
875    for (i, page) in pages.iter().enumerate() {
876        match page.standing {
877            Standing::Unconfirmed => report.stale_pages.push(i as u32),
878            Standing::Lost | Standing::Refused => report.lost_pages.push(i as u32),
879            Standing::Confirmed => {}
880        }
881    }
882    report.frozen = !report.stale_pages.is_empty() || !report.lost_pages.is_empty();
883    // A winner with a read-only-compatible feature this version does not
884    // know may be read but never rewritten (spec §14).
885    let foreign = core::iter::once(&volume_pair)
886        .chain(pages.iter().map(|p| &p.pair))
887        .any(|p| p.report.winner_info().is_some_and(|(_, i)| !i.writable()));
888    let mut meta = Meta {
889        volume: vm.base,
890        volume_pair,
891        table_pair: PairRead::blank(),
892        next_region_id: 0,
893        entries: Vec::new(),
894        container_len,
895        v2: Some(Box::new(Meta2 {
896            volume: vm,
897            pages,
898            free: crate::footprint::FreeMap::default(),
899            usage: Vec::new(),
900            reserved_names: Vec::new(),
901            cut_short: false,
902            allocated: Vec::new(),
903            claims: Vec::new(),
904            marked: 0,
905            holds: Vec::new(),
906            stale_extra: Vec::new(),
907        })),
908        unavailable: Vec::new(),
909        repairs: Vec::new(),
910    };
911    // Steps 3-6, before anything is written.
912    let regions = {
913        let v2 = meta.v2.as_deref().ok_or_else(corrupt)?;
914        crate::open2::check_regions(
915            q,
916            file,
917            pool,
918            layout,
919            volume,
920            v2,
921            container_len,
922            append_window,
923            &mut report,
924            header_queue,
925        )?
926    };
927    if let Some(v2) = meta.v2.as_deref_mut() {
928        v2.free = regions.free;
929        v2.usage = regions.usage;
930        v2.reserved_names = regions.reserved_names;
931        v2.cut_short = regions.cut_short;
932        v2.allocated = regions.allocated;
933        v2.holds = regions.holds;
934        v2.stale_extra = regions.stale_extra;
935    }
936    let read_only = read_only || {
937        report.read_only_reason = if !j.writable {
938            Some("the volume record is damaged and a table page holds a damaged copy")
939        } else if foreign {
940            Some("the metadata carries a feature this version may read but not write")
941        } else {
942            regions.read_only_reason
943        };
944        report.read_only_reason.is_some()
945    };
946    if read_only {
947        return Ok(Opened {
948            meta,
949            owner_generation: 0,
950            read_only,
951            report,
952            regions: regions.live,
953            unavailable: regions.unavailable,
954        });
955    }
956    let og = vm
957        .base
958        .owner_generation
959        .checked_add(1)
960        .ok_or_else(corrupt)?;
961    let domain = Domain::new();
962    if let Some((pair, slot)) = to_heal {
963        heal::<P>(
964            q, file, pool, layout, volume, policy, &domain, &mut meta, pair, slot, og,
965        )?;
966        report.healed = Some(if pair == 0 {
967            Healed::VolumeRecord
968        } else {
969            Healed::Page(pair as u32 - 1)
970        });
971    }
972    write_volume::<P>(
973        q, file, pool, layout, volume, policy, &domain, &mut meta, og, false,
974    )?;
975    Ok(Opened {
976        meta,
977        owner_generation: og,
978        read_only,
979        report,
980        regions: regions.live,
981        unavailable: regions.unavailable,
982    })
983}
984
985/// Rewrites the one torn metadata write (`pair` 0 the volume record, `p + 1`
986/// page `p`; `slot` its failed slot) with the winner's payload byte for
987/// byte, at the torn copy's own `meta_seq` when it was readable (spec §7).
988#[allow(clippy::too_many_arguments)]
989fn heal<P: Platform>(
990    q: &mut Lane<P::Queue>,
991    file: &P::File,
992    pool: &store_io_buf::BufPool,
993    layout: &Layout,
994    volume: VolumeId,
995    policy: &Policy,
996    domain: &Domain,
997    meta: &mut Meta,
998    pair: usize,
999    slot: SlotIndex,
1000    og: u64,
1001) -> Result<(), Error> {
1002    let v2 = meta.v2.as_mut().ok_or_else(corrupt)?;
1003    let (at, prev) = if pair == 0 {
1004        (pair_volume(volume, layout), &meta.volume_pair)
1005    } else {
1006        let p = u32::try_from(pair - 1).map_err(|_| corrupt())?;
1007        (pair_page(volume, layout, p), &v2.pages[pair - 1].pair)
1008    };
1009    let payload = prev.payload.clone().ok_or_else(corrupt)?;
1010    let mut next = plan_next(prev, &payload, og)?;
1011    if next.index != slot {
1012        return Err(corrupt());
1013    }
1014    let own = prev.facts[usize::from(slot.as_u8())]
1015        .and_then(|f| f.numbered)
1016        .map(|n| n.meta_seq);
1017    next.meta_seq = match own {
1018        Some(m) => m,
1019        None => next_meta_seq(&meta.volume_pair, &v2.pages, Some((pair, slot)))?,
1020    };
1021    let healed = durable_slot::<P>(q, file, pool, &at, prev, &next, policy, domain)?;
1022    if pair == 0 {
1023        meta.volume_pair = healed;
1024    } else {
1025        v2.pages[pair - 1].pair = healed;
1026        v2.pages[pair - 1].standing = Standing::Confirmed;
1027    }
1028    Ok(())
1029}
1030
1031/// The bytes of page `p`'s two slots (an error naming the page).
1032pub(crate) fn page_range(layout: &Layout, p: u32) -> store_io_core::error::ByteRange {
1033    let (a, b) = layout.page_slots(p);
1034    store_io_core::error::ByteRange {
1035        start: a.min(b),
1036        end: a.max(b) + (1u64 << layout.log2_table),
1037    }
1038}
1039
1040/// Accepts stale page `p` (spec §12 `accept_page_rollback`): its winner
1041/// rewritten byte for byte into its failed slot at the next `meta_seq`,
1042/// durably, then the pair read back (retried once, §7): both slots must be
1043/// Valid with the same payload (the twin the next open will see, which
1044/// then counts the page Confirmed). On success the page is Confirmed (its
1045/// `next_seq` was raised by the open that found it stale, see
1046/// [`SEQ_MARGIN`]). Any failure after the write
1047/// poisons the store: the new copy is on the media, at a `meta_seq` this
1048/// state cannot count (its slot may read at the next open), so only the
1049/// next open knows the page.
1050#[allow(clippy::too_many_arguments)]
1051pub(crate) fn accept_page<P: Platform>(
1052    q: &mut Lane<P::Queue>,
1053    file: &P::File,
1054    pool: &store_io_buf::BufPool,
1055    layout: &Layout,
1056    volume: VolumeId,
1057    policy: &Policy,
1058    domain: &Domain,
1059    meta: &mut Meta,
1060    p: usize,
1061    og: u64,
1062) -> Result<(), Error> {
1063    let meta_seq = next_meta_seq_of(meta)?;
1064    let v2 = meta.v2.as_mut().ok_or_else(corrupt)?;
1065    let page = v2.pages.get_mut(p).ok_or_else(corrupt)?;
1066    let at = pair_page(volume, layout, u32::try_from(p).map_err(|_| corrupt())?);
1067    let payload = page.pair.payload.clone().ok_or_else(corrupt)?;
1068    let mut next = plan_next(&page.pair, &payload, og)?;
1069    next.meta_seq = meta_seq;
1070    let _written = durable_slot::<P>(q, file, pool, &at, &page.pair, &next, policy, domain)?;
1071    let mut retried = 0;
1072    let back = read_retried(q, file, pool, &at, &mut retried).and_then(|back| {
1073        if back.twin {
1074            Ok(back)
1075        } else {
1076            Err(Error::Corruption {
1077                kind: store_io_core::error::CorruptionKind::MediaError,
1078                ctx: ErrorContext {
1079                    range: Some(page_range(layout, u32::try_from(p).map_err(|_| corrupt())?)),
1080                    ..ErrorContext::default()
1081                },
1082            })
1083        }
1084    });
1085    match back {
1086        Ok(back) => {
1087            page.pair = back;
1088            page.standing = Standing::Confirmed;
1089            Ok(())
1090        }
1091        Err(e) => {
1092            domain.poison(store_io_core::error::FirstCause {
1093                op: Some(store_io_core::error::Op::Read),
1094                raw: None,
1095            });
1096            Err(e)
1097        }
1098    }
1099}
1100
1101/// Writes the volume record's next version: `owner_generation` and
1102/// `clean_close` as given, the next `meta_seq`, durably.
1103#[allow(clippy::too_many_arguments)]
1104pub(crate) fn write_volume<P: Platform>(
1105    q: &mut Lane<P::Queue>,
1106    file: &P::File,
1107    pool: &store_io_buf::BufPool,
1108    layout: &Layout,
1109    volume: VolumeId,
1110    policy: &Policy,
1111    domain: &Domain,
1112    meta: &mut Meta,
1113    owner_generation: u64,
1114    clean_close: bool,
1115) -> Result<(), Error> {
1116    let v2 = meta.v2.as_mut().ok_or_else(corrupt)?;
1117    let mut vm = v2.volume;
1118    vm.base.owner_generation = owner_generation;
1119    vm.clean_close = clean_close;
1120    let vbuf = volume_payload(&vm)?;
1121    let mut next = plan_next(&meta.volume_pair, &vbuf, owner_generation)?;
1122    next.meta_seq = next_meta_seq(&meta.volume_pair, &v2.pages, Some((0, next.index)))?;
1123    let at = pair_volume(volume, layout);
1124    meta.volume_pair =
1125        durable_slot::<P>(q, file, pool, &at, &meta.volume_pair, &next, policy, domain)?;
1126    v2.volume = vm;
1127    meta.volume = vm.base;
1128    Ok(())
1129}
1130
1131impl<P: Platform> Drop for Inner<P> {
1132    /// Format 2's clean close: once every handle is gone (so every write has
1133    /// completed), a writable, unpoisoned store records `clean_close` in a
1134    /// final durable volume-record write. Not after a panic (the in-memory
1135    /// metadata may be half-changed). Best effort: a failure leaves the
1136    /// next open to judge the store as not closed cleanly, which is safe.
1137    fn drop(&mut self) {
1138        if self.read_only
1139            || self.domain.poisoned().is_some()
1140            || self.meta.is_poisoned()
1141            || std::thread::panicking()
1142        {
1143            return;
1144        }
1145        let mut meta = lock_meta(&self.meta);
1146        if meta.v2.is_none() {
1147            return;
1148        }
1149        let mut q = self.queues.get(0);
1150        let _closed = write_volume::<P>(
1151            &mut q,
1152            &self.file,
1153            &self.pool,
1154            &self.layout,
1155            self.volume,
1156            &self.policy,
1157            &self.domain,
1158            &mut meta,
1159            self.owner_generation,
1160            true,
1161        );
1162    }
1163}
1164
1165#[cfg(all(test, not(loom)))]
1166mod tests {
1167    #![allow(clippy::unwrap_used)]
1168
1169    use super::*;
1170
1171    fn record(log2_table: u8, table_pages: u32) -> Vec<u8> {
1172        let vm = VolumeMeta2 {
1173            base: VolumeMeta {
1174                log2_block_size: 12,
1175                log2_table_slot_size: log2_table,
1176                device_index: 0,
1177                owner_generation: 1,
1178                table_offset: 2 << 12,
1179                created_unix_s: 0,
1180                features: 0,
1181            },
1182            table_pages,
1183            entries_per_page: entries_per_page(log2_table),
1184            clean_close: true,
1185            flags: 0,
1186        };
1187        volume_payload(&vm).unwrap().to_vec()
1188    }
1189
1190    /// A volume record claiming more table pages than a create for the
1191    /// largest capacity makes is refused (`Unsupported`: a later version's
1192    /// table, or hostile, never a store to recreate); the largest real one
1193    /// opens (independent review F-1).
1194    #[test]
1195    fn test_a_volume_record_past_the_largest_table_is_unsupported() {
1196        for log2_table in 12..=16u8 {
1197            let max = max_table_pages(log2_table);
1198            let real = layout_for(12, log2_table, MAX_REGION_CAPACITY).pages;
1199            assert_eq!(max, real);
1200            assert!(max > 1 && max < store_io_format::meta2::MAX_TABLE_PAGES - 1);
1201            assert!(decode_volume(&record(log2_table, max)).is_ok());
1202            for hostile in [max + 1, store_io_format::meta2::MAX_TABLE_PAGES - 1] {
1203                assert!(
1204                    matches!(
1205                        decode_volume(&record(log2_table, hostile)),
1206                        Err(Error::Unsupported {
1207                            what: Capability::FormatVersion,
1208                        })
1209                    ),
1210                    "{log2_table}: {hostile} pages"
1211                );
1212            }
1213        }
1214    }
1215}