usr/src/cmd/truss/htbl.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, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright 2002 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 <stdio.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <synch.h>
  33 #include <thread.h>
  34 #include <memory.h>
  35 #include <assert.h>
  36 #include <libproc.h>
  37 #include "ramdata.h"
  38 #include "proto.h"
  39 #include "htbl.h"
  40
  41
  42 htbl_t *
  43 init_hash(unsigned int size)
  44 {
  45         htbl_t *htp;
  46         hashb_t *temp;
  47         int i;
  48
  49         if ((size & (size - 1)) != 0)
  50                 abend("Size must be power of two", NULL);
  51
  52         htp = (htbl_t *)my_malloc(sizeof (htbl_t), NULL);
  53         htp->size = size;
  54         htp->tbl = (hashb_t *)
  55             my_calloc((size_t)size, sizeof (hashb_t), NULL);
  56
  57         /* Init mutexes */
  58         for (i = 0; i < size; i++) {
  59                 temp = &htp->tbl[i];
  60                 (void) mutex_init(&temp->block, USYNC_THREAD, NULL);
  61         }
  62
  63         return (htp);
  64 }
  65
  66 void
  67 destroy_hash(htbl_t *htp)
  68 {
  69         int i;
  70         hentry_t *tmp;
  71         hentry_t *prev;
  72         hashb_t *cur;
  73
  74         for (i = 0; i < htp->size; i++) {
  75                 cur = &htp->tbl[i];
  76                 (void) mutex_destroy(&cur->block);
  77                 tmp = cur->first;
  78
  79                 while (tmp != NULL) {
  80                         prev = tmp;
  81                         tmp = tmp->next;
  82
  83                         free(prev->key);
  84                         prev->key = NULL;
  85                         free(prev->lib);
  86                         prev->lib = NULL;
  87
  88                         free((char *)prev);
  89                         if (tmp != NULL)
  90                                 tmp->prev = NULL;
  91                 }
  92         }
  93         free((char *)htp->tbl);
  94         htp->tbl = NULL;
  95         free(htp);
  96 }
  97
  98 static unsigned int
  99 hash_str(char *str, unsigned int sz)
 100 {
 101         uint_t hash = 0;
 102         uint_t g;
 103         char *p;
 104
 105         assert(str != NULL);
 106         for (p = str; *p != '\0'; p++) {
 107                 hash = (hash << 4) + *p;
 108                 if ((g = (hash & 0xf0000000)) != 0) {
 109                         hash ^= (g >> 24);
 110                         hash ^= g;
 111                 }
 112         }
 113
 114         return (hash & (sz - 1));
 115 }
 116
 117
 118 void
 119 add_fcall(htbl_t *htp, char *lib, char *key, unsigned long cnt)
 120 {
 121         unsigned int bucket;
 122         hentry_t *tmp;
 123         hentry_t *new;
 124         hashb_t *cur;
 125
 126         bucket = hash_str(key, htp->size);
 127         cur = &htp->tbl[bucket];
 128
 129         (void) mutex_lock(&cur->block);
 130
 131         tmp = cur->first;
 132         while (tmp != NULL) {
 133                 if (strcmp(tmp->key, key) == 0) {
 134                         if (strcmp(tmp->lib, lib) == 0) {
 135                                 tmp->count += cnt;
 136                                 (void) mutex_unlock(&cur->block);
 137                                 return;
 138                         }
 139                 }
 140                 tmp = tmp->next;
 141         }
 142
 143         /*
 144          * If we're still here, there was no such fcall recorded
 145          * so we make a new entry and add it to the table
 146          */
 147
 148         new = (hentry_t *)my_malloc(sizeof (hentry_t), NULL);
 149         new->key = strdup(key);
 150         if (new->key == NULL)
 151                 abend("Out of memory in htbl.c", NULL);
 152         new->lib = strdup(lib);
 153         if (new->lib == NULL)
 154                 abend("Out of memory in htbl.c", NULL);
 155         new->count = cnt;
 156         new->prev = NULL;
 157         new->next = cur->first;
 158         tmp = new->next;
 159         if (tmp != NULL) {
 160                 tmp->prev = new;
 161         }
 162         cur->first = new;
 163
 164         (void) mutex_unlock(&cur->block);
 165 }
 166
 167 /*
 168  * iterate_hash locks the table and returns an enumeration struct
 169  * using this it is possible to iterate through the entries of a hash table
 170  * once finished, use iter_free to unlock the table and free the struct
 171  */
 172
 173 hiter_t *
 174 iterate_hash(htbl_t *tbl)
 175 {
 176         int b;
 177         int i;
 178         hiter_t *new;
 179         hashb_t *cur;
 180         hentry_t *tmp = NULL;
 181
 182         new = (hiter_t *)my_malloc(sizeof (hiter_t), NULL);
 183         new->table = tbl;
 184
 185         for (i = 0; i < tbl->size; i++) {
 186                 cur = &tbl->tbl[i];
 187                 (void) mutex_lock(&cur->block);
 188                 if (tmp == NULL) {
 189                         tmp = cur->first;
 190                         b = i;
 191                 }
 192         }
 193
 194         new->next = tmp;
 195         new->bucket = b;
 196
 197         return (new);
 198 }
 199
 200 void
 201 iter_free(hiter_t *itr)
 202 {
 203         int i;
 204         hashb_t *cur;
 205         htbl_t *tbl;
 206
 207         tbl = itr->table;
 208         for (i = 0; i < tbl->size; i++) {
 209                 cur = &tbl->tbl[i];
 210                 (void) mutex_unlock(&cur->block);
 211         }
 212
 213         free(itr);
 214 }
 215
 216 hentry_t *
 217 iter_next(hiter_t *itr)
 218 {
 219         int i;
 220         hentry_t *tmp;
 221         hentry_t *ret;
 222         hashb_t *cur = NULL;
 223         htbl_t *hash;
 224
 225         ret = itr->next;
 226
 227
 228         if (ret == NULL)
 229                 return (ret);
 230
 231         hash = itr->table;
 232         tmp = ret->next;
 233         i = itr->bucket;
 234
 235         if (tmp == NULL) {
 236                 for (i = i + 1; i < hash->size; i++) {
 237                         cur = &hash->tbl[i];
 238                         tmp = cur->first;
 239                         if (tmp != NULL)
 240                                 break;
 241                 }
 242         }
 243
 244         itr->next = tmp;
 245         itr->bucket = i;
 246
 247         return (ret);
 248 }
 249
 250 size_t
 251 elements_in_table(htbl_t *tbl)
 252 {
 253         size_t elem = 0;
 254         hiter_t *itr = iterate_hash(tbl);
 255         hentry_t *tmp = iter_next(itr);
 256         while (tmp != NULL) {
 257                 elem++;
 258                 tmp = iter_next(itr);
 259         }
 260         iter_free(itr);
 261         return (elem);
 262 }