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