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 }