diff mbox series

[38/86] lib/rbtree: set successor's parent unconditionally

Message ID	20191205005147.IjXbLGgEv%akpm@linux-foundation.org (mailing list archive)
State	New, archived
Headers	show Return-Path: <SRS0=8yH2=Z3=kvack.org=owner-linux-mm@kernel.org> DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org DDC6C24658 Date: Wed, 04 Dec 2019 16:51:47 -0800 From: Andrew Morton <akpm@linux-foundation.org> To: akpm@linux-foundation.org, dbueso@suse.de, linux-mm@kvack.org, mm-commits@vger.kernel.org, peterz@infradead.org, richardw.yang@linux.intel.com, tglx@linutronix.de, torvalds@linux-foundation.org, walken@google.com Subject: [patch 38/86] lib/rbtree: set successor's parent unconditionally Message-ID: <20191205005147.IjXbLGgEv%akpm@linux-foundation.org> In-Reply-To: <20191204164858.fe4ed8886e34ad9f3b34ea00@linux-foundation.org> User-Agent: s-nail v14.8.16 Sender: owner-linux-mm@kvack.org Precedence: bulk
Series	[01/86] mm/kasan/common.c: fix compile error \| expand [01/86] mm/kasan/common.c: fix compile error [02/86] mm: memcg/slab: wait for !root kmem_cache refcnt killing on root kmem_cache destruction [03/86] mm/vmstat: add helpers to get vmstat item names for each enum type [04/86] mm/memcontrol: use vmstat names for printing statistics [05/86] mm/memory.c: replace is_zero_pfn with is_huge_zero_pmd for thp [06/86] proc: change ->nlink under proc_subdir_lock [07/86] fs/proc/generic.c: delete useless "len" variable [08/86] fs/proc/internal.h: shuffle "struct pde_opener" [09/86] include/linux/proc_fs.h: fix confusing macro arg name [10/86] fs/proc/Kconfig: fix indentation [11/86] include/linux/sysctl.h: inline braces for ctl_table and ctl_table_header [12/86] .gitattributes: use 'dts' diff driver for dts files [13/86] linux/build_bug.h: change type to int [14/86] linux/scc.h: make uapi linux/scc.h self-contained [15/86] arch/Kconfig: fix indentation [16/86] scripts/get_maintainer.pl: add signatures from Fixes: <badcommit> lines in commit message [17/86] kernel.h: update comment about simple_strto<foo>() functions [18/86] auxdisplay: charlcd: deduplicate simple_strtoul() [19/86] kernel/notifier.c: intercept duplicate registrations to avoid infinite loops [20/86] kernel/notifier.c: remove notifier_chain_cond_register() [21/86] kernel/notifier.c: remove blocking_notifier_chain_cond_register() [22/86] kernel/profile.c: use cpumask_available to check for NULL cpumask [23/86] kernel/sys.c: avoid copying possible padding bytes in copy_to_user [24/86] bitops: introduce the for_each_set_clump8 macro [25/86] lib/test_bitmap.c: add for_each_set_clump8 test cases [26/86] gpio: 104-dio-48e: utilize for_each_set_clump8 macro [27/86] gpio: 104-idi-48: utilize for_each_set_clump8 macro [28/86] gpio: gpio-mm: utilize for_each_set_clump8 macro [29/86] gpio: ws16c48: utilize for_each_set_clump8 macro [30/86] gpio: pci-idio-16: utilize for_each_set_clump8 macro [31/86] gpio: pcie-idio-24: utilize for_each_set_clump8 macro [32/86] gpio: uniphier: utilize for_each_set_clump8 macro [33/86] gpio: 74x164: utilize the for_each_set_clump8 macro [34/86] thermal: intel: intel_soc_dts_iosf: Utilize for_each_set_clump8 macro [35/86] gpio: pisosr: utilize the for_each_set_clump8 macro [36/86] gpio: max3191x: utilize the for_each_set_clump8 macro [37/86] gpio: pca953x: utilize the for_each_set_clump8 macro [38/86] lib/rbtree: set successor's parent unconditionally [39/86] lib/rbtree: get successor's color directly [40/86] lib/test_meminit.c: add bulk alloc/free tests [41/86] lib/math/rational.c: fix possible incorrect result from rational fractions helper [42/86] lib/genalloc.c: export symbol addr_in_gen_pool [43/86] lib/genalloc.c: rename addr_in_gen_pool to gen_pool_has_addr [44/86] checkpatch: improve ignoring CamelCase SI style variants like mA [45/86] checkpatch: reduce is_maintained_obsolete lookup runtime [46/86] epoll: simplify ep_poll_safewake() for CONFIG_DEBUG_LOCK_ALLOC [47/86] fs/epoll: remove unnecessary wakeups of nested epoll [48/86] selftests: add epoll selftests [49/86] fs/binfmt_elf.c: delete unused "interp_map_addr" argument [50/86] fs/binfmt_elf.c: extract elf_read() function [51/86] init/Kconfig: fix indentation [52/86] drivers/rapidio/rio-driver.c: fix missing include of <linux/rio_drv.h> [53/86] drivers/rapidio/rio-access.c: fix missing include of <linux/rio_drv.h> [54/86] drm: limit to INT_MAX in create_blob ioctl [55/86] uaccess: disallow > INT_MAX copy sizes [56/86] kcov: remote coverage support [57/86] usb, kcov: collect coverage from hub_event [58/86] vhost, kcov: collect coverage from vhost_worker [59/86] lib/ubsan: don't serialize UBSAN report [60/86] arch: ipcbuf.h: make uapi asm/ipcbuf.h self-contained [61/86] arch: msgbuf.h: make uapi asm/msgbuf.h self-contained [62/86] arch: sembuf.h: make uapi asm/sembuf.h self-contained [63/86] lib/test_bitmap: force argument of bitmap_parselist_user() to proper address space [64/86] lib/test_bitmap: undefine macros after use [65/86] lib/test_bitmap: name EXP_BYTES properly [66/86] lib/test_bitmap: rename exp to exp1 to avoid ambiguous name [67/86] lib/test_bitmap: move exp1 and exp2 upper for others to use [68/86] lib/test_bitmap: fix comment about this file [69/86] lib/bitmap: introduce bitmap_replace() helper [70/86] gpio: pca953x: remove redundant variable and check in IRQ handler [71/86] gpio: pca953x: use input from regs structure in pca953x_irq_pending() [72/86] gpio: pca953x: convert to use bitmap API [73/86] gpio: pca953x: tighten up indentation [74/86] alpha: use pgtable-nopud instead of 4level-fixup [75/86] arm: nommu: use pgtable-nopud instead of 4level-fixup [76/86] c6x: use pgtable-nopud instead of 4level-fixup [77/86] m68k: nommu: use pgtable-nopud instead of 4level-fixup [78/86] m68k: mm: use pgtable-nopXd instead of 4level-fixup [79/86] microblaze: use pgtable-nopmd instead of 4level-fixup [80/86] nds32: use pgtable-nopmd instead of 4level-fixup [81/86] parisc: use pgtable-nopXd instead of 4level-fixup [82/86] parisc/hugetlb: use pgtable-nopXd instead of 4level-fixup [83/86] sparc32: use pgtable-nopud instead of 4level-fixup [84/86] um: remove unused pxx_offset_proc() and addr_pte() functions [85/86] um: add support for folded p4d page tables [86/86] mm: remove __ARCH_HAS_4LEVEL_HACK and include/asm-generic/4level-fixup.h

