A debugging implementation of malloc

[jacob navia]

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.

Here is the code, and the explanations that go with it.

I would appreciate your feedback both about the code and
the associated explanations.

---------------------------------------------------------------------

Instead of using directly malloc/free here are two implementations of
equivalent functions with some added safety features:
o Freeing NULL is allowed and is not an error.
o Double freeing is made impossible.
o Any overwrite immediately at the end of the block is checked for.
o Memory is initialized to zero.
o A count of allocated memory is kept in a global variable.

#include <stdlib.h>
#define MAGIC 0xFFFF
#define SIGNATURE 12345678L
size_t AllocatedMemory;
void *allocate(size_t size)
{
register char *r;
register int *ip = NULL;
size += 3 * sizeof(int);
r = malloc(size);
if (r == NULL)
return r;
AllocatedMemory += size;
ip = (int *) r;
// At the start of the block we write the signature
*ip++ = SIGNATURE;
// Then we write the size of the block in bytes
*ip++ = (int) size;
// We zero the data space
memset(ip, 0, size - 3*sizeof(int));
// We write the magic number at the end of the block,
// just behind the data
ip = (int *) (&r[size - sizeof(int)]);
*ip = MAGIC;
// Return a pointer to the start of the data area
return (r + 2 * sizeof(int));
}
void release(void *pp)
{
register int *ip = NULL;
int s;
register char *p = pp;
if (p == NULL) // Freeing NULL is allowed
return;
// The start of the block is two integers before the data.
p -= 2 * sizeof(int);
ip = (int *) p;
if (*ip == SIGNATURE) {
// Overwrite the signature so that this block
// can’t be freed again
*ip++ = 0;
s = *ip;
ip = (int *) (&p[s - sizeof(int)]);
if (*ip != MAGIC) {
ErorPrintf(“Overwritten block size %d”, s);
return;
}
*ip = 0;
AllocatedMemory -= s;
free(p);
}
else {
/* The block has been overwritten. Complain. */
ErrorPrintf(“Wrong block passed to release”);
}
}

The allocate function adds to the requested size space for 3 integers.
1) The first is a magic number (a signature) that allows the
identification of this block as a block allocated by our allocation
system.
2) The second is the size of the block. After this two numbers, the data
follows.
3) The data is followed by a third number that is placed at the end of
the block. Any memory overwrite of any block will overwrite probably
this number first. Since the “release” function checks for this, we
will be able to detect when a block has been overwritten.

At any time, the user can ask for the size of total allocated memory
(valid blocks in circulation) by querying the AllocatedMemory variable.

The “release function” accepts NULL (that is ignored). If the pointer
passed to it is not NULL, it will check that it is a valid block, and
that the signature is still there, i.e. that no memory overwrites have
happened during the usage of the block.

 

[Ian Collins]

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.

Here is the code, and the explanations that go with it.

I would appreciate your feedback both about the code and
the associated explanations.

Are there any unit tests?

 

[Ben C]

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.

Here is the code, and the explanations that go with it.

I would appreciate your feedback both about the code and
the associated explanations.

---------------------------------------------------------------------

Instead of using directly malloc/free here are two implementations of
equivalent functions with some added safety features:
o Freeing NULL is allowed and is not an error.

free already lets you free(NULL) without an error doesn't it?

