m_transtab.c revision 10f08cf5b84882eebbb6712a7be890577650e8ad
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-2005 Julian Seward 12 jseward@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_machine.h" // ppc32: VG_(cache_line_size_ppc32) 34#include "pub_core_libcbase.h" 35#include "pub_core_libcassert.h" 36#include "pub_core_libcmman.h" // For VG_(get_memory_from_mmap)() 37#include "pub_core_libcprint.h" 38#include "pub_core_options.h" 39#include "pub_core_tooliface.h" // For VG_(details).avg_translation_sizeB 40#include "pub_core_transtab.h" 41 42/* #define DEBUG_TRANSTAB */ 43 44 45/*-------------------------------------------------------------*/ 46/*--- Management of the FIFO-based translation table+cache. ---*/ 47/*-------------------------------------------------------------*/ 48 49/*------------------ CONSTANTS ------------------*/ 50 51/* Number of sectors the TC is divided into. If you need a larger 52 overall translation cache, increase this value. */ 53#define N_SECTORS 8 54 55/* Number of TC entries in each sector. This needs to be a prime 56 number to work properly, and it is strongly recommended not to 57 change this. */ 58#define N_TTES_PER_SECTOR /*30011*/ 40009 59 60/* Because each sector contains a hash table of TTEntries, we need to 61 specify the maximum allowable loading, after which the sector is 62 deemed full. */ 63#define SECTOR_TT_LIMIT_PERCENT 60 64 65/* The sector is deemed full when this many entries are in it. */ 66#define N_TTES_PER_SECTOR_USABLE \ 67 ((N_TTES_PER_SECTOR * SECTOR_TT_LIMIT_PERCENT) / 100) 68 69 70/*------------------ TYPES ------------------*/ 71 72/* A translation-cache entry is two parts: 73 - The guest address of the first (entry) bb in the translation, 74 as a 64-bit word. 75 - One or more 64-bit words containing the code. 76 It is supposed to be 64-bit aligned. 77*/ 78/* 79typedef 80 struct { 81 Addr64 orig_addr; 82 ULong code[0]; 83 } 84 TCEntry; 85*/ 86 87/* A translation-table entry. This indicates precisely which areas of 88 guest code are included in the translation, and contains all other 89 auxiliary info too. */ 90typedef 91 struct { 92 /* Profiling only: the count and weight (arbitrary meaning) for 93 this translation. Weight is a property of the translation 94 itself and computed once when the translation is created. 95 Count is an entry count for the translation and is 96 incremented by 1 every time the translation is used, if we 97 are profiling. */ 98 UInt count; 99 UShort weight; 100 101 /* Status of the slot. Note, we need to be able to do lazy 102 deletion, hence the Deleted state. */ 103 enum { InUse, Deleted, Empty } status; 104 105 /* Pointer to the corresponding TCEntry (must be in the same 106 sector!) */ 107 ULong* tce; 108 109 /* This is the original guest address that purportedly is the 110 entry point of the translation. You might think that .entry 111 should be the same as .vge->base[0], and most of the time it 112 is. However, when doing redirections, that is not the case. 113 .vge must always correctly describe the guest code sections 114 from which this translation was made. However, .entry may or 115 may not be a lie, depending on whether or not we're doing 116 redirection. */ 117 Addr64 entry; 118 119 /* This structure describes precisely what ranges of guest code 120 the translation covers, so we can decide whether or not to 121 delete it when translations of a given address range are 122 invalidated. */ 123 VexGuestExtents vge; 124 } 125 TTEntry; 126 127 128/* Finally, a sector itself. Each sector contains an array of 129 TCEntries, which hold code, and an array of TTEntries, containing 130 all required administrative info. Profiling is supported using the 131 TTEntry .count and .weight fields, if required. Each sector is 132 independent in that no cross-sector references are allowed. 133 134 If the sector is not in use, all three pointers are NULL and 135 tt_n_inuse is zero. 136*/ 137typedef 138 struct { 139 /* The TCEntry area. Size of this depends on the average 140 translation size. We try and size it so it becomes full 141 precisely when this sector's translation table (tt) reaches 142 its load limit (SECTOR_TT_LIMIT_PERCENT). */ 143 ULong* tc; 144 145 /* The TTEntry array. This is a fixed size, always containing 146 exactly N_TTES_PER_SECTOR entries. */ 147 TTEntry* tt; 148 149 /* This points to the current allocation point in tc. */ 150 ULong* tc_next; 151 152 /* The count of tt entries with state InUse. */ 153 Int tt_n_inuse; 154 } 155 Sector; 156 157 158/*------------------ DECLS ------------------*/ 159 160/* The root data structure is an array of sectors. The index of the 161 youngest sector is recorded, and new translations are put into that 162 sector. When it fills up, we move along to the next sector and 163 start to fill that up, wrapping around at the end of the array. 164 That way, once all N_TC_SECTORS have been bought into use for the 165 first time, and are full, we then re-use the oldest sector, 166 endlessly. 167 168 When running, youngest sector should be between >= 0 and < 169 N_TC_SECTORS. The initial -1 value indicates the TT/TC system is 170 not yet initialised. 171*/ 172static Sector sectors[N_SECTORS]; 173static Int youngest_sector = -1; 174 175/* The number of ULongs in each TCEntry area. This is computed once 176 at startup and does not change. */ 177static Int tc_sector_szQ; 178 179 180/* Fast helper for the TC. A direct-mapped cache which holds a 181 pointer to a TC entry which may or may not be the correct one, but 182 which we hope usually is. This array is referred to directly from 183 <arch>/dispatch.S. 184 185 Entries in tt_fast may point to any valid TC entry, regardless of 186 which sector it's in. Consequently we must be very careful to 187 invalidate this cache when TC entries are changed or disappear. 188 189 A special TCEntry -- bogus_tc_entry -- must be pointed at to cause 190 that cache entry to miss. This relies on the assumption that no 191 guest code actually has an address of 0x1. 192*/ 193/*global*/ ULong* VG_(tt_fast)[VG_TT_FAST_SIZE]; 194 195static ULong bogus_tc_entry = (Addr64)1; 196 197 198/* For profiling, we have a parallel array of pointers to .count 199 fields in TT entries. Again, these pointers must be invalidated 200 when translations disappear. A NULL pointer suffices to indicate 201 an unused slot. 202 203 tt_fast and tt_fastN change together: if tt_fast[i] points to 204 bogus_tc_entry then the corresponding tt_fastN[i] must be null. If 205 tt_fast[i] points to some TC entry somewhere, then tt_fastN[i] 206 *must* point to the .count field of the corresponding TT entry. 207 208 tt_fast and tt_fastN are referred to from assembly code 209 (dispatch.S). 210*/ 211/*global*/ UInt* VG_(tt_fastN)[VG_TT_FAST_SIZE]; 212 213 214/* Make sure we're not used before initialisation. */ 215static Bool init_done = False; 216 217 218/*------------------ STATS DECLS ------------------*/ 219 220/* Number of fast-cache updates and flushes done. */ 221ULong n_fast_flushes = 0; 222ULong n_fast_updates = 0; 223 224/* Number of full lookups done. */ 225ULong n_full_lookups = 0; 226ULong n_lookup_probes = 0; 227 228/* Number/osize/tsize of translations entered. */ 229ULong n_in_count = 0; 230ULong n_in_osize = 0; 231ULong n_in_tsize = 0; 232 233/* Number/osize of translations discarded due to lack of space. */ 234ULong n_dump_count = 0; 235ULong n_dump_osize = 0; 236 237/* Number/osize of translations discarded due to requests to do so. */ 238ULong n_disc_count = 0; 239ULong n_disc_osize = 0; 240 241 242 243/*-------------------------------------------------------------*/ 244/*--- Add/delete/find translations ---*/ 245/*-------------------------------------------------------------*/ 246 247static UInt vge_osize ( VexGuestExtents* vge ) 248{ 249 UInt i, n = 0; 250 for (i = 0; i < vge->n_used; i++) 251 n += (UInt)vge->len[i]; 252 return n; 253} 254 255static Bool isValidSector ( Int sector ) 256{ 257 if (sector < 0 || sector >= N_SECTORS) 258 return False; 259 return True; 260} 261 262static inline UInt HASH_TT ( Addr64 key ) 263{ 264 UInt kHi = (UInt)(key >> 32); 265 UInt kLo = (UInt)key; 266 return (kHi ^ kLo) % N_TTES_PER_SECTOR; 267} 268 269static void setFastCacheEntry ( Addr64 key, ULong* tce, UInt* count ) 270{ 271 UInt cno = ((UInt)key) & VG_TT_FAST_MASK; 272 VG_(tt_fast)[cno] = tce; 273 VG_(tt_fastN)[cno] = count; 274 n_fast_updates++; 275} 276 277static void invalidateFastCache ( void ) 278{ 279 UInt j; 280 for (j = 0; j < VG_TT_FAST_SIZE; j++) { 281 VG_(tt_fast)[j] = &bogus_tc_entry; 282 VG_(tt_fastN)[j] = NULL; 283 } 284 n_fast_flushes++; 285} 286 287static void initialiseSector ( Int sno ) 288{ 289 Int i; 290 vg_assert(isValidSector(sno)); 291 292 if (sectors[sno].tc == NULL) { 293 /* Sector has never been used before. Need to allocate tt and 294 tc. */ 295 vg_assert(sectors[sno].tt == NULL); 296 vg_assert(sectors[sno].tc_next == NULL); 297 vg_assert(sectors[sno].tt_n_inuse == 0); 298 sectors[sno].tc 299 = VG_(get_memory_from_mmap) 300 ( 8 * tc_sector_szQ, "sectors[sno].tc" ); 301 sectors[sno].tt 302 = VG_(get_memory_from_mmap) 303 ( N_TTES_PER_SECTOR * sizeof(TTEntry), "sectors[sno].tt" ); 304 if (VG_(clo_verbosity) > 2) 305 VG_(message)(Vg_DebugMsg, "TT/TC: initialise sector %d", sno); 306 } else { 307 /* Sector has been used before. */ 308 vg_assert(sectors[sno].tt != NULL); 309 vg_assert(sectors[sno].tc_next != NULL); 310 n_dump_count += sectors[sno].tt_n_inuse; 311 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 312 if (sectors[sno].tt[i].status == InUse) { 313 n_dump_osize += vge_osize(§ors[sno].tt[i].vge); 314 } 315 } 316 if (VG_(clo_verbosity) > 2) 317 VG_(message)(Vg_DebugMsg, "TT/TC: recycle sector %d", sno); 318 } 319 320 sectors[sno].tc_next = sectors[sno].tc; 321 sectors[sno].tt_n_inuse = 0; 322 for (i = 0; i < N_TTES_PER_SECTOR; i++) 323 sectors[sno].tt[i].status = Empty; 324 325 invalidateFastCache(); 326} 327 328static void invalidate_icache ( void *ptr, Int nbytes ) 329{ 330# if defined(VGA_ppc32) 331 Addr startaddr = (Addr) ptr; 332 Addr endaddr = startaddr + nbytes; 333 Addr cls = VG_(cache_line_size_ppc32); 334 Addr addr; 335 336 /* Surely no real cache would have a different line size? */ 337 vg_assert(cls == 16 || cls == 32 || cls == 64); 338 339 startaddr &= ~(cls - 1); 340 for (addr = startaddr; addr < endaddr; addr += cls) 341 asm volatile("dcbst 0,%0" : : "r" (addr)); 342 asm volatile("sync"); 343 for (addr = startaddr; addr < endaddr; addr += cls) 344 asm volatile("icbi 0,%0" : : "r" (addr)); 345 asm volatile("sync; isync"); 346 347# elif defined(VGA_x86) 348 /* no need to do anything, hardware provides coherence */ 349 350# elif defined(VGA_amd64) 351 /* no need to do anything, hardware provides coherence */ 352 353# else 354# error "Unknown ARCH" 355# endif 356} 357 358 359/* Add a translation of vge to TT/TC. The translation is temporarily 360 in code[0 .. code_len-1]. 361 362 pre: youngest_sector points to a valid (although possibly full) 363 sector. 364*/ 365void VG_(add_to_transtab)( VexGuestExtents* vge, 366 Addr64 entry, 367 AddrH code, 368 UInt code_len ) 369{ 370 Int tcAvailQ, reqdQ, y, i; 371 ULong *tce, *tce2; 372 UChar* srcP; 373 UChar* dstP; 374 375 vg_assert(init_done); 376 vg_assert(vge->n_used >= 1 && vge->n_used <= 3); 377 vg_assert(code_len > 0 && code_len < 20000); 378 379 if (0) 380 VG_(printf)("add_to_transtab(entry = 0x%llx, len = %d)\n", 381 entry, code_len); 382 383 n_in_count++; 384 n_in_tsize += code_len; 385 n_in_osize += vge_osize(vge); 386 387 y = youngest_sector; 388 vg_assert(isValidSector(y)); 389 390 if (sectors[y].tc == NULL) 391 initialiseSector(y); 392 393 /* Try putting the translation in this sector. */ 394 reqdQ = 1 + ((code_len + 7) >> 3); 395 396 /* Will it fit in tc? */ 397 tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 398 - ((ULong*)(sectors[y].tc_next)); 399 vg_assert(tcAvailQ >= 0); 400 vg_assert(tcAvailQ <= tc_sector_szQ); 401 402 if (tcAvailQ < reqdQ 403 || sectors[y].tt_n_inuse >= N_TTES_PER_SECTOR_USABLE) { 404 /* No. So move on to the next sector. Either it's never been 405 used before, in which case it will get its tt/tc allocated 406 now, or it has been used before, in which case it is set to be 407 empty, hence throwing out the oldest sector. */ 408 youngest_sector++; 409 if (youngest_sector >= N_SECTORS) 410 youngest_sector = 0; 411 y = youngest_sector; 412 initialiseSector(y); 413 } 414 415 /* Be sure ... */ 416 tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 417 - ((ULong*)(sectors[y].tc_next)); 418 vg_assert(tcAvailQ >= 0); 419 vg_assert(tcAvailQ <= tc_sector_szQ); 420 vg_assert(tcAvailQ >= reqdQ); 421 vg_assert(sectors[y].tt_n_inuse < N_TTES_PER_SECTOR_USABLE); 422 vg_assert(sectors[y].tt_n_inuse >= 0); 423 424 /* Copy into tc. */ 425 tce = sectors[y].tc_next; 426 vg_assert(tce >= §ors[y].tc[0]); 427 vg_assert(tce <= §ors[y].tc[tc_sector_szQ]); 428 429 tce[0] = entry; 430 dstP = (UChar*)(&tce[1]); 431 srcP = (UChar*)code; 432 for (i = 0; i < code_len; i++) 433 dstP[i] = srcP[i]; 434 sectors[y].tc_next += reqdQ; 435 sectors[y].tt_n_inuse++; 436 437 invalidate_icache( dstP, code_len ); 438 439 /* more paranoia */ 440 tce2 = sectors[y].tc_next; 441 vg_assert(tce2 >= §ors[y].tc[0]); 442 vg_assert(tce2 <= §ors[y].tc[tc_sector_szQ]); 443 444 /* Find an empty tt slot, and use it. There must be such a slot 445 since tt is never allowed to get completely full. */ 446 i = HASH_TT(entry); 447 vg_assert(i >= 0 && i < N_TTES_PER_SECTOR); 448 while (True) { 449 if (sectors[y].tt[i].status == Empty 450 || sectors[y].tt[i].status == Deleted) 451 break; 452 i++; 453 if (i >= N_TTES_PER_SECTOR) 454 i = 0; 455 } 456 457 sectors[y].tt[i].status = InUse; 458 sectors[y].tt[i].tce = tce; 459 sectors[y].tt[i].count = 0; 460 sectors[y].tt[i].weight = 1; 461 sectors[y].tt[i].vge = *vge; 462 sectors[y].tt[i].entry = entry; 463 464 setFastCacheEntry( entry, tce, §ors[y].tt[i].count ); 465} 466 467 468/* Search for the translation of the given guest address. If 469 requested, a successful search can also cause the fast-caches to be 470 updated. 471*/ 472Bool VG_(search_transtab) ( /*OUT*/AddrH* result, 473 Addr64 guest_addr, 474 Bool upd_cache ) 475{ 476 Int i, j, k, kstart, sno; 477 478 vg_assert(init_done); 479 /* Find the initial probe point just once. It will be the same in 480 all sectors and avoids multiple expensive % operations. */ 481 n_full_lookups++; 482 k = -1; 483 kstart = HASH_TT(guest_addr); 484 vg_assert(kstart >= 0 && kstart < N_TTES_PER_SECTOR); 485 486 /* Search in all the sectors. Although the order should not matter, 487 it might be most efficient to search in the order youngest to 488 oldest. */ 489 sno = youngest_sector; 490 for (i = 0; i < N_SECTORS; i++) { 491 492 if (sectors[sno].tc == NULL) 493 goto notfound; /* sector not in use. */ 494 495 k = kstart; 496 for (j = 0; j < N_TTES_PER_SECTOR; j++) { 497 n_lookup_probes++; 498 if (sectors[sno].tt[k].status == InUse 499 && sectors[sno].tt[k].entry == guest_addr) { 500 /* found it */ 501 if (upd_cache) 502 setFastCacheEntry( 503 guest_addr, sectors[sno].tt[k].tce, 504 §ors[sno].tt[k].count ); 505 if (result) 506 *result = sizeof(Addr64) + (AddrH)sectors[sno].tt[k].tce; 507 return True; 508 } 509 if (sectors[sno].tt[k].status == Empty) 510 break; /* not found in this sector */ 511 k++; 512 if (k == N_TTES_PER_SECTOR) 513 k = 0; 514 } 515 516 /* If we fall off the end, all entries are InUse and not 517 matching, or Deleted. In any case we did not find it in this 518 sector. */ 519 520 notfound: 521 /* move to the next oldest sector */ 522 sno = sno==0 ? (N_SECTORS-1) : (sno-1); 523 } 524 525 /* Not found in any sector. */ 526 return False; 527} 528 529 530/* Delete all translations which intersect with any part of the 531 specified guest address range. Note, this is SLOW. 532*/ 533 534static inline 535Bool overlap1 ( Addr64 s1, UInt r1, Addr64 s2, UInt r2 ) 536{ 537 Addr64 e1 = s1 + (ULong)r1 - 1ULL; 538 Addr64 e2 = s2 + (ULong)r1 - 1ULL; 539 if (e1 < s2 || e2 < s1) 540 return False; 541 return True; 542} 543 544static inline 545Bool overlaps ( Addr64 start, UInt range, VexGuestExtents* vge ) 546{ 547 if (overlap1(start, range, vge->base[0], (UInt)vge->len[0])) 548 return True; 549 if (vge->n_used < 2) 550 return False; 551 if (overlap1(start, range, vge->base[1], (UInt)vge->len[1])) 552 return True; 553 if (vge->n_used < 3) 554 return False; 555 if (overlap1(start, range, vge->base[2], (UInt)vge->len[2])) 556 return True; 557 return False; 558} 559 560 561void VG_(discard_translations) ( Addr64 guest_start, UInt range ) 562{ 563 Int sno, i; 564 Bool anyDeleted = False; 565 566 vg_assert(init_done); 567 568 for (sno = 0; sno < N_SECTORS; sno++) { 569 if (sectors[sno].tc == NULL) 570 continue; 571 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 572 if (sectors[sno].tt[i].status == InUse 573 && overlaps( guest_start, range, §ors[sno].tt[i].vge )) { 574 sectors[sno].tt[i].status = Deleted; 575 sectors[sno].tt_n_inuse--; 576 anyDeleted = True; 577 n_disc_count++; 578 n_disc_osize += vge_osize(§ors[sno].tt[i].vge); 579 } 580 } 581 } 582 583 if (anyDeleted) 584 invalidateFastCache(); 585} 586 587 588/*------------------------------------------------------------*/ 589/*--- Initialisation. ---*/ 590/*------------------------------------------------------------*/ 591 592void VG_(init_tt_tc) ( void ) 593{ 594 Int i, avg_codeszQ; 595 596 vg_assert(!init_done); 597 init_done = True; 598 599 /* Otherwise lots of things go wrong... */ 600 vg_assert(sizeof(ULong) == 8); 601 vg_assert(sizeof(Addr64) == 8); 602 603 if (VG_(clo_verbosity) > 2) 604 VG_(message)(Vg_DebugMsg, 605 "TT/TC: VG_(init_tt_tc) " 606 "(startup of code management)"); 607 608 /* Figure out how big each tc area should be. */ 609 avg_codeszQ = (VG_(details).avg_translation_sizeB + 7) / 8; 610 tc_sector_szQ = N_TTES_PER_SECTOR_USABLE * (1 + avg_codeszQ); 611 612 /* Ensure the calculated value is not way crazy. */ 613 vg_assert(tc_sector_szQ >= 2 * N_TTES_PER_SECTOR_USABLE); 614 vg_assert(tc_sector_szQ <= 50 * N_TTES_PER_SECTOR_USABLE); 615 616 /* Initialise the sectors */ 617 youngest_sector = 0; 618 for (i = 0; i < N_SECTORS; i++) { 619 sectors[i].tc = NULL; 620 sectors[i].tt = NULL; 621 sectors[i].tc_next = NULL; 622 sectors[i].tt_n_inuse = 0; 623 } 624 625 /* and the fast caches. */ 626 invalidateFastCache(); 627 628 if (VG_(clo_verbosity) > 2) { 629 VG_(message)(Vg_DebugMsg, 630 "TT/TC: cache: %d sectors of %d bytes each = %d total", 631 N_SECTORS, 8 * tc_sector_szQ, 632 N_SECTORS * 8 * tc_sector_szQ ); 633 VG_(message)(Vg_DebugMsg, 634 "TT/TC: table: %d total entries, max occupancy %d (%d%%)", 635 N_SECTORS * N_TTES_PER_SECTOR, 636 N_SECTORS * N_TTES_PER_SECTOR_USABLE, 637 SECTOR_TT_LIMIT_PERCENT ); 638 } 639} 640 641 642/*------------------------------------------------------------*/ 643/*--- Printing out statistics. ---*/ 644/*------------------------------------------------------------*/ 645 646static ULong safe_idiv( ULong a, ULong b ) 647{ 648 return (b == 0 ? 0 : a / b); 649} 650 651UInt VG_(get_bbs_translated) ( void ) 652{ 653 return n_in_count; 654} 655 656void VG_(print_tt_tc_stats) ( void ) 657{ 658 VG_(message)(Vg_DebugMsg, 659 " tt/tc: %llu tt lookups requiring %llu probes", 660 n_full_lookups, n_lookup_probes ); 661 VG_(message)(Vg_DebugMsg, 662 " tt/tc: %llu fast-cache updates, %llu flushes", 663 n_fast_updates, n_fast_flushes ); 664 665 VG_(message)(Vg_DebugMsg, 666 "translate: new %lld (%lld -> %lld; ratio %lld:10)", 667 n_in_count, n_in_osize, n_in_tsize, 668 safe_idiv(10*n_in_tsize, n_in_osize)); 669 VG_(message)(Vg_DebugMsg, 670 "translate: dumped %lld (%lld -> ?" "?)", 671 n_dump_count, n_dump_osize ); 672 VG_(message)(Vg_DebugMsg, 673 "translate: discarded %lld (%lld -> ?" "?)", 674 n_disc_count, n_disc_osize ); 675} 676 677/*------------------------------------------------------------*/ 678/*--- Printing out of profiling results. ---*/ 679/*------------------------------------------------------------*/ 680 681static ULong score ( TTEntry* tte ) 682{ 683 return ((ULong)tte->weight) * ((ULong)tte->count); 684} 685 686ULong VG_(get_BB_profile) ( BBProfEntry tops[], UInt n_tops ) 687{ 688 Int sno, i, r, s; 689 ULong score_total; 690 691 /* First, compute the total weighted count, and find the top N 692 ttes. tops contains pointers to the most-used n_tops blocks, in 693 descending order (viz, tops[0] is the highest scorer). */ 694 for (i = 0; i < n_tops; i++) { 695 tops[i].addr = 0; 696 tops[i].score = 0; 697 } 698 699 score_total = 0; 700 701 for (sno = 0; sno < N_SECTORS; sno++) { 702 if (sectors[sno].tc == NULL) 703 continue; 704 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 705 if (sectors[sno].tt[i].status != InUse) 706 continue; 707 score_total += score(§ors[sno].tt[i]); 708 /* Find the rank for sectors[sno].tt[i]. */ 709 r = n_tops-1; 710 while (True) { 711 if (r == -1) 712 break; 713 if (tops[r].addr == 0) { 714 r--; 715 continue; 716 } 717 if ( score(§ors[sno].tt[i]) > tops[r].score ) { 718 r--; 719 continue; 720 } 721 break; 722 } 723 r++; 724 vg_assert(r >= 0 && r <= n_tops); 725 /* This bb should be placed at r, and bbs above it shifted 726 upwards one slot. */ 727 if (r < n_tops) { 728 for (s = n_tops-1; s > r; s--) 729 tops[s] = tops[s-1]; 730 tops[r].addr = sectors[sno].tt[i].entry; 731 tops[r].score = score( §ors[sno].tt[i] ); 732 } 733 } 734 } 735 736 return score_total; 737} 738 739/*--------------------------------------------------------------------*/ 740/*--- end ---*/ 741/*--------------------------------------------------------------------*/ 742