)]}' { "log": [ { "commit": "fffaee365fded09f9ebf2db19066065fa54323c3", "tree": "f6a6d331fa62c9814f9875a845afad1e7994cbde", "parents": [ "f9ba7179ce91fb77b2adf6eaab3676ab3a1f5a15" ], "author": { "name": "Konstantin Khlebnikov", "email": "khlebnikov@openvz.org", "time": "Tue Jun 05 21:36:33 2012 +0400" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue Jun 05 10:46:40 2012 -0700" }, "message": "radix-tree: fix contiguous iterator\n\nThis patch fixes bug in macro radix_tree_for_each_contig().\n\nIf radix_tree_next_slot() sees NULL in next slot it returns NULL, but following\nradix_tree_next_chunk() switches iterating into next chunk. As result iterating\nbecomes non-contiguous and breaks vfs \"splice\" and all its users.\n\nSigned-off-by: Konstantin Khlebnikov \u003ckhlebnikov@openvz.org\u003e\nReported-and-bisected-by: Hans de Bruin \u003cjmdebruin@xmsnet.nl\u003e\nReported-and-bisected-by: Ondrej Zary \u003clinux@rainbow-software.org\u003e\nReported-bisected-and-tested-by: Toralf Förster \u003ctoralf.foerster@gmx.de\u003e\nLink: https://lkml.org/lkml/2012/6/5/64\nCc: stable \u003cstable@vger.kernel.org\u003e # 3.4.x\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "5536805292e64393f57054de66578f17eb1ea994", "tree": "d7c283b123fd1fa0a944b500aba31f01207a98fd", "parents": [ "fd0a37355c4d39affa39d5cd75168fb94b292318" ], "author": { "name": "Nick Piggin", "email": "npiggin@kernel.dk", "time": "Tue May 29 15:07:34 2012 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue May 29 16:22:33 2012 -0700" }, "message": "radix-tree: fix preload vector size\n\nWe are not preallocating a sufficient number of nodes.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@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": "cebbd29e1c2f7a969919f19f74583070840163d7", "tree": "f9ec01b2cb5c3affe64587b83d4877429f0edc0c", "parents": [ "78c1d78488a3c45685d993130c9f17102dc79a54" ], "author": { "name": "Konstantin Khlebnikov", "email": "khlebnikov@openvz.org", "time": "Wed Mar 28 14:42:53 2012 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Wed Mar 28 17:14:37 2012 -0700" }, "message": "radix-tree: rewrite gang lookup using iterator\n\nRewrite radix_tree_gang_lookup_* functions using the new radix-tree\niterator.\n\nSigned-off-by: Konstantin Khlebnikov \u003ckhlebnikov@openvz.org\u003e\nTested-by: Hugh Dickins \u003chughd@google.com\u003e\nCc: Christoph Hellwig \u003chch@lst.de\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "78c1d78488a3c45685d993130c9f17102dc79a54", "tree": "b9fd6e6b53b5b161836bea39811f16deb0ad88ff", "parents": [ "4c619aa0ba171c092a0ae5d969364deb82dbe371" ], "author": { "name": "Konstantin Khlebnikov", "email": "khlebnikov@openvz.org", "time": "Wed Mar 28 14:42:53 2012 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Wed Mar 28 17:14:37 2012 -0700" }, "message": "radix-tree: introduce bit-optimized iterator\n\nA series of radix tree cleanups, and usage of them in the core pagecache\ncode.\n\nMicro-benchmark:\n\nlookup 14 slots (typical page-vector size)\nin radix-tree there earch \u003cstep\u003e slot filled and tagged\nbefore/after - nsec per full scan through tree\n\n* Intel Sandy Bridge i7-2620M 4Mb L3\nNew code always faster\n\n* AMD Athlon 6000+ 2x1Mb L2, without L3\nNew code generally faster,\nMinor degradation (marked with \"*\") for huge sparse trees\n\n* i386 on Sandy Bridge\nNew code faster for common cases: tagged and dense trees.\nSome degradations for non-tagged lookup on sparse trees.\n\nIdeally, there might help __ffs() analog for searching first non-zero\nlong element in array, gcc sometimes cannot optimize this loop corretly.\n\nNumbers:\n\nCPU: Intel Sandy Bridge i7-2620M 4Mb L3\n\nradix-tree with 1024 slots:\n\ntagged lookup\n\nstep 1 before 7156 after 3613\nstep 2 before 5399 after 2696\nstep 3 before 4779 after 1928\nstep 4 before 4456 after 1429\nstep 5 before 4292 after 1213\nstep 6 before 4183 after 1052\nstep 7 before 4157 after 951\nstep 8 before 4016 after 812\nstep 9 before 3952 after 851\nstep 10 before 3937 after 732\nstep 11 before 4023 after 709\nstep 12 before 3872 after 657\nstep 13 before 3892 after 633\nstep 14 before 3720 after 591\nstep 15 before 3879 after 578\nstep 16 before 3561 after 513\n\nnormal lookup\n\nstep 1 before 4266 after 3301\nstep 2 before 2695 after 2129\nstep 3 before 2083 after 1712\nstep 4 before 1801 after 1534\nstep 5 before 1628 after 1313\nstep 6 before 1551 after 1263\nstep 7 before 1475 after 1185\nstep 8 before 1432 after 1167\nstep 9 before 1373 after 1092\nstep 10 before 1339 after 1134\nstep 11 before 1292 after 1056\nstep 12 before 1319 after 1030\nstep 13 before 1276 after 1004\nstep 14 before 1256 after 987\nstep 15 before 1228 after 992\nstep 16 before 1247 after 999\n\nradix-tree with 1024*1024*128 slots:\n\ntagged lookup\n\nstep 1 before 1086102841 after 674196409\nstep 2 before 816839155 after 498138306\nstep 7 before 599728907 after 240676762\nstep 15 before 555729253 after 185219677\nstep 63 before 606637748 after 128585664\nstep 64 before 608384432 after 102945089\nstep 65 before 596987114 after 123996019\nstep 128 before 304459225 after 56783056\nstep 256 before 158846855 after 31232481\nstep 512 before 86085652 after 18950595\nstep 12345 before 6517189 after 1674057\n\nnormal lookup\n\nstep 1 before 626064869 after 544418266\nstep 2 before 418809975 after 336321473\nstep 7 before 242303598 after 207755560\nstep 15 before 208380563 after 176496355\nstep 63 before 186854206 after 167283638\nstep 64 before 176188060 after 170143976\nstep 65 before 185139608 after 167487116\nstep 128 before 88181865 after 86913490\nstep 256 before 45733628 after 45143534\nstep 512 before 24506038 after 23859036\nstep 12345 before 2177425 after 2018662\n\n* AMD Athlon 6000+ 2x1Mb L2, without L3\n\nradix-tree with 1024 slots:\n\ntag-lookup\n\nstep 1 before 8164 after 5379\nstep 2 before 5818 after 5581\nstep 3 before 4959 after 4213\nstep 4 before 4371 after 3386\nstep 5 before 4204 after 2997\nstep 6 before 4950 after 2744\nstep 7 before 4598 after 2480\nstep 8 before 4251 after 2288\nstep 9 before 4262 after 2243\nstep 10 before 4175 after 2131\nstep 11 before 3999 after 2024\nstep 12 before 3979 after 1994\nstep 13 before 3842 after 1929\nstep 14 before 3750 after 1810\nstep 15 before 3735 after 1810\nstep 16 before 3532 after 1660\n\nnormal-lookup\n\nstep 1 before 7875 after 5847\nstep 2 before 4808 after 4071\nstep 3 before 4073 after 3462\nstep 4 before 3677 after 3074\nstep 5 before 4308 after 2978\nstep 6 before 3911 after 3807\nstep 7 before 3635 after 3522\nstep 8 before 3313 after 3202\nstep 9 before 3280 after 3257\nstep 10 before 3166 after 3083\nstep 11 before 3066 after 3026\nstep 12 before 2985 after 2982\nstep 13 before 2925 after 2924\nstep 14 before 2834 after 2808\nstep 15 before 2805 after 2803\nstep 16 before 2647 after 2622\n\nradix-tree with 1024*1024*128 slots:\n\ntag-lookup\n\nstep 1 before 1288059720 after 951736580\nstep 2 before 961292300 after 884212140\nstep 7 before 768905140 after 547267580\nstep 15 before 771319480 after 456550640\nstep 63 before 504847640 after 242704304\nstep 64 before 392484800 after 177920786\nstep 65 before 491162160 after 246895264\nstep 128 before 208084064 after 97348392\nstep 256 before 112401035 after 51408126\nstep 512 before 75825834 after 29145070\nstep 12345 before 5603166 after 2847330\n\nnormal-lookup\n\nstep 1 before 1025677120 after 861375100\nstep 2 before 647220080 after 572258540\nstep 7 before 505518960 after 484041813\nstep 15 before 430483053 after 444815320\t*\nstep 63 before 388113453 after 404250546\t*\nstep 64 before 374154666 after 396027440\t*\nstep 65 before 381423973 after 396704853\t*\nstep 128 before 190078700 after 202619384\t*\nstep 256 before 100886756 after 102829108\t*\nstep 512 before 64074505 after 56158720\nstep 12345 before 4237289 after 4422299\t\t*\n\n* i686 on Sandy bridge\n\nradix-tree with 1024 slots:\n\ntagged lookup\n\nstep 1 before 7990 after 4019\nstep 2 before 5698 after 2897\nstep 3 before 5013 after 2475\nstep 4 before 4630 after 1721\nstep 5 before 4346 after 1759\nstep 6 before 4299 after 1556\nstep 7 before 4098 after 1513\nstep 8 before 4115 after 1222\nstep 9 before 3983 after 1390\nstep 10 before 4077 after 1207\nstep 11 before 3921 after 1231\nstep 12 before 3894 after 1116\nstep 13 before 3840 after 1147\nstep 14 before 3799 after 1090\nstep 15 before 3797 after 1059\nstep 16 before 3783 after 745\n\nnormal lookup\n\nstep 1 before 5103 after 3499\nstep 2 before 3299 after 2550\nstep 3 before 2489 after 2370\nstep 4 before 2034 after 2302\t\t*\nstep 5 before 1846 after 2268\t\t*\nstep 6 before 1752 after 2249\t\t*\nstep 7 before 1679 after 2164\t\t*\nstep 8 before 1627 after 2153\t\t*\nstep 9 before 1542 after 2095\t\t*\nstep 10 before 1479 after 2109\t\t*\nstep 11 before 1469 after 2009\t\t*\nstep 12 before 1445 after 2039\t\t*\nstep 13 before 1411 after 2013\t\t*\nstep 14 before 1374 after 2046\t\t*\nstep 15 before 1340 after 1975\t\t*\nstep 16 before 1331 after 2000\t\t*\n\nradix-tree with 1024*1024*128 slots:\n\ntagged lookup\n\nstep 1 before 1225865377 after 667153553\nstep 2 before 842427423 after 471533007\nstep 7 before 609296153 after 276260116\nstep 15 before 544232060 after 226859105\nstep 63 before 519209199 after 141343043\nstep 64 before 588980279 after 141951339\nstep 65 before 521099710 after 138282060\nstep 128 before 298476778 after 83390628\nstep 256 before 149358342 after 43602609\nstep 512 before 76994713 after 22911077\nstep 12345 before 5328666 after 1472111\n\nnormal lookup\n\nstep 1 before 819284564 after 533635310\nstep 2 before 512421605 after 364956155\nstep 7 before 271443305 after 305721345\t*\nstep 15 before 223591630 after 273960216\t*\nstep 63 before 190320247 after 217770207\t*\nstep 64 before 178538168 after 267411372\t*\nstep 65 before 186400423 after 215347937\t*\nstep 128 before 88106045 after 140540612\t*\nstep 256 before 44812420 after 70660377\t\t*\nstep 512 before 24435438 after 36328275\t\t*\nstep 12345 before 2123924 after 2148062\t\t*\n\nbloat-o-meter delta for this patchset + patchset with related shmem cleanups\n\nbloat-o-meter: x86_64\n\nadd/remove: 4/3 grow/shrink: 5/6 up/down: 928/-939 (-11)\nfunction old new delta\nradix_tree_next_chunk - 499 +499\nshmem_unuse 428 554 +126\nshmem_radix_tree_replace 131 227 +96\nfind_get_pages_tag 354 419 +65\nfind_get_pages_contig 345 407 +62\nfind_get_pages 362 396 +34\n__kstrtab_radix_tree_next_chunk - 22 +22\n__ksymtab_radix_tree_next_chunk - 16 +16\n__kcrctab_radix_tree_next_chunk - 8 +8\nradix_tree_gang_lookup_slot 204 203 -1\nstatic.shmem_xattr_set 384 381 -3\nradix_tree_gang_lookup_tag_slot 208 191 -17\nradix_tree_gang_lookup 231 187 -44\nradix_tree_gang_lookup_tag 247 199 -48\nshmem_unlock_mapping 278 190 -88\n__lookup 217 - -217\n__lookup_tag 242 - -242\nradix_tree_locate_item 279 - -279\n\nbloat-o-meter: i386\n\nadd/remove: 3/3 grow/shrink: 8/9 up/down: 1075/-1275 (-200)\nfunction old new delta\nradix_tree_next_chunk - 757 +757\nshmem_unuse 352 449 +97\nfind_get_pages_contig 269 322 +53\nshmem_radix_tree_replace 113 154 +41\nfind_get_pages_tag 277 318 +41\ndcache_dir_lseek 426 458 +32\n__kstrtab_radix_tree_next_chunk - 22 +22\nvc_do_resize 968 977 +9\nsnd_pcm_lib_read1 725 733 +8\n__ksymtab_radix_tree_next_chunk - 8 +8\nnetlbl_cipsov4_list 1120 1127 +7\nfind_get_pages 293 291 -2\nnew_slab 467 459 -8\nbitfill_unaligned_rev 425 417 -8\nradix_tree_gang_lookup_tag_slot 177 146 -31\nblk_dump_cmd 267 229 -38\nradix_tree_gang_lookup_slot 212 134 -78\nshmem_unlock_mapping 221 128 -93\nradix_tree_gang_lookup_tag 275 162 -113\nradix_tree_gang_lookup 255 126 -129\n__lookup 227 - -227\n__lookup_tag 271 - -271\nradix_tree_locate_item 277 - -277\n\nThis patch:\n\nImplement a clean, simple and effective radix-tree iteration routine.\n\nIterating divided into two phases:\n* lookup next chunk in radix-tree leaf node\n* iterating through slots in this chunk\n\nMain iterator function radix_tree_next_chunk() returns pointer to first\nslot, and stores in the struct radix_tree_iter index of next-to-last slot.\n For tagged-iterating it also constuct bitmask of tags for retunted chunk.\n All additional logic implemented as static-inline functions and macroses.\n\nAlso adds radix_tree_find_next_bit() static-inline variant of\nfind_next_bit() optimized for small constant size arrays, because\nfind_next_bit() too heavy for searching in an array with one/two long\nelements.\n\n[akpm@linux-foundation.org: rework comments a bit]\nSigned-off-by: Konstantin Khlebnikov \u003ckhlebnikov@openvz.org\u003e\nTested-by: Hugh Dickins \u003chughd@google.com\u003e\nCc: Christoph Hellwig \u003chch@lst.de\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "8bc3bcc93a2b4e47d5d410146f6546bca6171663", "tree": "101f55a96f751749041c90c32ef1ba89f94dc4d1", "parents": [ "630d9c47274aa89bfa77fe6556d7818bdcb12992" ], "author": { "name": "Paul Gortmaker", "email": "paul.gortmaker@windriver.com", "time": "Wed Nov 16 21:29:17 2011 -0500" }, "committer": { "name": "Paul Gortmaker", "email": "paul.gortmaker@windriver.com", "time": "Wed Mar 07 15:04:04 2012 -0500" }, "message": "lib: reduce the use of module.h wherever possible\n\nFor files only using THIS_MODULE and/or EXPORT_SYMBOL, map\nthem onto including export.h -- or if the file isn\u0027t even\nusing those, then just delete the include. Fix up any implicit\ninclude dependencies that were being masked by module.h along\nthe way.\n\nSigned-off-by: Paul Gortmaker \u003cpaul.gortmaker@windriver.com\u003e\n" }, { "commit": "e2bdb933ab8b7db71c318a4ddcf78a9fffd61ecb", "tree": "23f39b8a9996135b893442c41d6da05c7988a0db", "parents": [ "928da837aca77a9d3cb5076bf07b3224b1ba293b" ], "author": { "name": "Hugh Dickins", "email": "hughd@google.com", "time": "Thu Jan 12 17:20:41 2012 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Thu Jan 12 20:13:12 2012 -0800" }, "message": "radix_tree: take radix_tree_path off stack\n\nDown, down in the deepest depths of GFP_NOIO page reclaim, we have\nshrink_page_list() calling __remove_mapping() calling __delete_from_\nswap_cache() or __delete_from_page_cache().\n\nYou would not expect those to need much stack, but in fact they call\nradix_tree_delete(): which declares a 192-byte radix_tree_path array on\nits stack (to record the node,offsets it visits when descending, in case\nit needs to ascend to update them). And if any tag is still set [1],\nthat calls radix_tree_tag_clear(), which declares a further such\n192-byte radix_tree_path array on the stack. (At least we have\ninterrupts disabled here, so won\u0027t then be pushing registers too.)\n\nThat was probably a good choice when most users were 32-bit (array of\nhalf the size), and adding fields to radix_tree_node would have bloated\nit unnecessarily. But nowadays many are 64-bit, and each\nradix_tree_node contains a struct rcu_head, which is only used when\nfreeing; whereas the radix_tree_path info is only used for updating the\ntree (deleting, clearing tags or setting tags if tagged) when a lock\nmust be held, of no interest when accessing the tree locklessly.\n\nSo add a parent pointer to the radix_tree_node, in union with the\nrcu_head, and remove all uses of the radix_tree_path. There would be\nspace in that union to save the offset when descending as before (we can\nargue that a lock must already be held to exclude other users), but\nrecalculating it when ascending is both easy (a constant shift and a\nconstant mask) and uncommon, so it seems better just to do that.\n\nTwo little optimizations: no need to decrement height when descending,\nadjusting shift is enough; and once radix_tree_tag_if_tagged() has set\ntag on a node and its ancestors, it need not ascend from that node\nagain.\n\nperf on the radix tree test harness reports radix_tree_insert() as 2%\nslower (now having to set parent), but radix_tree_delete() 24% faster.\nSurely that\u0027s an exaggeration from rtth\u0027s artificially low map shift 3,\nbut forcing it back to 6 still rates radix_tree_delete() 8% faster.\n\n[1] Can a pagecache tag (dirty, writeback or towrite) actually still be\nset at the time of radix_tree_delete()? Perhaps not if the filesystem is\nwell-behaved. But although I\u0027ve not tracked any stack overflow down to\nthis cause, I have observed a curious case in which a dirty tag is set\nand left set on tmpfs: page migration\u0027s migrate_page_copy() happens to\nuse __set_page_dirty_nobuffers() to set PageDirty on the newpage, and\nthat sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a\nfilesystem which doesn\u0027t use tags, except for this stack depth issue.\n\nSigned-off-by: Hugh Dickins \u003chughd@google.com\u003e\nCc: Jan Kara \u003cjack@suse.cz\u003e\nCc: Dave Chinner \u003cdavid@fromorbit.com\u003e\nCc: Mel Gorman \u003cmgorman@suse.de\u003e\nCc: Nai Xia \u003cnai.xia@gmail.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "3fa36acbced23c563345de3179dfe1775f15be5e", "tree": "83ad10f4dda426ee3708bc67c9fc88b6c1c8cc34", "parents": [ "0dabec93de633a87adfbbe1d800a4c56cd19d73b" ], "author": { "name": "Hugh Dickins", "email": "hughd@google.com", "time": "Mon Oct 31 17:07:02 2011 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Mon Oct 31 17:30:45 2011 -0700" }, "message": "radix_tree: clean away saw_unset_tag leftovers\n\nradix_tree_tag_get()\u0027s BUG (when it sees a tag after saw_unset_tag) was\nunsafe and removed in 2.6.34, but the pointless saw_unset_tag left behind.\n\nRemove it now, and return 0 as soon as we see unset tag - we already rely\nupon the root tag to be correct, returning 0 immediately if it\u0027s not set.\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": "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": "ac15ee691fe84cb46cbd2497ddcb10e246f7ee47", "tree": "6f9b37d61833b6170b71fb6ce8b3f2a14196dc33", "parents": [ "1817dc0370873caff77b924b53ae489edaf9b1e2" ], "author": { "name": "Toshiyuki Okajima", "email": "toshi.okajima@jp.fujitsu.com", "time": "Tue Jan 25 15:07:32 2011 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Wed Jan 26 10:50:04 2011 +1000" }, "message": "radix_tree: radix_tree_gang_lookup_tag_slot() may never return\n\nExecuted command: fsstress -d /mnt -n 600 -p 850\n\n crash\u003e bt\n PID: 7947 TASK: ffff880160546a70 CPU: 0 COMMAND: \"fsstress\"\n #0 [ffff8800dfc07d00] machine_kexec at ffffffff81030db9\n #1 [ffff8800dfc07d70] crash_kexec at ffffffff810a7952\n #2 [ffff8800dfc07e40] oops_end at ffffffff814aa7c8\n #3 [ffff8800dfc07e70] die_nmi at ffffffff814aa969\n #4 [ffff8800dfc07ea0] do_nmi_callback at ffffffff8102b07b\n #5 [ffff8800dfc07f10] do_nmi at ffffffff814aa514\n #6 [ffff8800dfc07f50] nmi at ffffffff814a9d60\n [exception RIP: __lookup_tag+100]\n RIP: ffffffff812274b4 RSP: ffff88016056b998 RFLAGS: 00000287\n RAX: 0000000000000000 RBX: 0000000000000002 RCX: 0000000000000006\n RDX: 000000000000001d RSI: ffff88016056bb18 RDI: ffff8800c85366e0\n RBP: ffff88016056b9c8 R8: ffff88016056b9e8 R9: 0000000000000000\n R10: 000000000000000e R11: ffff8800c8536908 R12: 0000000000000010\n R13: 0000000000000040 R14: ffffffffffffffc0 R15: ffff8800c85366e0\n ORIG_RAX: ffffffffffffffff CS: 0010 SS: 0018\n \u003cNMI exception stack\u003e\n #7 [ffff88016056b998] __lookup_tag at ffffffff812274b4\n #8 [ffff88016056b9d0] radix_tree_gang_lookup_tag_slot at ffffffff81227605\n #9 [ffff88016056ba20] find_get_pages_tag at ffffffff810fc110\n #10 [ffff88016056ba80] pagevec_lookup_tag at ffffffff81105e85\n #11 [ffff88016056baa0] write_cache_pages at ffffffff81104c47\n #12 [ffff88016056bbd0] generic_writepages at ffffffff81105014\n #13 [ffff88016056bbe0] do_writepages at ffffffff81105055\n #14 [ffff88016056bbf0] __filemap_fdatawrite_range at ffffffff810fb2cb\n #15 [ffff88016056bc40] filemap_write_and_wait_range at ffffffff810fb32a\n #16 [ffff88016056bc70] generic_file_direct_write at ffffffff810fb3dc\n #17 [ffff88016056bce0] __generic_file_aio_write at ffffffff810fcee5\n #18 [ffff88016056bda0] generic_file_aio_write at ffffffff810fd085\n #19 [ffff88016056bdf0] do_sync_write at ffffffff8114f9ea\n #20 [ffff88016056bf00] vfs_write at ffffffff8114fcf8\n #21 [ffff88016056bf30] sys_write at ffffffff81150691\n #22 [ffff88016056bf80] system_call_fastpath at ffffffff8100c0b2\n\nI think this root cause is the following:\n\n radix_tree_range_tag_if_tagged() always tags the root tag with settag\n if the root tag is set with iftag even if there are no iftag tags\n in the specified range (Of course, there are some iftag tags\n outside the specified range).\n\n\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\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[[[Detailed description]]]\n\n(1) Why cannot radix_tree_gang_lookup_tag_slot() return forever?\n\n__lookup_tag():\n - Return with 0.\n - Return with the index which is not bigger than the old one as the\n input parameter.\n\nTherefore the following \"while\" repeats forever because the above\nconditions cause \"ret\" not to be updated and the cur_index cannot be\nchanged into the bigger one.\n\n(So, radix_tree_gang_lookup_tag_slot() cannot return forever.)\n\nradix_tree_gang_lookup_tag_slot():\n1178 while (ret \u003c max_items) {\n1179 unsigned int slots_found;\n1180 unsigned long next_index; /* Index of next search */\n1181\n1182 if (cur_index \u003e max_index)\n1183 break;\n1184 slots_found \u003d __lookup_tag(node, results + ret,\n1185 cur_index, max_items - ret, \u0026next_index,\ntag);\n1186 ret +\u003d slots_found;\n\t\t\t// cannot update ret because slots_found \u003d\u003d 0.\n\t\t\t// so, this while loops forever.\n1187 if (next_index \u003d\u003d 0)\n1188 break;\n1189 cur_index \u003d next_index;\n1190 }\n\n(2) Why does __lookup_tag() return with 0 and doesn\u0027t update the index?\n\nAssuming the following:\n - the one of the slot in radix_tree_node is NULL.\n - the one of the tag which corresponds to the slot sets with\n PAGECACHE_TAG_TOWRITE or other.\n - In a certain height(!\u003d0), the corresponding index is 0.\n\na) __lookup_tag() notices that the tag is set.\n\n1005 static unsigned int\n1006 __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,\n1007 unsigned int max_items, unsigned long *next_index, unsigned int tag)\n1008 {\n1009 unsigned int nr_found \u003d 0;\n1010 unsigned int shift, height;\n1011\n1012 height \u003d slot-\u003eheight;\n1013 if (height \u003d\u003d 0)\n1014 goto out;\n1015 shift \u003d (height-1) * RADIX_TREE_MAP_SHIFT;\n1016\n1017 while (height \u003e 0) {\n1018 unsigned long i \u003d (index \u003e\u003e shift) \u0026 RADIX_TREE_MAP_MASK ;\n1019\n1020 for (;;) {\n1021 if (tag_get(slot, tag, i))\n1022 break;\n ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n* the index is not updated yet.\n\nb) __lookup_tag() notices that the slot is NULL.\n\n1023 index \u0026\u003d ~((1UL \u003c\u003c shift) - 1);\n1024 index +\u003d 1UL \u003c\u003c shift;\n1025 if (index \u003d\u003d 0)\n1026 goto out; /* 32-bit wraparound */\n1027 i++;\n1028 if (i \u003d\u003d RADIX_TREE_MAP_SIZE)\n1029 goto out;\n1030 }\n1031 height--;\n1032 if (height \u003d\u003d 0) { /* Bottom level: grab some items */\n...\n1055 }\n1056 shift -\u003d RADIX_TREE_MAP_SHIFT;\n1057 slot \u003d rcu_dereference_raw(slot-\u003eslots[i]);\n1058 if (slot \u003d\u003d NULL)\n1059 break;\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nc) __lookup_tag() doesn\u0027t update the index and return with 0.\n\n1060 }\n1061 out:\n1062 *next_index \u003d index;\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n1063 return nr_found;\n1064 }\n\n(3) Why is the slot NULL even if the tag is set?\n\nBecause radix_tree_range_tag_if_tagged() always sets the root tag with\nPAGECACHE_TAG_TOWRITE if the root tag is set with PAGECACHE_TAG_DIRTY,\neven if there is no tag which can be set with PAGECACHE_TAG_TOWRITE\nin the specified range (from *first_indexp to last_index). Of course,\nsome PAGECACHE_TAG_DIRTY nodes must exist outside the specified range.\n(radix_tree_range_tag_if_tagged() is called only from tag_pages_for_writeback())\n\n 640 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root\n*root,\n 641 unsigned long *first_indexp, unsigned long last_index,\n 642 unsigned long nr_to_tag,\n 643 unsigned int iftag, unsigned int settag)\n 644 {\n 645 unsigned int height \u003d root-\u003eheight;\n 646 struct radix_tree_path path[height];\n 647 struct radix_tree_path *pathp \u003d path;\n 648 struct radix_tree_node *slot;\n 649 unsigned int shift;\n 650 unsigned long tagged \u003d 0;\n 651 unsigned long index \u003d *first_indexp;\n 652\n 653 last_index \u003d min(last_index, radix_tree_maxindex(height));\n 654 if (index \u003e last_index)\n 655 return 0;\n 656 if (!nr_to_tag)\n 657 return 0;\n 658 if (!root_tag_get(root, iftag)) {\n 659 *first_indexp \u003d last_index + 1;\n 660 return 0;\n 661 }\n 662 if (height \u003d\u003d 0) {\n 663 *first_indexp \u003d last_index + 1;\n 664 root_tag_set(root, settag);\n 665 return 1;\n 666 }\n...\n 733 root_tag_set(root, settag);\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n 734 *first_indexp \u003d index;\n 735\n 736 return tagged;\n 737 }\n\nAs the result, there is no radix_tree_node which is set with\nPAGECACHE_TAG_TOWRITE but the root tag(radix_tree_root) is set with\nPAGECACHE_TAG_TOWRITE.\n\n[figure: inside radix_tree]\n(Please see the figure with typewriter font)\n\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 [roottag \u003d DIRTY]\n | tag\u003d0:NOTHING\n tag[0 0 0 1] 1:DIRTY\n [x x x +] 2:WRITEBACK\n | 3:DIRTY,WRITEBACK\n p 4:TOWRITE\n \u003c---\u003e 5:DIRTY,TOWRITE ...\n specified range (index: 0 to 2)\n\n* There is no DIRTY tag within the specified range.\n (But there is a DIRTY tag outside that range.)\n\n | | | | | | | | |\n after calling tag_pages_for_writeback()\n | | | | | | | | |\n v v v v v v v v v\n\n [roottag \u003d DIRTY,TOWRITE]\n | p is \"page\".\n tag[0 0 0 1] x is NULL.\n [x x x +] +- is a pointer to \"page\".\n |\n p\n\n* But TOWRITE tag is set on the root tag.\n\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\nAfter that, radix_tree_extend() via radix_tree_insert() is called\nwhen the page is added.\nThis function sets the new radix_tree_node with PAGECACHE_TAG_TOWRITE\nto succeed the status of the root tag.\n\n 246 static int radix_tree_extend(struct radix_tree_root *root, unsigned long\nindex)\n 247 {\n 248 struct radix_tree_node *node;\n 249 unsigned int height;\n 250 int tag;\n 251\n 252 /* Figure out what the height should be. */\n 253 height \u003d root-\u003eheight + 1;\n 254 while (index \u003e radix_tree_maxindex(height))\n 255 height++;\n 256\n 257 if (root-\u003ernode \u003d\u003d NULL) {\n 258 root-\u003eheight \u003d height;\n 259 goto out;\n 260 }\n 261\n 262 do {\n 263 unsigned int newheight;\n 264 if (!(node \u003d radix_tree_node_alloc(root)))\n 265 return -ENOMEM;\n 266\n 267 /* Increase the height. */\n 268 node-\u003eslots[0] \u003d radix_tree_indirect_to_ptr(root-\u003ernode);\n 269\n 270 /* Propagate the aggregated tag info into the new root */\n 271 for (tag \u003d 0; tag \u003c RADIX_TREE_MAX_TAGS; tag++) {\n 272 if (root_tag_get(root, tag))\n 273 tag_set(node, tag, 0);\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n 274 }\n\n\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 [roottag \u003d DIRTY,TOWRITE]\n | :\n tag[0 0 0 1] [0 0 0 0]\n [x x x +] [+ x x x]\n | |\n p p (new page)\n\n | | | | | | | | |\n after calling radix_tree_insert\n | | | | | | | | |\n v v v v v v v v v\n\n [roottag \u003d DIRTY,TOWRITE]\n |\n tag [5 0 0 0] * DIRTY and TOWRITE tags are\n [+ + x x] succeeded to the new node.\n | |\n tag [0 0 0 1] [0 0 0 0]\n [x x x +] [+ x x x]\n | |\n p p\n\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\nAfter that, the index 3 page is released by remove_from_page_cache().\nThen we can make the situation that the tag is set with PAGECACHE_TAG_TOWRITE\nand that the slot which corresponds to the tag is NULL.\n\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 [roottag \u003d DIRTY,TOWRITE]\n |\n tag [5 0 0 0]\n [+ + x x]\n | |\n tag [0 0 0 1] [0 0 0 0]\n [x x x +] [+ x x x]\n | |\n p p\n (remove)\n\n | | | | | | | | |\n after calling remove_page_cache\n | | | | | | | | |\n v v v v v v v v v\n\n [roottag \u003d DIRTY,TOWRITE]\n |\n tag [4 0 0 0] * Only DIRTY tag is cleared\n [x + x x] because no TOWRITE tag is existed\n | in the bottom node.\n [0 0 0 0]\n [+ x x x]\n |\n p\n\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\nTo solve this problem\n\nChange to that radix_tree_tag_if_tagged() doesn\u0027t tag the root tag\nif it doesn\u0027t set any tags within the specified range.\n\nLike this.\n\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 640 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root\n*root,\n 641 unsigned long *first_indexp, unsigned long last_index,\n 642 unsigned long nr_to_tag,\n 643 unsigned int iftag, unsigned int settag)\n 644 {\n 650 unsigned long tagged \u003d 0;\n...\n 733 \t if (tagged)\n^^^^^^^^^^^^^^^^^^^^^^^^\n 734 root_tag_set(root, settag);\n 735 *first_indexp \u003d index;\n 736\n 737 return tagged;\n 738 }\n\n\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\nSigned-off-by: Toshiyuki Okajima \u003ctoshi.okajima@jp.fujitsu.com\u003e\nAcked-by: Jan Kara \u003cjack@suse.cz\u003e\nCc: Dave Chinner \u003cdavid@fromorbit.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.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": "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": "d4f8f217b8a5d5bd02af979650418dca4caec472", "tree": "af047bfa9729c975e24cb7624107574e884d3a57", "parents": [ "2dfbf4dfbe47a484bae20456c12b40763b9b6af7", "773e3f93577ffb493fb7c39b1a6ecf39b5748e87" ], "author": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Thu Oct 07 09:43:11 2010 +0200" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Thu Oct 07 09:43:11 2010 +0200" }, "message": "Merge branch \u0027rcu/urgent\u0027 of git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-2.6-rcu into core/rcu\n" }, { "commit": "a6b9b4d50f492630443b38404d1f436b3b748c14", "tree": "f3512389c42cecfae50b6a315ec6ab1fa470e30d", "parents": [ "e36c886a0f9d624377977fa6cae309cfd7f362fa", "28457ee69c473a903e51e26c7bcd6f1e9eceb93e" ], "author": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Mon Aug 23 11:32:34 2010 +0200" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Mon Aug 23 11:32:34 2010 +0200" }, "message": "Merge branch \u0027rcu/next\u0027 of git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-2.6-rcu into core/rcu\n" }, { "commit": "9ee47476d6734c9deb9ae9ab05d963302f6b6150", "tree": "d6d5a54831322628427eb54cb3edc2f78a6125f4", "parents": [ "76be97c1fc945db08aae1f1b746012662d643e97", "144dcfc01221e1a79fa47ca897df7d5e3ab298e6" ], "author": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Sun Aug 22 19:55:14 2010 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Sun Aug 22 19:55:14 2010 -0700" }, "message": "Merge branch \u0027radix-tree\u0027 of git://git.kernel.org/pub/scm/linux/kernel/git/dgc/xfsdev\n\n* \u0027radix-tree\u0027 of git://git.kernel.org/pub/scm/linux/kernel/git/dgc/xfsdev:\n radix-tree: radix_tree_range_tag_if_tagged() can set incorrect tags\n radix-tree: clear all tags in radix_tree_node_rcu_free\n" }, { "commit": "144dcfc01221e1a79fa47ca897df7d5e3ab298e6", "tree": "70b0d0bf73815fb242502a562da3a8c7667843ba", "parents": [ "b6dd08652e2b70e73661c4975ae46398066c06f8" ], "author": { "name": "Dave Chinner", "email": "dchinner@redhat.com", "time": "Mon Aug 23 10:33:53 2010 +1000" }, "committer": { "name": "Dave Chinner", "email": "david@fromorbit.com", "time": "Mon Aug 23 10:33:53 2010 +1000" }, "message": "radix-tree: radix_tree_range_tag_if_tagged() can set incorrect tags\n\nCommit ebf8aa44beed48cd17893a83d92a4403e5f9d9e2 (\"radix-tree:\nomplement function radix_tree_range_tag_if_tagged\") does not safely\nset tags on on intermediate tree nodes. The code walks down the tree\nsetting tags before it has fully resolved the path to the leaf under\nthe assumption there will be a leaf slot with the tag set in the\nrange it is searching.\n\nUnfortunately, this is not a valid assumption - we can abort after\nsetting a tag on an intermediate node if we overrun the number of\ntags we are allowed to set in a batch, or stop scanning because we\nwe have passed the last scan index before we reach a leaf slot with\nthe tag we are searching for set.\n\nAs a result, we can leave the function with tags set on intemediate\nnodes which can be tripped over later by tag-based lookups. The\nresult of these stale tags is that lookup may end prematurely or\nlivelock because the lookup cannot make progress.\n\nThe fix for the problem involves reocrding the traversal path we\ntake to the leaf nodes, and only propagating the tags back up the\ntree once the tag is set in the leaf node slot. We are already\nrecording the path for efficient traversal, so there is no\nadditional overhead to do the intermediately node tag setting in\nthis manner.\n\nThis fixes a radix tree lookup livelock triggered by the new\nwriteback sync livelock avoidance code introduced in commit\nf446daaea9d4a420d16c606f755f3689dcb2d0ce (\"mm: implement writeback\nlivelock avoidance using page tagging\").\n\nSigned-off-by: Dave Chinner \u003cdchinner@redhat.com\u003e\nAcked-by: Jan Kara \u003cjack@suse.cz\u003e\n" }, { "commit": "b6dd08652e2b70e73661c4975ae46398066c06f8", "tree": "fa70f295a5074627a6b6dba11a8c8cf90d4e4b95", "parents": [ "da5cabf80e2433131bf0ed8993abc0f7ea618c73" ], "author": { "name": "Dave Chinner", "email": "dchinner@redhat.com", "time": "Mon Aug 23 10:33:19 2010 +1000" }, "committer": { "name": "Dave Chinner", "email": "david@fromorbit.com", "time": "Mon Aug 23 10:33:19 2010 +1000" }, "message": "radix-tree: clear all tags in radix_tree_node_rcu_free\n\nCommit f446daaea9d4a420d16c606f755f3689dcb2d0ce (\"mm: implement\nwriteback livelock avoidance using page tagging\") introduced a new\nradix tree tag, increasing the number of tags in each node from 2 to\n3. It did not, however, fix up the code in\nradix_tree_node_rcu_free() that cleans up after radix_tree_shrink()\nand hence could leave stray tags set in the new tag array.\n\nThe result is that the livelock avoidance code added in the the\nabove commit would hit stale tags when doing tag based lookups,\nresulting in livelocks when trying to traverse the tree.\n\nFix this problem in radix_tree_node_rcu_free() so it doesn\u0027t happen\nagain in the future by using a loop to walk all the tags up to\nRADIX_TREE_MAX_TAGS to clear the stray tags radix_tree_shrink()\nleaves behind.\n\nSigned-off-by: Dave Chinner \u003cdchinner@redhat.com\u003e\nAcked-by: Nick Piggin \u003cnpiggin@kernel.dk\u003e\nAcked-by: Jan Kara \u003cjack@suse.cz\u003e\n" }, { "commit": "d5ed3a4af77b851b6271ad3d9abc4c57fa3ce0f5", "tree": "f06894404e4af25051e8918bfd3fdac95974fc97", "parents": [ "f2e41e910320197d55b52e28d99a07130f2ae738" ], "author": { "name": "Jan Kara", "email": "jack@suse.cz", "time": "Thu Aug 19 14:13:33 2010 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Fri Aug 20 09:34:55 2010 -0700" }, "message": "lib/radix-tree.c: fix overflow in radix_tree_range_tag_if_tagged()\n\nWhen radix_tree_maxindex() is ~0UL, it can happen that scanning overflows\nindex and tree traversal code goes astray reading memory until it hits\nunreadable memory. Check for overflow and exit in that case.\n\nSigned-off-by: Jan Kara \u003cjack@suse.cz\u003e\nCc: Christoph Hellwig \u003chch@lst.de\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.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": "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": "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": "edcd1d843adf09d1742d49ae04fa51bb63ddd1c3", "tree": "7c0af77b470531f3a5e648cca232ec5821101385", "parents": [ "9d85cba718efeef9ca00ce3f7f34f5880737aa9b" ], "author": { "name": "Cesar Eduardo Barros", "email": "cesarb@cesarb.net", "time": "Wed May 26 14:44:27 2010 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Thu May 27 09:12:53 2010 -0700" }, "message": "radix-tree: fix radix_tree_prev_hole() underflow case\n\nradix_tree_prev_hole() used LONG_MAX to detect underflow; however,\nULONG_MAX is clearly what was intended, both here and by its only user\n(count_history_pages at mm/readahead.c).\n\nReviewed-by: Wu Fengguang \u003cfengguang.wu@intel.com\u003e\nSigned-off-by: Cesar Eduardo Barros \u003ccesarb@cesarb.net\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": "5a0e3ad6af8660be21ca98a971cd00f331318c05", "tree": "5bfb7be11a03176a87296a43ac6647975c00a1d1", "parents": [ "ed391f4ebf8f701d3566423ce8f17e614cde9806" ], "author": { "name": "Tejun Heo", "email": "tj@kernel.org", "time": "Wed Mar 24 17:04:11 2010 +0900" }, "committer": { "name": "Tejun Heo", "email": "tj@kernel.org", "time": "Tue Mar 30 22:02:32 2010 +0900" }, "message": "include cleanup: Update gfp.h and slab.h includes to prepare for breaking implicit slab.h inclusion from percpu.h\n\npercpu.h is included by sched.h and module.h and thus ends up being\nincluded when building most .c files. percpu.h includes slab.h which\nin turn includes gfp.h making everything defined by the two files\nuniversally available and complicating inclusion dependencies.\n\npercpu.h -\u003e slab.h dependency is about to be removed. Prepare for\nthis change by updating users of gfp and slab facilities include those\nheaders directly instead of assuming availability. As this conversion\nneeds to touch large number of source files, the following script is\nused as the basis of conversion.\n\n http://userweb.kernel.org/~tj/misc/slabh-sweep.py\n\nThe script does the followings.\n\n* Scan files for gfp and slab usages and update includes such that\n only the necessary includes are there. ie. if only gfp is used,\n gfp.h, if slab is used, slab.h.\n\n* When the script inserts a new include, it looks at the include\n blocks and try to put the new include such that its order conforms\n to its surrounding. It\u0027s put in the include block which contains\n core kernel includes, in the same order that the rest are ordered -\n alphabetical, Christmas tree, rev-Xmas-tree or at the end if there\n doesn\u0027t seem to be any matching order.\n\n* If the script can\u0027t find a place to put a new include (mostly\n because the file doesn\u0027t have fitting include block), it prints out\n an error message indicating which .h file needs to be added to the\n file.\n\nThe conversion was done in the following steps.\n\n1. The initial automatic conversion of all .c files updated slightly\n over 4000 files, deleting around 700 includes and adding ~480 gfp.h\n and ~3000 slab.h inclusions. The script emitted errors for ~400\n files.\n\n2. Each error was manually checked. Some didn\u0027t need the inclusion,\n some needed manual addition while adding it to implementation .h or\n embedding .c file was more appropriate for others. This step added\n inclusions to around 150 files.\n\n3. The script was run again and the output was compared to the edits\n from #2 to make sure no file was left behind.\n\n4. Several build tests were done and a couple of problems were fixed.\n e.g. lib/decompress_*.c used malloc/free() wrappers around slab\n APIs requiring slab.h to be added manually.\n\n5. The script was run on all .h files but without automatically\n editing them as sprinkling gfp.h and slab.h inclusions around .h\n files could easily lead to inclusion dependency hell. Most gfp.h\n inclusion directives were ignored as stuff from gfp.h was usually\n wildly available and often used in preprocessor macros. Each\n slab.h inclusion directive was examined and added manually as\n necessary.\n\n6. percpu.h was updated not to include slab.h.\n\n7. Build test were done on the following configurations and failures\n were fixed. CONFIG_GCOV_KERNEL was turned off for all tests (as my\n distributed build env didn\u0027t work with gcov compiles) and a few\n more options had to be turned off depending on archs to make things\n build (like ipr on powerpc/64 which failed due to missing writeq).\n\n * x86 and x86_64 UP and SMP allmodconfig and a custom test config.\n * powerpc and powerpc64 SMP allmodconfig\n * sparc and sparc64 SMP allmodconfig\n * ia64 SMP allmodconfig\n * s390 SMP allmodconfig\n * alpha SMP allmodconfig\n * um on x86_64 SMP allmodconfig\n\n8. percpu.h modifications were reverted so that it could be applied as\n a separate patch and serve as bisection point.\n\nGiven the fact that I had only a couple of failures from tests on step\n6, I\u0027m fairly confident about the coverage of this conversion patch.\nIf there is a breakage, it\u0027s likely to be something in one of the arch\nheaders which should be easily discoverable easily on most builds of\nthe specific arch.\n\nSigned-off-by: Tejun Heo \u003ctj@kernel.org\u003e\nGuess-its-ok-by: Christoph Lameter \u003ccl@linux-foundation.org\u003e\nCc: Ingo Molnar \u003cmingo@redhat.com\u003e\nCc: Lee Schermerhorn \u003cLee.Schermerhorn@hp.com\u003e\n" }, { "commit": "2676a58c980b7ef076cc9bbff3fd8c9d2d5417ea", "tree": "e33561a942ee89c7b6574e55f93c6e08282be54e", "parents": [ "af61b96b4f68f7ab25ebf34fed275fabf64f2edc" ], "author": { "name": "Paul E. McKenney", "email": "paulmck@linux.vnet.ibm.com", "time": "Mon Feb 22 17:04:54 2010 -0800" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Thu Feb 25 10:34:50 2010 +0100" }, "message": "radix-tree: Disable RCU lockdep checking in radix tree\n\nBecause the radix tree is used with many different locking\ndesigns, we cannot do any effective checking without changing\nthe radix-tree APIs. It might make sense to do this later, but\nonly if the RCU lockdep checking proves itself sufficiently\nvaluable.\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: \u003c1266887105-1528-10-git-send-email-paulmck@linux.vnet.ibm.com\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "285e728b0ac55b53a673114096168d6f74930167", "tree": "725dbd61cc9a3fecd593163d9b2cb0a061315cbf", "parents": [ "1bccf513ac49d44604ba1cddcc29f5886e70f1b6" ], "author": { "name": "David Howells", "email": "dhowells@redhat.com", "time": "Thu Nov 19 18:11:29 2009 +0000" }, "committer": { "name": "David Howells", "email": "dhowells@redhat.com", "time": "Thu Nov 19 18:11:29 2009 +0000" }, "message": "FS-Cache: Don\u0027t delete pending pages from the page-store tracking tree\n\nDon\u0027t delete pending pages from the page-store tracking tree, but rather send\nthem for another write as they\u0027ve presumably been updated.\n\nSigned-off-by: David Howells \u003cdhowells@redhat.com\u003e\n" }, { "commit": "b34df792b4e9e311db47fad27949095d0629c197", "tree": "c0d513580d5d714066666993224970916e1f9358", "parents": [ "7e311a207d596b9273d811149d6e3e14f05ac4c0" ], "author": { "name": "David Howells", "email": "dhowells@redhat.com", "time": "Thu Nov 19 18:11:14 2009 +0000" }, "committer": { "name": "David Howells", "email": "dhowells@redhat.com", "time": "Thu Nov 19 18:11:14 2009 +0000" }, "message": "FS-Cache: Use radix tree preload correctly in tracking of pages to be stored\n\n__fscache_write_page() attempts to load the radix tree preallocation pool for\nthe CPU it is on before calling radix_tree_insert(), as the insertion must be\ndone inside a pair of spinlocks.\n\nUse of the preallocation pool, however, is contingent on the radix tree being\ninitialised without __GFP_WAIT specified. __fscache_acquire_cookie() was\npassing GFP_NOFS to INIT_RADIX_TREE() - but that includes __GFP_WAIT.\n\nThe solution is to AND out __GFP_WAIT.\n\nAdditionally, the banner comment to radix_tree_preload() is altered to make\nnote of this prerequisite. Possibly there should be a WARN_ON() too.\n\nWithout this fix, I have seen the following recursive deadlock caused by\nradix_tree_insert() attempting to allocate memory inside the spinlocked\nregion, which resulted in FS-Cache being called back into to release memory -\nwhich required the spinlock already held.\n\n\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[ INFO: possible recursive locking detected ]\n2.6.32-rc6-cachefs #24\n---------------------------------------------\nnfsiod/7916 is trying to acquire lock:\n (\u0026cookie-\u003elock){+.+.-.}, at: [\u003cffffffffa0076872\u003e] __fscache_uncache_page+0xdb/0x160 [fscache]\n\nbut task is already holding lock:\n (\u0026cookie-\u003elock){+.+.-.}, at: [\u003cffffffffa0076acc\u003e] __fscache_write_page+0x15c/0x3f3 [fscache]\n\nother info that might help us debug this:\n5 locks held by nfsiod/7916:\n #0: (nfsiod){+.+.+.}, at: [\u003cffffffff81048290\u003e] worker_thread+0x19a/0x2e2\n #1: (\u0026task-\u003eu.tk_work#2){+.+.+.}, at: [\u003cffffffff81048290\u003e] worker_thread+0x19a/0x2e2\n #2: (\u0026cookie-\u003elock){+.+.-.}, at: [\u003cffffffffa0076acc\u003e] __fscache_write_page+0x15c/0x3f3 [fscache]\n #3: (\u0026object-\u003elock#2){+.+.-.}, at: [\u003cffffffffa0076b07\u003e] __fscache_write_page+0x197/0x3f3 [fscache]\n #4: (\u0026cookie-\u003estores_lock){+.+...}, at: [\u003cffffffffa0076b0f\u003e] __fscache_write_page+0x19f/0x3f3 [fscache]\n\nstack backtrace:\nPid: 7916, comm: nfsiod Not tainted 2.6.32-rc6-cachefs #24\nCall Trace:\n [\u003cffffffff8105ac7f\u003e] __lock_acquire+0x1649/0x16e3\n [\u003cffffffff81059ded\u003e] ? __lock_acquire+0x7b7/0x16e3\n [\u003cffffffff8100e27d\u003e] ? dump_trace+0x248/0x257\n [\u003cffffffff8105ad70\u003e] lock_acquire+0x57/0x6d\n [\u003cffffffffa0076872\u003e] ? __fscache_uncache_page+0xdb/0x160 [fscache]\n [\u003cffffffff8135467c\u003e] _spin_lock+0x2c/0x3b\n [\u003cffffffffa0076872\u003e] ? __fscache_uncache_page+0xdb/0x160 [fscache]\n [\u003cffffffffa0076872\u003e] __fscache_uncache_page+0xdb/0x160 [fscache]\n [\u003cffffffffa0077eb7\u003e] ? __fscache_check_page_write+0x0/0x71 [fscache]\n [\u003cffffffffa00b4755\u003e] nfs_fscache_release_page+0x86/0xc4 [nfs]\n [\u003cffffffffa00907f0\u003e] nfs_release_page+0x3c/0x41 [nfs]\n [\u003cffffffff81087ffb\u003e] try_to_release_page+0x32/0x3b\n [\u003cffffffff81092c2b\u003e] shrink_page_list+0x316/0x4ac\n [\u003cffffffff81058a9b\u003e] ? mark_held_locks+0x52/0x70\n [\u003cffffffff8135451b\u003e] ? _spin_unlock_irq+0x2b/0x31\n [\u003cffffffff81093153\u003e] shrink_inactive_list+0x392/0x67c\n [\u003cffffffff81058a9b\u003e] ? mark_held_locks+0x52/0x70\n [\u003cffffffff810934ca\u003e] shrink_list+0x8d/0x8f\n [\u003cffffffff81093744\u003e] shrink_zone+0x278/0x33c\n [\u003cffffffff81052c70\u003e] ? ktime_get_ts+0xad/0xba\n [\u003cffffffff8109453b\u003e] try_to_free_pages+0x22e/0x392\n [\u003cffffffff8109184c\u003e] ? isolate_pages_global+0x0/0x212\n [\u003cffffffff8108e16b\u003e] __alloc_pages_nodemask+0x3dc/0x5cf\n [\u003cffffffff810ae24a\u003e] cache_alloc_refill+0x34d/0x6c1\n [\u003cffffffff811bcf74\u003e] ? radix_tree_node_alloc+0x52/0x5c\n [\u003cffffffff810ae929\u003e] kmem_cache_alloc+0xb2/0x118\n [\u003cffffffff811bcf74\u003e] radix_tree_node_alloc+0x52/0x5c\n [\u003cffffffff811bcfd5\u003e] radix_tree_insert+0x57/0x19c\n [\u003cffffffffa0076b53\u003e] __fscache_write_page+0x1e3/0x3f3 [fscache]\n [\u003cffffffffa00b4248\u003e] __nfs_readpage_to_fscache+0x58/0x11e [nfs]\n [\u003cffffffffa009bb77\u003e] nfs_readpage_release+0x34/0x9b [nfs]\n [\u003cffffffffa009c0d9\u003e] nfs_readpage_release_full+0x32/0x4b [nfs]\n [\u003cffffffffa0006cff\u003e] rpc_release_calldata+0x12/0x14 [sunrpc]\n [\u003cffffffffa0006e2d\u003e] rpc_free_task+0x59/0x61 [sunrpc]\n [\u003cffffffffa0006f03\u003e] rpc_async_release+0x10/0x12 [sunrpc]\n [\u003cffffffff810482e5\u003e] worker_thread+0x1ef/0x2e2\n [\u003cffffffff81048290\u003e] ? worker_thread+0x19a/0x2e2\n [\u003cffffffff81352433\u003e] ? thread_return+0x3e/0x101\n [\u003cffffffffa0006ef3\u003e] ? rpc_async_release+0x0/0x12 [sunrpc]\n [\u003cffffffff8104bff5\u003e] ? autoremove_wake_function+0x0/0x34\n [\u003cffffffff81058d25\u003e] ? trace_hardirqs_on+0xd/0xf\n [\u003cffffffff810480f6\u003e] ? worker_thread+0x0/0x2e2\n [\u003cffffffff8104bd21\u003e] kthread+0x7a/0x82\n [\u003cffffffff8100beda\u003e] child_rip+0xa/0x20\n [\u003cffffffff8100b87c\u003e] ? restore_args+0x0/0x30\n [\u003cffffffff8104c2b9\u003e] ? add_wait_queue+0x15/0x44\n [\u003cffffffff8104bca7\u003e] ? kthread+0x0/0x82\n [\u003cffffffff8100bed0\u003e] ? child_rip+0x0/0x20\n\nSigned-off-by: David Howells \u003cdhowells@redhat.com\u003e\n" }, { "commit": "b72b71c6cb6ecc564d4d5f9c512a7df269837846", "tree": "9923a6e1d59f92825df87cfd2bbd613d0f47a5f7", "parents": [ "30639b6af85a92491b22dd14c17b14ca11da60e6" ], "author": { "name": "Huang Shijie", "email": "shijie8@gmail.com", "time": "Tue Jun 16 15:33:42 2009 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue Jun 16 19:47:49 2009 -0700" }, "message": "lib: do code optimization for radix_tree_lookup() and radix_tree_lookup_slot()\n\nradix_tree_lookup() and radix_tree_lookup_slot() have much the\nsame code except for the return value.\n\nIntroduce radix_tree_lookup_element() to do the real work.\n\n/*\n * is_slot \u003d\u003d 1 : search for the slot.\n * is_slot \u003d\u003d 0 : search for the node.\n */\nstatic void * radix_tree_lookup_element(struct radix_tree_root *root,\n\t\t\t\t\tunsigned long index, int is_slot);\n\nSigned-off-by: Huang Shijie \u003cshijie8@gmail.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: Christoph Lameter \u003ccl@linux-foundation.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\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": "57c44c5f6fb0a8002feb258c1af58e1a744b1fcb", "tree": "978bd46ca765a88e9c101cb705bbb0bf46015643", "parents": [ "76052749143d03006271cc0ce8205ad756917062", "5a9e67b1a19e08a82387709f325d26e07b891d27" ], "author": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Wed Jan 07 11:31:52 2009 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Wed Jan 07 11:31:52 2009 -0800" }, "message": "Merge branch \u0027for-linus\u0027 of git://git.kernel.org/pub/scm/linux/kernel/git/jikos/trivial\n\n* \u0027for-linus\u0027 of git://git.kernel.org/pub/scm/linux/kernel/git/jikos/trivial: (24 commits)\n trivial: chack -\u003e check typo fix in main Makefile\n trivial: Add a space (and a comma) to a printk in 8250 driver\n trivial: Fix misspelling of \"firmware\" in docs for ncr53c8xx/sym53c8xx\n trivial: Fix misspelling of \"firmware\" in powerpc Makefile\n trivial: Fix misspelling of \"firmware\" in usb.c\n trivial: Fix misspelling of \"firmware\" in qla1280.c\n trivial: Fix misspelling of \"firmware\" in a100u2w.c\n trivial: Fix misspelling of \"firmware\" in megaraid.c\n trivial: Fix misspelling of \"firmware\" in ql4_mbx.c\n trivial: Fix misspelling of \"firmware\" in acpi_memhotplug.c\n trivial: Fix misspelling of \"firmware\" in ipw2100.c\n trivial: Fix misspelling of \"firmware\" in atmel.c\n trivial: Fix misspelled firmware in Kconfig\n trivial: fix an -\u003e a typos in documentation and comments\n trivial: fix then -\u003e than typos in comments and documentation\n trivial: update Jesper Juhl CREDITS entry with new email\n trivial: fix singal -\u003e signal typo\n trivial: Fix incorrect use of \"loose\" in event.c\n trivial: printk: fix indentation of new_text_line declaration\n trivial: rtc-stk17ta8: fix sparse warning\n ...\n" }, { "commit": "8cef7d57a4a47ef7166acde05eea0bc4f723691c", "tree": "1ec446c6734e2fcd5cf0c98274a0183cc6290f9d", "parents": [ "40bc1f2dbc29ab88176a650e51f2246526105093" ], "author": { "name": "Harvey Harrison", "email": "harvey.harrison@gmail.com", "time": "Tue Jan 06 14:40:50 2009 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue Jan 06 15:59:11 2009 -0800" }, "message": "lib: radix_tree.c make percpu variable static\n\nradix_tree_preloads is unused outside of this file, make it static.\n\nNoticed by sparse:\nlib/radix-tree.c:84:1: warning: symbol \u0027per_cpu__radix_tree_preloads\u0027 was not declared. Should it be static?\n\nSigned-off-by: Harvey Harrison \u003charvey.harrison@gmail.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "8e6bdb7f8b478323525444ecee7a1477ff5b6639", "tree": "02ff4e100e37a3fb8cf12b9cb321abe4ded58f36", "parents": [ "2b6a2f535dda8c60721b78699618d13d6799a29e" ], "author": { "name": "Wu Fengguang", "email": "fengguang.wu@intel.com", "time": "Thu Nov 27 11:42:22 2008 +0100" }, "committer": { "name": "Jiri Kosina", "email": "jkosina@suse.cz", "time": "Tue Jan 06 11:28:05 2009 +0100" }, "message": "trivial: radix-tree: document wrap-around issue of radix_tree_next_hole()\n\nAnd some 80-line cleanups.\n\nSigned-off-by: Wu Fengguang \u003cwfg@linux.intel.com\u003e\nSigned-off-by: Jiri Kosina \u003cjkosina@suse.cz\u003e\n" }, { "commit": "51cc50685a4275c6a02653670af9f108a64e01cf", "tree": "819d47bd2b0c8a9d1835d863853804b0a0242b97", "parents": [ "d91958815d214ea365b98cbff6215383897edcb6" ], "author": { "name": "Alexey Dobriyan", "email": "adobriyan@gmail.com", "time": "Fri Jul 25 19:45:34 2008 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Sat Jul 26 12:00:07 2008 -0700" }, "message": "SL*B: drop kmem cache argument from constructor\n\nKmem cache passed to constructor is only needed for constructors that are\nthemselves multiplexeres. Nobody uses this \"feature\", nor does anybody uses\npassed kmem cache in non-trivial way, so pass only pointer to object.\n\nNon-trivial places are:\n\tarch/powerpc/mm/init_64.c\n\tarch/powerpc/mm/hugetlbpage.c\n\nThis is flag day, yes.\n\nSigned-off-by: Alexey Dobriyan \u003cadobriyan@gmail.com\u003e\nAcked-by: Pekka Enberg \u003cpenberg@cs.helsinki.fi\u003e\nAcked-by: Christoph Lameter \u003ccl@linux-foundation.org\u003e\nCc: Jon Tollefson \u003ckniht@linux.vnet.ibm.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: Matt Mackall \u003cmpm@selenic.com\u003e\n[akpm@linux-foundation.org: fix arch/powerpc/mm/hugetlbpage.c]\n[akpm@linux-foundation.org: fix mm/slab.c]\n[akpm@linux-foundation.org: fix ubifs]\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\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": "cde53535991fbb5c34a1566f25955297c1487b8d", "tree": "4f87e67b52c8761cfc421a619379263733b91159", "parents": [ "a926c063738f31c8c8b5c2b883812a40e7868072" ], "author": { "name": "Christoph Lameter", "email": "clameter@sgi.com", "time": "Fri Jul 04 09:59:22 2008 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Fri Jul 04 10:40:04 2008 -0700" }, "message": "Christoph has moved\n\nRemove all clameter@sgi.com addresses from the kernel tree since they will\nbecome invalid on June 27th. Change my maintainer email address for the\nslab allocators to cl@linux-foundation.org (which will be the new email\naddress for the future).\n\nSigned-off-by: Christoph Lameter \u003cclameter@sgi.com\u003e\nSigned-off-by: Christoph Lameter \u003ccl@linux-foundation.org\u003e\nCc: Pekka Enberg \u003cpenberg@cs.helsinki.fi\u003e\nCc: Stephen Rothwell \u003csfr@canb.auug.org.au\u003e\nCc: Matt Mackall \u003cmpm@selenic.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "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" }, { "commit": "488514d1798289f56f80ed018e246179fe500383", "tree": "e68d9f703dcbceed0cc08b03014d109d7ec3acd4", "parents": [ "e92adcba261fd391591bb63c1703185a04a41554" ], "author": { "name": "Christoph Lameter", "email": "clameter@sgi.com", "time": "Mon Apr 28 02:12:05 2008 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Mon Apr 28 08:58:17 2008 -0700" }, "message": "Remove set_migrateflags()\n\nMigrate flags must be set on slab creation as agreed upon when the antifrag\nlogic was reviewed. Otherwise some slabs of a slabcache will end up in the\nunmovable and others in the reclaimable section depending on which flag was\nactive when a new slab page was allocated.\n\nThis likely slid in somehow when antifrag was merged. Remove it.\n\nThe buffer_heads are always allocated with __GFP_RECLAIMABLE because the\nSLAB_RECLAIM_ACCOUNT option is set. The set_migrateflags() never had any\neffect there.\n\nRadix tree allocations are not directly reclaimable but they are allocated\nwith __GFP_RECLAIMABLE set on each allocation. We now set\nSLAB_RECLAIM_ACCOUNT on radix tree slab creation making sure that radix\ntree slabs are consistently placed in the reclaimable section. Radix tree\nslabs will also be accounted as such.\n\nThere is then no user left of set_migratepages. So remove it.\n\nSigned-off-by: Christoph Lameter \u003cclameter@sgi.com\u003e\nCc: Mel Gorman \u003cmel@csn.ul.ie\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "e2848a0efedef4dad52d1334d37f8719cd6268fd", "tree": "f5d2b600b1275793e7c490f34ae9ec902af138b5", "parents": [ "e31d9eb5c17ae3b80f9e9403f8a5eaf6dba879c9" ], "author": { "name": "Nick Piggin", "email": "npiggin@suse.de", "time": "Mon Feb 04 22:29:10 2008 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.linux-foundation.org", "time": "Tue Feb 05 09:44:17 2008 -0800" }, "message": "radix-tree: avoid atomic allocations for preloaded insertions\n\nMost pagecache (and some other) radix tree insertions have the great\nopportunity to preallocate a few nodes with relaxed gfp flags. But the\npreallocation is squandered when it comes time to allocate a node, we\ndefault to first attempting a GFP_ATOMIC allocation -- that doesn\u0027t\nnormally fail, but it can eat into atomic memory reserves that we don\u0027t\nneed to be using.\n\nAnother upshot of this is that it removes the sometimes highly contended\nzone-\u003elock from underneath tree_lock. Pagecache insertions are always\nperformed with a radix tree preload, and after this change, such a\nsituation will never fall back to kmem_cache_alloc within\nradix_tree_node_alloc.\n\nDavid Miller reports seeing this allocation fail on a highly threaded\nsparc64 system:\n\n[527319.459981] dd: page allocation failure. order:0, mode:0x20\n[527319.460403] Call Trace:\n[527319.460568] [00000000004b71e0] __slab_alloc+0x1b0/0x6a8\n[527319.460636] [00000000004b7bbc] kmem_cache_alloc+0x4c/0xa8\n[527319.460698] [000000000055309c] radix_tree_node_alloc+0x20/0x90\n[527319.460763] [0000000000553238] radix_tree_insert+0x12c/0x260\n[527319.460830] [0000000000495cd0] add_to_page_cache+0x38/0xb0\n[527319.460893] [00000000004e4794] mpage_readpages+0x6c/0x134\n[527319.460955] [000000000049c7fc] __do_page_cache_readahead+0x170/0x280\n[527319.461028] [000000000049cc88] ondemand_readahead+0x208/0x214\n[527319.461094] [0000000000496018] do_generic_mapping_read+0xe8/0x428\n[527319.461152] [0000000000497948] generic_file_aio_read+0x108/0x170\n[527319.461217] [00000000004badac] do_sync_read+0x88/0xd0\n[527319.461292] [00000000004bb5cc] vfs_read+0x78/0x10c\n[527319.461361] [00000000004bb920] sys_read+0x34/0x60\n[527319.461424] [0000000000406294] linux_sparc_syscall32+0x3c/0x40\n\nThe calltrace is significant: __do_page_cache_readahead allocates a number\nof pages with GFP_KERNEL, and hence it should have reclaimed sufficient\nmemory to satisfy GFP_ATOMIC allocations. However after the list of pages\ngoes to mpage_readpages, there can be significant intervals (including disk\nIO) before all the pages are inserted into the radix-tree. So the reserves\ncan easily be depleted at that point. The patch is confirmed to fix the\nproblem.\n\nSigned-off-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nCc: \"David S. Miller\" \u003cdavem@davemloft.net\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "430d275a399175c7c0673459738979287ec1fd22", "tree": "e38f1e8b69ba5cad535a14edec4d0ff213bbc477", "parents": [ "22e48eaf587d044ba311a73c6fe0d0deaa8fdb63" ], "author": { "name": "Peter Lund", "email": "firefly@vax64.dk", "time": "Tue Oct 16 23:29:35 2007 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.linux-foundation.org", "time": "Wed Oct 17 08:42:56 2007 -0700" }, "message": "avoid negative (and full-width) shifts in radix-tree.c\n\nNegative shifts are not allowed in C (the result is undefined). Same thing\nwith full-width shifts.\n\nIt works on most platforms but not on the VAX with gcc 4.0.1 (it results in an\n\"operand reserved\" fault).\n\nShifting by more than the width of the value on the left is also not\nallowed. I think the extra \u0027\u003e\u003e 1\u0027 tacked on at the end in the original\ncode was an attempt to work around that. Getting rid of that is an extra\nfeature of this patch.\n\nHere\u0027s the chapter and verse, taken from the final draft of the C99\nstandard (\"6.5.7 Bitwise shift operators\", paragraph 3):\n\n \"The integer promotions are performed on each of the operands. The\n type of the result is that of the promoted left operand. If the\n value of the right operand is negative or is greater than or equal\n to the width of the promoted left operand, the behavior is\n undefined.\"\n\nThank you to Jan-Benedict Glaw, Christoph Hellwig, Maciej Rozycki, Pekka\nEnberg, Andreas Schwab, and Christoph Lameter for review. Special thanks\nto Andreas for spotting that my fix only removed half the undefined\nbehaviour.\n\nSigned-off-by: Peter Lund \u003cfirefly@vax64.dk\u003e\nChristoph Lameter \u003cclameter@sgi.com\u003e\nCc: Christoph Hellwig \u003chch@infradead.org\u003e\nCc: \"Maciej W. Rozycki\" \u003cmacro@linux-mips.org\u003e\nCc: Pekka Enberg \u003cpenberg@cs.helsinki.fi\u003e\nCc: Andreas Schwab \u003cschwab@suse.de\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: WU Fengguang \u003cwfg@mail.ustc.edu.cn\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "4ba9b9d0ba0a49d91fa6417c7510ee36f48cf957", "tree": "191b4f45f926e44b882b1e87a9a85dc12230b892", "parents": [ "b811c202a0edadaac7242ab834fe7ba409978ae7" ], "author": { "name": "Christoph Lameter", "email": "clameter@sgi.com", "time": "Tue Oct 16 23:25:51 2007 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.linux-foundation.org", "time": "Wed Oct 17 08:42:45 2007 -0700" }, "message": "Slab API: remove useless ctor parameter and reorder parameters\n\nSlab constructors currently have a flags parameter that is never used. And\nthe order of the arguments is opposite to other slab functions. The object\npointer is placed before the kmem_cache pointer.\n\nConvert\n\n ctor(void *object, struct kmem_cache *s, unsigned long flags)\n\nto\n\n ctor(struct kmem_cache *s, void *object)\n\nthroughout the kernel\n\n[akpm@linux-foundation.org: coupla fixes]\nSigned-off-by: Christoph Lameter \u003cclameter@sgi.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "e12ba74d8ff3e2f73a583500d7095e406df4d093", "tree": "a0d3385b65f0b3e1e00b0bbf11b75e7538a93edb", "parents": [ "c361be55b3128474aa66d31092db330b07539103" ], "author": { "name": "Mel Gorman", "email": "mel@csn.ul.ie", "time": "Tue Oct 16 01:25:52 2007 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.linux-foundation.org", "time": "Tue Oct 16 09:43:00 2007 -0700" }, "message": "Group short-lived and reclaimable kernel allocations\n\nThis patch marks a number of allocations that are either short-lived such as\nnetwork buffers or are reclaimable such as inode allocations. When something\nlike updatedb is called, long-lived and unmovable kernel allocations tend to\nbe spread throughout the address space which increases fragmentation.\n\nThis patch groups these allocations together as much as possible by adding a\nnew MIGRATE_TYPE. The MIGRATE_RECLAIMABLE type is for allocations that can be\nreclaimed on demand, but not moved. i.e. they can be migrated by deleting\nthem and re-reading the information from elsewhere.\n\nSigned-off-by: Mel Gorman \u003cmel@csn.ul.ie\u003e\nCc: Andy Whitcroft \u003capw@shadowen.org\u003e\nCc: Christoph Lameter \u003cclameter@sgi.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "26fb1589cb0aaec3a0b4418c54f30c1a2b1781f6", "tree": "1486600f31a6f1387f4f5db276684f0b727eec89", "parents": [ "a4b0672db3a698d0684ee6e54f44e2e162a3da1b" ], "author": { "name": "Jeff Moyer", "email": "jmoyer@redhat.com", "time": "Tue Oct 16 01:24:49 2007 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.linux-foundation.org", "time": "Tue Oct 16 09:42:54 2007 -0700" }, "message": "fix the max path calculation in radix-tree.c\n\nA while back, Nick Piggin introduced a patch to reduce the node memory\nusage for small files (commit cfd9b7df4abd3257c9e381b0e445817b26a51c0c):\n\n-#define RADIX_TREE_MAP_SHIFT\t6\n+#define RADIX_TREE_MAP_SHIFT\t(CONFIG_BASE_SMALL ? 4 : 6)\n\nUnfortunately, he didn\u0027t take into account the fact that the\ncalculation of the maximum path was based on an assumption of having\nto round up:\n\n#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)\n\nSo, if CONFIG_BASE_SMALL is set, you will end up with a\nRADIX_TREE_MAX_PATH that is one greater than necessary. The practical\nupshot of this is just a bit of wasted memory (one long in the\nheight_to_maxindex array, an extra pre-allocated radix tree node per\ncpu, and extra stack usage in a couple of functions), but it seems\nworth getting right.\n\nIt\u0027s also worth noting that I never build with CONFIG_BASE_SMALL.\nWhat I did to test this was duplicate the code in a small user-space\nprogram and check the results of the calculations for max path and the\ncontents of the height_to_maxindex array.\n\nSigned-off-by: Jeff Moyer \u003cjmoyer@redhat.com\u003e\nAcked-by: Nick Piggin \u003cnickpiggin@yahoo.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": "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": "20c2df83d25c6a95affe6157a4c9cac4cf5ffaac", "tree": "415c4453d2b17a50abe7a3e515177e1fa337bd67", "parents": [ "64fb98fc40738ae1a98bcea9ca3145b89fb71524" ], "author": { "name": "Paul Mundt", "email": "lethal@linux-sh.org", "time": "Fri Jul 20 10:11:58 2007 +0900" }, "committer": { "name": "Paul Mundt", "email": "lethal@linux-sh.org", "time": "Fri Jul 20 10:11:58 2007 +0900" }, "message": "mm: Remove slab destructors from kmem_cache_create().\n\nSlab destructors were no longer supported after Christoph\u0027s\nc59def9f222d44bb7e2f0a559f2906191a0862d7 change. They\u0027ve been\nBUGs for both slab and slub, and slob never supported them\neither.\n\nThis rips out support for the dtor pointer from kmem_cache_create()\ncompletely and fixes up every single callsite in the kernel (there were\nabout 224, not including the slab allocator definitions themselves,\nor the documentation references).\n\nSigned-off-by: Paul Mundt \u003clethal@linux-sh.org\u003e\n" }, { "commit": "d7f0923d83dcabfc063257a281529cdbcd5eedb5", "tree": "e45e8134c4d3b8c9a80d652063aa296fc222f31d", "parents": [ "faa63e9584df41020440756b8b90b7b63f95e4f6" ], "author": { "name": "David Chinner", "email": "dgc@sgi.com", "time": "Sat Jul 14 16:05:04 2007 +1000" }, "committer": { "name": "Tim Shimmin", "email": "tes@chook.melbourne.sgi.com", "time": "Sat Jul 14 16:05:04 2007 +1000" }, "message": "[LIB]: export radix_tree_preload()\n\nXFS filestreams functionality uses radix trees and the preload\nfunctions. XFS can be built as a module and hence we need\nradix_tree_preload() exported. radix_tree_preload_end() is a\nstatic inline, so it doesn\u0027t need exporting.\n\nSigned-Off-By: Dave Chinner \u003cdgc@sgi.com\u003e\nSigned-Off-By: Tim Shimmin \u003ctes@sgi.com\u003e\n" }, { "commit": "8bb7844286fb8c9fce6f65d8288aeb09d03a5e0d", "tree": "f4e305edaedbde05774bb1e4acd89a9475661d2e", "parents": [ "f37bc2712b54ec641e0c0c8634f1a4b61d9956c0" ], "author": { "name": "Rafael J. Wysocki", "email": "rjw@sisk.pl", "time": "Wed May 09 02:35:10 2007 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.linux-foundation.org", "time": "Wed May 09 12:30:56 2007 -0700" }, "message": "Add suspend-related notifications for CPU hotplug\n\nSince nonboot CPUs are now disabled after tasks and devices have been\nfrozen and the CPU hotplug infrastructure is used for this purpose, we need\nspecial CPU hotplug notifications that will help the CPU-hotplug-aware\nsubsystems distinguish normal CPU hotplug events from CPU hotplug events\nrelated to a system-wide suspend or resume operation in progress. This\npatch introduces such notifications and causes them to be used during\nsuspend and resume transitions. It also changes all of the\nCPU-hotplug-aware subsystems to take these notifications into consideration\n(for now they are handled in the same way as the corresponding \"normal\"\nones).\n\n[oleg@tv-sign.ru: cleanups]\nSigned-off-by: Rafael J. Wysocki \u003crjw@sisk.pl\u003e\nCc: Gautham R Shenoy \u003cego@in.ibm.com\u003e\nCc: Pavel Machek \u003cpavel@ucw.cz\u003e\nSigned-off-by: Oleg Nesterov \u003coleg@tv-sign.ru\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "02316067852187b8bec781bec07410e91af79627", "tree": "856e3f4610c91a6548bf3bf5c70ecbc0b28a4145", "parents": [ "a38a44c1a93078fc5fadc4ac2df8dea4697069e2" ], "author": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Wed Dec 06 20:38:17 2006 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.osdl.org", "time": "Thu Dec 07 08:39:39 2006 -0800" }, "message": "[PATCH] hotplug CPU: clean up hotcpu_notifier() use\n\nThere was lots of #ifdef noise in the kernel due to hotcpu_notifier(fn,\nprio) not correctly marking \u0027fn\u0027 as used in the !HOTPLUG_CPU case, and thus\ngenerating compiler warnings of unused symbols, hence forcing people to add\n#ifdefs.\n\nthe compiler can skip truly unused functions just fine:\n\n text data bss dec hex filename\n 1624412 728710 3674856 6027978 5bfaca vmlinux.before\n 1624412 728710 3674856 6027978 5bfaca vmlinux.after\n\n[akpm@osdl.org: topology.c fix]\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\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": "e18b890bb0881bbab6f4f1a6cd20d9c60d66b003", "tree": "4828be07e1c24781c264b42c5a75bcd968223c3f", "parents": [ "441e143e95f5aa1e04026cb0aa71c801ba53982f" ], "author": { "name": "Christoph Lameter", "email": "clameter@sgi.com", "time": "Wed Dec 06 20:33:20 2006 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@woody.osdl.org", "time": "Thu Dec 07 08:39:25 2006 -0800" }, "message": "[PATCH] slab: remove kmem_cache_t\n\nReplace all uses of kmem_cache_t with struct kmem_cache.\n\nThe patch was generated using the following script:\n\n\t#!/bin/sh\n\t#\n\t# Replace one string by another in all the kernel sources.\n\t#\n\n\tset -e\n\n\tfor file in `find * -name \"*.c\" -o -name \"*.h\"|xargs grep -l $1`; do\n\t\tquilt add $file\n\t\tsed -e \"1,\\$s/$1/$2/g\" $file \u003e/tmp/$$\n\t\tmv /tmp/$$ $file\n\t\tquilt refresh\n\tdone\n\nThe script was run like this\n\n\tsh replace kmem_cache_t \"struct kmem_cache\"\n\nSigned-off-by: Christoph Lameter \u003cclameter@sgi.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "20241ad409fbc42d9e7f92f5fdb4783b7f1b36eb", "tree": "2f6a12f447a259ba820ab055926bfb22400cb67b", "parents": [ "fa1f5ea860af34d74c1475eddde3364e71fac15d" ], "author": { "name": "Al Viro", "email": "viro@ftp.linux.org.uk", "time": "Tue Oct 10 22:47:57 2006 +0100" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Tue Oct 10 15:37:23 2006 -0700" }, "message": "[PATCH] gfp annotations: radix_tree_root\n\nstruct radix_tree_root has unused upper bits of -\u003egfp_mask reused for\ntags bitmap. Annotated.\n\nSigned-off-by: Al Viro \u003cviro@zeniv.linux.org.uk\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "e5dcd90b53d601a04482db9800336a0ccf190880", "tree": "b84936f569134612797cfa069401fe88dcac152d", "parents": [ "3419b23a919698f75944d3e0d97eb1d9c51e4bb6" ], "author": { "name": "Wu Fengguang", "email": "wfg@mail.ustc.edu.cn", "time": "Sun Jun 25 05:48:14 2006 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Sun Jun 25 10:01:13 2006 -0700" }, "message": "[PATCH] radixtree: normalize radix_tree_tag_get() return value\n\nIn radix_tree_tag_get(), return normalized value of 0/1, as indicated\nby its comment.\n\nSigned-off-by: Wu Fengguang \u003cwfg@mail.ustc.edu.cn\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "4c91c3648c620003cb7b21b8858f36cd6132e168", "tree": "6572fedb9a18ba0b31695f1ba30a219621b6f20a", "parents": [ "58ce1fd5805647a58a050bbbbd2252ea5ecb47b3" ], "author": { "name": "Peter Zijlstra", "email": "a.p.zijlstra@chello.nl", "time": "Fri Jun 23 02:03:25 2006 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Fri Jun 23 07:42:49 2006 -0700" }, "message": "[PATCH] buglet in radix_tree_tag_set\n\nThe comment states: \u0027Setting a tag on a not-present item is a BUG.\u0027 Hence\nif \u0027index\u0027 is larger than the maxindex; the item _cannot_ be presen; it\nshould also be a BUG.\n\nAlso, this allows the following statement (assume a fresh tree):\n\n radix_tree_tag_set(root, 16, 1);\n\nto fail silently, but when preceded by:\n\n radix_tree_insert(root, 32, item);\n\nit would BUG, because the height has been extended by the insert.\n\nIn neither case was 16 present.\n\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nAcked-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": "cfd9b7df4abd3257c9e381b0e445817b26a51c0c", "tree": "cd419f98fbf555fbcd92baf7ca41d45a8744f071", "parents": [ "612d6c19db2fd0dc97b0fa370613ecd4a305ffc3" ], "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: small\n\nReduce radix tree node memory usage by about a factor of 4 for small files\n(\u003c 64K). There are pointer traversal and memory usage costs for large\nfiles with dense pagecache.\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": "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": "90f9dd8f72773152b69042debd6b9ed6d224703a", "tree": "36a122a5672e0bb5f8f77e19619954f6073985b3", "parents": [ "d89b8f40fca43cab829fea5c0e7d3951db2fb4bd" ], "author": { "name": "NeilBrown", "email": "neilb@suse.de", "time": "Thu Feb 16 14:43:01 2006 +1100" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Thu Feb 16 08:45:50 2006 -0800" }, "message": "[PATCH] Fix over-zealous tag clearing in radix_tree_delete\n\nIf a tag is set for a node being deleted from a radix_tree, then that\ntag gets cleared from the parent of the node, even if it is set for some\nsiblings of the node begin deleted.\n\nThis patch changes the logic to include a test for any_tag_set similar\nto the logic a little futher down. Care is taken to ensure that\n\u0027nr_cleared_tags\u0027 remains equals to the number of entries in the \u0027tags\u0027\narray which are set to \u00270\u0027 (which means that this tag is not set in the\ntree below pathp-\u003enode, and should be cleared at pathp-\u003enode and\npossibly above.\n\n[ Nick says: \"Linus FYI, I was able to modify the radix tree test\n harness to catch the bug and can no longer trigger it after the fix.\n Resulting code passes all other harness tests as well of course.\" ]\n\nSigned-off-by: Neil Brown \u003cneilb@suse.de\u003e\nAcked-by: Nick Piggin \u003cnpiggin@suse.de\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "a5f51c966720fa519c6ce69b169107dbc5769cdf", "tree": "084928ba54750ba3959e376988b503f02ca698b8", "parents": [ "d5274261ea46f0aae93820fe36628249120d2f75" ], "author": { "name": "Nick Piggin", "email": "nickpiggin@yahoo.com.au", "time": "Sun Jan 08 01:01:41 2006 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Sun Jan 08 20:13:41 2006 -0800" }, "message": "[PATCH] radix-tree: reduce tree height upon partial truncation\n\nShrink the height of a radix tree when it is partially truncated - we only do\nshrinkage of full truncation at present.\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": "d5274261ea46f0aae93820fe36628249120d2f75", "tree": "e95c41295270c55ef27a3534894f066f31719ecc", "parents": [ "6e954b9e90c3a7157c0c1457dd3919e2a1345d23" ], "author": { "name": "Nick Piggin", "email": "nickpiggin@yahoo.com.au", "time": "Sun Jan 08 01:01:41 2006 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Sun Jan 08 20:13:41 2006 -0800" }, "message": "[PATCH] radix tree: early termination of tag clearing\n\nCorrectly determine the tags to be cleared in radix_tree_delete() so we\ndon\u0027t keep moving up the tree clearing tags that we don\u0027t need to. For\nexample, if a tag is simply not set in the deleted item, nor anywhere up\nthe tree, radix_tree_delete() would attempt to clear it up the entire\nheight of the tree.\n\nAlso, tag_set() was made conditional so as not to dirty too many cachelines\nhigh up in the radix tree. Instead, put this logic into\nradix_tree_tag_set().\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": "6e954b9e90c3a7157c0c1457dd3919e2a1345d23", "tree": "61812f63c0b9a354fb9e7f8e9c11cb350afc4c4f", "parents": [ "d4829cd5b4bd1ea58ba1bebad44d562f4027c290" ], "author": { "name": "Nick Piggin", "email": "nickpiggin@yahoo.com.au", "time": "Sun Jan 08 01:01:40 2006 -0800" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Sun Jan 08 20:13:41 2006 -0800" }, "message": "[PATCH] radix tree: code consolidation\n\nIntroduce helper any_tag_set() rather than repeat the same code sequence 4\ntimes.\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": "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": "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": "32605a18152b246df483fadc1c23854addde8755", "tree": "cb13f4d0d9040120b5ef6a90c8b174a0619756d0", "parents": [ "201b6264ff3865090747f58f48e087c3a35e0dbc" ], "author": { "name": "Marcelo Tosatti", "email": "marcelo.tosatti@cyclades.com", "time": "Tue Sep 06 15:16:48 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Wed Sep 07 16:57:21 2005 -0700" }, "message": "[PATCH] radix_tag_get(): differentiate between no present node and tag unset cases\n\nSimple patch to radix_tree_tag_get() to return different values for non\npresent node and tag unset.\n\nThe function is not used by any in-kernel callers (yet), but this\ninformation is definitely useful.\n\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "201b6264ff3865090747f58f48e087c3a35e0dbc", "tree": "0633a10394d402779465c821d9de57a5e3df2a4b", "parents": [ "987132bb0b136c93cef5f195e7371bb98df64709" ], "author": { "name": "Christoph Lameter", "email": "clameter@engr.sgi.com", "time": "Tue Sep 06 15:16:46 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Wed Sep 07 16:57:21 2005 -0700" }, "message": "[PATCH] radix-tree: Remove unnecessary indirections and clean up code\n\n- There is frequent use of indirections in the radix code. This patch\n removes those indirections, makes the code more readable and allows\n the compilers to generate better code.\n\n- Removing indirections allows the removal of several casts.\n\n- Removing indirections allows the reduction of the radix_tree_path\n size from 3 to 2 words.\n\n- Use pathp-\u003e consistently.\n\n- Remove unnecessary tmp variable in radix_tree_insert\n\n- Separate the upper layer processing from the lowest layer in __lookup()\n in order to make it easier to understand what is going on and allow\n compilers to generate better code for the loop.\n\nSigned-off-by: Christoph Lameter \u003cclameter@sgi.com\u003e\nCc: Nick Piggin \u003cnickpiggin@yahoo.com.au\u003e\nCc: James Bottomley \u003cJames.Bottomley@steeleye.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "6c036527a630720063b67d9a65455e8caca2c8fa", "tree": "316e947f5f4efcda0205e48044ed1d12665eaed1", "parents": [ "0db925af1db5f3dfe1691c35b39496e2baaff9c9" ], "author": { "name": "Christoph Lameter", "email": "christoph@lameter.com", "time": "Thu Jul 07 17:56:59 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@g5.osdl.org", "time": "Thu Jul 07 18:23:46 2005 -0700" }, "message": "[PATCH] mostly_read data section\n\nAdd a new section called \".data.read_mostly\" for data items that are read\nfrequently and rarely written to like cpumaps etc.\n\nIf these maps are placed in the .data section then these frequenly read\nitems may end up in cachelines with data is is frequently updated. In that\ncase all processors in an SMP system must needlessly reload the cachelines\nagain and again containing elements of those frequently used variables.\n\nThe ability to share these cachelines will allow each cpu in an SMP system\nto keep local copies of those shared cachelines thereby optimizing\nperformance.\n\nSigned-off-by: Alok N Kataria \u003calokk@calsoftinc.com\u003e\nSigned-off-by: Shobhit Dayal \u003cshobhit@calsoftinc.com\u003e\nSigned-off-by: Christoph Lameter \u003cchristoph@scalex86.org\u003e\nSigned-off-by: Shai Fultheim \u003cshai@scalex86.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" } ] }