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 2009 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 /* 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 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 71 static struct page *memstart; 72 73 #if DEBUG 74 /* 75 * When built for debugging, scribble a pattern over newly allocated and 76 * freed memory. 77 */ 78 #define NEWMEM 0 79 #define FREMEM 1 80 81 /* LINTED */ 82 const ulong_t patterns[] = { 83 (ulong_t)0xbaddcafebaddcafeULL, (ulong_t)0xdeadbeefdeadbeefULL 84 }; 85 86 static void 87 scribble(ulong_t *membgn, int pattern, size_t size) 88 { 89 size_t memsize = size / sizeof (ulong_t); 90 91 while (memsize--) { 92 if (pattern == FREMEM) 93 ASSERT(*membgn != patterns[pattern]); 94 *membgn++ = patterns[pattern]; 95 } 96 } 97 #endif 98 99 /* 100 * Defragmentation 101 */ 102 void 103 defrag() 104 { 105 struct page *page; 106 Aliste idx; 107 108 for (APLIST_TRAVERSE(free_alp, idx, page)) { 109 struct block *block; 110 111 for (block = page->block; block; block = block->next) { 112 struct block *block2; 113 114 if (block->status == BUSY) 115 continue; 116 for (block2 = block->next; block2 && 117 block2->status == FREE; block2 = block2->next) { 118 block->next = block2->next; 119 block->size += block2->size + HDR_BLOCK; 120 } 121 } 122 123 /* 124 * If a page becomes free, leave it, and save the unmapping 125 * expense, as we'll probably come back and reclaim the page 126 * for later malloc activity. 127 * 128 * Free the defrag index. 129 */ 130 aplist_delete(free_alp, &idx); 131 } 132 } 133 134 static void 135 split(struct block *block, size_t size) 136 { 137 if (block->size > size + sizeof (struct block)) { 138 struct block *newblock; 139 /* LINTED */ 140 newblock = (struct block *) 141 ((char *)block + HDR_BLOCK + size); 142 newblock->next = block->next; 143 block->next = newblock; 144 newblock->status = FREE; 145 newblock->page = block->page; 146 newblock->size = block->size - size - HDR_BLOCK; 147 block->size = size; 148 } 149 } 150 151 #include <stdio.h> 152 153 /* 154 * Replace both malloc() and lmalloc() (libc's private memory allocator). 155 * They are both private here. 156 */ 157 #pragma weak lmalloc = malloc 158 void * 159 malloc(size_t size) 160 { 161 struct block *block; 162 struct page *page; 163 164 size = S_DROUND(size); 165 166 /* 167 * Try to locate necessary space 168 */ 169 for (page = memstart; page; page = page->next) { 170 for (block = page->block; block; block = block->next) { 171 if ((block->status == FREE) && (block->size >= size)) 172 goto found; 173 } 174 } 175 found: 176 /* 177 * Need to allocate a new page 178 */ 179 if (!page) { 180 size_t totsize = size + HDR_PAGE; 181 size_t totpage = S_ROUND(totsize, syspagsz); 182 183 if ((page = dz_map(0, 0, totpage, 184 PROT_READ | PROT_WRITE | PROT_EXEC, 185 MAP_PRIVATE)) == MAP_FAILED) 186 return (0); 187 188 page->next = memstart; 189 memstart = page; 190 page->size = totpage; 191 block = page->block; 192 block->next = 0; 193 block->status = FREE; 194 block->size = totpage - HDR_PAGE; 195 block->page = page; 196 } 197 198 split(block, size); 199 #if DEBUG 200 scribble((ulong_t *)&block->memstart, NEWMEM, block->size); 201 #endif 202 block->status = BUSY; 203 return (&block->memstart); 204 } 205 206 void * 207 calloc(size_t num, size_t size) 208 { 209 void * mp; 210 211 num *= size; 212 if ((mp = malloc(num)) == NULL) 213 return (NULL); 214 (void) memset(mp, 0, num); 215 return (mp); 216 } 217 218 void * 219 realloc(void *ptr, size_t size) 220 { 221 struct block *block; 222 size_t osize; 223 void * newptr; 224 225 if (ptr == NULL) 226 return (malloc(size)); 227 228 /* LINTED */ 229 block = (struct block *)((char *)ptr - HDR_BLOCK); 230 size = S_DROUND(size); 231 osize = block->size; 232 233 /* 234 * Join block with next one if it is free 235 */ 236 if (block->next && block->next->status == FREE) { 237 block->size += block->next->size + HDR_BLOCK; 238 block->next = block->next->next; 239 } 240 241 if (size <= block->size) { 242 split(block, size); 243 #if DEBUG 244 if (block->size > osize) 245 scribble((ulong_t *)((char *)ptr + osize), NEWMEM, 246 (block->size - osize)); 247 #endif 248 return (ptr); 249 } 250 251 if ((newptr = malloc(size)) == NULL) 252 return (NULL); 253 (void) memcpy(newptr, ptr, osize); 254 block->status = FREE; 255 (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST); 256 return (newptr); 257 } 258 259 /* 260 * Replace both free() and lfree() (libc's private memory allocator). 261 * They are both private here. 262 */ 263 void 264 free(void *ptr) 265 { 266 struct block *block; 267 268 if (ptr == NULL) 269 return; 270 271 /* LINTED */ 272 block = (struct block *)((char *)ptr - HDR_BLOCK); 273 block->status = FREE; 274 #if DEBUG 275 scribble((ulong_t *)&block->memstart, FREMEM, block->size); 276 #endif 277 (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST); 278 } 279 280 /* ARGSUSED1 */ 281 void 282 lfree(void *ptr, size_t size) 283 { 284 free(ptr); 285 } 286 287 /* 288 * We can use any memory after ld.so.1's .bss up until the next page boundary 289 * as allocatable memory. 290 */ 291 void 292 addfree(void *ptr, size_t bytes) 293 { 294 struct block *block; 295 struct page *page; 296 297 if (bytes <= sizeof (struct page)) 298 return; 299 page = ptr; 300 page->next = memstart; 301 memstart = page; 302 page->size = bytes; 303 block = page->block; 304 block->next = 0; 305 block->status = FREE; 306 block->size = bytes - HDR_PAGE; 307 block->page = page; 308 } 309