Initial Contribution

1 files changed, 342 insertions, 0 deletions

diff --git a/dcache.c b/dcache.c
new file mode 100644
index 0000000..7a55d0c
--- /dev/null
+++ b/dcache.c
@@ -0,0 +1,342 @@
+/* Copyright (C) 2007-2008 The Android Open Source Project
+**
+** This software is licensed under the terms of the GNU General Public
+** License version 2, as published by the Free Software Foundation, and
+** may be copied, distributed, and modified under those terms.
+**
+** This program 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.
+*/
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "dcache.h"
+#include "cpu.h"
+#include "exec-all.h"
+#include "trace.h"
+#include "varint.h"
+
+extern FILE *ftrace_debug;
+
+typedef struct Dcache {
+  int		size;
+  int		ways;
+  int		line_size;
+  int		log_line_size;
+  int		rows;
+  uint32_t	addr_mask;
+  int		replace_policy;
+  int		next_way;
+  int		extra_increment_counter;
+  int		*replace;
+  uint32_t	**table;
+  int		load_miss_penalty;
+  int		store_miss_penalty;
+  uint64_t	load_hits;
+  uint64_t	load_misses;
+  uint64_t	store_hits;
+  uint64_t	store_misses;
+} Dcache;
+
+Dcache dcache;
+
+void dcache_cleanup();
+
+// Returns the log2 of "num" rounded up to the nearest integer.
+int log2_roundup(int num)
+{
+  int power2;
+  int exp;
+
+  for (exp = 0, power2 = 1; power2 < num; power2 <<= 1) {
+    exp += 1;
+  }
+  return exp;
+}
+
+void dcache_init(int size, int ways, int line_size, int replace_policy,
+                 int load_miss_penalty, int store_miss_penalty)
+{
+  int ii;
+
+  // Compute the logs of the params, rounded up
+  int log_size = log2_roundup(size);
+  int log_ways = log2_roundup(ways);
+  int log_line_size = log2_roundup(line_size);
+
+  // The number of rows in the table = size / (line_size * ways)
+  int log_rows = log_size - log_line_size - log_ways;
+
+  dcache.size = 1 << log_size;
+  dcache.ways = 1 << log_ways;
+  dcache.line_size = 1 << log_line_size;
+  dcache.log_line_size = log_line_size;
+  dcache.rows = 1 << log_rows;
+  dcache.addr_mask = (1 << log_rows) - 1;
+
+  // Allocate an array of pointers, one for each row
+  uint32_t **table = malloc(sizeof(uint32_t *) << log_rows);
+
+  // Allocate the data for the whole cache in one call to malloc()
+  int data_size = sizeof(uint32_t) << (log_rows + log_ways);
+  uint32_t *data = malloc(data_size);
+
+  // Fill the cache with invalid addresses
+  memset(data, ~0, data_size);
+
+  // Assign the pointers into the data array
+  int rows = dcache.rows;
+  for (ii = 0; ii < rows; ++ii) {
+    table[ii] = &data[ii << log_ways];
+  }
+  dcache.table = table;
+  dcache.replace_policy = replace_policy;
+  dcache.next_way = 0;
+  dcache.extra_increment_counter = 0;
+
+  dcache.replace = NULL;
+  if (replace_policy == kPolicyRoundRobin) {
+    dcache.replace = malloc(sizeof(int) << log_rows);
+    memset(dcache.replace, 0, sizeof(int) << log_rows);
+  }
+  dcache.load_miss_penalty = load_miss_penalty;
+  dcache.store_miss_penalty = store_miss_penalty;
+  dcache.load_hits = 0;
+  dcache.load_misses = 0;
+  dcache.store_hits = 0;
+  dcache.store_misses = 0;
+
+  atexit(dcache_cleanup);
+}
+
+void dcache_stats()
+{
+  uint64_t hits = dcache.load_hits + dcache.store_hits;
+  uint64_t misses = dcache.load_misses + dcache.store_misses;
+  uint64_t total = hits + misses;
+  double hit_per = 0;
+  double miss_per = 0;
+  if (total) {
+    hit_per = 100.0 * hits / total;
+    miss_per = 100.0 * misses / total;
+  }
+  printf("\n");
+  printf("Dcache hits   %10llu %6.2f%%\n", hits, hit_per);
+  printf("Dcache misses %10llu %6.2f%%\n", misses, miss_per);
+  printf("Dcache total  %10llu\n", hits + misses);
+}
+
+void dcache_free()
+{
+  free(dcache.table[0]);
+  free(dcache.table);
+  free(dcache.replace);
+  dcache.table = NULL;
+}
+
+void dcache_cleanup()
+{
+  dcache_stats();
+  dcache_free();
+}
+
+void compress_trace_addresses(TraceAddr *trace_addr)
+{
+  AddrRec *ptr;
+  char *comp_ptr = trace_addr->compressed_ptr;
+  uint32_t prev_addr = trace_addr->prev_addr;
+  uint64_t prev_time = trace_addr->prev_time;
+  AddrRec *last = &trace_addr->buffer[kMaxNumAddrs];
+  for (ptr = trace_addr->buffer; ptr != last; ++ptr) {
+    if (comp_ptr >= trace_addr->high_water_ptr) {
+      uint32_t size = comp_ptr - trace_addr->compressed;
+      fwrite(trace_addr->compressed, sizeof(char), size, trace_addr->fstream);
+      comp_ptr = trace_addr->compressed;
+    }
+
+    int addr_diff = ptr->addr - prev_addr;
+    uint64_t time_diff = ptr->time - prev_time;
+    prev_addr = ptr->addr;
+    prev_time = ptr->time;
+
+    comp_ptr = varint_encode_signed(addr_diff, comp_ptr);
+    comp_ptr = varint_encode(time_diff, comp_ptr);
+  }
+  trace_addr->compressed_ptr = comp_ptr;
+  trace_addr->prev_addr = prev_addr;
+  trace_addr->prev_time = prev_time;
+}
+
+// This function is called by the generated code to simulate
+// a dcache load access.
+void dcache_load(uint32_t addr)
+{
+  int ii;
+  int ways = dcache.ways;
+  uint32_t cache_addr = addr >> dcache.log_line_size;
+  int row = cache_addr & dcache.addr_mask;
+  //printf("ld %lld 0x%x\n", sim_time, addr);
+  for (ii = 0; ii < ways; ++ii) {
+    if (cache_addr == dcache.table[row][ii]) {
+      dcache.load_hits += 1;
+#if 0
+      printf("dcache load hit  addr: 0x%x cache_addr: 0x%x row %d way %d\n",
+             addr, cache_addr, row, ii);
+#endif
+      // If we are tracing all addresses, then include this in the trace.
+      if (trace_all_addr) {
+        AddrRec *next = trace_load.next;
+        next->addr = addr;
+        next->time = sim_time;
+        next += 1;
+        if (next == &trace_load.buffer[kMaxNumAddrs]) {
+          // Compress the trace
+          compress_trace_addresses(&trace_load);
+          next = &trace_load.buffer[0];
+        }
+        trace_load.next = next;
+      }
+      return;
+    }
+  }
+  // This is a cache miss
+
+#if 0
+  if (ftrace_debug)
+    fprintf(ftrace_debug, "t%lld %08x\n", sim_time, addr);
+#endif
+  if (trace_load.fstream) {
+    AddrRec *next = trace_load.next;
+    next->addr = addr;
+    next->time = sim_time;
+    next += 1;
+    if (next == &trace_load.buffer[kMaxNumAddrs]) {
+      // Compress the trace
+      compress_trace_addresses(&trace_load);
+      next = &trace_load.buffer[0];
+    }
+    trace_load.next = next;
+  }
+
+  dcache.load_misses += 1;
+  sim_time += dcache.load_miss_penalty;
+
+  // Pick a way to replace
+  int way;
+  if (dcache.replace_policy == kPolicyRoundRobin) {
+    // Round robin replacement policy
+    way = dcache.replace[row];
+    int next_way = way + 1;
+    if (next_way == dcache.ways)
+      next_way = 0;
+    dcache.replace[row] = next_way;
+  } else {
+    // Random replacement policy
+    way = dcache.next_way;
+    dcache.next_way += 1;
+    if (dcache.next_way >= dcache.ways)
+      dcache.next_way = 0;
+
+    // Every 13 replacements, add an extra increment to the next way
+    dcache.extra_increment_counter += 1;
+    if (dcache.extra_increment_counter == 13) {
+      dcache.extra_increment_counter = 0;
+      dcache.next_way += 1;
+      if (dcache.next_way >= dcache.ways)
+        dcache.next_way = 0;
+    }
+  }
+#if 0
+  printf("dcache load miss addr: 0x%x cache_addr: 0x%x row %d replacing way %d\n",
+         addr, cache_addr, row, way);
+#endif
+  dcache.table[row][way] = cache_addr;
+}
+
+// This function is called by the generated code to simulate
+// a dcache store access.
+void dcache_store(uint32_t addr, uint32_t val)
+{
+  // Check for a write to a magic address (this is a virtual address)
+  //printf("st %lld 0x%08x val 0x%x\n", sim_time, addr, val);
+  if ((addr & kMagicBaseMask) == kMagicBaseAddr) {
+    uint32_t offset = addr & kMagicOffsetMask;
+    switch (offset) {
+    case kMethodTraceEnterOffset:
+        trace_interpreted_method(val, kMethodEnter);
+        break;
+    case kMethodTraceExitOffset:
+        trace_interpreted_method(val, kMethodExit);
+        break;
+    case kMethodTraceExceptionOffset:
+        trace_interpreted_method(val, kMethodException);
+        break;
+    }
+  }
+
+  int ii;
+  int ways = dcache.ways;
+  uint32_t cache_addr = addr >> dcache.log_line_size;
+  int row = cache_addr & dcache.addr_mask;
+  for (ii = 0; ii < ways; ++ii) {
+    if (cache_addr == dcache.table[row][ii]) {
+      dcache.store_hits += 1;
+#if 0
+      printf("dcache store hit  addr: 0x%x cache_addr: 0x%x row %d way %d\n",
+             addr, cache_addr, row, ii);
+#endif
+      // If we are tracing all addresses, then include this in the trace.
+      if (trace_all_addr) {
+        AddrRec *next = trace_store.next;
+        next->addr = addr;
+        next->time = sim_time;
+        next += 1;
+        if (next == &trace_store.buffer[kMaxNumAddrs]) {
+          // Compress the trace
+          compress_trace_addresses(&trace_store);
+          next = &trace_store.buffer[0];
+        }
+        trace_store.next = next;
+      }
+      return;
+    }
+  }
+  // This is a cache miss
+#if 0
+  printf("dcache store miss addr: 0x%x cache_addr: 0x%x row %d\n",
+         addr, cache_addr, row);
+#endif
+
+#if 0
+  if (ftrace_debug)
+    fprintf(ftrace_debug, "t%lld %08x\n", sim_time, addr);
+#endif
+
+  if (trace_store.fstream) {
+    AddrRec *next = trace_store.next;
+    next->addr = addr;
+    next->time = sim_time;
+    next += 1;
+    if (next == &trace_store.buffer[kMaxNumAddrs]) {
+      // Compress the trace
+      compress_trace_addresses(&trace_store);
+      next = &trace_store.buffer[0];
+    }
+    trace_store.next = next;
+  }
+
+  dcache.store_misses += 1;
+  sim_time += dcache.store_miss_penalty;
+
+  // Assume no write-allocate for now
+}
+
+// This function is called by the generated code to simulate
+// a dcache load and store (swp) access.
+void dcache_swp(uint32_t addr)
+{
+  dcache_load(addr);
+  dcache_store(addr, 0);
+}