From 1570788072c1154eff93282e0bb8564de40bd8aa Mon Sep 17 00:00:00 2001 From: Charles Manning Date: Tue, 29 Mar 2011 06:57:02 +1300 Subject: [PATCH] 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 --- direct/basic-test/Makefile | 6 +- direct/basic-test/dtest.c | 2 +- direct/tests/Makefile | 6 +- yaffs_guts.c | 6 ++ yaffs_guts.h | 10 +- yaffs_nand.c | 21 ++-- yaffs_summary.c | 198 +++++++++++++++++++++++++++++++++++++ yaffs_summary.h | 33 +++++++ yaffs_yaffs2.c | 28 +++++- 9 files changed, 291 insertions(+), 19 deletions(-) create mode 100644 yaffs_summary.c create mode 100644 yaffs_summary.h 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 + * + * 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 + * + * 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; } -- 2.30.2