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