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}