#include <stdlib.h>
#define MAGIC 0xFFFF
#define SIGNATURE 12345678L
size_t AllocatedMemory;
void *allocate(size_t size)
{
register char *r;
register int *ip = NULL;
size += 3 * sizeof(int);
r = malloc(size);
if (r == NULL)
return r;
AllocatedMemory += size;
ip = (int *) r;
// At the start of the block we write the signature
*ip++ = SIGNATURE;
// Then we write the size of the block in bytes
*ip++ = (int) size;

You might as well store the size in your "metadata" as a size_t instead
of truncating to int-- no real harm in it, and people do allocate big
blocks sometimes.

// We zero the data space
memset(ip, 0, size - 3*sizeof(int));
// We write the magic number at the end of the block,
// just behind the data
ip = (int *) (&r[size - sizeof(int)]);
*ip = MAGIC;

This will likely cause alignment problems-- suppose size were 17, and
sizeof (int) 4, malloc returns 16-byte aligned pointers, and that on the
target machine ints have to be stored at 4-byte aligned addresses.

r is 0x10 (say). &r[size - 4] will be 0x1d, which is not 4-byte aligned (0x1d %
4 is 1)

Better to make your magic number guard band something like an array of
char, so it can always go at the end of a block, whatever the size of
the block.

 

[Ian Collins]

void release(void *pp)
{
register int *ip = NULL;
int s;
register char *p = pp;
if (p == NULL) // Freeing NULL is allowed
return;
// The start of the block is two integers before the data.
p -= 2 * sizeof(int);

Maybe consider an alignment check (p divisible by sizeof(int)) and check
for p > 2*sizeof(int) before the subtraction. Paranoid, put protects
against release( 7 );

ip = (int *) p;
if (*ip == SIGNATURE) {
// Overwrite the signature so that this block
// can’t be freed again
*ip++ = 0;
s = *ip;

I'd bring s (and call it size) into the if{} scope.

ip = (int *) (&p[s - sizeof(int)]);

Another paranoid alignment check here?

 

[Barry Schwarz]

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.

Here is the code, and the explanations that go with it.

I would appreciate your feedback both about the code and
the associated explanations.

---------------------------------------------------------------------

Instead of using directly malloc/free here are two implementations of
equivalent functions with some added safety features:
o Freeing NULL is allowed and is not an error.
o Double freeing is made impossible.
o Any overwrite immediately at the end of the block is checked for.
o Memory is initialized to zero.
o A count of allocated memory is kept in a global variable.

#include <stdlib.h>
#define MAGIC 0xFFFF
#define SIGNATURE 12345678L
size_t AllocatedMemory;
void *allocate(size_t size)
{
register char *r;
register int *ip = NULL;
size += 3 * sizeof(int);
r = malloc(size);
if (r == NULL)
return r;
AllocatedMemory += size;

At this point r contains the address of a block of memory properly
aligned for any possible object.

ip = (int *) r;
// At the start of the block we write the signature
*ip++ = SIGNATURE;

If sizeof(int)*CHAR_BIT < 32, SIGNATURE will not fit.

// Then we write the size of the block in bytes
*ip++ = (int) size;
// We zero the data space
memset(ip, 0, size - 3*sizeof(int));

It is legal for the user to malloc 0 bytes. I could not find a
description of what memset does if the third argument is 0. Let's
hope it checks first.

// We write the magic number at the end of the block,
// just behind the data
ip = (int *) (&r[size - sizeof(int)]);

There is no guarantee that size provided by the user is a multiple of
sizeof(int). If it is not, then this address calculation produces an
misaligned result.

*ip = MAGIC;

And this attempt to store into the "misaligned int" invokes undefined
behavior.

// Return a pointer to the start of the data area
return (r + 2 * sizeof(int));

Here you give the user an address two int into the block of memory. If
double requires 8 byte alignment and sizeof(int) is 2, the address you
return is not suitable for storing a double. Similarly if sizeof(long
long) is 16 and sizeof(int) is 4 (probably a more likely situation
with new systems).

}

<snip>


Remove del for email

 

[Ian Collins]

At this point r contains the address of a block of memory properly
aligned for any possible object.

Is there a portable way of finding out what this alignment is?

 

[Keith Thompson]

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.

Here is the code, and the explanations that go with it.

I would appreciate your feedback both about the code and
the associated explanations.

---------------------------------------------------------------------

Instead of using directly malloc/free here are two implementations of
equivalent functions with some added safety features:
o Freeing NULL is allowed and is not an error.

That's not an added safety feature; free(NULL) is explicitly required
to do nothing.

o Double freeing is made impossible.

Well, unlikely.

o Any overwrite immediately at the end of the block is checked for.
o Memory is initialized to zero.

Arguably, that could mask certain errors. For example, if I use the
standard malloc() function, and I attempt to access the allocated
memory before I've initialized it, I've invoked undefined behavior.
By initializing the memory to zero, you make such buggy code behave
consistently, making it more difficult to track down the error.

You might consider setting the allocated memory to a known bad value,
perhaps all-ones, or 0xDEADBEEF, or 0xE5E5E5E5.

o A count of allocated memory is kept in a global variable.

#include <stdlib.h>
#define MAGIC 0xFFFF
#define SIGNATURE 12345678L
size_t AllocatedMemory;
void *allocate(size_t size)
{
register char *r;
register int *ip = NULL;

The common wisdom is that "register" is more likely to interfere with
the compiler's optimizer than to actually make the code run faster. I
don't know how true that is. Declaring something as "register"
*should* be harmless as long as you don't try to take its address, but
it's a little odd to see it in new code.

size += 3 * sizeof(int);
r = malloc(size);
if (r == NULL)
return r;
AllocatedMemory += size;
ip = (int *) r;
// At the start of the block we write the signature
*ip++ = SIGNATURE;
// Then we write the size of the block in bytes
*ip++ = (int) size;

Why do you store the size as an int? (And why the unnecessary cast?)
It seems far more natural, more correct, and potentially more useful,
to store it as a size_t.

// We zero the data space
memset(ip, 0, size - 3*sizeof(int));
// We write the magic number at the end of the block,
// just behind the data
ip = (int *) (&r[size - sizeof(int)]);
*ip = MAGIC;
// Return a pointer to the start of the data area
return (r + 2 * sizeof(int));

r is correctly aligned for any type. You assume here that
r + 2 * sizeof(int) is also correctly aligned for any type. That's
very likely to be true (and there's no portable way to check it),
but you should at least document the assumption.

}
void release(void *pp)
{
register int *ip = NULL;
int s;
register char *p = pp;
if (p == NULL) // Freeing NULL is allowed
return;
// The start of the block is two integers before the data.
p -= 2 * sizeof(int);
ip = (int *) p;
if (*ip == SIGNATURE) {
// Overwrite the signature so that this block
// can’t be freed again
*ip++ = 0;
s = *ip;
ip = (int *) (&p[s - sizeof(int)]);
if (*ip != MAGIC) {
ErorPrintf(“Overwritten block size %d”, s);

Typo: that should be "ErrorPrintf", not "ErorPrintf". Also, your
quotation marks show up in my newsreader as "\223" and "\224" (I think
those are Windows-specific character codes). Both of these lead me to
suspect that you didn't copy this from an actual compilable source
file. (No need, I think, to go into the reasons why this is a Bad
Idea.)

return;
}
*ip = 0;
AllocatedMemory -= s;
free(p);
}
else {
/* The block has been overwritten. Complain. */
ErrorPrintf(“Wrong block passed to release”);
}
}

I don't know what ErrorPrintf does, but printing error messages from a
memory allocation function seems like a bad idea. If it doesn't abort
the program, the caller won't know that the call failed; if it does,
the caller can't handle the problem (perhaps by attempting to do some
cleanup before terminating the program).

Since this is intended to be a replacement for free(), which has no
way to indicate a failure, it's difficult to come up with a good way
to indicate an error. Perhaps the best compromise would be to have
release() return a status value, 0 for success and any of several
defined error codes on failure. Or it could set errno.

[...]

 

[Chris Torek]

At this point [where r is the result of a malloc() call] r contains
the address of a block of memory properly aligned for any possible
object.

Is there a portable way of finding out what this alignment is?

No. I consider this a flaw in the C standards.

If there *were* a portable way to find this, you could write portable
"augmented malloc and free" routines along the lines of those Mr Navia
has provided (with more work to deal with alignment, of course). But
there is not, so you cannot.

If you want to go ahead and write such routines, probably the best
approach is to mark any alignment assumptions you make, and try to
write the code such that, for porting to a new system with different
alignment requirements, changing one or two "#define"s is all that
is needed.

 

[Ian Collins]

At this point [where r is the result of a malloc() call] r contains
the address of a block of memory properly aligned for any possible
object.

Is there a portable way of finding out what this alignment is?

No. I consider this a flaw in the C standards.

Thanks, I didn't think so.

If there *were* a portable way to find this, you could write portable
"augmented malloc and free" routines along the lines of those Mr Navia
has provided (with more work to deal with alignment, of course). But
there is not, so you cannot.

I've used max(sizeof(void*), sizeof(long double)) as a 'fairly safe'
value for alignment in similar situations.

If you want to go ahead and write such routines, probably the best
approach is to mark any alignment assumptions you make, and try to
write the code such that, for porting to a new system with different
alignment requirements, changing one or two "#define"s is all that
is needed.

I agree.

 

[Ian Collins]

I've used max(sizeof(void*), sizeof(long double)) as a 'fairly safe'
value for alignment in similar situations.

Oops, looking back I used max(sizeof(void*), sizeof(double)). The
targets I was using didn't have long double and I don't use them anyway...

Where long double does exist, you'd have to use the lowest common
multiple of sizeof(void*) and sizeof(long double).

 

[jacob navia]

Thanks for the answers.
1) True, I do not consider alignment problems, and that could
be a problem in machines where integers are aligned at some
power of 2 boundary. A work-around would be to just
memcpy (or equivalent) and memcmp (or an equivalent loop)
instead of accessing the signature at the end of the
block as an integer.

2) This code is very old, and I have forgotten that now
free accepts NULL. It was written originally under
windows 3.0 (16 bit OS), and I have used it ever
since.

3) A problem arises when size_t is much bigger than
sizeof int. In 64 bit windows, for instance, this
code would truncate a size_t when the user attempts
to allocate more than 2GB of memory in a single block.

