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 "buflib.h"
  27
  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 #define ABS(x) \
  44 ({ \
  45     typeof(x) xtmp_abs_ = x; \
  46     xtmp_abs_ = xtmp_abs_ < 0 ? -xtmp_abs_ : xtmp_abs_; \
  47     xtmp_abs_; \
  48 })
  49
  50 /* Initialize buffer manager */
  51 void
  52 buflib_init(struct buflib_context *ctx, void *buf, size_t size)
  53 {
  54     union buflib_data *bd_buf = buf;
  55
  56     /* Align on sizeof(buflib_data), to prevent unaligned access */
  57     ALIGN_BUFFER(bd_buf, size, sizeof(union buflib_data));
  58     size /= sizeof(union buflib_data);
  59     /* The handle table is initialized with no entries */
  60     ctx->handle_table = bd_buf + size;
  61     ctx->last_handle = bd_buf + size;
  62     ctx->first_free_handle = bd_buf + size - 1;
  63     ctx->first_free_block = bd_buf;
  64     ctx->buf_start = bd_buf;
  65     /* A marker is needed for the end of allocated data, to make sure that it
  66      * does not collide with the handle table, and to detect end-of-buffer.
  67      */
  68     ctx->alloc_end = bd_buf;
  69     ctx->compact = true;
  70 }
  71
  72 /* Allocate a new handle, returning 0 on failure */
  73 static inline
  74 union buflib_data* handle_alloc(struct buflib_context *ctx)
  75 {
  76     union buflib_data *handle;
  77     /* first_free_handle is a lower bound on free handles, work through the
  78      * table from there until a handle containing NULL is found, or the end
  79      * of the table is reached.
  80      */
  81     for (handle = ctx->first_free_handle; handle >= ctx->last_handle; handle--)
  82         if (!handle->ptr)
  83             break;
  84     /* If the search went past the end of the table, it means we need to extend
  85      * the table to get a new handle.
  86      */
  87     if (handle < ctx->last_handle)
  88     {
  89         if (handle >= ctx->alloc_end)
  90             ctx->last_handle--;
  91         else
  92             return NULL;
  93     }
  94     handle->val = -1;
  95     return handle;
  96 }
  97
  98 /* Free one handle, shrinking the handle table if it's the last one */
  99 static inline
 100 void handle_free(struct buflib_context *ctx, union buflib_data *handle)
 101 {
 102     handle->ptr = 0;
 103     /* Update free handle lower bound if this handle has a lower index than the
 104      * old one.
 105      */
 106     if (handle > ctx->first_free_handle)
 107         ctx->first_free_handle = handle;
 108     if (handle == ctx->last_handle)
 109         ctx->last_handle++;
 110     else
 111         ctx->compact = false;
 112 }
 113
 114 /* Shrink the handle table, returning true if its size was reduced, false if
 115  * not
 116  */
 117 static inline
 118 bool
 119 handle_table_shrink(struct buflib_context *ctx)
 120 {
 121     bool rv;
 122     union buflib_data *handle;
 123     for (handle = ctx->last_handle; !(handle->ptr); handle++);
 124     if (handle > ctx->first_free_handle)
 125         ctx->first_free_handle = handle - 1;
 126     rv = handle == ctx->last_handle;
 127     ctx->last_handle = handle;
 128     return rv;
 129 }
 130
 131 /* Compact allocations and handle table, adjusting handle pointers as needed.
 132  * Return true if any space was freed or consolidated, false otherwise.
 133  */
 134 static bool
 135 buflib_compact(struct buflib_context *ctx)
 136 {
 137     union buflib_data *block = ctx->first_free_block, *new_block;
 138     int shift = 0, len;
 139     /* Store the results of attempting to shrink the handle table */
 140     bool ret = handle_table_shrink(ctx);
 141     for(; block != ctx->alloc_end; block += len)
 142     {
 143         len = block->val;
 144         /* This block is free, add its length to the shift value */
 145         if (len < 0)
 146         {
 147             shift += len;
 148             len = -len;
 149             continue;
 150         }
 151         /* If shift is non-zero, it represents the number of places to move
 152          * blocks down in memory. Calculate the new address for this block,
 153          * update its entry in the handle table, and then move its contents.
 154          */
 155         if (shift)
 156         {
 157             new_block = block + shift;
 158             block[1].ptr->ptr = new_block + 2;
 159             rb->memmove(new_block, block, len * sizeof(union buflib_data));
 160         }
 161     }
 162     /* Move the end-of-allocation mark, and return true if any new space has
 163      * been freed.
 164      */
 165     ctx->alloc_end += shift;
 166     ctx->first_free_block = ctx->alloc_end;
 167     ctx->compact = true;
 168     return ret || shift;
 169 }
 170
 171 /* Shift buffered items by size units, and update handle pointers. The shift
 172  * value must be determined to be safe *before* calling.
 173  */
 174 static void
 175 buflib_buffer_shift(struct buflib_context *ctx, int shift)
 176 {
 177     rb->memmove(ctx->buf_start + shift, ctx->buf_start,
 178         (ctx->alloc_end - ctx->buf_start) * sizeof(union buflib_data));
 179     union buflib_data *ptr;
 180     for (ptr = ctx->last_handle; ptr < ctx->handle_table; ptr++)
 181         if (ptr->ptr)
 182             ptr->ptr += shift;
 183     ctx->first_free_block += shift;
 184     ctx->buf_start += shift;
 185     ctx->alloc_end += shift;
 186 }
 187
 188 /* Shift buffered items up by size bytes, or as many as possible if size == 0.
 189  * Set size to the number of bytes freed.
 190  */
 191 void*
 192 buflib_buffer_out(struct buflib_context *ctx, size_t *size)
 193 {
 194     if (!ctx->compact)
 195         buflib_compact(ctx);
 196     size_t avail = ctx->last_handle - ctx->alloc_end;
 197     size_t avail_b = avail * sizeof(union buflib_data);
 198     if (*size && *size < avail_b)
 199     {
 200         avail = (*size + sizeof(union buflib_data) - 1)
 201             / sizeof(union buflib_data);
 202         avail_b = avail * sizeof(union buflib_data);
 203     }
 204     *size = avail_b;
 205     void *ret = ctx->buf_start;
 206     buflib_buffer_shift(ctx, avail);
 207     return ret;
 208 }
 209
 210 /* Shift buffered items down by size bytes */
 211 void
 212 buflib_buffer_in(struct buflib_context *ctx, int size)
 213 {
 214     size /= sizeof(union buflib_data);
 215     buflib_buffer_shift(ctx, -size);
 216 }
 217
 218 /* Allocate a buffer of size bytes, returning a handle for it */
 219 int
 220 buflib_alloc(struct buflib_context *ctx, size_t size)
 221 {
 222     union buflib_data *handle, *block;
 223     bool last = false;
 224     /* This really is assigned a value before use */
 225     int block_len;
 226     size = (size + sizeof(union buflib_data) - 1) /
 227            sizeof(union buflib_data) + 2;
 228 handle_alloc:
 229     handle = handle_alloc(ctx);
 230     if (!handle)
 231     {
 232         /* If allocation has failed, and compaction has succeded, it may be
 233          * possible to get a handle by trying again.
 234          */
 235         if (!ctx->compact && buflib_compact(ctx))
 236             goto handle_alloc;
 237         else
 238             return 0;
 239     }
 240
 241 buffer_alloc:
 242     for (block = ctx->first_free_block;; block += block_len)
 243     {
 244         /* If the last used block extends all the way to the handle table, the
 245          * block "after" it doesn't have a header. Because of this, it's easier
 246          * to always find the end of allocation by saving a pointer, and always
 247          * calculate the free space at the end by comparing it to the
 248          * last_handle pointer.
 249          */
 250         if(block == ctx->alloc_end)
 251         {
 252             last = true;
 253             block_len = ctx->last_handle - block;
 254             if ((size_t)block_len < size)
 255                 block = NULL;
 256             break;
 257         }
 258         block_len = block->val;
 259         /* blocks with positive length are already allocated. */
 260         if(block_len > 0)
 261             continue;
 262         block_len = -block_len;
 263         /* The search is first-fit, any fragmentation this causes will be
 264          * handled at compaction.
 265          */
 266         if ((size_t)block_len >= size)
 267             break;
 268     }
 269     if (!block)
 270     {
 271         /* Try compacting if allocation failed, but only if the handle
 272          * allocation did not trigger compaction already, since there will
 273          * be no further gain.
 274          */
 275         if (!ctx->compact && buflib_compact(ctx))
 276         {
 277             goto buffer_alloc;
 278         } else {
 279             handle->val=1;
 280             handle_free(ctx, handle);
 281             return 0;
 282         }
 283     }
 284
 285     /* Set up the allocated block, by marking the size allocated, and storing
 286      * a pointer to the handle.
 287      */
 288     block->val = size;
 289     block[1].ptr = handle;
 290     handle->ptr = block + 2;
 291     /* If we have just taken the first free block, the next allocation search
 292      * can save some time by starting after this block.
 293      */
 294     if (block == ctx->first_free_block)
 295         ctx->first_free_block += size;
 296     block += size;
 297     /* alloc_end must be kept current if we're taking the last block. */
 298     if (last)
 299         ctx->alloc_end = block;
 300     /* Only free blocks *before* alloc_end have tagged length. */
 301     else if ((size_t)block_len > size)
 302         block->val = size - block_len;
 303     /* Return the handle index as a positive integer. */
 304     return ctx->handle_table - handle;
 305 }
 306
 307 /* Free the buffer associated with handle_num. */
 308 void
 309 buflib_free(struct buflib_context *ctx, int handle_num)
 310 {
 311     union buflib_data *handle = ctx->handle_table - handle_num,
 312                       *freed_block = handle->ptr - 2,
 313                       *block = ctx->first_free_block,
 314                       *next_block = block;
 315     /* We need to find the block before the current one, to see if it is free
 316      * and can be merged with this one.
 317      */
 318     while (next_block < freed_block)
 319     {
 320         block = next_block;
 321         next_block += ABS(block->val);
 322     }
 323     /* If next_block == block, the above loop didn't go anywhere. If it did,
 324      * and the block before this one is empty, we can combine them.
 325      */
 326     if (next_block == freed_block && next_block != block && block->val < 0)
 327         block->val -= freed_block->val;
 328     /* Otherwise, set block to the newly-freed block, and mark it free, before
 329      * continuing on, since the code below exects block to point to a free
 330      * block which may have free space after it.
 331      */
 332     else
 333     {
 334         block = freed_block;
 335         block->val = -block->val;
 336     }
 337     next_block = block - block->val;
 338     /* Check if we are merging with the free space at alloc_end. */
 339     if (next_block == ctx->alloc_end)
 340         ctx->alloc_end = block;
 341     /* Otherwise, the next block might still be a "normal" free block, and the
 342      * mid-allocation free means that the buffer is no longer compact.
 343      */
 344     else {
 345         ctx->compact = false;
 346         if (next_block->val < 0)
 347             block->val += next_block->val;
 348     }
 349     handle_free(ctx, handle);
 350     handle->ptr = NULL;
 351     /* If this block is before first_free_block, it becomes the new starting
 352      * point for free-block search.
 353      */
 354     if (block < ctx->first_free_block)
 355         ctx->first_free_block = block;
 356 }