Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

On 5/25/12 7:53 AM, Baozeng wrote:
[snip]

As for the additions/subtraction, I stared at this code before, and couldn't figure out any explanation for it. Hopefully someone else can shed some light on it?

This code is implementing out-of-bounds pointers as described in Section 2.4 of the BBC paper.  Please read this section of the paper.  If it is still not clear what the code does after reading that section again, please email the list, and I will assist.

I took a look at BBC paper, but still cannot understand it clearly. Could you explain it using a small example?

Let's say you have an out-of-bounds (OOB) pointer that is less than slot_size/2 bytes outside of its referent memory object.  You mask off the high bits of the OOB pointer so that you see where in the address space it originally pointed.  Call this pointer p.

The first question is ask is whether p is pointing to an address before the beginning of the memory object or after the end of the memory object.  This is done be examining which portion of the slot p is in.  If p underflowed the buffer, then it will be in the second half of the slot that precedes the referent.  If p overflowed the memory object, then p will point in the first half of the slot that comes after the referent.

How can you find the referent?  If p is in the slot before the start of the referent, you can add SLOTSIZE to p, and you'll be pointing back into the referent memory object.  If you're in the slot just after the referent, you can subtract SLOTSIZE from p to get back into the referent.

Does this make sense?

So, having read over the code and the paper, there are some obvious improvements to be made:

1) There should be a big comment that explains what, conceptually, is being done (and a potential reference to Section 2.4 in the paper).

2) There should be inline functions called getActualValue() and rewritePtr() that convert a pointer to and from its OOB representation (instead of using SET_MASK and UNSET_MASK everywhere).

3) There should be an inline isInUpperHalf() function that determines whether a pointer is within the lower or upper half of a slot.  This function should configure its mask value based off of SLOTSIZE (or there should be another const integer value to hold it with a comment indicating that SLOTSIZE and the mask value need to be changed together).

4) The decision to add or subtract should be done with code like the following:

p += ((isInUpperHalf()) ? SLOTSIZE : -SLOTSIZE);

This should make it easier for the compiler to optimize the code.

-- John T.