xref: /titanic_41/usr/src/uts/common/os/ddi_nodeid.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
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	"%Z%%M%	%I%	%E% 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 *
np_alloc(int kmflag)85 np_alloc(int kmflag)
86 {
87 	return (kmem_zalloc(sizeof (struct available), kmflag));
88 }
89 
90 static void
np_free(struct available * np)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
np_unlink(struct available * np)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
np_insert(struct available * fp,struct available * np)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
np_add(struct available * fp)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
np_coalesce(struct available * np)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
impl_ddi_init_nodeid(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
impl_ddi_alloc_nodeid(int * nodeid)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
impl_ddi_free_nodeid(int n)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
impl_ddi_take_nodeid(int n,int kmflag)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