src/base/fast_alloc.hh

   1 /*
   2  * Copyright (c) 2000-2001, 2003-2005 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  * Authors: Steve Reinhardt
  29  */
  30
  31 /*
  32  * This code was originally written by Steve Reinhardt as part of
  33  * the Wisconsin Wind Tunnel simulator.  Relicensed as part of M5
  34  * by permission.
  35  */
  36
  37 #ifndef __BASE_FAST_ALLOC_HH__
  38 #define __BASE_FAST_ALLOC_HH__
  39
  40 #include <cstddef>
  41
  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.
  50
  51 // The static allocate() and deallocate() methods can also be called
  52 // directly if desired.
  53
  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
  63 // hierarchy.
  64
  65 #include "config/fast_alloc_stats.hh"
  66 #include "config/force_fast_alloc.hh"
  67 #include "config/no_fast_alloc.hh"
  68
  69 // By default, we want to enable FastAlloc in any build other than
  70 // m5.debug.  (FastAlloc's reuse policies can mask allocation bugs, so
  71 // we typically want it disabled when debugging.)  Set
  72 // FORCE_FAST_ALLOC to enable even when debugging, and set
  73 // NO_FAST_ALLOC to disable even in non-debug builds.
  74 #define USE_FAST_ALLOC \
  75     (FORCE_FAST_ALLOC || (!defined(DEBUG) && !NO_FAST_ALLOC))
  76
  77 #if !USE_FAST_ALLOC
  78
  79 class FastAlloc
  80 {
  81 };
  82
  83 #else
  84
  85 class FastAlloc
  86 {
  87   public:
  88     static void *allocate(size_t);
  89     static void deallocate(void *, size_t);
  90
  91     void *operator new(size_t);
  92     void operator delete(void *, size_t);
  93
  94     virtual ~FastAlloc() {}
  95
  96   private:
  97
  98     // Max_Alloc_Size is the largest object that can be allocated with
  99     // this class.  There's no fundamental limit, but this limits the
 100     // size of the freeLists array.  Let's not make this really huge
 101     // like in Blizzard.
 102     static const size_t Max_Alloc_Size = 512;
 103
 104     // Alloc_Quantum is the difference in size between adjacent
 105     // buckets in the free list array.
 106     static const int Log2_Alloc_Quantum = 3;
 107     static const int Alloc_Quantum = (1 << Log2_Alloc_Quantum);
 108
 109     // Num_Buckets = bucketFor(Max_Alloc_Size) + 1
 110     static const int Num_Buckets =
 111         ((Max_Alloc_Size + Alloc_Quantum - 1) >> Log2_Alloc_Quantum) + 1;
 112
 113     // when we call new() for more structures, how many should we get?
 114     static const int Num_Structs_Per_New = 20;
 115
 116     static int bucketFor(size_t);
 117     static void *moreStructs(int bucket);
 118
 119     static void *freeLists[Num_Buckets];
 120
 121 #if FAST_ALLOC_STATS
 122     static unsigned newCount[Num_Buckets];
 123     static unsigned deleteCount[Num_Buckets];
 124     static unsigned allocCount[Num_Buckets];
 125 #endif
 126 };
 127
 128 inline int
 129 FastAlloc::bucketFor(size_t sz)
 130 {
 131     return (sz + Alloc_Quantum - 1) >> Log2_Alloc_Quantum;
 132 }
 133
 134 inline void *
 135 FastAlloc::allocate(size_t sz)
 136 {
 137     int b;
 138     void *p;
 139
 140     if (sz > Max_Alloc_Size)
 141         return (void *)::new char[sz];
 142
 143     b = bucketFor(sz);
 144     p = freeLists[b];
 145
 146     if (p)
 147         freeLists[b] = *(void **)p;
 148     else
 149         p = moreStructs(b);
 150
 151 #if FAST_ALLOC_STATS
 152     ++newCount[b];
 153 #endif
 154
 155     return p;
 156 }
 157
 158 inline void
 159 FastAlloc::deallocate(void *p, size_t sz)
 160 {
 161     int b;
 162
 163     if (sz > Max_Alloc_Size) {
 164         ::delete [] (char *)p;
 165         return;
 166     }
 167
 168     b = bucketFor(sz);
 169     *(void **)p = freeLists[b];
 170     freeLists[b] = p;
 171 #if FAST_ALLOC_STATS
 172     ++deleteCount[b];
 173 #endif
 174 }
 175
 176 inline void *
 177 FastAlloc::operator new(size_t sz)
 178 {
 179     return allocate(sz);
 180 }
 181
 182 inline void
 183 FastAlloc::operator delete(void *p, size_t sz)
 184 {
 185     deallocate(p, sz);
 186 }
 187
 188 #endif // USE_FAST_ALLOC
 189
 190 #endif // __BASE_FAST_ALLOC_HH__