common/dtrace/dtrace.c

187 static dtrace_dynvar_t	dtrace_dynhash_sink;	/* end of dynamic hash chains */
282  * On DEBUG kernels, DTrace will track the errors that has seen in a hash
286  * error hash may be examined with the ::dtrace_errhash MDB dcmd.
303 #define	DTRACE_HASHSTR(hash, probe)	\
304 	dtrace_hash_str(*((char **)((uintptr_t)(probe) + (hash)->dth_stroffs)))
306 #define	DTRACE_HASHNEXT(hash, probe)	\
307 	(dtrace_probe_t **)((uintptr_t)(probe) + (hash)->dth_nextoffs)
309 #define	DTRACE_HASHPREV(hash, probe)	\
310 	(dtrace_probe_t **)((uintptr_t)(probe) + (hash)->dth_prevoffs)
312 #define	DTRACE_HASHEQ(hash, lhs, rhs)	\
313 	(strcmp(*((char **)((uintptr_t)(lhs) + (hash)->dth_stroffs)), \
314 	    *((char **)((uintptr_t)(rhs) + (hash)->dth_stroffs))) == 0)
631 		 *	(1) Start above the hash table that is at the base of
1273 			 * on a hash chain, either the dirty list or the
1298 		 * We are now guaranteed that no hash chain contains a pointer
1332 	dtrace_dynhash_t *hash = dstate->dtds_hash;
1350 	 * better than pathological hash distribution.  The efficacy of the
1401 	 * comes out to be one of our two sentinel hash values.  If this
1411 	 * critical that hash collisions be kept to an absolute minimum;
1419 		volatile uintptr_t *lockp = &hash[bucket].dtdh_lock;
1435 	lock = hash[bucket].dtdh_lock;
1439 	start = hash[bucket].dtdh_chain;
1452 				 * end of the hash chain; we can kick out of
1464 				 * the line, one of the members of this hash
1472 				 * possible by detecting the hash marker.  In
1510 			ASSERT(hash[bucket].dtdh_chain != dvar);
1515 			if (dtrace_casptr(&hash[bucket].dtdh_chain,
1519 				 * hash table head pointer, presumably because
1521 				 * We need to reread the hash chain and try
1531 		 * Now set the hash value to indicate that it's free.
1533 		ASSERT(hash[bucket].dtdh_chain != dvar);
1548 		 * Finally, unlock this hash bucket.
1550 		ASSERT(hash[bucket].dtdh_lock == lock);
1552 		hash[bucket].dtdh_lock++;
1563 		 * one of the elements that we traversed in the hash chain
1566 		 * the hash bucket to prevent themselves from racing with
1567 		 * one another), and retry the hash chain traversal.
1581 			if (hash[bucket].dtdh_lock != lock)
1585 			ASSERT(hash[bucket].dtdh_lock == lock);
1587 			hash[bucket].dtdh_lock++;
1761 	if (dtrace_casptr(&hash[bucket].dtdh_chain, start, dvar) == start)
1766 	 * this hash chain, or another CPU is deleting an element from this
1767 	 * hash chain.  The simplest way to deal with both of these cases
1985 		 * perchance, a prime) hash size for better hash distribution.
2003 	 * Calculate the hash value based on the key.  Note that we _don't_
2034 	 * over to compute hash values, compare data, etc.
2089 	 * link it into the hash table appropriately, and apply the aggregator
6190 	dtrace_hash_t *hash = kmem_zalloc(sizeof (dtrace_hash_t), KM_SLEEP);
6192 	hash->dth_stroffs = stroffs;
6193 	hash->dth_nextoffs = nextoffs;
6194 	hash->dth_prevoffs = prevoffs;
6196 	hash->dth_size = 1;
6197 	hash->dth_mask = hash->dth_size - 1;
6199 	hash->dth_tab = kmem_zalloc(hash->dth_size *
6202 	return (hash);
6206 dtrace_hash_destroy(dtrace_hash_t *hash)
6211 	for (i = 0; i < hash->dth_size; i++)
6212 		ASSERT(hash->dth_tab[i] == NULL);
6215 	kmem_free(hash->dth_tab,
6216 	    hash->dth_size * sizeof (dtrace_hashbucket_t *));
6217 	kmem_free(hash, sizeof (dtrace_hash_t));
6221 dtrace_hash_resize(dtrace_hash_t *hash)
6223 	int size = hash->dth_size, i, ndx;
6224 	int new_size = hash->dth_size << 1;
6233 		for (bucket = hash->dth_tab[i]; bucket != NULL; bucket = next) {
6237 			ndx = DTRACE_HASHSTR(hash, probe) & new_mask;
6245 	kmem_free(hash->dth_tab, hash->dth_size * sizeof (void *));
6246 	hash->dth_tab = new_tab;
6247 	hash->dth_size = new_size;
6248 	hash->dth_mask = new_mask;
6252 dtrace_hash_add(dtrace_hash_t *hash, dtrace_probe_t *new)
6254 	int hashval = DTRACE_HASHSTR(hash, new);
6255 	int ndx = hashval & hash->dth_mask;
6256 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
6260 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, new))
6264 	if ((hash->dth_nbuckets >> 1) > hash->dth_size) {
6265 		dtrace_hash_resize(hash);
6266 		dtrace_hash_add(hash, new);
6271 	bucket->dthb_next = hash->dth_tab[ndx];
6272 	hash->dth_tab[ndx] = bucket;
6273 	hash->dth_nbuckets++;
6276 	nextp = DTRACE_HASHNEXT(hash, new);
6277 	ASSERT(*nextp == NULL && *(DTRACE_HASHPREV(hash, new)) == NULL);
6281 		prevp = DTRACE_HASHPREV(hash, bucket->dthb_chain);
6291 dtrace_hash_lookup(dtrace_hash_t *hash, dtrace_probe_t *template)
6293 	int hashval = DTRACE_HASHSTR(hash, template);
6294 	int ndx = hashval & hash->dth_mask;
6295 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
6298 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, template))
6306 dtrace_hash_collisions(dtrace_hash_t *hash, dtrace_probe_t *template)
6308 	int hashval = DTRACE_HASHSTR(hash, template);
6309 	int ndx = hashval & hash->dth_mask;
6310 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
6313 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, template))
6321 dtrace_hash_remove(dtrace_hash_t *hash, dtrace_probe_t *probe)
6323 	int ndx = DTRACE_HASHSTR(hash, probe) & hash->dth_mask;
6324 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
6326 	dtrace_probe_t **prevp = DTRACE_HASHPREV(hash, probe);
6327 	dtrace_probe_t **nextp = DTRACE_HASHNEXT(hash, probe);
6333 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, probe))
6345 			dtrace_hashbucket_t *b = hash->dth_tab[ndx];
6351 				hash->dth_tab[ndx] = bucket->dthb_next;
6358 			ASSERT(hash->dth_nbuckets > 0);
6359 			hash->dth_nbuckets--;
6366 		*(DTRACE_HASHNEXT(hash, *prevp)) = *nextp;
6370 		*(DTRACE_HASHPREV(hash, *nextp)) = *prevp;
6481 	panic("dtrace: undersized error hash");
6712 	dtrace_hash_t *hash = NULL;
6739 	 * empty string, we perform a lookup in the corresponding hash and
6740 	 * use the hash table with the fewest collisions to do our search.
6745 		hash = dtrace_bymod;
6751 		hash = dtrace_byfunc;
6757 		hash = dtrace_byname;
6761 	 * If we did not select a hash table, iterate over every probe and
6764 	if (hash == NULL) {
6785 	 * If we selected a hash table, iterate over each probe of the same key
6789 	for (probe = dtrace_hash_lookup(hash, &template); probe != NULL;
6790 	    probe = *(DTRACE_HASHNEXT(hash, probe))) {
7086 	 * remove all of them from their hash chains and from the probe array.
7111 	 * The provider's probes have been removed from the hash chains and
11972 	 * Set all of our hash buckets to point to the single sink, and (if
11973 	 * it hasn't already been set), set the sink's hash value to be the
11975 	 * lookups to know that they have iterated over an entire, valid hash
14173 	 * We've removed all of the module's probes from the hash chains and