Commit Message

Andrew Morton Dec. 5, 2019, 12:51 a.m. UTC

From: Wei Yang <richardw.yang@linux.intel.com>
Subject: lib/rbtree: set successor's parent unconditionally

Both in Case 2 and 3, we exchange n and s.  This mean no matter whether
child2 is NULL or not, successor's parent should be assigned to node's.

This patch takes this step out to make it explicit and reduce the
ambiguity.

Besides, this step reduces some symbol size like rb_erase().

   KERN_CONFIG       upstream       patched
   OPT_FOR_PERF      877            870
   OPT_FOR_SIZE      635            621

Link: http://lkml.kernel.org/r/20191028021442.5450-1-richardw.yang@linux.intel.com
Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Davidlohr Bueso <dbueso@suse.de>
Cc: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 include/linux/rbtree_augmented.h |    3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff mbox series

Patch

--- a/include/linux/rbtree_augmented.h~lib-rbtree-set-successors-parent-unconditionally
+++ a/include/linux/rbtree_augmented.h
@@ -283,14 +283,13 @@  __rb_erase_augmented(struct rb_node *nod
 		__rb_change_child(node, successor, tmp, root);
 
 		if (child2) {
-			successor->__rb_parent_color = pc;
 			rb_set_parent_color(child2, parent, RB_BLACK);
 			rebalance = NULL;
 		} else {
 			unsigned long pc2 = successor->__rb_parent_color;
-			successor->__rb_parent_color = pc;
 			rebalance = __rb_is_black(pc2) ? parent : NULL;
 		}
+		successor->__rb_parent_color = pc;
 		tmp = successor;
 	}