|
From: Julian S. <js...@ac...> - 2005-02-14 11:19:17
|
I had a run-in last night with mmap. This, recent amd64
hackery, and contemplation of ppc and MacOSX, got me thinking
again about address space layout.
Currently on x86 we divide the address space at some point
(eg, 0x52000000), force the client to exist below that boundary
and give all above it to V. This scheme allows pointercheck to
be implemented for free using x86 segmentation.
On x86 that works well, although it does seem to have given
various kinds of brittleness when running large processes
and/or for people with unusual kernel/user address boundaries.
On amd64 that scheme isn't going to work, since all
client code has to be below 2G. A more flexible layout is
needed.
On ppc32, and other architectures, which I'm sure we'll
eventually get to, we can't implement pointercheck the way we
do now anyway.
To support MacOSX and other OSs, a more flexible approach
wouldn't hurt.
I've been thinking about a low-overhead, portable, software
implementation of pointercheck which would allow more flexibility.
One observation is (unless I am wrong) is that pointercheck
is valueless when running Memcheck, since Memcheck should be
able to catch all illegal accesses (if this isn't true then
Memcheck is broken and we should fix it). That means we
can omit pointercheck when doing Memcheck and so any
software-based checking scheme will have zero overhead for
our most-used tool.
-------------
The idea is to divide the process' address space up into
large blocks, call them superblocks. Each superblock is
2^n sized and 2^n aligned (huge pages, if you like). Currently
I am thinking of having 64M-sized superblocks.
Each superblock is allocated either to the client, to valgrind,
or is unallocated. Valgrind intercepts and messes with the client's
mmap calls to ensure they fall inside client-allocated superblocks;
dually V ensures all its own code and data, including shadow data,
falls inside its own superblocks. Unallocated superblocks are
handed out on demand. If we need to work around host-specific
constraints (eg amd64 code < 2G) then specific superblock ranges
can be reserved for the host only.
Access checks are performed using a table of booleans (bytes),
one for each superblock in the address space (with some qualification
for 64-bit address spaces, see below). The checking code can easily
enough be expressed in Vex's IR and turned into efficient machine
code by Vex's back ends, so there is no portability issue there.
A check is a basically
if (table[address >> n])
goto invalid-access
If the table is accessible at a fixed offset from the guest state
pointer, this becomes four insns on x86:
movl %addr, %tmp
shrl $n, %tmp
testb $0, offset(%ebp, %tmp, 1)
jz OK
<handle failure somehow>
OK:
There are a couple of options for <handle failure now>, which need
to be investigated for their impact on code size and the extent to
which they inhibit IR optimisation. Either way, they can be expressed
purely in IR, so no portability questions there either.
Why 64M-sized blocks? 64M is a coarse but just-about-manageable
granularity. On a 32-bit target, with 64M superblocks, the check
table has only 64 entries -- that is, 64 bytes -- so accesses to it
are unlikely to cause significant cache pollution (iow I hope all of
it will end up permanently in D1).
On a 64-bit target, we clearly cannot have a check table covering
the entire address space since that would require 2^38 entries.
However, even a 4096-entry table would cover 256GB of address space,
which is more than enough for the foreseeable future. The access
test would become a little more expensive because it would also have
to test that the upper bits of the address which are not covered by
the table, are all zero -- assuming the table maps the address
space of 0 - 256GB and not some other part.
So, what am I missing?
J
|