1 /* $OpenBSD: malloc.c,v 1.84 2006/10/24 04:35:30 tedu Exp $ */
2
3 /*
4 * ----------------------------------------------------------------------------
5 * "THE BEER-WARE LICENSE" (Revision 42):
6 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
7 * can do whatever you want with this stuff. If we meet some day, and you think
8 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
9 * ----------------------------------------------------------------------------
10 */
11
12 /*
13 * Defining MALLOC_EXTRA_SANITY will enable extra checks which are
14 * related to internal conditions and consistency in malloc.c. This has
15 * a noticeable runtime performance hit, and generally will not do you
16 * any good unless you fiddle with the internals of malloc or want
17 * to catch random pointer corruption as early as possible.
18 */
19 #ifndef MALLOC_EXTRA_SANITY
20 #undef MALLOC_EXTRA_SANITY
21 #endif
22
23 /*
24 * Defining MALLOC_STATS will enable you to call malloc_dump() and set
25 * the [dD] options in the MALLOC_OPTIONS environment variable.
26 * It has no run-time performance hit, but does pull in stdio...
27 */
28 #ifndef MALLOC_STATS
29 #undef MALLOC_STATS
30 #endif
31
32 /*
33 * What to use for Junk. This is the byte value we use to fill with
34 * when the 'J' option is enabled.
35 */
36 #define SOME_JUNK 0xd0 /* as in "Duh" :-) */
37
38 #include <sys/param.h>
39 #include <sys/time.h>
40 #include <sys/resource.h>
41 #include <sys/mman.h>
42 #include <sys/uio.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46 #include <unistd.h>
47 #include <fcntl.h>
48 #include <limits.h>
49 #include <errno.h>
50 #include <err.h>
51
52 #include "thread_private.h"
53
54 __IDSTRING(malloc_type, "@(#) mmap malloc 1.84 (OpenBSD)");
55 __RCSID("$MirOS: src/lib/libc/stdlib/malloc_mmap.c,v 1.1 2010/12/23 18:11:45 tg Exp $");
56
57 /*
58 * The basic parameters you can tweak.
59 *
60 * malloc_pageshift pagesize = 1 << malloc_pageshift
61 * It's probably best if this is the native
62 * page size, but it shouldn't have to be.
63 *
64 * malloc_minsize minimum size of an allocation in bytes.
65 * If this is too small it's too much work
66 * to manage them. This is also the smallest
67 * unit of alignment used for the storage
68 * returned by malloc/realloc.
69 *
70 */
71
72 #if defined(__sparc__)
73 #define malloc_pageshift 13U
74 #endif /* __sparc__ */
75
76 #ifndef malloc_pageshift
77 #define malloc_pageshift (PGSHIFT)
78 #endif
79
80 #ifndef malloc_minsize
81 #define malloc_minsize 16UL
82 #endif
83
84 #if !defined(malloc_pagesize)
85 #define malloc_pagesize (1UL<<malloc_pageshift)
86 #endif
87
88 /* How many bits per u_long in the bitmap */
89 #define MALLOC_BITS (NBBY * sizeof(u_long))
90
91
92 /*
93 * No user serviceable parts behind this point.
94 *
95 * This structure describes a page worth of chunks.
96 */
97 struct pginfo {
98 struct pginfo *next; /* next on the free list */
99 void *page; /* Pointer to the page */
100 u_short size; /* size of this page's chunks */
101 u_short shift; /* How far to shift for this size chunks */
102 u_short free; /* How many free chunks */
103 u_short total; /* How many chunk */
104 u_long bits[(malloc_pagesize / malloc_minsize) / MALLOC_BITS];/* Which chunks are free */
105 };
106
107 /*
108 * This structure describes a number of free pages.
109 */
110 struct pgfree {
111 struct pgfree *next; /* next run of free pages */
112 struct pgfree *prev; /* prev run of free pages */
113 void *page; /* pointer to free pages */
114 void *pdir; /* pointer to the base page's dir */
115 size_t size; /* number of bytes free */
116 };
117
118 /*
119 * Magic values to put in the page_directory
120 */
121 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
122 #define MALLOC_FREE ((struct pginfo*) 1)
123 #define MALLOC_FIRST ((struct pginfo*) 2)
124 #define MALLOC_FOLLOW ((struct pginfo*) 3)
125 #define MALLOC_MAGIC ((struct pginfo*) 4)
126
127 #if ((1UL<<malloc_pageshift) != malloc_pagesize)
128 #error "(1UL<<malloc_pageshift) != malloc_pagesize"
129 #endif
130
131 #ifndef malloc_maxsize
132 #define malloc_maxsize ((malloc_pagesize)>>1)
133 #endif
134
135 /* A mask for the offset inside a page. */
136 #define malloc_pagemask ((malloc_pagesize)-1)
137
138 #define pageround(foo) (((foo) + (malloc_pagemask)) & ~malloc_pagemask)
139 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift)
140 #define index2ptr(idx) ((void*)(((idx)-malloc_pageshift)<<malloc_pageshift))
141
142 /* Set when initialization has been done */
143 static unsigned int malloc_started;
144
145 /* Number of free pages we cache */
146 static unsigned int malloc_cache = 16;
147
148 /* Structure used for linking discrete directory pages. */
149 struct pdinfo {
150 struct pginfo **base;
151 struct pdinfo *prev;
152 struct pdinfo *next;
153 u_long dirnum;
154 };
155 static struct pdinfo *last_dir; /* Caches to the last and previous */
156 static struct pdinfo *prev_dir; /* referenced directory pages. */
157
158 static size_t pdi_off;
159 static u_long pdi_mod;
160 #define PD_IDX(num) ((num) / (malloc_pagesize/sizeof(struct pginfo *)))
161 #define PD_OFF(num) ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1))
162 #define PI_IDX(index) ((index) / pdi_mod)
163 #define PI_OFF(index) ((index) % pdi_mod)
164
165 /* The last index in the page directory we care about */
166 static u_long last_index;
167
168 /* Pointer to page directory. Allocated "as if with" malloc */
169 static struct pginfo **page_dir;
170
171 /* Free pages line up here */
172 static struct pgfree free_list;
173
174 /* Abort(), user doesn't handle problems. */
175 static int malloc_abort = 2;
176
177 /* Are we trying to die ? */
178 static int suicide;
179
180 #ifdef MALLOC_STATS
181 /* dump statistics */
182 static int malloc_stats;
183 #endif
184
185 /* avoid outputting warnings? */
186 static int malloc_silent;
187
188 /* always realloc ? */
189 static int malloc_realloc;
190
191 /* mprotect free pages PROT_NONE? */
192 static int malloc_freeprot;
193
194 /* use guard pages after allocations? */
195 static size_t malloc_guard = 0;
196 static size_t malloc_guarded;
197 /* align pointers to end of page? */
198 static int malloc_ptrguard;
199
200 static int malloc_hint;
201
202 /* xmalloc behaviour ? */
203 static int malloc_xmalloc;
204
205 /* zero fill ? */
206 static int malloc_zero;
207
208 /* junk fill ? */
209 static int malloc_junk;
210
211 #ifdef __FreeBSD__
212 /* utrace ? */
213 static int malloc_utrace;
214
215 struct ut {
216 void *p;
217 size_t s;
218 void *r;
219 };
220
221 void utrace(struct ut *, int);
222
223 #define UTRACE(a, b, c) \
224 if (malloc_utrace) \
225 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
226 #else /* !__FreeBSD__ */
227 #define UTRACE(a,b,c)
228 #endif
229
230 /* Status of malloc. */
231 static int malloc_active;
232
233 /* Allocated memory. */
234 static size_t malloc_used;
235
236 /* My last break. */
237 static caddr_t malloc_brk;
238
239 /* One location cache for free-list holders. */
240 static struct pgfree *px;
241
242 /* Compile-time options. */
243 char *malloc_options;
244
245 /* Name of the current public function. */
246 static char *malloc_func;
247
248 #define MMAP(size) \
249 mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
250 -1, (off_t)0)
251
252 /*
253 * Necessary function declarations.
254 */
255 static void *imalloc(size_t size);
256 static void ifree(void *ptr);
257 static void *irealloc(void *ptr, size_t size);
258 static void *malloc_bytes(size_t size);
259
260 static struct pginfo *pginfo_list;
261
262 static struct pgfree *pgfree_list;
263
264 static struct pgfree *
alloc_pgfree()265 alloc_pgfree()
266 {
267 struct pgfree *p;
268 int i;
269
270 if (pgfree_list == NULL) {
271 p = MMAP(malloc_pagesize);
272 if (!p)
273 return NULL;
274 for (i = 0; i < malloc_pagesize / sizeof(*p); i++) {
275 p[i].next = pgfree_list;
276 pgfree_list = &p[i];
277 }
278 }
279 p = pgfree_list;
280 pgfree_list = p->next;
281 memset(p, 0, sizeof *p);
282 return p;
283 }
284
285 static struct pginfo *
alloc_pginfo()286 alloc_pginfo()
287 {
288 struct pginfo *p;
289 int i;
290
291 if (pginfo_list == NULL) {
292 p = MMAP(malloc_pagesize);
293 if (!p)
294 return NULL;
295 for (i = 0; i < malloc_pagesize / sizeof(*p); i++) {
296 p[i].next = pginfo_list;
297 pginfo_list = &p[i];
298 }
299 }
300 p = pginfo_list;
301 pginfo_list = p->next;
302 memset(p, 0, sizeof *p);
303 return p;
304 }
305
306 static void
put_pgfree(struct pgfree * p)307 put_pgfree(struct pgfree *p)
308 {
309 p->next = pgfree_list;
310 pgfree_list = p;
311 }
312
313 static void
put_pginfo(struct pginfo * p)314 put_pginfo(struct pginfo *p)
315 {
316 p->next = pginfo_list;
317 pginfo_list = p;
318 }
319
320 /*
321 * Function for page directory lookup.
322 */
323 static int
pdir_lookup(u_long index,struct pdinfo ** pdi)324 pdir_lookup(u_long index, struct pdinfo ** pdi)
325 {
326 struct pdinfo *spi;
327 u_long pidx = PI_IDX(index);
328
329 if (last_dir != NULL && PD_IDX(last_dir->dirnum) == pidx)
330 *pdi = last_dir;
331 else if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) == pidx)
332 *pdi = prev_dir;
333 else if (last_dir != NULL && prev_dir != NULL) {
334 if ((PD_IDX(last_dir->dirnum) > pidx) ?
335 (PD_IDX(last_dir->dirnum) - pidx) :
336 (pidx - PD_IDX(last_dir->dirnum))
337 < (PD_IDX(prev_dir->dirnum) > pidx) ?
338 (PD_IDX(prev_dir->dirnum) - pidx) :
339 (pidx - PD_IDX(prev_dir->dirnum)))
340 *pdi = last_dir;
341 else
342 *pdi = prev_dir;
343
344 if (PD_IDX((*pdi)->dirnum) > pidx) {
345 for (spi = (*pdi)->prev;
346 spi != NULL && PD_IDX(spi->dirnum) > pidx;
347 spi = spi->prev)
348 *pdi = spi;
349 if (spi != NULL)
350 *pdi = spi;
351 } else
352 for (spi = (*pdi)->next;
353 spi != NULL && PD_IDX(spi->dirnum) <= pidx;
354 spi = spi->next)
355 *pdi = spi;
356 } else {
357 *pdi = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
358 for (spi = *pdi;
359 spi != NULL && PD_IDX(spi->dirnum) <= pidx;
360 spi = spi->next)
361 *pdi = spi;
362 }
363
364 return ((PD_IDX((*pdi)->dirnum) == pidx) ? 0 :
365 (PD_IDX((*pdi)->dirnum) > pidx) ? 1 : -1);
366 }
367
368 #ifdef MALLOC_STATS
369 void
malloc_dump(int fd)370 malloc_dump(int fd)
371 {
372 char buf[1024];
373 struct pginfo **pd;
374 struct pgfree *pf;
375 struct pdinfo *pi;
376 u_long j;
377
378 pd = page_dir;
379 pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
380
381 /* print out all the pages */
382 for (j = 0; j <= last_index;) {
383 snprintf(buf, sizeof buf, "%08lx %5lu ", j << malloc_pageshift, j);
384 write(fd, buf, strlen(buf));
385 if (pd[PI_OFF(j)] == MALLOC_NOT_MINE) {
386 for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_NOT_MINE;) {
387 if (!PI_OFF(++j)) {
388 if ((pi = pi->next) == NULL ||
389 PD_IDX(pi->dirnum) != PI_IDX(j))
390 break;
391 pd = pi->base;
392 j += pdi_mod;
393 }
394 }
395 j--;
396 snprintf(buf, sizeof buf, ".. %5lu not mine\n", j);
397 write(fd, buf, strlen(buf));
398 } else if (pd[PI_OFF(j)] == MALLOC_FREE) {
399 for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FREE;) {
400 if (!PI_OFF(++j)) {
401 if ((pi = pi->next) == NULL ||
402 PD_IDX(pi->dirnum) != PI_IDX(j))
403 break;
404 pd = pi->base;
405 j += pdi_mod;
406 }
407 }
408 j--;
409 snprintf(buf, sizeof buf, ".. %5lu free\n", j);
410 write(fd, buf, strlen(buf));
411 } else if (pd[PI_OFF(j)] == MALLOC_FIRST) {
412 for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FOLLOW;) {
413 if (!PI_OFF(++j)) {
414 if ((pi = pi->next) == NULL ||
415 PD_IDX(pi->dirnum) != PI_IDX(j))
416 break;
417 pd = pi->base;
418 j += pdi_mod;
419 }
420 }
421 j--;
422 snprintf(buf, sizeof buf, ".. %5lu in use\n", j);
423 write(fd, buf, strlen(buf));
424 } else if (pd[PI_OFF(j)] < MALLOC_MAGIC) {
425 snprintf(buf, sizeof buf, "(%p)\n", pd[PI_OFF(j)]);
426 write(fd, buf, strlen(buf));
427 } else {
428 snprintf(buf, sizeof buf, "%p %d (of %d) x %d @ %p --> %p\n",
429 pd[PI_OFF(j)], pd[PI_OFF(j)]->free,
430 pd[PI_OFF(j)]->total, pd[PI_OFF(j)]->size,
431 pd[PI_OFF(j)]->page, pd[PI_OFF(j)]->next);
432 write(fd, buf, strlen(buf));
433 }
434 if (!PI_OFF(++j)) {
435 if ((pi = pi->next) == NULL)
436 break;
437 pd = pi->base;
438 j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod;
439 }
440 }
441
442 for (pf = free_list.next; pf; pf = pf->next) {
443 snprintf(buf, sizeof buf, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
444 pf, pf->page, (char *)pf->page + pf->size,
445 pf->size, pf->prev, pf->next);
446 write(fd, buf, strlen(buf));
447 if (pf == pf->next) {
448 snprintf(buf, sizeof buf, "Free_list loops\n");
449 write(fd, buf, strlen(buf));
450 break;
451 }
452 }
453
454 /* print out various info */
455 snprintf(buf, sizeof buf, "Minsize\t%lu\n", malloc_minsize);
456 write(fd, buf, strlen(buf));
457 snprintf(buf, sizeof buf, "Maxsize\t%lu\n", malloc_maxsize);
458 write(fd, buf, strlen(buf));
459 snprintf(buf, sizeof buf, "Pagesize\t%lu\n", malloc_pagesize);
460 write(fd, buf, strlen(buf));
461 snprintf(buf, sizeof buf, "Pageshift\t%u\n", malloc_pageshift);
462 write(fd, buf, strlen(buf));
463 snprintf(buf, sizeof buf, "In use\t%lu\n", (u_long) malloc_used);
464 write(fd, buf, strlen(buf));
465 snprintf(buf, sizeof buf, "Guarded\t%lu\n", (u_long) malloc_guarded);
466 write(fd, buf, strlen(buf));
467 }
468 #endif /* MALLOC_STATS */
469
470 extern char *__progname;
471
472 static void
wrterror(char * p)473 wrterror(char *p)
474 {
475 char *q = " error: ";
476 struct iovec iov[5];
477
478 iov[0].iov_base = __progname;
479 iov[0].iov_len = strlen(__progname);
480 iov[1].iov_base = malloc_func;
481 iov[1].iov_len = strlen(malloc_func);
482 iov[2].iov_base = q;
483 iov[2].iov_len = strlen(q);
484 iov[3].iov_base = p;
485 iov[3].iov_len = strlen(p);
486 iov[4].iov_base = "\n";
487 iov[4].iov_len = 1;
488 writev(STDERR_FILENO, iov, 5);
489
490 suicide = 1;
491 #ifdef MALLOC_STATS
492 if (malloc_stats)
493 malloc_dump(STDERR_FILENO);
494 #endif /* MALLOC_STATS */
495 malloc_active--;
496 if (malloc_abort)
497 abort();
498 }
499
500 static void
wrtwarning(char * p)501 wrtwarning(char *p)
502 {
503 char *q = " warning: ";
504 struct iovec iov[5];
505
506 if (malloc_abort)
507 wrterror(p);
508 else if (malloc_silent)
509 return;
510
511 iov[0].iov_base = __progname;
512 iov[0].iov_len = strlen(__progname);
513 iov[1].iov_base = malloc_func;
514 iov[1].iov_len = strlen(malloc_func);
515 iov[2].iov_base = q;
516 iov[2].iov_len = strlen(q);
517 iov[3].iov_base = p;
518 iov[3].iov_len = strlen(p);
519 iov[4].iov_base = "\n";
520 iov[4].iov_len = 1;
521
522 writev(STDERR_FILENO, iov, 5);
523 }
524
525 #ifdef MALLOC_STATS
526 static void
malloc_exit(void)527 malloc_exit(void)
528 {
529 char *q = "malloc() warning: Couldn't dump stats\n";
530 int save_errno = errno, fd;
531
532 fd = open("malloc.out", O_RDWR|O_APPEND);
533 if (fd != -1) {
534 malloc_dump(fd);
535 close(fd);
536 } else
537 write(STDERR_FILENO, q, strlen(q));
538 errno = save_errno;
539 }
540 #endif /* MALLOC_STATS */
541
542 /*
543 * Allocate a number of pages from the OS
544 */
545 static void *
map_pages(size_t pages)546 map_pages(size_t pages)
547 {
548 struct pdinfo *pi, *spi;
549 struct pginfo **pd;
550 u_long idx, pidx, lidx;
551 caddr_t result, tail;
552 u_long index, lindex;
553 void *pdregion = NULL;
554 size_t dirs, cnt;
555
556 pages <<= malloc_pageshift;
557 result = MMAP(pages + malloc_guard);
558 if (result == MAP_FAILED) {
559 #ifdef MALLOC_EXTRA_SANITY
560 wrtwarning("(ES): map_pages fails");
561 #endif /* MALLOC_EXTRA_SANITY */
562 errno = ENOMEM;
563 return (NULL);
564 }
565 index = ptr2index(result);
566 tail = result + pages + malloc_guard;
567 lindex = ptr2index(tail) - 1;
568 if (malloc_guard)
569 mprotect(result + pages, malloc_guard, PROT_NONE);
570
571 pidx = PI_IDX(index);
572 lidx = PI_IDX(lindex);
573
574 if (tail > malloc_brk) {
575 malloc_brk = tail;
576 last_index = lindex;
577 }
578
579 dirs = lidx - pidx;
580
581 /* Insert directory pages, if needed. */
582 if (pdir_lookup(index, &pi) != 0)
583 dirs++;
584
585 if (dirs > 0) {
586 pdregion = MMAP(malloc_pagesize * dirs);
587 if (pdregion == MAP_FAILED) {
588 munmap(result, tail - result);
589 #ifdef MALLOC_EXTRA_SANITY
590 wrtwarning("(ES): map_pages fails");
591 #endif
592 errno = ENOMEM;
593 return (NULL);
594 }
595 }
596
597 cnt = 0;
598 for (idx = pidx, spi = pi; idx <= lidx; idx++) {
599 if (pi == NULL || PD_IDX(pi->dirnum) != idx) {
600 pd = (struct pginfo **)((char *)pdregion +
601 cnt * malloc_pagesize);
602 cnt++;
603 memset(pd, 0, malloc_pagesize);
604 pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
605 pi->base = pd;
606 pi->prev = spi;
607 pi->next = spi->next;
608 pi->dirnum = idx * (malloc_pagesize /
609 sizeof(struct pginfo *));
610
611 if (spi->next != NULL)
612 spi->next->prev = pi;
613 spi->next = pi;
614 }
615 if (idx > pidx && idx < lidx) {
616 pi->dirnum += pdi_mod;
617 } else if (idx == pidx) {
618 if (pidx == lidx) {
619 pi->dirnum += (u_long)(tail - result) >>
620 malloc_pageshift;
621 } else {
622 pi->dirnum += pdi_mod - PI_OFF(index);
623 }
624 } else {
625 pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1;
626 }
627 #ifdef MALLOC_EXTRA_SANITY
628 if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > idx) {
629 wrterror("(ES): pages directory overflow");
630 errno = EFAULT;
631 return (NULL);
632 }
633 #endif /* MALLOC_EXTRA_SANITY */
634 if (idx == pidx && pi != last_dir) {
635 prev_dir = last_dir;
636 last_dir = pi;
637 }
638 spi = pi;
639 pi = spi->next;
640 }
641 #ifdef MALLOC_EXTRA_SANITY
642 if (cnt > dirs)
643 wrtwarning("(ES): cnt > dirs");
644 #endif /* MALLOC_EXTRA_SANITY */
645 if (cnt < dirs)
646 munmap((char *)pdregion + cnt * malloc_pagesize,
647 (dirs - cnt) * malloc_pagesize);
648
649 return (result);
650 }
651
652 /*
653 * Initialize the world
654 */
655 static void
malloc_init(void)656 malloc_init(void)
657 {
658 char *p, b[64];
659 int i, j, save_errno = errno;
660
661 _MALLOC_LOCK_INIT();
662
663 #ifdef MALLOC_EXTRA_SANITY
664 malloc_junk = 1;
665 #endif /* MALLOC_EXTRA_SANITY */
666
667 for (i = 0; i < 3; i++) {
668 switch (i) {
669 case 0:
670 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
671 if (j <= 0)
672 continue;
673 b[j] = '\0';
674 p = b;
675 break;
676 case 1:
677 if (issetugid() == 0)
678 p = getenv("MALLOC_OPTIONS");
679 else
680 continue;
681 break;
682 case 2:
683 p = malloc_options;
684 break;
685 default:
686 p = NULL;
687 }
688
689 for (; p != NULL && *p != '\0'; p++) {
690 switch (*p) {
691 case '>':
692 malloc_cache <<= 1;
693 break;
694 case '<':
695 malloc_cache >>= 1;
696 break;
697 case 'a':
698 malloc_abort = 0;
699 break;
700 case 'A':
701 malloc_abort = 1;
702 break;
703 #ifdef MALLOC_STATS
704 case 'd':
705 malloc_stats = 0;
706 break;
707 case 'D':
708 malloc_stats = 1;
709 break;
710 #endif /* MALLOC_STATS */
711 case 'f':
712 malloc_freeprot = 0;
713 break;
714 case 'F':
715 malloc_freeprot = 1;
716 break;
717 case 'g':
718 malloc_guard = 0;
719 break;
720 case 'G':
721 malloc_guard = malloc_pagesize;
722 break;
723 case 'h':
724 malloc_hint = 0;
725 break;
726 case 'H':
727 malloc_hint = 1;
728 break;
729 case 'j':
730 malloc_junk = 0;
731 break;
732 case 'J':
733 malloc_junk = 1;
734 break;
735 case 'n':
736 malloc_silent = 0;
737 break;
738 case 'N':
739 malloc_silent = 1;
740 break;
741 case 'p':
742 malloc_ptrguard = 0;
743 break;
744 case 'P':
745 malloc_ptrguard = 1;
746 break;
747 case 'r':
748 malloc_realloc = 0;
749 break;
750 case 'R':
751 malloc_realloc = 1;
752 break;
753 #ifdef __FreeBSD__
754 case 'u':
755 malloc_utrace = 0;
756 break;
757 case 'U':
758 malloc_utrace = 1;
759 break;
760 #endif /* __FreeBSD__ */
761 case 'x':
762 malloc_xmalloc = 0;
763 break;
764 case 'X':
765 malloc_xmalloc = 1;
766 break;
767 case 'z':
768 malloc_zero = 0;
769 break;
770 case 'Z':
771 malloc_zero = 1;
772 break;
773 default:
774 j = malloc_abort;
775 malloc_abort = 0;
776 wrtwarning("unknown char in MALLOC_OPTIONS");
777 malloc_abort = j;
778 break;
779 }
780 }
781 }
782
783 UTRACE(0, 0, 0);
784
785 /*
786 * We want junk in the entire allocation, and zero only in the part
787 * the user asked for.
788 */
789 if (malloc_zero)
790 malloc_junk = 1;
791
792 #ifdef MALLOC_STATS
793 if (malloc_stats && (atexit(malloc_exit) == -1))
794 wrtwarning("atexit(2) failed."
795 " Will not be able to dump malloc stats on exit");
796 #endif /* MALLOC_STATS */
797
798 /* Allocate one page for the page directory. */
799 page_dir = (struct pginfo **)MMAP(malloc_pagesize);
800
801 if (page_dir == MAP_FAILED) {
802 wrterror("mmap(2) failed, check limits");
803 errno = ENOMEM;
804 return;
805 }
806 pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1);
807 pdi_mod = pdi_off / sizeof(struct pginfo *);
808
809 last_dir = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
810 last_dir->base = page_dir;
811 last_dir->prev = last_dir->next = NULL;
812 last_dir->dirnum = malloc_pageshift;
813
814 /* Been here, done that. */
815 malloc_started++;
816
817 /* Recalculate the cache size in bytes, and make sure it's nonzero. */
818 if (!malloc_cache)
819 malloc_cache++;
820 malloc_cache <<= malloc_pageshift;
821 errno = save_errno;
822 }
823
824 /*
825 * Allocate a number of complete pages
826 */
827 static void *
malloc_pages(size_t size)828 malloc_pages(size_t size)
829 {
830 void *p, *tp;
831 int i;
832 struct pginfo **pd;
833 struct pdinfo *pi;
834 u_long pidx, index;
835 struct pgfree *pf, *delay_free = NULL;
836
837 size = pageround(size) + malloc_guard;
838
839 p = NULL;
840 /* Look for free pages before asking for more */
841 for (pf = free_list.next; pf; pf = pf->next) {
842
843 #ifdef MALLOC_EXTRA_SANITY
844 if (pf->size & malloc_pagemask) {
845 wrterror("(ES): junk length entry on free_list");
846 errno = EFAULT;
847 return (NULL);
848 }
849 if (!pf->size) {
850 wrterror("(ES): zero length entry on free_list");
851 errno = EFAULT;
852 return (NULL);
853 }
854 if (pf->page > (pf->page + pf->size)) {
855 wrterror("(ES): sick entry on free_list");
856 errno = EFAULT;
857 return (NULL);
858 }
859 if ((pi = pf->pdir) == NULL) {
860 wrterror("(ES): invalid page directory on free-list");
861 errno = EFAULT;
862 return (NULL);
863 }
864 if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) {
865 wrterror("(ES): directory index mismatch on free-list");
866 errno = EFAULT;
867 return (NULL);
868 }
869 pd = pi->base;
870 if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) {
871 wrterror("(ES): non-free first page on free-list");
872 errno = EFAULT;
873 return (NULL);
874 }
875 pidx = PI_IDX(ptr2index((pf->page) + (pf->size)) - 1);
876 for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
877 pi = pi->next)
878 ;
879 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
880 wrterror("(ES): last page not referenced in page directory");
881 errno = EFAULT;
882 return (NULL);
883 }
884 pd = pi->base;
885 if (pd[PI_OFF(ptr2index((pf->page) + (pf->size)) - 1)] != MALLOC_FREE) {
886 wrterror("(ES): non-free last page on free-list");
887 errno = EFAULT;
888 return (NULL);
889 }
890 #endif /* MALLOC_EXTRA_SANITY */
891
892 if (pf->size < size)
893 continue;
894
895 if (pf->size == size) {
896 p = pf->page;
897 pi = pf->pdir;
898 if (pf->next != NULL)
899 pf->next->prev = pf->prev;
900 pf->prev->next = pf->next;
901 delay_free = pf;
902 break;
903 }
904 p = pf->page;
905 pf->page = (char *) pf->page + size;
906 pf->size -= size;
907 pidx = PI_IDX(ptr2index(pf->page));
908 for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
909 pi = pi->next)
910 ;
911 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
912 wrterror("(ES): hole in directories");
913 errno = EFAULT;
914 return (NULL);
915 }
916 tp = pf->pdir;
917 pf->pdir = pi;
918 pi = tp;
919 break;
920 }
921
922 size -= malloc_guard;
923
924 #ifdef MALLOC_EXTRA_SANITY
925 if (p != NULL && pi != NULL) {
926 pidx = PD_IDX(pi->dirnum);
927 pd = pi->base;
928 }
929 if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) {
930 wrterror("(ES): allocated non-free page on free-list");
931 errno = EFAULT;
932 return (NULL);
933 }
934 #endif /* MALLOC_EXTRA_SANITY */
935
936 if (p != NULL && (malloc_guard || malloc_freeprot))
937 mprotect(p, size, PROT_READ | PROT_WRITE);
938
939 size >>= malloc_pageshift;
940
941 /* Map new pages */
942 if (p == NULL)
943 p = map_pages(size);
944
945 if (p != NULL) {
946 index = ptr2index(p);
947 pidx = PI_IDX(index);
948 pdir_lookup(index, &pi);
949 #ifdef MALLOC_EXTRA_SANITY
950 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
951 wrterror("(ES): mapped pages not found in directory");
952 errno = EFAULT;
953 return (NULL);
954 }
955 #endif /* MALLOC_EXTRA_SANITY */
956 if (pi != last_dir) {
957 prev_dir = last_dir;
958 last_dir = pi;
959 }
960 pd = pi->base;
961 pd[PI_OFF(index)] = MALLOC_FIRST;
962 for (i = 1; i < size; i++) {
963 if (!PI_OFF(index + i)) {
964 pidx++;
965 pi = pi->next;
966 #ifdef MALLOC_EXTRA_SANITY
967 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
968 wrterror("(ES): hole in mapped pages directory");
969 errno = EFAULT;
970 return (NULL);
971 }
972 #endif /* MALLOC_EXTRA_SANITY */
973 pd = pi->base;
974 }
975 pd[PI_OFF(index + i)] = MALLOC_FOLLOW;
976 }
977 if (malloc_guard) {
978 if (!PI_OFF(index + i)) {
979 pidx++;
980 pi = pi->next;
981 #ifdef MALLOC_EXTRA_SANITY
982 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
983 wrterror("(ES): hole in mapped pages directory");
984 errno = EFAULT;
985 return (NULL);
986 }
987 #endif /* MALLOC_EXTRA_SANITY */
988 pd = pi->base;
989 }
990 pd[PI_OFF(index + i)] = MALLOC_FIRST;
991 }
992 malloc_used += size << malloc_pageshift;
993 malloc_guarded += malloc_guard;
994
995 if (malloc_junk)
996 memset(p, SOME_JUNK, size << malloc_pageshift);
997 }
998 if (delay_free) {
999 if (px == NULL)
1000 px = delay_free;
1001 else
1002 put_pgfree(delay_free);
1003 }
1004 return (p);
1005 }
1006
1007 /*
1008 * Allocate a page of fragments
1009 */
1010
1011 static int
malloc_make_chunks(int bits)1012 malloc_make_chunks(int bits)
1013 {
1014 struct pginfo *bp, **pd;
1015 struct pdinfo *pi;
1016 #ifdef MALLOC_EXTRA_SANITY
1017 u_long pidx;
1018 #endif /* MALLOC_EXTRA_SANITY */
1019 void *pp;
1020 long i, k;
1021
1022 /* Allocate a new bucket */
1023 pp = malloc_pages((size_t)malloc_pagesize);
1024 if (pp == NULL)
1025 return (0);
1026
1027 /* Find length of admin structure */
1028
1029 /* Don't waste more than two chunks on this */
1030
1031 /*
1032 * If we are to allocate a memory protected page for the malloc(0)
1033 * case (when bits=0), it must be from a different page than the
1034 * pginfo page.
1035 * --> Treat it like the big chunk alloc, get a second data page.
1036 */
1037 bp = alloc_pginfo();
1038 if (bp == NULL) {
1039 ifree(pp);
1040 return (0);
1041 }
1042
1043 /* memory protect the page allocated in the malloc(0) case */
1044 if (bits == 0) {
1045 bp->size = 0;
1046 bp->shift = 1;
1047 i = malloc_minsize - 1;
1048 while (i >>= 1)
1049 bp->shift++;
1050 bp->total = bp->free = malloc_pagesize >> bp->shift;
1051 bp->page = pp;
1052
1053 k = mprotect(pp, malloc_pagesize, PROT_NONE);
1054 if (k < 0) {
1055 ifree(pp);
1056 put_pginfo(bp);
1057 return (0);
1058 }
1059 } else {
1060 bp->size = (1UL << bits);
1061 bp->shift = bits;
1062 bp->total = bp->free = malloc_pagesize >> bits;
1063 bp->page = pp;
1064 }
1065
1066 /* set all valid bits in the bitmap */
1067 k = bp->total;
1068 i = 0;
1069
1070 /* Do a bunch at a time */
1071 for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
1072 bp->bits[i / MALLOC_BITS] = ~0UL;
1073
1074 for (; i < k; i++)
1075 bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
1076
1077 pdir_lookup(ptr2index(pp), &pi);
1078 #ifdef MALLOC_EXTRA_SANITY
1079 pidx = PI_IDX(ptr2index(pp));
1080 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1081 wrterror("(ES): mapped pages not found in directory");
1082 errno = EFAULT;
1083 return (0);
1084 }
1085 #endif /* MALLOC_EXTRA_SANITY */
1086 if (pi != last_dir) {
1087 prev_dir = last_dir;
1088 last_dir = pi;
1089 }
1090 pd = pi->base;
1091 pd[PI_OFF(ptr2index(pp))] = bp;
1092
1093 bp->next = page_dir[bits];
1094 page_dir[bits] = bp;
1095
1096 /* MALLOC_UNLOCK */
1097 return (1);
1098 }
1099
1100 /*
1101 * Allocate a fragment
1102 */
1103 static void *
malloc_bytes(size_t size)1104 malloc_bytes(size_t size)
1105 {
1106 int i, j;
1107 size_t k;
1108 u_long u, *lp;
1109 struct pginfo *bp;
1110
1111 /* Don't bother with anything less than this */
1112 /* unless we have a malloc(0) requests */
1113 if (size != 0 && size < malloc_minsize)
1114 size = malloc_minsize;
1115
1116 /* Find the right bucket */
1117 if (size == 0)
1118 j = 0;
1119 else {
1120 j = 1;
1121 i = size - 1;
1122 while (i >>= 1)
1123 j++;
1124 }
1125
1126 /* If it's empty, make a page more of that size chunks */
1127 if (page_dir[j] == NULL && !malloc_make_chunks(j))
1128 return (NULL);
1129
1130 bp = page_dir[j];
1131
1132 /* Find first word of bitmap which isn't empty */
1133 for (lp = bp->bits; !*lp; lp++);
1134
1135 /* Find that bit, and tweak it */
1136 u = 1;
1137 k = 0;
1138 while (!(*lp & u)) {
1139 u += u;
1140 k++;
1141 }
1142
1143 if (malloc_guard) {
1144 /* Walk to a random position. */
1145 i = arc4random_uniform(bp->free);
1146 while (i > 0) {
1147 u += u;
1148 k++;
1149 if (k >= MALLOC_BITS) {
1150 lp++;
1151 u = 1;
1152 k = 0;
1153 }
1154 #ifdef MALLOC_EXTRA_SANITY
1155 if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
1156 wrterror("chunk overflow");
1157 errno = EFAULT;
1158 return (NULL);
1159 }
1160 #endif /* MALLOC_EXTRA_SANITY */
1161 if (*lp & u)
1162 i--;
1163 }
1164 }
1165 *lp ^= u;
1166
1167 /* If there are no more free, remove from free-list */
1168 if (!--bp->free) {
1169 page_dir[j] = bp->next;
1170 bp->next = NULL;
1171 }
1172 /* Adjust to the real offset of that chunk */
1173 k += (lp - bp->bits) * MALLOC_BITS;
1174 k <<= bp->shift;
1175
1176 if (malloc_junk && bp->size != 0)
1177 memset((char *)bp->page + k, SOME_JUNK, (size_t)bp->size);
1178
1179 return ((u_char *) bp->page + k);
1180 }
1181
1182 /*
1183 * Magic so that malloc(sizeof(ptr)) is near the end of the page.
1184 */
1185 #define PTR_GAP (malloc_pagesize - sizeof(void *))
1186 #define PTR_SIZE (sizeof(void *))
1187 #define PTR_ALIGNED(p) (((unsigned long)p & malloc_pagemask) == PTR_GAP)
1188
1189 /*
1190 * Allocate a piece of memory
1191 */
1192 static void *
imalloc(size_t size)1193 imalloc(size_t size)
1194 {
1195 void *result;
1196 int ptralloc = 0;
1197
1198 if (!malloc_started)
1199 malloc_init();
1200
1201 if (suicide)
1202 abort();
1203
1204 /* does not matter if malloc_bytes fails */
1205 if (px == NULL)
1206 px = malloc_bytes(sizeof *px);
1207
1208 if (malloc_ptrguard && size == PTR_SIZE) {
1209 ptralloc = 1;
1210 size = malloc_pagesize;
1211 }
1212 if ((size + malloc_pagesize) < size) { /* Check for overflow */
1213 result = NULL;
1214 errno = ENOMEM;
1215 } else if (size <= malloc_maxsize)
1216 result = malloc_bytes(size);
1217 else
1218 result = malloc_pages(size);
1219
1220 if (malloc_abort == 1 && result == NULL)
1221 wrterror("allocation failed");
1222
1223 if (malloc_zero && result != NULL)
1224 memset(result, 0, size);
1225
1226 if (result && ptralloc)
1227 return ((char *) result + PTR_GAP);
1228 return (result);
1229 }
1230
1231 /*
1232 * Change the size of an allocation.
1233 */
1234 static void *
irealloc(void * ptr,size_t size)1235 irealloc(void *ptr, size_t size)
1236 {
1237 void *p;
1238 size_t osize;
1239 u_long index, i;
1240 struct pginfo **mp;
1241 struct pginfo **pd;
1242 struct pdinfo *pi;
1243 #ifdef MALLOC_EXTRA_SANITY
1244 u_long pidx;
1245 #endif /* MALLOC_EXTRA_SANITY */
1246
1247 if (suicide)
1248 abort();
1249
1250 if (!malloc_started) {
1251 wrtwarning("malloc() has never been called");
1252 return (NULL);
1253 }
1254 if (malloc_ptrguard && PTR_ALIGNED(ptr)) {
1255 if (size <= PTR_SIZE)
1256 return (ptr);
1257
1258 p = imalloc(size);
1259 if (p)
1260 memcpy(p, ptr, PTR_SIZE);
1261 ifree(ptr);
1262 return (p);
1263 }
1264 index = ptr2index(ptr);
1265
1266 if (index < malloc_pageshift) {
1267 wrtwarning("junk pointer, too low to make sense");
1268 return (NULL);
1269 }
1270 if (index > last_index) {
1271 wrtwarning("junk pointer, too high to make sense");
1272 return (NULL);
1273 }
1274 pdir_lookup(index, &pi);
1275 #ifdef MALLOC_EXTRA_SANITY
1276 pidx = PI_IDX(index);
1277 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1278 wrterror("(ES): mapped pages not found in directory");
1279 errno = EFAULT;
1280 return (NULL);
1281 }
1282 #endif /* MALLOC_EXTRA_SANITY */
1283 if (pi != last_dir) {
1284 prev_dir = last_dir;
1285 last_dir = pi;
1286 }
1287 pd = pi->base;
1288 mp = &pd[PI_OFF(index)];
1289
1290 if (*mp == MALLOC_FIRST) { /* Page allocation */
1291
1292 /* Check the pointer */
1293 if ((u_long) ptr & malloc_pagemask) {
1294 wrtwarning("modified (page-) pointer");
1295 return (NULL);
1296 }
1297 /* Find the size in bytes */
1298 i = index;
1299 if (!PI_OFF(++i)) {
1300 pi = pi->next;
1301 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1302 pi = NULL;
1303 if (pi != NULL)
1304 pd = pi->base;
1305 }
1306 for (osize = malloc_pagesize;
1307 pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
1308 osize += malloc_pagesize;
1309 if (!PI_OFF(++i)) {
1310 pi = pi->next;
1311 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1312 pi = NULL;
1313 if (pi != NULL)
1314 pd = pi->base;
1315 }
1316 }
1317
1318 if (!malloc_realloc && size <= osize &&
1319 size > osize - malloc_pagesize) {
1320 if (malloc_junk)
1321 memset((char *)ptr + size, SOME_JUNK, osize - size);
1322 return (ptr); /* ..don't do anything else. */
1323 }
1324 } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */
1325
1326 /* Check the pointer for sane values */
1327 if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) {
1328 wrtwarning("modified (chunk-) pointer");
1329 return (NULL);
1330 }
1331 /* Find the chunk index in the page */
1332 i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift;
1333
1334 /* Verify that it isn't a free chunk already */
1335 if ((*mp)->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
1336 wrtwarning("chunk is already free");
1337 return (NULL);
1338 }
1339 osize = (*mp)->size;
1340
1341 if (!malloc_realloc && size <= osize &&
1342 (size > osize / 2 || osize == malloc_minsize)) {
1343 if (malloc_junk)
1344 memset((char *) ptr + size, SOME_JUNK, osize - size);
1345 return (ptr); /* ..don't do anything else. */
1346 }
1347 } else {
1348 wrtwarning("irealloc: pointer to wrong page");
1349 return (NULL);
1350 }
1351
1352 p = imalloc(size);
1353
1354 if (p != NULL) {
1355 /* copy the lesser of the two sizes, and free the old one */
1356 /* Don't move from/to 0 sized region !!! */
1357 if (osize != 0 && size != 0) {
1358 if (osize < size)
1359 memcpy(p, ptr, osize);
1360 else
1361 memcpy(p, ptr, size);
1362 }
1363 ifree(ptr);
1364 }
1365 return (p);
1366 }
1367
1368 /*
1369 * Free a sequence of pages
1370 */
1371 static void
free_pages(void * ptr,u_long index,struct pginfo * info)1372 free_pages(void *ptr, u_long index, struct pginfo * info)
1373 {
1374 u_long i, pidx, lidx;
1375 size_t l, cachesize = 0;
1376 struct pginfo **pd;
1377 struct pdinfo *pi, *spi;
1378 struct pgfree *pf, *pt = NULL;
1379 caddr_t tail;
1380
1381 if (info == MALLOC_FREE) {
1382 wrtwarning("page is already free");
1383 return;
1384 }
1385 if (info != MALLOC_FIRST) {
1386 wrtwarning("free_pages: pointer to wrong page");
1387 return;
1388 }
1389 if ((u_long) ptr & malloc_pagemask) {
1390 wrtwarning("modified (page-) pointer");
1391 return;
1392 }
1393 /* Count how many pages and mark them free at the same time */
1394 pidx = PI_IDX(index);
1395 pdir_lookup(index, &pi);
1396 #ifdef MALLOC_EXTRA_SANITY
1397 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1398 wrterror("(ES): mapped pages not found in directory");
1399 errno = EFAULT;
1400 return;
1401 }
1402 #endif /* MALLOC_EXTRA_SANITY */
1403
1404 spi = pi; /* Save page index for start of region. */
1405
1406 pd = pi->base;
1407 pd[PI_OFF(index)] = MALLOC_FREE;
1408 i = 1;
1409 if (!PI_OFF(index + i)) {
1410 pi = pi->next;
1411 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i))
1412 pi = NULL;
1413 else
1414 pd = pi->base;
1415 }
1416 while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) {
1417 pd[PI_OFF(index + i)] = MALLOC_FREE;
1418 i++;
1419 if (!PI_OFF(index + i)) {
1420 if ((pi = pi->next) == NULL ||
1421 PD_IDX(pi->dirnum) != PI_IDX(index + i))
1422 pi = NULL;
1423 else
1424 pd = pi->base;
1425 }
1426 }
1427
1428 l = i << malloc_pageshift;
1429
1430 if (malloc_junk)
1431 memset(ptr, SOME_JUNK, l);
1432
1433 malloc_used -= l;
1434 malloc_guarded -= malloc_guard;
1435 if (malloc_guard) {
1436 #ifdef MALLOC_EXTRA_SANITY
1437 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) {
1438 wrterror("(ES): hole in mapped pages directory");
1439 errno = EFAULT;
1440 return;
1441 }
1442 #endif /* MALLOC_EXTRA_SANITY */
1443 pd[PI_OFF(index + i)] = MALLOC_FREE;
1444 l += malloc_guard;
1445 }
1446 tail = (caddr_t)ptr + l;
1447
1448 if (malloc_hint)
1449 madvise(ptr, l, MADV_FREE);
1450
1451 if (malloc_freeprot)
1452 mprotect(ptr, l, PROT_NONE);
1453
1454 /* Add to free-list. */
1455 if (px == NULL && (px = alloc_pgfree()) == NULL)
1456 goto not_return;
1457 px->page = ptr;
1458 px->pdir = spi;
1459 px->size = l;
1460
1461 if (free_list.next == NULL) {
1462 /* Nothing on free list, put this at head. */
1463 px->next = NULL;
1464 px->prev = &free_list;
1465 free_list.next = px;
1466 pf = px;
1467 px = NULL;
1468 } else {
1469 /*
1470 * Find the right spot, leave pf pointing to the modified
1471 * entry.
1472 */
1473
1474 /* Race ahead here, while calculating cache size. */
1475 for (pf = free_list.next;
1476 (caddr_t)ptr > ((caddr_t)pf->page + pf->size)
1477 && pf->next != NULL;
1478 pf = pf->next)
1479 cachesize += pf->size;
1480
1481 /* Finish cache size calculation. */
1482 pt = pf;
1483 while (pt) {
1484 cachesize += pt->size;
1485 pt = pt->next;
1486 }
1487
1488 if ((caddr_t)pf->page > tail) {
1489 /* Insert before entry */
1490 px->next = pf;
1491 px->prev = pf->prev;
1492 pf->prev = px;
1493 px->prev->next = px;
1494 pf = px;
1495 px = NULL;
1496 } else if (((caddr_t)pf->page + pf->size) == ptr) {
1497 /* Append to the previous entry. */
1498 cachesize -= pf->size;
1499 pf->size += l;
1500 if (pf->next != NULL &&
1501 pf->next->page == ((caddr_t)pf->page + pf->size)) {
1502 /* And collapse the next too. */
1503 pt = pf->next;
1504 pf->size += pt->size;
1505 pf->next = pt->next;
1506 if (pf->next != NULL)
1507 pf->next->prev = pf;
1508 }
1509 } else if (pf->page == tail) {
1510 /* Prepend to entry. */
1511 cachesize -= pf->size;
1512 pf->size += l;
1513 pf->page = ptr;
1514 pf->pdir = spi;
1515 } else if (pf->next == NULL) {
1516 /* Append at tail of chain. */
1517 px->next = NULL;
1518 px->prev = pf;
1519 pf->next = px;
1520 pf = px;
1521 px = NULL;
1522 } else {
1523 wrterror("freelist is destroyed");
1524 errno = EFAULT;
1525 return;
1526 }
1527 }
1528
1529 if (pf->pdir != last_dir) {
1530 prev_dir = last_dir;
1531 last_dir = pf->pdir;
1532 }
1533
1534 /* Return something to OS ? */
1535 if (pf->size > (malloc_cache - cachesize)) {
1536
1537 /*
1538 * Keep the cache intact. Notice that the '>' above guarantees that
1539 * the pf will always have at least one page afterwards.
1540 */
1541 if (munmap((char *) pf->page + (malloc_cache - cachesize),
1542 pf->size - (malloc_cache - cachesize)) != 0)
1543 goto not_return;
1544 tail = (caddr_t)pf->page + pf->size;
1545 lidx = ptr2index(tail) - 1;
1546 pf->size = malloc_cache - cachesize;
1547
1548 index = ptr2index((caddr_t)pf->page + pf->size);
1549
1550 pidx = PI_IDX(index);
1551 if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx)
1552 prev_dir = NULL; /* Will be wiped out below ! */
1553
1554 for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
1555 pi = pi->next)
1556 ;
1557
1558 spi = pi;
1559 if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
1560 pd = pi->base;
1561
1562 for (i = index; i <= lidx;) {
1563 if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
1564 pd[PI_OFF(i)] = MALLOC_NOT_MINE;
1565 #ifdef MALLOC_EXTRA_SANITY
1566 if (!PD_OFF(pi->dirnum)) {
1567 wrterror("(ES): pages directory underflow");
1568 errno = EFAULT;
1569 return;
1570 }
1571 #endif /* MALLOC_EXTRA_SANITY */
1572 pi->dirnum--;
1573 }
1574 #ifdef MALLOC_EXTRA_SANITY
1575 else
1576 wrtwarning("(ES): page already unmapped");
1577 #endif /* MALLOC_EXTRA_SANITY */
1578 i++;
1579 if (!PI_OFF(i)) {
1580 /*
1581 * If no page in that dir, free
1582 * directory page.
1583 */
1584 if (!PD_OFF(pi->dirnum)) {
1585 /* Remove from list. */
1586 if (spi == pi)
1587 spi = pi->prev;
1588 if (pi->prev != NULL)
1589 pi->prev->next = pi->next;
1590 if (pi->next != NULL)
1591 pi->next->prev = pi->prev;
1592 pi = pi->next;
1593 munmap(pd, malloc_pagesize);
1594 } else
1595 pi = pi->next;
1596 if (pi == NULL ||
1597 PD_IDX(pi->dirnum) != PI_IDX(i))
1598 break;
1599 pd = pi->base;
1600 }
1601 }
1602 if (pi && !PD_OFF(pi->dirnum)) {
1603 /* Resulting page dir is now empty. */
1604 /* Remove from list. */
1605 if (spi == pi) /* Update spi only if first. */
1606 spi = pi->prev;
1607 if (pi->prev != NULL)
1608 pi->prev->next = pi->next;
1609 if (pi->next != NULL)
1610 pi->next->prev = pi->prev;
1611 pi = pi->next;
1612 munmap(pd, malloc_pagesize);
1613 }
1614 }
1615 if (pi == NULL && malloc_brk == tail) {
1616 /* Resize down the malloc upper boundary. */
1617 last_index = index - 1;
1618 malloc_brk = index2ptr(index);
1619 }
1620
1621 /* XXX: We could realloc/shrink the pagedir here I guess. */
1622 if (pf->size == 0) { /* Remove from free-list as well. */
1623 if (px)
1624 put_pgfree(px);
1625 if ((px = pf->prev) != &free_list) {
1626 if (pi == NULL && last_index == (index - 1)) {
1627 if (spi == NULL) {
1628 malloc_brk = NULL;
1629 i = 11;
1630 } else {
1631 pd = spi->base;
1632 if (PD_IDX(spi->dirnum) < pidx)
1633 index =
1634 ((PD_IDX(spi->dirnum) + 1) *
1635 pdi_mod) - 1;
1636 for (pi = spi, i = index;
1637 pd[PI_OFF(i)] == MALLOC_NOT_MINE;
1638 i--) {
1639 #ifdef MALLOC_EXTRA_SANITY
1640 if (!PI_OFF(i)) {
1641 pi = pi->prev;
1642 if (pi == NULL || i == 0)
1643 break;
1644 pd = pi->base;
1645 i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
1646 }
1647 #endif /* MALLOC_EXTRA_SANITY */
1648 }
1649 malloc_brk = index2ptr(i + 1);
1650 }
1651 last_index = i;
1652 }
1653 if ((px->next = pf->next) != NULL)
1654 px->next->prev = px;
1655 } else {
1656 if ((free_list.next = pf->next) != NULL)
1657 free_list.next->prev = &free_list;
1658 }
1659 px = pf;
1660 last_dir = prev_dir;
1661 prev_dir = NULL;
1662 }
1663 }
1664 not_return:
1665 if (pt != NULL)
1666 put_pgfree(pt);
1667 }
1668
1669 /*
1670 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1671 */
1672
1673 /* ARGSUSED */
1674 static void
free_bytes(void * ptr)1675 free_bytes(void *ptr)
1676 {
1677 struct pginfo **mp, **pd, *info;
1678 struct pdinfo *pi;
1679 #ifdef MALLOC_EXTRA_SANITY
1680 u_long pidx;
1681 #endif /* MALLOC_EXTRA_SANITY */
1682 u_long index;
1683 void *vp;
1684 long i;
1685 void *tmpptr;
1686 unsigned int tmpidx;
1687 /* pointers that we will want to free at some future time */
1688 static void *chunk_buffer[16];
1689
1690
1691 /* delay return, returning a random something from before instead */
1692 tmpidx = arc4random() & 15;
1693 tmpptr = chunk_buffer[tmpidx];
1694 chunk_buffer[tmpidx] = ptr;
1695 ptr = tmpptr;
1696 if (!ptr)
1697 return;
1698
1699 index = ptr2index(ptr);
1700
1701 pdir_lookup(index, &pi);
1702 if (pi != last_dir) {
1703 prev_dir = last_dir;
1704 last_dir = pi;
1705 }
1706 pd = pi->base;
1707 info = pd[PI_OFF(index)];
1708
1709
1710 /* Find the chunk number on the page */
1711 i = ((u_long) ptr & malloc_pagemask) >> info->shift;
1712
1713 if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {
1714 wrtwarning("modified (chunk-) pointer");
1715 return;
1716 }
1717 if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
1718 wrtwarning("chunk is already free");
1719 return;
1720 }
1721 if (malloc_junk && info->size != 0)
1722 memset(ptr, SOME_JUNK, (size_t)info->size);
1723
1724 info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
1725 info->free++;
1726
1727 if (info->size != 0)
1728 mp = page_dir + info->shift;
1729 else
1730 mp = page_dir;
1731
1732 if (info->free == 1) {
1733 /* Page became non-full */
1734
1735 /* Insert in address order */
1736 while (*mp != NULL && (*mp)->next != NULL &&
1737 (*mp)->next->page < info->page)
1738 mp = &(*mp)->next;
1739 info->next = *mp;
1740 *mp = info;
1741 return;
1742 }
1743 if (info->free != info->total)
1744 return;
1745
1746 /* Find & remove this page in the queue */
1747 while (*mp != info) {
1748 mp = &((*mp)->next);
1749 #ifdef MALLOC_EXTRA_SANITY
1750 if (!*mp) {
1751 wrterror("(ES): Not on queue");
1752 errno = EFAULT;
1753 return;
1754 }
1755 #endif /* MALLOC_EXTRA_SANITY */
1756 }
1757 *mp = info->next;
1758
1759 /* Free the page & the info structure if need be */
1760 pdir_lookup(ptr2index(info->page), &pi);
1761 #ifdef MALLOC_EXTRA_SANITY
1762 pidx = PI_IDX(ptr2index(info->page));
1763 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1764 wrterror("(ES): mapped pages not found in directory");
1765 errno = EFAULT;
1766 return;
1767 }
1768 #endif /* MALLOC_EXTRA_SANITY */
1769 if (pi != last_dir) {
1770 prev_dir = last_dir;
1771 last_dir = pi;
1772 }
1773 pd = pi->base;
1774 pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;
1775
1776 /* If the page was mprotected, unprotect it before releasing it */
1777 if (info->size == 0)
1778 mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE);
1779
1780 vp = info->page;
1781 put_pginfo(info);
1782 ifree(vp);
1783 }
1784
1785 static void
ifree(void * ptr)1786 ifree(void *ptr)
1787 {
1788 struct pginfo *info, **pd;
1789 u_long index;
1790 #ifdef MALLOC_EXTRA_SANITY
1791 u_long pidx;
1792 #endif /* MALLOC_EXTRA_SANITY */
1793 struct pdinfo *pi;
1794
1795 if (!malloc_started) {
1796 wrtwarning("malloc() has never been called");
1797 return;
1798 }
1799 /* If we're already sinking, don't make matters any worse. */
1800 if (suicide)
1801 return;
1802
1803 if (malloc_ptrguard && PTR_ALIGNED(ptr))
1804 ptr = (char *)ptr - PTR_GAP;
1805
1806 index = ptr2index(ptr);
1807
1808 if (index < malloc_pageshift) {
1809 warnx("(%p)", ptr);
1810 wrtwarning("ifree: junk pointer, too low to make sense");
1811 return;
1812 }
1813 if (index > last_index) {
1814 warnx("(%p)", ptr);
1815 wrtwarning("ifree: junk pointer, too high to make sense");
1816 return;
1817 }
1818
1819 pdir_lookup(index, &pi);
1820 #ifdef MALLOC_EXTRA_SANITY
1821 pidx = PI_IDX(index);
1822 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1823 wrterror("(ES): mapped pages not found in directory");
1824 errno = EFAULT;
1825 return;
1826 }
1827 #endif /* MALLOC_EXTRA_SANITY */
1828 if (pi != last_dir) {
1829 prev_dir = last_dir;
1830 last_dir = pi;
1831 }
1832 pd = pi->base;
1833 info = pd[PI_OFF(index)];
1834
1835 if (info < MALLOC_MAGIC)
1836 free_pages(ptr, index, info);
1837 else
1838 free_bytes(ptr);
1839
1840 /* does not matter if malloc_bytes fails */
1841 if (px == NULL)
1842 px = alloc_pgfree();
1843
1844 return;
1845 }
1846
1847 /*
1848 * Common function for handling recursion. Only
1849 * print the error message once, to avoid making the problem
1850 * potentially worse.
1851 */
1852 static void
malloc_recurse(void)1853 malloc_recurse(void)
1854 {
1855 static int noprint;
1856
1857 if (noprint == 0) {
1858 noprint = 1;
1859 wrtwarning("recursive call");
1860 }
1861 malloc_active--;
1862 _MALLOC_UNLOCK();
1863 errno = EDEADLK;
1864 }
1865
1866 /*
1867 * These are the public exported interface routines.
1868 */
1869 void *
malloc(size_t size)1870 malloc(size_t size)
1871 {
1872 void *r;
1873
1874 _MALLOC_LOCK();
1875 malloc_func = " in malloc():";
1876 if (malloc_active++) {
1877 malloc_recurse();
1878 return (NULL);
1879 }
1880 r = imalloc(size);
1881 UTRACE(0, size, r);
1882 malloc_active--;
1883 _MALLOC_UNLOCK();
1884 if (malloc_xmalloc && r == NULL) {
1885 wrterror("out of memory");
1886 errno = ENOMEM;
1887 }
1888 return (r);
1889 }
1890
1891 void
free(void * ptr)1892 free(void *ptr)
1893 {
1894 /* This is legal. XXX quick path */
1895 if (ptr == NULL)
1896 return;
1897
1898 _MALLOC_LOCK();
1899 malloc_func = " in free():";
1900 if (malloc_active++) {
1901 malloc_recurse();
1902 return;
1903 }
1904 ifree(ptr);
1905 UTRACE(ptr, 0, 0);
1906 malloc_active--;
1907 _MALLOC_UNLOCK();
1908 return;
1909 }
1910
1911 void *
realloc(void * ptr,size_t size)1912 realloc(void *ptr, size_t size)
1913 {
1914 void *r;
1915
1916 _MALLOC_LOCK();
1917 malloc_func = " in realloc():";
1918 if (malloc_active++) {
1919 malloc_recurse();
1920 return (NULL);
1921 }
1922
1923 if (ptr == NULL)
1924 r = imalloc(size);
1925 else
1926 r = irealloc(ptr, size);
1927
1928 UTRACE(ptr, size, r);
1929 malloc_active--;
1930 _MALLOC_UNLOCK();
1931 if (malloc_xmalloc && r == NULL) {
1932 wrterror("out of memory");
1933 errno = ENOMEM;
1934 }
1935 return (r);
1936 }
1937