[PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Henrik Rydberg]

Dmitry,

Please find enclosed the fourth version of the evdev buffer patches.

This version implements buffer locking using event_lock as you
suggested, such that we can proceed with fixing the evdev buffer
problem independently from providing a suitable one-to-many buffer.

The first patch converts the per-client buffers to a common buffer,
and adds a fixme since the code is expected to be further
improved. The second and third patch includes your review comments.

Thanks,
Henrik

---

Henrik Rydberg (3):
  input: evdev: Use multi-reader buffer to save space (rev4)
  input: evdev: Convert to dynamic event buffer (rev4)
  input: Use driver hint to compute the evdev buffer size (rev2)

 drivers/input/evdev.c |   68 +++++++++++++++++++++++++++++++++----------------
 include/linux/input.h |   17 ++++++++++++
 2 files changed, 63 insertions(+), 22 deletions(-)

[PATCH 1/3] input: evdev: Use multi-reader buffer to save space (rev4)

[Henrik Rydberg]

Preparing for larger buffer needs, convert the current per-client
circular buffer to a single buffer with multiple clients. Ideally, there
should be a mechanism where clients wait during buffer collision only.
Meanwhile, let clients take the dev->event_lock, which is already held
during buffer writes.

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>
---
 drivers/input/evdev.c |   46 ++++++++++++++++++++++++++--------------------
 1 files changed, 26 insertions(+), 20 deletions(-)

