remove __arch_prctl alias for arch_prctl
[musl] / src / malloc / malloc.c
1 #define _GNU_SOURCE
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"
11
12 #if defined(__GNUC__) && defined(__PIC__)
13 #define inline inline __attribute__((always_inline))
14 #endif
15
16 uintptr_t __brk(uintptr_t);
17 void *__mmap(void *, size_t, int, int, int, off_t);
18 int __munmap(void *, size_t);
19 void *__mremap(void *, size_t, size_t, int, ...);
20 int __madvise(void *, size_t, int);
21
22 struct chunk {
23         size_t psize, csize;
24         struct chunk *next, *prev;
25 };
26
27 struct bin {
28         int lock[2];
29         struct chunk *head;
30         struct chunk *tail;
31 };
32
33 static struct {
34         uintptr_t brk;
35         size_t *heap;
36         uint64_t binmap;
37         struct bin bins[64];
38         int brk_lock[2];
39         int free_lock[2];
40 } mal;
41
42
43 #define SIZE_ALIGN (4*sizeof(size_t))
44 #define SIZE_MASK (-SIZE_ALIGN)
45 #define OVERHEAD (2*sizeof(size_t))
46 #define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN)
47 #define DONTCARE 16
48 #define RECLAIM 163840
49
50 #define CHUNK_SIZE(c) ((c)->csize & -2)
51 #define CHUNK_PSIZE(c) ((c)->psize & -2)
52 #define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)))
53 #define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
54 #define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD)
55 #define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD)
56 #define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head))
57
58 #define C_INUSE  ((size_t)1)
59
60 #define IS_MMAPPED(c) !((c)->csize & (C_INUSE))
61
62
63 /* Synchronization tools */
64
65 static inline void lock(volatile int *lk)
66 {
67         if (!libc.threads_minus_1) return;
68         while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
69 }
70
71 static inline void unlock(volatile int *lk)
72 {
73         if (!libc.threads_minus_1) return;
74         a_store(lk, 0);
75         if (lk[1]) __wake(lk, 1, 1);
76 }
77
78 static inline void lock_bin(int i)
79 {
80         if (libc.threads_minus_1)
81                 lock(mal.bins[i].lock);
82         if (!mal.bins[i].head)
83                 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
84 }
85
86 static inline void unlock_bin(int i)
87 {
88         if (!libc.threads_minus_1) return;
89         unlock(mal.bins[i].lock);
90 }
91
92 static int first_set(uint64_t x)
93 {
94 #if 1
95         return a_ctz_64(x);
96 #else
97         static const char debruijn64[64] = {
98                 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
99                 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
100                 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
101                 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
102         };
103         static const char debruijn32[32] = {
104                 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
105                 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
106         };
107         if (sizeof(long) < 8) {
108                 uint32_t y = x;
109                 if (!y) {
110                         y = x>>32;
111                         return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
112                 }
113                 return debruijn32[(y&-y)*0x076be629 >> 27];
114         }
115         return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
116 #endif
117 }
118
119 static int bin_index(size_t x)
120 {
121         x = x / SIZE_ALIGN - 1;
122         if (x <= 32) return x;
123         if (x > 0x1c00) return 63;
124         return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496;
125 }
126
127 static int bin_index_up(size_t x)
128 {
129         x = x / SIZE_ALIGN - 1;
130         if (x <= 32) return x;
131         return ((union { float v; uint32_t r; }){(int)x}.r+0x1fffff>>21) - 496;
132 }
133
134 #if 0
135 void __dump_heap(int x)
136 {
137         struct chunk *c;
138         int i;
139         for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
140                 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
141                         c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
142                         c->csize & 15,
143                         NEXT_CHUNK(c)->psize & 15);
144         for (i=0; i<64; i++) {
145                 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
146                         fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
147                         if (!(mal.binmap & 1ULL<<i))
148                                 fprintf(stderr, "missing from binmap!\n");
149                 } else if (mal.binmap & 1ULL<<i)
150                         fprintf(stderr, "binmap wrongly contains %d!\n", i);
151         }
152 }
153 #endif
154
155 static struct chunk *expand_heap(size_t n)
156 {
157         struct chunk *w;
158         uintptr_t new;
159
160         lock(mal.brk_lock);
161
162         if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
163         new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
164         n = new - mal.brk;
165
166         if (__brk(new) != new) goto fail;
167
168         w = MEM_TO_CHUNK(new);
169         w->psize = n | C_INUSE;
170         w->csize = 0 | C_INUSE;
171
172         w = MEM_TO_CHUNK(mal.brk);
173         w->csize = n | C_INUSE;
174         mal.brk = new;
175         
176         unlock(mal.brk_lock);
177
178         return w;
179 fail:
180         unlock(mal.brk_lock);
181         return 0;
182 }
183
184 static int init_malloc(size_t n)
185 {
186         static int init, waiters;
187         int state;
188         struct chunk *c;
189
190         if (init == 2) return 0;
191
192         while ((state=a_swap(&init, 1)) == 1)
193                 __wait(&init, &waiters, 1, 1);
194         if (state) {
195                 a_store(&init, 2);
196                 return 0;
197         }
198
199         mal.brk = __brk(0) + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
200
201         c = expand_heap(n);
202
203         if (!c) {
204                 a_store(&init, 0);
205                 if (waiters) __wake(&init, 1, 1);
206                 return -1;
207         }
208
209         mal.heap = (void *)c;
210         c->psize = 0 | C_INUSE;
211         free(CHUNK_TO_MEM(c));
212
213         a_store(&init, 2);
214         if (waiters) __wake(&init, -1, 1);
215         return 1;
216 }
217
218 static int adjust_size(size_t *n)
219 {
220         /* Result of pointer difference must fit in ptrdiff_t. */
221         if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
222                 if (*n) {
223                         errno = ENOMEM;
224                         return -1;
225                 } else {
226                         *n = SIZE_ALIGN;
227                         return 0;
228                 }
229         }
230         *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
231         return 0;
232 }
233
234 static void unbin(struct chunk *c, int i)
235 {
236         if (c->prev == c->next)
237                 a_and_64(&mal.binmap, ~(1ULL<<i));
238         c->prev->next = c->next;
239         c->next->prev = c->prev;
240         c->csize |= C_INUSE;
241         NEXT_CHUNK(c)->psize |= C_INUSE;
242 }
243
244 static int alloc_fwd(struct chunk *c)
245 {
246         int i;
247         size_t k;
248         while (!((k=c->csize) & C_INUSE)) {
249                 i = bin_index(k);
250                 lock_bin(i);
251                 if (c->csize == k) {
252                         unbin(c, i);
253                         unlock_bin(i);
254                         return 1;
255                 }
256                 unlock_bin(i);
257         }
258         return 0;
259 }
260
261 static int alloc_rev(struct chunk *c)
262 {
263         int i;
264         size_t k;
265         while (!((k=c->psize) & C_INUSE)) {
266                 i = bin_index(k);
267                 lock_bin(i);
268                 if (c->psize == k) {
269                         unbin(PREV_CHUNK(c), i);
270                         unlock_bin(i);
271                         return 1;
272                 }
273                 unlock_bin(i);
274         }
275         return 0;
276 }
277
278
279 /* pretrim - trims a chunk _prior_ to removing it from its bin.
280  * Must be called with i as the ideal bin for size n, j the bin
281  * for the _free_ chunk self, and bin j locked. */
282 static int pretrim(struct chunk *self, size_t n, int i, int j)
283 {
284         size_t n1;
285         struct chunk *next, *split;
286
287         /* We cannot pretrim if it would require re-binning. */
288         if (j < 40) return 0;
289         if (j < i+3) {
290                 if (j != 63) return 0;
291                 n1 = CHUNK_SIZE(self);
292                 if (n1-n <= MMAP_THRESHOLD) return 0;
293         } else {
294                 n1 = CHUNK_SIZE(self);
295         }
296         if (bin_index(n1-n) != j) return 0;
297
298         next = NEXT_CHUNK(self);
299         split = (void *)((char *)self + n);
300
301         split->prev = self->prev;
302         split->next = self->next;
303         split->prev->next = split;
304         split->next->prev = split;
305         split->psize = n | C_INUSE;
306         split->csize = n1-n;
307         next->psize = n1-n;
308         self->csize = n | C_INUSE;
309         return 1;
310 }
311
312 static void trim(struct chunk *self, size_t n)
313 {
314         size_t n1 = CHUNK_SIZE(self);
315         struct chunk *next, *split;
316
317         if (n >= n1 - DONTCARE) return;
318
319         next = NEXT_CHUNK(self);
320         split = (void *)((char *)self + n);
321
322         split->psize = n | C_INUSE;
323         split->csize = n1-n | C_INUSE;
324         next->psize = n1-n | C_INUSE;
325         self->csize = n | C_INUSE;
326
327         free(CHUNK_TO_MEM(split));
328 }
329
330 void *malloc(size_t n)
331 {
332         struct chunk *c;
333         int i, j;
334
335         if (adjust_size(&n) < 0) return 0;
336
337         if (n > MMAP_THRESHOLD) {
338                 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
339                 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
340                         MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
341                 if (base == (void *)-1) return 0;
342                 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
343                 c->csize = len - (SIZE_ALIGN - OVERHEAD);
344                 c->psize = SIZE_ALIGN - OVERHEAD;
345                 return CHUNK_TO_MEM(c);
346         }
347
348         i = bin_index_up(n);
349         for (;;) {
350                 uint64_t mask = mal.binmap & -(1ULL<<i);
351                 if (!mask) {
352                         if (init_malloc(n) > 0) continue;
353                         c = expand_heap(n);
354                         if (!c) return 0;
355                         if (alloc_rev(c)) {
356                                 struct chunk *x = c;
357                                 c = PREV_CHUNK(c);
358                                 NEXT_CHUNK(x)->psize = c->csize =
359                                         x->csize + CHUNK_SIZE(c);
360                         }
361                         break;
362                 }
363                 j = first_set(mask);
364                 lock_bin(j);
365                 c = mal.bins[j].head;
366                 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
367                         if (!pretrim(c, n, i, j)) unbin(c, j);
368                         unlock_bin(j);
369                         break;
370                 }
371                 unlock_bin(j);
372         }
373
374         /* Now patch up in case we over-allocated */
375         trim(c, n);
376
377         return CHUNK_TO_MEM(c);
378 }
379
380 void *realloc(void *p, size_t n)
381 {
382         struct chunk *self, *next;
383         size_t n0, n1;
384         void *new;
385
386         if (!p) return malloc(n);
387
388         if (adjust_size(&n) < 0) return 0;
389
390         self = MEM_TO_CHUNK(p);
391         n1 = n0 = CHUNK_SIZE(self);
392
393         if (IS_MMAPPED(self)) {
394                 size_t extra = self->psize;
395                 char *base = (char *)self - extra;
396                 size_t oldlen = n0 + extra;
397                 size_t newlen = n + extra;
398                 /* Crash on realloc of freed chunk */
399                 if (extra & 1) a_crash();
400                 if (newlen < PAGE_SIZE && (new = malloc(n))) {
401                         memcpy(new, p, n-OVERHEAD);
402                         free(p);
403                         return new;
404                 }
405                 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
406                 if (oldlen == newlen) return p;
407                 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
408                 if (base == (void *)-1)
409                         return newlen < oldlen ? p : 0;
410                 self = (void *)(base + extra);
411                 self->csize = newlen - extra;
412                 return CHUNK_TO_MEM(self);
413         }
414
415         next = NEXT_CHUNK(self);
416
417         /* Merge adjacent chunks if we need more space. This is not
418          * a waste of time even if we fail to get enough space, because our
419          * subsequent call to free would otherwise have to do the merge. */
420         if (n > n1 && alloc_fwd(next)) {
421                 n1 += CHUNK_SIZE(next);
422                 next = NEXT_CHUNK(next);
423         }
424         /* FIXME: find what's wrong here and reenable it..? */
425         if (0 && n > n1 && alloc_rev(self)) {
426                 self = PREV_CHUNK(self);
427                 n1 += CHUNK_SIZE(self);
428         }
429         self->csize = n1 | C_INUSE;
430         next->psize = n1 | C_INUSE;
431
432         /* If we got enough space, split off the excess and return */
433         if (n <= n1) {
434                 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
435                 trim(self, n);
436                 return CHUNK_TO_MEM(self);
437         }
438
439         /* As a last resort, allocate a new chunk and copy to it. */
440         new = malloc(n-OVERHEAD);
441         if (!new) return 0;
442         memcpy(new, p, n0-OVERHEAD);
443         free(CHUNK_TO_MEM(self));
444         return new;
445 }
446
447 void free(void *p)
448 {
449         struct chunk *self = MEM_TO_CHUNK(p);
450         struct chunk *next;
451         size_t final_size, new_size, size;
452         int reclaim=0;
453         int i;
454
455         if (!p) return;
456
457         if (IS_MMAPPED(self)) {
458                 size_t extra = self->psize;
459                 char *base = (char *)self - extra;
460                 size_t len = CHUNK_SIZE(self) + extra;
461                 /* Crash on double free */
462                 if (extra & 1) a_crash();
463                 __munmap(base, len);
464                 return;
465         }
466
467         final_size = new_size = CHUNK_SIZE(self);
468         next = NEXT_CHUNK(self);
469
470         for (;;) {
471                 /* Replace middle of large chunks with fresh zero pages */
472                 if (reclaim && (self->psize & next->csize & C_INUSE)) {
473                         uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
474                         uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
475 #if 1
476                         __madvise((void *)a, b-a, MADV_DONTNEED);
477 #else
478                         __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
479                                 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
480 #endif
481                 }
482
483                 if (self->psize & next->csize & C_INUSE) {
484                         self->csize = final_size | C_INUSE;
485                         next->psize = final_size | C_INUSE;
486                         i = bin_index(final_size);
487                         lock_bin(i);
488                         lock(mal.free_lock);
489                         if (self->psize & next->csize & C_INUSE)
490                                 break;
491                         unlock(mal.free_lock);
492                         unlock_bin(i);
493                 }
494
495                 if (alloc_rev(self)) {
496                         self = PREV_CHUNK(self);
497                         size = CHUNK_SIZE(self);
498                         final_size += size;
499                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
500                                 reclaim = 1;
501                 }
502
503                 if (alloc_fwd(next)) {
504                         size = CHUNK_SIZE(next);
505                         final_size += size;
506                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
507                                 reclaim = 1;
508                         next = NEXT_CHUNK(next);
509                 }
510         }
511
512         self->csize = final_size;
513         next->psize = final_size;
514         unlock(mal.free_lock);
515
516         self->next = BIN_TO_CHUNK(i);
517         self->prev = mal.bins[i].tail;
518         self->next->prev = self;
519         self->prev->next = self;
520
521         if (!(mal.binmap & 1ULL<<i))
522                 a_or_64(&mal.binmap, 1ULL<<i);
523
524         unlock_bin(i);
525 }