summaryrefslogtreecommitdiff
path: root/cesar
diff options
context:
space:
mode:
Diffstat (limited to 'cesar')
-rw-r--r--cesar/lib/Config1
-rw-r--r--cesar/lib/blk.h16
-rw-r--r--cesar/lib/src/blk.c230
3 files changed, 201 insertions, 46 deletions
diff --git a/cesar/lib/Config b/cesar/lib/Config
index f83aa90d75..45bd66cc18 100644
--- a/cesar/lib/Config
+++ b/cesar/lib/Config
@@ -1,6 +1,7 @@
CONFIG_DEBUG = y
CONFIG_DEBUG_MORE = n
CONFIG_DEBUG_FATAL_CATCH = n
+CONFIG_BLK_NB = 1024
CONFIG_HEAP_SKEW = y
CONFIG_HEAP_LEFTIST = n
CONFIG_RND_BUFFER_OPTIMISE = n
diff --git a/cesar/lib/blk.h b/cesar/lib/blk.h
index 2726fe1afd..1f6a186ba0 100644
--- a/cesar/lib/blk.h
+++ b/cesar/lib/blk.h
@@ -30,7 +30,7 @@
* The user can request one or more chained blocks and will be given pointers
* to descriptors. The second one works directly with data, hiding the
* descriptor to the user. In the second flavor, only one block can be
- * requested at a time.
+ * requested at a time, and performances can be lower as usage should be rare.
*
* An extra feature is provided for block allocated without a descriptor:
* automatic destruction. In this case, the descriptor is used to store the
@@ -49,11 +49,8 @@
/** A block descriptor is 16 bytes, that is greater than \c blk_t. */
#define BLK_DESC_SIZE 16
-/** A block descriptor reference counter is 4 bytes. */
-#define BLK_REFCNT_SIZE 4
-
/** Memory block descriptor.
- * This structure store information about a 512 byte memory block. This
+ * This structure stores information about a 512 byte memory block. This
* representation is shared between hardware and software. */
struct blk_t
{
@@ -69,14 +66,19 @@ typedef struct blk_t blk_t;
* \param data pointer to block data
*
* Destructor feature can only be used with block returned without a
- * descriptor as the it is then used internally to store the destructor
- * pointer.
+ * descriptor as it is then used internally to store the destructor pointer.
*/
typedef void (*blk_destructor_t) (void *data);
BEGIN_DECLS
/**
+ * Initialise the block allocator.
+ */
+void
+blk_init (void);
+
+/**
* Return a newly allocated 512 byte block with its descriptor.
* \return the descriptor pointer
*
diff --git a/cesar/lib/src/blk.c b/cesar/lib/src/blk.c
index 069bde958a..01df542f8d 100644
--- a/cesar/lib/src/blk.c
+++ b/cesar/lib/src/blk.c
@@ -10,7 +10,29 @@
* \brief 512 byte memory blocks.
* \ingroup lib
*
- * \todo This is a temporary implementation using malloc and no optimisations.
+ * Implementation
+ * --------------
+ *
+ * Almost everything ought to be aligned on its size. Therefore, descriptors
+ * can not be located near data blocks, and reference counters can not be
+ * located near the descriptors. Instead, the following organisation is used:
+ *
+ * | padding | reference counters | descriptors | data blocks | padding |
+ *
+ * There might be padding at allocation region end because of data blocks
+ * alignment requirement. There might also be padding at allocation region
+ * begin because everything is packed to the region end (there is no padding
+ * between reference counters, descriptors and data blocks).
+ *
+ * At initialisation, every blocks are chained in a simple list. When there
+ * is a allocation need, the requested blocks are extracted from this list.
+ *
+ * Freed blocks are inserted back in the list. This is a LIFO list in order
+ * to minimise page allocation on simulation environment (try to reuse the
+ * same pages instead of dirtying new pages).
+ *
+ * No special optimisation will be done on descriptor-less allocation as this
+ * is a rarely useful case in production code.
*/
#include "common/std.h"
@@ -21,24 +43,54 @@
#include <stdlib.h>
#include <string.h>
-#define REFCNT(blk) ((int *) ((u8 *) (blk) - BLK_REFCNT_SIZE))
-#define TO_BLK(data) ((blk_t *) ((u8 *) (data) + BLK_SIZE + BLK_REFCNT_SIZE))
+#include "config/blk.h"
+
+/** A block descriptor reference counter is 4 bytes. */
+#define BLK_REFCNT_SIZE 4
-/** Structure to accumulate the several actions type on blocks. */
-struct blocks_t
+/** Memory used by a block and its dependencies. */
+#define BLK_TOTAL_SIZE (BLK_SIZE + BLK_DESC_SIZE + BLK_REFCNT_SIZE)
+
+/** Find reference counter from descriptor. */
+#define REFCNT(desc) \
+ ((int *) ((uint) (desc) / (BLK_DESC_SIZE / BLK_REFCNT_SIZE) \
+ + blk_global.desc_to_refcnt_offset))
+
+/** Find descriptor from data. */
+#define DATA_TO_DESC(data) \
+ ((blk_t *) ((uint) (data) / (BLK_SIZE / BLK_DESC_SIZE) \
+ + blk_global.data_to_desc_offset))
+
+/** Block allocator context. */
+struct blk_global_t
{
- /** Incremented when a new blocks has been allocated. */
+ /** Offset to compute reference counter address from descriptor
+ * address. */
+ uint desc_to_refcnt_offset;
+ /** Offset to compute descriptor address from data address. */
+ uint data_to_desc_offset;
+ /** Automatic initialisation depends on this to be initialised to zero by
+ * the compiler. */
+ bool inited;
+ /** Free list head. */
+ blk_t *free_list;
+ /** Allocation region start. */
+ void *start;
+ /** Allocation region stop. */
+ void *stop;
+ /** Number of allocated blocks. */
uint allocated;
- /** Incremented when a block has been freed. */
+ /** Number of freed blocks. */
uint freed;
- /** Incremented when a new reference on a block has been added. */
+ /** Number of added references. */
uint referenced;
- /** Incremented when a release action on a block has been done. */
+ /** Number of released references. */
uint released;
};
-typedef struct blocks_t blocks_t;
+typedef struct blk_global_t blk_global_t;
-blocks_t blocks;
+/** Global context. */
+blk_global_t blk_global;
enum {
/** Magic code used for destructor-less allocations.
@@ -47,6 +99,18 @@ enum {
BLK_OBJ_MAGIC = 0x6f626aa5
};
+/** Block descriptor with two extra words. */
+struct blk_full_t
+{
+ /** Pointer to next descriptor. */
+ struct blk_full_t *next;
+ /** Pointer to data. */
+ u8 *data;
+ /** Two extra words. */
+ u32 w[2];
+};
+typedef struct blk_full_t blk_full_t;
+
/** Block descriptor for descriptor-less allocations. */
struct blk_obj_t
{
@@ -61,19 +125,74 @@ struct blk_obj_t
};
typedef struct blk_obj_t blk_obj_t;
+void
+blk_init (void)
+{
+ /* Allocate memory. */
+ uint size = BLK_TOTAL_SIZE * (CONFIG_BLK_NB + 1);
+ uint base = (uint) malloc (size);
+ if (!base)
+ dbg_fatal ("exhausted virtual memory");
+ uint start = base, stop = base + size;
+ /* Align block, descriptors and reference counters. */
+ stop = stop & ~(BLK_SIZE - 1);
+ uint nb_blks = (stop - start) / BLK_TOTAL_SIZE;
+ start = stop - nb_blks * BLK_TOTAL_SIZE;
+ blk_global.start = (void *) start;
+ blk_global.stop = (void *) stop;
+ /* Determine memory repartition. */
+ base = start;
+ dbg_assert (base % BLK_REFCNT_SIZE == 0);
+ int *refcnts = (void *) base;
+ base = base + BLK_REFCNT_SIZE * nb_blks;
+ dbg_assert (base % BLK_DESC_SIZE == 0);
+ blk_full_t *blks = (void *) base;
+ base = base + BLK_DESC_SIZE * nb_blks;
+ dbg_assert (base % BLK_SIZE == 0);
+ u8 *datas = (void *) base;
+ /* Initialise offsets. */
+ blk_global.desc_to_refcnt_offset =
+ (uint) refcnts - (uint) blks / (BLK_DESC_SIZE / BLK_REFCNT_SIZE);
+ blk_global.data_to_desc_offset =
+ (uint) blks - (uint) datas / (BLK_SIZE / BLK_DESC_SIZE);
+ /* Prepare free list. */
+ uint i;
+ blk_global.free_list = (blk_t *) blks;
+ for (i = 0; i < nb_blks; i++)
+ {
+ *refcnts = 1;
+ blks->next = blks + 1;
+ blks->data = datas;
+ refcnts++;
+ blks++;
+ datas += 512;
+ }
+ blks[-1].next = NULL;
+ dbg_assert ((uint) datas == (uint) blk_global.stop);
+ /* Initialised. */
+ blk_global.inited = true;
+}
+
blk_t *
blk_alloc_desc_ (void_FL)
{
- u8 *data = malloc (BLK_SIZE + BLK_REFCNT_SIZE + BLK_DESC_SIZE);
- if (!data)
- dbg_fatal ("exhausted virtual memory");
- blk_t *blk = TO_BLK (data);
+ /* Initialise block allocator. */
+ if (!blk_global.inited)
+ blk_init ();
+ /* Get a block from free list. */
+ arch_dsr_lock ();
+ blk_t *blk = blk_global.free_list;
+ if (!blk)
+ dbg_fatal ("exhausted block memory");
+ blk_global.free_list = blk->next;
+ arch_dsr_unlock ();
+ /* Prepare block. */
dbg_invalid_ptr (blk->next);
- blk->data = data;
- *REFCNT(blk) = 1;
- blocks.allocated++;
- blocks.referenced++;
+ /* Book keeping. */
+ blk_global.allocated++;
+ blk_global.referenced++;
restrack_create (NULL, blk, _fl_, 1);
+ /* Done. */
return blk;
}
@@ -81,14 +200,35 @@ blk_t *
blk_alloc_desc_range_ (uint n, blk_t **last __FL)
{
blk_t *first, *b;
+ uint i;
dbg_assert (n);
dbg_assert_ptr (last);
- first = b = blk_alloc_desc_ (_fl);
- for (n--; n; n--)
- {
- b->next = blk_alloc_desc_ (_fl);
+ /* Initialise block allocator. */
+ if (!blk_global.inited)
+ blk_init ();
+ /* Get blocks from free list. */
+ arch_dsr_lock ();
+ first = blk_global.free_list;
+ for (b = first, i = n - 1; i && b; i--)
b = b->next;
+ if (!b)
+ dbg_fatal ("exhausted block memory");
+ blk_global.free_list = b->next;
+ arch_dsr_unlock ();
+ /* Prepare last block. */
+ dbg_invalid_ptr (b->next);
+ /* Book keeping. */
+#if CONFIG_RESTRACK
+ {
+ blk_t *p;
+ for (p = first; p != b; p = p->next)
+ restrack_create (NULL, p, _fl_, 1);
+ restrack_create (NULL, p, _fl_, 1);
}
+#endif
+ blk_global.allocated += n;
+ blk_global.referenced += n;
+ /* Done. */
*last = b;
return first;
}
@@ -97,20 +237,29 @@ static void
blk_free_desc_ (blk_t *blk __FL)
{
dbg_assert_ptr (blk);
- dbg_assert (TO_BLK (blk->data) == blk);
+ dbg_assert (DATA_TO_DESC (blk->data) == blk);
+ /* Prepare next allocation. */
+ *REFCNT (blk) = 1;
+ /* Book keeping. */
restrack_destroy (NULL, blk, _fl_, 0);
- blocks.freed++;
- free (blk->data);
+ blk_global.freed++;
+ /* Insert block in free list. */
+ arch_dsr_lock ();
+ blk->next = blk_global.free_list;
+ blk_global.free_list = blk;
+ arch_dsr_unlock ();
}
void
blk_addref_desc_ (blk_t *blk __FL)
{
dbg_assert_ptr (blk);
- dbg_assert (TO_BLK (blk->data) == blk);
+ dbg_assert (DATA_TO_DESC (blk->data) == blk);
+ /* Update reference counter. */
arch_atomic_add (REFCNT (blk), 1);
+ /* Book keeping. */
restrack_update (NULL, blk, _fl_, 1);
- blocks.referenced++;
+ blk_global.referenced++;
}
void
@@ -140,11 +289,13 @@ void
blk_release_desc_ (blk_t *blk __FL)
{
dbg_assert_ptr (blk);
- dbg_assert (TO_BLK (blk->data) == blk);
+ dbg_assert (DATA_TO_DESC (blk->data) == blk);
dbg_assert (((blk_obj_t *) blk)->magic != BLK_OBJ_MAGIC);
dbg_assert (REFCNT (blk) != 0);
+ /* Book keeping. */
restrack_update (NULL, blk, _fl_, -1);
- blocks.released++;
+ blk_global.released++;
+ /* Update reference counter. */
if (arch_atomic_add (REFCNT (blk), -1) == 0)
{
blk_free_desc_ (blk __fl);
@@ -204,7 +355,7 @@ void
blk_addref_ (void *data __FL)
{
dbg_assert_ptr (data);
- blk_t *blk = TO_BLK (data);
+ blk_t *blk = DATA_TO_DESC (data);
dbg_assert (((blk_obj_t *) blk)->magic == BLK_OBJ_MAGIC);
blk_addref_desc_ (blk __fl);
}
@@ -213,11 +364,11 @@ void
blk_release_ (void *data __FL)
{
dbg_assert_ptr (data);
- blk_obj_t *obj = (blk_obj_t *) TO_BLK (data);
+ blk_obj_t *obj = (blk_obj_t *) DATA_TO_DESC (data);
dbg_assert_ptr (obj);
dbg_assert (obj->magic == BLK_OBJ_MAGIC);
restrack_update (NULL, obj, _fl_, -1);
- blocks.released++;
+ blk_global.released++;
if (arch_atomic_add (REFCNT (obj), -1) == 0)
{
if (obj->destructor)
@@ -230,15 +381,16 @@ bool
blk_check_memory (void)
{
return restrack_check ()
- && blocks.allocated == blocks.freed
- && blocks.referenced == blocks.released;
+ && blk_global.allocated == blk_global.freed
+ && blk_global.referenced == blk_global.released;
}
void
blk_print_memory (void)
{
- fprintf (stderr, "[MEM STATE] Allocated : %d\t Freed : %d\t Referenced : %d\t Released : %d\n",
- blocks.allocated, blocks.freed,
- blocks.referenced, blocks.released
- );
+ fprintf (stderr,
+ "blk: allocated: %d, freed: %d, referenced: %d, released: %d\n",
+ blk_global.allocated, blk_global.freed,
+ blk_global.referenced, blk_global.released);
}
+