/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (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 (c) 1999 by Sun Microsystems, Inc.
 * All rights reserved.
 */

/*
 * DDI nodeid management ...
 */

#include <sys/types.h>
#include <sys/ksynch.h>
#include <sys/kmem.h>
#include <sys/cmn_err.h>
#include <sys/ddi.h>
#include <sys/sunddi.h>
#include <sys/ddi_impldefs.h>
#include <sys/ddi_implfuncs.h>
#include <sys/debug.h>

/*
 * Keep a sorted free list of available nodeids.
 * Allocating a nodeid won't cause memory allocation.
 * Freeing a nodeid does cause memory allocation.
 */

struct available {
        uint32_t nodeid;
        uint32_t count;
        struct available *next;
        struct available *prev;
};

/*
 * The initial seed of available nodeids: 1 .. 0x10000000
 * 0, -1 (DEVI_PSEUDO_NODEID) and -2 (DEVI_SID_NODEID) are illegal values
 * and may not be used.  Although this code is fully capable of dealing
 * with a full 32-bit range of nodeids, we use a low numeric range of
 * nodeids as an optimization to avoid overlap with promif nodeids.
 */
#define OUR_NODEID_MIN          ((uint32_t)1)
#define OUR_NODEID_MAX          ((uint32_t)0x10000000)
#define OUR_NODEID_COUNT        ((uint32_t)(OUR_NODEID_MAX - OUR_NODEID_MIN))

static struct available seed = {
        OUR_NODEID_MIN, OUR_NODEID_COUNT, NULL, NULL
};

/*
 * head of the available list ...
 */
static struct available *nhead;

/*
 * A single lock for the list ...
 */
static kmutex_t nodeid_lock;

/*
 * Helper functions to manage the list ...
 */
static struct available *
np_alloc(int kmflag)
{
        return (kmem_zalloc(sizeof (struct available), kmflag));
}

static void
np_free(struct available *np)
{
        kmem_free(np, sizeof (struct available));
}

/*
 * Unlink a node from the list ... the lock must be held.
 */
static void
np_unlink(struct available *np)
{
        if (np->prev)
                np->prev->next = np->next;
        else
                nhead = np->next;

        if (np->next)
                np->next->prev = np->prev;
}

/*
 * Insert fp before np ... the lock must be held.
 */
static void
np_insert(struct available *fp, struct available *np)
{
        fp->prev = np->prev;
        fp->next = np;

        if (np->prev)
                np->prev->next = fp;
        else
                nhead = fp;
        np->prev = fp;
}

/*
 * Add fp to the end of the list ... the lock must be held.
 */
static void
np_add(struct available *fp)
{
        struct available *np;

        if (nhead == NULL) {
                nhead = fp;
                return;
        }

        for (np = nhead; np->next != NULL; np = np->next)
                /* empty */;

        np->next = fp;
        fp->prev = np;
}

/*
 * If this entry and the next entry are consecutive, coalesce the
 * two entries into a single entry ... the lock must be held.
 * If the entry can be coalesced, the extra entry is freed.
 */
static void
np_coalesce(struct available *np)
{
        struct available *xp;

        xp = np->next;
        if (xp == NULL)
                return;

        if ((np->nodeid + np->count) == xp->nodeid) {
                np->count += xp->count;
                np_unlink(xp);
                np_free(xp);
        }
}

void
impl_ddi_init_nodeid(void)
{
        struct available *np;

        mutex_init(&nodeid_lock, NULL, MUTEX_DEFAULT, NULL);

        /*
         * Copy the seed into kmem_alloc-ed memory so we don't have to
         * worry about not freeing it later.
         */
        np = np_alloc(KM_SLEEP);
        *np = seed;
        nhead = np;
}

int
impl_ddi_alloc_nodeid(int *nodeid)
{
        struct available *np;
        int x;
        int unlinked = 0;

        mutex_enter(&nodeid_lock);

        if (nhead == NULL) {
                mutex_exit(&nodeid_lock);
                *nodeid = 0;
                return (DDI_FAILURE);
        }

        np = nhead;
        x = (int)((unsigned int)np->nodeid);
        ++np->nodeid;
        --np->count;
        if (np->count == 0) {
                np_unlink(np);
                unlinked = 1;
        }
        mutex_exit(&nodeid_lock);

        if (unlinked)
                np_free(np);

        ASSERT(x != 0);
        ASSERT(x != DEVI_PSEUDO_NODEID);
        ASSERT(x != DEVI_SID_NODEID);

        *nodeid = x;
        return (DDI_SUCCESS);
}

void
impl_ddi_free_nodeid(int n)
{
        uint32_t nodeid = (uint32_t)n;
        struct available *np, *fp;

        ASSERT(n != 0);
        ASSERT(n != DEVI_PSEUDO_NODEID);
        ASSERT(n != DEVI_SID_NODEID);

        /*
         * Allocate memory wihout holding the lock in case we need it.
         * If we don't use it, we'll free it.
         */
        fp = np_alloc(KM_SLEEP);

        mutex_enter(&nodeid_lock);

        /*
         * Insert nodeid in the appropriate place in our sorted available
         * list. Maintain the list as we do it.
         */
        for (np = nhead; np != NULL; np = np->next) {
                /*
                 * Add to the beginning of this entry?
                 */
                if ((nodeid + 1) == np->nodeid) {
                        np->nodeid = nodeid;
                        ++np->count;
                        mutex_exit(&nodeid_lock);
                        np_free(fp);
                        return;
                }
                /*
                 * Add to end of this entry? (If yes, try to coalesce
                 * this entry with the next entry.)
                 */
                if (nodeid == (np->nodeid + np->count)) {
                        ++np->count;
                        np_coalesce(np);
                        mutex_exit(&nodeid_lock);
                        np_free(fp);
                        return;
                }
                /*
                 * Does it belong before this entry? (new entry)
                 */
                if (nodeid < np->nodeid)  {
                        fp->nodeid = nodeid;
                        fp->count = 1;
                        np_insert(fp, np);
                        mutex_exit(&nodeid_lock);
                        return;
                }
                if (nodeid < (np->nodeid + np->count))
                        cmn_err(CE_PANIC, "impl_ddi_free_nodeid: "
                            "nodeid %x already free", n);
        }

        /*
         * Add a new list item to the end of the list ...
         */
        fp->nodeid = nodeid;
        fp->count = 1;
        np_add(fp);
        mutex_exit(&nodeid_lock);
}

/*
 * Remove (take) nodeid n off of the available list.
 * Returns 0 if successful or -1 if it fails.
 *
 * A failure indicates we were called with KM_NOSLEEP and we
 * couldn't allocate memory when we needed to.
 */
int
impl_ddi_take_nodeid(int n, int kmflag)
{
        uint32_t nodeid = (uint32_t)n;
        struct available *np, *fp;
        int unlinked = 0;

        ASSERT(n != 0);
        ASSERT(n != DEVI_PSEUDO_NODEID);
        ASSERT(n != DEVI_SID_NODEID);

        /*
         * If this nodeid is not within the range of nodeids we
         * manage, we simply succeed.  The initial seed may be
         * setup so that promif nodeids fall outside our range.
         */
        if ((nodeid < OUR_NODEID_MIN) || (nodeid > OUR_NODEID_MAX))
                return (0);

        /*
         * Allocate memory wihout holding the lock in case we need it.
         * If we don't use it, we'll free it.
         */
        fp = np_alloc(kmflag);          /* if KM_NOSLEEP, fp may be NULL */

        mutex_enter(&nodeid_lock);

        /*
         * Find nodeid in our list, if it exists, 'take' it.
         */
        for (np = nhead; np != NULL; np = np->next) {

                /*
                 * If it's less than this entry, it's not available...
                 */
                if (nodeid < np->nodeid)
                        break;

                /*
                 * If it's the first entry in this list item, take it ...
                 */
                if ((nodeid) == np->nodeid) {
                        ++np->nodeid;
                        --np->count;
                        if (np->count == 0) {
                                np_unlink(np);
                                ++unlinked;
                        }
                        mutex_exit(&nodeid_lock);
                        if (fp)
                                np_free(fp);
                        if (unlinked)
                                np_free(np);
                        return (0);
                }

                /*
                 * If it's the last entry in this list item, take it ...
                 * The count can't be 1 otherwise it would have matched
                 * the beginning of list case, above.
                 */
                if (nodeid == (np->nodeid + np->count - 1)) {
                        --np->count;
                        ASSERT(np->count != 0);
                        mutex_exit(&nodeid_lock);
                        if (fp)
                                np_free(fp);
                        return (0);
                }

                /*
                 * Is it in the middle of this entry? If it is, we'll
                 * have to split np into two items, removing nodeid
                 * from the middle of the list item.
                 */
                if (nodeid < (np->nodeid + np->count - 1)) {
                        if (fp == NULL) {
                                /*
                                 * We were called with KM_NOSLEEP and
                                 * were unable to allocate memory.
                                 */
                                mutex_exit(&nodeid_lock);
                                return (-1);
                        }
                        /*
                         * Split np, removing nodeid from the middle of
                         * this entry. We already know it isn't on either
                         * end of of this entry, so we know we have to split it.
                         */
                        fp->nodeid = np->nodeid;
                        fp->count = nodeid - np->nodeid;
                        np->nodeid = nodeid + 1;
                        np->count = np->count - fp->count - 1;
                        ASSERT((fp->count != 0) && (np->count != 0));
                        ASSERT(np->nodeid == (fp->nodeid + fp->count + 1));
                        np_insert(fp, np);
                        mutex_exit(&nodeid_lock);
                        return (0);
                }
        }

        /*
         * Apparently the nodeid is not available ...
         */
        mutex_exit(&nodeid_lock);

        if (fp)
                np_free(fp);
        cmn_err(CE_CONT, "?impl_ddi_take_nodeid: nodeid %x may not "
            "be unique\n", nodeid);
        return (0);
}