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 __BASE_FAST_ALLOC_HH__
38 #define __BASE_FAST_ALLOC_HH__
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 #include "config/no_fast_alloc.hh"
66 #include "config/fast_alloc_debug.hh"
67 #include "config/fast_alloc_stats.hh"
78 #include "base/types.hh"
84 static void *allocate(size_t);
85 static void deallocate(void *, size_t);
87 void *operator new(size_t);
88 void operator delete(void *, size_t);
92 FastAlloc(FastAlloc *, FastAlloc *); // for inUseHead, see below
95 virtual ~FastAlloc() {}
100 // Max_Alloc_Size is the largest object that can be allocated with
101 // this class. There's no fundamental limit, but this limits the
102 // size of the freeLists array. Let's not make this really huge
104 static const size_t Max_Alloc_Size = 512;
106 // Alloc_Quantum is the difference in size between adjacent
107 // buckets in the free list array.
108 static const int Log2_Alloc_Quantum = 3;
109 static const int Alloc_Quantum = (1 << Log2_Alloc_Quantum);
111 // Num_Buckets = bucketFor(Max_Alloc_Size) + 1
112 static const int Num_Buckets =
113 ((Max_Alloc_Size + Alloc_Quantum - 1) >> Log2_Alloc_Quantum) + 1;
115 // when we call new() for more structures, how many should we get?
116 static const int Num_Structs_Per_New = 20;
118 static int bucketFor(size_t);
119 static void *moreStructs(int bucket);
121 static void *freeLists[Num_Buckets];
124 static unsigned newCount[Num_Buckets];
125 static unsigned deleteCount[Num_Buckets];
126 static unsigned allocCount[Num_Buckets];
130 // per-object debugging fields
131 bool inUse; // in-use flag
132 FastAlloc *inUsePrev; // ptrs to build list of in-use objects
133 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);
145 static void dump_oldest_of_type(int n, const char *type_name);
150 FastAlloc::bucketFor(size_t sz)
152 return (sz + Alloc_Quantum - 1) >> Log2_Alloc_Quantum;
156 FastAlloc::allocate(size_t sz)
161 if (sz > Max_Alloc_Size)
162 return (void *)::new char[sz];
168 freeLists[b] = *(void **)p;
180 FastAlloc::deallocate(void *p, size_t sz)
184 if (sz > Max_Alloc_Size) {
185 ::delete [] (char *)p;
190 *(void **)p = freeLists[b];
198 FastAlloc::operator new(size_t sz)
204 FastAlloc::operator delete(void *p, size_t sz)
209 #endif // NO_FAST_ALLOC
211 #endif // __BASE_FAST_ALLOC_HH__