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.
log2_roundup(int num)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
dcache_init(int size,int ways,int line_size,int replace_policy,int load_miss_penalty,int store_miss_penalty)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
dcache_stats()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
dcache_free()138 void dcache_free()
139 {
140 free(dcache.table[0]);
141 free(dcache.table);
142 free(dcache.replace);
143 dcache.table = NULL;
144 }
145
dcache_cleanup()146 void dcache_cleanup()
147 {
148 dcache_stats();
149 dcache_free();
150 }
151
compress_trace_addresses(TraceAddr * trace_addr)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.
dcache_load(uint32_t addr)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.
dcache_store(uint32_t addr,uint32_t val)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.
dcache_swp(uint32_t addr)330 void dcache_swp(uint32_t addr)
331 {
332 dcache_load(addr);
333 dcache_store(addr, 0);
334 }
335