mutexes, IPL, tty locking

[David Young]

There is something that confuses me about the TTY locking scheme, and I
wonder if it is a bug in the kernel code or in my expectations?

Consider the following code.  The kernel defies my expectations at line
10, because the IPL is always IPL_HIGH, and at line 11, because the
system panics.

     1  kmutex_t tty_lock, alldevs_mtx;
     2  mutex_init(&tty_lock, MUTEX_DEFAULT, IPL_VM);
     3  mutex_init(&alldevs_mtx, MUTEX_DEFAULT, IPL_HIGH);
       
     4  /* IPL == x */
     5  mutex_enter(&tty_lock);
     6  /* I expect for IPL to be max(x, IPL_VM) */
     7  mutex_enter(&alldevs_mtx);
     8  /* I expect for IPL to be max(x, IPL_HIGH) */
     9  mutex_exit(&alldevs_mtx);
    10  /* I expect for IPL to be max(x, IPL_VM) */
    11  ttysleep(...);  /* panic: cpu_switchto: switching above IPL_SCHED (8) */
    12  mutex_exit(&tty_lock);
    13  /* I expect for IPL to be x */

The sequence of events above will occur if sys/kern/tty.c:ttywait()
calls a driver output routine, (*tp->t_oproc)(tp), that acquires and
releases a mutex such as alldevs_mtx.

Is it more reasonable for the kernel to expect the driver output routine
to restore the IPL, or to expect the tty routines such as ttywait() to
save and restore the IPL across calls to the output routine?

Dave

--
David Young             OJC Technologies
dyoung@...      Urbana, IL * [phone]

[David Laight]

On Wed, Oct 21, 2009 at 01:19:22PM -0500, David Young wrote:

> There is something that confuses me about the TTY locking scheme, and I
> wonder if it is a bug in the kernel code or in my expectations?
>
> Consider the following code.  The kernel defies my expectations at line
> 10, because the IPL is always IPL_HIGH, and at line 11, because the
> system panics.
>
>      1  kmutex_t tty_lock, alldevs_mtx;
>      2  mutex_init(&tty_lock, MUTEX_DEFAULT, IPL_VM);
>      3  mutex_init(&alldevs_mtx, MUTEX_DEFAULT, IPL_HIGH);
>        
>      4  /* IPL == x */
>      5  mutex_enter(&tty_lock);
>      6  /* I expect for IPL to be max(x, IPL_VM) */
>      7  mutex_enter(&alldevs_mtx);
>      8  /* I expect for IPL to be max(x, IPL_HIGH) */

Presumable you mean max(x, IPL_VM, IPL_HIGH) but I guess IPL_HIGH >= IP_VM.

>      9  mutex_exit(&alldevs_mtx);
>     10  /* I expect for IPL to be max(x, IPL_VM) */
>     11  ttysleep(...);  /* panic: cpu_switchto: switching above IPL_SCHED (8) */
>     12  mutex_exit(&tty_lock);
>     13  /* I expect for IPL to be x */

