]>
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 | ||
43 | #define LINEAR_ALLOCATOR_ALIGN(value) \ | |
44 | (((value) + LINEAR_ALLOCATOR_ALIGNMENT - 1) & ~(LINEAR_ALLOCATOR_ALIGNMENT - 1)); | |
45 | ||
46 | /* | |
47 | * linear_allocator_align_ptr | |
48 | */ | |
49 | static inline char * | |
50 | linear_allocator_align_ptr (char *ptr) | |
51 | { | |
52 | return (char *) LINEAR_ALLOCATOR_ALIGN ((intptr_t) ptr); | |
53 | } | |
54 | ||
55 | typedef struct linear_allocator_t_ | |
56 | { | |
57 | char *buf; | |
58 | ||
59 | /* | |
60 | * Current location in the buffer. | |
61 | */ | |
62 | char *cur; | |
63 | ||
64 | /* | |
65 | * End of buffer. | |
66 | */ | |
67 | char *end; | |
68 | ||
69 | /* | |
70 | * Version number of the allocator, this is bumped up when the allocator | |
71 | * is reset and helps identifies bad frees. | |
72 | */ | |
73 | uint32_t version; | |
74 | ||
75 | /* | |
76 | * The number of blocks that are currently allocated. | |
77 | */ | |
78 | int num_allocated; | |
79 | } linear_allocator_t; | |
80 | ||
81 | /* | |
82 | * linear_allocator_block_t | |
83 | * | |
84 | * Header structure at the begining of each block. | |
85 | */ | |
86 | typedef struct linear_allocator_block_t_ | |
87 | { | |
88 | uint32_t flags; | |
89 | ||
90 | /* | |
91 | * The version of the allocator when this block was allocated. | |
92 | */ | |
93 | uint32_t version; | |
94 | char data[0]; | |
95 | } linear_allocator_block_t; | |
96 | ||
97 | #define LINEAR_ALLOCATOR_BLOCK_IN_USE 0x01 | |
98 | ||
99 | #define LINEAR_ALLOCATOR_HDR_SIZE (sizeof(linear_allocator_block_t)) | |
100 | ||
101 | /* | |
102 | * linear_allocator_block_size | |
103 | * | |
104 | * The total amount of space a block will take in the buffer, | |
105 | * including the size of the header. | |
106 | */ | |
107 | static inline size_t | |
108 | linear_allocator_block_size (size_t user_size) | |
109 | { | |
110 | return LINEAR_ALLOCATOR_ALIGN (LINEAR_ALLOCATOR_HDR_SIZE + user_size); | |
111 | } | |
112 | ||
113 | /* | |
114 | * linear_allocator_ptr_to_block | |
115 | */ | |
116 | static inline linear_allocator_block_t * | |
117 | linear_allocator_ptr_to_block (void *ptr) | |
118 | { | |
119 | void *block_ptr; | |
120 | block_ptr = ((char *) ptr) - offsetof (linear_allocator_block_t, data); | |
121 | return block_ptr; | |
122 | } | |
123 | ||
124 | /* | |
125 | * linear_allocator_init | |
126 | */ | |
127 | static inline void | |
128 | linear_allocator_init (linear_allocator_t * allocator, char *buf, | |
129 | size_t buf_len) | |
130 | { | |
131 | memset (allocator, 0, sizeof (*allocator)); | |
132 | ||
133 | assert (linear_allocator_align_ptr (buf) == buf); | |
134 | allocator->buf = buf; | |
135 | allocator->cur = buf; | |
136 | allocator->end = buf + buf_len; | |
137 | } | |
138 | ||
139 | /* | |
140 | * linear_allocator_reset | |
141 | * | |
142 | * Prepare an allocator for reuse. | |
143 | * | |
144 | * *** NOTE ** This implicitly frees all the blocks in the allocator. | |
145 | */ | |
146 | static inline void | |
147 | linear_allocator_reset (linear_allocator_t *allocator) | |
148 | { | |
149 | allocator->num_allocated = 0; | |
150 | allocator->version++; | |
151 | allocator->cur = allocator->buf; | |
152 | } | |
153 | ||
154 | /* | |
155 | * linear_allocator_alloc | |
156 | */ | |
157 | static inline void * | |
158 | linear_allocator_alloc (linear_allocator_t *allocator, size_t user_size) | |
159 | { | |
160 | size_t block_size; | |
161 | linear_allocator_block_t *block; | |
162 | ||
163 | block_size = linear_allocator_block_size (user_size); | |
164 | ||
165 | if (allocator->cur + block_size > allocator->end) | |
166 | { | |
167 | return NULL; | |
168 | } | |
169 | ||
170 | block = (linear_allocator_block_t *) allocator->cur; | |
171 | allocator->cur += block_size; | |
172 | ||
173 | block->flags = LINEAR_ALLOCATOR_BLOCK_IN_USE; | |
174 | block->version = allocator->version; | |
175 | allocator->num_allocated++; | |
176 | return block->data; | |
177 | } | |
178 | ||
179 | /* | |
180 | * linear_allocator_free | |
181 | */ | |
182 | static inline void | |
183 | linear_allocator_free (linear_allocator_t *allocator, void *ptr) | |
184 | { | |
185 | linear_allocator_block_t *block; | |
186 | ||
187 | if (((char *) ptr) < allocator->buf || ((char *) ptr) >= allocator->end) | |
188 | { | |
189 | assert (0); | |
190 | return; | |
191 | } | |
192 | ||
193 | block = linear_allocator_ptr_to_block (ptr); | |
194 | if (block->version != allocator->version) | |
195 | { | |
196 | assert (0); | |
197 | return; | |
198 | } | |
199 | ||
200 | block->flags = block->flags & ~LINEAR_ALLOCATOR_BLOCK_IN_USE; | |
201 | ||
202 | if (--allocator->num_allocated < 0) | |
203 | { | |
204 | assert (0); | |
205 | } | |
206 | } |