| 1 |
#ifndef MALLOC_META_H |
| 2 |
#define MALLOC_META_H |
| 3 |
|
| 4 |
#include <stdint.h> |
| 5 |
#include <errno.h> |
| 6 |
#include <limits.h> |
| 7 |
#include "glue.h" |
| 8 |
|
| 9 |
__attribute__((__visibility__("hidden"))) |
| 10 |
extern const uint16_t size_classes[]; |
| 11 |
|
| 12 |
#define MMAP_THRESHOLD 131052 |
| 13 |
|
| 14 |
#define UNIT 16 |
| 15 |
#define IB 4 |
| 16 |
|
| 17 |
struct group { |
| 18 |
struct meta *meta; |
| 19 |
unsigned char active_idx:5; |
| 20 |
char pad[UNIT - sizeof(struct meta *) - 1]; |
| 21 |
unsigned char storage[]; |
| 22 |
}; |
| 23 |
|
| 24 |
struct meta { |
| 25 |
struct meta *prev, *next; |
| 26 |
struct group *mem; |
| 27 |
volatile int avail_mask, freed_mask; |
| 28 |
uintptr_t last_idx:5; |
| 29 |
uintptr_t freeable:1; |
| 30 |
uintptr_t sizeclass:6; |
| 31 |
uintptr_t maplen:8*sizeof(uintptr_t)-12; |
| 32 |
}; |
| 33 |
|
| 34 |
struct meta_area { |
| 35 |
uint64_t check; |
| 36 |
struct meta_area *next; |
| 37 |
int nslots; |
| 38 |
struct meta slots[]; |
| 39 |
}; |
| 40 |
|
| 41 |
struct malloc_context { |
| 42 |
uint64_t secret; |
| 43 |
#ifndef PAGESIZE |
| 44 |
size_t pagesize; |
| 45 |
#endif |
| 46 |
int init_done; |
| 47 |
unsigned mmap_counter; |
| 48 |
struct meta *free_meta_head; |
| 49 |
struct meta *avail_meta; |
| 50 |
size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift; |
| 51 |
struct meta_area *meta_area_head, *meta_area_tail; |
| 52 |
unsigned char *avail_meta_areas; |
| 53 |
struct meta *active[48]; |
| 54 |
size_t usage_by_class[48]; |
| 55 |
uint8_t unmap_seq[32], bounces[32]; |
| 56 |
uint8_t seq; |
| 57 |
uintptr_t brk; |
| 58 |
}; |
| 59 |
|
| 60 |
__attribute__((__visibility__("hidden"))) |
| 61 |
extern struct malloc_context ctx; |
| 62 |
|
| 63 |
#ifdef PAGESIZE |
| 64 |
#define PGSZ PAGESIZE |
| 65 |
#else |
| 66 |
#define PGSZ ctx.pagesize |
| 67 |
#endif |
| 68 |
|
| 69 |
__attribute__((__visibility__("hidden"))) |
| 70 |
struct meta *alloc_meta(void); |
| 71 |
|
| 72 |
__attribute__((__visibility__("hidden"))) |
| 73 |
int is_allzero(void *); |
| 74 |
|
| 75 |
static inline void queue(struct meta **phead, struct meta *m) |
| 76 |
{ |
| 77 |
assert(!m->next); |
| 78 |
assert(!m->prev); |
| 79 |
if (*phead) { |
| 80 |
struct meta *head = *phead; |
| 81 |
m->next = head; |
| 82 |
m->prev = head->prev; |
| 83 |
m->next->prev = m->prev->next = m; |
| 84 |
} else { |
| 85 |
m->prev = m->next = m; |
| 86 |
*phead = m; |
| 87 |
} |
| 88 |
} |
| 89 |
|
| 90 |
static inline void dequeue(struct meta **phead, struct meta *m) |
| 91 |
{ |
| 92 |
if (m->next != m) { |
| 93 |
m->prev->next = m->next; |
| 94 |
m->next->prev = m->prev; |
| 95 |
if (*phead == m) *phead = m->next; |
| 96 |
} else { |
| 97 |
*phead = 0; |
| 98 |
} |
| 99 |
m->prev = m->next = 0; |
| 100 |
} |
| 101 |
|
| 102 |
static inline struct meta *dequeue_head(struct meta **phead) |
| 103 |
{ |
| 104 |
struct meta *m = *phead; |
| 105 |
if (m) dequeue(phead, m); |
| 106 |
return m; |
| 107 |
} |
| 108 |
|
| 109 |
static inline void free_meta(struct meta *m) |
| 110 |
{ |
| 111 |
*m = (struct meta){0}; |
| 112 |
queue(&ctx.free_meta_head, m); |
| 113 |
} |
| 114 |
|
| 115 |
static inline uint32_t activate_group(struct meta *m) |
| 116 |
{ |
| 117 |
assert(!m->avail_mask); |
| 118 |
uint32_t mask, act = (2u<<m->mem->active_idx)-1; |
| 119 |
do mask = m->freed_mask; |
| 120 |
while (a_cas(&m->freed_mask, mask, mask&~act)!=mask); |
| 121 |
return m->avail_mask = mask & act; |
| 122 |
} |
| 123 |
|
| 124 |
static inline int get_slot_index(const unsigned char *p) |
| 125 |
{ |
| 126 |
return p[-3] & 31; |
| 127 |
} |
| 128 |
|
| 129 |
static inline struct meta *get_meta(const unsigned char *p) |
| 130 |
{ |
| 131 |
assert(!((uintptr_t)p & 15)); |
| 132 |
int offset = *(const uint16_t *)(p - 2); |
| 133 |
int index = get_slot_index(p); |
| 134 |
if (p[-4]) { |
| 135 |
assert(!offset); |
| 136 |
offset = *(uint32_t *)(p - 8); |
| 137 |
assert(offset > 0xffff); |
| 138 |
} |
| 139 |
const struct group *base = (const void *)(p - UNIT*offset - UNIT); |
| 140 |
const struct meta *meta = base->meta; |
| 141 |
assert(meta->mem == base); |
| 142 |
assert(index <= meta->last_idx); |
| 143 |
assert(!(meta->avail_mask & (1u<<index))); |
| 144 |
assert(!(meta->freed_mask & (1u<<index))); |
| 145 |
const struct meta_area *area = (void *)((uintptr_t)meta & -4096); |
| 146 |
assert(area->check == ctx.secret); |
| 147 |
if (meta->sizeclass < 48) { |
| 148 |
assert(offset >= size_classes[meta->sizeclass]*index); |
| 149 |
assert(offset < size_classes[meta->sizeclass]*(index+1)); |
| 150 |
} else { |
| 151 |
assert(meta->sizeclass == 63); |
| 152 |
} |
| 153 |
if (meta->maplen) { |
| 154 |
assert(offset <= meta->maplen*4096UL/UNIT - 1); |
| 155 |
} |
| 156 |
return (struct meta *)meta; |
| 157 |
} |
| 158 |
|
| 159 |
static inline size_t get_nominal_size(const unsigned char *p, const unsigned char *end) |
| 160 |
{ |
| 161 |
size_t reserved = p[-3] >> 5; |
| 162 |
if (reserved >= 5) { |
| 163 |
assert(reserved == 5); |
| 164 |
reserved = *(const uint32_t *)(end-4); |
| 165 |
assert(reserved >= 5); |
| 166 |
assert(!end[-5]); |
| 167 |
} |
| 168 |
assert(reserved <= end-p); |
| 169 |
assert(!*(end-reserved)); |
| 170 |
// also check the slot's overflow byte |
| 171 |
assert(!*end); |
| 172 |
return end-reserved-p; |
| 173 |
} |
| 174 |
|
| 175 |
static inline size_t get_stride(const struct meta *g) |
| 176 |
{ |
| 177 |
if (!g->last_idx && g->maplen) { |
| 178 |
return g->maplen*4096UL - UNIT; |
| 179 |
} else { |
| 180 |
return UNIT*size_classes[g->sizeclass]; |
| 181 |
} |
| 182 |
} |
| 183 |
|
| 184 |
static inline void set_size(unsigned char *p, unsigned char *end, size_t n) |
| 185 |
{ |
| 186 |
int reserved = end-p-n; |
| 187 |
if (reserved) end[-reserved] = 0; |
| 188 |
if (reserved >= 5) { |
| 189 |
*(uint32_t *)(end-4) = reserved; |
| 190 |
end[-5] = 0; |
| 191 |
reserved = 5; |
| 192 |
} |
| 193 |
p[-3] = (p[-3]&31) + (reserved<<5); |
| 194 |
} |
| 195 |
|
| 196 |
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr) |
| 197 |
{ |
| 198 |
size_t stride = get_stride(g); |
| 199 |
size_t slack = (stride-IB-n)/UNIT; |
| 200 |
unsigned char *p = g->mem->storage + stride*idx; |
| 201 |
unsigned char *end = p+stride-IB; |
| 202 |
// cycle offset within slot to increase interval to address |
| 203 |
// reuse, facilitate trapping double-free. |
| 204 |
int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255; |
| 205 |
assert(!p[-4]); |
| 206 |
if (off > slack) { |
| 207 |
size_t m = slack; |
| 208 |
m |= m>>1; m |= m>>2; m |= m>>4; |
| 209 |
off &= m; |
| 210 |
if (off > slack) off -= slack+1; |
| 211 |
assert(off <= slack); |
| 212 |
} |
| 213 |
if (off) { |
| 214 |
// store offset in unused header at offset zero |
| 215 |
// if enframing at non-zero offset. |
| 216 |
*(uint16_t *)(p-2) = off; |
| 217 |
p[-3] = 7<<5; |
| 218 |
p += UNIT*off; |
| 219 |
// for nonzero offset there is no permanent check |
| 220 |
// byte, so make one. |
| 221 |
p[-4] = 0; |
| 222 |
} |
| 223 |
*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT; |
| 224 |
p[-3] = idx; |
| 225 |
set_size(p, end, n); |
| 226 |
return p; |
| 227 |
} |
| 228 |
|
| 229 |
static inline int size_to_class(size_t n) |
| 230 |
{ |
| 231 |
n = (n+IB-1)>>4; |
| 232 |
if (n<10) return n; |
| 233 |
n++; |
| 234 |
int i = (28-a_clz_32(n))*4 + 8; |
| 235 |
if (n>size_classes[i+1]) i+=2; |
| 236 |
if (n>size_classes[i]) i++; |
| 237 |
return i; |
| 238 |
} |
| 239 |
|
| 240 |
static inline int size_overflows(size_t n) |
| 241 |
{ |
| 242 |
if (n >= SIZE_MAX/2 - 4096) { |
| 243 |
errno = ENOMEM; |
| 244 |
return 1; |
| 245 |
} |
| 246 |
return 0; |
| 247 |
} |
| 248 |
|
| 249 |
static inline void step_seq(void) |
| 250 |
{ |
| 251 |
if (ctx.seq==255) { |
| 252 |
for (int i=0; i<32; i++) ctx.unmap_seq[i] = 0; |
| 253 |
ctx.seq = 1; |
| 254 |
} else { |
| 255 |
ctx.seq++; |
| 256 |
} |
| 257 |
} |
| 258 |
|
| 259 |
static inline void record_seq(int sc) |
| 260 |
{ |
| 261 |
if (sc-7U < 32) ctx.unmap_seq[sc-7] = ctx.seq; |
| 262 |
} |
| 263 |
|
| 264 |
static inline void account_bounce(int sc) |
| 265 |
{ |
| 266 |
if (sc-7U < 32) { |
| 267 |
int seq = ctx.unmap_seq[sc-7]; |
| 268 |
if (seq && ctx.seq-seq < 10) { |
| 269 |
if (ctx.bounces[sc-7]+1 < 100) |
| 270 |
ctx.bounces[sc-7]++; |
| 271 |
else |
| 272 |
ctx.bounces[sc-7] = 150; |
| 273 |
} |
| 274 |
} |
| 275 |
} |
| 276 |
|
| 277 |
static inline void decay_bounces(int sc) |
| 278 |
{ |
| 279 |
if (sc-7U < 32 && ctx.bounces[sc-7]) |
| 280 |
ctx.bounces[sc-7]--; |
| 281 |
} |
| 282 |
|
| 283 |
static inline int is_bouncing(int sc) |
| 284 |
{ |
| 285 |
return (sc-7U < 32 && ctx.bounces[sc-7] >= 100); |
| 286 |
} |
| 287 |
|
| 288 |
#endif |