2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
4 * Copyright (C) 2002-2011 Aleph One Ltd.
5 * for Toby Churchill Ltd and Brightstar Engineering
7 * Created by Charles Manning <charles@aleph1.co.uk>
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
14 #include "yaffs_guts.h"
15 #include "yaffs_trace.h"
16 #include "yaffs_yaffs2.h"
17 #include "yaffs_checkptrw.h"
18 #include "yaffs_bitmap.h"
19 #include "yaffs_nand.h"
20 #include "yaffs_getblockinfo.h"
21 #include "yaffs_verify.h"
22 #include "yaffs_attribs.h"
23 #include "yaffs_summary.h"
26 * Checkpoints are really no benefit on very small partitions.
28 * To save space on small partitions don't bother with checkpoints unless
29 * the partition is at least this big.
31 #define YAFFS_CHECKPOINT_MIN_BLOCKS 60
32 #define YAFFS_SMALL_HOLE_THRESHOLD 4
35 * Oldest Dirty Sequence Number handling.
38 /* yaffs_calc_oldest_dirty_seq()
39 * yaffs2_find_oldest_dirty_seq()
40 * Calculate the oldest dirty sequence number if we don't know it.
42 void yaffs_calc_oldest_dirty_seq(struct yaffs_dev *dev)
46 unsigned block_no = 0;
47 struct yaffs_block_info *b;
49 if (!dev->param.is_yaffs2)
52 /* Find the oldest dirty sequence number. */
53 seq = dev->seq_number + 1;
55 for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) {
56 if (b->block_state == YAFFS_BLOCK_STATE_FULL &&
57 (b->pages_in_use - b->soft_del_pages) <
58 dev->param.chunks_per_block &&
59 b->seq_number < seq) {
67 dev->oldest_dirty_seq = seq;
68 dev->oldest_dirty_block = block_no;
72 void yaffs2_find_oldest_dirty_seq(struct yaffs_dev *dev)
74 if (!dev->param.is_yaffs2)
77 if (!dev->oldest_dirty_seq)
78 yaffs_calc_oldest_dirty_seq(dev);
82 * yaffs_clear_oldest_dirty_seq()
83 * Called when a block is erased or marked bad. (ie. when its seq_number
84 * becomes invalid). If the value matches the oldest then we clear
85 * dev->oldest_dirty_seq to force its recomputation.
87 void yaffs2_clear_oldest_dirty_seq(struct yaffs_dev *dev,
88 struct yaffs_block_info *bi)
91 if (!dev->param.is_yaffs2)
94 if (!bi || bi->seq_number == dev->oldest_dirty_seq) {
95 dev->oldest_dirty_seq = 0;
96 dev->oldest_dirty_block = 0;
101 * yaffs2_update_oldest_dirty_seq()
102 * Update the oldest dirty sequence number whenever we dirty a block.
103 * Only do this if the oldest_dirty_seq is actually being tracked.
105 void yaffs2_update_oldest_dirty_seq(struct yaffs_dev *dev, unsigned block_no,
106 struct yaffs_block_info *bi)
108 if (!dev->param.is_yaffs2)
111 if (dev->oldest_dirty_seq) {
112 if (dev->oldest_dirty_seq > bi->seq_number) {
113 dev->oldest_dirty_seq = bi->seq_number;
114 dev->oldest_dirty_block = block_no;
119 int yaffs_block_ok_for_gc(struct yaffs_dev *dev, struct yaffs_block_info *bi)
122 if (!dev->param.is_yaffs2)
123 return 1; /* disqualification only applies to yaffs2. */
125 if (!bi->has_shrink_hdr)
126 return 1; /* can gc */
128 yaffs2_find_oldest_dirty_seq(dev);
130 /* Can't do gc of this block if there are any blocks older than this
131 * one that have discarded pages.
133 return (bi->seq_number <= dev->oldest_dirty_seq);
137 * yaffs2_find_refresh_block()
138 * periodically finds the oldest full block by sequence number for refreshing.
141 u32 yaffs2_find_refresh_block(struct yaffs_dev *dev)
146 struct yaffs_block_info *bi;
148 if (!dev->param.is_yaffs2)
152 * If refresh period < 10 then refreshing is disabled.
154 if (dev->param.refresh_period < 10)
160 if (dev->refresh_skip > dev->param.refresh_period)
161 dev->refresh_skip = dev->param.refresh_period;
163 if (dev->refresh_skip > 0)
167 * Refresh skip is now zero.
168 * We'll do a refresh this time around....
169 * Update the refresh skip and find the oldest block.
171 dev->refresh_skip = dev->param.refresh_period;
172 dev->refresh_count++;
173 bi = dev->block_info;
174 for (b = dev->internal_start_block; b <= dev->internal_end_block; b++) {
176 if (bi->block_state == YAFFS_BLOCK_STATE_FULL) {
178 if (oldest < 1 || bi->seq_number < oldest_seq) {
180 oldest_seq = bi->seq_number;
187 yaffs_trace(YAFFS_TRACE_GC,
188 "GC refresh count %d selected block %d with seq_number %d",
189 dev->refresh_count, oldest, oldest_seq);
195 int yaffs2_checkpt_required(struct yaffs_dev *dev)
199 if (!dev->param.is_yaffs2)
202 nblocks = dev->internal_end_block - dev->internal_start_block + 1;
204 return !dev->param.skip_checkpt_wr &&
205 !dev->read_only && (nblocks >= YAFFS_CHECKPOINT_MIN_BLOCKS);
208 int yaffs_calc_checkpt_blocks_required(struct yaffs_dev *dev)
215 if (!dev->param.is_yaffs2)
218 if (!dev->checkpoint_blocks_required && yaffs2_checkpt_required(dev)) {
219 /* Not a valid value so recalculate */
220 dev_blocks = dev->param.end_block - dev->param.start_block + 1;
221 n_bytes += sizeof(struct yaffs_checkpt_validity);
222 n_bytes += sizeof(struct yaffs_checkpt_dev);
223 n_bytes += dev_blocks * sizeof(struct yaffs_block_info);
224 n_bytes += dev_blocks * dev->chunk_bit_stride;
226 (sizeof(struct yaffs_checkpt_obj) + sizeof(u32)) *
228 n_bytes += (dev->tnode_size + sizeof(u32)) * dev->n_tnodes;
229 n_bytes += sizeof(struct yaffs_checkpt_validity);
230 n_bytes += sizeof(u32); /* checksum */
232 /* Round up and add 2 blocks to allow for some bad blocks,
237 (dev->data_bytes_per_chunk *
238 dev->param.chunks_per_block)) + 3;
240 dev->checkpoint_blocks_required = n_blocks;
243 retval = dev->checkpoint_blocks_required - dev->blocks_in_checkpt;
249 /*--------------------- Checkpointing --------------------*/
251 static int yaffs2_wr_checkpt_validity_marker(struct yaffs_dev *dev, int head)
253 struct yaffs_checkpt_validity cp;
255 memset(&cp, 0, sizeof(cp));
257 cp.struct_type = sizeof(cp);
258 cp.magic = YAFFS_MAGIC;
259 cp.version = YAFFS_CHECKPOINT_VERSION;
260 cp.head = (head) ? 1 : 0;
262 return (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp)) ? 1 : 0;
265 static int yaffs2_rd_checkpt_validity_marker(struct yaffs_dev *dev, int head)
267 struct yaffs_checkpt_validity cp;
270 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
273 ok = (cp.struct_type == sizeof(cp)) &&
274 (cp.magic == YAFFS_MAGIC) &&
275 (cp.version == YAFFS_CHECKPOINT_VERSION) &&
276 (cp.head == ((head) ? 1 : 0));
280 static void yaffs2_dev_to_checkpt_dev(struct yaffs_checkpt_dev *cp,
281 struct yaffs_dev *dev)
283 cp->n_erased_blocks = dev->n_erased_blocks;
284 cp->alloc_block = dev->alloc_block;
285 cp->alloc_page = dev->alloc_page;
286 cp->n_free_chunks = dev->n_free_chunks;
288 cp->n_deleted_files = dev->n_deleted_files;
289 cp->n_unlinked_files = dev->n_unlinked_files;
290 cp->n_bg_deletions = dev->n_bg_deletions;
291 cp->seq_number = dev->seq_number;
295 static void yaffs_checkpt_dev_to_dev(struct yaffs_dev *dev,
296 struct yaffs_checkpt_dev *cp)
298 dev->n_erased_blocks = cp->n_erased_blocks;
299 dev->alloc_block = cp->alloc_block;
300 dev->alloc_page = cp->alloc_page;
301 dev->n_free_chunks = cp->n_free_chunks;
303 dev->n_deleted_files = cp->n_deleted_files;
304 dev->n_unlinked_files = cp->n_unlinked_files;
305 dev->n_bg_deletions = cp->n_bg_deletions;
306 dev->seq_number = cp->seq_number;
309 static int yaffs2_wr_checkpt_dev(struct yaffs_dev *dev)
311 struct yaffs_checkpt_dev cp;
313 u32 n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
316 /* Write device runtime values */
317 yaffs2_dev_to_checkpt_dev(&cp, dev);
318 cp.struct_type = sizeof(cp);
320 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
324 /* Write block info */
325 n_bytes = n_blocks * sizeof(struct yaffs_block_info);
326 ok = (yaffs2_checkpt_wr(dev, dev->block_info, n_bytes) == n_bytes);
330 /* Write chunk bits */
331 n_bytes = n_blocks * dev->chunk_bit_stride;
332 ok = (yaffs2_checkpt_wr(dev, dev->chunk_bits, n_bytes) == n_bytes);
337 static int yaffs2_rd_checkpt_dev(struct yaffs_dev *dev)
339 struct yaffs_checkpt_dev cp;
342 (dev->internal_end_block - dev->internal_start_block + 1);
345 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
349 if (cp.struct_type != sizeof(cp))
352 yaffs_checkpt_dev_to_dev(dev, &cp);
354 n_bytes = n_blocks * sizeof(struct yaffs_block_info);
356 ok = (yaffs2_checkpt_rd(dev, dev->block_info, n_bytes) == n_bytes);
361 n_bytes = n_blocks * dev->chunk_bit_stride;
363 ok = (yaffs2_checkpt_rd(dev, dev->chunk_bits, n_bytes) == n_bytes);
369 static void yaffs2_checkpt_obj_bit_assign(struct yaffs_checkpt_obj *cp,
376 and_mask = ((1<<bit_width)-1) << bit_offset;
378 cp->bit_field &= ~and_mask;
379 cp->bit_field |= ((value << bit_offset) & and_mask);
382 static u32 yaffs2_checkpt_obj_bit_get(struct yaffs_checkpt_obj *cp,
388 and_mask = ((1<<bit_width)-1);
390 return (cp->bit_field >> bit_offset) & and_mask;
393 static void yaffs2_obj_checkpt_obj(struct yaffs_checkpt_obj *cp,
394 struct yaffs_obj *obj)
396 cp->obj_id = obj->obj_id;
397 cp->parent_id = (obj->parent) ? obj->parent->obj_id : 0;
398 cp->hdr_chunk = obj->hdr_chunk;
400 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_VARIANT_BITS, obj->variant_type);
401 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_DELETED_BITS, obj->deleted);
402 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_SOFT_DEL_BITS, obj->soft_del);
403 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_UNLINKED_BITS, obj->unlinked);
404 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_FAKE_BITS, obj->fake);
405 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_RENAME_ALLOWED_BITS, obj->rename_allowed);
406 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_UNLINK_ALLOWED_BITS, obj->unlink_allowed);
407 yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_SERIAL_BITS, obj->serial);
409 cp->n_data_chunks = obj->n_data_chunks;
411 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
412 cp->size_or_equiv_obj = obj->variant.file_variant.file_size;
413 else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
414 cp->size_or_equiv_obj = obj->variant.hardlink_variant.equiv_id;
417 static int yaffs2_checkpt_obj_to_obj(struct yaffs_obj *obj,
418 struct yaffs_checkpt_obj *cp)
420 struct yaffs_obj *parent;
421 u32 cp_variant_type = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_VARIANT_BITS);
423 if (obj->variant_type != cp_variant_type) {
424 yaffs_trace(YAFFS_TRACE_ERROR,
425 "Checkpoint read object %d type %d chunk %d does not match existing object type %d",
426 cp->obj_id, cp_variant_type, cp->hdr_chunk,
431 obj->obj_id = cp->obj_id;
434 parent = yaffs_find_or_create_by_number(obj->my_dev,
436 YAFFS_OBJECT_TYPE_DIRECTORY);
441 if (parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
442 yaffs_trace(YAFFS_TRACE_ALWAYS,
443 "Checkpoint read object %d parent %d type %d chunk %d Parent type, %d, not directory",
444 cp->obj_id, cp->parent_id,
445 cp_variant_type, cp->hdr_chunk,
446 parent->variant_type);
449 yaffs_add_obj_to_dir(parent, obj);
452 obj->hdr_chunk = cp->hdr_chunk;
454 obj->variant_type = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_VARIANT_BITS);
455 obj->deleted = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_DELETED_BITS);
456 obj->soft_del = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_SOFT_DEL_BITS);
457 obj->unlinked = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_UNLINKED_BITS);
458 obj->fake = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_FAKE_BITS);
459 obj->rename_allowed = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_RENAME_ALLOWED_BITS);
460 obj->unlink_allowed = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_UNLINK_ALLOWED_BITS);
461 obj->serial = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_SERIAL_BITS);
463 obj->n_data_chunks = cp->n_data_chunks;
465 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE) {
466 obj->variant.file_variant.file_size = cp->size_or_equiv_obj;
467 obj->variant.file_variant.stored_size = cp->size_or_equiv_obj;
468 } else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK) {
469 obj->variant.hardlink_variant.equiv_id = cp->size_or_equiv_obj;
471 if (obj->hdr_chunk > 0)
472 obj->lazy_loaded = 1;
476 static int yaffs2_checkpt_tnode_worker(struct yaffs_obj *in,
477 struct yaffs_tnode *tn, u32 level,
481 struct yaffs_dev *dev = in->my_dev;
489 for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) {
490 if (!tn->internal[i])
492 ok = yaffs2_checkpt_tnode_worker(in,
496 YAFFS_TNODES_INTERNAL_BITS) + i);
502 base_offset = chunk_offset << YAFFS_TNODES_LEVEL0_BITS;
503 ok = (yaffs2_checkpt_wr(dev, &base_offset, sizeof(base_offset)) ==
504 sizeof(base_offset));
506 ok = (yaffs2_checkpt_wr(dev, tn, dev->tnode_size) ==
512 static int yaffs2_wr_checkpt_tnodes(struct yaffs_obj *obj)
517 if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
520 ok = yaffs2_checkpt_tnode_worker(obj,
521 obj->variant.file_variant.top,
522 obj->variant.file_variant.
525 ok = (yaffs2_checkpt_wr(obj->my_dev, &end_marker,
526 sizeof(end_marker)) == sizeof(end_marker));
531 static int yaffs2_rd_checkpt_tnodes(struct yaffs_obj *obj)
535 struct yaffs_dev *dev = obj->my_dev;
536 struct yaffs_file_var *file_stuct_ptr = &obj->variant.file_variant;
537 struct yaffs_tnode *tn;
540 ok = (yaffs2_checkpt_rd(dev, &base_chunk, sizeof(base_chunk)) ==
543 while (ok && (~base_chunk)) {
545 /* Read level 0 tnode */
547 tn = yaffs_get_tnode(dev);
549 ok = (yaffs2_checkpt_rd(dev, tn, dev->tnode_size) ==
555 ok = yaffs_add_find_tnode_0(dev,
557 base_chunk, tn) ? 1 : 0;
560 ok = (yaffs2_checkpt_rd
562 sizeof(base_chunk)) == sizeof(base_chunk));
565 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
566 "Checkpoint read tnodes %d records, last %d. ok %d",
567 nread, base_chunk, ok);
572 static int yaffs2_wr_checkpt_objs(struct yaffs_dev *dev)
574 struct yaffs_obj *obj;
575 struct yaffs_checkpt_obj cp;
578 struct list_head *lh;
581 /* Iterate through the objects in each hash entry,
582 * dumping them to the checkpointing stream.
585 for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
586 list_for_each(lh, &dev->obj_bucket[i].list) {
587 obj = list_entry(lh, struct yaffs_obj, hash_link);
588 if (!obj->defered_free) {
589 yaffs2_obj_checkpt_obj(&cp, obj);
590 cp.struct_type = sizeof(cp);
591 cp_variant_type = yaffs2_checkpt_obj_bit_get(
592 &cp, CHECKPOINT_VARIANT_BITS);
593 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
594 "Checkpoint write object %d parent %d type %d chunk %d obj addr %p",
595 cp.obj_id, cp.parent_id,
596 cp_variant_type, cp.hdr_chunk, obj);
598 ok = (yaffs2_checkpt_wr(dev, &cp,
599 sizeof(cp)) == sizeof(cp));
603 YAFFS_OBJECT_TYPE_FILE)
604 ok = yaffs2_wr_checkpt_tnodes(obj);
609 /* Dump end of list */
610 memset(&cp, 0xff, sizeof(struct yaffs_checkpt_obj));
611 cp.struct_type = sizeof(cp);
614 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
619 static int yaffs2_rd_checkpt_objs(struct yaffs_dev *dev)
621 struct yaffs_obj *obj;
622 struct yaffs_checkpt_obj cp;
626 LIST_HEAD(hard_list);
629 while (ok && !done) {
630 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
631 if (cp.struct_type != sizeof(cp)) {
632 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
633 "struct size %d instead of %d ok %d",
634 cp.struct_type, (int)sizeof(cp), ok);
638 cp_variant_type = yaffs2_checkpt_obj_bit_get(
639 &cp, CHECKPOINT_VARIANT_BITS);
640 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
641 "Checkpoint read object %d parent %d type %d chunk %d ",
642 cp.obj_id, cp.parent_id, cp_variant_type,
645 if (ok && cp.obj_id == ~0) {
649 yaffs_find_or_create_by_number(dev, cp.obj_id,
652 ok = yaffs2_checkpt_obj_to_obj(obj, &cp);
655 if (obj->variant_type ==
656 YAFFS_OBJECT_TYPE_FILE) {
657 ok = yaffs2_rd_checkpt_tnodes(obj);
658 } else if (obj->variant_type ==
659 YAFFS_OBJECT_TYPE_HARDLINK) {
660 list_add(&obj->hard_links, &hard_list);
669 yaffs_link_fixup(dev, &hard_list);
674 static int yaffs2_wr_checkpt_sum(struct yaffs_dev *dev)
679 yaffs2_get_checkpt_sum(dev, &checkpt_sum);
681 ok = (yaffs2_checkpt_wr(dev, &checkpt_sum, sizeof(checkpt_sum)) ==
682 sizeof(checkpt_sum));
690 static int yaffs2_rd_checkpt_sum(struct yaffs_dev *dev)
696 yaffs2_get_checkpt_sum(dev, &checkpt_sum0);
698 ok = (yaffs2_checkpt_rd(dev, &checkpt_sum1, sizeof(checkpt_sum1)) ==
699 sizeof(checkpt_sum1));
704 if (checkpt_sum0 != checkpt_sum1)
710 static int yaffs2_wr_checkpt_data(struct yaffs_dev *dev)
714 if (!yaffs2_checkpt_required(dev)) {
715 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
716 "skipping checkpoint write");
721 ok = yaffs2_checkpt_open(dev, 1);
724 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
725 "write checkpoint validity");
726 ok = yaffs2_wr_checkpt_validity_marker(dev, 1);
729 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
730 "write checkpoint device");
731 ok = yaffs2_wr_checkpt_dev(dev);
734 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
735 "write checkpoint objects");
736 ok = yaffs2_wr_checkpt_objs(dev);
739 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
740 "write checkpoint validity");
741 ok = yaffs2_wr_checkpt_validity_marker(dev, 0);
745 ok = yaffs2_wr_checkpt_sum(dev);
747 if (!yaffs_checkpt_close(dev))
751 dev->is_checkpointed = 1;
753 dev->is_checkpointed = 0;
755 return dev->is_checkpointed;
758 static int yaffs2_rd_checkpt_data(struct yaffs_dev *dev)
762 if (!dev->param.is_yaffs2)
765 if (ok && dev->param.skip_checkpt_rd) {
766 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
767 "skipping checkpoint read");
772 ok = yaffs2_checkpt_open(dev, 0); /* open for read */
775 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
776 "read checkpoint validity");
777 ok = yaffs2_rd_checkpt_validity_marker(dev, 1);
780 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
781 "read checkpoint device");
782 ok = yaffs2_rd_checkpt_dev(dev);
785 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
786 "read checkpoint objects");
787 ok = yaffs2_rd_checkpt_objs(dev);
790 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
791 "read checkpoint validity");
792 ok = yaffs2_rd_checkpt_validity_marker(dev, 0);
796 ok = yaffs2_rd_checkpt_sum(dev);
797 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
798 "read checkpoint checksum %d", ok);
801 if (!yaffs_checkpt_close(dev))
805 dev->is_checkpointed = 1;
807 dev->is_checkpointed = 0;
812 void yaffs2_checkpt_invalidate(struct yaffs_dev *dev)
814 if (dev->is_checkpointed || dev->blocks_in_checkpt > 0) {
815 dev->is_checkpointed = 0;
816 yaffs2_checkpt_invalidate_stream(dev);
818 if (dev->param.sb_dirty_fn)
819 dev->param.sb_dirty_fn(dev);
822 int yaffs_checkpoint_save(struct yaffs_dev *dev)
824 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
825 "save entry: is_checkpointed %d",
826 dev->is_checkpointed);
828 yaffs_verify_objects(dev);
829 yaffs_verify_blocks(dev);
830 yaffs_verify_free_chunks(dev);
832 if (!dev->is_checkpointed) {
833 yaffs2_checkpt_invalidate(dev);
834 yaffs2_wr_checkpt_data(dev);
837 yaffs_trace(YAFFS_TRACE_CHECKPOINT | YAFFS_TRACE_MOUNT,
838 "save exit: is_checkpointed %d",
839 dev->is_checkpointed);
841 return dev->is_checkpointed;
844 int yaffs2_checkpt_restore(struct yaffs_dev *dev)
848 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
849 "restore entry: is_checkpointed %d",
850 dev->is_checkpointed);
852 retval = yaffs2_rd_checkpt_data(dev);
854 if (dev->is_checkpointed) {
855 yaffs_verify_objects(dev);
856 yaffs_verify_blocks(dev);
857 yaffs_verify_free_chunks(dev);
860 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
861 "restore exit: is_checkpointed %d",
862 dev->is_checkpointed);
867 int yaffs2_handle_hole(struct yaffs_obj *obj, loff_t new_size)
869 /* if new_size > old_file_size.
870 * We're going to be writing a hole.
871 * If the hole is small then write zeros otherwise write a start
874 loff_t old_file_size;
877 int result = YAFFS_OK;
878 struct yaffs_dev *dev = NULL;
879 u8 *local_buffer = NULL;
880 int small_increase_ok = 0;
885 if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
890 /* Bail out if not yaffs2 mode */
891 if (!dev->param.is_yaffs2)
894 old_file_size = obj->variant.file_variant.file_size;
896 if (new_size <= old_file_size)
899 increase = new_size - old_file_size;
901 if (increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->data_bytes_per_chunk &&
902 yaffs_check_alloc_available(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
908 local_buffer = yaffs_get_temp_buffer(dev);
911 /* fill hole with zero bytes */
912 loff_t pos = old_file_size;
915 memset(local_buffer, 0, dev->data_bytes_per_chunk);
916 small_increase_ok = 1;
918 while (increase > 0 && small_increase_ok) {
919 this_write = increase;
920 if (this_write > dev->data_bytes_per_chunk)
921 this_write = dev->data_bytes_per_chunk;
923 yaffs_do_file_wr(obj, local_buffer, pos, this_write,
925 if (written == this_write) {
927 increase -= this_write;
929 small_increase_ok = 0;
933 yaffs_release_temp_buffer(dev, local_buffer);
935 /* If out of space then reverse any chunks we've added */
936 if (!small_increase_ok)
937 yaffs_resize_file_down(obj, old_file_size);
940 if (!small_increase_ok &&
942 obj->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
943 obj->parent->obj_id != YAFFS_OBJECTID_DELETED) {
944 /* Write a hole start header with the old file size */
945 yaffs_update_oh(obj, NULL, 0, 1, 0, NULL);
951 struct yaffs_block_index {
956 static int yaffs2_ybicmp(const void *a, const void *b)
958 int aseq = ((struct yaffs_block_index *)a)->seq;
959 int bseq = ((struct yaffs_block_index *)b)->seq;
960 int ablock = ((struct yaffs_block_index *)a)->block;
961 int bblock = ((struct yaffs_block_index *)b)->block;
964 return ablock - bblock;
969 static inline int yaffs2_scan_chunk(struct yaffs_dev *dev,
970 struct yaffs_block_info *bi,
971 int blk, int chunk_in_block,
974 struct list_head *hard_list,
975 int summary_available)
977 struct yaffs_obj_hdr *oh;
978 struct yaffs_obj *in;
979 struct yaffs_obj *parent;
984 struct yaffs_ext_tags tags;
986 int alloc_failed = 0;
987 int chunk = blk * dev->param.chunks_per_block + chunk_in_block;
988 struct yaffs_file_var *file_var;
989 struct yaffs_hardlink_var *hl_var;
990 struct yaffs_symlink_var *sl_var;
992 if (summary_available) {
993 result = yaffs_summary_fetch(dev, &tags, chunk_in_block);
994 tags.seq_number = bi->seq_number;
997 if (!summary_available || tags.obj_id == 0) {
998 result = yaffs_rd_chunk_tags_nand(dev, chunk, NULL, &tags);
1001 dev->summary_used++;
1004 /* Let's have a good look at this chunk... */
1006 if (!tags.chunk_used) {
1007 /* An unassigned chunk in the block.
1008 * If there are used chunks after this one, then
1009 * it is a chunk that was skipped due to failing
1010 * the erased check. Just skip it so that it can
1012 * But, more typically, We get here when this is
1013 * an unallocated chunk and his means that
1014 * either the block is empty or this is the one
1015 * being allocated from
1018 if (*found_chunks) {
1019 /* This is a chunk that was skipped due
1020 * to failing the erased check */
1021 } else if (chunk_in_block == 0) {
1022 /* We're looking at the first chunk in
1023 * the block so the block is unused */
1024 bi->block_state = YAFFS_BLOCK_STATE_EMPTY;
1025 dev->n_erased_blocks++;
1027 if (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
1028 bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING) {
1029 if (dev->seq_number == bi->seq_number) {
1030 /* Allocating from this block*/
1031 yaffs_trace(YAFFS_TRACE_SCAN,
1032 " Allocating from %d %d",
1033 blk, chunk_in_block);
1036 YAFFS_BLOCK_STATE_ALLOCATING;
1037 dev->alloc_block = blk;
1038 dev->alloc_page = chunk_in_block;
1039 dev->alloc_block_finder = blk;
1041 /* This is a partially written block
1042 * that is not the current
1045 yaffs_trace(YAFFS_TRACE_SCAN,
1046 "Partially written block %d detected. gc will fix this.",
1052 dev->n_free_chunks++;
1054 } else if (tags.ecc_result ==
1055 YAFFS_ECC_RESULT_UNFIXED) {
1056 yaffs_trace(YAFFS_TRACE_SCAN,
1057 " Unfixed ECC in chunk(%d:%d), chunk ignored",
1058 blk, chunk_in_block);
1059 dev->n_free_chunks++;
1060 } else if (tags.obj_id > YAFFS_MAX_OBJECT_ID ||
1061 tags.chunk_id > YAFFS_MAX_CHUNK_ID ||
1062 tags.obj_id == YAFFS_OBJECTID_SUMMARY ||
1063 (tags.chunk_id > 0 &&
1064 tags.n_bytes > dev->data_bytes_per_chunk) ||
1065 tags.seq_number != bi->seq_number) {
1066 yaffs_trace(YAFFS_TRACE_SCAN,
1067 "Chunk (%d:%d) with bad tags:obj = %d, chunk_id = %d, n_bytes = %d, ignored",
1068 blk, chunk_in_block, tags.obj_id,
1069 tags.chunk_id, tags.n_bytes);
1070 dev->n_free_chunks++;
1071 } else if (tags.chunk_id > 0) {
1072 /* chunk_id > 0 so it is a data chunk... */
1074 loff_t chunk_base = (tags.chunk_id - 1) *
1075 dev->data_bytes_per_chunk;
1079 yaffs_set_chunk_bit(dev, blk, chunk_in_block);
1082 in = yaffs_find_or_create_by_number(dev,
1084 YAFFS_OBJECT_TYPE_FILE);
1090 in->variant_type == YAFFS_OBJECT_TYPE_FILE &&
1091 chunk_base < in->variant.file_variant.shrink_size) {
1092 /* This has not been invalidated by
1094 if (!yaffs_put_chunk_in_file(in, tags.chunk_id,
1098 /* File size is calculated by looking at
1099 * the data chunks if we have not
1100 * seen an object header yet.
1101 * Stop this practice once we find an
1104 endpos = chunk_base + tags.n_bytes;
1107 in->variant.file_variant.stored_size < endpos) {
1108 in->variant.file_variant.
1109 stored_size = endpos;
1110 in->variant.file_variant.
1114 /* This chunk has been invalidated by a
1115 * resize, or a past file deletion
1116 * so delete the chunk*/
1117 yaffs_chunk_del(dev, chunk, 1, __LINE__);
1120 /* chunk_id == 0, so it is an ObjectHeader.
1121 * Thus, we read in the object header and make
1126 yaffs_set_chunk_bit(dev, blk, chunk_in_block);
1132 if (tags.extra_available) {
1133 in = yaffs_find_or_create_by_number(dev,
1135 tags.extra_obj_type);
1141 (!in->valid && dev->param.disable_lazy_load) ||
1142 tags.extra_shadows ||
1143 (!in->valid && (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1144 tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND))) {
1146 /* If we don't have valid info then we
1147 * need to read the chunk
1148 * TODO In future we can probably defer
1149 * reading the chunk and living with
1150 * invalid data until needed.
1153 result = yaffs_rd_chunk_tags_nand(dev,
1158 oh = (struct yaffs_obj_hdr *)chunk_data;
1160 if (dev->param.inband_tags) {
1161 /* Fix up the header if they got
1162 * corrupted by inband tags */
1164 oh->inband_shadowed_obj_id;
1166 oh->inband_is_shrink;
1170 in = yaffs_find_or_create_by_number(dev,
1171 tags.obj_id, oh->type);
1178 /* TODO Hoosterman we have a problem! */
1179 yaffs_trace(YAFFS_TRACE_ERROR,
1180 "yaffs tragedy: Could not make object for object %d at chunk %d during scan",
1181 tags.obj_id, chunk);
1186 /* We have already filled this one.
1187 * We have a duplicate that will be
1188 * discarded, but we first have to suck
1189 * out resize info if it is a file.
1191 if ((in->variant_type == YAFFS_OBJECT_TYPE_FILE) &&
1192 ((oh && oh->type == YAFFS_OBJECT_TYPE_FILE) ||
1193 (tags.extra_available &&
1194 tags.extra_obj_type == YAFFS_OBJECT_TYPE_FILE)
1196 loff_t this_size = (oh) ?
1197 yaffs_oh_to_size(oh) :
1198 tags.extra_file_size;
1199 u32 parent_obj_id = (oh) ?
1201 tags.extra_parent_id;
1205 tags.extra_is_shrink;
1207 /* If it is deleted (unlinked
1208 * at start also means deleted)
1209 * we treat the file size as
1210 * being zeroed at this point.
1212 if (parent_obj_id == YAFFS_OBJECTID_DELETED ||
1213 parent_obj_id == YAFFS_OBJECTID_UNLINKED) {
1219 in->variant.file_variant.shrink_size >
1221 in->variant.file_variant.shrink_size =
1225 bi->has_shrink_hdr = 1;
1227 /* Use existing - destroy this one. */
1228 yaffs_chunk_del(dev, chunk, 1, __LINE__);
1231 if (!in->valid && in->variant_type !=
1232 (oh ? oh->type : tags.extra_obj_type)) {
1233 yaffs_trace(YAFFS_TRACE_ERROR,
1234 "yaffs tragedy: Bad type, %d != %d, for object %d at chunk %d during scan",
1235 oh ? oh->type : tags.extra_obj_type,
1236 in->variant_type, tags.obj_id,
1238 in = yaffs_retype_obj(in, oh ? oh->type : tags.extra_obj_type);
1242 (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1243 tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND)) {
1244 /* We only load some info, don't fiddle
1245 * with directory structure */
1249 in->yst_mode = oh->yst_mode;
1250 yaffs_load_attribs(in, oh);
1251 in->lazy_loaded = 0;
1253 in->lazy_loaded = 1;
1255 in->hdr_chunk = chunk;
1257 } else if (!in->valid) {
1258 /* we need to load this info */
1260 in->hdr_chunk = chunk;
1262 in->variant_type = oh->type;
1263 in->yst_mode = oh->yst_mode;
1264 yaffs_load_attribs(in, oh);
1266 if (oh->shadows_obj > 0)
1267 yaffs_handle_shadowed_obj(dev,
1268 oh->shadows_obj, 1);
1270 yaffs_set_obj_name_from_oh(in, oh);
1271 parent = yaffs_find_or_create_by_number(dev,
1273 YAFFS_OBJECT_TYPE_DIRECTORY);
1274 file_size = yaffs_oh_to_size(oh);
1275 is_shrink = oh->is_shrink;
1276 equiv_id = oh->equiv_id;
1278 in->variant_type = tags.extra_obj_type;
1279 parent = yaffs_find_or_create_by_number(dev,
1280 tags.extra_parent_id,
1281 YAFFS_OBJECT_TYPE_DIRECTORY);
1282 file_size = tags.extra_file_size;
1283 is_shrink = tags.extra_is_shrink;
1284 equiv_id = tags.extra_equiv_id;
1285 in->lazy_loaded = 1;
1292 /* directory stuff...
1297 parent->variant_type == YAFFS_OBJECT_TYPE_UNKNOWN) {
1298 /* Set up as a directory */
1299 parent->variant_type =
1300 YAFFS_OBJECT_TYPE_DIRECTORY;
1301 INIT_LIST_HEAD(&parent->
1302 variant.dir_variant.children);
1303 } else if (!parent ||
1304 parent->variant_type !=
1305 YAFFS_OBJECT_TYPE_DIRECTORY) {
1306 /* Hoosterman, another problem....
1307 * Trying to use a non-directory as a directory
1310 yaffs_trace(YAFFS_TRACE_ERROR,
1311 "yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1313 parent = dev->lost_n_found;
1315 yaffs_add_obj_to_dir(parent, in);
1317 is_unlinked = (parent == dev->del_dir) ||
1318 (parent == dev->unlinked_dir);
1321 /* Mark the block */
1322 bi->has_shrink_hdr = 1;
1324 /* Note re hardlinks.
1325 * Since we might scan a hardlink before its equivalent
1326 * object is scanned we put them all in a list.
1327 * After scanning is complete, we should have all the
1328 * objects, so we run through this list and fix up all
1332 switch (in->variant_type) {
1333 case YAFFS_OBJECT_TYPE_UNKNOWN:
1334 /* Todo got a problem */
1336 case YAFFS_OBJECT_TYPE_FILE:
1337 file_var = &in->variant.file_variant;
1338 if (file_var->stored_size < file_size) {
1339 /* This covers the case where the file
1340 * size is greater than the data held.
1341 * This will happen if the file is
1342 * resized to be larger than its
1343 * current data extents.
1345 file_var->file_size = file_size;
1346 file_var->stored_size = file_size;
1349 if (file_var->shrink_size > file_size)
1350 file_var->shrink_size = file_size;
1353 case YAFFS_OBJECT_TYPE_HARDLINK:
1354 hl_var = &in->variant.hardlink_variant;
1356 hl_var->equiv_id = equiv_id;
1357 list_add(&in->hard_links, hard_list);
1360 case YAFFS_OBJECT_TYPE_DIRECTORY:
1363 case YAFFS_OBJECT_TYPE_SPECIAL:
1366 case YAFFS_OBJECT_TYPE_SYMLINK:
1367 sl_var = &in->variant.symlink_variant;
1370 yaffs_clone_str(oh->alias);
1378 return alloc_failed ? YAFFS_FAIL : YAFFS_OK;
1381 int yaffs2_scan_backwards(struct yaffs_dev *dev)
1388 enum yaffs_block_state state;
1390 LIST_HEAD(hard_list);
1391 struct yaffs_block_info *bi;
1393 int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
1396 int alloc_failed = 0;
1397 struct yaffs_block_index *block_index = NULL;
1398 int alt_block_index = 0;
1399 int summary_available;
1401 yaffs_trace(YAFFS_TRACE_SCAN,
1402 "yaffs2_scan_backwards starts intstartblk %d intendblk %d...",
1403 dev->internal_start_block, dev->internal_end_block);
1405 dev->seq_number = YAFFS_LOWEST_SEQUENCE_NUMBER;
1408 kmalloc(n_blocks * sizeof(struct yaffs_block_index), GFP_NOFS);
1412 vmalloc(n_blocks * sizeof(struct yaffs_block_index));
1413 alt_block_index = 1;
1417 yaffs_trace(YAFFS_TRACE_SCAN,
1418 "yaffs2_scan_backwards() could not allocate block index!"
1423 dev->blocks_in_checkpt = 0;
1425 chunk_data = yaffs_get_temp_buffer(dev);
1427 /* Scan all the blocks to determine their state */
1428 bi = dev->block_info;
1429 for (blk = dev->internal_start_block; blk <= dev->internal_end_block;
1431 yaffs_clear_chunk_bits(dev, blk);
1432 bi->pages_in_use = 0;
1433 bi->soft_del_pages = 0;
1435 yaffs_query_init_block_state(dev, blk, &state, &seq_number);
1437 bi->block_state = state;
1438 bi->seq_number = seq_number;
1440 if (bi->seq_number == YAFFS_SEQUENCE_CHECKPOINT_DATA)
1441 bi->block_state = YAFFS_BLOCK_STATE_CHECKPOINT;
1442 if (bi->seq_number == YAFFS_SEQUENCE_BAD_BLOCK)
1443 bi->block_state = YAFFS_BLOCK_STATE_DEAD;
1445 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG,
1446 "Block scanning block %d state %d seq %d",
1447 blk, bi->block_state, seq_number);
1449 if (bi->block_state == YAFFS_BLOCK_STATE_CHECKPOINT) {
1450 dev->blocks_in_checkpt++;
1452 } else if (bi->block_state == YAFFS_BLOCK_STATE_DEAD) {
1453 yaffs_trace(YAFFS_TRACE_BAD_BLOCKS,
1454 "block %d is bad", blk);
1455 } else if (bi->block_state == YAFFS_BLOCK_STATE_EMPTY) {
1456 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "Block empty ");
1457 dev->n_erased_blocks++;
1458 dev->n_free_chunks += dev->param.chunks_per_block;
1459 } else if (bi->block_state ==
1460 YAFFS_BLOCK_STATE_NEEDS_SCAN) {
1461 /* Determine the highest sequence number */
1462 if (seq_number >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1463 seq_number < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1464 block_index[n_to_scan].seq = seq_number;
1465 block_index[n_to_scan].block = blk;
1467 if (seq_number >= dev->seq_number)
1468 dev->seq_number = seq_number;
1470 /* TODO: Nasty sequence number! */
1471 yaffs_trace(YAFFS_TRACE_SCAN,
1472 "Block scanning block %d has bad sequence number %d",
1479 yaffs_trace(YAFFS_TRACE_ALWAYS, "%d blocks to be sorted...", n_to_scan);
1483 /* Sort the blocks by sequence number */
1484 sort(block_index, n_to_scan, sizeof(struct yaffs_block_index),
1485 yaffs2_ybicmp, NULL);
1489 yaffs_trace(YAFFS_TRACE_SCAN, "...done");
1491 /* Now scan the blocks looking at the data. */
1493 end_iter = n_to_scan - 1;
1494 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "%d blocks to scan", n_to_scan);
1496 /* For each block.... backwards */
1497 for (block_iter = end_iter;
1498 !alloc_failed && block_iter >= start_iter;
1500 /* Cooperative multitasking! This loop can run for so
1501 long that watchdog timers expire. */
1504 /* get the block to scan in the correct order */
1505 blk = block_index[block_iter].block;
1506 bi = yaffs_get_block_info(dev, blk);
1508 summary_available = yaffs_summary_read(dev, dev->sum_tags, blk);
1510 /* For each chunk in each block that needs scanning.... */
1512 if (summary_available)
1513 c = dev->chunks_per_summary - 1;
1515 c = dev->param.chunks_per_block - 1;
1517 for (/* c is already initialised */;
1518 !alloc_failed && c >= 0 &&
1519 (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
1520 bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING);
1522 /* Scan backwards...
1523 * Read the tags and decide what to do
1525 if (yaffs2_scan_chunk(dev, bi, blk, c,
1526 &found_chunks, chunk_data,
1527 &hard_list, summary_available) ==
1532 if (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN) {
1533 /* If we got this far while scanning, then the block
1534 * is fully allocated. */
1535 bi->block_state = YAFFS_BLOCK_STATE_FULL;
1538 /* Now let's see if it was dirty */
1539 if (bi->pages_in_use == 0 &&
1540 !bi->has_shrink_hdr &&
1541 bi->block_state == YAFFS_BLOCK_STATE_FULL) {
1542 yaffs_block_became_dirty(dev, blk);
1546 yaffs_skip_rest_of_block(dev);
1548 if (alt_block_index)
1553 /* Ok, we've done all the scanning.
1554 * Fix up the hard link chains.
1555 * We have scanned all the objects, now it's time to add these
1558 yaffs_link_fixup(dev, &hard_list);
1560 yaffs_release_temp_buffer(dev, chunk_data);
1565 yaffs_trace(YAFFS_TRACE_SCAN, "yaffs2_scan_backwards ends");