src/calBdd/calMem.c File Reference

#include "calMem.h"
Include dependency graph for calMem.c:

Go to the source code of this file.

Data Structures

struct  SegmentStruct
struct  BlockStruct
struct  ListStruct
struct  Cal_RecMgrStruct

Defines

#define MAGIC_COOKIE   0x34f21ab3l
#define MAGIC_COOKIE1   0x432fa13bl
#define HEADER_SIZE   ((Cal_Address_t)CAL_ROUNDUP(sizeof(Block_t)))
#define MAX_SIZEINDEX   (8*sizeof(Cal_Address_t)-2)
#define MAX_SEG_SIZE   ((Cal_Address_t)1 << MAX_SIZEINDEX)
#define MAX_SIZE   ((Cal_Address_t)(MAX_SEG_SIZE-HEADER_SIZE))
#define NICE_BLOCK_SIZE   ((Cal_Address_t)PAGE_SIZE-CAL_ROUNDUP(sizeof(Block_t)))
#define ALLOC_SIZE   NICE_BLOCK_SIZE
#define MIN_ALLOC_SIZEINDEX   15
#define SBRK(size)   ((Cal_Pointer_t)sbrk((long)(size)))

Typedefs

typedef struct BlockStruct * Block
typedef struct BlockStruct Block_t
typedef struct SegmentStruct * Segment
typedef struct SegmentStruct Segment_t
typedef struct ListStruct * List
typedef struct ListStruct List_t
typedef struct Cal_RecMgrStruct Cal_RecMgr_t

Functions

static int CeilingLog2 (Cal_Address_t i)
static int BlockSizeIndex (Cal_Address_t size)
static void AddToFreeList (Block b)
static Block RemoveFromFreeList (Block b)
static Block Buddy (Block b)
static void TrimToSize (Block b, int sizeIndex)
static void MergeAndFree (Block b)
void Cal_MemFatal (char *message)
Cal_Address_t Cal_MemAllocation (void)
Cal_Pointer_t Cal_MemGetBlock (Cal_Address_t size)
void Cal_MemFreeBlock (Cal_Pointer_t p)
Cal_Pointer_t Cal_MemResizeBlock (Cal_Pointer_t p, Cal_Address_t newSize)
Cal_Pointer_t Cal_MemNewRec (Cal_RecMgr mgr)
void Cal_MemFreeRec (Cal_RecMgr mgr, Cal_Pointer_t rec)
Cal_RecMgr Cal_MemNewRecMgr (int size)
void Cal_MemFreeRecMgr (Cal_RecMgr mgr)

Variables

static Cal_Address_t blockAllocation
static Block avail [MAX_SIZEINDEX+1]
static Segment_t dummySeg = {(Cal_Pointer_t)0, (Cal_Address_t)0}
static Segment currSeg = &dummySeg

Define Documentation

#define ALLOC_SIZE   NICE_BLOCK_SIZE

Definition at line 85 of file calMem.c.

#define HEADER_SIZE   ((Cal_Address_t)CAL_ROUNDUP(sizeof(Block_t)))

Definition at line 80 of file calMem.c.

#define MAGIC_COOKIE   0x34f21ab3l

Definition at line 63 of file calMem.c.

#define MAGIC_COOKIE1   0x432fa13bl

Definition at line 64 of file calMem.c.

#define MAX_SEG_SIZE   ((Cal_Address_t)1 << MAX_SIZEINDEX)

Definition at line 82 of file calMem.c.

#define MAX_SIZE   ((Cal_Address_t)(MAX_SEG_SIZE-HEADER_SIZE))

Definition at line 83 of file calMem.c.

#define MAX_SIZEINDEX   (8*sizeof(Cal_Address_t)-2)

Definition at line 81 of file calMem.c.

#define MIN_ALLOC_SIZEINDEX   15

Definition at line 86 of file calMem.c.

#define NICE_BLOCK_SIZE   ((Cal_Address_t)PAGE_SIZE-CAL_ROUNDUP(sizeof(Block_t)))

Definition at line 84 of file calMem.c.

#define SBRK ( size   )     ((Cal_Pointer_t)sbrk((long)(size)))

Definition at line 126 of file calMem.c.

Typedef Documentation

typedef struct BlockStruct* Block

CFile*****************************************************************

FileName [calMem.c]

PackageName [cal]

Synopsis [Routines for memory management.]

Description [Contains allocation, free, resize routines. Also has routines for managing records of fixed size.]

SeeAlso [optional]

Author [Rajeev K. Ranjan (rajeev@eecs.berkeley.edu). Originally written by David Long.]

Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved.

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

