Module: xenomai-3
Branch: wip/heapmem
Commit: edde4308feb872e4885ff50329c2c9beb56757f4
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=edde4308feb872e4885ff50329c2c9beb56757f4
Author: Philippe Gerum <r...@xenomai.org>
Date: Sun May 13 19:00:50 2018 +0200
cobalt/heap: rebase on HEAPMEM algorithm
Address the issue mentioned in [1] regarding the core (xnheap)
allocator, using a variant of the McKusick scheme significantly
improving the performance figures.
As a by-product of this overhaul, the core allocator can now manage
heaps up to (4GB - PAGE_SIZE).
The performance report log obtained by testing on imx6qp
is as follows:
== memcheck started
seq_heap_size=2048k
random_alloc_rounds=1024
pattern_heap_size=128k
pattern_check_rounds=128
[SEQUENTIAL ALLOC->FREE, ^2 BLOCK SIZES] ON 'xnheap'
HEAPSZ test heap size
BLOCKSZ tested block size
NRBLKS number of blocks allocatable in heap
AVG-A average time to allocate block (us)
AVG-F average time to free block (us)
MAX-A max time to allocate block (us)
MAX-F max time to free block (us)
FLAGS +shuffle: randomized free
+realloc: measure after initial alloc/free pass (hot heap)
sorted by: max alloc time
HEAPSZ BLOCKSZ NRBLKS AVG-A AVG-F MAX-A MAX-F FLAGS
1024k 32 32768 0 0 8 6
1024k 32 32768 0 0 7 2 +shuffle +realloc
1024k 16 65536 0 0 7 2 +realloc
1024k 16 65536 0 0 6 7 +shuffle +realloc
... (364 results following) ...
sorted by: max free time
HEAPSZ BLOCKSZ NRBLKS AVG-A AVG-F MAX-A MAX-F FLAGS
1024k 128 8192 0 1 2 8
1024k 16 65536 0 0 6 7 +shuffle +realloc
1024k 32 32768 0 0 8 6
512k 32 16384 0 0 5 6 +realloc
... (364 results following) ...
overall:
worst alloc time: 8 (us)
worst free time: 8 (us)
average of max. alloc times: 1 (us)
average of max. free times: 2 (us)
average alloc time: 1 (us)
average free time: 1 (us)
[SEQUENTIAL ALLOC->FREE, RANDOM BLOCK SIZES] ON 'xnheap'
HEAPSZ test heap size
BLOCKSZ tested block size
NRBLKS number of blocks allocatable in heap
AVG-A average time to allocate block (us)
AVG-F average time to free block (us)
MAX-A max time to allocate block (us)
MAX-F max time to free block (us)
FLAGS +shuffle: randomized free
+realloc: measure after initial alloc/free pass (hot heap)
sorted by: max alloc time
HEAPSZ BLOCKSZ NRBLKS AVG-A AVG-F MAX-A MAX-F FLAGS
512k 17k 28 1 1 8 2 +shuffle
512k 45k 11 1 1 7 2
1024k 24 32768 0 0 7 6 +shuffle
128k 820 128 1 1 6 2 +shuffle
... (32764 results following) ...
sorted by: max free time
HEAPSZ BLOCKSZ NRBLKS AVG-A AVG-F MAX-A MAX-F FLAGS
1024k 3k 292 1 1 1 8 +shuffle
256k 174 1024 1 1 1 6 +shuffle
1024k 24 32768 0 0 7 6 +shuffle
32k 12k 2 2 3 1 5
... (32764 results following) ...
overall:
worst alloc time: 8 (us)
worst free time: 8 (us)
average of max. alloc times: 1 (us)
average of max. free times: 1 (us)
average alloc time: 1 (us)
average free time: 1 (us)
[1] http://www.xenomai.org/pipermail/xenomai/2018-April/038883.html
---
include/cobalt/kernel/heap.h | 168 ++++----
kernel/cobalt/Kconfig | 7 +
kernel/cobalt/heap.c | 979 +++++++++++++++++++++++++-----------------
3 files changed, 662 insertions(+), 492 deletions(-)
diff --git a/include/cobalt/kernel/heap.h b/include/cobalt/kernel/heap.h
index d89f25d..4f95c80 100644
--- a/include/cobalt/kernel/heap.h
+++ b/include/cobalt/kernel/heap.h
@@ -20,6 +20,7 @@
#define _COBALT_KERNEL_HEAP_H
#include <linux/string.h>
+#include <linux/rbtree.h>
#include <cobalt/kernel/lock.h>
#include <cobalt/kernel/list.h>
#include <cobalt/uapi/kernel/types.h>
@@ -28,66 +29,66 @@
/**
* @addtogroup cobalt_core_heap
* @{
- *
- * @par Implementation constraints
- *
- * - Minimum page size is 2 ** XNHEAP_MINLOG2 (must be large enough to
- * hold a pointer).
- *
- * - Maximum page size is 2 ** XNHEAP_MAXLOG2.
- *
- * - Requested block size is rounded up to XNHEAP_MINLOG2.
- *
- * - Requested block size larger than 2 times the XNHEAP_PAGESZ is
- * rounded up to the next page boundary and obtained from the free
- * page list. So we need a bucket for each power of two between
- * XNHEAP_MINLOG2 and XNHEAP_MAXLOG2 inclusive, plus one to honor
- * requests ranging from the maximum page size to twice this size.
*/
-#define XNHEAP_PAGESZ PAGE_SIZE
-#define XNHEAP_MINLOG2 3
-#define XNHEAP_MAXLOG2 22 /* Holds pagemap.bcount blocks */
-#define XNHEAP_MINALLOCSZ (1 << XNHEAP_MINLOG2)
-#define XNHEAP_MINALIGNSZ (1 << 4) /* i.e. 16 bytes */
-#define XNHEAP_NBUCKETS (XNHEAP_MAXLOG2 - XNHEAP_MINLOG2 + 2)
-#define XNHEAP_MAXHEAPSZ (1 << 31) /* i.e. 2Gb */
-
-#define XNHEAP_PFREE 0
-#define XNHEAP_PCONT 1
-#define XNHEAP_PLIST 2
-
-struct xnpagemap {
- /** PFREE, PCONT, PLIST or log2 */
- u32 type : 8;
- /** Number of active blocks */
- u32 bcount : 24;
+
+#define XNHEAP_PAGE_SHIFT 9 /* 2^9 => 512 bytes */
+#define XNHEAP_PAGE_SIZE (1UL << XNHEAP_PAGE_SHIFT)
+#define XNHEAP_PAGE_MASK (~(XNHEAP_PAGE_SIZE - 1))
+#define XNHEAP_MIN_LOG2 4 /* 16 bytes */
+/*
+ * Use bucketed memory for sizes between 2^XNHEAP_MIN_LOG2 and
+ * 2^(XNHEAP_PAGE_SHIFT-1).
+ */
+#define XNHEAP_MAX_BUCKETS (XNHEAP_PAGE_SHIFT - XNHEAP_MIN_LOG2)
+#define XNHEAP_MIN_ALIGN (1U << XNHEAP_MIN_LOG2)
+/* Maximum size of a heap (4Gb - PAGE_SIZE). */
+#define XNHEAP_MAX_HEAPSZ (4294967295U - PAGE_SIZE + 1)
+/* Bits we need for encoding a page # */
+#define XNHEAP_PGENT_BITS (32 - XNHEAP_PAGE_SHIFT)
+/* Each page is represented by a page map entry. */
+#define XNHEAP_PGMAP_BYTES sizeof(struct xnheap_pgentry)
+
+struct xnheap_pgentry {
+ /* Linkage in bucket list. */
+ unsigned int prev : XNHEAP_PGENT_BITS;
+ unsigned int next : XNHEAP_PGENT_BITS;
+ /* page_list or log2. */
+ unsigned int type : 6;
+ /*
+ * We hold either a spatial map of busy blocks within the page
+ * for bucketed memory (up to 32 blocks per page), or the
+ * overall size of the multi-page block if entry.type ==
+ * page_list.
+ */
+ union {
+ u32 map;
+ u32 bsize;
+ };
+};
+
+/*
+ * A range descriptor is stored at the beginning of the first page of
+ * a range of free pages. xnheap_range.size is nrpages *
+ * XNHEAP_PAGE_SIZE. Ranges are indexed by address and size in
+ * rbtrees.
+ */
+struct xnheap_range {
+ struct rb_node addr_node;
+ struct rb_node size_node;
+ size_t size;
};
struct xnheap {
- /** SMP lock */
+ void *membase;
+ struct rb_root addr_tree;
+ struct rb_root size_tree;
+ struct xnheap_pgentry *pagemap;
+ size_t usable_size;
+ size_t used_size;
+ u32 buckets[XNHEAP_MAX_BUCKETS];
+ char name[XNOBJECT_NAME_LEN];
DECLARE_XNLOCK(lock);
- /** Base address of the page array */
- caddr_t membase;
- /** Memory limit of page array */
- caddr_t memlim;
- /** Number of pages in the freelist */
- int npages;
- /** Head of the free page list */
- caddr_t freelist;
- /** Address of the page map */
- struct xnpagemap *pagemap;
- /** Link to heapq */
struct list_head next;
- /** log2 bucket list */
- struct xnbucket {
- caddr_t freelist;
- int fcount;
- } buckets[XNHEAP_NBUCKETS];
- char name[XNOBJECT_NAME_LEN];
- /** Size of storage area */
- u32 size;
- /** Used/busy storage size */
- u32 used;
};
extern struct xnheap cobalt_heap;
@@ -95,59 +96,42 @@ extern struct xnheap cobalt_heap;
#define xnmalloc(size) xnheap_alloc(&cobalt_heap, size)
#define xnfree(ptr) xnheap_free(&cobalt_heap, ptr)
-static inline u32 xnheap_get_size(const struct xnheap *heap)
-{
- return heap->size;
-}
-
-static inline u32 xnheap_get_free(const struct xnheap *heap)
-{
- return heap->size - heap->used;
-}
-
static inline void *xnheap_get_membase(const struct xnheap *heap)
{
return heap->membase;
}
-static inline u32 xnheap_rounded_size(u32 size)
+static inline
+size_t xnheap_get_size(const struct xnheap *heap)
{
- if (size < 2 * XNHEAP_PAGESZ)
- return 2 * XNHEAP_PAGESZ;
-
- return ALIGN(size, XNHEAP_PAGESZ);
+ return heap->usable_size;
}
-/* Private interface. */
+static inline
+size_t xnheap_get_free(const struct xnheap *heap)
+{
+ return heap->usable_size - heap->used_size;
+}
-#ifdef CONFIG_XENO_OPT_VFILE
-void xnheap_init_proc(void);
-void xnheap_cleanup_proc(void);
-#else /* !CONFIG_XENO_OPT_VFILE */
-static inline void xnheap_init_proc(void) { }
-static inline void xnheap_cleanup_proc(void) { }
-#endif /* !CONFIG_XENO_OPT_VFILE */
+int xnheap_init(struct xnheap *heap,
+ void *membase, size_t size);
-/* Public interface. */
+void xnheap_destroy(struct xnheap *heap);
-void *xnheap_vmalloc(size_t size);
+void *xnheap_alloc(struct xnheap *heap, size_t size);
-void xnheap_vfree(void *p);
+void xnheap_free(struct xnheap *heap, void *block);
-int xnheap_init(struct xnheap *heap, void *membase, u32 size);
+int xnheap_check_block(struct xnheap *heap, void *block);
void xnheap_set_name(struct xnheap *heap,
const char *name, ...);
-void xnheap_destroy(struct xnheap *heap);
-
-void *xnheap_alloc(struct xnheap *heap, u32 size);
-
-void xnheap_free(struct xnheap *heap, void *block);
+void *xnheap_vmalloc(size_t size);
-int xnheap_check_block(struct xnheap *heap, void *block);
+void xnheap_vfree(void *p);
-static inline void *xnheap_zalloc(struct xnheap *heap, u32 size)
+static inline void *xnheap_zalloc(struct xnheap *heap, size_t size)
{
void *p;
@@ -169,6 +153,14 @@ static inline char *xnstrdup(const char *s)
return strcpy(p, s);
}
+#ifdef CONFIG_XENO_OPT_VFILE
+void xnheap_init_proc(void);
+void xnheap_cleanup_proc(void);
+#else /* !CONFIG_XENO_OPT_VFILE */
+static inline void xnheap_init_proc(void) { }
+static inline void xnheap_cleanup_proc(void) { }
+#endif /* !CONFIG_XENO_OPT_VFILE */
+
/** @} */
#endif /* !_COBALT_KERNEL_HEAP_H */
diff --git a/kernel/cobalt/Kconfig b/kernel/cobalt/Kconfig
index 231a1ad..16602a7 100644
--- a/kernel/cobalt/Kconfig
+++ b/kernel/cobalt/Kconfig
@@ -364,6 +364,13 @@ config XENO_OPT_DEBUG_COBALT
This option activates various assertions inside the Cobalt
kernel. This option has limited overhead.
+config XENO_OPT_DEBUG_MEMORY
+ bool "Cobalt memory checks"
+ help
+ This option enables memory debug checks inside the Cobalt
+ kernel. This option may induce significant overhead with large
+ heaps.
+
config XENO_OPT_DEBUG_CONTEXT
bool "Check for calling context"
help
diff --git a/kernel/cobalt/heap.c b/kernel/cobalt/heap.c
index 5aacc9a..dfba370 100644
--- a/kernel/cobalt/heap.c
+++ b/kernel/cobalt/heap.c
@@ -21,7 +21,8 @@
#include <linux/slab.h>
#include <linux/kernel.h>
#include <linux/log2.h>
-#include <linux/kconfig.h>
+#include <linux/bitops.h>
+#include <linux/mm.h>
#include <asm/pgtable.h>
#include <cobalt/kernel/assert.h>
#include <cobalt/kernel/heap.h>
@@ -31,12 +32,13 @@
* @ingroup cobalt_core
* @defgroup cobalt_core_heap Dynamic memory allocation services
*
- * The implementation of the memory allocator follows the algorithm
- * described in a USENIX 1988 paper called "Design of a General
- * Purpose Memory Allocator for the 4.3BSD Unix Kernel" by Marshall
- * K. McKusick and Michael J. Karels. You can find it at various
- * locations on the net, including
- * http://docs.FreeBSD.org/44doc/papers/kernmalloc.pdf.
+ * This code implements a variant of the allocator described in
+ * "Design of a General Purpose Memory Allocator for the 4.3BSD Unix
+ * Kernel" by Marshall K. McKusick and Michael J. Karels (USENIX
+ * 1988), see http://docs.FreeBSD.org/44doc/papers/kernmalloc.pdf.
+ * The free page list is maintained in rbtrees for fast lookups of
+ * multi-page memory ranges, and pages holding bucketed memory have a
+ * fast allocation bitmap to manage their blocks internally.
*@{
*/
struct xnheap cobalt_heap; /* System heap */
@@ -139,250 +141,378 @@ void xnheap_cleanup_proc(void)
#endif /* CONFIG_XENO_OPT_VFILE */
-static void init_freelist(struct xnheap *heap)
+enum xnheap_pgtype {
+ page_free =0,
+ page_cont =1,
+ page_list =2
+};
+
+static inline u32 __always_inline
+gen_block_mask(int log2size)
{
- caddr_t freepage;
- int n, lastpgnum;
-
- heap->used = 0;
- memset(heap->buckets, 0, sizeof(heap->buckets));
- lastpgnum = heap->npages - 1;
-
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = heap->membase;
- n < lastpgnum; n++, freepage += XNHEAP_PAGESZ) {
- *((caddr_t *)freepage) = freepage + XNHEAP_PAGESZ;
- heap->pagemap[n].type = XNHEAP_PFREE;
- heap->pagemap[n].bcount = 0;
- }
+ return -1U >> (32 - (XNHEAP_PAGE_SIZE >> log2size));
+}
- *((caddr_t *) freepage) = NULL;
- heap->pagemap[lastpgnum].type = XNHEAP_PFREE;
- heap->pagemap[lastpgnum].bcount = 0;
- heap->memlim = freepage + XNHEAP_PAGESZ;
+static inline __always_inline
+int addr_to_pagenr(struct xnheap *heap, void *p)
+{
+ return ((void *)p - heap->membase) >> XNHEAP_PAGE_SHIFT;
+}
- /* The first page starts the free list. */
- heap->freelist = heap->membase;
+static inline __always_inline
+void *pagenr_to_addr(struct xnheap *heap, int pg)
+{
+ return heap->membase + (pg << XNHEAP_PAGE_SHIFT);
}
-/**
- * @fn xnheap_init(struct xnheap *heap, void *membase, u32 size)
- * @brief Initialize a memory heap.
- *
- * Initializes a memory heap suitable for time-bounded allocation
- * requests of dynamic memory.
- *
- * @param heap The address of a heap descriptor to initialize.
- *
- * @param membase The address of the storage area.
- *
- * @param size The size in bytes of the storage area. @a size
- * must be a multiple of PAGE_SIZE and smaller than 2 Gb in the
- * current implementation.
- *
- * @return 0 is returned upon success, or:
- *
- * - -EINVAL is returned if @a size is either:
- *
- * - not aligned on PAGE_SIZE
- * - smaller than 2 * PAGE_SIZE
- * - greater than 2 Gb (XNHEAP_MAXHEAPSZ)
- *
- * - -ENOMEM is returned upon failure of allocating the meta-data area
- * used internally to maintain the heap.
- *
- * @coretags{secondary-only}
+#ifdef CONFIG_XENO_OPT_DEBUG_MEMORY
+/*
+ * Setting page_cont/page_free in the page map is only required for
+ * enabling full checking of the block address in free requests, which
+ * may be extremely time-consuming when deallocating huge blocks
+ * spanning thousands of pages. We only do such marking when running
+ * in memory debug mode.
*/
-int xnheap_init(struct xnheap *heap, void *membase, u32 size)
+static inline bool
+page_is_valid(struct xnheap *heap, int pg)
{
- spl_t s;
+ switch (heap->pagemap[pg].type) {
+ case page_free:
+ case page_cont:
+ return false;
+ case page_list:
+ default:
+ return true;
+ }
+}
- secondary_mode_only();
+static void mark_pages(struct xnheap *heap,
+ int pg, int nrpages,
+ enum xnheap_pgtype type)
+{
+ while (nrpages-- > 0)
+ heap->pagemap[pg].type = type;
+}
- /*
- * HEAPSIZE must be aligned on XNHEAP_PAGESZ.
- * HEAPSIZE must be lower than XNHEAP_MAXHEAPSZ.
- */
- if (size > XNHEAP_MAXHEAPSZ ||
- !IS_ALIGNED(size, XNHEAP_PAGESZ))
- return -EINVAL;
+#else
- /*
- * We need to reserve 4 bytes in a page map for each page
- * which is addressable into the storage area. pmapsize =
- * (size / XNHEAP_PAGESZ) * sizeof(struct xnpagemap).
- */
- heap->size = size;
- heap->membase = membase;
- heap->npages = size / XNHEAP_PAGESZ;
- /*
- * The heap must contain at least two addressable pages to
- * cope with allocation sizes between XNHEAP_PAGESZ and 2 *
- * XNHEAP_PAGESZ.
- */
- if (heap->npages < 2)
- return -EINVAL;
+static inline bool
+page_is_valid(struct xnheap *heap, int pg)
+{
+ return true;
+}
- heap->pagemap = kmalloc(sizeof(struct xnpagemap) * heap->npages,
- GFP_KERNEL);
- if (heap->pagemap == NULL)
- return -ENOMEM;
+static void mark_pages(struct xnheap *heap,
+ int pg, int nrpages,
+ enum xnheap_pgtype type)
+{ }
- xnlock_init(&heap->lock);
- init_freelist(heap);
+#endif
- /* Default name, override with xnheap_set_name() */
- ksformat(heap->name, sizeof(heap->name), "(%p)", heap);
+static struct xnheap_range *
+search_size_ge(struct rb_root *t, size_t size)
+{
+ struct rb_node *rb, *deepest = NULL;
+ struct xnheap_range *r;
+
+ /*
+ * We first try to find an exact match. If that fails, we walk
+ * the tree in logical order by increasing size value from the
+ * deepest node traversed until we find the first successor to
+ * that node, or nothing beyond it, whichever comes first.
+ */
+ rb = t->rb_node;
+ while (rb) {
+ deepest = rb;
+ r = rb_entry(rb, struct xnheap_range, size_node);
+ if (size < r->size) {
+ rb = rb->rb_left;
+ continue;
+ }
+ if (size > r->size) {
+ rb = rb->rb_right;
+ continue;
+ }
+ return r;
+ }
- xnlock_get_irqsave(&nklock, s);
- list_add_tail(&heap->next, &heapq);
- nrheaps++;
- xnvfile_touch_tag(&vfile_tag);
- xnlock_put_irqrestore(&nklock, s);
+ rb = deepest;
+ while (rb) {
+ r = rb_entry(rb, struct xnheap_range, size_node);
+ if (size <= r->size)
+ return r;
+ rb = rb_next(rb);
+ }
- return 0;
+ return NULL;
}
-EXPORT_SYMBOL_GPL(xnheap_init);
-/**
- * @fn void xnheap_destroy(struct xnheap *heap)
- * @brief Destroys a memory heap.
- *
- * Destroys a memory heap.
- *
- * @param heap The heap descriptor.
- *
- * @coretags{secondary-only}
- */
-void xnheap_destroy(struct xnheap *heap)
+static struct xnheap_range *
+search_left_mergeable(struct xnheap *heap, struct xnheap_range *r)
{
- spl_t s;
+ struct rb_node *node = heap->addr_tree.rb_node;
+ struct xnheap_range *p;
+
+ while (node) {
+ p = rb_entry(node, struct xnheap_range, addr_node);
+ if ((void *)p + p->size == (void *)r)
+ return p;
+ if (&r->addr_node < node)
+ node = node->rb_left;
+ else
+ node = node->rb_right;
+ }
- secondary_mode_only();
+ return NULL;
+}
- xnlock_get_irqsave(&nklock, s);
- list_del(&heap->next);
- nrheaps--;
- xnvfile_touch_tag(&vfile_tag);
- xnlock_put_irqrestore(&nklock, s);
- kfree(heap->pagemap);
+static struct xnheap_range *
+search_right_mergeable(struct xnheap *heap, struct xnheap_range *r)
+{
+ struct rb_node *node = heap->addr_tree.rb_node;
+ struct xnheap_range *p;
+
+ while (node) {
+ p = rb_entry(node, struct xnheap_range, addr_node);
+ if ((void *)r + r->size == (void *)p)
+ return p;
+ if (&r->addr_node < node)
+ node = node->rb_left;
+ else
+ node = node->rb_right;
+ }
+
+ return NULL;
}
-EXPORT_SYMBOL_GPL(xnheap_destroy);
-/**
- * @fn xnheap_set_name(struct xnheap *heap,const char *name,...)
- * @brief Set the heap's name string.
- *
- * Set the heap name that will be used in statistic outputs.
- *
- * @param heap The address of a heap descriptor.
- *
- * @param name Name displayed in statistic outputs. This parameter can
- * be a printk()-like format argument list.
- *
- * @coretags{task-unrestricted}
- */
-void xnheap_set_name(struct xnheap *heap, const char *name, ...)
+static void insert_range_bysize(struct xnheap *heap, struct xnheap_range *r)
{
- va_list args;
+ struct rb_node **new = &heap->size_tree.rb_node, *parent = NULL;
+ struct xnheap_range *p;
+
+ while (*new) {
+ p = container_of(*new, struct xnheap_range, size_node);
+ parent = *new;
+ if (r->size <= p->size)
+ new = &((*new)->rb_left);
+ else
+ new = &((*new)->rb_right);
+ }
+
+ rb_link_node(&r->size_node, parent, new);
+ rb_insert_color(&r->size_node, &heap->size_tree);
+}
- va_start(args, name);
- kvsformat(heap->name, sizeof(heap->name), name, args);
- va_end(args);
+static void insert_range_byaddr(struct xnheap *heap, struct xnheap_range *r)
+{
+ struct rb_node **new = &heap->addr_tree.rb_node, *parent = NULL;
+ struct xnheap_range *p;
+
+ while (*new) {
+ p = container_of(*new, struct xnheap_range, addr_node);
+ parent = *new;
+ if (r < p)
+ new = &((*new)->rb_left);
+ else
+ new = &((*new)->rb_right);
+ }
+
+ rb_link_node(&r->addr_node, parent, new);
+ rb_insert_color(&r->addr_node, &heap->addr_tree);
}
-EXPORT_SYMBOL_GPL(xnheap_set_name);
-/*
- * get_free_range() -- Obtain a range of contiguous free pages to
- * fulfill an allocation of 2 ** log2size. The caller must have
- * acquired the heap lock.
- */
+static int reserve_page_range(struct xnheap *heap, size_t size)
+{
+ struct xnheap_range *new, *splitr;
+
+ /* Find a suitable range of pages covering 'size'. */
+ new = search_size_ge(&heap->size_tree, size);
+ if (new == NULL)
+ return -1;
+
+ rb_erase(&new->size_node, &heap->size_tree);
+ if (new->size == size) {
+ rb_erase(&new->addr_node, &heap->addr_tree);
+ return addr_to_pagenr(heap, new);
+ }
-static caddr_t get_free_range(struct xnheap *heap, u32 bsize, int log2size)
+ /*
+ * The free range fetched is larger than what we need: split
+ * it in two, the upper part is returned to the caller, the
+ * lower part is sent back to the free list, which makes
+ * reindexing by address pointless.
+ */
+ splitr = new;
+ splitr->size -= size;
+ new = (struct xnheap_range *)((void *)new + splitr->size);
+ insert_range_bysize(heap, splitr);
+
+ return addr_to_pagenr(heap, new);
+}
+
+static void release_page_range(struct xnheap *heap,
+ void *page, size_t size)
{
- caddr_t block, eblock, freepage, lastpage, headpage, freehead = NULL;
- u32 pagenum, pagecont, freecont;
+ struct xnheap_range *freed = page, *left, *right;
+ bool addr_linked = false;
- freepage = heap->freelist;
- while (freepage) {
- headpage = freepage;
- freecont = 0;
- /*
- * Search for a range of contiguous pages in the free
- * page list. The range must be 'bsize' long.
- */
- do {
- lastpage = freepage;
- freepage = *((caddr_t *) freepage);
- freecont += XNHEAP_PAGESZ;
- }
- while (freepage == lastpage + XNHEAP_PAGESZ &&
- freecont < bsize);
+ freed->size = size;
- if (freecont >= bsize) {
- /*
- * Ok, got it. Just update the free page list,
- * then proceed to the next step.
- */
- if (headpage == heap->freelist)
- heap->freelist = *((caddr_t *)lastpage);
- else
- *((caddr_t *)freehead) = *((caddr_t *)lastpage);
+ left = search_left_mergeable(heap, freed);
+ if (left) {
+ rb_erase(&left->size_node, &heap->size_tree);
+ left->size += freed->size;
+ freed = left;
+ addr_linked = true;
+ }
- goto splitpage;
- }
- freehead = lastpage;
+ right = search_right_mergeable(heap, freed);
+ if (right) {
+ rb_erase(&right->size_node, &heap->size_tree);
+ freed->size += right->size;
+ if (addr_linked)
+ rb_erase(&right->addr_node, &heap->addr_tree);
+ else
+ rb_replace_node(&right->addr_node, &freed->addr_node,
+ &heap->addr_tree);
+ } else if (!addr_linked)
+ insert_range_byaddr(heap, freed);
+
+ insert_range_bysize(heap, freed);
+ mark_pages(heap, addr_to_pagenr(heap, page),
+ size >> XNHEAP_PAGE_SHIFT, page_free);
+}
+
+static void add_page_front(struct xnheap *heap,
+ int pg, int log2size)
+{
+ struct xnheap_pgentry *new, *head, *next;
+ int ilog;
+
+ /* Insert page at front of the per-bucket page list. */
+
+ ilog = log2size - XNHEAP_MIN_LOG2;
+ new = &heap->pagemap[pg];
+ if (heap->buckets[ilog] == -1U) {
+ heap->buckets[ilog] = pg;
+ new->prev = new->next = pg;
+ } else {
+ head = &heap->pagemap[heap->buckets[ilog]];
+ new->prev = heap->buckets[ilog];
+ new->next = head->next;
+ next = &heap->pagemap[new->next];
+ next->prev = pg;
+ head->next = pg;
+ heap->buckets[ilog] = pg;
}
+}
- return NULL;
+static void remove_page(struct xnheap *heap,
+ int pg, int log2size)
+{
+ struct xnheap_pgentry *old, *prev, *next;
+ int ilog = log2size - XNHEAP_MIN_LOG2;
+
+ /* Remove page from the per-bucket page list. */
+
+ old = &heap->pagemap[pg];
+ if (pg == old->next)
+ heap->buckets[ilog] = -1U;
+ else {
+ if (pg == heap->buckets[ilog])
+ heap->buckets[ilog] = old->next;
+ prev = &heap->pagemap[old->prev];
+ prev->next = old->next;
+ next = &heap->pagemap[old->next];
+ next->prev = old->prev;
+ }
+}
-splitpage:
+static void move_page_front(struct xnheap *heap,
+ int pg, int log2size)
+{
+ int ilog = log2size - XNHEAP_MIN_LOG2;
+
+ /* Move page at front of the per-bucket page list. */
+
+ if (heap->buckets[ilog] == pg)
+ return; /* Already at front, no move. */
+
+ remove_page(heap, pg, log2size);
+ add_page_front(heap, pg, log2size);
+}
- /*
- * At this point, headpage is valid and points to the first
- * page of a range of contiguous free pages larger or equal
- * than 'bsize'.
- */
- if (bsize < XNHEAP_PAGESZ) {
- /*
- * If the allocation size is smaller than the page
- * size, split the page in smaller blocks of this
- * size, building a free list of free blocks.
- */
- for (block = headpage, eblock =
- headpage + XNHEAP_PAGESZ - bsize; block < eblock;
- block += bsize)
- *((caddr_t *)block) = block + bsize;
+static void move_page_back(struct xnheap *heap,
+ int pg, int log2size)
+{
+ struct xnheap_pgentry *old, *last, *head, *next;
+ int ilog;
- *((caddr_t *)eblock) = NULL;
- } else
- *((caddr_t *)headpage) = NULL;
+ /* Move page at end of the per-bucket page list. */
+
+ old = &heap->pagemap[pg];
+ if (pg == old->next) /* Singleton, no move. */
+ return;
+
+ remove_page(heap, pg, log2size);
+
+ ilog = log2size - XNHEAP_MIN_LOG2;
+ head = &heap->pagemap[heap->buckets[ilog]];
+ last = &heap->pagemap[head->prev];
+ old->prev = head->prev;
+ old->next = last->next;
+ next = &heap->pagemap[old->next];
+ next->prev = pg;
+ last->next = pg;
+}
- pagenum = (headpage - heap->membase) / XNHEAP_PAGESZ;
+static void *add_free_range(struct xnheap *heap,
+ size_t bsize, int log2size)
+{
+ int pg;
+ pg = reserve_page_range(heap, ALIGN(bsize, XNHEAP_PAGE_SIZE));
+ if (pg < 0)
+ return NULL;
+
/*
- * Update the page map. If log2size is non-zero (i.e. bsize
- * <= 2 * pagesize), store it in the first page's slot to
- * record the exact block size (which is a power of
- * two). Otherwise, store the special marker XNHEAP_PLIST,
- * indicating the start of a block whose size is a multiple of
- * the standard page size, but not necessarily a power of two.
- * In any case, the following pages slots are marked as
- * 'continued' (PCONT).
+ * Update the page entry. If @log2size is non-zero
+ * (i.e. bsize < XNHEAP_PAGE_SIZE), bsize is (1 << log2Size)
+ * between 2^XNHEAP_MIN_LOG2 and 2^(XNHEAP_PAGE_SHIFT - 1).
+ * Save the log2 power into entry.type, then update the
+ * per-page allocation bitmap to reserve the first block.
+ *
+ * Otherwise, we have a larger block which may span multiple
+ * pages: set entry.type to page_list, indicating the start of
+ * the page range, and entry.bsize to the overall block size.
*/
- heap->pagemap[pagenum].type = log2size ? : XNHEAP_PLIST;
- heap->pagemap[pagenum].bcount = 1;
-
- for (pagecont = bsize / XNHEAP_PAGESZ; pagecont > 1; pagecont--) {
- heap->pagemap[pagenum + pagecont - 1].type = XNHEAP_PCONT;
- heap->pagemap[pagenum + pagecont - 1].bcount = 0;
+ if (log2size) {
+ heap->pagemap[pg].type = log2size;
+ /*
+ * Mark the first object slot (#0) as busy, along with
+ * the leftmost bits we won't use for this log2 size.
+ */
+ heap->pagemap[pg].map = ~gen_block_mask(log2size) | 1;
+ /*
+ * Insert the new page at front of the per-bucket page
+ * list, enforcing the assumption that pages with free
+ * space live close to the head of this list.
+ */
+ add_page_front(heap, pg, log2size);
+ } else {
+ heap->pagemap[pg].type = page_list;
+ heap->pagemap[pg].bsize = (u32)bsize;
+ mark_pages(heap, pg + 1,
+ (bsize >> XNHEAP_PAGE_SHIFT) - 1, page_cont);
}
- return headpage;
+ heap->used_size += bsize;
+
+ return pagenr_to_addr(heap, pg);
}
/**
- * @fn void *xnheap_alloc(struct xnheap *heap, u32 size)
+ * @fn void *xnheap_alloc(struct xnheap *heap, size_t size)
* @brief Allocate a memory block from a memory heap.
*
* Allocates a contiguous region of memory from an active memory heap.
@@ -390,92 +520,85 @@ splitpage:
*
* @param heap The descriptor address of the heap to get memory from.
*
- * @param size The size in bytes of the requested block. Sizes lower
- * or equal to the page size are rounded either to the minimum
- * allocation size if lower than this value, or to the minimum
- * alignment size if greater or equal to this value. In the current
- * implementation, with MINALLOC = 8 and MINALIGN = 16, a 7 bytes
- * request will be rounded to 8 bytes, and a 17 bytes request will be
- * rounded to 32.
+ * @param size The size in bytes of the requested block.
*
* @return The address of the allocated region upon success, or NULL
* if no memory is available from the specified heap.
*
* @coretags{unrestricted}
*/
-void *xnheap_alloc(struct xnheap *heap, u32 size)
+void *xnheap_alloc(struct xnheap *heap, size_t size)
{
- u32 pagenum, bsize;
- int log2size, ilog;
- caddr_t block;
+ int log2size, ilog, pg, b = -1;
+ size_t bsize;
+ void *block;
spl_t s;
if (size == 0)
return NULL;
+ if (size < XNHEAP_MIN_ALIGN) {
+ bsize = size = XNHEAP_MIN_ALIGN;
+ log2size = XNHEAP_MIN_LOG2;
+ } else {
+ log2size = ilog2(size);
+ if (log2size < XNHEAP_PAGE_SHIFT) {
+ if (size & (size - 1))
+ log2size++;
+ bsize = 1 << log2size;
+ } else
+ bsize = ALIGN(size, XNHEAP_PAGE_SIZE);
+ }
+
/*
- * Sizes lower or equal to the page size are rounded either to
- * the minimum allocation size if lower than this value, or to
- * the minimum alignment size if greater or equal to this
- * value.
+ * Allocate entire pages directly from the pool whenever the
+ * block is larger or equal to XNHEAP_PAGE_SIZE. Otherwise,
+ * use bucketed memory.
+ *
+ * NOTE: Fully busy pages from bucketed memory are moved back
+ * at the end of the per-bucket page list, so that we may
+ * always assume that either the heading page has some room
+ * available, or no room is available from any page linked to
+ * this list, in which case we should immediately add a fresh
+ * page.
*/
- if (size > XNHEAP_PAGESZ)
- size = ALIGN(size, XNHEAP_PAGESZ);
- else if (size <= XNHEAP_MINALIGNSZ)
- size = ALIGN(size, XNHEAP_MINALLOCSZ);
- else
- size = ALIGN(size, XNHEAP_MINALIGNSZ);
+ xnlock_get_irqsave(&heap->lock, s);
- /*
- * It is more space efficient to directly allocate pages from
- * the free page list whenever the requested size is greater
- * than 2 times the page size. Otherwise, use the bucketed
- * memory blocks.
- */
- if (likely(size <= XNHEAP_PAGESZ * 2)) {
+ if (bsize >= XNHEAP_PAGE_SIZE)
+ /* Add a range of contiguous free pages. */
+ block = add_free_range(heap, bsize, 0);
+ else {
+ ilog = log2size - XNHEAP_MIN_LOG2;
+ XENO_WARN_ON(MEMORY, ilog < 0 || ilog >= XNHEAP_MAX_BUCKETS);
+ pg = heap->buckets[ilog];
/*
- * Find the first power of two greater or equal to the
- * rounded size.
+ * Find a block in the heading page if any. If there
+ * is none, there won't be any down the list: add a
+ * new page right away.
*/
- bsize = size < XNHEAP_MINALLOCSZ ? XNHEAP_MINALLOCSZ : size;
- log2size = order_base_2(bsize);
- bsize = 1 << log2size;
- ilog = log2size - XNHEAP_MINLOG2;
- xnlock_get_irqsave(&heap->lock, s);
- block = heap->buckets[ilog].freelist;
- if (block == NULL) {
- block = get_free_range(heap, bsize, log2size);
- if (block == NULL)
- goto out;
- if (bsize <= XNHEAP_PAGESZ)
- heap->buckets[ilog].fcount += (XNHEAP_PAGESZ >>
log2size) - 1;
- } else {
- if (bsize <= XNHEAP_PAGESZ)
- --heap->buckets[ilog].fcount;
- XENO_BUG_ON(COBALT, (caddr_t)block < heap->membase ||
- (caddr_t)block >= heap->memlim);
- pagenum = ((caddr_t)block - heap->membase) /
XNHEAP_PAGESZ;
- ++heap->pagemap[pagenum].bcount;
+ if (pg < 0 || heap->pagemap[pg].map == -1U)
+ block = add_free_range(heap, bsize, log2size);
+ else {
+ b = ffs(~heap->pagemap[pg].map) - 1;
+ /*
+ * Got one block from the heading per-bucket
+ * page, tag it as busy in the per-page
+ * allocation map.
+ */
+ heap->pagemap[pg].map |= (1U << b);
+ heap->used_size += bsize;
+ block = heap->membase +
+ (pg << XNHEAP_PAGE_SHIFT) +
+ (b << log2size);
+ if (heap->pagemap[pg].map == -1U)
+ move_page_back(heap, pg, log2size);
}
- heap->buckets[ilog].freelist = *((caddr_t *)block);
- heap->used += bsize;
- } else {
- if (size > heap->size)
- return NULL;
-
- xnlock_get_irqsave(&heap->lock, s);
-
- /* Directly request a free page range. */
- block = get_free_range(heap, size, 0);
- if (block)
- heap->used += size;
}
-out:
+
xnlock_put_irqrestore(&heap->lock, s);
return block;
}
-EXPORT_SYMBOL_GPL(xnheap_alloc);
/**
* @fn void xnheap_free(struct xnheap *heap, void *block)
@@ -491,171 +614,219 @@ EXPORT_SYMBOL_GPL(xnheap_alloc);
*/
void xnheap_free(struct xnheap *heap, void *block)
{
- caddr_t freepage, lastpage, nextpage, tailpage, freeptr, *tailptr;
- int log2size, npages, nblocks, xpage, ilog;
- u32 pagenum, pagecont, boffset, bsize;
+ unsigned long pgoff, boff;
+ int log2size, pg, n;
+ size_t bsize;
+ u32 oldmap;
spl_t s;
xnlock_get_irqsave(&heap->lock, s);
- if ((caddr_t)block < heap->membase || (caddr_t)block >= heap->memlim)
- goto bad_block;
-
/* Compute the heading page number in the page map. */
- pagenum = ((caddr_t)block - heap->membase) / XNHEAP_PAGESZ;
- boffset = ((caddr_t)block - (heap->membase + pagenum * XNHEAP_PAGESZ));
-
- switch (heap->pagemap[pagenum].type) {
- case XNHEAP_PFREE: /* Unallocated page? */
- case XNHEAP_PCONT: /* Not a range heading page? */
- bad_block:
- xnlock_put_irqrestore(&heap->lock, s);
- XENO_BUG(COBALT);
- return;
-
- case XNHEAP_PLIST:
- npages = 1;
- while (npages < heap->npages &&
- heap->pagemap[pagenum + npages].type == XNHEAP_PCONT)
- npages++;
-
- bsize = npages * XNHEAP_PAGESZ;
+ pgoff = block - heap->membase;
+ pg = pgoff >> XNHEAP_PAGE_SHIFT;
+
+ if (!page_is_valid(heap, pg))
+ goto bad;
+
+ switch (heap->pagemap[pg].type) {
+ case page_list:
+ bsize = heap->pagemap[pg].bsize;
+ XENO_WARN_ON(MEMORY, (bsize & (XNHEAP_PAGE_SIZE - 1)) != 0);
+ release_page_range(heap, pagenr_to_addr(heap, pg), bsize);
+ break;
- free_page_list:
- /* Link all freed pages in a single sub-list. */
- for (freepage = (caddr_t) block,
- tailpage = (caddr_t) block + bsize - XNHEAP_PAGESZ;
- freepage < tailpage; freepage += XNHEAP_PAGESZ)
- *((caddr_t *) freepage) = freepage + XNHEAP_PAGESZ;
+ default:
+ log2size = heap->pagemap[pg].type;
+ bsize = (1 << log2size);
+ XENO_WARN_ON(MEMORY, bsize >= XNHEAP_PAGE_SIZE);
+ boff = pgoff & ~XNHEAP_PAGE_MASK;
+ if ((boff & (bsize - 1)) != 0) /* Not at block start? */
+ goto bad;
- free_pages:
- /* Mark the released pages as free. */
- for (pagecont = 0; pagecont < npages; pagecont++)
- heap->pagemap[pagenum + pagecont].type = XNHEAP_PFREE;
+ n = boff >> log2size; /* Block position in page. */
+ oldmap = heap->pagemap[pg].map;
+ heap->pagemap[pg].map &= ~(1U << n);
/*
- * Return the sub-list to the free page list, keeping
- * an increasing address order to favor coalescence.
+ * If the page the block was sitting on is fully idle,
+ * return it to the pool. Otherwise, check whether
+ * that page is transitioning from fully busy to
+ * partially busy state, in which case it should move
+ * toward the front of the per-bucket page list.
*/
- for (nextpage = heap->freelist, lastpage = NULL;
- nextpage != NULL && nextpage < (caddr_t) block;
- lastpage = nextpage, nextpage = *((caddr_t *)nextpage))
- ; /* Loop */
-
- *((caddr_t *)tailpage) = nextpage;
+ if (heap->pagemap[pg].map == ~gen_block_mask(log2size)) {
+ remove_page(heap, pg, log2size);
+ release_page_range(heap, pagenr_to_addr(heap, pg),
+ XNHEAP_PAGE_SIZE);
+ } else if (oldmap == -1U)
+ move_page_front(heap, pg, log2size);
+ }
- if (lastpage)
- *((caddr_t *)lastpage) = (caddr_t)block;
- else
- heap->freelist = (caddr_t)block;
- break;
+ heap->used_size -= bsize;
- default:
- log2size = heap->pagemap[pagenum].type;
- bsize = (1 << log2size);
- if ((boffset & (bsize - 1)) != 0) /* Not a block start? */
- goto bad_block;
+ xnlock_put_irqrestore(&heap->lock, s);
- /*
- * Return the page to the free list if we've just
- * freed its last busy block. Pages from multi-page
- * blocks are always pushed to the free list (bcount
- * value for the heading page is always 1).
- */
+ return;
+bad:
+ xnlock_put_irqrestore(&heap->lock, s);
- ilog = log2size - XNHEAP_MINLOG2;
- if (likely(--heap->pagemap[pagenum].bcount > 0)) {
- /* Return the block to the bucketed memory space. */
- *((caddr_t *)block) = heap->buckets[ilog].freelist;
- heap->buckets[ilog].freelist = block;
- ++heap->buckets[ilog].fcount;
- break;
- }
+ XENO_WARN(MEMORY, 1, "invalid block %p in heap %s",
+ block, heap->name);
+}
- /*
- * In the simplest case, we only have a single block
- * to deal with, which spans multiple pages. We just
- * need to release it as a list of pages, without
- * caring about the consistency of the bucket.
- */
- npages = bsize / XNHEAP_PAGESZ;
- if (unlikely(npages > 1))
- goto free_page_list;
-
- freepage = heap->membase + pagenum * XNHEAP_PAGESZ;
- block = freepage;
- tailpage = freepage;
- nextpage = freepage + XNHEAP_PAGESZ;
- nblocks = XNHEAP_PAGESZ >> log2size;
- heap->buckets[ilog].fcount -= (nblocks - 1);
- XENO_BUG_ON(COBALT, heap->buckets[ilog].fcount < 0);
+ssize_t xnheap_check_block(struct xnheap *heap, void *block)
+{
+ unsigned long pg, pgoff, boff;
+ ssize_t ret = -EINVAL;
+ size_t bsize;
+ spl_t s;
- /*
- * Still easy case: all free blocks are laid on a
- * single page we are now releasing. Just clear the
- * bucket and bail out.
- */
- if (likely(heap->buckets[ilog].fcount == 0)) {
- heap->buckets[ilog].freelist = NULL;
- goto free_pages;
- }
+ xnlock_get_irqsave(&heap->lock, s);
- /*
- * Worst case: multiple pages are traversed by the
- * bucket list. Scan the list to remove all blocks
- * belonging to the freed page. We are done whenever
- * all possible blocks from the freed page have been
- * traversed, or we hit the end of list, whichever
- * comes first.
- */
- for (tailptr = &heap->buckets[ilog].freelist, freeptr =
*tailptr, xpage = 1;
- freeptr != NULL && nblocks > 0; freeptr = *((caddr_t *)
freeptr)) {
- if (unlikely(freeptr < freepage || freeptr >=
nextpage)) {
- if (unlikely(xpage)) {
- *tailptr = freeptr;
- xpage = 0;
- }
- tailptr = (caddr_t *)freeptr;
- } else {
- --nblocks;
- xpage = 1;
- }
+ /* Calculate the page number from the block address. */
+ pgoff = block - heap->membase;
+ pg = pgoff >> XNHEAP_PAGE_SHIFT;
+ if (page_is_valid(heap, pg)) {
+ if (heap->pagemap[pg].type == page_list)
+ bsize = heap->pagemap[pg].bsize;
+ else {
+ bsize = (1 << heap->pagemap[pg].type);
+ boff = pgoff & ~XNHEAP_PAGE_MASK;
+ if ((boff & (bsize - 1)) != 0) /* Not at block start? */
+ goto out;
}
- *tailptr = freeptr;
- goto free_pages;
+ ret = (ssize_t)bsize;
}
-
- heap->used -= bsize;
-
+out:
xnlock_put_irqrestore(&heap->lock, s);
+
+ return ret;
}
-EXPORT_SYMBOL_GPL(xnheap_free);
-int xnheap_check_block(struct xnheap *heap, void *block)
+/**
+ * @fn xnheap_init(struct xnheap *heap, void *membase, u32 size)
+ * @brief Initialize a memory heap.
+ *
+ * Initializes a memory heap suitable for time-bounded allocation
+ * requests of dynamic memory.
+ *
+ * @param heap The address of a heap descriptor to initialize.
+ *
+ * @param membase The address of the storage area.
+ *
+ * @param size The size in bytes of the storage area. @a size must be
+ * a multiple of XNHEAP_PAGE_SIZE and smaller than (4Gb - PAGE_SIZE)
+ * in the current implementation.
+ *
+ * @return 0 is returned upon success, or:
+ *
+ * - -EINVAL is returned if @a size is either greater than
+ * XNHEAP_MAX_HEAPSZ, or not aligned on PAGE_SIZE.
+ *
+ * - -ENOMEM is returned upon failure of allocating the meta-data area
+ * used internally to maintain the heap.
+ *
+ * @coretags{secondary-only}
+ */
+int xnheap_init(struct xnheap *heap, void *membase, size_t size)
{
- int ptype, ret = -EINVAL;
- u32 pagenum, boffset;
+ int n, nrpages;
spl_t s;
- xnlock_get_irqsave(&heap->lock, s);
+ secondary_mode_only();
- if ((caddr_t)block < heap->membase || (caddr_t)block >= heap->memlim)
- goto out;
+ if (size > XNHEAP_MAX_HEAPSZ || !PAGE_ALIGNED(size))
+ return -EINVAL;
- /* Compute the heading page number in the page map. */
- pagenum = ((caddr_t)block - heap->membase) / XNHEAP_PAGESZ;
- boffset = ((caddr_t)block - (heap->membase + pagenum * XNHEAP_PAGESZ));
- ptype = heap->pagemap[pagenum].type;
+ /* Reset bucket page lists, all empty. */
+ for (n = 0; n < XNHEAP_MAX_BUCKETS; n++)
+ heap->buckets[n] = -1U;
- /* Raise error if page unallocated or not heading a range. */
- if (ptype != XNHEAP_PFREE && ptype != XNHEAP_PCONT)
- ret = 0;
-out:
- xnlock_put_irqrestore(&heap->lock, s);
+ xnlock_init(&heap->lock);
- return ret;
+ nrpages = size >> XNHEAP_PAGE_SHIFT;
+ heap->pagemap = kzalloc(sizeof(struct xnheap_pgentry) * nrpages,
+ GFP_KERNEL);
+ if (heap->pagemap == NULL)
+ return -ENOMEM;
+
+ heap->membase = membase;
+ heap->usable_size = size;
+ heap->used_size = 0;
+
+ /*
+ * The free page pool is maintained as a set of ranges of
+ * contiguous pages indexed by address and size in rbtrees.
+ * Initially, we have a single range in those trees covering
+ * the whole memory we have been given for the heap. Over
+ * time, that range will be split then possibly re-merged back
+ * as allocations and deallocations take place.
+ */
+ heap->size_tree = RB_ROOT;
+ heap->addr_tree = RB_ROOT;
+ release_page_range(heap, membase, size);
+
+ /* Default name, override with xnheap_set_name() */
+ ksformat(heap->name, sizeof(heap->name), "(%p)", heap);
+
+ xnlock_get_irqsave(&nklock, s);
+ list_add_tail(&heap->next, &heapq);
+ nrheaps++;
+ xnvfile_touch_tag(&vfile_tag);
+ xnlock_put_irqrestore(&nklock, s);
+
+ return 0;
}
-EXPORT_SYMBOL_GPL(xnheap_check_block);
+EXPORT_SYMBOL_GPL(xnheap_init);
+
+/**
+ * @fn void xnheap_destroy(struct xnheap *heap)
+ * @brief Destroys a memory heap.
+ *
+ * Destroys a memory heap.
+ *
+ * @param heap The heap descriptor.
+ *
+ * @coretags{secondary-only}
+ */
+void xnheap_destroy(struct xnheap *heap)
+{
+ spl_t s;
+
+ secondary_mode_only();
+
+ xnlock_get_irqsave(&nklock, s);
+ list_del(&heap->next);
+ nrheaps--;
+ xnvfile_touch_tag(&vfile_tag);
+ xnlock_put_irqrestore(&nklock, s);
+ kfree(heap->pagemap);
+}
+EXPORT_SYMBOL_GPL(xnheap_destroy);
+
+/**
+ * @fn xnheap_set_name(struct xnheap *heap,const char *name,...)
+ * @brief Set the heap's name string.
+ *
+ * Set the heap name that will be used in statistic outputs.
+ *
+ * @param heap The address of a heap descriptor.
+ *
+ * @param name Name displayed in statistic outputs. This parameter can
+ * be a printk()-like format argument list.
+ *
+ * @coretags{task-unrestricted}
+ */
+void xnheap_set_name(struct xnheap *heap, const char *name, ...)
+{
+ va_list args;
+
+ va_start(args, name);
+ kvsformat(heap->name, sizeof(heap->name), name, args);
+ va_end(args);
+}
+EXPORT_SYMBOL_GPL(xnheap_set_name);
void *xnheap_vmalloc(size_t size)
{
_______________________________________________
Xenomai-git mailing list
Xenomai-git@xenomai.org
https://xenomai.org/mailman/listinfo/xenomai-git
