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