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.schucha...@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