heapmem.h

/*
 * Copyright (C) 2018 Philippe Gerum <rpm@xenomai.org>.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
 */
#ifndef _BOILERPLATE_HEAPMEM_H
#define _BOILERPLATE_HEAPMEM_H

#include <sys/types.h>
#include <stdint.h>
#include <limits.h>
#include <boilerplate/list.h>
#include <boilerplate/lock.h>
#include <boilerplate/avl.h>

#define HEAPMEM_PAGE_SHIFT      9 /* 2^9 => 512 bytes */
#define HEAPMEM_PAGE_SIZE       (1UL << HEAPMEM_PAGE_SHIFT)
#define HEAPMEM_PAGE_MASK       (~(HEAPMEM_PAGE_SIZE - 1))
#define HEAPMEM_MIN_LOG2        4 /* 16 bytes */
/*
 * Use bucketed memory for sizes between 2^HEAPMEM_MIN_LOG2 and
 * 2^(HEAPMEM_PAGE_SHIFT-1).
 */
#define HEAPMEM_MAX             (HEAPMEM_PAGE_SHIFT - HEAPMEM_MIN_LOG2)
#define HEAPMEM_MIN_ALIGN       (1U << HEAPMEM_MIN_LOG2)
/* Max size of an extent (4Gb - HEAPMEM_PAGE_SIZE). */
#define HEAPMEM_MAX_EXTSZ       (4294967295U - HEAPMEM_PAGE_SIZE + 1)
/* Bits we need for encoding a page # */
#define HEAPMEM_PGENT_BITS      (32 - HEAPMEM_PAGE_SHIFT)

/* Each page is represented by a page map entry. */
#define HEAPMEM_PGMAP_BYTES     sizeof(struct heapmem_pgentry)

struct heapmem_pgentry {
        /* Linkage in bucket list. */
        unsigned int prev : HEAPMEM_PGENT_BITS;
        unsigned int next : HEAPMEM_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 {
                uint32_t map;
                uint32_t bsize;
        };
};

/*
 * A range descriptor is stored at the beginning of the first page of
 * a range of free pages. heapmem_range.size is nrpages *
 * HEAPMEM_PAGE_SIZE. Ranges are indexed by address and size in AVL
 * trees.
 */
struct heapmem_range {
        struct avlh addr_node;
        struct avlh size_node;
        size_t size;
};

struct heapmem_extent {
        struct pvholder next;
        void *membase;          /* Base of page array */
        void *memlim;           /* Limit of page array */
        struct avl addr_tree;
        struct avl size_tree;
        struct heapmem_pgentry pagemap[0]; /* Start of page entries[] */
};

struct heap_memory {
        pthread_mutex_t lock;
        struct pvlistobj extents;
        size_t arena_size;
        size_t usable_size;
        size_t used_size;
        /* Heads of page lists for log2-sized blocks. */
        uint32_t buckets[HEAPMEM_MAX];
};

#define __HEAPMEM_MAP_SIZE(__nrpages)                                   \
        ((__nrpages) * HEAPMEM_PGMAP_BYTES)

#define __HEAPMEM_ARENA_SIZE(__size)                                    \
        (__size +                                                       \
         __align_to(sizeof(struct heapmem_extent) +                     \
                    __HEAPMEM_MAP_SIZE((__size) >> HEAPMEM_PAGE_SHIFT), \
                    HEAPMEM_MIN_ALIGN))

/*
 * Calculate the minimal size of the memory arena needed to contain a
 * heap of __user_size bytes, including our meta data for managing it.
 * Usable at build time if __user_size is constant.
 */
#define HEAPMEM_ARENA_SIZE(__user_size)                                 \
        __HEAPMEM_ARENA_SIZE(__align_to(__user_size, HEAPMEM_PAGE_SIZE))

#ifdef __cplusplus
extern "C" {
#endif

int heapmem_init(struct heap_memory *heap,
                 void *mem, size_t size);

int heapmem_extend(struct heap_memory *heap,
                   void *mem, size_t size);

void heapmem_destroy(struct heap_memory *heap);

void *heapmem_alloc(struct heap_memory *heap,
                    size_t size) __alloc_size(2);

int heapmem_free(struct heap_memory *heap,
                 void *block);

static inline
size_t heapmem_arena_size(const struct heap_memory *heap)
{
        return heap->arena_size;
}

static inline
size_t heapmem_usable_size(const struct heap_memory *heap)
{
        return heap->usable_size;
}

static inline
size_t heapmem_used_size(const struct heap_memory *heap)
{
        return heap->used_size;
}

ssize_t heapmem_check(struct heap_memory *heap,
                      void *block);

#ifdef __cplusplus
}
#endif

#endif /* _BOILERPLATE_HEAPMEM_H */