yaffs_yaffs2.c

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