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.
