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