Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsetswithin an entry

From: Neil Horman
Date: Wed Jul 20 2011 - 07:12:13 EST


On Wed, Jul 20, 2011 at 12:38:13PM +0200, Roedel, Joerg wrote:
> Hi Neil,
>
> thanks for your work on this :)
>
> On Tue, Jul 19, 2011 at 01:41:18PM -0400, Neil Horman wrote:
> > lib/dma-debug.c | 17 +++++++++++++++--
> > 1 files changed, 15 insertions(+), 2 deletions(-)
> >
> > diff --git a/lib/dma-debug.c b/lib/dma-debug.c
> > index db07bfd..333f0ee 100644
> > --- a/lib/dma-debug.c
> > +++ b/lib/dma-debug.c
> > @@ -248,10 +248,23 @@ static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
> > {
> > struct dma_debug_entry *entry, *ret = NULL;
> > int matches = 0, match_lvl, last_lvl = 0;
> > + u64 estart, eend, rstart, rend;
> > +
> > + rstart = ref->dev_addr;
> > + rend = rstart + ref->size;
> >
> > list_for_each_entry(entry, &bucket->list, list) {
> > - if ((entry->dev_addr != ref->dev_addr) ||
> > - (entry->dev != ref->dev))
> > + estart = entry->dev_addr;
> > + eend = estart + entry->size;
> > +
> > + /*
> > + * An entry matches if the address range specified by the ref
> > + * dev_addr and size falls entirely within the range specified
> > + * by the entries dev_addr and size and the devices match
> > + */
> > + if (entry->dev != ref->dev)
> > + continue;
> > + if ((estart > rstart) || (eend < rend))
> > continue;
> >
> > /*
>
> But it is not that easy. The hash_fn works on the dev_addr, this means
> to search all entries which might match you need to scan multiple
> hash-buckets potentially.
> In fact, you need to scan
>
> hash_fn(estart) <= idx <= hash_fn(eend)
>
Ah, good point. Its actually a bit more difficult that what you describe I
think. Given a ref->dev_addr, this check needs to find the entry in any bucket
for a matching device that has an entry->dev_addr less than ref->dev_addr, where
the former has a larger size than the latter. And since we don't know the true
size of the entry we are looking for, we could have crossed the HASH_FN_SHIFT
many times over to get to the ref->dev addr that was passed in. It almost
sounds like the hash table for this needs to be accessible by device rather than
by address.

> to be sure. The patch above also lifts up the check_unmap which is not
> desired.
Hm, you're right, I suppose we need to add an exact map option to the passed in
ref structure or some such, I'll rework this

Thanks
Neil

>
> Thanks,
>
> Joerg
>
> --
> AMD Operating System Research Center
>
> Advanced Micro Devices GmbH Einsteinring 24 85609 Dornach
> General Managers: Alberto Bozzo, Andrew Bowd
> Registration: Dornach, Landkr. Muenchen; Registerger. Muenchen, HRB Nr. 43632
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/