2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
4 * Copyright (C) 2002-2010 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"
25 * Checkpoints are really no benefit on very small partitions.
27 * To save space on small partitions don't bother with checkpoints unless
28 * the partition is at least this big.
30 #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 && b->seq_number < seq) {
66 dev->oldest_dirty_seq = seq;
67 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 one that have
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)
148 struct yaffs_block_info *bi;
150 if (!dev->param.is_yaffs2)
154 * If refresh period < 10 then refreshing is disabled.
156 if (dev->param.refresh_period < 10)
162 if (dev->refresh_skip > dev->param.refresh_period)
163 dev->refresh_skip = dev->param.refresh_period;
165 if (dev->refresh_skip > 0)
169 * Refresh skip is now zero.
170 * We'll do a refresh this time around....
171 * Update the refresh skip and find the oldest block.
173 dev->refresh_skip = dev->param.refresh_period;
174 dev->refresh_count++;
175 bi = dev->block_info;
176 for (b = dev->internal_start_block; b <= dev->internal_end_block; b++) {
178 if (bi->block_state == YAFFS_BLOCK_STATE_FULL) {
180 if (oldest < 1 || bi->seq_number < oldest_seq) {
182 oldest_seq = bi->seq_number;
189 yaffs_trace(YAFFS_TRACE_GC,
190 "GC refresh count %d selected block %d with seq_number %d",
191 dev->refresh_count, oldest, oldest_seq);
197 int yaffs2_checkpt_required(struct yaffs_dev *dev)
201 if (!dev->param.is_yaffs2)
204 nblocks = dev->internal_end_block - dev->internal_start_block + 1;
206 return !dev->param.skip_checkpt_wr &&
207 !dev->read_only && (nblocks >= YAFFS_CHECKPOINT_MIN_BLOCKS);
210 int yaffs_calc_checkpt_blocks_required(struct yaffs_dev *dev)
214 if (!dev->param.is_yaffs2)
217 if (!dev->checkpoint_blocks_required && yaffs2_checkpt_required(dev)) {
218 /* Not a valid value so recalculate */
222 (dev->param.end_block - dev->param.start_block + 1);
224 n_bytes += sizeof(struct yaffs_checkpt_validity);
225 n_bytes += sizeof(struct yaffs_checkpt_dev);
226 n_bytes += dev_blocks * sizeof(struct yaffs_block_info);
227 n_bytes += dev_blocks * dev->chunk_bit_stride;
229 (sizeof(struct yaffs_checkpt_obj) +
230 sizeof(u32)) * (dev->n_obj);
231 n_bytes += (dev->tnode_size + sizeof(u32)) * (dev->n_tnodes);
232 n_bytes += sizeof(struct yaffs_checkpt_validity);
233 n_bytes += sizeof(u32); /* checksum */
235 /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
239 (dev->data_bytes_per_chunk *
240 dev->param.chunks_per_block)) + 3;
242 dev->checkpoint_blocks_required = n_blocks;
245 retval = dev->checkpoint_blocks_required - dev->blocks_in_checkpt;
251 /*--------------------- Checkpointing --------------------*/
253 static int yaffs2_wr_checkpt_validity_marker(struct yaffs_dev *dev, int head)
255 struct yaffs_checkpt_validity cp;
257 memset(&cp, 0, sizeof(cp));
259 cp.struct_type = sizeof(cp);
260 cp.magic = YAFFS_MAGIC;
261 cp.version = YAFFS_CHECKPOINT_VERSION;
262 cp.head = (head) ? 1 : 0;
264 return (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp)) ? 1 : 0;
267 static int yaffs2_rd_checkpt_validity_marker(struct yaffs_dev *dev, int head)
269 struct yaffs_checkpt_validity cp;
272 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
275 ok = (cp.struct_type == sizeof(cp)) &&
276 (cp.magic == YAFFS_MAGIC) &&
277 (cp.version == YAFFS_CHECKPOINT_VERSION) &&
278 (cp.head == ((head) ? 1 : 0));
282 static void yaffs2_dev_to_checkpt_dev(struct yaffs_checkpt_dev *cp,
283 struct yaffs_dev *dev)
285 cp->n_erased_blocks = dev->n_erased_blocks;
286 cp->alloc_block = dev->alloc_block;
287 cp->alloc_page = dev->alloc_page;
288 cp->n_free_chunks = dev->n_free_chunks;
290 cp->n_deleted_files = dev->n_deleted_files;
291 cp->n_unlinked_files = dev->n_unlinked_files;
292 cp->n_bg_deletions = dev->n_bg_deletions;
293 cp->seq_number = dev->seq_number;
297 static void yaffs_checkpt_dev_to_dev(struct yaffs_dev *dev,
298 struct yaffs_checkpt_dev *cp)
300 dev->n_erased_blocks = cp->n_erased_blocks;
301 dev->alloc_block = cp->alloc_block;
302 dev->alloc_page = cp->alloc_page;
303 dev->n_free_chunks = cp->n_free_chunks;
305 dev->n_deleted_files = cp->n_deleted_files;
306 dev->n_unlinked_files = cp->n_unlinked_files;
307 dev->n_bg_deletions = cp->n_bg_deletions;
308 dev->seq_number = cp->seq_number;
311 static int yaffs2_wr_checkpt_dev(struct yaffs_dev *dev)
313 struct yaffs_checkpt_dev cp;
316 (dev->internal_end_block - dev->internal_start_block + 1);
320 /* Write device runtime values */
321 yaffs2_dev_to_checkpt_dev(&cp, dev);
322 cp.struct_type = sizeof(cp);
324 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
326 /* Write block info */
328 n_bytes = n_blocks * sizeof(struct yaffs_block_info);
329 ok = (yaffs2_checkpt_wr(dev, dev->block_info, n_bytes) ==
333 /* Write chunk bits */
335 n_bytes = n_blocks * dev->chunk_bit_stride;
336 ok = (yaffs2_checkpt_wr(dev, dev->chunk_bits, n_bytes) ==
343 static int yaffs2_rd_checkpt_dev(struct yaffs_dev *dev)
345 struct yaffs_checkpt_dev cp;
348 (dev->internal_end_block - dev->internal_start_block + 1);
352 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
356 if (cp.struct_type != sizeof(cp))
359 yaffs_checkpt_dev_to_dev(dev, &cp);
361 n_bytes = n_blocks * sizeof(struct yaffs_block_info);
363 ok = (yaffs2_checkpt_rd(dev, dev->block_info, n_bytes) == n_bytes);
367 n_bytes = n_blocks * dev->chunk_bit_stride;
369 ok = (yaffs2_checkpt_rd(dev, dev->chunk_bits, n_bytes) == n_bytes);
374 static void yaffs2_obj_checkpt_obj(struct yaffs_checkpt_obj *cp,
375 struct yaffs_obj *obj)
378 cp->obj_id = obj->obj_id;
379 cp->parent_id = (obj->parent) ? obj->parent->obj_id : 0;
380 cp->hdr_chunk = obj->hdr_chunk;
381 cp->variant_type = obj->variant_type;
382 cp->deleted = obj->deleted;
383 cp->soft_del = obj->soft_del;
384 cp->unlinked = obj->unlinked;
385 cp->fake = obj->fake;
386 cp->rename_allowed = obj->rename_allowed;
387 cp->unlink_allowed = obj->unlink_allowed;
388 cp->serial = obj->serial;
389 cp->n_data_chunks = obj->n_data_chunks;
391 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
392 cp->size_or_equiv_obj = obj->variant.file_variant.file_size;
393 else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
394 cp->size_or_equiv_obj = obj->variant.hardlink_variant.equiv_id;
397 static int taffs2_checkpt_obj_to_obj(struct yaffs_obj *obj,
398 struct yaffs_checkpt_obj *cp)
401 struct yaffs_obj *parent;
403 if (obj->variant_type != cp->variant_type) {
404 yaffs_trace(YAFFS_TRACE_ERROR,
405 "Checkpoint read object %d type %d chunk %d does not match existing object type %d",
406 cp->obj_id, cp->variant_type, cp->hdr_chunk,
411 obj->obj_id = cp->obj_id;
414 parent = yaffs_find_or_create_by_number(obj->my_dev,
416 YAFFS_OBJECT_TYPE_DIRECTORY);
421 if (parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
422 yaffs_trace(YAFFS_TRACE_ALWAYS,
423 "Checkpoint read object %d parent %d type %d chunk %d Parent type, %d, not directory",
424 cp->obj_id, cp->parent_id,
425 cp->variant_type, cp->hdr_chunk,
426 parent->variant_type);
429 yaffs_add_obj_to_dir(parent, obj);
432 obj->hdr_chunk = cp->hdr_chunk;
433 obj->variant_type = cp->variant_type;
434 obj->deleted = cp->deleted;
435 obj->soft_del = cp->soft_del;
436 obj->unlinked = cp->unlinked;
437 obj->fake = cp->fake;
438 obj->rename_allowed = cp->rename_allowed;
439 obj->unlink_allowed = cp->unlink_allowed;
440 obj->serial = cp->serial;
441 obj->n_data_chunks = cp->n_data_chunks;
443 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
444 obj->variant.file_variant.file_size = cp->size_or_equiv_obj;
445 else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
446 obj->variant.hardlink_variant.equiv_id = cp->size_or_equiv_obj;
448 if (obj->hdr_chunk > 0)
449 obj->lazy_loaded = 1;
453 static int yaffs2_checkpt_tnode_worker(struct yaffs_obj *in,
454 struct yaffs_tnode *tn, u32 level,
458 struct yaffs_dev *dev = in->my_dev;
464 for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) {
465 if (tn->internal[i]) {
466 ok = yaffs2_checkpt_tnode_worker(in,
474 YAFFS_TNODES_INTERNAL_BITS)
478 } else if (level == 0) {
480 chunk_offset << YAFFS_TNODES_LEVEL0_BITS;
481 ok = (yaffs2_checkpt_wr
483 sizeof(base_offset)) == sizeof(base_offset));
485 ok = (yaffs2_checkpt_wr
487 dev->tnode_size) == dev->tnode_size);
495 static int yaffs2_wr_checkpt_tnodes(struct yaffs_obj *obj)
500 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE) {
501 ok = yaffs2_checkpt_tnode_worker(obj,
502 obj->variant.file_variant.top,
503 obj->variant.file_variant.
506 ok = (yaffs2_checkpt_wr
507 (obj->my_dev, &end_marker,
508 sizeof(end_marker)) == sizeof(end_marker));
514 static int yaffs2_rd_checkpt_tnodes(struct yaffs_obj *obj)
518 struct yaffs_dev *dev = obj->my_dev;
519 struct yaffs_file_var *file_stuct_ptr = &obj->variant.file_variant;
520 struct yaffs_tnode *tn;
523 ok = (yaffs2_checkpt_rd(dev, &base_chunk, sizeof(base_chunk)) ==
526 while (ok && (~base_chunk)) {
528 /* Read level 0 tnode */
530 tn = yaffs_get_tnode(dev);
532 ok = (yaffs2_checkpt_rd(dev, tn, dev->tnode_size) ==
539 ok = yaffs_add_find_tnode_0(dev,
541 base_chunk, tn) ? 1 : 0;
544 ok = (yaffs2_checkpt_rd
546 sizeof(base_chunk)) == sizeof(base_chunk));
550 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
551 "Checkpoint read tnodes %d records, last %d. ok %d",
552 nread, base_chunk, ok);
557 static int yaffs2_wr_checkpt_objs(struct yaffs_dev *dev)
559 struct yaffs_obj *obj;
560 struct yaffs_checkpt_obj cp;
563 struct list_head *lh;
565 /* Iterate through the objects in each hash entry,
566 * dumping them to the checkpointing stream.
569 for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
570 list_for_each(lh, &dev->obj_bucket[i].list) {
573 list_entry(lh, struct yaffs_obj, hash_link);
574 if (!obj->defered_free) {
575 yaffs2_obj_checkpt_obj(&cp, obj);
576 cp.struct_type = sizeof(cp);
578 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
579 "Checkpoint write object %d parent %d type %d chunk %d obj addr %p",
580 cp.obj_id, cp.parent_id,
581 cp.variant_type, cp.hdr_chunk, obj);
583 ok = (yaffs2_checkpt_wr
585 sizeof(cp)) == sizeof(cp));
588 && obj->variant_type ==
589 YAFFS_OBJECT_TYPE_FILE)
590 ok = yaffs2_wr_checkpt_tnodes
597 /* Dump end of list */
598 memset(&cp, 0xFF, sizeof(struct yaffs_checkpt_obj));
599 cp.struct_type = sizeof(cp);
602 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
607 static int yaffs2_rd_checkpt_objs(struct yaffs_dev *dev)
609 struct yaffs_obj *obj;
610 struct yaffs_checkpt_obj cp;
613 struct yaffs_obj *hard_list = NULL;
615 while (ok && !done) {
616 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
617 if (cp.struct_type != sizeof(cp)) {
618 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
619 "struct size %d instead of %d ok %d",
620 cp.struct_type, (int)sizeof(cp), ok);
624 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
625 "Checkpoint read object %d parent %d type %d chunk %d ",
626 cp.obj_id, cp.parent_id, cp.variant_type,
629 if (ok && cp.obj_id == ~0) {
633 yaffs_find_or_create_by_number(dev, cp.obj_id,
636 ok = taffs2_checkpt_obj_to_obj(obj, &cp);
639 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE) {
640 ok = yaffs2_rd_checkpt_tnodes(obj);
641 } else if (obj->variant_type ==
642 YAFFS_OBJECT_TYPE_HARDLINK) {
643 obj->hard_links.next =
644 (struct list_head *)hard_list;
654 yaffs_link_fixup(dev, hard_list);
659 static int yaffs2_wr_checkpt_sum(struct yaffs_dev *dev)
664 yaffs2_get_checkpt_sum(dev, &checkpt_sum);
666 ok = (yaffs2_checkpt_wr(dev, &checkpt_sum, sizeof(checkpt_sum)) ==
667 sizeof(checkpt_sum));
675 static int yaffs2_rd_checkpt_sum(struct yaffs_dev *dev)
681 yaffs2_get_checkpt_sum(dev, &checkpt_sum0);
683 ok = (yaffs2_checkpt_rd(dev, &checkpt_sum1, sizeof(checkpt_sum1)) ==
684 sizeof(checkpt_sum1));
689 if (checkpt_sum0 != checkpt_sum1)
695 static int yaffs2_wr_checkpt_data(struct yaffs_dev *dev)
699 if (!yaffs2_checkpt_required(dev)) {
700 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
701 "skipping checkpoint write");
706 ok = yaffs2_checkpt_open(dev, 1);
709 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
710 "write checkpoint validity");
711 ok = yaffs2_wr_checkpt_validity_marker(dev, 1);
714 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
715 "write checkpoint device");
716 ok = yaffs2_wr_checkpt_dev(dev);
719 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
720 "write checkpoint objects");
721 ok = yaffs2_wr_checkpt_objs(dev);
724 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
725 "write checkpoint validity");
726 ok = yaffs2_wr_checkpt_validity_marker(dev, 0);
730 ok = yaffs2_wr_checkpt_sum(dev);
732 if (!yaffs_checkpt_close(dev))
736 dev->is_checkpointed = 1;
738 dev->is_checkpointed = 0;
740 return dev->is_checkpointed;
743 static int yaffs2_rd_checkpt_data(struct yaffs_dev *dev)
747 if (!dev->param.is_yaffs2)
750 if (ok && dev->param.skip_checkpt_rd) {
751 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
752 "skipping checkpoint read");
757 ok = yaffs2_checkpt_open(dev, 0); /* open for read */
760 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
761 "read checkpoint validity");
762 ok = yaffs2_rd_checkpt_validity_marker(dev, 1);
765 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
766 "read checkpoint device");
767 ok = yaffs2_rd_checkpt_dev(dev);
770 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
771 "read checkpoint objects");
772 ok = yaffs2_rd_checkpt_objs(dev);
775 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
776 "read checkpoint validity");
777 ok = yaffs2_rd_checkpt_validity_marker(dev, 0);
781 ok = yaffs2_rd_checkpt_sum(dev);
782 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
783 "read checkpoint checksum %d", ok);
786 if (!yaffs_checkpt_close(dev))
790 dev->is_checkpointed = 1;
792 dev->is_checkpointed = 0;
798 void yaffs2_checkpt_invalidate(struct yaffs_dev *dev)
800 if (dev->is_checkpointed || dev->blocks_in_checkpt > 0) {
801 dev->is_checkpointed = 0;
802 yaffs2_checkpt_invalidate_stream(dev);
804 if (dev->param.sb_dirty_fn)
805 dev->param.sb_dirty_fn(dev);
808 int yaffs_checkpoint_save(struct yaffs_dev *dev)
811 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
812 "save entry: is_checkpointed %d",
813 dev->is_checkpointed);
815 yaffs_verify_objects(dev);
816 yaffs_verify_blocks(dev);
817 yaffs_verify_free_chunks(dev);
819 if (!dev->is_checkpointed) {
820 yaffs2_checkpt_invalidate(dev);
821 yaffs2_wr_checkpt_data(dev);
824 yaffs_trace(YAFFS_TRACE_CHECKPOINT | YAFFS_TRACE_MOUNT,
825 "save exit: is_checkpointed %d",
826 dev->is_checkpointed);
828 return dev->is_checkpointed;
831 int yaffs2_checkpt_restore(struct yaffs_dev *dev)
834 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
835 "restore entry: is_checkpointed %d",
836 dev->is_checkpointed);
838 retval = yaffs2_rd_checkpt_data(dev);
840 if (dev->is_checkpointed) {
841 yaffs_verify_objects(dev);
842 yaffs_verify_blocks(dev);
843 yaffs_verify_free_chunks(dev);
846 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
847 "restore exit: is_checkpointed %d",
848 dev->is_checkpointed);
853 int yaffs2_handle_hole(struct yaffs_obj *obj, loff_t new_size)
855 /* if new_size > old_file_size.
856 * We're going to be writing a hole.
857 * If the hole is small then write zeros otherwise write a start of hole marker.
860 loff_t old_file_size;
863 int result = YAFFS_OK;
864 struct yaffs_dev *dev = NULL;
866 u8 *local_buffer = NULL;
868 int small_increase_ok = 0;
873 if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
878 /* Bail out if not yaffs2 mode */
879 if (!dev->param.is_yaffs2)
882 old_file_size = obj->variant.file_variant.file_size;
884 if (new_size <= old_file_size)
887 increase = new_size - old_file_size;
889 if (increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->data_bytes_per_chunk &&
890 yaffs_check_alloc_available(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
896 local_buffer = yaffs_get_temp_buffer(dev, __LINE__);
899 /* fill hole with zero bytes */
900 int pos = old_file_size;
903 memset(local_buffer, 0, dev->data_bytes_per_chunk);
904 small_increase_ok = 1;
906 while (increase > 0 && small_increase_ok) {
907 this_write = increase;
908 if (this_write > dev->data_bytes_per_chunk)
909 this_write = dev->data_bytes_per_chunk;
911 yaffs_do_file_wr(obj, local_buffer, pos, this_write,
913 if (written == this_write) {
915 increase -= this_write;
917 small_increase_ok = 0;
921 yaffs_release_temp_buffer(dev, local_buffer, __LINE__);
923 /* If we were out of space then reverse any chunks we've added */
924 if (!small_increase_ok)
925 yaffs_resize_file_down(obj, old_file_size);
928 if (!small_increase_ok &&
930 obj->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
931 obj->parent->obj_id != YAFFS_OBJECTID_DELETED) {
932 /* Write a hole start header with the old file size */
933 yaffs_update_oh(obj, NULL, 0, 1, 0, NULL);
940 struct yaffs_block_index {
945 static int yaffs2_ybicmp(const void *a, const void *b)
947 int aseq = ((struct yaffs_block_index *)a)->seq;
948 int bseq = ((struct yaffs_block_index *)b)->seq;
949 int ablock = ((struct yaffs_block_index *)a)->block;
950 int bblock = ((struct yaffs_block_index *)b)->block;
952 return ablock - bblock;
957 int yaffs2_scan_backwards(struct yaffs_dev *dev)
959 struct yaffs_ext_tags tags;
970 enum yaffs_block_state state;
971 struct yaffs_obj *hard_list = NULL;
972 struct yaffs_block_info *bi;
974 struct yaffs_obj_hdr *oh;
975 struct yaffs_obj *in;
976 struct yaffs_obj *parent;
977 int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
985 int alloc_failed = 0;
987 struct yaffs_block_index *block_index = NULL;
988 int alt_block_index = 0;
990 yaffs_trace(YAFFS_TRACE_SCAN,
991 "yaffs2_scan_backwards starts intstartblk %d intendblk %d...",
992 dev->internal_start_block, dev->internal_end_block);
994 dev->seq_number = YAFFS_LOWEST_SEQUENCE_NUMBER;
996 block_index = kmalloc(n_blocks * sizeof(struct yaffs_block_index),
1001 vmalloc(n_blocks * sizeof(struct yaffs_block_index));
1002 alt_block_index = 1;
1006 yaffs_trace(YAFFS_TRACE_SCAN,
1007 "yaffs2_scan_backwards() could not allocate block index!"
1012 dev->blocks_in_checkpt = 0;
1014 chunk_data = yaffs_get_temp_buffer(dev, __LINE__);
1016 /* Scan all the blocks to determine their state */
1017 bi = dev->block_info;
1018 for (blk = dev->internal_start_block; blk <= dev->internal_end_block;
1020 yaffs_clear_chunk_bits(dev, blk);
1021 bi->pages_in_use = 0;
1022 bi->soft_del_pages = 0;
1024 yaffs_query_init_block_state(dev, blk, &state, &seq_number);
1026 bi->block_state = state;
1027 bi->seq_number = seq_number;
1029 if (bi->seq_number == YAFFS_SEQUENCE_CHECKPOINT_DATA)
1030 bi->block_state = state = YAFFS_BLOCK_STATE_CHECKPOINT;
1031 if (bi->seq_number == YAFFS_SEQUENCE_BAD_BLOCK)
1032 bi->block_state = state = YAFFS_BLOCK_STATE_DEAD;
1034 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG,
1035 "Block scanning block %d state %d seq %d",
1036 blk, state, seq_number);
1038 if (state == YAFFS_BLOCK_STATE_CHECKPOINT) {
1039 dev->blocks_in_checkpt++;
1041 } else if (state == YAFFS_BLOCK_STATE_DEAD) {
1042 yaffs_trace(YAFFS_TRACE_BAD_BLOCKS,
1043 "block %d is bad", blk);
1044 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
1045 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "Block empty ");
1046 dev->n_erased_blocks++;
1047 dev->n_free_chunks += dev->param.chunks_per_block;
1048 } else if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1050 /* Determine the highest sequence number */
1051 if (seq_number >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1052 seq_number < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1054 block_index[n_to_scan].seq = seq_number;
1055 block_index[n_to_scan].block = blk;
1059 if (seq_number >= dev->seq_number)
1060 dev->seq_number = seq_number;
1062 /* TODO: Nasty sequence number! */
1063 yaffs_trace(YAFFS_TRACE_SCAN,
1064 "Block scanning block %d has bad sequence number %d",
1072 yaffs_trace(YAFFS_TRACE_SCAN, "%d blocks to be sorted...", n_to_scan);
1076 /* Sort the blocks by sequence number */
1077 sort(block_index, n_to_scan, sizeof(struct yaffs_block_index),
1078 yaffs2_ybicmp, NULL);
1082 yaffs_trace(YAFFS_TRACE_SCAN, "...done");
1084 /* Now scan the blocks looking at the data. */
1086 end_iter = n_to_scan - 1;
1087 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "%d blocks to scan", n_to_scan);
1089 /* For each block.... backwards */
1090 for (block_iter = end_iter; !alloc_failed && block_iter >= start_iter;
1092 /* Cooperative multitasking! This loop can run for so
1093 long that watchdog timers expire. */
1096 /* get the block to scan in the correct order */
1097 blk = block_index[block_iter].block;
1099 bi = yaffs_get_block_info(dev, blk);
1101 state = bi->block_state;
1105 /* For each chunk in each block that needs scanning.... */
1107 for (c = dev->param.chunks_per_block - 1;
1108 !alloc_failed && c >= 0 &&
1109 (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1110 state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
1111 /* Scan backwards...
1112 * Read the tags and decide what to do
1115 chunk = blk * dev->param.chunks_per_block + c;
1117 result = yaffs_rd_chunk_tags_nand(dev, chunk, NULL,
1120 /* Let's have a good look at this chunk... */
1122 if (!tags.chunk_used) {
1123 /* An unassigned chunk in the block.
1124 * If there are used chunks after this one, then
1125 * it is a chunk that was skipped due to failing the erased
1126 * check. Just skip it so that it can be deleted.
1127 * But, more typically, We get here when this is an unallocated
1128 * chunk and his means that either the block is empty or
1129 * this is the one being allocated from
1133 /* This is a chunk that was skipped due to failing the erased check */
1134 } else if (c == 0) {
1135 /* We're looking at the first chunk in the block so the block is unused */
1136 state = YAFFS_BLOCK_STATE_EMPTY;
1137 dev->n_erased_blocks++;
1140 YAFFS_BLOCK_STATE_NEEDS_SCANNING
1142 YAFFS_BLOCK_STATE_ALLOCATING) {
1143 if (dev->seq_number ==
1145 /* this is the block being allocated from */
1147 yaffs_trace(YAFFS_TRACE_SCAN,
1148 " Allocating from %d %d",
1152 YAFFS_BLOCK_STATE_ALLOCATING;
1153 dev->alloc_block = blk;
1154 dev->alloc_page = c;
1156 alloc_block_finder =
1159 /* This is a partially written block that is not
1160 * the current allocation block.
1163 yaffs_trace(YAFFS_TRACE_SCAN,
1164 "Partially written block %d detected",
1170 dev->n_free_chunks++;
1172 } else if (tags.ecc_result == YAFFS_ECC_RESULT_UNFIXED) {
1173 yaffs_trace(YAFFS_TRACE_SCAN,
1174 " Unfixed ECC in chunk(%d:%d), chunk ignored",
1177 dev->n_free_chunks++;
1179 } else if (tags.obj_id > YAFFS_MAX_OBJECT_ID ||
1180 tags.chunk_id > YAFFS_MAX_CHUNK_ID ||
1182 && tags.n_bytes > dev->data_bytes_per_chunk)
1183 || tags.seq_number != bi->seq_number) {
1184 yaffs_trace(YAFFS_TRACE_SCAN,
1185 "Chunk (%d:%d) with bad tags:obj = %d, chunk_id = %d, n_bytes = %d, ignored",
1186 blk, c, tags.obj_id,
1187 tags.chunk_id, tags.n_bytes);
1189 dev->n_free_chunks++;
1191 } else if (tags.chunk_id > 0) {
1192 /* chunk_id > 0 so it is a data chunk... */
1193 unsigned int endpos;
1196 1) * dev->data_bytes_per_chunk;
1200 yaffs_set_chunk_bit(dev, blk, c);
1203 in = yaffs_find_or_create_by_number(dev,
1205 YAFFS_OBJECT_TYPE_FILE);
1212 in->variant_type == YAFFS_OBJECT_TYPE_FILE
1214 in->variant.file_variant.shrink_size) {
1215 /* This has not been invalidated by a resize */
1216 if (!yaffs_put_chunk_in_file
1217 (in, tags.chunk_id, chunk, -1)) {
1221 /* File size is calculated by looking at the data chunks if we have not
1222 * seen an object header yet. Stop this practice once we find an object header.
1224 endpos = chunk_base + tags.n_bytes;
1226 if (!in->valid && /* have not got an object header yet */
1227 in->variant.file_variant.
1228 scanned_size < endpos) {
1229 in->variant.file_variant.
1230 scanned_size = endpos;
1231 in->variant.file_variant.
1236 /* This chunk has been invalidated by a resize, or a past file deletion
1237 * so delete the chunk*/
1238 yaffs_chunk_del(dev, chunk, 1,
1243 /* chunk_id == 0, so it is an ObjectHeader.
1244 * Thus, we read in the object header and make the object
1248 yaffs_set_chunk_bit(dev, blk, c);
1254 if (tags.extra_available) {
1255 in = yaffs_find_or_create_by_number(dev,
1265 (!in->valid && dev->param.disable_lazy_load)
1266 || tags.extra_shadows || (!in->valid
1271 YAFFS_OBJECTID_LOSTNFOUND)))
1274 /* If we don't have valid info then we need to read the chunk
1275 * TODO In future we can probably defer reading the chunk and
1276 * living with invalid data until needed.
1279 result = yaffs_rd_chunk_tags_nand(dev,
1284 oh = (struct yaffs_obj_hdr *)chunk_data;
1286 if (dev->param.inband_tags) {
1287 /* Fix up the header if they got corrupted by inband tags */
1289 oh->inband_shadowed_obj_id;
1291 oh->inband_is_shrink;
1295 in = yaffs_find_or_create_by_number(dev, tags.obj_id, oh->type);
1303 /* TODO Hoosterman we have a problem! */
1304 yaffs_trace(YAFFS_TRACE_ERROR,
1305 "yaffs tragedy: Could not make object for object %d at chunk %d during scan",
1306 tags.obj_id, chunk);
1311 /* We have already filled this one.
1312 * We have a duplicate that will be discarded, but
1313 * we first have to suck out resize info if it is a file.
1316 if ((in->variant_type ==
1317 YAFFS_OBJECT_TYPE_FILE) && ((oh
1322 YAFFS_OBJECT_TYPE_FILE)
1330 YAFFS_OBJECT_TYPE_FILE)))
1337 (oh) ? oh->parent_obj_id :
1338 tags.extra_parent_id;
1343 tags.extra_is_shrink;
1345 /* If it is deleted (unlinked at start also means deleted)
1346 * we treat the file size as being zeroed at this point.
1348 if (parent_obj_id ==
1349 YAFFS_OBJECTID_DELETED
1351 YAFFS_OBJECTID_UNLINKED) {
1357 && in->variant.file_variant.
1358 shrink_size > this_size)
1365 bi->has_shrink_hdr = 1;
1368 /* Use existing - destroy this one. */
1369 yaffs_chunk_del(dev, chunk, 1,
1374 if (!in->valid && in->variant_type !=
1375 (oh ? oh->type : tags.extra_obj_type))
1376 yaffs_trace(YAFFS_TRACE_ERROR,
1377 "yaffs tragedy: Bad object type, %d != %d, for object %d at chunk %d during scan",
1379 oh->type : tags.extra_obj_type,
1380 in->variant_type, tags.obj_id,
1384 (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1386 YAFFS_OBJECTID_LOSTNFOUND)) {
1387 /* We only load some info, don't fiddle with directory structure */
1392 in->yst_mode = oh->yst_mode;
1393 yaffs_load_attribs(in, oh);
1394 in->lazy_loaded = 0;
1396 in->lazy_loaded = 1;
1398 in->hdr_chunk = chunk;
1400 } else if (!in->valid) {
1401 /* we need to load this info */
1404 in->hdr_chunk = chunk;
1407 in->variant_type = oh->type;
1409 in->yst_mode = oh->yst_mode;
1410 yaffs_load_attribs(in, oh);
1412 if (oh->shadows_obj > 0)
1413 yaffs_handle_shadowed_obj
1418 yaffs_set_obj_name_from_oh(in,
1421 yaffs_find_or_create_by_number
1422 (dev, oh->parent_obj_id,
1423 YAFFS_OBJECT_TYPE_DIRECTORY);
1425 file_size = oh->file_size;
1426 is_shrink = oh->is_shrink;
1427 equiv_id = oh->equiv_id;
1431 tags.extra_obj_type;
1433 yaffs_find_or_create_by_number
1434 (dev, tags.extra_parent_id,
1435 YAFFS_OBJECT_TYPE_DIRECTORY);
1436 file_size = tags.extra_length;
1438 tags.extra_is_shrink;
1439 equiv_id = tags.extra_equiv_id;
1440 in->lazy_loaded = 1;
1448 /* directory stuff...
1452 if (parent && parent->variant_type ==
1453 YAFFS_OBJECT_TYPE_UNKNOWN) {
1454 /* Set up as a directory */
1455 parent->variant_type =
1456 YAFFS_OBJECT_TYPE_DIRECTORY;
1457 INIT_LIST_HEAD(&parent->
1458 variant.dir_variant.children);
1460 || parent->variant_type !=
1461 YAFFS_OBJECT_TYPE_DIRECTORY) {
1462 /* Hoosterman, another problem....
1463 * We're trying to use a non-directory as a directory
1466 yaffs_trace(YAFFS_TRACE_ERROR,
1467 "yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1469 parent = dev->lost_n_found;
1472 yaffs_add_obj_to_dir(parent, in);
1474 is_unlinked = (parent == dev->del_dir)
1475 || (parent == dev->unlinked_dir);
1478 /* Mark the block as having a shrink header */
1479 bi->has_shrink_hdr = 1;
1482 /* Note re hardlinks.
1483 * Since we might scan a hardlink before its equivalent object is scanned
1484 * we put them all in a list.
1485 * After scanning is complete, we should have all the objects, so we run
1486 * through this list and fix up all the chains.
1489 switch (in->variant_type) {
1490 case YAFFS_OBJECT_TYPE_UNKNOWN:
1491 /* Todo got a problem */
1493 case YAFFS_OBJECT_TYPE_FILE:
1496 file_variant.scanned_size <
1498 /* This covers the case where the file size is greater
1499 * than where the data is
1500 * This will happen if the file is resized to be larger
1501 * than its current data extents.
1513 if (in->variant.file_variant.
1514 shrink_size > file_size)
1521 case YAFFS_OBJECT_TYPE_HARDLINK:
1525 equiv_id = equiv_id;
1526 in->hard_links.next =
1527 (struct list_head *)
1532 case YAFFS_OBJECT_TYPE_DIRECTORY:
1535 case YAFFS_OBJECT_TYPE_SPECIAL:
1538 case YAFFS_OBJECT_TYPE_SYMLINK:
1543 yaffs_clone_str(oh->
1558 } /* End of scanning for each chunk */
1560 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1561 /* If we got this far while scanning, then the block is fully allocated. */
1562 state = YAFFS_BLOCK_STATE_FULL;
1565 bi->block_state = state;
1567 /* Now let's see if it was dirty */
1568 if (bi->pages_in_use == 0 &&
1569 !bi->has_shrink_hdr &&
1570 bi->block_state == YAFFS_BLOCK_STATE_FULL) {
1571 yaffs_block_became_dirty(dev, blk);
1576 yaffs_skip_rest_of_block(dev);
1578 if (alt_block_index)
1583 /* Ok, we've done all the scanning.
1584 * Fix up the hard link chains.
1585 * We should now have scanned all the objects, now it's time to add these
1588 yaffs_link_fixup(dev, hard_list);
1590 yaffs_release_temp_buffer(dev, chunk_data, __LINE__);
1595 yaffs_trace(YAFFS_TRACE_SCAN, "yaffs2_scan_backwards ends");