PATCH: Update U-Boot EXT2 Filesystem to support dynamic inode size and optimize ext2 read function to fasten read speed!

Description:
The patch updates /fs/ext2/ext2fs.c file. There are two aims:
1. Make U-Boot could support the EXT2 dynamic version that ext2_inode_size beyond 128bytes. One new feature be involved: CFG_EXT2_SUPPORT_DYNAMIC_REV
Refer to: linux-2.6.24.3 source code.
2. Make EXT2 read more fast.
One new feature be involved: CFG_OPTIMIZE_EXT2_READ

commit f4120b0f4f06cd1a382bb562d7fe33ea554a1982

Parent: 699f05125509249072a0b865c8d35520d97cd501 
Author: Ryan Chen <[email protected]>
Date:   Tue Jul 29 11:57:11 2008 -0400

modified: fs/ext2/ext2fs.c

old mode 100644
new mode 100755
index 7833551..3946978
@@ -29,6 +29,7 @@
 #include <ext2fs.h>
 #include <malloc.h>
 #include <asm/byteorder.h>
+#define CFG_EXT2_SUPPORT_DYNAMIC_REV
 
 extern int ext2fs_devread (int sector, int byte_offset, int byte_len,
 			   char *buf);

@@ -66,6 +67,17 @@ extern int ext2fs_devread (int sector, int byte_offset, int byte_len,
 /* The size of an ext2 block in bytes.  */
 #define EXT2_BLOCK_SIZE(data)	   (1 << LOG2_BLOCK_SIZE(data))
 
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+/*
+ * Revision levels
+ */
+#define EXT2_GOOD_OLD_REV       0       /* The good old (original) format */
+#define EXT2_DYNAMIC_REV        1       /* V2 format w/ dynamic inode sizes */
+
+#define EXT2_GOOD_OLD_INODE_SIZE 128
+uint32_t ext2_inode_size = EXT2_GOOD_OLD_INODE_SIZE;
+#endif
+
 /* The ext2 superblock.  */
 struct ext2_sblock {
 	uint32_t total_inodes;

@@ -217,7 +229,11 @@ static int ext2fs_read_inode
 	if (status == 0) {
 		return (0);
 	}
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+	inodes_per_block = EXT2_BLOCK_SIZE (data) / ext2_inode_size;
+#else
 	inodes_per_block = EXT2_BLOCK_SIZE (data) / 128;
+#endif
 	blkno = (ino % __le32_to_cpu (sblock->inodes_per_group)) /
 		inodes_per_block;
 	blkoff = (ino % __le32_to_cpu (sblock->inodes_per_group)) %

@@ -226,10 +242,17 @@ static int ext2fs_read_inode
 	printf ("ext2fs read inode blkno %d blkoff %d\n", blkno, blkoff);
 #endif
 	/* Read the inode.  */
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+	status = ext2fs_devread (((__le32_to_cpu (blkgrp.inode_table_id) +
+				   blkno) << LOG2_EXT2_BLOCK_SIZE (data)),
+				 ext2_inode_size * blkoff,
+				 sizeof (struct ext2_inode), (char *) inode);
+#else
 	status = ext2fs_devread (((__le32_to_cpu (blkgrp.inode_table_id) +
 				   blkno) << LOG2_EXT2_BLOCK_SIZE (data)),
 				 sizeof (struct ext2_inode) * blkoff,
 				 sizeof (struct ext2_inode), (char *) inode);
+#endif
 	if (status == 0) {
 		return (0);
 	}

@@ -243,8 +266,13 @@ void ext2fs_free_node (ext2fs_node_t node, ext2fs_node_t currroot) {
 	}
 }
 
+#define CFG_OPTIMIZE_EXT2_READ
 
+#ifdef CFG_OPTIMIZE_EXT2_READ
+static int ext2fs_read_block (ext2fs_node_t node, int fileblock, int *stream) {
+#else
 static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
+#endif
 	struct ext2_data *data = node->data;
 	struct ext2_inode *inode = &node->inode;
 	int blknr;

@@ -252,9 +280,20 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
 	int log2_blksz = LOG2_EXT2_BLOCK_SIZE (data);
 	int status;
 
+#ifdef CFG_OPTIMIZE_EXT2_READ
+	*stream = 1;/* itself */
+#endif
+
 	/* Direct blocks.  */
 	if (fileblock < INDIRECT_BLOCKS) {
 		blknr = __le32_to_cpu (inode->b.blocks.dir_blocks[fileblock]);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+		while(((inode->b.blocks.dir_blocks[fileblock + 1] - 
+			inode->b.blocks.dir_blocks[fileblock]) == 1) && (fileblock < INDIRECT_BLOCKS - 1)) {
+			fileblock++;
+			*stream += 1;
+		}
+#endif
 	}
 	/* Indirect.  */
 	else if (fileblock < (INDIRECT_BLOCKS + (blksz / 4))) {

@@ -294,6 +333,13 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
 		}
 		blknr = __le32_to_cpu (indir1_block
 				       [fileblock - INDIRECT_BLOCKS]);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+		while(((__le32_to_cpu (indir1_block[fileblock - INDIRECT_BLOCKS + 1]) - \
+			__le32_to_cpu (indir1_block[fileblock - INDIRECT_BLOCKS])) == 1) && (fileblock < (blksz - 1))) {
+			fileblock++;
+			*stream += 1;
+		}
+#endif
 	}
 	/* Double indirect.  */
 	else if (fileblock <

@@ -301,6 +347,9 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
 		unsigned int perblock = blksz / 4;
 		unsigned int rblock = fileblock - (INDIRECT_BLOCKS
 						   + blksz / 4);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+		int rbcnt = 0;
+#endif
 
 		if (indir1_block == NULL) {
 			indir1_block = (uint32_t *) malloc (blksz);

@@ -370,6 +419,14 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
 				__le32_to_cpu (indir1_block[rblock / perblock]) << log2_blksz;
 		}
 		blknr = __le32_to_cpu (indir2_block[rblock % perblock]);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+		rbcnt = rblock % perblock;
+		while(((__le32_to_cpu (indir2_block[rbcnt + 1]) - \
+			__le32_to_cpu (indir2_block[rbcnt])) == 1) && (rbcnt < (blksz - 1))) {
+			rbcnt++;
+			*stream += 1;
+		}
+#endif
 	}
 	/* Tripple indirect.  */
 	else {

@@ -382,7 +439,57 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
 	return (blknr);
 }
 
+#ifdef CFG_OPTIMIZE_EXT2_READ
+int ext2fs_read_file
+	(ext2fs_node_t node, int pos, unsigned int len, char *buf) {
+	int log2blocksize = LOG2_EXT2_BLOCK_SIZE (node->data);
+	int blocksize = 1 << (log2blocksize + DISK_SECTOR_BITS);
+	unsigned int filesize = __le32_to_cpu(node->inode.size);
+	int blknr;
+	int blockend;
+	int status;
+	int remain = len;
+	char *buffer = buf;
+	int stream = 0;
+	int cur = pos / blocksize;
+	int blockoff = pos % blocksize;
+
+	/* Adjust len so it we can't read past the end of the file.  */
+	if (len > filesize) {
+		len = filesize;
+	}
 
+	while (remain > 0) {
+		blknr = ext2fs_read_block (node, cur, &stream);
+		if (blknr < 0) {
+			return (-1);
+		}
+		blknr = blknr << log2blocksize;	
+	
+		if(remain < blocksize * stream) {
+			blockend = remain;
+		} else {
+			blockend = blocksize * stream;
+		}
+		
+		status = ext2fs_devread (blknr, blockoff, blockend, buffer);
+		if (status == 0) {
+			return (-1);
+		}
+	
+		remain -= blockend;
+		buffer += blockend;
+		cur += stream;
+		blockoff = 0;
+	
+		if(remain == 0)
+			return (len);
+		else if(remain < 0)
+			return (-1);
+	}
+	return (len);
+}
+#else
 int ext2fs_read_file
 	(ext2fs_node_t node, int pos, unsigned int len, char *buf) {
 	int i;

@@ -390,7 +497,7 @@ int ext2fs_read_file
 	int log2blocksize = LOG2_EXT2_BLOCK_SIZE (node->data);
 	int blocksize = 1 << (log2blocksize + DISK_SECTOR_BITS);
 	unsigned int filesize = __le32_to_cpu(node->inode.size);
-
+	
 	/* Adjust len so it we can't read past the end of the file.  */
 	if (len > filesize) {
 		len = filesize;

@@ -409,7 +516,7 @@ int ext2fs_read_file
 			return (-1);
 		}
 		blknr = blknr << log2blocksize;
-
+		
 		/* Last block.  */
 		if (i == blockcnt - 1) {
 			blockend = (len + pos) % blocksize;

@@ -442,6 +549,7 @@ int ext2fs_read_file
 	}
 	return (len);
 }
+#endif
 
 
 static int ext2fs_iterate_dir (ext2fs_node_t dir, char *name, ext2fs_node_t * fnode, int *ftype)

@@ -854,6 +962,17 @@ int ext2fs_mount (unsigned part_length) {
 	if (__le16_to_cpu (data->sblock.magic) != EXT2_MAGIC) {
 		goto fail;
 	}
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+#ifdef DEBUG
+	printf("revision_level = 0x%x, inode_size = 0x%x\n", data->sblock.revision_level, data->sblock.inode_size);
+#endif
+	if (__le32_to_cpu (data->sblock.revision_level) == EXT2_GOOD_OLD_REV) {
+		ext2_inode_size = EXT2_GOOD_OLD_INODE_SIZE;
+	} else {
+		ext2_inode_size = __le16_to_cpu (data->sblock.inode_size);
+	}
+#endif
+	
 	data->diropen.data = data;
 	data->diropen.ino = 2;
 	data->diropen.inode_read = 1;

Best Regards,
Ryan Chen

Does it significantly increase code size, or is there any other reason why these need to be conditionalized?

-Scott

Hi Scott,
For sure, the modification will increase code size, but I think it is reasonable.
1. Make U-Boot could support the EXT2 dynamic version that ext2_inode_size beyond 128bytes.
According to Linux kernel source code, now EXT2 filesystem could support two revision:
EXT2_GOOD_OLD_REV
EXT2_DYNAMIC_REV
ext2_inode_size be fixed as 128bytes in the first revision while it could beyond 128bytes in another revision. In the past, the first revision is the default option for mkfs.ext2 command. But now there are some OSes like Mandriva Linux 2008.1 for STLS want to use new revision option to format disk. I have tested it and our current U-Boot couldn't support it. So I think it is time to do it.

2. Make EXT2 read more fast.
I have tested our U-Boot to access EXT2 filesystem on USB disk. It's quite slow and it takes about 200 seconds to read a file that its size is 8MB. Our USB host controller is NEC upd720101 OHCI host controller and operation mode is 'bulk'. I think its width is enough. I have analyzed our ext2fs.c file and found it only read 4KB(512B/block * 8blocks, I format EXT2 filesystem with default options) once time. One time is a USB timing slot - 100ms. So it is so slow.
Now I mainly modified ext2fs_read_block() function to detect how many seriate blocks and read them in one time. The modification fasten read opertion a lot especially big file.

Best Regards,
Ryan Chen
-----Original Message-----
From: Scott Wood [mailto:scottwood at freescale.com]
Sent: Wednesday, July 30, 2008 4:11 AM
To: Ryan CHEN
Cc: u-boot-users at lists.sourceforge.net; Antonio Maria BORNEO
Subject: Re: [U-Boot-Users] PATCH: Update U-Boot EXT2 Filesystem to support dynamic inode size and optimize ext2 read function to fasten read speed!

beyond 128bytes.

Does it significantly increase code size, or is there any other reason why these need to be conditionalized?

-Scott

Do we really need new config options and #ifdeffery for these?

...

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
Certainly there are things in life that money  can't  buy,  but  it's
very funny - Did you ever try buying them without money? - Ogden Nash

Hi Wolfgang,
I have modified my patch according to your suggestion. The only question is that use debug() because I found all debug print msg lines are written as :
#ifdef DEBUG
printf(......);
#endif
Are you sure I need change my debug print to debug()?

commit 4e638f2b97cea8b256eca7eb098d4da45015e10d

Parent: 699f05125509249072a0b865c8d35520d97cd501 
Author: Ryan Chen <[email protected]>
Date:   Wed Jul 30 05:48:16 2008 -0400

modified: fs/ext2/ext2fs.c

old mode 100644
new mode 100755
index 7833551..4b01463
@@ -29,6 +29,7 @@
 #include <ext2fs.h>
 #include <malloc.h>
 #include <asm/byteorder.h>
+#define CFG_EXT2_SUPPORT_DYNAMIC_REV
 
 extern int ext2fs_devread (int sector, int byte_offset, int byte_len,
 			   char *buf);

@@ -66,6 +67,17 @@ extern int ext2fs_devread (int sector, int byte_offset,

int byte_len,
/* The size of an ext2 block in bytes. */
#define EXT2_BLOCK_SIZE(data) (1 << LOG2_BLOCK_SIZE(data))

+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+/*
+ * Revision levels
+ */
+#define EXT2_GOOD_OLD_REV 0 /* The good old (original) format
*/
+#define EXT2_DYNAMIC_REV 1 /* V2 format w/ dynamic inode sizes
*/
+
+#define EXT2_GOOD_OLD_INODE_SIZE 128
+uint32_t ext2_inode_size = EXT2_GOOD_OLD_INODE_SIZE;
+#endif
+
/* The ext2 superblock. */
struct ext2_sblock {
uint32_t total_inodes;
@@ -217,7 +229,11 @@ static int ext2fs_read_inode
if (status == 0) {
return (0);
}
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+ inodes_per_block = EXT2_BLOCK_SIZE (data) / ext2_inode_size;
+#else
inodes_per_block = EXT2_BLOCK_SIZE (data) / 128;
+#endif
blkno = (ino % __le32_to_cpu (sblock->inodes_per_group)) /
inodes_per_block;
blkoff = (ino % __le32_to_cpu (sblock->inodes_per_group)) %
@@ -226,10 +242,17 @@ static int ext2fs_read_inode
printf ("ext2fs read inode blkno %d blkoff %d\n", blkno, blkoff);
#endif
/* Read the inode. */
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+ status = ext2fs_devread (((__le32_to_cpu (blkgrp.inode_table_id) +
+ blkno) << LOG2_EXT2_BLOCK_SIZE (data)),
+ ext2_inode_size * blkoff,
+ sizeof (struct ext2_inode), (char *)
inode);
+#else
status = ext2fs_devread (((__le32_to_cpu (blkgrp.inode_table_id) +
blkno) << LOG2_EXT2_BLOCK_SIZE (data)),
sizeof (struct ext2_inode) * blkoff, sizeof (struct ext2_inode), (char *)
inode);
+#endif
if (status == 0) {
return (0);
}
@@ -243,8 +266,13 @@ void ext2fs_free_node (ext2fs_node_t node, ext2fs_node_t currroot) {
}
}

+#define CFG_OPTIMIZE_EXT2_READ

+#ifdef CFG_OPTIMIZE_EXT2_READ
+static int ext2fs_read_block (ext2fs_node_t node, int fileblock, int *stream) {
+#else
static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
+#endif
struct ext2_data *data = node->data;
struct ext2_inode *inode = &node->inode;
int blknr;
@@ -252,9 +280,21 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
int log2_blksz = LOG2_EXT2_BLOCK_SIZE (data);
int status;

+#ifdef CFG_OPTIMIZE_EXT2_READ
+ *stream = 1;/* itself */
+#endif
+
/* Direct blocks. */
if (fileblock < INDIRECT_BLOCKS) {
blknr = __le32_to_cpu
(inode->b.blocks.dir_blocks[fileblock]);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+ while(((inode->b.blocks.dir_blocks[fileblock + 1] -
+ inode->b.blocks.dir_blocks[fileblock]) == 1) && \
+ (fileblock < INDIRECT_BLOCKS - 1)) {
+ fileblock++;
+ *stream += 1;
+ }
+#endif
}
/* Indirect. */
else if (fileblock < (INDIRECT_BLOCKS + (blksz / 4))) {
@@ -294,6 +334,14 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
}
blknr = __le32_to_cpu (indir1_block
[fileblock - INDIRECT_BLOCKS]);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+ while(((__le32_to_cpu (indir1_block[fileblock -
INDIRECT_BLOCKS + 1]) - \
+ __le32_to_cpu (indir1_block[fileblock -
INDIRECT_BLOCKS])) == 1) && \
+ (fileblock < (blksz - 1))) {
+ fileblock++;
+ *stream += 1;
+ }
+#endif
}
/* Double indirect. */
else if (fileblock <
@@ -301,6 +349,9 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
unsigned int perblock = blksz / 4;
unsigned int rblock = fileblock - (INDIRECT_BLOCKS
+ blksz / 4);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+ int rbcnt = 0;
+#endif

if (indir1_block == NULL) {
indir1_block = (uint32_t *) malloc (blksz);
@@ -370,6 +421,15 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
__le32_to_cpu (indir1_block[rblock /
perblock]) << log2_blksz;
}
blknr = __le32_to_cpu (indir2_block[rblock % perblock]);
+#ifdef CFG_OPTIMIZE_EXT2_READ
+ rbcnt = rblock % perblock;
+ while(((__le32_to_cpu (indir2_block[rbcnt + 1]) - \
+ __le32_to_cpu (indir2_block[rbcnt])) == 1) \
+ && (rbcnt < (blksz - 1))) {
+ rbcnt++;
+ *stream += 1;
+ }
+#endif
}
/* Tripple indirect. */
else {
@@ -382,7 +442,57 @@ static int ext2fs_read_block (ext2fs_node_t node, int fileblock) {
return (blknr);
}

+#ifdef CFG_OPTIMIZE_EXT2_READ
+int ext2fs_read_file
+ (ext2fs_node_t node, int pos, unsigned int len, char *buf) {
+ int log2blocksize = LOG2_EXT2_BLOCK_SIZE (node->data);
+ int blocksize = 1 << (log2blocksize + DISK_SECTOR_BITS);
+ unsigned int filesize = __le32_to_cpu(node->inode.size);
+ int blknr;
+ int blockend;
+ int status;
+ int remain = len;
+ char *buffer = buf;
+ int stream = 0;
+ int cur = pos / blocksize;
+ int blockoff = pos % blocksize;
+
+ /* Adjust len so it we can't read past the end of the file. */
+ if (len > filesize) {
+ len = filesize;
+ }

+ while (remain > 0) {
+ blknr = ext2fs_read_block (node, cur, &stream);
+ if (blknr < 0) {
+ return (-1);
+ }
+ blknr = blknr << log2blocksize;
+
+ if(remain < blocksize * stream) {
+ blockend = remain;
+ } else {
+ blockend = blocksize * stream;
+ }
+
+ status = ext2fs_devread (blknr, blockoff, blockend, buffer);
+ if (status == 0) {
+ return (-1);
+ }
+
+ remain -= blockend;
+ buffer += blockend;
+ cur += stream;
+ blockoff = 0;
+
+ if(remain == 0)
+ return (len);
+ else if(remain < 0)
+ return (-1);
+ }
+ return (len);
+}
+#else
int ext2fs_read_file
(ext2fs_node_t node, int pos, unsigned int len, char *buf) { int i;
@@ -442,6 +552,7 @@ int ext2fs_read_file
}
return (len);
}
+#endif

static int ext2fs_iterate_dir (ext2fs_node_t dir, char *name, ext2fs_node_t
* fnode, int *ftype)
@@ -854,6 +965,18 @@ int ext2fs_mount (unsigned part_length) {
if (__le16_to_cpu (data->sblock.magic) != EXT2_MAGIC) {
goto fail;
}
+#ifdef CFG_EXT2_SUPPORT_DYNAMIC_REV
+#ifdef DEBUG
+ printf("revision_level = 0x%x, inode_size = 0x%x\n",
data->sblock.revision_level, \
+ data->sblock.inode_size);
+#endif
+ if (__le32_to_cpu (data->sblock.revision_level) ==
EXT2_GOOD_OLD_REV) {
+ ext2_inode_size = EXT2_GOOD_OLD_INODE_SIZE;
+ } else {
+ ext2_inode_size = __le16_to_cpu (data->sblock.inode_size);
+ }
+#endif
+
data->diropen.data = data;
data->diropen.ino = 2;
data->diropen.inode_read = 1;

Best Regards,
Ryan Chen

Best Regards,
Ryan Chen
-----Original Message-----
From: [email protected] [mailto:wd at denx.de]
Sent: Wednesday, July 30, 2008 7:17 AM
To: Ryan CHEN
Cc: u-boot-users at lists.sourceforge.net; Antonio Maria BORNEO
Subject: Re: [U-Boot-Users] PATCH: Update U-Boot EXT2 Filesystem to support dynamic inode size and optimize ext2 read function to fasten read speed!

beyond 128bytes.

Do we really need new config options and #ifdeffery for these?

...

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
Certainly there are things in life that money  can't  buy,  but  it's very
funny - Did you ever try buying them without money? - Ogden Nash

Hi Ryan,

Yes, please. We introduced the macro especially for this to make the code more readable.

If you find other instances of the macro not being used, feel free to send a patch changing it ;)

Cheers
Detlev

Multiple exclamation marks, the sure sign of an insane mind.
                        -- Terry Pratchett
--
DENX Software Engineering GmbH,      MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich,  Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-40 Fax: (+49)-8142-66989-80 Email: dzu at denx.de

Dear Ryan CHEN,

Since all the other code is like that I agree to leave it unchanged.

But:

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
In a survey taken several years ago, all  incoming  freshmen  at  MIT
were  asked  if  they  expected  to graduate in the top half of their
class. Ninety-seven percent responded that they did.