malloc.c revision 31c6d826a7f7a4ee7d83c8e99f25d82a4a248076
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
* Copyright (c) 1988 AT&T
* All Rights Reserved
*/
/*
* Simplified version of malloc(), calloc() and free(), to be linked with
* utilities that use [s]brk() and do not define their own version of the
* routines.
* The algorithm maps /dev/zero to get extra memory space.
* Each call to mmap() creates a page. The pages are linked in a list.
* Each page is divided in blocks. There is at least one block in a page.
* New memory chunks are allocated on a first-fit basis.
* Freed blocks are joined in larger blocks. Free pages are unmapped.
*/
#include <stdlib.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/debug.h>
#include <memory.h>
#include "_rtld.h"
#include "msg.h"
struct block {
size_t size; /* Space available for user */
struct page *page; /* Backwards reference to page */
int status;
struct block *next;
void * memstart[1];
};
struct page {
size_t size; /* Total page size (incl. header) */
struct page *next;
struct block block[1];
};
#define FREE 0
#define BUSY 1
#define HDR_BLOCK (sizeof (struct block) - sizeof (void *))
#define HDR_PAGE (sizeof (struct page) - sizeof (void *))
static struct page *memstart;
#if DEBUG
/*
* When built for debugging, scribble a pattern over newly allocated and
* freed memory.
*/
#define NEWMEM 0
#define FREMEM 1
/* LINTED */
const ulong_t patterns[] = {
(ulong_t)0xbaddcafebaddcafeULL, (ulong_t)0xdeadbeefdeadbeefULL
};
static void
scribble(ulong_t *membgn, int pattern, size_t size)
{
size_t memsize = size / sizeof (ulong_t);
while (memsize--) {
if (pattern == FREMEM)
ASSERT(*membgn != patterns[pattern]);
*membgn++ = patterns[pattern];
}
}
#endif
/*
* Defragmentation
*/
void
defrag()
{
struct page *page;
Aliste idx;
for (APLIST_TRAVERSE(free_alp, idx, page)) {
struct block *block;
for (block = page->block; block; block = block->next) {
struct block *block2;
if (block->status == BUSY)
continue;
for (block2 = block->next; block2 &&
block2->status == FREE; block2 = block2->next) {
block->next = block2->next;
block->size += block2->size + HDR_BLOCK;
}
}
/*
* If a page becomes free, leave it, and save the unmapping
* expense, as we'll probably come back and reclaim the page
* for later malloc activity.
*
* Free the defrag index.
*/
aplist_delete(free_alp, &idx);
}
}
static void
split(struct block *block, size_t size)
{
if (block->size > size + sizeof (struct block)) {
struct block *newblock;
/* LINTED */
newblock = (struct block *)
((char *)block + HDR_BLOCK + size);
newblock->next = block->next;
block->next = newblock;
newblock->status = FREE;
newblock->page = block->page;
newblock->size = block->size - size - HDR_BLOCK;
block->size = size;
}
}
#include <stdio.h>
/*
* Replace both malloc() and lmalloc() (libc's private memory allocator).
* They are both private here.
*/
#pragma weak lmalloc = malloc
void *
malloc(size_t size)
{
struct block *block;
struct page *page;
size = S_DROUND(size);
/*
* Try to locate necessary space
*/
for (page = memstart; page; page = page->next) {
for (block = page->block; block; block = block->next) {
if ((block->status == FREE) && (block->size >= size))
goto found;
}
}
found:
/*
* Need to allocate a new page
*/
if (!page) {
size_t totsize = size + HDR_PAGE;
size_t totpage = S_ROUND(totsize, syspagsz);
if ((page = dz_map(0, 0, totpage,
PROT_READ | PROT_WRITE | PROT_EXEC,
MAP_PRIVATE)) == MAP_FAILED)
return (0);
page->next = memstart;
memstart = page;
page->size = totpage;
block = page->block;
block->next = 0;
block->status = FREE;
block->size = totpage - HDR_PAGE;
block->page = page;
}
split(block, size);
#if DEBUG
scribble((ulong_t *)&block->memstart, NEWMEM, block->size);
#endif
block->status = BUSY;
return (&block->memstart);
}
void *
calloc(size_t num, size_t size)
{
void * mp;
size_t total;
if (num == 0 || size == 0) {
total = 0;
} else {
total = num * size;
/* check for overflow */
if ((total / num) != size) {
errno = ENOMEM;
return (NULL);
}
}
if ((mp = malloc(total)) == NULL)
return (NULL);
(void) memset(mp, 0, total);
return (mp);
}
void *
realloc(void *ptr, size_t size)
{
struct block *block;
size_t osize;
void * newptr;
if (ptr == NULL)
return (malloc(size));
/* LINTED */
block = (struct block *)((char *)ptr - HDR_BLOCK);
size = S_DROUND(size);
osize = block->size;
/*
* Join block with next one if it is free
*/
if (block->next && block->next->status == FREE) {
block->size += block->next->size + HDR_BLOCK;
block->next = block->next->next;
}
if (size <= block->size) {
split(block, size);
#if DEBUG
if (block->size > osize)
scribble((ulong_t *)((char *)ptr + osize), NEWMEM,
(block->size - osize));
#endif
return (ptr);
}
if ((newptr = malloc(size)) == NULL)
return (NULL);
(void) memcpy(newptr, ptr, osize);
block->status = FREE;
/*
* Add the free block to the free APlist for later defragmentation.
* However, this addition can only be achieved if there is room on the
* free APlist. The APlist can't be allowed to grow, as the growth
* requires a realloc(), which would recurse back here, resulting in an
* infinite loop. If the free APlist is full, defrag() now. This
* defragmentation might not be able to collapse any free space, but
* the free APlist will be cleared as part of the processing, ensuring
* room for the addition.
*/
if (free_alp && (aplist_nitems(free_alp) >= aplist_arritems(free_alp)))
defrag();
(void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST);
return (newptr);
}
/*
* Replace both free() and lfree() (libc's private memory allocator).
* They are both private here.
*/
void
free(void *ptr)
{
struct block *block;
if (ptr == NULL)
return;
/* LINTED */
block = (struct block *)((char *)ptr - HDR_BLOCK);
block->status = FREE;
#if DEBUG
scribble((ulong_t *)&block->memstart, FREMEM, block->size);
#endif
(void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST);
}
/* ARGSUSED1 */
void
lfree(void *ptr, size_t size)
{
free(ptr);
}
/*
* We can use any memory after ld.so.1's .bss up until the next page boundary
* as allocatable memory.
*/
void
addfree(void *ptr, size_t bytes)
{
struct block *block;
struct page *page;
if (bytes <= sizeof (struct page))
return;
page = ptr;
page->next = memstart;
memstart = page;
page->size = bytes;
block = page->block;
block->next = 0;
block->status = FREE;
block->size = bytes - HDR_PAGE;
block->page = page;
}