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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20110720143222.GB12349@hmsreliant.think-freely.org>
Date:	Wed, 20 Jul 2011 10:32:22 -0400
From:	Neil Horman <nhorman@...driver.com>
To:	"Roedel, Joerg" <Joerg.Roedel@....com>
Cc:	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	Divy LeRay <divy@...lsio.com>,
	Stanislaw Gruszka <sgruszka@...hat.com>,
	Arnd Bergmann <arnd@...db.de>
Subject: Re: [PATCH] dma-debug: hash_bucket_find needs to allow for offsets
 within an entry

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


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/