diff --git a/drivers/input/evdev.c b/drivers/input/evdev.c
index 2ee6c7a..7117589 100644
--- a/drivers/input/evdev.c
+++ b/drivers/input/evdev.c
@@ -33,13 +33,13 @@ struct evdev {
 	spinlock_t client_lock; /* protects client_list */
 	struct mutex mutex;
 	struct device dev;
+	int head;
+	struct input_event buffer[EVDEV_BUFFER_SIZE];
 };
 
 struct evdev_client {
-	struct input_event buffer[EVDEV_BUFFER_SIZE];
 	int head;
 	int tail;
-	spinlock_t buffer_lock; /* protects access to buffer, head and tail */
 	struct fasync_struct *fasync;
 	struct evdev *evdev;
 	struct list_head node;
@@ -48,18 +48,13 @@ struct evdev_client {
 static struct evdev *evdev_table[EVDEV_MINORS];
 static DEFINE_MUTEX(evdev_table_mutex);
 
-static void evdev_pass_event(struct evdev_client *client,
-			     struct input_event *event)
+static inline void evdev_sync_event(struct evdev_client *client,
+				    struct evdev *evdev, int type)
 {
-	/*
-	 * Interrupts are disabled, just acquire the lock
-	 */
-	spin_lock(&client->buffer_lock);
-	client->buffer[client->head++] = *event;
-	client->head &= EVDEV_BUFFER_SIZE - 1;
-	spin_unlock(&client->buffer_lock);
-
-	if (event->type == EV_SYN)
+	/* sync the reader such that it never becomes empty */
+	if (client->tail != evdev->head)
+		client->head = evdev->head;
+	if (type == EV_SYN)
 		kill_fasync(&client->fasync, SIGIO, POLL_IN);
 }
 
@@ -78,14 +73,18 @@ static void evdev_event(struct input_handle *handle,
 	event.code = code;
 	event.value = value;
 
+	/* dev->event_lock held */
+	evdev->buffer[evdev->head] = event;
+	evdev->head = (evdev->head + 1) & (EVDEV_BUFFER_SIZE - 1);
+
 	rcu_read_lock();
 
 	client = rcu_dereference(evdev->grab);
 	if (client)
-		evdev_pass_event(client, &event);
+		evdev_sync_event(client, evdev, type);
 	else
 		list_for_each_entry_rcu(client, &evdev->client_list, node)
-			evdev_pass_event(client, &event);
+			evdev_sync_event(client, evdev, type);
 
 	rcu_read_unlock();
 
@@ -269,7 +268,6 @@ static int evdev_open(struct inode *inode, struct file *file)
 		goto err_put_evdev;
 	}
 
-	spin_lock_init(&client->buffer_lock);
 	client->evdev = evdev;
 	evdev_attach_client(evdev, client);
 
@@ -325,19 +323,27 @@ static ssize_t evdev_write(struct file *file, const char __user *buffer,
 }
 
 static int evdev_fetch_next_event(struct evdev_client *client,
+				  struct evdev *evdev,
 				  struct input_event *event)
 {
+	struct input_dev *dev = evdev->handle.dev;
 	int have_event;
 
-	spin_lock_irq(&client->buffer_lock);
+	/*
+	 * FIXME: taking event_lock protects against reentrant fops
+	 * reads and provides sufficient buffer locking. However,
+	 * clients should not block writes, and having multiple clients
+	 * waiting for each other is suboptimal.
+	 */
+	spin_lock_irq(&dev->event_lock);
 
 	have_event = client->head != client->tail;
 	if (have_event) {
-		*event = client->buffer[client->tail++];
+		*event = evdev->buffer[client->tail++];
 		client->tail &= EVDEV_BUFFER_SIZE - 1;
 	}
 
-	spin_unlock_irq(&client->buffer_lock);
+	spin_unlock_irq(&dev->event_lock);
 
 	return have_event;
 }
@@ -366,7 +372,7 @@ static ssize_t evdev_read(struct file *file, char __user *buffer,
 		return -ENODEV;
 
 	while (retval + input_event_size() <= count &&
-	       evdev_fetch_next_event(client, &event)) {
+	       evdev_fetch_next_event(client, evdev, &event)) {
 
 		if (input_event_to_user(buffer + retval, &event))
 			return -EFAULT;
-- 
1.6.3.3

[PATCH 2/3] input: evdev: Convert to dynamic event buffer (rev4)

[Henrik Rydberg]

Allocate the event buffer dynamically, and prepare to compute the
buffer size in a separate function. This patch defines the size
computation to be identical to the current code, and does not contain
any logical changes.

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>
---
 drivers/input/evdev.c |   23 +++++++++++++++++++----
 1 files changed, 19 insertions(+), 4 deletions(-)

diff --git a/drivers/input/evdev.c b/drivers/input/evdev.c
index 7117589..463bf1b 100644
--- a/drivers/input/evdev.c
+++ b/drivers/input/evdev.c
@@ -10,7 +10,7 @@
 
 #define EVDEV_MINOR_BASE	64
 #define EVDEV_MINORS		32
-#define EVDEV_BUFFER_SIZE	64
+#define EVDEV_MIN_BUFFER_SIZE	64
 
 #include <linux/poll.h>
 #include <linux/sched.h>
@@ -34,7 +34,8 @@ struct evdev {
 	struct mutex mutex;
 	struct device dev;
 	int head;
-	struct input_event buffer[EVDEV_BUFFER_SIZE];
+	unsigned int bufsize;
+	struct input_event *buffer;
 };
 
 struct evdev_client {
@@ -75,7 +76,7 @@ static void evdev_event(struct input_handle *handle,
 
 	/* dev->event_lock held */
 	evdev->buffer[evdev->head] = event;
-	evdev->head = (evdev->head + 1) & (EVDEV_BUFFER_SIZE - 1);
+	evdev->head = (evdev->head + 1) & (evdev->bufsize - 1);
 
 	rcu_read_lock();
 
@@ -122,6 +123,7 @@ static void evdev_free(struct device *dev)
 	struct evdev *evdev = container_of(dev, struct evdev, dev);
 
 	input_put_device(evdev->handle.dev);
+	kfree(evdev->buffer);
 	kfree(evdev);
 }
 
@@ -340,7 +342,7 @@ static int evdev_fetch_next_event(struct evdev_client *client,
 	have_event = client->head != client->tail;
 	if (have_event) {
 		*event = evdev->buffer[client->tail++];
-		client->tail &= EVDEV_BUFFER_SIZE - 1;
+		client->tail &= evdev->bufsize - 1;
 	}
 
 	spin_unlock_irq(&dev->event_lock);
@@ -793,6 +795,11 @@ static void evdev_cleanup(struct evdev *evdev)
 	}
 }
 
+static int evdev_compute_buffer_size(struct input_dev *dev)
+{
+	return EVDEV_MIN_BUFFER_SIZE;
+}
+
 /*
  * Create new evdev device. Note that input core serializes calls
  * to connect and disconnect so we don't need to lock evdev_table here.
@@ -837,6 +844,14 @@ static int evdev_connect(struct input_handler *handler, struct input_dev *dev,
 	evdev->dev.release = evdev_free;
 	device_initialize(&evdev->dev);
 
+	evdev->bufsize = evdev_compute_buffer_size(dev);
+	evdev->buffer = kcalloc(evdev->bufsize, sizeof(struct input_event),
+				GFP_KERNEL);
+	if (!evdev->buffer) {
+		error = -ENOMEM;
+		goto err_free_evdev;
+	}
+
 	error = input_register_handle(&evdev->handle);
 	if (error)
 		goto err_free_evdev;
-- 
1.6.3.3

[PATCH 3/3] input: Use driver hint to compute the evdev buffer size (rev2)

[Henrik Rydberg]

Some devices, in particular MT devices, produce a lot of data.  This
leads to a high frequency of lost packets in evdev, which by default
uses a fairly small event buffer. Let the drivers hint the average
number of events per packet for the device by calling the
input_set_events_per_packet(), and use that information when computing
the evdev buffer size.

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>
---
 drivers/input/evdev.c |    5 ++++-
 include/linux/input.h |   17 +++++++++++++++++
 2 files changed, 21 insertions(+), 1 deletions(-)

diff --git a/drivers/input/evdev.c b/drivers/input/evdev.c
index 463bf1b..2cf7b3a 100644
--- a/drivers/input/evdev.c
+++ b/drivers/input/evdev.c
@@ -11,6 +11,7 @@
 #define EVDEV_MINOR_BASE	64
 #define EVDEV_MINORS		32
 #define EVDEV_MIN_BUFFER_SIZE	64
+#define EVDEV_BUF_PACKETS	8
 
 #include <linux/poll.h>
 #include <linux/sched.h>
@@ -797,7 +798,9 @@ static void evdev_cleanup(struct evdev *evdev)
 
 static int evdev_compute_buffer_size(struct input_dev *dev)
 {
-	return EVDEV_MIN_BUFFER_SIZE;
+	int nev = dev->hint_events_per_packet * EVDEV_BUF_PACKETS;
+	nev = max(nev, EVDEV_MIN_BUFFER_SIZE);
+	return roundup_pow_of_two(nev);
 }
 
 /*
diff --git a/include/linux/input.h b/include/linux/input.h
index bd00786..b2a8a59 100644
--- a/include/linux/input.h
+++ b/include/linux/input.h
@@ -1162,6 +1162,8 @@ struct input_dev {
 	unsigned long ffbit[BITS_TO_LONGS(FF_CNT)];
 	unsigned long swbit[BITS_TO_LONGS(SW_CNT)];
 
+	unsigned int hint_events_per_packet;
+
 	unsigned int keycodemax;
 	unsigned int keycodesize;
 	void *keycode;
@@ -1439,6 +1441,21 @@ static inline void input_mt_slot(struct input_dev *dev, int slot)
 
 void input_set_capability(struct input_dev *dev, unsigned int type, unsigned int code);
 
+/**
+ * input_set_events_per_packet - tell handlers about the driver event rate
+ * @dev: the input device used by the driver
+ * @nev: the average number of events between calls to input_sync()
+ *
+ * If the event rate sent from a device is unusually large, use this
+ * function to set the expected event rate. This will allow handlers
+ * to set up an approriate buffer size for the event stream, in order
+ * to minimize information loss.
+ */
+static inline void input_set_events_per_packet(struct input_dev *dev, int nev)
+{
+	dev->hint_events_per_packet = nev;
+}
+
 static inline void input_set_abs_params(struct input_dev *dev, int axis, int min, int max, int fuzz, int flat)
 {
 	dev->absmin[axis] = min;
-- 
1.6.3.3

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Chase Douglas]

On Sat, 2010-06-05 at 13:04 +0200, Henrik Rydberg wrote:
> Dmitry,
> 
> Please find enclosed the fourth version of the evdev buffer patches.
> 
> This version implements buffer locking using event_lock as you
> suggested, such that we can proceed with fixing the evdev buffer
> problem independently from providing a suitable one-to-many buffer.
> 
> The first patch converts the per-client buffers to a common buffer,
> and adds a fixme since the code is expected to be further
> improved. The second and third patch includes your review comments.
> 
> Thanks,
> Henrik
> 
> ---
> 
> Henrik Rydberg (3):
>   input: evdev: Use multi-reader buffer to save space (rev4)
>   input: evdev: Convert to dynamic event buffer (rev4)
>   input: Use driver hint to compute the evdev buffer size (rev2)
> 
>  drivers/input/evdev.c |   68 +++++++++++++++++++++++++++++++++----------------
>  include/linux/input.h |   17 ++++++++++++
>  2 files changed, 63 insertions(+), 22 deletions(-)

I like the first patch for the simplification of buffer management into
one buffer per device, and I think it may be more efficient due to there
being less locking when syncing the clients.

The second and third patches seem like reasonable solutions to the
buffers being too small for some devices that can handle many MT events
simultaneously and offer many attributes per event.

Acked-by: Chase Douglas <chase.douglas@canonical.com>

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Dmitry Torokhov]

On Saturday, June 05, 2010 04:04:26 am Henrik Rydberg wrote:
> Dmitry,
> 
> Please find enclosed the fourth version of the evdev buffer patches.
> 
> This version implements buffer locking using event_lock as you
> suggested, such that we can proceed with fixing the evdev buffer
> problem independently from providing a suitable one-to-many buffer.
> 
> The first patch converts the per-client buffers to a common buffer,
> and adds a fixme since the code is expected to be further
> improved. The second and third patch includes your review comments.

Henrik,

Applied to .36 queue with minor adjustments, please take a peek in my
'for-linus' branch and see if you spot anything wrong. The changes have
been made with an eye of implementing a per-client event filters which
would again require using private event queues (but only by clients that
request filtering).

The desire for allowing event filtering in kernel is to avoid waking up
HAL-ish processes (ones that only interested in certain special events, 
like KEY_SUSPEND, KEY_WIFI, KEY_MUTE, etc) needlessly. Not sure if I am
going to have time to actually implement it though, anyone wants to
take a stab?

-- 
Dmitry

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Henrik Rydberg]

Dmitry Torokhov wrote:
> On Saturday, June 05, 2010 04:04:26 am Henrik Rydberg wrote:
>> Dmitry,
>>
>> Please find enclosed the fourth version of the evdev buffer patches.
>>
>> This version implements buffer locking using event_lock as you
>> suggested, such that we can proceed with fixing the evdev buffer
>> problem independently from providing a suitable one-to-many buffer.
>>
>> The first patch converts the per-client buffers to a common buffer,
>> and adds a fixme since the code is expected to be further
>> improved. The second and third patch includes your review comments.
> 
> Henrik,
> 
> Applied to .36 queue with minor adjustments, please take a peek in my
> 'for-linus' branch and see if you spot anything wrong.

We are talking about your tree @kernel.org, right? Nothing appeared there...

> The changes have
> been made with an eye of implementing a per-client event filters which
> would again require using private event queues (but only by clients that
> request filtering).

Would not having the separate reader tails suffice? Implementing the filtering
during client read?

> The desire for allowing event filtering in kernel is to avoid waking up
> HAL-ish processes (ones that only interested in certain special events, 
> like KEY_SUSPEND, KEY_WIFI, KEY_MUTE, etc) needlessly. Not sure if I am
> going to have time to actually implement it though, anyone wants to
> take a stab?

I see. Something like a lovely new ioctl() command, setting the evbits on a per
client basis?

Henrik

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Dmitry Torokhov]

On Tue, Jun 15, 2010 at 11:43:13AM +0200, Henrik Rydberg wrote:
> Dmitry Torokhov wrote:
> > On Saturday, June 05, 2010 04:04:26 am Henrik Rydberg wrote:
> >> Dmitry,
> >>
> >> Please find enclosed the fourth version of the evdev buffer patches.
> >>
> >> This version implements buffer locking using event_lock as you
> >> suggested, such that we can proceed with fixing the evdev buffer
> >> problem independently from providing a suitable one-to-many buffer.
> >>
> >> The first patch converts the per-client buffers to a common buffer,
> >> and adds a fixme since the code is expected to be further
> >> improved. The second and third patch includes your review comments.
> > 
> > Henrik,
> > 
> > Applied to .36 queue with minor adjustments, please take a peek in my
> > 'for-linus' branch and see if you spot anything wrong.
> 
> We are talking about your tree @kernel.org, right? Nothing appeared there...
> 

Right, haven't actually pushed yet, queued e-mail leakage ;)

> > The changes have
> > been made with an eye of implementing a per-client event filters which
> > would again require using private event queues (but only by clients that
> > request filtering).
> 
> Would not having the separate reader tails suffice? Implementing the filtering
> during client read?

No, because that would cause waking up the reader thread, which is the
whole goal of the change.

> 
> > The desire for allowing event filtering in kernel is to avoid waking up
> > HAL-ish processes (ones that only interested in certain special events, 
> > like KEY_SUSPEND, KEY_WIFI, KEY_MUTE, etc) needlessly. Not sure if I am
> > going to have time to actually implement it though, anyone wants to
> > take a stab?
> 
> I see. Something like a lovely new ioctl() command, setting the evbits on a per
> client basis?

Yep, exactly.

-- 
Dmitry

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Jiri Kosina]

