[PATCH] evdev: discard oldest event on buffer overflow

[PATCH] evdev: discard oldest event on buffer overflow

[Bill Gatliff]

On a buffer overflow, the head and tail pointers collide.
This makes the buffer suddenly look empty, rather than
full, which may confuse applications.

This patch moves the tail pointer up one event on a buffer
overflow, which "consumes" the oldest event in the buffer
to make room for the incoming event.  Thus, although data
is lost due to the overflow (which is unavoidable), the
data that remains is both recent and still time-ordered.

Signed-off-by: Bill Gatliff <bgat@billgatliff.com>
---
 drivers/input/evdev.c |   18 +++++++++++-------
 1 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/drivers/input/evdev.c b/drivers/input/evdev.c
index e3f7fc6..04a18ff 100644
--- a/drivers/input/evdev.c
+++ b/drivers/input/evdev.c
@@ -55,15 +55,19 @@ static void evdev_pass_event(struct evdev_client *client,
 {
 	/*
 	 * Interrupts are disabled, just acquire the lock.
-	 * Make sure we don't leave with the client buffer
-	 * "empty" by having client->head == client->tail.
 	 */
 	spin_lock(&client->buffer_lock);
-	do {
-		client->buffer[client->head++] = *event;
-		client->head &= client->bufsize - 1;
-	} while (client->head == client->tail);
-	spin_unlock(&client->buffer_lock);
+	client->buffer[client->head++] = *event;
+	client->head &= client->bufsize - 1;
+
+	/*
+	 * If we overflow the buffer, consume the oldest
+	 * event to make room for the one that just arrived
+	 */
+	if (unlikely(client->head == client->tail)) {
+		client->tail++;
+		client->tail &= client->bufsize - 1;
+	}
 
 	if (event->type == EV_SYN)
 		kill_fasync(&client->fasync, SIGIO, POLL_IN);
-- 
1.7.1

Re: [PATCH] evdev: discard oldest event on buffer overflow

[Dmitry Torokhov]

On Wed, Oct 27, 2010 at 12:09:58PM -0500, Bill Gatliff wrote:
> On a buffer overflow, the head and tail pointers collide.
> This makes the buffer suddenly look empty, rather than
> full, which may confuse applications.
> 
> This patch moves the tail pointer up one event on a buffer
> overflow, which "consumes" the oldest event in the buffer
> to make room for the incoming event.  Thus, although data
> is lost due to the overflow (which is unavoidable), the
> data that remains is both recent and still time-ordered.
> 

It does not really matter... You are losing part of the hardware state
regardless so the packet is invalid anyway. What would probably make
more sense is to ignore all events up until next packet boundary
(EV_SYN/SYN_REPORT) so userspace would get most up-to-date _full_ packet
(when it catches up).

Thanks.

-- 
Dmitry

Re: [PATCH] evdev: discard oldest event on buffer overflow

[Bill Gatliff]

On Wed, Oct 27, 2010 at 4:57 PM, Dmitry Torokhov
<dmitry.torokhov@gmail.com> wrote:
> On Wed, Oct 27, 2010 at 12:09:58PM -0500, Bill Gatliff wrote:
>> This patch moves the tail pointer up one event on a buffer
>> overflow, which "consumes" the oldest event in the buffer
>> to make room for the incoming event.  Thus, although data
>> is lost due to the overflow (which is unavoidable), the
>> data that remains is both recent and still time-ordered.
>>
>
> It does not really matter... You are losing part of the hardware state
> regardless so the packet is invalid anyway. What would probably make
> more sense is to ignore all events up until next packet boundary
> (EV_SYN/SYN_REPORT) so userspace would get most up-to-date _full_ packet
> (when it catches up).

That's an interesting idea, actually.  Maybe the subject of a future patch.  :)

I still think my patch is a genuine improvement as-is, however.  But
perhaps not the final word on the issue.

For example, how do you recall the events that userspace has already
digested from the current packet?  One alternative is to not queue a
packet until the whole packet is ready, but that will introduce
latency.  I don't like that approach, either.  Hmmm...

I suppose another possibility is to always reserve enough room for an
EV_SYN/SYN_REPORT event, and never discard those events.  Then
userspace will always see a properly-terminated packet, but in a
collision it would receive a partial-but-properly-terminated packet.


b.g.
-- 
Bill Gatliff
bgat@billgatliff.com
--
To unsubscribe from this list: send the line "unsubscribe linux-input" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] evdev: discard oldest event on buffer overflow

[Dmitry Torokhov]

On Wed, Oct 27, 2010 at 05:11:28PM -0700, Bill Gatliff wrote:
> On Wed, Oct 27, 2010 at 4:57 PM, Dmitry Torokhov
> <dmitry.torokhov@gmail.com> wrote:
> > On Wed, Oct 27, 2010 at 12:09:58PM -0500, Bill Gatliff wrote:
> >> This patch moves the tail pointer up one event on a buffer
> >> overflow, which "consumes" the oldest event in the buffer
> >> to make room for the incoming event.  Thus, although data
> >> is lost due to the overflow (which is unavoidable), the
> >> data that remains is both recent and still time-ordered.
> >>
> >
> > It does not really matter... You are losing part of the hardware state
> > regardless so the packet is invalid anyway. What would probably make
> > more sense is to ignore all events up until next packet boundary
> > (EV_SYN/SYN_REPORT) so userspace would get most up-to-date _full_ packet
> > (when it catches up).
> 
> That's an interesting idea, actually.  Maybe the subject of a future patch.  :)
> 
> I still think my patch is a genuine improvement as-is, however.

Sorry, I am unconvinced that it is an improvement.

> But
> perhaps not the final word on the issue.
> 
> For example, how do you recall the events that userspace has already
> digested from the current packet?  One alternative is to not queue a
> packet until the whole packet is ready, but that will introduce
> latency.  I don't like that approach, either.  Hmmm...

Userspace is not supposed to act on a packet until it receives
SYN_REPORT. Userspace should also be prepared to handle events
overriding older ones. So there is no "recall" needed. Consider finger
moving on a high-speed/high-resolution touchpad (only coordinates, no
exteneded attributes for simplicity sake):

  1      2     3    4      5     6   7       8     9   10      11    12
ABS_X1 ABS_Y1 SYN ABS_X2 ABS_Y2 SYN ABS_X3 ABS_Y3 SYN ABS_X4 ABS_Y4 SYN

Imagine you overflow and lose events 5 through 9 - no big deal.
Userspace will get ABS_X2 ABS_X4 ABS_Y4 SYN which will tranlate into
(X4, Y4) - the most recent coordinates (and ones we are interested in
most of all). It is not that important where finger was a second ago as
it is important where it is _now_.

Of course you may still lose some data (key/button releases, etc) but
input devices should size buffers properly and overflows should be rare
events.

> 
> I suppose another possibility is to always reserve enough room for an
> EV_SYN/SYN_REPORT event, and never discard those events.  Then
> userspace will always see a properly-terminated packet, but in a
> collision it would receive a partial-but-properly-terminated packet.
> 

And what is the benefit of properly terminated but incomplete packet?
Let's say you are doing a pinch gesture with 2 fingers. Would you rather
lose one finger data (and then your pinch is not pinch anymore but a
single touch) or discard one packet completely so that the next
(complete one) allows you to continue gesture as is?

-- 
Dmitry
--
To unsubscribe from this list: send the line "unsubscribe linux-input" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] evdev: discard oldest event on buffer overflow

