#ifndef MALLOC_META_H
#define MALLOC_META_H
#include <stdint.h>
#include <errno.h>
#include <limits.h>
#include "glue.h"
__attribute__((__visibility__("hidden")))
extern const uint16_t size_classes[];
#define MMAP_THRESHOLD 131052
#define UNIT 16
#define IB 4
struct group {
struct meta *meta;
unsigned char active_idx:5;
char pad[UNIT - sizeof(struct meta *) - 1];
unsigned char storage[];
};
struct meta {
struct meta *prev, *next;
struct group *mem;
volatile int avail_mask, freed_mask;
uintptr_t last_idx:5;
uintptr_t freeable:1;
uintptr_t sizeclass:6;
uintptr_t maplen:8*sizeof(uintptr_t)-12;
};
struct meta_area {
uint64_t check;
struct meta_area *next;
int nslots;
struct meta slots[];
};
struct malloc_context {
uint64_t secret;
#ifndef PAGESIZE
size_t pagesize;
#endif
int init_done;
unsigned mmap_counter;
struct meta *free_meta_head;
struct meta *avail_meta;
size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift;
struct meta_area *meta_area_head, *meta_area_tail;
unsigned char *avail_meta_areas;
struct meta *active[48];
size_t usage_by_class[48];
uint8_t unmap_seq[32], bounces[32];
uint8_t seq;
uintptr_t brk;
};
__attribute__((__visibility__("hidden")))
extern struct malloc_context ctx;
#ifdef PAGESIZE
#define PGSZ PAGESIZE
#else
#define PGSZ ctx.pagesize
#endif
__attribute__((__visibility__("hidden")))
struct meta *alloc_meta(void);
__attribute__((__visibility__("hidden")))
int is_allzero(void *);
static inline void queue(struct meta **phead, struct meta *m)
{
assert(!m->next);
assert(!m->prev);
if (*phead) {
struct meta *head = *phead;
m->next = head;
m->prev = head->prev;
m->next->prev = m->prev->next = m;
} else {
m->prev = m->next = m;
*phead = m;
}
}
static inline void dequeue(struct meta **phead, struct meta *m)
{
if (m->next != m) {
m->prev->next = m->next;
m->next->prev = m->prev;
if (*phead == m) *phead = m->next;
} else {
*phead = 0;
}
m->prev = m->next = 0;
}
static inline struct meta *dequeue_head(struct meta **phead)
{
struct meta *m = *phead;
if (m) dequeue(phead, m);
return m;
}
static inline void free_meta(struct meta *m)
{
*m = (struct meta){0};
queue(&ctx.free_meta_head, m);
}
static inline uint32_t activate_group(struct meta *m)
{
assert(!m->avail_mask);
uint32_t mask, act = (2u<<m->mem->active_idx)-1;
do mask = m->freed_mask;
while (a_cas(&m->freed_mask, mask, mask&~act)!=mask);
return m->avail_mask = mask & act;
}
static inline int get_slot_index(const unsigned char *p)
{
return p[-3] & 31;
}
static inline struct meta *get_meta(const unsigned char *p)
{
assert(!((uintptr_t)p & 15));
int offset = *(const uint16_t *)(p - 2);
int index = get_slot_index(p);
if (p[-4]) {
assert(!offset);
offset = *(uint32_t *)(p - 8);
assert(offset > 0xffff);
}
const struct group *base = (const void *)(p - UNIT*offset - UNIT);
const struct meta *meta = base->meta;
assert(meta->mem == base);
assert(index <= meta->last_idx);
assert(!(meta->avail_mask & (1u<<index)));
assert(!(meta->freed_mask & (1u<<index)));
const struct meta_area *area = (void *)((uintptr_t)meta & -4096);
assert(area->check == ctx.secret);
if (meta->sizeclass < 48) {
assert(offset >= size_classes[meta->sizeclass]*index);
assert(offset < size_classes[meta->sizeclass]*(index+1));
} else {
assert(meta->sizeclass == 63);
}
if (meta->maplen) {
assert(offset <= meta->maplen*4096UL/UNIT - 1);
}
return (struct meta *)meta;
}
static inline size_t get_nominal_size(const unsigned char *p, const unsigned char *end)
{
size_t reserved = p[-3] >> 5;
if (reserved >= 5) {
assert(reserved == 5);
reserved = *(const uint32_t *)(end-4);
assert(reserved >= 5);
assert(!end[-5]);
}
assert(reserved <= end-p);
assert(!*(end-reserved));
// also check the slot's overflow byte
assert(!*end);
return end-reserved-p;
}
static inline size_t get_stride(const struct meta *g)
{
if (!g->last_idx && g->maplen) {
return g->maplen*4096UL - UNIT;
} else {
return UNIT*size_classes[g->sizeclass];
}
}
static inline void set_size(unsigned char *p, unsigned char *end, size_t n)
{
int reserved = end-p-n;
if (reserved) end[-reserved] = 0;
if (reserved >= 5) {
*(uint32_t *)(end-4) = reserved;
end[-5] = 0;
reserved = 5;
}
p[-3] = (p[-3]&31) + (reserved<<5);
}
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
{
size_t stride = get_stride(g);
size_t slack = (stride-IB-n)/UNIT;
unsigned char *p = g->mem->storage + stride*idx;
unsigned char *end = p+stride-IB;
// cycle offset within slot to increase interval to address
// reuse, facilitate trapping double-free.
int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
assert(!p[-4]);
if (off > slack) {
size_t m = slack;
m |= m>>1; m |= m>>2; m |= m>>4;
off &= m;
if (off > slack) off -= slack+1;
assert(off <= slack);
}
if (off) {
// store offset in unused header at offset zero
// if enframing at non-zero offset.
*(uint16_t *)(p-2) = off;
p[-3] = 7<<5;
p += UNIT*off;
// for nonzero offset there is no permanent check
// byte, so make one.
p[-4] = 0;
}
*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT;
p[-3] = idx;
set_size(p, end, n);
return p;
}
static inline int size_to_class(size_t n)
{
n = (n+IB-1)>>4;
if (n<10) return n;
n++;
int i = (28-a_clz_32(n))*4 + 8;
if (n>size_classes[i+1]) i+=2;
if (n>size_classes[i]) i++;
return i;
}
static inline int size_overflows(size_t n)
{
if (n >= SIZE_MAX/2 - 4096) {
errno = ENOMEM;
return 1;
}
return 0;
}
static inline void step_seq(void)
{
if (ctx.seq==255) {
for (int i=0; i<32; i++) ctx.unmap_seq[i] = 0;
ctx.seq = 1;
} else {
ctx.seq++;
}
}
static inline void record_seq(int sc)
{
if (sc-7U < 32) ctx.unmap_seq[sc-7] = ctx.seq;
}
static inline void account_bounce(int sc)
{
if (sc-7U < 32) {
int seq = ctx.unmap_seq[sc-7];
if (seq && ctx.seq-seq < 10) {
if (ctx.bounces[sc-7]+1 < 100)
ctx.bounces[sc-7]++;
else
ctx.bounces[sc-7] = 150;
}
}
}
static inline void decay_bounces(int sc)
{
if (sc-7U < 32 && ctx.bounces[sc-7])
ctx.bounces[sc-7]--;
}
static inline int is_bouncing(int sc)
{
return (sc-7U < 32 && ctx.bounces[sc-7] >= 100);
}
#endif
