vxmalloc.c

This version of malloc for VxWorks contains two different algorithms. One is the BSD based Kingsley

/*
        This version of malloc for VxWorks contains two different algorithms.
        One is the BSD based Kingsley "bucket" allocator which has some
        unique fragmentation behavior.  The other is Doug Lea's well tested
        allocator that tries to minimize fragmentation while keeping the
        speed/space requirements.

        Original version of this malloc software was obtained from:
		 Doug Lea's malloc from	ftp://g.oswego.edu/pub/misc/malloc.c
		 BSD  malloc from various BSD Unix ftp sites.

        USE_BSD and USE_DL are ifdefs used to enable either one of these.

        This file is intended to replace the VxWorks memLib.o, memPartLib.o
        and memShow.o completely out of the system.  Some of the scary
        looking hacks towards the end of this file which replaces some
        of the required VxWorks symbols can be modified to suit your needs.

        Typically, you would delete the objects memtioned above from
        your library and link this file instead, to provide memory routines.
        This seems to work fine in my environment.

        Of course, using this allocator is not compatible with memory
        partition handling in VxWorks.	 If you	must use partitioning
        you might as well rename all the standard malloc/free/calloc, etc.
        to a different name in this file and link against system memLib, etc.
        You can still allocate a partition or large chunk of memory and
        give it to either BSD or DL initializer and use special names
        to access the allocator facilities in this file, and you can
        access partition handler as well.

        The reason for this brain damage is due to the way some routines
        such as malloc/free are defined in memPartLib.o and calloc etc
        are defined in memLib.o in VxWorks.  Also some networking code
        and object ID code in VxWorks seems to reference global variables
        used in memPartLib.   In short, they don't make it easy to replace
        or augment the memory allocator.

        This port to VxWorks by Hwa Jin Bae, [e-mail], Piedmont California.

        This port is released under the same license as the original license.

*/

#define USE_DL
#define VXWORKS
#define __INCmemLibh    /* XXX to avoid including memLib.h */
#define __INCclassLibh

#define dbg_printf      printf

#if defined(USE_BSD) && defined(USE_DL)
XXXX only one of these can be used
#endif

#include "vxWorks.h"
#include "semLib.h"

#define VX_PAGE_SIZE    4096    /* XXX */

#ifdef USE_BSD
#include "sys/types.h"
#include "unistd.h"
#include "assert.h"

#define getpagesize()   VX_PAGE_SIZE    

char bsd_mem_semaphore[32];     /* XXX */
SEM_ID bsd_mem_sid = (SEM_ID)bsd_mem_semaphore;

/*
 * The overhead on a block is at least 4 bytes.	 When free, this space
 * contains a pointer to the next free block, and the bottom two bits must
 * be zero.  When in use, the first byte is set to MAGIC, and the second
 * byte is the size index.  The remaining bytes are for alignment.
 * If range checking is enabled then a second word holds the size of the
 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
 * The order of elements is critical: ov_magic must overlay the low order
 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
 */
union   overhead {
        union   overhead *ov_next;      /* when free */
        struct {
		u_char	ovu_magic;	/* magic number	*/
		u_char	ovu_index;	/* bucket # */
		u_short	ovu_rmagic;     /* range magic number */
		u_int	ovu_size;	/* actual block	size */
        } ovu;
#define ov_magic        ovu.ovu_magic
#define ov_index        ovu.ovu_index
#define ov_rmagic       ovu.ovu_rmagic
#define ov_size	        ovu.ovu_size
};

#define MAGIC		0xef		/* magic # on accounting info */
#define RMAGIC		0x5555		/* magic # on range info */
#define RSLOP		sizeof (u_short)

/*
 * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
 * smallest allocatable block is 8 bytes.  The overhead information
 * precedes the data area returned to the user.
 */
#define NBUCKETS 30

static  union overhead *nextf[NBUCKETS];
extern  char *sbrk();

static  int pagesz = 0;	        /* page size */
static  int pagebucket = 0;     /* page size bucket */

/*
 * nmalloc[i] is the difference between the number of mallocs and frees
 * for a given block size.
 */
static  u_int nmalloc[NBUCKETS];

char *bsd_malloc_bottom = 0;
char *bsd_malloc_top = 0;
char *bsd_malloc_brk = 0;
int bsd_malloc_initialized = 0;
int mem_added_to_pool = 0;

#define INFINITE  100000        /* XXX */

static void morecore();
static int findbucket();

extern void *bsd_malloc(size_t nbytes);
extern void bsd_free(void *cp);
extern void * bsd_realloc(void *cp, int nbytes);

#endif /* USE_BSD */

#ifdef USE_DL
#define malloc_getpagesize  VX_PAGE_SIZE        

char dl_mem_semaphore[32];      /* XXX */
SEM_ID dl_mem_sid = (SEM_ID)dl_mem_semaphore;

#define Void_t	    void
#define INTERNAL_SIZE_T size_t

struct mallinfo {
  int arena;    /* total space allocated from system */
  int ordblks;  /* number of non-inuse chunks */
  int smblks;   /* unused -- always zero */
  int hblks;    /* number of mmapped regions */
  int hblkhd;   /* total space in mmapped regions */
  int usmblks;  /* unused -- always zero */
  int fsmblks;  /* unused -- always zero */
  int uordblks; /* total allocated space */
  int fordblks; /* total non-inuse space */
  int keepcost; /* top-most, releasable (via malloc_trim) space */
};      


#define M_MXFAST  1    /* UNUSED in this malloc */
#define M_NLBLKS  2    /* UNUSED in this malloc */
#define M_GRAIN	  3    /* UNUSED in this malloc */
#define M_KEEP	  4    /* UNUSED in this malloc	*/

