yaffs_yaffs2.c

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