ocfs2: Add a name indexed b-tree to directory inodes

[deliverable/linux.git] / fs / ocfs2 / ocfs2_fs.h

diff --git a/fs/ocfs2/ocfs2_fs.h b/fs/ocfs2/ocfs2_fs.h
index 2332ef740f4f9bc852ad064832d9fa5a161bb2fe..036eb03950a36715d584c9ff9aceda29a23a6bf5 100644 (file)
--- a/fs/ocfs2/ocfs2_fs.h
+++ b/fs/ocfs2/ocfs2_fs.h
@@ -66,6 +66,8 @@
 #define OCFS2_GROUP_DESC_SIGNATURE      "GROUP01"
 #define OCFS2_XATTR_BLOCK_SIGNATURE    "XATTR01"
 #define OCFS2_DIR_TRAILER_SIGNATURE    "DIRTRL1"
+#define OCFS2_DX_ROOT_SIGNATURE                "DXDIR01"
+#define OCFS2_DX_LEAF_SIGNATURE                "DXLEAF1"
 
 /* Compatibility flags */
 #define OCFS2_HAS_COMPAT_FEATURE(sb,mask)                      \
@@ -151,6 +153,9 @@
 /* Support for extended attributes */
 #define OCFS2_FEATURE_INCOMPAT_XATTR           0x0200
 
+/* Support for indexed directores */
+#define OCFS2_FEATURE_INCOMPAT_INDEXED_DIRS    0x0400
+
 /* Metadata checksum and error correction */
 #define OCFS2_FEATURE_INCOMPAT_META_ECC                0x0800
 
@@ -628,8 +633,9 @@ struct ocfs2_super_block {
 /*B8*/ __le16 s_xattr_inline_size;     /* extended attribute inline size
                                           for this fs*/
        __le16 s_reserved0;
-       __le32 s_reserved1;
-/*C0*/  __le64 s_reserved2[16];                /* Fill out superblock */
+       __le32 s_dx_seed[3];            /* seed[0-2] for dx dir hash.
+                                        * s_uuid_hash serves as seed[3]. */
+/*C0*/  __le64 s_reserved2[15];                /* Fill out superblock */
 /*140*/
 
        /*
@@ -705,7 +711,8 @@ struct ocfs2_dinode {
        __le16 i_dyn_features;
        __le64 i_xattr_loc;
 /*80*/ struct ocfs2_block_check i_check;       /* Error checking */
-/*88*/ __le64 i_reserved2[6];
+/*88*/ __le64 i_dx_root;               /* Pointer to dir index root block */
+       __le64 i_reserved2[5];
 /*B8*/ union {
                __le64 i_pad1;          /* Generic way to refer to this
                                           64bit union */
@@ -781,6 +788,75 @@ struct ocfs2_dir_block_trailer {
 /*40*/
 };
 
+ /*
+ * A directory entry in the indexed tree. We don't store the full name here,
+ * but instead provide a pointer to the full dirent in the unindexed tree.
+ *
+ * We also store name_len here so as to reduce the number of leaf blocks we
+ * need to search in case of collisions.
+ */
+struct ocfs2_dx_entry {
+       __le32          dx_major_hash;  /* Used to find logical
+                                        * cluster in index */
+       __le32          dx_minor_hash;  /* Lower bits used to find
+                                        * block in cluster */
+       __le64          dx_dirent_blk;  /* Physical block in unindexed
+                                        * tree holding this dirent. */
+};
+
+struct ocfs2_dx_entry_list {
+       __le32          de_reserved;
+       __le16          de_count;       /* Maximum number of entries
+                                        * possible in de_entries */
+       __le16          de_num_used;    /* Current number of
+                                        * de_entries entries */
+       struct  ocfs2_dx_entry          de_entries[0];  /* Indexed dir entries
+                                                        * in a packed array of
+                                                        * length de_num_used */
+};
+
+/*
+ * A directory indexing block. Each indexed directory has one of these,
+ * pointed to by ocfs2_dinode.
+ *
+ * This block stores an indexed btree root, and a set of free space
+ * start-of-list pointers.
+ */
+struct ocfs2_dx_root_block {
+       __u8            dr_signature[8];        /* Signature for verification */
+       struct ocfs2_block_check dr_check;      /* Error checking */
+       __le16          dr_suballoc_slot;       /* Slot suballocator this
+                                                * block belongs to. */
+       __le16          dr_suballoc_bit;        /* Bit offset in suballocator
+                                                * block group */
+       __le32          dr_fs_generation;       /* Must match super block */
+       __le64          dr_blkno;               /* Offset on disk, in blocks */
+       __le64          dr_last_eb_blk;         /* Pointer to last
+                                                * extent block */
+       __le32          dr_clusters;            /* Clusters allocated
+                                                * to the indexed tree. */
+       __le32          dr_reserved1;
+       __le64          dr_dir_blkno;           /* Pointer to parent inode */
+       __le64          dr_reserved2;
+       __le64          dr_reserved3[16];
+       struct ocfs2_extent_list        dr_list; /* Keep this aligned to 128
+                                                 * bits for maximum space
+                                                 * efficiency. */
+};
+
+/*
+ * The header of a leaf block in the indexed tree.
+ */
+struct ocfs2_dx_leaf {
+       __u8            dl_signature[8];/* Signature for verification */
+       struct ocfs2_block_check dl_check;      /* Error checking */
+       __le64          dl_blkno;       /* Offset on disk, in blocks */
+       __le32          dl_fs_generation;/* Must match super block */
+       __le32          dl_reserved0;
+       __le64          dl_reserved1;
+       struct ocfs2_dx_entry_list      dl_list;
+};
+
 /*
  * On disk allocator group structure for OCFS2
  */
@@ -1112,6 +1188,16 @@ static inline int ocfs2_extent_recs_per_inode_with_xattr(
        return size / sizeof(struct ocfs2_extent_rec);
 }
 
+static inline int ocfs2_extent_recs_per_dx_root(struct super_block *sb)
+{
+       int size;
+
+       size = sb->s_blocksize -
+               offsetof(struct ocfs2_dx_root_block, dr_list.l_recs);
+
+       return size / sizeof(struct ocfs2_extent_rec);
+}
+
 static inline int ocfs2_chain_recs_per_inode(struct super_block *sb)
 {
        int size;
@@ -1132,6 +1218,16 @@ static inline u16 ocfs2_extent_recs_per_eb(struct super_block *sb)
        return size / sizeof(struct ocfs2_extent_rec);
 }
 
+static inline int ocfs2_dx_entries_per_leaf(struct super_block *sb)
+{
+       int size;
+
+       size = sb->s_blocksize -
+               offsetof(struct ocfs2_dx_leaf, dl_list.de_entries);
+
+       return size / sizeof(struct ocfs2_dx_entry);
+}
+
 static inline u16 ocfs2_local_alloc_size(struct super_block *sb)
 {
        u16 size;