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
49struct 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
67static struct available seed = {
68	OUR_NODEID_MIN, OUR_NODEID_COUNT, NULL, NULL
69};
70
71/*
72 * head of the available list ...
73 */
74static struct available *nhead;
75
76/*
77 * A single lock for the list ...
78 */
79static kmutex_t nodeid_lock;
80
81/*
82 * Helper functions to manage the list ...
83 */
84static struct available *
85np_alloc(int kmflag)
86{
87	return (kmem_zalloc(sizeof (struct available), kmflag));
88}
89
90static void
91np_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 */
99static void
100np_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 */
114static void
115np_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 */
130static void
131np_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 */
152static void
153np_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
168void
169impl_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
184int
185impl_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
220void
221impl_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 */
295int
296impl_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