1 /* Copyright (C) 2007-2008 The Android Open Source Project 2 ** 3 ** This software is licensed under the terms of the GNU General Public 4 ** License version 2, as published by the Free Software Foundation, and 5 ** may be copied, distributed, and modified under those terms. 6 ** 7 ** This program is distributed in the hope that it will be useful, 8 ** but WITHOUT ANY WARRANTY; without even the implied warranty of 9 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 ** GNU General Public License for more details. 11 */ 12 #include <stdio.h> 13 #include <stdlib.h> 14 #include <string.h> 15 #include "dcache.h" 16 #include "cpu.h" 17 #include "exec-all.h" 18 #include "trace.h" 19 #include "varint.h" 20 21 extern FILE *ftrace_debug; 22 23 int dcache_size = 16 * 1024; 24 int dcache_ways = 4; 25 int dcache_line_size = 32; 26 int dcache_replace_policy = kPolicyRandom; 27 int dcache_load_miss_penalty = 30; 28 int dcache_store_miss_penalty = 5; 29 30 typedef struct Dcache { 31 int size; 32 int ways; 33 int line_size; 34 int log_line_size; 35 int rows; 36 uint32_t addr_mask; 37 int replace_policy; 38 int next_way; 39 int extra_increment_counter; 40 int *replace; 41 uint32_t **table; 42 int load_miss_penalty; 43 int store_miss_penalty; 44 uint64_t load_hits; 45 uint64_t load_misses; 46 uint64_t store_hits; 47 uint64_t store_misses; 48 } Dcache; 49 50 Dcache dcache; 51 52 void dcache_cleanup(); 53 54 // Returns the log2 of "num" rounded up to the nearest integer. 55 int log2_roundup(int num) 56 { 57 int power2; 58 int exp; 59 60 for (exp = 0, power2 = 1; power2 < num; power2 <<= 1) { 61 exp += 1; 62 } 63 return exp; 64 } 65 66 void dcache_init(int size, int ways, int line_size, int replace_policy, 67 int load_miss_penalty, int store_miss_penalty) 68 { 69 int ii; 70 71 // Compute the logs of the params, rounded up 72 int log_size = log2_roundup(size); 73 int log_ways = log2_roundup(ways); 74 int log_line_size = log2_roundup(line_size); 75 76 // The number of rows in the table = size / (line_size * ways) 77 int log_rows = log_size - log_line_size - log_ways; 78 79 dcache.size = 1 << log_size; 80 dcache.ways = 1 << log_ways; 81 dcache.line_size = 1 << log_line_size; 82 dcache.log_line_size = log_line_size; 83 dcache.rows = 1 << log_rows; 84 dcache.addr_mask = (1 << log_rows) - 1; 85 86 // Allocate an array of pointers, one for each row 87 uint32_t **table = malloc(sizeof(uint32_t *) << log_rows); 88 89 // Allocate the data for the whole cache in one call to malloc() 90 int data_size = sizeof(uint32_t) << (log_rows + log_ways); 91 uint32_t *data = malloc(data_size); 92 93 // Fill the cache with invalid addresses 94 memset(data, ~0, data_size); 95 96 // Assign the pointers into the data array 97 int rows = dcache.rows; 98 for (ii = 0; ii < rows; ++ii) { 99 table[ii] = &data[ii << log_ways]; 100 } 101 dcache.table = table; 102 dcache.replace_policy = replace_policy; 103 dcache.next_way = 0; 104 dcache.extra_increment_counter = 0; 105 106 dcache.replace = NULL; 107 if (replace_policy == kPolicyRoundRobin) { 108 dcache.replace = malloc(sizeof(int) << log_rows); 109 memset(dcache.replace, 0, sizeof(int) << log_rows); 110 } 111 dcache.load_miss_penalty = load_miss_penalty; 112 dcache.store_miss_penalty = store_miss_penalty; 113 dcache.load_hits = 0; 114 dcache.load_misses = 0; 115 dcache.store_hits = 0; 116 dcache.store_misses = 0; 117 118 atexit(dcache_cleanup); 119 } 120 121 void dcache_stats() 122 { 123 uint64_t hits = dcache.load_hits + dcache.store_hits; 124 uint64_t misses = dcache.load_misses + dcache.store_misses; 125 uint64_t total = hits + misses; 126 double hit_per = 0; 127 double miss_per = 0; 128 if (total) { 129 hit_per = 100.0 * hits / total; 130 miss_per = 100.0 * misses / total; 131 } 132 printf("\n"); 133 printf("Dcache hits %10llu %6.2f%%\n", hits, hit_per); 134 printf("Dcache misses %10llu %6.2f%%\n", misses, miss_per); 135 printf("Dcache total %10llu\n", hits + misses); 136 } 137 138 void dcache_free() 139 { 140 free(dcache.table[0]); 141 free(dcache.table); 142 free(dcache.replace); 143 dcache.table = NULL; 144 } 145 146 void dcache_cleanup() 147 { 148 dcache_stats(); 149 dcache_free(); 150 } 151 152 void compress_trace_addresses(TraceAddr *trace_addr) 153 { 154 AddrRec *ptr; 155 char *comp_ptr = trace_addr->compressed_ptr; 156 uint32_t prev_addr = trace_addr->prev_addr; 157 uint64_t prev_time = trace_addr->prev_time; 158 AddrRec *last = &trace_addr->buffer[kMaxNumAddrs]; 159 for (ptr = trace_addr->buffer; ptr != last; ++ptr) { 160 if (comp_ptr >= trace_addr->high_water_ptr) { 161 uint32_t size = comp_ptr - trace_addr->compressed; 162 fwrite(trace_addr->compressed, sizeof(char), size, trace_addr->fstream); 163 comp_ptr = trace_addr->compressed; 164 } 165 166 int addr_diff = ptr->addr - prev_addr; 167 uint64_t time_diff = ptr->time - prev_time; 168 prev_addr = ptr->addr; 169 prev_time = ptr->time; 170 171 comp_ptr = varint_encode_signed(addr_diff, comp_ptr); 172 comp_ptr = varint_encode(time_diff, comp_ptr); 173 } 174 trace_addr->compressed_ptr = comp_ptr; 175 trace_addr->prev_addr = prev_addr; 176 trace_addr->prev_time = prev_time; 177 } 178 179 // This function is called by the generated code to simulate 180 // a dcache load access. 181 void dcache_load(uint32_t addr) 182 { 183 int ii; 184 int ways = dcache.ways; 185 uint32_t cache_addr = addr >> dcache.log_line_size; 186 int row = cache_addr & dcache.addr_mask; 187 //printf("ld %lld 0x%x\n", sim_time, addr); 188 for (ii = 0; ii < ways; ++ii) { 189 if (cache_addr == dcache.table[row][ii]) { 190 dcache.load_hits += 1; 191 #if 0 192 printf("dcache load hit addr: 0x%x cache_addr: 0x%x row %d way %d\n", 193 addr, cache_addr, row, ii); 194 #endif 195 // If we are tracing all addresses, then include this in the trace. 196 if (trace_all_addr) { 197 AddrRec *next = trace_load.next; 198 next->addr = addr; 199 next->time = sim_time; 200 next += 1; 201 if (next == &trace_load.buffer[kMaxNumAddrs]) { 202 // Compress the trace 203 compress_trace_addresses(&trace_load); 204 next = &trace_load.buffer[0]; 205 } 206 trace_load.next = next; 207 } 208 return; 209 } 210 } 211 // This is a cache miss 212 213 #if 0 214 if (ftrace_debug) 215 fprintf(ftrace_debug, "t%lld %08x\n", sim_time, addr); 216 #endif 217 if (trace_load.fstream) { 218 AddrRec *next = trace_load.next; 219 next->addr = addr; 220 next->time = sim_time; 221 next += 1; 222 if (next == &trace_load.buffer[kMaxNumAddrs]) { 223 // Compress the trace 224 compress_trace_addresses(&trace_load); 225 next = &trace_load.buffer[0]; 226 } 227 trace_load.next = next; 228 } 229 230 dcache.load_misses += 1; 231 sim_time += dcache.load_miss_penalty; 232 233 // Pick a way to replace 234 int way; 235 if (dcache.replace_policy == kPolicyRoundRobin) { 236 // Round robin replacement policy 237 way = dcache.replace[row]; 238 int next_way = way + 1; 239 if (next_way == dcache.ways) 240 next_way = 0; 241 dcache.replace[row] = next_way; 242 } else { 243 // Random replacement policy 244 way = dcache.next_way; 245 dcache.next_way += 1; 246 if (dcache.next_way >= dcache.ways) 247 dcache.next_way = 0; 248 249 // Every 13 replacements, add an extra increment to the next way 250 dcache.extra_increment_counter += 1; 251 if (dcache.extra_increment_counter == 13) { 252 dcache.extra_increment_counter = 0; 253 dcache.next_way += 1; 254 if (dcache.next_way >= dcache.ways) 255 dcache.next_way = 0; 256 } 257 } 258 #if 0 259 printf("dcache load miss addr: 0x%x cache_addr: 0x%x row %d replacing way %d\n", 260 addr, cache_addr, row, way); 261 #endif 262 dcache.table[row][way] = cache_addr; 263 } 264 265 // This function is called by the generated code to simulate 266 // a dcache store access. 267 void dcache_store(uint32_t addr, uint32_t val) 268 { 269 //printf("st %lld 0x%08x val 0x%x\n", sim_time, addr, val); 270 271 int ii; 272 int ways = dcache.ways; 273 uint32_t cache_addr = addr >> dcache.log_line_size; 274 int row = cache_addr & dcache.addr_mask; 275 for (ii = 0; ii < ways; ++ii) { 276 if (cache_addr == dcache.table[row][ii]) { 277 dcache.store_hits += 1; 278 #if 0 279 printf("dcache store hit addr: 0x%x cache_addr: 0x%x row %d way %d\n", 280 addr, cache_addr, row, ii); 281 #endif 282 // If we are tracing all addresses, then include this in the trace. 283 if (trace_all_addr) { 284 AddrRec *next = trace_store.next; 285 next->addr = addr; 286 next->time = sim_time; 287 next += 1; 288 if (next == &trace_store.buffer[kMaxNumAddrs]) { 289 // Compress the trace 290 compress_trace_addresses(&trace_store); 291 next = &trace_store.buffer[0]; 292 } 293 trace_store.next = next; 294 } 295 return; 296 } 297 } 298 // This is a cache miss 299 #if 0 300 printf("dcache store miss addr: 0x%x cache_addr: 0x%x row %d\n", 301 addr, cache_addr, row); 302 #endif 303 304 #if 0 305 if (ftrace_debug) 306 fprintf(ftrace_debug, "t%lld %08x\n", sim_time, addr); 307 #endif 308 309 if (trace_store.fstream) { 310 AddrRec *next = trace_store.next; 311 next->addr = addr; 312 next->time = sim_time; 313 next += 1; 314 if (next == &trace_store.buffer[kMaxNumAddrs]) { 315 // Compress the trace 316 compress_trace_addresses(&trace_store); 317 next = &trace_store.buffer[0]; 318 } 319 trace_store.next = next; 320 } 321 322 dcache.store_misses += 1; 323 sim_time += dcache.store_miss_penalty; 324 325 // Assume no write-allocate for now 326 } 327 328 // This function is called by the generated code to simulate 329 // a dcache load and store (swp) access. 330 void dcache_swp(uint32_t addr) 331 { 332 dcache_load(addr); 333 dcache_store(addr, 0); 334 } 335
