Skip to main content

store_io_engine/
scan.rs

1//! Raw ordered scans: the recovery read path.
2//!
3//! A scan reads a region from a block-aligned offset to the end of its data
4//! area and hands every byte to the caller in order, as [`ScanItem::Data`].
5//! It keeps several large reads in flight (direct I/O, never the page cache)
6//! and delivers them strictly in order.
7//!
8//! A caller's visitor never runs while the scan holds a shared lane, which
9//! every other call on the store may wait for: a visitor that calls the
10//! store would wait on itself (one lane), or on a thread waiting for that
11//! lane under the metadata lock. On a parallel lane (D-096), which no one
12//! waits for, reads are delivered as they arrive; on a shared lane, the
13//! scan collects every read in flight and puts the lane back before it
14//! delivers them, and a bisection's items are held back until it has. The
15//! store's own visitors (a read's pipeline and its bad-sector search),
16//! which never call the store, are delivered as reads arrive on any lane.
17//!
18//! A scan never stops at bad data. A read the device cannot complete is
19//! bisected down to single sectors (the device's logical block where the
20//! probe knows it and direct I/O allows reads that small; else the store
21//! block); every sector that still fails is reported as
22//! [`ScanItem::Unreadable`] (adjacent ones merged), and the scan carries on
23//! after it. Only the caller decides where valid data ends, by returning
24//! [`ControlFlow::Break`] from its visitor.
25
26use std::ops::ControlFlow;
27
28use store_io_core::errno::is_media_error;
29use store_io_core::error::{Error, ErrorContext, NotWrittenCause, Op, OsError};
30use store_io_core::observe::Counter;
31use store_io_platform::{IoBuf, IoOp, Platform, Queue, RawResult};
32
33use crate::exec::{Lane, LaneGuard, Ran, run};
34use crate::io::{ctx_range, not_written};
35use crate::store::{LiveRegion, Store};
36
37/// Reads kept in flight by a scan.
38const DEPTH: usize = 8;
39
40/// One step of a scan, in region order.
41#[derive(Debug, PartialEq, Eq)]
42pub enum ScanItem<'a> {
43    /// Bytes read from the region, starting at region offset `offset`.
44    Data {
45        /// Region offset of `bytes[0]`.
46        offset: u64,
47        /// The bytes, exactly as the device returned them.
48        bytes: &'a [u8],
49    },
50    /// The device could not read `[start, end)` (whole sectors: the
51    /// device's logical blocks where known, else store blocks). The scan
52    /// continues after it; the range is not "end of data".
53    Unreadable {
54        /// First unreadable byte.
55        start: u64,
56        /// One past the last unreadable byte.
57        end: u64,
58    },
59}
60
61/// How a scan ended.
62#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
63pub struct ScanSummary {
64    /// One past the last byte delivered, as data or as unreadable.
65    pub end: u64,
66    /// Bytes reported unreadable.
67    pub unreadable: u64,
68    /// The visitor stopped the scan.
69    pub stopped: bool,
70}
71
72/// Delivers items to the visitor in order, merging adjacent unreadable
73/// ranges, and keeps the summary.
74struct Emitter<F> {
75    visit: F,
76    bad: Option<(u64, u64)>,
77    sum: ScanSummary,
78    /// Items held back (copied) while a shared lane is held, replayed in
79    /// order by [`Self::release`].
80    held: Option<Vec<Held>>,
81}
82
83/// An item held back by [`Emitter::hold`].
84enum Held {
85    Data(u64, Vec<u8>),
86    Unreadable(u64, u64),
87}
88
89impl<F: FnMut(ScanItem<'_>) -> ControlFlow<()>> Emitter<F> {
90    /// Holds back every item until [`Self::release`].
91    fn hold(&mut self) {
92        let _held = self.held.get_or_insert_with(Vec::new);
93    }
94
95    /// Delivers the items held back, in order.
96    fn release(&mut self) {
97        for item in self.held.take().unwrap_or_default() {
98            match item {
99                Held::Data(offset, bytes) => self.data(offset, &bytes),
100                Held::Unreadable(start, end) => self.unreadable(start, end),
101            }
102        }
103    }
104
105    fn flush_bad(&mut self) {
106        if let Some((start, end)) = self.bad.take() {
107            if (self.visit)(ScanItem::Unreadable { start, end }).is_break() {
108                self.sum.stopped = true;
109            }
110        }
111    }
112
113    fn data(&mut self, offset: u64, bytes: &[u8]) {
114        if let Some(held) = &mut self.held {
115            held.push(Held::Data(offset, bytes.to_vec()));
116            return;
117        }
118        if self.sum.stopped {
119            return;
120        }
121        self.flush_bad();
122        if self.sum.stopped || bytes.is_empty() {
123            return;
124        }
125        self.sum.end = offset + bytes.len() as u64;
126        if (self.visit)(ScanItem::Data { offset, bytes }).is_break() {
127            self.sum.stopped = true;
128        }
129    }
130
131    fn unreadable(&mut self, start: u64, end: u64) {
132        if let Some(held) = &mut self.held {
133            held.push(Held::Unreadable(start, end));
134            return;
135        }
136        if self.sum.stopped || start >= end {
137            return;
138        }
139        self.sum.unreadable += end - start;
140        self.sum.end = end;
141        match &mut self.bad {
142            Some((_, e)) if *e == start => *e = end,
143            _ => {
144                self.flush_bad();
145                self.bad = Some((start, end));
146            }
147        }
148    }
149
150    fn finish(mut self) -> ScanSummary {
151        if !self.sum.stopped {
152            self.flush_bad();
153        }
154        self.sum
155    }
156}
157
158/// A read in flight, and its completion once it arrives.
159struct Pending {
160    start: u64,
161    len: usize,
162    done: Option<(RawResult<usize>, Option<IoBuf>)>,
163}
164
165fn read_error(raw: OsError, c: ErrorContext) -> Error {
166    Error::Io {
167        op: Op::Read,
168        raw,
169        ctx: c,
170    }
171}
172
173impl<P: Platform> Store<P>
174where
175    P::Queue: Send,
176{
177    /// Scans `r` from `from` to `to` (clamped to the data area).
178    /// A scan whose unreadable ranges are reported to the caller: each is
179    /// counted once as a media error (internal rescans are not counted).
180    pub(crate) fn scan_reported<F>(
181        &self,
182        r: &LiveRegion,
183        from: u64,
184        to: u64,
185        mut visit: F,
186    ) -> Result<ScanSummary, Error>
187    where
188        F: FnMut(ScanItem<'_>) -> ControlFlow<()>,
189    {
190        let obs = &self.inner.observer;
191        self.scan_region(r, from, to, true, |item| {
192            if matches!(item, ScanItem::Unreadable { .. }) {
193                obs.add(Counter::MediaErrors, 1);
194            }
195            visit(item)
196        })
197    }
198
199    /// Scans `r` from `from` to `to` (clamped to the data area). `calls_store`:
200    /// the visitor may call the store (a caller's), so it never runs while a
201    /// shared lane is held (the module's docs).
202    pub(crate) fn scan_region<F>(
203        &self,
204        r: &LiveRegion,
205        from: u64,
206        to: u64,
207        calls_store: bool,
208        visit: F,
209    ) -> Result<ScanSummary, Error>
210    where
211        F: FnMut(ScanItem<'_>) -> ControlFlow<()>,
212    {
213        let block = self.block();
214        let to = to.min(r.map.len());
215        let c = ctx_range(r, from, to);
216        if from % block != 0 {
217            return Err(not_written(NotWrittenCause::Misaligned, c));
218        }
219        if from > to {
220            return Err(not_written(NotWrittenCause::OutOfBounds, c));
221        }
222        let mut out = Emitter {
223            visit,
224            bad: None,
225            held: None,
226            sum: ScanSummary {
227                end: from,
228                ..ScanSummary::default()
229            },
230        };
231        if from == to {
232            return Ok(out.finish());
233        }
234        let chunk = self.chunk();
235        let mut free: Vec<IoBuf> = (0..DEPTH)
236            .map_while(|_| self.inner.pool.take_within(chunk, chunk).ok())
237            .collect();
238        if free.is_empty() {
239            return Err(not_written(NotWrittenCause::PoolExhausted, c));
240        }
241        let depth = free.len();
242        let mut ring: Vec<Option<Pending>> = (0..depth).map(|_| None).collect();
243        // Several reads in flight: a parallel lane (D-096). A range of one
244        // buffer in one run, or a pipeline of one, is a single read: the
245        // caller's lane.
246        let several = to - from > chunk as u64 || r.map.run_end(from) < to;
247        let take = || {
248            if several && depth > 1 {
249                self.par_lane(r, Op::Read)
250            } else {
251                self.lane(r, Op::Read)
252            }
253        };
254        let first = take()?;
255        // For a visitor that may call the store, on a shared lane every read
256        // in flight is collected and the lane put back before anything is
257        // delivered (the module's docs); each batch takes a lane again, a
258        // parallel one if it can.
259        let mut deferred = calls_store && first.is_shared();
260        let mut lane: Option<LaneGuard<'_, P::Queue>> = Some(first);
261        let file = &self.inner.file;
262        let (mut submitted, mut delivered) = (0u64, 0u64);
263        let mut next = from;
264        let mut in_flight = 0usize;
265        let mut failure: Option<Error> = None;
266        loop {
267            let progress = (submitted, delivered);
268            // Keep the pipeline full.
269            while failure.is_none() && !out.sum.stopped && next < to && !free.is_empty() {
270                if lane.is_none() {
271                    match take() {
272                        Ok(l) => {
273                            deferred = calls_store && l.is_shared();
274                            lane = Some(l);
275                        }
276                        Err(e) => {
277                            failure = Some(e);
278                            break;
279                        }
280                    }
281                }
282                let Some(lane) = &mut lane else { break };
283                let Some(mut buf) = free.pop() else { break };
284                // Never across a run's end (one device operation each).
285                let len = (to - next).min(chunk as u64).min(r.map.run_left(next)) as usize;
286                // `len ≤ chunk ≤ capacity`.
287                let _fits = buf.set_len(len);
288                let op = IoOp::Read {
289                    file,
290                    offset: r.map.locate(next, len as u64),
291                    buf,
292                };
293                match lane.submit(op, submitted) {
294                    Ok(()) => {
295                        ring[(submitted % depth as u64) as usize] = Some(Pending {
296                            start: next,
297                            len,
298                            done: None,
299                        });
300                        submitted += 1;
301                        next += len as u64;
302                        in_flight += 1;
303                    }
304                    Err(rejected) => {
305                        if let Some(b) = rejected.buf {
306                            free.push(b);
307                        }
308                        match rejected.raw {
309                            None if in_flight > 0 => break,
310                            None => failure = Some(not_written(NotWrittenCause::QueueFull, c)),
311                            Some(raw) => failure = Some(read_error(raw, c)),
312                        }
313                    }
314                }
315            }
316            if deferred {
317                if let Some(l) = &mut lane {
318                    if let Err(e) = collect(l, &mut ring, depth, &mut in_flight) {
319                        // As below: the reads in flight keep their buffers.
320                        return Err(read_error(e, c));
321                    }
322                }
323                lane = None;
324            }
325            // Deliver everything that has arrived, in order.
326            while delivered < submitted {
327                let idx = (delivered % depth as u64) as usize;
328                if ring[idx].as_ref().is_none_or(|p| p.done.is_none()) {
329                    break;
330                }
331                let Some(Pending {
332                    start,
333                    len,
334                    done: Some((result, buf)),
335                }) = ring[idx].take()
336                else {
337                    break;
338                };
339                delivered += 1;
340                let mut buf = buf;
341                debug_assert!(
342                    buf.is_some() || result.is_err(),
343                    "a read succeeded without its buffer (platform contract 1)"
344                );
345                // Counted as every read is: completed, with the bytes it
346                // returned.
347                if let (Ok(n), Some(_)) = (&result, &buf) {
348                    self.inner.observer.add(Counter::Reads, 1);
349                    self.inner
350                        .observer
351                        .add(Counter::ReadBytes, (*n).min(len) as u64);
352                }
353                if failure.is_none() && !out.sum.stopped {
354                    match result {
355                        Ok(n) => match &buf {
356                            Some(b) => {
357                                let n = n.min(len);
358                                out.data(start, &b.as_slice()[..n]);
359                                // A short read inside the container: the
360                                // rest could not be read.
361                                out.unreadable(start + n as u64, start + len as u64);
362                            }
363                            // No bytes came back (a backend breaking
364                            // platform contract 1): the scan stops, never
365                            // reporting the range as unreadable media.
366                            None => {
367                                failure = Some(not_written(NotWrittenCause::Interrupted, c));
368                            }
369                        },
370                        Err(raw) if is_media_error(raw) => {
371                            // Bisect on an idle queue: first collect every
372                            // read still in flight (they are delivered later,
373                            // in order), then split the failed range.
374                            if let Some(l) = &mut lane {
375                                if let Err(e) = collect(l, &mut ring, depth, &mut in_flight) {
376                                    return Err(read_error(e, c));
377                                }
378                            }
379                            match buf.take() {
380                                // On a lane kept (a parallel one, or any for the
381                                // store's own visitors), delivering as it goes.
382                                Some(b) if !deferred => {
383                                    let bisected = match &mut lane {
384                                        Some(l) => {
385                                            self.bisect(l, r, start, len as u64, b, &mut out, c)
386                                        }
387                                        None => Err(not_written(NotWrittenCause::Interrupted, c)),
388                                    };
389                                    match bisected {
390                                        Ok(b) => buf = Some(b),
391                                        Err(e) => failure = Some(e),
392                                    }
393                                }
394                                // On a shared lane taken again, holding its
395                                // items back until the lane is put back.
396                                Some(b) => match self.lane(r, Op::Read) {
397                                    Ok(mut l) => {
398                                        out.hold();
399                                        let bisected = self
400                                            .bisect(&mut l, r, start, len as u64, b, &mut out, c);
401                                        drop(l);
402                                        out.release();
403                                        match bisected {
404                                            Ok(b) => buf = Some(b),
405                                            // The visitor stopped inside the
406                                            // held items: what failed after
407                                            // was never asked for.
408                                            Err(_) if out.sum.stopped => {}
409                                            Err(e) => failure = Some(e),
410                                        }
411                                    }
412                                    Err(e) => failure = Some(e),
413                                },
414                                // No buffer to bisect with (withheld by a
415                                // backend that lost track of its kernel,
416                                // platform contract 1): stop, never drop the range.
417                                None => {
418                                    failure = Some(not_written(NotWrittenCause::Interrupted, c));
419                                }
420                            }
421                        }
422                        Err(raw) => failure = Some(read_error(raw, c)),
423                    }
424                }
425                if let Some(b) = buf {
426                    free.push(b);
427                }
428            }
429            if in_flight == 0 && (next >= to || out.sum.stopped || failure.is_some()) {
430                break;
431            }
432            // Nothing in flight and nothing done this round: nothing ever
433            // will be (a backstop: the scan fails, never spins).
434            if in_flight == 0 && (submitted, delivered) == progress {
435                return Err(not_written(NotWrittenCause::Interrupted, c));
436            }
437            if in_flight > 0 {
438                // Only a lane kept (not deferred) has reads in flight here.
439                let Some(l) = &mut lane else {
440                    return Err(not_written(NotWrittenCause::Interrupted, c));
441                };
442                if let Err(e) = collect_one(l, &mut ring, depth, &mut in_flight) {
443                    // The reads in flight still own their buffers; the queue
444                    // keeps them. Nothing else is safe.
445                    return Err(read_error(e, c));
446                }
447            }
448        }
449        match failure {
450            Some(e) => Err(e),
451            None => Ok(out.finish()),
452        }
453    }
454
455    /// Reads `[start, start + len)` again in halves on an idle lane until each
456    /// failing piece is one sector ([`Store::sector`]), delivering in order.
457    /// Returns the buffer.
458    #[allow(clippy::too_many_arguments)]
459    fn bisect<F>(
460        &self,
461        lane: &mut Lane<P::Queue>,
462        r: &LiveRegion,
463        start: u64,
464        len: u64,
465        mut buf: IoBuf,
466        out: &mut Emitter<F>,
467        c: ErrorContext,
468    ) -> Result<IoBuf, Error>
469    where
470        F: FnMut(ScanItem<'_>) -> ControlFlow<()>,
471    {
472        if out.sum.stopped {
473            return Ok(buf);
474        }
475        let sector = self.sector();
476        // `len ≤ chunk ≤ capacity`.
477        let _fits = buf.set_len(len as usize);
478        let done = run(
479            lane,
480            IoOp::Read {
481                file: &self.inner.file,
482                offset: r.map.locate(start, len),
483                buf,
484            },
485        );
486        let (result, back) = match done {
487            Ok(Ran::Done { buf, result }) => (result, buf),
488            Ok(Ran::Abandoned(raw)) => return Err(read_error(raw, c)),
489            Err((_refused, Some(raw))) => return Err(read_error(raw, c)),
490            Err((_refused, None)) => return Err(not_written(NotWrittenCause::QueueFull, c)),
491        };
492        let Some(buf) = back else {
493            // No buffer came back (a backend breaking platform contract 1;
494            // an abandoned read is `Ran::Abandoned` above).
495            return Err(match result {
496                Err(raw) => read_error(raw, c),
497                Ok(_) => not_written(NotWrittenCause::Interrupted, c),
498            });
499        };
500        match result {
501            Ok(n) => {
502                let n = (n as u64).min(len);
503                self.inner.observer.add(Counter::Reads, 1);
504                self.inner.observer.add(Counter::ReadBytes, n);
505                out.data(start, &buf.as_slice()[..n as usize]);
506                out.unreadable(start + n, start + len);
507                Ok(buf)
508            }
509            Err(raw) if is_media_error(raw) => {
510                if len <= sector {
511                    out.unreadable(start, start + len);
512                    return Ok(buf);
513                }
514                // Whole blocks while the piece spans several, so every read
515                // of a block or more stays block-aligned; sectors only
516                // inside one block.
517                let block = self.block();
518                let unit = if len > block { block } else { sector };
519                let half = (len / unit).div_ceil(2) * unit;
520                let buf = self.bisect(lane, r, start, half, buf, out, c)?;
521                self.bisect(lane, r, start + half, len - half, buf, out, c)
522            }
523            // Below the store block the device refused the smaller read
524            // (alignment) rather than failing on the media: this piece lies
525            // in a block that failed with a media error, so it is reported
526            // unreadable and the scan goes on.
527            Err(_) if len < self.block() => {
528                out.unreadable(start, start + len);
529                Ok(buf)
530            }
531            Err(raw) => Err(read_error(raw, c)),
532        }
533    }
534}
535
536/// Waits for at least one completion and files it under its read.
537fn collect_one<Q: Queue>(
538    lane: &mut Lane<Q>,
539    ring: &mut [Option<Pending>],
540    depth: usize,
541    in_flight: &mut usize,
542) -> Result<(), OsError> {
543    let _added = lane.wait(1)?;
544    for comp in lane.done.drain() {
545        *in_flight = in_flight.saturating_sub(1);
546        if let Some(p) = ring[(comp.tag % depth as u64) as usize].as_mut() {
547            p.done = Some((comp.result, comp.buf));
548        }
549    }
550    Ok(())
551}
552
553/// Waits for every read in flight.
554fn collect<Q: Queue>(
555    lane: &mut Lane<Q>,
556    ring: &mut [Option<Pending>],
557    depth: usize,
558    in_flight: &mut usize,
559) -> Result<(), OsError> {
560    while *in_flight > 0 {
561        collect_one(lane, ring, depth, in_flight)?;
562    }
563    Ok(())
564}