1 /***************************************************************************
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
10 * This is a memory allocator designed to provide reasonable management of free
11 * space and fast access to allocated data. More than one allocator can be used
12 * at a time by initializing multiple contexts.
14 * Copyright (C) 2009 Andrew Mahone
16 * This program is free software; you can redistribute it and/or
17 * modify it under the terms of the GNU General Public License
18 * as published by the Free Software Foundation; either version 2
19 * of the License, or (at your option) any later version.
21 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
22 * KIND, either express or implied.
24 ****************************************************************************/
26 #include <stdlib.h> /* for abs() */
28 /* The main goal of this design is fast fetching of the pointer for a handle.
29 * For that reason, the handles are stored in a table at the end of the buffer
30 * with a fixed address, so that returning the pointer for a handle is a simple
31 * table lookup. To reduce the frequency with which allocated blocks will need
32 * to be moved to free space, allocations grow up in address from the start of
33 * the buffer. The buffer is treated as an array of union buflib_data. Blocks
34 * start with a length marker, which is included in their length. Free blocks
35 * are marked by negative length, allocated ones use the second buflib_data in
36 * the block to store a pointer to their handle table entry, so that it can be
37 * quickly found and updated during compaction. The allocator functions are
38 * passed a context struct so that two allocators can be run, for example, one
39 * per core may be used, with convenience wrappers for the single-allocator
40 * case that use a predefined context.
43 /* Initialize buffer manager */
45 buflib_init(struct buflib_context
*ctx
, void *buf
, size_t size
)
47 union buflib_data
*bd_buf
= buf
;
49 /* Align on sizeof(buflib_data), to prevent unaligned access */
50 ALIGN_BUFFER(bd_buf
, size
, sizeof(union buflib_data
));
51 size
/= sizeof(union buflib_data
);
52 /* The handle table is initialized with no entries */
53 ctx
->handle_table
= bd_buf
+ size
;
54 ctx
->last_handle
= bd_buf
+ size
;
55 ctx
->first_free_handle
= bd_buf
+ size
- 1;
56 ctx
->first_free_block
= bd_buf
;
57 ctx
->buf_start
= bd_buf
;
58 /* A marker is needed for the end of allocated data, to make sure that it
59 * does not collide with the handle table, and to detect end-of-buffer.
61 ctx
->alloc_end
= bd_buf
;
65 /* Allocate a new handle, returning 0 on failure */
67 union buflib_data
* handle_alloc(struct buflib_context
*ctx
)
69 union buflib_data
*handle
;
70 /* first_free_handle is a lower bound on free handles, work through the
71 * table from there until a handle containing NULL is found, or the end
72 * of the table is reached.
74 for (handle
= ctx
->first_free_handle
; handle
>= ctx
->last_handle
; handle
--)
77 /* If the search went past the end of the table, it means we need to extend
78 * the table to get a new handle.
80 if (handle
< ctx
->last_handle
)
82 if (handle
>= ctx
->alloc_end
)
91 /* Free one handle, shrinking the handle table if it's the last one */
93 void handle_free(struct buflib_context
*ctx
, union buflib_data
*handle
)
96 /* Update free handle lower bound if this handle has a lower index than the
99 if (handle
> ctx
->first_free_handle
)
100 ctx
->first_free_handle
= handle
;
101 if (handle
== ctx
->last_handle
)
104 ctx
->compact
= false;
107 /* Shrink the handle table, returning true if its size was reduced, false if
112 handle_table_shrink(struct buflib_context
*ctx
)
115 union buflib_data
*handle
;
116 for (handle
= ctx
->last_handle
; !(handle
->ptr
); handle
++);
117 if (handle
> ctx
->first_free_handle
)
118 ctx
->first_free_handle
= handle
- 1;
119 rv
= handle
== ctx
->last_handle
;
120 ctx
->last_handle
= handle
;
124 /* Compact allocations and handle table, adjusting handle pointers as needed.
125 * Return true if any space was freed or consolidated, false otherwise.
128 buflib_compact(struct buflib_context
*ctx
)
130 union buflib_data
*block
= ctx
->first_free_block
, *new_block
;
132 /* Store the results of attempting to shrink the handle table */
133 bool ret
= handle_table_shrink(ctx
);
134 for(; block
!= ctx
->alloc_end
; block
+= len
)
137 /* This block is free, add its length to the shift value */
144 /* If shift is non-zero, it represents the number of places to move
145 * blocks down in memory. Calculate the new address for this block,
146 * update its entry in the handle table, and then move its contents.
150 new_block
= block
+ shift
;
151 block
[1].ptr
->ptr
= new_block
+ 2;
152 rb
->memmove(new_block
, block
, len
* sizeof(union buflib_data
));
155 /* Move the end-of-allocation mark, and return true if any new space has
158 ctx
->alloc_end
+= shift
;
159 ctx
->first_free_block
= ctx
->alloc_end
;
164 /* Shift buffered items by size units, and update handle pointers. The shift
165 * value must be determined to be safe *before* calling.
168 buflib_buffer_shift(struct buflib_context
*ctx
, int shift
)
170 rb
->memmove(ctx
->buf_start
+ shift
, ctx
->buf_start
,
171 (ctx
->alloc_end
- ctx
->buf_start
) * sizeof(union buflib_data
));
172 union buflib_data
*ptr
;
173 for (ptr
= ctx
->last_handle
; ptr
< ctx
->handle_table
; ptr
++)
176 ctx
->first_free_block
+= shift
;
177 ctx
->buf_start
+= shift
;
178 ctx
->alloc_end
+= shift
;
181 /* Shift buffered items up by size bytes, or as many as possible if size == 0.
182 * Set size to the number of bytes freed.
185 buflib_buffer_out(struct buflib_context
*ctx
, size_t *size
)
189 size_t avail
= ctx
->last_handle
- ctx
->alloc_end
;
190 size_t avail_b
= avail
* sizeof(union buflib_data
);
191 if (*size
&& *size
< avail_b
)
193 avail
= (*size
+ sizeof(union buflib_data
) - 1)
194 / sizeof(union buflib_data
);
195 avail_b
= avail
* sizeof(union buflib_data
);
198 void *ret
= ctx
->buf_start
;
199 buflib_buffer_shift(ctx
, avail
);
203 /* Shift buffered items down by size bytes */
205 buflib_buffer_in(struct buflib_context
*ctx
, int size
)
207 size
/= sizeof(union buflib_data
);
208 buflib_buffer_shift(ctx
, -size
);
211 /* Allocate a buffer of size bytes, returning a handle for it */
213 buflib_alloc(struct buflib_context
*ctx
, size_t size
)
215 union buflib_data
*handle
, *block
;
217 /* This really is assigned a value before use */
219 size
= (size
+ sizeof(union buflib_data
) - 1) /
220 sizeof(union buflib_data
) + 2;
222 handle
= handle_alloc(ctx
);
225 /* If allocation has failed, and compaction has succeded, it may be
226 * possible to get a handle by trying again.
228 if (!ctx
->compact
&& buflib_compact(ctx
))
235 for (block
= ctx
->first_free_block
;; block
+= block_len
)
237 /* If the last used block extends all the way to the handle table, the
238 * block "after" it doesn't have a header. Because of this, it's easier
239 * to always find the end of allocation by saving a pointer, and always
240 * calculate the free space at the end by comparing it to the
241 * last_handle pointer.
243 if(block
== ctx
->alloc_end
)
246 block_len
= ctx
->last_handle
- block
;
247 if ((size_t)block_len
< size
)
251 block_len
= block
->val
;
252 /* blocks with positive length are already allocated. */
255 block_len
= -block_len
;
256 /* The search is first-fit, any fragmentation this causes will be
257 * handled at compaction.
259 if ((size_t)block_len
>= size
)
264 /* Try compacting if allocation failed, but only if the handle
265 * allocation did not trigger compaction already, since there will
266 * be no further gain.
268 if (!ctx
->compact
&& buflib_compact(ctx
))
273 handle_free(ctx
, handle
);
278 /* Set up the allocated block, by marking the size allocated, and storing
279 * a pointer to the handle.
282 block
[1].ptr
= handle
;
283 handle
->ptr
= block
+ 2;
284 /* If we have just taken the first free block, the next allocation search
285 * can save some time by starting after this block.
287 if (block
== ctx
->first_free_block
)
288 ctx
->first_free_block
+= size
;
290 /* alloc_end must be kept current if we're taking the last block. */
292 ctx
->alloc_end
= block
;
293 /* Only free blocks *before* alloc_end have tagged length. */
294 else if ((size_t)block_len
> size
)
295 block
->val
= size
- block_len
;
296 /* Return the handle index as a positive integer. */
297 return ctx
->handle_table
- handle
;
300 /* Free the buffer associated with handle_num. */
302 buflib_free(struct buflib_context
*ctx
, int handle_num
)
304 union buflib_data
*handle
= ctx
->handle_table
- handle_num
,
305 *freed_block
= handle
->ptr
- 2,
306 *block
= ctx
->first_free_block
,
308 /* We need to find the block before the current one, to see if it is free
309 * and can be merged with this one.
311 while (next_block
< freed_block
)
314 next_block
+= abs(block
->val
);
316 /* If next_block == block, the above loop didn't go anywhere. If it did,
317 * and the block before this one is empty, we can combine them.
319 if (next_block
== freed_block
&& next_block
!= block
&& block
->val
< 0)
320 block
->val
-= freed_block
->val
;
321 /* Otherwise, set block to the newly-freed block, and mark it free, before
322 * continuing on, since the code below exects block to point to a free
323 * block which may have free space after it.
328 block
->val
= -block
->val
;
330 next_block
= block
- block
->val
;
331 /* Check if we are merging with the free space at alloc_end. */
332 if (next_block
== ctx
->alloc_end
)
333 ctx
->alloc_end
= block
;
334 /* Otherwise, the next block might still be a "normal" free block, and the
335 * mid-allocation free means that the buffer is no longer compact.
338 ctx
->compact
= false;
339 if (next_block
->val
< 0)
340 block
->val
+= next_block
->val
;
342 handle_free(ctx
, handle
);
344 /* If this block is before first_free_block, it becomes the new starting
345 * point for free-block search.
347 if (block
< ctx
->first_free_block
)
348 ctx
->first_free_block
= block
;