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.c1325
1 files changed, 0 insertions, 1325 deletions
diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
deleted file mode 100644
index ae8cd8157b..0000000000
--- a/src/lib/libc/stdlib/malloc.c
+++ /dev/null
@@ -1,1325 +0,0 @@
1/* $OpenBSD: malloc.c,v 1.92 2008/07/28 04:56:38 otto Exp $ */
2/*
3 * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18/*
19 * Parts of this code, mainly the sub page sized chunk management code is
20 * derived from the malloc implementation with the following license:
21 */
22/*
23 * ----------------------------------------------------------------------------
24 * "THE BEER-WARE LICENSE" (Revision 42):
25 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
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 * ----------------------------------------------------------------------------
29 */
30
31/* #define MALLOC_STATS */
32
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>
39#include <stdlib.h>
40#include <string.h>
41#include <stdio.h>
42#include <unistd.h>
43
44#ifdef MALLOC_STATS
45#include <fcntl.h>
46#endif
47
48#include "thread_private.h"
49
50#define MALLOC_MINSHIFT 4
51#define MALLOC_MAXSHIFT 16
52
53#if defined(__sparc__) && !defined(__sparcv9__)
54#define MALLOC_PAGESHIFT (13U)
55#else
56#define MALLOC_PAGESHIFT (PGSHIFT)
57#endif
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
70/*
71 * What to use for Junk. This is the byte value we use to fill with
72 * when the 'J' option is enabled. Use SOME_JUNK right after alloc,
73 * and SOME_FREEJUNK right before free.
74 */
75#define SOME_JUNK 0xd0 /* as in "Duh" :-) */
76#define SOME_FREEJUNK 0xdf
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};
116
117
118/*
119 * This structure describes a page worth of chunks.
120 *
121 * How many bits per u_long in the bitmap
122 */
123#define MALLOC_BITS (NBBY * sizeof(u_long))
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 */
158#endif
159
160static size_t rbytesused; /* random bytes used */
161static u_char rbytes[4096]; /* random bytes */
162static u_char getrbyte(void);
163
164extern char *__progname;
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)
175{
176 size_t sum;
177 union {
178 uintptr_t p;
179 unsigned short a[sizeof(void *) / sizeof(short)];
180 } u;
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];
187#endif
188 return sum;
189}
190
191#ifdef MALLOC_STATS
192static void
193dump_chunk(int fd, struct chunk_info *p, int fromfreelist)
194{
195 char buf[64];
196
197 while (p) {
198 snprintf(buf, sizeof(buf), "chunk %d %d/%d %p\n", p->size,
199 p->free, p->total, p->page);
200 write(fd, buf, strlen(buf));
201 if (!fromfreelist)
202 break;
203 p = p->next;
204 if (p != NULL) {
205 snprintf(buf, sizeof(buf), " ");
206 write(fd, buf, strlen(buf));
207 }
208 }
209}
210
211static void
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);
225 }
226 }
227
228}
229
230static void
231dump_free_page_info(int fd, struct dir_info *d)
232{
233 char buf[64];
234 int i;
235
236 snprintf(buf, sizeof(buf), "Free pages cached: %zu\n",
237 d->free_regions_size);
238 write(fd, buf, strlen(buf));
239 for (i = 0; i < malloc_cache; i++) {
240 if (d->free_regions[i].p != NULL) {
241 snprintf(buf, sizeof(buf), "%2d) ", i);
242 write(fd, buf, strlen(buf));
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 }
247 }
248}
249
250static void
251malloc_dump1(int fd, struct dir_info *d)
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 }
289 }
290 dump_free_chunk_info(fd, d);
291 dump_free_page_info(fd, d);
292 snprintf(buf, sizeof(buf), "In use %zu\n", malloc_used);
293 write(fd, buf, strlen(buf));
294 snprintf(buf, sizeof(buf), "Guarded %zu\n", malloc_guarded);
295 write(fd, buf, strlen(buf));
296}
297
298
299void
300malloc_dump(int fd)
301{
302 malloc_dump1(fd, &g_pool);
303}
304
305static void
306malloc_exit(void)
307{
308 char *q = "malloc() warning: Couldn't dump stats\n";
309 int save_errno = errno, fd;
310
311 fd = open("malloc.out", O_RDWR|O_APPEND);
312 if (fd != -1) {
313 malloc_dump(fd);
314 close(fd);
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);
373}
374
375/*
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.
381 */
382static void
383unmap(struct dir_info *d, void *p, size_t sz)
384{
385 size_t psz = PAGEROUND(sz) >> MALLOC_PAGESHIFT;
386 size_t rsz, tounmap;
387 struct region_info *r;
388 u_int i, offset;
389
390 if (psz > malloc_cache) {
391 if (munmap(p, sz))
392 wrterror("unmap");
393 malloc_used -= sz;
394 return;
395 }
396 tounmap = 0;
397 rsz = malloc_cache - d->free_regions_size;
398 if (psz > rsz)
399 tounmap = psz - rsz;
400 d->free_regions_size -= tounmap;
401 offset = getrbyte();
402 for (i = 0; tounmap > 0 && i < malloc_cache; i++) {
403 r = &d->free_regions[(i + offset) & (malloc_cache - 1)];
404 if (r->p != NULL) {
405 if (r->size <= tounmap) {
406 rsz = r->size << MALLOC_PAGESHIFT;
407 if (munmap(r->p, rsz))
408 wrterror("munmap");
409 tounmap -= r->size;
410 r->p = NULL;
411 r->size = 0;
412 malloc_used -= rsz;
413 } else {
414 rsz = tounmap << MALLOC_PAGESHIFT;
415 if (munmap((char *)r->p + ((r->size - tounmap)
416 << MALLOC_PAGESHIFT), rsz))
417 wrterror("munmap");
418 r->size -= tounmap ;
419 tounmap = 0;
420 malloc_used -= rsz;
421 }
422 }
423 }
424 if (tounmap > 0)
425 wrtwarning("malloc cache underflow");
426 for (i = 0; i < malloc_cache; i++) {
427 r = &d->free_regions[i];
428 if (r->p == NULL) {
429 if (malloc_hint)
430 madvise(p, sz, MADV_FREE);
431 if (malloc_freeprot)
432 mprotect(p, sz, PROT_NONE);
433 r->p = p;
434 r->size = psz;
435 d->free_regions_size += psz;
436 break;
437 }
438 }
439 if (i == malloc_cache)
440 wrtwarning("malloc free slot lost");
441 if (d->free_regions_size > malloc_cache)
442 wrtwarning("malloc cache overflow");
443}
444
445static void *
446map(struct dir_info *d, size_t sz)
447{
448 size_t psz = PAGEROUND(sz) >> MALLOC_PAGESHIFT;
449 struct region_info *r, *big = NULL;
450 u_int i, offset;
451 void *p;
452
453 if (psz > d->free_regions_size) {
454 p = MMAP(sz);
455 if (p != MAP_FAILED)
456 malloc_used += sz;
457 return p;
458 }
459 offset = getrbyte();
460 for (i = 0; i < malloc_cache; i++) {
461 r = &d->free_regions[(i + offset) & (malloc_cache - 1)];
462 if (r->p != NULL) {
463 if (r->size == psz) {
464 p = r->p;
465 if (malloc_freeprot)
466 mprotect(p, sz, PROT_READ | PROT_WRITE);
467 if (malloc_hint)
468 madvise(p, sz, MADV_NORMAL);
469 r->p = NULL;
470 r->size = 0;
471 d->free_regions_size -= psz;
472 return p;
473 } else if (r->size > psz)
474 big = r;
475 }
476 }
477 if (big != NULL) {
478 r = big;
479 p = (char *)r->p + ((r->size - psz) << MALLOC_PAGESHIFT);
480 if (malloc_freeprot)
481 mprotect(p, sz, PROT_READ | PROT_WRITE);
482 if (malloc_hint)
483 madvise(p, sz, MADV_NORMAL);
484 r->size -= psz;
485 d->free_regions_size -= psz;
486 return p;
487 }
488 p = MMAP(sz);
489 if (p != MAP_FAILED)
490 malloc_used += sz;
491 if (d->free_regions_size > malloc_cache)
492 wrtwarning("malloc cache");
493 return p;
494}
495
496static void
497rbytes_init(void)
498{
499 arc4random_buf(rbytes, sizeof(rbytes));
500 rbytesused = 0;
501}
502
503static u_char
504getrbyte(void)
505{
506 if (rbytesused >= sizeof(rbytes))
507 rbytes_init();
508 return rbytes[rbytesused++];
509}
510
511/*
512 * Initialize a dir_info, which should have been cleared by caller
513 */
514static int
515omalloc_init(struct dir_info *d)
516{
517 char *p, b[64];
518 int i, j, save_errno = errno;
519 size_t regioninfo_size;
520
521 rbytes_init();
522
523 for (i = 0; i < 3; i++) {
524 switch (i) {
525 case 0:
526 j = readlink("/etc/malloc.conf", b, sizeof b - 1);
527 if (j <= 0)
528 continue;
529 b[j] = '\0';
530 p = b;
531 break;
532 case 1:
533 if (issetugid() == 0)
534 p = getenv("MALLOC_OPTIONS");
535 else
536 continue;
537 break;
538 case 2:
539 p = malloc_options;
540 break;
541 default:
542 p = NULL;
543 }
544
545 for (; p != NULL && *p != '\0'; p++) {
546 switch (*p) {
547 case '>':
548 malloc_cache <<= 1;
549 if (malloc_cache > MALLOC_MAXCACHE)
550 malloc_cache = MALLOC_MAXCACHE;
551 break;
552 case '<':
553 malloc_cache >>= 1;
554 break;
555 case 'a':
556 malloc_abort = 0;
557 break;
558 case 'A':
559 malloc_abort = 1;
560 break;
561#ifdef MALLOC_STATS
562 case 'd':
563 malloc_stats = 0;
564 break;
565 case 'D':
566 malloc_stats = 1;
567 break;
568#endif /* MALLOC_STATS */
569 case 'f':
570 malloc_freeprot = 0;
571 break;
572 case 'F':
573 malloc_freeprot = 1;
574 break;
575 case 'g':
576 malloc_guard = 0;
577 break;
578 case 'G':
579 malloc_guard = MALLOC_PAGESIZE;
580 break;
581 case 'h':
582 malloc_hint = 0;
583 break;
584 case 'H':
585 malloc_hint = 1;
586 break;
587 case 'j':
588 malloc_junk = 0;
589 break;
590 case 'J':
591 malloc_junk = 1;
592 break;
593 case 'n':
594 malloc_silent = 0;
595 break;
596 case 'N':
597 malloc_silent = 1;
598 break;
599 case 'p':
600 malloc_move = 0;
601 break;
602 case 'P':
603 malloc_move = 1;
604 break;
605 case 'r':
606 malloc_realloc = 0;
607 break;
608 case 'R':
609 malloc_realloc = 1;
610 break;
611 case 'x':
612 malloc_xmalloc = 0;
613 break;
614 case 'X':
615 malloc_xmalloc = 1;
616 break;
617 case 'z':
618 malloc_zero = 0;
619 break;
620 case 'Z':
621 malloc_zero = 1;
622 break;
623 default:
624 j = malloc_abort;
625 malloc_abort = 0;
626 wrtwarning("unknown char in MALLOC_OPTIONS");
627 malloc_abort = j;
628 break;
629 }
630 }
631 }
632
633 /*
634 * We want junk in the entire allocation, and zero only in the part
635 * the user asked for.
636 */
637 if (malloc_zero)
638 malloc_junk = 1;
639
640#ifdef MALLOC_STATS
641 if (malloc_stats && (atexit(malloc_exit) == -1))
642 wrtwarning("atexit(2) failed."
643 " Will not be able to dump malloc stats on exit");
644#endif /* MALLOC_STATS */
645
646 errno = save_errno;
647
648 d->regions_bits = 9;
649 d->regions_free = d->regions_total = 1 << d->regions_bits;
650 regioninfo_size = d->regions_total * sizeof(struct region_info);
651 d->r = MMAP(regioninfo_size);
652 if (d->r == MAP_FAILED) {
653 wrterror("malloc init mmap failed");
654 d->regions_total = 0;
655 return 1;
656 }
657 malloc_used += regioninfo_size;
658 memset(d->r, 0, regioninfo_size);
659 d->canary1 = arc4random();
660 d->canary2 = ~d->canary1;
661 return 0;
662}
663
664static int
665omalloc_grow(struct dir_info *d)
666{
667 size_t newbits;
668 size_t newtotal;
669 size_t newsize;
670 size_t mask;
671 size_t i;
672 struct region_info *p;
673
674 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2 )
675 return 1;
676
677 newbits = d->regions_bits + 1;
678 newtotal = d->regions_total * 2;
679 newsize = newtotal * sizeof(struct region_info);
680 mask = newtotal - 1;
681
682 p = MMAP(newsize);
683 if (p == MAP_FAILED)
684 return 1;
685
686 malloc_used += newsize;
687 memset(p, 0, newsize);
688 STATS_ZERO(d->inserts);
689 STATS_ZERO(d->insert_collisions);
690 for (i = 0; i < d->regions_total; i++) {
691 void *q = d->r[i].p;
692 if (q != NULL) {
693 size_t index = hash(q) & mask;
694 STATS_INC(d->inserts);
695 while (p[index].p != NULL) {
696 index = (index - 1) & mask;
697 STATS_INC(d->insert_collisions);
698 }
699 p[index] = d->r[i];
700 }
701 }
702 /* avoid pages containing meta info to end up in cache */
703 if (munmap(d->r, d->regions_total * sizeof(struct region_info)))
704 wrterror("omalloc_grow munmap");
705 else
706 malloc_used -= d->regions_total * sizeof(struct region_info);
707 d->regions_free = d->regions_free + d->regions_total;
708 d->regions_total = newtotal;
709 d->regions_bits = newbits;
710 d->r = p;
711 return 0;
712}
713
714static struct chunk_info *
715alloc_chunk_info(struct dir_info *d)
716{
717 struct chunk_info *p;
718 int i;
719
720 if (d->chunk_info_list == NULL) {
721 p = MMAP(MALLOC_PAGESIZE);
722 if (p == MAP_FAILED)
723 return NULL;
724 malloc_used += MALLOC_PAGESIZE;
725 for (i = 0; i < MALLOC_PAGESIZE / sizeof(*p); i++) {
726 p[i].next = d->chunk_info_list;
727 d->chunk_info_list = &p[i];
728 }
729 }
730 p = d->chunk_info_list;
731 d->chunk_info_list = p->next;
732 memset(p, 0, sizeof *p);
733 p->canary = d->canary1;
734 return p;
735}
736
737
738static void
739put_chunk_info(struct dir_info *d, struct chunk_info *p)
740{
741 p->next = d->chunk_info_list;
742 d->chunk_info_list = p;
743}
744
745static int
746insert(struct dir_info *d, void *p, size_t sz)
747{
748 size_t index;
749 size_t mask;
750 void *q;
751
752 if (d->regions_free * 4 < d->regions_total) {
753 if (omalloc_grow(d))
754 return 1;
755 }
756 mask = d->regions_total - 1;
757 index = hash(p) & mask;
758 q = d->r[index].p;
759 STATS_INC(d->inserts);
760 while (q != NULL) {
761 index = (index - 1) & mask;
762 q = d->r[index].p;
763 STATS_INC(d->insert_collisions);
764 }
765 d->r[index].p = p;
766 d->r[index].size = sz;
767 d->regions_free--;
768 return 0;
769}
770
771static struct region_info *
772find(struct dir_info *d, void *p)
773{
774 size_t index;
775 size_t mask = d->regions_total - 1;
776 void *q, *r;
777
778 if (d->canary1 != ~d->canary2)
779 wrterror("internal struct corrupt");
780 p = MASK_POINTER(p);
781 index = hash(p) & mask;
782 r = d->r[index].p;
783 q = MASK_POINTER(r);
784 STATS_INC(d->finds);
785 while (q != p && r != NULL) {
786 index = (index - 1) & mask;
787 r = d->r[index].p;
788 q = MASK_POINTER(r);
789 STATS_INC(d->find_collisions);
790 }
791 return q == p ? &d->r[index] : NULL;
792}
793
794static void
795delete(struct dir_info *d, struct region_info *ri)
796{
797 /* algorithm R, Knuth Vol III section 6.4 */
798 size_t mask = d->regions_total - 1;
799 size_t i, j, r;
800
801 if (d->regions_total & (d->regions_total - 1))
802 wrterror("regions_total not 2^x");
803 d->regions_free++;
804 STATS_INC(g_pool.deletes);
805
806 i = ri - d->r;
807 for (;;) {
808 d->r[i].p = NULL;
809 d->r[i].size = 0;
810 j = i;
811 for (;;) {
812 i = (i - 1) & mask;
813 if (d->r[i].p == NULL)
814 return;
815 r = hash(d->r[i].p) & mask;
816 if ((i <= r && r < j) || (r < j && j < i) ||
817 (j < i && i <= r))
818 continue;
819 d->r[j] = d->r[i];
820 STATS_INC(g_pool.delete_moves);
821 break;
822 }
823
824 }
825}
826
827/*
828 * Allocate a page of chunks
829 */
830static struct chunk_info *
831omalloc_make_chunks(struct dir_info *d, int bits)
832{
833 struct chunk_info *bp;
834 void *pp;
835 long i, k;
836
837 /* Allocate a new bucket */
838 pp = map(d, MALLOC_PAGESIZE);
839 if (pp == MAP_FAILED)
840 return NULL;
841
842 bp = alloc_chunk_info(d);
843 if (bp == NULL) {
844 unmap(d, pp, MALLOC_PAGESIZE);
845 return NULL;
846 }
847
848 /* memory protect the page allocated in the malloc(0) case */
849 if (bits == 0) {
850 bp->size = 0;
851 bp->shift = 1;
852 i = MALLOC_MINSIZE - 1;
853 while (i >>= 1)
854 bp->shift++;
855 bp->total = bp->free = MALLOC_PAGESIZE >> bp->shift;
856 bp->page = pp;
857
858 k = mprotect(pp, MALLOC_PAGESIZE, PROT_NONE);
859 if (k < 0) {
860 unmap(d, pp, MALLOC_PAGESIZE);
861 put_chunk_info(d, bp);
862 return NULL;
863 }
864 } else {
865 bp->size = (1UL << bits);
866 bp->shift = bits;
867 bp->total = bp->free = MALLOC_PAGESIZE >> bits;
868 bp->page = pp;
869 }
870
871 /* set all valid bits in the bitmap */
872 k = bp->total;
873 i = 0;
874
875 /* Do a bunch at a time */
876 for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
877 bp->bits[i / MALLOC_BITS] = ~0UL;
878
879 for (; i < k; i++)
880 bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
881
882 bp->next = d->chunk_dir[bits];
883 d->chunk_dir[bits] = bp;
884
885 bits++;
886 if ((uintptr_t)pp & bits)
887 wrterror("pp & bits");
888
889 insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp);
890 return bp;
891}
892
893
894/*
895 * Allocate a chunk
896 */
897static void *
898malloc_bytes(struct dir_info *d, size_t size)
899{
900 int i, j;
901 size_t k;
902 u_long u, *lp;
903 struct chunk_info *bp;
904
905 /* Don't bother with anything less than this */
906 /* unless we have a malloc(0) requests */
907 if (size != 0 && size < MALLOC_MINSIZE)
908 size = MALLOC_MINSIZE;
909
910 /* Find the right bucket */
911 if (size == 0)
912 j = 0;
913 else {
914 j = MALLOC_MINSHIFT;
915 i = (size - 1) >> (MALLOC_MINSHIFT - 1);
916 while (i >>= 1)
917 j++;
918 }
919
920 /* If it's empty, make a page more of that size chunks */
921 bp = d->chunk_dir[j];
922 if (bp == NULL && (bp = omalloc_make_chunks(d, j)) == NULL)
923 return NULL;
924
925 if (bp->canary != d->canary1)
926 wrterror("chunk info corrupted");
927 /* Find first word of bitmap which isn't empty */
928 for (lp = bp->bits; !*lp; lp++)
929 /* EMPTY */;
930
931 /* Find that bit, and tweak it */
932 u = 1;
933 k = 0;
934 while (!(*lp & u)) {
935 u += u;
936 k++;
937 }
938
939 /* advance a random # of positions */
940 i = (getrbyte() & (MALLOC_DELAYED_CHUNKS - 1)) % bp->free;
941 while (i > 0) {
942 u += u;
943 k++;
944 if (k >= MALLOC_BITS) {
945 lp++;
946 u = 1;
947 k = 0;
948 }
949 if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
950 wrterror("chunk overflow");
951 errno = EFAULT;
952 return (NULL);
953 }
954 if (*lp & u)
955 i--;
956 }
957
958 *lp ^= u;
959
960 /* If there are no more free, remove from free-list */
961 if (!--bp->free) {
962 d->chunk_dir[j] = bp->next;
963 bp->next = NULL;
964 }
965 /* Adjust to the real offset of that chunk */
966 k += (lp - bp->bits) * MALLOC_BITS;
967 k <<= bp->shift;
968
969 if (malloc_junk && bp->size > 0)
970 memset((char *)bp->page + k, SOME_JUNK, bp->size);
971 return ((char *)bp->page + k);
972}
973
974
975/*
976 * Free a chunk, and possibly the page it's on, if the page becomes empty.
977 */
978static void
979free_bytes(struct dir_info *d, struct region_info *r, void *ptr)
980{
981 struct chunk_info *info, **mp;
982 long i;
983
984 info = (struct chunk_info *)r->size;
985 if (info->canary != d->canary1)
986 wrterror("chunk info corrupted");
987
988 /* Find the chunk number on the page */
989 i = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift;
990
991 if ((uintptr_t)ptr & ((1UL << (info->shift)) - 1)) {
992 wrtwarning("modified (chunk-) pointer");
993 return;
994 }
995 if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
996 wrtwarning("chunk is already free");
997 return;
998 }
999
1000 info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
1001 info->free++;
1002
1003 if (info->size != 0)
1004 mp = d->chunk_dir + info->shift;
1005 else
1006 mp = d->chunk_dir;
1007
1008 if (info->free == 1) {
1009 /* Page became non-full */
1010
1011 /* Insert in address order */
1012 while (*mp != NULL && (*mp)->next != NULL &&
1013 (*mp)->next->page < info->page)
1014 mp = &(*mp)->next;
1015 info->next = *mp;
1016 *mp = info;
1017 return;
1018 }
1019 if (info->free != info->total)
1020 return;
1021
1022 /* Find & remove this page in the queue */
1023 while (*mp != info) {
1024 mp = &((*mp)->next);
1025 if (!*mp) {
1026 wrterror("not on queue");
1027 errno = EFAULT;
1028 return;
1029 }
1030 }
1031 *mp = info->next;
1032
1033 if (info->size == 0 && !malloc_freeprot)
1034 mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE);
1035 unmap(d, info->page, MALLOC_PAGESIZE);
1036
1037 delete(d, r);
1038 put_chunk_info(d, info);
1039}
1040
1041
1042
1043static void *
1044omalloc(size_t sz, int zero_fill)
1045{
1046 void *p;
1047 size_t psz;
1048
1049 if (sz > MALLOC_MAXCHUNK) {
1050 if (sz >= SIZE_MAX - malloc_guard - MALLOC_PAGESIZE) {
1051 errno = ENOMEM;
1052 return NULL;
1053 }
1054 sz += malloc_guard;
1055 psz = PAGEROUND(sz);
1056 p = map(&g_pool, psz);
1057 if (p == MAP_FAILED) {
1058 errno = ENOMEM;
1059 return NULL;
1060 }
1061 if (insert(&g_pool, p, sz)) {
1062 unmap(&g_pool, p, sz);
1063 errno = ENOMEM;
1064 return NULL;
1065 }
1066 if (malloc_guard) {
1067 if (mprotect((char *)p + psz - malloc_guard,
1068 malloc_guard, PROT_NONE))
1069 wrterror("mprotect");
1070 malloc_guarded += malloc_guard;
1071 }
1072 if (malloc_junk)
1073 memset(p, SOME_JUNK, psz - malloc_guard);
1074
1075 /* shift towards the end */
1076 if (malloc_move &&
1077 sz - malloc_guard < MALLOC_PAGESIZE - MALLOC_MINSIZE)
1078 p = ((char *)p) + ((MALLOC_PAGESIZE - MALLOC_MINSIZE -
1079 (sz - malloc_guard)) & ~(MALLOC_MINSIZE-1));
1080 if (zero_fill)
1081 memset(p, 0, sz - malloc_guard);
1082 } else {
1083 /* takes care of SOME_JUNK */
1084 p = malloc_bytes(&g_pool, sz);
1085 if (zero_fill && p != NULL && sz > 0)
1086 memset(p, 0, sz);
1087 }
1088
1089 return p;
1090}
1091
1092/*
1093 * Common function for handling recursion. Only
1094 * print the error message once, to avoid making the problem
1095 * potentially worse.
1096 */
1097static void
1098malloc_recurse(void)
1099{
1100 static int noprint;
1101
1102 if (noprint == 0) {
1103 noprint = 1;
1104 wrtwarning("recursive call");
1105 }
1106 malloc_active--;
1107 _MALLOC_UNLOCK();
1108 errno = EDEADLK;
1109}
1110
1111void *
1112malloc(size_t size)
1113{
1114 void *r;
1115
1116 _MALLOC_LOCK();
1117 malloc_func = " in malloc():";
1118 if (!g_pool.regions_total) {
1119 if (omalloc_init(&g_pool)) {
1120 _MALLOC_UNLOCK();
1121 if (malloc_xmalloc)
1122 wrterror("out of memory");
1123 errno = ENOMEM;
1124 return NULL;
1125 }
1126 }
1127 if (malloc_active++) {
1128 malloc_recurse();
1129 return NULL;
1130 }
1131 r = omalloc(size, malloc_zero);
1132 malloc_active--;
1133 _MALLOC_UNLOCK();
1134 if (r == NULL && malloc_xmalloc) {
1135 wrterror("out of memory");
1136 errno = ENOMEM;
1137 }
1138 return r;
1139}
1140
1141static void
1142ofree(void *p)
1143{
1144 struct region_info *r;
1145 size_t sz;
1146
1147 r = find(&g_pool, p);
1148 if (r == NULL) {
1149 wrtwarning("bogus pointer (double free?)");
1150 return;
1151 }
1152 REALSIZE(sz, r);
1153 if (sz > MALLOC_MAXCHUNK) {
1154 if (sz - malloc_guard >= MALLOC_PAGESIZE - MALLOC_MINSIZE) {
1155 if (r->p != p)
1156 wrtwarning("bogus pointer");
1157 } else {
1158#if notyetbecause_of_realloc
1159 /* shifted towards the end */
1160 if (p != ((char *)r->p) + ((MALLOC_PAGESIZE -
1161 MALLOC_MINSIZE - sz - malloc_guard) &
1162 ~(MALLOC_MINSIZE-1))) {
1163 }
1164#endif
1165 p = r->p;
1166 }
1167 if (malloc_guard) {
1168 if (sz < malloc_guard)
1169 wrtwarning("guard size");
1170 if (!malloc_freeprot) {
1171 if (mprotect((char *)p + PAGEROUND(sz) -
1172 malloc_guard, malloc_guard,
1173 PROT_READ | PROT_WRITE))
1174 wrterror("mprotect");
1175 }
1176 malloc_guarded -= malloc_guard;
1177 }
1178 if (malloc_junk)
1179 memset(p, SOME_FREEJUNK, PAGEROUND(sz) - malloc_guard);
1180 unmap(&g_pool, p, sz);
1181 delete(&g_pool, r);
1182 } else {
1183 void *tmp;
1184 int i;
1185
1186 if (malloc_junk && sz > 0)
1187 memset(p, SOME_FREEJUNK, sz);
1188 i = getrbyte() & (MALLOC_DELAYED_CHUNKS - 1);
1189 tmp = p;
1190 p = g_pool.delayed_chunks[i];
1191 g_pool.delayed_chunks[i] = tmp;
1192 if (p != NULL) {
1193 r = find(&g_pool, p);
1194 if (r == NULL) {
1195 wrtwarning("bogus pointer (double free?)");
1196 return;
1197 }
1198 free_bytes(&g_pool, r, p);
1199 }
1200 }
1201}
1202
1203void
1204free(void *ptr)
1205{
1206 /* This is legal. */
1207 if (ptr == NULL)
1208 return;
1209
1210 _MALLOC_LOCK();
1211 malloc_func = " in free():";
1212 if (malloc_active++) {
1213 malloc_recurse();
1214 return;
1215 }
1216 ofree(ptr);
1217 malloc_active--;
1218 _MALLOC_UNLOCK();
1219}
1220
1221
1222static void *
1223orealloc(void *p, size_t newsz)
1224{
1225 struct region_info *r;
1226 size_t oldsz, goldsz, gnewsz;
1227 void *q;
1228
1229 if (p == NULL)
1230 return omalloc(newsz, 0);
1231
1232 r = find(&g_pool, p);
1233 if (r == NULL) {
1234 wrtwarning("bogus pointer (double free?)");
1235 return NULL;
1236 }
1237 if (newsz >= SIZE_MAX - malloc_guard - MALLOC_PAGESIZE) {
1238 errno = ENOMEM;
1239 return NULL;
1240 }
1241
1242 REALSIZE(oldsz, r);
1243 goldsz = oldsz;
1244 if (oldsz > MALLOC_MAXCHUNK) {
1245 if (oldsz < malloc_guard)
1246 wrtwarning("guard size");
1247 oldsz -= malloc_guard;
1248 }
1249
1250 gnewsz = newsz;
1251 if (gnewsz > MALLOC_MAXCHUNK)
1252 gnewsz += malloc_guard;
1253
1254 if (newsz > MALLOC_MAXCHUNK && oldsz > MALLOC_MAXCHUNK && p == r->p &&
1255 !malloc_realloc) {
1256 size_t roldsz = PAGEROUND(goldsz);
1257 size_t rnewsz = PAGEROUND(gnewsz);
1258
1259 if (rnewsz < roldsz) {
1260 if (malloc_guard) {
1261 if (mprotect((char *)p + roldsz - malloc_guard,
1262 malloc_guard, PROT_READ | PROT_WRITE))
1263 wrterror("mprotect");
1264 if (mprotect((char *)p + rnewsz - malloc_guard,
1265 malloc_guard, PROT_NONE))
1266 wrterror("mprotect");
1267 }
1268 unmap(&g_pool, (char *)p + rnewsz, roldsz - rnewsz);
1269 r->size = gnewsz;
1270 return p;
1271 } else if (rnewsz == roldsz) {
1272 if (newsz > oldsz && malloc_junk)
1273 memset((char *)p + newsz, SOME_JUNK,
1274 rnewsz - malloc_guard - newsz);
1275 r->size = gnewsz;
1276 return p;
1277 }
1278 }
1279 if (newsz <= oldsz && newsz > oldsz / 2 && !malloc_realloc) {
1280 if (malloc_junk && newsz > 0)
1281 memset((char *)p + newsz, SOME_JUNK, oldsz - newsz);
1282 return p;
1283 } else if (newsz != oldsz || malloc_realloc) {
1284 q = omalloc(newsz, 0);
1285 if (q == NULL)
1286 return NULL;
1287 if (newsz != 0 && oldsz != 0)
1288 memcpy(q, p, oldsz < newsz ? oldsz : newsz);
1289 ofree(p);
1290 return q;
1291 } else
1292 return p;
1293}
1294
1295void *
1296realloc(void *ptr, size_t size)
1297{
1298 void *r;
1299
1300 _MALLOC_LOCK();
1301 malloc_func = " in realloc():";
1302 if (!g_pool.regions_total) {
1303 if (omalloc_init(&g_pool)) {
1304 _MALLOC_UNLOCK();
1305 if (malloc_xmalloc)
1306 wrterror("out of memory");
1307 errno = ENOMEM;
1308 return NULL;
1309 }
1310 }
1311 if (malloc_active++) {
1312 malloc_recurse();
1313 return NULL;
1314 }
1315
1316 r = orealloc(ptr, size);
1317
1318 malloc_active--;
1319 _MALLOC_UNLOCK();
1320 if (r == NULL && malloc_xmalloc) {
1321 wrterror("out of memory");
1322 errno = ENOMEM;
1323 }
1324 return r;
1325}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2026-08-31 04:41:33 +0000