xref: /illumos-gate/usr/src/cmd/truss/htbl.c (revision 7c478bd9)
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 *
init_hash(unsigned int size)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
destroy_hash(htbl_t * htp)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
hash_str(char * str,unsigned int sz)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
add_fcall(htbl_t * htp,char * lib,char * key,unsigned long cnt)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 *
iterate_hash(htbl_t * tbl)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
iter_free(hiter_t * itr)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 *
iter_next(hiter_t * itr)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
elements_in_table(htbl_t * tbl)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 }
263