1use crate::reader::RangeReader;
28use std::collections::{BTreeSet, HashMap, HashSet};
29use std::sync::{Arc, Condvar, Mutex};
30
31pub const DEFAULT_BLOCK: u64 = 64 * 1024;
34
35pub const DEFAULT_CACHE_CAP: u64 = 256 * 1024 * 1024;
42
43pub fn auto_block(len: u64) -> u64 {
50 const MB: u64 = 1 << 20;
51 let mult: u64 = if len > 100 * MB {
59 2 } else {
61 1 };
63 mult * DEFAULT_BLOCK
64}
65
66fn charge(data: &Arc<[u8]>) -> u64 {
70 crate::chunk_cache::alloc_footprint(data.len() as u64 + 16)
71}
72
73struct CacheEntry {
75 data: Arc<[u8]>,
76 stamp: u64,
77}
78
79struct CacheState {
82 map: HashMap<u64, CacheEntry>,
83 used: u64,
84 tick: u64,
85 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 landed: Condvar,
100}
101
102impl<R: RangeReader> BlockCacheReader<R> {
103 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 pub fn with_cache_cap(mut self, cap: u64) -> Self {
127 self.cap = cap;
128 self
129 }
130
131 pub fn cached_bytes(&self) -> u64 {
133 self.cache.lock().unwrap().used
134 }
135
136 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 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 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 fn ensure(&self, want: &BTreeSet<u64>) -> std::io::Result<()> {
172 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 }
204 fetched
205 }
206
207 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 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 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); }
273 }
274 }
275 Ok(())
276 }
277
278 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 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 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 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 #[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 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 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 assert!(
503 counting.requests() <= 3,
504 "physical fetches: {}",
505 counting.requests()
506 );
507
508 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 #[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 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 assert!(
548 counting.requests() <= 3,
549 "physical: {}",
550 counting.requests()
551 );
552 }
553
554 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 #[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 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 #[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 #[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 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 #[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 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(); r.read_at(block(1), 16).unwrap(); r.read_at(block(0), 16).unwrap(); let before = counting.requests();
647 r.read_at(block(2), 16).unwrap(); assert_eq!(counting.requests(), before + 1);
649
650 let before = counting.requests();
651 r.read_at(block(0), 16).unwrap(); 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(); assert_eq!(counting.requests(), before + 1);
661 }
662
663 #[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); 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}