rh@smds.UUCP (Richard Harter) (11/11/90)
My apologies for the length of this posting and for the fact that
it is in lang.c rather than sources (which we don't carry because of
space problems). I have gotten a fair number of requests for a copy
of the allocator that I mentioned in a previous posting. After some
soul searching (we do sell software for *money* after all) I decided
to release it for public use. [Sarcastic comments like "You get money
for software like that!?" are directed to /dev/null.] I make no claims
that it is the best possible DSA. If I were writing it today there are
a number of things that I would do differently. That's as it may be.
Again apologies to everyone for the length of the posting.
-------------------------- CUT HERE ---------------------------------
/* --------------------------------------------------------------------- */
/* */
/* Copyright (c) 1990 Software Maintenance and Development Systems, Inc. */
/* */
/* Permission is granted to copy, modify, and distribute this software */
/* provided that this notice is retained and not modified. There is no */
/* guarantee that this software is useful for anything or that it is in */
/* any way correct or of value. SMDS Inc. disclaims any responsibility */
/* for the consequences of using this software. */
/* */
/* --------------------------------------------------------------------- */
#include <stdio.h>
/* -------------------------------------------------------------------- */
/*
REVISION HISTORY DATA
File name: getsp.c
Title: Storage allocation package
Version name: V7.22
Version date: plastic
Last cset: cs.0203
Last rev: 31
Last rev date: 90/10/31
DESCRIPTION
This is a dynamic storage allocation package. The entry points
are:
initsp Initialization entry
getsp Gets space from the allocator
retsp Returns space to the allocator
moresp Increases the size of an array
prgetsp Prints storage map
Initsp is called internally. Retsp has one argument -- the address of
a block of storage being returned; it should be cast as char *.
Getsp has two arguments, the length requested and an ID code. It returns
the address of the block as a character pointer. Moresp has four
arguments, the old pointer, the old length, the new length, and a
request ID; it returns a pointer to the increased block. Prgetsp
prints a storage map; it has one argument, a pointer to the output
file.
Associated with each block is a node; this node has five elements,
an address, storage left and right links, and avail left and right
links. Storage is divided into blocks requested from the system.
Each block has a dummy node at the high end for termination. The
blocks are doubly linked with null pointers for termination. The
avail lists are circularly double linked with no header node. The
blocks in use are singly linked, null terminated. They use the
avail left link (avail right for a block in use is null.)
Notes:
1. This is a best fit allocator
2. Global epoch_number must be set by the program using this
package. Set it in any way that's appropriate for your job.
3. Execution time of this package is about the same as malloc/free
on a SUN 3/50 OS 3.4; results may be entirely different on your
machine.
4. This is a modified version of the SMDS package; sundry utilities
have been stripped out.
5. The request number can be anything you like; you may wish to
modify the code to make it a pointer to a string.
6. Globals maxalloc and curalloc give you the maximum space allocated
and the current amount.
7. No claim is made that this code is beautiful, easy to read, or
easy to understand.
Note on allocation strategy:
The allocator distinguishes between big blocks (>1024 bytes) and small;
blocks. Blocks are allocated in units of 8 bytes. A list is maintained
for sizes up 128 units (1024 bytes) which heads a linked list of all
free blocks of that size. A subsidiary list is used when the regular
list of 'small' blocks is sparse. The package gets space from malloc
in 65K blocks for allocatable space; node space is also taken from
malloc.
*/
/* -------------------------------------------------------------------- */
#define NSH 3
#define MXSZ 128
#define BKSZ 65472
#define NH 1024
#define HMSK 0x000003ff
#define NPX 8
#define NN 256
#define TRUE 1
#define FALSE 0
#define GETNODES (struct node *)malloc(NN*sizeof(struct node))
struct node { /* Block control structure */
char *a; /* Address of block */
struct node *sl; /* Storage left pointer */
struct node *sr; /* Storage right pointer */
struct node *al; /* Avail left pointer */
struct node *ar; /* Avail right pointer */
int reqno; /* Request # */
int epoch; /* Epoch # of request */
} ;
static int npx = 0; /* # nonzero entries in px */
static int nfree = 0; /* # of free nodes */
static int svx[MXSZ]; /* Stack for px indices */
static int sx[MXSZ]; /* Array of svx entries */
static struct node *px[MXSZ+1]; /* Array of avail list headers */
static struct node *ha[NH]; /* Array of hash list headers */
static struct node *xfree = 0; /* Free list pointer */
static int ninit = TRUE; /* Not initialized flag */
/* ------------------------ Globals ----------------------------------- */
int epoch_number= 0; /* Allocation 'time' */
int maxalloc = 0; /* Maximum space allocated */
int curalloc = 0; /* Current space allocated */
/* ------------------------ Storage allocator ------------------------- */
char *getsp(size,reqno) /* Allocator entry */
int size; /* Size of requested block */
int reqno; /* Request identifier */
{
register struct node *rp; /* Right neighbour in split */
register struct node *np; /* Node of new block */
register struct node *ap; /* Utility node pointer */
register int fx; /* Found index */
register int kx; /* Split index */
register int i; /* Loop index */
register int *ps; /* Loop index */
register char *cc; /* Utility char ptr */
register int rsz; /* Requested size (rounded) */
register int nsz; /* Size of remnant */
register int sz; /* Size of block found */
register int rx; /* Requested index */
register int hx; /* Hash index */
register int *ts; /* Loop limit */
char *malloc(); /* System allocator */
if (size<=0) { /* Bad size request */
fprintf(stderr,"Bad allocation request: %d bytes requested with ID %d\n",
size,reqno);
exit(1); /* Get out of here, now! */
}
size += 4; /* Allow for check words */
if (ninit) initsp(); /* Initialize if needful */
if (nfree<=4) { /* Get more nodes if needful */
np=GETNODES; /* Allocate space for them */
for (i=0;i<NN;i++) (np+i)->ar = np+i+1; /* Link them */
(np+NN-1)->ar = xfree; /* Link to free list */
xfree = np; /* Reset free list ptr */
nfree += NN; /* Update free count */
}
rx=(size-1)>>NSH; /* Get requested index */
rsz=(1+rx)<<NSH; /* Get rounded request size */
curalloc += rsz; /* Update current usage */
if (maxalloc<curalloc) maxalloc=curalloc;/* Update maxalloc if more */
np=0; /* Init node pointer found */
if (rx>=MXSZ) fx=MXSZ; /* Big request, set fx for big */
else { /* Search small blocks lists */
if (px[rx]) fx=rx; /* Exact fit exists */
else if (npx<NPX) { /* Few small blocks */
fx = MXSZ; /* Init fx big for not gound */
ps = svx; /* Init svx search loop ptr */
ts = svx+npx; /* Init terminator */
for (;ps<ts;ps++) /* Loop to search svx */
if (*ps>rx && *ps<fx) fx = *ps; /* Better value for fx found */
}
else { /* Many small blocks, search px */
if (!px[MXSZ]) px[MXSZ]=xfree; /* Use xfree as sentinel */
for (fx=rx;!px[fx];fx++); /* Find non empty px slot */
if (px[MXSZ]==xfree) px[MXSZ]=0; /* Reset null big */
}
}
if (fx==MXSZ) { /* Must search large list */
np=px[fx]; /* Get big list header */
while (np) { /* Search loop */
sz=(np->sr->a)-(np->a); /* Get size of block */
if (sz>=rsz) break; /* Satisfactory block found */
np=np->ar; /* Else get next block */
if (np==px[fx]) np = 0; /* List exhausted */
}
}
else { /* Small block case */
np=px[fx]; /* Small block found, set np */
sz=(1+fx)<<NSH; /* Compute size */
}
if (!np) { /* No block found, get space */
np=xfree; /* Get free node for np */
rp=xfree->ar; /* Get node for sr neighbour */
xfree=rp->ar; /* Reset xfree */
nfree -=2; /* Decrease free count */
np->sl=0; /* No left neighbour */
np->sr=rp; /* Right neighbour is rp */
rp->sl=np; /* Set left of right */
rp->sr=0; /* Null right of right */
if (rsz<BKSZ) sz=BKSZ; /* Small request, use big block */
else sz=rsz; /* Big, use it instead */
np->a = malloc((unsigned)sz); /* Get space for new block */
if (!np->a) { /* Storage allocation failure */
fprintf(stderr,"Memory allocation error: size was %d, ID was %d\n",
size,reqno);
prgetsp(stderr);
exit(1); /* Get out entirely */
}
rp->a = (np->a)+sz; /* Set address for storage right*/
rp->ar=0; /* Mark right as boundary in use*/
}
else { /* Block found, detach it */
if (np->ar==np) { /* Self linked, list empty */
px[fx]=0; /* Remove entry from slot */
if (fx<MXSZ) { /* In short blocks list */
kx=sx[fx]; /* Get index in short list */
npx--; /* Decrease variety count */
svx[kx]=svx[npx]; /* Move old stack top down */
sx[svx[kx]]=kx; /* Record new pos in stack */
}
}
else { /* List not empty, do detach */
np->ar->al=np->al; /* Link right to left */
np->al->ar=np->ar; /* Link left to right */
px[fx]=np->ar; /* Get new px entry */
}
}
if (rsz<sz) { /* Block will be split */
rp=xfree; /* Get node for block */
xfree=xfree->ar; /* Reset free list header */
nfree--; /* Decrement free node count */
rp->a=(np->a)+rsz; /* Get address of new node */
rp->sl = np; /* Left of new is old */
rp->sr = np->sr; /* Right of new is right of old */
rp->sr->sl = rp; /* Left of right of new is new */
np->sr =rp; /* Right of old is new */
nsz=sz-rsz; /* Get size of new */
kx=(nsz-1)>>NSH; /* Get index of new */
if (kx>=MXSZ) kx=MXSZ; /* Bound index */
ap=px[kx]; /* Save some indexing with temp */
if (ap) { /* Already blocks of this size */
rp->al = ap; /* Left avail is list entry */
rp->ar = ap->ar; /* Right is right of list entry */
ap->ar = rp; /* Right of entry is new */
rp->ar->al = rp; /* Left of right of new is new */
}
else { /* List entry was empty */
rp->al=rp; /* Link left to self */
rp->ar=rp; /* Link right to self */
px[kx]=rp; /* Update list entry */
if (kx<MXSZ) { /* Not big block list */
sx[kx]=npx; /* Record as stop of stack */
svx[npx]=kx; /* Put in top of stack */
npx++; /* Increase stack size */
}
}
}
hx = (((int)(np->a))/31) & HMSK; /* Compute address hash value */
np->ar = 0; /* Mark not available */
np->al = ha[hx]; /* Link to hash list */
np->reqno = reqno; /* Enter request number */
np->epoch = epoch_number; /* Enter epoch number */
ha[hx] = np; /* Enter in hash list */
cc = np->sr->a -4; /* Get tail end */
*cc++ = 'C'; /* Load test char */
*cc++ = 'C'; /* Load test char */
*cc++ = 'C'; /* Load test char */
*cc++ = 'C'; /* Load test char */
return ((np->a)); /* Return address */
}
/* ------------------------- Return space to allocator ---------------- */
retsp(ad) /* Returns allocated space */
char *ad; /* Address of space */
{
register struct node *np; /* Ptr to node for block */
register struct node *rp; /* Ptr to storage neighbour */
register char *cc; /* Location of test pattern */
register int fx; /* Block index */
register int kx; /* Index into svx stack */
register int sz; /* Size of block */
if (!ad) return; /* Treat 0 address as no-op */
if (ninit) initsp(); /* Initialize if needful */
sz = (((int)ad)/31) & HMSK; /* Compute hash address */
np = ha[sz]; /* Init node pointer */
rp = 0; /* Init prior pointer */
for(;;) { /* Loop to find node */
if (!np) { /* Bad return address */
fprintf(stderr,"Bad memory deallocation: address was %d\n",ad);
exit(1);
}
if (np->a == ad) { /* Node for address found */
if (rp) rp->al = np->al; /* Link prior to next */
else ha[sz] = np->al; /* Else create new list head */
break; /* Escape search loop */
}
rp=np; /* Current becomes prior */
np=np->al; /* Get next trial node */
}
rp = np->sr; /* Get storage right neighbour */
cc = rp->a - 4; /* Get test pattern address */
sz = 1; /* Using sz as a flag */
if (*cc++ == 'C') {
if (*cc++ == 'C') {
if (*cc++ == 'C') {
if (*cc++ == 'C') sz = 0;
}
}
}
if (sz) { /* Bad check char */
fprintf(stderr,"Memory overwrite detected for block at %d with ID %d\n",
ad,np->reqno);
prgetsp(stderr);
exit(1);
}
curalloc -= (rp->a -np->a); /* Update current usage */
if (rp->ar) { /* It's free, do right merge */
sz=(rp->sr->a)-(rp->a); /* Get size of neighbour */
fx=(sz-1)>>NSH; /* Get index of neighbour */
if (fx>MXSZ) fx=MXSZ; /* Bound if big */
if (rp->ar == rp) { /* Self linked is last item */
px[fx]=0; /* Remove px pointer */
if (fx<MXSZ) { /* Small, reset sx, svx */
kx=sx[fx]; /* Get stack position */
npx--; /* Decrement stack size */
sx[svx[npx]]=kx; /* Record stack position */
svx[kx]=svx[npx]; /* Pop stack item down */
}
}
else { /* Not last item in list */
rp->al->ar = rp->ar; /* Link left to right */
rp->ar->al = rp->al; /* Link right to left */
px[fx]=rp->ar; /* Reset px entry, just in case */
}
rp->ar=xfree; /* Link to free list */
xfree = rp; /* New head for free list */
nfree++; /* Inc free list count */
rp->sr->sl = np; /* Link new right to np */
np->sr = rp->sr; /* New right for np */
}
rp = np->sl; /* Get storage left neighbour */
if (rp && rp->ar) { /* It's free, do left merge */
sz=(np->a)-(rp->a); /* Get size of neighbour */
fx=(sz-1)>>NSH; /* Get index of neighbour */
if (fx>MXSZ) fx=MXSZ; /* Bound if big */
if (rp->ar == rp) { /* Self linked is last item */
px[fx]=0; /* Remove px pointer */
if (fx<MXSZ) { /* Small, reset sx, svx */
kx=sx[fx]; /* Get stack position */
npx--; /* Decrement stack size */
sx[svx[npx]]=kx; /* Record stack position */
svx[kx]=svx[npx]; /* Pop stack item down */
}
}
else { /* Not last item in list */
rp->al->ar = rp->ar; /* Link left to left */
rp->ar->al = rp->al; /* Link left to left */
px[fx]=rp->ar; /* Reset px entry, just in case */
}
rp->ar=xfree; /* Link to free list */
xfree = rp; /* New head for free list */
nfree++; /* Inc free list count */
if (rp->sl) rp->sl->sr = np; /* Link new left to np */
np->sl = rp->sl; /* New left for np */
np->a = rp->a; /* Reset address */
}
if (!np->sl && !np->sr->sr) { /* Big block is now empty */
free(np->a); /* Return space for big block */
np->ar = xfree; /* Link node to free list */
np->sr->ar = np; /* Return boundary node */
xfree = np->sr; /* New head for free list */
nfree +=2; /* Inc free list count */
return; /* All done */
}
sz = np->sr->a - np->a; /* Get size of merged block */
fx = (sz-1)>>NSH; /* Get index of block */
if (fx>MXSZ) fx=MXSZ; /* Bound fx */
if (px[fx]) { /* px has entry for this size */
np->al = px[fx]; /* np left is px */
np->ar = px[fx]->ar; /* np right is px right */
np->ar->al = np; /* Link left of right to np */
px[fx]->ar = np; /* Link right of left to np */
}
else { /* px entry is empty */
px[fx] = np; /* Enter np in px */
np->al = np; /* Self link left */
np->ar = np; /* Self link right */
if (fx<MXSZ) { /* Block is small */
sx[fx] = npx; /* Enter stack index in sx */
svx[npx] = fx; /* Enter in stack */
npx++; /* Increment stack size */
}
}
}
/* ------------------------- Initialize allocator --------------------- */
initsp() { /* Initializes allocator */
register int i; /* Loop index */
for (i=MXSZ;--i>=0;) { /* Null out arrays */
svx[i] = 0; /* Clear out stack */
sx[i] = 0; /* Stack entry ptrs */
px[i] = 0; /* List header arrays */
}
px[MXSZ] = 0; /* Final header ptr */
xfree = 0; /* Free list */
nfree = 0; /* Count of free list */
npx = 0; /* Size of stack */
for (i=NH;--i>=0;) ha[i]=0; /* Null out hash list */
ninit = FALSE; /* Claim initialized */
}
/* ------------------------ Print a storage map ----------------------- */
prgetsp(fno) /* Print getsp map */
FILE *fno; /* Ptr to print file */
{
struct node *np = 0; /* Current node pointer */
int i = 0; /* Loop index */
int sz = 0; /* Size of block */
for (i=0;i<NH;i++) { /* Loop over hash indices */
np = ha[i]; /* Get head of hash list */
while (np) { /* Loop over hash list */
sz = np->sr->a - np->a; /* Compute block size */
fprintf(fno,"%3d %8d %8d %8d %10d\n",i,sz,np->epoch,np->reqno,np->a);
np=np->al; /* Next item in the list */
}
}
fclose(fno); /* Cleanup of error file */
}
/* ------------------------ Increases allocated storage --------------- */
char *moresp(old,len,inc,reqno) /* Gets more space */
char *old; /* Pointer to old */
int *len; /* Ptr to old length */
int inc; /* Amount to increase it */
int reqno; /* Request number */
{
char *new = 0; /* Pointer to new */
int n = 0; /* New length */
n = *len + inc; /* Length of new */
new = getsp(n,reqno); /* Get space for it */
if (*len) memcpy(new,old,*len); /* Copy in old, if needful */
if (old) retsp(old); /* Return space for old */
*len = n; /* Update size */
return new; /* Return new array */
}
---------------------------- CUT HERE ------------------------------------
--
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb. This sentence short. This signature done.