Rich Felker | b052f13 | 2011-04-20 15:55:58 -0400 | [diff] [blame] | 1 | #define _GNU_SOURCE |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 2 | #include <stdlib.h> |
| 3 | #include <string.h> |
| 4 | #include <limits.h> |
| 5 | #include <stdint.h> |
| 6 | #include <errno.h> |
| 7 | #include <sys/mman.h> |
| 8 | #include "libc.h" |
| 9 | #include "atomic.h" |
| 10 | #include "pthread_impl.h" |
Rich Felker | 23389b1 | 2018-04-19 18:43:05 -0400 | [diff] [blame] | 11 | #include "malloc_impl.h" |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 12 | |
Rich Felker | afd209d | 2012-09-14 23:52:51 -0400 | [diff] [blame] | 13 | #if defined(__GNUC__) && defined(__PIC__) |
| 14 | #define inline inline __attribute__((always_inline)) |
| 15 | #endif |
| 16 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 17 | static struct { |
Rich Felker | 56fbaa3 | 2015-03-03 22:50:02 -0500 | [diff] [blame] | 18 | volatile uint64_t binmap; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 19 | struct bin bins[64]; |
Rich Felker | 56fbaa3 | 2015-03-03 22:50:02 -0500 | [diff] [blame] | 20 | volatile int free_lock[2]; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 21 | } mal; |
| 22 | |
Rich Felker | b4b1e10 | 2018-04-19 22:19:29 -0400 | [diff] [blame] | 23 | int __malloc_replaced; |
| 24 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 25 | /* Synchronization tools */ |
| 26 | |
Rich Felker | afd209d | 2012-09-14 23:52:51 -0400 | [diff] [blame] | 27 | static inline void lock(volatile int *lk) |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 28 | { |
Rich Felker | e803829 | 2013-09-20 02:00:27 -0400 | [diff] [blame] | 29 | if (libc.threads_minus_1) |
| 30 | while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 31 | } |
| 32 | |
Rich Felker | afd209d | 2012-09-14 23:52:51 -0400 | [diff] [blame] | 33 | static inline void unlock(volatile int *lk) |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 34 | { |
Rich Felker | e803829 | 2013-09-20 02:00:27 -0400 | [diff] [blame] | 35 | if (lk[0]) { |
| 36 | a_store(lk, 0); |
| 37 | if (lk[1]) __wake(lk, 1, 1); |
| 38 | } |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 39 | } |
| 40 | |
Rich Felker | afd209d | 2012-09-14 23:52:51 -0400 | [diff] [blame] | 41 | static inline void lock_bin(int i) |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 42 | { |
Rich Felker | e803829 | 2013-09-20 02:00:27 -0400 | [diff] [blame] | 43 | lock(mal.bins[i].lock); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 44 | if (!mal.bins[i].head) |
| 45 | mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i); |
| 46 | } |
| 47 | |
Rich Felker | afd209d | 2012-09-14 23:52:51 -0400 | [diff] [blame] | 48 | static inline void unlock_bin(int i) |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 49 | { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 50 | unlock(mal.bins[i].lock); |
| 51 | } |
| 52 | |
| 53 | static int first_set(uint64_t x) |
| 54 | { |
| 55 | #if 1 |
| 56 | return a_ctz_64(x); |
| 57 | #else |
| 58 | static const char debruijn64[64] = { |
| 59 | 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, |
| 60 | 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, |
| 61 | 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, |
| 62 | 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12 |
| 63 | }; |
| 64 | static const char debruijn32[32] = { |
| 65 | 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, |
| 66 | 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 |
| 67 | }; |
| 68 | if (sizeof(long) < 8) { |
| 69 | uint32_t y = x; |
| 70 | if (!y) { |
| 71 | y = x>>32; |
| 72 | return 32 + debruijn32[(y&-y)*0x076be629 >> 27]; |
| 73 | } |
| 74 | return debruijn32[(y&-y)*0x076be629 >> 27]; |
| 75 | } |
| 76 | return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58]; |
| 77 | #endif |
| 78 | } |
| 79 | |
Szabolcs Nagy | 61ff1af | 2016-12-17 15:03:24 +0100 | [diff] [blame] | 80 | static const unsigned char bin_tab[60] = { |
| 81 | 32,33,34,35,36,36,37,37,38,38,39,39, |
| 82 | 40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43, |
| 83 | 44,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45, |
| 84 | 46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47, |
| 85 | }; |
| 86 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 87 | static int bin_index(size_t x) |
| 88 | { |
| 89 | x = x / SIZE_ALIGN - 1; |
| 90 | if (x <= 32) return x; |
Szabolcs Nagy | 61ff1af | 2016-12-17 15:03:24 +0100 | [diff] [blame] | 91 | if (x < 512) return bin_tab[x/8-4]; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 92 | if (x > 0x1c00) return 63; |
Szabolcs Nagy | 61ff1af | 2016-12-17 15:03:24 +0100 | [diff] [blame] | 93 | return bin_tab[x/128-4] + 16; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | static int bin_index_up(size_t x) |
| 97 | { |
| 98 | x = x / SIZE_ALIGN - 1; |
| 99 | if (x <= 32) return x; |
Szabolcs Nagy | 61ff1af | 2016-12-17 15:03:24 +0100 | [diff] [blame] | 100 | x--; |
| 101 | if (x < 512) return bin_tab[x/8-4] + 1; |
| 102 | return bin_tab[x/128-4] + 17; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 103 | } |
| 104 | |
| 105 | #if 0 |
| 106 | void __dump_heap(int x) |
| 107 | { |
| 108 | struct chunk *c; |
| 109 | int i; |
| 110 | for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c)) |
| 111 | fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n", |
| 112 | c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)), |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 113 | c->csize & 15, |
| 114 | NEXT_CHUNK(c)->psize & 15); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 115 | for (i=0; i<64; i++) { |
| 116 | if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) { |
| 117 | fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head); |
| 118 | if (!(mal.binmap & 1ULL<<i)) |
| 119 | fprintf(stderr, "missing from binmap!\n"); |
| 120 | } else if (mal.binmap & 1ULL<<i) |
| 121 | fprintf(stderr, "binmap wrongly contains %d!\n", i); |
| 122 | } |
| 123 | } |
| 124 | #endif |
| 125 | |
| 126 | static struct chunk *expand_heap(size_t n) |
| 127 | { |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 128 | static int heap_lock[2]; |
| 129 | static void *end; |
| 130 | void *p; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 131 | struct chunk *w; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 132 | |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 133 | /* The argument n already accounts for the caller's chunk |
| 134 | * overhead needs, but if the heap can't be extended in-place, |
| 135 | * we need room for an extra zero-sized sentinel chunk. */ |
| 136 | n += SIZE_ALIGN; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 137 | |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 138 | lock(heap_lock); |
| 139 | |
| 140 | p = __expand_heap(&n); |
| 141 | if (!p) { |
| 142 | unlock(heap_lock); |
| 143 | return 0; |
Rich Felker | 7a81fe3 | 2015-03-04 09:29:39 -0500 | [diff] [blame] | 144 | } |
| 145 | |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 146 | /* If not just expanding existing space, we need to make a |
| 147 | * new sentinel chunk below the allocated space. */ |
| 148 | if (p != end) { |
| 149 | /* Valid/safe because of the prologue increment. */ |
Rich Felker | 5446303 | 2014-04-02 17:57:15 -0400 | [diff] [blame] | 150 | n -= SIZE_ALIGN; |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 151 | p = (char *)p + SIZE_ALIGN; |
| 152 | w = MEM_TO_CHUNK(p); |
Rich Felker | 5446303 | 2014-04-02 17:57:15 -0400 | [diff] [blame] | 153 | w->psize = 0 | C_INUSE; |
Rich Felker | 5446303 | 2014-04-02 17:57:15 -0400 | [diff] [blame] | 154 | } |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 155 | |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 156 | /* Record new heap end and fill in footer. */ |
| 157 | end = (char *)p + n; |
| 158 | w = MEM_TO_CHUNK(end); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 159 | w->psize = n | C_INUSE; |
| 160 | w->csize = 0 | C_INUSE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 161 | |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 162 | /* Fill in header, which may be new or may be replacing a |
| 163 | * zero-size sentinel header at the old end-of-heap. */ |
| 164 | w = MEM_TO_CHUNK(p); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 165 | w->csize = n | C_INUSE; |
Rich Felker | e3bc22f | 2015-06-14 01:59:02 +0000 | [diff] [blame] | 166 | |
| 167 | unlock(heap_lock); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 168 | |
| 169 | return w; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 170 | } |
| 171 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 172 | static int adjust_size(size_t *n) |
| 173 | { |
| 174 | /* Result of pointer difference must fit in ptrdiff_t. */ |
Rich Felker | 26031da | 2011-02-20 16:16:33 -0500 | [diff] [blame] | 175 | if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) { |
| 176 | if (*n) { |
| 177 | errno = ENOMEM; |
| 178 | return -1; |
| 179 | } else { |
| 180 | *n = SIZE_ALIGN; |
| 181 | return 0; |
| 182 | } |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 183 | } |
| 184 | *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK; |
| 185 | return 0; |
| 186 | } |
| 187 | |
| 188 | static void unbin(struct chunk *c, int i) |
| 189 | { |
| 190 | if (c->prev == c->next) |
| 191 | a_and_64(&mal.binmap, ~(1ULL<<i)); |
| 192 | c->prev->next = c->next; |
| 193 | c->next->prev = c->prev; |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 194 | c->csize |= C_INUSE; |
| 195 | NEXT_CHUNK(c)->psize |= C_INUSE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 196 | } |
| 197 | |
| 198 | static int alloc_fwd(struct chunk *c) |
| 199 | { |
| 200 | int i; |
| 201 | size_t k; |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 202 | while (!((k=c->csize) & C_INUSE)) { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 203 | i = bin_index(k); |
| 204 | lock_bin(i); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 205 | if (c->csize == k) { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 206 | unbin(c, i); |
| 207 | unlock_bin(i); |
| 208 | return 1; |
| 209 | } |
| 210 | unlock_bin(i); |
| 211 | } |
| 212 | return 0; |
| 213 | } |
| 214 | |
| 215 | static int alloc_rev(struct chunk *c) |
| 216 | { |
| 217 | int i; |
| 218 | size_t k; |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 219 | while (!((k=c->psize) & C_INUSE)) { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 220 | i = bin_index(k); |
| 221 | lock_bin(i); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 222 | if (c->psize == k) { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 223 | unbin(PREV_CHUNK(c), i); |
| 224 | unlock_bin(i); |
| 225 | return 1; |
| 226 | } |
| 227 | unlock_bin(i); |
| 228 | } |
| 229 | return 0; |
| 230 | } |
| 231 | |
| 232 | |
| 233 | /* pretrim - trims a chunk _prior_ to removing it from its bin. |
| 234 | * Must be called with i as the ideal bin for size n, j the bin |
| 235 | * for the _free_ chunk self, and bin j locked. */ |
| 236 | static int pretrim(struct chunk *self, size_t n, int i, int j) |
| 237 | { |
| 238 | size_t n1; |
| 239 | struct chunk *next, *split; |
| 240 | |
| 241 | /* We cannot pretrim if it would require re-binning. */ |
| 242 | if (j < 40) return 0; |
| 243 | if (j < i+3) { |
| 244 | if (j != 63) return 0; |
| 245 | n1 = CHUNK_SIZE(self); |
| 246 | if (n1-n <= MMAP_THRESHOLD) return 0; |
| 247 | } else { |
| 248 | n1 = CHUNK_SIZE(self); |
| 249 | } |
| 250 | if (bin_index(n1-n) != j) return 0; |
| 251 | |
| 252 | next = NEXT_CHUNK(self); |
| 253 | split = (void *)((char *)self + n); |
| 254 | |
| 255 | split->prev = self->prev; |
| 256 | split->next = self->next; |
| 257 | split->prev->next = split; |
| 258 | split->next->prev = split; |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 259 | split->psize = n | C_INUSE; |
| 260 | split->csize = n1-n; |
| 261 | next->psize = n1-n; |
| 262 | self->csize = n | C_INUSE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 263 | return 1; |
| 264 | } |
| 265 | |
| 266 | static void trim(struct chunk *self, size_t n) |
| 267 | { |
| 268 | size_t n1 = CHUNK_SIZE(self); |
| 269 | struct chunk *next, *split; |
| 270 | |
| 271 | if (n >= n1 - DONTCARE) return; |
| 272 | |
| 273 | next = NEXT_CHUNK(self); |
| 274 | split = (void *)((char *)self + n); |
| 275 | |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 276 | split->psize = n | C_INUSE; |
| 277 | split->csize = n1-n | C_INUSE; |
| 278 | next->psize = n1-n | C_INUSE; |
| 279 | self->csize = n | C_INUSE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 280 | |
Rich Felker | 7214179 | 2018-04-19 20:56:26 -0400 | [diff] [blame] | 281 | __bin_chunk(split); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 282 | } |
| 283 | |
| 284 | void *malloc(size_t n) |
| 285 | { |
| 286 | struct chunk *c; |
| 287 | int i, j; |
| 288 | |
Rich Felker | 26031da | 2011-02-20 16:16:33 -0500 | [diff] [blame] | 289 | if (adjust_size(&n) < 0) return 0; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 290 | |
| 291 | if (n > MMAP_THRESHOLD) { |
Rich Felker | b761bd1 | 2011-04-04 17:26:41 -0400 | [diff] [blame] | 292 | size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 293 | char *base = __mmap(0, len, PROT_READ|PROT_WRITE, |
| 294 | MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); |
| 295 | if (base == (void *)-1) return 0; |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 296 | c = (void *)(base + SIZE_ALIGN - OVERHEAD); |
| 297 | c->csize = len - (SIZE_ALIGN - OVERHEAD); |
| 298 | c->psize = SIZE_ALIGN - OVERHEAD; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 299 | return CHUNK_TO_MEM(c); |
| 300 | } |
| 301 | |
| 302 | i = bin_index_up(n); |
| 303 | for (;;) { |
| 304 | uint64_t mask = mal.binmap & -(1ULL<<i); |
| 305 | if (!mask) { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 306 | c = expand_heap(n); |
| 307 | if (!c) return 0; |
| 308 | if (alloc_rev(c)) { |
| 309 | struct chunk *x = c; |
| 310 | c = PREV_CHUNK(c); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 311 | NEXT_CHUNK(x)->psize = c->csize = |
| 312 | x->csize + CHUNK_SIZE(c); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 313 | } |
| 314 | break; |
| 315 | } |
| 316 | j = first_set(mask); |
| 317 | lock_bin(j); |
| 318 | c = mal.bins[j].head; |
Rich Felker | 064898c | 2015-03-04 10:48:00 -0500 | [diff] [blame] | 319 | if (c != BIN_TO_CHUNK(j)) { |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 320 | if (!pretrim(c, n, i, j)) unbin(c, j); |
| 321 | unlock_bin(j); |
| 322 | break; |
| 323 | } |
| 324 | unlock_bin(j); |
| 325 | } |
| 326 | |
| 327 | /* Now patch up in case we over-allocated */ |
| 328 | trim(c, n); |
| 329 | |
| 330 | return CHUNK_TO_MEM(c); |
| 331 | } |
| 332 | |
Alexander Monakov | 424eab2 | 2017-12-16 14:27:25 +0300 | [diff] [blame] | 333 | static size_t mal0_clear(char *p, size_t pagesz, size_t n) |
| 334 | { |
| 335 | #ifdef __GNUC__ |
| 336 | typedef uint64_t __attribute__((__may_alias__)) T; |
| 337 | #else |
| 338 | typedef unsigned char T; |
| 339 | #endif |
| 340 | char *pp = p + n; |
| 341 | size_t i = (uintptr_t)pp & (pagesz - 1); |
| 342 | for (;;) { |
| 343 | pp = memset(pp - i, 0, i); |
| 344 | if (pp - p < pagesz) return pp - p; |
| 345 | for (i = pagesz; i; i -= 2*sizeof(T), pp -= 2*sizeof(T)) |
| 346 | if (((T *)pp)[-1] | ((T *)pp)[-2]) |
| 347 | break; |
| 348 | } |
| 349 | } |
| 350 | |
Rich Felker | c9f415d | 2018-04-17 18:36:19 -0400 | [diff] [blame] | 351 | void *calloc(size_t m, size_t n) |
Rich Felker | ba81978 | 2015-06-22 18:50:09 +0000 | [diff] [blame] | 352 | { |
Rich Felker | c9f415d | 2018-04-17 18:36:19 -0400 | [diff] [blame] | 353 | if (n && m > (size_t)-1/n) { |
| 354 | errno = ENOMEM; |
| 355 | return 0; |
| 356 | } |
| 357 | n *= m; |
Rich Felker | ba81978 | 2015-06-22 18:50:09 +0000 | [diff] [blame] | 358 | void *p = malloc(n); |
Rich Felker | b4b1e10 | 2018-04-19 22:19:29 -0400 | [diff] [blame] | 359 | if (!p) return p; |
| 360 | if (!__malloc_replaced) { |
| 361 | if (IS_MMAPPED(MEM_TO_CHUNK(p))) |
| 362 | return p; |
| 363 | if (n >= PAGE_SIZE) |
| 364 | n = mal0_clear(p, PAGE_SIZE, n); |
| 365 | } |
Alexander Monakov | 424eab2 | 2017-12-16 14:27:25 +0300 | [diff] [blame] | 366 | return memset(p, 0, n); |
Rich Felker | ba81978 | 2015-06-22 18:50:09 +0000 | [diff] [blame] | 367 | } |
| 368 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 369 | void *realloc(void *p, size_t n) |
| 370 | { |
| 371 | struct chunk *self, *next; |
| 372 | size_t n0, n1; |
| 373 | void *new; |
| 374 | |
| 375 | if (!p) return malloc(n); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 376 | |
| 377 | if (adjust_size(&n) < 0) return 0; |
| 378 | |
| 379 | self = MEM_TO_CHUNK(p); |
| 380 | n1 = n0 = CHUNK_SIZE(self); |
| 381 | |
| 382 | if (IS_MMAPPED(self)) { |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 383 | size_t extra = self->psize; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 384 | char *base = (char *)self - extra; |
| 385 | size_t oldlen = n0 + extra; |
| 386 | size_t newlen = n + extra; |
Rich Felker | 0958200 | 2011-03-23 13:24:00 -0400 | [diff] [blame] | 387 | /* Crash on realloc of freed chunk */ |
Rich Felker | 1c8bead | 2011-08-23 09:43:45 -0400 | [diff] [blame] | 388 | if (extra & 1) a_crash(); |
Alexander Monakov | d889cc3 | 2018-04-16 20:54:35 +0300 | [diff] [blame] | 389 | if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) { |
| 390 | n0 = n; |
| 391 | goto copy_free_ret; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 392 | } |
| 393 | newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE; |
| 394 | if (oldlen == newlen) return p; |
| 395 | base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE); |
| 396 | if (base == (void *)-1) |
Rich Felker | 1c86c7f | 2017-06-15 12:54:40 -0400 | [diff] [blame] | 397 | goto copy_realloc; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 398 | self = (void *)(base + extra); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 399 | self->csize = newlen - extra; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 400 | return CHUNK_TO_MEM(self); |
| 401 | } |
| 402 | |
| 403 | next = NEXT_CHUNK(self); |
| 404 | |
Rich Felker | 8389520 | 2013-07-19 20:00:11 -0400 | [diff] [blame] | 405 | /* Crash on corrupted footer (likely from buffer overflow) */ |
| 406 | if (next->psize != self->csize) a_crash(); |
| 407 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 408 | /* Merge adjacent chunks if we need more space. This is not |
| 409 | * a waste of time even if we fail to get enough space, because our |
| 410 | * subsequent call to free would otherwise have to do the merge. */ |
| 411 | if (n > n1 && alloc_fwd(next)) { |
| 412 | n1 += CHUNK_SIZE(next); |
| 413 | next = NEXT_CHUNK(next); |
| 414 | } |
| 415 | /* FIXME: find what's wrong here and reenable it..? */ |
| 416 | if (0 && n > n1 && alloc_rev(self)) { |
| 417 | self = PREV_CHUNK(self); |
| 418 | n1 += CHUNK_SIZE(self); |
| 419 | } |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 420 | self->csize = n1 | C_INUSE; |
| 421 | next->psize = n1 | C_INUSE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 422 | |
| 423 | /* If we got enough space, split off the excess and return */ |
| 424 | if (n <= n1) { |
| 425 | //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD); |
| 426 | trim(self, n); |
| 427 | return CHUNK_TO_MEM(self); |
| 428 | } |
| 429 | |
Rich Felker | 1c86c7f | 2017-06-15 12:54:40 -0400 | [diff] [blame] | 430 | copy_realloc: |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 431 | /* As a last resort, allocate a new chunk and copy to it. */ |
| 432 | new = malloc(n-OVERHEAD); |
| 433 | if (!new) return 0; |
Alexander Monakov | d889cc3 | 2018-04-16 20:54:35 +0300 | [diff] [blame] | 434 | copy_free_ret: |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 435 | memcpy(new, p, n0-OVERHEAD); |
| 436 | free(CHUNK_TO_MEM(self)); |
| 437 | return new; |
| 438 | } |
| 439 | |
Rich Felker | 7214179 | 2018-04-19 20:56:26 -0400 | [diff] [blame] | 440 | void __bin_chunk(struct chunk *self) |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 441 | { |
Alexander Monakov | ce7ae11 | 2018-04-16 20:54:36 +0300 | [diff] [blame] | 442 | struct chunk *next = NEXT_CHUNK(self); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 443 | size_t final_size, new_size, size; |
| 444 | int reclaim=0; |
| 445 | int i; |
| 446 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 447 | final_size = new_size = CHUNK_SIZE(self); |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 448 | |
Rich Felker | 8389520 | 2013-07-19 20:00:11 -0400 | [diff] [blame] | 449 | /* Crash on corrupted footer (likely from buffer overflow) */ |
| 450 | if (next->psize != self->csize) a_crash(); |
| 451 | |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 452 | for (;;) { |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 453 | if (self->psize & next->csize & C_INUSE) { |
| 454 | self->csize = final_size | C_INUSE; |
| 455 | next->psize = final_size | C_INUSE; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 456 | i = bin_index(final_size); |
| 457 | lock_bin(i); |
| 458 | lock(mal.free_lock); |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 459 | if (self->psize & next->csize & C_INUSE) |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 460 | break; |
| 461 | unlock(mal.free_lock); |
| 462 | unlock_bin(i); |
| 463 | } |
| 464 | |
| 465 | if (alloc_rev(self)) { |
| 466 | self = PREV_CHUNK(self); |
| 467 | size = CHUNK_SIZE(self); |
| 468 | final_size += size; |
| 469 | if (new_size+size > RECLAIM && (new_size+size^size) > size) |
| 470 | reclaim = 1; |
| 471 | } |
| 472 | |
| 473 | if (alloc_fwd(next)) { |
| 474 | size = CHUNK_SIZE(next); |
| 475 | final_size += size; |
| 476 | if (new_size+size > RECLAIM && (new_size+size^size) > size) |
| 477 | reclaim = 1; |
| 478 | next = NEXT_CHUNK(next); |
| 479 | } |
| 480 | } |
| 481 | |
Rich Felker | c376162 | 2015-08-07 19:19:49 +0000 | [diff] [blame] | 482 | if (!(mal.binmap & 1ULL<<i)) |
| 483 | a_or_64(&mal.binmap, 1ULL<<i); |
| 484 | |
Rich Felker | 5d0965c | 2011-06-26 16:12:43 -0400 | [diff] [blame] | 485 | self->csize = final_size; |
| 486 | next->psize = final_size; |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 487 | unlock(mal.free_lock); |
| 488 | |
| 489 | self->next = BIN_TO_CHUNK(i); |
| 490 | self->prev = mal.bins[i].tail; |
| 491 | self->next->prev = self; |
| 492 | self->prev->next = self; |
| 493 | |
Rich Felker | c376162 | 2015-08-07 19:19:49 +0000 | [diff] [blame] | 494 | /* Replace middle of large chunks with fresh zero pages */ |
| 495 | if (reclaim) { |
| 496 | uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE; |
| 497 | uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE; |
| 498 | #if 1 |
| 499 | __madvise((void *)a, b-a, MADV_DONTNEED); |
| 500 | #else |
| 501 | __mmap((void *)a, b-a, PROT_READ|PROT_WRITE, |
| 502 | MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0); |
| 503 | #endif |
| 504 | } |
Rich Felker | 0b44a03 | 2011-02-12 00:22:29 -0500 | [diff] [blame] | 505 | |
| 506 | unlock_bin(i); |
| 507 | } |
Alexander Monakov | ce7ae11 | 2018-04-16 20:54:36 +0300 | [diff] [blame] | 508 | |
| 509 | static void unmap_chunk(struct chunk *self) |
| 510 | { |
| 511 | size_t extra = self->psize; |
| 512 | char *base = (char *)self - extra; |
| 513 | size_t len = CHUNK_SIZE(self) + extra; |
| 514 | /* Crash on double free */ |
| 515 | if (extra & 1) a_crash(); |
| 516 | __munmap(base, len); |
| 517 | } |
| 518 | |
| 519 | void free(void *p) |
| 520 | { |
| 521 | if (!p) return; |
| 522 | |
| 523 | struct chunk *self = MEM_TO_CHUNK(p); |
| 524 | |
| 525 | if (IS_MMAPPED(self)) |
| 526 | unmap_chunk(self); |
| 527 | else |
Rich Felker | 7214179 | 2018-04-19 20:56:26 -0400 | [diff] [blame] | 528 | __bin_chunk(self); |
Alexander Monakov | ce7ae11 | 2018-04-16 20:54:36 +0300 | [diff] [blame] | 529 | } |
| 530 | |
| 531 | void __malloc_donate(char *start, char *end) |
| 532 | { |
| 533 | size_t align_start_up = (SIZE_ALIGN-1) & (-(uintptr_t)start - OVERHEAD); |
| 534 | size_t align_end_down = (SIZE_ALIGN-1) & (uintptr_t)end; |
| 535 | |
Rich Felker | 14032c3 | 2018-04-17 15:18:49 -0400 | [diff] [blame] | 536 | /* Getting past this condition ensures that the padding for alignment |
| 537 | * and header overhead will not overflow and will leave a nonzero |
| 538 | * multiple of SIZE_ALIGN bytes between start and end. */ |
Alexander Monakov | ce7ae11 | 2018-04-16 20:54:36 +0300 | [diff] [blame] | 539 | if (end - start <= OVERHEAD + align_start_up + align_end_down) |
| 540 | return; |
| 541 | start += align_start_up + OVERHEAD; |
| 542 | end -= align_end_down; |
| 543 | |
| 544 | struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end); |
| 545 | c->psize = n->csize = C_INUSE; |
| 546 | c->csize = n->psize = C_INUSE | (end-start); |
Rich Felker | 7214179 | 2018-04-19 20:56:26 -0400 | [diff] [blame] | 547 | __bin_chunk(c); |
Alexander Monakov | ce7ae11 | 2018-04-16 20:54:36 +0300 | [diff] [blame] | 548 | } |