Skip to main content

store_io_engine/
repair.rs

1//! Repairs of a format-2 store (v0.5 E6; spec §12, D-112, Q6):
2//! `repair_unavailable` releases an unavailable region's table entry (the
3//! page written without it, the commit; then free space is the complement
4//! again: the entry's span is never added back, other regions' bytes inside
5//! it stay allocated), its bytes untouched; `accept_page_rollback` makes a
6//! stale page's winner its content (whatever its lost commits held is
7//! given up), its regions writable and, once no page is stale, allocation
8//! free again.
9
10use store_io_core::error::{Capability, Error, ErrorContext, Named, NotWrittenCause};
11use store_io_core::id::RegionId;
12use store_io_format::judge::Standing;
13use store_io_format::meta2::{PAGE_HEADER_LEN, PageHeader, encode_page};
14use store_io_platform::Platform;
15
16use crate::io::not_written;
17use crate::report::Repair;
18use crate::store::*;
19
20/// Whether removing the entry `removing` (a repair of an unavailable one,
21/// or a release of a live region) would lift a verdict of the open at the
22/// next one (spec §9 step 4): a region demoted by an overlap or a name
23/// that would no longer be, or a live region found possibly superseded
24/// that would no longer be. The rule is judged again over what remains:
25/// the live regions' footprints and every unavailable entry's (a region
26/// demoted by step 4 counts as usable there; one that failed step 3 by
27/// what it may have written). Returns the first such region. Nothing to
28/// judge (no region demoted, none superseded: the common case) costs a
29/// scan of the holds and the live list only.
30pub(crate) fn would_lift<P: Platform>(
31    store: &Store<P>,
32    v2: &crate::v2::Meta2,
33    removing: u64,
34) -> Option<RegionId>
35where
36    P::Queue: Send,
37{
38    use crate::footprint::{Unavailable as Gone, Usable, settle};
39    let live = store
40        .inner
41        .regions
42        .lock()
43        .unwrap_or_else(std::sync::PoisonError::into_inner);
44    let demoted = v2
45        .holds
46        .iter()
47        .any(|h| h.demoted.is_some() && h.id() != removing);
48    let superseded = live.iter().any(|r| r.superseded && r.id.get() != removing);
49    if !demoted && !superseded {
50        return None;
51    }
52    let block = store.inner.layout.block();
53    // Live regions' footprints and sequences, as their entries stand now.
54    let seq_of = |id: u64| {
55        v2.pages
56            .get(usize::try_from(id >> 32).ok()?)?
57            .entries
58            .iter()
59            .find(|e| e.seq == (id & 0xFFFF_FFFF) as u32)
60            .map(|e| e.footprint_seq)
61    };
62    // (id, superseded now, demoted now).
63    let mut usable_ids: Vec<(u64, bool, bool)> = Vec::new();
64    let mut names: Vec<String> = Vec::new();
65    let mut seqs: Vec<u64> = Vec::new();
66    let mut footprints: Vec<Vec<(u64, u64)>> = Vec::new();
67    for r in live.iter().filter(|r| r.id.get() != removing) {
68        let mut f = vec![(r.header_at[0], block), (r.header_at[1], block)];
69        f.extend(r.map.extents());
70        // A live region's entry is always on its page under the metadata
71        // lock; were it not, judging it is not possible: refused.
72        let Some(seq) = seq_of(r.id.get()) else {
73            return Some(r.id);
74        };
75        usable_ids.push((r.id.get(), r.superseded, false));
76        names.push(r.name.as_str().to_owned());
77        seqs.push(seq);
78        footprints.push(f);
79    }
80    drop(live);
81    for h in v2.holds.iter().filter(|h| h.id() != removing) {
82        if let Some((name, ranges)) = &h.demoted {
83            usable_ids.push((h.id(), false, true));
84            names.push(name.as_str().to_owned());
85            seqs.push(h.footprint_seq);
86            footprints.push(ranges.clone());
87        }
88    }
89    let usable: Vec<Usable<'_>> = (0..usable_ids.len())
90        .map(|i| Usable {
91            name: &names[i],
92            seq: seqs[i],
93            ranges: &footprints[i],
94        })
95        .collect();
96    let gone: Vec<Gone<'_>> = v2
97        .holds
98        .iter()
99        .filter(|h| h.id() != removing && h.demoted.is_none())
100        .map(|h| Gone {
101            seq: h.footprint_seq,
102            own: &h.own,
103            name: h
104                .entry_name
105                .as_ref()
106                .map(store_io_format::meta::RegionName::as_str),
107        })
108        .collect();
109    let again = settle(&usable, &gone);
110    usable_ids
111        .iter()
112        .zip(again)
113        .find(|((_, superseded, demoted), s)| {
114            (*demoted && !(s.overlapped || s.renamed)) || (*superseded && !s.superseded)
115        })
116        .map(|((id, _, _), _)| RegionId::from_raw(*id))
117}
118
119impl<P: Platform> Store<P>
120where
121    P::Queue: Send,
122{
123    /// Releases the table entry of an unavailable region, one that
124    /// [`Self::unavailable_regions`] lists (or, named by its id
125    /// `page << 32 | seq`, an entry of a kind this version does not know,
126    /// `report().metadata.invalid_entries`: given up deliberately). The
127    /// entry's page is written without it (durable on return); the region's
128    /// bytes are not touched, and its space becomes free where no other
129    /// region's footprint lies. Its name is free again; the repair is
130    /// recorded ([`Self::repairs`]). Container format 2.
131    ///
132    /// # Errors
133    ///
134    /// `NotFound(Region)` if `id` names no unavailable entry (a usable
135    /// region is released with `release`); `NotWritten(Overlap)`, naming a
136    /// region whose open-time verdict rests on this entry (spec §9 step 4:
137    /// a live region it supersedes, which may read another's bytes, or an
138    /// unavailable one it demoted by an overlap or a name): the entry stays
139    /// while that region does (repair a demoted one first; a superseded
140    /// one is read-only and cannot be released: the way out is a copy of
141    /// the store that leaves unavailable entries out, `copy_store`'s
142    /// `accept_stale_pages`, v0.5 E6 C4); `NotWritten(Frozen)` also for a page holding an entry
143    /// past its own write that would be kept (repair that one first, when
144    /// it can be: one that supersedes a live region cannot, and two on one
145    /// page block each other; the way out is then the copy);
146    /// `NotWritten(Frozen)` while
147    /// allocation is frozen (a table page is stale or lost: free space
148    /// cannot be trusted); `NotWritten(ReadOnly)`; `Unsupported(FormatVersion)`
149    /// for format 1; `Poisoned`; `DurabilityUnknown` if the page write
150    /// failed after submission (the store is then poisoned; the entry may or
151    /// may not be gone at the next open).
152    pub fn repair_unavailable(&self, id: RegionId) -> Result<(), Error> {
153        self.ready()?;
154        let inner = &self.inner;
155        let ctx = ErrorContext {
156            region: Some(id),
157            ..ErrorContext::default()
158        };
159        if inner.layout.format != store_io_format::slot::FORMAT_2 {
160            return Err(Error::Unsupported {
161                what: Capability::FormatVersion,
162            });
163        }
164        if inner.frozen.load(std::sync::atomic::Ordering::Acquire) {
165            return Err(not_written(NotWrittenCause::Frozen, ctx));
166        }
167        let mut meta = lock_meta(&inner.meta);
168        let (p, payload, at) = {
169            let v2 = meta.v2.as_deref().ok_or_else(corrupt)?;
170            let Some(at) = v2.holds.iter().position(|h| h.id() == id.get()) else {
171                return Err(Error::NotFound {
172                    what: Named::Region,
173                });
174            };
175            let hold = &v2.holds[at];
176            if let Some(region) = crate::repair::would_lift(self, v2, id.get()) {
177                return Err(not_written(
178                    NotWrittenCause::Overlap,
179                    ErrorContext {
180                        region: Some(region),
181                        ..ErrorContext::default()
182                    },
183                ));
184            }
185            let page = v2.pages.get(hold.page).ok_or_else(corrupt)?;
186            if page.standing != Standing::Confirmed {
187                return Err(not_written(NotWrittenCause::Frozen, ctx));
188            }
189            let ph = page.header.ok_or_else(corrupt)?;
190            let mut raws = page.entries.clone();
191            let i = raws
192                .iter()
193                .position(|e| e.seq == hold.seq)
194                .ok_or_else(corrupt)?;
195            let _removed = raws.remove(i);
196            let next = PageHeader {
197                page_index: ph.page_index,
198                // Never decreases: the id is never handed out again.
199                next_seq: ph.next_seq,
200                count: raws.len() as u16,
201            };
202            let mut buf = vec![0u8; PAGE_HEADER_LEN + 96 * raws.len()];
203            let n = encode_page(&mut buf, &next, &raws).map_err(|_| corrupt())?;
204            buf.truncate(n);
205            (hold.page, buf, at)
206        };
207        // The commit.
208        let meta_seq = crate::v2::next_meta_seq_of(&meta)?;
209        {
210            let mut q = inner.queues.get(0);
211            crate::v2::write_page::<P>(
212                &mut q,
213                &inner.file,
214                &inner.pool,
215                &inner.layout,
216                inner.volume,
217                &inner.policy,
218                &inner.domain,
219                &mut meta,
220                p,
221                &payload,
222                meta_seq,
223                inner.owner_generation,
224            )?;
225        }
226        // Committed: memory follows. Exactly what the open added for the
227        // entry is taken away; free space is the complement again.
228        let len = meta.container_len;
229        let v2 = meta.v2.as_deref_mut().ok_or_else(corrupt)?;
230        let hold = v2.holds.swap_remove(at);
231        if let Some(span) = hold.span {
232            if let Some(i) = v2.allocated.iter().position(|a| *a == span) {
233                let _gone = v2.allocated.swap_remove(i);
234            }
235        }
236        if let Some(usage) = hold.usage {
237            if let Some(i) = v2.usage.iter().position(|u| *u == usage) {
238                let _gone = v2.usage.swap_remove(i);
239            }
240            crate::space::lock_acct(&inner.acct).remove_usage(usage.0, usage.1, usage.2);
241        }
242        if let Some(name) = &hold.name {
243            if let Some(i) = v2.reserved_names.iter().position(|n| n == name) {
244                let _gone = v2.reserved_names.swap_remove(i);
245            }
246        }
247        // Growth was refused while an entry named space past the end.
248        v2.cut_short = v2.holds.iter().any(|h| h.short);
249        v2.rebuild_free(len);
250        let record = match meta.unavailable.iter().position(|u| u.id == id) {
251            Some(i) => Repair::EntryReleased {
252                region: meta.unavailable.remove(i),
253            },
254            None => Repair::InvalidEntryReleased {
255                page: (id.get() >> 32) as u32,
256                seq: (id.get() & 0xFFFF_FFFF) as u32,
257            },
258        };
259        meta.repairs.push(record);
260        Ok(())
261    }
262
263    /// Accepts the rollback of stale table pages (spec §12): for each page
264    /// of `pages` that is Unconfirmed (`report().metadata.stale_pages`),
265    /// its winner is rewritten byte for byte into its failed slot (even an
266    /// unreadable one: writing usually remaps the sector) at the next
267    /// `meta_seq`, durably, and read back; once the new copy reads back as
268    /// the winner the page counts as Confirmed: whatever its lost commits
269    /// held is given up (space they used may be handed out again) and the
270    /// extra extents counted allocated for it are free. Every page is
271    /// checked before any is written (an error from a check accepts
272    /// none). Each accepted page is recorded ([`Self::repairs`]); a
273    /// Confirmed page is left as it is.
274    ///
275    /// Once no page is stale or lost, allocation is no longer frozen
276    /// ([`Self::frozen`]) and the regions become writable (not one possibly
277    /// superseded, or with a header feature this version may not write).
278    /// Not before: a region of an accepted page may be one a lost commit
279    /// released, its space then given to a region of another stale page's
280    /// lost commit, whose bytes it would overwrite. The same holds across
281    /// a reopen: an accepted page's two slots then hold the same payload
282    /// (as after a heal), and while any page is stale or lost the open
283    /// keeps such a page's regions read-only (also once its older copy is
284    /// damaged: any Confirmed page with a damaged older copy counts). A store with a Lost page
285    /// stays frozen, the regions of the pages accepted read-only: it is
286    /// copied (`copy_store`). An accepted page's `next_seq` counts higher
287    /// (raised by the open that found it stale and by each open while its
288    /// trace lasts, written by its next commit): the region ids its lost
289    /// commit gave out are not given out
290    /// again (unless more than 4,096 provisionings failed on that page
291    /// between its last two commits). Container format 2.
292    ///
293    /// # Errors
294    ///
295    /// `NotWritten(NotReady)` for a Lost page, its slots named (no winner
296    /// to keep); `NotWritten(OutOfBounds)` for a page the table does not
297    /// have; `NotWritten(Frozen)` for a page holding an entry whose
298    /// `footprint_seq` is past the page's own write, the entry named (the
299    /// rewrite would change how the next open counts it, and no repair
300    /// runs while allocation is frozen: such a store is copied).
301    /// `Corruption(MediaError)` if the page does not read back with both
302    /// slots Valid and the same, and `Io` if it does not read: the write was
303    /// durable, so the store is poisoned (what the next open finds is the
304    /// page's state: Confirmed if the new copy reads, else stale, to be
305    /// accepted again). `NotWritten(ReadOnly)`; `Unsupported(FormatVersion)`
306    /// for format 1; `Poisoned`; `DurabilityUnknown` if the write failed
307    /// after submission (the store poisoned; at the next open the page is
308    /// still stale, or Confirmed if the new copy reached the media).
309    pub fn accept_page_rollback(&self, pages: &[u32]) -> Result<(), Error> {
310        self.ready()?;
311        let inner = &self.inner;
312        if inner.layout.format != store_io_format::slot::FORMAT_2 {
313            return Err(Error::Unsupported {
314                what: Capability::FormatVersion,
315            });
316        }
317        let mut meta = lock_meta(&inner.meta);
318        let mut todo: Vec<(u32, usize)> = Vec::new();
319        {
320            let v2 = meta.v2.as_deref().ok_or_else(corrupt)?;
321            for &page in pages {
322                let p = usize::try_from(page).map_err(|_| corrupt())?;
323                let Some(pg) = v2.pages.get(p) else {
324                    return Err(not_written(
325                        NotWrittenCause::OutOfBounds,
326                        ErrorContext::default(),
327                    ));
328                };
329                match pg.standing {
330                    Standing::Confirmed => continue,
331                    Standing::Unconfirmed => {}
332                    Standing::Lost | Standing::Refused => {
333                        return Err(not_written(
334                            NotWrittenCause::NotReady,
335                            ErrorContext {
336                                range: Some(crate::v2::page_range(&inner.layout, page)),
337                                ..ErrorContext::default()
338                            },
339                        ));
340                    }
341                }
342                if let Some((seq, _)) = pg.ahead().next() {
343                    return Err(not_written(
344                        NotWrittenCause::Frozen,
345                        ErrorContext {
346                            region: Some(RegionId::from_raw(
347                                (u64::from(page) << 32) | u64::from(seq),
348                            )),
349                            ..ErrorContext::default()
350                        },
351                    ));
352                }
353                if !todo.iter().any(|&(_, at)| at == p) {
354                    todo.push((page, p));
355                }
356            }
357        }
358        for (page, p) in todo {
359            {
360                let mut q = inner.queues.get(0);
361                crate::v2::accept_page::<P>(
362                    &mut q,
363                    &inner.file,
364                    &inner.pool,
365                    &inner.layout,
366                    inner.volume,
367                    &inner.policy,
368                    &inner.domain,
369                    &mut meta,
370                    p,
371                    inner.owner_generation,
372                )?;
373            }
374            // Confirmed: the extra extents counted for it are free (a
375            // growth beyond capacity that never committed), free space is
376            // the complement again.
377            let len = meta.container_len;
378            let v2 = meta.v2.as_deref_mut().ok_or_else(corrupt)?;
379            let freed: Vec<(u64, u64)> = v2
380                .stale_extra
381                .iter()
382                .filter(|(at, _, _)| *at == p)
383                .map(|&(_, _, r)| r)
384                .collect();
385            v2.stale_extra.retain(|(at, _, _)| *at != p);
386            for range in &freed {
387                if let Some(i) = v2.allocated.iter().position(|a| a == range) {
388                    let _gone = v2.allocated.swap_remove(i);
389                }
390            }
391            v2.rebuild_free(len);
392            meta.repairs.push(Repair::PageAccepted { page });
393        }
394        // No page stale or lost: every region the open served read-only for
395        // its page is writable, and allocation unfrozen.
396        let v2 = meta.v2.as_deref().ok_or_else(corrupt)?;
397        if v2.pages.iter().all(|pg| pg.standing == Standing::Confirmed) {
398            for r in inner
399                .regions
400                .lock()
401                .unwrap_or_else(std::sync::PoisonError::into_inner)
402                .iter()
403                .filter(|r| !r.superseded && !r.foreign)
404            {
405                r.read_only
406                    .store(false, std::sync::atomic::Ordering::Release);
407            }
408            inner
409                .frozen
410                .store(false, std::sync::atomic::Ordering::Release);
411        }
412        Ok(())
413    }
414}