[PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry

[PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry

[Neil Horman]

Users of the pci_dma_sync_single_* api allow users to sync address ranges within
the range of a mapped entry (i.e. you can dma map address X to dma_addr_t A and
then pci_dma_sync_single on dma_addr_t A+1.  The dma-debug library however
assume dma syncs will always occur using the base address of a mapped region,
and uses that assumption to find entries in its hash table.  Since thats often
(but not always the case), the dma debug library can give us false errors about
missing entries, which are reported as syncing of memory not allocated by the
driver.  This was noted in the cxgb3 driver as this error:

WARNING: at lib/dma-debug.c:902 check_sync+0xdd/0x48c()
Hardware name: To be filled by O.E.M.
cxgb3 0000:01:00.0: DMA-API: device driver tries to sync DMA memory it has not
allocated [device address=0x00000000fff97800] [size=1984 bytes]
Modules linked in: autofs4 sunrpc cpufreq_ondemand acpi_cpufreq freq_table
mperf ip6t_REJECT nf_conntrack_ipv6 ip6table_filter ip6_tables ipv6 uinput
snd_hda_codec_intelhdmi snd_hda_codec_realtek snd_hda_intel snd_hda_codec
snd_hwdep snd_seq snd_seq_device snd_pcm snd_timer e1000e snd soundcore r8169
cxgb3 iTCO_wdt snd_page_alloc mii shpchp i2c_i801 iTCO_vendor_support mdio
microcode firewire_ohci firewire_core crc_itu_t ata_generic pata_acpi i915
drm_kms_helper drm i2c_algo_bit i2c_core video output [last unloaded:
scsi_wait_scan]
Pid: 1818, comm: ifconfig Not tainted 2.6.35-0.23.rc3.git6.fc14.x86_64 #1
Call Trace:
[<ffffffff81050f71>] warn_slowpath_common+0x85/0x9d
[<ffffffff8105102c>] warn_slowpath_fmt+0x46/0x48
[<ffffffff8124658e>] ? check_sync+0x39/0x48c
[<ffffffff8107c470>] ? trace_hardirqs_on+0xd/0xf
[<ffffffff81246632>] check_sync+0xdd/0x48c
[<ffffffff81246ca6>] debug_dma_sync_single_for_device+0x3f/0x41
[<ffffffffa011615c>] ? pci_map_page+0x84/0x97 [cxgb3]
[<ffffffffa0117bc3>] pci_dma_sync_single_for_device.clone.0+0x65/0x6e [cxgb3]
[<ffffffffa0117ed1>] refill_fl+0x305/0x30a [cxgb3]
[<ffffffffa011857d>] t3_sge_alloc_qset+0x6a7/0x821 [cxgb3]
[<ffffffffa010a07b>] cxgb_up+0x4d0/0xe62 [cxgb3]
[<ffffffff81086037>] ? __module_text_address+0x12/0x58
[<ffffffffa010aa4c>] cxgb_open+0x3f/0x309 [cxgb3]
[<ffffffff813e9f6c>] __dev_open+0x8e/0xbc
[<ffffffff813e7ca5>] __dev_change_flags+0xbe/0x142
[<ffffffff813e9ea8>] dev_change_flags+0x21/0x57
[<ffffffff81445937>] devinet_ioctl+0x29a/0x54b
[<ffffffff811f9a87>] ? inode_has_perm+0xaa/0xce
[<ffffffff81446ed2>] inet_ioctl+0x8f/0xa7
[<ffffffff813d683a>] sock_do_ioctl+0x29/0x48
[<ffffffff813d6c83>] sock_ioctl+0x213/0x222
[<ffffffff81137f78>] vfs_ioctl+0x32/0xa6
[<ffffffff811384e2>] do_vfs_ioctl+0x47a/0x4b3
[<ffffffff81138571>] sys_ioctl+0x56/0x79
[<ffffffff81009c32>] system_call_fastpath+0x16/0x1b
---[ end trace 69a4d4cc77b58004 ]---

This patch corrects the issue by changing the hash_bucket_find function so that
it matches on entries where the referenced address  and size fall within the
range of a given entry without overlapping.

Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
Reported-by: Jay Fenalson <fenlason@redhat.com>
CC: Divy LeRay <divy@chelsio.com>
CC: Stanislaw Gruszka <sgruszka@redhat.com>
CC: Joerg Roedel <joerg.roedel@amd.com>
CC: Arnd Bergmann <arnd@arndb.de>
---
 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;
 
 		/*
-- 
1.7.6

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

[Roedel, Joerg]

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)

to be sure. The patch above also lifts up the check_unmap which is not
desired.

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

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

[Neil Horman]

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

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

[Roedel, Joerg]

On Wed, Jul 20, 2011 at 07:11:56AM -0400, Neil Horman wrote:
> On Wed, Jul 20, 2011 at 12:38:13PM +0200, Roedel, Joerg wrote:

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

You are right. We need to scan

	0 <= idx <= hash_fn(rstart)

Probably we can fix that with a better hash-function. Any ideas? Using
the device is not an option because then all entries would end up in
only a few buckets. This will impact scanning performance too much.

For now, the partial syncs seem to happen rarely enough so that we can
make it a slow-path. It is probably the best to do the exact scan first
and do the full scan only if exact-scan failed (until we come up with a
better solution).


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

	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

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

[Neil Horman]

On Wed, Jul 20, 2011 at 03:29:25PM +0200, Roedel, Joerg wrote:
> On Wed, Jul 20, 2011 at 07:11:56AM -0400, Neil Horman wrote:
> > On Wed, Jul 20, 2011 at 12:38:13PM +0200, Roedel, Joerg wrote:
> 
> > > 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.
> 
> You are right. We need to scan
> 
> 	0 <= idx <= hash_fn(rstart)
> 
> Probably we can fix that with a better hash-function. Any ideas? Using
> the device is not an option because then all entries would end up in
> only a few buckets. This will impact scanning performance too much.
> 
Unfortunately I don't have any ideas for a better hash function here, but I had
been thinking about fixing this in add_dma_entry.  We could detect there that a
debug entry to be added crossed one or more hash bucket boundaries, and, if it
did, split it along those boundaries into multiple entries, hashing each of them
in separately.  The check_unmap and check_sync routines would of course then
potentially have to do multiple lookups as well to ensure that they found all of
the correct entries to validate/remove.  It would work in all cases, but it
might be overkill.  What do you think?

> For now, the partial syncs seem to happen rarely enough so that we can
> make it a slow-path. It is probably the best to do the exact scan first
> and do the full scan only if exact-scan failed (until we come up with a
> better solution).
> 
Agreed, if you don't like my above idea, I'll get to work on this this
afternoon.

Regards
Neil

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

[Roedel, Joerg]

On Wed, Jul 20, 2011 at 10:32:22AM -0400, Neil Horman wrote:
> On Wed, Jul 20, 2011 at 03:29:25PM +0200, Roedel, Joerg wrote:
> > You are right. We need to scan
> > 
> > 	0 <= idx <= hash_fn(rstart)
> > 
> > Probably we can fix that with a better hash-function. Any ideas? Using
> > the device is not an option because then all entries would end up in
> > only a few buckets. This will impact scanning performance too much.
> > 
> Unfortunately I don't have any ideas for a better hash function here, but I had
> been thinking about fixing this in add_dma_entry.  We could detect there that a
> debug entry to be added crossed one or more hash bucket boundaries, and, if it
> did, split it along those boundaries into multiple entries, hashing each of them
> in separately.  The check_unmap and check_sync routines would of course then
> potentially have to do multiple lookups as well to ensure that they found all of
> the correct entries to validate/remove.  It would work in all cases, but it
> might be overkill.  What do you think?

Interesting. I discussed that with a colleague an hour ago and he came
up with the same idea :-)
I like it because we still need to scan only one hash-bucket, so this
seems like the best solution.

> > For now, the partial syncs seem to happen rarely enough so that we can
> > make it a slow-path. It is probably the best to do the exact scan first
> > and do the full scan only if exact-scan failed (until we come up with a
> > better solution).
> > 
> Agreed, if you don't like my above idea, I'll get to work on this this
> afternoon.

I think this idea is a better solution.

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

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

[Neil Horman]

On Wed, Jul 20, 2011 at 04:59:01PM +0200, Roedel, Joerg wrote:
> On Wed, Jul 20, 2011 at 10:32:22AM -0400, Neil Horman wrote:
> > On Wed, Jul 20, 2011 at 03:29:25PM +0200, Roedel, Joerg wrote:
> > > You are right. We need to scan
> > > 
> > > 	0 <= idx <= hash_fn(rstart)
> > > 
> > > Probably we can fix that with a better hash-function. Any ideas? Using
> > > the device is not an option because then all entries would end up in
> > > only a few buckets. This will impact scanning performance too much.
> > > 
> > Unfortunately I don't have any ideas for a better hash function here, but I had
> > been thinking about fixing this in add_dma_entry.  We could detect there that a
> > debug entry to be added crossed one or more hash bucket boundaries, and, if it
> > did, split it along those boundaries into multiple entries, hashing each of them
> > in separately.  The check_unmap and check_sync routines would of course then
> > potentially have to do multiple lookups as well to ensure that they found all of
> > the correct entries to validate/remove.  It would work in all cases, but it
> > might be overkill.  What do you think?
> 
> Interesting. I discussed that with a colleague an hour ago and he came
> up with the same idea :-)
> I like it because we still need to scan only one hash-bucket, so this
> seems like the best solution.
> 
> > > For now, the partial syncs seem to happen rarely enough so that we can
> > > make it a slow-path. It is probably the best to do the exact scan first
> > > and do the full scan only if exact-scan failed (until we come up with a
> > > better solution).
> > > 
> > Agreed, if you don't like my above idea, I'll get to work on this this
> > afternoon.
> 
> I think this idea is a better solution.
> 
Copy that, i'll try implement it later today, 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
> 
> 

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Neil Horman]

dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

Summary:
Users of the pci_dma_sync_single_* api allow users to sync address ranges within
the range of a mapped entry (i.e. you can dma map address X to dma_addr_t A and
then pci_dma_sync_single on dma_addr_t A+1.  The dma-debug library however
assume dma syncs will always occur using the base address of a mapped region,
and uses that assumption to find entries in its hash table.  Since thats often
(but not always the case), the dma debug library can give us false errors about
missing entries, which are reported as syncing of memory not allocated by the
driver.  This was noted in the cxgb3 driver as this error:

WARNING: at lib/dma-debug.c:902 check_sync+0xdd/0x48c()
Hardware name: To be filled by O.E.M.
cxgb3 0000:01:00.0: DMA-API: device driver tries to sync DMA memory it has not
allocated [device address=0x00000000fff97800] [size=1984 bytes]
Modules linked in: autofs4 sunrpc cpufreq_ondemand acpi_cpufreq freq_table
mperf ip6t_REJECT nf_conntrack_ipv6 ip6table_filter ip6_tables ipv6 uinput
snd_hda_codec_intelhdmi snd_hda_codec_realtek snd_hda_intel snd_hda_codec
snd_hwdep snd_seq snd_seq_device snd_pcm snd_timer e1000e snd soundcore r8169
cxgb3 iTCO_wdt snd_page_alloc mii shpchp i2c_i801 iTCO_vendor_support mdio
microcode firewire_ohci firewire_core crc_itu_t ata_generic pata_acpi i915
drm_kms_helper drm i2c_algo_bit i2c_core video output [last unloaded:
scsi_wait_scan]
Pid: 1818, comm: ifconfig Not tainted 2.6.35-0.23.rc3.git6.fc14.x86_64 #1
Call Trace:
[<ffffffff81050f71>] warn_slowpath_common+0x85/0x9d
[<ffffffff8105102c>] warn_slowpath_fmt+0x46/0x48
[<ffffffff8124658e>] ? check_sync+0x39/0x48c
[<ffffffff8107c470>] ? trace_hardirqs_on+0xd/0xf
[<ffffffff81246632>] check_sync+0xdd/0x48c
[<ffffffff81246ca6>] debug_dma_sync_single_for_device+0x3f/0x41
[<ffffffffa011615c>] ? pci_map_page+0x84/0x97 [cxgb3]
[<ffffffffa0117bc3>] pci_dma_sync_single_for_device.clone.0+0x65/0x6e [cxgb3]
[<ffffffffa0117ed1>] refill_fl+0x305/0x30a [cxgb3]
[<ffffffffa011857d>] t3_sge_alloc_qset+0x6a7/0x821 [cxgb3]
[<ffffffffa010a07b>] cxgb_up+0x4d0/0xe62 [cxgb3]
[<ffffffff81086037>] ? __module_text_address+0x12/0x58
[<ffffffffa010aa4c>] cxgb_open+0x3f/0x309 [cxgb3]
[<ffffffff813e9f6c>] __dev_open+0x8e/0xbc
[<ffffffff813e7ca5>] __dev_change_flags+0xbe/0x142
[<ffffffff813e9ea8>] dev_change_flags+0x21/0x57
[<ffffffff81445937>] devinet_ioctl+0x29a/0x54b
[<ffffffff811f9a87>] ? inode_has_perm+0xaa/0xce
[<ffffffff81446ed2>] inet_ioctl+0x8f/0xa7
[<ffffffff813d683a>] sock_do_ioctl+0x29/0x48
[<ffffffff813d6c83>] sock_ioctl+0x213/0x222
[<ffffffff81137f78>] vfs_ioctl+0x32/0xa6
[<ffffffff811384e2>] do_vfs_ioctl+0x47a/0x4b3
[<ffffffff81138571>] sys_ioctl+0x56/0x79
[<ffffffff81009c32>] system_call_fastpath+0x16/0x1b
---[ end trace 69a4d4cc77b58004 ]---

Version 1 of this simply attempted to relax the search in hash_bucket_find to
allow for entries to be supersets of the requested address and range.  That
turned out to be to simplistic as it didn't account for the possibility that the
'base' entry might have hashed to a previous bucket, meaning several
(potentially time consuming) searches needed to be done.  The consensus was to
break a large entry up into several smaller entries, and hash them all
independently, but this turned out to hold its own issues.  Namely that some
devices have rather large dma operations, and consume many hundreds of entries
in a single map/unmap, making that approach detrimental as well.

So I came up with this idea.  Its closer to the first approach, but adds the
recursive search through the hash table, if the initial serach fails (i.e. a
slow path should the normal fast lookup fail).  I limit that search however to
the max_segment_size of the device, which tells us how big a given dma mapping
for that dev can be.  This lets us avoid having to traverse the hash table,
potentially many times over, looking for a match.  I've been testing this on my
system here, and it seems to be working well.

Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
Reported-by: Jay Fenalson <fenlason@redhat.com>
CC: Divy LeRay <divy@chelsio.com>
CC: Stanislaw Gruszka <sgruszka@redhat.com>
CC: Joerg Roedel <joerg.roedel@amd.com>
CC: Arnd Bergmann <arnd@arndb.de>

diff --git a/lib/dma-debug.c b/lib/dma-debug.c
index db07bfd..7f36be0 100644
--- a/lib/dma-debug.c
+++ b/lib/dma-debug.c
@@ -240,18 +240,39 @@ static void put_hash_bucket(struct hash_bucket *bucket,
 	spin_unlock_irqrestore(&bucket->lock, __flags);
 }
 
+static bool exact_match(struct dma_debug_entry *a, struct dma_debug_entry *b)
+{
+	return ((a->dev_addr == a->dev_addr) &&
+		(a->dev == b->dev)) ? true : false;
+}
+
+static bool containing_match(struct dma_debug_entry *a,
+			     struct dma_debug_entry *b)
+{
+	if (a->dev != b->dev)
+		return false;
+
+	if ((b->dev_addr <= a->dev_addr) &&
+	    ((b->dev_addr + b->size) >= (a->dev_addr + a->size)))
+		return true;
+
+	return false;
+}
+
 /*
  * Search a given entry in the hash bucket list
  */
 static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
-						struct dma_debug_entry *ref)
+						struct dma_debug_entry *ref,
+						bool (*match)(
+						     struct dma_debug_entry *a,
+						     struct dma_debug_entry *b))
 {
 	struct dma_debug_entry *entry, *ret = NULL;
 	int matches = 0, match_lvl, last_lvl = 0;
 
 	list_for_each_entry(entry, &bucket->list, list) {
-		if ((entry->dev_addr != ref->dev_addr) ||
-		    (entry->dev != ref->dev))
+		if (!match(ref, entry))
 			continue;
 
 		/*
@@ -293,6 +314,39 @@ static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
 	return ret;
 }
 
+static struct dma_debug_entry *hash_bucket_find_recursive(
+				  struct hash_bucket **bucket,
+				  struct dma_debug_entry *ref,
+				  unsigned long *flags)
+{
+
+	struct dma_debug_entry *entry, index;
+	unsigned int range = 0;
+	unsigned int max_range = dma_get_max_seg_size(ref->dev);
+
+	memcpy(&index, ref, sizeof(struct dma_debug_entry));
+	/*
+	 * Normalize the reference to start on a page boundary
+	 */
+
+	while (range <= max_range) {
+		entry = hash_bucket_find(*bucket, &index, containing_match);
+
+		if (entry)
+			return entry;
+
+		/*
+		 * Nothing found, go back a page
+		 */
+		range += (1 << HASH_FN_SHIFT);
+		put_hash_bucket(*bucket, flags);
+		index.dev_addr -= HASH_FN_SHIFT;
+		*bucket = get_hash_bucket(&index, flags);
+	}
+
+	return NULL;
+}
+
 /*
  * Add an entry to a hash bucket
  */
@@ -802,7 +856,7 @@ static void check_unmap(struct dma_debug_entry *ref)
 	}
 
 	bucket = get_hash_bucket(ref, &flags);
-	entry = hash_bucket_find(bucket, ref);
+	entry = hash_bucket_find(bucket, ref, exact_match);
 
 	if (!entry) {
 		err_printk(ref->dev, NULL, "DMA-API: device driver tries "
@@ -902,7 +956,7 @@ static void check_sync(struct device *dev,
 
 	bucket = get_hash_bucket(ref, &flags);
 
-	entry = hash_bucket_find(bucket, ref);
+	entry = hash_bucket_find_recursive(&bucket, ref, &flags);
 
 	if (!entry) {
 		err_printk(dev, NULL, "DMA-API: device driver tries "
@@ -1060,7 +1114,7 @@ static int get_nr_mapped_entries(struct device *dev,
 	int mapped_ents;
 
 	bucket       = get_hash_bucket(ref, &flags);
-	entry        = hash_bucket_find(bucket, ref);
+	entry        = hash_bucket_find(bucket, ref, exact_match);
 	mapped_ents  = 0;
 
 	if (entry)

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Roedel, Joerg]

On Mon, Aug 08, 2011 at 03:13:54PM -0400, Neil Horman wrote:
> dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)
> 
> Summary:
> Users of the pci_dma_sync_single_* api allow users to sync address ranges within
> the range of a mapped entry (i.e. you can dma map address X to dma_addr_t A and
> then pci_dma_sync_single on dma_addr_t A+1.  The dma-debug library however
> assume dma syncs will always occur using the base address of a mapped region,
> and uses that assumption to find entries in its hash table.  Since thats often
> (but not always the case), the dma debug library can give us false errors about
> missing entries, which are reported as syncing of memory not allocated by the
> driver.  This was noted in the cxgb3 driver as this error:

Hi Neil,

thanks for your patch. Im out-of-office this week and traveling next
week. So it may take a couple of days until I can take an in-depth look
at it. But I get to it as soon as I can :-)

Regards,

	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

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Neil Horman]

On Wed, Aug 10, 2011 at 03:31:59PM +0200, Roedel, Joerg wrote:
> On Mon, Aug 08, 2011 at 03:13:54PM -0400, Neil Horman wrote:
> > dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)
> > 
> > Summary:
> > Users of the pci_dma_sync_single_* api allow users to sync address ranges within
> > the range of a mapped entry (i.e. you can dma map address X to dma_addr_t A and
> > then pci_dma_sync_single on dma_addr_t A+1.  The dma-debug library however
> > assume dma syncs will always occur using the base address of a mapped region,
> > and uses that assumption to find entries in its hash table.  Since thats often
> > (but not always the case), the dma debug library can give us false errors about
> > missing entries, which are reported as syncing of memory not allocated by the
> > driver.  This was noted in the cxgb3 driver as this error:
> 
> Hi Neil,
> 
> thanks for your patch. Im out-of-office this week and traveling next
> week. So it may take a couple of days until I can take an in-depth look
> at it. But I get to it as soon as I can :-)
> 
> Regards,
> 
> 	Joerg
> 
No worries, don't rush.  Thank you for letting me know.
Regards
Neil

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

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Neil Horman]

On Wed, Aug 10, 2011 at 03:31:59PM +0200, Roedel, Joerg wrote:
> On Mon, Aug 08, 2011 at 03:13:54PM -0400, Neil Horman wrote:
> > dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)
> > 
> > Summary:
> > Users of the pci_dma_sync_single_* api allow users to sync address ranges within
> > the range of a mapped entry (i.e. you can dma map address X to dma_addr_t A and
> > then pci_dma_sync_single on dma_addr_t A+1.  The dma-debug library however
> > assume dma syncs will always occur using the base address of a mapped region,
> > and uses that assumption to find entries in its hash table.  Since thats often
> > (but not always the case), the dma debug library can give us false errors about
> > missing entries, which are reported as syncing of memory not allocated by the
> > driver.  This was noted in the cxgb3 driver as this error:
> 
> Hi Neil,
> 
> thanks for your patch. Im out-of-office this week and traveling next
> week. So it may take a couple of days until I can take an in-depth look
> at it. But I get to it as soon as I can :-)
> 
> Regards,
> 
> 	Joerg
> 
Hey, Jeorg, just wondering if you managed to get a look at this?
Neil

> -- 
> 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@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Roedel, Joerg]

