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 if (!(nv->nv_um_flags & UM_GC)) 251 mdb_free(nv->nv_hash, sizeof (mdb_var_t *) * nv->nv_hashsz); 252 nv->nv_hash = new_hash; 253 nv->nv_hashsz = new_hashsz; 254 } 255 256 /* 257 * Can return NULL only if the nv's memory allocation flags include UM_NOSLEEP 258 */ 259 mdb_var_t * 260 mdb_nv_insert(mdb_nv_t *nv, const char *name, const mdb_nv_disc_t *disc, 261 uintmax_t value, uint_t flags) 262 { 263 size_t i; 264 mdb_var_t *v; 265 266 ASSERT(!(flags & MDB_NV_EXTNAME) || !(flags & MDB_NV_OVERLOAD)); 267 ASSERT(!(flags & MDB_NV_RDONLY) || !(flags & MDB_NV_OVERLOAD)); 268 269 if (nv->nv_nelems > nv->nv_hashsz && nv->nv_iter_elt == NULL) { 270 nv_resize(nv); 271 } 272 273 i = nv_hashstring(name) % nv->nv_hashsz; 274 275 /* 276 * If the specified name is already hashed, 277 * and MDB_NV_OVERLOAD is set: insert new var into overload chain 278 * and MDB_NV_RDONLY is set: leave var unchanged, issue warning 279 * otherwise: update var with new value 280 */ 281 for (v = nv->nv_hash[i]; v != NULL; v = v->v_next) { 282 if (strcmp(NV_NAME(v), name) == 0) { 283 if (v->v_flags & MDB_NV_OVERLOAD) { 284 mdb_var_t *w = nv_var_alloc(NV_NAME(v), disc, 285 value, flags, nv->nv_um_flags, NULL); 286 287 if (w == NULL) { 288 ASSERT(nv->nv_um_flags & UM_NOSLEEP); 289 return (NULL); 290 } 291 292 if (flags & MDB_NV_INTERPOS) 293 v = nv_var_interpos(nv, i, v, w); 294 else 295 v = nv_var_overload(v, w); 296 297 } else if (v->v_flags & MDB_NV_RDONLY) { 298 if (!(flags & MDB_NV_SILENT)) { 299 warn("cannot modify read-only " 300 "variable '%s'\n", NV_NAME(v)); 301 } 302 } else 303 v->v_uvalue = value; 304 305 ASSERT(v != NULL); 306 return (v); 307 } 308 } 309 310 /* 311 * If the specified name was not found, initialize a new element 312 * and add it to the hash table at the beginning of this chain: 313 */ 314 v = nv_var_alloc(name, disc, value, flags, nv->nv_um_flags, 315 nv->nv_hash[i]); 316 317 if (v == NULL) { 318 ASSERT(nv->nv_um_flags & UM_NOSLEEP); 319 return (NULL); 320 } 321 322 nv->nv_hash[i] = v; 323 nv->nv_nelems++; 324 325 return (v); 326 } 327 328 static void 329 nv_var_defn_remove(mdb_var_t *v, mdb_var_t *corpse, uint_t um_flags) 330 { 331 mdb_var_t *w = v; 332 333 while (v->v_ndef != NULL && v->v_ndef != corpse) 334 v = v->v_ndef; 335 336 if (v == NULL) { 337 fail("var %p ('%s') not found on defn chain of %p\n", 338 (void *)corpse, NV_NAME(corpse), (void *)w); 339 } 340 341 v->v_ndef = corpse->v_ndef; 342 corpse->v_ndef = NULL; 343 nv_var_free(corpse, um_flags); 344 } 345 346 void 347 mdb_nv_remove(mdb_nv_t *nv, mdb_var_t *corpse) 348 { 349 const char *cname = NV_NAME(corpse); 350 size_t i = nv_hashstring(cname) % nv->nv_hashsz; 351 mdb_var_t *v = nv->nv_hash[i]; 352 mdb_var_t **pvp; 353 354 if (corpse->v_flags & MDB_NV_PERSIST) { 355 warn("cannot remove persistent variable '%s'\n", cname); 356 return; 357 } 358 359 if (v != corpse) { 360 do { 361 if (strcmp(NV_NAME(v), cname) == 0) { 362 if (corpse->v_flags & MDB_NV_OVERLOAD) { 363 nv_var_defn_remove(v, corpse, 364 nv->nv_um_flags); 365 return; /* No v_next changes needed */ 366 } else 367 goto notfound; 368 } 369 370 if (v->v_next == corpse) 371 break; /* Corpse is next on the chain */ 372 373 } while ((v = v->v_next) != NULL); 374 375 if (v == NULL) 376 goto notfound; 377 378 pvp = &v->v_next; 379 } else 380 pvp = &nv->nv_hash[i]; 381 382 if ((corpse->v_flags & MDB_NV_OVERLOAD) && corpse->v_ndef != NULL) { 383 corpse->v_ndef->v_next = corpse->v_next; 384 *pvp = corpse->v_ndef; 385 corpse->v_ndef = NULL; 386 } else { 387 *pvp = corpse->v_next; 388 nv->nv_nelems--; 389 } 390 391 nv_var_free(corpse, nv->nv_um_flags); 392 return; 393 394 notfound: 395 fail("var %p ('%s') not found on hash chain: nv=%p [%lu]\n", 396 (void *)corpse, cname, (void *)nv, (ulong_t)i); 397 } 398 399 void 400 mdb_nv_rewind(mdb_nv_t *nv) 401 { 402 size_t i; 403 404 for (i = 0; i < nv->nv_hashsz; i++) { 405 if (nv->nv_hash[i] != NULL) 406 break; 407 } 408 409 nv->nv_iter_elt = i < nv->nv_hashsz ? nv->nv_hash[i] : NULL; 410 nv->nv_iter_bucket = i; 411 } 412 413 mdb_var_t * 414 mdb_nv_advance(mdb_nv_t *nv) 415 { 416 mdb_var_t *v = nv->nv_iter_elt; 417 size_t i; 418 419 if (v == NULL) 420 return (NULL); 421 422 if (v->v_next != NULL) { 423 nv->nv_iter_elt = v->v_next; 424 return (v); 425 } 426 427 for (i = nv->nv_iter_bucket + 1; i < nv->nv_hashsz; i++) { 428 if (nv->nv_hash[i] != NULL) 429 break; 430 } 431 432 nv->nv_iter_elt = i < nv->nv_hashsz ? nv->nv_hash[i] : NULL; 433 nv->nv_iter_bucket = i; 434 435 return (v); 436 } 437 438 mdb_var_t * 439 mdb_nv_peek(mdb_nv_t *nv) 440 { 441 return (nv->nv_iter_elt); 442 } 443 444 size_t 445 mdb_nv_size(mdb_nv_t *nv) 446 { 447 return (nv->nv_nelems); 448 } 449 450 static int 451 nv_compare(const mdb_var_t **lp, const mdb_var_t **rp) 452 { 453 return (strcmp(mdb_nv_get_name(*lp), mdb_nv_get_name(*rp))); 454 } 455 456 void 457 mdb_nv_sort_iter(mdb_nv_t *nv, int (*func)(mdb_var_t *, void *), 458 void *private, uint_t um_flags) 459 { 460 mdb_var_t **vps = 461 mdb_alloc(nv->nv_nelems * sizeof (mdb_var_t *), um_flags); 462 463 if (nv->nv_nelems != 0 && vps != NULL) { 464 mdb_var_t *v, **vpp = vps; 465 size_t i; 466 467 for (mdb_nv_rewind(nv); (v = mdb_nv_advance(nv)) != NULL; ) 468 *vpp++ = v; 469 470 qsort(vps, nv->nv_nelems, sizeof (mdb_var_t *), 471 (int (*)(const void *, const void *))nv_compare); 472 473 for (vpp = vps, i = 0; i < nv->nv_nelems; i++) { 474 if (func(*vpp++, private) == -1) 475 break; 476 } 477 478 if (!(um_flags & UM_GC)) 479 mdb_free(vps, nv->nv_nelems * sizeof (mdb_var_t *)); 480 } 481 } 482 483 void 484 mdb_nv_defn_iter(mdb_var_t *v, int (*func)(mdb_var_t *, void *), void *private) 485 { 486 if (func(v, private) == -1 || !(v->v_flags & MDB_NV_OVERLOAD)) 487 return; 488 489 for (v = v->v_ndef; v != NULL; v = v->v_ndef) { 490 if (func(v, private) == -1) 491 break; 492 } 493 } 494 495 uintmax_t 496 mdb_nv_get_value(const mdb_var_t *v) 497 { 498 if (v->v_disc) 499 return (v->v_disc->disc_get(v)); 500 501 return (v->v_uvalue); 502 } 503 504 void 505 mdb_nv_set_value(mdb_var_t *v, uintmax_t l) 506 { 507 if (v->v_flags & MDB_NV_RDONLY) { 508 warn("cannot modify read-only variable '%s'\n", NV_NAME(v)); 509 return; 510 } 511 512 if (v->v_disc) 513 v->v_disc->disc_set(v, l); 514 else 515 v->v_uvalue = l; 516 } 517 518 void * 519 mdb_nv_get_cookie(const mdb_var_t *v) 520 { 521 if (v->v_disc) 522 return ((void *)(uintptr_t)v->v_disc->disc_get(v)); 523 524 return (MDB_NV_COOKIE(v)); 525 } 526 527 void 528 mdb_nv_set_cookie(mdb_var_t *v, void *cookie) 529 { 530 mdb_nv_set_value(v, (uintmax_t)(uintptr_t)cookie); 531 } 532 533 const char * 534 mdb_nv_get_name(const mdb_var_t *v) 535 { 536 return (NV_NAME(v)); 537 } 538 539 mdb_var_t * 540 mdb_nv_get_ndef(const mdb_var_t *v) 541 { 542 if (v->v_flags & MDB_NV_OVERLOAD) 543 return (v->v_ndef); 544 545 return (NULL); 546 } 547