t1malloc.c

unix vnc 协议源码. VNC是一款远程控制工具软件.

/* $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 ([e-mail])
 
*/

#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