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 /* 28 * Copyright (c) 1988 AT&T 29 * All Rights Reserved 30 */ 31 32 #pragma ident "%Z%%M% %I% %E% SMI" 33 34 /* 35 * Simplified version of malloc(), calloc() and free(), to be linked with 36 * utilities that use [s]brk() and do not define their own version of the 37 * routines. 38 * The algorithm maps /dev/zero to get extra memory space. 39 * Each call to mmap() creates a page. The pages are linked in a list. 40 * Each page is divided in blocks. There is at least one block in a page. 41 * New memory chunks are allocated on a first-fit basis. 42 * Freed blocks are joined in larger blocks. Free pages are unmapped. 43 */ 44 45 #include <stdlib.h> 46 #include <sys/types.h> 47 #include <sys/mman.h> 48 #include <sys/debug.h> 49 #include <memory.h> 50 #include "_rtld.h" 51 #include "msg.h" 52 53 struct block { 54 size_t size; /* Space available for user */ 55 struct page *page; /* Backwards reference to page */ 56 int status; 57 struct block *next; 58 void * memstart[1]; 59 }; 60 61 struct page { 62 size_t size; /* Total page size (incl. header) */ 63 struct page *next; 64 struct block block[1]; 65 }; 66 67 #define FREE 0 68 #define BUSY 1 69 70 #define HDR_BLOCK (sizeof (struct block) - sizeof (void *)) 71 #define HDR_PAGE (sizeof (struct page) - sizeof (void *)) 72 #define MINSZ 8 73 74 static struct page *memstart; 75 76 #if DEBUG 77 /* 78 * When built for debugging, scribble a pattern over newly allocated and 79 * freed memory. 80 */ 81 #define NEWMEM 0 82 #define FREMEM 1 83 84 /* LINTED */ 85 const ulong_t patterns[] = { 86 (ulong_t)0xbaddcafebaddcafeULL, (ulong_t)0xdeadbeefdeadbeefULL 87 }; 88 89 static void 90 scribble(ulong_t *membgn, int pattern, size_t size) 91 { 92 size_t memsize = size / sizeof (ulong_t); 93 94 while (memsize--) { 95 if (pattern == FREMEM) 96 ASSERT(*membgn != patterns[pattern]); 97 *membgn++ = patterns[pattern]; 98 } 99 } 100 #endif 101 102 /* 103 * Defragmentation 104 */ 105 static void 106 defrag(struct page *page) 107 { 108 struct block *block; 109 110 for (block = page->block; block; block = block->next) { 111 struct block *block2; 112 113 if (block->status == BUSY) 114 continue; 115 for (block2 = block->next; block2 && block2->status == FREE; 116 block2 = block2->next) { 117 block->next = block2->next; 118 block->size += block2->size + HDR_BLOCK; 119 } 120 } 121 122 /* 123 * Free page 124 */ 125 if (page->block->size == page->size - HDR_PAGE) { 126 if (page == memstart) 127 memstart = page->next; 128 else { 129 struct page *page2; 130 for (page2 = memstart; page2->next; 131 page2 = page2->next) { 132 if (page2->next == page) { 133 page2->next = page->next; 134 break; 135 } 136 } 137 } 138 (void) munmap((caddr_t)page, (size_t)page->size); 139 } 140 } 141 142 static void 143 split(struct block *block, size_t size) 144 { 145 if (block->size > size + sizeof (struct block)) { 146 struct block *newblock; 147 /* LINTED */ 148 newblock = (struct block *) 149 ((char *)block + HDR_BLOCK + size); 150 newblock->next = block->next; 151 block->next = newblock; 152 newblock->status = FREE; 153 newblock->page = block->page; 154 newblock->size = block->size - size - HDR_BLOCK; 155 block->size = size; 156 } 157 } 158 159 160 /* 161 * Align size on an appropriate boundary 162 */ 163 static size_t 164 align(size_t size, size_t bound) 165 { 166 if (size < bound) 167 return (bound); 168 else 169 return (size + bound - 1 - (size + bound - 1) % bound); 170 } 171 172 /* 173 * Replace both malloc() and lmalloc() (libc's private memory allocator). 174 * They are both private here. 175 */ 176 #pragma weak lmalloc = malloc 177 void * 178 malloc(size_t size) 179 { 180 struct block *block; 181 struct page *page; 182 183 size = align(size, MINSZ); 184 185 /* 186 * Try to locate necessary space 187 */ 188 for (page = memstart; page; page = page->next) { 189 for (block = page->block; block; block = block->next) { 190 if ((block->status == FREE) && (block->size >= size)) 191 goto found; 192 } 193 } 194 found: 195 196 /* 197 * Need to allocate a new page 198 */ 199 if (!page) { 200 size_t totsize = size + HDR_PAGE; 201 size_t totpage = align(totsize, syspagsz); 202 203 /* LINTED */ 204 if ((page = (struct page *)dz_map(0, 0, totpage, 205 PROT_READ | PROT_WRITE | PROT_EXEC, 206 MAP_PRIVATE)) == (struct page *)-1) 207 return (0); 208 209 page->next = memstart; 210 memstart = page; 211 page->size = totpage; 212 block = page->block; 213 block->next = 0; 214 block->status = FREE; 215 block->size = totpage - HDR_PAGE; 216 block->page = page; 217 } 218 219 split(block, size); 220 #if DEBUG 221 scribble((ulong_t *)&block->memstart, NEWMEM, block->size); 222 #endif 223 block->status = BUSY; 224 return (&block->memstart); 225 } 226 227 void * 228 calloc(size_t num, size_t size) 229 { 230 void * mp; 231 232 num *= size; 233 if ((mp = malloc(num)) == NULL) 234 return (NULL); 235 (void) memset(mp, 0, num); 236 return (mp); 237 } 238 239 void * 240 realloc(void * ptr, size_t size) 241 { 242 struct block *block; 243 size_t osize; 244 void * newptr; 245 246 if (ptr == NULL) 247 return (malloc(size)); 248 249 /* LINTED */ 250 block = (struct block *)((char *)ptr - HDR_BLOCK); 251 size = align(size, MINSZ); 252 osize = block->size; 253 254 /* 255 * Join block with next one if it is free 256 */ 257 if (block->next && block->next->status == FREE) { 258 block->size += block->next->size + HDR_BLOCK; 259 block->next = block->next->next; 260 } 261 262 if (size <= block->size) { 263 split(block, size); 264 #if DEBUG 265 if (block->size > osize) 266 scribble((ulong_t *)((char *)ptr + osize), NEWMEM, 267 (block->size - osize)); 268 #endif 269 return (ptr); 270 } 271 272 if ((newptr = malloc(size)) == NULL) 273 return (NULL); 274 (void) memcpy(newptr, ptr, osize); 275 block->status = FREE; 276 defrag(block->page); 277 return (newptr); 278 } 279 280 /* 281 * Replace both free() and lfree() (libc's private memory allocator). 282 * They are both private here. 283 */ 284 void 285 free(void * ptr) 286 { 287 struct block *block; 288 289 if (ptr == NULL) 290 return; 291 292 /* LINTED */ 293 block = (struct block *)((char *)ptr - HDR_BLOCK); 294 block->status = FREE; 295 #if DEBUG 296 scribble((ulong_t *)&block->memstart, FREMEM, block->size); 297 #endif 298 defrag(block->page); 299 } 300 301 /* ARGSUSED1 */ 302 void 303 lfree(void * ptr, size_t size) 304 { 305 free(ptr); 306 } 307 308 309 /* 310 * We can use any memory after ld.so.1's .bss up until the next page boundary 311 * as allocatable memory. 312 */ 313 void 314 addfree(void * ptr, size_t bytes) 315 { 316 struct block *block; 317 struct page *page; 318 319 if (bytes <= sizeof (struct page)) 320 return; 321 page = ptr; 322 page->next = memstart; 323 memstart = page; 324 page->size = bytes; 325 block = page->block; 326 block->next = 0; 327 block->status = FREE; 328 block->size = bytes - HDR_PAGE; 329 block->page = page; 330 } 331