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

00001 
00043 #include "malloc.h"
00044 #include "calInt.h"
00045 
00046 /*---------------------------------------------------------------------------*/
00047 /* Constant declarations                                                     */
00048 /*---------------------------------------------------------------------------*/
00049 
00050 /*---------------------------------------------------------------------------*/
00051 /* Type declarations                                                         */
00052 /*---------------------------------------------------------------------------*/
00053 
00054 
00055 /*---------------------------------------------------------------------------*/
00056 /* Stucture declarations                                                     */
00057 /*---------------------------------------------------------------------------*/
00058 
00059 /*---------------------------------------------------------------------------*/
00060 /* Variable declarations                                                     */
00061 /*---------------------------------------------------------------------------*/
00062 
00063 
00064 /*---------------------------------------------------------------------------*/
00065 /* Macro declarations                                                        */
00066 /*---------------------------------------------------------------------------*/
00067 #ifndef HAVE_VALLOC
00068 #define __NOVALLOC__
00069 #else
00070 #if HAVE_VALLOC != 1
00071 #define __NOVALLOC__
00072 #endif
00073 #endif
00074 
00077 /*---------------------------------------------------------------------------*/
00078 /* Static function prototypes                                                */
00079 /*---------------------------------------------------------------------------*/
00080 
00081 static int PageManagerExpandStorage(CalPageManager_t * pageManager);
00082 static CalAddress_t * PageAlign(CalAddress_t * p);
00083 static int SegmentToPageList(CalAddress_t * segment, int numPages, CalAddress_t * lastPointer);
00084 
00087 /*
00088  * object: pageManager
00089  * operations: Init, Quit, AllocPage, FreePage, Print
00090  */
00091 
00092 
00093 /*---------------------------------------------------------------------------*/
00094 /* Definition of exported functions                                          */
00095 /*---------------------------------------------------------------------------*/
00096 
00097 /*---------------------------------------------------------------------------*/
00098 /* Definition of internal functions                                          */
00099 /*---------------------------------------------------------------------------*/
00113 CalPageManager_t *
00114 CalPageManagerInit(int numPagesPerSegment)
00115 {
00116   CalPageManager_t *pageManager;
00117   pageManager = Cal_MemAlloc(CalPageManager_t, 1);
00118   pageManager->totalNumPages = 0;
00119   pageManager->numSegments = 0;
00120   pageManager->numPagesPerSegment = numPagesPerSegment;
00121   pageManager->maxNumSegments = MAX_NUM_SEGMENTS;
00122   pageManager->pageSegmentArray 
00123       = Cal_MemAlloc(CalAddress_t *, pageManager->maxNumSegments);
00124   pageManager->numPagesArray 
00125       = Cal_MemAlloc(int, pageManager->maxNumSegments);
00126   pageManager->freePageList = Cal_Nil(CalAddress_t);
00127   if(PageManagerExpandStorage(pageManager) == FALSE){
00128     Cal_MemFree(pageManager->pageSegmentArray);
00129     Cal_MemFree(pageManager);
00130     return Cal_Nil(CalPageManager_t);
00131   }
00132   return pageManager;
00133 }
00134 
00135 
00149 int
00150 CalPageManagerQuit(
00151   CalPageManager_t * pageManager)
00152 {
00153   int i;
00154   if(pageManager == Cal_Nil(CalPageManager_t)){
00155     return 1;
00156   }
00157   for(i = 0; i < pageManager->numSegments; i++){
00158     free(pageManager->pageSegmentArray[i]);
00159   }
00160   Cal_MemFree(pageManager->pageSegmentArray);
00161   Cal_MemFree(pageManager->numPagesArray);
00162   Cal_MemFree(pageManager);
00163   return 0;
00164 }
00165 
00166 
00180 void
00181 CalPageManagerPrint(
00182   CalPageManager_t * pageManager)
00183 {
00184   int i;
00185   CalAddress_t *page;
00186   printf("****************** pageManager ********************\n");
00187   printf("allocationList:\n");
00188   for(i = 0; i < pageManager->numSegments; i++){
00189     page = pageManager->pageSegmentArray[i];
00190     printf("%lx%c", (CalAddress_t)page, (i+1)%5?' ':'\n');
00191   }
00192   printf("\n");
00193   printf("freePageList:\n");
00194   i = 0;
00195   page = pageManager->freePageList;
00196   while(page){
00197     printf("%lx%c", (CalAddress_t)page, (i+1)%5?' ':'\n');
00198     i++;
00199     page = (CalAddress_t *)*page;
00200   }
00201   printf("\n");
00202 }
00203 
00204 
00218 CalNodeManager_t *
00219 CalNodeManagerInit(CalPageManager_t * pageManager)
00220 {
00221   CalNodeManager_t *nodeManager;
00222   nodeManager = Cal_MemAlloc(CalNodeManager_t, 1);
00223   nodeManager->freeNodeList = Cal_Nil(CalBddNode_t);
00224   nodeManager->pageManager = pageManager;
00225   nodeManager->numPages = 0;
00226   nodeManager->maxNumPages = 10;
00227   nodeManager->pageList = Cal_MemAlloc(CalAddress_t *,
00228                                         nodeManager->maxNumPages);
00229   return nodeManager;
00230 }
00231 
00232 
00246 int
00247 CalNodeManagerQuit(CalNodeManager_t * nodeManager)
00248 {
00249   if(nodeManager == Cal_Nil(CalNodeManager_t)){
00250     return 1;
00251   }
00252   else{
00253     int i;
00254     for (i = 0; i < nodeManager->numPages; i++){
00255       CalPageManagerFreePage(nodeManager->pageManager,
00256                              nodeManager->pageList[i]);
00257     }
00258     Cal_MemFree(nodeManager->pageList);
00259     Cal_MemFree(nodeManager);
00260     return 0;
00261   }
00262 }
00263 
00264 
00265 
00279 void
00280 CalNodeManagerPrint(
00281   CalNodeManager_t * nodeManager)
00282 {
00283   int i;
00284   CalBddNode_t *node;
00285   printf("****************** nodeManager ********************\n");
00286   printf("freeNodeList:\n");
00287   i = 0;
00288   node = nodeManager->freeNodeList;
00289   while(node){
00290     printf("%lx%c", (CalAddress_t)node, (i+1)%5?' ':'\n');
00291     i++;
00292     node = node->nextBddNode;
00293   }
00294   printf("\n");
00295 }
00296 
00297 
00311 CalAddress_t *
00312 CalPageManagerAllocPage(CalPageManager_t * pageManager)
00313 {
00314   CalAddress_t *page;
00315   char buffer[512];
00316   if(pageManager->freePageList == Cal_Nil(CalAddress_t)){
00317     if(PageManagerExpandStorage(pageManager) == FALSE){
00318       sprintf(buffer,
00319               "out of memory : Number of pages allocated = %d\n", 
00320               pageManager->totalNumPages);
00321       CalBddFatalMessage(buffer);
00322     }
00323   }
00324   page = pageManager->freePageList;
00325   pageManager->freePageList = (CalAddress_t *)*page;
00326   return page;
00327 }
00328 
00329 /*---------------------------------------------------------------------------*/
00330 /* Definition of static functions                                            */
00331 /*---------------------------------------------------------------------------*/
00332 
00346 void
00347 CalPageManagerFreePage(CalPageManager_t * pageManager, CalAddress_t * page)
00348 {
00349   *page = (CalAddress_t)(pageManager->freePageList);
00350   pageManager->freePageList = page;
00351 }
00352 
00353 
00373 static int
00374 PageManagerExpandStorage(CalPageManager_t * pageManager)
00375 {
00376   CalAddress_t *p;
00377   CalAddress_t *segment;
00378   int numUsefulPages;
00379 
00380   int numPagesPerSegment = pageManager->numPagesPerSegment;
00381 
00382 #ifdef __NOVALLOC__
00383   p = (CalAddress_t *) malloc(numPagesPerSegment*PAGE_SIZE);
00384 #else
00385   p = (CalAddress_t *) valloc(numPagesPerSegment*PAGE_SIZE);
00386 #endif
00387   /* Just check the page boundary correctness */
00388   Cal_Assert(((CalAddress_t)p & ((1 << LG_PAGE_SIZE)-1)) == 0);
00389   if(p == Cal_Nil(CalAddress_t)){
00390     numPagesPerSegment = numPagesPerSegment / 2;
00391     if(numPagesPerSegment < MIN_NUM_PAGES_PER_SEGMENT){
00392       return FALSE;
00393     }
00394     pageManager->numPagesPerSegment = numPagesPerSegment;
00395     return PageManagerExpandStorage(pageManager);  
00396   }
00397 
00398 #ifdef __NOVALLOC__
00399   /* No need to do it anymore, since I am using valloc */
00400   /* align the memory segment to a page boundary */
00401   segment = PageAlign(p);  
00402 
00403   /* if memory segment is already page aligned, all pages in the memory
00404    * segment are useful, otherwise, one page is wasted
00405    */
00406   if(segment == p){
00407     numUsefulPages = numPagesPerSegment;
00408   }
00409   else{
00410     numUsefulPages = numPagesPerSegment - 1;
00411   }
00412 #else
00413   segment = p;
00414   numUsefulPages = numPagesPerSegment;
00415 #endif
00416   
00417   /* Initialize the pages  */
00418   memset((char *)segment, 0, numUsefulPages*PAGE_SIZE);
00419 
00420   /* Keep track of the number of pages allocated */
00421   pageManager->totalNumPages += numUsefulPages;
00422   
00423   /* increase the size of the allocation list if neccessary */
00424   if(pageManager->numSegments == pageManager->maxNumSegments){
00425     pageManager->maxNumSegments = pageManager->maxNumSegments * 2;
00426     pageManager->pageSegmentArray = Cal_MemRealloc(CalAddress_t *,
00427                                                    pageManager->pageSegmentArray, 
00428                                                    pageManager->maxNumSegments);
00429     pageManager->numPagesArray = Cal_MemRealloc(int,
00430                                                 pageManager->numPagesArray, 
00431                                                 pageManager->maxNumSegments);
00432     
00433   }
00434 
00435   pageManager->pageSegmentArray[pageManager->numSegments] = p;
00436   pageManager->numPagesArray[pageManager->numSegments++] =
00437       numUsefulPages;
00438   
00439   SegmentToPageList(segment, numUsefulPages, pageManager->freePageList);
00440   pageManager->freePageList = segment;
00441   return TRUE;
00442 }
00443 
00444 
00459 static CalAddress_t *
00460 PageAlign(
00461   CalAddress_t * p)
00462 {
00463   if((CalAddress_t)p & (PAGE_SIZE - 1)){
00464     p = (CalAddress_t *)( (CalAddress_t)p >> LG_PAGE_SIZE );
00465     p = (CalAddress_t *)( ((CalAddress_t)p << LG_PAGE_SIZE) + PAGE_SIZE );
00466   }
00467   return p;
00468 }
00469 
00470 
00486 static int
00487 SegmentToPageList(CalAddress_t * segment,
00488                   int  numPages,
00489                   CalAddress_t * lastPointer)
00490 {
00491   int i;
00492   unsigned long thisPageOffset, nextPageOffset;
00493 
00494   if(numPages > 0){
00495     for(i = 0; i < numPages - 1; i++){
00496       thisPageOffset = (i<<LG_PAGE_SIZE)/sizeof(CalAddress_t);
00497       nextPageOffset = ((i+1)<<LG_PAGE_SIZE)/sizeof(CalAddress_t);
00498       *(segment + thisPageOffset) =
00499           (CalAddress_t)(segment + nextPageOffset);
00500     }
00501     thisPageOffset = ((numPages - 1)<<LG_PAGE_SIZE)/sizeof(CalAddress_t);
00502     *(segment + thisPageOffset) = (CalAddress_t)lastPointer;
00503   }
00504   else{
00505     CalBddFatalMessage("out of memory");
00506   }
00507   return 0;
00508 }
00509 
00510 
00511 /*---------------------------------------------------------------------------*/
00512 /* Module Testing                                                            */
00513 /*---------------------------------------------------------------------------*/
00514 #ifdef PAGE_MANAGER
00515 main(argc, argv)
00516 int argc;
00517 char **argv;
00518 {
00519   CalPageManager_t *pageManager;
00520   CalAddress_t *page, *pageArray[10];
00521   int i;
00522 
00523   pageManager = CalPageManagerInit();
00524   CalPageManagerPrint(pageManager);
00525 
00526   page = CalPageManagerAllocPage(pageManager);
00527   printf("PAGE - %x\n", (CalAddress_t)page);
00528   CalPageManagerPrint(pageManager);
00529 
00530   PageManagerFreePage(pageManager, page);
00531   CalPageManagerPrint(pageManager);
00532 
00533   printf("Cal_MemAllocATING PAGES\n");
00534   for(i = 0; i < 10; i++){
00535     pageArray[i] = CalPageManagerAllocPage(pageManager);
00536     CalPageManagerPrint(pageManager);
00537     printf("\n");
00538   }
00539   printf("\n");
00540 
00541   printf("FREEING PAGES\n");
00542   for(i = 0; i < 10; i++){
00543     PageManagerFreePage(pageManager, pageArray[i] );
00544     CalPageManagerPrint(pageManager);
00545     printf("\n");
00546   }    
00547   printf("\n");
00548   CalPageManagerQuit(pageManager);
00549 }
00550 #endif
00551 
00552 #ifdef NODE_MANAGER
00553 main(argc, argv)
00554 int argc;
00555 char **argv;
00556 {
00557   CalPageManager_t *pageManager;
00558   CalNodeManager_t *nodeManagerArray[5], *nodeManager;
00559   CalBddNode_t *node, *nodeArray[5][10];
00560   int numNodeManagers = 5;
00561   int numNodes = 10;
00562   int i,j;
00563   
00564 
00565   pageManager = CalPageManagerInit();
00566   /*CalNodeManagerPrint(nodeManager);*/
00567 
00568   printf("Allocating Nodes\n");
00569   for(i = 0; i < numNodeManagers; i++){
00570     nodeManagerArray[i] = CalNodeManagerInit(pageManager);
00571     for (j=0; j < numNodes; j++){
00572       CalNodeManagerAllocNode(nodeManagerArray[i], nodeArray[i][j]);
00573       CalBddNodePutRefCount(nodeArray[i][j], i+j);
00574     }
00575   }
00576   for(i = 0; i < numNodeManagers; i++){
00577     printf("i = %3d\n", i);
00578     for (j=0; j < numNodes; j++){
00579       CalBddNodePrint(nodeArray[i][j]);
00580     }
00581     printf("\n");
00582   }
00583 
00584   printf("FREEING NODES\n");
00585   for(i = 0; i < numNodeManagers; i++){
00586     for(j = 0; j < numNodes; j++){
00587       CalNodeManagerFreeNode(nodeManagerArray[i], nodeArray[i][j] );
00588     }    
00589     CalNodeManagerQuit(nodeManagerArray[i]);
00590   }
00591   CalPageManagerQuit(pageManager);
00592 }
00593 #endif