Revision [

Id
calMem.c,v 1.4 2002/08/25 05:29:59 fabio Exp

]

Definition at line 51 of file calMem.c.

typedef struct BlockStruct Block_t

Definition at line 52 of file calMem.c.

typedef struct Cal_RecMgrStruct Cal_RecMgr_t

Definition at line 57 of file calMem.c.

typedef struct ListStruct* List

Definition at line 55 of file calMem.c.

typedef struct ListStruct List_t

Definition at line 56 of file calMem.c.

typedef struct SegmentStruct* Segment

Definition at line 53 of file calMem.c.

typedef struct SegmentStruct Segment_t

Definition at line 54 of file calMem.c.

Function Documentation

static void AddToFreeList ( Block  b  )  [static]

Function********************************************************************

Synopsis [required]

Description [AddToFreeList(b) adds b to the appropriate free list. ]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 567 of file calMem.c.

00568 {
00569   int i;
00570 
00571   i=b->sizeIndex;
00572   if (!avail[i]){
00573       b->next=b;
00574       b->prev=b;
00575       avail[i]=b;
00576   }
00577   else {
00578     b->next=avail[i]->next;
00579     avail[i]->next->prev=b;
00580     avail[i]->next=b;
00581     b->prev=avail[i];
00582   }
00583   b->used=0;
00584 }

static int BlockSizeIndex ( Cal_Address_t  size  )  [static]

Function********************************************************************

Synopsis [required]

Description [BlockSizeIndex(size) return the coded size for a block. ]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 535 of file calMem.c.

00536 {
00537   if (size < 1)
00538     return (-1);
00539   if (size > MAX_SIZE)
00540     Cal_MemFatal("BlockSizeIndex: block size too large");
00541   else
00542     size+=HEADER_SIZE;
00543   return (CeilingLog2(size));
00544 }

static Block Buddy ( Block  b  )  [static]

Function********************************************************************

Synopsis [required]

Description [Buddy(b) returns the Buddy block of b, or null if there is no Buddy. ]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 645 of file calMem.c.

00646 {
00647   Cal_Address_t Buddy_offset;
00648 
00649   Buddy_offset=(Cal_Address_t)(((Cal_Address_t)b-(Cal_Address_t)b->seg->baseAddress) ^
00650                                ((Cal_Address_t)1 << b->sizeIndex));
00651   if (Buddy_offset < b->seg->limit)
00652     return ((Block)((Cal_Address_t)b->seg->baseAddress+Buddy_offset));
00653   else
00654     return ((Block)0);
00655 }

Cal_Address_t Cal_MemAllocation ( void   ) 

Function********************************************************************

Synopsis [Returns the memory allocated.]

Description [Returns the memory allocated.]

SideEffects [required]

SeeAlso [optional]

Definition at line 180 of file calMem.c.

00181 {
00182   return (blockAllocation);
00183 }

void Cal_MemFatal ( char *  message  ) 

AutomaticEnd Function********************************************************************

Synopsis [Prints an error message and exits.]

Description [Prints an error message and exits.]

SideEffects [required]

SeeAlso [optional]

Definition at line 162 of file calMem.c.

00163 {
00164   fprintf(stderr, "Memory management library: error: %s\n", message);
00165   exit(1);
00166 }

void Cal_MemFreeBlock ( Cal_Pointer_t  p  ) 

Function********************************************************************

Synopsis [Frees the block.]

Description [Frees the block.]

SideEffects [required]

SeeAlso [optional]

Definition at line 277 of file calMem.c.

00278 {
00279   Block b;
00280 
00281   if (!p) return;
00282   b = (Block) ((Cal_Address_t)p-HEADER_SIZE);
00283   if (!b->used) Cal_MemFatal("Cal_MemFreeBlock: block not in use");
00284   if (b->sizeIndex < 0 || b->sizeIndex > MAX_SIZEINDEX) Cal_MemFatal("Cal_MemFreeBlock: invalid block header");
00285   MergeAndFree(b);
00286 }

void Cal_MemFreeRec ( Cal_RecMgr  mgr,
Cal_Pointer_t  rec 
)

Function********************************************************************

Synopsis [Frees a record managed by the indicated record manager. ]

Description [Frees a record managed by the indicated record manager. ]

SideEffects [required]

SeeAlso [optional]

Definition at line 412 of file calMem.c.