On Thu, 10 Jun 2010, Dmitry Torokhov wrote:

> > This version implements buffer locking using event_lock as you
> > suggested, such that we can proceed with fixing the evdev buffer
> > problem independently from providing a suitable one-to-many buffer.
> > 
> > The first patch converts the per-client buffers to a common buffer,
> > and adds a fixme since the code is expected to be further
> > improved. The second and third patch includes your review comments.
> 
> Henrik,
> 
> Applied to .36 queue with minor adjustments, please take a peek in my
> 'for-linus' branch and see if you spot anything wrong. 

Hi Dmitry,

I guess you forgot to push it to kernel.org? Last change I see in your 
tree is 6 days old.

Thanks,

-- 
Jiri Kosina
SUSE Labs, Novell Inc.

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Henrik Rydberg]

Jiri Kosina wrote:
> On Thu, 10 Jun 2010, Dmitry Torokhov wrote:
> 
>>> This version implements buffer locking using event_lock as you
>>> suggested, such that we can proceed with fixing the evdev buffer
>>> problem independently from providing a suitable one-to-many buffer.
>>>
>>> The first patch converts the per-client buffers to a common buffer,
>>> and adds a fixme since the code is expected to be further
>>> improved. The second and third patch includes your review comments.
>> Henrik,
>>
>> Applied to .36 queue with minor adjustments, please take a peek in my
>> 'for-linus' branch and see if you spot anything wrong. 
> 
> Hi Dmitry,
> 
> I guess you forgot to push it to kernel.org? Last change I see in your 
> tree is 6 days old.
> 
> Thanks,
> 

