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
46static size_t
47nv_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
66static mdb_var_t *
67nv_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
103static void
104nv_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 */
124mdb_nv_t *
125mdb_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
141void
142mdb_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
160mdb_var_t *
161mdb_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 */
178static mdb_var_t *
179nv_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 */
201static mdb_var_t *
202nv_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 */
214mdb_var_t *
215mdb_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
277static void
278nv_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
295void
296mdb_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
343notfound:
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
348void
349mdb_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
362mdb_var_t *
363mdb_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
387mdb_var_t *
388mdb_nv_peek(mdb_nv_t *nv)
389{
390	return (nv->nv_iter_elt);
391}
392
393size_t
394mdb_nv_size(mdb_nv_t *nv)
395{
396	return (nv->nv_nelems);
397}
398
399static int
400nv_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
405void
406mdb_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
432void
433mdb_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
444uintmax_t
445mdb_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
453void
454mdb_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
467void *
468mdb_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
476void
477mdb_nv_set_cookie(mdb_var_t *v, void *cookie)
478{
479	mdb_nv_set_value(v, (uintmax_t)(uintptr_t)cookie);
480}
481
482const char *
483mdb_nv_get_name(const mdb_var_t *v)
484{
485	return (NV_NAME(v));
486}
487
488mdb_var_t *
489mdb_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}
496