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