Linux-mm Archive on lore.kernel.org
 help / color / Atom feed
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
Date: Wed, 04 Dec 2019 16:51:47 -0800
Message-ID: <20191205005147.IjXbLGgEv%akpm@linux-foundation.org> (raw)
In-Reply-To: <20191204164858.fe4ed8886e34ad9f3b34ea00@linux-foundation.org>

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(-)

--- 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;
 	}
 
_


  parent reply index

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

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20191205005147.IjXbLGgEv%akpm@linux-foundation.org \
    --to=akpm@linux-foundation.org \
    --cc=dbueso@suse.de \
    --cc=linux-mm@kvack.org \
    --cc=mm-commits@vger.kernel.org \
    --cc=peterz@infradead.org \
    --cc=richardw.yang@linux.intel.com \
    --cc=tglx@linutronix.de \
    --cc=torvalds@linux-foundation.org \
    --cc=walken@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-mm Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-mm/0 linux-mm/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-mm linux-mm/ https://lore.kernel.org/linux-mm \
		linux-mm@kvack.org
	public-inbox-index linux-mm

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kvack.linux-mm


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git