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