kernel/os/ddi_nodeid.c

   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 }