A problem arises then here. What should this routine do with
an allocation request of that size? It could be a legal
request, but it would also be the result of a negative
number being passed to malloc...
Microsoft proposed in the TR 24731 to coin a new type
rsize_t that would be the maximum value of a legal request
for an object, and limited to a signed int, in 32 bit systems
2GB. I think the solution would be along those lines here.

Again, thanks to all people that answered.

jacob

 

[Ian Collins]

3) A problem arises when size_t is much bigger than
sizeof int. In 64 bit windows, for instance, this
code would truncate a size_t when the user attempts
to allocate more than 2GB of memory in a single block.

A problem arises then here. What should this routine do with
an allocation request of that size? It could be a legal
request, but it would also be the result of a negative
number being passed to malloc...

I had to make the same call for the debug allocator I use. I settled
for an assert on the size being <= INT_MAX, assuming a request bigger
than that to more likely be a negative number than a real request.

 

[Keith Thompson]

Oops, looking back I used max(sizeof(void*), sizeof(double)). The
targets I was using didn't have long double and I don't use them anyway...

Where long double does exist, you'd have to use the lowest common
multiple of sizeof(void*) and sizeof(long double).

Really? long double has been standard since ANSI C89; any C compiler
that doesn't provide it is non-conforming. (It can have the same
characteristics as long, so it's just a matter of recognizing the
syntax.)

