2 * Copyright (c) 2000-2001, 2003 The Regents of The University of Michigan
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * This code was originally written by Steve Reinhardt as part of
31 * the Wisconsin Wind Tunnel simulator. Relicensed as part of M5
35 #ifndef __FAST_ALLOC_H__
36 #define __FAST_ALLOC_H__
40 // Fast structure allocator. Designed for small objects that are
41 // frequently allocated and deallocated. This code is derived from the
42 // 'alloc_struct' package used in WWT and Blizzard. C++ provides a
43 // much nicer framework for the same optimization. The package is
44 // implemented as a class, FastAlloc. Allocation and deletion are
45 // performed using FastAlloc's new and delete operators. Any object
46 // that derives from the FastAlloc class will transparently use this
47 // allocation package.
49 // The static allocate() and deallocate() methods can also be called
50 // directly if desired.
52 // In order for derived classes to call delete with the correct
53 // structure size even when they are deallocated via a base-type
54 // pointer, they must have a virtual destructor. It is sufficient for
55 // FastAlloc to declare a virtual destructor (as it does); it is not
56 // required for derived classes to declare their own destructor. The
57 // compiler will automatically generate a virtual destructor for each
58 // derived class. However, it is more efficient if each derived class
59 // defines an inline destructor, so that the compiler can statically
60 // collapse the destructor call chain back up the inheritance
63 // Uncomment this #define to track in-use objects
64 // (for debugging memory leaks).
65 //#define FAST_ALLOC_DEBUG
67 // Uncomment this #define to count news, deletes, and chunk allocations
69 // #define FAST_ALLOC_STATS
81 static void *allocate(size_t);
82 static void deallocate(void *, size_t);
84 void *operator new(size_t);
85 void operator delete(void *, size_t);
87 #ifdef FAST_ALLOC_DEBUG
89 FastAlloc(FastAlloc*,FastAlloc*); // for inUseHead, see below
92 virtual ~FastAlloc() {}
97 // Max_Alloc_Size is the largest object that can be allocated with
98 // this class. There's no fundamental limit, but this limits the
99 // size of the freeLists array. Let's not make this really huge
101 static const int Max_Alloc_Size = 512;
103 // Alloc_Quantum is the difference in size between adjacent
104 // buckets in the free list array.
105 static const int Log2_Alloc_Quantum = 3;
106 static const int Alloc_Quantum = (1 << Log2_Alloc_Quantum);
108 // Num_Buckets = bucketFor(Max_Alloc_Size) + 1
109 static const int Num_Buckets =
110 ((Max_Alloc_Size + Alloc_Quantum - 1) >> Log2_Alloc_Quantum) + 1;
112 // when we call new() for more structures, how many should we get?
113 static const int Num_Structs_Per_New = 20;
115 static int bucketFor(size_t);
116 static void *moreStructs(int bucket);
118 static void *freeLists[Num_Buckets];
120 #ifdef FAST_ALLOC_STATS
121 static unsigned newCount[Num_Buckets];
122 static unsigned deleteCount[Num_Buckets];
123 static unsigned allocCount[Num_Buckets];
126 #ifdef FAST_ALLOC_DEBUG
127 // per-object debugging fields
128 bool inUse; // in-use flag
129 FastAlloc *inUsePrev; // ptrs to build list of in-use objects
130 FastAlloc *inUseNext;
132 // static (global) debugging vars
133 static int numInUse; // count in-use objects
134 static FastAlloc inUseHead; // dummy head for list of in-use objects
137 // functions to dump debugging info (see fast_alloc.cc for C
138 // versions that might be more agreeable to call from gdb)
139 static void dump_summary();
140 static void dump_oldest(int n);
146 int FastAlloc::bucketFor(size_t sz)
148 return (sz + Alloc_Quantum - 1) >> Log2_Alloc_Quantum;
153 void *FastAlloc::allocate(size_t sz)
158 if (sz > Max_Alloc_Size)
159 return (void *)::new char[sz];
165 freeLists[b] = *(void **)p;
169 #ifdef FAST_ALLOC_STATS
178 void FastAlloc::deallocate(void *p, size_t sz)
182 if (sz > Max_Alloc_Size)
184 ::delete [] (char *)p;
189 *(void **)p = freeLists[b];
191 #ifdef FAST_ALLOC_STATS
198 void *FastAlloc::operator new(size_t sz)
205 void FastAlloc::operator delete(void *p, size_t sz)
210 #endif // NO_FAST_ALLOC
212 #endif // __FAST_ALLOC_H__