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

[Heinrich Schuchardt]

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.

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