| <html> |
| <head> |
| <style type="text/css"> |
| body { background-color: #ffffff; |
| color: #000000; |
| font-family: Times, Helvetica, Arial; |
| font-size: 14pt} |
| h4 { margin-bottom: 0.3em} |
| code { color: #000000; |
| font-family: Courier; |
| font-size: 13pt } |
| pre { color: #000000; |
| font-family: Courier; |
| font-size: 13pt } |
| a:link { color: #0000C0; |
| text-decoration: none; } |
| a:visited { color: #0000C0; |
| text-decoration: none; } |
| a:active { color: #0000C0; |
| text-decoration: none; } |
| </style> |
| <title>The design and implementation of Valgrind</title> |
| </head> |
| |
| <body bgcolor="#ffffff"> |
| |
| <a name="title"> </a> |
| <h1 align=center>The design and implementation of Valgrind</h1> |
| |
| <center> |
| Detailed technical notes for hackers, maintainers and the |
| overly-curious<br> |
| These notes pertain to snapshot 20020306<br> |
| <p> |
| <a href="mailto:jseward@acm.org">jseward@acm.org<br> |
| <a href="http://developer.kde.org/~sewardj">http://developer.kde.org/~sewardj</a><br> |
| Copyright © 2000-2002 Julian Seward |
| <p> |
| Valgrind is licensed under the GNU General Public License, |
| version 2<br> |
| An open-source tool for finding memory-management problems in |
| x86 GNU/Linux executables. |
| </center> |
| |
| <p> |
| |
| |
| |
| |
| <hr width="100%"> |
| |
| <h2>Introduction</h2> |
| |
| This document contains a detailed, highly-technical description of the |
| internals of Valgrind. This is not the user manual; if you are an |
| end-user of Valgrind, you do not want to read this. Conversely, if |
| you really are a hacker-type and want to know how it works, I assume |
| that you have read the user manual thoroughly. |
| <p> |
| You may need to read this document several times, and carefully. Some |
| important things, I only say once. |
| |
| |
| <h3>History</h3> |
| |
| Valgrind came into public view in late Feb 2002. However, it has been |
| under contemplation for a very long time, perhaps seriously for about |
| five years. Somewhat over two years ago, I started working on the x86 |
| code generator for the Glasgow Haskell Compiler |
| (http://www.haskell.org/ghc), gaining familiarity with x86 internals |
| on the way. I then did Cacheprof (http://www.cacheprof.org), gaining |
| further x86 experience. Some time around Feb 2000 I started |
| experimenting with a user-space x86 interpreter for x86-Linux. This |
| worked, but it was clear that a JIT-based scheme would be necessary to |
| give reasonable performance for Valgrind. Design work for the JITter |
| started in earnest in Oct 2000, and by early 2001 I had an x86-to-x86 |
| dynamic translator which could run quite large programs. This |
| translator was in a sense pointless, since it did not do any |
| instrumentation or checking. |
| |
| <p> |
| Most of the rest of 2001 was taken up designing and implementing the |
| instrumentation scheme. The main difficulty, which consumed a lot |
| of effort, was to design a scheme which did not generate large numbers |
| of false uninitialised-value warnings. By late 2001 a satisfactory |
| scheme had been arrived at, and I started to test it on ever-larger |
| programs, with an eventual eye to making it work well enough so that |
| it was helpful to folks debugging the upcoming version 3 of KDE. I've |
| used KDE since before version 1.0, and wanted to Valgrind to be an |
| indirect contribution to the KDE 3 development effort. At the start of |
| Feb 02 the kde-core-devel crew started using it, and gave a huge |
| amount of helpful feedback and patches in the space of three weeks. |
| Snapshot 20020306 is the result. |
| |
| <p> |
| In the best Unix tradition, or perhaps in the spirit of Fred Brooks' |
| depressing-but-completely-accurate epitaph "build one to throw away; |
| you will anyway", much of Valgrind is a second or third rendition of |
| the initial idea. The instrumentation machinery |
| (<code>vg_translate.c</code>, <code>vg_memory.c</code>) and core CPU |
| simulation (<code>vg_to_ucode.c</code>, <code>vg_from_ucode.c</code>) |
| have had three redesigns and rewrites; the register allocator, |
| low-level memory manager (<code>vg_malloc2.c</code>) and symbol table |
| reader (<code>vg_symtab2.c</code>) are on the second rewrite. In a |
| sense, this document serves to record some of the knowledge gained as |
| a result. |
| |
| |
| <h3>Design overview</h3> |
| |
| Valgrind is compiled into a Linux shared object, |
| <code>valgrind.so</code>, and also a dummy one, |
| <code>valgrinq.so</code>, of which more later. The |
| <code>valgrind</code> shell script adds <code>valgrind.so</code> to |
| the <code>LD_PRELOAD</code> list of extra libraries to be |
| loaded with any dynamically linked library. This is a standard trick, |
| one which I assume the <code>LD_PRELOAD</code> mechanism was developed |
| to support. |
| |
| <p> |
| <code>valgrind.so</code> |
| is linked with the <code>-z initfirst</code> flag, which requests that |
| its initialisation code is run before that of any other object in the |
| executable image. When this happens, valgrind gains control. The |
| real CPU becomes "trapped" in <code>valgrind.so</code> and the |
| translations it generates. The synthetic CPU provided by Valgrind |
| does, however, return from this initialisation function. So the |
| normal startup actions, orchestrated by the dynamic linker |
| <code>ld.so</code>, continue as usual, except on the synthetic CPU, |
| not the real one. Eventually <code>main</code> is run and returns, |
| and then the finalisation code of the shared objects is run, |
| presumably in inverse order to which they were initialised. Remember, |
| this is still all happening on the simulated CPU. Eventually |
| <code>valgrind.so</code>'s own finalisation code is called. It spots |
| this event, shuts down the simulated CPU, prints any error summaries |
| and/or does leak detection, and returns from the initialisation code |
| on the real CPU. At this point, in effect the real and synthetic CPUs |
| have merged back into one, Valgrind has lost control of the program, |
| and the program finally <code>exit()s</code> back to the kernel in the |
| usual way. |
| |
| <p> |
| The normal course of activity, one Valgrind has started up, is as |
| follows. Valgrind never runs any part of your program (usually |
| referred to as the "client"), not a single byte of it, directly. |
| Instead it uses function <code>VG_(translate)</code> to translate |
| basic blocks (BBs, straight-line sequences of code) into instrumented |
| translations, and those are run instead. The translations are stored |
| in the translation cache (TC), <code>vg_tc</code>, with the |
| translation table (TT), <code>vg_tt</code> supplying the |
| original-to-translation code address mapping. Auxiliary array |
| <code>VG_(tt_fast)</code> is used as a direct-map cache for fast |
| lookups in TT; it usually achieves a hit rate of around 98% and |
| facilitates an orig-to-trans lookup in 4 x86 insns, which is not bad. |
| |
| <p> |
| Function <code>VG_(dispatch)</code> in <code>vg_dispatch.S</code> is |
| the heart of the JIT dispatcher. Once a translated code address has |
| been found, it is executed simply by an x86 <code>call</code> |
| to the translation. At the end of the translation, the next |
| original code addr is loaded into <code>%eax</code>, and the |
| translation then does a <code>ret</code>, taking it back to the |
| dispatch loop, with, interestingly, zero branch mispredictions. |
| The address requested in <code>%eax</code> is looked up first in |
| <code>VG_(tt_fast)</code>, and, if not found, by calling C helper |
| <code>VG_(search_transtab)</code>. If there is still no translation |
| available, <code>VG_(dispatch)</code> exits back to the top-level |
| C dispatcher <code>VG_(toploop)</code>, which arranges for |
| <code>VG_(translate)</code> to make a new translation. All fairly |
| unsurprising, really. There are various complexities described below. |
| |
| <p> |
| The translator, orchestrated by <code>VG_(translate)</code>, is |
| complicated but entirely self-contained. It is described in great |
| detail in subsequent sections. Translations are stored in TC, with TT |
| tracking administrative information. The translations are subject to |
| an approximate LRU-based management scheme. With the current |
| settings, the TC can hold at most about 15MB of translations, and LRU |
| passes prune it to about 13.5MB. Given that the |
| orig-to-translation expansion ratio is about 13:1 to 14:1, this means |
| TC holds translations for more or less a megabyte of original code, |
| which generally comes to about 70000 basic blocks for C++ compiled |
| with optimisation on. Generating new translations is expensive, so it |
| is worth having a large TC to minimise the (capacity) miss rate. |
| |
| <p> |
| The dispatcher, <code>VG_(dispatch)</code>, receives hints from |
| the translations which allow it to cheaply spot all control |
| transfers corresponding to x86 <code>call</code> and <code>ret</code> |
| instructions. It has to do this in order to spot some special events: |
| <ul> |
| <li>Calls to <code>VG_(shutdown)</code>. This is Valgrind's cue to |
| exit. NOTE: actually this is done a different way; it should be |
| cleaned up. |
| <p> |
| <li>Returns of system call handlers, to the return address |
| <code>VG_(signalreturn_bogusRA)</code>. The signal simulator |
| needs to know when a signal handler is returning, so we spot |
| jumps (returns) to this address. |
| <p> |
| <li>Calls to <code>vg_trap_here</code>. All <code>malloc</code>, |
| <code>free</code>, etc calls that the client program makes are |
| eventually routed to a call to <code>vg_trap_here</code>, |
| and Valgrind does its own special thing with these calls. |
| In effect this provides a trapdoor, by which Valgrind can |
| intercept certain calls on the simulated CPU, run the call as it |
| sees fit itself (on the real CPU), and return the result to |
| the simulated CPU, quite transparently to the client program. |
| </ul> |
| Valgrind intercepts the client's <code>malloc</code>, |
| <code>free</code>, etc, |
| calls, so that it can store additional information. Each block |
| <code>malloc</code>'d by the client gives rise to a shadow block |
| in which Valgrind stores the call stack at the time of the |
| <code>malloc</code> |
| call. When the client calls <code>free</code>, Valgrind tries to |
| find the shadow block corresponding to the address passed to |
| <code>free</code>, and emits an error message if none can be found. |
| If it is found, the block is placed on the freed blocks queue |
| <code>vg_freed_list</code>, it is marked as inaccessible, and |
| its shadow block now records the call stack at the time of the |
| <code>free</code> call. Keeping <code>free</code>'d blocks in |
| this queue allows Valgrind to spot all (presumably invalid) accesses |
| to them. However, once the volume of blocks in the free queue |
| exceeds <code>VG_(clo_freelist_vol)</code>, blocks are finally |
| removed from the queue. |
| |
| <p> |
| Keeping track of A and V bits (note: if you don't know what these are, |
| you haven't read the user guide carefully enough) for memory is done |
| in <code>vg_memory.c</code>. This implements a sparse array structure |
| which covers the entire 4G address space in a way which is reasonably |
| fast and reasonably space efficient. The 4G address space is divided |
| up into 64K sections, each covering 64Kb of address space. Given a |
| 32-bit address, the top 16 bits are used to select one of the 65536 |
| entries in <code>VG_(primary_map)</code>. The resulting "secondary" |
| (<code>SecMap</code>) holds A and V bits for the 64k of address space |
| chunk corresponding to the lower 16 bits of the address. |
| |
| |
| <h3>Design decisions</h3> |
| |
| Some design decisions were motivated by the need to make Valgrind |
| debuggable. Imagine you are writing a CPU simulator. It works fairly |
| well. However, you run some large program, like Netscape, and after |
| tens of millions of instructions, it crashes. How can you figure out |
| where in your simulator the bug is? |
| |
| <p> |
| Valgrind's answer is: cheat. Valgrind is designed so that it is |
| possible to switch back to running the client program on the real |
| CPU at any point. Using the <code>--stop-after= </code> flag, you can |
| ask Valgrind to run just some number of basic blocks, and then |
| run the rest of the way on the real CPU. If you are searching for |
| a bug in the simulated CPU, you can use this to do a binary search, |
| which quickly leads you to the specific basic block which is |
| causing the problem. |
| |
| <p> |
| This is all very handy. It does constrain the design in certain |
| unimportant ways. Firstly, the layout of memory, when viewed from the |
| client's point of view, must be identical regardless of whether it is |
| running on the real or simulated CPU. This means that Valgrind can't |
| do pointer swizzling -- well, no great loss -- and it can't run on |
| the same stack as the client -- again, no great loss. |
| Valgrind operates on its own stack, <code>VG_(stack)</code>, which |
| it switches to at startup, temporarily switching back to the client's |
| stack when doing system calls for the client. |
| |
| <p> |
| Valgrind also receives signals on its own stack, |
| <code>VG_(sigstack)</code>, but for different gruesome reasons |
| discussed below. |
| |
| <p> |
| This nice clean switch-back-to-the-real-CPU-whenever-you-like story |
| is muddied by signals. Problem is that signals arrive at arbitrary |
| times and tend to slightly perturb the basic block count, with the |
| result that you can get close to the basic block causing a problem but |
| can't home in on it exactly. My kludgey hack is to define |
| <code>SIGNAL_SIMULATION</code> to 1 towards the bottom of |
| <code>vg_syscall_mem.c</code>, so that signal handlers are run on the |
| real CPU and don't change the BB counts. |
| |
| <p> |
| A second hole in the switch-back-to-real-CPU story is that Valgrind's |
| way of delivering signals to the client is different from that of the |
| kernel. Specifically, the layout of the signal delivery frame, and |
| the mechanism used to detect a sighandler returning, are different. |
| So you can't expect to make the transition inside a sighandler and |
| still have things working, but in practice that's not much of a |
| restriction. |
| |
| <p> |
| Valgrind's implementation of <code>malloc</code>, <code>free</code>, |
| etc, (in <code>vg_clientmalloc.c</code>, not the low-level stuff in |
| <code>vg_malloc2.c</code>) is somewhat complicated by the need to |
| handle switching back at arbitrary points. It does work tho. |
| |
| |
| |
| <h3>Correctness</h3> |
| |
| There's only one of me, and I have a Real Life (tm) as well as hacking |
| Valgrind [allegedly :-]. That means I don't have time to waste |
| chasing endless bugs in Valgrind. My emphasis is therefore on doing |
| everything as simply as possible, with correctness, stability and |
| robustness being the number one priority, more important than |
| performance or functionality. As a result: |
| <ul> |
| <li>The code is absolutely loaded with assertions, and these are |
| <b>permanently enabled.</b> I have no plan to remove or disable |
| them later. Over the past couple of months, as valgrind has |
| become more widely used, they have shown their worth, pulling |
| up various bugs which would otherwise have appeared as |
| hard-to-find segmentation faults. |
| <p> |
| I am of the view that it's acceptable to spend 5% of the total |
| running time of your valgrindified program doing assertion checks |
| and other internal sanity checks. |
| <p> |
| <li>Aside from the assertions, valgrind contains various sets of |
| internal sanity checks, which get run at varying frequencies |
| during normal operation. <code>VG_(do_sanity_checks)</code> |
| runs every 1000 basic blocks, which means 500 to 2000 times/second |
| for typical machines at present. It checks that Valgrind hasn't |
| overrun its private stack, and does some simple checks on the |
| memory permissions maps. Once every 25 calls it does some more |
| extensive checks on those maps. Etc, etc. |
| <p> |
| The following components also have sanity check code, which can |
| be enabled to aid debugging: |
| <ul> |
| <li>The low-level memory-manager |
| (<code>VG_(mallocSanityCheckArena)</code>). This does a |
| complete check of all blocks and chains in an arena, which |
| is very slow. Is not engaged by default. |
| <p> |
| <li>The symbol table reader(s): various checks to ensure |
| uniqueness of mappings; see <code>VG_(read_symbols)</code> |
| for a start. Is permanently engaged. |
| <p> |
| <li>The A and V bit tracking stuff in <code>vg_memory.c</code>. |
| This can be compiled with cpp symbol |
| <code>VG_DEBUG_MEMORY</code> defined, which removes all the |
| fast, optimised cases, and uses simple-but-slow fallbacks |
| instead. Not engaged by default. |
| <p> |
| <li>Ditto <code>VG_DEBUG_LEAKCHECK</code>. |
| <p> |
| <li>The JITter parses x86 basic blocks into sequences of |
| UCode instructions. It then sanity checks each one with |
| <code>VG_(saneUInstr)</code> and sanity checks the sequence |
| as a whole with <code>VG_(saneUCodeBlock)</code>. This stuff |
| is engaged by default, and has caught some way-obscure bugs |
| in the simulated CPU machinery in its time. |
| <p> |
| <li>The system call wrapper does |
| <code>VG_(first_and_last_secondaries_look_plausible)</code> after |
| every syscall; this is known to pick up bugs in the syscall |
| wrappers. Engaged by default. |
| <p> |
| <li>The main dispatch loop, in <code>VG_(dispatch)</code>, checks |
| that translations do not set <code>%ebp</code> to any value |
| different from <code>VG_EBP_DISPATCH_CHECKED</code> or |
| <code>& VG_(baseBlock)</code>. In effect this test is free, |
| and is permanently engaged. |
| <p> |
| <li>There are a couple of ifdefed-out consistency checks I |
| inserted whilst debugging the new register allocater, |
| <code>vg_do_register_allocation</code>. |
| </ul> |
| <p> |
| <li>I try to avoid techniques, algorithms, mechanisms, etc, for which |
| I can supply neither a convincing argument that they are correct, |
| nor sanity-check code which might pick up bugs in my |
| implementation. I don't always succeed in this, but I try. |
| Basically the idea is: avoid techniques which are, in practice, |
| unverifiable, in some sense. When doing anything, always have in |
| mind: "how can I verify that this is correct?" |
| </ul> |
| |
| <p> |
| Some more specific things are: |
| |
| <ul> |
| <li>Valgrind runs in the same namespace as the client, at least from |
| <code>ld.so</code>'s point of view, and it therefore absolutely |
| had better not export any symbol with a name which could clash |
| with that of the client or any of its libraries. Therefore, all |
| globally visible symbols exported from <code>valgrind.so</code> |
| are defined using the <code>VG_</code> CPP macro. As you'll see |
| from <code>vg_constants.h</code>, this appends some arbitrary |
| prefix to the symbol, in order that it be, we hope, globally |
| unique. Currently the prefix is <code>vgPlain_</code>. For |
| convenience there are also <code>VGM_</code>, <code>VGP_</code> |
| and <code>VGOFF_</code>. All locally defined symbols are declared |
| <code>static</code> and do not appear in the final shared object. |
| <p> |
| To check this, I periodically do |
| <code>nm valgrind.so | grep " T "</code>, |
| which shows you all the globally exported text symbols. |
| They should all have an approved prefix, except for those like |
| <code>malloc</code>, <code>free</code>, etc, which we deliberately |
| want to shadow and take precedence over the same names exported |
| from <code>glibc.so</code>, so that valgrind can intercept those |
| calls easily. Similarly, <code>nm valgrind.so | grep " D "</code> |
| allows you to find any rogue data-segment symbol names. |
| <p> |
| <li>Valgrind tries, and almost succeeds, in being completely |
| independent of all other shared objects, in particular of |
| <code>glibc.so</code>. For example, we have our own low-level |
| memory manager in <code>vg_malloc2.c</code>, which is a fairly |
| standard malloc/free scheme augmented with arenas, and |
| <code>vg_mylibc.c</code> exports reimplementations of various bits |
| and pieces you'd normally get from the C library. |
| <p> |
| Why all the hassle? Because imagine the potential chaos of both |
| the simulated and real CPUs executing in <code>glibc.so</code>. |
| It just seems simpler and cleaner to be completely self-contained, |
| so that only the simulated CPU visits <code>glibc.so</code>. In |
| practice it's not much hassle anyway. Also, valgrind starts up |
| before glibc has a chance to initialise itself, and who knows what |
| difficulties that could lead to. Finally, glibc has definitions |
| for some types, specifically <code>sigset_t</code>, which conflict |
| (are different from) the Linux kernel's idea of same. When |
| Valgrind wants to fiddle around with signal stuff, it wants to |
| use the kernel's definitions, not glibc's definitions. So it's |
| simplest just to keep glibc out of the picture entirely. |
| <p> |
| To find out which glibc symbols are used by Valgrind, reinstate |
| the link flags <code>-nostdlib -Wl,-no-undefined</code>. This |
| causes linking to fail, but will tell you what you depend on. |
| I have mostly, but not entirely, got rid of the glibc |
| dependencies; what remains is, IMO, fairly harmless. AFAIK the |
| current dependencies are: <code>memset</code>, |
| <code>memcmp</code>, <code>stat</code>, <code>system</code>, |
| <code>sbrk</code>, <code>setjmp</code> and <code>longjmp</code>. |
| |
| <p> |
| <li>Similarly, valgrind should not really import any headers other |
| than the Linux kernel headers, since it knows of no API other than |
| the kernel interface to talk to. At the moment this is really not |
| in a good state, and <code>vg_syscall_mem</code> imports, via |
| <code>vg_unsafe.h</code>, a significant number of C-library |
| headers so as to know the sizes of various structs passed across |
| the kernel boundary. This is of course completely bogus, since |
| there is no guarantee that the C library's definitions of these |
| structs matches those of the kernel. I have started to sort this |
| out using <code>vg_kerneliface.h</code>, into which I had intended |
| to copy all kernel definitions which valgrind could need, but this |
| has not gotten very far. At the moment it mostly contains |
| definitions for <code>sigset_t</code> and <code>struct |
| sigaction</code>, since the kernel's definition for these really |
| does clash with glibc's. I plan to use a <code>vki_</code> prefix |
| on all these types and constants, to denote the fact that they |
| pertain to <b>V</b>algrind's <b>K</b>ernel <b>I</b>nterface. |
| <p> |
| Another advantage of having a <code>vg_kerneliface.h</code> file |
| is that it makes it simpler to interface to a different kernel. |
| Once can, for example, easily imagine writing a new |
| <code>vg_kerneliface.h</code> for FreeBSD, or x86 NetBSD. |
| |
| </ul> |
| |
| <h3>Current limitations</h3> |
| |
| No threads. I think fixing this is close to a research-grade problem. |
| <p> |
| No MMX. Fixing this should be relatively easy, using the same giant |
| trick used for x86 FPU instructions. See below. |
| <p> |
| Support for weird (non-POSIX) signal stuff is patchy. Does anybody |
| care? |
| <p> |
| |
| |
| |
| |
| <hr width="100%"> |
| |
| <h2>The instrumenting JITter</h2> |
| |
| This really is the heart of the matter. We begin with various side |
| issues. |
| |
| <h3>Run-time storage, and the use of host registers</h3> |
| |
| Valgrind translates client (original) basic blocks into instrumented |
| basic blocks, which live in the translation cache TC, until either the |
| client finishes or the translations are ejected from TC to make room |
| for newer ones. |
| <p> |
| Since it generates x86 code in memory, Valgrind has complete control |
| of the use of registers in the translations. Now pay attention. I |
| shall say this only once, and it is important you understand this. In |
| what follows I will refer to registers in the host (real) cpu using |
| their standard names, <code>%eax</code>, <code>%edi</code>, etc. I |
| refer to registers in the simulated CPU by capitalising them: |
| <code>%EAX</code>, <code>%EDI</code>, etc. These two sets of |
| registers usually bear no direct relationship to each other; there is |
| no fixed mapping between them. This naming scheme is used fairly |
| consistently in the comments in the sources. |
| <p> |
| Host registers, once things are up and running, are used as follows: |
| <ul> |
| <li><code>%esp</code>, the real stack pointer, points |
| somewhere in Valgrind's private stack area, |
| <code>VG_(stack)</code> or, transiently, into its signal delivery |
| stack, <code>VG_(sigstack)</code>. |
| <p> |
| <li><code>%edi</code> is used as a temporary in code generation; it |
| is almost always dead, except when used for the <code>Left</code> |
| value-tag operations. |
| <p> |
| <li><code>%eax</code>, <code>%ebx</code>, <code>%ecx</code>, |
| <code>%edx</code> and <code>%esi</code> are available to |
| Valgrind's register allocator. They are dead (carry unimportant |
| values) in between translations, and are live only in |
| translations. The one exception to this is <code>%eax</code>, |
| which, as mentioned far above, has a special significance to the |
| dispatch loop <code>VG_(dispatch)</code>: when a translation |
| returns to the dispatch loop, <code>%eax</code> is expected to |
| contain the original-code-address of the next translation to run. |
| The register allocator is so good at minimising spill code that |
| using five regs and not having to save/restore <code>%edi</code> |
| actually gives better code than allocating to <code>%edi</code> |
| as well, but then having to push/pop it around special uses. |
| <p> |
| <li><code>%ebp</code> points permanently at |
| <code>VG_(baseBlock)</code>. Valgrind's translations are |
| position-independent, partly because this is convenient, but also |
| because translations get moved around in TC as part of the LRUing |
| activity. <b>All</b> static entities which need to be referred to |
| from generated code, whether data or helper functions, are stored |
| starting at <code>VG_(baseBlock)</code> and are therefore reached |
| by indexing from <code>%ebp</code>. There is but one exception, |
| which is that by placing the value |
| <code>VG_EBP_DISPATCH_CHECKED</code> |
| in <code>%ebp</code> just before a return to the dispatcher, |
| the dispatcher is informed that the next address to run, |
| in <code>%eax</code>, requires special treatment. |
| <p> |
| <li>The real machine's FPU state is pretty much unimportant, for |
| reasons which will become obvious. Ditto its <code>%eflags</code> |
| register. |
| </ul> |
| |
| <p> |
| The state of the simulated CPU is stored in memory, in |
| <code>VG_(baseBlock)</code>, which is a block of 200 words IIRC. |
| Recall that <code>%ebp</code> points permanently at the start of this |
| block. Function <code>vg_init_baseBlock</code> decides what the |
| offsets of various entities in <code>VG_(baseBlock)</code> are to be, |
| and allocates word offsets for them. The code generator then emits |
| <code>%ebp</code> relative addresses to get at those things. The |
| sequence in which entities are allocated has been carefully chosen so |
| that the 32 most popular entities come first, because this means 8-bit |
| offsets can be used in the generated code. |
| |
| <p> |
| If I was clever, I could make <code>%ebp</code> point 32 words along |
| <code>VG_(baseBlock)</code>, so that I'd have another 32 words of |
| short-form offsets available, but that's just complicated, and it's |
| not important -- the first 32 words take 99% (or whatever) of the |
| traffic. |
| |
| <p> |
| Currently, the sequence of stuff in <code>VG_(baseBlock)</code> is as |
| follows: |
| <ul> |
| <li>9 words, holding the simulated integer registers, |
| <code>%EAX</code> .. <code>%EDI</code>, and the simulated flags, |
| <code>%EFLAGS</code>. |
| <p> |
| <li>Another 9 words, holding the V bit "shadows" for the above 9 regs. |
| <p> |
| <li>The <b>addresses</b> of various helper routines called from |
| generated code: |
| <code>VG_(helper_value_check4_fail)</code>, |
| <code>VG_(helper_value_check0_fail)</code>, |
| which register V-check failures, |
| <code>VG_(helperc_STOREV4)</code>, |
| <code>VG_(helperc_STOREV1)</code>, |
| <code>VG_(helperc_LOADV4)</code>, |
| <code>VG_(helperc_LOADV1)</code>, |
| which do stores and loads of V bits to/from the |
| sparse array which keeps track of V bits in memory, |
| and |
| <code>VGM_(handle_esp_assignment)</code>, which messes with |
| memory addressibility resulting from changes in <code>%ESP</code>. |
| <p> |
| <li>The simulated <code>%EIP</code>. |
| <p> |
| <li>24 spill words, for when the register allocator can't make it work |
| with 5 measly registers. |
| <p> |
| <li>Addresses of helpers <code>VG_(helperc_STOREV2)</code>, |
| <code>VG_(helperc_LOADV2)</code>. These are here because 2-byte |
| loads and stores are relatively rare, so are placed above the |
| magic 32-word offset boundary. |
| <p> |
| <li>For similar reasons, addresses of helper functions |
| <code>VGM_(fpu_write_check)</code> and |
| <code>VGM_(fpu_read_check)</code>, which handle the A/V maps |
| testing and changes required by FPU writes/reads. |
| <p> |
| <li>Some other boring helper addresses: |
| <code>VG_(helper_value_check2_fail)</code> and |
| <code>VG_(helper_value_check1_fail)</code>. These are probably |
| never emitted now, and should be removed. |
| <p> |
| <li>The entire state of the simulated FPU, which I believe to be |
| 108 bytes long. |
| <p> |
| <li>Finally, the addresses of various other helper functions in |
| <code>vg_helpers.S</code>, which deal with rare situations which |
| are tedious or difficult to generate code in-line for. |
| </ul> |
| |
| <p> |
| As a general rule, the simulated machine's state lives permanently in |
| memory at <code>VG_(baseBlock)</code>. However, the JITter does some |
| optimisations which allow the simulated integer registers to be |
| cached in real registers over multiple simulated instructions within |
| the same basic block. These are always flushed back into memory at |
| the end of every basic block, so that the in-memory state is |
| up-to-date between basic blocks. (This flushing is implied by the |
| statement above that the real machine's allocatable registers are |
| dead in between simulated blocks). |
| |
| |
| <h3>Startup, shutdown, and system calls</h3> |
| |
| Getting into of Valgrind (<code>VG_(startup)</code>, called from |
| <code>valgrind.so</code>'s initialisation section), really means |
| copying the real CPU's state into <code>VG_(baseBlock)</code>, and |
| then installing our own stack pointer, etc, into the real CPU, and |
| then starting up the JITter. Exiting valgrind involves copying the |
| simulated state back to the real state. |
| |
| <p> |
| Unfortunately, there's a complication at startup time. Problem is |
| that at the point where we need to take a snapshot of the real CPU's |
| state, the offsets in <code>VG_(baseBlock)</code> are not set up yet, |
| because to do so would involve disrupting the real machine's state |
| significantly. The way round this is to dump the real machine's state |
| into a temporary, static block of memory, |
| <code>VG_(m_state_static)</code>. We can then set up the |
| <code>VG_(baseBlock)</code> offsets at our leisure, and copy into it |
| from <code>VG_(m_state_static)</code> at some convenient later time. |
| This copying is done by |
| <code>VG_(copy_m_state_static_to_baseBlock)</code>. |
| |
| <p> |
| On exit, the inverse transformation is (rather unnecessarily) used: |
| stuff in <code>VG_(baseBlock)</code> is copied to |
| <code>VG_(m_state_static)</code>, and the assembly stub then copies |
| from <code>VG_(m_state_static)</code> into the real machine registers. |
| |
| <p> |
| Doing system calls on behalf of the client (<code>vg_syscall.S</code>) |
| is something of a half-way house. We have to make the world look |
| sufficiently like that which the client would normally have to make |
| the syscall actually work properly, but we can't afford to lose |
| control. So the trick is to copy all of the client's state, <b>except |
| its program counter</b>, into the real CPU, do the system call, and |
| copy the state back out. Note that the client's state includes its |
| stack pointer register, so one effect of this partial restoration is |
| to cause the system call to be run on the client's stack, as it should |
| be. |
| |
| <p> |
| As ever there are complications. We have to save some of our own state |
| somewhere when restoring the client's state into the CPU, so that we |
| can keep going sensibly afterwards. In fact the only thing which is |
| important is our own stack pointer, but for paranoia reasons I save |
| and restore our own FPU state as well, even though that's probably |
| pointless. |
| |
| <p> |
| The complication on the above complication is, that for horrible |
| reasons to do with signals, we may have to handle a second client |
| system call whilst the client is blocked inside some other system |
| call (unbelievable!). That means there's two sets of places to |
| dump Valgrind's stack pointer and FPU state across the syscall, |
| and we decide which to use by consulting |
| <code>VG_(syscall_depth)</code>, which is in turn maintained by |
| <code>VG_(wrap_syscall)</code>. |
| |
| |
| |
| <h3>Introduction to UCode</h3> |
| |
| UCode lies at the heart of the x86-to-x86 JITter. The basic premise |
| is that dealing the the x86 instruction set head-on is just too darn |
| complicated, so we do the traditional compiler-writer's trick and |
| translate it into a simpler, easier-to-deal-with form. |
| |
| <p> |
| In normal operation, translation proceeds through six stages, |
| coordinated by <code>VG_(translate)</code>: |
| <ol> |
| <li>Parsing of an x86 basic block into a sequence of UCode |
| instructions (<code>VG_(disBB)</code>). |
| <p> |
| <li>UCode optimisation (<code>vg_improve</code>), with the aim of |
| caching simulated registers in real registers over multiple |
| simulated instructions, and removing redundant simulated |
| <code>%EFLAGS</code> saving/restoring. |
| <p> |
| <li>UCode instrumentation (<code>vg_instrument</code>), which adds |
| value and address checking code. |
| <p> |
| <li>Post-instrumentation cleanup (<code>vg_cleanup</code>), removing |
| redundant value-check computations. |
| <p> |
| <li>Register allocation (<code>vg_do_register_allocation</code>), |
| which, note, is done on UCode. |
| <p> |
| <li>Emission of final instrumented x86 code |
| (<code>VG_(emit_code)</code>). |
| </ol> |
| |
| <p> |
| Notice how steps 2, 3, 4 and 5 are simple UCode-to-UCode |
| transformation passes, all on straight-line blocks of UCode (type |
| <code>UCodeBlock</code>). Steps 2 and 4 are optimisation passes and |
| can be disabled for debugging purposes, with |
| <code>--optimise=no</code> and <code>--cleanup=no</code> respectively. |
| |
| <p> |
| Valgrind can also run in a no-instrumentation mode, given |
| <code>--instrument=no</code>. This is useful for debugging the JITter |
| quickly without having to deal with the complexity of the |
| instrumentation mechanism too. In this mode, steps 3 and 4 are |
| omitted. |
| |
| <p> |
| These flags combine, so that <code>--instrument=no</code> together with |
| <code>--optimise=no</code> means only steps 1, 5 and 6 are used. |
| <code>--single-step=yes</code> causes each x86 instruction to be |
| treated as a single basic block. The translations are terrible but |
| this is sometimes instructive. |
| |
| <p> |
| The <code>--stop-after=N</code> flag switches back to the real CPU |
| after <code>N</code> basic blocks. It also re-JITs the final basic |
| block executed and prints the debugging info resulting, so this |
| gives you a way to get a quick snapshot of how a basic block looks as |
| it passes through the six stages mentioned above. If you want to |
| see full information for every block translated (probably not, but |
| still ...) find, in <code>VG_(translate)</code>, the lines |
| <br><code> dis = True;</code> |
| <br><code> dis = debugging_translation;</code> |
| <br> |
| and comment out the second line. This will spew out debugging |
| junk faster than you can possibly imagine. |
| |
| |
| |
| <h3>UCode operand tags: type <code>Tag</code></h3> |
| |
| UCode is, more or less, a simple two-address RISC-like code. In |
| keeping with the x86 AT&T assembly syntax, generally speaking the |
| first operand is the source operand, and the second is the destination |
| operand, which is modified when the uinstr is notionally executed. |
| |
| <p> |
| UCode instructions have up to three operand fields, each of which has |
| a corresponding <code>Tag</code> describing it. Possible values for |
| the tag are: |
| |
| <ul> |
| <li><code>NoValue</code>: indicates that the field is not in use. |
| <p> |
| <li><code>Lit16</code>: the field contains a 16-bit literal. |
| <p> |
| <li><code>Literal</code>: the field denotes a 32-bit literal, whose |
| value is stored in the <code>lit32</code> field of the uinstr |
| itself. Since there is only one <code>lit32</code> for the whole |
| uinstr, only one operand field may contain this tag. |
| <p> |
| <li><code>SpillNo</code>: the field contains a spill slot number, in |
| the range 0 to 23 inclusive, denoting one of the spill slots |
| contained inside <code>VG_(baseBlock)</code>. Such tags only |
| exist after register allocation. |
| <p> |
| <li><code>RealReg</code>: the field contains a number in the range 0 |
| to 7 denoting an integer x86 ("real") register on the host. The |
| number is the Intel encoding for integer registers. Such tags |
| only exist after register allocation. |
| <p> |
| <li><code>ArchReg</code>: the field contains a number in the range 0 |
| to 7 denoting an integer x86 register on the simulated CPU. In |
| reality this means a reference to one of the first 8 words of |
| <code>VG_(baseBlock)</code>. Such tags can exist at any point in |
| the translation process. |
| <p> |
| <li>Last, but not least, <code>TempReg</code>. The field contains the |
| number of one of an infinite set of virtual (integer) |
| registers. <code>TempReg</code>s are used everywhere throughout |
| the translation process; you can have as many as you want. The |
| register allocator maps as many as it can into |
| <code>RealReg</code>s and turns the rest into |
| <code>SpillNo</code>s, so <code>TempReg</code>s should not exist |
| after the register allocation phase. |
| <p> |
| <code>TempReg</code>s are always 32 bits long, even if the data |
| they hold is logically shorter. In that case the upper unused |
| bits are required, and, I think, generally assumed, to be zero. |
| <code>TempReg</code>s holding V bits for quantities shorter than |
| 32 bits are expected to have ones in the unused places, since a |
| one denotes "undefined". |
| </ul> |
| |
| |
| <h3>UCode instructions: type <code>UInstr</code></h3> |
| |
| <p> |
| UCode was carefully designed to make it possible to do register |
| allocation on UCode and then translate the result into x86 code |
| without needing any extra registers ... well, that was the original |
| plan, anyway. Things have gotten a little more complicated since |
| then. In what follows, UCode instructions are referred to as uinstrs, |
| to distinguish them from x86 instructions. Uinstrs of course have |
| uopcodes which are (naturally) different from x86 opcodes. |
| |
| <p> |
| A uinstr (type <code>UInstr</code>) contains |
| various fields, not all of which are used by any one uopcode: |
| <ul> |
| <li>Three 16-bit operand fields, <code>val1</code>, <code>val2</code> |
| and <code>val3</code>. |
| <p> |
| <li>Three tag fields, <code>tag1</code>, <code>tag2</code> |
| and <code>tag3</code>. Each of these has a value of type |
| <code>Tag</code>, |
| and they describe what the <code>val1</code>, <code>val2</code> |
| and <code>val3</code> fields contain. |
| <p> |
| <li>A 32-bit literal field. |
| <p> |
| <li>Two <code>FlagSet</code>s, specifying which x86 condition codes are |
| read and written by the uinstr. |
| <p> |
| <li>An opcode byte, containing a value of type <code>Opcode</code>. |
| <p> |
| <li>A size field, indicating the data transfer size (1/2/4/8/10) in |
| cases where this makes sense, or zero otherwise. |
| <p> |
| <li>A condition-code field, which, for jumps, holds a |
| value of type <code>Condcode</code>, indicating the condition |
| which applies. The encoding is as it is in the x86 insn stream, |
| except we add a 17th value <code>CondAlways</code> to indicate |
| an unconditional transfer. |
| <p> |
| <li>Various 1-bit flags, indicating whether this insn pertains to an |
| x86 CALL or RET instruction, whether a widening is signed or not, |
| etc. |
| </ul> |
| |
| <p> |
| UOpcodes (type <code>Opcode</code>) are divided into two groups: those |
| necessary merely to express the functionality of the x86 code, and |
| extra uopcodes needed to express the instrumentation. The former |
| group contains: |
| <ul> |
| <li><code>GET</code> and <code>PUT</code>, which move values from the |
| simulated CPU's integer registers (<code>ArchReg</code>s) into |
| <code>TempReg</code>s, and back. <code>GETF</code> and |
| <code>PUTF</code> do the corresponding thing for the simulated |
| <code>%EFLAGS</code>. There are no corresponding insns for the |
| FPU register stack, since we don't explicitly simulate its |
| registers. |
| <p> |
| <li><code>LOAD</code> and <code>STORE</code>, which, in RISC-like |
| fashion, are the only uinstrs able to interact with memory. |
| <p> |
| <li><code>MOV</code> and <code>CMOV</code> allow unconditional and |
| conditional moves of values between <code>TempReg</code>s. |
| <p> |
| <li>ALU operations. Again in RISC-like fashion, these only operate on |
| <code>TempReg</code>s (before reg-alloc) or <code>RealReg</code>s |
| (after reg-alloc). These are: <code>ADD</code>, <code>ADC</code>, |
| <code>AND</code>, <code>OR</code>, <code>XOR</code>, |
| <code>SUB</code>, <code>SBB</code>, <code>SHL</code>, |
| <code>SHR</code>, <code>SAR</code>, <code>ROL</code>, |
| <code>ROR</code>, <code>RCL</code>, <code>RCR</code>, |
| <code>NOT</code>, <code>NEG</code>, <code>INC</code>, |
| <code>DEC</code>, <code>BSWAP</code>, <code>CC2VAL</code> and |
| <code>WIDEN</code>. <code>WIDEN</code> does signed or unsigned |
| value widening. <code>CC2VAL</code> is used to convert condition |
| codes into a value, zero or one. The rest are obvious. |
| <p> |
| To allow for more efficient code generation, we bend slightly the |
| restriction at the start of the previous para: for |
| <code>ADD</code>, <code>ADC</code>, <code>XOR</code>, |
| <code>SUB</code> and <code>SBB</code>, we allow the first (source) |
| operand to also be an <code>ArchReg</code>, that is, one of the |
| simulated machine's registers. Also, many of these ALU ops allow |
| the source operand to be a literal. See |
| <code>VG_(saneUInstr)</code> for the final word on the allowable |
| forms of uinstrs. |
| <p> |
| <li><code>LEA1</code> and <code>LEA2</code> are not strictly |
| necessary, but allow faciliate better translations. They |
| record the fancy x86 addressing modes in a direct way, which |
| allows those amodes to be emitted back into the final |
| instruction stream more or less verbatim. |
| <p> |
| <li><code>CALLM</code> calls a machine-code helper, one of the methods |
| whose address is stored at some <code>VG_(baseBlock)</code> |
| offset. <code>PUSH</code> and <code>POP</code> move values |
| to/from <code>TempReg</code> to the real (Valgrind's) stack, and |
| <code>CLEAR</code> removes values from the stack. |
| <code>CALLM_S</code> and <code>CALLM_E</code> delimit the |
| boundaries of call setups and clearings, for the benefit of the |
| instrumentation passes. Getting this right is critical, and so |
| <code>VG_(saneUCodeBlock)</code> makes various checks on the use |
| of these uopcodes. |
| <p> |
| It is important to understand that these uopcodes have nothing to |
| do with the x86 <code>call</code>, <code>return,</code> |
| <code>push</code> or <code>pop</code> instructions, and are not |
| used to implement them. Those guys turn into combinations of |
| <code>GET</code>, <code>PUT</code>, <code>LOAD</code>, |
| <code>STORE</code>, <code>ADD</code>, <code>SUB</code>, and |
| <code>JMP</code>. What these uopcodes support is calling of |
| helper functions such as <code>VG_(helper_imul_32_64)</code>, |
| which do stuff which is too difficult or tedious to emit inline. |
| <p> |
| <li><code>FPU</code>, <code>FPU_R</code> and <code>FPU_W</code>. |
| Valgrind doesn't attempt to simulate the internal state of the |
| FPU at all. Consequently it only needs to be able to distinguish |
| FPU ops which read and write memory from those that don't, and |
| for those which do, it needs to know the effective address and |
| data transfer size. This is made easier because the x86 FP |
| instruction encoding is very regular, basically consisting of |
| 16 bits for a non-memory FPU insn and 11 (IIRC) bits + an address mode |
| for a memory FPU insn. So our <code>FPU</code> uinstr carries |
| the 16 bits in its <code>val1</code> field. And |
| <code>FPU_R</code> and <code>FPU_W</code> carry 11 bits in that |
| field, together with the identity of a <code>TempReg</code> or |
| (later) <code>RealReg</code> which contains the address. |
| <p> |
| <li><code>JIFZ</code> is unique, in that it allows a control-flow |
| transfer which is not deemed to end a basic block. It causes a |
| jump to a literal (original) address if the specified argument |
| is zero. |
| <p> |
| <li>Finally, <code>INCEIP</code> advances the simulated |
| <code>%EIP</code> by the specified literal amount. This supports |
| lazy <code>%EIP</code> updating, as described below. |
| </ul> |
| |
| <p> |
| Stages 1 and 2 of the 6-stage translation process mentioned above |
| deal purely with these uopcodes, and no others. They are |
| sufficient to express pretty much all the x86 32-bit protected-mode |
| instruction set, at |
| least everything understood by a pre-MMX original Pentium (P54C). |
| |
| <p> |
| Stages 3, 4, 5 and 6 also deal with the following extra |
| "instrumentation" uopcodes. They are used to express all the |
| definedness-tracking and -checking machinery which valgrind does. In |
| later sections we show how to create checking code for each of the |
| uopcodes above. Note that these instrumentation uopcodes, although |
| some appearing complicated, have been carefully chosen so that |
| efficient x86 code can be generated for them. GNU superopt v2.5 did a |
| great job helping out here. Anyways, the uopcodes are as follows: |
| |
| <ul> |
| <li><code>GETV</code> and <code>PUTV</code> are analogues to |
| <code>GET</code> and <code>PUT</code> above. They are identical |
| except that they move the V bits for the specified values back and |
| forth to <code>TempRegs</code>, rather than moving the values |
| themselves. |
| <p> |
| <li>Similarly, <code>LOADV</code> and <code>STOREV</code> read and |
| write V bits from the synthesised shadow memory that Valgrind |
| maintains. In fact they do more than that, since they also do |
| address-validity checks, and emit complaints if the read/written |
| addresses are unaddressible. |
| <p> |
| <li><code>TESTV</code>, whose parameters are a <code>TempReg</code> |
| and a size, tests the V bits in the <code>TempReg</code>, at the |
| specified operation size (0/1/2/4 byte) and emits an error if any |
| of them indicate undefinedness. This is the only uopcode capable |
| of doing such tests. |
| <p> |
| <li><code>SETV</code>, whose parameters are also <code>TempReg</code> |
| and a size, makes the V bits in the <code>TempReg</code> indicated |
| definedness, at the specified operation size. This is usually |
| used to generate the correct V bits for a literal value, which is |
| of course fully defined. |
| <p> |
| <li><code>GETVF</code> and <code>PUTVF</code> are analogues to |
| <code>GETF</code> and <code>PUTF</code>. They move the single V |
| bit used to model definedness of <code>%EFLAGS</code> between its |
| home in <code>VG_(baseBlock)</code> and the specified |
| <code>TempReg</code>. |
| <p> |
| <li><code>TAG1</code> denotes one of a family of unary operations on |
| <code>TempReg</code>s containing V bits. Similarly, |
| <code>TAG2</code> denotes one in a family of binary operations on |
| V bits. |
| </ul> |
| |
| <p> |
| These 10 uopcodes are sufficient to express Valgrind's entire |
| definedness-checking semantics. In fact most of the interesting magic |
| is done by the <code>TAG1</code> and <code>TAG2</code> |
| suboperations. |
| |
| <p> |
| First, however, I need to explain about V-vector operation sizes. |
| There are 4 sizes: 1, 2 and 4, which operate on groups of 8, 16 and 32 |
| V bits at a time, supporting the usual 1, 2 and 4 byte x86 operations. |
| However there is also the mysterious size 0, which really means a |
| single V bit. Single V bits are used in various circumstances; in |
| particular, the definedness of <code>%EFLAGS</code> is modelled with a |
| single V bit. Now might be a good time to also point out that for |
| V bits, 1 means "undefined" and 0 means "defined". Similarly, for A |
| bits, 1 means "invalid address" and 0 means "valid address". This |
| seems counterintuitive (and so it is), but testing against zero on |
| x86s saves instructions compared to testing against all 1s, because |
| many ALU operations set the Z flag for free, so to speak. |
| |
| <p> |
| With that in mind, the tag ops are: |
| |
| <ul> |
| <li><b>(UNARY) Pessimising casts</b>: <code>VgT_PCast40</code>, |
| <code>VgT_PCast20</code>, <code>VgT_PCast10</code>, |
| <code>VgT_PCast01</code>, <code>VgT_PCast02</code> and |
| <code>VgT_PCast04</code>. A "pessimising cast" takes a V-bit |
| vector at one size, and creates a new one at another size, |
| pessimised in the sense that if any of the bits in the source |
| vector indicate undefinedness, then all the bits in the result |
| indicate undefinedness. In this case the casts are all to or from |
| a single V bit, so for example <code>VgT_PCast40</code> is a |
| pessimising cast from 32 bits to 1, whereas |
| <code>VgT_PCast04</code> simply copies the single source V bit |
| into all 32 bit positions in the result. Surprisingly, these ops |
| can all be implemented very efficiently. |
| <p> |
| There are also the pessimising casts <code>VgT_PCast14</code>, |
| from 8 bits to 32, <code>VgT_PCast12</code>, from 8 bits to 16, |
| and <code>VgT_PCast11</code>, from 8 bits to 8. This last one |
| seems nonsensical, but in fact it isn't a no-op because, as |
| mentioned above, any undefined (1) bits in the source infect the |
| entire result. |
| <p> |
| <li><b>(UNARY) Propagating undefinedness upwards in a word</b>: |
| <code>VgT_Left4</code>, <code>VgT_Left2</code> and |
| <code>VgT_Left1</code>. These are used to simulate the worst-case |
| effects of carry propagation in adds and subtracts. They return a |
| V vector identical to the original, except that if the original |
| contained any undefined bits, then it and all bits above it are |
| marked as undefined too. Hence the Left bit in the names. |
| <p> |
| <li><b>(UNARY) Signed and unsigned value widening</b>: |
| <code>VgT_SWiden14</code>, <code>VgT_SWiden24</code>, |
| <code>VgT_SWiden12</code>, <code>VgT_ZWiden14</code>, |
| <code>VgT_ZWiden24</code> and <code>VgT_ZWiden12</code>. These |
| mimic the definedness effects of standard signed and unsigned |
| integer widening. Unsigned widening creates zero bits in the new |
| positions, so <code>VgT_ZWiden*</code> accordingly park mark |
| those parts of their argument as defined. Signed widening copies |
| the sign bit into the new positions, so <code>VgT_SWiden*</code> |
| copies the definedness of the sign bit into the new positions. |
| Because 1 means undefined and 0 means defined, these operations |
| can (fascinatingly) be done by the same operations which they |
| mimic. Go figure. |
| <p> |
| <li><b>(BINARY) Undefined-if-either-Undefined, |
| Defined-if-either-Defined</b>: <code>VgT_UifU4</code>, |
| <code>VgT_UifU2</code>, <code>VgT_UifU1</code>, |
| <code>VgT_UifU0</code>, <code>VgT_DifD4</code>, |
| <code>VgT_DifD2</code>, <code>VgT_DifD1</code>. These do simple |
| bitwise operations on pairs of V-bit vectors, with |
| <code>UifU</code> giving undefined if either arg bit is |
| undefined, and <code>DifD</code> giving defined if either arg bit |
| is defined. Abstract interpretation junkies, if any make it this |
| far, may like to think of them as meets and joins (or is it joins |
| and meets) in the definedness lattices. |
| <p> |
| <li><b>(BINARY; one value, one V bits) Generate argument improvement |
| terms for AND and OR</b>: <code>VgT_ImproveAND4_TQ</code>, |
| <code>VgT_ImproveAND2_TQ</code>, <code>VgT_ImproveAND1_TQ</code>, |
| <code>VgT_ImproveOR4_TQ</code>, <code>VgT_ImproveOR2_TQ</code>, |
| <code>VgT_ImproveOR1_TQ</code>. These help out with AND and OR |
| operations. AND and OR have the inconvenient property that the |
| definedness of the result depends on the actual values of the |
| arguments as well as their definedness. At the bit level: |
| <br><code>1 AND undefined = undefined</code>, but |
| <br><code>0 AND undefined = 0</code>, and similarly |
| <br><code>0 OR undefined = undefined</code>, but |
| <br><code>1 OR undefined = 1</code>. |
| <br> |
| <p> |
| It turns out that gcc (quite legitimately) generates code which |
| relies on this fact, so we have to model it properly in order to |
| avoid flooding users with spurious value errors. The ultimate |
| definedness result of AND and OR is calculated using |
| <code>UifU</code> on the definedness of the arguments, but we |
| also <code>DifD</code> in some "improvement" terms which |
| take into account the above phenomena. |
| <p> |
| <code>ImproveAND</code> takes as its first argument the actual |
| value of an argument to AND (the T) and the definedness of that |
| argument (the Q), and returns a V-bit vector which is defined (0) |
| for bits which have value 0 and are defined; this, when |
| <code>DifD</code> into the final result causes those bits to be |
| defined even if the corresponding bit in the other argument is undefined. |
| <p> |
| The <code>ImproveOR</code> ops do the dual thing for OR |
| arguments. Note that XOR does not have this property that one |
| argument can make the other irrelevant, so there is no need for |
| such complexity for XOR. |
| </ul> |
| |
| <p> |
| That's all the tag ops. If you stare at this long enough, and then |
| run Valgrind and stare at the pre- and post-instrumented ucode, it |
| should be fairly obvious how the instrumentation machinery hangs |
| together. |
| |
| <p> |
| One point, if you do this: in order to make it easy to differentiate |
| <code>TempReg</code>s carrying values from <code>TempReg</code>s |
| carrying V bit vectors, Valgrind prints the former as (for example) |
| <code>t28</code> and the latter as <code>q28</code>; the fact that |
| they carry the same number serves to indicate their relationship. |
| This is purely for the convenience of the human reader; the register |
| allocator and code generator don't regard them as different. |
| |
| |
| <h3>Translation into UCode</h3> |
| |
| <code>VG_(disBB)</code> allocates a new <code>UCodeBlock</code> and |
| then uses <code>disInstr</code> to translate x86 instructions one at a |
| time into UCode, dumping the result in the <code>UCodeBlock</code>. |
| This goes on until a control-flow transfer instruction is encountered. |
| |
| <p> |
| Despite the large size of <code>vg_to_ucode.c</code>, this translation |
| is really very simple. Each x86 instruction is translated entirely |
| independently of its neighbours, merrily allocating new |
| <code>TempReg</code>s as it goes. The idea is to have a simple |
| translator -- in reality, no more than a macro-expander -- and the -- |
| resulting bad UCode translation is cleaned up by the UCode |
| optimisation phase which follows. To give you an idea of some x86 |
| instructions and their translations (this is a complete basic block, |
| as Valgrind sees it): |
| <pre> |
| 0x40435A50: incl %edx |
| |
| 0: GETL %EDX, t0 |
| 1: INCL t0 (-wOSZAP) |
| 2: PUTL t0, %EDX |
| |
| 0x40435A51: movsbl (%edx),%eax |
| |
| 3: GETL %EDX, t2 |
| 4: LDB (t2), t2 |
| 5: WIDENL_Bs t2 |
| 6: PUTL t2, %EAX |
| |
| 0x40435A54: testb $0x20, 1(%ecx,%eax,2) |
| |
| 7: GETL %EAX, t6 |
| 8: GETL %ECX, t8 |
| 9: LEA2L 1(t8,t6,2), t4 |
| 10: LDB (t4), t10 |
| 11: MOVB $0x20, t12 |
| 12: ANDB t12, t10 (-wOSZACP) |
| 13: INCEIPo $9 |
| |
| 0x40435A59: jnz-8 0x40435A50 |
| |
| 14: Jnzo $0x40435A50 (-rOSZACP) |
| 15: JMPo $0x40435A5B |
| </pre> |
| |
| <p> |
| Notice how the block always ends with an unconditional jump to the |
| next block. This is a bit unnecessary, but makes many things simpler. |
| |
| <p> |
| Most x86 instructions turn into sequences of <code>GET</code>, |
| <code>PUT</code>, <code>LEA1</code>, <code>LEA2</code>, |
| <code>LOAD</code> and <code>STORE</code>. Some complicated ones |
| however rely on calling helper bits of code in |
| <code>vg_helpers.S</code>. The ucode instructions <code>PUSH</code>, |
| <code>POP</code>, <code>CALL</code>, <code>CALLM_S</code> and |
| <code>CALLM_E</code> support this. The calling convention is somewhat |
| ad-hoc and is not the C calling convention. The helper routines must |
| save all integer registers, and the flags, that they use. Args are |
| passed on the stack underneath the return address, as usual, and if |
| result(s) are to be returned, it (they) are either placed in dummy arg |
| slots created by the ucode <code>PUSH</code> sequence, or just |
| overwrite the incoming args. |
| |
| <p> |
| In order that the instrumentation mechanism can handle calls to these |
| helpers, <code>VG_(saneUCodeBlock)</code> enforces the following |
| restrictions on calls to helpers: |
| |
| <ul> |
| <li>Each <code>CALL</code> uinstr must be bracketed by a preceding |
| <code>CALLM_S</code> marker (dummy uinstr) and a trailing |
| <code>CALLM_E</code> marker. These markers are used by the |
| instrumentation mechanism later to establish the boundaries of the |
| <code>PUSH</code>, <code>POP</code> and <code>CLEAR</code> |
| sequences for the call. |
| <p> |
| <li><code>PUSH</code>, <code>POP</code> and <code>CLEAR</code> |
| may only appear inside sections bracketed by <code>CALLM_S</code> |
| and <code>CALLM_E</code>, and nowhere else. |
| <p> |
| <li>In any such bracketed section, no two <code>PUSH</code> insns may |
| push the same <code>TempReg</code>. Dually, no two two |
| <code>POP</code>s may pop the same <code>TempReg</code>. |
| <p> |
| <li>Finally, although this is not checked, args should be removed from |
| the stack with <code>CLEAR</code>, rather than <code>POP</code>s |
| into a <code>TempReg</code> which is not subsequently used. This |
| is because the instrumentation mechanism assumes that all values |
| <code>POP</code>ped from the stack are actually used. |
| </ul> |
| |
| Some of the translations may appear to have redundant |
| <code>TempReg</code>-to-<code>TempReg</code> moves. This helps the |
| next phase, UCode optimisation, to generate better code. |
| |
| |
| |
| <h3>UCode optimisation</h3> |
| |
| UCode is then subjected to an improvement pass |
| (<code>vg_improve()</code>), which blurs the boundaries between the |
| translations of the original x86 instructions. It's pretty |
| straightforward. Three transformations are done: |
| |
| <ul> |
| <li>Redundant <code>GET</code> elimination. Actually, more general |
| than that -- eliminates redundant fetches of ArchRegs. In our |
| running example, uinstr 3 <code>GET</code>s <code>%EDX</code> into |
| <code>t2</code> despite the fact that, by looking at the previous |
| uinstr, it is already in <code>t0</code>. The <code>GET</code> is |
| therefore removed, and <code>t2</code> renamed to <code>t0</code>. |
| Assuming <code>t0</code> is allocated to a host register, it means |
| the simulated <code>%EDX</code> will exist in a host CPU register |
| for more than one simulated x86 instruction, which seems to me to |
| be a highly desirable property. |
| <p> |
| There is some mucking around to do with subregisters; |
| <code>%AL</code> vs <code>%AH</code> <code>%AX</code> vs |
| <code>%EAX</code> etc. I can't remember how it works, but in |
| general we are very conservative, and these tend to invalidate the |
| caching. |
| <p> |
| <li>Redundant <code>PUT</code> elimination. This annuls |
| <code>PUT</code>s of values back to simulated CPU registers if a |
| later <code>PUT</code> would overwrite the earlier |
| <code>PUT</code> value, and there is no intervening reads of the |
| simulated register (<code>ArchReg</code>). |
| <p> |
| As before, we are paranoid when faced with subregister references. |
| Also, <code>PUT</code>s of <code>%ESP</code> are never annulled, |
| because it is vital the instrumenter always has an up-to-date |
| <code>%ESP</code> value available, <code>%ESP</code> changes |
| affect addressibility of the memory around the simulated stack |
| pointer. |
| <p> |
| The implication of the above paragraph is that the simulated |
| machine's registers are only lazily updated once the above two |
| optimisation phases have run, with the exception of |
| <code>%ESP</code>. <code>TempReg</code>s go dead at the end of |
| every basic block, from which is is inferrable that any |
| <code>TempReg</code> caching a simulated CPU reg is flushed (back |
| into the relevant <code>VG_(baseBlock)</code> slot) at the end of |
| every basic block. The further implication is that the simulated |
| registers are only up-to-date at in between basic blocks, and not |
| at arbitrary points inside basic blocks. And the consequence of |
| that is that we can only deliver signals to the client in between |
| basic blocks. None of this seems any problem in practice. |
| <p> |
| <li>Finally there is a simple def-use thing for condition codes. If |
| an earlier uinstr writes the condition codes, and the next uinsn |
| along which actually cares about the condition codes writes the |
| same or larger set of them, but does not read any, the earlier |
| uinsn is marked as not writing any condition codes. This saves |
| a lot of redundant cond-code saving and restoring. |
| </ul> |
| |
| The effect of these transformations on our short block is rather |
| unexciting, and shown below. On longer basic blocks they can |
| dramatically improve code quality. |
| |
| <pre> |
| at 3: delete GET, rename t2 to t0 in (4 .. 6) |
| at 7: delete GET, rename t6 to t0 in (8 .. 9) |
| at 1: annul flag write OSZAP due to later OSZACP |
| |
| Improved code: |
| 0: GETL %EDX, t0 |
| 1: INCL t0 |
| 2: PUTL t0, %EDX |
| 4: LDB (t0), t0 |
| 5: WIDENL_Bs t0 |
| 6: PUTL t0, %EAX |
| 8: GETL %ECX, t8 |
| 9: LEA2L 1(t8,t0,2), t4 |
| 10: LDB (t4), t10 |
| 11: MOVB $0x20, t12 |
| 12: ANDB t12, t10 (-wOSZACP) |
| 13: INCEIPo $9 |
| 14: Jnzo $0x40435A50 (-rOSZACP) |
| 15: JMPo $0x40435A5B |
| </pre> |
| |
| <h3>UCode instrumentation</h3> |
| |
| Once you understand the meaning of the instrumentation uinstrs, |
| discussed in detail above, the instrumentation scheme is fairly |
| straighforward. Each uinstr is instrumented in isolation, and the |
| instrumentation uinstrs are placed before the original uinstr. |
| Our running example continues below. I have placed a blank line |
| after every original ucode, to make it easier to see which |
| instrumentation uinstrs correspond to which originals. |
| |
| <p> |
| As mentioned somewhere above, <code>TempReg</code>s carrying values |
| have names like <code>t28</code>, and each one has a shadow carrying |
| its V bits, with names like <code>q28</code>. This pairing aids in |
| reading instrumented ucode. |
| |
| <p> |
| One decision about all this is where to have "observation points", |
| that is, where to check that V bits are valid. I use a minimalistic |
| scheme, only checking where a failure of validity could cause the |
| original program to (seg)fault. So the use of values as memory |
| addresses causes a check, as do conditional jumps (these cause a check |
| on the definedness of the condition codes). And arguments |
| <code>PUSH</code>ed for helper calls are checked, hence the wierd |
| restrictions on help call preambles described above. |
| |
| <p> |
| Another decision is that once a value is tested, it is thereafter |
| regarded as defined, so that we do not emit multiple undefined-value |
| errors for the same undefined value. That means that |
| <code>TESTV</code> uinstrs are always followed by <code>SETV</code> |
| on the same (shadow) <code>TempReg</code>s. Most of these |
| <code>SETV</code>s are redundant and are removed by the |
| post-instrumentation cleanup phase. |
| |
| <p> |
| The instrumentation for calling helper functions deserves further |
| comment. The definedness of results from a helper is modelled using |
| just one V bit. So, in short, we do pessimising casts of the |
| definedness of all the args, down to a single bit, and then |
| <code>UifU</code> these bits together. So this single V bit will say |
| "undefined" if any part of any arg is undefined. This V bit is then |
| pessimally cast back up to the result(s) sizes, as needed. If, by |
| seeing that all the args are got rid of with <code>CLEAR</code> and |
| none with <code>POP</code>, Valgrind sees that the result of the call |
| is not actually used, it immediately examines the result V bit with a |
| <code>TESTV</code> -- <code>SETV</code> pair. If it did not do this, |
| there would be no observation point to detect that the some of the |
| args to the helper were undefined. Of course, if the helper's results |
| are indeed used, we don't do this, since the result usage will |
| presumably cause the result definedness to be checked at some suitable |
| future point. |
| |
| <p> |
| In general Valgrind tries to track definedness on a bit-for-bit basis, |
| but as the above para shows, for calls to helpers we throw in the |
| towel and approximate down to a single bit. This is because it's too |
| complex and difficult to track bit-level definedness through complex |
| ops such as integer multiply and divide, and in any case there is no |
| reasonable code fragments which attempt to (eg) multiply two |
| partially-defined values and end up with something meaningful, so |
| there seems little point in modelling multiplies, divides, etc, in |
| that level of detail. |
| |
| <p> |
| Integer loads and stores are instrumented with firstly a test of the |
| definedness of the address, followed by a <code>LOADV</code> or |
| <code>STOREV</code> respectively. These turn into calls to |
| (for example) <code>VG_(helperc_LOADV4)</code>. These helpers do two |
| things: they perform an address-valid check, and they load or store V |
| bits from/to the relevant address in the (simulated V-bit) memory. |
| |
| <p> |
| FPU loads and stores are different. As above the definedness of the |
| address is first tested. However, the helper routine for FPU loads |
| (<code>VGM_(fpu_read_check)</code>) emits an error if either the |
| address is invalid or the referenced area contains undefined values. |
| It has to do this because we do not simulate the FPU at all, and so |
| cannot track definedness of values loaded into it from memory, so we |
| have to check them as soon as they are loaded into the FPU, ie, at |
| this point. We notionally assume that everything in the FPU is |
| defined. |
| |
| <p> |
| It follows therefore that FPU writes first check the definedness of |
| the address, then the validity of the address, and finally mark the |
| written bytes as well-defined. |
| |
| <p> |
| If anyone is inspired to extend Valgrind to MMX/SSE insns, I suggest |
| you use the same trick. It works provided that the FPU/MMX unit is |
| not used to merely as a conduit to copy partially undefined data from |
| one place in memory to another. Unfortunately the integer CPU is used |
| like that (when copying C structs with holes, for example) and this is |
| the cause of much of the elaborateness of the instrumentation here |
| described. |
| |
| <p> |
| <code>vg_instrument()</code> in <code>vg_translate.c</code> actually |
| does the instrumentation. There are comments explaining how each |
| uinstr is handled, so we do not repeat that here. As explained |
| already, it is bit-accurate, except for calls to helper functions. |
| Unfortunately the x86 insns <code>bt/bts/btc/btr</code> are done by |
| helper fns, so bit-level accuracy is lost there. This should be fixed |
| by doing them inline; it will probably require adding a couple new |
| uinstrs. Also, left and right rotates through the carry flag (x86 |
| <code>rcl</code> and <code>rcr</code>) are approximated via a single |
| V bit; so far this has not caused anyone to complain. The |
| non-carry rotates, <code>rol</code> and <code>ror</code>, are much |
| more common and are done exactly. Re-visiting the instrumentation for |
| AND and OR, they seem rather verbose, and I wonder if it could be done |
| more concisely now. |
| |
| <p> |
| The lowercase <code>o</code> on many of the uopcodes in the running |
| example indicates that the size field is zero, usually meaning a |
| single-bit operation. |
| |
| <p> |
| Anyroads, the post-instrumented version of our running example looks |
| like this: |
| |
| <pre> |
| Instrumented code: |
| 0: GETVL %EDX, q0 |
| 1: GETL %EDX, t0 |
| |
| 2: TAG1o q0 = Left4 ( q0 ) |
| 3: INCL t0 |
| |
| 4: PUTVL q0, %EDX |
| 5: PUTL t0, %EDX |
| |
| 6: TESTVL q0 |
| 7: SETVL q0 |
| 8: LOADVB (t0), q0 |
| 9: LDB (t0), t0 |
| |
| 10: TAG1o q0 = SWiden14 ( q0 ) |
| 11: WIDENL_Bs t0 |
| |
| 12: PUTVL q0, %EAX |
| 13: PUTL t0, %EAX |
| |
| 14: GETVL %ECX, q8 |
| 15: GETL %ECX, t8 |
| |
| 16: MOVL q0, q4 |
| 17: SHLL $0x1, q4 |
| 18: TAG2o q4 = UifU4 ( q8, q4 ) |
| 19: TAG1o q4 = Left4 ( q4 ) |
| 20: LEA2L 1(t8,t0,2), t4 |
| |
| 21: TESTVL q4 |
| 22: SETVL q4 |
| 23: LOADVB (t4), q10 |
| 24: LDB (t4), t10 |
| |
| 25: SETVB q12 |
| 26: MOVB $0x20, t12 |
| |
| 27: MOVL q10, q14 |
| 28: TAG2o q14 = ImproveAND1_TQ ( t10, q14 ) |
| 29: TAG2o q10 = UifU1 ( q12, q10 ) |
| 30: TAG2o q10 = DifD1 ( q14, q10 ) |
| 31: MOVL q12, q14 |
| 32: TAG2o q14 = ImproveAND1_TQ ( t12, q14 ) |
| 33: TAG2o q10 = DifD1 ( q14, q10 ) |
| 34: MOVL q10, q16 |
| 35: TAG1o q16 = PCast10 ( q16 ) |
| 36: PUTVFo q16 |
| 37: ANDB t12, t10 (-wOSZACP) |
| |
| 38: INCEIPo $9 |
| |
| 39: GETVFo q18 |
| 40: TESTVo q18 |
| 41: SETVo q18 |
| 42: Jnzo $0x40435A50 (-rOSZACP) |
| |
| 43: JMPo $0x40435A5B |
| </pre> |
| |
| |
| <h3>UCode post-instrumentation cleanup</h3> |
| |
| <p> |
| This pass, coordinated by <code>vg_cleanup()</code>, removes redundant |
| definedness computation created by the simplistic instrumentation |
| pass. It consists of two passes, |
| <code>vg_propagate_definedness()</code> followed by |
| <code>vg_delete_redundant_SETVs</code>. |
| |
| <p> |
| <code>vg_propagate_definedness()</code> is a simple |
| constant-propagation and constant-folding pass. It tries to determine |
| which <code>TempReg</code>s containing V bits will always indicate |
| "fully defined", and it propagates this information as far as it can, |
| and folds out as many operations as possible. For example, the |
| instrumentation for an ADD of a literal to a variable quantity will be |
| reduced down so that the definedness of the result is simply the |
| definedness of the variable quantity, since the literal is by |
| definition fully defined. |
| |
| <p> |
| <code>vg_delete_redundant_SETVs</code> removes <code>SETV</code>s on |
| shadow <code>TempReg</code>s for which the next action is a write. |
| I don't think there's anything else worth saying about this; it is |
| simple. Read the sources for details. |
| |
| <p> |
| So the cleaned-up running example looks like this. As above, I have |
| inserted line breaks after every original (non-instrumentation) uinstr |
| to aid readability. As with straightforward ucode optimisation, the |
| results in this block are undramatic because it is so short; longer |
| blocks benefit more because they have more redundancy which gets |
| eliminated. |
| |
| |
| <pre> |
| at 29: delete UifU1 due to defd arg1 |
| at 32: change ImproveAND1_TQ to MOV due to defd arg2 |
| at 41: delete SETV |
| at 31: delete MOV |
| at 25: delete SETV |
| at 22: delete SETV |
| at 7: delete SETV |
| |
| 0: GETVL %EDX, q0 |
| 1: GETL %EDX, t0 |
| |
| 2: TAG1o q0 = Left4 ( q0 ) |
| 3: INCL t0 |
| |
| 4: PUTVL q0, %EDX |
| 5: PUTL t0, %EDX |
| |
| 6: TESTVL q0 |
| 8: LOADVB (t0), q0 |
| 9: LDB (t0), t0 |
| |
| 10: TAG1o q0 = SWiden14 ( q0 ) |
| 11: WIDENL_Bs t0 |
| |
| 12: PUTVL q0, %EAX |
| 13: PUTL t0, %EAX |
| |
| 14: GETVL %ECX, q8 |
| 15: GETL %ECX, t8 |
| |
| 16: MOVL q0, q4 |
| 17: SHLL $0x1, q4 |
| 18: TAG2o q4 = UifU4 ( q8, q4 ) |
| 19: TAG1o q4 = Left4 ( q4 ) |
| 20: LEA2L 1(t8,t0,2), t4 |
| |
| 21: TESTVL q4 |
| 23: LOADVB (t4), q10 |
| 24: LDB (t4), t10 |
| |
| 26: MOVB $0x20, t12 |
| |
| 27: MOVL q10, q14 |
| 28: TAG2o q14 = ImproveAND1_TQ ( t10, q14 ) |
| 30: TAG2o q10 = DifD1 ( q14, q10 ) |
| 32: MOVL t12, q14 |
| 33: TAG2o q10 = DifD1 ( q14, q10 ) |
| 34: MOVL q10, q16 |
| 35: TAG1o q16 = PCast10 ( q16 ) |
| 36: PUTVFo q16 |
| 37: ANDB t12, t10 (-wOSZACP) |
| |
| 38: INCEIPo $9 |
| 39: GETVFo q18 |
| 40: TESTVo q18 |
| 42: Jnzo $0x40435A50 (-rOSZACP) |
| |
| 43: JMPo $0x40435A5B |
| </pre> |
| |
| |
| <h3>Translation from UCode</h3> |
| |
| This is all very simple, even though <code>vg_from_ucode.c</code> |
| is a big file. Position-independent x86 code is generated into |
| a dynamically allocated array <code>emitted_code</code>; this is |
| doubled in size when it overflows. Eventually the array is handed |
| back to the caller of <code>VG_(translate)</code>, who must copy |
| the result into TC and TT, and free the array. |
| |
| <p> |
| This file is structured into four layers of abstraction, which, |
| thankfully, are glued back together with extensive |
| <code>__inline__</code> directives. From the bottom upwards: |
| |
| <ul> |
| <li>Address-mode emitters, <code>emit_amode_regmem_reg</code> et al. |
| <p> |
| <li>Emitters for specific x86 instructions. There are quite a lot of |
| these, with names such as <code>emit_movv_offregmem_reg</code>. |
| The <code>v</code> suffix is Intel parlance for a 16/32 bit insn; |
| there are also <code>b</code> suffixes for 8 bit insns. |
| <p> |
| <li>The next level up are the <code>synth_*</code> functions, which |
| synthesise possibly a sequence of raw x86 instructions to do some |
| simple task. Some of these are quite complex because they have to |
| work around Intel's silly restrictions on subregister naming. See |
| <code>synth_nonshiftop_reg_reg</code> for example. |
| <p> |
| <li>Finally, at the top of the heap, we have |
| <code>emitUInstr()</code>, |
| which emits code for a single uinstr. |
| </ul> |
| |
| <p> |
| Some comments: |
| <ul> |
| <li>The hack for FPU instructions becomes apparent here. To do a |
| <code>FPU</code> ucode instruction, we load the simulated FPU's |
| state into from its <code>VG_(baseBlock)</code> into the real FPU |
| using an x86 <code>frstor</code> insn, do the ucode |
| <code>FPU</code> insn on the real CPU, and write the updated FPU |
| state back into <code>VG_(baseBlock)</code> using an |
| <code>fnsave</code> instruction. This is pretty brutal, but is |
| simple and it works, and even seems tolerably efficient. There is |
| no attempt to cache the simulated FPU state in the real FPU over |
| multiple back-to-back ucode FPU instructions. |
| <p> |
| <code>FPU_R</code> and <code>FPU_W</code> are also done this way, |
| with the minor complication that we need to patch in some |
| addressing mode bits so the resulting insn knows the effective |
| address to use. This is easy because of the regularity of the x86 |
| FPU instruction encodings. |
| <p> |
| <li>An analogous trick is done with ucode insns which claim, in their |
| <code>flags_r</code> and <code>flags_w</code> fields, that they |
| read or write the simulated <code>%EFLAGS</code>. For such cases |
| we first copy the simulated <code>%EFLAGS</code> into the real |
| <code>%eflags</code>, then do the insn, then, if the insn says it |
| writes the flags, copy back to <code>%EFLAGS</code>. This is a |
| bit expensive, which is why the ucode optimisation pass goes to |
| some effort to remove redundant flag-update annotations. |
| </ul> |
| |
| <p> |
| And so ... that's the end of the documentation for the instrumentating |
| translator! It's really not that complex, because it's composed as a |
| sequence of simple(ish) self-contained transformations on |
| straight-line blocks of code. |
| |
| |
| <h3>Top-level dispatch loop</h3> |
| |
| Urk. In <code>VG_(toploop)</code>. This is basically boring and |
| unsurprising, not to mention fiddly and fragile. It needs to be |
| cleaned up. |
| |
| <p> |
| The only perhaps surprise is that the whole thing is run |
| on top of a <code>setjmp</code>-installed exception handler, because, |
| supposing a translation got a segfault, we have to bail out of the |
| Valgrind-supplied exception handler <code>VG_(oursignalhandler)</code> |
| and immediately start running the client's segfault handler, if it has |
| one. In particular we can't finish the current basic block and then |
| deliver the signal at some convenient future point, because signals |
| like SIGILL, SIGSEGV and SIGBUS mean that the faulting insn should not |
| simply be re-tried. (I'm sure there is a clearer way to explain this). |
| |
| |
| <h3>Exceptions, creating new translations</h3> |
| <h3>Self-modifying code</h3> |
| |
| <h3>Lazy updates of the simulated program counter</h3> |
| |
| Simulated <code>%EIP</code> is not updated after every simulated x86 |
| insn as this was regarded as too expensive. Instead ucode |
| <code>INCEIP</code> insns move it along as and when necessary. |
| Currently we don't allow it to fall more than 4 bytes behind reality |
| (see <code>VG_(disBB)</code> for the way this works). |
| <p> |
| Note that <code>%EIP</code> is always brought up to date by the inner |
| dispatch loop in <code>VG_(dispatch)</code>, so that if the client |
| takes a fault we know at least which basic block this happened in. |
| |
| |
| <h3>The translation cache and translation table</h3> |
| |
| <h3>Signals</h3> |
| |
| Horrible, horrible. <code>vg_signals.c</code>. |
| Basically, since we have to intercept all system |
| calls anyway, we can see when the client tries to install a signal |
| handler. If it does so, we make a note of what the client asked to |
| happen, and ask the kernel to route the signal to our own signal |
| handler, <code>VG_(oursignalhandler)</code>. This simply notes the |
| delivery of signals, and returns. |
| |
| <p> |
| Every 1000 basic blocks, we see if more signals have arrived. If so, |
| <code>VG_(deliver_signals)</code> builds signal delivery frames on the |
| client's stack, and allows their handlers to be run. Valgrind places |
| in these signal delivery frames a bogus return address, |
| </code>VG_(signalreturn_bogusRA)</code>, and checks all jumps to see |
| if any jump to it. If so, this is a sign that a signal handler is |
| returning, and if so Valgrind removes the relevant signal frame from |
| the client's stack, restores the from the signal frame the simulated |
| state before the signal was delivered, and allows the client to run |
| onwards. We have to do it this way because some signal handlers never |
| return, they just <code>longjmp()</code>, which nukes the signal |
| delivery frame. |
| |
| <p> |
| The Linux kernel has a different but equally horrible hack for |
| detecting signal handler returns. Discovering it is left as an |
| exercise for the reader. |
| |
| |
| |
| <h3>Errors, error contexts, error reporting, suppressions</h3> |
| <h3>Client malloc/free</h3> |
| <h3>Low-level memory management</h3> |
| <h3>A and V bitmaps</h3> |
| <h3>Symbol table management</h3> |
| <h3>Dealing with system calls</h3> |
| <h3>Namespace management</h3> |
| <h3>GDB attaching</h3> |
| <h3>Non-dependence on glibc or anything else</h3> |
| <h3>The leak detector</h3> |
| <h3>Performance problems</h3> |
| <h3>Continuous sanity checking</h3> |
| <h3>Tracing, or not tracing, child processes</h3> |
| <h3>Assembly glue for syscalls</h3> |
| |
| |
| <hr width="100%"> |
| |
| <h2>Extensions</h2> |
| |
| Some comments about Stuff To Do. |
| |
| <h3>Bugs</h3> |
| |
| Stephan Kulow and Marc Mutz report problems with kmail in KDE 3 CVS |
| (RC2 ish) when run on Valgrind. Stephan has it deadlocking; Marc has |
| it looping at startup. I can't repro either behaviour. Needs |
| repro-ing and fixing. |
| |
| |
| <h3>Threads</h3> |
| |
| Doing a good job of thread support strikes me as almost a |
| research-level problem. The central issues are how to do fast cheap |
| locking of the <code>VG_(primary_map)</code> structure, whether or not |
| accesses to the individual secondary maps need locking, what |
| race-condition issues result, and whether the already-nasty mess that |
| is the signal simulator needs further hackery. |
| |
| <p> |
| I realise that threads are the most-frequently-requested feature, and |
| I am thinking about it all. If you have guru-level understanding of |
| fast mutual exclusion mechanisms and race conditions, I would be |
| interested in hearing from you. |
| |
| |
| <h3>Verification suite</h3> |
| |
| Directory <code>tests/</code> contains various ad-hoc tests for |
| Valgrind. However, there is no systematic verification or regression |
| suite, that, for example, exercises all the stuff in |
| <code>vg_memory.c</code>, to ensure that illegal memory accesses and |
| undefined value uses are detected as they should be. It would be good |
| to have such a suite. |
| |
| |
| <h3>Porting to other platforms</h3> |
| |
| It would be great if Valgrind was ported to FreeBSD and x86 NetBSD, |
| and to x86 OpenBSD, if it's possible (doesn't OpenBSD use a.out-style |
| executables, not ELF ?) |
| |
| <p> |
| The main difficulties, for an x86-ELF platform, seem to be: |
| |
| <ul> |
| <li>You'd need to rewrite the <code>/proc/self/maps</code> parser |
| (<code>vg_procselfmaps.c</code>). |
| Easy. |
| <p> |
| <li>You'd need to rewrite <code>vg_syscall_mem.c</code>, or, more |
| specifically, provide one for your OS. This is tedious, but you |
| can implement syscalls on demand, and the Linux kernel interface |
| is, for the most part, going to look very similar to the *BSD |
| interfaces, so it's really a copy-paste-and-modify-on-demand job. |
| As part of this, you'd need to supply a new |
| <code>vg_kerneliface.h</code> file. |
| <p> |
| <li>You'd also need to change the syscall wrappers for Valgrind's |
| internal use, in <code>vg_mylibc.c</code>. |
| </ul> |
| |
| All in all, I think a port to x86-ELF *BSDs is not really very |
| difficult, and in some ways I would like to see it happen, because |
| that would force a more clear factoring of Valgrind into platform |
| dependent and independent pieces. Not to mention, *BSD folks also |
| deserve to use Valgrind just as much as the Linux crew do. |
| |
| |
| <p> |
| <hr width="100%"> |
| |
| <h2>Easy stuff which ought to be done</h2> |
| |
| <h3>MMX instructions</h3> |
| |
| MMX insns should be supported, using the same trick as for FPU insns. |
| If the MMX registers are not used to copy uninitialised junk from one |
| place to another in memory, this means we don't have to actually |
| simulate the internal MMX unit state, so the FPU hack applies. This |
| should be fairly easy. |
| |
| |
| |
| <h3>Fix stabs-info reader</h3> |
| |
| The machinery in <code>vg_symtab2.c</code> which reads "stabs" style |
| debugging info is pretty weak. It usually correctly translates |
| simulated program counter values into line numbers and procedure |
| names, but the file name is often completely wrong. I think the |
| logic used to parse "stabs" entries is weak. It should be fixed. |
| The simplest solution, IMO, is to copy either the logic or simply the |
| code out of GNU binutils which does this; since GDB can clearly get it |
| right, binutils (or GDB?) must have code to do this somewhere. |
| |
| |
| |
| |
| |
| <h3>BT/BTC/BTS/BTR</h3> |
| |
| These are x86 instructions which test, complement, set, or reset, a |
| single bit in a word. At the moment they are both incorrectly |
| implemented and incorrectly instrumented. |
| |
| <p> |
| The incorrect instrumentation is due to use of helper functions. This |
| means we lose bit-level definedness tracking, which could wind up |
| giving spurious uninitialised-value use errors. The Right Thing to do |
| is to invent a couple of new UOpcodes, I think <code>GET_BIT</code> |
| and <code>SET_BIT</code>, which can be used to implement all 4 x86 |
| insns, get rid of the helpers, and give bit-accurate instrumentation |
| rules for the two new UOpcodes. |
| |
| <p> |
| I realised the other day that they are mis-implemented too. The x86 |
| insns take a bit-index and a register or memory location to access. |
| For registers the bit index clearly can only be in the range zero to |
| register-width minus 1, and I assumed the same applied to memory |
| locations too. But evidently not; for memory locations the index can |
| be arbitrary, and the processor will index arbitrarily into memory as |
| a result. This too should be fixed. Sigh. Presumably indexing |
| outside the immediate word is not actually used by any programs yet |
| tested on Valgrind, for otherwise they (presumably) would simply not |
| work at all. If you plan to hack on this, first check the Intel docs |
| to make sure my understanding is really correct. |
| |
| |
| |
| <h3>Using PREFETCH instructions</h3> |
| |
| Here's a small but potentially interesting project for performance |
| junkies. Experiments with valgrind's code generator and optimiser(s) |
| suggest that reducing the number of instructions executed in the |
| translations and mem-check helpers gives disappointingly small |
| performance improvements. Perhaps this is because performance of |
| Valgrindified code is limited by cache misses. After all, each read |
| in the original program now gives rise to at least three reads, one |
| for the <code>VG_(primary_map)</code>, one of the resulting |
| secondary, and the original. Not to mention, the instrumented |
| translations are 13 to 14 times larger than the originals. All in all |
| one would expect the memory system to be hammered to hell and then |
| some. |
| |
| <p> |
| So here's an idea. An x86 insn involving a read from memory, after |
| instrumentation, will turn into ucode of the following form: |
| <pre> |
| ... calculate effective addr, into ta and qa ... |
| TESTVL qa -- is the addr defined? |
| LOADV (ta), qloaded -- fetch V bits for the addr |
| LOAD (ta), tloaded -- do the original load |
| </pre> |
| At the point where the <code>LOADV</code> is done, we know the actual |
| address (<code>ta</code>) from which the real <code>LOAD</code> will |
| be done. We also know that the <code>LOADV</code> will take around |
| 20 x86 insns to do. So it seems plausible that doing a prefetch of |
| <code>ta</code> just before the <code>LOADV</code> might just avoid a |
| miss at the <code>LOAD</code> point, and that might be a significant |
| performance win. |
| |
| <p> |
| Prefetch insns are notoriously tempermental, more often than not |
| making things worse rather than better, so this would require |
| considerable fiddling around. It's complicated because Intels and |
| AMDs have different prefetch insns with different semantics, so that |
| too needs to be taken into account. As a general rule, even placing |
| the prefetches before the <code>LOADV</code> insn is too near the |
| <code>LOAD</code>; the ideal distance is apparently circa 200 CPU |
| cycles. So it might be worth having another analysis/transformation |
| pass which pushes prefetches as far back as possible, hopefully |
| immediately after the effective address becomes available. |
| |
| <p> |
| Doing too many prefetches is also bad because they soak up bus |
| bandwidth / cpu resources, so some cleverness in deciding which loads |
| to prefetch and which to not might be helpful. One can imagine not |
| prefetching client-stack-relative (<code>%EBP</code> or |
| <code>%ESP</code>) accesses, since the stack in general tends to show |
| good locality anyway. |
| |
| <p> |
| There's quite a lot of experimentation to do here, but I think it |
| might make an interesting week's work for someone. |
| |
| <p> |
| As of 15-ish March 2002, I've started to experiment with this, using |
| the AMD <code>prefetch/prefetchw</code> insns. |
| |
| |
| |
| <h3>User-defined permission ranges</h3> |
| |
| This is quite a large project -- perhaps a month's hacking for a |
| capable hacker to do a good job -- but it's potentially very |
| interesting. The outcome would be that Valgrind could detect a |
| whole class of bugs which it currently cannot. |
| |
| <p> |
| The presentation falls into two pieces. |
| |
| <p> |
| <b>Part 1: user-defined address-range permission setting</b> |
| <p> |
| |
| Valgrind intercepts the client's <code>malloc</code>, |
| <code>free</code>, etc calls, watches system calls, and watches the |
| stack pointer move. This is currently the only way it knows about |
| which addresses are valid and which not. Sometimes the client program |
| knows extra information about its memory areas. For example, the |
| client could at some point know that all elements of an array are |
| out-of-date. We would like to be able to convey to Valgrind this |
| information that the array is now addressable-but-uninitialised, so |
| that Valgrind can then warn if elements are used before they get new |
| values. |
| |
| <p> |
| What I would like are some macros like this: |
| <pre> |
| VALGRIND_MAKE_NOACCESS(addr, len) |
| VALGRIND_MAKE_WRITABLE(addr, len) |
| VALGRIND_MAKE_READABLE(addr, len) |
| </pre> |
| and also, to check that memory is addressible/initialised, |
| <pre> |
| VALGRIND_CHECK_ADDRESSIBLE(addr, len) |
| VALGRIND_CHECK_INITIALISED(addr, len) |
| </pre> |
| |
| <p> |
| I then include in my sources a header defining these macros, rebuild |
| my app, run under Valgrind, and get user-defined checks. |
| |
| <p> |
| Now here's a neat trick. It's a nuisance to have to re-link the app |
| with some new library which implements the above macros. So the idea |
| is to define the macros so that the resulting executable is still |
| completely stand-alone, and can be run without Valgrind, in which case |
| the macros do nothing, but when run on Valgrind, the Right Thing |
| happens. How to do this? The idea is for these macros to turn into a |
| piece of inline assembly code, which (1) has no effect when run on the |
| real CPU, (2) is easily spotted by Valgrind's JITter, and (3) no sane |
| person would ever write, which is important for avoiding false matches |
| in (2). So here's a suggestion: |
| <pre> |
| VALGRIND_MAKE_NOACCESS(addr, len) |
| </pre> |
| becomes (roughly speaking) |
| <pre> |
| movl addr, %eax |
| movl len, %ebx |
| movl $1, %ecx -- 1 describes the action; MAKE_WRITABLE might be |
| -- 2, etc |
| rorl $13, %ecx |
| rorl $19, %ecx |
| rorl $11, %eax |
| rorl $21, %eax |
| </pre> |
| The rotate sequences have no effect, and it's unlikely they would |
| appear for any other reason, but they define a unique byte-sequence |
| which the JITter can easily spot. Using the operand constraints |
| section at the end of a gcc inline-assembly statement, we can tell gcc |
| that the assembly fragment kills <code>%eax</code>, <code>%ebx</code>, |
| <code>%ecx</code> and the condition codes, so this fragment is made |
| harmless when not running on Valgrind, runs quickly when not on |
| Valgrind, and does not require any other library support. |
| |
| |
| <p> |
| <b>Part 2: using it to detect interference between stack variables</b> |
| <p> |
| |
| Currently Valgrind cannot detect errors of the following form: |
| <pre> |
| void fooble ( void ) |
| { |
| int a[10]; |
| int b[10]; |
| a[10] = 99; |
| } |
| </pre> |
| Now imagine rewriting this as |
| <pre> |
| void fooble ( void ) |
| { |
| int spacer0; |
| int a[10]; |
| int spacer1; |
| int b[10]; |
| int spacer2; |
| VALGRIND_MAKE_NOACCESS(&spacer0, sizeof(int)); |
| VALGRIND_MAKE_NOACCESS(&spacer1, sizeof(int)); |
| VALGRIND_MAKE_NOACCESS(&spacer2, sizeof(int)); |
| a[10] = 99; |
| } |
| </pre> |
| Now the invalid write is certain to hit <code>spacer0</code> or |
| <code>spacer1</code>, so Valgrind will spot the error. |
| |
| <p> |
| There are two complications. |
| |
| <p> |
| The first is that we don't want to annotate sources by hand, so the |
| Right Thing to do is to write a C/C++ parser, annotator, prettyprinter |
| which does this automatically, and run it on post-CPP'd C/C++ source. |
| See http://www.cacheprof.org for an example of a system which |
| transparently inserts another phase into the gcc/g++ compilation |
| route. The parser/prettyprinter is probably not as hard as it sounds; |
| I would write it in Haskell, a powerful functional language well |
| suited to doing symbolic computation, with which I am intimately |
| familar. There is already a C parser written in Haskell by someone in |
| the Haskell community, and that would probably be a good starting |
| point. |
| |
| <p> |
| The second complication is how to get rid of these |
| <code>NOACCESS</code> records inside Valgrind when the instrumented |
| function exits; after all, these refer to stack addresses and will |
| make no sense whatever when some other function happens to re-use the |
| same stack address range, probably shortly afterwards. I think I |
| would be inclined to define a special stack-specific macro |
| <pre> |
| VALGRIND_MAKE_NOACCESS_STACK(addr, len) |
| </pre> |
| which causes Valgrind to record the client's <code>%ESP</code> at the |
| time it is executed. Valgrind will then watch for changes in |
| <code>%ESP</code> and discard such records as soon as the protected |
| area is uncovered by an increase in <code>%ESP</code>. I hesitate |
| with this scheme only because it is potentially expensive, if there |
| are hundreds of such records, and considering that changes in |
| <code>%ESP</code> already require expensive messing with stack access |
| permissions. |
| |
| <p> |
| This is probably easier and more robust than for the instrumenter |
| program to try and spot all exit points for the procedure and place |
| suitable deallocation annotations there. Plus C++ procedures can |
| bomb out at any point if they get an exception, so spotting return |
| points at the source level just won't work at all. |
| |
| <p> |
| Although some work, it's all eminently doable, and it would make |
| Valgrind into an even-more-useful tool. |
| |
| |
| <p> |
| |
| |
| <hr width="100%"> |
| |
| <h2>Cache profiling</h2> |
| Valgrind is a very nice platform for doing cache profiling and other kinds of |
| simulation, because it converts horrible x86 instructions into nice clean |
| RISC-like UCode. For example, for cache profiling we are interested in |
| instructions that read and write memory; in UCode there are only four |
| instructions that do this: <code>LOAD</code>, <code>STORE</code>, |
| <code>FPU_R</code> and <code>FPU_W</code>. By contrast, because of the x86 |
| addressing modes, almost every instruction can read or write memory.<p> |
| |
| Most of the cache profiling machinery is in the file |
| <code>vg_cachesim.c</code>.<p> |
| |
| These notes are a somewhat haphazard guide to how Valgrind's cache profiling |
| works.<p> |
| |
| <h3>Cost centres</h3> |
| Valgrind gathers cache profiling about every instruction executed, |
| individually. Each instruction has a <b>cost centre</b> associated with it. |
| There are two kinds of cost centre: one for instructions that don't reference |
| memory (<code>iCC</code>), and one for instructions that do |
| (<code>idCC</code>): |
| |
| <pre> |
| typedef struct _CC { |
| ULong a; |
| ULong m1; |
| ULong m2; |
| } CC; |
| |
| typedef struct _iCC { |
| /* word 1 */ |
| UChar tag; |
| UChar instr_size; |
| |
| /* words 2+ */ |
| Addr instr_addr; |
| CC I; |
| } iCC; |
| |
| typedef struct _idCC { |
| /* word 1 */ |
| UChar tag; |
| UChar instr_size; |
| UChar data_size; |
| |
| /* words 2+ */ |
| Addr instr_addr; |
| CC I; |
| CC D; |
| } idCC; |
| </pre> |
| |
| Each <code>CC</code> has three fields <code>a</code>, <code>m1</code>, |
| <code>m2</code> for recording references, level 1 misses and level 2 misses. |
| Each of these is a 64-bit <code>ULong</code> -- the numbers can get very large, |
| ie. greater than 4.2 billion allowed by a 32-bit unsigned int.<p> |
| |
| A <code>iCC</code> has one <code>CC</code> for instruction cache accesses. A |
| <code>idCC</code> has two, one for instruction cache accesses, and one for data |
| cache accesses.<p> |
| |
| The <code>iCC</code> and <code>dCC</code> structs also store unchanging |
| information about the instruction: |
| <ul> |
| <li>An instruction-type identification tag (explained below)</li><p> |
| <li>Instruction size</li><p> |
| <li>Data reference size (<code>idCC</code> only)</li><p> |
| <li>Instruction address</li><p> |
| </ul> |
| |
| Note that data address is not one of the fields for <code>idCC</code>. This is |
| because for many memory-referencing instructions the data address can change |
| each time it's executed (eg. if it uses register-offset addressing). We have |
| to give this item to the cache simulation in a different way (see |
| Instrumentation section below). Some memory-referencing instructions do always |
| reference the same address, but we don't try to treat them specialy in order to |
| keep things simple.<p> |
| |
| Also note that there is only room for recording info about one data cache |
| access in an <code>idCC</code>. So what about instructions that do a read then |
| a write, such as: |
| |
| <blockquote><code>inc %(esi)</code></blockquote> |
| |
| In a write-allocate cache, as simulated by Valgrind, the write cannot miss, |
| since it immediately follows the read which will drag the block into the cache |
| if it's not already there. So the write access isn't really interesting, and |
| Valgrind doesn't record it. This means that Valgrind doesn't measure |
| memory references, but rather memory references that could miss in the cache. |
| This behaviour is the same as that used by the AMD Athlon hardware counters. |
| It also has the benefit of simplifying the implementation -- instructions that |
| read and write memory can be treated like instructions that read memory.<p> |
| |
| <h3>Storing cost-centres</h3> |
| Cost centres are stored in a way that makes them very cheap to lookup, which is |
| important since one is looked up for every original x86 instruction |
| executed.<p> |
| |
| Valgrind does JIT translations at the basic block level, and cost centres are |
| also setup and stored at the basic block level. By doing things carefully, we |
| store all the cost centres for a basic block in a contiguous array, and lookup |
| comes almost for free.<p> |
| |
| Consider this part of a basic block (for exposition purposes, pretend it's an |
| entire basic block): |
| |
| <pre> |
| movl $0x0,%eax |
| movl $0x99, -4(%ebp) |
| </pre> |
| |
| The translation to UCode looks like this: |
| |
| <pre> |
| MOVL $0x0, t20 |
| PUTL t20, %EAX |
| INCEIPo $5 |
| |
| LEA1L -4(t4), t14 |
| MOVL $0x99, t18 |
| STL t18, (t14) |
| INCEIPo $7 |
| </pre> |
| |
| The first step is to allocate the cost centres. This requires a preliminary |
| pass to count how many x86 instructions were in the basic block, and their |
| types (and thus sizes). UCode translations for single x86 instructions are |
| delimited by the <code>INCEIPo</code> instruction, the argument of which gives |
| the byte size of the instruction (note that lazy INCEIP updating is turned off |
| to allow this).<p> |
| |
| We can tell if an x86 instruction references memory by looking for |
| <code>LDL</code> and <code>STL</code> UCode instructions, and thus what kind of |
| cost centre is required. From this we can determine how many cost centres we |
| need for the basic block, and their sizes. We can then allocate them in a |
| single array.<p> |
| |
| Consider the example code above. After the preliminary pass, we know we need |
| two cost centres, one <code>iCC</code> and one <code>dCC</code>. So we |
| allocate an array to store these which looks like this: |
| |
| <pre> |
| |(uninit)| tag (1 byte) |
| |(uninit)| instr_size (1 bytes) |
| |(uninit)| (padding) (2 bytes) |
| |(uninit)| instr_addr (4 bytes) |
| |(uninit)| I.a (8 bytes) |
| |(uninit)| I.m1 (8 bytes) |
| |(uninit)| I.m2 (8 bytes) |
| |
| |(uninit)| tag (1 byte) |
| |(uninit)| instr_size (1 bytes) |
| |(uninit)| (padding) (2 bytes) |
| |(uninit)| instr_addr (4 bytes) |
| |(uninit)| I.a (8 bytes) |
| |(uninit)| I.m1 (8 bytes) |
| |(uninit)| I.m2 (8 bytes) |
| |(uninit)| D.a (8 bytes) |
| |(uninit)| D.m1 (8 bytes) |
| |(uninit)| D.m2 (8 bytes) |
| </pre> |
| |
| (We can see now why we need tags to distinguish between the two types of cost |
| centres.)<p> |
| |
| We also record the size of the array. We look up the debug info of the first |
| instruction in the basic block, and then stick the array into a table indexed |
| by filename and function name. This makes it easy to dump the information |
| quickly to file at the end.<p> |
| |
| <h3>Instrumentation</h3> |
| The instrumentation pass has two main jobs: |
| |
| <ol> |
| <li>Fill in the gaps in the allocated cost centres.</li><p> |
| <li>Add UCode to call the cache simulator for each instruction.</li><p> |
| </ol> |
| |
| The instrumentation pass steps through the UCode and the cost centres in |
| tandem. As each original x86 instruction's UCode is processed, the appropriate |
| gaps in the instructions cost centre are filled in, for example: |
| |
| <pre> |
| |INSTR_CC| tag (1 byte) |
| |5 | instr_size (1 bytes) |
| |(uninit)| (padding) (2 bytes) |
| |i_addr1 | instr_addr (4 bytes) |
| |0 | I.a (8 bytes) |
| |0 | I.m1 (8 bytes) |
| |0 | I.m2 (8 bytes) |
| |
| |READ_CC | tag (1 byte) |
| |7 | instr_size (1 bytes) |
| |(uninit)| (padding) (2 bytes) |
| |i_addr2 | instr_addr (4 bytes) |
| |0 | I.a (8 bytes) |
| |0 | I.m1 (8 bytes) |
| |0 | I.m2 (8 bytes) |
| |0 | D.a (8 bytes) |
| |0 | D.m1 (8 bytes) |
| |0 | D.m2 (8 bytes) |
| </pre> |
| |
| (Note that this step is not performed if a basic block is re-translated; see |
| <a href="#retranslations">here</a> for more information.)<p> |
| |
| GCC inserts padding before the <code>instr_size</code> field so that it is word |
| aligned.<p> |
| |
| The instrumentation added to call the cache simulation function looks like this |
| (instrumentation is indented to distinguish it from the original UCode): |
| |
| <pre> |
| MOVL $0x0, t20 |
| PUTL t20, %EAX |
| PUSHL %eax |
| PUSHL %ecx |
| PUSHL %edx |
| MOVL $0x4091F8A4, t46 # address of 1st CC |
| PUSHL t46 |
| CALLMo $0x12 # second cachesim function |
| CLEARo $0x4 |
| POPL %edx |
| POPL %ecx |
| POPL %eax |
| INCEIPo $5 |
| |
| LEA1L -4(t4), t14 |
| MOVL $0x99, t18 |
| MOVL t14, t42 |
| STL t18, (t14) |
| PUSHL %eax |
| PUSHL %ecx |
| PUSHL %edx |
| PUSHL t42 |
| MOVL $0x4091F8C4, t44 # address of 2nd CC |
| PUSHL t44 |
| CALLMo $0x13 # second cachesim function |
| CLEARo $0x8 |
| POPL %edx |
| POPL %ecx |
| POPL %eax |
| INCEIPo $7 |
| </pre> |
| |
| Consider the first instruction's UCode. Each call is surrounded by three |
| <code>PUSHL</code> and <code>POPL</code> instructions to save and restore the |
| caller-save registers. Then the address of the instruction's cost centre is |
| pushed onto the stack, to be the first argument to the cache simulation |
| function. The address is known at this point because we are doing a |
| simultaneous pass through the cost centre array. This means the cost centre |
| lookup for each instruction is almost free (just the cost of pushing an |
| argument for a function call). Then the call to the cache simulation function |
| for non-memory-reference instructions is made (note that the |
| <code>CALLMo</code> UInstruction takes an offset into a table of predefined |
| functions; it is not an absolute address), and the single argument is |
| <code>CLEAR</code>ed from the stack.<p> |
| |
| The second instruction's UCode is similar. The only difference is that, as |
| mentioned before, we have to pass the address of the data item referenced to |
| the cache simulation function too. This explains the <code>MOVL t14, |
| t42</code> and <code>PUSHL t42</code> UInstructions. (Note that the seemingly |
| redundant <code>MOV</code>ing will probably be optimised away during register |
| allocation.)<p> |
| |
| Note that instead of storing unchanging information about each instruction |
| (instruction size, data size, etc) in its cost centre, we could have passed in |
| these arguments to the simulation function. But this would slow the calls down |
| (two or three extra arguments pushed onto the stack). Also it would bloat the |
| UCode instrumentation by amounts similar to the space required for them in the |
| cost centre; bloated UCode would also fill the translation cache more quickly, |
| requiring more translations for large programs and slowing them down more.<p> |
| |
| <a name="retranslations"></a> |
| <h3>Handling basic block retranslations</h3> |
| The above description ignores one complication. Valgrind has a limited size |
| cache for basic block translations; if it fills up, old translations are |
| discarded. If a discarded basic block is executed again, it must be |
| re-translated.<p> |
| |
| However, we can't use this approach for profiling -- we can't throw away cost |
| centres for instructions in the middle of execution! So when a basic block is |
| translated, we first look for its cost centre array in the hash table. If |
| there is no cost centre array, it must be the first translation, so we proceed |
| as described above. But if there is a cost centre array already, it must be a |
| retranslation. In this case, we skip the cost centre allocation and |
| initialisation steps, but still do the UCode instrumentation step.<p> |
| |
| <h3>The cache simulation</h3> |
| The cache simulation is fairly straightforward. It just tracks which memory |
| blocks are in the cache at the moment (it doesn't track the contents, since |
| that is irrelevant).<p> |
| |
| The interface to the simulation is quite clean. The functions called from the |
| UCode contain calls to the simulation functions in the files |
| <Code>vg_cachesim_{I1,D1,L2}.c</code>; these calls are inlined so that only |
| one function call is done per simulated x86 instruction. The file |
| <code>vg_cachesim.c</code> simply <code>#include</code>s the three files |
| containing the simulation, which makes plugging in new cache simulations is |
| very easy -- you just replace the three files and recompile.<p> |
| |
| <h3>Output</h3> |
| Output is fairly straightforward, basically printing the cost centre for every |
| instruction, grouped by files and functions. Total counts (eg. total cache |
| accesses, total L1 misses) are calculated when traversing this structure rather |
| than during execution, to save time; the cache simulation functions are called |
| so often that even one or two extra adds can make a sizeable difference.<p> |
| |
| Input file has the following format: |
| |
| <pre> |
| file ::= desc_line* cmd_line events_line data_line+ summary_line |
| desc_line ::= "desc:" ws? non_nl_string |
| cmd_line ::= "cmd:" ws? cmd |
| events_line ::= "events:" ws? (event ws)+ |
| data_line ::= file_line | fn_line | count_line |
| file_line ::= ("fl=" | "fi=" | "fe=") filename |
| fn_line ::= "fn=" fn_name |
| count_line ::= line_num ws? (count ws)+ |
| summary_line ::= "summary:" ws? (count ws)+ |
| count ::= num | "." |
| </pre> |
| |
| Where: |
| |
| <ul> |
| <li><code>non_nl_string</code> is any string not containing a newline.</li><p> |
| <li><code>cmd</code> is a command line invocation.</li><p> |
| <li><code>filename</code> and <code>fn_name</code> can be anything.</li><p> |
| <li><code>num</code> and <code>line_num</code> are decimal numbers.</li><p> |
| <li><code>ws</code> is whitespace.</li><p> |
| <li><code>nl</code> is a newline.</li><p> |
| </ul> |
| |
| The contents of the "desc:" lines is printed out at the top of the summary. |
| This is a generic way of providing simulation specific information, eg. for |
| giving the cache configuration for cache simulation.<p> |
| |
| Counts can be "." to represent "N/A", eg. the number of write misses for an |
| instruction that doesn't write to memory.<p> |
| |
| The number of counts in each <code>line</code> and the |
| <code>summary_line</code> should not exceed the number of events in the |
| <code>event_line</code>. If the number in each <code>line</code> is less, |
| vg_annotate treats those missing as though they were a "." entry. <p> |
| |
| A <code>file_line</code> changes the current file name. A <code>fn_line</code> |
| changes the current function name. A <code>count_line</code> contains counts |
| that pertain to the current filename/fn_name. A "fn=" <code>file_line</code> |
| and a <code>fn_line</code> must appear before any <code>count_line</code>s to |
| give the context of the first <code>count_line</code>s.<p> |
| |
| Each <code>file_line</code> should be immediately followed by a |
| <code>fn_line</code>. "fi=" <code>file_lines</code> are used to switch |
| filenames for inlined functions; "fe=" <code>file_lines</code> are similar, but |
| are put at the end of a basic block in which the file name hasn't been switched |
| back to the original file name. (fi and fe lines behave the same, they are |
| only distinguished to help debugging.)<p> |
| |
| |
| <h3>Summary of performance features</h3> |
| Quite a lot of work has gone into making the profiling as fast as possible. |
| This is a summary of the important features: |
| |
| <ul> |
| <li>The basic block-level cost centre storage allows almost free cost centre |
| lookup.</li><p> |
| |
| <li>Only one function call is made per instruction simulated; even this |
| accounts for a sizeable percentage of execution time, but it seems |
| unavoidable if we want flexibility in the cache simulator.</li><p> |
| |
| <li>Unchanging information about an instruction is stored in its cost centre, |
| avoiding unnecessary argument pushing, and minimising UCode |
| instrumentation bloat.</li><p> |
| |
| <li>Summary counts are calculated at the end, rather than during |
| execution.</li><p> |
| |
| <li>The <code>cachegrind.out</code> output files can contain huge amounts of |
| information; file format was carefully chosen to minimise file |
| sizes.</li><p> |
| </ul> |
| |
| |
| <h3>Annotation</h3> |
| Annotation is done by vg_annotate. It is a fairly straightforward Perl script |
| that slurps up all the cost centres, and then runs through all the chosen |
| source files, printing out cost centres with them. It too has been carefully |
| optimised. |
| |
| |
| <h3>Similar work, extensions</h3> |
| It would be relatively straightforward to do other simulations and obtain |
| line-by-line information about interesting events. A good example would be |
| branch prediction -- all branches could be instrumented to interact with a |
| branch prediction simulator, using very similar techniques to those described |
| above.<p> |
| |
| In particular, vg_annotate would not need to change -- the file format is such |
| that it is not specific to the cache simulation, but could be used for any kind |
| of line-by-line information. The only part of vg_annotate that is specific to |
| the cache simulation is the name of the input file |
| (<code>cachegrind.out</code>), although it would be very simple to add an |
| option to control this.<p> |
| |
| </body> |
| </html> |