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