Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752909Ab2KYCoh (ORCPT ); Sat, 24 Nov 2012 21:44:37 -0500 Received: from mail-pa0-f46.google.com ([209.85.220.46]:35277 "EHLO mail-pa0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752838Ab2KYCog (ORCPT ); Sat, 24 Nov 2012 21:44:36 -0500 From: Michel Lespinasse To: Sasha Levin Cc: Pekka Enberg , Asias He , Ingo Molnar , linux-kernel@vger.kernel.org Subject: [PATCH 1/3] kvm: ensure non-overlapping intervals in rb_int_insert() Date: Sat, 24 Nov 2012 18:44:22 -0800 Message-Id: <1353811464-6462-1-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: References: Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1537 Lines: 44 The rbtree interval API is designed for handling non-overlapping intervals; modify rb_int_insert() to guarantee this property is maintained by returning -EEXIST when attempting to insert a new interval that overlaps an existing interval. Also fix an issue where the computation of 'result' could trigger an integer overflow which would break the rbtree ordering. Signed-off-by: Michel Lespinasse --- tools/kvm/util/rbtree-interval.c | 10 +++++----- 1 files changed, 5 insertions(+), 5 deletions(-) diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c index d7fa96a06a92..fd69252bea02 100644 --- a/tools/kvm/util/rbtree-interval.c +++ b/tools/kvm/util/rbtree-interval.c @@ -99,13 +99,13 @@ int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node) struct rb_node **node = &root->rb_node, *parent = NULL; while (*node) { - int result = i_node->low - rb_int(*node)->low; + struct rb_int_node *cur = rb_int(*node); parent = *node; - if (result < 0) - node = &((*node)->rb_left); - else if (result > 0) - node = &((*node)->rb_right); + if (i_node->high <= cur->low) + node = &cur->node.rb_left; + else if (cur->high <= i_node->low) + node = &cur->node.rb_right; else return -EEXIST; } -- 1.7.7.3 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/