| #define _BSD_SOURCE | |
| #include <stdlib.h> | |
| #include <sys/mman.h> | |
| #include "meta.h" | |
| struct mapinfo { | |
| void *base; | |
| size_t len; | |
| }; | |
| static struct mapinfo nontrivial_free(struct meta *, int); | |
| static struct mapinfo free_group(struct meta *g) | |
| { | |
| struct mapinfo mi = { 0 }; | |
| int sc = g->sizeclass; | |
| if (sc < 48) { | |
| ctx.usage_by_class[sc] -= g->last_idx+1; | |
| } | |
| if (g->maplen) { | |
| step_seq(); | |
| record_seq(sc); | |
| mi.base = g->mem; | |
| mi.len = g->maplen*4096UL; | |
| } else { | |
| void *p = g->mem; | |
| struct meta *m = get_meta(p); | |
| int idx = get_slot_index(p); | |
| g->mem->meta = 0; | |
| // not checking size/reserved here; it's intentionally invalid | |
| mi = nontrivial_free(m, idx); | |
| } | |
| free_meta(g); | |
| return mi; | |
| } | |
| static int okay_to_free(struct meta *g) | |
| { | |
| int sc = g->sizeclass; | |
| if (!g->freeable) return 0; | |
| // always free individual mmaps not suitable for reuse | |
| if (sc >= 48 || get_stride(g) < UNIT*size_classes[sc]) | |
| return 1; | |
| // always free groups allocated inside another group's slot | |
| // since recreating them should not be expensive and they | |
| // might be blocking freeing of a much larger group. | |
| if (!g->maplen) return 1; | |
| // if there is another non-full group, free this one to | |
| // consolidate future allocations, reduce fragmentation. | |
| if (g->next != g) return 1; | |
| // free any group in a size class that's not bouncing | |
| if (!is_bouncing(sc)) return 1; | |
| size_t cnt = g->last_idx+1; | |
| size_t usage = ctx.usage_by_class[sc]; | |
| // if usage is high enough that a larger count should be | |
| // used, free the low-count group so a new one will be made. | |
| if (9*cnt <= usage && cnt < 20) | |
| return 1; | |
| // otherwise, keep the last group in a bouncing class. | |
| return 0; | |
| } | |
| static struct mapinfo nontrivial_free(struct meta *g, int i) | |
| { | |
| uint32_t self = 1u<<i; | |
| int sc = g->sizeclass; | |
| uint32_t mask = g->freed_mask | g->avail_mask; | |
| if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) { | |
| // any multi-slot group is necessarily on an active list | |
| // here, but single-slot groups might or might not be. | |
| if (g->next) { | |
| assert(sc < 48); | |
| int activate_new = (ctx.active[sc]==g); | |
| dequeue(&ctx.active[sc], g); | |
| if (activate_new && ctx.active[sc]) | |
| activate_group(ctx.active[sc]); | |
| } | |
| return free_group(g); | |
| } else if (!mask) { | |
| assert(sc < 48); | |
| // might still be active if there were no allocations | |
| // after last available slot was taken. | |
| if (ctx.active[sc] != g) { | |
| queue(&ctx.active[sc], g); | |
| } | |
| } | |
| a_or(&g->freed_mask, self); | |
| return (struct mapinfo){ 0 }; | |
| } | |
| void free(void *p) | |
| { | |
| if (!p) return; | |
| struct meta *g = get_meta(p); | |
| int idx = get_slot_index(p); | |
| size_t stride = get_stride(g); | |
| unsigned char *start = g->mem->storage + stride*idx; | |
| unsigned char *end = start + stride - IB; | |
| get_nominal_size(p, end); | |
| uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1; | |
| ((unsigned char *)p)[-3] = 255; | |
| // invalidate offset to group header, and cycle offset of | |
| // used region within slot if current offset is zero. | |
| *(uint16_t *)((char *)p-2) = 0; | |
| // release any whole pages contained in the slot to be freed | |
| // unless it's a single-slot group that will be unmapped. | |
| if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) { | |
| unsigned char *base = start + (-(uintptr_t)start & (PGSZ-1)); | |
| size_t len = (end-base) & -PGSZ; | |
| if (len && USE_MADV_FREE) { | |
| int e = errno; | |
| madvise(base, len, MADV_FREE); | |
| errno = e; | |
| } | |
| } | |
| // atomic free without locking if this is neither first or last slot | |
| for (;;) { | |
| uint32_t freed = g->freed_mask; | |
| uint32_t avail = g->avail_mask; | |
| uint32_t mask = freed | avail; | |
| assert(!(mask&self)); | |
| if (!freed || mask+self==all) break; | |
| if (!MT) | |
| g->freed_mask = freed+self; | |
| else if (a_cas(&g->freed_mask, freed, freed+self)!=freed) | |
| continue; | |
| return; | |
| } | |
| wrlock(); | |
| struct mapinfo mi = nontrivial_free(g, idx); | |
| unlock(); | |
| if (mi.len) { | |
| int e = errno; | |
| munmap(mi.base, mi.len); | |
| errno = e; | |
| } | |
| } |