Allocator.h revision 2a22004f6857c57dc483ea6180f0e1f86854bd13 
1//===--- Allocator.h - Simple memory allocation abstraction -----*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the MallocAllocator and BumpPtrAllocator interfaces.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_ALLOCATOR_H
15#define LLVM_SUPPORT_ALLOCATOR_H
16
17#include "llvm/Support/AlignOf.h"
18#include "llvm/Support/MathExtras.h"
19#include "llvm/System/DataTypes.h"
20#include <algorithm>
21#include <cassert>
22#include <cstdlib>
23#include <cstddef>
24
25namespace llvm {
26
27class MallocAllocator {
28public:
29  MallocAllocator() {}
30  ~MallocAllocator() {}
31
32  void Reset() {}
33
34  void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
35
36  template <typename T>
37  T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
38
39  template <typename T>
40  T *Allocate(size_t Num) {
41    return static_cast<T*>(malloc(sizeof(T)*Num));
42  }
43
44  void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
45
46  void PrintStats() const {}
47};
48
49/// MemSlab - This structure lives at the beginning of every slab allocated by
50/// the bump allocator.
51class MemSlab {
52public:
53  size_t Size;
54  MemSlab *NextPtr;
55};
56
57/// SlabAllocator - This class can be used to parameterize the underlying
58/// allocation strategy for the bump allocator.  In particular, this is used
59/// by the JIT to allocate contiguous swathes of executable memory.  The
60/// interface uses MemSlab's instead of void *'s so that the allocator
61/// doesn't have to remember the size of the pointer it allocated.
62class SlabAllocator {
63public:
64  virtual ~SlabAllocator();
65  virtual MemSlab *Allocate(size_t Size) = 0;
66  virtual void Deallocate(MemSlab *Slab) = 0;
67};
68
69/// MallocSlabAllocator - The default slab allocator for the bump allocator
70/// is an adapter class for MallocAllocator that just forwards the method
71/// calls and translates the arguments.
72class MallocSlabAllocator : public SlabAllocator {
73  /// Allocator - The underlying allocator that we forward to.
74  ///
75  MallocAllocator Allocator;
76
77public:
78  MallocSlabAllocator() : Allocator() { }
79  virtual ~MallocSlabAllocator();
80  virtual MemSlab *Allocate(size_t Size);
81  virtual void Deallocate(MemSlab *Slab);
82};
83
84/// BumpPtrAllocator - This allocator is useful for containers that need
85/// very simple memory allocation strategies.  In particular, this just keeps
86/// allocating memory, and never deletes it until the entire block is dead. This
87/// makes allocation speedy, but must only be used when the trade-off is ok.
88class BumpPtrAllocator {
89  BumpPtrAllocator(const BumpPtrAllocator &); // do not implement
90  void operator=(const BumpPtrAllocator &);   // do not implement
91
92  /// SlabSize - Allocate data into slabs of this size unless we get an
93  /// allocation above SizeThreshold.
94  size_t SlabSize;
95
96  /// SizeThreshold - For any allocation larger than this threshold, we should
97  /// allocate a separate slab.
98  size_t SizeThreshold;
99
100  /// Allocator - The underlying allocator we use to get slabs of memory.  This
101  /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
102  /// changed to use a custom allocator.
103  SlabAllocator &Allocator;
104
105  /// CurSlab - The slab that we are currently allocating into.
106  ///
107  MemSlab *CurSlab;
108
109  /// CurPtr - The current pointer into the current slab.  This points to the
110  /// next free byte in the slab.
111  char *CurPtr;
112
113  /// End - The end of the current slab.
114  ///
115  char *End;
116
117  /// BytesAllocated - This field tracks how many bytes we've allocated, so
118  /// that we can compute how much space was wasted.
119  size_t BytesAllocated;
120
121  /// AlignPtr - Align Ptr to Alignment bytes, rounding up.  Alignment should
122  /// be a power of two.  This method rounds up, so AlignPtr(7, 4) == 8 and
123  /// AlignPtr(8, 4) == 8.
124  static char *AlignPtr(char *Ptr, size_t Alignment);
125
126  /// StartNewSlab - Allocate a new slab and move the bump pointers over into
127  /// the new slab.  Modifies CurPtr and End.
128  void StartNewSlab();
129
130  /// DeallocateSlabs - Deallocate all memory slabs after and including this
131  /// one.
132  void DeallocateSlabs(MemSlab *Slab);
133
134  static MallocSlabAllocator DefaultSlabAllocator;
135
136public:
137  typedef void (*DTorFunction)(void*);
138  BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096,
139                   SlabAllocator &allocator = DefaultSlabAllocator);
140  ~BumpPtrAllocator();
141
142  /// Reset - Deallocate all but the current slab and reset the current pointer
143  /// to the beginning of it, freeing all memory allocated so far.
144  void Reset();
145
146  /// Reset - like Reset(), but call DTorFunction for each allocated
147  /// object. This assumes that all objects allocated with this allocator
148  /// had the same size and alignment specified here.
149  void Reset(size_t Size, size_t Alignment, DTorFunction DTor);
150
151  /// Allocate - Allocate space at the specified alignment.
152  ///
153  void *Allocate(size_t Size, size_t Alignment);
154
155  /// Allocate space, but do not construct, one object.
156  ///
157  template <typename T>
158  T *Allocate() {
159    return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
160  }
161
162  /// Allocate space for an array of objects.  This does not construct the
163  /// objects though.
164  template <typename T>
165  T *Allocate(size_t Num) {
166    return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
167  }
168
169  /// Allocate space for a specific count of elements and with a specified
170  /// alignment.
171  template <typename T>
172  T *Allocate(size_t Num, size_t Alignment) {
173    // Round EltSize up to the specified alignment.
174    size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
175    return static_cast<T*>(Allocate(Num * EltSize, Alignment));
176  }
177
178  void Deallocate(const void * /*Ptr*/) {}
179
180  unsigned GetNumSlabs() const;
181
182  void PrintStats() const;
183};
184
185}  // end namespace llvm
186
187inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
188  struct S {
189    char c;
190#ifdef __GNUC__
191    char x __attribute__((aligned));
192#else
193    union {
194      double D;
195      long double LD;
196      long long L;
197      void *P;
198    } x;
199#endif
200  };
201  return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
202                                           offsetof(S, x)));
203}
204
205#endif // LLVM_SUPPORT_ALLOCATOR_H
206