/*
 * 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 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/*        All Rights Reserved   */

#include <sys/types.h>


/*
 * Simplified version of malloc(), free() and realloc(), to be linked with
 * utilities that use [s]brk() and do not define their own version of the
 * routines.
 *
 * The algorithm used to get extra memory space by mmap'ing /dev/zero. This
 * breaks if the application closes the open descriptor, so now it uses
 * mmap's MAP_ANON feature.
 *
 * 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 <fcntl.h>
#include <errno.h>
#include <unistd.h>
#include <thread.h>
#include <pthread.h>
#include <synch.h>
#include <string.h>

static mutex_t lock = DEFAULTMUTEX;

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 *))
#define MINSZ           sizeof (double)

/* for convenience */
#ifndef NULL
#define NULL            (0)
#endif

struct page *memstart;
static int pagesize;
static void defrag(struct page *);
static void split(struct block *,  size_t);
static void *malloc_unlocked(size_t);
static size_t align(size_t, int);

void *
malloc(size_t size)
{
        void *retval;
        (void) mutex_lock(&lock);
        retval = malloc_unlocked(size);
        (void) mutex_unlock(&lock);
        return (retval);
}


static void *
malloc_unlocked(size_t size)
{
        struct block *block;
        struct page *page;

        if (pagesize == 0)
                pagesize = (int)sysconf(_SC_PAGESIZE);

        size = align(size, MINSZ);

        /*
         * 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 = align(totsize, pagesize);

                if ((page = (struct page *)mmap(0, totpage,
                    PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0))
                    == 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);

        block->status = BUSY;
        return (&block->memstart);
}

void *
realloc(void *ptr, size_t size)
{
        struct block *block;
        size_t osize;
        void *newptr;

        (void) mutex_lock(&lock);
        if (ptr == NULL) {
                newptr = malloc_unlocked(size);
                (void) mutex_unlock(&lock);
                return (newptr);
        }
        block = (struct block *)((char *)ptr - HDR_BLOCK);
        size = align(size, MINSZ);
        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);
                (void) mutex_unlock(&lock);
                return (ptr);
        }

        newptr = malloc_unlocked(size);
        (void) memcpy(newptr, ptr, osize);
        block->status = FREE;
        defrag(block->page);
        (void) mutex_unlock(&lock);
        return (newptr);
}

void
free(void *ptr)
{
        struct block *block;

        (void) mutex_lock(&lock);
        if (ptr == NULL) {
                (void) mutex_unlock(&lock);
                return;
        }
        block = (struct block *)((char *)ptr - HDR_BLOCK);
        block->status = FREE;

        defrag(block->page);
        (void) mutex_unlock(&lock);
}

/*
 * Align size on an appropriate boundary
 */
static size_t
align(size_t size, int bound)
{
        if (size < bound)
                return ((size_t)bound);
        else
                return (size + bound - 1 - (size + bound - 1) % bound);
}

static void
split(struct block *block, size_t size)
{
        if (block->size > size + sizeof (struct block)) {
                struct block *newblock;
                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;
        }
}

/*
 * Defragmentation
 */
static void
defrag(struct page *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;
                }
        }

        /*
         * Free page
         */
        if (page->block->size == page->size - HDR_PAGE) {
                if (page == memstart)
                        memstart = page->next;
                else {
                        struct page *page2;
                        for (page2 = memstart; page2->next;
                            page2 = page2->next) {
                                if (page2->next == page) {
                                        page2->next = page->next;
                                        break;
                                }
                        }
                }
                (void) munmap((caddr_t)page, page->size);
        }
}

static void
malloc_prepare()
{
        (void) mutex_lock(&lock);
}

static void
malloc_release()
{
        (void) mutex_unlock(&lock);
}

#pragma init(malloc_init)
static void
malloc_init(void)
{
        (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
}