Hi Neil,

On Mon, Aug 22, 2011 at 06:46:21AM -0400, Neil Horman wrote:

> Hey, Jeorg, just wondering if you managed to get a look at this?
> Neil

It is not forgotten :) This is my first day back in office and I will
look into it today.

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

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Neil Horman]

On Mon, Aug 22, 2011 at 02:44:27PM +0200, Roedel, Joerg wrote:
> Hi Neil,
> 
> On Mon, Aug 22, 2011 at 06:46:21AM -0400, Neil Horman wrote:
> 
> > Hey, Jeorg, just wondering if you managed to get a look at this?
> > Neil
> 
> It is not forgotten :) This is my first day back in office and I will
> look into it today.
> 
Ah, apologies, I'm just getting back from vacation myself, and am trying to
figure out where I left off with everything :)
Neil

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

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Roedel, Joerg]

Hi Neil,

I applied your patch and did some minor changes and fixed one problem I
have seen. Find the edited version appended, when this is fine for you I
push it.

Thanks,
	Joerg

On Mon, Aug 08, 2011 at 03:13:54PM -0400, Neil Horman wrote:
> +		range += (1 << HASH_FN_SHIFT);
> +		put_hash_bucket(*bucket, flags);
> +		index.dev_addr -= HASH_FN_SHIFT;

