Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Wed, 15 Jun 2022 14:40:43 +0100
From:   Matthew Wilcox <willy@infradead.org>
To:     Brian Foster <bfoster@redhat.com>
Cc:     Christoph Hellwig <hch@infradead.org>,
        linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
        ikent@redhat.com, onestero@redhat.com
Subject: Re: [PATCH 1/3] radix-tree: propagate all tags in idr tree
Message-ID: <YqnhW2CI1kbJ3NqR@casper.infradead.org>
References: <20220614180949.102914-1-bfoster@redhat.com>
 <20220614180949.102914-2-bfoster@redhat.com>
 <Yqm+jmkDA+um2+hd@infradead.org>
 <YqnXVMtBkS2nbx70@bfoster>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <YqnXVMtBkS2nbx70@bfoster>
Precedence: bulk

On Wed, Jun 15, 2022 at 08:57:56AM -0400, Brian Foster wrote:
> On Wed, Jun 15, 2022 at 04:12:14AM -0700, Christoph Hellwig wrote:
> > On Tue, Jun 14, 2022 at 02:09:47PM -0400, Brian Foster wrote:
> > > The IDR tree has hardcoded tag propagation logic to handle the
> > > internal IDR_FREE tag and ignore all others. Fix up the hardcoded
> > > logic to support additional tags.
> > > 
> > > This is specifically to support a new internal IDR_TGID radix tree
> > > tag used to improve search efficiency of pids with associated
> > > PIDTYPE_TGID tasks within a pid namespace.
> > 
> > Wouldn't it make sense to switch over to an xarray here rather
> > then adding new features to the radix tree?
> > 
> 
> The xarray question crossed my mind when I first waded into this code
> and realized the idr tree seems to be some sort of offshoot or custom
> mode of the core radix tree. I eventually realized that the problem wrt
> to normal radix tree tags in the idr variant was that the tag
> propagation logic in the idr variant simply didn't care to handle
> traditional tags, presumably because they were unused in that mode. So
> this patch doesn't really add a feature to the radix-tree, it just fixes
> up some of the grotty idr tree logic to handle both forms of tags.
> 
> I assume it makes sense for this to move towards xarray in general, but
> I don't have enough context on either side to know what the sticking
> points are. In particular, does xarray support something analogous to
> IDR_FREE or otherwise solve whatever problem idr currently depends on it
> for (i.e. efficient id allocation)? I think Willy has done work in this
> area so I'm hoping he can chime in on some of that if he's put any
> thought into the idr thing specifically..

Without going into the history of the idr/radix-tree/xarray, the
current hope is that we'll move all users of the idr & radix tree
over to the xarray API.  It's fundamentally the same data structure
for all three now, just a question of the API change. 

The XArray does indeed have a way to solve the IDR_FREE problem;
you need to declare an allocating XArray:
https://www.kernel.org/doc/html/latest/core-api/xarray.html#allocating-xarrays

and using XA_MARK_1 and XA_MARK_2 should work the way you want them to.