[RFC] FAT dirent scan with hint

Machida, Hiroyuki
2005-08-16T20:14:23Z

[-- Attachment #1: Type: text/plain, Size: 652 bytes --]

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@sm.sony.co.jp
SSW Dept. HENC, Sony Corp.

[-- Attachment #2: fat-dirscan-with-hint.patch --]
[-- Type: text/plain, Size: 3717 bytes --]

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@sm.sony.co.jp> 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 */