aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Li <li.davidm96@gmail.com>2016-01-24 15:55:50 -0500
committerDavid Li <li.davidm96@gmail.com>2016-01-24 15:55:50 -0500
commitc1fd66af614a1996d8e20f0e2789521de52dfc19 (patch)
tree52c449f2f64b3c5c061e5bafbe2d80de33076feb
parent210fff77d5ec0ab172aee309323168a052d489c3 (diff)
Provide API to react to cache events
-rw-r--r--src/cache.rs290
-rw-r--r--src/lib.rs12
-rw-r--r--src/memory.rs239
-rw-r--r--src/simulator.rs3
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;