From patchwork Tue Nov 5 01:40:01 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cody P Schafer X-Patchwork-Id: 288354 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 8D78D2C0087 for ; Tue, 5 Nov 2013 12:40:44 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753989Ab3KEBkc (ORCPT ); Mon, 4 Nov 2013 20:40:32 -0500 Received: from e9.ny.us.ibm.com ([32.97.182.139]:39700 "EHLO e9.ny.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753309Ab3KEBka (ORCPT ); Mon, 4 Nov 2013 20:40:30 -0500 Received: from /spool/local by e9.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Mon, 4 Nov 2013 20:40:30 -0500 Received: from d01dlp02.pok.ibm.com (9.56.250.167) by e9.ny.us.ibm.com (192.168.1.109) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Mon, 4 Nov 2013 20:40:27 -0500 Received: from b01cxnp23032.gho.pok.ibm.com (b01cxnp23032.gho.pok.ibm.com [9.57.198.27]) by d01dlp02.pok.ibm.com (Postfix) with ESMTP id E565A6E8040; Mon, 4 Nov 2013 20:40:24 -0500 (EST) Received: from d01av04.pok.ibm.com (d01av04.pok.ibm.com [9.56.224.64]) by b01cxnp23032.gho.pok.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id rA51eQda52756612; Tue, 5 Nov 2013 01:40:26 GMT Received: from d01av04.pok.ibm.com (localhost [127.0.0.1]) by d01av04.pok.ibm.com (8.14.4/8.14.4/NCO v10.0 AVout) with ESMTP id rA51ePls012820; Mon, 4 Nov 2013 20:40:26 -0500 Received: from kernel.stglabs.ibm.com (kernel.stglabs.ibm.com [9.114.214.19]) by d01av04.pok.ibm.com (8.14.4/8.14.4/NCO v10.0 AVin) with ESMTP id rA51ePaT012817; Mon, 4 Nov 2013 20:40:25 -0500 Received: from localhost (unknown [9.70.82.182]) by kernel.stglabs.ibm.com (Postfix) with SMTP id DF8942400DE; Mon, 4 Nov 2013 17:40:24 -0800 (PST) From: Cody P Schafer To: Andrew Morton , Jan Kara Cc: Andreas Dilger , LKML , EXT4 , Cody P Schafer Subject: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry Date: Mon, 4 Nov 2013 17:40:01 -0800 Message-Id: <1383615602-1784-1-git-send-email-cody@linux.vnet.ibm.com> X-Mailer: git-send-email 1.8.4.2 In-Reply-To: <52784ADF.1040104@linux.vnet.ibm.com> References: <52784ADF.1040104@linux.vnet.ibm.com> X-TM-AS-MML: No X-Content-Scanned: Fidelis XPS MAILER x-cbid: 13110501-7182-0000-0000-000009008707 Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org Provide a new helper called rb_next_postorder_entry() to perform NULL checks and container_of() coversions and use it in rbtree_for_each_entry_safe() to fix oopses that occur when rb_node is not the first element in the entry. Additionally, remove the missplaced NULL check from rb_next_postorder(). Signed-off-by: Cody P Schafer --- include/linux/rbtree.h | 20 +++++++++++++++----- lib/rbtree.c | 2 -- 2 files changed, 15 insertions(+), 7 deletions(-) diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index aa870a4..630eedb 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -86,6 +86,18 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, } /** + * rb_next_postorder_entry - a helper to check for a NULL entry and advance to + * the next element. + * + * @elem: a 'type *' which is contained in an rbtree + * @field: the field in 'type' which contains the struct rb_node. + */ +#define rb_next_postorder_entry(elem, field) \ + ((elem) ? rb_entry(rb_next_postorder(&(elem)->field), \ + typeof(*(elem)), field) \ + : NULL) + +/** * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of * given type safe against removal of rb_node entry * @@ -96,11 +108,9 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, */ #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ for (pos = rb_entry(rb_first_postorder(root), typeof(*pos), field),\ - n = rb_entry(rb_next_postorder(&pos->field), \ - typeof(*pos), field); \ - &pos->field; \ + n = rb_next_postorder_entry(pos, field); \ + pos; \ pos = n, \ - n = rb_entry(rb_next_postorder(&pos->field), \ - typeof(*pos), field)) + n = rb_next_postorder_entry(pos, field)) #endif /* _LINUX_RBTREE_H */ diff --git a/lib/rbtree.c b/lib/rbtree.c index 65f4eff..08168d0 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -534,8 +534,6 @@ static struct rb_node *rb_left_deepest_node(const struct rb_node *node) struct rb_node *rb_next_postorder(const struct rb_node *node) { const struct rb_node *parent; - if (!node) - return NULL; parent = rb_parent(node); /* If we're sitting on node, we've already seen our children */