mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Jan Kara <jack@suse.cz>
To: Cody P Schafer <cody@linux.vnet.ibm.com>
Cc: Andrew Morton <akpm@linux-foundation.org>,
	Jan Kara <jack@suse.cz>,
	Andreas Dilger <adilger.kernel@dilger.ca>,
	LKML <linux-kernel@vger.kernel.org>,
	EXT4 <linux-ext4@vger.kernel.org>
Subject: Re: [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry
Date: Tue, 5 Nov 2013 22:57:55 +0100	[thread overview]
Message-ID: <20131105215755.GB9236@quack.suse.cz> (raw)
In-Reply-To: <5278C2F8.3050805@linux.vnet.ibm.com>

On Tue 05-11-13 02:05:44, Cody P Schafer wrote:
> On 11/04/2013 05:40 PM, Cody P Schafer wrote:
> > 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.
> 
> On second thought, it appears I was a bit to hasty with this, and this patch actually breaks things.
> 
> On 11/04/2013 04:45 PM, Jan Kara wrote:> On Mon 04-11-13 15:26:38, Jan Kara wrote:
> >> On Fri 01-11-13 15:38:50, Cody P Schafer wrote:
> >>> Use rbtree_postorder_for_each_entry_safe() to destroy the rbtree instead
> >>> of opencoding an alternate postorder iteration that modifies the tree
> >>    Thanks. I've merged the patch into my tree.
> >    Hum, except that the kernel oopses with this patch. And I think the
> > problem is in rbtree_postorder_for_each_entry_safe(). How are those tests
> > for NULL supposed to work? For example if the tree is empty, 'pos' will be
> > NULL and you'll call rb_next_postorder(&NULL->field) which is pretty much
> > guaranteed to oops if 'field' doesn't have offset 0 in the structure...
> 
> No, it shouldn't oops because pos won't be NULL, &pos->field will be.
> 
> pos is only assigned via an rb_entry(rb_first_postorder()) or
> rb_entry(rb_next_postorder()). rb_next_postorder() and
> rb_first_postorder() can return NULL. That NULL then is munged by
> rb_entry to be (NULL - offset_of_field). Causing (&pos->field == NULL ==
> (pos + offset_of_field)).
  OK, so I had a second look. And the compiler thinks differently than you
:) The thing is that my gcc (4.3.4) apparently assumes pointer underflow is
undefined and thus optimizes your test &pos->field to 1. I've asked our gcc
guys for a definitive answer but clearly your code will need some way to
avoid pointer underflows...

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

  reply	other threads:[~2013-11-05 21:58 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2013-11-01 22:38 [PATCH 1/8] net ipset: use rbtree postorder iteration instead of opencoding Cody P Schafer
2013-11-01 22:38 ` [PATCH 2/8] trace/trace_stat: use rbtree postorder iteration helper " Cody P Schafer
2013-11-02  2:45   ` Steven Rostedt
2013-11-04  8:49     ` Cody P Schafer
2013-11-04 14:22       ` Steven Rostedt
2013-11-01 22:38 ` [PATCH 3/8] fs/ubifs: " Cody P Schafer
2013-11-01 22:38 ` [PATCH 4/8] fs/ext4: " Cody P Schafer
2013-11-01 22:38 ` [PATCH 5/8] fs/jffs2: " Cody P Schafer
2013-11-01 22:38 ` [PATCH 6/8] fs/ext3: " Cody P Schafer
2013-11-04 14:26   ` Jan Kara
2013-11-05  0:45     ` Jan Kara
2013-11-05  1:33       ` Cody P Schafer
2013-11-05  1:40         ` [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry Cody P Schafer
2013-11-05  1:40           ` [PATCH 2/2] rbtree/test: move rb_node to the middle of the test struct Cody P Schafer
2013-11-05 10:05           ` [PATCH 1/2] rbtree: fix postorder iteration when the rb_node is not the first element in an entry Cody P Schafer
2013-11-05 21:57             ` Jan Kara [this message]
2013-11-05 22:56               ` Jan Kara
2013-11-06 20:18                 ` Cody P Schafer
2013-11-06 21:37                   ` [PATCH] rbtree/test: test rbtree_postorder_for_each_entry_safe() Cody P Schafer
2013-11-06 23:16                     ` Andrew Morton
2013-11-01 22:38 ` [PATCH 7/8] mtd/ubi: use rbtree postorder iteration helper instead of opencoding Cody P Schafer
2013-11-01 22:38 ` [PATCH 8/8] sh/dwarf: use rbtree postorder iteration helper instead of solution using repeated rb_erase() Cody P Schafer

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20131105215755.GB9236@quack.suse.cz \
    --to=jack@suse.cz \
    --cc=adilger.kernel@dilger.ca \
    --cc=akpm@linux-foundation.org \
    --cc=cody@linux.vnet.ibm.com \
    --cc=linux-ext4@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®