keyframes.rsA branch's keyframes, kept at three tiers so a scrubber click near the live edge - where it matters most - never has to replay far, while a long session still stays bounded on disk. BizHawk calls this a "greenzone": dense near the tip, thinning out with age.
- Dense every [
DENSE_FRAMES] (~2s) for the most recent [DENSE_RETAIN_FRAMES] (~5 minutes). - Medium every [
MEDIUM_FRAMES] (~10s) for the next [MEDIUM_RETAIN_FRAMES] (~1 hour) beyond that. - Coarse every [
COARSE_FRAMES] (~30s) forever beyond that.
Every keyframe is delta-compressed (crate::keyframe) against the
nearest earlier keyframe of ITS OWN TIER OR COARSER - never a finer one -
so [KeyframeIndex::prune]ing a whole aged-out tier never orphans a
survivor's reference. A dense keyframe references the dense-or-coarser
keyframe DENSE_FRAMES earlier; a medium keyframe references the
medium-or-coarser keyframe MEDIUM_FRAMES earlier; a coarse keyframe is
a base. Chain depth is bounded by construction - at most
MEDIUM_FRAMES / DENSE_FRAMES - 1 dense hops before a medium-or-coarser
keyframe, then at most COARSE_FRAMES / MEDIUM_FRAMES - 1 medium hops
before a coarse (base) one - so BASE_EVERY-style depth bookkeeping is
no longer needed; the tier boundaries already bound it.
~2 seconds at 60.0988 fps.
32pub const DENSE_FRAMES: u64 = 120;
~10 seconds; an exact multiple of DENSE_FRAMES.
34pub const MEDIUM_FRAMES: u64 = 600;
~30 seconds; an exact multiple of MEDIUM_FRAMES. Matches this
project's earlier flat cadence, kept as the floor once history is old
enough that nobody is likely to scrub it frame-precisely.
38pub const COARSE_FRAMES: u64 = 1_800;
~5 minutes: how long a keyframe stays at dense spacing before thinning.
41pub const DENSE_RETAIN_FRAMES: u64 = 18_046;
~1 hour: how long a keyframe stays at medium spacing before thinning to coarse-only. Beyond this, only coarse keyframes remain for that stretch.
44pub const MEDIUM_RETAIN_FRAMES: u64 = 216_559;
Which tier frame belongs to - the FINEST tier its frame number lands
on. MEDIUM_FRAMES and COARSE_FRAMES are exact multiples of
DENSE_FRAMES, so this is just divisibility.
The frame frame's keyframe SHOULD be delta-compressed against, per its
tier - None for a base. KeyframeIndex::store still falls back to a
base if this frame is not actually present (a branch's own first
keyframe, at an arbitrary fork point, has nothing earlier in ITS OWN
directory to reference even if this says otherwise).
79const CONFIG: bincode::config::Configuration = bincode::config::standard(); 80 81#[derive(Encode, Decode)] 82struct Stored { 83 ref_frame: Option<u64>, 84 original_len: u32, 85 payload: Vec<u8>, 86} 87 88pub struct KeyframeIndex { 89 dir: PathBuf, 90} 91 92fn parse_frame(name: &std::ffi::OsStr) -> Option<u64> { 93 name.to_str()?.strip_suffix(".kf")?.parse().ok() 94} 95 96impl KeyframeIndex { 97 pub fn open(dir: &Path) -> io::Result<Self> { 98 fs::create_dir_all(dir)?; 99 Ok(Self { dir: dir.to_owned() }) 100 } 101 102 fn path(&self, frame: u64) -> PathBuf { 103 self.dir.join(format!("{frame:012}.kf")) 104 }
Where a keyframe's file lives on disk - for a caller that only wants
its size (apps/replay-probe's measurement) without decoding it.
Every keyframe's frame number in this branch, ascending.
The largest keyframe frame <= target, if any.
Decode the keyframe at frame back to a full snapshot. frame must
be one [Self::frames] lists.
138 pub fn load(&self, frame: u64) -> io::Result<Vec<u8>> { 139 let stored = self.read_stored(frame)?; 140 let reference = match stored.ref_frame { 141 None => None, 142 Some(rf) => Some(self.load(rf)?), 143 }; 144 keyframe::decompress(reference.as_deref(), &stored.payload, stored.original_len as usize) 145 }
Keep snapshot under frame, delta-compressed per its tier
([preferred_reference]) against whatever is actually on disk - a
branch's very first keyframe (at its fork point, any frame number)
has nothing to reference in ITS OWN directory yet regardless of what
tier its frame number would suggest, so it falls back to a base.
Written atomically, like every other file this project keeps beside
a running window.
154 pub fn store(&self, frame: u64, snapshot: &[u8]) -> io::Result<()> { 155 let existing = self.frames(); 156 let ref_frame = preferred_reference(frame).filter(|rf| existing.contains(rf)); 157 let reference = match ref_frame { 158 Some(rf) => Some(self.load(rf)?), 159 None => None, 160 }; 161 let payload = keyframe::compress(reference.as_deref(), snapshot); 162 let stored = Stored { ref_frame, original_len: snapshot.len() as u32, payload }; 163 let bytes = bincode::encode_to_vec(&stored, CONFIG).expect("encoding a keyframe never fails"); 164 let tmp = self.dir.join(format!("{frame:012}.kf.part")); 165 fs::write(&tmp, bytes)?; 166 fs::rename(tmp, self.path(frame)) 167 }
Thin keyframes that have aged out of a finer tier, relative to
tip_frame (the branch's current live edge - or, for a paused
branch, its last recorded frame). Deletes a WHOLE tier-bucket at
once, never a partial one, so a still-live keyframe's reference is
never removed out from under it (this module's own doc comment), and
never deletes the SMALLEST frame in the index - a branch's own
anchor keyframe at its fork point, which every seek into its early
history depends on regardless of what tier its frame number would
otherwise put it in. Returns how many files were removed.
178 pub fn prune(&self, tip_frame: u64) -> io::Result<usize> { 179 let frames = self.frames(); 180 let Some(&anchor) = frames.first() else { return Ok(0) }; 181 let mut removed = 0; 182 for frame in frames { 183 if frame == anchor { 184 continue; 185 } 186 let (bucket_width, tier_retain) = match tier_of(frame) { 187 Tier::Dense => (MEDIUM_FRAMES, DENSE_RETAIN_FRAMES), 188 Tier::Medium => (COARSE_FRAMES, MEDIUM_RETAIN_FRAMES), 189 Tier::Coarse => continue, // never thinned further 190 }; 191 // The bucket's own last (youngest) member at this tier - only 192 // once IT has aged past the tier's retention window is the 193 // whole bucket safe to remove together. 194 let bucket_start = frame - frame % bucket_width; 195 let bucket_last = bucket_start + bucket_width - if tier_of(frame) == Tier::Dense { DENSE_FRAMES } else { MEDIUM_FRAMES }; 196 if tip_frame.saturating_sub(bucket_last) > tier_retain { 197 fs::remove_file(self.path(frame))?; 198 removed += 1; 199 } 200 } 201 Ok(removed) 202 }
Bytes on disk of every keyframe in this branch.
Delete every dense and medium keyframe in the OLDEST COARSE_FRAMES
span that still has any, ahead of their age - what
crate::storage::enforce_cap does to the active recording once
nothing else is left to delete. The whole span goes at once for the
same reason [Self::prune] removes whole buckets: a finer keyframe
references one inside its own span, and a coarse keyframe references
nothing, so removing everything finer in one span can orphan nothing
that survives. Coarse keyframes and the anchor are never touched, so
every frame stays seekable, only slower. Returns the bytes freed, 0
once only coarse keyframes and the anchor remain.
219 pub fn thin_oldest_span(&self) -> io::Result<u64> { 220 let frames = self.frames(); 221 let Some(&anchor) = frames.first() else { return Ok(0) }; 222 let thinnable = |f: &u64| *f != anchor && tier_of(*f) != Tier::Coarse; 223 let Some(&oldest) = frames.iter().find(|f| thinnable(f)) else { return Ok(0) }; 224 let span = oldest / COARSE_FRAMES; 225 let mut freed = 0; 226 for f in frames.iter().filter(|f| thinnable(f) && **f / COARSE_FRAMES == span) { 227 let path = self.path(*f); 228 freed += fs::metadata(&path).map_or(0, |m| m.len()); 229 fs::remove_file(path)?; 230 } 231 Ok(freed) 232 } 233}
235#[cfg(test)] 236mod tests { 237 use super::*; 238 239 fn scratch(tag: &str) -> KeyframeIndex { 240 let dir = std::env::temp_dir().join(format!("jev-replay-keyframes-test-{tag}-{}", std::process::id())); 241 let _ = fs::remove_dir_all(&dir); 242 KeyframeIndex::open(&dir).unwrap() 243 } 244 245 fn snapshot(seed: u8, len: usize) -> Vec<u8> { 246 (0..len).map(|i| seed.wrapping_add((i % 251) as u8)).collect() 247 } 248 249 #[test] 250 fn tier_of_matches_the_three_boundaries() { 251 assert_eq!(tier_of(0), Tier::Coarse); 252 assert_eq!(tier_of(1_800), Tier::Coarse); 253 assert_eq!(tier_of(3_600), Tier::Coarse); 254 assert_eq!(tier_of(600), Tier::Medium); 255 assert_eq!(tier_of(1_200), Tier::Medium); 256 assert_eq!(tier_of(120), Tier::Dense); 257 assert_eq!(tier_of(240), Tier::Dense); 258 assert_eq!(tier_of(1), Tier::Dense); 259 } 260 261 #[test] 262 fn a_lone_keyframe_round_trips() { 263 let idx = scratch("lone"); 264 let data = snapshot(1, 5000); 265 idx.store(100, &data).unwrap(); 266 assert_eq!(idx.frames(), vec![100]); 267 assert_eq!(idx.load(100).unwrap(), data); 268 } 269 270 #[test] 271 fn a_full_tier_ladder_all_round_trips() { 272 let idx = scratch("ladder"); 273 // Every DENSE_FRAMES step for two full COARSE_FRAMES cycles, so 274 // every tier boundary and every in-between frame is exercised. 275 let mut frame = 0u64; 276 let mut seed = 0u8; 277 while frame <= COARSE_FRAMES * 2 { 278 let mut data = snapshot(seed, 4000); 279 data[10] = seed; // guarantee at least one real change per frame 280 idx.store(frame, &data).unwrap(); 281 frame += DENSE_FRAMES; 282 seed = seed.wrapping_add(1); 283 } 284 let frames = idx.frames(); 285 assert_eq!(frames.len() as u64, COARSE_FRAMES * 2 / DENSE_FRAMES + 1); 286 let mut seed = 0u8; 287 for f in frames { 288 let mut expected = snapshot(seed, 4000); 289 expected[10] = seed; 290 assert_eq!(idx.load(f).unwrap(), expected, "frame {f}"); 291 seed = seed.wrapping_add(1); 292 } 293 } 294 295 #[test] 296 fn nearest_at_or_before_finds_the_right_one() { 297 let idx = scratch("nearest"); 298 for f in [10u64, 50, 200] { 299 idx.store(f, &snapshot(1, 100)).unwrap(); 300 } 301 assert_eq!(idx.nearest_at_or_before(9), None); 302 assert_eq!(idx.nearest_at_or_before(10), Some(10)); 303 assert_eq!(idx.nearest_at_or_before(49), Some(10)); 304 assert_eq!(idx.nearest_at_or_before(500), Some(200)); 305 } 306 307 #[test] 308 fn a_branchs_first_keyframe_at_an_arbitrary_frame_is_a_base() { 309 // Not a multiple of anything: tier_of would call this Dense and 310 // want to reference frame-120, which does not exist in this fresh 311 // directory - it must fall back to a base instead of erroring. 312 let idx = scratch("arbitrary-anchor"); 313 let data = snapshot(7, 2000); 314 idx.store(1_234_567, &data).unwrap(); 315 assert_eq!(idx.load(1_234_567).unwrap(), data); 316 } 317 318 #[test] 319 fn pruning_removes_only_whole_aged_out_dense_buckets_and_never_the_anchor() { 320 let idx = scratch("prune-dense"); 321 // Anchor at 0 (coarse, never touched), then a full dense ladder up 322 // to just short of the next coarse boundary. 323 let mut frame = 0u64; 324 while frame < COARSE_FRAMES { 325 idx.store(frame, &snapshot(frame as u8, 500)).unwrap(); 326 frame += DENSE_FRAMES; 327 } 328 let before = idx.frames(); 329 assert!(before.len() > 2, "need more than just the anchor and one dense frame"); 330 331 // Not yet aged out: nothing removed. 332 let removed = idx.prune(DENSE_RETAIN_FRAMES).unwrap(); 333 assert_eq!(removed, 0); 334 assert_eq!(idx.frames(), before); 335 336 // Aged out: every dense (and medium) frame in the first 337 // MEDIUM_FRAMES bucket goes, but frame 0 (the anchor, coarse 338 // tier) survives regardless of age. 339 let tip = COARSE_FRAMES - DENSE_FRAMES + DENSE_RETAIN_FRAMES + 1; 340 idx.prune(tip).unwrap(); 341 let remaining = idx.frames(); 342 assert!(remaining.contains(&0), "the anchor must never be pruned"); 343 assert!(!remaining.contains(&DENSE_FRAMES), "an aged-out dense frame should be gone"); 344 // Every surviving keyframe must still decode. 345 for f in &remaining { 346 idx.load(*f).expect("a surviving keyframe must still decode after pruning"); 347 } 348 } 349 350 #[test] 351 fn pruning_a_medium_bucket_never_orphans_a_surviving_dense_reference() { 352 // A dense keyframe just past a medium boundary references the 353 // medium/coarse anchor of ITS OWN bucket, never the previous 354 // bucket's tail - so thinning one medium bucket must never break a 355 // dense keyframe that is still within its own retention window in 356 // the NEXT bucket. 357 let idx = scratch("prune-cross-bucket"); 358 for frame in (0..=MEDIUM_FRAMES * 3).step_by(DENSE_FRAMES as usize) { 359 idx.store(frame, &snapshot(frame as u8, 300)).unwrap(); 360 } 361 // Age everything past MEDIUM_RETAIN_FRAMES relative to a tip far in 362 // the future, but well within DENSE_RETAIN_FRAMES for the last 363 // bucket, whose own dense members must survive. 364 let tip = MEDIUM_FRAMES * 3 + 10; 365 idx.prune(tip).unwrap(); 366 for f in idx.frames() { 367 idx.load(f).expect("every surviving keyframe must still decode"); 368 } 369 } 370 371 #[test] 372 fn thinning_takes_the_oldest_span_whole_and_keeps_coarse_and_anchor() { 373 let idx = scratch("thin"); 374 // Anchor at 240 (a dense frame number), then every dense step 375 // through three coarse spans. 376 let mut frame = 240; 377 while frame <= COARSE_FRAMES * 3 { 378 idx.store(frame, &snapshot(frame as u8, 400)).unwrap(); 379 frame += DENSE_FRAMES; 380 } 381 assert!(idx.thin_oldest_span().unwrap() > 0); 382 let left = idx.frames(); 383 assert!(left.contains(&240), "anchor kept"); 384 assert!(left.contains(&COARSE_FRAMES), "coarse kept"); 385 assert!(!left.iter().any(|&f| f != 240 && f < COARSE_FRAMES), "the first span's finer keyframes are gone"); 386 assert!(left.contains(&(COARSE_FRAMES + DENSE_FRAMES)), "the next span is untouched"); 387 for f in &left { 388 idx.load(*f).expect("every survivor still decodes"); 389 } 390 while idx.thin_oldest_span().unwrap() > 0 {} 391 let left = idx.frames(); 392 assert!(left.iter().all(|&f| f == 240 || tier_of(f) == Tier::Coarse)); 393 for f in &left { 394 idx.load(*f).expect("every survivor still decodes"); 395 } 396 } 397}