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