path: root/main/common/malloc.c

/**************************************************************************
 *
 * Copyright (c) 2013 Alcatel-Lucent
 * 
 * Alcatel Lucent licenses this file to You under the Apache License,
 * Version 2.0 (the "License"); you may not use this file except in
 * compliance with the License.  A copy of the License is contained the
 * file LICENSE at the top level of this repository.
 * You may also obtain a copy of the License at:
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 **************************************************************************
 *
 * malloc():
 *
 * A simple memory allocator useful for embedded systems to provide 
 * some level of debug, plus the ability to increase heap space into
 * additional memory that is not contiguous with the intial statically
 * allocated array of memory.  The reason for supporting the ability to
 * allocate from 2 distinct blocks of memory is so that the monitor can
 * be built with some reasonable amount of heap space allocated to it; then
 * if the application is going to also use this malloc, it can do so
 * by simply extending the heap.  The monitor would not have to be
 * specifically built to support the large heap allocation.
 *	
 * The allocator data structures are part of the memory space used for
 * the allocation.  To test for memory overruns (using memory after the
 * end of the allocated space) or underruns (using memory prior to the
 * beginning of the allocated space), the data structure starts and ends
 * with a fixed tag that is always checked upon entry into malloc()
 * or free().
 * When the memory is freed, the next and previous block is checked to
 * determine if this newly freed block can be combined with a neighboring
 * block.  This provides some level of defragmentation.  Note, at
 * this point, that the blocks are only combined if they are found to be
 * contiguous.  This correctly implies that neighboring free blocks need
 * not be within contiguous memory space.
 * A function called GetMemory() must be provided as the underlying resource
 * of the memory used by the allocator.
 *
 * NOTE THAT THERE IS ABSOLUTELY NO CONCERN FOR SPEED IN THIS MEMORY
 * ALLOCATOR, IT IS SLOW!  Every call to malloc/free does a sanity check
 * on all allocation structures, so it is fairly good at detecting illegal
 * use of the allocated memory.
 *	
 * Original author:     Ed Sutter (ed.sutter@alcatel-lucent.com)
 *
 */
#include "config.h"
#if INCLUDE_MALLOC
#include "genlib.h"
#include "stddefs.h"
#include "cli.h"

#define FNAMESIZE			32

#define PRETAG				0xDEAD
#define POSTTAG				0xBEEF
#define MHDRSIZE			sizeof(struct mhdr)

extern	char *GetMemory(int);
extern	int GetMemoryLeft(void);
extern	int extendHeap(char *,int);
extern	void unExtendHeap(void);
extern	char *getExtHeapBase(void);


/* mhdr:
   The control structure used by the memory allocator.
*/
struct	mhdr {
	ushort	pretag;			/* Fixed value used as an overrun sanity
							 * check for the previous memory block.
							 */
	int	size;				/* Size of useable memory block.  Size is
							 * positive if block is free and negative if
							 * block is not free.
							 */
	struct mhdr *next;		/* Points to next mhdr structure (not
							 * necessarily in contiguous memory space).
							 */
	struct mhdr *prev;		/* Points to previous mhdr structure (not
							 * necessarily in contiguous memory space).
							 */
	ushort	posttag;		/* Fixed value used as an underrun sanity
							 * check for this memory block.
							 */
#ifdef MALLOC_DEBUG
	char	fname[FNAMESIZE];
	int		fline;
#endif
};

/* mcalls, fcalls & mfails:
 *	Used to keep track of malloc and free calls.  Plus keep track
 *	of the number of times malloc is called, but it returns 0.
 */
static int mcalls, rcalls, fcalls, mfails;

/* mtot, ftot & highwater:
 *	Keep track of total amount of memory allocated.
 */
static int mtot, ftot, highwater;

/* mquiet:
 * If set (by heap -q), then the MALLOC ERROR messages are not
 * printed at runtime when an error is detected.
 */
static char mquiet;

/* mtrace:
 * If set (by heap -V), then each call to malloc or free will include
 * a printed message.
 */
static char mtrace;

/* heapbase:
 *	Initially zero, this pointer is set to the base of the heap on
 *	the first call to malloc().
 */
static struct mhdr	*heapbase;

