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