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

#include <sys/types.h>
#include <sys/cmn_err.h>
#include <sys/mutex.h>
#include <sys/param.h>          /* for NULL */
#include <sys/debug.h>
#include <sys/memlist.h>
#include <sys/memlist_impl.h>

static struct memlist *memlist_freelist;
static uint_t memlist_freelist_count;
static kmutex_t memlist_freelist_mutex;

/*
 * Caller must test for NULL return.
 */
struct memlist *
memlist_get_one(void)
{
        struct memlist *mlp;

        mutex_enter(&memlist_freelist_mutex);
        mlp = memlist_freelist;
        if (mlp != NULL) {
                memlist_freelist = mlp->ml_next;
                memlist_freelist_count--;
        }
        mutex_exit(&memlist_freelist_mutex);

        return (mlp);
}

void
memlist_free_one(struct memlist *mlp)
{
        ASSERT(mlp != NULL);

        mutex_enter(&memlist_freelist_mutex);
        mlp->ml_next = memlist_freelist;
        memlist_freelist = mlp;
        memlist_freelist_count++;
        mutex_exit(&memlist_freelist_mutex);
}

void
memlist_free_list(struct memlist *mlp)
{
        struct memlist *mlendp;
        uint_t count;

        if (mlp == NULL) {
                return;
        }

        count = 1;
        for (mlendp = mlp; mlendp->ml_next != NULL; mlendp = mlendp->ml_next)
                count++;
        mutex_enter(&memlist_freelist_mutex);
        mlendp->ml_next = memlist_freelist;
        memlist_freelist = mlp;
        memlist_freelist_count += count;
        mutex_exit(&memlist_freelist_mutex);
}

void
memlist_free_block(caddr_t base, size_t bytes)
{
        struct memlist *mlp, *mlendp;
        uint_t count;

        count = bytes / sizeof (struct memlist);
        if (count == 0)
                return;

        mlp = (struct memlist *)base;
        mlendp = &mlp[count - 1];
        for (; mlp != mlendp; mlp++)
                mlp->ml_next = mlp + 1;
        mlendp->ml_next = NULL;
        mlp = (struct memlist *)base;
        mutex_enter(&memlist_freelist_mutex);
        mlendp->ml_next = memlist_freelist;
        memlist_freelist = mlp;
        memlist_freelist_count += count;
        mutex_exit(&memlist_freelist_mutex);
}

/*
 * Insert into a sorted memory list.
 * new = new element to insert
 * curmemlistp = memory list to which to add segment.
 */
void
memlist_insert(
        struct memlist *new,
        struct memlist **curmemlistp)
{
        struct memlist *cur, *last;
        uint64_t start, end;

        start = new->ml_address;
        end = start + new->ml_size;
        last = NULL;
        for (cur = *curmemlistp; cur; cur = cur->ml_next) {
                last = cur;
                if (cur->ml_address >= end) {
                        new->ml_next = cur;
                        new->ml_prev = cur->ml_prev;
                        cur->ml_prev = new;
                        if (cur == *curmemlistp)
                                *curmemlistp = new;
                        else
                                new->ml_prev->ml_next = new;
                        return;
                }
                if (cur->ml_address + cur->ml_size > start)
                        panic("munged memory list = 0x%p\n",
                            (void *)curmemlistp);
        }
        new->ml_next = NULL;
        new->ml_prev = last;
        if (last != NULL) {
                last->ml_next = new;
        } else {
                ASSERT3P(*curmemlistp, ==, NULL);
                *curmemlistp = new;
        }
}

void
memlist_del(struct memlist *memlistp,
    struct memlist **curmemlistp)
{
#ifdef DEBUG
        /*
         * Check that the memlist is on the list.
         */
        struct memlist *mlp;

        for (mlp = *curmemlistp; mlp != NULL; mlp = mlp->ml_next)
                if (mlp == memlistp)
                        break;
        ASSERT(mlp == memlistp);
#endif /* DEBUG */
        if (*curmemlistp == memlistp) {
                ASSERT(memlistp->ml_prev == NULL);
                *curmemlistp = memlistp->ml_next;
        }
        if (memlistp->ml_prev != NULL) {
                ASSERT(memlistp->ml_prev->ml_next == memlistp);
                memlistp->ml_prev->ml_next = memlistp->ml_next;
        }
        if (memlistp->ml_next != NULL) {
                ASSERT(memlistp->ml_next->ml_prev == memlistp);
                memlistp->ml_next->ml_prev = memlistp->ml_prev;
        }
}

struct memlist *
memlist_find(struct memlist *mlp, uint64_t address)
{
        for (; mlp != NULL; mlp = mlp->ml_next)
                if (address >= mlp->ml_address &&
                    address < (mlp->ml_address + mlp->ml_size))
                        break;
        return (mlp);
}

/*
 * Add a span to a memlist.
 * Return:
 * MEML_SPANOP_OK if OK.
 * MEML_SPANOP_ESPAN if part or all of span already exists
 * MEML_SPANOP_EALLOC for allocation failure
 */
int
memlist_add_span(
        uint64_t address,
        uint64_t bytes,
        struct memlist **curmemlistp)
{
        struct memlist *dst;
        struct memlist *prev, *next;

        /*
         * allocate a new struct memlist
         */

        dst = memlist_get_one();

        if (dst == NULL) {
                return (MEML_SPANOP_EALLOC);
        }

        dst->ml_address = address;
        dst->ml_size = bytes;

