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 held(&self, offset: u64, len: u64) -> bool {
138 offset
139 .checked_add(len)
140 .is_some_and(|e| e <= self.inner.resident_prefix())
141 }
142
143 fn bounds(&self, offset: u64, len: u64) -> std::io::Result<()> {
144 if offset.checked_add(len).is_none_or(|e| e > self.len) {
145 return Err(std::io::Error::new(
150 std::io::ErrorKind::UnexpectedEof,
151 format!(
152 "range out of bounds: read {offset}+{len} exceeds the reported resource length {} — \
153 the file's layout expects more bytes than the length probe found \
154 (a host serving a compressed Content-Length can cause this)",
155 self.len
156 ),
157 ));
158 }
159 Ok(())
160 }
161
162 fn ensure(&self, want: &BTreeSet<u64>) -> std::io::Result<()> {
166 let (missing, others): (Vec<u64>, Vec<u64>) = {
170 let mut st = self.cache.lock().unwrap();
171 st.tick += 1;
172 let tick = st.tick;
173 let mut missing = Vec::new();
174 let mut others = Vec::new();
175 for &b in want {
176 if let Some(e) = st.map.get_mut(&b) {
177 e.stamp = tick;
178 } else if st.in_flight.contains(&b) {
179 others.push(b);
180 } else {
181 missing.push(b);
182 }
183 }
184 for &b in &missing {
185 st.in_flight.insert(b);
186 }
187 (missing, others)
188 };
189 let fetched = self.fetch_claimed(&missing);
190 if !others.is_empty() {
191 let mut st = self.cache.lock().unwrap();
192 while others.iter().any(|b| st.in_flight.contains(b)) {
193 st = self.landed.wait(st).unwrap();
194 }
195 }
198 fetched
199 }
200
201 fn fetch_claimed(&self, missing: &[u64]) -> std::io::Result<()> {
204 if missing.is_empty() {
205 return Ok(());
206 }
207 let r = self.fetch_missing(missing);
208 let mut st = self.cache.lock().unwrap();
209 for b in missing {
210 st.in_flight.remove(b);
211 }
212 drop(st);
213 self.landed.notify_all();
214 r
215 }
216
217 fn fetch_missing(&self, missing: &[u64]) -> std::io::Result<()> {
218 let mut spans: Vec<(u64, u64)> = Vec::new();
220 let mut runs: Vec<(u64, u64)> = Vec::new();
221 let mut i = 0;
222 while i < missing.len() {
223 let first = missing[i];
224 let mut last = first;
225 let mut j = i + 1;
226 while j < missing.len() && missing[j] == last + 1 {
227 last = missing[j];
228 j += 1;
229 }
230 let off = first * self.block;
231 let end = ((last + 1) * self.block).min(self.len);
232 spans.push((off, end - off));
233 runs.push((first, last));
234 i = j;
235 }
236 let blobs = self.inner.read_many(&spans)?;
237 if blobs.len() != spans.len() {
238 return Err(std::io::Error::other("block fetch returned wrong count"));
239 }
240 if let Some(((o, l), b)) = spans
243 .iter()
244 .zip(&blobs)
245 .find(|((_, l), b)| b.len() as u64 != *l)
246 {
247 return Err(std::io::Error::new(
248 std::io::ErrorKind::UnexpectedEof,
249 format!("block fetch at {o} returned {} bytes, not {l}", b.len()),
250 ));
251 }
252 let mut st = self.cache.lock().unwrap();
253 st.tick += 1;
254 let tick = st.tick;
255 for (&(first, last), blob) in runs.iter().zip(blobs.into_iter()) {
256 let span_start = first * self.block;
257 for b in first..=last {
258 let lo = (b * self.block - span_start) as usize;
259 let hi = ((((b + 1) * self.block).min(self.len)) - span_start) as usize;
260 let hi = hi.min(blob.len());
261 let lo = lo.min(hi);
262 let data: Arc<[u8]> = Arc::from(&blob[lo..hi]);
263 st.used += charge(&data);
264 if let Some(old) = st.map.insert(b, CacheEntry { data, stamp: tick }) {
265 st.used -= charge(&old.data); }
267 }
268 }
269 Ok(())
270 }
271
272 fn trim(&self) {
282 let mut st = self.cache.lock().unwrap();
283 if st.used <= self.cap {
284 return;
285 }
286 let slack = if self.cap / 8 >= 4 * self.block {
287 self.cap / 8
288 } else {
289 0
290 };
291 let target = self.cap - slack;
292 let mut order: Vec<(u64, u64)> = st.map.iter().map(|(&b, e)| (e.stamp, b)).collect();
293 order.sort_unstable();
294 for (_, b) in order {
295 if st.used <= target {
296 break;
297 }
298 if let Some(e) = st.map.remove(&b) {
299 st.used -= charge(&e.data);
300 }
301 }
302 }
303
304 fn assemble(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
309 let first = offset / self.block;
310 let last = (offset + len - 1) / self.block;
311 let resident: Vec<Option<Arc<[u8]>>> = {
312 let st = self.cache.lock().unwrap();
313 (first..=last)
314 .map(|b| st.map.get(&b).map(|e| e.data.clone()))
315 .collect()
316 };
317 let mut out = Vec::with_capacity(len as usize);
318 let mut pos = offset;
319 let end = offset + len;
320 while pos < end {
321 let b = pos / self.block;
322 let block_start = b * self.block;
323 let within = (pos - block_start) as usize;
324 let fetched: Vec<u8>;
325 let blk: &[u8] = match &resident[(b - first) as usize] {
326 Some(data) => data,
327 None => {
328 let blen = ((b + 1) * self.block).min(self.len) - block_start;
329 fetched = self.inner.read_at(block_start, blen)?;
330 &fetched
331 }
332 };
333 let take = ((end - pos) as usize).min(blk.len().saturating_sub(within));
334 if take == 0 {
335 break;
336 }
337 out.extend_from_slice(&blk[within..within + take]);
338 pos += take as u64;
339 }
340 if out.len() as u64 != len {
341 return Err(std::io::Error::new(
342 std::io::ErrorKind::UnexpectedEof,
343 format!("short read: {} of {len} bytes at {offset}", out.len()),
344 ));
345 }
346 Ok(out)
347 }
348}
349
350impl<R: RangeReader> RangeReader for BlockCacheReader<R> {
351 fn len(&self) -> u64 {
352 self.len
353 }
354
355 fn concurrency(&self) -> usize {
356 self.inner.concurrency()
357 }
358
359 fn resident_prefix(&self) -> u64 {
360 self.inner.resident_prefix()
361 }
362
363 fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
364 if len == 0 {
365 return Ok(Vec::new());
366 }
367 self.bounds(offset, len)?;
368 if self.held(offset, len) {
372 return self.inner.read_at(offset, len);
373 }
374 let want: BTreeSet<u64> = (offset / self.block..=(offset + len - 1) / self.block).collect();
375 self.ensure(&want)?;
376 let out = self.assemble(offset, len)?;
377 self.trim();
378 Ok(out)
379 }
380
381 fn read_many(&self, ranges: &[(u64, u64)]) -> std::io::Result<Vec<Vec<u8>>> {
382 let mut want = BTreeSet::new();
383 for &(o, l) in ranges {
384 if l == 0 {
385 continue;
386 }
387 self.bounds(o, l)?;
388 if self.held(o, l) {
389 continue;
390 }
391 for b in o / self.block..=(o + l - 1) / self.block {
392 want.insert(b);
393 }
394 }
395 self.ensure(&want)?;
396 let out = ranges
397 .iter()
398 .map(|&(o, l)| {
399 if l == 0 {
400 Ok(Vec::new())
401 } else if self.held(o, l) {
402 self.inner.read_at(o, l)
403 } else {
404 self.assemble(o, l)
405 }
406 })
407 .collect::<std::io::Result<Vec<_>>>()?;
408 self.trim();
409 Ok(out)
410 }
411}
412
413#[cfg(test)]
414mod tests {
415 use super::*;
416 use crate::reader::PrefixReader;
417 use crate::reader::{CountingReader, SliceReader};
418
419 #[test]
422 fn reads_inside_the_inner_prefix_fetch_no_block() {
423 let data: Vec<u8> = (0..100_000u32).map(|i| i as u8).collect();
424 let prefix: Arc<[u8]> = Arc::from(&data[..4096]);
425 let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
426 let r = BlockCacheReader::new(PrefixReader::new(counting.clone(), prefix), 16 * 1024);
427 assert_eq!(r.read_at(0, 4096).unwrap(), data[..4096]);
428 assert_eq!(r.read_many(&[(10, 100)]).unwrap()[0], data[10..110]);
429 assert_eq!(counting.requests(), 0);
430 assert_eq!(r.read_at(5000, 10).unwrap(), data[5000..5010]);
432 assert_eq!(counting.requests(), 1);
433 assert_eq!(counting.bytes_read(), 16 * 1024);
434 }
435
436 #[test]
437 fn caches_blocks_and_serves_exact_bytes() {
438 let data: Vec<u8> = (0..100_000u32).map(|i| i as u8).collect();
439 let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
440 let r = BlockCacheReader::new(counting.clone(), 16 * 1024);
441
442 for off in [10u64, 200, 5000, 16_500, 17_000, 33_000, 33_100] {
444 assert_eq!(
445 r.read_at(off, 32).unwrap(),
446 data[off as usize..off as usize + 32]
447 );
448 }
449 assert!(
452 counting.requests() <= 3,
453 "physical fetches: {}",
454 counting.requests()
455 );
456
457 let before = counting.requests();
459 assert_eq!(r.read_at(200, 16).unwrap(), data[200..216]);
460 assert_eq!(counting.requests(), before);
461 }
462
463 #[test]
464 fn read_many_fetches_missing_blocks_once() {
465 let data: Vec<u8> = (0..200_000u32).map(|i| (i * 7) as u8).collect();
466 let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
467 let r = BlockCacheReader::new(counting.clone(), 32 * 1024);
468 let ranges = [(0u64, 8u64), (40_000, 16), (40_050, 16), (130_000, 64)];
469 let out = r.read_many(&ranges).unwrap();
470 for (&(o, l), got) in ranges.iter().zip(&out) {
471 assert_eq!(got, &data[o as usize..(o + l) as usize]);
472 }
473 assert!(
475 counting.requests() <= 3,
476 "physical: {}",
477 counting.requests()
478 );
479 }
480
481 struct Slow(Vec<u8>, std::sync::atomic::AtomicUsize);
483 impl RangeReader for Slow {
484 fn len(&self) -> u64 {
485 self.0.len() as u64
486 }
487 fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
488 self.1.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
489 std::thread::sleep(std::time::Duration::from_millis(30));
490 Ok(self.0[offset as usize..(offset + len) as usize].to_vec())
491 }
492 }
493
494 #[test]
498 fn concurrent_readers_fetch_a_block_once() {
499 let r = BlockCacheReader::new(Slow(vec![3u8; 100_000], Default::default()), 4096);
500 std::thread::scope(|s| {
501 for _ in 0..6 {
502 s.spawn(|| assert_eq!(r.read_at(5000, 100).unwrap(), vec![3u8; 100]));
503 }
504 });
505 assert_eq!(r.inner.1.load(std::sync::atomic::Ordering::SeqCst), 1);
506 }
507
508 struct Short(Vec<u8>);
510 impl RangeReader for Short {
511 fn len(&self) -> u64 {
512 self.0.len() as u64
513 }
514 fn read_at(&self, offset: u64, len: u64) -> std::io::Result<Vec<u8>> {
515 let end = (offset + len).saturating_sub(1) as usize;
516 Ok(self.0[offset as usize..end].to_vec())
517 }
518 }
519
520 #[test]
523 fn a_short_blob_is_refused_not_cached() {
524 let r = BlockCacheReader::new(Short(vec![9u8; 10_000]), 4096);
525 let err = r.read_at(100, 50).unwrap_err();
526 assert_eq!(err.kind(), std::io::ErrorKind::UnexpectedEof, "{err}");
527 assert!(r.read_many(&[(0, 10), (5000, 10)]).is_err());
528 }
529
530 #[test]
531 fn out_of_bounds_errors() {
532 let data = vec![0u8; 1000];
533 let r = BlockCacheReader::new(SliceReader::new(&data), 8192);
534 assert!(r.read_at(990, 20).is_err());
535 }
536
537 #[test]
540 fn eviction_caps_resident_bytes_and_keeps_reads_exact() {
541 let data: Vec<u8> = (0..1_000_000u32).map(|i| (i * 31) as u8).collect();
542 let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
543 let cap = 64 * 1024;
545 let r = BlockCacheReader::new(counting.clone(), 8192).with_cache_cap(cap);
546 for off in (0..1_000_000u64 - 64).step_by(37_777) {
547 assert_eq!(
548 r.read_at(off, 64).unwrap(),
549 data[off as usize..off as usize + 64]
550 );
551 assert!(
552 r.cached_bytes() <= cap,
553 "resident {} > cap {cap}",
554 r.cached_bytes()
555 );
556 }
557 }
558
559 #[test]
562 fn eviction_is_lru() {
563 let data: Vec<u8> = (0..64 * 1024u32).map(|i| i as u8).collect();
564 let counting = Arc::new(CountingReader::new(SliceReader::new(&data)));
565 let two = 2 * charge(&Arc::from(vec![0u8; 8192]));
567 let r = BlockCacheReader::new(counting.clone(), 8192).with_cache_cap(two);
568 let block = |i: u64| i * 8192;
569 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();
574 r.read_at(block(2), 16).unwrap(); assert_eq!(counting.requests(), before + 1);
576
577 let before = counting.requests();
578 r.read_at(block(0), 16).unwrap(); assert_eq!(
580 counting.requests(),
581 before,
582 "recently-touched block evicted"
583 );
584
585 let before = counting.requests();
586 r.read_at(block(1), 16).unwrap(); assert_eq!(counting.requests(), before + 1);
588 }
589
590 #[test]
594 fn request_larger_than_cap_reads_exactly_then_trims() {
595 let data: Vec<u8> = (0..256 * 1024u32).map(|i| (i * 7) as u8).collect();
596 let cap = 16 * 1024;
597 let r = BlockCacheReader::new(SliceReader::new(&data), 8192).with_cache_cap(cap);
598 let (off, len) = (1000usize, 96 * 1024usize); let out = r.read_at(off as u64, len as u64).unwrap();
600 assert_eq!(out, &data[off..off + len]);
601 assert!(
602 r.cached_bytes() <= cap,
603 "resident {} > cap {cap} after the read",
604 r.cached_bytes()
605 );
606 }
607}