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
nv_hashstring(const char * key)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 *
nv_var_alloc(const char * name,const mdb_nv_disc_t * disc,uintmax_t value,uint_t flags,uint_t um_flags,mdb_var_t * next)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
nv_var_free(mdb_var_t * v,uint_t um_flags)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 *
mdb_nv_create(mdb_nv_t * nv,uint_t um_flags)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
mdb_nv_destroy(mdb_nv_t * nv)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 *
mdb_nv_lookup(mdb_nv_t * nv,const char * name)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 *
nv_var_interpos(mdb_nv_t * nv,size_t i,mdb_var_t * v,mdb_var_t * w)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 *
nv_var_overload(mdb_var_t * v,mdb_var_t * w)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
nv_resize(mdb_nv_t * nv)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 *
mdb_nv_insert(mdb_nv_t * nv,const char * name,const mdb_nv_disc_t * disc,uintmax_t value,uint_t flags)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
nv_var_defn_remove(mdb_var_t * v,mdb_var_t * corpse,uint_t um_flags)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
mdb_nv_remove(mdb_nv_t * nv,mdb_var_t * corpse)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
mdb_nv_rewind(mdb_nv_t * nv)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 *
mdb_nv_advance(mdb_nv_t * nv)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 *
mdb_nv_peek(mdb_nv_t * nv)438 mdb_nv_peek(mdb_nv_t *nv)
439 {
440 return (nv->nv_iter_elt);
441 }
442
443 size_t
mdb_nv_size(mdb_nv_t * nv)444 mdb_nv_size(mdb_nv_t *nv)
445 {
446 return (nv->nv_nelems);
447 }
448
449 static int
nv_compare(const mdb_var_t ** lp,const mdb_var_t ** rp)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
mdb_nv_sort_iter(mdb_nv_t * nv,int (* func)(mdb_var_t *,void *),void * private,uint_t um_flags)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
mdb_nv_defn_iter(mdb_var_t * v,int (* func)(mdb_var_t *,void *),void * private)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
mdb_nv_get_value(const mdb_var_t * v)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
mdb_nv_set_value(mdb_var_t * v,uintmax_t l)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 *
mdb_nv_get_cookie(const mdb_var_t * v)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
mdb_nv_set_cookie(mdb_var_t * v,void * cookie)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 *
mdb_nv_get_name(const mdb_var_t * v)533 mdb_nv_get_name(const mdb_var_t *v)
534 {
535 return (NV_NAME(v));
536 }
537
538 mdb_var_t *
mdb_nv_get_ndef(const mdb_var_t * v)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