Re: [PATCH 11/16] f2fs: add inode operations for special inodes

[Arnd Bergmann <arnd@arndb.de>]

On Tuesday 16 October 2012, Jaegeuk Kim wrote:
> > IIRC, fs2fs uses 4k inodes, so IMO per-inode xattr tress with
> > internal storage before spilling to an external block is probably
> > the best approach to take...
> 
> Yes, indeed this is the best approach to f2fs's xattr.
> Apart from giving fs hints, it is worth enough to optimize later.

I've thought a bit more about how this could be represented efficiently
in 4KB nodes. This would require a significant change of the way you
represent inodes, but can improve a number of things at the same time.

The idea is to replace the fixed area in the inode that contains block
pointers with an extensible TLV (type/length/value) list that can contain
multiple variable-length fields, like this. All TLVs together with the
fixed-length inode data can fill a 4KB block.

The obvious types would be:

* Direct file contents if the file is less than a block
* List of block pointers, as before, minimum 1, maximum until the end
  of the block
* List of indirect pointers, now also a variable length, similar to the
  list of block pointers
* List of double-indirect block pointers
* direct xattr: zero-terminated attribute name followed by contents
* indirect xattr: zero-terminated attribute name followed by up to
  16 block pointers to store a maximum of 64KB sized xattrs

This could be extended later to cover additional types, e.g. a list
of erase block pointers, triple-indirect blocks or extents.

As a variation of this, it would also be nice to turn around the order
in which the pointers are walked, to optimize for space and for growing
files, rather than for reading the beginning of a file. With this, you
can represent a 9 KB file using a list of two block pointers, and 1KB
of direct data, all in the inode. When the user adds another byte, you
only need to rewrite the inode. Similarly, a 5 MB file would have a
single indirect node (covering block pointers for 4 MB), plus 256
separate block pointers (covering the last megabyte), and a 5 GB file
can be represented using 1 double-indirect node and 256 indirect nodes,
and each of them can still be followed by direct "tail" data and
extended attributes.

	Arnd