00413 {
00414 #if defined(DEBUG_MEM)
00415   if (mgr->size >= sizeof(long)+sizeof(List_t))
00416     if (*(long *)(sizeof(List_t)+(Cal_Address_t)rec) == MAGIC_COOKIE)
00417       fprintf(stderr, "record at 0x%lx may already be freed\n", (Cal_Address_t)rec);
00418 #endif
00419   ((List)rec)->next=mgr->free;
00420 #if defined(DEBUG_MEM)
00421   if (mgr->size >= sizeof(long)+sizeof(List_t))
00422     *(long *)(sizeof(List_t)+(Cal_Address_t)rec)=MAGIC_COOKIE;
00423 #endif
00424   mgr->free=(List)rec;
00425 }

void Cal_MemFreeRecMgr ( Cal_RecMgr  mgr  ) 

Function********************************************************************

Synopsis [Frees all the storage associated with the specified record manager.]

Description [Frees all the storage associated with the specified record manager.]

SideEffects [required]

SeeAlso [optional]

Definition at line 470 of file calMem.c.

00471 {
00472   List p, q;
00473   for (p=mgr->blocks; p; p=q){
00474     q=p->next;
00475     Cal_MemFreeBlock((Cal_Pointer_t)p);
00476   }
00477   Cal_MemFreeBlock((Cal_Pointer_t)mgr);
00478 }

Cal_Pointer_t Cal_MemGetBlock ( Cal_Address_t  size  ) 

Function********************************************************************

Synopsis [Allocates a new block of the specified size.]

Description [Allocates a new block of the specified size.]

SideEffects [required]

SeeAlso [optional]

Definition at line 197 of file calMem.c.

00198 {
00199   int i;
00200   int sizeIndex;
00201   int allocSizeIndex;
00202   int newSeg;
00203   Cal_Address_t allocSize;
00204   Cal_Pointer_t sbrkRet;
00205   Block b;
00206 
00207   if ((sizeIndex = BlockSizeIndex(size)) < 0) return ((Cal_Pointer_t)0);
00208   
00209   /* Find smallest free block which is large enough. */
00210   for (i = sizeIndex; i <= MAX_SIZEINDEX && !avail[i]; ++i);
00211   if (i > MAX_SIZEINDEX) {
00212     /* We must get more storage; don't allocate less than */
00213     /* 2^MIN_ALLOC_SIZE_INDEX */
00214     if (sizeIndex < MIN_ALLOC_SIZEINDEX) allocSizeIndex=MIN_ALLOC_SIZEINDEX;
00215     else allocSizeIndex=sizeIndex;
00216     allocSize=((Cal_Address_t)1 << allocSizeIndex);
00217     
00218     /* Pad current segment to be a multiple of 2^allocSizeIndex in */
00219     /* length. */
00220     allocSize += ((currSeg->limit + allocSize - 1) &
00221                   ~(allocSize - 1)) - currSeg->limit;
00222     if ((sbrkRet=(Cal_Pointer_t)SBRK(0)) !=
00223         (Cal_Pointer_t)((Cal_Address_t)currSeg->baseAddress+currSeg->limit) || 
00224         allocSize+currSeg->limit > MAX_SEG_SIZE) {
00225       
00226       /* Segment is too large or someone else has moved the break. */
00227       /* Pad to get to appropriate boundary. */
00228       allocSize=CAL_ROUNDUP((Cal_Address_t)sbrkRet)-(Cal_Address_t)sbrkRet;
00229       
00230       /* Pad allocation request with storage for new segment */
00231       /* information and indicate that a new segment must be */
00232         /* created. */
00233       allocSize+=((Cal_Address_t)1 << allocSizeIndex)+CAL_ROUNDUP(sizeof(Segment_t));
00234       newSeg=1;
00235     }
00236     else newSeg=0;
00237     sbrkRet=(Cal_Pointer_t)SBRK(allocSize);
00238     if (sbrkRet == (Cal_Pointer_t) -1) Cal_MemFatal("Cal_MemGetBlock: allocation failed");
00239     blockAllocation += allocSize;
00240     if (newSeg){
00241       currSeg = (Segment) CAL_ROUNDUP((Cal_Address_t)sbrkRet);
00242       currSeg->baseAddress=(Cal_Pointer_t)((Cal_Address_t)currSeg+CAL_ROUNDUP(sizeof(Segment_t)));
00243       currSeg->limit=0;
00244       /* Readjust allocation size. */
00245       allocSize=(1l << allocSizeIndex);
00246       }
00247     /* Carve allocated space up into blocks and add to free lists. */
00248     while (allocSize){
00249       size = allocSize - (allocSize & (allocSize-1));
00250       b = (Block) ((Cal_Address_t)currSeg->baseAddress+currSeg->limit);
00251       b->sizeIndex = CeilingLog2(size);
00252       b->seg = currSeg;
00253       AddToFreeList(b);
00254         currSeg->limit += size;
00255         allocSize -= size;
00256     }
00257     /* Find free block of appropriate size. */
00258     for (i=sizeIndex; i <= MAX_SIZEINDEX && !avail[i]; ++i);
00259   }
00260   b = RemoveFromFreeList(avail[i]);
00261   TrimToSize(b, sizeIndex);
00262   return ((Cal_Pointer_t)((Cal_Address_t)b + HEADER_SIZE));
00263 }

