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