yaffs_guts.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 "yportenv.h"
  15 #include "yaffs_trace.h"
  16
  17 #include "yaffs_guts.h"
  18 #include "yaffs_getblockinfo.h"
  19 #include "yaffs_tagscompat.h"
  20 #include "yaffs_nand.h"
  21 #include "yaffs_yaffs1.h"
  22 #include "yaffs_yaffs2.h"
  23 #include "yaffs_bitmap.h"
  24 #include "yaffs_verify.h"
  25 #include "yaffs_nand.h"
  26 #include "yaffs_packedtags2.h"
  27 #include "yaffs_nameval.h"
  28 #include "yaffs_allocator.h"
  29 #include "yaffs_attribs.h"
  30 #include "yaffs_summary.h"
  31
  32 /* Note YAFFS_GC_GOOD_ENOUGH must be <= YAFFS_GC_PASSIVE_THRESHOLD */
  33 #define YAFFS_GC_GOOD_ENOUGH 2
  34 #define YAFFS_GC_PASSIVE_THRESHOLD 4
  35
  36 #include "yaffs_ecc.h"
  37
  38 /* Forward declarations */
  39
  40 static int yaffs_wr_data_obj(struct yaffs_obj *in, int inode_chunk,
  41                              const u8 *buffer, int n_bytes, int use_reserve);
  42
  43 static void yaffs_fix_null_name(struct yaffs_obj *obj, YCHAR *name,
  44                                 int buffer_size);
  45
  46 /* Function to calculate chunk and offset */
  47
  48 void yaffs_addr_to_chunk(struct yaffs_dev *dev, loff_t addr,
  49                                 int *chunk_out, u32 *offset_out)
  50 {
  51         int chunk;
  52         u32 offset;
  53
  54         chunk = (u32) (addr >> dev->chunk_shift);
  55
  56         if (dev->chunk_div == 1) {
  57                 /* easy power of 2 case */
  58                 offset = (u32) (addr & dev->chunk_mask);
  59         } else {
  60                 /* Non power-of-2 case */
  61
  62                 loff_t chunk_base;
  63
  64                 chunk /= dev->chunk_div;
  65
  66                 chunk_base = ((loff_t) chunk) * dev->data_bytes_per_chunk;
  67                 offset = (u32) (addr - chunk_base);
  68         }
  69
  70         *chunk_out = chunk;
  71         *offset_out = offset;
  72 }
  73
  74 /* Function to return the number of shifts for a power of 2 greater than or
  75  * equal to the given number
  76  * Note we don't try to cater for all possible numbers and this does not have to
  77  * be hellishly efficient.
  78  */
  79
  80 static inline u32 calc_shifts_ceiling(u32 x)
  81 {
  82         int extra_bits;
  83         int shifts;
  84
  85         shifts = extra_bits = 0;
  86
  87         while (x > 1) {
  88                 if (x & 1)
  89                         extra_bits++;
  90                 x >>= 1;
  91                 shifts++;
  92         }
  93
  94         if (extra_bits)
  95                 shifts++;
  96
  97         return shifts;
  98 }
  99
 100 /* Function to return the number of shifts to get a 1 in bit 0
 101  */
 102
 103 static inline u32 calc_shifts(u32 x)
 104 {
 105         u32 shifts;
 106
 107         shifts = 0;
 108
 109         if (!x)
 110                 return 0;
 111
 112         while (!(x & 1)) {
 113                 x >>= 1;
 114                 shifts++;
 115         }
 116
 117         return shifts;
 118 }
 119
 120 /*
 121  * Temporary buffer manipulations.
 122  */
 123
 124 static int yaffs_init_tmp_buffers(struct yaffs_dev *dev)
 125 {
 126         int i;
 127         u8 *buf = (u8 *) 1;
 128
 129         memset(dev->temp_buffer, 0, sizeof(dev->temp_buffer));
 130
 131         for (i = 0; buf && i < YAFFS_N_TEMP_BUFFERS; i++) {
 132                 dev->temp_buffer[i].in_use = 0;
 133                 buf = kmalloc(dev->param.total_bytes_per_chunk, GFP_NOFS);
 134                 dev->temp_buffer[i].buffer = buf;
 135         }
 136
 137         return buf ? YAFFS_OK : YAFFS_FAIL;
 138 }
 139
 140 u8 *yaffs_get_temp_buffer(struct yaffs_dev * dev)
 141 {
 142         int i;
 143
 144         dev->temp_in_use++;
 145         if (dev->temp_in_use > dev->max_temp)
 146                 dev->max_temp = dev->temp_in_use;
 147
 148         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
 149                 if (dev->temp_buffer[i].in_use == 0) {
 150                         dev->temp_buffer[i].in_use = 1;
 151                         return dev->temp_buffer[i].buffer;
 152                 }
 153         }
 154
 155         yaffs_trace(YAFFS_TRACE_BUFFERS, "Out of temp buffers");
 156         /*
 157          * If we got here then we have to allocate an unmanaged one
 158          * This is not good.
 159          */
 160
 161         dev->unmanaged_buffer_allocs++;
 162         return kmalloc(dev->data_bytes_per_chunk, GFP_NOFS);
 163
 164 }
 165
 166 void yaffs_release_temp_buffer(struct yaffs_dev *dev, u8 *buffer)
 167 {
 168         int i;
 169
 170         dev->temp_in_use--;
 171
 172         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
 173                 if (dev->temp_buffer[i].buffer == buffer) {
 174                         dev->temp_buffer[i].in_use = 0;
 175                         return;
 176                 }
 177         }
 178
 179         if (buffer) {
 180                 /* assume it is an unmanaged one. */
 181                 yaffs_trace(YAFFS_TRACE_BUFFERS,
 182                         "Releasing unmanaged temp buffer");
 183                 kfree(buffer);
 184                 dev->unmanaged_buffer_deallocs++;
 185         }
 186
 187 }
 188
 189 /*
 190  * Functions for robustisizing TODO
 191  *
 192  */
 193
 194 static void yaffs_handle_chunk_wr_ok(struct yaffs_dev *dev, int nand_chunk,
 195                                      const u8 *data,
 196                                      const struct yaffs_ext_tags *tags)
 197 {
 198         (void) dev;
 199         (void) nand_chunk;
 200         (void) data;
 201         (void) tags;
 202 }
 203
 204 static void yaffs_handle_chunk_update(struct yaffs_dev *dev, int nand_chunk,
 205                                       const struct yaffs_ext_tags *tags)
 206 {
 207         (void) dev;
 208         (void) nand_chunk;
 209         (void) tags;
 210 }
 211
 212 void yaffs_handle_chunk_error(struct yaffs_dev *dev,
 213                               struct yaffs_block_info *bi)
 214 {
 215         if (!bi->gc_prioritise) {
 216                 bi->gc_prioritise = 1;
 217                 dev->has_pending_prioritised_gc = 1;
 218                 bi->chunk_error_strikes++;
 219
 220                 if (bi->chunk_error_strikes > 3) {
 221                         bi->needs_retiring = 1; /* Too many stikes, so retire */
 222                         yaffs_trace(YAFFS_TRACE_ALWAYS,
 223                                 "yaffs: Block struck out");
 224
 225                 }
 226         }
 227 }
 228
 229 static void yaffs_handle_chunk_wr_error(struct yaffs_dev *dev, int nand_chunk,
 230                                         int erased_ok)
 231 {
 232         int flash_block = nand_chunk / dev->param.chunks_per_block;
 233         struct yaffs_block_info *bi = yaffs_get_block_info(dev, flash_block);
 234
 235         yaffs_handle_chunk_error(dev, bi);
 236
 237         if (erased_ok) {
 238                 /* Was an actual write failure,
 239                  * so mark the block for retirement.*/
 240                 bi->needs_retiring = 1;
 241                 yaffs_trace(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
 242                   "**>> Block %d needs retiring", flash_block);
 243         }
 244
 245         /* Delete the chunk */
 246         yaffs_chunk_del(dev, nand_chunk, 1, __LINE__);
 247         yaffs_skip_rest_of_block(dev);
 248 }
 249
 250 /*
 251  * Verification code
 252  */
 253
 254 /*
 255  *  Simple hash function. Needs to have a reasonable spread
 256  */
 257
 258 static inline int yaffs_hash_fn(int n)
 259 {
 260         if (n < 0)
 261                 n = -n;
 262         return n % YAFFS_NOBJECT_BUCKETS;
 263 }
 264
 265 /*
 266  * Access functions to useful fake objects.
 267  * Note that root might have a presence in NAND if permissions are set.
 268  */
 269
 270 struct yaffs_obj *yaffs_root(struct yaffs_dev *dev)
 271 {
 272         return dev->root_dir;
 273 }
 274
 275 struct yaffs_obj *yaffs_lost_n_found(struct yaffs_dev *dev)
 276 {
 277         return dev->lost_n_found;
 278 }
 279
 280 /*
 281  *  Erased NAND checking functions
 282  */
 283
 284 int yaffs_check_ff(u8 *buffer, int n_bytes)
 285 {
 286         /* Horrible, slow implementation */
 287         while (n_bytes--) {
 288                 if (*buffer != 0xff)
 289                         return 0;
 290                 buffer++;
 291         }
 292         return 1;
 293 }
 294
 295 static int yaffs_check_chunk_erased(struct yaffs_dev *dev, int nand_chunk)
 296 {
 297         int retval = YAFFS_OK;
 298         u8 *data = yaffs_get_temp_buffer(dev);
 299         struct yaffs_ext_tags tags;
 300         int result;
 301
 302         result = yaffs_rd_chunk_tags_nand(dev, nand_chunk, data, &tags);
 303
 304         if (tags.ecc_result > YAFFS_ECC_RESULT_NO_ERROR)
 305                 retval = YAFFS_FAIL;
 306
 307         if (!yaffs_check_ff(data, dev->data_bytes_per_chunk) ||
 308                 tags.chunk_used) {
 309                 yaffs_trace(YAFFS_TRACE_NANDACCESS,
 310                         "Chunk %d not erased", nand_chunk);
 311                 retval = YAFFS_FAIL;
 312         }
 313
 314         yaffs_release_temp_buffer(dev, data);
 315
 316         return retval;
 317
 318 }
 319
 320 static int yaffs_verify_chunk_written(struct yaffs_dev *dev,
 321                                       int nand_chunk,
 322                                       const u8 *data,
 323                                       struct yaffs_ext_tags *tags)
 324 {
 325         int retval = YAFFS_OK;
 326         struct yaffs_ext_tags temp_tags;
 327         u8 *buffer = yaffs_get_temp_buffer(dev);
 328         int result;
 329
 330         result = yaffs_rd_chunk_tags_nand(dev, nand_chunk, buffer, &temp_tags);
 331         if (memcmp(buffer, data, dev->data_bytes_per_chunk) ||
 332             temp_tags.obj_id != tags->obj_id ||
 333             temp_tags.chunk_id != tags->chunk_id ||
 334             temp_tags.n_bytes != tags->n_bytes)
 335                 retval = YAFFS_FAIL;
 336
 337         yaffs_release_temp_buffer(dev, buffer);
 338
 339         return retval;
 340 }
 341
 342
 343 int yaffs_check_alloc_available(struct yaffs_dev *dev, int n_chunks)
 344 {
 345         int reserved_chunks;
 346         int reserved_blocks = dev->param.n_reserved_blocks;
 347         int checkpt_blocks;
 348
 349         checkpt_blocks = yaffs_calc_checkpt_blocks_required(dev);
 350
 351         reserved_chunks =
 352             (reserved_blocks + checkpt_blocks) * dev->param.chunks_per_block;
 353
 354         return (dev->n_free_chunks > (reserved_chunks + n_chunks));
 355 }
 356
 357 static int yaffs_find_alloc_block(struct yaffs_dev *dev)
 358 {
 359         int i;
 360         struct yaffs_block_info *bi;
 361
 362         if (dev->n_erased_blocks < 1) {
 363                 /* Hoosterman we've got a problem.
 364                  * Can't get space to gc
 365                  */
 366                 yaffs_trace(YAFFS_TRACE_ERROR,
 367                   "yaffs tragedy: no more erased blocks");
 368
 369                 return -1;
 370         }
 371
 372         /* Find an empty block. */
 373
 374         for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) {
 375                 dev->alloc_block_finder++;
 376                 if (dev->alloc_block_finder < dev->internal_start_block
 377                     || dev->alloc_block_finder > dev->internal_end_block) {
 378                         dev->alloc_block_finder = dev->internal_start_block;
 379                 }
 380
 381                 bi = yaffs_get_block_info(dev, dev->alloc_block_finder);
 382
 383                 if (bi->block_state == YAFFS_BLOCK_STATE_EMPTY) {
 384                         bi->block_state = YAFFS_BLOCK_STATE_ALLOCATING;
 385                         dev->seq_number++;
 386                         bi->seq_number = dev->seq_number;
 387                         dev->n_erased_blocks--;
 388                         yaffs_trace(YAFFS_TRACE_ALLOCATE,
 389                           "Allocated block %d, seq  %d, %d left" ,
 390                            dev->alloc_block_finder, dev->seq_number,
 391                            dev->n_erased_blocks);
 392                         return dev->alloc_block_finder;
 393                 }
 394         }
 395
 396         yaffs_trace(YAFFS_TRACE_ALWAYS,
 397                 "yaffs tragedy: no more erased blocks, but there should have been %d",
 398                 dev->n_erased_blocks);
 399
 400         return -1;
 401 }
 402
 403 static int yaffs_alloc_chunk(struct yaffs_dev *dev, int use_reserver,
 404                              struct yaffs_block_info **block_ptr)
 405 {
 406         int ret_val;
 407         struct yaffs_block_info *bi;
 408
 409         if (dev->alloc_block < 0) {
 410                 /* Get next block to allocate off */
 411                 dev->alloc_block = yaffs_find_alloc_block(dev);
 412                 dev->alloc_page = 0;
 413         }
 414
 415         if (!use_reserver && !yaffs_check_alloc_available(dev, 1)) {
 416                 /* No space unless we're allowed to use the reserve. */
 417                 return -1;
 418         }
 419
 420         if (dev->n_erased_blocks < dev->param.n_reserved_blocks
 421             && dev->alloc_page == 0)
 422                 yaffs_trace(YAFFS_TRACE_ALLOCATE, "Allocating reserve");
 423
 424         /* Next page please.... */
 425         if (dev->alloc_block >= 0) {
 426                 bi = yaffs_get_block_info(dev, dev->alloc_block);
 427
 428                 ret_val = (dev->alloc_block * dev->param.chunks_per_block) +
 429                     dev->alloc_page;
 430                 bi->pages_in_use++;
 431                 yaffs_set_chunk_bit(dev, dev->alloc_block, dev->alloc_page);
 432
 433                 dev->alloc_page++;
 434
 435                 dev->n_free_chunks--;
 436
 437                 /* If the block is full set the state to full */
 438                 if (dev->alloc_page >= dev->param.chunks_per_block) {
 439                         bi->block_state = YAFFS_BLOCK_STATE_FULL;
 440                         dev->alloc_block = -1;
 441                 }
 442
 443                 if (block_ptr)
 444                         *block_ptr = bi;
 445
 446                 return ret_val;
 447         }
 448
 449         yaffs_trace(YAFFS_TRACE_ERROR,
 450                 "!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!");
 451
 452         return -1;
 453 }
 454
 455 static int yaffs_get_erased_chunks(struct yaffs_dev *dev)
 456 {
 457         int n;
 458
 459         n = dev->n_erased_blocks * dev->param.chunks_per_block;
 460
 461         if (dev->alloc_block > 0)
 462                 n += (dev->param.chunks_per_block - dev->alloc_page);
 463
 464         return n;
 465
 466 }
 467
 468 /*
 469  * yaffs_skip_rest_of_block() skips over the rest of the allocation block
 470  * if we don't want to write to it.
 471  */
 472 void yaffs_skip_rest_of_block(struct yaffs_dev *dev)
 473 {
 474         struct yaffs_block_info *bi;
 475
 476         if (dev->alloc_block > 0) {
 477                 bi = yaffs_get_block_info(dev, dev->alloc_block);
 478                 if (bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING) {
 479                         bi->block_state = YAFFS_BLOCK_STATE_FULL;
 480                         dev->alloc_block = -1;
 481                 }
 482         }
 483 }
 484
 485 static int yaffs_write_new_chunk(struct yaffs_dev *dev,
 486                                  const u8 *data,
 487                                  struct yaffs_ext_tags *tags, int use_reserver)
 488 {
 489         int attempts = 0;
 490         int write_ok = 0;
 491         int chunk;
 492
 493         yaffs2_checkpt_invalidate(dev);
 494
 495         do {
 496                 struct yaffs_block_info *bi = 0;
 497                 int erased_ok = 0;
 498
 499                 chunk = yaffs_alloc_chunk(dev, use_reserver, &bi);
 500                 if (chunk < 0) {
 501                         /* no space */
 502                         break;
 503                 }
 504
 505                 /* First check this chunk is erased, if it needs
 506                  * checking.  The checking policy (unless forced
 507                  * always on) is as follows:
 508                  *
 509                  * Check the first page we try to write in a block.
 510                  * If the check passes then we don't need to check any
 511                  * more.        If the check fails, we check again...
 512                  * If the block has been erased, we don't need to check.
 513                  *
 514                  * However, if the block has been prioritised for gc,
 515                  * then we think there might be something odd about
 516                  * this block and stop using it.
 517                  *
 518                  * Rationale: We should only ever see chunks that have
 519                  * not been erased if there was a partially written
 520                  * chunk due to power loss.  This checking policy should
 521                  * catch that case with very few checks and thus save a
 522                  * lot of checks that are most likely not needed.
 523                  *
 524                  * Mods to the above
 525                  * If an erase check fails or the write fails we skip the
 526                  * rest of the block.
 527                  */
 528
 529                 /* let's give it a try */
 530                 attempts++;
 531
 532                 if (dev->param.always_check_erased)
 533                         bi->skip_erased_check = 0;
 534
 535                 if (!bi->skip_erased_check) {
 536                         erased_ok = yaffs_check_chunk_erased(dev, chunk);
 537                         if (erased_ok != YAFFS_OK) {
 538                                 yaffs_trace(YAFFS_TRACE_ERROR,
 539                                   "**>> yaffs chunk %d was not erased",
 540                                   chunk);
 541
 542                                 /* If not erased, delete this one,
 543                                  * skip rest of block and
 544                                  * try another chunk */
 545                                 yaffs_chunk_del(dev, chunk, 1, __LINE__);
 546                                 yaffs_skip_rest_of_block(dev);
 547                                 continue;
 548                         }
 549                 }
 550
 551                 write_ok = yaffs_wr_chunk_tags_nand(dev, chunk, data, tags);
 552
 553                 if (!bi->skip_erased_check)
 554                         write_ok =
 555                             yaffs_verify_chunk_written(dev, chunk, data, tags);
 556
 557                 if (write_ok != YAFFS_OK) {
 558                         /* Clean up aborted write, skip to next block and
 559                          * try another chunk */
 560                         yaffs_handle_chunk_wr_error(dev, chunk, erased_ok);
 561                         continue;
 562                 }
 563
 564                 bi->skip_erased_check = 1;
 565
 566                 /* Copy the data into the robustification buffer */
 567                 yaffs_handle_chunk_wr_ok(dev, chunk, data, tags);
 568
 569         } while (write_ok != YAFFS_OK &&
 570                  (yaffs_wr_attempts <= 0 || attempts <= yaffs_wr_attempts));
 571
 572         if (!write_ok)
 573                 chunk = -1;
 574
 575         if (attempts > 1) {
 576                 yaffs_trace(YAFFS_TRACE_ERROR,
 577                         "**>> yaffs write required %d attempts",
 578                         attempts);
 579                 dev->n_retried_writes += (attempts - 1);
 580         }
 581
 582         return chunk;
 583 }
 584
 585 /*
 586  * Block retiring for handling a broken block.
 587  */
 588
 589 static void yaffs_retire_block(struct yaffs_dev *dev, int flash_block)
 590 {
 591         struct yaffs_block_info *bi = yaffs_get_block_info(dev, flash_block);
 592
 593         yaffs2_checkpt_invalidate(dev);
 594
 595         yaffs2_clear_oldest_dirty_seq(dev, bi);
 596
 597         if (yaffs_mark_bad(dev, flash_block) != YAFFS_OK) {
 598                 if (yaffs_erase_block(dev, flash_block) != YAFFS_OK) {
 599                         yaffs_trace(YAFFS_TRACE_ALWAYS,
 600                                 "yaffs: Failed to mark bad and erase block %d",
 601                                 flash_block);
 602                 } else {
 603                         struct yaffs_ext_tags tags;
 604                         int chunk_id =
 605                             flash_block * dev->param.chunks_per_block;
 606
 607                         u8 *buffer = yaffs_get_temp_buffer(dev);
 608
 609                         memset(buffer, 0xff, dev->data_bytes_per_chunk);
 610                         memset(&tags, 0, sizeof(tags));
 611                         tags.seq_number = YAFFS_SEQUENCE_BAD_BLOCK;
 612                         if (dev->param.write_chunk_tags_fn(dev, chunk_id -
 613                                                            dev->chunk_offset,
 614                                                            buffer,
 615                                                            &tags) != YAFFS_OK)
 616                                 yaffs_trace(YAFFS_TRACE_ALWAYS,
 617                                         "yaffs: Failed to write bad block marker to block %d",
 618                                         flash_block);
 619
 620                         yaffs_release_temp_buffer(dev, buffer);
 621                 }
 622         }
 623
 624         bi->block_state = YAFFS_BLOCK_STATE_DEAD;
 625         bi->gc_prioritise = 0;
 626         bi->needs_retiring = 0;
 627
 628         dev->n_retired_blocks++;
 629 }
 630
 631 /*---------------- Name handling functions ------------*/
 632
 633 static u16 yaffs_calc_name_sum(const YCHAR *name)
 634 {
 635         u16 sum = 0;
 636         u16 i = 1;
 637
 638         if (!name)
 639                 return 0;
 640
 641         while ((*name) && i < (YAFFS_MAX_NAME_LENGTH / 2)) {
 642
 643                 /* 0x1f mask is case insensitive */
 644                 sum += ((*name) & 0x1f) * i;
 645                 i++;
 646                 name++;
 647         }
 648         return sum;
 649 }
 650
 651
 652 void yaffs_set_obj_name(struct yaffs_obj *obj, const YCHAR * name)
 653 {
 654         memset(obj->short_name, 0, sizeof(obj->short_name));
 655
 656         if (name && !name[0]) {
 657                 yaffs_fix_null_name(obj, obj->short_name,
 658                                 YAFFS_SHORT_NAME_LENGTH);
 659                 name = obj->short_name;
 660         } else if (name &&
 661                 strnlen(name, YAFFS_SHORT_NAME_LENGTH + 1) <=
 662                 YAFFS_SHORT_NAME_LENGTH)  {
 663                 strcpy(obj->short_name, name);
 664         }
 665
 666         obj->sum = yaffs_calc_name_sum(name);
 667 }
 668
 669 void yaffs_set_obj_name_from_oh(struct yaffs_obj *obj,
 670                                 const struct yaffs_obj_hdr *oh)
 671 {
 672 #ifdef CONFIG_YAFFS_AUTO_UNICODE
 673         YCHAR tmp_name[YAFFS_MAX_NAME_LENGTH + 1];
 674         memset(tmp_name, 0, sizeof(tmp_name));
 675         yaffs_load_name_from_oh(obj->my_dev, tmp_name, oh->name,
 676                                 YAFFS_MAX_NAME_LENGTH + 1);
 677         yaffs_set_obj_name(obj, tmp_name);
 678 #else
 679         yaffs_set_obj_name(obj, oh->name);
 680 #endif
 681 }
 682
 683 loff_t yaffs_max_file_size(struct yaffs_dev *dev)
 684 {
 685         if(sizeof(loff_t) < 8)
 686                 return YAFFS_MAX_FILE_SIZE_32;
 687         else
 688                 return ((loff_t) YAFFS_MAX_CHUNK_ID) * dev->data_bytes_per_chunk;
 689 }
 690
 691 /*-------------------- TNODES -------------------
 692
 693  * List of spare tnodes
 694  * The list is hooked together using the first pointer
 695  * in the tnode.
 696  */
 697
 698 struct yaffs_tnode *yaffs_get_tnode(struct yaffs_dev *dev)
 699 {
 700         struct yaffs_tnode *tn = yaffs_alloc_raw_tnode(dev);
 701
 702         if (tn) {
 703                 memset(tn, 0, dev->tnode_size);
 704                 dev->n_tnodes++;
 705         }
 706
 707         dev->checkpoint_blocks_required = 0;    /* force recalculation */
 708
 709         return tn;
 710 }
 711
 712 /* FreeTnode frees up a tnode and puts it back on the free list */
 713 static void yaffs_free_tnode(struct yaffs_dev *dev, struct yaffs_tnode *tn)
 714 {
 715         yaffs_free_raw_tnode(dev, tn);
 716         dev->n_tnodes--;
 717         dev->checkpoint_blocks_required = 0;    /* force recalculation */
 718 }
 719
 720 static void yaffs_deinit_tnodes_and_objs(struct yaffs_dev *dev)
 721 {
 722         yaffs_deinit_raw_tnodes_and_objs(dev);
 723         dev->n_obj = 0;
 724         dev->n_tnodes = 0;
 725 }
 726
 727 static void yaffs_load_tnode_0(struct yaffs_dev *dev, struct yaffs_tnode *tn,
 728                         unsigned pos, unsigned val)
 729 {
 730         u32 *map = (u32 *) tn;
 731         u32 bit_in_map;
 732         u32 bit_in_word;
 733         u32 word_in_map;
 734         u32 mask;
 735
 736         pos &= YAFFS_TNODES_LEVEL0_MASK;
 737         val >>= dev->chunk_grp_bits;
 738
 739         bit_in_map = pos * dev->tnode_width;
 740         word_in_map = bit_in_map / 32;
 741         bit_in_word = bit_in_map & (32 - 1);
 742
 743         mask = dev->tnode_mask << bit_in_word;
 744
 745         map[word_in_map] &= ~mask;
 746         map[word_in_map] |= (mask & (val << bit_in_word));
 747
 748         if (dev->tnode_width > (32 - bit_in_word)) {
 749                 bit_in_word = (32 - bit_in_word);
 750                 word_in_map++;
 751                 mask =
 752                     dev->tnode_mask >> bit_in_word;
 753                 map[word_in_map] &= ~mask;
 754                 map[word_in_map] |= (mask & (val >> bit_in_word));
 755         }
 756 }
 757
 758 u32 yaffs_get_group_base(struct yaffs_dev *dev, struct yaffs_tnode *tn,
 759                          unsigned pos)
 760 {
 761         u32 *map = (u32 *) tn;
 762         u32 bit_in_map;
 763         u32 bit_in_word;
 764         u32 word_in_map;
 765         u32 val;
 766
 767         pos &= YAFFS_TNODES_LEVEL0_MASK;
 768
 769         bit_in_map = pos * dev->tnode_width;
 770         word_in_map = bit_in_map / 32;
 771         bit_in_word = bit_in_map & (32 - 1);
 772
 773         val = map[word_in_map] >> bit_in_word;
 774
 775         if (dev->tnode_width > (32 - bit_in_word)) {
 776                 bit_in_word = (32 - bit_in_word);
 777                 word_in_map++;
 778                 val |= (map[word_in_map] << bit_in_word);
 779         }
 780
 781         val &= dev->tnode_mask;
 782         val <<= dev->chunk_grp_bits;
 783
 784         return val;
 785 }
 786
 787 /* ------------------- End of individual tnode manipulation -----------------*/
 788
 789 /* ---------Functions to manipulate the look-up tree (made up of tnodes) ------
 790  * The look up tree is represented by the top tnode and the number of top_level
 791  * in the tree. 0 means only the level 0 tnode is in the tree.
 792  */
 793
 794 /* FindLevel0Tnode finds the level 0 tnode, if one exists. */
 795 struct yaffs_tnode *yaffs_find_tnode_0(struct yaffs_dev *dev,
 796                                        struct yaffs_file_var *file_struct,
 797                                        u32 chunk_id)
 798 {
 799         struct yaffs_tnode *tn = file_struct->top;
 800         u32 i;
 801         int required_depth;
 802         int level = file_struct->top_level;
 803
 804         (void) dev;
 805
 806         /* Check sane level and chunk Id */
 807         if (level < 0 || level > YAFFS_TNODES_MAX_LEVEL)
 808                 return NULL;
 809
 810         if (chunk_id > YAFFS_MAX_CHUNK_ID)
 811                 return NULL;
 812
 813         /* First check we're tall enough (ie enough top_level) */
 814
 815         i = chunk_id >> YAFFS_TNODES_LEVEL0_BITS;
 816         required_depth = 0;
 817         while (i) {
 818                 i >>= YAFFS_TNODES_INTERNAL_BITS;
 819                 required_depth++;
 820         }
 821
 822         if (required_depth > file_struct->top_level)
 823                 return NULL;    /* Not tall enough, so we can't find it */
 824
 825         /* Traverse down to level 0 */
 826         while (level > 0 && tn) {
 827                 tn = tn->internal[(chunk_id >>
 828                                    (YAFFS_TNODES_LEVEL0_BITS +
 829                                     (level - 1) *
 830                                     YAFFS_TNODES_INTERNAL_BITS)) &
 831                                   YAFFS_TNODES_INTERNAL_MASK];
 832                 level--;
 833         }
 834
 835         return tn;
 836 }
 837
 838 /* add_find_tnode_0 finds the level 0 tnode if it exists,
 839  * otherwise first expands the tree.
 840  * This happens in two steps:
 841  *  1. If the tree isn't tall enough, then make it taller.
 842  *  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
 843  *
 844  * Used when modifying the tree.
 845  *
 846  *  If the tn argument is NULL, then a fresh tnode will be added otherwise the
 847  *  specified tn will be plugged into the ttree.
 848  */
 849
 850 struct yaffs_tnode *yaffs_add_find_tnode_0(struct yaffs_dev *dev,
 851                                            struct yaffs_file_var *file_struct,
 852                                            u32 chunk_id,
 853                                            struct yaffs_tnode *passed_tn)
 854 {
 855         int required_depth;
 856         int i;
 857         int l;
 858         struct yaffs_tnode *tn;
 859         u32 x;
 860
 861         /* Check sane level and page Id */
 862         if (file_struct->top_level < 0 ||
 863             file_struct->top_level > YAFFS_TNODES_MAX_LEVEL)
 864                 return NULL;
 865
 866         if (chunk_id > YAFFS_MAX_CHUNK_ID)
 867                 return NULL;
 868
 869         /* First check we're tall enough (ie enough top_level) */
 870
 871         x = chunk_id >> YAFFS_TNODES_LEVEL0_BITS;
 872         required_depth = 0;
 873         while (x) {
 874                 x >>= YAFFS_TNODES_INTERNAL_BITS;
 875                 required_depth++;
 876         }
 877
 878         if (required_depth > file_struct->top_level) {
 879                 /* Not tall enough, gotta make the tree taller */
 880                 for (i = file_struct->top_level; i < required_depth; i++) {
 881
 882                         tn = yaffs_get_tnode(dev);
 883
 884                         if (tn) {
 885                                 tn->internal[0] = file_struct->top;
 886                                 file_struct->top = tn;
 887                                 file_struct->top_level++;
 888                         } else {
 889                                 yaffs_trace(YAFFS_TRACE_ERROR,
 890                                         "yaffs: no more tnodes");
 891                                 return NULL;
 892                         }
 893                 }
 894         }
 895
 896         /* Traverse down to level 0, adding anything we need */
 897
 898         l = file_struct->top_level;
 899         tn = file_struct->top;
 900
 901         if (l > 0) {
 902                 while (l > 0 && tn) {
 903                         x = (chunk_id >>
 904                              (YAFFS_TNODES_LEVEL0_BITS +
 905                               (l - 1) * YAFFS_TNODES_INTERNAL_BITS)) &
 906                             YAFFS_TNODES_INTERNAL_MASK;
 907
 908                         if ((l > 1) && !tn->internal[x]) {
 909                                 /* Add missing non-level-zero tnode */
 910                                 tn->internal[x] = yaffs_get_tnode(dev);
 911                                 if (!tn->internal[x])
 912                                         return NULL;
 913                         } else if (l == 1) {
 914                                 /* Looking from level 1 at level 0 */
 915                                 if (passed_tn) {
 916                                         /* If we already have one, release it */
 917                                         if (tn->internal[x])
 918                                                 yaffs_free_tnode(dev,
 919                                                         tn->internal[x]);
 920                                         tn->internal[x] = passed_tn;
 921
 922                                 } else if (!tn->internal[x]) {
 923                                         /* Don't have one, none passed in */
 924                                         tn->internal[x] = yaffs_get_tnode(dev);
 925                                         if (!tn->internal[x])
 926                                                 return NULL;
 927                                 }
 928                         }
 929
 930                         tn = tn->internal[x];
 931                         l--;
 932                 }
 933         } else {
 934                 /* top is level 0 */
 935                 if (passed_tn) {
 936                         memcpy(tn, passed_tn,
 937                                (dev->tnode_width * YAFFS_NTNODES_LEVEL0) / 8);
 938                         yaffs_free_tnode(dev, passed_tn);
 939                 }
 940         }
 941
 942         return tn;
 943 }
 944
 945 static int yaffs_tags_match(const struct yaffs_ext_tags *tags, int obj_id,
 946                             int chunk_obj)
 947 {
 948         return (tags->chunk_id == chunk_obj &&
 949                 tags->obj_id == obj_id &&
 950                 !tags->is_deleted) ? 1 : 0;
 951
 952 }
 953
 954 static int yaffs_find_chunk_in_group(struct yaffs_dev *dev, int the_chunk,
 955                                         struct yaffs_ext_tags *tags, int obj_id,
 956                                         int inode_chunk)
 957 {
 958         int j;
 959
 960         for (j = 0; the_chunk && j < dev->chunk_grp_size; j++) {
 961                 if (yaffs_check_chunk_bit
 962                     (dev, the_chunk / dev->param.chunks_per_block,
 963                      the_chunk % dev->param.chunks_per_block)) {
 964
 965                         if (dev->chunk_grp_size == 1)
 966                                 return the_chunk;
 967                         else {
 968                                 yaffs_rd_chunk_tags_nand(dev, the_chunk, NULL,
 969                                                          tags);
 970                                 if (yaffs_tags_match(tags,
 971                                                         obj_id, inode_chunk)) {
 972                                         /* found it; */
 973                                         return the_chunk;
 974                                 }
 975                         }
 976                 }
 977                 the_chunk++;
 978         }
 979         return -1;
 980 }
 981
 982 static int yaffs_find_chunk_in_file(struct yaffs_obj *in, int inode_chunk,
 983                                     struct yaffs_ext_tags *tags)
 984 {
 985         /*Get the Tnode, then get the level 0 offset chunk offset */
 986         struct yaffs_tnode *tn;
 987         int the_chunk = -1;
 988         struct yaffs_ext_tags local_tags;
 989         int ret_val = -1;
 990         struct yaffs_dev *dev = in->my_dev;
 991
 992         if (!tags) {
 993                 /* Passed a NULL, so use our own tags space */
 994                 tags = &local_tags;
 995         }
 996
 997         tn = yaffs_find_tnode_0(dev, &in->variant.file_variant, inode_chunk);
 998
 999         if (!tn)
1000                 return ret_val;
1001
1002         the_chunk = yaffs_get_group_base(dev, tn, inode_chunk);
1003
1004         ret_val = yaffs_find_chunk_in_group(dev, the_chunk, tags, in->obj_id,
1005                                               inode_chunk);
1006         return ret_val;
1007 }
1008
1009 static int yaffs_find_del_file_chunk(struct yaffs_obj *in, int inode_chunk,
1010                                      struct yaffs_ext_tags *tags)
1011 {
1012         /* Get the Tnode, then get the level 0 offset chunk offset */
1013         struct yaffs_tnode *tn;
1014         int the_chunk = -1;
1015         struct yaffs_ext_tags local_tags;
1016         struct yaffs_dev *dev = in->my_dev;
1017         int ret_val = -1;
1018
1019         if (!tags) {
1020                 /* Passed a NULL, so use our own tags space */
1021                 tags = &local_tags;
1022         }
1023
1024         tn = yaffs_find_tnode_0(dev, &in->variant.file_variant, inode_chunk);
1025
1026         if (!tn)
1027                 return ret_val;
1028
1029         the_chunk = yaffs_get_group_base(dev, tn, inode_chunk);
1030
1031         ret_val = yaffs_find_chunk_in_group(dev, the_chunk, tags, in->obj_id,
1032                                               inode_chunk);
1033
1034         /* Delete the entry in the filestructure (if found) */
1035         if (ret_val != -1)
1036                 yaffs_load_tnode_0(dev, tn, inode_chunk, 0);
1037
1038         return ret_val;
1039 }
1040
1041 int yaffs_put_chunk_in_file(struct yaffs_obj *in, int inode_chunk,
1042                             int nand_chunk, int in_scan)
1043 {
1044         /* NB in_scan is zero unless scanning.
1045          * For forward scanning, in_scan is > 0;
1046          * for backward scanning in_scan is < 0
1047          *
1048          * nand_chunk = 0 is a dummy insert to make sure the tnodes are there.
1049          */
1050
1051         struct yaffs_tnode *tn;
1052         struct yaffs_dev *dev = in->my_dev;
1053         int existing_cunk;
1054         struct yaffs_ext_tags existing_tags;
1055         struct yaffs_ext_tags new_tags;
1056         unsigned existing_serial, new_serial;
1057
1058         if (in->variant_type != YAFFS_OBJECT_TYPE_FILE) {
1059                 /* Just ignore an attempt at putting a chunk into a non-file
1060                  * during scanning.
1061                  * If it is not during Scanning then something went wrong!
1062                  */
1063                 if (!in_scan) {
1064                         yaffs_trace(YAFFS_TRACE_ERROR,
1065                                 "yaffs tragedy:attempt to put data chunk into a non-file"
1066                                 );
1067                         BUG();
1068                 }
1069
1070                 yaffs_chunk_del(dev, nand_chunk, 1, __LINE__);
1071                 return YAFFS_OK;
1072         }
1073
1074         tn = yaffs_add_find_tnode_0(dev,
1075                                     &in->variant.file_variant,
1076                                     inode_chunk, NULL);
1077         if (!tn)
1078                 return YAFFS_FAIL;
1079
1080         if (!nand_chunk)
1081                 /* Dummy insert, bail now */
1082                 return YAFFS_OK;
1083
1084         existing_cunk = yaffs_get_group_base(dev, tn, inode_chunk);
1085
1086         if (in_scan != 0) {
1087                 /* If we're scanning then we need to test for duplicates
1088                  * NB This does not need to be efficient since it should only
1089                  * happen when the power fails during a write, then only one
1090                  * chunk should ever be affected.
1091                  *
1092                  * Correction for YAFFS2: This could happen quite a lot and we
1093                  * need to think about efficiency! TODO
1094                  * Update: For backward scanning we don't need to re-read tags
1095                  * so this is quite cheap.
1096                  */
1097
1098                 if (existing_cunk > 0) {
1099                         /* NB Right now existing chunk will not be real
1100                          * chunk_id if the chunk group size > 1
1101                          * thus we have to do a FindChunkInFile to get the
1102                          * real chunk id.
1103                          *
1104                          * We have a duplicate now we need to decide which
1105                          * one to use:
1106                          *
1107                          * Backwards scanning YAFFS2: The old one is what
1108                          * we use, dump the new one.
1109                          * YAFFS1: Get both sets of tags and compare serial
1110                          * numbers.
1111                          */
1112
1113                         if (in_scan > 0) {
1114                                 /* Only do this for forward scanning */
1115                                 yaffs_rd_chunk_tags_nand(dev,
1116                                                          nand_chunk,
1117                                                          NULL, &new_tags);
1118
1119                                 /* Do a proper find */
1120                                 existing_cunk =
1121                                     yaffs_find_chunk_in_file(in, inode_chunk,
1122                                                              &existing_tags);
1123                         }
1124
1125                         if (existing_cunk <= 0) {
1126                                 /*Hoosterman - how did this happen? */
1127
1128                                 yaffs_trace(YAFFS_TRACE_ERROR,
1129                                         "yaffs tragedy: existing chunk < 0 in scan"
1130                                         );
1131
1132                         }
1133
1134                         /* NB The deleted flags should be false, otherwise
1135                          * the chunks will not be loaded during a scan
1136                          */
1137
1138                         if (in_scan > 0) {
1139                                 new_serial = new_tags.serial_number;
1140                                 existing_serial = existing_tags.serial_number;
1141                         }
1142
1143                         if ((in_scan > 0) &&
1144                             (existing_cunk <= 0 ||
1145                              ((existing_serial + 1) & 3) == new_serial)) {
1146                                 /* Forward scanning.
1147                                  * Use new
1148                                  * Delete the old one and drop through to
1149                                  * update the tnode
1150                                  */
1151                                 yaffs_chunk_del(dev, existing_cunk, 1,
1152                                                 __LINE__);
1153                         } else {
1154                                 /* Backward scanning or we want to use the
1155                                  * existing one
1156                                  * Delete the new one and return early so that
1157                                  * the tnode isn't changed
1158                                  */
1159                                 yaffs_chunk_del(dev, nand_chunk, 1, __LINE__);
1160                                 return YAFFS_OK;
1161                         }
1162                 }
1163
1164         }
1165
1166         if (existing_cunk == 0)
1167                 in->n_data_chunks++;
1168
1169         yaffs_load_tnode_0(dev, tn, inode_chunk, nand_chunk);
1170
1171         return YAFFS_OK;
1172 }
1173
1174 static void yaffs_soft_del_chunk(struct yaffs_dev *dev, int chunk)
1175 {
1176         struct yaffs_block_info *the_block;
1177         unsigned block_no;
1178
1179         yaffs_trace(YAFFS_TRACE_DELETION, "soft delete chunk %d", chunk);
1180
1181         block_no = chunk / dev->param.chunks_per_block;
1182         the_block = yaffs_get_block_info(dev, block_no);
1183         if (the_block) {
1184                 the_block->soft_del_pages++;
1185                 dev->n_free_chunks++;
1186                 yaffs2_update_oldest_dirty_seq(dev, block_no, the_block);
1187         }
1188 }
1189
1190 /* SoftDeleteWorker scans backwards through the tnode tree and soft deletes all
1191  * the chunks in the file.
1192  * All soft deleting does is increment the block's softdelete count and pulls
1193  * the chunk out of the tnode.
1194  * Thus, essentially this is the same as DeleteWorker except that the chunks
1195  * are soft deleted.
1196  */
1197
1198 static int yaffs_soft_del_worker(struct yaffs_obj *in, struct yaffs_tnode *tn,
1199                                  u32 level, int chunk_offset)
1200 {
1201         int i;
1202         int the_chunk;
1203         int all_done = 1;
1204         struct yaffs_dev *dev = in->my_dev;
1205
1206         if (!tn)
1207                 return 1;
1208
1209         if (level > 0) {
1210                 for (i = YAFFS_NTNODES_INTERNAL - 1;
1211                         all_done && i >= 0;
1212                         i--) {
1213                         if (tn->internal[i]) {
1214                                 all_done =
1215                                     yaffs_soft_del_worker(in,
1216                                         tn->internal[i],
1217                                         level - 1,
1218                                         (chunk_offset <<
1219                                         YAFFS_TNODES_INTERNAL_BITS)
1220                                         + i);
1221                                 if (all_done) {
1222                                         yaffs_free_tnode(dev,
1223                                                 tn->internal[i]);
1224                                         tn->internal[i] = NULL;
1225                                 } else {
1226                                         /* Can this happen? */
1227                                 }
1228                         }
1229                 }
1230                 return (all_done) ? 1 : 0;
1231         }
1232
1233         /* level 0 */
1234          for (i = YAFFS_NTNODES_LEVEL0 - 1; i >= 0; i--) {
1235                 the_chunk = yaffs_get_group_base(dev, tn, i);
1236                 if (the_chunk) {
1237                         yaffs_soft_del_chunk(dev, the_chunk);
1238                         yaffs_load_tnode_0(dev, tn, i, 0);
1239                 }
1240         }
1241         return 1;
1242 }
1243
1244 static void yaffs_remove_obj_from_dir(struct yaffs_obj *obj)
1245 {
1246         struct yaffs_dev *dev = obj->my_dev;
1247         struct yaffs_obj *parent;
1248
1249         yaffs_verify_obj_in_dir(obj);
1250         parent = obj->parent;
1251
1252         yaffs_verify_dir(parent);
1253
1254         if (dev && dev->param.remove_obj_fn)
1255                 dev->param.remove_obj_fn(obj);
1256
1257         list_del_init(&obj->siblings);
1258         obj->parent = NULL;
1259
1260         yaffs_verify_dir(parent);
1261 }
1262
1263 void yaffs_add_obj_to_dir(struct yaffs_obj *directory, struct yaffs_obj *obj)
1264 {
1265         if (!directory) {
1266                 yaffs_trace(YAFFS_TRACE_ALWAYS,
1267                         "tragedy: Trying to add an object to a null pointer directory"
1268                         );
1269                 BUG();
1270                 return;
1271         }
1272         if (directory->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
1273                 yaffs_trace(YAFFS_TRACE_ALWAYS,
1274                         "tragedy: Trying to add an object to a non-directory"
1275                         );
1276                 BUG();
1277         }
1278
1279         if (obj->siblings.prev == NULL) {
1280                 /* Not initialised */
1281                 BUG();
1282         }
1283
1284         yaffs_verify_dir(directory);
1285
1286         yaffs_remove_obj_from_dir(obj);
1287
1288         /* Now add it */
1289         list_add(&obj->siblings, &directory->variant.dir_variant.children);
1290         obj->parent = directory;
1291
1292         if (directory == obj->my_dev->unlinked_dir
1293             || directory == obj->my_dev->del_dir) {
1294                 obj->unlinked = 1;
1295                 obj->my_dev->n_unlinked_files++;
1296                 obj->rename_allowed = 0;
1297         }
1298
1299         yaffs_verify_dir(directory);
1300         yaffs_verify_obj_in_dir(obj);
1301 }
1302
1303 static int yaffs_change_obj_name(struct yaffs_obj *obj,
1304                                  struct yaffs_obj *new_dir,
1305                                  const YCHAR *new_name, int force, int shadows)
1306 {
1307         int unlink_op;
1308         int del_op;
1309         struct yaffs_obj *existing_target;
1310
1311         if (new_dir == NULL)
1312                 new_dir = obj->parent;  /* use the old directory */
1313
1314         if (new_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
1315                 yaffs_trace(YAFFS_TRACE_ALWAYS,
1316                         "tragedy: yaffs_change_obj_name: new_dir is not a directory"
1317                         );
1318                 BUG();
1319         }
1320
1321         unlink_op = (new_dir == obj->my_dev->unlinked_dir);
1322         del_op = (new_dir == obj->my_dev->del_dir);
1323
1324         existing_target = yaffs_find_by_name(new_dir, new_name);
1325
1326         /* If the object is a file going into the unlinked directory,
1327          *   then it is OK to just stuff it in since duplicate names are OK.
1328          *   else only proceed if the new name does not exist and we're putting
1329          *   it into a directory.
1330          */
1331         if (!(unlink_op || del_op || force ||
1332               shadows > 0 || !existing_target) ||
1333               new_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY)
1334                 return YAFFS_FAIL;
1335
1336         yaffs_set_obj_name(obj, new_name);
1337         obj->dirty = 1;
1338         yaffs_add_obj_to_dir(new_dir, obj);
1339
1340         if (unlink_op)
1341                 obj->unlinked = 1;
1342
1343         /* If it is a deletion then we mark it as a shrink for gc  */
1344         if (yaffs_update_oh(obj, new_name, 0, del_op, shadows, NULL) >= 0)
1345                 return YAFFS_OK;
1346
1347         return YAFFS_FAIL;
1348 }
1349
1350 /*------------------------ Short Operations Cache ------------------------------
1351  *   In many situations where there is no high level buffering  a lot of
1352  *   reads might be short sequential reads, and a lot of writes may be short
1353  *   sequential writes. eg. scanning/writing a jpeg file.
1354  *   In these cases, a short read/write cache can provide a huge perfomance
1355  *   benefit with dumb-as-a-rock code.
1356  *   In Linux, the page cache provides read buffering and the short op cache
1357  *   provides write buffering.
1358  *
1359  *   There are a small number (~10) of cache chunks per device so that we don't
1360  *   need a very intelligent search.
1361  */
1362
1363 static int yaffs_obj_cache_dirty(struct yaffs_obj *obj)
1364 {
1365         struct yaffs_dev *dev = obj->my_dev;
1366         int i;
1367         struct yaffs_cache *cache;
1368         int n_caches = obj->my_dev->param.n_caches;
1369
1370         for (i = 0; i < n_caches; i++) {
1371                 cache = &dev->cache[i];
1372                 if (cache->object == obj && cache->dirty)
1373                         return 1;
1374         }
1375
1376         return 0;
1377 }
1378
1379 static void yaffs_flush_file_cache(struct yaffs_obj *obj)
1380 {
1381         struct yaffs_dev *dev = obj->my_dev;
1382         int lowest = -99;       /* Stop compiler whining. */
1383         int i;
1384         struct yaffs_cache *cache;
1385         int chunk_written = 0;
1386         int n_caches = obj->my_dev->param.n_caches;
1387
1388         if (n_caches < 1)
1389                 return;
1390         do {
1391                 cache = NULL;
1392
1393                 /* Find the lowest dirty chunk for this object */
1394                 for (i = 0; i < n_caches; i++) {
1395                         if (dev->cache[i].object == obj &&
1396                             dev->cache[i].dirty) {
1397                                 if (!cache ||
1398                                     dev->cache[i].chunk_id < lowest) {
1399                                         cache = &dev->cache[i];
1400                                         lowest = cache->chunk_id;
1401                                 }
1402                         }
1403                 }
1404
1405                 if (cache && !cache->locked) {
1406                         /* Write it out and free it up */
1407                         chunk_written =
1408                             yaffs_wr_data_obj(cache->object,
1409                                               cache->chunk_id,
1410                                               cache->data,
1411                                               cache->n_bytes, 1);
1412                         cache->dirty = 0;
1413                         cache->object = NULL;
1414                 }
1415         } while (cache && chunk_written > 0);
1416
1417         if (cache)
1418                 /* Hoosterman, disk full while writing cache out. */
1419                 yaffs_trace(YAFFS_TRACE_ERROR,
1420                         "yaffs tragedy: no space during cache write");
1421 }
1422
1423 /*yaffs_flush_whole_cache(dev)
1424  *
1425  *
1426  */
1427
1428 void yaffs_flush_whole_cache(struct yaffs_dev *dev)
1429 {
1430         struct yaffs_obj *obj;
1431         int n_caches = dev->param.n_caches;
1432         int i;
1433
1434         /* Find a dirty object in the cache and flush it...
1435          * until there are no further dirty objects.
1436          */
1437         do {
1438                 obj = NULL;
1439                 for (i = 0; i < n_caches && !obj; i++) {
1440                         if (dev->cache[i].object && dev->cache[i].dirty)
1441                                 obj = dev->cache[i].object;
1442                 }
1443                 if (obj)
1444                         yaffs_flush_file_cache(obj);
1445         } while (obj);
1446
1447 }
1448
1449 /* Grab us a cache chunk for use.
1450  * First look for an empty one.
1451  * Then look for the least recently used non-dirty one.
1452  * Then look for the least recently used dirty one...., flush and look again.
1453  */
1454 static struct yaffs_cache *yaffs_grab_chunk_worker(struct yaffs_dev *dev)
1455 {
1456         int i;
1457
1458         if (dev->param.n_caches > 0) {
1459                 for (i = 0; i < dev->param.n_caches; i++) {
1460                         if (!dev->cache[i].object)
1461                                 return &dev->cache[i];
1462                 }
1463         }
1464         return NULL;
1465 }
1466
1467 static struct yaffs_cache *yaffs_grab_chunk_cache(struct yaffs_dev *dev)
1468 {
1469         struct yaffs_cache *cache;
1470         struct yaffs_obj *the_obj;
1471         int usage;
1472         int i;
1473         int pushout;
1474
1475         if (dev->param.n_caches < 1)
1476                 return NULL;
1477
1478         /* Try find a non-dirty one... */
1479
1480         cache = yaffs_grab_chunk_worker(dev);
1481
1482         if (!cache) {
1483                 /* They were all dirty, find the LRU object and flush
1484                  * its cache, then  find again.
1485                  * NB what's here is not very accurate,
1486                  * we actually flush the object with the LRU chunk.
1487                  */
1488
1489                 /* With locking we can't assume we can use entry zero,
1490                  * Set the_obj to a valid pointer for Coverity. */
1491                 the_obj = dev->cache[0].object;
1492                 usage = -1;
1493                 cache = NULL;
1494                 pushout = -1;
1495
1496                 for (i = 0; i < dev->param.n_caches; i++) {
1497                         if (dev->cache[i].object &&
1498                             !dev->cache[i].locked &&
1499                             (dev->cache[i].last_use < usage ||
1500                             !cache)) {
1501                                 usage = dev->cache[i].last_use;
1502                                 the_obj = dev->cache[i].object;
1503                                 cache = &dev->cache[i];
1504                                 pushout = i;
1505                         }
1506                 }
1507
1508                 if (!cache || cache->dirty) {
1509                         /* Flush and try again */
1510                         yaffs_flush_file_cache(the_obj);
1511                         cache = yaffs_grab_chunk_worker(dev);
1512                 }
1513         }
1514         return cache;
1515 }
1516
1517 /* Find a cached chunk */
1518 static struct yaffs_cache *yaffs_find_chunk_cache(const struct yaffs_obj *obj,
1519                                                   int chunk_id)
1520 {
1521         struct yaffs_dev *dev = obj->my_dev;
1522         int i;
1523
1524         if (dev->param.n_caches < 1)
1525                 return NULL;
1526
1527         for (i = 0; i < dev->param.n_caches; i++) {
1528                 if (dev->cache[i].object == obj &&
1529                     dev->cache[i].chunk_id == chunk_id) {
1530                         dev->cache_hits++;
1531
1532                         return &dev->cache[i];
1533                 }
1534         }
1535         return NULL;
1536 }
1537
1538 /* Mark the chunk for the least recently used algorithym */
1539 static void yaffs_use_cache(struct yaffs_dev *dev, struct yaffs_cache *cache,
1540                             int is_write)
1541 {
1542         int i;
1543
1544         if (dev->param.n_caches < 1)
1545                 return;
1546
1547         if (dev->cache_last_use < 0 ||
1548                 dev->cache_last_use > 100000000) {
1549                 /* Reset the cache usages */
1550                 for (i = 1; i < dev->param.n_caches; i++)
1551                         dev->cache[i].last_use = 0;
1552
1553                 dev->cache_last_use = 0;
1554         }
1555         dev->cache_last_use++;
1556         cache->last_use = dev->cache_last_use;
1557
1558         if (is_write)
1559                 cache->dirty = 1;
1560 }
1561
1562 /* Invalidate a single cache page.
1563  * Do this when a whole page gets written,
1564  * ie the short cache for this page is no longer valid.
1565  */
1566 static void yaffs_invalidate_chunk_cache(struct yaffs_obj *object, int chunk_id)
1567 {
1568         struct yaffs_cache *cache;
1569
1570         if (object->my_dev->param.n_caches > 0) {
1571                 cache = yaffs_find_chunk_cache(object, chunk_id);
1572
1573                 if (cache)
1574                         cache->object = NULL;
1575         }
1576 }
1577
1578 /* Invalidate all the cache pages associated with this object
1579  * Do this whenever ther file is deleted or resized.
1580  */
1581 static void yaffs_invalidate_whole_cache(struct yaffs_obj *in)
1582 {
1583         int i;
1584         struct yaffs_dev *dev = in->my_dev;
1585
1586         if (dev->param.n_caches > 0) {
1587                 /* Invalidate it. */
1588                 for (i = 0; i < dev->param.n_caches; i++) {
1589                         if (dev->cache[i].object == in)
1590                                 dev->cache[i].object = NULL;
1591                 }
1592         }
1593 }
1594
1595 static void yaffs_unhash_obj(struct yaffs_obj *obj)
1596 {
1597         int bucket;
1598         struct yaffs_dev *dev = obj->my_dev;
1599
1600         /* If it is still linked into the bucket list, free from the list */
1601         if (!list_empty(&obj->hash_link)) {
1602                 list_del_init(&obj->hash_link);
1603                 bucket = yaffs_hash_fn(obj->obj_id);
1604                 dev->obj_bucket[bucket].count--;
1605         }
1606 }
1607
1608 /*  FreeObject frees up a Object and puts it back on the free list */
1609 static void yaffs_free_obj(struct yaffs_obj *obj)
1610 {
1611         struct yaffs_dev *dev;
1612
1613         if (!obj) {
1614                 BUG();
1615                 return;
1616         }
1617         dev = obj->my_dev;
1618         yaffs_trace(YAFFS_TRACE_OS, "FreeObject %p inode %p",
1619                 obj, obj->my_inode);
1620         if (obj->parent)
1621                 BUG();
1622         if (!list_empty(&obj->siblings))
1623                 BUG();
1624
1625         if (obj->my_inode) {
1626                 /* We're still hooked up to a cached inode.
1627                  * Don't delete now, but mark for later deletion
1628                  */
1629                 obj->defered_free = 1;
1630                 return;
1631         }
1632
1633         yaffs_unhash_obj(obj);
1634
1635         yaffs_free_raw_obj(dev, obj);
1636         dev->n_obj--;
1637         dev->checkpoint_blocks_required = 0;    /* force recalculation */
1638 }
1639
1640 void yaffs_handle_defered_free(struct yaffs_obj *obj)
1641 {
1642         if (obj->defered_free)
1643                 yaffs_free_obj(obj);
1644 }
1645
1646 static int yaffs_generic_obj_del(struct yaffs_obj *in)
1647 {
1648         /* Iinvalidate the file's data in the cache, without flushing. */
1649         yaffs_invalidate_whole_cache(in);
1650
1651         if (in->my_dev->param.is_yaffs2 && in->parent != in->my_dev->del_dir) {
1652                 /* Move to unlinked directory so we have a deletion record */
1653                 yaffs_change_obj_name(in, in->my_dev->del_dir, _Y("deleted"), 0,
1654                                       0);
1655         }
1656
1657         yaffs_remove_obj_from_dir(in);
1658         yaffs_chunk_del(in->my_dev, in->hdr_chunk, 1, __LINE__);
1659         in->hdr_chunk = 0;
1660
1661         yaffs_free_obj(in);
1662         return YAFFS_OK;
1663
1664 }
1665
1666 static void yaffs_soft_del_file(struct yaffs_obj *obj)
1667 {
1668         if (!obj->deleted ||
1669             obj->variant_type != YAFFS_OBJECT_TYPE_FILE ||
1670             obj->soft_del)
1671                 return;
1672
1673         if (obj->n_data_chunks <= 0) {
1674                 /* Empty file with no duplicate object headers,
1675                  * just delete it immediately */
1676                 yaffs_free_tnode(obj->my_dev, obj->variant.file_variant.top);
1677                 obj->variant.file_variant.top = NULL;
1678                 yaffs_trace(YAFFS_TRACE_TRACING,
1679                         "yaffs: Deleting empty file %d",
1680                         obj->obj_id);
1681                 yaffs_generic_obj_del(obj);
1682         } else {
1683                 yaffs_soft_del_worker(obj,
1684                                       obj->variant.file_variant.top,
1685                                       obj->variant.
1686                                       file_variant.top_level, 0);
1687                 obj->soft_del = 1;
1688         }
1689 }
1690
1691 /* Pruning removes any part of the file structure tree that is beyond the
1692  * bounds of the file (ie that does not point to chunks).
1693  *
1694  * A file should only get pruned when its size is reduced.
1695  *
1696  * Before pruning, the chunks must be pulled from the tree and the
1697  * level 0 tnode entries must be zeroed out.
1698  * Could also use this for file deletion, but that's probably better handled
1699  * by a special case.
1700  *
1701  * This function is recursive. For levels > 0 the function is called again on
1702  * any sub-tree. For level == 0 we just check if the sub-tree has data.
1703  * If there is no data in a subtree then it is pruned.
1704  */
1705
1706 static struct yaffs_tnode *yaffs_prune_worker(struct yaffs_dev *dev,
1707                                               struct yaffs_tnode *tn, u32 level,
1708                                               int del0)
1709 {
1710         int i;
1711         int has_data;
1712
1713         if (!tn)
1714                 return tn;
1715
1716         has_data = 0;
1717
1718         if (level > 0) {
1719                 for (i = 0; i < YAFFS_NTNODES_INTERNAL; i++) {
1720                         if (tn->internal[i]) {
1721                                 tn->internal[i] =
1722                                     yaffs_prune_worker(dev,
1723                                                 tn->internal[i],
1724                                                 level - 1,
1725                                                 (i == 0) ? del0 : 1);
1726                         }
1727
1728                         if (tn->internal[i])
1729                                 has_data++;
1730                 }
1731         } else {
1732                 int tnode_size_u32 = dev->tnode_size / sizeof(u32);
1733                 u32 *map = (u32 *) tn;
1734
1735                 for (i = 0; !has_data && i < tnode_size_u32; i++) {
1736                         if (map[i])
1737                                 has_data++;
1738                 }
1739         }
1740
1741         if (has_data == 0 && del0) {
1742                 /* Free and return NULL */
1743                 yaffs_free_tnode(dev, tn);
1744                 tn = NULL;
1745         }
1746         return tn;
1747 }
1748
1749 static int yaffs_prune_tree(struct yaffs_dev *dev,
1750                             struct yaffs_file_var *file_struct)
1751 {
1752         int i;
1753         int has_data;
1754         int done = 0;
1755         struct yaffs_tnode *tn;
1756
1757         if (file_struct->top_level < 1)
1758                 return YAFFS_OK;
1759
1760         file_struct->top =
1761            yaffs_prune_worker(dev, file_struct->top, file_struct->top_level, 0);
1762
1763         /* Now we have a tree with all the non-zero branches NULL but
1764          * the height is the same as it was.
1765          * Let's see if we can trim internal tnodes to shorten the tree.
1766          * We can do this if only the 0th element in the tnode is in use
1767          * (ie all the non-zero are NULL)
1768          */
1769
1770         while (file_struct->top_level && !done) {
1771                 tn = file_struct->top;
1772
1773                 has_data = 0;
1774                 for (i = 1; i < YAFFS_NTNODES_INTERNAL; i++) {
1775                         if (tn->internal[i])
1776                                 has_data++;
1777                 }
1778
1779                 if (!has_data) {
1780                         file_struct->top = tn->internal[0];
1781                         file_struct->top_level--;
1782                         yaffs_free_tnode(dev, tn);
1783                 } else {
1784                         done = 1;
1785                 }
1786         }
1787
1788         return YAFFS_OK;
1789 }
1790
1791 /*-------------------- End of File Structure functions.-------------------*/
1792
1793 /* alloc_empty_obj gets us a clean Object.*/
1794 static struct yaffs_obj *yaffs_alloc_empty_obj(struct yaffs_dev *dev)
1795 {
1796         struct yaffs_obj *obj = yaffs_alloc_raw_obj(dev);
1797
1798         if (!obj)
1799                 return obj;
1800
1801         dev->n_obj++;
1802
1803         /* Now sweeten it up... */
1804
1805         memset(obj, 0, sizeof(struct yaffs_obj));
1806         obj->being_created = 1;
1807
1808         obj->my_dev = dev;
1809         obj->hdr_chunk = 0;
1810         obj->variant_type = YAFFS_OBJECT_TYPE_UNKNOWN;
1811         INIT_LIST_HEAD(&(obj->hard_links));
1812         INIT_LIST_HEAD(&(obj->hash_link));
1813         INIT_LIST_HEAD(&obj->siblings);
1814
1815         /* Now make the directory sane */
1816         if (dev->root_dir) {
1817                 obj->parent = dev->root_dir;
1818                 list_add(&(obj->siblings),
1819                          &dev->root_dir->variant.dir_variant.children);
1820         }
1821
1822         /* Add it to the lost and found directory.
1823          * NB Can't put root or lost-n-found in lost-n-found so
1824          * check if lost-n-found exists first
1825          */
1826         if (dev->lost_n_found)
1827                 yaffs_add_obj_to_dir(dev->lost_n_found, obj);
1828
1829         obj->being_created = 0;
1830
1831         dev->checkpoint_blocks_required = 0;    /* force recalculation */
1832
1833         return obj;
1834 }
1835
1836 static int yaffs_find_nice_bucket(struct yaffs_dev *dev)
1837 {
1838         int i;
1839         int l = 999;
1840         int lowest = 999999;
1841
1842         /* Search for the shortest list or one that
1843          * isn't too long.
1844          */
1845
1846         for (i = 0; i < 10 && lowest > 4; i++) {
1847                 dev->bucket_finder++;
1848                 dev->bucket_finder %= YAFFS_NOBJECT_BUCKETS;
1849                 if (dev->obj_bucket[dev->bucket_finder].count < lowest) {
1850                         lowest = dev->obj_bucket[dev->bucket_finder].count;
1851                         l = dev->bucket_finder;
1852                 }
1853         }
1854
1855         return l;
1856 }
1857
1858 static int yaffs_new_obj_id(struct yaffs_dev *dev)
1859 {
1860         int bucket = yaffs_find_nice_bucket(dev);
1861         int found = 0;
1862         struct list_head *i;
1863         u32 n = (u32) bucket;
1864
1865         /* Now find an object value that has not already been taken
1866          * by scanning the list.
1867          */
1868
1869         while (!found) {
1870                 found = 1;
1871                 n += YAFFS_NOBJECT_BUCKETS;
1872                 if (1 || dev->obj_bucket[bucket].count > 0) {
1873                         list_for_each(i, &dev->obj_bucket[bucket].list) {
1874                                 /* If there is already one in the list */
1875                                 if (i && list_entry(i, struct yaffs_obj,
1876                                                     hash_link)->obj_id == n) {
1877                                         found = 0;
1878                                 }
1879                         }
1880                 }
1881         }
1882         return n;
1883 }
1884
1885 static void yaffs_hash_obj(struct yaffs_obj *in)
1886 {
1887         int bucket = yaffs_hash_fn(in->obj_id);
1888         struct yaffs_dev *dev = in->my_dev;
1889
1890         list_add(&in->hash_link, &dev->obj_bucket[bucket].list);
1891         dev->obj_bucket[bucket].count++;
1892 }
1893
1894 struct yaffs_obj *yaffs_find_by_number(struct yaffs_dev *dev, u32 number)
1895 {
1896         int bucket = yaffs_hash_fn(number);
1897         struct list_head *i;
1898         struct yaffs_obj *in;
1899
1900         list_for_each(i, &dev->obj_bucket[bucket].list) {
1901                 /* Look if it is in the list */
1902                 in = list_entry(i, struct yaffs_obj, hash_link);
1903                 if (in->obj_id == number) {
1904                         /* Don't show if it is defered free */
1905                         if (in->defered_free)
1906                                 return NULL;
1907                         return in;
1908                 }
1909         }
1910
1911         return NULL;
1912 }
1913
1914 static struct yaffs_obj *yaffs_new_obj(struct yaffs_dev *dev, int number,
1915                                 enum yaffs_obj_type type)
1916 {
1917         struct yaffs_obj *the_obj = NULL;
1918         struct yaffs_tnode *tn = NULL;
1919
1920         if (number < 0)
1921                 number = yaffs_new_obj_id(dev);
1922
1923         if (type == YAFFS_OBJECT_TYPE_FILE) {
1924                 tn = yaffs_get_tnode(dev);
1925                 if (!tn)
1926                         return NULL;
1927         }
1928
1929         the_obj = yaffs_alloc_empty_obj(dev);
1930         if (!the_obj) {
1931                 if (tn)
1932                         yaffs_free_tnode(dev, tn);
1933                 return NULL;
1934         }
1935
1936         the_obj->fake = 0;
1937         the_obj->rename_allowed = 1;
1938         the_obj->unlink_allowed = 1;
1939         the_obj->obj_id = number;
1940         yaffs_hash_obj(the_obj);
1941         the_obj->variant_type = type;
1942         yaffs_load_current_time(the_obj, 1, 1);
1943
1944         switch (type) {
1945         case YAFFS_OBJECT_TYPE_FILE:
1946                 the_obj->variant.file_variant.file_size = 0;
1947                 the_obj->variant.file_variant.scanned_size = 0;
1948                 the_obj->variant.file_variant.shrink_size =
1949                                                 yaffs_max_file_size(dev);
1950                 the_obj->variant.file_variant.top_level = 0;
1951                 the_obj->variant.file_variant.top = tn;
1952                 break;
1953         case YAFFS_OBJECT_TYPE_DIRECTORY:
1954                 INIT_LIST_HEAD(&the_obj->variant.dir_variant.children);
1955                 INIT_LIST_HEAD(&the_obj->variant.dir_variant.dirty);
1956                 break;
1957         case YAFFS_OBJECT_TYPE_SYMLINK:
1958         case YAFFS_OBJECT_TYPE_HARDLINK:
1959         case YAFFS_OBJECT_TYPE_SPECIAL:
1960                 /* No action required */
1961                 break;
1962         case YAFFS_OBJECT_TYPE_UNKNOWN:
1963                 /* todo this should not happen */
1964                 break;
1965         }
1966         return the_obj;
1967 }
1968
1969 static struct yaffs_obj *yaffs_create_fake_dir(struct yaffs_dev *dev,
1970                                                int number, u32 mode)
1971 {
1972
1973         struct yaffs_obj *obj =
1974             yaffs_new_obj(dev, number, YAFFS_OBJECT_TYPE_DIRECTORY);
1975
1976         if (!obj)
1977                 return NULL;
1978
1979         obj->fake = 1;  /* it is fake so it might not use NAND */
1980         obj->rename_allowed = 0;
1981         obj->unlink_allowed = 0;
1982         obj->deleted = 0;
1983         obj->unlinked = 0;
1984         obj->yst_mode = mode;
1985         obj->my_dev = dev;
1986         obj->hdr_chunk = 0;     /* Not a valid chunk. */
1987         return obj;
1988
1989 }
1990
1991
1992 static void yaffs_init_tnodes_and_objs(struct yaffs_dev *dev)
1993 {
1994         int i;
1995
1996         dev->n_obj = 0;
1997         dev->n_tnodes = 0;
1998         yaffs_init_raw_tnodes_and_objs(dev);
1999
2000         for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) {
2001                 INIT_LIST_HEAD(&dev->obj_bucket[i].list);
2002                 dev->obj_bucket[i].count = 0;
2003         }
2004 }
2005
2006 struct yaffs_obj *yaffs_find_or_create_by_number(struct yaffs_dev *dev,
2007                                                  int number,
2008                                                  enum yaffs_obj_type type)
2009 {
2010         struct yaffs_obj *the_obj = NULL;
2011
2012         if (number > 0)
2013                 the_obj = yaffs_find_by_number(dev, number);
2014
2015         if (!the_obj)
2016                 the_obj = yaffs_new_obj(dev, number, type);
2017
2018         return the_obj;
2019
2020 }
2021
2022 YCHAR *yaffs_clone_str(const YCHAR *str)
2023 {
2024         YCHAR *new_str = NULL;
2025         int len;
2026
2027         if (!str)
2028                 str = _Y("");
2029
2030         len = strnlen(str, YAFFS_MAX_ALIAS_LENGTH);
2031         new_str = kmalloc((len + 1) * sizeof(YCHAR), GFP_NOFS);
2032         if (new_str) {
2033                 strncpy(new_str, str, len);
2034                 new_str[len] = 0;
2035         }
2036         return new_str;
2037
2038 }
2039 /*
2040  *yaffs_update_parent() handles fixing a directories mtime and ctime when a new
2041  * link (ie. name) is created or deleted in the directory.
2042  *
2043  * ie.
2044  *   create dir/a : update dir's mtime/ctime
2045  *   rm dir/a:   update dir's mtime/ctime
2046  *   modify dir/a: don't update dir's mtimme/ctime
2047  *
2048  * This can be handled immediately or defered. Defering helps reduce the number
2049  * of updates when many files in a directory are changed within a brief period.
2050  *
2051  * If the directory updating is defered then yaffs_update_dirty_dirs must be
2052  * called periodically.
2053  */
2054
2055 static void yaffs_update_parent(struct yaffs_obj *obj)
2056 {
2057         struct yaffs_dev *dev;
2058
2059         if (!obj)
2060                 return;
2061         dev = obj->my_dev;
2062         obj->dirty = 1;
2063         yaffs_load_current_time(obj, 0, 1);
2064         if (dev->param.defered_dir_update) {
2065                 struct list_head *link = &obj->variant.dir_variant.dirty;
2066
2067                 if (list_empty(link)) {
2068                         list_add(link, &dev->dirty_dirs);
2069                         yaffs_trace(YAFFS_TRACE_BACKGROUND,
2070                           "Added object %d to dirty directories",
2071                            obj->obj_id);
2072                 }
2073
2074         } else {
2075                 yaffs_update_oh(obj, NULL, 0, 0, 0, NULL);
2076         }
2077 }
2078
2079 void yaffs_update_dirty_dirs(struct yaffs_dev *dev)
2080 {
2081         struct list_head *link;
2082         struct yaffs_obj *obj;
2083         struct yaffs_dir_var *d_s;
2084         union yaffs_obj_var *o_v;
2085
2086         yaffs_trace(YAFFS_TRACE_BACKGROUND, "Update dirty directories");
2087
2088         while (!list_empty(&dev->dirty_dirs)) {
2089                 link = dev->dirty_dirs.next;
2090                 list_del_init(link);
2091
2092                 d_s = list_entry(link, struct yaffs_dir_var, dirty);
2093                 o_v = list_entry(d_s, union yaffs_obj_var, dir_variant);
2094                 obj = list_entry(o_v, struct yaffs_obj, variant);
2095
2096                 yaffs_trace(YAFFS_TRACE_BACKGROUND, "Update directory %d",
2097                         obj->obj_id);
2098
2099                 if (obj->dirty)
2100                         yaffs_update_oh(obj, NULL, 0, 0, 0, NULL);
2101         }
2102 }
2103
2104 /*
2105  * Mknod (create) a new object.
2106  * equiv_obj only has meaning for a hard link;
2107  * alias_str only has meaning for a symlink.
2108  * rdev only has meaning for devices (a subset of special objects)
2109  */
2110
2111 static struct yaffs_obj *yaffs_create_obj(enum yaffs_obj_type type,
2112                                           struct yaffs_obj *parent,
2113                                           const YCHAR *name,
2114                                           u32 mode,
2115                                           u32 uid,
2116                                           u32 gid,
2117                                           struct yaffs_obj *equiv_obj,
2118                                           const YCHAR *alias_str, u32 rdev)
2119 {
2120         struct yaffs_obj *in;
2121         YCHAR *str = NULL;
2122         struct yaffs_dev *dev = parent->my_dev;
2123
2124         /* Check if the entry exists.
2125          * If it does then fail the call since we don't want a dup. */
2126         if (yaffs_find_by_name(parent, name))
2127                 return NULL;
2128
2129         if (type == YAFFS_OBJECT_TYPE_SYMLINK) {
2130                 str = yaffs_clone_str(alias_str);
2131                 if (!str)
2132                         return NULL;
2133         }
2134
2135         in = yaffs_new_obj(dev, -1, type);
2136
2137         if (!in) {
2138                 kfree(str);
2139                 return NULL;
2140         }
2141
2142         in->hdr_chunk = 0;
2143         in->valid = 1;
2144         in->variant_type = type;
2145
2146         in->yst_mode = mode;
2147
2148         yaffs_attribs_init(in, gid, uid, rdev);
2149
2150         in->n_data_chunks = 0;
2151
2152         yaffs_set_obj_name(in, name);
2153         in->dirty = 1;
2154
2155         yaffs_add_obj_to_dir(parent, in);
2156
2157         in->my_dev = parent->my_dev;
2158
2159         switch (type) {
2160         case YAFFS_OBJECT_TYPE_SYMLINK:
2161                 in->variant.symlink_variant.alias = str;
2162                 break;
2163         case YAFFS_OBJECT_TYPE_HARDLINK:
2164                 in->variant.hardlink_variant.equiv_obj = equiv_obj;
2165                 in->variant.hardlink_variant.equiv_id = equiv_obj->obj_id;
2166                 list_add(&in->hard_links, &equiv_obj->hard_links);
2167                 break;
2168         case YAFFS_OBJECT_TYPE_FILE:
2169         case YAFFS_OBJECT_TYPE_DIRECTORY:
2170         case YAFFS_OBJECT_TYPE_SPECIAL:
2171         case YAFFS_OBJECT_TYPE_UNKNOWN:
2172                 /* do nothing */
2173                 break;
2174         }
2175
2176         if (yaffs_update_oh(in, name, 0, 0, 0, NULL) < 0) {
2177                 /* Could not create the object header, fail */
2178                 yaffs_del_obj(in);
2179                 in = NULL;
2180         }
2181
2182         if (in)
2183                 yaffs_update_parent(parent);
2184
2185         return in;
2186 }
2187
2188 struct yaffs_obj *yaffs_create_file(struct yaffs_obj *parent,
2189                                     const YCHAR *name, u32 mode, u32 uid,
2190                                     u32 gid)
2191 {
2192         return yaffs_create_obj(YAFFS_OBJECT_TYPE_FILE, parent, name, mode,
2193                                 uid, gid, NULL, NULL, 0);
2194 }
2195
2196 struct yaffs_obj *yaffs_create_dir(struct yaffs_obj *parent, const YCHAR *name,
2197                                    u32 mode, u32 uid, u32 gid)
2198 {
2199         return yaffs_create_obj(YAFFS_OBJECT_TYPE_DIRECTORY, parent, name,
2200                                 mode, uid, gid, NULL, NULL, 0);
2201 }
2202
2203 struct yaffs_obj *yaffs_create_special(struct yaffs_obj *parent,
2204                                        const YCHAR *name, u32 mode, u32 uid,
2205                                        u32 gid, u32 rdev)
2206 {
2207         return yaffs_create_obj(YAFFS_OBJECT_TYPE_SPECIAL, parent, name, mode,
2208                                 uid, gid, NULL, NULL, rdev);
2209 }
2210
2211 struct yaffs_obj *yaffs_create_symlink(struct yaffs_obj *parent,
2212                                        const YCHAR *name, u32 mode, u32 uid,
2213                                        u32 gid, const YCHAR *alias)
2214 {
2215         return yaffs_create_obj(YAFFS_OBJECT_TYPE_SYMLINK, parent, name, mode,
2216                                 uid, gid, NULL, alias, 0);
2217 }
2218
2219 /* yaffs_link_obj returns the object id of the equivalent object.*/
2220 struct yaffs_obj *yaffs_link_obj(struct yaffs_obj *parent, const YCHAR * name,
2221                                  struct yaffs_obj *equiv_obj)
2222 {
2223         /* Get the real object in case we were fed a hard link obj */
2224         equiv_obj = yaffs_get_equivalent_obj(equiv_obj);
2225
2226         if (yaffs_create_obj(YAFFS_OBJECT_TYPE_HARDLINK,
2227                         parent, name, 0, 0, 0,
2228                         equiv_obj, NULL, 0))
2229                 return equiv_obj;
2230
2231         return NULL;
2232
2233 }
2234
2235
2236
2237 /*---------------------- Block Management and Page Allocation -------------*/
2238
2239 static void yaffs_deinit_blocks(struct yaffs_dev *dev)
2240 {
2241         if (dev->block_info_alt && dev->block_info)
2242                 vfree(dev->block_info);
2243         else
2244                 kfree(dev->block_info);
2245
2246         dev->block_info_alt = 0;
2247
2248         dev->block_info = NULL;
2249
2250         if (dev->chunk_bits_alt && dev->chunk_bits)
2251                 vfree(dev->chunk_bits);
2252         else
2253                 kfree(dev->chunk_bits);
2254         dev->chunk_bits_alt = 0;
2255         dev->chunk_bits = NULL;
2256 }
2257
2258 static int yaffs_init_blocks(struct yaffs_dev *dev)
2259 {
2260         int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
2261
2262         dev->block_info = NULL;
2263         dev->chunk_bits = NULL;
2264         dev->alloc_block = -1;  /* force it to get a new one */
2265
2266         /* If the first allocation strategy fails, thry the alternate one */
2267         dev->block_info =
2268                 kmalloc(n_blocks * sizeof(struct yaffs_block_info), GFP_NOFS);
2269         if (!dev->block_info) {
2270                 dev->block_info =
2271                     vmalloc(n_blocks * sizeof(struct yaffs_block_info));
2272                 dev->block_info_alt = 1;
2273         } else {
2274                 dev->block_info_alt = 0;
2275         }
2276
2277         if (!dev->block_info)
2278                 goto alloc_error;
2279
2280         /* Set up dynamic blockinfo stuff. Round up bytes. */
2281         dev->chunk_bit_stride = (dev->param.chunks_per_block + 7) / 8;
2282         dev->chunk_bits =
2283                 kmalloc(dev->chunk_bit_stride * n_blocks, GFP_NOFS);
2284         if (!dev->chunk_bits) {
2285                 dev->chunk_bits =
2286                     vmalloc(dev->chunk_bit_stride * n_blocks);
2287                 dev->chunk_bits_alt = 1;
2288         } else {
2289                 dev->chunk_bits_alt = 0;
2290         }
2291         if (!dev->chunk_bits)
2292                 goto alloc_error;
2293
2294
2295         memset(dev->block_info, 0, n_blocks * sizeof(struct yaffs_block_info));
2296         memset(dev->chunk_bits, 0, dev->chunk_bit_stride * n_blocks);
2297         return YAFFS_OK;
2298
2299 alloc_error:
2300         yaffs_deinit_blocks(dev);
2301         return YAFFS_FAIL;
2302 }
2303
2304
2305 void yaffs_block_became_dirty(struct yaffs_dev *dev, int block_no)
2306 {
2307         struct yaffs_block_info *bi = yaffs_get_block_info(dev, block_no);
2308         int erased_ok = 0;
2309         int i;
2310
2311         /* If the block is still healthy erase it and mark as clean.
2312          * If the block has had a data failure, then retire it.
2313          */
2314
2315         yaffs_trace(YAFFS_TRACE_GC | YAFFS_TRACE_ERASE,
2316                 "yaffs_block_became_dirty block %d state %d %s",
2317                 block_no, bi->block_state,
2318                 (bi->needs_retiring) ? "needs retiring" : "");
2319
2320         yaffs2_clear_oldest_dirty_seq(dev, bi);
2321
2322         bi->block_state = YAFFS_BLOCK_STATE_DIRTY;
2323
2324         /* If this is the block being garbage collected then stop gc'ing */
2325         if (block_no == dev->gc_block)
2326                 dev->gc_block = 0;
2327
2328         /* If this block is currently the best candidate for gc
2329          * then drop as a candidate */
2330         if (block_no == dev->gc_dirtiest) {
2331                 dev->gc_dirtiest = 0;
2332                 dev->gc_pages_in_use = 0;
2333         }
2334
2335         if (!bi->needs_retiring) {
2336                 yaffs2_checkpt_invalidate(dev);
2337                 erased_ok = yaffs_erase_block(dev, block_no);
2338                 if (!erased_ok) {
2339                         dev->n_erase_failures++;
2340                         yaffs_trace(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
2341                           "**>> Erasure failed %d", block_no);
2342                 }
2343         }
2344
2345         /* Verify erasure if needed */
2346         if (erased_ok &&
2347             ((yaffs_trace_mask & YAFFS_TRACE_ERASE) ||
2348              !yaffs_skip_verification(dev))) {
2349                 for (i = 0; i < dev->param.chunks_per_block; i++) {
2350                         if (!yaffs_check_chunk_erased(dev,
2351                                 block_no * dev->param.chunks_per_block + i)) {
2352                                 yaffs_trace(YAFFS_TRACE_ERROR,
2353                                         ">>Block %d erasure supposedly OK, but chunk %d not erased",
2354                                         block_no, i);
2355                         }
2356                 }
2357         }
2358
2359         if (!erased_ok) {
2360                 /* We lost a block of free space */
2361                 dev->n_free_chunks -= dev->param.chunks_per_block;
2362                 yaffs_retire_block(dev, block_no);
2363                 yaffs_trace(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
2364                         "**>> Block %d retired", block_no);
2365                 return;
2366         }
2367
2368         /* Clean it up... */
2369         bi->block_state = YAFFS_BLOCK_STATE_EMPTY;
2370         bi->seq_number = 0;
2371         dev->n_erased_blocks++;
2372         bi->pages_in_use = 0;
2373         bi->soft_del_pages = 0;
2374         bi->has_shrink_hdr = 0;
2375         bi->skip_erased_check = 1;      /* Clean, so no need to check */
2376         bi->gc_prioritise = 0;
2377         bi->has_summary = 0;
2378
2379         yaffs_clear_chunk_bits(dev, block_no);
2380
2381         yaffs_trace(YAFFS_TRACE_ERASE, "Erased block %d", block_no);
2382 }
2383
2384 static inline int yaffs_gc_process_chunk(struct yaffs_dev *dev,
2385                                         struct yaffs_block_info *bi,
2386                                         int old_chunk, u8 *buffer)
2387 {
2388         int new_chunk;
2389         int mark_flash = 1;
2390         struct yaffs_ext_tags tags;
2391         struct yaffs_obj *object;
2392         int matching_chunk;
2393         int ret_val = YAFFS_OK;
2394
2395         memset(&tags, 0, sizeof(tags));
2396         yaffs_rd_chunk_tags_nand(dev, old_chunk,
2397                                  buffer, &tags);
2398         object = yaffs_find_by_number(dev, tags.obj_id);
2399
2400         yaffs_trace(YAFFS_TRACE_GC_DETAIL,
2401                 "Collecting chunk in block %d, %d %d %d ",
2402                 dev->gc_chunk, tags.obj_id,
2403                 tags.chunk_id, tags.n_bytes);
2404
2405         if (object && !yaffs_skip_verification(dev)) {
2406                 if (tags.chunk_id == 0)
2407                         matching_chunk =
2408                             object->hdr_chunk;
2409                 else if (object->soft_del)
2410                         /* Defeat the test */
2411                         matching_chunk = old_chunk;
2412                 else
2413                         matching_chunk =
2414                             yaffs_find_chunk_in_file
2415                             (object, tags.chunk_id,
2416                              NULL);
2417
2418                 if (old_chunk != matching_chunk)
2419                         yaffs_trace(YAFFS_TRACE_ERROR,
2420                                 "gc: page in gc mismatch: %d %d %d %d",
2421                                 old_chunk,
2422                                 matching_chunk,
2423                                 tags.obj_id,
2424                                 tags.chunk_id);
2425         }
2426
2427         if (!object) {
2428                 yaffs_trace(YAFFS_TRACE_ERROR,
2429                         "page %d in gc has no object: %d %d %d ",
2430                         old_chunk,
2431                         tags.obj_id, tags.chunk_id,
2432                         tags.n_bytes);
2433         }
2434
2435         if (object &&
2436             object->deleted &&
2437             object->soft_del && tags.chunk_id != 0) {
2438                 /* Data chunk in a soft deleted file,
2439                  * throw it away.
2440                  * It's a soft deleted data chunk,
2441                  * No need to copy this, just forget
2442                  * about it and fix up the object.
2443                  */
2444
2445                 /* Free chunks already includes
2446                  * softdeleted chunks, how ever this
2447                  * chunk is going to soon be really
2448                  * deleted which will increment free
2449                  * chunks. We have to decrement free
2450                  * chunks so this works out properly.
2451                  */
2452                 dev->n_free_chunks--;
2453                 bi->soft_del_pages--;
2454
2455                 object->n_data_chunks--;
2456                 if (object->n_data_chunks <= 0) {
2457                         /* remeber to clean up obj */
2458                         dev->gc_cleanup_list[dev->n_clean_ups] = tags.obj_id;
2459                         dev->n_clean_ups++;
2460                 }
2461                 mark_flash = 0;
2462         } else if (object) {
2463                 /* It's either a data chunk in a live
2464                  * file or an ObjectHeader, so we're
2465                  * interested in it.
2466                  * NB Need to keep the ObjectHeaders of
2467                  * deleted files until the whole file
2468                  * has been deleted off
2469                  */
2470                 tags.serial_number++;
2471                 dev->n_gc_copies++;
2472
2473                 if (tags.chunk_id == 0) {
2474                         /* It is an object Id,
2475                          * We need to nuke the
2476                          * shrinkheader flags since its
2477                          * work is done.
2478                          * Also need to clean up
2479                          * shadowing.
2480                          */
2481                         struct yaffs_obj_hdr *oh;
2482                         oh = (struct yaffs_obj_hdr *) buffer;
2483
2484                         oh->is_shrink = 0;
2485                         tags.extra_is_shrink = 0;
2486                         oh->shadows_obj = 0;
2487                         oh->inband_shadowed_obj_id = 0;
2488                         tags.extra_shadows = 0;
2489
2490                         /* Update file size */
2491                         if (object->variant_type == YAFFS_OBJECT_TYPE_FILE) {
2492                                 yaffs_oh_size_load(oh,
2493                                     object->variant.file_variant.file_size);
2494                                 tags.extra_file_size =
2495                                     object->variant.file_variant.file_size;
2496                         }
2497
2498                         yaffs_verify_oh(object, oh, &tags, 1);
2499                         new_chunk =
2500                             yaffs_write_new_chunk(dev, (u8 *) oh, &tags, 1);
2501                 } else {
2502                         new_chunk =
2503                             yaffs_write_new_chunk(dev, buffer, &tags, 1);
2504                 }
2505
2506                 if (new_chunk < 0) {
2507                         ret_val = YAFFS_FAIL;
2508                 } else {
2509
2510                         /* Now fix up the Tnodes etc. */
2511
2512                         if (tags.chunk_id == 0) {
2513                                 /* It's a header */
2514                                 object->hdr_chunk = new_chunk;
2515                                 object->serial = tags.serial_number;
2516                         } else {
2517                                 /* It's a data chunk */
2518                                 yaffs_put_chunk_in_file(object, tags.chunk_id,
2519                                                         new_chunk, 0);
2520                         }
2521                 }
2522         }
2523         if (ret_val == YAFFS_OK)
2524                 yaffs_chunk_del(dev, old_chunk, mark_flash, __LINE__);
2525         return ret_val;
2526 }
2527
2528 static int yaffs_gc_block(struct yaffs_dev *dev, int block, int whole_block)
2529 {
2530         int old_chunk;
2531         int ret_val = YAFFS_OK;
2532         int i;
2533         int is_checkpt_block;
2534         int max_copies;
2535         int chunks_before = yaffs_get_erased_chunks(dev);
2536         int chunks_after;
2537         struct yaffs_block_info *bi = yaffs_get_block_info(dev, block);
2538
2539         is_checkpt_block = (bi->block_state == YAFFS_BLOCK_STATE_CHECKPOINT);
2540
2541         yaffs_trace(YAFFS_TRACE_TRACING,
2542                 "Collecting block %d, in use %d, shrink %d, whole_block %d",
2543                 block, bi->pages_in_use, bi->has_shrink_hdr,
2544                 whole_block);
2545
2546         /*yaffs_verify_free_chunks(dev); */
2547
2548         if (bi->block_state == YAFFS_BLOCK_STATE_FULL)
2549                 bi->block_state = YAFFS_BLOCK_STATE_COLLECTING;
2550
2551         bi->has_shrink_hdr = 0; /* clear the flag so that the block can erase */
2552
2553         dev->gc_disable = 1;
2554
2555         yaffs_summary_gc(dev, block);
2556
2557         if (is_checkpt_block || !yaffs_still_some_chunks(dev, block)) {
2558                 yaffs_trace(YAFFS_TRACE_TRACING,
2559                         "Collecting block %d that has no chunks in use",
2560                         block);
2561                 yaffs_block_became_dirty(dev, block);
2562         } else {
2563
2564                 u8 *buffer = yaffs_get_temp_buffer(dev);
2565
2566                 yaffs_verify_blk(dev, bi, block);
2567
2568                 max_copies = (whole_block) ? dev->param.chunks_per_block : 5;
2569                 old_chunk = block * dev->param.chunks_per_block + dev->gc_chunk;
2570
2571                 for (/* init already done */ ;
2572                      ret_val == YAFFS_OK &&
2573                      dev->gc_chunk < dev->param.chunks_per_block &&
2574                      (bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) &&
2575                      max_copies > 0;
2576                      dev->gc_chunk++, old_chunk++) {
2577                         if (yaffs_check_chunk_bit(dev, block, dev->gc_chunk)) {
2578                                 /* Page is in use and might need to be copied */
2579                                 max_copies--;
2580                                 ret_val = yaffs_gc_process_chunk(dev, bi,
2581                                                         old_chunk, buffer);
2582                         }
2583                 }
2584                 yaffs_release_temp_buffer(dev, buffer);
2585         }
2586
2587         yaffs_verify_collected_blk(dev, bi, block);
2588
2589         if (bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) {
2590                 /*
2591                  * The gc did not complete. Set block state back to FULL
2592                  * because checkpointing does not restore gc.
2593                  */
2594                 bi->block_state = YAFFS_BLOCK_STATE_FULL;
2595         } else {
2596                 /* The gc completed. */
2597                 /* Do any required cleanups */
2598                 for (i = 0; i < dev->n_clean_ups; i++) {
2599                         /* Time to delete the file too */
2600                         struct yaffs_obj *object =
2601                             yaffs_find_by_number(dev, dev->gc_cleanup_list[i]);
2602                         if (object) {
2603                                 yaffs_free_tnode(dev,
2604                                           object->variant.file_variant.top);
2605                                 object->variant.file_variant.top = NULL;
2606                                 yaffs_trace(YAFFS_TRACE_GC,
2607                                         "yaffs: About to finally delete object %d",
2608                                         object->obj_id);
2609                                 yaffs_generic_obj_del(object);
2610                                 object->my_dev->n_deleted_files--;
2611                         }
2612
2613                 }
2614                 chunks_after = yaffs_get_erased_chunks(dev);
2615                 if (chunks_before >= chunks_after)
2616                         yaffs_trace(YAFFS_TRACE_GC,
2617                                 "gc did not increase free chunks before %d after %d",
2618                                 chunks_before, chunks_after);
2619                 dev->gc_block = 0;
2620                 dev->gc_chunk = 0;
2621                 dev->n_clean_ups = 0;
2622         }
2623
2624         dev->gc_disable = 0;
2625
2626         return ret_val;
2627 }
2628
2629 /*
2630  * find_gc_block() selects the dirtiest block (or close enough)
2631  * for garbage collection.
2632  */
2633
2634 static unsigned yaffs_find_gc_block(struct yaffs_dev *dev,
2635                                     int aggressive, int background)
2636 {
2637         int i;
2638         int iterations;
2639         unsigned selected = 0;
2640         int prioritised = 0;
2641         int prioritised_exist = 0;
2642         struct yaffs_block_info *bi;
2643         int threshold;
2644
2645         /* First let's see if we need to grab a prioritised block */
2646         if (dev->has_pending_prioritised_gc && !aggressive) {
2647                 dev->gc_dirtiest = 0;
2648                 bi = dev->block_info;
2649                 for (i = dev->internal_start_block;
2650                      i <= dev->internal_end_block && !selected; i++) {
2651
2652                         if (bi->gc_prioritise) {
2653                                 prioritised_exist = 1;
2654                                 if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&
2655                                     yaffs_block_ok_for_gc(dev, bi)) {
2656                                         selected = i;
2657                                         prioritised = 1;
2658                                 }
2659                         }
2660                         bi++;
2661                 }
2662
2663                 /*
2664                  * If there is a prioritised block and none was selected then
2665                  * this happened because there is at least one old dirty block
2666                  * gumming up the works. Let's gc the oldest dirty block.
2667                  */
2668
2669                 if (prioritised_exist &&
2670                     !selected && dev->oldest_dirty_block > 0)
2671                         selected = dev->oldest_dirty_block;
2672
2673                 if (!prioritised_exist) /* None found, so we can clear this */
2674                         dev->has_pending_prioritised_gc = 0;
2675         }
2676
2677         /* If we're doing aggressive GC then we are happy to take a less-dirty
2678          * block, and search harder.
2679          * else (leasurely gc), then we only bother to do this if the
2680          * block has only a few pages in use.
2681          */
2682
2683         if (!selected) {
2684                 int pages_used;
2685                 int n_blocks =
2686                     dev->internal_end_block - dev->internal_start_block + 1;
2687                 if (aggressive) {
2688                         threshold = dev->param.chunks_per_block;
2689                         iterations = n_blocks;
2690                 } else {
2691                         int max_threshold;
2692
2693                         if (background)
2694                                 max_threshold = dev->param.chunks_per_block / 2;
2695                         else
2696                                 max_threshold = dev->param.chunks_per_block / 8;
2697
2698                         if (max_threshold < YAFFS_GC_PASSIVE_THRESHOLD)
2699                                 max_threshold = YAFFS_GC_PASSIVE_THRESHOLD;
2700
2701                         threshold = background ? (dev->gc_not_done + 2) * 2 : 0;
2702                         if (threshold < YAFFS_GC_PASSIVE_THRESHOLD)
2703                                 threshold = YAFFS_GC_PASSIVE_THRESHOLD;
2704                         if (threshold > max_threshold)
2705                                 threshold = max_threshold;
2706
2707                         iterations = n_blocks / 16 + 1;
2708                         if (iterations > 100)
2709                                 iterations = 100;
2710                 }
2711
2712                 for (i = 0;
2713                      i < iterations &&
2714                      (dev->gc_dirtiest < 1 ||
2715                       dev->gc_pages_in_use > YAFFS_GC_GOOD_ENOUGH);
2716                      i++) {
2717                         dev->gc_block_finder++;
2718                         if (dev->gc_block_finder < dev->internal_start_block ||
2719                             dev->gc_block_finder > dev->internal_end_block)
2720                                 dev->gc_block_finder =
2721                                     dev->internal_start_block;
2722
2723                         bi = yaffs_get_block_info(dev, dev->gc_block_finder);
2724
2725                         pages_used = bi->pages_in_use - bi->soft_del_pages;
2726
2727                         if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&
2728                             pages_used < dev->param.chunks_per_block &&
2729                             (dev->gc_dirtiest < 1 ||
2730                              pages_used < dev->gc_pages_in_use) &&
2731                             yaffs_block_ok_for_gc(dev, bi)) {
2732                                 dev->gc_dirtiest = dev->gc_block_finder;
2733                                 dev->gc_pages_in_use = pages_used;
2734                         }
2735                 }
2736
2737                 if (dev->gc_dirtiest > 0 && dev->gc_pages_in_use <= threshold)
2738                         selected = dev->gc_dirtiest;
2739         }
2740
2741         /*
2742          * If nothing has been selected for a while, try the oldest dirty
2743          * because that's gumming up the works.
2744          */
2745
2746         if (!selected && dev->param.is_yaffs2 &&
2747             dev->gc_not_done >= (background ? 10 : 20)) {
2748                 yaffs2_find_oldest_dirty_seq(dev);
2749                 if (dev->oldest_dirty_block > 0) {
2750                         selected = dev->oldest_dirty_block;
2751                         dev->gc_dirtiest = selected;
2752                         dev->oldest_dirty_gc_count++;
2753                         bi = yaffs_get_block_info(dev, selected);
2754                         dev->gc_pages_in_use =
2755                             bi->pages_in_use - bi->soft_del_pages;
2756                 } else {
2757                         dev->gc_not_done = 0;
2758                 }
2759         }
2760
2761         if (selected) {
2762                 yaffs_trace(YAFFS_TRACE_GC,
2763                         "GC Selected block %d with %d free, prioritised:%d",
2764                         selected,
2765                         dev->param.chunks_per_block - dev->gc_pages_in_use,
2766                         prioritised);
2767
2768                 dev->n_gc_blocks++;
2769                 if (background)
2770                         dev->bg_gcs++;
2771
2772                 dev->gc_dirtiest = 0;
2773                 dev->gc_pages_in_use = 0;
2774                 dev->gc_not_done = 0;
2775                 if (dev->refresh_skip > 0)
2776                         dev->refresh_skip--;
2777         } else {
2778                 dev->gc_not_done++;
2779                 yaffs_trace(YAFFS_TRACE_GC,
2780                         "GC none: finder %d skip %d threshold %d dirtiest %d using %d oldest %d%s",
2781                         dev->gc_block_finder, dev->gc_not_done, threshold,
2782                         dev->gc_dirtiest, dev->gc_pages_in_use,
2783                         dev->oldest_dirty_block, background ? " bg" : "");
2784         }
2785
2786         return selected;
2787 }
2788
2789 /* New garbage collector
2790  * If we're very low on erased blocks then we do aggressive garbage collection
2791  * otherwise we do "leasurely" garbage collection.
2792  * Aggressive gc looks further (whole array) and will accept less dirty blocks.
2793  * Passive gc only inspects smaller areas and only accepts more dirty blocks.
2794  *
2795  * The idea is to help clear out space in a more spread-out manner.
2796  * Dunno if it really does anything useful.
2797  */
2798 static int yaffs_check_gc(struct yaffs_dev *dev, int background)
2799 {
2800         int aggressive = 0;
2801         int gc_ok = YAFFS_OK;
2802         int max_tries = 0;
2803         int min_erased;
2804         int erased_chunks;
2805         int checkpt_block_adjust;
2806
2807         if (dev->param.gc_control && (dev->param.gc_control(dev) & 1) == 0)
2808                 return YAFFS_OK;
2809
2810         if (dev->gc_disable)
2811                 /* Bail out so we don't get recursive gc */
2812                 return YAFFS_OK;
2813
2814         /* This loop should pass the first time.
2815          * Only loops here if the collection does not increase space.
2816          */
2817
2818         do {
2819                 max_tries++;
2820
2821                 checkpt_block_adjust = yaffs_calc_checkpt_blocks_required(dev);
2822
2823                 min_erased =
2824                     dev->param.n_reserved_blocks + checkpt_block_adjust + 1;
2825                 erased_chunks =
2826                     dev->n_erased_blocks * dev->param.chunks_per_block;
2827
2828                 /* If we need a block soon then do aggressive gc. */
2829                 if (dev->n_erased_blocks < min_erased)
2830                         aggressive = 1;
2831                 else {
2832                         if (!background
2833                             && erased_chunks > (dev->n_free_chunks / 4))
2834                                 break;
2835
2836                         if (dev->gc_skip > 20)
2837                                 dev->gc_skip = 20;
2838                         if (erased_chunks < dev->n_free_chunks / 2 ||
2839                             dev->gc_skip < 1 || background)
2840                                 aggressive = 0;
2841                         else {
2842                                 dev->gc_skip--;
2843                                 break;
2844                         }
2845                 }
2846
2847                 dev->gc_skip = 5;
2848
2849                 /* If we don't already have a block being gc'd then see if we
2850                  * should start another */
2851
2852                 if (dev->gc_block < 1 && !aggressive) {
2853                         dev->gc_block = yaffs2_find_refresh_block(dev);
2854                         dev->gc_chunk = 0;
2855                         dev->n_clean_ups = 0;
2856                 }
2857                 if (dev->gc_block < 1) {
2858                         dev->gc_block =
2859                             yaffs_find_gc_block(dev, aggressive, background);
2860                         dev->gc_chunk = 0;
2861                         dev->n_clean_ups = 0;
2862                 }
2863
2864                 if (dev->gc_block > 0) {
2865                         dev->all_gcs++;
2866                         if (!aggressive)
2867                                 dev->passive_gc_count++;
2868
2869                         yaffs_trace(YAFFS_TRACE_GC,
2870                                 "yaffs: GC n_erased_blocks %d aggressive %d",
2871                                 dev->n_erased_blocks, aggressive);
2872
2873                         gc_ok = yaffs_gc_block(dev, dev->gc_block, aggressive);
2874                 }
2875
2876                 if (dev->n_erased_blocks < (dev->param.n_reserved_blocks) &&
2877                     dev->gc_block > 0) {
2878                         yaffs_trace(YAFFS_TRACE_GC,
2879                                 "yaffs: GC !!!no reclaim!!! n_erased_blocks %d after try %d block %d",
2880                                 dev->n_erased_blocks, max_tries,
2881                                 dev->gc_block);
2882                 }
2883         } while ((dev->n_erased_blocks < dev->param.n_reserved_blocks) &&
2884                  (dev->gc_block > 0) && (max_tries < 2));
2885
2886         return aggressive ? gc_ok : YAFFS_OK;
2887 }
2888
2889 /*
2890  * yaffs_bg_gc()
2891  * Garbage collects. Intended to be called from a background thread.
2892  * Returns non-zero if at least half the free chunks are erased.
2893  */
2894 int yaffs_bg_gc(struct yaffs_dev *dev, unsigned urgency)
2895 {
2896         int erased_chunks = dev->n_erased_blocks * dev->param.chunks_per_block;
2897
2898         yaffs_trace(YAFFS_TRACE_BACKGROUND, "Background gc %u", urgency);
2899
2900         yaffs_check_gc(dev, 1);
2901         return erased_chunks > dev->n_free_chunks / 2;
2902 }
2903
2904 /*-------------------- Data file manipulation -----------------*/
2905
2906 static int yaffs_rd_data_obj(struct yaffs_obj *in, int inode_chunk, u8 * buffer)
2907 {
2908         int nand_chunk = yaffs_find_chunk_in_file(in, inode_chunk, NULL);
2909
2910         if (nand_chunk >= 0)
2911                 return yaffs_rd_chunk_tags_nand(in->my_dev, nand_chunk,
2912                                                 buffer, NULL);
2913         else {
2914                 yaffs_trace(YAFFS_TRACE_NANDACCESS,
2915                         "Chunk %d not found zero instead",
2916                         nand_chunk);
2917                 /* get sane (zero) data if you read a hole */
2918                 memset(buffer, 0, in->my_dev->data_bytes_per_chunk);
2919                 return 0;
2920         }
2921
2922 }
2923
2924 void yaffs_chunk_del(struct yaffs_dev *dev, int chunk_id, int mark_flash,
2925                      int lyn)
2926 {
2927         int block;
2928         int page;
2929         struct yaffs_ext_tags tags;
2930         struct yaffs_block_info *bi;
2931
2932         if (chunk_id <= 0)
2933                 return;
2934
2935         dev->n_deletions++;
2936         block = chunk_id / dev->param.chunks_per_block;
2937         page = chunk_id % dev->param.chunks_per_block;
2938
2939         if (!yaffs_check_chunk_bit(dev, block, page))
2940                 yaffs_trace(YAFFS_TRACE_VERIFY,
2941                         "Deleting invalid chunk %d", chunk_id);
2942
2943         bi = yaffs_get_block_info(dev, block);
2944
2945         yaffs2_update_oldest_dirty_seq(dev, block, bi);
2946
2947         yaffs_trace(YAFFS_TRACE_DELETION,
2948                 "line %d delete of chunk %d",
2949                 lyn, chunk_id);
2950
2951         if (!dev->param.is_yaffs2 && mark_flash &&
2952             bi->block_state != YAFFS_BLOCK_STATE_COLLECTING) {
2953
2954                 memset(&tags, 0, sizeof(tags));
2955                 tags.is_deleted = 1;
2956                 yaffs_wr_chunk_tags_nand(dev, chunk_id, NULL, &tags);
2957                 yaffs_handle_chunk_update(dev, chunk_id, &tags);
2958         } else {
2959                 dev->n_unmarked_deletions++;
2960         }
2961
2962         /* Pull out of the management area.
2963          * If the whole block became dirty, this will kick off an erasure.
2964          */
2965         if (bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING ||
2966             bi->block_state == YAFFS_BLOCK_STATE_FULL ||
2967             bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
2968             bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) {
2969                 dev->n_free_chunks++;
2970                 yaffs_clear_chunk_bit(dev, block, page);
2971                 bi->pages_in_use--;
2972
2973                 if (bi->pages_in_use == 0 &&
2974                     !bi->has_shrink_hdr &&
2975                     bi->block_state != YAFFS_BLOCK_STATE_ALLOCATING &&
2976                     bi->block_state != YAFFS_BLOCK_STATE_NEEDS_SCAN) {
2977                         yaffs_block_became_dirty(dev, block);
2978                 }
2979         }
2980 }
2981
2982 static int yaffs_wr_data_obj(struct yaffs_obj *in, int inode_chunk,
2983                              const u8 *buffer, int n_bytes, int use_reserve)
2984 {
2985         /* Find old chunk Need to do this to get serial number
2986          * Write new one and patch into tree.
2987          * Invalidate old tags.
2988          */
2989
2990         int prev_chunk_id;
2991         struct yaffs_ext_tags prev_tags;
2992         int new_chunk_id;
2993         struct yaffs_ext_tags new_tags;
2994         struct yaffs_dev *dev = in->my_dev;
2995
2996         yaffs_check_gc(dev, 0);
2997
2998         /* Get the previous chunk at this location in the file if it exists.
2999          * If it does not exist then put a zero into the tree. This creates
3000          * the tnode now, rather than later when it is harder to clean up.
3001          */
3002         prev_chunk_id = yaffs_find_chunk_in_file(in, inode_chunk, &prev_tags);
3003         if (prev_chunk_id < 1 &&
3004             !yaffs_put_chunk_in_file(in, inode_chunk, 0, 0))
3005                 return 0;
3006
3007         /* Set up new tags */
3008         memset(&new_tags, 0, sizeof(new_tags));
3009
3010         new_tags.chunk_id = inode_chunk;
3011         new_tags.obj_id = in->obj_id;
3012         new_tags.serial_number =
3013             (prev_chunk_id > 0) ? prev_tags.serial_number + 1 : 1;
3014         new_tags.n_bytes = n_bytes;
3015
3016         if (n_bytes < 1 || n_bytes > dev->param.total_bytes_per_chunk) {
3017                 yaffs_trace(YAFFS_TRACE_ERROR,
3018                   "Writing %d bytes to chunk!!!!!!!!!",
3019                    n_bytes);
3020                 BUG();
3021         }
3022
3023         new_chunk_id =
3024             yaffs_write_new_chunk(dev, buffer, &new_tags, use_reserve);
3025
3026         if (new_chunk_id > 0) {
3027                 yaffs_put_chunk_in_file(in, inode_chunk, new_chunk_id, 0);
3028
3029                 if (prev_chunk_id > 0)
3030                         yaffs_chunk_del(dev, prev_chunk_id, 1, __LINE__);
3031
3032                 yaffs_verify_file_sane(in);
3033         }
3034         return new_chunk_id;
3035
3036 }
3037
3038
3039
3040 static int yaffs_do_xattrib_mod(struct yaffs_obj *obj, int set,
3041                                 const YCHAR *name, const void *value, int size,
3042                                 int flags)
3043 {
3044         struct yaffs_xattr_mod xmod;
3045         int result;
3046
3047         xmod.set = set;
3048         xmod.name = name;
3049         xmod.data = value;
3050         xmod.size = size;
3051         xmod.flags = flags;
3052         xmod.result = -ENOSPC;
3053
3054         result = yaffs_update_oh(obj, NULL, 0, 0, 0, &xmod);
3055
3056         if (result > 0)
3057                 return xmod.result;
3058         else
3059                 return -ENOSPC;
3060 }
3061
3062 static int yaffs_apply_xattrib_mod(struct yaffs_obj *obj, char *buffer,
3063                                    struct yaffs_xattr_mod *xmod)
3064 {
3065         int retval = 0;
3066         int x_offs = sizeof(struct yaffs_obj_hdr);
3067         struct yaffs_dev *dev = obj->my_dev;
3068         int x_size = dev->data_bytes_per_chunk - sizeof(struct yaffs_obj_hdr);
3069         char *x_buffer = buffer + x_offs;
3070
3071         if (xmod->set)
3072                 retval =
3073                     nval_set(x_buffer, x_size, xmod->name, xmod->data,
3074                              xmod->size, xmod->flags);
3075         else
3076                 retval = nval_del(x_buffer, x_size, xmod->name);
3077
3078         obj->has_xattr = nval_hasvalues(x_buffer, x_size);
3079         obj->xattr_known = 1;
3080         xmod->result = retval;
3081
3082         return retval;
3083 }
3084
3085 static int yaffs_do_xattrib_fetch(struct yaffs_obj *obj, const YCHAR *name,
3086                                   void *value, int size)
3087 {
3088         char *buffer = NULL;
3089         int result;
3090         struct yaffs_ext_tags tags;
3091         struct yaffs_dev *dev = obj->my_dev;
3092         int x_offs = sizeof(struct yaffs_obj_hdr);
3093         int x_size = dev->data_bytes_per_chunk - sizeof(struct yaffs_obj_hdr);
3094         char *x_buffer;
3095         int retval = 0;
3096
3097         if (obj->hdr_chunk < 1)
3098                 return -ENODATA;
3099
3100         /* If we know that the object has no xattribs then don't do all the
3101          * reading and parsing.
3102          */
3103         if (obj->xattr_known && !obj->has_xattr) {
3104                 if (name)
3105                         return -ENODATA;
3106                 else
3107                         return 0;
3108         }
3109
3110         buffer = (char *)yaffs_get_temp_buffer(dev);
3111         if (!buffer)
3112                 return -ENOMEM;
3113
3114         result =
3115             yaffs_rd_chunk_tags_nand(dev, obj->hdr_chunk, (u8 *) buffer, &tags);
3116
3117         if (result != YAFFS_OK)
3118                 retval = -ENOENT;
3119         else {
3120                 x_buffer = buffer + x_offs;
3121
3122                 if (!obj->xattr_known) {
3123                         obj->has_xattr = nval_hasvalues(x_buffer, x_size);
3124                         obj->xattr_known = 1;
3125                 }
3126
3127                 if (name)
3128                         retval = nval_get(x_buffer, x_size, name, value, size);
3129                 else
3130                         retval = nval_list(x_buffer, x_size, value, size);
3131         }
3132         yaffs_release_temp_buffer(dev, (u8 *) buffer);
3133         return retval;
3134 }
3135
3136 int yaffs_set_xattrib(struct yaffs_obj *obj, const YCHAR * name,
3137                       const void *value, int size, int flags)
3138 {
3139         return yaffs_do_xattrib_mod(obj, 1, name, value, size, flags);
3140 }
3141
3142 int yaffs_remove_xattrib(struct yaffs_obj *obj, const YCHAR * name)
3143 {
3144         return yaffs_do_xattrib_mod(obj, 0, name, NULL, 0, 0);
3145 }
3146
3147 int yaffs_get_xattrib(struct yaffs_obj *obj, const YCHAR * name, void *value,
3148                       int size)
3149 {
3150         return yaffs_do_xattrib_fetch(obj, name, value, size);
3151 }
3152
3153 int yaffs_list_xattrib(struct yaffs_obj *obj, char *buffer, int size)
3154 {
3155         return yaffs_do_xattrib_fetch(obj, NULL, buffer, size);
3156 }
3157
3158 static void yaffs_check_obj_details_loaded(struct yaffs_obj *in)
3159 {
3160         u8 *buf;
3161         struct yaffs_obj_hdr *oh;
3162         struct yaffs_dev *dev;
3163         struct yaffs_ext_tags tags;
3164         int result;
3165         int alloc_failed = 0;
3166
3167         if (!in || !in->lazy_loaded || in->hdr_chunk < 1)
3168                 return;
3169
3170         dev = in->my_dev;
3171         in->lazy_loaded = 0;
3172         buf = yaffs_get_temp_buffer(dev);
3173
3174         result = yaffs_rd_chunk_tags_nand(dev, in->hdr_chunk, buf, &tags);
3175         oh = (struct yaffs_obj_hdr *)buf;
3176
3177         in->yst_mode = oh->yst_mode;
3178         yaffs_load_attribs(in, oh);
3179         yaffs_set_obj_name_from_oh(in, oh);
3180
3181         if (in->variant_type == YAFFS_OBJECT_TYPE_SYMLINK) {
3182                 in->variant.symlink_variant.alias =
3183                     yaffs_clone_str(oh->alias);
3184                 if (!in->variant.symlink_variant.alias)
3185                         alloc_failed = 1;       /* Not returned */
3186         }
3187         yaffs_release_temp_buffer(dev, buf);
3188 }
3189
3190 static void yaffs_load_name_from_oh(struct yaffs_dev *dev, YCHAR *name,
3191                                     const YCHAR *oh_name, int buff_size)
3192 {
3193 #ifdef CONFIG_YAFFS_AUTO_UNICODE
3194         if (dev->param.auto_unicode) {
3195                 if (*oh_name) {
3196                         /* It is an ASCII name, do an ASCII to
3197                          * unicode conversion */
3198                         const char *ascii_oh_name = (const char *)oh_name;
3199                         int n = buff_size - 1;
3200                         while (n > 0 && *ascii_oh_name) {
3201                                 *name = *ascii_oh_name;
3202                                 name++;
3203                                 ascii_oh_name++;
3204                                 n--;
3205                         }
3206                 } else {
3207                         strncpy(name, oh_name + 1, buff_size - 1);
3208                 }
3209         } else {
3210 #else
3211         (void) dev;
3212         {
3213 #endif
3214                 strncpy(name, oh_name, buff_size - 1);
3215         }
3216 }
3217
3218 static void yaffs_load_oh_from_name(struct yaffs_dev *dev, YCHAR *oh_name,
3219                                     const YCHAR *name)
3220 {
3221 #ifdef CONFIG_YAFFS_AUTO_UNICODE
3222
3223         int is_ascii;
3224         YCHAR *w;
3225
3226         if (dev->param.auto_unicode) {
3227
3228                 is_ascii = 1;
3229                 w = name;
3230
3231                 /* Figure out if the name will fit in ascii character set */
3232                 while (is_ascii && *w) {
3233                         if ((*w) & 0xff00)
3234                                 is_ascii = 0;
3235                         w++;
3236                 }
3237
3238                 if (is_ascii) {
3239                         /* It is an ASCII name, so convert unicode to ascii */
3240                         char *ascii_oh_name = (char *)oh_name;
3241                         int n = YAFFS_MAX_NAME_LENGTH - 1;
3242                         while (n > 0 && *name) {
3243                                 *ascii_oh_name = *name;
3244                                 name++;
3245                                 ascii_oh_name++;
3246                                 n--;
3247                         }
3248                 } else {
3249                         /* Unicode name, so save starting at the second YCHAR */
3250                         *oh_name = 0;
3251                         strncpy(oh_name + 1, name, YAFFS_MAX_NAME_LENGTH - 2);
3252                 }
3253         } else {
3254 #else
3255         dev = dev;
3256         {
3257 #endif
3258                 strncpy(oh_name, name, YAFFS_MAX_NAME_LENGTH - 1);
3259         }
3260 }
3261
3262 /* UpdateObjectHeader updates the header on NAND for an object.
3263  * If name is not NULL, then that new name is used.
3264  */
3265 int yaffs_update_oh(struct yaffs_obj *in, const YCHAR *name, int force,
3266                     int is_shrink, int shadows, struct yaffs_xattr_mod *xmod)
3267 {
3268
3269         struct yaffs_block_info *bi;
3270         struct yaffs_dev *dev = in->my_dev;
3271         int prev_chunk_id;
3272         int ret_val = 0;
3273         int result = 0;
3274         int new_chunk_id;
3275         struct yaffs_ext_tags new_tags;
3276         struct yaffs_ext_tags old_tags;
3277         const YCHAR *alias = NULL;
3278         u8 *buffer = NULL;
3279         YCHAR old_name[YAFFS_MAX_NAME_LENGTH + 1];
3280         struct yaffs_obj_hdr *oh = NULL;
3281         loff_t file_size = 0;
3282
3283         strcpy(old_name, _Y("silly old name"));
3284
3285         if (in->fake && in != dev->root_dir && !force && !xmod)
3286                 return ret_val;
3287
3288         yaffs_check_gc(dev, 0);
3289         yaffs_check_obj_details_loaded(in);
3290
3291         buffer = yaffs_get_temp_buffer(in->my_dev);
3292         oh = (struct yaffs_obj_hdr *)buffer;
3293
3294         prev_chunk_id = in->hdr_chunk;
3295
3296         if (prev_chunk_id > 0) {
3297                 result = yaffs_rd_chunk_tags_nand(dev, prev_chunk_id,
3298                                                   buffer, &old_tags);
3299
3300                 yaffs_verify_oh(in, oh, &old_tags, 0);
3301                 memcpy(old_name, oh->name, sizeof(oh->name));
3302                 memset(buffer, 0xff, sizeof(struct yaffs_obj_hdr));
3303         } else {
3304                 memset(buffer, 0xff, dev->data_bytes_per_chunk);
3305         }
3306
3307         oh->type = in->variant_type;
3308         oh->yst_mode = in->yst_mode;
3309         oh->shadows_obj = oh->inband_shadowed_obj_id = shadows;
3310
3311         yaffs_load_attribs_oh(oh, in);
3312
3313         if (in->parent)
3314                 oh->parent_obj_id = in->parent->obj_id;
3315         else
3316                 oh->parent_obj_id = 0;
3317
3318         if (name && *name) {
3319                 memset(oh->name, 0, sizeof(oh->name));
3320                 yaffs_load_oh_from_name(dev, oh->name, name);
3321         } else if (prev_chunk_id > 0) {
3322                 memcpy(oh->name, old_name, sizeof(oh->name));
3323         } else {
3324                 memset(oh->name, 0, sizeof(oh->name));
3325         }
3326
3327         oh->is_shrink = is_shrink;
3328
3329         switch (in->variant_type) {
3330         case YAFFS_OBJECT_TYPE_UNKNOWN:
3331                 /* Should not happen */
3332                 break;
3333         case YAFFS_OBJECT_TYPE_FILE:
3334                 if (oh->parent_obj_id != YAFFS_OBJECTID_DELETED &&
3335                     oh->parent_obj_id != YAFFS_OBJECTID_UNLINKED)
3336                         file_size = in->variant.file_variant.file_size;
3337                 yaffs_oh_size_load(oh, file_size);
3338                 break;
3339         case YAFFS_OBJECT_TYPE_HARDLINK:
3340                 oh->equiv_id = in->variant.hardlink_variant.equiv_id;
3341                 break;
3342         case YAFFS_OBJECT_TYPE_SPECIAL:
3343                 /* Do nothing */
3344                 break;
3345         case YAFFS_OBJECT_TYPE_DIRECTORY:
3346                 /* Do nothing */
3347                 break;
3348         case YAFFS_OBJECT_TYPE_SYMLINK:
3349                 alias = in->variant.symlink_variant.alias;
3350                 if (!alias)
3351                         alias = _Y("no alias");
3352                 strncpy(oh->alias, alias, YAFFS_MAX_ALIAS_LENGTH);
3353                 oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
3354                 break;
3355         }
3356
3357         /* process any xattrib modifications */
3358         if (xmod)
3359                 yaffs_apply_xattrib_mod(in, (char *)buffer, xmod);
3360
3361         /* Tags */
3362         memset(&new_tags, 0, sizeof(new_tags));
3363         in->serial++;
3364         new_tags.chunk_id = 0;
3365         new_tags.obj_id = in->obj_id;
3366         new_tags.serial_number = in->serial;
3367
3368         /* Add extra info for file header */
3369         new_tags.extra_available = 1;
3370         new_tags.extra_parent_id = oh->parent_obj_id;
3371         new_tags.extra_file_size = file_size;
3372         new_tags.extra_is_shrink = oh->is_shrink;
3373         new_tags.extra_equiv_id = oh->equiv_id;
3374         new_tags.extra_shadows = (oh->shadows_obj > 0) ? 1 : 0;
3375         new_tags.extra_obj_type = in->variant_type;
3376         yaffs_verify_oh(in, oh, &new_tags, 1);
3377
3378         /* Create new chunk in NAND */
3379         new_chunk_id =
3380             yaffs_write_new_chunk(dev, buffer, &new_tags,
3381                                   (prev_chunk_id > 0) ? 1 : 0);
3382
3383         if (buffer)
3384                 yaffs_release_temp_buffer(dev, buffer);
3385
3386         if (new_chunk_id < 0)
3387                 return new_chunk_id;
3388
3389         in->hdr_chunk = new_chunk_id;
3390
3391         if (prev_chunk_id > 0)
3392                 yaffs_chunk_del(dev, prev_chunk_id, 1, __LINE__);
3393
3394         if (!yaffs_obj_cache_dirty(in))
3395                 in->dirty = 0;
3396
3397         /* If this was a shrink, then mark the block
3398          * that the chunk lives on */
3399         if (is_shrink) {
3400                 bi = yaffs_get_block_info(in->my_dev,
3401                                           new_chunk_id /
3402                                           in->my_dev->param.chunks_per_block);
3403                 bi->has_shrink_hdr = 1;
3404         }
3405
3406
3407         return new_chunk_id;
3408 }
3409
3410 /*--------------------- File read/write ------------------------
3411  * Read and write have very similar structures.
3412  * In general the read/write has three parts to it
3413  * An incomplete chunk to start with (if the read/write is not chunk-aligned)
3414  * Some complete chunks
3415  * An incomplete chunk to end off with
3416  *
3417  * Curve-balls: the first chunk might also be the last chunk.
3418  */
3419
3420 int yaffs_file_rd(struct yaffs_obj *in, u8 * buffer, loff_t offset, int n_bytes)
3421 {
3422         int chunk;
3423         u32 start;
3424         int n_copy;
3425         int n = n_bytes;
3426         int n_done = 0;
3427         struct yaffs_cache *cache;
3428         struct yaffs_dev *dev;
3429
3430         dev = in->my_dev;
3431
3432         while (n > 0) {
3433                 yaffs_addr_to_chunk(dev, offset, &chunk, &start);
3434                 chunk++;
3435
3436                 /* OK now check for the curveball where the start and end are in
3437                  * the same chunk.
3438                  */
3439                 if ((start + n) < dev->data_bytes_per_chunk)
3440                         n_copy = n;
3441                 else
3442                         n_copy = dev->data_bytes_per_chunk - start;
3443
3444                 cache = yaffs_find_chunk_cache(in, chunk);
3445
3446                 /* If the chunk is already in the cache or it is less than
3447                  * a whole chunk or we're using inband tags then use the cache
3448                  * (if there is caching) else bypass the cache.
3449                  */
3450                 if (cache || n_copy != dev->data_bytes_per_chunk ||
3451                     dev->param.inband_tags) {
3452                         if (dev->param.n_caches > 0) {
3453
3454                                 /* If we can't find the data in the cache,
3455                                  * then load it up. */
3456
3457                                 if (!cache) {
3458                                         cache =
3459                                             yaffs_grab_chunk_cache(in->my_dev);
3460                                         cache->object = in;
3461                                         cache->chunk_id = chunk;
3462                                         cache->dirty = 0;
3463                                         cache->locked = 0;
3464                                         yaffs_rd_data_obj(in, chunk,
3465                                                           cache->data);
3466                                         cache->n_bytes = 0;
3467                                 }
3468
3469                                 yaffs_use_cache(dev, cache, 0);
3470
3471                                 cache->locked = 1;
3472
3473                                 memcpy(buffer, &cache->data[start], n_copy);
3474
3475                                 cache->locked = 0;
3476                         } else {
3477                                 /* Read into the local buffer then copy.. */
3478
3479                                 u8 *local_buffer =
3480                                     yaffs_get_temp_buffer(dev);
3481                                 yaffs_rd_data_obj(in, chunk, local_buffer);
3482
3483                                 memcpy(buffer, &local_buffer[start], n_copy);
3484
3485                                 yaffs_release_temp_buffer(dev, local_buffer);
3486                         }
3487                 } else {
3488                         /* A full chunk. Read directly into the buffer. */
3489                         yaffs_rd_data_obj(in, chunk, buffer);
3490                 }
3491                 n -= n_copy;
3492                 offset += n_copy;
3493                 buffer += n_copy;
3494                 n_done += n_copy;
3495         }
3496         return n_done;
3497 }
3498
3499 int yaffs_do_file_wr(struct yaffs_obj *in, const u8 *buffer, loff_t offset,
3500                      int n_bytes, int write_through)
3501 {
3502
3503         int chunk;
3504         u32 start;
3505         int n_copy;
3506         int n = n_bytes;
3507         int n_done = 0;
3508         int n_writeback;
3509         loff_t start_write = offset;
3510         int chunk_written = 0;
3511         u32 n_bytes_read;
3512         loff_t chunk_start;
3513         struct yaffs_dev *dev;
3514
3515         dev = in->my_dev;
3516
3517         while (n > 0 && chunk_written >= 0) {
3518                 yaffs_addr_to_chunk(dev, offset, &chunk, &start);
3519
3520                 if (((loff_t)chunk) *
3521                     dev->data_bytes_per_chunk + start != offset ||
3522                     start >= dev->data_bytes_per_chunk) {
3523                         yaffs_trace(YAFFS_TRACE_ERROR,
3524                                 "AddrToChunk of offset %lld gives chunk %d start %d",
3525                                 offset, chunk, start);
3526                 }
3527                 chunk++;        /* File pos to chunk in file offset */
3528
3529                 /* OK now check for the curveball where the start and end are in
3530                  * the same chunk.
3531                  */
3532
3533                 if ((start + n) < dev->data_bytes_per_chunk) {
3534                         n_copy = n;
3535
3536                         /* Now calculate how many bytes to write back....
3537                          * If we're overwriting and not writing to then end of
3538                          * file then we need to write back as much as was there
3539                          * before.
3540                          */
3541
3542                         chunk_start = (((loff_t)(chunk - 1)) *
3543                                         dev->data_bytes_per_chunk);
3544
3545                         if (chunk_start > in->variant.file_variant.file_size)
3546                                 n_bytes_read = 0;       /* Past end of file */
3547                         else
3548                                 n_bytes_read =
3549                                     in->variant.file_variant.file_size -
3550                                     chunk_start;
3551
3552                         if (n_bytes_read > dev->data_bytes_per_chunk)
3553                                 n_bytes_read = dev->data_bytes_per_chunk;
3554
3555                         n_writeback =
3556                             (n_bytes_read >
3557                              (start + n)) ? n_bytes_read : (start + n);
3558
3559                         if (n_writeback < 0 ||
3560                             n_writeback > dev->data_bytes_per_chunk)
3561                                 BUG();
3562
3563                 } else {
3564                         n_copy = dev->data_bytes_per_chunk - start;
3565                         n_writeback = dev->data_bytes_per_chunk;
3566                 }
3567
3568                 if (n_copy != dev->data_bytes_per_chunk ||
3569                     dev->param.inband_tags) {
3570                         /* An incomplete start or end chunk (or maybe both
3571                          * start and end chunk), or we're using inband tags,
3572                          * so we want to use the cache buffers.
3573                          */
3574                         if (dev->param.n_caches > 0) {
3575                                 struct yaffs_cache *cache;
3576
3577                                 /* If we can't find the data in the cache, then
3578                                  * load the cache */
3579                                 cache = yaffs_find_chunk_cache(in, chunk);
3580
3581                                 if (!cache &&
3582                                     yaffs_check_alloc_available(dev, 1)) {
3583                                         cache = yaffs_grab_chunk_cache(dev);
3584                                         cache->object = in;
3585                                         cache->chunk_id = chunk;
3586                                         cache->dirty = 0;
3587                                         cache->locked = 0;
3588                                         yaffs_rd_data_obj(in, chunk,
3589                                                           cache->data);
3590                                 } else if (cache &&
3591                                            !cache->dirty &&
3592                                            !yaffs_check_alloc_available(dev,
3593                                                                         1)) {
3594                                         /* Drop the cache if it was a read cache
3595                                          * item and no space check has been made
3596                                          * for it.
3597                                          */
3598                                         cache = NULL;
3599                                 }
3600
3601                                 if (cache) {
3602                                         yaffs_use_cache(dev, cache, 1);
3603                                         cache->locked = 1;
3604
3605                                         memcpy(&cache->data[start], buffer,
3606                                                n_copy);
3607
3608                                         cache->locked = 0;
3609                                         cache->n_bytes = n_writeback;
3610
3611                                         if (write_through) {
3612                                                 chunk_written =
3613                                                     yaffs_wr_data_obj
3614                                                     (cache->object,
3615                                                      cache->chunk_id,
3616                                                      cache->data,
3617                                                      cache->n_bytes, 1);
3618                                                 cache->dirty = 0;
3619                                         }
3620                                 } else {
3621                                         chunk_written = -1;     /* fail write */
3622                                 }
3623                         } else {
3624                                 /* An incomplete start or end chunk (or maybe
3625                                  * both start and end chunk). Read into the
3626                                  * local buffer then copy over and write back.
3627                                  */
3628
3629                                 u8 *local_buffer = yaffs_get_temp_buffer(dev);
3630
3631                                 yaffs_rd_data_obj(in, chunk, local_buffer);
3632                                 memcpy(&local_buffer[start], buffer, n_copy);
3633
3634                                 chunk_written =
3635                                     yaffs_wr_data_obj(in, chunk,
3636                                                       local_buffer,
3637                                                       n_writeback, 0);
3638
3639                                 yaffs_release_temp_buffer(dev, local_buffer);
3640                         }
3641                 } else {
3642                         /* A full chunk. Write directly from the buffer. */
3643
3644                         chunk_written =
3645                             yaffs_wr_data_obj(in, chunk, buffer,
3646                                               dev->data_bytes_per_chunk, 0);
3647
3648                         /* Since we've overwritten the cached data,
3649                          * we better invalidate it. */
3650                         yaffs_invalidate_chunk_cache(in, chunk);
3651                 }
3652
3653                 if (chunk_written >= 0) {
3654                         n -= n_copy;
3655                         offset += n_copy;
3656                         buffer += n_copy;
3657                         n_done += n_copy;
3658                 }
3659         }
3660
3661         /* Update file object */
3662
3663         if ((start_write + n_done) > in->variant.file_variant.file_size)
3664                 in->variant.file_variant.file_size = (start_write + n_done);
3665
3666         in->dirty = 1;
3667         return n_done;
3668 }
3669
3670 int yaffs_wr_file(struct yaffs_obj *in, const u8 *buffer, loff_t offset,
3671                   int n_bytes, int write_through)
3672 {
3673         yaffs2_handle_hole(in, offset);
3674         return yaffs_do_file_wr(in, buffer, offset, n_bytes, write_through);
3675 }
3676
3677 /* ---------------------- File resizing stuff ------------------ */
3678
3679 static void yaffs_prune_chunks(struct yaffs_obj *in, loff_t new_size)
3680 {
3681
3682         struct yaffs_dev *dev = in->my_dev;
3683         loff_t old_size = in->variant.file_variant.file_size;
3684         int i;
3685         int chunk_id;
3686         u32 dummy;
3687         int last_del;
3688         int start_del;
3689
3690         if (old_size > 0)
3691                 yaffs_addr_to_chunk(dev, old_size - 1, &last_del, &dummy);
3692         else
3693                 last_del = 0;
3694
3695         yaffs_addr_to_chunk(dev, new_size + dev->data_bytes_per_chunk - 1,
3696                                 &start_del, &dummy);
3697         last_del++;
3698         start_del++;
3699
3700         /* Delete backwards so that we don't end up with holes if
3701          * power is lost part-way through the operation.
3702          */
3703         for (i = last_del; i >= start_del; i--) {
3704                 /* NB this could be optimised somewhat,
3705                  * eg. could retrieve the tags and write them without
3706                  * using yaffs_chunk_del
3707                  */
3708
3709                 chunk_id = yaffs_find_del_file_chunk(in, i, NULL);
3710
3711                 if (chunk_id < 1)
3712                         continue;
3713
3714                 if (chunk_id <
3715                     (dev->internal_start_block * dev->param.chunks_per_block) ||
3716                     chunk_id >=
3717                     ((dev->internal_end_block + 1) *
3718                       dev->param.chunks_per_block)) {
3719                         yaffs_trace(YAFFS_TRACE_ALWAYS,
3720                                 "Found daft chunk_id %d for %d",
3721                                 chunk_id, i);
3722                 } else {
3723                         in->n_data_chunks--;
3724                         yaffs_chunk_del(dev, chunk_id, 1, __LINE__);
3725                 }
3726         }
3727 }
3728
3729 void yaffs_resize_file_down(struct yaffs_obj *obj, loff_t new_size)
3730 {
3731         int new_full;
3732         u32 new_partial;
3733         struct yaffs_dev *dev = obj->my_dev;
3734
3735         yaffs_addr_to_chunk(dev, new_size, &new_full, &new_partial);
3736
3737         yaffs_prune_chunks(obj, new_size);
3738
3739         if (new_partial != 0) {
3740                 int last_chunk = 1 + new_full;
3741                 u8 *local_buffer = yaffs_get_temp_buffer(dev);
3742
3743                 /* Rewrite the last chunk with its new size and zero pad */
3744                 yaffs_rd_data_obj(obj, last_chunk, local_buffer);
3745                 memset(local_buffer + new_partial, 0,
3746                        dev->data_bytes_per_chunk - new_partial);
3747
3748                 yaffs_wr_data_obj(obj, last_chunk, local_buffer,
3749                                   new_partial, 1);
3750
3751                 yaffs_release_temp_buffer(dev, local_buffer);
3752         }
3753
3754         obj->variant.file_variant.file_size = new_size;
3755
3756         yaffs_prune_tree(dev, &obj->variant.file_variant);
3757 }
3758
3759 int yaffs_resize_file(struct yaffs_obj *in, loff_t new_size)
3760 {
3761         struct yaffs_dev *dev = in->my_dev;
3762         loff_t old_size = in->variant.file_variant.file_size;
3763
3764         yaffs_flush_file_cache(in);
3765         yaffs_invalidate_whole_cache(in);
3766
3767         yaffs_check_gc(dev, 0);
3768
3769         if (in->variant_type != YAFFS_OBJECT_TYPE_FILE)
3770                 return YAFFS_FAIL;
3771
3772         if (new_size == old_size)
3773                 return YAFFS_OK;
3774
3775         if (new_size > old_size) {
3776                 yaffs2_handle_hole(in, new_size);
3777                 in->variant.file_variant.file_size = new_size;
3778         } else {
3779                 /* new_size < old_size */
3780                 yaffs_resize_file_down(in, new_size);
3781         }
3782
3783         /* Write a new object header to reflect the resize.
3784          * show we've shrunk the file, if need be
3785          * Do this only if the file is not in the deleted directories
3786          * and is not shadowed.
3787          */
3788         if (in->parent &&
3789             !in->is_shadowed &&
3790             in->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
3791             in->parent->obj_id != YAFFS_OBJECTID_DELETED)
3792                 yaffs_update_oh(in, NULL, 0, 0, 0, NULL);
3793
3794         return YAFFS_OK;
3795 }
3796
3797 int yaffs_flush_file(struct yaffs_obj *in, int update_time, int data_sync)
3798 {
3799         if (!in->dirty)
3800                 return YAFFS_OK;
3801
3802         yaffs_flush_file_cache(in);
3803
3804         if (data_sync)
3805                 return YAFFS_OK;
3806
3807         if (update_time)
3808                 yaffs_load_current_time(in, 0, 0);
3809
3810         return (yaffs_update_oh(in, NULL, 0, 0, 0, NULL) >= 0) ?
3811                                 YAFFS_OK : YAFFS_FAIL;
3812 }
3813
3814
3815 /* yaffs_del_file deletes the whole file data
3816  * and the inode associated with the file.
3817  * It does not delete the links associated with the file.
3818  */
3819 static int yaffs_unlink_file_if_needed(struct yaffs_obj *in)
3820 {
3821         int ret_val;
3822         int del_now = 0;
3823         struct yaffs_dev *dev = in->my_dev;
3824
3825         if (!in->my_inode)
3826                 del_now = 1;
3827
3828         if (del_now) {
3829                 ret_val =
3830                     yaffs_change_obj_name(in, in->my_dev->del_dir,
3831                                           _Y("deleted"), 0, 0);
3832                 yaffs_trace(YAFFS_TRACE_TRACING,
3833                         "yaffs: immediate deletion of file %d",
3834                         in->obj_id);
3835                 in->deleted = 1;
3836                 in->my_dev->n_deleted_files++;
3837                 if (dev->param.disable_soft_del || dev->param.is_yaffs2)
3838                         yaffs_resize_file(in, 0);
3839                 yaffs_soft_del_file(in);
3840         } else {
3841                 ret_val =
3842                     yaffs_change_obj_name(in, in->my_dev->unlinked_dir,
3843                                           _Y("unlinked"), 0, 0);
3844         }
3845         return ret_val;
3846 }
3847
3848 static int yaffs_del_file(struct yaffs_obj *in)
3849 {
3850         int ret_val = YAFFS_OK;
3851         int deleted;    /* Need to cache value on stack if in is freed */
3852         struct yaffs_dev *dev = in->my_dev;
3853
3854         if (dev->param.disable_soft_del || dev->param.is_yaffs2)
3855                 yaffs_resize_file(in, 0);
3856
3857         if (in->n_data_chunks > 0) {
3858                 /* Use soft deletion if there is data in the file.
3859                  * That won't be the case if it has been resized to zero.
3860                  */
3861                 if (!in->unlinked)
3862                         ret_val = yaffs_unlink_file_if_needed(in);
3863
3864                 deleted = in->deleted;
3865
3866                 if (ret_val == YAFFS_OK && in->unlinked && !in->deleted) {
3867                         in->deleted = 1;
3868                         deleted = 1;
3869                         in->my_dev->n_deleted_files++;
3870                         yaffs_soft_del_file(in);
3871                 }
3872                 return deleted ? YAFFS_OK : YAFFS_FAIL;
3873         } else {
3874                 /* The file has no data chunks so we toss it immediately */
3875                 yaffs_free_tnode(in->my_dev, in->variant.file_variant.top);
3876                 in->variant.file_variant.top = NULL;
3877                 yaffs_generic_obj_del(in);
3878
3879                 return YAFFS_OK;
3880         }
3881 }
3882
3883 int yaffs_is_non_empty_dir(struct yaffs_obj *obj)
3884 {
3885         return (obj &&
3886                 obj->variant_type == YAFFS_OBJECT_TYPE_DIRECTORY) &&
3887                 !(list_empty(&obj->variant.dir_variant.children));
3888 }
3889
3890 static int yaffs_del_dir(struct yaffs_obj *obj)
3891 {
3892         /* First check that the directory is empty. */
3893         if (yaffs_is_non_empty_dir(obj))
3894                 return YAFFS_FAIL;
3895
3896         return yaffs_generic_obj_del(obj);
3897 }
3898
3899 static int yaffs_del_symlink(struct yaffs_obj *in)
3900 {
3901         kfree(in->variant.symlink_variant.alias);
3902         in->variant.symlink_variant.alias = NULL;
3903
3904         return yaffs_generic_obj_del(in);
3905 }
3906
3907 static int yaffs_del_link(struct yaffs_obj *in)
3908 {
3909         /* remove this hardlink from the list associated with the equivalent
3910          * object
3911          */
3912         list_del_init(&in->hard_links);
3913         return yaffs_generic_obj_del(in);
3914 }
3915
3916 int yaffs_del_obj(struct yaffs_obj *obj)
3917 {
3918         int ret_val = -1;
3919
3920         switch (obj->variant_type) {
3921         case YAFFS_OBJECT_TYPE_FILE:
3922                 ret_val = yaffs_del_file(obj);
3923                 break;
3924         case YAFFS_OBJECT_TYPE_DIRECTORY:
3925                 if (!list_empty(&obj->variant.dir_variant.dirty)) {
3926                         yaffs_trace(YAFFS_TRACE_BACKGROUND,
3927                                 "Remove object %d from dirty directories",
3928                                 obj->obj_id);
3929                         list_del_init(&obj->variant.dir_variant.dirty);
3930                 }
3931                 return yaffs_del_dir(obj);
3932                 break;
3933         case YAFFS_OBJECT_TYPE_SYMLINK:
3934                 ret_val = yaffs_del_symlink(obj);
3935                 break;
3936         case YAFFS_OBJECT_TYPE_HARDLINK:
3937                 ret_val = yaffs_del_link(obj);
3938                 break;
3939         case YAFFS_OBJECT_TYPE_SPECIAL:
3940                 ret_val = yaffs_generic_obj_del(obj);
3941                 break;
3942         case YAFFS_OBJECT_TYPE_UNKNOWN:
3943                 ret_val = 0;
3944                 break;          /* should not happen. */
3945         }
3946         return ret_val;
3947 }
3948
3949 static int yaffs_unlink_worker(struct yaffs_obj *obj)
3950 {
3951         int del_now = 0;
3952
3953         if (!obj)
3954                 return YAFFS_FAIL;
3955
3956         if (!obj->my_inode)
3957                 del_now = 1;
3958
3959         yaffs_update_parent(obj->parent);
3960
3961         if (obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK) {
3962                 return yaffs_del_link(obj);
3963         } else if (!list_empty(&obj->hard_links)) {
3964                 /* Curve ball: We're unlinking an object that has a hardlink.
3965                  *
3966                  * This problem arises because we are not strictly following
3967                  * The Linux link/inode model.
3968                  *
3969                  * We can't really delete the object.
3970                  * Instead, we do the following:
3971                  * - Select a hardlink.
3972                  * - Unhook it from the hard links
3973                  * - Move it from its parent directory so that the rename works.
3974                  * - Rename the object to the hardlink's name.
3975                  * - Delete the hardlink
3976                  */
3977
3978                 struct yaffs_obj *hl;
3979                 struct yaffs_obj *parent;
3980                 int ret_val;
3981                 YCHAR name[YAFFS_MAX_NAME_LENGTH + 1];
3982
3983                 hl = list_entry(obj->hard_links.next, struct yaffs_obj,
3984                                 hard_links);
3985
3986                 yaffs_get_obj_name(hl, name, YAFFS_MAX_NAME_LENGTH + 1);
3987                 parent = hl->parent;
3988
3989                 list_del_init(&hl->hard_links);
3990
3991                 yaffs_add_obj_to_dir(obj->my_dev->unlinked_dir, hl);
3992
3993                 ret_val = yaffs_change_obj_name(obj, parent, name, 0, 0);
3994
3995                 if (ret_val == YAFFS_OK)
3996                         ret_val = yaffs_generic_obj_del(hl);
3997
3998                 return ret_val;
3999
4000         } else if (del_now) {
4001                 switch (obj->variant_type) {
4002                 case YAFFS_OBJECT_TYPE_FILE:
4003                         return yaffs_del_file(obj);
4004                         break;
4005                 case YAFFS_OBJECT_TYPE_DIRECTORY:
4006                         list_del_init(&obj->variant.dir_variant.dirty);
4007                         return yaffs_del_dir(obj);
4008                         break;
4009                 case YAFFS_OBJECT_TYPE_SYMLINK:
4010                         return yaffs_del_symlink(obj);
4011                         break;
4012                 case YAFFS_OBJECT_TYPE_SPECIAL:
4013                         return yaffs_generic_obj_del(obj);
4014                         break;
4015                 case YAFFS_OBJECT_TYPE_HARDLINK:
4016                 case YAFFS_OBJECT_TYPE_UNKNOWN:
4017                 default:
4018                         return YAFFS_FAIL;
4019                 }
4020         } else if (yaffs_is_non_empty_dir(obj)) {
4021                 return YAFFS_FAIL;
4022         } else {
4023                 return yaffs_change_obj_name(obj, obj->my_dev->unlinked_dir,
4024                                                 _Y("unlinked"), 0, 0);
4025         }
4026 }
4027
4028 static int yaffs_unlink_obj(struct yaffs_obj *obj)
4029 {
4030         if (obj && obj->unlink_allowed)
4031                 return yaffs_unlink_worker(obj);
4032
4033         return YAFFS_FAIL;
4034 }
4035
4036 int yaffs_unlinker(struct yaffs_obj *dir, const YCHAR *name)
4037 {
4038         struct yaffs_obj *obj;
4039
4040         obj = yaffs_find_by_name(dir, name);
4041         return yaffs_unlink_obj(obj);
4042 }
4043
4044 /* Note:
4045  * If old_name is NULL then we take old_dir as the object to be renamed.
4046  */
4047 int yaffs_rename_obj(struct yaffs_obj *old_dir, const YCHAR *old_name,
4048                      struct yaffs_obj *new_dir, const YCHAR *new_name)
4049 {
4050         struct yaffs_obj *obj = NULL;
4051         struct yaffs_obj *existing_target = NULL;
4052         int force = 0;
4053         int result;
4054         struct yaffs_dev *dev;
4055
4056         if (!old_dir || old_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
4057                 BUG();
4058                 return YAFFS_FAIL;
4059         }
4060         if (!new_dir || new_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
4061                 BUG();
4062                 return YAFFS_FAIL;
4063         }
4064
4065         dev = old_dir->my_dev;
4066
4067 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
4068         /* Special case for case insemsitive systems.
4069          * While look-up is case insensitive, the name isn't.
4070          * Therefore we might want to change x.txt to X.txt
4071          */
4072         if (old_dir == new_dir &&
4073                 old_name && new_name &&
4074                 strcmp(old_name, new_name) == 0)
4075                 force = 1;
4076 #endif
4077
4078         if (strnlen(new_name, YAFFS_MAX_NAME_LENGTH + 1) >
4079             YAFFS_MAX_NAME_LENGTH)
4080                 /* ENAMETOOLONG */
4081                 return YAFFS_FAIL;
4082
4083         if (old_name)
4084                 obj = yaffs_find_by_name(old_dir, old_name);
4085         else{
4086                 obj = old_dir;
4087                 old_dir = obj->parent;
4088         }
4089
4090         if (obj && obj->rename_allowed) {
4091                 /* Now handle an existing target, if there is one */
4092                 existing_target = yaffs_find_by_name(new_dir, new_name);
4093                 if (yaffs_is_non_empty_dir(existing_target)) {
4094                         return YAFFS_FAIL;      /* ENOTEMPTY */
4095                 } else if (existing_target && existing_target != obj) {
4096                         /* Nuke the target first, using shadowing,
4097                          * but only if it isn't the same object.
4098                          *
4099                          * Note we must disable gc here otherwise it can mess
4100                          * up the shadowing.
4101                          *
4102                          */
4103                         dev->gc_disable = 1;
4104                         yaffs_change_obj_name(obj, new_dir, new_name, force,
4105                                               existing_target->obj_id);
4106                         existing_target->is_shadowed = 1;
4107                         yaffs_unlink_obj(existing_target);
4108                         dev->gc_disable = 0;
4109                 }
4110
4111                 result = yaffs_change_obj_name(obj, new_dir, new_name, 1, 0);
4112
4113                 yaffs_update_parent(old_dir);
4114                 if (new_dir != old_dir)
4115                         yaffs_update_parent(new_dir);
4116
4117                 return result;
4118         }
4119         return YAFFS_FAIL;
4120 }
4121
4122 /*----------------------- Initialisation Scanning ---------------------- */
4123
4124 void yaffs_handle_shadowed_obj(struct yaffs_dev *dev, int obj_id,
4125                                int backward_scanning)
4126 {
4127         struct yaffs_obj *obj;
4128
4129         if (backward_scanning) {
4130                 /* Handle YAFFS2 case (backward scanning)
4131                  * If the shadowed object exists then ignore.
4132                  */
4133                 obj = yaffs_find_by_number(dev, obj_id);
4134                 if (obj)
4135                         return;
4136         }
4137
4138         /* Let's create it (if it does not exist) assuming it is a file so that
4139          * it can do shrinking etc.
4140          * We put it in unlinked dir to be cleaned up after the scanning
4141          */
4142         obj =
4143             yaffs_find_or_create_by_number(dev, obj_id, YAFFS_OBJECT_TYPE_FILE);
4144         if (!obj)
4145                 return;
4146         obj->is_shadowed = 1;
4147         yaffs_add_obj_to_dir(dev->unlinked_dir, obj);
4148         obj->variant.file_variant.shrink_size = 0;
4149         obj->valid = 1;         /* So that we don't read any other info. */
4150 }
4151
4152 void yaffs_link_fixup(struct yaffs_dev *dev, struct list_head *hard_list)
4153 {
4154         struct list_head *lh;
4155         struct list_head *save;
4156         struct yaffs_obj *hl;
4157         struct yaffs_obj *in;
4158
4159         list_for_each_safe(lh, save, hard_list) {
4160                 hl = list_entry(lh, struct yaffs_obj, hard_links);
4161                 in = yaffs_find_by_number(dev,
4162                                         hl->variant.hardlink_variant.equiv_id);
4163
4164                 if (in) {
4165                         /* Add the hardlink pointers */
4166                         hl->variant.hardlink_variant.equiv_obj = in;
4167                         list_add(&hl->hard_links, &in->hard_links);
4168                 } else {
4169                         /* Todo Need to report/handle this better.
4170                          * Got a problem... hardlink to a non-existant object
4171                          */
4172                         hl->variant.hardlink_variant.equiv_obj = NULL;
4173                         INIT_LIST_HEAD(&hl->hard_links);
4174                 }
4175         }
4176 }
4177
4178 static void yaffs_strip_deleted_objs(struct yaffs_dev *dev)
4179 {
4180         /*
4181          *  Sort out state of unlinked and deleted objects after scanning.
4182          */
4183         struct list_head *i;
4184         struct list_head *n;
4185         struct yaffs_obj *l;
4186
4187         if (dev->read_only)
4188                 return;
4189
4190         /* Soft delete all the unlinked files */
4191         list_for_each_safe(i, n,
4192                            &dev->unlinked_dir->variant.dir_variant.children) {
4193                 l = list_entry(i, struct yaffs_obj, siblings);
4194                 yaffs_del_obj(l);
4195         }
4196
4197         list_for_each_safe(i, n, &dev->del_dir->variant.dir_variant.children) {
4198                 l = list_entry(i, struct yaffs_obj, siblings);
4199                 yaffs_del_obj(l);
4200         }
4201 }
4202
4203 /*
4204  * This code iterates through all the objects making sure that they are rooted.
4205  * Any unrooted objects are re-rooted in lost+found.
4206  * An object needs to be in one of:
4207  * - Directly under deleted, unlinked
4208  * - Directly or indirectly under root.
4209  *
4210  * Note:
4211  *  This code assumes that we don't ever change the current relationships
4212  *  between directories:
4213  *   root_dir->parent == unlinked_dir->parent == del_dir->parent == NULL
4214  *   lost-n-found->parent == root_dir
4215  *
4216  * This fixes the problem where directories might have inadvertently been
4217  * deleted leaving the object "hanging" without being rooted in the
4218  * directory tree.
4219  */
4220
4221 static int yaffs_has_null_parent(struct yaffs_dev *dev, struct yaffs_obj *obj)
4222 {
4223         return (obj == dev->del_dir ||
4224                 obj == dev->unlinked_dir || obj == dev->root_dir);
4225 }
4226
4227 static void yaffs_fix_hanging_objs(struct yaffs_dev *dev)
4228 {
4229         struct yaffs_obj *obj;
4230         struct yaffs_obj *parent;
4231         int i;
4232         struct list_head *lh;
4233         struct list_head *n;
4234         int depth_limit;
4235         int hanging;
4236
4237         if (dev->read_only)
4238                 return;
4239
4240         /* Iterate through the objects in each hash entry,
4241          * looking at each object.
4242          * Make sure it is rooted.
4243          */
4244
4245         for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) {
4246                 list_for_each_safe(lh, n, &dev->obj_bucket[i].list) {
4247                         obj = list_entry(lh, struct yaffs_obj, hash_link);
4248                         parent = obj->parent;
4249
4250                         if (yaffs_has_null_parent(dev, obj)) {
4251                                 /* These directories are not hanging */
4252                                 hanging = 0;
4253                         } else if (!parent ||
4254                                    parent->variant_type !=
4255                                    YAFFS_OBJECT_TYPE_DIRECTORY) {
4256                                 hanging = 1;
4257                         } else if (yaffs_has_null_parent(dev, parent)) {
4258                                 hanging = 0;
4259                         } else {
4260                                 /*
4261                                  * Need to follow the parent chain to
4262                                  * see if it is hanging.
4263                                  */
4264                                 hanging = 0;
4265                                 depth_limit = 100;
4266
4267                                 while (parent != dev->root_dir &&
4268                                        parent->parent &&
4269                                        parent->parent->variant_type ==
4270                                        YAFFS_OBJECT_TYPE_DIRECTORY &&
4271                                        depth_limit > 0) {
4272                                         parent = parent->parent;
4273                                         depth_limit--;
4274                                 }
4275                                 if (parent != dev->root_dir)
4276                                         hanging = 1;
4277                         }
4278                         if (hanging) {
4279                                 yaffs_trace(YAFFS_TRACE_SCAN,
4280                                         "Hanging object %d moved to lost and found",
4281                                         obj->obj_id);
4282                                 yaffs_add_obj_to_dir(dev->lost_n_found, obj);
4283                         }
4284                 }
4285         }
4286 }
4287
4288 /*
4289  * Delete directory contents for cleaning up lost and found.
4290  */
4291 static void yaffs_del_dir_contents(struct yaffs_obj *dir)
4292 {
4293         struct yaffs_obj *obj;
4294         struct list_head *lh;
4295         struct list_head *n;
4296
4297         if (dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY)
4298                 BUG();
4299
4300         list_for_each_safe(lh, n, &dir->variant.dir_variant.children) {
4301                 obj = list_entry(lh, struct yaffs_obj, siblings);
4302                 if (obj->variant_type == YAFFS_OBJECT_TYPE_DIRECTORY)
4303                         yaffs_del_dir_contents(obj);
4304                 yaffs_trace(YAFFS_TRACE_SCAN,
4305                         "Deleting lost_found object %d",
4306                         obj->obj_id);
4307                 yaffs_unlink_obj(obj);
4308         }
4309 }
4310
4311 static void yaffs_empty_l_n_f(struct yaffs_dev *dev)
4312 {
4313         yaffs_del_dir_contents(dev->lost_n_found);
4314 }
4315
4316
4317 struct yaffs_obj *yaffs_find_by_name(struct yaffs_obj *directory,
4318                                      const YCHAR *name)
4319 {
4320         int sum;
4321         struct list_head *i;
4322         YCHAR buffer[YAFFS_MAX_NAME_LENGTH + 1];
4323         struct yaffs_obj *l;
4324
4325         if (!name)
4326                 return NULL;
4327
4328         if (!directory) {
4329                 yaffs_trace(YAFFS_TRACE_ALWAYS,
4330                         "tragedy: yaffs_find_by_name: null pointer directory"
4331                         );
4332                 BUG();
4333                 return NULL;
4334         }
4335         if (directory->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
4336                 yaffs_trace(YAFFS_TRACE_ALWAYS,
4337                         "tragedy: yaffs_find_by_name: non-directory"
4338                         );
4339                 BUG();
4340         }
4341
4342         sum = yaffs_calc_name_sum(name);
4343
4344         list_for_each(i, &directory->variant.dir_variant.children) {
4345                 l = list_entry(i, struct yaffs_obj, siblings);
4346
4347                 if (l->parent != directory)
4348                         BUG();
4349
4350                 yaffs_check_obj_details_loaded(l);
4351
4352                 /* Special case for lost-n-found */
4353                 if (l->obj_id == YAFFS_OBJECTID_LOSTNFOUND) {
4354                         if (!strcmp(name, YAFFS_LOSTNFOUND_NAME))
4355                                 return l;
4356                 } else if (l->sum == sum || l->hdr_chunk <= 0) {
4357                         /* LostnFound chunk called Objxxx
4358                          * Do a real check
4359                          */
4360                         yaffs_get_obj_name(l, buffer,
4361                                 YAFFS_MAX_NAME_LENGTH + 1);
4362                         if (!strncmp(name, buffer, YAFFS_MAX_NAME_LENGTH))
4363                                 return l;
4364                 }
4365         }
4366         return NULL;
4367 }
4368
4369 /* GetEquivalentObject dereferences any hard links to get to the
4370  * actual object.
4371  */
4372
4373 struct yaffs_obj *yaffs_get_equivalent_obj(struct yaffs_obj *obj)
4374 {
4375         if (obj && obj->variant_type == YAFFS_OBJECT_TYPE_HARDLINK) {
4376                 obj = obj->variant.hardlink_variant.equiv_obj;
4377                 yaffs_check_obj_details_loaded(obj);
4378         }
4379         return obj;
4380 }
4381
4382 /*
4383  *  A note or two on object names.
4384  *  * If the object name is missing, we then make one up in the form objnnn
4385  *
4386  *  * ASCII names are stored in the object header's name field from byte zero
4387  *  * Unicode names are historically stored starting from byte zero.
4388  *
4389  * Then there are automatic Unicode names...
4390  * The purpose of these is to save names in a way that can be read as
4391  * ASCII or Unicode names as appropriate, thus allowing a Unicode and ASCII
4392  * system to share files.
4393  *
4394  * These automatic unicode are stored slightly differently...
4395  *  - If the name can fit in the ASCII character space then they are saved as
4396  *    ascii names as per above.
4397  *  - If the name needs Unicode then the name is saved in Unicode
4398  *    starting at oh->name[1].
4399
4400  */
4401 static void yaffs_fix_null_name(struct yaffs_obj *obj, YCHAR *name,
4402                                 int buffer_size)
4403 {
4404         /* Create an object name if we could not find one. */
4405         if (strnlen(name, YAFFS_MAX_NAME_LENGTH) == 0) {
4406                 YCHAR local_name[20];
4407                 YCHAR num_string[20];
4408                 YCHAR *x = &num_string[19];
4409                 unsigned v = obj->obj_id;
4410                 num_string[19] = 0;
4411                 while (v > 0) {
4412                         x--;
4413                         *x = '0' + (v % 10);
4414                         v /= 10;
4415                 }
4416                 /* make up a name */
4417                 strcpy(local_name, YAFFS_LOSTNFOUND_PREFIX);
4418                 strcat(local_name, x);
4419                 strncpy(name, local_name, buffer_size - 1);
4420         }
4421 }
4422
4423 int yaffs_get_obj_name(struct yaffs_obj *obj, YCHAR *name, int buffer_size)
4424 {
4425         memset(name, 0, buffer_size * sizeof(YCHAR));
4426         yaffs_check_obj_details_loaded(obj);
4427         if (obj->obj_id == YAFFS_OBJECTID_LOSTNFOUND) {
4428                 strncpy(name, YAFFS_LOSTNFOUND_NAME, buffer_size - 1);
4429         } else if (obj->short_name[0]) {
4430                 strcpy(name, obj->short_name);
4431         } else if (obj->hdr_chunk > 0) {
4432                 int result;
4433                 u8 *buffer = yaffs_get_temp_buffer(obj->my_dev);
4434
4435                 struct yaffs_obj_hdr *oh = (struct yaffs_obj_hdr *)buffer;
4436
4437                 memset(buffer, 0, obj->my_dev->data_bytes_per_chunk);
4438
4439                 if (obj->hdr_chunk > 0) {
4440                         result = yaffs_rd_chunk_tags_nand(obj->my_dev,
4441                                                           obj->hdr_chunk,
4442                                                           buffer, NULL);
4443                 }
4444                 yaffs_load_name_from_oh(obj->my_dev, name, oh->name,
4445                                         buffer_size);
4446
4447                 yaffs_release_temp_buffer(obj->my_dev, buffer);
4448         }
4449
4450         yaffs_fix_null_name(obj, name, buffer_size);
4451
4452         return strnlen(name, YAFFS_MAX_NAME_LENGTH);
4453 }
4454
4455 loff_t yaffs_get_obj_length(struct yaffs_obj *obj)
4456 {
4457         /* Dereference any hard linking */
4458         obj = yaffs_get_equivalent_obj(obj);
4459
4460         if (obj->variant_type == YAFFS_OBJECT_TYPE_FILE)
4461                 return obj->variant.file_variant.file_size;
4462         if (obj->variant_type == YAFFS_OBJECT_TYPE_SYMLINK) {
4463                 if (!obj->variant.symlink_variant.alias)
4464                         return 0;
4465                 return strnlen(obj->variant.symlink_variant.alias,
4466                                      YAFFS_MAX_ALIAS_LENGTH);
4467         } else {
4468                 /* Only a directory should drop through to here */
4469                 return obj->my_dev->data_bytes_per_chunk;
4470         }
4471 }
4472
4473 int yaffs_get_obj_link_count(struct yaffs_obj *obj)
4474 {
4475         int count = 0;
4476         struct list_head *i;
4477
4478         if (!obj->unlinked)
4479                 count++;        /* the object itself */
4480
4481         list_for_each(i, &obj->hard_links)
4482             count++;            /* add the hard links; */
4483
4484         return count;
4485 }
4486
4487 int yaffs_get_obj_inode(struct yaffs_obj *obj)
4488 {
4489         obj = yaffs_get_equivalent_obj(obj);
4490
4491         return obj->obj_id;
4492 }
4493
4494 unsigned yaffs_get_obj_type(struct yaffs_obj *obj)
4495 {
4496         obj = yaffs_get_equivalent_obj(obj);
4497
4498         switch (obj->variant_type) {
4499         case YAFFS_OBJECT_TYPE_FILE:
4500                 return DT_REG;
4501                 break;
4502         case YAFFS_OBJECT_TYPE_DIRECTORY:
4503                 return DT_DIR;
4504                 break;
4505         case YAFFS_OBJECT_TYPE_SYMLINK:
4506                 return DT_LNK;
4507                 break;
4508         case YAFFS_OBJECT_TYPE_HARDLINK:
4509                 return DT_REG;
4510                 break;
4511         case YAFFS_OBJECT_TYPE_SPECIAL:
4512                 if (S_ISFIFO(obj->yst_mode))
4513                         return DT_FIFO;
4514                 if (S_ISCHR(obj->yst_mode))
4515                         return DT_CHR;
4516                 if (S_ISBLK(obj->yst_mode))
4517                         return DT_BLK;
4518                 if (S_ISSOCK(obj->yst_mode))
4519                         return DT_SOCK;
4520                 return DT_REG;
4521                 break;
4522         default:
4523                 return DT_REG;
4524                 break;
4525         }
4526 }
4527
4528 YCHAR *yaffs_get_symlink_alias(struct yaffs_obj *obj)
4529 {
4530         obj = yaffs_get_equivalent_obj(obj);
4531         if (obj->variant_type == YAFFS_OBJECT_TYPE_SYMLINK)
4532                 return yaffs_clone_str(obj->variant.symlink_variant.alias);
4533         else
4534                 return yaffs_clone_str(_Y(""));
4535 }
4536
4537 /*--------------------------- Initialisation code -------------------------- */
4538
4539 static int yaffs_check_dev_fns(const struct yaffs_dev *dev)
4540 {
4541         /* Common functions, gotta have */
4542         if (!dev->param.erase_fn || !dev->param.initialise_flash_fn)
4543                 return 0;
4544
4545         /* Can use the "with tags" style interface for yaffs1 or yaffs2 */
4546         if (dev->param.write_chunk_tags_fn &&
4547             dev->param.read_chunk_tags_fn &&
4548             !dev->param.write_chunk_fn &&
4549             !dev->param.read_chunk_fn &&
4550             dev->param.bad_block_fn && dev->param.query_block_fn)
4551                 return 1;
4552
4553         /* Can use the "spare" style interface for yaffs1 */
4554         if (!dev->param.is_yaffs2 &&
4555             !dev->param.write_chunk_tags_fn &&
4556             !dev->param.read_chunk_tags_fn &&
4557             dev->param.write_chunk_fn &&
4558             dev->param.read_chunk_fn &&
4559             !dev->param.bad_block_fn && !dev->param.query_block_fn)
4560                 return 1;
4561
4562         return 0;               /* bad */
4563 }
4564
4565 static int yaffs_create_initial_dir(struct yaffs_dev *dev)
4566 {
4567         /* Initialise the unlinked, deleted, root and lost+found directories */
4568         dev->lost_n_found = dev->root_dir = NULL;
4569         dev->unlinked_dir = dev->del_dir = NULL;
4570         dev->unlinked_dir =
4571             yaffs_create_fake_dir(dev, YAFFS_OBJECTID_UNLINKED, S_IFDIR);
4572         dev->del_dir =
4573             yaffs_create_fake_dir(dev, YAFFS_OBJECTID_DELETED, S_IFDIR);
4574         dev->root_dir =
4575             yaffs_create_fake_dir(dev, YAFFS_OBJECTID_ROOT,
4576                                   YAFFS_ROOT_MODE | S_IFDIR);
4577         dev->lost_n_found =
4578             yaffs_create_fake_dir(dev, YAFFS_OBJECTID_LOSTNFOUND,
4579                                   YAFFS_LOSTNFOUND_MODE | S_IFDIR);
4580
4581         if (dev->lost_n_found && dev->root_dir && dev->unlinked_dir
4582             && dev->del_dir) {
4583                 yaffs_add_obj_to_dir(dev->root_dir, dev->lost_n_found);
4584                 return YAFFS_OK;
4585         }
4586         return YAFFS_FAIL;
4587 }
4588
4589 int yaffs_guts_initialise(struct yaffs_dev *dev)
4590 {
4591         int init_failed = 0;
4592         unsigned x;
4593         int bits;
4594
4595         yaffs_trace(YAFFS_TRACE_TRACING, "yaffs: yaffs_guts_initialise()");
4596
4597         /* Check stuff that must be set */
4598
4599         if (!dev) {
4600                 yaffs_trace(YAFFS_TRACE_ALWAYS,
4601                         "yaffs: Need a device"
4602                         );
4603                 return YAFFS_FAIL;
4604         }
4605
4606         if (dev->is_mounted) {
4607                 yaffs_trace(YAFFS_TRACE_ALWAYS, "device already mounted");
4608                 return YAFFS_FAIL;
4609         }
4610
4611         dev->internal_start_block = dev->param.start_block;
4612         dev->internal_end_block = dev->param.end_block;
4613         dev->block_offset = 0;
4614         dev->chunk_offset = 0;
4615         dev->n_free_chunks = 0;
4616
4617         dev->gc_block = 0;
4618
4619         if (dev->param.start_block == 0) {
4620                 dev->internal_start_block = dev->param.start_block + 1;
4621                 dev->internal_end_block = dev->param.end_block + 1;
4622                 dev->block_offset = 1;
4623                 dev->chunk_offset = dev->param.chunks_per_block;
4624         }
4625
4626         /* Check geometry parameters. */
4627
4628         if ((!dev->param.inband_tags && dev->param.is_yaffs2 &&
4629                 dev->param.total_bytes_per_chunk < 1024) ||
4630                 (!dev->param.is_yaffs2 &&
4631                         dev->param.total_bytes_per_chunk < 512) ||
4632                 (dev->param.inband_tags && !dev->param.is_yaffs2) ||
4633                  dev->param.chunks_per_block < 2 ||
4634                  dev->param.n_reserved_blocks < 2 ||
4635                 dev->internal_start_block <= 0 ||
4636                 dev->internal_end_block <= 0 ||
4637                 dev->internal_end_block <=
4638                 (dev->internal_start_block + dev->param.n_reserved_blocks + 2)
4639                 ) {
4640                 /* otherwise it is too small */
4641                 yaffs_trace(YAFFS_TRACE_ALWAYS,
4642                         "NAND geometry problems: chunk size %d, type is yaffs%s, inband_tags %d ",
4643                         dev->param.total_bytes_per_chunk,
4644                         dev->param.is_yaffs2 ? "2" : "",
4645                         dev->param.inband_tags);
4646                 return YAFFS_FAIL;
4647         }
4648
4649         if (yaffs_init_nand(dev) != YAFFS_OK) {
4650                 yaffs_trace(YAFFS_TRACE_ALWAYS, "InitialiseNAND failed");
4651                 return YAFFS_FAIL;
4652         }
4653
4654         /* Sort out space for inband tags, if required */
4655         if (dev->param.inband_tags)
4656                 dev->data_bytes_per_chunk =
4657                     dev->param.total_bytes_per_chunk -
4658                     sizeof(struct yaffs_packed_tags2_tags_only);
4659         else
4660                 dev->data_bytes_per_chunk = dev->param.total_bytes_per_chunk;
4661
4662         /* Got the right mix of functions? */
4663         if (!yaffs_check_dev_fns(dev)) {
4664                 /* Function missing */
4665                 yaffs_trace(YAFFS_TRACE_ALWAYS,
4666                         "device function(s) missing or wrong");
4667
4668                 return YAFFS_FAIL;
4669         }
4670
4671         /* Finished with most checks. Further checks happen later on too. */
4672
4673         dev->is_mounted = 1;
4674
4675         /* OK now calculate a few things for the device */
4676
4677         /*
4678          *  Calculate all the chunk size manipulation numbers:
4679          */
4680         x = dev->data_bytes_per_chunk;
4681         /* We always use dev->chunk_shift and dev->chunk_div */
4682         dev->chunk_shift = calc_shifts(x);
4683         x >>= dev->chunk_shift;
4684         dev->chunk_div = x;
4685         /* We only use chunk mask if chunk_div is 1 */
4686         dev->chunk_mask = (1 << dev->chunk_shift) - 1;
4687
4688         /*
4689          * Calculate chunk_grp_bits.
4690          * We need to find the next power of 2 > than internal_end_block
4691          */
4692
4693         x = dev->param.chunks_per_block * (dev->internal_end_block + 1);
4694
4695         bits = calc_shifts_ceiling(x);
4696
4697         /* Set up tnode width if wide tnodes are enabled. */
4698         if (!dev->param.wide_tnodes_disabled) {
4699                 /* bits must be even so that we end up with 32-bit words */
4700                 if (bits & 1)
4701                         bits++;
4702                 if (bits < 16)
4703                         dev->tnode_width = 16;
4704                 else
4705                         dev->tnode_width = bits;
4706         } else {
4707                 dev->tnode_width = 16;
4708         }
4709
4710         dev->tnode_mask = (1 << dev->tnode_width) - 1;
4711
4712         /* Level0 Tnodes are 16 bits or wider (if wide tnodes are enabled),
4713          * so if the bitwidth of the
4714          * chunk range we're using is greater than 16 we need
4715          * to figure out chunk shift and chunk_grp_size
4716          */
4717
4718         if (bits <= dev->tnode_width)
4719                 dev->chunk_grp_bits = 0;
4720         else
4721                 dev->chunk_grp_bits = bits - dev->tnode_width;
4722
4723         dev->tnode_size = (dev->tnode_width * YAFFS_NTNODES_LEVEL0) / 8;
4724         if (dev->tnode_size < sizeof(struct yaffs_tnode))
4725                 dev->tnode_size = sizeof(struct yaffs_tnode);
4726
4727         dev->chunk_grp_size = 1 << dev->chunk_grp_bits;
4728
4729         if (dev->param.chunks_per_block < dev->chunk_grp_size) {
4730                 /* We have a problem because the soft delete won't work if
4731                  * the chunk group size > chunks per block.
4732                  * This can be remedied by using larger "virtual blocks".
4733                  */
4734                 yaffs_trace(YAFFS_TRACE_ALWAYS, "chunk group too large");
4735
4736                 return YAFFS_FAIL;
4737         }
4738
4739         /* Finished verifying the device, continue with initialisation */
4740
4741         /* More device initialisation */
4742         dev->all_gcs = 0;
4743         dev->passive_gc_count = 0;
4744         dev->oldest_dirty_gc_count = 0;
4745         dev->bg_gcs = 0;
4746         dev->gc_block_finder = 0;
4747         dev->buffered_block = -1;
4748         dev->doing_buffered_block_rewrite = 0;
4749         dev->n_deleted_files = 0;
4750         dev->n_bg_deletions = 0;
4751         dev->n_unlinked_files = 0;
4752         dev->n_ecc_fixed = 0;
4753         dev->n_ecc_unfixed = 0;
4754         dev->n_tags_ecc_fixed = 0;
4755         dev->n_tags_ecc_unfixed = 0;
4756         dev->n_erase_failures = 0;
4757         dev->n_erased_blocks = 0;
4758         dev->gc_disable = 0;
4759         dev->has_pending_prioritised_gc = 1;
4760                 /* Assume the worst for now, will get fixed on first GC */
4761         INIT_LIST_HEAD(&dev->dirty_dirs);
4762         dev->oldest_dirty_seq = 0;
4763         dev->oldest_dirty_block = 0;
4764
4765         /* Initialise temporary buffers and caches. */
4766         if (!yaffs_init_tmp_buffers(dev))
4767                 init_failed = 1;
4768
4769         dev->cache = NULL;
4770         dev->gc_cleanup_list = NULL;
4771
4772         if (!init_failed && dev->param.n_caches > 0) {
4773                 int i;
4774                 void *buf;
4775                 int cache_bytes =
4776                     dev->param.n_caches * sizeof(struct yaffs_cache);
4777
4778                 if (dev->param.n_caches > YAFFS_MAX_SHORT_OP_CACHES)
4779                         dev->param.n_caches = YAFFS_MAX_SHORT_OP_CACHES;
4780
4781                 dev->cache = kmalloc(cache_bytes, GFP_NOFS);
4782
4783                 buf = (u8 *) dev->cache;
4784
4785                 if (dev->cache)
4786                         memset(dev->cache, 0, cache_bytes);
4787
4788                 for (i = 0; i < dev->param.n_caches && buf; i++) {
4789                         dev->cache[i].object = NULL;
4790                         dev->cache[i].last_use = 0;
4791                         dev->cache[i].dirty = 0;
4792                         dev->cache[i].data = buf =
4793                             kmalloc(dev->param.total_bytes_per_chunk, GFP_NOFS);
4794                 }
4795                 if (!buf)
4796                         init_failed = 1;
4797
4798                 dev->cache_last_use = 0;
4799         }
4800
4801         dev->cache_hits = 0;
4802
4803         if (!init_failed) {
4804                 dev->gc_cleanup_list =
4805                     kmalloc(dev->param.chunks_per_block * sizeof(u32),
4806                                         GFP_NOFS);
4807                 if (!dev->gc_cleanup_list)
4808                         init_failed = 1;
4809         }
4810
4811         if (dev->param.is_yaffs2)
4812                 dev->param.use_header_file_size = 1;
4813
4814         if (!init_failed && !yaffs_init_blocks(dev))
4815                 init_failed = 1;
4816
4817         yaffs_init_tnodes_and_objs(dev);
4818
4819         if (!init_failed && !yaffs_create_initial_dir(dev))
4820                 init_failed = 1;
4821
4822         if (!init_failed && dev->param.is_yaffs2 &&
4823                 !dev->param.disable_summary &&
4824                 !yaffs_summary_init(dev))
4825                 init_failed = 1;
4826
4827         if (!init_failed) {
4828                 /* Now scan the flash. */
4829                 if (dev->param.is_yaffs2) {
4830                         if (yaffs2_checkpt_restore(dev)) {
4831                                 yaffs_check_obj_details_loaded(dev->root_dir);
4832                                 yaffs_trace(YAFFS_TRACE_CHECKPOINT |
4833                                         YAFFS_TRACE_MOUNT,
4834                                         "yaffs: restored from checkpoint"
4835                                         );
4836                         } else {
4837
4838                                 /* Clean up the mess caused by an aborted
4839                                  * checkpoint load then scan backwards.
4840                                  */
4841                                 yaffs_deinit_blocks(dev);
4842
4843                                 yaffs_deinit_tnodes_and_objs(dev);
4844
4845                                 dev->n_erased_blocks = 0;
4846                                 dev->n_free_chunks = 0;
4847                                 dev->alloc_block = -1;
4848                                 dev->alloc_page = -1;
4849                                 dev->n_deleted_files = 0;
4850                                 dev->n_unlinked_files = 0;
4851                                 dev->n_bg_deletions = 0;
4852
4853                                 if (!init_failed && !yaffs_init_blocks(dev))
4854                                         init_failed = 1;
4855
4856                                 yaffs_init_tnodes_and_objs(dev);
4857
4858                                 if (!init_failed
4859                                     && !yaffs_create_initial_dir(dev))
4860                                         init_failed = 1;
4861
4862                                 if (!init_failed && !yaffs2_scan_backwards(dev))
4863                                         init_failed = 1;
4864                         }
4865                 } else if (!yaffs1_scan(dev)) {
4866                         init_failed = 1;
4867                 }
4868
4869                 yaffs_strip_deleted_objs(dev);
4870                 yaffs_fix_hanging_objs(dev);
4871                 if (dev->param.empty_lost_n_found)
4872                         yaffs_empty_l_n_f(dev);
4873         }
4874
4875         if (init_failed) {
4876                 /* Clean up the mess */
4877                 yaffs_trace(YAFFS_TRACE_TRACING,
4878                   "yaffs: yaffs_guts_initialise() aborted.");
4879
4880                 yaffs_deinitialise(dev);
4881                 return YAFFS_FAIL;
4882         }
4883
4884         /* Zero out stats */
4885         dev->n_page_reads = 0;
4886         dev->n_page_writes = 0;
4887         dev->n_erasures = 0;
4888         dev->n_gc_copies = 0;
4889         dev->n_retried_writes = 0;
4890
4891         dev->n_retired_blocks = 0;
4892
4893         yaffs_verify_free_chunks(dev);
4894         yaffs_verify_blocks(dev);
4895
4896         /* Clean up any aborted checkpoint data */
4897         if (!dev->is_checkpointed && dev->blocks_in_checkpt > 0)
4898                 yaffs2_checkpt_invalidate(dev);
4899
4900         yaffs_trace(YAFFS_TRACE_TRACING,
4901           "yaffs: yaffs_guts_initialise() done.");
4902         return YAFFS_OK;
4903 }
4904
4905 void yaffs_deinitialise(struct yaffs_dev *dev)
4906 {
4907         if (dev->is_mounted) {
4908                 int i;
4909
4910                 yaffs_deinit_blocks(dev);
4911                 yaffs_deinit_tnodes_and_objs(dev);
4912                 yaffs_summary_deinit(dev);
4913
4914                 if (dev->param.n_caches > 0 && dev->cache) {
4915
4916                         for (i = 0; i < dev->param.n_caches; i++) {
4917                                 kfree(dev->cache[i].data);
4918                                 dev->cache[i].data = NULL;
4919                         }
4920
4921                         kfree(dev->cache);
4922                         dev->cache = NULL;
4923                 }
4924
4925                 kfree(dev->gc_cleanup_list);
4926
4927                 for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
4928                         kfree(dev->temp_buffer[i].buffer);
4929
4930                 dev->is_mounted = 0;
4931
4932                 if (dev->param.deinitialise_flash_fn)
4933                         dev->param.deinitialise_flash_fn(dev);
4934         }
4935 }
4936
4937 int yaffs_count_free_chunks(struct yaffs_dev *dev)
4938 {
4939         int n_free = 0;
4940         int b;
4941         struct yaffs_block_info *blk;
4942
4943         blk = dev->block_info;
4944         for (b = dev->internal_start_block; b <= dev->internal_end_block; b++) {
4945                 switch (blk->block_state) {
4946                 case YAFFS_BLOCK_STATE_EMPTY:
4947                 case YAFFS_BLOCK_STATE_ALLOCATING:
4948                 case YAFFS_BLOCK_STATE_COLLECTING:
4949                 case YAFFS_BLOCK_STATE_FULL:
4950                         n_free +=
4951                             (dev->param.chunks_per_block - blk->pages_in_use +
4952                              blk->soft_del_pages);
4953                         break;
4954                 default:
4955                         break;
4956                 }
4957                 blk++;
4958         }
4959         return n_free;
4960 }
4961
4962 int yaffs_get_n_free_chunks(struct yaffs_dev *dev)
4963 {
4964         /* This is what we report to the outside world */
4965         int n_free;
4966         int n_dirty_caches;
4967         int blocks_for_checkpt;
4968         int i;
4969
4970         n_free = dev->n_free_chunks;
4971         n_free += dev->n_deleted_files;
4972
4973         /* Now count and subtract the number of dirty chunks in the cache. */
4974
4975         for (n_dirty_caches = 0, i = 0; i < dev->param.n_caches; i++) {
4976                 if (dev->cache[i].dirty)
4977                         n_dirty_caches++;
4978         }
4979
4980         n_free -= n_dirty_caches;
4981
4982         n_free -=
4983             ((dev->param.n_reserved_blocks + 1) * dev->param.chunks_per_block);
4984
4985         /* Now figure checkpoint space and report that... */
4986         blocks_for_checkpt = yaffs_calc_checkpt_blocks_required(dev);
4987
4988         n_free -= (blocks_for_checkpt * dev->param.chunks_per_block);
4989
4990         if (n_free < 0)
4991                 n_free = 0;
4992
4993         return n_free;
4994 }
4995
4996
4997 int yaffs_format_dev(struct yaffs_dev *dev)
4998 {
4999         int i;
5000         enum yaffs_block_state state;
5001         u32 dummy;
5002
5003         if(dev->is_mounted)
5004                 return YAFFS_FAIL;
5005
5006         /*
5007         * The runtime variables might not have been set up,
5008         * so set up what we need.
5009         */
5010         dev->internal_start_block = dev->param.start_block;
5011         dev->internal_end_block = dev->param.end_block;
5012         dev->block_offset = 0;
5013         dev->chunk_offset = 0;
5014
5015         if (dev->param.start_block == 0) {
5016                 dev->internal_start_block = dev->param.start_block + 1;
5017                 dev->internal_end_block = dev->param.end_block + 1;
5018                 dev->block_offset = 1;
5019                 dev->chunk_offset = dev->param.chunks_per_block;
5020         }
5021
5022         for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) {
5023                 yaffs_query_init_block_state(dev, i, &state, &dummy);
5024                 if (state != YAFFS_BLOCK_STATE_DEAD)
5025                         yaffs_erase_block(dev, i);
5026         }
5027
5028         return YAFFS_OK;
5029 }
5030
5031
5032 /*
5033  * Marshalling functions to get loff_t file sizes into and out of
5034  * object headers.
5035  */
5036 void yaffs_oh_size_load(struct yaffs_obj_hdr *oh, loff_t fsize)
5037 {
5038         oh->file_size_low = (fsize & 0xFFFFFFFF);
5039         oh->file_size_high = ((fsize >> 32) & 0xFFFFFFFF);
5040 }
5041
5042 loff_t yaffs_oh_to_size(struct yaffs_obj_hdr *oh)
5043 {
5044         loff_t retval;
5045
5046         if (sizeof(loff_t) >= 8 && ~(oh->file_size_high))
5047                 retval = (((loff_t) oh->file_size_high) << 32) |
5048                         (((loff_t) oh->file_size_low) & 0xFFFFFFFF);
5049         else
5050                 retval = (loff_t) oh->file_size_low;
5051
5052         return retval;
5053 }