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.c1263
1 files changed, 1263 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..e75c7cdb09
--- /dev/null
+++ b/src/lib/libc/stdlib/malloc.c
@@ -0,0 +1,1263 @@
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.35 1999/02/03 03:58:05 d 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 <stdio.h>
41#include <stdlib.h>
42#include <string.h>
43#include <unistd.h>
44#include <fcntl.h>
45#include <errno.h>
46#include <sys/types.h>
47#include <sys/param.h>
48#include <sys/mman.h>
49
50/*
51 * The basic parameters you can tweak.
52 *
53 * malloc_pageshift pagesize = 1 << malloc_pageshift
54 * It's probably best if this is the native
55 * page size, but it shouldn't have to be.
56 *
57 * malloc_minsize minimum size of an allocation in bytes.
58 * If this is too small it's too much work
59 * to manage them. This is also the smallest
60 * unit of alignment used for the storage
61 * returned by malloc/realloc.
62 *
63 */
64
65#if defined(__i386__) && defined(__FreeBSD__)
66# define malloc_pageshift 12U
67# define malloc_minsize 16U
68#endif /* __i386__ && __FreeBSD__ */
69
70#if defined(__sparc__) && !defined(__OpenBSD__)
71# define malloc_pageshirt 12U
72# define malloc_minsize 16U
73# define MAP_ANON (0)
74# define USE_DEV_ZERO
75# define MADV_FREE MADV_DONTNEED
76#endif /* __sparc__ */
77
78/* Insert your combination here... */
79#if defined(__FOOCPU__) && defined(__BAROS__)
80# define malloc_pageshift 12U
81# define malloc_minsize 16U
82#endif /* __FOOCPU__ && __BAROS__ */
83
84#if defined(__OpenBSD__) && !defined(__sparc__)
85# define malloc_pageshift (PGSHIFT)
86# define malloc_minsize 16U
87#endif /* __OpenBSD__ */
88
89#ifdef _THREAD_SAFE
90# include "thread_private.h"
91# if 0
92 /* kernel threads */
93# include <pthread.h>
94 static pthread_mutex_t malloc_lock;
95# define THREAD_LOCK() pthread_mutex_lock(&malloc_lock)
96# define THREAD_UNLOCK() pthread_mutex_unlock(&malloc_lock)
97# define THREAD_LOCK_INIT() pthread_mutex_init(&malloc_lock, 0);
98# else
99 /* user threads */
100# include "spinlock.h"
101 static spinlock_t malloc_lock = _SPINLOCK_INITIALIZER;
102# define THREAD_LOCK() if (__isthreaded) _SPINLOCK(&malloc_lock)
103# define THREAD_UNLOCK() if (__isthreaded) _SPINUNLOCK(&malloc_lock)
104# define THREAD_LOCK_INIT()
105 /*
106 * Malloc can't use the wrapped write() if it fails very early, so
107 * we use the unwrapped syscall _thread_sys_write()
108 */
109# define write _thread_sys_write
110 ssize_t write __P((int, const void *, size_t));
111# undef malloc
112# undef realloc
113# undef free
114# endif
115#else
116 /* no threads */
117# define THREAD_LOCK()
118# define THREAD_UNLOCK()
119# define THREAD_LOCK_INIT()
120#endif
121
122/*
123 * No user serviceable parts behind this point.
124 *
125 * This structure describes a page worth of chunks.
126 */
127
128struct pginfo {
129 struct pginfo *next; /* next on the free list */
130 void *page; /* Pointer to the page */
131 u_short size; /* size of this page's chunks */
132 u_short shift; /* How far to shift for this size chunks */
133 u_short free; /* How many free chunks */
134 u_short total; /* How many chunk */
135 u_long bits[1]; /* Which chunks are free */
136};
137
138/*
139 * This structure describes a number of free pages.
140 */
141
142struct pgfree {
143 struct pgfree *next; /* next run of free pages */
144 struct pgfree *prev; /* prev run of free pages */
145 void *page; /* pointer to free pages */
146 void *end; /* pointer to end of free pages */
147 u_long size; /* number of bytes free */
148};
149
150/*
151 * How many bits per u_long in the bitmap.
152 * Change only if not 8 bits/byte
153 */
154#define MALLOC_BITS (8*sizeof(u_long))
155
156/*
157 * Magic values to put in the page_directory
158 */
159#define MALLOC_NOT_MINE ((struct pginfo*) 0)
160#define MALLOC_FREE ((struct pginfo*) 1)
161#define MALLOC_FIRST ((struct pginfo*) 2)
162#define MALLOC_FOLLOW ((struct pginfo*) 3)
163#define MALLOC_MAGIC ((struct pginfo*) 4)
164
165#ifndef malloc_pageshift
166#define malloc_pageshift 12U
167#endif
168
169#ifndef malloc_minsize
170#define malloc_minsize 16U
171#endif
172
173#ifndef malloc_pageshift
174#error "malloc_pageshift undefined"
175#endif
176
177#if !defined(malloc_pagesize)
178#define malloc_pagesize (1UL<<malloc_pageshift)
179#endif
180
181#if ((1UL<<malloc_pageshift) != malloc_pagesize)
182#error "(1UL<<malloc_pageshift) != malloc_pagesize"
183#endif
184
185#ifndef malloc_maxsize
186#define malloc_maxsize ((malloc_pagesize)>>1)
187#endif
188
189/* A mask for the offset inside a page. */
190#define malloc_pagemask ((malloc_pagesize)-1)
191
192#define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
193#define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo)
194
195/* fd of /dev/zero */
196#ifdef USE_DEV_ZERO
197static int fdzero;
198#define MMAP_FD fdzero
199#define INIT_MMAP() \
200 { if ((fdzero=open("/dev/zero", O_RDWR, 0000)) == -1) \
201 wrterror("open of /dev/zero"); }
202#else
203#define MMAP_FD (-1)
204#define INIT_MMAP()
205#endif
206
207/* Set when initialization has been done */
208static unsigned malloc_started;
209
210/* Number of free pages we cache */
211static unsigned malloc_cache = 16;
212
213/* The offset from pagenumber to index into the page directory */
214static u_long malloc_origo;
215
216/* The last index in the page directory we care about */
217static u_long last_index;
218
219/* Pointer to page directory. Allocated "as if with" malloc */
220static struct pginfo **page_dir;
221
222/* How many slots in the page directory */
223static size_t malloc_ninfo;
224
225/* Free pages line up here */
226static struct pgfree free_list;
227
228/* Abort(), user doesn't handle problems. */
229static int malloc_abort;
230
231/* Are we trying to die ? */
232static int suicide;
233
234#ifdef MALLOC_STATS
235/* dump statistics */
236static int malloc_stats;
237#endif
238
239/* avoid outputting warnings? */
240static int malloc_silent;
241
242/* always realloc ? */
243static int malloc_realloc;
244
245#ifdef __FreeBSD__
246/* pass the kernel a hint on free pages ? */
247static int malloc_hint;
248#endif
249
250/* xmalloc behaviour ? */
251static int malloc_xmalloc;
252
253/* zero fill ? */
254static int malloc_zero;
255
256/* junk fill ? */
257static int malloc_junk;
258
259#ifdef __FreeBSD__
260/* utrace ? */
261static int malloc_utrace;
262
263struct ut { void *p; size_t s; void *r; };
264
265void utrace __P((struct ut *, int));
266
267#define UTRACE(a, b, c) \
268 if (malloc_utrace) \
269 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
270#else /* !__FreeBSD__ */
271#define UTRACE(a,b,c)
272#endif
273
274/* my last break. */
275static void *malloc_brk;
276
277/* one location cache for free-list holders */
278static struct pgfree *px;
279
280/* compile-time options */
281char *malloc_options;
282
283/* Name of the current public function */
284static 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 MMAP_FD, (off_t)0);
290
291/*
292 * Necessary function declarations
293 */
294static int extend_pgdir(u_long index);
295static void *imalloc(size_t size);
296static void ifree(void *ptr);
297static void *irealloc(void *ptr, size_t size);
298static void *malloc_bytes(size_t size);
299
300#ifdef MALLOC_STATS
301void
302malloc_dump(fd)
303 FILE *fd;
304{
305 struct pginfo **pd;
306 struct pgfree *pf;
307 int j;
308
309 pd = page_dir;
310
311 /* print out all the pages */
312 for(j=0;j<=last_index;j++) {
313 fprintf(fd, "%08lx %5d ", (j+malloc_origo) << malloc_pageshift, j);
314 if (pd[j] == MALLOC_NOT_MINE) {
315 for(j++;j<=last_index && pd[j] == MALLOC_NOT_MINE;j++)
316 ;
317 j--;
318 fprintf(fd, ".. %5d not mine\n", j);
319 } else if (pd[j] == MALLOC_FREE) {
320 for(j++;j<=last_index && pd[j] == MALLOC_FREE;j++)
321 ;
322 j--;
323 fprintf(fd, ".. %5d free\n", j);
324 } else if (pd[j] == MALLOC_FIRST) {
325 for(j++;j<=last_index && pd[j] == MALLOC_FOLLOW;j++)
326 ;
327 j--;
328 fprintf(fd, ".. %5d in use\n", j);
329 } else if (pd[j] < MALLOC_MAGIC) {
330 fprintf(fd, "(%p)\n", pd[j]);
331 } else {
332 fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n",
333 pd[j], pd[j]->free, pd[j]->total,
334 pd[j]->size, pd[j]->page, pd[j]->next);
335 }
336 }
337
338 for(pf=free_list.next; pf; pf=pf->next) {
339 fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
340 pf, pf->page, pf->end, pf->size, pf->prev, pf->next);
341 if (pf == pf->next) {
342 fprintf(fd, "Free_list loops.\n");
343 break;
344 }
345 }
346
347 /* print out various info */
348 fprintf(fd, "Minsize\t%d\n", malloc_minsize);
349 fprintf(fd, "Maxsize\t%d\n", malloc_maxsize);
350 fprintf(fd, "Pagesize\t%lu\n", (u_long)malloc_pagesize);
351 fprintf(fd, "Pageshift\t%d\n", malloc_pageshift);
352 fprintf(fd, "FirstPage\t%ld\n", malloc_origo);
353 fprintf(fd, "LastPage\t%ld %lx\n", last_index+malloc_pageshift,
354 (last_index + malloc_pageshift) << malloc_pageshift);
355 fprintf(fd, "Break\t%ld\n", (u_long)sbrk(0) >> malloc_pageshift);
356}
357#endif /* MALLOC_STATS */
358
359extern char *__progname;
360
361static void
362wrterror(p)
363 char *p;
364{
365 char *q = " error: ";
366 write(2, __progname, strlen(__progname));
367 write(2, malloc_func, strlen(malloc_func));
368 write(2, q, strlen(q));
369 write(2, p, strlen(p));
370 suicide = 1;
371#ifdef MALLOC_STATS
372 if (malloc_stats)
373 malloc_dump(stderr);
374#endif /* MALLOC_STATS */
375 abort();
376}
377
378static void
379wrtwarning(p)
380 char *p;
381{
382 char *q = " warning: ";
383 if (malloc_abort)
384 wrterror(p);
385 else if (malloc_silent)
386 return;
387 write(2, __progname, strlen(__progname));
388 write(2, malloc_func, strlen(malloc_func));
389 write(2, q, strlen(q));
390 write(2, p, strlen(p));
391}
392
393#ifdef MALLOC_STATS
394static void
395malloc_exit()
396{
397 FILE *fd = fopen("malloc.out", "a");
398 char *q = "malloc() warning: Couldn't dump stats.\n";
399 if (fd) {
400 malloc_dump(fd);
401 fclose(fd);
402 } else
403 write(2, q, strlen(q));
404}
405#endif /* MALLOC_STATS */
406
407
408/*
409 * Allocate a number of pages from the OS
410 */
411static void *
412map_pages(pages)
413 int pages;
414{
415 caddr_t result, tail;
416
417 result = (caddr_t)pageround((u_long)sbrk(0));
418 tail = result + (pages << malloc_pageshift);
419
420 if (brk(tail)) {
421#ifdef MALLOC_EXTRA_SANITY
422 wrterror("(ES): map_pages fails\n");
423#endif /* MALLOC_EXTRA_SANITY */
424 return 0;
425 }
426
427 last_index = ptr2index(tail) - 1;
428 malloc_brk = tail;
429
430 if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index))
431 return 0;
432
433 return result;
434}
435
436/*
437 * Extend page directory
438 */
439static int
440extend_pgdir(index)
441 u_long index;
442{
443 struct pginfo **new, **old;
444 size_t i, oldlen;
445
446 /* Make it this many pages */
447 i = index * sizeof *page_dir;
448 i /= malloc_pagesize;
449 i += 2;
450
451 /* remember the old mapping size */
452 oldlen = malloc_ninfo * sizeof *page_dir;
453
454 /*
455 * NOTE: we allocate new pages and copy the directory rather than tempt
456 * fate by trying to "grow" the region.. There is nothing to prevent
457 * us from accidently re-mapping space that's been allocated by our caller
458 * via dlopen() or other mmap().
459 *
460 * The copy problem is not too bad, as there is 4K of page index per
461 * 4MB of malloc arena.
462 *
463 * We can totally avoid the copy if we open a file descriptor to associate
464 * the anon mappings with. Then, when we remap the pages at the new
465 * address, the old pages will be "magically" remapped.. But this means
466 * keeping open a "secret" file descriptor.....
467 */
468
469 /* Get new pages */
470 new = (struct pginfo**) MMAP(i * malloc_pagesize);
471 if (new == (struct pginfo **)-1)
472 return 0;
473
474 /* Copy the old stuff */
475 memcpy(new, page_dir,
476 malloc_ninfo * sizeof *page_dir);
477
478 /* register the new size */
479 malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
480
481 /* swap the pointers */
482 old = page_dir;
483 page_dir = new;
484
485 /* Now free the old stuff */
486 munmap(old, oldlen);
487 return 1;
488}
489
490/*
491 * Initialize the world
492 */
493static void
494malloc_init ()
495{
496 char *p, b[64];
497 int i, j;
498 int save_errno = errno;
499
500 THREAD_LOCK_INIT();
501
502 INIT_MMAP();
503
504#ifdef MALLOC_EXTRA_SANITY
505 malloc_junk = 1;
506#endif /* MALLOC_EXTRA_SANITY */
507
508 for (i = 0; i < 3; i++) {
509 if (i == 0) {
510 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
511 if (j <= 0)
512 continue;
513 b[j] = '\0';
514 p = b;
515 } else if (i == 1) {
516 if (issetugid() == 0)
517 p = getenv("MALLOC_OPTIONS");
518 else
519 continue;
520 } else if (i == 2) {
521 p = malloc_options;
522 }
523 for (; p && *p; p++) {
524 switch (*p) {
525 case '>': malloc_cache <<= 1; break;
526 case '<': malloc_cache >>= 1; break;
527 case 'a': malloc_abort = 0; break;
528 case 'A': malloc_abort = 1; break;
529#ifdef MALLOC_STATS
530 case 'd': malloc_stats = 0; break;
531 case 'D': malloc_stats = 1; break;
532#endif /* MALLOC_STATS */
533#ifdef __FreeBSD__
534 case 'h': malloc_hint = 0; break;
535 case 'H': malloc_hint = 1; break;
536#endif /* __FreeBSD__ */
537 case 'r': malloc_realloc = 0; break;
538 case 'R': malloc_realloc = 1; break;
539 case 'j': malloc_junk = 0; break;
540 case 'J': malloc_junk = 1; break;
541 case 'n': malloc_silent = 0; break;
542 case 'N': malloc_silent = 1; break;
543#ifdef __FreeBSD__
544 case 'u': malloc_utrace = 0; break;
545 case 'U': malloc_utrace = 1; break;
546#endif /* __FreeBSD__ */
547 case 'x': malloc_xmalloc = 0; break;
548 case 'X': malloc_xmalloc = 1; break;
549 case 'z': malloc_zero = 0; break;
550 case 'Z': malloc_zero = 1; break;
551 default:
552 j = malloc_abort;
553 malloc_abort = 0;
554 wrtwarning("unknown char in MALLOC_OPTIONS\n");
555 malloc_abort = j;
556 break;
557 }
558 }
559 }
560
561 UTRACE(0, 0, 0);
562
563 /*
564 * We want junk in the entire allocation, and zero only in the part
565 * the user asked for.
566 */
567 if (malloc_zero)
568 malloc_junk=1;
569
570#ifdef MALLOC_STATS
571 if (malloc_stats)
572 atexit(malloc_exit);
573#endif /* MALLOC_STATS */
574
575 /* Allocate one page for the page directory */
576 page_dir = (struct pginfo **) MMAP(malloc_pagesize);
577
578 if (page_dir == (struct pginfo **) -1)
579 wrterror("mmap(2) failed, check limits.\n");
580
581 /*
582 * We need a maximum of malloc_pageshift buckets, steal these from the
583 * front of the page_directory;
584 */
585 malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift;
586 malloc_origo -= malloc_pageshift;
587
588 malloc_ninfo = malloc_pagesize / sizeof *page_dir;
589
590 /* Been here, done that */
591 malloc_started++;
592
593 /* Recalculate the cache size in bytes, and make sure it's nonzero */
594
595 if (!malloc_cache)
596 malloc_cache++;
597
598 malloc_cache <<= malloc_pageshift;
599
600 /*
601 * This is a nice hack from Kaleb Keithly (kaleb@x.org).
602 * We can sbrk(2) further back when we keep this on a low address.
603 */
604 px = (struct pgfree *) imalloc (sizeof *px);
605 errno = save_errno;
606}
607
608/*
609 * Allocate a number of complete pages
610 */
611static void *
612malloc_pages(size)
613 size_t size;
614{
615 void *p, *delay_free = 0;
616 int i;
617 struct pgfree *pf;
618 u_long index;
619
620 size = pageround(size);
621
622 p = 0;
623 /* Look for free pages before asking for more */
624 for(pf = free_list.next; pf; pf = pf->next) {
625
626#ifdef MALLOC_EXTRA_SANITY
627 if (pf->size & malloc_pagemask)
628 wrterror("(ES): junk length entry on free_list\n");
629 if (!pf->size)
630 wrterror("(ES): zero length entry on free_list\n");
631 if (pf->page == pf->end)
632 wrterror("(ES): zero entry on free_list\n");
633 if (pf->page > pf->end)
634 wrterror("(ES): sick entry on free_list\n");
635 if ((void*)pf->page >= (void*)sbrk(0))
636 wrterror("(ES): entry on free_list past brk\n");
637 if (page_dir[ptr2index(pf->page)] != MALLOC_FREE)
638 wrterror("(ES): non-free first page on free-list\n");
639 if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE)
640 wrterror("(ES): non-free last page on free-list\n");
641#endif /* MALLOC_EXTRA_SANITY */
642
643 if (pf->size < size)
644 continue;
645
646 if (pf->size == size) {
647 p = pf->page;
648 if (pf->next)
649 pf->next->prev = pf->prev;
650 pf->prev->next = pf->next;
651 delay_free = pf;
652 break;
653 }
654
655 p = pf->page;
656 pf->page = (char *)pf->page + size;
657 pf->size -= size;
658 break;
659 }
660
661#ifdef MALLOC_EXTRA_SANITY
662 if (p && page_dir[ptr2index(p)] != MALLOC_FREE)
663 wrterror("(ES): allocated non-free page on free-list\n");
664#endif /* MALLOC_EXTRA_SANITY */
665
666 size >>= malloc_pageshift;
667
668 /* Map new pages */
669 if (!p)
670 p = map_pages(size);
671
672 if (p) {
673
674 index = ptr2index(p);
675 page_dir[index] = MALLOC_FIRST;
676 for (i=1;i<size;i++)
677 page_dir[index+i] = MALLOC_FOLLOW;
678
679 if (malloc_junk)
680 memset(p, SOME_JUNK, size << malloc_pageshift);
681 }
682
683 if (delay_free) {
684 if (!px)
685 px = delay_free;
686 else
687 ifree(delay_free);
688 }
689
690 return p;
691}
692
693/*
694 * Allocate a page of fragments
695 */
696
697static __inline__ int
698malloc_make_chunks(bits)
699 int bits;
700{
701 struct pginfo *bp;
702 void *pp;
703 int i, k, l;
704
705 /* Allocate a new bucket */
706 pp = malloc_pages((size_t)malloc_pagesize);
707 if (!pp)
708 return 0;
709
710 /* Find length of admin structure */
711 l = sizeof *bp - sizeof(u_long);
712 l += sizeof(u_long) *
713 (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
714
715 /* Don't waste more than two chunks on this */
716 if ((1UL<<(bits)) <= l+l) {
717 bp = (struct pginfo *)pp;
718 } else {
719 bp = (struct pginfo *)imalloc(l);
720 if (!bp) {
721 ifree(pp);
722 return 0;
723 }
724 }
725
726 bp->size = (1UL<<bits);
727 bp->shift = bits;
728 bp->total = bp->free = malloc_pagesize >> bits;
729 bp->page = pp;
730
731 /* set all valid bits in the bitmap */
732 k = bp->total;
733 i = 0;
734
735 /* Do a bunch at a time */
736 for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
737 bp->bits[i / MALLOC_BITS] = ~0UL;
738
739 for(; i < k; i++)
740 bp->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS);
741
742 if (bp == bp->page) {
743 /* Mark the ones we stole for ourselves */
744 for(i=0;l > 0;i++) {
745 bp->bits[i/MALLOC_BITS] &= ~(1UL<<(i%MALLOC_BITS));
746 bp->free--;
747 bp->total--;
748 l -= (1 << bits);
749 }
750 }
751
752 /* MALLOC_LOCK */
753
754 page_dir[ptr2index(pp)] = bp;
755
756 bp->next = page_dir[bits];
757 page_dir[bits] = bp;
758
759 /* MALLOC_UNLOCK */
760
761 return 1;
762}
763
764/*
765 * Allocate a fragment
766 */
767static void *
768malloc_bytes(size)
769 size_t size;
770{
771 int i,j;
772 u_long u;
773 struct pginfo *bp;
774 int k;
775 u_long *lp;
776
777 /* Don't bother with anything less than this */
778 if (size < malloc_minsize)
779 size = malloc_minsize;
780
781 /* Find the right bucket */
782 j = 1;
783 i = size-1;
784 while (i >>= 1)
785 j++;
786
787 /* If it's empty, make a page more of that size chunks */
788 if (!page_dir[j] && !malloc_make_chunks(j))
789 return 0;
790
791 bp = page_dir[j];
792
793 /* Find first word of bitmap which isn't empty */
794 for (lp = bp->bits; !*lp; lp++)
795 ;
796
797 /* Find that bit, and tweak it */
798 u = 1;
799 k = 0;
800 while (!(*lp & u)) {
801 u += u;
802 k++;
803 }
804 *lp ^= u;
805
806 /* If there are no more free, remove from free-list */
807 if (!--bp->free) {
808 page_dir[j] = bp->next;
809 bp->next = 0;
810 }
811
812 /* Adjust to the real offset of that chunk */
813 k += (lp-bp->bits)*MALLOC_BITS;
814 k <<= bp->shift;
815
816 if (malloc_junk)
817 memset((char *)bp->page + k, SOME_JUNK, bp->size);
818
819 return (u_char *)bp->page + k;
820}
821
822/*
823 * Allocate a piece of memory
824 */
825static void *
826imalloc(size)
827 size_t size;
828{
829 void *result;
830
831 if (!malloc_started)
832 malloc_init();
833
834 if (suicide)
835 abort();
836
837 if ((size + malloc_pagesize) < size) /* Check for overflow */
838 result = 0;
839 else if (size <= malloc_maxsize)
840 result = malloc_bytes(size);
841 else
842 result = malloc_pages(size);
843
844 if (malloc_abort && !result)
845 wrterror("allocation failed.\n");
846
847 if (malloc_zero && result)
848 memset(result, 0, size);
849
850 return result;
851}
852
853/*
854 * Change the size of an allocation.
855 */
856static void *
857irealloc(ptr, size)
858 void *ptr;
859 size_t size;
860{
861 void *p;
862 u_long osize, index;
863 struct pginfo **mp;
864 int i;
865
866 if (suicide)
867 abort();
868
869 if (!malloc_started) {
870 wrtwarning("malloc() has never been called.\n");
871 return 0;
872 }
873
874 index = ptr2index(ptr);
875
876 if (index < malloc_pageshift) {
877 wrtwarning("junk pointer, too low to make sense.\n");
878 return 0;
879 }
880
881 if (index > last_index) {
882 wrtwarning("junk pointer, too high to make sense.\n");
883 return 0;
884 }
885
886 mp = &page_dir[index];
887
888 if (*mp == MALLOC_FIRST) { /* Page allocation */
889
890 /* Check the pointer */
891 if ((u_long)ptr & malloc_pagemask) {
892 wrtwarning("modified (page-) pointer.\n");
893 return 0;
894 }
895
896 /* Find the size in bytes */
897 for (osize = malloc_pagesize; *++mp == MALLOC_FOLLOW;)
898 osize += malloc_pagesize;
899
900 if (!malloc_realloc && /* unless we have to, */
901 size <= osize && /* .. or are too small, */
902 size > (osize - malloc_pagesize)) { /* .. or can free a page, */
903 return ptr; /* don't do anything. */
904 }
905
906 } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */
907
908 /* Check the pointer for sane values */
909 if (((u_long)ptr & ((*mp)->size-1))) {
910 wrtwarning("modified (chunk-) pointer.\n");
911 return 0;
912 }
913
914 /* Find the chunk index in the page */
915 i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
916
917 /* Verify that it isn't a free chunk already */
918 if ((*mp)->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
919 wrtwarning("chunk is already free.\n");
920 return 0;
921 }
922
923 osize = (*mp)->size;
924
925 if (!malloc_realloc && /* Unless we have to, */
926 size < osize && /* ..or are too small, */
927 (size > osize/2 || /* ..or could use a smaller size, */
928 osize == malloc_minsize)) { /* ..(if there is one) */
929 return ptr; /* ..Don't do anything */
930 }
931
932 } else {
933 wrtwarning("pointer to wrong page.\n");
934 return 0;
935 }
936
937 p = imalloc(size);
938
939 if (p) {
940 /* copy the lesser of the two sizes, and free the old one */
941 if (osize < size)
942 memcpy(p, ptr, osize);
943 else
944 memcpy(p, ptr, size);
945 ifree(ptr);
946 }
947 return p;
948}
949
950/*
951 * Free a sequence of pages
952 */
953
954static __inline__ void
955free_pages(ptr, index, info)
956 void *ptr;
957 int index;
958 struct pginfo *info;
959{
960 int i;
961 struct pgfree *pf, *pt=0;
962 u_long l;
963 void *tail;
964
965 if (info == MALLOC_FREE) {
966 wrtwarning("page is already free.\n");
967 return;
968 }
969
970 if (info != MALLOC_FIRST) {
971 wrtwarning("pointer to wrong page.\n");
972 return;
973 }
974
975 if ((u_long)ptr & malloc_pagemask) {
976 wrtwarning("modified (page-) pointer.\n");
977 return;
978 }
979
980 /* Count how many pages and mark them free at the same time */
981 page_dir[index] = MALLOC_FREE;
982 for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
983 page_dir[index + i] = MALLOC_FREE;
984
985 l = i << malloc_pageshift;
986
987 if (malloc_junk)
988 memset(ptr, SOME_JUNK, l);
989
990#ifdef __FreeBSD__
991 if (malloc_hint)
992 madvise(ptr, l, MADV_FREE);
993#endif
994
995 tail = (char *)ptr+l;
996
997 /* add to free-list */
998 if (!px)
999 px = imalloc(sizeof *px); /* This cannot fail... */
1000 px->page = ptr;
1001 px->end = tail;
1002 px->size = l;
1003 if (!free_list.next) {
1004
1005 /* Nothing on free list, put this at head */
1006 px->next = free_list.next;
1007 px->prev = &free_list;
1008 free_list.next = px;
1009 pf = px;
1010 px = 0;
1011
1012 } else {
1013
1014 /* Find the right spot, leave pf pointing to the modified entry. */
1015 tail = (char *)ptr+l;
1016
1017 for(pf = free_list.next; pf->end < ptr && pf->next; pf = pf->next)
1018 ; /* Race ahead here */
1019
1020 if (pf->page > tail) {
1021 /* Insert before entry */
1022 px->next = pf;
1023 px->prev = pf->prev;
1024 pf->prev = px;
1025 px->prev->next = px;
1026 pf = px;
1027 px = 0;
1028 } else if (pf->end == ptr ) {
1029 /* Append to the previous entry */
1030 pf->end = (char *)pf->end + l;
1031 pf->size += l;
1032 if (pf->next && pf->end == pf->next->page ) {
1033 /* And collapse the next too. */
1034 pt = pf->next;
1035 pf->end = pt->end;
1036 pf->size += pt->size;
1037 pf->next = pt->next;
1038 if (pf->next)
1039 pf->next->prev = pf;
1040 }
1041 } else if (pf->page == tail) {
1042 /* Prepend to entry */
1043 pf->size += l;
1044 pf->page = ptr;
1045 } else if (!pf->next) {
1046 /* Append at tail of chain */
1047 px->next = 0;
1048 px->prev = pf;
1049 pf->next = px;
1050 pf = px;
1051 px = 0;
1052 } else {
1053 wrterror("freelist is destroyed.\n");
1054 }
1055 }
1056
1057 /* Return something to OS ? */
1058 if (!pf->next && /* If we're the last one, */
1059 pf->size > malloc_cache && /* ..and the cache is full, */
1060 pf->end == malloc_brk && /* ..and none behind us, */
1061 malloc_brk == sbrk(0)) { /* ..and it's OK to do... */
1062
1063 /*
1064 * Keep the cache intact. Notice that the '>' above guarantees that
1065 * the pf will always have at least one page afterwards.
1066 */
1067 pf->end = (char *)pf->page + malloc_cache;
1068 pf->size = malloc_cache;
1069
1070 brk(pf->end);
1071 malloc_brk = pf->end;
1072
1073 index = ptr2index(pf->end);
1074 last_index = index - 1;
1075
1076 for(i=index;i <= last_index;)
1077 page_dir[i++] = MALLOC_NOT_MINE;
1078
1079 /* XXX: We could realloc/shrink the pagedir here I guess. */
1080 }
1081 if (pt)
1082 ifree(pt);
1083}
1084
1085/*
1086 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1087 */
1088
1089/* ARGSUSED */
1090static __inline__ void
1091free_bytes(ptr, index, info)
1092 void *ptr;
1093 int index;
1094 struct pginfo *info;
1095{
1096 int i;
1097 struct pginfo **mp;
1098 void *vp;
1099
1100 /* Find the chunk number on the page */
1101 i = ((u_long)ptr & malloc_pagemask) >> info->shift;
1102
1103 if (((u_long)ptr & (info->size-1))) {
1104 wrtwarning("modified (chunk-) pointer.\n");
1105 return;
1106 }
1107
1108 if (info->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
1109 wrtwarning("chunk is already free.\n");
1110 return;
1111 }
1112
1113 if (malloc_junk)
1114 memset(ptr, SOME_JUNK, info->size);
1115
1116 info->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS);
1117 info->free++;
1118
1119 mp = page_dir + info->shift;
1120
1121 if (info->free == 1) {
1122
1123 /* Page became non-full */
1124
1125 mp = page_dir + info->shift;
1126 /* Insert in address order */
1127 while (*mp && (*mp)->next && (*mp)->next->page < info->page)
1128 mp = &(*mp)->next;
1129 info->next = *mp;
1130 *mp = info;
1131 return;
1132 }
1133
1134 if (info->free != info->total)
1135 return;
1136
1137 /* Find & remove this page in the queue */
1138 while (*mp != info) {
1139 mp = &((*mp)->next);
1140#ifdef MALLOC_EXTRA_SANITY
1141 if (!*mp)
1142 wrterror("(ES): Not on queue\n");
1143#endif /* MALLOC_EXTRA_SANITY */
1144 }
1145 *mp = info->next;
1146
1147 /* Free the page & the info structure if need be */
1148 page_dir[ptr2index(info->page)] = MALLOC_FIRST;
1149 vp = info->page; /* Order is important ! */
1150 if(vp != (void*)info)
1151 ifree(info);
1152 ifree(vp);
1153}
1154
1155static void
1156ifree(ptr)
1157 void *ptr;
1158{
1159 struct pginfo *info;
1160 int index;
1161
1162 /* This is legal */
1163 if (!ptr)
1164 return;
1165
1166 if (!malloc_started) {
1167 wrtwarning("malloc() has never been called.\n");
1168 return;
1169 }
1170
1171 /* If we're already sinking, don't make matters any worse. */
1172 if (suicide)
1173 return;
1174
1175 index = ptr2index(ptr);
1176
1177 if (index < malloc_pageshift) {
1178 wrtwarning("junk pointer, too low to make sense.\n");
1179 return;
1180 }
1181
1182 if (index > last_index) {
1183 wrtwarning("junk pointer, too high to make sense.\n");
1184 return;
1185 }
1186
1187 info = page_dir[index];
1188
1189 if (info < MALLOC_MAGIC)
1190 free_pages(ptr, index, info);
1191 else
1192 free_bytes(ptr, index, info);
1193 return;
1194}
1195
1196/*
1197 * These are the public exported interface routines.
1198 */
1199
1200static int malloc_active;
1201
1202void *
1203malloc(size_t size)
1204{
1205 register void *r;
1206
1207 malloc_func = " in malloc():";
1208 THREAD_LOCK();
1209 if (malloc_active++) {
1210 wrtwarning("recursive call.\n");
1211 malloc_active--;
1212 return (0);
1213 }
1214 r = imalloc(size);
1215 UTRACE(0, size, r);
1216 malloc_active--;
1217 THREAD_UNLOCK();
1218 if (malloc_xmalloc && !r)
1219 wrterror("out of memory.\n");
1220 return (r);
1221}
1222
1223void
1224free(void *ptr)
1225{
1226 malloc_func = " in free():";
1227 THREAD_LOCK();
1228 if (malloc_active++) {
1229 wrtwarning("recursive call.\n");
1230 malloc_active--;
1231 return;
1232 }
1233 ifree(ptr);
1234 UTRACE(ptr, 0, 0);
1235 malloc_active--;
1236 THREAD_UNLOCK();
1237 return;
1238}
1239
1240void *
1241realloc(void *ptr, size_t size)
1242{
1243 register void *r;
1244
1245 malloc_func = " in realloc():";
1246 THREAD_LOCK();
1247 if (malloc_active++) {
1248 wrtwarning("recursive call.\n");
1249 malloc_active--;
1250 return (0);
1251 }
1252 if (!ptr) {
1253 r = imalloc(size);
1254 } else {
1255 r = irealloc(ptr, size);
1256 }
1257 UTRACE(ptr, size, r);
1258 malloc_active--;
1259 THREAD_UNLOCK();
1260 if (malloc_xmalloc && !r)
1261 wrterror("out of memory.\n");
1262 return (r);
1263}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-08 10:44:08 +0000