abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaMem.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [giaMem.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [AIG package.]
8 
9  Synopsis [Memory managers.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - April 28, 2007.]
16 
17  Revision [$Id: giaMem.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "gia.h"
22 
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
31 {
32  // information about individual entries
33  int nEntrySize; // the size of one entry
34  int nEntriesAlloc; // the total number of entries allocated
35  int nEntriesUsed; // the number of entries in use
36  int nEntriesMax; // the max number of entries in use
37  char * pEntriesFree; // the linked list of free entries
38 
39  // this is where the memory is stored
40  int nChunkSize; // the size of one chunk
41  int nChunksAlloc; // the maximum number of memory chunks
42  int nChunks; // the current number of memory chunks
43  char ** pChunks; // the allocated memory
44 
45  // statistics
46  int nMemoryUsed; // memory used in the allocated entries
47  int nMemoryAlloc; // memory allocated
48 };
49 
51 {
52  // information about individual entries
53  int nEntriesUsed; // the number of entries allocated
54  char * pCurrent; // the current pointer to free memory
55  char * pEnd; // the first entry outside the free memory
56 
57  // this is where the memory is stored
58  int nChunkSize; // the size of one chunk
59  int nChunksAlloc; // the maximum number of memory chunks
60  int nChunks; // the current number of memory chunks
61  char ** pChunks; // the allocated memory
62 
63  // statistics
64  int nMemoryUsed; // memory used in the allocated entries
65  int nMemoryAlloc; // memory allocated
66 };
67 
69 {
70  int nMems; // the number of fixed memory managers employed
71  Gia_MmFixed_t ** pMems; // memory managers: 2^1 words, 2^2 words, etc
72  int nMapSize; // the size of the memory array
73  Gia_MmFixed_t ** pMap; // maps the number of bytes into its memory manager
74  // additional memory chunks
75  int nChunksAlloc; // the maximum number of memory chunks
76  int nChunks; // the current number of memory chunks
77  char ** pChunks; // the allocated memory
78 };
79 
80 ////////////////////////////////////////////////////////////////////////
81 /// FUNCTION DEFINITIONS ///
82 ////////////////////////////////////////////////////////////////////////
83 
84 /**Function*************************************************************
85 
86  Synopsis [Allocates memory pieces of fixed size.]
87 
88  Description [The size of the chunk is computed as the minimum of
89  1024 entries and 64K. Can only work with entry size at least 4 byte long.]
90 
91  SideEffects []
92 
93  SeeAlso []
94 
95 ***********************************************************************/
96 Gia_MmFixed_t * Gia_MmFixedStart( int nEntrySize, int nEntriesMax )
97 {
98  Gia_MmFixed_t * p;
99 
100  p = ABC_ALLOC( Gia_MmFixed_t, 1 );
101  memset( p, 0, sizeof(Gia_MmFixed_t) );
102 
103  p->nEntrySize = nEntrySize;
104  p->nEntriesAlloc = 0;
105  p->nEntriesUsed = 0;
106  p->pEntriesFree = NULL;
107 
108  p->nChunkSize = nEntriesMax / 8;
109  if ( p->nChunkSize < 8 )
110  p->nChunkSize = 8;
111 
112  p->nChunksAlloc = 64;
113  p->nChunks = 0;
114  p->pChunks = ABC_ALLOC( char *, p->nChunksAlloc );
115 
116  p->nMemoryUsed = 0;
117  p->nMemoryAlloc = 0;
118  return p;
119 }
120 
121 /**Function*************************************************************
122 
123  Synopsis []
124 
125  Description []
126 
127  SideEffects []
128 
129  SeeAlso []
130 
131 ***********************************************************************/
132 void Gia_MmFixedStop( Gia_MmFixed_t * p, int fVerbose )
133 {
134  int i;
135  if ( p == NULL )
136  return;
137  if ( fVerbose )
138  {
139  printf( "Fixed memory manager: Entry = %5d. Chunk = %5d. Chunks used = %5d.\n",
140  p->nEntrySize, p->nChunkSize, p->nChunks );
141  printf( " Entries used = %8d. Entries peak = %8d. Memory used = %8d. Memory alloc = %8d.\n",
143  }
144  for ( i = 0; i < p->nChunks; i++ )
145  ABC_FREE( p->pChunks[i] );
146  ABC_FREE( p->pChunks );
147  ABC_FREE( p );
148 }
149 
150 /**Function*************************************************************
151 
152  Synopsis []
153 
154  Description []
155 
156  SideEffects []
157 
158  SeeAlso []
159 
160 ***********************************************************************/
162 {
163  char * pTemp;
164  int i;
165 
166  // check if there are still free entries
167  if ( p->nEntriesUsed == p->nEntriesAlloc )
168  { // need to allocate more entries
169  assert( p->pEntriesFree == NULL );
170  if ( p->nChunks == p->nChunksAlloc )
171  {
172  p->nChunksAlloc *= 2;
173  p->pChunks = ABC_REALLOC( char *, p->pChunks, p->nChunksAlloc );
174  }
175  p->pEntriesFree = ABC_ALLOC( char, p->nEntrySize * p->nChunkSize );
176  p->nMemoryAlloc += p->nEntrySize * p->nChunkSize;
177  // transform these entries into a linked list
178  pTemp = p->pEntriesFree;
179  for ( i = 1; i < p->nChunkSize; i++ )
180  {
181  *((char **)pTemp) = pTemp + p->nEntrySize;
182  pTemp += p->nEntrySize;
183  }
184  // set the last link
185  *((char **)pTemp) = NULL;
186  // add the chunk to the chunk storage
187  p->pChunks[ p->nChunks++ ] = p->pEntriesFree;
188  // add to the number of entries allocated
189  p->nEntriesAlloc += p->nChunkSize;
190  }
191  // incrememt the counter of used entries
192  p->nEntriesUsed++;
193  if ( p->nEntriesMax < p->nEntriesUsed )
194  p->nEntriesMax = p->nEntriesUsed;
195  // return the first entry in the free entry list
196  pTemp = p->pEntriesFree;
197  p->pEntriesFree = *((char **)pTemp);
198  return pTemp;
199 }
200 
201 /**Function*************************************************************
202 
203  Synopsis []
204 
205  Description []
206 
207  SideEffects []
208 
209  SeeAlso []
210 
211 ***********************************************************************/
212 void Gia_MmFixedEntryRecycle( Gia_MmFixed_t * p, char * pEntry )
213 {
214  // decrement the counter of used entries
215  p->nEntriesUsed--;
216  // add the entry to the linked list of free entries
217  *((char **)pEntry) = p->pEntriesFree;
218  p->pEntriesFree = pEntry;
219 }
220 
221 /**Function*************************************************************
222 
223  Synopsis []
224 
225  Description [Relocates all the memory except the first chunk.]
226 
227  SideEffects []
228 
229  SeeAlso []
230 
231 ***********************************************************************/
233 {
234  int i;
235  char * pTemp;
236  if ( p->nChunks == 0 )
237  return;
238  // deallocate all chunks except the first one
239  for ( i = 1; i < p->nChunks; i++ )
240  ABC_FREE( p->pChunks[i] );
241  p->nChunks = 1;
242  // transform these entries into a linked list
243  pTemp = p->pChunks[0];
244  for ( i = 1; i < p->nChunkSize; i++ )
245  {
246  *((char **)pTemp) = pTemp + p->nEntrySize;
247  pTemp += p->nEntrySize;
248  }
249  // set the last link
250  *((char **)pTemp) = NULL;
251  // set the free entry list
252  p->pEntriesFree = p->pChunks[0];
253  // set the correct statistics
254  p->nMemoryAlloc = p->nEntrySize * p->nChunkSize;
255  p->nMemoryUsed = 0;
256  p->nEntriesAlloc = p->nChunkSize;
257  p->nEntriesUsed = 0;
258 }
259 
260 /**Function*************************************************************
261 
262  Synopsis []
263 
264  Description []
265 
266  SideEffects []
267 
268  SeeAlso []
269 
270 ***********************************************************************/
272 {
273  return p->nMemoryAlloc;
274 }
275 
276 /**Function*************************************************************
277 
278  Synopsis []
279 
280  Description []
281 
282  SideEffects []
283 
284  SeeAlso []
285 
286 ***********************************************************************/
288 {
289  return p->nEntriesMax;
290 }
291 
292 
293 
294 /**Function*************************************************************
295 
296  Synopsis [Allocates entries of flexible size.]
297 
298  Description [Can only work with entry size at least 4 byte long.]
299 
300  SideEffects []
301 
302  SeeAlso []
303 
304 ***********************************************************************/
306 {
307  Gia_MmFlex_t * p;
308 
309  p = ABC_ALLOC( Gia_MmFlex_t, 1 );
310  memset( p, 0, sizeof(Gia_MmFlex_t) );
311 
312  p->nEntriesUsed = 0;
313  p->pCurrent = NULL;
314  p->pEnd = NULL;
315 
316  p->nChunkSize = (1 << 18);
317  p->nChunksAlloc = 64;
318  p->nChunks = 0;
319  p->pChunks = ABC_ALLOC( char *, p->nChunksAlloc );
320 
321  p->nMemoryUsed = 0;
322  p->nMemoryAlloc = 0;
323  return p;
324 }
325 
326 /**Function*************************************************************
327 
328  Synopsis []
329 
330  Description []
331 
332  SideEffects []
333 
334  SeeAlso []
335 
336 ***********************************************************************/
337 void Gia_MmFlexStop( Gia_MmFlex_t * p, int fVerbose )
338 {
339  int i;
340  if ( p == NULL )
341  return;
342  if ( fVerbose )
343  {
344  printf( "Flexible memory manager: Chunk size = %d. Chunks used = %d.\n",
345  p->nChunkSize, p->nChunks );
346  printf( " Entries used = %d. Memory used = %d. Memory alloc = %d.\n",
348  }
349  for ( i = 0; i < p->nChunks; i++ )
350  ABC_FREE( p->pChunks[i] );
351  ABC_FREE( p->pChunks );
352  ABC_FREE( p );
353 }
354 
355 /**Function*************************************************************
356 
357  Synopsis []
358 
359  Description []
360 
361  SideEffects []
362 
363  SeeAlso []
364 
365 ***********************************************************************/
366 char * Gia_MmFlexEntryFetch( Gia_MmFlex_t * p, int nBytes )
367 {
368  char * pTemp;
369  // check if there are still free entries
370  if ( p->pCurrent == NULL || p->pCurrent + nBytes > p->pEnd )
371  { // need to allocate more entries
372  if ( p->nChunks == p->nChunksAlloc )
373  {
374  p->nChunksAlloc *= 2;
375  p->pChunks = ABC_REALLOC( char *, p->pChunks, p->nChunksAlloc );
376  }
377  if ( nBytes > p->nChunkSize )
378  {
379  // resize the chunk size if more memory is requested than it can give
380  // (ideally, this should never happen)
381  p->nChunkSize = 2 * nBytes;
382  }
383  p->pCurrent = ABC_ALLOC( char, p->nChunkSize );
384  p->pEnd = p->pCurrent + p->nChunkSize;
385  p->nMemoryAlloc += p->nChunkSize;
386  // add the chunk to the chunk storage
387  p->pChunks[ p->nChunks++ ] = p->pCurrent;
388  }
389  assert( p->pCurrent + nBytes <= p->pEnd );
390  // increment the counter of used entries
391  p->nEntriesUsed++;
392  // keep track of the memory used
393  p->nMemoryUsed += nBytes;
394  // return the next entry
395  pTemp = p->pCurrent;
396  p->pCurrent += nBytes;
397  return pTemp;
398 }
399 
400 /**Function*************************************************************
401 
402  Synopsis []
403 
404  Description [Relocates all the memory except the first chunk.]
405 
406  SideEffects []
407 
408  SeeAlso []
409 
410 ***********************************************************************/
412 {
413  int i;
414  if ( p->nChunks == 0 )
415  return;
416  // deallocate all chunks except the first one
417  for ( i = 1; i < p->nChunks; i++ )
418  ABC_FREE( p->pChunks[i] );
419  p->nChunks = 1;
420  p->nMemoryAlloc = p->nChunkSize;
421  // transform these entries into a linked list
422  p->pCurrent = p->pChunks[0];
423  p->pEnd = p->pCurrent + p->nChunkSize;
424  p->nEntriesUsed = 0;
425  p->nMemoryUsed = 0;
426 }
427 
428 /**Function*************************************************************
429 
430  Synopsis []
431 
432  Description []
433 
434  SideEffects []
435 
436  SeeAlso []
437 
438 ***********************************************************************/
440 {
441  return p->nMemoryUsed;
442 }
443 
444 
445 
446 
447 
448 /**Function*************************************************************
449 
450  Synopsis [Starts the hierarchical memory manager.]
451 
452  Description [This manager can allocate entries of any size.
453  Iternally they are mapped into the entries with the number of bytes
454  equal to the power of 2. The smallest entry size is 8 bytes. The
455  next one is 16 bytes etc. So, if the user requests 6 bytes, he gets
456  8 byte entry. If we asks for 25 bytes, he gets 32 byte entry etc.
457  The input parameters "nSteps" says how many fixed memory managers
458  are employed internally. Calling this procedure with nSteps equal
459  to 10 results in 10 hierarchically arranged internal memory managers,
460  which can allocate up to 4096 (1Kb) entries. Requests for larger
461  entries are handed over to malloc() and then ABC_FREE()ed.]
462 
463  SideEffects []
464 
465  SeeAlso []
466 
467 ***********************************************************************/
469 {
470  Gia_MmStep_t * p;
471  int i, k;
472  p = ABC_ALLOC( Gia_MmStep_t, 1 );
473  memset( p, 0, sizeof(Gia_MmStep_t) );
474  p->nMems = nSteps;
475  // start the fixed memory managers
476  p->pMems = ABC_ALLOC( Gia_MmFixed_t *, p->nMems );
477  for ( i = 0; i < p->nMems; i++ )
478  p->pMems[i] = Gia_MmFixedStart( (8<<i), (1<<13) );
479  // set up the mapping of the required memory size into the corresponding manager
480  p->nMapSize = (4<<p->nMems);
481  p->pMap = ABC_ALLOC( Gia_MmFixed_t *, p->nMapSize+1 );
482  p->pMap[0] = NULL;
483  for ( k = 1; k <= 4; k++ )
484  p->pMap[k] = p->pMems[0];
485  for ( i = 0; i < p->nMems; i++ )
486  for ( k = (4<<i)+1; k <= (8<<i); k++ )
487  p->pMap[k] = p->pMems[i];
488 //for ( i = 1; i < 100; i ++ )
489 //printf( "%10d: size = %10d\n", i, p->pMap[i]->nEntrySize );
490  p->nChunksAlloc = 64;
491  p->nChunks = 0;
492  p->pChunks = ABC_ALLOC( char *, p->nChunksAlloc );
493  return p;
494 }
495 
496 /**Function*************************************************************
497 
498  Synopsis [Stops the memory manager.]
499 
500  Description []
501 
502  SideEffects []
503 
504  SeeAlso []
505 
506 ***********************************************************************/
507 void Gia_MmStepStop( Gia_MmStep_t * p, int fVerbose )
508 {
509  int i;
510  for ( i = 0; i < p->nMems; i++ )
511  Gia_MmFixedStop( p->pMems[i], fVerbose );
512  if ( p->nChunksAlloc )
513  {
514  for ( i = 0; i < p->nChunks; i++ )
515  ABC_FREE( p->pChunks[i] );
516  ABC_FREE( p->pChunks );
517  }
518  ABC_FREE( p->pMems );
519  ABC_FREE( p->pMap );
520  ABC_FREE( p );
521 }
522 
523 /**Function*************************************************************
524 
525  Synopsis [Creates the entry.]
526 
527  Description []
528 
529  SideEffects []
530 
531  SeeAlso []
532 
533 ***********************************************************************/
534 char * Gia_MmStepEntryFetch( Gia_MmStep_t * p, int nBytes )
535 {
536  if ( nBytes == 0 )
537  return NULL;
538  if ( nBytes > p->nMapSize )
539  {
540  if ( p->nChunks == p->nChunksAlloc )
541  {
542  p->nChunksAlloc *= 2;
543  p->pChunks = ABC_REALLOC( char *, p->pChunks, p->nChunksAlloc );
544  }
545  p->pChunks[ p->nChunks++ ] = ABC_ALLOC( char, nBytes );
546  return p->pChunks[p->nChunks-1];
547  }
548  return Gia_MmFixedEntryFetch( p->pMap[nBytes] );
549 }
550 
551 
552 /**Function*************************************************************
553 
554  Synopsis [Recycles the entry.]
555 
556  Description []
557 
558  SideEffects []
559 
560  SeeAlso []
561 
562 ***********************************************************************/
563 void Gia_MmStepEntryRecycle( Gia_MmStep_t * p, char * pEntry, int nBytes )
564 {
565  if ( nBytes == 0 )
566  return;
567  if ( nBytes > p->nMapSize )
568  {
569 // ABC_FREE( pEntry );
570  return;
571  }
572  Gia_MmFixedEntryRecycle( p->pMap[nBytes], pEntry );
573 }
574 
575 /**Function*************************************************************
576 
577  Synopsis []
578 
579  Description []
580 
581  SideEffects []
582 
583  SeeAlso []
584 
585 ***********************************************************************/
587 {
588  int i, nMemTotal = 0;
589  for ( i = 0; i < p->nMems; i++ )
590  nMemTotal += p->pMems[i]->nMemoryAlloc;
591  return nMemTotal;
592 }
593 
594 ////////////////////////////////////////////////////////////////////////
595 /// END OF FILE ///
596 ////////////////////////////////////////////////////////////////////////
598 
char * memset()
char ** pChunks
Definition: giaMem.c:61
int nEntriesAlloc
Definition: giaMem.c:34
int nChunks
Definition: giaMem.c:60
Gia_MmFixed_t ** pMap
Definition: giaMem.c:73
void Gia_MmFixedEntryRecycle(Gia_MmFixed_t *p, char *pEntry)
Definition: giaMem.c:212
int nEntriesUsed
Definition: giaMem.c:35
char * Gia_MmFlexEntryFetch(Gia_MmFlex_t *p, int nBytes)
Definition: giaMem.c:366
int Gia_MmStepReadMemUsage(Gia_MmStep_t *p)
Definition: giaMem.c:586
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Gia_MmStep_t * Gia_MmStepStart(int nSteps)
Definition: giaMem.c:468
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
char * pCurrent
Definition: giaMem.c:54
int nMemoryUsed
Definition: giaMem.c:64
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
char * Gia_MmFixedEntryFetch(Gia_MmFixed_t *p)
Definition: giaMem.c:161
int nChunksAlloc
Definition: giaMem.c:41
Gia_MmFixed_t ** pMems
Definition: giaMem.c:71
int nEntriesMax
Definition: giaMem.c:36
for(p=first;p->value< newval;p=p->next)
int nChunkSize
Definition: giaMem.c:58
void Gia_MmFlexStop(Gia_MmFlex_t *p, int fVerbose)
Definition: giaMem.c:337
void Gia_MmFixedRestart(Gia_MmFixed_t *p)
Definition: giaMem.c:232
void Gia_MmStepStop(Gia_MmStep_t *p, int fVerbose)
Definition: giaMem.c:507
void Gia_MmStepEntryRecycle(Gia_MmStep_t *p, char *pEntry, int nBytes)
Definition: giaMem.c:563
int Gia_MmFixedReadMemUsage(Gia_MmFixed_t *p)
Definition: giaMem.c:271
int nMemoryAlloc
Definition: giaMem.c:65
int nMems
Definition: giaMem.c:70
int nMapSize
Definition: giaMem.c:72
Gia_MmFixed_t * Gia_MmFixedStart(int nEntrySize, int nEntriesMax)
FUNCTION DEFINITIONS ///.
Definition: giaMem.c:96
Gia_MmFlex_t * Gia_MmFlexStart()
Definition: giaMem.c:305
int nMemoryUsed
Definition: giaMem.c:46
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
int nEntrySize
Definition: giaMem.c:33
int nChunks
Definition: giaMem.c:42
char * pEnd
Definition: giaMem.c:55
void Gia_MmFlexRestart(Gia_MmFlex_t *p)
Definition: giaMem.c:411
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
int Gia_MmFixedReadMaxEntriesUsed(Gia_MmFixed_t *p)
Definition: giaMem.c:287
char ** pChunks
Definition: giaMem.c:43
int nChunks
Definition: giaMem.c:76
char * pEntriesFree
Definition: giaMem.c:37
int Gia_MmFlexReadMemUsage(Gia_MmFlex_t *p)
Definition: giaMem.c:439
char * Gia_MmStepEntryFetch(Gia_MmStep_t *p, int nBytes)
Definition: giaMem.c:534
int nChunksAlloc
Definition: giaMem.c:59
#define ABC_FREE(obj)
Definition: abc_global.h:232
char ** pChunks
Definition: giaMem.c:77
int nEntriesUsed
Definition: giaMem.c:53
int nChunksAlloc
Definition: giaMem.c:75
int nChunkSize
Definition: giaMem.c:40
DECLARATIONS ///.
Definition: giaMem.c:30
#define assert(ex)
Definition: util_old.h:213
int nMemoryAlloc
Definition: giaMem.c:47
void Gia_MmFixedStop(Gia_MmFixed_t *p, int fVerbose)
Definition: giaMem.c:132