m_transtab.c revision 4ba057cce1d81a949f5a899b5abb99e90a731bcc
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_debuglog.h" 34#include "pub_core_machine.h" // ppc32: VG_(cache_line_size_ppc32) 35#include "pub_core_libcbase.h" 36#include "pub_core_libcassert.h" 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#include "pub_core_aspacemgr.h" 42#include "pub_core_mallocfree.h" // VG_(out_of_memory_NORETURN) 43 44/* #define DEBUG_TRANSTAB */ 45 46 47/*-------------------------------------------------------------*/ 48/*--- Management of the FIFO-based translation table+cache. ---*/ 49/*-------------------------------------------------------------*/ 50 51/*------------------ CONSTANTS ------------------*/ 52 53/* Number of sectors the TC is divided into. If you need a larger 54 overall translation cache, increase this value. */ 55#define N_SECTORS 8 56 57/* Number of TC entries in each sector. This needs to be a prime 58 number to work properly, it must be <= 65535 (so that a TT index 59 fits in a UShort, leaving room for 0xFFFF(EC2TTE_DELETED) to denote 60 'deleted') and it is strongly recommended not to change this. 61 65521 is the largest prime <= 65535. */ 62#define N_TTES_PER_SECTOR /*30011*/ /*40009*/ 65521 63 64/* Because each sector contains a hash table of TTEntries, we need to 65 specify the maximum allowable loading, after which the sector is 66 deemed full. */ 67#define SECTOR_TT_LIMIT_PERCENT 80 68 69/* The sector is deemed full when this many entries are in it. */ 70#define N_TTES_PER_SECTOR_USABLE \ 71 ((N_TTES_PER_SECTOR * SECTOR_TT_LIMIT_PERCENT) / 100) 72 73/* Equivalence classes for fast address range deletion. There are 1 + 74 2^ECLASS_WIDTH bins. The highest one, ECLASS_MISC, describes an 75 address range which does not fall cleanly within any specific bin. 76 Note that ECLASS_SHIFT + ECLASS_WIDTH must be < 32. */ 77#define ECLASS_SHIFT 11 78#define ECLASS_WIDTH 8 79#define ECLASS_MISC (1 << ECLASS_WIDTH) 80#define ECLASS_N (1 + ECLASS_MISC) 81 82#define EC2TTE_DELETED 0xFFFF /* 16-bit special value */ 83 84 85/*------------------ TYPES ------------------*/ 86 87/* A translation-cache entry is two parts: 88 - The guest address of the first (entry) bb in the translation, 89 as a 64-bit word. 90 - One or more 64-bit words containing the code. 91 It is supposed to be 64-bit aligned. 92*/ 93/* 94typedef 95 struct { 96 Addr64 orig_addr; 97 ULong code[0]; 98 } 99 TCEntry; 100*/ 101 102/* A translation-table entry. This indicates precisely which areas of 103 guest code are included in the translation, and contains all other 104 auxiliary info too. */ 105typedef 106 struct { 107 /* Profiling only: the count and weight (arbitrary meaning) for 108 this translation. Weight is a property of the translation 109 itself and computed once when the translation is created. 110 Count is an entry count for the translation and is 111 incremented by 1 every time the translation is used, if we 112 are profiling. */ 113 UInt count; 114 UShort weight; 115 116 /* Status of the slot. Note, we need to be able to do lazy 117 deletion, hence the Deleted state. */ 118 enum { InUse, Deleted, Empty } status; 119 120 /* Pointer to the corresponding TCEntry (must be in the same 121 sector!) */ 122 ULong* tce; 123 124 /* This is the original guest address that purportedly is the 125 entry point of the translation. You might think that .entry 126 should be the same as .vge->base[0], and most of the time it 127 is. However, when doing redirections, that is not the case. 128 .vge must always correctly describe the guest code sections 129 from which this translation was made. However, .entry may or 130 may not be a lie, depending on whether or not we're doing 131 redirection. */ 132 Addr64 entry; 133 134 /* This structure describes precisely what ranges of guest code 135 the translation covers, so we can decide whether or not to 136 delete it when translations of a given address range are 137 invalidated. */ 138 VexGuestExtents vge; 139 140 /* Address range summary info: these are pointers back to 141 eclass[] entries in the containing Sector. Those entries in 142 turn point back here -- the two structures are mutually 143 redundant but both necessary to make fast deletions work. 144 The eclass info is similar to, and derived from, this entry's 145 'vge' field, but it is not the same */ 146 UShort n_tte2ec; // # tte2ec pointers (1 to 3) 147 UShort tte2ec_ec[3]; // for each, the eclass # 148 UInt tte2ec_ix[3]; // and the index within the eclass. 149 // for i in 0 .. n_tte2ec-1 150 // sec->ec2tte[ tte2ec_ec[i] ][ tte2ec_ix[i] ] 151 // should be the index 152 // of this TTEntry in the containing Sector's tt array. 153 } 154 TTEntry; 155 156 157/* Finally, a sector itself. Each sector contains an array of 158 TCEntries, which hold code, and an array of TTEntries, containing 159 all required administrative info. Profiling is supported using the 160 TTEntry .count and .weight fields, if required. Each sector is 161 independent in that no cross-sector references are allowed. 162 163 If the sector is not in use, all three pointers are NULL and 164 tt_n_inuse is zero. 165*/ 166typedef 167 struct { 168 /* The TCEntry area. Size of this depends on the average 169 translation size. We try and size it so it becomes full 170 precisely when this sector's translation table (tt) reaches 171 its load limit (SECTOR_TT_LIMIT_PERCENT). */ 172 ULong* tc; 173 174 /* The TTEntry array. This is a fixed size, always containing 175 exactly N_TTES_PER_SECTOR entries. */ 176 TTEntry* tt; 177 178 /* This points to the current allocation point in tc. */ 179 ULong* tc_next; 180 181 /* The count of tt entries with state InUse. */ 182 Int tt_n_inuse; 183 184 /* Expandable arrays of tt indices for each of the ECLASS_N 185 address range equivalence classes. These hold indices into 186 the containing sector's tt array, which in turn should point 187 back here. */ 188 Int ec2tte_size[ECLASS_N]; 189 Int ec2tte_used[ECLASS_N]; 190 UShort* ec2tte[ECLASS_N]; 191 } 192 Sector; 193 194 195/*------------------ DECLS ------------------*/ 196 197/* The root data structure is an array of sectors. The index of the 198 youngest sector is recorded, and new translations are put into that 199 sector. When it fills up, we move along to the next sector and 200 start to fill that up, wrapping around at the end of the array. 201 That way, once all N_TC_SECTORS have been bought into use for the 202 first time, and are full, we then re-use the oldest sector, 203 endlessly. 204 205 When running, youngest sector should be between >= 0 and < 206 N_TC_SECTORS. The initial -1 value indicates the TT/TC system is 207 not yet initialised. 208*/ 209static Sector sectors[N_SECTORS]; 210static Int youngest_sector = -1; 211 212/* The number of ULongs in each TCEntry area. This is computed once 213 at startup and does not change. */ 214static Int tc_sector_szQ; 215 216 217/* Fast helper for the TC. A direct-mapped cache which holds a 218 pointer to a TC entry which may or may not be the correct one, but 219 which we hope usually is. This array is referred to directly from 220 <arch>/dispatch.S. 221 222 Entries in tt_fast may point to any valid TC entry, regardless of 223 which sector it's in. Consequently we must be very careful to 224 invalidate this cache when TC entries are changed or disappear. 225 226 A special TCEntry -- bogus_tc_entry -- must be pointed at to cause 227 that cache entry to miss. This relies on the assumption that no 228 guest code actually has an address of 0x1. 229*/ 230/*global*/ ULong* VG_(tt_fast)[VG_TT_FAST_SIZE]; 231 232static ULong bogus_tc_entry = (Addr64)1; 233 234 235/* For profiling, we have a parallel array of pointers to .count 236 fields in TT entries. Again, these pointers must be invalidated 237 when translations disappear. A NULL pointer suffices to indicate 238 an unused slot. 239 240 tt_fast and tt_fastN change together: if tt_fast[i] points to 241 bogus_tc_entry then the corresponding tt_fastN[i] must be null. If 242 tt_fast[i] points to some TC entry somewhere, then tt_fastN[i] 243 *must* point to the .count field of the corresponding TT entry. 244 245 tt_fast and tt_fastN are referred to from assembly code 246 (dispatch.S). 247*/ 248/*global*/ UInt* VG_(tt_fastN)[VG_TT_FAST_SIZE]; 249 250 251/* Make sure we're not used before initialisation. */ 252static Bool init_done = False; 253 254 255/*------------------ STATS DECLS ------------------*/ 256 257/* Number of fast-cache updates and flushes done. */ 258ULong n_fast_flushes = 0; 259ULong n_fast_updates = 0; 260 261/* Number of full lookups done. */ 262ULong n_full_lookups = 0; 263ULong n_lookup_probes = 0; 264 265/* Number/osize/tsize of translations entered; also the number of 266 those for which self-checking was requested. */ 267ULong n_in_count = 0; 268ULong n_in_osize = 0; 269ULong n_in_tsize = 0; 270ULong n_in_sc_count = 0; 271 272/* Number/osize of translations discarded due to lack of space. */ 273ULong n_dump_count = 0; 274ULong n_dump_osize = 0; 275 276/* Number/osize of translations discarded due to requests to do so. */ 277ULong n_disc_count = 0; 278ULong n_disc_osize = 0; 279 280 281/*-------------------------------------------------------------*/ 282/*--- Address-range equivalence class stuff ---*/ 283/*-------------------------------------------------------------*/ 284 285/* Return equivalence class number for a range. */ 286 287static Int range_to_eclass ( Addr64 start, UInt len ) 288{ 289 UInt mask = (1 << ECLASS_WIDTH) - 1; 290 UInt lo = (UInt)start; 291 UInt hi = lo + len - 1; 292 UInt loBits = (lo >> ECLASS_SHIFT) & mask; 293 UInt hiBits = (hi >> ECLASS_SHIFT) & mask; 294 if (loBits == hiBits) { 295 vg_assert(loBits < ECLASS_N-1); 296 return loBits; 297 } else { 298 return ECLASS_MISC; 299 } 300} 301 302 303/* Calculates the equivalence class numbers for any VexGuestExtent. 304 These are written in *eclasses, which must be big enough to hold 3 305 Ints. The number written, between 1 and 3, is returned. The 306 eclasses are presented in order, and any duplicates are removed. 307*/ 308 309static 310Int vexGuestExtents_to_eclasses ( /*OUT*/Int* eclasses, 311 VexGuestExtents* vge ) 312{ 313# define SWAP(_lv1,_lv2) \ 314 do { Int t = _lv1; _lv1 = _lv2; _lv2 = t; } while (0) 315 316 Int i, j, n_ec, r; 317 318 vg_assert(vge->n_used >= 1 && vge->n_used <= 3); 319 320 n_ec = 0; 321 for (i = 0; i < vge->n_used; i++) { 322 r = range_to_eclass( vge->base[i], (UInt)vge->len[i] ); 323 if (r == ECLASS_MISC) 324 goto bad; 325 /* only add if we haven't already seen it */ 326 for (j = 0; j < n_ec; j++) 327 if (eclasses[j] == r) 328 break; 329 if (j == n_ec) 330 eclasses[n_ec++] = r; 331 } 332 333 if (n_ec == 1) 334 return 1; 335 336 if (n_ec == 2) { 337 /* sort */ 338 if (eclasses[0] > eclasses[1]) 339 SWAP(eclasses[0], eclasses[1]); 340 return 2; 341 } 342 343 if (n_ec == 3) { 344 /* sort */ 345 if (eclasses[0] > eclasses[2]) 346 SWAP(eclasses[0], eclasses[2]); 347 if (eclasses[0] > eclasses[1]) 348 SWAP(eclasses[0], eclasses[1]); 349 if (eclasses[1] > eclasses[2]) 350 SWAP(eclasses[1], eclasses[2]); 351 return 3; 352 } 353 354 /* NOTREACHED */ 355 vg_assert(0); 356 357 bad: 358 eclasses[0] = ECLASS_MISC; 359 return 1; 360 361# undef SWAP 362} 363 364 365/* Add tteno to the set of entries listed for equivalence class ec in 366 this sector. Returns used location in eclass array. */ 367 368static 369UInt addEClassNo ( /*MOD*/Sector* sec, Int ec, UShort tteno ) 370{ 371 Int old_sz, new_sz, i, r; 372 UShort *old_ar, *new_ar; 373 374 vg_assert(ec >= 0 && ec < ECLASS_N); 375 vg_assert(tteno < N_TTES_PER_SECTOR); 376 377 if (0) VG_(printf)("ec %d gets %d\n", ec, (Int)tteno); 378 379 if (sec->ec2tte_used[ec] >= sec->ec2tte_size[ec]) { 380 381 vg_assert(sec->ec2tte_used[ec] == sec->ec2tte_size[ec]); 382 383 old_sz = sec->ec2tte_size[ec]; 384 old_ar = sec->ec2tte[ec]; 385 new_sz = old_sz==0 ? 8 : old_sz<64 ? 2*old_sz : (3*old_sz)/2; 386 new_ar = VG_(arena_malloc)(VG_AR_TTAUX, new_sz * sizeof(UShort)); 387 for (i = 0; i < old_sz; i++) 388 new_ar[i] = old_ar[i]; 389 if (old_ar) 390 VG_(arena_free)(VG_AR_TTAUX, old_ar); 391 sec->ec2tte_size[ec] = new_sz; 392 sec->ec2tte[ec] = new_ar; 393 394 if (0) VG_(printf)("expand ec %d to %d\n", ec, new_sz); 395 } 396 397 /* Common case */ 398 r = sec->ec2tte_used[ec]++; 399 vg_assert(r >= 0 && r < sec->ec2tte_size[ec]); 400 sec->ec2tte[ec][r] = tteno; 401 return (UInt)r; 402} 403 404 405/* 'vge' is being added to 'sec' at TT entry 'tteno'. Add appropriate 406 eclass entries to 'sec'. */ 407 408static 409void upd_eclasses_after_add ( /*MOD*/Sector* sec, Int tteno ) 410{ 411 Int i, r, eclasses[3]; 412 TTEntry* tte; 413 vg_assert(tteno >= 0 && tteno < N_TTES_PER_SECTOR); 414 415 tte = &sec->tt[tteno]; 416 r = vexGuestExtents_to_eclasses( eclasses, &tte->vge ); 417 418 vg_assert(r >= 1 && r <= 3); 419 tte->n_tte2ec = r; 420 421 for (i = 0; i < r; i++) { 422 tte->tte2ec_ec[i] = eclasses[i]; 423 tte->tte2ec_ix[i] = addEClassNo( sec, eclasses[i], (UShort)tteno ); 424 } 425} 426 427 428/* Check the eclass info in 'sec' to ensure it is consistent. Returns 429 True if OK, False if something's not right. Expensive. */ 430 431static Bool sanity_check_eclasses_in_sector ( Sector* sec ) 432{ 433# define BAD(_str) do { whassup = (_str); goto bad; } while (0) 434 435 HChar* whassup = NULL; 436 Int i, j, k, n, ec_num, ec_idx; 437 TTEntry* tte; 438 UShort tteno; 439 ULong* tce; 440 441 /* Basic checks on this sector */ 442 if (sec->tt_n_inuse < 0 || sec->tt_n_inuse > N_TTES_PER_SECTOR_USABLE) 443 BAD("invalid sec->tt_n_inuse"); 444 tce = sec->tc_next; 445 if (tce < &sec->tc[0] || tce > &sec->tc[tc_sector_szQ]) 446 BAD("sec->tc_next points outside tc"); 447 448 /* For each eclass ... */ 449 for (i = 0; i < ECLASS_N; i++) { 450 if (sec->ec2tte_size[i] == 0 && sec->ec2tte[i] != NULL) 451 BAD("ec2tte_size/ec2tte mismatch(1)"); 452 if (sec->ec2tte_size[i] != 0 && sec->ec2tte[i] == NULL) 453 BAD("ec2tte_size/ec2tte mismatch(2)"); 454 if (sec->ec2tte_used[i] < 0 455 || sec->ec2tte_used[i] > sec->ec2tte_size[i]) 456 BAD("implausible ec2tte_used"); 457 if (sec->ec2tte_used[i] == 0) 458 continue; 459 460 /* For each tt reference in each eclass .. ensure the reference 461 is to a valid tt entry, and that the entry's address ranges 462 really include this eclass. */ 463 464 for (j = 0; j < sec->ec2tte_used[i]; j++) { 465 tteno = sec->ec2tte[i][j]; 466 if (tteno == EC2TTE_DELETED) 467 continue; 468 if (tteno >= N_TTES_PER_SECTOR) 469 BAD("implausible tteno"); 470 tte = &sec->tt[tteno]; 471 if (tte->status != InUse) 472 BAD("tteno points to non-inuse tte"); 473 if (tte->n_tte2ec < 1 || tte->n_tte2ec > 3) 474 BAD("tte->n_tte2ec out of range"); 475 /* Exactly least one of tte->eclasses[0 .. tte->n_eclasses-1] 476 must equal i. Inspect tte's eclass info. */ 477 n = 0; 478 for (k = 0; k < tte->n_tte2ec; k++) { 479 if (k < tte->n_tte2ec-1 480 && tte->tte2ec_ec[k] >= tte->tte2ec_ec[k+1]) 481 BAD("tte->tte2ec_ec[..] out of order"); 482 ec_num = tte->tte2ec_ec[k]; 483 if (ec_num < 0 || ec_num >= ECLASS_N) 484 BAD("tte->tte2ec_ec[..] out of range"); 485 if (ec_num != i) 486 continue; 487 ec_idx = tte->tte2ec_ix[k]; 488 if (ec_idx < 0 || ec_idx >= sec->ec2tte_used[i]) 489 BAD("tte->tte2ec_ix[..] out of range"); 490 if (ec_idx == j) 491 n++; 492 } 493 if (n != 1) 494 BAD("tteno does not point back at eclass"); 495 } 496 } 497 498 /* That establishes that for each forward pointer from TTEntrys 499 there is a corresponding backward pointer from the eclass[] 500 arrays. However, it doesn't rule out the possibility of other, 501 bogus pointers in the eclass[] arrays. So do those similarly: 502 scan through them and check the TTEntryies they point at point 503 back. */ 504 505 for (i = 0; i < N_TTES_PER_SECTOR_USABLE; i++) { 506 507 tte = &sec->tt[i]; 508 if (tte->status == Empty || tte->status == Deleted) { 509 if (tte->n_tte2ec != 0) 510 BAD("tte->n_eclasses nonzero for unused tte"); 511 continue; 512 } 513 514 vg_assert(tte->status == InUse); 515 516 if (tte->n_tte2ec < 1 || tte->n_tte2ec > 3) 517 BAD("tte->n_eclasses out of range(2)"); 518 519 for (j = 0; j < tte->n_tte2ec; j++) { 520 ec_num = tte->tte2ec_ec[j]; 521 if (ec_num < 0 || ec_num >= ECLASS_N) 522 BAD("tte->eclass[..] out of range"); 523 ec_idx = tte->tte2ec_ix[j]; 524 if (ec_idx < 0 || ec_idx >= sec->ec2tte_used[ec_num]) 525 BAD("tte->ec_idx[..] out of range(2)"); 526 if (sec->ec2tte[ec_num][ec_idx] != i) 527 BAD("ec2tte does not point back to tte"); 528 } 529 } 530 531 return True; 532 533 bad: 534 if (whassup) 535 VG_(debugLog)(0, "transtab", "eclass sanity fail: %s\n", whassup); 536 537# if 0 538 VG_(printf)("eclass = %d\n", i); 539 VG_(printf)("tteno = %d\n", (Int)tteno); 540 switch (tte->status) { 541 case InUse: VG_(printf)("InUse\n"); break; 542 case Deleted: VG_(printf)("Deleted\n"); break; 543 case Empty: VG_(printf)("Empty\n"); break; 544 } 545 if (tte->status != Empty) { 546 for (k = 0; k < tte->vge.n_used; k++) 547 VG_(printf)("0x%llx %d\n", tte->vge.base[k], 548 (Int)tte->vge.len[k]); 549 } 550# endif 551 552 return False; 553 554# undef BAD 555} 556 557 558/* Sanity check absolutely everything. True == check passed. */ 559 560static Bool sanity_check_all_sectors ( void ) 561{ 562 Int sno; 563 Bool sane; 564 Sector* sec; 565 for (sno = 0; sno < N_SECTORS; sno++) { 566 sec = §ors[sno]; 567 if (sec->tc == NULL) 568 continue; 569 sane = sanity_check_eclasses_in_sector( sec ); 570 if (!sane) 571 return False; 572 } 573 return True; 574} 575 576 577/*-------------------------------------------------------------*/ 578/*--- Add/find translations ---*/ 579/*-------------------------------------------------------------*/ 580 581static UInt vge_osize ( VexGuestExtents* vge ) 582{ 583 UInt i, n = 0; 584 for (i = 0; i < vge->n_used; i++) 585 n += (UInt)vge->len[i]; 586 return n; 587} 588 589static Bool isValidSector ( Int sector ) 590{ 591 if (sector < 0 || sector >= N_SECTORS) 592 return False; 593 return True; 594} 595 596static inline UInt HASH_TT ( Addr64 key ) 597{ 598 UInt kHi = (UInt)(key >> 32); 599 UInt kLo = (UInt)key; 600 UInt k32 = kHi ^ kLo; 601 UInt ror = 7; 602 if (ror > 0) 603 k32 = (k32 >> ror) | (k32 << (32-ror)); 604 return k32 % N_TTES_PER_SECTOR; 605} 606 607static void setFastCacheEntry ( Addr64 key, ULong* tce, UInt* count ) 608{ 609 UInt cno = ((UInt)key) & VG_TT_FAST_MASK; 610 VG_(tt_fast)[cno] = tce; 611 VG_(tt_fastN)[cno] = count; 612 n_fast_updates++; 613} 614 615static void invalidateFastCache ( void ) 616{ 617 UInt j; 618 for (j = 0; j < VG_TT_FAST_SIZE; j++) { 619 VG_(tt_fast)[j] = &bogus_tc_entry; 620 VG_(tt_fastN)[j] = NULL; 621 } 622 n_fast_flushes++; 623} 624 625static void initialiseSector ( Int sno ) 626{ 627 Int i; 628 SysRes sres; 629 Sector* sec; 630 vg_assert(isValidSector(sno)); 631 632 sec = §ors[sno]; 633 634 if (sec->tc == NULL) { 635 636 /* Sector has never been used before. Need to allocate tt and 637 tc. */ 638 vg_assert(sec->tt == NULL); 639 vg_assert(sec->tc_next == NULL); 640 vg_assert(sec->tt_n_inuse == 0); 641 for (i = 0; i < ECLASS_N; i++) { 642 vg_assert(sec->ec2tte_size[i] == 0); 643 vg_assert(sec->ec2tte_used[i] == 0); 644 vg_assert(sec->ec2tte[i] == NULL); 645 } 646 647 VG_(debugLog)(1,"transtab", "allocate sector %d\n", sno); 648 649 sres = VG_(am_mmap_anon_float_valgrind)( 8 * tc_sector_szQ ); 650 if (sres.isError) { 651 VG_(out_of_memory_NORETURN)("initialiseSector(TC)", 652 8 * tc_sector_szQ ); 653 /*NOTREACHED*/ 654 } 655 sec->tc = (ULong*)sres.val; 656 657 sres = VG_(am_mmap_anon_float_valgrind) 658 ( N_TTES_PER_SECTOR * sizeof(TTEntry) ); 659 if (sres.isError) { 660 VG_(out_of_memory_NORETURN)("initialiseSector(TT)", 661 N_TTES_PER_SECTOR * sizeof(TTEntry) ); 662 /*NOTREACHED*/ 663 } 664 sec->tt = (TTEntry*)sres.val; 665 666 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 667 sec->tt[i].status = Empty; 668 sec->tt[i].n_tte2ec = 0; 669 } 670 671 if (VG_(clo_verbosity) > 2) 672 VG_(message)(Vg_DebugMsg, "TT/TC: initialise sector %d", sno); 673 674 } else { 675 676 /* Sector has been used before. Dump the old contents. */ 677 VG_(debugLog)(1,"transtab", "recycle sector %d\n", sno); 678 vg_assert(sec->tt != NULL); 679 vg_assert(sec->tc_next != NULL); 680 n_dump_count += sec->tt_n_inuse; 681 682 /* Visit each just-about-to-be-abandoned translation. */ 683 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 684 if (sec->tt[i].status == InUse) { 685 vg_assert(sec->tt[i].n_tte2ec >= 1); 686 vg_assert(sec->tt[i].n_tte2ec <= 3); 687 n_dump_osize += vge_osize(&sec->tt[i].vge); 688 /* Tell the tool too. */ 689 if (VG_(needs).basic_block_discards) { 690 VG_TDICT_CALL( tool_discard_basic_block_info, 691 sec->tt[i].entry, 692 sec->tt[i].vge ); 693 } 694 } else { 695 vg_assert(sec->tt[i].n_tte2ec == 0); 696 } 697 sec->tt[i].status = Empty; 698 sec->tt[i].n_tte2ec = 0; 699 } 700 701 /* Free up the eclass structures. */ 702 for (i = 0; i < ECLASS_N; i++) { 703 if (sec->ec2tte_size[i] == 0) { 704 vg_assert(sec->ec2tte_used[i] == 0); 705 vg_assert(sec->ec2tte[i] == NULL); 706 } else { 707 vg_assert(sec->ec2tte[i] != NULL); 708 VG_(arena_free)(VG_AR_TTAUX, sec->ec2tte[i]); 709 sec->ec2tte[i] = NULL; 710 sec->ec2tte_size[i] = 0; 711 sec->ec2tte_used[i] = 0; 712 } 713 } 714 715 if (VG_(clo_verbosity) > 2) 716 VG_(message)(Vg_DebugMsg, "TT/TC: recycle sector %d", sno); 717 } 718 719 sec->tc_next = sec->tc; 720 sec->tt_n_inuse = 0; 721 722 invalidateFastCache(); 723} 724 725static void invalidate_icache ( void *ptr, Int nbytes ) 726{ 727# if defined(VGA_ppc32) 728 Addr startaddr = (Addr) ptr; 729 Addr endaddr = startaddr + nbytes; 730 Addr cls = VG_(cache_line_size_ppc32); 731 Addr addr; 732 733 /* Stay sane .. */ 734 vg_assert(cls == 32 || cls == 128); 735 736 startaddr &= ~(cls - 1); 737 for (addr = startaddr; addr < endaddr; addr += cls) 738 asm volatile("dcbst 0,%0" : : "r" (addr)); 739 asm volatile("sync"); 740 for (addr = startaddr; addr < endaddr; addr += cls) 741 asm volatile("icbi 0,%0" : : "r" (addr)); 742 asm volatile("sync; isync"); 743 744# elif defined(VGA_x86) 745 /* no need to do anything, hardware provides coherence */ 746 747# elif defined(VGA_amd64) 748 /* no need to do anything, hardware provides coherence */ 749 750# else 751# error "Unknown ARCH" 752# endif 753} 754 755 756/* Add a translation of vge to TT/TC. The translation is temporarily 757 in code[0 .. code_len-1]. 758 759 pre: youngest_sector points to a valid (although possibly full) 760 sector. 761*/ 762void VG_(add_to_transtab)( VexGuestExtents* vge, 763 Addr64 entry, 764 AddrH code, 765 UInt code_len, 766 Bool is_self_checking ) 767{ 768 Int tcAvailQ, reqdQ, y, i; 769 ULong *tce, *tce2; 770 UChar* srcP; 771 UChar* dstP; 772 773 vg_assert(init_done); 774 vg_assert(vge->n_used >= 1 && vge->n_used <= 3); 775 vg_assert(code_len > 0 && code_len < 20000); 776 777 if (0) 778 VG_(printf)("add_to_transtab(entry = 0x%llx, len = %d)\n", 779 entry, code_len); 780 781 n_in_count++; 782 n_in_tsize += code_len; 783 n_in_osize += vge_osize(vge); 784 if (is_self_checking) 785 n_in_sc_count++; 786 787 y = youngest_sector; 788 vg_assert(isValidSector(y)); 789 790 if (sectors[y].tc == NULL) 791 initialiseSector(y); 792 793 /* Try putting the translation in this sector. */ 794 reqdQ = 1 + ((code_len + 7) >> 3); 795 796 /* Will it fit in tc? */ 797 tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 798 - ((ULong*)(sectors[y].tc_next)); 799 vg_assert(tcAvailQ >= 0); 800 vg_assert(tcAvailQ <= tc_sector_szQ); 801 802 if (tcAvailQ < reqdQ 803 || sectors[y].tt_n_inuse >= N_TTES_PER_SECTOR_USABLE) { 804 /* No. So move on to the next sector. Either it's never been 805 used before, in which case it will get its tt/tc allocated 806 now, or it has been used before, in which case it is set to be 807 empty, hence throwing out the oldest sector. */ 808 vg_assert(tc_sector_szQ > 0); 809 VG_(debugLog)(1,"transtab", 810 "declare sector %d full " 811 "(TT loading %2d%%, TC loading %2d%%)\n", 812 y, 813 (100 * sectors[y].tt_n_inuse) 814 / N_TTES_PER_SECTOR, 815 (100 * (tc_sector_szQ - tcAvailQ)) 816 / tc_sector_szQ); 817 youngest_sector++; 818 if (youngest_sector >= N_SECTORS) 819 youngest_sector = 0; 820 y = youngest_sector; 821 initialiseSector(y); 822 } 823 824 /* Be sure ... */ 825 tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 826 - ((ULong*)(sectors[y].tc_next)); 827 vg_assert(tcAvailQ >= 0); 828 vg_assert(tcAvailQ <= tc_sector_szQ); 829 vg_assert(tcAvailQ >= reqdQ); 830 vg_assert(sectors[y].tt_n_inuse < N_TTES_PER_SECTOR_USABLE); 831 vg_assert(sectors[y].tt_n_inuse >= 0); 832 833 /* Copy into tc. */ 834 tce = sectors[y].tc_next; 835 vg_assert(tce >= §ors[y].tc[0]); 836 vg_assert(tce <= §ors[y].tc[tc_sector_szQ]); 837 838 tce[0] = entry; 839 dstP = (UChar*)(&tce[1]); 840 srcP = (UChar*)code; 841 for (i = 0; i < code_len; i++) 842 dstP[i] = srcP[i]; 843 sectors[y].tc_next += reqdQ; 844 sectors[y].tt_n_inuse++; 845 846 invalidate_icache( dstP, code_len ); 847 848 /* more paranoia */ 849 tce2 = sectors[y].tc_next; 850 vg_assert(tce2 >= §ors[y].tc[0]); 851 vg_assert(tce2 <= §ors[y].tc[tc_sector_szQ]); 852 853 /* Find an empty tt slot, and use it. There must be such a slot 854 since tt is never allowed to get completely full. */ 855 i = HASH_TT(entry); 856 vg_assert(i >= 0 && i < N_TTES_PER_SECTOR); 857 while (True) { 858 if (sectors[y].tt[i].status == Empty 859 || sectors[y].tt[i].status == Deleted) 860 break; 861 i++; 862 if (i >= N_TTES_PER_SECTOR) 863 i = 0; 864 } 865 866 sectors[y].tt[i].status = InUse; 867 sectors[y].tt[i].tce = tce; 868 sectors[y].tt[i].count = 0; 869 sectors[y].tt[i].weight = 1; 870 sectors[y].tt[i].vge = *vge; 871 sectors[y].tt[i].entry = entry; 872 873 /* Update the fast-cache. */ 874 setFastCacheEntry( entry, tce, §ors[y].tt[i].count ); 875 876 /* Note the eclass numbers for this translation. */ 877 upd_eclasses_after_add( §ors[y], i ); 878} 879 880 881/* Search for the translation of the given guest address. If 882 requested, a successful search can also cause the fast-caches to be 883 updated. 884*/ 885Bool VG_(search_transtab) ( /*OUT*/AddrH* result, 886 Addr64 guest_addr, 887 Bool upd_cache ) 888{ 889 Int i, j, k, kstart, sno; 890 891 vg_assert(init_done); 892 /* Find the initial probe point just once. It will be the same in 893 all sectors and avoids multiple expensive % operations. */ 894 n_full_lookups++; 895 k = -1; 896 kstart = HASH_TT(guest_addr); 897 vg_assert(kstart >= 0 && kstart < N_TTES_PER_SECTOR); 898 899 /* Search in all the sectors. Although the order should not matter, 900 it might be most efficient to search in the order youngest to 901 oldest. */ 902 sno = youngest_sector; 903 for (i = 0; i < N_SECTORS; i++) { 904 905 if (sectors[sno].tc == NULL) 906 goto notfound; /* sector not in use. */ 907 908 k = kstart; 909 for (j = 0; j < N_TTES_PER_SECTOR; j++) { 910 n_lookup_probes++; 911 if (sectors[sno].tt[k].status == InUse 912 && sectors[sno].tt[k].entry == guest_addr) { 913 /* found it */ 914 if (upd_cache) 915 setFastCacheEntry( 916 guest_addr, sectors[sno].tt[k].tce, 917 §ors[sno].tt[k].count ); 918 if (result) 919 *result = sizeof(Addr64) + (AddrH)sectors[sno].tt[k].tce; 920 return True; 921 } 922 if (sectors[sno].tt[k].status == Empty) 923 break; /* not found in this sector */ 924 k++; 925 if (k == N_TTES_PER_SECTOR) 926 k = 0; 927 } 928 929 /* If we fall off the end, all entries are InUse and not 930 matching, or Deleted. In any case we did not find it in this 931 sector. */ 932 933 notfound: 934 /* move to the next oldest sector */ 935 sno = sno==0 ? (N_SECTORS-1) : (sno-1); 936 } 937 938 /* Not found in any sector. */ 939 return False; 940} 941 942 943/*-------------------------------------------------------------*/ 944/*--- Delete translations. ---*/ 945/*-------------------------------------------------------------*/ 946 947/* Stuff for deleting translations which intersect with a given 948 address range. Unfortunately, to make this run at a reasonable 949 speed, it is complex. */ 950 951static inline 952Bool overlap1 ( Addr64 s1, ULong r1, Addr64 s2, ULong r2 ) 953{ 954 Addr64 e1 = s1 + r1 - 1ULL; 955 Addr64 e2 = s2 + r2 - 1ULL; 956 if (e1 < s2 || e2 < s1) 957 return False; 958 return True; 959} 960 961static inline 962Bool overlaps ( Addr64 start, ULong range, VexGuestExtents* vge ) 963{ 964 if (overlap1(start, range, vge->base[0], (UInt)vge->len[0])) 965 return True; 966 if (vge->n_used < 2) 967 return False; 968 if (overlap1(start, range, vge->base[1], (UInt)vge->len[1])) 969 return True; 970 if (vge->n_used < 3) 971 return False; 972 if (overlap1(start, range, vge->base[2], (UInt)vge->len[2])) 973 return True; 974 return False; 975} 976 977 978/* Delete a tt entry, and update all the eclass data accordingly. */ 979 980static void delete_tte ( /*MOD*/Sector* sec, Int tteno ) 981{ 982 Int i, ec_num, ec_idx; 983 TTEntry* tte; 984 985 vg_assert(tteno >= 0 && tteno < N_TTES_PER_SECTOR); 986 tte = &sec->tt[tteno]; 987 vg_assert(tte->status == InUse); 988 vg_assert(tte->n_tte2ec >= 1 && tte->n_tte2ec <= 3); 989 990 /* Deal with the ec-to-tte links first. */ 991 for (i = 0; i < tte->n_tte2ec; i++) { 992 ec_num = (Int)tte->tte2ec_ec[i]; 993 ec_idx = tte->tte2ec_ix[i]; 994 vg_assert(ec_num >= 0 && ec_num < ECLASS_N); 995 vg_assert(ec_idx >= 0); 996 vg_assert(ec_idx < sec->ec2tte_used[ec_num]); 997 /* Assert that the two links point at each other. */ 998 vg_assert(sec->ec2tte[ec_num][ec_idx] == (UShort)tteno); 999 /* "delete" the pointer back to here. */ 1000 sec->ec2tte[ec_num][ec_idx] = EC2TTE_DELETED; 1001 } 1002 1003 /* Now fix up this TTEntry. */ 1004 tte->status = Deleted; 1005 tte->n_tte2ec = 0; 1006 1007 /* Stats .. */ 1008 sec->tt_n_inuse--; 1009 n_disc_count++; 1010 n_disc_osize += vge_osize(&tte->vge); 1011 1012 /* Tell the tool too. */ 1013 if (VG_(needs).basic_block_discards) { 1014 VG_TDICT_CALL( tool_discard_basic_block_info, 1015 tte->entry, 1016 tte->vge ); 1017 } 1018} 1019 1020 1021/* Delete translations from sec which intersect specified range, but 1022 only consider translations in the specified eclass. */ 1023 1024static 1025Bool delete_translations_in_sector_eclass ( /*MOD*/Sector* sec, 1026 Addr64 guest_start, ULong range, 1027 Int ec ) 1028{ 1029 Int i; 1030 UShort tteno; 1031 Bool anyDeld = False; 1032 TTEntry* tte; 1033 1034 vg_assert(ec >= 0 && ec < ECLASS_N); 1035 1036 for (i = 0; i < sec->ec2tte_used[ec]; i++) { 1037 1038 tteno = sec->ec2tte[ec][i]; 1039 if (tteno == EC2TTE_DELETED) { 1040 /* already deleted */ 1041 continue; 1042 } 1043 1044 vg_assert(tteno < N_TTES_PER_SECTOR); 1045 1046 tte = &sec->tt[tteno]; 1047 vg_assert(tte->status == InUse); 1048 1049 if (overlaps( guest_start, range, &tte->vge )) { 1050 anyDeld = True; 1051 delete_tte( sec, (Int)tteno ); 1052 } 1053 1054 } 1055 1056 return anyDeld; 1057} 1058 1059 1060/* Delete translations from sec which intersect specified range, the 1061 slow way, by inspecting all translations in sec. */ 1062 1063static 1064Bool delete_translations_in_sector ( /*MOD*/Sector* sec, 1065 Addr64 guest_start, ULong range ) 1066{ 1067 Int i; 1068 Bool anyDeld = False; 1069 1070 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 1071 if (sec->tt[i].status == InUse 1072 && overlaps( guest_start, range, &sec->tt[i].vge )) { 1073 anyDeld = True; 1074 delete_tte( sec, i ); 1075 } 1076 } 1077 1078 return anyDeld; 1079} 1080 1081 1082void VG_(discard_translations) ( Addr64 guest_start, ULong range, 1083 HChar* who ) 1084{ 1085 Sector* sec; 1086 Int sno, ec; 1087 Bool anyDeleted = False; 1088 1089 vg_assert(init_done); 1090 1091 VG_(debugLog)(2, "transtab", 1092 "discard_translations(0x%llx, %lld) req by %s\n", 1093 guest_start, range, who ); 1094 1095 /* Pre-deletion sanity check */ 1096 if (VG_(clo_sanity_level >= 4)) { 1097 Bool sane = sanity_check_all_sectors(); 1098 vg_assert(sane); 1099 } 1100 1101 if (range == 0) 1102 return; 1103 1104 /* There are two different ways to do this. 1105 1106 If the range fits within a single address-range equivalence 1107 class, as will be the case for a cache line sized invalidation, 1108 then we only have to inspect the set of translations listed in 1109 that equivalence class, and also in the "sin-bin" equivalence 1110 class ECLASS_MISC. 1111 1112 Otherwise, the invalidation is of a larger range and probably 1113 results from munmap. In this case it's (probably!) faster just 1114 to inspect all translations, dump those we don't want, and 1115 regenerate the equivalence class information (since modifying it 1116 in-situ is even more expensive). 1117 */ 1118 1119 /* First off, figure out if the range falls within a single class, 1120 and if so which one. */ 1121 1122 ec = ECLASS_MISC; 1123 if (range < (1ULL << ECLASS_SHIFT)) 1124 ec = range_to_eclass( guest_start, (UInt)range ); 1125 1126 /* if ec is ECLASS_MISC then we aren't looking at just a single 1127 class, so use the slow scheme. Else use the fast scheme, 1128 examining 'ec' and ECLASS_MISC. */ 1129 1130 if (ec != ECLASS_MISC) { 1131 1132 VG_(debugLog)(2, "transtab", 1133 " FAST, ec = %d\n", ec); 1134 1135 /* Fast scheme */ 1136 vg_assert(ec >= 0 && ec < ECLASS_MISC); 1137 1138 for (sno = 0; sno < N_SECTORS; sno++) { 1139 sec = §ors[sno]; 1140 if (sec->tc == NULL) 1141 continue; 1142 anyDeleted |= delete_translations_in_sector_eclass( 1143 sec, guest_start, range, ec ); 1144 anyDeleted |= delete_translations_in_sector_eclass( 1145 sec, guest_start, range, ECLASS_MISC ); 1146 } 1147 1148 } else { 1149 1150 /* slow scheme */ 1151 1152 VG_(debugLog)(2, "transtab", 1153 " SLOW, ec = %d\n", ec); 1154 1155 for (sno = 0; sno < N_SECTORS; sno++) { 1156 sec = §ors[sno]; 1157 if (sec->tc == NULL) 1158 continue; 1159 anyDeleted |= delete_translations_in_sector( 1160 sec, guest_start, range ); 1161 } 1162 1163 } 1164 1165 if (anyDeleted) 1166 invalidateFastCache(); 1167 1168 /* Post-deletion sanity check */ 1169 if (VG_(clo_sanity_level >= 4)) { 1170 Int i; 1171 TTEntry* tte; 1172 Bool sane = sanity_check_all_sectors(); 1173 vg_assert(sane); 1174 /* But now, also check the requested address range isn't 1175 present anywhere. */ 1176 for (sno = 0; sno < N_SECTORS; sno++) { 1177 sec = §ors[sno]; 1178 if (sec->tc == NULL) 1179 continue; 1180 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 1181 tte = &sec->tt[i]; 1182 if (tte->status != InUse) 1183 continue; 1184 vg_assert(!overlaps( guest_start, range, &tte->vge )); 1185 } 1186 } 1187 } 1188} 1189 1190 1191/*------------------------------------------------------------*/ 1192/*--- Initialisation. ---*/ 1193/*------------------------------------------------------------*/ 1194 1195void VG_(init_tt_tc) ( void ) 1196{ 1197 Int i, j, avg_codeszQ; 1198 1199 vg_assert(!init_done); 1200 init_done = True; 1201 1202 /* Otherwise lots of things go wrong... */ 1203 vg_assert(sizeof(ULong) == 8); 1204 vg_assert(sizeof(Addr64) == 8); 1205 1206 if (VG_(clo_verbosity) > 2) 1207 VG_(message)(Vg_DebugMsg, 1208 "TT/TC: VG_(init_tt_tc) " 1209 "(startup of code management)"); 1210 1211 /* Figure out how big each tc area should be. */ 1212 avg_codeszQ = (VG_(details).avg_translation_sizeB + 7) / 8; 1213 tc_sector_szQ = N_TTES_PER_SECTOR_USABLE * (1 + avg_codeszQ); 1214 1215 /* Ensure the calculated value is not way crazy. */ 1216 vg_assert(tc_sector_szQ >= 2 * N_TTES_PER_SECTOR_USABLE); 1217 vg_assert(tc_sector_szQ <= 50 * N_TTES_PER_SECTOR_USABLE); 1218 1219 /* Initialise the sectors */ 1220 youngest_sector = 0; 1221 for (i = 0; i < N_SECTORS; i++) { 1222 sectors[i].tc = NULL; 1223 sectors[i].tt = NULL; 1224 sectors[i].tc_next = NULL; 1225 sectors[i].tt_n_inuse = 0; 1226 for (j = 0; j < ECLASS_N; j++) { 1227 sectors[i].ec2tte_size[j] = 0; 1228 sectors[i].ec2tte_used[j] = 0; 1229 sectors[i].ec2tte[j] = NULL; 1230 } 1231 } 1232 1233 /* and the fast caches. */ 1234 invalidateFastCache(); 1235 1236 if (VG_(clo_verbosity) > 2) { 1237 VG_(message)(Vg_DebugMsg, 1238 "TT/TC: cache: %d sectors of %d bytes each = %d total", 1239 N_SECTORS, 8 * tc_sector_szQ, 1240 N_SECTORS * 8 * tc_sector_szQ ); 1241 VG_(message)(Vg_DebugMsg, 1242 "TT/TC: table: %d total entries, max occupancy %d (%d%%)", 1243 N_SECTORS * N_TTES_PER_SECTOR, 1244 N_SECTORS * N_TTES_PER_SECTOR_USABLE, 1245 SECTOR_TT_LIMIT_PERCENT ); 1246 } 1247 1248 VG_(debugLog)(2, "transtab", 1249 "cache: %d sectors of %d bytes each = %d total\n", 1250 N_SECTORS, 8 * tc_sector_szQ, 1251 N_SECTORS * 8 * tc_sector_szQ ); 1252 VG_(debugLog)(2, "transtab", 1253 "table: %d total entries, max occupancy %d (%d%%)\n", 1254 N_SECTORS * N_TTES_PER_SECTOR, 1255 N_SECTORS * N_TTES_PER_SECTOR_USABLE, 1256 SECTOR_TT_LIMIT_PERCENT ); 1257} 1258 1259 1260/*------------------------------------------------------------*/ 1261/*--- Printing out statistics. ---*/ 1262/*------------------------------------------------------------*/ 1263 1264static ULong safe_idiv( ULong a, ULong b ) 1265{ 1266 return (b == 0 ? 0 : a / b); 1267} 1268 1269UInt VG_(get_bbs_translated) ( void ) 1270{ 1271 return n_in_count; 1272} 1273 1274void VG_(print_tt_tc_stats) ( void ) 1275{ 1276 VG_(message)(Vg_DebugMsg, 1277 " tt/tc: %,llu tt lookups requiring %,llu probes", 1278 n_full_lookups, n_lookup_probes ); 1279 VG_(message)(Vg_DebugMsg, 1280 " tt/tc: %,llu fast-cache updates, %,llu flushes", 1281 n_fast_updates, n_fast_flushes ); 1282 1283 VG_(message)(Vg_DebugMsg, 1284 "translate: new %,lld " 1285 "(%,llu -> %,llu; ratio %,llu:10) [%,llu scs]", 1286 n_in_count, n_in_osize, n_in_tsize, 1287 safe_idiv(10*n_in_tsize, n_in_osize), 1288 n_in_sc_count); 1289 VG_(message)(Vg_DebugMsg, 1290 "translate: dumped %,llu (%,llu -> ?" "?)", 1291 n_dump_count, n_dump_osize ); 1292 VG_(message)(Vg_DebugMsg, 1293 "translate: discarded %,llu (%,llu -> ?" "?)", 1294 n_disc_count, n_disc_osize ); 1295 1296 if (0) { 1297 Int i; 1298 VG_(printf)("\n"); 1299 for (i = 0; i < ECLASS_N; i++) { 1300 VG_(printf)(" %4d", sectors[0].ec2tte_used[i]); 1301 if (i % 16 == 15) 1302 VG_(printf)("\n"); 1303 } 1304 VG_(printf)("\n\n"); 1305 } 1306} 1307 1308/*------------------------------------------------------------*/ 1309/*--- Printing out of profiling results. ---*/ 1310/*------------------------------------------------------------*/ 1311 1312static ULong score ( TTEntry* tte ) 1313{ 1314 return ((ULong)tte->weight) * ((ULong)tte->count); 1315} 1316 1317ULong VG_(get_BB_profile) ( BBProfEntry tops[], UInt n_tops ) 1318{ 1319 Int sno, i, r, s; 1320 ULong score_total; 1321 1322 /* First, compute the total weighted count, and find the top N 1323 ttes. tops contains pointers to the most-used n_tops blocks, in 1324 descending order (viz, tops[0] is the highest scorer). */ 1325 for (i = 0; i < n_tops; i++) { 1326 tops[i].addr = 0; 1327 tops[i].score = 0; 1328 } 1329 1330 score_total = 0; 1331 1332 for (sno = 0; sno < N_SECTORS; sno++) { 1333 if (sectors[sno].tc == NULL) 1334 continue; 1335 for (i = 0; i < N_TTES_PER_SECTOR; i++) { 1336 if (sectors[sno].tt[i].status != InUse) 1337 continue; 1338 score_total += score(§ors[sno].tt[i]); 1339 /* Find the rank for sectors[sno].tt[i]. */ 1340 r = n_tops-1; 1341 while (True) { 1342 if (r == -1) 1343 break; 1344 if (tops[r].addr == 0) { 1345 r--; 1346 continue; 1347 } 1348 if ( score(§ors[sno].tt[i]) > tops[r].score ) { 1349 r--; 1350 continue; 1351 } 1352 break; 1353 } 1354 r++; 1355 vg_assert(r >= 0 && r <= n_tops); 1356 /* This bb should be placed at r, and bbs above it shifted 1357 upwards one slot. */ 1358 if (r < n_tops) { 1359 for (s = n_tops-1; s > r; s--) 1360 tops[s] = tops[s-1]; 1361 tops[r].addr = sectors[sno].tt[i].entry; 1362 tops[r].score = score( §ors[sno].tt[i] ); 1363 } 1364 } 1365 } 1366 1367 return score_total; 1368} 1369 1370/*--------------------------------------------------------------------*/ 1371/*--- end ---*/ 1372/*--------------------------------------------------------------------*/ 1373