src/calBdd/calMemoryManagement.c File Reference

#include "malloc.h"
#include "calInt.h"

Include dependency graph for calMemoryManagement.c:

Defines
#define	__NOVALLOC__
Functions
static int	PageManagerExpandStorage (CalPageManager_t *pageManager)
static CalAddress_t *	PageAlign (CalAddress_t *p)
static int	SegmentToPageList (CalAddress_t segment, int numPages, CalAddress_t lastPointer)
CalPageManager_t *	CalPageManagerInit (int numPagesPerSegment)
int	CalPageManagerQuit (CalPageManager_t *pageManager)
void	CalPageManagerPrint (CalPageManager_t *pageManager)
CalNodeManager_t *	CalNodeManagerInit (CalPageManager_t *pageManager)
int	CalNodeManagerQuit (CalNodeManager_t *nodeManager)
void	CalNodeManagerPrint (CalNodeManager_t *nodeManager)
CalAddress_t *	CalPageManagerAllocPage (CalPageManager_t *pageManager)
void	CalPageManagerFreePage (CalPageManager_t pageManager, CalAddress_t page)

Define Documentation

#define __NOVALLOC__

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

FileName [calMemoryManagement.c]

PackageName [cal]

Synopsis [Special memory management routines specific to CAL.]

Description [Functions for managing the system memory using a set of nodeManagers. Each nodeManager manages a set of fixed size nodes obtained from a set of pages. When additional memory is required, nodeManager obtains a new page from the pageManager. The new page is divided into ( PAGE_SIZE/NODE_SIZE ) number of nodes.]

SeeAlso []

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: calMemoryManagement.c,v 1.6 2005/04/30 01:50:53 fabio Exp

]

Definition at line 68 of file calMemoryManagement.c.

Function Documentation

CalNodeManager_t* CalNodeManagerInit ( CalPageManager_t * pageManager )

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

Name [CalNodeManagerInit]

Synopsis [Initializes a node manager.]

Description [optional]

SideEffects []

SeeAlso [optional]

Definition at line 219 of file calMemoryManagement.c.

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 }

void CalNodeManagerPrint ( CalNodeManager_t * nodeManager )

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

Name [CalNodeManagerPrint]

Synopsis [Prints address of each free node.]

Description [optional]

SideEffects []

SeeAlso [optional]

Definition at line 280 of file calMemoryManagement.c.

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 }

int CalNodeManagerQuit ( CalNodeManager_t * nodeManager )

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

Name [CalNodeManagerQuit]

Synopsis [Frees a node manager.]

Description [optional]

SideEffects [The associated nodes are lost.]

SeeAlso [optional]

Definition at line 247 of file calMemoryManagement.c.

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 }

CalAddress_t* CalPageManagerAllocPage ( CalPageManager_t * pageManager )

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

Name [PageMangerAllocPage]

Synopsis [Allocs a new page.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 312 of file calMemoryManagement.c.

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 }

void CalPageManagerFreePage	(	CalPageManager_t *	pageManager,
		CalAddress_t *	page
	)

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

Name [PageMangerFreePage]

Synopsis [Free a page.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 347 of file calMemoryManagement.c.

00348 {
00349   *page = (CalAddress_t)(pageManager->freePageList);
00350   pageManager->freePageList = page;
00351 }

CalPageManager_t* CalPageManagerInit ( int numPagesPerSegment )

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

Name [CalPageMangerInit]

Synopsis [Initializes a pageManager.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 114 of file calMemoryManagement.c.

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 }

void CalPageManagerPrint ( CalPageManager_t * pageManager )

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

Name [CalPageMangerPrint]

Synopsis [Prints address of each memory segment and address of each page.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 181 of file calMemoryManagement.c.

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 }

int CalPageManagerQuit ( CalPageManager_t * pageManager )

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

Name [CalPageMangerQuit]

Synopsis [Frees pageManager and associated pages.]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 150 of file calMemoryManagement.c.

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 }

static CalAddress_t * PageAlign ( CalAddress_t * p ) [static]

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

Name [PageAlign]

Synopsis [Return page aligned address greater than or equal to the pointer.]

Description [optional]

SideEffects []

SeeAlso [optional]

Definition at line 460 of file calMemoryManagement.c.

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 }

static int PageManagerExpandStorage ( CalPageManager_t * pageManager ) [static]

AutomaticStart

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

Name [PageManagerExpandStorage]

Synopsis [Allocates a segment of memory to expand the storage managed by pageManager. The allocated segment is divided into free pages which are linked as a freePageList.]

Description [optional]

SideEffects [The size of the segment is stored in one of the fields of page manager - numPagesPerSegment. If a memory segment of a specific size cannot be allocated, the routine calls itself recursively by reducing numPagesPerSegment by a factor of 2.]

SeeAlso [optional]

Definition at line 374 of file calMemoryManagement.c.

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 }

static int SegmentToPageList	(	CalAddress_t *	segment,
		int	numPages,
		CalAddress_t *	lastPointer
	)			`[static]`

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

Name [SegmentToPageList]

Synopsis [Converts a memory segment into a linked list of pages. if p is a pointer to a page, *p contains address of the next page if p is a pointer to the last page, *p contains lastPointer.]

Description [optional]

SideEffects []

SeeAlso [optional]

Definition at line 487 of file calMemoryManagement.c.

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 }

src/calBdd/calMemoryManagement.c File Reference

Defines

Functions

Define Documentation

Function Documentation