1 /* $OpenBSD: malloc.c,v 1.150 2013/11/12 06:57:54 deraadt Exp $ */
2 /*
3 * Copyright © 2013
4 * Thorsten “mirabilos” Glaser <tg@mirbsd.org>
5 * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /*
21 * Parts of this code, mainly the sub page sized chunk management code is
22 * derived from the malloc implementation with the following license:
23 */
24 /*
25 * ----------------------------------------------------------------------------
26 * "THE BEER-WARE LICENSE" (Revision 42):
27 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
28 * can do whatever you want with this stuff. If we meet some day, and you think
29 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
30 * ----------------------------------------------------------------------------
31 */
32
33 /* #define MALLOC_STATS */
34
35 #include <sys/param.h>
36 #include <sys/queue.h>
37 #include <sys/mman.h>
38 #include <sys/uio.h>
39 #include <errno.h>
40 #include <stdint.h>
41 #include <stdlib.h>
42 #include <string.h>
43 #include <stdio.h>
44 #include <unistd.h>
45
46 #ifdef MALLOC_STATS
47 #include <sys/tree.h>
48 #include <fcntl.h>
49 #endif
50
51 #include "thread_private.h"
52
53 __IDSTRING(malloc_type, "@(#) omalloc 1.150 (OpenBSD)");
54 __RCSID("$MirOS: src/lib/libc/stdlib/malloc.c,v 1.14 2014/03/02 14:45:58 tg Exp $");
55
56 #if defined(__sparc__) && !defined(__sparcv9__)
57 #define MALLOC_PAGESHIFT (13U)
58 #elif defined(__mips64__)
59 #define MALLOC_PAGESHIFT (14U)
60 #else
61 #define MALLOC_PAGESHIFT (PAGE_SHIFT)
62 #endif
63
64 #define MALLOC_MINSHIFT 4
65 #define MALLOC_MAXSHIFT (MALLOC_PAGESHIFT - 1)
66 #define MALLOC_PAGESIZE (1UL << MALLOC_PAGESHIFT)
67 #define MALLOC_MINSIZE (1UL << MALLOC_MINSHIFT)
68 #define MALLOC_PAGEMASK (MALLOC_PAGESIZE - 1)
69 #define MASK_POINTER(p) ((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK))
70
71 #define MALLOC_MAXCHUNK (1 << MALLOC_MAXSHIFT)
72 #define MALLOC_MAXCACHE 256
73 #define MALLOC_DELAYED_CHUNKS 15 /* max of getrnibble() */
74 #define MALLOC_INITIAL_REGIONS 512
75 #define MALLOC_DEFAULT_CACHE 64
76
77 /*
78 * When the P option is active, we move allocations between half a page
79 * and a whole page towards the end, subject to alignment constraints.
80 * This is the extra headroom we allow. Set to zero to be the most
81 * strict.
82 */
83 #define MALLOC_LEEWAY 0
84
85 #define PAGEROUND(x) (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK)
86
87 /*
88 * What to use for Junk. This is the byte value we use to fill with
89 * when the 'J' option is enabled. Use SOME_JUNK right after alloc,
90 * and SOME_FREEJUNK right before free.
91 */
92 #define SOME_JUNK 0xd0 /* as in "Duh" :-) */
93 #define SOME_FREEJUNK 0xdf
94
95 #define MMAP(sz) mmap(NULL, (size_t)(sz), PROT_READ | PROT_WRITE, \
96 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0)
97
98 #define MMAPA(a,sz) mmap((a), (size_t)(sz), PROT_READ | PROT_WRITE, \
99 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0)
100
101 #define MQUERY(a, sz) mquery((a), (size_t)(sz), PROT_READ | PROT_WRITE, \
102 MAP_ANON | MAP_PRIVATE | MAP_FIXED, -1, (off_t)0)
103
104 struct region_info {
105 void *p; /* page; low bits used to mark chunks */
106 uintptr_t size; /* size for pages, or chunk_info pointer */
107 #ifdef MALLOC_STATS
108 void *f; /* where allocated from */
109 #endif
110 };
111
112 LIST_HEAD(chunk_head, chunk_info);
113
114 struct dir_info {
115 u_int32_t canary1;
116 struct region_info *r; /* region slots */
117 size_t regions_total; /* number of region slots */
118 size_t regions_free; /* number of free slots */
119 /* lists of free chunk info structs */
120 struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1];
121 /* lists of chunks with free slots */
122 struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1];
123 size_t free_regions_size; /* free pages cached */
124 /* free pages cache */
125 struct region_info free_regions[MALLOC_MAXCACHE];
126 /* delayed free chunk slots */
127 void *delayed_chunks[MALLOC_DELAYED_CHUNKS + 1];
128 u_short chunk_start;
129 #ifdef MALLOC_STATS
130 size_t inserts;
131 size_t insert_collisions;
132 size_t finds;
133 size_t find_collisions;
134 size_t deletes;
135 size_t delete_moves;
136 size_t cheap_realloc_tries;
137 size_t cheap_reallocs;
138 #define STATS_INC(x) ((x)++)
139 #define STATS_ZERO(x) ((x) = 0)
140 #define STATS_SETF(x,y) ((x)->f = (y))
141 #else
142 #define STATS_INC(x) /* nothing */
143 #define STATS_ZERO(x) /* nothing */
144 #define STATS_SETF(x,y) /* nothing */
145 #endif /* MALLOC_STATS */
146 u_int32_t canary2;
147 };
148 #define DIR_INFO_RSZ ((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \
149 ~MALLOC_PAGEMASK)
150
151 /*
152 * This structure describes a page worth of chunks.
153 *
154 * How many bits per u_short in the bitmap
155 */
156 #define MALLOC_BITS (NBBY * sizeof(u_short))
157 struct chunk_info {
158 LIST_ENTRY(chunk_info) entries;
159 void *page; /* pointer to the page */
160 u_int32_t canary;
161 u_short size; /* size of this page's chunks */
162 u_short shift; /* how far to shift for this size */
163 u_short free; /* how many free chunks */
164 u_short total; /* how many chunk */
165 /* which chunks are free */
166 u_short bits[1];
167 };
168
169 struct malloc_readonly {
170 struct dir_info *g_pool; /* Main bookkeeping information */
171 int malloc_abort; /* abort() on error */
172 int malloc_freenow; /* Free quickly - disable chunk rnd */
173 int malloc_freeunmap; /* mprotect free pages PROT_NONE? */
174 int malloc_hint; /* call madvice on free pages? */
175 int malloc_junk; /* junk fill? */
176 int malloc_move; /* move allocations to end of page? */
177 int malloc_realloc; /* always realloc? */
178 int malloc_xmalloc; /* xmalloc behaviour? */
179 int malloc_zero; /* zero fill? */
180 size_t malloc_guard; /* use guard pages after allocations? */
181 u_int malloc_cache; /* free pages we cache */
182 #ifdef MALLOC_STATS
183 int malloc_stats; /* dump statistics at end */
184 #endif
185 u_int32_t malloc_canary; /* Matched against ones in g_pool */
186 };
187
188 /* This object is mapped PROT_READ after initialisation to prevent tampering */
189 static union {
190 struct malloc_readonly mopts;
191 u_char _pad[MALLOC_PAGESIZE];
192 } malloc_readonly __attribute__((__aligned__(MALLOC_PAGESIZE)));
193 #define mopts malloc_readonly.mopts
194 #define g_pool mopts.g_pool
195
196 char *malloc_options; /* compile-time options */
197
198 static const char *malloc_func; /* current function */
199 static int malloc_active; /* status of malloc */
200
201 static size_t malloc_guarded; /* bytes used for guards */
202 static size_t malloc_used; /* bytes allocated */
203
204 static size_t rnibblesused; /* random nibbles used */
205 static u_char rbytes[512]; /* random bytes */
206 static u_char getrnibble(void);
207
208 extern char *__progname;
209
210 #ifdef MALLOC_STATS
211 void malloc_dump(int);
212 static void malloc_exit(void);
213 #define CALLER __builtin_return_address(0)
214 #else
215 #define CALLER NULL
216 #endif
217
218 /* low bits of r->p determine size: 0 means >= page size and p->size holding
219 * real size, otherwise r->size is a shift count, or 1 for malloc(0)
220 */
221 #define REALSIZE(sz, r) \
222 (sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \
223 (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1U << ((sz)-1))))
224
225 static inline size_t
hash(void * p)226 hash(void *p)
227 {
228 size_t sum;
229 union {
230 uintptr_t p;
231 unsigned short a[sizeof(void *) / sizeof(short)];
232 } u;
233 u.p = (uintptr_t)p >> MALLOC_PAGESHIFT;
234 sum = u.a[0];
235 sum = (sum << 7) - sum + u.a[1];
236 #ifdef __LP64__
237 sum = (sum << 7) - sum + u.a[2];
238 sum = (sum << 7) - sum + u.a[3];
239 #endif
240 return sum;
241 }
242
243 static void
wrterror(const char * msg,const void * p)244 wrterror(const char *msg, const void *p)
245 {
246 #define writev_unconst(s) __extension__({ \
247 union { \
248 char *rw; \
249 const char *ro; \
250 } writev_unconst_u; \
251 \
252 writev_unconst_u.ro = (s); \
253 (writev_unconst_u.rw); \
254 })
255 static const char q[] = " error: ";
256 struct iovec iov[6];
257 char buf[20];
258 int saved_errno = errno;
259
260 iov[0].iov_base = writev_unconst(__progname);
261 iov[0].iov_len = strlen(__progname);
262 iov[1].iov_base = writev_unconst(malloc_func);
263 iov[1].iov_len = strlen(malloc_func);
264 iov[2].iov_base = writev_unconst(q);
265 iov[2].iov_len = sizeof(q) - 1;
266 iov[3].iov_base = writev_unconst(msg);
267 iov[3].iov_len = strlen(msg);
268 iov[4].iov_base = buf;
269 if (p == NULL)
270 iov[4].iov_len = 0;
271 else {
272 snprintf(buf, sizeof(buf), " %p", p);
273 iov[4].iov_len = strlen(buf);
274 }
275 iov[5].iov_base = writev_unconst("\n");
276 iov[5].iov_len = 1;
277 writev(STDERR_FILENO, iov, 6);
278
279 #ifdef MALLOC_STATS
280 if (mopts.malloc_stats)
281 malloc_dump(STDERR_FILENO);
282 #endif /* MALLOC_STATS */
283
284 errno = saved_errno;
285 if (mopts.malloc_abort)
286 abort();
287 }
288
289 static void
rbytes_init(void)290 rbytes_init(void)
291 {
292 arc4random_buf(rbytes, sizeof(rbytes));
293 rnibblesused = 0;
294 }
295
296 static inline u_char
getrnibble(void)297 getrnibble(void)
298 {
299 u_char x;
300
301 if (rnibblesused >= 2 * sizeof(rbytes))
302 rbytes_init();
303 x = rbytes[rnibblesused++ / 2];
304 return (rnibblesused & 1 ? x & 0xf : x >> 4);
305 }
306
307 /*
308 * Cache maintenance. We keep at most malloc_cache pages cached.
309 * If the cache is becoming full, unmap pages in the cache for real,
310 * and then add the region to the cache
311 * Opposed to the regular region data structure, the sizes in the
312 * cache are in MALLOC_PAGESIZE units.
313 */
314 static void
unmap(struct dir_info * d,void * p,size_t sz)315 unmap(struct dir_info *d, void *p, size_t sz)
316 {
317 size_t psz = sz >> MALLOC_PAGESHIFT;
318 size_t rsz, tounmap;
319 struct region_info *r;
320 u_int i, offset;
321
322 if (sz != PAGEROUND(sz)) {
323 wrterror("munmap round", NULL);
324 return;
325 }
326
327 if (psz > mopts.malloc_cache) {
328 if (munmap(p, sz))
329 wrterror("munmap", p);
330 malloc_used -= sz;
331 return;
332 }
333 tounmap = 0;
334 rsz = mopts.malloc_cache - d->free_regions_size;
335 if (psz > rsz)
336 tounmap = psz - rsz;
337 offset = getrnibble() + (getrnibble() << 4);
338 for (i = 0; tounmap > 0 && i < mopts.malloc_cache; i++) {
339 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)];
340 if (r->p != NULL) {
341 rsz = r->size << MALLOC_PAGESHIFT;
342 if (munmap(r->p, rsz))
343 wrterror("munmap", r->p);
344 r->p = NULL;
345 if (tounmap > r->size)
346 tounmap -= r->size;
347 else
348 tounmap = 0;
349 d->free_regions_size -= r->size;
350 r->size = 0;
351 malloc_used -= rsz;
352 }
353 }
354 if (tounmap > 0)
355 wrterror("malloc cache underflow", NULL);
356 for (i = 0; i < mopts.malloc_cache; i++) {
357 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)];
358 if (r->p == NULL) {
359 if (mopts.malloc_hint)
360 madvise(p, sz, MADV_FREE);
361 if (mopts.malloc_freeunmap)
362 mprotect(p, sz, PROT_NONE);
363 r->p = p;
364 r->size = psz;
365 d->free_regions_size += psz;
366 break;
367 }
368 }
369 if (i == mopts.malloc_cache)
370 wrterror("malloc free slot lost", NULL);
371 if (d->free_regions_size > mopts.malloc_cache)
372 wrterror("malloc cache overflow", NULL);
373 }
374
375 static void
zapcacheregion(struct dir_info * d,void * p,size_t len)376 zapcacheregion(struct dir_info *d, void *p, size_t len)
377 {
378 u_int i;
379 struct region_info *r;
380 size_t rsz;
381
382 for (i = 0; i < mopts.malloc_cache; i++) {
383 r = &d->free_regions[i];
384 if (r->p >= p && r->p <= (void *)((char *)p + len)) {
385 rsz = r->size << MALLOC_PAGESHIFT;
386 if (munmap(r->p, rsz))
387 wrterror("munmap", r->p);
388 r->p = NULL;
389 d->free_regions_size -= r->size;
390 r->size = 0;
391 malloc_used -= rsz;
392 }
393 }
394 }
395
396 static void *
map(struct dir_info * d,size_t sz,int zero_fill)397 map(struct dir_info *d, size_t sz, int zero_fill)
398 {
399 size_t psz = sz >> MALLOC_PAGESHIFT;
400 struct region_info *r, *big = NULL;
401 u_int i, offset;
402 void *p;
403
404 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
405 d->canary1 != ~d->canary2)
406 wrterror("internal struct corrupt", NULL);
407 if (sz != PAGEROUND(sz)) {
408 wrterror("map round", NULL);
409 return MAP_FAILED;
410 }
411 if (psz > d->free_regions_size) {
412 p = MMAP(sz);
413 if (p != MAP_FAILED)
414 malloc_used += sz;
415 /* zero fill not needed */
416 return p;
417 }
418 offset = getrnibble() + (getrnibble() << 4);
419 for (i = 0; i < mopts.malloc_cache; i++) {
420 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)];
421 if (r->p != NULL) {
422 if (r->size == psz) {
423 p = r->p;
424 if (mopts.malloc_freeunmap)
425 mprotect(p, sz, PROT_READ | PROT_WRITE);
426 if (mopts.malloc_hint)
427 madvise(p, sz, MADV_NORMAL);
428 r->p = NULL;
429 r->size = 0;
430 d->free_regions_size -= psz;
431 if (zero_fill)
432 memset(p, 0, sz);
433 else if (mopts.malloc_junk &&
434 mopts.malloc_freeunmap)
435 memset(p, SOME_FREEJUNK, sz);
436 return p;
437 } else if (r->size > psz)
438 big = r;
439 }
440 }
441 if (big != NULL) {
442 r = big;
443 p = (char *)r->p + ((r->size - psz) << MALLOC_PAGESHIFT);
444 if (mopts.malloc_freeunmap)
445 mprotect(p, sz, PROT_READ | PROT_WRITE);
446 if (mopts.malloc_hint)
447 madvise(p, sz, MADV_NORMAL);
448 r->size -= psz;
449 d->free_regions_size -= psz;
450 if (zero_fill)
451 memset(p, 0, sz);
452 else if (mopts.malloc_junk && mopts.malloc_freeunmap)
453 memset(p, SOME_FREEJUNK, sz);
454 return p;
455 }
456 p = MMAP(sz);
457 if (p != MAP_FAILED)
458 malloc_used += sz;
459 if (d->free_regions_size > mopts.malloc_cache)
460 wrterror("malloc cache", NULL);
461 /* zero fill not needed */
462 return p;
463 }
464
465 /*
466 * Initialize a dir_info, which should have been cleared by caller
467 */
468 static int
omalloc_init(struct dir_info ** dp)469 omalloc_init(struct dir_info **dp)
470 {
471 char *p, b[64];
472 int i, j;
473 size_t d_avail, regioninfo_size;
474 struct dir_info *d;
475
476 rbytes_init();
477
478 /*
479 * Default options
480 */
481 mopts.malloc_abort = 1;
482 mopts.malloc_move = 1;
483 mopts.malloc_cache = MALLOC_DEFAULT_CACHE;
484
485 for (i = 0; i < 3; i++) {
486 switch (i) {
487 case 0:
488 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
489 if (j <= 0)
490 continue;
491 b[j] = '\0';
492 p = b;
493 break;
494 case 1:
495 if (issetugid() == 0)
496 p = getenv("MALLOC_OPTIONS");
497 else
498 continue;
499 break;
500 case 2:
501 p = malloc_options;
502 break;
503 default:
504 p = NULL;
505 }
506
507 for (; p != NULL && *p != '\0'; p++) {
508 switch (*p) {
509 case '>':
510 mopts.malloc_cache <<= 1;
511 if (mopts.malloc_cache > MALLOC_MAXCACHE)
512 mopts.malloc_cache = MALLOC_MAXCACHE;
513 break;
514 case '<':
515 mopts.malloc_cache >>= 1;
516 break;
517 case 'a':
518 mopts.malloc_abort = 0;
519 break;
520 case 'A':
521 mopts.malloc_abort = 1;
522 break;
523 #ifdef MALLOC_STATS
524 case 'd':
525 mopts.malloc_stats = 0;
526 break;
527 case 'D':
528 mopts.malloc_stats = 1;
529 break;
530 #endif /* MALLOC_STATS */
531 case 'f':
532 mopts.malloc_freenow = 0;
533 mopts.malloc_freeunmap = 0;
534 break;
535 case 'F':
536 mopts.malloc_freenow = 1;
537 mopts.malloc_freeunmap = 1;
538 break;
539 case 'g':
540 mopts.malloc_guard = 0;
541 break;
542 case 'G':
543 mopts.malloc_guard = MALLOC_PAGESIZE;
544 break;
545 case 'h':
546 mopts.malloc_hint = 0;
547 break;
548 case 'H':
549 mopts.malloc_hint = 1;
550 break;
551 case 'j':
552 mopts.malloc_junk = 0;
553 break;
554 case 'J':
555 mopts.malloc_junk = 1;
556 break;
557 case 'n':
558 case 'N':
559 break;
560 case 'p':
561 mopts.malloc_move = 0;
562 break;
563 case 'P':
564 mopts.malloc_move = 1;
565 break;
566 case 'r':
567 mopts.malloc_realloc = 0;
568 break;
569 case 'R':
570 mopts.malloc_realloc = 1;
571 break;
572 case 's':
573 mopts.malloc_freeunmap = mopts.malloc_junk = 0;
574 mopts.malloc_guard = 0;
575 mopts.malloc_cache = MALLOC_DEFAULT_CACHE;
576 break;
577 case 'S':
578 mopts.malloc_freeunmap = mopts.malloc_junk = 1;
579 mopts.malloc_guard = MALLOC_PAGESIZE;
580 mopts.malloc_cache = 0;
581 break;
582 case 'u':
583 mopts.malloc_freeunmap = 0;
584 break;
585 case 'U':
586 mopts.malloc_freeunmap = 1;
587 break;
588 case 'x':
589 mopts.malloc_xmalloc = 0;
590 break;
591 case 'X':
592 mopts.malloc_xmalloc = 1;
593 break;
594 case 'z':
595 mopts.malloc_zero = 0;
596 break;
597 case 'Z':
598 mopts.malloc_zero = 1;
599 break;
600 default: {
601 static const char q[] = "malloc() warning: "
602 "unknown char in MALLOC_OPTIONS\n";
603 write(STDERR_FILENO, q, sizeof(q) - 1);
604 break;
605 }
606 }
607 }
608 }
609
610 /*
611 * We want junk in the entire allocation, and zero only in the part
612 * the user asked for.
613 */
614 if (mopts.malloc_zero)
615 mopts.malloc_junk = 1;
616
617 #ifdef MALLOC_STATS
618 if (mopts.malloc_stats && (atexit(malloc_exit) == -1)) {
619 static const char q[] = "malloc() warning: atexit(2) failed."
620 " Will not be able to dump stats on exit\n";
621 write(STDERR_FILENO, q, sizeof(q) - 1);
622 }
623 #endif /* MALLOC_STATS */
624
625 while ((mopts.malloc_canary = arc4random()) == 0)
626 ;
627
628 /*
629 * Allocate dir_info with a guard page on either side. Also
630 * randomise offset inside the page at which the dir_info
631 * lies (subject to alignment by 1 << MALLOC_MINSHIFT)
632 */
633 if ((p = MMAP(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2))) == MAP_FAILED)
634 return -1;
635 mprotect(p, MALLOC_PAGESIZE, PROT_NONE);
636 mprotect(p + MALLOC_PAGESIZE + DIR_INFO_RSZ,
637 MALLOC_PAGESIZE, PROT_NONE);
638 d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT;
639 d = (struct dir_info *)(p + MALLOC_PAGESIZE +
640 (arc4random_uniform(d_avail) << MALLOC_MINSHIFT));
641
642 d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS;
643 regioninfo_size = d->regions_total * sizeof(struct region_info);
644 d->r = MMAP(regioninfo_size);
645 if (d->r == MAP_FAILED) {
646 wrterror("malloc init mmap failed", NULL);
647 d->regions_total = 0;
648 return 1;
649 }
650 for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
651 LIST_INIT(&d->chunk_info_list[i]);
652 LIST_INIT(&d->chunk_dir[i]);
653 }
654 malloc_used += regioninfo_size;
655 d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
656 d->canary2 = ~d->canary1;
657
658 *dp = d;
659
660 /*
661 * Options have been set and will never be reset.
662 * Prevent further tampering with them.
663 */
664 if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0)
665 mprotect(&malloc_readonly, sizeof(malloc_readonly), PROT_READ);
666
667 return 0;
668 }
669
670 static int
omalloc_grow(struct dir_info * d)671 omalloc_grow(struct dir_info *d)
672 {
673 size_t newtotal;
674 size_t newsize;
675 size_t mask;
676 size_t i;
677 struct region_info *p;
678
679 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2 )
680 return 1;
681
682 newtotal = d->regions_total * 2;
683 newsize = newtotal * sizeof(struct region_info);
684 mask = newtotal - 1;
685
686 p = MMAP(newsize);
687 if (p == MAP_FAILED)
688 return 1;
689
690 malloc_used += newsize;
691 memset(p, 0, newsize);
692 STATS_ZERO(d->inserts);
693 STATS_ZERO(d->insert_collisions);
694 for (i = 0; i < d->regions_total; i++) {
695 void *q = d->r[i].p;
696 if (q != NULL) {
697 size_t indexv = hash(q) & mask;
698 STATS_INC(d->inserts);
699 while (p[indexv].p != NULL) {
700 indexv = (indexv - 1) & mask;
701 STATS_INC(d->insert_collisions);
702 }
703 p[indexv] = d->r[i];
704 }
705 }
706 /* avoid pages containing meta info to end up in cache */
707 if (munmap(d->r, d->regions_total * sizeof(struct region_info)))
708 wrterror("munmap", d->r);
709 else
710 malloc_used -= d->regions_total * sizeof(struct region_info);
711 d->regions_free = d->regions_free + d->regions_total;
712 d->regions_total = newtotal;
713 d->r = p;
714 return 0;
715 }
716
717 static struct chunk_info *
alloc_chunk_info(struct dir_info * d,int bits)718 alloc_chunk_info(struct dir_info *d, int bits)
719 {
720 struct chunk_info *p;
721 size_t size, count;
722
723 if (bits == 0)
724 count = MALLOC_PAGESIZE / MALLOC_MINSIZE;
725 else
726 count = MALLOC_PAGESIZE >> bits;
727
728 size = howmany(count, MALLOC_BITS);
729 size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short);
730 size = ALIGN(size);
731
732 if (LIST_EMPTY(&d->chunk_info_list[bits])) {
733 char *q;
734 size_t i;
735
736 q = MMAP(MALLOC_PAGESIZE);
737 if (q == MAP_FAILED)
738 return NULL;
739 malloc_used += MALLOC_PAGESIZE;
740 count = MALLOC_PAGESIZE / size;
741 for (i = 0; i < count; i++, q += size)
742 LIST_INSERT_HEAD(&d->chunk_info_list[bits],
743 (struct chunk_info *)q, entries);
744 }
745 p = LIST_FIRST(&d->chunk_info_list[bits]);
746 LIST_REMOVE(p, entries);
747 memset(p, 0, size);
748 p->canary = d->canary1;
749 return p;
750 }
751
752
753 /*
754 * The hashtable uses the assumption that p is never NULL. This holds since
755 * non-MAP_FIXED mappings with hint 0 start at BRKSIZ.
756 */
757 static int
insert(struct dir_info * d,void * p,size_t sz,void * f __unused)758 insert(struct dir_info *d, void *p, size_t sz, void *f __unused)
759 {
760 size_t indexv;
761 size_t mask;
762 void *q;
763
764 if (d->regions_free * 4 < d->regions_total) {
765 if (omalloc_grow(d))
766 return 1;
767 }
768 mask = d->regions_total - 1;
769 indexv = hash(p) & mask;
770 q = d->r[indexv].p;
771 STATS_INC(d->inserts);
772 while (q != NULL) {
773 indexv = (indexv - 1) & mask;
774 q = d->r[indexv].p;
775 STATS_INC(d->insert_collisions);
776 }
777 d->r[indexv].p = p;
778 d->r[indexv].size = sz;
779 #ifdef MALLOC_STATS
780 d->r[indexv].f = f;
781 #endif
782 d->regions_free--;
783 return 0;
784 }
785
786 static struct region_info *
find(struct dir_info * d,void * p)787 find(struct dir_info *d, void *p)
788 {
789 size_t indexv;
790 size_t mask = d->regions_total - 1;
791 void *q, *r;
792
793 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
794 d->canary1 != ~d->canary2)
795 wrterror("internal struct corrupt", NULL);
796 p = MASK_POINTER(p);
797 indexv = hash(p) & mask;
798 r = d->r[indexv].p;
799 q = MASK_POINTER(r);
800 STATS_INC(d->finds);
801 while (q != p && r != NULL) {
802 indexv = (indexv - 1) & mask;
803 r = d->r[indexv].p;
804 q = MASK_POINTER(r);
805 STATS_INC(d->find_collisions);
806 }
807 return (q == p && r != NULL) ? &d->r[indexv] : NULL;
808 }
809
810 static void
delete(struct dir_info * d,struct region_info * ri)811 delete(struct dir_info *d, struct region_info *ri)
812 {
813 /* algorithm R, Knuth Vol III section 6.4 */
814 size_t mask = d->regions_total - 1;
815 size_t i, j, r;
816
817 if (d->regions_total & (d->regions_total - 1))
818 wrterror("regions_total not 2^x", NULL);
819 d->regions_free++;
820 STATS_INC(g_pool->deletes);
821
822 i = ri - d->r;
823 for (;;) {
824 d->r[i].p = NULL;
825 d->r[i].size = 0;
826 j = i;
827 for (;;) {
828 i = (i - 1) & mask;
829 if (d->r[i].p == NULL)
830 return;
831 r = hash(d->r[i].p) & mask;
832 if ((i <= r && r < j) || (r < j && j < i) ||
833 (j < i && i <= r))
834 continue;
835 d->r[j] = d->r[i];
836 STATS_INC(g_pool->delete_moves);
837 break;
838 }
839
840 }
841 }
842
843 /*
844 * Allocate a page of chunks
845 */
846 static struct chunk_info *
omalloc_make_chunks(struct dir_info * d,int bits)847 omalloc_make_chunks(struct dir_info *d, int bits)
848 {
849 struct chunk_info *bp;
850 void *pp;
851 int i, k;
852
853 /* Allocate a new bucket */
854 pp = map(d, MALLOC_PAGESIZE, 0);
855 if (pp == MAP_FAILED)
856 return NULL;
857
858 bp = alloc_chunk_info(d, bits);
859 if (bp == NULL) {
860 unmap(d, pp, MALLOC_PAGESIZE);
861 return NULL;
862 }
863
864 /* memory protect the page allocated in the malloc(0) case */
865 if (bits == 0) {
866 bp->size = 0;
867 bp->shift = 1;
868 i = MALLOC_MINSIZE - 1;
869 while (i >>= 1)
870 bp->shift++;
871 bp->total = bp->free = MALLOC_PAGESIZE >> bp->shift;
872 bp->page = pp;
873
874 k = mprotect(pp, MALLOC_PAGESIZE, PROT_NONE);
875 if (k < 0) {
876 unmap(d, pp, MALLOC_PAGESIZE);
877 LIST_INSERT_HEAD(&d->chunk_info_list[0], bp, entries);
878 return NULL;
879 }
880 } else {
881 bp->size = 1U << bits;
882 bp->shift = bits;
883 bp->total = bp->free = MALLOC_PAGESIZE >> bits;
884 bp->page = pp;
885 }
886
887 /* set all valid bits in the bitmap */
888 k = bp->total;
889 i = 0;
890
891 /* Do a bunch at a time */
892 for (; (u_long)(k - i) >= MALLOC_BITS; i += MALLOC_BITS)
893 bp->bits[i / MALLOC_BITS] = (u_short)~0U;
894
895 for (; i < k; i++)
896 bp->bits[i / MALLOC_BITS] |= (u_short)1U << (i % MALLOC_BITS);
897
898 LIST_INSERT_HEAD(&d->chunk_dir[bits], bp, entries);
899
900 bits++;
901 if ((uintptr_t)pp & bits)
902 wrterror("pp & bits", pp);
903
904 insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp, NULL);
905 return bp;
906 }
907
908
909 /*
910 * Allocate a chunk
911 */
912 static void *
malloc_bytes(struct dir_info * d,size_t size,void * f __unused)913 malloc_bytes(struct dir_info *d, size_t size, void *f __unused)
914 {
915 int i, j;
916 size_t k;
917 u_short u, *lp;
918 struct chunk_info *bp;
919
920 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
921 d->canary1 != ~d->canary2)
922 wrterror("internal struct corrupt", NULL);
923 /* Don't bother with anything less than this */
924 /* unless we have a malloc(0) requests */
925 if (size != 0 && size < MALLOC_MINSIZE)
926 size = MALLOC_MINSIZE;
927
928 /* Find the right bucket */
929 if (size == 0)
930 j = 0;
931 else {
932 j = MALLOC_MINSHIFT;
933 i = (size - 1) >> (MALLOC_MINSHIFT - 1);
934 while (i >>= 1)
935 j++;
936 }
937
938 /* If it's empty, make a page more of that size chunks */
939 if (LIST_EMPTY(&d->chunk_dir[j])) {
940 bp = omalloc_make_chunks(d, j);
941 if (bp == NULL)
942 return NULL;
943 } else
944 bp = LIST_FIRST(&d->chunk_dir[j]);
945
946 if (bp->canary != d->canary1)
947 wrterror("chunk info corrupted", NULL);
948
949 i = d->chunk_start;
950 if (bp->free > 1)
951 i += getrnibble();
952 if (i >= bp->total)
953 i &= bp->total - 1;
954 for (;;) {
955 for (;;) {
956 lp = &bp->bits[i / MALLOC_BITS];
957 if (!*lp) {
958 i += MALLOC_BITS;
959 i &= ~(MALLOC_BITS - 1);
960 if (i >= bp->total)
961 i = 0;
962 } else
963 break;
964 }
965 k = i % MALLOC_BITS;
966 u = 1 << k;
967 if (*lp & u)
968 break;
969 if (++i >= bp->total)
970 i = 0;
971 }
972 d->chunk_start += i + 1;
973 #ifdef MALLOC_STATS
974 if (i == 0) {
975 struct region_info *r = find(d, bp->page);
976 r->f = f;
977 }
978 #endif
979
980 *lp ^= u;
981
982 /* If there are no more free, remove from free-list */
983 if (!--bp->free)
984 LIST_REMOVE(bp, entries);
985
986 /* Adjust to the real offset of that chunk */
987 k += (lp - bp->bits) * MALLOC_BITS;
988 k <<= bp->shift;
989
990 if (mopts.malloc_junk && bp->size > 0)
991 memset((char *)bp->page + k, SOME_JUNK, bp->size);
992 return ((char *)bp->page + k);
993 }
994
995
996 /*
997 * Free a chunk, and possibly the page it's on, if the page becomes empty.
998 */
999 static void
free_bytes(struct dir_info * d,struct region_info * r,void * ptr)1000 free_bytes(struct dir_info *d, struct region_info *r, void *ptr)
1001 {
1002 struct chunk_head *mp;
1003 struct chunk_info *info;
1004 int i;
1005
1006 info = (struct chunk_info *)r->size;
1007 if (info->canary != d->canary1)
1008 wrterror("chunk info corrupted", NULL);
1009
1010 /* Find the chunk number on the page */
1011 i = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift;
1012
1013 if ((uintptr_t)ptr & ((1U << (info->shift)) - 1)) {
1014 wrterror("modified chunk-pointer", ptr);
1015 return;
1016 }
1017 if (info->bits[i / MALLOC_BITS] & (1U << (i % MALLOC_BITS))) {
1018 wrterror("chunk is already free", ptr);
1019 return;
1020 }
1021
1022 info->bits[i / MALLOC_BITS] |= 1U << (i % MALLOC_BITS);
1023 info->free++;
1024
1025 if (info->size != 0)
1026 mp = d->chunk_dir + info->shift;
1027 else
1028 mp = d->chunk_dir;
1029
1030 if (info->free == 1) {
1031 /* Page became non-full */
1032 LIST_INSERT_HEAD(mp, info, entries);
1033 return;
1034 }
1035 if (info->free != info->total)
1036 return;
1037
1038 LIST_REMOVE(info, entries);
1039
1040 if (info->size == 0 && !mopts.malloc_freeunmap)
1041 mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE);
1042 unmap(d, info->page, MALLOC_PAGESIZE);
1043
1044 delete(d, r);
1045 if (info->size != 0)
1046 mp = &d->chunk_info_list[info->shift];
1047 else
1048 mp = &d->chunk_info_list[0];
1049 LIST_INSERT_HEAD(mp, info, entries);
1050 }
1051
1052
1053
1054 static void *
omalloc(size_t sz,int zero_fill,void * f)1055 omalloc(size_t sz, int zero_fill, void *f)
1056 {
1057 void *p;
1058 size_t psz;
1059
1060 if (sz > MALLOC_MAXCHUNK) {
1061 if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1062 errno = ENOMEM;
1063 return NULL;
1064 }
1065 sz += mopts.malloc_guard;
1066 psz = PAGEROUND(sz);
1067 p = map(g_pool, psz, zero_fill);
1068 if (p == MAP_FAILED) {
1069 errno = ENOMEM;
1070 return NULL;
1071 }
1072 if (insert(g_pool, p, sz, f)) {
1073 unmap(g_pool, p, psz);
1074 errno = ENOMEM;
1075 return NULL;
1076 }
1077 if (mopts.malloc_guard) {
1078 if (mprotect((char *)p + psz - mopts.malloc_guard,
1079 mopts.malloc_guard, PROT_NONE))
1080 wrterror("mprotect", NULL);
1081 malloc_guarded += mopts.malloc_guard;
1082 }
1083
1084 if (mopts.malloc_move &&
1085 sz - mopts.malloc_guard < MALLOC_PAGESIZE -
1086 MALLOC_LEEWAY) {
1087 /* fill whole allocation */
1088 if (mopts.malloc_junk)
1089 memset(p, SOME_JUNK, psz - mopts.malloc_guard);
1090 /* shift towards the end */
1091 p = ((char *)p) + ((MALLOC_PAGESIZE - MALLOC_LEEWAY -
1092 (sz - mopts.malloc_guard)) & ~(MALLOC_MINSIZE-1));
1093 /* fill zeros if needed and overwritten above */
1094 if (zero_fill && mopts.malloc_junk)
1095 memset(p, 0, sz - mopts.malloc_guard);
1096 } else {
1097 if (mopts.malloc_junk) {
1098 if (zero_fill)
1099 memset((char *)p + sz - mopts.malloc_guard,
1100 SOME_JUNK, psz - sz);
1101 else
1102 memset(p, SOME_JUNK,
1103 psz - mopts.malloc_guard);
1104 }
1105 }
1106
1107 } else {
1108 /* takes care of SOME_JUNK */
1109 p = malloc_bytes(g_pool, sz, f);
1110 if (zero_fill && p != NULL && sz > 0)
1111 memset(p, 0, sz);
1112 }
1113
1114 return p;
1115 }
1116
1117 /*
1118 * Common function for handling recursion. Only
1119 * print the error message once, to avoid making the problem
1120 * potentially worse.
1121 */
1122 static void
malloc_recurse(void)1123 malloc_recurse(void)
1124 {
1125 static int noprint;
1126
1127 if (noprint == 0) {
1128 noprint = 1;
1129 wrterror("recursive call", NULL);
1130 }
1131 malloc_active--;
1132 _MALLOC_UNLOCK();
1133 errno = EDEADLK;
1134 }
1135
1136 static int
malloc_init(void)1137 malloc_init(void)
1138 {
1139 if (omalloc_init(&g_pool)) {
1140 _MALLOC_UNLOCK();
1141 if (mopts.malloc_xmalloc)
1142 wrterror("out of memory", NULL);
1143 errno = ENOMEM;
1144 return -1;
1145 }
1146 return 0;
1147 }
1148
1149 void *
malloc(size_t size)1150 malloc(size_t size)
1151 {
1152 void *r;
1153 int saved_errno = errno;
1154
1155 _MALLOC_LOCK();
1156 malloc_func = " in malloc():";
1157 if (g_pool == NULL) {
1158 if (malloc_init() != 0)
1159 return NULL;
1160 }
1161 if (malloc_active++) {
1162 malloc_recurse();
1163 return NULL;
1164 }
1165 r = omalloc(size, mopts.malloc_zero, CALLER);
1166 malloc_active--;
1167 _MALLOC_UNLOCK();
1168 if (r == NULL && mopts.malloc_xmalloc) {
1169 wrterror("out of memory", NULL);
1170 errno = ENOMEM;
1171 }
1172 if (r != NULL)
1173 errno = saved_errno;
1174 return r;
1175 }
1176
1177 static void
ofree(void * p)1178 ofree(void *p)
1179 {
1180 struct region_info *r;
1181 size_t sz;
1182
1183 r = find(g_pool, p);
1184 if (r == NULL) {
1185 wrterror("bogus pointer (double free?)", p);
1186 return;
1187 }
1188 REALSIZE(sz, r);
1189 if (sz > MALLOC_MAXCHUNK) {
1190 if (sz - mopts.malloc_guard >= MALLOC_PAGESIZE -
1191 MALLOC_LEEWAY) {
1192 if (r->p != p) {
1193 wrterror("bogus pointer", p);
1194 return;
1195 }
1196 } else {
1197 #ifdef notyetbecause_of_realloc
1198 /* shifted towards the end */
1199 if (p != ((char *)r->p) + ((MALLOC_PAGESIZE -
1200 MALLOC_MINSIZE - sz - mopts.malloc_guard) &
1201 ~(MALLOC_MINSIZE-1))) {
1202 }
1203 #endif
1204 p = r->p;
1205 }
1206 if (mopts.malloc_guard) {
1207 if (sz < mopts.malloc_guard)
1208 wrterror("guard size", NULL);
1209 if (!mopts.malloc_freeunmap) {
1210 if (mprotect((char *)p + PAGEROUND(sz) -
1211 mopts.malloc_guard, mopts.malloc_guard,
1212 PROT_READ | PROT_WRITE))
1213 wrterror("mprotect", NULL);
1214 }
1215 malloc_guarded -= mopts.malloc_guard;
1216 }
1217 if (mopts.malloc_junk && !mopts.malloc_freeunmap)
1218 memset(p, SOME_FREEJUNK,
1219 PAGEROUND(sz) - mopts.malloc_guard);
1220 unmap(g_pool, p, PAGEROUND(sz));
1221 delete(g_pool, r);
1222 } else {
1223 void *tmp;
1224 int i;
1225
1226 if (mopts.malloc_junk && sz > 0)
1227 memset(p, SOME_FREEJUNK, sz);
1228 if (!mopts.malloc_freenow) {
1229 i = getrnibble();
1230 tmp = p;
1231 p = g_pool->delayed_chunks[i];
1232 g_pool->delayed_chunks[i] = tmp;
1233 }
1234 if (p != NULL) {
1235 r = find(g_pool, p);
1236 if (r == NULL) {
1237 wrterror("bogus pointer (double free?)", p);
1238 return;
1239 }
1240 free_bytes(g_pool, r, p);
1241 }
1242 }
1243 }
1244
1245 void
free(void * ptr)1246 free(void *ptr)
1247 {
1248 int saved_errno = errno;
1249
1250 /* This is legal. */
1251 if (ptr == NULL)
1252 return;
1253
1254 _MALLOC_LOCK();
1255 malloc_func = " in free():";
1256 if (g_pool == NULL) {
1257 _MALLOC_UNLOCK();
1258 wrterror("free() called before allocation", NULL);
1259 return;
1260 }
1261 if (malloc_active++) {
1262 malloc_recurse();
1263 return;
1264 }
1265 ofree(ptr);
1266 malloc_active--;
1267 _MALLOC_UNLOCK();
1268 errno = saved_errno;
1269 }
1270
1271
1272 static void *
orealloc(void * p,size_t newsz,void * f)1273 orealloc(void *p, size_t newsz, void *f)
1274 {
1275 struct region_info *r;
1276 size_t oldsz, goldsz, gnewsz;
1277 void *q;
1278
1279 if (p == NULL)
1280 return omalloc(newsz, 0, f);
1281
1282 r = find(g_pool, p);
1283 if (r == NULL) {
1284 wrterror("bogus pointer (double free?)", p);
1285 return NULL;
1286 }
1287 if (newsz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1288 errno = ENOMEM;
1289 return NULL;
1290 }
1291
1292 REALSIZE(oldsz, r);
1293 goldsz = oldsz;
1294 if (oldsz > MALLOC_MAXCHUNK) {
1295 if (oldsz < mopts.malloc_guard)
1296 wrterror("guard size", NULL);
1297 oldsz -= mopts.malloc_guard;
1298 }
1299
1300 gnewsz = newsz;
1301 if (gnewsz > MALLOC_MAXCHUNK)
1302 gnewsz += mopts.malloc_guard;
1303
1304 if (newsz > MALLOC_MAXCHUNK && oldsz > MALLOC_MAXCHUNK && p == r->p &&
1305 !mopts.malloc_realloc) {
1306 size_t roldsz = PAGEROUND(goldsz);
1307 size_t rnewsz = PAGEROUND(gnewsz);
1308
1309 if (rnewsz > roldsz) {
1310 if (!mopts.malloc_guard) {
1311 void *hint = (char *)p + roldsz;
1312 size_t needed = rnewsz - roldsz;
1313
1314 STATS_INC(g_pool->cheap_realloc_tries);
1315 zapcacheregion(g_pool, hint, needed);
1316 q = MQUERY(hint, needed);
1317 if (q == hint)
1318 q = MMAPA(hint, needed);
1319 else
1320 q = MAP_FAILED;
1321 if (q == hint) {
1322 malloc_used += needed;
1323 if (mopts.malloc_junk)
1324 memset(q, SOME_JUNK, needed);
1325 r->size = newsz;
1326 STATS_SETF(r, f);
1327 STATS_INC(g_pool->cheap_reallocs);
1328 return p;
1329 } else if (q != MAP_FAILED) {
1330 if (munmap(q, needed))
1331 wrterror("munmap", q);
1332 }
1333 }
1334 } else if (rnewsz < roldsz) {
1335 if (mopts.malloc_guard) {
1336 if (mprotect((char *)p + roldsz -
1337 mopts.malloc_guard, mopts.malloc_guard,
1338 PROT_READ | PROT_WRITE))
1339 wrterror("mprotect", NULL);
1340 if (mprotect((char *)p + rnewsz -
1341 mopts.malloc_guard, mopts.malloc_guard,
1342 PROT_NONE))
1343 wrterror("mprotect", NULL);
1344 }
1345 unmap(g_pool, (char *)p + rnewsz, roldsz - rnewsz);
1346 r->size = gnewsz;
1347 STATS_SETF(r, f);
1348 return p;
1349 } else {
1350 if (newsz > oldsz && mopts.malloc_junk)
1351 memset((char *)p + newsz, SOME_JUNK,
1352 rnewsz - mopts.malloc_guard - newsz);
1353 r->size = gnewsz;
1354 STATS_SETF(r, f);
1355 return p;
1356 }
1357 }
1358 if (newsz <= oldsz && newsz > oldsz / 2 && !mopts.malloc_realloc) {
1359 if (mopts.malloc_junk && newsz > 0)
1360 memset((char *)p + newsz, SOME_JUNK, oldsz - newsz);
1361 STATS_SETF(r, f);
1362 return p;
1363 } else if (newsz != oldsz || mopts.malloc_realloc) {
1364 q = omalloc(newsz, 0, f);
1365 if (q == NULL)
1366 return NULL;
1367 if (newsz != 0 && oldsz != 0)
1368 memcpy(q, p, oldsz < newsz ? oldsz : newsz);
1369 ofree(p);
1370 return q;
1371 } else {
1372 STATS_SETF(r, f);
1373 return p;
1374 }
1375 }
1376
1377 void *
realloc(void * ptr,size_t size)1378 realloc(void *ptr, size_t size)
1379 {
1380 void *r;
1381 int saved_errno = errno;
1382
1383 _MALLOC_LOCK();
1384 malloc_func = " in realloc():";
1385 if (g_pool == NULL) {
1386 if (malloc_init() != 0)
1387 return NULL;
1388 }
1389 if (malloc_active++) {
1390 malloc_recurse();
1391 return NULL;
1392 }
1393 r = orealloc(ptr, size, CALLER);
1394
1395 malloc_active--;
1396 _MALLOC_UNLOCK();
1397 if (r == NULL && mopts.malloc_xmalloc) {
1398 wrterror("out of memory", NULL);
1399 errno = ENOMEM;
1400 }
1401 if (r != NULL)
1402 errno = saved_errno;
1403 return r;
1404 }
1405
1406
1407 #define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
1408
1409 void *
calloc(size_t nmemb,size_t size)1410 calloc(size_t nmemb, size_t size)
1411 {
1412 void *r;
1413 int saved_errno = errno;
1414
1415 _MALLOC_LOCK();
1416 malloc_func = " in calloc():";
1417 if (g_pool == NULL) {
1418 if (malloc_init() != 0)
1419 return NULL;
1420 }
1421 if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1422 nmemb > 0 && SIZE_MAX / nmemb < size) {
1423 _MALLOC_UNLOCK();
1424 if (mopts.malloc_xmalloc)
1425 wrterror("out of memory", NULL);
1426 errno = ENOMEM;
1427 return NULL;
1428 }
1429
1430 if (malloc_active++) {
1431 malloc_recurse();
1432 return NULL;
1433 }
1434
1435 size *= nmemb;
1436 r = omalloc(size, 1, CALLER);
1437
1438 malloc_active--;
1439 _MALLOC_UNLOCK();
1440 if (r == NULL && mopts.malloc_xmalloc) {
1441 wrterror("out of memory", NULL);
1442 errno = ENOMEM;
1443 }
1444 if (r != NULL)
1445 errno = saved_errno;
1446 return r;
1447 }
1448
1449 static void *
mapalign(struct dir_info * d,size_t alignment,size_t sz,int zero_fill)1450 mapalign(struct dir_info *d, size_t alignment, size_t sz, int zero_fill)
1451 {
1452 char *p, *q;
1453
1454 if (alignment < MALLOC_PAGESIZE || ((alignment - 1) & alignment) != 0) {
1455 wrterror("mapalign bad alignment", NULL);
1456 return MAP_FAILED;
1457 }
1458 if (sz != PAGEROUND(sz)) {
1459 wrterror("mapalign round", NULL);
1460 return MAP_FAILED;
1461 }
1462
1463 /* Allocate sz + alignment bytes of memory, which must include a
1464 * subrange of size bytes that is properly aligned. Unmap the
1465 * other bytes, and then return that subrange.
1466 */
1467
1468 /* We need sz + alignment to fit into a size_t. */
1469 if (alignment > SIZE_MAX - sz)
1470 return MAP_FAILED;
1471
1472 p = map(d, sz + alignment, zero_fill);
1473 if (p == MAP_FAILED)
1474 return MAP_FAILED;
1475 q = (char *)(((uintptr_t)p + alignment - 1) & ~(alignment - 1));
1476 if (q != p) {
1477 if (munmap(p, q - p))
1478 wrterror("munmap", p);
1479 }
1480 if (munmap(q + sz, alignment - (q - p)))
1481 wrterror("munmap", q + sz);
1482 malloc_used -= alignment;
1483
1484 return q;
1485 }
1486
1487 static void *
omemalign(size_t alignment,size_t sz,int zero_fill,void * f)1488 omemalign(size_t alignment, size_t sz, int zero_fill, void *f)
1489 {
1490 size_t psz;
1491 void *p;
1492
1493 if (alignment <= MALLOC_PAGESIZE) {
1494 /*
1495 * max(size, alignment) is enough to assure the requested alignment,
1496 * since the allocator always allocates power-of-two blocks.
1497 */
1498 if (sz < alignment)
1499 sz = alignment;
1500 return omalloc(sz, zero_fill, f);
1501 }
1502
1503 if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1504 errno = ENOMEM;
1505 return NULL;
1506 }
1507
1508 sz += mopts.malloc_guard;
1509 psz = PAGEROUND(sz);
1510
1511 p = mapalign(g_pool, alignment, psz, zero_fill);
1512 if (p == NULL) {
1513 errno = ENOMEM;
1514 return NULL;
1515 }
1516
1517 if (insert(g_pool, p, sz, f)) {
1518 unmap(g_pool, p, psz);
1519 errno = ENOMEM;
1520 return NULL;
1521 }
1522
1523 if (mopts.malloc_guard) {
1524 if (mprotect((char *)p + psz - mopts.malloc_guard,
1525 mopts.malloc_guard, PROT_NONE))
1526 wrterror("mprotect", NULL);
1527 malloc_guarded += mopts.malloc_guard;
1528 }
1529
1530 if (mopts.malloc_junk) {
1531 if (zero_fill)
1532 memset((char *)p + sz - mopts.malloc_guard,
1533 SOME_JUNK, psz - sz);
1534 else
1535 memset(p, SOME_JUNK, psz - mopts.malloc_guard);
1536 }
1537
1538 return p;
1539 }
1540
1541 int
posix_memalign(void ** memptr,size_t alignment,size_t size)1542 posix_memalign(void **memptr, size_t alignment, size_t size)
1543 {
1544 int res, saved_errno = errno;
1545 void *r;
1546
1547 /* Make sure that alignment is a large enough power of 2. */
1548 if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *))
1549 return EINVAL;
1550
1551 _MALLOC_LOCK();
1552 malloc_func = " in posix_memalign():";
1553 if (g_pool == NULL) {
1554 if (malloc_init() != 0)
1555 goto err;
1556 }
1557 if (malloc_active++) {
1558 malloc_recurse();
1559 goto err;
1560 }
1561 r = omemalign(alignment, size, mopts.malloc_zero, CALLER);
1562 malloc_active--;
1563 _MALLOC_UNLOCK();
1564 if (r == NULL) {
1565 if (mopts.malloc_xmalloc) {
1566 wrterror("out of memory", NULL);
1567 errno = ENOMEM;
1568 }
1569 goto err;
1570 }
1571 errno = saved_errno;
1572 *memptr = r;
1573 return 0;
1574
1575 err:
1576 res = errno;
1577 errno = saved_errno;
1578 return res;
1579 }
1580
1581 #ifdef MALLOC_STATS
1582
1583 struct malloc_leak {
1584 void (*f)();
1585 size_t total_size;
1586 int count;
1587 };
1588
1589 struct leaknode {
1590 RB_ENTRY(leaknode) entry;
1591 struct malloc_leak d;
1592 };
1593
1594 static int
leakcmp(struct leaknode * e1,struct leaknode * e2)1595 leakcmp(struct leaknode *e1, struct leaknode *e2)
1596 {
1597 return e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f;
1598 }
1599
1600 static RB_HEAD(leaktree, leaknode) leakhead;
RB_GENERATE_STATIC(leaktree,leaknode,entry,leakcmp)1601 RB_GENERATE_STATIC(leaktree, leaknode, entry, leakcmp)
1602
1603 static void
1604 putleakinfo(void *f, size_t sz, int cnt)
1605 {
1606 struct leaknode key, *p;
1607 static struct leaknode *page;
1608 static int used;
1609
1610 if (cnt == 0)
1611 return;
1612
1613 key.d.f = f;
1614 p = RB_FIND(leaktree, &leakhead, &key);
1615 if (p == NULL) {
1616 if (page == NULL ||
1617 used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) {
1618 page = MMAP(MALLOC_PAGESIZE);
1619 if (page == MAP_FAILED)
1620 return;
1621 used = 0;
1622 }
1623 p = &page[used++];
1624 p->d.f = f;
1625 p->d.total_size = sz * cnt;
1626 p->d.count = cnt;
1627 RB_INSERT(leaktree, &leakhead, p);
1628 } else {
1629 p->d.total_size += sz * cnt;
1630 p->d.count += cnt;
1631 }
1632 }
1633
1634 static struct malloc_leak *malloc_leaks;
1635
1636 static void
dump_leaks(int fd)1637 dump_leaks(int fd)
1638 {
1639 struct leaknode *p;
1640 char buf[64];
1641 int i = 0;
1642
1643 snprintf(buf, sizeof(buf), "Leak report\n");
1644 write(fd, buf, strlen(buf));
1645 snprintf(buf, sizeof(buf), " f sum # avg\n");
1646 write(fd, buf, strlen(buf));
1647 /* XXX only one page of summary */
1648 if (malloc_leaks == NULL)
1649 malloc_leaks = MMAP(MALLOC_PAGESIZE);
1650 if (malloc_leaks != MAP_FAILED)
1651 memset(malloc_leaks, 0, MALLOC_PAGESIZE);
1652 RB_FOREACH(p, leaktree, &leakhead) {
1653 snprintf(buf, sizeof(buf), "%12p %7zu %6u %6zu\n", p->d.f,
1654 p->d.total_size, p->d.count, p->d.total_size / p->d.count);
1655 write(fd, buf, strlen(buf));
1656 if (malloc_leaks == MAP_FAILED ||
1657 i >= MALLOC_PAGESIZE / sizeof(struct malloc_leak))
1658 continue;
1659 malloc_leaks[i].f = p->d.f;
1660 malloc_leaks[i].total_size = p->d.total_size;
1661 malloc_leaks[i].count = p->d.count;
1662 i++;
1663 }
1664 }
1665
1666 static void
dump_chunk(int fd,struct chunk_info * p,void * f,int fromfreelist)1667 dump_chunk(int fd, struct chunk_info *p, void *f, int fromfreelist)
1668 {
1669 char buf[64];
1670
1671 while (p != NULL) {
1672 snprintf(buf, sizeof(buf), "chunk %12p %12p %4d %d/%d\n",
1673 p->page, ((p->bits[0] & 1) ? NULL : f),
1674 p->size, p->free, p->total);
1675 write(fd, buf, strlen(buf));
1676 if (!fromfreelist) {
1677 if (p->bits[0] & 1)
1678 putleakinfo(NULL, p->size, p->total - p->free);
1679 else {
1680 putleakinfo(f, p->size, 1);
1681 putleakinfo(NULL, p->size,
1682 p->total - p->free - 1);
1683 }
1684 break;
1685 }
1686 p = LIST_NEXT(p, entries);
1687 if (p != NULL) {
1688 snprintf(buf, sizeof(buf), " ");
1689 write(fd, buf, strlen(buf));
1690 }
1691 }
1692 }
1693
1694 static void
dump_free_chunk_info(int fd,struct dir_info * d)1695 dump_free_chunk_info(int fd, struct dir_info *d)
1696 {
1697 char buf[64];
1698 int i, count;
1699
1700 snprintf(buf, sizeof(buf), "Free chunk structs:\n");
1701 write(fd, buf, strlen(buf));
1702 for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
1703 struct chunk_info *p;
1704
1705 count = 0;
1706 LIST_FOREACH(p, &d->chunk_info_list[i], entries)
1707 count++;
1708 p = LIST_FIRST(&d->chunk_dir[i]);
1709 if (p == NULL && count == 0)
1710 continue;
1711 snprintf(buf, sizeof(buf), "%2d) %3d ", i, count);
1712 write(fd, buf, strlen(buf));
1713 if (p != NULL)
1714 dump_chunk(fd, p, NULL, 1);
1715 else
1716 write(fd, "\n", 1);
1717 }
1718
1719 }
1720
1721 static void
dump_free_page_info(int fd,struct dir_info * d)1722 dump_free_page_info(int fd, struct dir_info *d)
1723 {
1724 char buf[64];
1725 int i;
1726
1727 snprintf(buf, sizeof(buf), "Free pages cached: %zu\n",
1728 d->free_regions_size);
1729 write(fd, buf, strlen(buf));
1730 for (i = 0; i < mopts.malloc_cache; i++) {
1731 if (d->free_regions[i].p != NULL) {
1732 snprintf(buf, sizeof(buf), "%2d) ", i);
1733 write(fd, buf, strlen(buf));
1734 snprintf(buf, sizeof(buf), "free at %p: %zu\n",
1735 d->free_regions[i].p, d->free_regions[i].size);
1736 write(fd, buf, strlen(buf));
1737 }
1738 }
1739 }
1740
1741 static void
malloc_dump1(int fd,struct dir_info * d)1742 malloc_dump1(int fd, struct dir_info *d)
1743 {
1744 char buf[64];
1745 size_t i, realsize;
1746
1747 snprintf(buf, sizeof(buf), "Malloc dir of %s at %p\n", __progname, d);
1748 write(fd, buf, strlen(buf));
1749 if (d == NULL)
1750 return;
1751 snprintf(buf, sizeof(buf), "Region slots free %zu/%zu\n",
1752 d->regions_free, d->regions_total);
1753 write(fd, buf, strlen(buf));
1754 snprintf(buf, sizeof(buf), "Finds %zu/%zu\n", d->finds,
1755 d->find_collisions);
1756 write(fd, buf, strlen(buf));
1757 snprintf(buf, sizeof(buf), "Inserts %zu/%zu\n", d->inserts,
1758 d->insert_collisions);
1759 write(fd, buf, strlen(buf));
1760 snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes,
1761 d->delete_moves);
1762 write(fd, buf, strlen(buf));
1763 snprintf(buf, sizeof(buf), "Cheap reallocs %zu/%zu\n",
1764 d->cheap_reallocs, d->cheap_realloc_tries);
1765 write(fd, buf, strlen(buf));
1766 dump_free_chunk_info(fd, d);
1767 dump_free_page_info(fd, d);
1768 snprintf(buf, sizeof(buf),
1769 "slot) hash d type page f size [free/n]\n");
1770 write(fd, buf, strlen(buf));
1771 for (i = 0; i < d->regions_total; i++) {
1772 if (d->r[i].p != NULL) {
1773 size_t h = hash(d->r[i].p) &
1774 (d->regions_total - 1);
1775 snprintf(buf, sizeof(buf), "%4zx) #%4zx %zd ",
1776 i, h, h - i);
1777 write(fd, buf, strlen(buf));
1778 REALSIZE(realsize, &d->r[i]);
1779 if (realsize > MALLOC_MAXCHUNK) {
1780 putleakinfo(d->r[i].f, realsize, 1);
1781 snprintf(buf, sizeof(buf),
1782 "pages %12p %12p %zu\n", d->r[i].p,
1783 d->r[i].f, realsize);
1784 write(fd, buf, strlen(buf));
1785 } else
1786 dump_chunk(fd,
1787 (struct chunk_info *)d->r[i].size,
1788 d->r[i].f, 0);
1789 }
1790 }
1791 snprintf(buf, sizeof(buf), "In use %zu\n", malloc_used);
1792 write(fd, buf, strlen(buf));
1793 snprintf(buf, sizeof(buf), "Guarded %zu\n", malloc_guarded);
1794 write(fd, buf, strlen(buf));
1795 dump_leaks(fd);
1796 write(fd, "\n", 1);
1797 }
1798
1799 void
malloc_dump(int fd)1800 malloc_dump(int fd)
1801 {
1802 int i;
1803 void *p;
1804 struct region_info *r;
1805 int saved_errno = errno;
1806
1807 for (i = 0; i <= MALLOC_DELAYED_CHUNKS; i++) {
1808 p = g_pool->delayed_chunks[i];
1809 if (p == NULL)
1810 continue;
1811 r = find(g_pool, p);
1812 if (r == NULL)
1813 wrterror("bogus pointer in malloc_dump", p);
1814 free_bytes(g_pool, r, p);
1815 g_pool->delayed_chunks[i] = NULL;
1816 }
1817 /* XXX leak when run multiple times */
1818 RB_INIT(&leakhead);
1819 malloc_dump1(fd, g_pool);
1820 errno = saved_errno;
1821 }
1822
1823 static void
malloc_exit(void)1824 malloc_exit(void)
1825 {
1826 static const char q[] = "malloc() warning: Couldn't dump stats\n";
1827 int save_errno = errno, fd;
1828
1829 fd = open("malloc.out", O_RDWR|O_APPEND);
1830 if (fd != -1) {
1831 malloc_dump(fd);
1832 close(fd);
1833 } else
1834 write(STDERR_FILENO, q, sizeof(q) - 1);
1835 errno = save_errno;
1836 }
1837
1838 #endif /* MALLOC_STATS */
1839