[DTrace-devel] [PATCH v2 04/11] htab: have dt_htab_destroy del all the elements

[Eugene Loh]

On 10/27/21 9:40 AM, Nick Alcock wrote:

> On 21 Oct 2021, Eugene Loh outgrape:
>> On 10/20/21 2:53 PM, Nick Alcock wrote:
>>> diff --git a/libdtrace/dt_htab.c b/libdtrace/dt_htab.c
>>>    void dt_htab_destroy(dtrace_hdl_t *dtp, dt_htab_t *htab)
>>>    {
>>> +	size_t		i;
>>> +
>>>    	if (!htab)
>>>    		return;
>>>    
>>> +	for (i = 0; i < htab->size; i++) {
>>> +		dt_hbucket_t	*bucket = htab->tab[i];
>>> +
>>> +		while (bucket && bucket->head)
>>> +			bucket->head = htab->ops->del(bucket->head,
>>> +			    bucket->head);
>>> +		free(bucket);
>>> +	}
>>> +
>>>    	dt_free(dtp, htab->tab);
>>>    	dt_free(dtp, htab);
>>>    }
>> Inside the "for i" loop, bucket does not change.  So, maybe replace
>>           while (bucket && bucket->head)
>> with
>>           if (bucket == NULL) continue;
>>           while (bucket->head)
>>
>> More importantly, is the looping right?  You loop over slots.  For each
>> slot, you choose a bucket, deleting its entries and then freeing the
>> bucket.  But what if there are multiple buckets per slot?  Don't you
>> have to chase bucket->next before freeing bucket?
> ... that's obviously wrong, thank you! Fixed. I wish I knew some way to
> *test* this. Synthesising hash collisions is quite hard... maybe a full
> amke check run with leak detection going would spot it. Will try.
What kind of collisions?  Multiple buckets in one slot?  You can hack 
the resizing so that there are "not enough" slots.  (E.g., allow only 
one slot no matter how many buckets.)  Another stress is dumbing down 
the hash function.