1d49ca25dSKonstantin Belousov /*- 2d49ca25dSKonstantin Belousov * SPDX-License-Identifier: BSD-3-Clause 3d49ca25dSKonstantin Belousov * 4d49ca25dSKonstantin Belousov * Copyright (c) 1983 Regents of the University of California. 5d49ca25dSKonstantin Belousov * All rights reserved. 6d49ca25dSKonstantin Belousov * 7d49ca25dSKonstantin Belousov * Redistribution and use in source and binary forms, with or without 8d49ca25dSKonstantin Belousov * modification, are permitted provided that the following conditions 9d49ca25dSKonstantin Belousov * are met: 10d49ca25dSKonstantin Belousov * 1. Redistributions of source code must retain the above copyright 11d49ca25dSKonstantin Belousov * notice, this list of conditions and the following disclaimer. 12d49ca25dSKonstantin Belousov * 2. Redistributions in binary form must reproduce the above copyright 13d49ca25dSKonstantin Belousov * notice, this list of conditions and the following disclaimer in the 14d49ca25dSKonstantin Belousov * documentation and/or other materials provided with the distribution. 15d49ca25dSKonstantin Belousov * 3. Neither the name of the University nor the names of its contributors 16d49ca25dSKonstantin Belousov * may be used to endorse or promote products derived from this software 17d49ca25dSKonstantin Belousov * without specific prior written permission. 18d49ca25dSKonstantin Belousov * 19d49ca25dSKonstantin Belousov * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20d49ca25dSKonstantin Belousov * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21d49ca25dSKonstantin Belousov * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22d49ca25dSKonstantin Belousov * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23d49ca25dSKonstantin Belousov * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24d49ca25dSKonstantin Belousov * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25d49ca25dSKonstantin Belousov * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26d49ca25dSKonstantin Belousov * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27d49ca25dSKonstantin Belousov * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28d49ca25dSKonstantin Belousov * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29d49ca25dSKonstantin Belousov * SUCH DAMAGE. 30d49ca25dSKonstantin Belousov */ 31d49ca25dSKonstantin Belousov 32d49ca25dSKonstantin Belousov #if defined(LIBC_SCCS) && !defined(lint) 33d49ca25dSKonstantin Belousov /*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/ 34d49ca25dSKonstantin Belousov static char *rcsid = "$FreeBSD$"; 35d49ca25dSKonstantin Belousov #endif /* LIBC_SCCS and not lint */ 36d49ca25dSKonstantin Belousov 37d49ca25dSKonstantin Belousov /* 38d49ca25dSKonstantin Belousov * malloc.c (Caltech) 2/21/82 39d49ca25dSKonstantin Belousov * Chris Kingsley, kingsley@cit-20. 40d49ca25dSKonstantin Belousov * 41d49ca25dSKonstantin Belousov * This is a very fast storage allocator. It allocates blocks of a small 42d49ca25dSKonstantin Belousov * number of different sizes, and keeps free lists of each size. Blocks that 43d49ca25dSKonstantin Belousov * don't exactly fit are passed up to the next larger size. In this 44d49ca25dSKonstantin Belousov * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. 45d49ca25dSKonstantin Belousov * This is designed for use in a virtual memory environment. 46d49ca25dSKonstantin Belousov */ 47d49ca25dSKonstantin Belousov 485cac2021SKonstantin Belousov #include <sys/param.h> 49d49ca25dSKonstantin Belousov #include <sys/sysctl.h> 505cac2021SKonstantin Belousov #include <sys/mman.h> 51d49ca25dSKonstantin Belousov #include <errno.h> 52d49ca25dSKonstantin Belousov #include <stdarg.h> 53d49ca25dSKonstantin Belousov #include <stddef.h> 54d49ca25dSKonstantin Belousov #include <string.h> 55d49ca25dSKonstantin Belousov #include <unistd.h> 56*bc7e8610SKonstantin Belousov #ifdef IN_RTLD 57d49ca25dSKonstantin Belousov #include "rtld.h" 58d49ca25dSKonstantin Belousov #include "rtld_printf.h" 5933dba3bbSKonstantin Belousov #include "rtld_paths.h" 60*bc7e8610SKonstantin Belousov #endif 61cf6dbdd1SKonstantin Belousov #include "rtld_malloc.h" 62d49ca25dSKonstantin Belousov 63d49ca25dSKonstantin Belousov /* 64d49ca25dSKonstantin Belousov * Pre-allocate mmap'ed pages 65d49ca25dSKonstantin Belousov */ 66d49ca25dSKonstantin Belousov #define NPOOLPAGES (128*1024/pagesz) 67d49ca25dSKonstantin Belousov static caddr_t pagepool_start, pagepool_end; 68d49ca25dSKonstantin Belousov 69d49ca25dSKonstantin Belousov /* 70d49ca25dSKonstantin Belousov * The overhead on a block is at least 4 bytes. When free, this space 71d49ca25dSKonstantin Belousov * contains a pointer to the next free block, and the bottom two bits must 72d49ca25dSKonstantin Belousov * be zero. When in use, the first byte is set to MAGIC, and the second 73d49ca25dSKonstantin Belousov * byte is the size index. The remaining bytes are for alignment. 74d49ca25dSKonstantin Belousov */ 75d49ca25dSKonstantin Belousov union overhead { 76d49ca25dSKonstantin Belousov union overhead *ov_next; /* when free */ 77d49ca25dSKonstantin Belousov struct { 78d49ca25dSKonstantin Belousov u_char ovu_magic; /* magic number */ 79d49ca25dSKonstantin Belousov u_char ovu_index; /* bucket # */ 80d49ca25dSKonstantin Belousov } ovu; 81d49ca25dSKonstantin Belousov #define ov_magic ovu.ovu_magic 82d49ca25dSKonstantin Belousov #define ov_index ovu.ovu_index 83d49ca25dSKonstantin Belousov }; 84d49ca25dSKonstantin Belousov 85d49ca25dSKonstantin Belousov static void morecore(int bucket); 86d49ca25dSKonstantin Belousov static int morepages(int n); 87d49ca25dSKonstantin Belousov 88d49ca25dSKonstantin Belousov #define MAGIC 0xef /* magic # on accounting info */ 89d49ca25dSKonstantin Belousov 90d49ca25dSKonstantin Belousov /* 9138915409SBrooks Davis * nextf[i] is the pointer to the next free block of size 9238915409SBrooks Davis * (FIRST_BUCKET_SIZE << i). The overhead information precedes the data 9338915409SBrooks Davis * area returned to the user. 94d49ca25dSKonstantin Belousov */ 9538915409SBrooks Davis #define FIRST_BUCKET_SIZE 8 96d49ca25dSKonstantin Belousov #define NBUCKETS 30 97d49ca25dSKonstantin Belousov static union overhead *nextf[NBUCKETS]; 98d49ca25dSKonstantin Belousov 99d49ca25dSKonstantin Belousov static int pagesz; /* page size */ 100d49ca25dSKonstantin Belousov 101d49ca25dSKonstantin Belousov /* 102d49ca25dSKonstantin Belousov * The array of supported page sizes is provided by the user, i.e., the 103d49ca25dSKonstantin Belousov * program that calls this storage allocator. That program must initialize 104d49ca25dSKonstantin Belousov * the array before making its first call to allocate storage. The array 105d49ca25dSKonstantin Belousov * must contain at least one page size. The page sizes must be stored in 106d49ca25dSKonstantin Belousov * increasing order. 107d49ca25dSKonstantin Belousov */ 108d49ca25dSKonstantin Belousov 109d49ca25dSKonstantin Belousov void * 110d49ca25dSKonstantin Belousov __crt_malloc(size_t nbytes) 111d49ca25dSKonstantin Belousov { 112d49ca25dSKonstantin Belousov union overhead *op; 113d49ca25dSKonstantin Belousov int bucket; 114d49ca25dSKonstantin Belousov size_t amt; 115d49ca25dSKonstantin Belousov 116d49ca25dSKonstantin Belousov /* 11738915409SBrooks Davis * First time malloc is called, setup page size. 118d49ca25dSKonstantin Belousov */ 11938915409SBrooks Davis if (pagesz == 0) 12038915409SBrooks Davis pagesz = pagesizes[0]; 121d49ca25dSKonstantin Belousov /* 122d49ca25dSKonstantin Belousov * Convert amount of memory requested into closest block size 123d49ca25dSKonstantin Belousov * stored in hash buckets which satisfies request. 124d49ca25dSKonstantin Belousov * Account for space used per block for accounting. 125d49ca25dSKonstantin Belousov */ 12638915409SBrooks Davis amt = FIRST_BUCKET_SIZE; 127d49ca25dSKonstantin Belousov bucket = 0; 12838915409SBrooks Davis while (nbytes > amt - sizeof(*op)) { 129d49ca25dSKonstantin Belousov amt <<= 1; 130d49ca25dSKonstantin Belousov bucket++; 13138915409SBrooks Davis if (amt == 0 || bucket >= NBUCKETS) 13238915409SBrooks Davis return (NULL); 133d49ca25dSKonstantin Belousov } 134d49ca25dSKonstantin Belousov /* 135d49ca25dSKonstantin Belousov * If nothing in hash bucket right now, 136d49ca25dSKonstantin Belousov * request more memory from the system. 137d49ca25dSKonstantin Belousov */ 138d49ca25dSKonstantin Belousov if ((op = nextf[bucket]) == NULL) { 139d49ca25dSKonstantin Belousov morecore(bucket); 140d49ca25dSKonstantin Belousov if ((op = nextf[bucket]) == NULL) 141d49ca25dSKonstantin Belousov return (NULL); 142d49ca25dSKonstantin Belousov } 143d49ca25dSKonstantin Belousov /* remove from linked list */ 144d49ca25dSKonstantin Belousov nextf[bucket] = op->ov_next; 145d49ca25dSKonstantin Belousov op->ov_magic = MAGIC; 146d49ca25dSKonstantin Belousov op->ov_index = bucket; 147d49ca25dSKonstantin Belousov return ((char *)(op + 1)); 148d49ca25dSKonstantin Belousov } 149d49ca25dSKonstantin Belousov 150d49ca25dSKonstantin Belousov void * 151d49ca25dSKonstantin Belousov __crt_calloc(size_t num, size_t size) 152d49ca25dSKonstantin Belousov { 153d49ca25dSKonstantin Belousov void *ret; 154d49ca25dSKonstantin Belousov 155d49ca25dSKonstantin Belousov if (size != 0 && (num * size) / size != num) { 156d49ca25dSKonstantin Belousov /* size_t overflow. */ 157d49ca25dSKonstantin Belousov return (NULL); 158d49ca25dSKonstantin Belousov } 159d49ca25dSKonstantin Belousov 160d49ca25dSKonstantin Belousov if ((ret = __crt_malloc(num * size)) != NULL) 161d49ca25dSKonstantin Belousov memset(ret, 0, num * size); 162d49ca25dSKonstantin Belousov 163d49ca25dSKonstantin Belousov return (ret); 164d49ca25dSKonstantin Belousov } 165d49ca25dSKonstantin Belousov 166d49ca25dSKonstantin Belousov /* 167d49ca25dSKonstantin Belousov * Allocate more memory to the indicated bucket. 168d49ca25dSKonstantin Belousov */ 169d49ca25dSKonstantin Belousov static void 170d49ca25dSKonstantin Belousov morecore(int bucket) 171d49ca25dSKonstantin Belousov { 172d49ca25dSKonstantin Belousov union overhead *op; 173d49ca25dSKonstantin Belousov int sz; /* size of desired block */ 174d49ca25dSKonstantin Belousov int amt; /* amount to allocate */ 175d49ca25dSKonstantin Belousov int nblks; /* how many blocks we get */ 176d49ca25dSKonstantin Belousov 17738915409SBrooks Davis sz = FIRST_BUCKET_SIZE << bucket; 178d49ca25dSKonstantin Belousov if (sz < pagesz) { 179d49ca25dSKonstantin Belousov amt = pagesz; 180d49ca25dSKonstantin Belousov nblks = amt / sz; 181d49ca25dSKonstantin Belousov } else { 18238915409SBrooks Davis amt = sz; 183d49ca25dSKonstantin Belousov nblks = 1; 184d49ca25dSKonstantin Belousov } 185d49ca25dSKonstantin Belousov if (amt > pagepool_end - pagepool_start) 18619e008e7SKonstantin Belousov if (morepages(amt / pagesz + NPOOLPAGES) == 0 && 18719e008e7SKonstantin Belousov /* Retry with min required size */ 18819e008e7SKonstantin Belousov morepages(amt / pagesz) == 0) 189d49ca25dSKonstantin Belousov return; 190d49ca25dSKonstantin Belousov op = (union overhead *)pagepool_start; 191d49ca25dSKonstantin Belousov pagepool_start += amt; 192d49ca25dSKonstantin Belousov 193d49ca25dSKonstantin Belousov /* 194d49ca25dSKonstantin Belousov * Add new memory allocated to that on 195d49ca25dSKonstantin Belousov * free list for this hash bucket. 196d49ca25dSKonstantin Belousov */ 197d49ca25dSKonstantin Belousov nextf[bucket] = op; 198d49ca25dSKonstantin Belousov while (--nblks > 0) { 199d49ca25dSKonstantin Belousov op->ov_next = (union overhead *)((caddr_t)op + sz); 200d49ca25dSKonstantin Belousov op = (union overhead *)((caddr_t)op + sz); 201d49ca25dSKonstantin Belousov } 202d49ca25dSKonstantin Belousov } 203d49ca25dSKonstantin Belousov 204d49ca25dSKonstantin Belousov void 205d49ca25dSKonstantin Belousov __crt_free(void *cp) 206d49ca25dSKonstantin Belousov { 207d49ca25dSKonstantin Belousov int size; 208d49ca25dSKonstantin Belousov union overhead *op; 209d49ca25dSKonstantin Belousov 210d49ca25dSKonstantin Belousov if (cp == NULL) 211d49ca25dSKonstantin Belousov return; 212d49ca25dSKonstantin Belousov op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 213d49ca25dSKonstantin Belousov if (op->ov_magic != MAGIC) 214d49ca25dSKonstantin Belousov return; /* sanity */ 215d49ca25dSKonstantin Belousov size = op->ov_index; 216d49ca25dSKonstantin Belousov op->ov_next = nextf[size]; /* also clobbers ov_magic */ 217d49ca25dSKonstantin Belousov nextf[size] = op; 218d49ca25dSKonstantin Belousov } 219d49ca25dSKonstantin Belousov 220d49ca25dSKonstantin Belousov void * 221d49ca25dSKonstantin Belousov __crt_realloc(void *cp, size_t nbytes) 222d49ca25dSKonstantin Belousov { 223d49ca25dSKonstantin Belousov u_int onb; 224d49ca25dSKonstantin Belousov int i; 225d49ca25dSKonstantin Belousov union overhead *op; 226d49ca25dSKonstantin Belousov char *res; 227d49ca25dSKonstantin Belousov 228d49ca25dSKonstantin Belousov if (cp == NULL) 229d49ca25dSKonstantin Belousov return (__crt_malloc(nbytes)); 230d49ca25dSKonstantin Belousov op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 23198ab7906SBrooks Davis if (op->ov_magic != MAGIC) 23298ab7906SBrooks Davis return (NULL); /* Double-free or bad argument */ 233d49ca25dSKonstantin Belousov i = op->ov_index; 234d49ca25dSKonstantin Belousov onb = 1 << (i + 3); 235d49ca25dSKonstantin Belousov if (onb < (u_int)pagesz) 2365cac2021SKonstantin Belousov onb -= sizeof(*op); 237d49ca25dSKonstantin Belousov else 2385cac2021SKonstantin Belousov onb += pagesz - sizeof(*op); 239d49ca25dSKonstantin Belousov /* avoid the copy if same size block */ 24098ab7906SBrooks Davis if (i != 0) { 241d49ca25dSKonstantin Belousov i = 1 << (i + 2); 242d49ca25dSKonstantin Belousov if (i < pagesz) 2435cac2021SKonstantin Belousov i -= sizeof(*op); 244d49ca25dSKonstantin Belousov else 2455cac2021SKonstantin Belousov i += pagesz - sizeof(*op); 246d49ca25dSKonstantin Belousov } 2475cac2021SKonstantin Belousov if (nbytes <= onb && nbytes > (size_t)i) 248d49ca25dSKonstantin Belousov return (cp); 249d49ca25dSKonstantin Belousov if ((res = __crt_malloc(nbytes)) == NULL) 250d49ca25dSKonstantin Belousov return (NULL); 251d49ca25dSKonstantin Belousov bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 25298ab7906SBrooks Davis __crt_free(cp); 253d49ca25dSKonstantin Belousov return (res); 254d49ca25dSKonstantin Belousov } 255d49ca25dSKonstantin Belousov 256d49ca25dSKonstantin Belousov static int 257d49ca25dSKonstantin Belousov morepages(int n) 258d49ca25dSKonstantin Belousov { 2593cac4083SKonstantin Belousov caddr_t addr; 260d49ca25dSKonstantin Belousov int offset; 261d49ca25dSKonstantin Belousov 262d49ca25dSKonstantin Belousov if (pagepool_end - pagepool_start > pagesz) { 2630b72d296SKonstantin Belousov addr = roundup2(pagepool_start, pagesz); 264d49ca25dSKonstantin Belousov if (munmap(addr, pagepool_end - addr) != 0) { 265d49ca25dSKonstantin Belousov #ifdef IN_RTLD 266d49ca25dSKonstantin Belousov rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": " 267d49ca25dSKonstantin Belousov "morepages: cannot munmap %p: %s\n", 268d49ca25dSKonstantin Belousov addr, rtld_strerror(errno)); 269d49ca25dSKonstantin Belousov #endif 270d49ca25dSKonstantin Belousov } 271d49ca25dSKonstantin Belousov } 272d49ca25dSKonstantin Belousov 2730b72d296SKonstantin Belousov offset = (uintptr_t)pagepool_start - rounddown2( 2740b72d296SKonstantin Belousov (uintptr_t)pagepool_start, pagesz); 275d49ca25dSKonstantin Belousov 27673dddffcSKonstantin Belousov addr = mmap(0, n * pagesz, PROT_READ | PROT_WRITE, 2773cac4083SKonstantin Belousov MAP_ANON | MAP_PRIVATE, -1, 0); 27873dddffcSKonstantin Belousov if (addr == MAP_FAILED) { 279d49ca25dSKonstantin Belousov #ifdef IN_RTLD 280d49ca25dSKonstantin Belousov rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": morepages: " 281d49ca25dSKonstantin Belousov "cannot mmap anonymous memory: %s\n", 282d49ca25dSKonstantin Belousov rtld_strerror(errno)); 283d49ca25dSKonstantin Belousov #endif 28473dddffcSKonstantin Belousov pagepool_start = pagepool_end = NULL; 2853cac4083SKonstantin Belousov return (0); 286d49ca25dSKonstantin Belousov } 28773dddffcSKonstantin Belousov pagepool_start = addr; 288d49ca25dSKonstantin Belousov pagepool_end = pagepool_start + n * pagesz; 289d49ca25dSKonstantin Belousov pagepool_start += offset; 290d49ca25dSKonstantin Belousov 2913cac4083SKonstantin Belousov return (n); 292d49ca25dSKonstantin Belousov } 293