linux-kernel - Is augmented rbtree propagation broken?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <50AE5D79.8040803@oracle.com>
Date:	Thu, 22 Nov 2012 12:14:33 -0500
From:	Sasha Levin <sasha.levin@...cle.com>
To:	Michel Lespinasse <walken@...gle.com>
CC:	Pekka Enberg <penberg@...nel.org>,
	Asias He <asias.hejun@...il.com>, Ingo Molnar <mingo@...e.hu>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Is augmented rbtree propagation broken?

Hi Michel,

I've noticed a bug regarding search of ioports in the KVM tool. Since the KVM tool is
using kernel's augmented rbtree implementation to represent an interval rbtree I dug a
bit into the new implementation in the kernel, and noticed the following odd behaviour.

Let's take a simple case where we have 2 intervals with the 3rd parameter being the
'max_high' field used by interval rbtrees: (1,2,0) , (3,4,0). Let's add them one by one:

1.		 (1,2,2)
		/	\
	     NULL	NULL

2.		 (1,2,4)
		/	\
	     NULL	(3,4,4)

On the 2nd stage we'd expect that the new (3,4) interval will be added to the right
subtree (which happens correctly), and that the insertion will be propagated to the
root of the tree to update max_high (which doesn't happen).

Basically, at stage 2, the tree we're left with is:

		 (1,2,2)
		/	\
	     NULL	(3,4,4)

Which is wrong.

I suspect that this happens because we never propagate upon insertion, which sounds
quite odd to me, but I might be missing something.

The following patch fixed the problem for me:

diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 214caa3..5cfdca6 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -47,6 +47,7 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root,
                    const struct rb_augment_callbacks *augment)
 {
        __rb_insert_augmented(node, root, augment->rotate);
+       augment->propagate(node, NULL);
 }

Thanks,
Sasha
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/