| #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 |