linux-kernel - [tip:core/iommu] dma-debug: change hash_bucket

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: <tip-7caf6a49bb17d0377210693af5737563b31aa5ee@git.kernel.org>
Date:	Sun, 7 Jun 2009 10:22:42 GMT
From:	tip-bot for Joerg Roedel <joerg.roedel@....com>
To:	linux-tip-commits@...r.kernel.org
Cc:	linux-kernel@...r.kernel.org, hpa@...or.com, mingo@...hat.com,
	just.for.lkml@...glemail.com, torvalds@...ux-foundation.org,
	joerg.roedel@....com, fujita.tomonori@....ntt.co.jp,
	stable@...nel.org, tglx@...utronix.de, mingo@...e.hu
Subject: [tip:core/iommu] dma-debug: change hash_bucket_find from first-fit to best-fit

Commit-ID:  7caf6a49bb17d0377210693af5737563b31aa5ee
Gitweb:     http://git.kernel.org/tip/7caf6a49bb17d0377210693af5737563b31aa5ee
Author:     Joerg Roedel <joerg.roedel@....com>
AuthorDate: Fri, 5 Jun 2009 12:01:35 +0200
Committer:  Ingo Molnar <mingo@...e.hu>
CommitDate: Sun, 7 Jun 2009 10:04:53 +0200

dma-debug: change hash_bucket_find from first-fit to best-fit

Some device drivers map the same physical address multiple times to a
dma address. Without an IOMMU this results in the same dma address being
put into the dma-debug hash multiple times. With a first-fit match in
hash_bucket_find() this function may return the wrong dma_debug_entry.

This can result in false positive warnings. This patch fixes it by
changing the first-fit behavior of hash_bucket_find() into a best-fit
algorithm.

Reported-by: Torsten Kaiser <just.for.lkml@...glemail.com>
Reported-by: FUJITA Tomonori <fujita.tomonori@....ntt.co.jp>
Signed-off-by: Joerg Roedel <joerg.roedel@....com>
Cc: lethal@...ux-sh.org
Cc: just.for.lkml@...glemail.com
Cc: hancockrwd@...il.com
Cc: jens.axboe@...cle.com
Cc: bharrosh@...asas.com
Cc: FUJITA Tomonori <fujita.tomonori@....ntt.co.jp>
Cc: Linus Torvalds <torvalds@...ux-foundation.org>
Cc: <stable@...nel.org>
LKML-Reference: <20090605104132.GE24836@....com>
Signed-off-by: Ingo Molnar <mingo@...e.hu>


---
 lib/dma-debug.c |   43 +++++++++++++++++++++++++++++++++++++++----
 1 files changed, 39 insertions(+), 4 deletions(-)

diff --git a/lib/dma-debug.c b/lib/dma-debug.c
index cdd205d..8fcc09c 100644
--- a/lib/dma-debug.c
+++ b/lib/dma-debug.c
@@ -186,15 +186,50 @@ static void put_hash_bucket(struct hash_bucket *bucket,
 static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
 						struct dma_debug_entry *ref)
 {
-	struct dma_debug_entry *entry;
+	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 ((entry->dev_addr != ref->dev_addr) ||
+		    (entry->dev != ref->dev))
+			continue;
+
+		/*
+		 * Some drivers map the same physical address multiple
+		 * times. Without a hardware IOMMU this results in the
+		 * same device addresses being put into the dma-debug
+		 * hash multiple times too. This can result in false
+		 * positives being reported. Therfore we implement a
+		 * best-fit algorithm here which returns the entry from
+		 * the hash which fits best to the reference value
+		 * instead of the first-fit.
+		 */
+		matches += 1;
+		match_lvl = 0;
+		entry->size      == ref->size      ? ++match_lvl : match_lvl;
+		entry->type      == ref->type      ? ++match_lvl : match_lvl;
+		entry->direction == ref->direction ? ++match_lvl : match_lvl;
+
+		if (match_lvl == 3) {
+			/* perfect-fit - return the result */
 			return entry;
+		} else if (match_lvl > last_lvl) {
+			/*
+			 * We found an entry that fits better then the
+			 * previous one
+			 */
+			last_lvl = match_lvl;
+			ret      = entry;
+		}
 	}
 
-	return NULL;
+	/*
+	 * If we have multiple matches but no perfect-fit, just return
+	 * NULL.
+	 */
+	ret = (matches == 1) ? ret : NULL;
+
+	return ret;
 }
 
 /*
--
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/