)]}'
{
  "log": [
    {
      "commit": "a46e0899eec7a3069bcadd45dfba7bf67c6ed016",
      "tree": "78158b4056fe1365d5086f66769abdc3ef2643c3",
      "parents": [
        "09223371deac67d08ca0b70bd18787920284c967"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Wed Jun 15 15:47:09 2011 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Wed Jun 15 23:07:21 2011 -0700"
      },
      "message": "rcu: use softirq instead of kthreads except when RCU_BOOST\u003dy\n\nThis patch #ifdefs RCU kthreads out of the kernel unless RCU_BOOST\u003dy,\nthus eliminating context-switch overhead if RCU priority boosting has\nnot been configured.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\n"
    },
    {
      "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"
    },
    {
      "commit": "80d02085d99039b3b7f3a73c8896226b0cb1ba07",
      "tree": "c310902423ecb00effadcb59c60cbf118d4037cb",
      "parents": [
        "11c476f31a0fabc6e604da5b09a6590b57c3fb20"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 12 01:08:07 2011 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Thu May 19 23:25:29 2011 +0200"
      },
      "message": "Revert \"rcu: Decrease memory-barrier usage based on semi-formal proof\"\n\nThis reverts commit e59fb3120becfb36b22ddb8bd27d065d3cdca499.\n\nThis reversion was due to (extreme) boot-time slowdowns on SPARC seen by\nYinghai Lu and on x86 by Ingo\n.\nThis is a non-trivial reversion due to intervening commits.\n\nConflicts:\n\n\tDocumentation/RCU/trace.txt\n\tkernel/rcutree.c\n\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "5ece5bab3ed8594ce2c85c6c6e6b82109db36ca7",
      "tree": "c9ef8faa5dbb9e7c82893657e5aa2c1040987f96",
      "parents": [
        "15ba0ba860871cf74b48b1bb47c26c91a66126f3"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Fri Apr 22 18:08:51 2011 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:57 2011 -0700"
      },
      "message": "rcu: Add forward-progress diagnostic for per-CPU kthreads\n\nIncrement a per-CPU counter on each pass through rcu_cpu_kthread()\u0027s\nservice loop, and add it to the rcudata trace output.\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "15ba0ba860871cf74b48b1bb47c26c91a66126f3",
      "tree": "2043eeca7d6df62fc0ae918b61abada073f81415",
      "parents": [
        "a9f4793d8900dc5dc09b3951bdcd4731290e06fe"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Wed Apr 06 16:01:16 2011 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:56 2011 -0700"
      },
      "message": "rcu: add grace-period age and more kthread state to tracing\n\nThis commit adds the age in jiffies of the current grace period along\nwith the duration in jiffies of the longest grace period since boot\nto the rcu/rcugp debugfs file.  It also adds an additional \"O\" state\nto kthread tracing to differentiate between the kthread waiting due to\nhaving nothing to do on the one hand and waiting due to being on the\nwrong CPU on the other hand.\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\n"
    },
    {
      "commit": "4a29865689dbb87a02e3b0fff4a4ae5041273173",
      "tree": "72c9f1641a9fb05e3ae4d8cc068f62f9c566bae9",
      "parents": [
        "d71df90eadfc35aa549ff9a850842673febca71f"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Sun Apr 03 21:33:51 2011 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:56 2011 -0700"
      },
      "message": "rcu: make rcutorture version numbers available through debugfs\n\nIt is not possible to accurately correlate rcutorture output with that\nof debugfs.  This patch therefore adds a debugfs file that prints out\nthe rcutorture version number, permitting easy correlation.\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "d71df90eadfc35aa549ff9a850842673febca71f",
      "tree": "dd275a3f4848784bc6625574341c11befc1b3823",
      "parents": [
        "0ac3d136b2e3cdf1161178223bc5da14a06241d0"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Tue Mar 29 17:48:28 2011 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:56 2011 -0700"
      },
      "message": "rcu: add tracing for RCU\u0027s kthread run states.\n\nAdd tracing to help debugging situations when RCU\u0027s kthreads are not\nrunning but are supposed to be.\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "0ac3d136b2e3cdf1161178223bc5da14a06241d0",
      "tree": "20ba3f20014425404b3dbcb5dfdd4410d87f879a",
      "parents": [
        "2fa218d8bbcff239302f9f36e19d7187077dd636"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Mon Mar 28 15:47:07 2011 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:56 2011 -0700"
      },
      "message": "rcu: add callback-queue information to rcudata output\n\nThis commit adds an indication of the state of the callback queue using\na string of four characters following the \"ql\u003d\" integer queue length.\nThe first character is \"N\" if there are callbacks that have been\nqueued that are not yet ready to be handled by the next grace period, or\n\".\" otherwise.  The second character is \"R\" if there are callbacks queued\nthat are ready to be handled by the next grace period, or \".\" otherwise.\nThe third character is \"W\" if there are callbacks waiting for the current\ngrace period, or \".\" otherwise.  Finally, the fourth character is \"D\"\nif there are callbacks that have been handled by a prior grace period\nand are waiting to be invoked, or \".\".\n\nNote that callbacks that are in the process of being invoked are\nnot shown.  These callbacks would have been removed from the rcu_data\nstructure\u0027s list by rcu_do_batch() prior to being executed.  (These\ncallbacks are also not reflected in the \"ql\u003d\" total, FWIW.)\n\nAlso, document the new callback-queue trace information.\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "0ea1f2ebeb217d38770aebf91c4ecaa8e01b3305",
      "tree": "ef558d2eb804ca033a5166d24f5b4be7cf87727f",
      "parents": [
        "67b98dba474f293c389fc2b7254dcf7c0492e3bd"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Tue Feb 22 13:42:43 2011 -0800"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:55 2011 -0700"
      },
      "message": "rcu: Add boosting to TREE_PREEMPT_RCU tracing\n\nIncludes total number of tasks boosted, number boosted on behalf of each\nof normal and expedited grace periods, and statistics on attempts to\ninitiate boosting that failed for various reasons.\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "12f5f524cafef3ab689929b118f2dfb8bf2be321",
      "tree": "639473556b6edf9b79e0a18d5ba58f80eea76519",
      "parents": [
        "e59fb3120becfb36b22ddb8bd27d065d3cdca499"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paul.mckenney@linaro.org",
        "time": "Mon Nov 29 21:56:39 2010 -0800"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu May 05 23:16:54 2011 -0700"
      },
      "message": "rcu: merge TREE_PREEPT_RCU blocked_tasks[] lists\n\nCombine the current TREE_PREEMPT_RCU -\u003eblocked_tasks[] lists in the\nrcu_node structure into a single -\u003eblkd_tasks list with -\u003egp_tasks\nand -\u003eexp_tasks tail pointers.  This is in preparation for RCU priority\nboosting, which will add a third dimension to the combinatorial explosion\nin the -\u003eblocked_tasks[] case, but simply a third pointer in the new\n-\u003eblkd_tasks case.\n\nAlso update documentation to reflect blocked_tasks[] merge\n\nSigned-off-by: Paul E. McKenney \u003cpaul.mckenney@linaro.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "e59fb3120becfb36b22ddb8bd27d065d3cdca499",
      "tree": "37eaadfe112b64caae943fc7469274bc96553d92",
      "parents": [
        "a00e0d714fbded07a7a2254391ce9ed5a5cb9d82"
      ],
      "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 05 23:16:54 2011 -0700"
      },
      "message": "rcu: Decrease memory-barrier usage based on semi-formal proof\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\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "29494be71afe2a16ad04e344306a620d7cc22d06",
      "tree": "d16a2acd1566be326483d5217d39b78d2ef798c5",
      "parents": [
        "7b27d5475f86186914e54e4a6bb994e9a985337b"
      ],
      "author": {
        "name": "Lai Jiangshan",
        "email": "laijs@cn.fujitsu.com",
        "time": "Wed Oct 20 14:13:06 2010 +0800"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Mon Nov 29 22:01:58 2010 -0800"
      },
      "message": "rcu,cleanup: simplify the code when cpu is dying\n\nWhen we handle the CPU_DYING notifier, the whole system is stopped except\nfor the current CPU.  We therefore need no synchronization with the other\nCPUs.  This allows us to move any orphaned RCU callbacks directly to the\nlist of any online CPU without needing to run them through the global\norphan lists.  These global orphan lists can therefore be dispensed with.\nThis commit makes thes changes, though currently victimizes CPU 0 @@@.\n\nSigned-off-by: Lai Jiangshan \u003claijs@cn.fujitsu.com\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\n"
    },
    {
      "commit": "deb7a41815a8a32d4f9ea2af7a48ed1175222cec",
      "tree": "d5c734642111ae5db356ce7174407f572209c0bb",
      "parents": [
        "e940cc804ec212e483f91167b93d1740c2fd3415"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu Sep 30 21:33:32 2010 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Mon Nov 29 22:01:57 2010 -0800"
      },
      "message": "rcu: get rid of obsolete \"classic\" names in TREE_RCU tracing\n\nThe TREE_RCU tracing had obsolete rcuclassic_trace_init() and\nrcuclassic_trace_cleanup() function names.  This commit brings them\nup to date: rcutree_trace_init() and rcutree_trace_cleanup(),\nrespectively.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\n"
    },
    {
      "commit": "269dcc1c2ec25864308ee03a3fa26ea819d9f5d0",
      "tree": "1c81ee6a9151ab1580628f6e9f85c469ceccb5c0",
      "parents": [
        "0ddea0ead2ced99eaaaddff2beb755381e5c89f8"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Tue Sep 07 14:23:09 2010 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu Sep 23 09:16:53 2010 -0700"
      },
      "message": "rcu: Add tracing data to support queueing models\n\nThe current tracing data is not sufficient to deduce the average time\nthat a callback spends waiting for a grace period to end.  Add three\nper-CPU counters recording the number of callbacks invoked (ci), the\nnumber of callbacks orphaned (co), and the number of callbacks adopted\n(ca).  Given the existing callback queue length (ql), the average wait\ntime in absence of CPU hotplug operations is ql/ci.  The units of wait\ntime will be in terms of the duration over which ci was measured.\n\nIn the presence of CPU hotplug operations, there is room for argument,\nbut ql/(ci-co+ca) won\u0027t steer you too far wrong.\n\nAlso fixes a typo called out by Lucas De Marchi \u003clucas.de.marchi@gmail.com\u003e.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\n"
    },
    {
      "commit": "394f99a9007d4274f7076bb8553ab0ff9707688b",
      "tree": "7d379f91321cec58b87fd5f5089947872689d591",
      "parents": [
        "e546f485e1d7520ca0200502cdcc11b503f4805c"
      ],
      "author": {
        "name": "Lai Jiangshan",
        "email": "laijs@cn.fujitsu.com",
        "time": "Mon Jun 28 16:25:04 2010 +0800"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu Aug 19 17:18:01 2010 -0700"
      },
      "message": "rcu: simplify the usage of percpu data\n\n\u0026percpu_data is compatible with allocated percpu data.\n\nAnd we use it and remove the \"-\u003erda[NR_CPUS]\" array, saving significant\nstorage on systems with large numbers of CPUs.  This does add an additional\nlevel of indirection and thus an additional cache line referenced, but\nbecause -\u003erda is not used on the read side, this is OK.\n\nSigned-off-by: Lai Jiangshan \u003claijs@cn.fujitsu.com\u003e\nReviewed-by: Tejun Heo \u003ctj@kernel.org\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "d21670acab9fcb4bc74a40b68a6941059234c55c",
      "tree": "6a4c054bc4dbadf0524b4e221889a8da558dbdaf",
      "parents": [
        "4a90a0681cf6cd21cd444184302aa045156486b3"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Wed Apr 14 17:39:26 2010 -0700"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Mon May 10 11:08:35 2010 -0700"
      },
      "message": "rcu: reduce the number of spurious RCU_SOFTIRQ invocations\n\nLai Jiangshan noted that up to 10% of the RCU_SOFTIRQ are spurious, and\ntraced this down to the fact that the current grace-period machinery\nwill uselessly raise RCU_SOFTIRQ when a given CPU needs to go through\na quiescent state, but has not yet done so.  In this situation, there\nmight well be nothing that RCU_SOFTIRQ can do, and the overhead can be\nworth worrying about in the ksoftirqd case.  This patch therefore avoids\nraising RCU_SOFTIRQ in this situation.\n\nChanges since v1 (http://lkml.org/lkml/2010/3/30/122 from Lai Jiangshan):\n\no\tOmit the rcu_qs_pending() prechecks, as they aren\u0027t that\n\tmuch less expensive than the quiescent-state checks.\n\no\tMerge with the set_need_resched() patch that reduces IPIs.\n\no\tAdd the new n_rp_report_qs field to the rcu_pending tracing output.\n\no\tUpdate the tracing documentation accordingly.\n\nSigned-off-by: Lai Jiangshan \u003claijs@cn.fujitsu.com\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\n"
    },
    {
      "commit": "20133cfce7d0bbdcc0c398301030c091f5675c88",
      "tree": "337f242bfc89f5880cf86234fa6b574f52a2f0a5",
      "parents": [
        "1bd22e374b20c2f0ba1d2723c1f585acab2251c5"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Mon Feb 22 17:05:01 2010 -0800"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Thu Feb 25 10:34:57 2010 +0100"
      },
      "message": "rcu: Stop overflowing signed integers\n\nThe C standard does not specify the result of an operation that\noverflows a signed integer, so such operations need to be\navoided.  This patch changes the type of several fields from\n\"long\" to \"unsigned long\" and adjusts operations as needed.\nULONG_CMP_GE() and ULONG_CMP_LT() macros are introduced to do\nthe modular comparisons that are appropriate given that overflow\nis an expected event.\n\nAcked-by: Mathieu Desnoyers \u003cmathieu.desnoyers@efficios.com\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: mathieu.desnoyers@polymtl.ca\nCc: josh@joshtriplett.org\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: Valdis.Kletnieks@vt.edu\nCc: dhowells@redhat.com\nLKML-Reference: \u003c1266887105-1528-17-git-send-email-paulmck@linux.vnet.ibm.com\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "d9a3da0699b24a589b27a61e1a5b5bd30d9db669",
      "tree": "f7440e396a6c818f3cef514ccc31ab55d88025ef",
      "parents": [
        "cf244dc01bf68e1ad338b82447f8686d24ea4435"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Wed Dec 02 12:10:15 2009 -0800"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Thu Dec 03 11:35:25 2009 +0100"
      },
      "message": "rcu: Add expedited grace-period support for preemptible RCU\n\nImplement an synchronize_rcu_expedited() for preemptible RCU\nthat actually is expedited.  This uses\nsynchronize_sched_expedited() to force all threads currently\nrunning in a preemptible-RCU read-side critical section onto the\nappropriate -\u003eblocked_tasks[] list, then takes a snapshot of all\nof these lists and waits for them to drain.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: mathieu.desnoyers@polymtl.ca\nCc: josh@joshtriplett.org\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: Valdis.Kletnieks@vt.edu\nCc: dhowells@redhat.com\nLKML-Reference: \u003c1259784616158-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "3397e040dfacbb303498ced1baa96be983dcea06",
      "tree": "a88622259699c066756c0ed62caa7218ca5b79ef",
      "parents": [
        "019129d595caaa5bd0b41d128308da1be6a91869"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Wed Oct 14 16:36:38 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Thu Oct 15 11:20:22 2009 +0200"
      },
      "message": "rcu: Add rnp-\u003eblocked_tasks to tracing\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: mathieu.desnoyers@polymtl.ca\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: Valdis.Kletnieks@vt.edu\nCc: dhowells@redhat.com\nCc: npiggin@suse.de\nCc: jens.axboe@oracle.com\nCc: Josh Triplett \u003cjosh@joshtriplett.org\u003e\nLKML-Reference: \u003c20091014233638.GE6763@linux.vnet.ibm.com\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n kernel/rcutree_trace.c |    8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n"
    },
    {
      "commit": "e74f4c4564455c91a3b4075bb1721993c2a95dda",
      "tree": "213f9df0974c6e1e729de207b2c6dd942a39ba8c",
      "parents": [
        "d0ec774cb2599c858be9d923bb873cf6697520d8"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Tue Oct 06 21:48:17 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Wed Oct 07 08:11:20 2009 +0200"
      },
      "message": "rcu: Make hot-unplugged CPU relinquish its own RCU callbacks\n\nThe current interaction between RCU and CPU hotplug requires that\nRCU block in CPU notifiers waiting for callbacks to drain.\n\nThis can be greatly simplified by having each CPU relinquish its\nown callbacks, and for both _rcu_barrier() and CPU_DEAD notifiers\nto adopt all callbacks that were previously relinquished.\n\nThis change also eliminates the possibility of certain types of\nhangs due to the previous practice of waiting for callbacks to be\ninvoked from within CPU notifiers.  If you don\u0027t every wait, you\ncannot hang.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josh@joshtriplett.org\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: Valdis.Kletnieks@vt.edu\nCc: dhowells@redhat.com\nLKML-Reference: \u003c1254890898456-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "9b2619aff0332e95ea5eb7a0d75b0208818d871c",
      "tree": "a1aed182c4f1ec511352c0e3cb3eba0e20535263",
      "parents": [
        "1eba8f84380bede3c602bd7758dea96925cead01"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Wed Sep 23 09:50:43 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Wed Sep 23 19:46:30 2009 +0200"
      },
      "message": "rcu: Clean up code to address Ingo\u0027s checkpatch feedback\n\nMove declarations and update storage classes to make checkpatch happy.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josh@joshtriplett.org\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: Valdis.Kletnieks@vt.edu\nCc: dhowells@redhat.com\nLKML-Reference: \u003c12537246441701-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "a71fca58b7f4abca551ae2256ac08dd9123a03f9",
      "tree": "55bef0550ff2558a117d768426474e15b081ff4b",
      "parents": [
        "49e291266d0920264471d9d64268fb030e33a99a"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Fri Sep 18 10:28:19 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Sat Sep 19 08:53:22 2009 +0200"
      },
      "message": "rcu: Fix whitespace inconsistencies\n\nFix a number of whitespace ^Ierrors in the include/linux/rcu*\nand the kernel/rcu* files.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josh@joshtriplett.org\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: Valdis.Kletnieks@vt.edu\nLKML-Reference: \u003c20090918172819.GA24405@linux.vnet.ibm.com\u003e\n[ did more checkpatch fixlets ]\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "f41d911f8c49a5d65c86504c19e8204bb605c4fd",
      "tree": "59bcd3048652ef290b3e19d2904409afd5c90eb3",
      "parents": [
        "a157229cabd6dd8cfa82525fc9bf730c94cc9ac2"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Sat Aug 22 13:56:52 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Sun Aug 23 10:32:40 2009 +0200"
      },
      "message": "rcu: Merge preemptable-RCU functionality into hierarchical RCU\n\nCreate a kernel/rcutree_plugin.h file that contains definitions\nfor preemptable RCU (or, under the #else branch of the #ifdef,\nempty definitions for the classic non-preemptable semantics).\nThese definitions fit into plugins defined in kernel/rcutree.c\nfor this purpose.\n\nThis variant of preemptable RCU uses a new algorithm whose\nread-side expense is roughly that of classic hierarchical RCU\nunder CONFIG_PREEMPT. This new algorithm\u0027s update-side expense\nis similar to that of classic hierarchical RCU, and, in absence\nof read-side preemption or blocking, is exactly that of classic\nhierarchical RCU.  Perhaps more important, this new algorithm\nhas a much simpler implementation, saving well over 1,000 lines\nof code compared to mainline\u0027s implementation of preemptable\nRCU, which will hopefully be retired in favor of this new\nalgorithm.\n\nThe simplifications are obtained by maintaining per-task\nnesting state for running tasks, and using a simple\nlock-protected algorithm to handle accounting when tasks block\nwithin RCU read-side critical sections, making use of lessons\nlearned while creating numerous user-level RCU implementations\nover the past 18 months.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josht@linux.vnet.ibm.com\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nLKML-Reference: \u003c12509746134003-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "22f00b69f6a7e1e18e821979a23e8307c2de9888",
      "tree": "692adbe758da2d52aac9d564b6fd55363aa2fbf6",
      "parents": [
        "65cf8f866fc0fb40fa9daaded7e938a886d6f7c5"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Sat Aug 22 13:56:50 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Sun Aug 23 10:32:39 2009 +0200"
      },
      "message": "rcu: Use debugfs_remove_recursive() simplify code.\n\nSuggested by Josh Triplett.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josht@linux.vnet.ibm.com\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nCc: \"Paul E. McKenney\" \u003cpaulmck@linux.vnet.ibm.com\u003e\nLKML-Reference: \u003c12509746132173-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "5699ed8fcb0c32ca699e2a27ad716eb70b367dbf",
      "tree": "69f0a831c48edd3a389da165b8afeba5139adfec",
      "parents": [
        "bc33f24bdca8b6e97376e3a182ab69e6cdefa989"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Sat Aug 22 13:56:48 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Sun Aug 23 10:32:38 2009 +0200"
      },
      "message": "rcu: Fix online/offline indication for rcudata.csv trace file\n\nThe heading said \"Online?\", but the column had \"Y\" for offline\nCPUs and \"N\" for online CPUs.  Swap the \"Y\" and \"N\" to match\nthe heading.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josht@linux.vnet.ibm.com\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nLKML-Reference: \u003c12509746132841-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "d6714c22b43fbcbead7e7b706ff270e15f04a791",
      "tree": "1dc15e57d982351bed45b7b9768a118f86b88c19",
      "parents": [
        "9f77da9f40045253e91f55c12d4481254b513d2d"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Sat Aug 22 13:56:46 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Sun Aug 23 10:32:37 2009 +0200"
      },
      "message": "rcu: Renamings to increase RCU clarity\n\nMake RCU-sched, RCU-bh, and RCU-preempt be underlying\nimplementations, with \"RCU\" defined in terms of one of the\nthree.  Update the outdated rcu_qsctr_inc() names, as these\nfunctions no longer increment anything.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josht@linux.vnet.ibm.com\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nLKML-Reference: \u003c12509746132696-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "9f77da9f40045253e91f55c12d4481254b513d2d",
      "tree": "8699c413d1493855ca8b1205e1b63090f568af42",
      "parents": [
        "b560d8ad8583803978aaaeba50ef29dc8e97a610"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Sat Aug 22 13:56:45 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Sun Aug 23 10:32:36 2009 +0200"
      },
      "message": "rcu: Move private definitions from include/linux/rcutree.h to kernel/rcutree.h\n\nSome information hiding that makes it easier to merge\npreemptability into rcutree without descending into #include\nhell.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: laijs@cn.fujitsu.com\nCc: dipankar@in.ibm.com\nCc: akpm@linux-foundation.org\nCc: mathieu.desnoyers@polymtl.ca\nCc: josht@linux.vnet.ibm.com\nCc: dvhltc@us.ibm.com\nCc: niv@us.ibm.com\nCc: peterz@infradead.org\nCc: rostedt@goodmis.org\nLKML-Reference: \u003c1250974613373-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "7ba5c840e64d4a967379f1ae3eca73278180b11d",
      "tree": "b77d70ce2b80f3be27add39fcd3bc7fbfe7a0847",
      "parents": [
        "05cfbd66d07c44865983c8b65ae9d0037d874206"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Mon Apr 13 21:31:17 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Tue Apr 14 11:33:43 2009 +0200"
      },
      "message": "rcu: Add __rcu_pending tracing to hierarchical RCU\n\nAdd tracing to __rcu_pending() to provide information on why RCU\nprocessing was kicked off.  This is helpful for debugging hierarchical\nRCU, and might also be helpful in learning how hierarchical RCU operates.\n\nLocated-by: Anton Blanchard \u003canton@au1.ibm.com\u003e\nTested-by: Anton Blanchard \u003canton@au1.ibm.com\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: anton@samba.org\nCc: akpm@linux-foundation.org\nCc: dipankar@in.ibm.com\nCc: manfred@colorfullife.com\nCc: cl@linux-foundation.org\nCc: josht@linux.vnet.ibm.com\nCc: schamp@sgi.com\nCc: niv@us.ibm.com\nCc: dvhltc@us.ibm.com\nCc: ego@in.ibm.com\nCc: laijs@cn.fujitsu.com\nCc: rostedt@goodmis.org\nCc: peterz@infradead.org\nCc: penberg@cs.helsinki.fi\nCc: andi@firstfloor.org\nCc: \"Paul E. McKenney\" \u003cpaulmck@linux.vnet.ibm.com\u003e\nLKML-Reference: \u003c1239683479943-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "ef631b0ca01655d24e9ca7e199262c4a46416a26",
      "tree": "0ef86d5b97c6e2de500e639ebb92da8f2ec8c863",
      "parents": [
        "27b19565fe4ca5b0e9d2ae98ce4b81ca728bf445"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Mon Apr 13 21:31:16 2009 -0700"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Tue Apr 14 11:31:50 2009 +0200"
      },
      "message": "rcu: Make hierarchical RCU less IPI-happy\n\nThis patch fixes a hierarchical-RCU performance bug located by Anton\nBlanchard.  The problem stems from a misguided attempt to provide a\nwork-around for jiffies-counter failure.  This work-around uses a per-CPU\nn_rcu_pending counter, which is incremented on each call to rcu_pending(),\nwhich in turn is called from each scheduling-clock interrupt.  Each CPU\nthen treats this counter as a surrogate for the jiffies counter, so\nthat if the jiffies counter fails to advance, the per-CPU n_rcu_pending\ncounter will cause RCU to invoke force_quiescent_state(), which in turn\nwill (among other things) send resched IPIs to CPUs that have thus far\nfailed to pass through an RCU quiescent state.\n\nUnfortunately, each CPU resets only its own counter after sending a\nbatch of IPIs.  This means that the other CPUs will also (needlessly)\nsend -another- round of IPIs, for a full N-squared set of IPIs in the\nworst case every three scheduler-clock ticks until the grace period\nfinally ends.  It is not reasonable for a given CPU to reset each and\nevery n_rcu_pending for all the other CPUs, so this patch instead simply\ndisables the jiffies-counter \"training wheels\", thus eliminating the\nexcessive IPIs.\n\nNote that the jiffies-counter IPIs do not have this problem due to\nthe fact that the jiffies counter is global, so that the CPU sending\nthe IPIs can easily reset things, thus preventing the other CPUs from\nsending redundant IPIs.\n\nNote also that the n_rcu_pending counter remains, as it will continue to\nbe used for tracing.  It may also see use to update the jiffies counter,\nshould an appropriate kick-the-jiffies-counter API appear.\n\nLocated-by: Anton Blanchard \u003canton@au1.ibm.com\u003e\nTested-by: Anton Blanchard \u003canton@au1.ibm.com\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: anton@samba.org\nCc: akpm@linux-foundation.org\nCc: dipankar@in.ibm.com\nCc: manfred@colorfullife.com\nCc: cl@linux-foundation.org\nCc: josht@linux.vnet.ibm.com\nCc: schamp@sgi.com\nCc: niv@us.ibm.com\nCc: dvhltc@us.ibm.com\nCc: ego@in.ibm.com\nCc: laijs@cn.fujitsu.com\nCc: rostedt@goodmis.org\nCc: peterz@infradead.org\nCc: penberg@cs.helsinki.fi\nCc: andi@firstfloor.org\nCc: \"Paul E. McKenney\" \u003cpaulmck@linux.vnet.ibm.com\u003e\nLKML-Reference: \u003c12396834793575-git-send-email-\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "6258c4fb59e77d748f7efc2c137ad420372edd07",
      "tree": "c1e2ae0f027e81e55613b043ce44965858475d59",
      "parents": [
        "b1f77b0581b8fd837acb4a973f7d5496cae6efee"
      ],
      "author": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Wed Mar 25 16:42:24 2009 +0100"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Fri Apr 03 12:23:03 2009 +0200"
      },
      "message": "kmemtrace, rcu: fix rcu_tree_trace.c data structure dependencies\n\nImpact: cleanup\n\nWe want to remove rcutree internals from the public rcutree.h file for\nupcoming kmemtrace changes - but kernel/rcutree_trace.c depends on them.\n\nIntroduce kernel/rcutree.h for internal definitions. (Probably all\nthe other data types from include/linux/rcutree.h could be\nmoved here too - except rcu_data.)\n\nCc: Pekka Enberg \u003cpenberg@cs.helsinki.fi\u003e\nCc: Eduard - Gabriel Munteanu \u003ceduard.munteanu@linux360.ro\u003e\nCc: paulmck@linux.vnet.ibm.com\nLKML-Reference: \u003c1237898630.25315.83.camel@penberg-laptop\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    },
    {
      "commit": "64db4cfff99c04cd5f550357edcc8780f96b54a2",
      "tree": "4856e788d21f0e31ed78a22b70b4521f7237705e",
      "parents": [
        "d110ec3a1e1f522e2e9dfceb9c36d6590c26d2d4"
      ],
      "author": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu Dec 18 21:55:32 2008 +0100"
      },
      "committer": {
        "name": "Ingo Molnar",
        "email": "mingo@elte.hu",
        "time": "Thu Dec 18 21:56:04 2008 +0100"
      },
      "message": "\"Tree RCU\": scalable classic RCU implementation\n\nThis patch fixes a long-standing performance bug in classic RCU that\nresults in massive internal-to-RCU lock contention on systems with\nmore than a few hundred CPUs.  Although this patch creates a separate\nflavor of RCU for ease of review and patch maintenance, it is intended\nto replace classic RCU.\n\nThis patch still handles stress better than does mainline, so I am still\ncalling it ready for inclusion.  This patch is against the -tip tree.\nNevertheless, experience on an actual 1000+ CPU machine would still be\nmost welcome.\n\nMost of the changes noted below were found while creating an rcutiny\n(which should permit ejecting the current rcuclassic) and while doing\ndetailed line-by-line documentation.\n\nUpdates from v9 (http://lkml.org/lkml/2008/12/2/334):\n\no\tFixes from remainder of line-by-line code walkthrough,\n\tincluding comment spelling, initialization, undesirable\n\tnarrowing due to type conversion, removing redundant memory\n\tbarriers, removing redundant local-variable initialization,\n\tand removing redundant local variables.\n\n\tI do not believe that any of these fixes address the CPU-hotplug\n\tissues that Andi Kleen was seeing, but please do give it a whirl\n\tin case the machine is smarter than I am.\n\n\tA writeup from the walkthrough may be found at the following\n\tURL, in case you are suffering from terminal insomnia or\n\tmasochism:\n\n\thttp://www.kernel.org/pub/linux/kernel/people/paulmck/tmp/rcutree-walkthrough.2008.12.16a.pdf\n\no\tMade rcutree tracing use seq_file, as suggested some time\n\tago by Lai Jiangshan.\n\no\tAdded a .csv variant of the rcudata debugfs trace file, to allow\n\tpeople having thousands of CPUs to drop the data into\n\ta spreadsheet.\tTested with oocalc and gnumeric.  Updated\n\tdocumentation to suit.\n\nUpdates from v8 (http://lkml.org/lkml/2008/11/15/139):\n\no\tFix a theoretical race between grace-period initialization and\n\tforce_quiescent_state() that could occur if more than three\n\tjiffies were required to carry out the grace-period\n\tinitialization.  Which it might, if you had enough CPUs.\n\no\tApply Ingo\u0027s printk-standardization patch.\n\no\tSubstitute local variables for repeated accesses to global\n\tvariables.\n\no\tFix comment misspellings and redundant (but harmless) increments\n\tof -\u003en_rcu_pending (this latter after having explicitly added it).\n\no\tApply checkpatch fixes.\n\nUpdates from v7 (http://lkml.org/lkml/2008/10/10/291):\n\no\tFixed a number of problems noted by Gautham Shenoy, including\n\tthe cpu-stall-detection bug that he was having difficulty\n\tconvincing me was real.  ;-)\n\no\tChanged cpu-stall detection to wait for ten seconds rather than\n\tthree in order to reduce false positive, as suggested by Ingo\n\tMolnar.\n\no\tProduced a design document (http://lwn.net/Articles/305782/).\n\tThe act of writing this document uncovered a number of both\n\ttheoretical and \"here and now\" bugs as noted below.\n\no\tFix dynticks_nesting accounting confusion, simplify WARN_ON()\n\tcondition, fix kerneldoc comments, and add memory barriers\n\tin dynticks interface functions.\n\no\tAdd more data to tracing.\n\no\tRemove unused \"rcu_barrier\" field from rcu_data structure.\n\no\tCount calls to rcu_pending() from scheduling-clock interrupt\n\tto use as a surrogate timebase should jiffies stop counting.\n\no\tFix a theoretical race between force_quiescent_state() and\n\tgrace-period initialization.  Yes, initialization does have to\n\tgo on for some jiffies for this race to occur, but given enough\n\tCPUs...\n\nUpdates from v6 (http://lkml.org/lkml/2008/9/23/448):\n\no\tFix a number of checkpatch.pl complaints.\n\no\tApply review comments from Ingo Molnar and Lai Jiangshan\n\ton the stall-detection code.\n\no\tFix several bugs in !CONFIG_SMP builds.\n\no\tFix a misspelled config-parameter name so that RCU now announces\n\tat boot time if stall detection is configured.\n\no\tRun tests on numerous combinations of configurations parameters,\n\twhich after the fixes above, now build and run correctly.\n\nUpdates from v5 (http://lkml.org/lkml/2008/9/15/92, bad subject line):\n\no\tFix a compiler error in the !CONFIG_FANOUT_EXACT case (blew a\n\tchangeset some time ago, and finally got around to retesting\n\tthis option).\n\no\tFix some tracing bugs in rcupreempt that caused incorrect\n\ttotals to be printed.\n\no\tI now test with a more brutal random-selection online/offline\n\tscript (attached).  Probably more brutal than it needs to be\n\ton the people reading it as well, but so it goes.\n\no\tA number of optimizations and usability improvements:\n\n\to\tMake rcu_pending() ignore the grace-period timeout when\n\t\tthere is no grace period in progress.\n\n\to\tMake force_quiescent_state() avoid going for a global\n\t\tlock in the case where there is no grace period in\n\t\tprogress.\n\n\to\tRearrange struct fields to improve struct layout.\n\n\to\tMake call_rcu() initiate a grace period if RCU was\n\t\tidle, rather than waiting for the next scheduling\n\t\tclock interrupt.\n\n\to\tInvoke rcu_irq_enter() and rcu_irq_exit() only when\n\t\tidle, as suggested by Andi Kleen.  I still don\u0027t\n\t\tcompletely trust this change, and might back it out.\n\n\to\tMake CONFIG_RCU_TRACE be the single config variable\n\t\tmanipulated for all forms of RCU, instead of the prior\n\t\tconfusion.\n\n\to\tDocument tracing files and formats for both rcupreempt\n\t\tand rcutree.\n\nUpdates from v4 for those missing v5 given its bad subject line:\n\no\tSeparated dynticks interface so that NMIs and irqs call separate\n\tfunctions, greatly simplifying it.  In particular, this code\n\tno longer requires a proof of correctness.  ;-)\n\no\tSeparated dynticks state out into its own per-CPU structure,\n\tavoiding the duplicated accounting.\n\no\tThe case where a dynticks-idle CPU runs an irq handler that\n\tinvokes call_rcu() is now correctly handled, forcing that CPU\n\tout of dynticks-idle mode.\n\no\tReview comments have been applied (thank you all!!!).\n\tFor but one example, fixed the dynticks-ordering issue that\n\tManfred pointed out, saving me much debugging.  ;-)\n\no\tAdjusted rcuclassic and rcupreempt to handle dynticks changes.\n\nAttached is an updated patch to Classic RCU that applies a hierarchy,\ngreatly reducing the contention on the top-level lock for large machines.\nThis passes 10-hour concurrent rcutorture and online-offline testing on\n128-CPU ppc64 without dynticks enabled, and exposes some timekeeping\nbugs in presence of dynticks (exciting working on a system where\n\"sleep 1\" hangs until interrupted...), which were fixed in the\n2.6.27 kernel.  It is getting more reliable than mainline by some\nmeasures, so the next version will be against -tip for inclusion.\nSee also Manfred Spraul\u0027s recent patches (or his earlier work from\n2004 at http://marc.info/?l\u003dlinux-kernel\u0026m\u003d108546384711797\u0026w\u003d2).\nWe will converge onto a common patch in the fullness of time, but are\ncurrently exploring different regions of the design space.  That said,\nI have already gratefully stolen quite a few of Manfred\u0027s ideas.\n\nThis patch provides CONFIG_RCU_FANOUT, which controls the bushiness\nof the RCU hierarchy.  Defaults to 32 on 32-bit machines and 64 on\n64-bit machines.  If CONFIG_NR_CPUS is less than CONFIG_RCU_FANOUT,\nthere is no hierarchy.  By default, the RCU initialization code will\nadjust CONFIG_RCU_FANOUT to balance the hierarchy, so strongly NUMA\narchitectures may choose to set CONFIG_RCU_FANOUT_EXACT to disable\nthis balancing, allowing the hierarchy to be exactly aligned to the\nunderlying hardware.  Up to two levels of hierarchy are permitted\n(in addition to the root node), allowing up to 16,384 CPUs on 32-bit\nsystems and up to 262,144 CPUs on 64-bit systems.  I just know that I\nam going to regret saying this, but this seems more than sufficient\nfor the foreseeable future.  (Some architectures might wish to set\nCONFIG_RCU_FANOUT\u003d4, which would limit such architectures to 64 CPUs.\nIf this becomes a real problem, additional levels can be added, but I\ndoubt that it will make a significant difference on real hardware.)\n\nIn the common case, a given CPU will manipulate its private rcu_data\nstructure and the rcu_node structure that it shares with its immediate\nneighbors.  This can reduce both lock and memory contention by multiple\norders of magnitude, which should eliminate the need for the strange\nmanipulations that are reported to be required when running Linux on\nvery large systems.\n\nSome shortcomings:\n\no\tMore bugs will probably surface as a result of an ongoing\n\tline-by-line code inspection.\n\n\tPatches will be provided as required.\n\no\tThere are probably hangs, rcutorture failures, \u0026c.  Seems\n\tquite stable on a 128-CPU machine, but that is kind of small\n\tcompared to 4096 CPUs.  However, seems to do better than\n\tmainline.\n\n\tPatches will be provided as required.\n\no\tThe memory footprint of this version is several KB larger\n\tthan rcuclassic.\n\n\tA separate UP-only rcutiny patch will be provided, which will\n\treduce the memory footprint significantly, even compared\n\tto the old rcuclassic.  One such patch passes light testing,\n\tand has a memory footprint smaller even than rcuclassic.\n\tInitial reaction from various embedded guys was \"it is not\n\tworth it\", so am putting it aside.\n\nCredits:\n\no\tManfred Spraul for ideas, review comments, and bugs spotted,\n\tas well as some good friendly competition.  ;-)\n\no\tJosh Triplett, Ingo Molnar, Peter Zijlstra, Mathieu Desnoyers,\n\tLai Jiangshan, Andi Kleen, Andy Whitcroft, and Andrew Morton\n\tfor reviews and comments.\n\no\tThomas Gleixner for much-needed help with some timer issues\n\t(see patches below).\n\no\tJon M. Tollefson, Tim Pepper, Andrew Theurer, Jose R. Santos,\n\tAndy Whitcroft, Darrick Wong, Nishanth Aravamudan, Anton\n\tBlanchard, Dave Kleikamp, and Nathan Lynch for keeping machines\n\talive despite my heavy abuse^Wtesting.\n\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n"
    }
  ]
}