+++ /dev/null
-/* $XConsortium: t1malloc.c,v 1.5 93/09/10 10:48:21 rws Exp $ */
-/* Copyright International Business Machines, Corp. 1991
- * All Rights Reserved
- * Copyright Lexmark International, Inc. 1991
- * All Rights Reserved
- *
- * License to use, copy, modify, and distribute this software and its
- * documentation for any purpose and without fee is hereby granted,
- * provided that the above copyright notice appear in all copies and that
- * both that copyright notice and this permission notice appear in
- * supporting documentation, and that the name of IBM or Lexmark not be
- * used in advertising or publicity pertaining to distribution of the
- * software without specific, written prior permission.
- *
- * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
- * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
- * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
- * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE
- * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
- * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE
- * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
- * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL
- * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
- * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
- * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
- * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
- * THIS SOFTWARE.
- */
- /* MALLOC CWEB V0004 LOTS */
-/*
-:h1.MALLOC - Fast Memory Allocation
-
-This module is meant to provide portable C-style memory allocation
-routines (malloc/free).
-
-&author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
-
-*/
-
-#include "objects.h" /* get #define for abort() */
-
-static combine();
-static freeuncombinable();
-static unhook();
-static dumpchain();
-/*
-:h3.Define NULL
-
-In the beginning, C compilers made no assumptions about NULL. It was
-even theoretically possible that NULL would not be 0. ANSI has tied
-this down a bit. The following definition seems to be the most
-popular (in terms of reducing compiler complaints), however, if your
-compiler is unhappy about it, you can redefine it on the command line:
-*/
-#ifndef NULL
-#define NULL 0
-#endif
-/*
-Of course, NULL is important because xiMalloc() is defined to return
-NULL when out of memory.
-
-:h2.Data Structures Used to Manage Free Memory
-
-:h3.The "freeblock" Structure
-
-The list of available memory blocks is a doubly-linked list. Each
-block begins with the following structure:
-*/
-
-struct freeblock {
- long size; /* number of 'longs' in block,
- including this header */
- struct freeblock *fore; /* forward in doubly-linked list */
- struct freeblock *back; /* backward in doubly-linked list */
-} ;
-/*
-In addition, each free block has a TRAILER that is simply the 'size'
-repeated. Thus 'size' is found at the beginning of the block and at the
-end of the block (size-1 longs away). 'size' includes both the header
-and the trailer.
-
-When a block is allocated, its 'size' is turned negative (both at the
-beginning and at the end). Thus, checking whether two blocks may be
-combined is very simple. We merely examine both neighboring blocks'
-size to see if they are positive (and hence available for combination).
-
-The memory address returned to the user is therefore one "long" below the
-size, and one extra "long" is added to the end of the block (beyond what
-the user requested) to store the trailing size.
-
-:h3."firstfree" and "lastfree", the Anchors to the Free List
-
-"firstfree" points to the first available free block; "lastfree" points
-to the end of the chain of available blocks. These are linked together
-by initialization code; see :hdref refid=addmem..
-*/
-
-static struct freeblock firstfree = { 0L, NULL, NULL };
-static struct freeblock lastfree = { 0L, NULL, NULL };
-
-/*
-:h3."firstcombined" and "uncombined", Keeping Track of Uncombined Blocks
-
-This module is designed to make the combining of adjacent free memory
-blocks be very fast. Nonetheless, combining blocks is naturally the
-most expensive part of any memory system. In an X system,
-it is worthwhile to defer the combination for a while, because
-frequently we will end up asking for a block of exactly the same
-size that we recently returned and we can save ourselves some work.
-
-"MAXUNCOMBINED" is the maximum number of uncombined blocks that we will
-allow at any time:
-*/
-
-#define MAXUNCOMBINED 3
-
-/*
-"firstcombined" is a pointer into the free list. The uncombined blocks
-are always at the front of the list. "firstcombined" points to the
-first block that has been combined.
-*/
-static struct freeblock *firstcombined = &lastfree;
-static short uncombined = 0; /* current number of uncombined blocks */
-
-/*
-Uncombined blocks have a negative 'size'; in this they are like
-allocated blocks.
-
-We store a distinctive hex pattern in 'size' when we combine a block
-to help us debug:
-*/
-#define COMBINED 0xBADBAD
-
-/*
-:h3.DEBUGWORDS - Extra Memory Saved With Each Block for Debug
-
-We add 'DEBUGWORDS' words to each allocated block to put interesting
-debug information:
-*/
-#ifndef DEBUGWORDS
-#define DEBUGWORDS 0
-#endif
-
-/*
-:h3.MINEXCESS - Amount of "Excess" We Would be Willing to Ignore
-
-When we search the free list to find memory for a user request, we
-frequently find an area that is bigger than what the user has asked for.
-Normally we put the remaining words (the excess) back on the free list.
-However, if the area is just slightly bigger than what the user needs,
-it is counter-productive to do this, as the small amount recovered tends
-to hurt by increasing memory fragmentation rather than help by providing
-more available memory. "MINEXCESS" is the number of words that must be
-recovered before we would bother to put the excess back on the free
-list. If there is not enough excess, we just give the user more than he
-asked for.
-*/
-
-#define MINEXCESS (7 + DEBUGWORDS)
-
-/*
-:h3.Some Flags for Debug
-*/
-
-long AvailableWords = 0; /* number of words available in memory */
-char mallocdebug = 0; /* a flag that enables some chatty printf's */
-
-/*
-:h3.whocalledme() - Debug for Memory Leaks
-
-This routine is 68000-specific; it copies the value of the application's
-curOper variable (which is often a pointer to a character string), and
-the first part of the stack at the time malloc was called into the
-DEBUGWORDS area reserved with each block.
-We use it to see who is malloc-ing memory without free-ing it.
-*/
-
-#if DEBUGWORDS
-
-static whocalledme(addr, stack)
- long *addr; /* address of memory block */
- long *stack; /* address of malloc's parameter on stack */
-{
- register long size; /* size of memory block */
- register int i; /* loop index */
- extern char *curOper; /* ptr to last operator (kept by appl.) */
-
- stack--;
- size = - *addr;
-
- addr += size - 1 - DEBUGWORDS;
- *addr++ = (long) curOper;
- for (i=0; i < DEBUGWORDS-1; i++)
- *addr++ = *stack++;
-}
-#else
-
-#define whocalledme(addr, stack)
-
-#endif
-/*
-:h2.xiFree() - User-Callable "Return Memory" Routine
-
-The actual beginning of the block is one 'long' before the address we
-gave to the user. The block begins and ends with '-size' in words.
-*/
-
-void xiFree(addr)
- register long *addr; /* user's memory to be returned */
-{
- register long size; /* amount of memory in this block */
- register struct freeblock *p; /* identical to 'addr' */
-
- if (addr == NULL) { /* common "mistake", so allow it (CHT) */
- printf("\nxiFree(NULL)?\n");
- return;
- }
-
- size = *--addr;
-/*
-Make sure this address looks OK; 'size' must be less than zero (meaning
-the block is allocated) and should be repeated at the end of the block.
-*/
- if (size >= 0)
- abort("free: bad size");
- if (addr[-1 - size] != size)
- abort("free: mismatched size");
-/*
-Now make this a 'freeblock' structure and tack it on the FRONT of the
-free list (where uncombined blocks go):
-*/
- AvailableWords -= size; /* actually INCREASES AvailableWords */
- p = (struct freeblock *) addr;
- p->back = &firstfree;
- (p->fore = firstfree.fore)->back = p;
- firstfree.fore = p;
-/*
-If we have too many uncombined blocks, call combine() to combine one.
-*/
- if (++uncombined > MAXUNCOMBINED) {
- combine();
- if (mallocdebug) {
- printf("xiFree(%08x) with combine, ", addr);
- dumpchain();
- }
- }
- else {
- if (mallocdebug) {
- printf("xiFree(%08x), ", addr);
- dumpchain();
- }
- }
-
- return;
-}
-
-/*
-:h3.combine() - Subroutine of xiFree() to Combine Blocks
-
-This routine tries to combine the block just before 'firstcombined'.
-In any event, that block will be moved to the end of the list (after
-'firstcombined').
-*/
-
-static combine()
-{
- register struct freeblock *p; /* block we will try to combine */
- register long *addr; /* identical to 'p' for 'long' access */
- register long size; /* size of this block */
- register long size2; /* size of potential combinee */
-
- p = firstcombined->back;
- if (p == &firstfree)
- abort("why are we combining?");
-
- addr = (long *) p;
- size = - p->size;
- if (--uncombined < 0)
- abort("too many combine()s");
-
- if (addr[-1] < 0 && addr[size] < 0) {
-/*
-We special case the situation where no combining can be done. Then, we
-just mark the chain "combined" (i.e., positive size), move the
-'firstcombined' pointer back in the chain, and return.
-*/
- addr[0] = addr[size - 1] = size;
- firstcombined = (struct freeblock *) addr;
- return;
- }
-/*
-Otherwise, we unhook this pointer from the chain:
-*/
- unhook(p);
-/*
-First we attempt to combine this with the block immediately above:
-*/
- size2 = addr[-1];
- if (size2 > 0) { /* i.e., block above is free */
- *addr = COMBINED; /* might help debug */
- addr -= size2;
- if (addr[0] != size2)
- abort("bad block above");
- unhook(addr);
- size += size2;
- }
-/*
-At this point 'addr' and 'size' may be the original block, or it may be
-the newly combined block. Now we attempt to combine it with the block
-below:
-*/
- p = (struct freeblock *) (addr + size);
- size2 = p->size;
-
- if (size2 > 0) { /* i.e., block below is free */
- p->size = COMBINED;
- if (size2 != ((long *) p)[size2 - 1])
- abort("bad block below");
- unhook(p);
- size += size2;
- }
-/*
-Finally we take the newly combined block and put it on the end of the
-chain by calling the "freeuncombinable" subroutine:
-*/
- freeuncombinable(addr, size);
-}
-
-/*
-:h3.freeuncombinable() - Free a Block That Need Not be Combined
-
-This block is "uncombinable" either because we have already combined
-it with its eligible neighbors, or perhaps because we know it has
-no neighbors.
-*/
-
-static freeuncombinable(addr, size)
- register long *addr; /* address of the block to be freed */
- register long size; /* size of block in words */
-{
- register struct freeblock *p; /* a convenient synonym for 'addr' */
-
-/*
-Mark block allocated and combined by setting its 'size' positive:
-*/
- addr[size - 1] = addr[0] = size;
-/*
-Now tack the block on the end of the doubly-linked free list:
-*/
- p = (struct freeblock *) addr;
- p->fore = &lastfree;
- (p->back = lastfree.back)->fore = p;
- lastfree.back = p;
-/*
-If we have previously had no combined blocks, we must update
-'firstcombined' to point to this block:
-*/
- if (firstcombined->fore == NULL)
- firstcombined = p;
-}
-
-/*
-:h3.unhook() - Unhook a Block from the Doubly-linked List
-
-The only tricky thing here is to make sure that 'firstcombined' is
-updated if this block happened to be the old 'firstcombined'. (We
-would never be unhooking 'firstfree' or 'lastfree', so we do not
-have to worry about the end cases.)
-*/
-
-static unhook(p)
- register struct freeblock *p; /* block to unhook */
-{
- p->back->fore = p->fore;
- p->fore->back = p->back;
-
- if (firstcombined == p)
- firstcombined = p->fore;
-}
-/*
-:h2.xiMalloc() - Main User Entry Point for Getting Memory
-
-We have two slightly different versions of xiMalloc(). In the case
-where we have TYPE1IMAGER and a font cache, we are prepared, when nominally
-out of memory, to loop calling TYPE1IMAGER's GimeSpace() to release font
-cache.
-*/
-
-/* The following code put in by MDC on 11/10/90 */
-
-#ifdef TYPE1IMAGER
-
-static char *malloc_local();
-
-char *xiMalloc(size)
- register unsigned size;
-{
- char *memaddr;
-
- while ( (memaddr = malloc_local(size)) == NULL ) {
- /* Ask TYPE1IMAGER to give us some of its cache back */
- if ( I_GimeSpace() == 0 ) break; /* We are really, really, out of memory */
- }
-
- return(memaddr);
-}
-#endif
-
-/*
-Now begins the real workhorse xiMalloc() (called 'malloc_local' if
-we are taking advantage of TYPE1IMAGER). Its argument is an unsigned;
-at least that lets users with 16-bit integers get a 64K chunk of
-memory, and it is also compatible with the definition of a "size_t"
-in most systems.
-*/
-#ifdef TYPE1IMAGER
-static char *malloc_local(Size)
-#else
-char *xiMalloc(Size)
-#endif
- unsigned Size; /* number of bytes the user requested */
-{
- register long size = (long)Size; /* a working register for size */
- register struct freeblock *p; /* tentative block to be returned */
- register long excess; /* words in excess of user request */
- register long *area; /* a convenient synonym for 'p' */
-
-/*
-First, we increase 'size' to allow for the two size fields we will
-save with the block, plus any information for debug purposes.
-Then we ensure that the block will be large enough to hold our
-'freeblock' information. Finally we convert it to be in words
-(longs), not bytes, increased to span an integral number of double
-words, so that all memory blocks dispensed with be properly aligned.
-*/
- size += 2*sizeof(long) + DEBUGWORDS*sizeof(long);
- if (size < sizeof(struct freeblock) + sizeof(long))
- size = sizeof(struct freeblock) + sizeof(long);
- size = ((unsigned) (size + sizeof(double) - 1) / sizeof(double)) * (sizeof(double)/sizeof(long));
-
-/*
-For speed, we will try first to give the user back a very recently
-returned block--one that is on the front of the chain before
-'firstcombined'. These blocks still have negative sizes, and need
-only to be "unhook"ed:
-*/
- size = -size;
- for (p=firstfree.fore; p != firstcombined; p=p->fore) {
- if (p->size == size) {
- unhook(p);
- uncombined--;
- if (mallocdebug) {
- printf("fast xiMalloc(%d) = %08x, ", size, p);
- dumpchain();
- }
- AvailableWords += size; /* decreases AvailableWords */
- whocalledme(p, &Size);
- return((char *)&p->fore);
- }
- }
-/*
-Well, if we get here, there are no uncombined blocks matching the user's
-request. So, we search the rest of the chain for a block that is big
-enough. ('size' becomes positive again):
-*/
- size = -size;
- for (;; p = p->fore) {
-/*
-If we hit the end of the chain (p->size == 0), we are probably out of
-memory. However, we should first try to combine any memory that has
-not yet been combined before we give that pessimistic answer. If
-we succeed in combining, we can call ourselves recursively to try to
-allocate the requested amount:
-*/
- if (p->size == 0) {
- if (uncombined <= 0)
- return(NULL);
- while (firstfree.fore != firstcombined)
- combine();
- return(xiMalloc(sizeof(long) * (size - 2 - DEBUGWORDS)));
- }
-/*
-Otherwise, we keep searching until we find a big enough block:
-*/
- if (p->size >= size)
- break;
- }
-/*
-At this point, 'p' contains a block at least as big as what the user
-requested, so we take it off the free chain. If it is excessively big,
-we return the excess to the free chain:
-*/
- unhook(p);
- excess = p->size - size;
- area = (long *) p;
-
- if (excess > MINEXCESS)
- freeuncombinable(area + size, excess);
- else
- size = p->size;
-
- AvailableWords -= size;
-/*
-Mark first and last word of block with the negative of the size, to
-flag that this block is allocated:
-*/
- area[size - 1] = area[0] = - size;
-
- if (mallocdebug) {
- printf("slow xiMalloc(%d) @ %08x, ", size, area);
- dumpchain();
- }
- whocalledme(area, &Size);
-/*
-The address we return to the user is one 'long' BELOW the address of
-the block. This protects our 'size' field, so we can tell the size
-of the block when he returns it to us with xiFree(). Also, he better not
-touch the 'size' field at the end of the block either. (That would be
-nasty of him, as he would be touching memory outside of the bytes he
-requested).
-*/
- return((char *) (area + 1));
-}
-
-/*
-:h2 id=addmem.addmemory() - Initialize Free Memory
-
-This routine should be called at initialization to initialize the
-free chain. There is no standard way to do this in C.
-We want the memory dispensed by malloc to be aligned on a double word
-boundary (because some machines either require alignment, or are
-more efficient if accesses are aligned). Since the total size of
-any block created by malloc is an integral number of double words,
-all we have to do to ensure alignment is to adjust each large block
-added to the free chain to start on an odd long-word boundary.
-(Malloc's size field will occupy the odd long and the user's memory
-will then begin on an even boundary.) Since we fill in additional
-size fields at the beginning and end of each of the large freeblocks,
-we need only adjust the address passed to addmemory to a double word
-boundary.
-*/
-
-#define MAXAREAS 10 /* there can be this many calls to addmemory() */
-
-static long *freearea[MAXAREAS] = { NULL }; /* so we can report later */
-
-void addmemory(addr, size)
- register long *addr; /* beginning of free area */
- register long size; /* number of bytes of free area */
-{
- register int i; /* loop index variable */
- register long *aaddr; /* aligned beginning of free area */
-
-#if DEBUGWORDS
- printf("malloc has DEBUGWORDS=%d\n", DEBUGWORDS);
-#endif
-/*
-First link together firstfree and lastfree if necessary:
-*/
- if (firstfree.fore == NULL) {
- firstfree.fore = &lastfree;
- lastfree.back = &firstfree;
- }
-/*
-We'll record where the area was that was given to us for later reports:
-*/
- for (i=0; i < MAXAREAS; i++)
- if (freearea[i] == NULL) break;
- if (i >= MAXAREAS)
- abort("too many addmemory()s");
- aaddr = (long *) ( ((long) addr + sizeof(double) - 1) & - (long)sizeof(double) );
- size -= (char *) aaddr - (char *) addr;
- freearea[i] = aaddr;
-/*
-Convert 'size' to number of longs, and store '-size' guards at the
-beginning and end of this area so we will not accidentally recombine the
-first or last block:
-*/
- size /= sizeof(long);
-
- AvailableWords += size - 2;
-
- aaddr[size - 1] = aaddr[0] = -size;
-/*
-Finally, call 'freeuncombinable' to put the remaining memory on the
-free list:
-*/
- freeuncombinable(aaddr + 1, size - 2);
-}
-
-/*
-:h3.delmemory() - Delete Memory Pool
-*/
-void delmemory()
-{
- register int i;
-
- AvailableWords = 0;
- firstfree.fore = &lastfree;
- lastfree.back = &firstfree;
- firstcombined = &lastfree;
- uncombined = 0;
- for (i=0; i<MAXAREAS; i++)
- freearea[i] = NULL;
-}
-
-/*
-:h2.Debug Routines
-
-:h3.dumpchain() - Print the Chain of Free Blocks
-*/
-
-static dumpchain()
-{
- register struct freeblock *p; /* current free block */
- register long size; /* size of block */
- register struct freeblock *back; /* block before 'p' */
- register int i; /* temp variable for counting */
-
- printf("DUMPING FAST FREE LIST:\n");
- back = &firstfree;
- for (p = firstfree.fore, i=uncombined; p != firstcombined;
- p = p->fore) {
- if (--i < 0)
- abort("too many uncombined areas");
- size = p->size;
- printf(". . . area @ %08x, size = %ld\n", p, -size);
- if (size >= 0 || size != ((int *) p)[-1 - size])
- abort("dumpchain: bad size");
- if (p->back != back)
- abort("dumpchain: bad back");
- back = p;
- }
- printf("DUMPING COMBINED FREE LIST:\n");
- for (; p != &lastfree; p = p->fore) {
- size = p->size;
- printf(". . . area @ %08x, size = %d\n", p, size);
- if (size <= 0 || size != ((int *) p)[size - 1])
- abort("dumpchain: bad size");
- if (p->back != back)
- abort("dumpchain: bad back");
- back = p;
- }
- if (back != lastfree.back)
- abort("dumpchain: bad lastfree");
-}
-
-/*
-:h3.reportarea() - Display a Contiguous Set of Memory Blocks
-*/
-
-static reportarea(area)
- register long *area; /* start of blocks (from addmemory) */
-{
- register long size; /* size of current block */
- register long wholesize; /* size of original area */
- register struct freeblock *p; /* pointer to block */
-
- if (area == NULL)
- return;
- wholesize = - *area++;
- wholesize -= 2;
-
- while (wholesize > 0) {
- size = *area;
- if (size < 0) {
- register int i,j;
-
- size = -size;
- printf("Allocated %5d bytes at %08x, first words=%08x %08x\n",
- size * sizeof(long), area + 1, area[1], area[2]);
-#if DEBUGWORDS
- printf(" ...Last operator: %s\n",
- (char *)area[size-DEBUGWORDS-1]);
-#endif
- for (i = size - DEBUGWORDS; i < size - 2; i += 8) {
- printf(" ...");
- for (j=0; j<8; j++)
- printf(" %08x", area[i+j]);
- printf("\n");
- }
-
- }
- else {
- printf("Free %d bytes at %x\n", size * sizeof(long),
- area);
- if (size == 0)
- abort("zero sized memory block");
-
- for (p = firstfree.fore; p != NULL; p = p->fore)
- if ((long *) p == area) break;
- if ((long *) p != area)
- abort("not found on forward chain");
-
- for (p = lastfree.back; p != NULL; p = p->back)
- if ((long *) p == area) break;
- if ((long *) p != area)
- abort("not found on backward chain");
- }
- if (area[0] != area[size - 1])
- abort("unmatched check sizes");
- area += size;
- wholesize -= size;
- }
-}
-
-/*
-:h3.MemReport() - Display All of Memory
-*/
-
-MemReport()
-{
- register int i;
-
- dumpchain();
-
- for (i=0; i<MAXAREAS; i++)
- reportarea(freearea[i]);
-}
-
-/*
-:h3.MemBytesAvail - Display Number of Bytes Now Available
-*/
-
-MemBytesAvail()
-{
- printf("There are now %d bytes available\n", AvailableWords *
- sizeof(long) );
-}
projects / rdpsrv / blobdiff