17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*2b6e762cSahl * Common Development and Distribution License (the "License").
6*2b6e762cSahl * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
21*2b6e762cSahl
227c478bd9Sstevel@tonic-gate /*
23*2b6e762cSahl * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate #include <sys/types.h>
287c478bd9Sstevel@tonic-gate #include <sys/sysmacros.h>
297c478bd9Sstevel@tonic-gate #include <strings.h>
307c478bd9Sstevel@tonic-gate #include <stdlib.h>
317c478bd9Sstevel@tonic-gate #include <assert.h>
327c478bd9Sstevel@tonic-gate
337c478bd9Sstevel@tonic-gate #include <dt_strtab.h>
347c478bd9Sstevel@tonic-gate #include <dt_impl.h>
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate static int
dt_strtab_grow(dt_strtab_t * sp)377c478bd9Sstevel@tonic-gate dt_strtab_grow(dt_strtab_t *sp)
387c478bd9Sstevel@tonic-gate {
397c478bd9Sstevel@tonic-gate char *ptr, **bufs;
407c478bd9Sstevel@tonic-gate
417c478bd9Sstevel@tonic-gate if ((ptr = malloc(sp->str_bufsz)) == NULL)
427c478bd9Sstevel@tonic-gate return (-1);
437c478bd9Sstevel@tonic-gate
447c478bd9Sstevel@tonic-gate bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *));
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate if (bufs == NULL) {
477c478bd9Sstevel@tonic-gate free(ptr);
487c478bd9Sstevel@tonic-gate return (-1);
497c478bd9Sstevel@tonic-gate }
507c478bd9Sstevel@tonic-gate
517c478bd9Sstevel@tonic-gate sp->str_nbufs++;
527c478bd9Sstevel@tonic-gate sp->str_bufs = bufs;
537c478bd9Sstevel@tonic-gate sp->str_ptr = ptr;
547c478bd9Sstevel@tonic-gate sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr;
557c478bd9Sstevel@tonic-gate
567c478bd9Sstevel@tonic-gate return (0);
577c478bd9Sstevel@tonic-gate }
587c478bd9Sstevel@tonic-gate
597c478bd9Sstevel@tonic-gate dt_strtab_t *
dt_strtab_create(size_t bufsz)607c478bd9Sstevel@tonic-gate dt_strtab_create(size_t bufsz)
617c478bd9Sstevel@tonic-gate {
627c478bd9Sstevel@tonic-gate dt_strtab_t *sp = malloc(sizeof (dt_strtab_t));
637c478bd9Sstevel@tonic-gate uint_t nbuckets = _dtrace_strbuckets;
647c478bd9Sstevel@tonic-gate
657c478bd9Sstevel@tonic-gate assert(bufsz != 0);
667c478bd9Sstevel@tonic-gate
677c478bd9Sstevel@tonic-gate if (sp == NULL)
687c478bd9Sstevel@tonic-gate return (NULL);
697c478bd9Sstevel@tonic-gate
707c478bd9Sstevel@tonic-gate bzero(sp, sizeof (dt_strtab_t));
717c478bd9Sstevel@tonic-gate sp->str_hash = malloc(nbuckets * sizeof (dt_strhash_t *));
727c478bd9Sstevel@tonic-gate
737c478bd9Sstevel@tonic-gate if (sp->str_hash == NULL)
747c478bd9Sstevel@tonic-gate goto err;
757c478bd9Sstevel@tonic-gate
767c478bd9Sstevel@tonic-gate bzero(sp->str_hash, nbuckets * sizeof (dt_strhash_t *));
777c478bd9Sstevel@tonic-gate sp->str_hashsz = nbuckets;
787c478bd9Sstevel@tonic-gate sp->str_bufs = NULL;
797c478bd9Sstevel@tonic-gate sp->str_ptr = NULL;
807c478bd9Sstevel@tonic-gate sp->str_nbufs = 0;
817c478bd9Sstevel@tonic-gate sp->str_bufsz = bufsz;
827c478bd9Sstevel@tonic-gate sp->str_nstrs = 1;
837c478bd9Sstevel@tonic-gate sp->str_size = 1;
847c478bd9Sstevel@tonic-gate
857c478bd9Sstevel@tonic-gate if (dt_strtab_grow(sp) == -1)
867c478bd9Sstevel@tonic-gate goto err;
877c478bd9Sstevel@tonic-gate
887c478bd9Sstevel@tonic-gate *sp->str_ptr++ = '\0';
897c478bd9Sstevel@tonic-gate return (sp);
907c478bd9Sstevel@tonic-gate
917c478bd9Sstevel@tonic-gate err:
927c478bd9Sstevel@tonic-gate dt_strtab_destroy(sp);
937c478bd9Sstevel@tonic-gate return (NULL);
947c478bd9Sstevel@tonic-gate }
957c478bd9Sstevel@tonic-gate
967c478bd9Sstevel@tonic-gate void
dt_strtab_destroy(dt_strtab_t * sp)977c478bd9Sstevel@tonic-gate dt_strtab_destroy(dt_strtab_t *sp)
987c478bd9Sstevel@tonic-gate {
997c478bd9Sstevel@tonic-gate dt_strhash_t *hp, *hq;
1007c478bd9Sstevel@tonic-gate ulong_t i;
1017c478bd9Sstevel@tonic-gate
1027c478bd9Sstevel@tonic-gate for (i = 0; i < sp->str_hashsz; i++) {
1037c478bd9Sstevel@tonic-gate for (hp = sp->str_hash[i]; hp != NULL; hp = hq) {
1047c478bd9Sstevel@tonic-gate hq = hp->str_next;
1057c478bd9Sstevel@tonic-gate free(hp);
1067c478bd9Sstevel@tonic-gate }
1077c478bd9Sstevel@tonic-gate }
1087c478bd9Sstevel@tonic-gate
1097c478bd9Sstevel@tonic-gate for (i = 0; i < sp->str_nbufs; i++)
1107c478bd9Sstevel@tonic-gate free(sp->str_bufs[i]);
1117c478bd9Sstevel@tonic-gate
1127c478bd9Sstevel@tonic-gate if (sp->str_hash != NULL)
1137c478bd9Sstevel@tonic-gate free(sp->str_hash);
1147c478bd9Sstevel@tonic-gate if (sp->str_bufs != NULL)
1157c478bd9Sstevel@tonic-gate free(sp->str_bufs);
1167c478bd9Sstevel@tonic-gate
1177c478bd9Sstevel@tonic-gate free(sp);
1187c478bd9Sstevel@tonic-gate }
1197c478bd9Sstevel@tonic-gate
1207c478bd9Sstevel@tonic-gate ulong_t
dt_strtab_hash(const char * key,size_t * len)1217c478bd9Sstevel@tonic-gate dt_strtab_hash(const char *key, size_t *len)
1227c478bd9Sstevel@tonic-gate {
1237c478bd9Sstevel@tonic-gate ulong_t g, h = 0;
1247c478bd9Sstevel@tonic-gate const char *p;
1257c478bd9Sstevel@tonic-gate size_t n = 0;
1267c478bd9Sstevel@tonic-gate
1277c478bd9Sstevel@tonic-gate for (p = key; *p != '\0'; p++, n++) {
1287c478bd9Sstevel@tonic-gate h = (h << 4) + *p;
1297c478bd9Sstevel@tonic-gate
1307c478bd9Sstevel@tonic-gate if ((g = (h & 0xf0000000)) != 0) {
1317c478bd9Sstevel@tonic-gate h ^= (g >> 24);
1327c478bd9Sstevel@tonic-gate h ^= g;
1337c478bd9Sstevel@tonic-gate }
1347c478bd9Sstevel@tonic-gate }
1357c478bd9Sstevel@tonic-gate
1367c478bd9Sstevel@tonic-gate if (len != NULL)
1377c478bd9Sstevel@tonic-gate *len = n;
1387c478bd9Sstevel@tonic-gate
1397c478bd9Sstevel@tonic-gate return (h);
1407c478bd9Sstevel@tonic-gate }
1417c478bd9Sstevel@tonic-gate
1427c478bd9Sstevel@tonic-gate static int
dt_strtab_compare(dt_strtab_t * sp,dt_strhash_t * hp,const char * str,size_t len)1437c478bd9Sstevel@tonic-gate dt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp,
1447c478bd9Sstevel@tonic-gate const char *str, size_t len)
1457c478bd9Sstevel@tonic-gate {
1467c478bd9Sstevel@tonic-gate ulong_t b = hp->str_buf;
1477c478bd9Sstevel@tonic-gate const char *buf = hp->str_data;
1487c478bd9Sstevel@tonic-gate size_t resid, n;
1497c478bd9Sstevel@tonic-gate int rv;
1507c478bd9Sstevel@tonic-gate
1517c478bd9Sstevel@tonic-gate while (len != 0) {
1527c478bd9Sstevel@tonic-gate if (buf == sp->str_bufs[b] + sp->str_bufsz)
1537c478bd9Sstevel@tonic-gate buf = sp->str_bufs[++b];
1547c478bd9Sstevel@tonic-gate
1557c478bd9Sstevel@tonic-gate resid = sp->str_bufs[b] + sp->str_bufsz - buf;
1567c478bd9Sstevel@tonic-gate n = MIN(resid, len);
1577c478bd9Sstevel@tonic-gate
1587c478bd9Sstevel@tonic-gate if ((rv = strncmp(buf, str, n)) != 0)
1597c478bd9Sstevel@tonic-gate return (rv);
1607c478bd9Sstevel@tonic-gate
1617c478bd9Sstevel@tonic-gate buf += n;
1627c478bd9Sstevel@tonic-gate str += n;
1637c478bd9Sstevel@tonic-gate len -= n;
1647c478bd9Sstevel@tonic-gate }
1657c478bd9Sstevel@tonic-gate
1667c478bd9Sstevel@tonic-gate return (0);
1677c478bd9Sstevel@tonic-gate }
1687c478bd9Sstevel@tonic-gate
1697c478bd9Sstevel@tonic-gate static int
dt_strtab_copyin(dt_strtab_t * sp,const char * str,size_t len)1707c478bd9Sstevel@tonic-gate dt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len)
1717c478bd9Sstevel@tonic-gate {
1727c478bd9Sstevel@tonic-gate char *old_p = sp->str_ptr;
1737c478bd9Sstevel@tonic-gate ulong_t old_n = sp->str_nbufs;
1747c478bd9Sstevel@tonic-gate
1757c478bd9Sstevel@tonic-gate ulong_t b = sp->str_nbufs - 1;
1767c478bd9Sstevel@tonic-gate size_t resid, n;
1777c478bd9Sstevel@tonic-gate
1787c478bd9Sstevel@tonic-gate while (len != 0) {
1797c478bd9Sstevel@tonic-gate if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) {
1807c478bd9Sstevel@tonic-gate if (dt_strtab_grow(sp) == -1)
1817c478bd9Sstevel@tonic-gate goto err;
1827c478bd9Sstevel@tonic-gate b++;
1837c478bd9Sstevel@tonic-gate }
1847c478bd9Sstevel@tonic-gate
1857c478bd9Sstevel@tonic-gate resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr;
1867c478bd9Sstevel@tonic-gate n = MIN(resid, len);
1877c478bd9Sstevel@tonic-gate bcopy(str, sp->str_ptr, n);
1887c478bd9Sstevel@tonic-gate
1897c478bd9Sstevel@tonic-gate sp->str_ptr += n;
1907c478bd9Sstevel@tonic-gate str += n;
1917c478bd9Sstevel@tonic-gate len -= n;
1927c478bd9Sstevel@tonic-gate }
1937c478bd9Sstevel@tonic-gate
1947c478bd9Sstevel@tonic-gate return (0);
1957c478bd9Sstevel@tonic-gate
1967c478bd9Sstevel@tonic-gate err:
1977c478bd9Sstevel@tonic-gate while (sp->str_nbufs != old_n)
1987c478bd9Sstevel@tonic-gate free(sp->str_bufs[--sp->str_nbufs]);
1997c478bd9Sstevel@tonic-gate
2007c478bd9Sstevel@tonic-gate sp->str_ptr = old_p;
2017c478bd9Sstevel@tonic-gate return (-1);
2027c478bd9Sstevel@tonic-gate }
2037c478bd9Sstevel@tonic-gate
2047c478bd9Sstevel@tonic-gate ssize_t
dt_strtab_index(dt_strtab_t * sp,const char * str)205*2b6e762cSahl dt_strtab_index(dt_strtab_t *sp, const char *str)
2067c478bd9Sstevel@tonic-gate {
2077c478bd9Sstevel@tonic-gate dt_strhash_t *hp;
2087c478bd9Sstevel@tonic-gate size_t len;
2097c478bd9Sstevel@tonic-gate ulong_t h;
2107c478bd9Sstevel@tonic-gate
2117c478bd9Sstevel@tonic-gate if (str == NULL || str[0] == '\0')
2127c478bd9Sstevel@tonic-gate return (0); /* we keep a \0 at offset 0 to simplify things */
2137c478bd9Sstevel@tonic-gate
2147c478bd9Sstevel@tonic-gate h = dt_strtab_hash(str, &len) % sp->str_hashsz;
2157c478bd9Sstevel@tonic-gate
2167c478bd9Sstevel@tonic-gate for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) {
2177c478bd9Sstevel@tonic-gate if (dt_strtab_compare(sp, hp, str, len + 1) == 0)
2187c478bd9Sstevel@tonic-gate return (hp->str_off);
2197c478bd9Sstevel@tonic-gate }
2207c478bd9Sstevel@tonic-gate
221*2b6e762cSahl return (-1);
222*2b6e762cSahl }
223*2b6e762cSahl
224*2b6e762cSahl ssize_t
dt_strtab_insert(dt_strtab_t * sp,const char * str)225*2b6e762cSahl dt_strtab_insert(dt_strtab_t *sp, const char *str)
226*2b6e762cSahl {
227*2b6e762cSahl dt_strhash_t *hp;
228*2b6e762cSahl size_t len;
229*2b6e762cSahl ssize_t off;
230*2b6e762cSahl ulong_t h;
231*2b6e762cSahl
232*2b6e762cSahl if ((off = dt_strtab_index(sp, str)) != -1)
233*2b6e762cSahl return (off);
234*2b6e762cSahl
235*2b6e762cSahl h = dt_strtab_hash(str, &len) % sp->str_hashsz;
236*2b6e762cSahl
2377c478bd9Sstevel@tonic-gate /*
2387c478bd9Sstevel@tonic-gate * Create a new hash bucket, initialize it, and insert it at the front
2397c478bd9Sstevel@tonic-gate * of the hash chain for the appropriate bucket.
2407c478bd9Sstevel@tonic-gate */
2417c478bd9Sstevel@tonic-gate if ((hp = malloc(sizeof (dt_strhash_t))) == NULL)
2427c478bd9Sstevel@tonic-gate return (-1L);
2437c478bd9Sstevel@tonic-gate
2447c478bd9Sstevel@tonic-gate hp->str_data = sp->str_ptr;
2457c478bd9Sstevel@tonic-gate hp->str_buf = sp->str_nbufs - 1;
2467c478bd9Sstevel@tonic-gate hp->str_off = sp->str_size;
2477c478bd9Sstevel@tonic-gate hp->str_len = len;
2487c478bd9Sstevel@tonic-gate hp->str_next = sp->str_hash[h];
2497c478bd9Sstevel@tonic-gate
2507c478bd9Sstevel@tonic-gate /*
2517c478bd9Sstevel@tonic-gate * Now copy the string data into our buffer list, and then update
2527c478bd9Sstevel@tonic-gate * the global counts of strings and bytes. Return str's byte offset.
2537c478bd9Sstevel@tonic-gate */
2547c478bd9Sstevel@tonic-gate if (dt_strtab_copyin(sp, str, len + 1) == -1)
2557c478bd9Sstevel@tonic-gate return (-1L);
2567c478bd9Sstevel@tonic-gate
2577c478bd9Sstevel@tonic-gate sp->str_nstrs++;
2587c478bd9Sstevel@tonic-gate sp->str_size += len + 1;
2597c478bd9Sstevel@tonic-gate sp->str_hash[h] = hp;
2607c478bd9Sstevel@tonic-gate
2617c478bd9Sstevel@tonic-gate return (hp->str_off);
2627c478bd9Sstevel@tonic-gate }
2637c478bd9Sstevel@tonic-gate
2647c478bd9Sstevel@tonic-gate size_t
dt_strtab_size(const dt_strtab_t * sp)2657c478bd9Sstevel@tonic-gate dt_strtab_size(const dt_strtab_t *sp)
2667c478bd9Sstevel@tonic-gate {
2677c478bd9Sstevel@tonic-gate return (sp->str_size);
2687c478bd9Sstevel@tonic-gate }
2697c478bd9Sstevel@tonic-gate
2707c478bd9Sstevel@tonic-gate ssize_t
dt_strtab_write(const dt_strtab_t * sp,dt_strtab_write_f * func,void * private)2717c478bd9Sstevel@tonic-gate dt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private)
2727c478bd9Sstevel@tonic-gate {
2737c478bd9Sstevel@tonic-gate ssize_t res, total = 0;
2747c478bd9Sstevel@tonic-gate ulong_t i;
2757c478bd9Sstevel@tonic-gate size_t n;
2767c478bd9Sstevel@tonic-gate
2777c478bd9Sstevel@tonic-gate for (i = 0; i < sp->str_nbufs; i++, total += res) {
2787c478bd9Sstevel@tonic-gate if (i == sp->str_nbufs - 1)
2797c478bd9Sstevel@tonic-gate n = sp->str_ptr - sp->str_bufs[i];
2807c478bd9Sstevel@tonic-gate else
2817c478bd9Sstevel@tonic-gate n = sp->str_bufsz;
2827c478bd9Sstevel@tonic-gate
2837c478bd9Sstevel@tonic-gate if ((res = func(sp->str_bufs[i], n, total, private)) <= 0)
2847c478bd9Sstevel@tonic-gate break;
2857c478bd9Sstevel@tonic-gate }
2867c478bd9Sstevel@tonic-gate
2877c478bd9Sstevel@tonic-gate if (total == 0 && sp->str_size != 0)
2887c478bd9Sstevel@tonic-gate return (-1);
2897c478bd9Sstevel@tonic-gate
2907c478bd9Sstevel@tonic-gate return (total);
2917c478bd9Sstevel@tonic-gate }
292