source: vis_dev/glu-2.3/src/calBdd/calMem.c @ 104

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

library glu 2.3
File size: 20.7 KB
RevLine 
[13]1/**CFile*****************************************************************
2
3  FileName    [calMem.c]
4
5  PackageName [cal]
6
7  Synopsis    [Routines for memory management.]
8
9  Description [Contains allocation, free, resize routines. Also has
10  routines for managing records of fixed size.]
11
12  SeeAlso     [optional]
13
14  Author      [Rajeev K. Ranjan (rajeev@eecs.berkeley.edu). Originally
15  written by David Long.]
16
17  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
18  All rights reserved.
19
20  Permission is hereby granted, without written agreement and without license
21  or royalty fees, to use, copy, modify, and distribute this software and its
22  documentation for any purpose, provided that the above copyright notice and
23  the following two paragraphs appear in all copies of this software.
24
25  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
26  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
27  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
28  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
31  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
32  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
33  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
34  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
35
36  Revision   [$Id: calMem.c,v 1.4 2002/08/25 05:29:59 fabio Exp $]
37
38******************************************************************************/
39
40#if HAVE_UNISTD_H
41#include <unistd.h>
42#endif
43#if STDC_HEADERS
44#include <stdlib.h>
45#include <string.h>
46#endif
47#include "calMem.h"
48/*---------------------------------------------------------------------------*/
49/* Type declarations                                                         */
50/*---------------------------------------------------------------------------*/
51typedef struct BlockStruct *Block;
52typedef struct BlockStruct Block_t;
53typedef struct SegmentStruct *Segment;
54typedef struct SegmentStruct Segment_t;
55typedef struct ListStruct *List;
56typedef struct ListStruct List_t;
57typedef struct Cal_RecMgrStruct Cal_RecMgr_t;
58
59/*---------------------------------------------------------------------------*/
60/* Constant declarations                                                     */
61/*---------------------------------------------------------------------------*/
62/* #define DEBUG_MEM */
63#define MAGIC_COOKIE 0x34f21ab3l
64#define MAGIC_COOKIE1 0x432fa13bl
65struct SegmentStruct
66{
67  Cal_Pointer_t baseAddress;
68  Cal_Address_t limit;
69};
70
71struct BlockStruct
72{
73  int used;
74  int sizeIndex;
75  unsigned long dummy;
76  Block_t *next;
77  Block_t *prev;
78  Segment seg;
79};
80#define HEADER_SIZE ((Cal_Address_t)CAL_ROUNDUP(sizeof(Block_t)))
81#define MAX_SIZEINDEX (8*sizeof(Cal_Address_t)-2)
82#define MAX_SEG_SIZE ((Cal_Address_t)1 << MAX_SIZEINDEX)
83#define MAX_SIZE ((Cal_Address_t)(MAX_SEG_SIZE-HEADER_SIZE))
84#define NICE_BLOCK_SIZE ((Cal_Address_t)PAGE_SIZE-CAL_ROUNDUP(sizeof(Block_t)))
85#define ALLOC_SIZE NICE_BLOCK_SIZE
86#define MIN_ALLOC_SIZEINDEX 15
87
88
89/*---------------------------------------------------------------------------*/
90/* Stucture declarations                                                     */
91/*---------------------------------------------------------------------------*/
92struct ListStruct
93{
94  List_t *next;
95};
96
97struct Cal_RecMgrStruct
98{
99  int size;
100  int recsPerBlock;
101  List free;
102  List blocks;
103  int numBlocks;
104};
105
106
107/*---------------------------------------------------------------------------*/
108/* Variable declarations                                                     */
109/*---------------------------------------------------------------------------*/
110static Cal_Address_t blockAllocation;
111static Block avail[MAX_SIZEINDEX+1];
112
113
114/* Bogus segment for initialization */
115
116static Segment_t dummySeg={(Cal_Pointer_t)0, (Cal_Address_t)0};
117
118
119/* Current segment */
120
121static Segment currSeg= &dummySeg;
122
123/*---------------------------------------------------------------------------*/
124/* Macro declarations                                                        */
125/*---------------------------------------------------------------------------*/
126#define SBRK(size) ((Cal_Pointer_t)sbrk((long)(size)))
127
128/**AutomaticStart*************************************************************/
129
130/*---------------------------------------------------------------------------*/
131/* Static function prototypes                                                */
132/*---------------------------------------------------------------------------*/
133
134static int CeilingLog2(Cal_Address_t i);
135static int BlockSizeIndex(Cal_Address_t size);
136static void AddToFreeList(Block b);
137static Block RemoveFromFreeList(Block b);
138static Block Buddy(Block b);
139static void TrimToSize(Block b, int sizeIndex);
140static void MergeAndFree(Block b);
141
142/**AutomaticEnd***************************************************************/
143
144/*---------------------------------------------------------------------------*/
145/* Definition of exported functions                                          */
146/*---------------------------------------------------------------------------*/
147
148
149
150/**Function********************************************************************
151
152  Synopsis           [Prints an error message and exits.]
153
154  Description        [Prints an error message and exits.]
155
156  SideEffects        [required]
157
158  SeeAlso            [optional]
159
160******************************************************************************/
161void
162Cal_MemFatal(char *message)
163{
164  fprintf(stderr, "Memory management library: error: %s\n", message);
165  exit(1);
166}
167
168/**Function********************************************************************
169
170  Synopsis           [Returns the memory allocated.]
171
172  Description        [Returns the memory allocated.]
173
174  SideEffects        [required]
175
176  SeeAlso            [optional]
177
178******************************************************************************/
179Cal_Address_t
180Cal_MemAllocation(void)
181{
182  return (blockAllocation);
183}
184
185/**Function********************************************************************
186
187  Synopsis           [Allocates a new block of the specified size.]
188
189  Description        [Allocates a new block of the specified size.]
190
191  SideEffects        [required]
192
193  SeeAlso            [optional]
194
195******************************************************************************/
196Cal_Pointer_t
197Cal_MemGetBlock(Cal_Address_t size)
198{
199  int i;
200  int sizeIndex;
201  int allocSizeIndex;
202  int newSeg;
203  Cal_Address_t allocSize;
204  Cal_Pointer_t sbrkRet;
205  Block b;
206
207  if ((sizeIndex = BlockSizeIndex(size)) < 0) return ((Cal_Pointer_t)0);
208 
209  /* Find smallest free block which is large enough. */
210  for (i = sizeIndex; i <= MAX_SIZEINDEX && !avail[i]; ++i);
211  if (i > MAX_SIZEINDEX) {
212    /* We must get more storage; don't allocate less than */
213    /* 2^MIN_ALLOC_SIZE_INDEX */
214    if (sizeIndex < MIN_ALLOC_SIZEINDEX) allocSizeIndex=MIN_ALLOC_SIZEINDEX;
215    else allocSizeIndex=sizeIndex;
216    allocSize=((Cal_Address_t)1 << allocSizeIndex);
217   
218    /* Pad current segment to be a multiple of 2^allocSizeIndex in */
219    /* length. */
220    allocSize += ((currSeg->limit + allocSize - 1) &
221                  ~(allocSize - 1)) - currSeg->limit;
222    if ((sbrkRet=(Cal_Pointer_t)SBRK(0)) !=
223        (Cal_Pointer_t)((Cal_Address_t)currSeg->baseAddress+currSeg->limit) || 
224        allocSize+currSeg->limit > MAX_SEG_SIZE) {
225     
226      /* Segment is too large or someone else has moved the break. */
227      /* Pad to get to appropriate boundary. */
228      allocSize=CAL_ROUNDUP((Cal_Address_t)sbrkRet)-(Cal_Address_t)sbrkRet;
229     
230      /* Pad allocation request with storage for new segment */
231      /* information and indicate that a new segment must be */
232        /* created. */
233      allocSize+=((Cal_Address_t)1 << allocSizeIndex)+CAL_ROUNDUP(sizeof(Segment_t));
234      newSeg=1;
235    }
236    else newSeg=0;
237    sbrkRet=(Cal_Pointer_t)SBRK(allocSize);
238    if (sbrkRet == (Cal_Pointer_t) -1) Cal_MemFatal("Cal_MemGetBlock: allocation failed");
239    blockAllocation += allocSize;
240    if (newSeg){
241      currSeg = (Segment) CAL_ROUNDUP((Cal_Address_t)sbrkRet);
242      currSeg->baseAddress=(Cal_Pointer_t)((Cal_Address_t)currSeg+CAL_ROUNDUP(sizeof(Segment_t)));
243      currSeg->limit=0;
244      /* Readjust allocation size. */
245      allocSize=(1l << allocSizeIndex);
246      }
247    /* Carve allocated space up into blocks and add to free lists. */
248    while (allocSize){
249      size = allocSize - (allocSize & (allocSize-1));
250      b = (Block) ((Cal_Address_t)currSeg->baseAddress+currSeg->limit);
251      b->sizeIndex = CeilingLog2(size);
252      b->seg = currSeg;
253      AddToFreeList(b);
254        currSeg->limit += size;
255        allocSize -= size;
256    }
257    /* Find free block of appropriate size. */
258    for (i=sizeIndex; i <= MAX_SIZEINDEX && !avail[i]; ++i);
259  }
260  b = RemoveFromFreeList(avail[i]);
261  TrimToSize(b, sizeIndex);
262  return ((Cal_Pointer_t)((Cal_Address_t)b + HEADER_SIZE));
263}
264
265
266/**Function********************************************************************
267
268  Synopsis           [Frees the block.]
269
270  Description        [Frees the block.]
271
272  SideEffects        [required]
273
274  SeeAlso            [optional]
275
276******************************************************************************/void
277Cal_MemFreeBlock(Cal_Pointer_t p)
278{
279  Block b;
280
281  if (!p) return;
282  b = (Block) ((Cal_Address_t)p-HEADER_SIZE);
283  if (!b->used) Cal_MemFatal("Cal_MemFreeBlock: block not in use");
284  if (b->sizeIndex < 0 || b->sizeIndex > MAX_SIZEINDEX) Cal_MemFatal("Cal_MemFreeBlock: invalid block header");
285  MergeAndFree(b);
286}
287
288
289
290/**Function********************************************************************
291
292  Synopsis           [Expands or contracts the block to a new size.
293  We try to avoid moving the block if possible. ]
294
295  Description        [Expands or contracts the block to a new size.
296  We try to avoid moving the block if possible. ] 
297
298  SideEffects        [required]
299
300  SeeAlso            [optional]
301
302******************************************************************************/
303Cal_Pointer_t
304Cal_MemResizeBlock(Cal_Pointer_t p, Cal_Address_t newSize)
305{
306  int newSizeIndex;
307  Block b;
308  Block bb;
309  Cal_Pointer_t q;
310  Cal_Address_t oldSize;
311
312  if (!p) return (Cal_MemGetBlock(newSize));
313  b = (Block) ((Cal_Address_t)p - HEADER_SIZE);
314  if (!b->used) Cal_MemFatal("Cal_MemResizeBlock: block not in use");
315  if (b->sizeIndex < 0 || b->sizeIndex > MAX_SIZEINDEX){
316    Cal_MemFatal("Cal_MemResizeBlock: invalid block header");
317  }
318  if ((newSizeIndex = BlockSizeIndex(newSize)) < 0){
319    Cal_MemFreeBlock(p);
320    return ((Cal_Pointer_t)0);
321  }
322  if (b->sizeIndex >= newSizeIndex){
323    /* Shrink block. */
324    TrimToSize(b, newSizeIndex);
325    return (p);
326  }
327  oldSize=(1l << b->sizeIndex) - HEADER_SIZE;
328  /* Try to expand by adding buddies at higher addresses. */
329  for (bb=Buddy(b);
330       bb && (Cal_Address_t)b < (Cal_Address_t)bb && !bb->used && bb->sizeIndex == b->sizeIndex;
331       bb=Buddy(b)) {
332    RemoveFromFreeList(bb);
333    if (++(b->sizeIndex) == newSizeIndex) return (p);
334  }
335  /* Couldn't expand all the way to needed size; allocate a new block */
336  /* and move the contents of the old one. */
337  q = (Cal_Pointer_t) Cal_MemGetBlock(newSize);
338  Cal_MemCopy(q, p, oldSize);
339  MergeAndFree(b);
340  return (q);
341}
342
343/**Function********************************************************************
344
345  Synopsis           [Allocates a record from the specified record manager. ]
346
347  Description        [Allocates a record from the specified record manager. ]
348
349  SideEffects        [required]
350
351  SeeAlso            [optional]
352
353******************************************************************************/
354Cal_Pointer_t
355Cal_MemNewRec(Cal_RecMgr mgr)
356{
357  int i;
358  Cal_Pointer_t p;
359  List new_;
360 
361  if (!mgr->free) {
362    /* Allocate a new block. */
363    new_ = (List) Cal_MemGetBlock(ALLOC_SIZE);
364    mgr->numBlocks++;
365    new_->next=mgr->blocks;
366    mgr->blocks=new_;
367    mgr->free=(List)((Cal_Address_t)new_+CAL_ROUNDUP(sizeof(List_t)));
368    p=(Cal_Pointer_t)(mgr->free);
369    /* Carve the block into pieces. */
370    for (i=1; i < mgr->recsPerBlock; ++i) {
371      ((List)p)->next=(List)((Cal_Address_t)p+mgr->size);
372#if defined(DEBUG_MEM)
373      if (mgr->size >= sizeof(long)+sizeof(List_t))
374        *(long *)(sizeof(List_t)+(Cal_Address_t)p)=MAGIC_COOKIE;
375#endif
376      p=(Cal_Pointer_t)((Cal_Address_t)p+mgr->size);
377    }
378    ((List)p)->next=0;
379#if defined(DEBUG_MEM)
380    if (mgr->size >= sizeof(long)+sizeof(List_t)){
381      *(long *)(sizeof(List_t)+(Cal_Address_t)p)=MAGIC_COOKIE;
382    }
383#endif
384  }
385  new_ = mgr->free;
386#if defined(DEBUG_MEM)
387  if (mgr->size >= sizeof(long)+sizeof(List_t)){
388    if (*(long *)(sizeof(List_t)+(Cal_Address_t)new_) != MAGIC_COOKIE)
389      fprintf(stderr, "record at 0x%lx may be in use\n", (Cal_Address_t)new_);
390    else
391      *(long *)(sizeof(struct
392                       list_)+(Cal_Address_t)new)=MAGIC_COOKIE1;
393  }
394#endif
395  mgr->free = mgr->free->next;
396  return ((Cal_Pointer_t)new_);
397}
398
399
400/**Function********************************************************************
401
402  Synopsis           [Frees a record managed by the indicated record manager. ]
403
404  Description        [Frees a record managed by the indicated record manager. ]
405
406  SideEffects        [required]
407
408  SeeAlso            [optional]
409
410******************************************************************************/
411void
412Cal_MemFreeRec(Cal_RecMgr mgr, Cal_Pointer_t rec)
413{
414#if defined(DEBUG_MEM)
415  if (mgr->size >= sizeof(long)+sizeof(List_t))
416    if (*(long *)(sizeof(List_t)+(Cal_Address_t)rec) == MAGIC_COOKIE)
417      fprintf(stderr, "record at 0x%lx may already be freed\n", (Cal_Address_t)rec);
418#endif
419  ((List)rec)->next=mgr->free;
420#if defined(DEBUG_MEM)
421  if (mgr->size >= sizeof(long)+sizeof(List_t))
422    *(long *)(sizeof(List_t)+(Cal_Address_t)rec)=MAGIC_COOKIE;
423#endif
424  mgr->free=(List)rec;
425}
426
427
428
429/**Function********************************************************************
430
431  Synopsis           [Creates a new record manager with the given  record size.]
432
433  Description        [Creates a new record manager with the given  record size.]
434
435  SideEffects        [required]
436
437  SeeAlso            [optional]
438
439******************************************************************************/
440Cal_RecMgr
441Cal_MemNewRecMgr(int size)
442{
443  Cal_RecMgr mgr;
444
445  if (size < sizeof(List_t)) size=sizeof(List_t);
446  size=CAL_ROUNDUP(size);
447  if (size > ALLOC_SIZE-CAL_ROUNDUP(sizeof(List_t)))
448    Cal_MemFatal("Cal_MemNewRecMgr: record size too large");
449  mgr = (Cal_RecMgr)Cal_MemGetBlock((Cal_Address_t)sizeof(Cal_RecMgr_t));
450  mgr->size=size;
451  mgr->recsPerBlock=(ALLOC_SIZE-CAL_ROUNDUP(sizeof(List_t)))/size;
452  mgr->free=0;
453  mgr->blocks=0;
454  mgr->numBlocks = 0;
455  return (mgr);
456}
457
458/**Function********************************************************************
459
460  Synopsis           [Frees all the storage associated with the specified record manager.]
461
462  Description        [Frees all the storage associated with the specified record manager.]
463
464  SideEffects        [required]
465
466  SeeAlso            [optional]
467
468******************************************************************************/
469void
470Cal_MemFreeRecMgr(Cal_RecMgr mgr)
471{
472  List p, q;
473  for (p=mgr->blocks; p; p=q){
474    q=p->next;
475    Cal_MemFreeBlock((Cal_Pointer_t)p);
476  }
477  Cal_MemFreeBlock((Cal_Pointer_t)mgr);
478}
479
480/*---------------------------------------------------------------------------*/
481/* Definition of internal functions                                          */
482/*---------------------------------------------------------------------------*/
483/*---------------------------------------------------------------------------*/
484/* Definition of static functions                                          */
485/*---------------------------------------------------------------------------*/
486/**Function********************************************************************
487
488  Synopsis           [required]
489
490  Description        [optional]
491
492  SideEffects        [required]
493
494  SeeAlso            [optional]
495
496  CommandName        [optional]           
497
498  CommandSynopsis    [optional] 
499
500  CommandArguments   [optional] 
501
502  CommandDescription [optional] 
503
504******************************************************************************/
505static int
506CeilingLog2(Cal_Address_t i)
507{
508  Cal_Address_t j;
509  int result;
510
511  for (result=0, j=1; j < i; ++result, j*=2);
512  return (result);
513}
514
515/**Function********************************************************************
516
517  Synopsis           [required]
518
519  Description        [BlockSizeIndex(size) return the coded size for a block. ]
520
521  SideEffects        [required]
522
523  SeeAlso            [optional]
524
525  CommandName        [optional]           
526
527  CommandSynopsis    [optional] 
528
529  CommandArguments   [optional] 
530
531  CommandDescription [optional] 
532
533******************************************************************************/
534static int
535BlockSizeIndex(Cal_Address_t size)
536{
537  if (size < 1)
538    return (-1);
539  if (size > MAX_SIZE)
540    Cal_MemFatal("BlockSizeIndex: block size too large");
541  else
542    size+=HEADER_SIZE;
543  return (CeilingLog2(size));
544}
545
546
547/**Function********************************************************************
548
549  Synopsis           [required]
550
551  Description        [AddToFreeList(b) adds b to the appropriate free list. ]
552
553  SideEffects        [required]
554
555  SeeAlso            [optional]
556
557  CommandName        [optional]           
558
559  CommandSynopsis    [optional] 
560
561  CommandArguments   [optional] 
562
563  CommandDescription [optional] 
564
565******************************************************************************/
566static void
567AddToFreeList(Block b)
568{
569  int i;
570
571  i=b->sizeIndex;
572  if (!avail[i]){
573      b->next=b;
574      b->prev=b;
575      avail[i]=b;
576  }
577  else {
578    b->next=avail[i]->next;
579    avail[i]->next->prev=b;
580    avail[i]->next=b;
581    b->prev=avail[i];
582  }
583  b->used=0;
584}
585
586
587/**Function********************************************************************
588
589  Synopsis           [required]
590
591  Description        [RemoveFromFreeList(b) removes b from the free list which it is on. ]
592
593  SideEffects        [required]
594
595  SeeAlso            [optional]
596
597  CommandName        [optional]           
598
599  CommandSynopsis    [optional] 
600
601  CommandArguments   [optional] 
602
603  CommandDescription [optional] 
604
605******************************************************************************/
606static Block
607RemoveFromFreeList(Block b)
608{
609  int i;
610
611  i=b->sizeIndex;
612  if (b->next == b)
613    avail[i]=0;
614  else {
615    b->next->prev=b->prev;
616    b->prev->next=b->next;
617    if (avail[i] == b) avail[i]=b->next;
618  }
619  b->used=1;
620  return (b);
621}
622
623
624/**Function********************************************************************
625
626  Synopsis           [required]
627
628  Description        [Buddy(b) returns the Buddy block of b, or null if there is no  Buddy. ]
629
630  SideEffects        [required]
631
632  SeeAlso            [optional]
633
634  CommandName        [optional]           
635
636  CommandSynopsis    [optional] 
637
638  CommandArguments   [optional] 
639
640  CommandDescription [optional] 
641
642******************************************************************************/
643
644static Block
645Buddy(Block b)
646{
647  Cal_Address_t Buddy_offset;
648
649  Buddy_offset=(Cal_Address_t)(((Cal_Address_t)b-(Cal_Address_t)b->seg->baseAddress) ^
650                               ((Cal_Address_t)1 << b->sizeIndex));
651  if (Buddy_offset < b->seg->limit)
652    return ((Block)((Cal_Address_t)b->seg->baseAddress+Buddy_offset));
653  else
654    return ((Block)0);
655}
656
657
658/**Function********************************************************************
659
660  Synopsis           [required]
661
662  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. ]
663
664  SideEffects        [required]
665
666  SeeAlso            [optional]
667
668  CommandName        [optional]           
669
670  CommandSynopsis    [optional] 
671
672  CommandArguments   [optional] 
673
674  CommandDescription [optional] 
675
676******************************************************************************/
677static void
678TrimToSize(Block b, int sizeIndex)
679{
680  Block bb;
681
682  while (b->sizeIndex > sizeIndex) {
683    b->sizeIndex--;
684    bb=Buddy(b);
685    bb->sizeIndex=b->sizeIndex;
686    bb->seg=b->seg;
687    AddToFreeList(bb);
688  }
689}
690
691
692/**Function********************************************************************
693
694  Synopsis           [required]
695
696  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. ]
697
698  SideEffects        [required]
699
700  SeeAlso            [optional]
701
702  CommandName        [optional]           
703
704  CommandSynopsis    [optional] 
705
706  CommandArguments   [optional] 
707
708  CommandDescription [optional] 
709
710******************************************************************************/
711static void
712MergeAndFree(Block b)
713{
714  Block bb;
715 
716  for (bb=Buddy(b); bb && !bb->used && bb->sizeIndex == b->sizeIndex;
717       bb=Buddy(b)) { 
718    RemoveFromFreeList(bb);
719    if ((Cal_Address_t)bb < (Cal_Address_t)b) b=bb;
720    b->sizeIndex++;
721  }
722  AddToFreeList(b);
723}
Note: See TracBrowser for help on using the repository browser.