Re: [PATCH][FAT] FAT dirent scan with hin take #3

Pekka Enberg
2005-08-31T10:14:27Z

Hi,

On 8/31/05, Machida, Hiroyuki <machida@sm.sony.co.jp> wrote:
>
> Sorry, I send out wrong version. I attached the latest patch to 2.6.13.
>
> OGAWA Hirofumi wrote:
> > "Machida, Hiroyuki" <machida@sm.sony.co.jp> writes:
> >
> >
> >>Here is a revised version of dirent scan patch, mentioned at
> >>following E-mail.
> >>
> >>This patch addresses performance damages on "ls | xargs xxx" and
> >>reverse order scan which are reported to the previous patch.
> >>
> >>With this patch, fat_search_long() and fat_scan() use hint value
> >>as start of scan. For each directory holds multiple hint value entries.
> >>The entry would be selected by hash value based on scan target name and
> >>PID. Hint value would be calculated based on the entry previously found
> >>entry, so that the hint can cover backward neighborhood.
> >
> >
> > This patch couldn't compile. I assume you post a wrong patch...?
> >
> > The code is strange... Is the hint value related to the previously
> > accessed entry?
> >
> > This seems to be randomly cacheing the recent access position... Is
> > it your intention of this patch?
>
> Right, it looks like TLB, which holds cache "Physical addres"
> correponding to "Logical address". In this case, PID and file name
> to be looked up, perform role of "Logical address".
>
> I prepared vfat16 fs where over 4000 files in /foo
> and 200 files in root, then checked with following cases;
>
>
> without patch with patch
> ls-vfat 59.0 2.49
> xargs-vfat 61.3 11.9
> stat-vfat 41 17
> stat-vfat-reverse 56 32
>
> ls-msdos 14.2 0.62
> xargs-msdos 16.8 16.7
> stat-msdos 21 15
> stat-msdos-reverse 22 16
> - all valuses have sec unit
>
> 1-1 ls-vat)
> mount vfat to /a
> /usr/bin/time -p sh -c "/usr/bin/ls -Rl /a > /dev/null"
> umount /a
>
> 1-2 ls-msdos)
> mount msdos to /a
> /usr/bin/time -p sh -c "/usr/bin/ls -Rl /a > /dev/null"
> umount /a
>
> 2-1 xargs-vfat)
> mount vfat to /a
> cd /a/foo
> /usr/bin/time -p sh -c "(/usr/bin/ls | /usr/in/xargs stat) > /dev/null"
> umount /a
>
> 2-2 xargs-msdos)
> mount msdos to /a
> cd /a/foo
> /usr/bin/time -p sh -c "(/usr/bin/ls | /usr/in/xargs stat) > /dev/null"
> umount /a
>
> 3-1 stat-vfat)
> mount vfat to /a
> cd /a/foo
> repeat stat files which have located in the last 1024 dir entries
> with incremental order.
> umount /a
>
> 3-2 stat-vfat-reverse)
> do 3-1 with decremental order
>
> 3-3 stat-msdos)
> do 3-1 with msdos fs
>
> 3-4 stat-msdos-reverse)
> do 3-2 with msdos fs
>
>
> --
> Hiroyuki Machida
>
>
> This patch enables using hint information on scanning dir.
> It achieves excellent performance with "ls -l" for over 1000 entries.
>
> * fat-dirscan-with-hint_3.patch for linux 2.6.13
>
> fs/fat/dir.c | 130 ++++++++++++++++++++++++++++++++++++++++++++---
> fs/fat/inode.c | 13 ++++
> include/linux/msdos_fs.h | 2
> 3 files changed, 137 insertions(+), 8 deletions(-)
>
> Signed-off-by: Hiroyuki Machida <machida@sm.sony.co.jp> for CELF
>
> * modified files
>
>
> --- linux-2.6.13/fs/fat/dir.c 2005-08-29 08:41:01.000000000 +0900
> +++ linux-2.6.13-work/fs/fat/dir.c 2005-08-31 13:48:01.001119437 +0900
> @@ -201,6 +201,88 @@ fat_shortname2uni(struct nls_table *nls,
> * Return values: negative -> error, 0 -> not found, positive -> found,
> * value is the total amount of slots, including the shortname entry.
> */
> +
> +#define FAT_SCAN_SHIFT 4 /* 2x8 way scan hints */
> +#define FAT_SCAN_NWAY (1<<FAT_SCAN_SHIFT)
> +
> +inline
> +static int hint_allocate(struct inode *dir)
> +{
> + loff_t *hints;
> + int err = 0;
> +
> + if (!MSDOS_I(dir)->scan_hints) {

Please consider moving this check to callers. Conditional allocation
makes this bit strange API-wise. Or alternatively, give
hint_allocate() a better name.

> --- linux-2.6.13/fs/fat/inode.c 2005-08-29 08:41:01.000000000 +0900
> +++ linux-2.6.13-work/fs/fat/inode.c 2005-08-31 12:59:54.292274060 +0900
> @@ -242,6 +242,8 @@ static int fat_fill_inode(struct inode *
> inode->i_version++;
> inode->i_generation = get_seconds();
>
> + init_MUTEX(&MSDOS_I(inode)->scan_lock);
> + MSDOS_I(inode)->scan_hints = 0;

Please use NULL.

> if ((de->attr & ATTR_DIR) && !IS_FREE(de->name)) {
> inode->i_generation &= ~1;
> inode->i_mode = MSDOS_MKMODE(de->attr,
> @@ -345,6 +347,15 @@ static void fat_delete_inode(struct inod
> static void fat_clear_inode(struct inode *inode)
> {
> struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
> + loff_t *hints;
> +
> + down(&MSDOS_I(inode)->scan_lock);
> + hints = (MSDOS_I(inode)->scan_hints);

Pleas drop redundant parenthesis.

> + if (hints) {
> + MSDOS_I(inode)->scan_hints = NULL;
> + }
> + up(&MSDOS_I(inode)->scan_lock);
> + kfree(hints);

Why can't you do kfree() under scan_lock?

> @@ -1011,6 +1022,8 @@ static int fat_read_root(struct inode *i
> struct msdos_sb_info *sbi = MSDOS_SB(sb);
> int error;
>
> + init_MUTEX(&MSDOS_I(inode)->scan_lock);
> + MSDOS_I(inode)->scan_hints = 0;

Please use NULL here.

Pekka