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 */
453 const char *progname
= getprogname();
454 const char *q
= " error: ";
456 _write(STDERR_FILENO
, progname
, strlen(progname
));
457 _write(STDERR_FILENO
, malloc_func
, strlen(malloc_func
));
458 _write(STDERR_FILENO
, q
, strlen(q
));
459 _write(STDERR_FILENO
, p
, strlen(p
));
464 malloc_dump(STDERR_FILENO
);
465 #endif /* MALLOC_STATS */
474 const char *progname
= getprogname();
475 const char *q
= " warning: ";
479 _write(STDERR_FILENO
, progname
, strlen(progname
));
480 _write(STDERR_FILENO
, malloc_func
, strlen(malloc_func
));
481 _write(STDERR_FILENO
, q
, strlen(q
));
482 _write(STDERR_FILENO
, p
, strlen(p
));
489 char *q
= "malloc() warning: Couldn't dump stats\n";
490 int save_errno
= errno
, fd
;
492 fd
= open("malloc.out", O_RDWR
|O_APPEND
);
497 _write(STDERR_FILENO
, q
, strlen(q
));
501 #endif /* MALLOC_STATS */
504 * Allocate a number of pages from the OS
507 map_pages(size_t pages
)
509 struct pdinfo
*pi
, *spi
;
511 u_long idx
, pidx
, lidx
;
513 u_long index
, lindex
;
515 pages
<<= malloc_pageshift
;
516 result
= MMAP(pages
+ malloc_guard
);
517 if (result
== MAP_FAILED
) {
519 #ifdef MALLOC_EXTRA_SANITY
520 wrtwarning("(ES): map_pages fails");
521 #endif /* MALLOC_EXTRA_SANITY */
524 index
= ptr2index(result
);
525 tail
= result
+ pages
+ malloc_guard
;
526 lindex
= ptr2index(tail
) - 1;
528 mprotect(result
+ pages
, malloc_guard
, PROT_NONE
);
530 pidx
= PI_IDX(index
);
531 lidx
= PI_IDX(lindex
);
533 if (tail
> malloc_brk
) {
537 /* Insert directory pages, if needed. */
538 pdir_lookup(index
, &pi
);
540 for (idx
= pidx
, spi
= pi
; idx
<= lidx
; idx
++) {
541 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != idx
) {
542 if ((pd
= MMAP(malloc_pagesize
)) == MAP_FAILED
) {
543 errno
= ENOMEM
; /* XXX */
544 munmap(result
, tail
- result
);
545 #ifdef MALLOC_EXTRA_SANITY
546 wrtwarning("(ES): map_pages fails");
547 #endif /* MALLOC_EXTRA_SANITY */
550 memset(pd
, 0, malloc_pagesize
);
551 pi
= (struct pdinfo
*) ((caddr_t
) pd
+ pdi_off
);
554 pi
->next
= spi
->next
;
555 pi
->dirnum
= idx
* (malloc_pagesize
/ sizeof(struct pginfo
*));
557 if (spi
->next
!= NULL
)
558 spi
->next
->prev
= pi
;
561 if (idx
> pidx
&& idx
< lidx
) {
562 pi
->dirnum
+= pdi_mod
;
563 } else if (idx
== pidx
) {
565 pi
->dirnum
+= (tail
- result
) >> malloc_pageshift
;
567 pi
->dirnum
+= pdi_mod
- PI_OFF(index
);
570 pi
->dirnum
+= PI_OFF(ptr2index(tail
- 1)) + 1;
572 #ifdef MALLOC_EXTRA_SANITY
573 if (PD_OFF(pi
->dirnum
) > pdi_mod
|| PD_IDX(pi
->dirnum
) > idx
) {
574 wrterror("(ES): pages directory overflow");
578 #endif /* MALLOC_EXTRA_SANITY */
579 if (idx
== pidx
&& pi
!= last_dir
) {
591 * Initialize the world
597 int i
, j
, save_errno
= errno
;
601 #ifdef MALLOC_EXTRA_SANITY
603 #endif /* MALLOC_EXTRA_SANITY */
605 for (i
= 0; i
< 3; i
++) {
608 j
= readlink("/etc/malloc.conf", b
, sizeof b
- 1);
615 if (issetugid() == 0)
616 p
= getenv("MALLOC_OPTIONS");
627 for (; p
!= NULL
&& *p
!= '\0'; p
++) {
629 case '>': malloc_cache
<<= 1; break;
630 case '<': malloc_cache
>>= 1; break;
631 case 'a': malloc_abort
= 0; break;
632 case 'A': malloc_abort
= 1; break;
634 case 'd': malloc_stats
= 0; break;
635 case 'D': malloc_stats
= 1; break;
636 #endif /* MALLOC_STATS */
637 case 'f': malloc_freeprot
= 0; break;
638 case 'F': malloc_freeprot
= 1; break;
639 case 'g': malloc_guard
= 0; break;
640 case 'G': malloc_guard
= malloc_pagesize
; break;
641 case 'h': malloc_hint
= 0; break;
642 case 'H': malloc_hint
= 1; break;
643 case 'j': malloc_junk
= 0; break;
644 case 'J': malloc_junk
= 1; break;
645 case 'n': malloc_silent
= 0; break;
646 case 'N': malloc_silent
= 1; break;
647 case 'p': malloc_ptrguard
= 0; break;
648 case 'P': malloc_ptrguard
= 1; break;
649 case 'r': malloc_realloc
= 0; break;
650 case 'R': malloc_realloc
= 1; break;
651 case 'u': malloc_utrace
= 0; break;
652 case 'U': malloc_utrace
= 1; break;
653 case 'v': malloc_sysv
= 0; break;
654 case 'V': malloc_sysv
= 1; break;
655 case 'x': malloc_xmalloc
= 0; break;
656 case 'X': malloc_xmalloc
= 1; break;
657 case 'z': malloc_zero
= 0; break;
658 case 'Z': malloc_zero
= 1; break;
662 wrtwarning("unknown char in MALLOC_OPTIONS");
672 * We want junk in the entire allocation, and zero only in the part
673 * the user asked for.
679 if (malloc_stats
&& (atexit(malloc_exit
) == -1))
680 wrtwarning("atexit(2) failed."
681 " Will not be able to dump malloc stats on exit");
682 #endif /* MALLOC_STATS */
684 /* Allocate one page for the page directory. */
685 page_dir
= (struct pginfo
**)MMAP(malloc_pagesize
);
687 if (page_dir
== MAP_FAILED
) {
688 wrterror("mmap(2) failed, check limits");
692 pdi_off
= (malloc_pagesize
- sizeof(struct pdinfo
)) & ~(malloc_minsize
- 1);
693 pdi_mod
= pdi_off
/ sizeof(struct pginfo
*);
695 last_dir
= (struct pdinfo
*) ((caddr_t
) page_dir
+ pdi_off
);
696 last_dir
->base
= page_dir
;
697 last_dir
->prev
= last_dir
->next
= NULL
;
698 last_dir
->dirnum
= malloc_pageshift
;
700 /* Been here, done that. */
703 /* Recalculate the cache size in bytes, and make sure it's nonzero. */
706 malloc_cache
<<= malloc_pageshift
;
711 * Allocate a number of complete pages
714 malloc_pages(size_t size
)
716 void *p
, *delay_free
= NULL
, *tp
;
723 size
= pageround(size
) + malloc_guard
;
726 /* Look for free pages before asking for more */
727 for (pf
= free_list
.next
; pf
; pf
= pf
->next
) {
729 #ifdef MALLOC_EXTRA_SANITY
730 if (pf
->size
& malloc_pagemask
) {
731 wrterror("(ES): junk length entry on free_list");
736 wrterror("(ES): zero length entry on free_list");
740 if (pf
->page
> (pf
->page
+ pf
->size
)) {
741 wrterror("(ES): sick entry on free_list");
745 if ((pi
= pf
->pdir
) == NULL
) {
746 wrterror("(ES): invalid page directory on free-list");
750 if ((pidx
= PI_IDX(ptr2index(pf
->page
))) != PD_IDX(pi
->dirnum
)) {
751 wrterror("(ES): directory index mismatch on free-list");
756 if (pd
[PI_OFF(ptr2index(pf
->page
))] != MALLOC_FREE
) {
757 wrterror("(ES): non-free first page on free-list");
761 pidx
= PI_IDX(ptr2index((pf
->page
) + (pf
->size
)) - 1);
762 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
765 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
766 wrterror("(ES): last page not referenced in page directory");
771 if (pd
[PI_OFF(ptr2index((pf
->page
) + (pf
->size
)) - 1)] != MALLOC_FREE
) {
772 wrterror("(ES): non-free last page on free-list");
776 #endif /* MALLOC_EXTRA_SANITY */
781 if (pf
->size
== size
) {
784 if (pf
->next
!= NULL
)
785 pf
->next
->prev
= pf
->prev
;
786 pf
->prev
->next
= pf
->next
;
791 pf
->page
= (char *) pf
->page
+ size
;
793 pidx
= PI_IDX(ptr2index(pf
->page
));
794 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
797 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
798 wrterror("(ES): hole in directories");
808 size
-= malloc_guard
;
810 #ifdef MALLOC_EXTRA_SANITY
811 if (p
!= NULL
&& pi
!= NULL
) {
812 pidx
= PD_IDX(pi
->dirnum
);
815 if (p
!= NULL
&& pd
[PI_OFF(ptr2index(p
))] != MALLOC_FREE
) {
816 wrterror("(ES): allocated non-free page on free-list");
820 #endif /* MALLOC_EXTRA_SANITY */
822 if (p
!= NULL
&& (malloc_guard
|| malloc_freeprot
))
823 mprotect(p
, size
, PROT_READ
| PROT_WRITE
);
825 size
>>= malloc_pageshift
;
832 index
= ptr2index(p
);
833 pidx
= PI_IDX(index
);
834 pdir_lookup(index
, &pi
);
835 #ifdef MALLOC_EXTRA_SANITY
836 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
837 wrterror("(ES): mapped pages not found in directory");
841 #endif /* MALLOC_EXTRA_SANITY */
842 if (pi
!= last_dir
) {
847 pd
[PI_OFF(index
)] = MALLOC_FIRST
;
848 for (i
= 1; i
< size
; i
++) {
849 if (!PI_OFF(index
+ i
)) {
852 #ifdef MALLOC_EXTRA_SANITY
853 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
854 wrterror("(ES): hole in mapped pages directory");
858 #endif /* MALLOC_EXTRA_SANITY */
861 pd
[PI_OFF(index
+ i
)] = MALLOC_FOLLOW
;
864 if (!PI_OFF(index
+ i
)) {
867 #ifdef MALLOC_EXTRA_SANITY
868 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
869 wrterror("(ES): hole in mapped pages directory");
873 #endif /* MALLOC_EXTRA_SANITY */
876 pd
[PI_OFF(index
+ i
)] = MALLOC_FIRST
;
878 malloc_used
+= size
<< malloc_pageshift
;
879 malloc_guarded
+= malloc_guard
;
882 memset(p
, SOME_JUNK
, size
<< malloc_pageshift
);
894 * Allocate a page of fragments
897 static __inline__
int
898 malloc_make_chunks(int bits
)
900 struct pginfo
*bp
, **pd
;
906 /* Allocate a new bucket */
907 pp
= malloc_pages((size_t) malloc_pagesize
);
911 /* Find length of admin structure */
912 l
= sizeof *bp
- sizeof(u_long
);
913 l
+= sizeof(u_long
) *
914 (((malloc_pagesize
>> bits
) + MALLOC_BITS
- 1) / MALLOC_BITS
);
916 /* Don't waste more than two chunks on this */
919 * If we are to allocate a memory protected page for the malloc(0)
920 * case (when bits=0), it must be from a different page than the
922 * --> Treat it like the big chunk alloc, get a second data page.
924 if (bits
!= 0 && (1UL << (bits
)) <= l
+ l
) {
925 bp
= (struct pginfo
*) pp
;
927 bp
= (struct pginfo
*) imalloc(l
);
933 /* memory protect the page allocated in the malloc(0) case */
937 i
= malloc_minsize
- 1;
940 bp
->total
= bp
->free
= malloc_pagesize
>> bp
->shift
;
943 k
= mprotect(pp
, malloc_pagesize
, PROT_NONE
);
950 bp
->size
= (1UL << bits
);
952 bp
->total
= bp
->free
= malloc_pagesize
>> bits
;
955 /* set all valid bits in the bitmap */
959 /* Do a bunch at a time */
960 for (; k
- i
>= MALLOC_BITS
; i
+= MALLOC_BITS
)
961 bp
->bits
[i
/ MALLOC_BITS
] = ~0UL;
964 bp
->bits
[i
/ MALLOC_BITS
] |= 1UL << (i
% MALLOC_BITS
);
966 if (bp
== bp
->page
) {
967 /* Mark the ones we stole for ourselves */
968 for (i
= 0; l
> 0; i
++) {
969 bp
->bits
[i
/ MALLOC_BITS
] &= ~(1UL << (i
% MALLOC_BITS
));
977 pidx
= PI_IDX(ptr2index(pp
));
978 pdir_lookup(ptr2index(pp
), &pi
);
979 #ifdef MALLOC_EXTRA_SANITY
980 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
981 wrterror("(ES): mapped pages not found in directory");
985 #endif /* MALLOC_EXTRA_SANITY */
986 if (pi
!= last_dir
) {
991 pd
[PI_OFF(ptr2index(pp
))] = bp
;
993 bp
->next
= page_dir
[bits
];
1001 * Allocate a fragment
1004 malloc_bytes(size_t size
)
1010 /* Don't bother with anything less than this */
1011 /* unless we have a malloc(0) requests */
1012 if (size
!= 0 && size
< malloc_minsize
)
1013 size
= malloc_minsize
;
1015 /* Find the right bucket */
1025 /* If it's empty, make a page more of that size chunks */
1026 if (page_dir
[j
] == NULL
&& !malloc_make_chunks(j
))
1031 /* Find first word of bitmap which isn't empty */
1032 for (lp
= bp
->bits
; !*lp
; lp
++);
1034 /* Find that bit, and tweak it */
1037 while (!(*lp
& u
)) {
1043 /* Walk to a random position. */
1044 i
= arc4random() % bp
->free
;
1048 if (k
>= MALLOC_BITS
) {
1053 #ifdef MALLOC_EXTRA_SANITY
1054 if (lp
- bp
->bits
> (bp
->total
- 1) / MALLOC_BITS
) {
1055 wrterror("chunk overflow");
1059 #endif /* MALLOC_EXTRA_SANITY */
1066 /* If there are no more free, remove from free-list */
1068 page_dir
[j
] = bp
->next
;
1071 /* Adjust to the real offset of that chunk */
1072 k
+= (lp
- bp
->bits
) * MALLOC_BITS
;
1075 if (malloc_junk
&& bp
->size
!= 0)
1076 memset((char *) bp
->page
+ k
, SOME_JUNK
, bp
->size
);
1078 return ((u_char
*) bp
->page
+ k
);
1082 * Magic so that malloc(sizeof(ptr)) is near the end of the page.
1084 #define PTR_GAP (malloc_pagesize - sizeof(void *))
1085 #define PTR_SIZE (sizeof(void *))
1086 #define PTR_ALIGNED(p) (((unsigned long)p & malloc_pagemask) == PTR_GAP)
1089 * Allocate a piece of memory
1092 imalloc(size_t size
)
1097 if (!malloc_started
)
1103 if (malloc_ptrguard
&& size
== PTR_SIZE
) {
1105 size
= malloc_pagesize
;
1107 if ((size
+ malloc_pagesize
) < size
) { /* Check for overflow */
1110 } else if (size
<= malloc_maxsize
)
1111 result
= malloc_bytes(size
);
1113 result
= malloc_pages(size
);
1115 if (malloc_abort
== 1 && result
== NULL
)
1116 wrterror("allocation failed");
1118 if (malloc_zero
&& result
!= NULL
)
1119 memset(result
, 0, size
);
1121 if (result
&& ptralloc
)
1122 return ((char *) result
+ PTR_GAP
);
1127 * Change the size of an allocation.
1130 irealloc(void *ptr
, size_t size
)
1133 u_long osize
, index
, i
;
1142 if (!malloc_started
) {
1143 wrtwarning("malloc() has never been called");
1146 if (malloc_ptrguard
&& PTR_ALIGNED(ptr
)) {
1147 if (size
<= PTR_SIZE
)
1152 memcpy(p
, ptr
, PTR_SIZE
);
1156 index
= ptr2index(ptr
);
1158 if (index
< malloc_pageshift
) {
1159 wrtwarning("junk pointer, too low to make sense");
1163 if (index
> last_index
) {
1164 wrtwarning("junk pointer, too high to make sense");
1168 pidx
= PI_IDX(index
);
1169 pdir_lookup(index
, &pi
);
1171 #ifdef MALLOC_EXTRA_SANITY
1172 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1173 wrterror("(ES): mapped pages not found in directory");
1177 #endif /* MALLOC_EXTRA_SANITY */
1179 if (pi
!= last_dir
) {
1180 prev_dir
= last_dir
;
1184 mp
= &pd
[PI_OFF(index
)];
1186 if (*mp
== MALLOC_FIRST
) { /* Page allocation */
1188 /* Check the pointer */
1189 if ((u_long
) ptr
& malloc_pagemask
) {
1190 wrtwarning("modified (page-) pointer");
1193 /* Find the size in bytes */
1197 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1202 for (osize
= malloc_pagesize
;pi
!= NULL
&& pd
[PI_OFF(i
)] == MALLOC_FOLLOW
;) {
1203 osize
+= malloc_pagesize
;
1206 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1213 if (!malloc_realloc
&& size
<= osize
&&
1214 size
> osize
- malloc_pagesize
) {
1217 memset((char *)ptr
+ size
, SOME_JUNK
, osize
- size
);
1218 return (ptr
); /* ..don't do anything else. */
1220 } else if (*mp
>= MALLOC_MAGIC
) { /* Chunk allocation */
1222 /* Check the pointer for sane values */
1223 if ((u_long
) ptr
& ((1UL << ((*mp
)->shift
)) - 1)) {
1224 wrtwarning("modified (chunk-) pointer");
1227 /* Find the chunk index in the page */
1228 i
= ((u_long
) ptr
& malloc_pagemask
) >> (*mp
)->shift
;
1230 /* Verify that it isn't a free chunk already */
1231 if ((*mp
)->bits
[i
/ MALLOC_BITS
] & (1UL << (i
% MALLOC_BITS
))) {
1232 wrtwarning("chunk is already free");
1235 osize
= (*mp
)->size
;
1237 if (!malloc_realloc
&& size
<= osize
&&
1238 (size
> osize
/ 2 || osize
== malloc_minsize
)) {
1240 memset((char *) ptr
+ size
, SOME_JUNK
, osize
- size
);
1241 return (ptr
); /* ..don't do anything else. */
1244 wrtwarning("irealloc: pointer to wrong page");
1251 /* copy the lesser of the two sizes, and free the old one */
1252 /* Don't move from/to 0 sized region !!! */
1253 if (osize
!= 0 && size
!= 0) {
1255 memcpy(p
, ptr
, osize
);
1257 memcpy(p
, ptr
, size
);
1265 * Free a sequence of pages
1267 static __inline__
void
1268 free_pages(void *ptr
, u_long index
, struct pginfo
* info
)
1270 u_long i
, l
, cachesize
= 0, pidx
, lidx
;
1272 struct pdinfo
*pi
, *spi
;
1273 struct pgfree
*pf
, *pt
= NULL
;
1276 if (info
== MALLOC_FREE
) {
1277 wrtwarning("page is already free");
1280 if (info
!= MALLOC_FIRST
) {
1281 wrtwarning("free_pages: pointer to wrong page");
1284 if ((u_long
) ptr
& malloc_pagemask
) {
1285 wrtwarning("modified (page-) pointer");
1288 /* Count how many pages and mark them free at the same time */
1289 pidx
= PI_IDX(index
);
1290 pdir_lookup(index
, &pi
);
1292 #ifdef MALLOC_EXTRA_SANITY
1293 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1294 wrterror("(ES): mapped pages not found in directory");
1298 #endif /* MALLOC_EXTRA_SANITY */
1300 spi
= pi
; /* Save page index for start of region. */
1303 pd
[PI_OFF(index
)] = MALLOC_FREE
;
1305 if (!PI_OFF(index
+ i
)) {
1307 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
))
1312 while (pi
!= NULL
&& pd
[PI_OFF(index
+ i
)] == MALLOC_FOLLOW
) {
1313 pd
[PI_OFF(index
+ i
)] = MALLOC_FREE
;
1315 if (!PI_OFF(index
+ i
)) {
1316 if ((pi
= pi
->next
) == NULL
||
1317 PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
))
1324 l
= i
<< malloc_pageshift
;
1327 memset(ptr
, SOME_JUNK
, l
);
1330 malloc_guarded
-= malloc_guard
;
1333 #ifdef MALLOC_EXTRA_SANITY
1334 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(index
+ i
)) {
1335 wrterror("(ES): hole in mapped pages directory");
1339 #endif /* MALLOC_EXTRA_SANITY */
1341 pd
[PI_OFF(index
+ i
)] = MALLOC_FREE
;
1344 tail
= (char *) ptr
+ l
;
1347 madvise(ptr
, l
, MADV_FREE
);
1349 if (malloc_freeprot
)
1350 mprotect(ptr
, l
, PROT_NONE
);
1352 /* Add to free-list. */
1354 px
= imalloc(sizeof *px
); /* This cannot fail... */
1359 if (free_list
.next
== NULL
) {
1360 /* Nothing on free list, put this at head. */
1362 px
->prev
= &free_list
;
1363 free_list
.next
= px
;
1368 * Find the right spot, leave pf pointing to the modified
1372 /* Race ahead here, while calculating cache size. */
1373 for (pf
= free_list
.next
;
1374 pf
->page
+ pf
->size
< ptr
&& pf
->next
!= NULL
;
1376 cachesize
+= pf
->size
;
1378 /* Finish cache size calculation. */
1381 cachesize
+= pt
->size
;
1385 if (pf
->page
> tail
) {
1386 /* Insert before entry */
1388 px
->prev
= pf
->prev
;
1390 px
->prev
->next
= px
;
1393 } else if ((pf
->page
+ pf
->size
) == ptr
) {
1394 /* Append to the previous entry. */
1395 cachesize
-= pf
->size
;
1397 if (pf
->next
!= NULL
&&
1398 pf
->page
+ pf
->size
== pf
->next
->page
) {
1399 /* And collapse the next too. */
1401 pf
->size
+= pt
->size
;
1402 pf
->next
= pt
->next
;
1403 if (pf
->next
!= NULL
)
1404 pf
->next
->prev
= pf
;
1406 } else if (pf
->page
== tail
) {
1407 /* Prepend to entry. */
1408 cachesize
-= pf
->size
;
1412 } else if (pf
->next
== NULL
) {
1413 /* Append at tail of chain. */
1420 wrterror("freelist is destroyed");
1426 if (pf
->pdir
!= last_dir
) {
1427 prev_dir
= last_dir
;
1428 last_dir
= pf
->pdir
;
1431 /* Return something to OS ? */
1432 if (pf
->size
> (malloc_cache
- cachesize
)) {
1435 * Keep the cache intact. Notice that the '>' above guarantees that
1436 * the pf will always have at least one page afterwards.
1438 if (munmap((char *) pf
->page
+ (malloc_cache
- cachesize
),
1439 pf
->size
- (malloc_cache
- cachesize
)) != 0)
1441 tail
= pf
->page
+ pf
->size
;
1442 lidx
= ptr2index(tail
) - 1;
1443 pf
->size
= malloc_cache
- cachesize
;
1445 index
= ptr2index(pf
->page
+ pf
->size
);
1447 pidx
= PI_IDX(index
);
1448 if (prev_dir
!= NULL
&& PD_IDX(prev_dir
->dirnum
) >= pidx
)
1449 prev_dir
= NULL
; /* Will be wiped out below ! */
1451 for (pi
= pf
->pdir
; pi
!= NULL
&& PD_IDX(pi
->dirnum
) < pidx
;
1456 if (pi
!= NULL
&& PD_IDX(pi
->dirnum
) == pidx
) {
1459 for (i
= index
; i
<= lidx
;) {
1460 if (pd
[PI_OFF(i
)] != MALLOC_NOT_MINE
) {
1461 pd
[PI_OFF(i
)] = MALLOC_NOT_MINE
;
1463 #ifdef MALLOC_EXTRA_SANITY
1464 if (!PD_OFF(pi
->dirnum
)) {
1465 wrterror("(ES): pages directory underflow");
1469 #endif /* MALLOC_EXTRA_SANITY */
1472 #ifdef MALLOC_EXTRA_SANITY
1474 wrtwarning("(ES): page already unmapped");
1475 #endif /* MALLOC_EXTRA_SANITY */
1479 * If no page in that dir, free
1482 if (!PD_OFF(pi
->dirnum
)) {
1483 /* Remove from list. */
1486 if (pi
->prev
!= NULL
)
1487 pi
->prev
->next
= pi
->next
;
1488 if (pi
->next
!= NULL
)
1489 pi
->next
->prev
= pi
->prev
;
1491 munmap(pd
, malloc_pagesize
);
1494 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != PI_IDX(i
))
1499 if (pi
&& !PD_OFF(pi
->dirnum
)) {
1500 /* Resulting page dir is now empty. */
1501 /* Remove from list. */
1502 if (spi
== pi
) /* Update spi only if first. */
1504 if (pi
->prev
!= NULL
)
1505 pi
->prev
->next
= pi
->next
;
1506 if (pi
->next
!= NULL
)
1507 pi
->next
->prev
= pi
->prev
;
1509 munmap(pd
, malloc_pagesize
);
1512 if (pi
== NULL
&& malloc_brk
== tail
) {
1513 /* Resize down the malloc upper boundary. */
1514 last_index
= index
- 1;
1515 malloc_brk
= index2ptr(index
);
1518 /* XXX: We could realloc/shrink the pagedir here I guess. */
1519 if (pf
->size
== 0) { /* Remove from free-list as well. */
1522 if ((px
= pf
->prev
) != &free_list
) {
1523 if (pi
== NULL
&& last_index
== (index
- 1)) {
1529 if (PD_IDX(spi
->dirnum
) < pidx
)
1530 index
= ((PD_IDX(spi
->dirnum
) + 1) * pdi_mod
) - 1;
1531 for (pi
= spi
, i
= index
;pd
[PI_OFF(i
)] == MALLOC_NOT_MINE
;i
--)
1532 #ifdef MALLOC_EXTRA_SANITY
1535 if (pi
== NULL
|| i
== 0)
1538 i
= (PD_IDX(pi
->dirnum
) + 1) * pdi_mod
;
1540 #else /* !MALLOC_EXTRA_SANITY */
1543 #endif /* MALLOC_EXTRA_SANITY */
1544 malloc_brk
= index2ptr(i
+ 1);
1548 if ((px
->next
= pf
->next
) != NULL
)
1549 px
->next
->prev
= px
;
1551 if ((free_list
.next
= pf
->next
) != NULL
)
1552 free_list
.next
->prev
= &free_list
;
1555 last_dir
= prev_dir
;
1565 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1569 static __inline__
void
1570 free_bytes(void *ptr
, int index
, struct pginfo
* info
)
1572 struct pginfo
**mp
, **pd
;
1578 /* Find the chunk number on the page */
1579 i
= ((u_long
) ptr
& malloc_pagemask
) >> info
->shift
;
1581 if ((u_long
) ptr
& ((1UL << (info
->shift
)) - 1)) {
1582 wrtwarning("modified (chunk-) pointer");
1585 if (info
->bits
[i
/ MALLOC_BITS
] & (1UL << (i
% MALLOC_BITS
))) {
1586 wrtwarning("chunk is already free");
1589 if (malloc_junk
&& info
->size
!= 0)
1590 memset(ptr
, SOME_JUNK
, info
->size
);
1592 info
->bits
[i
/ MALLOC_BITS
] |= 1UL << (i
% MALLOC_BITS
);
1595 if (info
->size
!= 0)
1596 mp
= page_dir
+ info
->shift
;
1600 if (info
->free
== 1) {
1601 /* Page became non-full */
1603 /* Insert in address order */
1604 while (*mp
!= NULL
&& (*mp
)->next
!= NULL
&&
1605 (*mp
)->next
->page
< info
->page
)
1611 if (info
->free
!= info
->total
)
1614 /* Find & remove this page in the queue */
1615 while (*mp
!= info
) {
1616 mp
= &((*mp
)->next
);
1617 #ifdef MALLOC_EXTRA_SANITY
1619 wrterror("(ES): Not on queue");
1623 #endif /* MALLOC_EXTRA_SANITY */
1627 /* Free the page & the info structure if need be */
1628 pidx
= PI_IDX(ptr2index(info
->page
));
1629 pdir_lookup(ptr2index(info
->page
), &pi
);
1630 #ifdef MALLOC_EXTRA_SANITY
1631 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1632 wrterror("(ES): mapped pages not found in directory");
1636 #endif /* MALLOC_EXTRA_SANITY */
1637 if (pi
!= last_dir
) {
1638 prev_dir
= last_dir
;
1642 pd
[PI_OFF(ptr2index(info
->page
))] = MALLOC_FIRST
;
1644 /* If the page was mprotected, unprotect it before releasing it */
1645 if (info
->size
== 0)
1646 mprotect(info
->page
, malloc_pagesize
, PROT_READ
| PROT_WRITE
);
1648 vp
= info
->page
; /* Order is important ! */
1649 if (vp
!= (void *) info
)
1657 struct pginfo
*info
, **pd
;
1665 if (!malloc_started
) {
1666 wrtwarning("malloc() has never been called");
1669 /* If we're already sinking, don't make matters any worse. */
1673 if (malloc_ptrguard
&& PTR_ALIGNED(ptr
))
1674 ptr
= (char *) ptr
- PTR_GAP
;
1676 index
= ptr2index(ptr
);
1678 if (index
< malloc_pageshift
) {
1680 wrtwarning("ifree: junk pointer, too low to make sense");
1683 if (index
> last_index
) {
1685 wrtwarning("ifree: junk pointer, too high to make sense");
1688 pidx
= PI_IDX(index
);
1689 pdir_lookup(index
, &pi
);
1690 #ifdef MALLOC_EXTRA_SANITY
1691 if (pi
== NULL
|| PD_IDX(pi
->dirnum
) != pidx
) {
1692 wrterror("(ES): mapped pages not found in directory");
1696 #endif /* MALLOC_EXTRA_SANITY */
1697 if (pi
!= last_dir
) {
1698 prev_dir
= last_dir
;
1702 info
= pd
[PI_OFF(index
)];
1704 if (info
< MALLOC_MAGIC
)
1705 free_pages(ptr
, index
, info
);
1707 free_bytes(ptr
, index
, info
);
1712 * Common function for handling recursion. Only
1713 * print the error message once, to avoid making the problem
1714 * potentially worse.
1717 malloc_recurse(void)
1723 wrtwarning("recursive call");
1731 * These are the public exported interface routines.
1739 malloc_func
= " in malloc():";
1740 if (malloc_active
++) {
1744 if (malloc_sysv
&& !size
)
1751 if (malloc_xmalloc
&& r
== NULL
) {
1752 wrterror("out of memory");
1762 malloc_func
= " in free():";
1763 if (malloc_active
++) {
1775 realloc(void *ptr
, size_t size
)
1780 malloc_func
= " in realloc():";
1781 if (malloc_active
++) {
1786 if (malloc_sysv
&& !size
) {
1789 } else if (ptr
== NULL
)
1792 r
= irealloc(ptr
, size
);
1794 UTRACE(ptr
, size
, r
);
1797 if (malloc_xmalloc
&& r
== NULL
) {
1798 wrterror("out of memory");