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 * 85 np_alloc(int kmflag) 86 { 87 return (kmem_zalloc(sizeof (struct available), kmflag)); 88 } 89 90 static void 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 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 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 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 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 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 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 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 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