usr/src/lib/libdtrace/common/dt_strtab.c

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