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: <20210515000206.u5l44sgr6xzmpe5d@revolver>
Date:   Sat, 15 May 2021 00:02:12 +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 11:40]:
> On Wed, Apr 28, 2021 at 03:36:02PM +0000, Liam Howlett wrote:
> > +/*
> > + * mas_set_alloc_req() - Set the requested number of allocations.
> > + * @mas: the maple state
> > + * @count: the number of allocations.
> > + *
> > + * If @mas->alloc has bit 1 set (0x1) or @mas->alloc is %NULL, then there are no
> > + * nodes allocated and @mas->alloc should be set to count << 1 | 1.  If there is
> > + * already nodes allocated, then @mas->alloc->request_count stores the request.
> > + */
> > +static inline void mas_set_alloc_req(struct ma_state *mas, unsigned long count)
> > +{
> > +	if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) {
> > +		if (!count)
> > +			mas->alloc = NULL;
> > +		else
> > +			mas->alloc = (struct maple_alloc *)(((count) << 1U) | 1U);
> > +		return;
> > +	}
> > +
> > +	mas->alloc->request_count = count;
> > +}
> > +
> > +/*
> > + * mas_alloc_req() - get the requested number of allocations.
> > + * @mas: The maple state
> > + *
> > + * The alloc count is either stored directly in @mas, or in
> > + * @mas->alloc->request_count if there is at least one node allocated.
> > + *
> > + * Return: The allocation request count.
> > + */
> > +static inline unsigned int mas_alloc_req(const struct ma_state *mas)
> > +{
> > +	if ((unsigned long)mas->alloc & 0x1)
> > +		return (unsigned long)(mas->alloc) >> 1;
> > +	else if (mas->alloc)
> > +		return mas->alloc->request_count;
> > +	return 0;
> > +}
> 
> 
> I'm confuse.. and the comments fail to eludicate *why* the code is the
> way it is, they simply explain exactly what the code does, which I can
> already tell from reading the code.
> 
> Why can't we have ->request_count unconditionally be the requested
> count, and have ->alloc be NULL or not. Why do we play games with low
> pointer bits here? AFAICT there's no actual benefit to doing so.
> 
> 


That comment was written by me before I coded the function.  I meant to
replace it.

The maple state stores the first node into alloc.  The alloc stores the
request_count if more nodes are needed than already allocated.  If there
is no nodes allocated, then the request count is stored directly into
alloc.  We do the low pointer bit game to reduce the maple state size.

In other words, the mas->alloc is overloaded to either hold an
allocation or the number of requested allocations.  Bit 1 indicates that
mas->alloc holds a request to alloc (mas->alloc >> 1) nodes.