extents in e2fsprogs

Index: e2fsprogs-1.39/lib/ext2fs/block.c
===================================================================
--- e2fsprogs-1.39.orig/lib/ext2fs/block.c	2006-05-31 15:44:49.000000000 +0200
+++ e2fsprogs-1.39/lib/ext2fs/block.c	2006-06-14 13:25:47.000000000 +0200
@@ -17,6 +17,7 @@
 
 #include "ext2_fs.h"
 #include "ext2fs.h"
+#include "ext3_extents.h"
 
 struct block_context {
 	ext2_filsys	fs;
@@ -36,6 +37,102 @@ struct block_context {
 	void	*priv_data;
 };
 
+#define DEBUG_EXT 0
+
+#if DEBUG_EXT
+void show_header(struct ext3_extent_header *eh)
+{
+        printf("header: magic=%x, entries=%d, max=%d, depth=%d, generation=%d,",
+	       eh->eh_magic, eh->eh_entries, eh->eh_max, eh->eh_depth,
+	       eh->eh_generation);
+}
+
+void show_index(struct ext3_extent_header *eh)
+{
+        struct ext3_extent_idx *ix;
+        int i;
+
+        ix = EXT_FIRST_INDEX(eh);
+        printf("this node has %d indexs\n",eh->e_num);
+        for (i = 0; i < eh->eh_entries; i++, ix++) {
+                printf("index %d, block = %d, leaf = %d\n", i,
+		       ix->ei_block, ix->ei_leaf);
+        }
+}
+
+void show_extent(struct ext3_extent_header *eh)
+{
+        struct ext3_extent *ex;
+        int i;
+
+        ex = EXT_FIRST_EXTENT(eh);
+        printf("this node has %d extents\n", eh->e_len);
+}
+#else
+#define show_header(eh) do { } while (0)
+#define show_index(eh) do { } while (0)
+#define show_extent(eh) do { } while (0)
+#endif
+
+static int block_iterate_extents(struct ext3_extent_header *eh, ext2_filsys fs,
+				 struct block_context *ctx)
+{
+        int ret = 0;
+        int i,j;
+        char * block_buf;
+        blk_t  block_address;
+        struct ext3_extent *ex;
+        struct ext3_extent_idx *ix;
+        struct ext3_extent_header *nh;
+
+        if(eh->eh_depth == 0) {
+                show_extent(eh);
+                ex = EXT_FIRST_EXTENT(eh);
+                for (i = 0; i < eh->eh_entries; i++, ex++) {
+                        for(j=0; j< ex->ee_len; j++) {
+                                block_address = ex->ee_start + j;
+				ret = (*ctx->func)(ctx->fs, &block_address,
+						   (ex->ee_block + j), 0,
+						   i, ctx->priv_data);
+                        }
+                }
+        } else {
+		show_index(eh);
+                ret = ext2fs_get_mem(fs->blocksize, &block_buf);
+                if (ret)
+                        return ret;
+                ix = EXT_FIRST_INDEX(eh);
+                for (i = 0; i < eh->eh_entries; i++, ix++) {
+			block_address = ix->ei_leaf;
+			ret = (*ctx->func)(ctx->fs, &block_address,
+					   BLOCK_COUNT_IND, 0, i, ctx->priv_data);
+			if (ret & BLOCK_ABORT) {
+				ext2fs_free_mem(&block_buf);
+				return ret;
+			}
+			ctx->errcode = io_channel_read_blk(ctx->fs->io,
+							   ix->ei_leaf, 1,
+							   block_buf);
+			if(ctx->errcode) {
+				ret |= BLOCK_ERROR;
+				ext2fs_free_mem(&block_buf);
+				return ret;
+			}
+			nh = (struct ext3_extent_header *)block_buf;
+			show_header(nh);
+			if (nh->eh_magic != EXT3_EXT_MAGIC)
+			{
+				ret |= BLOCK_ERROR;
+				ext2fs_free_mem(&block_buf);
+				return ret;
+			}
+			ret = block_iterate_extents(nh, fs, ctx);
+                }
+		ext2fs_free_mem(&block_buf);
+	}
+	return ret;
+}
+
 static int block_iterate_ind(blk_t *ind_block, blk_t ref_block,
 			     int ref_offset, struct block_context *ctx)
 {
@@ -283,6 +380,7 @@ errcode_t ext2fs_block_iterate2(ext2_fil
 	errcode_t	retval;
 	struct block_context ctx;
 	int	limit;
+        struct ext3_extent_header * eh;
 
 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 
@@ -338,7 +436,23 @@ errcode_t ext2fs_block_iterate2(ext2_fil
 				goto abort_exit;
 		}
 	}
-	
+
+	/*
+	 * Iterate over normal data blocks with extents
+	 */
+        ext2fs_read_inode(fs, ino, &inode);
+        if (inode.i_flags & EXT3_EXTENTS_FL) {
+                eh = (struct ext3_extent_header *)&inode.i_block[0];
+                if (eh->eh_magic == EXT3_EXT_MAGIC) {
+		        show_header(eh);
+                        ret = block_iterate_extents(eh, fs, &ctx);
+                        goto abort_exit;
+                } else {
+                        inode.i_flags &= ~(EXT3_EXTENTS_FL);
+                        ext2fs_write_inode(fs, ino, &inode);
+                }
+        }
+
 	/*
 	 * Iterate over normal data blocks
 	 */
Index: e2fsprogs-1.39/lib/ext2fs/bmap.c
===================================================================
--- e2fsprogs-1.39.orig/lib/ext2fs/bmap.c	2006-05-31 15:44:49.000000000 +0200
+++ e2fsprogs-1.39/lib/ext2fs/bmap.c	2006-06-14 13:25:47.000000000 +0200
@@ -17,6 +17,7 @@
 
 #include "ext2_fs.h"
 #include "ext2fs.h"
+#include "ext3_extents.h"
 
 #if defined(__GNUC__) && !defined(NO_INLINE_FUNCS)
 #define _BMAP_INLINE_	__inline__
@@ -31,6 +32,49 @@ extern errcode_t ext2fs_bmap(ext2_filsys
 
 #define inode_bmap(inode, nr) ((inode)->i_block[(nr)])
 
+static int block_extents_bmap(struct ext3_extent_header *eh, ext2_filsys fs,
+			      blk_t block, blk_t *phys_blk)
+{
+	int ret = 0;
+	int i;
+	char * block_buf;
+	struct ext3_extent *ex;
+	struct ext3_extent_idx *ix;
+	struct ext3_extent_header *nh;
+
+	if(eh->eh_depth == 0) {
+		ex = EXT_FIRST_EXTENT(eh);
+		for (i = 0; i < eh->eh_entries; i++, ex++)
+			if ( (ex->ee_block <= block) && (block < ex->ee_block +  ex->ee_len) ) {
+				*phys_blk = ex->ee_start + (block - ex->ee_block);
+				return 0;
+			}
+		return BLOCK_ERROR;
+	} else {
+		ret = ext2fs_get_mem(fs->blocksize, &block_buf);
+		if (ret)
+			return ret;
+		ix = EXT_FIRST_INDEX(eh);
+		for (i = 0; i < eh->eh_entries; i++, ix++) {
+			ret = io_channel_read_blk(fs->io,
+						  ix->ei_leaf, 1,
+						  block_buf);
+			if (ret) {
+				ext2fs_free_mem(&block_buf);
+				return BLOCK_ERROR;
+			}
+			nh = (struct ext3_extent_header *)block_buf;
+			if (nh->eh_magic != EXT3_EXT_MAGIC) {
+				ext2fs_free_mem(&block_buf);
+				return BLOCK_ERROR;
+			}
+			ret = block_extents_bmap(nh, fs, block, phys_blk);
+		}
+		ext2fs_free_mem(&block_buf);
+	}
+	return ret;
+}
+
 static _BMAP_INLINE_ errcode_t block_ind_bmap(ext2_filsys fs, int flags, 
 					      blk_t ind, char *block_buf, 
 					      int *blocks_alloc,
@@ -144,6 +188,7 @@ errcode_t ext2fs_bmap(ext2_filsys fs, ex
 	char	*buf = 0;
 	errcode_t	retval = 0;
 	int		blocks_alloc = 0, inode_dirty = 0;
+	struct ext3_extent_header * eh;
 
 	if (!(bmap_flags & BMAP_SET))
 		*phys_blk = 0;
@@ -155,6 +200,15 @@ errcode_t ext2fs_bmap(ext2_filsys fs, ex
 			return retval;
 		inode = &inode_buf;
 	}
+
+	if (inode->i_flags & EXT3_EXTENTS_FL) {
+		eh = (struct ext3_extent_header *)&inode->i_block[0];
+		if (eh->eh_magic == EXT3_EXT_MAGIC)
+			return block_extents_bmap(eh, fs, block, phys_blk);
+		else
+			return BLOCK_ERROR;
+	}
+
 	addr_per_block = (blk_t) fs->blocksize >> 2;
 
 	if (!block_buf) {
Index: e2fsprogs-1.39/lib/ext2fs/ext2fs.h
===================================================================
--- e2fsprogs-1.39.orig/lib/ext2fs/ext2fs.h	2006-06-14 12:35:51.000000000 +0200
+++ e2fsprogs-1.39/lib/ext2fs/ext2fs.h	2006-06-14 13:25:47.000000000 +0200
@@ -453,12 +453,14 @@ typedef struct ext2_icount *ext2_icount_
 					 EXT2_FEATURE_INCOMPAT_COMPRESSION|\
 					 EXT3_FEATURE_INCOMPAT_JOURNAL_DEV|\
 					 EXT2_FEATURE_INCOMPAT_META_BG|\
-					 EXT3_FEATURE_INCOMPAT_RECOVER)
+					 EXT3_FEATURE_INCOMPAT_RECOVER|\
+					 EXT3_FEATURE_INCOMPAT_EXTENTS)
 #else
 #define EXT2_LIB_FEATURE_INCOMPAT_SUPP	(EXT2_FEATURE_INCOMPAT_FILETYPE|\
 					 EXT3_FEATURE_INCOMPAT_JOURNAL_DEV|\
 					 EXT2_FEATURE_INCOMPAT_META_BG|\
-					 EXT3_FEATURE_INCOMPAT_RECOVER)
+					 EXT3_FEATURE_INCOMPAT_RECOVER|\
+					 EXT3_FEATURE_INCOMPAT_EXTENTS)
 #endif
 #define EXT2_LIB_FEATURE_RO_COMPAT_SUPP	(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER|\
 					 EXT2_FEATURE_RO_COMPAT_LARGE_FILE)
Index: e2fsprogs-1.39/lib/ext2fs/mkdir.c
===================================================================
--- e2fsprogs-1.39.orig/lib/ext2fs/mkdir.c	2006-05-31 15:44:49.000000000 +0200
+++ e2fsprogs-1.39/lib/ext2fs/mkdir.c	2006-06-14 13:25:47.000000000 +0200
@@ -25,6 +25,7 @@
 
 #include "ext2_fs.h"
 #include "ext2fs.h"
+#include "ext3_extents.h"
 
 #ifndef EXT2_FT_DIR
 #define EXT2_FT_DIR		2
@@ -83,10 +84,26 @@ errcode_t ext2fs_mkdir(ext2_filsys fs, e
 	inode.i_mode = LINUX_S_IFDIR | (0777 & ~fs->umask);
 	inode.i_uid = inode.i_gid = 0;
 	inode.i_blocks = fs->blocksize / 512;
-	inode.i_block[0] = blk;
 	inode.i_links_count = 2;
 	inode.i_ctime = inode.i_atime = inode.i_mtime = fs->now ? fs->now : time(NULL);
 	inode.i_size = fs->blocksize;
+	if (fs->super->s_feature_ro_compat & EXT2_FEATURE_RO_COMPAT_64BIT) {
+		struct ext3_extent_header *eh = (struct ext3_extent_header *)inode.i_block;
+		struct ext3_extent *ex = EXT_FIRST_EXTENT(eh);
+
+		 eh->eh_magic = EXT3_EXT_MAGIC;
+		 eh->eh_depth = 0;
+		 eh->eh_entries = 1;
+		 eh->eh_max = (sizeof(inode.i_block) - sizeof(struct ext3_extent_header))
+			 / sizeof(struct ext3_extent);
+		 ex->ee_block = 0;
+		 ex->ee_start = blk;
+		 ex->ee_len = 1;
+
+		 inode.i_flags = EXT3_EXTENTS_FL;
+	} else {
+		inode.i_block[0] = blk;
+	}
 
 	/*
 	 * Write out the inode and inode data block
Index: e2fsprogs-1.39/lib/ext2fs/ext3_extents.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ e2fsprogs-1.39/lib/ext2fs/ext3_extents.h	2006-06-14 13:25:47.000000000 +0200
@@ -0,0 +1,238 @@
+/*
+ * Copyright (c) 2003,2004 Cluster File Systems, Inc, [email protected]
+ * Written by Alex Tomas <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public Licens
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
+ */
+
+#ifndef _LINUX_EXT3_EXTENTS
+#define _LINUX_EXT3_EXTENTS
+
+/*
+ * with AGRESSIVE_TEST defined capacity of index/leaf blocks
+ * become very little, so index split, in-depth growing and
+ * other hard changes happens much more often
+ * this is for debug purposes only
+ */
+#define AGRESSIVE_TEST_
+
+/*
+ * if CHECK_BINSEARCH defined, then results of binary search
+ * will be checked by linear search
+ */
+#define CHECK_BINSEARCH_
+
+/*
+ * if EXT_DEBUG is defined you can use 'extdebug' mount option
+ * to get lots of info what's going on
+ */
+#define EXT_DEBUG
+#ifdef EXT_DEBUG
+#define ext_debug(tree,fmt,a...) 			\
+do {							\
+	if (test_opt((tree)->inode->i_sb, EXTDEBUG))	\
+		printk(fmt, ##a);			\
+} while (0);
+#else
+#define ext_debug(tree,fmt,a...)
+#endif
+
+/*
+ * if EXT_STATS is defined then stats numbers are collected
+ * these number will be displayed at umount time
+ */
+#define EXT_STATS_
+
+
+#define EXT3_ALLOC_NEEDED	3	/* block bitmap + group desc. + sb */
+
+/*
+ * ext3_inode has i_block array (total 60 bytes)
+ * first 4 bytes are used to store:
+ *  - tree depth (0 mean there is no tree yet. all extents in the inode)
+ *  - number of alive extents in the inode
+ */
+
+/*
+ * this is extent on-disk structure
+ * it's used at the bottom of the tree
+ */
+struct ext3_extent {
+	__u32	ee_block;	/* first logical block extent covers */
+	__u16	ee_len;		/* number of blocks covered by extent */
+	__u16	ee_start_hi;	/* high 16 bits of physical block */
+	__u32	ee_start;	/* low 32 bigs of physical block */
+};
+
+/*
+ * this is index on-disk structure
+ * it's used at all the levels, but the bottom
+ */
+struct ext3_extent_idx {
+	__u32	ei_block;	/* index covers logical blocks from 'block' */
+	__u32	ei_leaf;	/* pointer to the physical block of the next *
+				 * level. leaf or next index could bet here */
+	__u16	ei_leaf_hi;	/* high 16 bits of physical block */
+	__u16	ei_unused;
+};
+
+/*
+ * each block (leaves and indexes), even inode-stored has header
+ */
+struct ext3_extent_header {
+	__u16	eh_magic;	/* probably will support different formats */
+	__u16	eh_entries;	/* number of valid entries */
+	__u16	eh_max;		/* capacity of store in entries */
+	__u16	eh_depth;	/* has tree real underlaying blocks? */
+	__u32	eh_generation;	/* generation of the tree */
+};
+
+#define EXT3_EXT_MAGIC		0xf30a
+
+/*
+ * array of ext3_ext_path contains path to some extent
+ * creation/lookup routines use it for traversal/splitting/etc
+ * truncate uses it to simulate recursive walking
+ */
+struct ext3_ext_path {
+	__u32				p_block;
+	__u16				p_depth;
+	struct ext3_extent		*p_ext;
+	struct ext3_extent_idx		*p_idx;
+	struct ext3_extent_header	*p_hdr;
+	struct buffer_head		*p_bh;
+};
+
+/*
+ * structure for external API
+ */
+
+#define EXT_CONTINUE	0
+#define EXT_BREAK	1
+#define EXT_REPEAT	2
+
+
+#define EXT_MAX_BLOCK	0xffffffff
+#define EXT_CACHE_MARK	0xffff
+
+
+#define EXT_FIRST_EXTENT(__hdr__) \
+	((struct ext3_extent *) (((char *) (__hdr__)) +		\
+				 sizeof(struct ext3_extent_header)))
+#define EXT_FIRST_INDEX(__hdr__) \
+	((struct ext3_extent_idx *) (((char *) (__hdr__)) +	\
+				     sizeof(struct ext3_extent_header)))
+#define EXT_HAS_FREE_INDEX(__path__) \
+	((__path__)->p_hdr->eh_entries < (__path__)->p_hdr->eh_max)
+#define EXT_LAST_EXTENT(__hdr__) \
+	(EXT_FIRST_EXTENT((__hdr__)) + (__hdr__)->eh_entries - 1)
+#define EXT_LAST_INDEX(__hdr__) \
+	(EXT_FIRST_INDEX((__hdr__)) + (__hdr__)->eh_entries - 1)
+#define EXT_MAX_EXTENT(__hdr__) \
+	(EXT_FIRST_EXTENT((__hdr__)) + (__hdr__)->eh_max - 1)
+#define EXT_MAX_INDEX(__hdr__) \
+	(EXT_FIRST_INDEX((__hdr__)) + (__hdr__)->eh_max - 1)
+
+#define EXT_ROOT_HDR(tree) \
+	((struct ext3_extent_header *) (tree)->root)
+#define EXT_BLOCK_HDR(bh) \
+	((struct ext3_extent_header *) (bh)->b_data)
+#define EXT_DEPTH(_t_)	\
+	(((struct ext3_extent_header *)((_t_)->root))->eh_depth)
+#define EXT_GENERATION(_t_)	\
+	(((struct ext3_extent_header *)((_t_)->root))->eh_generation)
+
+
+#define EXT_ASSERT(__x__) if (!(__x__)) BUG();
+
+
+/*
+ * this structure is used to gather extents from the tree via ioctl
+ */
+struct ext3_extent_buf {
+	unsigned long start;
+	int buflen;
+	void *buffer;
+	void *cur;
+	int err;
+};
+
+/*
+ * this structure is used to collect stats info about the tree
+ */
+struct ext3_extent_tree_stats {
+	int depth;
+	int extents_num;
+	int leaf_num;
+};
+
+#ifdef __KERNEL__
+/*
+ * ext3_extents_tree is used to pass initial information
+ * to top-level extents API
+ */
+struct ext3_extents_helpers;
+struct ext3_extents_tree {
+	struct inode *inode;	/* inode which tree belongs to */
+	void *root;		/* ptr to data top of tree resides at */
+	void *buffer;		/* will be passed as arg to ^^ routines	*/
+	int buffer_len;
+	void *private;
+	struct ext3_extent *cex;/* last found extent */
+	struct ext3_extents_helpers *ops;
+};
+
+struct ext3_extents_helpers {
+	int (*get_write_access)(handle_t *h, void *buffer);
+	int (*mark_buffer_dirty)(handle_t *h, void *buffer);
+	int (*mergable)(struct ext3_extent *ex1, struct ext3_extent *ex2);
+	int (*remove_extent_credits)(struct ext3_extents_tree *,
+					struct ext3_extent *, unsigned long,
+					unsigned long);
+	int (*remove_extent)(struct ext3_extents_tree *,
+				struct ext3_extent *, unsigned long,
+				unsigned long);
+	int (*new_block)(handle_t *, struct ext3_extents_tree *,
+				struct ext3_ext_path *, struct ext3_extent *,
+				int *);
+};
+
+/*
+ * to be called by ext3_ext_walk_space()
+ * negative retcode - error
+ * positive retcode - signal for ext3_ext_walk_space(), see below
+ * callback must return valid extent (passed or newly created)
+ */
+typedef int (*ext_prepare_callback)(struct ext3_extents_tree *,
+					struct ext3_ext_path *,
+					struct ext3_extent *, int);
+void ext3_init_tree_desc(struct ext3_extents_tree *, struct inode *);
+extern int ext3_extent_tree_init(handle_t *, struct ext3_extents_tree *);
+extern int ext3_ext_calc_credits_for_insert(struct ext3_extents_tree *, struct ext3_ext_path *);
+extern int ext3_ext_insert_extent(handle_t *, struct ext3_extents_tree *, struct ext3_ext_path *, struct ext3_extent *);
+extern int ext3_ext_walk_space(struct ext3_extents_tree *, unsigned long, unsigned long, ext_prepare_callback);
+extern int ext3_ext_remove_space(struct ext3_extents_tree *, unsigned long, unsigned long);
+extern struct ext3_ext_path * ext3_ext_find_extent(struct ext3_extents_tree *, int, struct ext3_ext_path *);
+
+static inline void
+ext3_ext_invalidate_cache(struct ext3_extents_tree *tree)
+{
+	if (tree->cex)
+		tree->cex->ee_len = 0;
+}
+#endif /* __KERNEL__ */
+
+
+#endif /* _LINUX_EXT3_EXTENTS */
+
Index: e2fsprogs-1.39/e2fsck/pass1.c
===================================================================
--- e2fsprogs-1.39.orig/e2fsck/pass1.c	2006-05-31 15:44:49.000000000 +0200
+++ e2fsprogs-1.39/e2fsck/pass1.c	2006-06-14 13:25:47.000000000 +0200
@@ -806,21 +806,30 @@ void e2fsck_pass1(e2fsck_t ctx)
 			ctx->fs_sockets_count++;
 		} else
 			mark_inode_bad(ctx, ino);
-		if (inode->i_block[EXT2_IND_BLOCK])
-			ctx->fs_ind_count++;
-		if (inode->i_block[EXT2_DIND_BLOCK])
-			ctx->fs_dind_count++;
-		if (inode->i_block[EXT2_TIND_BLOCK])
-			ctx->fs_tind_count++;
-		if (inode->i_block[EXT2_IND_BLOCK] ||
-		    inode->i_block[EXT2_DIND_BLOCK] ||
-		    inode->i_block[EXT2_TIND_BLOCK] ||
-		    inode->i_file_acl) {
+		if (fs->super->s_feature_ro_compat & EXT2_FEATURE_RO_COMPAT_64BIT) {
+		    if (inode->i_flags & EXT3_EXTENTS_FL) {
 			inodes_to_process[process_inode_count].ino = ino;
 			inodes_to_process[process_inode_count].inode = *inode;
 			process_inode_count++;
-		} else
-			check_blocks(ctx, &pctx, block_buf);
+		    } else
+			    mark_inode_bad(ctx, ino);
+		} else {
+			if (inode->i_block[EXT2_IND_BLOCK])
+				ctx->fs_ind_count++;
+			if (inode->i_block[EXT2_DIND_BLOCK])
+				ctx->fs_dind_count++;
+			if (inode->i_block[EXT2_TIND_BLOCK])
+				ctx->fs_tind_count++;
+			if (inode->i_block[EXT2_IND_BLOCK] ||
+			    inode->i_block[EXT2_DIND_BLOCK] ||
+			    inode->i_block[EXT2_TIND_BLOCK] ||
+			    inode->i_file_acl) {
+				inodes_to_process[process_inode_count].ino = ino;
+				inodes_to_process[process_inode_count].inode = *inode;
+				process_inode_count++;
+			} else
+				    check_blocks(ctx, &pctx, block_buf);
+		}
 
 		if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
 			return;