Blame - memcheck/docs/mc_techdocs.html - fp2-dev/platform/external/valgrind

blob: 3566b96a90819c996ea946261ed1c02d53830ec8 [file] [log] [blame]

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