1 2 /*--------------------------------------------------------------------*/ 3 /*--- Management of the translation table and cache. ---*/ 4 /*--- m_transtab.c ---*/ 5 /*--------------------------------------------------------------------*/ 6 7 /* 8 This file is part of Valgrind, a dynamic binary instrumentation 9 framework. 10 11 Copyright (C) 2000-2013 Julian Seward 12 jseward (at) acm.org 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 29 The GNU General Public License is contained in the file COPYING. 30 */ 31 32 #include "pub_core_basics.h" 33 #include "pub_core_debuglog.h" 34 #include "pub_core_machine.h" // For VG_(machine_get_VexArchInfo) 35 #include "pub_core_libcbase.h" 36 #include "pub_core_vki.h" // to keep pub_core_libproc.h happy, sigh 37 #include "pub_core_libcproc.h" // VG_(invalidate_icache) 38 #include "pub_core_libcassert.h" 39 #include "pub_core_libcprint.h" 40 #include "pub_core_options.h" 41 #include "pub_core_tooliface.h" // For VG_(details).avg_translation_sizeB 42 #include "pub_core_transtab.h" 43 #include "pub_core_aspacemgr.h" 44 #include "pub_core_mallocfree.h" // VG_(out_of_memory_NORETURN) 45 #include "pub_core_xarray.h" 46 #include "pub_core_dispatch.h" // For VG_(disp_cp*) addresses 47 48 49 #define DEBUG_TRANSTAB 0 50 51 52 /*-------------------------------------------------------------*/ 53 /*--- Management of the FIFO-based translation table+cache. ---*/ 54 /*-------------------------------------------------------------*/ 55 56 /* Nr of sectors provided via command line parameter. */ 57 UInt VG_(clo_num_transtab_sectors) = N_SECTORS_DEFAULT; 58 /* Nr of sectors. 59 Will be set by VG_(init_tt_tc) to VG_(clo_num_transtab_sectors). */ 60 static SECno n_sectors = 0; 61 62 /* Average size of a transtab code entry. 0 means to use the tool 63 provided default. */ 64 UInt VG_(clo_avg_transtab_entry_size) = 0; 65 66 /*------------------ CONSTANTS ------------------*/ 67 /* Number of entries in hash table of each sector. This needs to be a prime 68 number to work properly, it must be <= 65535 (so that a TTE index 69 fits in a UShort, leaving room for 0xFFFF(EC2TTE_DELETED, HTT_DELETED) 70 to denote 'deleted') and 0xFFFE (HTT_EMPTY) to denote 'Empty' in the 71 hash table. 72 It is strongly recommended not to change this. 73 65521 is the largest prime <= 65535. */ 74 #define N_HTTES_PER_SECTOR /*10007*/ /*30011*/ /*40009*/ 65521 75 76 #define EC2TTE_DELETED 0xFFFF /* 16-bit special value */ 77 #define HTT_DELETED EC2TTE_DELETED 78 #define HTT_EMPTY 0XFFFE 79 80 // HTTno is the Sector->htt hash table index. Must be the same type as TTEno. 81 typedef UShort HTTno; 82 83 /* Because each sector contains a hash table of TTEntries, we need to 84 specify the maximum allowable loading, after which the sector is 85 deemed full. */ 86 #define SECTOR_TT_LIMIT_PERCENT 65 87 88 /* The sector is deemed full when this many entries are in it. */ 89 #define N_TTES_PER_SECTOR \ 90 ((N_HTTES_PER_SECTOR * SECTOR_TT_LIMIT_PERCENT) / 100) 91 92 /* Equivalence classes for fast address range deletion. There are 1 + 93 2^ECLASS_WIDTH bins. The highest one, ECLASS_MISC, describes an 94 address range which does not fall cleanly within any specific bin. 95 Note that ECLASS_SHIFT + ECLASS_WIDTH must be < 32. 96 ECLASS_N must fit in a EclassNo. */ 97 #define ECLASS_SHIFT 11 98 #define ECLASS_WIDTH 8 99 #define ECLASS_MISC (1 << ECLASS_WIDTH) 100 #define ECLASS_N (1 + ECLASS_MISC) 101 STATIC_ASSERT(ECLASS_SHIFT + ECLASS_WIDTH < 32); 102 103 typedef UShort EClassNo; 104 105 /*------------------ TYPES ------------------*/ 106 107 /* In edges ("to-me") in the graph created by chaining. */ 108 typedef 109 struct { 110 SECno from_sNo; /* sector number */ 111 TTEno from_tteNo; /* TTE number in given sector */ 112 UInt from_offs: (sizeof(UInt)*8)-1; /* code offset from TCEntry::tcptr 113 where the patch is */ 114 Bool to_fastEP:1; /* Is the patch to a fast or slow entry point? */ 115 } 116 InEdge; 117 118 119 /* Out edges ("from-me") in the graph created by chaining. */ 120 typedef 121 struct { 122 SECno to_sNo; /* sector number */ 123 TTEno to_tteNo; /* TTE number in given sector */ 124 UInt from_offs; /* code offset in owning translation where patch is */ 125 } 126 OutEdge; 127 128 129 #define N_FIXED_IN_EDGE_ARR 3 130 typedef 131 struct { 132 Bool has_var:1; /* True if var is used (then n_fixed must be 0) */ 133 UInt n_fixed: (sizeof(UInt)*8)-1; /* 0 .. N_FIXED_IN_EDGE_ARR */ 134 union { 135 InEdge fixed[N_FIXED_IN_EDGE_ARR]; /* if !has_var */ 136 XArray* var; /* XArray* of InEdgeArr */ /* if has_var */ 137 } edges; 138 } 139 InEdgeArr; 140 141 #define N_FIXED_OUT_EDGE_ARR 2 142 typedef 143 struct { 144 Bool has_var:1; /* True if var is used (then n_fixed must be 0) */ 145 UInt n_fixed: (sizeof(UInt)*8)-1; /* 0 .. N_FIXED_OUT_EDGE_ARR */ 146 union { 147 OutEdge fixed[N_FIXED_OUT_EDGE_ARR]; /* if !has_var */ 148 XArray* var; /* XArray* of OutEdgeArr */ /* if has_var */ 149 } edges; 150 } 151 OutEdgeArr; 152 153 154 /* A translation-table entry. This indicates precisely which areas of 155 guest code are included in the translation, and contains all other 156 auxiliary info too. */ 157 typedef 158 struct { 159 union { 160 struct { 161 /* Profiling only: the count and weight (arbitrary meaning) for 162 this translation. Weight is a property of the translation 163 itself and computed once when the translation is created. 164 Count is an entry count for the translation and is 165 incremented by 1 every time the translation is used, if we 166 are profiling. */ 167 ULong count; 168 UShort weight; 169 } prof; // if status == InUse 170 TTEno next_empty_tte; // if status != InUse 171 } usage; 172 173 /* Status of the slot. Note, we need to be able to do lazy 174 deletion, hence the Deleted state. */ 175 enum { InUse, Deleted, Empty } status; 176 177 /* 64-bit aligned pointer to one or more 64-bit words containing 178 the corresponding host code (must be in the same sector!) 179 This is a pointer into the sector's tc (code) area. */ 180 ULong* tcptr; 181 182 /* This is the original guest address that purportedly is the 183 entry point of the translation. You might think that .entry 184 should be the same as .vge->base[0], and most of the time it 185 is. However, when doing redirections, that is not the case. 186 .vge must always correctly describe the guest code sections 187 from which this translation was made. However, .entry may or 188 may not be a lie, depending on whether or not we're doing 189 redirection. */ 190 Addr entry; 191 192 /* This structure describes precisely what ranges of guest code 193 the translation covers, so we can decide whether or not to 194 delete it when translations of a given address range are 195 invalidated. */ 196 VexGuestExtents vge; 197 198 /* Address range summary info: these are pointers back to 199 eclass[] entries in the containing Sector. Those entries in 200 turn point back here -- the two structures are mutually 201 redundant but both necessary to make fast deletions work. 202 The eclass info is similar to, and derived from, this entry's 203 'vge' field, but it is not the same */ 204 UShort n_tte2ec; // # tte2ec pointers (1 to 3) 205 EClassNo tte2ec_ec[3]; // for each, the eclass # 206 UInt tte2ec_ix[3]; // and the index within the eclass. 207 // for i in 0 .. n_tte2ec-1 208 // sec->ec2tte[ tte2ec_ec[i] ][ tte2ec_ix[i] ] 209 // should be the index 210 // of this TTEntry in the containing Sector's tt array. 211 212 /* Admin information for chaining. 'in_edges' is a set of the 213 patch points which jump to this translation -- hence are 214 predecessors in the control flow graph. 'out_edges' points 215 to successors in the control flow graph -- translations to 216 which this one has a patched jump. In short these are just 217 backwards and forwards edges in the graph of patched-together 218 blocks. The 'in_edges' contain slightly more info, enough 219 that we can undo the chaining of each mentioned patch point. 220 The 'out_edges' list exists only so that we can visit the 221 'in_edges' entries of all blocks we're patched through to, in 222 order to remove ourselves from then when we're deleted. */ 223 224 /* A translation can disappear for two reasons: 225 1. erased (as part of the oldest sector cleanup) when the 226 youngest sector is full. 227 2. discarded due to calls to VG_(discard_translations). 228 VG_(discard_translations) sets the status of the 229 translation to 'Deleted'. 230 A.o., the gdbserver discards one or more translations 231 when a breakpoint is inserted or removed at an Addr, 232 or when single stepping mode is enabled/disabled 233 or when a translation is instrumented for gdbserver 234 (all the target jumps of this translation are 235 invalidated). 236 237 So, it is possible that the translation A to be patched 238 (to obtain a patched jump from A to B) is invalidated 239 after B is translated and before A is patched. 240 In case a translation is erased or discarded, the patching 241 cannot be done. VG_(tt_tc_do_chaining) and find_TTEntry_from_hcode 242 are checking the 'from' translation still exists before 243 doing the patching. 244 245 Is it safe to erase or discard the current translation E being 246 executed ? Amazing, but yes, it is safe. 247 Here is the explanation: 248 249 The translation E being executed can only be erased if a new 250 translation N is being done. A new translation is done only 251 if the host addr is a not yet patched jump to another 252 translation. In such a case, the guest address of N is 253 assigned to the PC in the VEX state. Control is returned 254 to the scheduler. N will be translated. This can erase the 255 translation E (in case of sector full). VG_(tt_tc_do_chaining) 256 will not do the chaining to a non found translation E. 257 The execution will continue at the current guest PC 258 (i.e. the translation N). 259 => it is safe to erase the current translation being executed. 260 261 The current translation E being executed can also be discarded 262 (e.g. by gdbserver). VG_(discard_translations) will mark 263 this translation E as Deleted, but the translation itself 264 is not erased. In particular, its host code can only 265 be overwritten or erased in case a new translation is done. 266 A new translation will only be done if a not yet translated 267 jump is to be executed. The execution of the Deleted translation 268 E will continue till a non patched jump is encountered. 269 This situation is then similar to the 'erasing' case above : 270 the current translation E can be erased or overwritten, as the 271 execution will continue at the new translation N. 272 273 */ 274 275 /* It is possible, although very unlikely, that a block A has 276 more than one patched jump to block B. This could happen if 277 (eg) A finishes "jcond B; jmp B". 278 279 This means in turn that B's in_edges set can list A more than 280 once (twice in this example). However, each such entry must 281 have a different from_offs, since a patched jump can only 282 jump to one place at once (it's meaningless for it to have 283 multiple destinations.) IOW, the successor and predecessor 284 edges in the graph are not uniquely determined by a 285 TTEntry --> TTEntry pair, but rather by a 286 (TTEntry,offset) --> TTEntry triple. 287 288 If A has multiple edges to B then B will mention A multiple 289 times in its in_edges. To make things simpler, we then 290 require that A mentions B exactly the same number of times in 291 its out_edges. Furthermore, a matching out-in pair must have 292 the same offset (from_offs). This facilitates sanity 293 checking, and it facilitates establishing the invariant that 294 a out_edges set may not have duplicates when using the 295 equality defined by (TTEntry,offset). Hence the out_edges 296 and in_edges sets really do have both have set semantics. 297 298 eg if A has been patched to B at offsets 42 and 87 (in A) 299 then A.out_edges = { (B,42), (B,87) } (in any order) 300 and B.in_edges = { (A,42), (A,87) } (in any order) 301 302 Hence for each node pair P->Q in the graph, there's a 1:1 303 mapping between P.out_edges and Q.in_edges. 304 */ 305 InEdgeArr in_edges; 306 OutEdgeArr out_edges; 307 } 308 TTEntry; 309 310 311 /* A structure used for mapping host code addresses back to the 312 relevant TTEntry. Used when doing chaining, for finding the 313 TTEntry to which some arbitrary patch address belongs. */ 314 typedef 315 struct { 316 UChar* start; 317 UInt len; 318 TTEno tteNo; 319 } 320 HostExtent; 321 322 /* Finally, a sector itself. Each sector contains an array of 323 TCEntries, which hold code, and an array of TTEntries, containing 324 all required administrative info. Profiling is supported using the 325 TTEntry usage.prof.count and usage.prof.weight fields, if required. 326 327 If the sector is not in use, all three pointers are NULL and 328 tt_n_inuse is zero. 329 */ 330 typedef 331 struct { 332 /* The TCEntry area. Size of this depends on the average 333 translation size. We try and size it so it becomes full 334 precisely when this sector's translation table (tt) reaches 335 its load limit (SECTOR_TT_LIMIT_PERCENT). */ 336 ULong* tc; 337 338 /* An hash table, mapping guest address to an index in the tt array. 339 htt is a fixed size, always containing 340 exactly N_HTTES_PER_SECTOR entries. */ 341 TTEno* htt; 342 343 /* The TTEntry array. This is a fixed size, always containing 344 exactly N_TTES_PER_SECTOR entries. */ 345 TTEntry* tt; 346 347 /* This points to the current allocation point in tc. */ 348 ULong* tc_next; 349 350 /* The count of tt entries with state InUse. */ 351 Int tt_n_inuse; 352 353 /* A list of Empty/Deleted entries, chained by tte->next_empty_tte */ 354 TTEno empty_tt_list; 355 356 /* Expandable arrays of tt indices for each of the ECLASS_N 357 address range equivalence classes. These hold indices into 358 the containing sector's tt array, which in turn should point 359 back here. */ 360 Int ec2tte_size[ECLASS_N]; 361 Int ec2tte_used[ECLASS_N]; 362 TTEno* ec2tte[ECLASS_N]; 363 364 /* The host extents. The [start, +len) ranges are constructed 365 in strictly non-overlapping order, so we can binary search 366 them at any time. */ 367 XArray* host_extents; /* XArray* of HostExtent */ 368 } 369 Sector; 370 371 372 /*------------------ DECLS ------------------*/ 373 374 /* The root data structure is an array of sectors. The index of the 375 youngest sector is recorded, and new translations are put into that 376 sector. When it fills up, we move along to the next sector and 377 start to fill that up, wrapping around at the end of the array. 378 That way, once all N_TC_SECTORS have been bought into use for the 379 first time, and are full, we then re-use the oldest sector, 380 endlessly. 381 382 When running, youngest sector should be between >= 0 and < 383 N_TC_SECTORS. The initial value indicates the TT/TC system is 384 not yet initialised. 385 */ 386 static Sector sectors[MAX_N_SECTORS]; 387 static Int youngest_sector = INV_SNO; 388 389 /* The number of ULongs in each TCEntry area. This is computed once 390 at startup and does not change. */ 391 static Int tc_sector_szQ = 0; 392 393 394 /* A list of sector numbers, in the order which they should be 395 searched to find translations. This is an optimisation to be used 396 when searching for translations and should not affect 397 correctness. INV_SNO denotes "no entry". */ 398 static SECno sector_search_order[MAX_N_SECTORS]; 399 400 401 /* Fast helper for the TC. A direct-mapped cache which holds a set of 402 recently used (guest address, host address) pairs. This array is 403 referred to directly from m_dispatch/dispatch-<platform>.S. 404 405 Entries in tt_fast may refer to any valid TC entry, regardless of 406 which sector it's in. Consequently we must be very careful to 407 invalidate this cache when TC entries are changed or disappear. 408 409 A special .guest address - TRANSTAB_BOGUS_GUEST_ADDR -- must be 410 pointed at to cause that cache entry to miss. This relies on the 411 assumption that no guest code actually has that address, hence a 412 value 0x1 seems good. m_translate gives the client a synthetic 413 segfault if it tries to execute at this address. 414 */ 415 /* 416 typedef 417 struct { 418 Addr guest; 419 Addr host; 420 } 421 FastCacheEntry; 422 */ 423 /*global*/ __attribute__((aligned(16))) 424 FastCacheEntry VG_(tt_fast)[VG_TT_FAST_SIZE]; 425 426 /* Make sure we're not used before initialisation. */ 427 static Bool init_done = False; 428 429 430 /*------------------ STATS DECLS ------------------*/ 431 432 /* Number of fast-cache updates and flushes done. */ 433 static ULong n_fast_flushes = 0; 434 static ULong n_fast_updates = 0; 435 436 /* Number of full lookups done. */ 437 static ULong n_full_lookups = 0; 438 static ULong n_lookup_probes = 0; 439 440 /* Number/osize/tsize of translations entered; also the number of 441 those for which self-checking was requested. */ 442 static ULong n_in_count = 0; 443 static ULong n_in_osize = 0; 444 static ULong n_in_tsize = 0; 445 static ULong n_in_sc_count = 0; 446 447 /* Number/osize of translations discarded due to lack of space. */ 448 static ULong n_dump_count = 0; 449 static ULong n_dump_osize = 0; 450 static ULong n_sectors_recycled = 0; 451 452 /* Number/osize of translations discarded due to requests to do so. */ 453 static ULong n_disc_count = 0; 454 static ULong n_disc_osize = 0; 455 456 457 /*-------------------------------------------------------------*/ 458 /*--- Misc ---*/ 459 /*-------------------------------------------------------------*/ 460 461 static void* ttaux_malloc ( const HChar* tag, SizeT n ) 462 { 463 return VG_(arena_malloc)(VG_AR_TTAUX, tag, n); 464 } 465 466 static void ttaux_free ( void* p ) 467 { 468 VG_(arena_free)(VG_AR_TTAUX, p); 469 } 470 471 472 /*-------------------------------------------------------------*/ 473 /*--- Chaining support ---*/ 474 /*-------------------------------------------------------------*/ 475 476 static inline TTEntry* index_tte ( SECno sNo, TTEno tteNo ) 477 { 478 vg_assert(sNo < n_sectors); 479 vg_assert(tteNo < N_TTES_PER_SECTOR); 480 Sector* s = §ors[sNo]; 481 vg_assert(s->tt); 482 TTEntry* tte = &s->tt[tteNo]; 483 vg_assert(tte->status == InUse); 484 return tte; 485 } 486 487 static void InEdge__init ( InEdge* ie ) 488 { 489 ie->from_sNo = INV_SNO; /* invalid */ 490 ie->from_tteNo = 0; 491 ie->from_offs = 0; 492 ie->to_fastEP = False; 493 } 494 495 static void OutEdge__init ( OutEdge* oe ) 496 { 497 oe->to_sNo = INV_SNO; /* invalid */ 498 oe->to_tteNo = 0; 499 oe->from_offs = 0; 500 } 501 502 static void TTEntry__init ( TTEntry* tte ) 503 { 504 VG_(memset)(tte, 0, sizeof(*tte)); 505 } 506 507 static UWord InEdgeArr__size ( const InEdgeArr* iea ) 508 { 509 if (iea->has_var) { 510 vg_assert(iea->n_fixed == 0); 511 return VG_(sizeXA)(iea->edges.var); 512 } else { 513 vg_assert(iea->n_fixed <= N_FIXED_IN_EDGE_ARR); 514 return iea->n_fixed; 515 } 516 } 517 518 static void InEdgeArr__makeEmpty ( InEdgeArr* iea ) 519 { 520 if (iea->has_var) { 521 vg_assert(iea->n_fixed == 0); 522 VG_(deleteXA)(iea->edges.var); 523 iea->edges.var = NULL; 524 iea->has_var = False; 525 } else { 526 vg_assert(iea->n_fixed <= N_FIXED_IN_EDGE_ARR); 527 iea->n_fixed = 0; 528 } 529 } 530 531 static 532 InEdge* InEdgeArr__index ( InEdgeArr* iea, UWord i ) 533 { 534 if (iea->has_var) { 535 vg_assert(iea->n_fixed == 0); 536 return (InEdge*)VG_(indexXA)(iea->edges.var, i); 537 } else { 538 vg_assert(i < iea->n_fixed); 539 return &iea->edges.fixed[i]; 540 } 541 } 542 543 static 544 void InEdgeArr__deleteIndex ( InEdgeArr* iea, UWord i ) 545 { 546 if (iea->has_var) { 547 vg_assert(iea->n_fixed == 0); 548 VG_(removeIndexXA)(iea->edges.var, i); 549 } else { 550 vg_assert(i < iea->n_fixed); 551 for (; i+1 < iea->n_fixed; i++) { 552 iea->edges.fixed[i] = iea->edges.fixed[i+1]; 553 } 554 iea->n_fixed--; 555 } 556 } 557 558 static 559 void InEdgeArr__add ( InEdgeArr* iea, InEdge* ie ) 560 { 561 if (iea->has_var) { 562 vg_assert(iea->n_fixed == 0); 563 VG_(addToXA)(iea->edges.var, ie); 564 } else { 565 vg_assert(iea->n_fixed <= N_FIXED_IN_EDGE_ARR); 566 if (iea->n_fixed == N_FIXED_IN_EDGE_ARR) { 567 /* The fixed array is full, so we have to initialise an 568 XArray and copy the fixed array into it. */ 569 XArray *var = VG_(newXA)(ttaux_malloc, "transtab.IEA__add", 570 ttaux_free, 571 sizeof(InEdge)); 572 VG_(hintSizeXA) (var, iea->n_fixed + 1); 573 UWord i; 574 for (i = 0; i < iea->n_fixed; i++) { 575 VG_(addToXA)(var, &iea->edges.fixed[i]); 576 } 577 VG_(addToXA)(var, ie); 578 iea->n_fixed = 0; 579 iea->has_var = True; 580 iea->edges.var = var; 581 } else { 582 /* Just add to the fixed array. */ 583 iea->edges.fixed[iea->n_fixed++] = *ie; 584 } 585 } 586 } 587 588 static UWord OutEdgeArr__size ( const OutEdgeArr* oea ) 589 { 590 if (oea->has_var) { 591 vg_assert(oea->n_fixed == 0); 592 return VG_(sizeXA)(oea->edges.var); 593 } else { 594 vg_assert(oea->n_fixed <= N_FIXED_OUT_EDGE_ARR); 595 return oea->n_fixed; 596 } 597 } 598 599 static void OutEdgeArr__makeEmpty ( OutEdgeArr* oea ) 600 { 601 if (oea->has_var) { 602 vg_assert(oea->n_fixed == 0); 603 VG_(deleteXA)(oea->edges.var); 604 oea->edges.var = NULL; 605 oea->has_var = False; 606 } else { 607 vg_assert(oea->n_fixed <= N_FIXED_OUT_EDGE_ARR); 608 oea->n_fixed = 0; 609 } 610 } 611 612 static 613 OutEdge* OutEdgeArr__index ( OutEdgeArr* oea, UWord i ) 614 { 615 if (oea->has_var) { 616 vg_assert(oea->n_fixed == 0); 617 return (OutEdge*)VG_(indexXA)(oea->edges.var, i); 618 } else { 619 vg_assert(i < oea->n_fixed); 620 return &oea->edges.fixed[i]; 621 } 622 } 623 624 static 625 void OutEdgeArr__deleteIndex ( OutEdgeArr* oea, UWord i ) 626 { 627 if (oea->has_var) { 628 vg_assert(oea->n_fixed == 0); 629 VG_(removeIndexXA)(oea->edges.var, i); 630 } else { 631 vg_assert(i < oea->n_fixed); 632 for (; i+1 < oea->n_fixed; i++) { 633 oea->edges.fixed[i] = oea->edges.fixed[i+1]; 634 } 635 oea->n_fixed--; 636 } 637 } 638 639 static 640 void OutEdgeArr__add ( OutEdgeArr* oea, OutEdge* oe ) 641 { 642 if (oea->has_var) { 643 vg_assert(oea->n_fixed == 0); 644 VG_(addToXA)(oea->edges.var, oe); 645 } else { 646 vg_assert(oea->n_fixed <= N_FIXED_OUT_EDGE_ARR); 647 if (oea->n_fixed == N_FIXED_OUT_EDGE_ARR) { 648 /* The fixed array is full, so we have to initialise an 649 XArray and copy the fixed array into it. */ 650 XArray *var = VG_(newXA)(ttaux_malloc, "transtab.OEA__add", 651 ttaux_free, 652 sizeof(OutEdge)); 653 VG_(hintSizeXA) (var, oea->n_fixed+1); 654 UWord i; 655 for (i = 0; i < oea->n_fixed; i++) { 656 VG_(addToXA)(var, &oea->edges.fixed[i]); 657 } 658 VG_(addToXA)(var, oe); 659 oea->n_fixed = 0; 660 oea->has_var = True; 661 oea->edges.var = var; 662 } else { 663 /* Just add to the fixed array. */ 664 oea->edges.fixed[oea->n_fixed++] = *oe; 665 } 666 } 667 } 668 669 static 670 Int HostExtent__cmpOrd ( const void* v1, const void* v2 ) 671 { 672 const HostExtent* hx1 = v1; 673 const HostExtent* hx2 = v2; 674 if (hx1->start + hx1->len <= hx2->start) return -1; 675 if (hx2->start + hx2->len <= hx1->start) return 1; 676 return 0; /* partial overlap */ 677 } 678 679 /* True if hx is a dead host extent, i.e. corresponds to host code 680 of an entry that was invalidated. */ 681 static 682 Bool HostExtent__is_dead (const HostExtent* hx, const Sector* sec) 683 { 684 const TTEno tteNo = hx->tteNo; 685 #define LDEBUG(m) if (DEBUG_TRANSTAB) \ 686 VG_(printf) (m \ 687 " start 0x%p len %u sector %d ttslot %u" \ 688 " tt.entry 0x%lu tt.tcptr 0x%p\n", \ 689 hx->start, hx->len, (int)(sec - sectors), \ 690 hx->tteNo, \ 691 sec->tt[tteNo].entry, sec->tt[tteNo].tcptr) 692 693 /* Entry might have been invalidated and not re-used yet.*/ 694 if (sec->tt[tteNo].status == Deleted) { 695 LDEBUG("found deleted entry"); 696 return True; 697 } 698 /* Maybe we found this entry via a host_extents which was 699 inserted for an entry which was changed to Deleted then 700 re-used after. If this entry was re-used, then its tcptr 701 is >= to host_extents start (i.e. the previous tcptr) + len. 702 This is the case as there is no re-use of host code: a new 703 entry or re-used entry always gets "higher value" host code. */ 704 if ((UChar*) sec->tt[tteNo].tcptr >= hx->start + hx->len) { 705 LDEBUG("found re-used entry"); 706 return True; 707 } 708 709 return False; 710 #undef LDEBUG 711 } 712 713 static __attribute__((noinline)) 714 Bool find_TTEntry_from_hcode( /*OUT*/SECno* from_sNo, 715 /*OUT*/TTEno* from_tteNo, 716 void* hcode ) 717 { 718 SECno i; 719 720 /* Search order logic copied from VG_(search_transtab). */ 721 for (i = 0; i < n_sectors; i++) { 722 SECno sno = sector_search_order[i]; 723 if (UNLIKELY(sno == INV_SNO)) 724 return False; /* run out of sectors to search */ 725 726 const Sector* sec = §ors[sno]; 727 const XArray* /* of HostExtent */ host_extents = sec->host_extents; 728 vg_assert(host_extents); 729 730 HostExtent key; 731 VG_(memset)(&key, 0, sizeof(key)); 732 key.start = hcode; 733 key.len = 1; 734 Word firstW = -1, lastW = -1; 735 Bool found = VG_(lookupXA_UNSAFE)( 736 host_extents, &key, &firstW, &lastW, 737 HostExtent__cmpOrd ); 738 vg_assert(firstW == lastW); // always true, even if not found 739 if (found) { 740 HostExtent* hx = VG_(indexXA)(host_extents, firstW); 741 TTEno tteNo = hx->tteNo; 742 /* Do some additional sanity checks. */ 743 vg_assert(tteNo < N_TTES_PER_SECTOR); 744 745 /* if this hx entry corresponds to dead host code, we must 746 tell this code has not been found, as it cannot be patched. */ 747 if (HostExtent__is_dead (hx, sec)) 748 return False; 749 750 vg_assert(sec->tt[tteNo].status == InUse); 751 /* Can only half check that the found TTEntry contains hcode, 752 due to not having a length value for the hcode in the 753 TTEntry. */ 754 vg_assert((UChar*)sec->tt[tteNo].tcptr <= (UChar*)hcode); 755 /* Looks plausible */ 756 *from_sNo = sno; 757 *from_tteNo = tteNo; 758 return True; 759 } 760 } 761 return False; 762 } 763 764 765 /* Figure out whether or not hcode is jitted code present in the main 766 code cache (but not in the no-redir cache). Used for sanity 767 checking. */ 768 static Bool is_in_the_main_TC ( const void* hcode ) 769 { 770 SECno i, sno; 771 for (i = 0; i < n_sectors; i++) { 772 sno = sector_search_order[i]; 773 if (sno == INV_SNO) 774 break; /* run out of sectors to search */ 775 if ((const UChar*)hcode >= (const UChar*)sectors[sno].tc 776 && (const UChar*)hcode <= (const UChar*)sectors[sno].tc_next 777 + sizeof(ULong) - 1) 778 return True; 779 } 780 return False; 781 } 782 783 784 /* Fulfill a chaining request, and record admin info so we 785 can undo it later, if required. 786 */ 787 void VG_(tt_tc_do_chaining) ( void* from__patch_addr, 788 SECno to_sNo, 789 TTEno to_tteNo, 790 Bool to_fastEP ) 791 { 792 /* Get the CPU info established at startup. */ 793 VexArch arch_host = VexArch_INVALID; 794 VexArchInfo archinfo_host; 795 VG_(bzero_inline)(&archinfo_host, sizeof(archinfo_host)); 796 VG_(machine_get_VexArchInfo)( &arch_host, &archinfo_host ); 797 VexEndness endness_host = archinfo_host.endness; 798 799 // host_code is where we're patching to. So it needs to 800 // take into account, whether we're jumping to the slow 801 // or fast entry point. By definition, the fast entry point 802 // is exactly one event check's worth of code along from 803 // the slow (tcptr) entry point. 804 TTEntry* to_tte = index_tte(to_sNo, to_tteNo); 805 void* host_code = ((UChar*)to_tte->tcptr) 806 + (to_fastEP ? LibVEX_evCheckSzB(arch_host) : 0); 807 808 // stay sane -- the patch point (dst) is in this sector's code cache 809 vg_assert( (UChar*)host_code >= (UChar*)sectors[to_sNo].tc ); 810 vg_assert( (UChar*)host_code <= (UChar*)sectors[to_sNo].tc_next 811 + sizeof(ULong) - 1 ); 812 813 /* Find the TTEntry for the from__ code. This isn't simple since 814 we only know the patch address, which is going to be somewhere 815 inside the from_ block. */ 816 SECno from_sNo = INV_SNO; 817 TTEno from_tteNo = INV_TTE; 818 Bool from_found 819 = find_TTEntry_from_hcode( &from_sNo, &from_tteNo, 820 from__patch_addr ); 821 if (!from_found) { 822 // The from code might have been discarded due to sector re-use 823 // or marked Deleted due to translation invalidation. 824 // In such a case, don't do the chaining. 825 VG_(debugLog)(1,"transtab", 826 "host code %p not found (discarded? sector recycled?)" 827 " => no chaining done\n", 828 from__patch_addr); 829 return; 830 } 831 832 TTEntry* from_tte = index_tte(from_sNo, from_tteNo); 833 834 /* Get VEX to do the patching itself. We have to hand it off 835 since it is host-dependent. */ 836 VexInvalRange vir 837 = LibVEX_Chain( 838 arch_host, endness_host, 839 from__patch_addr, 840 VG_(fnptr_to_fnentry)( 841 to_fastEP ? &VG_(disp_cp_chain_me_to_fastEP) 842 : &VG_(disp_cp_chain_me_to_slowEP)), 843 (void*)host_code 844 ); 845 VG_(invalidate_icache)( (void*)vir.start, vir.len ); 846 847 /* Now do the tricky bit -- update the ch_succs and ch_preds info 848 for the two translations involved, so we can undo the chaining 849 later, which we will have to do if the to_ block gets removed 850 for whatever reason. */ 851 852 /* This is the new from_ -> to_ link to add. */ 853 InEdge ie; 854 InEdge__init(&ie); 855 ie.from_sNo = from_sNo; 856 ie.from_tteNo = from_tteNo; 857 ie.to_fastEP = to_fastEP; 858 HWord from_offs = (HWord)( (UChar*)from__patch_addr 859 - (UChar*)from_tte->tcptr ); 860 vg_assert(from_offs < 100000/* let's say */); 861 ie.from_offs = (UInt)from_offs; 862 863 /* This is the new to_ -> from_ backlink to add. */ 864 OutEdge oe; 865 OutEdge__init(&oe); 866 oe.to_sNo = to_sNo; 867 oe.to_tteNo = to_tteNo; 868 oe.from_offs = (UInt)from_offs; 869 870 /* Add .. */ 871 InEdgeArr__add(&to_tte->in_edges, &ie); 872 OutEdgeArr__add(&from_tte->out_edges, &oe); 873 } 874 875 876 /* Unchain one patch, as described by the specified InEdge. For 877 sanity check purposes only (to check that the patched location is 878 as expected) it also requires the fast and slow entry point 879 addresses of the destination block (that is, the block that owns 880 this InEdge). */ 881 __attribute__((noinline)) 882 static void unchain_one ( VexArch arch_host, VexEndness endness_host, 883 InEdge* ie, 884 void* to_fastEPaddr, void* to_slowEPaddr ) 885 { 886 vg_assert(ie); 887 TTEntry* tte 888 = index_tte(ie->from_sNo, ie->from_tteNo); 889 UChar* place_to_patch 890 = ((UChar*)tte->tcptr) + ie->from_offs; 891 UChar* disp_cp_chain_me 892 = VG_(fnptr_to_fnentry)( 893 ie->to_fastEP ? &VG_(disp_cp_chain_me_to_fastEP) 894 : &VG_(disp_cp_chain_me_to_slowEP) 895 ); 896 UChar* place_to_jump_to_EXPECTED 897 = ie->to_fastEP ? to_fastEPaddr : to_slowEPaddr; 898 899 // stay sane: both src and dst for this unchaining are 900 // in the main code cache 901 vg_assert( is_in_the_main_TC(place_to_patch) ); // src 902 vg_assert( is_in_the_main_TC(place_to_jump_to_EXPECTED) ); // dst 903 // dst check is ok because LibVEX_UnChain checks that 904 // place_to_jump_to_EXPECTED really is the current dst, and 905 // asserts if it isn't. 906 VexInvalRange vir 907 = LibVEX_UnChain( arch_host, endness_host, place_to_patch, 908 place_to_jump_to_EXPECTED, disp_cp_chain_me ); 909 VG_(invalidate_icache)( (void*)vir.start, vir.len ); 910 } 911 912 913 /* The specified block is about to be deleted. Update the preds and 914 succs of its associated blocks accordingly. This includes undoing 915 any chained jumps to this block. */ 916 static 917 void unchain_in_preparation_for_deletion ( VexArch arch_host, 918 VexEndness endness_host, 919 SECno here_sNo, TTEno here_tteNo ) 920 { 921 if (DEBUG_TRANSTAB) 922 VG_(printf)("QQQ unchain_in_prep %u.%u...\n", here_sNo, here_tteNo); 923 UWord i, j, n, m; 924 Int evCheckSzB = LibVEX_evCheckSzB(arch_host); 925 TTEntry* here_tte = index_tte(here_sNo, here_tteNo); 926 if (DEBUG_TRANSTAB) 927 VG_(printf)("... QQQ tt.entry 0x%lu tt.tcptr 0x%p\n", 928 here_tte->entry, here_tte->tcptr); 929 vg_assert(here_tte->status == InUse); 930 931 /* Visit all InEdges owned by here_tte. */ 932 n = InEdgeArr__size(&here_tte->in_edges); 933 for (i = 0; i < n; i++) { 934 InEdge* ie = InEdgeArr__index(&here_tte->in_edges, i); 935 // Undo the chaining. 936 UChar* here_slow_EP = (UChar*)here_tte->tcptr; 937 UChar* here_fast_EP = here_slow_EP + evCheckSzB; 938 unchain_one(arch_host, endness_host, ie, here_fast_EP, here_slow_EP); 939 // Find the corresponding entry in the "from" node's out_edges, 940 // and remove it. 941 TTEntry* from_tte = index_tte(ie->from_sNo, ie->from_tteNo); 942 m = OutEdgeArr__size(&from_tte->out_edges); 943 vg_assert(m > 0); // it must have at least one entry 944 for (j = 0; j < m; j++) { 945 OutEdge* oe = OutEdgeArr__index(&from_tte->out_edges, j); 946 if (oe->to_sNo == here_sNo && oe->to_tteNo == here_tteNo 947 && oe->from_offs == ie->from_offs) 948 break; 949 } 950 vg_assert(j < m); // "oe must be findable" 951 OutEdgeArr__deleteIndex(&from_tte->out_edges, j); 952 } 953 954 /* Visit all OutEdges owned by here_tte. */ 955 n = OutEdgeArr__size(&here_tte->out_edges); 956 for (i = 0; i < n; i++) { 957 OutEdge* oe = OutEdgeArr__index(&here_tte->out_edges, i); 958 // Find the corresponding entry in the "to" node's in_edges, 959 // and remove it. 960 TTEntry* to_tte = index_tte(oe->to_sNo, oe->to_tteNo); 961 m = InEdgeArr__size(&to_tte->in_edges); 962 vg_assert(m > 0); // it must have at least one entry 963 for (j = 0; j < m; j++) { 964 InEdge* ie = InEdgeArr__index(&to_tte->in_edges, j); 965 if (ie->from_sNo == here_sNo && ie->from_tteNo == here_tteNo 966 && ie->from_offs == oe->from_offs) 967 break; 968 } 969 vg_assert(j < m); // "ie must be findable" 970 InEdgeArr__deleteIndex(&to_tte->in_edges, j); 971 } 972 973 InEdgeArr__makeEmpty(&here_tte->in_edges); 974 OutEdgeArr__makeEmpty(&here_tte->out_edges); 975 } 976 977 978 /*-------------------------------------------------------------*/ 979 /*--- Address-range equivalence class stuff ---*/ 980 /*-------------------------------------------------------------*/ 981 982 /* Return equivalence class number for a range. */ 983 984 static EClassNo range_to_eclass ( Addr start, UInt len ) 985 { 986 UInt mask = (1 << ECLASS_WIDTH) - 1; 987 UInt lo = (UInt)start; 988 UInt hi = lo + len - 1; 989 UInt loBits = (lo >> ECLASS_SHIFT) & mask; 990 UInt hiBits = (hi >> ECLASS_SHIFT) & mask; 991 if (loBits == hiBits) { 992 vg_assert(loBits < ECLASS_N-1); 993 return loBits; 994 } else { 995 return ECLASS_MISC; 996 } 997 } 998 999 1000 /* Calculates the equivalence class numbers for any VexGuestExtent. 1001 These are written in *eclasses, which must be big enough to hold 3 1002 Ints. The number written, between 1 and 3, is returned. The 1003 eclasses are presented in order, and any duplicates are removed. 1004 */ 1005 1006 static 1007 Int vexGuestExtents_to_eclasses ( /*OUT*/EClassNo* eclasses, 1008 const VexGuestExtents* vge ) 1009 { 1010 1011 # define SWAP(_lv1,_lv2) \ 1012 do { Int t = _lv1; _lv1 = _lv2; _lv2 = t; } while (0) 1013 1014 Int i, j, n_ec; 1015 EClassNo r; 1016 1017 vg_assert(vge->n_used >= 1 && vge->n_used <= 3); 1018 1019 n_ec = 0; 1020 for (i = 0; i < vge->n_used; i++) { 1021 r = range_to_eclass( vge->base[i], vge->len[i] ); 1022 if (r == ECLASS_MISC) 1023 goto bad; 1024 /* only add if we haven't already seen it */ 1025 for (j = 0; j < n_ec; j++) 1026 if (eclasses[j] == r) 1027 break; 1028 if (j == n_ec) 1029 eclasses[n_ec++] = r; 1030 } 1031 1032 if (n_ec == 1) 1033 return 1; 1034 1035 if (n_ec == 2) { 1036 /* sort */ 1037 if (eclasses[0] > eclasses[1]) 1038 SWAP(eclasses[0], eclasses[1]); 1039 return 2; 1040 } 1041 1042 if (n_ec == 3) { 1043 /* sort */ 1044 if (eclasses[0] > eclasses[2]) 1045 SWAP(eclasses[0], eclasses[2]); 1046 if (eclasses[0] > eclasses[1]) 1047 SWAP(eclasses[0], eclasses[1]); 1048 if (eclasses[1] > eclasses[2]) 1049 SWAP(eclasses[1], eclasses[2]); 1050 return 3; 1051 } 1052 1053 /* NOTREACHED */ 1054 vg_assert(0); 1055 1056 bad: 1057 eclasses[0] = ECLASS_MISC; 1058 return 1; 1059 1060 # undef SWAP 1061 } 1062 1063 1064 /* Add tteno to the set of entries listed for equivalence class ec in 1065 this sector. Returns used location in eclass array. */ 1066 1067 static 1068 UInt addEClassNo ( /*MOD*/Sector* sec, EClassNo ec, TTEno tteno ) 1069 { 1070 Int old_sz, new_sz, i, r; 1071 TTEno *old_ar, *new_ar; 1072 1073 vg_assert(ec >= 0 && ec < ECLASS_N); 1074 vg_assert(tteno < N_TTES_PER_SECTOR); 1075 1076 if (DEBUG_TRANSTAB) VG_(printf)("ec %d gets %d\n", ec, (Int)tteno); 1077 1078 if (sec->ec2tte_used[ec] >= sec->ec2tte_size[ec]) { 1079 1080 vg_assert(sec->ec2tte_used[ec] == sec->ec2tte_size[ec]); 1081 1082 old_sz = sec->ec2tte_size[ec]; 1083 old_ar = sec->ec2tte[ec]; 1084 new_sz = old_sz==0 ? 8 : old_sz<64 ? 2*old_sz : (3*old_sz)/2; 1085 new_ar = ttaux_malloc("transtab.aECN.1", 1086 new_sz * sizeof(TTEno)); 1087 for (i = 0; i < old_sz; i++) 1088 new_ar[i] = old_ar[i]; 1089 if (old_ar) 1090 ttaux_free(old_ar); 1091 sec->ec2tte_size[ec] = new_sz; 1092 sec->ec2tte[ec] = new_ar; 1093 1094 if (DEBUG_TRANSTAB) VG_(printf)("expand ec %d to %d\n", ec, new_sz); 1095 } 1096 1097 /* Common case */ 1098 r = sec->ec2tte_used[ec]++; 1099 vg_assert(r >= 0 && r < sec->ec2tte_size[ec]); 1100 sec->ec2tte[ec][r] = tteno; 1101 return (UInt)r; 1102 } 1103 1104 1105 /* 'vge' is being added to 'sec' at TT entry 'tteno'. Add appropriate 1106 eclass entries to 'sec'. */ 1107 1108 static 1109 void upd_eclasses_after_add ( /*MOD*/Sector* sec, TTEno tteno ) 1110 { 1111 Int i, r; 1112 EClassNo eclasses[3]; 1113 TTEntry* tte; 1114 vg_assert(tteno >= 0 && tteno < N_TTES_PER_SECTOR); 1115 1116 tte = &sec->tt[tteno]; 1117 r = vexGuestExtents_to_eclasses( eclasses, &tte->vge ); 1118 1119 vg_assert(r >= 1 && r <= 3); 1120 tte->n_tte2ec = r; 1121 1122 for (i = 0; i < r; i++) { 1123 tte->tte2ec_ec[i] = eclasses[i]; 1124 tte->tte2ec_ix[i] = addEClassNo( sec, eclasses[i], tteno ); 1125 } 1126 } 1127 1128 1129 /* Check the eclass info in 'sec' to ensure it is consistent. Returns 1130 True if OK, False if something's not right. Expensive. */ 1131 1132 static Bool sanity_check_eclasses_in_sector ( const Sector* sec ) 1133 { 1134 # define BAD(_str) do { whassup = (_str); goto bad; } while (0) 1135 1136 const HChar* whassup = NULL; 1137 Int j, k, n, ec_idx; 1138 EClassNo i; 1139 EClassNo ec_num; 1140 TTEntry* tte; 1141 TTEno tteno; 1142 ULong* tce; 1143 1144 /* Basic checks on this sector */ 1145 if (sec->tt_n_inuse < 0 || sec->tt_n_inuse > N_TTES_PER_SECTOR) 1146 BAD("invalid sec->tt_n_inuse"); 1147 tce = sec->tc_next; 1148 if (tce < &sec->tc[0] || tce > &sec->tc[tc_sector_szQ]) 1149 BAD("sec->tc_next points outside tc"); 1150 1151 /* For each eclass ... */ 1152 for (i = 0; i < ECLASS_N; i++) { 1153 if (sec->ec2tte_size[i] == 0 && sec->ec2tte[i] != NULL) 1154 BAD("ec2tte_size/ec2tte mismatch(1)"); 1155 if (sec->ec2tte_size[i] != 0 && sec->ec2tte[i] == NULL) 1156 BAD("ec2tte_size/ec2tte mismatch(2)"); 1157 if (sec->ec2tte_used[i] < 0 1158 || sec->ec2tte_used[i] > sec->ec2tte_size[i]) 1159 BAD("implausible ec2tte_used"); 1160 if (sec->ec2tte_used[i] == 0) 1161 continue; 1162 1163 /* For each tt reference in each eclass .. ensure the reference 1164 is to a valid tt entry, and that the entry's address ranges 1165 really include this eclass. */ 1166 1167 for (j = 0; j < sec->ec2tte_used[i]; j++) { 1168 tteno = sec->ec2tte[i][j]; 1169 if (tteno == EC2TTE_DELETED) 1170 continue; 1171 if (tteno >= N_TTES_PER_SECTOR) 1172 BAD("implausible tteno"); 1173 tte = &sec->tt[tteno]; 1174 if (tte->status != InUse) 1175 BAD("tteno points to non-inuse tte"); 1176 if (tte->n_tte2ec < 1 || tte->n_tte2ec > 3) 1177 BAD("tte->n_tte2ec out of range"); 1178 /* Exactly least one of tte->eclasses[0 .. tte->n_eclasses-1] 1179 must equal i. Inspect tte's eclass info. */ 1180 n = 0; 1181 for (k = 0; k < tte->n_tte2ec; k++) { 1182 if (k < tte->n_tte2ec-1 1183 && tte->tte2ec_ec[k] >= tte->tte2ec_ec[k+1]) 1184 BAD("tte->tte2ec_ec[..] out of order"); 1185 ec_num = tte->tte2ec_ec[k]; 1186 if (ec_num < 0 || ec_num >= ECLASS_N) 1187 BAD("tte->tte2ec_ec[..] out of range"); 1188 if (ec_num != i) 1189 continue; 1190 ec_idx = tte->tte2ec_ix[k]; 1191 if (ec_idx < 0 || ec_idx >= sec->ec2tte_used[i]) 1192 BAD("tte->tte2ec_ix[..] out of range"); 1193 if (ec_idx == j) 1194 n++; 1195 } 1196 if (n != 1) 1197 BAD("tteno does not point back at eclass"); 1198 } 1199 } 1200 1201 /* That establishes that for each forward pointer from TTEntrys 1202 there is a corresponding backward pointer from the eclass[] 1203 arrays. However, it doesn't rule out the possibility of other, 1204 bogus pointers in the eclass[] arrays. So do those similarly: 1205 scan through them and check the TTEntryies they point at point 1206 back. */ 1207 1208 for (tteno = 0; tteno < N_TTES_PER_SECTOR; tteno++) { 1209 1210 tte = &sec->tt[tteno]; 1211 if (tte->status == Empty || tte->status == Deleted) { 1212 if (tte->n_tte2ec != 0) 1213 BAD("tte->n_eclasses nonzero for unused tte"); 1214 continue; 1215 } 1216 1217 vg_assert(tte->status == InUse); 1218 1219 if (tte->n_tte2ec < 1 || tte->n_tte2ec > 3) 1220 BAD("tte->n_eclasses out of range(2)"); 1221 1222 for (j = 0; j < tte->n_tte2ec; j++) { 1223 ec_num = tte->tte2ec_ec[j]; 1224 if (ec_num < 0 || ec_num >= ECLASS_N) 1225 BAD("tte->eclass[..] out of range"); 1226 ec_idx = tte->tte2ec_ix[j]; 1227 if (ec_idx < 0 || ec_idx >= sec->ec2tte_used[ec_num]) 1228 BAD("tte->ec_idx[..] out of range(2)"); 1229 if (sec->ec2tte[ec_num][ec_idx] != tteno) 1230 BAD("ec2tte does not point back to tte"); 1231 } 1232 } 1233 1234 return True; 1235 1236 bad: 1237 if (whassup) 1238 VG_(debugLog)(0, "transtab", "eclass sanity fail: %s\n", whassup); 1239 1240 # if 0 1241 VG_(printf)("eclass = %d\n", i); 1242 VG_(printf)("tteno = %d\n", (Int)tteno); 1243 switch (tte->status) { 1244 case InUse: VG_(printf)("InUse\n"); break; 1245 case Deleted: VG_(printf)("Deleted\n"); break; 1246 case Empty: VG_(printf)("Empty\n"); break; 1247 } 1248 if (tte->status != Empty) { 1249 for (k = 0; k < tte->vge.n_used; k++) 1250 VG_(printf)("0x%lx %u\n", tte->vge.base[k], (UInt)tte->vge.len[k]); 1251 } 1252 # endif 1253 1254 return False; 1255 1256 # undef BAD 1257 } 1258 1259 1260 /* Sanity check absolutely everything. True == check passed. */ 1261 1262 /* forwards */ 1263 static Bool sanity_check_redir_tt_tc ( void ); 1264 1265 static Bool sanity_check_sector_search_order ( void ) 1266 { 1267 SECno i, j, nListed; 1268 /* assert the array is the right size */ 1269 vg_assert(MAX_N_SECTORS == (sizeof(sector_search_order) 1270 / sizeof(sector_search_order[0]))); 1271 /* Check it's of the form valid_sector_numbers ++ [INV_SNO, INV_SNO, ..] */ 1272 for (i = 0; i < n_sectors; i++) { 1273 if (sector_search_order[i] == INV_SNO 1274 || sector_search_order[i] >= n_sectors) 1275 break; 1276 } 1277 nListed = i; 1278 for (/* */; i < n_sectors; i++) { 1279 if (sector_search_order[i] != INV_SNO) 1280 break; 1281 } 1282 if (i != n_sectors) 1283 return False; 1284 /* Check each sector number only appears once */ 1285 for (i = 0; i < n_sectors; i++) { 1286 if (sector_search_order[i] == INV_SNO) 1287 continue; 1288 for (j = i+1; j < n_sectors; j++) { 1289 if (sector_search_order[j] == sector_search_order[i]) 1290 return False; 1291 } 1292 } 1293 /* Check that the number of listed sectors equals the number 1294 in use, by counting nListed back down. */ 1295 for (i = 0; i < n_sectors; i++) { 1296 if (sectors[i].tc != NULL) 1297 nListed--; 1298 } 1299 if (nListed != 0) 1300 return False; 1301 return True; 1302 } 1303 1304 static Bool sanity_check_all_sectors ( void ) 1305 { 1306 SECno sno; 1307 Bool sane; 1308 Sector* sec; 1309 for (sno = 0; sno < n_sectors; sno++) { 1310 Int i; 1311 Int nr_not_dead_hx = 0; 1312 Int szhxa; 1313 sec = §ors[sno]; 1314 if (sec->tc == NULL) 1315 continue; 1316 sane = sanity_check_eclasses_in_sector( sec ); 1317 if (!sane) 1318 return False; 1319 szhxa = VG_(sizeXA)(sec->host_extents); 1320 for (i = 0; i < szhxa; i++) { 1321 const HostExtent* hx = VG_(indexXA)(sec->host_extents, i); 1322 if (!HostExtent__is_dead (hx, sec)) 1323 nr_not_dead_hx++; 1324 } 1325 if (nr_not_dead_hx != sec->tt_n_inuse) { 1326 VG_(debugLog)(0, "transtab", 1327 "nr_not_dead_hx %d sanity fail " 1328 "(expected == in use %d)\n", 1329 nr_not_dead_hx, sec->tt_n_inuse); 1330 return False; 1331 } 1332 } 1333 1334 if ( !sanity_check_redir_tt_tc() ) 1335 return False; 1336 if ( !sanity_check_sector_search_order() ) 1337 return False; 1338 return True; 1339 } 1340 1341 1342 1343 /*-------------------------------------------------------------*/ 1344 /*--- Add/find translations ---*/ 1345 /*-------------------------------------------------------------*/ 1346 1347 static UInt vge_osize ( const VexGuestExtents* vge ) 1348 { 1349 UInt i, n = 0; 1350 for (i = 0; i < vge->n_used; i++) 1351 n += (UInt)vge->len[i]; 1352 return n; 1353 } 1354 1355 static Bool isValidSector ( SECno sector ) 1356 { 1357 if (sector == INV_SNO || sector >= n_sectors) 1358 return False; 1359 return True; 1360 } 1361 1362 static inline HTTno HASH_TT ( Addr key ) 1363 { 1364 UInt kHi = sizeof(Addr) == 4 ? 0 : (key >> 32); 1365 UInt kLo = (UInt)key; 1366 UInt k32 = kHi ^ kLo; 1367 UInt ror = 7; 1368 if (ror > 0) 1369 k32 = (k32 >> ror) | (k32 << (32-ror)); 1370 return (HTTno)(k32 % N_HTTES_PER_SECTOR); 1371 } 1372 1373 static void setFastCacheEntry ( Addr key, ULong* tcptr ) 1374 { 1375 UInt cno = (UInt)VG_TT_FAST_HASH(key); 1376 VG_(tt_fast)[cno].guest = key; 1377 VG_(tt_fast)[cno].host = (Addr)tcptr; 1378 n_fast_updates++; 1379 /* This shouldn't fail. It should be assured by m_translate 1380 which should reject any attempt to make translation of code 1381 starting at TRANSTAB_BOGUS_GUEST_ADDR. */ 1382 vg_assert(VG_(tt_fast)[cno].guest != TRANSTAB_BOGUS_GUEST_ADDR); 1383 } 1384 1385 /* Invalidate the fast cache VG_(tt_fast). */ 1386 static void invalidateFastCache ( void ) 1387 { 1388 UInt j; 1389 /* This loop is popular enough to make it worth unrolling a 1390 bit, at least on ppc32. */ 1391 vg_assert(VG_TT_FAST_SIZE > 0 && (VG_TT_FAST_SIZE % 4) == 0); 1392 for (j = 0; j < VG_TT_FAST_SIZE; j += 4) { 1393 VG_(tt_fast)[j+0].guest = TRANSTAB_BOGUS_GUEST_ADDR; 1394 VG_(tt_fast)[j+1].guest = TRANSTAB_BOGUS_GUEST_ADDR; 1395 VG_(tt_fast)[j+2].guest = TRANSTAB_BOGUS_GUEST_ADDR; 1396 VG_(tt_fast)[j+3].guest = TRANSTAB_BOGUS_GUEST_ADDR; 1397 } 1398 1399 vg_assert(j == VG_TT_FAST_SIZE); 1400 n_fast_flushes++; 1401 } 1402 1403 1404 static TTEno get_empty_tt_slot(SECno sNo) 1405 { 1406 TTEno i; 1407 1408 i = sectors[sNo].empty_tt_list; 1409 sectors[sNo].empty_tt_list = sectors[sNo].tt[i].usage.next_empty_tte; 1410 1411 vg_assert (i >= 0 && i < N_TTES_PER_SECTOR); 1412 1413 return i; 1414 } 1415 1416 static void add_in_empty_tt_list (SECno sNo, TTEno tteno) 1417 { 1418 sectors[sNo].tt[tteno].usage.next_empty_tte = sectors[sNo].empty_tt_list; 1419 sectors[sNo].empty_tt_list = tteno; 1420 } 1421 1422 static void initialiseSector ( SECno sno ) 1423 { 1424 UInt i; 1425 SysRes sres; 1426 Sector* sec; 1427 vg_assert(isValidSector(sno)); 1428 1429 { Bool sane = sanity_check_sector_search_order(); 1430 vg_assert(sane); 1431 } 1432 sec = §ors[sno]; 1433 1434 if (sec->tc == NULL) { 1435 1436 /* Sector has never been used before. Need to allocate tt and 1437 tc. */ 1438 vg_assert(sec->tt == NULL); 1439 vg_assert(sec->tc_next == NULL); 1440 vg_assert(sec->tt_n_inuse == 0); 1441 for (EClassNo e = 0; e < ECLASS_N; e++) { 1442 vg_assert(sec->ec2tte_size[e] == 0); 1443 vg_assert(sec->ec2tte_used[e] == 0); 1444 vg_assert(sec->ec2tte[e] == NULL); 1445 } 1446 vg_assert(sec->host_extents == NULL); 1447 1448 if (VG_(clo_stats) || VG_(debugLog_getLevel)() >= 1) 1449 VG_(dmsg)("transtab: " "allocate sector %d\n", sno); 1450 1451 sres = VG_(am_mmap_anon_float_valgrind)( 8 * tc_sector_szQ ); 1452 if (sr_isError(sres)) { 1453 VG_(out_of_memory_NORETURN)("initialiseSector(TC)", 1454 8 * tc_sector_szQ ); 1455 /*NOTREACHED*/ 1456 } 1457 sec->tc = (ULong*)(Addr)sr_Res(sres); 1458 1459 sres = VG_(am_mmap_anon_float_valgrind) 1460 ( N_TTES_PER_SECTOR * sizeof(TTEntry) ); 1461 if (sr_isError(sres)) { 1462 VG_(out_of_memory_NORETURN)("initialiseSector(TT)", 1463 N_TTES_PER_SECTOR * sizeof(TTEntry) ); 1464 /*NOTREACHED*/ 1465 } 1466 sec->tt = (TTEntry*)(Addr)sr_Res(sres); 1467 sec->empty_tt_list = HTT_EMPTY; 1468 for (TTEno ei = 0; ei < N_TTES_PER_SECTOR; ei++) { 1469 sec->tt[ei].status = Empty; 1470 sec->tt[ei].n_tte2ec = 0; 1471 add_in_empty_tt_list(sno, ei); 1472 } 1473 1474 sres = VG_(am_mmap_anon_float_valgrind) 1475 ( N_HTTES_PER_SECTOR * sizeof(TTEno) ); 1476 if (sr_isError(sres)) { 1477 VG_(out_of_memory_NORETURN)("initialiseSector(HTT)", 1478 N_HTTES_PER_SECTOR * sizeof(TTEno) ); 1479 /*NOTREACHED*/ 1480 } 1481 sec->htt = (TTEno*)(Addr)sr_Res(sres); 1482 for (HTTno hi = 0; hi < N_HTTES_PER_SECTOR; hi++) 1483 sec->htt[hi] = HTT_EMPTY; 1484 1485 /* Set up the host_extents array. */ 1486 sec->host_extents 1487 = VG_(newXA)(ttaux_malloc, "transtab.initialiseSector(host_extents)", 1488 ttaux_free, 1489 sizeof(HostExtent)); 1490 1491 /* Add an entry in the sector_search_order */ 1492 for (i = 0; i < n_sectors; i++) { 1493 if (sector_search_order[i] == INV_SNO) 1494 break; 1495 } 1496 vg_assert(i >= 0 && i < n_sectors); 1497 sector_search_order[i] = sno; 1498 1499 if (VG_(clo_verbosity) > 2) 1500 VG_(message)(Vg_DebugMsg, "TT/TC: initialise sector %d\n", sno); 1501 1502 } else { 1503 1504 /* Sector has been used before. Dump the old contents. */ 1505 if (VG_(clo_stats) || VG_(debugLog_getLevel)() >= 1) 1506 VG_(dmsg)("transtab: " "recycle sector %d\n", sno); 1507 n_sectors_recycled++; 1508 1509 vg_assert(sec->tt != NULL); 1510 vg_assert(sec->tc_next != NULL); 1511 n_dump_count += sec->tt_n_inuse; 1512 1513 VexArch arch_host = VexArch_INVALID; 1514 VexArchInfo archinfo_host; 1515 VG_(bzero_inline)(&archinfo_host, sizeof(archinfo_host)); 1516 VG_(machine_get_VexArchInfo)( &arch_host, &archinfo_host ); 1517 VexEndness endness_host = archinfo_host.endness; 1518 1519 /* Visit each just-about-to-be-abandoned translation. */ 1520 if (DEBUG_TRANSTAB) VG_(printf)("QQQ unlink-entire-sector: %d START\n", 1521 sno); 1522 sec->empty_tt_list = HTT_EMPTY; 1523 for (TTEno ei = 0; ei < N_TTES_PER_SECTOR; ei++) { 1524 if (sec->tt[ei].status == InUse) { 1525 vg_assert(sec->tt[ei].n_tte2ec >= 1); 1526 vg_assert(sec->tt[ei].n_tte2ec <= 3); 1527 n_dump_osize += vge_osize(&sec->tt[ei].vge); 1528 /* Tell the tool too. */ 1529 if (VG_(needs).superblock_discards) { 1530 VG_TDICT_CALL( tool_discard_superblock_info, 1531 sec->tt[ei].entry, 1532 sec->tt[ei].vge ); 1533 } 1534 unchain_in_preparation_for_deletion(arch_host, 1535 endness_host, sno, ei); 1536 } else { 1537 vg_assert(sec->tt[ei].n_tte2ec == 0); 1538 } 1539 sec->tt[ei].status = Empty; 1540 sec->tt[ei].n_tte2ec = 0; 1541 add_in_empty_tt_list(sno, ei); 1542 } 1543 for (HTTno hi = 0; hi < N_HTTES_PER_SECTOR; hi++) 1544 sec->htt[hi] = HTT_EMPTY; 1545 1546 if (DEBUG_TRANSTAB) VG_(printf)("QQQ unlink-entire-sector: %d END\n", 1547 sno); 1548 1549 /* Free up the eclass structures. */ 1550 for (EClassNo e = 0; e < ECLASS_N; e++) { 1551 if (sec->ec2tte_size[e] == 0) { 1552 vg_assert(sec->ec2tte_used[e] == 0); 1553 vg_assert(sec->ec2tte[e] == NULL); 1554 } else { 1555 vg_assert(sec->ec2tte[e] != NULL); 1556 ttaux_free(sec->ec2tte[e]); 1557 sec->ec2tte[e] = NULL; 1558 sec->ec2tte_size[e] = 0; 1559 sec->ec2tte_used[e] = 0; 1560 } 1561 } 1562 1563 /* Empty out the host extents array. */ 1564 vg_assert(sec->host_extents != NULL); 1565 VG_(dropTailXA)(sec->host_extents, VG_(sizeXA)(sec->host_extents)); 1566 vg_assert(VG_(sizeXA)(sec->host_extents) == 0); 1567 1568 /* Sanity check: ensure it is already in 1569 sector_search_order[]. */ 1570 SECno ix; 1571 for (ix = 0; ix < n_sectors; ix++) { 1572 if (sector_search_order[ix] == sno) 1573 break; 1574 } 1575 vg_assert(ix >= 0 && ix < n_sectors); 1576 1577 if (VG_(clo_verbosity) > 2) 1578 VG_(message)(Vg_DebugMsg, "TT/TC: recycle sector %d\n", sno); 1579 } 1580 1581 sec->tc_next = sec->tc; 1582 sec->tt_n_inuse = 0; 1583 1584 invalidateFastCache(); 1585 1586 { Bool sane = sanity_check_sector_search_order(); 1587 vg_assert(sane); 1588 } 1589 } 1590 1591 /* Add a translation of vge to TT/TC. The translation is temporarily 1592 in code[0 .. code_len-1]. 1593 1594 pre: youngest_sector points to a valid (although possibly full) 1595 sector. 1596 */ 1597 void VG_(add_to_transtab)( const VexGuestExtents* vge, 1598 Addr entry, 1599 Addr code, 1600 UInt code_len, 1601 Bool is_self_checking, 1602 Int offs_profInc, 1603 UInt n_guest_instrs ) 1604 { 1605 Int tcAvailQ, reqdQ, y; 1606 ULong *tcptr, *tcptr2; 1607 UChar* srcP; 1608 UChar* dstP; 1609 1610 vg_assert(init_done); 1611 vg_assert(vge->n_used >= 1 && vge->n_used <= 3); 1612 1613 /* 60000: should agree with N_TMPBUF in m_translate.c. */ 1614 vg_assert(code_len > 0 && code_len < 60000); 1615 1616 /* Generally stay sane */ 1617 vg_assert(n_guest_instrs < 200); /* it can be zero, tho */ 1618 1619 if (DEBUG_TRANSTAB) 1620 VG_(printf)("add_to_transtab(entry = 0x%lx, len = %u) ...\n", 1621 entry, code_len); 1622 1623 n_in_count++; 1624 n_in_tsize += code_len; 1625 n_in_osize += vge_osize(vge); 1626 if (is_self_checking) 1627 n_in_sc_count++; 1628 1629 y = youngest_sector; 1630 vg_assert(isValidSector(y)); 1631 1632 if (sectors[y].tc == NULL) 1633 initialiseSector(y); 1634 1635 /* Try putting the translation in this sector. */ 1636 reqdQ = (code_len + 7) >> 3; 1637 1638 /* Will it fit in tc? */ 1639 tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 1640 - ((ULong*)(sectors[y].tc_next)); 1641 vg_assert(tcAvailQ >= 0); 1642 vg_assert(tcAvailQ <= tc_sector_szQ); 1643 1644 if (tcAvailQ < reqdQ 1645 || sectors[y].tt_n_inuse >= N_TTES_PER_SECTOR) { 1646 /* No. So move on to the next sector. Either it's never been 1647 used before, in which case it will get its tt/tc allocated 1648 now, or it has been used before, in which case it is set to be 1649 empty, hence throwing out the oldest sector. */ 1650 vg_assert(tc_sector_szQ > 0); 1651 Int tt_loading_pct = (100 * sectors[y].tt_n_inuse) 1652 / N_HTTES_PER_SECTOR; 1653 Int tc_loading_pct = (100 * (tc_sector_szQ - tcAvailQ)) 1654 / tc_sector_szQ; 1655 if (VG_(clo_stats) || VG_(debugLog_getLevel)() >= 1) { 1656 VG_(dmsg)("transtab: " 1657 "declare sector %d full " 1658 "(TT loading %2d%%, TC loading %2d%%, avg tce size %d)\n", 1659 y, tt_loading_pct, tc_loading_pct, 1660 8 * (tc_sector_szQ - tcAvailQ)/sectors[y].tt_n_inuse); 1661 } 1662 youngest_sector++; 1663 if (youngest_sector >= n_sectors) 1664 youngest_sector = 0; 1665 y = youngest_sector; 1666 initialiseSector(y); 1667 } 1668 1669 /* Be sure ... */ 1670 tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 1671 - ((ULong*)(sectors[y].tc_next)); 1672 vg_assert(tcAvailQ >= 0); 1673 vg_assert(tcAvailQ <= tc_sector_szQ); 1674 vg_assert(tcAvailQ >= reqdQ); 1675 vg_assert(sectors[y].tt_n_inuse < N_TTES_PER_SECTOR); 1676 vg_assert(sectors[y].tt_n_inuse >= 0); 1677 1678 /* Copy into tc. */ 1679 tcptr = sectors[y].tc_next; 1680 vg_assert(tcptr >= §ors[y].tc[0]); 1681 vg_assert(tcptr <= §ors[y].tc[tc_sector_szQ]); 1682 1683 dstP = (UChar*)tcptr; 1684 srcP = (UChar*)code; 1685 VG_(memcpy)(dstP, srcP, code_len); 1686 sectors[y].tc_next += reqdQ; 1687 sectors[y].tt_n_inuse++; 1688 1689 /* more paranoia */ 1690 tcptr2 = sectors[y].tc_next; 1691 vg_assert(tcptr2 >= §ors[y].tc[0]); 1692 vg_assert(tcptr2 <= §ors[y].tc[tc_sector_szQ]); 1693 1694 /* Find an empty tt slot, and use it. There must be such a slot 1695 since tt is never allowed to get completely full. */ 1696 TTEno tteix = get_empty_tt_slot(y); 1697 TTEntry__init(§ors[y].tt[tteix]); 1698 sectors[y].tt[tteix].status = InUse; 1699 sectors[y].tt[tteix].tcptr = tcptr; 1700 sectors[y].tt[tteix].usage.prof.count = 0; 1701 sectors[y].tt[tteix].usage.prof.weight = 1702 n_guest_instrs == 0 ? 1 : n_guest_instrs; 1703 sectors[y].tt[tteix].vge = *vge; 1704 sectors[y].tt[tteix].entry = entry; 1705 1706 // Point an htt entry to the tt slot 1707 HTTno htti = HASH_TT(entry); 1708 vg_assert(htti >= 0 && htti < N_HTTES_PER_SECTOR); 1709 while (True) { 1710 if (sectors[y].htt[htti] == HTT_EMPTY 1711 || sectors[y].htt[htti] == HTT_DELETED) 1712 break; 1713 htti++; 1714 if (htti >= N_HTTES_PER_SECTOR) 1715 htti = 0; 1716 } 1717 sectors[y].htt[htti] = tteix; 1718 1719 /* Patch in the profile counter location, if necessary. */ 1720 if (offs_profInc != -1) { 1721 vg_assert(offs_profInc >= 0 && offs_profInc < code_len); 1722 VexArch arch_host = VexArch_INVALID; 1723 VexArchInfo archinfo_host; 1724 VG_(bzero_inline)(&archinfo_host, sizeof(archinfo_host)); 1725 VG_(machine_get_VexArchInfo)( &arch_host, &archinfo_host ); 1726 VexEndness endness_host = archinfo_host.endness; 1727 VexInvalRange vir 1728 = LibVEX_PatchProfInc( arch_host, endness_host, 1729 dstP + offs_profInc, 1730 §ors[y].tt[tteix].usage.prof.count ); 1731 VG_(invalidate_icache)( (void*)vir.start, vir.len ); 1732 } 1733 1734 VG_(invalidate_icache)( dstP, code_len ); 1735 1736 /* Add this entry to the host_extents map, checking that we're 1737 adding in order. */ 1738 { HostExtent hx; 1739 hx.start = (UChar*)tcptr; 1740 hx.len = code_len; 1741 hx.tteNo = tteix; 1742 vg_assert(hx.len > 0); /* bsearch fails w/ zero length entries */ 1743 XArray* hx_array = sectors[y].host_extents; 1744 vg_assert(hx_array); 1745 Word n = VG_(sizeXA)(hx_array); 1746 if (n > 0) { 1747 HostExtent* hx_prev = (HostExtent*)VG_(indexXA)(hx_array, n-1); 1748 vg_assert(hx_prev->start + hx_prev->len <= hx.start); 1749 } 1750 VG_(addToXA)(hx_array, &hx); 1751 if (DEBUG_TRANSTAB) 1752 VG_(printf)("... hx.start 0x%p hx.len %u sector %d ttslot %d\n", 1753 hx.start, hx.len, y, tteix); 1754 } 1755 1756 /* Update the fast-cache. */ 1757 setFastCacheEntry( entry, tcptr ); 1758 1759 /* Note the eclass numbers for this translation. */ 1760 upd_eclasses_after_add( §ors[y], tteix ); 1761 } 1762 1763 1764 /* Search for the translation of the given guest address. If 1765 requested, a successful search can also cause the fast-caches to be 1766 updated. 1767 */ 1768 Bool VG_(search_transtab) ( /*OUT*/Addr* res_hcode, 1769 /*OUT*/SECno* res_sNo, 1770 /*OUT*/TTEno* res_tteNo, 1771 Addr guest_addr, 1772 Bool upd_cache ) 1773 { 1774 SECno i, sno; 1775 HTTno j, k, kstart; 1776 TTEno tti; 1777 1778 vg_assert(init_done); 1779 /* Find the initial probe point just once. It will be the same in 1780 all sectors and avoids multiple expensive % operations. */ 1781 n_full_lookups++; 1782 kstart = HASH_TT(guest_addr); 1783 vg_assert(kstart >= 0 && kstart < N_HTTES_PER_SECTOR); 1784 1785 /* Search in all the sectors,using sector_search_order[] as a 1786 heuristic guide as to what order to visit the sectors. */ 1787 for (i = 0; i < n_sectors; i++) { 1788 1789 sno = sector_search_order[i]; 1790 if (UNLIKELY(sno == INV_SNO)) 1791 return False; /* run out of sectors to search */ 1792 1793 k = kstart; 1794 for (j = 0; j < N_HTTES_PER_SECTOR; j++) { 1795 n_lookup_probes++; 1796 tti = sectors[sno].htt[k]; 1797 if (tti < N_TTES_PER_SECTOR 1798 && sectors[sno].tt[tti].entry == guest_addr) { 1799 /* found it */ 1800 if (upd_cache) 1801 setFastCacheEntry( 1802 guest_addr, sectors[sno].tt[tti].tcptr ); 1803 if (res_hcode) 1804 *res_hcode = (Addr)sectors[sno].tt[tti].tcptr; 1805 if (res_sNo) 1806 *res_sNo = sno; 1807 if (res_tteNo) 1808 *res_tteNo = tti; 1809 /* pull this one one step closer to the front. For large 1810 apps this more or less halves the number of required 1811 probes. */ 1812 if (i > 0) { 1813 Int tmp = sector_search_order[i-1]; 1814 sector_search_order[i-1] = sector_search_order[i]; 1815 sector_search_order[i] = tmp; 1816 } 1817 return True; 1818 } 1819 // tti is HTT_EMPTY or HTT_DELETED or not the entry of guest_addr 1820 if (sectors[sno].htt[k] == HTT_EMPTY) 1821 break; /* not found in this sector */ 1822 k++; 1823 if (k == N_HTTES_PER_SECTOR) 1824 k = 0; 1825 } 1826 1827 /* If we fall off the end, all entries are InUse and not 1828 matching, or Deleted. In any case we did not find it in this 1829 sector. */ 1830 } 1831 1832 /* Not found in any sector. */ 1833 return False; 1834 } 1835 1836 1837 /*-------------------------------------------------------------*/ 1838 /*--- Delete translations. ---*/ 1839 /*-------------------------------------------------------------*/ 1840 1841 /* forward */ 1842 static void unredir_discard_translations( Addr, ULong ); 1843 1844 /* Stuff for deleting translations which intersect with a given 1845 address range. Unfortunately, to make this run at a reasonable 1846 speed, it is complex. */ 1847 1848 static inline 1849 Bool overlap1 ( Addr s1, ULong r1, Addr s2, ULong r2 ) 1850 { 1851 Addr e1 = s1 + r1 - 1; 1852 Addr e2 = s2 + r2 - 1; 1853 if (e1 < s2 || e2 < s1) 1854 return False; 1855 return True; 1856 } 1857 1858 static inline 1859 Bool overlaps ( Addr start, ULong range, const VexGuestExtents* vge ) 1860 { 1861 if (overlap1(start, range, vge->base[0], vge->len[0])) 1862 return True; 1863 if (vge->n_used < 2) 1864 return False; 1865 if (overlap1(start, range, vge->base[1], vge->len[1])) 1866 return True; 1867 if (vge->n_used < 3) 1868 return False; 1869 if (overlap1(start, range, vge->base[2], vge->len[2])) 1870 return True; 1871 return False; 1872 } 1873 1874 1875 /* Delete a tt entry, and update all the eclass data accordingly. */ 1876 1877 static void delete_tte ( /*MOD*/Sector* sec, SECno secNo, TTEno tteno, 1878 VexArch arch_host, VexEndness endness_host ) 1879 { 1880 Int i, ec_idx; 1881 EClassNo ec_num; 1882 TTEntry* tte; 1883 1884 /* sec and secNo are mutually redundant; cross-check. */ 1885 vg_assert(sec == §ors[secNo]); 1886 1887 vg_assert(tteno >= 0 && tteno < N_TTES_PER_SECTOR); 1888 tte = &sec->tt[tteno]; 1889 vg_assert(tte->status == InUse); 1890 vg_assert(tte->n_tte2ec >= 1 && tte->n_tte2ec <= 3); 1891 1892 /* Unchain .. */ 1893 unchain_in_preparation_for_deletion(arch_host, endness_host, secNo, tteno); 1894 1895 /* Deal with the ec-to-tte links first. */ 1896 for (i = 0; i < tte->n_tte2ec; i++) { 1897 ec_num = tte->tte2ec_ec[i]; 1898 ec_idx = tte->tte2ec_ix[i]; 1899 vg_assert(ec_num >= 0 && ec_num < ECLASS_N); 1900 vg_assert(ec_idx >= 0); 1901 vg_assert(ec_idx < sec->ec2tte_used[ec_num]); 1902 /* Assert that the two links point at each other. */ 1903 vg_assert(sec->ec2tte[ec_num][ec_idx] == tteno); 1904 /* "delete" the pointer back to here. */ 1905 sec->ec2tte[ec_num][ec_idx] = EC2TTE_DELETED; 1906 } 1907 1908 /* Now fix up this TTEntry. */ 1909 /* Mark the entry as deleted in htt. 1910 Note: we could avoid the below hash table search by 1911 adding a reference from tte to its hash position in tt. */ 1912 HTTno j; 1913 HTTno k = HASH_TT(tte->entry); 1914 vg_assert(k >= 0 && k < N_HTTES_PER_SECTOR); 1915 for (j = 0; j < N_HTTES_PER_SECTOR; j++) { 1916 if (sec->htt[k] == tteno) 1917 break; 1918 k++; 1919 if (k == N_HTTES_PER_SECTOR) 1920 k = 0; 1921 } 1922 vg_assert(j < N_HTTES_PER_SECTOR); 1923 sec->htt[k] = HTT_DELETED; 1924 tte->status = Deleted; 1925 tte->n_tte2ec = 0; 1926 add_in_empty_tt_list(secNo, tteno); 1927 1928 /* Stats .. */ 1929 sec->tt_n_inuse--; 1930 n_disc_count++; 1931 n_disc_osize += vge_osize(&tte->vge); 1932 1933 /* Tell the tool too. */ 1934 if (VG_(needs).superblock_discards) { 1935 VG_TDICT_CALL( tool_discard_superblock_info, 1936 tte->entry, 1937 tte->vge ); 1938 } 1939 } 1940 1941 1942 /* Delete translations from sec which intersect specified range, but 1943 only consider translations in the specified eclass. */ 1944 1945 static 1946 Bool delete_translations_in_sector_eclass ( /*MOD*/Sector* sec, SECno secNo, 1947 Addr guest_start, ULong range, 1948 EClassNo ec, 1949 VexArch arch_host, 1950 VexEndness endness_host ) 1951 { 1952 Int i; 1953 TTEno tteno; 1954 Bool anyDeld = False; 1955 TTEntry* tte; 1956 1957 vg_assert(ec >= 0 && ec < ECLASS_N); 1958 1959 for (i = 0; i < sec->ec2tte_used[ec]; i++) { 1960 1961 tteno = sec->ec2tte[ec][i]; 1962 if (tteno == EC2TTE_DELETED) { 1963 /* already deleted */ 1964 continue; 1965 } 1966 1967 vg_assert(tteno < N_TTES_PER_SECTOR); 1968 1969 tte = &sec->tt[tteno]; 1970 vg_assert(tte->status == InUse); 1971 1972 if (overlaps( guest_start, range, &tte->vge )) { 1973 anyDeld = True; 1974 delete_tte( sec, secNo, tteno, arch_host, endness_host ); 1975 } 1976 1977 } 1978 1979 return anyDeld; 1980 } 1981 1982 1983 /* Delete translations from sec which intersect specified range, the 1984 slow way, by inspecting all translations in sec. */ 1985 1986 static 1987 Bool delete_translations_in_sector ( /*MOD*/Sector* sec, SECno secNo, 1988 Addr guest_start, ULong range, 1989 VexArch arch_host, 1990 VexEndness endness_host ) 1991 { 1992 TTEno i; 1993 Bool anyDeld = False; 1994 1995 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 1996 if (sec->tt[i].status == InUse 1997 && overlaps( guest_start, range, &sec->tt[i].vge )) { 1998 anyDeld = True; 1999 delete_tte( sec, secNo, i, arch_host, endness_host ); 2000 } 2001 } 2002 2003 return anyDeld; 2004 } 2005 2006 2007 void VG_(discard_translations) ( Addr guest_start, ULong range, 2008 const HChar* who ) 2009 { 2010 Sector* sec; 2011 SECno sno; 2012 EClassNo ec; 2013 Bool anyDeleted = False; 2014 2015 vg_assert(init_done); 2016 2017 VG_(debugLog)(2, "transtab", 2018 "discard_translations(0x%lx, %llu) req by %s\n", 2019 guest_start, range, who ); 2020 2021 /* Pre-deletion sanity check */ 2022 if (VG_(clo_sanity_level >= 4)) { 2023 Bool sane = sanity_check_all_sectors(); 2024 vg_assert(sane); 2025 } 2026 2027 if (range == 0) 2028 return; 2029 2030 VexArch arch_host = VexArch_INVALID; 2031 VexArchInfo archinfo_host; 2032 VG_(bzero_inline)(&archinfo_host, sizeof(archinfo_host)); 2033 VG_(machine_get_VexArchInfo)( &arch_host, &archinfo_host ); 2034 VexEndness endness_host = archinfo_host.endness; 2035 2036 /* There are two different ways to do this. 2037 2038 If the range fits within a single address-range equivalence 2039 class, as will be the case for a cache line sized invalidation, 2040 then we only have to inspect the set of translations listed in 2041 that equivalence class, and also in the "sin-bin" equivalence 2042 class ECLASS_MISC. 2043 2044 Otherwise, the invalidation is of a larger range and probably 2045 results from munmap. In this case it's (probably!) faster just 2046 to inspect all translations, dump those we don't want, and 2047 regenerate the equivalence class information (since modifying it 2048 in-situ is even more expensive). 2049 */ 2050 2051 /* First off, figure out if the range falls within a single class, 2052 and if so which one. */ 2053 2054 ec = ECLASS_MISC; 2055 if (range < (1ULL << ECLASS_SHIFT)) 2056 ec = range_to_eclass( guest_start, (UInt)range ); 2057 2058 /* if ec is ECLASS_MISC then we aren't looking at just a single 2059 class, so use the slow scheme. Else use the fast scheme, 2060 examining 'ec' and ECLASS_MISC. */ 2061 2062 if (ec != ECLASS_MISC) { 2063 2064 VG_(debugLog)(2, "transtab", 2065 " FAST, ec = %d\n", ec); 2066 2067 /* Fast scheme */ 2068 vg_assert(ec >= 0 && ec < ECLASS_MISC); 2069 2070 for (sno = 0; sno < n_sectors; sno++) { 2071 sec = §ors[sno]; 2072 if (sec->tc == NULL) 2073 continue; 2074 anyDeleted |= delete_translations_in_sector_eclass( 2075 sec, sno, guest_start, range, ec, 2076 arch_host, endness_host 2077 ); 2078 anyDeleted |= delete_translations_in_sector_eclass( 2079 sec, sno, guest_start, range, ECLASS_MISC, 2080 arch_host, endness_host 2081 ); 2082 } 2083 2084 } else { 2085 2086 /* slow scheme */ 2087 2088 VG_(debugLog)(2, "transtab", 2089 " SLOW, ec = %d\n", ec); 2090 2091 for (sno = 0; sno < n_sectors; sno++) { 2092 sec = §ors[sno]; 2093 if (sec->tc == NULL) 2094 continue; 2095 anyDeleted |= delete_translations_in_sector( 2096 sec, sno, guest_start, range, 2097 arch_host, endness_host 2098 ); 2099 } 2100 2101 } 2102 2103 if (anyDeleted) 2104 invalidateFastCache(); 2105 2106 /* don't forget the no-redir cache */ 2107 unredir_discard_translations( guest_start, range ); 2108 2109 /* Post-deletion sanity check */ 2110 if (VG_(clo_sanity_level >= 4)) { 2111 TTEno i; 2112 TTEntry* tte; 2113 Bool sane = sanity_check_all_sectors(); 2114 vg_assert(sane); 2115 /* But now, also check the requested address range isn't 2116 present anywhere. */ 2117 for (sno = 0; sno < n_sectors; sno++) { 2118 sec = §ors[sno]; 2119 if (sec->tc == NULL) 2120 continue; 2121 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 2122 tte = &sec->tt[i]; 2123 if (tte->status != InUse) 2124 continue; 2125 vg_assert(!overlaps( guest_start, range, &tte->vge )); 2126 } 2127 } 2128 } 2129 } 2130 2131 /* Whether or not tools may discard translations. */ 2132 Bool VG_(ok_to_discard_translations) = False; 2133 2134 /* This function is exported to tools which can use it to discard 2135 translations, provided it is safe to do so. */ 2136 void VG_(discard_translations_safely) ( Addr start, SizeT len, 2137 const HChar* who ) 2138 { 2139 vg_assert(VG_(ok_to_discard_translations)); 2140 VG_(discard_translations)(start, len, who); 2141 } 2142 2143 /*------------------------------------------------------------*/ 2144 /*--- AUXILIARY: the unredirected TT/TC ---*/ 2145 /*------------------------------------------------------------*/ 2146 2147 /* A very simple translation cache which holds a small number of 2148 unredirected translations. This is completely independent of the 2149 main tt/tc structures. When unredir_tc or unredir_tt becomes full, 2150 both structures are simply dumped and we start over. 2151 2152 Since these translations are unredirected, the search key is (by 2153 definition) the first address entry in the .vge field. */ 2154 2155 /* Sized to hold 500 translations of average size 1000 bytes. */ 2156 2157 #define UNREDIR_SZB 1000 2158 2159 #define N_UNREDIR_TT 500 2160 #define N_UNREDIR_TCQ (N_UNREDIR_TT * UNREDIR_SZB / sizeof(ULong)) 2161 2162 typedef 2163 struct { 2164 VexGuestExtents vge; 2165 Addr hcode; 2166 Bool inUse; 2167 } 2168 UTCEntry; 2169 2170 /* We just allocate forwards in _tc, never deleting. */ 2171 static ULong *unredir_tc; 2172 static Int unredir_tc_used = N_UNREDIR_TCQ; 2173 2174 /* Slots in _tt can come into use and out again (.inUse). 2175 Nevertheless _tt_highwater is maintained so that invalidations 2176 don't have to scan all the slots when only a few are in use. 2177 _tt_highwater holds the index of the highest ever allocated 2178 slot. */ 2179 static UTCEntry unredir_tt[N_UNREDIR_TT]; 2180 static Int unredir_tt_highwater; 2181 2182 2183 static void init_unredir_tt_tc ( void ) 2184 { 2185 Int i; 2186 if (unredir_tc == NULL) { 2187 SysRes sres = VG_(am_mmap_anon_float_valgrind) 2188 ( N_UNREDIR_TT * UNREDIR_SZB ); 2189 if (sr_isError(sres)) { 2190 VG_(out_of_memory_NORETURN)("init_unredir_tt_tc", 2191 N_UNREDIR_TT * UNREDIR_SZB); 2192 /*NOTREACHED*/ 2193 } 2194 unredir_tc = (ULong *)(Addr)sr_Res(sres); 2195 } 2196 unredir_tc_used = 0; 2197 for (i = 0; i < N_UNREDIR_TT; i++) 2198 unredir_tt[i].inUse = False; 2199 unredir_tt_highwater = -1; 2200 } 2201 2202 /* Do a sanity check; return False on failure. */ 2203 static Bool sanity_check_redir_tt_tc ( void ) 2204 { 2205 Int i; 2206 if (unredir_tt_highwater < -1) return False; 2207 if (unredir_tt_highwater >= N_UNREDIR_TT) return False; 2208 2209 for (i = unredir_tt_highwater+1; i < N_UNREDIR_TT; i++) 2210 if (unredir_tt[i].inUse) 2211 return False; 2212 2213 if (unredir_tc_used < 0) return False; 2214 if (unredir_tc_used > N_UNREDIR_TCQ) return False; 2215 2216 return True; 2217 } 2218 2219 2220 /* Add an UNREDIRECTED translation of vge to TT/TC. The translation 2221 is temporarily in code[0 .. code_len-1]. 2222 */ 2223 void VG_(add_to_unredir_transtab)( const VexGuestExtents* vge, 2224 Addr entry, 2225 Addr code, 2226 UInt code_len ) 2227 { 2228 Int i, j, code_szQ; 2229 HChar *srcP, *dstP; 2230 2231 vg_assert(sanity_check_redir_tt_tc()); 2232 2233 /* This is the whole point: it's not redirected! */ 2234 vg_assert(entry == vge->base[0]); 2235 2236 /* How many unredir_tt slots are needed */ 2237 code_szQ = (code_len + 7) / 8; 2238 2239 /* Look for an empty unredir_tc slot */ 2240 for (i = 0; i < N_UNREDIR_TT; i++) 2241 if (!unredir_tt[i].inUse) 2242 break; 2243 2244 if (i >= N_UNREDIR_TT || code_szQ > (N_UNREDIR_TCQ - unredir_tc_used)) { 2245 /* It's full; dump everything we currently have */ 2246 init_unredir_tt_tc(); 2247 i = 0; 2248 } 2249 2250 vg_assert(unredir_tc_used >= 0); 2251 vg_assert(unredir_tc_used <= N_UNREDIR_TCQ); 2252 vg_assert(code_szQ > 0); 2253 vg_assert(code_szQ + unredir_tc_used <= N_UNREDIR_TCQ); 2254 vg_assert(i >= 0 && i < N_UNREDIR_TT); 2255 vg_assert(unredir_tt[i].inUse == False); 2256 2257 if (i > unredir_tt_highwater) 2258 unredir_tt_highwater = i; 2259 2260 dstP = (HChar*)&unredir_tc[unredir_tc_used]; 2261 srcP = (HChar*)code; 2262 for (j = 0; j < code_len; j++) 2263 dstP[j] = srcP[j]; 2264 2265 VG_(invalidate_icache)( dstP, code_len ); 2266 2267 unredir_tt[i].inUse = True; 2268 unredir_tt[i].vge = *vge; 2269 unredir_tt[i].hcode = (Addr)dstP; 2270 2271 unredir_tc_used += code_szQ; 2272 vg_assert(unredir_tc_used >= 0); 2273 vg_assert(unredir_tc_used <= N_UNREDIR_TCQ); 2274 2275 vg_assert(&dstP[code_len] <= (HChar*)&unredir_tc[unredir_tc_used]); 2276 } 2277 2278 Bool VG_(search_unredir_transtab) ( /*OUT*/Addr* result, 2279 Addr guest_addr ) 2280 { 2281 Int i; 2282 for (i = 0; i < N_UNREDIR_TT; i++) { 2283 if (!unredir_tt[i].inUse) 2284 continue; 2285 if (unredir_tt[i].vge.base[0] == guest_addr) { 2286 *result = unredir_tt[i].hcode; 2287 return True; 2288 } 2289 } 2290 return False; 2291 } 2292 2293 static void unredir_discard_translations( Addr guest_start, ULong range ) 2294 { 2295 Int i; 2296 2297 vg_assert(sanity_check_redir_tt_tc()); 2298 2299 for (i = 0; i <= unredir_tt_highwater; i++) { 2300 if (unredir_tt[i].inUse 2301 && overlaps( guest_start, range, &unredir_tt[i].vge)) 2302 unredir_tt[i].inUse = False; 2303 } 2304 } 2305 2306 2307 /*------------------------------------------------------------*/ 2308 /*--- Initialisation. ---*/ 2309 /*------------------------------------------------------------*/ 2310 2311 void VG_(init_tt_tc) ( void ) 2312 { 2313 Int i, avg_codeszQ; 2314 2315 vg_assert(!init_done); 2316 init_done = True; 2317 2318 /* Otherwise lots of things go wrong... */ 2319 vg_assert(sizeof(ULong) == 8); 2320 vg_assert(sizeof(TTEno) == sizeof(HTTno)); 2321 vg_assert(sizeof(TTEno) == 2); 2322 vg_assert(N_TTES_PER_SECTOR <= N_HTTES_PER_SECTOR); 2323 vg_assert(N_HTTES_PER_SECTOR < INV_TTE); 2324 vg_assert(N_HTTES_PER_SECTOR < EC2TTE_DELETED); 2325 vg_assert(N_HTTES_PER_SECTOR < HTT_EMPTY); 2326 /* check fast cache entries really are 2 words long */ 2327 vg_assert(sizeof(Addr) == sizeof(void*)); 2328 vg_assert(sizeof(FastCacheEntry) == 2 * sizeof(Addr)); 2329 /* check fast cache entries are packed back-to-back with no spaces */ 2330 vg_assert(sizeof( VG_(tt_fast) ) 2331 == VG_TT_FAST_SIZE * sizeof(FastCacheEntry)); 2332 /* check fast cache is aligned as we requested. Not fatal if it 2333 isn't, but we might as well make sure. */ 2334 vg_assert(VG_IS_16_ALIGNED( ((Addr) & VG_(tt_fast)[0]) )); 2335 2336 if (VG_(clo_verbosity) > 2) 2337 VG_(message)(Vg_DebugMsg, 2338 "TT/TC: VG_(init_tt_tc) " 2339 "(startup of code management)\n"); 2340 2341 /* Figure out how big each tc area should be. */ 2342 if (VG_(clo_avg_transtab_entry_size) == 0) 2343 avg_codeszQ = (VG_(details).avg_translation_sizeB + 7) / 8; 2344 else 2345 avg_codeszQ = (VG_(clo_avg_transtab_entry_size) + 7) / 8; 2346 tc_sector_szQ = N_TTES_PER_SECTOR * (1 + avg_codeszQ); 2347 2348 /* Ensure the calculated value is not way crazy. */ 2349 vg_assert(tc_sector_szQ >= 2 * N_TTES_PER_SECTOR); 2350 vg_assert(tc_sector_szQ <= 100 * N_TTES_PER_SECTOR); 2351 2352 n_sectors = VG_(clo_num_transtab_sectors); 2353 vg_assert(n_sectors >= MIN_N_SECTORS); 2354 vg_assert(n_sectors <= MAX_N_SECTORS); 2355 2356 /* Initialise the sectors, even the ones we aren't going to use. 2357 Set all fields to zero. */ 2358 youngest_sector = 0; 2359 for (i = 0; i < MAX_N_SECTORS; i++) 2360 VG_(memset)(§ors[i], 0, sizeof(sectors[i])); 2361 2362 /* Initialise the sector_search_order hint table, including the 2363 entries we aren't going to use. */ 2364 for (i = 0; i < MAX_N_SECTORS; i++) 2365 sector_search_order[i] = INV_SNO; 2366 2367 /* Initialise the fast cache. */ 2368 invalidateFastCache(); 2369 2370 /* and the unredir tt/tc */ 2371 init_unredir_tt_tc(); 2372 2373 if (VG_(clo_verbosity) > 2 || VG_(clo_stats) 2374 || VG_(debugLog_getLevel) () >= 2) { 2375 VG_(message)(Vg_DebugMsg, 2376 "TT/TC: cache: %s--avg-transtab-entry-size=%d, " 2377 "%stool provided default %d\n", 2378 VG_(clo_avg_transtab_entry_size) == 0 ? "ignoring " : "using ", 2379 VG_(clo_avg_transtab_entry_size), 2380 VG_(clo_avg_transtab_entry_size) == 0 ? "using " : "ignoring ", 2381 VG_(details).avg_translation_sizeB); 2382 VG_(message)(Vg_DebugMsg, 2383 "TT/TC: cache: %d sectors of %d bytes each = %d total TC\n", 2384 n_sectors, 8 * tc_sector_szQ, 2385 n_sectors * 8 * tc_sector_szQ ); 2386 VG_(message)(Vg_DebugMsg, 2387 "TT/TC: table: %d tables[%d] of %d bytes each = %d total TT\n", 2388 n_sectors, N_TTES_PER_SECTOR, 2389 (int)(N_TTES_PER_SECTOR * sizeof(TTEntry)), 2390 (int)(n_sectors * N_TTES_PER_SECTOR * sizeof(TTEntry))); 2391 VG_(message)(Vg_DebugMsg, 2392 "TT/TC: table: %d tt entries each = %d total tt entries\n", 2393 N_TTES_PER_SECTOR, n_sectors * N_TTES_PER_SECTOR); 2394 VG_(message)(Vg_DebugMsg, 2395 "TT/TC: table: %d htt[%d] of %d bytes each = %d total HTT" 2396 " (htt[%d] %d%% max occup)\n", 2397 n_sectors, N_HTTES_PER_SECTOR, 2398 (int)(N_HTTES_PER_SECTOR * sizeof(TTEno)), 2399 (int)(n_sectors * N_HTTES_PER_SECTOR * sizeof(TTEno)), 2400 N_HTTES_PER_SECTOR, SECTOR_TT_LIMIT_PERCENT); 2401 } 2402 } 2403 2404 2405 /*------------------------------------------------------------*/ 2406 /*--- Printing out statistics. ---*/ 2407 /*------------------------------------------------------------*/ 2408 2409 static Double safe_idiv( ULong a, ULong b ) 2410 { 2411 return (b == 0 ? 0 : (Double)a / (Double)b); 2412 } 2413 2414 UInt VG_(get_bbs_translated) ( void ) 2415 { 2416 return n_in_count; 2417 } 2418 2419 void VG_(print_tt_tc_stats) ( void ) 2420 { 2421 VG_(message)(Vg_DebugMsg, 2422 " tt/tc: %'llu tt lookups requiring %'llu probes\n", 2423 n_full_lookups, n_lookup_probes ); 2424 VG_(message)(Vg_DebugMsg, 2425 " tt/tc: %'llu fast-cache updates, %'llu flushes\n", 2426 n_fast_updates, n_fast_flushes ); 2427 2428 VG_(message)(Vg_DebugMsg, 2429 " transtab: new %'lld " 2430 "(%'llu -> %'llu; ratio %3.1f) [%'llu scs] " 2431 "avg tce size %d\n", 2432 n_in_count, n_in_osize, n_in_tsize, 2433 safe_idiv(n_in_tsize, n_in_osize), 2434 n_in_sc_count, 2435 (int) (n_in_tsize / (n_in_count ? n_in_count : 1))); 2436 VG_(message)(Vg_DebugMsg, 2437 " transtab: dumped %'llu (%'llu -> ?" "?) " 2438 "(sectors recycled %'llu)\n", 2439 n_dump_count, n_dump_osize, n_sectors_recycled ); 2440 VG_(message)(Vg_DebugMsg, 2441 " transtab: discarded %'llu (%'llu -> ?" "?)\n", 2442 n_disc_count, n_disc_osize ); 2443 2444 if (DEBUG_TRANSTAB) { 2445 VG_(printf)("\n"); 2446 for (EClassNo e = 0; e < ECLASS_N; e++) { 2447 VG_(printf)(" %4d", sectors[0].ec2tte_used[e]); 2448 if (e % 16 == 15) 2449 VG_(printf)("\n"); 2450 } 2451 VG_(printf)("\n\n"); 2452 } 2453 } 2454 2455 /*------------------------------------------------------------*/ 2456 /*--- Printing out of profiling results. ---*/ 2457 /*------------------------------------------------------------*/ 2458 2459 static ULong score ( const TTEntry* tte ) 2460 { 2461 return ((ULong)tte->usage.prof.weight) * ((ULong)tte->usage.prof.count); 2462 } 2463 2464 ULong VG_(get_SB_profile) ( SBProfEntry tops[], UInt n_tops ) 2465 { 2466 SECno sno; 2467 Int r, s; 2468 ULong score_total; 2469 TTEno i; 2470 2471 /* First, compute the total weighted count, and find the top N 2472 ttes. tops contains pointers to the most-used n_tops blocks, in 2473 descending order (viz, tops[0] is the highest scorer). */ 2474 for (s = 0; s < n_tops; s++) { 2475 tops[s].addr = 0; 2476 tops[s].score = 0; 2477 } 2478 2479 score_total = 0; 2480 2481 for (sno = 0; sno < n_sectors; sno++) { 2482 if (sectors[sno].tc == NULL) 2483 continue; 2484 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 2485 if (sectors[sno].tt[i].status != InUse) 2486 continue; 2487 score_total += score(§ors[sno].tt[i]); 2488 /* Find the rank for sectors[sno].tt[i]. */ 2489 r = n_tops-1; 2490 while (True) { 2491 if (r == -1) 2492 break; 2493 if (tops[r].addr == 0) { 2494 r--; 2495 continue; 2496 } 2497 if ( score(§ors[sno].tt[i]) > tops[r].score ) { 2498 r--; 2499 continue; 2500 } 2501 break; 2502 } 2503 r++; 2504 vg_assert(r >= 0 && r <= n_tops); 2505 /* This bb should be placed at r, and bbs above it shifted 2506 upwards one slot. */ 2507 if (r < n_tops) { 2508 for (s = n_tops-1; s > r; s--) 2509 tops[s] = tops[s-1]; 2510 tops[r].addr = sectors[sno].tt[i].entry; 2511 tops[r].score = score( §ors[sno].tt[i] ); 2512 } 2513 } 2514 } 2515 2516 /* Now zero out all the counter fields, so that we can make 2517 multiple calls here and just get the values since the last call, 2518 each time, rather than values accumulated for the whole run. */ 2519 for (sno = 0; sno < n_sectors; sno++) { 2520 if (sectors[sno].tc == NULL) 2521 continue; 2522 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 2523 if (sectors[sno].tt[i].status != InUse) 2524 continue; 2525 sectors[sno].tt[i].usage.prof.count = 0; 2526 } 2527 } 2528 2529 return score_total; 2530 } 2531 2532 /*--------------------------------------------------------------------*/ 2533 /*--- end ---*/ 2534 /*--------------------------------------------------------------------*/ 2535
