FAT dirent scan with hint
RFC 1/1 FAT dirent scan with hint
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?
Signature · 2 lines
Hiroyuki Machida [email protected] 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(-)
* modified files
fs/fat/dir.c +35 -14
@@ -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 ;
fs/fat/inode.c +2 -0
@@ -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;
include/linux/msdos_fs.h +1 -0
@@ -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 */