yaffs: Add first cut of block summary code

Some issues still need to be checked. In particular:
* Is free space handling correct?
* Is gc doing The Right Thing?

Signed-off-by: Charles Manning <cdhmanning@gmail.com>

9 files changed, 291 insertions, 19 deletions

diff --git a/direct/basic-test/Makefile b/direct/basic-test/Makefile
index 92891ae..afe0ef0 100644
--- a/direct/basic-test/Makefile
+++ b/direct/basic-test/Makefile
@@ -44,7 +44,8 @@ COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o yaffs_hweight.o \
 		 yaffs_bitmap.o \
 		 yaffs_yaffs1.o \
 		 yaffs_yaffs2.o \
-		 yaffs_verify.o
+		 yaffs_verify.o \
+		 yaffs_summary.o
 
 #		 yaffs_checkptrwtest.o\
 
@@ -59,7 +60,8 @@ YAFFSSYMLINKS = yaffs_ecc.c yaffs_ecc.h yaffs_guts.c yaffs_guts.h yaffs_tagscomp
           yaffs_yaffs1.c yaffs_yaffs1.h \
           yaffs_yaffs2.c yaffs_yaffs2.h \
           yaffs_bitmap.c yaffs_bitmap.h \
-          yaffs_verify.c yaffs_verify.h
+          yaffs_verify.c yaffs_verify.h \
+          yaffs_summary.c yaffs_summary.h
 
 YAFFSDIRECTSYMLINKS =  yaffsfs.c yaffs_flashif.h yaffs_flashif2.h\
 		       yaffsfs.h yaffs_osglue.h ydirectenv.h \
diff --git a/direct/basic-test/dtest.c b/direct/basic-test/dtest.c
index f8c6170..97e8fbe 100644
--- a/direct/basic-test/dtest.c
+++ b/direct/basic-test/dtest.c
@@ -2775,7 +2775,7 @@ int main(int argc, char *argv[])
 	 //null_name_test("yaffs2");
 
 	 test_flash_traffic("yaffs2");
-	 link_follow_test("/yaffs2");
+	 // link_follow_test("/yaffs2");
 
 	 return 0;
 	
diff --git a/direct/tests/Makefile b/direct/tests/Makefile
index 76dcd2b..1389552 100644
--- a/direct/tests/Makefile
+++ b/direct/tests/Makefile
@@ -41,7 +41,8 @@ COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o yaffs_hweight.o\
 		 yaffs_bitmap.o \
 		 yaffs_yaffs1.o \
 		 yaffs_yaffs2.o \
-		 yaffs_verify.o
+		 yaffs_verify.o \
+		 yaffs_summary.o
 
 #		 yaffs_checkptrwtest.o\
 
@@ -60,7 +61,8 @@ YAFFSSYMLINKS = yaffs_ecc.c yaffs_ecc.h yaffs_guts.c yaffs_guts.h yaffs_tagscomp
           yaffs_yaffs1.c yaffs_yaffs1.h \
           yaffs_yaffs2.c yaffs_yaffs2.h \
           yaffs_bitmap.c yaffs_bitmap.h \
-          yaffs_verify.c yaffs_verify.h
+          yaffs_verify.c yaffs_verify.h \
+          yaffs_summary.c yaffs_summary.h
 
 YAFFSDIRECTSYMLINKS =  yaffsfs.c yaffs_flashif.h yaffs_flashif2.h\
 		       yaffsfs.h yaffs_osglue.h ydirectenv.h \
diff --git a/yaffs_guts.c b/yaffs_guts.c
index 109a0b7..24126a1 100644
--- a/yaffs_guts.c
+++ b/yaffs_guts.c
@@ -27,6 +27,7 @@
 #include "yaffs_nameval.h"
 #include "yaffs_allocator.h"
 #include "yaffs_attribs.h"
+#include "yaffs_summary.h"
 
 /* Note YAFFS_GC_GOOD_ENOUGH must be <= YAFFS_GC_PASSIVE_THRESHOLD */
 #define YAFFS_GC_GOOD_ENOUGH 2
@@ -4813,6 +4814,9 @@ int yaffs_guts_initialise(struct yaffs_dev *dev)
 	if (!init_failed && !yaffs_create_initial_dir(dev))
 		init_failed = 1;
 
