ext4: Adding itree feature and inode flags

This commit adds two new flags for the itree. A new read-only file
system feature flag:

    EXT4_FEATURE_RO_COMPAT_ITREE    0x1000

And an inode flag to indicate that a directory has itree:

    EXT4_ITREE_FL = 0x10000000
    EXT4_INODE_ITREE = 29

Also a macro for checking these flags on a directory was added.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Allow sorting dx_map by inode as well

This commit extends the code used by the dir index to sort its leaf
blocks by hash before splits.

The implementation of itree needs to do a similar sort when the tree
is initialized. The order however is different.

These changes allow sorting by inode using the same code.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Adding a link to itree to the dx_root struct

The dx_tail struct that can be stored at the end of each root block was
extended with an additional link to the itree root block.

This commit renames the dx_tail to dx_csum_entry and adds dx_itree_entry
that holds the 64bit block pointer to itree root.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Adding itree structures

This commit adds 5 new structures that will be used in the itree code.

On-disk:
    struct itree_entry      Single entry in an itree_node.
    struct itree_node       A non-leaf node in the itree.
    struct itree_leaf_head  Comes first in every itree leaf block.
    struct itree_leaf_entry A dirent in itree leaf.

Memory only:
    struct itree_frame      Represents a path through a tree to one of
                            its leaves.
    struct itree_key        For representing the key for itree, which
                            is an inode number and file name hash

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Adding itree implementation I - Core

This commit contains the basic code related to the new inode tree
including the common/helper functions, tree initialisation, and
a few functions for debugging.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Adding itree implementation II - Inserting

This commit contains functions that are related to inserting entries
to the inode tree including the functions that handle the node splits.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Adding itree implementation III - Deleting

This commit contains functions that are related to the deletion of
entries from the inode tree. This also includes the code related to
coalesce-on-delete.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Make directory operations use itree

This commits adds some changes to the existing directory operations so
they use the itree as well, apart from the original index tree.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>
ext4: Make ext4_readdir() use itree if available

This patch adds an alternative implementation of ext4_readdir() that
will read the directory in inode order in case there is a inode tree
available in the directory index.

Signed-off-by: Radek Pazdera <rpazdera@redhat.com>