xref: /openbmc/u-boot/fs/yaffs2/yaffs_yaffs2.c (revision a4884831)
1 /*
2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
3  *
4  * Copyright (C) 2002-2011 Aleph One Ltd.
5  *   for Toby Churchill Ltd and Brightstar Engineering
6  *
7  * Created by Charles Manning <charles@aleph1.co.uk>
8  *
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.
12  */
13 
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"
24 
25 /*
26  * Checkpoints are really no benefit on very small partitions.
27  *
28  * To save space on small partitions don't bother with checkpoints unless
29  * the partition is at least this big.
30  */
31 #define YAFFS_CHECKPOINT_MIN_BLOCKS 60
32 #define YAFFS_SMALL_HOLE_THRESHOLD 4
33 
34 /*
35  * Oldest Dirty Sequence Number handling.
36  */
37 
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.
41  */
42 void yaffs_calc_oldest_dirty_seq(struct yaffs_dev *dev)
43 {
44 	int i;
45 	unsigned seq;
46 	unsigned block_no = 0;
47 	struct yaffs_block_info *b;
48 
49 	if (!dev->param.is_yaffs2)
50 		return;
51 
52 	/* Find the oldest dirty sequence number. */
53 	seq = dev->seq_number + 1;
54 	b = dev->block_info;
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) {
60 			seq = b->seq_number;
61 			block_no = i;
62 		}
63 		b++;
64 	}
65 
66 	if (block_no) {
67 		dev->oldest_dirty_seq = seq;
68 		dev->oldest_dirty_block = block_no;
69 	}
70 }
71 
72 void yaffs2_find_oldest_dirty_seq(struct yaffs_dev *dev)
73 {
74 	if (!dev->param.is_yaffs2)
75 		return;
76 
77 	if (!dev->oldest_dirty_seq)
78 		yaffs_calc_oldest_dirty_seq(dev);
79 }
80 
81 /*
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.
86  */
87 void yaffs2_clear_oldest_dirty_seq(struct yaffs_dev *dev,
88 				   struct yaffs_block_info *bi)
89 {
90 
91 	if (!dev->param.is_yaffs2)
92 		return;
93 
94 	if (!bi || bi->seq_number == dev->oldest_dirty_seq) {
95 		dev->oldest_dirty_seq = 0;
96 		dev->oldest_dirty_block = 0;
97 	}
98 }
99 
100 /*
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.
104  */
105 void yaffs2_update_oldest_dirty_seq(struct yaffs_dev *dev, unsigned block_no,
106 				    struct yaffs_block_info *bi)
107 {
108 	if (!dev->param.is_yaffs2)
109 		return;
110 
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;
115 		}
116 	}
117 }
118 
119 int yaffs_block_ok_for_gc(struct yaffs_dev *dev, struct yaffs_block_info *bi)
120 {
121 
122 	if (!dev->param.is_yaffs2)
123 		return 1;	/* disqualification only applies to yaffs2. */
124 
125 	if (!bi->has_shrink_hdr)
126 		return 1;	/* can gc */
127 
128 	yaffs2_find_oldest_dirty_seq(dev);
129 
130 	/* Can't do gc of this block if there are any blocks older than this
131 	 * one that have discarded pages.
132 	 */
133 	return (bi->seq_number <= dev->oldest_dirty_seq);
134 }
135 
136 /*
137  * yaffs2_find_refresh_block()
138  * periodically finds the oldest full block by sequence number for refreshing.
139  * Only for yaffs2.
140  */
141 u32 yaffs2_find_refresh_block(struct yaffs_dev *dev)
142 {
143 	u32 b;
144 	u32 oldest = 0;
145 	u32 oldest_seq = 0;
146 	struct yaffs_block_info *bi;
147 
148 	if (!dev->param.is_yaffs2)
149 		return oldest;
150 
151 	/*
152 	 * If refresh period < 10 then refreshing is disabled.
153 	 */
154 	if (dev->param.refresh_period < 10)
155 		return oldest;
156 
157 	/*
158 	 * Fix broken values.
159 	 */
160 	if (dev->refresh_skip > dev->param.refresh_period)
161 		dev->refresh_skip = dev->param.refresh_period;
162 
163 	if (dev->refresh_skip > 0)
164 		return oldest;
165 
166 	/*
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.
170 	 */
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++) {
175 
176 		if (bi->block_state == YAFFS_BLOCK_STATE_FULL) {
177 
178 			if (oldest < 1 || bi->seq_number < oldest_seq) {
179 				oldest = b;
180 				oldest_seq = bi->seq_number;
181 			}
182 		}
183 		bi++;
184 	}
185 
186 	if (oldest > 0) {
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);
190 	}
191 
192 	return oldest;
193 }
194 
195 int yaffs2_checkpt_required(struct yaffs_dev *dev)
196 {
197 	int nblocks;
198 
199 	if (!dev->param.is_yaffs2)
200 		return 0;
201 
202 	nblocks = dev->internal_end_block - dev->internal_start_block + 1;
203 
204 	return !dev->param.skip_checkpt_wr &&
205 	    !dev->read_only && (nblocks >= YAFFS_CHECKPOINT_MIN_BLOCKS);
206 }
207 
208 int yaffs_calc_checkpt_blocks_required(struct yaffs_dev *dev)
209 {
210 	int retval;
211 	int n_bytes = 0;
212 	int n_blocks;
213 	int dev_blocks;
214 
215 	if (!dev->param.is_yaffs2)
216 		return 0;
217 
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;
225 		n_bytes +=
226 		    (sizeof(struct yaffs_checkpt_obj) + sizeof(u32)) *
227 		    dev->n_obj;
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 */
231 
232 		/* Round up and add 2 blocks to allow for some bad blocks,
233 		 * so add 3 */
234 
235 		n_blocks =
236 		    (n_bytes /
237 		     (dev->data_bytes_per_chunk *
238 		      dev->param.chunks_per_block)) + 3;
239 
240 		dev->checkpoint_blocks_required = n_blocks;
241 	}
242 
243 	retval = dev->checkpoint_blocks_required - dev->blocks_in_checkpt;
244 	if (retval < 0)
245 		retval = 0;
246 	return retval;
247 }
248 
249 /*--------------------- Checkpointing --------------------*/
250 
251 static int yaffs2_wr_checkpt_validity_marker(struct yaffs_dev *dev, int head)
252 {
253 	struct yaffs_checkpt_validity cp;
254 
255 	memset(&cp, 0, sizeof(cp));
256 
257 	cp.struct_type = sizeof(cp);
258 	cp.magic = YAFFS_MAGIC;
259 	cp.version = YAFFS_CHECKPOINT_VERSION;
260 	cp.head = (head) ? 1 : 0;
261 
262 	return (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp)) ? 1 : 0;
263 }
264 
265 static int yaffs2_rd_checkpt_validity_marker(struct yaffs_dev *dev, int head)
266 {
267 	struct yaffs_checkpt_validity cp;
268 	int ok;
269 
270 	ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
271 
272 	if (ok)
273 		ok = (cp.struct_type == sizeof(cp)) &&
274 		    (cp.magic == YAFFS_MAGIC) &&
275 		    (cp.version == YAFFS_CHECKPOINT_VERSION) &&
276 		    (cp.head == ((head) ? 1 : 0));
277 	return ok ? 1 : 0;
278 }
279 
280 static void yaffs2_dev_to_checkpt_dev(struct yaffs_checkpt_dev *cp,
281 				      struct yaffs_dev *dev)
282 {
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;
287 
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;
292 
293 }
294 
295 static void yaffs_checkpt_dev_to_dev(struct yaffs_dev *dev,
296 				     struct yaffs_checkpt_dev *cp)
297 {
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;
302 
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;
307 }
308 
309 static int yaffs2_wr_checkpt_dev(struct yaffs_dev *dev)
310 {
311 	struct yaffs_checkpt_dev cp;
312 	u32 n_bytes;
313 	u32 n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
314 	int ok;
315 
316 	/* Write device runtime values */
317 	yaffs2_dev_to_checkpt_dev(&cp, dev);
318 	cp.struct_type = sizeof(cp);
319 
320 	ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
321 	if (!ok)
322 		return 0;
323 
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);
327 	if (!ok)
328 		return 0;
329 
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);
333 
334 	return ok ? 1 : 0;
335 }
336 
337 static int yaffs2_rd_checkpt_dev(struct yaffs_dev *dev)
338 {
339 	struct yaffs_checkpt_dev cp;
340 	u32 n_bytes;
341 	u32 n_blocks =
342 	    (dev->internal_end_block - dev->internal_start_block + 1);
343 	int ok;
344 
345 	ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
346 	if (!ok)
347 		return 0;
348 
349 	if (cp.struct_type != sizeof(cp))
350 		return 0;
351 
352 	yaffs_checkpt_dev_to_dev(dev, &cp);
353 
354 	n_bytes = n_blocks * sizeof(struct yaffs_block_info);
355 
356 	ok = (yaffs2_checkpt_rd(dev, dev->block_info, n_bytes) == n_bytes);
357 
358 	if (!ok)
359 		return 0;
360 
361 	n_bytes = n_blocks * dev->chunk_bit_stride;
362 
363 	ok = (yaffs2_checkpt_rd(dev, dev->chunk_bits, n_bytes) == n_bytes);
364 
365 	return ok ? 1 : 0;
366 }
367 
368 static void yaffs2_obj_checkpt_obj(struct yaffs_checkpt_obj *cp,
369 				   struct yaffs_obj *obj)
370 {
371 	cp->obj_id = obj->obj_id;
372 	cp->parent_id = (obj->parent) ? obj->parent->obj_id : 0;
373 	cp->hdr_chunk = obj->hdr_chunk;
374 	cp->variant_type = obj->variant_type;
375 	cp->deleted = obj->deleted;
376 	cp->soft_del = obj->soft_del;
377 	cp->unlinked = obj->unlinked;
378 	cp->fake = obj->fake;
379 	cp->rename_allowed = obj->rename_allowed;
380 	cp->unlink_allowed = obj->unlink_allowed;
381 	cp->serial = obj->serial;
382 	cp->n_data_chunks = obj->n_data_chunks;
383 
384 	if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
385 		cp->size_or_equiv_obj = obj->variant.file_variant.file_size;
386 	else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
387 		cp->size_or_equiv_obj = obj->variant.hardlink_variant.equiv_id;
388 }
389 
390 static int yaffs2_checkpt_obj_to_obj(struct yaffs_obj *obj,
391 				     struct yaffs_checkpt_obj *cp)
392 {
393 	struct yaffs_obj *parent;
394 
395 	if (obj->variant_type != cp->variant_type) {
396 		yaffs_trace(YAFFS_TRACE_ERROR,
397 			"Checkpoint read object %d type %d chunk %d does not match existing object type %d",
398 			cp->obj_id, cp->variant_type, cp->hdr_chunk,
399 			obj->variant_type);
400 		return 0;
401 	}
402 
403 	obj->obj_id = cp->obj_id;
404 
405 	if (cp->parent_id)
406 		parent = yaffs_find_or_create_by_number(obj->my_dev,
407 						cp->parent_id,
408 						YAFFS_OBJECT_TYPE_DIRECTORY);
409 	else
410 		parent = NULL;
411 
412 	if (parent) {
413 		if (parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
414 			yaffs_trace(YAFFS_TRACE_ALWAYS,
415 				"Checkpoint read object %d parent %d type %d chunk %d Parent type, %d, not directory",
416 				cp->obj_id, cp->parent_id,
417 				cp->variant_type, cp->hdr_chunk,
418 				parent->variant_type);
419 			return 0;
420 		}
421 		yaffs_add_obj_to_dir(parent, obj);
422 	}
423 
424 	obj->hdr_chunk = cp->hdr_chunk;
425 	obj->variant_type = cp->variant_type;
426 	obj->deleted = cp->deleted;
427 	obj->soft_del = cp->soft_del;
428 	obj->unlinked = cp->unlinked;
429 	obj->fake = cp->fake;
430 	obj->rename_allowed = cp->rename_allowed;
431 	obj->unlink_allowed = cp->unlink_allowed;
432 	obj->serial = cp->serial;
433 	obj->n_data_chunks = cp->n_data_chunks;
434 
435 	if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
436 		obj->variant.file_variant.file_size = cp->size_or_equiv_obj;
437 	else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
438 		obj->variant.hardlink_variant.equiv_id = cp->size_or_equiv_obj;
439 
440 	if (obj->hdr_chunk > 0)
441 		obj->lazy_loaded = 1;
442 	return 1;
443 }
444 
445 static int yaffs2_checkpt_tnode_worker(struct yaffs_obj *in,
446 				       struct yaffs_tnode *tn, u32 level,
447 				       int chunk_offset)
448 {
449 	int i;
450 	struct yaffs_dev *dev = in->my_dev;
451 	int ok = 1;
452 	u32 base_offset;
453 
454 	if (!tn)
455 		return 1;
456 
457 	if (level > 0) {
458 		for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) {
459 			if (!tn->internal[i])
460 				continue;
461 			ok = yaffs2_checkpt_tnode_worker(in,
462 				 tn->internal[i],
463 				 level - 1,
464 				 (chunk_offset <<
465 				  YAFFS_TNODES_INTERNAL_BITS) + i);
466 		}
467 		return ok;
468 	}
469 
470 	/* Level 0 tnode */
471 	base_offset = chunk_offset << YAFFS_TNODES_LEVEL0_BITS;
472 	ok = (yaffs2_checkpt_wr(dev, &base_offset, sizeof(base_offset)) ==
473 			sizeof(base_offset));
474 	if (ok)
475 		ok = (yaffs2_checkpt_wr(dev, tn, dev->tnode_size) ==
476 			dev->tnode_size);
477 
478 	return ok;
479 }
480 
481 static int yaffs2_wr_checkpt_tnodes(struct yaffs_obj *obj)
482 {
483 	u32 end_marker = ~0;
484 	int ok = 1;
485 
486 	if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
487 		return ok;
488 
489 	ok = yaffs2_checkpt_tnode_worker(obj,
490 					 obj->variant.file_variant.top,
491 					 obj->variant.file_variant.
492 					 top_level, 0);
493 	if (ok)
494 		ok = (yaffs2_checkpt_wr(obj->my_dev, &end_marker,
495 				sizeof(end_marker)) == sizeof(end_marker));
496 
497 	return ok ? 1 : 0;
498 }
499 
500 static int yaffs2_rd_checkpt_tnodes(struct yaffs_obj *obj)
501 {
502 	u32 base_chunk;
503 	int ok = 1;
504 	struct yaffs_dev *dev = obj->my_dev;
505 	struct yaffs_file_var *file_stuct_ptr = &obj->variant.file_variant;
506 	struct yaffs_tnode *tn;
507 	int nread = 0;
508 
509 	ok = (yaffs2_checkpt_rd(dev, &base_chunk, sizeof(base_chunk)) ==
510 	      sizeof(base_chunk));
511 
512 	while (ok && (~base_chunk)) {
513 		nread++;
514 		/* Read level 0 tnode */
515 
516 		tn = yaffs_get_tnode(dev);
517 		if (tn)
518 			ok = (yaffs2_checkpt_rd(dev, tn, dev->tnode_size) ==
519 				dev->tnode_size);
520 		else
521 			ok = 0;
522 
523 		if (tn && ok)
524 			ok = yaffs_add_find_tnode_0(dev,
525 						    file_stuct_ptr,
526 						    base_chunk, tn) ? 1 : 0;
527 
528 		if (ok)
529 			ok = (yaffs2_checkpt_rd
530 			      (dev, &base_chunk,
531 			       sizeof(base_chunk)) == sizeof(base_chunk));
532 	}
533 
534 	yaffs_trace(YAFFS_TRACE_CHECKPOINT,
535 		"Checkpoint read tnodes %d records, last %d. ok %d",
536 		nread, base_chunk, ok);
537 
538 	return ok ? 1 : 0;
539 }
540 
541 static int yaffs2_wr_checkpt_objs(struct yaffs_dev *dev)
542 {
543 	struct yaffs_obj *obj;
544 	struct yaffs_checkpt_obj cp;
545 	int i;
546 	int ok = 1;
547 	struct list_head *lh;
548 
549 	/* Iterate through the objects in each hash entry,
550 	 * dumping them to the checkpointing stream.
551 	 */
552 
553 	for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
554 		list_for_each(lh, &dev->obj_bucket[i].list) {
555 			obj = list_entry(lh, struct yaffs_obj, hash_link);
556 			if (!obj->defered_free) {
557 				yaffs2_obj_checkpt_obj(&cp, obj);
558 				cp.struct_type = sizeof(cp);
559 
560 				yaffs_trace(YAFFS_TRACE_CHECKPOINT,
561 					"Checkpoint write object %d parent %d type %d chunk %d obj addr %p",
562 					cp.obj_id, cp.parent_id,
563 					cp.variant_type, cp.hdr_chunk, obj);
564 
565 				ok = (yaffs2_checkpt_wr(dev, &cp,
566 						sizeof(cp)) == sizeof(cp));
567 
568 				if (ok &&
569 					obj->variant_type ==
570 					YAFFS_OBJECT_TYPE_FILE)
571 					ok = yaffs2_wr_checkpt_tnodes(obj);
572 			}
573 		}
574 	}
575 
576 	/* Dump end of list */
577 	memset(&cp, 0xff, sizeof(struct yaffs_checkpt_obj));
578 	cp.struct_type = sizeof(cp);
579 
580 	if (ok)
581 		ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
582 
583 	return ok ? 1 : 0;
584 }
585 
586 static int yaffs2_rd_checkpt_objs(struct yaffs_dev *dev)
587 {
588 	struct yaffs_obj *obj;
589 	struct yaffs_checkpt_obj cp;
590 	int ok = 1;
591 	int done = 0;
592 	LIST_HEAD(hard_list);
593 
594 
595 	while (ok && !done) {
596 		ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
597 		if (cp.struct_type != sizeof(cp)) {
598 			yaffs_trace(YAFFS_TRACE_CHECKPOINT,
599 				"struct size %d instead of %d ok %d",
600 				cp.struct_type, (int)sizeof(cp), ok);
601 			ok = 0;
602 		}
603 
604 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
605 			"Checkpoint read object %d parent %d type %d chunk %d ",
606 			cp.obj_id, cp.parent_id, cp.variant_type,
607 			cp.hdr_chunk);
608 
609 		if (ok && cp.obj_id == ~0) {
610 			done = 1;
611 		} else if (ok) {
612 			obj =
613 			    yaffs_find_or_create_by_number(dev, cp.obj_id,
614 							   cp.variant_type);
615 			if (obj) {
616 				ok = yaffs2_checkpt_obj_to_obj(obj, &cp);
617 				if (!ok)
618 					break;
619 				if (obj->variant_type ==
620 					YAFFS_OBJECT_TYPE_FILE) {
621 					ok = yaffs2_rd_checkpt_tnodes(obj);
622 				} else if (obj->variant_type ==
623 					YAFFS_OBJECT_TYPE_HARDLINK) {
624 					list_add(&obj->hard_links, &hard_list);
625 				}
626 			} else {
627 				ok = 0;
628 			}
629 		}
630 	}
631 
632 	if (ok)
633 		yaffs_link_fixup(dev, &hard_list);
634 
635 	return ok ? 1 : 0;
636 }
637 
638 static int yaffs2_wr_checkpt_sum(struct yaffs_dev *dev)
639 {
640 	u32 checkpt_sum;
641 	int ok;
642 
643 	yaffs2_get_checkpt_sum(dev, &checkpt_sum);
644 
645 	ok = (yaffs2_checkpt_wr(dev, &checkpt_sum, sizeof(checkpt_sum)) ==
646 		sizeof(checkpt_sum));
647 
648 	if (!ok)
649 		return 0;
650 
651 	return 1;
652 }
653 
654 static int yaffs2_rd_checkpt_sum(struct yaffs_dev *dev)
655 {
656 	u32 checkpt_sum0;
657 	u32 checkpt_sum1;
658 	int ok;
659 
660 	yaffs2_get_checkpt_sum(dev, &checkpt_sum0);
661 
662 	ok = (yaffs2_checkpt_rd(dev, &checkpt_sum1, sizeof(checkpt_sum1)) ==
663 		sizeof(checkpt_sum1));
664 
665 	if (!ok)
666 		return 0;
667 
668 	if (checkpt_sum0 != checkpt_sum1)
669 		return 0;
670 
671 	return 1;
672 }
673 
674 static int yaffs2_wr_checkpt_data(struct yaffs_dev *dev)
675 {
676 	int ok = 1;
677 
678 	if (!yaffs2_checkpt_required(dev)) {
679 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
680 			"skipping checkpoint write");
681 		ok = 0;
682 	}
683 
684 	if (ok)
685 		ok = yaffs2_checkpt_open(dev, 1);
686 
687 	if (ok) {
688 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
689 			"write checkpoint validity");
690 		ok = yaffs2_wr_checkpt_validity_marker(dev, 1);
691 	}
692 	if (ok) {
693 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
694 			"write checkpoint device");
695 		ok = yaffs2_wr_checkpt_dev(dev);
696 	}
697 	if (ok) {
698 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
699 			"write checkpoint objects");
700 		ok = yaffs2_wr_checkpt_objs(dev);
701 	}
702 	if (ok) {
703 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
704 			"write checkpoint validity");
705 		ok = yaffs2_wr_checkpt_validity_marker(dev, 0);
706 	}
707 
708 	if (ok)
709 		ok = yaffs2_wr_checkpt_sum(dev);
710 
711 	if (!yaffs_checkpt_close(dev))
712 		ok = 0;
713 
714 	if (ok)
715 		dev->is_checkpointed = 1;
716 	else
717 		dev->is_checkpointed = 0;
718 
719 	return dev->is_checkpointed;
720 }
721 
722 static int yaffs2_rd_checkpt_data(struct yaffs_dev *dev)
723 {
724 	int ok = 1;
725 
726 	if (!dev->param.is_yaffs2)
727 		ok = 0;
728 
729 	if (ok && dev->param.skip_checkpt_rd) {
730 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
731 			"skipping checkpoint read");
732 		ok = 0;
733 	}
734 
735 	if (ok)
736 		ok = yaffs2_checkpt_open(dev, 0); /* open for read */
737 
738 	if (ok) {
739 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
740 			"read checkpoint validity");
741 		ok = yaffs2_rd_checkpt_validity_marker(dev, 1);
742 	}
743 	if (ok) {
744 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
745 			"read checkpoint device");
746 		ok = yaffs2_rd_checkpt_dev(dev);
747 	}
748 	if (ok) {
749 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
750 			"read checkpoint objects");
751 		ok = yaffs2_rd_checkpt_objs(dev);
752 	}
753 	if (ok) {
754 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
755 			"read checkpoint validity");
756 		ok = yaffs2_rd_checkpt_validity_marker(dev, 0);
757 	}
758 
759 	if (ok) {
760 		ok = yaffs2_rd_checkpt_sum(dev);
761 		yaffs_trace(YAFFS_TRACE_CHECKPOINT,
762 			"read checkpoint checksum %d", ok);
763 	}
764 
765 	if (!yaffs_checkpt_close(dev))
766 		ok = 0;
767 
768 	if (ok)
769 		dev->is_checkpointed = 1;
770 	else
771 		dev->is_checkpointed = 0;
772 
773 	return ok ? 1 : 0;
774 }
775 
776 void yaffs2_checkpt_invalidate(struct yaffs_dev *dev)
777 {
778 	if (dev->is_checkpointed || dev->blocks_in_checkpt > 0) {
779 		dev->is_checkpointed = 0;
780 		yaffs2_checkpt_invalidate_stream(dev);
781 	}
782 	if (dev->param.sb_dirty_fn)
783 		dev->param.sb_dirty_fn(dev);
784 }
785 
786 int yaffs_checkpoint_save(struct yaffs_dev *dev)
787 {
788 	yaffs_trace(YAFFS_TRACE_CHECKPOINT,
789 		"save entry: is_checkpointed %d",
790 		dev->is_checkpointed);
791 
792 	yaffs_verify_objects(dev);
793 	yaffs_verify_blocks(dev);
794 	yaffs_verify_free_chunks(dev);
795 
796 	if (!dev->is_checkpointed) {
797 		yaffs2_checkpt_invalidate(dev);
798 		yaffs2_wr_checkpt_data(dev);
799 	}
800 
801 	yaffs_trace(YAFFS_TRACE_CHECKPOINT | YAFFS_TRACE_MOUNT,
802 		"save exit: is_checkpointed %d",
803 		dev->is_checkpointed);
804 
805 	return dev->is_checkpointed;
806 }
807 
808 int yaffs2_checkpt_restore(struct yaffs_dev *dev)
809 {
810 	int retval;
811 
812 	yaffs_trace(YAFFS_TRACE_CHECKPOINT,
813 		"restore entry: is_checkpointed %d",
814 		dev->is_checkpointed);
815 
816 	retval = yaffs2_rd_checkpt_data(dev);
817 
818 	if (dev->is_checkpointed) {
819 		yaffs_verify_objects(dev);
820 		yaffs_verify_blocks(dev);
821 		yaffs_verify_free_chunks(dev);
822 	}
823 
824 	yaffs_trace(YAFFS_TRACE_CHECKPOINT,
825 		"restore exit: is_checkpointed %d",
826 		dev->is_checkpointed);
827 
828 	return retval;
829 }
830 
831 int yaffs2_handle_hole(struct yaffs_obj *obj, loff_t new_size)
832 {
833 	/* if new_size > old_file_size.
834 	 * We're going to be writing a hole.
835 	 * If the hole is small then write zeros otherwise write a start
836 	 * of hole marker.
837 	 */
838 	loff_t old_file_size;
839 	loff_t increase;
840 	int small_hole;
841 	int result = YAFFS_OK;
842 	struct yaffs_dev *dev = NULL;
843 	u8 *local_buffer = NULL;
844 	int small_increase_ok = 0;
845 
846 	if (!obj)
847 		return YAFFS_FAIL;
848 
849 	if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
850 		return YAFFS_FAIL;
851 
852 	dev = obj->my_dev;
853 
854 	/* Bail out if not yaffs2 mode */
855 	if (!dev->param.is_yaffs2)
856 		return YAFFS_OK;
857 
858 	old_file_size = obj->variant.file_variant.file_size;
859 
860 	if (new_size <= old_file_size)
861 		return YAFFS_OK;
862 
863 	increase = new_size - old_file_size;
864 
865 	if (increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->data_bytes_per_chunk &&
866 	    yaffs_check_alloc_available(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
867 		small_hole = 1;
868 	else
869 		small_hole = 0;
870 
871 	if (small_hole)
872 		local_buffer = yaffs_get_temp_buffer(dev);
873 
874 	if (local_buffer) {
875 		/* fill hole with zero bytes */
876 		loff_t pos = old_file_size;
877 		int this_write;
878 		int written;
879 		memset(local_buffer, 0, dev->data_bytes_per_chunk);
880 		small_increase_ok = 1;
881 
882 		while (increase > 0 && small_increase_ok) {
883 			this_write = increase;
884 			if (this_write > dev->data_bytes_per_chunk)
885 				this_write = dev->data_bytes_per_chunk;
886 			written =
887 			    yaffs_do_file_wr(obj, local_buffer, pos, this_write,
888 					     0);
889 			if (written == this_write) {
890 				pos += this_write;
891 				increase -= this_write;
892 			} else {
893 				small_increase_ok = 0;
894 			}
895 		}
896 
897 		yaffs_release_temp_buffer(dev, local_buffer);
898 
899 		/* If out of space then reverse any chunks we've added */
900 		if (!small_increase_ok)
901 			yaffs_resize_file_down(obj, old_file_size);
902 	}
903 
904 	if (!small_increase_ok &&
905 	    obj->parent &&
906 	    obj->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
907 	    obj->parent->obj_id != YAFFS_OBJECTID_DELETED) {
908 		/* Write a hole start header with the old file size */
909 		yaffs_update_oh(obj, NULL, 0, 1, 0, NULL);
910 	}
911 
912 	return result;
913 }
914 
915 struct yaffs_block_index {
916 	int seq;
917 	int block;
918 };
919 
920 static int yaffs2_ybicmp(const void *a, const void *b)
921 {
922 	int aseq = ((struct yaffs_block_index *)a)->seq;
923 	int bseq = ((struct yaffs_block_index *)b)->seq;
924 	int ablock = ((struct yaffs_block_index *)a)->block;
925 	int bblock = ((struct yaffs_block_index *)b)->block;
926 
927 	if (aseq == bseq)
928 		return ablock - bblock;
929 
930 	return aseq - bseq;
931 }
932 
933 static inline int yaffs2_scan_chunk(struct yaffs_dev *dev,
934 		struct yaffs_block_info *bi,
935 		int blk, int chunk_in_block,
936 		int *found_chunks,
937 		u8 *chunk_data,
938 		struct list_head *hard_list,
939 		int summary_available)
940 {
941 	struct yaffs_obj_hdr *oh;
942 	struct yaffs_obj *in;
943 	struct yaffs_obj *parent;
944 	int equiv_id;
945 	loff_t file_size;
946 	int is_shrink;
947 	int is_unlinked;
948 	struct yaffs_ext_tags tags;
949 	int alloc_failed = 0;
950 	int chunk = blk * dev->param.chunks_per_block + chunk_in_block;
951 	struct yaffs_file_var *file_var;
952 	struct yaffs_hardlink_var *hl_var;
953 	struct yaffs_symlink_var *sl_var;
954 
955 	if (summary_available) {
956 		yaffs_summary_fetch(dev, &tags, chunk_in_block);
957 		tags.seq_number = bi->seq_number;
958 	}
959 
960 	if (!summary_available || tags.obj_id == 0) {
961 		yaffs_rd_chunk_tags_nand(dev, chunk, NULL, &tags);
962 		dev->tags_used++;
963 	} else {
964 		dev->summary_used++;
965 	}
966 
967 	/* Let's have a good look at this chunk... */
968 
969 	if (!tags.chunk_used) {
970 		/* An unassigned chunk in the block.
971 		 * If there are used chunks after this one, then
972 		 * it is a chunk that was skipped due to failing
973 		 * the erased check. Just skip it so that it can
974 		 * be deleted.
975 		 * But, more typically, We get here when this is
976 		 * an unallocated chunk and his means that
977 		 * either the block is empty or this is the one
978 		 * being allocated from
979 		 */
980 
981 		if (*found_chunks) {
982 			/* This is a chunk that was skipped due
983 			 * to failing the erased check */
984 		} else if (chunk_in_block == 0) {
985 			/* We're looking at the first chunk in
986 			 * the block so the block is unused */
987 			bi->block_state = YAFFS_BLOCK_STATE_EMPTY;
988 			dev->n_erased_blocks++;
989 		} else {
990 			if (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
991 			    bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING) {
992 				if (dev->seq_number == bi->seq_number) {
993 					/* Allocating from this block*/
994 					yaffs_trace(YAFFS_TRACE_SCAN,
995 					    " Allocating from %d %d",
996 					    blk, chunk_in_block);
997 
998 					bi->block_state =
999 						YAFFS_BLOCK_STATE_ALLOCATING;
1000 					dev->alloc_block = blk;
1001 					dev->alloc_page = chunk_in_block;
1002 					dev->alloc_block_finder = blk;
1003 				} else {
1004 					/* This is a partially written block
1005 					 * that is not the current
1006 					 * allocation block.
1007 					 */
1008 					yaffs_trace(YAFFS_TRACE_SCAN,
1009 						"Partially written block %d detected. gc will fix this.",
1010 						blk);
1011 				}
1012 			}
1013 		}
1014 
1015 		dev->n_free_chunks++;
1016 
1017 	} else if (tags.ecc_result ==
1018 		YAFFS_ECC_RESULT_UNFIXED) {
1019 		yaffs_trace(YAFFS_TRACE_SCAN,
1020 			" Unfixed ECC in chunk(%d:%d), chunk ignored",
1021 			blk, chunk_in_block);
1022 			dev->n_free_chunks++;
1023 	} else if (tags.obj_id > YAFFS_MAX_OBJECT_ID ||
1024 		   tags.chunk_id > YAFFS_MAX_CHUNK_ID ||
1025 		   tags.obj_id == YAFFS_OBJECTID_SUMMARY ||
1026 		   (tags.chunk_id > 0 &&
1027 		     tags.n_bytes > dev->data_bytes_per_chunk) ||
1028 		   tags.seq_number != bi->seq_number) {
1029 		yaffs_trace(YAFFS_TRACE_SCAN,
1030 			"Chunk (%d:%d) with bad tags:obj = %d, chunk_id = %d, n_bytes = %d, ignored",
1031 			blk, chunk_in_block, tags.obj_id,
1032 			tags.chunk_id, tags.n_bytes);
1033 		dev->n_free_chunks++;
1034 	} else if (tags.chunk_id > 0) {
1035 		/* chunk_id > 0 so it is a data chunk... */
1036 		loff_t endpos;
1037 		loff_t chunk_base = (tags.chunk_id - 1) *
1038 					dev->data_bytes_per_chunk;
1039 
1040 		*found_chunks = 1;
1041 
1042 		yaffs_set_chunk_bit(dev, blk, chunk_in_block);
1043 		bi->pages_in_use++;
1044 
1045 		in = yaffs_find_or_create_by_number(dev,
1046 					tags.obj_id,
1047 					YAFFS_OBJECT_TYPE_FILE);
1048 		if (!in)
1049 			/* Out of memory */
1050 			alloc_failed = 1;
1051 
1052 		if (in &&
1053 		    in->variant_type == YAFFS_OBJECT_TYPE_FILE &&
1054 		    chunk_base < in->variant.file_variant.shrink_size) {
1055 			/* This has not been invalidated by
1056 			 * a resize */
1057 			if (!yaffs_put_chunk_in_file(in, tags.chunk_id,
1058 								chunk, -1))
1059 				alloc_failed = 1;
1060 
1061 			/* File size is calculated by looking at
1062 			 * the data chunks if we have not
1063 			 * seen an object header yet.
1064 			 * Stop this practice once we find an
1065 			 * object header.
1066 			 */
1067 			endpos = chunk_base + tags.n_bytes;
1068 
1069 			if (!in->valid &&
1070 			    in->variant.file_variant.scanned_size < endpos) {
1071 				in->variant.file_variant.
1072 				    scanned_size = endpos;
1073 				in->variant.file_variant.
1074 				    file_size = endpos;
1075 			}
1076 		} else if (in) {
1077 			/* This chunk has been invalidated by a
1078 			 * resize, or a past file deletion
1079 			 * so delete the chunk*/
1080 			yaffs_chunk_del(dev, chunk, 1, __LINE__);
1081 		}
1082 	} else {
1083 		/* chunk_id == 0, so it is an ObjectHeader.
1084 		 * Thus, we read in the object header and make
1085 		 * the object
1086 		 */
1087 		*found_chunks = 1;
1088 
1089 		yaffs_set_chunk_bit(dev, blk, chunk_in_block);
1090 		bi->pages_in_use++;
1091 
1092 		oh = NULL;
1093 		in = NULL;
1094 
1095 		if (tags.extra_available) {
1096 			in = yaffs_find_or_create_by_number(dev,
1097 					tags.obj_id,
1098 					tags.extra_obj_type);
1099 			if (!in)
1100 				alloc_failed = 1;
1101 		}
1102 
1103 		if (!in ||
1104 		    (!in->valid && dev->param.disable_lazy_load) ||
1105 		    tags.extra_shadows ||
1106 		    (!in->valid && (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1107 				 tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND))) {
1108 
1109 			/* If we don't have  valid info then we
1110 			 * need to read the chunk
1111 			 * TODO In future we can probably defer
1112 			 * reading the chunk and living with
1113 			 * invalid data until needed.
1114 			 */
1115 
1116 			yaffs_rd_chunk_tags_nand(dev, chunk, chunk_data, NULL);
1117 
1118 			oh = (struct yaffs_obj_hdr *)chunk_data;
1119 
1120 			if (dev->param.inband_tags) {
1121 				/* Fix up the header if they got
1122 				 * corrupted by inband tags */
1123 				oh->shadows_obj =
1124 				    oh->inband_shadowed_obj_id;
1125 				oh->is_shrink =
1126 				    oh->inband_is_shrink;
1127 			}
1128 
1129 			if (!in) {
1130 				in = yaffs_find_or_create_by_number(dev,
1131 							tags.obj_id, oh->type);
1132 				if (!in)
1133 					alloc_failed = 1;
1134 			}
1135 		}
1136 
1137 		if (!in) {
1138 			/* TODO Hoosterman we have a problem! */
1139 			yaffs_trace(YAFFS_TRACE_ERROR,
1140 				"yaffs tragedy: Could not make object for object  %d at chunk %d during scan",
1141 				tags.obj_id, chunk);
1142 			return YAFFS_FAIL;
1143 		}
1144 
1145 		if (in->valid) {
1146 			/* We have already filled this one.
1147 			 * We have a duplicate that will be
1148 			 * discarded, but we first have to suck
1149 			 * out resize info if it is a file.
1150 			 */
1151 			if ((in->variant_type == YAFFS_OBJECT_TYPE_FILE) &&
1152 				((oh && oh->type == YAFFS_OBJECT_TYPE_FILE) ||
1153 				 (tags.extra_available &&
1154 				  tags.extra_obj_type == YAFFS_OBJECT_TYPE_FILE)
1155 				)) {
1156 				loff_t this_size = (oh) ?
1157 					yaffs_oh_to_size(oh) :
1158 					tags.extra_file_size;
1159 				u32 parent_obj_id = (oh) ?
1160 					oh->parent_obj_id :
1161 					tags.extra_parent_id;
1162 
1163 				is_shrink = (oh) ?
1164 					oh->is_shrink :
1165 					tags.extra_is_shrink;
1166 
1167 				/* If it is deleted (unlinked
1168 				 * at start also means deleted)
1169 				 * we treat the file size as
1170 				 * being zeroed at this point.
1171 				 */
1172 				if (parent_obj_id == YAFFS_OBJECTID_DELETED ||
1173 				    parent_obj_id == YAFFS_OBJECTID_UNLINKED) {
1174 					this_size = 0;
1175 					is_shrink = 1;
1176 				}
1177 
1178 				if (is_shrink &&
1179 				    in->variant.file_variant.shrink_size >
1180 				    this_size)
1181 					in->variant.file_variant.shrink_size =
1182 					this_size;
1183 
1184 				if (is_shrink)
1185 					bi->has_shrink_hdr = 1;
1186 			}
1187 			/* Use existing - destroy this one. */
1188 			yaffs_chunk_del(dev, chunk, 1, __LINE__);
1189 		}
1190 
1191 		if (!in->valid && in->variant_type !=
1192 		    (oh ? oh->type : tags.extra_obj_type))
1193 			yaffs_trace(YAFFS_TRACE_ERROR,
1194 				"yaffs tragedy: Bad object type, %d != %d, for object %d at chunk %d during scan",
1195 				oh ? oh->type : tags.extra_obj_type,
1196 				in->variant_type, tags.obj_id,
1197 				chunk);
1198 
1199 		if (!in->valid &&
1200 		    (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1201 		     tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND)) {
1202 			/* We only load some info, don't fiddle
1203 			 * with directory structure */
1204 			in->valid = 1;
1205 
1206 			if (oh) {
1207 				in->yst_mode = oh->yst_mode;
1208 				yaffs_load_attribs(in, oh);
1209 				in->lazy_loaded = 0;
1210 			} else {
1211 				in->lazy_loaded = 1;
1212 			}
1213 			in->hdr_chunk = chunk;
1214 
1215 		} else if (!in->valid) {
1216 			/* we need to load this info */
1217 			in->valid = 1;
1218 			in->hdr_chunk = chunk;
1219 			if (oh) {
1220 				in->variant_type = oh->type;
1221 				in->yst_mode = oh->yst_mode;
1222 				yaffs_load_attribs(in, oh);
1223 
1224 				if (oh->shadows_obj > 0)
1225 					yaffs_handle_shadowed_obj(dev,
1226 					     oh->shadows_obj, 1);
1227 
1228 				yaffs_set_obj_name_from_oh(in, oh);
1229 				parent = yaffs_find_or_create_by_number(dev,
1230 						oh->parent_obj_id,
1231 						YAFFS_OBJECT_TYPE_DIRECTORY);
1232 				file_size = yaffs_oh_to_size(oh);
1233 				is_shrink = oh->is_shrink;
1234 				equiv_id = oh->equiv_id;
1235 			} else {
1236 				in->variant_type = tags.extra_obj_type;
1237 				parent = yaffs_find_or_create_by_number(dev,
1238 						tags.extra_parent_id,
1239 						YAFFS_OBJECT_TYPE_DIRECTORY);
1240 				file_size = tags.extra_file_size;
1241 				is_shrink = tags.extra_is_shrink;
1242 				equiv_id = tags.extra_equiv_id;
1243 				in->lazy_loaded = 1;
1244 			}
1245 			in->dirty = 0;
1246 
1247 			if (!parent)
1248 				alloc_failed = 1;
1249 
1250 			/* directory stuff...
1251 			 * hook up to parent
1252 			 */
1253 
1254 			if (parent &&
1255 			    parent->variant_type == YAFFS_OBJECT_TYPE_UNKNOWN) {
1256 				/* Set up as a directory */
1257 				parent->variant_type =
1258 					YAFFS_OBJECT_TYPE_DIRECTORY;
1259 				INIT_LIST_HEAD(&parent->
1260 						variant.dir_variant.children);
1261 			} else if (!parent ||
1262 				   parent->variant_type !=
1263 					YAFFS_OBJECT_TYPE_DIRECTORY) {
1264 				/* Hoosterman, another problem....
1265 				 * Trying to use a non-directory as a directory
1266 				 */
1267 
1268 				yaffs_trace(YAFFS_TRACE_ERROR,
1269 					"yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1270 					);
1271 				parent = dev->lost_n_found;
1272 			}
1273 			yaffs_add_obj_to_dir(parent, in);
1274 
1275 			is_unlinked = (parent == dev->del_dir) ||
1276 					(parent == dev->unlinked_dir);
1277 
1278 			if (is_shrink)
1279 				/* Mark the block */
1280 				bi->has_shrink_hdr = 1;
1281 
1282 			/* Note re hardlinks.
1283 			 * Since we might scan a hardlink before its equivalent
1284 			 * object is scanned we put them all in a list.
1285 			 * After scanning is complete, we should have all the
1286 			 * objects, so we run through this list and fix up all
1287 			 * the chains.
1288 			 */
1289 
1290 			switch (in->variant_type) {
1291 			case YAFFS_OBJECT_TYPE_UNKNOWN:
1292 				/* Todo got a problem */
1293 				break;
1294 			case YAFFS_OBJECT_TYPE_FILE:
1295 				file_var = &in->variant.file_variant;
1296 				if (file_var->scanned_size < file_size) {
1297 					/* This covers the case where the file
1298 					 * size is greater than the data held.
1299 					 * This will happen if the file is
1300 					 * resized to be larger than its
1301 					 * current data extents.
1302 					 */
1303 					file_var->file_size = file_size;
1304 					file_var->scanned_size = file_size;
1305 				}
1306 
1307 				if (file_var->shrink_size > file_size)
1308 					file_var->shrink_size = file_size;
1309 
1310 				break;
1311 			case YAFFS_OBJECT_TYPE_HARDLINK:
1312 				hl_var = &in->variant.hardlink_variant;
1313 				if (!is_unlinked) {
1314 					hl_var->equiv_id = equiv_id;
1315 					list_add(&in->hard_links, hard_list);
1316 				}
1317 				break;
1318 			case YAFFS_OBJECT_TYPE_DIRECTORY:
1319 				/* Do nothing */
1320 				break;
1321 			case YAFFS_OBJECT_TYPE_SPECIAL:
1322 				/* Do nothing */
1323 				break;
1324 			case YAFFS_OBJECT_TYPE_SYMLINK:
1325 				sl_var = &in->variant.symlink_variant;
1326 				if (oh) {
1327 					sl_var->alias =
1328 					    yaffs_clone_str(oh->alias);
1329 					if (!sl_var->alias)
1330 						alloc_failed = 1;
1331 				}
1332 				break;
1333 			}
1334 		}
1335 	}
1336 	return alloc_failed ? YAFFS_FAIL : YAFFS_OK;
1337 }
1338 
1339 int yaffs2_scan_backwards(struct yaffs_dev *dev)
1340 {
1341 	int blk;
1342 	int block_iter;
1343 	int start_iter;
1344 	int end_iter;
1345 	int n_to_scan = 0;
1346 	enum yaffs_block_state state;
1347 	int c;
1348 	LIST_HEAD(hard_list);
1349 	struct yaffs_block_info *bi;
1350 	u32 seq_number;
1351 	int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
1352 	u8 *chunk_data;
1353 	int found_chunks;
1354 	int alloc_failed = 0;
1355 	struct yaffs_block_index *block_index = NULL;
1356 	int alt_block_index = 0;
1357 	int summary_available;
1358 
1359 	yaffs_trace(YAFFS_TRACE_SCAN,
1360 		"yaffs2_scan_backwards starts  intstartblk %d intendblk %d...",
1361 		dev->internal_start_block, dev->internal_end_block);
1362 
1363 	dev->seq_number = YAFFS_LOWEST_SEQUENCE_NUMBER;
1364 
1365 	block_index =
1366 		kmalloc(n_blocks * sizeof(struct yaffs_block_index), GFP_NOFS);
1367 
1368 	if (!block_index) {
1369 		block_index =
1370 		    vmalloc(n_blocks * sizeof(struct yaffs_block_index));
1371 		alt_block_index = 1;
1372 	}
1373 
1374 	if (!block_index) {
1375 		yaffs_trace(YAFFS_TRACE_SCAN,
1376 			"yaffs2_scan_backwards() could not allocate block index!"
1377 			);
1378 		return YAFFS_FAIL;
1379 	}
1380 
1381 	dev->blocks_in_checkpt = 0;
1382 
1383 	chunk_data = yaffs_get_temp_buffer(dev);
1384 
1385 	/* Scan all the blocks to determine their state */
1386 	bi = dev->block_info;
1387 	for (blk = dev->internal_start_block; blk <= dev->internal_end_block;
1388 	     blk++) {
1389 		yaffs_clear_chunk_bits(dev, blk);
1390 		bi->pages_in_use = 0;
1391 		bi->soft_del_pages = 0;
1392 
1393 		yaffs_query_init_block_state(dev, blk, &state, &seq_number);
1394 
1395 		bi->block_state = state;
1396 		bi->seq_number = seq_number;
1397 
1398 		if (bi->seq_number == YAFFS_SEQUENCE_CHECKPOINT_DATA)
1399 			bi->block_state = YAFFS_BLOCK_STATE_CHECKPOINT;
1400 		if (bi->seq_number == YAFFS_SEQUENCE_BAD_BLOCK)
1401 			bi->block_state = YAFFS_BLOCK_STATE_DEAD;
1402 
1403 		yaffs_trace(YAFFS_TRACE_SCAN_DEBUG,
1404 			"Block scanning block %d state %d seq %d",
1405 			blk, bi->block_state, seq_number);
1406 
1407 		if (bi->block_state == YAFFS_BLOCK_STATE_CHECKPOINT) {
1408 			dev->blocks_in_checkpt++;
1409 
1410 		} else if (bi->block_state == YAFFS_BLOCK_STATE_DEAD) {
1411 			yaffs_trace(YAFFS_TRACE_BAD_BLOCKS,
1412 				"block %d is bad", blk);
1413 		} else if (bi->block_state == YAFFS_BLOCK_STATE_EMPTY) {
1414 			yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "Block empty ");
1415 			dev->n_erased_blocks++;
1416 			dev->n_free_chunks += dev->param.chunks_per_block;
1417 		} else if (bi->block_state ==
1418 				YAFFS_BLOCK_STATE_NEEDS_SCAN) {
1419 			/* Determine the highest sequence number */
1420 			if (seq_number >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1421 			    seq_number < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1422 				block_index[n_to_scan].seq = seq_number;
1423 				block_index[n_to_scan].block = blk;
1424 				n_to_scan++;
1425 				if (seq_number >= dev->seq_number)
1426 					dev->seq_number = seq_number;
1427 			} else {
1428 				/* TODO: Nasty sequence number! */
1429 				yaffs_trace(YAFFS_TRACE_SCAN,
1430 					"Block scanning block %d has bad sequence number %d",
1431 					blk, seq_number);
1432 			}
1433 		}
1434 		bi++;
1435 	}
1436 
1437 	yaffs_trace(YAFFS_TRACE_SCAN, "%d blocks to be sorted...", n_to_scan);
1438 
1439 	cond_resched();
1440 
1441 	/* Sort the blocks by sequence number */
1442 	sort(block_index, n_to_scan, sizeof(struct yaffs_block_index),
1443 		   yaffs2_ybicmp, NULL);
1444 
1445 	cond_resched();
1446 
1447 	yaffs_trace(YAFFS_TRACE_SCAN, "...done");
1448 
1449 	/* Now scan the blocks looking at the data. */
1450 	start_iter = 0;
1451 	end_iter = n_to_scan - 1;
1452 	yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "%d blocks to scan", n_to_scan);
1453 
1454 	/* For each block.... backwards */
1455 	for (block_iter = end_iter;
1456 	     !alloc_failed && block_iter >= start_iter;
1457 	     block_iter--) {
1458 		/* Cooperative multitasking! This loop can run for so
1459 		   long that watchdog timers expire. */
1460 		cond_resched();
1461 
1462 		/* get the block to scan in the correct order */
1463 		blk = block_index[block_iter].block;
1464 		bi = yaffs_get_block_info(dev, blk);
1465 
1466 		summary_available = yaffs_summary_read(dev, dev->sum_tags, blk);
1467 
1468 		/* For each chunk in each block that needs scanning.... */
1469 		found_chunks = 0;
1470 		if (summary_available)
1471 			c = dev->chunks_per_summary - 1;
1472 		else
1473 			c = dev->param.chunks_per_block - 1;
1474 
1475 		for (/* c is already initialised */;
1476 		     !alloc_failed && c >= 0 &&
1477 		     (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
1478 		      bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING);
1479 		      c--) {
1480 			/* Scan backwards...
1481 			 * Read the tags and decide what to do
1482 			 */
1483 			if (yaffs2_scan_chunk(dev, bi, blk, c,
1484 					&found_chunks, chunk_data,
1485 					&hard_list, summary_available) ==
1486 					YAFFS_FAIL)
1487 				alloc_failed = 1;
1488 		}
1489 
1490 		if (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN) {
1491 			/* If we got this far while scanning, then the block
1492 			 * is fully allocated. */
1493 			bi->block_state = YAFFS_BLOCK_STATE_FULL;
1494 		}
1495 
1496 		/* Now let's see if it was dirty */
1497 		if (bi->pages_in_use == 0 &&
1498 		    !bi->has_shrink_hdr &&
1499 		    bi->block_state == YAFFS_BLOCK_STATE_FULL) {
1500 			yaffs_block_became_dirty(dev, blk);
1501 		}
1502 	}
1503 
1504 	yaffs_skip_rest_of_block(dev);
1505 
1506 	if (alt_block_index)
1507 		vfree(block_index);
1508 	else
1509 		kfree(block_index);
1510 
1511 	/* Ok, we've done all the scanning.
1512 	 * Fix up the hard link chains.
1513 	 * We have scanned all the objects, now it's time to add these
1514 	 * hardlinks.
1515 	 */
1516 	yaffs_link_fixup(dev, &hard_list);
1517 
1518 	yaffs_release_temp_buffer(dev, chunk_data);
1519 
1520 	if (alloc_failed)
1521 		return YAFFS_FAIL;
1522 
1523 	yaffs_trace(YAFFS_TRACE_SCAN, "yaffs2_scan_backwards ends");
1524 
1525 	return YAFFS_OK;
1526 }
1527