firmware/include/buflib.h

   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) 2010 Thomas Martitz
  16 *
  17 * This program is free software; you can redistribute it and/or
  18 * modify it under the terms of the GNU General Public License
  19 * as published by the Free Software Foundation; either version 2
  20 * of the License, or (at your option) any later version.
  21 *
  22 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  23 * KIND, either express or implied.
  24 *
  25 ****************************************************************************/
  26
  27 #ifndef _BUFLIB_H_
  28 #define _BUFLIB_H_
  29 #include <stdint.h>
  30 #include <stdbool.h>
  31 #include <string.h>
  32
  33 /* enable single block debugging */
  34 #define BUFLIB_DEBUG_BLOCK_SINGLE
  35
  36 union buflib_data
  37 {
  38     intptr_t val;
  39     char name[1]; /* actually a variable sized string */
  40     struct buflib_callbacks* ops;
  41     char* alloc;
  42     union buflib_data *handle;
  43 };
  44
  45 struct buflib_context
  46 {
  47     union buflib_data *handle_table;
  48     union buflib_data *first_free_handle;
  49     union buflib_data *last_handle;
  50     union buflib_data *first_free_block;
  51     union buflib_data *buf_start;
  52     union buflib_data *alloc_end;
  53     bool compact;
  54 };
  55
  56 /**
  57  * Callbacks used by the buflib to inform allocation that compaction
  58  * is happening (before data is moved)
  59  *
  60  * Note that buflib tries to move to satisfy new allocations before shrinking.
  61  * So if you have something to resize try to do it outside of the callback.
  62  *
  63  * Regardless of the above, if the allocation is SHRINKABLE, but not
  64  * MUST_NOT_MOVE buflib will move the allocation before even attempting to
  65  * shrink.
  66  */
  67 struct buflib_callbacks {
  68     /**
  69      * This is called before data is moved. Use this to fix up any pointers
  70      * pointing to within the allocation. The size is unchanged
  71      *
  72      * handle: The corresponding handle
  73      * current: The current start of the allocation
  74      * new: The new start of the allocation, after data movement
  75      *
  76      * Return: Return BUFLIB_CB_OK
  77      *
  78      * If NULL: this allocation must not be moved around by the buflib when
  79      * compation occurs
  80      */
  81     int (*move_callback)(int handle, void* current, void* new);
  82     /**
  83      * This is called when the buflib desires to shrink a SHRINKABLE buffer
  84      * in order to satisfy new allocation and if moving other allocations
  85      * failed.
  86      * Move data around as you need and call core_shrink() from within the
  87      * callback to do the shrink (buflib will not move data as part of shrinking)
  88      *
  89      * hint: bit mask containing hints on how shrinking is desired (see below)
  90      * handle: The corresponding handle
  91      * start: The old start of the allocation
  92      *
  93      * Return: Return BUFLIB_CB_OK, or BUFLIB_CB_CANNOT_SHRINK if shirinking
  94      * is impossible at this moment.
  95      *
  96      * if NULL: this allocation cannot be resized.
  97      * It is recommended that allocation that must not move are
  98      * at least shrinkable
  99      */
 100     int (*shrink_callback)(int handle, unsigned hints, void* start, size_t old_size);
 101 };
 102
 103 #define BUFLIB_SHRINK_POS_MASK ((1<<0|1<<1)<<30)
 104 #define BUFLIB_SHRINK_SIZE_MASK (~BUFLIB_SHRINK_POS_MASK)
 105 #define BUFLIB_SHRINK_POS_FRONT (1u<<31)
 106 #define BUFLIB_SHRINK_POS_BACK  (1u<<30)
 107
 108 /**
 109  * Possible return values for the callbacks, some of them can cause
 110  * compaction to fail and therefore new allocations to fail
 111  */
 112 /* Everything alright */
 113 #define BUFLIB_CB_OK 0
 114 /* Tell buflib that resizing failed, possibly future making allocations fail */
 115 #define BUFLIB_CB_CANNOT_SHRINK 1
 116
 117 /**
 118  * Initializes buflib with a caller allocated context and memory pool
 119  */
 120 void buflib_init(struct buflib_context *context, void *buf, size_t size);
 121
 122
 123 /**
 124  * Returns how many bytes left the buflib has to satisfy allocations (not
 125  * accounting possible compaction)
 126  *
 127  * There might be more after a future compaction which is not handled by
 128  * this function.
 129  */
 130 size_t buflib_available(struct buflib_context *ctx);
 131
 132
 133 /**
 134  * Allocates memory from buflib's memory pool
 135  *
 136  * name: A string identifier giving this allocation a name
 137  * size: How many bytes to allocate
 138  *
 139  * Returns: An integer handle identifying this allocation
 140  */
 141 int buflib_alloc(struct buflib_context *context, size_t size);
 142
 143
 144 /**
 145  * Allocates memory from the buflib's memory pool with additional callbacks
 146  * and flags
 147  *
 148  * name: A string identifier giving this allocation a name
 149  * size: How many bytes to allocate
 150  * flags: Flags giving information how this allocation needs to be handled (see below)
 151  * ops: a struct with pointers to callback functions (see below)
 152  *
 153  * Returns: An integer handle identifying this allocation
 154  */
 155 int buflib_alloc_ex(struct buflib_context *ctx, size_t size, const char *name,
 156                     struct buflib_callbacks *ops);
 157
 158
 159 /**
 160  * Gets all available memory from buflib, for temporary use.
 161  * It aquires a lock so allocations from other threads will wait until the
 162  * lock is released (by core_shrink()).
 163  *
 164  * Buflib may call the shrin_callback() after some time if it's in need of
 165  * memory and core_shrink() has not been called yet.
 166  *
 167  * name: A string identifier giving this allocation a name
 168  * size: The actual size will be returned into size
 169  * ops: a struct with pointers to callback functions
 170  *
 171  * Returns: An integer handle identifying this allocation
 172  */
 173 int buflib_alloc_maximum(struct buflib_context* ctx, const char* name,
 174                     size_t *size, struct buflib_callbacks *ops);
 175
 176 /**
 177  * Queries the data pointer for the given handle. It's actually a cheap operation,
 178  * so don't hesitate using it extensivly.
 179  *
 180  * Notice that you need to re-query after every direct or indirect yield(),
 181  * because compaction can happen by other threads which may get your data
 182  * moved around (or you can get notified about changes by callbacks,
 183  * see further above).
 184  *
 185  * handle: The handle corresponding to the allocation
 186  *
 187  * Returns: The start pointer of the allocation
 188  */
 189 static inline void* buflib_get_data(struct buflib_context *context, int handle)
 190 {
 191     return (void*)(context->handle_table[-handle].alloc);
 192 }
 193
 194 /**
 195  * Shrink the memory allocation associated with the given handle
 196  * Mainly intended to be used with the shrink callback (call this in the
 197  * callback and get return BUFLIB_CB_OK, but it can also be called outside
 198  *
 199  * If a lock was aquired for this handle, the lock will be unlocked, assuming
 200  * the allocation has freed memory for future allocation by other threads.
 201  *
 202  * Note that you must move/copy data around yourself before calling this,
 203  * buflib will not do this as part of shrinking.
 204  *
 205  * handle: The handle identifying this allocation
 206  * new_start: the new start of the allocation
 207  * new_size: the new size of the allocation
 208  *
 209  * Returns: true if shrinking was successful. Otherwise it returns false,
 210  * without having modified memory and without having unlocked the lock.
 211  *
 212  */
 213 bool buflib_shrink(struct buflib_context *ctx, int handle, void* newstart, size_t new_size);
 214
 215 /**
 216  * Frees memory associated with the given handle
 217  */
 218 void buflib_free(struct buflib_context *context, int handle);
 219
 220 /**
 221  * Moves the underlying buflib buffer up by size bytes (as much as
 222  * possible for size == 0) without moving the end. This effectively
 223  * reduces the available space by taking away managable space from the
 224  * front. This space is not available for new allocations anymore.
 225  *
 226  * To make space available in the front, everything is moved up.
 227  * It does _NOT_ call the move callbacks
 228  *
 229  *
 230  * size: size in bytes to move the buffer up (take away). The actual
 231  * bytes moved is returned in this
 232  * Returns: The new start of the underlying buflib buffer
 233  */
 234 void* buflib_buffer_out(struct buflib_context *ctx, size_t *size);
 235
 236 /**
 237  * Moves the underlying buflib buffer down by size bytes without
 238  * moving the end. This grows the buflib buffer by adding space to the front.
 239  * The new bytes are available for new allocations.
 240  *
 241  * Everything is moved down, and the new free space will be in the middle.
 242  * It does _NOT_ call the move callbacks.
 243  *
 244  * size: size in bytes to move the buffer down (new free space)
 245  */
 246 void buflib_buffer_in(struct buflib_context *ctx, int size);
 247
 248 /* debugging */
 249
 250 /**
 251  * Returns the name, as given to core_alloc() and core_allloc_ex(), of the
 252  * allocation associated with the given handle
 253  *
 254  * handle: The handle indicating the allocation
 255  *
 256  * Returns: A pointer to the string identifier of the allocation
 257  */
 258 const char* buflib_get_name(struct buflib_context *ctx, int handle);
 259
 260 /**
 261  * Prints an overview of all current allocations with the help
 262  * of the passed printer helper
 263  *
 264  * This walks only the handle table and prints only valid allocations
 265  *
 266  * Only available if BUFLIB_DEBUG_BLOCKS is defined
 267  */
 268 void buflib_print_allocs(struct buflib_context *ctx, void (*print)(int, const char*));
 269
 270 /**
 271  * Prints an overview of all blocks in the buflib buffer, allocated
 272  * or unallocated, with the help pf the passted printer helper
 273  *
 274  * This walks the entire buffer and prints unallocated space also.
 275  * The output is also different from buflib_print_allocs().
 276  *
 277  * Only available if BUFLIB_DEBUG_BLOCKS is defined
 278  */
 279 void buflib_print_blocks(struct buflib_context *ctx, void (*print)(int, const char*));
 280
 281 /**
 282  * Gets the number of blocks in the entire buffer, allocated or unallocated
 283  *
 284  * Only available if BUFLIB_DEBUG_BLOCK_SIGNLE is defined
 285  */
 286 int buflib_get_num_blocks(struct buflib_context *ctx);
 287
 288 /**
 289  * Print information about a single block as indicated by block_num
 290  * into buf
 291  *
 292  * buflib_get_num_blocks() beforehand to get the total number of blocks,
 293  * as passing an block_num higher than that is undefined
 294  *
 295  * Only available if BUFLIB_DEBUG_BLOCK_SIGNLE is defined
 296  */
 297 void buflib_print_block_at(struct buflib_context *ctx, int block_num,
 298                             char* buf, size_t bufsize);
 299 #endif