2 * ----------------------------------------------------------------------------
3 * "THE BEER-WARE LICENSE" (Revision 42):
4 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
5 * can do whatever you want with this stuff. If we meet some day, and you think
6 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
7 * ----------------------------------------------------------------------------
9 * $FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.49.2.4 2001/12/29 08:10:14 knu Exp $
10 * $DragonFly: src/lib/libc/stdlib/malloc.c,v 1.13 2006/07/27 00:43:09 corecode Exp $
15 * Defining EXTRA_SANITY will enable extra checks which are related
16 * to internal conditions and consistency in malloc.c. This has a
17 * noticeable runtime performance hit, and generally will not do you
18 * any good unless you fiddle with the internals of malloc or want
19 * to catch random pointer corruption as early as possible.
21 #ifndef MALLOC_EXTRA_SANITY
22 #undef MALLOC_EXTRA_SANITY
26 * Defining MALLOC_STATS will enable you to call malloc_dump() and set
27 * the [dD] options in the MALLOC_OPTIONS environment variable.
28 * It has no run-time performance hit, but does pull in stdio...
35 * What to use for Junk. This is the byte value we use to fill with
36 * when the 'J' option is enabled.
38 #define SOME_JUNK 0xd0 /* as in "Duh" :-) */
41 * The basic parameters you can tweak.
43 * malloc_pageshift pagesize = 1 << malloc_pageshift
44 * It's probably best if this is the native
45 * page size, but it doesn't have to be.
47 * malloc_minsize minimum size of an allocation in bytes.
48 * If this is too small it's too much work
49 * to manage them. This is also the smallest
50 * unit of alignment used for the storage
51 * returned by malloc/realloc.
55 #include "namespace.h"
56 #if defined(__FreeBSD__) || defined(__DragonFly__)
57 # if defined(__i386__) || defined(__amd64__)
58 # define malloc_pageshift 12U
59 # define malloc_minsize 16U
62 * Make malloc/free/realloc thread-safe in libc for use with
65 # include "libc_private.h"
66 # include "spinlock.h"
67 static spinlock_t thread_lock
= _SPINLOCK_INITIALIZER
;
68 # define THREAD_LOCK() if (__isthreaded) _SPINLOCK(&thread_lock);
69 # define THREAD_UNLOCK() if (__isthreaded) _SPINUNLOCK(&thread_lock);
70 #endif /* __FreeBSD__ || __DragonFly__ */
72 #if defined(__sparc__) && defined(sun)
73 # define malloc_pageshift 12U
74 # define malloc_minsize 16U
77 # define MMAP_FD fdzero
78 # define INIT_MMAP() \
79 { if ((fdzero = _open(_PATH_DEVZERO, O_RDWR, 0000)) == -1) \
80 wrterror("open of /dev/zero"); }
81 # define MADV_FREE MADV_DONTNEED
82 #endif /* __sparc__ */
84 #ifndef malloc_pageshift
85 #define malloc_pageshift (PGSHIFT)
89 * No user serviceable parts behind this point.
91 #include <sys/types.h>
101 #include "un-namespace.h"
104 * This structure describes a page worth of chunks.
108 struct pginfo
*next
; /* next on the free list */
109 void *page
; /* Pointer to the page */
110 u_short size
; /* size of this page's chunks */
111 u_short shift
; /* How far to shift for this size chunks */
112 u_short free
; /* How many free chunks */
113 u_short total
; /* How many chunk */
114 u_long bits
[1];/* Which chunks are free */
118 * This structure describes a number of free pages.
122 struct pgfree
*next
; /* next run of free pages */
123 struct pgfree
*prev
; /* prev run of free pages */
124 void *page
; /* pointer to free pages */
125 void *pdir
; /* pointer to the base page's dir */
126 size_t size
; /* number of bytes free */
129 /* How many bits per u_long in the bitmap */
130 #define MALLOC_BITS (NBBY * sizeof(u_long))
133 * Magic values to put in the page_directory
135 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
136 #define MALLOC_FREE ((struct pginfo*) 1)
137 #define MALLOC_FIRST ((struct pginfo*) 2)
138 #define MALLOC_FOLLOW ((struct pginfo*) 3)
139 #define MALLOC_MAGIC ((struct pginfo*) 4)
141 #ifndef malloc_pageshift
142 #define malloc_pageshift 12U
145 #ifndef malloc_minsize
146 #define malloc_minsize 16U
149 #if !defined(malloc_pagesize)
150 #define malloc_pagesize (1UL<<malloc_pageshift)
153 #if ((1UL<<malloc_pageshift) != malloc_pagesize)
154 #error "(1UL<<malloc_pageshift) != malloc_pagesize"
157 #ifndef malloc_maxsize
158 #define malloc_maxsize ((malloc_pagesize)>>1)
161 /* A mask for the offset inside a page. */
162 #define malloc_pagemask ((malloc_pagesize)-1)
164 #define pageround(foo) (((foo) + (malloc_pagemask)) & ~malloc_pagemask)
165 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift)
166 #define index2ptr(idx) ((void*)(((idx)-malloc_pageshift)<<malloc_pageshift))
169 #define THREAD_LOCK()
172 #ifndef THREAD_UNLOCK
173 #define THREAD_UNLOCK()
184 /* Set when initialization has been done */
185 static unsigned int malloc_started
;
187 /* Number of free pages we cache */
188 static unsigned int malloc_cache
= 16;
190 /* Structure used for linking discrete directory pages. */
192 struct pginfo
**base
;
197 static struct pdinfo
*last_dir
; /* Caches to the last and previous */
198 static struct pdinfo
*prev_dir
; /* referenced directory pages. */
200 static size_t pdi_off
;
201 static u_long pdi_mod
;
202 #define PD_IDX(num) ((num) / (malloc_pagesize/sizeof(struct pginfo *)))
203 #define PD_OFF(num) ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1))
204 #define PI_IDX(index) ((index) / pdi_mod)
205 #define PI_OFF(index) ((index) % pdi_mod)
207 /* The last index in the page directory we care about */
208 static u_long last_index
;
210 /* Pointer to page directory. Allocated "as if with" malloc */
211 static struct pginfo
**page_dir
;
213 /* Free pages line up here */
214 static struct pgfree free_list
;
216 /* Abort(), user doesn't handle problems. */
217 static int malloc_abort
= 2;
219 /* Are we trying to die ? */
223 /* dump statistics */
224 static int malloc_stats
;
227 /* avoid outputting warnings? */
228 static int malloc_silent
;
230 /* always realloc ? */
231 static int malloc_realloc
;
233 /* mprotect free pages PROT_NONE? */
234 static int malloc_freeprot
;
236 /* use guard pages after allocations? */
237 static int malloc_guard
= 0;
238 static int malloc_guarded
;
239 /* align pointers to end of page? */
240 static int malloc_ptrguard
;
242 /* pass the kernel a hint on free pages ? */
243 static int malloc_hint
= 0;
245 /* xmalloc behaviour ? */
246 static int malloc_xmalloc
;
248 /* sysv behaviour for malloc(0) ? */
249 static int malloc_sysv
;
252 static int malloc_zero
;
255 static int malloc_junk
;
258 static int malloc_utrace
;
260 struct ut
{ void *p
; size_t s
; void *r
; };
262 void utrace (struct ut
*, int);
264 #define UTRACE(a, b, c) \
266 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
268 /* Status of malloc. */
269 static int malloc_active
;
271 /* Allocated memory. */
272 static size_t malloc_used
;
275 static void *malloc_brk
;
277 /* one location cache for free-list holders */
278 static struct pgfree
*px
;
280 /* compile-time options */
281 char *malloc_options
;
283 /* Name of the current public function */
284 static char *malloc_func
;
288 mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
292 * Necessary function declarations.
294 static void *imalloc(size_t size
);
295 static void ifree(void *ptr
);
296 static void *irealloc(void *ptr
, size_t size
);
297 static void *malloc_bytes(size_t size
);
300 * Function for page directory lookup.
303 pdir_lookup(u_long index
, struct pdinfo
** pdi
)
306 u_long pidx
= PI_IDX(index
);
308 if (last_dir
!= NULL
&& PD_IDX(last_dir
->dirnum
) == pidx
)
310 else if (prev_dir
!= NULL
&& PD_IDX(prev_dir
->dirnum
) == pidx
)
312 else if (last_dir
!= NULL
&& prev_dir
!= NULL
) {
313 if ((PD_IDX(last_dir
->dirnum
) > pidx
) ?
314 (PD_IDX(last_dir
->dirnum
) - pidx
) :
315 (pidx
- PD_IDX(last_dir
->dirnum
))
316 < (PD_IDX(prev_dir
->dirnum
) > pidx
) ?
317 (PD_IDX(prev_dir
->dirnum
) - pidx
) :
318 (pidx
- PD_IDX(prev_dir
->dirnum
)))
323 if (PD_IDX((*pdi
)->dirnum
) > pidx
) {
324 for (spi
= (*pdi
)->prev
;
325 spi
!= NULL
&& PD_IDX(spi
->dirnum
) > pidx
;
331 for (spi
= (*pdi
)->next
;
332 spi
!= NULL
&& PD_IDX(spi
->dirnum
) <= pidx
;
336 *pdi
= (struct pdinfo
*) ((caddr_t
) page_dir
+ pdi_off
);
338 spi
!= NULL
&& PD_IDX(spi
->dirnum
) <= pidx
;
343 return ((PD_IDX((*pdi
)->dirnum
) == pidx
) ? 0 :
344 (PD_IDX((*pdi
)->dirnum
) > pidx
) ? 1 : -1);
358 pi
= (struct pdinfo
*) ((caddr_t
) pd
+ pdi_off
);
360 /* print out all the pages */
361 for (j
= 0; j
<= last_index
;) {
362 snprintf(buf
, sizeof buf
, "%08lx %5d ", j
<< malloc_pageshift
, j
);
363 _write(fd
, buf
, strlen(buf
));
364 if (pd
[PI_OFF(j
)] == MALLOC_NOT_MINE
) {
365 for (j
++; j
<= last_index
&& pd
[PI_OFF(j
)] == MALLOC_NOT_MINE
;) {
367 if ((pi
= pi
->next
) == NULL
||
368 PD_IDX(pi
->dirnum
) != PI_IDX(j
))
375 snprintf(buf
, sizeof buf
, ".. %5d not mine\n", j
);
376 _write(fd
, buf
, strlen(buf
));
377 } else if (pd
[PI_OFF(j
)] == MALLOC_FREE
) {
378 for (j
++; j
<= last_index
&& pd
[PI_OFF(j
)] == MALLOC_FREE
;) {
380 if ((pi
= pi
->next
) == NULL
||
381 PD_IDX(pi
->dirnum
) != PI_IDX(j
))
388 snprintf(buf
, sizeof buf
, ".. %5d free\n", j
);
389 _write(fd
, buf
, strlen(buf
));
390 } else if (pd
[PI_OFF(j
)] == MALLOC_FIRST
) {
391 for (j
++; j
<= last_index
&& pd
[PI_OFF(j
)] == MALLOC_FOLLOW
;) {
393 if ((pi
= pi
->next
) == NULL
||
394 PD_IDX(pi
->dirnum
) != PI_IDX(j
))
401 snprintf(buf
, sizeof buf
, ".. %5d in use\n", j
);
402 _write(fd
, buf
, strlen(buf
));
404 } else if (pd
[PI_OFF(j
)] < MALLOC_MAGIC
) {
405 snprintf(buf
, sizeof buf
, "(%p)\n", pd
[PI_OFF(j
)]);
406 _write(fd
, buf
, strlen(buf
));
408 snprintf(buf
, sizeof buf
, "%p %d (of %d) x %d @ %p --> %p\n",
409 pd
[PI_OFF(j
)], pd
[PI_OFF(j
)]->free
,
410 pd
[PI_OFF(j
)]->total
, pd
[PI_OFF(j
)]->size
,
411 pd
[PI_OFF(j
)]->page
, pd
[PI_OFF(j
)]->next
);
412 _write(fd
, buf
, strlen(buf
));
415 if ((pi
= pi
->next
) == NULL
)
418 j
+= (1 + PD_IDX(pi
->dirnum
) - PI_IDX(j
)) * pdi_mod
;
422 for (pf
= free_list
.next
; pf
; pf
= pf
->next
) {
423 snprintf(buf
, sizeof buf
, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
424 pf
, pf
->page
, pf
->page
+ pf
->size
,
425 pf
->size
, pf
->prev
, pf
->next
);
426 _write(fd
, buf
, strlen(buf
));
427 if (pf
== pf
->next
) {
428 snprintf(buf
, sizeof buf
, "Free_list loops\n");
429 _write(fd
, buf
, strlen(buf
));
434 /* print out various info */
435 snprintf(buf
, sizeof buf
, "Minsize\t%d\n", malloc_minsize
);
436 _write(fd
, buf
, strlen(buf
));
437 snprintf(buf
, sizeof buf
, "Maxsize\t%d\n", malloc_maxsize
);
438 _write(fd
, buf
, strlen(buf
));
439 snprintf(buf
, sizeof buf
, "Pagesize\t%lu\n", (u_long
) malloc_pagesize
);
440 _write(fd
, buf
, strlen(buf
));
441 snprintf(buf
, sizeof buf
, "Pageshift\t%d\n", malloc_pageshift
);
442 _write(fd
, buf
, strlen(buf
));
443 snprintf(buf
, sizeof buf
, "In use\t%lu\n", (u_long
) malloc_used
);
444 _write(fd
, buf
, strlen(buf
));
445 snprintf(buf
, sizeof buf
, "Guarded\t%lu\n", (u_long
) malloc_guarded
);
446 _write(fd
, buf
, strlen(buf
));
448 #endif /* MALLOC_STATS */
450 extern char *__progname
;
455 const char *progname
= getprogname();
456 const char *q
= " error: ";
458 _write(STDERR_FILENO
, progname
, strlen(progname
));
459 _write(STDERR_FILENO
, malloc_func
, strlen(malloc_func
));
460 _write(STDERR_FILENO
, q
, strlen(q
));
461 _write(STDERR_FILENO
, p
, strlen(p
));
466 malloc_dump(STDERR_FILENO
);
467 #endif /* MALLOC_STATS */
476 const char *progname
= getprogname();
477 const char *q
= " warning: ";
481 _write(STDERR_FILENO
, progname
, strlen(progname
));
482 _write(STDERR_FILENO
, malloc_func
, strlen(malloc_func
));
483 _write(STDERR_FILENO
, q
, strlen(q
));
484 _write(STDERR_FILENO
, p
, strlen(p
));
491 char *q
= "malloc() warning: Couldn't dump stats\n";
492 int save_errno
= errno
, fd
;
494 fd
= open("malloc.out", O_RDWR
|O_APPEND
);
499 _write(STDERR_FILENO
, q
, strlen(q
));
503 #endif /* MALLOC_STATS */
506 * Allocate a number of pages from the OS
509 map_pages(size_t pages
)
511 struct pdinfo
*pi
, *spi
;
513 u_long idx
, pidx
, lidx
;
515 u_long index
, lindex
;
517 pages
<<= malloc_pageshift
;
518 result
= MMAP(pages
+ malloc_guard
);
519 if (result
== MAP_FAILED
) {
521 #ifdef MALLOC_EXTRA_SANITY
522 wrtwarning("(ES): map_pages fails");
523 #endif /* MALLOC_EXTRA_SANITY */
526 index
= ptr2index(result
);
527 tail
= result
+ pages
+ malloc_guard
;
528 lindex
= ptr2index(tail
) - 1;
530 mprotect(result
+ pages
, malloc_guard
, PROT_NONE
);
532 pidx
= PI_IDX(index
);
533 lidx
= PI_IDX(lindex
);
535 if (tail
> malloc_brk
) {
539 /* Insert directory pages, if needed. */
540 pdir_lookup(index
, &pi
);
542 for (idx
= pidx
, spi
= pi
; idx
<= lidx
; idx
++) {
543 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != idx
) {
544 if ((pd
= MMAP(malloc_pagesize
)) == MAP_FAILED
) {
545 errno
= ENOMEM
; /* XXX */
546 munmap(result
, tail
- result
);
547 #ifdef MALLOC_EXTRA_SANITY
548 wrtwarning("(ES): map_pages fails");
549 #endif /* MALLOC_EXTRA_SANITY */
552 memset(pd
, 0, malloc_pagesize
);
553 pi
= (struct pdinfo
*) ((caddr_t
) pd
+ pdi_off
);
556 pi
->next
= spi
->next
;
557 pi
->dirnum
= idx
* (malloc_pagesize
/ sizeof(struct pginfo
*));
559 if (spi
->next
!= NULL
)
560 spi
->next
->prev
= pi
;
563 if (idx
> pidx
&& idx
< lidx
) {
564 pi
->dirnum
+= pdi_mod
;
565 } else if (idx
== pidx
) {
567 pi
->dirnum
+= (tail
- result
) >> malloc_pageshift
;
569 pi
->dirnum
+= pdi_mod
- PI_OFF(index
);
572 pi
->dirnum
+= PI_OFF(ptr2index(tail
- 1)) + 1;
574 #ifdef MALLOC_EXTRA_SANITY
575 if (PD_OFF(pi
->dirnum
) > pdi_mod
|| PD_IDX(pi
->dirnum
) > idx
) {
576 wrterror("(ES): pages directory overflow");
580 #endif /* MALLOC_EXTRA_SANITY */
581 if (idx
== pidx
&& pi
!= last_dir
) {
593 * Initialize the world
599 int i
, j
, save_errno
= errno
;
603 #ifdef MALLOC_EXTRA_SANITY
605 #endif /* MALLOC_EXTRA_SANITY */
607 for (i
= 0; i
< 3; i
++) {
610 j
= readlink("/etc/malloc.conf", b
, sizeof b
- 1);
617 if (issetugid() == 0)
618 p
= getenv("MALLOC_OPTIONS");
629 for (; p
!= NULL
&& *p
!= '\0'; p
++) {
631 case '>': malloc_cache
<<= 1; break;
632 case '<': malloc_cache
>>= 1; break;
633 case 'a': malloc_abort
= 0; break;
634 case 'A': malloc_abort
= 1; break;
636 case 'd': malloc_stats
= 0; break;
637 case 'D': malloc_stats
= 1; break;
638 #endif /* MALLOC_STATS */
639 case 'f': malloc_freeprot
= 0; break;
640 case 'F': malloc_freeprot
= 1; break;
641 case 'g': malloc_guard
= 0; break;
642 case 'G': malloc_guard
= malloc_pagesize
; break;
643 case 'h': malloc_hint
= 0; break;
644 case 'H': malloc_hint
= 1; break;
645 case 'j': malloc_junk
= 0; break;
646 case 'J': malloc_junk
= 1; break;
647 case 'n': malloc_silent
= 0; break;
648 case 'N': malloc_silent
= 1; break;
649 case 'p': malloc_ptrguard
= 0; break;
650 case 'P': malloc_ptrguard
= 1; break;
651 case 'r': malloc_realloc
= 0; break;
652 case 'R': malloc_realloc
= 1; break;
653 case 'u': malloc_utrace
= 0; break;
654 case 'U': malloc_utrace
= 1; break;
655 case 'v': malloc_sysv
= 0; break;
656 case 'V': malloc_sysv
= 1; break;
657 case 'x': malloc_xmalloc
= 0; break;
658 case 'X': malloc_xmalloc
= 1; break;
659 case 'z': malloc_zero
= 0; break;
660 case 'Z': malloc_zero
= 1; break;
664 wrtwarning("unknown char in MALLOC_OPTIONS");
674 * We want junk in the entire allocation, and zero only in the part
675 * the user asked for.
681 if (malloc_stats
&& (atexit(malloc_exit
) == -1))
682 wrtwarning("atexit(2) failed."
683 " Will not be able to dump malloc stats on exit");
684 #endif /* MALLOC_STATS */
686 /* Allocate one page for the page directory. */
687 page_dir
= (struct pginfo
**)MMAP(malloc_pagesize
);
689 if (page_dir
== MAP_FAILED
) {
690 wrterror("mmap(2) failed, check limits");
694 pdi_off
= (malloc_pagesize
- sizeof(struct pdinfo
)) & ~(malloc_minsize
- 1);
695 pdi_mod
= pdi_off
/ sizeof(struct pginfo
*);
697 last_dir
= (struct pdinfo
*) ((caddr_t
) page_dir
+ pdi_off
);
698 last_dir
->base
= page_dir
;
699 last_dir
->prev
= last_dir
->next
= NULL
;
700 last_dir
->dirnum
= malloc_pageshift
;
702 /* Been here, done that. */
705 /* Recalculate the cache size in bytes, and make sure it's nonzero. */
708 malloc_cache
<<= malloc_pageshift
;
713 * Allocate a number of complete pages
716 malloc_pages(size_t size
)
718 void *p
, *delay_free
= NULL
, *tp
;
725 size
= pageround(size
) + malloc_guard
;
728 /* Look for free pages before asking for more */
729 for (pf
= free_list
.next
; pf
; pf
= pf
->next
) {
731 #ifdef MALLOC_EXTRA_SANITY
732 if (pf
->size
& malloc_pagemask
) {
733 wrterror("(ES): junk length entry on free_list");
738 wrterror("(ES): zero length entry on free_list");
742 if (pf
->page
> (pf
->page
+ pf
->size
)) {
743 wrterror("(ES): sick entry on free_list");
747 if ((pi
= pf
->pdir
) == NULL
) {
748 wrterror("(ES): invalid page directory on free-list");
752 if ((pidx
= PI_IDX(ptr2index(pf
->page
))) != PD_IDX(pi
->dirnum
)) {
753 wrterror("(ES): directory index mismatch on free-list");
758 if (pd
[PI_OFF(ptr2index(pf
->page
))] != MALLOC_FREE
) {
759 wrterror("(ES): non-free first page on free-list");
763 pidx
= PI_IDX(ptr2index((pf
->page
) + (pf
->size
)) - 1);
764 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
767 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
768 wrterror("(ES): last page not referenced in page directory");
773 if (pd
[PI_OFF(ptr2index((pf
->page
) + (pf
->size
)) - 1)] != MALLOC_FREE
) {
774 wrterror("(ES): non-free last page on free-list");
778 #endif /* MALLOC_EXTRA_SANITY */
783 if (pf
->size
== size
) {
786 if (pf
->next
!= NULL
)
787 pf
->next
->prev
= pf
->prev
;
788 pf
->prev
->next
= pf
->next
;
793 pf
->page
= (char *) pf
->page
+ size
;
795 pidx
= PI_IDX(ptr2index(pf
->page
));
796 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
799 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
800 wrterror("(ES): hole in directories");
810 size
-= malloc_guard
;
812 #ifdef MALLOC_EXTRA_SANITY
813 if (p
!= NULL
&& pi
!= NULL
) {
814 pidx
= PD_IDX(pi
->dirnum
);
817 if (p
!= NULL
&& pd
[PI_OFF(ptr2index(p
))] != MALLOC_FREE
) {
818 wrterror("(ES): allocated non-free page on free-list");
822 #endif /* MALLOC_EXTRA_SANITY */
824 if (p
!= NULL
&& (malloc_guard
|| malloc_freeprot
))
825 mprotect(p
, size
, PROT_READ
| PROT_WRITE
);
827 size
>>= malloc_pageshift
;
834 index
= ptr2index(p
);
835 pidx
= PI_IDX(index
);
836 pdir_lookup(index
, &pi
);
837 #ifdef MALLOC_EXTRA_SANITY
838 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
839 wrterror("(ES): mapped pages not found in directory");
843 #endif /* MALLOC_EXTRA_SANITY */
844 if (pi
!= last_dir
) {
849 pd
[PI_OFF(index
)] = MALLOC_FIRST
;
850 for (i
= 1; i
< size
; i
++) {
851 if (!PI_OFF(index
+ i
)) {
854 #ifdef MALLOC_EXTRA_SANITY
855 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
856 wrterror("(ES): hole in mapped pages directory");
860 #endif /* MALLOC_EXTRA_SANITY */
863 pd
[PI_OFF(index
+ i
)] = MALLOC_FOLLOW
;
866 if (!PI_OFF(index
+ i
)) {
869 #ifdef MALLOC_EXTRA_SANITY
870 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
871 wrterror("(ES): hole in mapped pages directory");
875 #endif /* MALLOC_EXTRA_SANITY */
878 pd
[PI_OFF(index
+ i
)] = MALLOC_FIRST
;
880 malloc_used
+= size
<< malloc_pageshift
;
881 malloc_guarded
+= malloc_guard
;
884 memset(p
, SOME_JUNK
, size
<< malloc_pageshift
);
896 * Allocate a page of fragments
899 static __inline__
int
900 malloc_make_chunks(int bits
)
902 struct pginfo
*bp
, **pd
;
908 /* Allocate a new bucket */
909 pp
= malloc_pages((size_t) malloc_pagesize
);
913 /* Find length of admin structure */
914 l
= sizeof *bp
- sizeof(u_long
);
915 l
+= sizeof(u_long
) *
916 (((malloc_pagesize
>> bits
) + MALLOC_BITS
- 1) / MALLOC_BITS
);
918 /* Don't waste more than two chunks on this */
921 * If we are to allocate a memory protected page for the malloc(0)
922 * case (when bits=0), it must be from a different page than the
924 * --> Treat it like the big chunk alloc, get a second data page.
926 if (bits
!= 0 && (1UL << (bits
)) <= l
+ l
) {
927 bp
= (struct pginfo
*) pp
;
929 bp
= (struct pginfo
*) imalloc(l
);
935 /* memory protect the page allocated in the malloc(0) case */
939 i
= malloc_minsize
- 1;
942 bp
->total
= bp
->free
= malloc_pagesize
>> bp
->shift
;
945 k
= mprotect(pp
, malloc_pagesize
, PROT_NONE
);
952 bp
->size
= (1UL << bits
);
954 bp
->total
= bp
->free
= malloc_pagesize
>> bits
;
957 /* set all valid bits in the bitmap */
961 /* Do a bunch at a time */
962 for (; k
- i
>= MALLOC_BITS
; i
+= MALLOC_BITS
)
963 bp
->bits
[i
/ MALLOC_BITS
] = ~0UL;
966 bp
->bits
[i
/ MALLOC_BITS
] |= 1UL << (i
% MALLOC_BITS
);
968 if (bp
== bp
->page
) {
969 /* Mark the ones we stole for ourselves */
970 for (i
= 0; l
> 0; i
++) {
971 bp
->bits
[i
/ MALLOC_BITS
] &= ~(1UL << (i
% MALLOC_BITS
));
979 pidx
= PI_IDX(ptr2index(pp
));
980 pdir_lookup(ptr2index(pp
), &pi
);
981 #ifdef MALLOC_EXTRA_SANITY
982 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
983 wrterror("(ES): mapped pages not found in directory");
987 #endif /* MALLOC_EXTRA_SANITY */
988 if (pi
!= last_dir
) {
993 pd
[PI_OFF(ptr2index(pp
))] = bp
;
995 bp
->next
= page_dir
[bits
];
1003 * Allocate a fragment
1006 malloc_bytes(size_t size
)
1012 /* Don't bother with anything less than this */
1013 /* unless we have a malloc(0) requests */
1014 if (size
!= 0 && size
< malloc_minsize
)
1015 size
= malloc_minsize
;
1017 /* Find the right bucket */
1027 /* If it's empty, make a page more of that size chunks */
1028 if (page_dir
[j
] == NULL
&& !malloc_make_chunks(j
))
1033 /* Find first word of bitmap which isn't empty */
1034 for (lp
= bp
->bits
; !*lp
; lp
++);
1036 /* Find that bit, and tweak it */
1039 while (!(*lp
& u
)) {
1045 /* Walk to a random position. */
1046 i
= arc4random() % bp
->free
;
1050 if (k
>= MALLOC_BITS
) {
1055 #ifdef MALLOC_EXTRA_SANITY
1056 if (lp
- bp
->bits
> (bp
->total
- 1) / MALLOC_BITS
) {
1057 wrterror("chunk overflow");
1061 #endif /* MALLOC_EXTRA_SANITY */
1068 /* If there are no more free, remove from free-list */
1070 page_dir
[j
] = bp
->next
;
1073 /* Adjust to the real offset of that chunk */
1074 k
+= (lp
- bp
->bits
) * MALLOC_BITS
;
1077 if (malloc_junk
&& bp
->size
!= 0)
1078 memset((char *) bp
->page
+ k
, SOME_JUNK
, bp
->size
);
1080 return ((u_char
*) bp
->page
+ k
);
1084 * Magic so that malloc(sizeof(ptr)) is near the end of the page.
1086 #define PTR_GAP (malloc_pagesize - sizeof(void *))
1087 #define PTR_SIZE (sizeof(void *))
1088 #define PTR_ALIGNED(p) (((unsigned long)p & malloc_pagemask) == PTR_GAP)
1091 * Allocate a piece of memory
1094 imalloc(size_t size
)
1099 if (!malloc_started
)
1105 if (malloc_ptrguard
&& size
== PTR_SIZE
) {
1107 size
= malloc_pagesize
;
1109 if ((size
+ malloc_pagesize
) < size
) { /* Check for overflow */
1112 } else if (size
<= malloc_maxsize
)
1113 result
= malloc_bytes(size
);
1115 result
= malloc_pages(size
);
1117 if (malloc_abort
== 1 && result
== NULL
)
1118 wrterror("allocation failed");
1120 if (malloc_zero
&& result
!= NULL
)
1121 memset(result
, 0, size
);
1123 if (result
&& ptralloc
)
1124 return ((char *) result
+ PTR_GAP
);
1129 * Change the size of an allocation.
1132 irealloc(void *ptr
, size_t size
)
1135 u_long osize
, index
, i
;
1144 if (!malloc_started
) {
1145 wrtwarning("malloc() has never been called");
1148 if (malloc_ptrguard
&& PTR_ALIGNED(ptr
)) {
1149 if (size
<= PTR_SIZE
)
1154 memcpy(p
, ptr
, PTR_SIZE
);
1158 index
= ptr2index(ptr
);
1160 if (index
< malloc_pageshift
) {
1161 wrtwarning("junk pointer, too low to make sense");
1165 if (index
> last_index
) {
1166 wrtwarning("junk pointer, too high to make sense");
1170 pidx
= PI_IDX(index
);
1171 pdir_lookup(index
, &pi
);
1173 #ifdef MALLOC_EXTRA_SANITY
1174 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1175 wrterror("(ES): mapped pages not found in directory");
1179 #endif /* MALLOC_EXTRA_SANITY */
1181 if (pi
!= last_dir
) {
1182 prev_dir
= last_dir
;
1186 mp
= &pd
[PI_OFF(index
)];
1188 if (*mp
== MALLOC_FIRST
) { /* Page allocation */
1190 /* Check the pointer */
1191 if ((u_long
) ptr
& malloc_pagemask
) {
1192 wrtwarning("modified (page-) pointer");
1195 /* Find the size in bytes */
1199 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1204 for (osize
= malloc_pagesize
;pi
!= NULL
&& pd
[PI_OFF(i
)] == MALLOC_FOLLOW
;) {
1205 osize
+= malloc_pagesize
;
1208 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1215 if (!malloc_realloc
&& size
<= osize
&&
1216 size
> osize
- malloc_pagesize
) {
1219 memset((char *)ptr
+ size
, SOME_JUNK
, osize
- size
);
1220 return (ptr
); /* ..don't do anything else. */
1222 } else if (*mp
>= MALLOC_MAGIC
) { /* Chunk allocation */
1224 /* Check the pointer for sane values */
1225 if ((u_long
) ptr
& ((1UL << ((*mp
)->shift
)) - 1)) {
1226 wrtwarning("modified (chunk-) pointer");
1229 /* Find the chunk index in the page */
1230 i
= ((u_long
) ptr
& malloc_pagemask
) >> (*mp
)->shift
;
1232 /* Verify that it isn't a free chunk already */
1233 if ((*mp
)->bits
[i
/ MALLOC_BITS
] & (1UL << (i
% MALLOC_BITS
))) {
1234 wrtwarning("chunk is already free");
1237 osize
= (*mp
)->size
;
1239 if (!malloc_realloc
&& size
<= osize
&&
1240 (size
> osize
/ 2 || osize
== malloc_minsize
)) {
1242 memset((char *) ptr
+ size
, SOME_JUNK
, osize
- size
);
1243 return (ptr
); /* ..don't do anything else. */
1246 wrtwarning("irealloc: pointer to wrong page");
1253 /* copy the lesser of the two sizes, and free the old one */
1254 /* Don't move from/to 0 sized region !!! */
1255 if (osize
!= 0 && size
!= 0) {
1257 memcpy(p
, ptr
, osize
);
1259 memcpy(p
, ptr
, size
);
1267 * Free a sequence of pages
1269 static __inline__
void
1270 free_pages(void *ptr
, u_long index
, struct pginfo
* info
)
1272 u_long i
, l
, cachesize
= 0, pidx
, lidx
;
1274 struct pdinfo
*pi
, *spi
;
1275 struct pgfree
*pf
, *pt
= NULL
;
1278 if (info
== MALLOC_FREE
) {
1279 wrtwarning("page is already free");
1282 if (info
!= MALLOC_FIRST
) {
1283 wrtwarning("free_pages: pointer to wrong page");
1286 if ((u_long
) ptr
& malloc_pagemask
) {
1287 wrtwarning("modified (page-) pointer");
1290 /* Count how many pages and mark them free at the same time */
1291 pidx
= PI_IDX(index
);
1292 pdir_lookup(index
, &pi
);
1294 #ifdef MALLOC_EXTRA_SANITY
1295 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1296 wrterror("(ES): mapped pages not found in directory");
1300 #endif /* MALLOC_EXTRA_SANITY */
1302 spi
= pi
; /* Save page index for start of region. */
1305 pd
[PI_OFF(index
)] = MALLOC_FREE
;
1307 if (!PI_OFF(index
+ i
)) {
1309 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
))
1314 while (pi
!= NULL
&& pd
[PI_OFF(index
+ i
)] == MALLOC_FOLLOW
) {
1315 pd
[PI_OFF(index
+ i
)] = MALLOC_FREE
;
1317 if (!PI_OFF(index
+ i
)) {
1318 if ((pi
= pi
->next
) == NULL
||
1319 PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
))
1326 l
= i
<< malloc_pageshift
;
1329 memset(ptr
, SOME_JUNK
, l
);
1332 malloc_guarded
-= malloc_guard
;
1335 #ifdef MALLOC_EXTRA_SANITY
1336 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
)) {
1337 wrterror("(ES): hole in mapped pages directory");
1341 #endif /* MALLOC_EXTRA_SANITY */
1343 pd
[PI_OFF(index
+ i
)] = MALLOC_FREE
;
1346 tail
= (char *) ptr
+ l
;
1349 madvise(ptr
, l
, MADV_FREE
);
1351 if (malloc_freeprot
)
1352 mprotect(ptr
, l
, PROT_NONE
);
1354 /* Add to free-list. */
1356 px
= imalloc(sizeof *px
); /* This cannot fail... */
1361 if (free_list
.next
== NULL
) {
1362 /* Nothing on free list, put this at head. */
1364 px
->prev
= &free_list
;
1365 free_list
.next
= px
;
1370 * Find the right spot, leave pf pointing to the modified
1374 /* Race ahead here, while calculating cache size. */
1375 for (pf
= free_list
.next
;
1376 pf
->page
+ pf
->size
< ptr
&& pf
->next
!= NULL
;
1378 cachesize
+= pf
->size
;
1380 /* Finish cache size calculation. */
1383 cachesize
+= pt
->size
;
1387 if (pf
->page
> tail
) {
1388 /* Insert before entry */
1390 px
->prev
= pf
->prev
;
1392 px
->prev
->next
= px
;
1395 } else if ((pf
->page
+ pf
->size
) == ptr
) {
1396 /* Append to the previous entry. */
1397 cachesize
-= pf
->size
;
1399 if (pf
->next
!= NULL
&&
1400 pf
->page
+ pf
->size
== pf
->next
->page
) {
1401 /* And collapse the next too. */
1403 pf
->size
+= pt
->size
;
1404 pf
->next
= pt
->next
;
1405 if (pf
->next
!= NULL
)
1406 pf
->next
->prev
= pf
;
1408 } else if (pf
->page
== tail
) {
1409 /* Prepend to entry. */
1410 cachesize
-= pf
->size
;
1414 } else if (pf
->next
== NULL
) {
1415 /* Append at tail of chain. */
1422 wrterror("freelist is destroyed");
1428 if (pf
->pdir
!= last_dir
) {
1429 prev_dir
= last_dir
;
1430 last_dir
= pf
->pdir
;
1433 /* Return something to OS ? */
1434 if (pf
->size
> (malloc_cache
- cachesize
)) {
1437 * Keep the cache intact. Notice that the '>' above guarantees that
1438 * the pf will always have at least one page afterwards.
1440 if (munmap((char *) pf
->page
+ (malloc_cache
- cachesize
),
1441 pf
->size
- (malloc_cache
- cachesize
)) != 0)
1443 tail
= pf
->page
+ pf
->size
;
1444 lidx
= ptr2index(tail
) - 1;
1445 pf
->size
= malloc_cache
- cachesize
;
1447 index
= ptr2index(pf
->page
+ pf
->size
);
1449 pidx
= PI_IDX(index
);
1450 if (prev_dir
!= NULL
&& PD_IDX(prev_dir
->dirnum
) >= pidx
)
1451 prev_dir
= NULL
; /* Will be wiped out below ! */
1453 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
1458 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) == pidx
) {
1461 for (i
= index
; i
<= lidx
;) {
1462 if (pd
[PI_OFF(i
)] != MALLOC_NOT_MINE
) {
1463 pd
[PI_OFF(i
)] = MALLOC_NOT_MINE
;
1465 #ifdef MALLOC_EXTRA_SANITY
1466 if (!PD_OFF(pi
->dirnum
)) {
1467 wrterror("(ES): pages directory underflow");
1471 #endif /* MALLOC_EXTRA_SANITY */
1474 #ifdef MALLOC_EXTRA_SANITY
1476 wrtwarning("(ES): page already unmapped");
1477 #endif /* MALLOC_EXTRA_SANITY */
1481 * If no page in that dir, free
1484 if (!PD_OFF(pi
->dirnum
)) {
1485 /* Remove from list. */
1488 if (pi
->prev
!= NULL
)
1489 pi
->prev
->next
= pi
->next
;
1490 if (pi
->next
!= NULL
)
1491 pi
->next
->prev
= pi
->prev
;
1493 munmap(pd
, malloc_pagesize
);
1496 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1501 if (pi
&& !PD_OFF(pi
->dirnum
)) {
1502 /* Resulting page dir is now empty. */
1503 /* Remove from list. */
1504 if (spi
== pi
) /* Update spi only if first. */
1506 if (pi
->prev
!= NULL
)
1507 pi
->prev
->next
= pi
->next
;
1508 if (pi
->next
!= NULL
)
1509 pi
->next
->prev
= pi
->prev
;
1511 munmap(pd
, malloc_pagesize
);
1514 if (pi
== NULL
&& malloc_brk
== tail
) {
1515 /* Resize down the malloc upper boundary. */
1516 last_index
= index
- 1;
1517 malloc_brk
= index2ptr(index
);
1520 /* XXX: We could realloc/shrink the pagedir here I guess. */
1521 if (pf
->size
== 0) { /* Remove from free-list as well. */
1524 if ((px
= pf
->prev
) != &free_list
) {
1525 if (pi
== NULL
&& last_index
== (index
- 1)) {
1531 if (PD_IDX(spi
->dirnum
) < pidx
)
1532 index
= ((PD_IDX(spi
->dirnum
) + 1) * pdi_mod
) - 1;
1533 for (pi
= spi
, i
= index
;pd
[PI_OFF(i
)] == MALLOC_NOT_MINE
;i
--)
1534 #ifdef MALLOC_EXTRA_SANITY
1537 if (pi
== NULL
|| i
== 0)
1540 i
= (PD_IDX(pi
->dirnum
) + 1) * pdi_mod
;
1542 #else /* !MALLOC_EXTRA_SANITY */
1545 #endif /* MALLOC_EXTRA_SANITY */
1546 malloc_brk
= index2ptr(i
+ 1);
1550 if ((px
->next
= pf
->next
) != NULL
)
1551 px
->next
->prev
= px
;
1553 if ((free_list
.next
= pf
->next
) != NULL
)
1554 free_list
.next
->prev
= &free_list
;
1557 last_dir
= prev_dir
;
1567 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1571 static __inline__
void
1572 free_bytes(void *ptr
, int index
, struct pginfo
* info
)
1574 struct pginfo
**mp
, **pd
;
1580 /* Find the chunk number on the page */
1581 i
= ((u_long
) ptr
& malloc_pagemask
) >> info
->shift
;
1583 if ((u_long
) ptr
& ((1UL << (info
->shift
)) - 1)) {
1584 wrtwarning("modified (chunk-) pointer");
1587 if (info
->bits
[i
/ MALLOC_BITS
] & (1UL << (i
% MALLOC_BITS
))) {
1588 wrtwarning("chunk is already free");
1591 if (malloc_junk
&& info
->size
!= 0)
1592 memset(ptr
, SOME_JUNK
, info
->size
);
1594 info
->bits
[i
/ MALLOC_BITS
] |= 1UL << (i
% MALLOC_BITS
);
1597 if (info
->size
!= 0)
1598 mp
= page_dir
+ info
->shift
;
1602 if (info
->free
== 1) {
1603 /* Page became non-full */
1605 /* Insert in address order */
1606 while (*mp
!= NULL
&& (*mp
)->next
!= NULL
&&
1607 (*mp
)->next
->page
< info
->page
)
1613 if (info
->free
!= info
->total
)
1616 /* Find & remove this page in the queue */
1617 while (*mp
!= info
) {
1618 mp
= &((*mp
)->next
);
1619 #ifdef MALLOC_EXTRA_SANITY
1621 wrterror("(ES): Not on queue");
1625 #endif /* MALLOC_EXTRA_SANITY */
1629 /* Free the page & the info structure if need be */
1630 pidx
= PI_IDX(ptr2index(info
->page
));
1631 pdir_lookup(ptr2index(info
->page
), &pi
);
1632 #ifdef MALLOC_EXTRA_SANITY
1633 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1634 wrterror("(ES): mapped pages not found in directory");
1638 #endif /* MALLOC_EXTRA_SANITY */
1639 if (pi
!= last_dir
) {
1640 prev_dir
= last_dir
;
1644 pd
[PI_OFF(ptr2index(info
->page
))] = MALLOC_FIRST
;
1646 /* If the page was mprotected, unprotect it before releasing it */
1647 if (info
->size
== 0)
1648 mprotect(info
->page
, malloc_pagesize
, PROT_READ
| PROT_WRITE
);
1650 vp
= info
->page
; /* Order is important ! */
1651 if (vp
!= (void *) info
)
1659 struct pginfo
*info
, **pd
;
1667 if (!malloc_started
) {
1668 wrtwarning("malloc() has never been called");
1671 /* If we're already sinking, don't make matters any worse. */
1675 if (malloc_ptrguard
&& PTR_ALIGNED(ptr
))
1676 ptr
= (char *) ptr
- PTR_GAP
;
1678 index
= ptr2index(ptr
);
1680 if (index
< malloc_pageshift
) {
1682 wrtwarning("ifree: junk pointer, too low to make sense");
1685 if (index
> last_index
) {
1687 wrtwarning("ifree: junk pointer, too high to make sense");
1690 pidx
= PI_IDX(index
);
1691 pdir_lookup(index
, &pi
);
1692 #ifdef MALLOC_EXTRA_SANITY
1693 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1694 wrterror("(ES): mapped pages not found in directory");
1698 #endif /* MALLOC_EXTRA_SANITY */
1699 if (pi
!= last_dir
) {
1700 prev_dir
= last_dir
;
1704 info
= pd
[PI_OFF(index
)];
1706 if (info
< MALLOC_MAGIC
)
1707 free_pages(ptr
, index
, info
);
1709 free_bytes(ptr
, index
, info
);
1714 * Common function for handling recursion. Only
1715 * print the error message once, to avoid making the problem
1716 * potentially worse.
1719 malloc_recurse(void)
1725 wrtwarning("recursive call");
1733 * These are the public exported interface routines.
1741 malloc_func
= " in malloc():";
1742 if (malloc_active
++) {
1746 if (malloc_sysv
&& !size
)
1753 if (malloc_xmalloc
&& r
== NULL
) {
1754 wrterror("out of memory");
1764 malloc_func
= " in free():";
1765 if (malloc_active
++) {
1777 realloc(void *ptr
, size_t size
)
1782 malloc_func
= " in realloc():";
1783 if (malloc_active
++) {
1788 if (malloc_sysv
&& !size
) {
1791 } else if (ptr
== NULL
)
1794 r
= irealloc(ptr
, size
);
1796 UTRACE(ptr
, size
, r
);
1799 if (malloc_xmalloc
&& r
== NULL
) {
1800 wrterror("out of memory");