Provide API to react to cache events

4 files changed, 301 insertions, 243 deletions

diff --git a/src/cache.rs b/src/cache.rs
new file mode 100644
index 0000000..57bda25
--- /dev/null
+++ b/src/cache.rs
@@ -0,0 +1,290 @@
+// Copyright 2015-2016 David Li
+// This file is part of rustv.
+
+// rustv is free software: you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// rustv is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with rustv.  If not, see <http://www.gnu.org/licenses/>.
+
+use std::rc::Rc;
+use std::cell::RefCell;
+
+use isa;
+use memory::{MemoryError, MemoryInterface, Result, SharedMemory};
+
+pub struct CacheMetadata {
+    /// How many sets are in the cache
+    pub num_sets: usize,
+    /// How many ways are in a set
+    pub num_ways: usize,
+    /// How many words are in a block/line
+    pub num_block_words: usize,
+    /// The tags currently in the cache, in order of set, then way
+    pub tags: Vec<Option<isa::Address>>,
+}
+
+pub trait CacheInterface : MemoryInterface {
+    fn cache_metadata(&self) -> CacheMetadata;
+}
+
+pub type SharedCache<'a> = Rc<RefCell<CacheInterface + 'a>>;
+
+#[derive(Clone,Copy)]
+pub struct CacheLocation {
+    pub tag: u32,
+    pub index: u32,
+    pub offset: u32,
+    pub way: u32,
+}
+
+#[derive(Clone)]
+struct FetchRequest {
+    address: isa::Address,
+    prefetch: bool, // is this a prefetch
+    cycles_left: u32,
+    location: CacheLocation,
+    data: Vec<isa::Word>, // hold data temporarily while we wait for an entire line
+    error: Option<MemoryError>, // in case next level returns an error
+    waiting_on: u32, // which word of the block are we waiting on
+}
+
+#[derive(Clone)]
+struct CacheBlock {
+    valid: bool,
+    tag: u32,
+    contents: Vec<isa::Word>,
+    fetch_request: Option<FetchRequest>,
+}
+
+pub trait CacheEventHandler {
+    fn block_fetched(&self, location: CacheLocation);
+}
+
+pub struct EmptyCacheEventHandler {}
+
+impl CacheEventHandler for EmptyCacheEventHandler {
+    fn block_fetched(&self, _: CacheLocation) {}
+}
+
+// TODO: probably want different caches for different strategies, and
+// investigate how LRU is implemented
+// TODO: use hashtable for a way?
+// TODO: hashtable-based FA cache?
+pub struct DirectMappedCache<'a, T: CacheEventHandler> {
+    num_sets: u32,
+    block_words: u32,
+    cache: Vec<CacheBlock>,
+    next_level: SharedMemory<'a>,
+    events: T,
+}
+
+impl<'a, T: CacheEventHandler> DirectMappedCache<'a, T> {
+    pub fn new(sets: u32, block_words: u32,
+               next_level: SharedMemory<'a>, events: T)
+               -> DirectMappedCache<'a, T> {
+        let set = CacheBlock {
+            valid: false,
+            tag: 0,
+            contents: vec![isa::Word(0); block_words as usize],
+            fetch_request: None,
+        };
+        DirectMappedCache {
+            num_sets: sets,
+            block_words: block_words,
+            cache: vec![set; sets as usize],
+            next_level: next_level,
+            events: events,
+        }
+    }
+
+    pub fn parse_address(&self, address: isa::Address) -> (u32, u32, u32) {
+        // TODO: use constant in ISA module for word->byte conversion
+        let offset_mask = (self.block_words * 4 - 1) as u32;
+        let offset = address & offset_mask;
+        let index_mask = (self.num_sets - 1) as u32;
+        let index_shift = 32 - (self.block_words * 4).leading_zeros() - 1;
+        let index = (address >> index_shift) & index_mask;
+        let tag_shift = index_shift + (32 - self.num_sets.leading_zeros()) - 1;
+        let tag = address >> tag_shift;
+
+        (tag.0, index.0, offset.0)
+    }
+
+    fn normalize_address(&self, address: isa::Address) -> isa::Address {
+        let offset_mask = !(self.block_words * 4 - 1);
+        address & offset_mask
+    }
+}
+
+impl<'a, T: CacheEventHandler> MemoryInterface for DirectMappedCache<'a, T> {
+    fn latency(&self) -> u32 {
+        0
+    }
+
+    fn step(&mut self) {
+        for set in self.cache.iter_mut() {
+            if let Some(ref mut fetch_request) = set.fetch_request {
+                // Start filling the cache once the cycles_left would
+                // have hit 0, so that the consumer never gets
+                // stall_cycles = 0
+                if fetch_request.cycles_left > 1 {
+                    fetch_request.cycles_left -= 1;
+                    return;
+                }
+                // read all the words in a line from the next
+                // level, until we get a stall
+
+                for offset in fetch_request.waiting_on..self.block_words {
+                    let result = self.next_level
+                        .borrow_mut()
+                        .read_word(fetch_request.address + (4 * offset));
+                    match result {
+                        Ok(data) => {
+                            fetch_request.data[offset as usize] = data;
+                            fetch_request.waiting_on += 1;
+                        },
+                        Err(MemoryError::CacheMiss { stall_cycles, .. }) => {
+                            fetch_request.cycles_left = stall_cycles;
+                            continue;
+                        },
+                        Err(MemoryError::InvalidAddress) => {
+                            fetch_request.error =
+                                Some(MemoryError::InvalidAddress);
+                            continue;
+                        }
+                    }
+                }
+
+                // All words fetched, write to cache
+                self.events.block_fetched(fetch_request.location);
+
+                set.tag = fetch_request.location.tag;
+                set.contents = fetch_request.data.clone();
+                set.valid = true;
+            }
+
+            set.fetch_request = None;
+        }
+    }
+
+    fn is_address_accessible(&self, address: isa::Address) -> bool {
+        let (tag, index, _) = self.parse_address(address);
+        let ref set = self.cache[index as usize];
+
+        set.valid && set.tag == tag
+    }
+
+    fn read_word(&mut self, address: isa::Address) -> Result<isa::Word> {
+        let normalized = self.normalize_address(address);
+        let stall = self.next_level.borrow().latency();
+        let (tag, index, offset) = self.parse_address(address);
+        let location = CacheLocation {
+            tag: tag,
+            index: index,
+            offset: offset,
+            way: 0,
+        };
+        let ref mut set = self.cache[index as usize];
+
+        if set.valid && set.tag == tag {
+            return Ok(set.contents[(offset / 4) as usize]);
+        }
+        else if let None = set.fetch_request {
+            set.fetch_request = Some(FetchRequest {
+                address: normalized,
+                prefetch: false,
+                cycles_left: stall,
+                location: location,
+                data: vec![isa::Word(0); self.block_words as usize],
+                error: None,
+                waiting_on: 0,
+            });
+        }
+        else if let Some(ref mut fetch_request) = set.fetch_request {
+            if let Some(ref err) = fetch_request.error {
+                if fetch_request.address == normalized {
+                    return Err(err.clone());
+                }
+                else {
+                    fetch_request.address = normalized;
+                    fetch_request.prefetch = false;
+                    fetch_request.cycles_left = stall;
+                    fetch_request.location = location;
+                    fetch_request.waiting_on = 0;
+                }
+            }
+            // Do the assignment outside the borrow of the error
+            fetch_request.error = None;
+
+            return Err(MemoryError::CacheMiss {
+                stall_cycles: fetch_request.cycles_left,
+                retry: true,
+            });
+        }
+
+        Err(MemoryError::CacheMiss {
+            stall_cycles: stall,
+            retry: true,
+        })
+    }
+
+    fn write_word(&mut self, address: isa::Address, value: isa::Word)
+                  -> Result<()> {
+        // Write-allocate policy
+        match self.read_word(address) {
+            Ok(_) => {
+                let (tag, index, offset) = self.parse_address(address);
+                let ref mut set = self.cache[index as usize];
+
+                if set.valid && set.tag == tag {
+                    set.contents[(offset / 4) as usize] = value;
+                    // Write-through policy
+                    let result = self.next_level.borrow_mut()
+                        .write_word(address, value);
+                    match result {
+                        Ok(()) => Ok(()),
+                        Err(e) => Err(e),
+                    }
+                }
+                else {
+                    panic!("Could not find supposedly read word");
+                }
+            },
+            Err(e) => Err(e),
+        }
+    }
+}
+
+impl<'a, T: CacheEventHandler> CacheInterface for DirectMappedCache<'a, T> {
+    fn cache_metadata(&self) -> CacheMetadata {
+        let tags = {
+            let mut tags = Vec::new();
+
+            for set in self.cache.iter() {
+                if set.valid {
+                    tags.push(Some(isa::Word(set.tag)));
+                }
+                else {
+                    tags.push(None);
+                }
+            }
+
+            tags
+        };
+
+        CacheMetadata {
+            num_sets: self.num_sets as usize,
+            num_ways: 1,
+            num_block_words: self.block_words as usize,
+            tags: tags,
+        }
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 2aee390..a4def64 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -18,6 +18,7 @@
            op_assign_traits, step_by)]
 extern crate elfloader32 as elfloader_lib;
 
