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