Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   "Sungjong Seo" <sj1557.seo@samsung.com>
To:     "'Namjae Jeon'" <linkinjeon@kernel.org>
Cc:     "'linux-fsdevel'" <linux-fsdevel@vger.kernel.org>,
        "'linux-kernel'" <linux-kernel@vger.kernel.org>,
        <sj1557.seo@samsung.com>
In-Reply-To: <PUZPR04MB63168196EA8FB4352871DD4881369@PUZPR04MB6316.apcprd04.prod.outlook.com>
Subject: RE: [PATCH v1 2/2] exfat: hint the empty entry which at the end of
 cluster chain
Date:   Tue, 1 Nov 2022 16:40:31 +0900
Message-ID: <34e401d8edc5$38109260$a831b720$@samsung.com>
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Thread-Index: AQJbGVKlRTjGnAJr8oRiJ7knPGKj+wGohbknAXbHQ6wAlk5SbgIIQmXgAoTn59Ss4y/W8A==
Content-Language: ko
Content-Type: text/plain; charset="utf-8"
CMS-TYPE: 101P
DLP-Filter: Pass
References: <CGME20221019072854epcas1p2a2b272458803045b4dfa95b17fb4f547@epcas1p2.samsung.com>
        <PUZPR04MB631604A0BBD29713D3F8DAB0812B9@PUZPR04MB6316.apcprd04.prod.outlook.com>
        <014c01d8ecf0$6e74bc80$4b5e3580$@samsung.com>
        <CAKYAXd9omiOTAaAWSnzE5jCQFDL8Nkok_wm_OAYwxVpgcCxykg@mail.gmail.com>
        <PUZPR04MB6316E0E22B1CAAAB25E02C3581379@PUZPR04MB6316.apcprd04.prod.outlook.com>
        <PUZPR04MB63168196EA8FB4352871DD4881369@PUZPR04MB6316.apcprd04.prod.outlook.com>
Precedence: bulk

Hi, Yuezhang,

> At this stage, we can check this case in exfat_search_empty_slot() by
> removing the following if statement.
>=20
> -               if (num_entries <=3D hint_femp->count) =7B
> -                       hint_femp->eidx =3D EXFAT_HINT_NONE;
> -                       return dentry;
> -               =7D
>=20
> What do you think?

Are you planning to remove the code below as well?
+              /* All entries searched but not enough empty entries */
+               if (dentry + hint_femp->count =3D=3D p_dir->size * dentries=
_per_clu)
+                       return -ENOSPC;

Otherwise, with appropriate comments, it could be modified to:

+                /*
+                 * If hint_femp->count is enough, it is needed to check if
+                 * there are actual empty entries.
+                 * Otherwise, and if =22dentry + hint_famp->count=22 is al=
so equal
+                 * to =22p_dir->size * dentries_per_clu=22, it means ENOSP=
C.
+                 */
+                if ((num_entries > hint_femp->count) &&
+                     (dentry + hint_femp->count =3D=3D
+                      p_dir->size * dentries_per_clu))
+                        return -ENOSPC;

As of now, it seems like the simplest and the best way.

