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 256 /* 257 * Add the free block to the free APlist for later defragmentation. 258 * However, this addition can only be achieved if there is room on the 259 * free APlist. The APlist can't be allowed to grow, as the growth 260 * requires a realloc(), which would recurse back here, resulting in an 261 * infinite loop. If the free APlist is full, defrag() now. This 262 * defragmentation might not be able to collapse any free space, but 263 * the free APlist will be cleared as part of the processing, ensuring 264 * room for the addition. 265 */ 266 if (free_alp && (aplist_nitems(free_alp) >= aplist_arritems(free_alp))) 267 defrag(); 268 (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST); 269 return (newptr); 270 } 271 272 /* 273 * Replace both free() and lfree() (libc's private memory allocator). 274 * They are both private here. 275 */ 276 void 277 free(void *ptr) 278 { 279 struct block *block; 280 281 if (ptr == NULL) 282 return; 283 284 /* LINTED */ 285 block = (struct block *)((char *)ptr - HDR_BLOCK); 286 block->status = FREE; 287 #if DEBUG 288 scribble((ulong_t *)&block->memstart, FREMEM, block->size); 289 #endif 290 (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST); 291 } 292 293 /* ARGSUSED1 */ 294 void 295 lfree(void *ptr, size_t size) 296 { 297 free(ptr); 298 } 299 300 /* 301 * We can use any memory after ld.so.1's .bss up until the next page boundary 302 * as allocatable memory. 303 */ 304 void 305 addfree(void *ptr, size_t bytes) 306 { 307 struct block *block; 308 struct page *page; 309 310 if (bytes <= sizeof (struct page)) 311 return; 312 page = ptr; 313 page->next = memstart; 314 memstart = page; 315 page->size = bytes; 316 block = page->block; 317 block->next = 0; 318 block->status = FREE; 319 block->size = bytes - HDR_PAGE; 320 block->page = page; 321 } 322