This should be index.dev_addr -= (1 << HASH_FN_SHIFT), right?

Here is the changed version:

commit 30172f1a71871acbbbbe7325a4264762211f4824
Author: Neil Horman <nhorman@tuxdriver.com>
Date:   Mon Aug 8 15:13:54 2011 -0400

    dma-debug: hash_bucket_find needs to allow for offsets within an entry
    
    Summary:
    Users of the pci_dma_sync_single_* api allow users to sync address ranges within
    the range of a mapped entry (i.e. you can dma map address X to dma_addr_t A and
    then pci_dma_sync_single on dma_addr_t A+1.  The dma-debug library however
    assume dma syncs will always occur using the base address of a mapped region,
    and uses that assumption to find entries in its hash table.  Since thats often
    (but not always the case), the dma debug library can give us false errors about
    missing entries, which are reported as syncing of memory not allocated by the
    driver.  This was noted in the cxgb3 driver as this error:
    
    WARNING: at lib/dma-debug.c:902 check_sync+0xdd/0x48c()
    Hardware name: To be filled by O.E.M.
    cxgb3 0000:01:00.0: DMA-API: device driver tries to sync DMA memory it has not
    allocated [device address=0x00000000fff97800] [size=1984 bytes]
    Modules linked in: autofs4 sunrpc cpufreq_ondemand acpi_cpufreq freq_table
    mperf ip6t_REJECT nf_conntrack_ipv6 ip6table_filter ip6_tables ipv6 uinput
    snd_hda_codec_intelhdmi snd_hda_codec_realtek snd_hda_intel snd_hda_codec
    snd_hwdep snd_seq snd_seq_device snd_pcm snd_timer e1000e snd soundcore r8169
    cxgb3 iTCO_wdt snd_page_alloc mii shpchp i2c_i801 iTCO_vendor_support mdio
    microcode firewire_ohci firewire_core crc_itu_t ata_generic pata_acpi i915
    drm_kms_helper drm i2c_algo_bit i2c_core video output [last unloaded:
    scsi_wait_scan]
    Pid: 1818, comm: ifconfig Not tainted 2.6.35-0.23.rc3.git6.fc14.x86_64 #1
    Call Trace:
    [<ffffffff81050f71>] warn_slowpath_common+0x85/0x9d
    [<ffffffff8105102c>] warn_slowpath_fmt+0x46/0x48
    [<ffffffff8124658e>] ? check_sync+0x39/0x48c
    [<ffffffff8107c470>] ? trace_hardirqs_on+0xd/0xf
    [<ffffffff81246632>] check_sync+0xdd/0x48c
    [<ffffffff81246ca6>] debug_dma_sync_single_for_device+0x3f/0x41
    [<ffffffffa011615c>] ? pci_map_page+0x84/0x97 [cxgb3]
    [<ffffffffa0117bc3>] pci_dma_sync_single_for_device.clone.0+0x65/0x6e [cxgb3]
    [<ffffffffa0117ed1>] refill_fl+0x305/0x30a [cxgb3]
    [<ffffffffa011857d>] t3_sge_alloc_qset+0x6a7/0x821 [cxgb3]
    [<ffffffffa010a07b>] cxgb_up+0x4d0/0xe62 [cxgb3]
    [<ffffffff81086037>] ? __module_text_address+0x12/0x58
    [<ffffffffa010aa4c>] cxgb_open+0x3f/0x309 [cxgb3]
    [<ffffffff813e9f6c>] __dev_open+0x8e/0xbc
    [<ffffffff813e7ca5>] __dev_change_flags+0xbe/0x142
    [<ffffffff813e9ea8>] dev_change_flags+0x21/0x57
    [<ffffffff81445937>] devinet_ioctl+0x29a/0x54b
    [<ffffffff811f9a87>] ? inode_has_perm+0xaa/0xce
    [<ffffffff81446ed2>] inet_ioctl+0x8f/0xa7
    [<ffffffff813d683a>] sock_do_ioctl+0x29/0x48
    [<ffffffff813d6c83>] sock_ioctl+0x213/0x222
    [<ffffffff81137f78>] vfs_ioctl+0x32/0xa6
    [<ffffffff811384e2>] do_vfs_ioctl+0x47a/0x4b3
    [<ffffffff81138571>] sys_ioctl+0x56/0x79
    [<ffffffff81009c32>] system_call_fastpath+0x16/0x1b
    ---[ end trace 69a4d4cc77b58004 ]---
    
    (some edits by Joerg Roedel)
    
    Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
    Reported-by: Jay Fenalson <fenlason@redhat.com>
    CC: Divy LeRay <divy@chelsio.com>
    CC: Stanislaw Gruszka <sgruszka@redhat.com>
    CC: Joerg Roedel <joerg.roedel@amd.com>
    CC: Arnd Bergmann <arnd@arndb.de>
    Signed-off-by: Joerg Roedel <joerg.roedel@amd.com>

diff --git a/lib/dma-debug.c b/lib/dma-debug.c
index db07bfd..79700fa 100644
--- a/lib/dma-debug.c
+++ b/lib/dma-debug.c
@@ -62,6 +62,8 @@ struct dma_debug_entry {
 #endif
 };
 
+typedef bool (*match_fn)(struct dma_debug_entry *, struct dma_debug_entry *);
+
 struct hash_bucket {
 	struct list_head list;
 	spinlock_t lock;
@@ -240,18 +242,37 @@ static void put_hash_bucket(struct hash_bucket *bucket,
 	spin_unlock_irqrestore(&bucket->lock, __flags);
 }
 
+static bool exact_match(struct dma_debug_entry *a, struct dma_debug_entry *b)
+{
+	return ((a->dev_addr == a->dev_addr) &&
+		(a->dev == b->dev)) ? true : false;
+}
+
+static bool containing_match(struct dma_debug_entry *a,
+			     struct dma_debug_entry *b)
+{
+	if (a->dev != b->dev)
+		return false;
+
+	if ((b->dev_addr <= a->dev_addr) &&
+	    ((b->dev_addr + b->size) >= (a->dev_addr + a->size)))
+		return true;
+
+	return false;
+}
+
 /*
  * Search a given entry in the hash bucket list
  */
-static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
-						struct dma_debug_entry *ref)
+static struct dma_debug_entry *__hash_bucket_find(struct hash_bucket *bucket,
+						  struct dma_debug_entry *ref,
+						  match_fn match)
 {
 	struct dma_debug_entry *entry, *ret = NULL;
 	int matches = 0, match_lvl, last_lvl = 0;
 
 	list_for_each_entry(entry, &bucket->list, list) {
-		if ((entry->dev_addr != ref->dev_addr) ||
-		    (entry->dev != ref->dev))
+		if (!match(ref, entry))
 			continue;
 
 		/*
@@ -293,6 +314,39 @@ static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
 	return ret;
 }
 
+static struct dma_debug_entry *bucket_find_exact(struct hash_bucket *bucket,
+						 struct dma_debug_entry *ref)
+{
+	return __hash_bucket_find(bucket, ref, exact_match);
+}
+
+static struct dma_debug_entry *bucket_find_contain(struct hash_bucket **bucket,
+						   struct dma_debug_entry *ref,
+						   unsigned long *flags)
+{
+
+	unsigned int max_range = dma_get_max_seg_size(ref->dev);
+	struct dma_debug_entry *entry, index = *ref;
+	unsigned int range = 0;
+
+	while (range <= max_range) {
+		entry = __hash_bucket_find(*bucket, &index, containing_match);
+
+		if (entry)
+			return entry;
+
+		/*
+		 * Nothing found, go back a hash bucket
+		 */
+		put_hash_bucket(*bucket, flags);
+		range          += (1 << HASH_FN_SHIFT);
+		index.dev_addr -= (1 << HASH_FN_SHIFT);
+		*bucket = get_hash_bucket(&index, flags);
+	}
+
+	return NULL;
+}
+
 /*
  * Add an entry to a hash bucket
  */
@@ -802,7 +856,7 @@ static void check_unmap(struct dma_debug_entry *ref)
 	}
 
 	bucket = get_hash_bucket(ref, &flags);
