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.c1673
1 files changed, 1325 insertions, 348 deletions
diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
index 3c57fad024..be80640e81 100644
--- a/src/lib/libc/stdlib/malloc.c
+++ b/src/lib/libc/stdlib/malloc.c
@@ -1,421 +1,1398 @@
1/* $OpenBSD: malloc.c,v 1.98 2008/08/25 17:56:17 otto Exp $ */
1/* 2/*
2 * Copyright (c) 1983 Regents of the University of California. 3 * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net>
3 * All rights reserved.
4 * 4 *
5 * Redistribution and use in source and binary forms, with or without 5 * Permission to use, copy, modify, and distribute this software for any
6 * modification, are permitted provided that the following conditions 6 * purpose with or without fee is hereby granted, provided that the above
7 * are met: 7 * copyright notice and this permission notice appear in all copies.
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 * 8 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
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 */ 16 */
33 17
34#if defined(LIBC_SCCS) && !defined(lint)
35/*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/
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 */
38
39/* 18/*
40 * malloc.c (Caltech) 2/21/82 19 * Parts of this code, mainly the sub page sized chunk management code is
41 * Chris Kingsley, kingsley@cit-20. 20 * derived from the malloc implementation with the following license:
42 * 21 */
43 * This is a very fast storage allocator. It allocates blocks of a small 22/*
44 * number of different sizes, and keeps free lists of each size. Blocks that 23 * ----------------------------------------------------------------------------
45 * don't exactly fit are passed up to the next larger size. In this 24 * "THE BEER-WARE LICENSE" (Revision 42):
46 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. 25 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
47 * This is designed for use in a virtual memory environment. 26 * can do whatever you want with this stuff. If we meet some day, and you think
27 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
28 * ----------------------------------------------------------------------------
48 */ 29 */
49 30
31/* #define MALLOC_STATS */
32
50#include <sys/types.h> 33#include <sys/types.h>
34#include <sys/param.h>
35#include <sys/mman.h>
36#include <sys/uio.h>
37#include <errno.h>
38#include <stdint.h>
51#include <stdlib.h> 39#include <stdlib.h>
52#include <string.h> 40#include <string.h>
41#include <stdio.h>
53#include <unistd.h> 42#include <unistd.h>
54 43
55#define NULL 0 44#ifdef MALLOC_STATS
56 45#include <fcntl.h>
57static void morecore();
58static int findbucket();
59
60/*
61 * The overhead on a block is at least 4 bytes. When free, this space
62 * contains a pointer to the next free block, and the bottom two bits must
63 * be zero. When in use, the first byte is set to MAGIC, and the second
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 */
70union overhead {
71 union overhead *ov_next; /* when free */
72 struct {
73 u_char ovu_magic; /* magic number */
74 u_char ovu_index; /* bucket # */
75#ifdef RCHECK
76 u_short ovu_rmagic; /* range magic number */
77 u_long ovu_size; /* actual block size */
78#endif 46#endif
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};
85 47
86#define MAGIC 0xef /* magic # on accounting info */ 48#include "thread_private.h"
87#define RMAGIC 0x5555 /* magic # on range info */
88 49
89#ifdef RCHECK 50#define MALLOC_MINSHIFT 4
90#define RSLOP sizeof (u_short) 51#define MALLOC_MAXSHIFT 16
52
53#if defined(__sparc__) && !defined(__sparcv9__)
54#define MALLOC_PAGESHIFT (13U)
91#else 55#else
92#define RSLOP 0 56#define MALLOC_PAGESHIFT (PGSHIFT)
93#endif 57#endif
94 58
59#define MALLOC_PAGESIZE (1UL << MALLOC_PAGESHIFT)
60#define MALLOC_MINSIZE (1UL << MALLOC_MINSHIFT)
61#define MALLOC_PAGEMASK (MALLOC_PAGESIZE - 1)
62#define MASK_POINTER(p) ((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK))
63
64#define MALLOC_MAXCHUNK (1 << (MALLOC_PAGESHIFT-1))
65#define MALLOC_MAXCACHE 256
66#define MALLOC_DELAYED_CHUNKS 16 /* should be power of 2 */
67
68#define PAGEROUND(x) (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK)
69
95/* 70/*
96 * nextf[i] is the pointer to the next free block of size 2^(i+3). The 71 * What to use for Junk. This is the byte value we use to fill with
97 * smallest allocatable block is 8 bytes. The overhead information 72 * when the 'J' option is enabled. Use SOME_JUNK right after alloc,
98 * precedes the data area returned to the user. 73 * and SOME_FREEJUNK right before free.
99 */ 74 */
100#define NBUCKETS 30 75#define SOME_JUNK 0xd0 /* as in "Duh" :-) */
101static union overhead *nextf[NBUCKETS]; 76#define SOME_FREEJUNK 0xdf
102extern char *sbrk(); 77
78#define MMAP(sz) mmap(NULL, (size_t)(sz), PROT_READ | PROT_WRITE, \
79 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0)
80
81struct region_info {
82 void *p; /* page; low bits used to mark chunks */
83 uintptr_t size; /* size for pages, or chunk_info pointer */
84};
85
86struct dir_info {
87 u_int32_t canary1;
88 struct region_info *r; /* region slots */
89 size_t regions_total; /* number of region slots */
90 size_t regions_bits; /* log2 of total */
91 size_t regions_free; /* number of free slots */
92 /* list of free chunk info structs */
93 struct chunk_info *chunk_info_list;
94 /* lists of chunks with free slots */
95 struct chunk_info *chunk_dir[MALLOC_MAXSHIFT];
96 size_t free_regions_size; /* free pages cached */
97 /* free pages cache */
98 struct region_info free_regions[MALLOC_MAXCACHE];
99 /* delayed free chunk slots */
100 void *delayed_chunks[MALLOC_DELAYED_CHUNKS];
101#ifdef MALLOC_STATS
102 size_t inserts;
103 size_t insert_collisions;
104 size_t finds;
105 size_t find_collisions;
106 size_t deletes;
107 size_t delete_moves;
108#define STATS_INC(x) ((x)++)
109#define STATS_ZERO(x) ((x) = 0)
110#else
111#define STATS_INC(x) /* nothing */
112#define STATS_ZERO(x) /* nothing */
113#endif /* MALLOC_STATS */
114 u_int32_t canary2;
115};
103 116
104static int pagesz; /* page size */
105static int pagebucket; /* page size bucket */
106 117
107#ifdef MSTATS
108/* 118/*
109 * nmalloc[i] is the difference between the number of mallocs and frees 119 * This structure describes a page worth of chunks.
110 * for a given block size. 120 *
121 * How many bits per u_long in the bitmap
111 */ 122 */
112static u_int nmalloc[NBUCKETS]; 123#define MALLOC_BITS (NBBY * sizeof(u_long))
113#include <stdio.h> 124struct chunk_info {
125 struct chunk_info *next; /* next on the free list */
126 void *page; /* pointer to the page */
127 u_int32_t canary;
128 u_short size; /* size of this page's chunks */
129 u_short shift; /* how far to shift for this size */
130 u_short free; /* how many free chunks */
131 u_short total; /* how many chunk */
132 /* which chunks are free */
133 u_long bits[(MALLOC_PAGESIZE / MALLOC_MINSIZE) / MALLOC_BITS];
134};
135
136static struct dir_info g_pool;
137static char *malloc_func; /* current function */
138char *malloc_options; /* compile-time options */
139
140static int malloc_abort = 1; /* abort() on error */
141static int malloc_active; /* status of malloc */
142static int malloc_freeprot; /* mprotect free pages PROT_NONE? */
143static int malloc_hint; /* call madvice on free pages? */
144static int malloc_junk; /* junk fill? */
145static int malloc_move; /* move allocations to end of page? */
146static int malloc_realloc; /* always realloc? */
147static int malloc_silent; /* avoid outputting warnings? */
148static int malloc_xmalloc; /* xmalloc behaviour? */
149static int malloc_zero; /* zero fill? */
150static size_t malloc_guard; /* use guard pages after allocations? */
151
152static u_int malloc_cache = 64; /* free pages we cache */
153static size_t malloc_guarded; /* bytes used for guards */
154static size_t malloc_used; /* bytes allocated */
155
156#ifdef MALLOC_STATS
157static int malloc_stats; /* dump statistics at end */
114#endif 158#endif
115 159
116#if defined(DEBUG) || defined(RCHECK) 160static size_t rbytesused; /* random bytes used */
117#define ASSERT(p) if (!(p)) botch("p") 161static u_char rbytes[4096]; /* random bytes */
118#include <stdio.h> 162static u_char getrbyte(void);
119static 163
120botch(s) 164extern char *__progname;
121 char *s; 165
166/* low bits of r->p determine size: 0 means >= page size and p->size holding
167 * real size, otherwise r->size is a shift count, or 1 for malloc(0)
168 */
169#define REALSIZE(sz, r) \
170 (sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \
171 (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1))))
172
173static inline size_t
174hash(void *p)
122{ 175{
123 fprintf(stderr, "\r\nassertion botched: %s\r\n", s); 176 size_t sum;
124 (void) fflush(stderr); /* just in case user buffered it */ 177 union {
125 abort(); 178 uintptr_t p;
126} 179 unsigned short a[sizeof(void *) / sizeof(short)];
127#else 180 } u;
128#define ASSERT(p) 181 u.p = (uintptr_t)p >> MALLOC_PAGESHIFT;
182 sum = u.a[0];
183 sum = (sum << 7) - sum + u.a[1];
184#ifdef __LP64__
185 sum = (sum << 7) - sum + u.a[2];
186 sum = (sum << 7) - sum + u.a[3];
129#endif 187#endif
188 return sum;
189}
130 190
131void * 191#ifdef MALLOC_STATS
132malloc(nbytes) 192static void
133 size_t nbytes; 193dump_chunk(int fd, struct chunk_info *p, int fromfreelist)
134{ 194{
135 register union overhead *op; 195 char buf[64];
136 register long bucket, n;
137 register unsigned amt;
138 196
139 /* 197 while (p) {
140 * First time malloc is called, setup page size and 198 snprintf(buf, sizeof(buf), "chunk %d %d/%d %p\n", p->size,
141 * align break pointer so all data will be page aligned. 199 p->free, p->total, p->page);
142 */ 200 write(fd, buf, strlen(buf));
143 if (pagesz == 0) { 201 if (!fromfreelist)
144 pagesz = n = getpagesize(); 202 break;
145 op = (union overhead *)sbrk(0); 203 p = p->next;
146 n = n - sizeof (*op) - ((long)op & (n - 1)); 204 if (p != NULL) {
147 if (n < 0) 205 snprintf(buf, sizeof(buf), " ");
148 n += pagesz; 206 write(fd, buf, strlen(buf));
149 if (n) {
150 if (sbrk(n) == (char *)-1)
151 return (NULL);
152 } 207 }
153 bucket = 0; 208 }
154 amt = 8; 209}
155 while (pagesz > amt) { 210
156 amt <<= 1; 211static void
157 bucket++; 212dump_free_chunk_info(int fd, struct dir_info *d)
213{
214 char buf[64];
215 int i;
216
217 snprintf(buf, sizeof(buf), "Free chunk structs:\n");
218 write(fd, buf, strlen(buf));
219 for (i = 0; i < MALLOC_MAXSHIFT; i++) {
220 struct chunk_info *p = d->chunk_dir[i];
221 if (p != NULL) {
222 snprintf(buf, sizeof(buf), "%2d) ", i);
223 write(fd, buf, strlen(buf));
224 dump_chunk(fd, p, 1);
158 } 225 }
159 pagebucket = bucket;
160 } 226 }
161 /* 227
162 * Convert amount of memory requested into closest block size 228}
163 * stored in hash buckets which satisfies request. 229
164 * Account for space used per block for accounting. 230static void
165 */ 231dump_free_page_info(int fd, struct dir_info *d)
166 if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { 232{
167#ifndef RCHECK 233 char buf[64];
168 amt = 8; /* size of first bucket */ 234 int i;
169 bucket = 0; 235
170#else 236 snprintf(buf, sizeof(buf), "Free pages cached: %zu\n",
171 amt = 16; /* size of first bucket */ 237 d->free_regions_size);
172 bucket = 1; 238 write(fd, buf, strlen(buf));
173#endif 239 for (i = 0; i < malloc_cache; i++) {
174 n = -((long)sizeof (*op) + RSLOP); 240 if (d->free_regions[i].p != NULL) {
175 } else { 241 snprintf(buf, sizeof(buf), "%2d) ", i);
176 amt = pagesz; 242 write(fd, buf, strlen(buf));
177 bucket = pagebucket; 243 snprintf(buf, sizeof(buf), "free at %p: %zu\n",
244 d->free_regions[i].p, d->free_regions[i].size);
245 write(fd, buf, strlen(buf));
246 }
178 } 247 }
179 while (nbytes > amt + n) { 248}
180 amt <<= 1; 249
181 if (amt == 0) 250static void
182 return (NULL); 251malloc_dump1(int fd, struct dir_info *d)
183 bucket++; 252{
253 char buf[64];
254 size_t i, realsize;
255
256 snprintf(buf, sizeof(buf), "Malloc dir of %s at %p\n", __progname, d);
257 write(fd, buf, strlen(buf));
258 snprintf(buf, sizeof(buf), "Regions slots %zu\n", d->regions_total);
259 write(fd, buf, strlen(buf));
260 snprintf(buf, sizeof(buf), "Finds %zu/%zu %f\n", d->finds,
261 d->find_collisions,
262 1.0 + (double)d->find_collisions / d->finds);
263 write(fd, buf, strlen(buf));
264 snprintf(buf, sizeof(buf), "Inserts %zu/%zu %f\n", d->inserts,
265 d->insert_collisions,
266 1.0 + (double)d->insert_collisions / d->inserts);
267 write(fd, buf, strlen(buf));
268 snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes,
269 d->delete_moves);
270 write(fd, buf, strlen(buf));
271 snprintf(buf, sizeof(buf), "Regions slots free %zu\n", d->regions_free);
272 write(fd, buf, strlen(buf));
273 for (i = 0; i < d->regions_total; i++) {
274 if (d->r[i].p != NULL) {
275 size_t h = hash(d->r[i].p) &
276 (d->regions_total - 1);
277 snprintf(buf, sizeof(buf), "%4zx) #%zx %zd ",
278 i, h, h - i);
279 write(fd, buf, strlen(buf));
280 REALSIZE(realsize, &d->r[i]);
281 if (realsize > MALLOC_MAXCHUNK) {
282 snprintf(buf, sizeof(buf),
283 "%p: %zu\n", d->r[i].p, realsize);
284 write(fd, buf, strlen(buf));
285 } else
286 dump_chunk(fd,
287 (struct chunk_info *)d->r[i].size, 0);
288 }
184 } 289 }
185 /* 290 dump_free_chunk_info(fd, d);
186 * If nothing in hash bucket right now, 291 dump_free_page_info(fd, d);
187 * request more memory from the system. 292 snprintf(buf, sizeof(buf), "In use %zu\n", malloc_used);
188 */ 293 write(fd, buf, strlen(buf));
189 if ((op = nextf[bucket]) == NULL) { 294 snprintf(buf, sizeof(buf), "Guarded %zu\n", malloc_guarded);
190 morecore(bucket); 295 write(fd, buf, strlen(buf));
191 if ((op = nextf[bucket]) == NULL) 296}
192 return (NULL); 297
193 } 298
194 /* remove from linked list */ 299void
195 nextf[bucket] = op->ov_next; 300malloc_dump(int fd)
196 op->ov_magic = MAGIC; 301{
197 op->ov_index = bucket; 302 malloc_dump1(fd, &g_pool);
198#ifdef MSTATS 303}
199 nmalloc[bucket]++; 304
200#endif 305static void
201#ifdef RCHECK 306malloc_exit(void)
202 /* 307{
203 * Record allocated size of block and 308 char *q = "malloc() warning: Couldn't dump stats\n";
204 * bound space with magic numbers. 309 int save_errno = errno, fd;
205 */ 310
206 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 311 fd = open("malloc.out", O_RDWR|O_APPEND);
207 op->ov_rmagic = RMAGIC; 312 if (fd != -1) {
208 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 313 malloc_dump(fd);
209#endif 314 close(fd);
210 return ((char *)(op + 1)); 315 } else
316 write(STDERR_FILENO, q, strlen(q));
317 errno = save_errno;
318}
319#endif /* MALLOC_STATS */
320
321
322
323static void
324wrterror(char *p)
325{
326 char *q = " error: ";
327 struct iovec iov[5];
328
329 iov[0].iov_base = __progname;
330 iov[0].iov_len = strlen(__progname);
331 iov[1].iov_base = malloc_func;
332 iov[1].iov_len = strlen(malloc_func);
333 iov[2].iov_base = q;
334 iov[2].iov_len = strlen(q);
335 iov[3].iov_base = p;
336 iov[3].iov_len = strlen(p);
337 iov[4].iov_base = "\n";
338 iov[4].iov_len = 1;
339 writev(STDERR_FILENO, iov, 5);
340
341#ifdef MALLOC_STATS
342 if (malloc_stats)
343 malloc_dump(STDERR_FILENO);
344#endif /* MALLOC_STATS */
345 //malloc_active--;
346 if (malloc_abort)
347 abort();
348}
349
350static void
351wrtwarning(char *p)
352{
353 char *q = " warning: ";
354 struct iovec iov[5];
355
356 if (malloc_abort)
357 wrterror(p);
358 else if (malloc_silent)
359 return;
360
361 iov[0].iov_base = __progname;
362 iov[0].iov_len = strlen(__progname);
363 iov[1].iov_base = malloc_func;
364 iov[1].iov_len = strlen(malloc_func);
365 iov[2].iov_base = q;
366 iov[2].iov_len = strlen(q);
367 iov[3].iov_base = p;
368 iov[3].iov_len = strlen(p);
369 iov[4].iov_base = "\n";
370 iov[4].iov_len = 1;
371
372 writev(STDERR_FILENO, iov, 5);
211} 373}
212 374
213/* 375/*
214 * Allocate more memory to the indicated bucket. 376 * Cache maintenance. We keep at most malloc_cache pages cached.
377 * If the cache is becoming full, unmap pages in the cache for real,
378 * and then add the region to the cache
379 * Opposed to the regular region data structure, the sizes in the
380 * cache are in MALLOC_PAGESIZE units.
215 */ 381 */
216static void 382static void
217morecore(bucket) 383unmap(struct dir_info *d, void *p, size_t sz)
218 int bucket;
219{ 384{
220 register union overhead *op; 385 size_t psz = sz >> MALLOC_PAGESHIFT;
221 register long sz; /* size of desired block */ 386 size_t rsz, tounmap;
222 long amt; /* amount to allocate */ 387 struct region_info *r;
223 int nblks; /* how many blocks we get */ 388 u_int i, offset;
224 389
225 /* 390 if (sz != PAGEROUND(sz)) {
226 * sbrk_size <= 0 only for big, FLUFFY, requests (about 391 wrterror("munmap round");
227 * 2^30 bytes on a VAX, I think) or for a negative arg.
228 */
229 sz = 1 << (bucket + 3);
230#ifdef DEBUG
231 ASSERT(sz > 0);
232#else
233 if (sz <= 0)
234 return; 392 return;
235#endif
236 if (sz < pagesz) {
237 amt = pagesz;
238 nblks = amt / sz;
239 } else {
240 amt = sz + pagesz;
241 nblks = 1;
242 } 393 }
243 op = (union overhead *)sbrk(amt); 394
244 /* no more room! */ 395 if (psz > malloc_cache) {
245 if ((long)op == -1) 396 if (munmap(p, sz))
246 return; 397 wrterror("munmap");
398 malloc_used -= sz;
399 return;
400 }
401 tounmap = 0;
402 rsz = malloc_cache - d->free_regions_size;
403 if (psz > rsz)
404 tounmap = psz - rsz;
405 d->free_regions_size -= tounmap;
406 offset = getrbyte();
407 for (i = 0; tounmap > 0 && i < malloc_cache; i++) {
408 r = &d->free_regions[(i + offset) & (malloc_cache - 1)];
409 if (r->p != NULL) {
410 if (r->size <= tounmap) {
411 rsz = r->size << MALLOC_PAGESHIFT;
412 if (munmap(r->p, rsz))
413 wrterror("munmap");
414 tounmap -= r->size;
415 r->p = NULL;
416 r->size = 0;
417 malloc_used -= rsz;
418 } else {
419 rsz = tounmap << MALLOC_PAGESHIFT;
420 if (munmap((char *)r->p + ((r->size - tounmap)
421 << MALLOC_PAGESHIFT), rsz))
422 wrterror("munmap");
423 r->size -= tounmap ;
424 tounmap = 0;
425 malloc_used -= rsz;
426 }
427 }
428 }
429 if (tounmap > 0)
430 wrtwarning("malloc cache underflow");
431 for (i = 0; i < malloc_cache; i++) {
432 r = &d->free_regions[i];
433 if (r->p == NULL) {
434 if (malloc_hint)
435 madvise(p, sz, MADV_FREE);
436 if (malloc_freeprot)
437 mprotect(p, sz, PROT_NONE);
438 r->p = p;
439 r->size = psz;
440 d->free_regions_size += psz;
441 break;
442 }
443 }
444 if (i == malloc_cache)
445 wrtwarning("malloc free slot lost");
446 if (d->free_regions_size > malloc_cache)
447 wrtwarning("malloc cache overflow");
448}
449
450static void *
451map(struct dir_info *d, size_t sz, int zero_fill)
452{
453 size_t psz = sz >> MALLOC_PAGESHIFT;
454 struct region_info *r, *big = NULL;
455 u_int i, offset;
456 void *p;
457
458 if (sz != PAGEROUND(sz)) {
459 wrterror("map round");
460 return NULL;
461 }
462 if (psz > d->free_regions_size) {
463 p = MMAP(sz);
464 if (p != MAP_FAILED)
465 malloc_used += sz;
466 /* zero fill not needed */
467 return p;
468 }
469 offset = getrbyte();
470 for (i = 0; i < malloc_cache; i++) {
471 r = &d->free_regions[(i + offset) & (malloc_cache - 1)];
472 if (r->p != NULL) {
473 if (r->size == psz) {
474 p = r->p;
475 if (malloc_freeprot)
476 mprotect(p, sz, PROT_READ | PROT_WRITE);
477 if (malloc_hint)
478 madvise(p, sz, MADV_NORMAL);
479 r->p = NULL;
480 r->size = 0;
481 d->free_regions_size -= psz;
482 if (zero_fill)
483 memset(p, 0, sz);
484 return p;
485 } else if (r->size > psz)
486 big = r;
487 }
488 }
489 if (big != NULL) {
490 r = big;
491 p = (char *)r->p + ((r->size - psz) << MALLOC_PAGESHIFT);
492 if (malloc_freeprot)
493 mprotect(p, sz, PROT_READ | PROT_WRITE);
494 if (malloc_hint)
495 madvise(p, sz, MADV_NORMAL);
496 r->size -= psz;
497 d->free_regions_size -= psz;
498 if (zero_fill)
499 memset(p, 0, sz);
500 return p;
501 }
502 p = MMAP(sz);
503 if (p != MAP_FAILED)
504 malloc_used += sz;
505 if (d->free_regions_size > malloc_cache)
506 wrtwarning("malloc cache");
507 /* zero fill not needed */
508 return p;
509}
510
511static void
512rbytes_init(void)
513{
514 arc4random_buf(rbytes, sizeof(rbytes));
515 rbytesused = 0;
516}
517
518static u_char
519getrbyte(void)
520{
521 if (rbytesused >= sizeof(rbytes))
522 rbytes_init();
523 return rbytes[rbytesused++];
524}
525
526/*
527 * Initialize a dir_info, which should have been cleared by caller
528 */
529static int
530omalloc_init(struct dir_info *d)
531{
532 char *p, b[64];
533 int i, j, save_errno = errno;
534 size_t regioninfo_size;
535
536 rbytes_init();
537
538 for (i = 0; i < 3; i++) {
539 switch (i) {
540 case 0:
541 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
542 if (j <= 0)
543 continue;
544 b[j] = '\0';
545 p = b;
546 break;
547 case 1:
548 if (issetugid() == 0)
549 p = getenv("MALLOC_OPTIONS");
550 else
551 continue;
552 break;
553 case 2:
554 p = malloc_options;
555 break;
556 default:
557 p = NULL;
558 }
559
560 for (; p != NULL && *p != '\0'; p++) {
561 switch (*p) {
562 case '>':
563 malloc_cache <<= 1;
564 if (malloc_cache > MALLOC_MAXCACHE)
565 malloc_cache = MALLOC_MAXCACHE;
566 break;
567 case '<':
568 malloc_cache >>= 1;
569 break;
570 case 'a':
571 malloc_abort = 0;
572 break;
573 case 'A':
574 malloc_abort = 1;
575 break;
576#ifdef MALLOC_STATS
577 case 'd':
578 malloc_stats = 0;
579 break;
580 case 'D':
581 malloc_stats = 1;
582 break;
583#endif /* MALLOC_STATS */
584 case 'f':
585 malloc_freeprot = 0;
586 break;
587 case 'F':
588 malloc_freeprot = 1;
589 break;
590 case 'g':
591 malloc_guard = 0;
592 break;
593 case 'G':
594 malloc_guard = MALLOC_PAGESIZE;
595 break;
596 case 'h':
597 malloc_hint = 0;
598 break;
599 case 'H':
600 malloc_hint = 1;
601 break;
602 case 'j':
603 malloc_junk = 0;
604 break;
605 case 'J':
606 malloc_junk = 1;
607 break;
608 case 'n':
609 malloc_silent = 0;
610 break;
611 case 'N':
612 malloc_silent = 1;
613 break;
614 case 'p':
615 malloc_move = 0;
616 break;
617 case 'P':
618 malloc_move = 1;
619 break;
620 case 'r':
621 malloc_realloc = 0;
622 break;
623 case 'R':
624 malloc_realloc = 1;
625 break;
626 case 'x':
627 malloc_xmalloc = 0;
628 break;
629 case 'X':
630 malloc_xmalloc = 1;
631 break;
632 case 'z':
633 malloc_zero = 0;
634 break;
635 case 'Z':
636 malloc_zero = 1;
637 break;
638 default:
639 j = malloc_abort;
640 malloc_abort = 0;
641 wrtwarning("unknown char in MALLOC_OPTIONS");
642 malloc_abort = j;
643 break;
644 }
645 }
646 }
647
247 /* 648 /*
248 * Add new memory allocated to that on 649 * We want junk in the entire allocation, and zero only in the part
249 * free list for this hash bucket. 650 * the user asked for.
250 */ 651 */
251 nextf[bucket] = op; 652 if (malloc_zero)
252 while (--nblks > 0) { 653 malloc_junk = 1;
253 op->ov_next = (union overhead *)((caddr_t)op + sz); 654
254 op = (union overhead *)((caddr_t)op + sz); 655#ifdef MALLOC_STATS
255 } 656 if (malloc_stats && (atexit(malloc_exit) == -1))
657 wrtwarning("atexit(2) failed."
658 " Will not be able to dump malloc stats on exit");
659#endif /* MALLOC_STATS */
660
661 errno = save_errno;
662
663 d->regions_bits = 9;
664 d->regions_free = d->regions_total = 1 << d->regions_bits;
665 regioninfo_size = d->regions_total * sizeof(struct region_info);
666 d->r = MMAP(regioninfo_size);
667 if (d->r == MAP_FAILED) {
668 wrterror("malloc init mmap failed");
669 d->regions_total = 0;
670 return 1;
671 }
672 malloc_used += regioninfo_size;
673 memset(d->r, 0, regioninfo_size);
674 d->canary1 = arc4random();
675 d->canary2 = ~d->canary1;
676 return 0;
256} 677}
257 678
258void 679static int
259free(cp) 680omalloc_grow(struct dir_info *d)
260 void *cp; 681{
261{ 682 size_t newbits;
262 register long size; 683 size_t newtotal;
263 register union overhead *op; 684 size_t newsize;
264 685 size_t mask;
265 if (cp == NULL) 686 size_t i;
266 return; 687 struct region_info *p;
267 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 688
268#ifdef DEBUG 689 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2 )
269 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 690 return 1;
270#else 691
271 if (op->ov_magic != MAGIC) 692 newbits = d->regions_bits + 1;
272 return; /* sanity */ 693 newtotal = d->regions_total * 2;
273#endif 694 newsize = newtotal * sizeof(struct region_info);
274#ifdef RCHECK 695 mask = newtotal - 1;
275 ASSERT(op->ov_rmagic == RMAGIC); 696
276 ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 697 p = MMAP(newsize);
277#endif 698 if (p == MAP_FAILED)
278 size = op->ov_index; 699 return 1;
279 ASSERT(size < NBUCKETS); 700
280 op->ov_next = nextf[size]; /* also clobbers ov_magic */ 701 malloc_used += newsize;
281 nextf[size] = op; 702 memset(p, 0, newsize);
282#ifdef MSTATS 703 STATS_ZERO(d->inserts);
283 nmalloc[size]--; 704 STATS_ZERO(d->insert_collisions);
284#endif 705 for (i = 0; i < d->regions_total; i++) {
706 void *q = d->r[i].p;
707 if (q != NULL) {
708 size_t index = hash(q) & mask;
709 STATS_INC(d->inserts);
710 while (p[index].p != NULL) {
711 index = (index - 1) & mask;
712 STATS_INC(d->insert_collisions);
713 }
714 p[index] = d->r[i];
715 }
716 }
717 /* avoid pages containing meta info to end up in cache */
718 if (munmap(d->r, d->regions_total * sizeof(struct region_info)))
719 wrterror("munmap");
720 else
721 malloc_used -= d->regions_total * sizeof(struct region_info);
722 d->regions_free = d->regions_free + d->regions_total;
723 d->regions_total = newtotal;
724 d->regions_bits = newbits;
725 d->r = p;
726 return 0;
727}
728
729static struct chunk_info *
730alloc_chunk_info(struct dir_info *d)
731{
732 struct chunk_info *p;
733 int i;
734
735 if (d->chunk_info_list == NULL) {
736 p = MMAP(MALLOC_PAGESIZE);
737 if (p == MAP_FAILED)
738 return NULL;
739 malloc_used += MALLOC_PAGESIZE;
740 for (i = 0; i < MALLOC_PAGESIZE / sizeof(*p); i++) {
741 p[i].next = d->chunk_info_list;
742 d->chunk_info_list = &p[i];
743 }
744 }
745 p = d->chunk_info_list;
746 d->chunk_info_list = p->next;
747 memset(p, 0, sizeof *p);
748 p->canary = d->canary1;
749 return p;
750}
751
752
753static void
754put_chunk_info(struct dir_info *d, struct chunk_info *p)
755{
756 p->next = d->chunk_info_list;
757 d->chunk_info_list = p;
758}
759
760static int
761insert(struct dir_info *d, void *p, size_t sz)
762{
763 size_t index;
764 size_t mask;
765 void *q;
766
767 if (d->regions_free * 4 < d->regions_total) {
768 if (omalloc_grow(d))
769 return 1;
770 }
771 mask = d->regions_total - 1;
772 index = hash(p) & mask;
773 q = d->r[index].p;
774 STATS_INC(d->inserts);
775 while (q != NULL) {
776 index = (index - 1) & mask;
777 q = d->r[index].p;
778 STATS_INC(d->insert_collisions);
779 }
780 d->r[index].p = p;
781 d->r[index].size = sz;
782 d->regions_free--;
783 return 0;
285} 784}
286 785
786static struct region_info *
787find(struct dir_info *d, void *p)
788{
789 size_t index;
790 size_t mask = d->regions_total - 1;
791 void *q, *r;
792
793 if (d->canary1 != ~d->canary2)
794 wrterror("internal struct corrupt");
795 p = MASK_POINTER(p);
796 index = hash(p) & mask;
797 r = d->r[index].p;
798 q = MASK_POINTER(r);
799 STATS_INC(d->finds);
800 while (q != p && r != NULL) {
801 index = (index - 1) & mask;
802 r = d->r[index].p;
803 q = MASK_POINTER(r);
804 STATS_INC(d->find_collisions);
805 }
806 return q == p ? &d->r[index] : NULL;
807}
808
809static void
810delete(struct dir_info *d, struct region_info *ri)
811{
812 /* algorithm R, Knuth Vol III section 6.4 */
813 size_t mask = d->regions_total - 1;
814 size_t i, j, r;
815
816 if (d->regions_total & (d->regions_total - 1))
817 wrterror("regions_total not 2^x");
818 d->regions_free++;
819 STATS_INC(g_pool.deletes);
820
821 i = ri - d->r;
822 for (;;) {
823 d->r[i].p = NULL;
824 d->r[i].size = 0;
825 j = i;
826 for (;;) {
827 i = (i - 1) & mask;
828 if (d->r[i].p == NULL)
829 return;
830 r = hash(d->r[i].p) & mask;
831 if ((i <= r && r < j) || (r < j && j < i) ||
832 (j < i && i <= r))
833 continue;
834 d->r[j] = d->r[i];
835 STATS_INC(g_pool.delete_moves);
836 break;
837 }
838
839 }
840}
841
287/* 842/*
288 * When a program attempts "storage compaction" as mentioned in the 843 * Allocate a page of chunks
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 */ 844 */
298int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 845static struct chunk_info *
846omalloc_make_chunks(struct dir_info *d, int bits)
847{
848 struct chunk_info *bp;
849 void *pp;
850 long i, k;
299 851
300void * 852 /* Allocate a new bucket */
301realloc(cp, nbytes) 853 pp = map(d, MALLOC_PAGESIZE, 0);
302 void *cp; 854 if (pp == MAP_FAILED)
303 size_t nbytes; 855 return NULL;
304{ 856
305 register u_long onb; 857 bp = alloc_chunk_info(d);
306 register long i; 858 if (bp == NULL) {
307 union overhead *op; 859 unmap(d, pp, MALLOC_PAGESIZE);
308 char *res; 860 return NULL;
309 int was_alloced = 0; 861 }
310 862
311 if (cp == NULL) 863 /* memory protect the page allocated in the malloc(0) case */
312 return (malloc(nbytes)); 864 if (bits == 0) {
313 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 865 bp->size = 0;
314 if (op->ov_magic == MAGIC) { 866 bp->shift = 1;
315 was_alloced++; 867 i = MALLOC_MINSIZE - 1;
316 i = op->ov_index; 868 while (i >>= 1)
317 } else { 869 bp->shift++;
318 /* 870 bp->total = bp->free = MALLOC_PAGESIZE >> bp->shift;
319 * Already free, doing "compaction". 871 bp->page = pp;
320 * 872
321 * Search for the old block of memory on the 873 k = mprotect(pp, MALLOC_PAGESIZE, PROT_NONE);
322 * free list. First, check the most common 874 if (k < 0) {
323 * case (last element free'd), then (this failing) 875 unmap(d, pp, MALLOC_PAGESIZE);
324 * the last ``realloc_srchlen'' items free'd. 876 put_chunk_info(d, bp);
325 * If all lookups fail, then assume the size of 877 return NULL;
326 * the memory block being realloc'd is the
327 * largest possible (so that all "nbytes" of new
328 * memory are copied into). Note that this could cause
329 * a memory fault if the old area was tiny, and the moon
330 * is gibbous. However, that is very unlikely.
331 */
332 if ((i = findbucket(op, 1)) < 0 &&
333 (i = findbucket(op, realloc_srchlen)) < 0)
334 i = NBUCKETS;
335 }
336 onb = 1 << (i + 3);
337 if (onb < pagesz)
338 onb -= sizeof (*op) + RSLOP;
339 else
340 onb += pagesz - sizeof (*op) - RSLOP;
341 /* avoid the copy if same size block */
342 if (was_alloced) {
343 if (i) {
344 i = 1 << (i + 2);
345 if (i < pagesz)
346 i -= sizeof (*op) + RSLOP;
347 else
348 i += pagesz - sizeof (*op) - RSLOP;
349 } 878 }
350 if (nbytes <= onb && nbytes > i) { 879 } else {
351#ifdef RCHECK 880 bp->size = (1UL << bits);
352 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 881 bp->shift = bits;
353 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 882 bp->total = bp->free = MALLOC_PAGESIZE >> bits;
354#endif 883 bp->page = pp;
355 return(cp); 884 }
356 } else 885
357 free(cp); 886 /* set all valid bits in the bitmap */
358 } 887 k = bp->total;
359 if ((res = malloc(nbytes)) == NULL) 888 i = 0;
360 return (NULL); 889
361 if (cp != res) /* common optimization if "compacting" */ 890 /* Do a bunch at a time */
362 bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 891 for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
363 return (res); 892 bp->bits[i / MALLOC_BITS] = ~0UL;
893
894 for (; i < k; i++)
895 bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
896
897 bp->next = d->chunk_dir[bits];
898 d->chunk_dir[bits] = bp;
899
900 bits++;
901 if ((uintptr_t)pp & bits)
902 wrterror("pp & bits");
903
904 insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp);
905 return bp;
364} 906}
365 907
908
366/* 909/*
367 * Search ``srchlen'' elements of each free list for a block whose 910 * Allocate a chunk
368 * header starts at ``freep''. If srchlen is -1 search the whole list.
369 * Return bucket number, or -1 if not found.
370 */ 911 */
371static 912static void *
372findbucket(freep, srchlen) 913malloc_bytes(struct dir_info *d, size_t size)
373 union overhead *freep;
374 int srchlen;
375{ 914{
376 register union overhead *p; 915 int i, j;
377 register int i, j; 916 size_t k;
917 u_long u, *lp;
918 struct chunk_info *bp;
919
920 /* Don't bother with anything less than this */
921 /* unless we have a malloc(0) requests */
922 if (size != 0 && size < MALLOC_MINSIZE)
923 size = MALLOC_MINSIZE;
378 924
379 for (i = 0; i < NBUCKETS; i++) { 925 /* Find the right bucket */
926 if (size == 0)
380 j = 0; 927 j = 0;
381 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 928 else {
382 if (p == freep) 929 j = MALLOC_MINSHIFT;
383 return (i); 930 i = (size - 1) >> (MALLOC_MINSHIFT - 1);
931 while (i >>= 1)
384 j++; 932 j++;
933 }
934
935 /* If it's empty, make a page more of that size chunks */
936 bp = d->chunk_dir[j];
937 if (bp == NULL && (bp = omalloc_make_chunks(d, j)) == NULL)
938 return NULL;
939
940 if (bp->canary != d->canary1)
941 wrterror("chunk info corrupted");
942 /* Find first word of bitmap which isn't empty */
943 for (lp = bp->bits; !*lp; lp++)
944 /* EMPTY */;
945
946 /* Find that bit, and tweak it */
947 u = 1;
948 k = 0;
949 while (!(*lp & u)) {
950 u += u;
951 k++;
952 }
953
954 /* advance a random # of positions */
955 i = (getrbyte() & (MALLOC_DELAYED_CHUNKS - 1)) % bp->free;
956 while (i > 0) {
957 u += u;
958 k++;
959 if (k >= MALLOC_BITS) {
960 lp++;
961 u = 1;
962 k = 0;
385 } 963 }
964 if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
965 wrterror("chunk overflow");
966 errno = EFAULT;
967 return (NULL);
968 }
969 if (*lp & u)
970 i--;
386 } 971 }
387 return (-1); 972
973 *lp ^= u;
974
975 /* If there are no more free, remove from free-list */
976 if (!--bp->free) {
977 d->chunk_dir[j] = bp->next;
978 bp->next = NULL;
979 }
980 /* Adjust to the real offset of that chunk */
981 k += (lp - bp->bits) * MALLOC_BITS;
982 k <<= bp->shift;
983
984 if (malloc_junk && bp->size > 0)
985 memset((char *)bp->page + k, SOME_JUNK, bp->size);
986 return ((char *)bp->page + k);
388} 987}
389 988
390#ifdef MSTATS 989
391/* 990/*
392 * mstats - print out statistics about malloc 991 * Free a chunk, and possibly the page it's on, if the page becomes empty.
393 *
394 * Prints two lines of numbers, one showing the length of the free list
395 * for each size category, the second showing the number of mallocs -
396 * frees for each size category.
397 */ 992 */
398mstats(s) 993static void
399 char *s; 994free_bytes(struct dir_info *d, struct region_info *r, void *ptr)
400{ 995{
401 register int i, j; 996 struct chunk_info *info, **mp;
402 register union overhead *p; 997 long i;
403 int totfree = 0, 998
404 totused = 0; 999 info = (struct chunk_info *)r->size;
405 1000 if (info->canary != d->canary1)
406 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 1001 wrterror("chunk info corrupted");
407 for (i = 0; i < NBUCKETS; i++) { 1002
408 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 1003 /* Find the chunk number on the page */
409 ; 1004 i = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift;
410 fprintf(stderr, " %d", j); 1005
411 totfree += j * (1 << (i + 3)); 1006 if ((uintptr_t)ptr & ((1UL << (info->shift)) - 1)) {
412 } 1007 wrtwarning("modified chunk-pointer");
413 fprintf(stderr, "\nused:\t"); 1008 return;
414 for (i = 0; i < NBUCKETS; i++) { 1009 }
415 fprintf(stderr, " %d", nmalloc[i]); 1010 if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
416 totused += nmalloc[i] * (1 << (i + 3)); 1011 wrtwarning("chunk is already free");
417 } 1012 return;
418 fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 1013 }
419 totused, totfree); 1014
1015 info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
1016 info->free++;
1017
1018 if (info->size != 0)
1019 mp = d->chunk_dir + info->shift;
1020 else
1021 mp = d->chunk_dir;
1022
1023 if (info->free == 1) {
1024 /* Page became non-full */
1025
1026 /* Insert in address order */
1027 while (*mp != NULL && (*mp)->next != NULL &&
1028 (*mp)->next->page < info->page)
1029 mp = &(*mp)->next;
1030 info->next = *mp;
1031 *mp = info;
1032 return;
1033 }
1034 if (info->free != info->total)
1035 return;
1036
1037 /* Find & remove this page in the queue */
1038 while (*mp != info) {
1039 mp = &((*mp)->next);
1040 if (!*mp) {
1041 wrterror("not on queue");
1042 errno = EFAULT;
1043 return;
1044 }
1045 }
1046 *mp = info->next;
1047
1048 if (info->size == 0 && !malloc_freeprot)
1049 mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE);
1050 unmap(d, info->page, MALLOC_PAGESIZE);
1051
1052 delete(d, r);
1053 put_chunk_info(d, info);
420} 1054}
1055
1056
1057
1058static void *
1059omalloc(size_t sz, int zero_fill)
1060{
1061 void *p;
1062 size_t psz;
1063
1064 if (sz > MALLOC_MAXCHUNK) {
1065 if (sz >= SIZE_MAX - malloc_guard - MALLOC_PAGESIZE) {
1066 errno = ENOMEM;
1067 return NULL;
1068 }
1069 sz += malloc_guard;
1070 psz = PAGEROUND(sz);
1071 p = map(&g_pool, psz, zero_fill);
1072 if (p == MAP_FAILED) {
1073 errno = ENOMEM;
1074 return NULL;
1075 }
1076 if (insert(&g_pool, p, sz)) {
1077 unmap(&g_pool, p, psz);
1078 errno = ENOMEM;
1079 return NULL;
1080 }
1081 if (malloc_guard) {
1082 if (mprotect((char *)p + psz - malloc_guard,
1083 malloc_guard, PROT_NONE))
1084 wrterror("mprotect");
1085 malloc_guarded += malloc_guard;
1086 }
1087
1088 if (malloc_move &&
1089 sz - malloc_guard < MALLOC_PAGESIZE - MALLOC_MINSIZE) {
1090 /* fill whole allocation */
1091 if (malloc_junk)
1092 memset(p, SOME_JUNK, psz - malloc_guard);
1093 /* shift towards the end */
1094 p = ((char *)p) + ((MALLOC_PAGESIZE - MALLOC_MINSIZE -
1095 (sz - malloc_guard)) & ~(MALLOC_MINSIZE-1));
1096 /* fill zeros if needed and overwritten above */
1097 if (zero_fill && malloc_junk)
1098 memset(p, 0, sz - malloc_guard);
1099 } else {
1100 if (malloc_junk) {
1101 if (zero_fill)
1102 memset(p + sz - malloc_guard,
1103 SOME_JUNK, psz - sz);
1104 else
1105 memset(p,
1106 SOME_JUNK, psz - malloc_guard);
1107 }
1108 }
1109
1110 } else {
1111 /* takes care of SOME_JUNK */
1112 p = malloc_bytes(&g_pool, sz);
1113 if (zero_fill && p != NULL && sz > 0)
1114 memset(p, 0, sz);
1115 }
1116
1117 return p;
1118}
1119
1120/*
1121 * Common function for handling recursion. Only
1122 * print the error message once, to avoid making the problem
1123 * potentially worse.
1124 */
1125static void
1126malloc_recurse(void)
1127{
1128 static int noprint;
1129
1130 if (noprint == 0) {
1131 noprint = 1;
1132 wrtwarning("recursive call");
1133 }
1134 malloc_active--;
1135 _MALLOC_UNLOCK();
1136 errno = EDEADLK;
1137}
1138
1139void *
1140malloc(size_t size)
1141{
1142 void *r;
1143
1144 _MALLOC_LOCK();
1145 malloc_func = " in malloc():";
1146 if (!g_pool.regions_total) {
1147 if (omalloc_init(&g_pool)) {
1148 _MALLOC_UNLOCK();
1149 if (malloc_xmalloc)
1150 wrterror("out of memory");
1151 errno = ENOMEM;
1152 return NULL;
1153 }
1154 }
1155 if (malloc_active++) {
1156 malloc_recurse();
1157 return NULL;
1158 }
1159 r = omalloc(size, malloc_zero);
1160 malloc_active--;
1161 _MALLOC_UNLOCK();
1162 if (r == NULL && malloc_xmalloc) {
1163 wrterror("out of memory");
1164 errno = ENOMEM;
1165 }
1166 return r;
1167}
1168
1169static void
1170ofree(void *p)
1171{
1172 struct region_info *r;
1173 size_t sz;
1174
1175 r = find(&g_pool, p);
1176 if (r == NULL) {
1177 wrtwarning("bogus pointer (double free?)");
1178 return;
1179 }
1180 REALSIZE(sz, r);
1181 if (sz > MALLOC_MAXCHUNK) {
1182 if (sz - malloc_guard >= MALLOC_PAGESIZE - MALLOC_MINSIZE) {
1183 if (r->p != p)
1184 wrtwarning("bogus pointer");
1185 } else {
1186#if notyetbecause_of_realloc
1187 /* shifted towards the end */
1188 if (p != ((char *)r->p) + ((MALLOC_PAGESIZE -
1189 MALLOC_MINSIZE - sz - malloc_guard) &
1190 ~(MALLOC_MINSIZE-1))) {
1191 }
421#endif 1192#endif
1193 p = r->p;
1194 }
1195 if (malloc_guard) {
1196 if (sz < malloc_guard)
1197 wrtwarning("guard size");
1198 if (!malloc_freeprot) {
1199 if (mprotect((char *)p + PAGEROUND(sz) -
1200 malloc_guard, malloc_guard,
1201 PROT_READ | PROT_WRITE))
1202 wrterror("mprotect");
1203 }
1204 malloc_guarded -= malloc_guard;
1205 }
1206 if (malloc_junk)
1207 memset(p, SOME_FREEJUNK, PAGEROUND(sz) - malloc_guard);
1208 unmap(&g_pool, p, PAGEROUND(sz));
1209 delete(&g_pool, r);
1210 } else {
1211 void *tmp;
1212 int i;
1213
1214 if (malloc_junk && sz > 0)
1215 memset(p, SOME_FREEJUNK, sz);
1216 i = getrbyte() & (MALLOC_DELAYED_CHUNKS - 1);
1217 tmp = p;
1218 p = g_pool.delayed_chunks[i];
1219 g_pool.delayed_chunks[i] = tmp;
1220 if (p != NULL) {
1221 r = find(&g_pool, p);
1222 if (r == NULL) {
1223 wrtwarning("bogus pointer (double free?)");
1224 return;
1225 }
1226 free_bytes(&g_pool, r, p);
1227 }
1228 }
1229}
1230
1231void
1232free(void *ptr)
1233{
1234 /* This is legal. */
1235 if (ptr == NULL)
1236 return;
1237
1238 _MALLOC_LOCK();
1239 malloc_func = " in free():";
1240 if (malloc_active++) {
1241 malloc_recurse();
1242 return;
1243 }
1244 ofree(ptr);
1245 malloc_active--;
1246 _MALLOC_UNLOCK();
1247}
1248
1249
1250static void *
1251orealloc(void *p, size_t newsz)
1252{
1253 struct region_info *r;
1254 size_t oldsz, goldsz, gnewsz;
1255 void *q;
1256
1257 if (p == NULL)
1258 return omalloc(newsz, 0);
1259
1260 r = find(&g_pool, p);
1261 if (r == NULL) {
1262 wrtwarning("bogus pointer (double free?)");
1263 return NULL;
1264 }
1265 if (newsz >= SIZE_MAX - malloc_guard - MALLOC_PAGESIZE) {
1266 errno = ENOMEM;
1267 return NULL;
1268 }
1269
1270 REALSIZE(oldsz, r);
1271 goldsz = oldsz;
1272 if (oldsz > MALLOC_MAXCHUNK) {
1273 if (oldsz < malloc_guard)
1274 wrtwarning("guard size");
1275 oldsz -= malloc_guard;
1276 }
1277
1278 gnewsz = newsz;
1279 if (gnewsz > MALLOC_MAXCHUNK)
1280 gnewsz += malloc_guard;
1281
1282 if (newsz > MALLOC_MAXCHUNK && oldsz > MALLOC_MAXCHUNK && p == r->p &&
1283 !malloc_realloc) {
1284 size_t roldsz = PAGEROUND(goldsz);
1285 size_t rnewsz = PAGEROUND(gnewsz);
1286
1287 if (rnewsz < roldsz) {
1288 if (malloc_guard) {
1289 if (mprotect((char *)p + roldsz - malloc_guard,
1290 malloc_guard, PROT_READ | PROT_WRITE))
1291 wrterror("mprotect");
1292 if (mprotect((char *)p + rnewsz - malloc_guard,
1293 malloc_guard, PROT_NONE))
1294 wrterror("mprotect");
1295 }
1296 unmap(&g_pool, (char *)p + rnewsz, roldsz - rnewsz);
1297 r->size = gnewsz;
1298 return p;
1299 } else if (rnewsz == roldsz) {
1300 if (newsz > oldsz && malloc_junk)
1301 memset((char *)p + newsz, SOME_JUNK,
1302 rnewsz - malloc_guard - newsz);
1303 r->size = gnewsz;
1304 return p;
1305 }
1306 }
1307 if (newsz <= oldsz && newsz > oldsz / 2 && !malloc_realloc) {
1308 if (malloc_junk && newsz > 0)
1309 memset((char *)p + newsz, SOME_JUNK, oldsz - newsz);
1310 return p;
1311 } else if (newsz != oldsz || malloc_realloc) {
1312 q = omalloc(newsz, 0);
1313 if (q == NULL)
1314 return NULL;
1315 if (newsz != 0 && oldsz != 0)
1316 memcpy(q, p, oldsz < newsz ? oldsz : newsz);
1317 ofree(p);
1318 return q;
1319 } else
1320 return p;
1321}
1322
1323void *
1324realloc(void *ptr, size_t size)
1325{
1326 void *r;
1327
1328 _MALLOC_LOCK();
1329 malloc_func = " in realloc():";
1330 if (!g_pool.regions_total) {
1331 if (omalloc_init(&g_pool)) {
1332 _MALLOC_UNLOCK();
1333 if (malloc_xmalloc)
1334 wrterror("out of memory");
1335 errno = ENOMEM;
1336 return NULL;
1337 }
1338 }
1339 if (malloc_active++) {
1340 malloc_recurse();
1341 return NULL;
1342 }
1343
1344 r = orealloc(ptr, size);
1345
1346 malloc_active--;
1347 _MALLOC_UNLOCK();
1348 if (r == NULL && malloc_xmalloc) {
1349 wrterror("out of memory");
1350 errno = ENOMEM;
1351 }
1352 return r;
1353}
1354
1355
1356#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
1357
1358void *
1359calloc(size_t nmemb, size_t size)
1360{
1361 void *r;
1362
1363 _MALLOC_LOCK();
1364 malloc_func = " in calloc():";
1365 if (!g_pool.regions_total) {
1366 if (omalloc_init(&g_pool)) {
1367 _MALLOC_UNLOCK();
1368 if (malloc_xmalloc)
1369 wrterror("out of memory");
1370 errno = ENOMEM;
1371 return NULL;
1372 }
1373 }
1374 if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
1375 nmemb > 0 && SIZE_MAX / nmemb < size) {
1376 _MALLOC_UNLOCK();
1377 if (malloc_xmalloc)
1378 wrterror("out of memory");
1379 errno = ENOMEM;
1380 return NULL;
1381 }
1382
1383 if (malloc_active++) {
1384 malloc_recurse();
1385 return NULL;
1386 }
1387
1388 size *= nmemb;
1389 r = omalloc(size, 1);
1390
1391 malloc_active--;
1392 _MALLOC_UNLOCK();
1393 if (r == NULL && malloc_xmalloc) {
1394 wrterror("out of memory");
1395 errno = ENOMEM;
1396 }
1397 return r;
1398}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-10-26 22:50:00 +0000