>=20
> > -----Original Message-----
> > From: Mo, Yuezhang
> > Sent: Monday, October 31, 2022 7:05 PM
> > To: Namjae Jeon <linkinjeon=40kernel.org>; Sungjong Seo
> > <sj1557.seo=40samsung.com>
> > Cc: linux-fsdevel <linux-fsdevel=40vger.kernel.org>; linux-kernel
> > <linux-kernel=40vger.kernel.org>
> > Subject: RE: =5BPATCH v1 2/2=5D exfat: hint the empty entry which at th=
e
> > end of cluster chain
> >
> > > > This seems like a very good approach. Perhaps the key fix that
> > > > improved performance seems to be the handling of cases where empty
> > > > space was not found and ended with TYPE_UNUSED.
> > > >
> > > > However, there are concerns about trusting and using the number of
> > > > free entries after TYPE_UNUSED calculated based on directory size.
> > > > This is because, unlike exFAT Spec., in the real world, unexpected
> > > > TYPE_UNUSED entries may exist. :( That's why
> > > > exfat_search_empty_slot() checks if there is any valid entry after
> > > > TYPE_UNUSED. In my experience, they can be caused by a wrong FS
> > > > driver and H/W defects, and the probability of occurrence is not lo=
w.
> > > >
> > > > Therefore, when the lookup ends with TYPE_UNUSED, if there are no
> > > > empty entries found yet, it would be better to set the last empty
> > > > entry to hint_femp.eidx and set hint_femp.count to 0.
> > > > If so, even if the lookup ends with TYPE_UNUSED,
> > > > exfat_search_empty_slot() can start searching from the position of
> > > > the last empty entry and check whether there are actually empty
> > > > entries as many as the required num_entries as now.
> > > >
> > > > what do you think?
> >
> > We plan to add a new helper exfat_get_empty_dentry_set(), this helper
> > is called before setting the entry type, it caches and then checks for
> > empty entries(Check-on-write is safer than checking when looking for
> > empty directory entries).
> >
> >        for (i =3D 0; i < es->num_entries; i++) =7B
> >                ep =3D exfat_get_dentry_cached(es, i);
> >                type =3D exfat_get_entry_type(ep);
> >                if (type =3D=3D TYPE_UNUSED)
> >                        unused_hit =3D true;
> >                else if (type =3D=3D TYPE_DELETED) =7B
> >                        if (unused_hit)
> >                                goto error;
> >                =7D else
> >                        goto error;
> >        =7D
> >
> > This code is not ready, we are testing and internal reviewing.
> >
> > > -----Original Message-----
> > > From: Namjae Jeon <linkinjeon=40kernel.org>
> > > Sent: Monday, October 31, 2022 2:32 PM
> > > To: Sungjong Seo <sj1557.seo=40samsung.com>; Mo, Yuezhang
> > > <Yuezhang.Mo=40sony.com>
> > > Cc: linux-fsdevel <linux-fsdevel=40vger.kernel.org>; linux-kernel
> > > <linux-kernel=40vger.kernel.org>
> > > Subject: Re: =5BPATCH v1 2/2=5D exfat: hint the empty entry which at =
the
> > > end of cluster chain
> > >
> > > Add missing Cc: Yuezhang Mo.
> > >
> > > 2022-10-31 15:17 GMT+09:00, Sungjong Seo <sj1557.seo=40samsung.com>:
> > > > Hi, Yuezhang Mo,
> > > >
> > > >> After traversing all directory entries, hint the empty directory
> > > >> entry no matter whether or not there are enough empty directory
> > > >> entries.
> > > >>
> > > >> After this commit, hint the empty directory entries like this:
> > > >>
> > > >> 1. Hint the deleted directory entries if enough; 2. Hint the
> > > >> deleted and unused directory entries which at the
> > > >>    end of the cluster chain no matter whether enough or not(Add
> > > >>    by this commit);
> > > >> 3. If no any empty directory entries, hint the empty directory
> > > >>    entries in the new cluster(Add by this commit).
> > > >>
> > > >> This avoids repeated traversal of directory entries, reduces CPU
> > > >> usage, and improves the performance of creating files and
> > > >> directories(especially on low-performance CPUs).
> > > >>
> > > >> Test create 5000 files in a class 4 SD card on imx6q-sabrelite
> > > >> with:
> > > >>
> > > >> for ((i=3D0;i<5;i++)); do
> > > >>    sync
> > > >>    time (for ((j=3D1;j<=3D1000;j++)); do touch file=24((i*1000+j))=
;
> > > >> done) done
> > > >>
> > > >> The more files, the more performance improvements.
> > > >>
> > > >>             Before   After    Improvement
> > > >>    1=7E1000   25.360s  22.168s  14.40%
> > > >> 1001=7E2000   38.242s  28.72ss  33.15%
> > > >> 2001=7E3000   49.134s  35.037s  40.23%
> > > >> 3001=7E4000   62.042s  41.624s  49.05%
> > > >> 4001=7E5000   73.629s  46.772s  57.42%
> > > >>
> > > >> Signed-off-by: Yuezhang Mo <Yuezhang.Mo=40sony.com>
> > > >> Reviewed-by: Andy Wu <Andy.Wu=40sony.com>
> > > >> Reviewed-by: Aoyama Wataru <wataru.aoyama=40sony.com>
> > > >> ---
> > > >>  fs/exfat/dir.c   =7C 26 ++++++++++++++++++++++----
> > > >>  fs/exfat/namei.c =7C 22 ++++++++++++++--------
> > > >>  2 files changed, 36 insertions(+), 12 deletions(-)
> > > >>
> > > >> diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c index
> > > >> a569f285f4fd..7600f3521246 100644
> > > >> --- a/fs/exfat/dir.c
> > > >> +++ b/fs/exfat/dir.c
> > > >> =40=40 -936,18 +936,25 =40=40 struct exfat_entry_set_cache
> > > >> *exfat_get_dentry_set(struct super_block *sb,
> > > >>
> > > >>  static inline void exfat_hint_empty_entry(struct exfat_inode_info
> *ei,
> > > >>  		struct exfat_hint_femp *candi_empty, struct
> exfat_chain *clu,
> > > >> -		int dentry, int num_entries)
> > > >> +		int dentry, int num_entries, int entry_type)
> > > >>  =7B
> > > >>  	if (ei->hint_femp.eidx =3D=3D EXFAT_HINT_NONE =7C=7C
> > > >>  	    ei->hint_femp.count < num_entries =7C=7C
> > > >>  	    ei->hint_femp.eidx > dentry) =7B
> > > >> +		int total_entries =3D EXFAT_B_TO_DEN(i_size_read(&ei-
> > > >> >vfs_inode));
> > > >> +
> > > >>  		if (candi_empty->count =3D=3D 0) =7B
> > > >>  			candi_empty->cur =3D *clu;
> > > >>  			candi_empty->eidx =3D dentry;
> > > >>  		=7D
> > > >>
> > > >> -		candi_empty->count++;
> > > >> -		if (candi_empty->count =3D=3D num_entries)
> > > >> +		if (entry_type =3D=3D TYPE_UNUSED)
> > > >> +			candi_empty->count +=3D total_entries - dentry;
> > > >
> > > > This seems like a very good approach. Perhaps the key fix that
> > > > improved performance seems to be the handling of cases where empty
> > > > space was not found and ended with TYPE_UNUSED.
> > > >
> > > > However, there are concerns about trusting and using the number of
> > > > free entries after TYPE_UNUSED calculated based on directory size.
> > > > This is because, unlike exFAT Spec., in the real world, unexpected
> > > > TYPE_UNUSED entries may exist. :( That's why
> > > > exfat_search_empty_slot() checks if there is any valid entry after
> > > > TYPE_UNUSED. In my experience, they can be caused by a wrong FS
> > > > driver and H/W defects, and the probability of occurrence is not lo=
w.
> > > >
> > > > Therefore, when the lookup ends with TYPE_UNUSED, if there are no
> > > > empty entries found yet, it would be better to set the last empty
> > > > entry to hint_femp.eidx and set hint_femp.count to 0.
> > > > If so, even if the lookup ends with TYPE_UNUSED,
> > > > exfat_search_empty_slot() can start searching from the position of
> > > > the last empty entry and check whether there are actually empty
> > > > entries as many as the required num_entries as now.
> > > >
> > > > what do you think?
> > > >
> > > >> +		else
> > > >> +			candi_empty->count++;
> > > >> +
> > > >> +		if (candi_empty->count =3D=3D num_entries =7C=7C
> > > >> +		    candi_empty->count + candi_empty->eidx =3D=3D
> total_entries)
> > > >>  			ei->hint_femp =3D *candi_empty;
> > > >>  	=7D
> > > >>  =7D
> > > > =5Bsnip=5D
> > > >> --
> > > >> 2.25.1
> > > >
> > > >