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

[Nick Alcock]

On 21 Oct 2021, Eugene Loh outgrape:

> I'm struggling with this one.

So was I, and even Kris misread his own code: hence the extra comments
to try to clarify things a bit.

> On 10/20/21 2:53 PM, Nick Alcock wrote:
>> This means that a dt_htab_destroy of a non-empy htab doesn't leak memory
>> and leave all its former elements full of wild pointers.
>
> s/empy/empty/

Whoops, fixed.

> Were we leaking memory?  If so, what does this patch do to fix that?  I 

We weren't, but only because every single existing user of htabs goes to
some lengths to manually dt_htab_delete every single element before
destroying the htab.  I don't like having to do that and it means that
(in the absence of a hash iterator) you have to track the members
elsewhere, hence all those otherwise-pointless lists.

> can see that the former elements will have their next/prev pointers set 
> to NULL, dealing with those "wild pointers," but the patch does not free 
> any memory.  Or, what am I missing?

This:

>> +		while (bucket && bucket->head)
>> +			bucket->head = htab->ops->del(bucket->head,
>> +			    bucket->head);
>>> >> +	free(bucket);  <<<
>> +	}

So any buckets still in existence get freed at this stage rather than
being leaked.

Also, calling ->del only sets pointers to NULL and does nothing else *by
default*. Users can override it to do other things too (though, at this
point in the series, nobody did, because ->del was not reliably called).

>> Also add some comments to dt_htab_delete given how many mistakes I made
>> reading it.
>
> Thanks for adding the comments, but I don't think that merits mention in 
> the commit message.  Personal choice, I suppose.

I only note it because I went back and forth on what the comments should
say so many times: I spent longer agonizing over what I thought were
bugs in dt_htab_destroy (none of which were) than I did over the whole
rest of the change :)

>> 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.

The loop now reads

	for (i = 0; i < htab->size; i++) {
		dt_hbucket_t	*bucket = htab->tab[i];

		while (bucket) {
			dt_hbucket_t *obucket = bucket;

			while (bucket->head)
				bucket->head = htab->ops->del(bucket->head,
				    bucket->head);
			bucket = bucket->next;
			free(obucket);
		};
	}

i.e. we loop over all the entries in a given bucket, within a loop over
all the buckets in a given tab slot.

>> @@ -201,9 +216,16 @@ int dt_htab_delete(dt_htab_t *htab, void *entry)
>>   	if (bucket == NULL)
>>   		return -ENOENT;
>>   
>> +	/*
>> +	 * Destroy the specified entry, now known to be in this bucket.
>> +	 */
>>   	head = htab->ops->del(bucket->head, entry);
>>   	bucket->nentries--;
>>   	htab->nentries--;
> s/Destroy/Delete/ maybe?  To align better with the function name del()?

Yeah, I had "destroy" on the brain.

-- 
NULL && (void)