source: vis_dev/glu-2.3/src/calBdd/calMemoryManagement.c

Last change on this file was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 17.6 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [calMemoryManagement.c]
4
5  PackageName [cal]
6
7  Synopsis    [Special memory management routines specific to CAL.]
8
9  Description [Functions for managing the system memory using a set of
10              nodeManagers. Each nodeManager manages a set of fixed size
11              nodes obtained from a set of pages. When additional memory
12              is required, nodeManager obtains a new page from the pageManager.
13              The new page is divided into ( PAGE_SIZE/NODE_SIZE ) number of
14              nodes.]
15
16  SeeAlso     []
17
18  Author      [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
19               Rajeev Ranjan   (rajeev@eecs.berkeley.edu)
20              ]
21  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
22  All rights reserved.
23
24  Permission is hereby granted, without written agreement and without license
25  or royalty fees, to use, copy, modify, and distribute this software and its
26  documentation for any purpose, provided that the above copyright notice and
27  the following two paragraphs appear in all copies of this software.
28
29  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
30  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
31  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
32  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33
34  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
35  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
36  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
37  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
38  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
39
40  Revision    [$Id: calMemoryManagement.c,v 1.6 2005/04/30 01:50:53 fabio Exp $]
41
42******************************************************************************/
43#include "malloc.h"
44#include "calInt.h"
45
46/*---------------------------------------------------------------------------*/
47/* Constant declarations                                                     */
48/*---------------------------------------------------------------------------*/
49
50/*---------------------------------------------------------------------------*/
51/* Type declarations                                                         */
52/*---------------------------------------------------------------------------*/
53
54
55/*---------------------------------------------------------------------------*/
56/* Stucture declarations                                                     */
57/*---------------------------------------------------------------------------*/
58
59/*---------------------------------------------------------------------------*/
60/* Variable declarations                                                     */
61/*---------------------------------------------------------------------------*/
62
63
64/*---------------------------------------------------------------------------*/
65/* Macro declarations                                                        */
66/*---------------------------------------------------------------------------*/
67#ifndef HAVE_VALLOC
68#define __NOVALLOC__
69#else
70#if HAVE_VALLOC != 1
71#define __NOVALLOC__
72#endif
73#endif
74
75/**AutomaticStart*************************************************************/
76
77/*---------------------------------------------------------------------------*/
78/* Static function prototypes                                                */
79/*---------------------------------------------------------------------------*/
80
81static int PageManagerExpandStorage(CalPageManager_t * pageManager);
82static CalAddress_t * PageAlign(CalAddress_t * p);
83static int SegmentToPageList(CalAddress_t * segment, int numPages, CalAddress_t * lastPointer);
84
85/**AutomaticEnd***************************************************************/
86
87/*
88 * object: pageManager
89 * operations: Init, Quit, AllocPage, FreePage, Print
90 */
91
92
93/*---------------------------------------------------------------------------*/
94/* Definition of exported functions                                          */
95/*---------------------------------------------------------------------------*/
96
97/*---------------------------------------------------------------------------*/
98/* Definition of internal functions                                          */
99/*---------------------------------------------------------------------------*/
100/**Function********************************************************************
101
102  Name        [CalPageMangerInit]
103
104  Synopsis    [Initializes a pageManager.]
105
106  Description [optional]
107
108  SideEffects [required]
109
110  SeeAlso     [optional]
111
112******************************************************************************/
113CalPageManager_t *
114CalPageManagerInit(int numPagesPerSegment)
115{
116  CalPageManager_t *pageManager;
117  pageManager = Cal_MemAlloc(CalPageManager_t, 1);
118  pageManager->totalNumPages = 0;
119  pageManager->numSegments = 0;
120  pageManager->numPagesPerSegment = numPagesPerSegment;
121  pageManager->maxNumSegments = MAX_NUM_SEGMENTS;
122  pageManager->pageSegmentArray
123      = Cal_MemAlloc(CalAddress_t *, pageManager->maxNumSegments);
124  pageManager->numPagesArray
125      = Cal_MemAlloc(int, pageManager->maxNumSegments);
126  pageManager->freePageList = Cal_Nil(CalAddress_t);
127  if(PageManagerExpandStorage(pageManager) == FALSE){
128    Cal_MemFree(pageManager->pageSegmentArray);
129    Cal_MemFree(pageManager);
130    return Cal_Nil(CalPageManager_t);
131  }
132  return pageManager;
133}
134
135
136/**Function********************************************************************
137
138  Name        [CalPageMangerQuit]
139
140  Synopsis    [Frees pageManager and associated pages.]
141
142  Description [optional]
143
144  SideEffects [required]
145
146  SeeAlso     [optional]
147
148******************************************************************************/
149int
150CalPageManagerQuit(
151  CalPageManager_t * pageManager)
152{
153  int i;
154  if(pageManager == Cal_Nil(CalPageManager_t)){
155    return 1;
156  }
157  for(i = 0; i < pageManager->numSegments; i++){
158    free(pageManager->pageSegmentArray[i]);
159  }
160  Cal_MemFree(pageManager->pageSegmentArray);
161  Cal_MemFree(pageManager->numPagesArray);
162  Cal_MemFree(pageManager);
163  return 0;
164}
165
166
167/**Function********************************************************************
168
169  Name        [CalPageMangerPrint]
170
171  Synopsis    [Prints address of each memory segment and address of each page.]
172
173  Description [optional]
174
175  SideEffects [required]
176
177  SeeAlso     [optional]
178
179******************************************************************************/
180void
181CalPageManagerPrint(
182  CalPageManager_t * pageManager)
183{
184  int i;
185  CalAddress_t *page;
186  printf("****************** pageManager ********************\n");
187  printf("allocationList:\n");
188  for(i = 0; i < pageManager->numSegments; i++){
189    page = pageManager->pageSegmentArray[i];
190    printf("%lx%c", (CalAddress_t)page, (i+1)%5?' ':'\n');
191  }
192  printf("\n");
193  printf("freePageList:\n");
194  i = 0;
195  page = pageManager->freePageList;
196  while(page){
197    printf("%lx%c", (CalAddress_t)page, (i+1)%5?' ':'\n');
198    i++;
199    page = (CalAddress_t *)*page;
200  }
201  printf("\n");
202}
203
204
205/**Function********************************************************************
206
207  Name        [CalNodeManagerInit]
208
209  Synopsis    [Initializes a node manager.]
210
211  Description [optional]
212
213  SideEffects []
214
215  SeeAlso     [optional]
216
217******************************************************************************/
218CalNodeManager_t *
219CalNodeManagerInit(CalPageManager_t * pageManager)
220{
221  CalNodeManager_t *nodeManager;
222  nodeManager = Cal_MemAlloc(CalNodeManager_t, 1);
223  nodeManager->freeNodeList = Cal_Nil(CalBddNode_t);
224  nodeManager->pageManager = pageManager;
225  nodeManager->numPages = 0;
226  nodeManager->maxNumPages = 10;
227  nodeManager->pageList = Cal_MemAlloc(CalAddress_t *,
228                                        nodeManager->maxNumPages);
229  return nodeManager;
230}
231
232
233/**Function********************************************************************
234
235  Name        [CalNodeManagerQuit]
236
237  Synopsis    [Frees a node manager.]
238
239  Description [optional]
240
241  SideEffects [The associated nodes are lost.]
242
243  SeeAlso     [optional]
244
245******************************************************************************/
246int
247CalNodeManagerQuit(CalNodeManager_t * nodeManager)
248{
249  if(nodeManager == Cal_Nil(CalNodeManager_t)){
250    return 1;
251  }
252  else{
253    int i;
254    for (i = 0; i < nodeManager->numPages; i++){
255      CalPageManagerFreePage(nodeManager->pageManager,
256                             nodeManager->pageList[i]);
257    }
258    Cal_MemFree(nodeManager->pageList);
259    Cal_MemFree(nodeManager);
260    return 0;
261  }
262}
263
264
265
266/**Function********************************************************************
267
268  Name        [CalNodeManagerPrint]
269
270  Synopsis    [Prints address of each free node.]
271
272  Description [optional]
273
274  SideEffects []
275
276  SeeAlso     [optional]
277
278******************************************************************************/
279void
280CalNodeManagerPrint(
281  CalNodeManager_t * nodeManager)
282{
283  int i;
284  CalBddNode_t *node;
285  printf("****************** nodeManager ********************\n");
286  printf("freeNodeList:\n");
287  i = 0;
288  node = nodeManager->freeNodeList;
289  while(node){
290    printf("%lx%c", (CalAddress_t)node, (i+1)%5?' ':'\n');
291    i++;
292    node = node->nextBddNode;
293  }
294  printf("\n");
295}
296
297
298/**Function********************************************************************
299
300  Name        [PageMangerAllocPage]
301
302  Synopsis    [Allocs a new page.]
303
304  Description [optional]
305
306  SideEffects [required]
307
308  SeeAlso     [optional]
309
310******************************************************************************/
311CalAddress_t *
312CalPageManagerAllocPage(CalPageManager_t * pageManager)
313{
314  CalAddress_t *page;
315  char buffer[512];
316  if(pageManager->freePageList == Cal_Nil(CalAddress_t)){
317    if(PageManagerExpandStorage(pageManager) == FALSE){
318      sprintf(buffer,
319              "out of memory : Number of pages allocated = %d\n", 
320              pageManager->totalNumPages);
321      CalBddFatalMessage(buffer);
322    }
323  }
324  page = pageManager->freePageList;
325  pageManager->freePageList = (CalAddress_t *)*page;
326  return page;
327}
328
329/*---------------------------------------------------------------------------*/
330/* Definition of static functions                                            */
331/*---------------------------------------------------------------------------*/
332
333/**Function********************************************************************
334
335  Name        [PageMangerFreePage]
336
337  Synopsis    [Free a page.]
338
339  Description [optional]
340
341  SideEffects [required]
342
343  SeeAlso     [optional]
344
345******************************************************************************/
346void
347CalPageManagerFreePage(CalPageManager_t * pageManager, CalAddress_t * page)
348{
349  *page = (CalAddress_t)(pageManager->freePageList);
350  pageManager->freePageList = page;
351}
352
353
354/**Function********************************************************************
355
356  Name        [PageManagerExpandStorage]
357
358  Synopsis    [Allocates a segment of memory to expand the storage managed by
359              pageManager. The allocated segment is divided into free pages
360              which are linked as a freePageList.]
361
362  Description [optional]
363
364  SideEffects [The size of the segment is stored in one of the fields
365              of page manager - numPagesPerSegment. If a memory
366              segment of a specific size cannot be allocated, the
367              routine calls itself recursively by reducing
368              numPagesPerSegment by a factor of 2.]
369
370  SeeAlso     [optional]
371
372******************************************************************************/
373static int
374PageManagerExpandStorage(CalPageManager_t * pageManager)
375{
376  CalAddress_t *p;
377  CalAddress_t *segment;
378  int numUsefulPages;
379
380  int numPagesPerSegment = pageManager->numPagesPerSegment;
381
382#ifdef __NOVALLOC__
383  p = (CalAddress_t *) malloc(numPagesPerSegment*PAGE_SIZE);
384#else
385  p = (CalAddress_t *) valloc(numPagesPerSegment*PAGE_SIZE);
386#endif
387  /* Just check the page boundary correctness */
388  Cal_Assert(((CalAddress_t)p & ((1 << LG_PAGE_SIZE)-1)) == 0);
389  if(p == Cal_Nil(CalAddress_t)){
390    numPagesPerSegment = numPagesPerSegment / 2;
391    if(numPagesPerSegment < MIN_NUM_PAGES_PER_SEGMENT){
392      return FALSE;
393    }
394    pageManager->numPagesPerSegment = numPagesPerSegment;
395    return PageManagerExpandStorage(pageManager); 
396  }
397
398#ifdef __NOVALLOC__
399  /* No need to do it anymore, since I am using valloc */
400  /* align the memory segment to a page boundary */
401  segment = PageAlign(p); 
402
403  /* if memory segment is already page aligned, all pages in the memory
404   * segment are useful, otherwise, one page is wasted
405   */
406  if(segment == p){
407    numUsefulPages = numPagesPerSegment;
408  }
409  else{
410    numUsefulPages = numPagesPerSegment - 1;
411  }
412#else
413  segment = p;
414  numUsefulPages = numPagesPerSegment;
415#endif
416 
417  /* Initialize the pages  */
418  memset((char *)segment, 0, numUsefulPages*PAGE_SIZE);
419
420  /* Keep track of the number of pages allocated */
421  pageManager->totalNumPages += numUsefulPages;
422 
423  /* increase the size of the allocation list if neccessary */
424  if(pageManager->numSegments == pageManager->maxNumSegments){
425    pageManager->maxNumSegments = pageManager->maxNumSegments * 2;
426    pageManager->pageSegmentArray = Cal_MemRealloc(CalAddress_t *,
427                                                   pageManager->pageSegmentArray, 
428                                                   pageManager->maxNumSegments);
429    pageManager->numPagesArray = Cal_MemRealloc(int,
430                                                pageManager->numPagesArray, 
431                                                pageManager->maxNumSegments);
432   
433  }
434
435  pageManager->pageSegmentArray[pageManager->numSegments] = p;
436  pageManager->numPagesArray[pageManager->numSegments++] =
437      numUsefulPages;
438 
439  SegmentToPageList(segment, numUsefulPages, pageManager->freePageList);
440  pageManager->freePageList = segment;
441  return TRUE;
442}
443
444
445/**Function********************************************************************
446
447  Name        [PageAlign]
448
449  Synopsis    [Return page aligned address greater than or equal to
450  the pointer.]
451
452  Description [optional]
453
454  SideEffects []
455
456  SeeAlso     [optional]
457
458******************************************************************************/
459static CalAddress_t *
460PageAlign(
461  CalAddress_t * p)
462{
463  if((CalAddress_t)p & (PAGE_SIZE - 1)){
464    p = (CalAddress_t *)( (CalAddress_t)p >> LG_PAGE_SIZE );
465    p = (CalAddress_t *)( ((CalAddress_t)p << LG_PAGE_SIZE) + PAGE_SIZE );
466  }
467  return p;
468}
469
470
471/**Function********************************************************************
472
473  Name        [SegmentToPageList]
474
475  Synopsis    [Converts a memory segment into a linked list of pages.
476              if p is a pointer to a page, *p contains address of the next page
477              if p is a pointer to the last page, *p contains lastPointer.]
478
479  Description [optional]
480
481  SideEffects []
482
483  SeeAlso     [optional]
484
485******************************************************************************/
486static int
487SegmentToPageList(CalAddress_t * segment,
488                  int  numPages,
489                  CalAddress_t * lastPointer)
490{
491  int i;
492  unsigned long thisPageOffset, nextPageOffset;
493
494  if(numPages > 0){
495    for(i = 0; i < numPages - 1; i++){
496      thisPageOffset = (i<<LG_PAGE_SIZE)/sizeof(CalAddress_t);
497      nextPageOffset = ((i+1)<<LG_PAGE_SIZE)/sizeof(CalAddress_t);
498      *(segment + thisPageOffset) =
499          (CalAddress_t)(segment + nextPageOffset);
500    }
501    thisPageOffset = ((numPages - 1)<<LG_PAGE_SIZE)/sizeof(CalAddress_t);
502    *(segment + thisPageOffset) = (CalAddress_t)lastPointer;
503  }
504  else{
505    CalBddFatalMessage("out of memory");
506  }
507  return 0;
508}
509
510
511/*---------------------------------------------------------------------------*/
512/* Module Testing                                                            */
513/*---------------------------------------------------------------------------*/
514#ifdef PAGE_MANAGER
515main(argc, argv)
516int argc;
517char **argv;
518{
519  CalPageManager_t *pageManager;
520  CalAddress_t *page, *pageArray[10];
521  int i;
522
523  pageManager = CalPageManagerInit();
524  CalPageManagerPrint(pageManager);
525
526  page = CalPageManagerAllocPage(pageManager);
527  printf("PAGE - %x\n", (CalAddress_t)page);
528  CalPageManagerPrint(pageManager);
529
530  PageManagerFreePage(pageManager, page);
531  CalPageManagerPrint(pageManager);
532
533  printf("Cal_MemAllocATING PAGES\n");
534  for(i = 0; i < 10; i++){
535    pageArray[i] = CalPageManagerAllocPage(pageManager);
536    CalPageManagerPrint(pageManager);
537    printf("\n");
538  }
539  printf("\n");
540
541  printf("FREEING PAGES\n");
542  for(i = 0; i < 10; i++){
543    PageManagerFreePage(pageManager, pageArray[i] );
544    CalPageManagerPrint(pageManager);
545    printf("\n");
546  }   
547  printf("\n");
548  CalPageManagerQuit(pageManager);
549}
550#endif
551
552#ifdef NODE_MANAGER
553main(argc, argv)
554int argc;
555char **argv;
556{
557  CalPageManager_t *pageManager;
558  CalNodeManager_t *nodeManagerArray[5], *nodeManager;
559  CalBddNode_t *node, *nodeArray[5][10];
560  int numNodeManagers = 5;
561  int numNodes = 10;
562  int i,j;
563 
564
565  pageManager = CalPageManagerInit();
566  /*CalNodeManagerPrint(nodeManager);*/
567
568  printf("Allocating Nodes\n");
569  for(i = 0; i < numNodeManagers; i++){
570    nodeManagerArray[i] = CalNodeManagerInit(pageManager);
571    for (j=0; j < numNodes; j++){
572      CalNodeManagerAllocNode(nodeManagerArray[i], nodeArray[i][j]);
573      CalBddNodePutRefCount(nodeArray[i][j], i+j);
574    }
575  }
576  for(i = 0; i < numNodeManagers; i++){
577    printf("i = %3d\n", i);
578    for (j=0; j < numNodes; j++){
579      CalBddNodePrint(nodeArray[i][j]);
580    }
581    printf("\n");
582  }
583
584  printf("FREEING NODES\n");
585  for(i = 0; i < numNodeManagers; i++){
586    for(j = 0; j < numNodes; j++){
587      CalNodeManagerFreeNode(nodeManagerArray[i], nodeArray[i][j] );
588    }   
589    CalNodeManagerQuit(nodeManagerArray[i]);
590  }
591  CalPageManagerQuit(pageManager);
592}
593#endif
Note: See TracBrowser for help on using the repository browser.