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