diff options
author | Dylan Reid <dgreid@chromium.org> | 2018-08-28 17:07:56 -0700 |
---|---|---|
committer | chrome-bot <chrome-bot@chromium.org> | 2018-09-15 20:58:17 -0700 |
commit | 62d21839e6aa160f6db1957be018f4cebe36e397 (patch) | |
tree | 3ee7bb2a582d5b3f0d166885b0adde09e9e35d4d /qcow | |
parent | 8b952c2faf82c8e3c1c6e921edc9cc8a1b8c1851 (diff) | |
download | crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.tar crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.tar.gz crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.tar.bz2 crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.tar.lz crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.tar.xz crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.tar.zst crosvm-62d21839e6aa160f6db1957be018f4cebe36e397.zip |
qcow: Add vec_cache
The `VecCache` struct will be used to represent the file clusters in caches. It ties a vector to a state of dirty or clean. Change-Id: I474eb67d2ad9f086da638ecc385ccce74737d3b9 Signed-off-by: Dylan Reid <dgreid@chromium.org> Reviewed-on: https://chromium-review.googlesource.com/1207451 Reviewed-by: Chirantan Ekbote <chirantan@chromium.org>
Diffstat (limited to 'qcow')
-rw-r--r-- | qcow/src/vec_cache.rs | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/qcow/src/vec_cache.rs b/qcow/src/vec_cache.rs new file mode 100644 index 0000000..4144eb4 --- /dev/null +++ b/qcow/src/vec_cache.rs @@ -0,0 +1,172 @@ +// Copyright 2018 The Chromium OS Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +use std::collections::hash_map::IterMut; +use std::collections::HashMap; +use std::io; +use std::ops::{Index, IndexMut}; + +/// Trait that allows for checking if an implementor is dirty. Useful for types that are cached so +/// it can be checked if they need to be committed to disk. +pub trait Cacheable { + /// Used to check if the item needs to be written out or if it can be discarded. + fn dirty(&self) -> bool; +} + +#[derive(Debug)] +/// Represents a vector that implements the `Cacheable` trait so it can be held in a cache. +pub struct VecCache<T: 'static + Copy + Default> { + vec: Box<[T]>, + dirty: bool, +} + +impl<T: 'static + Copy + Default> VecCache<T> { + /// Creates a `VecCache` that can hold `count` elements. + pub fn new(count: usize) -> VecCache<T> { + VecCache { + vec: vec![Default::default(); count].into_boxed_slice(), + dirty: true, + } + } + + /// Creates a `VecCache` from the passed in `vec`. + pub fn from_vec(vec: Vec<T>) -> VecCache<T> { + VecCache { + vec: vec.into_boxed_slice(), + dirty: false, + } + } + + /// Gets a reference to the underlying vector. + pub fn get_values(&self) -> &[T] { + &self.vec + } + + /// Mark this cache element as clean. + pub fn mark_clean(&mut self) { + self.dirty = false; + } +} + +impl<T: 'static + Copy + Default> Cacheable for VecCache<T> { + fn dirty(&self) -> bool { + self.dirty + } +} + +impl<T: 'static + Copy + Default> Index<usize> for VecCache<T> { + type Output = T; + + fn index(&self, index: usize) -> &T { + self.vec.index(index) + } +} + +impl<T: 'static + Copy + Default> IndexMut<usize> for VecCache<T> { + fn index_mut(&mut self, index: usize) -> &mut T { + self.dirty = true; + self.vec.index_mut(index) + } +} + +#[derive(Debug)] +pub struct CacheMap<T: Cacheable> { + capacity: usize, + map: HashMap<usize, T>, +} + +impl<T: Cacheable> CacheMap<T> { + pub fn new(capacity: usize) -> Self { + CacheMap { + capacity, + map: HashMap::with_capacity(capacity), + } + } + + pub fn contains_key(&self, key: &usize) -> bool { + self.map.contains_key(key) + } + + pub fn get(&self, index: &usize) -> Option<&T> { + self.map.get(index) + } + + pub fn get_mut(&mut self, index: &usize) -> Option<&mut T> { + self.map.get_mut(index) + } + + pub fn iter_mut(&mut self) -> IterMut<usize, T> { + self.map.iter_mut() + } + + // Check if the refblock cache is full and we need to evict. + pub fn insert<F>(&mut self, index: usize, block: T, write_callback: F) -> io::Result<()> + where + F: FnOnce(usize, T) -> io::Result<()>, + { + if self.map.len() == self.capacity { + // TODO(dgreid) - smarter eviction strategy. + let to_evict = *self.map.iter().nth(0).unwrap().0; + if let Some(evicted) = self.map.remove(&to_evict) { + if evicted.dirty() { + write_callback(to_evict, evicted)?; + } + } + } + self.map.insert(index, block); + Ok(()) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + struct NumCache(pub u64); + impl Cacheable for NumCache { + fn dirty(&self) -> bool { + true + } + } + + #[test] + fn evicts_when_full() { + let mut cache = CacheMap::<NumCache>::new(3); + let mut evicted = None; + cache + .insert(0, NumCache(5), |index, _| { + evicted = Some(index); + Ok(()) + }) + .unwrap(); + assert_eq!(evicted, None); + cache + .insert(1, NumCache(6), |index, _| { + evicted = Some(index); + Ok(()) + }) + .unwrap(); + assert_eq!(evicted, None); + cache + .insert(2, NumCache(7), |index, _| { + evicted = Some(index); + Ok(()) + }) + .unwrap(); + assert_eq!(evicted, None); + cache + .insert(3, NumCache(8), |index, _| { + evicted = Some(index); + Ok(()) + }) + .unwrap(); + assert!(evicted.is_some()); + + // Check that three of the four items inserted are still there and that the most recently + // inserted is one of them. + let num_items = (0..=3).filter(|k| cache.contains_key(&k)).count(); + assert_eq!(num_items, 3); + assert!(cache.contains_key(&3)); + } +} |