GSoC/Buflib: Add buflib memory alocator to the core.

The buflib memory allocator is handle based and can free and
compact, move or resize memory on demand. This allows to effeciently
allocate memory dynamically without an MMU, by avoiding fragmentation
through memory compaction.

This patch adds the buflib library to the core, along with
convinience wrappers to omit the context parameter. Compaction is
not yet enabled, but will be in a later patch. Therefore, this acts as a
replacement for buffer_alloc/buffer_get_buffer() with the benifit of a debug
menu.

See buflib.h for some API documentation.

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@30380 a1c6a512-1295-4272-9138-f99709370657

2 files changed, 355 insertions, 0 deletions

diff --git a/firmware/include/buflib.h b/firmware/include/buflib.h
new file mode 100644
index 0000000000..db7b5ec50a
--- /dev/null
+++ b/firmware/include/buflib.h
@@ -0,0 +1,319 @@
+/***************************************************************************
+*             __________               __   ___.
+*   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+*   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+*   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+*   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+*                     \/            \/     \/    \/            \/
+* $Id$
+*
+* This is a memory allocator designed to provide reasonable management of free
+* space and fast access to allocated data. More than one allocator can be used
+* at a time by initializing multiple contexts.
+*
+* Copyright (C) 2009 Andrew Mahone
+* Copyright (C) 2011 Thomas Martitz
+*
+* This program is free software; you can redistribute it and/or
+* modify it under the terms of the GNU General Public License
+* as published by the Free Software Foundation; either version 2
+* of the License, or (at your option) any later version.
+*
+* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+* KIND, either express or implied.
+*
+****************************************************************************/
+
+#ifndef _BUFLIB_H_
+#define _BUFLIB_H_
+#include <stdint.h>
+#include <stdbool.h>
+#include <string.h>
+
+/* enable single block debugging */
+#define BUFLIB_DEBUG_BLOCK_SINGLE
+
+union buflib_data
+{
+    intptr_t val;
+    char name[1]; /* actually a variable sized string */
+    struct buflib_callbacks* ops;
+    char* alloc;
+    union buflib_data *handle;
+};
+
+struct buflib_context
+{
+    union buflib_data *handle_table;
+    union buflib_data *first_free_handle;
+    union buflib_data *last_handle;
+    union buflib_data *first_free_block;
+    union buflib_data *buf_start;
+    union buflib_data *alloc_end;
+    bool compact;
+};
+
+/**
+ * Callbacks used by the buflib to inform allocation that compaction
+ * is happening (before data is moved)
+ *
+ * Note that buflib tries to move to satisfy new allocations before shrinking.
+ * So if you have something to resize try to do it outside of the callback.
+ *
+ * Regardless of the above, if the allocation is SHRINKABLE, but not
+ * MUST_NOT_MOVE buflib will move the allocation before even attempting to
+ * shrink.
+ */
+struct buflib_callbacks {
+    /**
+     * This is called before data is moved. Use this to fix up any cached
+     * pointers pointing to inside the allocation. The size is unchanged.
+     *
+     * This is not needed if you don't cache the data pointer (but always
+     * call buflib_get_data()) and don't pass pointer to the data to yielding
+     * functions.
+     *
+     * handle: The corresponding handle
+     * current: The current start of the allocation
+     * new: The new start of the allocation, after data movement
+     *
+     * Return: Return BUFLIB_CB_OK, or BUFLIB_CB_CANNOT_MOVE if movement
+     * is impossible at this moment.
+     *
+     * If NULL: this allocation must not be moved around by the buflib when
+     * compation occurs
+     */
+    int (*move_callback)(int handle, void* current, void* new);
+    /**
+     * This is called when the buflib desires to shrink a buffer
+     * in order to satisfy new allocation. This happens when buflib runs
+     * out of memory, e.g. because buflib_alloc_maximum() was called.
+     * Move data around as you need to make space and call core_shrink() as
+     * appropriate from within the callback to complete the shrink operation.
+     * buflib will not move data as part of shrinking.
+     *
+     * hint: bit mask containing hints on how shrinking is desired (see below)
+     * handle: The corresponding handle
+     * start: The old start of the allocation
+     *
+     * Return: Return BUFLIB_CB_OK, or BUFLIB_CB_CANNOT_SHRINK if shirinking
+     * is impossible at this moment.
+     *
+     * if NULL: this allocation cannot be resized.
+     * It is recommended that allocation that must not move are
+     * at least shrinkable
+     */
+    int (*shrink_callback)(int handle, unsigned hints, void* start, size_t old_size);
+};
+
+#define BUFLIB_SHRINK_POS_MASK ((1<<0|1<<1)<<30)
+#define BUFLIB_SHRINK_SIZE_MASK (~BUFLIB_SHRINK_POS_MASK)
+#define BUFLIB_SHRINK_POS_FRONT (1u<<31)
+#define BUFLIB_SHRINK_POS_BACK  (1u<<30)
+
+/**
+ * Possible return values for the callbacks, some of them can cause
+ * compaction to fail and therefore new allocations to fail
+ */
+/* Everything alright */
+#define BUFLIB_CB_OK 0
+/* Tell buflib that moving failed. Buflib may retry to move at any point */
+#define BUFLIB_CB_CANNOT_MOVE 1
+/* Tell buflib that resizing failed, possibly future making allocations fail */
+#define BUFLIB_CB_CANNOT_SHRINK 1
+
+/**
+ * Initializes buflib with a caller allocated context instance and memory pool.
+ *
+ * The buflib_context instance needs to be passed to every other buflib
+ * function. It's should be considered opaque, even though it is not yet
+ * (that's to make inlining core_get_data() possible). The documentation
+ * of the other functions will not describe the context
+ * instance paramter further as it's obligatory.
+ *
+ * context: The new buflib instance to be initialized, allocated by the caller
+ * size: The size of the memory pool
+ */
+void buflib_init(struct buflib_context *context, void *buf, size_t size);
+
+
+/**
+ * Returns how many bytes left the buflib has to satisfy allocations.
+ *
+ * This function does not yet consider possible compaction so there might
+ * be more space left. This may change in the future.
+ *
+ * Returns: The number of bytes left in the memory pool.
+ */
+size_t buflib_available(struct buflib_context *ctx);
+
+
+/**
+ * Allocates memory from buflib's memory pool
+ *
+ * size: How many bytes to allocate
+ *
+ * Returns: An integer handle identifying this allocation
+ */
+int buflib_alloc(struct buflib_context *context, size_t size);
+
+
+/**
+ * Allocates memory from the buflib's memory pool with additional callbacks
+ * and flags
+ *
+ * name: A string identifier giving this allocation a name
+ * size: How many bytes to allocate
+ * ops: a struct with pointers to callback functions (see above)
+ *
+ * Returns: An integer handle identifying this allocation
+ */
+int buflib_alloc_ex(struct buflib_context *ctx, size_t size, const char *name,
+                    struct buflib_callbacks *ops);
+
+
+/**
+ * Gets all available memory from buflib, for temporary use.
+ *
+ * Since this effectively makes all future allocations fail (unless
+ * another allocation is freed in the meantime), you should definitely provide
+ * a shrink callback if you plan to hold the buffer for a longer period. This
+ * will allow buflib to permit allocations by shrinking the buffer returned by
+ * this function.
+ *
+ * Note that this currently gives whatever buflib_available() returns. However,
+ * do not depend on this behavior, it may change.
+ *
+ * name: A string identifier giving this allocation a name
+ * size: The actual size will be returned into size
+ * ops: a struct with pointers to callback functions
+ *
+ * Returns: An integer handle identifying this allocation
+ */
+int buflib_alloc_maximum(struct buflib_context* ctx, const char* name,
+                    size_t *size, struct buflib_callbacks *ops);
+
+/**
+ * Queries the data pointer for the given handle. It's actually a cheap
+ * operation, don't hesitate using it extensivly.
+ *
+ * Notice that you need to re-query after every direct or indirect yield(),
+ * because compaction can happen by other threads which may get your data
+ * moved around (or you can get notified about changes by callbacks,
+ * see further above).
+ *
+ * handle: The handle corresponding to the allocation
+ *
+ * Returns: The start pointer of the allocation
+ */
+static inline void* buflib_get_data(struct buflib_context *context, int handle)
+{
+    return (void*)(context->handle_table[-handle].alloc);
+}
+
+/**
+ * Shrink the memory allocation associated with the given handle
+ * Mainly intended to be used with the shrink callback, but it can also
+ * be called outside as well, e.g. to give back buffer space allocated
+ * with buflib_alloc_maximum().
+ *
+ * Note that you must move/copy data around yourself before calling this,
+ * buflib will not do this as part of shrinking.
+ *
+ * handle: The handle identifying this allocation
+ * new_start: the new start of the allocation
+ * new_size: the new size of the allocation
+ *
+ * Returns: true if shrinking was successful. Otherwise it returns false,
+ * without having modified memory.
+ *
+ */
+bool buflib_shrink(struct buflib_context *ctx, int handle, void* newstart, size_t new_size);
+
+/**
+ * Frees memory associated with the given handle
+ *
+ * Returns: 0 (to invalidate handles in one line)
+ */
+int buflib_free(struct buflib_context *context, int handle);
+
+/**
+ * Moves the underlying buflib buffer up by size bytes (as much as
+ * possible for size == 0) without moving the end. This effectively
+ * reduces the available space by taking away managable space from the
+ * front. This space is not available for new allocations anymore.
+ *
+ * To make space available in the front, everything is moved up.
+ * It does _NOT_ call the move callbacks
+ * 
+ *
+ * size: size in bytes to move the buffer up (take away). The actual
+ * bytes moved is returned in this
+ * Returns: The new start of the underlying buflib buffer
+ */
+void* buflib_buffer_out(struct buflib_context *ctx, size_t *size);
+
+/**
+ * Moves the underlying buflib buffer down by size bytes without
+ * moving the end. This grows the buflib buffer by adding space to the front.
+ * The new bytes are available for new allocations.
+ *
+ * Everything is moved down, and the new free space will be in the middle.
+ * It does _NOT_ call the move callbacks.
+ *
+ * size: size in bytes to move the buffer down (new free space)
+ */
+void buflib_buffer_in(struct buflib_context *ctx, int size);
+
+/* debugging */
+
+/**
+ * Returns the name, as given to core_alloc() and core_allloc_ex(), of the
+ * allocation associated with the given handle
+ *
+ * handle: The handle indicating the allocation
+ *
+ * Returns: A pointer to the string identifier of the allocation
+ */
+const char* buflib_get_name(struct buflib_context *ctx, int handle);
+
+/**
+ * Prints an overview of all current allocations with the help
+ * of the passed printer helper
+ *
+ * This walks only the handle table and prints only valid allocations
+ *
+ * Only available if BUFLIB_DEBUG_BLOCKS is defined
+ */
+void buflib_print_allocs(struct buflib_context *ctx, void (*print)(int, const char*));
+
+/**
+ * Prints an overview of all blocks in the buflib buffer, allocated
+ * or unallocated, with the help pf the passted printer helper
+ *
+ * This walks the entire buffer and prints unallocated space also.
+ * The output is also different from buflib_print_allocs().
+ *
+ * Only available if BUFLIB_DEBUG_BLOCKS is defined
+ */
+void buflib_print_blocks(struct buflib_context *ctx, void (*print)(int, const char*));
+
+/**
+ * Gets the number of blocks in the entire buffer, allocated or unallocated
+ *
+ * Only available if BUFLIB_DEBUG_BLOCK_SIGNLE is defined
+ */
+int buflib_get_num_blocks(struct buflib_context *ctx);
+
+/**
+ * Print information about a single block as indicated by block_num
+ * into buf
+ *
+ * buflib_get_num_blocks() beforehand to get the total number of blocks,
+ * as passing an block_num higher than that is undefined
+ *
+ * Only available if BUFLIB_DEBUG_BLOCK_SIGNLE is defined
+ */
+void buflib_print_block_at(struct buflib_context *ctx, int block_num,
+                            char* buf, size_t bufsize);
+#endif
diff --git a/firmware/include/core_alloc.h b/firmware/include/core_alloc.h
new file mode 100644
index 0000000000..f5206c9db9
--- /dev/null
+++ b/firmware/include/core_alloc.h
@@ -0,0 +1,36 @@
+
+#ifndef __CORE_ALLOC_H__
+#define __CORE_ALLOC_H__
+#include <string.h>
+#include <stdbool.h>
+#include "buflib.h"
+
+/* All functions below are wrappers for functions in buflib.h, except
+ * they have a predefined context
+ */
+void core_allocator_init(void);
+int core_alloc(const char* name, size_t size);
+int core_alloc_ex(const char* name, size_t size, struct buflib_callbacks *ops);
+int core_alloc_maximum(const char* name, size_t *size, struct buflib_callbacks *ops);
+bool core_shrink(int handle, void* new_start, size_t new_size);
+int core_free(int handle);
+size_t core_available(void);
+
+/* DO NOT ADD wrappers for buflib_buffer_out/in. They do not call
+ * the move callbacks and are therefore unsafe in the core */
+
+#ifdef BUFLIB_DEBUG_BLOCKS
+void core_print_allocs(void (*print)(const char*));
+void core_print_blocks(void (*print)(const char*));
+#endif
+#ifdef BUFLIB_DEBUG_BLOCK_SINGLE
+int  core_get_num_blocks(void);
+void core_print_block_at(int block_num, char* buf, size_t bufsize);
+#endif
+
+static inline void* core_get_data(int handle)
+{
+    extern struct buflib_context core_ctx;
+    return buflib_get_data(&core_ctx, handle);
+}
+#endif /* __CORE_ALLOC_H__ */