+	if(!init_failed && dev->param.is_yaffs2 && !yaffs_summary_init(dev))
+		init_failed = 1;
+
 	if (!init_failed) {
 		/* Now scan the flash. */
 		if (dev->param.is_yaffs2) {
@@ -4898,6 +4902,8 @@ void yaffs_deinitialise(struct yaffs_dev *dev)
 
 		yaffs_deinit_blocks(dev);
 		yaffs_deinit_tnodes_and_objs(dev);
+		yaffs_summary_deinit(dev);
+
 		if (dev->param.n_caches > 0 && dev->cache) {
 
 			for (i = 0; i < dev->param.n_caches; i++) {
diff --git a/yaffs_guts.h b/yaffs_guts.h
index 551fb7a..631bd65 100644
--- a/yaffs_guts.h
+++ b/yaffs_guts.h
@@ -78,10 +78,12 @@
 #define YAFFS_OBJECTID_UNLINKED		3
 #define YAFFS_OBJECTID_DELETED		4
 
+/* Fake object Id for summary data */
+#define YAFFS_OBJECTID_SUMMARY		0x10
+
 /* Pseudo object ids for checkpointing */
-#define YAFFS_OBJECTID_SB_HEADER	0x10
 #define YAFFS_OBJECTID_CHECKPOINT_DATA	0x20
-#define YAFFS_SEQUENCE_CHECKPOINT_DATA  0x21
+#define YAFFS_SEQUENCE_CHECKPOINT_DATA	0x21
 
 #define YAFFS_MAX_SHORT_OP_CACHES	20
 
@@ -729,6 +731,10 @@ struct yaffs_dev {
 	/* Dirty directory handling */
 	struct list_head dirty_dirs;	/* List of dirty directories */
 
+	/* Summary */
+	int chunks_per_summary;
+	struct yaffs_summary_tags *sum_tags;
+
 	/* Statistcs */
 	u32 n_page_writes;
 	u32 n_page_reads;
diff --git a/yaffs_nand.c b/yaffs_nand.c
index 0b59ec7..165d010 100644
--- a/yaffs_nand.c
+++ b/yaffs_nand.c
@@ -15,13 +15,14 @@
 #include "yaffs_tagscompat.h"
 
 #include "yaffs_getblockinfo.h"
+#include "yaffs_summary.h"
 
 int yaffs_rd_chunk_tags_nand(struct yaffs_dev *dev, int nand_chunk,
 			     u8 *buffer, struct yaffs_ext_tags *tags)
 {
 	int result;
 	struct yaffs_ext_tags local_tags;
-	int realigned_chunk = nand_chunk - dev->chunk_offset;
+	int flash_chunk = nand_chunk - dev->chunk_offset;
 
 	dev->n_page_reads++;
 
@@ -31,11 +32,11 @@ int yaffs_rd_chunk_tags_nand(struct yaffs_dev *dev, int nand_chunk,
 
 	if (dev->param.read_chunk_tags_fn)
 		result =
-		    dev->param.read_chunk_tags_fn(dev, realigned_chunk, buffer,
+		    dev->param.read_chunk_tags_fn(dev, flash_chunk, buffer,
 						  tags);
 	else
 		result = yaffs_tags_compat_rd(dev,
-					      realigned_chunk, buffer, tags);
+					      flash_chunk, buffer, tags);
 	if (tags && tags->ecc_result > YAFFS_ECC_RESULT_NO_ERROR) {
 
 		struct yaffs_block_info *bi;
@@ -51,8 +52,10 @@ int yaffs_wr_chunk_tags_nand(struct yaffs_dev *dev,
 				int nand_chunk,
 				const u8 *buffer, struct yaffs_ext_tags *tags)
 {
+	int result;
+	int flash_chunk = nand_chunk - dev->chunk_offset;
+
 	dev->n_page_writes++;
-	nand_chunk -= dev->chunk_offset;
 
 	if (tags) {
 		tags->seq_number = dev->seq_number;
@@ -67,10 +70,14 @@ int yaffs_wr_chunk_tags_nand(struct yaffs_dev *dev,
 	}
 
 	if (dev->param.write_chunk_tags_fn)
-		return dev->param.write_chunk_tags_fn(dev, nand_chunk, buffer,
-							tags);
+		result = dev->param.write_chunk_tags_fn(dev, flash_chunk,
+							buffer, tags);
+	else
+		result = yaffs_tags_compat_wr(dev, flash_chunk, buffer, tags);
 
-	return yaffs_tags_compat_wr(dev, nand_chunk, buffer, tags);
+	yaffs_summary_add(dev, tags, nand_chunk);
+
+	return result;
 }
 
 int yaffs_mark_bad(struct yaffs_dev *dev, int block_no)
diff --git a/yaffs_summary.c b/yaffs_summary.c
new file mode 100644
index 0000000..04ef96b
--- /dev/null
+++ b/yaffs_summary.c
@@ -0,0 +1,198 @@
+/*
+ * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
+ *
+ * Copyright (C) 2002-2011 Aleph One Ltd.
+ *   for Toby Churchill Ltd and Brightstar Engineering
+ *
+ * Created by Charles Manning <charles@aleph1.co.uk>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+/* Summaries write all the tags for the chunks in a block into packed tags
+ * (just the tags part - no ECC) in the last n chunks of the block.
+ * Reading the summaries gives all the tags for the block in one read. Much
+ * faster.
+ *
+ * Chunks holding summaries are marked with tags making it look like
+ * they are part of a fake file.
+ */
+
+#include "yaffs_summary.h"
+#include "yaffs_packedtags2.h"
+#include "yaffs_nand.h"
+
+/* Summary tags don't need the sequence number becase that is redundant. */
+struct yaffs_summary_tags {
+	unsigned obj_id;
+	unsigned chunk_id;
+	unsigned n_bytes;
+};
+
+static void yaffs_summary_clear(struct yaffs_dev *dev)
+{
+	if(!dev->sum_tags)
+		return;
+	memset(dev->sum_tags, 0, dev->chunks_per_summary *
+		sizeof(struct yaffs_summary_tags));
+}
+
+int yaffs_summary_init(struct yaffs_dev *dev)
+{
+	struct yaffs_summary_tags *sum;
+	int sum_bytes;
+	int chunks_used; /* Number of chunks used by summary */
+
+	sum_bytes = dev->param.chunks_per_block *
+			sizeof(struct yaffs_summary_tags);
+
+	chunks_used = (sum_bytes + dev->data_bytes_per_chunk - 1)/
+			dev->data_bytes_per_chunk;
+	dev->chunks_per_summary = dev->param.chunks_per_block - chunks_used;
+	sum = kmalloc(sizeof(struct yaffs_summary_tags) *
+				dev->chunks_per_summary, GFP_NOFS);
+	if(!sum)
+		return YAFFS_FAIL;
+
+	dev->sum_tags = sum;
+	yaffs_summary_clear(dev);
+
+	return YAFFS_OK;
+}
+
+void yaffs_summary_deinit(struct yaffs_dev *dev)
+{
+	if(dev->sum_tags) {
+		kfree(dev->sum_tags);
+		dev->sum_tags = NULL;
+	}
+	dev->chunks_per_summary = 0;
+}
+
+static int yaffs_summary_write(struct yaffs_dev *dev)
+{
+	struct yaffs_ext_tags tags;
+	u8 *buffer;
+	u8 *sum_buffer = (u8 *)dev->sum_tags;
+	int n_bytes;
+	int chunk_in_nand;
+	int result;
+	int this_tx;
+
+	buffer = yaffs_get_temp_buffer(dev);
+	n_bytes = sizeof(struct yaffs_summary_tags) * dev->chunks_per_summary;
+	memset(&tags, 0, sizeof(struct yaffs_ext_tags));
+	tags.obj_id = YAFFS_OBJECTID_SUMMARY;
+	tags.chunk_id = 1;
+	chunk_in_nand = dev->alloc_block * dev->param.chunks_per_block +
+						dev-> chunks_per_summary;
+	do {
+		this_tx = n_bytes;
+		if (this_tx > dev->data_bytes_per_chunk)
+			this_tx = dev->data_bytes_per_chunk;
+		memcpy(buffer, sum_buffer, this_tx);
+		tags.n_bytes = this_tx;
+		result = yaffs_wr_chunk_tags_nand(dev, chunk_in_nand,
+						buffer, &tags);
+		n_bytes -= this_tx;
+		sum_buffer += this_tx;
+		chunk_in_nand++;
+		tags.chunk_id++;
+	} while (result == YAFFS_OK && n_bytes > 0);
+	yaffs_release_temp_buffer(dev, buffer);
+	return result;
+}
+
+int yaffs_summary_read(struct yaffs_dev *dev, int blk)
+{
+	struct yaffs_ext_tags tags;
+	u8 *buffer;
+	u8 *sum_buffer = (u8 *)dev->sum_tags;
+	int n_bytes;
+	int chunk_id;
+	int chunk_in_nand;
+	int result;
+	int this_tx;
+
+	buffer = yaffs_get_temp_buffer(dev);
+	n_bytes = sizeof(struct yaffs_summary_tags) * dev->chunks_per_summary;
+	chunk_in_nand = blk * dev->param.chunks_per_block +
+							dev->chunks_per_summary;
+	chunk_id = 1;
+	do {
+		this_tx = n_bytes;
+		if(this_tx > dev->data_bytes_per_chunk)
+			this_tx = dev->data_bytes_per_chunk;
+		result = yaffs_rd_chunk_tags_nand(dev, chunk_in_nand,
+						buffer, &tags);
+
+		if (tags.chunk_id != chunk_id ||
+			tags.obj_id != YAFFS_OBJECTID_SUMMARY ||
+			tags.chunk_used == 0 ||
+			tags.ecc_result > YAFFS_ECC_RESULT_FIXED ||
+			this_tx != tags.n_bytes)
+				result = YAFFS_FAIL;
+		if (result != YAFFS_OK)
+			break;
+
+		memcpy(sum_buffer, buffer, this_tx);
+		n_bytes -= this_tx;
+		sum_buffer += this_tx;
+		chunk_in_nand++;
+		chunk_id++;
+		dev->n_free_chunks--;
+	} while (result == YAFFS_OK && n_bytes > 0);
+	yaffs_release_temp_buffer(dev, buffer);
+	return result;
+}
+int yaffs_summary_add(struct yaffs_dev *dev,
+			struct yaffs_ext_tags *tags,
+			int chunk_in_nand)
+{
+	struct yaffs_packed_tags2_tags_only tags_only;
+	struct yaffs_summary_tags *sum_tags;
+	int chunk_in_block = chunk_in_nand % dev->param.chunks_per_block;
+
+	if(!dev->sum_tags)
+		return YAFFS_OK;
+
+	printf("Add summary for chunk %d tags (%d %d %d)",chunk_in_block,
+			tags->seq_number, tags->obj_id, tags->chunk_id);
+	if(chunk_in_block >= 0 && chunk_in_block < dev->chunks_per_summary) {
+		yaffs_pack_tags2_tags_only(&tags_only, tags);
+		sum_tags = &dev->sum_tags[chunk_in_block];
+		sum_tags->chunk_id = tags_only.chunk_id;
+		sum_tags->n_bytes = tags_only.n_bytes;
+		sum_tags->obj_id = tags_only.obj_id;
+		printf(" added %d %d %d", sum_tags->obj_id, sum_tags->chunk_id, sum_tags->n_bytes);
+
+		if(chunk_in_block == dev->chunks_per_summary - 1) {
+			printf(" Write summary");
+			/* Time to write out the summary */
+			yaffs_summary_write(dev);
+			yaffs_summary_clear(dev);
+			yaffs_skip_rest_of_block(dev);
+		}
+	}
+	printf("\n");
+	return YAFFS_OK;
+}
+
+int yaffs_summary_fetch(struct yaffs_dev *dev,
+			struct yaffs_ext_tags *tags,
+			int chunk_in_block)
+{
+	struct yaffs_packed_tags2_tags_only tags_only;
+	struct yaffs_summary_tags *sum_tags;
+	if(chunk_in_block >= 0 && chunk_in_block < dev->chunks_per_summary) {
+		sum_tags = &dev->sum_tags[chunk_in_block];
+		tags_only.chunk_id = sum_tags->chunk_id;
+		tags_only.n_bytes = sum_tags->n_bytes;
+		tags_only.obj_id = sum_tags->obj_id;
+		yaffs_unpack_tags2_tags_only(tags, &tags_only);
+		return YAFFS_OK;
+	}
+	return YAFFS_FAIL;
+}
diff --git a/yaffs_summary.h b/yaffs_summary.h
new file mode 100644
index 0000000..e219745
--- /dev/null
+++ b/yaffs_summary.h
@@ -0,0 +1,33 @@
+/*
+ * YAFFS: Yet another Flash File System . A NAND-flash specific file system.
+ *
+ * Copyright (C) 2002-2011 Aleph One Ltd.
+ *   for Toby Churchill Ltd and Brightstar Engineering
+ *
+ * Created by Charles Manning <charles@aleph1.co.uk>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 2.1 as
+ * published by the Free Software Foundation.
+ *
+ * Note: Only YAFFS headers are LGPL, YAFFS C code is covered by GPL.
+ */
+
+#ifndef __YAFFS_SUMMARY_H__
+#define __YAFFS_SUMMARY_H__
+
+#include "yaffs_packedtags2.h"
+
+
+int yaffs_summary_init(struct yaffs_dev *dev);
+void yaffs_summary_deinit(struct yaffs_dev *dev);
+
+int yaffs_summary_add(struct yaffs_dev *dev,
+			struct yaffs_ext_tags *tags,
+			int chunk_in_block);
+int yaffs_summary_fetch(struct yaffs_dev *dev,
+			struct yaffs_ext_tags *tags,
+			int chunk_in_block);
+int yaffs_summary_read(struct yaffs_dev *dev, int blk);
+
+#endif
diff --git a/yaffs_yaffs2.c b/yaffs_yaffs2.c
index f4a7a7f..34c0bde 100644
--- a/yaffs_yaffs2.c
+++ b/yaffs_yaffs2.c
@@ -20,6 +20,7 @@
 #include "yaffs_getblockinfo.h"
 #include "yaffs_verify.h"
 #include "yaffs_attribs.h"
+#include "yaffs_summary.h"
 
 /*
  * Checkpoints are really no benefit on very small partitions.
@@ -934,7 +935,8 @@ static inline int yaffs2_scan_chunk(struct yaffs_dev *dev,
 		int blk, int chunk_in_block,
 		int *found_chunks,
 		u8 *chunk_data,
-		struct list_head *hard_list)
+		struct list_head *hard_list,
+		int summary_available)
 {
 	struct yaffs_obj_hdr *oh;
 	struct yaffs_obj *in;
@@ -951,7 +953,13 @@ static inline int yaffs2_scan_chunk(struct yaffs_dev *dev,
 	struct yaffs_hardlink_var *hl_var;
 	struct yaffs_symlink_var *sl_var;
 
-	result = yaffs_rd_chunk_tags_nand(dev, chunk, NULL, &tags);
+	if (summary_available) {
+		result = yaffs_summary_fetch(dev, &tags, chunk_in_block);
+		tags.seq_number = bi->seq_number;
+	}
+	
+	if (!summary_available || tags.obj_id == 0)
+		result = yaffs_rd_chunk_tags_nand(dev, chunk, NULL, &tags);
 
 	/* Let's have a good look at this chunk... */
 
@@ -1346,6 +1354,7 @@ int yaffs2_scan_backwards(struct yaffs_dev *dev)
 	int alloc_failed = 0;
 	struct yaffs_block_index *block_index = NULL;
 	int alt_block_index = 0;
+	int summary_available;
 
 	yaffs_trace(YAFFS_TRACE_SCAN,
 		"yaffs2_scan_backwards starts  intstartblk %d intendblk %d...",
@@ -1455,18 +1464,27 @@ int yaffs2_scan_backwards(struct yaffs_dev *dev)
 		bi = yaffs_get_block_info(dev, blk);
 		deleted = 0;
 
+		summary_available = yaffs_summary_read(dev, blk);
+
 		/* For each chunk in each block that needs scanning.... */
 		found_chunks = 0;
-		for (c = dev->param.chunks_per_block - 1;
+		if(summary_available)
+			c = dev->chunks_per_summary - 1;
+		else
+			c = dev->param.chunks_per_block - 1;
+
+		for (/* c is already initialised */;
 		     !alloc_failed && c >= 0 &&
 		     (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
-		      bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
+		      bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING);
+		      c--) {
 			/* Scan backwards...
 			 * Read the tags and decide what to do
 			 */
 			if (yaffs2_scan_chunk(dev, bi, blk, c,
 					&found_chunks, chunk_data,
-					&hard_list) == YAFFS_FAIL)
+					&hard_list, summary_available) ==
+					YAFFS_FAIL)
 				alloc_failed = 1;
 		}