... which seems like a lucky strike; the patch has a blatant security hole,
leaking grabbed events to listening clients after ungrab. I sent an updated
patch to Dmitry earlier today, in a brown paper bag. Not knowing if the original
patch was actually applied or not, I thought I had better hold on to the change
just a little bit.

Henrik

Re: [PATCH 0/3] input: evdev: Dynamic buffers (rev4)

[Dmitry Torokhov]

On Wed, Jun 16, 2010 at 06:17:10PM +0200, Henrik Rydberg wrote:
> Jiri Kosina wrote:
> > On Thu, 10 Jun 2010, Dmitry Torokhov wrote:
> > 
> >>> This version implements buffer locking using event_lock as you
> >>> suggested, such that we can proceed with fixing the evdev buffer
> >>> problem independently from providing a suitable one-to-many buffer.
> >>>
> >>> The first patch converts the per-client buffers to a common buffer,
> >>> and adds a fixme since the code is expected to be further
> >>> improved. The second and third patch includes your review comments.
> >> Henrik,
> >>
> >> Applied to .36 queue with minor adjustments, please take a peek in my
> >> 'for-linus' branch and see if you spot anything wrong. 
> > 
> > Hi Dmitry,
> > 
> > I guess you forgot to push it to kernel.org? Last change I see in your 
> > tree is 6 days old.
> > 
> > Thanks,
> > 
> 
> ... which seems like a lucky strike; the patch has a blatant security hole,
> leaking grabbed events to listening clients after ungrab. I sent an updated
> patch to Dmitry earlier today, in a brown paper bag. Not knowing if the original
> patch was actually applied or not, I thought I had better hold on to the change
> just a little bit.
> 

Sorry, just getting back from vacation, the mails escaped when I synced
the mailbox at an airport but I indeed did not push the patcehs out yet.

I should be operable in a day or so and sort everything out.

Thanks.

-- 
Dmitry