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