yaffs: Add first cut of block summary code
authorCharles Manning <cdhmanning@gmail.com>
Mon, 28 Mar 2011 17:57:02 +0000 (06:57 +1300)
committerCharles Manning <cdhmanning@gmail.com>
Mon, 28 Mar 2011 17:57:02 +0000 (06:57 +1300)
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>
direct/basic-test/Makefile
direct/basic-test/dtest.c
direct/tests/Makefile
yaffs_guts.c
yaffs_guts.h
yaffs_nand.c
yaffs_summary.c [new file with mode: 0644]
yaffs_summary.h [new file with mode: 0644]
yaffs_yaffs2.c

index 92891ae..afe0ef0 100644 (file)
@@ -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 \
index f8c6170..97e8fbe 100644 (file)
@@ -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;
        
index 76dcd2b..1389552 100644 (file)
@@ -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 \
index 109a0b7..24126a1 100644 (file)
@@ -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++) {
index 551fb7a..631bd65 100644 (file)
 #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;
index 0b59ec7..165d010 100644 (file)
 #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 (file)
index 0000000..04ef96b
--- /dev/null
@@ -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 (file)
index 0000000..e219745
--- /dev/null
@@ -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
index f4a7a7f..34c0bde 100644 (file)
@@ -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;
                }