#include <stdbool.h>
#include <stdint.h>
#include <kern/assert.h>
#include <kern/locks.h>
#include <os/atomic_private.h>
#include "log_mem.h"
#define BLOCK_INVALID ((size_t)-1)
#define BLOCK_LEVEL_BASE(level) ((1 << (level)) - 1)
#define BLOCK_SIZE(level) (1 << (level))
#define BLOCK_PARENT(b) (((b) % 2 == 0) ? ((b) >> 1) - 1 : ((b) >> 1))
#define BLOCK_LCHILD(b) (((b) << 1) + 1)
#define BLOCK_BUDDY(b) (((b) & 0x1) ? (b) + 1 : (b) - 1)
#define BLOCK_INDEX(lm, l, a, s) \
(BLOCK_LEVEL_BASE(l) + ((uintptr_t)(a) - (uintptr_t)(lm)->lm_mem) / (s))
#define BITMAP_BUCKET_SIZE (8 * sizeof(((logmem_t *)0)->lm_mem_map[0]))
#define BITMAP_BUCKET(i) ((i) / BITMAP_BUCKET_SIZE)
#define BITMAP_BIT(i) (1 << (BITMAP_BUCKET_SIZE - ((i) % BITMAP_BUCKET_SIZE) - 1))
static bool
bitmap_get(logmem_t *lm, size_t block)
{
return lm->lm_mem_map[BITMAP_BUCKET(block)] & BITMAP_BIT(block);
}
static void
bitmap_set(logmem_t *lm, size_t block)
{
lm->lm_mem_map[BITMAP_BUCKET(block)] |= BITMAP_BIT(block);
}
static void
bitmap_clear(logmem_t *lm, size_t block)
{
lm->lm_mem_map[BITMAP_BUCKET(block)] &= ~BITMAP_BIT(block);
}
static void
bitmap_reserve_root(logmem_t *lm, size_t block)
{
const size_t top_block = BLOCK_LEVEL_BASE(lm->lm_cap_order - lm->lm_max_order);
for (ssize_t next = BLOCK_PARENT(block); next >= top_block; next = BLOCK_PARENT(next)) {
if (bitmap_get(lm, next)) {
break;
}
bitmap_set(lm, next);
}
}
static void
bitmap_release_root(logmem_t *lm, size_t block)
{
const size_t top_block = BLOCK_LEVEL_BASE(lm->lm_cap_order - lm->lm_max_order);
int buddy_allocated = 0;
while (block > top_block) {
buddy_allocated = bitmap_get(lm, BLOCK_BUDDY(block));
block = BLOCK_PARENT(block);
if (buddy_allocated) {
break;
}
bitmap_clear(lm, block);
}
}
static void
bitmap_update_subtree(logmem_t *lm, size_t level, size_t block, void (*fun)(logmem_t *, size_t))
{
const size_t lcount = lm->lm_cap_order - lm->lm_min_order - level + 1;
for (size_t l = 0, n = 1; l < lcount; l++, n <<= 1) {
for (int i = 0; i < n; i++) {
fun(lm, block + i);
}
block = BLOCK_LCHILD(block);
}
}
static void
bitmap_release_subtree(logmem_t *lm, size_t level, size_t block)
{
bitmap_update_subtree(lm, level, block, bitmap_clear);
}
static void
bitmap_reserve_subtree(logmem_t *lm, size_t level, size_t block)
{
bitmap_update_subtree(lm, level, block, bitmap_set);
}
static size_t
block_size_level(logmem_t *lm, size_t amount)
{
for (size_t l = lm->lm_min_order; l <= lm->lm_max_order; l++) {
if (amount <= BLOCK_SIZE(l)) {
return lm->lm_cap_order - l;
}
}
return BLOCK_INVALID;
}
static size_t
block_locate(logmem_t *lm, void *addr, size_t amount, size_t *block)
{
size_t level = block_size_level(lm, amount);
if (level != BLOCK_INVALID) {
*block = BLOCK_INDEX(lm, level, addr, amount);
}
return level;
}
static size_t
block_reserve(logmem_t *lm, size_t level)
{
assert(level != BLOCK_INVALID);
const size_t base = BLOCK_LEVEL_BASE(level);
const size_t end = base + BLOCK_SIZE(level);
lck_spin_lock(lm->lm_lock);
for (size_t block = base; block < end; block++) {
if (!bitmap_get(lm, block)) {
bitmap_reserve_root(lm, block);
bitmap_reserve_subtree(lm, level, block);
lck_spin_unlock(lm->lm_lock);
return block - base;
}
}
lck_spin_unlock(lm->lm_lock);
return BLOCK_INVALID;
}
void *
logmem_alloc(logmem_t *lm, size_t *amount)
{
assert(amount);
os_atomic_inc(&lm->lm_cnt_allocations, relaxed);
if (*amount == 0 || *amount > BLOCK_SIZE(lm->lm_max_order)) {
os_atomic_inc(&lm->lm_cnt_failed_size, relaxed);
return NULL;
}
size_t level = block_size_level(lm, *amount);
size_t block = block_reserve(lm, level);
if (block == BLOCK_INVALID) {
os_atomic_inc(&lm->lm_cnt_failed_full, relaxed);
return NULL;
}
*amount = BLOCK_SIZE(lm->lm_cap_order - level);
os_atomic_sub(&lm->lm_cnt_free, (uint32_t)*amount, relaxed);
return &lm->lm_mem[block * *amount];
}
void
logmem_free(logmem_t *lm, void *addr, size_t amount)
{
assert(addr);
assert(amount > 0 && ((amount & (amount - 1)) == 0));
size_t block = BLOCK_INVALID;
size_t level = block_locate(lm, addr, amount, &block);
assert(level != BLOCK_INVALID);
assert(block != BLOCK_INVALID);
lck_spin_lock(lm->lm_lock);
bitmap_release_root(lm, block);
bitmap_release_subtree(lm, level, block);
lck_spin_unlock(lm->lm_lock);
os_atomic_add(&lm->lm_cnt_free, (uint32_t)amount, relaxed);
}
size_t
logmem_max_size(const logmem_t *lm)
{
return BLOCK_SIZE(lm->lm_max_order);
}