[PATCH 00/26] generic btree implementation, version 3

[PATCH 00/26] generic btree implementation, version 3

[Christoph Hellwig]

Firstly all but one of Dave's review comments are addressed. There is also
a new first patch to clean up the defintion of struct xfs_btree_block which
I would consider an ASAP merge candidate.

But there are also some bigger changes.  For reimplemented the newroot and
killroot methods.  In both cases one method was used for block rooted and
inode rooted btree but doing something quite different.  This patchset
gets rid of these two method completely and implements both cases in
xfs_btree.c.  For new_root that was as easy as just calling
xfs_btree_new_root directly for the !XFS_BTREE_ROOT_IN_INODE and moving
xfs_bmbt_newroot into the common code and calling it for the other case.
The XFS_BTREE_ROOT_IN_INODE case for kill_root was similarly easily solved
by just moving the code around and making it block/rec/key/ptr size
agnostic, but the !XFS_BTREE_ROOT_IN_INODE needed a little care.

The alloc and inobt trees were in fact using the almost exact sequence
built from ->set_root and ->free_block but the odd way to pass the
block to be freed made this non-obvious.  By changing the calling
convention to the normal one this one could be unified.  I've left
in some nasty asserts to ensure the assumptions about these blocks
wasn't wrong.

The other big news is the last patch in the series, which adds rec_len
and key_len members to the btree_ops structure and uses this to make the
ptr_addr, key_addr, rec_addr, set_key, set_rec, move_keys, move_recs,
copy_keys, copy_recsm log_keys and log_recs methods generic.  This
patch by itselfs saves a few hundred lines of code and more than two
kilobytes in the binary image.  With this eventual worse generated
code that needs to multiply by variables instead of constants should
easily be offset by the reduced instruction cache footprint.  The patch
is so far not really comments and more a proof of concept - if everyone
agrees with this approach the changes will be merged into the earlier
patches.

Now even with this move the set_*, move_* and copy_* interfaces are
left as-is.  All the old discussion still applies except that things
might be a little more clear now that there's just one implementation
each and everything is contained in one file.  I think keeping the
copy_* interfaces is a good idea, they are now basically just typed
memcpy wrappers - although we should switch the order of the src
and dst arguments to be the same as memcpy.  The set_* interfaces
can probably go away - over copy_ they just add the index based
addressing which most callers don't use anyway.  I'm not sure
what to do with move_* - these are the most ugly helpers, so maybe
we should just make them memmove wrappers in the style of copy_
and leave all addressing to the callers.


With all these changes the stats for this series are now:

 37 files changed, 6309 insertions(+), 7873 deletions(-)

   text	   data	    bss	    dec	    hex	filename
 631577	   4227	   3092	 638896	  9bfb0	fs/xfs/xfs.ko.base
 614298	   4435	   3124	 621857	  97d21	fs/xfs/xfs.ko.btree

-- 

Re: [PATCH 00/26] generic btree implementation, version 3

[Christoph Hellwig]

On Mon, Aug 04, 2008 at 11:54:25AM +1000, Dave Chinner wrote:
> > With all these changes the stats for this series are now:
> > 
> >  37 files changed, 6309 insertions(+), 7873 deletions(-)
> > 
> >    text	   data	    bss	    dec	    hex	filename
> >  631577	   4227	   3092	 638896	  9bfb0	fs/xfs/xfs.ko.base
> >  614298	   4435	   3124	 621857	  97d21	fs/xfs/xfs.ko.btree
> 
> FWIW, this aggregate doesn't show the real picture of the savings.
> What is really interesting is how small the individual
> implementations become....

hch@bigmac:~/work/linux-2.6-xfs$ wc -l fs/xfs/xfs{_alloc,_ialloc,_bmap,}_btree.c
   409 fs/xfs/xfs_alloc_btree.c
   309 fs/xfs/xfs_ialloc_btree.c
   858 fs/xfs/xfs_bmap_btree.c
  3813 fs/xfs/xfs_btree.c
  5389 total

hch@bigmac:~/work/linux-2.6-xfs$ size
fs/xfs/xfs{_alloc,_ialloc,_bmap,}_btree.o
   text	   data	    bss	    dec	    hex	filename
   2335	      0	      4	   2339	    923	fs/xfs/xfs_alloc_btree.o
   1589	      0	      4	   1593	    639	fs/xfs_ialloc_btree.o
   5827	      0	      4	   5831	   16c7 fs/xfs/xfs_bmap_btree.o
  32785	      0	      4	  32789	   8015 fs/xfs/xfs_btree.o