+pub mod cache;
 pub mod isa;
 pub mod memory;
 pub mod register_file;
@@ -31,6 +32,7 @@ pub use elfloader_lib as elfloader;
 mod tests {
     #[test]
     fn cache_address_parsing() {
+        use cache::*;
         use isa::*;
         use memory::*;
         use std::rc::Rc;
@@ -38,8 +40,10 @@ mod tests {
 
         let memory = Memory::new(16);
         let memory_ref = Rc::new(RefCell::new(memory));
-        let dm_cache_word = DirectMappedCache::new(4, 1, memory_ref.clone());
-        let dm_cache_doubleword = DirectMappedCache::new(4, 2, memory_ref.clone());
+        let dm_cache_word = DirectMappedCache::new(
+            4, 1, memory_ref.clone(), EmptyCacheEventHandler {});
+        let dm_cache_doubleword = DirectMappedCache::new(
+            4, 2, memory_ref.clone(), EmptyCacheEventHandler {});
 
         assert_eq!(dm_cache_word.parse_address(Word(0xFFFFFFFD)),
                    (0xFFFFFFF, 3, 1));
@@ -52,6 +56,7 @@ mod tests {
         use std::rc::Rc;
         use std::cell::RefCell;
 
+        use cache::*;
         use isa::*;
         use memory::*;
 
@@ -104,7 +109,8 @@ mod tests {
         });
 
         let memory_ref = Rc::new(RefCell::new(memory));
-        let mut dm_cache = DirectMappedCache::new(4, 4, memory_ref.clone());
+        let mut dm_cache = DirectMappedCache::new(
+            4, 4, memory_ref.clone(), EmptyCacheEventHandler {});
 
         assert_eq!(dm_cache.read_word(Word(0x10)), stall);
 
diff --git a/src/memory.rs b/src/memory.rs
index 958ef21..33a9503 100644
--- a/src/memory.rs
+++ b/src/memory.rs
@@ -123,23 +123,8 @@ pub trait MemoryInterface {
     }
 }
 
-pub struct CacheMetadata {
-    /// How many sets are in the cache
-    pub num_sets: usize,
-    /// How many ways are in a set
-    pub num_ways: usize,
-    /// How many words are in a block/line
-    pub num_block_words: usize,
-    /// The tags currently in the cache, in order of set, then way
-    pub tags: Vec<Option<isa::Address>>,
-}
-
-pub trait CacheInterface : MemoryInterface {
-    fn cache_metadata(&self) -> CacheMetadata;
-}
 
 pub type SharedMemory<'a> = Rc<RefCell<MemoryInterface + 'a>>;
-pub type SharedCache<'a> = Rc<RefCell<CacheInterface + 'a>>;
 
 pub trait Mmu {
     fn translate(&self, address: isa::Address) -> isa::Address;
@@ -181,36 +166,6 @@ pub struct Memory {
     memory: Vec<u32>,
 }
 
-#[derive(Clone)]
-struct FetchRequest {
-    address: isa::Address,
-    prefetch: bool, // is this a prefetch
-    cycles_left: u32,
-    tag: u32,
-    data: Vec<isa::Word>, // hold data temporarily while we wait for an entire line
-    error: Option<MemoryError>, // in case next level returns an error
-    waiting_on: u32, // which word of the block are we waiting on
-}
-
-#[derive(Clone)]
-struct CacheBlock {
-    valid: bool,
-    tag: u32,
-    contents: Vec<isa::Word>,
-    fetch_request: Option<FetchRequest>,
-}
-
-// TODO: probably want different caches for different strategies, and
-// investigate how LRU is implemented
-// TODO: use hashtable for a way?
-// TODO: hashtable-based FA cache?
-pub struct DirectMappedCache<'a> {
-    num_sets: u32,
-    block_words: u32,
-    cache: Vec<CacheBlock>,
-    next_level: SharedMemory<'a>,
-}
-
 fn copy_u8_into_u32<T: Mmu>(mmu: &T, base: usize, src: &[u8], dst: &mut [u32]) {
     for (offset, word) in src.chunks(4).enumerate() {
         let word = if word.len() == 4 {
@@ -289,197 +244,3 @@ impl MemoryInterface for Memory {
             .map(Instruction::new)
     }
 }
-
-impl<'a> DirectMappedCache<'a> {
-    pub fn new(sets: u32, block_words: u32, next_level: SharedMemory<'a>)
-               -> DirectMappedCache<'a> {
-        let set = CacheBlock {
-            valid: false,
-            tag: 0,
-            contents: vec![isa::Word(0); block_words as usize],
-            fetch_request: None,
-        };
-        DirectMappedCache {
-            num_sets: sets,
-            block_words: block_words,
-            cache: vec![set; sets as usize],
-            next_level: next_level,
-        }
-    }
-
-    pub fn parse_address(&self, address: isa::Address) -> (u32, u32, u32) {
-        // TODO: use constant in ISA module for word->byte conversion
-        let offset_mask = (self.block_words * 4 - 1) as u32;
-        let offset = address & offset_mask;
-        let index_mask = (self.num_sets - 1) as u32;
-        let index_shift = 32 - (self.block_words * 4).leading_zeros() - 1;
-        let index = (address >> index_shift) & index_mask;
-        let tag_shift = index_shift + (32 - self.num_sets.leading_zeros()) - 1;
-        let tag = address >> tag_shift;
-
-        (tag.0, index.0, offset.0)
-    }
-
-    fn normalize_address(&self, address: isa::Address) -> isa::Address {
-        let offset_mask = !(self.block_words * 4 - 1);
-        address & offset_mask
-    }
-}
-
-impl<'a> MemoryInterface for DirectMappedCache<'a> {
-    fn latency(&self) -> u32 {
-        0
-    }
-
-    fn step(&mut self) {
-        for set in self.cache.iter_mut() {
-            if let Some(ref mut fetch_request) = set.fetch_request {
-                // Start filling the cache once the cycles_left would
-                // have hit 0, so that the consumer never gets
-                // stall_cycles = 0
-                if fetch_request.cycles_left > 1 {
-                    fetch_request.cycles_left -= 1;
-                    return;
-                }
-                // read all the words in a line from the next
-                // level, until we get a stall
-
-                for offset in fetch_request.waiting_on..self.block_words {
-                    let result = self.next_level
-                        .borrow_mut()
-                        .read_word(fetch_request.address + (4 * offset));
-                    match result {
-                        Ok(data) => {
-                            fetch_request.data[offset as usize] = data;
-                            fetch_request.waiting_on += 1;
-                        },
-                        Err(MemoryError::CacheMiss { stall_cycles, .. }) => {
-                            fetch_request.cycles_left = stall_cycles;
-                            continue;
-                        },
-                        Err(MemoryError::InvalidAddress) => {
-                            fetch_request.error =
-                                Some(MemoryError::InvalidAddress);
-                            continue;
-                        }
-                    }
-                }
-
-                // All words fetched, write to cache
-                set.tag = fetch_request.tag;
-                set.contents = fetch_request.data.clone();
-                set.valid = true;
-            }
-
-            set.fetch_request = None;
-        }
-    }
-
-    fn is_address_accessible(&self, address: isa::Address) -> bool {
-        let (tag, index, _) = self.parse_address(address);
-        let ref set = self.cache[index as usize];
-
-        set.valid && set.tag == tag
-    }
-
-    fn read_word(&mut self, address: isa::Address) -> Result<isa::Word> {
-        let normalized = self.normalize_address(address);
-        let (new_tag, _, _) = self.parse_address(address);
-        let stall = self.next_level.borrow().latency();
-        let (tag, index, offset) = self.parse_address(address);
-        let ref mut set = self.cache[index as usize];
-
-        if set.valid && set.tag == tag {
-            return Ok(set.contents[(offset / 4) as usize]);
-        }
-        else if let None = set.fetch_request {
-            set.fetch_request = Some(FetchRequest {
-                address: normalized,
-                prefetch: false,
-                cycles_left: stall,
-                tag: new_tag,
-                data: vec![isa::Word(0); self.block_words as usize],
-                error: None,
-                waiting_on: 0,
-            });
-        }
-        else if let Some(ref mut fetch_request) = set.fetch_request {
-            if let Some(ref err) = fetch_request.error {
-                if fetch_request.address == normalized {
-                    return Err(err.clone());
-                }
-                else {
-                    fetch_request.address = normalized;
-                    fetch_request.prefetch = false;
-                    fetch_request.cycles_left = stall;
-                    fetch_request.tag = new_tag;
-                    fetch_request.waiting_on = 0;
-                }
-            }
-            // Do the assignment outside the borrow of the error
-            fetch_request.error = None;
-
-            return Err(MemoryError::CacheMiss {
-                stall_cycles: fetch_request.cycles_left,
-                retry: true,
-            });
-        }
-
-        Err(MemoryError::CacheMiss {
-            stall_cycles: stall,
-            retry: true,
-        })
-    }
-
-    fn write_word(&mut self, address: isa::Address, value: isa::Word)
-                  -> Result<()> {
-        // Write-allocate policy
-        match self.read_word(address) {
-            Ok(_) => {
-                let (tag, index, offset) = self.parse_address(address);
-                let ref mut set = self.cache[index as usize];
-
-                if set.valid && set.tag == tag {
-                    set.contents[(offset / 4) as usize] = value;
-                    // Write-through policy
-                    let result = self.next_level.borrow_mut()
-                        .write_word(address, value);
-                    match result {
-                        Ok(()) => Ok(()),
-                        Err(e) => Err(e),
-                    }
-                }
-                else {
-                    panic!("Could not find supposedly read word");
-                }
-            },
-            Err(e) => Err(e),
-        }
-    }
-}
-
-impl<'a> CacheInterface for DirectMappedCache<'a> {
-    fn cache_metadata(&self) -> CacheMetadata {
-        let tags = {
-            let mut tags = Vec::new();
-
-            for set in self.cache.iter() {
-                if set.valid {
-                    tags.push(Some(isa::Word(set.tag)));
-                }
-                else {
-                    tags.push(None);
-                }
-            }
-
-            tags
-        };
-
-        CacheMetadata {
-            num_sets: self.num_sets as usize,
-            num_ways: 1,
-            num_block_words: self.block_words as usize,
-            tags: tags,
-        }
-    }
-}
diff --git a/src/simulator.rs b/src/simulator.rs
index 9071599..005dd0e 100644
--- a/src/simulator.rs
+++ b/src/simulator.rs
@@ -14,9 +14,10 @@
 // You should have received a copy of the GNU General Public License
 // along with rustv.  If not, see <http://www.gnu.org/licenses/>.
 
+use cache::SharedCache;
 use isa;
 use isa::IsaType;
-use memory::{MemoryInterface, MemoryError, Mmu, SharedCache, SharedMemory};
+use memory::{MemoryInterface, MemoryError, Mmu, SharedMemory};
 use register_file::RegisterFile;
 use syscall::SyscallHandler;
 use trap::Trap;