Factor some btree code....

Only a small patch. ;)

basically, I need to introduce new formats to some of the btree block fields (crc, uuids) for resilience and recovery purposes. Rather than have to copy large chunks of three separate btree implementations, I decided that I'd factor them into one implementation first.

The approach I took was to build a bunch of ops structures taht each different btree structure could implement. basically, all the btrees do the same fundamental operations, so it shoul dbe easy to do. Right?

I've formed a "btree core" set of functions that operation on:

xfs_btree_block_t - a generic btree block
xfs_btree_key_t - a union of the different key types
xfs_btree_ptr_t - a union of the different pointer types
xfs_btree_rec_t - a union of the different record types

These are passed around the core btree code in disk endian format and the callouts convert to/from disk endian format as needed. there are operations for intialising keys, ptrs and records from either the cursor or other keys or records. There are operations for moving them, getting the address within the block of a given index within a block, logging the changes made etc.

There's various block operations e.g. allocating and freeing blocks, logging block headers, etc in a separate ops structure.

Some of the remaining operations are lumped into a "cursor ops" structure - I think I'll probably fold them back into the block ops structure, or even just make it one large ops structure for everything - there's really no need for multiple ops structures, except for....

... the btree tracing code. I haven't completed that yet, but the btree core inherits the tracing code from the bmap btree code, so we'll have fined grained tracing on all btree operations once this is complete.

The core btree code also got factored and commenting was improved; the result is that the code is now readable and understandable, which it certainly wasn't before I began this.

A further feature is that the core btree code now supports the btree root being placed in an inode. I still need to move the extent format code into the core as well as some of the root manipulation code, but in future the only difference between a pointer rooted btree (eg freespace trees) and an inode rooted btree (inode extent btree) will be a single flag being set in during the btree cursor initialisation.

The result of all this is a massive patch that cleans up a lot of stuff, introduces new functionality into the btree code and reduces each btree implementation down to a relatively simple set of operations to write. The freespace btrees (xfs_alloc_btree.c) have gone from 2200 lines to 900, the inode btree (xfs_ialloc_btree.c) has gone from 2000 lines to less than 800, and the bmap btree has gone from ~2600 lines to ~1400. There's probably more this can be reduced as well.

On top of this, modifying the btree structures will now involve writing only a handful of new functions to be written instead of duplicating most of those three files mentioned above.

The next question - does it work? Well, apart from test 042 (massively fragmented file and freespace btree) and occasional 013 (fstress) and 083 (fstress @ ENOSPC) corruptions, it runs fine. Indeed, I just did an apt-get update that replaced about 500MB of the binaries on the root drive of my test box, updated a git tree and rebuilt a kernel and the filesystem survived that just fine.

So, while I would not recommend it for production yet, it's definitely usable. The probelms remaining stem from level 3 btrees and larger, and I need the btree tracing code working to trace those problems (it doesn't work yet).

There's plenty still to clean up in the patch, but I thought that pushing it out early for comment would be better than leaving it until I had everything working.

Thoughts, comments, flames?

(Eric, I'm looking at you and your 3-way diffstats ;)

Cheers,

Dave.

13,113 lines not shown · raw message

Part of this message is not shown here. View the raw message.

I like this. But I think a single set of xfs_btree_ops would be a lot more readable. Also I'm not sure we actually need all these ops, e.g. instead of .buf_to_block we could always just call XFS_BUF_PTR directly.

I've already converted it to a single ops structure and cut out quite a few ops that could be generic (sibling ops, checking ops, numrecs ops, etc). I opted for moving them all over initially and now I'm culling the common stuff. .buf_to_block is another one that can go, .buf_to_ptr can be done generically, too....

I'm still flshing bugs out, so i haven't posted an update. When I get it to pass xfsqa I'll send out an updated patchset.

Cheers,

Dave.

Dave Chinner
Principal Engineer
SGI Australian Software Group