Are you sure you can trust this implementation to get the rest of the
language right?

 

[Eric Sosman]

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.
[...]

Others have commented on the alignment issues, and on
the wisdom of initializing newly-allocated memory to a
"useful" value like all zeroes. I've got a few further
suggestions:

When an allocation is released, consider filling it
with garbage. This may help catch erroneous uses of an
area after it's been freed, as in the famously incorrect
code for freeing a linked list:

for (ptr = head; ptr != NULL; ptr = ptr->next)
free(ptr);

release() leaks the memory that's passed to it, so the
package isn't suitable for debugging programs that churn
through a lot of allocations and releases and expect the
released memory to be recycled. Consider passing released
areas to free(), perhaps not immediately (so the garbage
mentioned above has time to cause damage). You might make
a FIFO list of released areas, and let it grow to a few
thousand entries before handing the oldest to free(). You
might even postpone free() until malloc() returns NULL.

Consider keeping the "metadata" -- addresses, sizes,
and so on -- separate from the allocated data. The idea is to
make the metadata less vulnerable to common off-by-one errors.
(I've used a skip-list with the block address as a key for
this purpose; that's not portable because C doesn't define
comparison between pointers to "unrelated" objects, but it
works for mainstream C implementations.) Maintaining the
metadata separately involves more overhead, but this is, after
all, a debugging package.

Consider adding a sanity-checker that visits all the
allocated areas and checks their signatures for signs of
damage. Making the checker callable by the user can help in
"wolf fence" debugging. If sufficiently desperate, sanity-
check at every transaction.

I found it helpful to keep a sequence number in the
metadata for each block, and to let the user program query
the current value. This is useful when tracking down leaks:

open files, initialize libraries, ...
epoch = getCurrentSeqno();
do something that should be memory-neutral ...
listSurvivingAllocationsSince(epoch);

.... where the final call just traverses all the allocations
that haven't been freed, reporting any whose sequence numbers
are greater than `epoch'.

 

[jacob navia]

Eric Sosman a écrit :

In the C tutorial for lcc-win32, I have a small chapter
about a debugging implementation of malloc.
[...]

Others have commented on the alignment issues, and on
the wisdom of initializing newly-allocated memory to a
"useful" value like all zeroes. I've got a few further
suggestions:

When an allocation is released, consider filling it
with garbage. This may help catch erroneous uses of an
area after it's been freed, as in the famously incorrect
code for freeing a linked list:

for (ptr = head; ptr != NULL; ptr = ptr->next)
free(ptr);

release() leaks the memory that's passed to it, so the
package isn't suitable for debugging programs that churn
through a lot of allocations and releases and expect the
released memory to be recycled. Consider passing released
areas to free(), perhaps not immediately (so the garbage
mentioned above has time to cause damage).

I do pass the pointer to the free() function. release()
does NOT leak memory. Maybe an oversight?


You might make

a FIFO list of released areas, and let it grow to a few
thousand entries before handing the oldest to free(). You
might even postpone free() until malloc() returns NULL.

Consider keeping the "metadata" -- addresses, sizes,
and so on -- separate from the allocated data. The idea is to
make the metadata less vulnerable to common off-by-one errors.
(I've used a skip-list with the block address as a key for
this purpose; that's not portable because C doesn't define
comparison between pointers to "unrelated" objects, but it
works for mainstream C implementations.) Maintaining the
metadata separately involves more overhead, but this is, after
all, a debugging package.

Consider adding a sanity-checker that visits all the
allocated areas and checks their signatures for signs of
damage. Making the checker callable by the user can help in
"wolf fence" debugging. If sufficiently desperate, sanity-
check at every transaction.

I cosnidered that, just making a table with all the allocated areas
and scanning that table in a memory check pass. Within the context
of a tutorial however, I do not know if it is that useful...

I will mention your ideas in the tutorial, and outline how
they could be implemented.

I found it helpful to keep a sequence number in the
metadata for each block, and to let the user program query
the current value. This is useful when tracking down leaks:

open files, initialize libraries, ...
epoch = getCurrentSeqno();
do something that should be memory-neutral ...
listSurvivingAllocationsSince(epoch);

... where the final call just traverses all the allocations
that haven't been freed, reporting any whose sequence numbers
are greater than `epoch'.

To detect memory leaks, I use the global variable AllocatedMemory.
You have just to change your example to:
open files, initialize libraries, ...
mem = AllocatedMemory;
do something that should be memory-neutral ...
if (AllocatedMemory != mem) {
//Memory leak detected
}
Obviously your approach is better since it would detect which
memory blocks are leaked, but a simpler approach still yields
useful information.

Thanks for your input

jacob

 

[Barry Schwarz]

Thanks for the answers.
1) True, I do not consider alignment problems, and that could
be a problem in machines where integers are aligned at some
power of 2 boundary. A work-around would be to just
memcpy (or equivalent) and memcmp (or an equivalent loop)
instead of accessing the signature at the end of the
block as an integer.

This doesn't solve the problem that your are returning an address
*only* two int beyond the allocated address.

Two possibilities come to mind:

On the very first call to your function, allocate a small
block (sizeof(long long)+sizeof(long double)). Convert the address to
unsigned long. Determine N, the number of low order zeros in the
result. Instead of using sizeof(int) as your delta, use pow(2,N).
Free the memory and get on with what the user requested.

On the very first call, compute max(sizeof(short),
sizeof(int), sizeof(size_t), sizeof(ptrdiff_t), sizeof(long long),
sizeof(long double), ...), betting on the assumption that the longest
object imposes the strictest alignment.

<snip>


Remove del for email

 

[Malcolm]

Microsoft proposed in the TR 24731 to coin a new type
rsize_t that would be the maximum value of a legal request
for an object, and limited to a signed int, in 32 bit systems
2GB. I think the solution would be along those lines here.

And so gibberish types multiply.
Why not just go back to malloc() taking an int?

 

[Eric Sosman]

[...]
On the very first call, compute max(sizeof(short),
sizeof(int), sizeof(size_t), sizeof(ptrdiff_t), sizeof(long long),
sizeof(long double), ...), betting on the assumption that the longest
object imposes the strictest alignment.

K&R (now retronymically called "K&R I") showed an easy
way to do this without a run-time computation by using the
size of a union whose elements are all the primitive types
likely to need special alignment. Paraphrasing (because
some of today's types didn't exist then):

union all_kinds {
char c;
short s;
int i;
long l;
long long ll;
intmax_t im;
float f;
double d;
long double ld;
void *vp;
void (*fp)(void);
/* others as seem needful */
};
#define ALIGNSIZE sizeof(union all_kinds)

K&R did not, of course, claim that this was perfect.
Still, it's as effective as Barry Schwartz' suggestion and
doesn't require any special first-call computation.

A refinement is possible, since the sizeof a type may
be greater than the type's required alignment:

struct aligned {
char pad;
union all_kinds u;
};
#define ALIGNSIZE offsetof(struct aligned, u)

This still isn't perfect, but may sometimes turn out to
be more economical.

 

[Eric Sosman]

Eric Sosman a écrit :

release() leaks the memory that's passed to it, [...]

I do pass the pointer to the free() function. release()
does NOT leak memory. Maybe an oversight?

Yes, indeed: mine. (I thought it was odd to omit free()
so I went back and double-checked; looks like I should have
triple- or quadruple-checked ... Sorry for the slander!)

 

[Ben Pfaff]

When an allocation is released, consider filling it with
garbage.

This is a good idea. If you know a little about the target
platform, you can even choose particularly good garbage. In
"debug" allocators I have designed, I have chosen 0xcc, because
on x86 that is a "debug trap" instruction when executed and it's
unlikely to be a valid pointer value for user programs. (I think
I originally got this idea from a book.)