Home | History | Annotate | Download | only in os
      1 /*
      2  * CDDL HEADER START
      3  *
      4  * The contents of this file are subject to the terms of the
      5  * Common Development and Distribution License, Version 1.0 only
      6  * (the "License").  You may not use this file except in compliance
      7  * with the License.
      8  *
      9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
     10  * or http://www.opensolaris.org/os/licensing.
     11  * See the License for the specific language governing permissions
     12  * and limitations under the License.
     13  *
     14  * When distributing Covered Code, include this CDDL HEADER in each
     15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     16  * If applicable, add the following below this CDDL HEADER, with the
     17  * fields enclosed by brackets "[]" replaced with your own identifying
     18  * information: Portions Copyright [yyyy] [name of copyright owner]
     19  *
     20  * CDDL HEADER END
     21  */
     22 /*
     23  * Copyright (c) 1999 by Sun Microsystems, Inc.
     24  * All rights reserved.
     25  */
     26 
     27 #pragma ident	"@(#)ddi_nodeid.c	1.2	05/06/08 SMI"
     28 
     29 /*
     30  * DDI nodeid management ...
     31  */
     32 
     33 #include <sys/types.h>
     34 #include <sys/ksynch.h>
     35 #include <sys/kmem.h>
     36 #include <sys/cmn_err.h>
     37 #include <sys/ddi.h>
     38 #include <sys/sunddi.h>
     39 #include <sys/ddi_impldefs.h>
     40 #include <sys/ddi_implfuncs.h>
     41 #include <sys/debug.h>
     42 
     43 /*
     44  * Keep a sorted free list of available nodeids.
     45  * Allocating a nodeid won't cause memory allocation.
     46  * Freeing a nodeid does cause memory allocation.
     47  */
     48 
     49 struct available {
     50 	uint32_t nodeid;
     51 	uint32_t count;
     52 	struct available *next;
     53 	struct available *prev;
     54 };
     55 
     56 /*
     57  * The initial seed of available nodeids: 1 .. 0x10000000
     58  * 0, -1 (DEVI_PSEUDO_NODEID) and -2 (DEVI_SID_NODEID) are illegal values
     59  * and may not be used.  Although this code is fully capable of dealing
     60  * with a full 32-bit range of nodeids, we use a low numeric range of
     61  * nodeids as an optimization to avoid overlap with promif nodeids.
     62  */
     63 #define	OUR_NODEID_MIN		((uint32_t)1)
     64 #define	OUR_NODEID_MAX		((uint32_t)0x10000000)
     65 #define	OUR_NODEID_COUNT	((uint32_t)(OUR_NODEID_MAX - OUR_NODEID_MIN))
     66 
     67 static struct available seed = {
     68 	OUR_NODEID_MIN, OUR_NODEID_COUNT, NULL, NULL
     69 };
     70 
     71 /*
     72  * head of the available list ...
     73  */
     74 static struct available *nhead;
     75 
     76 /*
     77  * A single lock for the list ...
     78  */
     79 static kmutex_t nodeid_lock;
     80 
     81 /*
     82  * Helper functions to manage the list ...
     83  */
     84 static struct available *
     85 np_alloc(int kmflag)
     86 {
     87 	return (kmem_zalloc(sizeof (struct available), kmflag));
     88 }
     89 
     90 static void
     91 np_free(struct available *np)
     92 {
     93 	kmem_free(np, sizeof (struct available));
     94 }
     95 
     96 /*
     97  * Unlink a node from the list ... the lock must be held.
     98  */
     99 static void
    100 np_unlink(struct available *np)
    101 {
    102 	if (np->prev)
    103 		np->prev->next = np->next;
    104 	else
    105 		nhead = np->next;
    106 
    107 	if (np->next)
    108 		np->next->prev = np->prev;
    109 }
    110 
    111 /*
    112  * Insert fp before np ... the lock must be held.
    113  */
    114 static void
    115 np_insert(struct available *fp, struct available *np)
    116 {
    117 	fp->prev = np->prev;
    118 	fp->next = np;
    119 
    120 	if (np->prev)
    121 		np->prev->next = fp;
    122 	else
    123 		nhead = fp;
    124 	np->prev = fp;
    125 }
    126 
    127 /*
    128  * Add fp to the end of the list ... the lock must be held.
    129  */
    130 static void
    131 np_add(struct available *fp)
    132 {
    133 	struct available *np;
    134 
    135 	if (nhead == NULL) {
    136 		nhead = fp;
    137 		return;
    138 	}
    139 
    140 	for (np = nhead; np->next != NULL; np = np->next)
    141 		/* empty */;
    142 
    143 	np->next = fp;
    144 	fp->prev = np;
    145 }
    146 
    147 /*
    148  * If this entry and the next entry are consecutive, coalesce the
    149  * two entries into a single entry ... the lock must be held.
    150  * If the entry can be coalesced, the extra entry is freed.
    151  */
    152 static void
    153 np_coalesce(struct available *np)
    154 {
    155 	struct available *xp;
    156 
    157 	xp = np->next;
    158 	if (xp == NULL)
    159 		return;
    160 
    161 	if ((np->nodeid + np->count) == xp->nodeid) {
    162 		np->count += xp->count;
    163 		np_unlink(xp);
    164 		np_free(xp);
    165 	}
    166 }
    167 
    168 void
    169 impl_ddi_init_nodeid(void)
    170 {
    171 	struct available *np;
    172 
    173 	mutex_init(&nodeid_lock, NULL, MUTEX_DEFAULT, NULL);
    174 
    175 	/*
    176 	 * Copy the seed into kmem_alloc-ed memory so we don't have to
    177 	 * worry about not freeing it later.
    178 	 */
    179 	np = np_alloc(KM_SLEEP);
    180 	*np = seed;
    181 	nhead = np;
    182 }
    183 
    184 int
    185 impl_ddi_alloc_nodeid(int *nodeid)
    186 {
    187 	struct available *np;
    188 	int x;
    189 	int unlinked = 0;
    190 
    191 	mutex_enter(&nodeid_lock);
    192 
    193 	if (nhead == NULL) {
    194 		mutex_exit(&nodeid_lock);
    195 		*nodeid = 0;
    196 		return (DDI_FAILURE);
    197 	}
    198 
    199 	np = nhead;
    200 	x = (int)((unsigned int)np->nodeid);
    201 	++np->nodeid;
    202 	--np->count;
    203 	if (np->count == 0) {
    204 		np_unlink(np);
    205 		unlinked = 1;
    206 	}
    207 	mutex_exit(&nodeid_lock);
    208 
    209 	if (unlinked)
    210 		np_free(np);
    211 
    212 	ASSERT(x != 0);
    213 	ASSERT(x != DEVI_PSEUDO_NODEID);
    214 	ASSERT(x != DEVI_SID_NODEID);
    215 
    216 	*nodeid = x;
    217 	return (DDI_SUCCESS);
    218 }
    219 
    220 void
    221 impl_ddi_free_nodeid(int n)
    222 {
    223 	uint32_t nodeid = (uint32_t)n;
    224 	struct available *np, *fp;
    225 
    226 	ASSERT(n != 0);
    227 	ASSERT(n != DEVI_PSEUDO_NODEID);
    228 	ASSERT(n != DEVI_SID_NODEID);
    229 
    230 	/*
    231 	 * Allocate memory wihout holding the lock in case we need it.
    232 	 * If we don't use it, we'll free it.
    233 	 */
    234 	fp = np_alloc(KM_SLEEP);
    235 
    236 	mutex_enter(&nodeid_lock);
    237 
    238 	/*
    239 	 * Insert nodeid in the appropriate place in our sorted available
    240 	 * list. Maintain the list as we do it.
    241 	 */
    242 	for (np = nhead; np != NULL; np = np->next) {
    243 		/*
    244 		 * Add to the beginning of this entry?
    245 		 */
    246 		if ((nodeid + 1) == np->nodeid) {
    247 			np->nodeid = nodeid;
    248 			++np->count;
    249 			mutex_exit(&nodeid_lock);
    250 			np_free(fp);
    251 			return;
    252 		}
    253 		/*
    254 		 * Add to end of this entry? (If yes, try to coalesce
    255 		 * this entry with the next entry.)
    256 		 */
    257 		if (nodeid == (np->nodeid + np->count)) {
    258 			++np->count;
    259 			np_coalesce(np);
    260 			mutex_exit(&nodeid_lock);
    261 			np_free(fp);
    262 			return;
    263 		}
    264 		/*
    265 		 * Does it belong before this entry? (new entry)
    266 		 */
    267 		if (nodeid < np->nodeid)  {
    268 			fp->nodeid = nodeid;
    269 			fp->count = 1;
    270 			np_insert(fp, np);
    271 			mutex_exit(&nodeid_lock);
    272 			return;
    273 		}
    274 		if (nodeid < (np->nodeid + np->count))
    275 			cmn_err(CE_PANIC, "impl_ddi_free_nodeid: "
    276 			    "nodeid %x already free", n);
    277 	}
    278 
    279 	/*
    280 	 * Add a new list item to the end of the list ...
    281 	 */
    282 	fp->nodeid = nodeid;
    283 	fp->count = 1;
    284 	np_add(fp);
    285 	mutex_exit(&nodeid_lock);
    286 }
    287 
    288 /*
    289  * Remove (take) nodeid n off of the available list.
    290  * Returns 0 if successful or -1 if it fails.
    291  *
    292  * A failure indicates we were called with KM_NOSLEEP and we
    293  * couldn't allocate memory when we needed to.
    294  */
    295 int
    296 impl_ddi_take_nodeid(int n, int kmflag)
    297 {
    298 	uint32_t nodeid = (uint32_t)n;
    299 	struct available *np, *fp;
    300 	int unlinked = 0;
    301 
    302 	ASSERT(n != 0);
    303 	ASSERT(n != DEVI_PSEUDO_NODEID);
    304 	ASSERT(n != DEVI_SID_NODEID);
    305 
    306 	/*
    307 	 * If this nodeid is not within the range of nodeids we
    308 	 * manage, we simply succeed.  The initial seed may be
    309 	 * setup so that promif nodeids fall outside our range.
    310 	 */
    311 	if ((nodeid < OUR_NODEID_MIN) || (nodeid > OUR_NODEID_MAX))
    312 		return (0);
    313 
    314 	/*
    315 	 * Allocate memory wihout holding the lock in case we need it.
    316 	 * If we don't use it, we'll free it.
    317 	 */
    318 	fp = np_alloc(kmflag);		/* if KM_NOSLEEP, fp may be NULL */
    319 
    320 	mutex_enter(&nodeid_lock);
    321 
    322 	/*
    323 	 * Find nodeid in our list, if it exists, 'take' it.
    324 	 */
    325 	for (np = nhead; np != NULL; np = np->next) {
    326 
    327 		/*
    328 		 * If it's less than this entry, it's not available...
    329 		 */
    330 		if (nodeid < np->nodeid)
    331 			break;
    332 
    333 		/*
    334 		 * If it's the first entry in this list item, take it ...
    335 		 */
    336 		if ((nodeid) == np->nodeid) {
    337 			++np->nodeid;
    338 			--np->count;
    339 			if (np->count == 0) {
    340 				np_unlink(np);
    341 				++unlinked;
    342 			}
    343 			mutex_exit(&nodeid_lock);
    344 			if (fp)
    345 				np_free(fp);
    346 			if (unlinked)
    347 				np_free(np);
    348 			return (0);
    349 		}
    350 
    351 		/*
    352 		 * If it's the last entry in this list item, take it ...
    353 		 * The count can't be 1 otherwise it would have matched
    354 		 * the beginning of list case, above.
    355 		 */
    356 		if (nodeid == (np->nodeid + np->count - 1)) {
    357 			--np->count;
    358 			ASSERT(np->count != 0);
    359 			mutex_exit(&nodeid_lock);
    360 			if (fp)
    361 				np_free(fp);
    362 			return (0);
    363 		}
    364 
    365 		/*
    366 		 * Is it in the middle of this entry? If it is, we'll
    367 		 * have to split np into two items, removing nodeid
    368 		 * from the middle of the list item.
    369 		 */
    370 		if (nodeid < (np->nodeid + np->count - 1)) {
    371 			if (fp == NULL) {
    372 				/*
    373 				 * We were called with KM_NOSLEEP and
    374 				 * were unable to allocate memory.
    375 				 */
    376 				mutex_exit(&nodeid_lock);
    377 				return (-1);
    378 			}
    379 			/*
    380 			 * Split np, removing nodeid from the middle of
    381 			 * this entry. We already know it isn't on either
    382 			 * end of of this entry, so we know we have to split it.
    383 			 */
    384 			fp->nodeid = np->nodeid;
    385 			fp->count = nodeid - np->nodeid;
    386 			np->nodeid = nodeid + 1;
    387 			np->count = np->count - fp->count - 1;
    388 			ASSERT((fp->count != 0) && (np->count != 0));
    389 			ASSERT(np->nodeid == (fp->nodeid + fp->count + 1));
    390 			np_insert(fp, np);
    391 			mutex_exit(&nodeid_lock);
    392 			return (0);
    393 		}
    394 	}
    395 
    396 	/*
    397 	 * Apparently the nodeid is not available ...
    398 	 */
    399 	mutex_exit(&nodeid_lock);
    400 
    401 	if (fp)
    402 		np_free(fp);
    403 	cmn_err(CE_CONT, "?impl_ddi_take_nodeid: nodeid %x may not "
    404 	    "be unique\n", nodeid);
    405 	return (0);
    406 }
    407