// SafeC Standard Library — TLSF Allocator
#pragma once
#include <std/stddef.h>
#include <std/alloc/tlsf.h>
#include <std/stderr_compat.h>
namespace std {
extern unsigned char* malloc(size_t size);
extern void free(unsigned char* ptr);
extern unsigned char* memset(unsigned char* ptr, int val, size_t n);
// Same rationale as mem.sc/pool.sc/slab.sc for not using panic.h/panic_at here.
extern void abort();
extern int fprintf(CFile_* stream, const char* fmt, ...);
static void tlsf_abort_(const char* msg) {
unsafe { fprintf(SAFEC_STDERR_, "std::alloc (tlsf) fatal: %s\n", msg); }
unsafe { abort(); }
}
// Block header size (32 bytes: size + prev_phys + next_free + prev_free)
inline unsigned long tlsf_hdr_size_() {
return (unsigned long)32;
}
// Minimum block size (must fit header pointers when free)
inline unsigned long tlsf_min_block_() {
return (unsigned long)32;
}
// ── TlsfBlock methods ────────────────────────────────────────────────────────
inline int TlsfBlock::is_free_() const {
unsafe { return (int)(self.size & (unsigned long)1); }
}
inline unsigned long TlsfBlock::block_size_() const {
unsafe { return self.size & ~(unsigned long)1; }
}
inline void TlsfBlock::set_free_() {
unsafe { self.size = self.size | (unsigned long)1; }
}
inline void TlsfBlock::set_used_() {
unsafe { self.size = self.size & ~(unsigned long)1; }
}
// ── Utility free function ────────────────────────────────────────────────────
void tlsf_mapping_(unsigned long size, &int fl, &int sl) {
if (size < (unsigned long)256) {
*fl = 0;
*sl = (int)(size / (unsigned long)16);
} else {
int f = 0;
unsigned long tmp = size;
while (tmp >= (unsigned long)2) {
tmp = tmp / (unsigned long)2;
f = f + 1;
}
*fl = f;
int shift = f - 4;
if (shift < 0) { shift = 0; }
unsigned long s = size;
int i = 0;
while (i < shift) {
s = s / (unsigned long)2;
i = i + 1;
}
int sli = (int)s - 16;
if (sli < 0) { sli = 0; }
if (sli > 15) { sli = 15; }
*sl = sli;
}
}
// ── TlsfAllocator methods ────────────────────────────────────────────────────
// Physical successor of 'blk' inside the allocator's buffer, or null for
// the last block. Every split/merge must re-point the successor's
// prev_phys, or a later dealloc() coalesces through a stale header.
static ?&TlsfBlock tlsf_next_phys_(&TlsfBlock blk, &TlsfAllocator a) {
unsigned long end;
unsigned long limit;
unsafe {
end = (unsigned long)blk + tlsf_hdr_size_() + blk.block_size_();
limit = (unsigned long)a.base + a.cap;
}
if (end + tlsf_hdr_size_() > limit) { return null; }
unsafe { return (?&TlsfBlock)end; }
}
// Point 'blk''s physical successor (if any) back at 'blk'.
static void tlsf_link_next_(&TlsfBlock blk, &TlsfAllocator a) {
match (tlsf_next_phys_(blk, a)) {
case null: return;
case some(n): { unsafe { n.prev_phys = (?&TlsfBlock)blk; } }
}
}
inline void TlsfAllocator::insert_(&TlsfBlock blk) {
int fl = 0;
int sl = 0;
unsigned long sz = blk.block_size_();
tlsf_mapping_(sz, &fl, &sl);
blk.set_free_();
unsafe {
int idx = fl * 16 + sl;
?&TlsfBlock head = self.blocks[idx];
blk.next_free = head;
blk.prev_free = null;
if (!head.is_null()) {
struct TlsfBlock* h = (struct TlsfBlock*)head;
h->prev_free = (?&TlsfBlock)blk;
}
self.blocks[idx] = (?&TlsfBlock)blk;
self.fl_bitmap = self.fl_bitmap | ((unsigned int)1 << fl);
self.sl_bitmap[fl] = self.sl_bitmap[fl] | ((unsigned int)1 << sl);
}
}
void TlsfAllocator::remove_(&TlsfBlock blk) {
int fl = 0;
int sl = 0;
unsigned long sz = blk.block_size_();
tlsf_mapping_(sz, &fl, &sl);
unsafe {
int idx = fl * 16 + sl;
struct TlsfBlock* prev = (struct TlsfBlock*)blk.prev_free;
struct TlsfBlock* next = (struct TlsfBlock*)blk.next_free;
if (prev != (struct TlsfBlock*)0) {
prev->next_free = (?&TlsfBlock)next;
} else {
self.blocks[idx] = (?&TlsfBlock)next;
}
if (next != (struct TlsfBlock*)0) {
next->prev_free = (?&TlsfBlock)prev;
}
if (self.blocks[idx] == (unsigned char*)0) {
self.sl_bitmap[fl] = self.sl_bitmap[fl] & ~((unsigned int)1 << sl);
if (self.sl_bitmap[fl] == (unsigned int)0) {
self.fl_bitmap = self.fl_bitmap & ~((unsigned int)1 << fl);
}
}
}
}
?&TlsfBlock TlsfAllocator::find_(unsigned long size) {
// Round the request up to the start of the next size class first
// ("mapping_search" in the TLSF paper): every block in the request's
// own class is only >= that class's lower bound, which may be smaller
// than 'size' itself. Searching from the next class up guarantees any
// block found is big enough, keeping alloc O(1) with no list walk.
unsigned long search = size;
if (search < (unsigned long)256) {
search = search + (unsigned long)15;
} else {
int f = 0;
unsigned long tmp = search;
while (tmp >= (unsigned long)2) { tmp = tmp / (unsigned long)2; f = f + 1; }
search = search + (((unsigned long)1 << (unsigned long)(f - 4)) - (unsigned long)1);
}
int fl = 0;
int sl = 0;
tlsf_mapping_(search, &fl, &sl);
if (fl >= TLSF_FL_MAX) { return null; }
unsafe {
// 'search' is already rounded up to a class whose every block fits,
// so that class itself (sl) is searched too, not only those above it.
unsigned int sl_map = self.sl_bitmap[fl] & ~(((unsigned int)1 << sl) - (unsigned int)1);
if (sl_map == (unsigned int)0) {
if (fl + 1 >= TLSF_FL_MAX) { return null; }
unsigned int fl_map = self.fl_bitmap & ~(((unsigned int)1 << (fl + 1)) - (unsigned int)1);
if (fl_map == (unsigned int)0) {
return null;
}
fl = 0;
unsigned int ftmp = fl_map;
while ((ftmp & (unsigned int)1) == (unsigned int)0) {
ftmp = ftmp >> 1;
fl = fl + 1;
}
sl_map = self.sl_bitmap[fl];
}
sl = 0;
unsigned int stmp = sl_map;
while ((stmp & (unsigned int)1) == (unsigned int)0) {
stmp = stmp >> 1;
sl = sl + 1;
}
int idx = fl * 16 + sl;
return self.blocks[idx];
}
}
// Empty free lists, then the whole buffer as one free block (none when
// cap can't hold a header).
void TlsfAllocator::reset() {
self.fl_bitmap = (unsigned int)0;
unsafe {
memset((unsigned char*)self.sl_bitmap, 0, sizeof(self.sl_bitmap));
memset((unsigned char*)self.blocks, 0, sizeof(self.blocks));
}
unsigned long hdr = tlsf_hdr_size_();
if (self.cap > hdr) {
unsafe {
struct TlsfBlock* blk = (struct TlsfBlock*)self.base;
blk->size = self.cap - hdr;
blk->prev_phys = null;
blk->next_free = null;
blk->prev_free = null;
self.insert_(&(*blk));
}
}
}
struct TlsfAllocator TlsfAllocator::over([]unsigned char buffer_s) {
unsigned long cap = buffer_s.len;
&unsigned char buffer;
unsafe { buffer = (&unsigned char)buffer_s.ptr; }
struct TlsfAllocator a;
unsafe { a.base = (&heap unsigned char)buffer; }
a.owned = 0;
a.cap = cap;
a.reset();
return a;
}
struct TlsfAllocator TlsfAllocator::new(unsigned long cap) {
struct TlsfAllocator a;
unsafe { a.base = (&heap unsigned char)malloc(cap); }
a.owned = 1;
a.cap = cap;
a.reset();
return a;
}
?&heap unsigned char TlsfAllocator::alloc(unsigned long size, unsigned long align) {
// Headers are 32 bytes and block sizes multiples of 8, so every block
// starts at an 8-aligned offset and payloads are 8-aligned: alignments
// up to 8 come free; above that would need padding blocks, so null.
if ((align & (align - 1UL)) != 0UL || align > 8UL) { return null; }
if (size > self.cap) { return null; } // also keeps the rounding below from wrapping
unsigned long hdr = tlsf_hdr_size_();
unsigned long min = tlsf_min_block_();
unsigned long aligned = (size + (unsigned long)7) & ~(unsigned long)7;
if (aligned < min) { aligned = min; }
?&TlsfBlock found = self.find_(aligned);
if (found.is_null()) {
return null;
}
unsafe {
struct TlsfBlock* blk = (struct TlsfBlock*)found;
self.remove_(&(*blk));
unsigned long bsz = blk->block_size_();
if (bsz >= aligned + hdr + min) {
struct TlsfBlock* rest = (struct TlsfBlock*)((unsigned long)blk + hdr + aligned);
rest->size = bsz - aligned - hdr;
rest->prev_phys = (?&TlsfBlock)blk;
rest->next_free = null;
rest->prev_free = null;
blk->size = aligned;
tlsf_link_next_(rest, self);
self.insert_(&(*rest));
}
blk->set_used_();
return (?&heap unsigned char)((unsigned long)blk + hdr);
}
}
void TlsfAllocator::dealloc(?&heap unsigned char ptr_ref) {
unsigned char* ptr = ptr_ref;
if (ptr == (unsigned char*)0) { return; }
unsigned long hdr = tlsf_hdr_size_();
unsafe {
struct TlsfBlock* blk = (struct TlsfBlock*)((unsigned long)ptr - hdr);
// blk's header lives in this allocator's own backing buffer for
// the buffer's whole lifetime — freeing it never hands memory to
// a system allocator that could clobber the free/used bit before
// a second dealloc() reads it, so (unlike mem.sc's alloc()/dealloc())
// this check is reliable without a quarantine.
if (blk->is_free_() == 1) {
tlsf_abort_("dealloc() called twice on the same pointer (double free)");
return;
}
// Coalesce with next physical block if free
unsigned long blk_end = (unsigned long)blk + hdr + blk->block_size_();
unsigned long buf_end = (unsigned long)self.base + self.cap;
if (blk_end < buf_end) {
struct TlsfBlock* next = (struct TlsfBlock*)blk_end;
if (next->is_free_() == 1) {
self.remove_(&(*next));
blk->size = blk->block_size_() + hdr + next->block_size_();
tlsf_link_next_(blk, self);
}
}
// Coalesce with previous physical block if free
if (blk->prev_phys != (unsigned char*)0) {
struct TlsfBlock* prev = (struct TlsfBlock*)blk->prev_phys;
if (prev->is_free_() == 1) {
self.remove_(&(*prev));
prev->size = prev->block_size_() + hdr + blk->block_size_();
blk = prev;
tlsf_link_next_(blk, self);
}
}
self.insert_(&(*blk));
}
}
inline void TlsfAllocator::destroy() { self.drop(); }
inline void TlsfAllocator::drop() {
if (self.owned) { unsafe { free((unsigned char*)self.base); } }
self.cap = (unsigned long)0;
}
} // namespace std