Re: [PATCH v2 1/5] fs: fat: finding an empty FAT cluster

AKASHI Takahiro
2022-08-02T00:03:12Z

On Mon, Aug 01, 2022 at 10:21:20AM +0200, Heinrich Schuchardt wrote:
>
>
> On 8/1/22 03:02, AKASHI Takahiro wrote:
> > On Sun, Jul 31, 2022 at 01:58:33PM +0200, Heinrich Schuchardt wrote:
> > > Currently we have two functions with redundant coding to find an empty
> > > cluster:
> > >
> > > * find_empty_cluster() seeks from the beginning of the FAT table
> > > * determine_fatent() seeks after a given entry
> > >
> > > Both do not detect the end of the FAT table correctly and return an invalid
> > > cluster number if no empty entry if found.
> > >
> > > find_empty_cluster() is replaced by an invocation of determine_fatent().
> > >
> > > determine_fatent() is changed to seek in a second round from the beginning
> > > of the FAT table and to return an error code if no free entry is found.
> > > With this patch we will always find an empty cluster if it exists.
> > >
> > > Further patches are needed to handle the disk full error gracefully.
> > >
> > > Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
> > > ---
> > > v2:
> > > no change
> >
> > I made this comment before:
> > https://lists.denx.de/pipermail/u-boot/2022-July/488827.html
> >
> > -Takahiro Akashi
>
> The speedup only exists in the rare case that the disk is full.
> Therefore reducing the code size and complexity has priority.

I don't believe that my approach is complexed at all.

-Takahiro Akashi

> Best regards
>
> Heinrich
>
> >
> > > ---
> > > fs/fat/fat_write.c | 56 ++++++++++++++++++++++++----------------------
> > > 1 file changed, 29 insertions(+), 27 deletions(-)
> > >
> > > diff --git a/fs/fat/fat_write.c b/fs/fat/fat_write.c
> > > index 8ff2f6def0..a137e14f41 100644
> > > --- a/fs/fat/fat_write.c
> > > +++ b/fs/fat/fat_write.c
> > > @@ -536,22 +536,41 @@ static int set_fatent_value(fsdata *mydata, __u32 entry, __u32 entry_value)
> > > return 0;
> > > }
> > > -/*
> > > - * Determine the next free cluster after 'entry' in a FAT (12/16/32) table
> > > - * and link it to 'entry'. EOC marker is not set on returned entry.
> > > +/**
> > > + * determine_fatent() - get next free FAT cluster
> > > + *
> > > + * The parameter @entry indicates the current cluster. To reduce fragementation
> > > + * the function first searches for a free cluster after the current cluster.
> > > + * If none is found, the search is repeated from the beginning of the FAT table.
> > > + *
> > > + * If @entry is set, the new FAT entry is appended to the given one.
> > > + * If @entry is zero, only the number of the first free cluster is returned.
> > > + *
> > > + * @entry: current entry
> > > + * Return: next free cluster or negative error
> > > */
> > > -static __u32 determine_fatent(fsdata *mydata, __u32 entry)
> > > +static int determine_fatent(fsdata *mydata, __u32 entry)
> > > {
> > > - __u32 next_fat, next_entry = entry + 1;
> > > + __u32 next_fat, next_entry = entry;
> > > + int second_round = 0;
> > > while (1) {
> > > + ++next_entry;
> > > + if (CHECK_CLUST(next_entry, mydata->fatsize)) {
> > > + if (!second_round) {
> > > + second_round = 1;
> > > + next_entry = 3;
> > > + } else {
> > > + return -ENOSPC;
> > > + }
> > > + }
> > > next_fat = get_fatent(mydata, next_entry);
> > > - if (next_fat == 0) {
> > > + if (!next_fat) {
> > > /* found free entry, link to entry */
> > > - set_fatent_value(mydata, entry, next_entry);
> > > + if (entry)
> > > + set_fatent_value(mydata, entry, next_entry);
> > > break;
> > > }
> > > - next_entry++;
> > > }
> > > debug("FAT%d: entry: %08x, entry_value: %04x\n",
> > > mydata->fatsize, entry, next_entry);
> > > @@ -794,23 +813,6 @@ get_set_cluster(fsdata *mydata, __u32 clustnum, loff_t pos, __u8 *buffer,
> > > return 0;
> > > }
> > > -/*
> > > - * Find the first empty cluster
> > > - */
> > > -static int find_empty_cluster(fsdata *mydata)
> > > -{
> > > - __u32 fat_val, entry = 3;
> > > -
> > > - while (1) {
> > > - fat_val = get_fatent(mydata, entry);
> > > - if (fat_val == 0)
> > > - break;
> > > - entry++;
> > > - }
> > > -
> > > - return entry;
> > > -}
> > > -
> > > /**
> > > * new_dir_table() - allocate a cluster for additional directory entries
> > > *
> > > @@ -824,7 +826,7 @@ static int new_dir_table(fat_itr *itr)
> > > int dir_oldclust = itr->clust;
> > > unsigned int bytesperclust = mydata->clust_size * mydata->sect_size;
> > > - dir_newclust = find_empty_cluster(mydata);
> > > + dir_newclust = determine_fatent(mydata, 0);
> > > /*
> > > * Flush before updating FAT to ensure valid directory structure
> > > @@ -1066,7 +1068,7 @@ set_clusters:
> > > /* Assure that curclust is valid */
> > > if (!curclust) {
> > > - curclust = find_empty_cluster(mydata);
> > > + curclust = determine_fatent(mydata, 0);
> > > set_start_cluster(mydata, dentptr, curclust);
> > > } else {
> > > newclust = get_fatent(mydata, curclust);
> > > --
> > > 2.36.1
> > >