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