]>
Commit | Line | Data |
---|---|---|
dad253b4 AS |
1 | /* |
2 | * linear_allocator.h | |
3 | * | |
4 | * @copyright Copyright (C) 2016 Sproute Networks, Inc. | |
5 | * | |
6 | * @author Avneesh Sachdev <avneesh@sproute.com> | |
7 | * | |
8 | * This file is part of Quagga. | |
9 | * | |
10 | * Quagga is free software; you can redistribute it and/or modify it | |
11 | * under the terms of the GNU General Public License as published by the | |
12 | * Free Software Foundation; either version 2, or (at your option) any | |
13 | * later version. | |
14 | * | |
15 | * Quagga is distributed in the hope that it will be useful, but | |
16 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
18 | * General Public License for more details. | |
19 | * | |
896014f4 DL |
20 | * You should have received a copy of the GNU General Public License along |
21 | * with this program; see the file COPYING; if not, write to the Free Software | |
22 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
dad253b4 AS |
23 | */ |
24 | ||
25 | /* | |
26 | * Header file for the linear allocator. | |
27 | * | |
28 | * An allocator that allocates memory by walking down towards the end | |
29 | * of a buffer. No attempt is made to reuse blocks that are freed | |
30 | * subsequently. The assumption is that the buffer is big enough to | |
31 | * cover allocations for a given purpose. | |
32 | */ | |
33 | #include <assert.h> | |
34 | #include <string.h> | |
35 | #include <stdint.h> | |
36 | #include <stddef.h> | |
37 | ||
38 | /* | |
39 | * Alignment for block allocated by the allocator. Must be a power of 2. | |
40 | */ | |
41 | #define LINEAR_ALLOCATOR_ALIGNMENT 8 | |
42 | ||
d62a17ae | 43 | #define LINEAR_ALLOCATOR_ALIGN(value) \ |
44 | (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1) \ | |
45 | & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1)); | |
dad253b4 AS |
46 | |
47 | /* | |
48 | * linear_allocator_align_ptr | |
49 | */ | |
d62a17ae | 50 | static inline char *linear_allocator_align_ptr(char *ptr) |
dad253b4 | 51 | { |
d62a17ae | 52 | return (char *)LINEAR_ALLOCATOR_ALIGN((intptr_t)ptr); |
dad253b4 AS |
53 | } |
54 | ||
d62a17ae | 55 | typedef struct linear_allocator_t_ { |
56 | char *buf; | |
57 | ||
58 | /* | |
59 | * Current location in the buffer. | |
60 | */ | |
61 | char *cur; | |
62 | ||
63 | /* | |
64 | * End of buffer. | |
65 | */ | |
66 | char *end; | |
67 | ||
68 | /* | |
69 | * Version number of the allocator, this is bumped up when the allocator | |
70 | * is reset and helps identifies bad frees. | |
71 | */ | |
72 | uint32_t version; | |
73 | ||
74 | /* | |
75 | * The number of blocks that are currently allocated. | |
76 | */ | |
77 | int num_allocated; | |
dad253b4 AS |
78 | } linear_allocator_t; |
79 | ||
80 | /* | |
81 | * linear_allocator_block_t | |
82 | * | |
83 | * Header structure at the begining of each block. | |
84 | */ | |
d62a17ae | 85 | typedef struct linear_allocator_block_t_ { |
86 | uint32_t flags; | |
87 | ||
88 | /* | |
89 | * The version of the allocator when this block was allocated. | |
90 | */ | |
91 | uint32_t version; | |
92 | char data[0]; | |
dad253b4 AS |
93 | } linear_allocator_block_t; |
94 | ||
95 | #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01 | |
96 | ||
97 | #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t)) | |
98 | ||
99 | /* | |
100 | * linear_allocator_block_size | |
101 | * | |
102 | * The total amount of space a block will take in the buffer, | |
103 | * including the size of the header. | |
104 | */ | |
d62a17ae | 105 | static inline size_t linear_allocator_block_size(size_t user_size) |
dad253b4 | 106 | { |
d62a17ae | 107 | return LINEAR_ALLOCATOR_ALIGN(LINEAR_ALLOCATOR_HDR_SIZE + user_size); |
dad253b4 AS |
108 | } |
109 | ||
110 | /* | |
111 | * linear_allocator_ptr_to_block | |
112 | */ | |
d62a17ae | 113 | static inline linear_allocator_block_t *linear_allocator_ptr_to_block(void *ptr) |
dad253b4 | 114 | { |
d62a17ae | 115 | void *block_ptr; |
116 | block_ptr = ((char *)ptr) - offsetof(linear_allocator_block_t, data); | |
117 | return block_ptr; | |
dad253b4 AS |
118 | } |
119 | ||
120 | /* | |
121 | * linear_allocator_init | |
122 | */ | |
d62a17ae | 123 | static inline void linear_allocator_init(linear_allocator_t *allocator, |
124 | char *buf, size_t buf_len) | |
dad253b4 | 125 | { |
d62a17ae | 126 | memset(allocator, 0, sizeof(*allocator)); |
dad253b4 | 127 | |
d62a17ae | 128 | assert(linear_allocator_align_ptr(buf) == buf); |
129 | allocator->buf = buf; | |
130 | allocator->cur = buf; | |
131 | allocator->end = buf + buf_len; | |
dad253b4 AS |
132 | } |
133 | ||
134 | /* | |
135 | * linear_allocator_reset | |
136 | * | |
137 | * Prepare an allocator for reuse. | |
138 | * | |
139 | * *** NOTE ** This implicitly frees all the blocks in the allocator. | |
140 | */ | |
d62a17ae | 141 | static inline void linear_allocator_reset(linear_allocator_t *allocator) |
dad253b4 | 142 | { |
d62a17ae | 143 | allocator->num_allocated = 0; |
144 | allocator->version++; | |
145 | allocator->cur = allocator->buf; | |
dad253b4 AS |
146 | } |
147 | ||
148 | /* | |
149 | * linear_allocator_alloc | |
150 | */ | |
d62a17ae | 151 | static inline void *linear_allocator_alloc(linear_allocator_t *allocator, |
152 | size_t user_size) | |
dad253b4 | 153 | { |
d62a17ae | 154 | size_t block_size; |
155 | linear_allocator_block_t *block; | |
dad253b4 | 156 | |
d62a17ae | 157 | block_size = linear_allocator_block_size(user_size); |
dad253b4 | 158 | |
d62a17ae | 159 | if (allocator->cur + block_size > allocator->end) { |
160 | return NULL; | |
161 | } | |
dad253b4 | 162 | |
d62a17ae | 163 | block = (linear_allocator_block_t *)allocator->cur; |
164 | allocator->cur += block_size; | |
dad253b4 | 165 | |
d62a17ae | 166 | block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE; |
167 | block->version = allocator->version; | |
168 | allocator->num_allocated++; | |
169 | return block->data; | |
dad253b4 AS |
170 | } |
171 | ||
172 | /* | |
173 | * linear_allocator_free | |
174 | */ | |
d62a17ae | 175 | static inline void linear_allocator_free(linear_allocator_t *allocator, |
176 | void *ptr) | |
dad253b4 | 177 | { |
d62a17ae | 178 | linear_allocator_block_t *block; |
179 | ||
180 | if (((char *)ptr) < allocator->buf || ((char *)ptr) >= allocator->end) { | |
181 | assert(0); | |
182 | return; | |
183 | } | |
184 | ||
185 | block = linear_allocator_ptr_to_block(ptr); | |
186 | if (block->version != allocator->version) { | |
187 | assert(0); | |
188 | return; | |
189 | } | |
190 | ||
191 | block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE; | |
192 | ||
193 | if (--allocator->num_allocated < 0) { | |
194 | assert(0); | |
195 | } | |
dad253b4 | 196 | } |