[Bill Gatliff]

On Wed, Oct 27, 2010 at 5:30 PM, Dmitry Torokhov
<dmitry.torokhov@gmail.com> wrote:
> On Wed, Oct 27, 2010 at 05:11:28PM -0700, Bill Gatliff wrote:
>> I still think my patch is a genuine improvement as-is, however.
>
> Sorry, I am unconvinced that it is an improvement.

The current code clobbers the queue suddenly and entirely on overflow,
and replaces all the events therein with the current one.  My version
simply discards the oldest event to make room for the newest one.
I'll agree that my patch doesn't utterly and completely fix the
problem, but I have verified that at least with a flood of incoming
multitouch packets, the system still generally behaves itself--- which
is far more than it was able to do with the code that I replaced.

How else would you be convinced?  You can't possibly believe that the
current code needs to stay in place, can you?

The thing with touch events specifically is that they contain tons of
redundant information, so losing a few old ones here and there
generally doesn't cause problems--- but losing a whole bunch of them
at the moment of overflow DOES seem to cause problems.  And touch
events tend to be bursty, making them more likely to trigger such
overflows in the first place.

With keycodes, on the other hand, you don't want to lose any of them.
Ever.  But such devices don't tend to generate events as fast, and the
recent versions of the evdev queue did such a poor job on overflow
that it's pretty clear that overflows must not have happened that
often.  Never, perhaps.

That's why even in its imperfect state, my patch seems to improve
things--- because it makes a difference under conditions where
dropping portions of a packet don't seem to matter as much.  It
doesn't get triggered in cases where dropping an event will almost
certainly lead to problems.

The alternative, of course, is to smarten-up the evdev queues so that
they work at the level of entire packets, rather than individual
events.  In the meantime, I'll proffer my patch as a small step in the
right direction.  Especially considering where we are coming from.


b.g.
-- 
Bill Gatliff
bgat@billgatliff.com

Re: [PATCH] evdev: discard oldest event on buffer overflow

[Dmitry Torokhov]

On Wed, Oct 27, 2010 at 09:25:23PM -0700, Bill Gatliff wrote:
> On Wed, Oct 27, 2010 at 5:30 PM, Dmitry Torokhov
> <dmitry.torokhov@gmail.com> wrote:
> > On Wed, Oct 27, 2010 at 05:11:28PM -0700, Bill Gatliff wrote:
> >> I still think my patch is a genuine improvement as-is, however.
> >
> > Sorry, I am unconvinced that it is an improvement.
> 
> The current code clobbers the queue suddenly and entirely on overflow,
> and replaces all the events therein with the current one.  My version
> simply discards the oldest event to make room for the newest one.
> I'll agree that my patch doesn't utterly and completely fix the
> problem, but I have verified that at least with a flood of incoming
> multitouch packets, the system still generally behaves itself--- which
> is far more than it was able to do with the code that I replaced.
> 

Is it still the case with 2.6.36? We added a code there to properly size
the length of evdev queues depending on the expected number of input
events in a packet.

-- 
Dmitry

Re: evdev: discard oldest event on buffer overflow

[Henrik Rydberg]

On 10/27/2010 07:09 PM, Bill Gatliff wrote:

> On a buffer overflow, the head and tail pointers collide.
> This makes the buffer suddenly look empty, rather than
> full, which may confuse applications.


This is actually an important regulatory effect which increases the ability for
the client to catch up.

> This patch moves the tail pointer up one event on a buffer
> overflow, which "consumes" the oldest event in the buffer
> to make room for the incoming event.  Thus, although data
> is lost due to the overflow (which is unavoidable), the
> data that remains is both recent and still time-ordered.


As Dmitry said, snapping discards to the event synchronization boundaries could
be useful, but I doubt it is really worthwhile.

Henrik