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

[AKASHI Takahiro]

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 at 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
> > >