1. 20 Jul, 2011 6 commits
    • Peter Zijlstra's avatar
      softirq,rcu: Inform RCU of irq_exit() activity · ec433f0c
      Peter Zijlstra authored
      The rcu_read_unlock_special() function relies on in_irq() to exclude
      scheduler activity from interrupt level.  This fails because exit_irq()
      can invoke the scheduler after clearing the preempt_count() bits that
      in_irq() uses to determine that it is at interrupt level.  This situation
      can result in failures as follows:
      
       $task			IRQ		SoftIRQ
      
       rcu_read_lock()
      
       /* do stuff */
      
       <preempt> |= UNLOCK_BLOCKED
      
       rcu_read_unlock()
         --t->rcu_read_lock_nesting
      
      			irq_enter();
      			/* do stuff, don't use RCU */
      			irq_exit();
      			  sub_preempt_count(IRQ_EXIT_OFFSET);
      			  invoke_softirq()
      
      					ttwu();
      					  spin_lock_irq(&pi->lock)
      					  rcu_read_lock();
      					  /* do stuff */
      					  rcu_read_unlock();
      					    rcu_read_unlock_special()
      					      rcu_report_exp_rnp()
      					        ttwu()
      					          spin_lock_irq(&pi->lock) /* deadlock */
      
         rcu_read_unlock_special(t);
      
      Ed can simply trigger this 'easy' because invoke_softirq() immediately
      does a ttwu() of ksoftirqd/# instead of doing the in-place softirq stuff
      first, but even without that the above happens.
      
      Cure this by also excluding softirqs from the
      rcu_read_unlock_special() handler and ensuring the force_irqthreads
      ksoftirqd/# wakeup is done from full softirq context.
      
      [ Alternatively, delaying the ->rcu_read_lock_nesting decrement
        until after the special handling would make the thing more robust
        in the face of interrupts as well.  And there is a separate patch
        for that. ]
      
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Reported-and-tested-by: default avatarEd Tomlinson <edt@aei.ca>
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      ec433f0c
    • Peter Zijlstra's avatar
      sched: Add irq_{enter,exit}() to scheduler_ipi() · c5d753a5
      Peter Zijlstra authored
      Ensure scheduler_ipi() calls irq_{enter,exit} when it does some actual
      work. Traditionally we never did any actual work from the resched IPI
      and all magic happened in the return from interrupt path.
      
      Now that we do do some work, we need to ensure irq_{enter,exit} are
      called so that we don't confuse things.
      
      This affects things like timekeeping, NO_HZ and RCU, basically
      everything with a hook in irq_enter/exit.
      
      Explicit examples of things going wrong are:
      
        sched_clock_cpu() -- has a callback when leaving NO_HZ state to take
                          a new reading from GTOD and TSC. Without this
                          callback, time is stuck in the past.
      
        RCU -- needs in_irq() to work in order to avoid some nasty deadlocks
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      c5d753a5
    • Paul E. McKenney's avatar
      rcu: protect __rcu_read_unlock() against scheduler-using irq handlers · 10f39bb1
      Paul E. McKenney authored
      The addition of RCU read-side critical sections within runqueue and
      priority-inheritance lock critical sections introduced some deadlock
      cycles, for example, involving interrupts from __rcu_read_unlock()
      where the interrupt handlers call wake_up().  This situation can cause
      the instance of __rcu_read_unlock() invoked from interrupt to do some
      of the processing that would otherwise have been carried out by the
      task-level instance of __rcu_read_unlock().  When the interrupt-level
      instance of __rcu_read_unlock() is called with a scheduler lock held
      from interrupt-entry/exit situations where in_irq() returns false,
      deadlock can result.
      
      This commit resolves these deadlocks by using negative values of
      the per-task ->rcu_read_lock_nesting counter to indicate that an
      instance of __rcu_read_unlock() is in flight, which in turn prevents
      instances from interrupt handlers from doing any special processing.
      This patch is inspired by Steven Rostedt's earlier patch that similarly
      made __rcu_read_unlock() guard against interrupt-mediated recursion
      (see https://lkml.org/lkml/2011/7/15/326), but this commit refines
      Steven's approach to avoid the need for preemption disabling on the
      __rcu_read_unlock() fastpath and to also avoid the need for manipulating
      a separate per-CPU variable.
      
      This patch avoids need for preempt_disable() by instead using negative
      values of the per-task ->rcu_read_lock_nesting counter.  Note that nested
      rcu_read_lock()/rcu_read_unlock() pairs are still permitted, but they will
      never see ->rcu_read_lock_nesting go to zero, and will therefore never
      invoke rcu_read_unlock_special(), thus preventing them from seeing the
      RCU_READ_UNLOCK_BLOCKED bit should it be set in ->rcu_read_unlock_special.
      This patch also adds a check for ->rcu_read_unlock_special being negative
      in rcu_check_callbacks(), thus preventing the RCU_READ_UNLOCK_NEED_QS
      bit from being set should a scheduling-clock interrupt occur while
      __rcu_read_unlock() is exiting from an outermost RCU read-side critical
      section.
      
      Of course, __rcu_read_unlock() can be preempted during the time that
      ->rcu_read_lock_nesting is negative.  This could result in the setting
      of the RCU_READ_UNLOCK_BLOCKED bit after __rcu_read_unlock() checks it,
      and would also result it this task being queued on the corresponding
      rcu_node structure's blkd_tasks list.  Therefore, some later RCU read-side
      critical section would enter rcu_read_unlock_special() to clean up --
      which could result in deadlock if that critical section happened to be in
      the scheduler where the runqueue or priority-inheritance locks were held.
      
      This situation is dealt with by making rcu_preempt_note_context_switch()
      check for negative ->rcu_read_lock_nesting, thus refraining from
      queuing the task (and from setting RCU_READ_UNLOCK_BLOCKED) if we are
      already exiting from the outermost RCU read-side critical section (in
      other words, we really are no longer actually in that RCU read-side
      critical section).  In addition, rcu_preempt_note_context_switch()
      invokes rcu_read_unlock_special() to carry out the cleanup in this case,
      which clears out the ->rcu_read_unlock_special bits and dequeues the task
      (if necessary), in turn avoiding needless delay of the current RCU grace
      period and needless RCU priority boosting.
      
      It is still illegal to call rcu_read_unlock() while holding a scheduler
      lock if the prior RCU read-side critical section has ever had either
      preemption or irqs enabled.  However, the common use case is legal,
      namely where then entire RCU read-side critical section executes with
      irqs disabled, for example, when the scheduler lock is held across the
      entire lifetime of the RCU read-side critical section.
      Signed-off-by: default avatarPaul E. McKenney <paul.mckenney@linaro.org>
      Signed-off-by: default avatarPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      10f39bb1
    • Paul E. McKenney's avatar
      rcu: Streamline code produced by __rcu_read_unlock() · be0e1e21
      Paul E. McKenney authored
      Given some common flag combinations, particularly -Os, gcc will inline
      rcu_read_unlock_special() despite its being in an unlikely() clause.
      Use noinline to prohibit this misoptimization.
      
      In addition, move the second barrier() in __rcu_read_unlock() so that
      it is not on the common-case code path.  This will allow the compiler to
      generate better code for the common-case path through __rcu_read_unlock().
      Suggested-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      Signed-off-by: default avatarPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      Acked-by: default avatarMathieu Desnoyers <mathieu.desnoyers@efficios.com>
      be0e1e21
    • Paul E. McKenney's avatar
      rcu: Fix RCU_BOOST race handling current->rcu_read_unlock_special · 7765be2f
      Paul E. McKenney authored
      The RCU_BOOST commits for TREE_PREEMPT_RCU introduced an other-task
      write to a new RCU_READ_UNLOCK_BOOSTED bit in the task_struct structure's
      ->rcu_read_unlock_special field, but, as noted by Steven Rostedt, without
      correctly synchronizing all accesses to ->rcu_read_unlock_special.
      This could result in bits in ->rcu_read_unlock_special being spuriously
      set and cleared due to conflicting accesses, which in turn could result
      in deadlocks between the rcu_node structure's ->lock and the scheduler's
      rq and pi locks.  These deadlocks would result from RCU incorrectly
      believing that the just-ended RCU read-side critical section had been
      preempted and/or boosted.  If that RCU read-side critical section was
      executed with either rq or pi locks held, RCU's ensuing (incorrect)
      calls to the scheduler would cause the scheduler to attempt to once
      again acquire the rq and pi locks, resulting in deadlock.  More complex
      deadlock cycles are also possible, involving multiple rq and pi locks
      as well as locks from multiple rcu_node structures.
      
      This commit fixes synchronization by creating ->rcu_boosted field in
      task_struct that is accessed and modified only when holding the ->lock
      in the rcu_node structure on which the task is queued (on that rcu_node
      structure's ->blkd_tasks list).  This results in tasks accessing only
      their own current->rcu_read_unlock_special fields, making unsynchronized
      access once again legal, and keeping the rcu_read_unlock() fastpath free
      of atomic instructions and memory barriers.
      
      The reason that the rcu_read_unlock() fastpath does not need to access
      the new current->rcu_boosted field is that this new field cannot
      be non-zero unless the RCU_READ_UNLOCK_BLOCKED bit is set in the
      current->rcu_read_unlock_special field.  Therefore, rcu_read_unlock()
      need only test current->rcu_read_unlock_special: if that is zero, then
      current->rcu_boosted must also be zero.
      
      This bug does not affect TINY_PREEMPT_RCU because this implementation
      of RCU accesses current->rcu_read_unlock_special with irqs disabled,
      thus preventing races on the !SMP systems that TINY_PREEMPT_RCU runs on.
      Maybe-reported-by: default avatarDave Jones <davej@redhat.com>
      Maybe-reported-by: default avatarSergey Senozhatsky <sergey.senozhatsky@gmail.com>
      Reported-by: default avatarSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: default avatarPaul E. McKenney <paul.mckenney@linaro.org>
      Signed-off-by: default avatarPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      Reviewed-by: default avatarSteven Rostedt <rostedt@goodmis.org>
      7765be2f
    • Paul E. McKenney's avatar
      rcu: decrease rcu_report_exp_rnp coupling with scheduler · 131906b0
      Paul E. McKenney authored
      PREEMPT_RCU read-side critical sections blocking an expedited grace
      period invoke rcu_report_exp_rnp().  When the last such critical section
      has completed, rcu_report_exp_rnp() invokes the scheduler to wake up the
      task that invoked synchronize_rcu_expedited() -- needlessly holding the
      root rcu_node structure's lock while doing so, thus needlessly providing
      a way for RCU and the scheduler to deadlock.
      
      This commit therefore releases the root rcu_node structure's lock before
      calling wake_up().
      Reported-by: default avatarEd Tomlinson <edt@aei.ca>
      Signed-off-by: default avatarPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      131906b0
  2. 13 Jul, 2011 1 commit
  3. 11 Jul, 2011 15 commits
  4. 10 Jul, 2011 9 commits
  5. 09 Jul, 2011 9 commits