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

[PATCH v2 0/5] 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.

Provide a unit test checking that a full FAT16 root directory is
recognized. For other file systems testing is too time consuming.
FAT32 allows 65536 entries per directory.

v2:
	Handle errors returned by fat_create_dir_entry()
	Add unit test

Heinrich Schuchardt (5):
  fs: fat: finding an empty FAT cluster
  fs: fat: determine_fatent() error handling
  fs: fat: carve out fat_create_dir_entry()
  test: let fs_obj_mkdir() provide full file system type
  test: add test for full FAT16 directory

 fs/fat/fat_write.c                  | 161 ++++++++++++++--------------
 test/py/tests/test_fs/conftest.py   |   6 +-
 test/py/tests/test_fs/test_mkdir.py |  72 ++++++++-----
 3 files changed, 131 insertions(+), 108 deletions(-)

-- 
2.36.1

[PATCH v2 1/5] 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 <heinrich.schuchardt@canonical.com>
---
v2:
	no change
---
 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

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

[Heinrich Schuchardt]

Handle disk full errors.

Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
---
v2:
	no change
---
 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.36.1

[PATCH v2 3/5] 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 <heinrich.schuchardt@canonical.com>
---
v2:
	handle errors returned by fat_create_dir_entry()
---
 fs/fat/fat_write.c | 93 ++++++++++++++++++++++------------------------
 1 file changed, 44 insertions(+), 49 deletions(-)

diff --git a/fs/fat/fat_write.c b/fs/fat/fat_write.c
index 57522f96a8..ccdacd22c2 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,26 +1427,12 @@ 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)
+		ret = fat_create_dir_entry(itr, basename, size, ATTR_ARCH);
+		if (ret < 0) {
+			log_err("Can't create directory entry\n");
 			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);
-
 		retdent = itr->dent;
 	}
 
@@ -1693,38 +1714,12 @@ 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)
+		ret = fat_create_dir_entry(itr, basename, 0,
+					   ATTR_DIR | ATTR_ARCH);
+		if (ret < 0) {
+			log_err("Can't create directory entry\n");
 			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);
-
 		retdent = itr->dent;
 	}
 
-- 
2.36.1

[PATCH v2 4/5] test: let fs_obj_mkdir() provide full file system type

[Heinrich Schuchardt]

The fixuture fs_obj_mkdir() up to now only supplies an abbreviated file
system type (e.g. fat). Provide the full file system type too (e.g. fat32).

Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
---
v2:
	new patch
---
 test/py/tests/test_fs/conftest.py   |  6 ++--
 test/py/tests/test_fs/test_mkdir.py | 54 ++++++++++++++---------------
 2 files changed, 30 insertions(+), 30 deletions(-)

diff --git a/test/py/tests/test_fs/conftest.py b/test/py/tests/test_fs/conftest.py
index b638284e07..efe8be06eb 100644
--- a/test/py/tests/test_fs/conftest.py
+++ b/test/py/tests/test_fs/conftest.py
@@ -489,8 +489,8 @@ def fs_obj_mkdir(request, u_boot_config):
 	u_boot_config: U-boot configuration.
 
     Return:
-        A fixture for mkdir test, i.e. a duplet of file system type and
-        volume file name.
+        A fixture for mkdir test, i.e. a triplet of file system type (e.g. fat),
+        volume file name and full file system type (e.g. fat32).
     """
     fs_type = request.param
     fs_img = ''
@@ -505,7 +505,7 @@ def fs_obj_mkdir(request, u_boot_config):
         pytest.skip('Setup failed for filesystem: ' + fs_type)
         return
     else:
-        yield [fs_ubtype, fs_img]
+        yield [fs_ubtype, fs_img, fs_type]
     call('rm -f %s' % fs_img, shell=True)
 
 #
diff --git a/test/py/tests/test_fs/test_mkdir.py b/test/py/tests/test_fs/test_mkdir.py
index fa9561ec35..f5cc308362 100644
--- a/test/py/tests/test_fs/test_mkdir.py
+++ b/test/py/tests/test_fs/test_mkdir.py
@@ -18,104 +18,104 @@ class TestMkdir(object):
         """
         Test Case 1 - create a directory under a root
         """
-        fs_type,fs_img = fs_obj_mkdir
+        fs_ubtype, fs_img, _ = fs_obj_mkdir
         with u_boot_console.log.section('Test Case 1 - mkdir'):
             output = u_boot_console.run_command_list([
                 'host bind 0 %s' % fs_img,
-                '%smkdir host 0:0 dir1' % fs_type,
-                '%sls host 0:0 /' % fs_type])
+                '%smkdir host 0:0 dir1' % fs_ubtype,
+                '%sls host 0:0 /' % fs_ubtype])
             assert('dir1/' in ''.join(output))
 
             output = u_boot_console.run_command(
-                '%sls host 0:0 dir1' % fs_type)
+                '%sls host 0:0 dir1' % fs_ubtype)
             assert('./'   in output)
             assert('../'  in output)
-            assert_fs_integrity(fs_type, fs_img)
+            assert_fs_integrity(fs_ubtype, fs_img)
 
 
     def test_mkdir2(self, u_boot_console, fs_obj_mkdir):
         """
         Test Case 2 - create a directory under a sub-directory
         """
-        fs_type,fs_img = fs_obj_mkdir
+        fs_ubtype, fs_img, _ = fs_obj_mkdir
         with u_boot_console.log.section('Test Case 2 - mkdir (sub-sub directory)'):
             output = u_boot_console.run_command_list([
                 'host bind 0 %s' % fs_img,
-                '%smkdir host 0:0 dir1/dir2' % fs_type,
-                '%sls host 0:0 dir1' % fs_type])
+                '%smkdir host 0:0 dir1/dir2' % fs_ubtype,
+                '%sls host 0:0 dir1' % fs_ubtype])
             assert('dir2/' in ''.join(output))
 
             output = u_boot_console.run_command(
-                '%sls host 0:0 dir1/dir2' % fs_type)
+                '%sls host 0:0 dir1/dir2' % fs_ubtype)
             assert('./'   in output)
             assert('../'  in output)
-            assert_fs_integrity(fs_type, fs_img)
+            assert_fs_integrity(fs_ubtype, fs_img)
 
     def test_mkdir3(self, u_boot_console, fs_obj_mkdir):
         """
         Test Case 3 - trying to create a directory with a non-existing
         path should fail
         """
-        fs_type,fs_img = fs_obj_mkdir
+        fs_ubtype, fs_img, _ = fs_obj_mkdir
         with u_boot_console.log.section('Test Case 3 - mkdir (non-existing path)'):
             output = u_boot_console.run_command_list([
                 'host bind 0 %s' % fs_img,
-                '%smkdir host 0:0 none/dir3' % fs_type])
+                '%smkdir host 0:0 none/dir3' % fs_ubtype])
             assert('Unable to create a directory' in ''.join(output))
-            assert_fs_integrity(fs_type, fs_img)
+            assert_fs_integrity(fs_ubtype, fs_img)
 
     def test_mkdir4(self, u_boot_console, fs_obj_mkdir):
         """
         Test Case 4 - trying to create "." should fail
         """
-        fs_type,fs_img = fs_obj_mkdir
+        fs_ubtype, fs_img, _ = fs_obj_mkdir
         with u_boot_console.log.section('Test Case 4 - mkdir (".")'):
             output = u_boot_console.run_command_list([
                 'host bind 0 %s' % fs_img,
-                '%smkdir host 0:0 .' % fs_type])
+                '%smkdir host 0:0 .' % fs_ubtype])
             assert('Unable to create a directory' in ''.join(output))
-            assert_fs_integrity(fs_type, fs_img)
+            assert_fs_integrity(fs_ubtype, fs_img)
 
     def test_mkdir5(self, u_boot_console, fs_obj_mkdir):
         """
         Test Case 5 - trying to create ".." should fail
         """
-        fs_type,fs_img = fs_obj_mkdir
+        fs_ubtype, fs_img, _ = fs_obj_mkdir
         with u_boot_console.log.section('Test Case 5 - mkdir ("..")'):
             output = u_boot_console.run_command_list([
                 'host bind 0 %s' % fs_img,
-                '%smkdir host 0:0 ..' % fs_type])
+                '%smkdir host 0:0 ..' % fs_ubtype])
             assert('Unable to create a directory' in ''.join(output))
-            assert_fs_integrity(fs_type, fs_img)
+            assert_fs_integrity(fs_ubtype, fs_img)
 
     def test_mkdir6(self, u_boot_console, fs_obj_mkdir):
         """
         'Test Case 6 - create as many directories as amount of directory
         entries goes beyond a cluster size)'
         """
-        fs_type,fs_img = fs_obj_mkdir
+        fs_ubtype, fs_img, _ = fs_obj_mkdir
         with u_boot_console.log.section('Test Case 6 - mkdir (create many)'):
             output = u_boot_console.run_command_list([
                 'host bind 0 %s' % fs_img,
-                '%smkdir host 0:0 dir6' % fs_type,
-                '%sls host 0:0 /' % fs_type])
+                '%smkdir host 0:0 dir6' % fs_ubtype,
+                '%sls host 0:0 /' % fs_ubtype])
             assert('dir6/' in ''.join(output))
 
             for i in range(0, 20):
                 output = u_boot_console.run_command(
                     '%smkdir host 0:0 dir6/0123456789abcdef%02x'
-                    % (fs_type, i))
-            output = u_boot_console.run_command('%sls host 0:0 dir6' % fs_type)
+                    % (fs_ubtype, i))
+            output = u_boot_console.run_command('%sls host 0:0 dir6' % fs_ubtype)
             assert('0123456789abcdef00/'  in output)
             assert('0123456789abcdef13/'  in output)
 
             output = u_boot_console.run_command(
-                '%sls host 0:0 dir6/0123456789abcdef13/.' % fs_type)
+                '%sls host 0:0 dir6/0123456789abcdef13/.' % fs_ubtype)
             assert('./'   in output)
             assert('../'  in output)
 
             output = u_boot_console.run_command(
-                '%sls host 0:0 dir6/0123456789abcdef13/..' % fs_type)
+                '%sls host 0:0 dir6/0123456789abcdef13/..' % fs_ubtype)
             assert('0123456789abcdef00/'  in output)
             assert('0123456789abcdef13/'  in output)
-            assert_fs_integrity(fs_type, fs_img)
+            assert_fs_integrity(fs_ubtype, fs_img)
-- 
2.36.1

[PATCH v2 5/5] test: add test for full FAT16 directory

[Heinrich Schuchardt]

Add a unit test checking that a full FAT16 directory leads to an error
when trying to add an additional entry.

Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
---
v2:
	new patch
---
 test/py/tests/test_fs/test_mkdir.py | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/test/py/tests/test_fs/test_mkdir.py b/test/py/tests/test_fs/test_mkdir.py
index f5cc308362..e3a9e3ed27 100644
--- a/test/py/tests/test_fs/test_mkdir.py
+++ b/test/py/tests/test_fs/test_mkdir.py
@@ -119,3 +119,20 @@ class TestMkdir(object):
             assert('0123456789abcdef00/'  in output)
             assert('0123456789abcdef13/'  in output)
             assert_fs_integrity(fs_ubtype, fs_img)
+
+    def test_mkdir7(self, u_boot_console, fs_obj_mkdir):
+        """ Test Case 7 - max out number of root directory entries
+        """
+        _, _, fs_type = fs_obj_mkdir
+        if fs_type != 'fat16':
+            return
+        with u_boot_console.log.section('Test Case 7 - mkdir (max out)'):
+            for i in range(0, 512):
+                output = u_boot_console.run_command(
+                    f'fatmkdir host 0:0 /U-Boot-mkdir-max-out-test-directory-{i:05d}')
+                if 'Can\'t create directory entry' in output:
+                    break
+            # A directory was created
+            assert i > 0
+            # The FAT16 root directory has only 512 directory entries
+            assert i <= 512 / 5
-- 
2.36.1

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

[AKASHI Takahiro]

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

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

Re: [PATCH v2 5/5] test: add test for full FAT16 directory

[AKASHI Takahiro]

On Sun, Jul 31, 2022 at 01:58:37PM +0200, Heinrich Schuchardt wrote:
> Add a unit test checking that a full FAT16 directory leads to an error
> when trying to add an additional entry.

Thank you for adding this test case, but
why do you restrict this test to fat16 and the root directory?
The root directory on fat16 is a very much special case and differently
implemented from others. So the test scenario doesn't do what we expect
for fulfilling the whole disk.

I think we should use other sub directories (and other file systems as well).

> Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
> ---
> v2:
> 	new patch
> ---
>  test/py/tests/test_fs/test_mkdir.py | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
> 
> diff --git a/test/py/tests/test_fs/test_mkdir.py b/test/py/tests/test_fs/test_mkdir.py
> index f5cc308362..e3a9e3ed27 100644
> --- a/test/py/tests/test_fs/test_mkdir.py
> +++ b/test/py/tests/test_fs/test_mkdir.py
> @@ -119,3 +119,20 @@ class TestMkdir(object):
>              assert('0123456789abcdef00/'  in output)
>              assert('0123456789abcdef13/'  in output)
>              assert_fs_integrity(fs_ubtype, fs_img)
> +
> +    def test_mkdir7(self, u_boot_console, fs_obj_mkdir):
> +        """ Test Case 7 - max out number of root directory entries
> +        """
> +        _, _, fs_type = fs_obj_mkdir

Why not use fs_ubtype, _, fs_type = ..., then

> +        if fs_type != 'fat16':
> +            return
> +        with u_boot_console.log.section('Test Case 7 - mkdir (max out)'):
> +            for i in range(0, 512):
> +                output = u_boot_console.run_command(
> +                    f'fatmkdir host 0:0 /U-Boot-mkdir-max-out-test-directory-{i:05d}')

'%smkdir ...'.format(fs_ubtype, i)

-Takahiro Akashi

> +                if 'Can\'t create directory entry' in output:
> +                    break
> +            # A directory was created
> +            assert i > 0
> +            # The FAT16 root directory has only 512 directory entries
> +            assert i <= 512 / 5
> -- 
> 2.36.1
> 

Re: [PATCH v2 5/5] test: add test for full FAT16 directory

[Heinrich Schuchardt]

On 8/1/22 03:50, AKASHI Takahiro wrote:
> On Sun, Jul 31, 2022 at 01:58:37PM +0200, Heinrich Schuchardt wrote:
>> Add a unit test checking that a full FAT16 directory leads to an error
>> when trying to add an additional entry.
> 
> Thank you for adding this test case, but
> why do you restrict this test to fat16 and the root directory?
> The root directory on fat16 is a very much special case and differently
> implemented from others. So the test scenario doesn't do what we expect
> for fulfilling the whole disk.
> 
> I think we should use other sub directories (and other file systems as well).

No other filesystem but FAT supports mkdir in U-Boot currently.

Creating the maximum 512 directory entries for the root directory of 
FAT16 can be done in a reasonable time.

Otherwise "The maximum valid directory size is 2**21 bytes." Creating 
65536 entries takes far too long to be done in a regular test. Even a 
bash script in Linux needs more than half an hour for this on my laptop.

The 2 MiB limit is not implemented in U-Boot. So the test would fail 
after a few days or weeks.

> 
>> Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
>> ---
>> v2:
>> 	new patch
>> ---
>>   test/py/tests/test_fs/test_mkdir.py | 17 +++++++++++++++++
>>   1 file changed, 17 insertions(+)
>>
>> diff --git a/test/py/tests/test_fs/test_mkdir.py b/test/py/tests/test_fs/test_mkdir.py
>> index f5cc308362..e3a9e3ed27 100644
>> --- a/test/py/tests/test_fs/test_mkdir.py
>> +++ b/test/py/tests/test_fs/test_mkdir.py
>> @@ -119,3 +119,20 @@ class TestMkdir(object):
>>               assert('0123456789abcdef00/'  in output)
>>               assert('0123456789abcdef13/'  in output)
>>               assert_fs_integrity(fs_ubtype, fs_img)
>> +
>> +    def test_mkdir7(self, u_boot_console, fs_obj_mkdir):
>> +        """ Test Case 7 - max out number of root directory entries
>> +        """
>> +        _, _, fs_type = fs_obj_mkdir
> 
> Why not use fs_ubtype, _, fs_type = ..., then
> 
>> +        if fs_type != 'fat16':
>> +            return
>> +        with u_boot_console.log.section('Test Case 7 - mkdir (max out)'):
>> +            for i in range(0, 512):
>> +                output = u_boot_console.run_command(
>> +                    f'fatmkdir host 0:0 /U-Boot-mkdir-max-out-test-directory-{i:05d}')
> 
> '%smkdir ...'.format(fs_ubtype, i)

We know it is FAT.

Best regards

Heinrich
> 
> -Takahiro Akashi
> 
>> +                if 'Can\'t create directory entry' in output:
>> +                    break
>> +            # A directory was created
>> +            assert i > 0
>> +            # The FAT16 root directory has only 512 directory entries
>> +            assert i <= 512 / 5
>> -- 
>> 2.36.1
>>

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

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

Re: [PATCH v2 5/5] test: add test for full FAT16 directory

[AKASHI Takahiro]

On Mon, Aug 01, 2022 at 08:14:15AM +0200, Heinrich Schuchardt wrote:
> 
> 
> On 8/1/22 03:50, AKASHI Takahiro wrote:
> > On Sun, Jul 31, 2022 at 01:58:37PM +0200, Heinrich Schuchardt wrote:
> > > Add a unit test checking that a full FAT16 directory leads to an error
> > > when trying to add an additional entry.
> > 
> > Thank you for adding this test case, but
> > why do you restrict this test to fat16 and the root directory?
> > The root directory on fat16 is a very much special case and differently
> > implemented from others. So the test scenario doesn't do what we expect
> > for fulfilling the whole disk.
> > 
> > I think we should use other sub directories (and other file systems as well).
> 
> No other filesystem but FAT supports mkdir in U-Boot currently.

Right, but it won't prevent us from creating a generic test scenario.
My pytest already has a mechanism to run a test for a specific set of
file systems. See supported_fs_xxx.

> Creating the maximum 512 directory entries for the root directory of FAT16
> can be done in a reasonable time.

As I said, the root directory on fat16 is very special and has a fixed size
of blocks and using it in your test will *never* make the file system full.

> Otherwise "The maximum valid directory size is 2**21 bytes." Creating 65536
> entries takes far too long to be done in a regular test. Even a bash script
> in Linux needs more than half an hour for this on my laptop.

Providing a test and running it is different things.
If necessary, we should exercise it.

> The 2 MiB limit is not implemented in U-Boot. So the test would fail after a
> few days or weeks.

If so, why not fix the problem?

-Takahiro Akashi

> 
> > 
> > > Signed-off-by: Heinrich Schuchardt <heinrich.schuchardt@canonical.com>
> > > ---
> > > v2:
> > > 	new patch
> > > ---
> > >   test/py/tests/test_fs/test_mkdir.py | 17 +++++++++++++++++
> > >   1 file changed, 17 insertions(+)
> > > 
> > > diff --git a/test/py/tests/test_fs/test_mkdir.py b/test/py/tests/test_fs/test_mkdir.py
> > > index f5cc308362..e3a9e3ed27 100644
> > > --- a/test/py/tests/test_fs/test_mkdir.py
> > > +++ b/test/py/tests/test_fs/test_mkdir.py
> > > @@ -119,3 +119,20 @@ class TestMkdir(object):
> > >               assert('0123456789abcdef00/'  in output)
> > >               assert('0123456789abcdef13/'  in output)
> > >               assert_fs_integrity(fs_ubtype, fs_img)
> > > +
> > > +    def test_mkdir7(self, u_boot_console, fs_obj_mkdir):
> > > +        """ Test Case 7 - max out number of root directory entries
> > > +        """
> > > +        _, _, fs_type = fs_obj_mkdir
> > 
> > Why not use fs_ubtype, _, fs_type = ..., then
> > 
> > > +        if fs_type != 'fat16':
> > > +            return
> > > +        with u_boot_console.log.section('Test Case 7 - mkdir (max out)'):
> > > +            for i in range(0, 512):
> > > +                output = u_boot_console.run_command(
> > > +                    f'fatmkdir host 0:0 /U-Boot-mkdir-max-out-test-directory-{i:05d}')
> > 
> > '%smkdir ...'.format(fs_ubtype, i)
> 
> We know it is FAT.
> 
> Best regards
> 
> Heinrich
> > 
> > -Takahiro Akashi
> > 
> > > +                if 'Can\'t create directory entry' in output:
> > > +                    break
> > > +            # A directory was created
> > > +            assert i > 0
> > > +            # The FAT16 root directory has only 512 directory entries
> > > +            assert i <= 512 / 5
> > > -- 
> > > 2.36.1
> > >