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