static int cumblocks=0;
static int cumbytes = 0;
/* mallopt options that actually do something */

#define M_TRIM_THRESHOLD    -1
#define M_TOP_PAD	    -2
#define M_MMAP_THRESHOLD    -3
#define M_MMAP_MAX	    -4



#define DEFAULT_TRIM_THRESHOLD (128 * 1024)
#define DEFAULT_TOP_PAD	       (0)

#define MORECORE sbrk

#define MORECORE_FAILURE -1
#define MORECORE_CLEARS 0


Void_t* mALLoc();
void    fREe(Void_t*);
Void_t* reALLoc(Void_t*, size_t);
Void_t* mEMALIGn(size_t, size_t);
Void_t* cALLoc(size_t, size_t);
int     malloc_trim(size_t);
size_t  malloc_usable_size(Void_t*);
void    malloc_stats();
int     mALLOPt(int, int);
struct mallinfo mALLINFo(void);
struct malloc_chunk
{
  INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
  INTERNAL_SIZE_T size;	     /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;   /* double links -- used only if free. */
  struct malloc_chunk* bk;
};

typedef struct malloc_chunk* mchunkptr;
void *mALLoc(size_t sz);
void fREe(void *ptr);


#include "assert.h"
#define _ASSERT_STR(z) _ASSERT_TMP(z)
#define _ASSERT_TMP(z) #z
#define ASSERT(test) ((void) \
		      ((test) ?	((void) 0) : \
		       dl_assert("Assertion failed: "#test", file "     \
				__FILE__ ", line "_ASSERT_STR(__LINE__)" ")))
#define PREV_INUSE 0x1 


char *dl_malloc_bottom = 0;
char *dl_malloc_top = 0;
char *dl_malloc_brk = 0;
int dl_malloc_initialized = 0;

#endif

#ifdef USE_BSD

#include "vxWorks.h"
#include "semLib.h"

/*
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * malloc.c (Caltech) 2/21/82
 * Chris Kingsley, kingsley@cit-20.
 *
 * This is a very fast storage allocator.  It allocates blocks of a small 
 * number of different sizes, and keeps free lists of each size.  Blocks that
 * don't exactly fit are passed up to the next larger size.  In this 
 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
 * This is designed for use in a virtual memory environment.
 */

int
bsd_malloc_init(char *cp, int sz)
{
        if (bsd_malloc_initialized) {
		dbg_printf("bsd_malloc_init: already initialized\n");
		return -1;
        }
        
        bsd_malloc_bottom = cp;
        bsd_malloc_brk = cp;		/* brk pointer currently at bottom */
        bsd_malloc_top = cp + sz;
        
        bsd_malloc_initialized ++;
        
        bzero((char *)nmalloc, sizeof(nmalloc));
        bzero((char *)nextf, sizeof(nextf));
        bzero((char *)cp, sz);  /* zero out the entire memory pool */
        
        semMInit(bsd_mem_sid, SEM_Q_PRIORITY);
        
        return 1;
}

char *
sbrk(int sz)
{
        char *cp;
        int orig_sz = sz;
        
        if (bsd_malloc_initialized == 0)
		return (char *)-1;
        
        sz = (sz + 3) & ~3;		/* align sz to 4 bytes */
        cp = bsd_malloc_brk;
        
        if (bsd_malloc_brk + sz >= bsd_malloc_top)
		return (char *)-1;
        
        if (orig_sz == 0)
		return cp;
        
        bsd_malloc_brk += sz;
        
        return cp;
}

void *
bsd_malloc(size_t nbytes)
{
        register union overhead *op;
        register int bucket, n;
        register unsigned amt;

        bucket = 0;

        assert(bsd_malloc_initialized);
        semTake(bsd_mem_sid, WAIT_FOREVER);

        if (pagesz == 0) {
		pagesz = n = getpagesize();
		op = (union overhead *)sbrk(0);
		n = n -	sizeof (*op) - ((int)op & (n - 1));
		if (n <	0)
			n += pagesz;
		if (n) {
			if (sbrk(n) == (char *)-1) {
				semGive(bsd_mem_sid);
				return (NULL);
		        }
	        }
		bucket = 0;
		amt = 8;
		while (pagesz >	amt) {
			amt <<=	1;
			bucket++;
	        }
		pagebucket = bucket;
        }

        /*
	 * Convert amount of memory requested into closest block size
	 * stored in hash buckets which	satisfies request.
	 * Account for space used per block for	accounting.
	 */
        if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
		amt = 16;	/* size	of first bucket */
		bucket = 1;
		n = -(sizeof (*op) + RSLOP);
        } else {
		amt = pagesz;
		bucket = pagebucket;
        }
        while (nbytes > amt + n) {
		amt <<=	1;
		if (amt	== 0)  {
			semGive(bsd_mem_sid);
			return (NULL);
	        }
		bucket++;
        }

        if (!(bucket >= 0 && bucket < NBUCKETS)) {
		dbg_printf("bsd	malloc: bucket %d nbytes %d\n", bucket, nbytes);
		panic("bsd malloc");
        }

        /*
	 * If nothing in hash bucket right now,
	 * request more	memory from the system.
	 */
        if ((op = nextf[bucket]) == NULL) {
		morecore(bucket);
		if ((op	= nextf[bucket]) == NULL) {
			semGive(bsd_mem_sid);
			return (NULL);
	        }
        }

        /* remove from linked list */
        nextf[bucket] = op->ov_next;
        op->ov_magic = MAGIC;
        op->ov_index = bucket;
        nmalloc[bucket]++;

        /*
	 * Record allocated size of block and
	 * bound space with magic numbers.
	 */
        op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
        op->ov_rmagic = RMAGIC;
        *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;

        semGive(bsd_mem_sid);
        return ((char *)(op + 1));
}