1 /*******************************************************************************
2 * Copyright (C) 2018 Cadence Design Systems, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to use this Software with Cadence processor cores only and
7 * not with any other processors and platforms, subject to
8 * the following conditions:
9 *
10 * The above copyright notice and this permission notice shall be included
11 * in all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
14 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
15 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
16 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
17 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
18 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
19 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21 ******************************************************************************/
22
23 /*******************************************************************************
24 * xf-mem.c
25 *
26 * Dynamic memory allocator implementation (based on rb-tree index)
27 *
28 ******************************************************************************/
29
30 #define MODULE_TAG MM
31
32 /*******************************************************************************
33 * Includes
34 ******************************************************************************/
35
36 #include "xf.h"
37
38 /*******************************************************************************
39 * Tracing configuration
40 ******************************************************************************/
41
42 TRACE_TAG(INIT, 1);
43
44 /*******************************************************************************
45 * Internal helpers
46 ******************************************************************************/
47
48 /* ...initialize block */
xf_mm_block_init(void * addr,u32 size)49 static inline xf_mm_block_t * xf_mm_block_init(void *addr, u32 size)
50 {
51 xf_mm_block_t *b = (xf_mm_block_t *)addr;
52
53 /* ...use 31 available bits of node color to keep aligned size */
54 return b->l_node.color = size, b;
55 }
56
57 /* ...check if the length of the block is less than given */
xf_mm_block_length_less(xf_mm_block_t * b,u32 size)58 static inline int xf_mm_block_length_less(xf_mm_block_t *b, u32 size)
59 {
60 /* ...we don't really care about LSB of color */
61 return (b->l_node.color < size);
62 }
63
64 /* ...return exact block length */
xf_mm_block_length(xf_mm_block_t * b)65 static inline u32 xf_mm_block_length(xf_mm_block_t *b)
66 {
67 /* ...wipe out least-significant bit from node color */
68 return (b->l_node.color & ~1);
69 }
70
71 /* ...increase block length */
xf_mm_block_length_add(xf_mm_block_t * b,u32 size)72 static inline u32 xf_mm_block_length_add(xf_mm_block_t *b, u32 size)
73 {
74 /* ...return exact block length after increase */
75 return ((b->l_node.color += size) & ~1);
76 }
77
78 /* ...decrease block length */
xf_mm_block_length_sub(xf_mm_block_t * b,u32 size)79 static inline u32 xf_mm_block_length_sub(xf_mm_block_t *b, u32 size)
80 {
81 /* ...return exact block length after decrease */
82 return ((b->l_node.color -= size) & ~1);
83 }
84
85 /*******************************************************************************
86 * Internal functions
87 ******************************************************************************/
88
89 /* ...find best-match node given requested size */
xf_mm_find_by_size(xf_mm_pool_t * pool,u32 size)90 static inline xf_mm_block_t * xf_mm_find_by_size(xf_mm_pool_t *pool, u32 size)
91 {
92 rb_tree_t *tree = &pool->l_map;
93 rb_idx_t p_idx, t_idx;
94
95 /* ...find first block having length greater than requested */
96 for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = rb_right(tree, p_idx))
97 {
98 xf_mm_block_t *b = container_of(p_idx, xf_mm_block_t, l_node);
99
100 /* ...break upon finding first matching candidate */
101 if (!xf_mm_block_length_less(b, size))
102 break;
103 }
104
105 /* ...bail out if haven't found a block with sufficient size */
106 if (p_idx == rb_null(tree))
107 return NULL;
108
109 /* ...try to find better match in left subtree */
110 for (t_idx = rb_left(tree, p_idx); t_idx != rb_null(tree); )
111 {
112 xf_mm_block_t *b = container_of(t_idx, xf_mm_block_t, l_node);
113
114 /* ...check the size of the block */
115 if (!xf_mm_block_length_less(b, size))
116 {
117 /* ...update best match */
118 p_idx = t_idx;
119
120 /* ...and check if we have anything better in left sbtree */
121 t_idx = rb_left(tree, t_idx);
122 }
123 else
124 {
125 /* ...move towards higher block sizes in that subtree */
126 t_idx = rb_right(tree, t_idx);
127 }
128 }
129
130 /* ...p_idx is our best choice */
131 return container_of(p_idx, xf_mm_block_t, l_node);
132 }
133
134 /* ...find the neighbours of the block basing on its address */
xf_mm_find_by_addr(xf_mm_pool_t * pool,void * addr,xf_mm_block_t ** n)135 static void xf_mm_find_by_addr(xf_mm_pool_t *pool, void *addr, xf_mm_block_t **n)
136 {
137 rb_tree_t *tree = &pool->a_map;
138 rb_idx_t p_idx, l_idx, r_idx;
139
140 /* ...it is not possible to have exact match in this map */
141 for (p_idx = rb_root(tree), l_idx = r_idx = NULL; p_idx != rb_null(tree); )
142 {
143 /* ...only "is less than" comparison is valid (as "a_node" pointer is biased) */
144 if ((u32)p_idx < (u32)addr)
145 {
146 /* ...update lower neighbour */
147 l_idx = p_idx;
148
149 /* ...and move towards higher addresses */
150 p_idx = rb_right(tree, p_idx);
151 }
152 else
153 {
154 /* ...update higher neighbour */
155 r_idx = p_idx;
156
157 /* ...and move towards lower addresses */
158 p_idx = rb_left(tree, p_idx);
159 }
160 }
161
162 /* ...translate nodes into blocks */
163 n[0] = (l_idx ? container_of(l_idx, xf_mm_block_t, a_node) : NULL);
164 n[1] = (r_idx ? container_of(r_idx, xf_mm_block_t, a_node) : NULL);
165 }
166
167 /* ...insert the block into L-map */
xf_mm_insert_size(xf_mm_pool_t * pool,xf_mm_block_t * b,u32 size)168 static void xf_mm_insert_size(xf_mm_pool_t *pool, xf_mm_block_t *b, u32 size)
169 {
170 rb_tree_t *tree = &pool->l_map;
171 rb_idx_t p_idx, t_idx;
172
173 /* ...find the parent node for the next block */
174 for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = t_idx)
175 {
176 /* ...check for the size */
177 if (xf_mm_block_length_less(container_of(p_idx, xf_mm_block_t, l_node), size))
178 {
179 /* ...move towards higher addresses */
180 if ((t_idx = rb_right(tree, p_idx)) == rb_null(tree))
181 {
182 /* ...node becomes a right child of parent p */
183 rb_set_right(tree, p_idx, &b->l_node);
184 break;
185 }
186 }
187 else
188 {
189 /* ...move towards lower addresses (ok if exact size match is found) */
190 if ((t_idx = rb_left(tree, p_idx)) == rb_null(tree))
191 {
192 /* ...node becomes a left child of parent p */
193 rb_set_left(tree, p_idx, &b->l_node);
194 break;
195 }
196 }
197 }
198
199 /* ...insert node into tree */
200 rb_insert(tree, &b->l_node, p_idx);
201 }
202
203 /* ...insert the block into A-map */
xf_mm_insert_addr(xf_mm_pool_t * pool,xf_mm_block_t * b)204 static void xf_mm_insert_addr(xf_mm_pool_t *pool, xf_mm_block_t *b)
205 {
206 rb_tree_t *tree = &pool->a_map;
207 rb_idx_t p_idx, t_idx;
208
209 /* ...find the parent node for the next block */
210 for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = t_idx)
211 {
212 /* ...check for the address (only "is less than" comparison is valid) */
213 if ((u32)p_idx < (u32)b)
214 {
215 /* ...move towards higher addresses */
216 if ((t_idx = rb_right(tree, p_idx)) == rb_null(tree))
217 {
218 /* ...node becomes a right child of parent p */
219 rb_set_right(tree, p_idx, &b->a_node);
220 break;
221 }
222 }
223 else
224 {
225 /* ...move towards lower addresses (by design there cannot be exact match) */
226 if ((t_idx = rb_left(tree, p_idx)) == rb_null(tree))
227 {
228 /* ...node becomes a left child of parent p */
229 rb_set_left(tree, p_idx, &b->a_node);
230 break;
231 }
232 }
233 }
234
235 /* ...insert node into tree */
236 rb_insert(tree, &b->a_node, p_idx);
237 }
238
239 /*******************************************************************************
240 * Entry points
241 ******************************************************************************/
242
243 /* ...block allocation */
xf_mm_alloc(xf_mm_pool_t * pool,u32 size)244 void * xf_mm_alloc(xf_mm_pool_t *pool, u32 size)
245 {
246 xf_mm_block_t *b;
247
248 /* ...find best-fit free block */
249 XF_CHK_ERR(b = xf_mm_find_by_size(pool, size), NULL);
250
251 /* ...remove the block from the L-map */
252 rb_delete(&pool->l_map, &b->l_node);
253
254 /* ...check if the size is exactly the same as requested */
255 if ((size = xf_mm_block_length_sub(b, size)) == 0)
256 {
257 /* ...the block needs to be removed from the A-map as well */
258 rb_delete(&pool->a_map, &b->a_node);
259
260 /* ...entire block goes to user */
261 return (void *) b;
262 }
263 else
264 {
265 /* ...insert the block into L-map */
266 xf_mm_insert_size(pool, b, size);
267
268 /* ...A-map remains intact; tail of the block goes to user */
269 return (void *) b + size;
270 }
271 }
272
273 /* ...block deallocation */
xf_mm_free(xf_mm_pool_t * pool,void * addr,u32 size)274 void xf_mm_free(xf_mm_pool_t *pool, void *addr, u32 size)
275 {
276 xf_mm_block_t *b = xf_mm_block_init(addr, size);
277 xf_mm_block_t *n[2];
278
279 /* ...find block neighbours in A-map */
280 xf_mm_find_by_addr(pool, addr, n);
281
282 /* ...check if we can merge block to left neighbour */
283 if (n[0])
284 {
285 if ((void *)n[0] + xf_mm_block_length(n[0]) == addr)
286 {
287 /* ...merge free block with left neighbour; delete it from L-map */
288 rb_delete(&pool->l_map, &n[0]->l_node);
289
290 /* ...adjust block length (block remains in A-map) */
291 addr = (void *)(b = n[0]), size = xf_mm_block_length_add(b, size);
292 }
293 else
294 {
295 /* ...mark there is no left-merge */
296 n[0] = NULL;
297 }
298 }
299
300 /* ...check if we can merge block to right neighbour */
301 if (n[1])
302 {
303 if ((void *)n[1] == addr + size)
304 {
305 /* ...merge free block with right neighbour; delete it from L-map */
306 rb_delete(&pool->l_map, &n[1]->l_node);
307
308 /* ...adjust block length */
309 size = xf_mm_block_length_add(b, xf_mm_block_length(n[1]));
310
311 /* ...check if left merge took place as well */
312 if (n[0])
313 {
314 /* ...left neighbour covers now all three blocks; drop record from A-map */
315 rb_delete(&pool->a_map, &n[1]->a_node);
316 }
317 else
318 {
319 /* ...fixup tree pointers (equivalent to remove/reinsert the same key) */
320 rb_replace(&pool->a_map, &n[1]->a_node, &b->a_node);
321 }
322 }
323 else
324 {
325 n[1] = NULL;
326 }
327 }
328
329 /* ...if any merge has occured, A-map is updated */
330 if (n[0] == NULL && n[1] == NULL)
331 {
332 /* ...add new block into A-map */
333 xf_mm_insert_addr(pool, b);
334 }
335
336 /* ...add (new or adjusted) block into L-map */
337 xf_mm_insert_size(pool, b, size);
338 }
339
340 /* ...initialize memory allocator */
xf_mm_init(xf_mm_pool_t * pool,void * addr,u32 size)341 int xf_mm_init(xf_mm_pool_t *pool, void *addr, u32 size)
342 {
343 /* ...check pool alignment validity */
344 XF_CHK_ERR(((u32)addr & (sizeof(xf_mm_block_t) - 1)) == 0, -EINVAL);
345
346 /* ...check pool size validity */
347 XF_CHK_ERR(((size) & (sizeof(xf_mm_block_t) - 1)) == 0, -EINVAL);
348
349 /* ...set pool parameters (need that stuff at all? - tbd) */
350 pool->addr = addr, pool->size = size;
351
352 /* ...initialize rb-trees */
353 rb_init(&pool->l_map), rb_init(&pool->a_map);
354
355 /* ..."free" the entire block */
356 xf_mm_free(pool, addr, size);
357
358 TRACE(INIT, _b("memory allocator initialized: [%p..%p)"), addr, addr + size);
359
360 return 0;
361 }
362