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