{"push_id":1336318651,"size":10,"distinct_size":10,"ref":"refs/heads/sto","head":"786e0a48fc6ce029e0a1096ae7ae482f1e693650","before":"d34c17287acde834541d1f9614d4d2f43f65ab1c","commits":[{"sha":"8ad0f47521bbbba231bbd717cf525580fe833143","author":{"name":"Joonsoo Kim","email":"3886d6c634fa2d42cac9fa2072ec015ddc12e785@gmail.com"},"message":"mm/slub: don't wait for high-order page allocation\n\nDescription is almost copied from commit fb05e7a89f50 (\"net: don't wait\nfor order-3 page allocation\").\n\nI saw excessive direct memory reclaim/compaction triggered by slub.  This\ncauses performance issues and add latency.  Slub uses high-order\nallocation to reduce internal fragmentation and management overhead.  But,\ndirect memory reclaim/compaction has high overhead and the benefit of\nhigh-order allocation can't compensate the overhead of both work.\n\nThis patch makes auxiliary high-order allocation atomic.  If there is no\nmemory pressure and memory isn't fragmented, the alloction will still\nsuccess, so we don't sacrifice high-order allocation's benefit here.  If\nthe atomic allocation fails, direct memory reclaim/compaction will not be\ntriggered, allocation fallback to low-order immediately, hence the direct\nmemory reclaim/compaction overhead is avoided.  In the allocation failure\ncase, kswapd is waken up and trying to make high-order freepages, so\nallocation could success next time.\n\nFollowing is the test to measure effect of this patch.\n\nSystem: QEMU, CPU 8, 512 MB\nMem: 25% memory is allocated at random position to make fragmentation.\n Memory-hogger occupies 150 MB memory.\nWorkload: hackbench -g 20 -l 1000\n\nAverage result by 10 runs (Base va Patched)\n\nelapsed_time(s): 4.3468 vs 2.9838\ncompact_stall: 461.7 vs 73.6\npgmigrate_success: 28315.9 vs 7256.1\n\nChange-Id: I84e305b4de4ce3c9d387c74d68a753fda4fe2234\nSigned-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>\nCc: Christoph Lameter <cl@linux.com>\nCc: Pekka Enberg <penberg@kernel.org>\nAcked-by: David Rientjes <rientjes@google.com>\nCc: Shaohua Li <shli@fb.com>\nCc: Vlastimil Babka <vbabka@suse.cz>\nCc: Michal Hocko <mhocko@suse.cz>\nCc: Eric Dumazet <edumazet@google.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\nGit-commit: 45eb00cd3a034b8448f52fd9074e9b2b11d857c1\nGit-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git\nSigned-off-by: Liam Mark <lmark@codeaurora.org>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/8ad0f47521bbbba231bbd717cf525580fe833143"},{"sha":"bb4d559d59d6416e162db77e7cc6af50ceb799a6","author":{"name":"Davidlohr Bueso","email":"00d5de41cc3d2418d03f53cfbcaf9aeba891dad2@hp.com"},"message":"lib/int_sqrt.c: optimize square root algorithm\n\nOptimize the current version of the shift-and-subtract (hardware)\nalgorithm, described by John von Newmann[1] and Guy L Steele.\n\nIterating 1,000,000 times, perf shows for the current version:\n\n Performance counter stats for './sqrt-curr' (10 runs):\n\n         27.170996 task-clock                #    0.979 CPUs utilized            ( +-  3.19% )\n                 3 context-switches          #    0.103 K/sec                    ( +-  4.76% )\n                 0 cpu-migrations            #    0.004 K/sec                    ( +-100.00% )\n               104 page-faults               #    0.004 M/sec                    ( +-  0.16% )\n        64,921,199 cycles                    #    2.389 GHz                      ( +-  0.03% )\n        28,967,789 stalled-cycles-frontend   #   44.62% frontend cycles idle     ( +-  0.18% )\n   <not supported> stalled-cycles-backend\n       104,502,623 instructions              #    1.61  insns per cycle\n                                             #    0.28  stalled cycles per insn  ( +-  0.00% )\n        34,088,368 branches                  # 1254.587 M/sec                    ( +-  0.00% )\n             4,901 branch-misses             #    0.01% of all branches          ( +-  1.32% )\n\n       0.027763015 seconds time elapsed                                          ( +-  3.22% )\n\nAnd for the new version:\n\nPerformance counter stats for './sqrt-new' (10 runs):\n\n          0.496869 task-clock                #    0.519 CPUs utilized            ( +-  2.38% )\n                 0 context-switches          #    0.000 K/sec\n                 0 cpu-migrations            #    0.403 K/sec                    ( +-100.00% )\n               104 page-faults               #    0.209 M/sec                    ( +-  0.15% )\n           590,760 cycles                    #    1.189 GHz                      ( +-  2.35% )\n           395,053 stalled-cycles-frontend   #   66.87% frontend cycles idle     ( +-  3.67% )\n   <not supported> stalled-cycles-backend\n           398,963 instructions              #    0.68  insns per cycle\n                                             #    0.99  stalled cycles per insn  ( +-  0.39% )\n            70,228 branches                  #  141.341 M/sec                    ( +-  0.36% )\n             3,364 branch-misses             #    4.79% of all branches          ( +-  5.45% )\n\n       0.000957440 seconds time elapsed                                          ( +-  2.42% )\n\nFurthermore, this saves space in instruction text:\n\n   text    data     bss     dec     hex filename\n    111       0       0     111      6f lib/int_sqrt-baseline.o\n     89       0       0      89      59 lib/int_sqrt.o\n\n[1] http://en.wikipedia.org/wiki/First_Draft_of_a_Report_on_the_EDVAC\n\nSigned-off-by: Davidlohr Bueso <davidlohr.bueso@hp.com>\nReviewed-by: Jonathan Gonzalez <jgonzlez@linets.cl>\nTested-by: Jonathan Gonzalez <jgonzlez@linets.cl>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/bb4d559d59d6416e162db77e7cc6af50ceb799a6"},{"sha":"6e83d44267a4ef11eda2ac9a5e05c97528e96a49","author":{"name":"ramgear","email":"f69620e59be9d495099daf98e24e66f83939f142@gmail.com"},"message":"int_sqrt.c: Correction square root algo with naming\n\nSigned-off-by: AngeloGioacchino Del Regno <kholk11@gmail.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/6e83d44267a4ef11eda2ac9a5e05c97528e96a49"},{"sha":"c473421bbd46c1bdb98e6bfaaf67303a9442bba3","author":{"name":"FlyFrog","email":"f69620e59be9d495099daf98e24e66f83939f142@gmail.com"},"message":"int_sqrt: Improve 3x faster integer sqrt.\n\nResult on 10,000,000 call.\nOld:\nsqrt(12345689) = 3513\nreal\t0m0.768s\nuser\t0m0.760s\nsys\t0m0.004s\n\nNew:\nsqrt(12345689) = 3513\nreal\t0m0.222s\nuser\t0m0.224s\nsys\t0m0.000s\n\nSigned-off-by: AngeloGioacchino Del Regno <kholk11@gmail.com>\n(Personal comment)\nThe only very important uses for this commit are in memcontrol.c\nand page_alloc.c, where we play with inactive anon ratio that\nuses sqrt.\nAside from this, we have some efficiency improvement in NFS.","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/c473421bbd46c1bdb98e6bfaaf67303a9442bba3"},{"sha":"716148cbbc0088082fff885d6f79c0dcabae213f","author":{"name":"gustavo","email":"c7207af6318086dc63721ec53590c76d1f21c661@gmail.com"},"message":"Optimize kernel cfbfillrect function\n\nThis is a  patch to speed up the kernel\ncfbfillrect function used for clearing the screen or filling an area\nwith a solid color.\n\nThe previous implementation was doing reads from the uncached framebuffer,\nin certain circumstances, even for simple fills, which for performance\nreasons, on most platforms, is ill-advised unless strictly necessary to\nconform to the raster operation. In these circumstances, doing 64-bit\naccess on 64-bit systems does not serve much purpose except for probing\nfor corner-case bugs and race conditions in the hardware's framebuffer\nbus implementation. On all systems, for 16bpp, it is better to take\nadvantage of write-combining features of the framebuffer and write a\nhalf-word if required for the left and right edges.\n\nAdditionally, on most platforms, integer divides are relatively slow so are\nbest avoided, especially in inner loops.\n\nThis patch implements optimizations for 16bpp and 32bpp that avoid\nframebuffer read operations during cfbfillrect if the raster-operation\nis GXcopy. This applies to both 32-bit (BITS_PER_LONG) and 64-bit\nsystems (BITS_PER_LONG == 64). Although cfbfillrect is not usually a\nbottleneck for the console text framebuffer (because regions filled\nusually are aligned to a multiple of 2 or 4 x-coordinate and reads\nare avoided), in some use-cases this patch could deliver a significant\nspeed-up.\n\nSigned-off-by: Harm Hanemaaijer <fgenfb@yahoo.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/716148cbbc0088082fff885d6f79c0dcabae213f"},{"sha":"b8f244816985eea89ede87c8d230ebaa12d74ec1","author":{"name":"gustavo","email":"c7207af6318086dc63721ec53590c76d1f21c661@gmail.com"},"message":"Speed up console framebuffer imageblit function\n\nEspecially on platforms with a slower CPU but a relatively high\nframebuffer fill bandwidth, like current ARM devices, the existing\nconsole monochrome imageblit function used to draw console text is\nsuboptimal for common pixel depths such as 16bpp and 32bpp. The existing\ncode is quite general and can deal with several pixel depths. By creating\nspecial case functions for 16bpp and 32bpp, by far the most common pixel\nformats used on modern systems, a significant speed-up is attained\nwhich can be readily felt on ARM-based devices like the Raspberry Pi\nand the Allwinner platform, but should help any platform using the\nfb layer.\n\nThe special case functions allow constant folding, eliminating a number\nof instructions including divide operations, and allow the use of an\nunrolled loop, eliminating instructions with a variable shift size,\nreducing source memory access instructions, and eliminating excessive\nbranching. These unrolled loops also allow much better code optimization\nby the C compiler. The code that selects which optimized variant is used\nis also simplified, eliminating integer divide instructions.\n\nThe speed-up, measured by timing 'cat file.txt' in the console, varies\nbetween 40% and 70%, when testing on the Raspberry Pi and Allwinner\nARM-based platforms, depending on font size and the pixel depth, with\nthe greater benefit for 32bpp.\n\nSigned-off-by: Harm Hanemaaijer <fgenfb@yahoo.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/b8f244816985eea89ede87c8d230ebaa12d74ec1"},{"sha":"b1692f753477ffe79d1938daf0a1270e222da150","author":{"name":"Will Deacon","email":"b2e33b86f3f248a395aadfb8ef1908ac314f4233@arm.com"},"message":"asm-generic: rwsem: ensure sem->cnt is only accessed via atomic_long_*\n\nThe asm-generic rwsem implementation directly acceses sem->cnt when\nperforming a __down_read_trylock operation. Whilst this is probably safe\non all architectures, we should stick to the atomic_long_* API and use\natomic_long_read instead.\n\nSigned-off-by: Will Deacon <will.deacon@arm.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/b1692f753477ffe79d1938daf0a1270e222da150"},{"sha":"db068d52d0143a56974a5c8aefbfc67818f7a091","author":{"name":"Will Deacon","email":"b2e33b86f3f248a395aadfb8ef1908ac314f4233@arm.com"},"message":"asm-generic: rwsem: de-PPCify rwsem.h\n\nasm-generic/rwsem.h used to live under arch/powerpc. During its\nliberation to common code, a few references to its former home where\npreserved, in particular the definition of RWSEM_ACTIVE_MASK is\npredicated on CONFIG_PPC64.\n\nThis patch updates the ifdefs and comments to architecturally neutral\nversions.\n\nSigned-off-by: Will Deacon <will.deacon@arm.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/db068d52d0143a56974a5c8aefbfc67818f7a091"},{"sha":"8bbcd403f746c0e7b29e85055265600b5fc19908","author":{"name":"Will Deacon","email":"b2e33b86f3f248a395aadfb8ef1908ac314f4233@arm.com"},"message":"ARM: rwsem: use asm-generic rwsem implementation\n\nasm-generic offers an atomic-add based rwsem implementation, which\ncan avoid the need for heavier, spinlock-based synchronisation on the\nfast path.\n\nThis patch makes use of the optimised implementation for ARM CPUs.\n\nSigned-off-by: Will Deacon <will.deacon@arm.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/8bbcd403f746c0e7b29e85055265600b5fc19908"},{"sha":"786e0a48fc6ce029e0a1096ae7ae482f1e693650","author":{"name":"Michel Lespinasse","email":"a5773662789a0e7d846e428fa24f3d04d48f4dbd@google.com"},"message":"rbtree: Backport from 3.10\n\nrbtree: empty nodes have no color\n\nEmpty nodes have no color.  We can make use of this property to simplify\nthe code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros.  Also,\nwe can get rid of the rb_init_node function which had been introduced by\ncommit 88d19cf ('timers: Add rb_init_node() to allow for stack\nallocated rb nodes') to avoid some issue with the empty node's color not\nbeing initialized.\n\nI'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are\ndoing there, though.  axboe introduced them in commit 10fd48f\n('rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev').  The way I\nsee it, the 'empty node' abstraction is only used by rbtree users to\nflag nodes that they haven't inserted in any rbtree, so asking the\npredecessor or successor of such nodes doesn't make any sense.\n\nOne final rb_init_node() caller was recently added in sysctl code to\nimplement faster sysctl name lookups.  This code doesn't make use of\nRB_EMPTY_NODE at all, and from what I could see it only called\nrb_init_node() under the mistaken assumption that such initialization was\nrequired before node insertion.\n\n[sfr@canb.auug.org.au: fix net/ceph/osd_client.c build]\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nCc: John Stultz <john.stultz@linaro.org>\nSigned-off-by: Stephen Rothwell <sfr@canb.auug.org.au>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nChange-Id: Ic1c555ddcf679f1d255a3992aa5f522983da6e07\n\nrbtree: move some implementation details from rbtree.h to rbtree.c\n\nrbtree users must use the documented APIs to manipulate the tree\nstructure.  Low-level helpers to manipulate node colors and parenthood are\nnot part of that API, so move them to lib/rbtree.c\n\n[dwmw2@infradead.org: fix jffs2 build issue due to renamed __rb_parent_color field]\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: David Woodhouse <David.Woodhouse@intel.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: break out of rb_insert_color loop after tree rotation\n\nIt is a well known property of rbtrees that insertion never requires more\nthan two tree rotations.  In our implementation, after one loop iteration\nidentified one or two necessary tree rotations, we would iterate and look\nfor more.  However at that point the node's parent would always be black,\nwhich would cause us to exit the loop.\n\nWe can make the code flow more obvious by just adding a break statement\nafter the tree rotations, where we know we are done.  Additionally, in the\ncases where two tree rotations are necessary, we don't have to update the\n'node' pointer as it wouldn't be used until the next loop iteration, which\nwe now avoid due to this break statement.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: adjust root color in rb_insert_color() only when necessary\n\nThe root node of an rbtree must always be black.  However,\nrb_insert_color() only needs to maintain this invariant when it has been\nbroken - that is, when it exits the loop due to the current (red) node\nbeing the root.  In all other cases (exiting after tree rotations, or\nexiting due to an existing black parent) the invariant is already\nsatisfied, so there is no need to adjust the root node color.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: low level optimizations in rb_insert_color()\n\n- Use the newly introduced rb_set_parent_color() function to flip the color\n  of nodes whose parent is already known.\n- Optimize rb_parent() when the node is known to be red - there is no need\n  to mask out the color in that case.\n- Flipping gparent's color to red requires us to fetch its rb_parent_color\n  field, so we can reuse it as the parent value for the next loop iteration.\n- Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree\n  rotations: we already have pointers to all relevant nodes, and know their\n  colors (either because we want to adjust it, or because we've tested it,\n  or we can deduce it as black due to the node proximity to a known red node).\n  So we can generate more efficient code by making use of the node pointers\n  we already have, and setting both the parent and color attributes for\n  nodes all at once. Also in Case 2, some node attributes don't have to\n  be set because we know another tree rotation (Case 3) will always follow\n  and override them.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: adjust node color in __rb_erase_color() only when necessary\n\nIn __rb_erase_color(), we were always setting a node to black after\nexiting the main loop.  And in one case, after fixing up the tree to\nsatisfy all rbtree invariants, we were setting the current node to root\njust to guarantee a loop exit, at which point the root would be set to\nblack.  However this is not necessary, as the root of an rbtree is already\nknown to be black.  The only case where the color flip is required is when\nwe exit the loop due to the current node being red, and it's easiest to\njust do the flip at that point instead of doing it after the loop.\n\n[adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change]\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Adrian Hunter <adrian.hunter@intel.com>\nCc: Alexander Shishkin <alexander.shishkin@intel.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nChange-Id: I74f2ec209a070e11a122e28f2061fcb4c1be4f6d\n\nrbtree: optimize case selection logic in __rb_erase_color()\n\nIn __rb_erase_color(), we have to select one of 3 cases depending on the\ncolor on the 'other' node children.  If both children are black, we flip a\nfew node colors and iterate.  Otherwise, we do either one or two tree\nrotations, depending on the color of the 'other' child opposite to 'node',\nand then we are done.\n\nThe corresponding logic had duplicate checks for the color of the 'other'\nchild opposite to 'node'.  It was checking it first to determine if both\nchildren are black, and then to determine how many tree rotations are\nrequired.  Rearrange the logic to avoid that extra check.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: low level optimizations in __rb_erase_color()\n\nIn __rb_erase_color(), we often already have pointers to the nodes being\nrotated and/or know what their colors must be, so we can generate more\nefficient code than the generic __rb_rotate_left() and __rb_rotate_right()\nfunctions.\n\nAlso when the current node is red or when flipping the sibling's color,\nthe parent is already known so we can use the more efficient\nrb_set_parent_color() function to set the desired color.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: coding style adjustments\n\nSet comment and indentation style to be consistent with linux coding style\nand the rest of the file, as suggested by Peter Zijlstra\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: optimize fetching of sibling node\n\nWhen looking to fetch a node's sibling, we went through a sequence of:\n- check if node is the parent's left child\n- if it is, then fetch the parent's right child\n\nThis can be replaced with:\n- fetch the parent's right child as an assumed sibling\n- check that node is NOT the fetched child\n\nThis avoids fetching the parent's left child when node is actually\nthat child. Saves a bit on code size, though it doesn't seem to make\na large difference in speed.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <David.Woodhouse@intel.com>\nAcked-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: add __rb_change_child() helper function\n\nAdd __rb_change_child() as an inline helper function to replace code that\nwould otherwise be duplicated 4 times in the source.\n\nNo changes to binary size or speed.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nReviewed-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: place easiest case first in rb_erase()\n\nIn rb_erase, move the easy case (node to erase has no more than\n1 child) first. I feel the code reads easier that way.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nReviewed-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()\n\nAn interesting observation for rb_erase() is that when a node has\nexactly one child, the node must be black and the child must be red.\nAn interesting consequence is that removing such a node can be done by\nsimply replacing it with its child and making the child black,\nwhich we can do efficiently in rb_erase(). __rb_erase_color() then\nonly needs to handle the no-childs case and can be modified accordingly.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nAcked-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: low level optimizations in rb_erase()\n\nVarious minor optimizations in rb_erase():\n- Avoid multiple loading of node->__rb_parent_color when computing parent\n  and color information (possibly not in close sequence, as there might\n  be further branches in the algorithm)\n- In the 1-child subcase of case 1, copy the __rb_parent_color field from\n  the erased node to the child instead of recomputing it from the desired\n  parent and color\n- When searching for the erased node's successor, differentiate between\n  cases 2 and 3 based on whether any left links were followed. This avoids\n  a condition later down.\n- In case 3, keep a pointer to the erased node's right child so we don't\n  have to refetch it later to adjust its parent.\n- In the no-childs subcase of cases 2 and 3, place the rebalance assigment\n  last so that the compiler can remove the following if(rebalance) test.\n\nAlso, added some comments to illustrate cases 2 and 3.\n\nChange-Id: I04582595b7a1864a57ae8a8460a7795bf45d25fe\nSigned-off-by: Michel Lespinasse <walken@google.com>\nAcked-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: faster augmented rbtree manipulation\n\nIntroduce new augmented rbtree APIs that allow minimal recalculation of\naugmented node information.\n\nA new callback is added to the rbtree insertion and erase rebalancing\nfunctions, to be called on each tree rotations. Such rotations preserve\nthe subtree's root augmented value, but require recalculation of the one\nchild that was previously located at the subtree root.\n\nIn the insertion case, the handcoded search phase must be updated to\nmaintain the augmented information on insertion, and then the rbtree\ncoloring/rebalancing algorithms keep it up to date.\n\nIn the erase case, things are more complicated since it is library\ncode that manipulates the rbtree in order to remove internal nodes.\nThis requires a couple additional callbacks to copy a subtree's\naugmented value when a new root is stitched in, and to recompute\naugmented values down the ancestry path when a node is removed from\nthe tree.\n\nIn order to preserve maximum speed for the non-augmented case,\nwe provide two versions of each tree manipulation function.\nrb_insert_augmented() is the augmented equivalent of rb_insert_color(),\nand rb_erase_augmented() is the augmented equivalent of rb_erase().\n\nChange-Id: Ibf0ddfb0197ca2188b80c81d11db46b1a331c609\nSigned-off-by: Michel Lespinasse <walken@google.com>\nAcked-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: remove prior augmented rbtree implementation\n\nconvert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api\nand remove the old augmented rbtree implementation.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nAcked-by: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: move augmented rbtree functionality to rbtree_augmented.h\n\nProvide rb_insert_augmented() and rb_erase_augmented() through a new\nrbtree_augmented.h include file.  rb_erase_augmented() is defined there as\nan __always_inline function, in order to allow inlining of augmented\nrbtree callbacks into it.  Since this generates a relatively large\nfunction, each augmented rbtree user should make sure to have a single\ncall site.\n\nChange-Id: I345d226bb58cc5f9fd9ff2221fe6a6f137df0d28\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Hillf Danton <dhillf@gmail.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Catalin Marinas <catalin.marinas@arm.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nCc: David Woodhouse <dwmw2@infradead.org>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nlib/rbtree.c: avoid the use of non-static __always_inline\n\nlib/rbtree.c declared __rb_erase_color() as __always_inline void, and\nthen exported it with EXPORT_SYMBOL.\n\nThis was because __rb_erase_color() must be exported for augmented\nrbtree users, but it must also be inlined into rb_erase() so that the\ndummy callback can get optimized out of that call site.\n\n(Actually with a modern compiler, none of the dummy callback functions\nshould even be generated as separate text functions).\n\nThe above usage is legal C, but it was unusual enough for some compilers\nto warn about it.  This change makes things more explicit, with a static\n__always_inline ____rb_erase_color function for use in rb_erase(), and a\nseparate non-inline __rb_erase_color function for use in\nrb_erase_augmented call sites.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nReported-by: Wu Fengguang <fengguang.wu@intel.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: add postorder iteration functions\n\nPostorder iteration yields all of a node's children prior to yielding the\nnode itself, and this particular implementation also avoids examining the\nleaf links in a node after that node has been yielded.\n\nIn what I expect will be its most common usage, postorder iteration allows\nthe deletion of every node in an rbtree without modifying the rbtree nodes\n(no _requirement_ that they be nulled) while avoiding referencing child\nnodes after they have been 'deleted' (most commonly, freed).\n\nI have only updated zswap to use this functionality at this point, but\nnumerous bits of code (most notably in the filesystem drivers) use a hand\nrolled postorder iteration that NULLs child links as it traverses the\ntree.  Each of those instances could be replaced with this common\nimplementation.\n\n1 & 2 add rbtree postorder iteration functions.\n3 adds testing of the iteration to the rbtree runtime tests\n4 allows building the rbtree runtime tests as builtins\n5 updates zswap.\n\nThis patch:\n\nAdd postorder iteration functions for rbtree.  These are useful for safely\nfreeing an entire rbtree without modifying the tree at all.\n\nChange-Id: I5d0f2db0b5bcb57da9c7fa1c5f34b8686db8dcc9\nSigned-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>\nReviewed-by: Seth Jennings <sjenning@linux.vnet.ibm.com>\nCc: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Michel Lespinasse <walken@google.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\nSigned-off-by: Theodore Ts'o <tytso@google.com>\nGit-commit: 06d0bde2d213b6d401e224b7ef49a72f8ab5e906\nGit-repo: https://android.googlesource.com/kernel/common.git\nSigned-off-by: Ian Maund <imaund@codeaurora.org>\n\nrbtree: add rbtree_postorder_for_each_entry_safe() helper\n\nBecause deletion (of the entire tree) is a relatively common use of the\nrbtree_postorder iteration, and because doing it safely means fiddling\nwith temporary storage, provide a helper to simplify postorder rbtree\niteration.\n\nChange-Id: Ifb89570a13fe7f3f480aa48f4281c21d99e28094\nSigned-off-by: Cody P Schafer <cody@linux.vnet.ibm.com>\nReviewed-by: Seth Jennings <sjenning@linux.vnet.ibm.com>\nCc: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Michel Lespinasse <walken@google.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\nSigned-off-by: Theodore Ts'o <tytso@google.com>\nGit-commit: bcccac5961bdc0ad3f5c54ceee9ecab8697a6405\nGit-repo: https://android.googlesource.com/kernel/common.git\nSigned-off-by: Ian Maund <imaund@codeaurora.org>\n\nrbtree: reference Documentation/rbtree.txt for usage instructions\n\nI recently started looking at the rbtree code (with an eye towards\nimproving the augmented rbtree support, but I haven't gotten there yet).\nI noticed a lot of possible speed improvements, which I am now proposing\nin this patch set.\n\nPatches 1-4 are preparatory: remove internal functions from rbtree.h so\nthat users won't be tempted to use them instead of the documented APIs,\nclean up some incorrect usages I've noticed (in particular, with the\nrecently added fs/proc/proc_sysctl.c rbtree usage), reference the\ndocumentation so that people have one less excuse to miss it, etc.\n\nPatch 5 is a small module I wrote to check the rbtree performance.  It\ncreates 100 nodes with random keys and repeatedly inserts and erases them\nfrom an rbtree.  Additionally, it has code to check for rbtree invariants\nafter each insert or erase operation.\n\nPatches 6-12 is where the rbtree optimizations are done, and they touch\nonly that one file, lib/rbtree.c .  I am getting good results out of these\n- in my small benchmark doing rbtree insertion (including search) and\nerase, I'm seeing a 30% runtime reduction on Sandybridge E5, which is more\nthan I initially thought would be possible.  (the results aren't as\nimpressive on my two other test hosts though, AMD barcelona and Intel\nWestmere, where I am seeing 14% runtime reduction only).  The code size -\nboth source (ommiting comments) and compiled - is also shorter after these\nchanges.  However, I do admit that the updated code is more arduous to\nread - one big reason for that is the removal of the tree rotation\nhelpers, which added some overhead but also made it easier to reason about\nthings locally.  Overall, I believe this is an acceptable compromise,\ngiven that this code doesn't get modified very often, and that I have good\ntests for it.\n\nUpon Peter's suggestion, I added comments showing the rtree configuration\nbefore every rotation.  I think they help; however it's still best to have\na copy of the cormen/leiserson/rivest book when digging into this code.\n\nThis patch: reference Documentation/rbtree.txt for usage instructions\n\ninclude/linux/rbtree.h included some basic usage instructions, while\nDocumentation/rbtree.txt had some more complete and easier to follow\ninstructions.  Replacing the former with a reference to the latter.\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n\nrbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c\n\nThe recently added code to use rbtrees in sysctl did not follow the proper\nrbtree interface on insertion - it was calling rb_link_node() which\ninserts a new node into the binary tree, but missed the call to\nrb_insert_color() which properly balances the rbtree and establishes all\nexpected rbtree invariants.\n\nI found out about this only because faulty commit also used\nrb_init_node(), which I am removing within this patchset.  But I think\nit's an easy mistake to make, and it makes me wonder if we should change\nthe rbtree API so that insertions would be done with a single rb_insert()\ncall (even if its implementation could still inline the rb_link_node()\npart and call a private __rb_insert_color function to do the rebalancing).\n\nSigned-off-by: Michel Lespinasse <walken@google.com>\nCc: Andrea Arcangeli <aarcange@redhat.com>\nAcked-by: David Woodhouse <David.Woodhouse@intel.com>\nCc: Rik van Riel <riel@redhat.com>\nCc: Peter Zijlstra <a.p.zijlstra@chello.nl>\nCc: Daniel Santos <daniel.santos@pobox.com>\nCc: Jens Axboe <axboe@kernel.dk>\nCc: 'Eric W. Biederman' <ebiederm@xmission.com>\nSigned-off-by: Andrew Morton <akpm@linux-foundation.org>\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\nSigned-off-by: The Linux Foundation. All rights reserved.\nSigned-off-by: Alex Saiko <solcmdr@gmail.com>","distinct":true,"url":"https://api.github.com/repos/tunturn/android_kernel_aries_concept/commits/786e0a48fc6ce029e0a1096ae7ae482f1e693650"}]}
{"actor":{"display_login":"tunturn"}}