1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 23*0Sstevel@tonic-gate /* All Rights Reserved */ 24*0Sstevel@tonic-gate 25*0Sstevel@tonic-gate 26*0Sstevel@tonic-gate /* 27*0Sstevel@tonic-gate * Copyright (c) 1991-1997,2000-2001 by Sun Microsystems, Inc. 28*0Sstevel@tonic-gate * All rights reserved. 29*0Sstevel@tonic-gate */ 30*0Sstevel@tonic-gate 31*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" /* SVR4/MNLS 1.1.2.1 */ 32*0Sstevel@tonic-gate 33*0Sstevel@tonic-gate /*LINTLIBRARY*/ 34*0Sstevel@tonic-gate 35*0Sstevel@tonic-gate #include <sys/types.h> 36*0Sstevel@tonic-gate 37*0Sstevel@tonic-gate 38*0Sstevel@tonic-gate /* 39*0Sstevel@tonic-gate * Simplified version of malloc(), free() and realloc(), to be linked with 40*0Sstevel@tonic-gate * utilities that use [s]brk() and do not define their own version of the 41*0Sstevel@tonic-gate * routines. 42*0Sstevel@tonic-gate * 43*0Sstevel@tonic-gate * The algorithm used to get extra memory space by mmap'ing /dev/zero. This 44*0Sstevel@tonic-gate * breaks if the application closes the open descriptor, so now it uses 45*0Sstevel@tonic-gate * mmap's MAP_ANON feature. 46*0Sstevel@tonic-gate * 47*0Sstevel@tonic-gate * Each call to mmap() creates a page. The pages are linked in a list. 48*0Sstevel@tonic-gate * Each page is divided in blocks. There is at least one block in a page. 49*0Sstevel@tonic-gate * New memory chunks are allocated on a first-fit basis. 50*0Sstevel@tonic-gate * Freed blocks are joined in larger blocks. Free pages are unmapped. 51*0Sstevel@tonic-gate */ 52*0Sstevel@tonic-gate #include <stdlib.h> 53*0Sstevel@tonic-gate #include <sys/types.h> 54*0Sstevel@tonic-gate #include <sys/mman.h> 55*0Sstevel@tonic-gate #include <fcntl.h> 56*0Sstevel@tonic-gate #include <errno.h> 57*0Sstevel@tonic-gate #include <unistd.h> 58*0Sstevel@tonic-gate #include <thread.h> 59*0Sstevel@tonic-gate #include <synch.h> 60*0Sstevel@tonic-gate #include <string.h> 61*0Sstevel@tonic-gate 62*0Sstevel@tonic-gate 63*0Sstevel@tonic-gate #ifdef _REENTRANT 64*0Sstevel@tonic-gate static mutex_t lock = DEFAULTMUTEX; 65*0Sstevel@tonic-gate #endif /* _REENTRANT */ 66*0Sstevel@tonic-gate 67*0Sstevel@tonic-gate struct block { 68*0Sstevel@tonic-gate size_t size; /* Space available for user */ 69*0Sstevel@tonic-gate struct page *page; /* Backwards reference to page */ 70*0Sstevel@tonic-gate int status; 71*0Sstevel@tonic-gate struct block *next; 72*0Sstevel@tonic-gate void *memstart[1]; 73*0Sstevel@tonic-gate }; 74*0Sstevel@tonic-gate 75*0Sstevel@tonic-gate struct page { 76*0Sstevel@tonic-gate size_t size; /* Total page size (incl. header) */ 77*0Sstevel@tonic-gate struct page *next; 78*0Sstevel@tonic-gate struct block block[1]; 79*0Sstevel@tonic-gate }; 80*0Sstevel@tonic-gate 81*0Sstevel@tonic-gate #define FREE 0 82*0Sstevel@tonic-gate #define BUSY 1 83*0Sstevel@tonic-gate 84*0Sstevel@tonic-gate #define HDR_BLOCK (sizeof (struct block) - sizeof (void *)) 85*0Sstevel@tonic-gate #define HDR_PAGE (sizeof (struct page) - sizeof (void *)) 86*0Sstevel@tonic-gate #define MINSZ sizeof (double) 87*0Sstevel@tonic-gate 88*0Sstevel@tonic-gate /* for convenience */ 89*0Sstevel@tonic-gate #ifndef NULL 90*0Sstevel@tonic-gate #define NULL (0) 91*0Sstevel@tonic-gate #endif 92*0Sstevel@tonic-gate 93*0Sstevel@tonic-gate struct page *memstart; 94*0Sstevel@tonic-gate static int pagesize; 95*0Sstevel@tonic-gate static void defrag(struct page *); 96*0Sstevel@tonic-gate static void split(struct block *, size_t); 97*0Sstevel@tonic-gate static void *malloc_unlocked(size_t); 98*0Sstevel@tonic-gate static size_t align(size_t, int); 99*0Sstevel@tonic-gate 100*0Sstevel@tonic-gate void * 101*0Sstevel@tonic-gate malloc(size_t size) 102*0Sstevel@tonic-gate { 103*0Sstevel@tonic-gate void *retval; 104*0Sstevel@tonic-gate (void) mutex_lock(&lock); 105*0Sstevel@tonic-gate retval = malloc_unlocked(size); 106*0Sstevel@tonic-gate (void) mutex_unlock(&lock); 107*0Sstevel@tonic-gate return (retval); 108*0Sstevel@tonic-gate } 109*0Sstevel@tonic-gate 110*0Sstevel@tonic-gate 111*0Sstevel@tonic-gate static void * 112*0Sstevel@tonic-gate malloc_unlocked(size_t size) 113*0Sstevel@tonic-gate { 114*0Sstevel@tonic-gate struct block *block; 115*0Sstevel@tonic-gate struct page *page; 116*0Sstevel@tonic-gate 117*0Sstevel@tonic-gate if (pagesize == 0) 118*0Sstevel@tonic-gate pagesize = (int)sysconf(_SC_PAGESIZE); 119*0Sstevel@tonic-gate 120*0Sstevel@tonic-gate size = align(size, MINSZ); 121*0Sstevel@tonic-gate 122*0Sstevel@tonic-gate /* 123*0Sstevel@tonic-gate * Try to locate necessary space 124*0Sstevel@tonic-gate */ 125*0Sstevel@tonic-gate for (page = memstart; page; page = page->next) { 126*0Sstevel@tonic-gate for (block = page->block; block; block = block->next) { 127*0Sstevel@tonic-gate if (block->status == FREE && block->size >= size) 128*0Sstevel@tonic-gate goto found; 129*0Sstevel@tonic-gate } 130*0Sstevel@tonic-gate } 131*0Sstevel@tonic-gate found: 132*0Sstevel@tonic-gate 133*0Sstevel@tonic-gate /* 134*0Sstevel@tonic-gate * Need to allocate a new page 135*0Sstevel@tonic-gate */ 136*0Sstevel@tonic-gate if (!page) { 137*0Sstevel@tonic-gate size_t totsize = size + HDR_PAGE; 138*0Sstevel@tonic-gate size_t totpage = align(totsize, pagesize); 139*0Sstevel@tonic-gate 140*0Sstevel@tonic-gate if ((page = (struct page *)mmap(0, totpage, 141*0Sstevel@tonic-gate PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0)) 142*0Sstevel@tonic-gate == MAP_FAILED) 143*0Sstevel@tonic-gate return (0); 144*0Sstevel@tonic-gate 145*0Sstevel@tonic-gate page->next = memstart; 146*0Sstevel@tonic-gate memstart = page; 147*0Sstevel@tonic-gate page->size = totpage; 148*0Sstevel@tonic-gate block = page->block; 149*0Sstevel@tonic-gate block->next = 0; 150*0Sstevel@tonic-gate block->status = FREE; 151*0Sstevel@tonic-gate block->size = totpage - HDR_PAGE; 152*0Sstevel@tonic-gate block->page = page; 153*0Sstevel@tonic-gate } 154*0Sstevel@tonic-gate 155*0Sstevel@tonic-gate split(block, size); 156*0Sstevel@tonic-gate 157*0Sstevel@tonic-gate block->status = BUSY; 158*0Sstevel@tonic-gate return (&block->memstart); 159*0Sstevel@tonic-gate } 160*0Sstevel@tonic-gate 161*0Sstevel@tonic-gate void * 162*0Sstevel@tonic-gate realloc(void *ptr, size_t size) 163*0Sstevel@tonic-gate { 164*0Sstevel@tonic-gate struct block *block; 165*0Sstevel@tonic-gate size_t osize; 166*0Sstevel@tonic-gate void *newptr; 167*0Sstevel@tonic-gate 168*0Sstevel@tonic-gate (void) mutex_lock(&lock); 169*0Sstevel@tonic-gate if (ptr == NULL) { 170*0Sstevel@tonic-gate newptr = malloc_unlocked(size); 171*0Sstevel@tonic-gate (void) mutex_unlock(&lock); 172*0Sstevel@tonic-gate return (newptr); 173*0Sstevel@tonic-gate } 174*0Sstevel@tonic-gate block = (struct block *)((char *)ptr - HDR_BLOCK); 175*0Sstevel@tonic-gate size = align(size, MINSZ); 176*0Sstevel@tonic-gate osize = block->size; 177*0Sstevel@tonic-gate 178*0Sstevel@tonic-gate /* 179*0Sstevel@tonic-gate * Join block with next one if it is free 180*0Sstevel@tonic-gate */ 181*0Sstevel@tonic-gate if (block->next && block->next->status == FREE) { 182*0Sstevel@tonic-gate block->size += block->next->size + HDR_BLOCK; 183*0Sstevel@tonic-gate block->next = block->next->next; 184*0Sstevel@tonic-gate } 185*0Sstevel@tonic-gate 186*0Sstevel@tonic-gate if (size <= block->size) { 187*0Sstevel@tonic-gate split(block, size); 188*0Sstevel@tonic-gate (void) mutex_unlock(&lock); 189*0Sstevel@tonic-gate return (ptr); 190*0Sstevel@tonic-gate } 191*0Sstevel@tonic-gate 192*0Sstevel@tonic-gate newptr = malloc_unlocked(size); 193*0Sstevel@tonic-gate (void) memcpy(newptr, ptr, osize); 194*0Sstevel@tonic-gate block->status = FREE; 195*0Sstevel@tonic-gate defrag(block->page); 196*0Sstevel@tonic-gate (void) mutex_unlock(&lock); 197*0Sstevel@tonic-gate return (newptr); 198*0Sstevel@tonic-gate } 199*0Sstevel@tonic-gate 200*0Sstevel@tonic-gate void 201*0Sstevel@tonic-gate free(void *ptr) 202*0Sstevel@tonic-gate { 203*0Sstevel@tonic-gate struct block *block; 204*0Sstevel@tonic-gate 205*0Sstevel@tonic-gate (void) mutex_lock(&lock); 206*0Sstevel@tonic-gate if (ptr == NULL) { 207*0Sstevel@tonic-gate (void) mutex_unlock(&lock); 208*0Sstevel@tonic-gate return; 209*0Sstevel@tonic-gate } 210*0Sstevel@tonic-gate block = (struct block *)((char *)ptr - HDR_BLOCK); 211*0Sstevel@tonic-gate block->status = FREE; 212*0Sstevel@tonic-gate 213*0Sstevel@tonic-gate defrag(block->page); 214*0Sstevel@tonic-gate (void) mutex_unlock(&lock); 215*0Sstevel@tonic-gate } 216*0Sstevel@tonic-gate 217*0Sstevel@tonic-gate /* 218*0Sstevel@tonic-gate * Align size on an appropriate boundary 219*0Sstevel@tonic-gate */ 220*0Sstevel@tonic-gate static size_t 221*0Sstevel@tonic-gate align(size_t size, int bound) 222*0Sstevel@tonic-gate { 223*0Sstevel@tonic-gate if (size < bound) 224*0Sstevel@tonic-gate return ((size_t)bound); 225*0Sstevel@tonic-gate else 226*0Sstevel@tonic-gate return (size + bound - 1 - (size + bound - 1) % bound); 227*0Sstevel@tonic-gate } 228*0Sstevel@tonic-gate 229*0Sstevel@tonic-gate static void 230*0Sstevel@tonic-gate split(struct block *block, size_t size) 231*0Sstevel@tonic-gate { 232*0Sstevel@tonic-gate if (block->size > size + sizeof (struct block)) { 233*0Sstevel@tonic-gate struct block *newblock; 234*0Sstevel@tonic-gate newblock = (struct block *)((char *)block + HDR_BLOCK + size); 235*0Sstevel@tonic-gate newblock->next = block->next; 236*0Sstevel@tonic-gate block->next = newblock; 237*0Sstevel@tonic-gate newblock->status = FREE; 238*0Sstevel@tonic-gate newblock->page = block->page; 239*0Sstevel@tonic-gate newblock->size = block->size - size - HDR_BLOCK; 240*0Sstevel@tonic-gate block->size = size; 241*0Sstevel@tonic-gate } 242*0Sstevel@tonic-gate } 243*0Sstevel@tonic-gate 244*0Sstevel@tonic-gate /* 245*0Sstevel@tonic-gate * Defragmentation 246*0Sstevel@tonic-gate */ 247*0Sstevel@tonic-gate static void 248*0Sstevel@tonic-gate defrag(struct page *page) 249*0Sstevel@tonic-gate { 250*0Sstevel@tonic-gate struct block *block; 251*0Sstevel@tonic-gate 252*0Sstevel@tonic-gate for (block = page->block; block; block = block->next) { 253*0Sstevel@tonic-gate struct block *block2; 254*0Sstevel@tonic-gate 255*0Sstevel@tonic-gate if (block->status == BUSY) 256*0Sstevel@tonic-gate continue; 257*0Sstevel@tonic-gate for (block2 = block->next; block2 && block2->status == FREE; 258*0Sstevel@tonic-gate block2 = block2->next) { 259*0Sstevel@tonic-gate block->next = block2->next; 260*0Sstevel@tonic-gate block->size += block2->size + HDR_BLOCK; 261*0Sstevel@tonic-gate } 262*0Sstevel@tonic-gate } 263*0Sstevel@tonic-gate 264*0Sstevel@tonic-gate /* 265*0Sstevel@tonic-gate * Free page 266*0Sstevel@tonic-gate */ 267*0Sstevel@tonic-gate if (page->block->size == page->size - HDR_PAGE) { 268*0Sstevel@tonic-gate if (page == memstart) 269*0Sstevel@tonic-gate memstart = page->next; 270*0Sstevel@tonic-gate else { 271*0Sstevel@tonic-gate struct page *page2; 272*0Sstevel@tonic-gate for (page2 = memstart; page2->next; 273*0Sstevel@tonic-gate page2 = page2->next) { 274*0Sstevel@tonic-gate if (page2->next == page) { 275*0Sstevel@tonic-gate page2->next = page->next; 276*0Sstevel@tonic-gate break; 277*0Sstevel@tonic-gate } 278*0Sstevel@tonic-gate } 279*0Sstevel@tonic-gate } 280*0Sstevel@tonic-gate (void) munmap((caddr_t)page, page->size); 281*0Sstevel@tonic-gate } 282*0Sstevel@tonic-gate } 283