linux-kernel - Re: [PATCH 1/3] Input: mt - prevent balanced slot assignment to assign twice the slot

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]

Date:	Tue, 31 Mar 2015 09:24:30 +0200
From:	Henrik Rydberg <rydberg@...math.org>
To:	Benjamin Tissoires <benjamin.tissoires@...hat.com>
Cc:	Dmitry Torokhov <dmitry.torokhov@...il.com>,
	Hans de Goede <hdegoede@...hat.com>,
	Peter Hutterer <peter.hutterer@...hat.com>,
	linux-input@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/3] Input: mt - prevent balanced slot assignment to
 assign twice the slot

Hi Benjamin,

> If two touches are under the dmax distance, it looks like they can now
> be assigned to the same slot. Add a band aid to prevent such situation
> and be able to use the balanced slot assignment.

Yes, great find. You patch is correct, but it is not a band aid, but a
result stemming from a limitation in how equality constraints (read
unique assignments) can be handled in the iterative algorithm. This
cannot happen in the original algorithm, because of the extra
penalization for overcovers.

Here is an alternative version which cleans up the loop logic
somewhat, together with a different commit message. I did not have any
opportunity to check this in hardware. I you like it and find it
working, then please take over the authorship and just add a
signed-off from me.

Thanks,
Henrik

---

>From e00d63f6cadf20d871bed763b3531428b34d785c Mon Sep 17 00:00:00 2001
From: Henrik Rydberg <rydberg@...math.org>
Date: Tue, 31 Mar 2015 09:10:02 +0200
Subject: [PATCH] Input: MT - make slot assignment work for overcovered
 solutions

The recent inclusion of a deassignment cost in the slot assignment
algorithm did not properly account for the corner cases where the
solutions are overcovered. This patch makes sure the resulting assignment
is unique, allocating new slots when necessary.

UNTESTED
---
 drivers/input/input-mt.c | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/drivers/input/input-mt.c b/drivers/input/input-mt.c
index fbe29fc..17e80a6 100644
--- a/drivers/input/input-mt.c
+++ b/drivers/input/input-mt.c
@@ -363,25 +363,28 @@ static void input_mt_set_slots(struct input_mt *mt,
 			       int *slots, int num_pos)
 {
 	struct input_mt_slot *s;
-	int *w = mt->red, *p;
+	int *w = mt->red, j;
 
-	for (p = slots; p != slots + num_pos; p++)
-		*p = -1;
+	for (j = 0; j != num_pos; j++)
+		slots[j] = -1;
 
 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
 		if (!input_mt_is_active(s))
 			continue;
-		for (p = slots; p != slots + num_pos; p++)
-			if (*w++ < 0)
-				*p = s - mt->slots;
+		for (j = 0; j != num_pos; j++)
+			if (w[j] < 0) {
+				slots[j] = s - mt->slots;
+				break;
+			}
+		w += num_pos;
 	}
 
 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
 		if (input_mt_is_active(s))
 			continue;
-		for (p = slots; p != slots + num_pos; p++)
-			if (*p < 0) {
-				*p = s - mt->slots;
+		for (j = 0; j != num_pos; j++)
+			if (slots[j] < 0) {
+				slots[j] = s - mt->slots;
 				break;
 			}
 	}
-- 
2.3.0

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