base/fast_alloc.hh

   1 /*
   2  * Copyright (c) 2003 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   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.
  15  *
  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.
  27  */
  28
  29 /*
  30  * This code was originally written by Steve Reinhardt as part of
  31  * the Wisconsin Wind Tunnel simulator.  Relicensed as part of M5
  32  * by permission.
  33  */
  34
  35 #ifndef __FAST_ALLOC_H__
  36 #define __FAST_ALLOC_H__
  37
  38 #include <stddef.h>
  39
  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.
  48
  49 // The static allocate() and deallocate() methods can also be called
  50 // directly if desired.
  51
  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
  61 // hierarchy.
  62
  63 // Uncomment this #define to track in-use objects
  64 // (for debugging memory leaks).
  65 //#define FAST_ALLOC_DEBUG
  66
  67 // Uncomment this #define to count news, deletes, and chunk allocations
  68 // (by bucket).
  69 // #define FAST_ALLOC_STATS
  70
  71 class FastAlloc {
  72   public:
  73
  74     static void *allocate(size_t);
  75     static void deallocate(void *, size_t);
  76
  77     void *operator new(size_t);
  78     void operator delete(void *, size_t);
  79
  80 #ifdef FAST_ALLOC_DEBUG
  81     FastAlloc();
  82     FastAlloc(FastAlloc*,FastAlloc*);   // for inUseHead, see below
  83     virtual ~FastAlloc();
  84 #else
  85     virtual ~FastAlloc() {}
  86 #endif
  87
  88   private:
  89
  90     // Max_Alloc_Size is the largest object that can be allocated with
  91     // this class.  There's no fundamental limit, but this limits the
  92     // size of the freeLists array.  Let's not make this really huge
  93     // like in Blizzard.
  94     static const int Max_Alloc_Size = 512;
  95
  96     // Alloc_Quantum is the difference in size between adjacent
  97     // buckets in the free list array.
  98     static const int Log2_Alloc_Quantum = 3;
  99     static const int Alloc_Quantum = (1 << Log2_Alloc_Quantum);
 100
 101     // Num_Buckets = bucketFor(Max_Alloc_Size) + 1
 102     static const int Num_Buckets =
 103         ((Max_Alloc_Size + Alloc_Quantum - 1) >> Log2_Alloc_Quantum) + 1;
 104
 105     // when we call new() for more structures, how many should we get?
 106     static const int Num_Structs_Per_New = 20;
 107
 108     static int bucketFor(size_t);
 109     static void *moreStructs(int bucket);
 110
 111     static void *freeLists[Num_Buckets];
 112
 113 #ifdef FAST_ALLOC_STATS
 114     static unsigned newCount[Num_Buckets];
 115     static unsigned deleteCount[Num_Buckets];
 116     static unsigned allocCount[Num_Buckets];
 117 #endif
 118
 119 #ifdef FAST_ALLOC_DEBUG
 120     // per-object debugging fields
 121     bool inUse;                 // in-use flag
 122     FastAlloc *inUsePrev;       // ptrs to build list of in-use objects
 123     FastAlloc *inUseNext;
 124
 125     // static (global) debugging vars
 126     static int numInUse;        // count in-use objects
 127     static FastAlloc inUseHead; // dummy head for list of in-use objects
 128
 129   public:
 130     // functions to dump debugging info (see fast_alloc.cc for C
 131     // versions that might be more agreeable to call from gdb)
 132     static void dump_summary();
 133     static void dump_oldest(int n);
 134 #endif
 135 };
 136
 137
 138 inline
 139 int FastAlloc::bucketFor(size_t sz)
 140 {
 141     return (sz + Alloc_Quantum - 1) >> Log2_Alloc_Quantum;
 142 }
 143
 144
 145 inline
 146 void *FastAlloc::allocate(size_t sz)
 147 {
 148     int b;
 149     void *p;
 150
 151     if (sz > Max_Alloc_Size)
 152         return (void *)::new char[sz];
 153
 154     b = bucketFor(sz);
 155     p = freeLists[b];
 156
 157     if (p)
 158         freeLists[b] = *(void **)p;
 159     else
 160         p = moreStructs(b);
 161
 162 #ifdef FAST_ALLOC_STATS
 163     ++newCount[b];
 164 #endif
 165
 166     return p;
 167 }
 168
 169
 170 inline
 171 void FastAlloc::deallocate(void *p, size_t sz)
 172 {
 173     int b;
 174
 175     if (sz > Max_Alloc_Size)
 176     {
 177         ::delete [] (char *)p;
 178         return;
 179     }
 180
 181     b = bucketFor(sz);
 182     *(void **)p = freeLists[b];
 183     freeLists[b] = p;
 184 #ifdef FAST_ALLOC_STATS
 185     ++deleteCount[b];
 186 #endif
 187 }
 188
 189
 190 inline
 191 void *FastAlloc::operator new(size_t sz)
 192 {
 193     return allocate(sz);
 194 }
 195
 196
 197 inline
 198 void FastAlloc::operator delete(void *p, size_t sz)
 199 {
 200     deallocate(p, sz);
 201 }
 202
 203 #endif // __FAST_ALLOC_H__