[PATCH 0/4] input: Sizing the evdev ring buffer for MT devices and reporting overruns.

In recent kernels, input device drivers can specify a hint for the number of input events per packet.  However, most drivers don't do this.  There is some code in hid/hid-input.c that attempts to choose a larger default for MT devices but it does not apply to all input devices.  In particular, it does not apply to embedded touchscreens in phones and the like.

Currently, when the evdev ring buffer overflows, all old events are dropped.  (See input/evdev.c: evdev_pass_event)

Unfortunately, the reader has no idea that this has occurred.  The next event that the reader receives will likely be in the middle of a new packet.  This can cause the reader getting confused about which fingers are down or which slots are in use.

There are also problems on SMP systems where an evdev client may end up in a degenerate case where it reads events one at a time at the same rate they are produced instead of reading the entire packet all at once when it is ready.  This causes high CPU usage, particularly when reading from MT devices.  Ideally, evdev should only wake up poll() when the packet is complete.  (Assuming all input drivers call input_sync after they are finished writing events.  Some drivers seem to be broken in this regard.)

As a point of departure for further discussion, here are four patches.

1. During input device registration, choose a default size for the buffer based on the number of slots or tracking ids that a device reports and the number of axes it has.

2. Remove a redundant hardcoded default from hid-input.c.

3. Add a new SYN_DROPPED code that is used by evdev to indicate that some input events were dropped from the ring buffer and are missing.  The client can use this event as a hint that it should reset its state or ignore all following events until the next packet begins.

4. Only wake evdev clients from poll() when an EV_SYN is enqueued, excluding SYN_MT_REPORT.

Thanks,
Jeff.

From: Jeff Brown <redacted>

Calculate a default based on the number of ABS axes, REL axes,
and MT slots for the device during input device registration.

Signed-off-by: jeffbrown@android.com
---
 drivers/input/input.c |   46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 46 insertions(+), 0 deletions(-)

diff --git a/drivers/input/input.c b/drivers/input/input.c
index d6e8bd8..c27292b 100644
--- a/drivers/input/input.c
+++ b/drivers/input/input.c

@@ -1746,6 +1746,49 @@ void input_set_capability(struct input_dev *dev, unsigned int type, unsigned int
 }
 EXPORT_SYMBOL(input_set_capability);
 
