altos: Add a simple cache for the FAT position->cluster computation

This improves read/write performance with large files by not
re-walking the cluster chain for every operation

Signed-off-by: Keith Packard <keithp@keithp.com>

2 files changed, 88 insertions, 71 deletions

diff --git a/src/drivers/ao_fat.c b/src/drivers/ao_fat.c
index c0412380..65c5ea7c 100644
--- a/src/drivers/ao_fat.c
+++ b/src/drivers/ao_fat.c
@@ -136,7 +136,6 @@ ao_fat_entry_read(uint16_t cluster)
 	if (!ao_fat_cluster_valid(cluster))
 		return 0xfff7;
 
-//	cluster -= 2;
 	sector = cluster >> (SECTOR_SHIFT - 1);
 	offset = (cluster << 1) & SECTOR_MASK;
 	buf = ao_fat_sector_get(fat_start + sector);
@@ -162,7 +161,6 @@ ao_fat_entry_replace(uint16_t  cluster, uint16_t new_value)
 	if (!ao_fat_cluster_valid(cluster))
 		return 0;
 
-//	cluster -= 2;
 	sector = cluster >> (SECTOR_SHIFT - 1);
 	offset = (cluster << 1) & SECTOR_MASK;
 	buf = ao_fat_sector_get(fat_start + sector);
@@ -203,8 +201,11 @@ ao_fat_free_cluster_chain(uint16_t cluster)
 /*
  * ao_fat_cluster_seek
  * 
- * Walk a cluster chain the specified distance and return what we find
- * there. If distance is zero, return the provided cluster.
+ * The basic file system operation -- map a file cluster index to a
+ * partition cluster number. Done by computing the cluster number and
+ * then walking that many clusters from the first cluster. Returns
+ * 0xffff if we walk off the end of the file or the cluster chain
+ * is damaged somehow
  */
 static uint16_t
 ao_fat_cluster_seek(uint16_t cluster, uint16_t distance)
