allbery@ncoast.UUCP (Brandon S. Allbery) (07/21/87)
This is my malloc() debugging package. Response to my small note was rather
startling, so I'm posting it.
The basic idea is that malloc'ed and free'd blocks are kept in doubly-linked
lists. Every time an allocation function (malloc, free, calloc, realloc,
or _mallchk) is called, the lists are checked to make sure the pointers have
not been overwritten and the sizes are valid. They catch the majority of
malloc'ed array overflows, and print dumps on segmentation and bus errors
in order to determine if a memory overwrite was involved. They aren't
perfect (an interpreter or other form of full runtime checking of every
assignment would be needed for that), but they're pretty good.
One warning: you can't depend on a free()'d block still being available,
it will sbrk() backwards if possible. It also doesn't coalesce adjacent free
blocks or do other kinds of "optimum" memory management; I consider this
unimportant, since this is a debugging package rather than a full replacement
for malloc. It's also slower than the "real" malloc.
The code is included below; it's probably heavily 68000 dependent, but I've
done my best to reduce such dependencies to a miminum.
(WARNING: THIS IS NOT A "shar" FILE! Cut below and save to the file malloc.c)
===============================================================================
/*
* malloc for debugging -- allocates via sbrk and tracks stuff, does diag dump
* if things appear to be screwed up
*/
#include <signal.h>
extern char *sbrk();
extern char *memcpy();
extern char *memset();
extern char etext[];
extern char edata[];
extern char end[];
struct _Dmi {
struct _Dmi *m_next;
struct _Dmi *m_prev;
long m_size;
char m_blk[1];
};
static struct _Dmi *_fab = (struct _Dmi *) 0;
static struct _Dmi *_ffb = (struct _Dmi *) 0;
static char *_xbrk = 0;
static int _in_malloc = 0;
static int _st_malloc = 0;
int _mall_opt = 1;
/*
* initialize stuff, we want to _malldmp() on a bus/seg error
*/
static _mall_sig(sig) {
if (sig == SIGSEGV)
_malldstr("\nsegmentation violation\n\n");
else if (sig == SIGBUS)
_malldstr("\nbus error\n\n");
else if (sig == SIGSYS)
_malldstr("\ninvalid syscall arg\n\n");
else {
_malldstr("\nsignal ");
_malldptr(sig);
_malldstr("\n\n");
}
_malldmp();
kill(getpid(), sig);
}
static _mall_init() {
if (_st_malloc)
return;
signal(SIGSEGV, _mall_sig);
signal(SIGBUS, _mall_sig);
_st_malloc = 1;
}
/*
* figure out which allocation block this pointer came from
* return NULL if none
*/
static struct _Dmi *_mallgb(s)
char *s; {
register struct _Dmi *blk;
for (blk = _fab; blk != (struct _Dmi *) 0; blk = blk->m_next)
if (blk->m_blk == s)
break;
return blk;
}
/*
* internal: write a pointer in hex without using stdio
*/
static _malldptr(x)
register long x; {
char buf[20];
static char hex[] = "0123456789abcdef";
register long dx;
register char *p;
if (x == 0)
return _malldstr("0x0(0)");
_malldstr("0x");
p = buf;
dx = x;
while (x > 0)
*p++ = hex[x % 16], x = x / 16;
while (p != buf)
write(2, --p, 1);
_malldstr("(");
p = buf;
x = dx;
while (x > 0)
*p++ = hex[x % 10], x /= 10;
while (p != buf)
write(2, --p, 1);
_malldstr(")");
}
/*
* internal: dump a string
*/
static _malldstr(s)
register char *s; {
register int len;
for (len = 0; s[len] != '\0'; len++)
;
write(2, s, len);
}
/*
* dump arena; can be called externally, and is non-destructive
*/
_malldmp() {
register struct _Dmi *blk;
int oldf;
oldf = _in_malloc;
_in_malloc = 0;
_malldstr("brk = ");
_malldptr(sbrk(0));
_malldstr(" xbrk = ");
_malldptr(_xbrk);
_malldstr("\n_fab = ");
_malldptr(_fab);
_malldstr(" _ffb = ");
_malldptr(_ffb);
_malldstr(" blksiz = ");
_malldptr(sizeof (struct _Dmi));
_malldstr("\netext = ");
_malldptr(etext);
_malldstr(" edata = ");
_malldptr(edata);
_malldstr(" end = ");
_malldptr(end);
_malldstr("\n\nallocated blocks\n\n");
if (_fab == (struct _Dmi *) 0)
_malldstr("(none)\n");
else {
for (blk = _fab; blk != (struct _Dmi *) 0 && (char *) blk >= _xbrk && (char *) blk < sbrk(0); blk = blk->m_next) {
_malldstr("(");
_malldptr(blk);
_malldstr(") ");
_malldptr(blk->m_prev);
_malldstr("< ");
_malldptr(blk->m_size);
_malldstr(" >");
_malldptr(blk->m_next);
_malldstr("\n");
}
if (blk != (struct _Dmi *) 0)
_malldstr("(subsequent block pointers corrupted)\n");
}
_malldstr("\nfree blocks\n\n");
if (_ffb == (struct _Dmi *) 0)
_malldstr("(none)\n");
else {
for (blk = _ffb; blk != (struct _Dmi *) 0 && (char *) blk >= _xbrk && (char *) blk < sbrk(0); blk = blk->m_next) {
_malldstr("(");
_malldptr(blk);
_malldstr(") ");
_malldptr(blk->m_prev);
_malldstr("< ");
_malldptr(blk->m_size);
_malldstr(" >");
_malldptr(blk->m_next);
_malldstr("\n");
}
if (blk != (struct _Dmi *) 0)
_malldstr("(subsequent block pointers corrupted)\n");
}
_in_malloc = oldf;
}
/*
* internal error routine: print error message (without using stdio) and
* drop core
*/
static _mallerr(fn, s, ptr)
char *fn, *s;
long ptr; {
_malldstr(fn);
_malldstr(": ");
_malldstr(s);
_malldptr(ptr);
_malldstr("\n");
_malldmp();
signal(SIGQUIT, SIG_DFL);
kill(getpid(), SIGQUIT);
}
char *malloc(n)
register unsigned n; {
register struct _Dmi *blk;
_in_malloc = 1;
_mall_init();
if (_mall_opt)
_malldstr("called malloc("), _malldptr(n), _malldstr(")\n");
_mallchk("malloc");
if (n == 0) {
_malldstr("malloc(0) is illegal!\n");
_mall_sig(SIGSYS);
}
for (blk = _ffb; blk != (struct _Dmi *) 0; blk = blk->m_next)
if (blk->m_size >= n) {
if (blk->m_next != (struct _Dmi *) 0)
blk->m_next->m_prev = blk->m_prev;
if (blk->m_prev != (struct _Dmi *) 0)
blk->m_prev->m_next = blk->m_next;
if (blk == _ffb)
_ffb = blk->m_next;
blk->m_next = _fab;
blk->m_prev = (struct _Dmi *) 0;
if (_fab != (struct _Dmi *) 0)
_fab->m_prev = blk;
_fab = blk;
_in_malloc = 0;
return blk->m_blk;
}
if ((blk = (struct _Dmi *) sbrk(sizeof (struct _Dmi) + n - 1)) == (struct _Dmi *) -1) {
_in_malloc = 0;
return (char *) 0; /* no space */
}
if (_xbrk == (char *) 0)
_xbrk = (char *) blk;
blk->m_next = _fab;
blk->m_prev = (struct _Dmi *) 0;
if (_fab != (struct _Dmi *) 0)
_fab->m_prev = blk;
_fab = blk;
blk->m_size = n;
_in_malloc = 0;
return blk->m_blk;
}
/* The free-block list is sorted in size order */
free(s)
register char *s; {
register struct _Dmi *blk, *fblk;
int didit;
_in_malloc = 1;
_mall_init();
if (_mall_opt)
_malldstr("called free("), _malldptr(s), _malldstr(")\n");
_mallchk("free");
if (s == (char *) 0) {
_malldstr("free((char *) 0) is illegal!\n");
_mall_sig(SIGSYS);
}
if ((blk = _mallgb(s)) == (struct _Dmi *) 0)
_mallerr("non-allocated pointer passed to free(): ", s);
if (blk->m_prev != (struct _Dmi *) 0)
blk->m_prev->m_next = blk->m_next;
if (blk->m_next != (struct _Dmi *) 0)
blk->m_next->m_prev = blk->m_prev;
if (blk == _fab)
_fab = blk->m_next;
if (_ffb == (struct _Dmi *) 0) {
_ffb = blk;
blk->m_next = (struct _Dmi *) 0;
blk->m_prev = (struct _Dmi *) 0;
goto crunch;
}
for (fblk = _ffb; fblk->m_next != (struct _Dmi *) 0; fblk = fblk->m_next)
if (fblk->m_next->m_size >= blk->m_size)
break;
blk->m_next = fblk->m_next;
if (fblk->m_next != (struct _Dmi *) 0)
fblk->m_next->m_prev = blk;
blk->m_prev = fblk;
fblk->m_next = blk;
/*
* crunch the free list by dropping consecutive end-of-brk until we hit xbrk
* or a "hole" (i.e. allocated block). coalescing is possible but not supp-
* orted in malloc, so we don't bother here.
*/
crunch:
didit = 1;
while (_ffb != (struct _Dmi *) 0 && didit) {
didit = 0;
for (fblk = _ffb; fblk != (struct _Dmi *) 0; fblk = fblk->m_next)
if ((char *) fblk + sizeof *fblk + fblk->m_size - 1 == sbrk(0)) {
didit = 1;
if (fblk->m_next != (struct _Dmi *) 0)
fblk->m_next->m_prev = fblk->m_prev;
if (fblk->m_prev != (struct _Dmi *) 0)
fblk->m_prev->m_next = fblk->m_next;
if (fblk == _ffb)
_ffb = fblk->m_next;
sbrk(- fblk->m_size);
break;
}
}
_in_malloc = 0;
}
char *realloc(s, n)
register char *s;
register unsigned n; {
register char *s1, *d, *d1;
register struct _Dmi *blk;
if (_mall_opt)
_malldstr("called realloc("), _malldptr(s), _malldstr(", "), _malldptr(n), _malldstr(")\n");
_mallchk("realloc");
if (s == (char *) 0) {
_malldstr("realloc((char *) 0, size) is illegal!\n");
_mall_sig(SIGSYS);
}
if (n == 0) {
_malldstr("realloc(ptr, 0) is illegal!\n");
_mall_sig(SIGSYS);
}
if ((blk = _mallgb(s)) == (struct _Dmi *) 0)
_mallerr("non-allocated pointer passed to realloc(): ", s);
if ((s1 = malloc(n)) == (char *) 0)
return (char *) 0;
if (blk->m_size < n)
n = blk->m_size;
d1 = s1;
d = s;
while (n-- != 0)
*d1++ = *d++;
free(s);
return s1;
}
/*
* _mallchk() is global, so external routines can do discreet checks on the
* arena. If the arena is detectibly corrupted, it will abort().
*/
_mallchk(fn)
char *fn; {
register struct _Dmi *blk, *cblk;
register char *send;
register int cnt;
send = sbrk(0);
cblk = (struct _Dmi *) 0;
for (blk = _fab; blk != (struct _Dmi *) 0; cblk = blk, blk = blk->m_next) {
if ((char *) blk < _xbrk || (char *) blk >= send)
_mallerr(fn, "allocated block list corrupted: blkptr = ", blk);
if (blk->m_prev != cblk)
_mallerr(fn, "allocated block list corrupted: back pointer incorrect blk ", blk);
if (blk->m_size < 0)
_mallerr(fn, "allocated block list corrupted: blk->m_size = ", blk->m_size);
}
cblk = (struct _Dmi *) 0;
for (blk = _ffb; blk != (struct _Dmi *) 0; cblk = blk, blk = blk->m_next) {
if ((char *) blk < _xbrk || (char *) blk >= sbrk(0))
_mallerr(fn, "free block list corrupted: blkptr = ", blk);
if (blk->m_prev != cblk)
_mallerr(fn, "free block list corrupted: back pointer incorrect blk ", blk);
if (blk->m_size < 0)
_mallerr(fn, "free block list corrupted: blk->m_size = ", blk->m_size);
}
for (blk = _fab; blk != (struct _Dmi *) 0; blk = blk->m_next) {
if ((char *) blk + sizeof *blk + blk->m_size - 1 > send) {
_malldstr("(brk = ");
_malldptr(send);
_malldstr(", eblk = ");
_malldptr((char *) blk + sizeof *blk + blk->m_size - 1);
_malldstr(")\n");
_mallerr(fn, "allocated block extends past brk: ", blk);
}
cnt = 0;
for (cblk = _fab; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
if (blk == cblk)
if (cnt++ == 0)
continue;
else
_mallerr(fn, "block allocated twice: ", blk);
if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
_malldstr("(blk = ");
_malldptr(blk);
_malldstr(", cblk = ");
_malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
_malldstr(")\n");
_mallerr(fn, "nested block in allocated list: ", blk);
}
}
for (cblk = _ffb; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
if (blk == cblk)
_mallerr(fn, "block on allocated and free lists: ", blk);
if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
_malldstr("(blk = ");
_malldptr(blk);
_malldstr(", cblk = ");
_malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
_malldstr(")\n");
_mallerr(fn, "allocated block nested in free block: ", blk);
}
}
}
for (blk = _ffb; blk != (struct _Dmi *) 0; blk = blk->m_next) {
if ((char *) blk + sizeof *blk + blk->m_size - 1 > send) {
_malldstr("(brk = ");
_malldptr(send);
_malldstr(", eblk = ");
_malldptr((char *) blk + sizeof *blk + blk->m_size - 1);
_malldstr(")\n");
_mallerr(fn, "free block extends past brk: ", blk);
}
cnt = 0;
for (cblk = _ffb; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
if (blk == cblk)
if (cnt++ == 0)
continue;
else
_mallerr(fn, "block freed twice: ", blk);
if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
_malldstr("(blk = ");
_malldptr(blk);
_malldstr(", cblk = ");
_malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
_malldstr(")\n");
_mallerr(fn, "nested block in free list: ", blk);
}
}
for (cblk = _fab; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
if (blk == cblk)
_mallerr(fn, "block on allocated and free lists: ", blk);
if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
_malldstr("(blk = ");
_malldptr(blk);
_malldstr(", cblk = ");
_malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
_malldstr(")\n");
_mallerr(fn, "free block nested in allocated block: ", blk);
}
}
}
}
/*
* malloc objects and zero storage
*/
char *calloc(n, size)
register unsigned n, size; {
register char *s, *s1;
if (_mall_opt)
_malldstr("called calloc("), _malldptr(n), _malldstr(", "), _malldptr(size), _malldstr(")\n");
n *= size;
if ((s = malloc(n)) == (char *) 0)
return (char *) 0;
for (s1 = s; n != 0; n--)
*s1++ = 0;
return s;
}
/*
* for some reason this is in /lib/libc.a(calloc.o)
*/
cfree(s)
char *s; {
free(s);
}
--
[Copyright 1987 Brandon S. Allbery, all rights reserved]
[Redistribution permitted only if redistribution is subsequently permitted.]
Brandon S. Allbery, moderator of comp.sources.misc and comp.binaries.ibm.pc
{{harvard,mit-eddie}!necntc,well!hoptoad,sun!cwruecmp!hal,cbosgd}!ncoast!allbery
<<ncoast Public Access UNIX: +1 216 781 6201 24hrs. 300/1200/2400 baud>>