1 files changed, 99 insertions, 3 deletions

diff --git a/fs/ocfs2/ocfs2_fs.h b/fs/ocfs2/ocfs2_fs.h
index 2332ef740f4f..036eb03950a3 100644
--- 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;