-	entry = hash_bucket_find(bucket, ref);
+	entry = bucket_find_exact(bucket, ref);
 
 	if (!entry) {
 		err_printk(ref->dev, NULL, "DMA-API: device driver tries "
@@ -902,7 +956,7 @@ static void check_sync(struct device *dev,
 
 	bucket = get_hash_bucket(ref, &flags);
 
-	entry = hash_bucket_find(bucket, ref);
+	entry = bucket_find_contain(&bucket, ref, &flags);
 
 	if (!entry) {
 		err_printk(dev, NULL, "DMA-API: device driver tries "
@@ -1060,7 +1114,7 @@ static int get_nr_mapped_entries(struct device *dev,
 	int mapped_ents;
 
 	bucket       = get_hash_bucket(ref, &flags);
-	entry        = hash_bucket_find(bucket, ref);
+	entry        = bucket_find_exact(bucket, ref);
 	mapped_ents  = 0;
 
 	if (entry)

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

Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets within an entry (v2)

[Neil Horman]

On Mon, Aug 22, 2011 at 06:46:26PM +0200, Roedel, Joerg wrote:
> Hi Neil,
> 
> I applied your patch and did some minor changes and fixed one problem I
> have seen. Find the edited version appended, when this is fine for you I
> push it.
> 
> Thanks,
> 	Joerg
> 
> On Mon, Aug 08, 2011 at 03:13:54PM -0400, Neil Horman wrote:
> > +		range += (1 << HASH_FN_SHIFT);
> > +		put_hash_bucket(*bucket, flags);
> > +		index.dev_addr -= HASH_FN_SHIFT;
> 
> This should be index.dev_addr -= (1 << HASH_FN_SHIFT), right?
> 
Yup, thats right, good catch, thanks!
Acked-by: Neil Horman <nhorman@tuxdriver.com>