Saturday, 30 October 2010

BSDNT - v0.20 redzones

In this update we implement another improvement to the test code in bsdnt. I don't know
what the correct name is, but I call them redzones.

The basic idea is this: suppose you have a function nn_blah say, and it writes to an nn_t
b say. If it writes well beyond the allocated space for b, then almost certainly a
segfault will occur. But what if it only writes a word or two before the beginning or
after the end of the allocated space? Very likely this will cause a segfault only on
some systems, depending on the granularity of the heap allocator and depending
on what other bsdnt data might be in the overwritten space!

So what if we could detect this kind of error? Well, that is what redzones hope to do.
Essentially if an nn_t b is allocated with m words of space, when redzones are turned on
it allocates m + 2C words of space for some small constant C. It then fills the first
and last C words of b with known words of data (usually some recognisable pattern of bits).

When the garbage collector cleans up, it examines the redzones to ensure that they have
not been altered. If they have, they raise an error.

The nn_t b is set to point just after the first C words, which contain the redzone, and in
every other respect act like a normal nn_t. The user needn't know that an extra C words
of data were allocated immediately before and after the length m nn_t they requested.
Nor do they need to be aware of the checking that goes on when the nn_t is finally cleaned
up, that the redzones haven't been touched.

Of course it's nice to be able to turn redzones off sometimes, when testing the library.
Therefore I've added a configure option -noredzones which turns off redzones if they are
not required. This works by setting a #define WANT_REDZONES 0 in config.h. The
memory allocator for nn_t's and the garbage collector both operate differently if redzones
are turned on.

At present, the only way to allocate memory for nn_t's in test code is to use
randoms_of_len, so it is convenient to rewrite this to call a function alloc_redzoned_nn
instead of malloc, and for the garbage collector to call free_redzoned_nn. These new
functions are defined in test.c.

The only difference when WANT_REDZONES is set in config.h is that REDZONE_WORDS, which is defined in test.h is changed from 0 to 4 words (meaning 4 redzone words are to be
allocated at each end of a redzoned nn_t). Having redzones of length 0 is the same as not
having them at all. So this makes the functions easy to write.

Also in test.h REDZONE_BYTE is defined to the hexaecimal byte 0xA which has binary bit
pattern 1010, i.e. alternating one's and zeroes. This is the value that is placed into the
redzones byte-by-byte before the nn_t is used. At the end, when they are cleaned up, the
garbage collector examines the redzones to ensure they are still filled with these bytes.

Fortunately checking redzones does not dramatically slow down our test code, and no new
test failures result. This means it is highly likely that our nn_t functions do not overwrite
their bounds. To check that the new redzones code works, it is a simple matter of mocking
up a broken function which overwrites its bounds. The new code complains loudly as it
should, unless redzones are switched off at configure time.

The code for today's update is here: v0.20

Previous article: v0.19 - asserts
Next article: v0.21 - prngs

No comments:

Post a Comment