yaffs_guts.c

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