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
  34
  35 union buflib_data
  36 {
  37     intptr_t val;
  38     char name[1]; /* actually a variable sized string */
  39     struct buflib_callbacks* ops;
  40     char* alloc;
  41     union buflib_data *handle;
  42 };
  43
  44 struct buflib_context
  45 {
  46     union buflib_data *handle_table;
  47     union buflib_data *first_free_handle;
  48     union buflib_data *last_handle;
  49     union buflib_data *first_free_block;
  50     union buflib_data *buf_start;
  51     union buflib_data *alloc_end;
  52     volatile int handle_lock;
  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
  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  * Shrink the memory allocation associated with the given handle
 178  * Mainly intended to be used with the shrink callback (call this in the
 179  * callback and get return BUFLIB_CB_OK, but it can also be called outside
 180  *
 181  * If a lock was aquired for this handle, the lock will be unlocked, assuming
 182  * the allocation has freed memory for future allocation by other threads.
 183  *
 184  * Note that you must move/copy data around yourself before calling this,
 185  * buflib will not do this as part of shrinking.
 186  *
 187  * handle: The handle identifying this allocation
 188  * new_start: the new start of the allocation
 189  * new_size: the new size of the allocation
 190  *
 191  * Returns: true if shrinking was successful. Otherwise it returns false,
 192  * without having modified memory and without having unlocked the lock.
 193  *
 194  */
 195 bool buflib_shrink(struct buflib_context *ctx, int handle, void* newstart, size_t new_size);
 196
 197 /**
 198  * Frees memory associated with the given handle
 199  */
 200 void buflib_free(struct buflib_context *context, int handle);
 201 void* buflib_buffer_out(struct buflib_context *ctx, size_t *size);
 202 void buflib_buffer_in(struct buflib_context *ctx, int size);
 203
 204 /* debugging */
 205
 206 /**
 207  * Returns the name, as given to core_alloc() and core_allloc_ex(), of the
 208  * allocation associated with the given handle
 209  *
 210  * handle: The handle indicating the allocation
 211  *
 212  * Returns: A pointer to the string identifier of the allocation
 213  */
 214 const char* buflib_get_name(struct buflib_context *ctx, int handle);
 215
 216 /**
 217  * Prints an overview of all current allocations with the help
 218  * of the passed printer helper
 219  */
 220 void buflib_print_allocs(struct buflib_context *ctx, void (*print)(const char*));
 221 void buflib_print_blocks(struct buflib_context *ctx, void (*print)(const char*));
 222
 223 /**
 224  * Queries the data pointer for the given handle. It's actually a cheap operation,
 225  * so don't hesitate using it extensivly.
 226  *
 227  * Notice that you need to re-query after every direct or indirect yield(),
 228  * because compaction can happen by other threads which may get your data
 229  * moved around (or you can get notified about changes by callbacks,
 230  * see further below).
 231  *
 232  * handle: The handle corresponding to the allocation
 233  *
 234  * Returns: The start pointer of the allocation
 235  */
 236 static inline void* buflib_get_data(struct buflib_context *context, int handle)
 237 {
 238     return (void*)(context->handle_table[-handle].alloc);
 239 }
 240 #endif