static void
heapinit(void)
{
	mcalls = rcalls = fcalls = mfails = 0;
	mtot = ftot = highwater = 0;
	heapbase = (struct mhdr *)GetMemory(ALLOCSIZE);
	heapbase->pretag = PRETAG;
	heapbase->posttag = POSTTAG;
	heapbase->size = ALLOCSIZE - MHDRSIZE;
	if (heapbase->size < 0)
		printf("heapinit(): ALLOCSIZE too small!\n");
	heapbase->next = (struct mhdr *)0;
	heapbase->prev = (struct mhdr *)0;
}

/* heapcheck():
 *	Called with an mhdr pointer (or NULL).  This function just steps through
 *	the heap control structures to make sure there is some level of sanity.
 *	If the incoming mhdr pointer is non-zero, then it will also verify that
 *	the pointer is a valid control pointer in the heap.
 */
int
heapcheck(struct mhdr *mp,char *msg)
{
	int	i, mpok;
	register struct	mhdr *mptr;

	mpok = 0;
	if (!heapbase)
		heapinit();

	mptr = heapbase;
	for(i=0;mptr;i++,mptr=mptr->next) {
		if (mp == mptr)
			mpok = 1;
		if ((mptr->pretag != PRETAG) || (mptr->posttag != POSTTAG)) {
			if (!mquiet) {
				printf("\007MALLOC ERROR: heap corrupted at entry %d",i);
				if (msg)
					printf(" (%s)",msg);
				printf("\n");
			}
			return(-1);
		}
	}
	if ((mp) && (!mpok)) {
		if (!mquiet) {
			printf("\007MALLOC ERROR: 0x%lx (mem @ 0x%lx) invalid heap pointer",
		   	 (ulong)mp,(ulong)(mp+1));
			if (msg)
				printf(" (%s)",msg);
			printf("\n");
		}
		return(-1);
	}
	return(0);
}

static char *
_malloc(int size)
{
	register struct	mhdr *mptr, *mptr1;

	if (mtrace)
		printf("malloc(%d) = ",size);

	if (size <= 0) {
		if (mtrace)
			printf("0\n");
		return(0);
	}

	/* Start by checking sanity of heap. */
	if (heapcheck(0,0) < 0) {
		if (mtrace)
			printf("00\n");
		return((char *)0);
	}

	/* Keep track of number of calls to malloc for debug. */
	mcalls++;

	/* Make size divisible by 4: */
	if (size & 3) {
		size += 4;
		size &= 0xfffffffc;
	}

	mptr = (struct mhdr *)heapbase;
	while(1) {
		/* If request size is equal to the free block size or
		 * if the free block size is only slightly larger than the
		 * request size, then just use that free block as is.
		 * If the request size is at least "MHDRSIZE * 2"
		 * bytes smaller than free block size, then break
		 * that block up into 2 smaller chunks with one of the chunks
		 * being the size of the request and the size of the other chunk
		 * being whatever is left over.
		 */
		if (mptr->size >= size) {
			if (mptr->size <= (int)(size + (MHDRSIZE * 2))) {
				mtot += mptr->size;
				if ((mtot - ftot) > highwater)
					highwater = (mtot - ftot);
				mptr->size = -mptr->size;
			}
			else {
				mptr1 = (struct mhdr *)((char *)(mptr+1) + size);
				mptr1->pretag  = PRETAG;
				mptr1->posttag = POSTTAG;
				mptr1->next = mptr->next;
				mptr->next = mptr1;
				if (mptr1->next)
					mptr1->next->prev = mptr1;
				mptr1->prev = mptr;
				mptr1->size = (mptr->size - size) - MHDRSIZE;
				mptr->size = -size;
				mtot += size;
				if ((mtot - ftot) > highwater)
					highwater = (mtot - ftot);
			}
			if (mtrace)
				printf("0x%lx\n",(long)(mptr+1));
			return((char *)(mptr+1));
		}
		if (mptr->next == (struct mhdr *)0) {
			struct mhdr *moremem;
			int		getsize;

			getsize = size + MHDRSIZE;
			moremem = (struct mhdr *)GetMemory(getsize);
			if (!moremem) {
				mfails++;
				if (!mquiet)
					printf("\007MALLOC ERROR: no more memory\n");
				if (mtrace)
					printf("000\n");
				return((char *)0);
			}
			mptr->next = moremem;
			mptr->next->prev = mptr;
			mptr = mptr->next;
			mptr->next = (struct mhdr *)0;
			mptr->pretag = PRETAG;
			mptr->posttag = POSTTAG;
			mptr->size = getsize - MHDRSIZE;
		}
		else
			mptr = mptr->next;
	}
}