@@ -219,34 +220,6 @@ ao_fat_cluster_seek(uint16_t cluster, uint16_t distance)
 }
 
 /*
- * ao_fat_sector_seek
- *
- * The basic file system operation -- map a file sector number to a
- * partition sector number. Done by computing the cluster number and
- * then walking that many clusters from the first cluster, then
- * adding the sector offset from the start of the cluster. Returns
- * 0xffffffff if we walk off the end of the file or the cluster chain
- * is damaged somehow
- */
-static uint32_t
-ao_fat_sector_seek(uint16_t cluster, uint32_t sector)
-{
-	uint16_t	distance;
-	uint16_t	offset;
-
-	distance = sector / sectors_per_cluster;
-	offset = sector % sectors_per_cluster;
-
-	cluster = ao_fat_cluster_seek(cluster, distance);
-
-	if (!ao_fat_cluster_valid(cluster))
-		return 0xffffffff;
-
-	/* Compute the sector within the partition and return it */
-	return data_start + (uint32_t) (cluster-2) * sectors_per_cluster + offset;
-}
-
-/*
  * ao_fat_setup_partition
  * 
  * Load the boot block and find the first partition
@@ -385,14 +358,51 @@ ao_fat_setup(void)
 
 static struct ao_fat_dirent	ao_file_dirent;
 static uint32_t 		ao_file_offset;
+static uint32_t			ao_file_cluster_offset;
+static uint16_t			ao_file_cluster;
 static uint8_t			ao_file_opened;
 
 static uint32_t
-ao_fat_offset_to_sector(uint32_t offset)
+ao_fat_current_sector(void)
 {
-	if (offset > ao_file_dirent.size)
+	uint16_t	cluster_offset;
+	uint32_t	sector_offset;
+	uint16_t	sector_index;
+	uint16_t	cluster;
+
+	if (ao_file_offset > ao_file_dirent.size)
 		return 0xffffffff;
-	return ao_fat_sector_seek(ao_file_dirent.cluster, offset >> SECTOR_SHIFT);
+
+	sector_offset = ao_file_offset >> SECTOR_SHIFT;
+
+	if (!ao_file_cluster) {
+		cluster_offset = sector_offset / sectors_per_cluster;
+
+		cluster = ao_fat_cluster_seek(ao_file_dirent.cluster, cluster_offset);
+		if (!ao_fat_cluster_valid(cluster))
+			return 0xffffffff;
+		ao_file_cluster = cluster;
+		ao_file_cluster_offset = cluster_offset * bytes_per_cluster;
+	}
+
+	sector_index = sector_offset % sectors_per_cluster;
+	return data_start + (uint32_t) (ao_file_cluster-2) * sectors_per_cluster + sector_index;
+}
+
+static void
+ao_fat_set_offset(uint32_t offset)
+{
+	
+	if (offset == 0) {
+		ao_file_cluster = ao_file_dirent.cluster;
+		ao_file_cluster_offset = 0;
+	}
+	else if (offset < ao_file_cluster_offset ||
+	    ao_file_cluster_offset + bytes_per_cluster <= offset)
+	{
+		ao_file_cluster = 0;
+	}
+	ao_file_offset = offset;
 }
 
 /*
@@ -576,7 +586,7 @@ ao_fat_open(char name[11], uint8_t mode)
 			if (mode > AO_FAT_OPEN_READ && (dirent.attr & AO_FAT_FILE_READ_ONLY))
 				return -AO_FAT_EACCESS;
 			ao_file_dirent = dirent;
-			ao_file_offset = 0;
+			ao_fat_set_offset(0);
 			ao_file_opened = 1;
 			return AO_FAT_SUCCESS;
 		}
@@ -620,6 +630,7 @@ ao_fat_creat(char name[11])
 				ao_fat_dirent_init(dent, entry,  &ao_file_dirent);
 				ao_fat_root_put(dent, entry, 1);
 				ao_file_opened = 1;
+				ao_fat_set_offset(0);
 				status = -AO_FAT_SUCCESS;
 				break;
 			} else {
@@ -645,6 +656,7 @@ ao_fat_close(void)
 
 	memset(&ao_file_dirent, '\0', sizeof (struct ao_fat_dirent));
 	ao_file_offset = 0;
+	ao_file_cluster = 0;
 	ao_file_opened = 0;
 	ao_bufio_flush();
 	return AO_FAT_SUCCESS;
@@ -681,7 +693,7 @@ ao_fat_read(void *dst, int len)
 		else
 			this_time = SECTOR_SIZE - offset;
 
-		sector = ao_fat_offset_to_sector(ao_file_offset);
+		sector = ao_fat_current_sector();
 		if (sector == 0xffffffff)
 			break;
 		buf = ao_fat_sector_get(sector);
@@ -695,7 +707,7 @@ ao_fat_read(void *dst, int len)
 		ret += this_time;
 		len -= this_time;
 		dst_b += this_time;
-		ao_file_offset += this_time;
+		ao_fat_set_offset(ao_file_offset + this_time);
 	}
 	return ret;
 }
@@ -731,7 +743,7 @@ ao_fat_write(void *src, int len)
 		else
 			this_time = SECTOR_SIZE - offset;
 
-		sector = ao_fat_offset_to_sector(ao_file_offset);
+		sector = ao_fat_current_sector();
 		if (sector == 0xffffffff)
 			break;
 		buf = ao_fat_sector_get(sector);
@@ -745,7 +757,7 @@ ao_fat_write(void *src, int len)
 		ret += this_time;
 		len -= this_time;
 		src_b += this_time;
-		ao_file_offset += this_time;
+		ao_fat_set_offset(ao_file_offset + this_time);
 	}
 	return ret;
 }
@@ -762,20 +774,23 @@ ao_fat_write(void *src, int len)
 int32_t
 ao_fat_seek(int32_t pos, uint8_t whence)
 {
+	uint32_t	new_offset = ao_file_offset;
+
 	if (!ao_file_opened)
 		return -AO_FAT_EBADF;
 
 	switch (whence) {
 	case AO_FAT_SEEK_SET:
-		ao_file_offset = pos;
+		new_offset = pos;
 		break;
 	case AO_FAT_SEEK_CUR:
-		ao_file_offset += pos;
+		new_offset += pos;
 		break;
 	case AO_FAT_SEEK_END:
-		ao_file_offset = ao_file_dirent.size + pos;
+		new_offset = ao_file_dirent.size + pos;
 		break;
 	}
+	ao_fat_set_offset(new_offset);
 	return ao_file_offset;
 }
 
diff --git a/src/test/ao_fat_test.c b/src/test/ao_fat_test.c
index 3f947034..fffd5af4 100644
--- a/src/test/ao_fat_test.c
+++ b/src/test/ao_fat_test.c
@@ -261,12 +261,17 @@ check_fs(void)
 		}
 
 		clusters = check_file(r, first_cluster, used);
-		if (size > clusters * bytes_per_cluster)
-			fatal("file %d: size %u beyond clusters %d (%u)\n",
-			      r, size, clusters, clusters * bytes_per_cluster);
-		if (size <= (clusters - 1) * bytes_per_cluster)
-			fatal("file %d: size %u too small clusters %d (%u)\n",
-			      r, size, clusters, clusters * bytes_per_cluster);
+		if (size == 0) {
+			if (clusters != 0)
+				fatal("file %d: zero sized, but %d clusters\n", clusters);
+		} else {
+			if (size > clusters * bytes_per_cluster)
+				fatal("file %d: size %u beyond clusters %d (%u)\n",
+				      r, size, clusters, clusters * bytes_per_cluster);
+			if (size <= (clusters - 1) * bytes_per_cluster)
+				fatal("file %d: size %u too small clusters %d (%u)\n",
+				      r, size, clusters, clusters * bytes_per_cluster);
+		}
 	}
 	for (; r < root_entries; r++) {
 		uint8_t	*dent = ao_fat_root_get(r);
@@ -296,8 +301,8 @@ check_fs(void)
 	}
 }
 
-#define NUM_FILES	512
-#define LINES_FILE	1000
+#define NUM_FILES	10
+#define LINES_FILE	80000
 
 uint32_t		sizes[NUM_FILES];
 
@@ -330,22 +335,20 @@ main(int argc, char **argv)
 			char	line[64];
 			check_bufio("file created");
 			MD5_Init(&ctx);
-			for (j = 0; j < 1000; j++) {
-				int len;
+			for (j = 0; j < LINES_FILE; j++) {
+				int len, ret;
 				sprintf (line, "Hello, world %d %d\r\n", id, j);
 				len = strlen(line);
-				ao_fat_write((uint8_t *) line, len);
-				MD5_Update(&ctx, line, len);
-				sizes[id] += len;
+				ret = ao_fat_write((uint8_t *) line, len);
+				if (ret <= 0)
+					break;
+				MD5_Update(&ctx, line, ret);
+				sizes[id] += ret;
+				if (ret != len)
+					printf ("write failed %d\n", ret);
 			}
 			ao_fat_close();
 			MD5_Final(&md5[id][0], &ctx);
-			if (id == 0) {
-				printf ("MD5 write %d:", id);
-				for (j = 0; j < MD5_DIGEST_LENGTH; j++)
-					printf(" %02x", md5[id][j]);
-				printf ("\n");
-			}
 			check_bufio("file written");
 		}
 	}
@@ -357,26 +360,25 @@ main(int argc, char **argv)
 	printf ("   **** Comparing %d files\n", NUM_FILES);
 
 	for (id = 0; id < NUM_FILES; id++) {
-		char	buf[337];
+		char buf[337];
+		uint32_t size;
 		sprintf(name, "D%07dTXT", id);
+		size = 0;
 		if (ao_fat_open(name, AO_FAT_OPEN_READ) == AO_FAT_SUCCESS) {
 			int	len;
 
 			MD5_Init(&ctx);
 			while ((len = ao_fat_read((uint8_t *) buf, sizeof(buf))) > 0) {
 				MD5_Update(&ctx, buf, len);
+				size += len;
 			}
 			ao_fat_close();
 			MD5_Final(md5_check, &ctx);
-			if (id == 0) {
-				int j;
-				printf ("MD5 read %d:", id);
-				for (j = 0; j < MD5_DIGEST_LENGTH; j++)
-					printf(" %02x", md5_check[j]);
-				printf ("\n");
-			}
+			if (size != sizes[id])
+				fatal("file %d: size differs %d written %d read\n",
+				      id, sizes[id], size);
 			if (memcmp(md5_check, &md5[id][0], sizeof (md5_check)) != 0)
-				fatal ("checksum failed file %d\n", id);
+				fatal ("file %d: checksum failed\n", id);
 			check_bufio("file shown");
 		}
 	}