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