libexec/rtld-elf/rtld_malloc.c

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