tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/***************************************************************************
2* __________ __ ___.
3* Open \______ \ ____ ____ | | _\_ |__ _______ ___
4* Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5* Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6* Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
7* \/ \/ \/ \/ \/
8* $Id$
9*
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.
13*
14* Copyright (C) 2009 Andrew Mahone
15* Copyright (C) 2011 Thomas Martitz
16*
17*
18* This program is free software; you can redistribute it and/or
19* modify it under the terms of the GNU General Public License
20* as published by the Free Software Foundation; either version 2
21* of the License, or (at your option) any later version.
22*
23* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
24* KIND, either express or implied.
25*
26****************************************************************************/
27
28#include <stdarg.h>
29#include <stdlib.h> /* for abs() */
30#include <stdio.h> /* for snprintf() */
31#include <stddef.h> /* for ptrdiff_t */
32#include "buflib.h"
33#include "string-extra.h" /* strmemccpy() */
34#include "debug.h"
35#include "panic.h"
36#include "system.h" /* for ALIGN_*() */
37
38/* FIXME: This comment is pretty out of date now and wrong in some details.
39 *
40 * The main goal of this design is fast fetching of the pointer for a handle.
41 * For that reason, the handles are stored in a table at the end of the buffer
42 * with a fixed address, so that returning the pointer for a handle is a simple
43 * table lookup. To reduce the frequency with which allocated blocks will need
44 * to be moved to free space, allocations grow up in address from the start of
45 * the buffer. The buffer is treated as an array of union buflib_data. Blocks
46 * start with a length marker, which is included in their length. Free blocks
47 * are marked by negative length. Allocated blocks have a positiv length marker,
48 * and additional metadata following that: It follows a pointer
49 * (union buflib_data*) to the corresponding handle table entry. so that it can
50 * be quickly found and updated during compaction. After that follows
51 * the pointer to the struct buflib_callbacks associated with this allocation
52 * (may be NULL). That pointer follows a variable length character array
53 * containing the nul-terminated string identifier of the allocation. After this
54 * array there's a length marker for the length of the character array including
55 * this length marker (counted in n*sizeof(union buflib_data)), which allows
56 * to find the start of the character array (and therefore the start of the
57 * entire block) when only the handle or payload start is known.
58 *
59 * UPDATE BUFLIB_ALLOC_OVERHEAD (buflib.h) WHEN THE METADATA CHANGES!
60 *
61 * Example:
62 * |<- alloc block #1 ->|<- unalloc block ->|<- alloc block #2 ->|<-handle table->|
63 * |L|H|C|cccc|L2|crc|XXXXXX|-L|YYYYYYYYYYYYYYYY|L|H|C|cc|L2|crc|XXXXXXXXXXXXX|AAA|
64 *
65 * L - length marker (negative if block unallocated)
66 * H - handle table entry pointer
67 * C - pointer to struct buflib_callbacks
68 * c - variable sized string identifier
69 * L2 - length of the metadata
70 * crc - crc32 protecting buflib metadata integrity
71 * X - actual payload
72 * Y - unallocated space
73 *
74 * A - pointer to start of payload (first X) in the handle table (may be null)
75 *
76 * The blocks can be walked by jumping the abs() of the L length marker, i.e.
77 * union buflib_data* L;
78 * for(L = start; L < end; L += abs(L->val)) { .... }
79 *
80 *
81 * The allocator functions are passed a context struct so that two allocators
82 * can be run, for example, one per core may be used, with convenience wrappers
83 * for the single-allocator case that use a predefined context.
84 */
85
86#define B_ALIGN_DOWN(x) \
87 ALIGN_DOWN(x, sizeof(union buflib_data))
88
89#define B_ALIGN_UP(x) \
90 ALIGN_UP(x, sizeof(union buflib_data))
91
92#ifdef DEBUG
93 #include <stdio.h>
94 #define BDEBUGF DEBUGF
95#else
96 #define BDEBUGF(...) do { } while(0)
97#endif
98
99#define BPANICF panicf
100
101/* Available paranoia checks */
102#define PARANOIA_CHECK_LENGTH (1 << 0)
103#define PARANOIA_CHECK_BLOCK_HANDLE (1 << 1)
104#define PARANOIA_CHECK_PINNING (1 << 2)
105/* Bitmask of enabled paranoia checks */
106#define BUFLIB_PARANOIA \
107 (PARANOIA_CHECK_LENGTH | \
108 PARANOIA_CHECK_BLOCK_HANDLE | PARANOIA_CHECK_PINNING)
109
110struct buflib_callbacks buflib_ops_locked = {
111 .move_callback = NULL,
112 .shrink_callback = NULL,
113 .sync_callback = NULL,
114};
115
116#define IS_MOVABLE(a) \
117 (!a[BUFLIB_IDX_OPS].ops || a[BUFLIB_IDX_OPS].ops->move_callback)
118
119static union buflib_data* find_first_free(struct buflib_context *ctx);
120static union buflib_data* find_block_before(struct buflib_context *ctx,
121 union buflib_data* block,
122 bool is_free);
123
124/* Check the length of a block to ensure it does not go beyond the end
125 * of the allocated area. The block can be either allocated or free.
126 *
127 * This verifies that it is safe to iterate to the next block in a loop.
128 */
129static void check_block_length(struct buflib_context *ctx,
130 union buflib_data *block);
131
132/* Check a block's handle pointer to ensure it is within the handle
133 * table, and that the user pointer is pointing within the block.
134 *
135 * This verifies that it is safe to dereference the entry and ensures
136 * that the pointer in the handle table points within the block, as
137 * determined by the length field at the start of the block.
138 */
139static void check_block_handle(struct buflib_context *ctx,
140 union buflib_data *block);
141
142/* Initialize buffer manager */
143void
144buflib_init(struct buflib_context *ctx, void *buf, size_t size)
145{
146 union buflib_data *bd_buf = buf;
147 BDEBUGF("buflib initialized with %lu.%02lu kiB\n",
148 (unsigned long)size / 1024, ((unsigned long)size%1000)/10);
149
150 /* Align on sizeof(buflib_data), to prevent unaligned access */
151 ALIGN_BUFFER(bd_buf, size, sizeof(union buflib_data));
152 size /= sizeof(union buflib_data);
153 /* The handle table is initialized with no entries */
154 ctx->handle_table = bd_buf + size;
155 ctx->last_handle = bd_buf + size;
156 ctx->first_free_handle = bd_buf + size - 1;
157 ctx->buf_start = bd_buf;
158 /* A marker is needed for the end of allocated data, to make sure that it
159 * does not collide with the handle table, and to detect end-of-buffer.
160 */
161 ctx->alloc_end = bd_buf;
162 ctx->compact = true;
163
164 if (size == 0)
165 {
166 BPANICF("buflib_init error (CTX:%p, %zd bytes):\n", ctx,
167 (ctx->handle_table - ctx->buf_start) * sizeof(union buflib_data));
168 }
169}
170
171bool buflib_context_relocate(struct buflib_context *ctx, void *buf)
172{
173 union buflib_data *handle, *bd_buf = buf;
174 ptrdiff_t diff = bd_buf - ctx->buf_start;
175
176 /* cannot continue if the buffer is not aligned, since we would need
177 * to reduce the size of the buffer for aligning */
178 if (!IS_ALIGNED((uintptr_t)buf, sizeof(union buflib_data)))
179 return false;
180
181 /* relocate the handle table entries */
182 for (handle = ctx->last_handle; handle < ctx->handle_table; handle++)
183 {
184 if (handle->alloc)
185 handle->alloc += diff * sizeof(union buflib_data);
186 }
187 /* relocate the pointers in the context */
188 ctx->handle_table += diff;
189 ctx->last_handle += diff;
190 ctx->first_free_handle += diff;
191 ctx->buf_start += diff;
192 ctx->alloc_end += diff;
193
194 return true;
195}
196
197static void buflib_panic(struct buflib_context *ctx, const char *message, ...)
198{
199 char buf[128];
200 va_list ap;
201
202 va_start(ap, message);
203 vsnprintf(buf, sizeof(buf), message, ap);
204 va_end(ap);
205
206 BPANICF("buflib error (CTX:%p, %zd bytes):\n%s", ctx,
207 (ctx->handle_table - ctx->buf_start) * sizeof(union buflib_data), buf);
208}
209
210/* Allocate a new handle, returning 0 on failure */
211static inline
212union buflib_data* handle_alloc(struct buflib_context *ctx)
213{
214 union buflib_data *handle;
215 /* first_free_handle is a lower bound on free handles, work through the
216 * table from there until a handle containing NULL is found, or the end
217 * of the table is reached.
218 */
219 for (handle = ctx->first_free_handle; handle >= ctx->last_handle; handle--)
220 if (!handle->alloc)
221 break;
222 /* If the search went past the end of the table, it means we need to extend
223 * the table to get a new handle.
224 */
225 if (handle < ctx->last_handle)
226 {
227 if (handle >= ctx->alloc_end)
228 ctx->last_handle--;
229 else
230 {
231 /* We know the table is full, so update first_free_handle */
232 ctx->first_free_handle = ctx->last_handle - 1;
233 return NULL;
234 }
235 }
236
237 /* We know there are no free handles between the old first_free_handle
238 * and the found handle, therefore we can update first_free_handle */
239 ctx->first_free_handle = handle - 1;
240
241 /* We need to set the table entry to a non-NULL value to ensure that
242 * compactions triggered by an allocation do not compact the handle
243 * table and delete this handle. */
244 handle->val = -1;
245
246 return handle;
247}
248
249/* Free one handle, shrinking the handle table if it's the last one */
250static inline
251void handle_free(struct buflib_context *ctx, union buflib_data *handle)
252{
253 handle->alloc = 0;
254 /* Update free handle lower bound if this handle has a lower index than the
255 * old one.
256 */
257 if (handle > ctx->first_free_handle)
258 ctx->first_free_handle = handle;
259 if (handle == ctx->last_handle)
260 ctx->last_handle++;
261 else
262 ctx->compact = false;
263}
264
265/* Get the start block of an allocation */
266static inline
267union buflib_data* handle_to_block(struct buflib_context* ctx, int handle)
268{
269 void *ptr = buflib_get_data(ctx, handle);
270
271 /* this is a valid case for shrinking if handle
272 * was freed by the shrink callback */
273 if (!ptr)
274 return NULL;
275
276 return _buflib_get_block_header(ptr);
277}
278
279/* Shrink the handle table, returning true if its size was reduced, false if
280 * not
281 */
282static inline bool handle_table_shrink(struct buflib_context *ctx)
283{
284 union buflib_data *handle;
285 union buflib_data *old_last = ctx->last_handle;
286
287 for (handle = ctx->last_handle; handle != ctx->handle_table; ++handle)
288 if (handle->alloc)
289 break;
290
291 if (handle > ctx->first_free_handle)
292 ctx->first_free_handle = handle - 1;
293
294 ctx->last_handle = handle;
295 return handle != old_last;
296}
297
298/* If shift is non-zero, it represents the number of places to move
299 * blocks in memory. Calculate the new address for this block,
300 * update its entry in the handle table, and then move its contents.
301 *
302 * Returns false if moving was unsucessful
303 * (NULL callback or BUFLIB_CB_CANNOT_MOVE was returned)
304 */
305static bool
306move_block(struct buflib_context* ctx, union buflib_data* block, int shift)
307{
308 char* new_start;
309 union buflib_data *new_block;
310
311 check_block_handle(ctx, block);
312 union buflib_data *h_entry = block[BUFLIB_IDX_HANDLE].handle;
313
314 if (!IS_MOVABLE(block) || block[BUFLIB_IDX_PIN].pincount > 0)
315 return false;
316
317 int handle = ctx->handle_table - h_entry;
318 BDEBUGF("%s(): moving id=%d by %d(%d)\n", __func__,
319 handle, shift, shift*(int)sizeof(union buflib_data));
320 new_block = block + shift;
321 new_start = h_entry->alloc + shift*sizeof(union buflib_data);
322
323 struct buflib_callbacks *ops = block[BUFLIB_IDX_OPS].ops;
324
325 /* If move must be synchronized with use, user should have specified a
326 callback that handles this */
327 if (ops && ops->sync_callback)
328 ops->sync_callback(handle, true);
329
330 bool retval = false;
331 if (!ops || ops->move_callback(handle, h_entry->alloc, new_start)
332 != BUFLIB_CB_CANNOT_MOVE)
333 {
334 h_entry->alloc = new_start; /* update handle table */
335 memmove(new_block, block, block->val * sizeof(union buflib_data));
336 retval = true;
337 }
338
339 if (ops && ops->sync_callback)
340 ops->sync_callback(handle, false);
341
342 return retval;
343}
344
345/* Compact allocations and handle table, adjusting handle pointers as needed.
346 * Return true if any space was freed or consolidated, false otherwise.
347 */
348static bool
349buflib_compact(struct buflib_context *ctx)
350{
351 BDEBUGF("%s(): Compacting!\n", __func__);
352 union buflib_data *block,
353 *hole = NULL;
354 int shift = 0, len;
355 /* Store the results of attempting to shrink the handle table */
356 bool ret = handle_table_shrink(ctx);
357 /* compaction has basically two modes of operation:
358 * 1) the buffer is nicely movable: In this mode, blocks can be simply
359 * moved towards the beginning. Free blocks add to a shift value,
360 * which is the amount to move.
361 * 2) the buffer contains unmovable blocks: unmovable blocks create
362 * holes and reset shift. Once a hole is found, we're trying to fill
363 * holes first, moving by shift is the fallback. As the shift is reset,
364 * this effectively splits the buffer into portions of movable blocks.
365 * This mode cannot be used if no holes are found yet as it only works
366 * when it moves blocks across the portions. On the other side,
367 * moving by shift only works within the same portion
368 * For simplicity only 1 hole at a time is considered */
369 for(block = find_first_free(ctx); block < ctx->alloc_end; block += len)
370 {
371 check_block_length(ctx, block);
372
373 bool movable = true; /* cache result to avoid 2nd call to move_block */
374 len = block->val;
375 /* This block is free, add its length to the shift value */
376 if (len < 0)
377 {
378 shift += len;
379 len = -len;
380 continue;
381 }
382 /* attempt to fill any hole */
383 if (hole && -hole->val >= len)
384 {
385 intptr_t hlen = -hole->val;
386 if ((movable = move_block(ctx, block, hole - block)))
387 {
388 ret = true;
389 /* Move was successful. The memory at block is now free */
390 block->val = -len;
391
392 /* add its length to shift */
393 shift += -len;
394 /* Reduce the size of the hole accordingly
395 * but be careful to not overwrite an existing block */
396 if (hlen != len)
397 {
398 hole += len;
399 hole->val = len - hlen; /* negative */
400 }
401 else /* hole closed */
402 hole = NULL;
403 continue;
404 }
405 }
406 /* attempt move the allocation by shift */
407 if (shift)
408 {
409 union buflib_data* target_block = block + shift;
410 if (!movable || !move_block(ctx, block, shift))
411 {
412 /* free space before an unmovable block becomes a hole,
413 * therefore mark this block free and track the hole */
414 target_block->val = shift;
415 hole = target_block;
416 shift = 0;
417 }
418 else
419 ret = true;
420 }
421 }
422 /* Move the end-of-allocation mark, and return true if any new space has
423 * been freed.
424 */
425 ctx->alloc_end += shift;
426 ctx->compact = true;
427 return ret || shift;
428}
429
430/* Compact the buffer by trying both shrinking and moving.
431 *
432 * Try to move first. If unsuccesfull, try to shrink. If that was successful
433 * try to move once more as there might be more room now.
434 */
435static bool
436buflib_compact_and_shrink(struct buflib_context *ctx, unsigned shrink_hints)
437{
438 bool result = false;
439 /* if something compacted before already there will be no further gain */
440 if (!ctx->compact)
441 result = buflib_compact(ctx);
442 if (!result)
443 {
444 union buflib_data *this, *before;
445 for(this = ctx->buf_start, before = this;
446 this < ctx->alloc_end;
447 before = this, this += abs(this->val))
448 {
449 check_block_length(ctx, this);
450 if (this->val < 0)
451 continue;
452
453 struct buflib_callbacks *ops = this[BUFLIB_IDX_OPS].ops;
454 if (!ops || !ops->shrink_callback)
455 continue;
456
457 check_block_handle(ctx, this);
458 union buflib_data* h_entry = this[BUFLIB_IDX_HANDLE].handle;
459 int handle = ctx->handle_table - h_entry;
460
461 unsigned pos_hints = shrink_hints & BUFLIB_SHRINK_POS_MASK;
462 /* adjust what we ask for if there's free space in the front
463 * this isn't too unlikely assuming this block is
464 * shrinkable but not movable */
465 if (pos_hints == BUFLIB_SHRINK_POS_FRONT &&
466 before != this && before->val < 0)
467 {
468 size_t free_space = (-before->val) * sizeof(union buflib_data);
469 size_t wanted = shrink_hints & BUFLIB_SHRINK_SIZE_MASK;
470 if (wanted < free_space) /* no shrink needed? */
471 continue;
472 wanted -= free_space;
473 shrink_hints = pos_hints | wanted;
474 }
475
476 char* data = h_entry->alloc;
477 char* data_end = (char*)(this + this->val);
478 bool last = (data_end == (char*)ctx->alloc_end);
479
480 int ret = ops->shrink_callback(handle, shrink_hints,
481 data, data_end - data);
482 result |= (ret == BUFLIB_CB_OK);
483
484 /* 'this' might have changed in the callback (if it shrinked
485 * from the top or even freed the handle), get it again */
486 this = handle_to_block(ctx, handle);
487
488 /* The handle was possibly be freed in the callback,
489 * re-run the loop with the handle before */
490 if (!this)
491 this = before;
492 /* could also change with shrinking from back */
493 else if (last)
494 ctx->alloc_end = this + this->val;
495 }
496 /* shrinking was successful at least once, try compaction again */
497 if (result)
498 result |= buflib_compact(ctx);
499 }
500
501 return result;
502}
503
504/* Shift buffered items by size units, and update handle pointers. The shift
505 * value must be determined to be safe *before* calling.
506 */
507static void
508buflib_buffer_shift(struct buflib_context *ctx, int shift)
509{
510 memmove(ctx->buf_start + shift, ctx->buf_start,
511 (ctx->alloc_end - ctx->buf_start) * sizeof(union buflib_data));
512 ctx->buf_start += shift;
513 ctx->alloc_end += shift;
514 shift *= sizeof(union buflib_data);
515 union buflib_data *handle;
516 for (handle = ctx->last_handle; handle < ctx->handle_table; handle++)
517 if (handle->alloc)
518 handle->alloc += shift;
519}
520
521/* Shift buffered items up by size bytes, or as many as possible if size == 0.
522 * Set size to the number of bytes freed.
523 */
524void*
525buflib_buffer_out(struct buflib_context *ctx, size_t *size)
526{
527 if (!ctx->compact)
528 buflib_compact(ctx);
529 size_t avail = ctx->last_handle - ctx->alloc_end;
530 size_t avail_b = avail * sizeof(union buflib_data);
531 if (*size && *size < avail_b)
532 {
533 avail = (*size + sizeof(union buflib_data) - 1)
534 / sizeof(union buflib_data);
535 avail_b = avail * sizeof(union buflib_data);
536 }
537 *size = avail_b;
538 void *ret = ctx->buf_start;
539 buflib_buffer_shift(ctx, avail);
540 return ret;
541}
542
543/* Shift buffered items down by size bytes */
544void
545buflib_buffer_in(struct buflib_context *ctx, int size)
546{
547 size /= sizeof(union buflib_data);
548 buflib_buffer_shift(ctx, -size);
549}
550
551/* Allocate a buffer of size bytes, returning a handle for it.
552 * Note: Buffers are movable since NULL is passed for "ops".
553 Don't pass them to functions that call yield() */
554int
555buflib_alloc(struct buflib_context *ctx, size_t size)
556{
557 return buflib_alloc_ex(ctx, size, NULL);
558}
559
560/* Allocate a buffer of size bytes, returning a handle for it.
561 *
562 * The ops parameter points to caller-implemented callbacks for moving and
563 * shrinking.
564 *
565 * If you pass NULL for "ops", buffers are movable by default.
566 * Don't pass them to functions that call yield() like I/O.
567 * Buffers are only shrinkable when a shrink callback is given.
568 */
569
570int
571buflib_alloc_ex(struct buflib_context *ctx, size_t size,
572 struct buflib_callbacks *ops)
573{
574 union buflib_data *handle, *block;
575 bool last;
576 /* This really is assigned a value before use */
577 int block_len;
578 size = (size + sizeof(union buflib_data) - 1) /
579 sizeof(union buflib_data)
580 + BUFLIB_NUM_FIELDS;
581handle_alloc:
582 handle = handle_alloc(ctx);
583 if (!handle)
584 {
585 /* If allocation has failed, and compaction has succeded, it may be
586 * possible to get a handle by trying again.
587 */
588 union buflib_data* last_block = find_block_before(ctx,
589 ctx->alloc_end, false);
590 struct buflib_callbacks* ops = last_block[BUFLIB_IDX_OPS].ops;
591 unsigned hints = 0;
592 if (!ops || !ops->shrink_callback)
593 { /* the last one isn't shrinkable
594 * make room in front of a shrinkable and move this alloc */
595 hints = BUFLIB_SHRINK_POS_FRONT;
596 hints |= last_block->val * sizeof(union buflib_data);
597 }
598 else if (ops && ops->shrink_callback)
599 { /* the last is shrinkable, make room for handles directly */
600 hints = BUFLIB_SHRINK_POS_BACK;
601 hints |= 16*sizeof(union buflib_data);
602 }
603 /* buflib_compact_and_shrink() will compact and move last_block()
604 * if possible */
605 if (buflib_compact_and_shrink(ctx, hints))
606 goto handle_alloc;
607 return -1;
608 }
609
610buffer_alloc:
611 /* need to re-evaluate last before the loop because the last allocation
612 * possibly made room in its front to fit this, so last would be wrong */
613 last = false;
614 for (block = find_first_free(ctx);; block += block_len)
615 {
616 /* If the last used block extends all the way to the handle table, the
617 * block "after" it doesn't have a header. Because of this, it's easier
618 * to always find the end of allocation by saving a pointer, and always
619 * calculate the free space at the end by comparing it to the
620 * last_handle pointer.
621 */
622 if(block == ctx->alloc_end)
623 {
624 last = true;
625 block_len = ctx->last_handle - block;
626 if ((size_t)block_len < size)
627 block = NULL;
628 break;
629 }
630
631 check_block_length(ctx, block);
632 block_len = block->val;
633 /* blocks with positive length are already allocated. */
634 if(block_len > 0)
635 continue;
636 block_len = -block_len;
637 /* The search is first-fit, any fragmentation this causes will be
638 * handled at compaction.
639 */
640 if ((size_t)block_len >= size)
641 break;
642 }
643 if (!block)
644 {
645 /* Try compacting if allocation failed */
646 unsigned hint = BUFLIB_SHRINK_POS_FRONT |
647 ((size*sizeof(union buflib_data))&BUFLIB_SHRINK_SIZE_MASK);
648 if (buflib_compact_and_shrink(ctx, hint))
649 {
650 goto buffer_alloc;
651 } else {
652 handle_free(ctx, handle);
653 return -2;
654 }
655 }
656
657 /* Set up the allocated block, by marking the size allocated, and storing
658 * a pointer to the handle.
659 */
660 block[BUFLIB_IDX_LEN].val = size;
661 block[BUFLIB_IDX_HANDLE].handle = handle;
662 block[BUFLIB_IDX_OPS].ops = ops;
663 block[BUFLIB_IDX_PIN].pincount = 0;
664
665 handle->alloc = (char*)&block[BUFLIB_NUM_FIELDS];
666
667 BDEBUGF("buflib_alloc_ex: size=%d handle=%p clb=%p\n",
668 (unsigned int)size, (void *)handle, (void *)ops);
669
670 block += size;
671 /* alloc_end must be kept current if we're taking the last block. */
672 if (last)
673 ctx->alloc_end = block;
674 /* Only free blocks *before* alloc_end have tagged length. */
675 else if ((size_t)block_len > size)
676 block->val = size - block_len;
677 /* Return the handle index as a positive integer. */
678 return ctx->handle_table - handle;
679}
680
681static union buflib_data*
682find_first_free(struct buflib_context *ctx)
683{
684 union buflib_data *ret;
685 for(ret = ctx->buf_start; ret < ctx->alloc_end; ret += ret->val)
686 {
687 check_block_length(ctx, ret);
688 if (ret->val < 0)
689 break;
690 }
691
692 /* ret is now either a free block or the same as alloc_end, both is fine */
693 return ret;
694}
695
696/* Finds the free block before block, and returns NULL if it's not free */
697static union buflib_data*
698find_block_before(struct buflib_context *ctx, union buflib_data* block,
699 bool is_free)
700{
701 union buflib_data *ret = ctx->buf_start,
702 *next_block = ret;
703
704 /* no previous block */
705 if (next_block == block)
706 return NULL;
707
708 /* find the block that's before the current one */
709 while (next_block != block)
710 {
711 check_block_length(ctx, ret);
712 ret = next_block;
713 next_block += abs(ret->val);
714 }
715
716 /* don't return it if the found block isn't free */
717 if (is_free && ret->val >= 0)
718 return NULL;
719
720 return ret;
721}
722
723/* Free the buffer associated with handle_num. */
724int
725buflib_free(struct buflib_context *ctx, int handle_num)
726{
727 if (handle_num <= 0) /* invalid or already free */
728 return handle_num;
729 union buflib_data *handle = ctx->handle_table - handle_num,
730 *freed_block = handle_to_block(ctx, handle_num),
731 *block, *next_block;
732 /* We need to find the block before the current one, to see if it is free
733 * and can be merged with this one.
734 */
735 block = find_block_before(ctx, freed_block, true);
736 if (block)
737 {
738 block->val -= freed_block->val;
739 }
740 else
741 {
742 /* Otherwise, set block to the newly-freed block, and mark it free,
743 * before continuing on, since the code below expects block to point
744 * to a free block which may have free space after it. */
745 block = freed_block;
746 block->val = -block->val;
747 }
748
749 next_block = block - block->val;
750 /* Check if we are merging with the free space at alloc_end. */
751 if (next_block == ctx->alloc_end)
752 ctx->alloc_end = block;
753 /* Otherwise, the next block might still be a "normal" free block, and the
754 * mid-allocation free means that the buffer is no longer compact.
755 */
756 else {
757 ctx->compact = false;
758 if (next_block->val < 0)
759 block->val += next_block->val;
760 }
761 handle_free(ctx, handle);
762 handle->alloc = NULL;
763
764 return 0; /* unconditionally */
765}
766
767static size_t
768free_space_at_end(struct buflib_context* ctx)
769{
770 /* subtract 5 elements for
771 * val, handle, meta_len, ops and the handle table entry*/
772 ptrdiff_t diff = (ctx->last_handle - ctx->alloc_end - BUFLIB_NUM_FIELDS);
773 diff -= 16; /* space for future handles */
774 diff *= sizeof(union buflib_data); /* make it bytes */
775
776 if (diff > 0)
777 return diff;
778 else
779 return 0;
780}
781
782/* Return the maximum allocatable contiguous memory in bytes */
783size_t
784buflib_allocatable(struct buflib_context* ctx)
785{
786 size_t free_space = 0, max_free_space = 0;
787 intptr_t block_len;
788
789 /* make sure buffer is as contiguous as possible */
790 if (!ctx->compact)
791 buflib_compact(ctx);
792
793 /* now look if there's free in holes */
794 for(union buflib_data *block = find_first_free(ctx);
795 block < ctx->alloc_end;
796 block += block_len)
797 {
798 check_block_length(ctx, block);
799 block_len = block->val;
800
801 if (block_len < 0)
802 {
803 block_len = -block_len;
804 free_space += block_len;
805 continue;
806 }
807
808 /* an unmovable section resets the count as free space
809 * can't be contigous */
810 if (!IS_MOVABLE(block))
811 {
812 if (max_free_space < free_space)
813 max_free_space = free_space;
814 free_space = 0;
815 }
816 }
817
818 /* select the best */
819 max_free_space = MAX(max_free_space, free_space);
820 max_free_space *= sizeof(union buflib_data);
821 max_free_space = MAX(max_free_space, free_space_at_end(ctx));
822
823 if (max_free_space > 0)
824 return max_free_space;
825 else
826 return 0;
827}
828
829/* Return the amount of unallocated memory in bytes (even if not contiguous) */
830size_t
831buflib_available(struct buflib_context* ctx)
832{
833 size_t free_space = 0;
834
835 /* add up all holes */
836 for(union buflib_data *block = find_first_free(ctx);
837 block < ctx->alloc_end;
838 block += abs(block->val))
839 {
840 check_block_length(ctx, block);
841 if (block->val < 0)
842 free_space += -block->val;
843 }
844
845 free_space *= sizeof(union buflib_data); /* make it bytes */
846 free_space += free_space_at_end(ctx);
847
848 return free_space;
849}
850
851/*
852 * Allocate all available (as returned by buflib_available()) memory and return
853 * a handle to it
854 *
855 * This grabs a lock which can only be unlocked by buflib_free() or
856 * buflib_shrink(), to protect from further allocations (which couldn't be
857 * serviced anyway).
858 */
859int
860buflib_alloc_maximum(struct buflib_context* ctx, size_t *size, struct buflib_callbacks *ops)
861{
862 /* ignore ctx->compact because it's true if all movable blocks are contiguous
863 * even if the buffer has holes due to unmovable allocations */
864 unsigned hints;
865 size_t bufsize = ctx->handle_table - ctx->buf_start;
866 bufsize = MIN(BUFLIB_SHRINK_SIZE_MASK, bufsize*sizeof(union buflib_data)); /* make it bytes */
867 /* try as hard as possible to free up space. allocations are
868 * welcome to give up some or all of their memory */
869 hints = BUFLIB_SHRINK_POS_BACK | BUFLIB_SHRINK_POS_FRONT | bufsize;
870 /* compact until no space can be gained anymore */
871 while (buflib_compact_and_shrink(ctx, hints));
872
873 *size = buflib_allocatable(ctx);
874 if (*size <= 0) /* OOM */
875 return -1;
876
877 return buflib_alloc_ex(ctx, *size, ops);
878}
879
880/* Shrink the allocation indicated by the handle according to new_start and
881 * new_size. Grow is not possible, therefore new_start and new_start + new_size
882 * must be within the original allocation
883 */
884bool
885buflib_shrink(struct buflib_context* ctx, int handle, void* new_start, size_t new_size)
886{
887 char* oldstart = buflib_get_data(ctx, handle);
888 char* newstart = new_start != NULL ? new_start : oldstart;
889 char* newend = newstart + new_size;
890
891 /* newstart must be higher and new_size not "negative" */
892 if (newstart < oldstart || newend < newstart)
893 return false;
894 union buflib_data *block = handle_to_block(ctx, handle),
895 *old_next_block = block + block->val,
896 /* newstart isn't necessarily properly aligned but it
897 * needn't be since it's only dereferenced by the user code */
898 *aligned_newstart = (union buflib_data*)B_ALIGN_DOWN(newstart),
899 *aligned_oldstart = (union buflib_data*)B_ALIGN_DOWN(oldstart),
900 *new_next_block = (union buflib_data*)B_ALIGN_UP(newend),
901 *new_block, metadata_size;
902
903 /* growing is not supported */
904 if (new_next_block > old_next_block)
905 return false;
906
907 metadata_size.val = aligned_oldstart - block;
908 /* update val and the handle table entry */
909 new_block = aligned_newstart - metadata_size.val;
910 block[BUFLIB_IDX_LEN].val = new_next_block - new_block;
911
912 check_block_handle(ctx, block);
913 block[BUFLIB_IDX_HANDLE].handle->alloc = newstart;
914 if (block != new_block)
915 {
916 /* move metadata over, i.e. pointer to handle table entry and name
917 * This is actually the point of no return. Data in the allocation is
918 * being modified, and therefore we must successfully finish the shrink
919 * operation */
920 memmove(new_block, block, metadata_size.val*sizeof(metadata_size));
921 /* mark the old block unallocated */
922 block->val = block - new_block;
923 /* find the block before in order to merge with the new free space */
924 union buflib_data *free_before = find_block_before(ctx, block, true);
925 if (free_before)
926 free_before->val += block->val;
927
928 /* We didn't handle size changes yet, assign block to the new one
929 * the code below the wants block whether it changed or not */
930 block = new_block;
931 }
932
933 /* Now deal with size changes that create free blocks after the allocation */
934 if (old_next_block != new_next_block)
935 {
936 if (ctx->alloc_end == old_next_block)
937 ctx->alloc_end = new_next_block;
938 else if (old_next_block->val < 0)
939 { /* enlarge next block by moving it up */
940 new_next_block->val = old_next_block->val - (old_next_block - new_next_block);
941 }
942 else if (old_next_block != new_next_block)
943 { /* creating a hole */
944 /* must be negative to indicate being unallocated */
945 new_next_block->val = new_next_block - old_next_block;
946 }
947 }
948
949 return true;
950}
951
952void buflib_pin(struct buflib_context *ctx, int handle)
953{
954 if ((BUFLIB_PARANOIA & PARANOIA_CHECK_PINNING) && handle <= 0)
955 buflib_panic(ctx, "invalid handle pin: %d", handle);
956
957 union buflib_data *data = handle_to_block(ctx, handle);
958 data[BUFLIB_IDX_PIN].pincount++;
959}
960
961void buflib_unpin(struct buflib_context *ctx, int handle)
962{
963 if ((BUFLIB_PARANOIA & PARANOIA_CHECK_PINNING) && handle <= 0)
964 buflib_panic(ctx, "invalid handle unpin: %d", handle);
965
966 union buflib_data *data = handle_to_block(ctx, handle);
967 if (BUFLIB_PARANOIA & PARANOIA_CHECK_PINNING)
968 {
969 if (data[BUFLIB_IDX_PIN].pincount == 0)
970 buflib_panic(ctx, "handle pin underflow: %d", handle);
971 }
972
973 data[BUFLIB_IDX_PIN].pincount--;
974}
975
976unsigned buflib_pin_count(struct buflib_context *ctx, int handle)
977{
978 if ((BUFLIB_PARANOIA & PARANOIA_CHECK_PINNING) && handle <= 0)
979 buflib_panic(ctx, "invalid handle: %d", handle);
980
981 union buflib_data *data = handle_to_block(ctx, handle);
982 return data[BUFLIB_IDX_PIN].pincount;
983}
984
985#ifdef BUFLIB_DEBUG_GET_DATA
986void *buflib_get_data(struct buflib_context *ctx, int handle)
987{
988 if (handle <= 0)
989 buflib_panic(ctx, "invalid handle access: %d", handle);
990
991 return (void*)(ctx->handle_table[-handle].alloc);
992}
993#endif
994
995#ifdef BUFLIB_DEBUG_CHECK_VALID
996void buflib_check_valid(struct buflib_context *ctx)
997{
998 for(union buflib_data *block = ctx->buf_start;
999 block < ctx->alloc_end;
1000 block += abs(block->val))
1001 {
1002 check_block_length(ctx, block);
1003 if (block->val < 0)
1004 continue;
1005
1006 check_block_handle(ctx, block);
1007 }
1008}
1009#endif
1010
1011#ifdef BUFLIB_DEBUG_PRINT
1012int buflib_get_num_blocks(struct buflib_context *ctx)
1013{
1014 int i = 0;
1015
1016 for(union buflib_data *block = ctx->buf_start;
1017 block < ctx->alloc_end;
1018 block += abs(block->val))
1019 {
1020 check_block_length(ctx, block);
1021 ++i;
1022 }
1023
1024 return i;
1025}
1026
1027bool buflib_print_block_at(struct buflib_context *ctx, int block_num,
1028 char *buf, size_t bufsize)
1029{
1030 for(union buflib_data *block = ctx->buf_start;
1031 block < ctx->alloc_end;
1032 block += abs(block->val))
1033 {
1034 check_block_length(ctx, block);
1035
1036 if (block_num-- == 0)
1037 {
1038 snprintf(buf, bufsize, "%8p: val: %4ld (%sallocated)",
1039 block, (long)block->val,
1040 block->val > 0 ? "" : "un");
1041 return true;
1042 }
1043 }
1044
1045 if (bufsize > 0)
1046 *buf = '\0';
1047 return false;
1048}
1049#endif
1050
1051static void check_block_length(struct buflib_context *ctx,
1052 union buflib_data *block)
1053{
1054 if (BUFLIB_PARANOIA & PARANOIA_CHECK_LENGTH)
1055 {
1056 intptr_t length = block[BUFLIB_IDX_LEN].val;
1057
1058 /* Check the block length does not pass beyond the end */
1059 if (length == 0 || block > ctx->alloc_end - abs(length))
1060 {
1061 buflib_panic(ctx, "block len wacky [%p]=%ld",
1062 (void*)&block[BUFLIB_IDX_LEN], (long)length);
1063 }
1064 }
1065}
1066
1067static void check_block_handle(struct buflib_context *ctx,
1068 union buflib_data *block)
1069{
1070 if (BUFLIB_PARANOIA & PARANOIA_CHECK_BLOCK_HANDLE)
1071 {
1072 intptr_t length = block[BUFLIB_IDX_LEN].val;
1073 union buflib_data *h_entry = block[BUFLIB_IDX_HANDLE].handle;
1074
1075 /* Check the handle pointer is properly aligned */
1076 /* TODO: Can we ensure the compiler doesn't optimize this out?
1077 * I dunno, maybe the compiler can assume the pointer is always
1078 * properly aligned due to some C standard voodoo?? */
1079 if (!IS_ALIGNED((uintptr_t)h_entry, alignof(*h_entry)))
1080 {
1081 buflib_panic(ctx, "handle unaligned [%p]=%p",
1082 &block[BUFLIB_IDX_HANDLE], h_entry);
1083 }
1084
1085 /* Check the pointer is actually inside the handle table */
1086 if (h_entry < ctx->last_handle || h_entry >= ctx->handle_table)
1087 {
1088 buflib_panic(ctx, "handle out of bounds [%p]=%p",
1089 &block[BUFLIB_IDX_HANDLE], h_entry);
1090 }
1091
1092 /* Now check the allocation is within the block.
1093 * This is stricter than check_handle(). */
1094 void *alloc = h_entry->alloc;
1095 void *alloc_begin = block;
1096 void *alloc_end = block + length;
1097 /* buflib allows zero length allocations, so alloc_end is inclusive */
1098 if (alloc < alloc_begin || alloc > alloc_end)
1099 {
1100 buflib_panic(ctx, "alloc outside block [%p]=%p, %p-%p",
1101 h_entry, alloc, alloc_begin, alloc_end);
1102 }
1103 }
1104}