Use a 0-sized sentinel to avoid assigning the head ptr from
the driver side thread. This also eliminates testing head/tail
for NULL.

When the sentinel is first 'consumed' by the buffer work
(or by tty_buffer_flush()), it is detached from the list but not
freed nor added to the free list. Both buffer work and
tty_buffer_flush() continue to preserve at least 1 flip buffer
to which head & tail is pointed.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

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: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

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

tty_buffer_find() implements a simple free list lookaside cache.
Merge this functionality into tty_buffer_alloc() to reflect the
more traditional alloc/free symmetry.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Factor shared code; prepare for adding 0-sized sentinel flip buffer.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Since flip buffers are size-aligned to 256 bytes and all flip
buffers 512-bytes or larger are not added to the free list, the
free list only contains 256-byte flip buffers.

Remove the list search when allocating a new flip buffer.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

The char_buf_ptr and flag_buf_ptr values are trivially derived from
the .data field offset; compute values as needed.

Fixes a long-standing type-mismatch with the char and flag ptrs.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Scheduling buffer work on the same cpu as the read() thread
limits the parallelism now possible between the receive_buf path
and the n_tty_read() path.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

The pty driver forces ldisc flow control on, regardless of available
receive buffer space, so the writer can be woken whenever unthrottle
is called. However, this 'forced throttle' has performance
consequences, as multiple atomic operations are necessary to
unthrottle and perform the write wakeup for every input line (in
canonical mode).

Instead, short-circuit the unthrottle if the tty is a pty and perform
the write wakeup directly.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Prepare to special case pty flow control; avoid forward declaration.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Prepare for special handling of pty throttle/unthrottle; factor
flow control into helper functions.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Prepare to factor throttle and unthrottle into helper functions;
relocate chars_in_buffer() to avoid forward declaration.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

No tty driver modifies termios during throttle() or unthrottle().
Therefore, only read safety is required.

However, tty_throttle_safe and tty_unthrottle_safe must still be
mutually exclusive; introduce throttle_mutex for that purpose.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

If the read buffer indices are in the same cache-line, cpus will
contended over the cache-line (so called 'false sharing').

Separate the producer-published fields from the consumer-published
fields; document the locks relevant to each field.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

User-space read() can run concurrently with receiving from device;
waiting for receive_buf() to complete is not required.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

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

lnext escapes the next input character as a literal, and must
be reset when canonical mode changes (to avoid misinterpreting
a special character as a literal if canonical mode is changed
back again).

lnext is specifically not reset on a buffer flush so as to avoid
misinterpreting the next input character as a special character.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

n_tty has a single-producer/single-consumer input model;
use lockless publish instead.

Use termios_rwsem to exclude both consumer and producer while
changing or resetting buffer indices, eg., when flushing. Also,
claim exclusive termios_rwsem to safely retrieve the buffer
indices from a thread other than consumer or producer
(eg., TIOCINQ ioctl).

Note the read_tail is published _after_ clearing the newline
indicator in read_flags to avoid racing the producer.

Drop read_lock spinlock.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

canon_data represented the # of lines which had been copied
to the receive buffer but not yet copied to the user buffer.
The value was tested to determine if input was available in
canonical mode (and also to force input overrun if the
receive buffer was full but a newline had not been received).

However, the actual count was irrelevent; only whether it was
non-zero (meaning 'is there any input to transfer?'). This
shared count is unnecessary and unsafe with a lockless algorithm.
The same check is made by comparing canon_head with read_tail instead.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Use termios_rwsem to guarantee safe access to the termios values.
This is particularly important for N_TTY as changing certain termios
settings alters the mode of operation.

termios_rwsem must be dropped across throttle/unthrottle since
those functions claim the termios_rwsem exclusively (to guarantee
safe access to the termios and for mutual exclusion).
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

termios is commonly accessed unsafely (especially by N_TTY)
because the existing mutex forces exclusive access.
Convert existing usage.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Storing the read_cnt creates an unnecessary shared variable
between the single-producer (n_tty_receive_buf()) and the
single-consumer (n_tty_read()).

Compute read_cnt from head & tail instead of storing.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Wrap read_buf indices (read_head, read_tail, canon_head) at
max representable value, instead of at the N_TTY_BUF_SIZE. This step
is necessary to allow lockless reads of these shared variables
(by updating the variables atomically).
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Prepare for replacing read_cnt field with computed value.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

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

N_TTY .chars_in_buffer() method requires serialized access if
the current thread is not the single-consumer, n_tty_read().

Separate the internal interface; prepare for lockless read-side.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Instead of pushing one char per loop, pre-compute the data length
to copy and copy all at once.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Simplify n_tty_read(); extract complex copy algorithm
into separate function, canon_copy_to_user().
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Although line discipline receiving is single-producer/single-consumer,
using tty->receive_room to manage flow control creates unnecessary
critical regions requiring additional lock use.

Instead, introduce the optional .receive_buf2() ldisc method which
returns the # of bytes actually received. Serialization is guaranteed
by the caller.

In turn, the line discipline should schedule the buffer work item
whenever space becomes available; ie., when there is room to receive
data and receive_room() previously returned 0 (the buffer work
item stops processing if receive_buf2() returns 0). Note the
'no room' state need not be atomic despite concurrent use by two
threads because only the buffer work thread can set the state and
only the read() thread can clear the state.

Add n_tty_receive_buf2() as the receive_buf2() method for N_TTY.
Provide a public helper function, tty_ldisc_receive_buf(), to use
when directly accessing the receive_buf() methods.

Line disciplines not using input flow control can continue to set
tty->receive_room to a fixed value and only provide the receive_buf()
method.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Ldisc interface functions must be called with interrupts enabled.
Separating the ldisc calls into a helper function simplies the
eventual removal of the spinlock.

