/* --------------------------------------------------------------------- */ /* BEGIN COPYRIGHT AND LICENSE NOTICE */ /* --------------------------------------------------------------------- */ /* ** Copyright (c) 2008 by Richard Harter. ** ** Permission is hereby granted, free of charge, to any person ** obtaining a copy of this software and associated documentation ** files (the "Software"), to deal in the Software without ** restriction, including without limitation the rights to use, ** copy, modify, merge, publish, distribute, sublicense, and/or ** sell copies of the Software, and to permit persons to whom the ** Software is furnished to do so, subject to the following ** conditions: ** ** The above copyright notices and this permission notice shall be ** included in all copies or substantial portions of the ** Software. ** ** Derivative works shall include a notice that the software is a ** modified version of the copyrighted software. ** ** There is no guarantee that this software is useful for anything ** or that it is any way correct or of value. The author disclaims ** any responsibility for the consequences of using this software. ** */ /* --------------------------------------------------------------------- */ /* END COPYRIGHT AND LICENSE NOTICE */ /* --------------------------------------------------------------------- */ /* DESCRIPTION This is a dynamic storage allocation package. It is not a replacement for malloc/free; instead it sits on top of malloc/free. The purpose of this package is to provide a portable storage allocation package that is friendlier to error detection and correction than raw malloc/free. There is an associated include file called getspace.h that contains the prototypes, macros, and structure definitions needed by the user. There is a readme.txt file that gives the rationale for using the package, and information about using it. The entry points are: cfgspace Configures the allocator package getspace Gets space from the allocator freespace Returns space to the allocator morespace Increases the size of allocated space printspace Prints a storage usage map queryspace Returns the usuable space in a block The argument lists for freespace, getspace, morespace, and printspace all include an identification string as the final argument. The id string is used for documentation in reports. The id string can be any thing you like; getspace.h provides a macro called LINELOC that creates a string containing the file name and line number that is particularly useful * Cfgspace has one argument, a pointer to a configuration structure defined in getspace.h. Use this function to override the default values in the allocator. A commmon use is to change the error file. * Freespace has two arguments, the address of the block of storage being freed, and an identification string. It returns TRUE (1) if the block was successsfully freed and FALSE (0) if it was not. * Getspace has two arguments, the requested length and a pointer to an identification string. It returns a pointer to the allocated block. * Morespace is a fancy version of realloc. It has four arguments. The first is the address of the buffer being resized; if it is 0 a fresh buffer is allocated. The second argument is the number of bytes to retain. The third argument is the number of bytes needed. Finally the fourth argument is an identification string. It returns a pointer to the reallocated block. * Printspace prints information about the storage allocation, including the avail lists and the storage map. It has two arguments, the file pointer to the file that will be written, and an identification string. * Queryspace is a utility. It has one argument, the address of a possibly allocated block of storage. It returns the block size, if any. */ /* ------------------------- Include files ----------------------------- */ #include #include #include #include #include #include "getspace.h" #include "trace.h" /* -------------------------- Macro Definitions ------------------------ */ #define NABITS 3 #define ASIZE (1<>5); hash &=HMSK; } while(0) #define ENTER_CHECK_BYTES(address) do { \ int i; \ for (i=ASIZE; i-- > 0;) address[i] = chkstr[i]; \ } while(0) #define CADTYPE size_t #define CTAD(x) (CADTYPE)x #define NODE struct node #define SDATA struct sdata_s #define NODESZ(x) (x->sr->a - x->a) #define USIZE(x) ((NODESZ(x) - ASIZE) /* ------------------------ structure Definitions ---------------------- */ NODE { /* Block control structure */ char *a; /* Address of block */ NODE *sl; /* Storage left pointer */ NODE *sr; /* Storage right pointer */ NODE *al; /* Avail left pointer */ NODE *ar; /* Avail right pointer */ char *id; /* Request identifier */ unsigned long seqno; /* Sequence # (epoch) */ }; SDATA { /* Small bins search data */ int mark; /* Mark/unmarked flag */ size_t parent; /* Parent in sdata tree */ size_t right; /* Right child, if any */ size_t up; /* Where to search up */ }; /* ------------ Internal globals not configurable by user -------------- */ static NODE **small = 0; /* Array of avail list headers */ static SDATA *sdata = 0; /* Array of search data info */ static NODE *big = 0; /* Root of the big tree */ static NODE **atree = 0; /* Address tree headers array */ static int *hcnt = 0; /* Array of atree sizes by hash */ static NODE *xfree = 0; /* Free list pointer */ static NODE *stgstart = 0; /* First node in storage list */ static NODE *stgend = 0; /* Last node in last slab */ static int notinit = TRUE; /* Not initialized flag */ static int nfree = 0; /* # of free nodes */ static unsigned long ntotal = 0; /* Total number of nodes */ static unsigned long seqno = 2; /* Allocator sequence number */ static unsigned long maxstg = 0; /* Maximum space allocated */ static unsigned long curstg = 0; /* Current space allocated */ static unsigned long totstg = 0; /* Total storage managed */ static unsigned long maxslab = 0; /* Maximum number of slabs */ static unsigned long curslab = 0; /* Current number of slabs */ static char * idbuf = 0; /* Buffer for IDs in printnode */ static char *chkstr = "D9qzjxWk"; /* Terminating check string */ /* ------------ Defaults for configurable internal globals ------------- */ #define SLABSZ 131072 #define MINSLAB 8192 #define NH 1024 #define SSZ 8191 #define NNODE 256 /* -------------- Internal globals configurable by user ---------------- */ static size_t slabsz = SLABSZ;/* Block size for slabs */ static FILE * errfile = stderr;/* Program error file */ static int ufree = FALSE; /* T says free malloc zllocs */ static size_t idsize = 20; /* Default ID max size */ static int kslab = FALSE; /* Kill empty slabs flag */ static int dbgflag = FALSE; /* Debug flag, print extra info */ static int nokill = FALSE; /* Debug flag, print extra info */ static int zero = FALSE; /* Zero allocated memory */ static size_t nh = NH; /* # of hashes for address trees*/ static size_t ssz = SSZ; /* Size of small blocks headers */ static size_t nnode = NNODE; /* Expand node list by nnode */ /* ---------------------- Internal prototypes -------------------------- */ static void atree_enter_address (NODE *); static int check_overwrite (NODE *); static int check_tree (NODE *, int); static void detach_node (NODE *, NODE **, NODE **); static void errspace (unsigned int, char *, void *, size_t); static NODE * find_available (int, size_t); static void big_remove (NODE ** , NODE * ); static NODE * big_extract (NODE **, size_t); static void big_insert (NODE ** , NODE *); static NODE * get_node (void); static void initspace (void); static void place_in_free (NODE *); static void place_in_use (NODE *, char *); static void printnode (FILE *, NODE *, int *); static void printtitle (FILE *); static void print_sdata (FILE *); static void print_tree (FILE *,NODE *); static void remove_from_free (NODE *); static NODE * remove_from_use (char *); static void sdata_populate (SDATA *); static void sdata_populate_r (size_t, size_t); static size_t small_count (size_t); static void small_insert (NODE *, size_t); static size_t small_find (size_t); static void small_remove (NODE *, size_t); static int stg_free_slab (NODE *); static void stg_merge_left (NODE *); static void stg_merge_right (NODE *); static NODE * stg_new_slab (size_t); static void stg_split_block (NODE *,size_t); static size_t sz_index_for_size (size_t); static size_t sz_round_up_size (size_t); /* --------------------------------------------------------------------- */ /* BEGIN PUBLIC FUNCTIONS */ /* --------------------------------------------------------------------- */ /* ------------------------- Configure allocator ----------------------- */ /* Function name: cfgspace Description: Configures the allocator package Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: struct cfgspace_s * cfg Ptr to structure holding config info Abstract: This routine passes configuration information to the allocator package. Configurable items fall into two categories, those reconfigurable at any time, and those configurable only during initialization. */ void cfgspace(struct cfgspace_s *cfg) { trace("cfgspace"); /* Calling sequence trace */ if (cfg) { /* There is a config structure */ if (cfg->fptr) errfile = cfg->fptr; /* Reset the error file */ if (cfg->slabsz && (cfg->slabsz >= MINSLAB)) /* Valid slab size? */ { slabsz = cfg->slabsz ; /* Reset the slab size */ } ufree = !!(cfg->ufree); /* set freespace calls free flag*/ if (cfg->idsize >0) { /* The idsize field is set */ if (cfg->idsize > idsize) { /* The new one is bigger, resize*/ free(idbuf); /* Get rid of old idbuf, if any */ idbuf = malloc(idsize+1); /* New one, idsiz + nul space*/ if (!idbuf) errspace(9,0,0,0); /* Malloc failed, die */ } idsize = cfg->idsize; /* Enter new ID buffer size */ } kslab = cfg->kslab; /* Set kill empty slab flag */ dbgflag = cfg->dbgflag; /* Sets the debug flag */ nokill = cfg->nokill; /* Sets the nokill flag */ zero = cfg->zero; /* Sets the zero memory flag */ if (cfg->nnode > 2) { /* Nnode must be at least 3 */ nnode = cfg->nnode; /* Set the free list increase # */ } if (notinit) { /* Initialization only params */ if (cfg->nh) nh = cfg->nh; /* Set the number of hashes */ if (cfg->ssz) ssz = cfg->ssz; /* Set the small lists size */ } } if (notinit) initspace(); /* Initialize if needful */ cfg->fptr = errfile; /* Record error file pointer */ cfg->slabsz = slabsz; /* Record slab size */ cfg->ufree = ufree; /* Record calls free flag */ cfg->idsize = idsize; /* Record ID print buffer size */ cfg->kslab = kslab; /* Record kill empty slabs flag */ cfg->dbgflag = dbgflag; /* Record debug flag */ cfg->nokill = nokill; /* Record no kill on error flag */ cfg->nnode = nnode; /* Record # nodes to fetch */ cfg->nh = nh; /* Record # of address hashes */ cfg->ssz = ssz; /* Record # of small lists */ } /* ------------------------- Return space to allocator ----------------- */ /* Function name: freespace Description: Returns allocated space to the allocator Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: int Arguments: void * ad The address of the block being freed char * id An identifying string use to tag the request Abstract: This routine returns an allocated block to the allocator. If the argument is a null pointer (0) the allocator will be initialized if wasn't already initialized; other than that, nothing is done. Freespace expects the first argument to be the address of an allocated block. If it is, freespace frees it. What freespace does if ad is not a valid getspace address depends upon the setting of ufree. If ufree is set, freespace assumes the block came from malloc and frees it using free. If ufree is not set, the address is an error; the error handler is called. The error handler writes an error message and the program is terminated unless the nokill flag is set. Freespace returns TRUE (1) if a block was successfully freed and FALSE (0) if it was not. The id argument can be any C string the user desires; however it is suggested that getspace be called with the LINELOC macro. */ int freespace(void * ad, char *id) /* Returns allocated space */ { NODE *np; /* Ptr to node for block */ NODE *rp; /* Ptr to storage right */ NODE *lp; /* Ptr to storage left */ trace("freespace"); /* Calling sequence trace */ if (!ad) { /* Treat 0 address as no-op */ if (notinit) initspace(); /* Allow no-op to initialize */ return FALSE; /* Go away quietly */ } if (notinit) errspace(3,0,ad,0); /* Not init here must be bad */ np = remove_from_use(ad); /* Get node for the address */ if (!np) return FALSE; /* No node, just called free */ if (check_overwrite(np)) { /* Check for overwrite */ errspace(4,np->id,np->a,0); /* Overwrite happened, die */ } rp = np->sr; /* Get storage right neighbour */ lp = np->sl; /* Get storage left neighbour */ curstg -= (rp->a -np->a); /* Update current usage */ seqno += 2; /* Advance sequence number */ np->seqno = (seqno +=2) & FREESPACE; /* Enter sequence number */ if (!(rp->seqno & USED)) stg_merge_right(np); /* Merge right if free */ if (!(lp->seqno & USED)) stg_merge_left(np); /* Merge left if free */ if (kslab && stg_free_slab(np)) return TRUE; /* Killed an empty slab*/ place_in_free(np); /* Add to the free blocks */ np->id = id; /* Tag the freed block */ return TRUE; /* Successful deallocation */ } /* ------------------------- Storage allocator ------------------------- */ /* Function name: getspace Description: Gets the requested amount of space Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void * Arguments: size_t size The amount of storage being requested char * id An identifying string use to tag the request Abstract: This routine returns an aligned pointer to space that is sufficient to include the requested amount of space plus space for check bytes used for error detection. Getspace guarantees that it has returned the requested amount of space. If it can't, what it does depends upon the nokill flag. When set, getspace returns a null pointer. If not set, getspace generates an error report and exits. The id argument can be any C string the user desires; however it is suggested that getspace be called with the LINELOC macro. */ void * getspace(size_t size,char * id) /* Allocator entry */ { NODE *np; /* Node of new block */ int sx; /* Found index */ size_t rsz; /* Requested size (rounded) */ size_t sz; /* Size of block found */ trace("getspace"); /* Calling sequence trace */ if (notinit) initspace(); /* Initialize if needful */ rsz = sz_round_up_size (size); /* Round up, allow check chars */ sx = sz_index_for_size(rsz ); /* Map the size to an index */ np = find_available(sx,rsz); /* Get an available free node */ if (!np) np=stg_new_slab(rsz); /* Else get a new slab */ sz = NODESZ(np); /* Get new block size */ if (rszsr->a - np->a); /* Update current usage */ if (maxstga)); /* Return address */ } /* ----------- morespace - Increases allocated storage ---------------- */ /* Function name: morespace Description: Increases size of an allocated block Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void * Arguments: void * old The address of the block being resized size_t keep The number of bytes to keep of the old site_t need The new size needed char * id An identifying string use to tag the request Abstract: Morespace is a fancy version of realloc. It has four arguments. The first is the address of the buffer being resized; if it is 0 a fresh buffer is allocated. The second argument is the number of bytes to retain. The third argument is the number of bytes needed. The fourth argument is an identifying string; it is suggested that the string be the LINELOC macro. It is an error if (a) the address is not that of an allocated block or (b) the number of bytes to be kept is greater than the number of bytes in old. */ void * morespace(void *old, size_t keep, size_t need, char * id) { NODE *np = 0; /* Node pointer for block */ size_t csz; /* Current block size */ size_t avail_l; /* Space available on the left */ size_t avail_r; /* Space available on the right */ size_t avail; /* Space available left & right */ char *new = 0; /* Pointer to new */ trace("morespace"); /* Calling sequence trace */ if (!old) { /* Special case, no old block */ if (!keep) return getspace(need,id); /* Getspace is all we need */ errspace(10,id,0,keep); /* Want to keep, can't - err */ } if (notinit) initspace(); /* Initialize if needful */ if (keep > need) need = keep; /* Need must hold keep */ need = sz_round_up_size(need); /* Get actual need */ np = remove_from_use(old); /* Get node for the address */ csz = np->sr->a - np->a; /* Get the current block size */ if (csz >= need) { /* Current is big enough */ place_in_use(np,id); /* Re-enter into node/addr str */ return np->a; /* All done, return old address */ } avail_r = (np->sr->seqno & USED) ? 0 : np->sr->a - np->a; avail_l = (np->sl->seqno & USED) ? 0 : np->a - np->sl->a; avail = csz + avail_l + avail_r; /* Space available if merging */ if (avail >= need) { /* We can merge to get space */ if (avail_r) stg_merge_right(np); /* Merge in right block */ if (avail_l) { /* There is a free left side */ if (keep) memcpy(np->sl->a,np->a,keep); /* Copy down */ stg_merge_left(np); /* Merge in left */ } stg_split_block(np,need); /* Split the merged block */ curstg += NODESZ(np) -csz; /* Update current usage */ if (maxstga; /* Return the expanded block */ } else { new = getspace(need,id); /* Get a whole new block */ if (old && (keep > 0)) memcpy(new,old,keep); /* Copy amount to keep */ freespace(old,id); /* Free the old array */ return new; /* Return new array */ } } /* ------------------------ Print a storage map ------------------------ */ /* Function name: printspace Description: Prints the storage allocation report Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: FILE * fptr Pointer to the output file char * id String to identify where printspace was called Abstract: Printspace prints a complete map of the storage allocation blocks, and various statistics about storage usage. It is intended as a diagnostic tool for finding memory leaks, buffer overruns, and for analyzing memory usage patterns. */ void printspace( FILE *fptr, char *id) /* Print storage map & info */ { NODE *np = 0; /* Current node pointer */ time_t tt; /* Time data */ int count; /* Counter used by check tree */ int all_v = 1; /* All address trees valid flag */ int h; /* Index over the hash array */ int i; /* Utility loop index */ int imax; /* Max value in loops for i */ unsigned long bound = 0; /* Number of boundary nodes */ unsigned long free = 0; /* Number of free blocks */ unsigned long inuse = 0; /* Number of blocks in use */ trace("printspace"); /* Calling sequence trace */ if (notinit) initspace(); fptr = fptr ? fptr : stderr; /* Set report file pointer */ tt = time(0); /* Get the current time */ fprintf(fptr,"\n\n****************************************************\n"); fprintf(fptr,"Storage allocation report - %s",ctime(&tt)); fprintf(fptr,"Report identifier: %s\n",id? id : ""); fprintf(fptr,"****************************************************\n\n"); fprintf(fptr,"I. Usage information table\n"); fprintf(fptr," Current allocation ...%9lu\n",curstg); fprintf(fptr," Maximum allocation ...%9lu\n",maxstg); fprintf(fptr," Free space ...........%9lu\n",(totstg-curstg)); fprintf(fptr," Total space managed ..%9lu\n",totstg); fprintf(fptr," Current # of slabs ...%9lu\n",curslab); fprintf(fptr," Maximum # of slabs ...%9lu\n",maxslab); fprintf(fptr," Number of nodes ......%9lu\n",ntotal); fprintf(fptr," Big root node ........%9lu\n", big?(unsigned long)big : 0); for (np = stgstart;;np = np->sr) { /* Node print loop */ if (np->seqno == 1) bound++; /* Boundary node */ else if (np->seqno & USED) inuse++;/* Block in use */ else free++; /* Free block */ if (np==stgend) break; /* Quit when stgend is printed */ } fprintf(fptr," # of boundary nodes ..%9lu\n",bound); fprintf(fptr," # of blocks in use ...%9lu\n",inuse); fprintf(fptr," # of free blocks .....%9lu\n",free); fflush(fptr); for (h=0;h 10 ? 10 :imax; for (i=0;i= imax) continue; fprintf(fptr,"%5d",h); for (i=0;i0) fprintf(fptr," %6d",hcnt[h+i]); else fprintf(fptr," ."); } fprintf(fptr,"\n"); } fflush(fptr); fprintf(fptr,"\nIV. Small lists search tree data\n\n"); print_sdata(fptr); fflush(fptr); fprintf(fptr,"\nV. Big blocks search tree\n\n"); print_tree(fptr,big); fflush(fptr); fprintf(fptr,"\nVI. Sequential storage map \n\n"); fprintf(fptr,"BEGIN MAP\n"); printtitle(fptr); for (np = stgstart;;np = np->sr) { /* Node print loop */ printnode(fptr,np,hcnt); /* Print the individual node */ if (np==stgend) break; /* Quit when stgend is printed */ } fprintf(fptr,"END MAP\n"); fflush(fptr); fprintf(fptr,"\n\n****************************************************\n"); fprintf(fptr,"End of the storage allocation report\n"); fprintf(fptr,"****************************************************\n\n"); fflush(fptr); } /* ------------------------ Queries the allocator ----------------------- */ /* Function name: queryspace Description: Queries the allocator about a block Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: size_t Arguments: void * addr Pointer to an allocated block, maybe Abstract: Queryspace expects a pointer to an address of an allocated block of storage. It checks to see if the address is legitimate. If it is, it returns the usable size of the block. If it is not it returns 0 */ size_t queryspace(void * ad) /* Get block size for address */ { NODE * np; /* Node pointer to be found */ int hash; /* The address hash code */ CADTYPE cad; /* Comparison casted address */ CADTYPE nad; /* Comparison casted node ad */ size_t size; /* Raw size of block */ NODE ** plink; /* Link of parent to current */ trace("queryspace"); /* Calling sequence trace */ if (notinit) { /* Check for not initialized */ initspace(); /* Initialize if needful */ return 0; /* Nothing in use, go away */ } GETHASH(hash,ad); /* Compute hash address */ cad = CTAD(ad); /* Cast to comparison type */ np = atree[hash]; /* Init node pointer */ for (plink=0;np;) { /* Find address loop, init plink*/ nad = CTAD(np->a); /* Get address as comparable */ if (nad == cad) { /* Address found, block ok */ size = np->sr->a - np->a; /* Get raw block size */ return (size-ASIZE); /* Allow for check bytes */ } plink = (nadar):&(np->al); /* Save link matching size */ np = *plink; /* Goto appropriate link */ } return 0; /* Bad address, return zero */ } /* --------------------------------------------------------------------- */ /* BEGIN PRIVATE FUNCTIONS */ /* --------------------------------------------------------------------- */ /* ------------------------ atree_enter_address ------------------------ */ /* Function name: atree_enter_address Description: Enters a node in the address/node map Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The node to be entered in the map Abstract: The package maintains a binary search tree called the atree that is used to find the node corresponding to a given address. Nodes that are in use are recorded in this tree. The al and ar fields are used for the left and right children. atree_enter_address is called when a free block is put into use. */ static void atree_enter_address(NODE *np) /* Enter node np in the atree */ { NODE * sp; /* Search pointer into tree */ int hx; /* Index into hash table */ CADTYPE nad; /* Comparable node address */ CADTYPE sad; /* Comparable search address */ int lpchk; /* Loop check counter */ GETHASH(hx,np->a); /* Get hash index for address */ np->al = 0; /* np is a leaf, no left link */ np->ar = 0; /* np is a leaf, no right link */ nad = CTAD(np->a); /* Create comparable node addr */ sp = atree[hx]; /* Get the root for the hash */ lpchk = ntotal; /* Initializ count check */ if (!sp) atree[hx] = np; /* Empty tree, set head to np */ else for (;lpchk-- >0;) { /* Search for entry point */ sad = CTAD(sp->a); /* Get comparable search addr */ if (sad > nad) { /* np->a is small, go left */ if (sp->al) sp = sp->al; /* There is a left, go down */ else {sp->al = np; return;} /* No left, make np a leaf */ } else if (sad < nad) { /* Np->a big, go right */ if (sp->ar) sp = sp->ar; /* There is a right, go down */ else {sp->ar = np; return;} /* No right, make np a leaf */ } else errspace(6,0,np->a,0); /* Address is already present */ } if (lpchk <= 0) { errspace(8,np->id,np->a,0); /* Death in the loop */ } } /*----------------------------- big_extract -----------------------------*/ /* Function name: big_extract Description: Tries to find a big block at least the given size Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: NODE * Arguments: NODE ** root The size index size_t rsz The requested size Abstract: This routine searches the big blocks tree for the smallest size block that can hold the requested size. It returns 0 if no suitable node can be found. If one is found big_extract removes it from the big blocks tree. */ static NODE * big_extract(NODE **root, size_t size) { NODE * np; /* Node pointer to be found */ size_t npsz = 0; /* Size of np block */ size_t cpsz; /* Size of candidate */ NODE ** plink; /* Link of parent to current */ np = *root; /* Start at tree root */ plink = 0; /* Init no parent */ while (np) { /* Search right a big one */ npsz = NODESZ(np); /* Get the node size */ if (npsz >= size) break; /* Big enough node found */ plink = &(np->ar); /* Get link to next np */ np = np->ar; /* Get next bigger in the tree */ } if (!np) return 0; /* Nothing big enough in tree */ if (npsz > size) do { /* Search for smaller candidate */ if (!np->al) break; /* Np is a leaf node, done */ cpsz = NODESZ(np->al); /* Get size of candidate */ if (cpsz < size) break; /* No smaller candidate */ plink = &(np->al); /* Get link to next np */ np = np->al; /* Get next smaller in tree */ } while (1); /* End of forever loop */ detach_node(np, plink, root); /* Remove the node from the tree*/ return np; /* Return the detached node */ } /* --------------------------- big_insert ------------------------------ */ /* Function name: big_insert Description: Inserts a node in the big tree Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE ** root Address of the tree root NODE * np The node to be inserted Abstract: This routine inserts a node into the big tree. It first compares on size and then on address. The routine calls the error handler if the node is already present. */ static void big_insert(NODE ** root, NODE *np) { NODE ** plink = 0; /* Parent link to search node */ NODE * sp; /* Search pointer into tree */ size_t npsz; /* Size of node block */ size_t spsz; /* Size of search block */ CADTYPE nad; /* Comparable node address */ CADTYPE sad; /* Comparable search address */ size_t lpcheck; /* Counter to check wild loop */ npsz = NODESZ(np); /* Get the node size */ nad = CTAD(np->a); /* Create comparable node addr */ np->al = 0; /* np is a leaf, no left link */ np->ar = 0; /* np is a leaf, no right link */ if (!*root) { /* This is an empty tree */ *root = np; /* Np becomes the tree root */ return; /* No more to do, go away */ } lpcheck=ntotal; /* Init loop check counter */ for (sp = *root;lpcheck-- > 0;) { /* Loop to search on size */ spsz = NODESZ(sp); /* Get the node size */ sad = CTAD(sp->a); /* Get comparable search addr */ if (spsz > npsz) plink = &(sp->al); /* Np small, go left */ else if (spsz < npsz) plink = &(sp->ar); /* Np right, go left */ else if (sad>nad) plink = &(sp->al); /* Np small, go left */ else if (sadar); /* Np right, go left */ else errspace(6,0,np->a,0); /* Address is already present */ if (*plink) sp = *plink; /* Slot not empty, go down */ else { /* Sp's child is an empty slot */ *plink = np; /* Np is now sp's child */ return; /* Np entered, go away */ } } errspace(8,sp->id,sp->a,0); /* Loop detected */ } /*----------------------------- big_remove ----------------------------*/ /* Function name: big_remove Description: Extract a given node from the big tree Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE ** root Address of the tree root node NODE * np The node to be extracted Abstract: This routine searches the big tree for a given node and extracts it. In this case it is important to know that the tree has a dual ordering, first by size and then by address within blocks with the same size. It is a fatal error if the node is not present. */ static void big_remove (NODE ** root, NODE * np) { NODE ** plink; /* Link from parent to node */ NODE * cp; /* Ptr to search candidate */ size_t cpsz; /* Size of block sp points to */ size_t npsz; /* Size of block np points to */ CADTYPE cad; /* Candidate address casted */ CADTYPE nad; /* Desired node address casted */ if (!root) errspace(7,LINELOC,np->a,0); /* Node missing, die */ nad = CTAD(np); /* Get np casted address */ npsz = NODESZ(np); /* Get size of np block */ plink = 0; /* No parent yet, so no link */ for (cp = *root;cp != np;) { /* Search for right sized node */ cpsz = NODESZ(cp); /* Get the candidate size */ cad = CTAD(cp); /* Get the casted address */ if (cpszar); /* Cand small, save R link */ else if (cpsz>npsz) plink = &(cp->al); /* Cand big, save L link */ else if (cadar); /* Address small, go right */ else if (cad>nad) plink = &(cp->al); /* Address big, go left */ else errspace(11,(char *)np,(void *)cp,0); /* Two nodes death */ cp = *plink; /* Set cand to saved link */ if (!cp) { errspace(7,LINELOC,np->a,0); /* Node missing, die */ } } detach_node(np, plink, root); /* Remove the node from the tree*/ } /*---------------------------- check_overwrite --------------------------*/ /* Function name: check_overwrite Description: Checks whether an array overwrite has occurred Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: int Arguments: NODE * np The node for the block being returned. Abstract: This routine examines the check bytes of a returned array to see if they have been overwritten. Check_overwrite returns TRUE (1)if there is an overwrite; it returns FALSE (0) if none is found. */ static int check_overwrite(NODE *np) /* Check for overwrite */ { char * pre; /* Ptr to before test chars */ char * post; /* Ptr to before test chars */ char * chk; /* Ptr into check string */ int i; /* Loop index */ pre = np->a - 8; /* Point to pre test pattern */ post = np->sr->a - 8; /* Point to post test pattern */ chk = chkstr; /* Point to pattern to match */ for (i=8; i-- >0;) { /* Char match loop */ if ((pre[i] != chk[i]) || /* Check on pre char */ (post[i] != chk[i])) { /* Check on post char */ return TRUE; /* Mismatch, serious error */ } } return FALSE; /* No overwrite */ } /*------------------------------ check_tree -----------------------------*/ /* Function name: check_tree Description: Checks whether a tree is legal Date documented: Sunday 9 March 2008 Documented by: Richard Harter Returned type: int Arguments: NODE * np The current node in the tree. int count The counter used to track # of nodes visited Abstract: This routine recursively examines a binary tree to see if it has a cycle, i.e., whether its linkage has been corrupted. The method used is to use a counter that is decremented each time a node is visited. The counter is initialized with a known bound; if the count reaches zero there must be a cycle. */ static int check_tree(NODE *np, int count) /* Check for overwrite */ { if (!np || (count <= 0)) return count;/* No node, or else cycle */ --count; /* Valid node, decrement counter*/ count = check_tree(np->al,count); /* Check the left child */ return check_tree(np->ar,count); /* Check the right child */ } /*----------------------------- detach_node -----------------------------*/ /* Function name: detach_node Description: Service routine to remove a node from a BST Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The node for the block being returned. NODE ** plink Address of link to np in the parent, NODE ** root Address of the variable containing the root node Abstract: This routine removes a node from a tree. If the node is the only member of the tree the root is set nil. Otherwise there are four cases to handle, no children, left child only, right child only, and both children present. In the second and third cases the child replaces the deleted node. In the fourth case we "randomly" pick either the traversal predecessor (left) or the successor (right). This routine is used both by the address tree and big tree routines. */ static void detach_node(NODE *np, NODE **plink, NODE **root) { int scase = 0; /* Selector for switch */ static int left = 1; /* Picks L or R in case IV */ NODE * sp; /* Search pointer */ NODE * xp; /* Search pointer's parent */ if (np->al) scase += 1; /* Left is present */ if (np->ar) scase += 2; /* Right is present */ switch (scase) { /* Switch on linkage case */ case 0: /* Neither left link nor right */ if (np == *root) *root = 0; /* Tree is empty, kill its root */ *plink = 0; /* Leaf node, just delete it */ break; /* C demands this */ case 1: /* Left child only */ if (plink) *plink = np->al; /* There is a parent */ else *root = np->al; /* Move left child up, done */ break; case 2: /* Right child only */ if (plink) *plink = np->ar; /* There is a parent */ else *root = np->ar; /* Move left child up, done */ break; case 3: /* Both left and right children */ if (left) { /* Move predecessor up */ sp = np->al; /* Initialize search pointer */ if (sp->ar) { /* There is a R, must detach */ do { /* Search down the right side */ xp = sp; /* Child becomes parent */ sp = xp->ar; /* Parent's right is next child */ } while(sp->ar); /* Keep going while more right */ xp->ar = sp->al; /* Parent's R is now sp's left */ sp->al = np->al; /* Sp inherits np's left */ } sp->ar = np->ar; /* Sp inherits np's right */ } else { /* Move the successor up */ sp = np->ar; /* Initialize search pointer */ if (sp->al) { /* There is a L, must detach */ do { /* Search down the right side */ xp = sp; /* Child becomes parent */ sp = xp->al; /* Parent's left is next child */ } while(sp->al); /* Keep going while more left */ xp->al = sp->ar; /* Parent's L is now sp's right */ sp->ar = np->ar; /* Sp inherits np's right */ } sp->al = np->al; /* Sp inherits np's left */ } if (plink) *plink = sp; /* Parent exists, link in sp */ else *root = sp; /* No parent, sp is new root */ left = !left; /* Switch side to use next time */ break; } } /*---------------------------- errspace ----------------------------*/ /* Function name: errspace Description: Handles errors Date documented: Monday 25 February 2008 Documented by: Richard Harter Last modified: Saturday 22 March 2008 Returned type: void Arguments: int errno An error code number char * id Block identifier associated with the error void * a Block address associated with the error size_t sz Block size associated with the error Abstract: This routine is a version for programs that do not have an error processing routine as part of its framework. It generates an error message. If the nokill flag is set and the error is a user error the routine returns. Otherwise it makes a call to the allocator info dump, and a call to the trace dump. It then aborts. */ static void errspace(unsigned int errno, char *id, void *a, size_t sz) { struct err_s { int user_err; int prflag; char * fmt; }; static struct err_s action[] = { {1, 1, "GSP00: Size request was 0\n"}, {1, 1, "GSP01: Request size %lu was too large\n"}, {0, 1, "GSP02: Memory allocation error: size was %lu}, ID was %s\n"}, {1, 1, "GSP03: Tried to free unallocated address %lu\n"}, {0, 1, "GSP04: Memory overwrite detected for block at %lu with ID %s\n"}, {0, 1, "GSP05: Malloc failure, can't get node space.\n"}, {1, 1, "GSP06: Trying to use address %lu while already in use.\n"}, {0, 1, "GSP07: Internal linkage error for block with address %lu, id %s\n"}, {0, 0, "GSP08: Cycle detected in tree linkage, address = %lu, id = %s\n"}, {0, 1, "GSP09: Malloc failed during getspace initialization\n"}, {1, 1, "GSP10: Morespace: Keep was %lu, but no file. ID = %s\n"}, {0, 1, "GSP11: Linkage error, two blocks with the same data, %lu, %lu\n"}, {0, 0, "GSP12: Cycle detected in list linkage, bin no = %l\n"}, }; size_t actsize; actsize = sizeof (action)/sizeof(struct err_s); switch (errno) { case 0: fprintf(errfile,action[errno].fmt );break; case 1: fprintf(errfile,action[errno].fmt,sz );break; case 2: fprintf(errfile,action[errno].fmt,sz,id );break; case 3: fprintf(errfile,action[errno].fmt,(unsigned long)a );break; case 4: fprintf(errfile,action[errno].fmt,(unsigned long)a,id );break; case 5: fprintf(errfile,action[errno].fmt );break; case 6: fprintf(errfile,action[errno].fmt,(unsigned long)a );break; case 7: fprintf(errfile,action[errno].fmt,(unsigned long)a,id );break; case 8: fprintf(errfile,action[errno].fmt,(unsigned long)a,id );break; case 9: fprintf(errfile,action[errno].fmt );break; case 10: fprintf(errfile,action[errno].fmt,sz,id );break; case 11: fprintf(errfile,action[errno].fmt,(unsigned long)a, (unsigned long)id );break; case 12: fprintf(errfile,action[errno].fmt,(unsigned long)sz );break; default: break; } if (nokill && action[errno].user_err) return; if (action[errno].prflag) { printspace(errfile,LINELOC); } trace_dump(errfile); exit(EXIT_FAILURE); } /*-------------------------- find_available -------------------------*/ /* Function name: find_available Description: Finds a large enough block and extracts it Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: NODE * Arguments: int sx The size index size_t rsz The requested size Abstract: This routine searches the free blocks data structures for the smallest size block that can hold the requested size. The package uses doubly linked lists for "small" blocks and a BST for "big" blocks. The linked list headers are in an array called small; the size index, sx, is the index of a block of size rsz. If the request is small, small_find is called to find a small best fit for the block. If a suitable small block is found, small_remove is called to extract a node from its list. If no suitable small node can be found or if the request was big to begin with big_extract is called to extract it from the big tree. */ static NODE * find_available(int sx, size_t rsz) { NODE * np; /* The free node found */ size_t ssx; /* Resized size index */ if (sx 4;nn /=2) { /* Loop to find node space */ sz = nn*sizeof(NODE); /* Space needed for nn nodes */ np = malloc(sz); /* Get node space from malloc */ if (!np) continue; /* Malloc failed, ask for less */ } if (!np) errspace(5,0,0,0); /* Can't get node space, retire */ for (i=0;iar; /* Restore free list header */ nfree--; /* Decrement free node count */ return np; /* Return the new node pointer */ } /* ------------------------- Initialize allocator ---------------------- */ /* Function name: initspace Description: Initializes the allocator Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: void Abstract: This routine takes care of initialization of the various data structures and flags. The flag, notinit, is used to signal that the package has not been initialized. Initspace will be called by getspace and morespace if notinit is set. Freespace will abort if it is called before the package has been initialized. */ static void initspace(void) /* Initializes allocator */ { int i; /* Loop index */ free(idbuf); /* Get rid of old idbuf, if any */ idbuf = malloc(idsize+1); /* Get new one, allow for nul */ if (!idbuf) errspace(9,0,0,0); /* Malloc failed, die */ hcnt = malloc(nh *sizeof(int)); /* Space for hash count array */ if (!hcnt) errspace(9,0,0,0); /* Malloc failed, die */ atree = malloc(nh *sizeof(int)); /* Space for address tree array */ if (!atree) errspace(9,0,0,0); /* Malloc failed, die */ for (i=nh;--i>=0;) atree[i]=0; /* Null out hash list */ small = malloc(ssz *sizeof(int)); /* Space for size header array */ if (!small) errspace(9,0,0,0); /* Malloc failed, die */ for (i=ssz;--i>=0;) small[i] = 0; /* Null out size header arrays */ sdata = malloc(ssz *sizeof(SDATA)); /* Space for sdata array */ if (!small) errspace(9,0,0,0); /* Malloc failed, die */ sdata_populate(sdata); /* Populate the sdata array */ small[ssz] = 0; /* Final header ptr */ xfree = 0; /* Free list */ nfree = 0; /* Count of free list */ notinit = 0; /* Claim initialized */ stgstart = get_node(); /* Get a node for storage start */ stgstart->a = 0; /* Init address field */ stgstart->sl = 0; /* Init storage left field */ stgstart->sr = 0; /* Init storage right field */ stgstart->al = 0; /* Init avail left field */ stgstart->ar = 0; /* Init avail right field */ stgstart->id = LINELOC; /* Init the request ID field */ stgstart->seqno = 0 | USED; /* Init the sequence field */ stgend = stgstart; /* Start is also first end */ } /*--------------------------- place_in_free ----------------------------*/ /* Function name: place_in_free Description: Puts a block in the free data structures Date documented: Monday 7 April 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The node for the block being put in use Abstract: This routine puts a block in the free data structures. If the block is small it will be added to a doubly linked list and the sdata tree will be updated. If it is large it will be placed in the big tree. */ static void place_in_free(NODE * np) /* Enter node in free blocks */ { size_t sx; /* Block index */ sx = sz_index_for_size(NODESZ(np)); /* Get index of block */ if (sx id = id; /* Enter request pointer */ np->seqno = (seqno += 2) | USED; /* Enter sequence number */ if (np->seqno == 1) { /* Checking for rollover */ np->seqno = 3; /* Skip 1, reserved for slabs */ seqno += 2; /* Advance sequence number also */ } ENTER_CHECK_BYTES(np->a); /* Enter the check bytes */ cc = np->sr->a -8; /* Get tail end */ if (zero) { /* Zero memory option */ sz = np->sr->a - np->a; /* Size of the block */ memset(np->a,0,sz); /* Zero it */ } for (i=8;i-- >0;) cc[i] = chkstr[i]; /* Load test characters */ atree_enter_address(np); /* Set up address/node map */ } /*--------------------- printnode - prints node data --------------------*/ /* Function name: printnode Description: Prints the data for a single node Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: FILE * fptr The file pointer for the output file NODE * np The pointer to the node int * hcnt Hash count table, - is an error Abstract: This routine prints the data for a single node. Addresses are converted to decimal. */ static void printnode(FILE *fptr, NODE *np, int * hcnt) { void * sla; void * sra; size_t size; char usage; char errcode; char *cc; int hash; sla = np->sl ? np->sl->a : 0; sra = np->sr ? np->sr->a : 0; if (np->seqno == 1) { if (np != stgend) size = ASIZE; else size = 0; } else if (np->sr && np->sr->a) size = NODESZ(np); else size = 0; usage = np->seqno & USED ? np->seqno == 1 ? 'S' :'U' : 'F'; errcode = '.'; if (usage == 'F') { GETHASH(hash,np->a); if (hcnt[hash] < 0 ) errcode = '-'; if (check_overwrite(np)) errcode = 'E'; } if (!np->id) cc = ""; else if (strlen(np->id) <= idsize) cc = np->id; else { memcpy(idbuf,np->id,idsize); cc = idbuf; cc[idsize] = 0; } fprintf(fptr,"%c %c %6lu ",usage, errcode, size); fprintf(fptr,"%9lu %9lu %9lu %9lu %9lu %9lu %9lu %9lu %6ld %6s\n", (unsigned long)np, (unsigned long )np->a, (unsigned long)np->sl, (unsigned long)sla, (unsigned long)np->sr, (unsigned long)sra, (unsigned long)np->al, (unsigned long )np->ar, np->seqno, cc); } /*--------------------------- print_sdata -------------------------------*/ /* Function name: print_sdata Description: Prints the sdata tree Date documented: Monday 7 April 2008 Documented by: Richard Harter Returned type: void Arguments: FILE * fptr File pointer for the output file Abstract: This routine prints out the fields of the sdata tree. The left link and the size of corresponding small linked list are computed. */ static void print_sdata(FILE * fptr) { size_t i; /* Loop index for print loop */ size_t left; /* Left link, if any */ size_t parent; /* Parent, if needed */ fprintf(fptr," Bin Mark Parent Left Right Up Size\n"); for (i=0;iad","sr","sr->ad","al","ar", "seq","origin",0}; char * fmts[] = { "%1s"," %1s"," %6s", " %9s"," %9s"," %9s"," %9s"," %9s"," %9s"," %9s"," %9s", " %6s"," %6s\n\n",0 }; int i; for (i=0;fmts[i];i++) fprintf(fptr,fmts[i],hdrs[i]); } /*------------------------------ print_tree -----------------------------*/ /* Function name: print_tree Description: Prints a tree Date documented: Wednesday 16 April 2008 Documented by: Richard Harter Returned type: void Arguments: FILE * fptr The file pointer for the file to write to NODE * root Root of the tree being printed Abstract: This routine rcursively prints out the content of a tree. */ static void print_tree(FILE *fptr, NODE *np) { if (!np) return; print_tree(fptr,np->al); printnode(fptr,np,hcnt); print_tree(fptr,np->ar); fflush(fptr); } /* ------------------------ remove_from_free ------------------------*/ /* Function name: remove_from_free Description: Extracts a specific node from the free blocks Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The node to be extracted size_t rsz The requested size Abstract: This routine searches the free blocks data structures for a specific node and extracts it. The node can either be in a small blocks doubly linked list or in the large blocks tree. If it is small, we call small_remove; if big, we call big_remove. */ static void remove_from_free (NODE * np) { size_t sx; /* Found index */ size_t sz; /* Block size */ sz = NODESZ(np); /* Size of block */ sx = (sz-1) >> NABITS; /* Get index of left storage */ if (sxa); /* Get address as comparable */ if (nad == cad) break; /* Address found, escape loop */ plink = (nadar):&(np->al); /* Save link matching size */ np = *plink; /* Goto appropriate link */ } detach_node(np,plink,&(atree[hash])); /* Relink the tree minus np */ return np; /* Return the detached node */ } /*---------------------------- sdata_populate ---------------------------*/ /* Function name: sdata_populate Description: Populates the sdata array Date documented: Wednesday 2 April 2008 Documented by: Richard Harter Returned type: void Arguments: SDATA * sdata Holds traversal data for the small bins array. Abstract: This routine initializes the sdata array. The parent, right, and up fields are static and depend only on n. */ static void sdata_populate(SDATA * sdata) { size_t i; /* Traversal loop index */ size_t step; /* Size of step to right */ for (step = 1;step <= ssz; step *= 2);/* Get pow2 bounding ssz */ step /= 2; /* Step is just under ssz */ for (i = ssz; i-- > 0;) { /* Initialize everything loop */ sdata[i].mark = FALSE; /* All marks are set unmarked */ sdata[i].parent = 0; /* Init no parent */ sdata[i].right = 0; /* Init no right neighbour */ sdata[i].up = 0; /* Init no path up */ } sdata_populate_r(0,step); /* Start recursive initialize */ } /*---------------------------- sdata_populate_r -------------------------*/ /* Function name: sdata_populate_r Description: Recursive subroutine of sdata_populate Date documented: Wednesday 2 April 2008 Documented by: Richard Harter Returned type: void Arguments: size_t entry Current index into the table. size_t step Step size for right child. Abstract: This routine is the recursive component of sdata initialization; it takes care of one node and then populates the left and right children. */ static void sdata_populate_r(size_t entry, size_t step) { size_t left; /* Left child */ size_t right; /* Right child */ if (step <= 1) return; /* At the bottom tier */ left = entry + 1; /* Left child is parent + 1 */ right = entry + step; /* Right is parent + step */ fflush(stdout); step /= 2; /* Cut step size for children */ if (left < ssz) { /* Is there a left child? */ sdata[left].parent = entry; /* Set left child's parent */ sdata_populate_r(left,step); /* Process the left child */ if (right < ssz) { /* Is there also a right child? */ sdata[left].up = right; /* Up is right for lefties */ sdata[right].parent = entry; /* Set its parent */ sdata[entry].right = right; /* Set parent's right child */ sdata[right].up = sdata[entry].up;/* Inherit parent's up link*/ sdata_populate_r(right,step); /* Process the right child */ } } } /*------------------------------ small_count ----------------------------*/ /* Function name: small_count Description: Counts the number of entries in a bin Date documented: Saturday 5 April 2008 Documented by: Richard Harter Returned type: size_t Arguments: size_t sx Bin index of node. Abstract: This routine counts the number of nodes in the a bin's list. There is a cycle detection check. */ static size_t small_count(size_t sx) { NODE * np; /* Small bin header, if any */ NODE * sp; /* Search node pointer */ size_t count =1; /* Number of nodes in list */ np = small[sx]; /* Get bin header */ if (!np) return 0; /* Nothing in bin, go away */ for (sp=np;sp->ar != np;sp=sp->ar) { /* Loop through the list */ count++; /* Inc count, not back at np */ if (count>=ntotal) errspace(12,0,0,sx); /* Linkage error check */ } return count; /* The number of nodes in bin */ } /*------------------------------ small_insert ---------------------------*/ /* Function name: small_insert Description: Enters node into small lists using sdata Date documented: Wednesday 2 April 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * sdata Enters node into small bins array. size_t sx Bin index of node. Abstract: This routine enters a node into a small bin. If the bin has content we simply link it in. If it is an empty bin we add marks as needed in sdata and init the bin contents. */ static void small_insert(NODE *np, size_t sx) { NODE * sp; /* Small bin header, if any */ sp = small[sx]; /* Get bin header */ small[sx] = np; /* Lifo block usage */ if (sp) { /* Bin has content branch */ np->al = sp->al; /* Np left is sp's old left */ sp->al->ar = np; /* Sp's old left points to np */ np->ar = sp; /* Np's right is now sp */ sp->al = np; /* Sp's left is now np */ } else { /* Bin is empty, do magic */ np->al = np; /* One element circular list */ np->ar = np; /* Doubly linked list */ sdata[0].mark = TRUE; /* Take care of tree head */ do { /* Loop to enter marks upward */ sdata[sx].mark = TRUE; /* Mark this bin index */ sx = sdata[sx].parent; /* Go up to parent */ } while (!sdata[sx].mark); /* Parent unmarked, do it too */ } } /*------------------------------ small_find -----------------------------*/ /* Function name: small_find Description: Finds bin closest to required size Date documented: Wednesday 2 April 2008 Documented by: Richard Harter Returned type: size_t Arguments: size_t sx Index of the required size. Abstract: This routine looks for a bin that has blocks closest to the required size. It only finds the bin; it doesn't remove a block from the bin. */ static size_t small_find(size_t sx) { while (!sdata[sx].mark) { /* Ascend loop to find a mark */ sx = sdata[sx].up; /* Go up looking for a mark */ if (!sx) return 0; /* Oops, can't go up */ } while (!small[sx] && sx) { /* Descend while no content */ sx = sdata[sx+1].mark /* Is left child marked? */ ? sx + 1 /* Has a mark, go left */ : sdata[sx].right; /* No left, go right */ } return sx; /* Return best fit size */ } /*------------------------------ small_remove ---------------------------*/ /* Function name: small_remove Description: Removes a node from small using sdata Date documented: Wednesday 2 April 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * sdata Node to be removed. size_t sx Bin index of node. Abstract: This routine removes a node from the small bins. If there more nodes in the bin we delink the node and go away. Otherwise we zero out the entry and erase marks as needed. Note: The case, sx==ssz-2 is a special case, depending on whether the last node is a left or a right. */ static void small_remove(NODE *np, size_t sx) { size_t right; /* Right child, if any */ size_t parent; /* Parent, if needed */ if (np->al != np) { /* Not emptying bin */ np->al->ar = np->ar; /* Node's L pts to node's R */ np->ar->al = np->al; /* Node's R pts to node's L */ small[sx] = np->ar; /* Ensure np is not header */ return; /* All done, go away */ } small[sx] = 0; /* Clear the bin */ do { /* Up until bin with content */ right = sdata[sx].right; /* Get right link, if any */ if (right) { /* Normal case, has right child*/ if (sdata[right].mark) return; /* Right subtree has content */ if (sdata[sx+1 ].mark) return; /* Left subtree has content */ } else if (sx == ssz-2) { /* Special case, next to last */ parent = sdata[sx].parent; /* Get parent to simplify code */ if (sdata[parent].right == sx) { /* Special case, last not right*/ if(sdata[sx].mark) return; /* Final left has content */ } } sdata[sx].mark = FALSE; /* No content, no kids, dead */ if (!sx) return; /* At root, go away */ sx = sdata[sx].parent; /* Dead, go up to parent */ } while (!small[sx]); /* Stop when we find content */ } /*---------------------------- stg_free_slab ----------------------------*/ /* Function name: stg_free_slab Description: Frees the current slab, if permissable Date documented: Monday 10 March 2008 Documented by: Richard Harter Returned type: int Arguments: NODE * np The possibly empty slab Abstract: This routine is called by freespace when the kill slab flag (kslab) is turned on. It checks whether the current block is an empty block. If it is we check if the left boundary is not stgstart. If it is not we delete the slab and its left boundary. If it is we check if the right boundary is not stgend. If it is not we delete the slab and its right boundary. Otherwise we only have one slab left and we do not delete it. The routine returns TRUE (1) if the slab is deleted and FALSE (0) if it is not. */ static int stg_free_slab(NODE * np) { NODE *lp; /* Node of left neighbour */ NODE *rp; /* Node of right neighbour */ int retval = TRUE; /* Return value */ rp = np->sr; /* Get storage right neighbour */ lp = np->sl; /* Get storage left neighbour */ if ((lp->seqno == 1) && (rp->seqno == 1)) { /* Is This an empty slab? */ if (lp->sl) { /* Can we del the left border? */ lp->sl->sr = rp; /* Link last left block to rp */ rp->sl = lp->sl; /* lp and np are now snipped out*/ lp->ar = xfree; /* Put node lp on free node list*/ np->ar = lp; /* Also put np on it too */ } else if (rp->sr) { /* Left no good, howabout right?*/ rp->sr->sl = lp; /* Link last right to lp */ lp->sr = rp->sr; /* rp and np now snipped out */ rp->ar = xfree; /* Put rp on the free node list */ np->ar = rp; /* Also put np on it */ } else retval = FALSE; /* Couldn't kill it */ } else retval = FALSE; /* Not an empty slab */ if (retval) { xfree = np; /* New free list header */ free(np->a-ASIZE); /* Release actual storage */ } return retval; /* Say what happened */ } /*---------------------------- stg_merge_left ---------------------------*/ /* Function name: stg_merge_left Description: This merges a block with its storage left neighbour Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The node being merged with its neighbour Abstract: This routine merges a block with its storage left neighbour (which is assumed to be a free block - this should be checked by the caller). It calls remove_from_free to remove the left neighbour from the free blocks data structure, relinks storage, and puts the now unused node on the free list. */ static void stg_merge_left (NODE * np) /* Merge with left neighbour */ { NODE *lp; /* Left neighbour in link */ lp = np->sl; /* Left storage neighbour */ lp->sl->sr = np; /* Link SL SL to np; */ np->sl = lp->sl; /* Link np to SL SL */ remove_from_free(lp); /* Remove from free blocks DS */ np->a = lp->a; /* Reset address */ lp->ar = xfree; /* Point to top of free list */ xfree = lp; /* Make free list top np */ } /*--------------------------- stg_merge_right ---------------------------*/ /* Function name: stg_merge_right Description: This merges a block with its storage right neighbour Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The node being merged with its neighbour Abstract: This routine merges a block with its storage right neighbour (which is assumed to be a free block - this should be checked by the caller). It calls remove_from_free to remove the right neighbour from the free blocks data structure, relinks storage, and puts the now unused node on the free list. */ static void stg_merge_right(NODE *np) /* Merge with right block */ { NODE *rp; /* Right neighbour in link */ rp = np->sr; /* Right storage neighbour */ rp->sr->sl = np; /* Link SR SR to np; */ np->sr = rp->sr; /* Link np to SR SR */ remove_from_free (rp); /* Remove from free blocks DS */ rp->ar = xfree; /* Point to top of free list */ xfree = rp; /* Make free list top np */ } /*---------------------------- stg_new_slab -----------------------------*/ /* Function name: stg_new_slab Description: Get a new slab (large block of storage) from malloc Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: NODE * Arguments: size_t rsz The requested slab size Abstract: This routine gets a large block of storage from malloc. The request size is at least slabsz bytes although it may be larger. A pointer to the new large free block is returned. */ static NODE * stg_new_slab(size_t rsz) { NODE *np; /* Node of new block */ NODE *oe; /* Node of old stgend */ size_t sz; /* Size to allocate */ char * finial; /* Final check bytes address */ oe = stgend; /* Save the old stgend */ np = get_node(); /* Get node for the space */ np->sl = stgend; /* Left neighbour is stgend */ stgend->sr = np; /* Set right of left */ stgend = get_node(); /* Get node for new stgend */ stgend->sl = np; /* Set left of right */ stgend->sr = 0; /* Null right of right */ stgend->al = 0; /* Clear avail left field */ stgend->ar = 0; /* Clear avail right field */ stgend->seqno = USED; /* Set sequence #, mark used */ stgend->id = LINELOC; /* Enter origin of stgend */ np->sr = stgend; /* Right neighbour is rp */ rsz += 2*ASIZE; /* Allow for check bytes */ sz = (rsza = malloc((unsigned)sz); /* Get space for new block */ if (!np->a) errspace(2,LINELOC,0,rsz);/* Die if no more space */ totstg += sz; /* Add to total managed storage */ if (!(np->a)) return 0; /* Can't get storage */ if (stgstart == oe) { /* Checking for first slab */ stgstart->a = np->a; /* Force 0 size stgstart */ } ENTER_CHECK_BYTES(np->a); /* Load slab with check bytes */ np->a += ASIZE; /* Usable space goes after check*/ stgend->a = np->a + sz - ASIZE; /* Enter terminating address */ finial = stgend->a - ASIZE; /* Address of terminal check */ ENTER_CHECK_BYTES(finial); /* Also put in terminal check */ np->seqno = (seqno += 2) & FREESPACE; /* Mark as being free */ np->id = LINELOC; /* Enter origin of np */ curslab += 1; /* Increase current # of slabs */ maxslab += 1; /* Increase maximum # of slabs */ return np; /* Return np or null if failure */ } /*--------------------------- stg_split_block ---------------------------*/ /* Function name: stg_split_block Description: This rounds up the size as needed Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: void Arguments: NODE * np The block to be split size_t rsz The requested size Abstract: This routine splits a block into two pieces. The left most has the requested size; the right most has the tail space. It is assumed that the block has already been removed from the free lists or, if it is a slab, it was never entered. */ static void stg_split_block(NODE *np, size_t rsz) /* Split storage block */ { NODE *rp; /* Right neighbour in split */ size_t sz; /* Block size */ sz = NODESZ(np); /* Get block size */ rp = get_node(); /* Get node for stg right */ 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 */ rp->seqno = seqno & FREESPACE; /* Enter sequence number */ rp->id = LINELOC; /* Init reqid */ np->sr = rp; /* Right of old is new */ place_in_free(rp); /* Make tail space available */ } /* -------------------------- get_rounded_size ------------------------- */ /* Function name: sz_round_up_size Description: This rounds up the size as needed Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: size_t Arguments: size_t size The requested size Abstract: This routine rounds up the size so that there is enough space for the check bytes and for ASIZE alignment. It also checks that the rounded up size is not "too large". */ static size_t sz_round_up_size (size_t size) /* Round up size, include check */ { size_t rsz; /* Rounded up size */ if (size == 0) errspace(0,0,0,0); /* Zero size illegal */ rsz = (size + (2*ASIZE-1)) & AMASK; /* Get rounded size up */ if (rsz < size) errspace(1,0,0,size); /* Size too big */ return rsz; /* Return rounded up size */ } /* ------------------------- sz_index_for_size ------------------------- */ /* Function name: sz_index_for_size Description: Gets the size index for a rounded up size Date documented: Monday 25 February 2008 Documented by: Richard Harter Returned type: size_t Arguments: size_t sz The requested size Abstract: This routine gets the size index for a request size. The index is used as an index into the array of linked list headers. */ static size_t sz_index_for_size (size_t sz) /* Gets an index value for size */ { size_t sx; /* Found index */ sx = (sz-1)>>NABITS; /* Shift NABITS to get index */ /* Sub -1 makes index 0 based */ if (sx>ssz) sx=ssz; /* Bound if big */ return sx; /* Return index found */ }