#ifdef MALLOC_DEBUG
#undef malloc

char *
malloc(int size, char *fname, int fline)
{
	char *cp;
	struct	mhdr	*mptr;

	cp = _malloc(size);
	if (cp) {
		mptr = (struct mhdr *)cp;
		mptr--;
		strncpy(mptr->fname,fname,FNAMESIZE-1);
		mptr->fline = fline;
		mptr->fname[FNAMESIZE-1] = 0;
		mptr->fline = fline;
	}
	return(cp);
}

#else
char *
malloc(int size)
{
	return(_malloc(size));
}
#endif

void
free(void *vp)
{
	char	*cp	 = vp;
	struct	mhdr	*mptr;

	if (mtrace)
		printf("free(0x%lx)\n",(long)cp);

	/* Keep track of number of calls to free for debug. */
	fcalls++;

	mptr = (struct mhdr *)cp - 1;

	/* Start by checking sanity of heap and make sure that the incoming
	 * pointer corresponds to a valid entry in the heap.
	 */
	if (heapcheck(mptr,0) < 0)
		return;

	/* The first thing to do to free the block is to make the size
	 * positive.
	 */
	mptr->size = abs(mptr->size);

	/* Keep track of how much memory is freed for debug. */
	ftot += mptr->size;

	/* To defragment the memory, see if previous and/or
	 * next block is free; if yes, then join them into one larger
	 * block. Note that the blocks will only be joined if they are in
	 * contiguous memory space.
	 */
	if (mptr->next) {
		if ((mptr->next->size > 0)  &&
		    (mptr->next == (struct mhdr *)
		    ((char *)mptr + mptr->size + MHDRSIZE))) {
			mptr->size += mptr->next->size + MHDRSIZE;
			mptr->next = mptr->next->next;
			if (mptr->next)
				mptr->next->prev = mptr;
		}
	}
	if (mptr->prev) {
		if ((mptr->prev->size > 0) &&
		    (mptr->prev == (struct mhdr *)
		    ((char *)mptr-mptr->prev->size - MHDRSIZE))) {
			if (mptr->next)
				mptr->next->prev = mptr->prev;
			mptr->prev->next = mptr->next;
			mptr->prev->size += mptr->size + MHDRSIZE;
		}
	}
}

/* calloc():
 *	Allocate space for an array of nelem elements of size elsize.
 *	Initialize the space to zero.
 */
static char *
_calloc(int nelem, int elsize)
{
	register char	*cp, *end;
	char	*base;
	int		size;

	size = nelem * elsize;
	base = _malloc(size);
	if (base) {
		cp = base;
		end = base+size;
		while(cp<end)
			*cp++ = 0;
	}
	return(base);
}

#ifdef MALLOC_DEBUG
char *
calloc(int nelem, int elsize, char *fname, int fline)
{
	char *cp;
	struct	mhdr	*mptr;

	cp = _calloc(nelem, elsize);
	if (cp) {
		mptr = (struct mhdr *)cp;
		mptr--;
		strncpy(mptr->fname,fname,FNAMESIZE-1);
		mptr->fline = fline;
		mptr->fname[FNAMESIZE-1] = 0;
		mptr->fline = fline;
	}
	return(cp);
}

#else

char *
calloc(int nelem, int elsize)
{
	return(_calloc(nelem,elsize));
}
#endif


