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