[PATCH 0/3] HID: debug: fix the ring buffer implementation

[PATCH 0/3] HID: debug: fix the ring buffer implementation

[Vladis Dronov]

This patchset is fixing some aspects of the ring buffer implementation in
drivers/hid/hid-debug.c. This implementation has certain problem points:

- it may stuck in an infinite loop
- it may return corrupted data
- a reader and a writer are not protected by spinlocks, which can lead to
  the corrupted data

The suggested patchset is a new ring buffer implementation which overwrites
the oldest data in case of an overflow. One can verify the suggested ring
buffer implementation by fuzzing it with modified kernel and fuzzer-reader
at: https://gist.github.com/nefigtut/33d56e3870b67493cc867344aed2a062

Vladis Dronov (3):
  HID: debug: avoid infinite loop and corrupting data
  HID: debug: provide reader-writer locking for the ring buffer
  HID: debug: fix ring buffer implementation

 drivers/hid/hid-debug.c   | 201 ++++++++++++++++++++++++++------------
 include/linux/hid-debug.h |   1 +
 2 files changed, 142 insertions(+), 60 deletions(-)

-- 
2.19.0

[PATCH 1/3] HID: debug: avoid infinite loop and corrupting data

[Vladis Dronov]

hid_debug_events_read() does not properly handle the case when tail < head
and count < HID_DEBUG_BUFSIZE - head and returns corrupted data. Also,
after commit 717adfdaf147 ("HID: debug: check length before
copy_to_user()") it can enter an infinite loop if called with count == 0.
Fix this by properly handling this case and adding a check.

Also, the function has "while (ret == 0)" loop which is not needed, remove
it.

Signed-off-by: Vladis Dronov <vdronov@redhat.com>
---
 drivers/hid/hid-debug.c | 109 ++++++++++++++++++++++++----------------
 1 file changed, 65 insertions(+), 44 deletions(-)

diff --git a/drivers/hid/hid-debug.c b/drivers/hid/hid-debug.c
index b48100236df8..20580871b0ec 100644
--- a/drivers/hid/hid-debug.c
+++ b/drivers/hid/hid-debug.c
@@ -722,7 +722,7 @@ void hid_dump_input(struct hid_device *hdev, struct hid_usage *usage, __s32 valu
 	hid_debug_event(hdev, buf);
 
 	kfree(buf);
-        wake_up_interruptible(&hdev->debug_wait);
+	wake_up_interruptible(&hdev->debug_wait);
 
 }
 EXPORT_SYMBOL_GPL(hid_dump_input);
@@ -1112,73 +1112,95 @@ static ssize_t hid_debug_events_read(struct file *file, char __user *buffer,
 	int ret = 0, len;
 	DECLARE_WAITQUEUE(wait, current);
 
-	mutex_lock(&list->read_mutex);
-	while (ret == 0) {
-		if (list->head == list->tail) {
-			add_wait_queue(&list->hdev->debug_wait, &wait);
-			set_current_state(TASK_INTERRUPTIBLE);
+	if (!count)
+		return 0;
 
-			while (list->head == list->tail) {
-				if (file->f_flags & O_NONBLOCK) {
-					ret = -EAGAIN;
-					break;
-				}
-				if (signal_pending(current)) {
-					ret = -ERESTARTSYS;
-					break;
-				}
+	mutex_lock(&list->read_mutex);
+	if (list->head == list->tail) {
+		add_wait_queue(&list->hdev->debug_wait, &wait);
+		set_current_state(TASK_INTERRUPTIBLE);
+
+		while (list->head == list->tail) {
+			if (file->f_flags & O_NONBLOCK) {
+				ret = -EAGAIN;
+				break;
+			}
 
-				if (!list->hdev || !list->hdev->debug) {
-					ret = -EIO;
-					set_current_state(TASK_RUNNING);
-					goto out;
-				}
+			if (signal_pending(current)) {
+				ret = -ERESTARTSYS;
+				break;
+			}
 
-				/* allow O_NONBLOCK from other threads */
-				mutex_unlock(&list->read_mutex);
-				schedule();
-				mutex_lock(&list->read_mutex);
-				set_current_state(TASK_INTERRUPTIBLE);
+			if (!list->hdev || !list->hdev->debug) {
+				ret = -EIO;
+				set_current_state(TASK_RUNNING);
+				goto out;
 			}
 
-			set_current_state(TASK_RUNNING);
-			remove_wait_queue(&list->hdev->debug_wait, &wait);
+			/* allow O_NONBLOCK from other threads */
+			mutex_unlock(&list->read_mutex);
+			schedule();
+			mutex_lock(&list->read_mutex);
+			set_current_state(TASK_INTERRUPTIBLE);
 		}
 
-		if (ret)
-			goto out;
+		set_current_state(TASK_RUNNING);
+		remove_wait_queue(&list->hdev->debug_wait, &wait);
+	}
+
+	if (ret)
+		goto out;
 
-		/* pass the ringbuffer contents to userspace */
+	/* pass the ringbuffer content to userspace */
 copy_rest:
-		if (list->tail == list->head)
-			goto out;
-		if (list->tail > list->head) {
-			len = list->tail - list->head;
-			if (len > count)
-				len = count;
+	if (list->tail == list->head)
+		goto out;
+
+	/* the data from the head to the tail in the buffer is linear */
+	if (list->tail > list->head) {
+		len = list->tail - list->head;
+		if (len > count)
+			len = count;
 
-			if (copy_to_user(buffer + ret, &list->hid_debug_buf[list->head], len)) {
+		if (copy_to_user(buffer + ret,
+		      &list->hid_debug_buf[list->head], len)) {
+			ret = -EFAULT;
+			goto out;
+		}
+		ret += len;
+		list->head += len;
+	} else {
+		len = HID_DEBUG_BUFSIZE - list->head;
+
+		/* the data is split in 2 pieces: from the head to the end of
+		 * the ring buffer and from the start of the ring buffer to the
+		 *  tail. check if we need to copy out only the part between the
+		 * head and the end.
+		 */
+		if (len > count) {
+			len = count;
+
+			if (copy_to_user(buffer,
+			      &list->hid_debug_buf[list->head], len)) {
 				ret = -EFAULT;
 				goto out;
 			}
 			ret += len;
 			list->head += len;
 		} else {
-			len = HID_DEBUG_BUFSIZE - list->head;
-			if (len > count)
-				len = count;
-
-			if (copy_to_user(buffer, &list->hid_debug_buf[list->head], len)) {
+			if (copy_to_user(buffer,
+			      &list->hid_debug_buf[list->head], len)) {
 				ret = -EFAULT;
 				goto out;
 			}
 			list->head = 0;
 			ret += len;
 			count -= len;
+
+			/* check for a corner case when len == count */
 			if (count > 0)
 				goto copy_rest;
 		}
-
 	}
 out:
 	mutex_unlock(&list->read_mutex);
@@ -1256,4 +1278,3 @@ void hid_debug_exit(void)
 {
 	debugfs_remove_recursive(hid_debug_root);
 }
-
-- 
2.19.0

[PATCH 2/3] HID: debug: provide reader-writer locking for the ring buffer

[Vladis Dronov]

hdev->debug_list->hid_debug_buf is not protected from concurrent updates
from the writer, hid_debug_event() and reads by the reader,
hid_debug_events_read(). Fix this by adding per-list-element spinlock.
Also introduce a temporary buffer tempbuf so copy_to_user() is not called
from under a spinlock.

Signed-off-by: Vladis Dronov <vdronov@redhat.com>
---
 drivers/hid/hid-debug.c   | 47 +++++++++++++++++++++++----------------
 include/linux/hid-debug.h |  1 +
 2 files changed, 29 insertions(+), 19 deletions(-)

diff --git a/drivers/hid/hid-debug.c b/drivers/hid/hid-debug.c
index 20580871b0ec..e827784baf1a 100644
--- a/drivers/hid/hid-debug.c
+++ b/drivers/hid/hid-debug.c
@@ -663,15 +663,17 @@ void hid_debug_event(struct hid_device *hdev, char *buf)
 {
 	unsigned i;
 	struct hid_debug_list *list;
-	unsigned long flags;
+	unsigned long flags, flags2;
 
 	spin_lock_irqsave(&hdev->debug_list_lock, flags);
 	list_for_each_entry(list, &hdev->debug_list, node) {
+		spin_lock_irqsave(&list->list_lock, flags2);
 		for (i = 0; buf[i]; i++)
 			list->hid_debug_buf[(list->tail + i) % HID_DEBUG_BUFSIZE] =
 				buf[i];
 		list->tail = (list->tail + i) % HID_DEBUG_BUFSIZE;
-        }
+		spin_unlock_irqrestore(&list->list_lock, flags2);
+	}
 	spin_unlock_irqrestore(&hdev->debug_list_lock, flags);
 
 	wake_up_interruptible(&hdev->debug_wait);
@@ -1095,6 +1097,7 @@ static int hid_debug_events_open(struct inode *inode, struct file *file)
 	}
 	list->hdev = (struct hid_device *) inode->i_private;
 	file->private_data = list;
+	spin_lock_init(&list->list_lock);
 	mutex_init(&list->read_mutex);
 
 	spin_lock_irqsave(&list->hdev->debug_list_lock, flags);
@@ -1109,6 +1112,8 @@ static ssize_t hid_debug_events_read(struct file *file, char __user *buffer,
 		size_t count, loff_t *ppos)
 {
 	struct hid_debug_list *list = file->private_data;
+	char *tmpbuf;
+	unsigned long flags;
 	int ret = 0, len;
 	DECLARE_WAITQUEUE(wait, current);
 
@@ -1151,10 +1156,18 @@ static ssize_t hid_debug_events_read(struct file *file, char __user *buffer,
 	if (ret)
 		goto out;
 
-	/* pass the ringbuffer content to userspace */
+	tmpbuf = kmalloc(min_t(size_t, count, HID_DEBUG_BUFSIZE),
+			 GFP_KERNEL|__GFP_NOWARN);
+	if (!tmpbuf) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	/* lock and copy the ringbuffer content to tmpbuf */
+	spin_lock_irqsave(&list->list_lock, flags);
 copy_rest:
 	if (list->tail == list->head)
-		goto out;
+		goto out_unlock;
 
 	/* the data from the head to the tail in the buffer is linear */
 	if (list->tail > list->head) {
@@ -1162,11 +1174,7 @@ static ssize_t hid_debug_events_read(struct file *file, char __user *buffer,
 		if (len > count)
 			len = count;
 
-		if (copy_to_user(buffer + ret,
-		      &list->hid_debug_buf[list->head], len)) {
-			ret = -EFAULT;
-			goto out;
-		}
+		memcpy(tmpbuf + ret, &list->hid_debug_buf[list->head], len);
 		ret += len;
 		list->head += len;
 	} else {
@@ -1180,19 +1188,11 @@ static ssize_t hid_debug_events_read(struct file *file, char __user *buffer,
 		if (len > count) {
 			len = count;
 
-			if (copy_to_user(buffer,
-			      &list->hid_debug_buf[list->head], len)) {
-				ret = -EFAULT;
-				goto out;
-			}
+			memcpy(tmpbuf, &list->hid_debug_buf[list->head], len);
 			ret += len;
 			list->head += len;
 		} else {
-			if (copy_to_user(buffer,
-			      &list->hid_debug_buf[list->head], len)) {
-				ret = -EFAULT;
-				goto out;
-			}
+			memcpy(tmpbuf, &list->hid_debug_buf[list->head], len);
 			list->head = 0;
 			ret += len;
 			count -= len;
@@ -1202,6 +1202,15 @@ static ssize_t hid_debug_events_read(struct file *file, char __user *buffer,
 				goto copy_rest;
 		}
 	}
+
+out_unlock:
+	spin_unlock_irqrestore(&list->list_lock, flags);
+
+	/* copy out tmpbuf content to userspace */
+	if (ret && copy_to_user(buffer, tmpbuf, ret))
+		ret = -EFAULT;
+	kfree(tmpbuf);
+
 out:
 	mutex_unlock(&list->read_mutex);
 	return ret;
diff --git a/include/linux/hid-debug.h b/include/linux/hid-debug.h
index 8663f216c563..f58665651cb5 100644
--- a/include/linux/hid-debug.h
+++ b/include/linux/hid-debug.h
@@ -45,6 +45,7 @@ struct hid_debug_list {
 	struct fasync_struct *fasync;
 	struct hid_device *hdev;
 	struct list_head node;
+	spinlock_t list_lock;
 	struct mutex read_mutex;
 };
 
-- 
2.19.0

[PATCH 3/3] HID: debug: fix the ring buffer writer implementation

[Vladis Dronov]

ring buffer implementation hid_debug_event() is strange allowing a lost
of data. it does not move head pointer on append and uses per-byte for()
loop. fix this by introducing a new ring buffer implementation, which
overwrites the oldest data in case of the ring buffer overflow. it uses
some calculations for the buffer pointers but only 2 or less memcpy()
calls.

Signed-off-by: Vladis Dronov <vdronov@redhat.com>
---
 drivers/hid/hid-debug.c | 66 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 58 insertions(+), 8 deletions(-)

diff --git a/drivers/hid/hid-debug.c b/drivers/hid/hid-debug.c
index de640e4132c7..63247ac4a9ce 100644
--- a/drivers/hid/hid-debug.c
+++ b/drivers/hid/hid-debug.c
@@ -661,20 +661,70 @@ EXPORT_SYMBOL_GPL(hid_dump_device);
 /* enqueue string to 'events' ring buffer */
 void hid_debug_event(struct hid_device *hdev, char *buf)
 {
-	unsigned i;
 	struct hid_debug_list *list;
-	unsigned long flags, flags2;
+	unsigned long flags1, flags2;
+	unsigned int part1, part2;
+	size_t len;
 
-	spin_lock_irqsave(&hdev->debug_list_lock, flags);
+	if (!buf || !buf[0])
+		return;
+
+	len = strlen(buf);
+
+	spin_lock_irqsave(&hdev->debug_list_lock, flags1);
 	list_for_each_entry(list, &hdev->debug_list, node) {
 		spin_lock_irqsave(&list->list_lock, flags2);
-		for (i = 0; buf[i]; i++)
-			list->hid_debug_buf[(list->tail + i) % HID_DEBUG_BUFSIZE] =
-				buf[i];
-		list->tail = (list->tail + i) % HID_DEBUG_BUFSIZE;
+
+		/* len >= BUFSIZE, copy the last HID_DEBUG_BUFSIZE-1 bytes */
+		if (len > HID_DEBUG_BUFSIZE - 1) {
+			memcpy(list->hid_debug_buf,
+				buf + len - (HID_DEBUG_BUFSIZE - 1),
+				HID_DEBUG_BUFSIZE - 1);
+
+			list->head = 0;
+			list->tail = HID_DEBUG_BUFSIZE - 1;
+		} else {
+			/* append data to the ring buffer */
+			part1 = min_t(size_t, HID_DEBUG_BUFSIZE - list->tail,
+					len);
+			part2 = len - part1;
+
+			memcpy(list->hid_debug_buf + list->tail, buf, part1);
+
+			/* check if head must be moved as the ring is full */
+			if ((list->tail < list->head) &&
+			    (list->tail + part1 >= list->head)) {
+				list->head = list->tail + part1 + 1;
+
+				if (list->head >= HID_DEBUG_BUFSIZE)
+					list->head -= HID_DEBUG_BUFSIZE;
+			}
+
+			/* set tail after the end of appended data */
+			list->tail = list->tail + part1;
+			if (list->tail == HID_DEBUG_BUFSIZE) {
+				list->tail = 0;
+				if (list->head == 0)
+					list->head = 1;
+			}
+
+			/* append the 2nd part of data to the ring */
+			if (part2 > 0) {
+				memcpy(list->hid_debug_buf, buf + part1, part2);
+
+				/* check if head must be moved again as
+				 * the ring is full
+				 */
+				if (list->tail + part2 >= list->head)
+					list->head = list->tail + part2 + 1;
+
+				list->tail = list->tail + part2;
+			}
+		}
+
 		spin_unlock_irqrestore(&list->list_lock, flags2);
 	}
-	spin_unlock_irqrestore(&hdev->debug_list_lock, flags);
+	spin_unlock_irqrestore(&hdev->debug_list_lock, flags1);
 
 	wake_up_interruptible(&hdev->debug_wait);
 }
-- 
2.19.0

Re: [PATCH 0/3] HID: debug: fix the ring buffer implementation

[Jiri Kosina]

On Wed, 3 Oct 2018, Vladis Dronov wrote:

> This patchset is fixing some aspects of the ring buffer implementation in
> drivers/hid/hid-debug.c. This implementation has certain problem points:
> 
> - it may stuck in an infinite loop
> - it may return corrupted data
> - a reader and a writer are not protected by spinlocks, which can lead to
>   the corrupted data
> 
> The suggested patchset is a new ring buffer implementation which overwrites
> the oldest data in case of an overflow. One can verify the suggested ring
> buffer implementation by fuzzing it with modified kernel and fuzzer-reader
> at: https://gist.github.com/nefigtut/33d56e3870b67493cc867344aed2a062

Vladis,

thanks for cleaning it up. I actually like your rewrite quite a lot.

Quick question -- how well was it tested in which scenarios?

-- 
Jiri Kosina
SUSE Labs

Re: [PATCH 0/3] HID: debug: fix the ring buffer implementation

[Vladis Dronov]

Hello, Jiri,

Thank you for the reply and your opinion. It appeared that my own implementation
of a ring buffer was kind of "inventing a wheel", as "kfifo" is already is the
kernel and it may work as a ring buffer quite well. I would like to rewrite my
patchset and use kfifo instead in a new one. Please, ignore this my patchset and
I'll try to submit v2 soon.

This also will answer to "how was it tested" concern, as I believe, kfifo was
quite tested.

Best regards,
Vladis Dronov | Red Hat, Inc. | Product Security Engineer

----- Original Message -----
> From: "Jiri Kosina" <jikos@kernel.org>
> To: "Vladis Dronov" <vdronov@redhat.com>
> Cc: "Benjamin Tissoires" <benjamin.tissoires@redhat.com>, linux-input@vger.kernel.org, linux-kernel@vger.kernel.org
> Sent: Friday, October 26, 2018 5:25:21 PM
> Subject: Re: [PATCH 0/3] HID: debug: fix the ring buffer implementation
> 
> On Wed, 3 Oct 2018, Vladis Dronov wrote:
> 
> > This patchset is fixing some aspects of the ring buffer implementation in
> > drivers/hid/hid-debug.c. This implementation has certain problem points:
> > 
> > - it may stuck in an infinite loop
> > - it may return corrupted data
> > - a reader and a writer are not protected by spinlocks, which can lead to
> >   the corrupted data
> > 
> > The suggested patchset is a new ring buffer implementation which overwrites
> > the oldest data in case of an overflow. One can verify the suggested ring
> > buffer implementation by fuzzing it with modified kernel and fuzzer-reader
> > at: https://gist.github.com/nefigtut/33d56e3870b67493cc867344aed2a062
> 
> Vladis,
> 
> thanks for cleaning it up. I actually like your rewrite quite a lot.
> 
> Quick question -- how well was it tested in which scenarios?
> 
> --
> Jiri Kosina
> SUSE Labs