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::error::{Error, ErrorContext, NotWrittenCause, Op};
28use store_io_core::id::RegionId;
29use store_io_format::judge::Standing;
30use store_io_format::meta::{FillPattern, REGION_META_LEN, RegionKind, RegionMeta};
31use store_io_format::meta2::{FLAG_CAPPED, decode_region_header, max_object};
32use store_io_format::slot::FORMAT_2;
33use store_io_platform::{IoOp, Platform};
34
35use crate::exec::{Ran, clear_stale, run};
36use crate::pace::Pace;
37use crate::qos::Qos;
38use crate::settle::settle_read;
39use crate::target::TargetDir;
40
41use crate::slot_handle::committed_object;
42use crate::store::{LiveRegion, Meta, Store, StoreOptions, io, lock_meta};
43use crate::{RegionOptions, ScanItem};
44
45/// The temporary name a copy's target is built under (no live store ever
46/// has it: one left by a crashed copy is removed by the next).
47pub const COPYING: &str = "store.sio.copying";
48
49/// The file in a copy's target directory whose lock a copy holds from
50/// before it looks for a store there until after its rename (created by
51/// the first copy and kept: removing a lock file races its next user).
52pub const COPY_LOCK: &str = "store.sio.copy-lock";
53
54/// How [`copy_store`] builds its target.
55#[derive(Debug, Clone, Default)]
56pub struct CopyOptions {
57    /// The target store's options (trust, buffers, queues...). Its block
58    /// size is the source's whatever this says, and its table holds at
59    /// least the source's regions; the container format is 2.
60    pub store: StoreOptions,
61    /// Copy a source the open left frozen (a stale or lost table page) or
62    /// with unavailable regions or entries this version cannot read,
63    /// instead of refusing it (spec §12, "What `copy_store` copies"; the
64    /// way out of a store no repair can mend in place):
65    /// - every usable region, by its recorded data size;
66    /// - a usable region of a stale page **in full**: its whole capacity,
67    ///   plus the extra extent its header lists when that overlaps no other
68    ///   region's footprint and no reserved span (a growth whose commit may
69    ///   be the page's lost one); the target's data size covers all of it,
70    ///   and its recorded data size is reported
71    ///   ([`CopyReport::verified_up_to`]): the bytes past it may never
72    ///   have been written, may be the newest, or (where no check can
73    ///   tell: a growth another damaged header never listed, an uncommitted
74    ///   one of a confirmed page's region) may never have been this
75    ///   region's;
76    /// - every stale page reported ([`CopyReport::stale_pages`]): its
77    ///   newest commit is given up, so a region it created is missing and
78    ///   one it released is back;
79    /// - unavailable regions and unreadable entries left out, reported
80    ///   ([`CopyReport::omitted`]); a lost page's regions are unknown,
81    ///   reported by page ([`CopyReport::lost_pages`]);
82    /// - a possibly superseded region copied and reported
83    ///   ([`CopyReport::superseded`]): it may read another region's bytes.
84    ///
85    /// Default false: such a source is refused.
86    pub accept_stale_pages: bool,
87}
88
89/// What [`copy_store`] copied.
90#[derive(Debug, Clone, PartialEq, Eq)]
91pub struct CopyReport {
92    /// Regions recreated in the target (slots included).
93    pub regions: usize,
94    /// Data bytes copied (regions' data sizes and slots' objects).
95    pub bytes: u64,
96    /// The source's container format.
97    pub source_format: u16,
98    /// With `accept_stale_pages`: the source's table entries left out
99    /// (unavailable regions, entries of a kind or name this version cannot
100    /// read), by id; the source's report says why.
101    pub omitted: Vec<RegionId>,
102    /// With `accept_stale_pages`: the source's lost table pages (no copy
103    /// of them reads): their regions are unknown, none copied; a region
104    /// they may have taken the bytes of is listed in
105    /// [`Self::superseded`], and no extra extent is copied.
106    pub lost_pages: Vec<u32>,
107    /// With `accept_stale_pages`: the source's stale table pages (a newer
108    /// copy damaged): each one's newest commit is given up, so a region
109    /// that commit created is missing from the copy and one it released is
110    /// in it, whatever regions the page holds.
111    pub stale_pages: Vec<u32>,
112    /// With `accept_stale_pages`: each region of a stale page, copied in
113    /// full, with its recorded data size (name, bytes): only that much is
114    /// known to be the region's acknowledged data (unless it is also listed
115    /// in [`Self::superseded`]).
116    pub verified_up_to: Vec<(String, u64)>,
117    /// With `accept_stale_pages`: the regions copied that may hold another
118    /// region's bytes, by name: possibly superseded (spec §9 step 4:
119    /// another region's newer footprint may cover them), or of a stale or
120    /// possibly accepted page while another page is stale or lost (D-130:
121    /// a given-up commit may have released one, and another given-up
122    /// commit handed its space to a region it created). The source held
123    /// each read-only; the copy's is writable.
124    pub superseded: Vec<String>,
125}
126
127/// What a recreated region keeps of its source (internal: for the
128/// target's provisioning).
129#[derive(Debug, Clone, Copy)]
130pub(crate) struct CopyAttrs {
131    pub(crate) generation: u64,
132    pub(crate) fill: FillPattern,
133    pub(crate) fill_key: [u8; 16],
134    pub(crate) tag: u32,
135}
136
137/// A region's header facts, from a plan's header pass.
138struct HeaderFacts {
139    fill: FillPattern,
140    fill_key: [u8; 16],
141    capped: bool,
142    object: Option<Vec<u8>>,
143}
144
145/// A copy's plan ([`Store::copy_plan`]): every region's facts, in the
146/// store's order, and the volume's (an export's too, `export.rs`).
147pub(crate) struct CopyPlan {
148    pub(crate) facts: Vec<Facts>,
149    pub(crate) omitted: Vec<RegionId>,
150    pub(crate) lost_pages: Vec<u32>,
151    pub(crate) stale_pages: Vec<u32>,
152    pub(crate) verified_up_to: Vec<(String, u64)>,
153    pub(crate) superseded: Vec<String>,
154    pub(crate) block: u64,
155    pub(crate) source_format: u16,
156}
157
158/// A refusal, its region named if it has one.
159fn refused(cause: NotWrittenCause, region: Option<RegionId>) -> Error {
160    Error::NotWritten {
161        cause,
162        ctx: ErrorContext {
163            region,
164            ..ErrorContext::default()
165        },
166    }
167}
168
169/// A source region, as the copy recreates it (and an export describes it).
170pub(crate) struct Facts {
171    pub(crate) name: String,
172    pub(crate) kind: RegionKind,
173    /// The target's data size (the source's, or a full copy's length).
174    pub(crate) data_size: u64,
175    /// Its cap (format 2's capped regions): the target is capped there too.
176    pub(crate) cap: Option<u64>,
177    pub(crate) attrs: CopyAttrs,
178    /// A slot's committed object, if any.
179    pub(crate) object: Option<Vec<u8>>,
180    /// A region of a stale page, copied in full: the container ranges, in
181    /// data order (its capacity, then its extra extent if taken), and its
182    /// recorded data size.
183    pub(crate) full: Option<(Vec<(u64, u64)>, u64)>,
184    /// Possibly superseded (spec §9 step 4).
185    pub(crate) superseded: bool,
186    /// The source region (a full copy reads its runs and extra extent).
187    pub(crate) source: std::sync::Arc<LiveRegion>,
188}
189
190/// The largest piece a copy's reader hands the fill (a scan buffer is cut
191/// into pieces this size or smaller), and how many it keeps queued (D-137):
192/// at most `FEED_DEPTH + 2` pieces exist at once (queued, the one being
193/// built, the one being consumed), 10 MiB whatever `max_io` is.
194const FEED_PIECE: usize = 1 << 20;
195/// See [`FEED_PIECE`].
196const FEED_DEPTH: usize = 8;
197
198/// A copied region's bytes, in order, from the source's scan on another
199/// thread (D-137): the scan's reads stay in flight while the fill writes
200/// (while commits are quiet; while they are active the call has one piece
201/// in flight, a read or a write, when both stores are on one device).
202struct Feed {
203    pieces: std::sync::mpsc::Receiver<Result<(u64, Vec<u8>), Error>>,
204    spent: std::sync::mpsc::Sender<Vec<u8>>,
205    /// The piece being consumed and how much of it is.
206    current: Vec<u8>,
207    start: u64,
208    used: usize,
209    /// The source region, named in an error.
210    region: RegionId,
211}
212
213impl Feed {
214    /// Starts the reader of `r` (its region offsets `[0, len)`) on a
215    /// thread of `s`. The thread ends when the scan does, on the first
216    /// error (sent), or once the returned `Feed` is dropped.
217    ///
218    /// # Errors
219    ///
220    /// `Io { op: Queue }` if the thread cannot be started.
221    fn start<'s, P: Platform>(
222        s: &'s std::thread::Scope<'s, '_>,
223        src: &'s Store<P>,
224        r: &'s LiveRegion,
225        len: u64,
226        pace: Option<Pace>,
227    ) -> Result<(std::thread::ScopedJoinHandle<'s, Result<(), Error>>, Self), Error>
228    where
229        P::Queue: Send,
230    {
231        let (put, pieces) = std::sync::mpsc::sync_channel(FEED_DEPTH);
232        let (spent, back) = std::sync::mpsc::channel::<Vec<u8>>();
233        let handle = std::thread::Builder::new()
234            .name("store-io-copy".into())
235            .spawn_scoped(s, move || {
236                let mut fail = None;
237                let scanned =
238                    src.scan_region(r, 0, len, false, pace.as_ref(), |item, drain| match item {
239                        ScanItem::Data { offset, bytes } => {
240                            for (i, part) in bytes.chunks(FEED_PIECE).enumerate() {
241                                let at = offset + (i * FEED_PIECE) as u64;
242                                let mut v = back.try_recv().unwrap_or_default();
243                                v.clear();
244                                // Memory the pool does not account for: a failed
245                                // allocation is reported, never an abort.
246                                if v.try_reserve_exact(part.len()).is_err() {
247                                    fail = Some(crate::io::not_written(
248                                        NotWrittenCause::PoolExhausted,
249                                        crate::io::ctx_range(r, at, at + part.len() as u64),
250                                    ));
251                                    return ControlFlow::Break(());
252                                }
253                                v.extend_from_slice(part);
254                                // Never blocked on a full feed holding reads in
255                                // flight (R5.4's progress rule): the fill may be
256                                // waiting on the call's record for one of them,
257                                // so the scan's reads are drained first.
258                                let sent = match put.try_send(Ok((at, v))) {
259                                    Ok(()) => true,
260                                    Err(std::sync::mpsc::TrySendError::Full(piece)) => {
261                                        drain() && {
262                                            crate::test_hook::step(
263                                                crate::test_hook::Step::FeedBlocking,
264                                            );
265                                            put.send(piece).is_ok()
266                                        }
267                                    }
268                                    Err(std::sync::mpsc::TrySendError::Disconnected(_)) => false,
269                                };
270                                // The fill stopped (or the drain failed: the scan
271                                // reports it): so does the scan.
272                                if !sent {
273                                    return ControlFlow::Break(());
274                                }
275                            }
276                            ControlFlow::Continue(())
277                        }
278                        ScanItem::Unreadable { start, end } => {
279                            fail = Some(Error::Corruption {
280                                kind: store_io_core::error::CorruptionKind::MediaError,
281                                ctx: crate::io::ctx_range(r, start, end),
282                            });
283                            ControlFlow::Break(())
284                        }
285                    });
286                let failed = match (scanned, fail) {
287                    (_, Some(e)) | (Err(e), None) => Some(e),
288                    (Ok(_), None) => None,
289                };
290                if let Some(e) = failed {
291                    // The fill may already have stopped: then nobody reads
292                    // it, and its own error stands.
293                    let _sent = put.send(Err(e.clone()));
294                    return Err(e);
295                }
296                Ok(())
297            })
298            .map_err(|e| Error::Io {
299                op: Op::Queue,
300                raw: os_error(&e),
301                ctx: ErrorContext {
302                    region: Some(r.id),
303                    ..ErrorContext::default()
304                },
305            })?;
306        Ok((
307            handle,
308            Self {
309                pieces,
310                spent,
311                current: Vec::new(),
312                start: 0,
313                used: 0,
314                region: r.id,
315            },
316        ))
317    }
318
319    /// Fills `dst` with the region's bytes from offset `index` (the fill
320    /// asks for them in order, with no gap).
321    fn read(&mut self, index: u64, dst: &mut [u8]) -> Result<(), Error> {
322        let mut done = 0usize;
323        while done < dst.len() {
324            if self.used == self.current.len() {
325                let (start, piece) = match self.pieces.recv() {
326                    Ok(Ok(p)) => p,
327                    Ok(Err(e)) => return Err(e),
328                    // The scan ended before the region did: bytes its map
329                    // says exist are not there.
330                    Err(_) => return Err(self.wrong(index + done as u64, index + dst.len() as u64)),
331                };
332                let old = std::mem::replace(&mut self.current, piece);
333                let _recycled = self.spent.send(old);
334                self.start = start;
335                self.used = 0;
336            }
337            // In order and without a gap, or the copy is wrong.
338            if self.start + self.used as u64 != index + done as u64 {
339                return Err(self.wrong(index + done as u64, index + dst.len() as u64));
340            }
341            let n = (self.current.len() - self.used).min(dst.len() - done);
342            dst[done..done + n].copy_from_slice(&self.current[self.used..self.used + n]);
343            self.used += n;
344            done += n;
345        }
346        Ok(())
347    }
348
349    /// The source's bytes `[start, end)` did not arrive as its map says.
350    fn wrong(&self, start: u64, end: u64) -> Error {
351        let mut e = crate::store::corrupt();
352        if let Error::Corruption { ctx, .. } = &mut e {
353            *ctx = ErrorContext {
354                region: Some(self.region),
355                range: Some(store_io_core::error::ByteRange { start, end }),
356            };
357        }
358        e
359    }
360}
361
362/// A thread's start failure as an [`OsError`](store_io_core::error::OsError).
363fn os_error(e: &std::io::Error) -> store_io_core::error::OsError {
364    use store_io_core::error::{OsError, OsErrorSource};
365    OsError {
366        code: e.raw_os_error().unwrap_or(0),
367        source: if cfg!(windows) {
368            OsErrorSource::Win32
369        } else {
370            OsErrorSource::Errno
371        },
372    }
373}
374
375/// Copies the store in `from` into a new format-2 store in `to`, whose
376/// directory must hold no store. See the module docs.
377///
378/// # Errors
379///
380/// As [`Store::open_readonly`] for the source and [`Store::create`] for
381/// the target; `Locked` while a writer holds `from` open or another copy
382/// into `to` runs;
383/// `AlreadyExists` if `to` holds a container file (any `store.sio`, even
384/// one a crashed create left empty, which [`Store::create`] would take
385/// over: remove it to copy there), or one appears there during the copy
386/// (kept: the copy's temporary store is removed); `NotWritten(NotReady)`
387/// for a source with unavailable regions or table entries that do not
388/// decode (the first in the error's context; the source's report lists
389/// them all), `NotWritten(Frozen)` for one with a stale or lost table
390/// page (both unless [`CopyOptions::accept_stale_pages`]: then copied as
391/// far as they can be; a full copy's read fails as a region read does:
392/// `Corruption(MediaError)` naming the region and range, `Io`,
393/// `NotWritten(Interrupted | QueueFull)`, or `Corruption(Metadata)` for a
394/// read cut short, `NotWritten(PoolExhausted)`), `NotWritten(TooLarge)` for
395/// a slot object larger than a format-2
396/// slot holds (that region in the context), all before anything is
397/// created; `Io` if whether `to` holds a store cannot be told (any failure
398/// to look but "not found"), before anything but the target directory
399/// (and, on the second look under the lock, the copy lock's file) is
400/// created;
401/// `NotWritten(Misaligned)` if the target's device needs larger blocks
402/// than the source's, or a region's data size is not whole target blocks
403/// (naming the source's region, before that region is provisioned);
404/// `Io { op: Queue }` if a region's reader thread cannot be started; a
405/// copied region's read errors as a scan's (`Corruption(MediaError)`
406/// naming the source's region and range, also for a read cut short),
407/// `NotWritten(PoolExhausted)` if the reader's pieces cannot be allocated;
408/// then any error of provisioning, reading or writing (the target left
409/// under its temporary name, removed by the next copy into `to`);
410/// `DurabilityUnknown` if the rename or the directory flush after it
411/// failed: the copy, whole, may or may not be in place under the target
412/// name (open it, or copy again: `AlreadyExists` means it is).
413pub fn copy_store<P: Platform + Clone>(
414    platform: P,
415    from: &Path,
416    to: &Path,
417    opts: CopyOptions,
418) -> Result<CopyReport, Error>
419where
420    P::Queue: Send,
421{
422    let src = Store::open_readonly(platform.clone(), from, opts.store.clone())?;
423    let CopyPlan {
424        facts,
425        omitted,
426        lost_pages,
427        stale_pages,
428        verified_up_to,
429        superseded,
430        block,
431        source_format,
432    } = src.copy_plan(opts.accept_stale_pages)?;
433    // The target directory under its copy lock, a crashed copy's or
434    // import's temporary removed (`target.rs`).
435    let target = TargetDir::open(&platform, to)?;
436    let mut target_opts = opts.store.clone();
437    target_opts.container_format = FORMAT_2;
438    target_opts.block_size = Some(block as u32);
439    target_opts.region_capacity = target_opts
440        .region_capacity
441        .max(u32::try_from(facts.len()).unwrap_or(u32::MAX));
442    let mut bytes = 0u64;
443    {
444        // The target is this call's own (R5.4): created, filled and closed
445        // as background I/O, paced by its device's commits.
446        let dst = Store::create_named(
447            platform.clone(),
448            to,
449            target_opts,
450            &target.temp,
451            store_io_core::IoClass::Background,
452        )?;
453        // A device that needs larger blocks than the source's would round
454        // every size up: refused (the temporary store is removed by the
455        // next copy).
456        if dst.report().block_size != block {
457            return Err(refused(NotWrittenCause::Misaligned, None));
458        }
459        let reading = dst.reader_pace(&src);
460        for f in &facts {
461            bytes += dst.recreate(&src, f, reading.as_ref())?;
462        }
463        // One barrier for every byte not written as a fill (a stale page's
464        // full copies; the clean close is best effort and reports nothing).
465        dst.flush_all_accounted()?;
466        // Closed here (the drop writes the clean-close record).
467    }
468    // Into place: the rename is the commit of the copy, and never replaces
469    // a store another process created meanwhile.
470    target.commit(&platform)?;
471    Ok(CopyReport {
472        regions: facts.len(),
473        bytes,
474        source_format,
475        omitted,
476        lost_pages,
477        stale_pages,
478        verified_up_to,
479        superseded,
480    })
481}
482
483/// The copy's chunk: 1 MiB.
484const CHUNK: usize = 1 << 20;
485
486impl<P: Platform> Store<P>
487where
488    P::Queue: Send,
489{
490    /// The entries `copy_store` leaves out (`CopyReport::omitted`): format
491    /// 2's holds (every unavailable or unknown-kind entry), else the
492    /// unavailable regions (from the held metadata).
493    fn omitted_for_copy(meta: &Meta) -> Vec<RegionId> {
494        match meta.v2.as_deref() {
495            Some(v2) => {
496                let mut ids: Vec<RegionId> = v2
497                    .holds
498                    .iter()
499                    .map(|h| RegionId::from_raw(h.id()))
500                    .collect();
501                ids.sort_unstable_by_key(|id| id.get());
502                ids
503            }
504            None => {
505                let mut ids: Vec<RegionId> = meta.unavailable.iter().map(|u| u.id).collect();
506                ids.sort_unstable_by_key(|id| id.get());
507                ids
508            }
509        }
510    }
511
512    /// A region of a stale page, copied in full (format 2): its runs over
513    /// the whole capacity, then its extra extent when that overlaps nothing
514    /// any other bytes may belong to: the volume record and table, the
515    /// region's own header blocks and runs, every other region's (header
516    /// blocks and runs over the capacity, an extra extent), and every
517    /// unavailable entry's reserved span and possible writes; never while a
518    /// page is lost (its regions' footprints are unknown). `None` on a
519    /// confirmed page.
520    fn full_copy(
521        &self,
522        meta: &Meta,
523        r: &LiveRegion,
524        regions: &[std::sync::Arc<LiveRegion>],
525    ) -> Option<(Vec<(u64, u64)>, u64)> {
526        let v2 = meta.v2.as_deref()?;
527        let page = usize::try_from(r.id.get() >> 32).ok()?;
528        if v2.pages.get(page)?.standing != Standing::Unconfirmed {
529            return None;
530        }
531        let block = self.block();
532        let mut ranges: Vec<(u64, u64)> = r.map.extents().collect();
533        let overlaps = |(a, n): (u64, u64), (b, m): (u64, u64)| a < b + m && b < a + n;
534        let extra = v2
535            .stale_extra
536            .iter()
537            .find(|e| e.1 == r.id.get())
538            .map(|e| e.2);
539        let lost = v2
540            .pages
541            .iter()
542            .any(|p| p.standing != Standing::Confirmed && p.standing != Standing::Unconfirmed);
543        if let Some(extra) = extra.filter(|_| !lost) {
544            let mut others = regions
545                .iter()
546                .flat_map(|o| {
547                    o.map
548                        .extents()
549                        .chain(o.header_at.iter().map(|&h| (h, block)))
550                        .collect::<Vec<_>>()
551                })
552                .chain(core::iter::once((0, self.inner.layout.data_start())))
553                .chain(v2.holds.iter().filter_map(|h| h.span))
554                .chain(v2.holds.iter().flat_map(|h| h.own.iter().copied()))
555                .chain(
556                    v2.stale_extra
557                        .iter()
558                        .filter(|e| e.1 != r.id.get())
559                        .map(|e| e.2),
560                );
561            if !others.any(|o| overlaps(extra, o)) {
562                ranges.push(extra);
563            }
564        }
565        Some((ranges, r.map.len()))
566    }
567
568    /// Reads `out.len()` bytes of the container at `offset` (both whole
569    /// blocks), whatever `r`'s data size says: a copy's full region, `at`
570    /// the region offset they stand for (named in an error, as a region
571    /// read's verdict is: `settle_read`). With `pace` (the copy's reader's
572    /// call), in its pieces, each admitted before it is submitted and
573    /// charged until it completes, their buffers under the pool's
574    /// background cap.
575    fn read_raw(
576        &self,
577        r: &LiveRegion,
578        mut at: u64,
579        mut offset: u64,
580        out: &mut [u8],
581        pace: Option<&Pace>,
582    ) -> Result<(), Error> {
583        let mut lane = self.inner.queues.get(0);
584        clear_stale(&mut lane).map_err(|raw| io(Op::Read, raw))?;
585        let chunk = pace.map_or(self.chunk(), |p| p.piece().min(self.chunk()));
586        for piece in out.chunks_mut(chunk) {
587            let c = crate::io::ctx_range(r, at, at + piece.len() as u64);
588            let buf = match pace {
589                Some(_) => self.take_capped(piece.len(), c)?,
590                None => self.take(piece.len(), c)?,
591            };
592            let op = IoOp::Read {
593                file: &self.inner.file,
594                offset,
595                buf,
596            };
597            let admitted = pace.map(Pace::admit).transpose()?;
598            let ran = run(&mut lane, op);
599            // Completed (or abandoned): its charge goes with it.
600            drop(admitted);
601            let (got, result) = match ran {
602                Ok(Ran::Done { buf, result }) => (buf, result),
603                // The wait failed with the read in flight: the queue's
604                // failure, no verdict on the media.
605                Ok(Ran::Abandoned(raw)) | Err((_, Some(raw))) => return Err(io(Op::Read, raw)),
606                Err((_, None)) => {
607                    return Err(crate::io::not_written(NotWrittenCause::QueueFull, c));
608                }
609            };
610            let n = settle_read(self, r, at, at + piece.len() as u64, got.as_ref(), result)?;
611            match got {
612                Some(b) if n == piece.len() => piece.copy_from_slice(&b.as_slice()[..n]),
613                // Short: bytes the region's runs say exist are not there.
614                _ => return Err(crate::store::corrupt()),
615            }
616            offset += piece.len() as u64;
617            at += piece.len() as u64;
618        }
619        Ok(())
620    }
621
622    /// The pacing of this copy's reads of `src` (R5.4: a call holds one
623    /// issuer record per device group it uses): the target's own (the
624    /// call's) when `src` is in its group, so the reader and the fill share
625    /// one piece while commits are active and, while they are quiet, the
626    /// reader leaves one of the call's pieces to the fill; else a record of
627    /// the call on `src`'s group. `None` for a target that is no
628    /// background call's.
629    fn reader_pace(&self, src: &Store<P>) -> Option<Pace> {
630        let own = self.inner.domain.pace()?;
631        if Qos::same_group(&self.inner.qos, &src.inner.qos) {
632            Some(own.second())
633        } else {
634            src.inner.domain.new_pace()
635        }
636    }
637
638    /// Whether `r`, on a stale or possibly accepted page while another page
639    /// is too (or lost), may hold another region's bytes (D-130): each
640    /// such page's newest commit may be given up, one releasing `r`, the
641    /// other handing its space to a region it created.
642    fn at_risk(meta: &Meta, r: &LiveRegion) -> bool {
643        let Some(v2) = meta.v2.as_deref() else {
644            return false;
645        };
646        let page = usize::try_from(r.id.get() >> 32).unwrap_or(usize::MAX);
647        v2.pages.get(page).is_some_and(|pg| {
648            (pg.standing == Standing::Unconfirmed || pg.pair.possibly_accepted())
649                && v2.pages.iter().enumerate().any(|(i, o)| {
650                    i != page && (o.standing != Standing::Confirmed || o.pair.possibly_accepted())
651                })
652        })
653    }
654
655    /// What a region's header gives a plan, read with its header lock alone
656    /// and dropped (the header pass, D-113's order: never under the
657    /// metadata lock): its fill, fill key and capped flag, and a slot's
658    /// committed object. The region's gate is checked after the header is
659    /// read: a recycle or release retires it before it changes the header
660    /// (and swaps the region list's entry only after), so a header read
661    /// with the gate still live is the listed generation's, and one a retire
662    /// may have changed fails `StaleGeneration`, before it is decoded.
663    fn header_facts(&self, r: &LiveRegion) -> Result<HeaderFacts, Error> {
664        let inner = &self.inner;
665        let header = r
666            .header
667            .lock()
668            .unwrap_or_else(std::sync::PoisonError::into_inner)
669            .clone();
670        if r.gate.live().is_err() {
671            return Err(refused(NotWrittenCause::StaleGeneration, Some(r.id)));
672        }
673        let payload = header.payload.as_deref().unwrap_or(&[]);
674        let format_2 = inner.layout.format == FORMAT_2;
675        let (fill, fill_key, capped) = if format_2 {
676            let v = decode_region_header(payload, inner.layout.log2_block, u64::MAX)
677                .map_err(|_| crate::store::corrupt())?;
678            (
679                v.header.fill,
680                v.header.fill_key,
681                v.header.flags & FLAG_CAPPED != 0,
682            )
683        } else {
684            // Format 1: the region meta (a slot's object follows it).
685            let m = payload
686                .get(..REGION_META_LEN)
687                .and_then(|meta| RegionMeta::decode(meta).ok())
688                .ok_or_else(crate::store::corrupt)?;
689            (m.fill, m.fill_key, false)
690        };
691        let object = if r.kind == RegionKind::Slot {
692            committed_object(&header, &inner.layout)
693        } else {
694            None
695        };
696        Ok(HeaderFacts {
697            fill,
698            fill_key,
699            capped,
700            object,
701        })
702    }
703
704    /// Region `r`'s tag, from the held metadata's table entry.
705    fn tag_of(meta: &Meta, r: &LiveRegion) -> Result<u32, Error> {
706        match meta.v2.as_deref() {
707            Some(v2) => {
708                let id = r.id.get();
709                v2.pages
710                    .get(usize::try_from(id >> 32).unwrap_or(usize::MAX))
711                    .and_then(|p| {
712                        p.entries
713                            .iter()
714                            .find(|e| e.seq == (id & 0xFFFF_FFFF) as u32)
715                    })
716                    .map(|e| e.tag)
717                    .ok_or_else(crate::store::corrupt)
718            }
719            None => meta
720                .entries
721                .iter()
722                .find(|e| u64::from(e.region_id) == r.id.get())
723                .map(|e| e.tag)
724                .ok_or_else(crate::store::corrupt),
725        }
726    }
727
728    /// What a copy keeps of region `r` (either format): `h` from the header
729    /// pass, the rest from the held metadata; `regions` is every region of
730    /// the store (a full copy's overlap test).
731    fn facts_for_copy(
732        &self,
733        meta: &Meta,
734        r: &std::sync::Arc<LiveRegion>,
735        regions: &[std::sync::Arc<LiveRegion>],
736        h: HeaderFacts,
737    ) -> Result<Facts, Error> {
738        let format_2 = self.inner.layout.format == FORMAT_2;
739        // A format-1 slot's header-pair generation counts its commits; a
740        // slot is never recycled, so its region generation is 1.
741        let generation = if !format_2 && r.kind == RegionKind::Slot {
742            1
743        } else {
744            r.generation.get()
745        };
746        let tag = Self::tag_of(meta, r)?;
747        // A slot's object is whole as committed: never copied "in full".
748        let full = if r.kind == RegionKind::Slot {
749            None
750        } else {
751            self.full_copy(meta, r, regions)
752        };
753        let data_size = full
754            .as_ref()
755            .map_or(r.map.len(), |(ranges, _)| ranges.iter().map(|x| x.1).sum());
756        Ok(Facts {
757            name: r.name.as_str().to_owned(),
758            kind: r.kind,
759            data_size,
760            // A capped region copied in full holds all of it.
761            cap: h.capped.then(|| r.map.capacity().max(data_size)),
762            attrs: CopyAttrs {
763                generation,
764                fill: h.fill,
765                fill_key: h.fill_key,
766                tag,
767            },
768            object: h.object,
769            full,
770            superseded: r.superseded || Self::at_risk(meta, r),
771            source: std::sync::Arc::clone(r),
772        })
773    }
774
775    /// A copy's plan of this store (V6's export shares it): every region's
776    /// facts and the volume's, read in D-113's lock order. First the header
777    /// pass, each region's header lock taken alone and dropped; then one
778    /// metadata hold for the region list (its lock under the metadata
779    /// lock, as provisioning takes it), the tags, the full copies, the
780    /// regions at risk, and the unavailable and omitted lists. A region is
781    /// its (id, generation): the hold's list must be the header pass's, or
782    /// the plan fails `NotWritten(StaleGeneration)` naming the first region
783    /// that changed between them (provisioned, released, recycled), never
784    /// retried silently.
785    ///
786    /// # Errors
787    ///
788    /// `StaleGeneration` as above; without `accept`, `NotReady` for an
789    /// unavailable region or an entry that does not decode, `Frozen` for a
790    /// stale or lost page; `TooLarge` for a slot object a format-2 slot
791    /// cannot hold; `Corruption(Metadata)` for a header or entry that does
792    /// not decode.
793    pub(crate) fn copy_plan(&self, accept: bool) -> Result<CopyPlan, Error> {
794        self.plan_of(accept, None)
795    }
796
797    /// [`Self::copy_plan`] of the regions `subset` names (each once; all
798    /// with `None`): an export's (R5.6). Only those regions' headers are
799    /// read and only their (id, generation) compared between the header
800    /// pass and the hold, so a provisioning or release of another region
801    /// meanwhile fails nothing; the volume-wide refusals (frozen, lost or
802    /// stale pages, unavailable entries) stand whatever the subset.
803    ///
804    /// # Errors
805    ///
806    /// As [`Self::copy_plan`]; `NotWritten(InvalidOptions)` for a name in
807    /// `subset` no region has.
808    pub(crate) fn plan_of(
809        &self,
810        accept: bool,
811        subset: Option<&[String]>,
812    ) -> Result<CopyPlan, Error> {
813        let report = self.report();
814        let block = report.block_size;
815        let log2 = block.trailing_zeros() as u8;
816        let picked =
817            |r: &LiveRegion| subset.is_none_or(|names| names.iter().any(|n| n == r.name.as_str()));
818        let regions: Vec<_> = self
819            .regions_snapshot()
820            .into_iter()
821            .filter(|r| picked(r))
822            .collect();
823        let mut headers = Vec::with_capacity(regions.len());
824        for r in &regions {
825            headers.push(self.header_facts(r)?);
826        }
827        crate::test_hook::step(crate::test_hook::Step::PlanHeaders);
828        let meta = lock_meta(&self.inner.meta);
829        // Every region (a full copy's overlap test), and those planned.
830        let all = self.regions_snapshot();
831        let held: Vec<_> = all.iter().filter(|r| picked(r)).cloned().collect();
832        let same = |a: &LiveRegion, b: &LiveRegion| a.id == b.id && a.generation == b.generation;
833        if let Some(i) = (0..regions.len().max(held.len()))
834            .find(|&i| !matches!((regions.get(i), held.get(i)), (Some(a), Some(b)) if same(a, b)))
835        {
836            let changed = regions.get(i).or_else(|| held.get(i)).map(|r| r.id);
837            return Err(refused(NotWrittenCause::StaleGeneration, changed));
838        }
839        if let Some(names) = subset {
840            // An empty subset is a caller's filter gone wrong, never a
841            // complete backup of nothing.
842            if names.is_empty() {
843                return Err(refused(NotWrittenCause::InvalidOptions, None));
844            }
845            if let Some(n) = names
846                .iter()
847                .find(|n| !held.iter().any(|r| r.name.as_str() == n.as_str()))
848            {
849                // A named region the open could not serve is not ready,
850                // not a name no region has.
851                if let Some(u) = meta.unavailable.iter().find(|u| u.name == **n) {
852                    return Err(refused(NotWrittenCause::NotReady, Some(u.id)));
853                }
854                return Err(refused(NotWrittenCause::InvalidOptions, None));
855            }
856        }
857        let (mut omitted, mut lost_pages, mut stale_pages) = (Vec::new(), Vec::new(), Vec::new());
858        if accept {
859            // Every entry the open holds space for without serving it: the
860            // unavailable regions and the entries of an unknown kind (format
861            // 2's holds are the whole list; format 1 has only the former).
862            omitted = Self::omitted_for_copy(&meta);
863            // The pages as they stand now (an accepted rollback since the
864            // open confirmed some).
865            if let Some(v2) = meta.v2.as_deref() {
866                for (i, p) in v2.pages.iter().enumerate() {
867                    match p.standing {
868                        Standing::Unconfirmed => stale_pages.push(i as u32),
869                        Standing::Lost | Standing::Refused => lost_pages.push(i as u32),
870                        Standing::Confirmed => {}
871                    }
872                }
873            }
874        } else {
875            if let Some(u) = meta.unavailable.first() {
876                return Err(refused(NotWrittenCause::NotReady, Some(u.id)));
877            }
878            // An entry whose kind or name does not decode (a newer release's)
879            // is a region the copy cannot recreate (the list may be truncated:
880            // any).
881            // (The open's list, less those given up since: format 2's
882            // holds are the entries as they stand.)
883            let still = |id: u64| {
884                meta.v2
885                    .as_deref()
886                    .is_none_or(|v2| v2.holds.iter().any(|h| h.id() == id))
887            };
888            if let Some(id) = report
889                .metadata
890                .invalid_entries
891                .iter()
892                .map(|&(p, s)| (u64::from(p) << 32) | u64::from(s))
893                .find(|&id| still(id))
894            {
895                return Err(refused(
896                    NotWrittenCause::NotReady,
897                    Some(RegionId::from_raw(id)),
898                ));
899            }
900            if self.frozen() {
901                return Err(refused(NotWrittenCause::Frozen, None));
902            }
903        }
904        let mut facts = Vec::with_capacity(held.len());
905        let (mut verified_up_to, mut superseded) = (Vec::new(), Vec::new());
906        for (r, h) in held.iter().zip(headers) {
907            if h.object
908                .as_ref()
909                .is_some_and(|o| o.len() > max_object(log2))
910            {
911                return Err(refused(NotWrittenCause::TooLarge, Some(r.id)));
912            }
913            let f = self.facts_for_copy(&meta, r, &all, h)?;
914            if let Some((_, recorded)) = &f.full {
915                verified_up_to.push((f.name.clone(), *recorded));
916            }
917            if f.superseded {
918                superseded.push(f.name.clone());
919            }
920            facts.push(f);
921        }
922        drop(meta);
923        Ok(CopyPlan {
924            facts,
925            omitted,
926            lost_pages,
927            stale_pages,
928            verified_up_to,
929            superseded,
930            block,
931            source_format: report.format,
932        })
933    }
934
935    /// Recreates `f` (a region of `src`) in this store and copies its data:
936    /// an append or page region's as its provisioning's fill (durable and
937    /// verified before its header, D-137), a full copy's after it (not yet
938    /// durable: the caller's one barrier makes it so). Returns the bytes
939    /// copied.
940    fn recreate(&self, src: &Store<P>, f: &Facts, reading: Option<&Pace>) -> Result<u64, Error> {
941        let mut opts = RegionOptions::default().size(f.data_size);
942        if let Some(cap) = f.cap {
943            opts = opts.max_size(cap);
944        }
945        // A data size the target's blocks cannot hold exactly would be
946        // rounded up: refused before anything is read or written, naming
947        // the source's region.
948        if f.kind != RegionKind::Slot && f.data_size % self.block() != 0 {
949            return Err(Error::NotWritten {
950                cause: NotWrittenCause::Misaligned,
951                ctx: ErrorContext {
952                    region: Some(f.source.id),
953                    ..ErrorContext::default()
954                },
955            });
956        }
957        // An append or page region read whole through its own map is
958        // copied as its provisioning's fill (D-137): one write per byte,
959        // the source's reads in flight on a second thread.
960        if f.full.is_none() && f.kind != RegionKind::Slot && f.data_size > 0 {
961            let made = std::thread::scope(|s| {
962                // The reader starts at the fill's first request, after the
963                // region is placed: a region read in one piece is then read
964                // while this thread waits for it, in a fixed order with this
965                // thread's steps (the simulator's crash enumerations count
966                // them). It may wait on its queue, or on the call's record
967                // for the fill's piece, holding a lane of the source, and the
968                // fill on it holding the target's queue 0: both stores are
969                // this copy's own, opened by it, so nothing else waits for
970                // either (D-136 forbids it in general).
971                let mut feed = None;
972                let mut content = |index: u64, dst: &mut [u8]| -> Result<(), Error> {
973                    // A request for nothing (a first chunk all header
974                    // zeros) starts nothing: the reader starts at the first
975                    // request it must answer.
976                    if dst.is_empty() {
977                        return Ok(());
978                    }
979                    if feed.is_none() {
980                        feed = Some(Feed::start(
981                            s,
982                            src,
983                            &f.source,
984                            f.data_size,
985                            reading.cloned(),
986                        )?);
987                    }
988                    match feed.as_mut() {
989                        Some((_, reader)) => reader.read(index, dst),
990                        None => Err(crate::store::corrupt()),
991                    }
992                };
993                let made = self.provision2(
994                    &f.name,
995                    f.kind,
996                    opts,
997                    None,
998                    Some(&f.attrs),
999                    Some(&mut content),
1000                );
1001                // A failed provisioning stops the reader (its queue closed)
1002                // before it is joined. The provisioning's error comes first
1003                // (a reader's error reached it through the queue); else one
1004                // the reader met after the last byte was taken.
1005                let fed = match feed.take() {
1006                    None => Ok(()),
1007                    Some((handle, reader)) => {
1008                        drop(reader);
1009                        match handle.join() {
1010                            Ok(fed) => fed,
1011                            // A panic in the reader is the caller's, as it
1012                            // would be on this thread.
1013                            Err(panic) => std::panic::resume_unwind(panic),
1014                        }
1015                    }
1016                };
1017                match (made, fed) {
1018                    (Ok(made), Ok(())) => Ok(made),
1019                    (Err(e), _) | (Ok(_), Err(e)) => Err(e),
1020                }
1021            })?;
1022            debug_assert_eq!(made.generation.get(), f.attrs.generation, "{}", f.name);
1023            // Every byte of the data area was asked for: one the fill did
1024            // not cover would be committed unread (a backstop: the check
1025            // above makes the sizes equal).
1026            if made.map.len() != f.data_size {
1027                return Err(crate::store::corrupt());
1028            }
1029            return Ok(f.data_size);
1030        }
1031        let made = self.provision2(&f.name, f.kind, opts, None, Some(&f.attrs), None)?;
1032        debug_assert_eq!(made.generation.get(), f.attrs.generation, "{}", f.name);
1033        // The data size as the source's (checked above).
1034        debug_assert_eq!(made.map.len(), f.data_size, "{}", f.name);
1035        if let Some((ranges, _)) = &f.full {
1036            // This call's pieces (the target's `Domain::pace`), each
1037            // admitted before it is written and never across one of the
1038            // target's runs, so each charge covers one device I/O. Their
1039            // buffers are the region write path's own: the target's pool is
1040            // the call's, shared with no commit.
1041            let pace = self.inner.domain.pace();
1042            let piece = pace.map_or(CHUNK, |p| p.piece().min(CHUNK));
1043            let mut buf = vec![0u8; piece];
1044            let mut at = 0u64;
1045            for &(file, len) in ranges {
1046                let mut done = 0u64;
1047                while done < len {
1048                    let n = (len - done).min(piece as u64).min(made.map.run_left(at)) as usize;
1049                    src.read_raw(&f.source, at, file + done, &mut buf[..n], reading)?;
1050                    let charge = pace.map(crate::pace::Pace::admit).transpose()?;
1051                    match f.kind {
1052                        RegionKind::Page => {
1053                            let to = self.page_region(&f.name)?;
1054                            let _ticket = to.write(to.pos(at)?, &buf[..n])?;
1055                        }
1056                        _ => {
1057                            let _ticket = self.append_region(&f.name)?.append(&buf[..n])?;
1058                        }
1059                    }
1060                    drop(charge);
1061                    done += n as u64;
1062                    at += n as u64;
1063                }
1064            }
1065            return Ok(f.data_size);
1066        }
1067        match f.kind {
1068            RegionKind::Slot => {
1069                let Some(object) = &f.object else {
1070                    return Ok(0);
1071                };
1072                let _receipt = self.slot(&f.name)?.commit(object)?;
1073                Ok(object.len() as u64)
1074            }
1075            // Empty: every other one was copied as its fill (D-137). A
1076            // region with data reaching here would be committed holding its
1077            // fill instead: refused (a backstop).
1078            RegionKind::Page | RegionKind::Append => {
1079                if f.data_size != 0 {
1080                    return Err(crate::store::corrupt());
1081                }
1082                Ok(0)
1083            }
1084        }
1085    }
1086}
1087
1088#[cfg(all(test, not(loom)))]
1089mod tests {
1090    #![allow(clippy::unwrap_used, unused_results)]
1091
1092    use std::path::Path;
1093    use std::sync::{Arc, Mutex};
1094
1095    use store_io_core::IoClass;
1096    use store_io_sim::world::TraceEvent;
1097    use store_io_sim::{SimConfig, SimPlatform};
1098
1099    use crate::store::container_name;
1100    use crate::{Store, StoreOptions};
1101
1102    fn background(p: &SimPlatform, dir: &str) -> Store<SimPlatform> {
1103        Store::create_named(
1104            p.clone(),
1105            Path::new(dir),
1106            StoreOptions::default(),
1107            &container_name().unwrap(),
1108            IoClass::Background,
1109        )
1110        .unwrap()
1111    }
1112
1113    /// A copy's reader is a piece of its call: on the target's device group
1114    /// it shares the target's record (the call's), so reader and fill hold
1115    /// one piece between them while commits are active. A store that is no
1116    /// background call's has no reader pacing.
1117    #[test]
1118    fn test_a_copy_s_reader_shares_its_call_s_record_on_one_group() {
1119        let p = SimPlatform::new(SimConfig::volatile(54));
1120        let src = Store::create(p.clone(), Path::new("/a"), StoreOptions::default()).unwrap();
1121        let dst = background(&p, "/c");
1122        let own = dst.inner.domain.pace().unwrap();
1123        let reader = dst.reader_pace(&src).unwrap();
1124        assert!(reader.same_call(own));
1125        assert!(
1126            reader.is_second() && !own.is_second(),
1127            "it leaves the fill a piece"
1128        );
1129        assert!(src.reader_pace(&dst).is_none());
1130    }
1131
1132    /// A copy's raw reads with its reader's pacing: `background_io`
1133    /// pieces, each charged when it is submitted, its buffer under the
1134    /// pool's background cap.
1135    #[test]
1136    fn test_a_paced_raw_read_reads_charged_capped_pieces() {
1137        let p = SimPlatform::new(SimConfig::volatile(55));
1138        let s = Store::create(p.clone(), Path::new("/s"), StoreOptions::default()).unwrap();
1139        let log = s.provision_append_region("log", 1 << 20).unwrap();
1140        let data: Vec<u8> = (0..1usize << 20)
1141            .map(|i| (i as u8) ^ ((i / 4096) as u8).wrapping_mul(37))
1142            .collect();
1143        let t = log.append(&data).unwrap();
1144        let _receipt = log.sync_through(&t).unwrap();
1145        let _hold = s.commit_hold();
1146        let r = Arc::clone(log.state());
1147        assert!(r.map.run_left(0) >= 1 << 20, "one run");
1148        let at = r.map.locate(0, 1 << 20);
1149        let pace = s.inner.domain.new_pace().unwrap();
1150        let (s2, seen) = (s.clone(), Arc::new(Mutex::new(Vec::new())));
1151        let out = Arc::clone(&seen);
1152        p.with_world(|w| {
1153            w.set_submit_probe(Some(Arc::new(move || {
1154                let held: u64 = s2
1155                    .inner
1156                    .pool
1157                    .background_holdings()
1158                    .iter()
1159                    .map(|c| u64::from(c.1))
1160                    .sum();
1161                out.lock().unwrap().push((s2.qos().in_flight, held));
1162            })))
1163        });
1164        let from = p.with_world(|w| w.trace().len());
1165        let mut back = vec![0u8; 1 << 20];
1166        s.read_raw(&r, 0, at, &mut back, Some(&pace)).unwrap();
1167        p.with_world(|w| w.set_submit_probe(None));
1168        assert!(back == data);
1169        let lens: Vec<u64> = p.with_world(|w| {
1170            w.trace()[from..]
1171                .iter()
1172                .filter_map(|e| match e {
1173                    TraceEvent::Read { len, .. } => Some(*len),
1174                    _ => None,
1175                })
1176                .collect()
1177        });
1178        assert_eq!(lens, vec![256 << 10; 4]);
1179        assert_eq!(*seen.lock().unwrap(), vec![(1, 1); 4]);
1180    }
1181
1182    /// A reader with no pacing (a `Feed` given none: every store has a
1183    /// record today, but the type allows it) reads in the store's chunk,
1184    /// here 4 MiB (`max_io`), and still sends `FEED_PIECE` parts, each at
1185    /// its own offset (the reader's bound on the bytes it holds); the fill
1186    /// reads the region whole, in order.
1187    #[test]
1188    fn test_an_unpaced_feed_sends_pieces_at_their_offsets() {
1189        let p = SimPlatform::new(SimConfig::volatile(59));
1190        let opts = StoreOptions {
1191            max_io: 4 << 20,
1192            ..StoreOptions::default()
1193        };
1194        let s = Store::create(p.clone(), Path::new("/s"), opts).unwrap();
1195        assert!(s.chunk() > super::FEED_PIECE, "a chunk of several parts");
1196        let len = 8usize << 20;
1197        let log = s.provision_append_region("log", len as u64).unwrap();
1198        let data: Vec<u8> = (0..len)
1199            .map(|i| (i as u8) ^ ((i / 4096) as u8).wrapping_mul(37) ^ ((i >> 20) as u8))
1200            .collect();
1201        let t = log.append(&data).unwrap();
1202        let _receipt = log.sync_through(&t).unwrap();
1203        let r = Arc::clone(log.state());
1204        let back = std::thread::scope(|sc| {
1205            let (reader, mut feed) = super::Feed::start(sc, &s, &r, len as u64, None).unwrap();
1206            let mut back = vec![0u8; len];
1207            for (i, part) in back.chunks_mut(1 << 20).enumerate() {
1208                feed.read((i << 20) as u64, part).unwrap();
1209            }
1210            drop(feed);
1211            reader.join().unwrap().unwrap();
1212            back
1213        });
1214        assert!(back == data);
1215    }
1216}
1217
1218/// The plan's lock order and its region identity (V6: export plans a live
1219/// store, so a region may change between the header pass and the hold).
1220#[cfg(all(test, not(loom)))]
1221mod plan_tests {
1222    #![allow(clippy::unwrap_used, clippy::expect_used, unused_results)]
1223
1224    use std::path::Path;
1225
1226    use store_io_core::error::{Error, NotWrittenCause};
1227    use store_io_format::slot::{FORMAT_1, FORMAT_2};
1228    use store_io_sim::{SimConfig, SimPlatform};
1229
1230    use crate::test_hook::{Step, lib_tests};
1231    use crate::{Store, StoreOptions};
1232
1233    type Action = Box<dyn FnOnce() + Send>;
1234
1235    /// A writable store of `format` with an append region, a page region
1236    /// and a committed slot.
1237    fn store(seed: u64, format: u16) -> Store<SimPlatform> {
1238        let p = SimPlatform::new(SimConfig::volatile(seed));
1239        let opts = StoreOptions {
1240            container_format: format,
1241            ..StoreOptions::default()
1242        };
1243        let s = Store::create(p, Path::new("/s"), opts).unwrap();
1244        let _a = s.provision_append_region("a", 1 << 20).unwrap();
1245        let _p = s.provision_page_region("p", 1 << 20).unwrap();
1246        let slot = s.provision_slot("s").unwrap();
1247        let _r = slot.commit(b"object").unwrap();
1248        s
1249    }
1250
1251    /// Plans `s` with `act` run between its passes.
1252    fn plan_with(s: &Store<SimPlatform>, act: Action) -> Result<super::CopyPlan, Error> {
1253        lib_tests::at(Step::PlanHeaders, act);
1254        let plan = s.copy_plan(false);
1255        lib_tests::clear();
1256        plan
1257    }
1258
1259    /// The plan failed `StaleGeneration` naming `name`'s region (as it
1260    /// was listed when the test began).
1261    fn stale(r: &Result<super::CopyPlan, Error>, id: Option<store_io_core::id::RegionId>) -> bool {
1262        matches!(
1263            r,
1264            Err(Error::NotWritten {
1265                cause: NotWrittenCause::StaleGeneration,
1266                ctx,
1267            }) if ctx.region.is_some() && (id.is_none() || ctx.region == id)
1268        )
1269    }
1270
1271    fn id_of(s: &Store<SimPlatform>, name: &str) -> Option<store_io_core::id::RegionId> {
1272        s.regions_snapshot()
1273            .iter()
1274            .find(|r| r.name.as_str() == name)
1275            .map(|r| r.id)
1276    }
1277
1278    /// A plan made while a recycle has rewritten its region's header but
1279    /// not yet swapped the region list's entry (the list still names the
1280    /// old generation) fails `StaleGeneration`, never a plan pairing the
1281    /// new header with the old generation. Both formats.
1282    #[test]
1283    fn test_a_plan_inside_a_recycle_s_window_fails() {
1284        for (seed, format) in [(84, FORMAT_1), (85, FORMAT_2)] {
1285            let s = store(seed, format);
1286            let p_id = id_of(&s, "p");
1287            let s2 = s.clone();
1288            let seen = std::sync::Arc::new(std::sync::Mutex::new(None));
1289            let out = std::sync::Arc::clone(&seen);
1290            lib_tests::at(
1291                Step::RecycleRewritten,
1292                Box::new(move || {
1293                    let plan = s2.copy_plan(false);
1294                    *out.lock().unwrap() = Some(stale(&plan, p_id));
1295                }),
1296            );
1297            let _q = s.page_region("p").unwrap().recycle().unwrap();
1298            lib_tests::clear();
1299            assert_eq!(*seen.lock().unwrap(), Some(true), "format {format}");
1300            assert!(s.copy_plan(false).is_ok());
1301        }
1302    }
1303
1304    /// A region provisioned, released, recycled, or released and
1305    /// provisioned again under its name between the header pass and the
1306    /// hold fails the plan `StaleGeneration`, the region named; with
1307    /// nothing between, the plan holds every region, its slot's object
1308    /// from the header pass. Both formats.
1309    #[test]
1310    fn test_a_region_changed_between_the_passes_fails_the_plan() {
1311        for (seed, format) in [(80, FORMAT_1), (81, FORMAT_2)] {
1312            let s = store(seed, format);
1313            let plan = plan_with(&s, Box::new(|| {})).unwrap();
1314            assert_eq!(plan.facts.len(), 3, "format {format}");
1315            let slot = plan.facts.iter().find(|f| f.name == "s").unwrap();
1316            assert_eq!(slot.object.as_deref(), Some(&b"object"[..]));
1317
1318            let s2 = s.clone();
1319            let r = plan_with(
1320                &s,
1321                Box::new(move || {
1322                    let _n = s2.provision_append_region("new", 1 << 20).unwrap();
1323                }),
1324            );
1325            assert!(
1326                stale(&r, None),
1327                "provisioned, format {format}: {:?}",
1328                r.err()
1329            );
1330
1331            let s2 = s.clone();
1332            let r = plan_with(
1333                &s,
1334                Box::new(move || {
1335                    let _q = s2.page_region("p").unwrap().recycle().unwrap();
1336                }),
1337            );
1338            assert!(
1339                stale(&r, id_of(&s, "p")),
1340                "recycled, format {format}: {:?}",
1341                r.err()
1342            );
1343
1344            let a_id = id_of(&s, "a");
1345            let s2 = s.clone();
1346            let r = plan_with(
1347                &s,
1348                Box::new(move || {
1349                    s2.append_region("a").unwrap().release().unwrap();
1350                    let _a = s2.provision_append_region("a", 1 << 20).unwrap();
1351                }),
1352            );
1353            assert!(
1354                stale(&r, a_id),
1355                "released and again, format {format}: {:?}",
1356                r.err()
1357            );
1358
1359            let a_id = id_of(&s, "a");
1360            let s2 = s.clone();
1361            let r = plan_with(
1362                &s,
1363                Box::new(move || {
1364                    s2.append_region("a").unwrap().release().unwrap();
1365                }),
1366            );
1367            assert!(stale(&r, a_id), "released, format {format}: {:?}", r.err());
1368            assert!(s.copy_plan(false).is_ok(), "unchanged since");
1369        }
1370    }
1371
1372    /// Plans racing provisioning, growth, recycling and release on another
1373    /// thread never deadlock (D-113's order: no header lock under the
1374    /// metadata lock) and fail only `StaleGeneration`. Both formats, under
1375    /// a watchdog.
1376    #[test]
1377    fn test_plans_racing_metadata_operations_never_deadlock() {
1378        let (tx, rx) = std::sync::mpsc::channel();
1379        let _w = std::thread::spawn(move || {
1380            for (seed, format) in [(82, FORMAT_1), (83, FORMAT_2)] {
1381                let s = store(seed, format);
1382                let s2 = s.clone();
1383                let ops = std::thread::spawn(move || {
1384                    for i in 0..60u64 {
1385                        let name = format!("r{}", i % 4);
1386                        if let Ok(r) = s2.provision_page_region(&name, 1 << 16) {
1387                            let _g = r.grow(1 << 17);
1388                            if i % 2 == 0 {
1389                                let _q = r.recycle();
1390                            }
1391                            let _r = r.release();
1392                        }
1393                        let _q = s2.page_region("p").and_then(|p| p.recycle());
1394                    }
1395                });
1396                let mut planned = 0;
1397                while !ops.is_finished() || planned == 0 {
1398                    match s.copy_plan(false) {
1399                        Ok(_) => planned += 1,
1400                        Err(e) => assert!(
1401                            matches!(
1402                                e,
1403                                Error::NotWritten {
1404                                    cause: NotWrittenCause::StaleGeneration,
1405                                    ..
1406                                }
1407                            ),
1408                            "format {format}: {e:?}"
1409                        ),
1410                    }
1411                }
1412                ops.join().unwrap();
1413            }
1414            let _sent = tx.send(());
1415        });
1416        rx.recv_timeout(std::time::Duration::from_secs(120))
1417            .expect("a plan deadlocked against a metadata operation (or panicked)");
1418    }
1419}