On Wed, Jun 15, 2022 at 02:40:43PM +0100, Matthew Wilcox wrote: > 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. > Interesting, thanks. I'll have to dig more into this to grok the current state of the radix-tree interface vs. the underlying data structure. If I follow correctly, you're saying the radix-tree api is essentially already a translation layer to the xarray these days, and we just need to move legacy users off the radix-tree api so we can eventually kill it off... Brian
