1 /* $OpenBSD: malloc.c,v 1.35 2022/01/18 21:59:29 deraadt Exp $ */
2 /*
3 * Copyright (c) 2008, 2010, 2011 Otto Moerbeek <otto@drijf.net>
4 * Copyright (c) 2012 Matthew Dempsky <matthew@openbsd.org>
5 * Copyright (c) 2008 Damien Miller <djm@openbsd.org>
6 * Copyright (c) 2000 Poul-Henning Kamp <phk@FreeBSD.org>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21 /*
22 * If we meet some day, and you think this stuff is worth it, you
23 * can buy me a beer in return. Poul-Henning Kamp
24 */
25
26 #include <sys/types.h>
27 #include <sys/queue.h>
28 #include <sys/time.h>
29 #include <sys/mman.h>
30 #include <stdint.h>
31
32 #include "syscall.h"
33 #include "util.h"
34 #include "resolve.h" /* for lock_cb */
35
36 #define MALLOC_PAGESHIFT _MAX_PAGE_SHIFT
37 #define MALLOC_MINSHIFT 4
38 #define MALLOC_MAXSHIFT (MALLOC_PAGESHIFT - 1)
39 #define MALLOC_PAGESIZE (1UL << MALLOC_PAGESHIFT)
40 #define MALLOC_MINSIZE (1UL << MALLOC_MINSHIFT)
41 #define MALLOC_PAGEMASK (MALLOC_PAGESIZE - 1)
42 #define MASK_POINTER(p) ((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK))
43
44 #define MALLOC_MAXCHUNK (1 << MALLOC_MAXSHIFT)
45 #define MALLOC_MAXCACHE 256
46 #define MALLOC_DELAYED_CHUNK_MASK 15
47 #define MALLOC_INITIAL_REGIONS (MALLOC_PAGESIZE / sizeof(struct region_info))
48 #define MALLOC_DEFAULT_CACHE 64
49 #define MALLOC_CHUNK_LISTS 4
50 #define CHUNK_CHECK_LENGTH 32
51
52 /*
53 * We move allocations between half a page and a whole page towards the end,
54 * subject to alignment constraints. This is the extra headroom we allow.
55 * Set to zero to be the most strict.
56 */
57 #define MALLOC_LEEWAY 0
58
59 #define PAGEROUND(x) (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK)
60
61 /*
62 * What to use for Junk. This is the byte value we use to fill with
63 * when the 'J' option is enabled. Use SOME_JUNK right after alloc,
64 * and SOME_FREEJUNK right before free.
65 */
66 #define SOME_JUNK 0xdb /* deadbeef */
67 #define SOME_FREEJUNK 0xdf /* dead, free */
68
69 #define MMAP(sz) _dl_mmap(NULL, (size_t)(sz), PROT_READ | PROT_WRITE, \
70 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0)
71
72 #define MMAPNONE(sz) _dl_mmap(NULL, (size_t)(sz), PROT_NONE, \
73 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0)
74
75 #define MMAP_ERROR(p) (_dl_mmap_error(p) ? MAP_FAILED : (p))
76
77 struct region_info {
78 void *p; /* page; low bits used to mark chunks */
79 uintptr_t size; /* size for pages, or chunk_info pointer */
80 };
81
82 LIST_HEAD(chunk_head, chunk_info);
83
84 struct dir_info {
85 u_int32_t canary1;
86 int active; /* status of malloc */
87 struct region_info *r; /* region slots */
88 size_t regions_total; /* number of region slots */
89 size_t regions_free; /* number of free slots */
90 /* lists of free chunk info structs */
91 struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1];
92 /* lists of chunks with free slots */
93 struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS];
94 size_t free_regions_size; /* free pages cached */
95 /* free pages cache */
96 u_int rotor;
97 struct region_info free_regions[MALLOC_MAXCACHE];
98 /* delayed free chunk slots */
99 void *delayed_chunks[MALLOC_DELAYED_CHUNK_MASK + 1];
100 size_t rbytesused; /* random bytes used */
101 char *func; /* current function */
102 u_char rbytes[256]; /* random bytes */
103 u_int32_t canary2;
104 };
105 #define DIR_INFO_RSZ ((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \
106 ~MALLOC_PAGEMASK)
107
108 /*
109 * This structure describes a page worth of chunks.
110 *
111 * How many bits per u_short in the bitmap
112 */
113 #define MALLOC_BITS (NBBY * sizeof(u_short))
114 struct chunk_info {
115 LIST_ENTRY(chunk_info) entries;
116 void *page; /* pointer to the page */
117 u_short canary;
118 u_short size; /* size of this page's chunks */
119 u_short shift; /* how far to shift for this size */
120 u_short free; /* how many free chunks */
121 u_short total; /* how many chunk */
122 u_short offset; /* requested size table offset */
123 /* which chunks are free */
124 u_short bits[1];
125 };
126
127 #define MALLOC_FREEUNMAP 0
128 #define MALLOC_JUNK 1
129 #define CHUNK_CANARIES 1
130 #define MALLOC_GUARD ((size_t)MALLOC_PAGESIZE)
131 #define MALLOC_CACHE MALLOC_DEFAULT_CACHE
132
133 struct malloc_readonly {
134 struct dir_info *g_pool; /* Main bookkeeping information */
135 u_int32_t malloc_canary; /* Matched against ones in g_pool */
136 };
137
138 /*
139 * malloc configuration
140 */
141 static struct malloc_readonly mopts __relro;
142
143 #define g_pool mopts.g_pool
144
145 static u_char getrbyte(struct dir_info *d);
146
147 /* low bits of r->p determine size: 0 means >= page size and p->size holding
148 * real size, otherwise r->size is a shift count, or 1 for malloc(0)
149 */
150 #define REALSIZE(sz, r) \
151 (sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \
152 (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1))))
153
154 static inline size_t
hash(void * p)155 hash(void *p)
156 {
157 size_t sum;
158 uintptr_t u;
159
160 u = (uintptr_t)p >> MALLOC_PAGESHIFT;
161 sum = u;
162 sum = (sum << 7) - sum + (u >> 16);
163 #ifdef __LP64__
164 sum = (sum << 7) - sum + (u >> 32);
165 sum = (sum << 7) - sum + (u >> 48);
166 #endif
167 return sum;
168 }
169
170 static __dead void
wrterror(char * msg)171 wrterror(char *msg)
172 {
173 if (g_pool != NULL && g_pool->func != NULL)
174 _dl_die("%s error: %s", g_pool->func, msg);
175 else
176 _dl_die("%s", msg);
177 }
178
179 static void
rbytes_init(struct dir_info * d)180 rbytes_init(struct dir_info *d)
181 {
182 _dl_arc4randombuf(d->rbytes, sizeof(d->rbytes));
183 /* add 1 to account for using d->rbytes[0] */
184 d->rbytesused = 1 + d->rbytes[0] % (sizeof(d->rbytes) / 2);
185 }
186
187 static inline u_char
getrbyte(struct dir_info * d)188 getrbyte(struct dir_info *d)
189 {
190 u_char x;
191
192 if (d->rbytesused >= sizeof(d->rbytes))
193 rbytes_init(d);
194 x = d->rbytes[d->rbytesused++];
195 return x;
196 }
197
198 /*
199 * Initialize the malloc subsystem before relro processing.
200 */
201 void
_dl_malloc_init(void)202 _dl_malloc_init(void)
203 {
204 char *p;
205 int i, j;
206 size_t d_avail, regioninfo_size, tmp;
207 struct dir_info *d;
208
209 do {
210 _dl_arc4randombuf(&mopts.malloc_canary,
211 sizeof(mopts.malloc_canary));
212 } while (mopts.malloc_canary == 0);
213
214 /*
215 * Allocate dir_info with a guard page on either side. Also
216 * randomise offset inside the page at which the dir_info
217 * lies (subject to alignment by 1 << MALLOC_MINSHIFT)
218 */
219 p = MMAPNONE(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2));
220 p = MMAP_ERROR(p);
221 if (p == MAP_FAILED)
222 wrterror("malloc init mmap failed");
223 _dl_mprotect(p + MALLOC_PAGESIZE, DIR_INFO_RSZ, PROT_READ | PROT_WRITE);
224 d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT;
225
226 _dl_arc4randombuf(&tmp, sizeof(tmp));
227 d = (struct dir_info *)(p + MALLOC_PAGESIZE +
228 ((tmp % d_avail) << MALLOC_MINSHIFT)); /* not uniform */
229
230 rbytes_init(d);
231 d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS;
232 regioninfo_size = d->regions_total * sizeof(struct region_info);
233 d->r = MMAP(regioninfo_size);
234 d->r = MMAP_ERROR(d->r);
235 if (d->r == MAP_FAILED)
236 wrterror("malloc init mmap failed");
237 for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
238 LIST_INIT(&d->chunk_info_list[i]);
239 for (j = 0; j < MALLOC_CHUNK_LISTS; j++)
240 LIST_INIT(&d->chunk_dir[i][j]);
241 }
242 d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
243 d->canary2 = ~d->canary1;
244
245 g_pool = d;
246 }
247
248 static int
omalloc_grow(struct dir_info * d)249 omalloc_grow(struct dir_info *d)
250 {
251 size_t newtotal;
252 size_t newsize;
253 size_t mask;
254 size_t i;
255 struct region_info *p;
256
257 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2)
258 return 1;
259
260 newtotal = d->regions_total * 2;
261 newsize = newtotal * sizeof(struct region_info);
262 mask = newtotal - 1;
263
264 p = MMAP(newsize);
265 p = MMAP_ERROR(p);
266 if (p == MAP_FAILED)
267 return 1;
268
269 for (i = 0; i < d->regions_total; i++) {
270 void *q = d->r[i].p;
271 if (q != NULL) {
272 size_t index = hash(q) & mask;
273 while (p[index].p != NULL) {
274 index = (index - 1) & mask;
275 }
276 p[index] = d->r[i];
277 }
278 }
279 /* avoid pages containing meta info to end up in cache */
280 if (_dl_munmap(d->r, d->regions_total * sizeof(struct region_info)))
281 wrterror("munmap");
282 d->regions_free = d->regions_free + d->regions_total;
283 d->regions_total = newtotal;
284 d->r = p;
285 return 0;
286 }
287
288 /*
289 * The hashtable uses the assumption that p is never NULL. This holds since
290 * non-MAP_FIXED mappings with hint 0 start at BRKSIZ.
291 */
292 static int
insert(struct dir_info * d,void * p,size_t sz)293 insert(struct dir_info *d, void *p, size_t sz)
294 {
295 size_t index;
296 size_t mask;
297 void *q;
298
299 if (d->regions_free * 4 < d->regions_total) {
300 if (omalloc_grow(d))
301 return 1;
302 }
303 mask = d->regions_total - 1;
304 index = hash(p) & mask;
305 q = d->r[index].p;
306 while (q != NULL) {
307 index = (index - 1) & mask;
308 q = d->r[index].p;
309 }
310 d->r[index].p = p;
311 d->r[index].size = sz;
312 d->regions_free--;
313 return 0;
314 }
315
316 static struct region_info *
find(struct dir_info * d,void * p)317 find(struct dir_info *d, void *p)
318 {
319 size_t index;
320 size_t mask = d->regions_total - 1;
321 void *q, *r;
322
323 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
324 d->canary1 != ~d->canary2)
325 wrterror("internal struct corrupt");
326 p = MASK_POINTER(p);
327 index = hash(p) & mask;
328 r = d->r[index].p;
329 q = MASK_POINTER(r);
330 while (q != p && r != NULL) {
331 index = (index - 1) & mask;
332 r = d->r[index].p;
333 q = MASK_POINTER(r);
334 }
335 return (q == p && r != NULL) ? &d->r[index] : NULL;
336 }
337
338 static void
delete(struct dir_info * d,struct region_info * ri)339 delete(struct dir_info *d, struct region_info *ri)
340 {
341 /* algorithm R, Knuth Vol III section 6.4 */
342 size_t mask = d->regions_total - 1;
343 size_t i, j, r;
344
345 if (d->regions_total & (d->regions_total - 1))
346 wrterror("regions_total not 2^x");
347 d->regions_free++;
348
349 i = ri - d->r;
350 for (;;) {
351 d->r[i].p = NULL;
352 d->r[i].size = 0;
353 j = i;
354 for (;;) {
355 i = (i - 1) & mask;
356 if (d->r[i].p == NULL)
357 return;
358 r = hash(d->r[i].p) & mask;
359 if ((i <= r && r < j) || (r < j && j < i) ||
360 (j < i && i <= r))
361 continue;
362 d->r[j] = d->r[i];
363 break;
364 }
365
366 }
367 }
368
369 /*
370 * Cache maintenance. We keep at most malloc_cache pages cached.
371 * If the cache is becoming full, unmap pages in the cache for real,
372 * and then add the region to the cache
373 * Opposed to the regular region data structure, the sizes in the
374 * cache are in MALLOC_PAGESIZE units.
375 */
376 static void
unmap(struct dir_info * d,void * p,size_t sz,int junk)377 unmap(struct dir_info *d, void *p, size_t sz, int junk)
378 {
379 size_t psz = sz >> MALLOC_PAGESHIFT;
380 size_t rsz;
381 struct region_info *r;
382 u_int i, offset, mask;
383
384 if (sz != PAGEROUND(sz))
385 wrterror("munmap round");
386
387 rsz = MALLOC_CACHE - d->free_regions_size;
388
389 if (psz > MALLOC_CACHE) {
390 if (_dl_munmap(p, sz))
391 wrterror("munmap");
392 return;
393 }
394 offset = getrbyte(d);
395 mask = MALLOC_CACHE - 1;
396 if (psz > rsz) {
397 size_t tounmap = psz - rsz;
398 for (i = 0; ; i++) {
399 r = &d->free_regions[(i + offset) & mask];
400 if (r->p != NULL) {
401 rsz = r->size << MALLOC_PAGESHIFT;
402 if (_dl_munmap(r->p, rsz))
403 wrterror("munmap");
404 r->p = NULL;
405 if (tounmap > r->size)
406 tounmap -= r->size;
407 else
408 tounmap = 0;
409 d->free_regions_size -= r->size;
410 if (tounmap == 0) {
411 offset = i;
412 break;
413 }
414 }
415 }
416 }
417 for (i = 0; ; i++) {
418 r = &d->free_regions[(i + offset) & mask];
419 if (r->p == NULL) {
420 if (junk && !MALLOC_FREEUNMAP) {
421 size_t amt = junk == 1 ? MALLOC_MAXCHUNK : sz;
422 _dl_memset(p, SOME_FREEJUNK, amt);
423 }
424 if (MALLOC_FREEUNMAP)
425 _dl_mprotect(p, sz, PROT_NONE);
426 r->p = p;
427 r->size = psz;
428 d->free_regions_size += psz;
429 break;
430 }
431 }
432 if (d->free_regions_size > MALLOC_CACHE)
433 wrterror("malloc cache overflow");
434 }
435
436 static void *
map(struct dir_info * d,size_t sz,int zero_fill)437 map(struct dir_info *d, size_t sz, int zero_fill)
438 {
439 size_t psz = sz >> MALLOC_PAGESHIFT;
440 struct region_info *r, *big = NULL;
441 u_int i;
442 void *p;
443
444 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
445 d->canary1 != ~d->canary2)
446 wrterror("internal struct corrupt");
447 if (sz != PAGEROUND(sz)) {
448 wrterror("map round");
449 return MAP_FAILED;
450 }
451 if (psz > d->free_regions_size) {
452 p = MMAP(sz);
453 p = MMAP_ERROR(p);
454 /* zero fill not needed */
455 return p;
456 }
457 for (i = 0; i < MALLOC_CACHE; i++) {
458 r = &d->free_regions[(i + d->rotor) & (MALLOC_CACHE - 1)];
459 if (r->p != NULL) {
460 if (r->size == psz) {
461 p = r->p;
462 if (MALLOC_FREEUNMAP)
463 _dl_mprotect(p, sz, PROT_READ | PROT_WRITE);
464 r->p = NULL;
465 d->free_regions_size -= psz;
466 if (zero_fill)
467 _dl_memset(p, 0, sz);
468 else if (MALLOC_JUNK == 2 &&
469 MALLOC_FREEUNMAP)
470 _dl_memset(p, SOME_FREEJUNK, sz);
471 d->rotor += i + 1;
472 return p;
473 } else if (r->size > psz)
474 big = r;
475 }
476 }
477 if (big != NULL) {
478 r = big;
479 p = (char *)r->p + ((r->size - psz) << MALLOC_PAGESHIFT);
480 if (MALLOC_FREEUNMAP)
481 _dl_mprotect(p, sz, PROT_READ | PROT_WRITE);
482 r->size -= psz;
483 d->free_regions_size -= psz;
484 if (zero_fill)
485 _dl_memset(p, 0, sz);
486 else if (MALLOC_JUNK == 2 && MALLOC_FREEUNMAP)
487 _dl_memset(p, SOME_FREEJUNK, sz);
488 return p;
489 }
490 p = MMAP(sz);
491 p = MMAP_ERROR(p);
492 if (d->free_regions_size > MALLOC_CACHE)
493 wrterror("malloc cache");
494 /* zero fill not needed */
495 return p;
496 }
497
498 static void
init_chunk_info(struct dir_info * d,struct chunk_info * p,int bits)499 init_chunk_info(struct dir_info *d, struct chunk_info *p, int bits)
500 {
501 int i;
502
503 if (bits == 0) {
504 p->shift = MALLOC_MINSHIFT;
505 p->total = p->free = MALLOC_PAGESIZE >> p->shift;
506 p->size = 0;
507 p->offset = 0xdead;
508 } else {
509 p->shift = bits;
510 p->total = p->free = MALLOC_PAGESIZE >> p->shift;
511 p->size = 1U << bits;
512 p->offset = howmany(p->total, MALLOC_BITS);
513 }
514 p->canary = (u_short)d->canary1;
515
516 /* set all valid bits in the bitmap */
517 i = p->total - 1;
518 _dl_memset(p->bits, 0xff, sizeof(p->bits[0]) * (i / MALLOC_BITS));
519 p->bits[i / MALLOC_BITS] = (2U << (i % MALLOC_BITS)) - 1;
520 }
521
522 static struct chunk_info *
alloc_chunk_info(struct dir_info * d,int bits)523 alloc_chunk_info(struct dir_info *d, int bits)
524 {
525 struct chunk_info *p;
526
527 if (LIST_EMPTY(&d->chunk_info_list[bits])) {
528 size_t size, count, i;
529 char *q;
530
531 if (bits == 0)
532 count = MALLOC_PAGESIZE / MALLOC_MINSIZE;
533 else
534 count = MALLOC_PAGESIZE >> bits;
535
536 size = howmany(count, MALLOC_BITS);
537 size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short);
538 if (CHUNK_CANARIES)
539 size += count * sizeof(u_short);
540 size = _ALIGN(size);
541
542 q = MMAP(MALLOC_PAGESIZE);
543 q = MMAP_ERROR(q);
544 if (q == MAP_FAILED)
545 return NULL;
546 count = MALLOC_PAGESIZE / size;
547
548 for (i = 0; i < count; i++, q += size)
549 LIST_INSERT_HEAD(&d->chunk_info_list[bits],
550 (struct chunk_info *)q, entries);
551 }
552 p = LIST_FIRST(&d->chunk_info_list[bits]);
553 LIST_REMOVE(p, entries);
554 if (p->shift == 0)
555 init_chunk_info(d, p, bits);
556 return p;
557 }
558
559 /*
560 * Allocate a page of chunks
561 */
562 static struct chunk_info *
omalloc_make_chunks(struct dir_info * d,int bits,int listnum)563 omalloc_make_chunks(struct dir_info *d, int bits, int listnum)
564 {
565 struct chunk_info *bp;
566 void *pp;
567
568 /* Allocate a new bucket */
569 pp = map(d, MALLOC_PAGESIZE, 0);
570 if (pp == MAP_FAILED)
571 return NULL;
572
573 bp = alloc_chunk_info(d, bits);
574 if (bp == NULL)
575 goto err;
576 /* memory protect the page allocated in the malloc(0) case */
577 if (bits == 0 && _dl_mprotect(pp, MALLOC_PAGESIZE, PROT_NONE) < 0)
578 goto err;
579
580 bp->page = pp;
581
582 if (insert(d, (void *)((uintptr_t)pp | (bits + 1)), (uintptr_t)bp))
583 goto err;
584 LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries);
585 return bp;
586
587 err:
588 unmap(d, pp, MALLOC_PAGESIZE, MALLOC_JUNK);
589 return NULL;
590 }
591
592 static int
find_chunksize(size_t size)593 find_chunksize(size_t size)
594 {
595 int r;
596
597 /* malloc(0) is special */
598 if (size == 0)
599 return 0;
600
601 if (size < MALLOC_MINSIZE)
602 size = MALLOC_MINSIZE;
603 size--;
604
605 r = MALLOC_MINSHIFT;
606 while (size >> r)
607 r++;
608 return r;
609 }
610
611 static void
fill_canary(char * ptr,size_t sz,size_t allocated)612 fill_canary(char *ptr, size_t sz, size_t allocated)
613 {
614 size_t check_sz = allocated - sz;
615
616 if (check_sz > CHUNK_CHECK_LENGTH)
617 check_sz = CHUNK_CHECK_LENGTH;
618 _dl_memset(ptr + sz, SOME_JUNK, check_sz);
619 }
620
621 /*
622 * Allocate a chunk
623 */
624 static void *
malloc_bytes(struct dir_info * d,size_t size)625 malloc_bytes(struct dir_info *d, size_t size)
626 {
627 u_int i, r;
628 int j, listnum;
629 size_t k;
630 u_short *lp;
631 struct chunk_info *bp;
632 void *p;
633
634 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
635 d->canary1 != ~d->canary2)
636 wrterror("internal struct corrupt");
637
638 j = find_chunksize(size);
639
640 r = ((u_int)getrbyte(d) << 8) | getrbyte(d);
641 listnum = r % MALLOC_CHUNK_LISTS;
642 /* If it's empty, make a page more of that size chunks */
643 if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) {
644 bp = omalloc_make_chunks(d, j, listnum);
645 if (bp == NULL)
646 return NULL;
647 }
648
649 if (bp->canary != (u_short)d->canary1)
650 wrterror("chunk info corrupted");
651
652 i = (r / MALLOC_CHUNK_LISTS) & (bp->total - 1);
653
654 /* start somewhere in a short */
655 lp = &bp->bits[i / MALLOC_BITS];
656 if (*lp) {
657 j = i % MALLOC_BITS;
658 k = __builtin_ffs(*lp >> j);
659 if (k != 0) {
660 k += j - 1;
661 goto found;
662 }
663 }
664 /* no bit halfway, go to next full short */
665 i /= MALLOC_BITS;
666 for (;;) {
667 if (++i >= bp->total / MALLOC_BITS)
668 i = 0;
669 lp = &bp->bits[i];
670 if (*lp) {
671 k = __builtin_ffs(*lp) - 1;
672 break;
673 }
674 }
675 found:
676 *lp ^= 1 << k;
677
678 /* If there are no more free, remove from free-list */
679 if (--bp->free == 0)
680 LIST_REMOVE(bp, entries);
681
682 /* Adjust to the real offset of that chunk */
683 k += (lp - bp->bits) * MALLOC_BITS;
684
685 if (CHUNK_CANARIES && size > 0)
686 bp->bits[bp->offset + k] = size;
687
688 k <<= bp->shift;
689
690 p = (char *)bp->page + k;
691 if (bp->size > 0) {
692 if (MALLOC_JUNK == 2)
693 _dl_memset(p, SOME_JUNK, bp->size);
694 else if (CHUNK_CANARIES)
695 fill_canary(p, size, bp->size);
696 }
697 return p;
698 }
699
700 static void
validate_canary(u_char * ptr,size_t sz,size_t allocated)701 validate_canary(u_char *ptr, size_t sz, size_t allocated)
702 {
703 size_t check_sz = allocated - sz;
704 u_char *p, *q;
705
706 if (check_sz > CHUNK_CHECK_LENGTH)
707 check_sz = CHUNK_CHECK_LENGTH;
708 p = ptr + sz;
709 q = p + check_sz;
710
711 while (p < q)
712 if (*p++ != SOME_JUNK)
713 wrterror("chunk canary corrupted");
714 }
715
716 static uint32_t
find_chunknum(struct dir_info * d,struct region_info * r,void * ptr,int check)717 find_chunknum(struct dir_info *d, struct region_info *r, void *ptr, int check)
718 {
719 struct chunk_info *info;
720 uint32_t chunknum;
721
722 info = (struct chunk_info *)r->size;
723 if (info->canary != (u_short)d->canary1)
724 wrterror("chunk info corrupted");
725
726 /* Find the chunk number on the page */
727 chunknum = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift;
728 if (check && info->size > 0) {
729 validate_canary(ptr, info->bits[info->offset + chunknum],
730 info->size);
731 }
732
733 if ((uintptr_t)ptr & ((1U << (info->shift)) - 1)) {
734 wrterror("modified chunk-pointer");
735 return -1;
736 }
737 if (info->bits[chunknum / MALLOC_BITS] &
738 (1U << (chunknum % MALLOC_BITS)))
739 wrterror("chunk is already free");
740 return chunknum;
741 }
742
743 /*
744 * Free a chunk, and possibly the page it's on, if the page becomes empty.
745 */
746 static void
free_bytes(struct dir_info * d,struct region_info * r,void * ptr)747 free_bytes(struct dir_info *d, struct region_info *r, void *ptr)
748 {
749 struct chunk_head *mp;
750 struct chunk_info *info;
751 uint32_t chunknum;
752 int listnum;
753
754 info = (struct chunk_info *)r->size;
755 chunknum = find_chunknum(d, r, ptr, 0);
756
757 info->bits[chunknum / MALLOC_BITS] |= 1U << (chunknum % MALLOC_BITS);
758 info->free++;
759
760 if (info->free == 1) {
761 /* Page became non-full */
762 listnum = getrbyte(d) % MALLOC_CHUNK_LISTS;
763 if (info->size != 0)
764 mp = &d->chunk_dir[info->shift][listnum];
765 else
766 mp = &d->chunk_dir[0][listnum];
767
768 LIST_INSERT_HEAD(mp, info, entries);
769 return;
770 }
771
772 if (info->free != info->total)
773 return;
774
775 LIST_REMOVE(info, entries);
776
777 if (info->size == 0 && !MALLOC_FREEUNMAP)
778 _dl_mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE);
779 unmap(d, info->page, MALLOC_PAGESIZE, 0);
780
781 delete(d, r);
782 if (info->size != 0)
783 mp = &d->chunk_info_list[info->shift];
784 else
785 mp = &d->chunk_info_list[0];
786 LIST_INSERT_HEAD(mp, info, entries);
787 }
788
789 static void *
omalloc(size_t sz,int zero_fill)790 omalloc(size_t sz, int zero_fill)
791 {
792 void *p;
793 size_t psz;
794
795 if (sz > MALLOC_MAXCHUNK) {
796 if (sz >= SIZE_MAX - MALLOC_GUARD - MALLOC_PAGESIZE) {
797 return NULL;
798 }
799 sz += MALLOC_GUARD;
800 psz = PAGEROUND(sz);
801 p = map(g_pool, psz, zero_fill);
802 if (p == MAP_FAILED) {
803 return NULL;
804 }
805 if (insert(g_pool, p, sz)) {
806 unmap(g_pool, p, psz, 0);
807 return NULL;
808 }
809 if (MALLOC_GUARD) {
810 if (_dl_mprotect((char *)p + psz - MALLOC_GUARD,
811 MALLOC_GUARD, PROT_NONE))
812 wrterror("mprotect");
813 }
814
815 if (sz - MALLOC_GUARD < MALLOC_PAGESIZE - MALLOC_LEEWAY) {
816 /* fill whole allocation */
817 if (MALLOC_JUNK == 2)
818 _dl_memset(p, SOME_JUNK, psz - MALLOC_GUARD);
819 /* shift towards the end */
820 p = ((char *)p) + ((MALLOC_PAGESIZE - MALLOC_LEEWAY -
821 (sz - MALLOC_GUARD)) & ~(MALLOC_MINSIZE-1));
822 /* fill zeros if needed and overwritten above */
823 if (zero_fill && MALLOC_JUNK == 2)
824 _dl_memset(p, 0, sz - MALLOC_GUARD);
825 } else {
826 if (MALLOC_JUNK == 2) {
827 if (zero_fill)
828 _dl_memset((char *)p + sz - MALLOC_GUARD,
829 SOME_JUNK, psz - sz);
830 else
831 _dl_memset(p, SOME_JUNK,
832 psz - MALLOC_GUARD);
833 } else if (CHUNK_CANARIES)
834 fill_canary(p, sz - MALLOC_GUARD,
835 psz - MALLOC_GUARD);
836 }
837
838 } else {
839 /* takes care of SOME_JUNK */
840 p = malloc_bytes(g_pool, sz);
841 if (zero_fill && p != NULL && sz > 0)
842 _dl_memset(p, 0, sz);
843 }
844
845 return p;
846 }
847
848 /*
849 * Common function for handling recursion. Only
850 * print the error message once, to avoid making the problem
851 * potentially worse.
852 */
853 static void
malloc_recurse(void)854 malloc_recurse(void)
855 {
856 static int noprint;
857
858 if (noprint == 0) {
859 noprint = 1;
860 wrterror("recursive call");
861 }
862 g_pool->active--;
863 }
864
865 void *
_dl_malloc(size_t size)866 _dl_malloc(size_t size)
867 {
868 void *r = NULL;
869 lock_cb *cb;
870
871 cb = _dl_thread_kern_stop();
872 g_pool->func = "malloc():";
873 if (g_pool->active++) {
874 malloc_recurse();
875 goto ret;
876 }
877 r = omalloc(size, 0);
878 g_pool->active--;
879 ret:
880 _dl_thread_kern_go(cb);
881 return r;
882 }
883
884 static void
validate_junk(struct dir_info * pool,void * p)885 validate_junk(struct dir_info *pool, void *p)
886 {
887 struct region_info *r;
888 size_t byte, sz;
889
890 if (p == NULL)
891 return;
892 r = find(pool, p);
893 if (r == NULL)
894 wrterror("bogus pointer in validate_junk");
895 REALSIZE(sz, r);
896 if (sz > CHUNK_CHECK_LENGTH)
897 sz = CHUNK_CHECK_LENGTH;
898 for (byte = 0; byte < sz; byte++) {
899 if (((unsigned char *)p)[byte] != SOME_FREEJUNK)
900 wrterror("use after free");
901 }
902 }
903
904 static void
ofree(void * p)905 ofree(void *p)
906 {
907 struct region_info *r;
908 size_t sz;
909
910 r = find(g_pool, p);
911 if (r == NULL)
912 wrterror("bogus pointer (double free?)");
913 REALSIZE(sz, r);
914 if (sz > MALLOC_MAXCHUNK) {
915 if (sz - MALLOC_GUARD >= MALLOC_PAGESIZE -
916 MALLOC_LEEWAY) {
917 if (r->p != p)
918 wrterror("bogus pointer");
919 if (CHUNK_CANARIES)
920 validate_canary(p,
921 sz - MALLOC_GUARD,
922 PAGEROUND(sz - MALLOC_GUARD));
923 } else {
924 #if notyetbecause_of_realloc
925 /* shifted towards the end */
926 if (p != ((char *)r->p) + ((MALLOC_PAGESIZE -
927 MALLOC_MINSIZE - sz - MALLOC_GUARD) &
928 ~(MALLOC_MINSIZE-1))) {
929 }
930 #endif
931 p = r->p;
932 }
933 if (MALLOC_GUARD) {
934 if (sz < MALLOC_GUARD)
935 wrterror("guard size");
936 if (!MALLOC_FREEUNMAP) {
937 if (_dl_mprotect((char *)p + PAGEROUND(sz) -
938 MALLOC_GUARD, MALLOC_GUARD,
939 PROT_READ | PROT_WRITE))
940 wrterror("mprotect");
941 }
942 }
943 unmap(g_pool, p, PAGEROUND(sz), MALLOC_JUNK);
944 delete(g_pool, r);
945 } else {
946 void *tmp;
947 int i;
948 struct chunk_info *info = (struct chunk_info *)r->size;
949
950 if (info->size != sz)
951 wrterror("internal struct corrupt");
952 find_chunknum(g_pool, r, p, CHUNK_CANARIES);
953 for (i = 0; i <= MALLOC_DELAYED_CHUNK_MASK; i++) {
954 if (p == g_pool->delayed_chunks[i])
955 wrterror("double free");
956 }
957 if (MALLOC_JUNK && sz > 0)
958 _dl_memset(p, SOME_FREEJUNK, sz);
959 i = getrbyte(g_pool) & MALLOC_DELAYED_CHUNK_MASK;
960 tmp = p;
961 p = g_pool->delayed_chunks[i];
962 g_pool->delayed_chunks[i] = tmp;
963 if (MALLOC_JUNK)
964 validate_junk(g_pool, p);
965 if (p != NULL) {
966 r = find(g_pool, p);
967 if (r == NULL)
968 wrterror("bogus pointer (double free?)");
969 free_bytes(g_pool, r, p);
970 }
971 }
972 }
973
974 void
_dl_free(void * ptr)975 _dl_free(void *ptr)
976 {
977 lock_cb *cb;
978
979 /* This is legal. */
980 if (ptr == NULL)
981 return;
982
983 cb = _dl_thread_kern_stop();
984 if (g_pool == NULL)
985 wrterror("free() called before allocation");
986 g_pool->func = "free():";
987 if (g_pool->active++) {
988 malloc_recurse();
989 goto ret;
990 }
991 ofree(ptr);
992 g_pool->active--;
993 ret:
994 _dl_thread_kern_go(cb);
995 }
996
997
998 /*
999 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
1000 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
1001 */
1002 #define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
1003
1004 void *
_dl_calloc(size_t nmemb,size_t size)1005 _dl_calloc(size_t nmemb, size_t size)
1006 {
1007 void *r = NULL;
1008 lock_cb *cb;
1009
1010 cb = _dl_thread_kern_stop();
1011 g_pool->func = "calloc():";
1012 if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1013 nmemb > 0 && SIZE_MAX / nmemb < size) {
1014 goto ret;
1015 }
1016
1017 if (g_pool->active++) {
1018 malloc_recurse();
1019 goto ret;
1020 }
1021
1022 size *= nmemb;
1023 r = omalloc(size, 1);
1024 g_pool->active--;
1025 ret:
1026 _dl_thread_kern_go(cb);
1027 return r;
1028 }
1029
1030
1031 static void *
orealloc(void * p,size_t newsz)1032 orealloc(void *p, size_t newsz)
1033 {
1034 struct region_info *r;
1035 void *q;
1036 size_t oldsz;
1037
1038 q = omalloc(newsz, 0);
1039 if (p == NULL || q == NULL)
1040 return q;
1041 r = find(g_pool, p);
1042 if (r == NULL)
1043 wrterror("bogus pointer (double free?)");
1044 REALSIZE(oldsz, r);
1045 if (oldsz > MALLOC_MAXCHUNK) {
1046 if (oldsz < MALLOC_GUARD)
1047 wrterror("guard size");
1048 oldsz -= MALLOC_GUARD;
1049 }
1050 _dl_bcopy(p, q, oldsz < newsz ? oldsz : newsz);
1051 ofree(p);
1052 return q;
1053 }
1054
1055
1056 void *
_dl_realloc(void * ptr,size_t size)1057 _dl_realloc(void *ptr, size_t size)
1058 {
1059 void *r = NULL;
1060 lock_cb *cb;
1061
1062 cb = _dl_thread_kern_stop();
1063 g_pool->func = "realloc():";
1064 if (g_pool->active++) {
1065 malloc_recurse();
1066 goto ret;
1067 }
1068 r = orealloc(ptr, size);
1069 g_pool->active--;
1070 ret:
1071 _dl_thread_kern_go(cb);
1072 return r;
1073 }
1074
1075 static void *
mapalign(struct dir_info * d,size_t alignment,size_t sz,int zero_fill)1076 mapalign(struct dir_info *d, size_t alignment, size_t sz, int zero_fill)
1077 {
1078 char *p, *q;
1079
1080 if (alignment < MALLOC_PAGESIZE || ((alignment - 1) & alignment) != 0)
1081 wrterror("mapalign bad alignment");
1082 if (sz != PAGEROUND(sz))
1083 wrterror("mapalign round");
1084
1085 /* Allocate sz + alignment bytes of memory, which must include a
1086 * subrange of size bytes that is properly aligned. Unmap the
1087 * other bytes, and then return that subrange.
1088 */
1089
1090 /* We need sz + alignment to fit into a size_t. */
1091 if (alignment > SIZE_MAX - sz)
1092 return MAP_FAILED;
1093
1094 p = map(d, sz + alignment, zero_fill);
1095 if (p == MAP_FAILED)
1096 return MAP_FAILED;
1097 q = (char *)(((uintptr_t)p + alignment - 1) & ~(alignment - 1));
1098 if (q != p) {
1099 if (_dl_munmap(p, q - p))
1100 wrterror("munmap");
1101 }
1102 if (_dl_munmap(q + sz, alignment - (q - p)))
1103 wrterror("munmap");
1104
1105 return q;
1106 }
1107
1108 static void *
omemalign(size_t alignment,size_t sz,int zero_fill)1109 omemalign(size_t alignment, size_t sz, int zero_fill)
1110 {
1111 size_t psz;
1112 void *p;
1113
1114 /* If between half a page and a page, avoid MALLOC_MOVE. */
1115 if (sz > MALLOC_MAXCHUNK && sz < MALLOC_PAGESIZE)
1116 sz = MALLOC_PAGESIZE;
1117 if (alignment <= MALLOC_PAGESIZE) {
1118 /*
1119 * max(size, alignment) is enough to assure the requested
1120 * alignment, since the allocator always allocates
1121 * power-of-two blocks.
1122 */
1123 if (sz < alignment)
1124 sz = alignment;
1125 return omalloc(sz, zero_fill);
1126 }
1127
1128 if (sz >= SIZE_MAX - MALLOC_GUARD - MALLOC_PAGESIZE) {
1129 return NULL;
1130 }
1131
1132 sz += MALLOC_GUARD;
1133 psz = PAGEROUND(sz);
1134
1135 p = mapalign(g_pool, alignment, psz, zero_fill);
1136 if (p == MAP_FAILED) {
1137 return NULL;
1138 }
1139
1140 if (insert(g_pool, p, sz)) {
1141 unmap(g_pool, p, psz, 0);
1142 return NULL;
1143 }
1144
1145 if (MALLOC_GUARD) {
1146 if (_dl_mprotect((char *)p + psz - MALLOC_GUARD,
1147 MALLOC_GUARD, PROT_NONE))
1148 wrterror("mprotect");
1149 }
1150
1151 if (MALLOC_JUNK == 2) {
1152 if (zero_fill)
1153 _dl_memset((char *)p + sz - MALLOC_GUARD,
1154 SOME_JUNK, psz - sz);
1155 else
1156 _dl_memset(p, SOME_JUNK, psz - MALLOC_GUARD);
1157 } else if (CHUNK_CANARIES)
1158 fill_canary(p, sz - MALLOC_GUARD,
1159 psz - MALLOC_GUARD);
1160
1161 return p;
1162 }
1163
1164 void *
_dl_aligned_alloc(size_t alignment,size_t size)1165 _dl_aligned_alloc(size_t alignment, size_t size)
1166 {
1167 void *r = NULL;
1168 lock_cb *cb;
1169
1170 /* Make sure that alignment is a large enough power of 2. */
1171 if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *))
1172 return NULL;
1173
1174 cb = _dl_thread_kern_stop();
1175 g_pool->func = "aligned_alloc():";
1176 if (g_pool->active++) {
1177 malloc_recurse();
1178 goto ret;
1179 }
1180 r = omemalign(alignment, size, 0);
1181 g_pool->active--;
1182 ret:
1183 _dl_thread_kern_go(cb);
1184 return r;
1185 }
1186