xref: /openbsd-src/lib/libc/stdlib/malloc.c (revision c7e8ea31cd41a963f06f0a8ba93948b06aa6b4a4)
1 /*	$OpenBSD: malloc.c,v 1.229 2017/08/20 11:06:16 otto Exp $	*/
2 /*
3  * Copyright (c) 2008, 2010, 2011, 2016 Otto Moerbeek <otto@drijf.net>
4  * Copyright (c) 2012 Matthew Dempsky <matthew@openbsd.org>
5  * Copyright (c) 2008 Damien Miller <djm@openbsd.org>
6  * Copyright (c) 2000 Poul-Henning Kamp <phk@FreeBSD.org>
7  *
8  * Permission to use, copy, modify, and distribute this software for any
9  * purpose with or without fee is hereby granted, provided that the above
10  * copyright notice and this permission notice appear in all copies.
11  *
12  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19  */
20 
21 /*
22  * If we meet some day, and you think this stuff is worth it, you
23  * can buy me a beer in return. Poul-Henning Kamp
24  */
25 
26 /* #define MALLOC_STATS */
27 
28 #include <sys/types.h>
29 #include <sys/param.h>	/* PAGE_SHIFT ALIGN */
30 #include <sys/queue.h>
31 #include <sys/mman.h>
32 #include <sys/uio.h>
33 #include <errno.h>
34 #include <stdarg.h>
35 #include <stdint.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <stdio.h>
39 #include <unistd.h>
40 
41 #ifdef MALLOC_STATS
42 #include <sys/tree.h>
43 #include <fcntl.h>
44 #endif
45 
46 #include "thread_private.h"
47 #include <tib.h>
48 
49 #if defined(__mips64__)
50 #define MALLOC_PAGESHIFT	(14U)
51 #else
52 #define MALLOC_PAGESHIFT	(PAGE_SHIFT)
53 #endif
54 
55 #define MALLOC_MINSHIFT		4
56 #define MALLOC_MAXSHIFT		(MALLOC_PAGESHIFT - 1)
57 #define MALLOC_PAGESIZE		(1UL << MALLOC_PAGESHIFT)
58 #define MALLOC_MINSIZE		(1UL << MALLOC_MINSHIFT)
59 #define MALLOC_PAGEMASK		(MALLOC_PAGESIZE - 1)
60 #define MASK_POINTER(p)		((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK))
61 
62 #define MALLOC_MAXCHUNK		(1 << MALLOC_MAXSHIFT)
63 #define MALLOC_MAXCACHE		256
64 #define MALLOC_DELAYED_CHUNK_MASK	15
65 #define MALLOC_INITIAL_REGIONS	512
66 #define MALLOC_DEFAULT_CACHE	64
67 #define MALLOC_CHUNK_LISTS	4
68 #define CHUNK_CHECK_LENGTH	32
69 
70 /*
71  * We move allocations between half a page and a whole page towards the end,
72  * subject to alignment constraints. This is the extra headroom we allow.
73  * Set to zero to be the most strict.
74  */
75 #define MALLOC_LEEWAY		0
76 #define MALLOC_MOVE_COND(sz)	((sz) - mopts.malloc_guard < 		\
77 				    MALLOC_PAGESIZE - MALLOC_LEEWAY)
78 #define MALLOC_MOVE(p, sz)  	(((char *)(p)) +			\
79 				    ((MALLOC_PAGESIZE - MALLOC_LEEWAY -	\
80 			    	    ((sz) - mopts.malloc_guard)) & 	\
81 				    ~(MALLOC_MINSIZE - 1)))
82 
83 #define PAGEROUND(x)  (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK)
84 
85 /*
86  * What to use for Junk.  This is the byte value we use to fill with
87  * when the 'J' option is enabled. Use SOME_JUNK right after alloc,
88  * and SOME_FREEJUNK right before free.
89  */
90 #define SOME_JUNK		0xdb	/* deadbeef */
91 #define SOME_FREEJUNK		0xdf	/* dead, free */
92 
93 #define MMAP(sz)	mmap(NULL, (sz), PROT_READ | PROT_WRITE, \
94     MAP_ANON | MAP_PRIVATE, -1, 0)
95 
96 #define MMAPA(a,sz)	mmap((a), (sz), PROT_READ | PROT_WRITE, \
97     MAP_ANON | MAP_PRIVATE, -1, 0)
98 
99 #define MQUERY(a, sz)	mquery((a), (sz), PROT_READ | PROT_WRITE, \
100     MAP_ANON | MAP_PRIVATE | MAP_FIXED, -1, 0)
101 
102 struct region_info {
103 	void *p;		/* page; low bits used to mark chunks */
104 	uintptr_t size;		/* size for pages, or chunk_info pointer */
105 #ifdef MALLOC_STATS
106 	void *f;		/* where allocated from */
107 #endif
108 };
109 
110 LIST_HEAD(chunk_head, chunk_info);
111 
112 struct dir_info {
113 	u_int32_t canary1;
114 	int active;			/* status of malloc */
115 	struct region_info *r;		/* region slots */
116 	size_t regions_total;		/* number of region slots */
117 	size_t regions_free;		/* number of free slots */
118 					/* lists of free chunk info structs */
119 	struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1];
120 					/* lists of chunks with free slots */
121 	struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS];
122 	size_t free_regions_size;	/* free pages cached */
123 					/* free pages cache */
124 	struct region_info free_regions[MALLOC_MAXCACHE];
125 					/* delayed free chunk slots */
126 	void *delayed_chunks[MALLOC_DELAYED_CHUNK_MASK + 1];
127 	size_t rbytesused;		/* random bytes used */
128 	char *func;			/* current function */
129 	int mutex;
130 	u_char rbytes[32];		/* random bytes */
131 	u_short chunk_start;
132 #ifdef MALLOC_STATS
133 	size_t inserts;
134 	size_t insert_collisions;
135 	size_t finds;
136 	size_t find_collisions;
137 	size_t deletes;
138 	size_t delete_moves;
139 	size_t cheap_realloc_tries;
140 	size_t cheap_reallocs;
141 	size_t malloc_used;		/* bytes allocated */
142 	size_t malloc_guarded;		/* bytes used for guards */
143 #define STATS_ADD(x,y)	((x) += (y))
144 #define STATS_SUB(x,y)	((x) -= (y))
145 #define STATS_INC(x)	((x)++)
146 #define STATS_ZERO(x)	((x) = 0)
147 #define STATS_SETF(x,y)	((x)->f = (y))
148 #else
149 #define STATS_ADD(x,y)	/* nothing */
150 #define STATS_SUB(x,y)	/* nothing */
151 #define STATS_INC(x)	/* nothing */
152 #define STATS_ZERO(x)	/* nothing */
153 #define STATS_SETF(x,y)	/* nothing */
154 #endif /* MALLOC_STATS */
155 	u_int32_t canary2;
156 };
157 #define DIR_INFO_RSZ	((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \
158 			~MALLOC_PAGEMASK)
159 
160 /*
161  * This structure describes a page worth of chunks.
162  *
163  * How many bits per u_short in the bitmap
164  */
165 #define MALLOC_BITS		(NBBY * sizeof(u_short))
166 struct chunk_info {
167 	LIST_ENTRY(chunk_info) entries;
168 	void *page;			/* pointer to the page */
169 	u_int32_t canary;
170 	u_short size;			/* size of this page's chunks */
171 	u_short shift;			/* how far to shift for this size */
172 	u_short free;			/* how many free chunks */
173 	u_short total;			/* how many chunks */
174 	u_short offset;			/* requested size table offset */
175 					/* which chunks are free */
176 	u_short bits[1];
177 };
178 
179 struct malloc_readonly {
180 	struct dir_info *malloc_pool[_MALLOC_MUTEXES];	/* Main bookkeeping information */
181 	int	malloc_mt;		/* multi-threaded mode? */
182 	int	malloc_freenow;		/* Free quickly - disable chunk rnd */
183 	int	malloc_freeunmap;	/* mprotect free pages PROT_NONE? */
184 	int	malloc_junk;		/* junk fill? */
185 	int	malloc_realloc;		/* always realloc? */
186 	int	malloc_xmalloc;		/* xmalloc behaviour? */
187 	int	chunk_canaries;		/* use canaries after chunks? */
188 	int	internal_funcs;		/* use better recallocarray/freezero? */
189 	u_int	malloc_cache;		/* free pages we cache */
190 	size_t	malloc_guard;		/* use guard pages after allocations? */
191 #ifdef MALLOC_STATS
192 	int	malloc_stats;		/* dump statistics at end */
193 #endif
194 	u_int32_t malloc_canary;	/* Matched against ones in malloc_pool */
195 };
196 
197 /* This object is mapped PROT_READ after initialisation to prevent tampering */
198 static union {
199 	struct malloc_readonly mopts;
200 	u_char _pad[MALLOC_PAGESIZE];
201 } malloc_readonly __attribute__((aligned(MALLOC_PAGESIZE)));
202 #define mopts	malloc_readonly.mopts
203 
204 char		*malloc_options;	/* compile-time options */
205 
206 static u_char getrbyte(struct dir_info *d);
207 static __dead void wrterror(struct dir_info *d, char *msg, ...)
208     __attribute__((__format__ (printf, 2, 3)));
209 static void fill_canary(char *ptr, size_t sz, size_t allocated);
210 
211 #ifdef MALLOC_STATS
212 void malloc_dump(int, int, struct dir_info *);
213 PROTO_NORMAL(malloc_dump);
214 void malloc_gdump(int);
215 PROTO_NORMAL(malloc_gdump);
216 static void malloc_exit(void);
217 #define CALLER	__builtin_return_address(0)
218 #else
219 #define CALLER	NULL
220 #endif
221 
222 /* low bits of r->p determine size: 0 means >= page size and r->size holding
223  * real size, otherwise low bits are a shift count, or 1 for malloc(0)
224  */
225 #define REALSIZE(sz, r)						\
226 	(sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK,		\
227 	(sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1))))
228 
229 static inline void
230 _MALLOC_LEAVE(struct dir_info *d)
231 {
232 	if (mopts.malloc_mt) {
233 		d->active--;
234 		_MALLOC_UNLOCK(d->mutex);
235 	}
236 }
237 
238 static inline void
239 _MALLOC_ENTER(struct dir_info *d)
240 {
241 	if (mopts.malloc_mt) {
242 		_MALLOC_LOCK(d->mutex);
243 		d->active++;
244 	}
245 }
246 
247 static inline size_t
248 hash(void *p)
249 {
250 	size_t sum;
251 	uintptr_t u;
252 
253 	u = (uintptr_t)p >> MALLOC_PAGESHIFT;
254 	sum = u;
255 	sum = (sum << 7) - sum + (u >> 16);
256 #ifdef __LP64__
257 	sum = (sum << 7) - sum + (u >> 32);
258 	sum = (sum << 7) - sum + (u >> 48);
259 #endif
260 	return sum;
261 }
262 
263 static inline
264 struct dir_info *getpool(void)
265 {
266 	if (!mopts.malloc_mt)
267 		return mopts.malloc_pool[0];
268 	else
269 		return mopts.malloc_pool[TIB_GET()->tib_tid &
270 		    (_MALLOC_MUTEXES - 1)];
271 }
272 
273 static __dead void
274 wrterror(struct dir_info *d, char *msg, ...)
275 {
276 	struct iovec	iov[3];
277 	char		pidbuf[80];
278 	char		buf[80];
279 	int		saved_errno = errno;
280 	va_list		ap;
281 
282 	iov[0].iov_base = pidbuf;
283 	snprintf(pidbuf, sizeof(pidbuf), "%s(%d) in %s(): ", __progname,
284 	    getpid(), (d != NULL && d->func) ? d->func : "unknown");
285 	iov[0].iov_len = strlen(pidbuf);
286 	iov[1].iov_base = buf;
287 	va_start(ap, msg);
288 	vsnprintf(buf, sizeof(buf), msg, ap);
289 	va_end(ap);
290 	iov[1].iov_len = strlen(buf);
291 	iov[2].iov_base = "\n";
292 	iov[2].iov_len = 1;
293 	writev(STDERR_FILENO, iov, 3);
294 
295 #ifdef MALLOC_STATS
296 	if (mopts.malloc_stats)
297 		malloc_gdump(STDERR_FILENO);
298 #endif /* MALLOC_STATS */
299 
300 	errno = saved_errno;
301 
302 	abort();
303 }
304 
305 static void
306 rbytes_init(struct dir_info *d)
307 {
308 	arc4random_buf(d->rbytes, sizeof(d->rbytes));
309 	/* add 1 to account for using d->rbytes[0] */
310 	d->rbytesused = 1 + d->rbytes[0] % (sizeof(d->rbytes) / 2);
311 }
312 
313 static inline u_char
314 getrbyte(struct dir_info *d)
315 {
316 	u_char x;
317 
318 	if (d->rbytesused >= sizeof(d->rbytes))
319 		rbytes_init(d);
320 	x = d->rbytes[d->rbytesused++];
321 	return x;
322 }
323 
324 /*
325  * Cache maintenance. We keep at most malloc_cache pages cached.
326  * If the cache is becoming full, unmap pages in the cache for real,
327  * and then add the region to the cache
328  * Opposed to the regular region data structure, the sizes in the
329  * cache are in MALLOC_PAGESIZE units.
330  */
331 static void
332 unmap(struct dir_info *d, void *p, size_t sz, int clear)
333 {
334 	size_t psz = sz >> MALLOC_PAGESHIFT;
335 	size_t rsz, tounmap;
336 	struct region_info *r;
337 	u_int i, offset;
338 
339 	if (sz != PAGEROUND(sz))
340 		wrterror(d, "munmap round");
341 
342 	rsz = mopts.malloc_cache - d->free_regions_size;
343 
344 	/*
345 	 * normally the cache holds recently freed regions, but if the region
346 	 * to unmap is larger than the cache size or we're clearing and the
347 	 * cache is full, just munmap
348 	 */
349 	if (psz > mopts.malloc_cache || (clear && rsz == 0)) {
350 		i = munmap(p, sz);
351 		if (i)
352 			wrterror(d, "munmap %p", p);
353 		STATS_SUB(d->malloc_used, sz);
354 		return;
355 	}
356 	tounmap = 0;
357 	if (psz > rsz)
358 		tounmap = psz - rsz;
359 	offset = getrbyte(d);
360 	for (i = 0; tounmap > 0 && i < mopts.malloc_cache; i++) {
361 		r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)];
362 		if (r->p != NULL) {
363 			rsz = r->size << MALLOC_PAGESHIFT;
364 			if (munmap(r->p, rsz))
365 				wrterror(d, "munmap %p", r->p);
366 			r->p = NULL;
367 			if (tounmap > r->size)
368 				tounmap -= r->size;
369 			else
370 				tounmap = 0;
371 			d->free_regions_size -= r->size;
372 			r->size = 0;
373 			STATS_SUB(d->malloc_used, rsz);
374 		}
375 	}
376 	if (tounmap > 0)
377 		wrterror(d, "malloc cache underflow");
378 	for (i = 0; i < mopts.malloc_cache; i++) {
379 		r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)];
380 		if (r->p == NULL) {
381 			if (clear)
382 				memset(p, 0, sz - mopts.malloc_guard);
383 			if (mopts.malloc_junk && !mopts.malloc_freeunmap) {
384 				size_t amt = mopts.malloc_junk == 1 ?
385 				    MALLOC_MAXCHUNK : sz;
386 				memset(p, SOME_FREEJUNK, amt);
387 			}
388 			if (mopts.malloc_freeunmap)
389 				mprotect(p, sz, PROT_NONE);
390 			r->p = p;
391 			r->size = psz;
392 			d->free_regions_size += psz;
393 			break;
394 		}
395 	}
396 	if (i == mopts.malloc_cache)
397 		wrterror(d, "malloc free slot lost");
398 	if (d->free_regions_size > mopts.malloc_cache)
399 		wrterror(d, "malloc cache overflow");
400 }
401 
402 static void
403 zapcacheregion(struct dir_info *d, void *p, size_t len)
404 {
405 	u_int i;
406 	struct region_info *r;
407 	size_t rsz;
408 
409 	for (i = 0; i < mopts.malloc_cache; i++) {
410 		r = &d->free_regions[i];
411 		if (r->p >= p && r->p <= (void *)((char *)p + len)) {
412 			rsz = r->size << MALLOC_PAGESHIFT;
413 			if (munmap(r->p, rsz))
414 				wrterror(d, "munmap %p", r->p);
415 			r->p = NULL;
416 			d->free_regions_size -= r->size;
417 			r->size = 0;
418 			STATS_SUB(d->malloc_used, rsz);
419 		}
420 	}
421 }
422 
423 static void *
424 map(struct dir_info *d, void *hint, size_t sz, int zero_fill)
425 {
426 	size_t psz = sz >> MALLOC_PAGESHIFT;
427 	struct region_info *r, *big = NULL;
428 	u_int i, offset;
429 	void *p;
430 
431 	if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
432 	    d->canary1 != ~d->canary2)
433 		wrterror(d, "internal struct corrupt");
434 	if (sz != PAGEROUND(sz))
435 		wrterror(d, "map round");
436 
437 	if (!hint && psz > d->free_regions_size) {
438 		_MALLOC_LEAVE(d);
439 		p = MMAP(sz);
440 		_MALLOC_ENTER(d);
441 		if (p != MAP_FAILED)
442 			STATS_ADD(d->malloc_used, sz);
443 		/* zero fill not needed */
444 		return p;
445 	}
446 	offset = getrbyte(d);
447 	for (i = 0; i < mopts.malloc_cache; i++) {
448 		r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)];
449 		if (r->p != NULL) {
450 			if (hint && r->p != hint)
451 				continue;
452 			if (r->size == psz) {
453 				p = r->p;
454 				r->p = NULL;
455 				r->size = 0;
456 				d->free_regions_size -= psz;
457 				if (mopts.malloc_freeunmap)
458 					mprotect(p, sz, PROT_READ | PROT_WRITE);
459 				if (zero_fill)
460 					memset(p, 0, sz);
461 				else if (mopts.malloc_junk == 2 &&
462 				    mopts.malloc_freeunmap)
463 					memset(p, SOME_FREEJUNK, sz);
464 				return p;
465 			} else if (r->size > psz)
466 				big = r;
467 		}
468 	}
469 	if (big != NULL) {
470 		r = big;
471 		p = r->p;
472 		r->p = (char *)r->p + (psz << MALLOC_PAGESHIFT);
473 		if (mopts.malloc_freeunmap)
474 			mprotect(p, sz, PROT_READ | PROT_WRITE);
475 		r->size -= psz;
476 		d->free_regions_size -= psz;
477 		if (zero_fill)
478 			memset(p, 0, sz);
479 		else if (mopts.malloc_junk == 2 && mopts.malloc_freeunmap)
480 			memset(p, SOME_FREEJUNK, sz);
481 		return p;
482 	}
483 	if (hint)
484 		return MAP_FAILED;
485 	if (d->free_regions_size > mopts.malloc_cache)
486 		wrterror(d, "malloc cache");
487 	_MALLOC_LEAVE(d);
488 	p = MMAP(sz);
489 	_MALLOC_ENTER(d);
490 	if (p != MAP_FAILED)
491 		STATS_ADD(d->malloc_used, sz);
492 	/* zero fill not needed */
493 	return p;
494 }
495 
496 static void
497 omalloc_parseopt(char opt)
498 {
499 	switch (opt) {
500 	case '>':
501 		mopts.malloc_cache <<= 1;
502 		if (mopts.malloc_cache > MALLOC_MAXCACHE)
503 			mopts.malloc_cache = MALLOC_MAXCACHE;
504 		break;
505 	case '<':
506 		mopts.malloc_cache >>= 1;
507 		break;
508 	case 'c':
509 		mopts.chunk_canaries = 0;
510 		break;
511 	case 'C':
512 		mopts.chunk_canaries = 1;
513 		break;
514 #ifdef MALLOC_STATS
515 	case 'd':
516 		mopts.malloc_stats = 0;
517 		break;
518 	case 'D':
519 		mopts.malloc_stats = 1;
520 		break;
521 #endif /* MALLOC_STATS */
522 	case 'f':
523 		mopts.malloc_freenow = 0;
524 		mopts.malloc_freeunmap = 0;
525 		break;
526 	case 'F':
527 		mopts.malloc_freenow = 1;
528 		mopts.malloc_freeunmap = 1;
529 		break;
530 	case 'g':
531 		mopts.malloc_guard = 0;
532 		break;
533 	case 'G':
534 		mopts.malloc_guard = MALLOC_PAGESIZE;
535 		break;
536 	case 'j':
537 		if (mopts.malloc_junk > 0)
538 			mopts.malloc_junk--;
539 		break;
540 	case 'J':
541 		if (mopts.malloc_junk < 2)
542 			mopts.malloc_junk++;
543 		break;
544 	case 'r':
545 		mopts.malloc_realloc = 0;
546 		break;
547 	case 'R':
548 		mopts.malloc_realloc = 1;
549 		break;
550 	case 'u':
551 		mopts.malloc_freeunmap = 0;
552 		break;
553 	case 'U':
554 		mopts.malloc_freeunmap = 1;
555 		break;
556 	case 'x':
557 		mopts.malloc_xmalloc = 0;
558 		break;
559 	case 'X':
560 		mopts.malloc_xmalloc = 1;
561 		break;
562 	default: {
563 		static const char q[] = "malloc() warning: "
564 		    "unknown char in MALLOC_OPTIONS\n";
565 		write(STDERR_FILENO, q, sizeof(q) - 1);
566 		break;
567 	}
568 	}
569 }
570 
571 static void
572 omalloc_init(void)
573 {
574 	char *p, *q, b[64];
575 	int i, j;
576 
577 	/*
578 	 * Default options
579 	 */
580 	mopts.malloc_junk = 1;
581 	mopts.malloc_cache = MALLOC_DEFAULT_CACHE;
582 
583 	for (i = 0; i < 3; i++) {
584 		switch (i) {
585 		case 0:
586 			j = readlink("/etc/malloc.conf", b, sizeof b - 1);
587 			if (j <= 0)
588 				continue;
589 			b[j] = '\0';
590 			p = b;
591 			break;
592 		case 1:
593 			if (issetugid() == 0)
594 				p = getenv("MALLOC_OPTIONS");
595 			else
596 				continue;
597 			break;
598 		case 2:
599 			p = malloc_options;
600 			break;
601 		default:
602 			p = NULL;
603 		}
604 
605 		for (; p != NULL && *p != '\0'; p++) {
606 			switch (*p) {
607 			case 'S':
608 				for (q = "CGJ"; *q != '\0'; q++)
609 					omalloc_parseopt(*q);
610 				mopts.malloc_cache = 0;
611 				break;
612 			case 's':
613 				for (q = "cgj"; *q != '\0'; q++)
614 					omalloc_parseopt(*q);
615 				mopts.malloc_cache = MALLOC_DEFAULT_CACHE;
616 				break;
617 			default:
618 				omalloc_parseopt(*p);
619 				break;
620 			}
621 		}
622 	}
623 
624 #ifdef MALLOC_STATS
625 	if (mopts.malloc_stats && (atexit(malloc_exit) == -1)) {
626 		static const char q[] = "malloc() warning: atexit(2) failed."
627 		    " Will not be able to dump stats on exit\n";
628 		write(STDERR_FILENO, q, sizeof(q) - 1);
629 	}
630 #endif /* MALLOC_STATS */
631 
632 	while ((mopts.malloc_canary = arc4random()) == 0)
633 		;
634 }
635 
636 /*
637  * Initialize a dir_info, which should have been cleared by caller
638  */
639 static void
640 omalloc_poolinit(struct dir_info **dp)
641 {
642 	void *p;
643 	size_t d_avail, regioninfo_size;
644 	struct dir_info *d;
645 	int i, j;
646 
647 	/*
648 	 * Allocate dir_info with a guard page on either side. Also
649 	 * randomise offset inside the page at which the dir_info
650 	 * lies (subject to alignment by 1 << MALLOC_MINSHIFT)
651 	 */
652 	if ((p = MMAP(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2))) == MAP_FAILED)
653 		wrterror(NULL, "malloc init mmap failed");
654 	mprotect(p, MALLOC_PAGESIZE, PROT_NONE);
655 	mprotect((char *)p + MALLOC_PAGESIZE + DIR_INFO_RSZ,
656 	    MALLOC_PAGESIZE, PROT_NONE);
657 	d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT;
658 	d = (struct dir_info *)((char *)p + MALLOC_PAGESIZE +
659 	    (arc4random_uniform(d_avail) << MALLOC_MINSHIFT));
660 
661 	rbytes_init(d);
662 	d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS;
663 	regioninfo_size = d->regions_total * sizeof(struct region_info);
664 	d->r = MMAP(regioninfo_size);
665 	if (d->r == MAP_FAILED) {
666 		d->regions_total = 0;
667 		wrterror(NULL, "malloc init mmap failed");
668 	}
669 	for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
670 		LIST_INIT(&d->chunk_info_list[i]);
671 		for (j = 0; j < MALLOC_CHUNK_LISTS; j++)
672 			LIST_INIT(&d->chunk_dir[i][j]);
673 	}
674 	STATS_ADD(d->malloc_used, regioninfo_size);
675 	d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
676 	d->canary2 = ~d->canary1;
677 
678 	*dp = d;
679 }
680 
681 static int
682 omalloc_grow(struct dir_info *d)
683 {
684 	size_t newtotal;
685 	size_t newsize;
686 	size_t mask;
687 	size_t i;
688 	struct region_info *p;
689 
690 	if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2 )
691 		return 1;
692 
693 	newtotal = d->regions_total * 2;
694 	newsize = newtotal * sizeof(struct region_info);
695 	mask = newtotal - 1;
696 
697 	p = MMAP(newsize);
698 	if (p == MAP_FAILED)
699 		return 1;
700 
701 	STATS_ADD(d->malloc_used, newsize);
702 	STATS_ZERO(d->inserts);
703 	STATS_ZERO(d->insert_collisions);
704 	for (i = 0; i < d->regions_total; i++) {
705 		void *q = d->r[i].p;
706 		if (q != NULL) {
707 			size_t index = hash(q) & mask;
708 			STATS_INC(d->inserts);
709 			while (p[index].p != NULL) {
710 				index = (index - 1) & mask;
711 				STATS_INC(d->insert_collisions);
712 			}
713 			p[index] = d->r[i];
714 		}
715 	}
716 	/* avoid pages containing meta info to end up in cache */
717 	if (munmap(d->r, d->regions_total * sizeof(struct region_info)))
718 		wrterror(d, "munmap %p", (void *)d->r);
719 	else
720 		STATS_SUB(d->malloc_used,
721 		    d->regions_total * sizeof(struct region_info));
722 	d->regions_free = d->regions_free + d->regions_total;
723 	d->regions_total = newtotal;
724 	d->r = p;
725 	return 0;
726 }
727 
728 static struct chunk_info *
729 alloc_chunk_info(struct dir_info *d, int bits)
730 {
731 	struct chunk_info *p;
732 	size_t size, count;
733 
734 	if (bits == 0)
735 		count = MALLOC_PAGESIZE / MALLOC_MINSIZE;
736 	else
737 		count = MALLOC_PAGESIZE >> bits;
738 
739 	size = howmany(count, MALLOC_BITS);
740 	size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short);
741 	if (mopts.chunk_canaries)
742 		size += count * sizeof(u_short);
743 	size = ALIGN(size);
744 
745 	if (LIST_EMPTY(&d->chunk_info_list[bits])) {
746 		char *q;
747 		int i;
748 
749 		q = MMAP(MALLOC_PAGESIZE);
750 		if (q == MAP_FAILED)
751 			return NULL;
752 		STATS_ADD(d->malloc_used, MALLOC_PAGESIZE);
753 		count = MALLOC_PAGESIZE / size;
754 		for (i = 0; i < count; i++, q += size)
755 			LIST_INSERT_HEAD(&d->chunk_info_list[bits],
756 			    (struct chunk_info *)q, entries);
757 	}
758 	p = LIST_FIRST(&d->chunk_info_list[bits]);
759 	LIST_REMOVE(p, entries);
760 	memset(p, 0, size);
761 	p->canary = d->canary1;
762 	return p;
763 }
764 
765 
766 /*
767  * The hashtable uses the assumption that p is never NULL. This holds since
768  * non-MAP_FIXED mappings with hint 0 start at BRKSIZ.
769  */
770 static int
771 insert(struct dir_info *d, void *p, size_t sz, void *f)
772 {
773 	size_t index;
774 	size_t mask;
775 	void *q;
776 
777 	if (d->regions_free * 4 < d->regions_total) {
778 		if (omalloc_grow(d))
779 			return 1;
780 	}
781 	mask = d->regions_total - 1;
782 	index = hash(p) & mask;
783 	q = d->r[index].p;
784 	STATS_INC(d->inserts);
785 	while (q != NULL) {
786 		index = (index - 1) & mask;
787 		q = d->r[index].p;
788 		STATS_INC(d->insert_collisions);
789 	}
790 	d->r[index].p = p;
791 	d->r[index].size = sz;
792 #ifdef MALLOC_STATS
793 	d->r[index].f = f;
794 #endif
795 	d->regions_free--;
796 	return 0;
797 }
798 
799 static struct region_info *
800 find(struct dir_info *d, void *p)
801 {
802 	size_t index;
803 	size_t mask = d->regions_total - 1;
804 	void *q, *r;
805 
806 	if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
807 	    d->canary1 != ~d->canary2)
808 		wrterror(d, "internal struct corrupt");
809 	p = MASK_POINTER(p);
810 	index = hash(p) & mask;
811 	r = d->r[index].p;
812 	q = MASK_POINTER(r);
813 	STATS_INC(d->finds);
814 	while (q != p && r != NULL) {
815 		index = (index - 1) & mask;
816 		r = d->r[index].p;
817 		q = MASK_POINTER(r);
818 		STATS_INC(d->find_collisions);
819 	}
820 	return (q == p && r != NULL) ? &d->r[index] : NULL;
821 }
822 
823 static void
824 delete(struct dir_info *d, struct region_info *ri)
825 {
826 	/* algorithm R, Knuth Vol III section 6.4 */
827 	size_t mask = d->regions_total - 1;
828 	size_t i, j, r;
829 
830 	if (d->regions_total & (d->regions_total - 1))
831 		wrterror(d, "regions_total not 2^x");
832 	d->regions_free++;
833 	STATS_INC(d->deletes);
834 
835 	i = ri - d->r;
836 	for (;;) {
837 		d->r[i].p = NULL;
838 		d->r[i].size = 0;
839 		j = i;
840 		for (;;) {
841 			i = (i - 1) & mask;
842 			if (d->r[i].p == NULL)
843 				return;
844 			r = hash(d->r[i].p) & mask;
845 			if ((i <= r && r < j) || (r < j && j < i) ||
846 			    (j < i && i <= r))
847 				continue;
848 			d->r[j] = d->r[i];
849 			STATS_INC(d->delete_moves);
850 			break;
851 		}
852 
853 	}
854 }
855 
856 /*
857  * Allocate a page of chunks
858  */
859 static struct chunk_info *
860 omalloc_make_chunks(struct dir_info *d, int bits, int listnum)
861 {
862 	struct chunk_info *bp;
863 	void		*pp;
864 	int		i, k;
865 
866 	/* Allocate a new bucket */
867 	pp = map(d, NULL, MALLOC_PAGESIZE, 0);
868 	if (pp == MAP_FAILED)
869 		return NULL;
870 
871 	bp = alloc_chunk_info(d, bits);
872 	if (bp == NULL) {
873 		unmap(d, pp, MALLOC_PAGESIZE, 0);
874 		return NULL;
875 	}
876 
877 	/* memory protect the page allocated in the malloc(0) case */
878 	if (bits == 0) {
879 		bp->size = 0;
880 		bp->shift = 1;
881 		i = MALLOC_MINSIZE - 1;
882 		while (i >>= 1)
883 			bp->shift++;
884 		bp->total = bp->free = MALLOC_PAGESIZE >> bp->shift;
885 		bp->offset = 0xdead;
886 		bp->page = pp;
887 
888 		k = mprotect(pp, MALLOC_PAGESIZE, PROT_NONE);
889 		if (k < 0) {
890 			unmap(d, pp, MALLOC_PAGESIZE, 0);
891 			LIST_INSERT_HEAD(&d->chunk_info_list[0], bp, entries);
892 			return NULL;
893 		}
894 	} else {
895 		bp->size = 1U << bits;
896 		bp->shift = bits;
897 		bp->total = bp->free = MALLOC_PAGESIZE >> bits;
898 		bp->offset = howmany(bp->total, MALLOC_BITS);
899 		bp->page = pp;
900 	}
901 
902 	/* set all valid bits in the bitmap */
903 	k = bp->total;
904 	i = 0;
905 
906 	/* Do a bunch at a time */
907 	for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
908 		bp->bits[i / MALLOC_BITS] = (u_short)~0U;
909 
910 	for (; i < k; i++)
911 		bp->bits[i / MALLOC_BITS] |= (u_short)1U << (i % MALLOC_BITS);
912 
913 	LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries);
914 
915 	bits++;
916 	if ((uintptr_t)pp & bits)
917 		wrterror(d, "pp & bits %p", pp);
918 
919 	insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp, NULL);
920 	return bp;
921 }
922 
923 static int
924 find_chunksize(size_t size)
925 {
926 	int		i, j;
927 
928 	/* Don't bother with anything less than this */
929 	/* unless we have a malloc(0) requests */
930 	if (size != 0 && size < MALLOC_MINSIZE)
931 		size = MALLOC_MINSIZE;
932 
933 	/* Find the right bucket */
934 	if (size == 0)
935 		j = 0;
936 	else {
937 		j = MALLOC_MINSHIFT;
938 		i = (size - 1) >> (MALLOC_MINSHIFT - 1);
939 		while (i >>= 1)
940 			j++;
941 	}
942 	return j;
943 }
944 
945 /*
946  * Allocate a chunk
947  */
948 static void *
949 malloc_bytes(struct dir_info *d, size_t size, void *f)
950 {
951 	int		i, j, listnum;
952 	size_t		k;
953 	u_short		u, *lp;
954 	struct chunk_info *bp;
955 
956 	if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) ||
957 	    d->canary1 != ~d->canary2)
958 		wrterror(d, "internal struct corrupt");
959 
960 	j = find_chunksize(size);
961 
962 	listnum = getrbyte(d) % MALLOC_CHUNK_LISTS;
963 	/* If it's empty, make a page more of that size chunks */
964 	if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) {
965 		bp = omalloc_make_chunks(d, j, listnum);
966 		if (bp == NULL)
967 			return NULL;
968 	}
969 
970 	if (bp->canary != d->canary1)
971 		wrterror(d, "chunk info corrupted");
972 
973 	i = d->chunk_start;
974 	if (bp->free > 1)
975 		i += getrbyte(d);
976 	if (i >= bp->total)
977 		i &= bp->total - 1;
978 	for (;;) {
979 		for (;;) {
980 			lp = &bp->bits[i / MALLOC_BITS];
981 			if (!*lp) {
982 				i += MALLOC_BITS;
983 				i &= ~(MALLOC_BITS - 1);
984 				if (i >= bp->total)
985 					i = 0;
986 			} else
987 				break;
988 		}
989 		k = i % MALLOC_BITS;
990 		u = 1 << k;
991 		if (*lp & u)
992 			break;
993 		if (++i >= bp->total)
994 			i = 0;
995 	}
996 	d->chunk_start += i + 1;
997 #ifdef MALLOC_STATS
998 	if (i == 0) {
999 		struct region_info *r = find(d, bp->page);
1000 		r->f = f;
1001 	}
1002 #endif
1003 
1004 	*lp ^= u;
1005 
1006 	/* If there are no more free, remove from free-list */
1007 	if (!--bp->free)
1008 		LIST_REMOVE(bp, entries);
1009 
1010 	/* Adjust to the real offset of that chunk */
1011 	k += (lp - bp->bits) * MALLOC_BITS;
1012 
1013 	if (mopts.chunk_canaries && size > 0)
1014 		bp->bits[bp->offset + k] = size;
1015 
1016 	k <<= bp->shift;
1017 
1018 	if (bp->size > 0) {
1019 		if (mopts.malloc_junk == 2)
1020 			memset((char *)bp->page + k, SOME_JUNK, bp->size);
1021 		else if (mopts.chunk_canaries)
1022 			fill_canary((char *)bp->page + k, size, bp->size);
1023 	}
1024 	return ((char *)bp->page + k);
1025 }
1026 
1027 static void
1028 fill_canary(char *ptr, size_t sz, size_t allocated)
1029 {
1030 	size_t check_sz = allocated - sz;
1031 
1032 	if (check_sz > CHUNK_CHECK_LENGTH)
1033 		check_sz = CHUNK_CHECK_LENGTH;
1034 	memset(ptr + sz, SOME_JUNK, check_sz);
1035 }
1036 
1037 static void
1038 validate_canary(struct dir_info *d, u_char *ptr, size_t sz, size_t allocated)
1039 {
1040 	size_t check_sz = allocated - sz;
1041 	u_char *p, *q;
1042 
1043 	if (check_sz > CHUNK_CHECK_LENGTH)
1044 		check_sz = CHUNK_CHECK_LENGTH;
1045 	p = ptr + sz;
1046 	q = p + check_sz;
1047 
1048 	while (p < q) {
1049 		if (*p++ != SOME_JUNK) {
1050 			wrterror(d, "chunk canary corrupted %p %#tx@%#zx",
1051 			    ptr, p - ptr - 1, sz);
1052 		}
1053 	}
1054 }
1055 
1056 static uint32_t
1057 find_chunknum(struct dir_info *d, struct region_info *r, void *ptr, int check)
1058 {
1059 	struct chunk_info *info;
1060 	uint32_t chunknum;
1061 
1062 	info = (struct chunk_info *)r->size;
1063 	if (info->canary != d->canary1)
1064 		wrterror(d, "chunk info corrupted");
1065 
1066 	/* Find the chunk number on the page */
1067 	chunknum = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift;
1068 	if (check && info->size > 0) {
1069 		validate_canary(d, ptr, info->bits[info->offset + chunknum],
1070 		    info->size);
1071 	}
1072 
1073 	if ((uintptr_t)ptr & ((1U << (info->shift)) - 1))
1074 		wrterror(d, "modified chunk-pointer %p", ptr);
1075 	if (info->bits[chunknum / MALLOC_BITS] &
1076 	    (1U << (chunknum % MALLOC_BITS)))
1077 		wrterror(d, "chunk is already free %p", ptr);
1078 	return chunknum;
1079 }
1080 
1081 /*
1082  * Free a chunk, and possibly the page it's on, if the page becomes empty.
1083  */
1084 static void
1085 free_bytes(struct dir_info *d, struct region_info *r, void *ptr)
1086 {
1087 	struct chunk_head *mp;
1088 	struct chunk_info *info;
1089 	uint32_t chunknum;
1090 	int listnum;
1091 
1092 	info = (struct chunk_info *)r->size;
1093 	chunknum = find_chunknum(d, r, ptr, 0);
1094 
1095 	info->bits[chunknum / MALLOC_BITS] |= 1U << (chunknum % MALLOC_BITS);
1096 	info->free++;
1097 
1098 	if (info->free == 1) {
1099 		/* Page became non-full */
1100 		listnum = getrbyte(d) % MALLOC_CHUNK_LISTS;
1101 		if (info->size != 0)
1102 			mp = &d->chunk_dir[info->shift][listnum];
1103 		else
1104 			mp = &d->chunk_dir[0][listnum];
1105 
1106 		LIST_INSERT_HEAD(mp, info, entries);
1107 		return;
1108 	}
1109 
1110 	if (info->free != info->total)
1111 		return;
1112 
1113 	LIST_REMOVE(info, entries);
1114 
1115 	if (info->size == 0 && !mopts.malloc_freeunmap)
1116 		mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE);
1117 	unmap(d, info->page, MALLOC_PAGESIZE, 0);
1118 
1119 	delete(d, r);
1120 	if (info->size != 0)
1121 		mp = &d->chunk_info_list[info->shift];
1122 	else
1123 		mp = &d->chunk_info_list[0];
1124 	LIST_INSERT_HEAD(mp, info, entries);
1125 }
1126 
1127 
1128 
1129 static void *
1130 omalloc(struct dir_info *pool, size_t sz, int zero_fill, void *f)
1131 {
1132 	void *p;
1133 	size_t psz;
1134 
1135 	if (sz > MALLOC_MAXCHUNK) {
1136 		if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1137 			errno = ENOMEM;
1138 			return NULL;
1139 		}
1140 		sz += mopts.malloc_guard;
1141 		psz = PAGEROUND(sz);
1142 		p = map(pool, NULL, psz, zero_fill);
1143 		if (p == MAP_FAILED) {
1144 			errno = ENOMEM;
1145 			return NULL;
1146 		}
1147 		if (insert(pool, p, sz, f)) {
1148 			unmap(pool, p, psz, 0);
1149 			errno = ENOMEM;
1150 			return NULL;
1151 		}
1152 		if (mopts.malloc_guard) {
1153 			if (mprotect((char *)p + psz - mopts.malloc_guard,
1154 			    mopts.malloc_guard, PROT_NONE))
1155 				wrterror(pool, "mprotect");
1156 			STATS_ADD(pool->malloc_guarded, mopts.malloc_guard);
1157 		}
1158 
1159 		if (MALLOC_MOVE_COND(sz)) {
1160 			/* fill whole allocation */
1161 			if (mopts.malloc_junk == 2)
1162 				memset(p, SOME_JUNK, psz - mopts.malloc_guard);
1163 			/* shift towards the end */
1164 			p = MALLOC_MOVE(p, sz);
1165 			/* fill zeros if needed and overwritten above */
1166 			if (zero_fill && mopts.malloc_junk == 2)
1167 				memset(p, 0, sz - mopts.malloc_guard);
1168 		} else {
1169 			if (mopts.malloc_junk == 2) {
1170 				if (zero_fill)
1171 					memset((char *)p + sz - mopts.malloc_guard,
1172 					    SOME_JUNK, psz - sz);
1173 				else
1174 					memset(p, SOME_JUNK,
1175 					    psz - mopts.malloc_guard);
1176 			}
1177 			else if (mopts.chunk_canaries)
1178 				fill_canary(p, sz - mopts.malloc_guard,
1179 				    psz - mopts.malloc_guard);
1180 		}
1181 
1182 	} else {
1183 		/* takes care of SOME_JUNK */
1184 		p = malloc_bytes(pool, sz, f);
1185 		if (zero_fill && p != NULL && sz > 0)
1186 			memset(p, 0, sz);
1187 	}
1188 
1189 	return p;
1190 }
1191 
1192 /*
1193  * Common function for handling recursion.  Only
1194  * print the error message once, to avoid making the problem
1195  * potentially worse.
1196  */
1197 static void
1198 malloc_recurse(struct dir_info *d)
1199 {
1200 	static int noprint;
1201 
1202 	if (noprint == 0) {
1203 		noprint = 1;
1204 		wrterror(d, "recursive call");
1205 	}
1206 	d->active--;
1207 	_MALLOC_UNLOCK(d->mutex);
1208 	errno = EDEADLK;
1209 }
1210 
1211 void
1212 _malloc_init(int from_rthreads)
1213 {
1214 	int i, max;
1215 	struct dir_info *d;
1216 
1217 	_MALLOC_LOCK(0);
1218 	if (!from_rthreads && mopts.malloc_pool[0]) {
1219 		_MALLOC_UNLOCK(0);
1220 		return;
1221 	}
1222 	if (!mopts.malloc_canary)
1223 		omalloc_init();
1224 
1225 	max = from_rthreads ? _MALLOC_MUTEXES : 1;
1226 	if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0)
1227 		mprotect(&malloc_readonly, sizeof(malloc_readonly),
1228 		     PROT_READ | PROT_WRITE);
1229 	for (i = 0; i < max; i++) {
1230 		if (mopts.malloc_pool[i])
1231 			continue;
1232 		omalloc_poolinit(&d);
1233 		d->mutex = i;
1234 		mopts.malloc_pool[i] = d;
1235 	}
1236 
1237 	if (from_rthreads)
1238 		mopts.malloc_mt = 1;
1239 	else
1240 		mopts.internal_funcs = 1;
1241 
1242 	/*
1243 	 * Options have been set and will never be reset.
1244 	 * Prevent further tampering with them.
1245 	 */
1246 	if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0)
1247 		mprotect(&malloc_readonly, sizeof(malloc_readonly), PROT_READ);
1248 	_MALLOC_UNLOCK(0);
1249 }
1250 DEF_STRONG(_malloc_init);
1251 
1252 void *
1253 malloc(size_t size)
1254 {
1255 	void *r;
1256 	struct dir_info *d;
1257 	int saved_errno = errno;
1258 
1259 	d = getpool();
1260 	if (d == NULL) {
1261 		_malloc_init(0);
1262 		d = getpool();
1263 	}
1264 	_MALLOC_LOCK(d->mutex);
1265 	d->func = "malloc";
1266 
1267 	if (d->active++) {
1268 		malloc_recurse(d);
1269 		return NULL;
1270 	}
1271 	r = omalloc(d, size, 0, CALLER);
1272 	d->active--;
1273 	_MALLOC_UNLOCK(d->mutex);
1274 	if (r == NULL && mopts.malloc_xmalloc)
1275 		wrterror(d, "out of memory");
1276 	if (r != NULL)
1277 		errno = saved_errno;
1278 	return r;
1279 }
1280 /*DEF_STRONG(malloc);*/
1281 
1282 static void
1283 validate_junk(struct dir_info *pool, void *p)
1284 {
1285 	struct region_info *r;
1286 	size_t byte, sz;
1287 
1288 	if (p == NULL)
1289 		return;
1290 	r = find(pool, p);
1291 	if (r == NULL)
1292 		wrterror(pool, "bogus pointer in validate_junk %p", p);
1293 	REALSIZE(sz, r);
1294 	if (sz > CHUNK_CHECK_LENGTH)
1295 		sz = CHUNK_CHECK_LENGTH;
1296 	for (byte = 0; byte < sz; byte++) {
1297 		if (((unsigned char *)p)[byte] != SOME_FREEJUNK)
1298 			wrterror(pool, "use after free %p", p);
1299 	}
1300 }
1301 
1302 static void
1303 ofree(struct dir_info *argpool, void *p, int clear, int check, size_t argsz)
1304 {
1305 	struct dir_info *pool;
1306 	struct region_info *r;
1307 	size_t sz;
1308 	int i;
1309 
1310 	pool = argpool;
1311 	r = find(pool, p);
1312 	if (r == NULL) {
1313 		if (mopts.malloc_mt)  {
1314 			for (i = 0; i < _MALLOC_MUTEXES; i++) {
1315 				if (i == argpool->mutex)
1316 					continue;
1317 				pool->active--;
1318 				_MALLOC_UNLOCK(pool->mutex);
1319 				pool = mopts.malloc_pool[i];
1320 				_MALLOC_LOCK(pool->mutex);
1321 				pool->active++;
1322 				r = find(pool, p);
1323 				if (r != NULL)
1324 					break;
1325 			}
1326 		}
1327 		if (r == NULL)
1328 			wrterror(pool, "bogus pointer (double free?) %p", p);
1329 	}
1330 
1331 	REALSIZE(sz, r);
1332 	if (check) {
1333 		if (sz <= MALLOC_MAXCHUNK) {
1334 			if (mopts.chunk_canaries && sz > 0) {
1335 				struct chunk_info *info =
1336 				    (struct chunk_info *)r->size;
1337 				uint32_t chunknum =
1338 				    find_chunknum(pool, r, p, 0);
1339 
1340 				if (info->bits[info->offset + chunknum] <
1341 				    argsz)
1342 					wrterror(pool, "recorded size %hu"
1343 					    " < %zu",
1344 					    info->bits[info->offset + chunknum],
1345 					    argsz);
1346 			} else {
1347 				if (sz < argsz)
1348 					wrterror(pool, "chunk size %zu < %zu",
1349 					    sz, argsz);
1350 			}
1351 		} else if (sz - mopts.malloc_guard < argsz) {
1352 			wrterror(pool, "recorded size %zu < %zu",
1353 			    sz - mopts.malloc_guard, argsz);
1354 		}
1355 	}
1356 	if (sz > MALLOC_MAXCHUNK) {
1357 		if (!MALLOC_MOVE_COND(sz)) {
1358 			if (r->p != p)
1359 				wrterror(pool, "bogus pointer %p", p);
1360 			if (mopts.chunk_canaries)
1361 				validate_canary(pool, p,
1362 				    sz - mopts.malloc_guard,
1363 				    PAGEROUND(sz - mopts.malloc_guard));
1364 		} else {
1365 			/* shifted towards the end */
1366 			if (p != MALLOC_MOVE(r->p, sz))
1367 				wrterror(pool, "bogus moved pointer %p", p);
1368 			p = r->p;
1369 		}
1370 		if (mopts.malloc_guard) {
1371 			if (sz < mopts.malloc_guard)
1372 				wrterror(pool, "guard size");
1373 			if (!mopts.malloc_freeunmap) {
1374 				if (mprotect((char *)p + PAGEROUND(sz) -
1375 				    mopts.malloc_guard, mopts.malloc_guard,
1376 				    PROT_READ | PROT_WRITE))
1377 					wrterror(pool, "mprotect");
1378 			}
1379 			STATS_SUB(pool->malloc_guarded, mopts.malloc_guard);
1380 		}
1381 		unmap(pool, p, PAGEROUND(sz), clear);
1382 		delete(pool, r);
1383 	} else {
1384 		void *tmp;
1385 		int i;
1386 
1387 		/* Delayed free or canaries? Extra check */
1388 		if (!mopts.malloc_freenow || mopts.chunk_canaries)
1389 			find_chunknum(pool, r, p, mopts.chunk_canaries);
1390 		if (!clear && !mopts.malloc_freenow) {
1391 			if (mopts.malloc_junk && sz > 0)
1392 				memset(p, SOME_FREEJUNK, sz);
1393 			i = getrbyte(pool) & MALLOC_DELAYED_CHUNK_MASK;
1394 			tmp = p;
1395 			p = pool->delayed_chunks[i];
1396 			if (tmp == p)
1397 				wrterror(pool, "double free %p", tmp);
1398 			if (mopts.malloc_junk)
1399 				validate_junk(pool, p);
1400 			pool->delayed_chunks[i] = tmp;
1401 		} else {
1402 			if ((clear || mopts.malloc_junk) && sz > 0)
1403 				memset(p, clear ? 0 : SOME_FREEJUNK, sz);
1404 		}
1405 		if (p != NULL) {
1406 			r = find(pool, p);
1407 			if (r == NULL)
1408 				wrterror(pool,
1409 				    "bogus pointer (double free?) %p", p);
1410 			free_bytes(pool, r, p);
1411 		}
1412 	}
1413 
1414 	if (argpool != pool) {
1415 		pool->active--;
1416 		_MALLOC_UNLOCK(pool->mutex);
1417 		_MALLOC_LOCK(argpool->mutex);
1418 		argpool->active++;
1419 	}
1420 }
1421 
1422 void
1423 free(void *ptr)
1424 {
1425 	struct dir_info *d;
1426 	int saved_errno = errno;
1427 
1428 	/* This is legal. */
1429 	if (ptr == NULL)
1430 		return;
1431 
1432 	d = getpool();
1433 	if (d == NULL)
1434 		wrterror(d, "free() called before allocation");
1435 	_MALLOC_LOCK(d->mutex);
1436 	d->func = "free";
1437 	if (d->active++) {
1438 		malloc_recurse(d);
1439 		return;
1440 	}
1441 	ofree(d, ptr, 0, 0, 0);
1442 	d->active--;
1443 	_MALLOC_UNLOCK(d->mutex);
1444 	errno = saved_errno;
1445 }
1446 /*DEF_STRONG(free);*/
1447 
1448 static void
1449 freezero_p(void *ptr, size_t sz)
1450 {
1451 	explicit_bzero(ptr, sz);
1452 	free(ptr);
1453 }
1454 
1455 void
1456 freezero(void *ptr, size_t sz)
1457 {
1458 	struct dir_info *d;
1459 	int saved_errno = errno;
1460 
1461 	/* This is legal. */
1462 	if (ptr == NULL)
1463 		return;
1464 
1465 	if (!mopts.internal_funcs)
1466 		return freezero_p(ptr, sz);
1467 
1468 	d = getpool();
1469 	if (d == NULL)
1470 		wrterror(d, "freezero() called before allocation");
1471 	_MALLOC_LOCK(d->mutex);
1472 	d->func = "freezero";
1473 	if (d->active++) {
1474 		malloc_recurse(d);
1475 		return;
1476 	}
1477 	ofree(d, ptr, 1, 1, sz);
1478 	d->active--;
1479 	_MALLOC_UNLOCK(d->mutex);
1480 	errno = saved_errno;
1481 }
1482 DEF_WEAK(freezero);
1483 
1484 static void *
1485 orealloc(struct dir_info *argpool, void *p, size_t newsz, void *f)
1486 {
1487 	struct dir_info *pool;
1488 	struct region_info *r;
1489 	struct chunk_info *info;
1490 	size_t oldsz, goldsz, gnewsz;
1491 	void *q, *ret;
1492 	int i;
1493 	uint32_t chunknum;
1494 
1495 	pool = argpool;
1496 
1497 	if (p == NULL)
1498 		return omalloc(pool, newsz, 0, f);
1499 
1500 	r = find(pool, p);
1501 	if (r == NULL) {
1502 		if (mopts.malloc_mt) {
1503 			for (i = 0; i < _MALLOC_MUTEXES; i++) {
1504 				if (i == argpool->mutex)
1505 					continue;
1506 				pool->active--;
1507 				_MALLOC_UNLOCK(pool->mutex);
1508 				pool = mopts.malloc_pool[i];
1509 				_MALLOC_LOCK(pool->mutex);
1510 				pool->active++;
1511 				r = find(pool, p);
1512 				if (r != NULL)
1513 					break;
1514 			}
1515 		}
1516 		if (r == NULL)
1517 			wrterror(pool, "bogus pointer (double free?) %p", p);
1518 	}
1519 	if (newsz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1520 		errno = ENOMEM;
1521 		ret = NULL;
1522 		goto done;
1523 	}
1524 
1525 	REALSIZE(oldsz, r);
1526 	if (mopts.chunk_canaries && oldsz <= MALLOC_MAXCHUNK) {
1527 		chunknum = find_chunknum(pool, r, p, 0);
1528 		info = (struct chunk_info *)r->size;
1529 	}
1530 
1531 	goldsz = oldsz;
1532 	if (oldsz > MALLOC_MAXCHUNK) {
1533 		if (oldsz < mopts.malloc_guard)
1534 			wrterror(pool, "guard size");
1535 		oldsz -= mopts.malloc_guard;
1536 	}
1537 
1538 	gnewsz = newsz;
1539 	if (gnewsz > MALLOC_MAXCHUNK)
1540 		gnewsz += mopts.malloc_guard;
1541 
1542 	if (newsz > MALLOC_MAXCHUNK && oldsz > MALLOC_MAXCHUNK &&
1543 	    !mopts.malloc_realloc) {
1544 		/* First case: from n pages sized allocation to m pages sized
1545 		   allocation, m > n */
1546 		size_t roldsz = PAGEROUND(goldsz);
1547 		size_t rnewsz = PAGEROUND(gnewsz);
1548 
1549 		if (rnewsz > roldsz) {
1550 			/* try to extend existing region */
1551 			if (!mopts.malloc_guard) {
1552 				void *hint = (char *)r->p + roldsz;
1553 				size_t needed = rnewsz - roldsz;
1554 
1555 				STATS_INC(pool->cheap_realloc_tries);
1556 				q = map(pool, hint, needed, 0);
1557 				if (q == hint)
1558 					goto gotit;
1559 				zapcacheregion(pool, hint, needed);
1560 				q = MQUERY(hint, needed);
1561 				if (q == hint)
1562 					q = MMAPA(hint, needed);
1563 				else
1564 					q = MAP_FAILED;
1565 				if (q == hint) {
1566 gotit:
1567 					STATS_ADD(pool->malloc_used, needed);
1568 					if (mopts.malloc_junk == 2)
1569 						memset(q, SOME_JUNK, needed);
1570 					r->size = gnewsz;
1571 					if (r->p != p) {
1572 						/* old pointer is moved */
1573 						memmove(r->p, p, oldsz);
1574 						p = r->p;
1575 					}
1576 					if (mopts.chunk_canaries)
1577 						fill_canary(p, newsz,
1578 						    PAGEROUND(newsz));
1579 					STATS_SETF(r, f);
1580 					STATS_INC(pool->cheap_reallocs);
1581 					ret = p;
1582 					goto done;
1583 				} else if (q != MAP_FAILED) {
1584 					if (munmap(q, needed))
1585 						wrterror(pool, "munmap %p", q);
1586 				}
1587 			}
1588 		} else if (rnewsz < roldsz) {
1589 			/* shrink number of pages */
1590 			if (mopts.malloc_guard) {
1591 				if (mprotect((char *)r->p + roldsz -
1592 				    mopts.malloc_guard, mopts.malloc_guard,
1593 				    PROT_READ | PROT_WRITE))
1594 					wrterror(pool, "mprotect");
1595 				if (mprotect((char *)r->p + rnewsz -
1596 				    mopts.malloc_guard, mopts.malloc_guard,
1597 				    PROT_NONE))
1598 					wrterror(pool, "mprotect");
1599 			}
1600 			unmap(pool, (char *)r->p + rnewsz, roldsz - rnewsz, 0);
1601 			r->size = gnewsz;
1602 			if (MALLOC_MOVE_COND(gnewsz)) {
1603 				void *pp = MALLOC_MOVE(r->p, gnewsz);
1604 				memmove(pp, p, newsz);
1605 				p = pp;
1606 			} else if (mopts.chunk_canaries)
1607 				fill_canary(p, newsz, PAGEROUND(newsz));
1608 			STATS_SETF(r, f);
1609 			ret = p;
1610 			goto done;
1611 		} else {
1612 			/* number of pages remains the same */
1613 			void *pp = r->p;
1614 
1615 			r->size = gnewsz;
1616 			if (MALLOC_MOVE_COND(gnewsz))
1617 				pp = MALLOC_MOVE(r->p, gnewsz);
1618 			if (p != pp) {
1619 				memmove(pp, p, oldsz < newsz ? oldsz : newsz);
1620 				p = pp;
1621 			}
1622 			if (p == r->p) {
1623 				if (newsz > oldsz && mopts.malloc_junk == 2)
1624 					memset((char *)p + newsz, SOME_JUNK,
1625 					    rnewsz - mopts.malloc_guard -
1626 					    newsz);
1627 				if (mopts.chunk_canaries)
1628 					fill_canary(p, newsz, PAGEROUND(newsz));
1629 			}
1630 			STATS_SETF(r, f);
1631 			ret = p;
1632 			goto done;
1633 		}
1634 	}
1635 	if (oldsz <= MALLOC_MAXCHUNK && oldsz > 0 &&
1636 	    newsz <= MALLOC_MAXCHUNK && newsz > 0 &&
1637 	    1 << find_chunksize(newsz) == oldsz && !mopts.malloc_realloc) {
1638 		/* do not reallocate if new size fits good in existing chunk */
1639 		if (mopts.malloc_junk == 2)
1640 			memset((char *)p + newsz, SOME_JUNK, oldsz - newsz);
1641 		if (mopts.chunk_canaries) {
1642 			info->bits[info->offset + chunknum] = newsz;
1643 			fill_canary(p, newsz, info->size);
1644 		}
1645 		STATS_SETF(r, f);
1646 		ret = p;
1647 	} else if (newsz != oldsz || mopts.malloc_realloc) {
1648 		/* create new allocation */
1649 		q = omalloc(pool, newsz, 0, f);
1650 		if (q == NULL) {
1651 			ret = NULL;
1652 			goto done;
1653 		}
1654 		if (newsz != 0 && oldsz != 0)
1655 			memcpy(q, p, oldsz < newsz ? oldsz : newsz);
1656 		ofree(pool, p, 0, 0, 0);
1657 		ret = q;
1658 	} else {
1659 		/* oldsz == newsz */
1660 		if (newsz != 0)
1661 			wrterror(pool, "realloc internal inconsistency");
1662 		STATS_SETF(r, f);
1663 		ret = p;
1664 	}
1665 done:
1666 	if (argpool != pool) {
1667 		pool->active--;
1668 		_MALLOC_UNLOCK(pool->mutex);
1669 		_MALLOC_LOCK(argpool->mutex);
1670 		argpool->active++;
1671 	}
1672 	return ret;
1673 }
1674 
1675 void *
1676 realloc(void *ptr, size_t size)
1677 {
1678 	struct dir_info *d;
1679 	void *r;
1680 	int saved_errno = errno;
1681 
1682 	d = getpool();
1683 	if (d == NULL) {
1684 		_malloc_init(0);
1685 		d = getpool();
1686 	}
1687 	_MALLOC_LOCK(d->mutex);
1688 	d->func = "realloc";
1689 	if (d->active++) {
1690 		malloc_recurse(d);
1691 		return NULL;
1692 	}
1693 	r = orealloc(d, ptr, size, CALLER);
1694 
1695 	d->active--;
1696 	_MALLOC_UNLOCK(d->mutex);
1697 	if (r == NULL && mopts.malloc_xmalloc)
1698 		wrterror(d, "out of memory");
1699 	if (r != NULL)
1700 		errno = saved_errno;
1701 	return r;
1702 }
1703 /*DEF_STRONG(realloc);*/
1704 
1705 
1706 /*
1707  * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
1708  * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
1709  */
1710 #define MUL_NO_OVERFLOW	(1UL << (sizeof(size_t) * 4))
1711 
1712 void *
1713 calloc(size_t nmemb, size_t size)
1714 {
1715 	struct dir_info *d;
1716 	void *r;
1717 	int saved_errno = errno;
1718 
1719 	d = getpool();
1720 	if (d == NULL) {
1721 		_malloc_init(0);
1722 		d = getpool();
1723 	}
1724 	_MALLOC_LOCK(d->mutex);
1725 	d->func = "calloc";
1726 	if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1727 	    nmemb > 0 && SIZE_MAX / nmemb < size) {
1728 		_MALLOC_UNLOCK(d->mutex);
1729 		if (mopts.malloc_xmalloc)
1730 			wrterror(d, "out of memory");
1731 		errno = ENOMEM;
1732 		return NULL;
1733 	}
1734 
1735 	if (d->active++) {
1736 		malloc_recurse(d);
1737 		return NULL;
1738 	}
1739 
1740 	size *= nmemb;
1741 	r = omalloc(d, size, 1, CALLER);
1742 
1743 	d->active--;
1744 	_MALLOC_UNLOCK(d->mutex);
1745 	if (r == NULL && mopts.malloc_xmalloc)
1746 		wrterror(d, "out of memory");
1747 	if (r != NULL)
1748 		errno = saved_errno;
1749 	return r;
1750 }
1751 /*DEF_STRONG(calloc);*/
1752 
1753 static void *
1754 orecallocarray(struct dir_info *argpool, void *p, size_t oldsize,
1755     size_t newsize, void *f)
1756 {
1757 	struct dir_info *pool;
1758 	struct region_info *r;
1759 	void *newptr;
1760 	size_t sz;
1761 	int i;
1762 
1763 	pool = argpool;
1764 
1765 	if (p == NULL)
1766 		return omalloc(pool, newsize, 1, f);
1767 
1768 	if (oldsize == newsize)
1769 		return p;
1770 
1771 	r = find(pool, p);
1772 	if (r == NULL) {
1773 		if (mopts.malloc_mt) {
1774 			for (i = 0; i < _MALLOC_MUTEXES; i++) {
1775 				if (i == argpool->mutex)
1776 					continue;
1777 				pool->active--;
1778 				_MALLOC_UNLOCK(pool->mutex);
1779 				pool = mopts.malloc_pool[i];
1780 				_MALLOC_LOCK(pool->mutex);
1781 				pool->active++;
1782 				r = find(pool, p);
1783 				if (r != NULL)
1784 					break;
1785 			}
1786 		}
1787 		if (r == NULL)
1788 			wrterror(pool, "bogus pointer (double free?) %p", p);
1789 	}
1790 
1791 	REALSIZE(sz, r);
1792 	if (sz <= MALLOC_MAXCHUNK) {
1793 		if (mopts.chunk_canaries && sz > 0) {
1794 			struct chunk_info *info = (struct chunk_info *)r->size;
1795 			uint32_t chunknum = find_chunknum(pool, r, p, 0);
1796 
1797 			if (info->bits[info->offset + chunknum] != oldsize)
1798 				wrterror(pool, "recorded old size %hu != %zu",
1799 				    info->bits[info->offset + chunknum],
1800 				    oldsize);
1801 		}
1802 	} else if (oldsize != sz - mopts.malloc_guard)
1803 		wrterror(pool, "recorded old size %zu != %zu",
1804 		    sz - mopts.malloc_guard, oldsize);
1805 
1806 	newptr = omalloc(pool, newsize, 0, f);
1807 	if (newptr == NULL)
1808 		goto done;
1809 
1810 	if (newsize > oldsize) {
1811 		memcpy(newptr, p, oldsize);
1812 		memset((char *)newptr + oldsize, 0, newsize - oldsize);
1813 	} else
1814 		memcpy(newptr, p, newsize);
1815 
1816 	ofree(pool, p, 1, 0, 0);
1817 
1818 done:
1819 	if (argpool != pool) {
1820 		pool->active--;
1821 		_MALLOC_UNLOCK(pool->mutex);
1822 		_MALLOC_LOCK(argpool->mutex);
1823 		argpool->active++;
1824 	}
1825 
1826 	return newptr;
1827 }
1828 
1829 static void *
1830 recallocarray_p(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size)
1831 {
1832 	size_t oldsize, newsize;
1833 	void *newptr;
1834 
1835 	if (ptr == NULL)
1836 		return calloc(newnmemb, size);
1837 
1838 	if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1839 	    newnmemb > 0 && SIZE_MAX / newnmemb < size) {
1840 		errno = ENOMEM;
1841 		return NULL;
1842 	}
1843 	newsize = newnmemb * size;
1844 
1845 	if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1846 	    oldnmemb > 0 && SIZE_MAX / oldnmemb < size) {
1847 		errno = EINVAL;
1848 		return NULL;
1849 	}
1850 	oldsize = oldnmemb * size;
1851 
1852 	/*
1853 	 * Don't bother too much if we're shrinking just a bit,
1854 	 * we do not shrink for series of small steps, oh well.
1855 	 */
1856 	if (newsize <= oldsize) {
1857 		size_t d = oldsize - newsize;
1858 
1859 		if (d < oldsize / 2 && d < MALLOC_PAGESIZE) {
1860 			memset((char *)ptr + newsize, 0, d);
1861 			return ptr;
1862 		}
1863 	}
1864 
1865 	newptr = malloc(newsize);
1866 	if (newptr == NULL)
1867 		return NULL;
1868 
1869 	if (newsize > oldsize) {
1870 		memcpy(newptr, ptr, oldsize);
1871 		memset((char *)newptr + oldsize, 0, newsize - oldsize);
1872 	} else
1873 		memcpy(newptr, ptr, newsize);
1874 
1875 	explicit_bzero(ptr, oldsize);
1876 	free(ptr);
1877 
1878 	return newptr;
1879 }
1880 
1881 void *
1882 recallocarray(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size)
1883 {
1884 	struct dir_info *d;
1885 	size_t oldsize = 0, newsize;
1886 	void *r;
1887 	int saved_errno = errno;
1888 
1889 	if (!mopts.internal_funcs)
1890 		return recallocarray_p(ptr, oldnmemb, newnmemb, size);
1891 
1892 	d = getpool();
1893 	if (d == NULL) {
1894 		_malloc_init(0);
1895 		d = getpool();
1896 	}
1897 
1898 	_MALLOC_LOCK(d->mutex);
1899 	d->func = "recallocarray";
1900 
1901 	if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1902 	    newnmemb > 0 && SIZE_MAX / newnmemb < size) {
1903 		_MALLOC_UNLOCK(d->mutex);
1904 		if (mopts.malloc_xmalloc)
1905 			wrterror(d, "out of memory");
1906 		errno = ENOMEM;
1907 		return NULL;
1908 	}
1909 	newsize = newnmemb * size;
1910 
1911 	if (ptr != NULL) {
1912 		if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1913 		    oldnmemb > 0 && SIZE_MAX / oldnmemb < size) {
1914 			_MALLOC_UNLOCK(d->mutex);
1915 			errno = EINVAL;
1916 			return NULL;
1917 		}
1918 		oldsize = oldnmemb * size;
1919 	}
1920 
1921 	if (d->active++) {
1922 		malloc_recurse(d);
1923 		return NULL;
1924 	}
1925 
1926 	r = orecallocarray(d, ptr, oldsize, newsize, CALLER);
1927 
1928 	d->active--;
1929 	_MALLOC_UNLOCK(d->mutex);
1930 	if (r == NULL && mopts.malloc_xmalloc)
1931 		wrterror(d, "out of memory");
1932 	if (r != NULL)
1933 		errno = saved_errno;
1934 	return r;
1935 }
1936 DEF_WEAK(recallocarray);
1937 
1938 
1939 static void *
1940 mapalign(struct dir_info *d, size_t alignment, size_t sz, int zero_fill)
1941 {
1942 	char *p, *q;
1943 
1944 	if (alignment < MALLOC_PAGESIZE || ((alignment - 1) & alignment) != 0)
1945 		wrterror(d, "mapalign bad alignment");
1946 	if (sz != PAGEROUND(sz))
1947 		wrterror(d, "mapalign round");
1948 
1949 	/* Allocate sz + alignment bytes of memory, which must include a
1950 	 * subrange of size bytes that is properly aligned.  Unmap the
1951 	 * other bytes, and then return that subrange.
1952 	 */
1953 
1954 	/* We need sz + alignment to fit into a size_t. */
1955 	if (alignment > SIZE_MAX - sz)
1956 		return MAP_FAILED;
1957 
1958 	p = map(d, NULL, sz + alignment, zero_fill);
1959 	if (p == MAP_FAILED)
1960 		return MAP_FAILED;
1961 	q = (char *)(((uintptr_t)p + alignment - 1) & ~(alignment - 1));
1962 	if (q != p) {
1963 		if (munmap(p, q - p))
1964 			wrterror(d, "munmap %p", p);
1965 	}
1966 	if (munmap(q + sz, alignment - (q - p)))
1967 		wrterror(d, "munmap %p", q + sz);
1968 	STATS_SUB(d->malloc_used, alignment);
1969 
1970 	return q;
1971 }
1972 
1973 static void *
1974 omemalign(struct dir_info *pool, size_t alignment, size_t sz, int zero_fill,
1975     void *f)
1976 {
1977 	size_t psz;
1978 	void *p;
1979 
1980 	/* If between half a page and a page, avoid MALLOC_MOVE. */
1981 	if (sz > MALLOC_MAXCHUNK && sz < MALLOC_PAGESIZE)
1982 		sz = MALLOC_PAGESIZE;
1983 	if (alignment <= MALLOC_PAGESIZE) {
1984 		/*
1985 		 * max(size, alignment) is enough to assure the requested
1986 		 * alignment, since the allocator always allocates
1987 		 * power-of-two blocks.
1988 		 */
1989 		if (sz < alignment)
1990 			sz = alignment;
1991 		return omalloc(pool, sz, zero_fill, f);
1992 	}
1993 
1994 	if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
1995 		errno = ENOMEM;
1996 		return NULL;
1997 	}
1998 
1999 	sz += mopts.malloc_guard;
2000 	psz = PAGEROUND(sz);
2001 
2002 	p = mapalign(pool, alignment, psz, zero_fill);
2003 	if (p == NULL) {
2004 		errno = ENOMEM;
2005 		return NULL;
2006 	}
2007 
2008 	if (insert(pool, p, sz, f)) {
2009 		unmap(pool, p, psz, 0);
2010 		errno = ENOMEM;
2011 		return NULL;
2012 	}
2013 
2014 	if (mopts.malloc_guard) {
2015 		if (mprotect((char *)p + psz - mopts.malloc_guard,
2016 		    mopts.malloc_guard, PROT_NONE))
2017 			wrterror(pool, "mprotect");
2018 		STATS_ADD(pool->malloc_guarded, mopts.malloc_guard);
2019 	}
2020 
2021 	if (mopts.malloc_junk == 2) {
2022 		if (zero_fill)
2023 			memset((char *)p + sz - mopts.malloc_guard,
2024 			    SOME_JUNK, psz - sz);
2025 		else
2026 			memset(p, SOME_JUNK, psz - mopts.malloc_guard);
2027 	}
2028 	else if (mopts.chunk_canaries)
2029 		fill_canary(p, sz - mopts.malloc_guard,
2030 		    psz - mopts.malloc_guard);
2031 
2032 	return p;
2033 }
2034 
2035 int
2036 posix_memalign(void **memptr, size_t alignment, size_t size)
2037 {
2038 	struct dir_info *d;
2039 	int res, saved_errno = errno;
2040 	void *r;
2041 
2042 	/* Make sure that alignment is a large enough power of 2. */
2043 	if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *))
2044 		return EINVAL;
2045 
2046 	d = getpool();
2047 	if (d == NULL) {
2048 		_malloc_init(0);
2049 		d = getpool();
2050 	}
2051 	_MALLOC_LOCK(d->mutex);
2052 	d->func = "posix_memalign";
2053 	if (d->active++) {
2054 		malloc_recurse(d);
2055 		goto err;
2056 	}
2057 	r = omemalign(d, alignment, size, 0, CALLER);
2058 	d->active--;
2059 	_MALLOC_UNLOCK(d->mutex);
2060 	if (r == NULL) {
2061 		if (mopts.malloc_xmalloc)
2062 			wrterror(d, "out of memory");
2063 		goto err;
2064 	}
2065 	errno = saved_errno;
2066 	*memptr = r;
2067 	return 0;
2068 
2069 err:
2070 	res = errno;
2071 	errno = saved_errno;
2072 	return res;
2073 }
2074 /*DEF_STRONG(posix_memalign);*/
2075 
2076 #ifdef MALLOC_STATS
2077 
2078 struct malloc_leak {
2079 	void *f;
2080 	size_t total_size;
2081 	int count;
2082 };
2083 
2084 struct leaknode {
2085 	RBT_ENTRY(leaknode) entry;
2086 	struct malloc_leak d;
2087 };
2088 
2089 static inline int
2090 leakcmp(const struct leaknode *e1, const struct leaknode *e2)
2091 {
2092 	return e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f;
2093 }
2094 
2095 static RBT_HEAD(leaktree, leaknode) leakhead;
2096 RBT_PROTOTYPE(leaktree, leaknode, entry, leakcmp);
2097 RBT_GENERATE(leaktree, leaknode, entry, leakcmp);
2098 
2099 static void
2100 putleakinfo(void *f, size_t sz, int cnt)
2101 {
2102 	struct leaknode key, *p;
2103 	static struct leaknode *page;
2104 	static int used;
2105 
2106 	if (cnt == 0 || page == MAP_FAILED)
2107 		return;
2108 
2109 	key.d.f = f;
2110 	p = RBT_FIND(leaktree, &leakhead, &key);
2111 	if (p == NULL) {
2112 		if (page == NULL ||
2113 		    used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) {
2114 			page = MMAP(MALLOC_PAGESIZE);
2115 			if (page == MAP_FAILED)
2116 				return;
2117 			used = 0;
2118 		}
2119 		p = &page[used++];
2120 		p->d.f = f;
2121 		p->d.total_size = sz * cnt;
2122 		p->d.count = cnt;
2123 		RBT_INSERT(leaktree, &leakhead, p);
2124 	} else {
2125 		p->d.total_size += sz * cnt;
2126 		p->d.count += cnt;
2127 	}
2128 }
2129 
2130 static struct malloc_leak *malloc_leaks;
2131 
2132 static void
2133 writestr(int fd, const char *p)
2134 {
2135 	write(fd, p, strlen(p));
2136 }
2137 
2138 static void
2139 dump_leaks(int fd)
2140 {
2141 	struct leaknode *p;
2142 	char buf[64];
2143 	int i = 0;
2144 
2145 	writestr(fd, "Leak report\n");
2146 	writestr(fd, "                 f     sum      #    avg\n");
2147 	/* XXX only one page of summary */
2148 	if (malloc_leaks == NULL)
2149 		malloc_leaks = MMAP(MALLOC_PAGESIZE);
2150 	if (malloc_leaks != MAP_FAILED)
2151 		memset(malloc_leaks, 0, MALLOC_PAGESIZE);
2152 	RBT_FOREACH(p, leaktree, &leakhead) {
2153 		snprintf(buf, sizeof(buf), "%18p %7zu %6u %6zu\n", p->d.f,
2154 		    p->d.total_size, p->d.count, p->d.total_size / p->d.count);
2155 		write(fd, buf, strlen(buf));
2156 		if (malloc_leaks == MAP_FAILED ||
2157 		    i >= MALLOC_PAGESIZE / sizeof(struct malloc_leak))
2158 			continue;
2159 		malloc_leaks[i].f = p->d.f;
2160 		malloc_leaks[i].total_size = p->d.total_size;
2161 		malloc_leaks[i].count = p->d.count;
2162 		i++;
2163 	}
2164 }
2165 
2166 static void
2167 dump_chunk(int fd, struct chunk_info *p, void *f, int fromfreelist)
2168 {
2169 	char buf[64];
2170 
2171 	while (p != NULL) {
2172 		snprintf(buf, sizeof(buf), "chunk %18p %18p %4d %d/%d\n",
2173 		    p->page, ((p->bits[0] & 1) ? NULL : f),
2174 		    p->size, p->free, p->total);
2175 		write(fd, buf, strlen(buf));
2176 		if (!fromfreelist) {
2177 			if (p->bits[0] & 1)
2178 				putleakinfo(NULL, p->size, p->total - p->free);
2179 			else {
2180 				putleakinfo(f, p->size, 1);
2181 				putleakinfo(NULL, p->size,
2182 				    p->total - p->free - 1);
2183 			}
2184 			break;
2185 		}
2186 		p = LIST_NEXT(p, entries);
2187 		if (p != NULL)
2188 			writestr(fd, "        ");
2189 	}
2190 }
2191 
2192 static void
2193 dump_free_chunk_info(int fd, struct dir_info *d)
2194 {
2195 	char buf[64];
2196 	int i, j, count;
2197 	struct chunk_info *p;
2198 
2199 	writestr(fd, "Free chunk structs:\n");
2200 	for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
2201 		count = 0;
2202 		LIST_FOREACH(p, &d->chunk_info_list[i], entries)
2203 			count++;
2204 		for (j = 0; j < MALLOC_CHUNK_LISTS; j++) {
2205 			p = LIST_FIRST(&d->chunk_dir[i][j]);
2206 			if (p == NULL && count == 0)
2207 				continue;
2208 			snprintf(buf, sizeof(buf), "%2d) %3d ", i, count);
2209 			write(fd, buf, strlen(buf));
2210 			if (p != NULL)
2211 				dump_chunk(fd, p, NULL, 1);
2212 			else
2213 				write(fd, "\n", 1);
2214 		}
2215 	}
2216 
2217 }
2218 
2219 static void
2220 dump_free_page_info(int fd, struct dir_info *d)
2221 {
2222 	char buf[64];
2223 	int i;
2224 
2225 	snprintf(buf, sizeof(buf), "Free pages cached: %zu\n",
2226 	    d->free_regions_size);
2227 	write(fd, buf, strlen(buf));
2228 	for (i = 0; i < mopts.malloc_cache; i++) {
2229 		if (d->free_regions[i].p != NULL) {
2230 			snprintf(buf, sizeof(buf), "%2d) ", i);
2231 			write(fd, buf, strlen(buf));
2232 			snprintf(buf, sizeof(buf), "free at %p: %zu\n",
2233 			    d->free_regions[i].p, d->free_regions[i].size);
2234 			write(fd, buf, strlen(buf));
2235 		}
2236 	}
2237 }
2238 
2239 static void
2240 malloc_dump1(int fd, int poolno, struct dir_info *d)
2241 {
2242 	char buf[100];
2243 	size_t i, realsize;
2244 
2245 	snprintf(buf, sizeof(buf), "Malloc dir of %s pool %d at %p\n", __progname, poolno, d);
2246 	write(fd, buf, strlen(buf));
2247 	if (d == NULL)
2248 		return;
2249 	snprintf(buf, sizeof(buf), "Region slots free %zu/%zu\n",
2250 		d->regions_free, d->regions_total);
2251 	write(fd, buf, strlen(buf));
2252 	snprintf(buf, sizeof(buf), "Finds %zu/%zu\n", d->finds,
2253 	    d->find_collisions);
2254 	write(fd, buf, strlen(buf));
2255 	snprintf(buf, sizeof(buf), "Inserts %zu/%zu\n", d->inserts,
2256 	    d->insert_collisions);
2257 	write(fd, buf, strlen(buf));
2258 	snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes,
2259 	    d->delete_moves);
2260 	write(fd, buf, strlen(buf));
2261 	snprintf(buf, sizeof(buf), "Cheap reallocs %zu/%zu\n",
2262 	    d->cheap_reallocs, d->cheap_realloc_tries);
2263 	write(fd, buf, strlen(buf));
2264 	snprintf(buf, sizeof(buf), "In use %zu\n", d->malloc_used);
2265 	write(fd, buf, strlen(buf));
2266 	snprintf(buf, sizeof(buf), "Guarded %zu\n", d->malloc_guarded);
2267 	write(fd, buf, strlen(buf));
2268 	dump_free_chunk_info(fd, d);
2269 	dump_free_page_info(fd, d);
2270 	writestr(fd,
2271 	    "slot)  hash d  type               page                  f size [free/n]\n");
2272 	for (i = 0; i < d->regions_total; i++) {
2273 		if (d->r[i].p != NULL) {
2274 			size_t h = hash(d->r[i].p) &
2275 			    (d->regions_total - 1);
2276 			snprintf(buf, sizeof(buf), "%4zx) #%4zx %zd ",
2277 			    i, h, h - i);
2278 			write(fd, buf, strlen(buf));
2279 			REALSIZE(realsize, &d->r[i]);
2280 			if (realsize > MALLOC_MAXCHUNK) {
2281 				putleakinfo(d->r[i].f, realsize, 1);
2282 				snprintf(buf, sizeof(buf),
2283 				    "pages %18p %18p %zu\n", d->r[i].p,
2284 				    d->r[i].f, realsize);
2285 				write(fd, buf, strlen(buf));
2286 			} else
2287 				dump_chunk(fd,
2288 				    (struct chunk_info *)d->r[i].size,
2289 				    d->r[i].f, 0);
2290 		}
2291 	}
2292 	dump_leaks(fd);
2293 	write(fd, "\n", 1);
2294 }
2295 
2296 void
2297 malloc_dump(int fd, int poolno, struct dir_info *pool)
2298 {
2299 	int i;
2300 	void *p;
2301 	struct region_info *r;
2302 	int saved_errno = errno;
2303 
2304 	if (pool == NULL)
2305 		return;
2306 	for (i = 0; i < MALLOC_DELAYED_CHUNK_MASK + 1; i++) {
2307 		p = pool->delayed_chunks[i];
2308 		if (p == NULL)
2309 			continue;
2310 		r = find(pool, p);
2311 		if (r == NULL)
2312 			wrterror(pool, "bogus pointer in malloc_dump %p", p);
2313 		free_bytes(pool, r, p);
2314 		pool->delayed_chunks[i] = NULL;
2315 	}
2316 	/* XXX leak when run multiple times */
2317 	RBT_INIT(leaktree, &leakhead);
2318 	malloc_dump1(fd, poolno, pool);
2319 	errno = saved_errno;
2320 }
2321 DEF_WEAK(malloc_dump);
2322 
2323 void
2324 malloc_gdump(int fd)
2325 {
2326 	int i;
2327 	int saved_errno = errno;
2328 
2329 	for (i = 0; i < _MALLOC_MUTEXES; i++)
2330 		malloc_dump(fd, i, mopts.malloc_pool[i]);
2331 
2332 	errno = saved_errno;
2333 }
2334 DEF_WEAK(malloc_gdump);
2335 
2336 static void
2337 malloc_exit(void)
2338 {
2339 	static const char q[] = "malloc() warning: Couldn't dump stats\n";
2340 	int save_errno = errno, fd, i;
2341 	char buf[100];
2342 
2343 	fd = open("malloc.out", O_RDWR|O_APPEND);
2344 	if (fd != -1) {
2345 		snprintf(buf, sizeof(buf), "******** Start dump %s *******\n",
2346 		     __progname);
2347 		write(fd, buf, strlen(buf));
2348 		snprintf(buf, sizeof(buf),
2349 		    "MT=%d I=%d F=%d U=%d J=%d R=%d X=%d C=%d cache=%u G=%zu\n",
2350 		    mopts.malloc_mt, mopts.internal_funcs,
2351 		    mopts.malloc_freenow,
2352 		    mopts.malloc_freeunmap, mopts.malloc_junk,
2353 		    mopts.malloc_realloc, mopts.malloc_xmalloc,
2354 		    mopts.chunk_canaries, mopts.malloc_cache,
2355 		    mopts.malloc_guard);
2356 		write(fd, buf, strlen(buf));
2357 
2358 		for (i = 0; i < _MALLOC_MUTEXES; i++)
2359 			malloc_dump(fd, i, mopts.malloc_pool[i]);
2360 		snprintf(buf, sizeof(buf), "******** End dump %s *******\n",
2361 		    __progname);
2362 		write(fd, buf, strlen(buf));
2363 		close(fd);
2364 	} else
2365 		write(STDERR_FILENO, q, sizeof(q) - 1);
2366 	errno = save_errno;
2367 }
2368 
2369 #endif /* MALLOC_STATS */
2370