tty: Use lockless flip buffer free list

In preparation for lockless flip buffers, make the flip buffer
free list lockless.

NB: using llist is not the optimal solution, as the driver and
buffer work may contend over the llist head unnecessarily. However,
test measurements indicate this contention is low.

Signed-off-by: Peter Hurley <peter@hurleysoftware.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

2 files changed, 29 insertions, 2 deletions

diff --git a/include/linux/llist.h b/include/linux/llist.h
index cdaa7f023899..8828a78dec9a 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -125,6 +125,29 @@ static inline void init_llist_head(struct llist_head *list)
              (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
 
 /**
+ * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
+ *                             safe against removal of list entry
+ * @pos:        the type * to use as a loop cursor.
+ * @n:          another type * to use as temporary storage
+ * @node:       the first entry of deleted list entries.
+ * @member:     the name of the llist_node with the struct.
+ *
+ * In general, some entries of the lock-less list can be traversed
+ * safely only after being removed from list, so start with an entry
+ * instead of list head.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ */
+#define llist_for_each_entry_safe(pos, n, node, member)                        \
+        for (pos = llist_entry((node), typeof(*pos), member);                  \
+             &pos->member != NULL &&                                           \
+                (n = llist_entry(pos->member.next, typeof(*n), member), true); \
+             pos = n)
+
+/**
  * llist_empty - tests whether a lock-less list is empty
  * @head:       the list to test
  *
diff --git a/include/linux/tty.h b/include/linux/tty.h
index 87bbaa31ebf5..5043b12f23ea 100644
--- a/include/linux/tty.h
+++ b/include/linux/tty.h
@@ -11,6 +11,7 @@
 #include <linux/tty_flags.h>
 #include <uapi/linux/tty.h>
 #include <linux/rwsem.h>
+#include <linux/llist.h>
 
 
 
@@ -30,7 +31,10 @@
 #define __DISABLED_CHAR '\0'
 
 struct tty_buffer {
-        struct tty_buffer *next;
+        union {
+                struct tty_buffer *next;
+                struct llist_node free;
+        };
         int used;
         int size;
         int commit;
@@ -65,7 +69,7 @@ struct tty_bufhead {
         spinlock_t lock;
         struct tty_buffer *head;        /* Queue head */
         struct tty_buffer *tail;        /* Active buffer */
-        struct tty_buffer *free;        /* Free queue head */
+        struct llist_head free;         /* Free queue head */
         int memory_used;                /* Buffer space used excluding
                                                                 free queue */
 };