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.
15 #include "yaffs_guts.h"
16 #include "yaffs_trace.h"
17 #include "yaffs_yaffs2.h"
18 #include "yaffs_checkptrw.h"
19 #include "yaffs_bitmap.h"
20 #include "yaffs_nand.h"
21 #include "yaffs_getblockinfo.h"
22 #include "yaffs_verify.h"
23 #include "yaffs_attribs.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
33 #define YAFFS_SMALL_HOLE_THRESHOLD 4
37 * Oldest Dirty Sequence Number handling.
40 /* yaffs_calc_oldest_dirty_seq()
41 * yaffs2_find_oldest_dirty_seq()
42 * Calculate the oldest dirty sequence number if we don't know it.
44 void yaffs_calc_oldest_dirty_seq(struct yaffs_dev *dev)
48 unsigned block_no = 0;
49 struct yaffs_block_info *b;
51 if(!dev->param.is_yaffs2)
54 /* Find the oldest dirty sequence number. */
55 seq = dev->seq_number + 1;
57 for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) {
58 if (b->block_state == YAFFS_BLOCK_STATE_FULL &&
59 (b->pages_in_use - b->soft_del_pages) < dev->param.chunks_per_block &&
60 b->seq_number < seq) {
68 dev->oldest_dirty_seq = seq;
69 dev->oldest_dirty_block = block_no;
75 void yaffs2_find_oldest_dirty_seq(struct yaffs_dev *dev)
77 if(!dev->param.is_yaffs2)
80 if(!dev->oldest_dirty_seq)
81 yaffs_calc_oldest_dirty_seq(dev);
85 * yaffs_clear_oldest_dirty_seq()
86 * Called when a block is erased or marked bad. (ie. when its seq_number
87 * becomes invalid). If the value matches the oldest then we clear
88 * dev->oldest_dirty_seq to force its recomputation.
90 void yaffs2_clear_oldest_dirty_seq(struct yaffs_dev *dev, struct yaffs_block_info *bi)
93 if(!dev->param.is_yaffs2)
96 if(!bi || bi->seq_number == dev->oldest_dirty_seq){
97 dev->oldest_dirty_seq = 0;
98 dev->oldest_dirty_block = 0;
103 * yaffs2_update_oldest_dirty_seq()
104 * Update the oldest dirty sequence number whenever we dirty a block.
105 * Only do this if the oldest_dirty_seq is actually being tracked.
107 void yaffs2_update_oldest_dirty_seq(struct yaffs_dev *dev, unsigned block_no, struct yaffs_block_info *bi)
109 if(!dev->param.is_yaffs2)
112 if(dev->oldest_dirty_seq){
113 if(dev->oldest_dirty_seq > bi->seq_number){
114 dev->oldest_dirty_seq = bi->seq_number;
115 dev->oldest_dirty_block = block_no;
120 int yaffs_block_ok_for_gc(struct yaffs_dev *dev,
121 struct yaffs_block_info *bi)
124 if (!dev->param.is_yaffs2)
125 return 1; /* disqualification only applies to yaffs2. */
127 if (!bi->has_shrink_hdr)
128 return 1; /* can gc */
130 yaffs2_find_oldest_dirty_seq(dev);
132 /* Can't do gc of this block if there are any blocks older than this one that have
135 return (bi->seq_number <= dev->oldest_dirty_seq);
139 * yaffs2_find_refresh_block()
140 * periodically finds the oldest full block by sequence number for refreshing.
143 u32 yaffs2_find_refresh_block(struct yaffs_dev *dev)
150 struct yaffs_block_info *bi;
152 if(!dev->param.is_yaffs2)
156 * If refresh period < 10 then refreshing is disabled.
158 if(dev->param.refresh_period < 10)
164 if(dev->refresh_skip > dev->param.refresh_period)
165 dev->refresh_skip = dev->param.refresh_period;
167 if(dev->refresh_skip > 0)
171 * Refresh skip is now zero.
172 * We'll do a refresh this time around....
173 * Update the refresh skip and find the oldest block.
175 dev->refresh_skip = dev->param.refresh_period;
176 dev->refresh_count++;
177 bi = dev->block_info;
178 for (b = dev->internal_start_block; b <=dev->internal_end_block; b++){
180 if (bi->block_state == YAFFS_BLOCK_STATE_FULL){
183 bi->seq_number < oldest_seq){
185 oldest_seq = bi->seq_number;
193 (TSTR("GC refresh count %d selected block %d with seq_number %d" TENDSTR),
194 dev->refresh_count, oldest, oldest_seq));
200 int yaffs2_checkpt_required(struct yaffs_dev *dev)
204 if(!dev->param.is_yaffs2)
207 nblocks = dev->internal_end_block - dev->internal_start_block + 1 ;
209 return !dev->param.skip_checkpt_wr &&
211 (nblocks >= YAFFS_CHECKPOINT_MIN_BLOCKS);
214 int yaffs_calc_checkpt_blocks_required(struct yaffs_dev *dev)
218 if(!dev->param.is_yaffs2)
221 if (!dev->checkpoint_blocks_required &&
222 yaffs2_checkpt_required(dev)){
223 /* Not a valid value so recalculate */
226 int dev_blocks = (dev->param.end_block - dev->param.start_block + 1);
228 n_bytes += sizeof(struct yaffs_checkpt_validity);
229 n_bytes += sizeof(struct yaffs_checkpt_dev);
230 n_bytes += dev_blocks * sizeof(struct yaffs_block_info);
231 n_bytes += dev_blocks * dev->chunk_bit_stride;
232 n_bytes += (sizeof(struct yaffs_checkpt_obj) + sizeof(u32)) * (dev->n_obj);
233 n_bytes += (dev->tnode_size + sizeof(u32)) * (dev->n_tnodes);
234 n_bytes += sizeof(struct yaffs_checkpt_validity);
235 n_bytes += sizeof(u32); /* checksum*/
237 /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
239 n_blocks = (n_bytes/(dev->data_bytes_per_chunk * dev->param.chunks_per_block)) + 3;
241 dev->checkpoint_blocks_required = n_blocks;
244 retval = dev->checkpoint_blocks_required - dev->blocks_in_checkpt;
250 /*--------------------- 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)) ?
268 static int yaffs2_rd_checkpt_validity_marker(struct yaffs_dev *dev, int head)
270 struct yaffs_checkpt_validity cp;
273 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
276 ok = (cp.struct_type == sizeof(cp)) &&
277 (cp.magic == YAFFS_MAGIC) &&
278 (cp.version == YAFFS_CHECKPOINT_VERSION) &&
279 (cp.head == ((head) ? 1 : 0));
283 static void yaffs2_dev_to_checkpt_dev(struct yaffs_checkpt_dev *cp,
284 struct yaffs_dev *dev)
286 cp->n_erased_blocks = dev->n_erased_blocks;
287 cp->alloc_block = dev->alloc_block;
288 cp->alloc_page = dev->alloc_page;
289 cp->n_free_chunks = dev->n_free_chunks;
291 cp->n_deleted_files = dev->n_deleted_files;
292 cp->n_unlinked_files = dev->n_unlinked_files;
293 cp->n_bg_deletions = dev->n_bg_deletions;
294 cp->seq_number = dev->seq_number;
298 static void yaffs_checkpt_dev_to_dev(struct yaffs_dev *dev,
299 struct yaffs_checkpt_dev *cp)
301 dev->n_erased_blocks = cp->n_erased_blocks;
302 dev->alloc_block = cp->alloc_block;
303 dev->alloc_page = cp->alloc_page;
304 dev->n_free_chunks = cp->n_free_chunks;
306 dev->n_deleted_files = cp->n_deleted_files;
307 dev->n_unlinked_files = cp->n_unlinked_files;
308 dev->n_bg_deletions = cp->n_bg_deletions;
309 dev->seq_number = cp->seq_number;
313 static int yaffs2_wr_checkpt_dev(struct yaffs_dev *dev)
315 struct yaffs_checkpt_dev cp;
317 u32 n_blocks = (dev->internal_end_block - dev->internal_start_block + 1);
321 /* Write device runtime values*/
322 yaffs2_dev_to_checkpt_dev(&cp, dev);
323 cp.struct_type = sizeof(cp);
325 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
327 /* Write block info */
329 n_bytes = n_blocks * sizeof(struct yaffs_block_info);
330 ok = (yaffs2_checkpt_wr(dev, dev->block_info, n_bytes) == 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) == n_bytes);
342 static int yaffs2_rd_checkpt_dev(struct yaffs_dev *dev)
344 struct yaffs_checkpt_dev cp;
346 u32 n_blocks = (dev->internal_end_block - dev->internal_start_block + 1);
350 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
354 if (cp.struct_type != sizeof(cp))
358 yaffs_checkpt_dev_to_dev(dev, &cp);
360 n_bytes = n_blocks * sizeof(struct yaffs_block_info);
362 ok = (yaffs2_checkpt_rd(dev, dev->block_info, n_bytes) == n_bytes);
366 n_bytes = n_blocks * dev->chunk_bit_stride;
368 ok = (yaffs2_checkpt_rd(dev, dev->chunk_bits, n_bytes) == n_bytes);
373 static void yaffs2_obj_checkpt_obj(struct yaffs_checkpt_obj *cp,
374 struct yaffs_obj *obj)
377 cp->obj_id = obj->obj_id;
378 cp->parent_id = (obj->parent) ? obj->parent->obj_id : 0;
379 cp->hdr_chunk = obj->hdr_chunk;
380 cp->variant_type = obj->variant_type;
381 cp->deleted = obj->deleted;
382 cp->soft_del = obj->soft_del;
383 cp->unlinked = obj->unlinked;
384 cp->fake = obj->fake;
385 cp->rename_allowed = obj->rename_allowed;
386 cp->unlink_allowed = obj->unlink_allowed;
387 cp->serial = obj->serial;
388 cp->n_data_chunks = obj->n_data_chunks;
390 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
391 cp->size_or_equiv_obj = obj->variant.file_variant.file_size;
392 else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
393 cp->size_or_equiv_obj = obj->variant.hardlink_variant.equiv_id;
396 static int taffs2_checkpt_obj_to_obj(struct yaffs_obj *obj, struct yaffs_checkpt_obj *cp)
399 struct yaffs_obj *parent;
401 if (obj->variant_type != cp->variant_type) {
402 T(YAFFS_TRACE_ERROR, (TSTR("Checkpoint read object %d type %d "
403 TCONT("chunk %d does not match existing object type %d")
404 TENDSTR), cp->obj_id, cp->variant_type, cp->hdr_chunk,
409 obj->obj_id = cp->obj_id;
412 parent = yaffs_find_or_create_by_number(
415 YAFFS_OBJECT_TYPE_DIRECTORY);
420 if (parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
421 T(YAFFS_TRACE_ALWAYS, (TSTR("Checkpoint read object %d parent %d type %d"
422 TCONT(" chunk %d Parent type, %d, not directory")
424 cp->obj_id, cp->parent_id, cp->variant_type,
425 cp->hdr_chunk, parent->variant_type));
428 yaffs_add_obj_to_dir(parent, obj);
431 obj->hdr_chunk = cp->hdr_chunk;
432 obj->variant_type = cp->variant_type;
433 obj->deleted = cp->deleted;
434 obj->soft_del = cp->soft_del;
435 obj->unlinked = cp->unlinked;
436 obj->fake = cp->fake;
437 obj->rename_allowed = cp->rename_allowed;
438 obj->unlink_allowed = cp->unlink_allowed;
439 obj->serial = cp->serial;
440 obj->n_data_chunks = cp->n_data_chunks;
442 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
443 obj->variant.file_variant.file_size = cp->size_or_equiv_obj;
444 else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
445 obj->variant.hardlink_variant.equiv_id = cp->size_or_equiv_obj;
447 if (obj->hdr_chunk > 0)
448 obj->lazy_loaded = 1;
454 static int yaffs2_checkpt_tnode_worker(struct yaffs_obj *in, struct yaffs_tnode *tn,
455 u32 level, int chunk_offset)
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,
469 (chunk_offset<<YAFFS_TNODES_INTERNAL_BITS) + i);
472 } else if (level == 0) {
473 u32 base_offset = chunk_offset << YAFFS_TNODES_LEVEL0_BITS;
474 ok = (yaffs2_checkpt_wr(dev, &base_offset, sizeof(base_offset)) ==
475 sizeof(base_offset));
477 ok = (yaffs2_checkpt_wr(dev, tn, dev->tnode_size) == dev->tnode_size);
485 static int yaffs2_wr_checkpt_tnodes(struct yaffs_obj *obj)
490 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE) {
491 ok = yaffs2_checkpt_tnode_worker(obj,
492 obj->variant.file_variant.top,
493 obj->variant.file_variant.top_level,
496 ok = (yaffs2_checkpt_wr(obj->my_dev, &end_marker, sizeof(end_marker)) ==
503 static int yaffs2_rd_checkpt_tnodes(struct yaffs_obj *obj)
507 struct yaffs_dev *dev = obj->my_dev;
508 struct yaffs_file_var *file_stuct_ptr = &obj->variant.file_variant;
509 struct yaffs_tnode *tn;
512 ok = (yaffs2_checkpt_rd(dev, &base_chunk, sizeof(base_chunk)) == sizeof(base_chunk));
514 while (ok && (~base_chunk)) {
516 /* Read level 0 tnode */
519 tn = yaffs_get_tnode(dev);
521 ok = (yaffs2_checkpt_rd(dev, tn, dev->tnode_size) == dev->tnode_size);
526 ok = yaffs_add_find_tnode_0(dev,
532 ok = (yaffs2_checkpt_rd(dev, &base_chunk, sizeof(base_chunk)) == sizeof(base_chunk));
536 T(YAFFS_TRACE_CHECKPOINT, (
537 TSTR("Checkpoint read tnodes %d records, last %d. ok %d" TENDSTR),
538 nread, base_chunk, ok));
544 static int yaffs2_wr_checkpt_objs(struct yaffs_dev *dev)
546 struct yaffs_obj *obj;
547 struct yaffs_checkpt_obj cp;
550 struct list_head *lh;
553 /* Iterate through the objects in each hash entry,
554 * dumping them to the checkpointing stream.
557 for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
558 list_for_each(lh, &dev->obj_bucket[i].list) {
560 obj = list_entry(lh, struct yaffs_obj, hash_link);
561 if (!obj->defered_free) {
562 yaffs2_obj_checkpt_obj(&cp, obj);
563 cp.struct_type = sizeof(cp);
565 T(YAFFS_TRACE_CHECKPOINT, (
566 TSTR("Checkpoint write object %d parent %d type %d chunk %d obj addr %p" TENDSTR),
567 cp.obj_id, cp.parent_id, cp.variant_type, cp.hdr_chunk, obj));
569 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
571 if (ok && obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
572 ok = yaffs2_wr_checkpt_tnodes(obj);
578 /* Dump end of list */
579 memset(&cp, 0xFF, sizeof(struct yaffs_checkpt_obj));
580 cp.struct_type = sizeof(cp);
583 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
588 static int yaffs2_rd_checkpt_objs(struct yaffs_dev *dev)
590 struct yaffs_obj *obj;
591 struct yaffs_checkpt_obj cp;
594 struct yaffs_obj *hard_list = NULL;
596 while (ok && !done) {
597 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
598 if (cp.struct_type != sizeof(cp)) {
599 T(YAFFS_TRACE_CHECKPOINT, (TSTR("struct size %d instead of %d ok %d"TENDSTR),
600 cp.struct_type, (int)sizeof(cp), ok));
604 T(YAFFS_TRACE_CHECKPOINT, (TSTR("Checkpoint read object %d parent %d type %d chunk %d " TENDSTR),
605 cp.obj_id, cp.parent_id, cp.variant_type, cp.hdr_chunk));
607 if (ok && cp.obj_id == ~0)
610 obj = yaffs_find_or_create_by_number(dev, cp.obj_id, cp.variant_type);
612 ok = taffs2_checkpt_obj_to_obj(obj, &cp);
615 if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE) {
616 ok = yaffs2_rd_checkpt_tnodes(obj);
617 } else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK) {
618 obj->hard_links.next =
619 (struct list_head *) hard_list;
628 yaffs_link_fixup(dev, hard_list);
633 static int yaffs2_wr_checkpt_sum(struct yaffs_dev *dev)
638 yaffs2_get_checkpt_sum(dev, &checkpt_sum);
640 ok = (yaffs2_checkpt_wr(dev, &checkpt_sum, sizeof(checkpt_sum)) == sizeof(checkpt_sum));
648 static int yaffs2_rd_checkpt_sum(struct yaffs_dev *dev)
654 yaffs2_get_checkpt_sum(dev, &checkpt_sum0);
656 ok = (yaffs2_checkpt_rd(dev, &checkpt_sum1, sizeof(checkpt_sum1)) == sizeof(checkpt_sum1));
661 if (checkpt_sum0 != checkpt_sum1)
668 static int yaffs2_wr_checkpt_data(struct yaffs_dev *dev)
672 if (!yaffs2_checkpt_required(dev)) {
673 T(YAFFS_TRACE_CHECKPOINT, (TSTR("skipping checkpoint write" TENDSTR)));
678 ok = yaffs2_checkpt_open(dev, 1);
681 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint validity" TENDSTR)));
682 ok = yaffs2_wr_checkpt_validity_marker(dev, 1);
685 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint device" TENDSTR)));
686 ok = yaffs2_wr_checkpt_dev(dev);
689 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint objects" TENDSTR)));
690 ok = yaffs2_wr_checkpt_objs(dev);
693 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint validity" TENDSTR)));
694 ok = yaffs2_wr_checkpt_validity_marker(dev, 0);
698 ok = yaffs2_wr_checkpt_sum(dev);
700 if (!yaffs_checkpt_close(dev))
704 dev->is_checkpointed = 1;
706 dev->is_checkpointed = 0;
708 return dev->is_checkpointed;
711 static int yaffs2_rd_checkpt_data(struct yaffs_dev *dev)
715 if(!dev->param.is_yaffs2)
718 if (ok && dev->param.skip_checkpt_rd) {
719 T(YAFFS_TRACE_CHECKPOINT, (TSTR("skipping checkpoint read" TENDSTR)));
724 ok = yaffs2_checkpt_open(dev, 0); /* open for read */
727 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint validity" TENDSTR)));
728 ok = yaffs2_rd_checkpt_validity_marker(dev, 1);
731 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint device" TENDSTR)));
732 ok = yaffs2_rd_checkpt_dev(dev);
735 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint objects" TENDSTR)));
736 ok = yaffs2_rd_checkpt_objs(dev);
739 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint validity" TENDSTR)));
740 ok = yaffs2_rd_checkpt_validity_marker(dev, 0);
744 ok = yaffs2_rd_checkpt_sum(dev);
745 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint checksum %d" TENDSTR), ok));
748 if (!yaffs_checkpt_close(dev))
752 dev->is_checkpointed = 1;
754 dev->is_checkpointed = 0;
760 void yaffs2_checkpt_invalidate(struct yaffs_dev *dev)
762 if (dev->is_checkpointed ||
763 dev->blocks_in_checkpt > 0) {
764 dev->is_checkpointed = 0;
765 yaffs2_checkpt_invalidate_stream(dev);
767 if (dev->param.sb_dirty_fn)
768 dev->param.sb_dirty_fn(dev);
772 int yaffs_checkpoint_save(struct yaffs_dev *dev)
775 T(YAFFS_TRACE_CHECKPOINT, (TSTR("save entry: is_checkpointed %d"TENDSTR), dev->is_checkpointed));
777 yaffs_verify_objects(dev);
778 yaffs_verify_blocks(dev);
779 yaffs_verify_free_chunks(dev);
781 if (!dev->is_checkpointed) {
782 yaffs2_checkpt_invalidate(dev);
783 yaffs2_wr_checkpt_data(dev);
786 T(YAFFS_TRACE_ALWAYS, (TSTR("save exit: is_checkpointed %d"TENDSTR), dev->is_checkpointed));
788 return dev->is_checkpointed;
791 int yaffs2_checkpt_restore(struct yaffs_dev *dev)
794 T(YAFFS_TRACE_CHECKPOINT, (TSTR("restore entry: is_checkpointed %d"TENDSTR), dev->is_checkpointed));
796 retval = yaffs2_rd_checkpt_data(dev);
798 if (dev->is_checkpointed) {
799 yaffs_verify_objects(dev);
800 yaffs_verify_blocks(dev);
801 yaffs_verify_free_chunks(dev);
804 T(YAFFS_TRACE_CHECKPOINT, (TSTR("restore exit: is_checkpointed %d"TENDSTR), dev->is_checkpointed));
809 int yaffs2_handle_hole(struct yaffs_obj *obj, loff_t new_size)
811 /* if new_size > old_file_size.
812 * We're going to be writing a hole.
813 * If the hole is small then write zeros otherwise write a start of hole marker.
817 loff_t old_file_size;
820 int result = YAFFS_OK;
821 struct yaffs_dev *dev = NULL;
823 u8 *local_buffer = NULL;
825 int small_increase_ok = 0;
830 if(obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
835 /* Bail out if not yaffs2 mode */
836 if(!dev->param.is_yaffs2)
839 old_file_size = obj->variant.file_variant.file_size;
841 if (new_size <= old_file_size)
844 increase = new_size - old_file_size;
846 if(increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->data_bytes_per_chunk &&
847 yaffs_check_alloc_available(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
853 local_buffer= yaffs_get_temp_buffer(dev, __LINE__);
856 /* fill hole with zero bytes */
857 int pos = old_file_size;
860 memset(local_buffer,0,dev->data_bytes_per_chunk);
861 small_increase_ok = 1;
863 while(increase > 0 && small_increase_ok){
864 this_write = increase;
865 if(this_write > dev->data_bytes_per_chunk)
866 this_write = dev->data_bytes_per_chunk;
867 written = yaffs_do_file_wr(obj,local_buffer,pos,this_write,0);
868 if(written == this_write){
870 increase -= this_write;
872 small_increase_ok = 0;
875 yaffs_release_temp_buffer(dev,local_buffer,__LINE__);
877 /* If we were out of space then reverse any chunks we've added */
878 if(!small_increase_ok)
879 yaffs_resize_file_down(obj, old_file_size);
882 if (!small_increase_ok &&
884 obj->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
885 obj->parent->obj_id != YAFFS_OBJECTID_DELETED){
886 /* Write a hole start header with the old file size */
887 yaffs_update_oh(obj, NULL, 0, 1, 0, NULL);
895 struct yaffs_block_index{
901 static int yaffs2_ybicmp(const void *a, const void *b)
903 int aseq = ((struct yaffs_block_index *)a)->seq;
904 int bseq = ((struct yaffs_block_index *)b)->seq;
905 int ablock = ((struct yaffs_block_index *)a)->block;
906 int bblock = ((struct yaffs_block_index *)b)->block;
908 return ablock - bblock;
913 int yaffs2_scan_backwards(struct yaffs_dev *dev)
915 struct yaffs_ext_tags tags;
926 enum yaffs_block_state state;
927 struct yaffs_obj *hard_list = NULL;
928 struct yaffs_block_info *bi;
930 struct yaffs_obj_hdr *oh;
931 struct yaffs_obj *in;
932 struct yaffs_obj *parent;
933 int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
941 int alloc_failed = 0;
944 struct yaffs_block_index *block_index = NULL;
945 int alt_block_index = 0;
949 ("yaffs2_scan_backwards starts intstartblk %d intendblk %d..."
950 TENDSTR), dev->internal_start_block, dev->internal_end_block));
953 dev->seq_number = YAFFS_LOWEST_SEQUENCE_NUMBER;
955 block_index = YMALLOC(n_blocks * sizeof(struct yaffs_block_index));
958 block_index = YMALLOC_ALT(n_blocks * sizeof(struct yaffs_block_index));
964 (TSTR("yaffs2_scan_backwards() could not allocate block index!" TENDSTR)));
968 dev->blocks_in_checkpt = 0;
970 chunk_data = yaffs_get_temp_buffer(dev, __LINE__);
972 /* Scan all the blocks to determine their state */
973 bi = dev->block_info;
974 for (blk = dev->internal_start_block; blk <= dev->internal_end_block; blk++) {
975 yaffs_clear_chunk_bits(dev, blk);
976 bi->pages_in_use = 0;
977 bi->soft_del_pages = 0;
979 yaffs_query_init_block_state(dev, blk, &state, &seq_number);
981 bi->block_state = state;
982 bi->seq_number = seq_number;
984 if (bi->seq_number == YAFFS_SEQUENCE_CHECKPOINT_DATA)
985 bi->block_state = state = YAFFS_BLOCK_STATE_CHECKPOINT;
986 if (bi->seq_number == YAFFS_SEQUENCE_BAD_BLOCK)
987 bi->block_state = state = YAFFS_BLOCK_STATE_DEAD;
989 T(YAFFS_TRACE_SCAN_DEBUG,
990 (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
994 if (state == YAFFS_BLOCK_STATE_CHECKPOINT) {
995 dev->blocks_in_checkpt++;
997 } else if (state == YAFFS_BLOCK_STATE_DEAD) {
998 T(YAFFS_TRACE_BAD_BLOCKS,
999 (TSTR("block %d is bad" TENDSTR), blk));
1000 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
1001 T(YAFFS_TRACE_SCAN_DEBUG,
1002 (TSTR("Block empty " TENDSTR)));
1003 dev->n_erased_blocks++;
1004 dev->n_free_chunks += dev->param.chunks_per_block;
1005 } else if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1007 /* Determine the highest sequence number */
1008 if (seq_number >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1009 seq_number < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1011 block_index[n_to_scan].seq = seq_number;
1012 block_index[n_to_scan].block = blk;
1016 if (seq_number >= dev->seq_number)
1017 dev->seq_number = seq_number;
1019 /* TODO: Nasty sequence number! */
1022 ("Block scanning block %d has bad sequence number %d"
1023 TENDSTR), blk, seq_number));
1031 (TSTR("%d blocks to be sorted..." TENDSTR), n_to_scan));
1037 /* Sort the blocks by sequence number*/
1038 yaffs_sort(block_index, n_to_scan, sizeof(struct yaffs_block_index), yaffs2_ybicmp);
1042 T(YAFFS_TRACE_SCAN, (TSTR("...done" TENDSTR)));
1044 /* Now scan the blocks looking at the data. */
1046 end_iter = n_to_scan - 1;
1047 T(YAFFS_TRACE_SCAN_DEBUG,
1048 (TSTR("%d blocks to be scanned" TENDSTR), n_to_scan));
1050 /* For each block.... backwards */
1051 for (block_iter = end_iter; !alloc_failed && block_iter >= start_iter;
1053 /* Cooperative multitasking! This loop can run for so
1054 long that watchdog timers expire. */
1057 /* get the block to scan in the correct order */
1058 blk = block_index[block_iter].block;
1060 bi = yaffs_get_block_info(dev, blk);
1063 state = bi->block_state;
1067 /* For each chunk in each block that needs scanning.... */
1069 for (c = dev->param.chunks_per_block - 1;
1070 !alloc_failed && c >= 0 &&
1071 (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1072 state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
1073 /* Scan backwards...
1074 * Read the tags and decide what to do
1077 chunk = blk * dev->param.chunks_per_block + c;
1079 result = yaffs_rd_chunk_tags_nand(dev, chunk, NULL,
1082 /* Let's have a good look at this chunk... */
1084 if (!tags.chunk_used) {
1085 /* An unassigned chunk in the block.
1086 * If there are used chunks after this one, then
1087 * it is a chunk that was skipped due to failing the erased
1088 * check. Just skip it so that it can be deleted.
1089 * But, more typically, We get here when this is an unallocated
1090 * chunk and his means that either the block is empty or
1091 * this is the one being allocated from
1095 /* This is a chunk that was skipped due to failing the erased check */
1096 } else if (c == 0) {
1097 /* We're looking at the first chunk in the block so the block is unused */
1098 state = YAFFS_BLOCK_STATE_EMPTY;
1099 dev->n_erased_blocks++;
1101 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1102 state == YAFFS_BLOCK_STATE_ALLOCATING) {
1103 if (dev->seq_number == bi->seq_number) {
1104 /* this is the block being allocated from */
1108 (" Allocating from %d %d"
1111 state = YAFFS_BLOCK_STATE_ALLOCATING;
1112 dev->alloc_block = blk;
1113 dev->alloc_page = c;
1114 dev->alloc_block_finder = blk;
1116 /* This is a partially written block that is not
1117 * the current allocation block.
1121 (TSTR("Partially written block %d detected" TENDSTR),
1127 dev->n_free_chunks++;
1129 } else if (tags.ecc_result == YAFFS_ECC_RESULT_UNFIXED) {
1131 (TSTR(" Unfixed ECC in chunk(%d:%d), chunk ignored"TENDSTR),
1134 dev->n_free_chunks++;
1136 } else if (tags.obj_id > YAFFS_MAX_OBJECT_ID ||
1137 tags.chunk_id > YAFFS_MAX_CHUNK_ID ||
1138 (tags.chunk_id > 0 && tags.n_bytes > dev->data_bytes_per_chunk) ||
1139 tags.seq_number != bi->seq_number ) {
1141 (TSTR("Chunk (%d:%d) with bad tags:obj = %d, chunk_id = %d, n_bytes = %d, ignored"TENDSTR),
1142 blk, c,tags.obj_id, tags.chunk_id, tags.n_bytes));
1144 dev->n_free_chunks++;
1146 } else if (tags.chunk_id > 0) {
1147 /* chunk_id > 0 so it is a data chunk... */
1148 unsigned int endpos;
1150 (tags.chunk_id - 1) * dev->data_bytes_per_chunk;
1155 yaffs_set_chunk_bit(dev, blk, c);
1158 in = yaffs_find_or_create_by_number(dev,
1161 YAFFS_OBJECT_TYPE_FILE);
1168 in->variant_type == YAFFS_OBJECT_TYPE_FILE
1169 && chunk_base < in->variant.file_variant.shrink_size) {
1170 /* This has not been invalidated by a resize */
1171 if (!yaffs_put_chunk_in_file(in, tags.chunk_id, chunk, -1)) {
1175 /* File size is calculated by looking at the data chunks if we have not
1176 * seen an object header yet. Stop this practice once we find an object header.
1178 endpos = chunk_base + tags.n_bytes;
1180 if (!in->valid && /* have not got an object header yet */
1181 in->variant.file_variant.scanned_size < endpos) {
1182 in->variant.file_variant.scanned_size = endpos;
1183 in->variant.file_variant.file_size = endpos;
1187 /* This chunk has been invalidated by a resize, or a past file deletion
1188 * so delete the chunk*/
1189 yaffs_chunk_del(dev, chunk, 1, __LINE__);
1193 /* chunk_id == 0, so it is an ObjectHeader.
1194 * Thus, we read in the object header and make the object
1198 yaffs_set_chunk_bit(dev, blk, c);
1204 if (tags.extra_available) {
1205 in = yaffs_find_or_create_by_number(dev,
1207 tags.extra_obj_type);
1213 (!in->valid && dev->param.disable_lazy_load) ||
1214 tags.extra_shadows ||
1216 (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1217 tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND))) {
1219 /* If we don't have valid info then we need to read the chunk
1220 * TODO In future we can probably defer reading the chunk and
1221 * living with invalid data until needed.
1224 result = yaffs_rd_chunk_tags_nand(dev,
1229 oh = (struct yaffs_obj_hdr *) chunk_data;
1231 if (dev->param.inband_tags) {
1232 /* Fix up the header if they got corrupted by inband tags */
1233 oh->shadows_obj = oh->inband_shadowed_obj_id;
1234 oh->is_shrink = oh->inband_is_shrink;
1238 in = yaffs_find_or_create_by_number(dev, tags.obj_id, oh->type);
1246 /* TODO Hoosterman we have a problem! */
1247 T(YAFFS_TRACE_ERROR,
1249 ("yaffs tragedy: Could not make object for object %d at chunk %d during scan"
1250 TENDSTR), tags.obj_id, chunk));
1255 /* We have already filled this one.
1256 * We have a duplicate that will be discarded, but
1257 * we first have to suck out resize info if it is a file.
1260 if ((in->variant_type == YAFFS_OBJECT_TYPE_FILE) &&
1262 oh->type == YAFFS_OBJECT_TYPE_FILE) ||
1263 (tags.extra_available &&
1264 tags.extra_obj_type == YAFFS_OBJECT_TYPE_FILE))) {
1266 (oh) ? oh->file_size : tags.
1270 parent_obj_id : tags.
1275 (oh) ? oh->is_shrink : tags.
1278 /* If it is deleted (unlinked at start also means deleted)
1279 * we treat the file size as being zeroed at this point.
1281 if (parent_obj_id ==
1282 YAFFS_OBJECTID_DELETED
1284 YAFFS_OBJECTID_UNLINKED) {
1289 if (is_shrink && in->variant.file_variant.shrink_size > this_size)
1290 in->variant.file_variant.shrink_size = this_size;
1293 bi->has_shrink_hdr = 1;
1296 /* Use existing - destroy this one. */
1297 yaffs_chunk_del(dev, chunk, 1, __LINE__);
1301 if (!in->valid && in->variant_type !=
1302 (oh ? oh->type : tags.extra_obj_type))
1303 T(YAFFS_TRACE_ERROR, (
1304 TSTR("yaffs tragedy: Bad object type, "
1305 TCONT("%d != %d, for object %d at chunk ")
1306 TCONT("%d during scan")
1308 oh->type : tags.extra_obj_type,
1309 in->variant_type, tags.obj_id,
1313 (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1315 YAFFS_OBJECTID_LOSTNFOUND)) {
1316 /* We only load some info, don't fiddle with directory structure */
1321 in->yst_mode = oh->yst_mode;
1322 yaffs_load_attribs(in, oh);
1323 in->lazy_loaded = 0;
1325 in->lazy_loaded = 1;
1327 in->hdr_chunk = chunk;
1329 } else if (!in->valid) {
1330 /* we need to load this info */
1333 in->hdr_chunk = chunk;
1336 in->variant_type = oh->type;
1338 in->yst_mode = oh->yst_mode;
1339 yaffs_load_attribs(in, oh);
1341 if (oh->shadows_obj > 0)
1342 yaffs_handle_shadowed_obj(dev,
1349 yaffs_set_obj_name_from_oh(in, oh);
1351 yaffs_find_or_create_by_number
1352 (dev, oh->parent_obj_id,
1353 YAFFS_OBJECT_TYPE_DIRECTORY);
1355 file_size = oh->file_size;
1356 is_shrink = oh->is_shrink;
1357 equiv_id = oh->equiv_id;
1360 in->variant_type = tags.extra_obj_type;
1362 yaffs_find_or_create_by_number
1363 (dev, tags.extra_parent_id,
1364 YAFFS_OBJECT_TYPE_DIRECTORY);
1365 file_size = tags.extra_length;
1366 is_shrink = tags.extra_is_shrink;
1367 equiv_id = tags.extra_equiv_id;
1368 in->lazy_loaded = 1;
1376 /* directory stuff...
1380 if (parent && parent->variant_type ==
1381 YAFFS_OBJECT_TYPE_UNKNOWN) {
1382 /* Set up as a directory */
1383 parent->variant_type =
1384 YAFFS_OBJECT_TYPE_DIRECTORY;
1385 INIT_LIST_HEAD(&parent->variant.
1388 } else if (!parent || parent->variant_type !=
1389 YAFFS_OBJECT_TYPE_DIRECTORY) {
1390 /* Hoosterman, another problem....
1391 * We're trying to use a non-directory as a directory
1394 T(YAFFS_TRACE_ERROR,
1396 ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1398 parent = dev->lost_n_found;
1401 yaffs_add_obj_to_dir(parent, in);
1403 is_unlinked = (parent == dev->del_dir) ||
1404 (parent == dev->unlinked_dir);
1407 /* Mark the block as having a shrink header */
1408 bi->has_shrink_hdr = 1;
1411 /* Note re hardlinks.
1412 * Since we might scan a hardlink before its equivalent object is scanned
1413 * we put them all in a list.
1414 * After scanning is complete, we should have all the objects, so we run
1415 * through this list and fix up all the chains.
1418 switch (in->variant_type) {
1419 case YAFFS_OBJECT_TYPE_UNKNOWN:
1420 /* Todo got a problem */
1422 case YAFFS_OBJECT_TYPE_FILE:
1424 if (in->variant.file_variant.
1425 scanned_size < file_size) {
1426 /* This covers the case where the file size is greater
1427 * than where the data is
1428 * This will happen if the file is resized to be larger
1429 * than its current data extents.
1431 in->variant.file_variant.file_size = file_size;
1432 in->variant.file_variant.scanned_size = file_size;
1435 if (in->variant.file_variant.shrink_size > file_size)
1436 in->variant.file_variant.shrink_size = file_size;
1440 case YAFFS_OBJECT_TYPE_HARDLINK:
1442 in->variant.hardlink_variant.equiv_id =
1444 in->hard_links.next =
1445 (struct list_head *) hard_list;
1449 case YAFFS_OBJECT_TYPE_DIRECTORY:
1452 case YAFFS_OBJECT_TYPE_SPECIAL:
1455 case YAFFS_OBJECT_TYPE_SYMLINK:
1457 in->variant.symlink_variant.alias =
1458 yaffs_clone_str(oh->alias);
1459 if (!in->variant.symlink_variant.alias)
1469 } /* End of scanning for each chunk */
1471 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1472 /* If we got this far while scanning, then the block is fully allocated. */
1473 state = YAFFS_BLOCK_STATE_FULL;
1477 bi->block_state = state;
1479 /* Now let's see if it was dirty */
1480 if (bi->pages_in_use == 0 &&
1481 !bi->has_shrink_hdr &&
1482 bi->block_state == YAFFS_BLOCK_STATE_FULL) {
1483 yaffs_block_became_dirty(dev, blk);
1488 yaffs_skip_rest_of_block(dev);
1490 if (alt_block_index)
1491 YFREE_ALT(block_index);
1495 /* Ok, we've done all the scanning.
1496 * Fix up the hard link chains.
1497 * We should now have scanned all the objects, now it's time to add these
1500 yaffs_link_fixup(dev, hard_list);
1503 yaffs_release_temp_buffer(dev, chunk_data, __LINE__);
1508 T(YAFFS_TRACE_SCAN, (TSTR("yaffs2_scan_backwards ends" TENDSTR)));