Note that access to the buf->head ptr outside the spinlock is
safe here because;
* __tty_buffer_flush() is prevented from running while buffer work
  performs i/o,
* tty_buffer_find() only assigns buf->head if the flip buffer list
  is empty (which is never the case in flush_to_ldisc() since at
  least one buffer is always left in the list after use)
Access to the read index outside the spinlock is safe here for the
same reasons.

Update the buffer's read index _after_ the data has been received
by the ldisc.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

tty_set_ldisc() is guaranteed exclusive use of the line discipline
by tty_ldisc_lock_pair_timeout(); shutting off input by resetting
receive_room is unnecessary.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

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

The hangup may already have happened; check for that state also.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Rename o_ldisc to avoid confusion with the ldisc of the
'other' tty.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Line discipline locking was performed with a combination of
a mutex, a status bit, a count, and a waitqueue -- basically,
a rw semaphore.

Replace the existing combination with an ld_semaphore.

Fixes:
 1) the 'reference acquire after ldisc locked' bug
 2) the over-complicated halt mechanism
 3) lock order wrt. tty_lock()
 4) dropping locks while changing ldisc
 5) previously unidentified deadlock while locking ldisc from
    both linked ttys concurrently
 6) previously unidentified recursive deadlocks

Adds much-needed lockdep diagnostics.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Just as the tty pair must be locked in a stable sequence
(ie, independent of which is consider the 'other' tty), so must
the ldisc pair be locked in a stable sequence as well.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

The file scope spinlock identifier, tty_ldisc_lock, will collide
with the file scope lock function tty_ldisc_lock() so rename it.
Signed-off-by: NPeter Hurley <peter@hurleysoftware.com>
Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>

Pull ACPI video support fixes from Rafael Wysocki:
 "I'm sending a separate pull request for this as it may be somewhat
  controversial.  The breakage addressed here is not really new and the
  fixes may not satisfy all users of the affected systems, but we've had
  so much back and forth dance in this area over the last several weeks
  that I think it's time to actually make some progress.

  The source of the problem is that about a year ago we started to tell
  BIOSes that we're compatible with Windows 8, which we really need to
  do, because some systems shipping with Windows 8 are tested with it
  and nothing else, so if we tell their BIOSes that we aren't compatible
  with Windows 8, we expose our users to untested BIOS/AML code paths.

  However, as it turns out, some Windows 8-specific AML code paths are
  not tested either, because Windows 8 actually doesn't use the ACPI
  methods containing them, so if we declare Windows 8 compatibility and
  attempt to use those ACPI methods, things break.  That occurs mostly
  in the backlight support area where in particular the _BCM and _BQC
  methods are plain unusable on some systems if the OS declares Windows
  8 compatibility.

  [ The additional twist is that they actually become usable if the OS
    says it is not compatible with Windows 8, but that may cause
    problems to show up elsewhere ]

  Investigation carried out by Matthew Garrett indicates that what
  Windows 8 does about backlight is to leave backlight control up to
  individual graphics drivers.  At least there's evidence that it does
  that if the Intel graphics driver is used, so we've decided to follow
  Windows 8 in that respect and allow i915 to control backlight (Daniel
  likes that part).

  The first commit from Aaron Lu makes ACPICA export the variable from
  which we can infer whether or not the BIOS believes that we are
  compatible with Windows 8.

  The second commit from Matthew Garrett prepares the ACPI video driver
  by making it initialize the ACPI backlight even if it is not going to
  be used afterward (that is needed for backlight control to work on
  Thinkpads).

  The third commit implements the actual workaround making i915 take
  over backlight control if the firmware thinks it's dealing with
  Windows 8 and is based on the work of multiple developers, including
  Matthew Garrett, Chun-Yi Lee, Seth Forshee, and Aaron Lu.

  The final commit from Aaron Lu makes us follow Windows 8 by informing
  the firmware through the _DOS method that it should not carry out
  automatic brightness changes, so that brightness can be controlled by
  GUI.

  Hopefully, this approach will allow us to avoid using blacklists of
  systems that should not declare Windows 8 compatibility just to avoid
  backlight control problems in the future.

   - Change from Aaron Lu makes ACPICA export a variable which can be
     used by driver code to determine whether or not the BIOS believes
     that we are compatible with Windows 8.

   - Change from Matthew Garrett makes the ACPI video driver initialize
     the ACPI backlight even if it is not going to be used afterward
     (that is needed for backlight control to work on Thinkpads).

   - Fix from Rafael J Wysocki implements Windows 8 backlight support
     workaround making i915 take over bakclight control if the firmware
     thinks it's dealing with Windows 8.  Based on the work of multiple
     developers including Matthew Garrett, Chun-Yi Lee, Seth Forshee,
     and Aaron Lu.

   - Fix from Aaron Lu makes the kernel follow Windows 8 by informing
     the firmware through the _DOS method that it should not carry out
     automatic brightness changes, so that brightness can be controlled
     by GUI"

* tag 'acpi-video-3.11' of git://git.kernel.org/pub/scm/linux/kernel/git/rafael/linux-pm:
  ACPI / video: no automatic brightness changes by win8-compatible firmware
  ACPI / video / i915: No ACPI backlight if firmware expects Windows 8
  ACPI / video: Always call acpi_video_init_brightness() on init
  ACPICA: expose OSI version

Pull ext[34] tmpfile bugfix from Ted Ts'o:
 "Fix regression caused by commit af51a2ac which added ->tmpfile()
  support (along with a similar fix for ext3)"

* tag 'ext4_for_linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tytso/ext4:
  ext3: fix a BUG when opening a file with O_TMPFILE flag
  ext4: fix a BUG when opening a file with O_TMPFILE flag