/
MemoryPool.h
221 lines (177 loc) · 7.17 KB
/
MemoryPool.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
/*
*
*
* Distributed under the OpenDDS License.
* See: http://www.opendds.org/license.html
*/
#ifndef OPENDDS_DCPS_MEMORYPOOL_H
#define OPENDDS_DCPS_MEMORYPOOL_H
#include "dcps_export.h"
OPENDDS_BEGIN_VERSIONED_NAMESPACE_DECL
namespace OpenDDS {
namespace Test {
class MemoryPoolTest;
class FreeIndexTest;
}
namespace DCPS {
/// Header of all allocations - found at beginning of allocation inside pool.
/// Extra room must be added to each allocation for this header.
class OpenDDS_Dcps_Export AllocHeader {
public:
/** Construct */
AllocHeader();
/** Get alloc size */
unsigned int size() const { return is_free() ? -alloc_size_ : alloc_size_; }
/** Get prev alloc size */
unsigned int prev_size() const { return prev_size_; }
/** Is this alloc free */
bool is_free() const { return alloc_size_ < 0; }
/** Get pointer to start of my buffer */
unsigned char* ptr() const;
/** Go to next header */
AllocHeader* next_adjacent();
/** Go to prev header */
AllocHeader* prev_adjacent();
/** Allocate from this block: change size, and mark as allocated */
void allocate(size_t size);
/** Set the size value stored in this header */
void set_size(size_t size);
/** Set the prev size value stored in this header */
void set_prev_size(int size) { prev_size_ = size; }
/** Mark this block as allocated */
void set_allocated() { if (alloc_size_ < 0) alloc_size_ = - alloc_size_; }
/** Join with the next adjacent block */
void join_next();
protected:
/** Sizes are those of buffers, does not include size of headers */
int alloc_size_; ///< Size of my buffer, negative if free, positive if alloc
int prev_size_; ///< Size of previous buffer, or 0 if first, never negative
};
/// Header of free allocations - found at beginning of allocation inside pool.
/// This forces a minimum allocation size, so that, when freed, header can
/// be cast to this type.
class OpenDDS_Dcps_Export FreeHeader : public AllocHeader {
public:
/** Initialize the first AllocHeader with its size */
void init_free_block(unsigned int pool_size);
/** Mark as free */
void set_free();
/** Get next equal or smaller free block in size order */
FreeHeader* smaller_free(unsigned char* pool_base) const;
/** Get next equal or larger free block in size order */
FreeHeader* larger_free(unsigned char* pool_base) const;
/** Set the next equal or smaller free block in size order */
void set_smaller_free(FreeHeader* next, unsigned char* pool_base);
/** Set the next equal or larger free block in size order */
void set_larger_free(FreeHeader* prev, unsigned char* pool_base);
private:
size_t offset_smaller_free_; ///< Offset to smaller free block in size order
size_t offset_larger_free_; ///< Offset to larger free block in size order
};
/// Node of free index. Should point to smallest free block of the range
/// from size (inclusive) to limit (non inclusive). If multiple free
/// allocations of the smallest size in range exist, should point to the one
/// which is the "smallest" (in free list order).
class FreeIndexNode {
public:
FreeIndexNode();
/** Set the free alloc this node points to */
void set_ptr(FreeHeader* ptr) { ptr_ = ptr; }
/** Set the sizes for this node */
void set_sizes(size_t size, size_t limit);
/** Does this node contain a given size */
bool contains(size_t size) { return ((size >= size_) && (size < limit_)); }
/** Get this node's free block */
FreeHeader* ptr() { return ptr_; }
/** Get this node's minimum size */
unsigned int size() const { return static_cast<unsigned int>(size_); }
private:
size_t size_; ///< size of buffer
size_t limit_; ///< upper_limit of buffer size (one too large)
FreeHeader* ptr_; ///< points to smallest free alloc of size_ or larger
};
/// Index of free nodes in memory pool.
/// Allows for a faster search of free nodes
class OpenDDS_Dcps_Export FreeIndex {
friend class Test::MemoryPoolTest;
friend class Test::FreeIndexTest;
public:
explicit FreeIndex(FreeHeader*& largest_free);
/** Initialize index with initial free block */
void init(FreeHeader* init_free_block);
/** Add free block to index */
void add(FreeHeader* free_block);
/** Remove free block from index */
void remove(FreeHeader* free_block, FreeHeader* next_largest);
/** Find smallest free block of size or larger */
FreeHeader* find(size_t size, unsigned char* base);
/** Calculate index of node corresponding to a size */
static unsigned int node_index(size_t size);
#ifdef VALIDATE_MEMORY_POOL
static void validate_index(FreeIndex& index,
unsigned char* base,
bool log = false);
#endif
private:
enum {
min_index_pow = 3,
max_index_pow = 12
};
enum {
min_index = 8, // 2^^3
max_index = 4096 // 2^^12
};
size_t size_; ///< Number of index nodes
FreeHeader*& largest_free_; ///< Memory pool's pointer to largest free block
FreeIndexNode nodes_[max_index_pow - min_index_pow + 1]; ///< Index nodes
};
// MemoryPool tracks free list, in size order (next meaning largest to smallest)
// and an index into the list at various sizes, which point to the smallest
// free allocation of that size or larger (but not larger than the next size).
// Allocations can be done by checking the index for the needed size, and going
// to the first free block.
class OpenDDS_Dcps_Export MemoryPool {
friend class Test::MemoryPoolTest;
public:
explicit MemoryPool(unsigned int pool_size, size_t granularity = 8);
~MemoryPool();
/** Does the pool include a given pointer */
bool includes(void* ptr) const {
return (pool_ptr_ <= ptr) && (ptr < pool_ptr_ + pool_size_); }
/** Allocate size bytes from the pool **/
void* pool_alloc(size_t size);
/** Attempt to free an allocation. Return true if allocation is managed by
this pool (and thus was freed).
*/
bool pool_free(void* ptr);
/** Low water mark of maximum available bytes for an allocation */
size_t lwm_free_bytes() const;
/** Calculate aligned size of allocation */
static size_t align(size_t size, size_t granularity) {
return (size + granularity - 1) / granularity * granularity; }
size_t size () const { return pool_size_; }
private:
const size_t granularity_; ///< Configured granularity
const size_t min_alloc_size_; ///< Aligned minimum allocation size
const size_t pool_size_; ///< Configured pool size
size_t lwm_free_bytes_; ///< Low water mark of available bytes
unsigned char* pool_ptr_; ///< Pointer to pool
FreeHeader* largest_free_; ///< Pointer to largest free index
FreeIndex free_index_; ///< Index of free nodex
enum {
min_free_size = sizeof(FreeHeader)
};
// Helpers
void remove_free_alloc(FreeHeader* block_to_alloc);
void insert_free_alloc(FreeHeader* block_freed);
void join_free_allocs(FreeHeader* block_freed);
unsigned char* allocate(FreeHeader* free_block, size_t alloc_size);
bool joinable_next(FreeHeader* freed);
bool joinable_prev(FreeHeader* freed);
#ifdef VALIDATE_MEMORY_POOL
static void validate_pool(MemoryPool& pool, bool log = false);
#endif
};
}} // end namespaces
OPENDDS_END_VERSIONED_NAMESPACE_DECL
#endif // OPENDDS_MEMORY_POOL_H