From mboxrd@z Thu Jan 1 00:00:00 1970 From: James Morse Subject: [PATCH] kvmtool: devices.c: Update parent when inserting into rbtree Date: Wed, 15 Jun 2016 11:59:08 +0100 Message-ID: <1465988348-968-1-git-send-email-james.morse@arm.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Cc: Will Deacon To: kvmarm@lists.cs.columbia.edu, kvm@vger.kernel.org Return-path: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kvmarm-bounces@lists.cs.columbia.edu Sender: kvmarm-bounces@lists.cs.columbia.edu List-Id: kvm.vger.kernel.org When walking the devices rbtree to insert a node, we must keep track of the parent node when we descend. If we skip this step, we always insert new nodes with a NULL parent, bypassing __rb_insert()s rebalance code. Things get worse when we come to walk the tree, as we can't move up a level. This isn't a problem in practice, as all devices appear to be inserted in-order, so our rbtree is actually a monochrome linked list. Signed-off-by: James Morse --- devices.c | 1 + 1 file changed, 1 insertion(+) diff --git a/devices.c b/devices.c index b560a59..a7c666a 100644 --- a/devices.c +++ b/devices.c @@ -45,6 +45,7 @@ int device__register(struct device_header *dev) int num = rb_entry(*node, struct device_header, node)->dev_num; int result = dev->dev_num - num; + parent = *node; if (result < 0) node = &((*node)->rb_left); else if (result > 0) -- 2.8.0.rc3