usr/src/lib/libmapmalloc/common/textmem.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 2008 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  28 /*        All Rights Reserved   */
  29
  30 #pragma ident   "%Z%%M% %I%     %E% SMI"
  31
  32 #include <sys/types.h>
  33
  34
  35 /*
  36  * Simplified version of malloc(), free() and realloc(), to be linked with
  37  * utilities that use [s]brk() and do not define their own version of the
  38  * routines.
  39  *
  40  * The algorithm used to get extra memory space by mmap'ing /dev/zero. This
  41  * breaks if the application closes the open descriptor, so now it uses
  42  * mmap's MAP_ANON feature.
  43  *
  44  * Each call to mmap() creates a page. The pages are linked in a list.
  45  * Each page is divided in blocks. There is at least one block in a page.
  46  * New memory chunks are allocated on a first-fit basis.
  47  * Freed blocks are joined in larger blocks. Free pages are unmapped.
  48  */
  49 #include <stdlib.h>
  50 #include <sys/types.h>
  51 #include <sys/mman.h>
  52 #include <fcntl.h>
  53 #include <errno.h>
  54 #include <unistd.h>
  55 #include <thread.h>
  56 #include <pthread.h>
  57 #include <synch.h>
  58 #include <string.h>
  59
  60 static mutex_t lock = DEFAULTMUTEX;
  61
  62 struct block {
  63         size_t size;            /* Space available for user */
  64         struct page *page;      /* Backwards reference to page */
  65         int status;
  66         struct block *next;
  67         void *memstart[1];
  68 };
  69
  70 struct page {
  71         size_t size;            /* Total page size (incl. header) */
  72         struct page *next;
  73         struct block block[1];
  74 };
  75
  76 #define FREE    0
  77 #define BUSY    1
  78
  79 #define HDR_BLOCK       (sizeof (struct block) - sizeof (void *))
  80 #define HDR_PAGE        (sizeof (struct page) - sizeof (void *))
  81 #define MINSZ           sizeof (double)
  82
  83 /* for convenience */
  84 #ifndef NULL
  85 #define NULL            (0)
  86 #endif
  87
  88 struct page *memstart;
  89 static int pagesize;
  90 static void defrag(struct page *);
  91 static void split(struct block *,  size_t);
  92 static void *malloc_unlocked(size_t);
  93 static size_t align(size_t, int);
  94
  95 void *
  96 malloc(size_t size)
  97 {
  98         void *retval;
  99         (void) mutex_lock(&lock);
 100         retval = malloc_unlocked(size);
 101         (void) mutex_unlock(&lock);
 102         return (retval);
 103 }
 104
 105
 106 static void *
 107 malloc_unlocked(size_t size)
 108 {
 109         struct block *block;
 110         struct page *page;
 111
 112         if (pagesize == 0)
 113                 pagesize = (int)sysconf(_SC_PAGESIZE);
 114
 115         size = align(size, MINSZ);
 116
 117         /*
 118          * Try to locate necessary space
 119          */
 120         for (page = memstart; page; page = page->next) {
 121                 for (block = page->block; block; block = block->next) {
 122                         if (block->status == FREE && block->size >= size)
 123                                 goto found;
 124                 }
 125         }
 126 found:
 127
 128         /*
 129          * Need to allocate a new page
 130          */
 131         if (!page) {
 132                 size_t totsize = size + HDR_PAGE;
 133                 size_t totpage = align(totsize, pagesize);
 134
 135                 if ((page = (struct page *)mmap(0, totpage,
 136                     PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0))
 137                     == MAP_FAILED)
 138                         return (0);
 139
 140                 page->next = memstart;
 141                 memstart = page;
 142                 page->size = totpage;
 143                 block = page->block;
 144                 block->next = 0;
 145                 block->status = FREE;
 146                 block->size = totpage - HDR_PAGE;
 147                 block->page = page;
 148         }
 149
 150         split(block, size);
 151
 152         block->status = BUSY;
 153         return (&block->memstart);
 154 }
 155
 156 void *
 157 realloc(void *ptr, size_t size)
 158 {
 159         struct block *block;
 160         size_t osize;
 161         void *newptr;
 162
 163         (void) mutex_lock(&lock);
 164         if (ptr == NULL) {
 165                 newptr = malloc_unlocked(size);
 166                 (void) mutex_unlock(&lock);
 167                 return (newptr);
 168         }
 169         block = (struct block *)((char *)ptr - HDR_BLOCK);
 170         size = align(size, MINSZ);
 171         osize = block->size;
 172
 173         /*
 174          * Join block with next one if it is free
 175          */
 176         if (block->next && block->next->status == FREE) {
 177                 block->size += block->next->size + HDR_BLOCK;
 178                 block->next = block->next->next;
 179         }
 180
 181         if (size <= block->size) {
 182                 split(block, size);
 183                 (void) mutex_unlock(&lock);
 184                 return (ptr);
 185         }
 186
 187         newptr = malloc_unlocked(size);
 188         (void) memcpy(newptr, ptr, osize);
 189         block->status = FREE;
 190         defrag(block->page);
 191         (void) mutex_unlock(&lock);
 192         return (newptr);
 193 }
 194
 195 void
 196 free(void *ptr)
 197 {
 198         struct block *block;
 199
 200         (void) mutex_lock(&lock);
 201         if (ptr == NULL) {
 202                 (void) mutex_unlock(&lock);
 203                 return;
 204         }
 205         block = (struct block *)((char *)ptr - HDR_BLOCK);
 206         block->status = FREE;
 207
 208         defrag(block->page);
 209         (void) mutex_unlock(&lock);
 210 }
 211
 212 /*
 213  * Align size on an appropriate boundary
 214  */
 215 static size_t
 216 align(size_t size, int bound)
 217 {
 218         if (size < bound)
 219                 return ((size_t)bound);
 220         else
 221                 return (size + bound - 1 - (size + bound - 1) % bound);
 222 }
 223
 224 static void
 225 split(struct block *block, size_t size)
 226 {
 227         if (block->size > size + sizeof (struct block)) {
 228                 struct block *newblock;
 229                 newblock = (struct block *)((char *)block + HDR_BLOCK + size);
 230                 newblock->next = block->next;
 231                 block->next = newblock;
 232                 newblock->status = FREE;
 233                 newblock->page = block->page;
 234                 newblock->size = block->size - size - HDR_BLOCK;
 235                 block->size = size;
 236         }
 237 }
 238
 239 /*
 240  * Defragmentation
 241  */
 242 static void
 243 defrag(struct page *page)
 244 {
 245         struct block *block;
 246
 247         for (block = page->block; block; block = block->next) {
 248                 struct block *block2;
 249
 250                 if (block->status == BUSY)
 251                         continue;
 252                 for (block2 = block->next; block2 && block2->status == FREE;
 253                     block2 = block2->next) {
 254                         block->next = block2->next;
 255                         block->size += block2->size + HDR_BLOCK;
 256                 }
 257         }
 258
 259         /*
 260          * Free page
 261          */
 262         if (page->block->size == page->size - HDR_PAGE) {
 263                 if (page == memstart)
 264                         memstart = page->next;
 265                 else {
 266                         struct page *page2;
 267                         for (page2 = memstart; page2->next;
 268                             page2 = page2->next) {
 269                                 if (page2->next == page) {
 270                                         page2->next = page->next;
 271                                         break;
 272                                 }
 273                         }
 274                 }
 275                 (void) munmap((caddr_t)page, page->size);
 276         }
 277 }
 278
 279 static void
 280 malloc_prepare()
 281 {
 282         (void) mutex_lock(&lock);
 283 }
 284
 285 static void
 286 malloc_release()
 287 {
 288         (void) mutex_unlock(&lock);
 289 }
 290
 291 #pragma init(malloc_init)
 292 static void
 293 malloc_init(void)
 294 {
 295         (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
 296 }