Hmmm.... I wonder where the old IPL is saved ?
(I've not looked to see!)

But the locking scheme ought to support releasing locks in other
that strict reverse order of acquisition. Which rather makes
saving the old IPL anywhere other than in the callers stack frame
rather difficult.

Of course, the above code is releasing in the 'easy' order!

        David

--
David Laight: david@...

[David Holland-6]

On Wed, Oct 21, 2009 at 09:52:35PM +0100, David Laight wrote:
 > But the locking scheme ought to support releasing locks in other
 > that strict reverse order of acquisition. Which rather makes
 > saving the old IPL anywhere other than in the callers stack frame
 > rather difficult.

Not really. My understanding is that somewhere in there there's code
that counts how many times each IPL has been asserted; the current IPL
is thus the highest IPL that's been asserted at least once.

In this case it would seem that the observed behavior is wrong. But
maybe my understanding is inadequate.

--
David A. Holland
dholland@...

[Masao Uebayashi-5]

> Hmmm.... I wonder where the old IPL is saved ?
> (I've not looked to see!)

I see that i386 and mips save the old one in struct cpu_info (ci_mtx_oldspl).

Masao

--
Masao Uebayashi / Tombi Inc. / Tel: [phone]

[Mindaugas Rasiukevicius]

David Laight <david@...> wrote:

> >      9  mutex_exit(&alldevs_mtx);
> >     10  /* I expect for IPL to be max(x, IPL_VM) */
> >     11  ttysleep(...);  /* panic: cpu_switchto: switching above IPL_SCHED
> > (8) */ 12  mutex_exit(&tty_lock);
> >     13  /* I expect for IPL to be x */
>
> Hmmm.... I wonder where the old IPL is saved ?
> (I've not looked to see!)
>
> But the locking scheme ought to support releasing locks in other
> that strict reverse order of acquisition. Which rather makes
> saving the old IPL anywhere other than in the callers stack frame
> rather difficult.

IPL is only being raised and that works in reference counting principle.
Therefore IPL is lowered (and only to IPL_NONE) after the last release,
see ci_mtx_oldspl and ci_mtx_count.  Which means that order of releases
does not matter.  Gradual IPL lowering would unnecessary complicate the
implementation or interface.

Forcing lower IPL with explicit splx() call should work, but that would
be a hack.  While our tty locking should be revamped, the question here
is probably - why alldevs_mtx needs IPL_HIGH?

--
Mindaugas

[David Young]

On Thu, Oct 22, 2009 at 12:32:12PM +0100, Mindaugas Rasiukevicius wrote:

> David Laight <david@...> wrote:
> > >      9  mutex_exit(&alldevs_mtx);
> > >     10  /* I expect for IPL to be max(x, IPL_VM) */
> > >     11  ttysleep(...);  /* panic: cpu_switchto: switching above IPL_SCHED
> > > (8) */ 12  mutex_exit(&tty_lock);
> > >     13  /* I expect for IPL to be x */
> >
> > Hmmm.... I wonder where the old IPL is saved ?
> > (I've not looked to see!)
> >
> > But the locking scheme ought to support releasing locks in other
> > that strict reverse order of acquisition. Which rather makes
> > saving the old IPL anywhere other than in the callers stack frame
> > rather difficult.
>
> IPL is only being raised and that works in reference counting principle.
> Therefore IPL is lowered (and only to IPL_NONE) after the last release,
> see ci_mtx_oldspl and ci_mtx_count.  Which means that order of releases
> does not matter.  Gradual IPL lowering would unnecessary complicate the
> implementation or interface.
>
> Forcing lower IPL with explicit splx() call should work, but that would
> be a hack.  While our tty locking should be revamped, the question here
> is probably - why alldevs_mtx needs IPL_HIGH?

alldevs_mtx will synchronize access to alldevs by both threads and
interrupts, especially interrupts indicating device disconnection
(unplugging FireWire/CardBus/PCMCIA/USB) or bus exceptions (PCI aborts),
which I want to handle at a high priority.

What I really want to know is:

> Is it more reasonable for the kernel to expect the driver output      
> routine to restore the IPL, or to expect the tty routines such as    
> ttywait() to save and restore the IPL across calls to the output      
> routine?                                                              

Yesterday, I thought that it was more reasonable for the tty routines to
save & restore the IPL.  Today, I think that the driver should save &
restore the IPL.  What do you think?

Dave

--
David Young             OJC Technologies
dyoung@...      Urbana, IL * [phone]

[David Laight]

On Thu, Oct 22, 2009 at 10:03:13AM -0500, David Young wrote:
>
> What I really want to know is:
>
> > Is it more reasonable for the kernel to expect the driver output      
> > routine to restore the IPL, or to expect the tty routines such as    
> > ttywait() to save and restore the IPL across calls to the output      
> > routine?                                                              

I think the mutex_exit() should do it - somehow.
Otherwise this will all crop up again and again ...

        David

--
David Laight: david@...

[David Holland-6]

On Thu, Oct 22, 2009 at 12:32:12PM +0100, Mindaugas Rasiukevicius wrote:
 > IPL is only being raised and that works in reference counting principle.
 > Therefore IPL is lowered (and only to IPL_NONE) after the last release,
 > see ci_mtx_oldspl and ci_mtx_count.  Which means that order of releases
 > does not matter.  Gradual IPL lowering would unnecessary complicate the
 > implementation or interface.

Not that much. Here's some strawman code based on what's in one of my
kernels, adapted partly for NetBSD. It isn't tested (and doesn't
compile) but the original form does of course compile, run, and work
in its own environment.

I'm not suggesting that we use this as such (and it would take quite a
bit of work to merge it) but I think the general approach is worth
considering.

   ------ snip ------

/*
 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
 * The President and Fellows of Harvard College.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef _SYS_SPL_H_
#define _SYS_SPL_H_

/*
 * Machine-independent interface to interrupt enable/disable.
 *
 * The number of defined interrupt levels (NIPL) is machine-dependent;
 * each one has an IPL_* symbol whose names must be taken from the
 * following list:
 *      IPL_HALT
 *      IPL_PAUSE
 *      IPL_PREEMPT
 *      IPL_SCHED
 *      IPL_SOFTAUDIO
 *      IPL_SOFTBIO
 *      IPL_SOFTCLOCK
 *      IPL_SOFTDDB
 *      IPL_SOFTFDC
 *      IPL_SOFTNET
 *      IPL_SOFTSERIAL
 *      IPL_VM
 * Additionally, IPL_NONE (always 0) and IPL_HIGH (the highest level)
 * must be defined, and IPL_HIGH should ordinarily be a distinct level
 * of its own and not an alias for one of the others.
 *
 * Each of these levels is asserted by the corresponding spl*
 * function: spl0(), splvm(), splsoftnet(), splhigh(), etc. splx()
 * sets a specific level. All these functions return the prior level.
 *
 * Note that these functions only affect interrupts on the current
 * processor.
 */

#include <sys/cdefs.h>
#include <machine/intr.h>

/*
 * Lower-level functions for explicitly raising and lowering
 * particular interrupt levels. These are used by splx() and by the
 * spinlock code.
 *
 * A previous setting of OLDIPL is cancelled and replaced with NEWIPL.
 *
 * For splraise, NEWIPL > OLDIPL, and for spllower, NEWIPL < OLDIPL.
 */
void splraise(int oldipl, int newipl);
void spllower(int oldipl, int newipl);

////////////////////////////////////////////////////////////

/* Inlining support - for making sure an out-of-line copy gets built */
#ifndef SPL_INLINE
#define SPL_INLINE INLINE
#endif

int splx(int);

#define MKSPL(splname, iplname) \
int splname(void); \
SPL_INLINE \
int \
splname(void) \
{ \
        return splx(iplname); \
}

MKSPL(spl0, IPL_NONE);

#ifdef IPL_HALT
    MKSPL(splhalt, IPL_HALT);
#endif

#ifdef IPL_PAUSE
    MKSPL(splpause, IPL_PAUSE);
#endif

#ifdef IPL_PREEMPT
    MKSPL(splpreempt, IPL_PREEMPT);
#endif

#ifdef IPL_SCHED
    MKSPL(splsched, IPL_SCHED);
#endif

#ifdef IPL_SOFTAUDIO
    MKSPL(splsoftaudio, IPL_SOFTAUDIO);
#endif

#ifdef IPL_SOFTBIO
    MKSPL(splsoftbio, IPL_SOFTBIO);
#endif

#ifdef IPL_SOFTCLOCK
    MKSPL(splsoftclock, IPL_SOFTCLOCK);
#endif

#ifdef IPL_SOFTDDB
    MKSPL(splsoftddb, IPL_SOFTDDB);
#endif

#ifdef IPL_SOFTFDC
    MKSPL(splsoftfdc, IPL_SOFTFDC);
#endif

#ifdef IPL_SOFTNET
    MKSPL(splsoftnet, IPL_SOFTNET);
#endif

#ifdef IPL_SOFTSERIAL
    MKSPL(splsoftserial, IPL_SOFTSERIAL);
#endif

#ifdef IPL_VM
    MKSPL(splvm, IPL_VM);
#endif

MKSPL(splhigh, IPL_HIGH);

#undef MKSPL

#endif /* _SPL_H_ */

   ------ snip ------

/*
 * Copyright (c) 2009
 * The President and Fellows of Harvard College.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/* Make sure to build out-of-line versions of spl inline functions */
#define SPL_INLINE /* empty */

#include <sys/types.h>
#include <sys/spl.h>
#include <sys/proc.h>
/* ... more includes here ... */

/*
 * Machine-independent interrupt handling functions.
 *
 * This code assumes that each port provides NIPL interrupt levels
 * (where NIPL is at least 2) and a function cpu_setipl() that sets
 * the interrupt level in/for the current processor.
 */


/*
 * Raise and lower the interrupt priority level.
 *
 * Each spinlock acquisition can raise and lower the priority level
 * independently. The spl calls also raise and lower the priority
 * level independently of the spinlocks. This is necessary because in
 * general spinlock acquisitions and releases don't nest perfectly,
 * and don't necessarily nest with respect to spl calls either.
 *
 * For example:
 *
 *    struct mutex *red = ..., *blue = ...;
 *    int s;
 *
 *    mutex_enter(red);
 *    s = splhigh();
 *    mutex_enter(blue);
 *    splx(s);
 *    mutex_exit(red);
 *    mutex_exit(blue);
 *
 * In order to make this work we need to count the number of times
 * each interrupt priority level has been raised. Interrupts go off on
 * the first raise, and go on again only on the last lower.
 *
 * curlwp->l_iplcounts[NIPL-1] is used to track this.
 * curlwp->l_highestipl remembers the highest level currently
 * asserted.
 */
void
splraise(int oldspl, int newspl)
{
        struct lwp *cur = curlwp;

        KASSERT(oldspl < newspl);
        KASSERT(oldspl >= 0 && oldspl < NIPL);
        KASSERT(newspl > 0 && newspl < NIPL);

        if (newspl > cur->l_highestipl) {
           cpu_setipl(newspl);
           cur->l_highestipl = newspl;
        }

        if (oldspl > 0) {
           KASSERT(cur->l_iplcounts[oldspl-1] > 0);
           cur->l_iplcounts[oldspl-1]--;
        }
        cur->l_iplcounts[newspl-1]++;
}

void
spllower(int oldspl, int newspl)
{
        struct lwp *cur = curlwp;
        int highest;

        KASSERT(oldspl > newspl);
        KASSERT(oldspl > 0 && oldspl < NIPL);
        KASSERT(newspl >= 0 && newspl < NIPL);

        KASSERT(cur->l_iplcounts[oldspl-1] > 0);
        cur->l_iplcounts[oldspl-1]--;
        if (newspl > 0) {
           cur->l_iplcounts[newspl-1]++;
        }
        highest = cur->l_highestipl;
        KASSERT(oldspl <= highest);
        if (oldspl == highest && cur->l_iplcounts[highest-1] == 0) {
           while (highest > 0 && cur->l_iplcounts[highest-1] == 0) {
              highest--;
           }
           cur->l_highestipl = highest;
           cpu_setipl(highest);
        }
}


/*
 * Disable or enable interrupts and adjust curspl setting. Return old
 * spl level.
 */
int
splx(int spl)
{
        struct lwp *cur = curlwp;
        int ret;

        if (cur->l_curspl < spl) {
                /* turning interrupts off */
                splraise(cur->l_curspl, spl);
                ret = cur->l_curspl;
                cur->l_curspl = spl;
        }
        else if (cur->l_curspl > spl) {
                /* turning interrupts on */
                ret = cur->l_curspl;
                cur->l_curspl = spl;
                spllower(ret, spl);
        }
        else {
                /* do nothing */
                ret = spl;
        }

        return ret;
}

   ------ snip ------

--
David A. Holland
dholland@...

[Mindaugas Rasiukevicius]

David Holland <dholland-tech@...> wrote:
> if (oldspl == highest && cur->l_iplcounts[highest-1] == 0) {
>   while (highest > 0 && cur->l_iplcounts[highest-1] == 0) {
>      highest--;
>   }

It would probably be better to use bitmask and ffs() right here, to avoid
looping through priorities.   Anyway, this is some overhead in low level
primitive to support very rare cases.   I do not think it is worth.  Also,
the case in our TTY locking should be fixed be revamping it (i.e. having
locking in drivers).

--
Mindaugas

[David Holland-6]

On Thu, Oct 29, 2009 at 09:41:12PM +0000, Mindaugas Rasiukevicius wrote:
 > David Holland <dholland-tech@...> wrote:
 > > if (oldspl == highest && cur->l_iplcounts[highest-1] == 0) {
 > >   while (highest > 0 && cur->l_iplcounts[highest-1] == 0) {
 > >      highest--;
 > >   }
 >
 > It would probably be better to use bitmask and ffs() right here, to avoid
 > looping through priorities.

Yes, except that you need the counts. Maintaining a mask as well as
the counts is probably more expensive than executing this loop once in
a while.

 > Anyway, this is some overhead in low level
 > primitive to support very rare cases.   I do not think it is worth.  Also,
 > the case in our TTY locking should be fixed be revamping it (i.e. having
 > locking in drivers).

I'm not sure it's as rare as all that; it just mostly doesn't overtly
fail. Instead you end up silently running at a higher IPL than
necessary, and that buys you longer interrupt latencies and more
dropped packets and all that.

--
David A. Holland
dholland@...

[Mindaugas Rasiukevicius]

David Holland <dholland-tech@...> wrote:
>  > It would probably be better to use bitmask and ffs() right here, to avoid
>  > looping through priorities.
>
> Yes, except that you need the counts. Maintaining a mask as well as
> the counts is probably more expensive than executing this loop once in
> a while.

I doubt it would be more expensive, especially if you have more priorities.
It's something one would benchmark, but see below..

> I'm not sure it's as rare as all that; it just mostly doesn't overtly
> fail. Instead you end up silently running at a higher IPL than
> necessary, and that buys you longer interrupt latencies and more
> dropped packets and all that.

Locks and especially spin-locks should be held for shortest possible time.
If your code blocks interrupts too long, then perhaps it's time to make it
more fine-grained.

And again - looking at our tree, it is optimisation for some tiny percent.
One needs to acquire two (or more) spin-locks with different IPL, release
higher first, and have some significant workload before releasing second.
This is more than rare, rather something what needs improvement. :)

--
Mindaugas

[Masao Uebayashi-5]

> alldevs_mtx will synchronize access to alldevs by both threads and
> interrupts, especially interrupts indicating device disconnection
> (unplugging FireWire/CardBus/PCMCIA/USB) or bus exceptions (PCI aborts),
> which I want to handle at a high priority.

Even if handling those exeptions in the IPL_HIGH interrupt context, you can't
avoid all the inconsistencies in drivers.  What if one thread is about to
access PCI.  Unplug interrupt happens, you execute detach process in IPL_HIGH
interrupt.  Now back to the original thread, it just accesses PCI and you
lose...

In other words, the above situation is not an excuse to make alldevs_mtx
protected with IPL_HIGH.  I think IPL_NONE is just fine.

Masao

--
Masao Uebayashi / Tombi Inc. / Tel: [phone]

[David Young]

On Tue, Nov 03, 2009 at 07:26:25PM +0900, Masao Uebayashi wrote:
> What if one thread is about to
> access PCI.  Unplug interrupt happens, you execute detach process in IPL_HIGH
> interrupt.  Now back to the original thread, it just accesses PCI and you
> lose...

There is a window of time where accesses "in flight" (for example,
posted writes) or an instruction sequence in progress will generate
exceptions.  I plan to deal with those exceptions.  To keep the window
of time manageable, I will service PCI exceptions and device-detachment
notifications at a high priority.

Dave

--
David Young             OJC Technologies
dyoung@...      Urbana, IL * [phone]