sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 1 | <html> |
| 2 | <head> |
| 3 | <style type="text/css"> |
| 4 | body { background-color: #ffffff; |
| 5 | color: #000000; |
| 6 | font-family: Times, Helvetica, Arial; |
| 7 | font-size: 14pt} |
| 8 | h4 { margin-bottom: 0.3em} |
| 9 | code { color: #000000; |
| 10 | font-family: Courier; |
| 11 | font-size: 13pt } |
| 12 | pre { color: #000000; |
| 13 | font-family: Courier; |
| 14 | font-size: 13pt } |
| 15 | a:link { color: #0000C0; |
| 16 | text-decoration: none; } |
| 17 | a:visited { color: #0000C0; |
| 18 | text-decoration: none; } |
| 19 | a:active { color: #0000C0; |
| 20 | text-decoration: none; } |
| 21 | </style> |
| 22 | <title>The design and implementation of Valgrind</title> |
| 23 | </head> |
| 24 | |
| 25 | <body bgcolor="#ffffff"> |
| 26 | |
| 27 | <a name="title"> </a> |
| 28 | <h1 align=center>The design and implementation of Valgrind</h1> |
| 29 | |
| 30 | <center> |
| 31 | Detailed technical notes for hackers, maintainers and the |
| 32 | overly-curious<br> |
| 33 | These notes pertain to snapshot 20020306<br> |
| 34 | <p> |
| 35 | <a href="mailto:jseward@acm.org">jseward@acm.org<br> |
| 36 | <a href="http://developer.kde.org/~sewardj">http://developer.kde.org/~sewardj</a><br> |
| 37 | <a href="http://www.muraroa.demon.co.uk">http://www.muraroa.demon.co.uk</a><br> |
| 38 | Copyright © 2000-2002 Julian Seward |
| 39 | <p> |
| 40 | Valgrind is licensed under the GNU General Public License, |
| 41 | version 2<br> |
| 42 | An open-source tool for finding memory-management problems in |
| 43 | x86 GNU/Linux executables. |
| 44 | </center> |
| 45 | |
| 46 | <p> |
| 47 | |
| 48 | |
| 49 | |
| 50 | |
| 51 | <hr width="100%"> |
| 52 | |
| 53 | <h2>Introduction</h2> |
| 54 | |
| 55 | This document contains a detailed, highly-technical description of the |
| 56 | internals of Valgrind. This is not the user manual; if you are an |
| 57 | end-user of Valgrind, you do not want to read this. Conversely, if |
| 58 | you really are a hacker-type and want to know how it works, I assume |
| 59 | that you have read the user manual thoroughly. |
| 60 | <p> |
| 61 | You may need to read this document several times, and carefully. Some |
| 62 | important things, I only say once. |
| 63 | |
| 64 | |
| 65 | <h3>History</h3> |
| 66 | |
| 67 | Valgrind came into public view in late Feb 2002. However, it has been |
| 68 | under contemplation for a very long time, perhaps seriously for about |
| 69 | five years. Somewhat over two years ago, I started working on the x86 |
| 70 | code generator for the Glasgow Haskell Compiler |
| 71 | (http://www.haskell.org/ghc), gaining familiarity with x86 internals |
| 72 | on the way. I then did Cacheprof (http://www.cacheprof.org), gaining |
| 73 | further x86 experience. Some time around Feb 2000 I started |
| 74 | experimenting with a user-space x86 interpreter for x86-Linux. This |
| 75 | worked, but it was clear that a JIT-based scheme would be necessary to |
| 76 | give reasonable performance for Valgrind. Design work for the JITter |
| 77 | started in earnest in Oct 2000, and by early 2001 I had an x86-to-x86 |
| 78 | dynamic translator which could run quite large programs. This |
| 79 | translator was in a sense pointless, since it did not do any |
| 80 | instrumentation or checking. |
| 81 | |
| 82 | <p> |
| 83 | Most of the rest of 2001 was taken up designing and implementing the |
| 84 | instrumentation scheme. The main difficulty, which consumed a lot |
| 85 | of effort, was to design a scheme which did not generate large numbers |
| 86 | of false uninitialised-value warnings. By late 2001 a satisfactory |
| 87 | scheme had been arrived at, and I started to test it on ever-larger |
| 88 | programs, with an eventual eye to making it work well enough so that |
| 89 | it was helpful to folks debugging the upcoming version 3 of KDE. I've |
| 90 | used KDE since before version 1.0, and wanted to Valgrind to be an |
| 91 | indirect contribution to the KDE 3 development effort. At the start of |
| 92 | Feb 02 the kde-core-devel crew started using it, and gave a huge |
| 93 | amount of helpful feedback and patches in the space of three weeks. |
| 94 | Snapshot 20020306 is the result. |
| 95 | |
| 96 | <p> |
| 97 | In the best Unix tradition, or perhaps in the spirit of Fred Brooks' |
| 98 | depressing-but-completely-accurate epitaph "build one to throw away; |
| 99 | you will anyway", much of Valgrind is a second or third rendition of |
| 100 | the initial idea. The instrumentation machinery |
| 101 | (<code>vg_translate.c</code>, <code>vg_memory.c</code>) and core CPU |
| 102 | simulation (<code>vg_to_ucode.c</code>, <code>vg_from_ucode.c</code>) |
| 103 | have had three redesigns and rewrites; the register allocator, |
| 104 | low-level memory manager (<code>vg_malloc2.c</code>) and symbol table |
| 105 | reader (<code>vg_symtab2.c</code>) are on the second rewrite. In a |
| 106 | sense, this document serves to record some of the knowledge gained as |
| 107 | a result. |
| 108 | |
| 109 | |
| 110 | <h3>Design overview</h3> |
| 111 | |
| 112 | Valgrind is compiled into a Linux shared object, |
| 113 | <code>valgrind.so</code>, and also a dummy one, |
| 114 | <code>valgrinq.so</code>, of which more later. The |
| 115 | <code>valgrind</code> shell script adds <code>valgrind.so</code> to |
| 116 | the <code>LD_PRELOAD</code> list of extra libraries to be |
| 117 | loaded with any dynamically linked library. This is a standard trick, |
| 118 | one which I assume the <code>LD_PRELOAD</code> mechanism was developed |
| 119 | to support. |
| 120 | |
| 121 | <p> |
| 122 | <code>valgrind.so</code> |
| 123 | is linked with the <code>-z initfirst</code> flag, which requests that |
| 124 | its initialisation code is run before that of any other object in the |
| 125 | executable image. When this happens, valgrind gains control. The |
| 126 | real CPU becomes "trapped" in <code>valgrind.so</code> and the |
| 127 | translations it generates. The synthetic CPU provided by Valgrind |
| 128 | does, however, return from this initialisation function. So the |
| 129 | normal startup actions, orchestrated by the dynamic linker |
| 130 | <code>ld.so</code>, continue as usual, except on the synthetic CPU, |
| 131 | not the real one. Eventually <code>main</code> is run and returns, |
| 132 | and then the finalisation code of the shared objects is run, |
| 133 | presumably in inverse order to which they were initialised. Remember, |
| 134 | this is still all happening on the simulated CPU. Eventually |
| 135 | <code>valgrind.so</code>'s own finalisation code is called. It spots |
| 136 | this event, shuts down the simulated CPU, prints any error summaries |
| 137 | and/or does leak detection, and returns from the initialisation code |
| 138 | on the real CPU. At this point, in effect the real and synthetic CPUs |
| 139 | have merged back into one, Valgrind has lost control of the program, |
| 140 | and the program finally <code>exit()s</code> back to the kernel in the |
| 141 | usual way. |
| 142 | |
| 143 | <p> |
| 144 | The normal course of activity, one Valgrind has started up, is as |
| 145 | follows. Valgrind never runs any part of your program (usually |
| 146 | referred to as the "client"), not a single byte of it, directly. |
| 147 | Instead it uses function <code>VG_(translate)</code> to translate |
| 148 | basic blocks (BBs, straight-line sequences of code) into instrumented |
| 149 | translations, and those are run instead. The translations are stored |
| 150 | in the translation cache (TC), <code>vg_tc</code>, with the |
| 151 | translation table (TT), <code>vg_tt</code> supplying the |
| 152 | original-to-translation code address mapping. Auxiliary array |
| 153 | <code>VG_(tt_fast)</code> is used as a direct-map cache for fast |
| 154 | lookups in TT; it usually achieves a hit rate of around 98% and |
| 155 | facilitates an orig-to-trans lookup in 4 x86 insns, which is not bad. |
| 156 | |
| 157 | <p> |
| 158 | Function <code>VG_(dispatch)</code> in <code>vg_dispatch.S</code> is |
| 159 | the heart of the JIT dispatcher. Once a translated code address has |
| 160 | been found, it is executed simply by an x86 <code>call</code> |
| 161 | to the translation. At the end of the translation, the next |
| 162 | original code addr is loaded into <code>%eax</code>, and the |
| 163 | translation then does a <code>ret</code>, taking it back to the |
| 164 | dispatch loop, with, interestingly, zero branch mispredictions. |
| 165 | The address requested in <code>%eax</code> is looked up first in |
| 166 | <code>VG_(tt_fast)</code>, and, if not found, by calling C helper |
| 167 | <code>VG_(search_transtab)</code>. If there is still no translation |
| 168 | available, <code>VG_(dispatch)</code> exits back to the top-level |
| 169 | C dispatcher <code>VG_(toploop)</code>, which arranges for |
| 170 | <code>VG_(translate)</code> to make a new translation. All fairly |
| 171 | unsurprising, really. There are various complexities described below. |
| 172 | |
| 173 | <p> |
| 174 | The translator, orchestrated by <code>VG_(translate)</code>, is |
| 175 | complicated but entirely self-contained. It is described in great |
| 176 | detail in subsequent sections. Translations are stored in TC, with TT |
| 177 | tracking administrative information. The translations are subject to |
| 178 | an approximate LRU-based management scheme. With the current |
| 179 | settings, the TC can hold at most about 15MB of translations, and LRU |
| 180 | passes prune it to about 13.5MB. Given that the |
| 181 | orig-to-translation expansion ratio is about 13:1 to 14:1, this means |
| 182 | TC holds translations for more or less a megabyte of original code, |
| 183 | which generally comes to about 70000 basic blocks for C++ compiled |
| 184 | with optimisation on. Generating new translations is expensive, so it |
| 185 | is worth having a large TC to minimise the (capacity) miss rate. |
| 186 | |
| 187 | <p> |
| 188 | The dispatcher, <code>VG_(dispatch)</code>, receives hints from |
| 189 | the translations which allow it to cheaply spot all control |
| 190 | transfers corresponding to x86 <code>call</code> and <code>ret</code> |
| 191 | instructions. It has to do this in order to spot some special events: |
| 192 | <ul> |
| 193 | <li>Calls to <code>VG_(shutdown)</code>. This is Valgrind's cue to |
| 194 | exit. NOTE: actually this is done a different way; it should be |
| 195 | cleaned up. |
| 196 | <p> |
| 197 | <li>Returns of system call handlers, to the return address |
| 198 | <code>VG_(signalreturn_bogusRA)</code>. The signal simulator |
| 199 | needs to know when a signal handler is returning, so we spot |
| 200 | jumps (returns) to this address. |
| 201 | <p> |
| 202 | <li>Calls to <code>vg_trap_here</code>. All <code>malloc</code>, |
| 203 | <code>free</code>, etc calls that the client program makes are |
| 204 | eventually routed to a call to <code>vg_trap_here</code>, |
| 205 | and Valgrind does its own special thing with these calls. |
| 206 | In effect this provides a trapdoor, by which Valgrind can |
| 207 | intercept certain calls on the simulated CPU, run the call as it |
| 208 | sees fit itself (on the real CPU), and return the result to |
| 209 | the simulated CPU, quite transparently to the client program. |
| 210 | </ul> |
| 211 | Valgrind intercepts the client's <code>malloc</code>, |
| 212 | <code>free</code>, etc, |
| 213 | calls, so that it can store additional information. Each block |
| 214 | <code>malloc</code>'d by the client gives rise to a shadow block |
| 215 | in which Valgrind stores the call stack at the time of the |
| 216 | <code>malloc</code> |
| 217 | call. When the client calls <code>free</code>, Valgrind tries to |
| 218 | find the shadow block corresponding to the address passed to |
| 219 | <code>free</code>, and emits an error message if none can be found. |
| 220 | If it is found, the block is placed on the freed blocks queue |
| 221 | <code>vg_freed_list</code>, it is marked as inaccessible, and |
| 222 | its shadow block now records the call stack at the time of the |
| 223 | <code>free</code> call. Keeping <code>free</code>'d blocks in |
| 224 | this queue allows Valgrind to spot all (presumably invalid) accesses |
| 225 | to them. However, once the volume of blocks in the free queue |
| 226 | exceeds <code>VG_(clo_freelist_vol)</code>, blocks are finally |
| 227 | removed from the queue. |
| 228 | |
| 229 | <p> |
| 230 | Keeping track of A and V bits (note: if you don't know what these are, |
| 231 | you haven't read the user guide carefully enough) for memory is done |
| 232 | in <code>vg_memory.c</code>. This implements a sparse array structure |
| 233 | which covers the entire 4G address space in a way which is reasonably |
| 234 | fast and reasonably space efficient. The 4G address space is divided |
| 235 | up into 64K sections, each covering 64Kb of address space. Given a |
| 236 | 32-bit address, the top 16 bits are used to select one of the 65536 |
| 237 | entries in <code>VG_(primary_map)</code>. The resulting "secondary" |
| 238 | (<code>SecMap</code>) holds A and V bits for the 64k of address space |
| 239 | chunk corresponding to the lower 16 bits of the address. |
| 240 | |
| 241 | |
| 242 | <h3>Design decisions</h3> |
| 243 | |
| 244 | Some design decisions were motivated by the need to make Valgrind |
| 245 | debuggable. Imagine you are writing a CPU simulator. It works fairly |
| 246 | well. However, you run some large program, like Netscape, and after |
| 247 | tens of millions of instructions, it crashes. How can you figure out |
| 248 | where in your simulator the bug is? |
| 249 | |
| 250 | <p> |
| 251 | Valgrind's answer is: cheat. Valgrind is designed so that it is |
| 252 | possible to switch back to running the client program on the real |
| 253 | CPU at any point. Using the <code>--stop-after= </code> flag, you can |
| 254 | ask Valgrind to run just some number of basic blocks, and then |
| 255 | run the rest of the way on the real CPU. If you are searching for |
| 256 | a bug in the simulated CPU, you can use this to do a binary search, |
| 257 | which quickly leads you to the specific basic block which is |
| 258 | causing the problem. |
| 259 | |
| 260 | <p> |
| 261 | This is all very handy. It does constrain the design in certain |
| 262 | unimportant ways. Firstly, the layout of memory, when viewed from the |
| 263 | client's point of view, must be identical regardless of whether it is |
| 264 | running on the real or simulated CPU. This means that Valgrind can't |
| 265 | do pointer swizzling -- well, no great loss -- and it can't run on |
| 266 | the same stack as the client -- again, no great loss. |
| 267 | Valgrind operates on its own stack, <code>VG_(stack)</code>, which |
| 268 | it switches to at startup, temporarily switching back to the client's |
| 269 | stack when doing system calls for the client. |
| 270 | |
| 271 | <p> |
| 272 | Valgrind also receives signals on its own stack, |
| 273 | <code>VG_(sigstack)</code>, but for different gruesome reasons |
| 274 | discussed below. |
| 275 | |
| 276 | <p> |
| 277 | This nice clean switch-back-to-the-real-CPU-whenever-you-like story |
| 278 | is muddied by signals. Problem is that signals arrive at arbitrary |
| 279 | times and tend to slightly perturb the basic block count, with the |
| 280 | result that you can get close to the basic block causing a problem but |
| 281 | can't home in on it exactly. My kludgey hack is to define |
| 282 | <code>SIGNAL_SIMULATION</code> to 1 towards the bottom of |
| 283 | <code>vg_syscall_mem.c</code>, so that signal handlers are run on the |
| 284 | real CPU and don't change the BB counts. |
| 285 | |
| 286 | <p> |
| 287 | A second hole in the switch-back-to-real-CPU story is that Valgrind's |
| 288 | way of delivering signals to the client is different from that of the |
| 289 | kernel. Specifically, the layout of the signal delivery frame, and |
| 290 | the mechanism used to detect a sighandler returning, are different. |
| 291 | So you can't expect to make the transition inside a sighandler and |
| 292 | still have things working, but in practice that's not much of a |
| 293 | restriction. |
| 294 | |
| 295 | <p> |
| 296 | Valgrind's implementation of <code>malloc</code>, <code>free</code>, |
| 297 | etc, (in <code>vg_clientmalloc.c</code>, not the low-level stuff in |
| 298 | <code>vg_malloc2.c</code>) is somewhat complicated by the need to |
| 299 | handle switching back at arbitrary points. It does work tho. |
| 300 | |
| 301 | |
| 302 | |
| 303 | <h3>Correctness</h3> |
| 304 | |
| 305 | There's only one of me, and I have a Real Life (tm) as well as hacking |
| 306 | Valgrind [allegedly :-]. That means I don't have time to waste |
| 307 | chasing endless bugs in Valgrind. My emphasis is therefore on doing |
| 308 | everything as simply as possible, with correctness, stability and |
| 309 | robustness being the number one priority, more important than |
| 310 | performance or functionality. As a result: |
| 311 | <ul> |
| 312 | <li>The code is absolutely loaded with assertions, and these are |
| 313 | <b>permanently enabled.</b> I have no plan to remove or disable |
| 314 | them later. Over the past couple of months, as valgrind has |
| 315 | become more widely used, they have shown their worth, pulling |
| 316 | up various bugs which would otherwise have appeared as |
| 317 | hard-to-find segmentation faults. |
| 318 | <p> |
| 319 | I am of the view that it's acceptable to spend 5% of the total |
| 320 | running time of your valgrindified program doing assertion checks |
| 321 | and other internal sanity checks. |
| 322 | <p> |
| 323 | <li>Aside from the assertions, valgrind contains various sets of |
| 324 | internal sanity checks, which get run at varying frequencies |
| 325 | during normal operation. <code>VG_(do_sanity_checks)</code> |
| 326 | runs every 1000 basic blocks, which means 500 to 2000 times/second |
| 327 | for typical machines at present. It checks that Valgrind hasn't |
| 328 | overrun its private stack, and does some simple checks on the |
| 329 | memory permissions maps. Once every 25 calls it does some more |
| 330 | extensive checks on those maps. Etc, etc. |
| 331 | <p> |
| 332 | The following components also have sanity check code, which can |
| 333 | be enabled to aid debugging: |
| 334 | <ul> |
| 335 | <li>The low-level memory-manager |
| 336 | (<code>VG_(mallocSanityCheckArena)</code>). This does a |
| 337 | complete check of all blocks and chains in an arena, which |
| 338 | is very slow. Is not engaged by default. |
| 339 | <p> |
| 340 | <li>The symbol table reader(s): various checks to ensure |
| 341 | uniqueness of mappings; see <code>VG_(read_symbols)</code> |
| 342 | for a start. Is permanently engaged. |
| 343 | <p> |
| 344 | <li>The A and V bit tracking stuff in <code>vg_memory.c</code>. |
| 345 | This can be compiled with cpp symbol |
| 346 | <code>VG_DEBUG_MEMORY</code> defined, which removes all the |
| 347 | fast, optimised cases, and uses simple-but-slow fallbacks |
| 348 | instead. Not engaged by default. |
| 349 | <p> |
| 350 | <li>Ditto <code>VG_DEBUG_LEAKCHECK</code>. |
| 351 | <p> |
| 352 | <li>The JITter parses x86 basic blocks into sequences of |
| 353 | UCode instructions. It then sanity checks each one with |
| 354 | <code>VG_(saneUInstr)</code> and sanity checks the sequence |
| 355 | as a whole with <code>VG_(saneUCodeBlock)</code>. This stuff |
| 356 | is engaged by default, and has caught some way-obscure bugs |
| 357 | in the simulated CPU machinery in its time. |
| 358 | <p> |
| 359 | <li>The system call wrapper does |
| 360 | <code>VG_(first_and_last_secondaries_look_plausible)</code> after |
| 361 | every syscall; this is known to pick up bugs in the syscall |
| 362 | wrappers. Engaged by default. |
| 363 | <p> |
| 364 | <li>The main dispatch loop, in <code>VG_(dispatch)</code>, checks |
| 365 | that translations do not set <code>%ebp</code> to any value |
| 366 | different from <code>VG_EBP_DISPATCH_CHECKED</code> or |
| 367 | <code>& VG_(baseBlock)</code>. In effect this test is free, |
| 368 | and is permanently engaged. |
| 369 | <p> |
| 370 | <li>There are a couple of ifdefed-out consistency checks I |
| 371 | inserted whilst debugging the new register allocater, |
| 372 | <code>vg_do_register_allocation</code>. |
| 373 | </ul> |
| 374 | <p> |
| 375 | <li>I try to avoid techniques, algorithms, mechanisms, etc, for which |
| 376 | I can supply neither a convincing argument that they are correct, |
| 377 | nor sanity-check code which might pick up bugs in my |
| 378 | implementation. I don't always succeed in this, but I try. |
| 379 | Basically the idea is: avoid techniques which are, in practice, |
| 380 | unverifiable, in some sense. When doing anything, always have in |
| 381 | mind: "how can I verify that this is correct?" |
| 382 | </ul> |
| 383 | |
| 384 | <p> |
| 385 | Some more specific things are: |
| 386 | |
| 387 | <ul> |
| 388 | <li>Valgrind runs in the same namespace as the client, at least from |
| 389 | <code>ld.so</code>'s point of view, and it therefore absolutely |
| 390 | had better not export any symbol with a name which could clash |
| 391 | with that of the client or any of its libraries. Therefore, all |
| 392 | globally visible symbols exported from <code>valgrind.so</code> |
| 393 | are defined using the <code>VG_</code> CPP macro. As you'll see |
| 394 | from <code>vg_constants.h</code>, this appends some arbitrary |
| 395 | prefix to the symbol, in order that it be, we hope, globally |
| 396 | unique. Currently the prefix is <code>vgPlain_</code>. For |
| 397 | convenience there are also <code>VGM_</code>, <code>VGP_</code> |
| 398 | and <code>VGOFF_</code>. All locally defined symbols are declared |
| 399 | <code>static</code> and do not appear in the final shared object. |
| 400 | <p> |
| 401 | To check this, I periodically do |
| 402 | <code>nm valgrind.so | grep " T "</code>, |
| 403 | which shows you all the globally exported text symbols. |
| 404 | They should all have an approved prefix, except for those like |
| 405 | <code>malloc</code>, <code>free</code>, etc, which we deliberately |
| 406 | want to shadow and take precedence over the same names exported |
| 407 | from <code>glibc.so</code>, so that valgrind can intercept those |
| 408 | calls easily. Similarly, <code>nm valgrind.so | grep " D "</code> |
| 409 | allows you to find any rogue data-segment symbol names. |
| 410 | <p> |
| 411 | <li>Valgrind tries, and almost succeeds, in being completely |
| 412 | independent of all other shared objects, in particular of |
| 413 | <code>glibc.so</code>. For example, we have our own low-level |
| 414 | memory manager in <code>vg_malloc2.c</code>, which is a fairly |
| 415 | standard malloc/free scheme augmented with arenas, and |
| 416 | <code>vg_mylibc.c</code> exports reimplementations of various bits |
| 417 | and pieces you'd normally get from the C library. |
| 418 | <p> |
| 419 | Why all the hassle? Because imagine the potential chaos of both |
| 420 | the simulated and real CPUs executing in <code>glibc.so</code>. |
| 421 | It just seems simpler and cleaner to be completely self-contained, |
| 422 | so that only the simulated CPU visits <code>glibc.so</code>. In |
| 423 | practice it's not much hassle anyway. Also, valgrind starts up |
| 424 | before glibc has a chance to initialise itself, and who knows what |
| 425 | difficulties that could lead to. Finally, glibc has definitions |
| 426 | for some types, specifically <code>sigset_t</code>, which conflict |
| 427 | (are different from) the Linux kernel's idea of same. When |
| 428 | Valgrind wants to fiddle around with signal stuff, it wants to |
| 429 | use the kernel's definitions, not glibc's definitions. So it's |
| 430 | simplest just to keep glibc out of the picture entirely. |
| 431 | <p> |
| 432 | To find out which glibc symbols are used by Valgrind, reinstate |
| 433 | the link flags <code>-nostdlib -Wl,-no-undefined</code>. This |
| 434 | causes linking to fail, but will tell you what you depend on. |
| 435 | I have mostly, but not entirely, got rid of the glibc |
| 436 | dependencies; what remains is, IMO, fairly harmless. AFAIK the |
| 437 | current dependencies are: <code>memset</code>, |
| 438 | <code>memcmp</code>, <code>stat</code>, <code>system</code>, |
| 439 | <code>sbrk</code>, <code>setjmp</code> and <code>longjmp</code>. |
| 440 | |
| 441 | <p> |
| 442 | <li>Similarly, valgrind should not really import any headers other |
| 443 | than the Linux kernel headers, since it knows of no API other than |
| 444 | the kernel interface to talk to. At the moment this is really not |
| 445 | in a good state, and <code>vg_syscall_mem</code> imports, via |
| 446 | <code>vg_unsafe.h</code>, a significant number of C-library |
| 447 | headers so as to know the sizes of various structs passed across |
| 448 | the kernel boundary. This is of course completely bogus, since |
| 449 | there is no guarantee that the C library's definitions of these |
| 450 | structs matches those of the kernel. I have started to sort this |
| 451 | out using <code>vg_kerneliface.h</code>, into which I had intended |
| 452 | to copy all kernel definitions which valgrind could need, but this |
| 453 | has not gotten very far. At the moment it mostly contains |
| 454 | definitions for <code>sigset_t</code> and <code>struct |
| 455 | sigaction</code>, since the kernel's definition for these really |
| 456 | does clash with glibc's. I plan to use a <code>vki_</code> prefix |
| 457 | on all these types and constants, to denote the fact that they |
| 458 | pertain to <b>V</b>algrind's <b>K</b>ernel <b>I</b>nterface. |
| 459 | <p> |
| 460 | Another advantage of having a <code>vg_kerneliface.h</code> file |
| 461 | is that it makes it simpler to interface to a different kernel. |
| 462 | Once can, for example, easily imagine writing a new |
| 463 | <code>vg_kerneliface.h</code> for FreeBSD, or x86 NetBSD. |
| 464 | |
| 465 | </ul> |
| 466 | |
| 467 | <h3>Current limitations</h3> |
| 468 | |
| 469 | No threads. I think fixing this is close to a research-grade problem. |
| 470 | <p> |
| 471 | No MMX. Fixing this should be relatively easy, using the same giant |
| 472 | trick used for x86 FPU instructions. See below. |
| 473 | <p> |
| 474 | Support for weird (non-POSIX) signal stuff is patchy. Does anybody |
| 475 | care? |
| 476 | <p> |
| 477 | |
| 478 | |
| 479 | |
| 480 | |
| 481 | <hr width="100%"> |
| 482 | |
| 483 | <h2>The instrumenting JITter</h2> |
| 484 | |
| 485 | This really is the heart of the matter. We begin with various side |
| 486 | issues. |
| 487 | |
| 488 | <h3>Run-time storage, and the use of host registers</h3> |
| 489 | |
| 490 | Valgrind translates client (original) basic blocks into instrumented |
| 491 | basic blocks, which live in the translation cache TC, until either the |
| 492 | client finishes or the translations are ejected from TC to make room |
| 493 | for newer ones. |
| 494 | <p> |
| 495 | Since it generates x86 code in memory, Valgrind has complete control |
| 496 | of the use of registers in the translations. Now pay attention. I |
| 497 | shall say this only once, and it is important you understand this. In |
| 498 | what follows I will refer to registers in the host (real) cpu using |
| 499 | their standard names, <code>%eax</code>, <code>%edi</code>, etc. I |
| 500 | refer to registers in the simulated CPU by capitalising them: |
| 501 | <code>%EAX</code>, <code>%EDI</code>, etc. These two sets of |
| 502 | registers usually bear no direct relationship to each other; there is |
| 503 | no fixed mapping between them. This naming scheme is used fairly |
| 504 | consistently in the comments in the sources. |
| 505 | <p> |
| 506 | Host registers, once things are up and running, are used as follows: |
| 507 | <ul> |
| 508 | <li><code>%esp</code>, the real stack pointer, points |
| 509 | somewhere in Valgrind's private stack area, |
| 510 | <code>VG_(stack)</code> or, transiently, into its signal delivery |
| 511 | stack, <code>VG_(sigstack)</code>. |
| 512 | <p> |
| 513 | <li><code>%edi</code> is used as a temporary in code generation; it |
| 514 | is almost always dead, except when used for the <code>Left</code> |
| 515 | value-tag operations. |
| 516 | <p> |
| 517 | <li><code>%eax</code>, <code>%ebx</code>, <code>%ecx</code>, |
| 518 | <code>%edx</code> and <code>%esi</code> are available to |
| 519 | Valgrind's register allocator. They are dead (carry unimportant |
| 520 | values) in between translations, and are live only in |
| 521 | translations. The one exception to this is <code>%eax</code>, |
| 522 | which, as mentioned far above, has a special significance to the |
| 523 | dispatch loop <code>VG_(dispatch)</code>: when a translation |
| 524 | returns to the dispatch loop, <code>%eax</code> is expected to |
| 525 | contain the original-code-address of the next translation to run. |
| 526 | The register allocator is so good at minimising spill code that |
| 527 | using five regs and not having to save/restore <code>%edi</code> |
| 528 | actually gives better code than allocating to <code>%edi</code> |
| 529 | as well, but then having to push/pop it around special uses. |
| 530 | <p> |
| 531 | <li><code>%ebp</code> points permanently at |
| 532 | <code>VG_(baseBlock)</code>. Valgrind's translations are |
| 533 | position-independent, partly because this is convenient, but also |
| 534 | because translations get moved around in TC as part of the LRUing |
| 535 | activity. <b>All</b> static entities which need to be referred to |
| 536 | from generated code, whether data or helper functions, are stored |
| 537 | starting at <code>VG_(baseBlock)</code> and are therefore reached |
| 538 | by indexing from <code>%ebp</code>. There is but one exception, |
| 539 | which is that by placing the value |
| 540 | <code>VG_EBP_DISPATCH_CHECKED</code> |
| 541 | in <code>%ebp</code> just before a return to the dispatcher, |
| 542 | the dispatcher is informed that the next address to run, |
| 543 | in <code>%eax</code>, requires special treatment. |
| 544 | <p> |
| 545 | <li>The real machine's FPU state is pretty much unimportant, for |
| 546 | reasons which will become obvious. Ditto its <code>%eflags</code> |
| 547 | register. |
| 548 | </ul> |
| 549 | |
| 550 | <p> |
| 551 | The state of the simulated CPU is stored in memory, in |
| 552 | <code>VG_(baseBlock)</code>, which is a block of 200 words IIRC. |
| 553 | Recall that <code>%ebp</code> points permanently at the start of this |
| 554 | block. Function <code>vg_init_baseBlock</code> decides what the |
| 555 | offsets of various entities in <code>VG_(baseBlock)</code> are to be, |
| 556 | and allocates word offsets for them. The code generator then emits |
| 557 | <code>%ebp</code> relative addresses to get at those things. The |
| 558 | sequence in which entities are allocated has been carefully chosen so |
| 559 | that the 32 most popular entities come first, because this means 8-bit |
| 560 | offsets can be used in the generated code. |
| 561 | |
| 562 | <p> |
| 563 | If I was clever, I could make <code>%ebp</code> point 32 words along |
| 564 | <code>VG_(baseBlock)</code>, so that I'd have another 32 words of |
| 565 | short-form offsets available, but that's just complicated, and it's |
| 566 | not important -- the first 32 words take 99% (or whatever) of the |
| 567 | traffic. |
| 568 | |
| 569 | <p> |
| 570 | Currently, the sequence of stuff in <code>VG_(baseBlock)</code> is as |
| 571 | follows: |
| 572 | <ul> |
| 573 | <li>9 words, holding the simulated integer registers, |
| 574 | <code>%EAX</code> .. <code>%EDI</code>, and the simulated flags, |
| 575 | <code>%EFLAGS</code>. |
| 576 | <p> |
| 577 | <li>Another 9 words, holding the V bit "shadows" for the above 9 regs. |
| 578 | <p> |
| 579 | <li>The <b>addresses</b> of various helper routines called from |
| 580 | generated code: |
| 581 | <code>VG_(helper_value_check4_fail)</code>, |
| 582 | <code>VG_(helper_value_check0_fail)</code>, |
| 583 | which register V-check failures, |
| 584 | <code>VG_(helperc_STOREV4)</code>, |
| 585 | <code>VG_(helperc_STOREV1)</code>, |
| 586 | <code>VG_(helperc_LOADV4)</code>, |
| 587 | <code>VG_(helperc_LOADV1)</code>, |
| 588 | which do stores and loads of V bits to/from the |
| 589 | sparse array which keeps track of V bits in memory, |
| 590 | and |
| 591 | <code>VGM_(handle_esp_assignment)</code>, which messes with |
| 592 | memory addressibility resulting from changes in <code>%ESP</code>. |
| 593 | <p> |
| 594 | <li>The simulated <code>%EIP</code>. |
| 595 | <p> |
| 596 | <li>24 spill words, for when the register allocator can't make it work |
| 597 | with 5 measly registers. |
| 598 | <p> |
| 599 | <li>Addresses of helpers <code>VG_(helperc_STOREV2)</code>, |
| 600 | <code>VG_(helperc_LOADV2)</code>. These are here because 2-byte |
| 601 | loads and stores are relatively rare, so are placed above the |
| 602 | magic 32-word offset boundary. |
| 603 | <p> |
| 604 | <li>For similar reasons, addresses of helper functions |
| 605 | <code>VGM_(fpu_write_check)</code> and |
| 606 | <code>VGM_(fpu_read_check)</code>, which handle the A/V maps |
| 607 | testing and changes required by FPU writes/reads. |
| 608 | <p> |
| 609 | <li>Some other boring helper addresses: |
| 610 | <code>VG_(helper_value_check2_fail)</code> and |
| 611 | <code>VG_(helper_value_check1_fail)</code>. These are probably |
| 612 | never emitted now, and should be removed. |
| 613 | <p> |
| 614 | <li>The entire state of the simulated FPU, which I believe to be |
| 615 | 108 bytes long. |
| 616 | <p> |
| 617 | <li>Finally, the addresses of various other helper functions in |
| 618 | <code>vg_helpers.S</code>, which deal with rare situations which |
| 619 | are tedious or difficult to generate code in-line for. |
| 620 | </ul> |
| 621 | |
| 622 | <p> |
| 623 | As a general rule, the simulated machine's state lives permanently in |
| 624 | memory at <code>VG_(baseBlock)</code>. However, the JITter does some |
| 625 | optimisations which allow the simulated integer registers to be |
| 626 | cached in real registers over multiple simulated instructions within |
| 627 | the same basic block. These are always flushed back into memory at |
| 628 | the end of every basic block, so that the in-memory state is |
| 629 | up-to-date between basic blocks. (This flushing is implied by the |
| 630 | statement above that the real machine's allocatable registers are |
| 631 | dead in between simulated blocks). |
| 632 | |
| 633 | |
| 634 | <h3>Startup, shutdown, and system calls</h3> |
| 635 | |
| 636 | Getting into of Valgrind (<code>VG_(startup)</code>, called from |
| 637 | <code>valgrind.so</code>'s initialisation section), really means |
| 638 | copying the real CPU's state into <code>VG_(baseBlock)</code>, and |
| 639 | then installing our own stack pointer, etc, into the real CPU, and |
| 640 | then starting up the JITter. Exiting valgrind involves copying the |
| 641 | simulated state back to the real state. |
| 642 | |
| 643 | <p> |
| 644 | Unfortunately, there's a complication at startup time. Problem is |
| 645 | that at the point where we need to take a snapshot of the real CPU's |
| 646 | state, the offsets in <code>VG_(baseBlock)</code> are not set up yet, |
| 647 | because to do so would involve disrupting the real machine's state |
| 648 | significantly. The way round this is to dump the real machine's state |
| 649 | into a temporary, static block of memory, |
| 650 | <code>VG_(m_state_static)</code>. We can then set up the |
| 651 | <code>VG_(baseBlock)</code> offsets at our leisure, and copy into it |
| 652 | from <code>VG_(m_state_static)</code> at some convenient later time. |
| 653 | This copying is done by |
| 654 | <code>VG_(copy_m_state_static_to_baseBlock)</code>. |
| 655 | |
| 656 | <p> |
| 657 | On exit, the inverse transformation is (rather unnecessarily) used: |
| 658 | stuff in <code>VG_(baseBlock)</code> is copied to |
| 659 | <code>VG_(m_state_static)</code>, and the assembly stub then copies |
| 660 | from <code>VG_(m_state_static)</code> into the real machine registers. |
| 661 | |
| 662 | <p> |
| 663 | Doing system calls on behalf of the client (<code>vg_syscall.S</code>) |
| 664 | is something of a half-way house. We have to make the world look |
| 665 | sufficiently like that which the client would normally have to make |
| 666 | the syscall actually work properly, but we can't afford to lose |
| 667 | control. So the trick is to copy all of the client's state, <b>except |
| 668 | its program counter</b>, into the real CPU, do the system call, and |
| 669 | copy the state back out. Note that the client's state includes its |
| 670 | stack pointer register, so one effect of this partial restoration is |
| 671 | to cause the system call to be run on the client's stack, as it should |
| 672 | be. |
| 673 | |
| 674 | <p> |
| 675 | As ever there are complications. We have to save some of our own state |
| 676 | somewhere when restoring the client's state into the CPU, so that we |
| 677 | can keep going sensibly afterwards. In fact the only thing which is |
| 678 | important is our own stack pointer, but for paranoia reasons I save |
| 679 | and restore our own FPU state as well, even though that's probably |
| 680 | pointless. |
| 681 | |
| 682 | <p> |
| 683 | The complication on the above complication is, that for horrible |
| 684 | reasons to do with signals, we may have to handle a second client |
| 685 | system call whilst the client is blocked inside some other system |
| 686 | call (unbelievable!). That means there's two sets of places to |
| 687 | dump Valgrind's stack pointer and FPU state across the syscall, |
| 688 | and we decide which to use by consulting |
| 689 | <code>VG_(syscall_depth)</code>, which is in turn maintained by |
| 690 | <code>VG_(wrap_syscall)</code>. |
| 691 | |
| 692 | |
| 693 | |
| 694 | <h3>Introduction to UCode</h3> |
| 695 | |
| 696 | UCode lies at the heart of the x86-to-x86 JITter. The basic premise |
| 697 | is that dealing the the x86 instruction set head-on is just too darn |
| 698 | complicated, so we do the traditional compiler-writer's trick and |
| 699 | translate it into a simpler, easier-to-deal-with form. |
| 700 | |
| 701 | <p> |
| 702 | In normal operation, translation proceeds through six stages, |
| 703 | coordinated by <code>VG_(translate)</code>: |
| 704 | <ol> |
| 705 | <li>Parsing of an x86 basic block into a sequence of UCode |
| 706 | instructions (<code>VG_(disBB)</code>). |
| 707 | <p> |
| 708 | <li>UCode optimisation (<code>vg_improve</code>), with the aim of |
| 709 | caching simulated registers in real registers over multiple |
| 710 | simulated instructions, and removing redundant simulated |
| 711 | <code>%EFLAGS</code> saving/restoring. |
| 712 | <p> |
| 713 | <li>UCode instrumentation (<code>vg_instrument</code>), which adds |
| 714 | value and address checking code. |
| 715 | <p> |
| 716 | <li>Post-instrumentation cleanup (<code>vg_cleanup</code>), removing |
| 717 | redundant value-check computations. |
| 718 | <p> |
| 719 | <li>Register allocation (<code>vg_do_register_allocation</code>), |
| 720 | which, note, is done on UCode. |
| 721 | <p> |
| 722 | <li>Emission of final instrumented x86 code |
| 723 | (<code>VG_(emit_code)</code>). |
| 724 | </ol> |
| 725 | |
| 726 | <p> |
| 727 | Notice how steps 2, 3, 4 and 5 are simple UCode-to-UCode |
| 728 | transformation passes, all on straight-line blocks of UCode (type |
| 729 | <code>UCodeBlock</code>). Steps 2 and 4 are optimisation passes and |
| 730 | can be disabled for debugging purposes, with |
| 731 | <code>--optimise=no</code> and <code>--cleanup=no</code> respectively. |
| 732 | |
| 733 | <p> |
| 734 | Valgrind can also run in a no-instrumentation mode, given |
| 735 | <code>--instrument=no</code>. This is useful for debugging the JITter |
| 736 | quickly without having to deal with the complexity of the |
| 737 | instrumentation mechanism too. In this mode, steps 3 and 4 are |
| 738 | omitted. |
| 739 | |
| 740 | <p> |
| 741 | These flags combine, so that <code>--instrument=no</code> together with |
| 742 | <code>--optimise=no</code> means only steps 1, 5 and 6 are used. |
| 743 | <code>--single-step=yes</code> causes each x86 instruction to be |
| 744 | treated as a single basic block. The translations are terrible but |
| 745 | this is sometimes instructive. |
| 746 | |
| 747 | <p> |
| 748 | The <code>--stop-after=N</code> flag switches back to the real CPU |
| 749 | after <code>N</code> basic blocks. It also re-JITs the final basic |
| 750 | block executed and prints the debugging info resulting, so this |
| 751 | gives you a way to get a quick snapshot of how a basic block looks as |
| 752 | it passes through the six stages mentioned above. If you want to |
| 753 | see full information for every block translated (probably not, but |
| 754 | still ...) find, in <code>VG_(translate)</code>, the lines |
| 755 | <br><code> dis = True;</code> |
| 756 | <br><code> dis = debugging_translation;</code> |
| 757 | <br> |
| 758 | and comment out the second line. This will spew out debugging |
| 759 | junk faster than you can possibly imagine. |
| 760 | |
| 761 | |
| 762 | |
| 763 | <h3>UCode operand tags: type <code>Tag</code></h3> |
| 764 | |
| 765 | UCode is, more or less, a simple two-address RISC-like code. In |
| 766 | keeping with the x86 AT&T assembly syntax, generally speaking the |
| 767 | first operand is the source operand, and the second is the destination |
| 768 | operand, which is modified when the uinstr is notionally executed. |
| 769 | |
| 770 | <p> |
| 771 | UCode instructions have up to three operand fields, each of which has |
| 772 | a corresponding <code>Tag</code> describing it. Possible values for |
| 773 | the tag are: |
| 774 | |
| 775 | <ul> |
| 776 | <li><code>NoValue</code>: indicates that the field is not in use. |
| 777 | <p> |
| 778 | <li><code>Lit16</code>: the field contains a 16-bit literal. |
| 779 | <p> |
| 780 | <li><code>Literal</code>: the field denotes a 32-bit literal, whose |
| 781 | value is stored in the <code>lit32</code> field of the uinstr |
| 782 | itself. Since there is only one <code>lit32</code> for the whole |
| 783 | uinstr, only one operand field may contain this tag. |
| 784 | <p> |
| 785 | <li><code>SpillNo</code>: the field contains a spill slot number, in |
| 786 | the range 0 to 23 inclusive, denoting one of the spill slots |
| 787 | contained inside <code>VG_(baseBlock)</code>. Such tags only |
| 788 | exist after register allocation. |
| 789 | <p> |
| 790 | <li><code>RealReg</code>: the field contains a number in the range 0 |
| 791 | to 7 denoting an integer x86 ("real") register on the host. The |
| 792 | number is the Intel encoding for integer registers. Such tags |
| 793 | only exist after register allocation. |
| 794 | <p> |
| 795 | <li><code>ArchReg</code>: the field contains a number in the range 0 |
| 796 | to 7 denoting an integer x86 register on the simulated CPU. In |
| 797 | reality this means a reference to one of the first 8 words of |
| 798 | <code>VG_(baseBlock)</code>. Such tags can exist at any point in |
| 799 | the translation process. |
| 800 | <p> |
| 801 | <li>Last, but not least, <code>TempReg</code>. The field contains the |
| 802 | number of one of an infinite set of virtual (integer) |
| 803 | registers. <code>TempReg</code>s are used everywhere throughout |
| 804 | the translation process; you can have as many as you want. The |
| 805 | register allocator maps as many as it can into |
| 806 | <code>RealReg</code>s and turns the rest into |
| 807 | <code>SpillNo</code>s, so <code>TempReg</code>s should not exist |
| 808 | after the register allocation phase. |
| 809 | <p> |
| 810 | <code>TempReg</code>s are always 32 bits long, even if the data |
| 811 | they hold is logically shorter. In that case the upper unused |
| 812 | bits are required, and, I think, generally assumed, to be zero. |
| 813 | <code>TempReg</code>s holding V bits for quantities shorter than |
| 814 | 32 bits are expected to have ones in the unused places, since a |
| 815 | one denotes "undefined". |
| 816 | </ul> |
| 817 | |
| 818 | |
| 819 | <h3>UCode instructions: type <code>UInstr</code></h3> |
| 820 | |
| 821 | <p> |
| 822 | UCode was carefully designed to make it possible to do register |
| 823 | allocation on UCode and then translate the result into x86 code |
| 824 | without needing any extra registers ... well, that was the original |
| 825 | plan, anyway. Things have gotten a little more complicated since |
| 826 | then. In what follows, UCode instructions are referred to as uinstrs, |
| 827 | to distinguish them from x86 instructions. Uinstrs of course have |
| 828 | uopcodes which are (naturally) different from x86 opcodes. |
| 829 | |
| 830 | <p> |
| 831 | A uinstr (type <code>UInstr</code>) contains |
| 832 | various fields, not all of which are used by any one uopcode: |
| 833 | <ul> |
| 834 | <li>Three 16-bit operand fields, <code>val1</code>, <code>val2</code> |
| 835 | and <code>val3</code>. |
| 836 | <p> |
| 837 | <li>Three tag fields, <code>tag1</code>, <code>tag2</code> |
| 838 | and <code>tag3</code>. Each of these has a value of type |
| 839 | <code>Tag</code>, |
| 840 | and they describe what the <code>val1</code>, <code>val2</code> |
| 841 | and <code>val3</code> fields contain. |
| 842 | <p> |
| 843 | <li>A 32-bit literal field. |
| 844 | <p> |
| 845 | <li>Two <code>FlagSet</code>s, specifying which x86 condition codes are |
| 846 | read and written by the uinstr. |
| 847 | <p> |
| 848 | <li>An opcode byte, containing a value of type <code>Opcode</code>. |
| 849 | <p> |
| 850 | <li>A size field, indicating the data transfer size (1/2/4/8/10) in |
| 851 | cases where this makes sense, or zero otherwise. |
| 852 | <p> |
| 853 | <li>A condition-code field, which, for jumps, holds a |
| 854 | value of type <code>Condcode</code>, indicating the condition |
| 855 | which applies. The encoding is as it is in the x86 insn stream, |
| 856 | except we add a 17th value <code>CondAlways</code> to indicate |
| 857 | an unconditional transfer. |
| 858 | <p> |
| 859 | <li>Various 1-bit flags, indicating whether this insn pertains to an |
| 860 | x86 CALL or RET instruction, whether a widening is signed or not, |
| 861 | etc. |
| 862 | </ul> |
| 863 | |
| 864 | <p> |
| 865 | UOpcodes (type <code>Opcode</code>) are divided into two groups: those |
| 866 | necessary merely to express the functionality of the x86 code, and |
| 867 | extra uopcodes needed to express the instrumentation. The former |
| 868 | group contains: |
| 869 | <ul> |
| 870 | <li><code>GET</code> and <code>PUT</code>, which move values from the |
| 871 | simulated CPU's integer registers (<code>ArchReg</code>s) into |
| 872 | <code>TempReg</code>s, and back. <code>GETF</code> and |
| 873 | <code>PUTF</code> do the corresponding thing for the simulated |
| 874 | <code>%EFLAGS</code>. There are no corresponding insns for the |
| 875 | FPU register stack, since we don't explicitly simulate its |
| 876 | registers. |
| 877 | <p> |
| 878 | <li><code>LOAD</code> and <code>STORE</code>, which, in RISC-like |
| 879 | fashion, are the only uinstrs able to interact with memory. |
| 880 | <p> |
| 881 | <li><code>MOV</code> and <code>CMOV</code> allow unconditional and |
| 882 | conditional moves of values between <code>TempReg</code>s. |
| 883 | <p> |
| 884 | <li>ALU operations. Again in RISC-like fashion, these only operate on |
| 885 | <code>TempReg</code>s (before reg-alloc) or <code>RealReg</code>s |
| 886 | (after reg-alloc). These are: <code>ADD</code>, <code>ADC</code>, |
| 887 | <code>AND</code>, <code>OR</code>, <code>XOR</code>, |
| 888 | <code>SUB</code>, <code>SBB</code>, <code>SHL</code>, |
| 889 | <code>SHR</code>, <code>SAR</code>, <code>ROL</code>, |
| 890 | <code>ROR</code>, <code>RCL</code>, <code>RCR</code>, |
| 891 | <code>NOT</code>, <code>NEG</code>, <code>INC</code>, |
| 892 | <code>DEC</code>, <code>BSWAP</code>, <code>CC2VAL</code> and |
| 893 | <code>WIDEN</code>. <code>WIDEN</code> does signed or unsigned |
| 894 | value widening. <code>CC2VAL</code> is used to convert condition |
| 895 | codes into a value, zero or one. The rest are obvious. |
| 896 | <p> |
| 897 | To allow for more efficient code generation, we bend slightly the |
| 898 | restriction at the start of the previous para: for |
| 899 | <code>ADD</code>, <code>ADC</code>, <code>XOR</code>, |
| 900 | <code>SUB</code> and <code>SBB</code>, we allow the first (source) |
| 901 | operand to also be an <code>ArchReg</code>, that is, one of the |
| 902 | simulated machine's registers. Also, many of these ALU ops allow |
| 903 | the source operand to be a literal. See |
| 904 | <code>VG_(saneUInstr)</code> for the final word on the allowable |
| 905 | forms of uinstrs. |
| 906 | <p> |
| 907 | <li><code>LEA1</code> and <code>LEA2</code> are not strictly |
| 908 | necessary, but allow faciliate better translations. They |
| 909 | record the fancy x86 addressing modes in a direct way, which |
| 910 | allows those amodes to be emitted back into the final |
| 911 | instruction stream more or less verbatim. |
| 912 | <p> |
| 913 | <li><code>CALLM</code> calls a machine-code helper, one of the methods |
| 914 | whose address is stored at some <code>VG_(baseBlock)</code> |
| 915 | offset. <code>PUSH</code> and <code>POP</code> move values |
| 916 | to/from <code>TempReg</code> to the real (Valgrind's) stack, and |
| 917 | <code>CLEAR</code> removes values from the stack. |
| 918 | <code>CALLM_S</code> and <code>CALLM_E</code> delimit the |
| 919 | boundaries of call setups and clearings, for the benefit of the |
| 920 | instrumentation passes. Getting this right is critical, and so |
| 921 | <code>VG_(saneUCodeBlock)</code> makes various checks on the use |
| 922 | of these uopcodes. |
| 923 | <p> |
| 924 | It is important to understand that these uopcodes have nothing to |
| 925 | do with the x86 <code>call</code>, <code>return,</code> |
| 926 | <code>push</code> or <code>pop</code> instructions, and are not |
| 927 | used to implement them. Those guys turn into combinations of |
| 928 | <code>GET</code>, <code>PUT</code>, <code>LOAD</code>, |
| 929 | <code>STORE</code>, <code>ADD</code>, <code>SUB</code>, and |
| 930 | <code>JMP</code>. What these uopcodes support is calling of |
| 931 | helper functions such as <code>VG_(helper_imul_32_64)</code>, |
| 932 | which do stuff which is too difficult or tedious to emit inline. |
| 933 | <p> |
| 934 | <li><code>FPU</code>, <code>FPU_R</code> and <code>FPU_W</code>. |
| 935 | Valgrind doesn't attempt to simulate the internal state of the |
| 936 | FPU at all. Consequently it only needs to be able to distinguish |
| 937 | FPU ops which read and write memory from those that don't, and |
| 938 | for those which do, it needs to know the effective address and |
| 939 | data transfer size. This is made easier because the x86 FP |
| 940 | instruction encoding is very regular, basically consisting of |
| 941 | 16 bits for a non-memory FPU insn and 11 (IIRC) bits + an address mode |
| 942 | for a memory FPU insn. So our <code>FPU</code> uinstr carries |
| 943 | the 16 bits in its <code>val1</code> field. And |
| 944 | <code>FPU_R</code> and <code>FPU_W</code> carry 11 bits in that |
| 945 | field, together with the identity of a <code>TempReg</code> or |
| 946 | (later) <code>RealReg</code> which contains the address. |
| 947 | <p> |
| 948 | <li><code>JIFZ</code> is unique, in that it allows a control-flow |
| 949 | transfer which is not deemed to end a basic block. It causes a |
| 950 | jump to a literal (original) address if the specified argument |
| 951 | is zero. |
| 952 | <p> |
| 953 | <li>Finally, <code>INCEIP</code> advances the simulated |
| 954 | <code>%EIP</code> by the specified literal amount. This supports |
| 955 | lazy <code>%EIP</code> updating, as described below. |
| 956 | </ul> |
| 957 | |
| 958 | <p> |
| 959 | Stages 1 and 2 of the 6-stage translation process mentioned above |
| 960 | deal purely with these uopcodes, and no others. They are |
| 961 | sufficient to express pretty much all the x86 32-bit protected-mode |
| 962 | instruction set, at |
| 963 | least everything understood by a pre-MMX original Pentium (P54C). |
| 964 | |
| 965 | <p> |
| 966 | Stages 3, 4, 5 and 6 also deal with the following extra |
| 967 | "instrumentation" uopcodes. They are used to express all the |
| 968 | definedness-tracking and -checking machinery which valgrind does. In |
| 969 | later sections we show how to create checking code for each of the |
| 970 | uopcodes above. Note that these instrumentation uopcodes, although |
| 971 | some appearing complicated, have been carefully chosen so that |
| 972 | efficient x86 code can be generated for them. GNU superopt v2.5 did a |
| 973 | great job helping out here. Anyways, the uopcodes are as follows: |
| 974 | |
| 975 | <ul> |
| 976 | <li><code>GETV</code> and <code>PUTV</code> are analogues to |
| 977 | <code>GET</code> and <code>PUT</code> above. They are identical |
| 978 | except that they move the V bits for the specified values back and |
| 979 | forth to <code>TempRegs</code>, rather than moving the values |
| 980 | themselves. |
| 981 | <p> |
| 982 | <li>Similarly, <code>LOADV</code> and <code>STOREV</code> read and |
| 983 | write V bits from the synthesised shadow memory that Valgrind |
| 984 | maintains. In fact they do more than that, since they also do |
| 985 | address-validity checks, and emit complaints if the read/written |
| 986 | addresses are unaddressible. |
| 987 | <p> |
| 988 | <li><code>TESTV</code>, whose parameters are a <code>TempReg</code> |
| 989 | and a size, tests the V bits in the <code>TempReg</code>, at the |
| 990 | specified operation size (0/1/2/4 byte) and emits an error if any |
| 991 | of them indicate undefinedness. This is the only uopcode capable |
| 992 | of doing such tests. |
| 993 | <p> |
| 994 | <li><code>SETV</code>, whose parameters are also <code>TempReg</code> |
| 995 | and a size, makes the V bits in the <code>TempReg</code> indicated |
| 996 | definedness, at the specified operation size. This is usually |
| 997 | used to generate the correct V bits for a literal value, which is |
| 998 | of course fully defined. |
| 999 | <p> |
| 1000 | <li><code>GETVF</code> and <code>PUTVF</code> are analogues to |
| 1001 | <code>GETF</code> and <code>PUTF</code>. They move the single V |
| 1002 | bit used to model definedness of <code>%EFLAGS</code> between its |
| 1003 | home in <code>VG_(baseBlock)</code> and the specified |
| 1004 | <code>TempReg</code>. |
| 1005 | <p> |
| 1006 | <li><code>TAG1</code> denotes one of a family of unary operations on |
| 1007 | <code>TempReg</code>s containing V bits. Similarly, |
| 1008 | <code>TAG2</code> denotes one in a family of binary operations on |
| 1009 | V bits. |
| 1010 | </ul> |
| 1011 | |
| 1012 | <p> |
| 1013 | These 10 uopcodes are sufficient to express Valgrind's entire |
| 1014 | definedness-checking semantics. In fact most of the interesting magic |
| 1015 | is done by the <code>TAG1</code> and <code>TAG2</code> |
| 1016 | suboperations. |
| 1017 | |
| 1018 | <p> |
| 1019 | First, however, I need to explain about V-vector operation sizes. |
| 1020 | There are 4 sizes: 1, 2 and 4, which operate on groups of 8, 16 and 32 |
| 1021 | V bits at a time, supporting the usual 1, 2 and 4 byte x86 operations. |
| 1022 | However there is also the mysterious size 0, which really means a |
| 1023 | single V bit. Single V bits are used in various circumstances; in |
| 1024 | particular, the definedness of <code>%EFLAGS</code> is modelled with a |
| 1025 | single V bit. Now might be a good time to also point out that for |
| 1026 | V bits, 1 means "undefined" and 0 means "defined". Similarly, for A |
| 1027 | bits, 1 means "invalid address" and 0 means "valid address". This |
| 1028 | seems counterintuitive (and so it is), but testing against zero on |
| 1029 | x86s saves instructions compared to testing against all 1s, because |
| 1030 | many ALU operations set the Z flag for free, so to speak. |
| 1031 | |
| 1032 | <p> |
| 1033 | With that in mind, the tag ops are: |
| 1034 | |
| 1035 | <ul> |
| 1036 | <li><b>(UNARY) Pessimising casts</b>: <code>VgT_PCast40</code>, |
| 1037 | <code>VgT_PCast20</code>, <code>VgT_PCast10</code>, |
| 1038 | <code>VgT_PCast01</code>, <code>VgT_PCast02</code> and |
| 1039 | <code>VgT_PCast04</code>. A "pessimising cast" takes a V-bit |
| 1040 | vector at one size, and creates a new one at another size, |
| 1041 | pessimised in the sense that if any of the bits in the source |
| 1042 | vector indicate undefinedness, then all the bits in the result |
| 1043 | indicate undefinedness. In this case the casts are all to or from |
| 1044 | a single V bit, so for example <code>VgT_PCast40</code> is a |
| 1045 | pessimising cast from 32 bits to 1, whereas |
| 1046 | <code>VgT_PCast04</code> simply copies the single source V bit |
| 1047 | into all 32 bit positions in the result. Surprisingly, these ops |
| 1048 | can all be implemented very efficiently. |
| 1049 | <p> |
| 1050 | There are also the pessimising casts <code>VgT_PCast14</code>, |
| 1051 | from 8 bits to 32, <code>VgT_PCast12</code>, from 8 bits to 16, |
| 1052 | and <code>VgT_PCast11</code>, from 8 bits to 8. This last one |
| 1053 | seems nonsensical, but in fact it isn't a no-op because, as |
| 1054 | mentioned above, any undefined (1) bits in the source infect the |
| 1055 | entire result. |
| 1056 | <p> |
| 1057 | <li><b>(UNARY) Propagating undefinedness upwards in a word</b>: |
| 1058 | <code>VgT_Left4</code>, <code>VgT_Left2</code> and |
| 1059 | <code>VgT_Left1</code>. These are used to simulate the worst-case |
| 1060 | effects of carry propagation in adds and subtracts. They return a |
| 1061 | V vector identical to the original, except that if the original |
| 1062 | contained any undefined bits, then it and all bits above it are |
| 1063 | marked as undefined too. Hence the Left bit in the names. |
| 1064 | <p> |
| 1065 | <li><b>(UNARY) Signed and unsigned value widening</b>: |
| 1066 | <code>VgT_SWiden14</code>, <code>VgT_SWiden24</code>, |
| 1067 | <code>VgT_SWiden12</code>, <code>VgT_ZWiden14</code>, |
| 1068 | <code>VgT_ZWiden24</code> and <code>VgT_ZWiden12</code>. These |
| 1069 | mimic the definedness effects of standard signed and unsigned |
| 1070 | integer widening. Unsigned widening creates zero bits in the new |
| 1071 | positions, so <code>VgT_ZWiden*</code> accordingly park mark |
| 1072 | those parts of their argument as defined. Signed widening copies |
| 1073 | the sign bit into the new positions, so <code>VgT_SWiden*</code> |
| 1074 | copies the definedness of the sign bit into the new positions. |
| 1075 | Because 1 means undefined and 0 means defined, these operations |
| 1076 | can (fascinatingly) be done by the same operations which they |
| 1077 | mimic. Go figure. |
| 1078 | <p> |
| 1079 | <li><b>(BINARY) Undefined-if-either-Undefined, |
| 1080 | Defined-if-either-Defined</b>: <code>VgT_UifU4</code>, |
| 1081 | <code>VgT_UifU2</code>, <code>VgT_UifU1</code>, |
| 1082 | <code>VgT_UifU0</code>, <code>VgT_DifD4</code>, |
| 1083 | <code>VgT_DifD2</code>, <code>VgT_DifD1</code>. These do simple |
| 1084 | bitwise operations on pairs of V-bit vectors, with |
| 1085 | <code>UifU</code> giving undefined if either arg bit is |
| 1086 | undefined, and <code>DifD</code> giving defined if either arg bit |
| 1087 | is defined. Abstract interpretation junkies, if any make it this |
| 1088 | far, may like to think of them as meets and joins (or is it joins |
| 1089 | and meets) in the definedness lattices. |
| 1090 | <p> |
| 1091 | <li><b>(BINARY; one value, one V bits) Generate argument improvement |
| 1092 | terms for AND and OR</b>: <code>VgT_ImproveAND4_TQ</code>, |
| 1093 | <code>VgT_ImproveAND2_TQ</code>, <code>VgT_ImproveAND1_TQ</code>, |
| 1094 | <code>VgT_ImproveOR4_TQ</code>, <code>VgT_ImproveOR2_TQ</code>, |
| 1095 | <code>VgT_ImproveOR1_TQ</code>. These help out with AND and OR |
| 1096 | operations. AND and OR have the inconvenient property that the |
| 1097 | definedness of the result depends on the actual values of the |
| 1098 | arguments as well as their definedness. At the bit level: |
| 1099 | <br><code>1 AND undefined = undefined</code>, but |
| 1100 | <br><code>0 AND undefined = 0</code>, and similarly |
| 1101 | <br><code>0 OR undefined = undefined</code>, but |
| 1102 | <br><code>1 OR undefined = 1</code>. |
| 1103 | <br> |
| 1104 | <p> |
| 1105 | It turns out that gcc (quite legitimately) generates code which |
| 1106 | relies on this fact, so we have to model it properly in order to |
| 1107 | avoid flooding users with spurious value errors. The ultimate |
| 1108 | definedness result of AND and OR is calculated using |
| 1109 | <code>UifU</code> on the definedness of the arguments, but we |
| 1110 | also <code>DifD</code> in some "improvement" terms which |
| 1111 | take into account the above phenomena. |
| 1112 | <p> |
| 1113 | <code>ImproveAND</code> takes as its first argument the actual |
| 1114 | value of an argument to AND (the T) and the definedness of that |
| 1115 | argument (the Q), and returns a V-bit vector which is defined (0) |
| 1116 | for bits which have value 0 and are defined; this, when |
| 1117 | <code>DifD</code> into the final result causes those bits to be |
| 1118 | defined even if the corresponding bit in the other argument is undefined. |
| 1119 | <p> |
| 1120 | The <code>ImproveOR</code> ops do the dual thing for OR |
| 1121 | arguments. Note that XOR does not have this property that one |
| 1122 | argument can make the other irrelevant, so there is no need for |
| 1123 | such complexity for XOR. |
| 1124 | </ul> |
| 1125 | |
| 1126 | <p> |
| 1127 | That's all the tag ops. If you stare at this long enough, and then |
| 1128 | run Valgrind and stare at the pre- and post-instrumented ucode, it |
| 1129 | should be fairly obvious how the instrumentation machinery hangs |
| 1130 | together. |
| 1131 | |
| 1132 | <p> |
| 1133 | One point, if you do this: in order to make it easy to differentiate |
| 1134 | <code>TempReg</code>s carrying values from <code>TempReg</code>s |
| 1135 | carrying V bit vectors, Valgrind prints the former as (for example) |
| 1136 | <code>t28</code> and the latter as <code>q28</code>; the fact that |
| 1137 | they carry the same number serves to indicate their relationship. |
| 1138 | This is purely for the convenience of the human reader; the register |
| 1139 | allocator and code generator don't regard them as different. |
| 1140 | |
| 1141 | |
| 1142 | <h3>Translation into UCode</h3> |
| 1143 | |
| 1144 | <code>VG_(disBB)</code> allocates a new <code>UCodeBlock</code> and |
| 1145 | then uses <code>disInstr</code> to translate x86 instructions one at a |
| 1146 | time into UCode, dumping the result in the <code>UCodeBlock</code>. |
| 1147 | This goes on until a control-flow transfer instruction is encountered. |
| 1148 | |
| 1149 | <p> |
| 1150 | Despite the large size of <code>vg_to_ucode.c</code>, this translation |
| 1151 | is really very simple. Each x86 instruction is translated entirely |
| 1152 | independently of its neighbours, merrily allocating new |
| 1153 | <code>TempReg</code>s as it goes. The idea is to have a simple |
| 1154 | translator -- in reality, no more than a macro-expander -- and the -- |
| 1155 | resulting bad UCode translation is cleaned up by the UCode |
| 1156 | optimisation phase which follows. To give you an idea of some x86 |
| 1157 | instructions and their translations (this is a complete basic block, |
| 1158 | as Valgrind sees it): |
| 1159 | <pre> |
| 1160 | 0x40435A50: incl %edx |
| 1161 | |
| 1162 | 0: GETL %EDX, t0 |
| 1163 | 1: INCL t0 (-wOSZAP) |
| 1164 | 2: PUTL t0, %EDX |
| 1165 | |
| 1166 | 0x40435A51: movsbl (%edx),%eax |
| 1167 | |
| 1168 | 3: GETL %EDX, t2 |
| 1169 | 4: LDB (t2), t2 |
| 1170 | 5: WIDENL_Bs t2 |
| 1171 | 6: PUTL t2, %EAX |
| 1172 | |
| 1173 | 0x40435A54: testb $0x20, 1(%ecx,%eax,2) |
| 1174 | |
| 1175 | 7: GETL %EAX, t6 |
| 1176 | 8: GETL %ECX, t8 |
| 1177 | 9: LEA2L 1(t8,t6,2), t4 |
| 1178 | 10: LDB (t4), t10 |
| 1179 | 11: MOVB $0x20, t12 |
| 1180 | 12: ANDB t12, t10 (-wOSZACP) |
| 1181 | 13: INCEIPo $9 |
| 1182 | |
| 1183 | 0x40435A59: jnz-8 0x40435A50 |
| 1184 | |
| 1185 | 14: Jnzo $0x40435A50 (-rOSZACP) |
| 1186 | 15: JMPo $0x40435A5B |
| 1187 | </pre> |
| 1188 | |
| 1189 | <p> |
| 1190 | Notice how the block always ends with an unconditional jump to the |
| 1191 | next block. This is a bit unnecessary, but makes many things simpler. |
| 1192 | |
| 1193 | <p> |
| 1194 | Most x86 instructions turn into sequences of <code>GET</code>, |
sewardj | 177380e | 2002-03-24 11:31:13 +0000 | [diff] [blame] | 1195 | <code>PUT</code>, <code>LEA1</code>, <code>LEA2</code>, |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 1196 | <code>LOAD</code> and <code>STORE</code>. Some complicated ones |
| 1197 | however rely on calling helper bits of code in |
| 1198 | <code>vg_helpers.S</code>. The ucode instructions <code>PUSH</code>, |
| 1199 | <code>POP</code>, <code>CALL</code>, <code>CALLM_S</code> and |
| 1200 | <code>CALLM_E</code> support this. The calling convention is somewhat |
| 1201 | ad-hoc and is not the C calling convention. The helper routines must |
| 1202 | save all integer registers, and the flags, that they use. Args are |
| 1203 | passed on the stack underneath the return address, as usual, and if |
| 1204 | result(s) are to be returned, it (they) are either placed in dummy arg |
| 1205 | slots created by the ucode <code>PUSH</code> sequence, or just |
| 1206 | overwrite the incoming args. |
| 1207 | |
| 1208 | <p> |
| 1209 | In order that the instrumentation mechanism can handle calls to these |
| 1210 | helpers, <code>VG_(saneUCodeBlock)</code> enforces the following |
| 1211 | restrictions on calls to helpers: |
| 1212 | |
| 1213 | <ul> |
| 1214 | <li>Each <code>CALL</code> uinstr must be bracketed by a preceding |
| 1215 | <code>CALLM_S</code> marker (dummy uinstr) and a trailing |
| 1216 | <code>CALLM_E</code> marker. These markers are used by the |
| 1217 | instrumentation mechanism later to establish the boundaries of the |
| 1218 | <code>PUSH</code>, <code>POP</code> and <code>CLEAR</code> |
| 1219 | sequences for the call. |
| 1220 | <p> |
| 1221 | <li><code>PUSH</code>, <code>POP</code> and <code>CLEAR</code> |
| 1222 | may only appear inside sections bracketed by <code>CALLM_S</code> |
| 1223 | and <code>CALLM_E</code>, and nowhere else. |
| 1224 | <p> |
| 1225 | <li>In any such bracketed section, no two <code>PUSH</code> insns may |
| 1226 | push the same <code>TempReg</code>. Dually, no two two |
| 1227 | <code>POP</code>s may pop the same <code>TempReg</code>. |
| 1228 | <p> |
| 1229 | <li>Finally, although this is not checked, args should be removed from |
| 1230 | the stack with <code>CLEAR</code>, rather than <code>POP</code>s |
| 1231 | into a <code>TempReg</code> which is not subsequently used. This |
| 1232 | is because the instrumentation mechanism assumes that all values |
| 1233 | <code>POP</code>ped from the stack are actually used. |
| 1234 | </ul> |
| 1235 | |
| 1236 | Some of the translations may appear to have redundant |
| 1237 | <code>TempReg</code>-to-<code>TempReg</code> moves. This helps the |
| 1238 | next phase, UCode optimisation, to generate better code. |
| 1239 | |
| 1240 | |
| 1241 | |
| 1242 | <h3>UCode optimisation</h3> |
| 1243 | |
| 1244 | UCode is then subjected to an improvement pass |
| 1245 | (<code>vg_improve()</code>), which blurs the boundaries between the |
| 1246 | translations of the original x86 instructions. It's pretty |
| 1247 | straightforward. Three transformations are done: |
| 1248 | |
| 1249 | <ul> |
| 1250 | <li>Redundant <code>GET</code> elimination. Actually, more general |
| 1251 | than that -- eliminates redundant fetches of ArchRegs. In our |
| 1252 | running example, uinstr 3 <code>GET</code>s <code>%EDX</code> into |
| 1253 | <code>t2</code> despite the fact that, by looking at the previous |
| 1254 | uinstr, it is already in <code>t0</code>. The <code>GET</code> is |
| 1255 | therefore removed, and <code>t2</code> renamed to <code>t0</code>. |
| 1256 | Assuming <code>t0</code> is allocated to a host register, it means |
| 1257 | the simulated <code>%EDX</code> will exist in a host CPU register |
| 1258 | for more than one simulated x86 instruction, which seems to me to |
| 1259 | be a highly desirable property. |
| 1260 | <p> |
| 1261 | There is some mucking around to do with subregisters; |
| 1262 | <code>%AL</code> vs <code>%AH</code> <code>%AX</code> vs |
| 1263 | <code>%EAX</code> etc. I can't remember how it works, but in |
| 1264 | general we are very conservative, and these tend to invalidate the |
| 1265 | caching. |
| 1266 | <p> |
| 1267 | <li>Redundant <code>PUT</code> elimination. This annuls |
| 1268 | <code>PUT</code>s of values back to simulated CPU registers if a |
| 1269 | later <code>PUT</code> would overwrite the earlier |
| 1270 | <code>PUT</code> value, and there is no intervening reads of the |
| 1271 | simulated register (<code>ArchReg</code>). |
| 1272 | <p> |
| 1273 | As before, we are paranoid when faced with subregister references. |
| 1274 | Also, <code>PUT</code>s of <code>%ESP</code> are never annulled, |
| 1275 | because it is vital the instrumenter always has an up-to-date |
| 1276 | <code>%ESP</code> value available, <code>%ESP</code> changes |
| 1277 | affect addressibility of the memory around the simulated stack |
| 1278 | pointer. |
| 1279 | <p> |
| 1280 | The implication of the above paragraph is that the simulated |
| 1281 | machine's registers are only lazily updated once the above two |
| 1282 | optimisation phases have run, with the exception of |
| 1283 | <code>%ESP</code>. <code>TempReg</code>s go dead at the end of |
| 1284 | every basic block, from which is is inferrable that any |
| 1285 | <code>TempReg</code> caching a simulated CPU reg is flushed (back |
| 1286 | into the relevant <code>VG_(baseBlock)</code> slot) at the end of |
| 1287 | every basic block. The further implication is that the simulated |
| 1288 | registers are only up-to-date at in between basic blocks, and not |
| 1289 | at arbitrary points inside basic blocks. And the consequence of |
| 1290 | that is that we can only deliver signals to the client in between |
| 1291 | basic blocks. None of this seems any problem in practice. |
| 1292 | <p> |
| 1293 | <li>Finally there is a simple def-use thing for condition codes. If |
| 1294 | an earlier uinstr writes the condition codes, and the next uinsn |
| 1295 | along which actually cares about the condition codes writes the |
| 1296 | same or larger set of them, but does not read any, the earlier |
| 1297 | uinsn is marked as not writing any condition codes. This saves |
| 1298 | a lot of redundant cond-code saving and restoring. |
| 1299 | </ul> |
| 1300 | |
| 1301 | The effect of these transformations on our short block is rather |
| 1302 | unexciting, and shown below. On longer basic blocks they can |
| 1303 | dramatically improve code quality. |
| 1304 | |
| 1305 | <pre> |
| 1306 | at 3: delete GET, rename t2 to t0 in (4 .. 6) |
| 1307 | at 7: delete GET, rename t6 to t0 in (8 .. 9) |
| 1308 | at 1: annul flag write OSZAP due to later OSZACP |
| 1309 | |
| 1310 | Improved code: |
| 1311 | 0: GETL %EDX, t0 |
| 1312 | 1: INCL t0 |
| 1313 | 2: PUTL t0, %EDX |
| 1314 | 4: LDB (t0), t0 |
| 1315 | 5: WIDENL_Bs t0 |
| 1316 | 6: PUTL t0, %EAX |
| 1317 | 8: GETL %ECX, t8 |
| 1318 | 9: LEA2L 1(t8,t0,2), t4 |
| 1319 | 10: LDB (t4), t10 |
| 1320 | 11: MOVB $0x20, t12 |
| 1321 | 12: ANDB t12, t10 (-wOSZACP) |
| 1322 | 13: INCEIPo $9 |
| 1323 | 14: Jnzo $0x40435A50 (-rOSZACP) |
| 1324 | 15: JMPo $0x40435A5B |
| 1325 | </pre> |
| 1326 | |
| 1327 | <h3>UCode instrumentation</h3> |
| 1328 | |
| 1329 | Once you understand the meaning of the instrumentation uinstrs, |
| 1330 | discussed in detail above, the instrumentation scheme is fairly |
| 1331 | straighforward. Each uinstr is instrumented in isolation, and the |
| 1332 | instrumentation uinstrs are placed before the original uinstr. |
| 1333 | Our running example continues below. I have placed a blank line |
| 1334 | after every original ucode, to make it easier to see which |
| 1335 | instrumentation uinstrs correspond to which originals. |
| 1336 | |
| 1337 | <p> |
| 1338 | As mentioned somewhere above, <code>TempReg</code>s carrying values |
| 1339 | have names like <code>t28</code>, and each one has a shadow carrying |
| 1340 | its V bits, with names like <code>q28</code>. This pairing aids in |
| 1341 | reading instrumented ucode. |
| 1342 | |
| 1343 | <p> |
| 1344 | One decision about all this is where to have "observation points", |
| 1345 | that is, where to check that V bits are valid. I use a minimalistic |
| 1346 | scheme, only checking where a failure of validity could cause the |
| 1347 | original program to (seg)fault. So the use of values as memory |
| 1348 | addresses causes a check, as do conditional jumps (these cause a check |
| 1349 | on the definedness of the condition codes). And arguments |
| 1350 | <code>PUSH</code>ed for helper calls are checked, hence the wierd |
| 1351 | restrictions on help call preambles described above. |
| 1352 | |
| 1353 | <p> |
| 1354 | Another decision is that once a value is tested, it is thereafter |
| 1355 | regarded as defined, so that we do not emit multiple undefined-value |
| 1356 | errors for the same undefined value. That means that |
| 1357 | <code>TESTV</code> uinstrs are always followed by <code>SETV</code> |
| 1358 | on the same (shadow) <code>TempReg</code>s. Most of these |
| 1359 | <code>SETV</code>s are redundant and are removed by the |
| 1360 | post-instrumentation cleanup phase. |
| 1361 | |
| 1362 | <p> |
| 1363 | The instrumentation for calling helper functions deserves further |
| 1364 | comment. The definedness of results from a helper is modelled using |
| 1365 | just one V bit. So, in short, we do pessimising casts of the |
| 1366 | definedness of all the args, down to a single bit, and then |
| 1367 | <code>UifU</code> these bits together. So this single V bit will say |
| 1368 | "undefined" if any part of any arg is undefined. This V bit is then |
| 1369 | pessimally cast back up to the result(s) sizes, as needed. If, by |
| 1370 | seeing that all the args are got rid of with <code>CLEAR</code> and |
| 1371 | none with <code>POP</code>, Valgrind sees that the result of the call |
| 1372 | is not actually used, it immediately examines the result V bit with a |
| 1373 | <code>TESTV</code> -- <code>SETV</code> pair. If it did not do this, |
| 1374 | there would be no observation point to detect that the some of the |
| 1375 | args to the helper were undefined. Of course, if the helper's results |
| 1376 | are indeed used, we don't do this, since the result usage will |
| 1377 | presumably cause the result definedness to be checked at some suitable |
| 1378 | future point. |
| 1379 | |
| 1380 | <p> |
| 1381 | In general Valgrind tries to track definedness on a bit-for-bit basis, |
| 1382 | but as the above para shows, for calls to helpers we throw in the |
| 1383 | towel and approximate down to a single bit. This is because it's too |
| 1384 | complex and difficult to track bit-level definedness through complex |
| 1385 | ops such as integer multiply and divide, and in any case there is no |
| 1386 | reasonable code fragments which attempt to (eg) multiply two |
| 1387 | partially-defined values and end up with something meaningful, so |
| 1388 | there seems little point in modelling multiplies, divides, etc, in |
| 1389 | that level of detail. |
| 1390 | |
| 1391 | <p> |
| 1392 | Integer loads and stores are instrumented with firstly a test of the |
| 1393 | definedness of the address, followed by a <code>LOADV</code> or |
| 1394 | <code>STOREV</code> respectively. These turn into calls to |
| 1395 | (for example) <code>VG_(helperc_LOADV4)</code>. These helpers do two |
| 1396 | things: they perform an address-valid check, and they load or store V |
| 1397 | bits from/to the relevant address in the (simulated V-bit) memory. |
| 1398 | |
| 1399 | <p> |
| 1400 | FPU loads and stores are different. As above the definedness of the |
| 1401 | address is first tested. However, the helper routine for FPU loads |
| 1402 | (<code>VGM_(fpu_read_check)</code>) emits an error if either the |
| 1403 | address is invalid or the referenced area contains undefined values. |
| 1404 | It has to do this because we do not simulate the FPU at all, and so |
| 1405 | cannot track definedness of values loaded into it from memory, so we |
| 1406 | have to check them as soon as they are loaded into the FPU, ie, at |
| 1407 | this point. We notionally assume that everything in the FPU is |
| 1408 | defined. |
| 1409 | |
| 1410 | <p> |
| 1411 | It follows therefore that FPU writes first check the definedness of |
| 1412 | the address, then the validity of the address, and finally mark the |
| 1413 | written bytes as well-defined. |
| 1414 | |
| 1415 | <p> |
| 1416 | If anyone is inspired to extend Valgrind to MMX/SSE insns, I suggest |
| 1417 | you use the same trick. It works provided that the FPU/MMX unit is |
| 1418 | not used to merely as a conduit to copy partially undefined data from |
| 1419 | one place in memory to another. Unfortunately the integer CPU is used |
| 1420 | like that (when copying C structs with holes, for example) and this is |
| 1421 | the cause of much of the elaborateness of the instrumentation here |
| 1422 | described. |
| 1423 | |
| 1424 | <p> |
| 1425 | <code>vg_instrument()</code> in <code>vg_translate.c</code> actually |
| 1426 | does the instrumentation. There are comments explaining how each |
| 1427 | uinstr is handled, so we do not repeat that here. As explained |
| 1428 | already, it is bit-accurate, except for calls to helper functions. |
| 1429 | Unfortunately the x86 insns <code>bt/bts/btc/btr</code> are done by |
| 1430 | helper fns, so bit-level accuracy is lost there. This should be fixed |
| 1431 | by doing them inline; it will probably require adding a couple new |
| 1432 | uinstrs. Also, left and right rotates through the carry flag (x86 |
| 1433 | <code>rcl</code> and <code>rcr</code>) are approximated via a single |
| 1434 | V bit; so far this has not caused anyone to complain. The |
| 1435 | non-carry rotates, <code>rol</code> and <code>ror</code>, are much |
| 1436 | more common and are done exactly. Re-visiting the instrumentation for |
| 1437 | AND and OR, they seem rather verbose, and I wonder if it could be done |
| 1438 | more concisely now. |
| 1439 | |
| 1440 | <p> |
| 1441 | The lowercase <code>o</code> on many of the uopcodes in the running |
| 1442 | example indicates that the size field is zero, usually meaning a |
| 1443 | single-bit operation. |
| 1444 | |
| 1445 | <p> |
| 1446 | Anyroads, the post-instrumented version of our running example looks |
| 1447 | like this: |
| 1448 | |
| 1449 | <pre> |
| 1450 | Instrumented code: |
| 1451 | 0: GETVL %EDX, q0 |
| 1452 | 1: GETL %EDX, t0 |
| 1453 | |
| 1454 | 2: TAG1o q0 = Left4 ( q0 ) |
| 1455 | 3: INCL t0 |
| 1456 | |
| 1457 | 4: PUTVL q0, %EDX |
| 1458 | 5: PUTL t0, %EDX |
| 1459 | |
| 1460 | 6: TESTVL q0 |
| 1461 | 7: SETVL q0 |
| 1462 | 8: LOADVB (t0), q0 |
| 1463 | 9: LDB (t0), t0 |
| 1464 | |
| 1465 | 10: TAG1o q0 = SWiden14 ( q0 ) |
| 1466 | 11: WIDENL_Bs t0 |
| 1467 | |
| 1468 | 12: PUTVL q0, %EAX |
| 1469 | 13: PUTL t0, %EAX |
| 1470 | |
| 1471 | 14: GETVL %ECX, q8 |
| 1472 | 15: GETL %ECX, t8 |
| 1473 | |
| 1474 | 16: MOVL q0, q4 |
| 1475 | 17: SHLL $0x1, q4 |
| 1476 | 18: TAG2o q4 = UifU4 ( q8, q4 ) |
| 1477 | 19: TAG1o q4 = Left4 ( q4 ) |
| 1478 | 20: LEA2L 1(t8,t0,2), t4 |
| 1479 | |
| 1480 | 21: TESTVL q4 |
| 1481 | 22: SETVL q4 |
| 1482 | 23: LOADVB (t4), q10 |
| 1483 | 24: LDB (t4), t10 |
| 1484 | |
| 1485 | 25: SETVB q12 |
| 1486 | 26: MOVB $0x20, t12 |
| 1487 | |
| 1488 | 27: MOVL q10, q14 |
| 1489 | 28: TAG2o q14 = ImproveAND1_TQ ( t10, q14 ) |
| 1490 | 29: TAG2o q10 = UifU1 ( q12, q10 ) |
| 1491 | 30: TAG2o q10 = DifD1 ( q14, q10 ) |
| 1492 | 31: MOVL q12, q14 |
| 1493 | 32: TAG2o q14 = ImproveAND1_TQ ( t12, q14 ) |
| 1494 | 33: TAG2o q10 = DifD1 ( q14, q10 ) |
| 1495 | 34: MOVL q10, q16 |
| 1496 | 35: TAG1o q16 = PCast10 ( q16 ) |
| 1497 | 36: PUTVFo q16 |
| 1498 | 37: ANDB t12, t10 (-wOSZACP) |
| 1499 | |
| 1500 | 38: INCEIPo $9 |
| 1501 | |
| 1502 | 39: GETVFo q18 |
| 1503 | 40: TESTVo q18 |
| 1504 | 41: SETVo q18 |
| 1505 | 42: Jnzo $0x40435A50 (-rOSZACP) |
| 1506 | |
| 1507 | 43: JMPo $0x40435A5B |
| 1508 | </pre> |
| 1509 | |
| 1510 | |
| 1511 | <h3>UCode post-instrumentation cleanup</h3> |
| 1512 | |
| 1513 | <p> |
| 1514 | This pass, coordinated by <code>vg_cleanup()</code>, removes redundant |
| 1515 | definedness computation created by the simplistic instrumentation |
| 1516 | pass. It consists of two passes, |
| 1517 | <code>vg_propagate_definedness()</code> followed by |
| 1518 | <code>vg_delete_redundant_SETVs</code>. |
| 1519 | |
| 1520 | <p> |
| 1521 | <code>vg_propagate_definedness()</code> is a simple |
| 1522 | constant-propagation and constant-folding pass. It tries to determine |
| 1523 | which <code>TempReg</code>s containing V bits will always indicate |
| 1524 | "fully defined", and it propagates this information as far as it can, |
| 1525 | and folds out as many operations as possible. For example, the |
| 1526 | instrumentation for an ADD of a literal to a variable quantity will be |
| 1527 | reduced down so that the definedness of the result is simply the |
| 1528 | definedness of the variable quantity, since the literal is by |
| 1529 | definition fully defined. |
| 1530 | |
| 1531 | <p> |
| 1532 | <code>vg_delete_redundant_SETVs</code> removes <code>SETV</code>s on |
| 1533 | shadow <code>TempReg</code>s for which the next action is a write. |
| 1534 | I don't think there's anything else worth saying about this; it is |
| 1535 | simple. Read the sources for details. |
| 1536 | |
| 1537 | <p> |
| 1538 | So the cleaned-up running example looks like this. As above, I have |
| 1539 | inserted line breaks after every original (non-instrumentation) uinstr |
| 1540 | to aid readability. As with straightforward ucode optimisation, the |
| 1541 | results in this block are undramatic because it is so short; longer |
| 1542 | blocks benefit more because they have more redundancy which gets |
| 1543 | eliminated. |
| 1544 | |
| 1545 | |
| 1546 | <pre> |
| 1547 | at 29: delete UifU1 due to defd arg1 |
| 1548 | at 32: change ImproveAND1_TQ to MOV due to defd arg2 |
| 1549 | at 41: delete SETV |
| 1550 | at 31: delete MOV |
| 1551 | at 25: delete SETV |
| 1552 | at 22: delete SETV |
| 1553 | at 7: delete SETV |
| 1554 | |
| 1555 | 0: GETVL %EDX, q0 |
| 1556 | 1: GETL %EDX, t0 |
| 1557 | |
| 1558 | 2: TAG1o q0 = Left4 ( q0 ) |
| 1559 | 3: INCL t0 |
| 1560 | |
| 1561 | 4: PUTVL q0, %EDX |
| 1562 | 5: PUTL t0, %EDX |
| 1563 | |
| 1564 | 6: TESTVL q0 |
| 1565 | 8: LOADVB (t0), q0 |
| 1566 | 9: LDB (t0), t0 |
| 1567 | |
| 1568 | 10: TAG1o q0 = SWiden14 ( q0 ) |
| 1569 | 11: WIDENL_Bs t0 |
| 1570 | |
| 1571 | 12: PUTVL q0, %EAX |
| 1572 | 13: PUTL t0, %EAX |
| 1573 | |
| 1574 | 14: GETVL %ECX, q8 |
| 1575 | 15: GETL %ECX, t8 |
| 1576 | |
| 1577 | 16: MOVL q0, q4 |
| 1578 | 17: SHLL $0x1, q4 |
| 1579 | 18: TAG2o q4 = UifU4 ( q8, q4 ) |
| 1580 | 19: TAG1o q4 = Left4 ( q4 ) |
| 1581 | 20: LEA2L 1(t8,t0,2), t4 |
| 1582 | |
| 1583 | 21: TESTVL q4 |
| 1584 | 23: LOADVB (t4), q10 |
| 1585 | 24: LDB (t4), t10 |
| 1586 | |
| 1587 | 26: MOVB $0x20, t12 |
| 1588 | |
| 1589 | 27: MOVL q10, q14 |
| 1590 | 28: TAG2o q14 = ImproveAND1_TQ ( t10, q14 ) |
| 1591 | 30: TAG2o q10 = DifD1 ( q14, q10 ) |
| 1592 | 32: MOVL t12, q14 |
| 1593 | 33: TAG2o q10 = DifD1 ( q14, q10 ) |
| 1594 | 34: MOVL q10, q16 |
| 1595 | 35: TAG1o q16 = PCast10 ( q16 ) |
| 1596 | 36: PUTVFo q16 |
| 1597 | 37: ANDB t12, t10 (-wOSZACP) |
| 1598 | |
| 1599 | 38: INCEIPo $9 |
| 1600 | 39: GETVFo q18 |
| 1601 | 40: TESTVo q18 |
| 1602 | 42: Jnzo $0x40435A50 (-rOSZACP) |
| 1603 | |
| 1604 | 43: JMPo $0x40435A5B |
| 1605 | </pre> |
| 1606 | |
| 1607 | |
| 1608 | <h3>Translation from UCode</h3> |
| 1609 | |
| 1610 | This is all very simple, even though <code>vg_from_ucode.c</code> |
| 1611 | is a big file. Position-independent x86 code is generated into |
| 1612 | a dynamically allocated array <code>emitted_code</code>; this is |
| 1613 | doubled in size when it overflows. Eventually the array is handed |
| 1614 | back to the caller of <code>VG_(translate)</code>, who must copy |
| 1615 | the result into TC and TT, and free the array. |
| 1616 | |
| 1617 | <p> |
| 1618 | This file is structured into four layers of abstraction, which, |
| 1619 | thankfully, are glued back together with extensive |
| 1620 | <code>__inline__</code> directives. From the bottom upwards: |
| 1621 | |
| 1622 | <ul> |
| 1623 | <li>Address-mode emitters, <code>emit_amode_regmem_reg</code> et al. |
| 1624 | <p> |
| 1625 | <li>Emitters for specific x86 instructions. There are quite a lot of |
| 1626 | these, with names such as <code>emit_movv_offregmem_reg</code>. |
| 1627 | The <code>v</code> suffix is Intel parlance for a 16/32 bit insn; |
| 1628 | there are also <code>b</code> suffixes for 8 bit insns. |
| 1629 | <p> |
| 1630 | <li>The next level up are the <code>synth_*</code> functions, which |
| 1631 | synthesise possibly a sequence of raw x86 instructions to do some |
| 1632 | simple task. Some of these are quite complex because they have to |
| 1633 | work around Intel's silly restrictions on subregister naming. See |
| 1634 | <code>synth_nonshiftop_reg_reg</code> for example. |
| 1635 | <p> |
| 1636 | <li>Finally, at the top of the heap, we have |
| 1637 | <code>emitUInstr()</code>, |
| 1638 | which emits code for a single uinstr. |
| 1639 | </ul> |
| 1640 | |
| 1641 | <p> |
| 1642 | Some comments: |
| 1643 | <ul> |
| 1644 | <li>The hack for FPU instructions becomes apparent here. To do a |
| 1645 | <code>FPU</code> ucode instruction, we load the simulated FPU's |
| 1646 | state into from its <code>VG_(baseBlock)</code> into the real FPU |
| 1647 | using an x86 <code>frstor</code> insn, do the ucode |
| 1648 | <code>FPU</code> insn on the real CPU, and write the updated FPU |
| 1649 | state back into <code>VG_(baseBlock)</code> using an |
| 1650 | <code>fnsave</code> instruction. This is pretty brutal, but is |
| 1651 | simple and it works, and even seems tolerably efficient. There is |
| 1652 | no attempt to cache the simulated FPU state in the real FPU over |
| 1653 | multiple back-to-back ucode FPU instructions. |
| 1654 | <p> |
| 1655 | <code>FPU_R</code> and <code>FPU_W</code> are also done this way, |
| 1656 | with the minor complication that we need to patch in some |
| 1657 | addressing mode bits so the resulting insn knows the effective |
| 1658 | address to use. This is easy because of the regularity of the x86 |
| 1659 | FPU instruction encodings. |
| 1660 | <p> |
| 1661 | <li>An analogous trick is done with ucode insns which claim, in their |
| 1662 | <code>flags_r</code> and <code>flags_w</code> fields, that they |
| 1663 | read or write the simulated <code>%EFLAGS</code>. For such cases |
| 1664 | we first copy the simulated <code>%EFLAGS</code> into the real |
| 1665 | <code>%eflags</code>, then do the insn, then, if the insn says it |
| 1666 | writes the flags, copy back to <code>%EFLAGS</code>. This is a |
| 1667 | bit expensive, which is why the ucode optimisation pass goes to |
| 1668 | some effort to remove redundant flag-update annotations. |
| 1669 | </ul> |
| 1670 | |
| 1671 | <p> |
| 1672 | And so ... that's the end of the documentation for the instrumentating |
| 1673 | translator! It's really not that complex, because it's composed as a |
| 1674 | sequence of simple(ish) self-contained transformations on |
| 1675 | straight-line blocks of code. |
| 1676 | |
| 1677 | |
| 1678 | <h3>Top-level dispatch loop</h3> |
| 1679 | |
| 1680 | Urk. In <code>VG_(toploop)</code>. This is basically boring and |
| 1681 | unsurprising, not to mention fiddly and fragile. It needs to be |
| 1682 | cleaned up. |
| 1683 | |
| 1684 | <p> |
| 1685 | The only perhaps surprise is that the whole thing is run |
| 1686 | on top of a <code>setjmp</code>-installed exception handler, because, |
| 1687 | supposing a translation got a segfault, we have to bail out of the |
| 1688 | Valgrind-supplied exception handler <code>VG_(oursignalhandler)</code> |
| 1689 | and immediately start running the client's segfault handler, if it has |
| 1690 | one. In particular we can't finish the current basic block and then |
| 1691 | deliver the signal at some convenient future point, because signals |
| 1692 | like SIGILL, SIGSEGV and SIGBUS mean that the faulting insn should not |
| 1693 | simply be re-tried. (I'm sure there is a clearer way to explain this). |
| 1694 | |
| 1695 | |
| 1696 | <h3>Exceptions, creating new translations</h3> |
| 1697 | <h3>Self-modifying code</h3> |
| 1698 | |
| 1699 | <h3>Lazy updates of the simulated program counter</h3> |
| 1700 | |
| 1701 | Simulated <code>%EIP</code> is not updated after every simulated x86 |
| 1702 | insn as this was regarded as too expensive. Instead ucode |
| 1703 | <code>INCEIP</code> insns move it along as and when necessary. |
| 1704 | Currently we don't allow it to fall more than 4 bytes behind reality |
| 1705 | (see <code>VG_(disBB)</code> for the way this works). |
| 1706 | <p> |
| 1707 | Note that <code>%EIP</code> is always brought up to date by the inner |
| 1708 | dispatch loop in <code>VG_(dispatch)</code>, so that if the client |
| 1709 | takes a fault we know at least which basic block this happened in. |
| 1710 | |
| 1711 | |
| 1712 | <h3>The translation cache and translation table</h3> |
| 1713 | |
| 1714 | <h3>Signals</h3> |
| 1715 | |
| 1716 | Horrible, horrible. <code>vg_signals.c</code>. |
| 1717 | Basically, since we have to intercept all system |
| 1718 | calls anyway, we can see when the client tries to install a signal |
| 1719 | handler. If it does so, we make a note of what the client asked to |
| 1720 | happen, and ask the kernel to route the signal to our own signal |
| 1721 | handler, <code>VG_(oursignalhandler)</code>. This simply notes the |
| 1722 | delivery of signals, and returns. |
| 1723 | |
| 1724 | <p> |
| 1725 | Every 1000 basic blocks, we see if more signals have arrived. If so, |
| 1726 | <code>VG_(deliver_signals)</code> builds signal delivery frames on the |
| 1727 | client's stack, and allows their handlers to be run. Valgrind places |
| 1728 | in these signal delivery frames a bogus return address, |
| 1729 | </code>VG_(signalreturn_bogusRA)</code>, and checks all jumps to see |
| 1730 | if any jump to it. If so, this is a sign that a signal handler is |
| 1731 | returning, and if so Valgrind removes the relevant signal frame from |
| 1732 | the client's stack, restores the from the signal frame the simulated |
| 1733 | state before the signal was delivered, and allows the client to run |
| 1734 | onwards. We have to do it this way because some signal handlers never |
| 1735 | return, they just <code>longjmp()</code>, which nukes the signal |
| 1736 | delivery frame. |
| 1737 | |
| 1738 | <p> |
| 1739 | The Linux kernel has a different but equally horrible hack for |
| 1740 | detecting signal handler returns. Discovering it is left as an |
| 1741 | exercise for the reader. |
| 1742 | |
| 1743 | |
| 1744 | |
| 1745 | <h3>Errors, error contexts, error reporting, suppressions</h3> |
| 1746 | <h3>Client malloc/free</h3> |
| 1747 | <h3>Low-level memory management</h3> |
| 1748 | <h3>A and V bitmaps</h3> |
| 1749 | <h3>Symbol table management</h3> |
| 1750 | <h3>Dealing with system calls</h3> |
| 1751 | <h3>Namespace management</h3> |
| 1752 | <h3>GDB attaching</h3> |
| 1753 | <h3>Non-dependence on glibc or anything else</h3> |
| 1754 | <h3>The leak detector</h3> |
| 1755 | <h3>Performance problems</h3> |
| 1756 | <h3>Continuous sanity checking</h3> |
| 1757 | <h3>Tracing, or not tracing, child processes</h3> |
| 1758 | <h3>Assembly glue for syscalls</h3> |
| 1759 | |
| 1760 | |
| 1761 | <hr width="100%"> |
| 1762 | |
| 1763 | <h2>Extensions</h2> |
| 1764 | |
| 1765 | Some comments about Stuff To Do. |
| 1766 | |
| 1767 | <h3>Bugs</h3> |
| 1768 | |
| 1769 | Stephan Kulow and Marc Mutz report problems with kmail in KDE 3 CVS |
| 1770 | (RC2 ish) when run on Valgrind. Stephan has it deadlocking; Marc has |
| 1771 | it looping at startup. I can't repro either behaviour. Needs |
| 1772 | repro-ing and fixing. |
| 1773 | |
| 1774 | |
| 1775 | <h3>Threads</h3> |
| 1776 | |
| 1777 | Doing a good job of thread support strikes me as almost a |
| 1778 | research-level problem. The central issues are how to do fast cheap |
| 1779 | locking of the <code>VG_(primary_map)</code> structure, whether or not |
| 1780 | accesses to the individual secondary maps need locking, what |
| 1781 | race-condition issues result, and whether the already-nasty mess that |
| 1782 | is the signal simulator needs further hackery. |
| 1783 | |
| 1784 | <p> |
| 1785 | I realise that threads are the most-frequently-requested feature, and |
| 1786 | I am thinking about it all. If you have guru-level understanding of |
| 1787 | fast mutual exclusion mechanisms and race conditions, I would be |
| 1788 | interested in hearing from you. |
| 1789 | |
| 1790 | |
| 1791 | <h3>Verification suite</h3> |
| 1792 | |
| 1793 | Directory <code>tests/</code> contains various ad-hoc tests for |
| 1794 | Valgrind. However, there is no systematic verification or regression |
| 1795 | suite, that, for example, exercises all the stuff in |
| 1796 | <code>vg_memory.c</code>, to ensure that illegal memory accesses and |
| 1797 | undefined value uses are detected as they should be. It would be good |
| 1798 | to have such a suite. |
| 1799 | |
| 1800 | |
| 1801 | <h3>Porting to other platforms</h3> |
| 1802 | |
| 1803 | It would be great if Valgrind was ported to FreeBSD and x86 NetBSD, |
| 1804 | and to x86 OpenBSD, if it's possible (doesn't OpenBSD use a.out-style |
| 1805 | executables, not ELF ?) |
| 1806 | |
| 1807 | <p> |
| 1808 | The main difficulties, for an x86-ELF platform, seem to be: |
| 1809 | |
| 1810 | <ul> |
| 1811 | <li>You'd need to rewrite the <code>/proc/self/maps</code> parser |
| 1812 | (<code>vg_procselfmaps.c</code>). |
| 1813 | Easy. |
| 1814 | <p> |
| 1815 | <li>You'd need to rewrite <code>vg_syscall_mem.c</code>, or, more |
| 1816 | specifically, provide one for your OS. This is tedious, but you |
| 1817 | can implement syscalls on demand, and the Linux kernel interface |
| 1818 | is, for the most part, going to look very similar to the *BSD |
| 1819 | interfaces, so it's really a copy-paste-and-modify-on-demand job. |
| 1820 | As part of this, you'd need to supply a new |
| 1821 | <code>vg_kerneliface.h</code> file. |
| 1822 | <p> |
| 1823 | <li>You'd also need to change the syscall wrappers for Valgrind's |
| 1824 | internal use, in <code>vg_mylibc.c</code>. |
| 1825 | </ul> |
| 1826 | |
| 1827 | All in all, I think a port to x86-ELF *BSDs is not really very |
| 1828 | difficult, and in some ways I would like to see it happen, because |
| 1829 | that would force a more clear factoring of Valgrind into platform |
| 1830 | dependent and independent pieces. Not to mention, *BSD folks also |
| 1831 | deserve to use Valgrind just as much as the Linux crew do. |
| 1832 | |
| 1833 | |
| 1834 | <p> |
| 1835 | <hr width="100%"> |
| 1836 | |
| 1837 | <h2>Easy stuff which ought to be done</h2> |
| 1838 | |
| 1839 | <h3>MMX instructions</h3> |
| 1840 | |
| 1841 | MMX insns should be supported, using the same trick as for FPU insns. |
| 1842 | If the MMX registers are not used to copy uninitialised junk from one |
| 1843 | place to another in memory, this means we don't have to actually |
| 1844 | simulate the internal MMX unit state, so the FPU hack applies. This |
| 1845 | should be fairly easy. |
| 1846 | |
| 1847 | |
| 1848 | |
| 1849 | <h3>Fix stabs-info reader</h3> |
| 1850 | |
| 1851 | The machinery in <code>vg_symtab2.c</code> which reads "stabs" style |
| 1852 | debugging info is pretty weak. It usually correctly translates |
| 1853 | simulated program counter values into line numbers and procedure |
| 1854 | names, but the file name is often completely wrong. I think the |
| 1855 | logic used to parse "stabs" entries is weak. It should be fixed. |
| 1856 | The simplest solution, IMO, is to copy either the logic or simply the |
| 1857 | code out of GNU binutils which does this; since GDB can clearly get it |
| 1858 | right, binutils (or GDB?) must have code to do this somewhere. |
| 1859 | |
| 1860 | |
| 1861 | |
| 1862 | |
| 1863 | |
| 1864 | <h3>BT/BTC/BTS/BTR</h3> |
| 1865 | |
| 1866 | These are x86 instructions which test, complement, set, or reset, a |
| 1867 | single bit in a word. At the moment they are both incorrectly |
| 1868 | implemented and incorrectly instrumented. |
| 1869 | |
| 1870 | <p> |
| 1871 | The incorrect instrumentation is due to use of helper functions. This |
| 1872 | means we lose bit-level definedness tracking, which could wind up |
| 1873 | giving spurious uninitialised-value use errors. The Right Thing to do |
| 1874 | is to invent a couple of new UOpcodes, I think <code>GET_BIT</code> |
| 1875 | and <code>SET_BIT</code>, which can be used to implement all 4 x86 |
| 1876 | insns, get rid of the helpers, and give bit-accurate instrumentation |
| 1877 | rules for the two new UOpcodes. |
| 1878 | |
| 1879 | <p> |
| 1880 | I realised the other day that they are mis-implemented too. The x86 |
| 1881 | insns take a bit-index and a register or memory location to access. |
| 1882 | For registers the bit index clearly can only be in the range zero to |
| 1883 | register-width minus 1, and I assumed the same applied to memory |
| 1884 | locations too. But evidently not; for memory locations the index can |
| 1885 | be arbitrary, and the processor will index arbitrarily into memory as |
| 1886 | a result. This too should be fixed. Sigh. Presumably indexing |
| 1887 | outside the immediate word is not actually used by any programs yet |
| 1888 | tested on Valgrind, for otherwise they (presumably) would simply not |
| 1889 | work at all. If you plan to hack on this, first check the Intel docs |
| 1890 | to make sure my understanding is really correct. |
| 1891 | |
| 1892 | |
| 1893 | |
| 1894 | <h3>Using PREFETCH instructions</h3> |
| 1895 | |
| 1896 | Here's a small but potentially interesting project for performance |
| 1897 | junkies. Experiments with valgrind's code generator and optimiser(s) |
| 1898 | suggest that reducing the number of instructions executed in the |
| 1899 | translations and mem-check helpers gives disappointingly small |
| 1900 | performance improvements. Perhaps this is because performance of |
| 1901 | Valgrindified code is limited by cache misses. After all, each read |
| 1902 | in the original program now gives rise to at least three reads, one |
| 1903 | for the <code>VG_(primary_map)</code>, one of the resulting |
| 1904 | secondary, and the original. Not to mention, the instrumented |
| 1905 | translations are 13 to 14 times larger than the originals. All in all |
| 1906 | one would expect the memory system to be hammered to hell and then |
| 1907 | some. |
| 1908 | |
| 1909 | <p> |
| 1910 | So here's an idea. An x86 insn involving a read from memory, after |
| 1911 | instrumentation, will turn into ucode of the following form: |
| 1912 | <pre> |
| 1913 | ... calculate effective addr, into ta and qa ... |
| 1914 | TESTVL qa -- is the addr defined? |
| 1915 | LOADV (ta), qloaded -- fetch V bits for the addr |
| 1916 | LOAD (ta), tloaded -- do the original load |
| 1917 | </pre> |
| 1918 | At the point where the <code>LOADV</code> is done, we know the actual |
| 1919 | address (<code>ta</code>) from which the real <code>LOAD</code> will |
| 1920 | be done. We also know that the <code>LOADV</code> will take around |
| 1921 | 20 x86 insns to do. So it seems plausible that doing a prefetch of |
| 1922 | <code>ta</code> just before the <code>LOADV</code> might just avoid a |
| 1923 | miss at the <code>LOAD</code> point, and that might be a significant |
| 1924 | performance win. |
| 1925 | |
| 1926 | <p> |
| 1927 | Prefetch insns are notoriously tempermental, more often than not |
| 1928 | making things worse rather than better, so this would require |
| 1929 | considerable fiddling around. It's complicated because Intels and |
| 1930 | AMDs have different prefetch insns with different semantics, so that |
| 1931 | too needs to be taken into account. As a general rule, even placing |
| 1932 | the prefetches before the <code>LOADV</code> insn is too near the |
| 1933 | <code>LOAD</code>; the ideal distance is apparently circa 200 CPU |
| 1934 | cycles. So it might be worth having another analysis/transformation |
| 1935 | pass which pushes prefetches as far back as possible, hopefully |
| 1936 | immediately after the effective address becomes available. |
| 1937 | |
| 1938 | <p> |
| 1939 | Doing too many prefetches is also bad because they soak up bus |
| 1940 | bandwidth / cpu resources, so some cleverness in deciding which loads |
| 1941 | to prefetch and which to not might be helpful. One can imagine not |
| 1942 | prefetching client-stack-relative (<code>%EBP</code> or |
| 1943 | <code>%ESP</code>) accesses, since the stack in general tends to show |
| 1944 | good locality anyway. |
| 1945 | |
| 1946 | <p> |
| 1947 | There's quite a lot of experimentation to do here, but I think it |
| 1948 | might make an interesting week's work for someone. |
| 1949 | |
| 1950 | <p> |
| 1951 | As of 15-ish March 2002, I've started to experiment with this, using |
| 1952 | the AMD <code>prefetch/prefetchw</code> insns. |
| 1953 | |
| 1954 | |
| 1955 | |
| 1956 | <h3>User-defined permission ranges</h3> |
| 1957 | |
| 1958 | This is quite a large project -- perhaps a month's hacking for a |
| 1959 | capable hacker to do a good job -- but it's potentially very |
| 1960 | interesting. The outcome would be that Valgrind could detect a |
| 1961 | whole class of bugs which it currently cannot. |
| 1962 | |
| 1963 | <p> |
| 1964 | The presentation falls into two pieces. |
| 1965 | |
| 1966 | <p> |
| 1967 | <b>Part 1: user-defined address-range permission setting</b> |
| 1968 | <p> |
| 1969 | |
| 1970 | Valgrind intercepts the client's <code>malloc</code>, |
| 1971 | <code>free</code>, etc calls, watches system calls, and watches the |
| 1972 | stack pointer move. This is currently the only way it knows about |
| 1973 | which addresses are valid and which not. Sometimes the client program |
| 1974 | knows extra information about its memory areas. For example, the |
| 1975 | client could at some point know that all elements of an array are |
| 1976 | out-of-date. We would like to be able to convey to Valgrind this |
| 1977 | information that the array is now addressable-but-uninitialised, so |
| 1978 | that Valgrind can then warn if elements are used before they get new |
| 1979 | values. |
| 1980 | |
| 1981 | <p> |
| 1982 | What I would like are some macros like this: |
| 1983 | <pre> |
| 1984 | VALGRIND_MAKE_NOACCESS(addr, len) |
| 1985 | VALGRIND_MAKE_WRITABLE(addr, len) |
| 1986 | VALGRIND_MAKE_READABLE(addr, len) |
| 1987 | </pre> |
| 1988 | and also, to check that memory is addressible/initialised, |
| 1989 | <pre> |
| 1990 | VALGRIND_CHECK_ADDRESSIBLE(addr, len) |
| 1991 | VALGRIND_CHECK_INITIALISED(addr, len) |
| 1992 | </pre> |
| 1993 | |
| 1994 | <p> |
| 1995 | I then include in my sources a header defining these macros, rebuild |
| 1996 | my app, run under Valgrind, and get user-defined checks. |
| 1997 | |
| 1998 | <p> |
| 1999 | Now here's a neat trick. It's a nuisance to have to re-link the app |
| 2000 | with some new library which implements the above macros. So the idea |
| 2001 | is to define the macros so that the resulting executable is still |
| 2002 | completely stand-alone, and can be run without Valgrind, in which case |
| 2003 | the macros do nothing, but when run on Valgrind, the Right Thing |
| 2004 | happens. How to do this? The idea is for these macros to turn into a |
| 2005 | piece of inline assembly code, which (1) has no effect when run on the |
| 2006 | real CPU, (2) is easily spotted by Valgrind's JITter, and (3) no sane |
| 2007 | person would ever write, which is important for avoiding false matches |
| 2008 | in (2). So here's a suggestion: |
| 2009 | <pre> |
| 2010 | VALGRIND_MAKE_NOACCESS(addr, len) |
| 2011 | </pre> |
| 2012 | becomes (roughly speaking) |
| 2013 | <pre> |
| 2014 | movl addr, %eax |
| 2015 | movl len, %ebx |
| 2016 | movl $1, %ecx -- 1 describes the action; MAKE_WRITABLE might be |
| 2017 | -- 2, etc |
| 2018 | rorl $13, %ecx |
| 2019 | rorl $19, %ecx |
| 2020 | rorl $11, %eax |
| 2021 | rorl $21, %eax |
| 2022 | </pre> |
| 2023 | The rotate sequences have no effect, and it's unlikely they would |
| 2024 | appear for any other reason, but they define a unique byte-sequence |
| 2025 | which the JITter can easily spot. Using the operand constraints |
| 2026 | section at the end of a gcc inline-assembly statement, we can tell gcc |
| 2027 | that the assembly fragment kills <code>%eax</code>, <code>%ebx</code>, |
| 2028 | <code>%ecx</code> and the condition codes, so this fragment is made |
| 2029 | harmless when not running on Valgrind, runs quickly when not on |
| 2030 | Valgrind, and does not require any other library support. |
| 2031 | |
| 2032 | |
| 2033 | <p> |
| 2034 | <b>Part 2: using it to detect interference between stack variables</b> |
| 2035 | <p> |
| 2036 | |
| 2037 | Currently Valgrind cannot detect errors of the following form: |
| 2038 | <pre> |
| 2039 | void fooble ( void ) |
| 2040 | { |
| 2041 | int a[10]; |
| 2042 | int b[10]; |
| 2043 | a[10] = 99; |
| 2044 | } |
| 2045 | </pre> |
| 2046 | Now imagine rewriting this as |
| 2047 | <pre> |
| 2048 | void fooble ( void ) |
| 2049 | { |
| 2050 | int spacer0; |
| 2051 | int a[10]; |
| 2052 | int spacer1; |
| 2053 | int b[10]; |
| 2054 | int spacer2; |
| 2055 | VALGRIND_MAKE_NOACCESS(&spacer0, sizeof(int)); |
| 2056 | VALGRIND_MAKE_NOACCESS(&spacer1, sizeof(int)); |
| 2057 | VALGRIND_MAKE_NOACCESS(&spacer2, sizeof(int)); |
| 2058 | a[10] = 99; |
| 2059 | } |
| 2060 | </pre> |
| 2061 | Now the invalid write is certain to hit <code>spacer0</code> or |
| 2062 | <code>spacer1</code>, so Valgrind will spot the error. |
| 2063 | |
| 2064 | <p> |
| 2065 | There are two complications. |
| 2066 | |
| 2067 | <p> |
| 2068 | The first is that we don't want to annotate sources by hand, so the |
| 2069 | Right Thing to do is to write a C/C++ parser, annotator, prettyprinter |
| 2070 | which does this automatically, and run it on post-CPP'd C/C++ source. |
| 2071 | See http://www.cacheprof.org for an example of a system which |
| 2072 | transparently inserts another phase into the gcc/g++ compilation |
| 2073 | route. The parser/prettyprinter is probably not as hard as it sounds; |
| 2074 | I would write it in Haskell, a powerful functional language well |
| 2075 | suited to doing symbolic computation, with which I am intimately |
| 2076 | familar. There is already a C parser written in Haskell by someone in |
| 2077 | the Haskell community, and that would probably be a good starting |
| 2078 | point. |
| 2079 | |
| 2080 | <p> |
| 2081 | The second complication is how to get rid of these |
| 2082 | <code>NOACCESS</code> records inside Valgrind when the instrumented |
| 2083 | function exits; after all, these refer to stack addresses and will |
| 2084 | make no sense whatever when some other function happens to re-use the |
| 2085 | same stack address range, probably shortly afterwards. I think I |
| 2086 | would be inclined to define a special stack-specific macro |
| 2087 | <pre> |
| 2088 | VALGRIND_MAKE_NOACCESS_STACK(addr, len) |
| 2089 | </pre> |
| 2090 | which causes Valgrind to record the client's <code>%ESP</code> at the |
| 2091 | time it is executed. Valgrind will then watch for changes in |
| 2092 | <code>%ESP</code> and discard such records as soon as the protected |
| 2093 | area is uncovered by an increase in <code>%ESP</code>. I hesitate |
| 2094 | with this scheme only because it is potentially expensive, if there |
| 2095 | are hundreds of such records, and considering that changes in |
| 2096 | <code>%ESP</code> already require expensive messing with stack access |
| 2097 | permissions. |
| 2098 | |
| 2099 | <p> |
| 2100 | This is probably easier and more robust than for the instrumenter |
| 2101 | program to try and spot all exit points for the procedure and place |
| 2102 | suitable deallocation annotations there. Plus C++ procedures can |
| 2103 | bomb out at any point if they get an exception, so spotting return |
| 2104 | points at the source level just won't work at all. |
| 2105 | |
| 2106 | <p> |
| 2107 | Although some work, it's all eminently doable, and it would make |
| 2108 | Valgrind into an even-more-useful tool. |
| 2109 | |
sewardj | de4a1d0 | 2002-03-22 01:27:54 +0000 | [diff] [blame] | 2110 | |
| 2111 | <p> |
| 2112 | </body> |
| 2113 | </html> |