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