1 /*
2  * Copyright 2012 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #ifndef GrMemoryPool_DEFINED
9 #define GrMemoryPool_DEFINED
10 
11 #include "GrTypes.h"
12 
13 /**
14  * Allocates memory in blocks and parcels out space in the blocks for allocation
15  * requests. It is optimized for allocate / release speed over memory
16  * efficiency. The interface is designed to be used to implement operator new
17  * and delete overrides. All allocations are expected to be released before the
18  * pool's destructor is called. Allocations will be 8-byte aligned.
19  */
20 class GrMemoryPool {
21 public:
22     /**
23      * Prealloc size is the amount of space to allocate at pool creation
24      * time and keep around until pool destruction. The min alloc size is
25      * the smallest allowed size of additional allocations. Both sizes are
26      * adjusted to ensure that:
27      *   1. they are are 8-byte aligned
28      *   2. minAllocSize >= kSmallestMinAllocSize
29      *   3. preallocSize >= minAllocSize
30      *
31      * Both sizes is what the pool will end up allocating from the system, and
32      * portions of the allocated memory is used for internal bookkeeping.
33      */
34     GrMemoryPool(size_t preallocSize, size_t minAllocSize);
35 
36     ~GrMemoryPool();
37 
38     /**
39      * Allocates memory. The memory must be freed with release().
40      */
41     void* allocate(size_t size);
42 
43     /**
44      * p must have been returned by allocate()
45      */
46     void release(void* p);
47 
48     /**
49      * Returns true if there are no unreleased allocations.
50      */
isEmpty()51     bool isEmpty() const { return fTail == fHead && !fHead->fLiveCount; }
52 
53     /**
54      * Returns the total allocated size of the GrMemoryPool minus any preallocated amount
55      */
size()56     size_t size() const { return fSize; }
57 
58     /**
59      * Returns the preallocated size of the GrMemoryPool
60      */
preallocSize()61     size_t preallocSize() const { return fHead->fSize; }
62 
63     /**
64      * Minimum value of minAllocSize constructor argument.
65      */
66     constexpr static size_t kSmallestMinAllocSize = 1 << 10;
67 
68 private:
69     struct BlockHeader;
70 
71     static BlockHeader* CreateBlock(size_t size);
72 
73     static void DeleteBlock(BlockHeader* block);
74 
75     void validate();
76 
77     struct BlockHeader {
78 #ifdef SK_DEBUG
79         uint32_t     fBlockSentinal;  ///< known value to check for bad back pointers to blocks
80 #endif
81         BlockHeader* fNext;      ///< doubly-linked list of blocks.
82         BlockHeader* fPrev;
83         int          fLiveCount; ///< number of outstanding allocations in the
84                                  ///< block.
85         intptr_t     fCurrPtr;   ///< ptr to the start of blocks free space.
86         intptr_t     fPrevPtr;   ///< ptr to the last allocation made
87         size_t       fFreeSize;  ///< amount of free space left in the block.
88         size_t       fSize;      ///< total allocated size of the block
89     };
90 
91     static const uint32_t kAssignedMarker = 0xCDCDCDCD;
92     static const uint32_t kFreedMarker    = 0xEFEFEFEF;
93 
94     struct AllocHeader {
95 #ifdef SK_DEBUG
96         uint32_t fSentinal;      ///< known value to check for memory stomping (e.g., (CD)*)
97 #endif
98         BlockHeader* fHeader;    ///< pointer back to the block header in which an alloc resides
99     };
100 
101     size_t                            fSize;
102     size_t                            fMinAllocSize;
103     BlockHeader*                      fHead;
104     BlockHeader*                      fTail;
105 #ifdef SK_DEBUG
106     int                               fAllocationCnt;
107     int                               fAllocBlockCnt;
108 #endif
109 
110 protected:
111     enum {
112         // We assume this alignment is good enough for everybody.
113         kAlignment    = 8,
114         kHeaderSize   = GR_CT_ALIGN_UP(sizeof(BlockHeader), kAlignment),
115         kPerAllocPad  = GR_CT_ALIGN_UP(sizeof(AllocHeader), kAlignment),
116     };
117 };
118 
119 /**
120  * Variant of GrMemoryPool that can only allocate objects of a single type. It is
121  * not as flexible as GrMemoryPool, but it has more convenient allocate() method,
122  * and more importantly, it guarantees number of objects that are preallocated at
123  * construction or when adding a new memory block. I.e.
124  *
125  * GrMemoryPool pool(3 * sizeof(T), 1000 * sizeof(T));
126  * pool.allocate(sizeof(T));
127  * pool.allocate(sizeof(T));
128  * pool.allocate(sizeof(T));
129  *
130  * will preallocate 3 * sizeof(T) bytes and use some of those bytes for internal
131  * structures. Because of that, last allocate() call will end up allocating a new
132  * block of 1000 * sizeof(T) bytes. In contrast,
133  *
134  * GrObjectMemoryPool<T> pool(3, 1000);
135  * pool.allocate();
136  * pool.allocate();
137  * pool.allocate();
138  *
139  * guarantees to preallocate enough memory for 3 objects of sizeof(T), so last
140  * allocate() will use preallocated memory and won't cause allocation of a new block.
141  *
142  * Same thing is true for the second (minAlloc) ctor argument: this class guarantees
143  * that a newly added block will have enough space for 1000 objects of sizeof(T), while
144  * GrMemoryPool does not.
145  */
146 template <class T>
147 class GrObjectMemoryPool: public GrMemoryPool {
148 public:
149     /**
150      * Preallocates memory for preallocCount objects, and sets new block size to be
151      * enough to hold minAllocCount objects.
152      */
GrObjectMemoryPool(size_t preallocCount,size_t minAllocCount)153     GrObjectMemoryPool(size_t preallocCount, size_t minAllocCount)
154         : GrMemoryPool(CountToSize(preallocCount),
155                        CountToSize(SkTMax(minAllocCount, kSmallestMinAllocCount))) {
156     }
157 
158     /**
159      * Allocates memory for an object, but doesn't construct or otherwise initialize it.
160      * The memory must be freed with release().
161      */
allocate()162     T* allocate() { return static_cast<T*>(GrMemoryPool::allocate(sizeof(T))); }
163 
164 private:
165     constexpr static size_t kTotalObjectSize =
166         kPerAllocPad + GR_CT_ALIGN_UP(sizeof(T), kAlignment);
167 
CountToSize(size_t count)168     constexpr static size_t CountToSize(size_t count) {
169         return kHeaderSize + count * kTotalObjectSize;
170     }
171 
172 public:
173     /**
174      * Minimum value of minAllocCount constructor argument.
175      */
176     constexpr static size_t kSmallestMinAllocCount =
177         (GrMemoryPool::kSmallestMinAllocSize - kHeaderSize + kTotalObjectSize - 1) /
178             kTotalObjectSize;
179 };
180 
181 template <class T>
182 constexpr size_t GrObjectMemoryPool<T>::kSmallestMinAllocCount;
183 
184 #endif
185