)]}'
{
  "commit": "23b5c8fa01b723c70a20d6e4ef4ff54c7656d6e1",
  "tree": "d03faad5e19848b35a019793b9a1cbc0bb68a708",
  "parents": [
    "4305ce7894dd38b0633bfc8978437320119223bd"
  ],
  "author": {
    "name": "Paul E. McKenney",
    "email": "paulmck@linux.vnet.ibm.com",
    "time": "Tue Sep 07 10:38:22 2010 -0700"
  },
  "committer": {
    "name": "Paul E. McKenney",
    "email": "paulmck@linux.vnet.ibm.com",
    "time": "Thu May 26 09:42:23 2011 -0700"
  },
  "message": "rcu: Decrease memory-barrier usage based on semi-formal proof\n\n(Note: this was reverted, and is now being re-applied in pieces, with\nthis being the fifth and final piece.  See below for the reason that\nit is now felt to be safe to re-apply this.)\n\nCommit d09b62d fixed grace-period synchronization, but left some smp_mb()\ninvocations in rcu_process_callbacks() that are no longer needed, but\nsheer paranoia prevented them from being removed.  This commit removes\nthem and provides a proof of correctness in their absence.  It also adds\na memory barrier to rcu_report_qs_rsp() immediately before the update to\nrsp-\u003ecompleted in order to handle the theoretical possibility that the\ncompiler or CPU might move massive quantities of code into a lock-based\ncritical section.  This also proves that the sheer paranoia was not\nentirely unjustified, at least from a theoretical point of view.\n\nIn addition, the old dyntick-idle synchronization depended on the fact\nthat grace periods were many milliseconds in duration, so that it could\nbe assumed that no dyntick-idle CPU could reorder a memory reference\nacross an entire grace period.  Unfortunately for this design, the\naddition of expedited grace periods breaks this assumption, which has\nthe unfortunate side-effect of requiring atomic operations in the\nfunctions that track dyntick-idle state for RCU.  (There is some hope\nthat the algorithms used in user-level RCU might be applied here, but\nsome work is required to handle the NMIs that user-space applications\ncan happily ignore.  For the short term, better safe than sorry.)\n\nThis proof assumes that neither compiler nor CPU will allow a lock\nacquisition and release to be reordered, as doing so can result in\ndeadlock.  The proof is as follows:\n\n1.\tA given CPU declares a quiescent state under the protection of\n\tits leaf rcu_node\u0027s lock.\n\n2.\tIf there is more than one level of rcu_node hierarchy, the\n\tlast CPU to declare a quiescent state will also acquire the\n\t-\u003elock of the next rcu_node up in the hierarchy,  but only\n\tafter releasing the lower level\u0027s lock.  The acquisition of this\n\tlock clearly cannot occur prior to the acquisition of the leaf\n\tnode\u0027s lock.\n\n3.\tStep 2 repeats until we reach the root rcu_node structure.\n\tPlease note again that only one lock is held at a time through\n\tthis process.  The acquisition of the root rcu_node\u0027s -\u003elock\n\tmust occur after the release of that of the leaf rcu_node.\n\n4.\tAt this point, we set the -\u003ecompleted field in the rcu_state\n\tstructure in rcu_report_qs_rsp().  However, if the rcu_node\n\thierarchy contains only one rcu_node, then in theory the code\n\tpreceding the quiescent state could leak into the critical\n\tsection.  We therefore precede the update of -\u003ecompleted with a\n\tmemory barrier.  All CPUs will therefore agree that any updates\n\tpreceding any report of a quiescent state will have happened\n\tbefore the update of -\u003ecompleted.\n\n5.\tRegardless of whether a new grace period is needed, rcu_start_gp()\n\twill propagate the new value of -\u003ecompleted to all of the leaf\n\trcu_node structures, under the protection of each rcu_node\u0027s -\u003elock.\n\tIf a new grace period is needed immediately, this propagation\n\twill occur in the same critical section that -\u003ecompleted was\n\tset in, but courtesy of the memory barrier in #4 above, is still\n\tseen to follow any pre-quiescent-state activity.\n\n6.\tWhen a given CPU invokes __rcu_process_gp_end(), it becomes\n\taware of the end of the old grace period and therefore makes\n\tany RCU callbacks that were waiting on that grace period eligible\n\tfor invocation.\n\n\tIf this CPU is the same one that detected the end of the grace\n\tperiod, and if there is but a single rcu_node in the hierarchy,\n\twe will still be in the single critical section.  In this case,\n\tthe memory barrier in step #4 guarantees that all callbacks will\n\tbe seen to execute after each CPU\u0027s quiescent state.\n\n\tOn the other hand, if this is a different CPU, it will acquire\n\tthe leaf rcu_node\u0027s -\u003elock, and will again be serialized after\n\teach CPU\u0027s quiescent state for the old grace period.\n\nOn the strength of this proof, this commit therefore removes the memory\nbarriers from rcu_process_callbacks() and adds one to rcu_report_qs_rsp().\nThe effect is to reduce the number of memory barriers by one and to\nreduce the frequency of execution from about once per scheduling tick\nper CPU to once per grace period.\n\nThis was reverted do to hangs found during testing by Yinghai Lu and\nIngo Molnar.  Frederic Weisbecker supplied Yinghai with tracing that\nlocated the underlying problem, and Frederic also provided the fix.\n\nThe underlying problem was that the HARDIRQ_ENTER() macro from\nlib/locking-selftest.c invoked irq_enter(), which in turn invokes\nrcu_irq_enter(), but HARDIRQ_EXIT() invoked __irq_exit(), which\ndoes not invoke rcu_irq_exit().  This situation resulted in calls\nto rcu_irq_enter() that were not balanced by the required calls to\nrcu_irq_exit().  Therefore, after these locking selftests completed,\nRCU\u0027s dyntick-idle nesting count was a large number (for example,\n72), which caused RCU to to conclude that the affected CPU was not in\ndyntick-idle mode when in fact it was.\n\nRCU would therefore incorrectly wait for this dyntick-idle CPU, resulting\nin hangs.\n\nIn contrast, with Frederic\u0027s patch, which replaces the irq_enter()\nin HARDIRQ_ENTER() with an __irq_enter(), these tests don\u0027t ever call\neither rcu_irq_enter() or rcu_irq_exit(), which works because the CPU\nrunning the test is already marked as not being in dyntick-idle mode.\nThis means that the rcu_irq_enter() and rcu_irq_exit() calls and RCU\nthen has no problem working out which CPUs are in dyntick-idle mode and\nwhich are not.\n\nThe reason that the imbalance was not noticed before the barrier patch\nwas applied is that the old implementation of rcu_enter_nohz() ignored\nthe nesting depth.  This could still result in delays, but much shorter\nones.  Whenever there was a delay, RCU would IPI the CPU with the\nunbalanced nesting level, which would eventually result in rcu_enter_nohz()\nbeing called, which in turn would force RCU to see that the CPU was in\ndyntick-idle mode.\n\nThe reason that very few people noticed the problem is that the mismatched\nirq_enter() vs. __irq_exit() occured only when the kernel was built with\nCONFIG_DEBUG_LOCKING_API_SELFTESTS.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "c078ad48f7a187aa8d76e9885d1776a46a4255e7",
      "old_mode": 33188,
      "old_path": "Documentation/RCU/trace.txt",
      "new_id": "8173cec473aa0099a185d694bad1b1b6ee48743d",
      "new_mode": 33188,
      "new_path": "Documentation/RCU/trace.txt"
    },
    {
      "type": "modify",
      "old_id": "99c6038ad04de61f08969ec3c2825b475b31eb5a",
      "old_mode": 33188,
      "old_path": "kernel/rcutree.c",
      "new_id": "5616b17e4a225d5c61a1f847ee0405149446e0ab",
      "new_mode": 33188,
      "new_path": "kernel/rcutree.c"
    },
    {
      "type": "modify",
      "old_id": "257664815d5d9cdfd645d08f6bd2e873e10a2cff",
      "old_mode": 33188,
      "old_path": "kernel/rcutree.h",
      "new_id": "93d4a1c2e88b2a46c9f0daae78063c953cc49fa6",
      "new_mode": 33188,
      "new_path": "kernel/rcutree.h"
    },
    {
      "type": "modify",
      "old_id": "3f6559a5f5cd7911fac44ac500b670e125e73157",
      "old_mode": 33188,
      "old_path": "kernel/rcutree_plugin.h",
      "new_id": "ed339702481dfc3a7746a10a38cc3309fa82e238",
      "new_mode": 33188,
      "new_path": "kernel/rcutree_plugin.h"
    },
    {
      "type": "modify",
      "old_id": "aa0fd72b4bc714ae3b8f4c41f48f712513e8d6f3",
      "old_mode": 33188,
      "old_path": "kernel/rcutree_trace.c",
      "new_id": "9678cc3650f5e9c8f4e3eb409d26e9c4e784e7d5",
      "new_mode": 33188,
      "new_path": "kernel/rcutree_trace.c"
    }
  ]
}