[PATCH 0/3] fs/fat: fix handling of full disk

[PATCH 0/3] fs/fat: fix handling of full disk

[Heinrich Schuchardt]

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.

Correctly determine empty FAT entries and full disk correctly.

Carve out a function for creating directory entries to avoid code
duplication.

Heinrich Schuchardt (3):
  fs: fat: finding an empty FAT cluster
  fs: fat: determine_fatent() error handling
  fs: fat: carve out fat_create_dir_entry()

 fs/fat/fat_write.c | 161 ++++++++++++++++++++++-----------------------
 1 file changed, 79 insertions(+), 82 deletions(-)

--
2.30.2

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

[Heinrich Schuchardt]

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 <xypron.glpk@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;
+			}
+		}
 		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

Re: [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@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
> 

[PATCH 2/3] fs: fat: determine_fatent() error handling

[Heinrich Schuchardt]

Handle disk full errors.

Signed-off-by: Heinrich Schuchardt <xypron.glpk@gmx.de>
---
 fs/fat/fat_write.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/fs/fat/fat_write.c b/fs/fat/fat_write.c
index a137e14f41..57522f96a8 100644
--- a/fs/fat/fat_write.c
+++ b/fs/fat/fat_write.c
@@ -827,6 +827,8 @@ static int new_dir_table(fat_itr *itr)
 	unsigned int bytesperclust = mydata->clust_size * mydata->sect_size;

 	dir_newclust = determine_fatent(mydata, 0);
+	if (dir_newclust < 0)
+		return dir_newclust;

 	/*
 	 * Flush before updating FAT to ensure valid directory structure
@@ -927,8 +929,8 @@ set_contents(fsdata *mydata, dir_entry *dentptr, loff_t pos, __u8 *buffer,
 	     loff_t maxsize, loff_t *gotsize)
 {
 	unsigned int bytesperclust = mydata->clust_size * mydata->sect_size;
-	__u32 curclust = START(dentptr);
-	__u32 endclust = 0, newclust = 0;
+	int curclust = START(dentptr);
+	int endclust = 0, newclust = 0;
 	u64 cur_pos, filesize;
 	loff_t offset, actsize, wsize;

@@ -1069,12 +1071,16 @@ set_clusters:
 	/* Assure that curclust is valid */
 	if (!curclust) {
 		curclust = determine_fatent(mydata, 0);
+		if (curclust < 0)
+			return -1;
 		set_start_cluster(mydata, dentptr, curclust);
 	} else {
 		newclust = get_fatent(mydata, curclust);

 		if (IS_LAST_CLUST(newclust, mydata->fatsize)) {
 			newclust = determine_fatent(mydata, curclust);
+			if (newclust < 0)
+				return -1;
 			set_fatent_value(mydata, curclust, newclust);
 			curclust = newclust;
 		} else {
@@ -1095,6 +1101,8 @@ set_clusters:
 		/* search for consecutive clusters */
 		while (actsize < filesize) {
 			newclust = determine_fatent(mydata, endclust);
+			if (newclust < 0)
+				return -1;

 			if ((newclust - 1) != endclust)
 				/* write to <curclust..endclust> */
--
2.30.2

[PATCH 3/3] fs: fat: carve out fat_create_dir_entry()

[Heinrich Schuchardt]

fat_mkdir() and file_fat_write_at() use identical code to create a new
directory entry. Carve out a new function fat_create_dir_entry() to avoid
this code duplication.

Signed-off-by: Heinrich Schuchardt <xypron.glpk@gmx.de>
---
 fs/fat/fat_write.c | 93 ++++++++++++++++++++--------------------------
 1 file changed, 40 insertions(+), 53 deletions(-)

diff --git a/fs/fat/fat_write.c b/fs/fat/fat_write.c
index 57522f96a8..a25b2283d4 100644
--- a/fs/fat/fat_write.c
+++ b/fs/fat/fat_write.c
@@ -1314,6 +1314,43 @@ static int normalize_longname(char *l_filename, const char *filename)
 	return 0;
 }

+/**
+ * fat_create_dir_entry() - create directory entry
+ *
+ * @itr:	directory iterator
+ * @basename:	name of file or directory to be created
+ * @size:	file size
+ * @attr:	file or directory attributes
+ * Return:	0 for success, -EIO on error
+ */
+static int fat_create_dir_entry(fat_itr *itr, const char *basename,
+				loff_t size, u8 attr)
+{
+	/* Create a new file */
+	char shortname[SHORT_NAME_SIZE];
+	int ndent;
+	int ret;
+
+	/* Check if long name is needed */
+	ndent = set_name(itr, basename, shortname);
+	if (ndent < 0)
+		return ndent;
+	ret = fat_find_empty_dentries(itr, ndent);
+	if (ret)
+		return ret;
+	if (ndent > 1) {
+		/* Set long name entries */
+		ret = fill_dir_slot(itr, basename, shortname);
+		if (ret)
+			return ret;
+	}
+
+	/* Set short name entry */
+	fill_dentry(itr->fsdata, itr->dent, shortname, 0, size, attr);
+
+	return 0;
+}
+
 int file_fat_write_at(const char *filename, loff_t pos, void *buffer,
 		      loff_t size, loff_t *actwrite)
 {
@@ -1383,8 +1420,6 @@ int file_fat_write_at(const char *filename, loff_t pos, void *buffer,
 		retdent->size = cpu_to_le32(pos + size);
 	} else {
 		/* Create a new file */
-		char shortname[SHORT_NAME_SIZE];
-		int ndent;

 		if (pos) {
 			/* No hole allowed */
@@ -1392,25 +1427,7 @@ int file_fat_write_at(const char *filename, loff_t pos, void *buffer,
 			goto exit;
 		}

-		/* Check if long name is needed */
-		ndent = set_name(itr, basename, shortname);
-		if (ndent < 0) {
-			ret = ndent;
-			goto exit;
-		}
-		ret = fat_find_empty_dentries(itr, ndent);
-		if (ret)
-			goto exit;
-		if (ndent > 1) {
-			/* Set long name entries */
-			ret = fill_dir_slot(itr, basename, shortname);
-			if (ret)
-				goto exit;
-		}
-
-		/* Set short name entry */
-		fill_dentry(itr->fsdata, itr->dent, shortname, 0, size,
-			    ATTR_ARCH);
+		ret = fat_create_dir_entry(itr, basename, size, ATTR_ARCH);

 		retdent = itr->dent;
 	}
@@ -1693,38 +1710,8 @@ int fat_mkdir(const char *dirname)
 		ret = -EEXIST;
 		goto exit;
 	} else {
-		char shortname[SHORT_NAME_SIZE];
-		int ndent;
-
-		if (itr->is_root) {
-			/* root dir cannot have "." or ".." */
-			if (!strcmp(l_dirname, ".") ||
-			    !strcmp(l_dirname, "..")) {
-				ret = -EINVAL;
-				goto exit;
-			}
-		}
-
-		/* Check if long name is needed */
-		ndent = set_name(itr, basename, shortname);
-		if (ndent < 0) {
-			ret = ndent;
-			goto exit;
-		}
-		ret = fat_find_empty_dentries(itr, ndent);
-		if (ret)
-			goto exit;
-		if (ndent > 1) {
-			/* Set long name entries */
-			ret = fill_dir_slot(itr, basename, shortname);
-			if (ret)
-				goto exit;
-		}
-
-		/* Set attribute as archive for regular file */
-		fill_dentry(itr->fsdata, itr->dent, shortname, 0, 0,
-			    ATTR_DIR | ATTR_ARCH);
-
+		ret = fat_create_dir_entry(itr, basename, 0,
+					   ATTR_DIR | ATTR_ARCH);
 		retdent = itr->dent;
 	}

--
2.30.2

Re: [PATCH 3/3] fs: fat: carve out fat_create_dir_entry()

[AKASHI Takahiro]

On Tue, Jul 12, 2022 at 10:33:14PM +0000, Heinrich Schuchardt wrote:
> fat_mkdir() and file_fat_write_at() use identical code to create a new
> directory entry. Carve out a new function fat_create_dir_entry() to avoid
> this code duplication.

Why not merge your patch[1] here as you're going to newly introduce fat_create_dir_entry()?

[1] https://lists.denx.de/pipermail/u-boot/2022-July/488693.html

-Takahiro Akashi


> Signed-off-by: Heinrich Schuchardt <xypron.glpk@gmx.de>
> ---
>  fs/fat/fat_write.c | 93 ++++++++++++++++++++--------------------------
>  1 file changed, 40 insertions(+), 53 deletions(-)
> 
> diff --git a/fs/fat/fat_write.c b/fs/fat/fat_write.c
> index 57522f96a8..a25b2283d4 100644
> --- a/fs/fat/fat_write.c
> +++ b/fs/fat/fat_write.c
> @@ -1314,6 +1314,43 @@ static int normalize_longname(char *l_filename, const char *filename)
>  	return 0;
>  }
> 
> +/**
> + * fat_create_dir_entry() - create directory entry
> + *
> + * @itr:	directory iterator
> + * @basename:	name of file or directory to be created
> + * @size:	file size
> + * @attr:	file or directory attributes
> + * Return:	0 for success, -EIO on error
> + */
> +static int fat_create_dir_entry(fat_itr *itr, const char *basename,
> +				loff_t size, u8 attr)
> +{
> +	/* Create a new file */
> +	char shortname[SHORT_NAME_SIZE];
> +	int ndent;
> +	int ret;
> +
> +	/* Check if long name is needed */
> +	ndent = set_name(itr, basename, shortname);
> +	if (ndent < 0)
> +		return ndent;
> +	ret = fat_find_empty_dentries(itr, ndent);
> +	if (ret)
> +		return ret;
> +	if (ndent > 1) {
> +		/* Set long name entries */
> +		ret = fill_dir_slot(itr, basename, shortname);
> +		if (ret)
> +			return ret;
> +	}
> +
> +	/* Set short name entry */
> +	fill_dentry(itr->fsdata, itr->dent, shortname, 0, size, attr);
> +
> +	return 0;
> +}
> +
>  int file_fat_write_at(const char *filename, loff_t pos, void *buffer,
>  		      loff_t size, loff_t *actwrite)
>  {
> @@ -1383,8 +1420,6 @@ int file_fat_write_at(const char *filename, loff_t pos, void *buffer,
>  		retdent->size = cpu_to_le32(pos + size);
>  	} else {
>  		/* Create a new file */
> -		char shortname[SHORT_NAME_SIZE];
> -		int ndent;
> 
>  		if (pos) {
>  			/* No hole allowed */
> @@ -1392,25 +1427,7 @@ int file_fat_write_at(const char *filename, loff_t pos, void *buffer,
>  			goto exit;
>  		}
> 
> -		/* Check if long name is needed */
> -		ndent = set_name(itr, basename, shortname);
> -		if (ndent < 0) {
> -			ret = ndent;
> -			goto exit;
> -		}
> -		ret = fat_find_empty_dentries(itr, ndent);
> -		if (ret)
> -			goto exit;
> -		if (ndent > 1) {
> -			/* Set long name entries */
> -			ret = fill_dir_slot(itr, basename, shortname);
> -			if (ret)
> -				goto exit;
> -		}
> -
> -		/* Set short name entry */
> -		fill_dentry(itr->fsdata, itr->dent, shortname, 0, size,
> -			    ATTR_ARCH);
> +		ret = fat_create_dir_entry(itr, basename, size, ATTR_ARCH);
> 
>  		retdent = itr->dent;
>  	}
> @@ -1693,38 +1710,8 @@ int fat_mkdir(const char *dirname)
>  		ret = -EEXIST;
>  		goto exit;
>  	} else {
> -		char shortname[SHORT_NAME_SIZE];
> -		int ndent;
> -
> -		if (itr->is_root) {
> -			/* root dir cannot have "." or ".." */
> -			if (!strcmp(l_dirname, ".") ||
> -			    !strcmp(l_dirname, "..")) {
> -				ret = -EINVAL;
> -				goto exit;
> -			}
> -		}
> -
> -		/* Check if long name is needed */
> -		ndent = set_name(itr, basename, shortname);
> -		if (ndent < 0) {
> -			ret = ndent;
> -			goto exit;
> -		}
> -		ret = fat_find_empty_dentries(itr, ndent);
> -		if (ret)
> -			goto exit;
> -		if (ndent > 1) {
> -			/* Set long name entries */
> -			ret = fill_dir_slot(itr, basename, shortname);
> -			if (ret)
> -				goto exit;
> -		}
> -
> -		/* Set attribute as archive for regular file */
> -		fill_dentry(itr->fsdata, itr->dent, shortname, 0, 0,
> -			    ATTR_DIR | ATTR_ARCH);
> -
> +		ret = fat_create_dir_entry(itr, basename, 0,
> +					   ATTR_DIR | ATTR_ARCH);
>  		retdent = itr->dent;
>  	}
> 
> --
> 2.30.2
> 

Re: [PATCH 0/3] fs/fat: fix handling of full disk

[AKASHI Takahiro]

On Tue, Jul 12, 2022 at 10:33:11PM +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.
> 
> Correctly determine empty FAT entries and full disk correctly.

I hope that you add a test for this specific corner case.

Thanks,
-Takahiro Akashi


> Carve out a function for creating directory entries to avoid code
> duplication.
> 
> Heinrich Schuchardt (3):
>   fs: fat: finding an empty FAT cluster
>   fs: fat: determine_fatent() error handling
>   fs: fat: carve out fat_create_dir_entry()
> 
>  fs/fat/fat_write.c | 161 ++++++++++++++++++++++-----------------------
>  1 file changed, 79 insertions(+), 82 deletions(-)
> 
> --
> 2.30.2
>