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 */
20class GrMemoryPool {
21public:
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     */
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     */
56    size_t size() const { return fSize; }
57
58    /**
59     * Returns the preallocated size of the GrMemoryPool
60     */
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
68private:
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
110protected:
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 */
146template <class T>
147class GrObjectMemoryPool: public GrMemoryPool {
148public:
149    /**
150     * Preallocates memory for preallocCount objects, and sets new block size to be
151     * enough to hold minAllocCount objects.
152     */
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     */
162    T* allocate() { return static_cast<T*>(GrMemoryPool::allocate(sizeof(T))); }
163
164private:
165    constexpr static size_t kTotalObjectSize =
166        kPerAllocPad + GR_CT_ALIGN_UP(sizeof(T), kAlignment);
167
168    constexpr static size_t CountToSize(size_t count) {
169        return kHeaderSize + count * kTotalObjectSize;
170    }
171
172public:
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
181template <class T>
182constexpr size_t GrObjectMemoryPool<T>::kSmallestMinAllocCount;
183
184#endif
185