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