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
 369 static void yaffs2_checkpt_obj_bit_assign(struct yaffs_checkpt_obj *cp,
 370                                           int bit_offset,
 371                                           int bit_width,
 372                                           u32 value)
 373 {
 374         u32 and_mask;
 375
 376         and_mask = ((1<<bit_width)-1) << bit_offset;
 377
 378         cp->bit_field &= ~and_mask;
 379         cp->bit_field |= ((value << bit_offset) & and_mask);
 380 }
 381
 382 static u32 yaffs2_checkpt_obj_bit_get(struct yaffs_checkpt_obj *cp,
 383                                       int bit_offset,
 384                                       int bit_width)
 385 {
 386         u32 and_mask;
 387
 388         and_mask = ((1<<bit_width)-1);
 389
 390         return (cp->bit_field >> bit_offset) & and_mask;
 391 }
 392
 393 static void yaffs2_obj_checkpt_obj(struct yaffs_checkpt_obj *cp,
 394                                    struct yaffs_obj *obj)
 395 {
 396         cp->obj_id = obj->obj_id;
 397         cp->parent_id = (obj->parent) ? obj->parent->obj_id : 0;
 398         cp->hdr_chunk = obj->hdr_chunk;
 399
 400         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_VARIANT_BITS, obj->variant_type);
 401         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_DELETED_BITS, obj->deleted);
 402         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_SOFT_DEL_BITS, obj->soft_del);
 403         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_UNLINKED_BITS, obj->unlinked);
 404         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_FAKE_BITS, obj->fake);
 405         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_RENAME_ALLOWED_BITS, obj->rename_allowed);
 406         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_UNLINK_ALLOWED_BITS, obj->unlink_allowed);
 407         yaffs2_checkpt_obj_bit_assign(cp, CHECKPOINT_SERIAL_BITS, obj->serial);
 408
 409         cp->n_data_chunks = obj->n_data_chunks;
 410
 411         if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
 412                 cp->size_or_equiv_obj = obj->variant.file_variant.file_size;
 413         else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK)
 414                 cp->size_or_equiv_obj = obj->variant.hardlink_variant.equiv_id;
 415 }
 416
 417 static int yaffs2_checkpt_obj_to_obj(struct yaffs_obj *obj,
 418                                      struct yaffs_checkpt_obj *cp)
 419 {
 420         struct yaffs_obj *parent;
 421         u32 cp_variant_type = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_VARIANT_BITS);
 422
 423         if (obj->variant_type != cp_variant_type) {
 424                 yaffs_trace(YAFFS_TRACE_ERROR,
 425                         "Checkpoint read object %d type %d chunk %d does not match existing object type %d",
 426                         cp->obj_id, cp_variant_type, cp->hdr_chunk,
 427                         obj->variant_type);
 428                 return 0;
 429         }
 430
 431         obj->obj_id = cp->obj_id;
 432
 433         if (cp->parent_id)
 434                 parent = yaffs_find_or_create_by_number(obj->my_dev,
 435                                                 cp->parent_id,
 436                                                 YAFFS_OBJECT_TYPE_DIRECTORY);
 437         else
 438                 parent = NULL;
 439
 440         if (parent) {
 441                 if (parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
 442                         yaffs_trace(YAFFS_TRACE_ALWAYS,
 443                                 "Checkpoint read object %d parent %d type %d chunk %d Parent type, %d, not directory",
 444                                 cp->obj_id, cp->parent_id,
 445                                 cp_variant_type, cp->hdr_chunk,
 446                                 parent->variant_type);
 447                         return 0;
 448                 }
 449                 yaffs_add_obj_to_dir(parent, obj);
 450         }
 451
 452         obj->hdr_chunk = cp->hdr_chunk;
 453
 454         obj->variant_type = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_VARIANT_BITS);
 455         obj->deleted = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_DELETED_BITS);
 456         obj->soft_del = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_SOFT_DEL_BITS);
 457         obj->unlinked = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_UNLINKED_BITS);
 458         obj->fake = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_FAKE_BITS);
 459         obj->rename_allowed = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_RENAME_ALLOWED_BITS);
 460         obj->unlink_allowed = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_UNLINK_ALLOWED_BITS);
 461         obj->serial = yaffs2_checkpt_obj_bit_get(cp, CHECKPOINT_SERIAL_BITS);
 462
 463         obj->n_data_chunks = cp->n_data_chunks;
 464
 465         if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE) {
 466                 obj->variant.file_variant.file_size = cp->size_or_equiv_obj;
 467                 obj->variant.file_variant.stored_size = cp->size_or_equiv_obj;
 468         } else if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK) {
 469                 obj->variant.hardlink_variant.equiv_id = cp->size_or_equiv_obj;
 470         }
 471         if (obj->hdr_chunk > 0)
 472                 obj->lazy_loaded = 1;
 473         return 1;
 474 }
 475
 476 static int yaffs2_checkpt_tnode_worker(struct yaffs_obj *in,
 477                                        struct yaffs_tnode *tn, u32 level,
 478                                        int chunk_offset)
 479 {
 480         int i;
 481         struct yaffs_dev *dev = in->my_dev;
 482         int ok = 1;
 483         u32 base_offset;
 484
 485         if (!tn)
 486                 return 1;
 487
 488         if (level > 0) {
 489                 for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) {
 490                         if (!tn->internal[i])
 491                                 continue;
 492                         ok = yaffs2_checkpt_tnode_worker(in,
 493                                  tn->internal[i],
 494                                  level - 1,
 495                                  (chunk_offset <<
 496                                   YAFFS_TNODES_INTERNAL_BITS) + i);
 497                 }
 498                 return ok;
 499         }
 500
 501         /* Level 0 tnode */
 502         base_offset = chunk_offset << YAFFS_TNODES_LEVEL0_BITS;
 503         ok = (yaffs2_checkpt_wr(dev, &base_offset, sizeof(base_offset)) ==
 504                         sizeof(base_offset));
 505         if (ok)
 506                 ok = (yaffs2_checkpt_wr(dev, tn, dev->tnode_size) ==
 507                         dev->tnode_size);
 508
 509         return ok;
 510 }
 511
 512 static int yaffs2_wr_checkpt_tnodes(struct yaffs_obj *obj)
 513 {
 514         u32 end_marker = ~0;
 515         int ok = 1;
 516
 517         if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
 518                 return ok;
 519
 520         ok = yaffs2_checkpt_tnode_worker(obj,
 521                                          obj->variant.file_variant.top,
 522                                          obj->variant.file_variant.
 523                                          top_level, 0);
 524         if (ok)
 525                 ok = (yaffs2_checkpt_wr(obj->my_dev, &end_marker,
 526                                 sizeof(end_marker)) == sizeof(end_marker));
 527
 528         return ok ? 1 : 0;
 529 }
 530
 531 static int yaffs2_rd_checkpt_tnodes(struct yaffs_obj *obj)
 532 {
 533         u32 base_chunk;
 534         int ok = 1;
 535         struct yaffs_dev *dev = obj->my_dev;
 536         struct yaffs_file_var *file_stuct_ptr = &obj->variant.file_variant;
 537         struct yaffs_tnode *tn;
 538         int nread = 0;
 539
 540         ok = (yaffs2_checkpt_rd(dev, &base_chunk, sizeof(base_chunk)) ==
 541               sizeof(base_chunk));
 542
 543         while (ok && (~base_chunk)) {
 544                 nread++;
 545                 /* Read level 0 tnode */
 546
 547                 tn = yaffs_get_tnode(dev);
 548                 if (tn)
 549                         ok = (yaffs2_checkpt_rd(dev, tn, dev->tnode_size) ==
 550                                 dev->tnode_size);
 551                 else
 552                         ok = 0;
 553
 554                 if (tn && ok)
 555                         ok = yaffs_add_find_tnode_0(dev,
 556                                                     file_stuct_ptr,
 557                                                     base_chunk, tn) ? 1 : 0;
 558
 559                 if (ok)
 560                         ok = (yaffs2_checkpt_rd
 561                               (dev, &base_chunk,
 562                                sizeof(base_chunk)) == sizeof(base_chunk));
 563         }
 564
 565         yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 566                 "Checkpoint read tnodes %d records, last %d. ok %d",
 567                 nread, base_chunk, ok);
 568
 569         return ok ? 1 : 0;
 570 }
 571
 572 static int yaffs2_wr_checkpt_objs(struct yaffs_dev *dev)
 573 {
 574         struct yaffs_obj *obj;
 575         struct yaffs_checkpt_obj cp;
 576         int i;
 577         int ok = 1;
 578         struct list_head *lh;
 579         u32 cp_variant_type;
 580
 581         /* Iterate through the objects in each hash entry,
 582          * dumping them to the checkpointing stream.
 583          */
 584
 585         for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
 586                 list_for_each(lh, &dev->obj_bucket[i].list) {
 587                         obj = list_entry(lh, struct yaffs_obj, hash_link);
 588                         if (!obj->defered_free) {
 589                                 yaffs2_obj_checkpt_obj(&cp, obj);
 590                                 cp.struct_type = sizeof(cp);
 591                                 cp_variant_type = yaffs2_checkpt_obj_bit_get(
 592                                                 &cp, CHECKPOINT_VARIANT_BITS);
 593                                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 594                                         "Checkpoint write object %d parent %d type %d chunk %d obj addr %p",
 595                                         cp.obj_id, cp.parent_id,
 596                                         cp_variant_type, cp.hdr_chunk, obj);
 597
 598                                 ok = (yaffs2_checkpt_wr(dev, &cp,
 599                                                 sizeof(cp)) == sizeof(cp));
 600
 601                                 if (ok &&
 602                                         obj->variant_type ==
 603                                         YAFFS_OBJECT_TYPE_FILE)
 604                                         ok = yaffs2_wr_checkpt_tnodes(obj);
 605                         }
 606                 }
 607         }
 608
 609         /* Dump end of list */
 610         memset(&cp, 0xff, sizeof(struct yaffs_checkpt_obj));
 611         cp.struct_type = sizeof(cp);
 612
 613         if (ok)
 614                 ok = (yaffs2_checkpt_wr(dev, &cp, sizeof(cp)) == sizeof(cp));
 615
 616         return ok ? 1 : 0;
 617 }
 618
 619 static int yaffs2_rd_checkpt_objs(struct yaffs_dev *dev)
 620 {
 621         struct yaffs_obj *obj;
 622         struct yaffs_checkpt_obj cp;
 623         int ok = 1;
 624         int done = 0;
 625         u32 cp_variant_type;
 626         LIST_HEAD(hard_list);
 627
 628
 629         while (ok && !done) {
 630                 ok = (yaffs2_checkpt_rd(dev, &cp, sizeof(cp)) == sizeof(cp));
 631                 if (cp.struct_type != sizeof(cp)) {
 632                         yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 633                                 "struct size %d instead of %d ok %d",
 634                                 cp.struct_type, (int)sizeof(cp), ok);
 635                         ok = 0;
 636                 }
 637
 638                 cp_variant_type = yaffs2_checkpt_obj_bit_get(
 639                                                 &cp, CHECKPOINT_VARIANT_BITS);
 640                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 641                         "Checkpoint read object %d parent %d type %d chunk %d ",
 642                         cp.obj_id, cp.parent_id, cp_variant_type,
 643                         cp.hdr_chunk);
 644
 645                 if (ok && cp.obj_id == ~0) {
 646                         done = 1;
 647                 } else if (ok) {
 648                         obj =
 649                             yaffs_find_or_create_by_number(dev, cp.obj_id,
 650                                                            cp_variant_type);
 651                         if (obj) {
 652                                 ok = yaffs2_checkpt_obj_to_obj(obj, &cp);
 653                                 if (!ok)
 654                                         break;
 655                                 if (obj->variant_type ==
 656                                         YAFFS_OBJECT_TYPE_FILE) {
 657                                         ok = yaffs2_rd_checkpt_tnodes(obj);
 658                                 } else if (obj->variant_type ==
 659                                         YAFFS_OBJECT_TYPE_HARDLINK) {
 660                                         list_add(&obj->hard_links, &hard_list);
 661                                 }
 662                         } else {
 663                                 ok = 0;
 664                         }
 665                 }
 666         }
 667
 668         if (ok)
 669                 yaffs_link_fixup(dev, &hard_list);
 670
 671         return ok ? 1 : 0;
 672 }
 673
 674 static int yaffs2_wr_checkpt_sum(struct yaffs_dev *dev)
 675 {
 676         u32 checkpt_sum;
 677         int ok;
 678
 679         yaffs2_get_checkpt_sum(dev, &checkpt_sum);
 680
 681         ok = (yaffs2_checkpt_wr(dev, &checkpt_sum, sizeof(checkpt_sum)) ==
 682                 sizeof(checkpt_sum));
 683
 684         if (!ok)
 685                 return 0;
 686
 687         return 1;
 688 }
 689
 690 static int yaffs2_rd_checkpt_sum(struct yaffs_dev *dev)
 691 {
 692         u32 checkpt_sum0;
 693         u32 checkpt_sum1;
 694         int ok;
 695
 696         yaffs2_get_checkpt_sum(dev, &checkpt_sum0);
 697
 698         ok = (yaffs2_checkpt_rd(dev, &checkpt_sum1, sizeof(checkpt_sum1)) ==
 699                 sizeof(checkpt_sum1));
 700
 701         if (!ok)
 702                 return 0;
 703
 704         if (checkpt_sum0 != checkpt_sum1)
 705                 return 0;
 706
 707         return 1;
 708 }
 709
 710 static int yaffs2_wr_checkpt_data(struct yaffs_dev *dev)
 711 {
 712         int ok = 1;
 713
 714         if (!yaffs2_checkpt_required(dev)) {
 715                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 716                         "skipping checkpoint write");
 717                 ok = 0;
 718         }
 719
 720         if (ok)
 721                 ok = yaffs2_checkpt_open(dev, 1);
 722
 723         if (ok) {
 724                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 725                         "write checkpoint validity");
 726                 ok = yaffs2_wr_checkpt_validity_marker(dev, 1);
 727         }
 728         if (ok) {
 729                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 730                         "write checkpoint device");
 731                 ok = yaffs2_wr_checkpt_dev(dev);
 732         }
 733         if (ok) {
 734                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 735                         "write checkpoint objects");
 736                 ok = yaffs2_wr_checkpt_objs(dev);
 737         }
 738         if (ok) {
 739                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 740                         "write checkpoint validity");
 741                 ok = yaffs2_wr_checkpt_validity_marker(dev, 0);
 742         }
 743
 744         if (ok)
 745                 ok = yaffs2_wr_checkpt_sum(dev);
 746
 747         if (!yaffs_checkpt_close(dev))
 748                 ok = 0;
 749
 750         if (ok)
 751                 dev->is_checkpointed = 1;
 752         else
 753                 dev->is_checkpointed = 0;
 754
 755         return dev->is_checkpointed;
 756 }
 757
 758 static int yaffs2_rd_checkpt_data(struct yaffs_dev *dev)
 759 {
 760         int ok = 1;
 761
 762         if (!dev->param.is_yaffs2)
 763                 ok = 0;
 764
 765         if (ok && dev->param.skip_checkpt_rd) {
 766                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 767                         "skipping checkpoint read");
 768                 ok = 0;
 769         }
 770
 771         if (ok)
 772                 ok = yaffs2_checkpt_open(dev, 0); /* open for read */
 773
 774         if (ok) {
 775                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 776                         "read checkpoint validity");
 777                 ok = yaffs2_rd_checkpt_validity_marker(dev, 1);
 778         }
 779         if (ok) {
 780                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 781                         "read checkpoint device");
 782                 ok = yaffs2_rd_checkpt_dev(dev);
 783         }
 784         if (ok) {
 785                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 786                         "read checkpoint objects");
 787                 ok = yaffs2_rd_checkpt_objs(dev);
 788         }
 789         if (ok) {
 790                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 791                         "read checkpoint validity");
 792                 ok = yaffs2_rd_checkpt_validity_marker(dev, 0);
 793         }
 794
 795         if (ok) {
 796                 ok = yaffs2_rd_checkpt_sum(dev);
 797                 yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 798                         "read checkpoint checksum %d", ok);
 799         }
 800
 801         if (!yaffs_checkpt_close(dev))
 802                 ok = 0;
 803
 804         if (ok)
 805                 dev->is_checkpointed = 1;
 806         else
 807                 dev->is_checkpointed = 0;
 808
 809         return ok ? 1 : 0;
 810 }
 811
 812 void yaffs2_checkpt_invalidate(struct yaffs_dev *dev)
 813 {
 814         if (dev->is_checkpointed || dev->blocks_in_checkpt > 0) {
 815                 dev->is_checkpointed = 0;
 816                 yaffs2_checkpt_invalidate_stream(dev);
 817         }
 818         if (dev->param.sb_dirty_fn)
 819                 dev->param.sb_dirty_fn(dev);
 820 }
 821
 822 int yaffs_checkpoint_save(struct yaffs_dev *dev)
 823 {
 824         yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 825                 "save entry: is_checkpointed %d",
 826                 dev->is_checkpointed);
 827
 828         yaffs_verify_objects(dev);
 829         yaffs_verify_blocks(dev);
 830         yaffs_verify_free_chunks(dev);
 831
 832         if (!dev->is_checkpointed) {
 833                 yaffs2_checkpt_invalidate(dev);
 834                 yaffs2_wr_checkpt_data(dev);
 835         }
 836
 837         yaffs_trace(YAFFS_TRACE_CHECKPOINT | YAFFS_TRACE_MOUNT,
 838                 "save exit: is_checkpointed %d",
 839                 dev->is_checkpointed);
 840
 841         return dev->is_checkpointed;
 842 }
 843
 844 int yaffs2_checkpt_restore(struct yaffs_dev *dev)
 845 {
 846         int retval;
 847
 848         yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 849                 "restore entry: is_checkpointed %d",
 850                 dev->is_checkpointed);
 851
 852         retval = yaffs2_rd_checkpt_data(dev);
 853
 854         if (dev->is_checkpointed) {
 855                 yaffs_verify_objects(dev);
 856                 yaffs_verify_blocks(dev);
 857                 yaffs_verify_free_chunks(dev);
 858         }
 859
 860         yaffs_trace(YAFFS_TRACE_CHECKPOINT,
 861                 "restore exit: is_checkpointed %d",
 862                 dev->is_checkpointed);
 863
 864         return retval;
 865 }
 866
 867 int yaffs2_handle_hole(struct yaffs_obj *obj, loff_t new_size)
 868 {
 869         /* if new_size > old_file_size.
 870          * We're going to be writing a hole.
 871          * If the hole is small then write zeros otherwise write a start
 872          * of hole marker.
 873          */
 874         loff_t old_file_size;
 875         loff_t increase;
 876         int small_hole;
 877         int result = YAFFS_OK;
 878         struct yaffs_dev *dev = NULL;
 879         u8 *local_buffer = NULL;
 880         int small_increase_ok = 0;
 881
 882         if (!obj)
 883                 return YAFFS_FAIL;
 884
 885         if (obj->variant_type != YAFFS_OBJECT_TYPE_FILE)
 886                 return YAFFS_FAIL;
 887
 888         dev = obj->my_dev;
 889
 890         /* Bail out if not yaffs2 mode */
 891         if (!dev->param.is_yaffs2)
 892                 return YAFFS_OK;
 893
 894         old_file_size = obj->variant.file_variant.file_size;
 895
 896         if (new_size <= old_file_size)
 897                 return YAFFS_OK;
 898
 899         increase = new_size - old_file_size;
 900
 901         if (increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->data_bytes_per_chunk &&
 902             yaffs_check_alloc_available(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
 903                 small_hole = 1;
 904         else
 905                 small_hole = 0;
 906
 907         if (small_hole)
 908                 local_buffer = yaffs_get_temp_buffer(dev);
 909
 910         if (local_buffer) {
 911                 /* fill hole with zero bytes */
 912                 loff_t pos = old_file_size;
 913                 int this_write;
 914                 int written;
 915                 memset(local_buffer, 0, dev->data_bytes_per_chunk);
 916                 small_increase_ok = 1;
 917
 918                 while (increase > 0 && small_increase_ok) {
 919                         this_write = increase;
 920                         if (this_write > dev->data_bytes_per_chunk)
 921                                 this_write = dev->data_bytes_per_chunk;
 922                         written =
 923                             yaffs_do_file_wr(obj, local_buffer, pos, this_write,
 924                                              0);
 925                         if (written == this_write) {
 926                                 pos += this_write;
 927                                 increase -= this_write;
 928                         } else {
 929                                 small_increase_ok = 0;
 930                         }
 931                 }
 932
 933                 yaffs_release_temp_buffer(dev, local_buffer);
 934
 935                 /* If out of space then reverse any chunks we've added */
 936                 if (!small_increase_ok)
 937                         yaffs_resize_file_down(obj, old_file_size);
 938         }
 939
 940         if (!small_increase_ok &&
 941             obj->parent &&
 942             obj->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
 943             obj->parent->obj_id != YAFFS_OBJECTID_DELETED) {
 944                 /* Write a hole start header with the old file size */
 945                 yaffs_update_oh(obj, NULL, 0, 1, 0, NULL);
 946         }
 947
 948         return result;
 949 }
 950
 951 struct yaffs_block_index {
 952         int seq;
 953         int block;
 954 };
 955
 956 static int yaffs2_ybicmp(const void *a, const void *b)
 957 {
 958         int aseq = ((struct yaffs_block_index *)a)->seq;
 959         int bseq = ((struct yaffs_block_index *)b)->seq;
 960         int ablock = ((struct yaffs_block_index *)a)->block;
 961         int bblock = ((struct yaffs_block_index *)b)->block;
 962
 963         if (aseq == bseq)
 964                 return ablock - bblock;
 965
 966         return aseq - bseq;
 967 }
 968
 969 static inline int yaffs2_scan_chunk(struct yaffs_dev *dev,
 970                 struct yaffs_block_info *bi,
 971                 int blk, int chunk_in_block,
 972                 int *found_chunks,
 973                 u8 *chunk_data,
 974                 struct list_head *hard_list,
 975                 int summary_available)
 976 {
 977         struct yaffs_obj_hdr *oh;
 978         struct yaffs_obj *in;
 979         struct yaffs_obj *parent;
 980         int equiv_id;
 981         loff_t file_size;
 982         int is_shrink;
 983         int is_unlinked;
 984         struct yaffs_ext_tags tags;
 985         int result;
 986         int alloc_failed = 0;
 987         int chunk = blk * dev->param.chunks_per_block + chunk_in_block;
 988         struct yaffs_file_var *file_var;
 989         struct yaffs_hardlink_var *hl_var;
 990         struct yaffs_symlink_var *sl_var;
 991
 992         if (summary_available) {
 993                 result = yaffs_summary_fetch(dev, &tags, chunk_in_block);
 994                 tags.seq_number = bi->seq_number;
 995         }
 996
 997         if (!summary_available || tags.obj_id == 0) {
 998                 result = yaffs_rd_chunk_tags_nand(dev, chunk, NULL, &tags);
 999                 dev->tags_used++;
1000         } else {
1001                 dev->summary_used++;
1002         }
1003
1004         /* Let's have a good look at this chunk... */
1005
1006         if (!tags.chunk_used) {
1007                 /* An unassigned chunk in the block.
1008                  * If there are used chunks after this one, then
1009                  * it is a chunk that was skipped due to failing
1010                  * the erased check. Just skip it so that it can
1011                  * be deleted.
1012                  * But, more typically, We get here when this is
1013                  * an unallocated chunk and his means that
1014                  * either the block is empty or this is the one
1015                  * being allocated from
1016                  */
1017
1018                 if (*found_chunks) {
1019                         /* This is a chunk that was skipped due
1020                          * to failing the erased check */
1021                 } else if (chunk_in_block == 0) {
1022                         /* We're looking at the first chunk in
1023                          * the block so the block is unused */
1024                         bi->block_state = YAFFS_BLOCK_STATE_EMPTY;
1025                         dev->n_erased_blocks++;
1026                 } else {
1027                         if (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
1028                             bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING) {
1029                                 if (dev->seq_number == bi->seq_number) {
1030                                         /* Allocating from this block*/
1031                                         yaffs_trace(YAFFS_TRACE_SCAN,
1032                                             " Allocating from %d %d",
1033                                             blk, chunk_in_block);
1034
1035                                         bi->block_state =
1036                                                 YAFFS_BLOCK_STATE_ALLOCATING;
1037                                         dev->alloc_block = blk;
1038                                         dev->alloc_page = chunk_in_block;
1039                                         dev->alloc_block_finder = blk;
1040                                 } else {
1041                                         /* This is a partially written block
1042                                          * that is not the current
1043                                          * allocation block.
1044                                          */
1045                                         yaffs_trace(YAFFS_TRACE_SCAN,
1046                                                 "Partially written block %d detected. gc will fix this.",
1047                                                 blk);
1048                                 }
1049                         }
1050                 }
1051
1052                 dev->n_free_chunks++;
1053
1054         } else if (tags.ecc_result ==
1055                 YAFFS_ECC_RESULT_UNFIXED) {
1056                 yaffs_trace(YAFFS_TRACE_SCAN,
1057                         " Unfixed ECC in chunk(%d:%d), chunk ignored",
1058                         blk, chunk_in_block);
1059                         dev->n_free_chunks++;
1060         } else if (tags.obj_id > YAFFS_MAX_OBJECT_ID ||
1061                    tags.chunk_id > YAFFS_MAX_CHUNK_ID ||
1062                    tags.obj_id == YAFFS_OBJECTID_SUMMARY ||
1063                    (tags.chunk_id > 0 &&
1064                      tags.n_bytes > dev->data_bytes_per_chunk) ||
1065                    tags.seq_number != bi->seq_number) {
1066                 yaffs_trace(YAFFS_TRACE_SCAN,
1067                         "Chunk (%d:%d) with bad tags:obj = %d, chunk_id = %d, n_bytes = %d, ignored",
1068                         blk, chunk_in_block, tags.obj_id,
1069                         tags.chunk_id, tags.n_bytes);
1070                 dev->n_free_chunks++;
1071         } else if (tags.chunk_id > 0) {
1072                 /* chunk_id > 0 so it is a data chunk... */
1073                 loff_t endpos;
1074                 loff_t chunk_base = (tags.chunk_id - 1) *
1075                                         dev->data_bytes_per_chunk;
1076
1077                 *found_chunks = 1;
1078
1079                 yaffs_set_chunk_bit(dev, blk, chunk_in_block);
1080                 bi->pages_in_use++;
1081
1082                 in = yaffs_find_or_create_by_number(dev,
1083                                         tags.obj_id,
1084                                         YAFFS_OBJECT_TYPE_FILE);
1085                 if (!in)
1086                         /* Out of memory */
1087                         alloc_failed = 1;
1088
1089                 if (in &&
1090                     in->variant_type == YAFFS_OBJECT_TYPE_FILE &&
1091                     chunk_base < in->variant.file_variant.shrink_size) {
1092                         /* This has not been invalidated by
1093                          * a resize */
1094                         if (!yaffs_put_chunk_in_file(in, tags.chunk_id,
1095                                                                 chunk, -1))
1096                                 alloc_failed = 1;
1097
1098                         /* File size is calculated by looking at
1099                          * the data chunks if we have not
1100                          * seen an object header yet.
1101                          * Stop this practice once we find an
1102                          * object header.
1103                          */
1104                         endpos = chunk_base + tags.n_bytes;
1105
1106                         if (!in->valid &&
1107                             in->variant.file_variant.stored_size < endpos) {
1108                                 in->variant.file_variant.
1109                                     stored_size = endpos;
1110                                 in->variant.file_variant.
1111                                     file_size = endpos;
1112                         }
1113                 } else if (in) {
1114                         /* This chunk has been invalidated by a
1115                          * resize, or a past file deletion
1116                          * so delete the chunk*/
1117                         yaffs_chunk_del(dev, chunk, 1, __LINE__);
1118                 }
1119         } else {
1120                 /* chunk_id == 0, so it is an ObjectHeader.
1121                  * Thus, we read in the object header and make
1122                  * the object
1123                  */
1124                 *found_chunks = 1;
1125
1126                 yaffs_set_chunk_bit(dev, blk, chunk_in_block);
1127                 bi->pages_in_use++;
1128
1129                 oh = NULL;
1130                 in = NULL;
1131
1132                 if (tags.extra_available) {
1133                         in = yaffs_find_or_create_by_number(dev,
1134                                         tags.obj_id,
1135                                         tags.extra_obj_type);
1136                         if (!in)
1137                                 alloc_failed = 1;
1138                 }
1139
1140                 if (!in ||
1141                     (!in->valid && dev->param.disable_lazy_load) ||
1142                     tags.extra_shadows ||
1143                     (!in->valid && (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1144                                  tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND))) {
1145
1146                         /* If we don't have  valid info then we
1147                          * need to read the chunk
1148                          * TODO In future we can probably defer
1149                          * reading the chunk and living with
1150                          * invalid data until needed.
1151                          */
1152
1153                         result = yaffs_rd_chunk_tags_nand(dev,
1154                                                   chunk,
1155                                                   chunk_data,
1156                                                   NULL);
1157
1158                         oh = (struct yaffs_obj_hdr *)chunk_data;
1159
1160                         if (dev->param.inband_tags) {
1161                                 /* Fix up the header if they got
1162                                  * corrupted by inband tags */
1163                                 oh->shadows_obj =
1164                                     oh->inband_shadowed_obj_id;
1165                                 oh->is_shrink =
1166                                     oh->inband_is_shrink;
1167                         }
1168
1169                         if (!in) {
1170                                 in = yaffs_find_or_create_by_number(dev,
1171                                                         tags.obj_id, oh->type);
1172                                 if (!in)
1173                                         alloc_failed = 1;
1174                         }
1175                 }
1176
1177                 if (!in) {
1178                         /* TODO Hoosterman we have a problem! */
1179                         yaffs_trace(YAFFS_TRACE_ERROR,
1180                                 "yaffs tragedy: Could not make object for object  %d at chunk %d during scan",
1181                                 tags.obj_id, chunk);
1182                         return YAFFS_FAIL;
1183                 }
1184
1185                 if (in->valid) {
1186                         /* We have already filled this one.
1187                          * We have a duplicate that will be
1188                          * discarded, but we first have to suck
1189                          * out resize info if it is a file.
1190                          */
1191                         if ((in->variant_type == YAFFS_OBJECT_TYPE_FILE) &&
1192                                 ((oh && oh->type == YAFFS_OBJECT_TYPE_FILE) ||
1193                                  (tags.extra_available &&
1194                                   tags.extra_obj_type == YAFFS_OBJECT_TYPE_FILE)
1195                                 )) {
1196                                 loff_t this_size = (oh) ?
1197                                         yaffs_oh_to_size(oh) :
1198                                         tags.extra_file_size;
1199                                 u32 parent_obj_id = (oh) ?
1200                                         oh->parent_obj_id :
1201                                         tags.extra_parent_id;
1202
1203                                 is_shrink = (oh) ?
1204                                         oh->is_shrink :
1205                                         tags.extra_is_shrink;
1206
1207                                 /* If it is deleted (unlinked
1208                                  * at start also means deleted)
1209                                  * we treat the file size as
1210                                  * being zeroed at this point.
1211                                  */
1212                                 if (parent_obj_id == YAFFS_OBJECTID_DELETED ||
1213                                     parent_obj_id == YAFFS_OBJECTID_UNLINKED) {
1214                                         this_size = 0;
1215                                         is_shrink = 1;
1216                                 }
1217
1218                                 if (is_shrink &&
1219                                     in->variant.file_variant.shrink_size >
1220                                     this_size)
1221                                         in->variant.file_variant.shrink_size =
1222                                         this_size;
1223
1224                                 if (is_shrink)
1225                                         bi->has_shrink_hdr = 1;
1226                         }
1227                         /* Use existing - destroy this one. */
1228                         yaffs_chunk_del(dev, chunk, 1, __LINE__);
1229                 }
1230
1231                 if (!in->valid && in->variant_type !=
1232                     (oh ? oh->type : tags.extra_obj_type)) {
1233                         yaffs_trace(YAFFS_TRACE_ERROR,
1234                                 "yaffs tragedy: Bad type, %d != %d, for object %d at chunk %d during scan",
1235                                 oh ? oh->type : tags.extra_obj_type,
1236                                 in->variant_type, tags.obj_id,
1237                                 chunk);
1238                         in = yaffs_retype_obj(in, oh ? oh->type : tags.extra_obj_type);
1239                 }
1240
1241                 if (!in->valid &&
1242                     (tags.obj_id == YAFFS_OBJECTID_ROOT ||
1243                      tags.obj_id == YAFFS_OBJECTID_LOSTNFOUND)) {
1244                         /* We only load some info, don't fiddle
1245                          * with directory structure */
1246                         in->valid = 1;
1247
1248                         if (oh) {
1249                                 in->yst_mode = oh->yst_mode;
1250                                 yaffs_load_attribs(in, oh);
1251                                 in->lazy_loaded = 0;
1252                         } else {
1253                                 in->lazy_loaded = 1;
1254                         }
1255                         in->hdr_chunk = chunk;
1256
1257                 } else if (!in->valid) {
1258                         /* we need to load this info */
1259                         in->valid = 1;
1260                         in->hdr_chunk = chunk;
1261                         if (oh) {
1262                                 in->variant_type = oh->type;
1263                                 in->yst_mode = oh->yst_mode;
1264                                 yaffs_load_attribs(in, oh);
1265
1266                                 if (oh->shadows_obj > 0)
1267                                         yaffs_handle_shadowed_obj(dev,
1268                                              oh->shadows_obj, 1);
1269
1270                                 yaffs_set_obj_name_from_oh(in, oh);
1271                                 parent = yaffs_find_or_create_by_number(dev,
1272                                                 oh->parent_obj_id,
1273                                                 YAFFS_OBJECT_TYPE_DIRECTORY);
1274                                 file_size = yaffs_oh_to_size(oh);
1275                                 is_shrink = oh->is_shrink;
1276                                 equiv_id = oh->equiv_id;
1277                         } else {
1278                                 in->variant_type = tags.extra_obj_type;
1279                                 parent = yaffs_find_or_create_by_number(dev,
1280                                                 tags.extra_parent_id,
1281                                                 YAFFS_OBJECT_TYPE_DIRECTORY);
1282                                 file_size = tags.extra_file_size;
1283                                 is_shrink = tags.extra_is_shrink;
1284                                 equiv_id = tags.extra_equiv_id;
1285                                 in->lazy_loaded = 1;
1286                         }
1287                         in->dirty = 0;
1288
1289                         if (!parent)
1290                                 alloc_failed = 1;
1291
1292                         /* directory stuff...
1293                          * hook up to parent
1294                          */
1295
1296                         if (parent &&
1297                             parent->variant_type == YAFFS_OBJECT_TYPE_UNKNOWN) {
1298                                 /* Set up as a directory */
1299                                 parent->variant_type =
1300                                         YAFFS_OBJECT_TYPE_DIRECTORY;
1301                                 INIT_LIST_HEAD(&parent->
1302                                                 variant.dir_variant.children);
1303                         } else if (!parent ||
1304                                    parent->variant_type !=
1305                                         YAFFS_OBJECT_TYPE_DIRECTORY) {
1306                                 /* Hoosterman, another problem....
1307                                  * Trying to use a non-directory as a directory
1308                                  */
1309
1310                                 yaffs_trace(YAFFS_TRACE_ERROR,
1311                                         "yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1312                                         );
1313                                 parent = dev->lost_n_found;
1314                         }
1315                         yaffs_add_obj_to_dir(parent, in);
1316
1317                         is_unlinked = (parent == dev->del_dir) ||
1318                                         (parent == dev->unlinked_dir);
1319
1320                         if (is_shrink)
1321                                 /* Mark the block */
1322                                 bi->has_shrink_hdr = 1;
1323
1324                         /* Note re hardlinks.
1325                          * Since we might scan a hardlink before its equivalent
1326                          * object is scanned we put them all in a list.
1327                          * After scanning is complete, we should have all the
1328                          * objects, so we run through this list and fix up all
1329                          * the chains.
1330                          */
1331
1332                         switch (in->variant_type) {
1333                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1334                                 /* Todo got a problem */
1335                                 break;
1336                         case YAFFS_OBJECT_TYPE_FILE:
1337                                 file_var = &in->variant.file_variant;
1338                                 if (file_var->stored_size < file_size) {
1339                                         /* This covers the case where the file
1340                                          * size is greater than the data held.
1341                                          * This will happen if the file is
1342                                          * resized to be larger than its
1343                                          * current data extents.
1344                                          */
1345                                         file_var->file_size = file_size;
1346                                         file_var->stored_size = file_size;
1347                                 }
1348
1349                                 if (file_var->shrink_size > file_size)
1350                                         file_var->shrink_size = file_size;
1351
1352                                 break;
1353                         case YAFFS_OBJECT_TYPE_HARDLINK:
1354                                 hl_var = &in->variant.hardlink_variant;
1355                                 if (!is_unlinked) {
1356                                         hl_var->equiv_id = equiv_id;
1357                                         list_add(&in->hard_links, hard_list);
1358                                 }
1359                                 break;
1360                         case YAFFS_OBJECT_TYPE_DIRECTORY:
1361                                 /* Do nothing */
1362                                 break;
1363                         case YAFFS_OBJECT_TYPE_SPECIAL:
1364                                 /* Do nothing */
1365                                 break;
1366                         case YAFFS_OBJECT_TYPE_SYMLINK:
1367                                 sl_var = &in->variant.symlink_variant;
1368                                 if (oh) {
1369                                         sl_var->alias =
1370                                             yaffs_clone_str(oh->alias);
1371                                         if (!sl_var->alias)
1372                                                 alloc_failed = 1;
1373                                 }
1374                                 break;
1375                         }
1376                 }
1377         }
1378         return alloc_failed ? YAFFS_FAIL : YAFFS_OK;
1379 }
1380
1381 int yaffs2_scan_backwards(struct yaffs_dev *dev)
1382 {
1383         int blk;
1384         int block_iter;
1385         int start_iter;
1386         int end_iter;
1387         int n_to_scan = 0;
1388         enum yaffs_block_state state;
1389         int c;
1390         LIST_HEAD(hard_list);
1391         struct yaffs_block_info *bi;
1392         u32 seq_number;
1393         int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
1394         u8 *chunk_data;
1395         int found_chunks;
1396         int alloc_failed = 0;
1397         struct yaffs_block_index *block_index = NULL;
1398         int alt_block_index = 0;
1399         int summary_available;
1400
1401         yaffs_trace(YAFFS_TRACE_SCAN,
1402                 "yaffs2_scan_backwards starts  intstartblk %d intendblk %d...",
1403                 dev->internal_start_block, dev->internal_end_block);
1404
1405         dev->seq_number = YAFFS_LOWEST_SEQUENCE_NUMBER;
1406
1407         block_index =
1408                 kmalloc(n_blocks * sizeof(struct yaffs_block_index), GFP_NOFS);
1409
1410         if (!block_index) {
1411                 block_index =
1412                     vmalloc(n_blocks * sizeof(struct yaffs_block_index));
1413                 alt_block_index = 1;
1414         }
1415
1416         if (!block_index) {
1417                 yaffs_trace(YAFFS_TRACE_SCAN,
1418                         "yaffs2_scan_backwards() could not allocate block index!"
1419                         );
1420                 return YAFFS_FAIL;
1421         }
1422
1423         dev->blocks_in_checkpt = 0;
1424
1425         chunk_data = yaffs_get_temp_buffer(dev);
1426
1427         /* Scan all the blocks to determine their state */
1428         bi = dev->block_info;
1429         for (blk = dev->internal_start_block; blk <= dev->internal_end_block;
1430              blk++) {
1431                 yaffs_clear_chunk_bits(dev, blk);
1432                 bi->pages_in_use = 0;
1433                 bi->soft_del_pages = 0;
1434
1435                 yaffs_query_init_block_state(dev, blk, &state, &seq_number);
1436
1437                 bi->block_state = state;
1438                 bi->seq_number = seq_number;
1439
1440                 if (bi->seq_number == YAFFS_SEQUENCE_CHECKPOINT_DATA)
1441                         bi->block_state = YAFFS_BLOCK_STATE_CHECKPOINT;
1442                 if (bi->seq_number == YAFFS_SEQUENCE_BAD_BLOCK)
1443                         bi->block_state = YAFFS_BLOCK_STATE_DEAD;
1444
1445                 yaffs_trace(YAFFS_TRACE_SCAN_DEBUG,
1446                         "Block scanning block %d state %d seq %d",
1447                         blk, bi->block_state, seq_number);
1448
1449                 if (bi->block_state == YAFFS_BLOCK_STATE_CHECKPOINT) {
1450                         dev->blocks_in_checkpt++;
1451
1452                 } else if (bi->block_state == YAFFS_BLOCK_STATE_DEAD) {
1453                         yaffs_trace(YAFFS_TRACE_BAD_BLOCKS,
1454                                 "block %d is bad", blk);
1455                 } else if (bi->block_state == YAFFS_BLOCK_STATE_EMPTY) {
1456                         yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "Block empty ");
1457                         dev->n_erased_blocks++;
1458                         dev->n_free_chunks += dev->param.chunks_per_block;
1459                 } else if (bi->block_state ==
1460                                 YAFFS_BLOCK_STATE_NEEDS_SCAN) {
1461                         /* Determine the highest sequence number */
1462                         if (seq_number >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1463                             seq_number < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1464                                 block_index[n_to_scan].seq = seq_number;
1465                                 block_index[n_to_scan].block = blk;
1466                                 n_to_scan++;
1467                                 if (seq_number >= dev->seq_number)
1468                                         dev->seq_number = seq_number;
1469                         } else {
1470                                 /* TODO: Nasty sequence number! */
1471                                 yaffs_trace(YAFFS_TRACE_SCAN,
1472                                         "Block scanning block %d has bad sequence number %d",
1473                                         blk, seq_number);
1474                         }
1475                 }
1476                 bi++;
1477         }
1478
1479         yaffs_trace(YAFFS_TRACE_ALWAYS, "%d blocks to be sorted...", n_to_scan);
1480
1481         cond_resched();
1482
1483         /* Sort the blocks by sequence number */
1484         sort(block_index, n_to_scan, sizeof(struct yaffs_block_index),
1485                    yaffs2_ybicmp, NULL);
1486
1487         cond_resched();
1488
1489         yaffs_trace(YAFFS_TRACE_SCAN, "...done");
1490
1491         /* Now scan the blocks looking at the data. */
1492         start_iter = 0;
1493         end_iter = n_to_scan - 1;
1494         yaffs_trace(YAFFS_TRACE_SCAN_DEBUG, "%d blocks to scan", n_to_scan);
1495
1496         /* For each block.... backwards */
1497         for (block_iter = end_iter;
1498              !alloc_failed && block_iter >= start_iter;
1499              block_iter--) {
1500                 /* Cooperative multitasking! This loop can run for so
1501                    long that watchdog timers expire. */
1502                 cond_resched();
1503
1504                 /* get the block to scan in the correct order */
1505                 blk = block_index[block_iter].block;
1506                 bi = yaffs_get_block_info(dev, blk);
1507
1508                 summary_available = yaffs_summary_read(dev, dev->sum_tags, blk);
1509
1510                 /* For each chunk in each block that needs scanning.... */
1511                 found_chunks = 0;
1512                 if (summary_available)
1513                         c = dev->chunks_per_summary - 1;
1514                 else
1515                         c = dev->param.chunks_per_block - 1;
1516
1517                 for (/* c is already initialised */;
1518                      !alloc_failed && c >= 0 &&
1519                      (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
1520                       bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING);
1521                       c--) {
1522                         /* Scan backwards...
1523                          * Read the tags and decide what to do
1524                          */
1525                         if (yaffs2_scan_chunk(dev, bi, blk, c,
1526                                         &found_chunks, chunk_data,
1527                                         &hard_list, summary_available) ==
1528                                         YAFFS_FAIL)
1529                                 alloc_failed = 1;
1530                 }
1531
1532                 if (bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN) {
1533                         /* If we got this far while scanning, then the block
1534                          * is fully allocated. */
1535                         bi->block_state = YAFFS_BLOCK_STATE_FULL;
1536                 }
1537
1538                 /* Now let's see if it was dirty */
1539                 if (bi->pages_in_use == 0 &&
1540                     !bi->has_shrink_hdr &&
1541                     bi->block_state == YAFFS_BLOCK_STATE_FULL) {
1542                         yaffs_block_became_dirty(dev, blk);
1543                 }
1544         }
1545
1546         yaffs_skip_rest_of_block(dev);
1547
1548         if (alt_block_index)
1549                 vfree(block_index);
1550         else
1551                 kfree(block_index);
1552
1553         /* Ok, we've done all the scanning.
1554          * Fix up the hard link chains.
1555          * We have scanned all the objects, now it's time to add these
1556          * hardlinks.
1557          */
1558         yaffs_link_fixup(dev, &hard_list);
1559
1560         yaffs_release_temp_buffer(dev, chunk_data);
1561
1562         if (alloc_failed)
1563                 return YAFFS_FAIL;
1564
1565         yaffs_trace(YAFFS_TRACE_SCAN, "yaffs2_scan_backwards ends");
1566
1567         return YAFFS_OK;
1568 }