Skip to main content

store_io_engine/
copy.rs

1//! Copying a store into a fresh format-2 one (v0.5 E5 C1; PLANNING r4 "The
2//! copy tool", D-116): the way a format-1 store moves to format 2, and the
3//! way out of a format-2 store that needs compacting.
4//!
5//! The source is opened read-only (it never heals and never writes its
6//! volume record). A source with unavailable regions, table entries that do
7//! not decode, or a stale or lost table page is refused, as is one holding
8//! a slot object larger than a format-2 slot takes, before anything is
9//! created; with [`CopyOptions::accept_stale_pages`] such a source is
10//! copied as far as it can be (spec §12 "What `copy_store` copies"): the
11//! regions of a stale page in full, what is left out or uncertain
12//! reported. The target directory's copy lock ([`COPY_LOCK`], held for the
13//! whole copy) keeps two copies into one directory apart. The target is
14//! created there under a temporary container name, every region recreated
15//! with its name, kind, data size, cap, tag, region generation, fill
16//! pattern and fill key (laid out anew, one extent each) and its data
17//! copied (an append or page region's as its fill, durable before its
18//! header, D-137; a stale page's full copies made durable by one barrier
19//! after them all), closed, and only then renamed into
20//! place by a rename that never replaces (a store created there meanwhile
21//! is kept, the copy refused): a crash leaves no store under the target
22//! name, or the whole copy.
23
24use std::ops::ControlFlow;
25use std::path::Path;
26
27use store_io_core::errno::{is_already_exists, is_lock_held, is_not_found};
28use store_io_core::error::{Error, ErrorContext, Named, NotWrittenCause, Op};
29use store_io_core::id::RegionId;
30use store_io_format::judge::Standing;
31use store_io_format::meta::{FillPattern, REGION_META_LEN, RegionKind, RegionMeta};
32use store_io_format::meta2::{FLAG_CAPPED, decode_region_header, max_object};
33use store_io_format::slot::FORMAT_2;
34use store_io_platform::{FileMode, FileName, IoOp, Platform};
35
36use crate::exec::{Ran, clear_stale, run};
37use crate::settle::settle_read;
38
39use crate::store::{CONTAINER, LiveRegion, Store, StoreOptions, io, lock_meta};
40use crate::{RegionOptions, ScanItem};
41
42/// The temporary name a copy's target is built under (no live store ever
43/// has it: one left by a crashed copy is removed by the next).
44pub const COPYING: &str = "store.sio.copying";
45
46/// The file in a copy's target directory whose lock a copy holds from
47/// before it looks for a store there until after its rename (created by
48/// the first copy and kept: removing a lock file races its next user).
49pub const COPY_LOCK: &str = "store.sio.copy-lock";
50
51/// How [`copy_store`] builds its target.
52#[derive(Debug, Clone, Default)]
53pub struct CopyOptions {
54    /// The target store's options (trust, buffers, queues...). Its block
55    /// size is the source's whatever this says, and its table holds at
56    /// least the source's regions; the container format is 2.
57    pub store: StoreOptions,
58    /// Copy a source the open left frozen (a stale or lost table page) or
59    /// with unavailable regions or entries this version cannot read,
60    /// instead of refusing it (spec §12, "What `copy_store` copies"; the
61    /// way out of a store no repair can mend in place):
62    /// - every usable region, by its recorded data size;
63    /// - a usable region of a stale page **in full**: its whole capacity,
64    ///   plus the extra extent its header lists when that overlaps no other
65    ///   region's footprint and no reserved span (a growth whose commit may
66    ///   be the page's lost one); the target's data size covers all of it,
67    ///   and its recorded data size is reported
68    ///   ([`CopyReport::verified_up_to`]): the bytes past it may never
69    ///   have been written, may be the newest, or (where no check can
70    ///   tell: a growth another damaged header never listed, an uncommitted
71    ///   one of a confirmed page's region) may never have been this
72    ///   region's;
73    /// - every stale page reported ([`CopyReport::stale_pages`]): its
74    ///   newest commit is given up, so a region it created is missing and
75    ///   one it released is back;
76    /// - unavailable regions and unreadable entries left out, reported
77    ///   ([`CopyReport::omitted`]); a lost page's regions are unknown,
78    ///   reported by page ([`CopyReport::lost_pages`]);
79    /// - a possibly superseded region copied and reported
80    ///   ([`CopyReport::superseded`]): it may read another region's bytes.
81    ///
82    /// Default false: such a source is refused.
83    pub accept_stale_pages: bool,
84}
85
86/// What [`copy_store`] copied.
87#[derive(Debug, Clone, PartialEq, Eq)]
88pub struct CopyReport {
89    /// Regions recreated in the target (slots included).
90    pub regions: usize,
91    /// Data bytes copied (regions' data sizes and slots' objects).
92    pub bytes: u64,
93    /// The source's container format.
94    pub source_format: u16,
95    /// With `accept_stale_pages`: the source's table entries left out
96    /// (unavailable regions, entries of a kind or name this version cannot
97    /// read), by id; the source's report says why.
98    pub omitted: Vec<RegionId>,
99    /// With `accept_stale_pages`: the source's lost table pages (no copy
100    /// of them reads): their regions are unknown, none copied; a region
101    /// they may have taken the bytes of is listed in
102    /// [`Self::superseded`], and no extra extent is copied.
103    pub lost_pages: Vec<u32>,
104    /// With `accept_stale_pages`: the source's stale table pages (a newer
105    /// copy damaged): each one's newest commit is given up, so a region
106    /// that commit created is missing from the copy and one it released is
107    /// in it, whatever regions the page holds.
108    pub stale_pages: Vec<u32>,
109    /// With `accept_stale_pages`: each region of a stale page, copied in
110    /// full, with its recorded data size (name, bytes): only that much is
111    /// known to be the region's acknowledged data (unless it is also listed
112    /// in [`Self::superseded`]).
113    pub verified_up_to: Vec<(String, u64)>,
114    /// With `accept_stale_pages`: the regions copied that may hold another
115    /// region's bytes, by name: possibly superseded (spec §9 step 4:
116    /// another region's newer footprint may cover them), or of a stale or
117    /// possibly accepted page while another page is stale or lost (D-130:
118    /// a given-up commit may have released one, and another given-up
119    /// commit handed its space to a region it created). The source held
120    /// each read-only; the copy's is writable.
121    pub superseded: Vec<String>,
122}
123
124/// What a recreated region keeps of its source (internal: for the
125/// target's provisioning).
126#[derive(Debug, Clone, Copy)]
127pub(crate) struct CopyAttrs {
128    pub(crate) generation: u64,
129    pub(crate) fill: FillPattern,
130    pub(crate) fill_key: [u8; 16],
131    pub(crate) tag: u32,
132}
133
134/// A source region, as the copy recreates it.
135struct Facts {
136    name: String,
137    kind: RegionKind,
138    /// The target's data size (the source's, or a full copy's length).
139    data_size: u64,
140    /// Its cap (format 2's capped regions): the target is capped there too.
141    cap: Option<u64>,
142    attrs: CopyAttrs,
143    /// A slot's committed object, if any.
144    object: Option<Vec<u8>>,
145    /// A region of a stale page, copied in full: the container ranges, in
146    /// data order (its capacity, then its extra extent if taken), and its
147    /// recorded data size.
148    full: Option<(Vec<(u64, u64)>, u64)>,
149    /// Possibly superseded (spec §9 step 4).
150    superseded: bool,
151    /// The source region (a full copy reads its runs and extra extent).
152    source: std::sync::Arc<LiveRegion>,
153}
154
155/// The largest piece a copy's reader hands the fill (a scan buffer is cut
156/// into pieces this size or smaller), and how many it keeps queued (D-137):
157/// at most `FEED_DEPTH + 2` pieces exist at once (queued, the one being
158/// built, the one being consumed), 10 MiB whatever `max_io` is.
159const FEED_PIECE: usize = 1 << 20;
160/// See [`FEED_PIECE`].
161const FEED_DEPTH: usize = 8;
162
163/// A copied region's bytes, in order, from the source's scan on another
164/// thread (D-137): the scan's reads stay in flight while the fill writes.
165struct Feed {
166    pieces: std::sync::mpsc::Receiver<Result<(u64, Vec<u8>), Error>>,
167    spent: std::sync::mpsc::Sender<Vec<u8>>,
168    /// The piece being consumed and how much of it is.
169    current: Vec<u8>,
170    start: u64,
171    used: usize,
172    /// The source region, named in an error.
173    region: RegionId,
174}
175
176impl Feed {
177    /// Starts the reader of `r` (its region offsets `[0, len)`) on a
178    /// thread of `s`. The thread ends when the scan does, on the first
179    /// error (sent), or once the returned `Feed` is dropped.
180    ///
181    /// # Errors
182    ///
183    /// `Io { op: Queue }` if the thread cannot be started.
184    fn start<'s, P: Platform>(
185        s: &'s std::thread::Scope<'s, '_>,
186        src: &'s Store<P>,
187        r: &'s LiveRegion,
188        len: u64,
189    ) -> Result<(std::thread::ScopedJoinHandle<'s, Result<(), Error>>, Self), Error>
190    where
191        P::Queue: Send,
192    {
193        let (put, pieces) = std::sync::mpsc::sync_channel(FEED_DEPTH);
194        let (spent, back) = std::sync::mpsc::channel::<Vec<u8>>();
195        let handle = std::thread::Builder::new()
196            .name("store-io-copy".into())
197            .spawn_scoped(s, move || {
198                let mut fail = None;
199                let scanned = src.scan_region(r, 0, len, false, |item| match item {
200                    ScanItem::Data { offset, bytes } => {
201                        for (i, part) in bytes.chunks(FEED_PIECE).enumerate() {
202                            let at = offset + (i * FEED_PIECE) as u64;
203                            let mut v = back.try_recv().unwrap_or_default();
204                            v.clear();
205                            // Memory the pool does not account for: a failed
206                            // allocation is reported, never an abort.
207                            if v.try_reserve_exact(part.len()).is_err() {
208                                fail = Some(crate::io::not_written(
209                                    NotWrittenCause::PoolExhausted,
210                                    crate::io::ctx_range(r, at, at + part.len() as u64),
211                                ));
212                                return ControlFlow::Break(());
213                            }
214                            v.extend_from_slice(part);
215                            if put.send(Ok((at, v))).is_err() {
216                                // The fill stopped: so does the scan.
217                                return ControlFlow::Break(());
218                            }
219                        }
220                        ControlFlow::Continue(())
221                    }
222                    ScanItem::Unreadable { start, end } => {
223                        fail = Some(Error::Corruption {
224                            kind: store_io_core::error::CorruptionKind::MediaError,
225                            ctx: crate::io::ctx_range(r, start, end),
226                        });
227                        ControlFlow::Break(())
228                    }
229                });
230                let failed = match (scanned, fail) {
231                    (_, Some(e)) | (Err(e), None) => Some(e),
232                    (Ok(_), None) => None,
233                };
234                if let Some(e) = failed {
235                    // The fill may already have stopped: then nobody reads
236                    // it, and its own error stands.
237                    let _sent = put.send(Err(e.clone()));
238                    return Err(e);
239                }
240                Ok(())
241            })
242            .map_err(|e| Error::Io {
243                op: Op::Queue,
244                raw: os_error(&e),
245                ctx: ErrorContext {
246                    region: Some(r.id),
247                    ..ErrorContext::default()
248                },
249            })?;
250        Ok((
251            handle,
252            Self {
253                pieces,
254                spent,
255                current: Vec::new(),
256                start: 0,
257                used: 0,
258                region: r.id,
259            },
260        ))
261    }
262
263    /// Fills `dst` with the region's bytes from offset `index` (the fill
264    /// asks for them in order, with no gap).
265    fn read(&mut self, index: u64, dst: &mut [u8]) -> Result<(), Error> {
266        let mut done = 0usize;
267        while done < dst.len() {
268            if self.used == self.current.len() {
269                let (start, piece) = match self.pieces.recv() {
270                    Ok(Ok(p)) => p,
271                    Ok(Err(e)) => return Err(e),
272                    // The scan ended before the region did: bytes its map
273                    // says exist are not there.
274                    Err(_) => return Err(self.wrong(index + done as u64, index + dst.len() as u64)),
275                };
276                let old = std::mem::replace(&mut self.current, piece);
277                let _recycled = self.spent.send(old);
278                self.start = start;
279                self.used = 0;
280            }
281            // In order and without a gap, or the copy is wrong.
282            if self.start + self.used as u64 != index + done as u64 {
283                return Err(self.wrong(index + done as u64, index + dst.len() as u64));
284            }
285            let n = (self.current.len() - self.used).min(dst.len() - done);
286            dst[done..done + n].copy_from_slice(&self.current[self.used..self.used + n]);
287            self.used += n;
288            done += n;
289        }
290        Ok(())
291    }
292
293    /// The source's bytes `[start, end)` did not arrive as its map says.
294    fn wrong(&self, start: u64, end: u64) -> Error {
295        let mut e = crate::store::corrupt();
296        if let Error::Corruption { ctx, .. } = &mut e {
297            *ctx = ErrorContext {
298                region: Some(self.region),
299                range: Some(store_io_core::error::ByteRange { start, end }),
300            };
301        }
302        e
303    }
304}
305
306/// A thread's start failure as an [`OsError`](store_io_core::error::OsError).
307fn os_error(e: &std::io::Error) -> store_io_core::error::OsError {
308    use store_io_core::error::{OsError, OsErrorSource};
309    OsError {
310        code: e.raw_os_error().unwrap_or(0),
311        source: if cfg!(windows) {
312            OsErrorSource::Win32
313        } else {
314            OsErrorSource::Errno
315        },
316    }
317}
318
319/// Copies the store in `from` into a new format-2 store in `to`, whose
320/// directory must hold no store. See the module docs.
321///
322/// # Errors
323///
324/// As [`Store::open_readonly`] for the source and [`Store::create`] for
325/// the target; `Locked` while a writer holds `from` open or another copy
326/// into `to` runs;
327/// `AlreadyExists` if `to` holds a container file (any `store.sio`, even
328/// one a crashed create left empty, which [`Store::create`] would take
329/// over: remove it to copy there), or one appears there during the copy
330/// (kept: the copy's temporary store is removed); `NotWritten(NotReady)`
331/// for a source with unavailable regions or table entries that do not
332/// decode (the first in the error's context; the source's report lists
333/// them all), `NotWritten(Frozen)` for one with a stale or lost table
334/// page (both unless [`CopyOptions::accept_stale_pages`]: then copied as
335/// far as they can be; a full copy's read fails as a region read does:
336/// `Corruption(MediaError)` naming the region and range, `Io`,
337/// `NotWritten(Interrupted | QueueFull)`, or `Corruption(Metadata)` for a
338/// read cut short, `NotWritten(PoolExhausted)`), `NotWritten(TooLarge)` for
339/// a slot object larger than a format-2
340/// slot holds (that region in the context), all before anything is
341/// created; `Io` if whether `to` holds a store cannot be told (any failure
342/// to look but "not found"), before anything but the target directory
343/// (and, on the second look under the lock, the copy lock's file) is
344/// created;
345/// `NotWritten(Misaligned)` if the target's device needs larger blocks
346/// than the source's, or a region's data size is not whole target blocks
347/// (naming the source's region, before that region is provisioned);
348/// `Io { op: Queue }` if a region's reader thread cannot be started; a
349/// copied region's read errors as a scan's (`Corruption(MediaError)`
350/// naming the source's region and range, also for a read cut short),
351/// `NotWritten(PoolExhausted)` if the reader's pieces cannot be allocated;
352/// then any error of provisioning, reading or writing (the target left
353/// under its temporary name, removed by the next copy into `to`);
354/// `DurabilityUnknown` if the rename or the directory flush after it
355/// failed: the copy, whole, may or may not be in place under the target
356/// name (open it, or copy again: `AlreadyExists` means it is).
357pub fn copy_store<P: Platform + Clone>(
358    platform: P,
359    from: &Path,
360    to: &Path,
361    opts: CopyOptions,
362) -> Result<CopyReport, Error>
363where
364    P::Queue: Send,
365{
366    let src = Store::open_readonly(platform.clone(), from, opts.store.clone())?;
367    let report = src.report();
368    let refused = |cause, region| Error::NotWritten {
369        cause,
370        ctx: ErrorContext {
371            region,
372            ..ErrorContext::default()
373        },
374    };
375    let accept = opts.accept_stale_pages;
376    let (mut omitted, mut lost_pages, mut stale_pages) = (Vec::new(), Vec::new(), Vec::new());
377    if accept {
378        // Every entry the open holds space for without serving it: the
379        // unavailable regions and the entries of an unknown kind (format
380        // 2's holds are the whole list; format 1 has only the former).
381        omitted = src.omitted_for_copy();
382        lost_pages.clone_from(&report.metadata.lost_pages);
383        stale_pages.clone_from(&report.metadata.stale_pages);
384    } else {
385        // The source's state now (a read-only open: what its open found).
386        if let Some(u) = src.unavailable_regions().first() {
387            return Err(refused(NotWrittenCause::NotReady, Some(u.id)));
388        }
389        // An entry whose kind or name does not decode (a newer release's)
390        // is a region the copy cannot recreate (the list may be truncated:
391        // any).
392        if let Some(&(p, s)) = report.metadata.invalid_entries.first() {
393            let id = RegionId::from_raw((u64::from(p) << 32) | u64::from(s));
394            return Err(refused(NotWrittenCause::NotReady, Some(id)));
395        }
396        if src.frozen() {
397            return Err(refused(NotWrittenCause::Frozen, None));
398        }
399    }
400    let block = report.block_size;
401    let log2 = block.trailing_zeros() as u8;
402    let source_format = report.format;
403    let regions = src.regions_snapshot();
404    let mut facts = Vec::with_capacity(regions.len());
405    let (mut verified_up_to, mut superseded) = (Vec::new(), Vec::new());
406    for r in &regions {
407        let f = src.facts_for_copy(r, &regions)?;
408        if let Some((_, recorded)) = &f.full {
409            verified_up_to.push((f.name.clone(), *recorded));
410        }
411        if f.superseded {
412            superseded.push(f.name.clone());
413        }
414        if f.object
415            .as_ref()
416            .is_some_and(|o| o.len() > max_object(log2))
417        {
418            return Err(refused(NotWrittenCause::TooLarge, Some(r.id)));
419        }
420        facts.push(f);
421    }
422    let dir = platform
423        .open_dir(to, true)
424        .map_err(|raw| io(Op::Create, raw))?;
425    let final_name = name(CONTAINER)?;
426    let temp = name(COPYING)?;
427    let holds_store = || match platform.open_file(&dir, &final_name, FileMode::ReadOnly) {
428        Ok(_) => Err(Error::AlreadyExists { what: Named::Store }),
429        Err(raw) if is_not_found(raw) => Ok(()),
430        Err(raw) => Err(io(Op::Open, raw)),
431    };
432    holds_store()?;
433    // The copy lock, then (under it) no store there and a crashed copy's
434    // leftover removed: no other copy can touch the temporary name until
435    // this one's rename is done.
436    let lock_name = name(COPY_LOCK)?;
437    let lock_file = match platform.create_file(&dir, &lock_name) {
438        Ok(f) => f,
439        Err(raw) if is_already_exists(raw) => platform
440            .open_file(&dir, &lock_name, FileMode::ReadWrite)
441            .map_err(|raw| io(Op::Open, raw))?,
442        Err(raw) => return Err(io(Op::Create, raw)),
443    };
444    let _lock = platform.lock_exclusive(&lock_file).map_err(|raw| {
445        if is_lock_held(raw) {
446            Error::Locked
447        } else {
448            io(Op::Lock, raw)
449        }
450    })?;
451    holds_store()?;
452    match platform.unlink(&dir, &temp) {
453        Ok(()) => {}
454        Err(raw) if is_not_found(raw) => {}
455        Err(raw) => return Err(io(Op::Unlink, raw)),
456    }
457    let mut target_opts = opts.store.clone();
458    target_opts.container_format = FORMAT_2;
459    target_opts.block_size = Some(block as u32);
460    target_opts.region_capacity = target_opts
461        .region_capacity
462        .max(u32::try_from(facts.len()).unwrap_or(u32::MAX));
463    let mut bytes = 0u64;
464    {
465        let dst = Store::create_named(platform.clone(), to, target_opts, &temp)?;
466        // A device that needs larger blocks than the source's would round
467        // every size up: refused (the temporary store is removed by the
468        // next copy).
469        if dst.report().block_size != block {
470            return Err(refused(NotWrittenCause::Misaligned, None));
471        }
472        for f in &facts {
473            bytes += dst.recreate(&src, f)?;
474        }
475        // One barrier for every byte not written as a fill (a stale page's
476        // full copies; the clean close is best effort and reports nothing).
477        dst.flush_all_accounted()?;
478        // Closed here (the drop writes the clean-close record).
479    }
480    // Into place: the rename is the commit of the copy, and never replaces
481    // a store another process created meanwhile.
482    let file = platform
483        .open_file(&dir, &temp, FileMode::ReadWrite)
484        .map_err(|raw| io(Op::Open, raw))?;
485    match platform.rename_noreplace(&dir, &temp, &final_name, &file) {
486        Ok(()) => {}
487        Err(raw) if is_already_exists(raw) => {
488            drop(file);
489            // Best effort: the next copy removes it otherwise.
490            if platform.unlink(&dir, &temp).is_ok() {
491                let _synced = platform.sync_dir(&dir);
492            }
493            return Err(Error::AlreadyExists { what: Named::Store });
494        }
495        Err(raw) => {
496            return Err(Error::DurabilityUnknown {
497                op: Op::Rename,
498                raw: Some(raw),
499                ctx: ErrorContext::default(),
500            });
501        }
502    }
503    drop(file);
504    platform
505        .sync_dir(&dir)
506        .map_err(|raw| Error::DurabilityUnknown {
507            op: Op::SyncDir,
508            raw: Some(raw),
509            ctx: ErrorContext::default(),
510        })?;
511    Ok(CopyReport {
512        regions: facts.len(),
513        bytes,
514        source_format,
515        omitted,
516        lost_pages,
517        stale_pages,
518        verified_up_to,
519        superseded,
520    })
521}
522
523fn name(s: &str) -> Result<FileName, Error> {
524    FileName::new(s).map_err(|_| Error::NotWritten {
525        cause: NotWrittenCause::InvalidName,
526        ctx: ErrorContext::default(),
527    })
528}
529
530/// The copy's chunk: 1 MiB.
531const CHUNK: usize = 1 << 20;
532
533impl<P: Platform> Store<P>
534where
535    P::Queue: Send,
536{
537    /// The entries `copy_store` leaves out (`CopyReport::omitted`): format
538    /// 2's holds (every unavailable or unknown-kind entry), else the
539    /// unavailable regions.
540    fn omitted_for_copy(&self) -> Vec<RegionId> {
541        let meta = lock_meta(&self.inner.meta);
542        match meta.v2.as_deref() {
543            Some(v2) => {
544                let mut ids: Vec<RegionId> = v2
545                    .holds
546                    .iter()
547                    .map(|h| RegionId::from_raw(h.id()))
548                    .collect();
549                ids.sort_unstable_by_key(|id| id.get());
550                ids
551            }
552            None => {
553                let mut ids: Vec<RegionId> = meta.unavailable.iter().map(|u| u.id).collect();
554                ids.sort_unstable_by_key(|id| id.get());
555                ids
556            }
557        }
558    }
559
560    /// A region of a stale page, copied in full (format 2): its runs over
561    /// the whole capacity, then its extra extent when that overlaps nothing
562    /// any other bytes may belong to: the volume record and table, the
563    /// region's own header blocks and runs, every other region's (header
564    /// blocks and runs over the capacity, an extra extent), and every
565    /// unavailable entry's reserved span and possible writes; never while a
566    /// page is lost (its regions' footprints are unknown). `None` on a
567    /// confirmed page.
568    fn full_copy(
569        &self,
570        r: &LiveRegion,
571        regions: &[std::sync::Arc<LiveRegion>],
572    ) -> Option<(Vec<(u64, u64)>, u64)> {
573        let meta = lock_meta(&self.inner.meta);
574        let v2 = meta.v2.as_deref()?;
575        let page = usize::try_from(r.id.get() >> 32).ok()?;
576        if v2.pages.get(page)?.standing != Standing::Unconfirmed {
577            return None;
578        }
579        let block = self.block();
580        let mut ranges: Vec<(u64, u64)> = r.map.extents().collect();
581        let overlaps = |(a, n): (u64, u64), (b, m): (u64, u64)| a < b + m && b < a + n;
582        let extra = v2
583            .stale_extra
584            .iter()
585            .find(|e| e.1 == r.id.get())
586            .map(|e| e.2);
587        let lost = v2
588            .pages
589            .iter()
590            .any(|p| p.standing != Standing::Confirmed && p.standing != Standing::Unconfirmed);
591        if let Some(extra) = extra.filter(|_| !lost) {
592            let mut others = regions
593                .iter()
594                .flat_map(|o| {
595                    o.map
596                        .extents()
597                        .chain(o.header_at.iter().map(|&h| (h, block)))
598                        .collect::<Vec<_>>()
599                })
600                .chain(core::iter::once((0, self.inner.layout.data_start())))
601                .chain(v2.holds.iter().filter_map(|h| h.span))
602                .chain(v2.holds.iter().flat_map(|h| h.own.iter().copied()))
603                .chain(
604                    v2.stale_extra
605                        .iter()
606                        .filter(|e| e.1 != r.id.get())
607                        .map(|e| e.2),
608                );
609            if !others.any(|o| overlaps(extra, o)) {
610                ranges.push(extra);
611            }
612        }
613        Some((ranges, r.map.len()))
614    }
615
616    /// Reads `out.len()` bytes of the container at `offset` (both whole
617    /// blocks), whatever `r`'s data size says: a copy's full region, `at`
618    /// the region offset they stand for (named in an error, as a region
619    /// read's verdict is: `settle_read`).
620    fn read_raw(
621        &self,
622        r: &LiveRegion,
623        mut at: u64,
624        mut offset: u64,
625        out: &mut [u8],
626    ) -> Result<(), Error> {
627        let mut lane = self.inner.queues.get(0);
628        clear_stale(&mut lane).map_err(|raw| io(Op::Read, raw))?;
629        let chunk = self.chunk();
630        for piece in out.chunks_mut(chunk) {
631            let c = crate::io::ctx_range(r, at, at + piece.len() as u64);
632            let buf = self.take(piece.len(), c)?;
633            let op = IoOp::Read {
634                file: &self.inner.file,
635                offset,
636                buf,
637            };
638            let (got, result) = match run(&mut lane, op) {
639                Ok(Ran::Done { buf, result }) => (buf, result),
640                // The wait failed with the read in flight: the queue's
641                // failure, no verdict on the media.
642                Ok(Ran::Abandoned(raw)) | Err((_, Some(raw))) => return Err(io(Op::Read, raw)),
643                Err((_, None)) => {
644                    return Err(crate::io::not_written(NotWrittenCause::QueueFull, c));
645                }
646            };
647            let n = settle_read(self, r, at, at + piece.len() as u64, got.as_ref(), result)?;
648            match got {
649                Some(b) if n == piece.len() => piece.copy_from_slice(&b.as_slice()[..n]),
650                // Short: bytes the region's runs say exist are not there.
651                _ => return Err(crate::store::corrupt()),
652            }
653            offset += piece.len() as u64;
654            at += piece.len() as u64;
655        }
656        Ok(())
657    }
658
659    /// Whether `r`, on a stale or possibly accepted page while another page
660    /// is too (or lost), may hold another region's bytes (D-130): each
661    /// such page's newest commit may be given up, one releasing `r`, the
662    /// other handing its space to a region it created.
663    fn at_risk(&self, r: &LiveRegion) -> bool {
664        let meta = lock_meta(&self.inner.meta);
665        let Some(v2) = meta.v2.as_deref() else {
666            return false;
667        };
668        let page = usize::try_from(r.id.get() >> 32).unwrap_or(usize::MAX);
669        v2.pages.get(page).is_some_and(|pg| {
670            (pg.standing == Standing::Unconfirmed || pg.pair.possibly_accepted())
671                && v2.pages.iter().enumerate().any(|(i, o)| {
672                    i != page && (o.standing != Standing::Confirmed || o.pair.possibly_accepted())
673                })
674        })
675    }
676
677    /// What `copy_store` keeps of region `r` (either format); `regions` is
678    /// every region of the store (a full copy's overlap test).
679    fn facts_for_copy(
680        &self,
681        r: &std::sync::Arc<LiveRegion>,
682        regions: &[std::sync::Arc<LiveRegion>],
683    ) -> Result<Facts, Error> {
684        let inner = &self.inner;
685        let header = r
686            .header
687            .lock()
688            .unwrap_or_else(std::sync::PoisonError::into_inner)
689            .clone();
690        let payload = header.payload.as_deref().unwrap_or(&[]);
691        let format_2 = inner.layout.format == FORMAT_2;
692        let (fill, fill_key, capped) = if format_2 {
693            let v = decode_region_header(payload, inner.layout.log2_block, u64::MAX)
694                .map_err(|_| crate::store::corrupt())?;
695            (
696                v.header.fill,
697                v.header.fill_key,
698                v.header.flags & FLAG_CAPPED != 0,
699            )
700        } else {
701            // Format 1: the region meta (a slot's object follows it).
702            let m = payload
703                .get(..REGION_META_LEN)
704                .and_then(|meta| RegionMeta::decode(meta).ok())
705                .ok_or_else(crate::store::corrupt)?;
706            (m.fill, m.fill_key, false)
707        };
708        // A format-1 slot's header-pair generation counts its commits; a
709        // slot is never recycled, so its region generation is 1.
710        let generation = if !format_2 && r.kind == RegionKind::Slot {
711            1
712        } else {
713            r.generation.get()
714        };
715        let tag = {
716            let meta = lock_meta(&inner.meta);
717            match meta.v2.as_deref() {
718                Some(v2) => {
719                    let id = r.id.get();
720                    v2.pages
721                        .get(usize::try_from(id >> 32).unwrap_or(usize::MAX))
722                        .and_then(|p| {
723                            p.entries
724                                .iter()
725                                .find(|e| e.seq == (id & 0xFFFF_FFFF) as u32)
726                        })
727                        .map(|e| e.tag)
728                        .ok_or_else(crate::store::corrupt)?
729                }
730                None => meta
731                    .entries
732                    .iter()
733                    .find(|e| u64::from(e.region_id) == r.id.get())
734                    .map(|e| e.tag)
735                    .ok_or_else(crate::store::corrupt)?,
736            }
737        };
738        let object = if r.kind == RegionKind::Slot {
739            self.slot(r.name.as_str())?.read()
740        } else {
741            None
742        };
743        // A slot's object is whole as committed: never copied "in full".
744        let full = if r.kind == RegionKind::Slot {
745            None
746        } else {
747            self.full_copy(r, regions)
748        };
749        let data_size = full
750            .as_ref()
751            .map_or(r.map.len(), |(ranges, _)| ranges.iter().map(|x| x.1).sum());
752        Ok(Facts {
753            name: r.name.as_str().to_owned(),
754            kind: r.kind,
755            data_size,
756            // A capped region copied in full holds all of it.
757            cap: capped.then(|| r.map.capacity().max(data_size)),
758            attrs: CopyAttrs {
759                generation,
760                fill,
761                fill_key,
762                tag,
763            },
764            object,
765            full,
766            superseded: r.superseded || self.at_risk(r),
767            source: std::sync::Arc::clone(r),
768        })
769    }
770
771    /// Recreates `f` (a region of `src`) in this store and copies its data:
772    /// an append or page region's as its provisioning's fill (durable and
773    /// verified before its header, D-137), a full copy's after it (not yet
774    /// durable: the caller's one barrier makes it so). Returns the bytes
775    /// copied.
776    fn recreate(&self, src: &Store<P>, f: &Facts) -> Result<u64, Error> {
777        let mut opts = RegionOptions::default().size(f.data_size);
778        if let Some(cap) = f.cap {
779            opts = opts.max_size(cap);
780        }
781        // A data size the target's blocks cannot hold exactly would be
782        // rounded up: refused before anything is read or written, naming
783        // the source's region.
784        if f.kind != RegionKind::Slot && f.data_size % self.block() != 0 {
785            return Err(Error::NotWritten {
786                cause: NotWrittenCause::Misaligned,
787                ctx: ErrorContext {
788                    region: Some(f.source.id),
789                    ..ErrorContext::default()
790                },
791            });
792        }
793        // An append or page region read whole through its own map is
794        // copied as its provisioning's fill (D-137): one write per byte,
795        // the source's reads in flight on a second thread.
796        if f.full.is_none() && f.kind != RegionKind::Slot && f.data_size > 0 {
797            let made = std::thread::scope(|s| {
798                // The reader starts at the fill's first request, after the
799                // region is placed: a region read in one piece is then read
800                // while this thread waits for it, in a fixed order with this
801                // thread's steps (the simulator's crash enumerations count
802                // them). It may wait on its queue holding a lane of the
803                // source, and the fill on it holding the target's queue 0:
804                // both stores are this copy's own, opened by it, so nothing
805                // else waits for either (D-136 forbids it in general).
806                let mut feed = None;
807                let mut content = |index: u64, dst: &mut [u8]| -> Result<(), Error> {
808                    // A request for nothing (a first chunk all header
809                    // zeros) starts nothing: the reader starts at the first
810                    // request it must answer.
811                    if dst.is_empty() {
812                        return Ok(());
813                    }
814                    if feed.is_none() {
815                        feed = Some(Feed::start(s, src, &f.source, f.data_size)?);
816                    }
817                    match feed.as_mut() {
818                        Some((_, reader)) => reader.read(index, dst),
819                        None => Err(crate::store::corrupt()),
820                    }
821                };
822                let made = self.provision2(
823                    &f.name,
824                    f.kind,
825                    opts,
826                    None,
827                    Some(&f.attrs),
828                    Some(&mut content),
829                );
830                // A failed provisioning stops the reader (its queue closed)
831                // before it is joined. The provisioning's error comes first
832                // (a reader's error reached it through the queue); else one
833                // the reader met after the last byte was taken.
834                let fed = match feed.take() {
835                    None => Ok(()),
836                    Some((handle, reader)) => {
837                        drop(reader);
838                        match handle.join() {
839                            Ok(fed) => fed,
840                            // A panic in the reader is the caller's, as it
841                            // would be on this thread.
842                            Err(panic) => std::panic::resume_unwind(panic),
843                        }
844                    }
845                };
846                match (made, fed) {
847                    (Ok(made), Ok(())) => Ok(made),
848                    (Err(e), _) | (Ok(_), Err(e)) => Err(e),
849                }
850            })?;
851            debug_assert_eq!(made.generation.get(), f.attrs.generation, "{}", f.name);
852            // Every byte of the data area was asked for: one the fill did
853            // not cover would be committed unread (a backstop: the check
854            // above makes the sizes equal).
855            if made.map.len() != f.data_size {
856                return Err(crate::store::corrupt());
857            }
858            return Ok(f.data_size);
859        }
860        let made = self.provision2(&f.name, f.kind, opts, None, Some(&f.attrs), None)?;
861        debug_assert_eq!(made.generation.get(), f.attrs.generation, "{}", f.name);
862        // The data size as the source's (checked above).
863        debug_assert_eq!(made.map.len(), f.data_size, "{}", f.name);
864        if let Some((ranges, _)) = &f.full {
865            let mut buf = vec![0u8; CHUNK];
866            let mut at = 0u64;
867            for &(file, len) in ranges {
868                let mut done = 0u64;
869                while done < len {
870                    let n = (len - done).min(CHUNK as u64) as usize;
871                    src.read_raw(&f.source, at, file + done, &mut buf[..n])?;
872                    match f.kind {
873                        RegionKind::Page => {
874                            let to = self.page_region(&f.name)?;
875                            let _ticket = to.write(to.pos(at)?, &buf[..n])?;
876                        }
877                        _ => {
878                            let _ticket = self.append_region(&f.name)?.append(&buf[..n])?;
879                        }
880                    }
881                    done += n as u64;
882                    at += n as u64;
883                }
884            }
885            return Ok(f.data_size);
886        }
887        match f.kind {
888            RegionKind::Slot => {
889                let Some(object) = &f.object else {
890                    return Ok(0);
891                };
892                let _receipt = self.slot(&f.name)?.commit(object)?;
893                Ok(object.len() as u64)
894            }
895            // Empty: every other one was copied as its fill (D-137). A
896            // region with data reaching here would be committed holding its
897            // fill instead: refused (a backstop).
898            RegionKind::Page | RegionKind::Append => {
899                if f.data_size != 0 {
900                    return Err(crate::store::corrupt());
901                }
902                Ok(0)
903            }
904        }
905    }
906}