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
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 struct Gia_MmFixed_t_
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
50 struct Gia_MmFlex_t_
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
68 struct Gia_MmStep_t_
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 ***********************************************************************/
Gia_MmFixedStart(int nEntrySize,int nEntriesMax)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 ***********************************************************************/
Gia_MmFixedStop(Gia_MmFixed_t * p,int fVerbose)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",
142 p->nEntriesUsed, p->nEntriesMax, p->nEntrySize * p->nEntriesUsed, p->nMemoryAlloc );
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 ***********************************************************************/
Gia_MmFixedEntryFetch(Gia_MmFixed_t * p)161 char * Gia_MmFixedEntryFetch( Gia_MmFixed_t * p )
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 ***********************************************************************/
Gia_MmFixedEntryRecycle(Gia_MmFixed_t * p,char * pEntry)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 ***********************************************************************/
Gia_MmFixedRestart(Gia_MmFixed_t * p)232 void Gia_MmFixedRestart( Gia_MmFixed_t * p )
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 ***********************************************************************/
Gia_MmFixedReadMemUsage(Gia_MmFixed_t * p)271 int Gia_MmFixedReadMemUsage( Gia_MmFixed_t * p )
272 {
273 return p->nMemoryAlloc;
274 }
275
276 /**Function*************************************************************
277
278 Synopsis []
279
280 Description []
281
282 SideEffects []
283
284 SeeAlso []
285
286 ***********************************************************************/
Gia_MmFixedReadMaxEntriesUsed(Gia_MmFixed_t * p)287 int Gia_MmFixedReadMaxEntriesUsed( Gia_MmFixed_t * p )
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 ***********************************************************************/
Gia_MmFlexStart()305 Gia_MmFlex_t * Gia_MmFlexStart()
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 ***********************************************************************/
Gia_MmFlexStop(Gia_MmFlex_t * p,int fVerbose)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",
347 p->nEntriesUsed, p->nMemoryUsed, p->nMemoryAlloc );
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 ***********************************************************************/
Gia_MmFlexEntryFetch(Gia_MmFlex_t * p,int nBytes)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 ***********************************************************************/
Gia_MmFlexRestart(Gia_MmFlex_t * p)411 void Gia_MmFlexRestart( Gia_MmFlex_t * p )
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 ***********************************************************************/
Gia_MmFlexReadMemUsage(Gia_MmFlex_t * p)439 int Gia_MmFlexReadMemUsage( Gia_MmFlex_t * p )
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 ***********************************************************************/
Gia_MmStepStart(int nSteps)468 Gia_MmStep_t * Gia_MmStepStart( int nSteps )
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 ***********************************************************************/
Gia_MmStepStop(Gia_MmStep_t * p,int fVerbose)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 ***********************************************************************/
Gia_MmStepEntryFetch(Gia_MmStep_t * p,int nBytes)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 ***********************************************************************/
Gia_MmStepEntryRecycle(Gia_MmStep_t * p,char * pEntry,int nBytes)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 ***********************************************************************/
Gia_MmStepReadMemUsage(Gia_MmStep_t * p)586 int Gia_MmStepReadMemUsage( Gia_MmStep_t * p )
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 ////////////////////////////////////////////////////////////////////////
597 ABC_NAMESPACE_IMPL_END
598
599