yaffs_yaffs2.c

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