Cal_Pointer_t Cal_MemNewRec ( Cal_RecMgr  mgr  ) 

Function********************************************************************

Synopsis [Allocates a record from the specified record manager. ]

Description [Allocates a record from the specified record manager. ]

SideEffects [required]

SeeAlso [optional]

Definition at line 355 of file calMem.c.

00356 {
00357   int i;
00358   Cal_Pointer_t p;
00359   List new_;
00360   
00361   if (!mgr->free) {
00362     /* Allocate a new block. */
00363     new_ = (List) Cal_MemGetBlock(ALLOC_SIZE);
00364     mgr->numBlocks++;
00365     new_->next=mgr->blocks;
00366     mgr->blocks=new_;
00367     mgr->free=(List)((Cal_Address_t)new_+CAL_ROUNDUP(sizeof(List_t)));
00368     p=(Cal_Pointer_t)(mgr->free);
00369     /* Carve the block into pieces. */
00370     for (i=1; i < mgr->recsPerBlock; ++i) {
00371       ((List)p)->next=(List)((Cal_Address_t)p+mgr->size);
00372 #if defined(DEBUG_MEM)
00373       if (mgr->size >= sizeof(long)+sizeof(List_t))
00374         *(long *)(sizeof(List_t)+(Cal_Address_t)p)=MAGIC_COOKIE;
00375 #endif
00376       p=(Cal_Pointer_t)((Cal_Address_t)p+mgr->size);
00377     }
00378     ((List)p)->next=0;
00379 #if defined(DEBUG_MEM)
00380     if (mgr->size >= sizeof(long)+sizeof(List_t)){
00381       *(long *)(sizeof(List_t)+(Cal_Address_t)p)=MAGIC_COOKIE;
00382     }
00383 #endif
00384   }
00385   new_ = mgr->free;
00386 #if defined(DEBUG_MEM)
00387   if (mgr->size >= sizeof(long)+sizeof(List_t)){
00388     if (*(long *)(sizeof(List_t)+(Cal_Address_t)new_) != MAGIC_COOKIE)
00389       fprintf(stderr, "record at 0x%lx may be in use\n", (Cal_Address_t)new_);
00390     else
00391       *(long *)(sizeof(struct
00392                        list_)+(Cal_Address_t)new)=MAGIC_COOKIE1;
00393   }
00394 #endif
00395   mgr->free = mgr->free->next;
00396   return ((Cal_Pointer_t)new_);
00397 }

Cal_RecMgr Cal_MemNewRecMgr ( int  size  ) 

Function********************************************************************

Synopsis [Creates a new record manager with the given record size.]

Description [Creates a new record manager with the given record size.]

SideEffects [required]

SeeAlso [optional]

Definition at line 441 of file calMem.c.

00442 {
00443   Cal_RecMgr mgr;
00444 
00445   if (size < sizeof(List_t)) size=sizeof(List_t);
00446   size=CAL_ROUNDUP(size);
00447   if (size > ALLOC_SIZE-CAL_ROUNDUP(sizeof(List_t)))
00448     Cal_MemFatal("Cal_MemNewRecMgr: record size too large");
00449   mgr = (Cal_RecMgr)Cal_MemGetBlock((Cal_Address_t)sizeof(Cal_RecMgr_t));
00450   mgr->size=size;
00451   mgr->recsPerBlock=(ALLOC_SIZE-CAL_ROUNDUP(sizeof(List_t)))/size;
00452   mgr->free=0;
00453   mgr->blocks=0;
00454   mgr->numBlocks = 0;
00455   return (mgr);
00456 }

Cal_Pointer_t Cal_MemResizeBlock ( Cal_Pointer_t  p,
Cal_Address_t  newSize 
)

Function********************************************************************

Synopsis [Expands or contracts the block to a new size. We try to avoid moving the block if possible. ]

Description [Expands or contracts the block to a new size. We try to avoid moving the block if possible. ]

SideEffects [required]

SeeAlso [optional]

Definition at line 304 of file calMem.c.

