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