vxmalloc.c

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

/*
 * Allocate more memory to the indicated bucket.
 */
static void
morecore(bucket)
        int bucket;
{
        register union overhead *op;
        register int sz;		/* size	of desired block */
        int amt;			/* amount to allocate */
        int nblks;			/* how many blocks we get */

        /*
	 * sbrk_size <=	0 only for big, FLUFFY, requests (about
	 * 2^30	bytes on a VAX, I think) or for a negative arg.
	 */
        sz = 1 << (bucket + 3);
        if (sz <= 0)
		return;
        if (sz < pagesz) {
		amt = pagesz;
		nblks =	amt / sz;
        } else {
		amt = sz + pagesz;
		nblks =	1;
        }
        op = (union overhead *)sbrk(amt);
        /* no more room! */
        if ((int)op == -1)
		return;
        /*
	 * Add new memory allocated to that on
	 * free	list for this hash bucket.
	 */
        nextf[bucket] = op;
        while (--nblks > 0) {
		op->ov_next = (union overhead *)((caddr_t)op + sz);
		op = (union overhead *)((caddr_t)op + sz);
        }
}

void
bsd_free(void *cp)
{   
        register int size;
        register union overhead *op;

        assert(bsd_malloc_initialized);

        if (cp == NULL)
		return;

        semTake(bsd_mem_sid, WAIT_FOREVER);

        op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
        if (op->ov_magic != MAGIC)  {
		semGive(bsd_mem_sid);
		return;				/* sanity */
        }

        assert(op->ov_rmagic == RMAGIC);
        assert(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
        size = op->ov_index;
        assert(size < NBUCKETS);
        op->ov_next = nextf[size];      /* also clobbers ov_magic */
        nextf[size] = op;

        nmalloc[size]--;
        semGive(bsd_mem_sid);
}

/*
 * When a program attempts "storage compaction" as mentioned in the
 * old malloc man page, it realloc's an already freed block.  Usually
 * this is the last block it freed; occasionally it might be farther
 * back.  We have to search all the free lists for the block in order
 * to determine its bucket: 1st we make one pass thru the lists
 * checking only the first block in each; if that fails we search
 * ``realloc_srchlen'' blocks in each list for a match (the variable
 * is extern so the caller can modify it).  If that fails we just copy
 * however many bytes was given to realloc() and hope it's not huge.
 */
int realloc_srchlen = 4;        /* 4 should be plenty, -1 =>'s whole list */

void *
bsd_realloc(void *cp, int nbytes)
{   
        register u_int onb;
        register int i;
        union overhead *op;
        char *res;
        int was_alloced = 0;

        assert(bsd_malloc_initialized);

        semTake(bsd_mem_sid, WAIT_FOREVER);

        if (cp == NULL)	 {
		semGive(bsd_mem_sid);
		return (bsd_malloc(nbytes));
        }
        op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
        if (op->ov_magic == MAGIC) {
		was_alloced++;
		i = op->ov_index;
        } else {
		/*
		 * Already free, doing "compaction".
		 *
		 * Search for the old block of memory on the
		 * free	list.  First, check the most common
		 * case	(last element free'd), then (this failing)
		 * the last ``realloc_srchlen''	items free'd.
		 * If all lookups fail,	then assume the size of
		 * the memory block being realloc'd is the
		 * largest possible (so	that all "nbytes" of new
		 * memory are copied into).  Note that this could cause
		 * a memory fault if the old area was tiny, and	the moon
		 * is gibbous.	However, that is very unlikely.
		 */
		if ((i = findbucket(op,	1)) < 0 &&
		    (i = findbucket(op,	realloc_srchlen)) < 0)
			i = NBUCKETS;
        }
        onb = 1 << (i + 3);
        if (onb < pagesz)
		onb -= sizeof (*op) + RSLOP;
        else
		onb += pagesz -	sizeof (*op) - RSLOP;
        /* avoid the copy if same size block */
        if (was_alloced) {
		if (i) {
			i = 1 << (i + 2);
			if (i <	pagesz)
				i -= sizeof (*op) + RSLOP;
			else
				i += pagesz - sizeof (*op) - RSLOP;
	        }
		if (nbytes <= onb && nbytes > i) {
			op->ov_size = (nbytes +	RSLOP - 1) & ~(RSLOP - 1);
			*(u_short *)((caddr_t)(op + 1) + op->ov_size) =	RMAGIC;
			semGive(bsd_mem_sid);
			return(cp);
		} else
			bsd_free(cp);
        }
        if ((res = bsd_malloc(nbytes)) == NULL)	 {
		semGive(bsd_mem_sid);
		return (NULL);
        }
        if (cp != res)		/* common optimization if "compacting" */
		bcopy(cp, res, (nbytes < onb) ?	nbytes : onb);

        semGive(bsd_mem_sid);
        return (res);
}

/*
 * Search ``srchlen'' elements of each free list for a block whose
 * header starts at ``freep''.  If srchlen is -1 search the whole list.
 * Return bucket number, or -1 if not found.
 */
static int
findbucket(freep, srchlen)
        union overhead *freep;
        int srchlen;
{
        register union overhead *p;
        register int i, j;

        for (i = 0; i < NBUCKETS; i++) {
		j = 0;
		for (p = nextf[i]; p &&	j != srchlen; p = p->ov_next) {
			if (p == freep)
				return (i);
			j++;
	        }
        }
        return (-1);
}


/*
 * mstats - print out statistics about malloc
 * 
 * Prints two lines of numbers, one showing the length of the free list
 * for each size category, the second showing the number of mallocs -
 * frees for each size category.
 */


void
bsd_mstats(int mode)
{
        register int i, j;
        register union overhead *p;
        unsigned int totfree = 0, totused = 0;

        dbg_printf("\nBSD memory allocation statistics\n");
        if (mode) {
		dbg_printf("%12s size %12s free	%10s used\n"," ", " ", " ");
		for (i = 0; i <	NBUCKETS; i++) {
			for (j = 0, p =	nextf[i]; p && j < INFINITE;
			     p = p->ov_next, j++)
			        ;
			if (j == INFINITE) /* just in case something is	corrupted */
			  {
			    dbg_printf("\nToo many links in block %d(%u)!\n", i,
				 (1<< (i+3)));
			    return;
			  }
		        
			dbg_printf("%16u: %16u %16u\n",	(1<< (i + 3)), j, nmalloc[i]);
			totfree	+= j * (1 << (i + 3));
			totused	+= nmalloc[i] * (1 << (i+3));
	        }
        }
        dbg_printf("\n");
        dbg_printf("\tbytes in use: %16u\n", totused);
        dbg_printf("\tbytes free:   %16u\n", totfree);
        dbg_printf("\tpool size:    %16d\n", 
				(int)(bsd_malloc_top - bsd_malloc_bottom));
        dbg_printf("\tmargin:	    %16d\n",  
				(int)(bsd_malloc_top - bsd_malloc_brk));
        dbg_printf("\n");
        dbg_printf("\tbottom:	    0x%x\n", (int)bsd_malloc_bottom);
        dbg_printf("\ttop:	    0x%x\n", (int)bsd_malloc_top);
        dbg_printf("\tbrk:	    0x%x\n",  (int)bsd_malloc_brk);
}

#endif /* USE_BSD */
#ifdef USE_DL


/* 
  A version of malloc/free/realloc written by Doug Lea and released to the 
  public domain.  Send questions/comments/complaints/performance data
  to [e-mail]
*/


/* VERSION 2.6.2  Mon Jan  8 10:28:33 1996  Doug Lea  (dl at gee)
  
   Note: There may be an updated version of this malloc obtainable at
	   ftp://g.oswego.edu/pub/misc/malloc.c
	 Check before installing!

* Synopsis of public routines

  (Much fuller descriptions are contained in the program documentation below.)

  malloc(size_t n);
     Return a pointer to a newly allocated chunk of at least n bytes, or null
     if no space is available.
  free(Void_t* p);
     Release the chunk of memory pointed to by p, or no effect if p is null.
  realloc(Void_t* p, size_t n);
     Return a pointer to a chunk of size n that contains the same data
     as does chunk p up to the minimum of (n, p's size) bytes, or null
     if no space is available. The returned pointer may or may not be
     the same as p. If p is null, equivalent to malloc.	 Unless the
     #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a
     size argument of zero (re)allocates a minimum-sized chunk.
  memalign(size_t alignment, size_t n);
     Return a pointer to a newly allocated chunk of n bytes, aligned
     in accord with the alignment argument, which must be a power of
     two.
  valloc(size_t n);
     Equivalent to memalign(pagesize, n), where pagesize is the page
     size of the system (or as near to this as can be figured out from
     all the includes/defines below.)
  calloc(size_t unit, size_t quantity);
     Returns a pointer to quantity * unit bytes, with all locations
     set to zero.
  cfree(Void_t* p);
     Equivalent to free(p).
  malloc_trim(size_t pad);
     Release all but pad bytes of freed top-most memory back 
     to the system. Return 1 if successful, else 0.
  malloc_usable_size(Void_t* p);
     Report the number usable allocated bytes associated with allocated
     chunk p. This may or may not report more bytes than were requested,
     due to alignment and minimum size constraints.
  malloc_stats();
     Prints brief summary statistics on stderr.
  mallinfo()
     Returns (by copy) a struct containing various summary statistics.
  mallopt(int parameter_number, int parameter_value)
     Changes one of the tunable parameters described below. Returns
     1 if successful in changing the parameter, else 0.

* Vital statistics:

  Alignment:				8-byte

       8 byte alignment is currently hardwired into the design.	 This
       seems to suffice for all current machines and C compilers.

  Assumed pointer representation:       4 bytes
  Assumed size_t  representation:       4 bytes
  Minimum overhead per allocated chunk: 4 bytes

       Each malloced chunk has a hidden overhead of 4 bytes holding size
       and status information.  

  Minimum allocated size:	       16 bytes	(12 bytes usable, 4 overhead)

       When a chunk is freed, 12 additional bytes are needed; 4 for a
       trailing size field and 8 bytes for free list pointers. Thus,
       the minimum allocatable size is 16 bytes, of which 12 bytes are
       usable. Even a request for zero bytes (i.e., malloc(0)) returns 
       a pointer to something of the minimum allocatable size.  

  Maximum allocated size:      2147483640 (2^31 - 8) bytes

       It is assumed that (possibly signed) 32 bit values suffice to
       represent chunk sizes. `Possibly signed' is due to the fact
       that `size_t' may be defined on a system as either a signed or
       an unsigned type. To be conservative, values that would appear
       as negative numbers are avoided.	 The maximum size chunk is
       2^31 - 8 bytes.  Requests for negative sizes (when size_t is
       signed) or those greater than (2^31 - 8) bytes will return a
       minimum-sized chunk.

  Maximum overhead wastage per allocated chunk: normally 15 bytes

       Alignnment demands, plus the minimum allocatable size restriction
       make the normal worst-case wastage 15 bytes (i.e., up to 15
       more bytes will be allocated than were requested in malloc), with 
       two exceptions:
	 1. Because requests for zero bytes allocate non-zero space,
	    the	worst case wastage for a request of zero bytes is 24 bytes.
	 2. For	requests >= mmap_threshold that are serviced via
	    mmap(), the	worst case wastage is 8 bytes plus the remainder
	    from a system page (the minimal mmap unit);	typically 4096 bytes.


* Synopsis of compile-time options:

    People have reported using previous versions of this malloc on all
    versions of Unix, sometimes by tweaking some of the defines
    below. It has been tested most extensively on Solaris and
    Linux. People have also reported adapting this malloc for use in
    stand-alone embedded systems.

    The implementation is in straight, hand-tuned ANSI C.  Among other
    consequences, it uses a lot of macros.  Because of this, to be at
    all usable, this code should be compiled using an optimizing compiler
    (for example gcc -O2) that can simplify expressions and control
    paths.

  __STD_C		   (default: derived from C compiler defines)
     Nonzero if using ANSI-standard C compiler, a C++ compiler, or
     a C compiler sufficiently close to ANSI to get away with it.
  DEBUG			   (default: NOT defined)
     Define to enable debugging. Adds fairly extensive assertion-based 
     checking to help track down memory errors, but noticeably slows down
     execution.
  REALLOC_ZERO_BYTES_FREES (default: NOT defined) 
     Define this if you think that realloc(p, 0) should be equivalent
     to free(p). Otherwise, since malloc returns a unique pointer for
     malloc(0), so does realloc(p, 0).
  HAVE_MEMCPY		    (default: defined)
     Define if you are not otherwise using ANSI STD C, but still 
     have memcpy and memset in your C library and want to use them.
     Otherwise, simple internal versions are supplied.
  HAVE_MMAP		    (default: defined as 1)
     Define to non-zero to optionally make malloc() use mmap() to
     allocate very large blocks.  
  malloc_getpagesize	    (default: derived from system #includes)
     Either a constant or routine call returning the system page size.
  HAVE_USR_INCLUDE_MALLOC_H (default: NOT defined) 
     Optionally define if you are on a system with a /usr/include/malloc.h
     that declares struct mallinfo. It is not at all necessary to
     define this even if you do, but will ensure consistency.
  INTERNAL_LINUX_C_LIB	    (default: NOT defined)
     Defined only when compiled as part of Linux libc.
     Also note that there is some odd internal name-magling via defines
     (for example, internally, `malloc' is named `mALLOc') needed
     when compiling in this case. These look funny but don't otherwise
     affect anything.
  MORECORE		    (default: sbrk)
     The name of the routine to call to obtain more memory from the system.
  MORECORE_FAILURE	    (default: -1)
     The value returned upon failure of MORECORE.
  DEFAULT_TRIM_THRESHOLD
  DEFAULT_TOP_PAD       
  DEFAULT_MMAP_THRESHOLD
  DEFAULT_MMAP_MAX      
     Default values of tunable parameters (described in detail below)
     controlling interaction with host system routines (sbrk, mmap, etc).
     These values may also be changed dynamically via mallopt(). The
     preset defaults are those that give best performance for typical
     programs/systems.


*/

/*

History:

    V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)
      * Integrated most documentation with the code.
      * Add support for mmap, with help from 
        Wolfram Gloger ([e-mail]).
      * Use last_remainder in more cases.