tst-malloc-usable failure

[James Lemke <jwlemke at codesourcery dot com>]

Using an internal mips-linux target I have been getting a failure for
tst-malloc-usable:
malloc_usable_size: expected 7 but got 11

After some investigation, I found a flaw in the malloc checking algorithm.
The problem can be seen in this code from glibc-2.17/malloc/hooks.c:

/* A simple, standard set of debugging hooks.  Overhead is `only' one
    byte per chunk; still this will catch most cases of double frees or
    overruns.  The goal here is to avoid obscure crashes due to invalid
    usage, unlike in the MALLOC_DEBUG code. */

#define MAGICBYTE(p) ( ( ((size_t)p >> 3) ^ ((size_t)p >> 11)) & 0xFF )

/* Visualize the chunk as being partitioned into blocks of 256 bytes from the
(sic - they are actually 255 byte blocks)
    highest address of the chunk, downwards.  The beginning of each block tells
    us the size of the previous block, up to the actual size of the requested
    memory.  Our magic byte is right at the end of the requested size, so we
    must reach it with this iteration, otherwise we have witnessed a memory
    corruption.  */
static size_t
malloc_check_get_size(mchunkptr p)
{
   size_t size;
   unsigned char c;
   unsigned char magic = MAGICBYTE(p);

   assert(using_malloc_checking == 1);

   for (size = chunksize(p) - 1 + (chunk_is_mmapped(p) ? 0 : SIZE_SZ);
        (c = ((unsigned char*)p)[size]) != magic;
        size -= c) {
     if(c<=0 || size<(c+2*SIZE_SZ)) {
       malloc_printerr(check_action, "malloc_check_get_size: memory corruption",
                       chunk2mem(p));
       return 0;
     }
   }

   /* chunk2mem size.  */
   return size - 2*SIZE_SZ;
}

1/ The "magic byte" is constructed as a hash of the chunk pointer.
2/ The magic byte is written immediately following the user portion of the
chunk.
3/ A length byte is written to the last byte of every partially used and
unused 255-byte block.
4/ The code above starts at the last byte of the chunk, reading a length byte
and then moving down (decreasing address) by that count and iterating.  It
stops when it reads the "magic byte", but in this case the first length byte
has the same value as the magic byte and the loop ends early.

When I run this test MAGICBYTE gives a value of 0x04.  The test calls malloc
with a size of 7 bytes.  With overhead and alignment, the chunk allocated is
20 bytes.  From low to high addresses we have:
mchunkptr:
   4 bytes length of previous chunk
   4 bytes length of chunk (16)
   7 bytes user values
   1 byte magic value (0x04)
   3 bytes unused
   1 byte length of unused (0x04)

The initial read is the last byte (chunk[19]) which matches the magic byte and
the loop terminates with zero iterations.  This gives a size of 7+1+3=11.
Which is wrong.

Since the "magic" value is a hash it can be any value (0-0xff).
The length bytes can be any value from 1-0xff, so I don't see a way to
distinguish the two and terminate the loop correctly.

A possible solution is to always terminate the sequence of length bytes with
a null entry.  Since the lengths are inclusive, the chain would always end
with a null "1" entry.  The "magic" value would always follow the null
entry.  The disadvantage is that you must have a length chain even if it is 
just the null entry.  Checking overhead is 2 bytes instead of 1.

The example above would become:
mchunkptr:
   4 bytes length of previous chunk
   4 bytes length of chunk (16)
   7 bytes used for caller values
   1 byte magic value (0x04)
   1 byte length (0x01) - the null entry
   2 bytes unused
   1 byte length of unused (0x03)

Or I'm open to other ideas..
Jim.

--
Jim Lemke
Mentor Graphics / CodeSourcery
Orillia Ontario