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