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