In comparism for the old code:

hch@bigmac:~/work/linux-2.6-xfs$ wc -l fs/xfs/xfs{_alloc,_ialloc,_bmap,}_btree.c
  2211 fs/xfs/xfs_alloc_btree.c
  2078 fs/xfs/xfs_ialloc_btree.c
  2610 fs/xfs/xfs_bmap_btree.c
   914 fs/xfs/xfs_btree.c
  7813 total

hch@bigmac:~/work/linux-2.6-xfs$ size fs/xfs/xfs{_alloc,_ialloc,_bmap,}_btree.o
   text	   data	    bss	    dec	    hex	filename
  13383	      0	      0	  13383	   3447	fs/xfs/xfs_alloc_btree.o
  12923	      0	      0	  12923	   327b fs/xfs/xfs_ialloc_btree.o
  28870	     22	      4	  28896	   70e0	fs/xfs/xfs_bmap_btree.o
   7062	      0	      4	   7066	   1b9a fs/xfs/xfs_btree.o

Re: [PATCH 00/26] generic btree implementation, version 3

[Christoph Hellwig]

On Mon, Aug 04, 2008 at 11:54:25AM +1000, Dave Chinner wrote:
> > I'm not sure
> > what to do with move_* - these are the most ugly helpers, so maybe
> > we should just make them memmove wrappers in the style of copy_
> > and leave all addressing to the callers.
> 
> Yes, it would be nice to have them use the same interface. If
> we do that, then there's no real point for having a copy vs move
> distinction - we could just make everything use the
> memmove version and drop one of the interfaces altogether....

I've actually come up with another variant.  Since what we do in the
memmove case is to move a number of entries in a single block up or down
one position I've added the following helper:

STATIC void
xfs_btree_shift_keys(
	struct xfs_btree_cur    *cur,
	union xfs_btree_key     *key
	int                     dir,
	int                     numkeys)
{
	char			*dst_key;

	ASSERT(numkeys >= 0);
	ASSERT(dir == 1 || dir == -1);

	dst_key = (char *)key + (dir * cur->bc_ops->key_len);
	memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
}

and the same for ptrs and recs.  This follows the original code in
spirit and is quite readable.

Re: [PATCH 00/26] generic btree implementation, version 3

[Dave Chinner]

On Mon, Aug 04, 2008 at 04:21:32PM +0200, Christoph Hellwig wrote:
> On Mon, Aug 04, 2008 at 11:54:25AM +1000, Dave Chinner wrote:
> > > I'm not sure
> > > what to do with move_* - these are the most ugly helpers, so maybe
> > > we should just make them memmove wrappers in the style of copy_
> > > and leave all addressing to the callers.
> > 
> > Yes, it would be nice to have them use the same interface. If
> > we do that, then there's no real point for having a copy vs move
> > distinction - we could just make everything use the
> > memmove version and drop one of the interfaces altogether....
> 
> I've actually come up with another variant.  Since what we do in the
> memmove case is to move a number of entries in a single block up or down
> one position I've added the following helper:
> 
> STATIC void
> xfs_btree_shift_keys(
> 	struct xfs_btree_cur    *cur,
> 	union xfs_btree_key     *key
> 	int                     dir,
> 	int                     numkeys)
> {
> 	char			*dst_key;
> 
> 	ASSERT(numkeys >= 0);
> 	ASSERT(dir == 1 || dir == -1);
> 
> 	dst_key = (char *)key + (dir * cur->bc_ops->key_len);
> 	memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
> }
> 
> and the same for ptrs and recs.  This follows the original code in
> spirit and is quite readable.

Nice. That fits nicely into the 'make a hole' or 'fill a hole' parts
of various functions which will remove a lot of magic from them.
The only thing I'd do is add an enum for the direction so the
callers are self-documenting as to the direction of the shift....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: [PATCH 00/26] generic btree implementation, version 3

[Christoph Hellwig]

On Mon, Aug 04, 2008 at 11:54:25AM +1000, Dave Chinner wrote:
> > The alloc and inobt trees were in fact using the almost exact sequence
> > built from ->set_root and ->free_block but the odd way to pass the
> > block to be freed made this non-obvious.  By changing the calling
> > convention to the normal one this one could be unified.  I've left
> > in some nasty asserts to ensure the assumptions about these blocks
> > wasn't wrong.
> 
> Ok. I'll comment on it when the patches come through....

The killroot unification turned out to be buggy, I'll fix it in the
next round of patches.