#ifndef _MALLOC_H
#define _MALLOC_H 1
/* A bucket-based malloc implementation for 2^n sized objects.
* Allocates memory at pbrk for use in dynamic allocations, called "objects".
* Each object is pre-empted by metadata, which stores a checksum, the width,
* and a bit to mark it as taken.
*
* Each alloc-able region is pre-empted by a "bucket", which stores metadata
* about the bucket's state, the width, the first free object, and the next
* bucket in the chain.
*
* Buckets are allocated when needed. The width of the new bucket is determined
* by the object that needs the bucket.
* Buckets are always page aligned, and the size is a multiple of a page width.
*
* Dependencies:
* stddef.h
* stdint.h
* errno.h
* assert.h
* assert
* string.h
* memset
* memcpy
* unistd.h
* sbrk
* brk
*
* with MALLOC_DBG:
* stdio.h
* printf*/
#include <stddef.h>
#include <stdint.h>
#define DBGPRINT(...)
#ifdef MALLOC_DBG
#include <stdio.h>
#undef DBGPRINT
#define DBGPRINT(...) printf(__VA_ARGS__)
#endif
/* Bucket checksum is a 64-bit value containing the string "BUCKET\0\0"*/
#define OBJ_CHECKSUM \
(((uintmax_t)'B') | \
((uintmax_t)'U' << 8) | \
((uintmax_t)'C' << 16) | \
((uintmax_t)'K' << 24) | \
((uintmax_t)'E' << 32) | \
((uintmax_t)'T' << 40))
/* For an object to be valid, the object must have the correct checksum.*/
#define OBJ_VALID(obj) (obj->checksum == OBJ_CHECKSUM)
/* Object width is assumed to be a multiple of two. The first bit is reserved
* for the taken flag.*/
#define OBJ_WIDTH(obj) (obj->size_taken & ~1)
#define OBJ_TAKEN(obj) (obj->size_taken & 1)
/* Gets the object struct after this object.
* Since objects are allocated in-place, we can get the next object using
* the object's size and it's pointer to the start of data.
*
* The same is true for getting the metadata for any given data pointer.
* We take the pointer and subtract the size of the object struct from it
* since the metadata is behind the actual data.*/
#define OBJ_AFTER(obj) \
((bucket_obj_t*)(((uintptr_t)obj->data) + OBJ_WIDTH(obj)))
#define OBJ_FROM_PTR(ptr) ((bucket_obj_t*)((uintptr_t)ptr - sizeof(bucket_obj_t)));
typedef struct bucket_obj
{
uintmax_t checksum;
size_t size_taken;
char data[];
} bucket_obj_t;
#define LOG2(n) ((31) - __builtin_clz(n))
/* Buckets are always aligned to the page boundary for cache friendliness.*/
#define BUCKET_ALIGN (4096)
/* Buckets should always be a multiple of the page width, expanding with the
* initial object size.*/
#define BUCKET_WIDTH(w) \
(1UL << (12 + (w < BUCKET_ALIGN ? 0 : LOG2(w + 1) - 11)))
/* Bucket metadata is stored behind the object metadata.*/
typedef struct bucket
{
size_t checksum;
struct bucket *next;
uintptr_t limit;
bucket_obj_t *firstfree; /* Helpful for fast object allocations.*/
char objs[];
} bucket_t;
/* The overall size of an object (data + metadata) should be 2*metadata.*/
#define OBJ_SIZE_MIN (sizeof(bucket_obj_t))
/* Data width is always a power of two.*/
#define REALW(n) \
(n < OBJ_SIZE_MIN ? OBJ_SIZE_MIN : (1UL << (LOG2(n + 1))))
typedef struct heap_cache
{
bucket_t *head;
bucket_t *tail;
} heap_cache_t;
/**Given the heap cache and an object, find the bucket to which the object
* belongs.
* Since buckets are always page aligned, we can check each page boundary
* for the checksum until we find it, then check the limit.
* Since we also know the first bucket in the cache, we can also check if the
* passed object is invalid and return NULL.
* @param heap cache.
* @param obj to find the bucket for.
* @return bucket owning obj, or NULL if obj is invalid.*/
bucket_t *__bucket_from_obj(heap_cache_t *heap, bucket_obj_t *obj);
/**Allocate w bytes into the given heap.
* If w == 0, returns NULL.
* If w is not a power of 2, rounds to the nearest pow2.
* If the heap is corrupted, assert fail.
* If the program is OOM, errno is assumed to be set and returns (void*)-1
* @param heap cache.
* @param w n-bytes to allocate.
* @return pointer to allocated memory.*/
void* __malloc_impl(heap_cache_t *heap, size_t w);
/**Allocate a contiguous array of nmemb members each w wide.
* Newly allocated memory is zero'd.
* If w == 0 || nmemb == 0, returns NULL
* If w is not a power of 2, rounds to nearest pow2
* If the heap is corrupted, assert fail
* If the program is OON, ernno is assumed to be set and returns (void*)-1
* @param heap cache.
* @param nmemb number of members.
* @param w number of bytes per member.
* @return pointer to allocated memory.*/
void* __calloc_impl(heap_cache_t *heap, size_t nmemb, size_t w);
/**Resize the given allocated memory region to fit w.
* If w is less than the original width, does nothing.
* If w == 0, frees p
* If the heap is corrupted, assert fail.
* If the heap is OOM, errno is assumed to be set and returns (void*)-1
* @param heap cache.
* @param p pointer to reallocate.
* @param w width to fit p to.
* @return pointer to memory allocated to fit w.*/
void* __realloc_impl(heap_cache_t *heap, void *p, size_t w);
/**Resize the given allocated contiguous array to fit nmemb members of w width
* objects.
* Zeros the new members excluding already existing data.
* If w * nmemb is less than the original width, does nothing.
* If w == 0 || nmemb == 0, frees p
* If the heap is corrupted, assert fail.
* If the heap is OOM, errno is assumed to be set and returns (void*)-1
* @param heap cache.
* @param p pointer to reallocate.
* @param nmemb number of members.
* @param w width to fit p to.
* @return pointer to memory allocated to fit w * nmemb.*/
void* __reallocarray_impl(heap_cache_t *heap, void *p, size_t nmemb, size_t w);
/**Free a pointer in the given heap.
* If p == NULL, do nothing.
* If p does not fall in the range of heap, assert fail.
* If the heap is corrupted, assert fail.
* @param heap cache.
* @param p pointer to free.*/
void __free_impl(heap_cache_t *heap, void *p);
#endif
