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