Skip to content

generic btree implementation, version 3

Christoph Hellwig linux-xfs 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest26 patches 18 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/26kill struct xfs_btree_hdrfs/xfs/xfs_btree.c fs/xfs/xfs_btree.h+7 -121 reply
2/26split up xfs_btree_init_cursorfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +9 more+196 -1580 replies
3/26add generic btree typesfs/xfs/xfs_btree.h+25 -00 replies
4/26make btree root in inode support genericfs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c fs/xfs/xfs_btree.h+30 -190 replies
5/26add a long pointers flag to xfs_btree_curfs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c fs/xfs/xfs_btree.h+5 -90 replies
6/26refactor xfs_btree_readaheadfs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c fs/xfs/xfs_btree.h+76 -720 replies
7/26refactor btree validation helpersfs/xfs/xfs_btree.c fs/xfs/xfs_btree.h+146 -1280 replies
8/26add new btree statisticsfs/xfs/linux-2.6/xfs_stats.c fs/xfs/linux-2.6/xfs_stats.h fs/xfs/xfs_btree.h+97 -00 replies
9/26make btree tracing genericfs/xfs/Makefile fs/xfs/linux-2.6/xfs_ksyms.c fs/xfs/linux-2.6/xfs_super.c +11 more+886 -3260 replies
10/26implement generic xfs_btree_incrementfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +9 more+303 -3050 replies
11/26implement generic xfs_btree_decrementfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +8 more+137 -2920 replies
12/26implement generic xfs_btree_lookupfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +9 more+557 -7350 replies
13/26implement generic xfs_btree_updkeyfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +2 more+201 -2150 replies
14/26implement generic xfs_btree_updatefs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +8 more+342 -2690 replies
15/26add get_maxrecs btree operationfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +2 more+32 -270 replies
16/26implement generic xfs_btree_rshiftfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +2 more+522 -4080 replies
17/26implement generic xfs_btree_lshiftfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +2 more+202 -4250 replies
18/26implement generic xfs_btree_splitfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +2 more+464 -5030 replies
19/26implement semi-generic xfs_btree_new_rootfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_btree.c fs/xfs/xfs_btree.h +1 more+171 -3050 replies
20/26move xfs_bmbt_newroot to common codefs/xfs/xfs_bmap.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_bmap_btree.h +2 more+115 -1201 reply
21/26implement generic xfs_btree_inѕert/insrecfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +8 more+483 -8732 replies
22/26move xfs_bmbt_killroot to common codefs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +2 more+181 -943 replies
23/26implement generic xfs_btree_delete/delrecfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +8 more+699 -17063 replies
24/26implement generic xfs_btree_getrecfs/xfs/xfs_alloc.c fs/xfs/xfs_alloc_btree.c fs/xfs/xfs_alloc_btree.h +6 more+90 -1022 replies
25/26kill xfs_bmbt_log_blockfs/xfs/xfs_bmap.c fs/xfs/xfs_bmap_btree.c fs/xfs/xfs_btree.c +1 more+7 -641 reply
26/26add rec_len and key_len fields to struct xfs_btree_opsfs/xfs/xfs_alloc_btree.c fs/xfs/xfs_bmap.c fs/xfs/xfs_bmap_btree.c +3 more+335 -7061 reply

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

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

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