static char *
_realloc(char *cp,int newsize)
{
	char			*new;
	int				asize, delta;
	struct	mhdr	*mptr, tmphdr;

	rcalls++;

	/* If incoming pointer is NULL, then do a regular malloc. */
	if (!cp)
		return(_malloc(newsize));

	/* If newsize is zero and pointer is not null, then do a free. */
	if (!newsize) {
		free(cp);
		return((char *)0);
	}

	/* Set the mhdr pointer to the header attached to the incoming 
	 * char pointer.  We assume here that the incoming pointer is the
	 * base address of the block of memory that is being reallocated.
	 */
	mptr = (struct mhdr *)cp - 1;

	/* Start by checking sanity of heap and make sure that the incoming
	 * pointer corresponds to a valid entry in the heap.
	 */
	if (heapcheck(mptr,0) < 0)
		return((char *)0);

	/* Recall that mptr->size is negative since the block is not free, so
	 * use the absolute value of mptr->size...
	 */
	asize = abs(mptr->size);

	/* Make requested size divisible by 4:
	 */
	if (newsize & 3) {
		newsize += 4;
		newsize &= 0xfffffffc;
	}

	/* If newsize is less than or equal to current size, just return with
	 * the same pointer.  At some point, this should be improved so that
	 * the memory made made available by this reallocation is put back in
	 * the pool.
	 */
	if (newsize <= asize) 
		return(cp);

	/* Now we do the actual reallocation...
	 * If there is a fragment after this one (next != NULL) AND it is
	 * available (size > 0) AND the combined size of the next fragment
	 * along with the current fragment exceeds the request, then we can
	 * reallocate quickly.
	 * Otherwise, we have to just malloc a whole new block and copy the
	 * old buffer to the new larger space.
	 */
	if ((mptr->next) && (mptr->next->size > 0) &&
		((asize + mptr->next->size + MHDRSIZE) > newsize)) {

		/* At this point we know we have the space to reallocate without
		 * the malloc/free step.  Now we need to add the necessary space
		 * to the current fragment, and take that much away from the next
		 * fragment...
		 */
		delta = newsize - asize;
		/* next line used to be: tmphdr = *mptr->next... */
		memcpy((char *)&tmphdr,(char *)mptr->next, sizeof(struct mhdr));
		mptr->size = -newsize;
		mptr->next = (struct mhdr *)(delta + (int)(mptr->next));
		mptr->next->size = (abs(tmphdr.size) - delta);
		mptr->next->pretag  = PRETAG;
		mptr->next->posttag = POSTTAG;
		mptr->next->next = tmphdr.next;
		mptr->next->prev = tmphdr.prev;

		/* Keep track of totals and highwater:
		 */
		mtot += (newsize - asize);
		if ((mtot - ftot) > highwater)
			highwater = (mtot - ftot);
		return(cp);
	}

	/* If the next fragment is not large enough, then malloc new space,
	 * copy the existing data to that block, free the old space and return
	 * a pointer to the new block.
	 */
	new = _malloc(newsize);
	if (!new)
		return((char *)0);

	memcpy(new,cp,asize);
	free(cp);
	return(new);
}

#ifdef MALLOC_DEBUG
#undef realloc
char *
realloc(char *buf, int newsize, char *fname, int fline)
{
	char *cp;
	struct	mhdr	*mptr;

	cp = _realloc(buf, newsize);
	if (cp) {
		mptr = (struct mhdr *)cp;
		mptr--;
		strncpy(mptr->fname,fname,FNAMESIZE-1);
		mptr->fline = fline;
		mptr->fname[FNAMESIZE-1] = 0;
		mptr->fline = fline;
	}
	return(cp);
}

#else

char *
realloc(char *buf, int newsize)
{
	return(_realloc(buf,newsize));
}
#endif


void
heapdump(int verbose)
{
	register struct	mhdr *mptr;
	char	freenow;
	int		i, alloctot, freetot, size;

	heapcheck(0,0);

	mptr = heapbase;
	i=0;
	freetot = 0;
	alloctot = 0;
	if (verbose)
		printf("        addr     size free?    mptr        nxt        prv      ascii@addr\n");
	else
		printf("Heap summary:\n");
	for(i=0;mptr;i++) {
		if (mptr->size < 0) {
			freenow = 'n';
			size = -mptr->size;
			alloctot += size;
		}
		else {
			freenow = 'y';
			size = mptr->size;
			freetot += size;
		}
		if (verbose) {
			printf("%3d: 0x%08lx %5d   %c   0x%08lx 0x%08lx 0x%08lx  ",
				i,(ulong)(mptr+1),size,freenow,(ulong)mptr,
				(ulong)(mptr->next),(ulong)(mptr->prev));
			prascii((unsigned char *)(mptr+1),size > 16 ? 16 : size);
			putchar('\n');
#ifdef MALLOC_DEBUG
			if (freenow == 'n')
				printf("     %s %d\n",mptr->fname,mptr->fline);
#endif
		}
		mptr = mptr->next;
	}
	if (verbose)
		putchar('\n');
	printf("  Malloc/realloc/free calls:  %d/%d/%d\n",mcalls,rcalls,fcalls);
	printf("  Malloc/free totals: %d/%d\n",mtot,ftot);
	printf("  High-water level:   %d\n",highwater);
	printf("  Malloc failures:    %d\n",mfails);
	printf("  Bytes overhead:     %d\n",i * MHDRSIZE);
	printf("  Bytes currently allocated:   %d\n",alloctot);
	printf("  Bytes free on current heap:  %d\n",freetot);
	printf("  Bytes left in allocation pool:  %d\n",GetMemoryLeft());
}

