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.c1979
1 files changed, 1628 insertions, 351 deletions
diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
index 3c57fad024..ae89f5d72b 100644
--- a/src/lib/libc/stdlib/malloc.c
+++ b/src/lib/libc/stdlib/malloc.c
@@ -1,421 +1,1698 @@
1/* 1/*
2 * Copyright (c) 1983 Regents of the University of California. 2 * ----------------------------------------------------------------------------
3 * All rights reserved. 3 * "THE BEER-WARE LICENSE" (Revision 42):
4 * 4 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
5 * Redistribution and use in source and binary forms, with or without 5 * can do whatever you want with this stuff. If we meet some day, and you think
6 * modification, are permitted provided that the following conditions 6 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
7 * are met: 7 * ----------------------------------------------------------------------------
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */ 8 */
33 9
34#if defined(LIBC_SCCS) && !defined(lint) 10#if defined(LIBC_SCCS) && !defined(lint)
35/*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/ 11static char rcsid[] = "$OpenBSD: malloc.c,v 1.72 2005/03/31 21:24:46 tdeval Exp $";
36static char *rcsid = "$Id: malloc.c,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $";
37#endif /* LIBC_SCCS and not lint */ 12#endif /* LIBC_SCCS and not lint */
38 13
39/* 14/*
40 * malloc.c (Caltech) 2/21/82 15 * Defining MALLOC_EXTRA_SANITY will enable extra checks which are
41 * Chris Kingsley, kingsley@cit-20. 16 * related to internal conditions and consistency in malloc.c. This has
42 * 17 * a noticeable runtime performance hit, and generally will not do you
43 * This is a very fast storage allocator. It allocates blocks of a small 18 * any good unless you fiddle with the internals of malloc or want
44 * number of different sizes, and keeps free lists of each size. Blocks that 19 * to catch random pointer corruption as early as possible.
45 * don't exactly fit are passed up to the next larger size. In this
46 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
47 * This is designed for use in a virtual memory environment.
48 */ 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" :-) */
49 39
50#include <sys/types.h> 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>
51#include <stdlib.h> 47#include <stdlib.h>
52#include <string.h> 48#include <string.h>
53#include <unistd.h> 49#include <unistd.h>
50#include <fcntl.h>
51#include <limits.h>
52#include <errno.h>
54 53
55#define NULL 0 54#include "thread_private.h"
56 55
57static void morecore(); 56/*
58static int findbucket(); 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__ */
59 74
60/* 75/*
61 * The overhead on a block is at least 4 bytes. When free, this space 76 * No user serviceable parts behind this point.
62 * contains a pointer to the next free block, and the bottom two bits must 77 *
63 * be zero. When in use, the first byte is set to MAGIC, and the second 78 * This structure describes a page worth of chunks.
64 * byte is the size index. The remaining bytes are for alignment.
65 * If range checking is enabled then a second word holds the size of the
66 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
67 * The order of elements is critical: ov_magic must overlay the low order
68 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
69 */ 79 */
70union overhead { 80
71 union overhead *ov_next; /* when free */ 81struct pginfo {
72 struct { 82 struct pginfo *next; /* next on the free list */
73 u_char ovu_magic; /* magic number */ 83 void *page; /* Pointer to the page */
74 u_char ovu_index; /* bucket # */ 84 u_short size; /* size of this page's chunks */
75#ifdef RCHECK 85 u_short shift; /* How far to shift for this size chunks */
76 u_short ovu_rmagic; /* range magic number */ 86 u_short free; /* How many free chunks */
77 u_long ovu_size; /* actual block size */ 87 u_short total; /* How many chunk */
78#endif 88 u_long bits[1]; /* Which chunks are free */
79 } ovu;
80#define ov_magic ovu.ovu_magic
81#define ov_index ovu.ovu_index
82#define ov_rmagic ovu.ovu_rmagic
83#define ov_size ovu.ovu_size
84}; 89};
85 90
86#define MAGIC 0xef /* magic # on accounting info */ 91/*
87#define RMAGIC 0x5555 /* magic # on range info */ 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};
88 102
89#ifdef RCHECK 103/*
90#define RSLOP sizeof (u_short) 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"); }
91#else 155#else
92#define RSLOP 0 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;
93#endif 201#endif
94 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
95/* 267/*
96 * nextf[i] is the pointer to the next free block of size 2^(i+3). The 268 * Necessary function declarations.
97 * smallest allocatable block is 8 bytes. The overhead information
98 * precedes the data area returned to the user.
99 */ 269 */
100#define NBUCKETS 30 270static void *imalloc(size_t size);
101static union overhead *nextf[NBUCKETS]; 271static void ifree(void *ptr);
102extern char *sbrk(); 272static void *irealloc(void *ptr, size_t size);
273static void *malloc_bytes(size_t size);
103 274
104static int pagesz; /* page size */
105static int pagebucket; /* page size bucket */
106 275
107#ifdef MSTATS
108/* 276/*
109 * nmalloc[i] is the difference between the number of mallocs and frees 277 * Function for page directory lookup.
110 * for a given block size.
111 */ 278 */
112static u_int nmalloc[NBUCKETS]; 279static int
113#include <stdio.h> 280pdir_lookup(u_long index, struct pdinfo **pdi)
114#endif
115
116#if defined(DEBUG) || defined(RCHECK)
117#define ASSERT(p) if (!(p)) botch("p")
118#include <stdio.h>
119static
120botch(s)
121 char *s;
122{ 281{
123 fprintf(stderr, "\r\nassertion botched: %s\r\n", s); 282 struct pdinfo *spi;
124 (void) fflush(stderr); /* just in case user buffered it */ 283 u_long pidx = PI_IDX(index);
125 abort(); 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);
126} 315}
127#else
128#define ASSERT(p)
129#endif
130 316
131void * 317
132malloc(nbytes) 318#ifdef MALLOC_STATS
133 size_t nbytes; 319void
320malloc_dump(FILE *fd)
134{ 321{
135 register union overhead *op; 322 struct pginfo **pd;
136 register long bucket, n; 323 struct pgfree *pf;
137 register unsigned amt; 324 struct pdinfo *pi;
325 int j;
138 326
139 /* 327 pd = page_dir;
140 * First time malloc is called, setup page size and 328 pi = (struct pdinfo *)((caddr_t)pd + pdi_off);
141 * align break pointer so all data will be page aligned. 329
142 */ 330 /* print out all the pages */
143 if (pagesz == 0) { 331 for(j=0;j<=last_index;) {
144 pagesz = n = getpagesize(); 332 fprintf(fd, "%08lx %5d ", j << malloc_pageshift, j);
145 op = (union overhead *)sbrk(0); 333 if (pd[PI_OFF(j)] == MALLOC_NOT_MINE) {
146 n = n - sizeof (*op) - ((long)op & (n - 1)); 334 for(j++;j<=last_index && pd[PI_OFF(j)] == MALLOC_NOT_MINE;) {
147 if (n < 0) 335 if (!PI_OFF(++j)) {
148 n += pagesz; 336 if ((pi = pi->next) == NULL ||
149 if (n) { 337 PD_IDX(pi->dirnum) != PI_IDX(j)) break;
150 if (sbrk(n) == (char *)-1) 338 pd = pi->base;
151 return (NULL); 339 j += pdi_mod;
152 } 340 }
153 bucket = 0; 341 }
154 amt = 8; 342 j--;
155 while (pagesz > amt) { 343 fprintf(fd, ".. %5d not mine\n", j);
156 amt <<= 1; 344 } else if (pd[PI_OFF(j)] == MALLOC_FREE) {
157 bucket++; 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;
158 } 351 }
159 pagebucket = bucket; 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);
160 } 372 }
161 /* 373 if (!PI_OFF(++j)) {
162 * Convert amount of memory requested into closest block size 374 if ((pi = pi->next) == NULL)
163 * stored in hash buckets which satisfies request. 375 break;
164 * Account for space used per block for accounting. 376 pd = pi->base;
165 */ 377 j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod;
166 if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { 378 }
167#ifndef RCHECK 379 }
168 amt = 8; /* size of first bucket */ 380
169 bucket = 0; 381 for(pf=free_list.next; pf; pf=pf->next) {
170#else 382 fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
171 amt = 16; /* size of first bucket */ 383 pf, pf->page, pf->page + pf->size, pf->size,
172 bucket = 1; 384 pf->prev, pf->next);
173#endif 385 if (pf == pf->next) {
174 n = -((long)sizeof (*op) + RSLOP); 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 }
175 } else { 530 } else {
176 amt = pagesz; 531 pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1;
177 bucket = pagebucket;
178 } 532 }
179 while (nbytes > amt + n) { 533#ifdef MALLOC_EXTRA_SANITY
180 amt <<= 1; 534 if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > index) {
181 if (amt == 0) 535 wrterror("(ES): pages directory overflow\n");
182 return (NULL); 536 errno = EFAULT;
183 bucket++; 537 return (NULL);
184 } 538 }
185 /* 539#endif /* MALLOC_EXTRA_SANITY */
186 * If nothing in hash bucket right now, 540 if (index == pidx && pi != last_dir) {
187 * request more memory from the system. 541 prev_dir = last_dir;
188 */ 542 last_dir = pi;
189 if ((op = nextf[bucket]) == NULL) { 543 }
190 morecore(bucket); 544 spi = pi;
191 if ((op = nextf[bucket]) == NULL) 545 pi = spi->next;
192 return (NULL); 546 }
193 } 547
194 /* remove from linked list */ 548 return (result);
195 nextf[bucket] = op->ov_next;
196 op->ov_magic = MAGIC;
197 op->ov_index = bucket;
198#ifdef MSTATS
199 nmalloc[bucket]++;
200#endif
201#ifdef RCHECK
202 /*
203 * Record allocated size of block and
204 * bound space with magic numbers.
205 */
206 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
207 op->ov_rmagic = RMAGIC;
208 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
209#endif
210 return ((char *)(op + 1));
211} 549}
212 550
551
213/* 552/*
214 * Allocate more memory to the indicated bucket. 553 * Initialize the world
215 */ 554 */
216static void 555static void
217morecore(bucket) 556malloc_init(void)
218 int bucket;
219{ 557{
220 register union overhead *op; 558 char *p, b[64];
221 register long sz; /* size of desired block */ 559 int i, j;
222 long amt; /* amount to allocate */ 560 int save_errno = errno;
223 int nblks; /* how many blocks we get */
224 561
225 /* 562 _MALLOC_LOCK_INIT();
226 * sbrk_size <= 0 only for big, FLUFFY, requests (about 563
227 * 2^30 bytes on a VAX, I think) or for a negative arg. 564 INIT_MMAP();
228 */ 565
229 sz = 1 << (bucket + 3); 566#ifdef MALLOC_EXTRA_SANITY
230#ifdef DEBUG 567 malloc_junk = 1;
231 ASSERT(sz > 0); 568#endif /* MALLOC_EXTRA_SANITY */
232#else 569
233 if (sz <= 0) 570 for (i = 0; i < 3; i++) {
234 return; 571 switch (i) {
235#endif 572 case 0:
236 if (sz < pagesz) { 573 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
237 amt = pagesz; 574 if (j <= 0)
238 nblks = amt / sz; 575 continue;
239 } else { 576 b[j] = '\0';
240 amt = sz + pagesz; 577 p = b;
241 nblks = 1; 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;
242 } 592 }
243 op = (union overhead *)sbrk(amt); 593 for (; p != NULL && *p != '\0'; p++) {
244 /* no more room! */ 594 switch (*p) {
245 if ((long)op == -1) 595 case '>': malloc_cache <<= 1; break;
246 return; 596 case '<': malloc_cache >>= 1; break;
247 /* 597 case 'a': malloc_abort = 0; break;
248 * Add new memory allocated to that on 598 case 'A': malloc_abort = 1; break;
249 * free list for this hash bucket. 599#ifdef MALLOC_STATS
250 */ 600 case 'd': malloc_stats = 0; break;
251 nextf[bucket] = op; 601 case 'D': malloc_stats = 1; break;
252 while (--nblks > 0) { 602#endif /* MALLOC_STATS */
253 op->ov_next = (union overhead *)((caddr_t)op + sz); 603 case 'f': malloc_freeprot = 0; break;
254 op = (union overhead *)((caddr_t)op + sz); 604 case 'F': malloc_freeprot = 1; break;
255 } 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;
256} 677}
257 678
258void 679/*
259free(cp) 680 * Allocate a number of complete pages
260 void *cp; 681 */
261{ 682static void *
262 register long size; 683malloc_pages(size_t size)
263 register union overhead *op; 684{
264 685 void *p, *delay_free = NULL;
265 if (cp == NULL) 686 int i;
266 return; 687 struct rlimit rl;
267 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 688 struct pginfo **pd;
268#ifdef DEBUG 689 struct pdinfo *pi;
269 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 690 u_long pidx;
270#else 691 void *tp;
271 if (op->ov_magic != MAGIC) 692 struct pgfree *pf;
272 return; /* sanity */ 693 u_long index;
273#endif 694 int m;
274#ifdef RCHECK 695
275 ASSERT(op->ov_rmagic == RMAGIC); 696 size = pageround(size) + malloc_guard;
276 ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 697
277#endif 698 p = NULL;
278 size = op->ov_index; 699 /* Look for free pages before asking for more */
279 ASSERT(size < NBUCKETS); 700 for (pf = free_list.next; pf; pf = pf->next) {
280 op->ov_next = nextf[size]; /* also clobbers ov_magic */ 701
281 nextf[size] = op; 702#ifdef MALLOC_EXTRA_SANITY
282#ifdef MSTATS 703 if (pf->size & malloc_pagemask) {
283 nmalloc[size]--; 704 wrterror("(ES): junk length entry on free_list\n");
284#endif 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);
285} 864}
286 865
287/* 866/*
288 * When a program attempts "storage compaction" as mentioned in the 867 * Allocate a page of fragments
289 * old malloc man page, it realloc's an already freed block. Usually
290 * this is the last block it freed; occasionally it might be farther
291 * back. We have to search all the free lists for the block in order
292 * to determine its bucket: 1st we make one pass thru the lists
293 * checking only the first block in each; if that fails we search
294 * ``realloc_srchlen'' blocks in each list for a match (the variable
295 * is extern so the caller can modify it). If that fails we just copy
296 * however many bytes was given to realloc() and hope it's not huge.
297 */ 868 */
298int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
299 869
300void * 870static __inline__ int
301realloc(cp, nbytes) 871malloc_make_chunks(int bits)
302 void *cp; 872{
303 size_t nbytes; 873 struct pginfo *bp;
304{ 874 struct pginfo **pd;
305 register u_long onb; 875 struct pdinfo *pi;
306 register long i; 876 u_long pidx;
307 union overhead *op; 877 void *pp;
308 char *res; 878 int i, k, l;
309 int was_alloced = 0; 879
310 880 /* Allocate a new bucket */
311 if (cp == NULL) 881 pp = malloc_pages((size_t)malloc_pagesize);
312 return (malloc(nbytes)); 882 if (pp == NULL)
313 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 883 return (0);
314 if (op->ov_magic == MAGIC) { 884
315 was_alloced++; 885 /* Find length of admin structure */
316 i = op->ov_index; 886 l = sizeof *bp - sizeof(u_long);
317 } else { 887 l += sizeof(u_long) *
318 /* 888 (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
319 * Already free, doing "compaction". 889
320 * 890 /* Don't waste more than two chunks on this */
321 * Search for the old block of memory on the 891 /*
322 * free list. First, check the most common 892 * If we are to allocate a memory protected page for the malloc(0)
323 * case (last element free'd), then (this failing) 893 * case (when bits=0), it must be from a different page than the
324 * the last ``realloc_srchlen'' items free'd. 894 * pginfo page.
325 * If all lookups fail, then assume the size of 895 * --> Treat it like the big chunk alloc, get a second data page.
326 * the memory block being realloc'd is the 896 */
327 * largest possible (so that all "nbytes" of new 897 if (bits != 0 && (1UL<<(bits)) <= l+l) {
328 * memory are copied into). Note that this could cause 898 bp = (struct pginfo *)pp;
329 * a memory fault if the old area was tiny, and the moon 899 } else {
330 * is gibbous. However, that is very unlikely. 900 bp = (struct pginfo *)imalloc(l);
331 */ 901 if (bp == NULL) {
332 if ((i = findbucket(op, 1)) < 0 && 902 ifree(pp);
333 (i = findbucket(op, realloc_srchlen)) < 0) 903 return (0);
334 i = NBUCKETS; 904 }
335 } 905 }
336 onb = 1 << (i + 3); 906
337 if (onb < pagesz) 907 /* memory protect the page allocated in the malloc(0) case */
338 onb -= sizeof (*op) + RSLOP; 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;
339 else 1282 else
340 onb += pagesz - sizeof (*op) - RSLOP; 1283 pd = pi->base;
341 /* avoid the copy if same size block */ 1284 }
342 if (was_alloced) { 1285 while (pi != NULL && pd[PI_OFF(index+i)] == MALLOC_FOLLOW) {
343 if (i) { 1286 pd[PI_OFF(index+i)] = MALLOC_FREE;
344 i = 1 << (i + 2); 1287 i++;
345 if (i < pagesz) 1288 if (!PI_OFF(index+i)) {
346 i -= sizeof (*op) + RSLOP; 1289 if ((pi=pi->next) == NULL || PD_IDX(pi->dirnum) != PI_IDX(index+i))
347 else 1290 pi = NULL;
348 i += pagesz - sizeof (*op) - RSLOP; 1291 else
349 } 1292 pd = pi->base;
350 if (nbytes <= onb && nbytes > i) { 1293 }
351#ifdef RCHECK 1294 }
352 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 1295
353 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 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);
354#endif 1318#endif
355 return(cp); 1319
356 } else 1320 if (malloc_freeprot)
357 free(cp); 1321 mprotect(ptr, l, PROT_NONE);
358 } 1322
359 if ((res = malloc(nbytes)) == NULL) 1323 /* Add to free-list. */
360 return (NULL); 1324 if (px == NULL)
361 if (cp != res) /* common optimization if "compacting" */ 1325 px = imalloc(sizeof *px); /* This cannot fail... */
362 bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 1326 px->page = ptr;
363 return (res); 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);
364} 1456}
365 1457
366/* 1458/*
367 * Search ``srchlen'' elements of each free list for a block whose 1459 * Free a chunk, and possibly the page it's on, if the page becomes empty.
368 * header starts at ``freep''. If srchlen is -1 search the whole list.
369 * Return bucket number, or -1 if not found.
370 */ 1460 */
371static 1461
372findbucket(freep, srchlen) 1462/* ARGSUSED */
373 union overhead *freep; 1463static __inline__ void
374 int srchlen; 1464free_bytes(void *ptr, int index, struct pginfo *info)
375{ 1465{
376 register union overhead *p; 1466 int i;
377 register int i, j; 1467 struct pginfo **mp;
378 1468 struct pginfo **pd;
379 for (i = 0; i < NBUCKETS; i++) { 1469 struct pdinfo *pi;
380 j = 0; 1470 u_long pidx;
381 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 1471 void *vp;
382 if (p == freep) 1472
383 return (i); 1473 /* Find the chunk number on the page */
384 j++; 1474 i = ((u_long)ptr & malloc_pagemask) >> info->shift;
385 } 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;
386 } 1521 }
387 return (-1); 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;
388} 1612}
389 1613
390#ifdef MSTATS
391/* 1614/*
392 * mstats - print out statistics about malloc 1615 * Common function for handling recursion. Only
393 * 1616 * print the error message once, to avoid making the problem
394 * Prints two lines of numbers, one showing the length of the free list 1617 * potentially worse.
395 * for each size category, the second showing the number of mallocs -
396 * frees for each size category.
397 */ 1618 */
398mstats(s) 1619static void
399 char *s; 1620malloc_recurse(void)
400{ 1621{
401 register int i, j; 1622 static int noprint;
402 register union overhead *p; 1623
403 int totfree = 0, 1624 if (noprint == 0) {
404 totused = 0; 1625 noprint = 1;
405 1626 wrtwarning("recursive call\n");
406 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 1627 }
407 for (i = 0; i < NBUCKETS; i++) { 1628 malloc_active--;
408 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 1629 _MALLOC_UNLOCK();
409 ; 1630 errno = EDEADLK;
410 fprintf(stderr, " %d", j); 1631}
411 totfree += j * (1 << (i + 3)); 1632
412 } 1633/*
413 fprintf(stderr, "\nused:\t"); 1634 * These are the public exported interface routines.
414 for (i = 0; i < NBUCKETS; i++) { 1635 */
415 fprintf(stderr, " %d", nmalloc[i]); 1636void *
416 totused += nmalloc[i] * (1 << (i + 3)); 1637malloc(size_t size)
417 } 1638{
418 fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 1639 void *r;
419 totused, totfree); 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);
420} 1698}
421#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-05-01 19:51:22 +0000