qArticle 312 of comp.sys.acorn:
Xref: rusmv1 comp.sys.acorn:312 eunet.micro.acorn:133
Path: rusmv1!ira.uka.de!fauern!unido!mcsun!ukc!acorn!john
From: john@acorn.co.uk (John Bowler)
Newsgroups: comp.sys.acorn,eunet.micro.acorn
Subject: Re: Any got a malloc function with debugging facilities?
Summary: No, but this may help
Keywords: malloc
Message-ID: <4938@acorn.co.uk>
Date: 1 Feb 91 20:14:56 GMT
References: <3430@gos.ukc.ac.uk>
Organization: Acorn Computers Ltd, Cambridge, UK
Lines: 130

In article <3430@gos.ukc.ac.uk> nms@ukc.ac.uk (N.M.Smith) writes:
>Has anyone got a malloc functions that has debugging features?  The problem
>I have is that there is a large piece of C code that does _a lot_ of mallocing
>of complex structures.  The memory usage is so high that it doesn't run a 440.
>I know that a least some of the structures are freed after use but I need to 
>know if there is any other memory that the structure pointed to that is not
>freed.

Debugging malloc's probably won't help very much unless RISC OS specific.
You need to know what store is in use *and* who allocated it (although
brave users of debuggers have been seen attempting to deduce who allocated
heap space by exmaining the contents :-)).  Finding out what store is
in use and who allocated it is frequently useful anyway, even if the
programs storage use isn't apparently excessive.  The RISC OS malloc
makes it impossible to even find out what store is in use - you can work
out which regions of memory are in use, but not (necessarily) where individual
allocations within those regions start or end.

The approach I have used in the past (on RISC iX, but the problems are
similar) involves code along the following lines (it is obviously RISCOS
specific...)  No guarantees this code is correct, I write it each time
I need it.

#include <stdlib.h>

#define RND(x) (((x)+sizeof (int)-1)/sizeof (int))
#define CHECK1 0x12345678	/* Or anything you like */
#define CHECK2 0x9abcdef0	/* Or anything you like */

static int *list;

void *MALLOC(size_t size) {
	int *ptr = malloc(size+20);

	if (ptr == NULL) return ptr;
	ptr[0] = CHECK1;
	ptr[1] = caller_pc();	/* Identifies caller of MALLOC */
	ptr[2] = size;
	ptr[3] = (int)list;	/* SIC */
	list = ptr;
	ptr[1+RND(size)] = CHECK2;
	return ptr+4;
}

/* Make the following as complicated as you like */
static void check(int *pi) {
	if (pi[0] != CHECK1 || pi[1+RND(pi[2])] != CHECK2)
		/* Store overwritten */;
}

static int *remove(int *pi) {
	int **lp = &list;
	while (*lp) {
		/* Checks every allocated item on each free() */
		check(*lp);
		if (*lp == pi) {
			*lp = (int *)pi[3];
			/* pi now removed from list */
			return pi;
		}
		/* Point to next list pointer */
		lp = (int **)&((*lp)[3]);
	}
	/* *lp == NULL, pi not in list */
	/* ERROR - invalid pointer to free */
	return NULL;
}
	
void FREE(void *ptr) {
	int *p = remove(ptr);

	if (p) free(p-4);
}

The implementation of REALLOC should be fairly obvious.   This
code is proof against bogus pointers being passed to free()
(in particular, it is proof against multiple freeing).  Also each
storage unit contains the result of the caller_pc() function;
if this function returns the pc of the caller of malloc (and similarly
for realloc) it is possible to use these and the list static variable
to find the pc of each call to malloc which is not matched by a
free.

To ensure the code gets called you need to convert every malloc
call to a MALLOC call, and so on.  Do this using #define's in the
code or command line options:-

	-Dmalloc=MALLOC -Dfree=FREE -Drealloc=REALLOC

The only problem is that this does *not* get the malloc calls in
RISCOS_Lib - I can see no easy way of catching these, as RISCOS_Lib
has already been compiled.  (You can do it in RISC iX 1.2 by renaming
the symbols and using a non-shared libc library.)

To write caller_pc you need to resort to objasm and the APCS 
documentation.  The simplest implementation is:-

|_caller_pc|	LDR	A1, [FP, #-4]
		MOVS	PC, LR

Then the result is the address of the instruction immediately
after the (original) call to MALLOC (etc).  Actually the following
bit of C will do the same (possibly only at the revision and release
of the compiler which I have on RISC iX).

static int dummy(void) { return 22; }

void *caller_pc(void) {
	int	a = dummy();
	int	*fp = (int *)((&a)[1]);	/* Revolting */
	return (void *)fp[-1];
}

Sometimes on RISC OS you will get an address in MALLOC itself,
because of stack overflow, caller_pc() could be made to work round this,
but it hardly seems worth it.

The only problem with this approach is that the addition of 20 bytes
to each allocation distorts heap use enormously, however this should
not cause problems when trying to track down failures to free things.
There are a lot of potential approaches to detecting free failures.
One is to simply find out which malloc caller allocated the greatest
number of outstanding storage units.  Another is to note a position
in the list using a debugging function (make a call to MALLOC and
read the value of the ``list'' static) then, some time later, examine
the list down to this point in another function - that will avoid
the large numbers of (effectively) static allocations which occur
during program startup.

John Bowler (jbowler@acorn.co.uk)