apps/plugins/lib/buflib.c

   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 *
  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.
  20 *
  21 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  22 * KIND, either express or implied.
  23 *
  24 ****************************************************************************/
  25
  26 #include <stdlib.h> /* for abs() */
  27 #include "buflib.h"
  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.
  41  */
  42
  43 /* Initialize buffer manager */
  44 void
  45 buflib_init(struct buflib_context *ctx, void *buf, size_t size)
  46 {
  47     union buflib_data *bd_buf = buf;
  48
  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.
  60      */
  61     ctx->alloc_end = bd_buf;
  62     ctx->compact = true;
  63 }
  64
  65 /* Allocate a new handle, returning 0 on failure */
  66 static inline
  67 union buflib_data* handle_alloc(struct buflib_context *ctx)
  68 {
  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.
  73      */
  74     for (handle = ctx->first_free_handle; handle >= ctx->last_handle; handle--)
  75         if (!handle->ptr)
  76             break;
  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.
  79      */
  80     if (handle < ctx->last_handle)
  81     {
  82         if (handle >= ctx->alloc_end)
  83             ctx->last_handle--;
  84         else
  85             return NULL;
  86     }
  87     handle->val = -1;
  88     return handle;
  89 }
  90
  91 /* Free one handle, shrinking the handle table if it's the last one */
  92 static inline
  93 void handle_free(struct buflib_context *ctx, union buflib_data *handle)
  94 {
  95     handle->ptr = 0;
  96     /* Update free handle lower bound if this handle has a lower index than the
  97      * old one.
  98      */
  99     if (handle > ctx->first_free_handle)
 100         ctx->first_free_handle = handle;
 101     if (handle == ctx->last_handle)
 102         ctx->last_handle++;
 103     else
 104         ctx->compact = false;
 105 }
 106
 107 /* Shrink the handle table, returning true if its size was reduced, false if
 108  * not
 109  */
 110 static inline
 111 bool
 112 handle_table_shrink(struct buflib_context *ctx)
 113 {
 114     bool rv;
 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;
 121     return rv;
 122 }
 123
 124 /* Compact allocations and handle table, adjusting handle pointers as needed.
 125  * Return true if any space was freed or consolidated, false otherwise.
 126  */
 127 static bool
 128 buflib_compact(struct buflib_context *ctx)
 129 {
 130     union buflib_data *block = ctx->first_free_block, *new_block;
 131     int shift = 0, len;
 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)
 135     {
 136         len = block->val;
 137         /* This block is free, add its length to the shift value */
 138         if (len < 0)
 139         {
 140             shift += len;
 141             len = -len;
 142             continue;
 143         }
 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.
 147          */
 148         if (shift)
 149         {
 150             new_block = block + shift;
 151             block[1].ptr->ptr = new_block + 2;
 152             rb->memmove(new_block, block, len * sizeof(union buflib_data));
 153         }
 154     }
 155     /* Move the end-of-allocation mark, and return true if any new space has
 156      * been freed.
 157      */
 158     ctx->alloc_end += shift;
 159     ctx->first_free_block = ctx->alloc_end;
 160     ctx->compact = true;
 161     return ret || shift;
 162 }
 163
 164 /* Shift buffered items by size units, and update handle pointers. The shift
 165  * value must be determined to be safe *before* calling.
 166  */
 167 static void
 168 buflib_buffer_shift(struct buflib_context *ctx, int shift)
 169 {
 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++)
 174         if (ptr->ptr)
 175             ptr->ptr += shift;
 176     ctx->first_free_block += shift;
 177     ctx->buf_start += shift;
 178     ctx->alloc_end += shift;
 179 }
 180
 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.
 183  */
 184 void*
 185 buflib_buffer_out(struct buflib_context *ctx, size_t *size)
 186 {
 187     if (!ctx->compact)
 188         buflib_compact(ctx);
 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)
 192     {
 193         avail = (*size + sizeof(union buflib_data) - 1)
 194             / sizeof(union buflib_data);
 195         avail_b = avail * sizeof(union buflib_data);
 196     }
 197     *size = avail_b;
 198     void *ret = ctx->buf_start;
 199     buflib_buffer_shift(ctx, avail);
 200     return ret;
 201 }
 202
 203 /* Shift buffered items down by size bytes */
 204 void
 205 buflib_buffer_in(struct buflib_context *ctx, int size)
 206 {
 207     size /= sizeof(union buflib_data);
 208     buflib_buffer_shift(ctx, -size);
 209 }
 210
 211 /* Allocate a buffer of size bytes, returning a handle for it */
 212 int
 213 buflib_alloc(struct buflib_context *ctx, size_t size)
 214 {
 215     union buflib_data *handle, *block;
 216     bool last = false;
 217     /* This really is assigned a value before use */
 218     int block_len;
 219     size = (size + sizeof(union buflib_data) - 1) /
 220            sizeof(union buflib_data) + 2;
 221 handle_alloc:
 222     handle = handle_alloc(ctx);
 223     if (!handle)
 224     {
 225         /* If allocation has failed, and compaction has succeded, it may be
 226          * possible to get a handle by trying again.
 227          */
 228         if (!ctx->compact && buflib_compact(ctx))
 229             goto handle_alloc;
 230         else
 231             return 0;
 232     }
 233
 234 buffer_alloc:
 235     for (block = ctx->first_free_block;; block += block_len)
 236     {
 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.
 242          */
 243         if(block == ctx->alloc_end)
 244         {
 245             last = true;
 246             block_len = ctx->last_handle - block;
 247             if ((size_t)block_len < size)
 248                 block = NULL;
 249             break;
 250         }
 251         block_len = block->val;
 252         /* blocks with positive length are already allocated. */
 253         if(block_len > 0)
 254             continue;
 255         block_len = -block_len;
 256         /* The search is first-fit, any fragmentation this causes will be
 257          * handled at compaction.
 258          */
 259         if ((size_t)block_len >= size)
 260             break;
 261     }
 262     if (!block)
 263     {
 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.
 267          */
 268         if (!ctx->compact && buflib_compact(ctx))
 269         {
 270             goto buffer_alloc;
 271         } else {
 272             handle->val=1;
 273             handle_free(ctx, handle);
 274             return 0;
 275         }
 276     }
 277
 278     /* Set up the allocated block, by marking the size allocated, and storing
 279      * a pointer to the handle.
 280      */
 281     block->val = size;
 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.
 286      */
 287     if (block == ctx->first_free_block)
 288         ctx->first_free_block += size;
 289     block += size;
 290     /* alloc_end must be kept current if we're taking the last block. */
 291     if (last)
 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;
 298 }
 299
 300 /* Free the buffer associated with handle_num. */
 301 void
 302 buflib_free(struct buflib_context *ctx, int handle_num)
 303 {
 304     union buflib_data *handle = ctx->handle_table - handle_num,
 305                       *freed_block = handle->ptr - 2,
 306                       *block = ctx->first_free_block,
 307                       *next_block = 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.
 310      */
 311     while (next_block < freed_block)
 312     {
 313         block = next_block;
 314         next_block += abs(block->val);
 315     }
 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.
 318      */
 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.
 324      */
 325     else
 326     {
 327         block = freed_block;
 328         block->val = -block->val;
 329     }
 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.
 336      */
 337     else {
 338         ctx->compact = false;
 339         if (next_block->val < 0)
 340             block->val += next_block->val;
 341     }
 342     handle_free(ctx, handle);
 343     handle->ptr = NULL;
 344     /* If this block is before first_free_block, it becomes the new starting
 345      * point for free-block search.
 346      */
 347     if (block < ctx->first_free_block)
 348         ctx->first_free_block = block;
 349 }