Tor  0.4.7.0-alpha-dev
OpenBSD_malloc_Linux.c
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 }
torint.h
Integer definitions used throughout Tor.
Generated by doxygen 1.9.1