summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/malloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/malloc.c')
-rw-r--r--src/lib/libc/stdlib/malloc.c1698
1 files changed, 1698 insertions, 0 deletions
diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
new file mode 100644
index 0000000000..ae89f5d72b
--- /dev/null
+++ b/src/lib/libc/stdlib/malloc.c
@@ -0,0 +1,1698 @@
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
10#if defined(LIBC_SCCS) && !defined(lint)
11static char rcsid[] = "$OpenBSD: malloc.c,v 1.72 2005/03/31 21:24:46 tdeval Exp $";
12#endif /* LIBC_SCCS and not lint */
13
14/*
15 * Defining MALLOC_EXTRA_SANITY will enable extra checks which are
16 * related to internal conditions and consistency in malloc.c. This has
17 * a 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#include <sys/types.h>
41#include <sys/time.h>
42#include <sys/resource.h>
43#include <sys/param.h>
44#include <sys/mman.h>
45#include <sys/uio.h>
46#include <stdio.h>
47#include <stdlib.h>
48#include <string.h>
49#include <unistd.h>
50#include <fcntl.h>
51#include <limits.h>
52#include <errno.h>
53
54#include "thread_private.h"
55
56/*
57 * The basic parameters you can tweak.
58 *
59 * malloc_pageshift pagesize = 1 << malloc_pageshift
60 * It's probably best if this is the native
61 * page size, but it shouldn't have to be.
62 *
63 * malloc_minsize minimum size of an allocation in bytes.
64 * If this is too small it's too much work
65 * to manage them. This is also the smallest
66 * unit of alignment used for the storage
67 * returned by malloc/realloc.
68 *
69 */
70
71#if defined(__OpenBSD__) && defined(__sparc__)
72# define malloc_pageshift 13U
73#endif /* __OpenBSD__ */
74
75/*
76 * No user serviceable parts behind this point.
77 *
78 * This structure describes a page worth of chunks.
79 */
80
81struct pginfo {
82 struct pginfo *next; /* next on the free list */
83 void *page; /* Pointer to the page */
84 u_short size; /* size of this page's chunks */
85 u_short shift; /* How far to shift for this size chunks */
86 u_short free; /* How many free chunks */
87 u_short total; /* How many chunk */
88 u_long bits[1]; /* Which chunks are free */
89};
90
91/*
92 * This structure describes a number of free pages.
93 */
94
95struct pgfree {
96 struct pgfree *next; /* next run of free pages */
97 struct pgfree *prev; /* prev run of free pages */
98 void *page; /* pointer to free pages */
99 void *pdir; /* pointer to the base page's dir */
100 size_t size; /* number of bytes free */
101};
102
103/*
104 * How many bits per u_long in the bitmap.
105 * Change only if not 8 bits/byte
106 */
107#define MALLOC_BITS (8*sizeof(u_long))
108
109/*
110 * Magic values to put in the page_directory
111 */
112#define MALLOC_NOT_MINE ((struct pginfo*) 0)
113#define MALLOC_FREE ((struct pginfo*) 1)
114#define MALLOC_FIRST ((struct pginfo*) 2)
115#define MALLOC_FOLLOW ((struct pginfo*) 3)
116#define MALLOC_MAGIC ((struct pginfo*) 4)
117
118#ifndef malloc_pageshift
119#define malloc_pageshift (PGSHIFT)
120#endif
121
122#ifndef malloc_minsize
123#define malloc_minsize 16U
124#endif
125
126#ifndef malloc_pageshift
127#error "malloc_pageshift undefined"
128#endif
129
130#if !defined(malloc_pagesize)
131#define malloc_pagesize (1UL<<malloc_pageshift)
132#endif
133
134#if ((1UL<<malloc_pageshift) != malloc_pagesize)
135#error "(1UL<<malloc_pageshift) != malloc_pagesize"
136#endif
137
138#ifndef malloc_maxsize
139#define malloc_maxsize ((malloc_pagesize)>>1)
140#endif
141
142/* A mask for the offset inside a page. */
143#define malloc_pagemask ((malloc_pagesize)-1)
144
145#define pageround(foo) (((foo) + (malloc_pagemask)) & ~malloc_pagemask)
146#define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift)
147
148/* fd of /dev/zero */
149#ifdef USE_DEV_ZERO
150static int fdzero;
151#define MMAP_FD fdzero
152#define INIT_MMAP() \
153 { if ((fdzero=open("/dev/zero", O_RDWR, 0000)) == -1) \
154 wrterror("open of /dev/zero\n"); }
155#else
156#define MMAP_FD (-1)
157#define INIT_MMAP()
158#endif
159
160/* Set when initialization has been done */
161static unsigned int malloc_started;
162
163/* Number of free pages we cache */
164static unsigned int malloc_cache = 16;
165
166/* Structure used for linking discrete directory pages. */
167struct pdinfo {
168 struct pginfo **base;
169 struct pdinfo *prev;
170 struct pdinfo *next;
171 u_long dirnum;
172};
173static struct pdinfo *last_dir; /* Caches to the last and previous */
174static struct pdinfo *prev_dir; /* referenced directory pages. */
175
176static size_t pdi_off;
177static u_long pdi_mod;
178#define PD_IDX(num) ((num) / (malloc_pagesize/sizeof(struct pginfo *)))
179#define PD_OFF(num) ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1))
180#define PI_IDX(index) ((index) / pdi_mod)
181#define PI_OFF(index) ((index) % pdi_mod)
182
183/* The last index in the page directory we care about */
184static u_long last_index;
185
186/* Pointer to page directory. Allocated "as if with" malloc */
187static struct pginfo **page_dir;
188
189/* Free pages line up here */
190static struct pgfree free_list;
191
192/* Abort(), user doesn't handle problems. */
193static int malloc_abort = 2;
194
195/* Are we trying to die ? */
196static int suicide;
197
198#ifdef MALLOC_STATS
199/* dump statistics */
200static int malloc_stats;
201#endif
202
203/* avoid outputting warnings? */
204static int malloc_silent;
205
206/* always realloc ? */
207static int malloc_realloc;
208
209/* mprotect free pages PROT_NONE? */
210static int malloc_freeprot;
211
212/* use guard pages after allocations? */
213static int malloc_guard = 0;
214
215#if defined(__FreeBSD__) || (defined(__OpenBSD__) && defined(MADV_FREE))
216/* pass the kernel a hint on free pages ? */
217static int malloc_hint;
218#endif
219
220/* xmalloc behaviour ? */
221static int malloc_xmalloc;
222
223/* zero fill ? */
224static int malloc_zero;
225
226/* junk fill ? */
227static int malloc_junk;
228
229#ifdef __FreeBSD__
230/* utrace ? */
231static int malloc_utrace;
232
233struct ut { void *p; size_t s; void *r; };
234
235void utrace(struct ut *, int);
236
237#define UTRACE(a, b, c) \
238 if (malloc_utrace) \
239 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
240#else /* !__FreeBSD__ */
241#define UTRACE(a,b,c)
242#endif
243
244/* Status of malloc. */
245static int malloc_active;
246
247/* Allocated memory. */
248static size_t malloc_used;
249
250/* My last break. */
251static void *malloc_brk;
252
253/* One location cache for free-list holders. */
254static struct pgfree *px;
255
256/* Compile-time options. */
257char *malloc_options;
258
259/* Name of the current public function. */
260static char *malloc_func;
261
262/* Macro for mmap. */
263#define MMAP(size) \
264 mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
265 MMAP_FD, (off_t)0)
266
267/*
268 * Necessary function declarations.
269 */
270static void *imalloc(size_t size);
271static void ifree(void *ptr);
272static void *irealloc(void *ptr, size_t size);
273static void *malloc_bytes(size_t size);
274
275
276/*
277 * Function for page directory lookup.
278 */
279static int
280pdir_lookup(u_long index, struct pdinfo **pdi)
281{
282 struct pdinfo *spi;
283 u_long pidx = PI_IDX(index);
284
285 if (last_dir != NULL && PD_IDX(last_dir->dirnum) == pidx)
286 *pdi = last_dir;
287 else if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) == pidx)
288 *pdi = prev_dir;
289 else if (last_dir != NULL && prev_dir != NULL) {
290 if ((PD_IDX(last_dir->dirnum) > pidx) ?
291 (PD_IDX(last_dir->dirnum) - pidx):(pidx - PD_IDX(last_dir->dirnum))
292 < (PD_IDX(prev_dir->dirnum) > pidx) ?
293 (PD_IDX(prev_dir->dirnum) - pidx):(pidx - PD_IDX(prev_dir->dirnum)))
294 *pdi = last_dir;
295 else
296 *pdi = prev_dir;
297
298 if (PD_IDX((*pdi)->dirnum) > pidx) {
299 for (spi=(*pdi)->prev;spi!=NULL && PD_IDX(spi->dirnum)>pidx;
300 spi=spi->prev)
301 *pdi = spi;
302 if (spi != NULL)
303 *pdi = spi;
304 } else
305 for (spi=(*pdi)->next;spi!=NULL && PD_IDX(spi->dirnum)<=pidx;
306 spi=spi->next)
307 *pdi = spi;
308 } else {
309 *pdi = (struct pdinfo *)((caddr_t)page_dir + pdi_off);
310 for (spi=*pdi;spi!=NULL && PD_IDX(spi->dirnum)<=pidx;spi=spi->next)
311 *pdi = spi;
312 }
313
314 return ((PD_IDX((*pdi)->dirnum) == pidx)?0:(PD_IDX((*pdi)->dirnum) > pidx)?1:-1);
315}
316
317
318#ifdef MALLOC_STATS
319void
320malloc_dump(FILE *fd)
321{
322 struct pginfo **pd;
323 struct pgfree *pf;
324 struct pdinfo *pi;
325 int j;
326
327 pd = page_dir;
328 pi = (struct pdinfo *)((caddr_t)pd + pdi_off);
329
330 /* print out all the pages */
331 for(j=0;j<=last_index;) {
332 fprintf(fd, "%08lx %5d ", j << malloc_pageshift, j);
333 if (pd[PI_OFF(j)] == MALLOC_NOT_MINE) {
334 for(j++;j<=last_index && pd[PI_OFF(j)] == MALLOC_NOT_MINE;) {
335 if (!PI_OFF(++j)) {
336 if ((pi = pi->next) == NULL ||
337 PD_IDX(pi->dirnum) != PI_IDX(j)) break;
338 pd = pi->base;
339 j += pdi_mod;
340 }
341 }
342 j--;
343 fprintf(fd, ".. %5d not mine\n", j);
344 } else if (pd[PI_OFF(j)] == MALLOC_FREE) {
345 for(j++;j<=last_index && pd[PI_OFF(j)] == MALLOC_FREE;) {
346 if (!PI_OFF(++j)) {
347 if ((pi = pi->next) == NULL ||
348 PD_IDX(pi->dirnum) != PI_IDX(j)) break;
349 pd = pi->base;
350 j += pdi_mod;
351 }
352 }
353 j--;
354 fprintf(fd, ".. %5d free\n", j);
355 } else if (pd[PI_OFF(j)] == MALLOC_FIRST) {
356 for(j++;j<=last_index && pd[PI_OFF(j)] == MALLOC_FOLLOW;) {
357 if (!PI_OFF(++j)) {
358 if ((pi = pi->next) == NULL ||
359 PD_IDX(pi->dirnum) != PI_IDX(j)) break;
360 pd = pi->base;
361 j += pdi_mod;
362 }
363 }
364 j--;
365 fprintf(fd, ".. %5d in use\n", j);
366 } else if (pd[PI_OFF(j)] < MALLOC_MAGIC) {
367 fprintf(fd, "(%p)\n", pd[PI_OFF(j)]);
368 } else {
369 fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n",
370 pd[PI_OFF(j)], pd[PI_OFF(j)]->free, pd[PI_OFF(j)]->total,
371 pd[PI_OFF(j)]->size, pd[PI_OFF(j)]->page, pd[PI_OFF(j)]->next);
372 }
373 if (!PI_OFF(++j)) {
374 if ((pi = pi->next) == NULL)
375 break;
376 pd = pi->base;
377 j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod;
378 }
379 }
380
381 for(pf=free_list.next; pf; pf=pf->next) {
382 fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
383 pf, pf->page, pf->page + pf->size, pf->size,
384 pf->prev, pf->next);
385 if (pf == pf->next) {
386 fprintf(fd, "Free_list loops\n");
387 break;
388 }
389 }
390
391 /* print out various info */
392 fprintf(fd, "Minsize\t%d\n", malloc_minsize);
393 fprintf(fd, "Maxsize\t%d\n", malloc_maxsize);
394 fprintf(fd, "Pagesize\t%lu\n", (u_long)malloc_pagesize);
395 fprintf(fd, "Pageshift\t%d\n", malloc_pageshift);
396 fprintf(fd, "In use\t%lu\n", (u_long)malloc_used);
397}
398#endif /* MALLOC_STATS */
399
400extern char *__progname;
401
402static void
403wrterror(char *p)
404{
405 char *q = " error: ";
406 struct iovec iov[4];
407
408 iov[0].iov_base = __progname;
409 iov[0].iov_len = strlen(__progname);
410 iov[1].iov_base = malloc_func;
411 iov[1].iov_len = strlen(malloc_func);
412 iov[2].iov_base = q;
413 iov[2].iov_len = strlen(q);
414 iov[3].iov_base = p;
415 iov[3].iov_len = strlen(p);
416 writev(STDERR_FILENO, iov, 4);
417
418 suicide = 1;
419#ifdef MALLOC_STATS
420 if (malloc_stats)
421 malloc_dump(stderr);
422#endif /* MALLOC_STATS */
423 malloc_active--;
424 if (malloc_abort)
425 abort();
426}
427
428static void
429wrtwarning(char *p)
430{
431 char *q = " warning: ";
432 struct iovec iov[4];
433
434 if (malloc_abort)
435 wrterror(p);
436 else if (malloc_silent)
437 return;
438
439 iov[0].iov_base = __progname;
440 iov[0].iov_len = strlen(__progname);
441 iov[1].iov_base = malloc_func;
442 iov[1].iov_len = strlen(malloc_func);
443 iov[2].iov_base = q;
444 iov[2].iov_len = strlen(q);
445 iov[3].iov_base = p;
446 iov[3].iov_len = strlen(p);
447 writev(STDERR_FILENO, iov, 4);
448}
449
450#ifdef MALLOC_STATS
451static void
452malloc_exit(void)
453{
454 FILE *fd = fopen("malloc.out", "a");
455 char *q = "malloc() warning: Couldn't dump stats\n";
456 if (fd != NULL) {
457 malloc_dump(fd);
458 fclose(fd);
459 } else
460 write(STDERR_FILENO, q, strlen(q));
461}
462#endif /* MALLOC_STATS */
463
464
465/*
466 * Allocate a number of pages from the OS
467 */
468static void *
469map_pages(size_t pages)
470{
471 struct pdinfo *pi, *spi;
472 struct pginfo **pd;
473 u_long pidx,lidx;
474 void *result, *tail;
475 u_long index;
476
477 pages <<= malloc_pageshift;
478 result = MMAP(pages + malloc_guard);
479 if (result == MAP_FAILED) {
480 errno = ENOMEM;
481#ifdef MALLOC_EXTRA_SANITY
482 wrtwarning("(ES): map_pages fails\n");
483#endif /* MALLOC_EXTRA_SANITY */
484 return (NULL);
485 }
486 tail = result + pages + malloc_guard;
487 if (malloc_guard)
488 mprotect(result + pages, malloc_guard, PROT_NONE);
489
490 if (tail > malloc_brk)
491 malloc_brk = tail;
492 if ((index = ptr2index(tail) - 1) > last_index)
493 last_index = index;
494
495 /* Insert directory pages, if needed. */
496 pidx = PI_IDX(ptr2index(result));
497 lidx = PI_IDX(index);
498
499 pdir_lookup(ptr2index(result), &pi);
500
501 for (index=pidx,spi=pi;index<=lidx;index++) {
502 if (pi == NULL || PD_IDX(pi->dirnum) != index) {
503 if ((pd = MMAP(malloc_pagesize)) == MAP_FAILED) {
504 errno = ENOMEM;
505 munmap(result, tail - result);
506#ifdef MALLOC_EXTRA_SANITY
507 wrtwarning("(ES): map_pages fails\n");
508#endif /* MALLOC_EXTRA_SANITY */
509 return (NULL);
510 }
511 memset(pd, 0, malloc_pagesize);
512 pi = (struct pdinfo *)((caddr_t)pd + pdi_off);
513 pi->base = pd;
514 pi->prev = spi;
515 pi->next = spi->next;
516 pi->dirnum = index * (malloc_pagesize/sizeof(struct pginfo *));
517
518 if (spi->next != NULL)
519 spi->next->prev = pi;
520 spi->next = pi;
521 }
522 if (index > pidx && index < lidx) {
523 pi->dirnum += pdi_mod;
524 } else if (index == pidx) {
525 if (pidx == lidx) {
526 pi->dirnum += (tail - result) >> malloc_pageshift;
527 } else {
528 pi->dirnum += pdi_mod - PI_OFF(ptr2index(result));
529 }
530 } else {
531 pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1;
532 }
533#ifdef MALLOC_EXTRA_SANITY
534 if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > index) {
535 wrterror("(ES): pages directory overflow\n");
536 errno = EFAULT;
537 return (NULL);
538 }
539#endif /* MALLOC_EXTRA_SANITY */
540 if (index == pidx && pi != last_dir) {
541 prev_dir = last_dir;
542 last_dir = pi;
543 }
544 spi = pi;
545 pi = spi->next;
546 }
547
548 return (result);
549}
550
551
552/*
553 * Initialize the world
554 */
555static void
556malloc_init(void)
557{
558 char *p, b[64];
559 int i, j;
560 int save_errno = errno;
561
562 _MALLOC_LOCK_INIT();
563
564 INIT_MMAP();
565
566#ifdef MALLOC_EXTRA_SANITY
567 malloc_junk = 1;
568#endif /* MALLOC_EXTRA_SANITY */
569
570 for (i = 0; i < 3; i++) {
571 switch (i) {
572 case 0:
573 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
574 if (j <= 0)
575 continue;
576 b[j] = '\0';
577 p = b;
578 break;
579
580 case 1:
581 if (issetugid() == 0)
582 p = getenv("MALLOC_OPTIONS");
583 else
584 continue;
585 break;
586
587 case 2:
588 p = malloc_options;
589 break;
590
591 default: p = NULL;
592 }
593 for (; p != NULL && *p != '\0'; p++) {
594 switch (*p) {
595 case '>': malloc_cache <<= 1; break;
596 case '<': malloc_cache >>= 1; break;
597 case 'a': malloc_abort = 0; break;
598 case 'A': malloc_abort = 1; break;
599#ifdef MALLOC_STATS
600 case 'd': malloc_stats = 0; break;
601 case 'D': malloc_stats = 1; break;
602#endif /* MALLOC_STATS */
603 case 'f': malloc_freeprot = 0; break;
604 case 'F': malloc_freeprot = 1; break;
605 case 'g': malloc_guard = 0; break;
606 case 'G': malloc_guard = malloc_pagesize; break;
607#if defined(__FreeBSD__) || (defined(__OpenBSD__) && defined(MADV_FREE))
608 case 'h': malloc_hint = 0; break;
609 case 'H': malloc_hint = 1; break;
610#endif /* __FreeBSD__ */
611 case 'j': malloc_junk = 0; break;
612 case 'J': malloc_junk = 1; break;
613 case 'n': malloc_silent = 0; break;
614 case 'N': malloc_silent = 1; break;
615 case 'r': malloc_realloc = 0; break;
616 case 'R': malloc_realloc = 1; break;
617#ifdef __FreeBSD__
618 case 'u': malloc_utrace = 0; break;
619 case 'U': malloc_utrace = 1; break;
620#endif /* __FreeBSD__ */
621 case 'x': malloc_xmalloc = 0; break;
622 case 'X': malloc_xmalloc = 1; break;
623 case 'z': malloc_zero = 0; break;
624 case 'Z': malloc_zero = 1; break;
625 default:
626 j = malloc_abort;
627 malloc_abort = 0;
628 wrtwarning("unknown char in MALLOC_OPTIONS\n");
629 malloc_abort = j;
630 break;
631 }
632 }
633 }
634
635 UTRACE(0, 0, 0);
636
637 /*
638 * We want junk in the entire allocation, and zero only in the part
639 * the user asked for.
640 */
641 if (malloc_zero)
642 malloc_junk=1;
643
644#ifdef MALLOC_STATS
645 if (malloc_stats && (atexit(malloc_exit) == -1))
646 wrtwarning("atexit(2) failed. Will not be able to dump malloc stats on exit\n");
647#endif /* MALLOC_STATS */
648
649 /* Allocate one page for the page directory. */
650 page_dir = (struct pginfo **) MMAP(malloc_pagesize);
651
652 if (page_dir == MAP_FAILED) {
653 wrterror("mmap(2) failed, check limits\n");
654 errno = ENOMEM;
655 return;
656 }
657
658 pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1);
659 pdi_mod = pdi_off / sizeof(struct pginfo *);
660
661 last_dir = (struct pdinfo *)((caddr_t)page_dir + pdi_off);
662 last_dir->base = page_dir;
663 last_dir->prev = last_dir->next = NULL;
664 last_dir->dirnum = malloc_pageshift;
665
666 /* Been here, done that. */
667 malloc_started++;
668
669 /* Recalculate the cache size in bytes, and make sure it's nonzero. */
670
671 if (!malloc_cache)
672 malloc_cache++;
673
674 malloc_cache <<= malloc_pageshift;
675
676 errno = save_errno;
677}
678
679/*
680 * Allocate a number of complete pages
681 */
682static void *
683malloc_pages(size_t size)
684{
685 void *p, *delay_free = NULL;
686 int i;
687 struct rlimit rl;
688 struct pginfo **pd;
689 struct pdinfo *pi;
690 u_long pidx;
691 void *tp;
692 struct pgfree *pf;
693 u_long index;
694 int m;
695
696 size = pageround(size) + malloc_guard;
697
698 p = NULL;
699 /* Look for free pages before asking for more */
700 for (pf = free_list.next; pf; pf = pf->next) {
701
702#ifdef MALLOC_EXTRA_SANITY
703 if (pf->size & malloc_pagemask) {
704 wrterror("(ES): junk length entry on free_list\n");
705 errno = EFAULT;
706 return (NULL);
707 }
708 if (!pf->size) {
709 wrterror("(ES): zero length entry on free_list\n");
710 errno = EFAULT;
711 return (NULL);
712 }
713 if (pf->page > (pf->page + pf->size)) {
714 wrterror("(ES): sick entry on free_list\n");
715 errno = EFAULT;
716 return (NULL);
717 }
718 if ((pi = pf->pdir) == NULL) {
719 wrterror("(ES): invalid page directory on free-list\n");
720 errno = EFAULT;
721 return (NULL);
722 }
723 if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) {
724 wrterror("(ES): directory index mismatch on free-list\n");
725 errno = EFAULT;
726 return (NULL);
727 }
728 pd = pi->base;
729 if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) {
730 wrterror("(ES): non-free first page on free-list\n");
731 errno = EFAULT;
732 return (NULL);
733 }
734 pidx = PI_IDX(ptr2index((pf->page)+(pf->size))-1);
735 for (pi=pf->pdir; pi!=NULL && PD_IDX(pi->dirnum)<pidx; pi=pi->next);
736 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
737 wrterror("(ES): last page not referenced in page directory\n");
738 errno = EFAULT;
739 return (NULL);
740 }
741 pd = pi->base;
742 if (pd[PI_OFF(ptr2index((pf->page)+(pf->size))-1)] != MALLOC_FREE) {
743 wrterror("(ES): non-free last page on free-list\n");
744 errno = EFAULT;
745 return (NULL);
746 }
747#endif /* MALLOC_EXTRA_SANITY */
748
749 if (pf->size < size)
750 continue;
751
752 if (pf->size == size) {
753 p = pf->page;
754 pi = pf->pdir;
755 if (pf->next != NULL)
756 pf->next->prev = pf->prev;
757 pf->prev->next = pf->next;
758 delay_free = pf;
759 break;
760 }
761
762 p = pf->page;
763 pf->page = (char *)pf->page + size;
764 pf->size -= size;
765 pidx = PI_IDX(ptr2index(pf->page));
766 for (pi=pf->pdir; pi!=NULL && PD_IDX(pi->dirnum)<pidx; pi=pi->next);
767 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
768 wrterror("(ES): hole in directories\n");
769 errno = EFAULT;
770 return (NULL);
771 }
772 tp = pf->pdir;
773 pf->pdir = pi;
774 pi = tp;
775 break;
776 }
777
778 size -= malloc_guard;
779
780#ifdef MALLOC_EXTRA_SANITY
781 if (p != NULL && pi != NULL) {
782 pidx = PD_IDX(pi->dirnum);
783 pd = pi->base;
784 }
785 if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) {
786 wrterror("(ES): allocated non-free page on free-list\n");
787 errno = EFAULT;
788 return (NULL);
789 }
790#endif /* MALLOC_EXTRA_SANITY */
791
792 if (p != NULL && (malloc_guard || malloc_freeprot))
793 mprotect(p, size, PROT_READ|PROT_WRITE);
794
795 size >>= malloc_pageshift;
796
797 /* Map new pages */
798 if (p == NULL)
799 p = map_pages(size);
800
801 if (p != NULL) {
802
803 index = ptr2index(p);
804 pidx = PI_IDX(index);
805 pdir_lookup(index, &pi);
806#ifdef MALLOC_EXTRA_SANITY
807 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
808 wrterror("(ES): mapped pages not found in directory\n");
809 errno = EFAULT;
810 return (NULL);
811 }
812#endif /* MALLOC_EXTRA_SANITY */
813 if (pi != last_dir) {
814 prev_dir = last_dir;
815 last_dir = pi;
816 }
817 pd = pi->base;
818 pd[PI_OFF(index)] = MALLOC_FIRST;
819 for (i=1;i<size;i++) {
820 if (!PI_OFF(index+i)) {
821 pidx++;
822 pi = pi->next;
823#ifdef MALLOC_EXTRA_SANITY
824 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
825 wrterror("(ES): hole in mapped pages directory\n");
826 errno = EFAULT;
827 return (NULL);
828 }
829#endif /* MALLOC_EXTRA_SANITY */
830 pd = pi->base;
831 }
832 pd[PI_OFF(index+i)] = MALLOC_FOLLOW;
833 }
834 if (malloc_guard) {
835 if (!PI_OFF(index+i)) {
836 pidx++;
837 pi = pi->next;
838#ifdef MALLOC_EXTRA_SANITY
839 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
840 wrterror("(ES): hole in mapped pages directory\n");
841 errno = EFAULT;
842 return (NULL);
843 }
844#endif /* MALLOC_EXTRA_SANITY */
845 pd = pi->base;
846 }
847 pd[PI_OFF(index+i)] = MALLOC_FIRST;
848 }
849
850 malloc_used += size << malloc_pageshift;
851
852 if (malloc_junk)
853 memset(p, SOME_JUNK, size << malloc_pageshift);
854 }
855
856 if (delay_free) {
857 if (px == NULL)
858 px = delay_free;
859 else
860 ifree(delay_free);
861 }
862
863 return (p);
864}
865
866/*
867 * Allocate a page of fragments
868 */
869
870static __inline__ int
871malloc_make_chunks(int bits)
872{
873 struct pginfo *bp;
874 struct pginfo **pd;
875 struct pdinfo *pi;
876 u_long pidx;
877 void *pp;
878 int i, k, l;
879
880 /* Allocate a new bucket */
881 pp = malloc_pages((size_t)malloc_pagesize);
882 if (pp == NULL)
883 return (0);
884
885 /* Find length of admin structure */
886 l = sizeof *bp - sizeof(u_long);
887 l += sizeof(u_long) *
888 (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
889
890 /* Don't waste more than two chunks on this */
891 /*
892 * If we are to allocate a memory protected page for the malloc(0)
893 * case (when bits=0), it must be from a different page than the
894 * pginfo page.
895 * --> Treat it like the big chunk alloc, get a second data page.
896 */
897 if (bits != 0 && (1UL<<(bits)) <= l+l) {
898 bp = (struct pginfo *)pp;
899 } else {
900 bp = (struct pginfo *)imalloc(l);
901 if (bp == NULL) {
902 ifree(pp);
903 return (0);
904 }
905 }
906
907 /* memory protect the page allocated in the malloc(0) case */
908 if (bits == 0) {
909
910 bp->size = 0;
911 bp->shift = 1;
912 i = malloc_minsize-1;
913 while (i >>= 1)
914 bp->shift++;
915 bp->total = bp->free = malloc_pagesize >> bp->shift;
916 bp->page = pp;
917
918 k = mprotect(pp, malloc_pagesize, PROT_NONE);
919 if (k < 0) {
920 ifree(pp);
921 ifree(bp);
922 return (0);
923 }
924 } else {
925 bp->size = (1UL<<bits);
926 bp->shift = bits;
927 bp->total = bp->free = malloc_pagesize >> bits;
928 bp->page = pp;
929 }
930
931 /* set all valid bits in the bitmap */
932 k = bp->total;
933 i = 0;
934
935 /* Do a bunch at a time */
936 for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
937 bp->bits[i / MALLOC_BITS] = ~0UL;
938
939 for(; i < k; i++)
940 bp->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS);
941
942 if (bp == bp->page) {
943 /* Mark the ones we stole for ourselves */
944 for(i=0;l > 0;i++) {
945 bp->bits[i/MALLOC_BITS] &= ~(1UL<<(i%MALLOC_BITS));
946 bp->free--;
947 bp->total--;
948 l -= (1 << bits);
949 }
950 }
951
952 /* MALLOC_LOCK */
953
954 pidx = PI_IDX(ptr2index(pp));
955 pdir_lookup(ptr2index(pp), &pi);
956#ifdef MALLOC_EXTRA_SANITY
957 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
958 wrterror("(ES): mapped pages not found in directory\n");
959 errno = EFAULT;
960 return (0);
961 }
962#endif /* MALLOC_EXTRA_SANITY */
963 if (pi != last_dir) {
964 prev_dir = last_dir;
965 last_dir = pi;
966 }
967 pd = pi->base;
968 pd[PI_OFF(ptr2index(pp))] = bp;
969
970 bp->next = page_dir[bits];
971 page_dir[bits] = bp;
972
973 /* MALLOC_UNLOCK */
974
975 return (1);
976}
977
978/*
979 * Allocate a fragment
980 */
981static void *
982malloc_bytes(size_t size)
983{
984 int i,j;
985 u_long u;
986 struct pginfo *bp;
987 int k;
988 u_long *lp;
989
990 /* Don't bother with anything less than this */
991 /* unless we have a malloc(0) requests */
992 if (size != 0 && size < malloc_minsize)
993 size = malloc_minsize;
994
995 /* Find the right bucket */
996 if (size == 0)
997 j=0;
998 else {
999 j = 1;
1000 i = size-1;
1001 while (i >>= 1)
1002 j++;
1003 }
1004
1005 /* If it's empty, make a page more of that size chunks */
1006 if (page_dir[j] == NULL && !malloc_make_chunks(j))
1007 return (NULL);
1008
1009 bp = page_dir[j];
1010
1011 /* Find first word of bitmap which isn't empty */
1012 for (lp = bp->bits; !*lp; lp++)
1013 ;
1014
1015 /* Find that bit, and tweak it */
1016 u = 1;
1017 k = 0;
1018 while (!(*lp & u)) {
1019 u += u;
1020 k++;
1021 }
1022
1023 if (malloc_guard) {
1024 /* Walk to a random position. */
1025 i = arc4random() % bp->free;
1026 while (i > 0) {
1027 u += u;
1028 k++;
1029 if (k >= MALLOC_BITS) {
1030 lp++;
1031 u = 1;
1032 k = 0;
1033 }
1034#ifdef MALLOC_EXTRA_SANITY
1035 if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
1036 wrterror("chunk overflow\n");
1037 errno = EFAULT;
1038 return (NULL);
1039 }
1040#endif /* MALLOC_EXTRA_SANITY */
1041 if (*lp & u)
1042 i--;
1043 }
1044 }
1045 *lp ^= u;
1046
1047 /* If there are no more free, remove from free-list */
1048 if (!--bp->free) {
1049 page_dir[j] = bp->next;
1050 bp->next = NULL;
1051 }
1052
1053 /* Adjust to the real offset of that chunk */
1054 k += (lp-bp->bits)*MALLOC_BITS;
1055 k <<= bp->shift;
1056
1057 if (malloc_junk && bp->size != 0)
1058 memset((char *)bp->page + k, SOME_JUNK, bp->size);
1059
1060 return ((u_char *)bp->page + k);
1061}
1062
1063/*
1064 * Allocate a piece of memory
1065 */
1066static void *
1067imalloc(size_t size)
1068{
1069 void *result;
1070 int ptralloc = 0;
1071
1072 if (!malloc_started)
1073 malloc_init();
1074
1075 if (suicide)
1076 abort();
1077
1078 if ((size + malloc_pagesize) < size) { /* Check for overflow */
1079 result = NULL;
1080 errno = ENOMEM;
1081 }
1082 else if (size <= malloc_maxsize)
1083 result = malloc_bytes(size);
1084 else
1085 result = malloc_pages(size);
1086
1087 if (malloc_abort == 1 && result == NULL)
1088 wrterror("allocation failed\n");
1089
1090 if (malloc_zero && result != NULL)
1091 memset(result, 0, size);
1092
1093 return (result);
1094}
1095
1096/*
1097 * Change the size of an allocation.
1098 */
1099static void *
1100irealloc(void *ptr, size_t size)
1101{
1102 void *p;
1103 u_long osize, index, i;
1104 struct pginfo **mp;
1105 struct pginfo **pd;
1106 struct pdinfo *pi;
1107 u_long pidx;
1108
1109 if (suicide)
1110 abort();
1111
1112 if (!malloc_started) {
1113 wrtwarning("malloc() has never been called\n");
1114 return (NULL);
1115 }
1116
1117 index = ptr2index(ptr);
1118
1119 if (index < malloc_pageshift) {
1120 wrtwarning("junk pointer, too low to make sense\n");
1121 return (NULL);
1122 }
1123
1124 if (index > last_index) {
1125 wrtwarning("junk pointer, too high to make sense\n");
1126 return (NULL);
1127 }
1128
1129 pidx = PI_IDX(index);
1130 pdir_lookup(index, &pi);
1131#ifdef MALLOC_EXTRA_SANITY
1132 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1133 wrterror("(ES): mapped pages not found in directory\n");
1134 errno = EFAULT;
1135 return (NULL);
1136 }
1137#endif /* MALLOC_EXTRA_SANITY */
1138 if (pi != last_dir) {
1139 prev_dir = last_dir;
1140 last_dir = pi;
1141 }
1142
1143 pd = pi->base;
1144 mp = &pd[PI_OFF(index)];
1145
1146 if (*mp == MALLOC_FIRST) { /* Page allocation */
1147
1148 /* Check the pointer */
1149 if ((u_long)ptr & malloc_pagemask) {
1150 wrtwarning("modified (page-) pointer\n");
1151 return (NULL);
1152 }
1153
1154 /* Find the size in bytes */
1155 i = index;
1156 if (!PI_OFF(++i)) {
1157 pi = pi->next;
1158 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1159 pi = NULL;
1160 if (pi != NULL)
1161 pd = pi->base;
1162 }
1163 for (osize = malloc_pagesize;
1164 pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
1165 osize += malloc_pagesize;
1166 if (!PI_OFF(++i)) {
1167 pi = pi->next;
1168 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1169 pi = NULL;
1170 if (pi != NULL)
1171 pd = pi->base;
1172 }
1173 }
1174
1175 if (!malloc_realloc && /* Unless we have to, */
1176 size <= osize && /* .. or are too small, */
1177 size > (osize - malloc_pagesize)) { /* .. or can free a page, */
1178 if (malloc_junk)
1179 memset((char *)ptr + size, SOME_JUNK, osize-size);
1180 return (ptr); /* ..don't do anything else. */
1181 }
1182
1183 } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */
1184
1185 /* Check the pointer for sane values */
1186 if ((u_long)ptr & ((1UL<<((*mp)->shift))-1)) {
1187 wrtwarning("modified (chunk-) pointer\n");
1188 return (NULL);
1189 }
1190
1191 /* Find the chunk index in the page */
1192 i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
1193
1194 /* Verify that it isn't a free chunk already */
1195 if ((*mp)->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
1196 wrtwarning("chunk is already free\n");
1197 return (NULL);
1198 }
1199
1200 osize = (*mp)->size;
1201
1202 if (!malloc_realloc && /* Unless we have to, */
1203 size <= osize && /* ..or are too small, */
1204 (size > osize/2 || /* ..or could use a smaller size, */
1205 osize == malloc_minsize)) { /* ..(if there is one) */
1206 if (malloc_junk)
1207 memset((char *)ptr + size, SOME_JUNK, osize-size);
1208 return (ptr); /* ..don't do anything else. */
1209 }
1210
1211 } else {
1212 wrtwarning("pointer to wrong page\n");
1213 return (NULL);
1214 }
1215
1216 p = imalloc(size);
1217
1218 if (p != NULL) {
1219 /* copy the lesser of the two sizes, and free the old one */
1220 /* Don't move from/to 0 sized region !!! */
1221 if (osize != 0 && size != 0) {
1222 if (osize < size)
1223 memcpy(p, ptr, osize);
1224 else
1225 memcpy(p, ptr, size);
1226 }
1227 ifree(ptr);
1228 }
1229
1230 return (p);
1231}
1232
1233/*
1234 * Free a sequence of pages
1235 */
1236
1237static __inline__ void
1238free_pages(void *ptr, u_long index, struct pginfo *info)
1239{
1240 u_long i, l;
1241 struct pginfo **pd;
1242 struct pdinfo *pi, *spi;
1243 u_long pidx, lidx;
1244 struct pgfree *pf, *pt=NULL;
1245 void *tail;
1246
1247 if (info == MALLOC_FREE) {
1248 wrtwarning("page is already free\n");
1249 return;
1250 }
1251
1252 if (info != MALLOC_FIRST) {
1253 wrtwarning("pointer to wrong page\n");
1254 return;
1255 }
1256
1257 if ((u_long)ptr & malloc_pagemask) {
1258 wrtwarning("modified (page-) pointer\n");
1259 return;
1260 }
1261
1262 /* Count how many pages and mark them free at the same time */
1263 pidx = PI_IDX(index);
1264 pdir_lookup(index, &pi);
1265#ifdef MALLOC_EXTRA_SANITY
1266 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1267 wrterror("(ES): mapped pages not found in directory\n");
1268 errno = EFAULT;
1269 return;
1270 }
1271#endif /* MALLOC_EXTRA_SANITY */
1272
1273 spi = pi; /* Save page index for start of region. */
1274
1275 pd = pi->base;
1276 pd[PI_OFF(index)] = MALLOC_FREE;
1277 i = 1;
1278 if (!PI_OFF(index+i)) {
1279 pi = pi->next;
1280 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index+i))
1281 pi = NULL;
1282 else
1283 pd = pi->base;
1284 }
1285 while (pi != NULL && pd[PI_OFF(index+i)] == MALLOC_FOLLOW) {
1286 pd[PI_OFF(index+i)] = MALLOC_FREE;
1287 i++;
1288 if (!PI_OFF(index+i)) {
1289 if ((pi=pi->next) == NULL || PD_IDX(pi->dirnum) != PI_IDX(index+i))
1290 pi = NULL;
1291 else
1292 pd = pi->base;
1293 }
1294 }
1295
1296 l = i << malloc_pageshift;
1297
1298 if (malloc_junk)
1299 memset(ptr, SOME_JUNK, l);
1300
1301 malloc_used -= l;
1302 if (malloc_guard) {
1303#ifdef MALLOC_EXTRA_SANITY
1304 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index+i)) {
1305 wrterror("(ES): hole in mapped pages directory\n");
1306 errno = EFAULT;
1307 return;
1308 }
1309#endif /* MALLOC_EXTRA_SANITY */
1310 pd[PI_OFF(index+i)] = MALLOC_FREE;
1311 l += malloc_guard;
1312 }
1313 tail = (char *)ptr + l;
1314
1315#if defined(__FreeBSD__) || (defined(__OpenBSD__) && defined(MADV_FREE))
1316 if (malloc_hint)
1317 madvise(ptr, l, MADV_FREE);
1318#endif
1319
1320 if (malloc_freeprot)
1321 mprotect(ptr, l, PROT_NONE);
1322
1323 /* Add to free-list. */
1324 if (px == NULL)
1325 px = imalloc(sizeof *px); /* This cannot fail... */
1326 px->page = ptr;
1327 px->pdir = spi;
1328 px->size = l;
1329
1330 if (free_list.next == NULL) {
1331
1332 /* Nothing on free list, put this at head. */
1333 px->next = NULL;
1334 px->prev = &free_list;
1335 free_list.next = px;
1336 pf = px;
1337 px = NULL;
1338
1339 } else {
1340
1341 /* Find the right spot, leave pf pointing to the modified entry. */
1342
1343 for(pf = free_list.next; (pf->page+pf->size) < ptr && pf->next != NULL;
1344 pf = pf->next)
1345 ; /* Race ahead here. */
1346
1347 if (pf->page > tail) {
1348 /* Insert before entry */
1349 px->next = pf;
1350 px->prev = pf->prev;
1351 pf->prev = px;
1352 px->prev->next = px;
1353 pf = px;
1354 px = NULL;
1355 } else if ((pf->page + pf->size) == ptr ) {
1356 /* Append to the previous entry. */
1357 pf->size += l;
1358 if (pf->next != NULL && (pf->page + pf->size) == pf->next->page ) {
1359 /* And collapse the next too. */
1360 pt = pf->next;
1361 pf->size += pt->size;
1362 pf->next = pt->next;
1363 if (pf->next != NULL)
1364 pf->next->prev = pf;
1365 }
1366 } else if (pf->page == tail) {
1367 /* Prepend to entry. */
1368 pf->size += l;
1369 pf->page = ptr;
1370 pf->pdir = spi;
1371 } else if (pf->next == NULL) {
1372 /* Append at tail of chain. */
1373 px->next = NULL;
1374 px->prev = pf;
1375 pf->next = px;
1376 pf = px;
1377 px = NULL;
1378 } else {
1379 wrterror("freelist is destroyed\n");
1380 errno = EFAULT;
1381 return;
1382 }
1383 }
1384
1385 if (pf->pdir != last_dir) {
1386 prev_dir = last_dir;
1387 last_dir = pf->pdir;
1388 }
1389
1390 /* Return something to OS ? */
1391 if (pf->next == NULL && /* If we're the last one, */
1392 pf->size > malloc_cache && /* ..and the cache is full, */
1393 (pf->page + pf->size) == malloc_brk) { /* ..and none behind us, */
1394
1395 /*
1396 * Keep the cache intact. Notice that the '>' above guarantees that
1397 * the pf will always have at least one page afterwards.
1398 */
1399 if (munmap((char *)pf->page + malloc_cache, pf->size - malloc_cache)!=0)
1400 goto not_return;
1401 tail = pf->page + pf->size;
1402 lidx = ptr2index(tail) - 1;
1403 pf->size = malloc_cache;
1404
1405 malloc_brk = pf->page + malloc_cache;
1406
1407 index = ptr2index(malloc_brk);
1408
1409 pidx = PI_IDX(index);
1410 if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx)
1411 prev_dir = NULL; /* Will be wiped out below ! */
1412
1413 for (pi=pf->pdir; pi!=NULL && PD_IDX(pi->dirnum)<pidx; pi=pi->next);
1414
1415 if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
1416 pd = pi->base;
1417
1418 for(i=index;i <= last_index;) {
1419 if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
1420 pd[PI_OFF(i)] = MALLOC_NOT_MINE;
1421#ifdef MALLOC_EXTRA_SANITY
1422 if (!PD_OFF(pi->dirnum)) {
1423 wrterror("(ES): pages directory underflow\n");
1424 errno = EFAULT;
1425 return;
1426 }
1427#endif /* MALLOC_EXTRA_SANITY */
1428 pi->dirnum--;
1429 }
1430 i++;
1431 if (!PI_OFF(i)) {
1432 /* If no page in that dir, free directory page. */
1433 if (!PD_OFF(pi->dirnum)) {
1434 /* Remove from list. */
1435 pi->prev->next = pi->next;
1436 if (pi->next != NULL)
1437 pi->next->prev = pi->prev;
1438 pi = pi->next;
1439 munmap(pd, malloc_pagesize);
1440 } else
1441 pi = pi->next;
1442 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(i))
1443 break;
1444 pd = pi->base;
1445 }
1446 }
1447 }
1448
1449 last_index = index - 1;
1450
1451 /* XXX: We could realloc/shrink the pagedir here I guess. */
1452 }
1453not_return:
1454 if (pt != NULL)
1455 ifree(pt);
1456}
1457
1458/*
1459 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1460 */
1461
1462/* ARGSUSED */
1463static __inline__ void
1464free_bytes(void *ptr, int index, struct pginfo *info)
1465{
1466 int i;
1467 struct pginfo **mp;
1468 struct pginfo **pd;
1469 struct pdinfo *pi;
1470 u_long pidx;
1471 void *vp;
1472
1473 /* Find the chunk number on the page */
1474 i = ((u_long)ptr & malloc_pagemask) >> info->shift;
1475
1476 if ((u_long)ptr & ((1UL<<(info->shift))-1)) {
1477 wrtwarning("modified (chunk-) pointer\n");
1478 return;
1479 }
1480
1481 if (info->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
1482 wrtwarning("chunk is already free\n");
1483 return;
1484 }
1485
1486 if (malloc_junk && info->size != 0)
1487 memset(ptr, SOME_JUNK, info->size);
1488
1489 info->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS);
1490 info->free++;
1491
1492 if (info->size != 0)
1493 mp = page_dir + info->shift;
1494 else
1495 mp = page_dir;
1496
1497 if (info->free == 1) {
1498
1499 /* Page became non-full */
1500
1501 /* Insert in address order */
1502 while (*mp != NULL && (*mp)->next != NULL &&
1503 (*mp)->next->page < info->page)
1504 mp = &(*mp)->next;
1505 info->next = *mp;
1506 *mp = info;
1507 return;
1508 }
1509
1510 if (info->free != info->total)
1511 return;
1512
1513 /* Find & remove this page in the queue */
1514 while (*mp != info) {
1515 mp = &((*mp)->next);
1516#ifdef MALLOC_EXTRA_SANITY
1517 if (!*mp) {
1518 wrterror("(ES): Not on queue\n");
1519 errno = EFAULT;
1520 return;
1521 }
1522#endif /* MALLOC_EXTRA_SANITY */
1523 }
1524 *mp = info->next;
1525
1526 /* Free the page & the info structure if need be */
1527 pidx = PI_IDX(ptr2index(info->page));
1528 pdir_lookup(ptr2index(info->page), &pi);
1529#ifdef MALLOC_EXTRA_SANITY
1530 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1531 wrterror("(ES): mapped pages not found in directory\n");
1532 errno = EFAULT;
1533 return;
1534 }
1535#endif /* MALLOC_EXTRA_SANITY */
1536 if (pi != last_dir) {
1537 prev_dir = last_dir;
1538 last_dir = pi;
1539 }
1540
1541 pd = pi->base;
1542 pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;
1543
1544 /* If the page was mprotected, unprotect it before releasing it */
1545 if (info->size == 0) {
1546 mprotect(info->page, malloc_pagesize, PROT_READ|PROT_WRITE);
1547 /* Do we have to care if mprotect succeeds here ? */
1548 }
1549
1550 vp = info->page; /* Order is important ! */
1551 if(vp != (void*)info)
1552 ifree(info);
1553 ifree(vp);
1554}
1555
1556static void
1557ifree(void *ptr)
1558{
1559 struct pginfo *info;
1560 struct pginfo **pd;
1561 struct pdinfo *pi;
1562 u_long pidx;
1563 u_long index;
1564
1565 /* This is legal */
1566 if (ptr == NULL)
1567 return;
1568
1569 if (!malloc_started) {
1570 wrtwarning("malloc() has never been called\n");
1571 return;
1572 }
1573
1574 /* If we're already sinking, don't make matters any worse. */
1575 if (suicide)
1576 return;
1577
1578 index = ptr2index(ptr);
1579
1580 if (index < malloc_pageshift) {
1581 wrtwarning("junk pointer, too low to make sense\n");
1582 return;
1583 }
1584
1585 if (index > last_index) {
1586 wrtwarning("junk pointer, too high to make sense\n");
1587 return;
1588 }
1589
1590 pidx = PI_IDX(index);
1591 pdir_lookup(index, &pi);
1592#ifdef MALLOC_EXTRA_SANITY
1593 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1594 wrterror("(ES): mapped pages not found in directory\n");
1595 errno = EFAULT;
1596 return;
1597 }
1598#endif /* MALLOC_EXTRA_SANITY */
1599 if (pi != last_dir) {
1600 prev_dir = last_dir;
1601 last_dir = pi;
1602 }
1603
1604 pd = pi->base;
1605 info = pd[PI_OFF(index)];
1606
1607 if (info < MALLOC_MAGIC)
1608 free_pages(ptr, index, info);
1609 else
1610 free_bytes(ptr, index, info);
1611 return;
1612}
1613
1614/*
1615 * Common function for handling recursion. Only
1616 * print the error message once, to avoid making the problem
1617 * potentially worse.
1618 */
1619static void
1620malloc_recurse(void)
1621{
1622 static int noprint;
1623
1624 if (noprint == 0) {
1625 noprint = 1;
1626 wrtwarning("recursive call\n");
1627 }
1628 malloc_active--;
1629 _MALLOC_UNLOCK();
1630 errno = EDEADLK;
1631}
1632
1633/*
1634 * These are the public exported interface routines.
1635 */
1636void *
1637malloc(size_t size)
1638{
1639 void *r;
1640
1641 _MALLOC_LOCK();
1642 malloc_func = " in malloc():";
1643 if (malloc_active++) {
1644 malloc_recurse();
1645 return (NULL);
1646 }
1647 r = imalloc(size);
1648 UTRACE(0, size, r);
1649 malloc_active--;
1650 _MALLOC_UNLOCK();
1651 if (malloc_xmalloc && r == NULL) {
1652 wrterror("out of memory\n");
1653 errno = ENOMEM;
1654 }
1655 return (r);
1656}
1657
1658void
1659free(void *ptr)
1660{
1661 _MALLOC_LOCK();
1662 malloc_func = " in free():";
1663 if (malloc_active++) {
1664 malloc_recurse();
1665 return;
1666 }
1667 ifree(ptr);
1668 UTRACE(ptr, 0, 0);
1669 malloc_active--;
1670 _MALLOC_UNLOCK();
1671 return;
1672}
1673
1674void *
1675realloc(void *ptr, size_t size)
1676{
1677 void *r;
1678
1679 _MALLOC_LOCK();
1680 malloc_func = " in realloc():";
1681 if (malloc_active++) {
1682 malloc_recurse();
1683 return (NULL);
1684 }
1685 if (ptr == NULL) {
1686 r = imalloc(size);
1687 } else {
1688 r = irealloc(ptr, size);
1689 }
1690 UTRACE(ptr, size, r);
1691 malloc_active--;
1692 _MALLOC_UNLOCK();
1693 if (malloc_xmalloc && r == NULL) {
1694 wrterror("out of memory\n");
1695 errno = ENOMEM;
1696 }
1697 return (r);
1698}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-05-02 14:31:00 +0000