common/dtrace/dtrace.c

240 static dtrace_dynvar_t	dtrace_dynhash_sink;	/* end of dynamic hash chains */
374  * On DEBUG kernels, DTrace will track the errors that has seen in a hash
378  * error hash may be examined with the ::dtrace_errhash MDB dcmd.
395 #define	DTRACE_HASHSTR(hash, probe)	\
396 	dtrace_hash_str(*((char **)((uintptr_t)(probe) + (hash)->dth_stroffs)))
398 #define	DTRACE_HASHNEXT(hash, probe)	\
399 	(dtrace_probe_t **)((uintptr_t)(probe) + (hash)->dth_nextoffs)
401 #define	DTRACE_HASHPREV(hash, probe)	\
402 	(dtrace_probe_t **)((uintptr_t)(probe) + (hash)->dth_prevoffs)
404 #define	DTRACE_HASHEQ(hash, lhs, rhs)	\
405 	(strcmp(*((char **)((uintptr_t)(lhs) + (hash)->dth_stroffs)), \
406 	    *((char **)((uintptr_t)(rhs) + (hash)->dth_stroffs))) == 0)
752 		 *	(1) Start above the hash table that is at the base of
1653 			 * on a hash chain, either the dirty list or the
1678 		 * We are now guaranteed that no hash chain contains a pointer
1712 	dtrace_dynhash_t *hash = dstate->dtds_hash;
1730 	 * better than pathological hash distribution.  The efficacy of the
1781 	 * comes out to be one of our two sentinel hash values.  If this
1791 	 * critical that hash collisions be kept to an absolute minimum;
1799 		volatile uintptr_t *lockp = &hash[bucket].dtdh_lock;
1815 	lock = hash[bucket].dtdh_lock;
1819 	start = hash[bucket].dtdh_chain;
1832 				 * end of the hash chain; we can kick out of
1844 				 * the line, one of the members of this hash
1852 				 * possible by detecting the hash marker.  In
1890 			ASSERT(hash[bucket].dtdh_chain != dvar);
1895 			if (dtrace_casptr(&hash[bucket].dtdh_chain,
1899 				 * hash table head pointer, presumably because
1901 				 * We need to reread the hash chain and try
1911 		 * Now set the hash value to indicate that it's free.
1913 		ASSERT(hash[bucket].dtdh_chain != dvar);
1928 		 * Finally, unlock this hash bucket.
1930 		ASSERT(hash[bucket].dtdh_lock == lock);
1932 		hash[bucket].dtdh_lock++;
1943 		 * one of the elements that we traversed in the hash chain
1946 		 * the hash bucket to prevent themselves from racing with
1947 		 * one another), and retry the hash chain traversal.
1961 			if (hash[bucket].dtdh_lock != lock)
1965 			ASSERT(hash[bucket].dtdh_lock == lock);
1967 			hash[bucket].dtdh_lock++;
2141 	if (dtrace_casptr(&hash[bucket].dtdh_chain, start, dvar) == start)
2146 	 * this hash chain, or another CPU is deleting an element from this
2147 	 * hash chain.  The simplest way to deal with both of these cases
2434 		 * perchance, a prime) hash size for better hash distribution.
2452 	 * Calculate the hash value based on the key.  Note that we _don't_
2483 	 * over to compute hash values, compare data, etc.
2538 	 * link it into the hash table appropriately, and apply the aggregator
7804 	dtrace_hash_t *hash = kmem_zalloc(sizeof (dtrace_hash_t), KM_SLEEP);
7806 	hash->dth_stroffs = stroffs;
7807 	hash->dth_nextoffs = nextoffs;
7808 	hash->dth_prevoffs = prevoffs;
7810 	hash->dth_size = 1;
7811 	hash->dth_mask = hash->dth_size - 1;
7813 	hash->dth_tab = kmem_zalloc(hash->dth_size *
7816 	return (hash);
7820 dtrace_hash_destroy(dtrace_hash_t *hash)
7825 	for (i = 0; i < hash->dth_size; i++)
7826 		ASSERT(hash->dth_tab[i] == NULL);
7829 	kmem_free(hash->dth_tab,
7830 	    hash->dth_size * sizeof (dtrace_hashbucket_t *));
7831 	kmem_free(hash, sizeof (dtrace_hash_t));
7835 dtrace_hash_resize(dtrace_hash_t *hash)
7837 	int size = hash->dth_size, i, ndx;
7838 	int new_size = hash->dth_size << 1;
7847 		for (bucket = hash->dth_tab[i]; bucket != NULL; bucket = next) {
7851 			ndx = DTRACE_HASHSTR(hash, probe) & new_mask;
7859 	kmem_free(hash->dth_tab, hash->dth_size * sizeof (void *));
7860 	hash->dth_tab = new_tab;
7861 	hash->dth_size = new_size;
7862 	hash->dth_mask = new_mask;
7866 dtrace_hash_add(dtrace_hash_t *hash, dtrace_probe_t *new)
7868 	int hashval = DTRACE_HASHSTR(hash, new);
7869 	int ndx = hashval & hash->dth_mask;
7870 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
7874 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, new))
7878 	if ((hash->dth_nbuckets >> 1) > hash->dth_size) {
7879 		dtrace_hash_resize(hash);
7880 		dtrace_hash_add(hash, new);
7885 	bucket->dthb_next = hash->dth_tab[ndx];
7886 	hash->dth_tab[ndx] = bucket;
7887 	hash->dth_nbuckets++;
7890 	nextp = DTRACE_HASHNEXT(hash, new);
7891 	ASSERT(*nextp == NULL && *(DTRACE_HASHPREV(hash, new)) == NULL);
7895 		prevp = DTRACE_HASHPREV(hash, bucket->dthb_chain);
7905 dtrace_hash_lookup(dtrace_hash_t *hash, dtrace_probe_t *template)
7907 	int hashval = DTRACE_HASHSTR(hash, template);
7908 	int ndx = hashval & hash->dth_mask;
7909 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
7912 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, template))
7920 dtrace_hash_collisions(dtrace_hash_t *hash, dtrace_probe_t *template)
7922 	int hashval = DTRACE_HASHSTR(hash, template);
7923 	int ndx = hashval & hash->dth_mask;
7924 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
7927 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, template))
7935 dtrace_hash_remove(dtrace_hash_t *hash, dtrace_probe_t *probe)
7937 	int ndx = DTRACE_HASHSTR(hash, probe) & hash->dth_mask;
7938 	dtrace_hashbucket_t *bucket = hash->dth_tab[ndx];
7940 	dtrace_probe_t **prevp = DTRACE_HASHPREV(hash, probe);
7941 	dtrace_probe_t **nextp = DTRACE_HASHNEXT(hash, probe);
7947 		if (DTRACE_HASHEQ(hash, bucket->dthb_chain, probe))
7959 			dtrace_hashbucket_t *b = hash->dth_tab[ndx];
7965 				hash->dth_tab[ndx] = bucket->dthb_next;
7972 			ASSERT(hash->dth_nbuckets > 0);
7973 			hash->dth_nbuckets--;
7980 		*(DTRACE_HASHNEXT(hash, *prevp)) = *nextp;
7984 		*(DTRACE_HASHPREV(hash, *nextp)) = *prevp;
8099 	panic("dtrace: undersized error hash");
8330 	dtrace_hash_t *hash = NULL;
8356 	 * empty string, we perform a lookup in the corresponding hash and
8357 	 * use the hash table with the fewest collisions to do our search.
8362 		hash = dtrace_bymod;
8368 		hash = dtrace_byfunc;
8374 		hash = dtrace_byname;
8378 	 * If we did not select a hash table, iterate over every probe and
8381 	if (hash == NULL) {
8398 	 * If we selected a hash table, iterate over each probe of the same key
8402 	for (probe = dtrace_hash_lookup(hash, &template); probe != NULL;
8403 	    probe = *(DTRACE_HASHNEXT(hash, probe))) {
8721 	 * remove all of them from their hash chains and from the probe array.
8746 	 * The provider's probes have been removed from the hash chains and
13960 	 * Set all of our hash buckets to point to the single sink, and (if
13961 	 * it hasn't already been set), set the sink's hash value to be the
13963 	 * lookups to know that they have iterated over an entire, valid hash
16385 	 * We've removed all of the module's probes from the hash chains and