[RFC] FAT dirent scan with hint

[Machida, Hiroyuki]

We realized that "ls -l" has taken so long time, over 1000 entries on
directory in FAT/VFAT. Attached patch tries to solve the issue.

This uses a simple solution which records position of the last found
entry and uses it as start position of next scan. It would work well
under following assumption;
- in most case dirent will be examined by stat() or it's variants with
  from top to bottom direction.
- found entries would be cached with VFS level dentry cache.

What do you think about this patch and above assumption?
Do you have any other good solution about this issue?

-- 
Hiroyuki Machida		machida@xxxxxxxxxxxxx		
SSW Dept. HENC, Sony Corp.
This patch enables using hint nformation on scanning dir.
It reaches excelent performance with "ls -l" for over 1000 entries.
I'm not the original author. I just ported it to 2.6.12 and clean it up.


* fat-dirscan-with-hint.patch

 fs/fat/dir.c             |   49 +++++++++++++++++++++++++++++++++--------------
 fs/fat/inode.c           |    2 +
 include/linux/msdos_fs.h |    1 
 3 files changed, 38 insertions(+), 14 deletions(-)

Signed-off-by: Hiroyuki Machida <machida@xxxxxxxxxxxxx> for CELF

* modified files

--- orig/fs/fat/dir.c
+++ mod/fs/fat/dir.c
@@ -218,13 +218,20 @@
 	int utf8 = sbi->options.utf8;
 	int anycase = (sbi->options.name_check != 's');
 	unsigned short opt_shortname = sbi->options.shortname;
-	loff_t cpos = 0;
 	int chl, i, j, last_u, err;
+	loff_t cpos;
+	loff_t start = cpos = MSDOS_I(inode)->i_dirscan_hint;
+	int reach_bottom = 0;
 
 	err = -ENOENT;
 	while(1) {
-		if (fat_get_entry(inode, &cpos, &bh, &de) == -1)
-			goto EODir;
+Top:
+		if (reach_bottom && cpos >= start) goto EODir;
+		if (fat_get_entry(inode, &cpos, &bh, &de) == -1) {
+			if (!start) goto EODir;
+			reach_bottom ++; cpos = 0;
+			continue;
+		}
 parse_record:
 		nr_slots = 0;
 		if (de->name[0] == DELETED_FLAG)
@@ -274,8 +281,11 @@
 				if (ds->id & 0x40) {
 					unicode[offset + 13] = 0;
 				}
-				if (fat_get_entry(inode, &cpos, &bh, &de) < 0)
-					goto EODir;
+				if (fat_get_entry(inode, &cpos, &bh, &de) <0 ) {
+					if (!start) goto EODir;
+					reach_bottom ++; cpos = 0;
+					goto Top;
+				}
 				if (slot == 0)
 					break;
 				ds = (struct msdos_dir_slot *) de;
@@ -363,6 +373,7 @@
 	sinfo->de = de;
 	sinfo->bh = bh;
 	sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, sinfo->de);
+	MSDOS_I(inode)->i_dirscan_hint = sinfo->slot_off;
 	err = 0;
 EODir:
 	if (unicode)
@@ -838,16 +849,26 @@
 	     struct fat_slot_info *sinfo)
 {
 	struct super_block *sb = dir->i_sb;
+	loff_t start = sinfo->slot_off = MSDOS_I(dir)->i_dirscan_hint;
+	int reach_bottom = 0;
 
-	sinfo->slot_off = 0;
-	sinfo->bh = NULL;
-	while (fat_get_short_entry(dir, &sinfo->slot_off, &sinfo->bh,
-				   &sinfo->de) >= 0) {
-		if (!strncmp(sinfo->de->name, name, MSDOS_NAME)) {
-			sinfo->slot_off -= sizeof(*sinfo->de);
-			sinfo->nr_slots = 1;
-			sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, sinfo->de);
-			return 0;
+	sinfo->bh=NULL;
+	while (1) {
+		if (fat_get_short_entry(dir, &sinfo->slot_off, &sinfo->bh,
+					&sinfo->de) >= 0) {
+			if (!strncmp(sinfo->de->name, name, MSDOS_NAME)) {
+				sinfo->slot_off -= sizeof(*sinfo->de);
+				sinfo->nr_slots = 1;
+				sinfo->i_pos = fat_make_i_pos(sb, sinfo->bh, 
+							      sinfo->de);
+				MSDOS_I(dir)->i_dirscan_hint = sinfo->slot_off;
+				return 0;
+			}
+			if (reach_bottom && (start <= sinfo->slot_off)) break;
+		} else {
+			if (!start) break;
+			sinfo->slot_off = 0;
+			reach_bottom++;
 		}
 	}
 	return -ENOENT;


--- orig/fs/fat/inode.c
+++ mod/fs/fat/inode.c
@@ -236,6 +236,7 @@
 	struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
 	int error;
 
+	MSDOS_I(inode)->i_dirscan_hint = 0;
 	MSDOS_I(inode)->i_pos = 0;
 	inode->i_uid = sbi->options.fs_uid;
 	inode->i_gid = sbi->options.fs_gid;
@@ -1034,6 +1035,7 @@
 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
 	int error;
 
+	MSDOS_I(inode)->i_dirscan_hint = 0;
 	MSDOS_I(inode)->i_pos = 0;
 	inode->i_uid = sbi->options.fs_uid;
 	inode->i_gid = sbi->options.fs_gid;


--- orig/include/linux/msdos_fs.h
+++ mod/include/linux/msdos_fs.h
@@ -257,6 +257,7 @@
 	unsigned int cache_valid_id;
 
 	loff_t mmu_private;
+	loff_t i_dirscan_hint;	/* last scaned and found pos */
 	int i_start;		/* first cluster or 0 */
 	int i_logstart;		/* logical first cluster */
 	int i_attrs;		/* unused attribute bits */