        /*
         * First insert.
         */
        if (*curmemlistp == NULL) {
                dst->ml_prev = NULL;
                dst->ml_next = NULL;
                *curmemlistp = dst;
                return (MEML_SPANOP_OK);
        }

        /*
         * Insert into sorted list.
         */
        for (prev = NULL, next = *curmemlistp; next != NULL;
            prev = next, next = next->ml_next) {
                if (address > (next->ml_address + next->ml_size))
                        continue;

                /*
                 * Else insert here.
                 */

                /*
                 * Prepend to next.
                 */
                if ((address + bytes) == next->ml_address) {
                        memlist_free_one(dst);

                        next->ml_address = address;
                        next->ml_size += bytes;

                        return (MEML_SPANOP_OK);
                }

                /*
                 * Append to next.
                 */
                if (address == (next->ml_address + next->ml_size)) {
                        memlist_free_one(dst);

                        if (next->ml_next) {
                                /*
                                 * don't overlap with next->ml_next
                                 */
                                if ((address + bytes) >
                                    next->ml_next->ml_address) {
                                        return (MEML_SPANOP_ESPAN);
                                }
                                /*
                                 * Concatenate next and next->ml_next
                                 */
                                if ((address + bytes) ==
                                    next->ml_next->ml_address) {
                                        struct memlist *mlp = next->ml_next;

                                        if (next == *curmemlistp)
                                                *curmemlistp = next->ml_next;

                                        mlp->ml_address = next->ml_address;
                                        mlp->ml_size += next->ml_size;
                                        mlp->ml_size += bytes;

                                        if (next->ml_prev)
                                                next->ml_prev->ml_next = mlp;
                                        mlp->ml_prev = next->ml_prev;

                                        memlist_free_one(next);
                                        return (MEML_SPANOP_OK);
                                }
                        }

                        next->ml_size += bytes;

                        return (MEML_SPANOP_OK);
                }

                /* don't overlap with next */
                if ((address + bytes) > next->ml_address) {
                        memlist_free_one(dst);
                        return (MEML_SPANOP_ESPAN);
                }

                /*
                 * Insert before next.
                 */
                dst->ml_prev = prev;
                dst->ml_next = next;
                next->ml_prev = dst;
                if (prev == NULL) {
                        *curmemlistp = dst;
                } else {
                        prev->ml_next = dst;
                }
                return (MEML_SPANOP_OK);
        }

        /*
         * End of list, prev is valid and next is NULL.
         */
        prev->ml_next = dst;
        dst->ml_prev = prev;
        dst->ml_next = NULL;

        return (MEML_SPANOP_OK);
}

/*
 * Delete a span from a memlist.
 * Return:
 * MEML_SPANOP_OK if OK.
 * MEML_SPANOP_ESPAN if part or all of span does not exist
 * MEML_SPANOP_EALLOC for allocation failure
 */
int
memlist_delete_span(
        uint64_t address,
        uint64_t bytes,
        struct memlist **curmemlistp)
{
        struct memlist *dst, *next;

        /*
         * Find element containing address.
         */
        for (next = *curmemlistp; next != NULL; next = next->ml_next) {
                if ((address >= next->ml_address) &&
                    (address < next->ml_address + next->ml_size))
                        break;
        }

        /*
         * If start address not in list.
         */
        if (next == NULL) {
                return (MEML_SPANOP_ESPAN);
        }

        /*
         * Error if size goes off end of this struct memlist.
         */
        if (address + bytes > next->ml_address + next->ml_size) {
                return (MEML_SPANOP_ESPAN);
        }

        /*
         * Span at beginning of struct memlist.
         */
        if (address == next->ml_address) {
                /*
                 * If start & size match, delete from list.
                 */
                if (bytes == next->ml_size) {
                        if (next == *curmemlistp)
                                *curmemlistp = next->ml_next;
                        if (next->ml_prev != NULL)
                                next->ml_prev->ml_next = next->ml_next;
                        if (next->ml_next != NULL)
                                next->ml_next->ml_prev = next->ml_prev;

                        memlist_free_one(next);
                } else {
                        /*
                         * Increment start address by bytes.
                         */
                        next->ml_address += bytes;
                        next->ml_size -= bytes;
                }
                return (MEML_SPANOP_OK);
        }

        /*
         * Span at end of struct memlist.
         */
        if (address + bytes == next->ml_address + next->ml_size) {
                /*
                 * decrement size by bytes
                 */
                next->ml_size -= bytes;
                return (MEML_SPANOP_OK);
        }

        /*
         * Delete a span in the middle of the struct memlist.
         */
        {
                /*
                 * create a new struct memlist
                 */
                dst = memlist_get_one();

                if (dst == NULL) {
                        return (MEML_SPANOP_EALLOC);
                }

                /*
                 * Existing struct memlist gets address
                 * and size up to start of span.
                 */
                dst->ml_address = address + bytes;
                dst->ml_size =
                    (next->ml_address + next->ml_size) - dst->ml_address;
                next->ml_size = address - next->ml_address;

                /*
                 * New struct memlist gets address starting
                 * after span, until end.
                 */

                /*
                 * link in new memlist after old
                 */
                dst->ml_next = next->ml_next;
                dst->ml_prev = next;

                if (next->ml_next != NULL)
                        next->ml_next->ml_prev = dst;
                next->ml_next = dst;
        }
        return (MEML_SPANOP_OK);
}