Re: [PATCH 08/47] xfs: support btrees with overlapping intervals for keys

Dave Chinner
2016-08-03T01:07:04Z

On Tue, Aug 02, 2016 at 10:04:12AM -0400, Brian Foster wrote:
> On Mon, Aug 01, 2016 at 12:11:26PM -0700, Darrick J. Wong wrote:
> > On Sun, Jul 31, 2016 at 11:48:18PM -0700, Christoph Hellwig wrote:
> ...
> > >
> > > > +++ b/fs/xfs/libxfs/xfs_btree.c
> ...
> > > I don't understand the purpose of this union at all, and the comment
> > > seems misleading. Compared to union xfs_btree_key the only difference
> > > seems to be that xfs_btree_bigkey is missing the
> > > 'struct xfs_rmap_key rmap' member. How does that enable us to holds
> >
> > I think you might be missing a later patch, wherein we add the rmap
> > stuff to the btree structures, which expands bigkey to look like this:
> >
> > union xfs_btree_bigkey {
> > struct xfs_bmbt_key bmbt;
> > xfs_bmdr_key_t bmbr; /* bmbt root block */
> > xfs_alloc_key_t alloc;
> > struct xfs_inobt_key inobt;
> > struct {
> > struct xfs_rmap_key rmap;
> > struct xfs_rmap_key rmap_hi;
> > };
> > struct xfs_refcount_key refc;
> > };
> >
> > bigkey.rmap is the low key, bigkey.rmap_hi is the high key. None of
> > the other btrees are overlapped, so they don't get a high key.
> >
> > > low and high keys? Also every single user seems to cast it to
> > > xfs_btree_key which is a little odd and smells unsafe.
> >
> > On disk, the low and high keys of a pointer reside next to each other.
> > The btree_split code wants to store the new block's keys somewhere so
> > that the block can later be insrec'd into a higher btree level. It
> > would be convenient if this incore storage could also store the two
> > keys right next to each other so that we can memcpy key_len bytes from
> > the temporary storage into the on-disk btree block and not have to
> > special case that code.
> >
> > I thought about simply declaring an on-stack array of two union
> > xfs_btree_keys. The array is big enough to contain both keys and
> > eliminates the need for casting. On the other hand it's weird because
> > the two keys have to be aligned to xfs_rmap_key boundaries, not
> > xfs_btree_key, which means that the high key isn't necessarily stored
> > in the second array element like the code would suggest.
> >
>
> Thanks for writing this up...
>
> I'm wondering if we should define an in-core key structure variant
> similar to what we have for in-core records. That structure could
> encapsulate the low/high key model and use the already-defined in-core
> record structures (I suppose we could define tree-specific ikey
> variants, but I'll leave that alone for now). For example:
>
> struct xfs_btree_ikey {
> union xfs_bree_irec lo;
> union xfs_btree_irec hi;
> }
>
> Then define some conversion functions, tease apart the bits of the
> generic btree code that use the on-disk structure for in-memory storage
> vs. on-disk buffer references, and use the in-core structure for all
> instances of the former.
>
> That most certainly would mean more changes (as an indepedent patch) and
> tbh, it's not yet clear to me whether we'd run into other roadblocks
> that make it too ugly an option or just not worth it. I do feel like
> we're trying a bit too hard to retrofit the extra complexity of the
> multi-key model into the current design, however, and should try to
> explicitly define the multi-key model if we can find a reasonably
> elegant way to do so. Even passing around the xfs_btree_bigkey structure
> seems safer to me than pretending it's an xfs_btree_key and relying on
> key_len to make sure we copy the right amount of data or that we've
> defined bigkey in the right layers of the call stack. Thoughts?

Yes, we should clean it up, but I'm not going to hold off merging
because of this. We can clean this sort of thing up as followup
patches.

Cheers,

Dave.
--
Dave Chinner
david@fromorbit.com