m_transtab.c revision 26412bd2c4ef3e55683141f132ebd1eb32d8530b
1de4a1d01951937632098a6cda45859afa587a06fsewardj 2de4a1d01951937632098a6cda45859afa587a06fsewardj/*--------------------------------------------------------------------*/ 3de4a1d01951937632098a6cda45859afa587a06fsewardj/*--- Management of the translation table and cache. ---*/ 48bddf58af8cc7342d4bde6712c5a6a33bf2850d4njn/*--- m_transtab.c ---*/ 5de4a1d01951937632098a6cda45859afa587a06fsewardj/*--------------------------------------------------------------------*/ 6de4a1d01951937632098a6cda45859afa587a06fsewardj 7de4a1d01951937632098a6cda45859afa587a06fsewardj/* 8b9c427c63a278cc612ae0ec573be7bb1abaa447fnjn This file is part of Valgrind, a dynamic binary instrumentation 9b9c427c63a278cc612ae0ec573be7bb1abaa447fnjn framework. 10de4a1d01951937632098a6cda45859afa587a06fsewardj 11fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Copyright (C) 2000-2005 Julian Seward 12de4a1d01951937632098a6cda45859afa587a06fsewardj jseward@acm.org 13de4a1d01951937632098a6cda45859afa587a06fsewardj 14de4a1d01951937632098a6cda45859afa587a06fsewardj This program is free software; you can redistribute it and/or 15de4a1d01951937632098a6cda45859afa587a06fsewardj modify it under the terms of the GNU General Public License as 16de4a1d01951937632098a6cda45859afa587a06fsewardj published by the Free Software Foundation; either version 2 of the 17de4a1d01951937632098a6cda45859afa587a06fsewardj License, or (at your option) any later version. 18de4a1d01951937632098a6cda45859afa587a06fsewardj 19de4a1d01951937632098a6cda45859afa587a06fsewardj This program is distributed in the hope that it will be useful, but 20de4a1d01951937632098a6cda45859afa587a06fsewardj WITHOUT ANY WARRANTY; without even the implied warranty of 21de4a1d01951937632098a6cda45859afa587a06fsewardj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 22de4a1d01951937632098a6cda45859afa587a06fsewardj General Public License for more details. 23de4a1d01951937632098a6cda45859afa587a06fsewardj 24de4a1d01951937632098a6cda45859afa587a06fsewardj You should have received a copy of the GNU General Public License 25de4a1d01951937632098a6cda45859afa587a06fsewardj along with this program; if not, write to the Free Software 26de4a1d01951937632098a6cda45859afa587a06fsewardj Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 27de4a1d01951937632098a6cda45859afa587a06fsewardj 02111-1307, USA. 28de4a1d01951937632098a6cda45859afa587a06fsewardj 29e49d8e7dfd3a9c96feb9935b5920973dfc0b170anjn The GNU General Public License is contained in the file COPYING. 30de4a1d01951937632098a6cda45859afa587a06fsewardj*/ 31de4a1d01951937632098a6cda45859afa587a06fsewardj 32c7561b931e249acf3768ead77638545b0ccaa8f1njn#include "pub_core_basics.h" 3310f08cf5b84882eebbb6712a7be890577650e8adsewardj#include "pub_core_machine.h" // ppc32: VG_(cache_line_size_ppc32) 3497405b2d134b52880d6dbec3eb2929e2002c2542njn#include "pub_core_libcbase.h" 35132bfccd21960e462352175f8553a5bdce8a210cnjn#include "pub_core_libcassert.h" 3610f08cf5b84882eebbb6712a7be890577650e8adsewardj#include "pub_core_libcmman.h" // For VG_(get_memory_from_mmap)() 3736a20fa5f779a0a6fb7b4a90dcaa6376481f1faanjn#include "pub_core_libcprint.h" 382024234c590f408994b373abfb00bc2cd2a90c48njn#include "pub_core_options.h" 3910f08cf5b84882eebbb6712a7be890577650e8adsewardj#include "pub_core_tooliface.h" // For VG_(details).avg_translation_sizeB 408bddf58af8cc7342d4bde6712c5a6a33bf2850d4njn#include "pub_core_transtab.h" 41de4a1d01951937632098a6cda45859afa587a06fsewardj 4218d7513cc08bf982711c8a22b70d56af6aa87b33sewardj/* #define DEBUG_TRANSTAB */ 4318d7513cc08bf982711c8a22b70d56af6aa87b33sewardj 44de4a1d01951937632098a6cda45859afa587a06fsewardj 456c3769f487145a08c01b58d6e5db3ba274062ad4sewardj/*-------------------------------------------------------------*/ 466c3769f487145a08c01b58d6e5db3ba274062ad4sewardj/*--- Management of the FIFO-based translation table+cache. ---*/ 476c3769f487145a08c01b58d6e5db3ba274062ad4sewardj/*-------------------------------------------------------------*/ 48de4a1d01951937632098a6cda45859afa587a06fsewardj 496c3769f487145a08c01b58d6e5db3ba274062ad4sewardj/*------------------ CONSTANTS ------------------*/ 50de4a1d01951937632098a6cda45859afa587a06fsewardj 51fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Number of sectors the TC is divided into. If you need a larger 52fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj overall translation cache, increase this value. */ 53fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj#define N_SECTORS 8 54de4a1d01951937632098a6cda45859afa587a06fsewardj 55fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Number of TC entries in each sector. This needs to be a prime 56fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj number to work properly, and it is strongly recommended not to 57fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj change this. */ 58fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj#define N_TTES_PER_SECTOR /*30011*/ 40009 59de4a1d01951937632098a6cda45859afa587a06fsewardj 60fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Because each sector contains a hash table of TTEntries, we need to 61fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj specify the maximum allowable loading, after which the sector is 62fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj deemed full. */ 63fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj#define SECTOR_TT_LIMIT_PERCENT 60 64de4a1d01951937632098a6cda45859afa587a06fsewardj 65fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* The sector is deemed full when this many entries are in it. */ 66fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj#define N_TTES_PER_SECTOR_USABLE \ 67fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ((N_TTES_PER_SECTOR * SECTOR_TT_LIMIT_PERCENT) / 100) 686c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 69de4a1d01951937632098a6cda45859afa587a06fsewardj 706c3769f487145a08c01b58d6e5db3ba274062ad4sewardj/*------------------ TYPES ------------------*/ 71de4a1d01951937632098a6cda45859afa587a06fsewardj 72fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* A translation-cache entry is two parts: 73fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj - The guest address of the first (entry) bb in the translation, 74fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj as a 64-bit word. 75fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj - One or more 64-bit words containing the code. 76fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj It is supposed to be 64-bit aligned. 77fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 78fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* 796c3769f487145a08c01b58d6e5db3ba274062ad4sewardjtypedef 80fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj struct { 81fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Addr64 orig_addr; 82fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ULong code[0]; 836c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 846c3769f487145a08c01b58d6e5db3ba274062ad4sewardj TCEntry; 85fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 866c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 87fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* A translation-table entry. This indicates precisely which areas of 88fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj guest code are included in the translation, and contains all other 89fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj auxiliary info too. */ 906c3769f487145a08c01b58d6e5db3ba274062ad4sewardjtypedef 916c3769f487145a08c01b58d6e5db3ba274062ad4sewardj struct { 92fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Profiling only: the count and weight (arbitrary meaning) for 93fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj this translation. Weight is a property of the translation 94fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj itself and computed once when the translation is created. 95fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Count is an entry count for the translation and is 96fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj incremented by 1 every time the translation is used, if we 97fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj are profiling. */ 98fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UInt count; 99fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UShort weight; 100fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 101fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Status of the slot. Note, we need to be able to do lazy 102fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj deletion, hence the Deleted state. */ 103fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj enum { InUse, Deleted, Empty } status; 104fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 105fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Pointer to the corresponding TCEntry (must be in the same 106fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sector!) */ 107fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ULong* tce; 108fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 109fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* This is the original guest address that purportedly is the 110fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj entry point of the translation. You might think that .entry 111fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj should be the same as .vge->base[0], and most of the time it 112fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj is. However, when doing redirections, that is not the case. 113fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj .vge must always correctly describe the guest code sections 114fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj from which this translation was made. However, .entry may or 115fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj may not be a lie, depending on whether or not we're doing 116fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj redirection. */ 117fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Addr64 entry; 118fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 119fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* This structure describes precisely what ranges of guest code 120fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj the translation covers, so we can decide whether or not to 121fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj delete it when translations of a given address range are 122fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj invalidated. */ 123fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VexGuestExtents vge; 1246c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 1256c3769f487145a08c01b58d6e5db3ba274062ad4sewardj TTEntry; 1266c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 1274ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 128fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Finally, a sector itself. Each sector contains an array of 129fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj TCEntries, which hold code, and an array of TTEntries, containing 130fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj all required administrative info. Profiling is supported using the 131fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj TTEntry .count and .weight fields, if required. Each sector is 132fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj independent in that no cross-sector references are allowed. 1334ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 134fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj If the sector is not in use, all three pointers are NULL and 135fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tt_n_inuse is zero. 136fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 137fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjtypedef 138fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj struct { 139fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* The TCEntry area. Size of this depends on the average 140fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj translation size. We try and size it so it becomes full 141fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj precisely when this sector's translation table (tt) reaches 142fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj its load limit (SECTOR_TT_LIMIT_PERCENT). */ 143fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ULong* tc; 1444ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 145fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* The TTEntry array. This is a fixed size, always containing 146fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj exactly N_TTES_PER_SECTOR entries. */ 147fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj TTEntry* tt; 1486c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 149fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* This points to the current allocation point in tc. */ 150fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ULong* tc_next; 151de4a1d01951937632098a6cda45859afa587a06fsewardj 152fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* The count of tt entries with state InUse. */ 153fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int tt_n_inuse; 154fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 155fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Sector; 156de4a1d01951937632098a6cda45859afa587a06fsewardj 157de4a1d01951937632098a6cda45859afa587a06fsewardj 1586c3769f487145a08c01b58d6e5db3ba274062ad4sewardj/*------------------ DECLS ------------------*/ 1596c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 160fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* The root data structure is an array of sectors. The index of the 161fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj youngest sector is recorded, and new translations are put into that 162fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sector. When it fills up, we move along to the next sector and 163fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj start to fill that up, wrapping around at the end of the array. 164fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj That way, once all N_TC_SECTORS have been bought into use for the 165fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj first time, and are full, we then re-use the oldest sector, 166fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj endlessly. 167fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 168fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj When running, youngest sector should be between >= 0 and < 169fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj N_TC_SECTORS. The initial -1 value indicates the TT/TC system is 170fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj not yet initialised. 171fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 172fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic Sector sectors[N_SECTORS]; 173fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic Int youngest_sector = -1; 1746c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 175fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* The number of ULongs in each TCEntry area. This is computed once 176fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj at startup and does not change. */ 177fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic Int tc_sector_szQ; 1786c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 1796c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 180fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Fast helper for the TC. A direct-mapped cache which holds a 181fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj pointer to a TC entry which may or may not be the correct one, but 182fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj which we hope usually is. This array is referred to directly from 183fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj <arch>/dispatch.S. 1846c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 185fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Entries in tt_fast may point to any valid TC entry, regardless of 186fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj which sector it's in. Consequently we must be very careful to 187fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj invalidate this cache when TC entries are changed or disappear. 188c0d8f68810eb79a5a6cb6049d6a4ab1de7dc4e18sewardj 189fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj A special TCEntry -- bogus_tc_entry -- must be pointed at to cause 190fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj that cache entry to miss. This relies on the assumption that no 191fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj guest code actually has an address of 0x1. 192fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 193fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*global*/ ULong* VG_(tt_fast)[VG_TT_FAST_SIZE]; 19492e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote 195fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic ULong bogus_tc_entry = (Addr64)1; 19692e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote 19792e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote 198fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* For profiling, we have a parallel array of pointers to .count 199fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj fields in TT entries. Again, these pointers must be invalidated 200fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj when translations disappear. A NULL pointer suffices to indicate 201fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj an unused slot. 2026c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 203fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tt_fast and tt_fastN change together: if tt_fast[i] points to 204fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj bogus_tc_entry then the corresponding tt_fastN[i] must be null. If 205fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tt_fast[i] points to some TC entry somewhere, then tt_fastN[i] 206fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj *must* point to the .count field of the corresponding TT entry. 2076c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 208fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tt_fast and tt_fastN are referred to from assembly code 209fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj (dispatch.S). 210fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 211fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*global*/ UInt* VG_(tt_fastN)[VG_TT_FAST_SIZE]; 212de4a1d01951937632098a6cda45859afa587a06fsewardj 213de4a1d01951937632098a6cda45859afa587a06fsewardj 214663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj/* Make sure we're not used before initialisation. */ 215663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardjstatic Bool init_done = False; 216663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj 217663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj 218fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------ STATS DECLS ------------------*/ 219de4a1d01951937632098a6cda45859afa587a06fsewardj 220fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Number of fast-cache updates and flushes done. */ 221fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_fast_flushes = 0; 222fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_fast_updates = 0; 22322854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj 224fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Number of full lookups done. */ 225fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_full_lookups = 0; 226fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_lookup_probes = 0; 22722854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj 22826412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj/* Number/osize/tsize of translations entered; also the number of 22926412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj those for which self-checking was requested. */ 23026412bd2c4ef3e55683141f132ebd1eb32d8530bsewardjULong n_in_count = 0; 23126412bd2c4ef3e55683141f132ebd1eb32d8530bsewardjULong n_in_osize = 0; 23226412bd2c4ef3e55683141f132ebd1eb32d8530bsewardjULong n_in_tsize = 0; 23326412bd2c4ef3e55683141f132ebd1eb32d8530bsewardjULong n_in_sc_count = 0; 234de4a1d01951937632098a6cda45859afa587a06fsewardj 235fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Number/osize of translations discarded due to lack of space. */ 236fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_dump_count = 0; 237fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_dump_osize = 0; 238fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 239fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Number/osize of translations discarded due to requests to do so. */ 240fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_disc_count = 0; 241fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjULong n_disc_osize = 0; 242fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 243fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 244fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 245fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*-------------------------------------------------------------*/ 246fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*--- Add/delete/find translations ---*/ 247fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*-------------------------------------------------------------*/ 248fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 249fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic UInt vge_osize ( VexGuestExtents* vge ) 250c0d8f68810eb79a5a6cb6049d6a4ab1de7dc4e18sewardj{ 251fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UInt i, n = 0; 252fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < vge->n_used; i++) 253fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n += (UInt)vge->len[i]; 254fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return n; 255c0d8f68810eb79a5a6cb6049d6a4ab1de7dc4e18sewardj} 256c0d8f68810eb79a5a6cb6049d6a4ab1de7dc4e18sewardj 257fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic Bool isValidSector ( Int sector ) 2586c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 259fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sector < 0 || sector >= N_SECTORS) 260fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return False; 261fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return True; 2626c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 263de4a1d01951937632098a6cda45859afa587a06fsewardj 264fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic inline UInt HASH_TT ( Addr64 key ) 265de4a1d01951937632098a6cda45859afa587a06fsewardj{ 266fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UInt kHi = (UInt)(key >> 32); 267fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UInt kLo = (UInt)key; 268fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return (kHi ^ kLo) % N_TTES_PER_SECTOR; 269de4a1d01951937632098a6cda45859afa587a06fsewardj} 270de4a1d01951937632098a6cda45859afa587a06fsewardj 271fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic void setFastCacheEntry ( Addr64 key, ULong* tce, UInt* count ) 272de4a1d01951937632098a6cda45859afa587a06fsewardj{ 273fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UInt cno = ((UInt)key) & VG_TT_FAST_MASK; 274fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(tt_fast)[cno] = tce; 275fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(tt_fastN)[cno] = count; 276fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_fast_updates++; 2776c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 278de4a1d01951937632098a6cda45859afa587a06fsewardj 279fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic void invalidateFastCache ( void ) 2806c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 281fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UInt j; 282fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (j = 0; j < VG_TT_FAST_SIZE; j++) { 283fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(tt_fast)[j] = &bogus_tc_entry; 284fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(tt_fastN)[j] = NULL; 2856c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 286fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_fast_flushes++; 2876c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 288de4a1d01951937632098a6cda45859afa587a06fsewardj 289fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic void initialiseSector ( Int sno ) 2906c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 291fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int i; 292fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(isValidSector(sno)); 293fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 294fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tc == NULL) { 295fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Sector has never been used before. Need to allocate tt and 296fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tc. */ 297fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[sno].tt == NULL); 298fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[sno].tc_next == NULL); 299fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[sno].tt_n_inuse == 0); 300fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tc 301fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj = VG_(get_memory_from_mmap) 302fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ( 8 * tc_sector_szQ, "sectors[sno].tc" ); 303fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tt 304fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj = VG_(get_memory_from_mmap) 305fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ( N_TTES_PER_SECTOR * sizeof(TTEntry), "sectors[sno].tt" ); 306fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (VG_(clo_verbosity) > 2) 307fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(message)(Vg_DebugMsg, "TT/TC: initialise sector %d", sno); 308fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } else { 309fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Sector has been used before. */ 310fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[sno].tt != NULL); 311fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[sno].tc_next != NULL); 312fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_dump_count += sectors[sno].tt_n_inuse; 313fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < N_TTES_PER_SECTOR; i++) { 314fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tt[i].status == InUse) { 315fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_dump_osize += vge_osize(§ors[sno].tt[i].vge); 316fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 317fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 318fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (VG_(clo_verbosity) > 2) 319fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(message)(Vg_DebugMsg, "TT/TC: recycle sector %d", sno); 3206c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 3214ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 322fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tc_next = sectors[sno].tc; 323fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tt_n_inuse = 0; 324fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < N_TTES_PER_SECTOR; i++) 325fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tt[i].status = Empty; 326fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 327fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj invalidateFastCache(); 3286c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 329de4a1d01951937632098a6cda45859afa587a06fsewardj 33010f08cf5b84882eebbb6712a7be890577650e8adsewardjstatic void invalidate_icache ( void *ptr, Int nbytes ) 33185665ca6fa29dd64754dabe50eb98f25896e752acerion{ 33210f08cf5b84882eebbb6712a7be890577650e8adsewardj# if defined(VGA_ppc32) 33310f08cf5b84882eebbb6712a7be890577650e8adsewardj Addr startaddr = (Addr) ptr; 33410f08cf5b84882eebbb6712a7be890577650e8adsewardj Addr endaddr = startaddr + nbytes; 33510f08cf5b84882eebbb6712a7be890577650e8adsewardj Addr cls = VG_(cache_line_size_ppc32); 33610f08cf5b84882eebbb6712a7be890577650e8adsewardj Addr addr; 33710f08cf5b84882eebbb6712a7be890577650e8adsewardj 3382bf6ba55b04ea9a58098f041c5ee149539c0f081sewardj /* Stay sane .. */ 3392bf6ba55b04ea9a58098f041c5ee149539c0f081sewardj vg_assert(cls == 32 || cls == 128); 34085665ca6fa29dd64754dabe50eb98f25896e752acerion 34185665ca6fa29dd64754dabe50eb98f25896e752acerion startaddr &= ~(cls - 1); 34285665ca6fa29dd64754dabe50eb98f25896e752acerion for (addr = startaddr; addr < endaddr; addr += cls) 34385665ca6fa29dd64754dabe50eb98f25896e752acerion asm volatile("dcbst 0,%0" : : "r" (addr)); 34485665ca6fa29dd64754dabe50eb98f25896e752acerion asm volatile("sync"); 34585665ca6fa29dd64754dabe50eb98f25896e752acerion for (addr = startaddr; addr < endaddr; addr += cls) 34685665ca6fa29dd64754dabe50eb98f25896e752acerion asm volatile("icbi 0,%0" : : "r" (addr)); 34785665ca6fa29dd64754dabe50eb98f25896e752acerion asm volatile("sync; isync"); 34810f08cf5b84882eebbb6712a7be890577650e8adsewardj 34910f08cf5b84882eebbb6712a7be890577650e8adsewardj# elif defined(VGA_x86) 35010f08cf5b84882eebbb6712a7be890577650e8adsewardj /* no need to do anything, hardware provides coherence */ 35110f08cf5b84882eebbb6712a7be890577650e8adsewardj 35210f08cf5b84882eebbb6712a7be890577650e8adsewardj# elif defined(VGA_amd64) 35310f08cf5b84882eebbb6712a7be890577650e8adsewardj /* no need to do anything, hardware provides coherence */ 35410f08cf5b84882eebbb6712a7be890577650e8adsewardj 35510f08cf5b84882eebbb6712a7be890577650e8adsewardj# else 35610f08cf5b84882eebbb6712a7be890577650e8adsewardj# error "Unknown ARCH" 35710f08cf5b84882eebbb6712a7be890577650e8adsewardj# endif 35885665ca6fa29dd64754dabe50eb98f25896e752acerion} 35985665ca6fa29dd64754dabe50eb98f25896e752acerion 360de4a1d01951937632098a6cda45859afa587a06fsewardj 361fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Add a translation of vge to TT/TC. The translation is temporarily 362fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj in code[0 .. code_len-1]. 363de4a1d01951937632098a6cda45859afa587a06fsewardj 364fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj pre: youngest_sector points to a valid (although possibly full) 365fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sector. 366fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 3678bddf58af8cc7342d4bde6712c5a6a33bf2850d4njnvoid VG_(add_to_transtab)( VexGuestExtents* vge, 3688bddf58af8cc7342d4bde6712c5a6a33bf2850d4njn Addr64 entry, 3698bddf58af8cc7342d4bde6712c5a6a33bf2850d4njn AddrH code, 37026412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj UInt code_len, 37126412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj Bool is_self_checking ) 37222854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj{ 373fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int tcAvailQ, reqdQ, y, i; 374fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj ULong *tce, *tce2; 375fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UChar* srcP; 376fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj UChar* dstP; 377fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 378663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj vg_assert(init_done); 379fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(vge->n_used >= 1 && vge->n_used <= 3); 380fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(code_len > 0 && code_len < 20000); 381fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 382fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (0) 3838bddf58af8cc7342d4bde6712c5a6a33bf2850d4njn VG_(printf)("add_to_transtab(entry = 0x%llx, len = %d)\n", 384fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj entry, code_len); 385fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 386fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_in_count++; 387fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_in_tsize += code_len; 388fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_in_osize += vge_osize(vge); 38926412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj if (is_self_checking) 39026412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj n_in_sc_count++; 391fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 392fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj y = youngest_sector; 393fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(isValidSector(y)); 394fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 395fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[y].tc == NULL) 396fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj initialiseSector(y); 397fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 398fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Try putting the translation in this sector. */ 399fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj reqdQ = 1 + ((code_len + 7) >> 3); 400fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 401fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Will it fit in tc? */ 402fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 403fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj - ((ULong*)(sectors[y].tc_next)); 404fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tcAvailQ >= 0); 405fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tcAvailQ <= tc_sector_szQ); 406fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 407fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (tcAvailQ < reqdQ 408fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj || sectors[y].tt_n_inuse >= N_TTES_PER_SECTOR_USABLE) { 409fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* No. So move on to the next sector. Either it's never been 410fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj used before, in which case it will get its tt/tc allocated 411fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj now, or it has been used before, in which case it is set to be 412fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj empty, hence throwing out the oldest sector. */ 413fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj youngest_sector++; 414fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (youngest_sector >= N_SECTORS) 415fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj youngest_sector = 0; 416fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj y = youngest_sector; 417fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj initialiseSector(y); 418fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 41922854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj 420fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Be sure ... */ 421fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tcAvailQ = ((ULong*)(§ors[y].tc[tc_sector_szQ])) 422fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj - ((ULong*)(sectors[y].tc_next)); 423fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tcAvailQ >= 0); 424fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tcAvailQ <= tc_sector_szQ); 425fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tcAvailQ >= reqdQ); 426fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[y].tt_n_inuse < N_TTES_PER_SECTOR_USABLE); 427fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sectors[y].tt_n_inuse >= 0); 428fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 429fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Copy into tc. */ 430fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tce = sectors[y].tc_next; 431fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tce >= §ors[y].tc[0]); 432fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tce <= §ors[y].tc[tc_sector_szQ]); 433fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 434fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tce[0] = entry; 435fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj dstP = (UChar*)(&tce[1]); 436fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj srcP = (UChar*)code; 437fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < code_len; i++) 438fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj dstP[i] = srcP[i]; 439fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tc_next += reqdQ; 440fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt_n_inuse++; 441fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 44285665ca6fa29dd64754dabe50eb98f25896e752acerion invalidate_icache( dstP, code_len ); 44385665ca6fa29dd64754dabe50eb98f25896e752acerion 444fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* more paranoia */ 445fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tce2 = sectors[y].tc_next; 446fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tce2 >= §ors[y].tc[0]); 447fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tce2 <= §ors[y].tc[tc_sector_szQ]); 448fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 449fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Find an empty tt slot, and use it. There must be such a slot 450fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj since tt is never allowed to get completely full. */ 451fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj i = HASH_TT(entry); 452fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(i >= 0 && i < N_TTES_PER_SECTOR); 45322854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj while (True) { 454fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[y].tt[i].status == Empty 455fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj || sectors[y].tt[i].status == Deleted) 456fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj break; 457fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj i++; 458fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (i >= N_TTES_PER_SECTOR) 459fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj i = 0; 46022854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj } 461fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 462fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt[i].status = InUse; 463fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt[i].tce = tce; 464fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt[i].count = 0; 465fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt[i].weight = 1; 466fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt[i].vge = *vge; 467fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[y].tt[i].entry = entry; 468fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 469fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj setFastCacheEntry( entry, tce, §ors[y].tt[i].count ); 47022854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj} 47122854b907c1925a9af97ad20ca3dacb5e300d6f9sewardj 472fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 473fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Search for the translation of the given guest address. If 474fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj requested, a successful search can also cause the fast-caches to be 475fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj updated. 476fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 477fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjBool VG_(search_transtab) ( /*OUT*/AddrH* result, 478fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Addr64 guest_addr, 479fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Bool upd_cache ) 4806c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 481fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int i, j, k, kstart, sno; 482663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj 483663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj vg_assert(init_done); 484fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Find the initial probe point just once. It will be the same in 485fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj all sectors and avoids multiple expensive % operations. */ 486fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_full_lookups++; 487fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj k = -1; 488fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj kstart = HASH_TT(guest_addr); 489fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(kstart >= 0 && kstart < N_TTES_PER_SECTOR); 490fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 491fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Search in all the sectors. Although the order should not matter, 492fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj it might be most efficient to search in the order youngest to 493fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj oldest. */ 494fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sno = youngest_sector; 495fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < N_SECTORS; i++) { 496fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 497fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tc == NULL) 498fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj goto notfound; /* sector not in use. */ 499fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 500fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj k = kstart; 501fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (j = 0; j < N_TTES_PER_SECTOR; j++) { 502fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_lookup_probes++; 503fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tt[k].status == InUse 504fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj && sectors[sno].tt[k].entry == guest_addr) { 505fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* found it */ 506fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (upd_cache) 507fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj setFastCacheEntry( 508fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj guest_addr, sectors[sno].tt[k].tce, 509fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj §ors[sno].tt[k].count ); 510fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (result) 511fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj *result = sizeof(Addr64) + (AddrH)sectors[sno].tt[k].tce; 512fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return True; 513fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 514fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tt[k].status == Empty) 515fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj break; /* not found in this sector */ 516fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj k++; 517fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (k == N_TTES_PER_SECTOR) 518fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj k = 0; 5196c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 520fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 521fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* If we fall off the end, all entries are InUse and not 522fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj matching, or Deleted. In any case we did not find it in this 523fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sector. */ 524fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 525fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj notfound: 526fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* move to the next oldest sector */ 527fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sno = sno==0 ? (N_SECTORS-1) : (sno-1); 5286c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 529fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 530fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Not found in any sector. */ 531fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return False; 5326c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 533de4a1d01951937632098a6cda45859afa587a06fsewardj 534de4a1d01951937632098a6cda45859afa587a06fsewardj 535fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/* Delete all translations which intersect with any part of the 536fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj specified guest address range. Note, this is SLOW. 537fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj*/ 538fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 539fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic inline 540fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjBool overlap1 ( Addr64 s1, UInt r1, Addr64 s2, UInt r2 ) 5416c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 542fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Addr64 e1 = s1 + (ULong)r1 - 1ULL; 543fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Addr64 e2 = s2 + (ULong)r1 - 1ULL; 544fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (e1 < s2 || e2 < s1) 545fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return False; 546fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return True; 5476c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 548de4a1d01951937632098a6cda45859afa587a06fsewardj 549fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic inline 550fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjBool overlaps ( Addr64 start, UInt range, VexGuestExtents* vge ) 5516c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 552fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (overlap1(start, range, vge->base[0], (UInt)vge->len[0])) 553fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return True; 554fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (vge->n_used < 2) 555fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return False; 556fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (overlap1(start, range, vge->base[1], (UInt)vge->len[1])) 557fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return True; 558fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (vge->n_used < 3) 559fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return False; 560fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (overlap1(start, range, vge->base[2], (UInt)vge->len[2])) 561fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return True; 562fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return False; 5636c3769f487145a08c01b58d6e5db3ba274062ad4sewardj} 564de4a1d01951937632098a6cda45859afa587a06fsewardj 565de4a1d01951937632098a6cda45859afa587a06fsewardj 566fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjvoid VG_(discard_translations) ( Addr64 guest_start, UInt range ) 5676c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 568fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int sno, i; 569fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Bool anyDeleted = False; 5706c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 571663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj vg_assert(init_done); 572663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj 573fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (sno = 0; sno < N_SECTORS; sno++) { 574fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tc == NULL) 575fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj continue; 576fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < N_TTES_PER_SECTOR; i++) { 577fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tt[i].status == InUse 578fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj && overlaps( guest_start, range, §ors[sno].tt[i].vge )) { 579fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tt[i].status = Deleted; 580fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[sno].tt_n_inuse--; 581fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj anyDeleted = True; 582fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_disc_count++; 583fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_disc_osize += vge_osize(§ors[sno].tt[i].vge); 584fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 585fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 586de4a1d01951937632098a6cda45859afa587a06fsewardj } 587de4a1d01951937632098a6cda45859afa587a06fsewardj 588fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (anyDeleted) 589fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj invalidateFastCache(); 590fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj} 5916c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 5926c3769f487145a08c01b58d6e5db3ba274062ad4sewardj 593fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------------------------------------------------*/ 594fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*--- Initialisation. ---*/ 595fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------------------------------------------------*/ 596fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 597fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjvoid VG_(init_tt_tc) ( void ) 5986c3769f487145a08c01b58d6e5db3ba274062ad4sewardj{ 599fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int i, avg_codeszQ; 600de4a1d01951937632098a6cda45859afa587a06fsewardj 601663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj vg_assert(!init_done); 602663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj init_done = True; 603663a1bd7a8def9d4ef4a10615732a15cc9b09171sewardj 604fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Otherwise lots of things go wrong... */ 605fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sizeof(ULong) == 8); 606fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(sizeof(Addr64) == 8); 607de4a1d01951937632098a6cda45859afa587a06fsewardj 608fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (VG_(clo_verbosity) > 2) 609fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(message)(Vg_DebugMsg, 610fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj "TT/TC: VG_(init_tt_tc) " 611fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj "(startup of code management)"); 612fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 613fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Figure out how big each tc area should be. */ 61443b9a8abb139b86a24457fa3c19b9cb60ca17c3anjn avg_codeszQ = (VG_(details).avg_translation_sizeB + 7) / 8; 61543b9a8abb139b86a24457fa3c19b9cb60ca17c3anjn tc_sector_szQ = N_TTES_PER_SECTOR_USABLE * (1 + avg_codeszQ); 616fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 617fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Ensure the calculated value is not way crazy. */ 618fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tc_sector_szQ >= 2 * N_TTES_PER_SECTOR_USABLE); 619fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj vg_assert(tc_sector_szQ <= 50 * N_TTES_PER_SECTOR_USABLE); 620fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 621fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Initialise the sectors */ 622fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj youngest_sector = 0; 623fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < N_SECTORS; i++) { 624fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[i].tc = NULL; 625fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[i].tt = NULL; 626fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[i].tc_next = NULL; 627fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj sectors[i].tt_n_inuse = 0; 6286c3769f487145a08c01b58d6e5db3ba274062ad4sewardj } 6294ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 630fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* and the fast caches. */ 631fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj invalidateFastCache(); 632fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 633fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (VG_(clo_verbosity) > 2) { 634fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(message)(Vg_DebugMsg, 635fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj "TT/TC: cache: %d sectors of %d bytes each = %d total", 636fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj N_SECTORS, 8 * tc_sector_szQ, 637fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj N_SECTORS * 8 * tc_sector_szQ ); 638fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(message)(Vg_DebugMsg, 639fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj "TT/TC: table: %d total entries, max occupancy %d (%d%%)", 640fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj N_SECTORS * N_TTES_PER_SECTOR, 641fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj N_SECTORS * N_TTES_PER_SECTOR_USABLE, 642fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj SECTOR_TT_LIMIT_PERCENT ); 643fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 644de4a1d01951937632098a6cda45859afa587a06fsewardj} 645de4a1d01951937632098a6cda45859afa587a06fsewardj 6464ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 647fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------------------------------------------------*/ 648fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*--- Printing out statistics. ---*/ 649fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------------------------------------------------*/ 650fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 651fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic ULong safe_idiv( ULong a, ULong b ) 65292e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote{ 65392e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote return (b == 0 ? 0 : a / b); 65492e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote} 65592e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote 656fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjUInt VG_(get_bbs_translated) ( void ) 657fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj{ 658fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return n_in_count; 659fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj} 660fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 661fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjvoid VG_(print_tt_tc_stats) ( void ) 66292e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote{ 66392e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote VG_(message)(Vg_DebugMsg, 664fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj " tt/tc: %llu tt lookups requiring %llu probes", 665fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_full_lookups, n_lookup_probes ); 66692e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote VG_(message)(Vg_DebugMsg, 667fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj " tt/tc: %llu fast-cache updates, %llu flushes", 668fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_fast_updates, n_fast_flushes ); 669fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 67092e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote VG_(message)(Vg_DebugMsg, 67126412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj "translate: new %lld " 67226412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj "(%lld -> %lld; ratio %lld:10) [%lld scs]", 673fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_in_count, n_in_osize, n_in_tsize, 67426412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj safe_idiv(10*n_in_tsize, n_in_osize), 67526412bd2c4ef3e55683141f132ebd1eb32d8530bsewardj n_in_sc_count); 67692e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote VG_(message)(Vg_DebugMsg, 677fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj "translate: dumped %lld (%lld -> ?" "?)", 678fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_dump_count, n_dump_osize ); 679fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj VG_(message)(Vg_DebugMsg, 680fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj "translate: discarded %lld (%lld -> ?" "?)", 681fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj n_disc_count, n_disc_osize ); 68292e7b7f3d93564e293483fcf0f52f2d6f6c6dcc0nethercote} 683de4a1d01951937632098a6cda45859afa587a06fsewardj 684fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------------------------------------------------*/ 685fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*--- Printing out of profiling results. ---*/ 686fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj/*------------------------------------------------------------*/ 6874ccf707a1b52898b878fc90dc0054a0c23cc9fccsewardj 688fa8ec113ecff891bdefb13dd361b40a503a992f8sewardjstatic ULong score ( TTEntry* tte ) 689fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj{ 690fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj return ((ULong)tte->weight) * ((ULong)tte->count); 691de4a1d01951937632098a6cda45859afa587a06fsewardj} 692de4a1d01951937632098a6cda45859afa587a06fsewardj 6932025cf98a3210c175a90fc77cb599cca1643bd68njnULong VG_(get_BB_profile) ( BBProfEntry tops[], UInt n_tops ) 694de4a1d01951937632098a6cda45859afa587a06fsewardj{ 695fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj Int sno, i, r, s; 6962025cf98a3210c175a90fc77cb599cca1643bd68njn ULong score_total; 697fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 698fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* First, compute the total weighted count, and find the top N 6992025cf98a3210c175a90fc77cb599cca1643bd68njn ttes. tops contains pointers to the most-used n_tops blocks, in 700fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj descending order (viz, tops[0] is the highest scorer). */ 7012025cf98a3210c175a90fc77cb599cca1643bd68njn for (i = 0; i < n_tops; i++) { 7022025cf98a3210c175a90fc77cb599cca1643bd68njn tops[i].addr = 0; 7032025cf98a3210c175a90fc77cb599cca1643bd68njn tops[i].score = 0; 7042025cf98a3210c175a90fc77cb599cca1643bd68njn } 705fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 706fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj score_total = 0; 707fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj 708fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (sno = 0; sno < N_SECTORS; sno++) { 709fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tc == NULL) 71018d7513cc08bf982711c8a22b70d56af6aa87b33sewardj continue; 711fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj for (i = 0; i < N_TTES_PER_SECTOR; i++) { 712fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (sectors[sno].tt[i].status != InUse) 713fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj continue; 714fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj score_total += score(§ors[sno].tt[i]); 715fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* Find the rank for sectors[sno].tt[i]. */ 7162025cf98a3210c175a90fc77cb599cca1643bd68njn r = n_tops-1; 717fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj while (True) { 718fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj if (r == -1) 719fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj break; 7202025cf98a3210c175a90fc77cb599cca1643bd68njn if (tops[r].addr == 0) { 721fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj r--; 722fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj continue; 723fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 7242025cf98a3210c175a90fc77cb599cca1643bd68njn if ( score(§ors[sno].tt[i]) > tops[r].score ) { 725fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj r--; 726fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj continue; 727fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 728fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj break; 729fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 730fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj r++; 7312025cf98a3210c175a90fc77cb599cca1643bd68njn vg_assert(r >= 0 && r <= n_tops); 732fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj /* This bb should be placed at r, and bbs above it shifted 733fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj upwards one slot. */ 7342025cf98a3210c175a90fc77cb599cca1643bd68njn if (r < n_tops) { 7352025cf98a3210c175a90fc77cb599cca1643bd68njn for (s = n_tops-1; s > r; s--) 736fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj tops[s] = tops[s-1]; 7372025cf98a3210c175a90fc77cb599cca1643bd68njn tops[r].addr = sectors[sno].tt[i].entry; 7382025cf98a3210c175a90fc77cb599cca1643bd68njn tops[r].score = score( §ors[sno].tt[i] ); 739fa8ec113ecff891bdefb13dd361b40a503a992f8sewardj } 740de4a1d01951937632098a6cda45859afa587a06fsewardj } 741de4a1d01951937632098a6cda45859afa587a06fsewardj } 742de4a1d01951937632098a6cda45859afa587a06fsewardj 7432025cf98a3210c175a90fc77cb599cca1643bd68njn return score_total; 744c0d8f68810eb79a5a6cb6049d6a4ab1de7dc4e18sewardj} 745c0d8f68810eb79a5a6cb6049d6a4ab1de7dc4e18sewardj 746de4a1d01951937632098a6cda45859afa587a06fsewardj/*--------------------------------------------------------------------*/ 7478bddf58af8cc7342d4bde6712c5a6a33bf2850d4njn/*--- end ---*/ 748de4a1d01951937632098a6cda45859afa587a06fsewardj/*--------------------------------------------------------------------*/ 749