/*
 * 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;
}