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 #include "config/no_fast_alloc.hh"
66 #include "config/fast_alloc_debug.hh"
67 #include "config/fast_alloc_stats.hh"
79 static void *allocate(size_t);
80 static void deallocate(void *, size_t);
82 void *operator new(size_t);
83 void operator delete(void *, size_t);
87 FastAlloc(FastAlloc*,FastAlloc*); // for inUseHead, see below
90 virtual ~FastAlloc() {}
95 // Max_Alloc_Size is the largest object that can be allocated with
96 // this class. There's no fundamental limit, but this limits the
97 // size of the freeLists array. Let's not make this really huge
99 static const int Max_Alloc_Size = 512;
101 // Alloc_Quantum is the difference in size between adjacent
102 // buckets in the free list array.
103 static const int Log2_Alloc_Quantum = 3;
104 static const int Alloc_Quantum = (1 << Log2_Alloc_Quantum);
106 // Num_Buckets = bucketFor(Max_Alloc_Size) + 1
107 static const int Num_Buckets =
108 ((Max_Alloc_Size + Alloc_Quantum - 1) >> Log2_Alloc_Quantum) + 1;
110 // when we call new() for more structures, how many should we get?
111 static const int Num_Structs_Per_New = 20;
113 static int bucketFor(size_t);
114 static void *moreStructs(int bucket);
116 static void *freeLists[Num_Buckets];
119 static unsigned newCount[Num_Buckets];
120 static unsigned deleteCount[Num_Buckets];
121 static unsigned allocCount[Num_Buckets];
125 // per-object debugging fields
126 bool inUse; // in-use flag
127 FastAlloc *inUsePrev; // ptrs to build list of in-use objects
128 FastAlloc *inUseNext;
130 // static (global) debugging vars
131 static int numInUse; // count in-use objects
132 static FastAlloc inUseHead; // dummy head for list of in-use objects
135 // functions to dump debugging info (see fast_alloc.cc for C
136 // versions that might be more agreeable to call from gdb)
137 static void dump_summary();
138 static void dump_oldest(int n);
144 int FastAlloc::bucketFor(size_t sz)
146 return (sz + Alloc_Quantum - 1) >> Log2_Alloc_Quantum;
151 void *FastAlloc::allocate(size_t sz)
156 if (sz > Max_Alloc_Size)
157 return (void *)::new char[sz];
163 freeLists[b] = *(void **)p;
176 void FastAlloc::deallocate(void *p, size_t sz)
180 if (sz > Max_Alloc_Size)
182 ::delete [] (char *)p;
187 *(void **)p = freeLists[b];
196 void *FastAlloc::operator new(size_t sz)
203 void FastAlloc::operator delete(void *p, size_t sz)
208 #endif // NO_FAST_ALLOC
210 #endif // __FAST_ALLOC_H__