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.
45 * WARNING! Must be exactly the page size in bits
46 * or the page-directory will not be properly aligned.
48 * malloc_minsize minimum size of an allocation in bytes.
49 * If this is too small it's too much work
50 * to manage them. This is also the smallest
51 * unit of alignment used for the storage
52 * returned by malloc/realloc.
56 #include "namespace.h"
57 #if defined(__FreeBSD__) || defined(__DragonFly__)
58 # if defined(__i386__) || defined(__amd64__)
59 # define malloc_pageshift 12U
60 # define malloc_minsize 16U
62 # error "What OS is this?"
65 #error "What OS is this?"
69 * Make malloc/free/realloc thread-safe in libc for use with
72 #include "libc_private.h"
75 static spinlock_t thread_lock
= _SPINLOCK_INITIALIZER
;
77 #define THREAD_LOCK() if (__isthreaded) _SPINLOCK(&thread_lock);
78 #define THREAD_UNLOCK() if (__isthreaded) _SPINUNLOCK(&thread_lock);
81 * No user serviceable parts behind this point.
83 #include <sys/types.h>
93 #include "un-namespace.h"
96 * This structure describes a page worth of chunks.
100 struct pginfo
*next
; /* next on the free list */
101 void *page
; /* Pointer to the page */
102 u_short size
; /* size of this page's chunks */
103 u_short shift
; /* How far to shift for this size chunks */
104 u_short free
; /* How many free chunks */
105 u_short total
; /* How many chunk */
106 u_long bits
[1];/* Which chunks are free */
110 * This structure describes a number of free pages.
114 struct pgfree
*next
; /* next run of free pages */
115 struct pgfree
*prev
; /* prev run of free pages */
116 void *page
; /* pointer to free pages */
117 void *pdir
; /* pointer to the base page's dir */
118 size_t size
; /* number of bytes free */
121 /* How many bits per u_long in the bitmap */
122 #define MALLOC_BITS (NBBY * sizeof(u_long))
125 * Magic values to put in the page_directory
127 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
128 #define MALLOC_FREE ((struct pginfo*) 1)
129 #define MALLOC_FIRST ((struct pginfo*) 2)
130 #define MALLOC_FOLLOW ((struct pginfo*) 3)
131 #define MALLOC_MAGIC ((struct pginfo*) 4)
133 #ifndef malloc_minsize
134 #define malloc_minsize 16U
137 #if !defined(malloc_pagesize)
138 #define malloc_pagesize (1UL<<malloc_pageshift)
141 #if ((1UL<<malloc_pageshift) != malloc_pagesize)
142 #error "(1UL<<malloc_pageshift) != malloc_pagesize"
145 #ifndef malloc_maxsize
146 #define malloc_maxsize ((malloc_pagesize)>>1)
149 /* A mask for the offset inside a page. */
150 #define malloc_pagemask ((malloc_pagesize)-1)
152 #define pageround(foo) (((foo) + (malloc_pagemask)) & ~malloc_pagemask)
153 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift)
154 #define index2ptr(idx) ((void*)(((idx)-malloc_pageshift)<<malloc_pageshift))
157 #define THREAD_LOCK()
160 #ifndef THREAD_UNLOCK
161 #define THREAD_UNLOCK()
172 /* Set when initialization has been done */
173 static unsigned int malloc_started
;
175 /* Number of free pages we cache */
176 static unsigned int malloc_cache
= 16;
178 /* Structure used for linking discrete directory pages. */
180 struct pginfo
**base
;
185 static struct pdinfo
*last_dir
; /* Caches to the last and previous */
186 static struct pdinfo
*prev_dir
; /* referenced directory pages. */
188 static size_t pdi_off
;
189 static u_long pdi_mod
;
190 #define PD_IDX(num) ((num) / (malloc_pagesize/sizeof(struct pginfo *)))
191 #define PD_OFF(num) ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1))
192 #define PI_IDX(index) ((index) / pdi_mod)
193 #define PI_OFF(index) ((index) % pdi_mod)
195 /* The last index in the page directory we care about */
196 static u_long last_index
;
198 /* Pointer to page directory. Allocated "as if with" malloc */
199 static struct pginfo
**page_dir
;
201 /* Free pages line up here */
202 static struct pgfree free_list
;
204 /* Abort(), user doesn't handle problems. */
205 static int malloc_abort
= 2;
207 /* Are we trying to die ? */
211 /* dump statistics */
212 static int malloc_stats
;
215 /* avoid outputting warnings? */
216 static int malloc_silent
;
218 /* always realloc ? */
219 static int malloc_realloc
;
221 /* mprotect free pages PROT_NONE? */
222 static int malloc_freeprot
;
224 /* use guard pages after allocations? */
225 static int malloc_guard
= 0;
226 static int malloc_guarded
;
227 /* align pointers to end of page? */
228 static int malloc_ptrguard
;
230 /* pass the kernel a hint on free pages ? */
231 static int malloc_hint
= 0;
233 /* xmalloc behaviour ? */
234 static int malloc_xmalloc
;
236 /* sysv behaviour for malloc(0) ? */
237 static int malloc_sysv
;
240 static int malloc_zero
;
243 static int malloc_junk
;
246 static int malloc_utrace
;
248 struct ut
{ void *p
; size_t s
; void *r
; };
250 void utrace (struct ut
*, int);
252 #define UTRACE(a, b, c) \
254 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
256 /* Status of malloc. */
257 static int malloc_active
;
259 /* Allocated memory. */
260 static size_t malloc_used
;
263 static void *malloc_brk
;
265 /* one location cache for free-list holders */
266 static struct pgfree
*px
;
268 /* compile-time options */
269 char *malloc_options
;
271 /* Name of the current public function */
272 static char *malloc_func
;
276 mmap(NULL, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
280 * Necessary function declarations.
282 static void *imalloc(size_t size
);
283 static void ifree(void *ptr
);
284 static void *irealloc(void *ptr
, size_t size
);
285 static void *malloc_bytes(size_t size
);
288 * Function for page directory lookup.
291 pdir_lookup(u_long index
, struct pdinfo
** pdi
)
294 u_long pidx
= PI_IDX(index
);
296 if (last_dir
!= NULL
&& PD_IDX(last_dir
->dirnum
) == pidx
)
298 else if (prev_dir
!= NULL
&& PD_IDX(prev_dir
->dirnum
) == pidx
)
300 else if (last_dir
!= NULL
&& prev_dir
!= NULL
) {
301 if ((PD_IDX(last_dir
->dirnum
) > pidx
) ?
302 (PD_IDX(last_dir
->dirnum
) - pidx
) :
303 (pidx
- PD_IDX(last_dir
->dirnum
))
304 < (PD_IDX(prev_dir
->dirnum
) > pidx
) ?
305 (PD_IDX(prev_dir
->dirnum
) - pidx
) :
306 (pidx
- PD_IDX(prev_dir
->dirnum
)))
311 if (PD_IDX((*pdi
)->dirnum
) > pidx
) {
312 for (spi
= (*pdi
)->prev
;
313 spi
!= NULL
&& PD_IDX(spi
->dirnum
) > pidx
;
319 for (spi
= (*pdi
)->next
;
320 spi
!= NULL
&& PD_IDX(spi
->dirnum
) <= pidx
;
324 *pdi
= (struct pdinfo
*) ((caddr_t
) page_dir
+ pdi_off
);
326 spi
!= NULL
&& PD_IDX(spi
->dirnum
) <= pidx
;
331 return ((PD_IDX((*pdi
)->dirnum
) == pidx
) ? 0 :
332 (PD_IDX((*pdi
)->dirnum
) > pidx
) ? 1 : -1);
346 pi
= (struct pdinfo
*) ((caddr_t
) pd
+ pdi_off
);
348 /* print out all the pages */
349 for (j
= 0; j
<= last_index
;) {
350 snprintf(buf
, sizeof buf
, "%08lx %5d ", j
<< malloc_pageshift
, j
);
351 _write(fd
, buf
, strlen(buf
));
352 if (pd
[PI_OFF(j
)] == MALLOC_NOT_MINE
) {
353 for (j
++; j
<= last_index
&& pd
[PI_OFF(j
)] == MALLOC_NOT_MINE
;) {
355 if ((pi
= pi
->next
) == NULL
||
356 PD_IDX(pi
->dirnum
) != PI_IDX(j
))
363 snprintf(buf
, sizeof buf
, ".. %5d not mine\n", j
);
364 _write(fd
, buf
, strlen(buf
));
365 } else if (pd
[PI_OFF(j
)] == MALLOC_FREE
) {
366 for (j
++; j
<= last_index
&& pd
[PI_OFF(j
)] == MALLOC_FREE
;) {
368 if ((pi
= pi
->next
) == NULL
||
369 PD_IDX(pi
->dirnum
) != PI_IDX(j
))
376 snprintf(buf
, sizeof buf
, ".. %5d free\n", j
);
377 _write(fd
, buf
, strlen(buf
));
378 } else if (pd
[PI_OFF(j
)] == MALLOC_FIRST
) {
379 for (j
++; j
<= last_index
&& pd
[PI_OFF(j
)] == MALLOC_FOLLOW
;) {
381 if ((pi
= pi
->next
) == NULL
||
382 PD_IDX(pi
->dirnum
) != PI_IDX(j
))
389 snprintf(buf
, sizeof buf
, ".. %5d in use\n", j
);
390 _write(fd
, buf
, strlen(buf
));
392 } else if (pd
[PI_OFF(j
)] < MALLOC_MAGIC
) {
393 snprintf(buf
, sizeof buf
, "(%p)\n", pd
[PI_OFF(j
)]);
394 _write(fd
, buf
, strlen(buf
));
396 snprintf(buf
, sizeof buf
, "%p %d (of %d) x %d @ %p --> %p\n",
397 pd
[PI_OFF(j
)], pd
[PI_OFF(j
)]->free
,
398 pd
[PI_OFF(j
)]->total
, pd
[PI_OFF(j
)]->size
,
399 pd
[PI_OFF(j
)]->page
, pd
[PI_OFF(j
)]->next
);
400 _write(fd
, buf
, strlen(buf
));
403 if ((pi
= pi
->next
) == NULL
)
406 j
+= (1 + PD_IDX(pi
->dirnum
) - PI_IDX(j
)) * pdi_mod
;
410 for (pf
= free_list
.next
; pf
; pf
= pf
->next
) {
411 snprintf(buf
, sizeof buf
, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
412 pf
, pf
->page
, pf
->page
+ pf
->size
,
413 pf
->size
, pf
->prev
, pf
->next
);
414 _write(fd
, buf
, strlen(buf
));
415 if (pf
== pf
->next
) {
416 snprintf(buf
, sizeof buf
, "Free_list loops\n");
417 _write(fd
, buf
, strlen(buf
));
422 /* print out various info */
423 snprintf(buf
, sizeof buf
, "Minsize\t%d\n", malloc_minsize
);
424 _write(fd
, buf
, strlen(buf
));
425 snprintf(buf
, sizeof buf
, "Maxsize\t%d\n", malloc_maxsize
);
426 _write(fd
, buf
, strlen(buf
));
427 snprintf(buf
, sizeof buf
, "Pagesize\t%lu\n", (u_long
) malloc_pagesize
);
428 _write(fd
, buf
, strlen(buf
));
429 snprintf(buf
, sizeof buf
, "Pageshift\t%d\n", malloc_pageshift
);
430 _write(fd
, buf
, strlen(buf
));
431 snprintf(buf
, sizeof buf
, "In use\t%lu\n", (u_long
) malloc_used
);
432 _write(fd
, buf
, strlen(buf
));
433 snprintf(buf
, sizeof buf
, "Guarded\t%lu\n", (u_long
) malloc_guarded
);
434 _write(fd
, buf
, strlen(buf
));
436 #endif /* MALLOC_STATS */
441 const char *progname
= getprogname();
442 const char *q
= " error: ";
444 _write(STDERR_FILENO
, progname
, strlen(progname
));
445 _write(STDERR_FILENO
, malloc_func
, strlen(malloc_func
));
446 _write(STDERR_FILENO
, q
, strlen(q
));
447 _write(STDERR_FILENO
, p
, strlen(p
));
452 malloc_dump(STDERR_FILENO
);
453 #endif /* MALLOC_STATS */
462 const char *progname
= getprogname();
463 const char *q
= " warning: ";
467 _write(STDERR_FILENO
, progname
, strlen(progname
));
468 _write(STDERR_FILENO
, malloc_func
, strlen(malloc_func
));
469 _write(STDERR_FILENO
, q
, strlen(q
));
470 _write(STDERR_FILENO
, p
, strlen(p
));
477 char *q
= "malloc() warning: Couldn't dump stats\n";
478 int save_errno
= errno
, fd
;
480 fd
= open("malloc.out", O_RDWR
|O_APPEND
);
485 _write(STDERR_FILENO
, q
, strlen(q
));
489 #endif /* MALLOC_STATS */
492 * Allocate a number of pages from the OS
495 map_pages(size_t pages
)
497 struct pdinfo
*pi
, *spi
;
499 u_long idx
, pidx
, lidx
;
501 u_long index
, lindex
;
503 pages
<<= malloc_pageshift
;
504 result
= MMAP(pages
+ malloc_guard
);
505 if (result
== MAP_FAILED
) {
507 #ifdef MALLOC_EXTRA_SANITY
508 wrtwarning("(ES): map_pages fails");
509 #endif /* MALLOC_EXTRA_SANITY */
512 index
= ptr2index(result
);
513 tail
= result
+ pages
+ malloc_guard
;
514 lindex
= ptr2index(tail
) - 1;
516 mprotect(result
+ pages
, malloc_guard
, PROT_NONE
);
518 pidx
= PI_IDX(index
);
519 lidx
= PI_IDX(lindex
);
521 if (tail
> malloc_brk
) {
525 /* Insert directory pages, if needed. */
526 pdir_lookup(index
, &pi
);
528 for (idx
= pidx
, spi
= pi
; idx
<= lidx
; idx
++) {
529 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != idx
) {
530 if ((pd
= MMAP(malloc_pagesize
)) == MAP_FAILED
) {
531 errno
= ENOMEM
; /* XXX */
532 munmap(result
, tail
- result
);
533 #ifdef MALLOC_EXTRA_SANITY
534 wrtwarning("(ES): map_pages fails");
535 #endif /* MALLOC_EXTRA_SANITY */
538 memset(pd
, 0, malloc_pagesize
);
539 pi
= (struct pdinfo
*) ((caddr_t
) pd
+ pdi_off
);
542 pi
->next
= spi
->next
;
543 pi
->dirnum
= idx
* (malloc_pagesize
/ sizeof(struct pginfo
*));
545 if (spi
->next
!= NULL
)
546 spi
->next
->prev
= pi
;
549 if (idx
> pidx
&& idx
< lidx
) {
550 pi
->dirnum
+= pdi_mod
;
551 } else if (idx
== pidx
) {
553 pi
->dirnum
+= (tail
- result
) >> malloc_pageshift
;
555 pi
->dirnum
+= pdi_mod
- PI_OFF(index
);
558 pi
->dirnum
+= PI_OFF(ptr2index(tail
- 1)) + 1;
560 #ifdef MALLOC_EXTRA_SANITY
561 if (PD_OFF(pi
->dirnum
) > pdi_mod
|| PD_IDX(pi
->dirnum
) > idx
) {
562 wrterror("(ES): pages directory overflow");
566 #endif /* MALLOC_EXTRA_SANITY */
567 if (idx
== pidx
&& pi
!= last_dir
) {
579 * Initialize the world
585 int i
, j
, save_errno
= errno
;
589 #ifdef MALLOC_EXTRA_SANITY
591 #endif /* MALLOC_EXTRA_SANITY */
593 for (i
= 0; i
< 3; i
++) {
596 j
= readlink("/etc/malloc.conf", b
, sizeof b
- 1);
603 if (issetugid() == 0)
604 p
= getenv("MALLOC_OPTIONS");
615 for (; p
!= NULL
&& *p
!= '\0'; p
++) {
617 case '>': malloc_cache
<<= 1; break;
618 case '<': malloc_cache
>>= 1; break;
619 case 'a': malloc_abort
= 0; break;
620 case 'A': malloc_abort
= 1; break;
622 case 'd': malloc_stats
= 0; break;
623 case 'D': malloc_stats
= 1; break;
624 #endif /* MALLOC_STATS */
625 case 'f': malloc_freeprot
= 0; break;
626 case 'F': malloc_freeprot
= 1; break;
627 case 'g': malloc_guard
= 0; break;
628 case 'G': malloc_guard
= malloc_pagesize
; break;
629 case 'h': malloc_hint
= 0; break;
630 case 'H': malloc_hint
= 1; break;
631 case 'j': malloc_junk
= 0; break;
632 case 'J': malloc_junk
= 1; break;
633 case 'n': malloc_silent
= 0; break;
634 case 'N': malloc_silent
= 1; break;
635 case 'p': malloc_ptrguard
= 0; break;
636 case 'P': malloc_ptrguard
= 1; break;
637 case 'r': malloc_realloc
= 0; break;
638 case 'R': malloc_realloc
= 1; break;
639 case 'u': malloc_utrace
= 0; break;
640 case 'U': malloc_utrace
= 1; break;
641 case 'v': malloc_sysv
= 0; break;
642 case 'V': malloc_sysv
= 1; break;
643 case 'x': malloc_xmalloc
= 0; break;
644 case 'X': malloc_xmalloc
= 1; break;
645 case 'z': malloc_zero
= 0; break;
646 case 'Z': malloc_zero
= 1; break;
650 wrtwarning("unknown char in MALLOC_OPTIONS");
660 * We want junk in the entire allocation, and zero only in the part
661 * the user asked for.
667 if (malloc_stats
&& (atexit(malloc_exit
) == -1))
668 wrtwarning("atexit(2) failed."
669 " Will not be able to dump malloc stats on exit");
670 #endif /* MALLOC_STATS */
672 /* Allocate one page for the page directory. */
673 page_dir
= (struct pginfo
**)MMAP(malloc_pagesize
);
675 if (page_dir
== MAP_FAILED
) {
676 wrterror("mmap(2) failed, check limits");
680 pdi_off
= (malloc_pagesize
- sizeof(struct pdinfo
)) & ~(malloc_minsize
- 1);
681 pdi_mod
= pdi_off
/ sizeof(struct pginfo
*);
683 last_dir
= (struct pdinfo
*) ((caddr_t
) page_dir
+ pdi_off
);
684 last_dir
->base
= page_dir
;
685 last_dir
->prev
= last_dir
->next
= NULL
;
686 last_dir
->dirnum
= malloc_pageshift
;
688 /* Been here, done that. */
691 /* Recalculate the cache size in bytes, and make sure it's nonzero. */
694 malloc_cache
<<= malloc_pageshift
;
699 * Allocate a number of complete pages
702 malloc_pages(size_t size
)
704 void *p
, *delay_free
= NULL
, *tp
;
711 size
= pageround(size
) + malloc_guard
;
714 /* Look for free pages before asking for more */
715 for (pf
= free_list
.next
; pf
; pf
= pf
->next
) {
717 #ifdef MALLOC_EXTRA_SANITY
718 if (pf
->size
& malloc_pagemask
) {
719 wrterror("(ES): junk length entry on free_list");
724 wrterror("(ES): zero length entry on free_list");
728 if (pf
->page
> (pf
->page
+ pf
->size
)) {
729 wrterror("(ES): sick entry on free_list");
733 if ((pi
= pf
->pdir
) == NULL
) {
734 wrterror("(ES): invalid page directory on free-list");
738 if ((pidx
= PI_IDX(ptr2index(pf
->page
))) != PD_IDX(pi
->dirnum
)) {
739 wrterror("(ES): directory index mismatch on free-list");
744 if (pd
[PI_OFF(ptr2index(pf
->page
))] != MALLOC_FREE
) {
745 wrterror("(ES): non-free first page on free-list");
749 pidx
= PI_IDX(ptr2index((pf
->page
) + (pf
->size
)) - 1);
750 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
753 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
754 wrterror("(ES): last page not referenced in page directory");
759 if (pd
[PI_OFF(ptr2index((pf
->page
) + (pf
->size
)) - 1)] != MALLOC_FREE
) {
760 wrterror("(ES): non-free last page on free-list");
764 #endif /* MALLOC_EXTRA_SANITY */
769 if (pf
->size
== size
) {
772 if (pf
->next
!= NULL
)
773 pf
->next
->prev
= pf
->prev
;
774 pf
->prev
->next
= pf
->next
;
779 pf
->page
= (char *) pf
->page
+ size
;
781 pidx
= PI_IDX(ptr2index(pf
->page
));
782 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
785 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
786 wrterror("(ES): hole in directories");
796 size
-= malloc_guard
;
798 #ifdef MALLOC_EXTRA_SANITY
799 if (p
!= NULL
&& pi
!= NULL
) {
800 pidx
= PD_IDX(pi
->dirnum
);
803 if (p
!= NULL
&& pd
[PI_OFF(ptr2index(p
))] != MALLOC_FREE
) {
804 wrterror("(ES): allocated non-free page on free-list");
808 #endif /* MALLOC_EXTRA_SANITY */
810 if (p
!= NULL
&& (malloc_guard
|| malloc_freeprot
))
811 mprotect(p
, size
, PROT_READ
| PROT_WRITE
);
813 size
>>= malloc_pageshift
;
820 index
= ptr2index(p
);
821 pidx
= PI_IDX(index
);
822 pdir_lookup(index
, &pi
);
823 #ifdef MALLOC_EXTRA_SANITY
824 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
825 wrterror("(ES): mapped pages not found in directory");
829 #endif /* MALLOC_EXTRA_SANITY */
830 if (pi
!= last_dir
) {
835 pd
[PI_OFF(index
)] = MALLOC_FIRST
;
836 for (i
= 1; i
< size
; i
++) {
837 if (!PI_OFF(index
+ i
)) {
840 #ifdef MALLOC_EXTRA_SANITY
841 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
842 wrterror("(ES): hole in mapped pages directory");
846 #endif /* MALLOC_EXTRA_SANITY */
849 pd
[PI_OFF(index
+ i
)] = MALLOC_FOLLOW
;
852 if (!PI_OFF(index
+ i
)) {
855 #ifdef MALLOC_EXTRA_SANITY
856 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
857 wrterror("(ES): hole in mapped pages directory");
861 #endif /* MALLOC_EXTRA_SANITY */
864 pd
[PI_OFF(index
+ i
)] = MALLOC_FIRST
;
866 malloc_used
+= size
<< malloc_pageshift
;
867 malloc_guarded
+= malloc_guard
;
870 memset(p
, SOME_JUNK
, size
<< malloc_pageshift
);
882 * Allocate a page of fragments
885 static __inline__
int
886 malloc_make_chunks(int bits
)
888 struct pginfo
*bp
, **pd
;
894 /* Allocate a new bucket */
895 pp
= malloc_pages((size_t) malloc_pagesize
);
899 /* Find length of admin structure */
900 l
= sizeof *bp
- sizeof(u_long
);
901 l
+= sizeof(u_long
) *
902 (((malloc_pagesize
>> bits
) + MALLOC_BITS
- 1) / MALLOC_BITS
);
904 /* Don't waste more than two chunks on this */
907 * If we are to allocate a memory protected page for the malloc(0)
908 * case (when bits=0), it must be from a different page than the
910 * --> Treat it like the big chunk alloc, get a second data page.
912 if (bits
!= 0 && (1UL << (bits
)) <= l
+ l
) {
913 bp
= (struct pginfo
*) pp
;
915 bp
= (struct pginfo
*) imalloc(l
);
921 /* memory protect the page allocated in the malloc(0) case */
925 i
= malloc_minsize
- 1;
928 bp
->total
= bp
->free
= malloc_pagesize
>> bp
->shift
;
931 k
= mprotect(pp
, malloc_pagesize
, PROT_NONE
);
938 bp
->size
= (1UL << bits
);
940 bp
->total
= bp
->free
= malloc_pagesize
>> bits
;
943 /* set all valid bits in the bitmap */
947 /* Do a bunch at a time */
948 for (; k
- i
>= MALLOC_BITS
; i
+= MALLOC_BITS
)
949 bp
->bits
[i
/ MALLOC_BITS
] = ~0UL;
952 bp
->bits
[i
/ MALLOC_BITS
] |= 1UL << (i
% MALLOC_BITS
);
954 if (bp
== bp
->page
) {
955 /* Mark the ones we stole for ourselves */
956 for (i
= 0; l
> 0; i
++) {
957 bp
->bits
[i
/ MALLOC_BITS
] &= ~(1UL << (i
% MALLOC_BITS
));
965 pidx
= PI_IDX(ptr2index(pp
));
966 pdir_lookup(ptr2index(pp
), &pi
);
967 #ifdef MALLOC_EXTRA_SANITY
968 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
969 wrterror("(ES): mapped pages not found in directory");
973 #endif /* MALLOC_EXTRA_SANITY */
974 if (pi
!= last_dir
) {
979 pd
[PI_OFF(ptr2index(pp
))] = bp
;
981 bp
->next
= page_dir
[bits
];
989 * Allocate a fragment
992 malloc_bytes(size_t size
)
998 /* Don't bother with anything less than this */
999 /* unless we have a malloc(0) requests */
1000 if (size
!= 0 && size
< malloc_minsize
)
1001 size
= malloc_minsize
;
1003 /* Find the right bucket */
1013 /* If it's empty, make a page more of that size chunks */
1014 if (page_dir
[j
] == NULL
&& !malloc_make_chunks(j
))
1019 /* Find first word of bitmap which isn't empty */
1020 for (lp
= bp
->bits
; !*lp
; lp
++);
1022 /* Find that bit, and tweak it */
1025 while (!(*lp
& u
)) {
1031 /* Walk to a random position. */
1032 i
= arc4random() % bp
->free
;
1036 if (k
>= MALLOC_BITS
) {
1041 #ifdef MALLOC_EXTRA_SANITY
1042 if (lp
- bp
->bits
> (bp
->total
- 1) / MALLOC_BITS
) {
1043 wrterror("chunk overflow");
1047 #endif /* MALLOC_EXTRA_SANITY */
1054 /* If there are no more free, remove from free-list */
1056 page_dir
[j
] = bp
->next
;
1059 /* Adjust to the real offset of that chunk */
1060 k
+= (lp
- bp
->bits
) * MALLOC_BITS
;
1063 if (malloc_junk
&& bp
->size
!= 0)
1064 memset((char *) bp
->page
+ k
, SOME_JUNK
, bp
->size
);
1066 return ((u_char
*) bp
->page
+ k
);
1070 * Magic so that malloc(sizeof(ptr)) is near the end of the page.
1072 #define PTR_GAP (malloc_pagesize - sizeof(void *))
1073 #define PTR_SIZE (sizeof(void *))
1074 #define PTR_ALIGNED(p) (((unsigned long)p & malloc_pagemask) == PTR_GAP)
1077 * Allocate a piece of memory
1080 imalloc(size_t size
)
1085 if (!malloc_started
)
1091 if (malloc_ptrguard
&& size
== PTR_SIZE
) {
1093 size
= malloc_pagesize
;
1095 if ((size
+ malloc_pagesize
) < size
) { /* Check for overflow */
1098 } else if (size
<= malloc_maxsize
)
1099 result
= malloc_bytes(size
);
1101 result
= malloc_pages(size
);
1103 if (malloc_abort
== 1 && result
== NULL
)
1104 wrterror("allocation failed");
1106 if (malloc_zero
&& result
!= NULL
)
1107 memset(result
, 0, size
);
1109 if (result
&& ptralloc
)
1110 return ((char *) result
+ PTR_GAP
);
1115 * Change the size of an allocation.
1118 irealloc(void *ptr
, size_t size
)
1121 u_long osize
, index
, i
;
1130 if (!malloc_started
) {
1131 wrtwarning("malloc() has never been called");
1134 if (malloc_ptrguard
&& PTR_ALIGNED(ptr
)) {
1135 if (size
<= PTR_SIZE
)
1140 memcpy(p
, ptr
, PTR_SIZE
);
1144 index
= ptr2index(ptr
);
1146 if (index
< malloc_pageshift
) {
1147 wrtwarning("junk pointer, too low to make sense");
1151 if (index
> last_index
) {
1152 wrtwarning("junk pointer, too high to make sense");
1156 pidx
= PI_IDX(index
);
1157 pdir_lookup(index
, &pi
);
1159 #ifdef MALLOC_EXTRA_SANITY
1160 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1161 wrterror("(ES): mapped pages not found in directory");
1165 #endif /* MALLOC_EXTRA_SANITY */
1167 if (pi
!= last_dir
) {
1168 prev_dir
= last_dir
;
1172 mp
= &pd
[PI_OFF(index
)];
1174 if (*mp
== MALLOC_FIRST
) { /* Page allocation */
1176 /* Check the pointer */
1177 if ((u_long
) ptr
& malloc_pagemask
) {
1178 wrtwarning("modified (page-) pointer");
1181 /* Find the size in bytes */
1185 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1190 for (osize
= malloc_pagesize
;pi
!= NULL
&& pd
[PI_OFF(i
)] == MALLOC_FOLLOW
;) {
1191 osize
+= malloc_pagesize
;
1194 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1201 if (!malloc_realloc
&& size
<= osize
&&
1202 size
> osize
- malloc_pagesize
) {
1205 memset((char *)ptr
+ size
, SOME_JUNK
, osize
- size
);
1206 return (ptr
); /* ..don't do anything else. */
1208 } else if (*mp
>= MALLOC_MAGIC
) { /* Chunk allocation */
1210 /* Check the pointer for sane values */
1211 if ((u_long
) ptr
& ((1UL << ((*mp
)->shift
)) - 1)) {
1212 wrtwarning("modified (chunk-) pointer");
1215 /* Find the chunk index in the page */
1216 i
= ((u_long
) ptr
& malloc_pagemask
) >> (*mp
)->shift
;
1218 /* Verify that it isn't a free chunk already */
1219 if ((*mp
)->bits
[i
/ MALLOC_BITS
] & (1UL << (i
% MALLOC_BITS
))) {
1220 wrtwarning("chunk is already free");
1223 osize
= (*mp
)->size
;
1225 if (!malloc_realloc
&& size
<= osize
&&
1226 (size
> osize
/ 2 || osize
== malloc_minsize
)) {
1228 memset((char *) ptr
+ size
, SOME_JUNK
, osize
- size
);
1229 return (ptr
); /* ..don't do anything else. */
1232 wrtwarning("irealloc: pointer to wrong page");
1239 /* copy the lesser of the two sizes, and free the old one */
1240 /* Don't move from/to 0 sized region !!! */
1241 if (osize
!= 0 && size
!= 0) {
1243 memcpy(p
, ptr
, osize
);
1245 memcpy(p
, ptr
, size
);
1253 * Free a sequence of pages
1255 static __inline__
void
1256 free_pages(void *ptr
, u_long index
, struct pginfo
* info
)
1258 u_long i
, l
, cachesize
= 0, pidx
, lidx
;
1260 struct pdinfo
*pi
, *spi
;
1261 struct pgfree
*pf
, *pt
= NULL
;
1264 if (info
== MALLOC_FREE
) {
1265 wrtwarning("page is already free");
1268 if (info
!= MALLOC_FIRST
) {
1269 wrtwarning("free_pages: pointer to wrong page");
1272 if ((u_long
) ptr
& malloc_pagemask
) {
1273 wrtwarning("modified (page-) pointer");
1276 /* Count how many pages and mark them free at the same time */
1277 pidx
= PI_IDX(index
);
1278 pdir_lookup(index
, &pi
);
1280 #ifdef MALLOC_EXTRA_SANITY
1281 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1282 wrterror("(ES): mapped pages not found in directory");
1286 #endif /* MALLOC_EXTRA_SANITY */
1288 spi
= pi
; /* Save page index for start of region. */
1291 pd
[PI_OFF(index
)] = MALLOC_FREE
;
1293 if (!PI_OFF(index
+ i
)) {
1295 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
))
1300 while (pi
!= NULL
&& pd
[PI_OFF(index
+ i
)] == MALLOC_FOLLOW
) {
1301 pd
[PI_OFF(index
+ i
)] = MALLOC_FREE
;
1303 if (!PI_OFF(index
+ i
)) {
1304 if ((pi
= pi
->next
) == NULL
||
1305 PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
))
1312 l
= i
<< malloc_pageshift
;
1315 memset(ptr
, SOME_JUNK
, l
);
1318 malloc_guarded
-= malloc_guard
;
1321 #ifdef MALLOC_EXTRA_SANITY
1322 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
)) {
1323 wrterror("(ES): hole in mapped pages directory");
1327 #endif /* MALLOC_EXTRA_SANITY */
1329 pd
[PI_OFF(index
+ i
)] = MALLOC_FREE
;
1332 tail
= (char *) ptr
+ l
;
1335 madvise(ptr
, l
, MADV_FREE
);
1337 if (malloc_freeprot
)
1338 mprotect(ptr
, l
, PROT_NONE
);
1340 /* Add to free-list. */
1342 px
= imalloc(sizeof *px
); /* This cannot fail... */
1347 if (free_list
.next
== NULL
) {
1348 /* Nothing on free list, put this at head. */
1350 px
->prev
= &free_list
;
1351 free_list
.next
= px
;
1356 * Find the right spot, leave pf pointing to the modified
1360 /* Race ahead here, while calculating cache size. */
1361 for (pf
= free_list
.next
;
1362 pf
->page
+ pf
->size
< ptr
&& pf
->next
!= NULL
;
1364 cachesize
+= pf
->size
;
1366 /* Finish cache size calculation. */
1369 cachesize
+= pt
->size
;
1373 if (pf
->page
> tail
) {
1374 /* Insert before entry */
1376 px
->prev
= pf
->prev
;
1378 px
->prev
->next
= px
;
1381 } else if ((pf
->page
+ pf
->size
) == ptr
) {
1382 /* Append to the previous entry. */
1383 cachesize
-= pf
->size
;
1385 if (pf
->next
!= NULL
&&
1386 pf
->page
+ pf
->size
== pf
->next
->page
) {
1387 /* And collapse the next too. */
1389 pf
->size
+= pt
->size
;
1390 pf
->next
= pt
->next
;
1391 if (pf
->next
!= NULL
)
1392 pf
->next
->prev
= pf
;
1394 } else if (pf
->page
== tail
) {
1395 /* Prepend to entry. */
1396 cachesize
-= pf
->size
;
1400 } else if (pf
->next
== NULL
) {
1401 /* Append at tail of chain. */
1408 wrterror("freelist is destroyed");
1414 if (pf
->pdir
!= last_dir
) {
1415 prev_dir
= last_dir
;
1416 last_dir
= pf
->pdir
;
1419 /* Return something to OS ? */
1420 if (pf
->size
> (malloc_cache
- cachesize
)) {
1423 * Keep the cache intact. Notice that the '>' above guarantees that
1424 * the pf will always have at least one page afterwards.
1426 if (munmap((char *) pf
->page
+ (malloc_cache
- cachesize
),
1427 pf
->size
- (malloc_cache
- cachesize
)) != 0)
1429 tail
= pf
->page
+ pf
->size
;
1430 lidx
= ptr2index(tail
) - 1;
1431 pf
->size
= malloc_cache
- cachesize
;
1433 index
= ptr2index(pf
->page
+ pf
->size
);
1435 pidx
= PI_IDX(index
);
1436 if (prev_dir
!= NULL
&& PD_IDX(prev_dir
->dirnum
) >= pidx
)
1437 prev_dir
= NULL
; /* Will be wiped out below ! */
1439 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
1444 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) == pidx
) {
1447 for (i
= index
; i
<= lidx
;) {
1448 if (pd
[PI_OFF(i
)] != MALLOC_NOT_MINE
) {
1449 pd
[PI_OFF(i
)] = MALLOC_NOT_MINE
;
1451 #ifdef MALLOC_EXTRA_SANITY
1452 if (!PD_OFF(pi
->dirnum
)) {
1453 wrterror("(ES): pages directory underflow");
1457 #endif /* MALLOC_EXTRA_SANITY */
1460 #ifdef MALLOC_EXTRA_SANITY
1462 wrtwarning("(ES): page already unmapped");
1463 #endif /* MALLOC_EXTRA_SANITY */
1467 * If no page in that dir, free
1470 if (!PD_OFF(pi
->dirnum
)) {
1471 /* Remove from list. */
1474 if (pi
->prev
!= NULL
)
1475 pi
->prev
->next
= pi
->next
;
1476 if (pi
->next
!= NULL
)
1477 pi
->next
->prev
= pi
->prev
;
1479 munmap(pd
, malloc_pagesize
);
1482 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1487 if (pi
&& !PD_OFF(pi
->dirnum
)) {
1488 /* Resulting page dir is now empty. */
1489 /* Remove from list. */
1490 if (spi
== pi
) /* Update spi only if first. */
1492 if (pi
->prev
!= NULL
)
1493 pi
->prev
->next
= pi
->next
;
1494 if (pi
->next
!= NULL
)
1495 pi
->next
->prev
= pi
->prev
;
1497 munmap(pd
, malloc_pagesize
);
1500 if (pi
== NULL
&& malloc_brk
== tail
) {
1501 /* Resize down the malloc upper boundary. */
1502 last_index
= index
- 1;
1503 malloc_brk
= index2ptr(index
);
1506 /* XXX: We could realloc/shrink the pagedir here I guess. */
1507 if (pf
->size
== 0) { /* Remove from free-list as well. */
1510 if ((px
= pf
->prev
) != &free_list
) {
1511 if (pi
== NULL
&& last_index
== (index
- 1)) {
1517 if (PD_IDX(spi
->dirnum
) < pidx
)
1518 index
= ((PD_IDX(spi
->dirnum
) + 1) * pdi_mod
) - 1;
1519 for (pi
= spi
, i
= index
;pd
[PI_OFF(i
)] == MALLOC_NOT_MINE
;i
--)
1520 #ifdef MALLOC_EXTRA_SANITY
1523 if (pi
== NULL
|| i
== 0)
1526 i
= (PD_IDX(pi
->dirnum
) + 1) * pdi_mod
;
1528 #else /* !MALLOC_EXTRA_SANITY */
1531 #endif /* MALLOC_EXTRA_SANITY */
1532 malloc_brk
= index2ptr(i
+ 1);
1536 if ((px
->next
= pf
->next
) != NULL
)
1537 px
->next
->prev
= px
;
1539 if ((free_list
.next
= pf
->next
) != NULL
)
1540 free_list
.next
->prev
= &free_list
;
1543 last_dir
= prev_dir
;
1553 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1557 static __inline__
void
1558 free_bytes(void *ptr
, int index
, struct pginfo
* info
)
1560 struct pginfo
**mp
, **pd
;
1566 /* Find the chunk number on the page */
1567 i
= ((u_long
) ptr
& malloc_pagemask
) >> info
->shift
;
1569 if ((u_long
) ptr
& ((1UL << (info
->shift
)) - 1)) {
1570 wrtwarning("modified (chunk-) pointer");
1573 if (info
->bits
[i
/ MALLOC_BITS
] & (1UL << (i
% MALLOC_BITS
))) {
1574 wrtwarning("chunk is already free");
1577 if (malloc_junk
&& info
->size
!= 0)
1578 memset(ptr
, SOME_JUNK
, info
->size
);
1580 info
->bits
[i
/ MALLOC_BITS
] |= 1UL << (i
% MALLOC_BITS
);
1583 if (info
->size
!= 0)
1584 mp
= page_dir
+ info
->shift
;
1588 if (info
->free
== 1) {
1589 /* Page became non-full */
1591 /* Insert in address order */
1592 while (*mp
!= NULL
&& (*mp
)->next
!= NULL
&&
1593 (*mp
)->next
->page
< info
->page
)
1599 if (info
->free
!= info
->total
)
1602 /* Find & remove this page in the queue */
1603 while (*mp
!= info
) {
1604 mp
= &((*mp
)->next
);
1605 #ifdef MALLOC_EXTRA_SANITY
1607 wrterror("(ES): Not on queue");
1611 #endif /* MALLOC_EXTRA_SANITY */
1615 /* Free the page & the info structure if need be */
1616 pidx
= PI_IDX(ptr2index(info
->page
));
1617 pdir_lookup(ptr2index(info
->page
), &pi
);
1618 #ifdef MALLOC_EXTRA_SANITY
1619 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1620 wrterror("(ES): mapped pages not found in directory");
1624 #endif /* MALLOC_EXTRA_SANITY */
1625 if (pi
!= last_dir
) {
1626 prev_dir
= last_dir
;
1630 pd
[PI_OFF(ptr2index(info
->page
))] = MALLOC_FIRST
;
1632 /* If the page was mprotected, unprotect it before releasing it */
1633 if (info
->size
== 0)
1634 mprotect(info
->page
, malloc_pagesize
, PROT_READ
| PROT_WRITE
);
1636 vp
= info
->page
; /* Order is important ! */
1637 if (vp
!= (void *) info
)
1645 struct pginfo
*info
, **pd
;
1653 if (!malloc_started
) {
1654 wrtwarning("malloc() has never been called");
1657 /* If we're already sinking, don't make matters any worse. */
1661 if (malloc_ptrguard
&& PTR_ALIGNED(ptr
))
1662 ptr
= (char *) ptr
- PTR_GAP
;
1664 index
= ptr2index(ptr
);
1666 if (index
< malloc_pageshift
) {
1668 wrtwarning("ifree: junk pointer, too low to make sense");
1671 if (index
> last_index
) {
1673 wrtwarning("ifree: junk pointer, too high to make sense");
1676 pidx
= PI_IDX(index
);
1677 pdir_lookup(index
, &pi
);
1678 #ifdef MALLOC_EXTRA_SANITY
1679 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1680 wrterror("(ES): mapped pages not found in directory");
1684 #endif /* MALLOC_EXTRA_SANITY */
1685 if (pi
!= last_dir
) {
1686 prev_dir
= last_dir
;
1690 info
= pd
[PI_OFF(index
)];
1692 if (info
< MALLOC_MAGIC
)
1693 free_pages(ptr
, index
, info
);
1695 free_bytes(ptr
, index
, info
);
1700 * Common function for handling recursion. Only
1701 * print the error message once, to avoid making the problem
1702 * potentially worse.
1705 malloc_recurse(void)
1711 wrtwarning("recursive call");
1719 * These are the public exported interface routines.
1727 malloc_func
= " in malloc():";
1728 if (malloc_active
++) {
1732 if (malloc_sysv
&& !size
)
1739 if (malloc_xmalloc
&& r
== NULL
) {
1740 wrterror("out of memory");
1750 malloc_func
= " in free():";
1751 if (malloc_active
++) {
1763 realloc(void *ptr
, size_t size
)
1768 malloc_func
= " in realloc():";
1769 if (malloc_active
++) {
1774 if (malloc_sysv
&& !size
) {
1777 } else if (ptr
== NULL
)
1780 r
= irealloc(ptr
, size
);
1782 UTRACE(ptr
, size
, r
);
1785 if (malloc_xmalloc
&& r
== NULL
) {
1786 wrterror("out of memory");