yaffs_guts.c

   1 /*
   2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2007 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 const char *yaffs_guts_c_version =
  15     "$Id: yaffs_guts.c,v 1.69 2009-01-04 21:44:23 charles Exp $";
  16
  17 #include "yportenv.h"
  18
  19 #include "yaffsinterface.h"
  20 #include "yaffs_guts.h"
  21 #include "yaffs_tagsvalidity.h"
  22 #include "yaffs_getblockinfo.h"
  23
  24 #include "yaffs_tagscompat.h"
  25 #ifndef  CONFIG_YAFFS_USE_OWN_SORT
  26 #include "yaffs_qsort.h"
  27 #endif
  28 #include "yaffs_nand.h"
  29
  30 #include "yaffs_checkptrw.h"
  31
  32 #include "yaffs_nand.h"
  33 #include "yaffs_packedtags2.h"
  34
  35
  36 #ifdef CONFIG_YAFFS_WINCE
  37 void yfsd_LockYAFFS(BOOL fsLockOnly);
  38 void yfsd_UnlockYAFFS(BOOL fsLockOnly);
  39 #endif
  40
  41 #define YAFFS_PASSIVE_GC_CHUNKS 2
  42
  43 #include "yaffs_ecc.h"
  44
  45
  46 /* Robustification (if it ever comes about...) */
  47 static void yaffs_RetireBlock(yaffs_Device * dev, int blockInNAND);
  48 static void yaffs_HandleWriteChunkError(yaffs_Device * dev, int chunkInNAND, int erasedOk);
  49 static void yaffs_HandleWriteChunkOk(yaffs_Device * dev, int chunkInNAND,
  50                                      const __u8 * data,
  51                                      const yaffs_ExtendedTags * tags);
  52 static void yaffs_HandleUpdateChunk(yaffs_Device * dev, int chunkInNAND,
  53                                     const yaffs_ExtendedTags * tags);
  54
  55 /* Other local prototypes */
  56 static int yaffs_UnlinkObject( yaffs_Object *obj);
  57 static int yaffs_ObjectHasCachedWriteData(yaffs_Object *obj);
  58
  59 static void yaffs_HardlinkFixup(yaffs_Device *dev, yaffs_Object *hardList);
  60
  61 static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device * dev,
  62                                              const __u8 * buffer,
  63                                              yaffs_ExtendedTags * tags,
  64                                              int useReserve);
  65 static int yaffs_PutChunkIntoFile(yaffs_Object * in, int chunkInInode,
  66                                   int chunkInNAND, int inScan);
  67
  68 static yaffs_Object *yaffs_CreateNewObject(yaffs_Device * dev, int number,
  69                                            yaffs_ObjectType type);
  70 static void yaffs_AddObjectToDirectory(yaffs_Object * directory,
  71                                        yaffs_Object * obj);
  72 static int yaffs_UpdateObjectHeader(yaffs_Object * in, const YCHAR * name,
  73                                     int force, int isShrink, int shadows);
  74 static void yaffs_RemoveObjectFromDirectory(yaffs_Object * obj);
  75 static int yaffs_CheckStructures(void);
  76 static int yaffs_DeleteWorker(yaffs_Object * in, yaffs_Tnode * tn, __u32 level,
  77                               int chunkOffset, int *limit);
  78 static int yaffs_DoGenericObjectDeletion(yaffs_Object * in);
  79
  80 static yaffs_BlockInfo *yaffs_GetBlockInfo(yaffs_Device * dev, int blockNo);
  81
  82
  83 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,
  84                                   int chunkInNAND);
  85
  86 static int yaffs_UnlinkWorker(yaffs_Object * obj);
  87 static void yaffs_DestroyObject(yaffs_Object * obj);
  88
  89 static int yaffs_TagsMatch(const yaffs_ExtendedTags * tags, int objectId,
  90                            int chunkInObject);
  91
  92 loff_t yaffs_GetFileSize(yaffs_Object * obj);
  93
  94 static int yaffs_AllocateChunk(yaffs_Device * dev, int useReserve, yaffs_BlockInfo **blockUsedPtr);
  95
  96 static void yaffs_VerifyFreeChunks(yaffs_Device * dev);
  97
  98 static void yaffs_CheckObjectDetailsLoaded(yaffs_Object *in);
  99
 100 static void yaffs_VerifyDirectory(yaffs_Object *directory);
 101 #ifdef YAFFS_PARANOID
 102 static int yaffs_CheckFileSanity(yaffs_Object * in);
 103 #else
 104 #define yaffs_CheckFileSanity(in)
 105 #endif
 106
 107 static void yaffs_InvalidateWholeChunkCache(yaffs_Object * in);
 108 static void yaffs_InvalidateChunkCache(yaffs_Object * object, int chunkId);
 109
 110 static void yaffs_InvalidateCheckpoint(yaffs_Device *dev);
 111
 112 static int yaffs_FindChunkInFile(yaffs_Object * in, int chunkInInode,
 113                                  yaffs_ExtendedTags * tags);
 114
 115 static __u32 yaffs_GetChunkGroupBase(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos);
 116 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device * dev,
 117                                           yaffs_FileStructure * fStruct,
 118                                           __u32 chunkId);
 119
 120
 121 /* Function to calculate chunk and offset */
 122
 123 static void yaffs_AddrToChunk(yaffs_Device *dev, loff_t addr, int *chunkOut, __u32 *offsetOut)
 124 {
 125         int chunk;
 126         __u32 offset;
 127
 128         chunk  = (__u32)(addr >> dev->chunkShift);
 129
 130         if(dev->chunkDiv == 1)
 131         {
 132                 /* easy power of 2 case */
 133                 offset = (__u32)(addr & dev->chunkMask);
 134         }
 135         else
 136         {
 137                 /* Non power-of-2 case */
 138
 139                 loff_t chunkBase;
 140
 141                 chunk /= dev->chunkDiv;
 142
 143                 chunkBase = ((loff_t)chunk) * dev->nDataBytesPerChunk;
 144                 offset = (__u32)(addr - chunkBase);
 145         }
 146
 147         *chunkOut = chunk;
 148         *offsetOut = offset;
 149 }
 150
 151 /* Function to return the number of shifts for a power of 2 greater than or equal
 152  * to the given number
 153  * Note we don't try to cater for all possible numbers and this does not have to
 154  * be hellishly efficient.
 155  */
 156
 157 static __u32 ShiftsGE(__u32 x)
 158 {
 159         int extraBits;
 160         int nShifts;
 161
 162         nShifts = extraBits = 0;
 163
 164         while(x>1){
 165                 if(x & 1) extraBits++;
 166                 x>>=1;
 167                 nShifts++;
 168         }
 169
 170         if(extraBits)
 171                 nShifts++;
 172
 173         return nShifts;
 174 }
 175
 176 /* Function to return the number of shifts to get a 1 in bit 0
 177  */
 178
 179 static __u32 Shifts(__u32 x)
 180 {
 181         int nShifts;
 182
 183         nShifts =  0;
 184
 185         if(!x) return 0;
 186
 187         while( !(x&1)){
 188                 x>>=1;
 189                 nShifts++;
 190         }
 191
 192         return nShifts;
 193 }
 194
 195
 196
 197 /*
 198  * Temporary buffer manipulations.
 199  */
 200
 201 static int yaffs_InitialiseTempBuffers(yaffs_Device *dev)
 202 {
 203         int i;
 204         __u8 *buf = (__u8 *)1;
 205
 206         memset(dev->tempBuffer,0,sizeof(dev->tempBuffer));
 207
 208         for (i = 0; buf && i < YAFFS_N_TEMP_BUFFERS; i++) {
 209                 dev->tempBuffer[i].line = 0;    /* not in use */
 210                 dev->tempBuffer[i].buffer = buf =
 211                     YMALLOC_DMA(dev->totalBytesPerChunk);
 212         }
 213
 214         return buf ? YAFFS_OK : YAFFS_FAIL;
 215
 216 }
 217
 218 __u8 *yaffs_GetTempBuffer(yaffs_Device * dev, int lineNo)
 219 {
 220         int i, j;
 221
 222         dev->tempInUse++;
 223         if(dev->tempInUse > dev->maxTemp)
 224                 dev->maxTemp = dev->tempInUse;
 225
 226         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
 227                 if (dev->tempBuffer[i].line == 0) {
 228                         dev->tempBuffer[i].line = lineNo;
 229                         if ((i + 1) > dev->maxTemp) {
 230                                 dev->maxTemp = i + 1;
 231                                 for (j = 0; j <= i; j++)
 232                                         dev->tempBuffer[j].maxLine =
 233                                             dev->tempBuffer[j].line;
 234                         }
 235
 236                         return dev->tempBuffer[i].buffer;
 237                 }
 238         }
 239
 240         T(YAFFS_TRACE_BUFFERS,
 241           (TSTR("Out of temp buffers at line %d, other held by lines:"),
 242            lineNo));
 243         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
 244                 T(YAFFS_TRACE_BUFFERS, (TSTR(" %d "), dev->tempBuffer[i].line));
 245         }
 246         T(YAFFS_TRACE_BUFFERS, (TSTR(" " TENDSTR)));
 247
 248         /*
 249          * If we got here then we have to allocate an unmanaged one
 250          * This is not good.
 251          */
 252
 253         dev->unmanagedTempAllocations++;
 254         return YMALLOC(dev->nDataBytesPerChunk);
 255
 256 }
 257
 258 void yaffs_ReleaseTempBuffer(yaffs_Device * dev, __u8 * buffer,
 259                                     int lineNo)
 260 {
 261         int i;
 262
 263         dev->tempInUse--;
 264
 265         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
 266                 if (dev->tempBuffer[i].buffer == buffer) {
 267                         dev->tempBuffer[i].line = 0;
 268                         return;
 269                 }
 270         }
 271
 272         if (buffer) {
 273                 /* assume it is an unmanaged one. */
 274                 T(YAFFS_TRACE_BUFFERS,
 275                   (TSTR("Releasing unmanaged temp buffer in line %d" TENDSTR),
 276                    lineNo));
 277                 YFREE(buffer);
 278                 dev->unmanagedTempDeallocations++;
 279         }
 280
 281 }
 282
 283 /*
 284  * Determine if we have a managed buffer.
 285  */
 286 int yaffs_IsManagedTempBuffer(yaffs_Device * dev, const __u8 * buffer)
 287 {
 288         int i;
 289         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
 290                 if (dev->tempBuffer[i].buffer == buffer)
 291                         return 1;
 292
 293         }
 294
 295     for (i = 0; i < dev->nShortOpCaches; i++) {
 296         if( dev->srCache[i].data == buffer )
 297             return 1;
 298
 299     }
 300
 301     if (buffer == dev->checkpointBuffer)
 302       return 1;
 303
 304     T(YAFFS_TRACE_ALWAYS,
 305           (TSTR("yaffs: unmaged buffer detected.\n" TENDSTR)));
 306     return 0;
 307 }
 308
 309
 310
 311 /*
 312  * Chunk bitmap manipulations
 313  */
 314
 315 static Y_INLINE __u8 *yaffs_BlockBits(yaffs_Device * dev, int blk)
 316 {
 317         if (blk < dev->internalStartBlock || blk > dev->internalEndBlock) {
 318                 T(YAFFS_TRACE_ERROR,
 319                   (TSTR("**>> yaffs: BlockBits block %d is not valid" TENDSTR),
 320                    blk));
 321                 YBUG();
 322         }
 323         return dev->chunkBits +
 324             (dev->chunkBitmapStride * (blk - dev->internalStartBlock));
 325 }
 326
 327 static Y_INLINE void yaffs_VerifyChunkBitId(yaffs_Device *dev, int blk, int chunk)
 328 {
 329         if(blk < dev->internalStartBlock || blk > dev->internalEndBlock ||
 330            chunk < 0 || chunk >= dev->nChunksPerBlock) {
 331            T(YAFFS_TRACE_ERROR,
 332             (TSTR("**>> yaffs: Chunk Id (%d:%d) invalid"TENDSTR),blk,chunk));
 333             YBUG();
 334         }
 335 }
 336
 337 static Y_INLINE void yaffs_ClearChunkBits(yaffs_Device * dev, int blk)
 338 {
 339         __u8 *blkBits = yaffs_BlockBits(dev, blk);
 340
 341         memset(blkBits, 0, dev->chunkBitmapStride);
 342 }
 343
 344 static Y_INLINE void yaffs_ClearChunkBit(yaffs_Device * dev, int blk, int chunk)
 345 {
 346         __u8 *blkBits = yaffs_BlockBits(dev, blk);
 347
 348         yaffs_VerifyChunkBitId(dev,blk,chunk);
 349
 350         blkBits[chunk / 8] &= ~(1 << (chunk & 7));
 351 }
 352
 353 static Y_INLINE void yaffs_SetChunkBit(yaffs_Device * dev, int blk, int chunk)
 354 {
 355         __u8 *blkBits = yaffs_BlockBits(dev, blk);
 356
 357         yaffs_VerifyChunkBitId(dev,blk,chunk);
 358
 359         blkBits[chunk / 8] |= (1 << (chunk & 7));
 360 }
 361
 362 static Y_INLINE int yaffs_CheckChunkBit(yaffs_Device * dev, int blk, int chunk)
 363 {
 364         __u8 *blkBits = yaffs_BlockBits(dev, blk);
 365         yaffs_VerifyChunkBitId(dev,blk,chunk);
 366
 367         return (blkBits[chunk / 8] & (1 << (chunk & 7))) ? 1 : 0;
 368 }
 369
 370 static Y_INLINE int yaffs_StillSomeChunkBits(yaffs_Device * dev, int blk)
 371 {
 372         __u8 *blkBits = yaffs_BlockBits(dev, blk);
 373         int i;
 374         for (i = 0; i < dev->chunkBitmapStride; i++) {
 375                 if (*blkBits)
 376                         return 1;
 377                 blkBits++;
 378         }
 379         return 0;
 380 }
 381
 382 static int yaffs_CountChunkBits(yaffs_Device * dev, int blk)
 383 {
 384         __u8 *blkBits = yaffs_BlockBits(dev, blk);
 385         int i;
 386         int n = 0;
 387         for (i = 0; i < dev->chunkBitmapStride; i++) {
 388                 __u8 x = *blkBits;
 389                 while(x){
 390                         if(x & 1)
 391                                 n++;
 392                         x >>=1;
 393                 }
 394
 395                 blkBits++;
 396         }
 397         return n;
 398 }
 399
 400 /*
 401  * Verification code
 402  */
 403
 404 static int yaffs_SkipVerification(yaffs_Device *dev)
 405 {
 406         return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY | YAFFS_TRACE_VERIFY_FULL));
 407 }
 408
 409 static int yaffs_SkipFullVerification(yaffs_Device *dev)
 410 {
 411         return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY_FULL));
 412 }
 413
 414 static int yaffs_SkipNANDVerification(yaffs_Device *dev)
 415 {
 416         return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY_NAND));
 417 }
 418
 419 static const char * blockStateName[] = {
 420 "Unknown",
 421 "Needs scanning",
 422 "Scanning",
 423 "Empty",
 424 "Allocating",
 425 "Full",
 426 "Dirty",
 427 "Checkpoint",
 428 "Collecting",
 429 "Dead"
 430 };
 431
 432 static void yaffs_VerifyBlock(yaffs_Device *dev,yaffs_BlockInfo *bi,int n)
 433 {
 434         int actuallyUsed;
 435         int inUse;
 436
 437         if(yaffs_SkipVerification(dev))
 438                 return;
 439
 440         /* Report illegal runtime states */
 441         if(bi->blockState >= YAFFS_NUMBER_OF_BLOCK_STATES)
 442                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has undefined state %d"TENDSTR),n,bi->blockState));
 443
 444         switch(bi->blockState){
 445          case YAFFS_BLOCK_STATE_UNKNOWN:
 446          case YAFFS_BLOCK_STATE_SCANNING:
 447          case YAFFS_BLOCK_STATE_NEEDS_SCANNING:
 448                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has bad run-state %s"TENDSTR),
 449                 n,blockStateName[bi->blockState]));
 450         }
 451
 452         /* Check pages in use and soft deletions are legal */
 453
 454         actuallyUsed = bi->pagesInUse - bi->softDeletions;
 455
 456         if(bi->pagesInUse < 0 || bi->pagesInUse > dev->nChunksPerBlock ||
 457            bi->softDeletions < 0 || bi->softDeletions > dev->nChunksPerBlock ||
 458            actuallyUsed < 0 || actuallyUsed > dev->nChunksPerBlock)
 459                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has illegal values pagesInUsed %d softDeletions %d"TENDSTR),
 460                 n,bi->pagesInUse,bi->softDeletions));
 461
 462
 463         /* Check chunk bitmap legal */
 464         inUse = yaffs_CountChunkBits(dev,n);
 465         if(inUse != bi->pagesInUse)
 466                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has inconsistent values pagesInUse %d counted chunk bits %d"TENDSTR),
 467                         n,bi->pagesInUse,inUse));
 468
 469         /* Check that the sequence number is valid.
 470          * Ten million is legal, but is very unlikely
 471          */
 472         if(dev->isYaffs2 &&
 473            (bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING || bi->blockState == YAFFS_BLOCK_STATE_FULL) &&
 474            (bi->sequenceNumber < YAFFS_LOWEST_SEQUENCE_NUMBER || bi->sequenceNumber > 10000000 ))
 475                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has suspect sequence number of %d"TENDSTR),
 476                 n,bi->sequenceNumber));
 477
 478 }
 479
 480 static void yaffs_VerifyCollectedBlock(yaffs_Device *dev,yaffs_BlockInfo *bi,int n)
 481 {
 482         yaffs_VerifyBlock(dev,bi,n);
 483
 484         /* After collection the block should be in the erased state */
 485         /* This will need to change if we do partial gc */
 486
 487         if(bi->blockState != YAFFS_BLOCK_STATE_COLLECTING &&
 488            bi->blockState != YAFFS_BLOCK_STATE_EMPTY){
 489                 T(YAFFS_TRACE_ERROR,(TSTR("Block %d is in state %d after gc, should be erased"TENDSTR),
 490                         n,bi->blockState));
 491         }
 492 }
 493
 494 static void yaffs_VerifyBlocks(yaffs_Device *dev)
 495 {
 496         int i;
 497         int nBlocksPerState[YAFFS_NUMBER_OF_BLOCK_STATES];
 498         int nIllegalBlockStates = 0;
 499
 500
 501         if(yaffs_SkipVerification(dev))
 502                 return;
 503
 504         memset(nBlocksPerState,0,sizeof(nBlocksPerState));
 505
 506
 507         for(i = dev->internalStartBlock; i <= dev->internalEndBlock; i++){
 508                 yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,i);
 509                 yaffs_VerifyBlock(dev,bi,i);
 510
 511                 if(bi->blockState < YAFFS_NUMBER_OF_BLOCK_STATES)
 512                         nBlocksPerState[bi->blockState]++;
 513                 else
 514                         nIllegalBlockStates++;
 515
 516         }
 517
 518         T(YAFFS_TRACE_VERIFY,(TSTR(""TENDSTR)));
 519         T(YAFFS_TRACE_VERIFY,(TSTR("Block summary"TENDSTR)));
 520
 521         T(YAFFS_TRACE_VERIFY,(TSTR("%d blocks have illegal states"TENDSTR),nIllegalBlockStates));
 522         if(nBlocksPerState[YAFFS_BLOCK_STATE_ALLOCATING] > 1)
 523                 T(YAFFS_TRACE_VERIFY,(TSTR("Too many allocating blocks"TENDSTR)));
 524
 525         for(i = 0; i < YAFFS_NUMBER_OF_BLOCK_STATES; i++)
 526                 T(YAFFS_TRACE_VERIFY,
 527                   (TSTR("%s %d blocks"TENDSTR),
 528                   blockStateName[i],nBlocksPerState[i]));
 529
 530         if(dev->blocksInCheckpoint != nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT])
 531                 T(YAFFS_TRACE_VERIFY,
 532                  (TSTR("Checkpoint block count wrong dev %d count %d"TENDSTR),
 533                  dev->blocksInCheckpoint, nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT]));
 534
 535         if(dev->nErasedBlocks != nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY])
 536                 T(YAFFS_TRACE_VERIFY,
 537                  (TSTR("Erased block count wrong dev %d count %d"TENDSTR),
 538                  dev->nErasedBlocks, nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY]));
 539
 540         if(nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING] > 1)
 541                 T(YAFFS_TRACE_VERIFY,
 542                  (TSTR("Too many collecting blocks %d (max is 1)"TENDSTR),
 543                  nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING]));
 544
 545         T(YAFFS_TRACE_VERIFY,(TSTR(""TENDSTR)));
 546
 547 }
 548
 549 /*
 550  * Verify the object header. oh must be valid, but obj and tags may be NULL in which
 551  * case those tests will not be performed.
 552  */
 553 static void yaffs_VerifyObjectHeader(yaffs_Object *obj, yaffs_ObjectHeader *oh, yaffs_ExtendedTags *tags, int parentCheck)
 554 {
 555         if(obj && yaffs_SkipVerification(obj->myDev))
 556                 return;
 557
 558         if(!(tags && obj && oh)){
 559                 T(YAFFS_TRACE_VERIFY,
 560                                 (TSTR("Verifying object header tags %x obj %x oh %x"TENDSTR),
 561                                 (__u32)tags,(__u32)obj,(__u32)oh));
 562                 return;
 563         }
 564
 565         if(oh->type <= YAFFS_OBJECT_TYPE_UNKNOWN ||
 566            oh->type > YAFFS_OBJECT_TYPE_MAX)
 567                 T(YAFFS_TRACE_VERIFY,
 568                  (TSTR("Obj %d header type is illegal value 0x%x"TENDSTR),
 569                  tags->objectId, oh->type));
 570
 571         if(tags->objectId != obj->objectId)
 572                 T(YAFFS_TRACE_VERIFY,
 573                  (TSTR("Obj %d header mismatch objectId %d"TENDSTR),
 574                  tags->objectId, obj->objectId));
 575
 576
 577         /*
 578          * Check that the object's parent ids match if parentCheck requested.
 579          *
 580          * Tests do not apply to the root object.
 581          */
 582
 583         if(parentCheck && tags->objectId > 1 && !obj->parent)
 584                 T(YAFFS_TRACE_VERIFY,
 585                  (TSTR("Obj %d header mismatch parentId %d obj->parent is NULL"TENDSTR),
 586                  tags->objectId, oh->parentObjectId));
 587
 588
 589         if(parentCheck && obj->parent &&
 590            oh->parentObjectId != obj->parent->objectId &&
 591            (oh->parentObjectId != YAFFS_OBJECTID_UNLINKED ||
 592             obj->parent->objectId != YAFFS_OBJECTID_DELETED))
 593                 T(YAFFS_TRACE_VERIFY,
 594                  (TSTR("Obj %d header mismatch parentId %d parentObjectId %d"TENDSTR),
 595                  tags->objectId, oh->parentObjectId, obj->parent->objectId));
 596
 597
 598         if(tags->objectId > 1 && oh->name[0] == 0) /* Null name */
 599                 T(YAFFS_TRACE_VERIFY,
 600                 (TSTR("Obj %d header name is NULL"TENDSTR),
 601                  obj->objectId));
 602
 603         if(tags->objectId > 1 && ((__u8)(oh->name[0])) == 0xff) /* Trashed name */
 604                 T(YAFFS_TRACE_VERIFY,
 605                 (TSTR("Obj %d header name is 0xFF"TENDSTR),
 606                  obj->objectId));
 607 }
 608
 609
 610
 611 static int yaffs_VerifyTnodeWorker(yaffs_Object * obj, yaffs_Tnode * tn,
 612                                         __u32 level, int chunkOffset)
 613 {
 614         int i;
 615         yaffs_Device *dev = obj->myDev;
 616         int ok = 1;
 617
 618         if (tn) {
 619                 if (level > 0) {
 620
 621                         for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++){
 622                                 if (tn->internal[i]) {
 623                                         ok = yaffs_VerifyTnodeWorker(obj,
 624                                                         tn->internal[i],
 625                                                         level - 1,
 626                                                         (chunkOffset<<YAFFS_TNODES_INTERNAL_BITS) + i);
 627                                 }
 628                         }
 629                 } else if (level == 0) {
 630                         yaffs_ExtendedTags tags;
 631                         __u32 objectId = obj->objectId;
 632
 633                         chunkOffset <<=  YAFFS_TNODES_LEVEL0_BITS;
 634
 635                         for(i = 0; i < YAFFS_NTNODES_LEVEL0; i++){
 636                                 __u32 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
 637
 638                                 if(theChunk > 0){
 639                                         /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),tags.objectId,tags.chunkId,theChunk)); */
 640                                         yaffs_ReadChunkWithTagsFromNAND(dev,theChunk,NULL, &tags);
 641                                         if(tags.objectId != objectId || tags.chunkId != chunkOffset){
 642                                                 T(~0,(TSTR("Object %d chunkId %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR),
 643                                                         objectId, chunkOffset, theChunk,
 644                                                         tags.objectId, tags.chunkId));
 645                                         }
 646                                 }
 647                                 chunkOffset++;
 648                         }
 649                 }
 650         }
 651
 652         return ok;
 653
 654 }
 655
 656
 657 static void yaffs_VerifyFile(yaffs_Object *obj)
 658 {
 659         int requiredTallness;
 660         int actualTallness;
 661         __u32 lastChunk;
 662         __u32 x;
 663         __u32 i;
 664         yaffs_Device *dev;
 665         yaffs_ExtendedTags tags;
 666         yaffs_Tnode *tn;
 667         __u32 objectId;
 668
 669         if(!obj)
 670                 return;
 671
 672         if(yaffs_SkipVerification(obj->myDev))
 673                 return;
 674
 675         dev = obj->myDev;
 676         objectId = obj->objectId;
 677
 678         /* Check file size is consistent with tnode depth */
 679         lastChunk =  obj->variant.fileVariant.fileSize / dev->nDataBytesPerChunk + 1;
 680         x = lastChunk >> YAFFS_TNODES_LEVEL0_BITS;
 681         requiredTallness = 0;
 682         while (x> 0) {
 683                 x >>= YAFFS_TNODES_INTERNAL_BITS;
 684                 requiredTallness++;
 685         }
 686
 687         actualTallness = obj->variant.fileVariant.topLevel;
 688
 689         if(requiredTallness > actualTallness )
 690                 T(YAFFS_TRACE_VERIFY,
 691                 (TSTR("Obj %d had tnode tallness %d, needs to be %d"TENDSTR),
 692                  obj->objectId,actualTallness, requiredTallness));
 693
 694
 695         /* Check that the chunks in the tnode tree are all correct.
 696          * We do this by scanning through the tnode tree and
 697          * checking the tags for every chunk match.
 698          */
 699
 700         if(yaffs_SkipNANDVerification(dev))
 701                 return;
 702
 703         for(i = 1; i <= lastChunk; i++){
 704                 tn = yaffs_FindLevel0Tnode(dev, &obj->variant.fileVariant,i);
 705
 706                 if (tn) {
 707                         __u32 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
 708                         if(theChunk > 0){
 709                                 /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),objectId,i,theChunk)); */
 710                                 yaffs_ReadChunkWithTagsFromNAND(dev,theChunk,NULL, &tags);
 711                                 if(tags.objectId != objectId || tags.chunkId != i){
 712                                         T(~0,(TSTR("Object %d chunkId %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR),
 713                                                 objectId, i, theChunk,
 714                                                 tags.objectId, tags.chunkId));
 715                                 }
 716                         }
 717                 }
 718
 719         }
 720
 721 }
 722
 723
 724 static void yaffs_VerifyHardLink(yaffs_Object *obj)
 725 {
 726         if(obj && yaffs_SkipVerification(obj->myDev))
 727                 return;
 728
 729         /* Verify sane equivalent object */
 730 }
 731
 732 static void yaffs_VerifySymlink(yaffs_Object *obj)
 733 {
 734         if(obj && yaffs_SkipVerification(obj->myDev))
 735                 return;
 736
 737         /* Verify symlink string */
 738 }
 739
 740 static void yaffs_VerifySpecial(yaffs_Object *obj)
 741 {
 742         if(obj && yaffs_SkipVerification(obj->myDev))
 743                 return;
 744 }
 745
 746 static void yaffs_VerifyObject(yaffs_Object *obj)
 747 {
 748         yaffs_Device *dev;
 749
 750         __u32 chunkMin;
 751         __u32 chunkMax;
 752
 753         __u32 chunkIdOk;
 754         __u32 chunkIsLive;
 755
 756         if(!obj)
 757                 return;
 758
 759         dev = obj->myDev;
 760
 761         if(yaffs_SkipVerification(dev))
 762                 return;
 763
 764         /* Check sane object header chunk */
 765
 766         chunkMin = dev->internalStartBlock * dev->nChunksPerBlock;
 767         chunkMax = (dev->internalEndBlock+1) * dev->nChunksPerBlock - 1;
 768
 769         chunkIdOk = (((unsigned)(obj->hdrChunk)) >= chunkMin && ((unsigned)(obj->hdrChunk)) <= chunkMax);
 770         chunkIsLive = chunkIdOk &&
 771                         yaffs_CheckChunkBit(dev,
 772                                             obj->hdrChunk / dev->nChunksPerBlock,
 773                                             obj->hdrChunk % dev->nChunksPerBlock);
 774         if(!obj->fake &&
 775             (!chunkIdOk || !chunkIsLive)) {
 776            T(YAFFS_TRACE_VERIFY,
 777            (TSTR("Obj %d has chunkId %d %s %s"TENDSTR),
 778            obj->objectId,obj->hdrChunk,
 779            chunkIdOk ? "" : ",out of range",
 780            chunkIsLive || !chunkIdOk ? "" : ",marked as deleted"));
 781         }
 782
 783         if(chunkIdOk && chunkIsLive &&!yaffs_SkipNANDVerification(dev)) {
 784                 yaffs_ExtendedTags tags;
 785                 yaffs_ObjectHeader *oh;
 786                 __u8 *buffer = yaffs_GetTempBuffer(dev,__LINE__);
 787
 788                 oh = (yaffs_ObjectHeader *)buffer;
 789
 790                 yaffs_ReadChunkWithTagsFromNAND(dev, obj->hdrChunk,buffer, &tags);
 791
 792                 yaffs_VerifyObjectHeader(obj,oh,&tags,1);
 793
 794                 yaffs_ReleaseTempBuffer(dev,buffer,__LINE__);
 795         }
 796
 797         /* Verify it has a parent */
 798         if(obj && !obj->fake &&
 799            (!obj->parent || obj->parent->myDev != dev)){
 800            T(YAFFS_TRACE_VERIFY,
 801            (TSTR("Obj %d has parent pointer %p which does not look like an object"TENDSTR),
 802            obj->objectId,obj->parent));
 803         }
 804
 805         /* Verify parent is a directory */
 806         if(obj->parent && obj->parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY){
 807            T(YAFFS_TRACE_VERIFY,
 808            (TSTR("Obj %d's parent is not a directory (type %d)"TENDSTR),
 809            obj->objectId,obj->parent->variantType));
 810         }
 811
 812         switch(obj->variantType){
 813         case YAFFS_OBJECT_TYPE_FILE:
 814                 yaffs_VerifyFile(obj);
 815                 break;
 816         case YAFFS_OBJECT_TYPE_SYMLINK:
 817                 yaffs_VerifySymlink(obj);
 818                 break;
 819         case YAFFS_OBJECT_TYPE_DIRECTORY:
 820                 yaffs_VerifyDirectory(obj);
 821                 break;
 822         case YAFFS_OBJECT_TYPE_HARDLINK:
 823                 yaffs_VerifyHardLink(obj);
 824                 break;
 825         case YAFFS_OBJECT_TYPE_SPECIAL:
 826                 yaffs_VerifySpecial(obj);
 827                 break;
 828         case YAFFS_OBJECT_TYPE_UNKNOWN:
 829         default:
 830                 T(YAFFS_TRACE_VERIFY,
 831                 (TSTR("Obj %d has illegaltype %d"TENDSTR),
 832                 obj->objectId,obj->variantType));
 833                 break;
 834         }
 835
 836
 837 }
 838
 839 static void yaffs_VerifyObjects(yaffs_Device *dev)
 840 {
 841         yaffs_Object *obj;
 842         int i;
 843         struct ylist_head *lh;
 844
 845         if(yaffs_SkipVerification(dev))
 846                 return;
 847
 848         /* Iterate through the objects in each hash entry */
 849
 850          for(i = 0; i <  YAFFS_NOBJECT_BUCKETS; i++){
 851                 ylist_for_each(lh, &dev->objectBucket[i].list) {
 852                         if (lh) {
 853                                 obj = ylist_entry(lh, yaffs_Object, hashLink);
 854                                 yaffs_VerifyObject(obj);
 855                         }
 856                 }
 857          }
 858
 859 }
 860
 861
 862 /*
 863  *  Simple hash function. Needs to have a reasonable spread
 864  */
 865
 866 static Y_INLINE int yaffs_HashFunction(int n)
 867 {
 868         n = abs(n);
 869         return (n % YAFFS_NOBJECT_BUCKETS);
 870 }
 871
 872 /*
 873  * Access functions to useful fake objects.
 874  * Note that root might have a presence in NAND if permissions are set.
 875  */
 876
 877 yaffs_Object *yaffs_Root(yaffs_Device * dev)
 878 {
 879         return dev->rootDir;
 880 }
 881
 882 yaffs_Object *yaffs_LostNFound(yaffs_Device * dev)
 883 {
 884         return dev->lostNFoundDir;
 885 }
 886
 887
 888 /*
 889  *  Erased NAND checking functions
 890  */
 891
 892 int yaffs_CheckFF(__u8 * buffer, int nBytes)
 893 {
 894         /* Horrible, slow implementation */
 895         while (nBytes--) {
 896                 if (*buffer != 0xFF)
 897                         return 0;
 898                 buffer++;
 899         }
 900         return 1;
 901 }
 902
 903 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,
 904                                   int chunkInNAND)
 905 {
 906
 907         int retval = YAFFS_OK;
 908         __u8 *data = yaffs_GetTempBuffer(dev, __LINE__);
 909         yaffs_ExtendedTags tags;
 910         int result;
 911
 912         result = yaffs_ReadChunkWithTagsFromNAND(dev, chunkInNAND, data, &tags);
 913
 914         if(tags.eccResult > YAFFS_ECC_RESULT_NO_ERROR)
 915                 retval = YAFFS_FAIL;
 916
 917
 918         if (!yaffs_CheckFF(data, dev->nDataBytesPerChunk) || tags.chunkUsed) {
 919                 T(YAFFS_TRACE_NANDACCESS,
 920                   (TSTR("Chunk %d not erased" TENDSTR), chunkInNAND));
 921                 retval = YAFFS_FAIL;
 922         }
 923
 924         yaffs_ReleaseTempBuffer(dev, data, __LINE__);
 925
 926         return retval;
 927
 928 }
 929
 930 static int yaffs_WriteNewChunkWithTagsToNAND(struct yaffs_DeviceStruct *dev,
 931                                              const __u8 * data,
 932                                              yaffs_ExtendedTags * tags,
 933                                              int useReserve)
 934 {
 935         int attempts = 0;
 936         int writeOk = 0;
 937         int chunk;
 938
 939         yaffs_InvalidateCheckpoint(dev);
 940
 941         do {
 942                 yaffs_BlockInfo *bi = 0;
 943                 int erasedOk = 0;
 944
 945                 chunk = yaffs_AllocateChunk(dev, useReserve, &bi);
 946                 if (chunk < 0) {
 947                         /* no space */
 948                         break;
 949                 }
 950
 951                 /* First check this chunk is erased, if it needs
 952                  * checking.  The checking policy (unless forced
 953                  * always on) is as follows:
 954                  *
 955                  * Check the first page we try to write in a block.
 956                  * If the check passes then we don't need to check any
 957                  * more.        If the check fails, we check again...
 958                  * If the block has been erased, we don't need to check.
 959                  *
 960                  * However, if the block has been prioritised for gc,
 961                  * then we think there might be something odd about
 962                  * this block and stop using it.
 963                  *
 964                  * Rationale: We should only ever see chunks that have
 965                  * not been erased if there was a partially written
 966                  * chunk due to power loss.  This checking policy should
 967                  * catch that case with very few checks and thus save a
 968                  * lot of checks that are most likely not needed.
 969                  */
 970                 if (bi->gcPrioritise) {
 971                         yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
 972                         /* try another chunk */
 973                         continue;
 974                 }
 975
 976                 /* let's give it a try */
 977                 attempts++;
 978
 979 #ifdef CONFIG_YAFFS_ALWAYS_CHECK_CHUNK_ERASED
 980                 bi->skipErasedCheck = 0;
 981 #endif
 982                 if (!bi->skipErasedCheck) {
 983                         erasedOk = yaffs_CheckChunkErased(dev, chunk);
 984                         if (erasedOk != YAFFS_OK) {
 985                                 T(YAFFS_TRACE_ERROR,
 986                                 (TSTR ("**>> yaffs chunk %d was not erased"
 987                                 TENDSTR), chunk));
 988
 989                                 /* try another chunk */
 990                                 continue;
 991                         }
 992                         bi->skipErasedCheck = 1;
 993                 }
 994
 995                 writeOk = yaffs_WriteChunkWithTagsToNAND(dev, chunk,
 996                                 data, tags);
 997                 if (writeOk != YAFFS_OK) {
 998                         yaffs_HandleWriteChunkError(dev, chunk, erasedOk);
 999                         /* try another chunk */
1000                         continue;
1001                 }
1002
1003                 /* Copy the data into the robustification buffer */
1004                 yaffs_HandleWriteChunkOk(dev, chunk, data, tags);
1005
1006         } while (writeOk != YAFFS_OK &&
1007                 (yaffs_wr_attempts <= 0 || attempts <= yaffs_wr_attempts));
1008
1009         if(!writeOk)
1010                 chunk = -1;
1011
1012         if (attempts > 1) {
1013                 T(YAFFS_TRACE_ERROR,
1014                         (TSTR("**>> yaffs write required %d attempts" TENDSTR),
1015                         attempts));
1016
1017                 dev->nRetriedWrites += (attempts - 1);
1018         }
1019
1020         return chunk;
1021 }
1022
1023 /*
1024  * Block retiring for handling a broken block.
1025  */
1026
1027 static void yaffs_RetireBlock(yaffs_Device * dev, int blockInNAND)
1028 {
1029         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockInNAND);
1030
1031         yaffs_InvalidateCheckpoint(dev);
1032
1033         yaffs_MarkBlockBad(dev, blockInNAND);
1034
1035         bi->blockState = YAFFS_BLOCK_STATE_DEAD;
1036         bi->gcPrioritise = 0;
1037         bi->needsRetiring = 0;
1038
1039         dev->nRetiredBlocks++;
1040 }
1041
1042 /*
1043  * Functions for robustisizing TODO
1044  *
1045  */
1046
1047 static void yaffs_HandleWriteChunkOk(yaffs_Device * dev, int chunkInNAND,
1048                                      const __u8 * data,
1049                                      const yaffs_ExtendedTags * tags)
1050 {
1051 }
1052
1053 static void yaffs_HandleUpdateChunk(yaffs_Device * dev, int chunkInNAND,
1054                                     const yaffs_ExtendedTags * tags)
1055 {
1056 }
1057
1058 void yaffs_HandleChunkError(yaffs_Device *dev, yaffs_BlockInfo *bi)
1059 {
1060         if(!bi->gcPrioritise){
1061                 bi->gcPrioritise = 1;
1062                 dev->hasPendingPrioritisedGCs = 1;
1063                 bi->chunkErrorStrikes ++;
1064
1065                 if(bi->chunkErrorStrikes > 3){
1066                         bi->needsRetiring = 1; /* Too many stikes, so retire this */
1067                         T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs: Block struck out" TENDSTR)));
1068
1069                 }
1070
1071         }
1072 }
1073
1074 static void yaffs_HandleWriteChunkError(yaffs_Device * dev, int chunkInNAND, int erasedOk)
1075 {
1076
1077         int blockInNAND = chunkInNAND / dev->nChunksPerBlock;
1078         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockInNAND);
1079
1080         yaffs_HandleChunkError(dev,bi);
1081
1082
1083         if(erasedOk ) {
1084                 /* Was an actual write failure, so mark the block for retirement  */
1085                 bi->needsRetiring = 1;
1086                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
1087                   (TSTR("**>> Block %d needs retiring" TENDSTR), blockInNAND));
1088
1089
1090         }
1091
1092         /* Delete the chunk */
1093         yaffs_DeleteChunk(dev, chunkInNAND, 1, __LINE__);
1094 }
1095
1096
1097 /*---------------- Name handling functions ------------*/
1098
1099 static __u16 yaffs_CalcNameSum(const YCHAR * name)
1100 {
1101         __u16 sum = 0;
1102         __u16 i = 1;
1103
1104         const YUCHAR *bname = (const YUCHAR *) name;
1105         if (bname) {
1106                 while ((*bname) && (i < (YAFFS_MAX_NAME_LENGTH/2))) {
1107
1108 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
1109                         sum += yaffs_toupper(*bname) * i;
1110 #else
1111                         sum += (*bname) * i;
1112 #endif
1113                         i++;
1114                         bname++;
1115                 }
1116         }
1117
1118         return sum;
1119 }
1120
1121 static void yaffs_SetObjectName(yaffs_Object * obj, const YCHAR * name)
1122 {
1123 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
1124         memset(obj->shortName,0,sizeof (YCHAR) * (YAFFS_SHORT_NAME_LENGTH+1));
1125         if (name && yaffs_strlen(name) <= YAFFS_SHORT_NAME_LENGTH) {
1126                 yaffs_strcpy(obj->shortName, name);
1127         } else {
1128                 obj->shortName[0] = _Y('\0');
1129         }
1130 #endif
1131         obj->sum = yaffs_CalcNameSum(name);
1132 }
1133
1134 /*-------------------- TNODES -------------------
1135
1136  * List of spare tnodes
1137  * The list is hooked together using the first pointer
1138  * in the tnode.
1139  */
1140
1141 /* yaffs_CreateTnodes creates a bunch more tnodes and
1142  * adds them to the tnode free list.
1143  * Don't use this function directly
1144  */
1145
1146 static int yaffs_CreateTnodes(yaffs_Device * dev, int nTnodes)
1147 {
1148         int i;
1149         int tnodeSize;
1150         yaffs_Tnode *newTnodes;
1151         __u8 *mem;
1152         yaffs_Tnode *curr;
1153         yaffs_Tnode *next;
1154         yaffs_TnodeList *tnl;
1155
1156         if (nTnodes < 1)
1157                 return YAFFS_OK;
1158
1159         /* Calculate the tnode size in bytes for variable width tnode support.
1160          * Must be a multiple of 32-bits  */
1161         tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
1162
1163         if(tnodeSize < sizeof(yaffs_Tnode))
1164                 tnodeSize = sizeof(yaffs_Tnode);
1165
1166
1167         /* make these things */
1168
1169         newTnodes = YMALLOC(nTnodes * tnodeSize);
1170         mem = (__u8 *)newTnodes;
1171
1172         if (!newTnodes) {
1173                 T(YAFFS_TRACE_ERROR,
1174                   (TSTR("yaffs: Could not allocate Tnodes" TENDSTR)));
1175                 return YAFFS_FAIL;
1176         }
1177
1178         /* Hook them into the free list */
1179 #if 0
1180         for (i = 0; i < nTnodes - 1; i++) {
1181                 newTnodes[i].internal[0] = &newTnodes[i + 1];
1182 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1183                 newTnodes[i].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
1184 #endif
1185         }
1186
1187         newTnodes[nTnodes - 1].internal[0] = dev->freeTnodes;
1188 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1189         newTnodes[nTnodes - 1].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
1190 #endif
1191         dev->freeTnodes = newTnodes;
1192 #else
1193         /* New hookup for wide tnodes */
1194         for(i = 0; i < nTnodes -1; i++) {
1195                 curr = (yaffs_Tnode *) &mem[i * tnodeSize];
1196                 next = (yaffs_Tnode *) &mem[(i+1) * tnodeSize];
1197                 curr->internal[0] = next;
1198         }
1199
1200         curr = (yaffs_Tnode *) &mem[(nTnodes - 1) * tnodeSize];
1201         curr->internal[0] = dev->freeTnodes;
1202         dev->freeTnodes = (yaffs_Tnode *)mem;
1203
1204 #endif
1205
1206
1207         dev->nFreeTnodes += nTnodes;
1208         dev->nTnodesCreated += nTnodes;
1209
1210         /* Now add this bunch of tnodes to a list for freeing up.
1211          * NB If we can't add this to the management list it isn't fatal
1212          * but it just means we can't free this bunch of tnodes later.
1213          */
1214
1215         tnl = YMALLOC(sizeof(yaffs_TnodeList));
1216         if (!tnl) {
1217                 T(YAFFS_TRACE_ERROR,
1218                   (TSTR
1219                    ("yaffs: Could not add tnodes to management list" TENDSTR)));
1220                    return YAFFS_FAIL;
1221
1222         } else {
1223                 tnl->tnodes = newTnodes;
1224                 tnl->next = dev->allocatedTnodeList;
1225                 dev->allocatedTnodeList = tnl;
1226         }
1227
1228         T(YAFFS_TRACE_ALLOCATE, (TSTR("yaffs: Tnodes added" TENDSTR)));
1229
1230         return YAFFS_OK;
1231 }
1232
1233 /* GetTnode gets us a clean tnode. Tries to make allocate more if we run out */
1234
1235 static yaffs_Tnode *yaffs_GetTnodeRaw(yaffs_Device * dev)
1236 {
1237         yaffs_Tnode *tn = NULL;
1238
1239         /* If there are none left make more */
1240         if (!dev->freeTnodes) {
1241                 yaffs_CreateTnodes(dev, YAFFS_ALLOCATION_NTNODES);
1242         }
1243
1244         if (dev->freeTnodes) {
1245                 tn = dev->freeTnodes;
1246 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1247                 if (tn->internal[YAFFS_NTNODES_INTERNAL] != (void *)1) {
1248                         /* Hoosterman, this thing looks like it isn't in the list */
1249                         T(YAFFS_TRACE_ALWAYS,
1250                           (TSTR("yaffs: Tnode list bug 1" TENDSTR)));
1251                 }
1252 #endif
1253                 dev->freeTnodes = dev->freeTnodes->internal[0];
1254                 dev->nFreeTnodes--;
1255         }
1256
1257         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
1258
1259         return tn;
1260 }
1261
1262 static yaffs_Tnode *yaffs_GetTnode(yaffs_Device * dev)
1263 {
1264         yaffs_Tnode *tn = yaffs_GetTnodeRaw(dev);
1265         int tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
1266
1267         if(tnodeSize < sizeof(yaffs_Tnode))
1268                 tnodeSize = sizeof(yaffs_Tnode);
1269
1270         if(tn)
1271                 memset(tn, 0, tnodeSize);
1272
1273         return tn;
1274 }
1275
1276 /* FreeTnode frees up a tnode and puts it back on the free list */
1277 static void yaffs_FreeTnode(yaffs_Device * dev, yaffs_Tnode * tn)
1278 {
1279         if (tn) {
1280 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1281                 if (tn->internal[YAFFS_NTNODES_INTERNAL] != 0) {
1282                         /* Hoosterman, this thing looks like it is already in the list */
1283                         T(YAFFS_TRACE_ALWAYS,
1284                           (TSTR("yaffs: Tnode list bug 2" TENDSTR)));
1285                 }
1286                 tn->internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
1287 #endif
1288                 tn->internal[0] = dev->freeTnodes;
1289                 dev->freeTnodes = tn;
1290                 dev->nFreeTnodes++;
1291         }
1292         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
1293
1294 }
1295
1296 static void yaffs_DeinitialiseTnodes(yaffs_Device * dev)
1297 {
1298         /* Free the list of allocated tnodes */
1299         yaffs_TnodeList *tmp;
1300
1301         while (dev->allocatedTnodeList) {
1302                 tmp = dev->allocatedTnodeList->next;
1303
1304                 YFREE(dev->allocatedTnodeList->tnodes);
1305                 YFREE(dev->allocatedTnodeList);
1306                 dev->allocatedTnodeList = tmp;
1307
1308         }
1309
1310         dev->freeTnodes = NULL;
1311         dev->nFreeTnodes = 0;
1312 }
1313
1314 static void yaffs_InitialiseTnodes(yaffs_Device * dev)
1315 {
1316         dev->allocatedTnodeList = NULL;
1317         dev->freeTnodes = NULL;
1318         dev->nFreeTnodes = 0;
1319         dev->nTnodesCreated = 0;
1320
1321 }
1322
1323
1324 void yaffs_PutLevel0Tnode(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos, unsigned val)
1325 {
1326   __u32 *map = (__u32 *)tn;
1327   __u32 bitInMap;
1328   __u32 bitInWord;
1329   __u32 wordInMap;
1330   __u32 mask;
1331
1332   pos &= YAFFS_TNODES_LEVEL0_MASK;
1333   val >>= dev->chunkGroupBits;
1334
1335   bitInMap = pos * dev->tnodeWidth;
1336   wordInMap = bitInMap /32;
1337   bitInWord = bitInMap & (32 -1);
1338
1339   mask = dev->tnodeMask << bitInWord;
1340
1341   map[wordInMap] &= ~mask;
1342   map[wordInMap] |= (mask & (val << bitInWord));
1343
1344   if(dev->tnodeWidth > (32-bitInWord)) {
1345     bitInWord = (32 - bitInWord);
1346     wordInMap++;;
1347     mask = dev->tnodeMask >> (/*dev->tnodeWidth -*/ bitInWord);
1348     map[wordInMap] &= ~mask;
1349     map[wordInMap] |= (mask & (val >> bitInWord));
1350   }
1351 }
1352
1353 static __u32 yaffs_GetChunkGroupBase(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos)
1354 {
1355   __u32 *map = (__u32 *)tn;
1356   __u32 bitInMap;
1357   __u32 bitInWord;
1358   __u32 wordInMap;
1359   __u32 val;
1360
1361   pos &= YAFFS_TNODES_LEVEL0_MASK;
1362
1363   bitInMap = pos * dev->tnodeWidth;
1364   wordInMap = bitInMap /32;
1365   bitInWord = bitInMap & (32 -1);
1366
1367   val = map[wordInMap] >> bitInWord;
1368
1369   if(dev->tnodeWidth > (32-bitInWord)) {
1370     bitInWord = (32 - bitInWord);
1371     wordInMap++;;
1372     val |= (map[wordInMap] << bitInWord);
1373   }
1374
1375   val &= dev->tnodeMask;
1376   val <<= dev->chunkGroupBits;
1377
1378   return val;
1379 }
1380
1381 /* ------------------- End of individual tnode manipulation -----------------*/
1382
1383 /* ---------Functions to manipulate the look-up tree (made up of tnodes) ------
1384  * The look up tree is represented by the top tnode and the number of topLevel
1385  * in the tree. 0 means only the level 0 tnode is in the tree.
1386  */
1387
1388 /* FindLevel0Tnode finds the level 0 tnode, if one exists. */
1389 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device * dev,
1390                                           yaffs_FileStructure * fStruct,
1391                                           __u32 chunkId)
1392 {
1393
1394         yaffs_Tnode *tn = fStruct->top;
1395         __u32 i;
1396         int requiredTallness;
1397         int level = fStruct->topLevel;
1398
1399         /* Check sane level and chunk Id */
1400         if (level < 0 || level > YAFFS_TNODES_MAX_LEVEL) {
1401                 return NULL;
1402         }
1403
1404         if (chunkId > YAFFS_MAX_CHUNK_ID) {
1405                 return NULL;
1406         }
1407
1408         /* First check we're tall enough (ie enough topLevel) */
1409
1410         i = chunkId >> YAFFS_TNODES_LEVEL0_BITS;
1411         requiredTallness = 0;
1412         while (i) {
1413                 i >>= YAFFS_TNODES_INTERNAL_BITS;
1414                 requiredTallness++;
1415         }
1416
1417         if (requiredTallness > fStruct->topLevel) {
1418                 /* Not tall enough, so we can't find it, return NULL. */
1419                 return NULL;
1420         }
1421
1422         /* Traverse down to level 0 */
1423         while (level > 0 && tn) {
1424                 tn = tn->
1425                     internal[(chunkId >>
1426                                ( YAFFS_TNODES_LEVEL0_BITS +
1427                                  (level - 1) *
1428                                  YAFFS_TNODES_INTERNAL_BITS)
1429                               ) &
1430                              YAFFS_TNODES_INTERNAL_MASK];
1431                 level--;
1432
1433         }
1434
1435         return tn;
1436 }
1437
1438 /* AddOrFindLevel0Tnode finds the level 0 tnode if it exists, otherwise first expands the tree.
1439  * This happens in two steps:
1440  *  1. If the tree isn't tall enough, then make it taller.
1441  *  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
1442  *
1443  * Used when modifying the tree.
1444  *
1445  *  If the tn argument is NULL, then a fresh tnode will be added otherwise the specified tn will
1446  *  be plugged into the ttree.
1447  */
1448
1449 static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device * dev,
1450                                                yaffs_FileStructure * fStruct,
1451                                                __u32 chunkId,
1452                                                yaffs_Tnode *passedTn)
1453 {
1454
1455         int requiredTallness;
1456         int i;
1457         int l;
1458         yaffs_Tnode *tn;
1459
1460         __u32 x;
1461
1462
1463         /* Check sane level and page Id */
1464         if (fStruct->topLevel < 0 || fStruct->topLevel > YAFFS_TNODES_MAX_LEVEL) {
1465                 return NULL;
1466         }
1467
1468         if (chunkId > YAFFS_MAX_CHUNK_ID) {
1469                 return NULL;
1470         }
1471
1472         /* First check we're tall enough (ie enough topLevel) */
1473
1474         x = chunkId >> YAFFS_TNODES_LEVEL0_BITS;
1475         requiredTallness = 0;
1476         while (x) {
1477                 x >>= YAFFS_TNODES_INTERNAL_BITS;
1478                 requiredTallness++;
1479         }
1480
1481
1482         if (requiredTallness > fStruct->topLevel) {
1483                 /* Not tall enough,gotta make the tree taller */
1484                 for (i = fStruct->topLevel; i < requiredTallness; i++) {
1485
1486                         tn = yaffs_GetTnode(dev);
1487
1488                         if (tn) {
1489                                 tn->internal[0] = fStruct->top;
1490                                 fStruct->top = tn;
1491                         } else {
1492                                 T(YAFFS_TRACE_ERROR,
1493                                   (TSTR("yaffs: no more tnodes" TENDSTR)));
1494                         }
1495                 }
1496
1497                 fStruct->topLevel = requiredTallness;
1498         }
1499
1500         /* Traverse down to level 0, adding anything we need */
1501
1502         l = fStruct->topLevel;
1503         tn = fStruct->top;
1504
1505         if(l > 0) {
1506                 while (l > 0 && tn) {
1507                         x = (chunkId >>
1508                              ( YAFFS_TNODES_LEVEL0_BITS +
1509                               (l - 1) * YAFFS_TNODES_INTERNAL_BITS)) &
1510                             YAFFS_TNODES_INTERNAL_MASK;
1511
1512
1513                         if((l>1) && !tn->internal[x]){
1514                                 /* Add missing non-level-zero tnode */
1515                                 tn->internal[x] = yaffs_GetTnode(dev);
1516
1517                         } else if(l == 1) {
1518                                 /* Looking from level 1 at level 0 */
1519                                 if (passedTn) {
1520                                         /* If we already have one, then release it.*/
1521                                         if(tn->internal[x])
1522                                                 yaffs_FreeTnode(dev,tn->internal[x]);
1523                                         tn->internal[x] = passedTn;
1524
1525                                 } else if(!tn->internal[x]) {
1526                                         /* Don't have one, none passed in */
1527                                         tn->internal[x] = yaffs_GetTnode(dev);
1528                                 }
1529                         }
1530
1531                         tn = tn->internal[x];
1532                         l--;
1533                 }
1534         } else {
1535                 /* top is level 0 */
1536                 if(passedTn) {
1537                         memcpy(tn,passedTn,(dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8);
1538                         yaffs_FreeTnode(dev,passedTn);
1539                 }
1540         }
1541
1542         return tn;
1543 }
1544
1545 static int yaffs_FindChunkInGroup(yaffs_Device * dev, int theChunk,
1546                                   yaffs_ExtendedTags * tags, int objectId,
1547                                   int chunkInInode)
1548 {
1549         int j;
1550
1551         for (j = 0; theChunk && j < dev->chunkGroupSize; j++) {
1552                 if (yaffs_CheckChunkBit
1553                     (dev, theChunk / dev->nChunksPerBlock,
1554                      theChunk % dev->nChunksPerBlock)) {
1555                         yaffs_ReadChunkWithTagsFromNAND(dev, theChunk, NULL,
1556                                                         tags);
1557                         if (yaffs_TagsMatch(tags, objectId, chunkInInode)) {
1558                                 /* found it; */
1559                                 return theChunk;
1560
1561                         }
1562                 }
1563                 theChunk++;
1564         }
1565         return -1;
1566 }
1567
1568
1569 /* DeleteWorker scans backwards through the tnode tree and deletes all the
1570  * chunks and tnodes in the file
1571  * Returns 1 if the tree was deleted.
1572  * Returns 0 if it stopped early due to hitting the limit and the delete is incomplete.
1573  */
1574
1575 static int yaffs_DeleteWorker(yaffs_Object * in, yaffs_Tnode * tn, __u32 level,
1576                               int chunkOffset, int *limit)
1577 {
1578         int i;
1579         int chunkInInode;
1580         int theChunk;
1581         yaffs_ExtendedTags tags;
1582         int foundChunk;
1583         yaffs_Device *dev = in->myDev;
1584
1585         int allDone = 1;
1586
1587         if (tn) {
1588                 if (level > 0) {
1589
1590                         for (i = YAFFS_NTNODES_INTERNAL - 1; allDone && i >= 0;
1591                              i--) {
1592                                 if (tn->internal[i]) {
1593                                         if (limit && (*limit) < 0) {
1594                                                 allDone = 0;
1595                                         } else {
1596                                                 allDone =
1597                                                     yaffs_DeleteWorker(in,
1598                                                                        tn->
1599                                                                        internal
1600                                                                        [i],
1601                                                                        level -
1602                                                                        1,
1603                                                                        (chunkOffset
1604                                                                         <<
1605                                                                         YAFFS_TNODES_INTERNAL_BITS)
1606                                                                        + i,
1607                                                                        limit);
1608                                         }
1609                                         if (allDone) {
1610                                                 yaffs_FreeTnode(dev,
1611                                                                 tn->
1612                                                                 internal[i]);
1613                                                 tn->internal[i] = NULL;
1614                                         }
1615                                 }
1616
1617                         }
1618                         return (allDone) ? 1 : 0;
1619                 } else if (level == 0) {
1620                         int hitLimit = 0;
1621
1622                         for (i = YAFFS_NTNODES_LEVEL0 - 1; i >= 0 && !hitLimit;
1623                              i--) {
1624                                 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
1625                                 if (theChunk) {
1626
1627                                         chunkInInode =
1628                                             (chunkOffset <<
1629                                              YAFFS_TNODES_LEVEL0_BITS) + i;
1630
1631                                         foundChunk =
1632                                             yaffs_FindChunkInGroup(dev,
1633                                                                    theChunk,
1634                                                                    &tags,
1635                                                                    in->objectId,
1636                                                                    chunkInInode);
1637
1638                                         if (foundChunk > 0) {
1639                                                 yaffs_DeleteChunk(dev,
1640                                                                   foundChunk, 1,
1641                                                                   __LINE__);
1642                                                 in->nDataChunks--;
1643                                                 if (limit) {
1644                                                         *limit = *limit - 1;
1645                                                         if (*limit <= 0) {
1646                                                                 hitLimit = 1;
1647                                                         }
1648                                                 }
1649
1650                                         }
1651
1652                                         yaffs_PutLevel0Tnode(dev,tn,i,0);
1653                                 }
1654
1655                         }
1656                         return (i < 0) ? 1 : 0;
1657
1658                 }
1659
1660         }
1661
1662         return 1;
1663
1664 }
1665
1666 static void yaffs_SoftDeleteChunk(yaffs_Device * dev, int chunk)
1667 {
1668
1669         yaffs_BlockInfo *theBlock;
1670
1671         T(YAFFS_TRACE_DELETION, (TSTR("soft delete chunk %d" TENDSTR), chunk));
1672
1673         theBlock = yaffs_GetBlockInfo(dev, chunk / dev->nChunksPerBlock);
1674         if (theBlock) {
1675                 theBlock->softDeletions++;
1676                 dev->nFreeChunks++;
1677         }
1678 }
1679
1680 /* SoftDeleteWorker scans backwards through the tnode tree and soft deletes all the chunks in the file.
1681  * All soft deleting does is increment the block's softdelete count and pulls the chunk out
1682  * of the tnode.
1683  * Thus, essentially this is the same as DeleteWorker except that the chunks are soft deleted.
1684  */
1685
1686 static int yaffs_SoftDeleteWorker(yaffs_Object * in, yaffs_Tnode * tn,
1687                                   __u32 level, int chunkOffset)
1688 {
1689         int i;
1690         int theChunk;
1691         int allDone = 1;
1692         yaffs_Device *dev = in->myDev;
1693
1694         if (tn) {
1695                 if (level > 0) {
1696
1697                         for (i = YAFFS_NTNODES_INTERNAL - 1; allDone && i >= 0;
1698                              i--) {
1699                                 if (tn->internal[i]) {
1700                                         allDone =
1701                                             yaffs_SoftDeleteWorker(in,
1702                                                                    tn->
1703                                                                    internal[i],
1704                                                                    level - 1,
1705                                                                    (chunkOffset
1706                                                                     <<
1707                                                                     YAFFS_TNODES_INTERNAL_BITS)
1708                                                                    + i);
1709                                         if (allDone) {
1710                                                 yaffs_FreeTnode(dev,
1711                                                                 tn->
1712                                                                 internal[i]);
1713                                                 tn->internal[i] = NULL;
1714                                         } else {
1715                                                 /* Hoosterman... how could this happen? */
1716                                         }
1717                                 }
1718                         }
1719                         return (allDone) ? 1 : 0;
1720                 } else if (level == 0) {
1721
1722                         for (i = YAFFS_NTNODES_LEVEL0 - 1; i >= 0; i--) {
1723                                 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
1724                                 if (theChunk) {
1725                                         /* Note this does not find the real chunk, only the chunk group.
1726                                          * We make an assumption that a chunk group is not larger than
1727                                          * a block.
1728                                          */
1729                                         yaffs_SoftDeleteChunk(dev, theChunk);
1730                                         yaffs_PutLevel0Tnode(dev,tn,i,0);
1731                                 }
1732
1733                         }
1734                         return 1;
1735
1736                 }
1737
1738         }
1739
1740         return 1;
1741
1742 }
1743
1744 static void yaffs_SoftDeleteFile(yaffs_Object * obj)
1745 {
1746         if (obj->deleted &&
1747             obj->variantType == YAFFS_OBJECT_TYPE_FILE && !obj->softDeleted) {
1748                 if (obj->nDataChunks <= 0) {
1749                         /* Empty file with no duplicate object headers, just delete it immediately */
1750                         yaffs_FreeTnode(obj->myDev,
1751                                         obj->variant.fileVariant.top);
1752                         obj->variant.fileVariant.top = NULL;
1753                         T(YAFFS_TRACE_TRACING,
1754                           (TSTR("yaffs: Deleting empty file %d" TENDSTR),
1755                            obj->objectId));
1756                         yaffs_DoGenericObjectDeletion(obj);
1757                 } else {
1758                         yaffs_SoftDeleteWorker(obj,
1759                                                obj->variant.fileVariant.top,
1760                                                obj->variant.fileVariant.
1761                                                topLevel, 0);
1762                         obj->softDeleted = 1;
1763                 }
1764         }
1765 }
1766
1767 /* Pruning removes any part of the file structure tree that is beyond the
1768  * bounds of the file (ie that does not point to chunks).
1769  *
1770  * A file should only get pruned when its size is reduced.
1771  *
1772  * Before pruning, the chunks must be pulled from the tree and the
1773  * level 0 tnode entries must be zeroed out.
1774  * Could also use this for file deletion, but that's probably better handled
1775  * by a special case.
1776  */
1777
1778 static yaffs_Tnode *yaffs_PruneWorker(yaffs_Device * dev, yaffs_Tnode * tn,
1779                                       __u32 level, int del0)
1780 {
1781         int i;
1782         int hasData;
1783
1784         if (tn) {
1785                 hasData = 0;
1786
1787                 for (i = 0; i < YAFFS_NTNODES_INTERNAL; i++) {
1788                         if (tn->internal[i] && level > 0) {
1789                                 tn->internal[i] =
1790                                     yaffs_PruneWorker(dev, tn->internal[i],
1791                                                       level - 1,
1792                                                       (i == 0) ? del0 : 1);
1793                         }
1794
1795                         if (tn->internal[i]) {
1796                                 hasData++;
1797                         }
1798                 }
1799
1800                 if (hasData == 0 && del0) {
1801                         /* Free and return NULL */
1802
1803                         yaffs_FreeTnode(dev, tn);
1804                         tn = NULL;
1805                 }
1806
1807         }
1808
1809         return tn;
1810
1811 }
1812
1813 static int yaffs_PruneFileStructure(yaffs_Device * dev,
1814                                     yaffs_FileStructure * fStruct)
1815 {
1816         int i;
1817         int hasData;
1818         int done = 0;
1819         yaffs_Tnode *tn;
1820
1821         if (fStruct->topLevel > 0) {
1822                 fStruct->top =
1823                     yaffs_PruneWorker(dev, fStruct->top, fStruct->topLevel, 0);
1824
1825                 /* Now we have a tree with all the non-zero branches NULL but the height
1826                  * is the same as it was.
1827                  * Let's see if we can trim internal tnodes to shorten the tree.
1828                  * We can do this if only the 0th element in the tnode is in use
1829                  * (ie all the non-zero are NULL)
1830                  */
1831
1832                 while (fStruct->topLevel && !done) {
1833                         tn = fStruct->top;
1834
1835                         hasData = 0;
1836                         for (i = 1; i < YAFFS_NTNODES_INTERNAL; i++) {
1837                                 if (tn->internal[i]) {
1838                                         hasData++;
1839                                 }
1840                         }
1841
1842                         if (!hasData) {
1843                                 fStruct->top = tn->internal[0];
1844                                 fStruct->topLevel--;
1845                                 yaffs_FreeTnode(dev, tn);
1846                         } else {
1847                                 done = 1;
1848                         }
1849                 }
1850         }
1851
1852         return YAFFS_OK;
1853 }
1854
1855 /*-------------------- End of File Structure functions.-------------------*/
1856
1857 /* yaffs_CreateFreeObjects creates a bunch more objects and
1858  * adds them to the object free list.
1859  */
1860 static int yaffs_CreateFreeObjects(yaffs_Device * dev, int nObjects)
1861 {
1862         int i;
1863         yaffs_Object *newObjects;
1864         yaffs_ObjectList *list;
1865
1866         if (nObjects < 1)
1867                 return YAFFS_OK;
1868
1869         /* make these things */
1870         newObjects = YMALLOC(nObjects * sizeof(yaffs_Object));
1871         list = YMALLOC(sizeof(yaffs_ObjectList));
1872
1873         if (!newObjects || !list) {
1874                 if(newObjects)
1875                         YFREE(newObjects);
1876                 if(list)
1877                         YFREE(list);
1878                 T(YAFFS_TRACE_ALLOCATE,
1879                   (TSTR("yaffs: Could not allocate more objects" TENDSTR)));
1880                 return YAFFS_FAIL;
1881         }
1882
1883         /* Hook them into the free list */
1884         for (i = 0; i < nObjects - 1; i++) {
1885                 newObjects[i].siblings.next =
1886                     (struct ylist_head *)(&newObjects[i + 1]);
1887         }
1888
1889         newObjects[nObjects - 1].siblings.next = (void *)dev->freeObjects;
1890         dev->freeObjects = newObjects;
1891         dev->nFreeObjects += nObjects;
1892         dev->nObjectsCreated += nObjects;
1893
1894         /* Now add this bunch of Objects to a list for freeing up. */
1895
1896         list->objects = newObjects;
1897         list->next = dev->allocatedObjectList;
1898         dev->allocatedObjectList = list;
1899
1900         return YAFFS_OK;
1901 }
1902
1903
1904 /* AllocateEmptyObject gets us a clean Object. Tries to make allocate more if we run out */
1905 static yaffs_Object *yaffs_AllocateEmptyObject(yaffs_Device * dev)
1906 {
1907         yaffs_Object *tn = NULL;
1908
1909 #ifdef VALGRIND_TEST
1910         tn = YMALLOC(sizeof(yaffs_Object));
1911 #else
1912         /* If there are none left make more */
1913         if (!dev->freeObjects) {
1914                 yaffs_CreateFreeObjects(dev, YAFFS_ALLOCATION_NOBJECTS);
1915         }
1916
1917         if (dev->freeObjects) {
1918                 tn = dev->freeObjects;
1919                 dev->freeObjects =
1920                     (yaffs_Object *) (dev->freeObjects->siblings.next);
1921                 dev->nFreeObjects--;
1922         }
1923 #endif
1924         if(tn){
1925                 /* Now sweeten it up... */
1926
1927                 memset(tn, 0, sizeof(yaffs_Object));
1928                 tn->myDev = dev;
1929                 tn->hdrChunk = 0;
1930                 tn->variantType = YAFFS_OBJECT_TYPE_UNKNOWN;
1931                 YINIT_LIST_HEAD(&(tn->hardLinks));
1932                 YINIT_LIST_HEAD(&(tn->hashLink));
1933                 YINIT_LIST_HEAD(&tn->siblings);
1934
1935
1936                 /* Now make the directory sane */
1937                 if(dev->rootDir){
1938                         tn->parent = dev->rootDir;
1939                         ylist_add(&(tn->siblings),&dev->rootDir->variant.directoryVariant.children);
1940                 }
1941
1942                 /* Add it to the lost and found directory.
1943                  * NB Can't put root or lostNFound in lostNFound so
1944                  * check if lostNFound exists first
1945                  */
1946                 if (dev->lostNFoundDir) {
1947                         yaffs_AddObjectToDirectory(dev->lostNFoundDir, tn);
1948                 }
1949         }
1950
1951         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
1952
1953         return tn;
1954 }
1955
1956 static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device * dev, int number,
1957                                                __u32 mode)
1958 {
1959
1960         yaffs_Object *obj =
1961             yaffs_CreateNewObject(dev, number, YAFFS_OBJECT_TYPE_DIRECTORY);
1962         if (obj) {
1963                 obj->fake = 1;          /* it is fake so it might have no NAND presence... */
1964                 obj->renameAllowed = 0; /* ... and we're not allowed to rename it... */
1965                 obj->unlinkAllowed = 0; /* ... or unlink it */
1966                 obj->deleted = 0;
1967                 obj->unlinked = 0;
1968                 obj->yst_mode = mode;
1969                 obj->myDev = dev;
1970                 obj->hdrChunk = 0;      /* Not a valid chunk. */
1971         }
1972
1973         return obj;
1974
1975 }
1976
1977 static void yaffs_UnhashObject(yaffs_Object * tn)
1978 {
1979         int bucket;
1980         yaffs_Device *dev = tn->myDev;
1981
1982         /* If it is still linked into the bucket list, free from the list */
1983         if (!ylist_empty(&tn->hashLink)) {
1984                 ylist_del_init(&tn->hashLink);
1985                 bucket = yaffs_HashFunction(tn->objectId);
1986                 dev->objectBucket[bucket].count--;
1987         }
1988
1989 }
1990
1991 /*  FreeObject frees up a Object and puts it back on the free list */
1992 static void yaffs_FreeObject(yaffs_Object * tn)
1993 {
1994
1995         yaffs_Device *dev = tn->myDev;
1996
1997
1998         if(tn->parent)
1999                 YBUG();
2000         if(!ylist_empty(&tn->siblings))
2001                 YBUG();
2002
2003
2004 #ifdef  __KERNEL__
2005         if (tn->myInode) {
2006                 /* We're still hooked up to a cached inode.
2007                  * Don't delete now, but mark for later deletion
2008                  */
2009                 tn->deferedFree = 1;
2010                 return;
2011         }
2012 #endif
2013
2014         yaffs_UnhashObject(tn);
2015
2016 #ifdef VALGRIND_TEST
2017         YFREE(tn);
2018 #else
2019         /* Link into the free list. */
2020         tn->siblings.next = (struct ylist_head *)(dev->freeObjects);
2021         dev->freeObjects = tn;
2022         dev->nFreeObjects++;
2023 #endif
2024         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
2025
2026 }
2027
2028 #ifdef __KERNEL__
2029
2030 void yaffs_HandleDeferedFree(yaffs_Object * obj)
2031 {
2032         if (obj->deferedFree) {
2033                 yaffs_FreeObject(obj);
2034         }
2035 }
2036
2037 #endif
2038
2039 static void yaffs_DeinitialiseObjects(yaffs_Device * dev)
2040 {
2041         /* Free the list of allocated Objects */
2042
2043         yaffs_ObjectList *tmp;
2044
2045         while (dev->allocatedObjectList) {
2046                 tmp = dev->allocatedObjectList->next;
2047                 YFREE(dev->allocatedObjectList->objects);
2048                 YFREE(dev->allocatedObjectList);
2049
2050                 dev->allocatedObjectList = tmp;
2051         }
2052
2053         dev->freeObjects = NULL;
2054         dev->nFreeObjects = 0;
2055 }
2056
2057 static void yaffs_InitialiseObjects(yaffs_Device * dev)
2058 {
2059         int i;
2060
2061         dev->allocatedObjectList = NULL;
2062         dev->freeObjects = NULL;
2063         dev->nFreeObjects = 0;
2064
2065         for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) {
2066                 YINIT_LIST_HEAD(&dev->objectBucket[i].list);
2067                 dev->objectBucket[i].count = 0;
2068         }
2069
2070 }
2071
2072 static int yaffs_FindNiceObjectBucket(yaffs_Device * dev)
2073 {
2074         static int x = 0;
2075         int i;
2076         int l = 999;
2077         int lowest = 999999;
2078
2079         /* First let's see if we can find one that's empty. */
2080
2081         for (i = 0; i < 10 && lowest > 0; i++) {
2082                 x++;
2083                 x %= YAFFS_NOBJECT_BUCKETS;
2084                 if (dev->objectBucket[x].count < lowest) {
2085                         lowest = dev->objectBucket[x].count;
2086                         l = x;
2087                 }
2088
2089         }
2090
2091         /* If we didn't find an empty list, then try
2092          * looking a bit further for a short one
2093          */
2094
2095         for (i = 0; i < 10 && lowest > 3; i++) {
2096                 x++;
2097                 x %= YAFFS_NOBJECT_BUCKETS;
2098                 if (dev->objectBucket[x].count < lowest) {
2099                         lowest = dev->objectBucket[x].count;
2100                         l = x;
2101                 }
2102
2103         }
2104
2105         return l;
2106 }
2107
2108 static int yaffs_CreateNewObjectNumber(yaffs_Device * dev)
2109 {
2110         int bucket = yaffs_FindNiceObjectBucket(dev);
2111
2112         /* Now find an object value that has not already been taken
2113          * by scanning the list.
2114          */
2115
2116         int found = 0;
2117         struct ylist_head *i;
2118
2119         __u32 n = (__u32) bucket;
2120
2121         /* yaffs_CheckObjectHashSanity();  */
2122
2123         while (!found) {
2124                 found = 1;
2125                 n += YAFFS_NOBJECT_BUCKETS;
2126                 if (1 || dev->objectBucket[bucket].count > 0) {
2127                         ylist_for_each(i, &dev->objectBucket[bucket].list) {
2128                                 /* If there is already one in the list */
2129                                 if (i
2130                                     && ylist_entry(i, yaffs_Object,
2131                                                   hashLink)->objectId == n) {
2132                                         found = 0;
2133                                 }
2134                         }
2135                 }
2136         }
2137
2138
2139         return n;
2140 }
2141
2142 static void yaffs_HashObject(yaffs_Object * in)
2143 {
2144         int bucket = yaffs_HashFunction(in->objectId);
2145         yaffs_Device *dev = in->myDev;
2146
2147         ylist_add(&in->hashLink, &dev->objectBucket[bucket].list);
2148         dev->objectBucket[bucket].count++;
2149
2150 }
2151
2152 yaffs_Object *yaffs_FindObjectByNumber(yaffs_Device * dev, __u32 number)
2153 {
2154         int bucket = yaffs_HashFunction(number);
2155         struct ylist_head *i;
2156         yaffs_Object *in;
2157
2158         ylist_for_each(i, &dev->objectBucket[bucket].list) {
2159                 /* Look if it is in the list */
2160                 if (i) {
2161                         in = ylist_entry(i, yaffs_Object, hashLink);
2162                         if (in->objectId == number) {
2163 #ifdef __KERNEL__
2164                                 /* Don't tell the VFS about this one if it is defered free */
2165                                 if (in->deferedFree)
2166                                         return NULL;
2167 #endif
2168
2169                                 return in;
2170                         }
2171                 }
2172         }
2173
2174         return NULL;
2175 }
2176
2177 yaffs_Object *yaffs_CreateNewObject(yaffs_Device * dev, int number,
2178                                     yaffs_ObjectType type)
2179 {
2180
2181         yaffs_Object *theObject;
2182         yaffs_Tnode *tn = NULL;
2183
2184         if (number < 0) {
2185                 number = yaffs_CreateNewObjectNumber(dev);
2186         }
2187
2188         theObject = yaffs_AllocateEmptyObject(dev);
2189         if(!theObject)
2190                 return NULL;
2191
2192         if(type == YAFFS_OBJECT_TYPE_FILE){
2193                 tn = yaffs_GetTnode(dev);
2194                 if(!tn){
2195                         yaffs_FreeObject(theObject);
2196                         return NULL;
2197                 }
2198         }
2199
2200
2201
2202         if (theObject) {
2203                 theObject->fake = 0;
2204                 theObject->renameAllowed = 1;
2205                 theObject->unlinkAllowed = 1;
2206                 theObject->objectId = number;
2207                 yaffs_HashObject(theObject);
2208                 theObject->variantType = type;
2209 #ifdef CONFIG_YAFFS_WINCE
2210                 yfsd_WinFileTimeNow(theObject->win_atime);
2211                 theObject->win_ctime[0] = theObject->win_mtime[0] =
2212                     theObject->win_atime[0];
2213                 theObject->win_ctime[1] = theObject->win_mtime[1] =
2214                     theObject->win_atime[1];
2215
2216 #else
2217
2218                 theObject->yst_atime = theObject->yst_mtime =
2219                     theObject->yst_ctime = Y_CURRENT_TIME;
2220 #endif
2221
2222 #if 0
2223                 theObject->sum_prev = 12345;
2224                 theObject->sum_trailer = 6789;
2225 #endif
2226
2227                 switch (type) {
2228                 case YAFFS_OBJECT_TYPE_FILE:
2229                         theObject->variant.fileVariant.fileSize = 0;
2230                         theObject->variant.fileVariant.scannedFileSize = 0;
2231                         theObject->variant.fileVariant.shrinkSize = 0xFFFFFFFF; /* max __u32 */
2232                         theObject->variant.fileVariant.topLevel = 0;
2233                         theObject->variant.fileVariant.top = tn;
2234                         break;
2235                 case YAFFS_OBJECT_TYPE_DIRECTORY:
2236                         YINIT_LIST_HEAD(&theObject->variant.directoryVariant.
2237                                        children);
2238                         break;
2239                 case YAFFS_OBJECT_TYPE_SYMLINK:
2240                 case YAFFS_OBJECT_TYPE_HARDLINK:
2241                 case YAFFS_OBJECT_TYPE_SPECIAL:
2242                         /* No action required */
2243                         break;
2244                 case YAFFS_OBJECT_TYPE_UNKNOWN:
2245                         /* todo this should not happen */
2246                         break;
2247                 }
2248         }
2249
2250         return theObject;
2251 }
2252
2253 static yaffs_Object *yaffs_FindOrCreateObjectByNumber(yaffs_Device * dev,
2254                                                       int number,
2255                                                       yaffs_ObjectType type)
2256 {
2257         yaffs_Object *theObject = NULL;
2258
2259         if (number > 0) {
2260                 theObject = yaffs_FindObjectByNumber(dev, number);
2261         }
2262
2263         if (!theObject) {
2264                 theObject = yaffs_CreateNewObject(dev, number, type);
2265         }
2266
2267         return theObject;
2268
2269 }
2270
2271
2272 static YCHAR *yaffs_CloneString(const YCHAR * str)
2273 {
2274         YCHAR *newStr = NULL;
2275
2276         if (str && *str) {
2277                 newStr = YMALLOC((yaffs_strlen(str) + 1) * sizeof(YCHAR));
2278                 if(newStr)
2279                         yaffs_strcpy(newStr, str);
2280         }
2281
2282         return newStr;
2283
2284 }
2285
2286 /*
2287  * Mknod (create) a new object.
2288  * equivalentObject only has meaning for a hard link;
2289  * aliasString only has meaning for a sumlink.
2290  * rdev only has meaning for devices (a subset of special objects)
2291  */
2292
2293 static yaffs_Object *yaffs_MknodObject(yaffs_ObjectType type,
2294                                        yaffs_Object * parent,
2295                                        const YCHAR * name,
2296                                        __u32 mode,
2297                                        __u32 uid,
2298                                        __u32 gid,
2299                                        yaffs_Object * equivalentObject,
2300                                        const YCHAR * aliasString, __u32 rdev)
2301 {
2302         yaffs_Object *in;
2303         YCHAR *str = NULL;
2304
2305         yaffs_Device *dev = parent->myDev;
2306
2307         /* Check if the entry exists. If it does then fail the call since we don't want a dup.*/
2308         if (yaffs_FindObjectByName(parent, name)) {
2309                 return NULL;
2310         }
2311
2312         in = yaffs_CreateNewObject(dev, -1, type);
2313
2314         if(!in)
2315                 return YAFFS_FAIL;
2316
2317         if(type == YAFFS_OBJECT_TYPE_SYMLINK){
2318                 str = yaffs_CloneString(aliasString);
2319                 if(!str){
2320                         yaffs_FreeObject(in);
2321                         return NULL;
2322                 }
2323         }
2324
2325
2326
2327         if (in) {
2328                 in->hdrChunk = 0;
2329                 in->valid = 1;
2330                 in->variantType = type;
2331
2332                 in->yst_mode = mode;
2333
2334 #ifdef CONFIG_YAFFS_WINCE
2335                 yfsd_WinFileTimeNow(in->win_atime);
2336                 in->win_ctime[0] = in->win_mtime[0] = in->win_atime[0];
2337                 in->win_ctime[1] = in->win_mtime[1] = in->win_atime[1];
2338
2339 #else
2340                 in->yst_atime = in->yst_mtime = in->yst_ctime = Y_CURRENT_TIME;
2341
2342                 in->yst_rdev = rdev;
2343                 in->yst_uid = uid;
2344                 in->yst_gid = gid;
2345 #endif
2346                 in->nDataChunks = 0;
2347
2348                 yaffs_SetObjectName(in, name);
2349                 in->dirty = 1;
2350
2351                 yaffs_AddObjectToDirectory(parent, in);
2352
2353                 in->myDev = parent->myDev;
2354
2355                 switch (type) {
2356                 case YAFFS_OBJECT_TYPE_SYMLINK:
2357                         in->variant.symLinkVariant.alias = str;
2358                         break;
2359                 case YAFFS_OBJECT_TYPE_HARDLINK:
2360                         in->variant.hardLinkVariant.equivalentObject =
2361                             equivalentObject;
2362                         in->variant.hardLinkVariant.equivalentObjectId =
2363                             equivalentObject->objectId;
2364                         ylist_add(&in->hardLinks, &equivalentObject->hardLinks);
2365                         break;
2366                 case YAFFS_OBJECT_TYPE_FILE:
2367                 case YAFFS_OBJECT_TYPE_DIRECTORY:
2368                 case YAFFS_OBJECT_TYPE_SPECIAL:
2369                 case YAFFS_OBJECT_TYPE_UNKNOWN:
2370                         /* do nothing */
2371                         break;
2372                 }
2373
2374                 if (yaffs_UpdateObjectHeader(in, name, 0, 0, 0) < 0) {
2375                         /* Could not create the object header, fail the creation */
2376                         yaffs_DestroyObject(in);
2377                         in = NULL;
2378                 }
2379
2380         }
2381
2382         return in;
2383 }
2384
2385 yaffs_Object *yaffs_MknodFile(yaffs_Object * parent, const YCHAR * name,
2386                               __u32 mode, __u32 uid, __u32 gid)
2387 {
2388         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_FILE, parent, name, mode,
2389                                  uid, gid, NULL, NULL, 0);
2390 }
2391
2392 yaffs_Object *yaffs_MknodDirectory(yaffs_Object * parent, const YCHAR * name,
2393                                    __u32 mode, __u32 uid, __u32 gid)
2394 {
2395         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_DIRECTORY, parent, name,
2396                                  mode, uid, gid, NULL, NULL, 0);
2397 }
2398
2399 yaffs_Object *yaffs_MknodSpecial(yaffs_Object * parent, const YCHAR * name,
2400                                  __u32 mode, __u32 uid, __u32 gid, __u32 rdev)
2401 {
2402         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SPECIAL, parent, name, mode,
2403                                  uid, gid, NULL, NULL, rdev);
2404 }
2405
2406 yaffs_Object *yaffs_MknodSymLink(yaffs_Object * parent, const YCHAR * name,
2407                                  __u32 mode, __u32 uid, __u32 gid,
2408                                  const YCHAR * alias)
2409 {
2410         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SYMLINK, parent, name, mode,
2411                                  uid, gid, NULL, alias, 0);
2412 }
2413
2414 /* yaffs_Link returns the object id of the equivalent object.*/
2415 yaffs_Object *yaffs_Link(yaffs_Object * parent, const YCHAR * name,
2416                          yaffs_Object * equivalentObject)
2417 {
2418         /* Get the real object in case we were fed a hard link as an equivalent object */
2419         equivalentObject = yaffs_GetEquivalentObject(equivalentObject);
2420
2421         if (yaffs_MknodObject
2422             (YAFFS_OBJECT_TYPE_HARDLINK, parent, name, 0, 0, 0,
2423              equivalentObject, NULL, 0)) {
2424                 return equivalentObject;
2425         } else {
2426                 return NULL;
2427         }
2428
2429 }
2430
2431 static int yaffs_ChangeObjectName(yaffs_Object * obj, yaffs_Object * newDir,
2432                                   const YCHAR * newName, int force, int shadows)
2433 {
2434         int unlinkOp;
2435         int deleteOp;
2436
2437         yaffs_Object *existingTarget;
2438
2439         if (newDir == NULL) {
2440                 newDir = obj->parent;   /* use the old directory */
2441         }
2442
2443         if (newDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
2444                 T(YAFFS_TRACE_ALWAYS,
2445                   (TSTR
2446                    ("tragedy: yaffs_ChangeObjectName: newDir is not a directory"
2447                     TENDSTR)));
2448                 YBUG();
2449         }
2450
2451         /* TODO: Do we need this different handling for YAFFS2 and YAFFS1?? */
2452         if (obj->myDev->isYaffs2) {
2453                 unlinkOp = (newDir == obj->myDev->unlinkedDir);
2454         } else {
2455                 unlinkOp = (newDir == obj->myDev->unlinkedDir
2456                             && obj->variantType == YAFFS_OBJECT_TYPE_FILE);
2457         }
2458
2459         deleteOp = (newDir == obj->myDev->deletedDir);
2460
2461         existingTarget = yaffs_FindObjectByName(newDir, newName);
2462
2463         /* If the object is a file going into the unlinked directory,
2464          *   then it is OK to just stuff it in since duplicate names are allowed.
2465          *   else only proceed if the new name does not exist and if we're putting
2466          *   it into a directory.
2467          */
2468         if ((unlinkOp ||
2469              deleteOp ||
2470              force ||
2471              (shadows > 0) ||
2472              !existingTarget) &&
2473             newDir->variantType == YAFFS_OBJECT_TYPE_DIRECTORY) {
2474                 yaffs_SetObjectName(obj, newName);
2475                 obj->dirty = 1;
2476
2477                 yaffs_AddObjectToDirectory(newDir, obj);
2478
2479                 if (unlinkOp)
2480                         obj->unlinked = 1;
2481
2482                 /* If it is a deletion then we mark it as a shrink for gc purposes. */
2483                 if (yaffs_UpdateObjectHeader(obj, newName, 0, deleteOp, shadows)>= 0)
2484                         return YAFFS_OK;
2485         }
2486
2487         return YAFFS_FAIL;
2488 }
2489
2490 int yaffs_RenameObject(yaffs_Object * oldDir, const YCHAR * oldName,
2491                        yaffs_Object * newDir, const YCHAR * newName)
2492 {
2493         yaffs_Object *obj=NULL;
2494         yaffs_Object *existingTarget=NULL;
2495         int force = 0;
2496
2497
2498         if(!oldDir || oldDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
2499                 YBUG();
2500         if(!newDir || newDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
2501                 YBUG();
2502
2503 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
2504         /* Special case for case insemsitive systems (eg. WinCE).
2505          * While look-up is case insensitive, the name isn't.
2506          * Therefore we might want to change x.txt to X.txt
2507         */
2508         if (oldDir == newDir && yaffs_strcmp(oldName, newName) == 0) {
2509                 force = 1;
2510         }
2511 #endif
2512
2513         else if (yaffs_strlen(newName) > YAFFS_MAX_NAME_LENGTH)
2514           /* ENAMETOOLONG */
2515           return YAFFS_FAIL;
2516
2517         obj = yaffs_FindObjectByName(oldDir, oldName);
2518
2519         if (obj && obj->renameAllowed) {
2520
2521                 /* Now do the handling for an existing target, if there is one */
2522
2523                 existingTarget = yaffs_FindObjectByName(newDir, newName);
2524                 if (existingTarget &&
2525                     existingTarget->variantType == YAFFS_OBJECT_TYPE_DIRECTORY &&
2526                     !ylist_empty(&existingTarget->variant.directoryVariant.children)) {
2527                         /* There is a target that is a non-empty directory, so we fail */
2528                         return YAFFS_FAIL;      /* EEXIST or ENOTEMPTY */
2529                 } else if (existingTarget && existingTarget != obj) {
2530                         /* Nuke the target first, using shadowing,
2531                          * but only if it isn't the same object
2532                          */
2533                         yaffs_ChangeObjectName(obj, newDir, newName, force,
2534                                                existingTarget->objectId);
2535                         yaffs_UnlinkObject(existingTarget);
2536                 }
2537
2538                 return yaffs_ChangeObjectName(obj, newDir, newName, 1, 0);
2539         }
2540         return YAFFS_FAIL;
2541 }
2542
2543 /*------------------------- Block Management and Page Allocation ----------------*/
2544
2545 static int yaffs_InitialiseBlocks(yaffs_Device * dev)
2546 {
2547         int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
2548
2549         dev->blockInfo = NULL;
2550         dev->chunkBits = NULL;
2551
2552         dev->allocationBlock = -1;      /* force it to get a new one */
2553
2554         /* If the first allocation strategy fails, thry the alternate one */
2555         dev->blockInfo = YMALLOC(nBlocks * sizeof(yaffs_BlockInfo));
2556         if(!dev->blockInfo){
2557                 dev->blockInfo = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockInfo));
2558                 dev->blockInfoAlt = 1;
2559         }
2560         else
2561                 dev->blockInfoAlt = 0;
2562
2563         if(dev->blockInfo){
2564
2565                 /* Set up dynamic blockinfo stuff. */
2566                 dev->chunkBitmapStride = (dev->nChunksPerBlock + 7) / 8; /* round up bytes */
2567                 dev->chunkBits = YMALLOC(dev->chunkBitmapStride * nBlocks);
2568                 if(!dev->chunkBits){
2569                         dev->chunkBits = YMALLOC_ALT(dev->chunkBitmapStride * nBlocks);
2570                         dev->chunkBitsAlt = 1;
2571                 }
2572                 else
2573                         dev->chunkBitsAlt = 0;
2574         }
2575
2576         if (dev->blockInfo && dev->chunkBits) {
2577                 memset(dev->blockInfo, 0, nBlocks * sizeof(yaffs_BlockInfo));
2578                 memset(dev->chunkBits, 0, dev->chunkBitmapStride * nBlocks);
2579                 return YAFFS_OK;
2580         }
2581
2582         return YAFFS_FAIL;
2583
2584 }
2585
2586 static void yaffs_DeinitialiseBlocks(yaffs_Device * dev)
2587 {
2588         if(dev->blockInfoAlt && dev->blockInfo)
2589                 YFREE_ALT(dev->blockInfo);
2590         else if(dev->blockInfo)
2591                 YFREE(dev->blockInfo);
2592
2593         dev->blockInfoAlt = 0;
2594
2595         dev->blockInfo = NULL;
2596
2597         if(dev->chunkBitsAlt && dev->chunkBits)
2598                 YFREE_ALT(dev->chunkBits);
2599         else if(dev->chunkBits)
2600                 YFREE(dev->chunkBits);
2601         dev->chunkBitsAlt = 0;
2602         dev->chunkBits = NULL;
2603 }
2604
2605 static int yaffs_BlockNotDisqualifiedFromGC(yaffs_Device * dev,
2606                                             yaffs_BlockInfo * bi)
2607 {
2608         int i;
2609         __u32 seq;
2610         yaffs_BlockInfo *b;
2611
2612         if (!dev->isYaffs2)
2613                 return 1;       /* disqualification only applies to yaffs2. */
2614
2615         if (!bi->hasShrinkHeader)
2616                 return 1;       /* can gc */
2617
2618         /* Find the oldest dirty sequence number if we don't know it and save it
2619          * so we don't have to keep recomputing it.
2620          */
2621         if (!dev->oldestDirtySequence) {
2622                 seq = dev->sequenceNumber;
2623
2624                 for (i = dev->internalStartBlock; i <= dev->internalEndBlock;
2625                      i++) {
2626                         b = yaffs_GetBlockInfo(dev, i);
2627                         if (b->blockState == YAFFS_BLOCK_STATE_FULL &&
2628                             (b->pagesInUse - b->softDeletions) <
2629                             dev->nChunksPerBlock && b->sequenceNumber < seq) {
2630                                 seq = b->sequenceNumber;
2631                         }
2632                 }
2633                 dev->oldestDirtySequence = seq;
2634         }
2635
2636         /* Can't do gc of this block if there are any blocks older than this one that have
2637          * discarded pages.
2638          */
2639         return (bi->sequenceNumber <= dev->oldestDirtySequence);
2640
2641 }
2642
2643 /* FindDiretiestBlock is used to select the dirtiest block (or close enough)
2644  * for garbage collection.
2645  */
2646
2647 static int yaffs_FindBlockForGarbageCollection(yaffs_Device * dev,
2648                                                int aggressive)
2649 {
2650
2651         int b = dev->currentDirtyChecker;
2652
2653         int i;
2654         int iterations;
2655         int dirtiest = -1;
2656         int pagesInUse = 0;
2657         int prioritised=0;
2658         yaffs_BlockInfo *bi;
2659         int pendingPrioritisedExist = 0;
2660
2661         /* First let's see if we need to grab a prioritised block */
2662         if(dev->hasPendingPrioritisedGCs){
2663                 for(i = dev->internalStartBlock; i < dev->internalEndBlock && !prioritised; i++){
2664
2665                         bi = yaffs_GetBlockInfo(dev, i);
2666                         //yaffs_VerifyBlock(dev,bi,i);
2667
2668                         if(bi->gcPrioritise) {
2669                                 pendingPrioritisedExist = 1;
2670                                 if(bi->blockState == YAFFS_BLOCK_STATE_FULL &&
2671                                    yaffs_BlockNotDisqualifiedFromGC(dev, bi)){
2672                                         pagesInUse = (bi->pagesInUse - bi->softDeletions);
2673                                         dirtiest = i;
2674                                         prioritised = 1;
2675                                         aggressive = 1; /* Fool the non-aggressive skip logiv below */
2676                                 }
2677                         }
2678                 }
2679
2680                 if(!pendingPrioritisedExist) /* None found, so we can clear this */
2681                         dev->hasPendingPrioritisedGCs = 0;
2682         }
2683
2684         /* If we're doing aggressive GC then we are happy to take a less-dirty block, and
2685          * search harder.
2686          * else (we're doing a leasurely gc), then we only bother to do this if the
2687          * block has only a few pages in use.
2688          */
2689
2690         dev->nonAggressiveSkip--;
2691
2692         if (!aggressive && (dev->nonAggressiveSkip > 0)) {
2693                 return -1;
2694         }
2695
2696         if(!prioritised)
2697                 pagesInUse =
2698                         (aggressive) ? dev->nChunksPerBlock : YAFFS_PASSIVE_GC_CHUNKS + 1;
2699
2700         if (aggressive) {
2701                 iterations =
2702                     dev->internalEndBlock - dev->internalStartBlock + 1;
2703         } else {
2704                 iterations =
2705                     dev->internalEndBlock - dev->internalStartBlock + 1;
2706                 iterations = iterations / 16;
2707                 if (iterations > 200) {
2708                         iterations = 200;
2709                 }
2710         }
2711
2712         for (i = 0; i <= iterations && pagesInUse > 0 && !prioritised; i++) {
2713                 b++;
2714                 if (b < dev->internalStartBlock || b > dev->internalEndBlock) {
2715                         b = dev->internalStartBlock;
2716                 }
2717
2718                 if (b < dev->internalStartBlock || b > dev->internalEndBlock) {
2719                         T(YAFFS_TRACE_ERROR,
2720                           (TSTR("**>> Block %d is not valid" TENDSTR), b));
2721                         YBUG();
2722                 }
2723
2724                 bi = yaffs_GetBlockInfo(dev, b);
2725
2726 #if 0
2727                 if (bi->blockState == YAFFS_BLOCK_STATE_CHECKPOINT) {
2728                         dirtiest = b;
2729                         pagesInUse = 0;
2730                 }
2731                 else
2732 #endif
2733
2734                 if (bi->blockState == YAFFS_BLOCK_STATE_FULL &&
2735                        (bi->pagesInUse - bi->softDeletions) < pagesInUse &&
2736                         yaffs_BlockNotDisqualifiedFromGC(dev, bi)) {
2737                         dirtiest = b;
2738                         pagesInUse = (bi->pagesInUse - bi->softDeletions);
2739                 }
2740         }
2741
2742         dev->currentDirtyChecker = b;
2743
2744         if (dirtiest > 0) {
2745                 T(YAFFS_TRACE_GC,
2746                   (TSTR("GC Selected block %d with %d free, prioritised:%d" TENDSTR), dirtiest,
2747                    dev->nChunksPerBlock - pagesInUse,prioritised));
2748         }
2749
2750         dev->oldestDirtySequence = 0;
2751
2752         if (dirtiest > 0) {
2753                 dev->nonAggressiveSkip = 4;
2754         }
2755
2756         return dirtiest;
2757 }
2758
2759 static void yaffs_BlockBecameDirty(yaffs_Device * dev, int blockNo)
2760 {
2761         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockNo);
2762
2763         int erasedOk = 0;
2764
2765         /* If the block is still healthy erase it and mark as clean.
2766          * If the block has had a data failure, then retire it.
2767          */
2768
2769         T(YAFFS_TRACE_GC | YAFFS_TRACE_ERASE,
2770                 (TSTR("yaffs_BlockBecameDirty block %d state %d %s"TENDSTR),
2771                 blockNo, bi->blockState, (bi->needsRetiring) ? "needs retiring" : ""));
2772
2773         bi->blockState = YAFFS_BLOCK_STATE_DIRTY;
2774
2775         if (!bi->needsRetiring) {
2776                 yaffs_InvalidateCheckpoint(dev);
2777                 erasedOk = yaffs_EraseBlockInNAND(dev, blockNo);
2778                 if (!erasedOk) {
2779                         dev->nErasureFailures++;
2780                         T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
2781                           (TSTR("**>> Erasure failed %d" TENDSTR), blockNo));
2782                 }
2783         }
2784
2785         if (erasedOk &&
2786             ((yaffs_traceMask & YAFFS_TRACE_ERASE) || !yaffs_SkipVerification(dev))) {
2787                 int i;
2788                 for (i = 0; i < dev->nChunksPerBlock; i++) {
2789                         if (!yaffs_CheckChunkErased
2790                             (dev, blockNo * dev->nChunksPerBlock + i)) {
2791                                 T(YAFFS_TRACE_ERROR,
2792                                   (TSTR
2793                                    (">>Block %d erasure supposedly OK, but chunk %d not erased"
2794                                     TENDSTR), blockNo, i));
2795                         }
2796                 }
2797         }
2798
2799         if (erasedOk) {
2800                 /* Clean it up... */
2801                 bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
2802                 dev->nErasedBlocks++;
2803                 bi->pagesInUse = 0;
2804                 bi->softDeletions = 0;
2805                 bi->hasShrinkHeader = 0;
2806                 bi->skipErasedCheck = 1;  /* This is clean, so no need to check */
2807                 bi->gcPrioritise = 0;
2808                 yaffs_ClearChunkBits(dev, blockNo);
2809
2810                 T(YAFFS_TRACE_ERASE,
2811                   (TSTR("Erased block %d" TENDSTR), blockNo));
2812         } else {
2813                 dev->nFreeChunks -= dev->nChunksPerBlock;       /* We lost a block of free space */
2814
2815                 yaffs_RetireBlock(dev, blockNo);
2816                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
2817                   (TSTR("**>> Block %d retired" TENDSTR), blockNo));
2818         }
2819 }
2820
2821 static int yaffs_FindBlockForAllocation(yaffs_Device * dev)
2822 {
2823         int i;
2824
2825         yaffs_BlockInfo *bi;
2826
2827         if (dev->nErasedBlocks < 1) {
2828                 /* Hoosterman we've got a problem.
2829                  * Can't get space to gc
2830                  */
2831                 T(YAFFS_TRACE_ERROR,
2832                   (TSTR("yaffs tragedy: no more erased blocks" TENDSTR)));
2833
2834                 return -1;
2835         }
2836
2837         /* Find an empty block. */
2838
2839         for (i = dev->internalStartBlock; i <= dev->internalEndBlock; i++) {
2840                 dev->allocationBlockFinder++;
2841                 if (dev->allocationBlockFinder < dev->internalStartBlock
2842                     || dev->allocationBlockFinder > dev->internalEndBlock) {
2843                         dev->allocationBlockFinder = dev->internalStartBlock;
2844                 }
2845
2846                 bi = yaffs_GetBlockInfo(dev, dev->allocationBlockFinder);
2847
2848                 if (bi->blockState == YAFFS_BLOCK_STATE_EMPTY) {
2849                         bi->blockState = YAFFS_BLOCK_STATE_ALLOCATING;
2850                         dev->sequenceNumber++;
2851                         bi->sequenceNumber = dev->sequenceNumber;
2852                         dev->nErasedBlocks--;
2853                         T(YAFFS_TRACE_ALLOCATE,
2854                           (TSTR("Allocated block %d, seq  %d, %d left" TENDSTR),
2855                            dev->allocationBlockFinder, dev->sequenceNumber,
2856                            dev->nErasedBlocks));
2857                         return dev->allocationBlockFinder;
2858                 }
2859         }
2860
2861         T(YAFFS_TRACE_ALWAYS,
2862           (TSTR
2863            ("yaffs tragedy: no more erased blocks, but there should have been %d"
2864             TENDSTR), dev->nErasedBlocks));
2865
2866         return -1;
2867 }
2868
2869
2870
2871 static int yaffs_CalcCheckpointBlocksRequired(yaffs_Device *dev)
2872 {
2873         if(!dev->nCheckpointBlocksRequired &&
2874            dev->isYaffs2){
2875                 /* Not a valid value so recalculate */
2876                 int nBytes = 0;
2877                 int nBlocks;
2878                 int devBlocks = (dev->endBlock - dev->startBlock + 1);
2879                 int tnodeSize;
2880
2881                 tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
2882
2883                 if(tnodeSize < sizeof(yaffs_Tnode))
2884                         tnodeSize = sizeof(yaffs_Tnode);
2885
2886                 nBytes += sizeof(yaffs_CheckpointValidity);
2887                 nBytes += sizeof(yaffs_CheckpointDevice);
2888                 nBytes += devBlocks * sizeof(yaffs_BlockInfo);
2889                 nBytes += devBlocks * dev->chunkBitmapStride;
2890                 nBytes += (sizeof(yaffs_CheckpointObject) + sizeof(__u32)) * (dev->nObjectsCreated - dev->nFreeObjects);
2891                 nBytes += (tnodeSize + sizeof(__u32)) * (dev->nTnodesCreated - dev->nFreeTnodes);
2892                 nBytes += sizeof(yaffs_CheckpointValidity);
2893                 nBytes += sizeof(__u32); /* checksum*/
2894
2895                 /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
2896
2897                 nBlocks = (nBytes/(dev->nDataBytesPerChunk * dev->nChunksPerBlock)) + 3;
2898
2899                 dev->nCheckpointBlocksRequired = nBlocks;
2900         }
2901
2902         return dev->nCheckpointBlocksRequired;
2903 }
2904
2905 // Check if there's space to allocate...
2906 // Thinks.... do we need top make this ths same as yaffs_GetFreeChunks()?
2907 static int yaffs_CheckSpaceForAllocation(yaffs_Device * dev)
2908 {
2909         int reservedChunks;
2910         int reservedBlocks = dev->nReservedBlocks;
2911         int checkpointBlocks;
2912
2913         if(dev->isYaffs2){
2914                 checkpointBlocks =  yaffs_CalcCheckpointBlocksRequired(dev) -
2915                                     dev->blocksInCheckpoint;
2916                 if(checkpointBlocks < 0)
2917                         checkpointBlocks = 0;
2918         } else {
2919                 checkpointBlocks =0;
2920         }
2921
2922         reservedChunks = ((reservedBlocks + checkpointBlocks) * dev->nChunksPerBlock);
2923
2924         return (dev->nFreeChunks > reservedChunks);
2925 }
2926
2927 static int yaffs_AllocateChunk(yaffs_Device * dev, int useReserve, yaffs_BlockInfo **blockUsedPtr)
2928 {
2929         int retVal;
2930         yaffs_BlockInfo *bi;
2931
2932         if (dev->allocationBlock < 0) {
2933                 /* Get next block to allocate off */
2934                 dev->allocationBlock = yaffs_FindBlockForAllocation(dev);
2935                 dev->allocationPage = 0;
2936         }
2937
2938         if (!useReserve && !yaffs_CheckSpaceForAllocation(dev)) {
2939                 /* Not enough space to allocate unless we're allowed to use the reserve. */
2940                 return -1;
2941         }
2942
2943         if (dev->nErasedBlocks < dev->nReservedBlocks
2944             && dev->allocationPage == 0) {
2945                 T(YAFFS_TRACE_ALLOCATE, (TSTR("Allocating reserve" TENDSTR)));
2946         }
2947
2948         /* Next page please.... */
2949         if (dev->allocationBlock >= 0) {
2950                 bi = yaffs_GetBlockInfo(dev, dev->allocationBlock);
2951
2952                 retVal = (dev->allocationBlock * dev->nChunksPerBlock) +
2953                     dev->allocationPage;
2954                 bi->pagesInUse++;
2955                 yaffs_SetChunkBit(dev, dev->allocationBlock,
2956                                   dev->allocationPage);
2957
2958                 dev->allocationPage++;
2959
2960                 dev->nFreeChunks--;
2961
2962                 /* If the block is full set the state to full */
2963                 if (dev->allocationPage >= dev->nChunksPerBlock) {
2964                         bi->blockState = YAFFS_BLOCK_STATE_FULL;
2965                         dev->allocationBlock = -1;
2966                 }
2967
2968                 if(blockUsedPtr)
2969                         *blockUsedPtr = bi;
2970
2971                 return retVal;
2972         }
2973
2974         T(YAFFS_TRACE_ERROR,
2975           (TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));
2976
2977         return -1;
2978 }
2979
2980 static int yaffs_GetErasedChunks(yaffs_Device * dev)
2981 {
2982         int n;
2983
2984         n = dev->nErasedBlocks * dev->nChunksPerBlock;
2985
2986         if (dev->allocationBlock > 0) {
2987                 n += (dev->nChunksPerBlock - dev->allocationPage);
2988         }
2989
2990         return n;
2991
2992 }
2993
2994 static int yaffs_GarbageCollectBlock(yaffs_Device * dev, int block, int wholeBlock)
2995 {
2996         int oldChunk;
2997         int newChunk;
2998         int markNAND;
2999         int retVal = YAFFS_OK;
3000         int cleanups = 0;
3001         int i;
3002         int isCheckpointBlock;
3003         int matchingChunk;
3004         int maxCopies;
3005
3006         int chunksBefore = yaffs_GetErasedChunks(dev);
3007         int chunksAfter;
3008
3009         yaffs_ExtendedTags tags;
3010
3011         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, block);
3012
3013         yaffs_Object *object;
3014
3015         isCheckpointBlock = (bi->blockState == YAFFS_BLOCK_STATE_CHECKPOINT);
3016
3017         bi->blockState = YAFFS_BLOCK_STATE_COLLECTING;
3018
3019         T(YAFFS_TRACE_TRACING,
3020           (TSTR("Collecting block %d, in use %d, shrink %d, wholeBlock %d" TENDSTR),
3021           block,
3022           bi->pagesInUse,
3023           bi->hasShrinkHeader,
3024           wholeBlock));
3025
3026         /*yaffs_VerifyFreeChunks(dev); */
3027
3028         bi->hasShrinkHeader = 0;        /* clear the flag so that the block can erase */
3029
3030         /* Take off the number of soft deleted entries because
3031          * they're going to get really deleted during GC.
3032          */
3033         dev->nFreeChunks -= bi->softDeletions;
3034
3035         dev->isDoingGC = 1;
3036
3037         if (isCheckpointBlock ||
3038             !yaffs_StillSomeChunkBits(dev, block)) {
3039                 T(YAFFS_TRACE_TRACING,
3040                   (TSTR
3041                    ("Collecting block %d that has no chunks in use" TENDSTR),
3042                    block));
3043                 yaffs_BlockBecameDirty(dev, block);
3044         } else {
3045
3046                 __u8 *buffer = yaffs_GetTempBuffer(dev, __LINE__);
3047
3048                 yaffs_VerifyBlock(dev,bi,block);
3049
3050                 maxCopies = (wholeBlock) ? dev->nChunksPerBlock : 10;
3051                 oldChunk = block * dev->nChunksPerBlock + dev->gcChunk;
3052
3053                 for ( /* init already done */;
3054                      retVal == YAFFS_OK &&
3055                      dev->gcChunk < dev->nChunksPerBlock &&
3056                      (bi->blockState == YAFFS_BLOCK_STATE_COLLECTING)&&
3057                      maxCopies > 0;
3058                      dev->gcChunk++, oldChunk++) {
3059                         if (yaffs_CheckChunkBit(dev, block, dev->gcChunk)) {
3060
3061                                 /* This page is in use and might need to be copied off */
3062
3063                                 maxCopies--;
3064
3065                                 markNAND = 1;
3066
3067                                 yaffs_InitialiseTags(&tags);
3068
3069                                 yaffs_ReadChunkWithTagsFromNAND(dev, oldChunk,
3070                                                                 buffer, &tags);
3071
3072                                 object =
3073                                     yaffs_FindObjectByNumber(dev,
3074                                                              tags.objectId);
3075
3076                                 T(YAFFS_TRACE_GC_DETAIL,
3077                                   (TSTR
3078                                    ("Collecting chunk in block %d, %d %d %d " TENDSTR),
3079                                    dev->gcChunk, tags.objectId, tags.chunkId,
3080                                    tags.byteCount));
3081
3082                                 if(object && !yaffs_SkipVerification(dev)){
3083                                         if(tags.chunkId == 0)
3084                                                 matchingChunk = object->hdrChunk;
3085                                         else if(object->softDeleted)
3086                                                 matchingChunk = oldChunk; /* Defeat the test */
3087                                         else
3088                                                 matchingChunk = yaffs_FindChunkInFile(object,tags.chunkId,NULL);
3089
3090                                         if(oldChunk != matchingChunk)
3091                                                 T(YAFFS_TRACE_ERROR,
3092                                                   (TSTR("gc: page in gc mismatch: %d %d %d %d"TENDSTR),
3093                                                   oldChunk,matchingChunk,tags.objectId, tags.chunkId));
3094
3095                                 }
3096
3097                                 if (!object) {
3098                                         T(YAFFS_TRACE_ERROR,
3099                                           (TSTR
3100                                            ("page %d in gc has no object: %d %d %d "
3101                                             TENDSTR), oldChunk,
3102                                             tags.objectId, tags.chunkId, tags.byteCount));
3103                                 }
3104
3105                                 if (object &&
3106                                     object->deleted &&
3107                                     object->softDeleted &&
3108                                     tags.chunkId != 0) {
3109                                         /* Data chunk in a soft deleted file, throw it away
3110                                          * It's a soft deleted data chunk,
3111                                          * No need to copy this, just forget about it and
3112                                          * fix up the object.
3113                                          */
3114
3115                                         object->nDataChunks--;
3116
3117                                         if (object->nDataChunks <= 0) {
3118                                                 /* remeber to clean up the object */
3119                                                 dev->gcCleanupList[cleanups] =
3120                                                     tags.objectId;
3121                                                 cleanups++;
3122                                         }
3123                                         markNAND = 0;
3124                                 } else if (0
3125                                            /* Todo object && object->deleted && object->nDataChunks == 0 */
3126                                            ) {
3127                                         /* Deleted object header with no data chunks.
3128                                          * Can be discarded and the file deleted.
3129                                          */
3130                                         object->hdrChunk = 0;
3131                                         yaffs_FreeTnode(object->myDev,
3132                                                         object->variant.
3133                                                         fileVariant.top);
3134                                         object->variant.fileVariant.top = NULL;
3135                                         yaffs_DoGenericObjectDeletion(object);
3136
3137                                 } else if (object) {
3138                                         /* It's either a data chunk in a live file or
3139                                          * an ObjectHeader, so we're interested in it.
3140                                          * NB Need to keep the ObjectHeaders of deleted files
3141                                          * until the whole file has been deleted off
3142                                          */
3143                                         tags.serialNumber++;
3144
3145                                         dev->nGCCopies++;
3146
3147                                         if (tags.chunkId == 0) {
3148                                                 /* It is an object Id,
3149                                                  * We need to nuke the shrinkheader flags first
3150                                                  * We no longer want the shrinkHeader flag since its work is done
3151                                                  * and if it is left in place it will mess up scanning.
3152                                                  * Also, clear out any shadowing stuff
3153                                                  */
3154
3155                                                 yaffs_ObjectHeader *oh;
3156                                                 oh = (yaffs_ObjectHeader *)buffer;
3157                                                 oh->isShrink = 0;
3158                                                 tags.extraShadows = 0;
3159                                                 tags.extraIsShrinkHeader = 0;
3160
3161                                                 yaffs_VerifyObjectHeader(object,oh,&tags,1);
3162                                         }
3163
3164                                         newChunk =
3165                                             yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &tags, 1);
3166
3167                                         if (newChunk < 0) {
3168                                                 retVal = YAFFS_FAIL;
3169                                         } else {
3170
3171                                                 /* Ok, now fix up the Tnodes etc. */
3172
3173                                                 if (tags.chunkId == 0) {
3174                                                         /* It's a header */
3175                                                         object->hdrChunk =  newChunk;
3176                                                         object->serial =   tags.serialNumber;
3177                                                 } else {
3178                                                         /* It's a data chunk */
3179                                                         yaffs_PutChunkIntoFile
3180                                                             (object,
3181                                                              tags.chunkId,
3182                                                              newChunk, 0);
3183                                                 }
3184                                         }
3185                                 }
3186
3187                                 if(retVal == YAFFS_OK)
3188                                         yaffs_DeleteChunk(dev, oldChunk, markNAND, __LINE__);
3189
3190                         }
3191                 }
3192
3193                 yaffs_ReleaseTempBuffer(dev, buffer, __LINE__);
3194
3195
3196
3197                 /* Do any required cleanups */
3198                 for (i = 0; i < cleanups; i++) {
3199                         /* Time to delete the file too */
3200                         object =
3201                             yaffs_FindObjectByNumber(dev,
3202                                                      dev->gcCleanupList[i]);
3203                         if (object) {
3204                                 yaffs_FreeTnode(dev,
3205                                                 object->variant.fileVariant.
3206                                                 top);
3207                                 object->variant.fileVariant.top = NULL;
3208                                 T(YAFFS_TRACE_GC,
3209                                   (TSTR
3210                                    ("yaffs: About to finally delete object %d"
3211                                     TENDSTR), object->objectId));
3212                                 yaffs_DoGenericObjectDeletion(object);
3213                                 object->myDev->nDeletedFiles--;
3214                         }
3215
3216                 }
3217
3218         }
3219
3220         yaffs_VerifyCollectedBlock(dev,bi,block);
3221
3222         if (chunksBefore >= (chunksAfter = yaffs_GetErasedChunks(dev))) {
3223                 T(YAFFS_TRACE_GC,
3224                   (TSTR
3225                    ("gc did not increase free chunks before %d after %d"
3226                     TENDSTR), chunksBefore, chunksAfter));
3227         }
3228
3229         /* If the gc completed then clear the current gcBlock so that we find another. */
3230         if(bi->blockState != YAFFS_BLOCK_STATE_COLLECTING){
3231                 dev->gcBlock = -1;
3232                 dev->gcChunk = 0;
3233         }
3234
3235         dev->isDoingGC = 0;
3236
3237         return retVal;
3238 }
3239
3240 /* New garbage collector
3241  * If we're very low on erased blocks then we do aggressive garbage collection
3242  * otherwise we do "leasurely" garbage collection.
3243  * Aggressive gc looks further (whole array) and will accept less dirty blocks.
3244  * Passive gc only inspects smaller areas and will only accept more dirty blocks.
3245  *
3246  * The idea is to help clear out space in a more spread-out manner.
3247  * Dunno if it really does anything useful.
3248  */
3249 static int yaffs_CheckGarbageCollection(yaffs_Device * dev)
3250 {
3251         int block;
3252         int aggressive;
3253         int gcOk = YAFFS_OK;
3254         int maxTries = 0;
3255
3256         int checkpointBlockAdjust;
3257
3258         if (dev->isDoingGC) {
3259                 /* Bail out so we don't get recursive gc */
3260                 return YAFFS_OK;
3261         }
3262
3263         /* This loop should pass the first time.
3264          * We'll only see looping here if the erase of the collected block fails.
3265          */
3266
3267         do {
3268                 maxTries++;
3269
3270                 checkpointBlockAdjust = yaffs_CalcCheckpointBlocksRequired(dev) - dev->blocksInCheckpoint;
3271                 if(checkpointBlockAdjust < 0)
3272                         checkpointBlockAdjust = 0;
3273
3274                 if (dev->nErasedBlocks < (dev->nReservedBlocks + checkpointBlockAdjust + 2)) {
3275                         /* We need a block soon...*/
3276                         aggressive = 1;
3277                 } else {
3278                         /* We're in no hurry */
3279                         aggressive = 0;
3280                 }
3281
3282                 if(dev->gcBlock <= 0){
3283                         dev->gcBlock = yaffs_FindBlockForGarbageCollection(dev, aggressive);
3284                         dev->gcChunk = 0;
3285                 }
3286
3287                 block = dev->gcBlock;
3288
3289                 if (block > 0) {
3290                         dev->garbageCollections++;
3291                         if (!aggressive) {
3292                                 dev->passiveGarbageCollections++;
3293                         }
3294
3295                         T(YAFFS_TRACE_GC,
3296                           (TSTR
3297                            ("yaffs: GC erasedBlocks %d aggressive %d" TENDSTR),
3298                            dev->nErasedBlocks, aggressive));
3299
3300                         gcOk = yaffs_GarbageCollectBlock(dev,block,aggressive);
3301                 }
3302
3303                 if (dev->nErasedBlocks < (dev->nReservedBlocks) && block > 0) {
3304                         T(YAFFS_TRACE_GC,
3305                           (TSTR
3306                            ("yaffs: GC !!!no reclaim!!! erasedBlocks %d after try %d block %d"
3307                             TENDSTR), dev->nErasedBlocks, maxTries, block));
3308                 }
3309         } while ((dev->nErasedBlocks < dev->nReservedBlocks) &&
3310                  (block > 0) &&
3311                  (maxTries < 2));
3312
3313         return aggressive ? gcOk : YAFFS_OK;
3314 }
3315
3316 /*-------------------------  TAGS --------------------------------*/
3317
3318 static int yaffs_TagsMatch(const yaffs_ExtendedTags * tags, int objectId,
3319                            int chunkInObject)
3320 {
3321         return (tags->chunkId == chunkInObject &&
3322                 tags->objectId == objectId && !tags->chunkDeleted) ? 1 : 0;
3323
3324 }
3325
3326
3327 /*-------------------- Data file manipulation -----------------*/
3328
3329 static int yaffs_FindChunkInFile(yaffs_Object * in, int chunkInInode,
3330                                  yaffs_ExtendedTags * tags)
3331 {
3332         /*Get the Tnode, then get the level 0 offset chunk offset */
3333         yaffs_Tnode *tn;
3334         int theChunk = -1;
3335         yaffs_ExtendedTags localTags;
3336         int retVal = -1;
3337
3338         yaffs_Device *dev = in->myDev;
3339
3340         if (!tags) {
3341                 /* Passed a NULL, so use our own tags space */
3342                 tags = &localTags;
3343         }
3344
3345         tn = yaffs_FindLevel0Tnode(dev, &in->variant.fileVariant, chunkInInode);
3346
3347         if (tn) {
3348                 theChunk = yaffs_GetChunkGroupBase(dev,tn,chunkInInode);
3349
3350                 retVal =
3351                     yaffs_FindChunkInGroup(dev, theChunk, tags, in->objectId,
3352                                            chunkInInode);
3353         }
3354         return retVal;
3355 }
3356
3357 static int yaffs_FindAndDeleteChunkInFile(yaffs_Object * in, int chunkInInode,
3358                                           yaffs_ExtendedTags * tags)
3359 {
3360         /* Get the Tnode, then get the level 0 offset chunk offset */
3361         yaffs_Tnode *tn;
3362         int theChunk = -1;
3363         yaffs_ExtendedTags localTags;
3364
3365         yaffs_Device *dev = in->myDev;
3366         int retVal = -1;
3367
3368         if (!tags) {
3369                 /* Passed a NULL, so use our own tags space */
3370                 tags = &localTags;
3371         }
3372
3373         tn = yaffs_FindLevel0Tnode(dev, &in->variant.fileVariant, chunkInInode);
3374
3375         if (tn) {
3376
3377                 theChunk = yaffs_GetChunkGroupBase(dev,tn,chunkInInode);
3378
3379                 retVal =
3380                     yaffs_FindChunkInGroup(dev, theChunk, tags, in->objectId,
3381                                            chunkInInode);
3382
3383                 /* Delete the entry in the filestructure (if found) */
3384                 if (retVal != -1) {
3385                         yaffs_PutLevel0Tnode(dev,tn,chunkInInode,0);
3386                 }
3387         } else {
3388                 /*T(("No level 0 found for %d\n", chunkInInode)); */
3389         }
3390
3391         if (retVal == -1) {
3392                 /* T(("Could not find %d to delete\n",chunkInInode)); */
3393         }
3394         return retVal;
3395 }
3396
3397 #ifdef YAFFS_PARANOID
3398
3399 static int yaffs_CheckFileSanity(yaffs_Object * in)
3400 {
3401         int chunk;
3402         int nChunks;
3403         int fSize;
3404         int failed = 0;
3405         int objId;
3406         yaffs_Tnode *tn;
3407         yaffs_Tags localTags;
3408         yaffs_Tags *tags = &localTags;
3409         int theChunk;
3410         int chunkDeleted;
3411
3412         if (in->variantType != YAFFS_OBJECT_TYPE_FILE) {
3413                 /* T(("Object not a file\n")); */
3414                 return YAFFS_FAIL;
3415         }
3416
3417         objId = in->objectId;
3418         fSize = in->variant.fileVariant.fileSize;
3419         nChunks =
3420             (fSize + in->myDev->nDataBytesPerChunk - 1) / in->myDev->nDataBytesPerChunk;
3421
3422         for (chunk = 1; chunk <= nChunks; chunk++) {
3423                 tn = yaffs_FindLevel0Tnode(in->myDev, &in->variant.fileVariant,
3424                                            chunk);
3425
3426                 if (tn) {
3427
3428                         theChunk = yaffs_GetChunkGroupBase(dev,tn,chunk);
3429
3430                         if (yaffs_CheckChunkBits
3431                             (dev, theChunk / dev->nChunksPerBlock,
3432                              theChunk % dev->nChunksPerBlock)) {
3433
3434                                 yaffs_ReadChunkTagsFromNAND(in->myDev, theChunk,
3435                                                             tags,
3436                                                             &chunkDeleted);
3437                                 if (yaffs_TagsMatch
3438                                     (tags, in->objectId, chunk, chunkDeleted)) {
3439                                         /* found it; */
3440
3441                                 }
3442                         } else {
3443
3444                                 failed = 1;
3445                         }
3446
3447                 } else {
3448                         /* T(("No level 0 found for %d\n", chunk)); */
3449                 }
3450         }
3451
3452         return failed ? YAFFS_FAIL : YAFFS_OK;
3453 }
3454
3455 #endif
3456
3457 static int yaffs_PutChunkIntoFile(yaffs_Object * in, int chunkInInode,
3458                                   int chunkInNAND, int inScan)
3459 {
3460         /* NB inScan is zero unless scanning.
3461          * For forward scanning, inScan is > 0;
3462          * for backward scanning inScan is < 0
3463          */
3464
3465         yaffs_Tnode *tn;
3466         yaffs_Device *dev = in->myDev;
3467         int existingChunk;
3468         yaffs_ExtendedTags existingTags;
3469         yaffs_ExtendedTags newTags;
3470         unsigned existingSerial, newSerial;
3471
3472         if (in->variantType != YAFFS_OBJECT_TYPE_FILE) {
3473                 /* Just ignore an attempt at putting a chunk into a non-file during scanning
3474                  * If it is not during Scanning then something went wrong!
3475                  */
3476                 if (!inScan) {
3477                         T(YAFFS_TRACE_ERROR,
3478                           (TSTR
3479                            ("yaffs tragedy:attempt to put data chunk into a non-file"
3480                             TENDSTR)));
3481                         YBUG();
3482                 }
3483
3484                 yaffs_DeleteChunk(dev, chunkInNAND, 1, __LINE__);
3485                 return YAFFS_OK;
3486         }
3487
3488         tn = yaffs_AddOrFindLevel0Tnode(dev,
3489                                         &in->variant.fileVariant,
3490                                         chunkInInode,
3491                                         NULL);
3492         if (!tn) {
3493                 return YAFFS_FAIL;
3494         }
3495
3496         existingChunk = yaffs_GetChunkGroupBase(dev,tn,chunkInInode);
3497
3498         if (inScan != 0) {
3499                 /* If we're scanning then we need to test for duplicates
3500                  * NB This does not need to be efficient since it should only ever
3501                  * happen when the power fails during a write, then only one
3502                  * chunk should ever be affected.
3503                  *
3504                  * Correction for YAFFS2: This could happen quite a lot and we need to think about efficiency! TODO
3505                  * Update: For backward scanning we don't need to re-read tags so this is quite cheap.
3506                  */
3507
3508                 if (existingChunk > 0) {
3509                         /* NB Right now existing chunk will not be real chunkId if the device >= 32MB
3510                          *    thus we have to do a FindChunkInFile to get the real chunk id.
3511                          *
3512                          * We have a duplicate now we need to decide which one to use:
3513                          *
3514                          * Backwards scanning YAFFS2: The old one is what we use, dump the new one.
3515                          * Forward scanning YAFFS2: The new one is what we use, dump the old one.
3516                          * YAFFS1: Get both sets of tags and compare serial numbers.
3517                          */
3518
3519                         if (inScan > 0) {
3520                                 /* Only do this for forward scanning */
3521                                 yaffs_ReadChunkWithTagsFromNAND(dev,
3522                                                                 chunkInNAND,
3523                                                                 NULL, &newTags);
3524
3525                                 /* Do a proper find */
3526                                 existingChunk =
3527                                     yaffs_FindChunkInFile(in, chunkInInode,
3528                                                           &existingTags);
3529                         }
3530
3531                         if (existingChunk <= 0) {
3532                                 /*Hoosterman - how did this happen? */
3533
3534                                 T(YAFFS_TRACE_ERROR,
3535                                   (TSTR
3536                                    ("yaffs tragedy: existing chunk < 0 in scan"
3537                                     TENDSTR)));
3538
3539                         }
3540
3541                         /* NB The deleted flags should be false, otherwise the chunks will
3542                          * not be loaded during a scan
3543                          */
3544
3545                         if(inScan > 0) {
3546                                 newSerial = newTags.serialNumber;
3547                                 existingSerial = existingTags.serialNumber;
3548                         }
3549
3550                         if ((inScan > 0) &&
3551                             (in->myDev->isYaffs2 ||
3552                              existingChunk <= 0 ||
3553                              ((existingSerial + 1) & 3) == newSerial)) {
3554                                 /* Forward scanning.
3555                                  * Use new
3556                                  * Delete the old one and drop through to update the tnode
3557                                  */
3558                                 yaffs_DeleteChunk(dev, existingChunk, 1,
3559                                                   __LINE__);
3560                         } else {
3561                                 /* Backward scanning or we want to use the existing one
3562                                  * Use existing.
3563                                  * Delete the new one and return early so that the tnode isn't changed
3564                                  */
3565                                 yaffs_DeleteChunk(dev, chunkInNAND, 1,
3566                                                   __LINE__);
3567                                 return YAFFS_OK;
3568                         }
3569                 }
3570
3571         }
3572
3573         if (existingChunk == 0) {
3574                 in->nDataChunks++;
3575         }
3576
3577         yaffs_PutLevel0Tnode(dev,tn,chunkInInode,chunkInNAND);
3578
3579         return YAFFS_OK;
3580 }
3581
3582 static int yaffs_ReadChunkDataFromObject(yaffs_Object * in, int chunkInInode,
3583                                          __u8 * buffer)
3584 {
3585         int chunkInNAND = yaffs_FindChunkInFile(in, chunkInInode, NULL);
3586
3587         if (chunkInNAND >= 0) {
3588                 return yaffs_ReadChunkWithTagsFromNAND(in->myDev, chunkInNAND,
3589                                                        buffer,NULL);
3590         } else {
3591                 T(YAFFS_TRACE_NANDACCESS,
3592                   (TSTR("Chunk %d not found zero instead" TENDSTR),
3593                    chunkInNAND));
3594                 /* get sane (zero) data if you read a hole */
3595                 memset(buffer, 0, in->myDev->nDataBytesPerChunk);
3596                 return 0;
3597         }
3598
3599 }
3600
3601 void yaffs_DeleteChunk(yaffs_Device * dev, int chunkId, int markNAND, int lyn)
3602 {
3603         int block;
3604         int page;
3605         yaffs_ExtendedTags tags;
3606         yaffs_BlockInfo *bi;
3607
3608         if (chunkId <= 0)
3609                 return;
3610
3611
3612         dev->nDeletions++;
3613         block = chunkId / dev->nChunksPerBlock;
3614         page = chunkId % dev->nChunksPerBlock;
3615
3616
3617         if(!yaffs_CheckChunkBit(dev,block,page))
3618                 T(YAFFS_TRACE_VERIFY,
3619                         (TSTR("Deleting invalid chunk %d"TENDSTR),
3620                          chunkId));
3621
3622         bi = yaffs_GetBlockInfo(dev, block);
3623
3624         T(YAFFS_TRACE_DELETION,
3625           (TSTR("line %d delete of chunk %d" TENDSTR), lyn, chunkId));
3626
3627         if (markNAND &&
3628             bi->blockState != YAFFS_BLOCK_STATE_COLLECTING && !dev->isYaffs2) {
3629
3630                 yaffs_InitialiseTags(&tags);
3631
3632                 tags.chunkDeleted = 1;
3633
3634                 yaffs_WriteChunkWithTagsToNAND(dev, chunkId, NULL, &tags);
3635                 yaffs_HandleUpdateChunk(dev, chunkId, &tags);
3636         } else {
3637                 dev->nUnmarkedDeletions++;
3638         }
3639
3640         /* Pull out of the management area.
3641          * If the whole block became dirty, this will kick off an erasure.
3642          */
3643         if (bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING ||
3644             bi->blockState == YAFFS_BLOCK_STATE_FULL ||
3645             bi->blockState == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
3646             bi->blockState == YAFFS_BLOCK_STATE_COLLECTING) {
3647                 dev->nFreeChunks++;
3648
3649                 yaffs_ClearChunkBit(dev, block, page);
3650
3651                 bi->pagesInUse--;
3652
3653                 if (bi->pagesInUse == 0 &&
3654                     !bi->hasShrinkHeader &&
3655                     bi->blockState != YAFFS_BLOCK_STATE_ALLOCATING &&
3656                     bi->blockState != YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
3657                         yaffs_BlockBecameDirty(dev, block);
3658                 }
3659
3660         } else {
3661                 /* T(("Bad news deleting chunk %d\n",chunkId)); */
3662         }
3663
3664 }
3665
3666 static int yaffs_WriteChunkDataToObject(yaffs_Object * in, int chunkInInode,
3667                                         const __u8 * buffer, int nBytes,
3668                                         int useReserve)
3669 {
3670         /* Find old chunk Need to do this to get serial number
3671          * Write new one and patch into tree.
3672          * Invalidate old tags.
3673          */
3674
3675         int prevChunkId;
3676         yaffs_ExtendedTags prevTags;
3677
3678         int newChunkId;
3679         yaffs_ExtendedTags newTags;
3680
3681         yaffs_Device *dev = in->myDev;
3682
3683         yaffs_CheckGarbageCollection(dev);
3684
3685         /* Get the previous chunk at this location in the file if it exists */
3686         prevChunkId = yaffs_FindChunkInFile(in, chunkInInode, &prevTags);
3687
3688         /* Set up new tags */
3689         yaffs_InitialiseTags(&newTags);
3690
3691         newTags.chunkId = chunkInInode;
3692         newTags.objectId = in->objectId;
3693         newTags.serialNumber =
3694             (prevChunkId >= 0) ? prevTags.serialNumber + 1 : 1;
3695         newTags.byteCount = nBytes;
3696
3697         if(nBytes < 1 || nBytes > dev->totalBytesPerChunk){
3698           T(YAFFS_TRACE_ERROR,
3699           (TSTR("Writing %d bytes to chunk!!!!!!!!!" TENDSTR), nBytes));
3700           while(1){}
3701         }
3702
3703
3704
3705         newChunkId =
3706             yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &newTags,
3707                                               useReserve);
3708
3709         if (newChunkId >= 0) {
3710                 yaffs_PutChunkIntoFile(in, chunkInInode, newChunkId, 0);
3711
3712                 if (prevChunkId >= 0) {
3713                         yaffs_DeleteChunk(dev, prevChunkId, 1, __LINE__);
3714
3715                 }
3716
3717                 yaffs_CheckFileSanity(in);
3718         }
3719         return newChunkId;
3720
3721 }
3722
3723 /* UpdateObjectHeader updates the header on NAND for an object.
3724  * If name is not NULL, then that new name is used.
3725  */
3726 int yaffs_UpdateObjectHeader(yaffs_Object * in, const YCHAR * name, int force,
3727                              int isShrink, int shadows)
3728 {
3729
3730         yaffs_BlockInfo *bi;
3731
3732         yaffs_Device *dev = in->myDev;
3733
3734         int prevChunkId;
3735         int retVal = 0;
3736         int result = 0;
3737
3738         int newChunkId;
3739         yaffs_ExtendedTags newTags;
3740         yaffs_ExtendedTags oldTags;
3741
3742         __u8 *buffer = NULL;
3743         YCHAR oldName[YAFFS_MAX_NAME_LENGTH + 1];
3744
3745         yaffs_ObjectHeader *oh = NULL;
3746
3747         yaffs_strcpy(oldName,_Y("silly old name"));
3748
3749
3750         if (!in->fake ||
3751             in == dev->rootDir || /* The rootDir should also be saved */
3752             force) {
3753
3754                 yaffs_CheckGarbageCollection(dev);
3755                 yaffs_CheckObjectDetailsLoaded(in);
3756
3757                 buffer = yaffs_GetTempBuffer(in->myDev, __LINE__);
3758                 oh = (yaffs_ObjectHeader *) buffer;
3759
3760                 prevChunkId = in->hdrChunk;
3761
3762                 if (prevChunkId > 0) {
3763                         result = yaffs_ReadChunkWithTagsFromNAND(dev, prevChunkId,
3764                                                         buffer, &oldTags);
3765
3766                         yaffs_VerifyObjectHeader(in,oh,&oldTags,0);
3767
3768                         memcpy(oldName, oh->name, sizeof(oh->name));
3769                 }
3770
3771                 memset(buffer, 0xFF, dev->nDataBytesPerChunk);
3772
3773                 oh->type = in->variantType;
3774                 oh->yst_mode = in->yst_mode;
3775                 oh->shadowsObject = oh->inbandShadowsObject = shadows;
3776
3777 #ifdef CONFIG_YAFFS_WINCE
3778                 oh->win_atime[0] = in->win_atime[0];
3779                 oh->win_ctime[0] = in->win_ctime[0];
3780                 oh->win_mtime[0] = in->win_mtime[0];
3781                 oh->win_atime[1] = in->win_atime[1];
3782                 oh->win_ctime[1] = in->win_ctime[1];
3783                 oh->win_mtime[1] = in->win_mtime[1];
3784 #else
3785                 oh->yst_uid = in->yst_uid;
3786                 oh->yst_gid = in->yst_gid;
3787                 oh->yst_atime = in->yst_atime;
3788                 oh->yst_mtime = in->yst_mtime;
3789                 oh->yst_ctime = in->yst_ctime;
3790                 oh->yst_rdev = in->yst_rdev;
3791 #endif
3792                 if (in->parent) {
3793                         oh->parentObjectId = in->parent->objectId;
3794                 } else {
3795                         oh->parentObjectId = 0;
3796                 }
3797
3798                 if (name && *name) {
3799                         memset(oh->name, 0, sizeof(oh->name));
3800                         yaffs_strncpy(oh->name, name, YAFFS_MAX_NAME_LENGTH);
3801                 } else if (prevChunkId>=0) {
3802                         memcpy(oh->name, oldName, sizeof(oh->name));
3803                 } else {
3804                         memset(oh->name, 0, sizeof(oh->name));
3805                 }
3806
3807                 oh->isShrink = isShrink;
3808
3809                 switch (in->variantType) {
3810                 case YAFFS_OBJECT_TYPE_UNKNOWN:
3811                         /* Should not happen */
3812                         break;
3813                 case YAFFS_OBJECT_TYPE_FILE:
3814                         oh->fileSize =
3815                             (oh->parentObjectId == YAFFS_OBJECTID_DELETED
3816                              || oh->parentObjectId ==
3817                              YAFFS_OBJECTID_UNLINKED) ? 0 : in->variant.
3818                             fileVariant.fileSize;
3819                         break;
3820                 case YAFFS_OBJECT_TYPE_HARDLINK:
3821                         oh->equivalentObjectId =
3822                             in->variant.hardLinkVariant.equivalentObjectId;
3823                         break;
3824                 case YAFFS_OBJECT_TYPE_SPECIAL:
3825                         /* Do nothing */
3826                         break;
3827                 case YAFFS_OBJECT_TYPE_DIRECTORY:
3828                         /* Do nothing */
3829                         break;
3830                 case YAFFS_OBJECT_TYPE_SYMLINK:
3831                         yaffs_strncpy(oh->alias,
3832                                       in->variant.symLinkVariant.alias,
3833                                       YAFFS_MAX_ALIAS_LENGTH);
3834                         oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
3835                         break;
3836                 }
3837
3838                 /* Tags */
3839                 yaffs_InitialiseTags(&newTags);
3840                 in->serial++;
3841                 newTags.chunkId = 0;
3842                 newTags.objectId = in->objectId;
3843                 newTags.serialNumber = in->serial;
3844
3845                 /* Add extra info for file header */
3846
3847                 newTags.extraHeaderInfoAvailable = 1;
3848                 newTags.extraParentObjectId = oh->parentObjectId;
3849                 newTags.extraFileLength = oh->fileSize;
3850                 newTags.extraIsShrinkHeader = oh->isShrink;
3851                 newTags.extraEquivalentObjectId = oh->equivalentObjectId;
3852                 newTags.extraShadows = (oh->shadowsObject > 0) ? 1 : 0;
3853                 newTags.extraObjectType = in->variantType;
3854
3855                 yaffs_VerifyObjectHeader(in,oh,&newTags,1);
3856
3857                 /* Create new chunk in NAND */
3858                 newChunkId =
3859                     yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &newTags,
3860                                                       (prevChunkId >= 0) ? 1 : 0);
3861
3862                 if (newChunkId >= 0) {
3863
3864                         in->hdrChunk = newChunkId;
3865
3866                         if (prevChunkId >= 0) {
3867                                 yaffs_DeleteChunk(dev, prevChunkId, 1,
3868                                                   __LINE__);
3869                         }
3870
3871                         if(!yaffs_ObjectHasCachedWriteData(in))
3872                                 in->dirty = 0;
3873
3874                         /* If this was a shrink, then mark the block that the chunk lives on */
3875                         if (isShrink) {
3876                                 bi = yaffs_GetBlockInfo(in->myDev,
3877                                                         newChunkId /in->myDev-> nChunksPerBlock);
3878                                 bi->hasShrinkHeader = 1;
3879                         }
3880
3881                 }
3882
3883                 retVal = newChunkId;
3884
3885         }
3886
3887         if (buffer)
3888                 yaffs_ReleaseTempBuffer(dev, buffer, __LINE__);
3889
3890         return retVal;
3891 }
3892
3893 /*------------------------ Short Operations Cache ----------------------------------------
3894  *   In many situations where there is no high level buffering (eg WinCE) a lot of
3895  *   reads might be short sequential reads, and a lot of writes may be short
3896  *   sequential writes. eg. scanning/writing a jpeg file.
3897  *   In these cases, a short read/write cache can provide a huge perfomance benefit
3898  *   with dumb-as-a-rock code.
3899  *   In Linux, the page cache provides read buffering aand the short op cache provides write
3900  *   buffering.
3901  *
3902  *   There are a limited number (~10) of cache chunks per device so that we don't
3903  *   need a very intelligent search.
3904  */
3905
3906 static int yaffs_ObjectHasCachedWriteData(yaffs_Object *obj)
3907 {
3908         yaffs_Device *dev = obj->myDev;
3909         int i;
3910         yaffs_ChunkCache *cache;
3911         int nCaches = obj->myDev->nShortOpCaches;
3912
3913         for(i = 0; i < nCaches; i++){
3914                 cache = &dev->srCache[i];
3915                 if (cache->object == obj &&
3916                     cache->dirty)
3917                         return 1;
3918         }
3919
3920         return 0;
3921 }
3922
3923
3924 static void yaffs_FlushFilesChunkCache(yaffs_Object * obj)
3925 {
3926         yaffs_Device *dev = obj->myDev;
3927         int lowest = -99;       /* Stop compiler whining. */
3928         int i;
3929         yaffs_ChunkCache *cache;
3930         int chunkWritten = 0;
3931         int nCaches = obj->myDev->nShortOpCaches;
3932
3933         if (nCaches > 0) {
3934                 do {
3935                         cache = NULL;
3936
3937                         /* Find the dirty cache for this object with the lowest chunk id. */
3938                         for (i = 0; i < nCaches; i++) {
3939                                 if (dev->srCache[i].object == obj &&
3940                                     dev->srCache[i].dirty) {
3941                                         if (!cache
3942                                             || dev->srCache[i].chunkId <
3943                                             lowest) {
3944                                                 cache = &dev->srCache[i];
3945                                                 lowest = cache->chunkId;
3946                                         }
3947                                 }
3948                         }
3949
3950                         if (cache && !cache->locked) {
3951                                 /* Write it out and free it up */
3952
3953                                 chunkWritten =
3954                                     yaffs_WriteChunkDataToObject(cache->object,
3955                                                                  cache->chunkId,
3956                                                                  cache->data,
3957                                                                  cache->nBytes,
3958                                                                  1);
3959                                 cache->dirty = 0;
3960                                 cache->object = NULL;
3961                         }
3962
3963                 } while (cache && chunkWritten > 0);
3964
3965                 if (cache) {
3966                         /* Hoosterman, disk full while writing cache out. */
3967                         T(YAFFS_TRACE_ERROR,
3968                           (TSTR("yaffs tragedy: no space during cache write" TENDSTR)));
3969
3970                 }
3971         }
3972
3973 }
3974
3975 /*yaffs_FlushEntireDeviceCache(dev)
3976  *
3977  *
3978  */
3979
3980 void yaffs_FlushEntireDeviceCache(yaffs_Device *dev)
3981 {
3982         yaffs_Object *obj;
3983         int nCaches = dev->nShortOpCaches;
3984         int i;
3985
3986         /* Find a dirty object in the cache and flush it...
3987          * until there are no further dirty objects.
3988          */
3989         do {
3990                 obj = NULL;
3991                 for( i = 0; i < nCaches && !obj; i++) {
3992                         if (dev->srCache[i].object &&
3993                             dev->srCache[i].dirty)
3994                                 obj = dev->srCache[i].object;
3995
3996                 }
3997                 if(obj)
3998                         yaffs_FlushFilesChunkCache(obj);
3999
4000         } while(obj);
4001
4002 }
4003
4004
4005 /* Grab us a cache chunk for use.
4006  * First look for an empty one.
4007  * Then look for the least recently used non-dirty one.
4008  * Then look for the least recently used dirty one...., flush and look again.
4009  */
4010 static yaffs_ChunkCache *yaffs_GrabChunkCacheWorker(yaffs_Device * dev)
4011 {
4012         int i;
4013
4014         if (dev->nShortOpCaches > 0) {
4015                 for (i = 0; i < dev->nShortOpCaches; i++) {
4016                         if (!dev->srCache[i].object)
4017                                 return &dev->srCache[i];
4018                 }
4019         }
4020
4021         return NULL;
4022 }
4023
4024 static yaffs_ChunkCache *yaffs_GrabChunkCache(yaffs_Device * dev)
4025 {
4026         yaffs_ChunkCache *cache;
4027         yaffs_Object *theObj;
4028         int usage;
4029         int i;
4030         int pushout;
4031
4032         if (dev->nShortOpCaches > 0) {
4033                 /* Try find a non-dirty one... */
4034
4035                 cache = yaffs_GrabChunkCacheWorker(dev);
4036
4037                 if (!cache) {
4038                         /* They were all dirty, find the last recently used object and flush
4039                          * its cache, then  find again.
4040                          * NB what's here is not very accurate, we actually flush the object
4041                          * the last recently used page.
4042                          */
4043
4044                         /* With locking we can't assume we can use entry zero */
4045
4046                         theObj = NULL;
4047                         usage = -1;
4048                         cache = NULL;
4049                         pushout = -1;
4050
4051                         for (i = 0; i < dev->nShortOpCaches; i++) {
4052                                 if (dev->srCache[i].object &&
4053                                     !dev->srCache[i].locked &&
4054                                     (dev->srCache[i].lastUse < usage || !cache))
4055                                 {
4056                                         usage = dev->srCache[i].lastUse;
4057                                         theObj = dev->srCache[i].object;
4058                                         cache = &dev->srCache[i];
4059                                         pushout = i;
4060                                 }
4061                         }
4062
4063                         if (!cache || cache->dirty) {
4064                                 /* Flush and try again */
4065                                 yaffs_FlushFilesChunkCache(theObj);
4066                                 cache = yaffs_GrabChunkCacheWorker(dev);
4067                         }
4068
4069                 }
4070                 return cache;
4071         } else
4072                 return NULL;
4073
4074 }
4075
4076 /* Find a cached chunk */
4077 static yaffs_ChunkCache *yaffs_FindChunkCache(const yaffs_Object * obj,
4078                                               int chunkId)
4079 {
4080         yaffs_Device *dev = obj->myDev;
4081         int i;
4082         if (dev->nShortOpCaches > 0) {
4083                 for (i = 0; i < dev->nShortOpCaches; i++) {
4084                         if (dev->srCache[i].object == obj &&
4085                             dev->srCache[i].chunkId == chunkId) {
4086                                 dev->cacheHits++;
4087
4088                                 return &dev->srCache[i];
4089                         }
4090                 }
4091         }
4092         return NULL;
4093 }
4094
4095 /* Mark the chunk for the least recently used algorithym */
4096 static void yaffs_UseChunkCache(yaffs_Device * dev, yaffs_ChunkCache * cache,
4097                                 int isAWrite)
4098 {
4099
4100         if (dev->nShortOpCaches > 0) {
4101                 if (dev->srLastUse < 0 || dev->srLastUse > 100000000) {
4102                         /* Reset the cache usages */
4103                         int i;
4104                         for (i = 1; i < dev->nShortOpCaches; i++) {
4105                                 dev->srCache[i].lastUse = 0;
4106                         }
4107                         dev->srLastUse = 0;
4108                 }
4109
4110                 dev->srLastUse++;
4111
4112                 cache->lastUse = dev->srLastUse;
4113
4114                 if (isAWrite) {
4115                         cache->dirty = 1;
4116                 }
4117         }
4118 }
4119
4120 /* Invalidate a single cache page.
4121  * Do this when a whole page gets written,
4122  * ie the short cache for this page is no longer valid.
4123  */
4124 static void yaffs_InvalidateChunkCache(yaffs_Object * object, int chunkId)
4125 {
4126         if (object->myDev->nShortOpCaches > 0) {
4127                 yaffs_ChunkCache *cache = yaffs_FindChunkCache(object, chunkId);
4128
4129                 if (cache) {
4130                         cache->object = NULL;
4131                 }
4132         }
4133 }
4134
4135 /* Invalidate all the cache pages associated with this object
4136  * Do this whenever ther file is deleted or resized.
4137  */
4138 static void yaffs_InvalidateWholeChunkCache(yaffs_Object * in)
4139 {
4140         int i;
4141         yaffs_Device *dev = in->myDev;
4142
4143         if (dev->nShortOpCaches > 0) {
4144                 /* Invalidate it. */
4145                 for (i = 0; i < dev->nShortOpCaches; i++) {
4146                         if (dev->srCache[i].object == in) {
4147                                 dev->srCache[i].object = NULL;
4148                         }
4149                 }
4150         }
4151 }
4152
4153 /*--------------------- Checkpointing --------------------*/
4154
4155
4156 static int yaffs_WriteCheckpointValidityMarker(yaffs_Device *dev,int head)
4157 {
4158         yaffs_CheckpointValidity cp;
4159
4160         memset(&cp,0,sizeof(cp));
4161
4162         cp.structType = sizeof(cp);
4163         cp.magic = YAFFS_MAGIC;
4164         cp.version = YAFFS_CHECKPOINT_VERSION;
4165         cp.head = (head) ? 1 : 0;
4166
4167         return (yaffs_CheckpointWrite(dev,&cp,sizeof(cp)) == sizeof(cp))?
4168                 1 : 0;
4169 }
4170
4171 static int yaffs_ReadCheckpointValidityMarker(yaffs_Device *dev, int head)
4172 {
4173         yaffs_CheckpointValidity cp;
4174         int ok;
4175
4176         ok = (yaffs_CheckpointRead(dev,&cp,sizeof(cp)) == sizeof(cp));
4177
4178         if(ok)
4179                 ok = (cp.structType == sizeof(cp)) &&
4180                      (cp.magic == YAFFS_MAGIC) &&
4181                      (cp.version == YAFFS_CHECKPOINT_VERSION) &&
4182                      (cp.head == ((head) ? 1 : 0));
4183         return ok ? 1 : 0;
4184 }
4185
4186 static void yaffs_DeviceToCheckpointDevice(yaffs_CheckpointDevice *cp,
4187                                            yaffs_Device *dev)
4188 {
4189         cp->nErasedBlocks = dev->nErasedBlocks;
4190         cp->allocationBlock = dev->allocationBlock;
4191         cp->allocationPage = dev->allocationPage;
4192         cp->nFreeChunks = dev->nFreeChunks;
4193
4194         cp->nDeletedFiles = dev->nDeletedFiles;
4195         cp->nUnlinkedFiles = dev->nUnlinkedFiles;
4196         cp->nBackgroundDeletions = dev->nBackgroundDeletions;
4197         cp->sequenceNumber = dev->sequenceNumber;
4198         cp->oldestDirtySequence = dev->oldestDirtySequence;
4199
4200 }
4201
4202 static void yaffs_CheckpointDeviceToDevice(yaffs_Device *dev,
4203                                            yaffs_CheckpointDevice *cp)
4204 {
4205         dev->nErasedBlocks = cp->nErasedBlocks;
4206         dev->allocationBlock = cp->allocationBlock;
4207         dev->allocationPage = cp->allocationPage;
4208         dev->nFreeChunks = cp->nFreeChunks;
4209
4210         dev->nDeletedFiles = cp->nDeletedFiles;
4211         dev->nUnlinkedFiles = cp->nUnlinkedFiles;
4212         dev->nBackgroundDeletions = cp->nBackgroundDeletions;
4213         dev->sequenceNumber = cp->sequenceNumber;
4214         dev->oldestDirtySequence = cp->oldestDirtySequence;
4215 }
4216
4217
4218 static int yaffs_WriteCheckpointDevice(yaffs_Device *dev)
4219 {
4220         yaffs_CheckpointDevice cp;
4221         __u32 nBytes;
4222         __u32 nBlocks = (dev->internalEndBlock - dev->internalStartBlock + 1);
4223
4224         int ok;
4225
4226         /* Write device runtime values*/
4227         yaffs_DeviceToCheckpointDevice(&cp,dev);
4228         cp.structType = sizeof(cp);
4229
4230         ok = (yaffs_CheckpointWrite(dev,&cp,sizeof(cp)) == sizeof(cp));
4231
4232         /* Write block info */
4233         if(ok) {
4234                 nBytes = nBlocks * sizeof(yaffs_BlockInfo);
4235                 ok = (yaffs_CheckpointWrite(dev,dev->blockInfo,nBytes) == nBytes);
4236         }
4237
4238         /* Write chunk bits */
4239         if(ok) {
4240                 nBytes = nBlocks * dev->chunkBitmapStride;
4241                 ok = (yaffs_CheckpointWrite(dev,dev->chunkBits,nBytes) == nBytes);
4242         }
4243         return   ok ? 1 : 0;
4244
4245 }
4246
4247 static int yaffs_ReadCheckpointDevice(yaffs_Device *dev)
4248 {
4249         yaffs_CheckpointDevice cp;
4250         __u32 nBytes;
4251         __u32 nBlocks = (dev->internalEndBlock - dev->internalStartBlock + 1);
4252
4253         int ok;
4254
4255         ok = (yaffs_CheckpointRead(dev,&cp,sizeof(cp)) == sizeof(cp));
4256         if(!ok)
4257                 return 0;
4258
4259         if(cp.structType != sizeof(cp))
4260                 return 0;
4261
4262
4263         yaffs_CheckpointDeviceToDevice(dev,&cp);
4264
4265         nBytes = nBlocks * sizeof(yaffs_BlockInfo);
4266
4267         ok = (yaffs_CheckpointRead(dev,dev->blockInfo,nBytes) == nBytes);
4268
4269         if(!ok)
4270                 return 0;
4271         nBytes = nBlocks * dev->chunkBitmapStride;
4272
4273         ok = (yaffs_CheckpointRead(dev,dev->chunkBits,nBytes) == nBytes);
4274
4275         return ok ? 1 : 0;
4276 }
4277
4278 static void yaffs_ObjectToCheckpointObject(yaffs_CheckpointObject *cp,
4279                                            yaffs_Object *obj)
4280 {
4281
4282         cp->objectId = obj->objectId;
4283         cp->parentId = (obj->parent) ? obj->parent->objectId : 0;
4284         cp->hdrChunk = obj->hdrChunk;
4285         cp->variantType = obj->variantType;
4286         cp->deleted = obj->deleted;
4287         cp->softDeleted = obj->softDeleted;
4288         cp->unlinked = obj->unlinked;
4289         cp->fake = obj->fake;
4290         cp->renameAllowed = obj->renameAllowed;
4291         cp->unlinkAllowed = obj->unlinkAllowed;
4292         cp->serial = obj->serial;
4293         cp->nDataChunks = obj->nDataChunks;
4294
4295         if(obj->variantType == YAFFS_OBJECT_TYPE_FILE)
4296                 cp->fileSizeOrEquivalentObjectId = obj->variant.fileVariant.fileSize;
4297         else if(obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
4298                 cp->fileSizeOrEquivalentObjectId = obj->variant.hardLinkVariant.equivalentObjectId;
4299 }
4300
4301 static void yaffs_CheckpointObjectToObject( yaffs_Object *obj,yaffs_CheckpointObject *cp)
4302 {
4303
4304         yaffs_Object *parent;
4305
4306         obj->objectId = cp->objectId;
4307
4308         if(cp->parentId)
4309                 parent = yaffs_FindOrCreateObjectByNumber(
4310                                         obj->myDev,
4311                                         cp->parentId,
4312                                         YAFFS_OBJECT_TYPE_DIRECTORY);
4313         else
4314                 parent = NULL;
4315
4316         if(parent)
4317                 yaffs_AddObjectToDirectory(parent, obj);
4318
4319         obj->hdrChunk = cp->hdrChunk;
4320         obj->variantType = cp->variantType;
4321         obj->deleted = cp->deleted;
4322         obj->softDeleted = cp->softDeleted;
4323         obj->unlinked = cp->unlinked;
4324         obj->fake = cp->fake;
4325         obj->renameAllowed = cp->renameAllowed;
4326         obj->unlinkAllowed = cp->unlinkAllowed;
4327         obj->serial = cp->serial;
4328         obj->nDataChunks = cp->nDataChunks;
4329
4330         if(obj->variantType == YAFFS_OBJECT_TYPE_FILE)
4331                 obj->variant.fileVariant.fileSize = cp->fileSizeOrEquivalentObjectId;
4332         else if(obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
4333                 obj->variant.hardLinkVariant.equivalentObjectId = cp->fileSizeOrEquivalentObjectId;
4334
4335         if(obj->hdrChunk > 0)
4336                 obj->lazyLoaded = 1;
4337 }
4338
4339
4340
4341 static int yaffs_CheckpointTnodeWorker(yaffs_Object * in, yaffs_Tnode * tn,
4342                                         __u32 level, int chunkOffset)
4343 {
4344         int i;
4345         yaffs_Device *dev = in->myDev;
4346         int ok = 1;
4347         int tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
4348
4349         if(tnodeSize < sizeof(yaffs_Tnode))
4350                 tnodeSize = sizeof(yaffs_Tnode);
4351
4352
4353         if (tn) {
4354                 if (level > 0) {
4355
4356                         for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++){
4357                                 if (tn->internal[i]) {
4358                                         ok = yaffs_CheckpointTnodeWorker(in,
4359                                                         tn->internal[i],
4360                                                         level - 1,
4361                                                         (chunkOffset<<YAFFS_TNODES_INTERNAL_BITS) + i);
4362                                 }
4363                         }
4364                 } else if (level == 0) {
4365                         __u32 baseOffset = chunkOffset <<  YAFFS_TNODES_LEVEL0_BITS;
4366                         /* printf("write tnode at %d\n",baseOffset); */
4367                         ok = (yaffs_CheckpointWrite(dev,&baseOffset,sizeof(baseOffset)) == sizeof(baseOffset));
4368                         if(ok)
4369                                 ok = (yaffs_CheckpointWrite(dev,tn,tnodeSize) == tnodeSize);
4370                 }
4371         }
4372
4373         return ok;
4374
4375 }
4376
4377 static int yaffs_WriteCheckpointTnodes(yaffs_Object *obj)
4378 {
4379         __u32 endMarker = ~0;
4380         int ok = 1;
4381
4382         if(obj->variantType == YAFFS_OBJECT_TYPE_FILE){
4383                 ok = yaffs_CheckpointTnodeWorker(obj,
4384                                             obj->variant.fileVariant.top,
4385                                             obj->variant.fileVariant.topLevel,
4386                                             0);
4387                 if(ok)
4388                         ok = (yaffs_CheckpointWrite(obj->myDev,&endMarker,sizeof(endMarker)) ==
4389                                 sizeof(endMarker));
4390         }
4391
4392         return ok ? 1 : 0;
4393 }
4394
4395 static int yaffs_ReadCheckpointTnodes(yaffs_Object *obj)
4396 {
4397         __u32 baseChunk;
4398         int ok = 1;
4399         yaffs_Device *dev = obj->myDev;
4400         yaffs_FileStructure *fileStructPtr = &obj->variant.fileVariant;
4401         yaffs_Tnode *tn;
4402         int nread = 0;
4403         int tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
4404
4405         if(tnodeSize < sizeof(yaffs_Tnode))
4406                 tnodeSize = sizeof(yaffs_Tnode);
4407
4408         ok = (yaffs_CheckpointRead(dev,&baseChunk,sizeof(baseChunk)) == sizeof(baseChunk));
4409
4410         while(ok && (~baseChunk)){
4411                 nread++;
4412                 /* Read level 0 tnode */
4413
4414
4415                 /* printf("read  tnode at %d\n",baseChunk); */
4416                 tn = yaffs_GetTnodeRaw(dev);
4417                 if(tn)
4418                         ok = (yaffs_CheckpointRead(dev,tn,tnodeSize) == tnodeSize);
4419                 else
4420                         ok = 0;
4421
4422                 if(tn && ok){
4423                         ok = yaffs_AddOrFindLevel0Tnode(dev,
4424                                                         fileStructPtr,
4425                                                         baseChunk,
4426                                                         tn) ? 1 : 0;
4427
4428                 }
4429
4430                 if(ok)
4431                         ok = (yaffs_CheckpointRead(dev,&baseChunk,sizeof(baseChunk)) == sizeof(baseChunk));
4432
4433         }
4434
4435         T(YAFFS_TRACE_CHECKPOINT,(
4436                 TSTR("Checkpoint read tnodes %d records, last %d. ok %d" TENDSTR),
4437                 nread,baseChunk,ok));
4438
4439         return ok ? 1 : 0;
4440 }
4441
4442
4443 static int yaffs_WriteCheckpointObjects(yaffs_Device *dev)
4444 {
4445         yaffs_Object *obj;
4446         yaffs_CheckpointObject cp;
4447         int i;
4448         int ok = 1;
4449         struct ylist_head *lh;
4450
4451
4452         /* Iterate through the objects in each hash entry,
4453          * dumping them to the checkpointing stream.
4454          */
4455
4456          for(i = 0; ok &&  i <  YAFFS_NOBJECT_BUCKETS; i++){
4457                 ylist_for_each(lh, &dev->objectBucket[i].list) {
4458                         if (lh) {
4459                                 obj = ylist_entry(lh, yaffs_Object, hashLink);
4460                                 if (!obj->deferedFree) {
4461                                         yaffs_ObjectToCheckpointObject(&cp,obj);
4462                                         cp.structType = sizeof(cp);
4463
4464                                         T(YAFFS_TRACE_CHECKPOINT,(
4465                                                 TSTR("Checkpoint write object %d parent %d type %d chunk %d obj addr %x" TENDSTR),
4466                                                 cp.objectId,cp.parentId,cp.variantType,cp.hdrChunk,(unsigned) obj));
4467
4468                                         ok = (yaffs_CheckpointWrite(dev,&cp,sizeof(cp)) == sizeof(cp));
4469
4470                                         if(ok && obj->variantType == YAFFS_OBJECT_TYPE_FILE){
4471                                                 ok = yaffs_WriteCheckpointTnodes(obj);
4472                                         }
4473                                 }
4474                         }
4475                 }
4476          }
4477
4478          /* Dump end of list */
4479         memset(&cp,0xFF,sizeof(yaffs_CheckpointObject));
4480         cp.structType = sizeof(cp);
4481
4482         if(ok)
4483                 ok = (yaffs_CheckpointWrite(dev,&cp,sizeof(cp)) == sizeof(cp));
4484
4485         return ok ? 1 : 0;
4486 }
4487
4488 static int yaffs_ReadCheckpointObjects(yaffs_Device *dev)
4489 {
4490         yaffs_Object *obj;
4491         yaffs_CheckpointObject cp;
4492         int ok = 1;
4493         int done = 0;
4494         yaffs_Object *hardList = NULL;
4495
4496         while(ok && !done) {
4497                 ok = (yaffs_CheckpointRead(dev,&cp,sizeof(cp)) == sizeof(cp));
4498                 if(cp.structType != sizeof(cp)) {
4499                         T(YAFFS_TRACE_CHECKPOINT,(TSTR("struct size %d instead of %d ok %d"TENDSTR),
4500                                 cp.structType,sizeof(cp),ok));
4501                         ok = 0;
4502                 }
4503
4504                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("Checkpoint read object %d parent %d type %d chunk %d " TENDSTR),
4505                         cp.objectId,cp.parentId,cp.variantType,cp.hdrChunk));
4506
4507                 if(ok && cp.objectId == ~0)
4508                         done = 1;
4509                 else if(ok){
4510                         obj = yaffs_FindOrCreateObjectByNumber(dev,cp.objectId, cp.variantType);
4511                         if(obj) {
4512                                 yaffs_CheckpointObjectToObject(obj,&cp);
4513                                 if(obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
4514                                         ok = yaffs_ReadCheckpointTnodes(obj);
4515                                 } else if(obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
4516                                         obj->hardLinks.next =
4517                                                     (struct ylist_head *)
4518                                                     hardList;
4519                                         hardList = obj;
4520                                 }
4521
4522                         }
4523                 }
4524         }
4525
4526         if(ok)
4527                 yaffs_HardlinkFixup(dev,hardList);
4528
4529         return ok ? 1 : 0;
4530 }
4531
4532 static int yaffs_WriteCheckpointSum(yaffs_Device *dev)
4533 {
4534         __u32 checkpointSum;
4535         int ok;
4536
4537         yaffs_GetCheckpointSum(dev,&checkpointSum);
4538
4539         ok = (yaffs_CheckpointWrite(dev,&checkpointSum,sizeof(checkpointSum)) == sizeof(checkpointSum));
4540
4541         if(!ok)
4542                 return 0;
4543
4544         return 1;
4545 }
4546
4547 static int yaffs_ReadCheckpointSum(yaffs_Device *dev)
4548 {
4549         __u32 checkpointSum0;
4550         __u32 checkpointSum1;
4551         int ok;
4552
4553         yaffs_GetCheckpointSum(dev,&checkpointSum0);
4554
4555         ok = (yaffs_CheckpointRead(dev,&checkpointSum1,sizeof(checkpointSum1)) == sizeof(checkpointSum1));
4556
4557         if(!ok)
4558                 return 0;
4559
4560         if(checkpointSum0 != checkpointSum1)
4561                 return 0;
4562
4563         return 1;
4564 }
4565
4566
4567 static int yaffs_WriteCheckpointData(yaffs_Device *dev)
4568 {
4569
4570         int ok = 1;
4571
4572         if(dev->skipCheckpointWrite || !dev->isYaffs2){
4573                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("skipping checkpoint write" TENDSTR)));
4574                 ok = 0;
4575         }
4576
4577         if(ok)
4578                 ok = yaffs_CheckpointOpen(dev,1);
4579
4580         if(ok){
4581                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("write checkpoint validity" TENDSTR)));
4582                 ok = yaffs_WriteCheckpointValidityMarker(dev,1);
4583         }
4584         if(ok){
4585                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("write checkpoint device" TENDSTR)));
4586                 ok = yaffs_WriteCheckpointDevice(dev);
4587         }
4588         if(ok){
4589                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("write checkpoint objects" TENDSTR)));
4590                 ok = yaffs_WriteCheckpointObjects(dev);
4591         }
4592         if(ok){
4593                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("write checkpoint validity" TENDSTR)));
4594                 ok = yaffs_WriteCheckpointValidityMarker(dev,0);
4595         }
4596
4597         if(ok){
4598                 ok = yaffs_WriteCheckpointSum(dev);
4599         }
4600
4601
4602         if(!yaffs_CheckpointClose(dev))
4603                  ok = 0;
4604
4605         if(ok)
4606                 dev->isCheckpointed = 1;
4607          else
4608                 dev->isCheckpointed = 0;
4609
4610         return dev->isCheckpointed;
4611 }
4612
4613 static int yaffs_ReadCheckpointData(yaffs_Device *dev)
4614 {
4615         int ok = 1;
4616
4617         if(dev->skipCheckpointRead || !dev->isYaffs2){
4618                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("skipping checkpoint read" TENDSTR)));
4619                 ok = 0;
4620         }
4621
4622         if(ok)
4623                 ok = yaffs_CheckpointOpen(dev,0); /* open for read */
4624
4625         if(ok){
4626                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("read checkpoint validity" TENDSTR)));
4627                 ok = yaffs_ReadCheckpointValidityMarker(dev,1);
4628         }
4629         if(ok){
4630                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("read checkpoint device" TENDSTR)));
4631                 ok = yaffs_ReadCheckpointDevice(dev);
4632         }
4633         if(ok){
4634                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("read checkpoint objects" TENDSTR)));
4635                 ok = yaffs_ReadCheckpointObjects(dev);
4636         }
4637         if(ok){
4638                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("read checkpoint validity" TENDSTR)));
4639                 ok = yaffs_ReadCheckpointValidityMarker(dev,0);
4640         }
4641
4642         if(ok){
4643                 ok = yaffs_ReadCheckpointSum(dev);
4644                 T(YAFFS_TRACE_CHECKPOINT,(TSTR("read checkpoint checksum %d" TENDSTR),ok));
4645         }
4646
4647         if(!yaffs_CheckpointClose(dev))
4648                 ok = 0;
4649
4650         if(ok)
4651                 dev->isCheckpointed = 1;
4652          else
4653                 dev->isCheckpointed = 0;
4654
4655         return ok ? 1 : 0;
4656
4657 }
4658
4659 static void yaffs_InvalidateCheckpoint(yaffs_Device *dev)
4660 {
4661         if(dev->isCheckpointed ||
4662            dev->blocksInCheckpoint > 0){
4663                 dev->isCheckpointed = 0;
4664                 yaffs_CheckpointInvalidateStream(dev);
4665                 if(dev->superBlock && dev->markSuperBlockDirty)
4666                         dev->markSuperBlockDirty(dev->superBlock);
4667         }
4668 }
4669
4670
4671 int yaffs_CheckpointSave(yaffs_Device *dev)
4672 {
4673
4674         T(YAFFS_TRACE_CHECKPOINT,(TSTR("save entry: isCheckpointed %d"TENDSTR),dev->isCheckpointed));
4675
4676         yaffs_VerifyObjects(dev);
4677         yaffs_VerifyBlocks(dev);
4678         yaffs_VerifyFreeChunks(dev);
4679
4680         if(!dev->isCheckpointed) {
4681                 yaffs_InvalidateCheckpoint(dev);
4682                 yaffs_WriteCheckpointData(dev);
4683         }
4684
4685         T(YAFFS_TRACE_ALWAYS,(TSTR("save exit: isCheckpointed %d"TENDSTR),dev->isCheckpointed));
4686
4687         return dev->isCheckpointed;
4688 }
4689
4690 int yaffs_CheckpointRestore(yaffs_Device *dev)
4691 {
4692         int retval;
4693         T(YAFFS_TRACE_CHECKPOINT,(TSTR("restore entry: isCheckpointed %d"TENDSTR),dev->isCheckpointed));
4694
4695         retval = yaffs_ReadCheckpointData(dev);
4696
4697         if(dev->isCheckpointed){
4698                 yaffs_VerifyObjects(dev);
4699                 yaffs_VerifyBlocks(dev);
4700                 yaffs_VerifyFreeChunks(dev);
4701         }
4702
4703         T(YAFFS_TRACE_CHECKPOINT,(TSTR("restore exit: isCheckpointed %d"TENDSTR),dev->isCheckpointed));
4704
4705         return retval;
4706 }
4707
4708 /*--------------------- File read/write ------------------------
4709  * Read and write have very similar structures.
4710  * In general the read/write has three parts to it
4711  * An incomplete chunk to start with (if the read/write is not chunk-aligned)
4712  * Some complete chunks
4713  * An incomplete chunk to end off with
4714  *
4715  * Curve-balls: the first chunk might also be the last chunk.
4716  */
4717
4718 int yaffs_ReadDataFromFile(yaffs_Object * in, __u8 * buffer, loff_t offset,
4719                            int nBytes)
4720 {
4721
4722         int chunk;
4723         __u32 start;
4724         int nToCopy;
4725         int n = nBytes;
4726         int nDone = 0;
4727         yaffs_ChunkCache *cache;
4728
4729         yaffs_Device *dev;
4730
4731         dev = in->myDev;
4732
4733         while (n > 0) {
4734                 //chunk = offset / dev->nDataBytesPerChunk + 1;
4735                 //start = offset % dev->nDataBytesPerChunk;
4736                 yaffs_AddrToChunk(dev,offset,&chunk,&start);
4737                 chunk++;
4738
4739                 /* OK now check for the curveball where the start and end are in
4740                  * the same chunk.
4741                  */
4742                 if ((start + n) < dev->nDataBytesPerChunk) {
4743                         nToCopy = n;
4744                 } else {
4745                         nToCopy = dev->nDataBytesPerChunk - start;
4746                 }
4747
4748                 cache = yaffs_FindChunkCache(in, chunk);
4749
4750                 /* If the chunk is already in the cache or it is less than a whole chunk
4751                  * or we're using inband tags then use the cache (if there is caching)
4752                  * else bypass the cache.
4753                  */
4754                 if (cache || nToCopy != dev->nDataBytesPerChunk || dev->inbandTags) {
4755                         if (dev->nShortOpCaches > 0) {
4756
4757                                 /* If we can't find the data in the cache, then load it up. */
4758
4759                                 if (!cache) {
4760                                         cache = yaffs_GrabChunkCache(in->myDev);
4761                                         cache->object = in;
4762                                         cache->chunkId = chunk;
4763                                         cache->dirty = 0;
4764                                         cache->locked = 0;
4765                                         yaffs_ReadChunkDataFromObject(in, chunk,
4766                                                                       cache->
4767                                                                       data);
4768                                         cache->nBytes = 0;
4769                                 }
4770
4771                                 yaffs_UseChunkCache(dev, cache, 0);
4772
4773                                 cache->locked = 1;
4774
4775 #ifdef CONFIG_YAFFS_WINCE
4776                                 yfsd_UnlockYAFFS(TRUE);
4777 #endif
4778                                 memcpy(buffer, &cache->data[start], nToCopy);
4779
4780 #ifdef CONFIG_YAFFS_WINCE
4781                                 yfsd_LockYAFFS(TRUE);
4782 #endif
4783                                 cache->locked = 0;
4784                         } else {
4785                                 /* Read into the local buffer then copy..*/
4786
4787                                 __u8 *localBuffer =
4788                                     yaffs_GetTempBuffer(dev, __LINE__);
4789                                 yaffs_ReadChunkDataFromObject(in, chunk,
4790                                                               localBuffer);
4791 #ifdef CONFIG_YAFFS_WINCE
4792                                 yfsd_UnlockYAFFS(TRUE);
4793 #endif
4794                                 memcpy(buffer, &localBuffer[start], nToCopy);
4795
4796 #ifdef CONFIG_YAFFS_WINCE
4797                                 yfsd_LockYAFFS(TRUE);
4798 #endif
4799                                 yaffs_ReleaseTempBuffer(dev, localBuffer,
4800                                                         __LINE__);
4801                         }
4802
4803                 } else {
4804 #ifdef CONFIG_YAFFS_WINCE
4805                         __u8 *localBuffer = yaffs_GetTempBuffer(dev, __LINE__);
4806
4807                         /* Under WinCE can't do direct transfer. Need to use a local buffer.
4808                          * This is because we otherwise screw up WinCE's memory mapper
4809                          */
4810                         yaffs_ReadChunkDataFromObject(in, chunk, localBuffer);
4811
4812 #ifdef CONFIG_YAFFS_WINCE
4813                         yfsd_UnlockYAFFS(TRUE);
4814 #endif
4815                         memcpy(buffer, localBuffer, dev->nDataBytesPerChunk);
4816
4817 #ifdef CONFIG_YAFFS_WINCE
4818                         yfsd_LockYAFFS(TRUE);
4819                         yaffs_ReleaseTempBuffer(dev, localBuffer, __LINE__);
4820 #endif
4821
4822 #else
4823                         /* A full chunk. Read directly into the supplied buffer. */
4824                         yaffs_ReadChunkDataFromObject(in, chunk, buffer);
4825 #endif
4826                 }
4827
4828                 n -= nToCopy;
4829                 offset += nToCopy;
4830                 buffer += nToCopy;
4831                 nDone += nToCopy;
4832
4833         }
4834
4835         return nDone;
4836 }
4837
4838 int yaffs_WriteDataToFile(yaffs_Object * in, const __u8 * buffer, loff_t offset,
4839                           int nBytes, int writeThrough)
4840 {
4841
4842         int chunk;
4843         __u32 start;
4844         int nToCopy;
4845         int n = nBytes;
4846         int nDone = 0;
4847         int nToWriteBack;
4848         int startOfWrite = offset;
4849         int chunkWritten = 0;
4850         int nBytesRead;
4851
4852         yaffs_Device *dev;
4853
4854         dev = in->myDev;
4855
4856         while (n > 0 && chunkWritten >= 0) {
4857                 //chunk = offset / dev->nDataBytesPerChunk + 1;
4858                 //start = offset % dev->nDataBytesPerChunk;
4859                 yaffs_AddrToChunk(dev,offset,&chunk,&start);
4860
4861                 if(chunk * dev->nDataBytesPerChunk + start != offset ||
4862                    start >= dev->nDataBytesPerChunk){
4863                    T(YAFFS_TRACE_ERROR,(TSTR("AddrToChunk of offset %d gives chunk %d start %d"TENDSTR),
4864                                         (int)offset, chunk,start));
4865                 }
4866                 chunk++;
4867
4868                 /* OK now check for the curveball where the start and end are in
4869                  * the same chunk.
4870                  */
4871
4872                 if ((start + n) < dev->nDataBytesPerChunk) {
4873                         nToCopy = n;
4874
4875                         /* Now folks, to calculate how many bytes to write back....
4876                          * If we're overwriting and not writing to then end of file then
4877                          * we need to write back as much as was there before.
4878                          */
4879
4880                         nBytesRead =
4881                             in->variant.fileVariant.fileSize -
4882                             ((chunk - 1) * dev->nDataBytesPerChunk);
4883
4884                         if (nBytesRead > dev->nDataBytesPerChunk) {
4885                                 nBytesRead = dev->nDataBytesPerChunk;
4886                         }
4887
4888                         nToWriteBack =
4889                             (nBytesRead >
4890                              ((int)start + n)) ? nBytesRead : (start + n);
4891
4892                 } else {
4893                         nToCopy = dev->nDataBytesPerChunk - start;
4894                         nToWriteBack = dev->nDataBytesPerChunk;
4895                 }
4896
4897                 if (nToCopy != dev->nDataBytesPerChunk || dev->inbandTags) {
4898                         /* An incomplete start or end chunk (or maybe both start and end chunk),
4899                          * or we're using inband tags, so we want to use the cache buffers.
4900                          */
4901                         if (dev->nShortOpCaches > 0) {
4902                                 yaffs_ChunkCache *cache;
4903                                 /* If we can't find the data in the cache, then load the cache */
4904                                 cache = yaffs_FindChunkCache(in, chunk);
4905
4906                                 if (!cache
4907                                     && yaffs_CheckSpaceForAllocation(in->
4908                                                                      myDev)) {
4909                                         cache = yaffs_GrabChunkCache(in->myDev);
4910                                         cache->object = in;
4911                                         cache->chunkId = chunk;
4912                                         cache->dirty = 0;
4913                                         cache->locked = 0;
4914                                         yaffs_ReadChunkDataFromObject(in, chunk,
4915                                                                       cache->
4916                                                                       data);
4917                                 }
4918                                 else if(cache &&
4919                                         !cache->dirty &&
4920                                         !yaffs_CheckSpaceForAllocation(in->myDev)){
4921                                         /* Drop the cache if it was a read cache item and
4922                                          * no space check has been made for it.
4923                                          */
4924                                          cache = NULL;
4925                                 }
4926
4927                                 if (cache) {
4928                                         yaffs_UseChunkCache(dev, cache, 1);
4929                                         cache->locked = 1;
4930 #ifdef CONFIG_YAFFS_WINCE
4931                                         yfsd_UnlockYAFFS(TRUE);
4932 #endif
4933
4934                                         memcpy(&cache->data[start], buffer,
4935                                                nToCopy);
4936
4937 #ifdef CONFIG_YAFFS_WINCE
4938                                         yfsd_LockYAFFS(TRUE);
4939 #endif
4940                                         cache->locked = 0;
4941                                         cache->nBytes = nToWriteBack;
4942
4943                                         if (writeThrough) {
4944                                                 chunkWritten =
4945                                                     yaffs_WriteChunkDataToObject
4946                                                     (cache->object,
4947                                                      cache->chunkId,
4948                                                      cache->data, cache->nBytes,
4949                                                      1);
4950                                                 cache->dirty = 0;
4951                                         }
4952
4953                                 } else {
4954                                         chunkWritten = -1;      /* fail the write */
4955                                 }
4956                         } else {
4957                                 /* An incomplete start or end chunk (or maybe both start and end chunk)
4958                                  * Read into the local buffer then copy, then copy over and write back.
4959                                  */
4960
4961                                 __u8 *localBuffer =
4962                                     yaffs_GetTempBuffer(dev, __LINE__);
4963
4964                                 yaffs_ReadChunkDataFromObject(in, chunk,
4965                                                               localBuffer);
4966
4967 #ifdef CONFIG_YAFFS_WINCE
4968                                 yfsd_UnlockYAFFS(TRUE);
4969 #endif
4970
4971                                 memcpy(&localBuffer[start], buffer, nToCopy);
4972
4973 #ifdef CONFIG_YAFFS_WINCE
4974                                 yfsd_LockYAFFS(TRUE);
4975 #endif
4976                                 chunkWritten =
4977                                     yaffs_WriteChunkDataToObject(in, chunk,
4978                                                                  localBuffer,
4979                                                                  nToWriteBack,
4980                                                                  0);
4981
4982                                 yaffs_ReleaseTempBuffer(dev, localBuffer,
4983                                                         __LINE__);
4984
4985                         }
4986
4987                 } else {
4988                         /* A full chunk. Write directly from the supplied buffer. */
4989
4990 #ifdef CONFIG_YAFFS_WINCE
4991                         /* Under WinCE can't do direct transfer. Need to use a local buffer.
4992                          * This is because we otherwise screw up WinCE's memory mapper
4993                          */
4994                         __u8 *localBuffer = yaffs_GetTempBuffer(dev, __LINE__);
4995 #ifdef CONFIG_YAFFS_WINCE
4996                         yfsd_UnlockYAFFS(TRUE);
4997 #endif
4998                         memcpy(localBuffer, buffer, dev->nDataBytesPerChunk);
4999 #ifdef CONFIG_YAFFS_WINCE
5000                         yfsd_LockYAFFS(TRUE);
5001 #endif
5002                         chunkWritten =
5003                             yaffs_WriteChunkDataToObject(in, chunk, localBuffer,
5004                                                          dev->nDataBytesPerChunk,
5005                                                          0);
5006                         yaffs_ReleaseTempBuffer(dev, localBuffer, __LINE__);
5007 #else
5008
5009                         chunkWritten =
5010                             yaffs_WriteChunkDataToObject(in, chunk, buffer,
5011                                                          dev->nDataBytesPerChunk,
5012                                                          0);
5013 #endif
5014                         /* Since we've overwritten the cached data, we better invalidate it. */
5015                         yaffs_InvalidateChunkCache(in, chunk);
5016                 }
5017
5018                 if (chunkWritten >= 0) {
5019                         n -= nToCopy;
5020                         offset += nToCopy;
5021                         buffer += nToCopy;
5022                         nDone += nToCopy;
5023                 }
5024
5025         }
5026
5027         /* Update file object */
5028
5029         if ((startOfWrite + nDone) > in->variant.fileVariant.fileSize) {
5030                 in->variant.fileVariant.fileSize = (startOfWrite + nDone);
5031         }
5032
5033         in->dirty = 1;
5034
5035         return nDone;
5036 }
5037
5038
5039 /* ---------------------- File resizing stuff ------------------ */
5040
5041 static void yaffs_PruneResizedChunks(yaffs_Object * in, int newSize)
5042 {
5043
5044         yaffs_Device *dev = in->myDev;
5045         int oldFileSize = in->variant.fileVariant.fileSize;
5046
5047         int lastDel = 1 + (oldFileSize - 1) / dev->nDataBytesPerChunk;
5048
5049         int startDel = 1 + (newSize + dev->nDataBytesPerChunk - 1) /
5050             dev->nDataBytesPerChunk;
5051         int i;
5052         int chunkId;
5053
5054         /* Delete backwards so that we don't end up with holes if
5055          * power is lost part-way through the operation.
5056          */
5057         for (i = lastDel; i >= startDel; i--) {
5058                 /* NB this could be optimised somewhat,
5059                  * eg. could retrieve the tags and write them without
5060                  * using yaffs_DeleteChunk
5061                  */
5062
5063                 chunkId = yaffs_FindAndDeleteChunkInFile(in, i, NULL);
5064                 if (chunkId > 0) {
5065                         if (chunkId <
5066                             (dev->internalStartBlock * dev->nChunksPerBlock)
5067                             || chunkId >=
5068                             ((dev->internalEndBlock +
5069                               1) * dev->nChunksPerBlock)) {
5070                                 T(YAFFS_TRACE_ALWAYS,
5071                                   (TSTR("Found daft chunkId %d for %d" TENDSTR),
5072                                    chunkId, i));
5073                         } else {
5074                                 in->nDataChunks--;
5075                                 yaffs_DeleteChunk(dev, chunkId, 1, __LINE__);
5076                         }
5077                 }
5078         }
5079
5080 }
5081
5082 int yaffs_ResizeFile(yaffs_Object * in, loff_t newSize)
5083 {
5084
5085         int oldFileSize = in->variant.fileVariant.fileSize;
5086         __u32 newSizeOfPartialChunk;
5087         int newFullChunks;
5088
5089         yaffs_Device *dev = in->myDev;
5090
5091         yaffs_AddrToChunk(dev, newSize, &newFullChunks, &newSizeOfPartialChunk);
5092
5093         yaffs_FlushFilesChunkCache(in);
5094         yaffs_InvalidateWholeChunkCache(in);
5095
5096         yaffs_CheckGarbageCollection(dev);
5097
5098         if (in->variantType != YAFFS_OBJECT_TYPE_FILE) {
5099                 return YAFFS_FAIL;
5100         }
5101
5102         if (newSize == oldFileSize) {
5103                 return YAFFS_OK;
5104         }
5105
5106         if (newSize < oldFileSize) {
5107
5108                 yaffs_PruneResizedChunks(in, newSize);
5109
5110                 if (newSizeOfPartialChunk != 0) {
5111                         int lastChunk = 1 + newFullChunks;
5112
5113                         __u8 *localBuffer = yaffs_GetTempBuffer(dev, __LINE__);
5114
5115                         /* Got to read and rewrite the last chunk with its new size and zero pad */
5116                         yaffs_ReadChunkDataFromObject(in, lastChunk,
5117                                                       localBuffer);
5118
5119                         memset(localBuffer + newSizeOfPartialChunk, 0,
5120                                dev->nDataBytesPerChunk - newSizeOfPartialChunk);
5121
5122                         yaffs_WriteChunkDataToObject(in, lastChunk, localBuffer,
5123                                                      newSizeOfPartialChunk, 1);
5124
5125                         yaffs_ReleaseTempBuffer(dev, localBuffer, __LINE__);
5126                 }
5127
5128                 in->variant.fileVariant.fileSize = newSize;
5129
5130                 yaffs_PruneFileStructure(dev, &in->variant.fileVariant);
5131         } else {
5132                 /* newsSize > oldFileSize */
5133                 in->variant.fileVariant.fileSize = newSize;
5134         }
5135
5136
5137
5138         /* Write a new object header.
5139          * show we've shrunk the file, if need be
5140          * Do this only if the file is not in the deleted directories.
5141          */
5142         if (in->parent &&
5143             in->parent->objectId != YAFFS_OBJECTID_UNLINKED &&
5144             in->parent->objectId != YAFFS_OBJECTID_DELETED) {
5145                 yaffs_UpdateObjectHeader(in, NULL, 0,
5146                                          (newSize < oldFileSize) ? 1 : 0, 0);
5147         }
5148
5149         return YAFFS_OK;
5150 }
5151
5152 loff_t yaffs_GetFileSize(yaffs_Object * obj)
5153 {
5154         obj = yaffs_GetEquivalentObject(obj);
5155
5156         switch (obj->variantType) {
5157         case YAFFS_OBJECT_TYPE_FILE:
5158                 return obj->variant.fileVariant.fileSize;
5159         case YAFFS_OBJECT_TYPE_SYMLINK:
5160                 return yaffs_strlen(obj->variant.symLinkVariant.alias);
5161         default:
5162                 return 0;
5163         }
5164 }
5165
5166
5167
5168 int yaffs_FlushFile(yaffs_Object * in, int updateTime)
5169 {
5170         int retVal;
5171         if (in->dirty) {
5172                 yaffs_FlushFilesChunkCache(in);
5173                 if (updateTime) {
5174 #ifdef CONFIG_YAFFS_WINCE
5175                         yfsd_WinFileTimeNow(in->win_mtime);
5176 #else
5177
5178                         in->yst_mtime = Y_CURRENT_TIME;
5179
5180 #endif
5181                 }
5182
5183                 retVal =
5184                     (yaffs_UpdateObjectHeader(in, NULL, 0, 0, 0) >=
5185                      0) ? YAFFS_OK : YAFFS_FAIL;
5186         } else {
5187                 retVal = YAFFS_OK;
5188         }
5189
5190         return retVal;
5191
5192 }
5193
5194 static int yaffs_DoGenericObjectDeletion(yaffs_Object * in)
5195 {
5196
5197         /* First off, invalidate the file's data in the cache, without flushing. */
5198         yaffs_InvalidateWholeChunkCache(in);
5199
5200         if (in->myDev->isYaffs2 && (in->parent != in->myDev->deletedDir)) {
5201                 /* Move to the unlinked directory so we have a record that it was deleted. */
5202                 yaffs_ChangeObjectName(in, in->myDev->deletedDir,_Y("deleted"), 0, 0);
5203
5204         }
5205
5206         yaffs_RemoveObjectFromDirectory(in);
5207         yaffs_DeleteChunk(in->myDev, in->hdrChunk, 1, __LINE__);
5208         in->hdrChunk = 0;
5209
5210         yaffs_FreeObject(in);
5211         return YAFFS_OK;
5212
5213 }
5214
5215 /* yaffs_DeleteFile deletes the whole file data
5216  * and the inode associated with the file.
5217  * It does not delete the links associated with the file.
5218  */
5219
5220 static int yaffs_UnlinkFile(yaffs_Object * in)
5221 {
5222
5223         int retVal;
5224         int immediateDeletion = 0;
5225
5226 #ifdef __KERNEL__
5227         if (!in->myInode) {
5228                 immediateDeletion = 1;
5229         }
5230 #else
5231         if (in->inUse <= 0) {
5232                 immediateDeletion = 1;
5233         }
5234 #endif
5235
5236         if (immediateDeletion) {
5237                 retVal =
5238                     yaffs_ChangeObjectName(in, in->myDev->deletedDir,
5239                                            _Y("deleted"), 0, 0);
5240                 T(YAFFS_TRACE_TRACING,
5241                   (TSTR("yaffs: immediate deletion of file %d" TENDSTR),
5242                    in->objectId));
5243                 in->deleted = 1;
5244                 in->myDev->nDeletedFiles++;
5245                 if (1 || in->myDev->isYaffs2) {
5246                         yaffs_ResizeFile(in, 0);
5247                 }
5248                 yaffs_SoftDeleteFile(in);
5249         } else {
5250                 retVal =
5251                     yaffs_ChangeObjectName(in, in->myDev->unlinkedDir,
5252                                            _Y("unlinked"), 0, 0);
5253         }
5254
5255
5256         return retVal;
5257 }
5258
5259 int yaffs_DeleteFile(yaffs_Object * in)
5260 {
5261         int retVal = YAFFS_OK;
5262         int deleted = in->deleted;
5263
5264         yaffs_ResizeFile(in,0);
5265
5266         if (in->nDataChunks > 0) {
5267                 /* Use soft deletion if there is data in the file.
5268                  * That won't be the case if it has been resized to zero.
5269                  */
5270                 if (!in->unlinked) {
5271                         retVal = yaffs_UnlinkFile(in);
5272                 }
5273                 if (retVal == YAFFS_OK && in->unlinked && !in->deleted) {
5274                         in->deleted = deleted = 1;
5275                         in->myDev->nDeletedFiles++;
5276                         yaffs_SoftDeleteFile(in);
5277                 }
5278                 return deleted ? YAFFS_OK : YAFFS_FAIL;
5279         } else {
5280                 /* The file has no data chunks so we toss it immediately */
5281                 yaffs_FreeTnode(in->myDev, in->variant.fileVariant.top);
5282                 in->variant.fileVariant.top = NULL;
5283                 yaffs_DoGenericObjectDeletion(in);
5284
5285                 return YAFFS_OK;
5286         }
5287 }
5288
5289 static int yaffs_DeleteDirectory(yaffs_Object * in)
5290 {
5291         /* First check that the directory is empty. */
5292         if (ylist_empty(&in->variant.directoryVariant.children)) {
5293                 return yaffs_DoGenericObjectDeletion(in);
5294         }
5295
5296         return YAFFS_FAIL;
5297
5298 }
5299
5300 static int yaffs_DeleteSymLink(yaffs_Object * in)
5301 {
5302         YFREE(in->variant.symLinkVariant.alias);
5303
5304         return yaffs_DoGenericObjectDeletion(in);
5305 }
5306
5307 static int yaffs_DeleteHardLink(yaffs_Object * in)
5308 {
5309         /* remove this hardlink from the list assocaited with the equivalent
5310          * object
5311          */
5312         ylist_del_init(&in->hardLinks);
5313         return yaffs_DoGenericObjectDeletion(in);
5314 }
5315
5316 static void yaffs_DestroyObject(yaffs_Object * obj)
5317 {
5318         switch (obj->variantType) {
5319         case YAFFS_OBJECT_TYPE_FILE:
5320                 yaffs_DeleteFile(obj);
5321                 break;
5322         case YAFFS_OBJECT_TYPE_DIRECTORY:
5323                 yaffs_DeleteDirectory(obj);
5324                 break;
5325         case YAFFS_OBJECT_TYPE_SYMLINK:
5326                 yaffs_DeleteSymLink(obj);
5327                 break;
5328         case YAFFS_OBJECT_TYPE_HARDLINK:
5329                 yaffs_DeleteHardLink(obj);
5330                 break;
5331         case YAFFS_OBJECT_TYPE_SPECIAL:
5332                 yaffs_DoGenericObjectDeletion(obj);
5333                 break;
5334         case YAFFS_OBJECT_TYPE_UNKNOWN:
5335                 break;          /* should not happen. */
5336         }
5337 }
5338
5339 static int yaffs_UnlinkWorker(yaffs_Object * obj)
5340 {
5341
5342         if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
5343                 return yaffs_DeleteHardLink(obj);
5344         } else if (!ylist_empty(&obj->hardLinks)) {
5345                 /* Curve ball: We're unlinking an object that has a hardlink.
5346                  *
5347                  * This problem arises because we are not strictly following
5348                  * The Linux link/inode model.
5349                  *
5350                  * We can't really delete the object.
5351                  * Instead, we do the following:
5352                  * - Select a hardlink.
5353                  * - Unhook it from the hard links
5354                  * - Unhook it from its parent directory (so that the rename can work)
5355                  * - Rename the object to the hardlink's name.
5356                  * - Delete the hardlink
5357                  */
5358
5359                 yaffs_Object *hl;
5360                 int retVal;
5361                 YCHAR name[YAFFS_MAX_NAME_LENGTH + 1];
5362
5363                 hl = ylist_entry(obj->hardLinks.next, yaffs_Object, hardLinks);
5364
5365                 ylist_del_init(&hl->hardLinks);
5366                 ylist_del_init(&hl->siblings);
5367
5368                 yaffs_GetObjectName(hl, name, YAFFS_MAX_NAME_LENGTH + 1);
5369
5370                 retVal = yaffs_ChangeObjectName(obj, hl->parent, name, 0, 0);
5371
5372                 if (retVal == YAFFS_OK) {
5373                         retVal = yaffs_DoGenericObjectDeletion(hl);
5374                 }
5375                 return retVal;
5376
5377         } else {
5378                 switch (obj->variantType) {
5379                 case YAFFS_OBJECT_TYPE_FILE:
5380                         return yaffs_UnlinkFile(obj);
5381                         break;
5382                 case YAFFS_OBJECT_TYPE_DIRECTORY:
5383                         return yaffs_DeleteDirectory(obj);
5384                         break;
5385                 case YAFFS_OBJECT_TYPE_SYMLINK:
5386                         return yaffs_DeleteSymLink(obj);
5387                         break;
5388                 case YAFFS_OBJECT_TYPE_SPECIAL:
5389                         return yaffs_DoGenericObjectDeletion(obj);
5390                         break;
5391                 case YAFFS_OBJECT_TYPE_HARDLINK:
5392                 case YAFFS_OBJECT_TYPE_UNKNOWN:
5393                 default:
5394                         return YAFFS_FAIL;
5395                 }
5396         }
5397 }
5398
5399
5400 static int yaffs_UnlinkObject( yaffs_Object *obj)
5401 {
5402
5403         if (obj && obj->unlinkAllowed) {
5404                 return yaffs_UnlinkWorker(obj);
5405         }
5406
5407         return YAFFS_FAIL;
5408
5409 }
5410 int yaffs_Unlink(yaffs_Object * dir, const YCHAR * name)
5411 {
5412         yaffs_Object *obj;
5413
5414         obj = yaffs_FindObjectByName(dir, name);
5415         return yaffs_UnlinkObject(obj);
5416 }
5417
5418 /*----------------------- Initialisation Scanning ---------------------- */
5419
5420 static void yaffs_HandleShadowedObject(yaffs_Device * dev, int objId,
5421                                        int backwardScanning)
5422 {
5423         yaffs_Object *obj;
5424
5425         if (!backwardScanning) {
5426                 /* Handle YAFFS1 forward scanning case
5427                  * For YAFFS1 we always do the deletion
5428                  */
5429
5430         } else {
5431                 /* Handle YAFFS2 case (backward scanning)
5432                  * If the shadowed object exists then ignore.
5433                  */
5434                 if (yaffs_FindObjectByNumber(dev, objId)) {
5435                         return;
5436                 }
5437         }
5438
5439         /* Let's create it (if it does not exist) assuming it is a file so that it can do shrinking etc.
5440          * We put it in unlinked dir to be cleaned up after the scanning
5441          */
5442         obj =
5443             yaffs_FindOrCreateObjectByNumber(dev, objId,
5444                                              YAFFS_OBJECT_TYPE_FILE);
5445         yaffs_AddObjectToDirectory(dev->unlinkedDir, obj);
5446         obj->variant.fileVariant.shrinkSize = 0;
5447         obj->valid = 1;         /* So that we don't read any other info for this file */
5448
5449 }
5450
5451 typedef struct {
5452         int seq;
5453         int block;
5454 } yaffs_BlockIndex;
5455
5456
5457 static void yaffs_HardlinkFixup(yaffs_Device *dev, yaffs_Object *hardList)
5458 {
5459         yaffs_Object *hl;
5460         yaffs_Object *in;
5461
5462         while (hardList) {
5463                 hl = hardList;
5464                 hardList = (yaffs_Object *) (hardList->hardLinks.next);
5465
5466                 in = yaffs_FindObjectByNumber(dev,
5467                                               hl->variant.hardLinkVariant.
5468                                               equivalentObjectId);
5469
5470                 if (in) {
5471                         /* Add the hardlink pointers */
5472                         hl->variant.hardLinkVariant.equivalentObject = in;
5473                         ylist_add(&hl->hardLinks, &in->hardLinks);
5474                 } else {
5475                         /* Todo Need to report/handle this better.
5476                          * Got a problem... hardlink to a non-existant object
5477                          */
5478                         hl->variant.hardLinkVariant.equivalentObject = NULL;
5479                         YINIT_LIST_HEAD(&hl->hardLinks);
5480
5481                 }
5482
5483         }
5484
5485 }
5486
5487
5488
5489
5490
5491 static int ybicmp(const void *a, const void *b){
5492     register int aseq = ((yaffs_BlockIndex *)a)->seq;
5493     register int bseq = ((yaffs_BlockIndex *)b)->seq;
5494     register int ablock = ((yaffs_BlockIndex *)a)->block;
5495     register int bblock = ((yaffs_BlockIndex *)b)->block;
5496     if( aseq == bseq )
5497         return ablock - bblock;
5498     else
5499         return aseq - bseq;
5500
5501 }
5502
5503
5504 struct yaffs_ShadowFixerStruct {
5505         int objectId;
5506         int shadowedId;
5507         struct yaffs_ShadowFixerStruct *next;
5508 };
5509
5510 static int yaffs_Scan(yaffs_Device * dev)
5511 {
5512         yaffs_ExtendedTags tags;
5513         int blk;
5514         int blockIterator;
5515         int startIterator;
5516         int endIterator;
5517         int result;
5518
5519         int chunk;
5520         int c;
5521         int deleted;
5522         yaffs_BlockState state;
5523         yaffs_Object *hardList = NULL;
5524         yaffs_BlockInfo *bi;
5525         __u32 sequenceNumber;
5526         yaffs_ObjectHeader *oh;
5527         yaffs_Object *in;
5528         yaffs_Object *parent;
5529
5530         int alloc_failed = 0;
5531
5532         struct yaffs_ShadowFixerStruct *shadowFixerList = NULL;
5533
5534
5535         __u8 *chunkData;
5536
5537
5538
5539         T(YAFFS_TRACE_SCAN,
5540           (TSTR("yaffs_Scan starts  intstartblk %d intendblk %d..." TENDSTR),
5541            dev->internalStartBlock, dev->internalEndBlock));
5542
5543         chunkData = yaffs_GetTempBuffer(dev, __LINE__);
5544
5545         dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
5546
5547         /* Scan all the blocks to determine their state */
5548         for (blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++) {
5549                 bi = yaffs_GetBlockInfo(dev, blk);
5550                 yaffs_ClearChunkBits(dev, blk);
5551                 bi->pagesInUse = 0;
5552                 bi->softDeletions = 0;
5553
5554                 yaffs_QueryInitialBlockState(dev, blk, &state, &sequenceNumber);
5555
5556                 bi->blockState = state;
5557                 bi->sequenceNumber = sequenceNumber;
5558
5559                 T(YAFFS_TRACE_SCAN_DEBUG,
5560                   (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
5561                    state, sequenceNumber));
5562
5563                 if (state == YAFFS_BLOCK_STATE_DEAD) {
5564                         T(YAFFS_TRACE_BAD_BLOCKS,
5565                           (TSTR("block %d is bad" TENDSTR), blk));
5566                 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
5567                         T(YAFFS_TRACE_SCAN_DEBUG,
5568                           (TSTR("Block empty " TENDSTR)));
5569                         dev->nErasedBlocks++;
5570                         dev->nFreeChunks += dev->nChunksPerBlock;
5571                 }
5572         }
5573
5574         startIterator = dev->internalStartBlock;
5575         endIterator = dev->internalEndBlock;
5576
5577         /* For each block.... */
5578         for (blockIterator = startIterator; !alloc_failed && blockIterator <= endIterator;
5579              blockIterator++) {
5580
5581                 YYIELD();
5582
5583                 YYIELD();
5584
5585                 blk = blockIterator;
5586
5587                 bi = yaffs_GetBlockInfo(dev, blk);
5588                 state = bi->blockState;
5589
5590                 deleted = 0;
5591
5592                 /* For each chunk in each block that needs scanning....*/
5593                 for (c = 0; !alloc_failed && c < dev->nChunksPerBlock &&
5594                      state == YAFFS_BLOCK_STATE_NEEDS_SCANNING; c++) {
5595                         /* Read the tags and decide what to do */
5596                         chunk = blk * dev->nChunksPerBlock + c;
5597
5598                         result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk, NULL,
5599                                                         &tags);
5600
5601                         /* Let's have a good look at this chunk... */
5602
5603                         if (tags.eccResult == YAFFS_ECC_RESULT_UNFIXED || tags.chunkDeleted) {
5604                                 /* YAFFS1 only...
5605                                  * A deleted chunk
5606                                  */
5607                                 deleted++;
5608                                 dev->nFreeChunks++;
5609                                 /*T((" %d %d deleted\n",blk,c)); */
5610                         } else if (!tags.chunkUsed) {
5611                                 /* An unassigned chunk in the block
5612                                  * This means that either the block is empty or
5613                                  * this is the one being allocated from
5614                                  */
5615
5616                                 if (c == 0) {
5617                                         /* We're looking at the first chunk in the block so the block is unused */
5618                                         state = YAFFS_BLOCK_STATE_EMPTY;
5619                                         dev->nErasedBlocks++;
5620                                 } else {
5621                                         /* this is the block being allocated from */
5622                                         T(YAFFS_TRACE_SCAN,
5623                                           (TSTR
5624                                            (" Allocating from %d %d" TENDSTR),
5625                                            blk, c));
5626                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
5627                                         dev->allocationBlock = blk;
5628                                         dev->allocationPage = c;
5629                                         dev->allocationBlockFinder = blk;
5630                                         /* Set it to here to encourage the allocator to go forth from here. */
5631
5632                                 }
5633
5634                                 dev->nFreeChunks += (dev->nChunksPerBlock - c);
5635                         } else if (tags.chunkId > 0) {
5636                                 /* chunkId > 0 so it is a data chunk... */
5637                                 unsigned int endpos;
5638
5639                                 yaffs_SetChunkBit(dev, blk, c);
5640                                 bi->pagesInUse++;
5641
5642                                 in = yaffs_FindOrCreateObjectByNumber(dev,
5643                                                                       tags.
5644                                                                       objectId,
5645                                                                       YAFFS_OBJECT_TYPE_FILE);
5646                                 /* PutChunkIntoFile checks for a clash (two data chunks with
5647                                  * the same chunkId).
5648                                  */
5649
5650                                 if(!in)
5651                                         alloc_failed = 1;
5652
5653                                 if(in){
5654                                         if(!yaffs_PutChunkIntoFile(in, tags.chunkId, chunk,1))
5655                                                 alloc_failed = 1;
5656                                 }
5657
5658                                 endpos =
5659                                     (tags.chunkId - 1) * dev->nDataBytesPerChunk +
5660                                     tags.byteCount;
5661                                 if (in &&
5662                                     in->variantType == YAFFS_OBJECT_TYPE_FILE
5663                                     && in->variant.fileVariant.scannedFileSize <
5664                                     endpos) {
5665                                         in->variant.fileVariant.
5666                                             scannedFileSize = endpos;
5667                                         if (!dev->useHeaderFileSize) {
5668                                                 in->variant.fileVariant.
5669                                                     fileSize =
5670                                                     in->variant.fileVariant.
5671                                                     scannedFileSize;
5672                                         }
5673
5674                                 }
5675                                 /* T((" %d %d data %d %d\n",blk,c,tags.objectId,tags.chunkId));   */
5676                         } else {
5677                                 /* chunkId == 0, so it is an ObjectHeader.
5678                                  * Thus, we read in the object header and make the object
5679                                  */
5680                                 yaffs_SetChunkBit(dev, blk, c);
5681                                 bi->pagesInUse++;
5682
5683                                 result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk,
5684                                                                 chunkData,
5685                                                                 NULL);
5686
5687                                 oh = (yaffs_ObjectHeader *) chunkData;
5688
5689                                 in = yaffs_FindObjectByNumber(dev,
5690                                                               tags.objectId);
5691                                 if (in && in->variantType != oh->type) {
5692                                         /* This should not happen, but somehow
5693                                          * Wev'e ended up with an objectId that has been reused but not yet
5694                                          * deleted, and worse still it has changed type. Delete the old object.
5695                                          */
5696
5697                                         yaffs_DestroyObject(in);
5698
5699                                         in = 0;
5700                                 }
5701
5702                                 in = yaffs_FindOrCreateObjectByNumber(dev,
5703                                                                       tags.
5704                                                                       objectId,
5705                                                                       oh->type);
5706
5707                                 if(!in)
5708                                         alloc_failed = 1;
5709
5710                                 if (in && oh->shadowsObject > 0) {
5711
5712                                         struct yaffs_ShadowFixerStruct *fixer;
5713                                         fixer = YMALLOC(sizeof(struct yaffs_ShadowFixerStruct));
5714                                         if(fixer){
5715                                                 fixer-> next = shadowFixerList;
5716                                                 shadowFixerList = fixer;
5717                                                 fixer->objectId = tags.objectId;
5718                                                 fixer->shadowedId = oh->shadowsObject;
5719                                         }
5720
5721                                 }
5722
5723                                 if (in && in->valid) {
5724                                         /* We have already filled this one. We have a duplicate and need to resolve it. */
5725
5726                                         unsigned existingSerial = in->serial;
5727                                         unsigned newSerial = tags.serialNumber;
5728
5729                                         if (((existingSerial + 1) & 3) == newSerial) {
5730                                                 /* Use new one - destroy the exisiting one */
5731                                                 yaffs_DeleteChunk(dev,
5732                                                                   in->hdrChunk,
5733                                                                   1, __LINE__);
5734                                                 in->valid = 0;
5735                                         } else {
5736                                                 /* Use existing - destroy this one. */
5737                                                 yaffs_DeleteChunk(dev, chunk, 1,
5738                                                                   __LINE__);
5739                                         }
5740                                 }
5741
5742                                 if (in && !in->valid &&
5743                                     (tags.objectId == YAFFS_OBJECTID_ROOT ||
5744                                      tags.objectId == YAFFS_OBJECTID_LOSTNFOUND)) {
5745                                         /* We only load some info, don't fiddle with directory structure */
5746                                         in->valid = 1;
5747                                         in->variantType = oh->type;
5748
5749                                         in->yst_mode = oh->yst_mode;
5750 #ifdef CONFIG_YAFFS_WINCE
5751                                         in->win_atime[0] = oh->win_atime[0];
5752                                         in->win_ctime[0] = oh->win_ctime[0];
5753                                         in->win_mtime[0] = oh->win_mtime[0];
5754                                         in->win_atime[1] = oh->win_atime[1];
5755                                         in->win_ctime[1] = oh->win_ctime[1];
5756                                         in->win_mtime[1] = oh->win_mtime[1];
5757 #else
5758                                         in->yst_uid = oh->yst_uid;
5759                                         in->yst_gid = oh->yst_gid;
5760                                         in->yst_atime = oh->yst_atime;
5761                                         in->yst_mtime = oh->yst_mtime;
5762                                         in->yst_ctime = oh->yst_ctime;
5763                                         in->yst_rdev = oh->yst_rdev;
5764 #endif
5765                                         in->hdrChunk = chunk;
5766                                         in->serial = tags.serialNumber;
5767
5768                                 } else if (in && !in->valid) {
5769                                         /* we need to load this info */
5770
5771                                         in->valid = 1;
5772                                         in->variantType = oh->type;
5773
5774                                         in->yst_mode = oh->yst_mode;
5775 #ifdef CONFIG_YAFFS_WINCE
5776                                         in->win_atime[0] = oh->win_atime[0];
5777                                         in->win_ctime[0] = oh->win_ctime[0];
5778                                         in->win_mtime[0] = oh->win_mtime[0];
5779                                         in->win_atime[1] = oh->win_atime[1];
5780                                         in->win_ctime[1] = oh->win_ctime[1];
5781                                         in->win_mtime[1] = oh->win_mtime[1];
5782 #else
5783                                         in->yst_uid = oh->yst_uid;
5784                                         in->yst_gid = oh->yst_gid;
5785                                         in->yst_atime = oh->yst_atime;
5786                                         in->yst_mtime = oh->yst_mtime;
5787                                         in->yst_ctime = oh->yst_ctime;
5788                                         in->yst_rdev = oh->yst_rdev;
5789 #endif
5790                                         in->hdrChunk = chunk;
5791                                         in->serial = tags.serialNumber;
5792
5793                                         yaffs_SetObjectName(in, oh->name);
5794                                         in->dirty = 0;
5795
5796                                         /* directory stuff...
5797                                          * hook up to parent
5798                                          */
5799
5800                                         parent =
5801                                             yaffs_FindOrCreateObjectByNumber
5802                                             (dev, oh->parentObjectId,
5803                                              YAFFS_OBJECT_TYPE_DIRECTORY);
5804                                         if (parent->variantType ==
5805                                             YAFFS_OBJECT_TYPE_UNKNOWN) {
5806                                                 /* Set up as a directory */
5807                                                 parent->variantType =
5808                                                     YAFFS_OBJECT_TYPE_DIRECTORY;
5809                                                 YINIT_LIST_HEAD(&parent->variant.
5810                                                                directoryVariant.
5811                                                                children);
5812                                         } else if (parent->variantType !=
5813                                                    YAFFS_OBJECT_TYPE_DIRECTORY)
5814                                         {
5815                                                 /* Hoosterman, another problem....
5816                                                  * We're trying to use a non-directory as a directory
5817                                                  */
5818
5819                                                 T(YAFFS_TRACE_ERROR,
5820                                                   (TSTR
5821                                                    ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
5822                                                     TENDSTR)));
5823                                                 parent = dev->lostNFoundDir;
5824                                         }
5825
5826                                         yaffs_AddObjectToDirectory(parent, in);
5827
5828                                         if (0 && (parent == dev->deletedDir ||
5829                                                   parent == dev->unlinkedDir)) {
5830                                                 in->deleted = 1;        /* If it is unlinked at start up then it wants deleting */
5831                                                 dev->nDeletedFiles++;
5832                                         }
5833                                         /* Note re hardlinks.
5834                                          * Since we might scan a hardlink before its equivalent object is scanned
5835                                          * we put them all in a list.
5836                                          * After scanning is complete, we should have all the objects, so we run through this
5837                                          * list and fix up all the chains.
5838                                          */
5839
5840                                         switch (in->variantType) {
5841                                         case YAFFS_OBJECT_TYPE_UNKNOWN:
5842                                                 /* Todo got a problem */
5843                                                 break;
5844                                         case YAFFS_OBJECT_TYPE_FILE:
5845                                                 if (dev->useHeaderFileSize)
5846
5847                                                         in->variant.fileVariant.
5848                                                             fileSize =
5849                                                             oh->fileSize;
5850
5851                                                 break;
5852                                         case YAFFS_OBJECT_TYPE_HARDLINK:
5853                                                 in->variant.hardLinkVariant.
5854                                                     equivalentObjectId =
5855                                                     oh->equivalentObjectId;
5856                                                 in->hardLinks.next =
5857                                                     (struct ylist_head *)
5858                                                     hardList;
5859                                                 hardList = in;
5860                                                 break;
5861                                         case YAFFS_OBJECT_TYPE_DIRECTORY:
5862                                                 /* Do nothing */
5863                                                 break;
5864                                         case YAFFS_OBJECT_TYPE_SPECIAL:
5865                                                 /* Do nothing */
5866                                                 break;
5867                                         case YAFFS_OBJECT_TYPE_SYMLINK:
5868                                                 in->variant.symLinkVariant.alias =
5869                                                     yaffs_CloneString(oh->alias);
5870                                                 if(!in->variant.symLinkVariant.alias)
5871                                                         alloc_failed = 1;
5872                                                 break;
5873                                         }
5874
5875 /*
5876                                         if (parent == dev->deletedDir) {
5877                                                 yaffs_DestroyObject(in);
5878                                                 bi->hasShrinkHeader = 1;
5879                                         }
5880 */
5881                                 }
5882                         }
5883                 }
5884
5885                 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
5886                         /* If we got this far while scanning, then the block is fully allocated.*/
5887                         state = YAFFS_BLOCK_STATE_FULL;
5888                 }
5889
5890                 bi->blockState = state;
5891
5892                 /* Now let's see if it was dirty */
5893                 if (bi->pagesInUse == 0 &&
5894                     !bi->hasShrinkHeader &&
5895                     bi->blockState == YAFFS_BLOCK_STATE_FULL) {
5896                         yaffs_BlockBecameDirty(dev, blk);
5897                 }
5898
5899         }
5900
5901
5902         /* Ok, we've done all the scanning.
5903          * Fix up the hard link chains.
5904          * We should now have scanned all the objects, now it's time to add these
5905          * hardlinks.
5906          */
5907
5908         yaffs_HardlinkFixup(dev,hardList);
5909
5910         /* Handle the unlinked files. Since they were left in an unlinked state we should
5911          * just delete them.
5912          */
5913         {
5914                 struct ylist_head *i;
5915                 struct ylist_head *n;
5916
5917                 yaffs_Object *l;
5918                 /* Soft delete all the unlinked files */
5919                 ylist_for_each_safe(i, n,
5920                                    &dev->unlinkedDir->variant.directoryVariant.
5921                                    children) {
5922                         if (i) {
5923                                 l = ylist_entry(i, yaffs_Object, siblings);
5924                                 yaffs_DestroyObject(l);
5925                         }
5926                 }
5927         }
5928
5929         /* Fix up any shadowed objects */
5930         {
5931                 struct yaffs_ShadowFixerStruct *fixer;
5932                 yaffs_Object *obj;
5933
5934                 while(shadowFixerList){
5935                         fixer = shadowFixerList;
5936                         shadowFixerList = fixer->next;
5937                         /* Complete the rename transaction by deleting the shadowed object
5938                          * then setting the object header to unshadowed.
5939                          */
5940                         obj = yaffs_FindObjectByNumber(dev,fixer->shadowedId);
5941                         if(obj)
5942                                 yaffs_DestroyObject(obj);
5943
5944                         obj = yaffs_FindObjectByNumber(dev,fixer->objectId);
5945                         if(obj){
5946                                 yaffs_UpdateObjectHeader(obj,NULL,1,0,0);
5947                         }
5948
5949                         YFREE(fixer);
5950                 }
5951         }
5952
5953         yaffs_ReleaseTempBuffer(dev, chunkData, __LINE__);
5954
5955         if(alloc_failed){
5956                 return YAFFS_FAIL;
5957         }
5958
5959         T(YAFFS_TRACE_SCAN, (TSTR("yaffs_Scan ends" TENDSTR)));
5960
5961
5962         return YAFFS_OK;
5963 }
5964
5965 static void yaffs_CheckObjectDetailsLoaded(yaffs_Object *in)
5966 {
5967         __u8 *chunkData;
5968         yaffs_ObjectHeader *oh;
5969         yaffs_Device *dev;
5970         yaffs_ExtendedTags tags;
5971         int result;
5972         int alloc_failed = 0;
5973
5974         if(!in)
5975                 return;
5976
5977         dev = in->myDev;
5978
5979 #if 0
5980         T(YAFFS_TRACE_SCAN,(TSTR("details for object %d %s loaded" TENDSTR),
5981                 in->objectId,
5982                 in->lazyLoaded ? "not yet" : "already"));
5983 #endif
5984
5985         if(in->lazyLoaded && in->hdrChunk > 0){
5986                 in->lazyLoaded = 0;
5987                 chunkData = yaffs_GetTempBuffer(dev, __LINE__);
5988
5989                 result = yaffs_ReadChunkWithTagsFromNAND(dev,in->hdrChunk,chunkData,&tags);
5990                 oh = (yaffs_ObjectHeader *) chunkData;
5991
5992                 in->yst_mode = oh->yst_mode;
5993 #ifdef CONFIG_YAFFS_WINCE
5994                 in->win_atime[0] = oh->win_atime[0];
5995                 in->win_ctime[0] = oh->win_ctime[0];
5996                 in->win_mtime[0] = oh->win_mtime[0];
5997                 in->win_atime[1] = oh->win_atime[1];
5998                 in->win_ctime[1] = oh->win_ctime[1];
5999                 in->win_mtime[1] = oh->win_mtime[1];
6000 #else
6001                 in->yst_uid = oh->yst_uid;
6002                 in->yst_gid = oh->yst_gid;
6003                 in->yst_atime = oh->yst_atime;
6004                 in->yst_mtime = oh->yst_mtime;
6005                 in->yst_ctime = oh->yst_ctime;
6006                 in->yst_rdev = oh->yst_rdev;
6007
6008 #endif
6009                 yaffs_SetObjectName(in, oh->name);
6010
6011                 if(in->variantType == YAFFS_OBJECT_TYPE_SYMLINK){
6012                          in->variant.symLinkVariant.alias =
6013                                                     yaffs_CloneString(oh->alias);
6014                         if(!in->variant.symLinkVariant.alias)
6015                                 alloc_failed = 1; /* Not returned to caller */
6016                 }
6017
6018                 yaffs_ReleaseTempBuffer(dev,chunkData, __LINE__);
6019         }
6020 }
6021
6022 static int yaffs_ScanBackwards(yaffs_Device * dev)
6023 {
6024         yaffs_ExtendedTags tags;
6025         int blk;
6026         int blockIterator;
6027         int startIterator;
6028         int endIterator;
6029         int nBlocksToScan = 0;
6030
6031         int chunk;
6032         int result;
6033         int c;
6034         int deleted;
6035         yaffs_BlockState state;
6036         yaffs_Object *hardList = NULL;
6037         yaffs_BlockInfo *bi;
6038         __u32 sequenceNumber;
6039         yaffs_ObjectHeader *oh;
6040         yaffs_Object *in;
6041         yaffs_Object *parent;
6042         int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
6043         int itsUnlinked;
6044         __u8 *chunkData;
6045
6046         int fileSize;
6047         int isShrink;
6048         int foundChunksInBlock;
6049         int equivalentObjectId;
6050         int alloc_failed = 0;
6051
6052
6053         yaffs_BlockIndex *blockIndex = NULL;
6054         int altBlockIndex = 0;
6055
6056         if (!dev->isYaffs2) {
6057                 T(YAFFS_TRACE_SCAN,
6058                   (TSTR("yaffs_ScanBackwards is only for YAFFS2!" TENDSTR)));
6059                 return YAFFS_FAIL;
6060         }
6061
6062         T(YAFFS_TRACE_SCAN,
6063           (TSTR
6064            ("yaffs_ScanBackwards starts  intstartblk %d intendblk %d..."
6065             TENDSTR), dev->internalStartBlock, dev->internalEndBlock));
6066
6067
6068         dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
6069
6070         blockIndex = YMALLOC(nBlocks * sizeof(yaffs_BlockIndex));
6071
6072         if(!blockIndex) {
6073                 blockIndex = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockIndex));
6074                 altBlockIndex = 1;
6075         }
6076
6077         if(!blockIndex) {
6078                 T(YAFFS_TRACE_SCAN,
6079                   (TSTR("yaffs_Scan() could not allocate block index!" TENDSTR)));
6080                 return YAFFS_FAIL;
6081         }
6082
6083         dev->blocksInCheckpoint = 0;
6084
6085         chunkData = yaffs_GetTempBuffer(dev, __LINE__);
6086
6087         /* Scan all the blocks to determine their state */
6088         for (blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++) {
6089                 bi = yaffs_GetBlockInfo(dev, blk);
6090                 yaffs_ClearChunkBits(dev, blk);
6091                 bi->pagesInUse = 0;
6092                 bi->softDeletions = 0;
6093
6094                 yaffs_QueryInitialBlockState(dev, blk, &state, &sequenceNumber);
6095
6096                 bi->blockState = state;
6097                 bi->sequenceNumber = sequenceNumber;
6098
6099                 if(bi->sequenceNumber == YAFFS_SEQUENCE_CHECKPOINT_DATA)
6100                         bi->blockState = state = YAFFS_BLOCK_STATE_CHECKPOINT;
6101
6102                 T(YAFFS_TRACE_SCAN_DEBUG,
6103                   (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
6104                    state, sequenceNumber));
6105
6106
6107                 if(state == YAFFS_BLOCK_STATE_CHECKPOINT){
6108                         dev->blocksInCheckpoint++;
6109
6110                 } else if (state == YAFFS_BLOCK_STATE_DEAD) {
6111                         T(YAFFS_TRACE_BAD_BLOCKS,
6112                           (TSTR("block %d is bad" TENDSTR), blk));
6113                 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
6114                         T(YAFFS_TRACE_SCAN_DEBUG,
6115                           (TSTR("Block empty " TENDSTR)));
6116                         dev->nErasedBlocks++;
6117                         dev->nFreeChunks += dev->nChunksPerBlock;
6118                 } else if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
6119
6120                         /* Determine the highest sequence number */
6121                         if (sequenceNumber >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
6122                             sequenceNumber < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
6123
6124                                 blockIndex[nBlocksToScan].seq = sequenceNumber;
6125                                 blockIndex[nBlocksToScan].block = blk;
6126
6127                                 nBlocksToScan++;
6128
6129                                 if (sequenceNumber >= dev->sequenceNumber) {
6130                                         dev->sequenceNumber = sequenceNumber;
6131                                 }
6132                         } else {
6133                                 /* TODO: Nasty sequence number! */
6134                                 T(YAFFS_TRACE_SCAN,
6135                                   (TSTR
6136                                    ("Block scanning block %d has bad sequence number %d"
6137                                     TENDSTR), blk, sequenceNumber));
6138
6139                         }
6140                 }
6141         }
6142
6143         T(YAFFS_TRACE_SCAN,
6144         (TSTR("%d blocks to be sorted..." TENDSTR), nBlocksToScan));
6145
6146
6147
6148         YYIELD();
6149
6150         /* Sort the blocks */
6151 #ifndef CONFIG_YAFFS_USE_OWN_SORT
6152         {
6153                 /* Use qsort now. */
6154                 yaffs_qsort(blockIndex, nBlocksToScan, sizeof(yaffs_BlockIndex), ybicmp);
6155         }
6156 #else
6157         {
6158                 /* Dungy old bubble sort... */
6159
6160                 yaffs_BlockIndex temp;
6161                 int i;
6162                 int j;
6163
6164                 for (i = 0; i < nBlocksToScan; i++)
6165                         for (j = i + 1; j < nBlocksToScan; j++)
6166                                 if (blockIndex[i].seq > blockIndex[j].seq) {
6167                                         temp = blockIndex[j];
6168                                         blockIndex[j] = blockIndex[i];
6169                                         blockIndex[i] = temp;
6170                                 }
6171         }
6172 #endif
6173
6174         YYIELD();
6175
6176         T(YAFFS_TRACE_SCAN, (TSTR("...done" TENDSTR)));
6177
6178         /* Now scan the blocks looking at the data. */
6179         startIterator = 0;
6180         endIterator = nBlocksToScan - 1;
6181         T(YAFFS_TRACE_SCAN_DEBUG,
6182           (TSTR("%d blocks to be scanned" TENDSTR), nBlocksToScan));
6183
6184         /* For each block.... backwards */
6185         for (blockIterator = endIterator; !alloc_failed && blockIterator >= startIterator;
6186              blockIterator--) {
6187                 /* Cooperative multitasking! This loop can run for so
6188                    long that watchdog timers expire. */
6189                 YYIELD();
6190
6191                 /* get the block to scan in the correct order */
6192                 blk = blockIndex[blockIterator].block;
6193
6194                 bi = yaffs_GetBlockInfo(dev, blk);
6195
6196
6197                 state = bi->blockState;
6198
6199                 deleted = 0;
6200
6201                 /* For each chunk in each block that needs scanning.... */
6202                 foundChunksInBlock = 0;
6203                 for (c = dev->nChunksPerBlock - 1;
6204                      !alloc_failed && c >= 0 &&
6205                      (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
6206                       state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
6207                         /* Scan backwards...
6208                          * Read the tags and decide what to do
6209                          */
6210
6211                         chunk = blk * dev->nChunksPerBlock + c;
6212
6213                         result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk, NULL,
6214                                                         &tags);
6215
6216                         /* Let's have a good look at this chunk... */
6217
6218                         if (!tags.chunkUsed) {
6219                                 /* An unassigned chunk in the block.
6220                                  * If there are used chunks after this one, then
6221                                  * it is a chunk that was skipped due to failing the erased
6222                                  * check. Just skip it so that it can be deleted.
6223                                  * But, more typically, We get here when this is an unallocated
6224                                  * chunk and his means that either the block is empty or
6225                                  * this is the one being allocated from
6226                                  */
6227
6228                                 if(foundChunksInBlock)
6229                                 {
6230                                         /* This is a chunk that was skipped due to failing the erased check */
6231
6232                                 } else if (c == 0) {
6233                                         /* We're looking at the first chunk in the block so the block is unused */
6234                                         state = YAFFS_BLOCK_STATE_EMPTY;
6235                                         dev->nErasedBlocks++;
6236                                 } else {
6237                                         if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
6238                                             state == YAFFS_BLOCK_STATE_ALLOCATING) {
6239                                                 if(dev->sequenceNumber == bi->sequenceNumber) {
6240                                                         /* this is the block being allocated from */
6241
6242                                                         T(YAFFS_TRACE_SCAN,
6243                                                           (TSTR
6244                                                            (" Allocating from %d %d"
6245                                                             TENDSTR), blk, c));
6246
6247                                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
6248                                                         dev->allocationBlock = blk;
6249                                                         dev->allocationPage = c;
6250                                                         dev->allocationBlockFinder = blk;
6251                                                 }
6252                                                 else {
6253                                                         /* This is a partially written block that is not
6254                                                          * the current allocation block. This block must have
6255                                                          * had a write failure, so set up for retirement.
6256                                                          */
6257
6258                                                          /* bi->needsRetiring = 1; ??? TODO */
6259                                                          bi->gcPrioritise = 1;
6260
6261                                                          T(YAFFS_TRACE_ALWAYS,
6262                                                          (TSTR("Partially written block %d detected" TENDSTR),
6263                                                          blk));
6264                                                 }
6265
6266                                         }
6267
6268                                 }
6269
6270                                 dev->nFreeChunks++;
6271
6272                         } else if (tags.chunkId > 0) {
6273                                 /* chunkId > 0 so it is a data chunk... */
6274                                 unsigned int endpos;
6275                                 __u32 chunkBase =
6276                                     (tags.chunkId - 1) * dev->nDataBytesPerChunk;
6277
6278                                 foundChunksInBlock = 1;
6279
6280
6281                                 yaffs_SetChunkBit(dev, blk, c);
6282                                 bi->pagesInUse++;
6283
6284                                 in = yaffs_FindOrCreateObjectByNumber(dev,
6285                                                                       tags.
6286                                                                       objectId,
6287                                                                       YAFFS_OBJECT_TYPE_FILE);
6288                                 if(!in){
6289                                         /* Out of memory */
6290                                         alloc_failed = 1;
6291                                 }
6292
6293                                 if (in &&
6294                                     in->variantType == YAFFS_OBJECT_TYPE_FILE
6295                                     && chunkBase <
6296                                     in->variant.fileVariant.shrinkSize) {
6297                                         /* This has not been invalidated by a resize */
6298                                         if(!yaffs_PutChunkIntoFile(in, tags.chunkId,
6299                                                                chunk, -1)){
6300                                                 alloc_failed = 1;
6301                                         }
6302
6303                                         /* File size is calculated by looking at the data chunks if we have not
6304                                          * seen an object header yet. Stop this practice once we find an object header.
6305                                          */
6306                                         endpos =
6307                                             (tags.chunkId -
6308                                              1) * dev->nDataBytesPerChunk +
6309                                             tags.byteCount;
6310
6311                                         if (!in->valid &&       /* have not got an object header yet */
6312                                             in->variant.fileVariant.
6313                                             scannedFileSize < endpos) {
6314                                                 in->variant.fileVariant.
6315                                                     scannedFileSize = endpos;
6316                                                 in->variant.fileVariant.
6317                                                     fileSize =
6318                                                     in->variant.fileVariant.
6319                                                     scannedFileSize;
6320                                         }
6321
6322                                 } else if(in) {
6323                                         /* This chunk has been invalidated by a resize, so delete */
6324                                         yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
6325
6326                                 }
6327                         } else {
6328                                 /* chunkId == 0, so it is an ObjectHeader.
6329                                  * Thus, we read in the object header and make the object
6330                                  */
6331                                 foundChunksInBlock = 1;
6332
6333                                 yaffs_SetChunkBit(dev, blk, c);
6334                                 bi->pagesInUse++;
6335
6336                                 oh = NULL;
6337                                 in = NULL;
6338
6339                                 if (tags.extraHeaderInfoAvailable) {
6340                                         in = yaffs_FindOrCreateObjectByNumber
6341                                             (dev, tags.objectId,
6342                                              tags.extraObjectType);
6343                                 }
6344
6345                                 if (!in ||
6346 #ifdef CONFIG_YAFFS_DISABLE_LAZY_LOAD
6347                                     !in->valid ||
6348 #endif
6349                                     tags.extraShadows ||
6350                                     (!in->valid &&
6351                                     (tags.objectId == YAFFS_OBJECTID_ROOT ||
6352                                      tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))
6353                                     ) {
6354
6355                                         /* If we don't have  valid info then we need to read the chunk
6356                                          * TODO In future we can probably defer reading the chunk and
6357                                          * living with invalid data until needed.
6358                                          */
6359
6360                                         result = yaffs_ReadChunkWithTagsFromNAND(dev,
6361                                                                         chunk,
6362                                                                         chunkData,
6363                                                                         NULL);
6364
6365                                         oh = (yaffs_ObjectHeader *) chunkData;
6366
6367                                         if(dev->inbandTags){
6368                                                 /* Fix up the header if they got corrupted by inband tags */
6369                                                 oh->shadowsObject = oh->inbandShadowsObject;
6370                                                 oh->isShrink = oh->inbandIsShrink;
6371                                         }
6372
6373                                         if (!in)
6374                                                 in = yaffs_FindOrCreateObjectByNumber(dev, tags.objectId, oh->type);
6375
6376                                 }
6377
6378                                 if (!in) {
6379                                         /* TODO Hoosterman we have a problem! */
6380                                         T(YAFFS_TRACE_ERROR,
6381                                           (TSTR
6382                                            ("yaffs tragedy: Could not make object for object  %d at chunk %d during scan"
6383                                             TENDSTR), tags.objectId, chunk));
6384
6385                                 }
6386
6387                                 if (in->valid) {
6388                                         /* We have already filled this one.
6389                                          * We have a duplicate that will be discarded, but
6390                                          * we first have to suck out resize info if it is a file.
6391                                          */
6392
6393                                         if ((in->variantType == YAFFS_OBJECT_TYPE_FILE) &&
6394                                              ((oh &&
6395                                                oh-> type == YAFFS_OBJECT_TYPE_FILE)||
6396                                               (tags.extraHeaderInfoAvailable  &&
6397                                                tags.extraObjectType == YAFFS_OBJECT_TYPE_FILE))
6398                                             ) {
6399                                                 __u32 thisSize =
6400                                                     (oh) ? oh->fileSize : tags.
6401                                                     extraFileLength;
6402                                                 __u32 parentObjectId =
6403                                                     (oh) ? oh->
6404                                                     parentObjectId : tags.
6405                                                     extraParentObjectId;
6406
6407
6408                                                 isShrink =
6409                                                     (oh) ? oh->isShrink : tags.
6410                                                     extraIsShrinkHeader;
6411
6412                                                 /* If it is deleted (unlinked at start also means deleted)
6413                                                  * we treat the file size as being zeroed at this point.
6414                                                  */
6415                                                 if (parentObjectId ==
6416                                                     YAFFS_OBJECTID_DELETED
6417                                                     || parentObjectId ==
6418                                                     YAFFS_OBJECTID_UNLINKED) {
6419                                                         thisSize = 0;
6420                                                         isShrink = 1;
6421                                                 }
6422
6423                                                 if (isShrink &&
6424                                                     in->variant.fileVariant.
6425                                                     shrinkSize > thisSize) {
6426                                                         in->variant.fileVariant.
6427                                                             shrinkSize =
6428                                                             thisSize;
6429                                                 }
6430
6431                                                 if (isShrink) {
6432                                                         bi->hasShrinkHeader = 1;
6433                                                 }
6434
6435                                         }
6436                                         /* Use existing - destroy this one. */
6437                                         yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
6438
6439                                 }
6440
6441                                 if (!in->valid &&
6442                                     (tags.objectId == YAFFS_OBJECTID_ROOT ||
6443                                      tags.objectId ==
6444                                      YAFFS_OBJECTID_LOSTNFOUND)) {
6445                                         /* We only load some info, don't fiddle with directory structure */
6446                                         in->valid = 1;
6447
6448                                         if(oh) {
6449                                                 in->variantType = oh->type;
6450
6451                                                 in->yst_mode = oh->yst_mode;
6452 #ifdef CONFIG_YAFFS_WINCE
6453                                                 in->win_atime[0] = oh->win_atime[0];
6454                                                 in->win_ctime[0] = oh->win_ctime[0];
6455                                                 in->win_mtime[0] = oh->win_mtime[0];
6456                                                 in->win_atime[1] = oh->win_atime[1];
6457                                                 in->win_ctime[1] = oh->win_ctime[1];
6458                                                 in->win_mtime[1] = oh->win_mtime[1];
6459 #else
6460                                                 in->yst_uid = oh->yst_uid;
6461                                                 in->yst_gid = oh->yst_gid;
6462                                                 in->yst_atime = oh->yst_atime;
6463                                                 in->yst_mtime = oh->yst_mtime;
6464                                                 in->yst_ctime = oh->yst_ctime;
6465                                                 in->yst_rdev = oh->yst_rdev;
6466
6467 #endif
6468                                         } else {
6469                                                 in->variantType = tags.extraObjectType;
6470                                                 in->lazyLoaded = 1;
6471                                         }
6472
6473                                         in->hdrChunk = chunk;
6474
6475                                 } else if (!in->valid) {
6476                                         /* we need to load this info */
6477
6478                                         in->valid = 1;
6479                                         in->hdrChunk = chunk;
6480
6481                                         if(oh) {
6482                                                 in->variantType = oh->type;
6483
6484                                                 in->yst_mode = oh->yst_mode;
6485 #ifdef CONFIG_YAFFS_WINCE
6486                                                 in->win_atime[0] = oh->win_atime[0];
6487                                                 in->win_ctime[0] = oh->win_ctime[0];
6488                                                 in->win_mtime[0] = oh->win_mtime[0];
6489                                                 in->win_atime[1] = oh->win_atime[1];
6490                                                 in->win_ctime[1] = oh->win_ctime[1];
6491                                                 in->win_mtime[1] = oh->win_mtime[1];
6492 #else
6493                                                 in->yst_uid = oh->yst_uid;
6494                                                 in->yst_gid = oh->yst_gid;
6495                                                 in->yst_atime = oh->yst_atime;
6496                                                 in->yst_mtime = oh->yst_mtime;
6497                                                 in->yst_ctime = oh->yst_ctime;
6498                                                 in->yst_rdev = oh->yst_rdev;
6499 #endif
6500
6501                                                 if (oh->shadowsObject > 0)
6502                                                         yaffs_HandleShadowedObject(dev,
6503                                                                            oh->
6504                                                                            shadowsObject,
6505                                                                            1);
6506
6507
6508                                                 yaffs_SetObjectName(in, oh->name);
6509                                                 parent =
6510                                                     yaffs_FindOrCreateObjectByNumber
6511                                                         (dev, oh->parentObjectId,
6512                                                          YAFFS_OBJECT_TYPE_DIRECTORY);
6513
6514                                                  fileSize = oh->fileSize;
6515                                                  isShrink = oh->isShrink;
6516                                                  equivalentObjectId = oh->equivalentObjectId;
6517
6518                                         }
6519                                         else {
6520                                                 in->variantType = tags.extraObjectType;
6521                                                 parent =
6522                                                     yaffs_FindOrCreateObjectByNumber
6523                                                         (dev, tags.extraParentObjectId,
6524                                                          YAFFS_OBJECT_TYPE_DIRECTORY);
6525                                                  fileSize = tags.extraFileLength;
6526                                                  isShrink = tags.extraIsShrinkHeader;
6527                                                  equivalentObjectId = tags.extraEquivalentObjectId;
6528                                                 in->lazyLoaded = 1;
6529
6530                                         }
6531                                         in->dirty = 0;
6532
6533                                         /* directory stuff...
6534                                          * hook up to parent
6535                                          */
6536
6537                                         if (parent->variantType ==
6538                                             YAFFS_OBJECT_TYPE_UNKNOWN) {
6539                                                 /* Set up as a directory */
6540                                                 parent->variantType =
6541                                                     YAFFS_OBJECT_TYPE_DIRECTORY;
6542                                                 YINIT_LIST_HEAD(&parent->variant.
6543                                                                directoryVariant.
6544                                                                children);
6545                                         } else if (parent->variantType !=
6546                                                    YAFFS_OBJECT_TYPE_DIRECTORY)
6547                                         {
6548                                                 /* Hoosterman, another problem....
6549                                                  * We're trying to use a non-directory as a directory
6550                                                  */
6551
6552                                                 T(YAFFS_TRACE_ERROR,
6553                                                   (TSTR
6554                                                    ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
6555                                                     TENDSTR)));
6556                                                 parent = dev->lostNFoundDir;
6557                                         }
6558
6559                                         yaffs_AddObjectToDirectory(parent, in);
6560
6561                                         itsUnlinked = (parent == dev->deletedDir) ||
6562                                                       (parent == dev->unlinkedDir);
6563
6564                                         if (isShrink) {
6565                                                 /* Mark the block as having a shrinkHeader */
6566                                                 bi->hasShrinkHeader = 1;
6567                                         }
6568
6569                                         /* Note re hardlinks.
6570                                          * Since we might scan a hardlink before its equivalent object is scanned
6571                                          * we put them all in a list.
6572                                          * After scanning is complete, we should have all the objects, so we run
6573                                          * through this list and fix up all the chains.
6574                                          */
6575
6576                                         switch (in->variantType) {
6577                                         case YAFFS_OBJECT_TYPE_UNKNOWN:
6578                                                 /* Todo got a problem */
6579                                                 break;
6580                                         case YAFFS_OBJECT_TYPE_FILE:
6581
6582                                                 if (in->variant.fileVariant.
6583                                                     scannedFileSize < fileSize) {
6584                                                         /* This covers the case where the file size is greater
6585                                                          * than where the data is
6586                                                          * This will happen if the file is resized to be larger
6587                                                          * than its current data extents.
6588                                                          */
6589                                                         in->variant.fileVariant.fileSize = fileSize;
6590                                                         in->variant.fileVariant.scannedFileSize =
6591                                                             in->variant.fileVariant.fileSize;
6592                                                 }
6593
6594                                                 if (isShrink &&
6595                                                     in->variant.fileVariant.shrinkSize > fileSize) {
6596                                                         in->variant.fileVariant.shrinkSize = fileSize;
6597                                                 }
6598
6599                                                 break;
6600                                         case YAFFS_OBJECT_TYPE_HARDLINK:
6601                                                 if(!itsUnlinked) {
6602                                                   in->variant.hardLinkVariant.equivalentObjectId =
6603                                                     equivalentObjectId;
6604                                                   in->hardLinks.next =
6605                                                     (struct ylist_head *) hardList;
6606                                                   hardList = in;
6607                                                 }
6608                                                 break;
6609                                         case YAFFS_OBJECT_TYPE_DIRECTORY:
6610                                                 /* Do nothing */
6611                                                 break;
6612                                         case YAFFS_OBJECT_TYPE_SPECIAL:
6613                                                 /* Do nothing */
6614                                                 break;
6615                                         case YAFFS_OBJECT_TYPE_SYMLINK:
6616                                                 if(oh){
6617                                                    in->variant.symLinkVariant.alias =
6618                                                     yaffs_CloneString(oh->
6619                                                                       alias);
6620                                                    if(!in->variant.symLinkVariant.alias)
6621                                                         alloc_failed = 1;
6622                                                 }
6623                                                 break;
6624                                         }
6625
6626                                 }
6627
6628                         }
6629
6630                 } /* End of scanning for each chunk */
6631
6632                 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
6633                         /* If we got this far while scanning, then the block is fully allocated. */
6634                         state = YAFFS_BLOCK_STATE_FULL;
6635                 }
6636
6637                 bi->blockState = state;
6638
6639                 /* Now let's see if it was dirty */
6640                 if (bi->pagesInUse == 0 &&
6641                     !bi->hasShrinkHeader &&
6642                     bi->blockState == YAFFS_BLOCK_STATE_FULL) {
6643                         yaffs_BlockBecameDirty(dev, blk);
6644                 }
6645
6646         }
6647
6648         if (altBlockIndex)
6649                 YFREE_ALT(blockIndex);
6650         else
6651                 YFREE(blockIndex);
6652
6653         /* Ok, we've done all the scanning.
6654          * Fix up the hard link chains.
6655          * We should now have scanned all the objects, now it's time to add these
6656          * hardlinks.
6657          */
6658         yaffs_HardlinkFixup(dev,hardList);
6659
6660
6661         /*
6662         *  Sort out state of unlinked and deleted objects.
6663         */
6664         {
6665                 struct ylist_head *i;
6666                 struct ylist_head *n;
6667
6668                 yaffs_Object *l;
6669
6670                 /* Soft delete all the unlinked files */
6671                 ylist_for_each_safe(i, n,
6672                                    &dev->unlinkedDir->variant.directoryVariant.
6673                                    children) {
6674                         if (i) {
6675                                 l = ylist_entry(i, yaffs_Object, siblings);
6676                                 yaffs_DestroyObject(l);
6677                         }
6678                 }
6679
6680                 /* Soft delete all the deletedDir files */
6681                 ylist_for_each_safe(i, n,
6682                                    &dev->deletedDir->variant.directoryVariant.
6683                                    children) {
6684                         if (i) {
6685                                 l = ylist_entry(i, yaffs_Object, siblings);
6686                                 yaffs_DestroyObject(l);
6687
6688                         }
6689                 }
6690         }
6691
6692         yaffs_ReleaseTempBuffer(dev, chunkData, __LINE__);
6693
6694         if(alloc_failed){
6695                 return YAFFS_FAIL;
6696         }
6697
6698         T(YAFFS_TRACE_SCAN, (TSTR("yaffs_ScanBackwards ends" TENDSTR)));
6699
6700         return YAFFS_OK;
6701 }
6702
6703 /*------------------------------  Directory Functions ----------------------------- */
6704
6705 static void yaffs_VerifyObjectInDirectory(yaffs_Object *obj)
6706 {
6707         struct ylist_head *lh;
6708         yaffs_Object *listObj;
6709
6710         int count = 0;
6711
6712         if(!obj){
6713                 T(YAFFS_TRACE_ALWAYS, (TSTR("No object to verify" TENDSTR)));
6714                 YBUG();
6715         }
6716
6717         if(yaffs_SkipVerification(obj->myDev))
6718                 return;
6719
6720         if(!obj->parent){
6721                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object does not have parent" TENDSTR)));
6722                 YBUG();
6723         }
6724
6725         if(obj->parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY){
6726                 T(YAFFS_TRACE_ALWAYS, (TSTR("Parent is not directory" TENDSTR)));
6727                 YBUG();
6728         }
6729
6730         /* Iterate through the objects in each hash entry */
6731
6732         ylist_for_each(lh, &obj->parent->variant.directoryVariant.children) {
6733                 if (lh) {
6734                         listObj = ylist_entry(lh, yaffs_Object, siblings);
6735                         yaffs_VerifyObject(listObj);
6736                         if(obj == listObj)
6737                                 count ++;
6738                 }
6739          }
6740
6741          if(count != 1){
6742                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory %d times" TENDSTR),count));
6743                 YBUG();
6744         }
6745
6746 }
6747
6748 static void yaffs_VerifyDirectory(yaffs_Object *directory)
6749 {
6750
6751         struct ylist_head *lh;
6752         yaffs_Object *listObj;
6753
6754         if(!directory)
6755                 YBUG();
6756
6757         if(yaffs_SkipFullVerification(directory->myDev))
6758                 return;
6759
6760
6761         if(directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY){
6762                 T(YAFFS_TRACE_ALWAYS, (TSTR("Directory has wrong type: %d" TENDSTR),directory->variantType));
6763                 YBUG();
6764         }
6765
6766         /* Iterate through the objects in each hash entry */
6767
6768         ylist_for_each(lh, &directory->variant.directoryVariant.children) {
6769                 if (lh) {
6770                         listObj = ylist_entry(lh, yaffs_Object, siblings);
6771                         if(listObj->parent != directory){
6772                                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory list has wrong parent %p" TENDSTR),listObj->parent));
6773                                 YBUG();
6774                         }
6775                         yaffs_VerifyObjectInDirectory(listObj);
6776                 }
6777          }
6778
6779 }
6780
6781
6782 static void yaffs_RemoveObjectFromDirectory(yaffs_Object * obj)
6783 {
6784         yaffs_Device *dev = obj->myDev;
6785         yaffs_Object *parent;
6786
6787         yaffs_VerifyObjectInDirectory(obj);
6788         parent = obj->parent;
6789
6790         yaffs_VerifyDirectory(parent);
6791
6792         if(dev && dev->removeObjectCallback)
6793                 dev->removeObjectCallback(obj);
6794
6795
6796         ylist_del_init(&obj->siblings);
6797         obj->parent = NULL;
6798
6799         yaffs_VerifyDirectory(parent);
6800
6801 }
6802
6803
6804 static void yaffs_AddObjectToDirectory(yaffs_Object * directory,
6805                                        yaffs_Object * obj)
6806 {
6807
6808         if (!directory) {
6809                 T(YAFFS_TRACE_ALWAYS,
6810                   (TSTR
6811                    ("tragedy: Trying to add an object to a null pointer directory"
6812                     TENDSTR)));
6813                 YBUG();
6814         }
6815         if (directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
6816                 T(YAFFS_TRACE_ALWAYS,
6817                   (TSTR
6818                    ("tragedy: Trying to add an object to a non-directory"
6819                     TENDSTR)));
6820                 YBUG();
6821         }
6822
6823         if (obj->siblings.prev == NULL) {
6824                 /* Not initialised */
6825                 YBUG();
6826
6827         } else if (ylist_empty(&obj->siblings)) {
6828                 YBUG();
6829         }
6830
6831
6832         yaffs_VerifyDirectory(directory);
6833
6834         yaffs_RemoveObjectFromDirectory(obj);
6835
6836
6837         /* Now add it */
6838         ylist_add(&obj->siblings, &directory->variant.directoryVariant.children);
6839         obj->parent = directory;
6840
6841         if (directory == obj->myDev->unlinkedDir
6842             || directory == obj->myDev->deletedDir) {
6843                 obj->unlinked = 1;
6844                 obj->myDev->nUnlinkedFiles++;
6845                 obj->renameAllowed = 0;
6846         }
6847
6848         yaffs_VerifyDirectory(directory);
6849         yaffs_VerifyObjectInDirectory(obj);
6850
6851
6852 }
6853
6854 yaffs_Object *yaffs_FindObjectByName(yaffs_Object * directory,
6855                                      const YCHAR * name)
6856 {
6857         int sum;
6858
6859         struct ylist_head *i;
6860         YCHAR buffer[YAFFS_MAX_NAME_LENGTH + 1];
6861
6862         yaffs_Object *l;
6863
6864         if (!name) {
6865                 return NULL;
6866         }
6867
6868         if (!directory) {
6869                 T(YAFFS_TRACE_ALWAYS,
6870                   (TSTR
6871                    ("tragedy: yaffs_FindObjectByName: null pointer directory"
6872                     TENDSTR)));
6873                 YBUG();
6874         }
6875         if (directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
6876                 T(YAFFS_TRACE_ALWAYS,
6877                   (TSTR
6878                    ("tragedy: yaffs_FindObjectByName: non-directory" TENDSTR)));
6879                 YBUG();
6880         }
6881
6882         sum = yaffs_CalcNameSum(name);
6883
6884         ylist_for_each(i, &directory->variant.directoryVariant.children) {
6885                 if (i) {
6886                         l = ylist_entry(i, yaffs_Object, siblings);
6887
6888                         if(l->parent != directory)
6889                                 YBUG();
6890
6891                         yaffs_CheckObjectDetailsLoaded(l);
6892
6893                         /* Special case for lost-n-found */
6894                         if (l->objectId == YAFFS_OBJECTID_LOSTNFOUND) {
6895                                 if (yaffs_strcmp(name, YAFFS_LOSTNFOUND_NAME) == 0) {
6896                                         return l;
6897                                 }
6898                         } else if (yaffs_SumCompare(l->sum, sum) || l->hdrChunk <= 0){
6899                                 /* LostnFound chunk called Objxxx
6900                                  * Do a real check
6901                                  */
6902                                 yaffs_GetObjectName(l, buffer,
6903                                                     YAFFS_MAX_NAME_LENGTH);
6904                                 if (yaffs_strncmp(name, buffer,YAFFS_MAX_NAME_LENGTH) == 0) {
6905                                         return l;
6906                                 }
6907
6908                         }
6909                 }
6910         }
6911
6912         return NULL;
6913 }
6914
6915
6916 #if 0
6917 int yaffs_ApplyToDirectoryChildren(yaffs_Object * theDir,
6918                                    int (*fn) (yaffs_Object *))
6919 {
6920         struct ylist_head *i;
6921         yaffs_Object *l;
6922
6923         if (!theDir) {
6924                 T(YAFFS_TRACE_ALWAYS,
6925                   (TSTR
6926                    ("tragedy: yaffs_FindObjectByName: null pointer directory"
6927                     TENDSTR)));
6928                 YBUG();
6929         }
6930         if (theDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
6931                 T(YAFFS_TRACE_ALWAYS,
6932                   (TSTR
6933                    ("tragedy: yaffs_FindObjectByName: non-directory" TENDSTR)));
6934                 YBUG();
6935         }
6936
6937         ylist_for_each(i, &theDir->variant.directoryVariant.children) {
6938                 if (i) {
6939                         l = ylist_entry(i, yaffs_Object, siblings);
6940                         if (l && !fn(l)) {
6941                                 return YAFFS_FAIL;
6942                         }
6943                 }
6944         }
6945
6946         return YAFFS_OK;
6947
6948 }
6949 #endif
6950
6951 /* GetEquivalentObject dereferences any hard links to get to the
6952  * actual object.
6953  */
6954
6955 yaffs_Object *yaffs_GetEquivalentObject(yaffs_Object * obj)
6956 {
6957         if (obj && obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
6958                 /* We want the object id of the equivalent object, not this one */
6959                 obj = obj->variant.hardLinkVariant.equivalentObject;
6960                 yaffs_CheckObjectDetailsLoaded(obj);
6961         }
6962         return obj;
6963
6964 }
6965
6966 int yaffs_GetObjectName(yaffs_Object * obj, YCHAR * name, int buffSize)
6967 {
6968         memset(name, 0, buffSize * sizeof(YCHAR));
6969
6970         yaffs_CheckObjectDetailsLoaded(obj);
6971
6972         if (obj->objectId == YAFFS_OBJECTID_LOSTNFOUND) {
6973                 yaffs_strncpy(name, YAFFS_LOSTNFOUND_NAME, buffSize - 1);
6974         } else if (obj->hdrChunk <= 0) {
6975                 YCHAR locName[20];
6976                 YCHAR numString[20];
6977                 YCHAR *x = &numString[19];
6978                 unsigned v = obj->objectId;
6979                 numString[19] = 0;
6980                 while(v>0){
6981                         x--;
6982                         *x = '0' + (v % 10);
6983                         v /= 10;
6984                 }
6985                 /* make up a name */
6986                 yaffs_strcpy(locName, YAFFS_LOSTNFOUND_PREFIX);
6987                 yaffs_strcat(locName,x);
6988                 yaffs_strncpy(name, locName, buffSize - 1);
6989
6990         }
6991 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
6992         else if (obj->shortName[0]) {
6993                 yaffs_strcpy(name, obj->shortName);
6994         }
6995 #endif
6996         else {
6997                 int result;
6998                 __u8 *buffer = yaffs_GetTempBuffer(obj->myDev, __LINE__);
6999
7000                 yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *) buffer;
7001
7002                 memset(buffer, 0, obj->myDev->nDataBytesPerChunk);
7003
7004                 if (obj->hdrChunk > 0) {
7005                         result = yaffs_ReadChunkWithTagsFromNAND(obj->myDev,
7006                                                         obj->hdrChunk, buffer,
7007                                                         NULL);
7008                 }
7009                 yaffs_strncpy(name, oh->name, buffSize - 1);
7010
7011                 yaffs_ReleaseTempBuffer(obj->myDev, buffer, __LINE__);
7012         }
7013
7014         return yaffs_strlen(name);
7015 }
7016
7017 int yaffs_GetObjectFileLength(yaffs_Object * obj)
7018 {
7019
7020         /* Dereference any hard linking */
7021         obj = yaffs_GetEquivalentObject(obj);
7022
7023         if (obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
7024                 return obj->variant.fileVariant.fileSize;
7025         }
7026         if (obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK) {
7027                 return yaffs_strlen(obj->variant.symLinkVariant.alias);
7028         } else {
7029                 /* Only a directory should drop through to here */
7030                 return obj->myDev->nDataBytesPerChunk;
7031         }
7032 }
7033
7034 int yaffs_GetObjectLinkCount(yaffs_Object * obj)
7035 {
7036         int count = 0;
7037         struct ylist_head *i;
7038
7039         if (!obj->unlinked) {
7040                 count++;        /* the object itself */
7041         }
7042         ylist_for_each(i, &obj->hardLinks) {
7043                 count++;        /* add the hard links; */
7044         }
7045         return count;
7046
7047 }
7048
7049 int yaffs_GetObjectInode(yaffs_Object * obj)
7050 {
7051         obj = yaffs_GetEquivalentObject(obj);
7052
7053         return obj->objectId;
7054 }
7055
7056 unsigned yaffs_GetObjectType(yaffs_Object * obj)
7057 {
7058         obj = yaffs_GetEquivalentObject(obj);
7059
7060         switch (obj->variantType) {
7061         case YAFFS_OBJECT_TYPE_FILE:
7062                 return DT_REG;
7063                 break;
7064         case YAFFS_OBJECT_TYPE_DIRECTORY:
7065                 return DT_DIR;
7066                 break;
7067         case YAFFS_OBJECT_TYPE_SYMLINK:
7068                 return DT_LNK;
7069                 break;
7070         case YAFFS_OBJECT_TYPE_HARDLINK:
7071                 return DT_REG;
7072                 break;
7073         case YAFFS_OBJECT_TYPE_SPECIAL:
7074                 if (S_ISFIFO(obj->yst_mode))
7075                         return DT_FIFO;
7076                 if (S_ISCHR(obj->yst_mode))
7077                         return DT_CHR;
7078                 if (S_ISBLK(obj->yst_mode))
7079                         return DT_BLK;
7080                 if (S_ISSOCK(obj->yst_mode))
7081                         return DT_SOCK;
7082         default:
7083                 return DT_REG;
7084                 break;
7085         }
7086 }
7087
7088 YCHAR *yaffs_GetSymlinkAlias(yaffs_Object * obj)
7089 {
7090         obj = yaffs_GetEquivalentObject(obj);
7091         if (obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK) {
7092                 return yaffs_CloneString(obj->variant.symLinkVariant.alias);
7093         } else {
7094                 return yaffs_CloneString(_Y(""));
7095         }
7096 }
7097
7098 #ifndef CONFIG_YAFFS_WINCE
7099
7100 int yaffs_SetAttributes(yaffs_Object * obj, struct iattr *attr)
7101 {
7102         unsigned int valid = attr->ia_valid;
7103
7104         if (valid & ATTR_MODE)
7105                 obj->yst_mode = attr->ia_mode;
7106         if (valid & ATTR_UID)
7107                 obj->yst_uid = attr->ia_uid;
7108         if (valid & ATTR_GID)
7109                 obj->yst_gid = attr->ia_gid;
7110
7111         if (valid & ATTR_ATIME)
7112                 obj->yst_atime = Y_TIME_CONVERT(attr->ia_atime);
7113         if (valid & ATTR_CTIME)
7114                 obj->yst_ctime = Y_TIME_CONVERT(attr->ia_ctime);
7115         if (valid & ATTR_MTIME)
7116                 obj->yst_mtime = Y_TIME_CONVERT(attr->ia_mtime);
7117
7118         if (valid & ATTR_SIZE)
7119                 yaffs_ResizeFile(obj, attr->ia_size);
7120
7121         yaffs_UpdateObjectHeader(obj, NULL, 1, 0, 0);
7122
7123         return YAFFS_OK;
7124
7125 }
7126 int yaffs_GetAttributes(yaffs_Object * obj, struct iattr *attr)
7127 {
7128         unsigned int valid = 0;
7129
7130         attr->ia_mode = obj->yst_mode;
7131         valid |= ATTR_MODE;
7132         attr->ia_uid = obj->yst_uid;
7133         valid |= ATTR_UID;
7134         attr->ia_gid = obj->yst_gid;
7135         valid |= ATTR_GID;
7136
7137         Y_TIME_CONVERT(attr->ia_atime) = obj->yst_atime;
7138         valid |= ATTR_ATIME;
7139         Y_TIME_CONVERT(attr->ia_ctime) = obj->yst_ctime;
7140         valid |= ATTR_CTIME;
7141         Y_TIME_CONVERT(attr->ia_mtime) = obj->yst_mtime;
7142         valid |= ATTR_MTIME;
7143
7144         attr->ia_size = yaffs_GetFileSize(obj);
7145         valid |= ATTR_SIZE;
7146
7147         attr->ia_valid = valid;
7148
7149         return YAFFS_OK;
7150
7151 }
7152
7153 #endif
7154
7155 #if 0
7156 int yaffs_DumpObject(yaffs_Object * obj)
7157 {
7158         YCHAR name[257];
7159
7160         yaffs_GetObjectName(obj, name, 256);
7161
7162         T(YAFFS_TRACE_ALWAYS,
7163           (TSTR
7164            ("Object %d, inode %d \"%s\"\n dirty %d valid %d serial %d sum %d"
7165             " chunk %d type %d size %d\n"
7166             TENDSTR), obj->objectId, yaffs_GetObjectInode(obj), name,
7167            obj->dirty, obj->valid, obj->serial, obj->sum, obj->hdrChunk,
7168            yaffs_GetObjectType(obj), yaffs_GetObjectFileLength(obj)));
7169
7170         return YAFFS_OK;
7171 }
7172 #endif
7173
7174 /*---------------------------- Initialisation code -------------------------------------- */
7175
7176 static int yaffs_CheckDevFunctions(const yaffs_Device * dev)
7177 {
7178
7179         /* Common functions, gotta have */
7180         if (!dev->eraseBlockInNAND || !dev->initialiseNAND)
7181                 return 0;
7182
7183 #ifdef CONFIG_YAFFS_YAFFS2
7184
7185         /* Can use the "with tags" style interface for yaffs1 or yaffs2 */
7186         if (dev->writeChunkWithTagsToNAND &&
7187             dev->readChunkWithTagsFromNAND &&
7188             !dev->writeChunkToNAND &&
7189             !dev->readChunkFromNAND &&
7190             dev->markNANDBlockBad && dev->queryNANDBlock)
7191                 return 1;
7192 #endif
7193
7194         /* Can use the "spare" style interface for yaffs1 */
7195         if (!dev->isYaffs2 &&
7196             !dev->writeChunkWithTagsToNAND &&
7197             !dev->readChunkWithTagsFromNAND &&
7198             dev->writeChunkToNAND &&
7199             dev->readChunkFromNAND &&
7200             !dev->markNANDBlockBad && !dev->queryNANDBlock)
7201                 return 1;
7202
7203         return 0;               /* bad */
7204 }
7205
7206
7207 static int yaffs_CreateInitialDirectories(yaffs_Device *dev)
7208 {
7209         /* Initialise the unlinked, deleted, root and lost and found directories */
7210
7211         dev->lostNFoundDir = dev->rootDir =  NULL;
7212         dev->unlinkedDir = dev->deletedDir = NULL;
7213
7214         dev->unlinkedDir =
7215             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_UNLINKED, S_IFDIR);
7216
7217         dev->deletedDir =
7218             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_DELETED, S_IFDIR);
7219
7220         dev->rootDir =
7221             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_ROOT,
7222                                       YAFFS_ROOT_MODE | S_IFDIR);
7223         dev->lostNFoundDir =
7224             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_LOSTNFOUND,
7225                                       YAFFS_LOSTNFOUND_MODE | S_IFDIR);
7226
7227         if(dev->lostNFoundDir && dev->rootDir && dev->unlinkedDir && dev->deletedDir){
7228                 yaffs_AddObjectToDirectory(dev->rootDir, dev->lostNFoundDir);
7229                 return YAFFS_OK;
7230         }
7231
7232         return YAFFS_FAIL;
7233 }
7234
7235 int yaffs_GutsInitialise(yaffs_Device * dev)
7236 {
7237         int init_failed = 0;
7238         unsigned x;
7239         int bits;
7240
7241         T(YAFFS_TRACE_TRACING, (TSTR("yaffs: yaffs_GutsInitialise()" TENDSTR)));
7242
7243         /* Check stuff that must be set */
7244
7245         if (!dev) {
7246                 T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs: Need a device" TENDSTR)));
7247                 return YAFFS_FAIL;
7248         }
7249
7250         dev->internalStartBlock = dev->startBlock;
7251         dev->internalEndBlock = dev->endBlock;
7252         dev->blockOffset = 0;
7253         dev->chunkOffset = 0;
7254         dev->nFreeChunks = 0;
7255
7256         dev->gcBlock = -1;
7257
7258         if (dev->startBlock == 0) {
7259                 dev->internalStartBlock = dev->startBlock + 1;
7260                 dev->internalEndBlock = dev->endBlock + 1;
7261                 dev->blockOffset = 1;
7262                 dev->chunkOffset = dev->nChunksPerBlock;
7263         }
7264
7265         /* Check geometry parameters. */
7266
7267         if ((!dev->inbandTags && dev->isYaffs2 && dev->totalBytesPerChunk < 1024) ||
7268             (!dev->isYaffs2 && dev->totalBytesPerChunk < 512) ||
7269             (dev->inbandTags && !dev->isYaffs2 ) ||
7270              dev->nChunksPerBlock < 2 ||
7271              dev->nReservedBlocks < 2 ||
7272              dev->internalStartBlock <= 0 ||
7273              dev->internalEndBlock <= 0 ||
7274              dev->internalEndBlock <= (dev->internalStartBlock + dev->nReservedBlocks + 2)      // otherwise it is too small
7275             ) {
7276                 T(YAFFS_TRACE_ALWAYS,
7277                   (TSTR
7278                    ("yaffs: NAND geometry problems: chunk size %d, type is yaffs%s, inbandTags %d "
7279                     TENDSTR), dev->totalBytesPerChunk, dev->isYaffs2 ? "2" : "", dev->inbandTags));
7280                 return YAFFS_FAIL;
7281         }
7282
7283         if (yaffs_InitialiseNAND(dev) != YAFFS_OK) {
7284                 T(YAFFS_TRACE_ALWAYS,
7285                   (TSTR("yaffs: InitialiseNAND failed" TENDSTR)));
7286                 return YAFFS_FAIL;
7287         }
7288
7289         /* Sort out space for inband tags, if required */
7290         if(dev->inbandTags)
7291                 dev->nDataBytesPerChunk = dev->totalBytesPerChunk - sizeof(yaffs_PackedTags2TagsPart);
7292         else
7293                 dev->nDataBytesPerChunk = dev->totalBytesPerChunk;
7294
7295         /* Got the right mix of functions? */
7296         if (!yaffs_CheckDevFunctions(dev)) {
7297                 /* Function missing */
7298                 T(YAFFS_TRACE_ALWAYS,
7299                   (TSTR
7300                    ("yaffs: device function(s) missing or wrong\n" TENDSTR)));
7301
7302                 return YAFFS_FAIL;
7303         }
7304
7305         /* This is really a compilation check. */
7306         if (!yaffs_CheckStructures()) {
7307                 T(YAFFS_TRACE_ALWAYS,
7308                   (TSTR("yaffs_CheckStructures failed\n" TENDSTR)));
7309                 return YAFFS_FAIL;
7310         }
7311
7312         if (dev->isMounted) {
7313                 T(YAFFS_TRACE_ALWAYS,
7314                   (TSTR("yaffs: device already mounted\n" TENDSTR)));
7315                 return YAFFS_FAIL;
7316         }
7317
7318         /* Finished with most checks. One or two more checks happen later on too. */
7319
7320         dev->isMounted = 1;
7321
7322         /* OK now calculate a few things for the device */
7323
7324         /*
7325          *  Calculate all the chunk size manipulation numbers:
7326          */
7327         x = dev->nDataBytesPerChunk;
7328         /* We always use dev->chunkShift and dev->chunkDiv */
7329         dev->chunkShift = Shifts(x);
7330         x >>= dev->chunkShift;
7331         dev->chunkDiv = x;
7332         /* We only use chunk mask if chunkDiv is 1 */
7333         dev->chunkMask = (1<<dev->chunkShift) - 1;
7334
7335         /*
7336          * Calculate chunkGroupBits.
7337          * We need to find the next power of 2 > than internalEndBlock
7338          */
7339
7340         x = dev->nChunksPerBlock * (dev->internalEndBlock + 1);
7341
7342         bits = ShiftsGE(x);
7343
7344         /* Set up tnode width if wide tnodes are enabled. */
7345         if(!dev->wideTnodesDisabled){
7346                 /* bits must be even so that we end up with 32-bit words */
7347                 if(bits & 1)
7348                         bits++;
7349                 if(bits < 16)
7350                         dev->tnodeWidth = 16;
7351                 else
7352                         dev->tnodeWidth = bits;
7353         }
7354         else
7355                 dev->tnodeWidth = 16;
7356
7357         dev->tnodeMask = (1<<dev->tnodeWidth)-1;
7358
7359         /* Level0 Tnodes are 16 bits or wider (if wide tnodes are enabled),
7360          * so if the bitwidth of the
7361          * chunk range we're using is greater than 16 we need
7362          * to figure out chunk shift and chunkGroupSize
7363          */
7364
7365         if (bits <= dev->tnodeWidth)
7366                 dev->chunkGroupBits = 0;
7367         else
7368                 dev->chunkGroupBits = bits - dev->tnodeWidth;
7369
7370
7371         dev->chunkGroupSize = 1 << dev->chunkGroupBits;
7372
7373         if (dev->nChunksPerBlock < dev->chunkGroupSize) {
7374                 /* We have a problem because the soft delete won't work if
7375                  * the chunk group size > chunks per block.
7376                  * This can be remedied by using larger "virtual blocks".
7377                  */
7378                 T(YAFFS_TRACE_ALWAYS,
7379                   (TSTR("yaffs: chunk group too large\n" TENDSTR)));
7380
7381                 return YAFFS_FAIL;
7382         }
7383
7384         /* OK, we've finished verifying the device, lets continue with initialisation */
7385
7386         /* More device initialisation */
7387         dev->garbageCollections = 0;
7388         dev->passiveGarbageCollections = 0;
7389         dev->currentDirtyChecker = 0;
7390         dev->bufferedBlock = -1;
7391         dev->doingBufferedBlockRewrite = 0;
7392         dev->nDeletedFiles = 0;
7393         dev->nBackgroundDeletions = 0;
7394         dev->nUnlinkedFiles = 0;
7395         dev->eccFixed = 0;
7396         dev->eccUnfixed = 0;
7397         dev->tagsEccFixed = 0;
7398         dev->tagsEccUnfixed = 0;
7399         dev->nErasureFailures = 0;
7400         dev->nErasedBlocks = 0;
7401         dev->isDoingGC = 0;
7402         dev->hasPendingPrioritisedGCs = 1; /* Assume the worst for now, will get fixed on first GC */
7403
7404         /* Initialise temporary buffers and caches. */
7405         if(!yaffs_InitialiseTempBuffers(dev))
7406                 init_failed = 1;
7407
7408         dev->srCache = NULL;
7409         dev->gcCleanupList = NULL;
7410
7411
7412         if (!init_failed &&
7413             dev->nShortOpCaches > 0) {
7414                 int i;
7415                 void *buf;
7416                 int srCacheBytes = dev->nShortOpCaches * sizeof(yaffs_ChunkCache);
7417
7418                 if (dev->nShortOpCaches > YAFFS_MAX_SHORT_OP_CACHES) {
7419                         dev->nShortOpCaches = YAFFS_MAX_SHORT_OP_CACHES;
7420                 }
7421
7422                 dev->srCache =  YMALLOC(srCacheBytes);
7423
7424                 buf = (__u8 *) dev->srCache;
7425
7426                 if(dev->srCache)
7427                         memset(dev->srCache,0,srCacheBytes);
7428
7429                 for (i = 0; i < dev->nShortOpCaches && buf; i++) {
7430                         dev->srCache[i].object = NULL;
7431                         dev->srCache[i].lastUse = 0;
7432                         dev->srCache[i].dirty = 0;
7433                         dev->srCache[i].data = buf = YMALLOC_DMA(dev->totalBytesPerChunk);
7434                 }
7435                 if(!buf)
7436                         init_failed = 1;
7437
7438                 dev->srLastUse = 0;
7439         }
7440
7441         dev->cacheHits = 0;
7442
7443         if(!init_failed){
7444                 dev->gcCleanupList = YMALLOC(dev->nChunksPerBlock * sizeof(__u32));
7445                 if(!dev->gcCleanupList)
7446                         init_failed = 1;
7447         }
7448
7449         if (dev->isYaffs2) {
7450                 dev->useHeaderFileSize = 1;
7451         }
7452         if(!init_failed && !yaffs_InitialiseBlocks(dev))
7453                 init_failed = 1;
7454
7455         yaffs_InitialiseTnodes(dev);
7456         yaffs_InitialiseObjects(dev);
7457
7458         if(!init_failed && !yaffs_CreateInitialDirectories(dev))
7459                 init_failed = 1;
7460
7461
7462         if(!init_failed){
7463                 /* Now scan the flash. */
7464                 if (dev->isYaffs2) {
7465                         if(yaffs_CheckpointRestore(dev)) {
7466                                 yaffs_CheckObjectDetailsLoaded(dev->rootDir);
7467                                 T(YAFFS_TRACE_ALWAYS,
7468                                   (TSTR("yaffs: restored from checkpoint" TENDSTR)));
7469                         } else {
7470
7471                                 /* Clean up the mess caused by an aborted checkpoint load
7472                                  * and scan backwards.
7473                                  */
7474                                 yaffs_DeinitialiseBlocks(dev);
7475                                 yaffs_DeinitialiseTnodes(dev);
7476                                 yaffs_DeinitialiseObjects(dev);
7477
7478
7479                                 dev->nErasedBlocks = 0;
7480                                 dev->nFreeChunks = 0;
7481                                 dev->allocationBlock = -1;
7482                                 dev->allocationPage = -1;
7483                                 dev->nDeletedFiles = 0;
7484                                 dev->nUnlinkedFiles = 0;
7485                                 dev->nBackgroundDeletions = 0;
7486                                 dev->oldestDirtySequence = 0;
7487
7488                                 if(!init_failed && !yaffs_InitialiseBlocks(dev))
7489                                         init_failed = 1;
7490
7491                                 yaffs_InitialiseTnodes(dev);
7492                                 yaffs_InitialiseObjects(dev);
7493
7494                                 if(!init_failed && !yaffs_CreateInitialDirectories(dev))
7495                                         init_failed = 1;
7496
7497                                 if(!init_failed && !yaffs_ScanBackwards(dev))
7498                                         init_failed = 1;
7499                         }
7500                 }else
7501                         if(!yaffs_Scan(dev))
7502                                 init_failed = 1;
7503         }
7504
7505         if(init_failed){
7506                 /* Clean up the mess */
7507                 T(YAFFS_TRACE_TRACING,
7508                   (TSTR("yaffs: yaffs_GutsInitialise() aborted.\n" TENDSTR)));
7509
7510                 yaffs_Deinitialise(dev);
7511                 return YAFFS_FAIL;
7512         }
7513
7514         /* Zero out stats */
7515         dev->nPageReads = 0;
7516         dev->nPageWrites = 0;
7517         dev->nBlockErasures = 0;
7518         dev->nGCCopies = 0;
7519         dev->nRetriedWrites = 0;
7520
7521         dev->nRetiredBlocks = 0;
7522
7523         yaffs_VerifyFreeChunks(dev);
7524         yaffs_VerifyBlocks(dev);
7525
7526
7527         T(YAFFS_TRACE_TRACING,
7528           (TSTR("yaffs: yaffs_GutsInitialise() done.\n" TENDSTR)));
7529         return YAFFS_OK;
7530
7531 }
7532
7533 void yaffs_Deinitialise(yaffs_Device * dev)
7534 {
7535         if (dev->isMounted) {
7536                 int i;
7537
7538                 yaffs_DeinitialiseBlocks(dev);
7539                 yaffs_DeinitialiseTnodes(dev);
7540                 yaffs_DeinitialiseObjects(dev);
7541                 if (dev->nShortOpCaches > 0 &&
7542                     dev->srCache) {
7543
7544                         for (i = 0; i < dev->nShortOpCaches; i++) {
7545                                 if(dev->srCache[i].data)
7546                                         YFREE(dev->srCache[i].data);
7547                                 dev->srCache[i].data = NULL;
7548                         }
7549
7550                         YFREE(dev->srCache);
7551                         dev->srCache = NULL;
7552                 }
7553
7554                 YFREE(dev->gcCleanupList);
7555
7556                 for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
7557                         YFREE(dev->tempBuffer[i].buffer);
7558                 }
7559
7560
7561                 dev->isMounted = 0;
7562
7563                 if(dev->deinitialiseNAND)
7564                         dev->deinitialiseNAND(dev);
7565         }
7566
7567 }
7568
7569 static int yaffs_CountFreeChunks(yaffs_Device * dev)
7570 {
7571         int nFree;
7572         int b;
7573
7574         yaffs_BlockInfo *blk;
7575
7576         for (nFree = 0, b = dev->internalStartBlock; b <= dev->internalEndBlock;
7577              b++) {
7578                 blk = yaffs_GetBlockInfo(dev, b);
7579
7580                 switch (blk->blockState) {
7581                 case YAFFS_BLOCK_STATE_EMPTY:
7582                 case YAFFS_BLOCK_STATE_ALLOCATING:
7583                 case YAFFS_BLOCK_STATE_COLLECTING:
7584                 case YAFFS_BLOCK_STATE_FULL:
7585                         nFree +=
7586                             (dev->nChunksPerBlock - blk->pagesInUse +
7587                              blk->softDeletions);
7588                         break;
7589                 default:
7590                         break;
7591                 }
7592
7593         }
7594
7595         return nFree;
7596 }
7597
7598 int yaffs_GetNumberOfFreeChunks(yaffs_Device * dev)
7599 {
7600         /* This is what we report to the outside world */
7601
7602         int nFree;
7603         int nDirtyCacheChunks;
7604         int blocksForCheckpoint;
7605
7606 #if 1
7607         nFree = dev->nFreeChunks;
7608 #else
7609         nFree = yaffs_CountFreeChunks(dev);
7610 #endif
7611
7612         nFree += dev->nDeletedFiles;
7613
7614         /* Now count the number of dirty chunks in the cache and subtract those */
7615
7616         {
7617                 int i;
7618                 for (nDirtyCacheChunks = 0, i = 0; i < dev->nShortOpCaches; i++) {
7619                         if (dev->srCache[i].dirty)
7620                                 nDirtyCacheChunks++;
7621                 }
7622         }
7623
7624         nFree -= nDirtyCacheChunks;
7625
7626         nFree -= ((dev->nReservedBlocks + 1) * dev->nChunksPerBlock);
7627
7628         /* Now we figure out how much to reserve for the checkpoint and report that... */
7629         blocksForCheckpoint = yaffs_CalcCheckpointBlocksRequired(dev) - dev->blocksInCheckpoint;
7630         if(blocksForCheckpoint < 0)
7631                 blocksForCheckpoint = 0;
7632
7633         nFree -= (blocksForCheckpoint * dev->nChunksPerBlock);
7634
7635         if (nFree < 0)
7636                 nFree = 0;
7637
7638         return nFree;
7639
7640 }
7641
7642 static int yaffs_freeVerificationFailures;
7643
7644 static void yaffs_VerifyFreeChunks(yaffs_Device * dev)
7645 {
7646         int counted;
7647         int difference;
7648
7649         if(yaffs_SkipVerification(dev))
7650                 return;
7651
7652         counted = yaffs_CountFreeChunks(dev);
7653
7654         difference = dev->nFreeChunks - counted;
7655
7656         if (difference) {
7657                 T(YAFFS_TRACE_ALWAYS,
7658                   (TSTR("Freechunks verification failure %d %d %d" TENDSTR),
7659                    dev->nFreeChunks, counted, difference));
7660                 yaffs_freeVerificationFailures++;
7661         }
7662 }
7663
7664 /*---------------------------------------- YAFFS test code ----------------------*/
7665
7666 #define yaffs_CheckStruct(structure,syze, name) \
7667         do { \
7668            if(sizeof(structure) != syze) \
7669                { \
7670                  T(YAFFS_TRACE_ALWAYS,(TSTR("%s should be %d but is %d\n" TENDSTR),\
7671                  name,syze,sizeof(structure))); \
7672                  return YAFFS_FAIL; \
7673                 } \
7674         } while(0)
7675
7676 static int yaffs_CheckStructures(void)
7677 {
7678 /*      yaffs_CheckStruct(yaffs_Tags,8,"yaffs_Tags"); */
7679 /*      yaffs_CheckStruct(yaffs_TagsUnion,8,"yaffs_TagsUnion"); */
7680 /*      yaffs_CheckStruct(yaffs_Spare,16,"yaffs_Spare"); */
7681 #ifndef CONFIG_YAFFS_TNODE_LIST_DEBUG
7682         yaffs_CheckStruct(yaffs_Tnode, 2 * YAFFS_NTNODES_LEVEL0, "yaffs_Tnode");
7683 #endif
7684 #ifndef CONFIG_YAFFS_WINCE
7685                 yaffs_CheckStruct(yaffs_ObjectHeader, 512, "yaffs_ObjectHeader");
7686 #endif
7687             return YAFFS_OK;
7688 }