From patchwork Wed Jun 15 10:59:08 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Morse X-Patchwork-Id: 9178157 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 6033D60573 for ; Wed, 15 Jun 2016 11:01:40 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4FACA27DF9 for ; Wed, 15 Jun 2016 11:01:40 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 446E32821D; Wed, 15 Jun 2016 11:01:40 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E2A9027DF9 for ; Wed, 15 Jun 2016 11:01:39 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753454AbcFOLBY (ORCPT ); Wed, 15 Jun 2016 07:01:24 -0400 Received: from foss.arm.com ([217.140.101.70]:36582 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753430AbcFOLBV (ORCPT ); Wed, 15 Jun 2016 07:01:21 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 61F2E441; Wed, 15 Jun 2016 04:02:02 -0700 (PDT) Received: from melchizedek.cambridge.arm.com (melchizedek.cambridge.arm.com [10.1.209.158]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id A5A323F213; Wed, 15 Jun 2016 04:01:20 -0700 (PDT) From: James Morse To: kvmarm@lists.cs.columbia.edu, kvm@vger.kernel.org Cc: Will Deacon , 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> X-Mailer: git-send-email 2.8.0.rc3 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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)