+static inline bool is_mt_axis(int axis)
+{
+	return axis == ABS_MT_SLOT ||
+		(axis >= ABS_MT_FIRST && axis <= ABS_MT_LAST);
+}
+
+static void input_set_default_events_per_packet(struct input_dev *dev)
+{
+	int mt_slots;
+	int i;
+	int events;
+
+	if (dev->hint_events_per_packet)
+		return;
+
+	if (dev->mtsize)
+		mt_slots = dev->mtsize;
+	else if (test_bit(ABS_MT_TRACKING_ID, dev->absbit))
+		mt_slots = dev->absinfo[ABS_MT_TRACKING_ID].maximum -
+			dev->absinfo[ABS_MT_TRACKING_ID].minimum + 1;
+	else if (test_bit(ABS_MT_POSITION_X, dev->absbit))
+		mt_slots = 2;
+	else
+		mt_slots = 0;
+
+	events = mt_slots + 1; /* count SYN_MT_REPORT and SYN_REPORT */
+
+	for (i = 0; i < ABS_CNT; i++) {
+		if (test_bit(i, dev->absbit)) {
+			if (is_mt_axis(i))
+				events += mt_slots;
+			else
+				events++;
+		}
+	}
+
+	for (i = 0; i < REL_CNT; i++)
+		if (test_bit(i, dev->relbit))
+			events++;
+
+	input_set_events_per_packet(dev, events);
+}
+
 #define INPUT_CLEANSE_BITMASK(dev, type, bits)				\
 	do {								\
 		if (!test_bit(EV_##type, dev->evbit))			\

@@ -1784,6 +1827,9 @@ int input_register_device(struct input_dev *dev)
 	const char *path;
 	int error;
 
+	/* Use a larger default input buffer for MT devices */
+	input_set_default_events_per_packet(dev);
+
 	/* Every input device generates EV_SYN/SYN_REPORT events. */
 	__set_bit(EV_SYN, dev->evbit);
 

-- 
1.7.0.4

From: Jeff Brown <redacted>

The hardcoded default is no longer needed because the input core now
calculates an appropriate value when the input device is registered.

Signed-off-by: jeffbrown@android.com
---
 drivers/hid/hid-input.c |    4 ----
 1 files changed, 0 insertions(+), 4 deletions(-)

diff --git a/drivers/hid/hid-input.c b/drivers/hid/hid-input.c
index 33dde87..4b348e0 100644
--- a/drivers/hid/hid-input.c
+++ b/drivers/hid/hid-input.c

@@ -665,10 +665,6 @@ mapped:
 
 		input_abs_set_res(input, usage->code,
 				  hidinput_calc_abs_res(field, usage->code));
-
-		/* use a larger default input buffer for MT devices */
-		if (usage->code == ABS_MT_POSITION_X && input->hint_events_per_packet == 0)
-			input_set_events_per_packet(input, 60);
 	}
 
 	if (usage->type == EV_ABS &&

-- 
1.7.0.4

On SMP systems, it is possible for an evdev client blocked on poll()
to wake up and read events from the evdev ring buffer at the same
rate as they are enqueued.  This can result in high CPU usage,
particularly for MT devices, because the client ends up reading
events one at a time instead of reading complete packets.  This patch
ensures that the client only wakes from poll() when a complete packet
is ready to be read.

Signed-off-by: jeffbrown@android.com
---
 drivers/input/evdev.c |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/drivers/input/evdev.c b/drivers/input/evdev.c
index 203ed70..7b6770d 100644
--- a/drivers/input/evdev.c
+++ b/drivers/input/evdev.c

@@ -73,7 +73,7 @@ static void evdev_pass_event(struct evdev_client *client,
 	}
 	spin_unlock(&client->buffer_lock);
 
-	if (event->type == EV_SYN)
+	if (event->type == EV_SYN && event->code != SYN_MT_REPORT)
 		kill_fasync(&client->fasync, SIGIO, POLL_IN);
 }
 

@@ -103,7 +103,8 @@ static void evdev_event(struct input_handle *handle,
 
 	rcu_read_unlock();
 
-	wake_up_interruptible(&evdev->wait);
+	if (type == EV_SYN && code != SYN_MT_REPORT)
+		wake_up_interruptible(&evdev->wait);
 }
 
 static int evdev_fasync(int fd, struct file *file, int on)

-- 
1.7.0.4

From: Jeff Brown <redacted>

Add a new EV_SYN code, SYN_DROPPED, to inform the client when input
events have been dropped from the evdev input buffer due to a
buffer overrun.  The client should use this event as a hint to
reset its state or ignore all following events until the next
packet begins.

Signed-off-by: jeffbrown@android.com
---
 drivers/input/evdev.c |   18 ++++++++++++------
 include/linux/input.h |    1 +
 2 files changed, 13 insertions(+), 6 deletions(-)

diff --git a/drivers/input/evdev.c b/drivers/input/evdev.c
index 7f42d3a..203ed70 100644
--- a/drivers/input/evdev.c
+++ b/drivers/input/evdev.c

@@ -57,14 +57,20 @@ 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.
+	 * When the client buffer is full, replace the tail with SYN_DROPPED
+	 * to let the client know that events were dropped.  Ensure that the
+	 * head and tail never coincide so the buffer does not appear "empty".
 	 */
 	spin_lock(&client->buffer_lock);
-	do {
-		client->buffer[client->head++] = *event;
-		client->head &= client->bufsize - 1;
-	} while (client->head == client->tail);
+	client->buffer[client->head++] = *event;
+	client->head &= client->bufsize - 1;
+	if (client->head == client->tail) {
+		client->tail = (client->tail + 1) & (client->bufsize - 1);
+		client->buffer[client->tail].time = event->time;
+		client->buffer[client->tail].type = EV_SYN;
+		client->buffer[client->tail].code = SYN_DROPPED;
+		client->buffer[client->tail].value = 0;
+	}
 	spin_unlock(&client->buffer_lock);
 
 	if (event->type == EV_SYN)

diff --git a/include/linux/input.h b/include/linux/input.h
index 056ae8a..65d253e 100644
--- a/include/linux/input.h
+++ b/include/linux/input.h

@@ -167,6 +167,7 @@ struct input_keymap_entry {
 #define SYN_REPORT		0
 #define SYN_CONFIG		1
 #define SYN_MT_REPORT		2
+#define SYN_DROPPED		3
 
 /*
  * Keys and buttons

-- 
1.7.0.4

On Tue, Mar 22, 2011 at 06:04:03PM -0700, Jeff Brown wrote:

From: Jeff Brown <redacted>

Add a new EV_SYN code, SYN_DROPPED, to inform the client when input
events have been dropped from the evdev input buffer due to a
buffer overrun.  The client should use this event as a hint to
reset its state or ignore all following events until the next
packet begins.

I like it.

Do you think this should be unlikely()?

Thanks.

-- 
Dmitry

On Tue, Mar 22, 2011 at 06:04:04PM -0700, Jeff Brown wrote:

On SMP systems, it is possible for an evdev client blocked on poll()
to wake up and read events from the evdev ring buffer at the same
rate as they are enqueued.  This can result in high CPU usage,
particularly for MT devices, because the client ends up reading
events one at a time instead of reading complete packets.  This patch
ensures that the client only wakes from poll() when a complete packet
is ready to be read.

Doesn't this only help with very first packet after a pause in event
stream?

-- 
Dmitry

Hi Jeff,

It looks like this will eventually fill the entire buffer with
SYN_DROPPED events if the client does not catch up.

Thanks,
Henrik

Hi Jeff,

It would be great to get this inline into input/mt.h instead.

This one is a bit iffy - the tracking id is not limited like this in
mainline, looks like android usage. A test againts some arbitrary max
should do it.

Thanks,
Henrik

On Tue, Mar 22, 2011 at 06:04:04PM -0700, Jeff Brown wrote:

It is not clear what should happen at the other SYN events.  Maybe
event->code == SYN_REPORT instead?

Ah, this is a good one. Since the code depends on the same logic being
applied in evdev_pass_event as well, a boolean argument to that
function would be good.

Thanks,
Henrik

My last comment was not right, the SYN_DROPPED is pushed ahead in the
buffer, sorry about that. However, this change does not shrink the
number of buffered elements in case of an overrun, which has been
discussed before as a possibly important feature of the current
code. I would be more comfortable prepending the head with a
SYN_DROPPED, like this:

if (client->head == client->tail) {
	struct input_event drop;

	drop.time = event->time;
	drop.type = EV_SYN;
	drop.code = SYN_DROPPED;
	drop.value = 0;
	client->buffer[client->head++] = drop;
	client->head &= client->bufsize - 1;

	client->buffer[client->head++] = *event;
	client->head &= client->bufsize - 1;
}

The main point is that if we end up having to drop an event, it is
likely we will have to drop the next one, too.

Thanks,
Henrik

It helps with every packet.  I have seen situations where user space
somehow manages to read events faster than the driver enqueues them.

Pseudo-code basic processing loop:

struct input_event buffer[100];
for (;;) {
    poll(...);
    count = read(fd, buffer, sizeof(buffer) / sizeof(buffer[0]));
    process(buffer, count / sizeof(buffer[0]));
}

I've seen cases on a dual-core ARM processor where instead of reading
a block of 71 events all at once, it ends up reading 1 event after
another 71 times.  CPU usage for the reading thread climbs to 35%
whereas it should be less than 5%.

The problem is that poll() wakes up after the first event becomes
available.  So the reader wakes up, promptly reads the event and goes
back to sleep waiting for the next one.  Of course nothing useful
happens until a SYN_REPORT arrives to complete the packet.

Adding a usleep(100) after the poll() is enough to allow the driver
time to finish writing the packet into the evdev ring buffer before
the reader tries to read it.  In that case, we mostly read complete 71
event packets although sometimes the 100us sleep isn't enough so we
end up reading half a packet instead of the whole thing, eg. 28 events
+ 43 events.

Instead it would be better if the poll() didn't wake up until a
complete packet is available for reading all at once.

Jeff.

On Fri, Mar 25, 2011 at 12:49 AM, Dmitry Torokhov
[off-list ref] wrote:

On Tue, Mar 22, 2011 at 06:04:04PM -0700, Jeff Brown wrote:

quoted

On SMP systems, it is possible for an evdev client blocked on poll()
to wake up and read events from the evdev ring buffer at the same
rate as they are enqueued.  This can result in high CPU usage,
particularly for MT devices, because the client ends up reading
events one at a time instead of reading complete packets.  This patch
ensures that the client only wakes from poll() when a complete packet
is ready to be read.

Doesn't this only help with very first packet after a pause in event
stream?

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

quoted

-     if (event->type == EV_SYN)
+     if (event->type == EV_SYN && event->code != SYN_MT_REPORT)

It is not clear what should happen at the other SYN events.  Maybe
event->code == SYN_REPORT instead?

quoted

              kill_fasync(&client->fasync, SIGIO, POLL_IN);
 }

The reasoning here is that we want to wake up (for poll) or signal
(for fasync) the waiters when a complete packet is available.

SYN_CONFIG, SYN_REPORT and the proposed SYN_DROPPED are all
indications of a complete packet being ready or at least an indication
that the reader should do something.  The odd one out is
SYN_MT_REPORT.

quoted

-     wake_up_interruptible(&evdev->wait);
+     if (type == EV_SYN && code != SYN_MT_REPORT)
+             wake_up_interruptible(&evdev->wait);

Ah, this is a good one. Since the code depends on the same logic being
applied in evdev_pass_event as well, a boolean argument to that
function would be good.

I agree.  We could pass a flag to evdev_pass_event to indicate whether
to signal fasync processes that are waiting for data.

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

Hi Henrik,

On Fri, Mar 25, 2011 at 2:02 AM, Henrik Rydberg [off-list ref] wrote:

My last comment was not right, the SYN_DROPPED is pushed ahead in the
buffer, sorry about that. However, this change does not shrink the
number of buffered elements in case of an overrun, which has been
discussed before as a possibly important feature of the current
code. I would be more comfortable prepending the head with a
SYN_DROPPED, like this:

if (client->head == client->tail) {
       struct input_event drop;

       drop.time = event->time;
       drop.type = EV_SYN;
       drop.code = SYN_DROPPED;
       drop.value = 0;
       client->buffer[client->head++] = drop;
       client->head &= client->bufsize - 1;

       client->buffer[client->head++] = *event;
       client->head &= client->bufsize - 1;
}

The main point is that if we end up having to drop an event, it is
likely we will have to drop the next one, too.

I think that's a good idea.  If the client is far behind then we might
as well truncate the buffer as you suggest.  I'll do that.

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

On Fri, Mar 25, 2011 at 1:20 AM, Henrik Rydberg [off-list ref] wrote:

quoted

+static inline bool is_mt_axis(int axis)
+{
+     return axis == ABS_MT_SLOT ||
+             (axis >= ABS_MT_FIRST && axis <= ABS_MT_LAST);
+}

It would be great to get this inline into input/mt.h instead.

Makes sense.  I'll do that.

quoted

+     else if (test_bit(ABS_MT_TRACKING_ID, dev->absbit))
+             mt_slots = dev->absinfo[ABS_MT_TRACKING_ID].maximum -
+                     dev->absinfo[ABS_MT_TRACKING_ID].minimum + 1;

This one is a bit iffy - the tracking id is not limited like this in
mainline, looks like android usage. A test againts some arbitrary max
should do it.

Yeah, I'm not sure about this one.  Tracking ID could effectively have
any range.  All of the MT Protocol A touch screen drivers I have
looked at, assuming they report tracking ids at all, report a
reasonable upper bound on the contact points they support.

Originally, I set an arbitrary maximum bound of 20 slots.  In the
interests of keeping it simple, I decided to remove that bound when I
submitted the patch for review here.

How about:

mt_slots = min(MAX_MT_SLOTS_TO_INFER_FROM_TRACKING_ID_RANGE,
   dev->absinfo[ABS_MT_TRACKING_ID].maximum -
dev->absinfo[ABS_MT_TRACKING_ID].minimum + 1);

Where MAX_MT_SLOTS_TO_INFER_FROM_TRACKING_ID_RANGE is set to 32 or something.

There's also the question of how many slots we should infer when
neither ABS_MT_SLOT or ABS_MT_TRACKING_ID is available.  The drivers
I've seen that don't provide tracking ids, are very basic and tend to
only support 2 touch points.

I guess we could add a DEFAULT_NUMBER_OF_MT_SLOTS constant to handle that case.

Please feel free to suggest better names for these constants.

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

First of all - please do not top post.

On Fri, Mar 25, 2011 at 04:03:18PM -0700, Jeffrey Brown wrote:

It helps with every packet.  I have seen situations where user space
somehow manages to read events faster than the driver enqueues them.

Pseudo-code basic processing loop:

struct input_event buffer[100];
for (;;) {
    poll(...);
    count = read(fd, buffer, sizeof(buffer) / sizeof(buffer[0]));

I hope this is simply a typo in pseudo-code - read takes size in bytes,
not in number of structures.

    process(buffer, count / sizeof(buffer[0]));
}

I've seen cases on a dual-core ARM processor where instead of reading
a block of 71 events all at once, it ends up reading 1 event after
another 71 times.  CPU usage for the reading thread climbs to 35%
whereas it should be less than 5%.

The problem is that poll() wakes up after the first event becomes
available.  So the reader wakes up, promptly reads the event and goes
back to sleep waiting for the next one.  Of course nothing useful
happens until a SYN_REPORT arrives to complete the packet.

Unfortunately your change fixes only first packet, like I mentioned.
Consider the following scenario:

 - input core delivers events, we postpone waking up waiters
   till we get EV_SYN/SYN_REPORT;
 - userspace is waken and consumes entire packet;
 - in the meantime input core delivered 3 more events;
 - userpsace executes poll;
 - kernel adds the process to poll waiters list (poll_wait() call in
   evdev_poll();
 - evdev_poll() checks the condition, sees that there are events and
   signals that the data is ready even though we did not accumulate
   full event packet.

Hence your fix did not reliably fix the issue you are seeing.

Adding a usleep(100) after the poll() is enough to allow the driver
time to finish writing the packet into the evdev ring buffer before
the reader tries to read it.  In that case, we mostly read complete 71
event packets although sometimes the 100us sleep isn't enough so we
end up reading half a packet instead of the whole thing, eg. 28 events
+ 43 events.

Instead it would be better if the poll() didn't wake up until a
complete packet is available for reading all at once.

Unfortunately poll() does not know the intent of userspace program -
will it try to consume the whole event or will it work in poll/read one
event/poll again mode. In this case you really do not want to delay
reading till next EV_SYN comes along.

We might entertain notion of not considering device readable unless
there is a sync event that has not been consumed, but this is
significant change in semantics and we need much more consideration.

Jeff.

On Fri, Mar 25, 2011 at 12:49 AM, Dmitry Torokhov
[off-list ref] wrote:

quoted

On Tue, Mar 22, 2011 at 06:04:04PM -0700, Jeff Brown wrote:

quoted

On SMP systems, it is possible for an evdev client blocked on poll()
to wake up and read events from the evdev ring buffer at the same
rate as they are enqueued.  This can result in high CPU usage,
particularly for MT devices, because the client ends up reading
events one at a time instead of reading complete packets.  This patch
ensures that the client only wakes from poll() when a complete packet
is ready to be read.

Doesn't this only help with very first packet after a pause in event
stream?

--
Dmitry

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

Originally, I set an arbitrary maximum bound of 20 slots.  In the
interests of keeping it simple, I decided to remove that bound when I
submitted the patch for review here.

How about:

mt_slots = min(MAX_MT_SLOTS_TO_INFER_FROM_TRACKING_ID_RANGE,
   dev->absinfo[ABS_MT_TRACKING_ID].maximum -
dev->absinfo[ABS_MT_TRACKING_ID].minimum + 1);

Where MAX_MT_SLOTS_TO_INFER_FROM_TRACKING_ID_RANGE is set to 32 or something.

Sure, 32 works for me.

There's also the question of how many slots we should infer when
neither ABS_MT_SLOT or ABS_MT_TRACKING_ID is available.  The drivers
I've seen that don't provide tracking ids, are very basic and tend to
only support 2 touch points.

There is the bcm5974 driver, but it sets its own limit, so 2 is fine.

I guess we could add a DEFAULT_NUMBER_OF_MT_SLOTS constant to handle that case.

Please feel free to suggest better names for these constants.

With the same interest of keeping it simple in mind, inserting the
actual values is fine. We do not expect to duplicate the decisions
made in this function anywhere else.

Thanks,
Henrik

Hi Dmitry,

On Sun, Mar 27, 2011 at 11:12 PM, Dmitry Torokhov
[off-list ref] wrote:

quoted

    count = read(fd, buffer, sizeof(buffer) / sizeof(buffer[0]));

I hope this is simply a typo in pseudo-code - read takes size in bytes,
not in number of structures.

Definitely a typo.  :)

Unfortunately your change fixes only first packet, like I mentioned.
Consider the following scenario:

 - input core delivers events, we postpone waking up waiters
  till we get EV_SYN/SYN_REPORT;
 - userspace is waken and consumes entire packet;
 - in the meantime input core delivered 3 more events;
 - userpsace executes poll;
 - kernel adds the process to poll waiters list (poll_wait() call in
  evdev_poll();
 - evdev_poll() checks the condition, sees that there are events and
  signals that the data is ready even though we did not accumulate
  full event packet.

Hence your fix did not reliably fix the issue you are seeing.

Ahh, I see what you mean.  As long as the buffer is non-empty, poll()
considers the stream to be readable therefore it does not block.
That's a good thing as otherwise clients that poll() / read() one
event at a time would be broken.

Delaying when we wake waiters is helpful in the common case but as you
point out there still exists a potential degenerate case if the writer
is busy and prevents the reader from ever catching up completely and
blocking when the buffer is empty.  I haven't seen that happen but
it's certainly possible.  In any case, it would be no worse than what
we have now.

We might entertain notion of not considering device readable unless
there is a sync event that has not been consumed, but this is
significant change in semantics and we need much more consideration.

Indeed.  That's why I brought the idea here for discussion.  :)

For maximum compatibility we could define an ioctl to enable new
readability semantics.  Existing clients would retain the old behavior
(device is readable whenever it is non-empty).  I'm not sure this is
really necessary but it might be useful to help diagnose bad drivers
that never write sync packets.

Suppose we adopt the invariant that when new readability semantics are
enabled, clients are only allowed to read events that belong to
complete packets.  That is, they can read events one at a time or in
batches all they like but only up to and including the last sync
event.

Implementing this behavior is straightforward.

Keep track of the end index one past the last readable event in the
ring buffer.  The end index marks the end of the readable portion of
the buffer.  Initially the read index and end index are the same
(zero).  The read index is never allowed to advance past the end
index.  When the read index equals the end index, the device is not
readable.  (Equivalently, the device is only readable when the buffer
contains at least one sync event that has not yet been read.)  When a
sync event (other than SYN_MT_REPORT) is written, advance the end
index past the sync event so that the entire packet becomes readable,
then wake up the waiters because readability may have changed.

How's that sound?

Thanks,
Jeff.
--
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