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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 23 /* All Rights Reserved */ 24 25 26 /* 27 * Copyright (c) 1991-1997,2000-2001 by Sun Microsystems, Inc. 28 * All rights reserved. 29 */ 30 31 #pragma ident "%Z%%M% %I% %E% SMI" /* SVR4/MNLS 1.1.2.1 */ 32 33 /*LINTLIBRARY*/ 34 35 #include <sys/types.h> 36 37 38 /* 39 * Simplified version of malloc(), free() and realloc(), to be linked with 40 * utilities that use [s]brk() and do not define their own version of the 41 * routines. 42 * 43 * The algorithm used to get extra memory space by mmap'ing /dev/zero. This 44 * breaks if the application closes the open descriptor, so now it uses 45 * mmap's MAP_ANON feature. 46 * 47 * Each call to mmap() creates a page. The pages are linked in a list. 48 * Each page is divided in blocks. There is at least one block in a page. 49 * New memory chunks are allocated on a first-fit basis. 50 * Freed blocks are joined in larger blocks. Free pages are unmapped. 51 */ 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 <synch.h> 60 #include <string.h> 61 62 63 #ifdef _REENTRANT 64 static mutex_t lock = DEFAULTMUTEX; 65 #endif /* _REENTRANT */ 66 67 struct block { 68 size_t size; /* Space available for user */ 69 struct page *page; /* Backwards reference to page */ 70 int status; 71 struct block *next; 72 void *memstart[1]; 73 }; 74 75 struct page { 76 size_t size; /* Total page size (incl. header) */ 77 struct page *next; 78 struct block block[1]; 79 }; 80 81 #define FREE 0 82 #define BUSY 1 83 84 #define HDR_BLOCK (sizeof (struct block) - sizeof (void *)) 85 #define HDR_PAGE (sizeof (struct page) - sizeof (void *)) 86 #define MINSZ sizeof (double) 87 88 /* for convenience */ 89 #ifndef NULL 90 #define NULL (0) 91 #endif 92 93 struct page *memstart; 94 static int pagesize; 95 static void defrag(struct page *); 96 static void split(struct block *, size_t); 97 static void *malloc_unlocked(size_t); 98 static size_t align(size_t, int); 99 100 void * 101 malloc(size_t size) 102 { 103 void *retval; 104 (void) mutex_lock(&lock); 105 retval = malloc_unlocked(size); 106 (void) mutex_unlock(&lock); 107 return (retval); 108 } 109 110 111 static void * 112 malloc_unlocked(size_t size) 113 { 114 struct block *block; 115 struct page *page; 116 117 if (pagesize == 0) 118 pagesize = (int)sysconf(_SC_PAGESIZE); 119 120 size = align(size, MINSZ); 121 122 /* 123 * Try to locate necessary space 124 */ 125 for (page = memstart; page; page = page->next) { 126 for (block = page->block; block; block = block->next) { 127 if (block->status == FREE && block->size >= size) 128 goto found; 129 } 130 } 131 found: 132 133 /* 134 * Need to allocate a new page 135 */ 136 if (!page) { 137 size_t totsize = size + HDR_PAGE; 138 size_t totpage = align(totsize, pagesize); 139 140 if ((page = (struct page *)mmap(0, totpage, 141 PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0)) 142 == MAP_FAILED) 143 return (0); 144 145 page->next = memstart; 146 memstart = page; 147 page->size = totpage; 148 block = page->block; 149 block->next = 0; 150 block->status = FREE; 151 block->size = totpage - HDR_PAGE; 152 block->page = page; 153 } 154 155 split(block, size); 156 157 block->status = BUSY; 158 return (&block->memstart); 159 } 160 161 void * 162 realloc(void *ptr, size_t size) 163 { 164 struct block *block; 165 size_t osize; 166 void *newptr; 167 168 (void) mutex_lock(&lock); 169 if (ptr == NULL) { 170 newptr = malloc_unlocked(size); 171 (void) mutex_unlock(&lock); 172 return (newptr); 173 } 174 block = (struct block *)((char *)ptr - HDR_BLOCK); 175 size = align(size, MINSZ); 176 osize = block->size; 177 178 /* 179 * Join block with next one if it is free 180 */ 181 if (block->next && block->next->status == FREE) { 182 block->size += block->next->size + HDR_BLOCK; 183 block->next = block->next->next; 184 } 185 186 if (size <= block->size) { 187 split(block, size); 188 (void) mutex_unlock(&lock); 189 return (ptr); 190 } 191 192 newptr = malloc_unlocked(size); 193 (void) memcpy(newptr, ptr, osize); 194 block->status = FREE; 195 defrag(block->page); 196 (void) mutex_unlock(&lock); 197 return (newptr); 198 } 199 200 void 201 free(void *ptr) 202 { 203 struct block *block; 204 205 (void) mutex_lock(&lock); 206 if (ptr == NULL) { 207 (void) mutex_unlock(&lock); 208 return; 209 } 210 block = (struct block *)((char *)ptr - HDR_BLOCK); 211 block->status = FREE; 212 213 defrag(block->page); 214 (void) mutex_unlock(&lock); 215 } 216 217 /* 218 * Align size on an appropriate boundary 219 */ 220 static size_t 221 align(size_t size, int bound) 222 { 223 if (size < bound) 224 return ((size_t)bound); 225 else 226 return (size + bound - 1 - (size + bound - 1) % bound); 227 } 228 229 static void 230 split(struct block *block, size_t size) 231 { 232 if (block->size > size + sizeof (struct block)) { 233 struct block *newblock; 234 newblock = (struct block *)((char *)block + HDR_BLOCK + size); 235 newblock->next = block->next; 236 block->next = newblock; 237 newblock->status = FREE; 238 newblock->page = block->page; 239 newblock->size = block->size - size - HDR_BLOCK; 240 block->size = size; 241 } 242 } 243 244 /* 245 * Defragmentation 246 */ 247 static void 248 defrag(struct page *page) 249 { 250 struct block *block; 251 252 for (block = page->block; block; block = block->next) { 253 struct block *block2; 254 255 if (block->status == BUSY) 256 continue; 257 for (block2 = block->next; block2 && block2->status == FREE; 258 block2 = block2->next) { 259 block->next = block2->next; 260 block->size += block2->size + HDR_BLOCK; 261 } 262 } 263 264 /* 265 * Free page 266 */ 267 if (page->block->size == page->size - HDR_PAGE) { 268 if (page == memstart) 269 memstart = page->next; 270 else { 271 struct page *page2; 272 for (page2 = memstart; page2->next; 273 page2 = page2->next) { 274 if (page2->next == page) { 275 page2->next = page->next; 276 break; 277 } 278 } 279 } 280 (void) munmap((caddr_t)page, page->size); 281 } 282 } 283