linux-kernel - Re: [PATCH 1/12] radix_tree: exceptional entries and indices

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <alpine.LSU.2.00.1106141707540.31043@sister.anvils>
Date:	Tue, 14 Jun 2011 17:24:38 -0700 (PDT)
From:	Hugh Dickins <hughd@...gle.com>
To:	Pekka Enberg <penberg@...nel.org>
cc:	Andrew Morton <akpm@...ux-foundation.org>,
	linux-kernel@...r.kernel.org, linux-mm@...ck.org
Subject: Re: [PATCH 1/12] radix_tree: exceptional entries and indices

Hi Pekka!

Thanks for taking a look.

On Tue, 14 Jun 2011, Pekka Enberg wrote:
> On Tue, Jun 14, 2011 at 1:42 PM, Hugh Dickins <hughd@...gle.com> wrote:
> > @@ -39,7 +39,15 @@
> >  * when it is shrunk, before we rcu free the node. See shrink code for
> >  * details.
> >  */
> > -#define RADIX_TREE_INDIRECT_PTR        1
> > +#define RADIX_TREE_INDIRECT_PTR                1
> > +/*
> > + * A common use of the radix tree is to store pointers to struct pages;
> > + * but shmem/tmpfs needs also to store swap entries in the same tree:
> > + * those are marked as exceptional entries to distinguish them.
> > + * EXCEPTIONAL_ENTRY tests the bit, EXCEPTIONAL_SHIFT shifts content past it.
> > + */
> > +#define RADIX_TREE_EXCEPTIONAL_ENTRY   2
> > +#define RADIX_TREE_EXCEPTIONAL_SHIFT   2
> >
> >  #define radix_tree_indirect_to_ptr(ptr) \
> >        radix_tree_indirect_to_ptr((void __force *)(ptr))
> > @@ -174,6 +182,28 @@ static inline int radix_tree_deref_retry
> >  }
> >
> >  /**
> > + * radix_tree_exceptional_entry        - radix_tree_deref_slot gave exceptional entry?
> > + * @arg:       value returned by radix_tree_deref_slot
> > + * Returns:    0 if well-aligned pointer, non-0 if exceptional entry.
> > + */
> > +static inline int radix_tree_exceptional_entry(void *arg)
> > +{
> > +       /* Not unlikely because radix_tree_exception often tested first */
> > +       return (unsigned long)arg & RADIX_TREE_EXCEPTIONAL_ENTRY;
> > +}
> > +
> > +/**
> > + * radix_tree_exception        - radix_tree_deref_slot returned either exception?
> > + * @arg:       value returned by radix_tree_deref_slot
> > + * Returns:    0 if well-aligned pointer, non-0 if either kind of exception.
> > + */
> > +static inline int radix_tree_exception(void *arg)
> > +{
> > +       return unlikely((unsigned long)arg &
> > +               (RADIX_TREE_INDIRECT_PTR | RADIX_TREE_EXCEPTIONAL_ENTRY));
> > +}
> 
> Would something like radix_tree_augmented() be a better name for this
> (with RADIX_TREE_AUGMENTED_MASK defined)? This one seems too easy to
> confuse with radix_tree_exceptional_entry() to me which is not the
> same thing, right?

They're not _quite_ the same thing, and I agree that a different naming
that would make it clearer (without going on and on) would be welcome.

But I don't think the word "augmented" helps or really fits in there.

What I had in mind was: there are two exceptional conditions which you
can meet in reading the radix tree, and radix_tree_exception() covers
both of those conditions.

One exceptional condition is the radix_tree_deref_retry() case, a
momentary condition where you just have to go back and read it again.

The other exceptional condition is the radix_tree_exceptional_entry():
you've read a valid entry, but it's not the usual type of thing stored
there, you need to be careful to process it differently (not try to
increment its "page" count in our case).

I'm fairly happy with "radix_tree_exceptional_entry" for the second;
we could make the test for both more explicit by calling it
"radix_tree_exceptional_entry_or_deref_retry", but
I grow bored before I reach the end of that!

Hugh