)]}'
{
  "log": [
    {
      "commit": "928da837aca77a9d3cb5076bf07b3224b1ba293b",
      "tree": "741c003b608d50101fa91746d36a7c5e847a8fa5",
      "parents": [
        "65dd2aa90aa17a26703c28652408192856aa0396"
      ],
      "author": {
        "name": "Xiao Guangrong",
        "email": "xiaoguangrong@linux.vnet.ibm.com",
        "time": "Thu Jan 12 17:20:39 2012 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Thu Jan 12 20:13:12 2012 -0800"
      },
      "message": "radix_tree: remove radix_tree_indirect_to_ptr()\n\nIt is not used anymore, remove it\n\nSigned-off-by: Xiao Guangrong \u003cxiaoguangrong@linux.vnet.ibm.com\u003e\nAcked-by: Hugh Dickins \u003chughd@google.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "e504f3fdd63d486d45b18009e5a65f2e329acb0a",
      "tree": "2d02a5c29a922fae626a69cd0fc92cae37d7918e",
      "parents": [
        "31475dd611209413bace21651a400afb91d0bd9d"
      ],
      "author": {
        "name": "Hugh Dickins",
        "email": "hughd@google.com",
        "time": "Wed Aug 03 16:21:27 2011 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Wed Aug 03 14:25:24 2011 -1000"
      },
      "message": "tmpfs radix_tree: locate_item to speed up swapoff\n\nWe have already acknowledged that swapoff of a tmpfs file is slower than\nit was before conversion to the generic radix_tree: a little slower\nthere will be acceptable, if the hotter paths are faster.\n\nBut it was a shock to find swapoff of a 500MB file 20 times slower on my\nlaptop, taking 10 minutes; and at that rate it significantly slows down\nmy testing.\n\nNow, most of that turned out to be overhead from PROVE_LOCKING and\nPROVE_RCU: without those it was only 4 times slower than before; and\nmore realistic tests on other machines don\u0027t fare as badly.\n\nI\u0027ve tried a number of things to improve it, including tagging the swap\nentries, then doing lookup by tag: I\u0027d expected that to halve the time,\nbut in practice it\u0027s erratic, and often counter-productive.\n\nThe only change I\u0027ve so far found to make a consistent improvement, is\nto short-circuit the way we go back and forth, gang lookup packing\nentries into the array supplied, then shmem scanning that array for the\ntarget entry.  Scanning in place doubles the speed, so it\u0027s now only\ntwice as slow as before (or three times slower when the PROVEs are on).\n\nSo, add radix_tree_locate_item() as an expedient, once-off,\nsingle-caller hack to do the lookup directly in place.  #ifdef it on\nCONFIG_SHMEM and CONFIG_SWAP, as much to document its limited\napplicability as save space in other configurations.  And, sadly,\n#include sched.h for cond_resched().\n\nSigned-off-by: Hugh Dickins \u003chughd@google.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "6328650bb4d854a7dc1498d1c0048b838b0d340c",
      "tree": "0e265dc86f7c4451647c1e227843cdd1530f9651",
      "parents": [
        "70d327198a434edb95b3d858bc8010b8add28e3e"
      ],
      "author": {
        "name": "Hugh Dickins",
        "email": "hughd@google.com",
        "time": "Wed Aug 03 16:21:18 2011 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Wed Aug 03 14:25:22 2011 -1000"
      },
      "message": "radix_tree: exceptional entries and indices\n\nA patchset to extend tmpfs to MAX_LFS_FILESIZE by abandoning its\npeculiar swap vector, instead keeping a file\u0027s swap entries in the same\nradix tree as its struct page pointers: thus saving memory, and\nsimplifying its code and locking.\n\nThis patch:\n\nThe radix_tree is used by several subsystems for different purposes.  A\nmajor use is to store the struct page pointers of a file\u0027s pagecache for\nmemory management.  But what if mm wanted to store something other than\npage pointers there too?\n\nThe low bit of a radix_tree entry is already used to denote an indirect\npointer, for internal use, and the unlikely radix_tree_deref_retry()\ncase.\n\nDefine the next bit as denoting an exceptional entry, and supply inline\nfunctions radix_tree_exception() to return non-0 in either unlikely\ncase, and radix_tree_exceptional_entry() to return non-0 in the second\ncase.\n\nIf a subsystem already uses radix_tree with that bit set, no problem: it\ndoes not affect internal workings at all, but is defined for the\nconvenience of those storing well-aligned pointers in the radix_tree.\n\nThe radix_tree_gang_lookups have an implicit assumption that the caller\ncan deduce the offset of each entry returned e.g.  by the page-\u003eindex of\na struct page.  But that may not be feasible for some kinds of item to\nbe stored there.\n\nradix_tree_gang_lookup_slot() allow for an optional indices argument,\noutput array in which to return those offsets.  The same could be added\nto other radix_tree_gang_lookups, but for now keep it to the only one\nfor which we need it.\n\nSigned-off-by: Hugh Dickins \u003chughd@google.com\u003e\nAcked-by: Rik van Riel \u003criel@redhat.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "29c1f677d424e8c5683a837fc4f03fc9f19201d7",
      "tree": "97f257ab279cc000e02a1a58fa0869fb405f26cd",
      "parents": [
        "22e5c47ee238abe636655c3862ed28d6eb084ad4"
      ],
      "author": {
        "name": "Mel Gorman",
        "email": "mel@csn.ul.ie",
        "time": "Thu Jan 13 15:47:21 2011 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Thu Jan 13 17:32:48 2011 -0800"
      },
      "message": "mm: migration: use rcu_dereference_protected when dereferencing the radix tree slot during file page migration\n\nmigrate_pages() -\u003e unmap_and_move() only calls rcu_read_lock() for\nanonymous pages, as introduced by git commit\n989f89c57e6361e7d16fbd9572b5da7d313b073d (\"fix rcu_read_lock() in page\nmigraton\").  The point of the RCU protection there is part of getting a\nstable reference to anon_vma and is only held for anon pages as file pages\nare locked which is sufficient protection against freeing.\n\nHowever, while a file page\u0027s mapping is being migrated, the radix tree is\ndouble checked to ensure it is the expected page.  This uses\nradix_tree_deref_slot() -\u003e rcu_dereference() without the RCU lock held\ntriggering the following warning.\n\n[  173.674290] \u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n[  173.676016] [ INFO: suspicious rcu_dereference_check() usage. ]\n[  173.676016] ---------------------------------------------------\n[  173.676016] include/linux/radix-tree.h:145 invoked rcu_dereference_check() without protection!\n[  173.676016]\n[  173.676016] other info that might help us debug this:\n[  173.676016]\n[  173.676016]\n[  173.676016] rcu_scheduler_active \u003d 1, debug_locks \u003d 0\n[  173.676016] 1 lock held by hugeadm/2899:\n[  173.676016]  #0:  (\u0026(\u0026inode-\u003ei_data.tree_lock)-\u003erlock){..-.-.}, at: [\u003cc10e3d2b\u003e] migrate_page_move_mapping+0x40/0x1ab\n[  173.676016]\n[  173.676016] stack backtrace:\n[  173.676016] Pid: 2899, comm: hugeadm Not tainted 2.6.37-rc5-autobuild\n[  173.676016] Call Trace:\n[  173.676016]  [\u003cc128cc01\u003e] ? printk+0x14/0x1b\n[  173.676016]  [\u003cc1063502\u003e] lockdep_rcu_dereference+0x7d/0x86\n[  173.676016]  [\u003cc10e3db5\u003e] migrate_page_move_mapping+0xca/0x1ab\n[  173.676016]  [\u003cc10e41ad\u003e] migrate_page+0x23/0x39\n[  173.676016]  [\u003cc10e491b\u003e] buffer_migrate_page+0x22/0x107\n[  173.676016]  [\u003cc10e48f9\u003e] ? buffer_migrate_page+0x0/0x107\n[  173.676016]  [\u003cc10e425d\u003e] move_to_new_page+0x9a/0x1ae\n[  173.676016]  [\u003cc10e47e6\u003e] migrate_pages+0x1e7/0x2fa\n\nThis patch introduces radix_tree_deref_slot_protected() which calls\nrcu_dereference_protected().  Users of it must pass in the\nmapping-\u003etree_lock that is protecting this dereference.  Holding the tree\nlock protects against parallel updaters of the radix tree meaning that\nrcu_dereference_protected is allowable.\n\n[akpm@linux-foundation.org: remove unneeded casts]\nSigned-off-by: Mel Gorman \u003cmel@csn.ul.ie\u003e\nCc: Minchan Kim \u003cminchan.kim@gmail.com\u003e\nCc: KAMEZAWA Hiroyuki \u003ckamezawa.hiroyu@jp.fujitsu.com\u003e\nCc: Milton Miller \u003cmiltonm@bga.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: Wu Fengguang \u003cfengguang.wu@intel.com\u003e\nCc: \u003cstable@kernel.org\u003e\t\t[2.6.37.early]\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "27d20fddc8af539464fc3ba499d6a830054c3bd6",
      "tree": "23514cfe88f90150a8635c47586a8a378fb905e3",
      "parents": [
        "eaf06b241b091357e72b76863ba16e89610d31bd"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "npiggin@kernel.dk",
        "time": "Thu Nov 11 14:05:19 2010 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Fri Nov 12 07:55:32 2010 -0800"
      },
      "message": "radix-tree: fix RCU bug\n\nSalman Qazi describes the following radix-tree bug:\n\nIn the following case, we get can get a deadlock:\n\n0.  The radix tree contains two items, one has the index 0.\n1.  The reader (in this case find_get_pages) takes the rcu_read_lock.\n2.  The reader acquires slot(s) for item(s) including the index 0 item.\n3.  The non-zero index item is deleted, and as a consequence the other item is\n    moved to the root of the tree. The place where it used to be is queued for\n    deletion after the readers finish.\n3b. The zero item is deleted, removing it from the direct slot, it remains in\n    the rcu-delayed indirect node.\n4.  The reader looks at the index 0 slot, and finds that the page has 0 ref\n    count\n5.  The reader looks at it again, hoping that the item will either be freed or\n    the ref count will increase. This never happens, as the slot it is looking\n    at will never be updated. Also, this slot can never be reclaimed because\n    the reader is holding rcu_read_lock and is in an infinite loop.\n\nThe fix is to re-use the same \"indirect\" pointer case that requires a slot\nlookup retry into a general \"retry the lookup\" bit.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@kernel.dk\u003e\nReported-by: Salman Qazi \u003csqazi@google.com\u003e\nCc: \u003cstable@kernel.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "a1115570b31091f3e3ab9e6cf7ee8d320a42be84",
      "tree": "1253b42dd3348fb733fdf51bcf30f1abf1388b19",
      "parents": [
        "374a8e0dc33c984fac284de7d57d77af3cfdbfb7"
      ],
      "author": {
        "name": "Arnd Bergmann",
        "email": "arnd@arndb.de",
        "time": "Thu Feb 25 23:43:52 2010 +0100"
      },
      "committer": {
        "name": "Paul E. McKenney",
        "email": "paulmck@linux.vnet.ibm.com",
        "time": "Thu Aug 19 17:18:03 2010 -0700"
      },
      "message": "radix-tree: __rcu annotations\n\nSigned-off-by: Arnd Bergmann \u003carnd@arndb.de\u003e\nSigned-off-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nCc: Nick Piggin \u003cnpiggin@suse.de\u003e\nReviewed-by: Josh Triplett \u003cjosh@joshtriplett.org\u003e\n"
    },
    {
      "commit": "f446daaea9d4a420d16c606f755f3689dcb2d0ce",
      "tree": "be2afc18f79aa4ff9be245b0a036aa06185b5dc4",
      "parents": [
        "ebf8aa44beed48cd17893a83d92a4403e5f9d9e2"
      ],
      "author": {
        "name": "Jan Kara",
        "email": "jack@suse.cz",
        "time": "Mon Aug 09 17:19:12 2010 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Mon Aug 09 20:44:59 2010 -0700"
      },
      "message": "mm: implement writeback livelock avoidance using page tagging\n\nWe try to avoid livelocks of writeback when some steadily creates dirty\npages in a mapping we are writing out.  For memory-cleaning writeback,\nusing nr_to_write works reasonably well but we cannot really use it for\ndata integrity writeback.  This patch tries to solve the problem.\n\nThe idea is simple: Tag all pages that should be written back with a\nspecial tag (TOWRITE) in the radix tree.  This can be done rather quickly\nand thus livelocks should not happen in practice.  Then we start doing the\nhard work of locking pages and sending them to disk only for those pages\nthat have TOWRITE tag set.\n\nNote: Adding new radix tree tag grows radix tree node from 288 to 296\nbytes for 32-bit archs and from 552 to 560 bytes for 64-bit archs.\nHowever, the number of slab/slub items per page remains the same (13 and 7\nrespectively).\n\nSigned-off-by: Jan Kara \u003cjack@suse.cz\u003e\nCc: Dave Chinner \u003cdavid@fromorbit.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: Chris Mason \u003cchris.mason@oracle.com\u003e\nCc: Theodore Ts\u0027o \u003ctytso@mit.edu\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "ebf8aa44beed48cd17893a83d92a4403e5f9d9e2",
      "tree": "03607aa1cdbbb7fda935edb28bb3ad06423852ac",
      "parents": [
        "44ab57a06ded284db6ccdefc6b76eddb1c34d7ed"
      ],
      "author": {
        "name": "Jan Kara",
        "email": "jack@suse.cz",
        "time": "Mon Aug 09 17:19:11 2010 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Mon Aug 09 20:44:59 2010 -0700"
      },
      "message": "radix-tree: omplement function radix_tree_range_tag_if_tagged\n\nImplement function for setting one tag if another tag is set for each item\nin given range.\n\nSigned-off-by: Jan Kara \u003cjack@suse.cz\u003e\nCc: Dave Chinner \u003cdavid@fromorbit.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: Chris Mason \u003cchris.mason@oracle.com\u003e\nCc: Theodore Ts\u0027o \u003ctytso@mit.edu\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "ce82653d6cfcc95ba88c25908664878459fb1b8d",
      "tree": "ab80dd0055bcb4b9296c28c241f1d1fba229be1f",
      "parents": [
        "d3e06e2b15590b70ea73733fc4612e4741ff46e0"
      ],
      "author": {
        "name": "David Howells",
        "email": "dhowells@redhat.com",
        "time": "Tue Apr 06 22:36:20 2010 +0100"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Fri Apr 09 10:12:03 2010 -0700"
      },
      "message": "radix_tree_tag_get() is not as safe as the docs make out [ver #2]\n\nradix_tree_tag_get() is not safe to use concurrently with radix_tree_tag_set()\nor radix_tree_tag_clear().  The problem is that the double tag_get() in\nradix_tree_tag_get():\n\n\t\tif (!tag_get(node, tag, offset))\n\t\t\tsaw_unset_tag \u003d 1;\n\t\tif (height \u003d\u003d 1) {\n\t\t\tint ret \u003d tag_get(node, tag, offset);\n\nmay see the value change due to the action of set/clear.  RCU is no protection\nagainst this as no pointers are being changed, no nodes are being replaced\naccording to a COW protocol - set/clear alter the node directly.\n\nThe documentation in linux/radix-tree.h, however, says that\nradix_tree_tag_get() is an exception to the rule that \"any function modifying\nthe tree or tags (...) must exclude other modifications, and exclude any\nfunctions reading the tree\".\n\nThe problem is that the next statement in radix_tree_tag_get() checks that the\ntag doesn\u0027t vary over time:\n\n\t\t\tBUG_ON(ret \u0026\u0026 saw_unset_tag);\n\nThis has been seen happening in FS-Cache:\n\n\thttps://www.redhat.com/archives/linux-cachefs/2010-April/msg00013.html\n\nTo this end, remove the BUG_ON() from radix_tree_tag_get() and note in various\ncomments that the value of the tag may change whilst the RCU read lock is held,\nand thus that the return value of radix_tree_tag_get() may not be relied upon\nunless radix_tree_tag_set/clear() and radix_tree_delete() are excluded from\nrunning concurrently with it.\n\nReported-by: Romain DEGEZ \u003cromain.degez@smartjog.com\u003e\nSigned-off-by: David Howells \u003cdhowells@redhat.com\u003e\nAcked-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "dc566127dd161b6c997466a2349ac179527ea89b",
      "tree": "2973018dd4a89f0b20eaa0838eb654b6eff06f68",
      "parents": [
        "d30a11004e3411909f2448546f036a011978062e"
      ],
      "author": {
        "name": "Wu Fengguang",
        "email": "fengguang.wu@intel.com",
        "time": "Tue Jun 16 15:31:32 2009 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Jun 16 19:47:30 2009 -0700"
      },
      "message": "radix-tree: add radix_tree_prev_hole()\n\nThe counterpart of radix_tree_next_hole(). To be used by context readahead.\n\nSigned-off-by: Wu Fengguang \u003cfengguang.wu@intel.com\u003e\nCc: Vladislav Bolkhovitin \u003cvst@vlnb.net\u003e\nCc: Jens Axboe \u003cjens.axboe@oracle.com\u003e\nCc: Jeff Moyer \u003cjmoyer@redhat.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: Ying Han \u003cyinghan@google.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "e8c82c2e23e3527e0c9dc195e432c16784d270fa",
      "tree": "943b1359ff8d6855b0b5fd37bb0ae61f01a7da0d",
      "parents": [
        "f1b11e505463fd597ab7963df26dd1f446dcceae"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "npiggin@suse.de",
        "time": "Tue Jan 06 03:05:50 2009 +0100"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Mon Jan 05 18:31:12 2009 -0800"
      },
      "message": "mm lockless pagecache barrier fix\n\nAn XFS workload showed up a bug in the lockless pagecache patch. Basically it\nwould go into an \"infinite\" loop, although it would sometimes be able to break\nout of the loop! The reason is a missing compiler barrier in the \"increment\nreference count unless it was zero\" case of the lockless pagecache protocol in\nthe gang lookup functions.\n\nThis would cause the compiler to use a cached value of struct page pointer to\nretry the operation with, rather than reload it. So the page might have been\nremoved from pagecache and freed (refcount\u003d\u003d0) but the lookup would not correctly\nnotice the page is no longer in pagecache, and keep attempting to increment the\nrefcount and failing, until the page gets reallocated for something else. This\nisn\u0027t a data corruption because the condition will be detected if the page has\nbeen reallocated. However it can result in a lockup.\n\nLinus points out that ACCESS_ONCE is also required in that pointer load, even\nif it\u0027s absence is not causing a bug on our particular build. The most general\nway to solve this is just to put an rcu_dereference in radix_tree_deref_slot.\n\nAssembly of find_get_pages,\nbefore:\n.L220:\n        movq    (%rbx), %rax    #* ivtmp.1162, tmp82\n        movq    (%rax), %rdi    #, prephitmp.1149\n.L218:\n        testb   $1, %dil        #, prephitmp.1149\n        jne     .L217   #,\n        testq   %rdi, %rdi      # prephitmp.1149\n        je      .L203   #,\n        cmpq    $-1, %rdi       #, prephitmp.1149\n        je      .L217   #,\n        movl    8(%rdi), %esi   # \u003cvariable\u003e._count.counter, c\n        testl   %esi, %esi      # c\n        je      .L218   #,\n\nafter:\n.L212:\n        movq    (%rbx), %rax    #* ivtmp.1109, tmp81\n        movq    (%rax), %rdi    #, ret\n        testb   $1, %dil        #, ret\n        jne     .L211   #,\n        testq   %rdi, %rdi      # ret\n        je      .L197   #,\n        cmpq    $-1, %rdi       #, ret\n        je      .L211   #,\n        movl    8(%rdi), %esi   # \u003cvariable\u003e._count.counter, c\n        testl   %esi, %esi      # c\n        je      .L212   #,\n\n(notice the obvious infinite loop in the first example, if page-\u003ecount remains 0)\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nReviewed-by: Paul E. McKenney \u003cpaulmck@linux.vnet.ibm.com\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "47feff2c8eefe85099f87c43d3096855f0085ca0",
      "tree": "a3a6d005f202d1a37bb406c5623a9d09a447b0f0",
      "parents": [
        "30002ed2e41830ec03ec3e577ad83ac6b188f96e"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "npiggin@suse.de",
        "time": "Fri Jul 25 19:45:29 2008 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Sat Jul 26 12:00:06 2008 -0700"
      },
      "message": "radix-tree: add gang_lookup_slot, gang_lookup_slot_tag\n\nIntroduce gang_lookup_slot() and gang_lookup_slot_tag() functions, which\nare used by lockless pagecache.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nCc: Benjamin Herrenschmidt \u003cbenh@kernel.crashing.org\u003e\nCc: Paul Mackerras \u003cpaulus@samba.org\u003e\nCc: Hugh Dickins \u003chugh@veritas.com\u003e\nCc: \"Paul E. McKenney\" \u003cpaulmck@us.ibm.com\u003e\nReviewed-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "eb8dc5e7b58bfe56aa91bcc501b62f214bb401e8",
      "tree": "a14cccf94ba18e09e224fd8bdf395e362fec6c45",
      "parents": [
        "48cc7ec93f65b48d3366c1a5c5b612a0d2c282a6"
      ],
      "author": {
        "name": "Tim Pepper",
        "email": "lnxninja@linux.vnet.ibm.com",
        "time": "Sun Feb 03 16:12:47 2008 +0200"
      },
      "committer": {
        "name": "Adrian Bunk",
        "email": "bunk@kernel.org",
        "time": "Sun Feb 03 16:12:47 2008 +0200"
      },
      "message": "radix_tree.h trivial comment correction\n\nThere is an unmatched parenthesis in the locking commentary of radix_tree.h\nwhich is trivially fixed by the patch below.\n\nSigned-off-by: Tim Pepper \u003clnxninja@linux.vnet.ibm.com\u003e\nAcked-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nSigned-off-by: Adrian Bunk \u003cbunk@kernel.org\u003e\n"
    },
    {
      "commit": "c0bc9875b701c588e448302d41181995c21e8040",
      "tree": "c320855d4c04bd51ded6b4888bc5895ab539165f",
      "parents": [
        "b55ed816235cf41c29159d22a4cdeec7deb5821c"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "npiggin@suse.de",
        "time": "Tue Oct 16 01:24:42 2007 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@woody.linux-foundation.org",
        "time": "Tue Oct 16 09:42:53 2007 -0700"
      },
      "message": "radix-tree: use indirect bit\n\nRather than sign direct radix-tree pointers with a special bit, sign the\nindirect one that hangs off the root.  This means that, given a lookup_slot\noperation, the invalid result will be differentiated from the valid\n(previously, valid results could have the bit either set or clear).\n\nThis does not affect slot lookups which occur under lock -- they can never\nreturn an invalid result.  Is needed in future for lockless pagecache.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nAcked-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Hugh Dickins \u003chugh@veritas.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "6df8ba4f8a4c4abca9ccad10441d0dddbdff301c",
      "tree": "6ac5cd48d3400a9d32f8affd31106f7942df9547",
      "parents": [
        "f4e6b498d6e06742d72706ef50593a9c4dd72214"
      ],
      "author": {
        "name": "Fengguang Wu",
        "email": "wfg@mail.ustc.edu.cn",
        "time": "Tue Oct 16 01:24:33 2007 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@woody.linux-foundation.org",
        "time": "Tue Oct 16 09:42:52 2007 -0700"
      },
      "message": "radixtree: introduce radix_tree_next_hole()\n\nIntroduce radix_tree_next_hole(root, index, max_scan) to scan radix tree for\nthe first hole.  It will be used in interleaved readahead.\n\nThe implementation is dumb and obviously correct.  It can help debug(and\ndocument) the possible smart one in future.\n\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nSigned-off-by: Fengguang Wu \u003cwfg@mail.ustc.edu.cn\u003e\nCc: Rusty Russell \u003crusty@rustcorp.com.au\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "59c51591a0ac7568824f541f57de967e88adaa07",
      "tree": "243d20eb0a26b76d5d312f39ec5a1ff60e036711",
      "parents": [
        "02a3e59a088749c08b0293ee1535f5bf48f5926c"
      ],
      "author": {
        "name": "Michael Opdenacker",
        "email": "michael@free-electrons.com",
        "time": "Wed May 09 08:57:56 2007 +0200"
      },
      "committer": {
        "name": "Adrian Bunk",
        "email": "bunk@stusta.de",
        "time": "Wed May 09 08:57:56 2007 +0200"
      },
      "message": "Fix occurrences of \"the the \"\n\nSigned-off-by: Michael Opdenacker \u003cmichael@free-electrons.com\u003e\nSigned-off-by: Adrian Bunk \u003cbunk@stusta.de\u003e\n"
    },
    {
      "commit": "7cf9c2c76c1a17b32f2da85b50cd4fe468ed44b5",
      "tree": "c3ed3e92e21f19ef744c9ea6829f4ff8d06e9f14",
      "parents": [
        "36de6437866bbb1d37e2312ff4f95ee4ed6d2b61"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "npiggin@suse.de",
        "time": "Wed Dec 06 20:33:44 2006 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@woody.osdl.org",
        "time": "Thu Dec 07 08:39:25 2006 -0800"
      },
      "message": "[PATCH] radix-tree: RCU lockless readside\n\nMake radix tree lookups safe to be performed without locks.  Readers are\nprotected against nodes being deleted by using RCU based freeing.  Readers\nare protected against new node insertion by using memory barriers to ensure\nthe node itself will be properly written before it is visible in the radix\ntree.\n\nEach radix tree node keeps a record of their height (above leaf nodes).\nThis height does not change after insertion -- when the radix tree is\nextended, higher nodes are only inserted in the top.  So a lookup can take\nthe pointer to what is *now* the root node, and traverse down it even if\nthe tree is concurrently extended and this node becomes a subtree of a new\nroot.\n\n\"Direct\" pointers (tree height of 0, where root-\u003ernode points directly to\nthe data item) are handled by using the low bit of the pointer to signal\nwhether rnode is a direct pointer or a pointer to a radix tree node.\n\nWhen a reader wants to traverse the next branch, they will take a copy of\nthe pointer.  This pointer will be either NULL (and the branch is empty) or\nnon-NULL (and will point to a valid node).\n\n[akpm@osdl.org: cleanups]\n[Lee.Schermerhorn@hp.com: bugfixes, comments, simplifications]\n[clameter@sgi.com: build fix]\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nCc: \"Paul E. McKenney\" \u003cpaulmck@us.ibm.com\u003e\nSigned-off-by: Lee Schermerhorn \u003clee.schermerhorn@hp.com\u003e\nCc: Christoph Lameter \u003cclameter@engr.sgi.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "914e26379decf1fd984b22e51fd2e4209b7a7f1b",
      "tree": "4f20ee40e959699e344cdff0e117d309d238f6be",
      "parents": [
        "f6a570333e554b48ad589e7137c77c57809eee81"
      ],
      "author": {
        "name": "Al Viro",
        "email": "viro@zeniv.linux.org.uk",
        "time": "Wed Oct 18 13:55:46 2006 -0400"
      },
      "committer": {
        "name": "Al Viro",
        "email": "viro@zeniv.linux.org.uk",
        "time": "Mon Dec 04 02:00:24 2006 -0500"
      },
      "message": "[PATCH] severing fs.h, radix-tree.h -\u003e sched.h\n\nSigned-off-by: Al Viro \u003cviro@zeniv.linux.org.uk\u003e\n"
    },
    {
      "commit": "612d6c19db2fd0dc97b0fa370613ecd4a305ffc3",
      "tree": "3ab670895b5c3e389ff922192a572cbfd8159d03",
      "parents": [
        "929f97276bcf7f4a95272ed08a85339b98ba210d"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "npiggin@suse.de",
        "time": "Fri Jun 23 02:03:22 2006 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Fri Jun 23 07:42:49 2006 -0700"
      },
      "message": "[PATCH] radix-tree: direct data\n\nThe ability to have height 0 radix trees (a direct pointer to the data item\nrather than going through a full node-\u003eslot) quietly disappeared with\nold-2.6-bkcvs commit ffee171812d51652f9ba284302d9e5c5cc14bdfd.  On 64-bit\nmachines this causes nearly 600 bytes to be used for every \u003c\u003d 4K file in\npagecache.\n\nRe-introduce this feature, root tags stored in spare -\u003egfp_mask bits.\n\nSimplify radix_tree_delete\u0027s complex tag clearing arrangement (which would\nbecome even more complex) by just falling back to tag clearing functions\n(the pagecache radix-tree never uses this path anyway, so the icache\nsavings will mean it\u0027s actually a speedup).\n\nOn my 4GB G5, this saves 8MB RAM per kernel kernel source+object tree in\npagecache.\n\nPagecache lookup, insertion, and removal speed for small files will also be\nimproved.\n\nThis makes RCU radix tree harder, but it\u0027s worth it.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "daff89f324755f87a060d5125a205c0755811ea9",
      "tree": "5b2734bd46c8d73a068b571ba1059e67df014825",
      "parents": [
        "57070d012cd425c3a71663528c56a436abd2d9da"
      ],
      "author": {
        "name": "Jonathan Corbet",
        "email": "corbet@lwn.net",
        "time": "Sat Mar 25 03:08:05 2006 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Sat Mar 25 08:22:59 2006 -0800"
      },
      "message": "[PATCH] radix-tree documentation cleanups\n\nDocumentation changes to help radix tree users avoid overrunning the tags\narray.  RADIX_TREE_TAGS moves to linux/radix-tree.h and is now known as\nRADIX_TREE_MAX_TAGS (Nick Piggin\u0027s idea).  Tag parameters are changed to\nunsigned, and some comments are updated.\n\nSigned-off-by: Jonathan Corbet \u003ccorbet@lwn.net\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "095975da26dba21698582e91e96be10f7417333f",
      "tree": "ce1ffac556d394ef56a18faa97d38f79b07f31e2",
      "parents": [
        "a57004e1afb6ee03c509f1b1ec74a000682ab93b"
      ],
      "author": {
        "name": "Nick Piggin",
        "email": "nickpiggin@yahoo.com.au",
        "time": "Sun Jan 08 01:02:19 2006 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Sun Jan 08 20:13:48 2006 -0800"
      },
      "message": "[PATCH] rcu file: use atomic primitives\n\nUse atomic_inc_not_zero for rcu files instead of special case rcuref.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nCc: \"Paul E. McKenney\" \u003cpaulmck@us.ibm.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "a43313668f62a06e14c915b8c8994fc8a1257394",
      "tree": "ae02e1ae145b3f277ead948c32b8b6d06a4e23d9",
      "parents": [
        "7361f4d8ca65d23a18ba009b4484612183332c2f"
      ],
      "author": {
        "name": "Hans Reiser",
        "email": "reiser@namesys.com",
        "time": "Mon Nov 07 00:59:29 2005 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Mon Nov 07 07:53:37 2005 -0800"
      },
      "message": "[PATCH] reiser4: add radix_tree_lookup_slot()\n\nReiser4 uses radix trees to solve a trouble reiser4_readdir has serving nfs\nrequests.\n\nUnfortunately, radix tree api lacks an operation suitable for modifying\nexisting entry.  This patch adds radix_tree_lookup_slot which returns pointer\nto found item within the tree.  That location can be then updated.\n\nBoth Nick and Christoph Lameter have patches which need this as well.\n\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "fd4f2df24bc23e6b8fc069765b425c7dacf52347",
      "tree": "f7e993817030747c5e1000d46685ebd2eef11085",
      "parents": [
        "6daa0e28627abf362138244a620a821a9027d816"
      ],
      "author": {
        "name": "Al Viro",
        "email": "viro@zeniv.linux.org.uk",
        "time": "Fri Oct 21 03:18:50 2005 -0400"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Fri Oct 28 08:16:47 2005 -0700"
      },
      "message": "[PATCH] gfp_t: lib/*\n\nSigned-off-by: Al Viro \u003cviro@zeniv.linux.org.uk\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "dd0fc66fb33cd610bc1a5db8a5e232d34879b4d7",
      "tree": "51f96a9db96293b352e358f66032e1f4ff79fafb",
      "parents": [
        "3b0e77bd144203a507eb191f7117d2c5004ea1de"
      ],
      "author": {
        "name": "Al Viro",
        "email": "viro@ftp.linux.org.uk",
        "time": "Fri Oct 07 07:46:04 2005 +0100"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Sat Oct 08 15:00:57 2005 -0700"
      },
      "message": "[PATCH] gfp flags annotations - part 1\n\n - added typedef unsigned int __nocast gfp_t;\n\n - replaced __nocast uses for gfp flags with gfp_t - it gives exactly\n   the same warnings as far as sparse is concerned, doesn\u0027t change\n   generated code (from gcc point of view we replaced unsigned int with\n   typedef) and documents what\u0027s going on far better.\n\nSigned-off-by: Al Viro \u003cviro@zeniv.linux.org.uk\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "00b61f51922e432fd92a482ba1e0b5f8f326ef46",
      "tree": "8e639c633b9dfd826993ced8dad82e4578b25a6e",
      "parents": [
        "d533f671852cc4e481ea7070aa1a3b6fc75b8e44"
      ],
      "author": {
        "name": "Victor Fusco",
        "email": "victor@cetuc.puc-rio.br",
        "time": "Sat Sep 10 00:26:48 2005 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@g5.osdl.org",
        "time": "Sat Sep 10 10:06:28 2005 -0700"
      },
      "message": "[PATCH] lib/radix-tree: Fix \"nocast type\" warnings\n\nFix the sparse warning \"implicit cast to nocast type\"\n\nSigned-off-by: Victor Fusco \u003cvictor@cetuc.puc-rio.br\u003e\nSigned-off-by: Domen Puncer \u003cdomen@coderock.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n"
    },
    {
      "commit": "1da177e4c3f41524e886b7f1b8a0c1fc7321cac2",
      "tree": "0bba044c4ce775e45a88a51686b5d9f90697ea9d",
      "parents": [],
      "author": {
        "name": "Linus Torvalds",
        "email": "torvalds@ppc970.osdl.org",
        "time": "Sat Apr 16 15:20:36 2005 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@ppc970.osdl.org",
        "time": "Sat Apr 16 15:20:36 2005 -0700"
      },
      "message": "Linux-2.6.12-rc2\n\nInitial git repository build. I\u0027m not bothering with the full history,\neven though we have it. We can create a separate \"historical\" git\narchive of that later if we want to, and in the meantime it\u0027s about\n3.2GB when imported into git - space that would just make the early\ngit days unnecessarily complicated, when we don\u0027t have a lot of good\ninfrastructure for it.\n\nLet it rip!\n"
    }
  ]
}