)]}'
{
  "commit": "643b52b9c0b4e959436b4b551ebf4060d06d5ae8",
  "tree": "5ccce7688ba638e863a391ca84441d081e666f99",
  "parents": [
    "d2187ebd84c7dd13ef269e9600f4daebeb02816e"
  ],
  "author": {
    "name": "Nick Piggin",
    "email": "nickpiggin@yahoo.com.au",
    "time": "Thu Jun 12 15:21:52 2008 -0700"
  },
  "committer": {
    "name": "Linus Torvalds",
    "email": "torvalds@linux-foundation.org",
    "time": "Thu Jun 12 18:05:41 2008 -0700"
  },
  "message": "radix-tree: fix small lockless radix-tree bug\n\nWe shrink a radix tree when its root node has only one child, in the left\nmost slot.  The child becomes the new root node.  To perform this\noperation in a manner compatible with concurrent lockless lookups, we\natomically switch the root pointer from the parent to its child.\n\nHowever a concurrent lockless lookup may now have loaded a pointer to the\nparent (and is presently deciding what to do next).  For this reason, we\nalso have to keep the parent node in a valid state after shrinking the\ntree, until the next RCU grace period -- otherwise this lookup with the\nparent pointer may not do the right thing.  Notably, we need to keep the\nchild in the left most slot there in case that is requested by the lookup.\n\nThis is all pretty standard RCU stuff.  It is worth repeating because in\nmy eagerness to obey the radix tree node constructor scheme, I had broken\nit by zeroing the radix tree node before the grace period.\n\nWhat could happen is that a lookup can load the parent pointer, then\ndecide it wants to follow the left most child slot, only to find the slot\ncontained NULL due to the concurrent shrinker having zeroed the parent\nnode before waiting for a grace period.  The lookup would return a false\nnegative as a result.\n\nFix it by doing that clearing in the RCU callback.  I would normally want\nto rip out the constructor entirely, but radix tree nodes are one of those\nplaces where they make sense (only few cachelines will be touched soon\nafter allocation).\n\nThis was never actually found in any lockless pagecache testing or by the\ntest harness, but by seeing the odd problem with my scalable vmap rewrite.\n I have not tickled the test harness into reproducing it yet, but I\u0027ll\nkeep working at it.\n\nFortunately, it is not a problem anywhere lockless pagecache is used in\nmainline kernels (pagecache probe is not a guarantee, and brd does not\nhave concurrent lookups and deletes).\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nAcked-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: \"Paul E. McKenney\" \u003cpaulmck@us.ibm.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "bd521716ab1a0498242e5dabc7021f1db7e0d91a",
      "old_mode": 33188,
      "old_path": "lib/radix-tree.c",
      "new_id": "169a2f8dabcc901f185faec5ff26da0d7194cdff",
      "new_mode": 33188,
      "new_path": "lib/radix-tree.c"
    }
  ]
}