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 2004 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26 
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28 
  29 #include <mdb/mdb_debug.h>
  30 #include <mdb/mdb_string.h>
  31 #include <mdb/mdb_modapi.h>
  32 #include <mdb/mdb_err.h>
  33 #include <mdb/mdb_nv.h>
  34 #include <mdb/mdb.h>
  35 
  36 #define NV_NAME(v) \
  37         (((v)->v_flags & MDB_NV_EXTNAME) ? (v)->v_ename : (v)->v_lname)
  38 
  39 #define NV_SIZE(v) \
  40         (((v)->v_flags & MDB_NV_EXTNAME) ? sizeof (mdb_var_t) : \
  41         sizeof (mdb_var_t) + strlen((v)->v_lname))
  42 
  43 #define NV_HASHSZ       211
  44 
  45 static size_t
  46 nv_hashstring(const char *key)
  47 {
  48         size_t g, h = 0;
  49         const char *p;
  50 
  51         ASSERT(key != NULL);
  52 
  53         for (p = key; *p != '\0'; p++) {
  54                 h = (h << 4) + *p;
  55 
  56                 if ((g = (h & 0xf0000000)) != 0) {
  57                         h ^= (g >> 24);
  58                         h ^= g;
  59                 }
  60         }
  61 
  62         return (h);
  63 }
  64 
  65 static mdb_var_t *
  66 nv_var_alloc(const char *name, const mdb_nv_disc_t *disc,
  67         uintmax_t value, uint_t flags, uint_t um_flags, mdb_var_t *next)
  68 {
  69         size_t nbytes;
  70         mdb_var_t *v;
  71 
  72         if (flags & MDB_NV_EXTNAME)
  73                 nbytes = sizeof (mdb_var_t);
  74         else
  75                 nbytes = sizeof (mdb_var_t) + strlen(name);
  76 
  77         v = mdb_alloc(nbytes, um_flags);
  78 
  79         if (v == NULL)
  80                 return (NULL);
  81 
  82         if (flags & MDB_NV_EXTNAME) {
  83                 v->v_ename = name;
  84                 v->v_lname[0] = '\0';
  85         } else {
  86                 strcpy(v->v_lname, name);
  87                 v->v_ename = NULL;
  88         }
  89 
  90         v->v_uvalue = value;
  91         v->v_flags = flags & ~(MDB_NV_SILENT | MDB_NV_INTERPOS);
  92         v->v_disc = disc;
  93         v->v_next = next;
  94 
  95         return (v);
  96 }
  97 
  98 static void
  99 nv_var_free(mdb_var_t *v, uint_t um_flags)
 100 {
 101         if (um_flags & UM_GC)
 102                 return;
 103 
 104         if (v->v_flags & MDB_NV_OVERLOAD) {
 105                 mdb_var_t *w, *nw;
 106 
 107                 for (w = v->v_ndef; w != NULL; w = nw) {
 108                         nw = w->v_ndef;
 109                         mdb_free(w, NV_SIZE(w));
 110                 }
 111         }
 112 
 113         mdb_free(v, NV_SIZE(v));
 114 }
 115 
 116 /*
 117  * Can return NULL only if the nv's memory allocation flags include UM_NOSLEEP
 118  */
 119 mdb_nv_t *
 120 mdb_nv_create(mdb_nv_t *nv, uint_t um_flags)
 121 {
 122         nv->nv_hash = mdb_zalloc(sizeof (mdb_var_t *) * NV_HASHSZ, um_flags);
 123 
 124         if (nv->nv_hash == NULL)
 125                 return (NULL);
 126 
 127         nv->nv_hashsz = NV_HASHSZ;
 128         nv->nv_nelems = 0;
 129         nv->nv_iter_elt = NULL;
 130         nv->nv_iter_bucket = 0;
 131         nv->nv_um_flags = um_flags;
 132 
 133         return (nv);
 134 }
 135 
 136 void
 137 mdb_nv_destroy(mdb_nv_t *nv)
 138 {
 139         mdb_var_t *v, *w;
 140         size_t i;
 141 
 142         if (nv->nv_um_flags & UM_GC)
 143                 return;
 144 
 145         for (i = 0; i < nv->nv_hashsz; i++) {
 146                 for (v = nv->nv_hash[i]; v != NULL; v = w) {
 147                         w = v->v_next;
 148                         nv_var_free(v, nv->nv_um_flags);
 149                 }
 150         }
 151 
 152         mdb_free(nv->nv_hash, sizeof (mdb_var_t *) * NV_HASHSZ);
 153 }
 154 
 155 mdb_var_t *
 156 mdb_nv_lookup(mdb_nv_t *nv, const char *name)
 157 {
 158         size_t i = nv_hashstring(name) % nv->nv_hashsz;
 159         mdb_var_t *v;
 160 
 161         for (v = nv->nv_hash[i]; v != NULL; v = v->v_next) {
 162                 if (strcmp(NV_NAME(v), name) == 0)
 163                         return (v);
 164         }
 165 
 166         return (NULL);
 167 }
 168 
 169 /*
 170  * Interpose W in place of V.  We replace V with W in nv_hash, and then
 171  * set W's v_ndef overload chain to point at V.
 172  */
 173 static mdb_var_t *
 174 nv_var_interpos(mdb_nv_t *nv, size_t i, mdb_var_t *v, mdb_var_t *w)
 175 {
 176         mdb_var_t **pvp = &nv->nv_hash[i];
 177 
 178         while (*pvp != v) {
 179                 mdb_var_t *vp = *pvp;
 180                 ASSERT(vp != NULL);
 181                 pvp = &vp->v_next;
 182         }
 183 
 184         *pvp = w;
 185         w->v_next = v->v_next;
 186         w->v_ndef = v;
 187         v->v_next = NULL;
 188 
 189         return (w);
 190 }
 191 
 192 /*
 193  * Add W to the end of V's overload chain.  We simply follow v_ndef to the
 194  * end, and then append W.  We don't expect these chains to grow very long.
 195  */
 196 static mdb_var_t *
 197 nv_var_overload(mdb_var_t *v, mdb_var_t *w)
 198 {
 199         while (v->v_ndef != NULL)
 200                 v = v->v_ndef;
 201 
 202         v->v_ndef = w;
 203         return (w);
 204 }
 205 
 206 /*
 207  * Can return NULL only if the nv's memory allocation flags include UM_NOSLEEP
 208  */
 209 mdb_var_t *
 210 mdb_nv_insert(mdb_nv_t *nv, const char *name, const mdb_nv_disc_t *disc,
 211     uintmax_t value, uint_t flags)
 212 {
 213         size_t i = nv_hashstring(name) % nv->nv_hashsz;
 214         mdb_var_t *v;
 215 
 216         ASSERT(!(flags & MDB_NV_EXTNAME) || !(flags & MDB_NV_OVERLOAD));
 217         ASSERT(!(flags & MDB_NV_RDONLY) || !(flags & MDB_NV_OVERLOAD));
 218 
 219         /*
 220          * If the specified name is already hashed,
 221          * and MDB_NV_OVERLOAD is set:  insert new var into overload chain
 222          * and MDB_NV_RDONLY is set:    leave var unchanged, issue warning
 223          * otherwise:                   update var with new value
 224          */
 225         for (v = nv->nv_hash[i]; v != NULL; v = v->v_next) {
 226                 if (strcmp(NV_NAME(v), name) == 0) {
 227                         if (v->v_flags & MDB_NV_OVERLOAD) {
 228                                 mdb_var_t *w = nv_var_alloc(NV_NAME(v), disc,
 229                                     value, flags, nv->nv_um_flags, NULL);
 230 
 231                                 if (w == NULL) {
 232                                         ASSERT(nv->nv_um_flags & UM_NOSLEEP);
 233                                         return (NULL);
 234                                 }
 235 
 236                                 if (flags & MDB_NV_INTERPOS)
 237                                         v = nv_var_interpos(nv, i, v, w);
 238                                 else
 239                                         v = nv_var_overload(v, w);
 240 
 241                         } else if (v->v_flags & MDB_NV_RDONLY) {
 242                                 if (!(flags & MDB_NV_SILENT)) {
 243                                         warn("cannot modify read-only "
 244                                             "variable '%s'\n", NV_NAME(v));
 245                                 }
 246                         } else
 247                                 v->v_uvalue = value;
 248 
 249                         ASSERT(v != NULL);
 250                         return (v);
 251                 }
 252         }
 253 
 254         /*
 255          * If the specified name was not found, initialize a new element
 256          * and add it to the hash table at the beginning of this chain:
 257          */
 258         v = nv_var_alloc(name, disc, value, flags, nv->nv_um_flags,
 259             nv->nv_hash[i]);
 260 
 261         if (v == NULL) {
 262                 ASSERT(nv->nv_um_flags & UM_NOSLEEP);
 263                 return (NULL);
 264         }
 265 
 266         nv->nv_hash[i] = v;
 267         nv->nv_nelems++;
 268 
 269         return (v);
 270 }
 271 
 272 static void
 273 nv_var_defn_remove(mdb_var_t *v, mdb_var_t *corpse, uint_t um_flags)
 274 {
 275         mdb_var_t *w = v;
 276 
 277         while (v->v_ndef != NULL && v->v_ndef != corpse)
 278                 v = v->v_ndef;
 279 
 280         if (v == NULL) {
 281                 fail("var %p ('%s') not found on defn chain of %p\n",
 282                     (void *)corpse, NV_NAME(corpse), (void *)w);
 283         }
 284 
 285         v->v_ndef = corpse->v_ndef;
 286         corpse->v_ndef = NULL;
 287         nv_var_free(corpse, um_flags);
 288 }
 289 
 290 void
 291 mdb_nv_remove(mdb_nv_t *nv, mdb_var_t *corpse)
 292 {
 293         const char *cname = NV_NAME(corpse);
 294         size_t i = nv_hashstring(cname) % nv->nv_hashsz;
 295         mdb_var_t *v = nv->nv_hash[i];
 296         mdb_var_t **pvp;
 297 
 298         if (corpse->v_flags & MDB_NV_PERSIST) {
 299                 warn("cannot remove persistent variable '%s'\n", cname);
 300                 return;
 301         }
 302 
 303         if (v != corpse) {
 304                 do {
 305                         if (strcmp(NV_NAME(v), cname) == 0) {
 306                                 if (corpse->v_flags & MDB_NV_OVERLOAD) {
 307                                         nv_var_defn_remove(v, corpse,
 308                                             nv->nv_um_flags);
 309                                         return; /* No v_next changes needed */
 310                                 } else
 311                                         goto notfound;
 312                         }
 313 
 314                         if (v->v_next == corpse)
 315                                 break; /* Corpse is next on the chain */
 316 
 317                 } while ((v = v->v_next) != NULL);
 318 
 319                 if (v == NULL)
 320                         goto notfound;
 321 
 322                 pvp = &v->v_next;
 323         } else
 324                 pvp = &nv->nv_hash[i];
 325 
 326         if ((corpse->v_flags & MDB_NV_OVERLOAD) && corpse->v_ndef != NULL) {
 327                 corpse->v_ndef->v_next = corpse->v_next;
 328                 *pvp = corpse->v_ndef;
 329                 corpse->v_ndef = NULL;
 330         } else {
 331                 *pvp = corpse->v_next;
 332                 nv->nv_nelems--;
 333         }
 334 
 335         nv_var_free(corpse, nv->nv_um_flags);
 336         return;
 337 
 338 notfound:
 339         fail("var %p ('%s') not found on hash chain: nv=%p [%lu]\n",
 340             (void *)corpse, cname, (void *)nv, (ulong_t)i);
 341 }
 342 
 343 void
 344 mdb_nv_rewind(mdb_nv_t *nv)
 345 {
 346         size_t i;
 347 
 348         for (i = 0; i < nv->nv_hashsz; i++) {
 349                 if (nv->nv_hash[i] != NULL)
 350                         break;
 351         }
 352 
 353         nv->nv_iter_elt = i < nv->nv_hashsz ? nv->nv_hash[i] : NULL;
 354         nv->nv_iter_bucket = i;
 355 }
 356 
 357 mdb_var_t *
 358 mdb_nv_advance(mdb_nv_t *nv)
 359 {
 360         mdb_var_t *v = nv->nv_iter_elt;
 361         size_t i;
 362 
 363         if (v == NULL)
 364                 return (NULL);
 365 
 366         if (v->v_next != NULL) {
 367                 nv->nv_iter_elt = v->v_next;
 368                 return (v);
 369         }
 370 
 371         for (i = nv->nv_iter_bucket + 1; i < nv->nv_hashsz; i++) {
 372                 if (nv->nv_hash[i] != NULL)
 373                         break;
 374         }
 375 
 376         nv->nv_iter_elt = i < nv->nv_hashsz ? nv->nv_hash[i] : NULL;
 377         nv->nv_iter_bucket = i;
 378 
 379         return (v);
 380 }
 381 
 382 mdb_var_t *
 383 mdb_nv_peek(mdb_nv_t *nv)
 384 {
 385         return (nv->nv_iter_elt);
 386 }
 387 
 388 size_t
 389 mdb_nv_size(mdb_nv_t *nv)
 390 {
 391         return (nv->nv_nelems);
 392 }
 393 
 394 static int
 395 nv_compare(const mdb_var_t **lp, const mdb_var_t **rp)
 396 {
 397         return (strcmp(mdb_nv_get_name(*lp), mdb_nv_get_name(*rp)));
 398 }
 399 
 400 void
 401 mdb_nv_sort_iter(mdb_nv_t *nv, int (*func)(mdb_var_t *, void *),
 402     void *private, uint_t um_flags)
 403 {
 404         mdb_var_t **vps =
 405             mdb_alloc(nv->nv_nelems * sizeof (mdb_var_t *), um_flags);
 406 
 407         if (nv->nv_nelems != 0 && vps != NULL) {
 408                 mdb_var_t *v, **vpp = vps;
 409                 size_t i;
 410 
 411                 for (mdb_nv_rewind(nv); (v = mdb_nv_advance(nv)) != NULL; )
 412                         *vpp++ = v;
 413 
 414                 qsort(vps, nv->nv_nelems, sizeof (mdb_var_t *),
 415                     (int (*)(const void *, const void *))nv_compare);
 416 
 417                 for (vpp = vps, i = 0; i < nv->nv_nelems; i++) {
 418                         if (func(*vpp++, private) == -1)
 419                                 break;
 420                 }
 421 
 422                 if (!(um_flags & UM_GC))
 423                         mdb_free(vps, nv->nv_nelems * sizeof (mdb_var_t *));
 424         }
 425 }
 426 
 427 void
 428 mdb_nv_defn_iter(mdb_var_t *v, int (*func)(mdb_var_t *, void *), void *private)
 429 {
 430         if (func(v, private) == -1 || !(v->v_flags & MDB_NV_OVERLOAD))
 431                 return;
 432 
 433         for (v = v->v_ndef; v != NULL; v = v->v_ndef) {
 434                 if (func(v, private) == -1)
 435                         break;
 436         }
 437 }
 438 
 439 uintmax_t
 440 mdb_nv_get_value(const mdb_var_t *v)
 441 {
 442         if (v->v_disc)
 443                 return (v->v_disc->disc_get(v));
 444 
 445         return (v->v_uvalue);
 446 }
 447 
 448 void
 449 mdb_nv_set_value(mdb_var_t *v, uintmax_t l)
 450 {
 451         if (v->v_flags & MDB_NV_RDONLY) {
 452                 warn("cannot modify read-only variable '%s'\n", NV_NAME(v));
 453                 return;
 454         }
 455 
 456         if (v->v_disc)
 457                 v->v_disc->disc_set(v, l);
 458         else
 459                 v->v_uvalue = l;
 460 }
 461 
 462 void *
 463 mdb_nv_get_cookie(const mdb_var_t *v)
 464 {
 465         if (v->v_disc)
 466                 return ((void *)(uintptr_t)v->v_disc->disc_get(v));
 467 
 468         return (MDB_NV_COOKIE(v));
 469 }
 470 
 471 void
 472 mdb_nv_set_cookie(mdb_var_t *v, void *cookie)
 473 {
 474         mdb_nv_set_value(v, (uintmax_t)(uintptr_t)cookie);
 475 }
 476 
 477 const char *
 478 mdb_nv_get_name(const mdb_var_t *v)
 479 {
 480         return (NV_NAME(v));
 481 }
 482 
 483 mdb_var_t *
 484 mdb_nv_get_ndef(const mdb_var_t *v)
 485 {
 486         if (v->v_flags & MDB_NV_OVERLOAD)
 487                 return (v->v_ndef);
 488 
 489         return (NULL);
 490 }