Fix FAT block caching

Fix FAT block caching

[Sascha Hauer]

The FAT driver has to access the file allocation table and also the
data on the device. This case hasn't been covered by the current
block caching mechanism. For this reason the FAT driver cached the
file allocation table itself. Due to some bugs the file allocation
table in the cache and on the device can get out of sync. A quite
simple way to trigger this is to create a directory and unmount
the filesystem afterwards. The directory will not be written to
disk. This series fixes this by reverting the FAT internal caching
mechanism and instead extend the block caching layer to cover
this case.

Sascha Hauer (3):
      list: add list_last_entry function
      fat: revert fat caching mechanism
      block: reimplement caching

 common/block.c       |  274 ++++++++++++++++++++++++++++++++++++-------------
 fs/fat/ff.c          |   93 ++++-------------
 include/block.h      |   16 ++--
 include/linux/list.h |   11 ++
 4 files changed, 241 insertions(+), 153 deletions(-)

_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

[PATCH 1/3] list: add list_last_entry function

[Sascha Hauer]

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
 include/linux/list.h |   11 +++++++++++
 1 files changed, 11 insertions(+), 0 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 1a4cbc4..15ed499 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -272,6 +272,17 @@ static inline void list_splice_init(struct list_head *list,
 	list_entry((ptr)->next, type, member)
 
 /**
+ * list_last_entry - get the last element from a list
+ * @head: the list head to take the element from.
+ * @type: the type of the struct this is embedded in.
+ * @member: the name of the list_struct within the struct.
+ *
+ * Note, that list is expected to be not empty.
+ */
+#define list_last_entry(head, type, member) \
+	list_entry((head)->prev, type, member)
+
+/**
  * list_for_each	-	iterate over a list
  * @pos:	the &struct list_head to use as a loop cursor.
  * @head:	the head for your list.
-- 
1.7.9


_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

[PATCH 2/3] fat: revert fat caching mechanism

[Sascha Hauer]

There seems to be a bug in this mechanism. It's easy to
get the cached fat out of sync with the device. Revert
it for now. This includes a huge write performance drop.

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
 fs/fat/ff.c |   93 ++++++++++++----------------------------------------------
 1 files changed, 20 insertions(+), 73 deletions(-)

diff --git a/fs/fat/ff.c b/fs/fat/ff.c
index 0087e21..a720389 100644
--- a/fs/fat/ff.c
+++ b/fs/fat/ff.c
@@ -234,89 +234,38 @@ struct fat_sector {
 	unsigned char data[0];
 };
 
-#ifdef CONFIG_FS_FAT_WRITE
-static int push_fat_sector(FATFS *fs, DWORD sector)
-{
-	struct fat_sector *s;
-
-	list_for_each_entry(s, &fs->dirtylist, list) {
-		if (s->sector == sector) {
-			memcpy(s->data, fs->win, SS(fs));
-			return 0;
-		}
-	}
-
-	s = xmalloc(sizeof(*s) + SS(fs));
-	memcpy(s->data, fs->win, SS(fs));
-	s->sector = sector;
-	list_add_tail(&s->list, &fs->dirtylist);
-
-	return 0;
-}
-#endif
-
-static int get_fat_sector(FATFS *fs, DWORD sector)
-{
-	struct fat_sector *s;
-
-	list_for_each_entry(s, &fs->dirtylist, list) {
-		if (s->sector == sector) {
-			memcpy(fs->win, s->data, SS(fs));
-			return 0;
-		}
-	}
-
-	return disk_read(fs, fs->win, sector, 1);
-}
+/*-----------------------------------------------------------------------*/
+/* Change window offset                                                  */
+/*-----------------------------------------------------------------------*/
 
-#ifdef CONFIG_FS_FAT_WRITE
-static int flush_dirty_fat(FATFS *fs)
-{
-	struct fat_sector *s, *tmp;
-
-	list_for_each_entry_safe(s, tmp, &fs->dirtylist, list) {
-		disk_write(fs, s->data, s->sector, 1);
-		if (s->sector < (fs->fatbase + fs->fsize)) {
-			/* In FAT area */
-			BYTE nf;
-			DWORD wsect = s->sector;
-			/* Reflect the change to all FAT copies */
-			for (nf = fs->n_fats; nf > 1; nf--) {
-				wsect += fs->fsize;
-				disk_write(fs, s->data, wsect, 1);
-			}
-		}
-		list_del(&s->list);
-		free(s);
-	}
-
-	return 0;
-}
-#endif
-
-static int move_window (
-	FATFS *fs,	/* File system object */
+static
+int move_window (
+	FATFS *fs,		/* File system object */
 	DWORD sector	/* Sector number to make appearance in the fs->win[] */
-)			/* Move to zero only writes back dirty window */
+)					/* Move to zero only writes back dirty window */
 {
 	DWORD wsect;
-	int ret;
+
 
 	wsect = fs->winsect;
 	if (wsect != sector) {	/* Changed current window */
 #ifdef CONFIG_FS_FAT_WRITE
-		/* Write back dirty window if needed */
-		if (fs->wflag) {
-			ret = push_fat_sector(fs, wsect);
-			if (ret)
-				return ret;
+		if (fs->wflag) {	/* Write back dirty window if needed */
+			if (disk_write(fs, fs->win, wsect, 1) != RES_OK)
+				return -EIO;
 			fs->wflag = 0;
+			if (wsect < (fs->fatbase + fs->fsize)) {	/* In FAT area */
+				BYTE nf;
+				for (nf = fs->n_fats; nf > 1; nf--) {	/* Reflect the change to all FAT copies */
+					wsect += fs->fsize;
+					disk_write(fs, fs->win, wsect, 1);
+				}
+			}
 		}
 #endif
 		if (sector) {
-			ret = get_fat_sector(fs, sector);
-			if (ret)
-				return ret;
+			if (disk_read(fs, fs->win, sector, 1) != RES_OK)
+				return -EIO;
 			fs->winsect = sector;
 		}
 	}
@@ -2091,8 +2040,6 @@ int f_sync (
 	fp->fs->wflag = 1;
 	res = sync(fp->fs);
 
-	flush_dirty_fat(fp->fs);
-
 	return res;
 }
 
-- 
1.7.9


_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

[PATCH 3/3] block: reimplement caching

[Sascha Hauer]

The current caching layer only has a single buffer for
writing and reading. The FAT driver often accesses the
fat and then data again, which currently can't be cached.
Reimplement this with a list of cached chunks. The number
of chunks and their sizes are currently hardcoded, but
that could be easily made configurable.

Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
 common/block.c  |  274 ++++++++++++++++++++++++++++++++++++++++---------------
 include/block.h |   16 ++--
 2 files changed, 210 insertions(+), 80 deletions(-)

diff --git a/common/block.c b/common/block.c
index 24377c6..4253fc4 100644
--- a/common/block.c
+++ b/common/block.c
@@ -21,89 +21,161 @@
  */
 #include <common.h>
 #include <block.h>
+#include <malloc.h>
 #include <linux/err.h>
+#include <linux/list.h>
 
 #define BLOCKSIZE(blk)	(1 << blk->blockbits)
 
-#define WRBUFFER_LAST(blk)	(blk->wrblock + blk->wrbufblocks - 1)
+/* a chunk of contigous data */
+struct chunk {
+	void *data; /* data buffer */
+	int block_start; /* first block in this chunk */
+	int dirty; /* need to write back to device */
+	int num; /* number of chunk, debugging only */
+	struct list_head list;
+};
 
-#ifdef CONFIG_BLOCK_WRITE
+#define BUFSIZE (PAGE_SIZE * 16)
+
+/*
+ * Write all dirty chunks back to the device
+ */
 static int writebuffer_flush(struct block_device *blk)
 {
-	if (!blk->wrbufblocks)
-		return 0;
+	struct chunk *chunk;
 
-	blk->ops->write(blk, blk->wrbuf, blk->wrblock,
-			blk->wrbufblocks);
-
-	blk->wrbufblocks = 0;
+	list_for_each_entry(chunk, &blk->buffered_blocks, list) {
+		if (chunk->dirty) {
+			blk->ops->write(blk, chunk->data, chunk->block_start, blk->rdbufsize);
+			chunk->dirty = 0;
+		}
+	}
 
 	return 0;
 }
 
-static int block_put(struct block_device *blk, const void *buf, int block)
+/*
+ * get the chunk containing a given block. Will return NULL if the
+ * block is not cached, the chunk otherwise.
+ */
+static struct chunk *chunk_get_cached(struct block_device *blk, int block)
 {
-	if (block >= blk->num_blocks)
-		return -EIO;
-
-	if (block < blk->wrblock || block > blk->wrblock + blk->wrbufblocks) {
-		writebuffer_flush(blk);
+	struct chunk *chunk;
+
+	list_for_each_entry(chunk, &blk->buffered_blocks, list) {
+		if (block >= chunk->block_start &&
+				block < chunk->block_start + blk->rdbufsize) {
+			debug("%s: found %d in %d\n", __func__, block, chunk->num);
+			/*
+			 * move most recently used entry to the head of the list
+			 */
+			list_move(&chunk->list, &blk->buffered_blocks);
+			return chunk;
+		}
 	}
 
-	if (blk->wrbufblocks == 0) {
-		blk->wrblock = block;
-		blk->wrbufblocks = 1;
-	}
+	return NULL;
+}
+
+/*
+ * Get the data pointer for a given block. Will return NULL if
+ * the block is not cached, the data pointer otherwise.
+ */
+static void *block_get_cached(struct block_device *blk, int block)
+{
+	struct chunk *chunk;
 
-	memcpy(blk->wrbuf + (block - blk->wrblock) * BLOCKSIZE(blk),
-			buf, BLOCKSIZE(blk));
+	chunk = chunk_get_cached(blk, block);
+	if (!chunk)
+		return NULL;
 
-	if (block > WRBUFFER_LAST(blk))
-		blk->wrbufblocks++;
+	return chunk->data + (block - chunk->block_start) * BLOCKSIZE(blk);
+}
 
-	if (blk->wrbufblocks == blk->wrbufsize)
-		writebuffer_flush(blk);
+/*
+ * Get a data chunk, either from the idle list or if the idle list
+ * is empty, the least recently used is written back to disk and
+ * returned.
+ */
+static struct chunk *get_chunk(struct block_device *blk)
+{
+	struct chunk *chunk;
+
+	if (list_empty(&blk->idle_blocks)) {
+		/* use last entry which is the most unused */
+		chunk = list_last_entry(&blk->buffered_blocks, struct chunk, list);
+		if (chunk->dirty) {
+			size_t num_blocks = min(blk->rdbufsize,
+					blk->num_blocks - chunk->block_start);
+			blk->ops->write(blk, chunk->data, chunk->block_start,
+					num_blocks);
+			chunk->dirty = 0;
+		}
+
+		list_del(&chunk->list);
+	} else {
+		chunk = list_first_entry(&blk->idle_blocks, struct chunk, list);
+		list_del(&chunk->list);
+	}
 
-	return 0;
+	return chunk;
 }
 
-#else
-static int writebuffer_flush(struct block_device *blk)
+/*
+ * read a block into the cache. This assumes that the block is
+ * not cached already. By definition block_get_cached() for
+ * the same block will succeed after this call.
+ */
+static int block_cache(struct block_device *blk, int block)
 {
+	struct chunk *chunk;
+	size_t num_blocks;
+	int ret;
+
+	chunk = get_chunk(blk);
+	chunk->block_start = block & ~blk->blkmask;
+
+	debug("%s: %d to %d %s\n", __func__, chunk->block_start,
+			chunk->num);
+
+	num_blocks = min(blk->rdbufsize, blk->num_blocks - chunk->block_start);
+
+	ret = blk->ops->read(blk, chunk->data, chunk->block_start, num_blocks);
+	if (ret) {
+		list_add_tail(&chunk->list, &blk->idle_blocks);
+		return ret;
+	}
+	list_add(&chunk->list, &blk->buffered_blocks);
+
 	return 0;
 }
-#endif
 
+/*
+ * Get the data for a block, either from the cache or from
+ * the device.
+ */
 static void *block_get(struct block_device *blk, int block)
 {
+	void *outdata;
 	int ret;
-	int num_blocks;
 
 	if (block >= blk->num_blocks)
-		return ERR_PTR(-EIO);
-
-	/* first look into write buffer */
-	if (block >= blk->wrblock && block <= WRBUFFER_LAST(blk))
-		return blk->wrbuf + (block - blk->wrblock) * BLOCKSIZE(blk);
+		return NULL;
 
-	/* then look into read buffer */
-	if (block >= blk->rdblock && block <= blk->rdblockend)
-		return blk->rdbuf + (block - blk->rdblock) * BLOCKSIZE(blk);
+	outdata = block_get_cached(blk, block);
+	if (outdata)
+		return outdata;
 
-	/*
-	 * If none of the buffers above match read the block from
-	 * the device
-	 */
-	num_blocks = min(blk->rdbufsize, blk->num_blocks - block);
-
-	ret = blk->ops->read(blk, blk->rdbuf, block, num_blocks);
+	ret = block_cache(blk, block);
 	if (ret)
-		return ERR_PTR(ret);
+		return NULL;
 
-	blk->rdblock = block;
-	blk->rdblockend = block + num_blocks - 1;
+	outdata = block_get_cached(blk, block);
+	if (!outdata)
+		BUG();
 
-	return blk->rdbuf;
+	return outdata;
 }
 
 static ssize_t block_read(struct cdev *cdev, void *buf, size_t count,
@@ -119,10 +191,10 @@ static ssize_t block_read(struct cdev *cdev, void *buf, size_t count,
 		size_t now = BLOCKSIZE(blk) - (offset & mask);
 		void *iobuf = block_get(blk, block);
 
-		now = min(count, now);
+		if (!iobuf)
+			return -EIO;
 
-		if (IS_ERR(iobuf))
-			return PTR_ERR(iobuf);
+		now = min(count, now);
 
 		memcpy(buf, iobuf + (offset & mask), now);
 		buf += now;
@@ -135,8 +207,8 @@ static ssize_t block_read(struct cdev *cdev, void *buf, size_t count,
 	while (blocks) {
 		void *iobuf = block_get(blk, block);
 
-		if (IS_ERR(iobuf))
-			return PTR_ERR(iobuf);
+		if (!iobuf)
+			return -EIO;
 
 		memcpy(buf, iobuf, BLOCKSIZE(blk));
 		buf += BLOCKSIZE(blk);
@@ -148,8 +220,8 @@ static ssize_t block_read(struct cdev *cdev, void *buf, size_t count,
 	if (count) {
 		void *iobuf = block_get(blk, block);
 
-		if (IS_ERR(iobuf))
-			return PTR_ERR(iobuf);
+		if (!iobuf)
+			return -EIO;
 
 		memcpy(buf, iobuf, count);
 	}
@@ -158,6 +230,31 @@ static ssize_t block_read(struct cdev *cdev, void *buf, size_t count,
 }
 
 #ifdef CONFIG_BLOCK_WRITE
+
+/*
+ * Put data into a block. This only overwrites the data in the
+ * cache and marks the corresponding chunk as dirty.
+ */
+static int block_put(struct block_device *blk, const void *buf, int block)
+{
+	struct chunk *chunk;
+	void *data;
+
+	if (block >= blk->num_blocks)
+		return -EINVAL;
+
+	data = block_get(blk, block);
+	if (!data)
+		BUG();
+
+	memcpy(data, buf, 1 << blk->blockbits);
+
+	chunk = chunk_get_cached(blk, block);
+	chunk->dirty = 1;
+
+	return 0;
+}
+
 static ssize_t block_write(struct cdev *cdev, const void *buf, size_t count,
 		unsigned long offset, ulong flags)
 {
@@ -165,7 +262,7 @@ static ssize_t block_write(struct cdev *cdev, const void *buf, size_t count,
 	unsigned long mask = BLOCKSIZE(blk) - 1;
 	unsigned long block = offset >> blk->blockbits;
 	size_t icount = count;
-	int blocks;
+	int blocks, ret;
 
 	if (offset & mask) {
 		size_t now = BLOCKSIZE(blk) - (offset & mask);
@@ -173,11 +270,14 @@ static ssize_t block_write(struct cdev *cdev, const void *buf, size_t count,
 
 		now = min(count, now);
 
-		if (IS_ERR(iobuf))
-			return PTR_ERR(iobuf);
+		if (!iobuf)
+			return -EIO;
 
 		memcpy(iobuf + (offset & mask), buf, now);
-		block_put(blk, iobuf, block);
+		ret = block_put(blk, iobuf, block);
+		if (ret)
+			return ret;
+
 		buf += now;
 		count -= now;
 		block++;
@@ -186,7 +286,10 @@ static ssize_t block_write(struct cdev *cdev, const void *buf, size_t count,
 	blocks = count >> blk->blockbits;
 
 	while (blocks) {
-		block_put(blk, buf, block);
+		ret = block_put(blk, buf, block);
+		if (ret)
+			return ret;
+
 		buf += BLOCKSIZE(blk);
 		blocks--;
 		block++;
@@ -196,11 +299,13 @@ static ssize_t block_write(struct cdev *cdev, const void *buf, size_t count,
 	if (count) {
 		void *iobuf = block_get(blk, block);
 
-		if (IS_ERR(iobuf))
-			return PTR_ERR(iobuf);
+		if (!iobuf)
+			return -EIO;
 
 		memcpy(iobuf, buf, count);
-		block_put(blk, iobuf, block);
+		ret = block_put(blk, iobuf, block);
+		if (ret)
+			return ret;
 	}
 
 	return icount;
@@ -221,7 +326,7 @@ static int block_flush(struct cdev *cdev)
 	return writebuffer_flush(blk);
 }
 
-struct file_operations block_ops = {
+static struct file_operations block_ops = {
 	.read	= block_read,
 #ifdef CONFIG_BLOCK_WRITE
 	.write	= block_write,
@@ -235,19 +340,27 @@ int blockdevice_register(struct block_device *blk)
 {
 	size_t size = blk->num_blocks * BLOCKSIZE(blk);
 	int ret;
+	int i;
 
 	blk->cdev.size = size;
 	blk->cdev.dev = blk->dev;
 	blk->cdev.ops = &block_ops;
 	blk->cdev.priv = blk;
-	blk->rdbufsize = PAGE_SIZE >> blk->blockbits;
-	blk->rdbuf = xmalloc(PAGE_SIZE);
-	blk->rdblock = 1;
-	blk->rdblockend = 0;
-	blk->wrbufsize = PAGE_SIZE >> blk->blockbits;
-	blk->wrbuf = xmalloc(PAGE_SIZE);
-	blk->wrblock = 0;
-	blk->wrbufblocks = 0;
+	blk->rdbufsize = BUFSIZE >> blk->blockbits;
+
+	INIT_LIST_HEAD(&blk->buffered_blocks);
+	INIT_LIST_HEAD(&blk->idle_blocks);
+	blk->blkmask = blk->rdbufsize - 1;
+
+	debug("%s: rdbufsize: %d blockbits: %d blkmask: 0x%08x\n", __func__, blk->rdbufsize, blk->blockbits,
+			blk->blkmask);
+
+	for (i = 0; i < 8; i++) {
+		struct chunk *chunk = xzalloc(sizeof(*chunk));
+		chunk->data = xmalloc(BUFSIZE);
+		chunk->num = i;
+		list_add_tail(&chunk->list, &blk->idle_blocks);
+	}
 
 	ret = devfs_create(&blk->cdev);
 	if (ret)
@@ -258,6 +371,21 @@ int blockdevice_register(struct block_device *blk)
 
 int blockdevice_unregister(struct block_device *blk)
 {
+	struct chunk *chunk, *tmp;
+
+	writebuffer_flush(blk);
+
+	list_for_each_entry_safe(chunk, tmp, &blk->buffered_blocks, list) {
+		free(chunk->data);
+		free(chunk);
+	}
+
+	list_for_each_entry_safe(chunk, tmp, &blk->idle_blocks, list) {
+		free(chunk->data);
+		free(chunk);
+	}
+
+	devfs_remove(&blk->cdev);
+
 	return 0;
 }
-
diff --git a/include/block.h b/include/block.h
index aaab4e3..cfa4cb9 100644
--- a/include/block.h
+++ b/include/block.h
@@ -8,21 +8,23 @@ struct block_device;
 struct block_device_ops {
 	int (*read)(struct block_device *, void *buf, int block, int num_blocks);
 	int (*write)(struct block_device *, const void *buf, int block, int num_blocks);
+	int (*read_start)(struct block_device *, void *buf, int block, int num_blocks);
+	int (*read_done)(struct block_device *);
 };
 
+struct chunk;
+
 struct block_device {
 	struct device_d *dev;
 	struct block_device_ops *ops;
 	int blockbits;
 	int num_blocks;
-	void *rdbuf; /* read buffer */
 	int rdbufsize;
-	int rdblock; /* start block in read buffer */
-	int rdblockend; /* end block in read buffer */
-	void *wrbuf; /* write buffer */
-	int wrblock; /* start block in write buffer */
-	int wrbufblocks; /* number of blocks currently in write buffer */
-	int wrbufsize; /* size of write buffer in blocks */
+	int blkmask;
+
+	struct list_head buffered_blocks;
+	struct list_head idle_blocks;
+
 	struct cdev cdev;
 };
 
-- 
1.7.9


_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox