OpenSolaris_b135/uts/common/os/ddi_nodeid.c
/*
* 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.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* 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);
}