glu-2.2: src/calBdd/calMem.c Source File

00001 
00040 #if HAVE_UNISTD_H
00041 #include <unistd.h>
00042 #endif
00043 #if STDC_HEADERS
00044 #include <stdlib.h>
00045 #include <string.h>
00046 #endif
00047 #include "calMem.h"
00048 /*---------------------------------------------------------------------------*/
00049 /* Type declarations                                                         */
00050 /*---------------------------------------------------------------------------*/
00051 typedef struct BlockStruct *Block;
00052 typedef struct BlockStruct Block_t;
00053 typedef struct SegmentStruct *Segment;
00054 typedef struct SegmentStruct Segment_t;
00055 typedef struct ListStruct *List;
00056 typedef struct ListStruct List_t;
00057 typedef struct Cal_RecMgrStruct Cal_RecMgr_t;
00058 
00059 /*---------------------------------------------------------------------------*/
00060 /* Constant declarations                                                     */
00061 /*---------------------------------------------------------------------------*/
00062 /* #define DEBUG_MEM */
00063 #define MAGIC_COOKIE 0x34f21ab3l
00064 #define MAGIC_COOKIE1 0x432fa13bl
00065 struct SegmentStruct
00066 {
00067   Cal_Pointer_t baseAddress;
00068   Cal_Address_t limit;
00069 };
00070 
00071 struct BlockStruct
00072 {
00073   int used;
00074   int sizeIndex;
00075   unsigned long dummy;
00076   Block_t *next;
00077   Block_t *prev;
00078   Segment seg;
00079 };
00080 #define HEADER_SIZE ((Cal_Address_t)CAL_ROUNDUP(sizeof(Block_t)))
00081 #define MAX_SIZEINDEX (8*sizeof(Cal_Address_t)-2)
00082 #define MAX_SEG_SIZE ((Cal_Address_t)1 << MAX_SIZEINDEX)
00083 #define MAX_SIZE ((Cal_Address_t)(MAX_SEG_SIZE-HEADER_SIZE))
00084 #define NICE_BLOCK_SIZE ((Cal_Address_t)PAGE_SIZE-CAL_ROUNDUP(sizeof(Block_t)))
00085 #define ALLOC_SIZE NICE_BLOCK_SIZE
00086 #define MIN_ALLOC_SIZEINDEX 15
00087 
00088 
00089 /*---------------------------------------------------------------------------*/
00090 /* Stucture declarations                                                     */
00091 /*---------------------------------------------------------------------------*/
00092 struct ListStruct
00093 {
00094   List_t *next;
00095 };
00096 
00097 struct Cal_RecMgrStruct
00098 {
00099   int size;
00100   int recsPerBlock;
00101   List free;
00102   List blocks;
00103   int numBlocks;
00104 };
00105 
00106 
00107 /*---------------------------------------------------------------------------*/
00108 /* Variable declarations                                                     */
00109 /*---------------------------------------------------------------------------*/
00110 static Cal_Address_t blockAllocation;
00111 static Block avail[MAX_SIZEINDEX+1];
00112 
00113 
00114 /* Bogus segment for initialization */
00115 
00116 static Segment_t dummySeg={(Cal_Pointer_t)0, (Cal_Address_t)0};
00117 
00118 
00119 /* Current segment */
00120 
00121 static Segment currSeg= &dummySeg;
00122 
00123 /*---------------------------------------------------------------------------*/
00124 /* Macro declarations                                                        */
00125 /*---------------------------------------------------------------------------*/
00126 #define SBRK(size) ((Cal_Pointer_t)sbrk((long)(size)))
00127 
00130 /*---------------------------------------------------------------------------*/
00131 /* Static function prototypes                                                */
00132 /*---------------------------------------------------------------------------*/
00133 
00134 static int CeilingLog2(Cal_Address_t i);
00135 static int BlockSizeIndex(Cal_Address_t size);
00136 static void AddToFreeList(Block b);
00137 static Block RemoveFromFreeList(Block b);
00138 static Block Buddy(Block b);
00139 static void TrimToSize(Block b, int sizeIndex);
00140 static void MergeAndFree(Block b);
00141 
00144 /*---------------------------------------------------------------------------*/
00145 /* Definition of exported functions                                          */
00146 /*---------------------------------------------------------------------------*/
00147 
00148 
00149 
00161 void
00162 Cal_MemFatal(char *message)
00163 {
00164   fprintf(stderr, "Memory management library: error: %s\n", message);
00165   exit(1);
00166 }
00167 
00179 Cal_Address_t
00180 Cal_MemAllocation(void)
00181 {
00182   return (blockAllocation);
00183 }
00184 
00196 Cal_Pointer_t
00197 Cal_MemGetBlock(Cal_Address_t size)
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 }
00264 
00265 void
00277 Cal_MemFreeBlock(Cal_Pointer_t p)
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 }
00287 
00288 
00289 
00303 Cal_Pointer_t
00304 Cal_MemResizeBlock(Cal_Pointer_t p, Cal_Address_t newSize)
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 }
00342 
00354 Cal_Pointer_t
00355 Cal_MemNewRec(Cal_RecMgr mgr)
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 }
00398 
00399 
00411 void
00412 Cal_MemFreeRec(Cal_RecMgr mgr, Cal_Pointer_t rec)
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 }
00426 
00427 
00428 
00440 Cal_RecMgr
00441 Cal_MemNewRecMgr(int size)
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 }
00457 
00469 void
00470 Cal_MemFreeRecMgr(Cal_RecMgr mgr)
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 }
00479 
00480 /*---------------------------------------------------------------------------*/
00481 /* Definition of internal functions                                          */
00482 /*---------------------------------------------------------------------------*/
00483 /*---------------------------------------------------------------------------*/
00484 /* Definition of static functions                                          */
00485 /*---------------------------------------------------------------------------*/
00505 static int
00506 CeilingLog2(Cal_Address_t i)
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 }
00514 
00534 static int
00535 BlockSizeIndex(Cal_Address_t size)
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 }
00545 
00546 
00566 static void
00567 AddToFreeList(Block b)
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 }
00585 
00586 
00606 static Block
00607 RemoveFromFreeList(Block b)
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 }
00622 
00623 
00644 static Block
00645 Buddy(Block b)
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 }
00656 
00657 
00677 static void
00678 TrimToSize(Block b, int sizeIndex)
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 }
00690 
00691 
00711 static void
00712 MergeAndFree(Block b)
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 }