linux-kernel - Re: [PATCH 26/94] Maple Tree: Add new data structure

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: <20210514214230.wpsim46hpnyyzoe7@revolver>
Date:   Fri, 14 May 2021 21:42:32 +0000
From:   Liam Howlett <liam.howlett@...cle.com>
To:     Peter Zijlstra <peterz@...radead.org>
CC:     "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Song Liu <songliubraving@...com>,
        Davidlohr Bueso <dave@...olabs.net>,
        "Paul E . McKenney" <paulmck@...nel.org>,
        Matthew Wilcox <willy@...radead.org>,
        Laurent Dufour <ldufour@...ux.ibm.com>,
        David Rientjes <rientjes@...gle.com>,
        Axel Rasmussen <axelrasmussen@...gle.com>,
        Suren Baghdasaryan <surenb@...gle.com>,
        Vlastimil Babka <vbabka@...e.cz>,
        Rik van Riel <riel@...riel.com>,
        Michel Lespinasse <walken.cr@...il.com>
Subject: Re: [PATCH 26/94] Maple Tree: Add new data structure

* Peter Zijlstra <peterz@...radead.org> [210514 09:42]:
> On Wed, Apr 28, 2021 at 03:36:02PM +0000, Liam Howlett wrote:
> > +/*
> > + * mte_set_parent() - Set the parent node and encode the slot.
> > + * @enode: The encoded maple node.
> > + * @parent: The encoded maple node that is the parent of @enode.
> > + * @slot: The slot that @enode resides in @parent.
> > + *
> > + * Type is encoded in the enode->parent
> > + * bit 0: 1 = root, 0 otherwise
> > + * bit 1: Reserved.
> > + * bit 2: 0 = range 32, 1 = [a]range 64
> > + *
> > + * Slot number is encoded in the enode->parent
> > + * range_32, slot number is encoded in bits 3-6
> > + * [a]range_64, slot number is encoded in bits 3-6
> > + */
> > +static inline void mte_set_parent(struct maple_enode *enode,
> > +				 const struct maple_enode *parent,
> > +				 unsigned char slot)
> > +{
> > +	unsigned long bitmask = 0x78;
> > +	unsigned long val = (unsigned long) parent;
> > +	unsigned long type = 0;
> > +
> > +	switch (mte_node_type(parent)) {
> > +	case maple_range_64:
> > +	case maple_arange_64:
> > +		type = 6;
> 
> 6 = 4 + 2, which has bit1 set, but the above sayeth bit1 is reserved.

Yeah, that's not good.

> 
> It is also mighty confusing to have two different type fields, is there
> no way we can merge the types into a single (shared) space?
> 
> > +		break;
> > +	default:
> > +		break;
> > +	}
> > +
> > +	val &= ~bitmask; // Remove any old slot number.
> > +	val |= (slot << MAPLE_PARENT_SHIFT); // Set the slot.
> > +	val |= type;
> > +	mte_to_node(enode)->parent = ma_parent_ptr(val);
> > +}
> 


Sorry, this is more fallout from removing types for the initial merge..
I will re-examine the mte_set_paret/mte_parent_slot stuff and fix the
comments (note range 32 above is not even in this code base either).

The type space maple_range_64/maple_arange_64 cannot be merged into a
single type as they have different slot and pivot counts.  The type of
node it is depends on the immutable tree flag for alloc on creation
time.  Since both node types cannot exist in the same type of tree,
reusing the same value here allows for more node types to exist..
Merging them would cause multiple checks of the tree flag during a walk
and function pointers are not as fast as they used to be.

I can just set type to range/arange right now as it's the only option.

Thanks for highlighting this as confusing.  I'll rework this to be
easier to understand.