Module: xenomai-3 Branch: next Commit: 0446cc545543100016491a71d7e2fc87082e6575 URL: http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0446cc545543100016491a71d7e2fc87082e6575
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..8a1c6f6 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); +ssize_t 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