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}