1178479Sjb/* 2178479Sjb * CDDL HEADER START 3178479Sjb * 4178479Sjb * The contents of this file are subject to the terms of the 5178479Sjb * Common Development and Distribution License (the "License"). 6178479Sjb * You may not use this file except in compliance with the License. 7178479Sjb * 8178479Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9178479Sjb * or http://www.opensolaris.org/os/licensing. 10178479Sjb * See the License for the specific language governing permissions 11178479Sjb * and limitations under the License. 12178479Sjb * 13178479Sjb * When distributing Covered Code, include this CDDL HEADER in each 14178479Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15178479Sjb * If applicable, add the following below this CDDL HEADER, with the 16178479Sjb * fields enclosed by brackets "[]" replaced with your own identifying 17178479Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 18178479Sjb * 19178479Sjb * CDDL HEADER END 20178479Sjb */ 21178479Sjb 22178479Sjb/* 23178479Sjb * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 24178479Sjb * Use is subject to license terms. 25178479Sjb */ 26178479Sjb 27296816Spfg/* 28296816Spfg * Portions Copyright 2016 Pedro Giffuni. All rights reserved. 29296816Spfg */ 30296816Spfg 31178479Sjb#pragma ident "%Z%%M% %I% %E% SMI" 32178479Sjb 33178479Sjb#include <sys/types.h> 34178479Sjb#include <sys/sysmacros.h> 35178479Sjb#include <strings.h> 36178479Sjb#include <stdlib.h> 37178479Sjb#include <assert.h> 38178479Sjb 39178479Sjb#include <dt_strtab.h> 40178479Sjb#include <dt_impl.h> 41178479Sjb 42178479Sjbstatic int 43178479Sjbdt_strtab_grow(dt_strtab_t *sp) 44178479Sjb{ 45178479Sjb char *ptr, **bufs; 46178479Sjb 47178479Sjb if ((ptr = malloc(sp->str_bufsz)) == NULL) 48178479Sjb return (-1); 49178479Sjb 50178479Sjb bufs = realloc(sp->str_bufs, (sp->str_nbufs + 1) * sizeof (char *)); 51178479Sjb 52178479Sjb if (bufs == NULL) { 53178479Sjb free(ptr); 54178479Sjb return (-1); 55178479Sjb } 56178479Sjb 57178479Sjb sp->str_nbufs++; 58178479Sjb sp->str_bufs = bufs; 59178479Sjb sp->str_ptr = ptr; 60178479Sjb sp->str_bufs[sp->str_nbufs - 1] = sp->str_ptr; 61178479Sjb 62178479Sjb return (0); 63178479Sjb} 64178479Sjb 65178479Sjbdt_strtab_t * 66178479Sjbdt_strtab_create(size_t bufsz) 67178479Sjb{ 68178479Sjb dt_strtab_t *sp = malloc(sizeof (dt_strtab_t)); 69178479Sjb uint_t nbuckets = _dtrace_strbuckets; 70178479Sjb 71178479Sjb assert(bufsz != 0); 72178479Sjb 73178479Sjb if (sp == NULL) 74178479Sjb return (NULL); 75178479Sjb 76178479Sjb bzero(sp, sizeof (dt_strtab_t)); 77296816Spfg sp->str_hash = calloc(nbuckets, sizeof (dt_strhash_t *)); 78178479Sjb 79178479Sjb if (sp->str_hash == NULL) 80178479Sjb goto err; 81178479Sjb 82178479Sjb sp->str_hashsz = nbuckets; 83178479Sjb sp->str_bufs = NULL; 84178479Sjb sp->str_ptr = NULL; 85178479Sjb sp->str_nbufs = 0; 86178479Sjb sp->str_bufsz = bufsz; 87178479Sjb sp->str_nstrs = 1; 88178479Sjb sp->str_size = 1; 89178479Sjb 90178479Sjb if (dt_strtab_grow(sp) == -1) 91178479Sjb goto err; 92178479Sjb 93178479Sjb *sp->str_ptr++ = '\0'; 94178479Sjb return (sp); 95178479Sjb 96178479Sjberr: 97178479Sjb dt_strtab_destroy(sp); 98178479Sjb return (NULL); 99178479Sjb} 100178479Sjb 101178479Sjbvoid 102178479Sjbdt_strtab_destroy(dt_strtab_t *sp) 103178479Sjb{ 104178479Sjb dt_strhash_t *hp, *hq; 105178479Sjb ulong_t i; 106178479Sjb 107178479Sjb for (i = 0; i < sp->str_hashsz; i++) { 108178479Sjb for (hp = sp->str_hash[i]; hp != NULL; hp = hq) { 109178479Sjb hq = hp->str_next; 110178479Sjb free(hp); 111178479Sjb } 112178479Sjb } 113178479Sjb 114178479Sjb for (i = 0; i < sp->str_nbufs; i++) 115178479Sjb free(sp->str_bufs[i]); 116178479Sjb 117178479Sjb if (sp->str_hash != NULL) 118178479Sjb free(sp->str_hash); 119178479Sjb if (sp->str_bufs != NULL) 120178479Sjb free(sp->str_bufs); 121178479Sjb 122178479Sjb free(sp); 123178479Sjb} 124178479Sjb 125178479Sjbulong_t 126178479Sjbdt_strtab_hash(const char *key, size_t *len) 127178479Sjb{ 128178479Sjb ulong_t g, h = 0; 129178479Sjb const char *p; 130178479Sjb size_t n = 0; 131178479Sjb 132178479Sjb for (p = key; *p != '\0'; p++, n++) { 133178479Sjb h = (h << 4) + *p; 134178479Sjb 135178479Sjb if ((g = (h & 0xf0000000)) != 0) { 136178479Sjb h ^= (g >> 24); 137178479Sjb h ^= g; 138178479Sjb } 139178479Sjb } 140178479Sjb 141178479Sjb if (len != NULL) 142178479Sjb *len = n; 143178479Sjb 144178479Sjb return (h); 145178479Sjb} 146178479Sjb 147178479Sjbstatic int 148178479Sjbdt_strtab_compare(dt_strtab_t *sp, dt_strhash_t *hp, 149178479Sjb const char *str, size_t len) 150178479Sjb{ 151178479Sjb ulong_t b = hp->str_buf; 152178479Sjb const char *buf = hp->str_data; 153178479Sjb size_t resid, n; 154178479Sjb int rv; 155178479Sjb 156178479Sjb while (len != 0) { 157178479Sjb if (buf == sp->str_bufs[b] + sp->str_bufsz) 158178479Sjb buf = sp->str_bufs[++b]; 159178479Sjb 160178479Sjb resid = sp->str_bufs[b] + sp->str_bufsz - buf; 161178479Sjb n = MIN(resid, len); 162178479Sjb 163178479Sjb if ((rv = strncmp(buf, str, n)) != 0) 164178479Sjb return (rv); 165178479Sjb 166178479Sjb buf += n; 167178479Sjb str += n; 168178479Sjb len -= n; 169178479Sjb } 170178479Sjb 171178479Sjb return (0); 172178479Sjb} 173178479Sjb 174178479Sjbstatic int 175178479Sjbdt_strtab_copyin(dt_strtab_t *sp, const char *str, size_t len) 176178479Sjb{ 177178479Sjb char *old_p = sp->str_ptr; 178178479Sjb ulong_t old_n = sp->str_nbufs; 179178479Sjb 180178479Sjb ulong_t b = sp->str_nbufs - 1; 181178479Sjb size_t resid, n; 182178479Sjb 183178479Sjb while (len != 0) { 184178479Sjb if (sp->str_ptr == sp->str_bufs[b] + sp->str_bufsz) { 185178479Sjb if (dt_strtab_grow(sp) == -1) 186178479Sjb goto err; 187178479Sjb b++; 188178479Sjb } 189178479Sjb 190178479Sjb resid = sp->str_bufs[b] + sp->str_bufsz - sp->str_ptr; 191178479Sjb n = MIN(resid, len); 192178479Sjb bcopy(str, sp->str_ptr, n); 193178479Sjb 194178479Sjb sp->str_ptr += n; 195178479Sjb str += n; 196178479Sjb len -= n; 197178479Sjb } 198178479Sjb 199178479Sjb return (0); 200178479Sjb 201178479Sjberr: 202178479Sjb while (sp->str_nbufs != old_n) 203178479Sjb free(sp->str_bufs[--sp->str_nbufs]); 204178479Sjb 205178479Sjb sp->str_ptr = old_p; 206178479Sjb return (-1); 207178479Sjb} 208178479Sjb 209178479Sjbssize_t 210178479Sjbdt_strtab_index(dt_strtab_t *sp, const char *str) 211178479Sjb{ 212178479Sjb dt_strhash_t *hp; 213178479Sjb size_t len; 214178479Sjb ulong_t h; 215178479Sjb 216178479Sjb if (str == NULL || str[0] == '\0') 217178479Sjb return (0); /* we keep a \0 at offset 0 to simplify things */ 218178479Sjb 219178479Sjb h = dt_strtab_hash(str, &len) % sp->str_hashsz; 220178479Sjb 221178479Sjb for (hp = sp->str_hash[h]; hp != NULL; hp = hp->str_next) { 222178479Sjb if (dt_strtab_compare(sp, hp, str, len + 1) == 0) 223178479Sjb return (hp->str_off); 224178479Sjb } 225178479Sjb 226178479Sjb return (-1); 227178479Sjb} 228178479Sjb 229178479Sjbssize_t 230178479Sjbdt_strtab_insert(dt_strtab_t *sp, const char *str) 231178479Sjb{ 232178479Sjb dt_strhash_t *hp; 233178479Sjb size_t len; 234178479Sjb ssize_t off; 235178479Sjb ulong_t h; 236178479Sjb 237178479Sjb if ((off = dt_strtab_index(sp, str)) != -1) 238178479Sjb return (off); 239178479Sjb 240178479Sjb h = dt_strtab_hash(str, &len) % sp->str_hashsz; 241178479Sjb 242178479Sjb /* 243178479Sjb * Create a new hash bucket, initialize it, and insert it at the front 244178479Sjb * of the hash chain for the appropriate bucket. 245178479Sjb */ 246178479Sjb if ((hp = malloc(sizeof (dt_strhash_t))) == NULL) 247178479Sjb return (-1L); 248178479Sjb 249178479Sjb hp->str_data = sp->str_ptr; 250178479Sjb hp->str_buf = sp->str_nbufs - 1; 251178479Sjb hp->str_off = sp->str_size; 252178479Sjb hp->str_len = len; 253178479Sjb hp->str_next = sp->str_hash[h]; 254178479Sjb 255178479Sjb /* 256178479Sjb * Now copy the string data into our buffer list, and then update 257178479Sjb * the global counts of strings and bytes. Return str's byte offset. 258178479Sjb */ 259315014Smarkj if (dt_strtab_copyin(sp, str, len + 1) == -1) { 260315014Smarkj free(hp); 261178479Sjb return (-1L); 262315014Smarkj } 263178479Sjb 264178479Sjb sp->str_nstrs++; 265178479Sjb sp->str_size += len + 1; 266178479Sjb sp->str_hash[h] = hp; 267178479Sjb 268178479Sjb return (hp->str_off); 269178479Sjb} 270178479Sjb 271178479Sjbsize_t 272178479Sjbdt_strtab_size(const dt_strtab_t *sp) 273178479Sjb{ 274178479Sjb return (sp->str_size); 275178479Sjb} 276178479Sjb 277178479Sjbssize_t 278178479Sjbdt_strtab_write(const dt_strtab_t *sp, dt_strtab_write_f *func, void *private) 279178479Sjb{ 280178479Sjb ssize_t res, total = 0; 281178479Sjb ulong_t i; 282178479Sjb size_t n; 283178479Sjb 284178479Sjb for (i = 0; i < sp->str_nbufs; i++, total += res) { 285178479Sjb if (i == sp->str_nbufs - 1) 286178479Sjb n = sp->str_ptr - sp->str_bufs[i]; 287178479Sjb else 288178479Sjb n = sp->str_bufsz; 289178479Sjb 290178479Sjb if ((res = func(sp->str_bufs[i], n, total, private)) <= 0) 291178479Sjb break; 292178479Sjb } 293178479Sjb 294178479Sjb if (total == 0 && sp->str_size != 0) 295178479Sjb return (-1); 296178479Sjb 297178479Sjb return (total); 298178479Sjb} 299