/* releaseExtendedHeap():
 *	If memory has been allocated through the extended heap established
 *	by the heap -x{start,size} command, this function will attempt
 *	to "undo" that.  It can only be un-done if there is no currently active
 *	allocations in that range.
 *
 *	This function is accessible by the application through monlib.
 */
int
releaseExtendedHeap(int verbose)
{
	int	i;
	struct	mhdr *mptr, *extbase;

	extbase = (struct mhdr *)getExtHeapBase();
	if (!extbase) {
		if (verbose)
			printf("Heap extension not set\n");
		return(-1);
	}
	
	heapcheck(0,0);
	mptr = heapbase;
	for(i=0;mptr;i++) {
		if (mptr->next == extbase) {
			if (mptr->next->next == (struct mhdr *)0) {
				mptr->next = (struct mhdr *)0;
				unExtendHeap();
				if (verbose)
					printf("Heap extension cleared\n");
				return(0);
			}
			else if (verbose)
				printf("Extended heap space is in use.\n");
			break;
		}
		mptr = mptr->next;
	}
	if (!mptr) {		/* Heap was extended, but not used. */
		unExtendHeap();	/* Remove the extension. */
		if (verbose)
			printf("Heap extension cleared.\n");
	}
	return(0);
}


char *HeapHelp[] = {
	"Display heap statistics.",
	"-[cf:m:qtvX:x]",
#if INCLUDE_VERBOSEHELP
	"Options:",
	" -c        clear high-water level and malloc/free totals",
	" -f{ptr}   free block @ 'ptr'",
	" -m{size}  malloc 'size' bytes",
	" -q        quiet runtime (don't print MALLOC ERROR msgs)",
	" -v        verbose (more detail)",
	" -t        toggle runtime malloc/free trace",
	" -X{base,size}",
	"           extend heap by 'size' bytes starting at 'base'",
	" -x        clear heap extension",
#endif
	0
};

int
Heap(int argc,char *argv[])
{
	char *establish_extended_heap, buf[32];
	int	verbose, release_extended_heap, showheap, opt;

	showheap = 1;
	establish_extended_heap = (char *)0;
	release_extended_heap = verbose = 0;
	while((opt=getopt(argc,argv,"cf:m:qtvX:x")) != -1) {
		switch(opt) {
		case 'c':
			mcalls = fcalls = 0;
			mtot = ftot = highwater = 0;
			showheap = 0;
			break;
		case 'f':
			free((char *)strtoul(optarg,0,0));
			showheap = 0;
			break;
		case 'm':
			shell_sprintf("MALLOC","0x%lx",
				(ulong)_malloc(strtoul(optarg,0,0)));
			if (verbose)
				printf("%s\n",buf);
			showheap = 0;
			break;
		case 'q':
			showheap = 0;
			mquiet = 1;
			break;
		case 't':
			mtrace = ~mtrace;
			printf("Runtime trace: %sabled\n",
				mtrace ? "en" : "dis");
			return(CMD_SUCCESS);
		case 'v':
			verbose = 1;
			break;
		case 'X':
			establish_extended_heap = optarg;
			showheap = 0;
			break;
		case 'x':
			release_extended_heap = 1;
			showheap = 0;
			break;
		default:
			return(CMD_PARAM_ERROR);
		}
	}
	if (release_extended_heap)
		releaseExtendedHeap(verbose);

	if (establish_extended_heap) {
		int  size, rc;
		char *comma, *begin;

		comma = strchr(establish_extended_heap,',');
		if (!comma)
			return(CMD_PARAM_ERROR);
		*comma = 0;
		begin = (char *)strtoul(establish_extended_heap,0,0);
		size = (int)strtoul(comma+1,0,0);
		rc = extendHeap(begin,size);
		if (rc == -1) {
			printf("Extended heap already exists @ 0x%lx\n",
				(ulong)getExtHeapBase());
		}
		if (rc < 0)
			return(CMD_FAILURE);
	}

	if (!showheap)
		return(CMD_SUCCESS);

	if (optind == argc)
		heapdump(verbose);

	return(CMD_SUCCESS);
}
#else
char *
malloc(int size)
{
	return(0);
}

void
free(char *buf)
{
}

char *
realloc(char *buf, int newsize, char *fname, int fline)
{
	return(0);
}

#endif