nsz Git - musl/blob - src/malloc/mallocng/free.c

   1 #define _BSD_SOURCE
   2 #include <stdlib.h>
   3 #include <sys/mman.h>
   4
   5 #include "meta.h"
   6
   7 struct mapinfo {
   8         void *base;
   9         size_t len;
  10 };
  11
  12 static struct mapinfo nontrivial_free(struct meta *, int);
  13
  14 static struct mapinfo free_group(struct meta *g)
  15 {
  16         struct mapinfo mi = { 0 };
  17         int sc = g->sizeclass;
  18         if (sc < 48) {
  19                 ctx.usage_by_class[sc] -= g->last_idx+1;
  20         }
  21         if (g->maplen) {
  22                 step_seq();
  23                 record_seq(sc);
  24                 mi.base = g->mem;
  25                 mi.len = g->maplen*4096UL;
  26         } else {
  27                 void *p = g->mem;
  28                 struct meta *m = get_meta(p);
  29                 int idx = get_slot_index(p);
  30                 g->mem->meta = 0;
  31                 // not checking size/reserved here; it's intentionally invalid
  32                 mi = nontrivial_free(m, idx);
  33         }
  34         free_meta(g);
  35         return mi;
  36 }
  37
  38 static int okay_to_free(struct meta *g)
  39 {
  40         int sc = g->sizeclass;
  41
  42         if (!g->freeable) return 0;
  43
  44         // always free individual mmaps not suitable for reuse
  45         if (sc >= 48 || get_stride(g) < UNIT*size_classes[sc])
  46                 return 1;
  47
  48         // always free groups allocated inside another group's slot
  49         // since recreating them should not be expensive and they
  50         // might be blocking freeing of a much larger group.
  51         if (!g->maplen) return 1;
  52
  53         // if there is another non-full group, free this one to
  54         // consolidate future allocations, reduce fragmentation.
  55         if (g->next != g) return 1;
  56
  57         // free any group in a size class that's not bouncing
  58         if (!is_bouncing(sc)) return 1;
  59
  60         size_t cnt = g->last_idx+1;
  61         size_t usage = ctx.usage_by_class[sc];
  62
  63         // if usage is high enough that a larger count should be
  64         // used, free the low-count group so a new one will be made.
  65         if (9*cnt <= usage && cnt < 20)
  66                 return 1;
  67
  68         // otherwise, keep the last group in a bouncing class.
  69         return 0;
  70 }
  71
  72 static struct mapinfo nontrivial_free(struct meta *g, int i)
  73 {
  74         uint32_t self = 1u<<i;
  75         int sc = g->sizeclass;
  76         uint32_t mask = g->freed_mask | g->avail_mask;
  77
  78         if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) {
  79                 // any multi-slot group is necessarily on an active list
  80                 // here, but single-slot groups might or might not be.
  81                 if (g->next) {
  82                         assert(sc < 48);
  83                         int activate_new = (ctx.active[sc]==g);
  84                         dequeue(&ctx.active[sc], g);
  85                         if (activate_new && ctx.active[sc])
  86                                 activate_group(ctx.active[sc]);
  87                 }
  88                 return free_group(g);
  89         } else if (!mask) {
  90                 assert(sc < 48);
  91                 // might still be active if there were no allocations
  92                 // after last available slot was taken.
  93                 if (ctx.active[sc] != g) {
  94                         queue(&ctx.active[sc], g);
  95                 }
  96         }
  97         a_or(&g->freed_mask, self);
  98         return (struct mapinfo){ 0 };
  99 }
 100
 101 void free(void *p)
 102 {
 103         if (!p) return;
 104
 105         struct meta *g = get_meta(p);
 106         int idx = get_slot_index(p);
 107         size_t stride = get_stride(g);
 108         unsigned char *start = g->mem->storage + stride*idx;
 109         unsigned char *end = start + stride - IB;
 110         get_nominal_size(p, end);
 111         uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1;
 112         ((unsigned char *)p)[-3] = 255;
 113         // invalidate offset to group header, and cycle offset of
 114         // used region within slot if current offset is zero.
 115         *(uint16_t *)((char *)p-2) = 0;
 116
 117         // release any whole pages contained in the slot to be freed
 118         // unless it's a single-slot group that will be unmapped.
 119         if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) {
 120                 unsigned char *base = start + (-(uintptr_t)start & (PGSZ-1));
 121                 size_t len = (end-base) & -PGSZ;
 122                 if (len) madvise(base, len, MADV_FREE);
 123         }
 124
 125         // atomic free without locking if this is neither first or last slot
 126         for (;;) {
 127                 uint32_t freed = g->freed_mask;
 128                 uint32_t avail = g->avail_mask;
 129                 uint32_t mask = freed | avail;
 130                 assert(!(mask&self));
 131                 if (!freed || mask+self==all) break;
 132                 if (!MT)
 133                         g->freed_mask = freed+self;
 134                 else if (a_cas(&g->freed_mask, freed, freed+self)!=freed)
 135                         continue;
 136                 return;
 137         }
 138
 139         wrlock();
 140         struct mapinfo mi = nontrivial_free(g, idx);
 141         unlock();
 142         if (mi.len) munmap(mi.base, mi.len);
 143 }