sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 1 | |
| 2 | /*--------------------------------------------------------------------*/ |
| 3 | /*--- Management of the translation table and cache. ---*/ |
| 4 | /*--- vg_transtab.c ---*/ |
| 5 | /*--------------------------------------------------------------------*/ |
| 6 | |
| 7 | /* |
njn | c953984 | 2002-10-02 13:26:35 +0000 | [diff] [blame] | 8 | This file is part of Valgrind, an extensible x86 protected-mode |
| 9 | emulator for monitoring program execution on x86-Unixes. |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 10 | |
| 11 | Copyright (C) 2000-2002 Julian Seward |
| 12 | jseward@acm.org |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 13 | |
| 14 | This program is free software; you can redistribute it and/or |
| 15 | modify it under the terms of the GNU General Public License as |
| 16 | published by the Free Software Foundation; either version 2 of the |
| 17 | License, or (at your option) any later version. |
| 18 | |
| 19 | This program is distributed in the hope that it will be useful, but |
| 20 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 21 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 22 | General Public License for more details. |
| 23 | |
| 24 | You should have received a copy of the GNU General Public License |
| 25 | along with this program; if not, write to the Free Software |
| 26 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 27 | 02111-1307, USA. |
| 28 | |
njn25 | e49d8e7 | 2002-09-23 09:36:25 +0000 | [diff] [blame] | 29 | The GNU General Public License is contained in the file COPYING. |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 30 | */ |
| 31 | |
| 32 | #include "vg_include.h" |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 33 | #include <stddef.h> |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 34 | |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 35 | /* #define DEBUG_TRANSTAB */ |
| 36 | |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 37 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 38 | /*-------------------------------------------------------------*/ |
| 39 | /*--- Management of the FIFO-based translation table+cache. ---*/ |
| 40 | /*-------------------------------------------------------------*/ |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 41 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 42 | /*------------------ CONSTANTS ------------------*/ |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 43 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 44 | /* Number of sectors the TC is divided into. */ |
| 45 | #define VG_TC_N_SECTORS 8 |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 46 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 47 | /* Calculated once at startup and never changed. */ |
| 48 | /* const */ Int vg_tc_sector_szB = 0; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 49 | |
| 50 | /* Number of entries in the translation table. This must be a prime |
| 51 | number in order to make the hashing work properly. */ |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 52 | #define VG_TT_SIZE /*5281*/ /*100129*/ 200191 /*250829*/ |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 53 | |
| 54 | /* Do an LRU pass when the translation table becomes this full. */ |
| 55 | #define VG_TT_LIMIT_PERCENT /*67*/ 80 |
| 56 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 57 | #define VG_TT_LIMIT ((VG_TT_SIZE * VG_TT_LIMIT_PERCENT) / 100) |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 58 | |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 59 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 60 | /*------------------ TYPES ------------------*/ |
| 61 | |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 62 | #define CODE_ALIGNMENT 16 /* alignment of TCEntries */ |
| 63 | #define CODE_ALIGN(a) (((a)+CODE_ALIGNMENT-1) & ~(CODE_ALIGNMENT-1)) |
| 64 | #define IS_ALIGNED(a) (((a) & (CODE_ALIGNMENT-1)) == 0) |
| 65 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 66 | /* An entry in TC. Payload always is always padded out to a 4-aligned |
| 67 | quantity so that these structs are always word-aligned. */ |
| 68 | typedef |
| 69 | struct { |
| 70 | /* +0 */ Addr orig_addr; |
| 71 | /* +4 */ UShort orig_size; |
| 72 | /* +6 */ UShort trans_size; |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 73 | /* +8 */ UShort jump_sites[VG_MAX_JUMPS]; |
| 74 | /* +VG_CODE_OFFSET */ UChar payload[0]; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 75 | } |
| 76 | TCEntry; |
| 77 | |
| 78 | /* An entry in TT. */ |
| 79 | typedef |
| 80 | struct { |
| 81 | Addr orig_addr; |
| 82 | TCEntry* tcentry; |
| 83 | } |
| 84 | TTEntry; |
| 85 | |
| 86 | /* Denotes an empty TT slot, when TTEntry.orig_addr holds this |
| 87 | value. */ |
| 88 | #define VG_TTE_EMPTY ((Addr)1) |
| 89 | |
| 90 | /* Denotes an empty TT slot, when TTEntry.orig_addr holds this |
| 91 | value. */ |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 92 | #define VG_TTE_DELETED ((Addr)3) |
| 93 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 94 | /* A bogus TCEntry which hopefully does not match code from any valid |
| 95 | address. This is what all VG_(tt_fast) entries are made to point |
| 96 | at when we want to invalidate it. */ |
| 97 | static const TCEntry vg_tc_bogus_TCEntry = { ((Addr)5), 0, 0 }; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 98 | |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 99 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 100 | /*------------------ DECLS ------------------*/ |
| 101 | |
| 102 | /* The translation cache sectors. These are NULL until allocated |
| 103 | dynamically. */ |
| 104 | static UChar* vg_tc[VG_TC_N_SECTORS]; |
| 105 | |
| 106 | /* Count of bytes used in each sector of the TC. */ |
| 107 | static Int vg_tc_used[VG_TC_N_SECTORS]; |
| 108 | |
| 109 | /* The age of each sector, so we can find the oldest. We just use the |
| 110 | global count of translations made when the sector was brought into |
| 111 | use. Doesn't matter if this mechanism gets confused (wraps around |
| 112 | 4G) once in a while. */ |
| 113 | static Int vg_tc_age[VG_TC_N_SECTORS]; |
| 114 | |
| 115 | /* The number of the sector currently being allocated in. */ |
| 116 | static Int vg_tc_current; |
| 117 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 118 | /* Count of number of translations, orig and new bytes in each sector. |
| 119 | For stats purposes only. */ |
| 120 | static Int vg_tc_stats_count[VG_TC_N_SECTORS]; |
| 121 | static Int vg_tc_stats_osize[VG_TC_N_SECTORS]; |
| 122 | static Int vg_tc_stats_tsize[VG_TC_N_SECTORS]; |
| 123 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 124 | |
| 125 | /*------------------ TRANSLATION TABLE ------------------*/ |
| 126 | |
| 127 | /* The translation table. An array of VG_TT_SIZE TTEntrys. */ |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 128 | static TTEntry* vg_tt = NULL; |
| 129 | |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 130 | /* Count of non-empty TT entries. This includes deleted ones. */ |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 131 | static Int vg_tt_used = 0; |
| 132 | |
| 133 | /* Fast helper for the TT. A direct-mapped cache which holds a |
| 134 | pointer to a TT entry which may or may not be the correct one, but |
| 135 | which we hope usually is. This array is referred to directly from |
| 136 | vg_dispatch.S. */ |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 137 | Addr /* TCEntry*, really */ VG_(tt_fast)[VG_TT_FAST_SIZE]; |
sewardj | 8aef119 | 2002-07-24 09:36:36 +0000 | [diff] [blame] | 138 | |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 139 | static void for_each_tc(Int sector, void (*fn)(TCEntry *)); |
| 140 | |
| 141 | |
| 142 | /*------------------ T-CHAINING HELPERS ------------------*/ |
| 143 | |
| 144 | static |
| 145 | void for_each_jumpsite(TCEntry *tce, void (*fn)(Addr)) |
| 146 | { |
| 147 | Int i; |
| 148 | for(i = 0; i < VG_MAX_JUMPS; i++) { |
| 149 | Addr a; |
| 150 | UShort idx = tce->jump_sites[i]; |
| 151 | |
| 152 | if (idx == (UShort)-1) |
| 153 | continue; |
| 154 | |
| 155 | a = (Addr)&tce->payload[idx]; |
| 156 | |
| 157 | (*fn)(a); |
| 158 | } |
| 159 | } |
| 160 | |
| 161 | static inline |
| 162 | void unchain_tce(TCEntry *tce) |
| 163 | { |
| 164 | for_each_jumpsite(tce, VG_(unchain_jumpsite)); |
| 165 | } |
| 166 | |
| 167 | /* Unchain any jumps pointing to a sector we're about to free */ |
| 168 | static |
| 169 | void unchain_sector(Int s, Addr base, UInt len) |
| 170 | { |
| 171 | void unchain_site(Addr a) { |
| 172 | Addr jmp = VG_(get_jmp_dest)(a); |
| 173 | if (jmp >= base && jmp < (base+len)) |
| 174 | VG_(unchain_jumpsite)(a); |
| 175 | } |
| 176 | void _unchain_tce(TCEntry *tce) { |
| 177 | for_each_jumpsite(tce, unchain_site); |
| 178 | } |
| 179 | |
| 180 | for_each_tc(s, _unchain_tce); |
| 181 | } |
| 182 | |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 183 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 184 | /*------------------ TT HELPERS ------------------*/ |
| 185 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 186 | static |
| 187 | void pp_tt_tc_status ( Char* submsg ) |
| 188 | { |
| 189 | Int tc_used, s; |
| 190 | if (VG_(clo_verbosity) <= 2) |
| 191 | return; |
| 192 | tc_used = 0; |
| 193 | for (s = 0; s < VG_TC_N_SECTORS; s++) |
| 194 | tc_used += vg_tc_used[s]; |
| 195 | |
| 196 | VG_(message)(Vg_DebugMsg, |
| 197 | "%luk bbs: tt %d, tc %d, %s", |
| 198 | VG_(bbs_done) / 1000, |
| 199 | vg_tt_used, tc_used, submsg ); |
| 200 | } |
| 201 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 202 | /* Invalidate the tt_fast cache, for whatever reason, by pointing all |
| 203 | entries at vg_tc_bogus_TCEntry. */ |
| 204 | static |
| 205 | void vg_invalidate_tt_fast( void ) |
| 206 | { |
| 207 | Int j; |
| 208 | for (j = 0; j < VG_TT_FAST_SIZE; j++) |
| 209 | VG_(tt_fast)[j] = (Addr)&vg_tc_bogus_TCEntry; |
| 210 | } |
| 211 | |
| 212 | |
| 213 | static |
| 214 | void add_tt_entry ( TCEntry* tce ) |
| 215 | { |
| 216 | UInt i; |
| 217 | /* VG_(printf)("add_TT_entry orig_addr %p\n", tce->orig_addr); */ |
| 218 | /* Hash to get initial probe point. */ |
| 219 | i = ((UInt)(tce->orig_addr)) % VG_TT_SIZE; |
| 220 | while (True) { |
| 221 | if (vg_tt[i].orig_addr == tce->orig_addr) |
| 222 | VG_(core_panic)("add_TT_entry: duplicate"); |
| 223 | if (vg_tt[i].orig_addr == VG_TTE_EMPTY) |
| 224 | break; |
| 225 | i++; |
| 226 | if (i == VG_TT_SIZE) |
| 227 | i = 0; |
| 228 | } |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 229 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 230 | vg_tt[i].orig_addr = tce->orig_addr; |
| 231 | vg_tt[i].tcentry = tce; |
| 232 | vg_tt_used++; |
| 233 | /* sanity ... */ |
| 234 | vg_assert(vg_tt_used < VG_TT_SIZE-1000); |
| 235 | } |
| 236 | |
| 237 | |
| 238 | /* Search TT to find the translated address of the supplied original, |
| 239 | or NULL if not found. This routine is used when we miss in |
| 240 | VG_(tt_fast). |
| 241 | */ |
| 242 | static __inline__ |
| 243 | TTEntry* search_tt ( Addr orig_addr ) |
| 244 | { |
| 245 | Int i; |
| 246 | /* Hash to get initial probe point. */ |
| 247 | i = ((UInt)orig_addr) % VG_TT_SIZE; |
| 248 | while (True) { |
| 249 | if (vg_tt[i].orig_addr == orig_addr) |
| 250 | return &vg_tt[i]; |
| 251 | if (vg_tt[i].orig_addr == VG_TTE_EMPTY) |
| 252 | return NULL; |
| 253 | i++; |
| 254 | if (i == VG_TT_SIZE) i = 0; |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | |
| 259 | static |
| 260 | void initialise_tt ( void ) |
| 261 | { |
| 262 | Int i; |
| 263 | vg_tt_used = 0; |
| 264 | for (i = 0; i < VG_TT_SIZE; i++) { |
| 265 | vg_tt[i].orig_addr = VG_TTE_EMPTY; |
| 266 | } |
| 267 | vg_invalidate_tt_fast(); |
| 268 | } |
| 269 | |
| 270 | |
| 271 | static |
| 272 | void rebuild_TT ( void ) |
| 273 | { |
| 274 | Int s; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 275 | |
| 276 | /* Throw away TT. */ |
| 277 | initialise_tt(); |
| 278 | |
| 279 | /* Rebuild TT from the remaining quarters. */ |
| 280 | for (s = 0; s < VG_TC_N_SECTORS; s++) { |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 281 | for_each_tc(s, add_tt_entry); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 282 | } |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 283 | pp_tt_tc_status ( "after rebuild of TC" ); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 284 | } |
| 285 | |
| 286 | |
| 287 | /*------------------ TC HELPERS ------------------*/ |
| 288 | |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 289 | static |
| 290 | void for_each_tc(Int s, void (*fn)(TCEntry *)) |
| 291 | { |
| 292 | UChar *pc; |
| 293 | UChar *pc_lim; |
| 294 | TCEntry *tce; |
| 295 | |
| 296 | pc = &(vg_tc[s][0]); |
| 297 | pc_lim = &(vg_tc[s][vg_tc_used[s]]); |
| 298 | while (True) { |
| 299 | if (pc >= pc_lim) break; |
| 300 | tce = (TCEntry*)pc; |
| 301 | pc += sizeof(TCEntry) + tce->trans_size; |
| 302 | if (tce->orig_addr != VG_TTE_DELETED) |
| 303 | (*fn)(tce); |
| 304 | } |
| 305 | } |
| 306 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 307 | /* Find the oldest non-NULL, non-empty sector, or -1 if none such. */ |
| 308 | static |
| 309 | Int find_oldest_sector ( void ) |
| 310 | { |
| 311 | Int oldest_age, oldest, i; |
| 312 | oldest_age = 1000 * 1000 * 1000; |
| 313 | oldest = -1; |
| 314 | for (i = 0; i < VG_TC_N_SECTORS; i++) { |
| 315 | if (vg_tc[i] == NULL) |
| 316 | continue; |
| 317 | if (vg_tc_used[i] == 0) |
| 318 | continue; |
| 319 | if (vg_tc_age[i] < oldest_age) { |
| 320 | oldest = i; |
| 321 | oldest_age = vg_tc_age[i]; |
| 322 | } |
| 323 | } |
| 324 | return oldest; |
| 325 | } |
| 326 | |
| 327 | |
| 328 | /* Discard the oldest sector, if any such exists. */ |
| 329 | static |
| 330 | void discard_oldest_sector ( void ) |
| 331 | { |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 332 | Char msg[100]; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 333 | Int s = find_oldest_sector(); |
| 334 | if (s != -1) { |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 335 | Int i; |
| 336 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 337 | vg_assert(s >= 0 && s < VG_TC_N_SECTORS); |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 338 | VG_(sprintf)(msg, "before discard of sector %d (%d bytes)", |
| 339 | s, vg_tc_used[s]); |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 340 | |
| 341 | for(i = 0; i < VG_TC_N_SECTORS; i++) { |
| 342 | if (i != s && vg_tc[i] != NULL) |
| 343 | unchain_sector(i, (Addr)vg_tc[s], vg_tc_used[s]); |
| 344 | } |
| 345 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 346 | pp_tt_tc_status ( msg ); |
| 347 | VG_(overall_out_count) += vg_tc_stats_count[s]; |
| 348 | VG_(overall_out_osize) += vg_tc_stats_osize[s]; |
| 349 | VG_(overall_out_tsize) += vg_tc_stats_tsize[s]; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 350 | vg_tc_used[s] = 0; |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 351 | vg_tc_stats_count[s] = 0; |
| 352 | vg_tc_stats_osize[s] = 0; |
| 353 | vg_tc_stats_tsize[s] = 0; |
| 354 | VG_(number_of_tc_discards) ++; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 355 | } |
| 356 | } |
| 357 | |
| 358 | |
| 359 | /* Find an empty sector and bring it into use. If there isn't one, |
| 360 | try and allocate one. If that fails, return -1. */ |
| 361 | static |
| 362 | Int maybe_commission_sector ( void ) |
| 363 | { |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 364 | Char msg[100]; |
| 365 | Int s; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 366 | for (s = 0; s < VG_TC_N_SECTORS; s++) { |
| 367 | if (vg_tc[s] != NULL && vg_tc_used[s] == 0) { |
| 368 | vg_tc_age[s] = VG_(overall_in_count); |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 369 | VG_(sprintf)(msg, "after commission of sector %d " |
| 370 | "at time %d", |
| 371 | s, vg_tc_age[s]); |
| 372 | pp_tt_tc_status ( msg ); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 373 | # ifdef DEBUG_TRANSTAB |
| 374 | VG_(sanity_check_tc_tt)(); |
| 375 | # endif |
| 376 | return s; |
| 377 | } |
| 378 | } |
| 379 | for (s = 0; s < VG_TC_N_SECTORS; s++) { |
| 380 | if (vg_tc[s] == NULL) { |
| 381 | vg_tc[s] = VG_(get_memory_from_mmap) |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 382 | ( vg_tc_sector_szB, "trans-cache(sector)" ); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 383 | vg_tc_used[s] = 0; |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 384 | VG_(sprintf)(msg, "after allocation of sector %d " |
| 385 | "(size %d)", |
| 386 | s, vg_tc_sector_szB ); |
| 387 | pp_tt_tc_status ( msg ); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 388 | return maybe_commission_sector(); |
| 389 | } |
| 390 | } |
| 391 | return -1; |
| 392 | } |
| 393 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 394 | |
| 395 | static |
| 396 | UChar* allocate ( Int nBytes ) |
| 397 | { |
| 398 | Int i; |
| 399 | |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 400 | vg_assert(IS_ALIGNED(nBytes)); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 401 | |
| 402 | /* Ensure the TT is still OK. */ |
| 403 | while (vg_tt_used >= VG_TT_LIMIT) { |
| 404 | (void)discard_oldest_sector(); |
| 405 | rebuild_TT(); |
| 406 | vg_assert(vg_tt_used < VG_TT_LIMIT); |
| 407 | } |
| 408 | |
| 409 | /* Can we get it into the current sector? */ |
| 410 | if (vg_tc_current >= 0 |
| 411 | && vg_tc_current < VG_TC_N_SECTORS |
| 412 | && vg_tc[vg_tc_current] != NULL |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 413 | && vg_tc_used[vg_tc_current] + nBytes <= vg_tc_sector_szB) { |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 414 | /* Yes. */ |
| 415 | UChar* p = &(vg_tc[vg_tc_current][ vg_tc_used[vg_tc_current] ]); |
| 416 | vg_tc_used[vg_tc_current] += nBytes; |
| 417 | return p; |
| 418 | } |
| 419 | |
| 420 | /* Perhaps we can bring a new sector into use, for the first |
| 421 | time. */ |
| 422 | vg_tc_current = maybe_commission_sector(); |
| 423 | if (vg_tc_current >= 0 && vg_tc_current < VG_TC_N_SECTORS) |
| 424 | return allocate(nBytes); |
| 425 | |
| 426 | /* That didn't work. We'll have to dump the oldest. We take the |
| 427 | opportunity to dump the N oldest at once. */ |
| 428 | for (i = 0; i < 1; i++) |
| 429 | (void)discard_oldest_sector(); |
| 430 | |
| 431 | rebuild_TT(); |
| 432 | vg_tc_current = maybe_commission_sector(); |
| 433 | vg_assert(vg_tc_current >= 0 && vg_tc_current < VG_TC_N_SECTORS); |
| 434 | # ifdef DEBUG_TRANSTAB |
| 435 | VG_(sanity_check_tc_tt)(); |
| 436 | # endif |
| 437 | |
| 438 | return allocate(nBytes); |
| 439 | } |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 440 | |
| 441 | |
| 442 | /* Just so these counts can be queried without making them globally |
| 443 | visible. */ |
| 444 | void VG_(get_tt_tc_used) ( UInt* tt_used, UInt* tc_used ) |
| 445 | { |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 446 | Int s; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 447 | *tt_used = vg_tt_used; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 448 | *tc_used = 0; |
| 449 | for (s = 0; s < VG_TC_N_SECTORS; s++) |
| 450 | *tc_used += vg_tc_used[s]; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 451 | } |
| 452 | |
| 453 | |
| 454 | /* Do a sanity check on TT/TC. |
| 455 | */ |
| 456 | void VG_(sanity_check_tc_tt) ( void ) |
| 457 | { |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 458 | Int i, s; |
| 459 | TTEntry* tte; |
| 460 | TCEntry* tce; |
| 461 | /* Checks: |
| 462 | - Each TT entry points to a valid and corresponding TC entry. |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 463 | */ |
| 464 | for (i = 0; i < VG_TT_SIZE; i++) { |
| 465 | tte = &vg_tt[i]; |
| 466 | /* empty slots are harmless. */ |
| 467 | if (tte->orig_addr == VG_TTE_EMPTY) continue; |
| 468 | /* all others should agree with the TC entry. */ |
| 469 | tce = tte->tcentry; |
| 470 | vg_assert(IS_ALIGNED4_ADDR(tce)); |
| 471 | /* does this point into a valid TC sector? */ |
| 472 | for (s = 0; s < VG_TC_N_SECTORS; s++) |
| 473 | if (vg_tc[s] != NULL |
| 474 | && ((Addr)tce) >= (Addr)&vg_tc[s][0] |
| 475 | && ((Addr)tce) < (Addr)&vg_tc[s][ vg_tc_used[s] ]) |
| 476 | break; |
| 477 | vg_assert(s < VG_TC_N_SECTORS); |
| 478 | /* It should agree with the TC entry on the orig_addr. This may |
| 479 | be VG_TTE_DELETED, or a real orig addr. */ |
| 480 | vg_assert(tte->orig_addr == tce->orig_addr); |
| 481 | } |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 482 | } |
| 483 | |
| 484 | |
| 485 | /* Add this already-filled-in entry to the TT. Assumes that the |
| 486 | relevant code chunk has been placed in TC, along with a dummy back |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 487 | pointer, which is inserted here. |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 488 | */ |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 489 | void VG_(add_to_trans_tab) ( Addr orig_addr, Int orig_size, |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 490 | Addr trans_addr, Int trans_size, |
| 491 | UShort jumps[VG_MAX_JUMPS]) |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 492 | { |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 493 | Int i, nBytes, trans_size_aligned; |
| 494 | TCEntry* tce; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 495 | /* |
| 496 | VG_(printf)("add_to_trans_tab(%d) %x %d %x %d\n", |
| 497 | vg_tt_used, tte->orig_addr, tte->orig_size, |
| 498 | tte->trans_addr, tte->trans_size); |
| 499 | */ |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 500 | |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 501 | vg_assert(offsetof(TCEntry, payload) == VG_CODE_OFFSET); |
| 502 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 503 | /* figure out how many bytes we require. */ |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 504 | nBytes = CODE_ALIGN(trans_size + sizeof(TCEntry)); |
| 505 | trans_size_aligned = nBytes-sizeof(TCEntry); |
| 506 | vg_assert(IS_ALIGNED(nBytes)); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 507 | |
| 508 | tce = (TCEntry*)allocate(nBytes); |
| 509 | /* VG_(printf)("allocate returned %p\n", tce); */ |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 510 | vg_assert(vg_tc_current >= 0 && vg_tc_current < VG_TC_N_SECTORS); |
| 511 | |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 512 | tce->orig_addr = orig_addr; |
| 513 | tce->orig_size = (UShort)orig_size; /* what's the point of storing this? */ |
| 514 | tce->trans_size = (UShort)trans_size_aligned; |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 515 | for (i = 0; i < VG_MAX_JUMPS; i++) { |
| 516 | tce->jump_sites[i] = jumps[i]; |
| 517 | } |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 518 | for (i = 0; i < trans_size; i++) { |
| 519 | tce->payload[i] = ((UChar*)trans_addr)[i]; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 520 | } |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 521 | |
| 522 | unchain_tce(tce); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 523 | add_tt_entry(tce); |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 524 | |
| 525 | /* Update stats. */ |
| 526 | VG_(overall_in_count) ++; |
| 527 | VG_(overall_in_osize) += orig_size; |
| 528 | VG_(overall_in_tsize) += trans_size; |
| 529 | |
| 530 | vg_tc_stats_count[vg_tc_current] ++; |
| 531 | vg_tc_stats_osize[vg_tc_current] += orig_size; |
| 532 | vg_tc_stats_tsize[vg_tc_current] += trans_size; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 533 | } |
| 534 | |
| 535 | |
| 536 | /* Find the translation address for a given (original) code address. |
| 537 | If found, update VG_(tt_fast) so subsequent lookups are fast. If |
| 538 | no translation can be found, return zero. This routine is (the |
| 539 | only one) called from vg_run_innerloop. */ |
| 540 | Addr VG_(search_transtab) ( Addr original_addr ) |
| 541 | { |
| 542 | TTEntry* tte; |
| 543 | VGP_PUSHCC(VgpSlowFindT); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 544 | tte = search_tt ( original_addr ); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 545 | if (tte == NULL) { |
| 546 | /* We didn't find it. vg_run_innerloop will have to request a |
| 547 | translation. */ |
njn25 | e49d8e7 | 2002-09-23 09:36:25 +0000 | [diff] [blame] | 548 | VGP_POPCC(VgpSlowFindT); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 549 | return (Addr)0; |
| 550 | } else { |
| 551 | /* Found it. Put the search result into the fast cache now. |
| 552 | Also set the mru_epoch to mark this translation as used. */ |
| 553 | UInt cno = (UInt)original_addr & VG_TT_FAST_MASK; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 554 | VG_(tt_fast)[cno] = (Addr)(tte->tcentry); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 555 | VG_(tt_fast_misses)++; |
njn25 | e49d8e7 | 2002-09-23 09:36:25 +0000 | [diff] [blame] | 556 | VGP_POPCC(VgpSlowFindT); |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 557 | return (Addr)&(tte->tcentry->payload[0]); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 558 | } |
| 559 | } |
| 560 | |
| 561 | |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 562 | /* Invalidate translations of original code [start .. start + range - 1]. |
| 563 | This is slow, so you *really* don't want to call it very often. |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 564 | */ |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 565 | void VG_(invalidate_translations) ( Addr start, UInt range ) |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 566 | { |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 567 | Addr i_start, i_end, o_start, o_end; |
| 568 | UInt out_count, out_osize, out_tsize; |
| 569 | Int i; |
| 570 | TCEntry* tce; |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 571 | # ifdef DEBUG_TRANSTAB |
| 572 | VG_(sanity_check_tc_tt)(); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 573 | # endif |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 574 | i_start = start; |
| 575 | i_end = start + range - 1; |
| 576 | out_count = out_osize = out_tsize = 0; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 577 | |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 578 | for (i = 0; i < VG_TT_SIZE; i++) { |
| 579 | if (vg_tt[i].orig_addr == VG_TTE_EMPTY |
| 580 | || vg_tt[i].orig_addr == VG_TTE_DELETED) continue; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 581 | tce = vg_tt[i].tcentry; |
| 582 | o_start = tce->orig_addr; |
| 583 | o_end = o_start + tce->trans_size - 1; |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 584 | if (o_end < i_start || o_start > i_end) |
| 585 | continue; |
njn25 | e49d8e7 | 2002-09-23 09:36:25 +0000 | [diff] [blame] | 586 | |
| 587 | if (VG_(needs).basic_block_discards) |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 588 | SK_(discard_basic_block_info)( tce->orig_addr, |
| 589 | tce->orig_size ); |
njn25 | e49d8e7 | 2002-09-23 09:36:25 +0000 | [diff] [blame] | 590 | |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 591 | vg_tt[i].orig_addr = VG_TTE_DELETED; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 592 | tce->orig_addr = VG_TTE_DELETED; |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 593 | VG_(overall_out_count) ++; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 594 | VG_(overall_out_osize) += tce->orig_size; |
| 595 | VG_(overall_out_tsize) += tce->trans_size; |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 596 | out_count ++; |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 597 | out_osize += tce->orig_size; |
| 598 | out_tsize += tce->trans_size; |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 599 | } |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 600 | |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 601 | if (out_count > 0) { |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 602 | vg_invalidate_tt_fast(); |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 603 | VG_(sanity_check_tc_tt)(); |
| 604 | # ifdef DEBUG_TRANSTAB |
| 605 | { Addr aa; |
| 606 | for (aa = i_start; aa <= i_end; aa++) |
sewardj | 6c3769f | 2002-11-29 01:02:45 +0000 | [diff] [blame] | 607 | vg_assert(search_tt ( aa ) == NULL); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 608 | } |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 609 | # endif |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 610 | } |
| 611 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 612 | if (VG_(clo_verbosity) > 2) |
sewardj | 18d7513 | 2002-05-16 11:06:21 +0000 | [diff] [blame] | 613 | VG_(message)(Vg_UserMsg, |
| 614 | "discard %d (%d -> %d) translations in range %p .. %p", |
| 615 | out_count, out_osize, out_tsize, i_start, i_end ); |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 616 | } |
| 617 | |
| 618 | |
| 619 | /*------------------------------------------------------------*/ |
| 620 | /*--- Initialisation. ---*/ |
| 621 | /*------------------------------------------------------------*/ |
| 622 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 623 | void VG_(init_tt_tc) ( void ) |
| 624 | { |
| 625 | Int s; |
| 626 | |
sewardj | 22854b9 | 2002-11-30 14:00:47 +0000 | [diff] [blame^] | 627 | /* Otherwise we wind up with non-32-bit-aligned code in |
| 628 | TCEntries. */ |
| 629 | vg_assert((VG_MAX_JUMPS % 2) == 0); |
| 630 | |
sewardj | c0d8f68 | 2002-11-30 00:49:43 +0000 | [diff] [blame] | 631 | /* Figure out how big each sector should be. */ |
| 632 | vg_tc_sector_szB |
| 633 | = (VG_TT_LIMIT /* max TT entries we expect */ |
| 634 | * VG_(details).avg_translation_sizeB) |
| 635 | / VG_TC_N_SECTORS; |
| 636 | /* Ensure the calculated value is not way crazy. */ |
| 637 | vg_assert(vg_tc_sector_szB >= 200000); |
| 638 | vg_assert(vg_tc_sector_szB <= 6000000); |
| 639 | |
| 640 | for (s = 0; s < VG_TC_N_SECTORS; s++) { |
| 641 | vg_tc[s] = NULL; |
| 642 | vg_tc_used[s] = 0; |
| 643 | vg_tc_age[s] = 0; |
| 644 | vg_tc_stats_count[s] = 0; |
| 645 | vg_tc_stats_osize[s] = 0; |
| 646 | vg_tc_stats_tsize[s] = 0; |
| 647 | } |
| 648 | vg_tc_current = 0; |
| 649 | |
| 650 | vg_tt = VG_(get_memory_from_mmap) ( VG_TT_SIZE * sizeof(TTEntry), |
| 651 | "trans-table" ); |
| 652 | /* The main translation table is empty. */ |
| 653 | initialise_tt(); |
| 654 | |
| 655 | if (VG_(clo_verbosity) > 2) { |
| 656 | VG_(message)(Vg_DebugMsg, |
| 657 | "Translation Cache: using %d sectors of %d bytes each", |
| 658 | VG_TC_N_SECTORS, vg_tc_sector_szB ); |
| 659 | VG_(message)(Vg_DebugMsg, |
| 660 | "Translation Table: %d total entries, max occupancy %d (%d%%)", |
| 661 | VG_TT_SIZE, VG_TT_LIMIT, VG_TT_LIMIT_PERCENT ); |
| 662 | } |
| 663 | |
| 664 | # ifdef DEBUG_TRANSTAB |
| 665 | VG_(sanity_check_tc_tt)(); |
| 666 | # endif |
| 667 | } |
| 668 | |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 669 | /*--------------------------------------------------------------------*/ |
| 670 | /*--- end vg_transtab.c ---*/ |
| 671 | /*--------------------------------------------------------------------*/ |