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 (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2006 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 <sys/types.h>
30 #include <sys/sysmacros.h>
31 #include <strings.h>
32 #include <stdlib.h>
33 #include <assert.h>
34 
35 #include <dt_strtab.h>
36 #include <dt_impl.h>
37 
38 static int
39 dt_strtab_grow(dt_strtab_t *sp)
40 {
41 	char *ptr, **bufs;
42 
43 	if ((ptr = malloc(sp->str_bufsz)) == NULL)
44 		return (-1);
45 
46 	bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *));
47 
48 	if (bufs == NULL) {
49 		free(ptr);
50 		return (-1);
51 	}
52 
53 	sp->str_nbufs++;
54 	sp->str_bufs = bufs;
55 	sp->str_ptr = ptr;
56 	sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr;
57 
58 	return (0);
59 }
60 
61 dt_strtab_t *
62 dt_strtab_create(size_t bufsz)
63 {
64 	dt_strtab_t *sp = malloc(sizeof (dt_strtab_t));
65 	uint_t nbuckets = _dtrace_strbuckets;
66 
67 	assert(bufsz != 0);
68 
69 	if (sp == NULL)
70 		return (NULL);
71 
72 	bzero(sp, sizeof (dt_strtab_t));
73 	sp->str_hash = malloc(nbuckets * sizeof (dt_strhash_t *));
74 
75 	if (sp->str_hash == NULL)
76 		goto err;
77 
78 	bzero(sp->str_hash, nbuckets * sizeof (dt_strhash_t *));
79 	sp->str_hashsz = nbuckets;
80 	sp->str_bufs = NULL;
81 	sp->str_ptr = NULL;
82 	sp->str_nbufs = 0;
83 	sp->str_bufsz = bufsz;
84 	sp->str_nstrs = 1;
85 	sp->str_size = 1;
86 
87 	if (dt_strtab_grow(sp) == -1)
88 		goto err;
89 
90 	*sp->str_ptr++ = '\0';
91 	return (sp);
92 
93 err:
94 	dt_strtab_destroy(sp);
95 	return (NULL);
96 }
97 
98 void
99 dt_strtab_destroy(dt_strtab_t *sp)
100 {
101 	dt_strhash_t *hp, *hq;
102 	ulong_t i;
103 
104 	for (i = 0; i < sp->str_hashsz; i++) {
105 		for (hp = sp->str_hash[i]; hp != NULL; hp = hq) {
106 			hq = hp->str_next;
107 			free(hp);
108 		}
109 	}
110 
111 	for (i = 0; i < sp->str_nbufs; i++)
112 		free(sp->str_bufs[i]);
113 
114 	if (sp->str_hash != NULL)
115 		free(sp->str_hash);
116 	if (sp->str_bufs != NULL)
117 		free(sp->str_bufs);
118 
119 	free(sp);
120 }
121 
122 ulong_t
123 dt_strtab_hash(const char *key, size_t *len)
124 {
125 	ulong_t g, h = 0;
126 	const char *p;
127 	size_t n = 0;
128 
129 	for (p = key; *p != '\0'; p++, n++) {
130 		h = (h << 4) + *p;
131 
132 		if ((g = (h & 0xf0000000)) != 0) {
133 			h ^= (g >> 24);
134 			h ^= g;
135 		}
136 	}
137 
138 	if (len != NULL)
139 		*len = n;
140 
141 	return (h);
142 }
143 
144 static int
145 dt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp,
146     const char *str, size_t len)
147 {
148 	ulong_t b = hp->str_buf;
149 	const char *buf = hp->str_data;
150 	size_t resid, n;
151 	int rv;
152 
153 	while (len != 0) {
154 		if (buf == sp->str_bufs[b] + sp->str_bufsz)
155 			buf = sp->str_bufs[++b];
156 
157 		resid = sp->str_bufs[b] + sp->str_bufsz - buf;
158 		n = MIN(resid, len);
159 
160 		if ((rv = strncmp(buf, str, n)) != 0)
161 			return (rv);
162 
163 		buf += n;
164 		str += n;
165 		len -= n;
166 	}
167 
168 	return (0);
169 }
170 
171 static int
172 dt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len)
173 {
174 	char *old_p = sp->str_ptr;
175 	ulong_t old_n = sp->str_nbufs;
176 
177 	ulong_t b = sp->str_nbufs - 1;
178 	size_t resid, n;
179 
180 	while (len != 0) {
181 		if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) {
182 			if (dt_strtab_grow(sp) == -1)
183 				goto err;
184 			b++;
185 		}
186 
187 		resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr;
188 		n = MIN(resid, len);
189 		bcopy(str, sp->str_ptr, n);
190 
191 		sp->str_ptr += n;
192 		str += n;
193 		len -= n;
194 	}
195 
196 	return (0);
197 
198 err:
199 	while (sp->str_nbufs != old_n)
200 		free(sp->str_bufs[--sp->str_nbufs]);
201 
202 	sp->str_ptr = old_p;
203 	return (-1);
204 }
205 
206 ssize_t
207 dt_strtab_index(dt_strtab_t *sp, const char *str)
208 {
209 	dt_strhash_t *hp;
210 	size_t len;
211 	ulong_t h;
212 
213 	if (str == NULL || str[0] == '\0')
214 		return (0); /* we keep a \0 at offset 0 to simplify things */
215 
216 	h = dt_strtab_hash(str, &len) % sp->str_hashsz;
217 
218 	for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) {
219 		if (dt_strtab_compare(sp, hp, str, len + 1) == 0)
220 			return (hp->str_off);
221 	}
222 
223 	return (-1);
224 }
225 
226 ssize_t
227 dt_strtab_insert(dt_strtab_t *sp, const char *str)
228 {
229 	dt_strhash_t *hp;
230 	size_t len;
231 	ssize_t off;
232 	ulong_t h;
233 
234 	if ((off = dt_strtab_index(sp, str)) != -1)
235 		return (off);
236 
237 	h = dt_strtab_hash(str, &len) % sp->str_hashsz;
238 
239 	/*
240 	 * Create a new hash bucket, initialize it, and insert it at the front
241 	 * of the hash chain for the appropriate bucket.
242 	 */
243 	if ((hp = malloc(sizeof (dt_strhash_t))) == NULL)
244 		return (-1L);
245 
246 	hp->str_data = sp->str_ptr;
247 	hp->str_buf = sp->str_nbufs - 1;
248 	hp->str_off = sp->str_size;
249 	hp->str_len = len;
250 	hp->str_next = sp->str_hash[h];
251 
252 	/*
253 	 * Now copy the string data into our buffer list, and then update
254 	 * the global counts of strings and bytes.  Return str's byte offset.
255 	 */
256 	if (dt_strtab_copyin(sp, str, len + 1) == -1)
257 		return (-1L);
258 
259 	sp->str_nstrs++;
260 	sp->str_size += len + 1;
261 	sp->str_hash[h] = hp;
262 
263 	return (hp->str_off);
264 }
265 
266 size_t
267 dt_strtab_size(const dt_strtab_t *sp)
268 {
269 	return (sp->str_size);
270 }
271 
272 ssize_t
273 dt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private)
274 {
275 	ssize_t res, total = 0;
276 	ulong_t i;
277 	size_t n;
278 
279 	for (i = 0; i < sp->str_nbufs; i++, total += res) {
280 		if (i == sp->str_nbufs - 1)
281 			n = sp->str_ptr - sp->str_bufs[i];
282 		else
283 			n = sp->str_bufsz;
284 
285 		if ((res = func(sp->str_bufs[i], n, total, private)) <= 0)
286 			break;
287 	}
288 
289 	if (total == 0 && sp->str_size != 0)
290 		return (-1);
291 
292 	return (total);
293 }
294