usr/src/cmd/sgs/rtld/common/malloc.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21
  22 /*
  23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 /*
  28  *      Copyright (c) 1988 AT&T
  29  *        All Rights Reserved
  30  */
  31
  32 /*
  33  * Simplified version of malloc(), calloc() and free(), to be linked with
  34  * utilities that use [s]brk() and do not define their own version of the
  35  * routines.
  36  * The algorithm maps /dev/zero to get extra memory space.
  37  * Each call to mmap() creates a page. The pages are linked in a list.
  38  * Each page is divided in blocks. There is at least one block in a page.
  39  * New memory chunks are allocated on a first-fit basis.
  40  * Freed blocks are joined in larger blocks. Free pages are unmapped.
  41  */
  42
  43 #include        <stdlib.h>
  44 #include        <sys/types.h>
  45 #include        <sys/mman.h>
  46 #include        <sys/debug.h>
  47 #include        <memory.h>
  48 #include        "_rtld.h"
  49 #include        "msg.h"
  50
  51 struct block {
  52         size_t          size;           /* Space available for user */
  53         struct page     *page;          /* Backwards reference to page */
  54         int             status;
  55         struct block    *next;
  56         void *          memstart[1];
  57 };
  58
  59 struct page {
  60         size_t          size;           /* Total page size (incl. header) */
  61         struct page     *next;
  62         struct block    block[1];
  63 };
  64
  65 #define FREE    0
  66 #define BUSY    1
  67
  68 #define HDR_BLOCK       (sizeof (struct block) - sizeof (void *))
  69 #define HDR_PAGE        (sizeof (struct page) - sizeof (void *))
  70
  71 static struct page      *memstart;
  72
  73 #if     DEBUG
  74 /*
  75  * When built for debugging, scribble a pattern over newly allocated and
  76  * freed memory.
  77  */
  78 #define NEWMEM          0
  79 #define FREMEM          1
  80
  81 /* LINTED */
  82 const ulong_t   patterns[] = {
  83         (ulong_t)0xbaddcafebaddcafeULL, (ulong_t)0xdeadbeefdeadbeefULL
  84 };
  85
  86 static void
  87 scribble(ulong_t *membgn, int pattern, size_t size)
  88 {
  89         size_t  memsize = size / sizeof (ulong_t);
  90
  91         while (memsize--) {
  92                 if (pattern == FREMEM)
  93                         ASSERT(*membgn != patterns[pattern]);
  94                 *membgn++ = patterns[pattern];
  95         }
  96 }
  97 #endif
  98
  99 /*
 100  * Defragmentation
 101  */
 102 void
 103 defrag()
 104 {
 105         struct page     *page;
 106         Aliste          idx;
 107
 108         for (APLIST_TRAVERSE(free_alp, idx, page)) {
 109                 struct block    *block;
 110
 111                 for (block = page->block; block; block = block->next) {
 112                         struct block    *block2;
 113
 114                         if (block->status == BUSY)
 115                                 continue;
 116                         for (block2 = block->next; block2 &&
 117                             block2->status == FREE; block2 = block2->next) {
 118                                 block->next = block2->next;
 119                                 block->size += block2->size + HDR_BLOCK;
 120                         }
 121                 }
 122
 123                 /*
 124                  * If a page becomes free, leave it, and save the unmapping
 125                  * expense, as we'll probably come back and reclaim the page
 126                  * for later malloc activity.
 127                  *
 128                  * Free the defrag index.
 129                  */
 130                 aplist_delete(free_alp, &idx);
 131         }
 132 }
 133
 134 static void
 135 split(struct block *block, size_t size)
 136 {
 137         if (block->size > size + sizeof (struct block)) {
 138                 struct block    *newblock;
 139                 /* LINTED */
 140                 newblock = (struct block *)
 141                     ((char *)block + HDR_BLOCK + size);
 142                 newblock->next = block->next;
 143                 block->next = newblock;
 144                 newblock->status = FREE;
 145                 newblock->page = block->page;
 146                 newblock->size = block->size - size - HDR_BLOCK;
 147                 block->size = size;
 148         }
 149 }
 150
 151 #include <stdio.h>
 152
 153 /*
 154  * Replace both malloc() and lmalloc() (libc's private memory allocator).
 155  * They are both private here.
 156  */
 157 #pragma weak lmalloc = malloc
 158 void *
 159 malloc(size_t size)
 160 {
 161         struct block    *block;
 162         struct page     *page;
 163
 164         size = S_DROUND(size);
 165
 166         /*
 167          * Try to locate necessary space
 168          */
 169         for (page = memstart; page; page = page->next) {
 170                 for (block = page->block; block; block = block->next) {
 171                         if ((block->status == FREE) && (block->size >= size))
 172                                 goto found;
 173                 }
 174         }
 175 found:
 176         /*
 177          * Need to allocate a new page
 178          */
 179         if (!page) {
 180                 size_t  totsize = size + HDR_PAGE;
 181                 size_t  totpage = S_ROUND(totsize, syspagsz);
 182
 183                 if ((page = dz_map(0, 0, totpage,
 184                     PROT_READ | PROT_WRITE | PROT_EXEC,
 185                     MAP_PRIVATE)) == MAP_FAILED)
 186                         return (0);
 187
 188                 page->next = memstart;
 189                 memstart = page;
 190                 page->size = totpage;
 191                 block = page->block;
 192                 block->next = 0;
 193                 block->status = FREE;
 194                 block->size = totpage - HDR_PAGE;
 195                 block->page = page;
 196         }
 197
 198         split(block, size);
 199 #if     DEBUG
 200         scribble((ulong_t *)&block->memstart, NEWMEM, block->size);
 201 #endif
 202         block->status = BUSY;
 203         return (&block->memstart);
 204 }
 205
 206 void *
 207 calloc(size_t num, size_t size)
 208 {
 209         void *  mp;
 210         size_t  total;
 211
 212         if (num == 0 || size == 0) {
 213                 total = 0;
 214         } else {
 215                 total = num * size;
 216
 217                 /* check for overflow */
 218                 if ((total / num) != size) {
 219                         errno = ENOMEM;
 220                         return (NULL);
 221                 }
 222         }
 223
 224         if ((mp = malloc(total)) == NULL)
 225                 return (NULL);
 226         (void) memset(mp, 0, total);
 227         return (mp);
 228 }
 229
 230 void *
 231 realloc(void *ptr, size_t size)
 232 {
 233         struct block    *block;
 234         size_t          osize;
 235         void *          newptr;
 236
 237         if (ptr == NULL)
 238                 return (malloc(size));
 239
 240         /* LINTED */
 241         block = (struct block *)((char *)ptr - HDR_BLOCK);
 242         size = S_DROUND(size);
 243         osize = block->size;
 244
 245         /*
 246          * Join block with next one if it is free
 247          */
 248         if (block->next && block->next->status == FREE) {
 249                 block->size += block->next->size + HDR_BLOCK;
 250                 block->next = block->next->next;
 251         }
 252
 253         if (size <= block->size) {
 254                 split(block, size);
 255 #if     DEBUG
 256                 if (block->size > osize)
 257                         scribble((ulong_t *)((char *)ptr + osize), NEWMEM,
 258                             (block->size - osize));
 259 #endif
 260                 return (ptr);
 261         }
 262
 263         if ((newptr = malloc(size)) == NULL)
 264                 return (NULL);
 265         (void) memcpy(newptr, ptr, osize);
 266         block->status = FREE;
 267
 268         /*
 269          * Add the free block to the free APlist for later defragmentation.
 270          * However, this addition can only be achieved if there is room on the
 271          * free APlist.  The APlist can't be allowed to grow, as the growth
 272          * requires a realloc(), which would recurse back here, resulting in an
 273          * infinite loop.  If the free APlist is full, defrag() now.  This
 274          * defragmentation might not be able to collapse any free space, but
 275          * the free APlist will be cleared as part of the processing, ensuring
 276          * room for the addition.
 277          */
 278         if (free_alp && (aplist_nitems(free_alp) >= aplist_arritems(free_alp)))
 279                 defrag();
 280         (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST);
 281         return (newptr);
 282 }
 283
 284 /*
 285  * Replace both free() and lfree() (libc's private memory allocator).
 286  * They are both private here.
 287  */
 288 void
 289 free(void *ptr)
 290 {
 291         struct block    *block;
 292
 293         if (ptr == NULL)
 294                 return;
 295
 296         /* LINTED */
 297         block = (struct block *)((char *)ptr - HDR_BLOCK);
 298         block->status = FREE;
 299 #if     DEBUG
 300         scribble((ulong_t *)&block->memstart, FREMEM, block->size);
 301 #endif
 302         (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST);
 303 }
 304
 305 /* ARGSUSED1 */
 306 void
 307 lfree(void *ptr, size_t size)
 308 {
 309         free(ptr);
 310 }
 311
 312 /*
 313  * We can use any memory after ld.so.1's .bss up until the next page boundary
 314  * as allocatable memory.
 315  */
 316 void
 317 addfree(void *ptr, size_t bytes)
 318 {
 319         struct block    *block;
 320         struct page     *page;
 321
 322         if (bytes <= sizeof (struct page))
 323                 return;
 324         page = ptr;
 325         page->next = memstart;
 326         memstart = page;
 327         page->size = bytes;
 328         block = page->block;
 329         block->next = 0;
 330         block->status = FREE;
 331         block->size = bytes - HDR_PAGE;
 332         block->page = page;
 333 }