17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
51d530678Sraf * Common Development and Distribution License (the "License").
61d530678Sraf * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate
227c478bd9Sstevel@tonic-gate /*
23*7257d1b4Sraf * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
241d530678Sraf * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
271d530678Sraf /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
281d530678Sraf /* All Rights Reserved */
291d530678Sraf
307c478bd9Sstevel@tonic-gate #include <sys/types.h>
317c478bd9Sstevel@tonic-gate
327c478bd9Sstevel@tonic-gate
337c478bd9Sstevel@tonic-gate /*
347c478bd9Sstevel@tonic-gate * Simplified version of malloc(), free() and realloc(), to be linked with
357c478bd9Sstevel@tonic-gate * utilities that use [s]brk() and do not define their own version of the
367c478bd9Sstevel@tonic-gate * routines.
377c478bd9Sstevel@tonic-gate *
387c478bd9Sstevel@tonic-gate * The algorithm used to get extra memory space by mmap'ing /dev/zero. This
397c478bd9Sstevel@tonic-gate * breaks if the application closes the open descriptor, so now it uses
407c478bd9Sstevel@tonic-gate * mmap's MAP_ANON feature.
417c478bd9Sstevel@tonic-gate *
427c478bd9Sstevel@tonic-gate * Each call to mmap() creates a page. The pages are linked in a list.
437c478bd9Sstevel@tonic-gate * Each page is divided in blocks. There is at least one block in a page.
447c478bd9Sstevel@tonic-gate * New memory chunks are allocated on a first-fit basis.
457c478bd9Sstevel@tonic-gate * Freed blocks are joined in larger blocks. Free pages are unmapped.
467c478bd9Sstevel@tonic-gate */
477c478bd9Sstevel@tonic-gate #include <stdlib.h>
487c478bd9Sstevel@tonic-gate #include <sys/types.h>
497c478bd9Sstevel@tonic-gate #include <sys/mman.h>
507c478bd9Sstevel@tonic-gate #include <fcntl.h>
517c478bd9Sstevel@tonic-gate #include <errno.h>
527c478bd9Sstevel@tonic-gate #include <unistd.h>
537c478bd9Sstevel@tonic-gate #include <thread.h>
541d530678Sraf #include <pthread.h>
557c478bd9Sstevel@tonic-gate #include <synch.h>
567c478bd9Sstevel@tonic-gate #include <string.h>
577c478bd9Sstevel@tonic-gate
587c478bd9Sstevel@tonic-gate static mutex_t lock = DEFAULTMUTEX;
597c478bd9Sstevel@tonic-gate
607c478bd9Sstevel@tonic-gate struct block {
617c478bd9Sstevel@tonic-gate size_t size; /* Space available for user */
627c478bd9Sstevel@tonic-gate struct page *page; /* Backwards reference to page */
637c478bd9Sstevel@tonic-gate int status;
647c478bd9Sstevel@tonic-gate struct block *next;
657c478bd9Sstevel@tonic-gate void *memstart[1];
667c478bd9Sstevel@tonic-gate };
677c478bd9Sstevel@tonic-gate
687c478bd9Sstevel@tonic-gate struct page {
697c478bd9Sstevel@tonic-gate size_t size; /* Total page size (incl. header) */
707c478bd9Sstevel@tonic-gate struct page *next;
717c478bd9Sstevel@tonic-gate struct block block[1];
727c478bd9Sstevel@tonic-gate };
737c478bd9Sstevel@tonic-gate
747c478bd9Sstevel@tonic-gate #define FREE 0
757c478bd9Sstevel@tonic-gate #define BUSY 1
767c478bd9Sstevel@tonic-gate
777c478bd9Sstevel@tonic-gate #define HDR_BLOCK (sizeof (struct block) - sizeof (void *))
787c478bd9Sstevel@tonic-gate #define HDR_PAGE (sizeof (struct page) - sizeof (void *))
797c478bd9Sstevel@tonic-gate #define MINSZ sizeof (double)
807c478bd9Sstevel@tonic-gate
817c478bd9Sstevel@tonic-gate /* for convenience */
827c478bd9Sstevel@tonic-gate #ifndef NULL
837c478bd9Sstevel@tonic-gate #define NULL (0)
847c478bd9Sstevel@tonic-gate #endif
857c478bd9Sstevel@tonic-gate
867c478bd9Sstevel@tonic-gate struct page *memstart;
877c478bd9Sstevel@tonic-gate static int pagesize;
887c478bd9Sstevel@tonic-gate static void defrag(struct page *);
897c478bd9Sstevel@tonic-gate static void split(struct block *, size_t);
907c478bd9Sstevel@tonic-gate static void *malloc_unlocked(size_t);
917c478bd9Sstevel@tonic-gate static size_t align(size_t, int);
927c478bd9Sstevel@tonic-gate
937c478bd9Sstevel@tonic-gate void *
malloc(size_t size)947c478bd9Sstevel@tonic-gate malloc(size_t size)
957c478bd9Sstevel@tonic-gate {
967c478bd9Sstevel@tonic-gate void *retval;
977c478bd9Sstevel@tonic-gate (void) mutex_lock(&lock);
987c478bd9Sstevel@tonic-gate retval = malloc_unlocked(size);
997c478bd9Sstevel@tonic-gate (void) mutex_unlock(&lock);
1007c478bd9Sstevel@tonic-gate return (retval);
1017c478bd9Sstevel@tonic-gate }
1027c478bd9Sstevel@tonic-gate
1037c478bd9Sstevel@tonic-gate
1047c478bd9Sstevel@tonic-gate static void *
malloc_unlocked(size_t size)1057c478bd9Sstevel@tonic-gate malloc_unlocked(size_t size)
1067c478bd9Sstevel@tonic-gate {
1077c478bd9Sstevel@tonic-gate struct block *block;
1087c478bd9Sstevel@tonic-gate struct page *page;
1097c478bd9Sstevel@tonic-gate
1107c478bd9Sstevel@tonic-gate if (pagesize == 0)
1117c478bd9Sstevel@tonic-gate pagesize = (int)sysconf(_SC_PAGESIZE);
1127c478bd9Sstevel@tonic-gate
1137c478bd9Sstevel@tonic-gate size = align(size, MINSZ);
1147c478bd9Sstevel@tonic-gate
1157c478bd9Sstevel@tonic-gate /*
1167c478bd9Sstevel@tonic-gate * Try to locate necessary space
1177c478bd9Sstevel@tonic-gate */
1187c478bd9Sstevel@tonic-gate for (page = memstart; page; page = page->next) {
1197c478bd9Sstevel@tonic-gate for (block = page->block; block; block = block->next) {
1207c478bd9Sstevel@tonic-gate if (block->status == FREE && block->size >= size)
1217c478bd9Sstevel@tonic-gate goto found;
1227c478bd9Sstevel@tonic-gate }
1237c478bd9Sstevel@tonic-gate }
1247c478bd9Sstevel@tonic-gate found:
1257c478bd9Sstevel@tonic-gate
1267c478bd9Sstevel@tonic-gate /*
1277c478bd9Sstevel@tonic-gate * Need to allocate a new page
1287c478bd9Sstevel@tonic-gate */
1297c478bd9Sstevel@tonic-gate if (!page) {
1307c478bd9Sstevel@tonic-gate size_t totsize = size + HDR_PAGE;
1317c478bd9Sstevel@tonic-gate size_t totpage = align(totsize, pagesize);
1327c478bd9Sstevel@tonic-gate
1337c478bd9Sstevel@tonic-gate if ((page = (struct page *)mmap(0, totpage,
1347c478bd9Sstevel@tonic-gate PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0))
135*7257d1b4Sraf == MAP_FAILED)
1367c478bd9Sstevel@tonic-gate return (0);
1377c478bd9Sstevel@tonic-gate
1387c478bd9Sstevel@tonic-gate page->next = memstart;
1397c478bd9Sstevel@tonic-gate memstart = page;
1407c478bd9Sstevel@tonic-gate page->size = totpage;
1417c478bd9Sstevel@tonic-gate block = page->block;
1427c478bd9Sstevel@tonic-gate block->next = 0;
1437c478bd9Sstevel@tonic-gate block->status = FREE;
1447c478bd9Sstevel@tonic-gate block->size = totpage - HDR_PAGE;
1457c478bd9Sstevel@tonic-gate block->page = page;
1467c478bd9Sstevel@tonic-gate }
1477c478bd9Sstevel@tonic-gate
1487c478bd9Sstevel@tonic-gate split(block, size);
1497c478bd9Sstevel@tonic-gate
1507c478bd9Sstevel@tonic-gate block->status = BUSY;
1517c478bd9Sstevel@tonic-gate return (&block->memstart);
1527c478bd9Sstevel@tonic-gate }
1537c478bd9Sstevel@tonic-gate
1547c478bd9Sstevel@tonic-gate void *
realloc(void * ptr,size_t size)1557c478bd9Sstevel@tonic-gate realloc(void *ptr, size_t size)
1567c478bd9Sstevel@tonic-gate {
1577c478bd9Sstevel@tonic-gate struct block *block;
1587c478bd9Sstevel@tonic-gate size_t osize;
1597c478bd9Sstevel@tonic-gate void *newptr;
1607c478bd9Sstevel@tonic-gate
1617c478bd9Sstevel@tonic-gate (void) mutex_lock(&lock);
1627c478bd9Sstevel@tonic-gate if (ptr == NULL) {
1637c478bd9Sstevel@tonic-gate newptr = malloc_unlocked(size);
1647c478bd9Sstevel@tonic-gate (void) mutex_unlock(&lock);
1657c478bd9Sstevel@tonic-gate return (newptr);
1667c478bd9Sstevel@tonic-gate }
1677c478bd9Sstevel@tonic-gate block = (struct block *)((char *)ptr - HDR_BLOCK);
1687c478bd9Sstevel@tonic-gate size = align(size, MINSZ);
1697c478bd9Sstevel@tonic-gate osize = block->size;
1707c478bd9Sstevel@tonic-gate
1717c478bd9Sstevel@tonic-gate /*
1727c478bd9Sstevel@tonic-gate * Join block with next one if it is free
1737c478bd9Sstevel@tonic-gate */
1747c478bd9Sstevel@tonic-gate if (block->next && block->next->status == FREE) {
1757c478bd9Sstevel@tonic-gate block->size += block->next->size + HDR_BLOCK;
1767c478bd9Sstevel@tonic-gate block->next = block->next->next;
1777c478bd9Sstevel@tonic-gate }
1787c478bd9Sstevel@tonic-gate
1797c478bd9Sstevel@tonic-gate if (size <= block->size) {
1807c478bd9Sstevel@tonic-gate split(block, size);
1817c478bd9Sstevel@tonic-gate (void) mutex_unlock(&lock);
1827c478bd9Sstevel@tonic-gate return (ptr);
1837c478bd9Sstevel@tonic-gate }
1847c478bd9Sstevel@tonic-gate
1857c478bd9Sstevel@tonic-gate newptr = malloc_unlocked(size);
1867c478bd9Sstevel@tonic-gate (void) memcpy(newptr, ptr, osize);
1877c478bd9Sstevel@tonic-gate block->status = FREE;
1887c478bd9Sstevel@tonic-gate defrag(block->page);
1897c478bd9Sstevel@tonic-gate (void) mutex_unlock(&lock);
1907c478bd9Sstevel@tonic-gate return (newptr);
1917c478bd9Sstevel@tonic-gate }
1927c478bd9Sstevel@tonic-gate
1937c478bd9Sstevel@tonic-gate void
free(void * ptr)1947c478bd9Sstevel@tonic-gate free(void *ptr)
1957c478bd9Sstevel@tonic-gate {
1967c478bd9Sstevel@tonic-gate struct block *block;
1977c478bd9Sstevel@tonic-gate
1987c478bd9Sstevel@tonic-gate (void) mutex_lock(&lock);
1997c478bd9Sstevel@tonic-gate if (ptr == NULL) {
2007c478bd9Sstevel@tonic-gate (void) mutex_unlock(&lock);
2017c478bd9Sstevel@tonic-gate return;
2027c478bd9Sstevel@tonic-gate }
2037c478bd9Sstevel@tonic-gate block = (struct block *)((char *)ptr - HDR_BLOCK);
2047c478bd9Sstevel@tonic-gate block->status = FREE;
2057c478bd9Sstevel@tonic-gate
2067c478bd9Sstevel@tonic-gate defrag(block->page);
2077c478bd9Sstevel@tonic-gate (void) mutex_unlock(&lock);
2087c478bd9Sstevel@tonic-gate }
2097c478bd9Sstevel@tonic-gate
2107c478bd9Sstevel@tonic-gate /*
2117c478bd9Sstevel@tonic-gate * Align size on an appropriate boundary
2127c478bd9Sstevel@tonic-gate */
2137c478bd9Sstevel@tonic-gate static size_t
align(size_t size,int bound)2147c478bd9Sstevel@tonic-gate align(size_t size, int bound)
2157c478bd9Sstevel@tonic-gate {
2167c478bd9Sstevel@tonic-gate if (size < bound)
2177c478bd9Sstevel@tonic-gate return ((size_t)bound);
2187c478bd9Sstevel@tonic-gate else
2197c478bd9Sstevel@tonic-gate return (size + bound - 1 - (size + bound - 1) % bound);
2207c478bd9Sstevel@tonic-gate }
2217c478bd9Sstevel@tonic-gate
2227c478bd9Sstevel@tonic-gate static void
split(struct block * block,size_t size)2237c478bd9Sstevel@tonic-gate split(struct block *block, size_t size)
2247c478bd9Sstevel@tonic-gate {
2257c478bd9Sstevel@tonic-gate if (block->size > size + sizeof (struct block)) {
2267c478bd9Sstevel@tonic-gate struct block *newblock;
2277c478bd9Sstevel@tonic-gate newblock = (struct block *)((char *)block + HDR_BLOCK + size);
2287c478bd9Sstevel@tonic-gate newblock->next = block->next;
2297c478bd9Sstevel@tonic-gate block->next = newblock;
2307c478bd9Sstevel@tonic-gate newblock->status = FREE;
2317c478bd9Sstevel@tonic-gate newblock->page = block->page;
2327c478bd9Sstevel@tonic-gate newblock->size = block->size - size - HDR_BLOCK;
2337c478bd9Sstevel@tonic-gate block->size = size;
2347c478bd9Sstevel@tonic-gate }
2357c478bd9Sstevel@tonic-gate }
2367c478bd9Sstevel@tonic-gate
2377c478bd9Sstevel@tonic-gate /*
2387c478bd9Sstevel@tonic-gate * Defragmentation
2397c478bd9Sstevel@tonic-gate */
2407c478bd9Sstevel@tonic-gate static void
defrag(struct page * page)2417c478bd9Sstevel@tonic-gate defrag(struct page *page)
2427c478bd9Sstevel@tonic-gate {
2437c478bd9Sstevel@tonic-gate struct block *block;
2447c478bd9Sstevel@tonic-gate
2457c478bd9Sstevel@tonic-gate for (block = page->block; block; block = block->next) {
2467c478bd9Sstevel@tonic-gate struct block *block2;
2477c478bd9Sstevel@tonic-gate
2487c478bd9Sstevel@tonic-gate if (block->status == BUSY)
2497c478bd9Sstevel@tonic-gate continue;
2507c478bd9Sstevel@tonic-gate for (block2 = block->next; block2 && block2->status == FREE;
251*7257d1b4Sraf block2 = block2->next) {
2527c478bd9Sstevel@tonic-gate block->next = block2->next;
2537c478bd9Sstevel@tonic-gate block->size += block2->size + HDR_BLOCK;
2547c478bd9Sstevel@tonic-gate }
2557c478bd9Sstevel@tonic-gate }
2567c478bd9Sstevel@tonic-gate
2577c478bd9Sstevel@tonic-gate /*
2587c478bd9Sstevel@tonic-gate * Free page
2597c478bd9Sstevel@tonic-gate */
2607c478bd9Sstevel@tonic-gate if (page->block->size == page->size - HDR_PAGE) {
2617c478bd9Sstevel@tonic-gate if (page == memstart)
2627c478bd9Sstevel@tonic-gate memstart = page->next;
2637c478bd9Sstevel@tonic-gate else {
2647c478bd9Sstevel@tonic-gate struct page *page2;
2657c478bd9Sstevel@tonic-gate for (page2 = memstart; page2->next;
266*7257d1b4Sraf page2 = page2->next) {
2677c478bd9Sstevel@tonic-gate if (page2->next == page) {
2687c478bd9Sstevel@tonic-gate page2->next = page->next;
2697c478bd9Sstevel@tonic-gate break;
2707c478bd9Sstevel@tonic-gate }
2717c478bd9Sstevel@tonic-gate }
2727c478bd9Sstevel@tonic-gate }
2737c478bd9Sstevel@tonic-gate (void) munmap((caddr_t)page, page->size);
2747c478bd9Sstevel@tonic-gate }
2757c478bd9Sstevel@tonic-gate }
2761d530678Sraf
2771d530678Sraf static void
malloc_prepare()2781d530678Sraf malloc_prepare()
2791d530678Sraf {
2801d530678Sraf (void) mutex_lock(&lock);
2811d530678Sraf }
2821d530678Sraf
2831d530678Sraf static void
malloc_release()2841d530678Sraf malloc_release()
2851d530678Sraf {
2861d530678Sraf (void) mutex_unlock(&lock);
2871d530678Sraf }
2881d530678Sraf
2891d530678Sraf #pragma init(malloc_init)
2901d530678Sraf static void
malloc_init(void)2911d530678Sraf malloc_init(void)
2921d530678Sraf {
2931d530678Sraf (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
2941d530678Sraf }
295