]> git.sur5r.net Git - u-boot/blob - fs/yaffs2/yaffs_yaffs2.c
ARM: sunxi: Add Ippo-q8h-v5 A23 tablet board defconfig
[u-boot] / fs / yaffs2 / yaffs_yaffs2.c
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 }