Put the 'V' option back in.
[dragonfly.git] / lib / libc / stdlib / malloc.c
1 /*
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  * ----------------------------------------------------------------------------
8  *
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.12 2006/04/07 16:44:51 swildner Exp $
11  *
12  */
13
14 /*
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.
20  */
21 #ifndef MALLOC_EXTRA_SANITY
22 #undef MALLOC_EXTRA_SANITY
23 #endif
24
25 /*
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...
29  */
30 #ifndef MALLOC_STATS
31 #undef  MALLOC_STATS
32 #endif
33
34 /*
35  * What to use for Junk.  This is the byte value we use to fill with
36  * when the 'J' option is enabled.
37  */
38 #define SOME_JUNK       0xd0            /* as in "Duh" :-) */
39
40 /*
41  * The basic parameters you can tweak.
42  *
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.
46  *
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.
52  *
53  */
54
55 #include "namespace.h"
56 #if defined(__FreeBSD__) || defined(__DragonFly__)
57 #   if defined(__i386__)
58 #       define malloc_pageshift         12U
59 #       define malloc_minsize           16U
60 #   endif
61     /*
62      * Make malloc/free/realloc thread-safe in libc for use with
63      * kernel threads.
64      */
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__ */
71
72 #if defined(__sparc__) && defined(sun)
73 #   define malloc_pageshift             12U
74 #   define malloc_minsize               16U
75 #   define MAP_ANON                     (0)
76     static int fdzero;
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__ */
83
84 #ifndef malloc_pageshift
85 #define malloc_pageshift        (PGSHIFT)
86 #endif
87
88 /*
89  * No user serviceable parts behind this point.
90  */
91 #include <sys/types.h>
92 #include <sys/mman.h>
93 #include <errno.h>
94 #include <fcntl.h>
95 #include <paths.h>
96 #include <stddef.h>
97 #include <stdio.h>
98 #include <stdlib.h>
99 #include <string.h>
100 #include <unistd.h>
101 #include "un-namespace.h"
102
103 /*
104  * This structure describes a page worth of chunks.
105  */
106
107 struct pginfo {
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 */
115 };
116
117 /*
118  * This structure describes a number of free pages.
119  */
120
121 struct pgfree {
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 */
127 };
128
129 /* How many bits per u_long in the bitmap */
130 #define MALLOC_BITS     (NBBY * sizeof(u_long))
131
132 /*
133  * Magic values to put in the page_directory
134  */
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)
140
141 #ifndef malloc_pageshift
142 #define malloc_pageshift                12U
143 #endif
144
145 #ifndef malloc_minsize
146 #define malloc_minsize                  16U
147 #endif
148
149 #if !defined(malloc_pagesize)
150 #define malloc_pagesize                 (1UL<<malloc_pageshift)
151 #endif
152
153 #if ((1UL<<malloc_pageshift) != malloc_pagesize)
154 #error  "(1UL<<malloc_pageshift) != malloc_pagesize"
155 #endif
156
157 #ifndef malloc_maxsize
158 #define malloc_maxsize                  ((malloc_pagesize)>>1)
159 #endif
160
161 /* A mask for the offset inside a page.  */
162 #define malloc_pagemask ((malloc_pagesize)-1)
163
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))
167
168 #ifndef THREAD_LOCK
169 #define THREAD_LOCK()
170 #endif
171
172 #ifndef THREAD_UNLOCK
173 #define THREAD_UNLOCK()
174 #endif
175
176 #ifndef MMAP_FD
177 #define MMAP_FD (-1)
178 #endif
179
180 #ifndef INIT_MMAP
181 #define INIT_MMAP()
182 #endif
183
184 /* Set when initialization has been done */
185 static unsigned int malloc_started;
186
187 /* Number of free pages we cache */
188 static unsigned int malloc_cache = 16;
189
190 /* Structure used for linking discrete directory pages. */
191 struct pdinfo {
192     struct pginfo       **base;
193     struct pdinfo       *prev;
194     struct pdinfo       *next;
195     u_long              dirnum;
196 };
197 static struct pdinfo *last_dir; /* Caches to the last and previous */
198 static struct pdinfo *prev_dir; /* referenced directory pages. */
199
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)
206
207 /* The last index in the page directory we care about */
208 static u_long last_index;
209
210 /* Pointer to page directory. Allocated "as if with" malloc */
211 static struct pginfo **page_dir;
212
213 /* Free pages line up here */
214 static struct pgfree free_list;
215
216 /* Abort(), user doesn't handle problems. */
217 static int malloc_abort = 2;
218
219 /* Are we trying to die ?  */
220 static int suicide;
221
222 #ifdef MALLOC_STATS
223 /* dump statistics */
224 static int malloc_stats;
225 #endif
226
227 /* avoid outputting warnings? */
228 static int malloc_silent;
229
230 /* always realloc ?  */
231 static int malloc_realloc;
232
233 /* mprotect free pages PROT_NONE? */
234 static int malloc_freeprot;
235
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;
241
242 /* pass the kernel a hint on free pages ?  */
243 static int malloc_hint = 0;
244
245 /* xmalloc behaviour ?  */
246 static int malloc_xmalloc;
247
248 /* sysv behaviour for malloc(0) ?  */
249 static int malloc_sysv;
250
251 /* zero fill ?  */
252 static int malloc_zero;
253
254 /* junk fill ?  */
255 static int malloc_junk;
256
257 /* utrace ?  */
258 static int malloc_utrace;
259
260 struct ut { void *p; size_t s; void *r; };
261
262 void utrace (struct ut *, int);
263
264 #define UTRACE(a, b, c) \
265         if (malloc_utrace) \
266                 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
267
268 /* Status of malloc. */
269 static int malloc_active;
270
271 /* Allocated memory. */
272 static size_t malloc_used;
273
274 /* my last break. */
275 static void *malloc_brk;
276
277 /* one location cache for free-list holders */
278 static struct pgfree *px;
279
280 /* compile-time options */
281 char *malloc_options;
282
283 /* Name of the current public function */
284 static char *malloc_func;
285
286 /* Macro for mmap */
287 #define MMAP(size) \
288         mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
289             -1, (off_t)0)
290
291 /*
292  * Necessary function declarations.
293  */
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);
298
299 /*
300  * Function for page directory lookup.
301  */
302 static int
303 pdir_lookup(u_long index, struct pdinfo ** pdi)
304 {
305     struct pdinfo       *spi;
306     u_long              pidx = PI_IDX(index);
307
308     if (last_dir != NULL && PD_IDX(last_dir->dirnum) == pidx)
309         *pdi = last_dir;
310     else if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) == pidx)
311         *pdi = prev_dir;
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)))
319                 *pdi = last_dir;
320         else
321             *pdi = prev_dir;
322
323         if (PD_IDX((*pdi)->dirnum) > pidx) {
324             for (spi = (*pdi)->prev;
325                 spi != NULL && PD_IDX(spi->dirnum) > pidx;
326                 spi = spi->prev)
327                     *pdi = spi;
328             if (spi != NULL)
329                 *pdi = spi;
330         } else
331             for (spi = (*pdi)->next;
332                 spi != NULL && PD_IDX(spi->dirnum) <= pidx;
333                 spi = spi->next)
334                     *pdi = spi;
335     } else {
336         *pdi = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
337         for (spi = *pdi;
338             spi != NULL && PD_IDX(spi->dirnum) <= pidx;
339             spi = spi->next)
340                 *pdi = spi;
341     }
342
343     return ((PD_IDX((*pdi)->dirnum) == pidx) ? 0 :
344             (PD_IDX((*pdi)->dirnum) > pidx) ? 1 : -1);
345 }
346
347 #ifdef MALLOC_STATS
348 void
349 malloc_dump(int fd)
350 {
351     char                buf[1024];
352     struct pginfo       **pd;
353     struct pgfree       *pf;
354     struct pdinfo       *pi;
355     int                 j;
356
357     pd = page_dir;
358     pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
359
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;) {
366                 if (!PI_OFF(++j)) {
367                     if ((pi = pi->next) == NULL ||
368                         PD_IDX(pi->dirnum) != PI_IDX(j))
369                             break;
370                     pd = pi->base;
371                     j += pdi_mod;
372                 }
373             }
374             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;) {
379                 if (!PI_OFF(++j)) {
380                     if ((pi = pi->next) == NULL ||
381                         PD_IDX(pi->dirnum) != PI_IDX(j))
382                             break;
383                     pd = pi->base;
384                     j += pdi_mod;
385                 }
386             }
387             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;) {
392                 if (!PI_OFF(++j)) {
393                     if ((pi = pi->next) == NULL ||
394                         PD_IDX(pi->dirnum) != PI_IDX(j))
395                             break;
396                     pd = pi->base;
397                     j += pdi_mod;
398                 }
399             }
400             j--;
401             snprintf(buf, sizeof buf, ".. %5d in use\n", j);
402             _write(fd, buf, strlen(buf));
403
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));
407         } else {
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));
413         }
414         if (!PI_OFF(++j)) {
415             if ((pi = pi->next) == NULL)
416                 break;
417             pd = pi->base;
418             j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod;
419         }
420     }
421
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));
430             break;
431         }
432     }
433
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));
447 }
448 #endif /* MALLOC_STATS */
449
450 extern char     *__progname;
451
452 static void
453 wrterror(char *p)
454 {
455     const char *progname = getprogname();
456     const char *q = " error: ";
457
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));
462     suicide = 1;
463
464 #ifdef MALLOC_STATS
465     if (malloc_stats)
466         malloc_dump(STDERR_FILENO);
467 #endif /* MALLOC_STATS */
468     malloc_active--;
469     if (malloc_abort)
470         abort();
471 }
472
473 static void
474 wrtwarning(char *p)
475 {
476     const char *progname = getprogname();
477     const char *q = " warning: ";
478
479     if (malloc_abort)
480         wrterror(p);
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));
485 }
486
487 #ifdef MALLOC_STATS
488 static void
489 malloc_exit(void)
490 {
491     char *q = "malloc() warning: Couldn't dump stats\n";
492     int  save_errno = errno, fd;
493
494     fd = open("malloc.out", O_RDWR|O_APPEND);
495     if (fd != -1) {
496         malloc_dump(fd);
497         close(fd);
498     } else
499         _write(STDERR_FILENO, q, strlen(q));
500
501     errno = save_errno;
502 }
503 #endif /* MALLOC_STATS */
504
505 /*
506  * Allocate a number of pages from the OS
507  */
508 static void *
509 map_pages(size_t pages)
510 {
511     struct pdinfo       *pi, *spi;
512     struct pginfo       **pd;
513     u_long              idx, pidx, lidx;
514     void                *result, *tail;
515     u_long              index, lindex;
516
517     pages <<= malloc_pageshift;
518     result = MMAP(pages + malloc_guard);
519     if (result == MAP_FAILED) {
520         errno = ENOMEM;
521 #ifdef MALLOC_EXTRA_SANITY
522         wrtwarning("(ES): map_pages fails");
523 #endif /* MALLOC_EXTRA_SANITY */
524         return (NULL);
525     }
526     index = ptr2index(result);
527     tail = result + pages + malloc_guard;
528     lindex = ptr2index(tail) - 1;
529     if (malloc_guard)
530         mprotect(result + pages, malloc_guard, PROT_NONE);
531
532     pidx = PI_IDX(index);
533     lidx = PI_IDX(lindex);
534
535     if (tail > malloc_brk) {
536         malloc_brk = tail;
537         last_index = lindex;
538     }
539     /* Insert directory pages, if needed. */
540     pdir_lookup(index, &pi);
541
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 */
550                 return (NULL);
551             }
552             memset(pd, 0, malloc_pagesize);
553             pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
554             pi->base = pd;
555             pi->prev = spi;
556             pi->next = spi->next;
557             pi->dirnum = idx * (malloc_pagesize / sizeof(struct pginfo *));
558
559             if (spi->next != NULL)
560                 spi->next->prev = pi;
561             spi->next = pi;
562         }
563         if (idx > pidx && idx < lidx) {
564             pi->dirnum += pdi_mod;
565         } else if (idx == pidx) {
566             if (pidx == lidx) {
567                 pi->dirnum += (tail - result) >> malloc_pageshift;
568             } else {
569                 pi->dirnum += pdi_mod - PI_OFF(index);
570             }
571         } else {
572             pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1;
573         }
574 #ifdef MALLOC_EXTRA_SANITY
575         if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > idx) {
576             wrterror("(ES): pages directory overflow");
577             errno = EFAULT;
578             return (NULL);
579         }
580 #endif /* MALLOC_EXTRA_SANITY */
581         if (idx == pidx && pi != last_dir) {
582             prev_dir = last_dir;
583             last_dir = pi;
584         }
585         spi = pi;
586         pi = spi->next;
587     }
588
589     return (result);
590 }
591
592 /*
593  * Initialize the world
594  */
595 static void
596 malloc_init(void)
597 {
598     char        *p, b[64];
599     int         i, j, save_errno = errno;
600
601     INIT_MMAP();
602
603 #ifdef MALLOC_EXTRA_SANITY
604     malloc_junk = 1;
605 #endif /* MALLOC_EXTRA_SANITY */
606
607     for (i = 0; i < 3; i++) {
608         switch (i) {
609             case 0:
610                 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
611                 if (j <= 0)
612                     continue;
613                 b[j] = '\0';
614                 p = b;
615                 break;
616             case 1:
617                 if (issetugid() == 0)
618                     p = getenv("MALLOC_OPTIONS");
619                 else
620                     continue;
621                 break;
622             case 2:
623                 p = malloc_options;
624                 break;
625             default:
626                 p = NULL;
627         }
628
629         for (; p != NULL && *p != '\0'; p++) {
630             switch (*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;
635 #ifdef MALLOC_STATS
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;
661                 default:
662                     j = malloc_abort;
663                     malloc_abort = 0;
664                     wrtwarning("unknown char in MALLOC_OPTIONS");
665                     malloc_abort = j;
666                     break;
667             }
668         }
669     }
670
671     UTRACE(0, 0, 0);
672
673     /*
674      * We want junk in the entire allocation, and zero only in the part
675      * the user asked for.
676      */
677     if (malloc_zero)
678         malloc_junk = 1;
679
680 #ifdef MALLOC_STATS
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 */
685
686     /* Allocate one page for the page directory. */
687     page_dir = (struct pginfo **)MMAP(malloc_pagesize);
688
689     if (page_dir == MAP_FAILED) {
690         wrterror("mmap(2) failed, check limits");
691         errno = ENOMEM;
692         return;
693     }
694     pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1);
695     pdi_mod = pdi_off / sizeof(struct pginfo *);
696
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;
701
702     /* Been here, done that. */
703     malloc_started++;
704
705     /* Recalculate the cache size in bytes, and make sure it's nonzero. */
706     if (!malloc_cache)
707         malloc_cache++;
708     malloc_cache <<= malloc_pageshift;
709     errno = save_errno;
710 }
711
712 /*
713  * Allocate a number of complete pages
714  */
715 static void *
716 malloc_pages(size_t size)
717 {
718     void                *p, *delay_free = NULL, *tp;
719     int                 i;
720     struct pginfo       **pd;
721     struct pdinfo       *pi;
722     u_long              pidx, index;
723     struct pgfree       *pf;
724
725     size = pageround(size) + malloc_guard;
726
727     p = NULL;
728     /* Look for free pages before asking for more */
729     for (pf = free_list.next; pf; pf = pf->next) {
730
731 #ifdef MALLOC_EXTRA_SANITY
732     if (pf->size & malloc_pagemask) {
733         wrterror("(ES): junk length entry on free_list");
734         errno = EFAULT;
735         return (NULL);
736     }
737     if (!pf->size) {
738         wrterror("(ES): zero length entry on free_list");
739         errno = EFAULT;
740         return (NULL);
741     }
742     if (pf->page > (pf->page + pf->size)) {
743         wrterror("(ES): sick entry on free_list");
744         errno = EFAULT;
745         return (NULL);
746     }
747     if ((pi = pf->pdir) == NULL) {
748         wrterror("(ES): invalid page directory on free-list");
749         errno = EFAULT;
750         return (NULL);
751     }
752     if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) {
753         wrterror("(ES): directory index mismatch on free-list");
754         errno = EFAULT;
755         return (NULL);
756     }
757     pd = pi->base;
758     if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) {
759         wrterror("(ES): non-free first page on free-list");
760         errno = EFAULT;
761         return (NULL);
762     }
763     pidx = PI_IDX(ptr2index((pf->page) + (pf->size)) - 1);
764     for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
765             pi = pi->next)
766                 ;
767     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
768         wrterror("(ES): last page not referenced in page directory");
769         errno = EFAULT;
770         return (NULL);
771     }
772     pd = pi->base;
773     if (pd[PI_OFF(ptr2index((pf->page) + (pf->size)) - 1)] != MALLOC_FREE) {
774         wrterror("(ES): non-free last page on free-list");
775         errno = EFAULT;
776         return (NULL);
777     }
778 #endif /* MALLOC_EXTRA_SANITY */
779
780     if (pf->size < size)
781         continue;
782
783     if (pf->size == size) {
784         p = pf->page;
785         pi = pf->pdir;
786         if (pf->next != NULL)
787             pf->next->prev = pf->prev;
788             pf->prev->next = pf->next;
789             delay_free = pf;
790             break;
791         }
792         p = pf->page;
793         pf->page = (char *) pf->page + size;
794         pf->size -= size;
795         pidx = PI_IDX(ptr2index(pf->page));
796         for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
797             pi = pi->next)
798                 ;
799         if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
800             wrterror("(ES): hole in directories");
801             errno = EFAULT;
802             return (NULL);
803         }
804         tp = pf->pdir;
805         pf->pdir = pi;
806         pi = tp;
807         break;
808     }
809
810     size -= malloc_guard;
811
812 #ifdef MALLOC_EXTRA_SANITY
813     if (p != NULL && pi != NULL) {
814         pidx = PD_IDX(pi->dirnum);
815         pd = pi->base;
816     }
817     if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) {
818         wrterror("(ES): allocated non-free page on free-list");
819         errno = EFAULT;
820         return (NULL);
821     }
822 #endif /* MALLOC_EXTRA_SANITY */
823
824     if (p != NULL && (malloc_guard || malloc_freeprot))
825         mprotect(p, size, PROT_READ | PROT_WRITE);
826
827     size >>= malloc_pageshift;
828
829     /* Map new pages */
830     if (p == NULL)
831         p = map_pages(size);
832
833     if (p != NULL) {
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");
840             errno = EFAULT;
841             return (NULL);
842         }
843 #endif /* MALLOC_EXTRA_SANITY */
844         if (pi != last_dir) {
845             prev_dir = last_dir;
846             last_dir = pi;
847         }
848         pd = pi->base;
849         pd[PI_OFF(index)] = MALLOC_FIRST;
850         for (i = 1; i < size; i++) {
851             if (!PI_OFF(index + i)) {
852                 pidx++;
853                 pi = pi->next;
854 #ifdef MALLOC_EXTRA_SANITY
855                 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
856                     wrterror("(ES): hole in mapped pages directory");
857                     errno = EFAULT;
858                     return (NULL);
859                 }
860 #endif /* MALLOC_EXTRA_SANITY */
861                 pd = pi->base;
862             }
863             pd[PI_OFF(index + i)] = MALLOC_FOLLOW;
864         }
865         if (malloc_guard) {
866             if (!PI_OFF(index + i)) {
867                 pidx++;
868                 pi = pi->next;
869 #ifdef MALLOC_EXTRA_SANITY
870                 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
871                     wrterror("(ES): hole in mapped pages directory");
872                     errno = EFAULT;
873                     return (NULL);
874                 }
875 #endif /* MALLOC_EXTRA_SANITY */
876                 pd = pi->base;
877             }
878             pd[PI_OFF(index + i)] = MALLOC_FIRST;
879         }
880         malloc_used += size << malloc_pageshift;
881         malloc_guarded += malloc_guard;
882
883         if (malloc_junk)
884             memset(p, SOME_JUNK, size << malloc_pageshift);
885     }
886     if (delay_free) {
887         if (px == NULL)
888             px = delay_free;
889         else
890             ifree(delay_free);
891     }
892     return (p);
893 }
894
895 /*
896  * Allocate a page of fragments
897  */
898
899 static __inline__ int
900 malloc_make_chunks(int bits)
901 {
902     struct pginfo       *bp, **pd;
903     struct pdinfo       *pi;
904     u_long              pidx;
905     void                *pp;
906     int                 i, k, l;
907
908     /* Allocate a new bucket */
909     pp = malloc_pages((size_t) malloc_pagesize);
910     if (pp == NULL)
911         return (0);
912
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);
917
918     /* Don't waste more than two chunks on this */
919
920     /*
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
923      * pginfo page.
924      * --> Treat it like the big chunk alloc, get a second data page.
925      */
926     if (bits != 0 && (1UL << (bits)) <= l + l) {
927         bp = (struct pginfo *) pp;
928     } else {
929         bp = (struct pginfo *) imalloc(l);
930         if (bp == NULL) {
931             ifree(pp);
932             return (0);
933         }
934     }
935     /* memory protect the page allocated in the malloc(0) case */
936     if (bits == 0) {
937         bp->size = 0;
938         bp->shift = 1;
939         i = malloc_minsize - 1;
940         while (i >>= 1)
941             bp->shift++;
942         bp->total = bp->free = malloc_pagesize >> bp->shift;
943         bp->page = pp;
944
945         k = mprotect(pp, malloc_pagesize, PROT_NONE);
946         if (k < 0) {
947             ifree(pp);
948             ifree(bp);
949             return (0);
950         }
951     } else {
952         bp->size = (1UL << bits);
953         bp->shift = bits;
954         bp->total = bp->free = malloc_pagesize >> bits;
955         bp->page = pp;
956     }
957     /* set all valid bits in the bitmap */
958     k = bp->total;
959     i = 0;
960
961     /* Do a bunch at a time */
962     for (; k - i >= MALLOC_BITS; i += MALLOC_BITS)
963         bp->bits[i / MALLOC_BITS] = ~0UL;
964
965     for (; i < k; i++)
966         bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
967
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));
972             bp->free--;
973             bp->total--;
974             l -= (1 << bits);
975         }
976     }
977     /* MALLOC_LOCK */
978
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");
984         errno = EFAULT;
985         return (0);
986     }
987 #endif /* MALLOC_EXTRA_SANITY */
988     if (pi != last_dir) {
989         prev_dir = last_dir;
990         last_dir = pi;
991     }
992     pd = pi->base;
993     pd[PI_OFF(ptr2index(pp))] = bp;
994
995     bp->next = page_dir[bits];
996     page_dir[bits] = bp;
997
998     /* MALLOC_UNLOCK */
999     return (1);
1000 }
1001
1002 /*
1003  * Allocate a fragment
1004  */
1005 static void *
1006 malloc_bytes(size_t size)
1007 {
1008     int             i, j, k;
1009     u_long          u, *lp;
1010     struct pginfo   *bp;
1011
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;
1016
1017     /* Find the right bucket */
1018     if (size == 0)
1019         j = 0;
1020     else {
1021         j = 1;
1022         i = size - 1;
1023         while (i >>= 1)
1024             j++;
1025     }
1026
1027     /* If it's empty, make a page more of that size chunks */
1028     if (page_dir[j] == NULL && !malloc_make_chunks(j))
1029         return (NULL);
1030
1031     bp = page_dir[j];
1032
1033     /* Find first word of bitmap which isn't empty */
1034     for (lp = bp->bits; !*lp; lp++);
1035
1036     /* Find that bit, and tweak it */
1037     u = 1;
1038     k = 0;
1039     while (!(*lp & u)) {
1040         u += u;
1041         k++;
1042     }
1043
1044     if (malloc_guard) {
1045         /* Walk to a random position. */
1046         i = arc4random() % bp->free;
1047         while (i > 0) {
1048             u += u;
1049             k++;
1050             if (k >= MALLOC_BITS) {
1051                 lp++;
1052                 u = 1;
1053                 k = 0;
1054             }
1055 #ifdef MALLOC_EXTRA_SANITY
1056             if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
1057                 wrterror("chunk overflow");
1058                 errno = EFAULT;
1059                 return (NULL);
1060             }
1061 #endif /* MALLOC_EXTRA_SANITY */
1062             if (*lp & u)
1063                 i--;
1064         }
1065     }
1066     *lp ^= u;
1067
1068     /* If there are no more free, remove from free-list */
1069     if (!--bp->free) {
1070         page_dir[j] = bp->next;
1071         bp->next = NULL;
1072     }
1073     /* Adjust to the real offset of that chunk */
1074     k += (lp - bp->bits) * MALLOC_BITS;
1075     k <<= bp->shift;
1076
1077     if (malloc_junk && bp->size != 0)
1078         memset((char *) bp->page + k, SOME_JUNK, bp->size);
1079
1080     return ((u_char *) bp->page + k);
1081 }
1082
1083 /*
1084  * Magic so that malloc(sizeof(ptr)) is near the end of the page.
1085  */
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)
1089
1090 /*
1091  * Allocate a piece of memory
1092  */
1093 static void *
1094 imalloc(size_t size)
1095 {
1096     void        *result;
1097     int         ptralloc = 0;
1098
1099     if (!malloc_started)
1100         malloc_init();
1101
1102     if (suicide)
1103         abort();
1104
1105     if (malloc_ptrguard && size == PTR_SIZE) {
1106         ptralloc = 1;
1107         size = malloc_pagesize;
1108     }
1109     if ((size + malloc_pagesize) < size) {      /* Check for overflow */
1110         result = NULL;
1111         errno = ENOMEM;
1112     } else if (size <= malloc_maxsize)
1113         result = malloc_bytes(size);
1114     else
1115         result = malloc_pages(size);
1116
1117     if (malloc_abort == 1 && result == NULL)
1118         wrterror("allocation failed");
1119
1120     if (malloc_zero && result != NULL)
1121         memset(result, 0, size);
1122
1123     if (result && ptralloc)
1124         return ((char *) result + PTR_GAP);
1125     return (result);
1126 }
1127
1128 /*
1129  * Change the size of an allocation.
1130  */
1131 static void *
1132 irealloc(void *ptr, size_t size)
1133 {
1134     void                *p;
1135     u_long              osize, index, i;
1136     struct pginfo       **mp;
1137     struct pginfo       **pd;
1138     struct pdinfo       *pi;
1139     u_long              pidx;
1140
1141     if (suicide)
1142         abort();
1143
1144     if (!malloc_started) {
1145         wrtwarning("malloc() has never been called");
1146         return (NULL);
1147     }
1148     if (malloc_ptrguard && PTR_ALIGNED(ptr)) {
1149         if (size <= PTR_SIZE)
1150             return (ptr);
1151
1152         p = imalloc(size);
1153         if (p)
1154             memcpy(p, ptr, PTR_SIZE);
1155         ifree(ptr);
1156         return (p);
1157     }
1158     index = ptr2index(ptr);
1159
1160     if (index < malloc_pageshift) {
1161         wrtwarning("junk pointer, too low to make sense");
1162         return (NULL);
1163     }
1164
1165     if (index > last_index) {
1166         wrtwarning("junk pointer, too high to make sense");
1167         return (NULL);
1168     }
1169
1170     pidx = PI_IDX(index);
1171     pdir_lookup(index, &pi);
1172
1173 #ifdef MALLOC_EXTRA_SANITY
1174     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1175         wrterror("(ES): mapped pages not found in directory");
1176         errno = EFAULT;
1177         return (NULL);
1178     }
1179 #endif /* MALLOC_EXTRA_SANITY */
1180
1181     if (pi != last_dir) {
1182         prev_dir = last_dir;
1183         last_dir = pi;
1184     }
1185     pd = pi->base;
1186     mp = &pd[PI_OFF(index)];
1187
1188     if (*mp == MALLOC_FIRST) {  /* Page allocation */
1189
1190         /* Check the pointer */
1191         if ((u_long) ptr & malloc_pagemask) {
1192             wrtwarning("modified (page-) pointer");
1193             return (NULL);
1194         }
1195         /* Find the size in bytes */
1196         i = index;
1197         if (!PI_OFF(++i)) {
1198             pi = pi->next;
1199             if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1200                 pi = NULL;
1201             if (pi != NULL)
1202                 pd = pi->base;
1203         }
1204         for (osize = malloc_pagesize;pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
1205             osize += malloc_pagesize;
1206             if (!PI_OFF(++i)) {
1207                 pi = pi->next;
1208                 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1209                     pi = NULL;
1210                 if (pi != NULL)
1211                     pd = pi->base;
1212             }
1213         }
1214
1215         if (!malloc_realloc && size <= osize &&
1216             size > osize - malloc_pagesize) {
1217             
1218             if (malloc_junk)
1219                 memset((char *)ptr + size, SOME_JUNK, osize - size);
1220                 return (ptr);   /* ..don't do anything else. */
1221         }
1222     } else if (*mp >= MALLOC_MAGIC) {   /* Chunk allocation */
1223
1224         /* Check the pointer for sane values */
1225         if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) {
1226             wrtwarning("modified (chunk-) pointer");
1227             return (NULL);
1228         }
1229         /* Find the chunk index in the page */
1230         i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift;
1231
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");
1235             return (NULL);
1236         }
1237         osize = (*mp)->size;
1238
1239         if (!malloc_realloc && size <= osize &&
1240             (size > osize / 2 || osize == malloc_minsize)) {
1241             if (malloc_junk)
1242                 memset((char *) ptr + size, SOME_JUNK, osize - size);
1243                 return (ptr);   /* ..don't do anything else. */
1244         }
1245     } else {
1246         wrtwarning("irealloc: pointer to wrong page");
1247         return (NULL);
1248     }
1249
1250     p = imalloc(size);
1251
1252     if (p != NULL) {
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) {
1256             if (osize < size)
1257                 memcpy(p, ptr, osize);
1258             else
1259                 memcpy(p, ptr, size);
1260         }
1261         ifree(ptr);
1262     }
1263     return (p);
1264 }
1265
1266 /*
1267  * Free a sequence of pages
1268  */
1269 static __inline__ void
1270 free_pages(void *ptr, u_long index, struct pginfo * info)
1271 {
1272     u_long              i, l, cachesize = 0, pidx, lidx;
1273     struct pginfo       **pd;
1274     struct pdinfo       *pi, *spi;
1275     struct pgfree       *pf, *pt = NULL;
1276     void                *tail;
1277
1278     if (info == MALLOC_FREE) {
1279         wrtwarning("page is already free");
1280         return;
1281     }
1282     if (info != MALLOC_FIRST) {
1283         wrtwarning("free_pages: pointer to wrong page");
1284         return;
1285     }
1286     if ((u_long) ptr & malloc_pagemask) {
1287         wrtwarning("modified (page-) pointer");
1288         return;
1289     }
1290     /* Count how many pages and mark them free at the same time */
1291     pidx = PI_IDX(index);
1292     pdir_lookup(index, &pi);
1293
1294 #ifdef MALLOC_EXTRA_SANITY
1295     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1296         wrterror("(ES): mapped pages not found in directory");
1297         errno = EFAULT;
1298         return;
1299     }
1300 #endif /* MALLOC_EXTRA_SANITY */
1301
1302     spi = pi;           /* Save page index for start of region. */
1303
1304     pd = pi->base;
1305     pd[PI_OFF(index)] = MALLOC_FREE;
1306     i = 1;
1307     if (!PI_OFF(index + i)) {
1308         pi = pi->next;
1309         if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i))
1310             pi = NULL;
1311         else
1312             pd = pi->base;
1313     }
1314     while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) {
1315         pd[PI_OFF(index + i)] = MALLOC_FREE;
1316         i++;
1317         if (!PI_OFF(index + i)) {
1318             if ((pi = pi->next) == NULL ||
1319                 PD_IDX(pi->dirnum) != PI_IDX(index + i))
1320                     pi = NULL;
1321             else
1322                 pd = pi->base;
1323         }
1324     }
1325
1326     l = i << malloc_pageshift;
1327
1328     if (malloc_junk)
1329         memset(ptr, SOME_JUNK, l);
1330
1331     malloc_used -= l;
1332     malloc_guarded -= malloc_guard;
1333     if (malloc_guard) {
1334
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");
1338             errno = EFAULT;
1339             return;
1340         }
1341 #endif /* MALLOC_EXTRA_SANITY */
1342
1343         pd[PI_OFF(index + i)] = MALLOC_FREE;
1344         l += malloc_guard;
1345     }
1346     tail = (char *) ptr + l;
1347
1348     if (malloc_hint)
1349         madvise(ptr, l, MADV_FREE);
1350
1351     if (malloc_freeprot)
1352         mprotect(ptr, l, PROT_NONE);
1353
1354     /* Add to free-list. */
1355     if (px == NULL)
1356         px = imalloc(sizeof *px);       /* This cannot fail... */
1357     px->page = ptr;
1358     px->pdir = spi;
1359     px->size = l;
1360
1361     if (free_list.next == NULL) {
1362         /* Nothing on free list, put this at head. */
1363         px->next = NULL;
1364         px->prev = &free_list;
1365         free_list.next = px;
1366         pf = px;
1367         px = NULL;
1368     } else {
1369         /*
1370          * Find the right spot, leave pf pointing to the modified
1371          * entry.
1372          */
1373
1374         /* Race ahead here, while calculating cache size. */
1375         for (pf = free_list.next;
1376             pf->page + pf->size < ptr && pf->next != NULL;
1377             pf = pf->next)
1378                 cachesize += pf->size;
1379
1380         /* Finish cache size calculation. */
1381         pt = pf;
1382         while (pt) {
1383             cachesize += pt->size;
1384             pt = pt->next;
1385         }
1386
1387         if (pf->page > tail) {
1388             /* Insert before entry */
1389             px->next = pf;
1390             px->prev = pf->prev;
1391             pf->prev = px;
1392             px->prev->next = px;
1393             pf = px;
1394             px = NULL;
1395         } else if ((pf->page + pf->size) == ptr) {
1396             /* Append to the previous entry. */
1397             cachesize -= pf->size;
1398             pf->size += l;
1399             if (pf->next != NULL &&
1400                 pf->page + pf->size == pf->next->page) {
1401                     /* And collapse the next too. */
1402                     pt = pf->next;
1403                     pf->size += pt->size;
1404                     pf->next = pt->next;
1405                     if (pf->next != NULL)
1406                         pf->next->prev = pf;
1407             }
1408         } else if (pf->page == tail) {
1409             /* Prepend to entry. */
1410             cachesize -= pf->size;
1411             pf->size += l;
1412             pf->page = ptr;
1413             pf->pdir = spi;
1414         } else if (pf->next == NULL) {
1415             /* Append at tail of chain. */
1416             px->next = NULL;
1417             px->prev = pf;
1418             pf->next = px;
1419             pf = px;
1420             px = NULL;
1421         } else {
1422             wrterror("freelist is destroyed");
1423             errno = EFAULT;
1424             return;
1425         }
1426     }
1427
1428     if (pf->pdir != last_dir) {
1429         prev_dir = last_dir;
1430         last_dir = pf->pdir;
1431     }
1432
1433     /* Return something to OS ? */
1434     if (pf->size > (malloc_cache - cachesize)) {
1435
1436         /*
1437          * Keep the cache intact.  Notice that the '>' above guarantees that
1438          * the pf will always have at least one page afterwards.
1439          */
1440         if (munmap((char *) pf->page + (malloc_cache - cachesize),
1441             pf->size - (malloc_cache - cachesize)) != 0)
1442                 goto not_return;
1443         tail = pf->page + pf->size;
1444         lidx = ptr2index(tail) - 1;
1445         pf->size = malloc_cache - cachesize;
1446
1447         index = ptr2index(pf->page + pf->size);
1448
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 ! */
1452
1453         for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
1454             pi = pi->next)
1455                 ;
1456
1457         spi = pi;
1458         if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
1459             pd = pi->base;
1460
1461             for (i = index; i <= lidx;) {
1462                 if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
1463                     pd[PI_OFF(i)] = MALLOC_NOT_MINE;
1464
1465 #ifdef MALLOC_EXTRA_SANITY
1466                     if (!PD_OFF(pi->dirnum)) {
1467                         wrterror("(ES): pages directory underflow");
1468                         errno = EFAULT;
1469                         return;
1470                     }
1471 #endif /* MALLOC_EXTRA_SANITY */
1472                     pi->dirnum--;
1473                 }
1474 #ifdef MALLOC_EXTRA_SANITY
1475                 else
1476                     wrtwarning("(ES): page already unmapped");
1477 #endif /* MALLOC_EXTRA_SANITY */
1478                 i++;
1479                 if (!PI_OFF(i)) {
1480                     /*
1481                      * If no page in that dir, free
1482                      * directory page.
1483                      */
1484                     if (!PD_OFF(pi->dirnum)) {
1485                         /* Remove from list. */
1486                         if (spi == pi)
1487                         spi = pi->prev;
1488                         if (pi->prev != NULL)
1489                             pi->prev->next = pi->next;
1490                         if (pi->next != NULL)
1491                             pi->next->prev = pi->prev;
1492                         pi = pi->next;
1493                         munmap(pd, malloc_pagesize);
1494                     } else
1495                         pi = pi->next;
1496                     if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(i))
1497                         break;
1498                         pd = pi->base;
1499                     }
1500                 }
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. */
1505                         spi = pi->prev;
1506                     if (pi->prev != NULL)
1507                         pi->prev->next = pi->next;
1508                     if (pi->next != NULL)
1509                         pi->next->prev = pi->prev;
1510                     pi = pi->next;
1511                     munmap(pd, malloc_pagesize);
1512                 }
1513             }
1514             if (pi == NULL && malloc_brk == tail) {
1515                 /* Resize down the malloc upper boundary. */
1516                 last_index = index - 1;
1517                 malloc_brk = index2ptr(index);
1518             }
1519
1520             /* XXX: We could realloc/shrink the pagedir here I guess. */
1521             if (pf->size == 0) {        /* Remove from free-list as well. */
1522                 if (px)
1523                     ifree(px);
1524                 if ((px = pf->prev) != &free_list) {
1525                     if (pi == NULL && last_index == (index - 1)) {
1526                         if (spi == NULL) {
1527                             malloc_brk = NULL;
1528                             i = 11;
1529                         } else {
1530                             pd = spi->base;
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
1535                             if (!PI_OFF(i)) {
1536                                 pi = pi->prev;
1537                                 if (pi == NULL || i == 0)
1538                                     break;
1539                                 pd = pi->base;
1540                                 i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
1541                             }
1542 #else /* !MALLOC_EXTRA_SANITY */
1543                             {
1544                         }
1545 #endif /* MALLOC_EXTRA_SANITY */
1546                         malloc_brk = index2ptr(i + 1);
1547                     }
1548                     last_index = i;
1549                 }
1550                 if ((px->next = pf->next) != NULL)
1551                     px->next->prev = px;
1552             } else {
1553                 if ((free_list.next = pf->next) != NULL)
1554                     free_list.next->prev = &free_list;
1555             }
1556             px = pf;
1557             last_dir = prev_dir;
1558             prev_dir = NULL;
1559         }
1560     }
1561 not_return:
1562     if (pt != NULL)
1563         ifree(pt);
1564 }
1565
1566 /*
1567  * Free a chunk, and possibly the page it's on, if the page becomes empty.
1568  */
1569
1570 /* ARGSUSED */
1571 static __inline__ void
1572 free_bytes(void *ptr, int index, struct pginfo * info)
1573 {
1574     struct pginfo       **mp, **pd;
1575     struct pdinfo       *pi;
1576     u_long              pidx;
1577     void                *vp;
1578     int         i;
1579
1580     /* Find the chunk number on the page */
1581     i = ((u_long) ptr & malloc_pagemask) >> info->shift;
1582
1583     if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {
1584         wrtwarning("modified (chunk-) pointer");
1585         return;
1586     }
1587     if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
1588         wrtwarning("chunk is already free");
1589         return;
1590     }
1591     if (malloc_junk && info->size != 0)
1592         memset(ptr, SOME_JUNK, info->size);
1593
1594     info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
1595     info->free++;
1596
1597     if (info->size != 0)
1598         mp = page_dir + info->shift;
1599     else
1600         mp = page_dir;
1601
1602     if (info->free == 1) {
1603         /* Page became non-full */
1604
1605         /* Insert in address order */
1606         while (*mp != NULL && (*mp)->next != NULL &&
1607             (*mp)->next->page < info->page)
1608                 mp = &(*mp)->next;
1609         info->next = *mp;
1610         *mp = info;
1611         return;
1612     }
1613     if (info->free != info->total)
1614         return;
1615
1616     /* Find & remove this page in the queue */
1617     while (*mp != info) {
1618         mp = &((*mp)->next);
1619 #ifdef MALLOC_EXTRA_SANITY
1620         if (!*mp) {
1621             wrterror("(ES): Not on queue");
1622             errno = EFAULT;
1623             return;
1624         }
1625 #endif /* MALLOC_EXTRA_SANITY */
1626     }
1627     *mp = info->next;
1628
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");
1635         errno = EFAULT;
1636         return;
1637     }
1638 #endif /* MALLOC_EXTRA_SANITY */
1639     if (pi != last_dir) {
1640         prev_dir = last_dir;
1641         last_dir = pi;
1642     }
1643     pd = pi->base;
1644     pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;
1645
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);
1649
1650     vp = info->page;    /* Order is important ! */
1651     if (vp != (void *) info)
1652         ifree(info);
1653     ifree(vp);
1654 }
1655
1656 static void
1657 ifree(void *ptr)
1658 {
1659     struct pginfo       *info, **pd;
1660     u_long              pidx, index;
1661     struct pdinfo       *pi;
1662
1663     /* This is legal */
1664     if (ptr == NULL)
1665         return;
1666
1667     if (!malloc_started) {
1668         wrtwarning("malloc() has never been called");
1669         return;
1670     }
1671     /* If we're already sinking, don't make matters any worse. */
1672     if (suicide)
1673         return;
1674
1675     if (malloc_ptrguard && PTR_ALIGNED(ptr))
1676         ptr = (char *) ptr - PTR_GAP;
1677
1678     index = ptr2index(ptr);
1679
1680     if (index < malloc_pageshift) {
1681         warnx("(%p)", ptr);
1682         wrtwarning("ifree: junk pointer, too low to make sense");
1683         return;
1684     }
1685     if (index > last_index) {
1686         warnx("(%p)", ptr);
1687         wrtwarning("ifree: junk pointer, too high to make sense");
1688         return;
1689     }
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");
1695         errno = EFAULT;
1696         return;
1697     }
1698 #endif /* MALLOC_EXTRA_SANITY */
1699     if (pi != last_dir) {
1700         prev_dir = last_dir;
1701         last_dir = pi;
1702     }
1703     pd = pi->base;
1704     info = pd[PI_OFF(index)];
1705
1706     if (info < MALLOC_MAGIC)
1707         free_pages(ptr, index, info);
1708     else
1709         free_bytes(ptr, index, info);
1710     return;
1711 }
1712
1713 /*
1714  * Common function for handling recursion.  Only
1715  * print the error message once, to avoid making the problem
1716  * potentially worse.
1717  */
1718 static void
1719 malloc_recurse(void)
1720 {
1721     static int  noprint;
1722
1723     if (noprint == 0) {
1724         noprint = 1;
1725         wrtwarning("recursive call");
1726     }
1727     malloc_active--;
1728     THREAD_UNLOCK();
1729     errno = EDEADLK;
1730 }
1731
1732 /*
1733  * These are the public exported interface routines.
1734  */
1735 void *
1736 malloc(size_t size)
1737 {
1738     void *r;
1739
1740     THREAD_LOCK();
1741     malloc_func = " in malloc():";
1742     if (malloc_active++) {
1743         malloc_recurse();
1744         return (NULL);
1745     }
1746     if (malloc_sysv && !size)
1747        r = 0;
1748     else
1749        r = imalloc(size);
1750     UTRACE(0, size, r);
1751     malloc_active--;
1752     THREAD_UNLOCK();
1753     if (malloc_xmalloc && r == NULL) {
1754         wrterror("out of memory");
1755         errno = ENOMEM;
1756     }
1757     return (r);
1758 }
1759
1760 void
1761 free(void *ptr)
1762 {
1763     THREAD_LOCK();
1764     malloc_func = " in free():";
1765     if (malloc_active++) {
1766         malloc_recurse();
1767         return;
1768     }
1769     ifree(ptr);
1770     UTRACE(ptr, 0, 0);
1771     malloc_active--;
1772     THREAD_UNLOCK();
1773     return;
1774 }
1775
1776 void *
1777 realloc(void *ptr, size_t size)
1778 {
1779     void *r;
1780
1781     THREAD_LOCK();
1782     malloc_func = " in realloc():";
1783     if (malloc_active++) {
1784         malloc_recurse();
1785         return (NULL);
1786     }
1787
1788     if (malloc_sysv && !size) {
1789         ifree(ptr);
1790         r = 0;
1791     } else if (ptr == NULL)
1792         r = imalloc(size);
1793     else
1794         r = irealloc(ptr, size);
1795
1796     UTRACE(ptr, size, r);
1797     malloc_active--;
1798     THREAD_UNLOCK();
1799     if (malloc_xmalloc && r == NULL) {
1800         wrterror("out of memory");
1801         errno = ENOMEM;
1802     }
1803     return (r);
1804 }