00305 {
00306   int newSizeIndex;
00307   Block b;
00308   Block bb;
00309   Cal_Pointer_t q;
00310   Cal_Address_t oldSize;
00311 
00312   if (!p) return (Cal_MemGetBlock(newSize));
00313   b = (Block) ((Cal_Address_t)p - HEADER_SIZE);
00314   if (!b->used) Cal_MemFatal("Cal_MemResizeBlock: block not in use");
00315   if (b->sizeIndex < 0 || b->sizeIndex > MAX_SIZEINDEX){
00316     Cal_MemFatal("Cal_MemResizeBlock: invalid block header");
00317   }
00318   if ((newSizeIndex = BlockSizeIndex(newSize)) < 0){
00319     Cal_MemFreeBlock(p);
00320     return ((Cal_Pointer_t)0);
00321   }
00322   if (b->sizeIndex >= newSizeIndex){
00323     /* Shrink block. */
00324     TrimToSize(b, newSizeIndex);
00325     return (p);
00326   }
00327   oldSize=(1l << b->sizeIndex) - HEADER_SIZE;
00328   /* Try to expand by adding buddies at higher addresses. */
00329   for (bb=Buddy(b);
00330        bb && (Cal_Address_t)b < (Cal_Address_t)bb && !bb->used && bb->sizeIndex == b->sizeIndex;
00331        bb=Buddy(b)) {
00332     RemoveFromFreeList(bb);
00333     if (++(b->sizeIndex) == newSizeIndex) return (p);
00334   }
00335   /* Couldn't expand all the way to needed size; allocate a new block */
00336   /* and move the contents of the old one. */
00337   q = (Cal_Pointer_t) Cal_MemGetBlock(newSize);
00338   Cal_MemCopy(q, p, oldSize);
00339   MergeAndFree(b);
00340   return (q);
00341 }

static int CeilingLog2 ( Cal_Address_t  i  )  [static]

AutomaticStart

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 506 of file calMem.c.

00507 {
00508   Cal_Address_t j;
00509   int result;
00510 
00511   for (result=0, j=1; j < i; ++result, j*=2);
00512   return (result);
00513 }

static void MergeAndFree ( Block  b  )  [static]

Function********************************************************************

Synopsis [required]

Description [MergeAndFree(b) repeatedly merges b its Buddy until b has no Buddy or the Buddy isn't free, then adds the result to the appropriate free list. ]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 712 of file calMem.c.

00713 {
00714   Block bb;
00715   
00716   for (bb=Buddy(b); bb && !bb->used && bb->sizeIndex == b->sizeIndex;
00717        bb=Buddy(b)) { 
00718     RemoveFromFreeList(bb);
00719     if ((Cal_Address_t)bb < (Cal_Address_t)b) b=bb;
00720     b->sizeIndex++;
00721   }
00722   AddToFreeList(b);
00723 }

static Block RemoveFromFreeList ( Block  b  )  [static]

Function********************************************************************

Synopsis [required]

Description [RemoveFromFreeList(b) removes b from the free list which it is on. ]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 607 of file calMem.c.

00608 {
00609   int i;
00610 
00611   i=b->sizeIndex;
00612   if (b->next == b)
00613     avail[i]=0;
00614   else {
00615     b->next->prev=b->prev;
00616     b->prev->next=b->next;
00617     if (avail[i] == b) avail[i]=b->next;
00618   }
00619   b->used=1;
00620   return (b);
00621 }

static void TrimToSize ( Block  b,
int  sizeIndex 
) [static]

Function********************************************************************

Synopsis [required]

Description [TrimToSize(b, sizeIndex) repeatedly splits b until it has the indicated size. Blocks which are split off are added to the appropriate free list. ]

SideEffects [required]

SeeAlso [optional]

CommandName [optional]

CommandSynopsis [optional]

CommandArguments [optional]

CommandDescription [optional]

Definition at line 678 of file calMem.c.

00679 {
00680   Block bb;
00681 
00682   while (b->sizeIndex > sizeIndex) {
00683     b->sizeIndex--;
00684     bb=Buddy(b);
00685     bb->sizeIndex=b->sizeIndex;
00686     bb->seg=b->seg;
00687     AddToFreeList(bb);
00688   }
00689 }

Variable Documentation

Block avail[MAX_SIZEINDEX+1] [static]

Definition at line 111 of file calMem.c.

Cal_Address_t blockAllocation [static]

Definition at line 110 of file calMem.c.

Segment currSeg = &dummySeg [static]

Definition at line 121 of file calMem.c.

Segment_t dummySeg = {(Cal_Pointer_t)0, (Cal_Address_t)0} [static]

Definition at line 116 of file calMem.c.

Generated on Tue Jan 12 13:57:12 2010 for glu-2.2 by  doxygen 1.6.1