lkml.org 
[lkml]   [2006]   [Jul]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC, PATCH, -rt] Early prototype RCU priority-boost patch
    On Fri, Jul 28, 2006 at 07:50:37PM -0700, Bill Huey wrote:
    > On Fri, Jul 28, 2006 at 07:18:29PM -0700, Paul E. McKenney wrote:
    > > On Fri, Jul 28, 2006 at 03:27:16PM -0700, Bill Huey wrote:
    > > > What is that ? like randomly boosting without tracking which thread is
    > > > inside an RCU critical section ?
    > >
    > > Perhaps a better way to put it would be that a thread preempted in
    > > an RCU read-side critical section boosts itself, and tracks the fact
    > > that it boosted itself in its tasks structure.
    > >
    > > The second boost would be from some other task, but if the task had
    > > already boosted itself, the de-boosting would already be taken care of
    > > at the next rcu_read_unlock() -- but as mentioned earlier in this
    > > thread, you only boost someone else if they are not currently running.
    >
    > The problem here is that I can't see how it's going to boost the thread
    > if the things doing the RCU sync can't track the list of readers. It
    > might be record in the trask struct, now what ?

    The first boost is performed by the task itself the first time there
    is a preemption attempt (or the first time it blocks on a mutex), so
    no need to track the list of readers in that case. The trick is that
    there is no benefit to boosting someone who is already running -- we
    only need to boost the first time they are considering blocking.

    If there is a need for a second "boost to the sky" in case of excessively
    delayed grace period (or to provide deterministic synchronize_rcu()
    latency), then we need a list only of those RCU readers who have attempted
    to block at least once thus far in their current RCU read-side critical
    section. But I was putting this off until I get the simple case right.
    Cowardly of me, I know! ;-)

    Finally found Steve Rostedt's PI document (in 2.6.18-rc2), very helpful
    (though I suppose I should reserve judgement until after I get this
    working...)

    > > > > 2. RCU reader boosting a lock holder. This ends up being a
    > > > > combination of #1 (because the act of blocking on a lock implies
    > > > > an "out of nowhere" priority boost) and normal lock boosting.
    > > >
    > > > Lock holder as in mutex held below and RCU critical section ?
    > >
    > > Lock holder as in task 0 holds the lock, perhaps in an RCU read-side
    > > critical section and perhaps not. Task 1 is in an RCU read-side
    > > critical section and attempts to acquire the lock. Task 1 must block,
    > > because task 0 still holds the lock. Task 1 must boost itself before
    > > blocking, and must donate its boosted priority to task 0.
    >
    > Ok (thinking...)
    >
    > > > > 3. A call_rcu() or synchronize_rcu() boosting all readers. I am
    > > > > not sure we really need this, but in case we do... One would
    > > > > need an additional prio_booster for each task to be boosted,
    > > > > right? This would seem to require an additional prio_booster
    > > > > struct in each task structure.
    > > >
    > > > This needs a notion of RCU read side ownership to boost those preempted
    > > > threads.
    > >
    > > I am getting the impression that #3 is something to leave aside for now.
    >
    > ...
    >
    > > The idea is that none of this stuff ever happens except in cases where
    > > the RCU read-side critical section blocks, in which case all this is
    >
    > ...
    >
    > > in the noise compared to the context switch. The sole exception to
    > > this is that rcu_read_unlock() must check to see if it has been boosted,
    > > and deboost itself if so. I don't particularly like the additional
    > > comparison, but it should not be too expensive.
    >
    > Oh, blocks as is gets shoved into a wait queue for a PI enabled lock.

    Yep.

    > > > Don't know what to think about it other than some kind of tracking or
    > > > boosting logic in the per CPU run queue or the task struct itself during
    > > > the boost operation. But you're still stuck with the problem of what
    > > > to boost and how to find that out during an RCU sync side. It's still
    > > > an ownership problem unless Esben can think of another way of getting
    > > > around that problem.
    > >
    > > One idea is to put tasks that block in RCU read-side critical sections
    > > on a list -- again, the hope is that the overhead is in the noise compared
    > > to the context switch.
    >
    > Only way to find out is to try it.

    Or to try without it and see what happens.

    > > > That's why I suggested a priority ceiling or per CPU priority threshold
    > > > tracking (+ CPU binding) the priority of the irq-threads and stuff. It's
    > > > a simple hack to restore the cheesy preempt count stuff without having
    > > > to revert to invasive ownership tracking for each reader.
    > > >
    > > > It's just an idea. Maybe it'll be useful to you.
    > >
    > > Let me make sure I understand what you are suggesting -- sounds to me
    > > like a check in preempt_schedule(). If the task to be preempted is
    > > higher priority than the ceiling, the preemption request is refused.
    > >
    > > Or am I missing part of your proposal?
    >
    > Something like at all preemption points, cond_resched() and friends (scheduler
    > tick) to an additional check against a value in a threads own CPU run queue
    > struct to see if it should permit the preemption or not. I'm thinking about
    > ways to avoid doing an expensive run queue lock during a task's priority
    > manipulation and instead have some other kind of logic orthogonal to that so
    > that it can bypass this overhead. A value in a run queue that can be checked
    > against in order to prevent a preemption from happen might be able to side
    > step the need for a doing a full run queue lock to reorder a tasks priority
    > ranking.
    >
    > If a ceiling or threshold was defined for RCU (another somewhat complicated
    > topic) it could prevent the RCU critical section from preempting other
    > than with other SCHED_FIFO tasks at and above that priority, if you choose
    > a threshold at that priority. That'll be apart of the runtime configuratio
    > of the system. You'd have to cpu_get/put to get that value so that you get
    > at it safely, read or write to it, and maybe save and restore that value on
    > entry and exit respectively. You'll also have to set a field in the task
    > struct to prevent it from migration to another CPU and make sure that's
    > modifying the right stuff on the right CPU.
    >
    > It's a possible solution to a rather difficult problem. What do you think ?
    > too much of a hack ?

    I am not sure -- seems to be a dual approach to boosting the RCU reader's
    priority in the preemption case. I suspect that a real priority boost
    would still be needed in the case where the RCU reader blocks on a mutex,
    since we need the priority inheritance to happen in that case, right?

    > (I'm into -rt development again after a good OLS and I'm trying to get my
    > kernel development up and going so that I can help out)

    Sounds very good!!!

    Thanx, Paul
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2006-07-31 16:41    [W:0.031 / U:91.516 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site