Skip to main content

rete_core/
block_cache.rs

1//! A read-through **block cache** over any [`RangeReader`] — the client-side
2//! half of lazy range serving (SPEC.md §9).
3//!
4//! The engine faults small, scattered byte ranges (a dictionary chunk here, an
5//! index tile there). Issued one-for-one against a high-latency remote, that is
6//! many round trips. This wrapper fetches fixed-size, **block-aligned** spans
7//! instead of exact ranges and caches them, so:
8//!
9//! - nearby reads coalesce into a few block fetches,
10//! - repeated reads (and the header re-read) are free, and
11//! - it needs only plain single-range `Range: bytes=a-b` support — so it speeds
12//!   up reads from **any** object store (S3, GCS, Azure, a CDN) that has no
13//!   multi-range / `multipart/byteranges` support at all.
14//!
15//! The trade is a little over-fetch (whole blocks) for far fewer requests — the
16//! right call on a latency-bound link. Missing blocks for one access are fetched
17//! through [`RangeReader::read_many`], so a backend that *does* support
18//! multi-range collapses them further still; the two optimizations compose.
19//!
20//! Residency is **bounded**: past a byte cap (default [`DEFAULT_CACHE_CAP`],
21//! overridable with [`BlockCacheReader::with_cache_cap`]) the least-recently
22//! touched blocks are evicted after each read. Without the cap, a wide scan of a
23//! multi-GB remote file would grow the cache toward the whole file — on 32-bit
24//! wasm (a 4 GiB address space shared with the decompressed tiles and dictionary
25//! chunks) that is an out-of-memory crash, not a slowdown.
26
27use crate::reader::RangeReader;
28use std::collections::{BTreeSet, HashMap, HashSet};
29use std::sync::{Arc, Condvar, Mutex};
30
31/// Default block size: 64 KiB — large enough to swallow a dictionary chunk or an
32/// index tile in one fetch, small enough to keep over-fetch modest.
33pub const DEFAULT_BLOCK: u64 = 64 * 1024;
34
35/// Default cap on resident cached bytes: 256 MiB. Large enough that a working
36/// set (the tiles + dictionary chunks a query family touches) stays warm; small
37/// enough that a full sweep of a multi-GB file leaves plenty of the 32-bit wasm
38/// address space for the decompressed structures built on top of these bytes.
39/// At the auto-tuned 128–512 KiB block sizes this is 512–2048 resident blocks,
40/// so the eviction scan is trivial.
41pub const DEFAULT_CACHE_CAP: u64 = 256 * 1024 * 1024;
42
43/// Pick a [`BlockCacheReader`] block size from the file length: bigger files get
44/// bigger blocks so a remote query makes far fewer (but larger) round trips —
45/// 128 KiB ≤ 10 MB, 256 KiB ≤ 100 MB, 512 KiB above. The over-fetch is modest
46/// next to the round-trip latency it saves on a high-latency link (S3/CDN). Shared
47/// by the CLI and the wasm client so both size identically; the file length is
48/// known for free from the opening `HEAD` / `Content-Range`.
49pub fn auto_block(len: u64) -> u64 {
50    const MB: u64 = 1 << 20;
51    // The reader coalesces byte-adjacent missing blocks into one request, so a
52    // large block buys little on a contiguous read — it only over-fetches the
53    // *scattered* faults that dominate a selective query (a dictionary chunk is
54    // 64 KiB; a 512 KiB block dragged in 8× the bytes). Keep the block near the
55    // chunk size; nearby-but-not-adjacent faults still merge when they share a
56    // block, and the bigger tier for huge files trades a little over-fetch for
57    // fewer round trips on the biggest scans.
58    let mult: u64 = if len > 100 * MB {
59        2 // 128 KiB
60    } else {
61        1 // 64 KiB
62    };
63    mult * DEFAULT_BLOCK
64}
65
66/// What a cached block costs against the cap: its allocation's real size
67/// (`Arc` header included, rounded to the allocator's class), not its length —
68/// a 128 KiB block occupies 160 KiB under jemalloc.
69fn charge(data: &Arc<[u8]>) -> u64 {
70    crate::chunk_cache::alloc_footprint(data.len() as u64 + 16)
71}
72
73/// One resident block: its bytes plus the last-touch stamp eviction orders by.
74struct CacheEntry {
75    data: Arc<[u8]>,
76    stamp: u64,
77}
78
79/// The cache state behind one mutex: resident blocks, their total byte size,
80/// and the monotonic access counter that makes eviction least-recently-used.
81struct CacheState {
82    map: HashMap<u64, CacheEntry>,
83    used: u64,
84    tick: u64,
85    /// Blocks a reader is fetching right now: a concurrent reader that wants
86    /// one waits for it ([`BlockCacheReader::landed`]) instead of fetching the
87    /// same bytes a second time.
88    in_flight: HashSet<u64>,
89}
90
91pub struct BlockCacheReader<R> {
92    inner: R,
93    block: u64,
94    len: u64,
95    cap: u64,
96    cache: Mutex<CacheState>,
97    /// Signalled whenever a fetch lands (or fails) and clears its in-flight
98    /// marks.
99    landed: Condvar,
100}
101
102impl<R: RangeReader> BlockCacheReader<R> {
103    /// Wrap `inner`, fetching `block`-aligned blocks (clamped to ≥ 4 KiB) and
104    /// keeping at most [`DEFAULT_CACHE_CAP`] bytes of them resident.
105    pub fn new(inner: R, block: u64) -> Self {
106        let len = inner.len();
107        Self {
108            inner,
109            block: block.max(4096),
110            len,
111            cap: DEFAULT_CACHE_CAP,
112            cache: Mutex::new(CacheState {
113                map: HashMap::new(),
114                used: 0,
115                tick: 0,
116                in_flight: HashSet::new(),
117            }),
118            landed: Condvar::new(),
119        }
120    }
121
122    /// Override the resident-byte cap. The cap is enforced *between* reads: a
123    /// single read spanning more than `cap` bytes of blocks is still served
124    /// exactly (its blocks are resident while it assembles) and the cache is
125    /// trimmed back under the cap right after. `u64::MAX` disables eviction.
126    pub fn with_cache_cap(mut self, cap: u64) -> Self {
127        self.cap = cap;
128        self
129    }
130
131    /// Bytes currently resident in the cache (for stats and tests).
132    pub fn cached_bytes(&self) -> u64 {
133        self.cache.lock().unwrap().used
134    }
135
136    /// Is every block of `[offset, offset+len)` resident in the cache?
137    fn resident(&self, offset: u64, len: u64) -> bool {
138        let st = self.cache.lock().unwrap();
139        (offset / self.block..=(offset + len - 1) / self.block).all(|b| st.map.contains_key(&b))
140    }
141
142    /// Does the inner reader already hold `[offset, offset+len)` in memory?
143    fn held(&self, offset: u64, len: u64) -> bool {
144        offset
145            .checked_add(len)
146            .is_some_and(|e| e <= self.inner.resident_prefix())
147    }
148
149    fn bounds(&self, offset: u64, len: u64) -> std::io::Result<()> {
150        if offset.checked_add(len).is_none_or(|e| e > self.len) {
151            // Name the numbers: this fires when a read the file's own layout
152            // demands overruns the length the transport reported, and the two
153            // disagreeing values are the whole diagnosis (issue #95: a host
154            // advertised its gzip size, 58 MB, for a 71 MB file).
155            return Err(std::io::Error::new(
156                std::io::ErrorKind::UnexpectedEof,
157                format!(
158                    "range out of bounds: read {offset}+{len} exceeds the reported resource length {} — \
159                     the file's layout expects more bytes than the length probe found \
160                     (a host serving a compressed Content-Length can cause this)",
161                    self.len
162                ),
163            ));
164        }
165        Ok(())
166    }
167
168    /// Fetch and cache every block index in `want` that isn't resident, issuing
169    /// the missing ones as coalesced spans through `read_many`. Already-resident
170    /// wanted blocks get their recency stamp refreshed.
171    fn ensure(&self, want: &BTreeSet<u64>) -> std::io::Result<()> {
172        // Resident blocks are touched; blocks another reader is fetching are
173        // waited for, not fetched again (a parallel open walks two containers
174        // at once and both often want the next block); the rest are claimed.
175        let (missing, others): (Vec<u64>, Vec<u64>) = {
176            let mut st = self.cache.lock().unwrap();
177            st.tick += 1;
178            let tick = st.tick;
179            let mut missing = Vec::new();
180            let mut others = Vec::new();
181            for &b in want {
182                if let Some(e) = st.map.get_mut(&b) {
183                    e.stamp = tick;
184                } else if st.in_flight.contains(&b) {
185                    others.push(b);
186                } else {
187                    missing.push(b);
188                }
189            }
190            for &b in &missing {
191                st.in_flight.insert(b);
192            }
193            (missing, others)
194        };
195        let fetched = self.fetch_claimed(&missing);
196        if !others.is_empty() {
197            let mut st = self.cache.lock().unwrap();
198            while others.iter().any(|b| st.in_flight.contains(b)) {
199                st = self.landed.wait(st).unwrap();
200            }
201            // A block the other reader failed to fetch is read directly by
202            // `assemble`: correctness never depends on residency.
203        }
204        fetched
205    }
206
207    /// Fetch the blocks this reader claimed in [`ensure`](Self::ensure), cache
208    /// them, and clear their in-flight marks whatever the outcome.
209    fn fetch_claimed(&self, missing: &[u64]) -> std::io::Result<()> {
210        if missing.is_empty() {
211            return Ok(());
212        }
213        let r = self.fetch_missing(missing);
214        let mut st = self.cache.lock().unwrap();
215        for b in missing {
216            st.in_flight.remove(b);
217        }
218        drop(st);
219        self.landed.notify_all();
220        r
221    }
222
223    fn fetch_missing(&self, missing: &[u64]) -> std::io::Result<()> {
224        // Coalesce consecutive block indices into one span each.
225        let mut spans: Vec<(u64, u64)> = Vec::new();
226        let mut runs: Vec<(u64, u64)> = Vec::new();
227        let mut i = 0;
228        while i < missing.len() {
229            let first = missing[i];
230            let mut last = first;
231            let mut j = i + 1;
232            while j < missing.len() && missing[j] == last + 1 {
233                last = missing[j];
234                j += 1;
235            }
236            let off = first * self.block;
237            let end = ((last + 1) * self.block).min(self.len);
238            spans.push((off, end - off));
239            runs.push((first, last));
240            i = j;
241        }
242        let blobs = self.inner.read_many(&spans)?;
243        if blobs.len() != spans.len() {
244            return Err(std::io::Error::other("block fetch returned wrong count"));
245        }
246        // A blob of any other length than its span is not that span: caching
247        // a short one would hand the parsers a silently truncated block.
248        if let Some(((o, l), b)) = spans
249            .iter()
250            .zip(&blobs)
251            .find(|((_, l), b)| b.len() as u64 != *l)
252        {
253            return Err(std::io::Error::new(
254                std::io::ErrorKind::UnexpectedEof,
255                format!("block fetch at {o} returned {} bytes, not {l}", b.len()),
256            ));
257        }
258        let mut st = self.cache.lock().unwrap();
259        st.tick += 1;
260        let tick = st.tick;
261        for (&(first, last), blob) in runs.iter().zip(blobs.into_iter()) {
262            let span_start = first * self.block;
263            for b in first..=last {
264                let lo = (b * self.block - span_start) as usize;
265                let hi = ((((b + 1) * self.block).min(self.len)) - span_start) as usize;
266                let hi = hi.min(blob.len());
267                let lo = lo.min(hi);
268                let data: Arc<[u8]> = Arc::from(&blob[lo..hi]);
269                st.used += charge(&data);
270                if let Some(old) = st.map.insert(b, CacheEntry { data, stamp: tick }) {
271                    st.used -= charge(&old.data); // concurrent double-fetch
272                }
273            }
274        }
275        Ok(())
276    }
277
278    /// Evict least-recently-touched blocks until the resident total fits the
279    /// cap. Called after a read has assembled its bytes, so nothing in flight
280    /// depends on what gets dropped.
281    ///
282    /// Once over the cap it evicts down to 7/8 of it, not just under it:
283    /// finding the least-recent blocks sorts the whole map, and a full cache
284    /// (every read of a long export) used to pay that sort on every single
285    /// read. The slack amortizes one sort over ~1/8 of the cache's turnover
286    /// (only once the cache holds 32+ blocks, so a tiny cache stays exact LRU).
287    fn trim(&self) {
288        let mut st = self.cache.lock().unwrap();
289        if st.used <= self.cap {
290            return;
291        }
292        let slack = if self.cap / 8 >= 4 * self.block {
293            self.cap / 8
294        } else {
295            0
296        };
297        let target = self.cap - slack;
298        let mut order: Vec<(u64, u64)> = st.map.iter().map(|(&b, e)| (e.stamp, b)).collect();
299        order.sort_unstable();
300        for (_, b) in order {
301            if st.used <= target {
302                break;
303            }
304            if let Some(e) = st.map.remove(&b) {
305                st.used -= charge(&e.data);
306            }
307        }
308    }
309
310    /// Copy `[offset, offset+len)` out of the cache. The needed blocks are
311    /// cloned out under one short lock; a block missing here (evicted by a
312    /// concurrent reader's trim between `ensure` and this call) is re-read
313    /// directly from the inner reader — correctness never depends on residency.
314    fn assemble(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
315        let first = offset / self.block;
316        let last = (offset + len - 1) / self.block;
317        let resident: Vec<Option<Arc<[u8]>>> = {
318            let st = self.cache.lock().unwrap();
319            (first..=last)
320                .map(|b| st.map.get(&b).map(|e| e.data.clone()))
321                .collect()
322        };
323        let mut out = Vec::with_capacity(len as usize);
324        let mut pos = offset;
325        let end = offset + len;
326        while pos < end {
327            let b = pos / self.block;
328            let block_start = b * self.block;
329            let within = (pos - block_start) as usize;
330            let fetched: Vec<u8>;
331            let blk: &[u8] = match &resident[(b - first) as usize] {
332                Some(data) => data,
333                None => {
334                    let blen = ((b + 1) * self.block).min(self.len) - block_start;
335                    fetched = self.inner.read_at(block_start, blen)?;
336                    &fetched
337                }
338            };
339            let take = ((end - pos) as usize).min(blk.len().saturating_sub(within));
340            if take == 0 {
341                break;
342            }
343            out.extend_from_slice(&blk[within..within + take]);
344            pos += take as u64;
345        }
346        if out.len() as u64 != len {
347            return Err(std::io::Error::new(
348                std::io::ErrorKind::UnexpectedEof,
349                format!("short read: {} of {len} bytes at {offset}", out.len()),
350            ));
351        }
352        Ok(out)
353    }
354}
355
356impl<R: RangeReader> RangeReader for BlockCacheReader<R> {
357    fn is_local(&self) -> bool {
358        self.inner.is_local()
359    }
360
361    fn len(&self) -> u64 {
362        self.len
363    }
364
365    fn concurrency(&self) -> usize {
366        self.inner.concurrency()
367    }
368
369    fn resident_prefix(&self) -> u64 {
370        self.inner.resident_prefix()
371    }
372
373    fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
374        if len == 0 {
375            return Ok(Vec::new());
376        }
377        self.bounds(offset, len)?;
378        // Bytes the inner reader already holds (an HTTP open's first read) are
379        // no fetch: asking it for the block-aligned span around them would
380        // re-read them, and the rest of the block, in a request of its own.
381        if self.held(offset, len) {
382            return self.inner.read_at(offset, len);
383        }
384        let want: BTreeSet<u64> = (offset / self.block..=(offset + len - 1) / self.block).collect();
385        self.ensure(&want)?;
386        let out = self.assemble(offset, len)?;
387        self.trim();
388        Ok(out)
389    }
390
391    fn read_many(&self, ranges: &[(u64, u64)]) -> std::io::Result<Vec<Vec<u8>>> {
392        let mut want = BTreeSet::new();
393        for &(o, l) in ranges {
394            if l == 0 {
395                continue;
396            }
397            self.bounds(o, l)?;
398            if self.held(o, l) {
399                continue;
400            }
401            for b in o / self.block..=(o + l - 1) / self.block {
402                want.insert(b);
403            }
404        }
405        self.ensure(&want)?;
406        let out = ranges
407            .iter()
408            .map(|&(o, l)| {
409                if l == 0 {
410                    Ok(Vec::new())
411                } else if self.held(o, l) {
412                    self.inner.read_at(o, l)
413                } else {
414                    self.assemble(o, l)
415                }
416            })
417            .collect::<std::io::Result<Vec<_>>>()?;
418        self.trim();
419        Ok(out)
420    }
421
422    /// Ranges the caller knows lie far apart: those the cache holds are served
423    /// from it; the rest go to the inner reader as they are, not rounded out to
424    /// blocks (a 19 KB tile would cost its 128 KiB block, or two) and not
425    /// cached here, since a scattered tile is not near the next one wanted.
426    fn read_many_scattered(&self, ranges: &[(u64, u64)]) -> std::io::Result<Vec<Vec<u8>>> {
427        let mut out: Vec<Option<Vec<u8>>> = vec![None; ranges.len()];
428        let mut rest: Vec<(usize, (u64, u64))> = Vec::new();
429        for (i, &(o, l)) in ranges.iter().enumerate() {
430            if l == 0 {
431                out[i] = Some(Vec::new());
432                continue;
433            }
434            self.bounds(o, l)?;
435            if self.held(o, l) {
436                out[i] = Some(self.inner.read_at(o, l)?);
437            } else if self.resident(o, l) {
438                out[i] = Some(self.assemble(o, l)?);
439            } else {
440                rest.push((i, (o, l)));
441            }
442        }
443        if !rest.is_empty() {
444            let asked: Vec<(u64, u64)> = rest.iter().map(|r| r.1).collect();
445            let got = self.inner.read_many_scattered(&asked)?;
446            if got.len() != asked.len() {
447                return Err(std::io::Error::other("scattered read returned wrong count"));
448            }
449            for ((i, (o, l)), blob) in rest.into_iter().zip(got) {
450                if blob.len() as u64 != l {
451                    return Err(std::io::Error::new(
452                        std::io::ErrorKind::UnexpectedEof,
453                        format!("read at {o} returned {} bytes, not {l}", blob.len()),
454                    ));
455                }
456                out[i] = Some(blob);
457            }
458        }
459        self.trim();
460        Ok(out.into_iter().map(|b| b.unwrap_or_default()).collect())
461    }
462}
463
464#[cfg(test)]
465mod tests {
466    use super::*;
467    use crate::reader::PrefixReader;
468    use crate::reader::{CountingReader, SliceReader};
469
470    /// An HTTP open already holds the file's first bytes: a read inside them
471    /// is served as it is, not by fetching the block-aligned span around it.
472    #[test]
473    fn reads_inside_the_inner_prefix_fetch_no_block() {
474        let data: Vec<u8> = (0..100_000u32).map(|i| i as u8).collect();
475        let prefix: Arc<[u8]> = Arc::from(&data[..4096]);
476        let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
477        let r = BlockCacheReader::new(PrefixReader::new(counting.clone(), prefix), 16 * 1024);
478        assert_eq!(r.read_at(0, 4096).unwrap(), data[..4096]);
479        assert_eq!(r.read_many(&[(10, 100)]).unwrap()[0], data[10..110]);
480        assert_eq!(counting.requests(), 0);
481        // Past the prefix the block is fetched whole, as before.
482        assert_eq!(r.read_at(5000, 10).unwrap(), data[5000..5010]);
483        assert_eq!(counting.requests(), 1);
484        assert_eq!(counting.bytes_read(), 16 * 1024);
485    }
486
487    #[test]
488    fn caches_blocks_and_serves_exact_bytes() {
489        let data: Vec<u8> = (0..100_000u32).map(|i| i as u8).collect();
490        let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
491        let r = BlockCacheReader::new(counting.clone(), 16 * 1024);
492
493        // many small scattered reads inside the first few blocks
494        for off in [10u64, 200, 5000, 16_500, 17_000, 33_000, 33_100] {
495            assert_eq!(
496                r.read_at(off, 32).unwrap(),
497                data[off as usize..off as usize + 32]
498            );
499        }
500        // exact bytes returned, but the 7 logical reads touched only 3 blocks
501        // (0,1,2) → at most 3 physical fetches, not 7.
502        assert!(
503            counting.requests() <= 3,
504            "physical fetches: {}",
505            counting.requests()
506        );
507
508        // a repeat read is fully cached → no new fetch
509        let before = counting.requests();
510        assert_eq!(r.read_at(200, 16).unwrap(), data[200..216]);
511        assert_eq!(counting.requests(), before);
512    }
513
514    /// Scattered ranges are fetched as asked: no block rounding, nothing cached;
515    /// a range whose blocks are resident is still served from the cache.
516    #[test]
517    fn read_many_scattered_is_exact_and_uncached() {
518        let data: Vec<u8> = (0..200_000u32).map(|i| (i * 7) as u8).collect();
519        let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
520        let r = BlockCacheReader::new(counting.clone(), 32 * 1024);
521        let ranges = [(1000u64, 100u64), (100_000, 50), (150_000, 10), (7, 0)];
522        let out = r.read_many_scattered(&ranges).unwrap();
523        for (&(o, l), got) in ranges.iter().zip(&out) {
524            assert_eq!(got.as_slice(), &data[o as usize..(o + l) as usize]);
525        }
526        assert_eq!(counting.bytes_read(), 160);
527        assert_eq!(r.cached_bytes(), 0);
528        // Block 0 resident: a scattered range inside it costs nothing more.
529        r.read_at(5, 8).unwrap();
530        let before = counting.bytes_read();
531        let got = r.read_many_scattered(&[(2000, 10)]).unwrap();
532        assert_eq!(got[0].as_slice(), &data[2000..2010]);
533        assert_eq!(counting.bytes_read(), before);
534    }
535
536    #[test]
537    fn read_many_fetches_missing_blocks_once() {
538        let data: Vec<u8> = (0..200_000u32).map(|i| (i * 7) as u8).collect();
539        let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
540        let r = BlockCacheReader::new(counting.clone(), 32 * 1024);
541        let ranges = [(0u64, 8u64), (40_000, 16), (40_050, 16), (130_000, 64)];
542        let out = r.read_many(&ranges).unwrap();
543        for (&(o, l), got) in ranges.iter().zip(&out) {
544            assert_eq!(got, &data[o as usize..(o + l) as usize]);
545        }
546        // 4 ranges over blocks {0, 1, 4} → ≤ 3 physical fetches.
547        assert!(
548            counting.requests() <= 3,
549            "physical: {}",
550            counting.requests()
551        );
552    }
553
554    /// A slow reader that counts its reads.
555    struct Slow(Vec<u8>, std::sync::atomic::AtomicUsize);
556    impl RangeReader for Slow {
557        fn len(&self) -> u64 {
558            self.0.len() as u64
559        }
560        fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
561            self.1.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
562            std::thread::sleep(std::time::Duration::from_millis(30));
563            Ok(self.0[offset as usize..(offset + len) as usize].to_vec())
564        }
565    }
566
567    /// Readers that want the same block at the same time fetch it once: the
568    /// others wait for it to land (a parallel open walks two containers at
569    /// once, and both used to fetch, and count, the next block).
570    #[test]
571    fn concurrent_readers_fetch_a_block_once() {
572        let r = BlockCacheReader::new(Slow(vec![3u8; 100_000], Default::default()), 4096);
573        std::thread::scope(|s| {
574            for _ in 0..6 {
575                s.spawn(|| assert_eq!(r.read_at(5000, 100).unwrap(), vec![3u8; 100]));
576            }
577        });
578        assert_eq!(r.inner.1.load(std::sync::atomic::Ordering::SeqCst), 1);
579    }
580
581    /// A reader that answers every range one byte short (audit fix 9).
582    struct Short(Vec<u8>);
583    impl RangeReader for Short {
584        fn len(&self) -> u64 {
585            self.0.len() as u64
586        }
587        fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
588            let end = (offset + len).saturating_sub(1) as usize;
589            Ok(self.0[offset as usize..end].to_vec())
590        }
591    }
592
593    /// A short blob from the inner reader is an error, never a short block
594    /// cached and handed out as if it were the range.
595    #[test]
596    fn a_short_blob_is_refused_not_cached() {
597        let r = BlockCacheReader::new(Short(vec![9u8; 10_000]), 4096);
598        let err = r.read_at(100, 50).unwrap_err();
599        assert_eq!(err.kind(), std::io::ErrorKind::UnexpectedEof, "{err}");
600        assert!(r.read_many(&[(0, 10), (5000, 10)]).is_err());
601    }
602
603    #[test]
604    fn out_of_bounds_errors() {
605        let data = vec![0u8; 1000];
606        let r = BlockCacheReader::new(SliceReader::new(&data), 8192);
607        assert!(r.read_at(990, 20).is_err());
608    }
609
610    /// A sweep far wider than the cap must stay under the cap after every read
611    /// while still returning exact bytes — the unbounded-growth regression.
612    #[test]
613    fn eviction_caps_resident_bytes_and_keeps_reads_exact() {
614        let data: Vec<u8> = (0..1_000_000u32).map(|i| (i * 31) as u8).collect();
615        let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
616        // 64 KiB cap over 8 KiB blocks = at most 8 resident blocks.
617        let cap = 64 * 1024;
618        let r = BlockCacheReader::new(counting.clone(), 8192).with_cache_cap(cap);
619        for off in (0..1_000_000u64 - 64).step_by(37_777) {
620            assert_eq!(
621                r.read_at(off, 64).unwrap(),
622                data[off as usize..off as usize + 64]
623            );
624            assert!(
625                r.cached_bytes() <= cap,
626                "resident {} > cap {cap}",
627                r.cached_bytes()
628            );
629        }
630    }
631
632    /// Eviction is least-recently-used: re-touching a block protects it, the
633    /// stalest block goes first, and an evicted block re-fetches exactly once.
634    #[test]
635    fn eviction_is_lru() {
636        let data: Vec<u8> = (0..64 * 1024u32).map(|i| i as u8).collect();
637        let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
638        // Cap = exactly 2 blocks of 8 KiB (as charged).
639        let two = 2 * charge(&Arc::from(vec![0u8; 8192]));
640        let r = BlockCacheReader::new(counting.clone(), 8192).with_cache_cap(two);
641        let block = |i: u64| i * 8192;
642        r.read_at(block(0), 16).unwrap(); // cache {0}
643        r.read_at(block(1), 16).unwrap(); // cache {0,1}
644        r.read_at(block(0), 16).unwrap(); // touch 0 → 1 is now the LRU
645
646        let before = counting.requests();
647        r.read_at(block(2), 16).unwrap(); // fetches 2, evicts 1, keeps 0
648        assert_eq!(counting.requests(), before + 1);
649
650        let before = counting.requests();
651        r.read_at(block(0), 16).unwrap(); // still resident → no fetch
652        assert_eq!(
653            counting.requests(),
654            before,
655            "recently-touched block evicted"
656        );
657
658        let before = counting.requests();
659        r.read_at(block(1), 16).unwrap(); // was evicted → exactly one refetch
660        assert_eq!(counting.requests(), before + 1);
661    }
662
663    /// One read spanning more blocks than the cap allows must still return the
664    /// exact bytes (blocks are resident while the read assembles) and the cache
665    /// must be trimmed back under the cap immediately after.
666    #[test]
667    fn request_larger_than_cap_reads_exactly_then_trims() {
668        let data: Vec<u8> = (0..256 * 1024u32).map(|i| (i * 7) as u8).collect();
669        let cap = 16 * 1024;
670        let r = BlockCacheReader::new(SliceReader::new(&data), 8192).with_cache_cap(cap);
671        let (off, len) = (1000usize, 96 * 1024usize); // 6× the cap
672        let out = r.read_at(off as u64, len as u64).unwrap();
673        assert_eq!(out, &data[off..off + len]);
674        assert!(
675            r.cached_bytes() <= cap,
676            "resident {} > cap {cap} after the read",
677            r.cached_bytes()
678        );
679    }
680}