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

[AKASHI Takahiro]

Thank you for fixing this.

On Tue, Jul 12, 2022 at 10:33:12PM +0000, 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.

nitpick: empty -> free for consistent uses across this patch

> Further patches are needed to handle the disk full error gracefully.
> 
> Signed-off-by: Heinrich Schuchardt <xypron.glpk at gmx.de>
> ---
>  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;
> +			}
> +		}

The logic is fine, but in case of entry != 0 and second_round
and if disk is full, fat entries after "entry" can unnecessarily be
checked twice. So,

        next_entry = entry + 1;
        while (1) {
                if (next_entry == entry)
                        return -ENOSPC;
                if (CHECK_CLUST(...)) {
                        if (!entry)
                                return -ENOSPC;
                        next_entry = 3;
                        continue;
                }
                ...

                next_entry++;
        }

should work better.

-Takahiro Akashi

>  		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.30.2
>