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

[Pekka Enberg <penberg@cs.helsinki.fi>]

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