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 } 297