2 * Copyright (c) 2000-2001, 2003-2005 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.
28 * Authors: Steve Reinhardt
32 * This code was originally written by Steve Reinhardt as part of
33 * the Wisconsin Wind Tunnel simulator. Relicensed as part of M5
37 #ifndef __FAST_ALLOC_H__
38 #define __FAST_ALLOC_H__
42 // Fast structure allocator. Designed for small objects that are
43 // frequently allocated and deallocated. This code is derived from the
44 // 'alloc_struct' package used in WWT and Blizzard. C++ provides a
45 // much nicer framework for the same optimization. The package is
46 // implemented as a class, FastAlloc. Allocation and deletion are
47 // performed using FastAlloc's new and delete operators. Any object
48 // that derives from the FastAlloc class will transparently use this
49 // allocation package.
51 // The static allocate() and deallocate() methods can also be called
52 // directly if desired.
54 // In order for derived classes to call delete with the correct
55 // structure size even when they are deallocated via a base-type
56 // pointer, they must have a virtual destructor. It is sufficient for
57 // FastAlloc to declare a virtual destructor (as it does); it is not
58 // required for derived classes to declare their own destructor. The
59 // compiler will automatically generate a virtual destructor for each
60 // derived class. However, it is more efficient if each derived class
61 // defines an inline destructor, so that the compiler can statically
62 // collapse the destructor call chain back up the inheritance
65 // Uncomment this #define to track in-use objects
66 // (for debugging memory leaks).
67 //#define FAST_ALLOC_DEBUG
69 // Uncomment this #define to count news, deletes, and chunk allocations
71 // #define FAST_ALLOC_STATS
73 #include "config/no_fast_alloc.hh"
85 static void *allocate(size_t);
86 static void deallocate(void *, size_t);
88 void *operator new(size_t);
89 void operator delete(void *, size_t);
91 #ifdef FAST_ALLOC_DEBUG
93 FastAlloc(FastAlloc*,FastAlloc*); // for inUseHead, see below
96 virtual ~FastAlloc() {}
101 // Max_Alloc_Size is the largest object that can be allocated with
102 // this class. There's no fundamental limit, but this limits the
103 // size of the freeLists array. Let's not make this really huge
105 static const int Max_Alloc_Size = 512;
107 // Alloc_Quantum is the difference in size between adjacent
108 // buckets in the free list array.
109 static const int Log2_Alloc_Quantum = 3;
110 static const int Alloc_Quantum = (1 << Log2_Alloc_Quantum);
112 // Num_Buckets = bucketFor(Max_Alloc_Size) + 1
113 static const int Num_Buckets =
114 ((Max_Alloc_Size + Alloc_Quantum - 1) >> Log2_Alloc_Quantum) + 1;
116 // when we call new() for more structures, how many should we get?
117 static const int Num_Structs_Per_New = 20;
119 static int bucketFor(size_t);
120 static void *moreStructs(int bucket);
122 static void *freeLists[Num_Buckets];
124 #ifdef FAST_ALLOC_STATS
125 static unsigned newCount[Num_Buckets];
126 static unsigned deleteCount[Num_Buckets];
127 static unsigned allocCount[Num_Buckets];
130 #ifdef FAST_ALLOC_DEBUG
131 // per-object debugging fields
132 bool inUse; // in-use flag
133 FastAlloc *inUsePrev; // ptrs to build list of in-use objects
134 FastAlloc *inUseNext;
136 // static (global) debugging vars
137 static int numInUse; // count in-use objects
138 static FastAlloc inUseHead; // dummy head for list of in-use objects
141 // functions to dump debugging info (see fast_alloc.cc for C
142 // versions that might be more agreeable to call from gdb)
143 static void dump_summary();
144 static void dump_oldest(int n);
150 int FastAlloc::bucketFor(size_t sz)
152 return (sz + Alloc_Quantum - 1) >> Log2_Alloc_Quantum;
157 void *FastAlloc::allocate(size_t sz)
162 if (sz > Max_Alloc_Size)
163 return (void *)::new char[sz];
169 freeLists[b] = *(void **)p;
173 #ifdef FAST_ALLOC_STATS
182 void FastAlloc::deallocate(void *p, size_t sz)
186 if (sz > Max_Alloc_Size)
188 ::delete [] (char *)p;
193 *(void **)p = freeLists[b];
195 #ifdef FAST_ALLOC_STATS
202 void *FastAlloc::operator new(size_t sz)
209 void FastAlloc::operator delete(void *p, size_t sz)
214 #endif // NO_FAST_ALLOC
216 #endif // __FAST_ALLOC_H__