Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * OpenSPARC T2 Processor File: hash.H | |
5 | * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
6 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES. | |
7 | * | |
8 | * The above named program is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU General Public | |
10 | * License version 2 as published by the Free Software Foundation. | |
11 | * | |
12 | * The above named program is distributed in the hope that it will be | |
13 | * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | * General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public | |
18 | * License along with this work; if not, write to the Free Software | |
19 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. | |
20 | * | |
21 | * ========== Copyright Header End ============================================ | |
22 | */ | |
23 | // ========== Copyright Header Begin ========================================== | |
24 | // | |
25 | // OpenSPARC T2 Processor File: hash.H | |
26 | // Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
27 | // DO NOT ALTER OR REMOVE COPYRIGHT NOTICES. | |
28 | // | |
29 | // The above named program is free software; you can redistribute it and/or | |
30 | // modify it under the terms of the GNU General Public | |
31 | // License version 2 as published by the Free Software Foundation. | |
32 | // | |
33 | // The above named program is distributed in the hope that it will be | |
34 | // useful, but WITHOUT ANY WARRANTY; without even the implied warranty of | |
35 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
36 | // General Public License for more details. | |
37 | // | |
38 | // You should have received a copy of the GNU General Public | |
39 | // License along with this work; if not, write to the Free Software | |
40 | // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. | |
41 | // | |
42 | // ========== Copyright Header End ============================================ | |
43 | #ifndef _HASH_H | |
44 | #define _HASH_H | |
45 | ||
46 | // File: hash.H | |
47 | // | |
48 | // Date: August 23, 2000 | |
49 | // | |
50 | #include <string.h> | |
51 | ||
52 | #include "rstf/rstf.h" | |
53 | ||
54 | // table size = HASH_TBL_ASSOC * HASH_TBL_SIZE | |
55 | #define HASH_TBL_ASSOC (4) | |
56 | #define HASH_TBL_SIZE (3391) // 1013, 2371, 3391, 4093, 6073, 8093 are prime | |
57 | ||
58 | #define HASH_FUNC_STRING "((pc >> 2) * 47) % HASH_TBL_SIZE" | |
59 | ||
60 | #define NOT_FOUND (-1) | |
61 | ||
62 | typedef struct { | |
63 | uint8_t timestamp; | |
64 | ||
65 | uint16_t num_instr; | |
66 | uint16_t num_ea; | |
67 | // uint16_t instr_buf_size; | |
68 | // uint16_t ea_buf_size; | |
69 | ||
70 | uint64_t pc_start; | |
71 | ||
72 | uint32_t* instr_buf; | |
73 | uint64_t* ea_buf; | |
74 | } hash_table_t; | |
75 | ||
76 | class RstzipHash { | |
77 | public: | |
78 | // constructor (zeros table[][]) | |
79 | RstzipHash() { | |
80 | hash_init(); | |
81 | } // RstzipHash::RstzipHash() | |
82 | ||
83 | // destructor (frees table[][]) | |
84 | ~RstzipHash() { | |
85 | hash_close(); | |
86 | } // RstzipHash::RstzipHash() | |
87 | ||
88 | void hash_init() { | |
89 | memset(table, 0, HASH_TBL_ASSOC * HASH_TBL_SIZE * sizeof(hash_table_t)); | |
90 | } | |
91 | ||
92 | void hash_close() { | |
93 | int i, j; | |
94 | ||
95 | for (i = 0; i < HASH_TBL_ASSOC; i++) { | |
96 | for (j = 0; j < HASH_TBL_SIZE; j++) { | |
97 | if (table[i][j].instr_buf != NULL) { | |
98 | trz_free(table[i][j].instr_buf, table[i][j].num_instr * sizeof(uint32_t)); | |
99 | } | |
100 | ||
101 | if (table[i][j].ea_buf != NULL) { | |
102 | trz_free(table[i][j].ea_buf, table[i][j].num_ea * sizeof(uint64_t)); | |
103 | } | |
104 | } | |
105 | } | |
106 | } | |
107 | ||
108 | int search(uint64_t pc_start, int num_instr, | |
109 | uint32_t instr_buf[], int hashval) { | |
110 | int i, j; | |
111 | ||
112 | for (i = 0; i < HASH_TBL_ASSOC; i++) { | |
113 | if (table[i][hashval].pc_start == pc_start) { | |
114 | if (table[i][hashval].num_instr >= num_instr) { | |
115 | if (instr_buf != NULL) { | |
116 | for (j = 0; j < num_instr; j++) { | |
117 | if (table[i][hashval].instr_buf[j] != instr_buf[j]) { | |
118 | return NOT_FOUND; | |
119 | } | |
120 | } | |
121 | ||
122 | return i; | |
123 | } else { | |
124 | return i; | |
125 | } | |
126 | } | |
127 | } | |
128 | } | |
129 | ||
130 | return NOT_FOUND; | |
131 | } // RstzipHash::search() | |
132 | ||
133 | hash_table_t* read(int set, int hashval) { | |
134 | return &table[set][hashval]; | |
135 | } // RstzipHash::read() | |
136 | ||
137 | void write(uint64_t pc_start, | |
138 | uint16_t num_instr, uint32_t instr_buf[], | |
139 | uint16_t num_ea, uint64_t ea_buf[], | |
140 | int hashval) { | |
141 | int set = replace(pc_start, hashval); | |
142 | hash_table_t* tbl = &table[set][hashval]; | |
143 | ||
144 | copy_instr_buf(tbl, instr_buf, num_instr); | |
145 | copy_ea_buf(tbl, ea_buf, num_ea); | |
146 | ||
147 | tbl->pc_start = pc_start; | |
148 | tbl->num_instr = num_instr; | |
149 | tbl->num_ea = num_ea; | |
150 | ||
151 | // No need to update if timestamp was HASH_TBL_ASSOC - 1 already | |
152 | if (tbl->timestamp != HASH_TBL_ASSOC - 1) { | |
153 | update(num_ea, ea_buf, hashval); | |
154 | } | |
155 | } // RstzipHash::write() | |
156 | ||
157 | void update(int num_ea, uint64_t ea_buf[], | |
158 | int hashval, int index = NOT_FOUND) { | |
159 | int i; | |
160 | uint8_t prev_timestamp; | |
161 | ||
162 | if (index == NOT_FOUND) { | |
163 | prev_timestamp = 0; | |
164 | } else { | |
165 | prev_timestamp = table[index][hashval].timestamp; | |
166 | } | |
167 | ||
168 | for (i = 0; i < HASH_TBL_ASSOC; i++) { | |
169 | if (table[i][hashval].timestamp > prev_timestamp) { | |
170 | table[i][hashval].timestamp--; | |
171 | } | |
172 | } | |
173 | ||
174 | if (index != NOT_FOUND) { | |
175 | table[index][hashval].timestamp = HASH_TBL_ASSOC - 1; | |
176 | memcpy(table[index][hashval].ea_buf, ea_buf, num_ea * sizeof(uint64_t)); | |
177 | } | |
178 | } // RstzipHash::update() | |
179 | ||
180 | int hash(uint64_t pc) { | |
181 | return (int) (((pc >> 2) * 47) % HASH_TBL_SIZE); | |
182 | } // RstzipHash::hash() | |
183 | ||
184 | #define SEGMENT_SIZE (512) | |
185 | ||
186 | size_t get_segment_size(long num, size_t size) { | |
187 | return (((num * size) / SEGMENT_SIZE) + 1) * SEGMENT_SIZE; | |
188 | } | |
189 | ||
190 | void print_table(hash_table_t* tbl) { | |
191 | int i; | |
192 | ||
193 | fprintf(stdout, "Hash Table [%d]:\n", tbl->timestamp); | |
194 | fprintf(stdout, " pc_start=0x%llx\n", tbl->pc_start); | |
195 | fprintf(stdout, " num_instr=%d\n", tbl->num_instr); | |
196 | fprintf(stdout, " num_ea=%d\n", tbl->num_ea); | |
197 | fflush(stdout); | |
198 | ||
199 | for (i = 0; i < tbl->num_instr; i++) { | |
200 | fprintf(stdout, " instr_buf[%d]=0x%08x\n", i, tbl->instr_buf[i]); | |
201 | } | |
202 | fprintf(stdout, "\n"); | |
203 | ||
204 | for (i = 0; i < tbl->num_ea; i++) { | |
205 | fprintf(stdout, " ea_buf[%d]=0x%016llx\n", i, tbl->ea_buf[i]); | |
206 | } | |
207 | fprintf(stdout, "\n"); | |
208 | ||
209 | fflush(stdout); | |
210 | } // RstzipHash::print_table() | |
211 | ||
212 | void print_set(int hashval) { | |
213 | int i; | |
214 | ||
215 | fprintf(stdout, "hashval=%d\n", hashval); | |
216 | for (i = 0; i < HASH_TBL_ASSOC; i++) { | |
217 | print_table(&table[i][hashval]); | |
218 | } | |
219 | } | |
220 | ||
221 | void print() { | |
222 | int i, j; | |
223 | ||
224 | for (i = 0; i < HASH_TBL_ASSOC; i++) { | |
225 | for (j = 0; j < HASH_TBL_SIZE; j++) { | |
226 | if (table[i][j].pc_start) { | |
227 | fprintf(stdout, "1"); | |
228 | } else { | |
229 | fprintf(stdout, "0"); | |
230 | } | |
231 | } | |
232 | ||
233 | fprintf(stdout, "\n\n"); | |
234 | } | |
235 | } // RstzipHash::print() | |
236 | ||
237 | #if 0 | |
238 | ||
239 | #define MALLOC_WORD (0xbaddcafe) | |
240 | ||
241 | void* trz_malloc(size_t size) { | |
242 | int* ptr; | |
243 | ||
244 | if (size % 4 != 0) { | |
245 | fprintf(stderr, "Error: size param in RstzipHash::trz_malloc() is not word aligned (%u)\n", size); | |
246 | exit(2); | |
247 | } | |
248 | ||
249 | ptr = (int*) calloc(1, size); | |
250 | ||
251 | if (ptr == NULL) { | |
252 | fprintf(stderr, "Error: unable to alloc %d bytes in RstzipHash::trz_malloc()\n", size); | |
253 | exit(2); | |
254 | } | |
255 | ||
256 | #ifdef _DEBUG0 | |
257 | for (int i = 0; i < size / 4; i++) { | |
258 | ptr[i] = MALLOC_WORD; | |
259 | } | |
260 | #endif | |
261 | ||
262 | return (void*) ptr; | |
263 | } | |
264 | ||
265 | #define FREE_WORD (0xdeadbeef) | |
266 | ||
267 | void trz_free(void* ptr, size_t size) { | |
268 | #ifdef _DEBUG0 | |
269 | int* int_ptr = (int*) ptr; | |
270 | #endif | |
271 | ||
272 | if (size > 0) { | |
273 | if (size % 4 != 0) { | |
274 | fprintf(stderr, "Error: size param in RstzipHash::trz_free() is not word aligned (%u)\n", size); | |
275 | exit(2); | |
276 | } | |
277 | ||
278 | #ifdef _DEBUG0 | |
279 | for (int i = 0; i < size / 4; i++) { | |
280 | int_ptr[i] = FREE_WORD; | |
281 | } | |
282 | #endif | |
283 | } | |
284 | ||
285 | free(ptr); | |
286 | } | |
287 | ||
288 | #else | |
289 | ||
290 | void* trz_malloc(size_t size) { | |
291 | return calloc(1, size); | |
292 | } | |
293 | ||
294 | void trz_free(void* ptr, size_t size) { | |
295 | size = 0; | |
296 | free(ptr); | |
297 | } | |
298 | ||
299 | #endif | |
300 | ||
301 | protected: | |
302 | hash_table_t table[HASH_TBL_ASSOC][HASH_TBL_SIZE]; | |
303 | ||
304 | void invalidate(hash_table_t* tbl) { | |
305 | trz_free(tbl->instr_buf, tbl->num_instr * sizeof(uint32_t)); | |
306 | ||
307 | tbl->timestamp = 0; | |
308 | tbl->pc_start = 0; | |
309 | tbl->num_instr = 0; | |
310 | } | |
311 | ||
312 | int replace(uint64_t pc_start, int hashval) { | |
313 | int i; | |
314 | ||
315 | for (i = 0; i < HASH_TBL_ASSOC; i++) { | |
316 | if (table[i][hashval].timestamp == 0) { | |
317 | table[i][hashval].timestamp = HASH_TBL_ASSOC; | |
318 | return i; | |
319 | } | |
320 | } | |
321 | ||
322 | fprintf(stderr, "Error: no pc=0x%llx or timestamp=0 found at hashval=%d in " | |
323 | "Hash_Table_C::replace()\n", pc_start, hashval); | |
324 | exit(2); | |
325 | } // RstzipHash::replace() | |
326 | ||
327 | void copy_instr_buf(hash_table_t* tbl, uint32_t instr_buf[], int num_instr) { | |
328 | size_t old_segment_size, new_segment_size; | |
329 | ||
330 | old_segment_size = get_segment_size(tbl->num_instr, sizeof(uint32_t)); | |
331 | new_segment_size = get_segment_size(num_instr, sizeof(uint32_t)); | |
332 | ||
333 | if (old_segment_size != new_segment_size || tbl->instr_buf == NULL) { | |
334 | if (tbl->instr_buf != NULL) { | |
335 | trz_free(tbl->instr_buf, tbl->num_instr * sizeof(uint32_t)); | |
336 | } | |
337 | ||
338 | tbl->instr_buf = (uint32_t*) trz_malloc(new_segment_size); | |
339 | ||
340 | if (tbl->instr_buf == NULL) { | |
341 | fprintf(stderr, "Error: unable to malloc %d bytes in " | |
342 | "RstzipHash::copy_instr_buf()\n", | |
343 | new_segment_size); | |
344 | exit(2); | |
345 | } | |
346 | } | |
347 | ||
348 | //tbl->num_instr = num_instr; | |
349 | ||
350 | memcpy(tbl->instr_buf, instr_buf, num_instr * sizeof(uint32_t)); | |
351 | } // RstzipHash::copy_instr_buf() | |
352 | ||
353 | void copy_ea_buf(hash_table_t* tbl, uint64_t ea_buf[], int num_ea) { | |
354 | size_t old_segment_size, new_segment_size; | |
355 | ||
356 | old_segment_size = get_segment_size(tbl->num_ea, sizeof(uint64_t)); | |
357 | new_segment_size = get_segment_size(num_ea, sizeof(uint64_t)); | |
358 | ||
359 | if (old_segment_size < new_segment_size || tbl->ea_buf == NULL) { | |
360 | if (tbl->ea_buf != NULL) { | |
361 | trz_free(tbl->ea_buf, tbl->num_ea * sizeof(uint64_t)); | |
362 | } | |
363 | ||
364 | tbl->ea_buf = (uint64_t*) trz_malloc(2 * new_segment_size); | |
365 | ||
366 | if (tbl->ea_buf == NULL) { | |
367 | fprintf(stderr, "Error: unable to malloc %d bytes in RstzipHash::copy_ea_buf()\n", | |
368 | new_segment_size); | |
369 | exit(2); | |
370 | } | |
371 | } | |
372 | ||
373 | //tbl->num_ea = num_ea; | |
374 | ||
375 | memcpy(tbl->ea_buf, ea_buf, num_ea * sizeof(uint64_t)); | |
376 | } // RstzipHash::copy_ea_buf() | |
377 | ||
378 | }; // RstzipHash | |
379 | ||
380 | // This *MUST* correspond to the number of compressed pavadiff | |
381 | // rtypes in librstzip.H !!!! | |
382 | #define PAVADIFF_CACHESIZE (8) | |
383 | ||
384 | typedef struct { | |
385 | uint8_t timestamp; | |
386 | rstf_pavadiffT rst; | |
387 | } pavadiff_table_t; | |
388 | ||
389 | class RstzipPavadiffCache { | |
390 | public: | |
391 | RstzipPavadiffCache() { | |
392 | pavadiff_cache_init(); | |
393 | } | |
394 | ||
395 | void pavadiff_cache_init() { | |
396 | memset(table, 0, PAVADIFF_CACHESIZE * sizeof(pavadiff_table_t)); | |
397 | } | |
398 | ||
399 | int search(rstf_pavadiffT* rst) { | |
400 | int i; | |
401 | ||
402 | for (i = 0; i < PAVADIFF_CACHESIZE; i++) { | |
403 | if (memcmp(&table[i].rst, rst, sizeof(rstf_pavadiffT)) == 0) { | |
404 | return i; | |
405 | } else if (rst->ea_valid == 0) { | |
406 | if (memcmp(&table[i].rst, rst, sizeof(rstf_pavadiffT) - sizeof(rst->ea_pa_va)) == 0) { | |
407 | return i; | |
408 | } | |
409 | } | |
410 | } | |
411 | ||
412 | return NOT_FOUND; | |
413 | } | |
414 | ||
415 | rstf_pavadiffT* read(int index) { | |
416 | return &table[index].rst; | |
417 | } | |
418 | ||
419 | void write(rstf_pavadiffT* rst) { | |
420 | int index = replace(); | |
421 | ||
422 | table[index].rst = *rst; | |
423 | ||
424 | if (table[index].timestamp != PAVADIFF_CACHESIZE - 1) { | |
425 | update(); | |
426 | } | |
427 | } | |
428 | ||
429 | void update(int index = NOT_FOUND) { | |
430 | int i; | |
431 | uint8_t prev_timestamp; | |
432 | ||
433 | if (index == NOT_FOUND) { | |
434 | prev_timestamp = 0; | |
435 | } else { | |
436 | prev_timestamp = table[index].timestamp; | |
437 | } | |
438 | ||
439 | for (i = 0; i < PAVADIFF_CACHESIZE; i++) { | |
440 | if (table[i].timestamp > prev_timestamp) { | |
441 | table[i].timestamp--; | |
442 | } | |
443 | } | |
444 | ||
445 | if (index != NOT_FOUND) { | |
446 | table[index].timestamp = PAVADIFF_CACHESIZE - 1; | |
447 | } | |
448 | } | |
449 | ||
450 | protected: | |
451 | pavadiff_table_t table[PAVADIFF_CACHESIZE]; | |
452 | ||
453 | int replace() { | |
454 | int i; | |
455 | ||
456 | for (i = 0; i < PAVADIFF_CACHESIZE; i++) { | |
457 | if (table[i].timestamp == 0) { | |
458 | table[i].timestamp = PAVADIFF_CACHESIZE; | |
459 | return i; | |
460 | } | |
461 | } | |
462 | ||
463 | fprintf(stderr, | |
464 | "Error: no timestamp=0 found in Pavadiff_Cache::replace()\n"); | |
465 | exit(2); | |
466 | } | |
467 | }; | |
468 | ||
469 | #endif // _HASH_H |