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.71 2009-01-12 00:53:47 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         __u32 nBytesRead;
4851         __u32 chunkStart;
4852
4853         yaffs_Device *dev;
4854
4855         dev = in->myDev;
4856
4857         while (n > 0 && chunkWritten >= 0) {
4858                 //chunk = offset / dev->nDataBytesPerChunk + 1;
4859                 //start = offset % dev->nDataBytesPerChunk;
4860                 yaffs_AddrToChunk(dev,offset,&chunk,&start);
4861
4862                 if(chunk * dev->nDataBytesPerChunk + start != offset ||
4863                    start >= dev->nDataBytesPerChunk){
4864                    T(YAFFS_TRACE_ERROR,(TSTR("AddrToChunk of offset %d gives chunk %d start %d"TENDSTR),
4865                                         (int)offset, chunk,start));
4866                 }
4867                 chunk++;
4868
4869                 /* OK now check for the curveball where the start and end are in
4870                  * the same chunk.
4871                  */
4872
4873                 if ((start + n) < dev->nDataBytesPerChunk) {
4874                         nToCopy = n;
4875
4876                         /* Now folks, to calculate how many bytes to write back....
4877                          * If we're overwriting and not writing to then end of file then
4878                          * we need to write back as much as was there before.
4879                          */
4880
4881                         chunkStart = ((chunk - 1) * dev->nDataBytesPerChunk);
4882
4883                         if(chunkStart > in->variant.fileVariant.fileSize)
4884                                 nBytesRead = 0; /* Past end of file */
4885                         else
4886                                 nBytesRead = in->variant.fileVariant.fileSize - chunkStart;
4887
4888                         if (nBytesRead > dev->nDataBytesPerChunk) {
4889                                 nBytesRead = dev->nDataBytesPerChunk;
4890                         }
4891
4892                         nToWriteBack =
4893                             (nBytesRead >
4894                              (start + n)) ? nBytesRead : (start + n);
4895
4896                         if(nToWriteBack < 0 || nToWriteBack > dev->nDataBytesPerChunk)
4897                                 YBUG();
4898
4899                 } else {
4900                         nToCopy = dev->nDataBytesPerChunk - start;
4901                         nToWriteBack = dev->nDataBytesPerChunk;
4902                 }
4903
4904                 if (nToCopy != dev->nDataBytesPerChunk || dev->inbandTags) {
4905                         /* An incomplete start or end chunk (or maybe both start and end chunk),
4906                          * or we're using inband tags, so we want to use the cache buffers.
4907                          */
4908                         if (dev->nShortOpCaches > 0) {
4909                                 yaffs_ChunkCache *cache;
4910                                 /* If we can't find the data in the cache, then load the cache */
4911                                 cache = yaffs_FindChunkCache(in, chunk);
4912
4913                                 if (!cache
4914                                     && yaffs_CheckSpaceForAllocation(in->
4915                                                                      myDev)) {
4916                                         cache = yaffs_GrabChunkCache(in->myDev);
4917                                         cache->object = in;
4918                                         cache->chunkId = chunk;
4919                                         cache->dirty = 0;
4920                                         cache->locked = 0;
4921                                         yaffs_ReadChunkDataFromObject(in, chunk,
4922                                                                       cache->
4923                                                                       data);
4924                                 }
4925                                 else if(cache &&
4926                                         !cache->dirty &&
4927                                         !yaffs_CheckSpaceForAllocation(in->myDev)){
4928                                         /* Drop the cache if it was a read cache item and
4929                                          * no space check has been made for it.
4930                                          */
4931                                          cache = NULL;
4932                                 }
4933
4934                                 if (cache) {
4935                                         yaffs_UseChunkCache(dev, cache, 1);
4936                                         cache->locked = 1;
4937 #ifdef CONFIG_YAFFS_WINCE
4938                                         yfsd_UnlockYAFFS(TRUE);
4939 #endif
4940
4941                                         memcpy(&cache->data[start], buffer,
4942                                                nToCopy);
4943
4944 #ifdef CONFIG_YAFFS_WINCE
4945                                         yfsd_LockYAFFS(TRUE);
4946 #endif
4947                                         cache->locked = 0;
4948                                         cache->nBytes = nToWriteBack;
4949
4950                                         if (writeThrough) {
4951                                                 chunkWritten =
4952                                                     yaffs_WriteChunkDataToObject
4953                                                     (cache->object,
4954                                                      cache->chunkId,
4955                                                      cache->data, cache->nBytes,
4956                                                      1);
4957                                                 cache->dirty = 0;
4958                                         }
4959
4960                                 } else {
4961                                         chunkWritten = -1;      /* fail the write */
4962                                 }
4963                         } else {
4964                                 /* An incomplete start or end chunk (or maybe both start and end chunk)
4965                                  * Read into the local buffer then copy, then copy over and write back.
4966                                  */
4967
4968                                 __u8 *localBuffer =
4969                                     yaffs_GetTempBuffer(dev, __LINE__);
4970
4971                                 yaffs_ReadChunkDataFromObject(in, chunk,
4972                                                               localBuffer);
4973
4974 #ifdef CONFIG_YAFFS_WINCE
4975                                 yfsd_UnlockYAFFS(TRUE);
4976 #endif
4977
4978                                 memcpy(&localBuffer[start], buffer, nToCopy);
4979
4980 #ifdef CONFIG_YAFFS_WINCE
4981                                 yfsd_LockYAFFS(TRUE);
4982 #endif
4983                                 chunkWritten =
4984                                     yaffs_WriteChunkDataToObject(in, chunk,
4985                                                                  localBuffer,
4986                                                                  nToWriteBack,
4987                                                                  0);
4988
4989                                 yaffs_ReleaseTempBuffer(dev, localBuffer,
4990                                                         __LINE__);
4991
4992                         }
4993
4994                 } else {
4995                         /* A full chunk. Write directly from the supplied buffer. */
4996
4997 #ifdef CONFIG_YAFFS_WINCE
4998                         /* Under WinCE can't do direct transfer. Need to use a local buffer.
4999                          * This is because we otherwise screw up WinCE's memory mapper
5000                          */
5001                         __u8 *localBuffer = yaffs_GetTempBuffer(dev, __LINE__);
5002 #ifdef CONFIG_YAFFS_WINCE
5003                         yfsd_UnlockYAFFS(TRUE);
5004 #endif
5005                         memcpy(localBuffer, buffer, dev->nDataBytesPerChunk);
5006 #ifdef CONFIG_YAFFS_WINCE
5007                         yfsd_LockYAFFS(TRUE);
5008 #endif
5009                         chunkWritten =
5010                             yaffs_WriteChunkDataToObject(in, chunk, localBuffer,
5011                                                          dev->nDataBytesPerChunk,
5012                                                          0);
5013                         yaffs_ReleaseTempBuffer(dev, localBuffer, __LINE__);
5014 #else
5015
5016                         chunkWritten =
5017                             yaffs_WriteChunkDataToObject(in, chunk, buffer,
5018                                                          dev->nDataBytesPerChunk,
5019                                                          0);
5020 #endif
5021                         /* Since we've overwritten the cached data, we better invalidate it. */
5022                         yaffs_InvalidateChunkCache(in, chunk);
5023                 }
5024
5025                 if (chunkWritten >= 0) {
5026                         n -= nToCopy;
5027                         offset += nToCopy;
5028                         buffer += nToCopy;
5029                         nDone += nToCopy;
5030                 }
5031
5032         }
5033
5034         /* Update file object */
5035
5036         if ((startOfWrite + nDone) > in->variant.fileVariant.fileSize) {
5037                 in->variant.fileVariant.fileSize = (startOfWrite + nDone);
5038         }
5039
5040         in->dirty = 1;
5041
5042         return nDone;
5043 }
5044
5045
5046 /* ---------------------- File resizing stuff ------------------ */
5047
5048 static void yaffs_PruneResizedChunks(yaffs_Object * in, int newSize)
5049 {
5050
5051         yaffs_Device *dev = in->myDev;
5052         int oldFileSize = in->variant.fileVariant.fileSize;
5053
5054         int lastDel = 1 + (oldFileSize - 1) / dev->nDataBytesPerChunk;
5055
5056         int startDel = 1 + (newSize + dev->nDataBytesPerChunk - 1) /
5057             dev->nDataBytesPerChunk;
5058         int i;
5059         int chunkId;
5060
5061         /* Delete backwards so that we don't end up with holes if
5062          * power is lost part-way through the operation.
5063          */
5064         for (i = lastDel; i >= startDel; i--) {
5065                 /* NB this could be optimised somewhat,
5066                  * eg. could retrieve the tags and write them without
5067                  * using yaffs_DeleteChunk
5068                  */
5069
5070                 chunkId = yaffs_FindAndDeleteChunkInFile(in, i, NULL);
5071                 if (chunkId > 0) {
5072                         if (chunkId <
5073                             (dev->internalStartBlock * dev->nChunksPerBlock)
5074                             || chunkId >=
5075                             ((dev->internalEndBlock +
5076                               1) * dev->nChunksPerBlock)) {
5077                                 T(YAFFS_TRACE_ALWAYS,
5078                                   (TSTR("Found daft chunkId %d for %d" TENDSTR),
5079                                    chunkId, i));
5080                         } else {
5081                                 in->nDataChunks--;
5082                                 yaffs_DeleteChunk(dev, chunkId, 1, __LINE__);
5083                         }
5084                 }
5085         }
5086
5087 }
5088
5089 int yaffs_ResizeFile(yaffs_Object * in, loff_t newSize)
5090 {
5091
5092         int oldFileSize = in->variant.fileVariant.fileSize;
5093         __u32 newSizeOfPartialChunk;
5094         int newFullChunks;
5095
5096         yaffs_Device *dev = in->myDev;
5097
5098         yaffs_AddrToChunk(dev, newSize, &newFullChunks, &newSizeOfPartialChunk);
5099
5100         yaffs_FlushFilesChunkCache(in);
5101         yaffs_InvalidateWholeChunkCache(in);
5102
5103         yaffs_CheckGarbageCollection(dev);
5104
5105         if (in->variantType != YAFFS_OBJECT_TYPE_FILE) {
5106                 return YAFFS_FAIL;
5107         }
5108
5109         if (newSize == oldFileSize) {
5110                 return YAFFS_OK;
5111         }
5112
5113         if (newSize < oldFileSize) {
5114
5115                 yaffs_PruneResizedChunks(in, newSize);
5116
5117                 if (newSizeOfPartialChunk != 0) {
5118                         int lastChunk = 1 + newFullChunks;
5119
5120                         __u8 *localBuffer = yaffs_GetTempBuffer(dev, __LINE__);
5121
5122                         /* Got to read and rewrite the last chunk with its new size and zero pad */
5123                         yaffs_ReadChunkDataFromObject(in, lastChunk,
5124                                                       localBuffer);
5125
5126                         memset(localBuffer + newSizeOfPartialChunk, 0,
5127                                dev->nDataBytesPerChunk - newSizeOfPartialChunk);
5128
5129                         yaffs_WriteChunkDataToObject(in, lastChunk, localBuffer,
5130                                                      newSizeOfPartialChunk, 1);
5131
5132                         yaffs_ReleaseTempBuffer(dev, localBuffer, __LINE__);
5133                 }
5134
5135                 in->variant.fileVariant.fileSize = newSize;
5136
5137                 yaffs_PruneFileStructure(dev, &in->variant.fileVariant);
5138         } else {
5139                 /* newsSize > oldFileSize */
5140                 in->variant.fileVariant.fileSize = newSize;
5141         }
5142
5143
5144
5145         /* Write a new object header.
5146          * show we've shrunk the file, if need be
5147          * Do this only if the file is not in the deleted directories.
5148          */
5149         if (in->parent &&
5150             in->parent->objectId != YAFFS_OBJECTID_UNLINKED &&
5151             in->parent->objectId != YAFFS_OBJECTID_DELETED) {
5152                 yaffs_UpdateObjectHeader(in, NULL, 0,
5153                                          (newSize < oldFileSize) ? 1 : 0, 0);
5154         }
5155
5156         return YAFFS_OK;
5157 }
5158
5159 loff_t yaffs_GetFileSize(yaffs_Object * obj)
5160 {
5161         obj = yaffs_GetEquivalentObject(obj);
5162
5163         switch (obj->variantType) {
5164         case YAFFS_OBJECT_TYPE_FILE:
5165                 return obj->variant.fileVariant.fileSize;
5166         case YAFFS_OBJECT_TYPE_SYMLINK:
5167                 return yaffs_strlen(obj->variant.symLinkVariant.alias);
5168         default:
5169                 return 0;
5170         }
5171 }
5172
5173
5174
5175 int yaffs_FlushFile(yaffs_Object * in, int updateTime)
5176 {
5177         int retVal;
5178         if (in->dirty) {
5179                 yaffs_FlushFilesChunkCache(in);
5180                 if (updateTime) {
5181 #ifdef CONFIG_YAFFS_WINCE
5182                         yfsd_WinFileTimeNow(in->win_mtime);
5183 #else
5184
5185                         in->yst_mtime = Y_CURRENT_TIME;
5186
5187 #endif
5188                 }
5189
5190                 retVal =
5191                     (yaffs_UpdateObjectHeader(in, NULL, 0, 0, 0) >=
5192                      0) ? YAFFS_OK : YAFFS_FAIL;
5193         } else {
5194                 retVal = YAFFS_OK;
5195         }
5196
5197         return retVal;
5198
5199 }
5200
5201 static int yaffs_DoGenericObjectDeletion(yaffs_Object * in)
5202 {
5203
5204         /* First off, invalidate the file's data in the cache, without flushing. */
5205         yaffs_InvalidateWholeChunkCache(in);
5206
5207         if (in->myDev->isYaffs2 && (in->parent != in->myDev->deletedDir)) {
5208                 /* Move to the unlinked directory so we have a record that it was deleted. */
5209                 yaffs_ChangeObjectName(in, in->myDev->deletedDir,_Y("deleted"), 0, 0);
5210
5211         }
5212
5213         yaffs_RemoveObjectFromDirectory(in);
5214         yaffs_DeleteChunk(in->myDev, in->hdrChunk, 1, __LINE__);
5215         in->hdrChunk = 0;
5216
5217         yaffs_FreeObject(in);
5218         return YAFFS_OK;
5219
5220 }
5221
5222 /* yaffs_DeleteFile deletes the whole file data
5223  * and the inode associated with the file.
5224  * It does not delete the links associated with the file.
5225  */
5226
5227 static int yaffs_UnlinkFile(yaffs_Object * in)
5228 {
5229
5230         int retVal;
5231         int immediateDeletion = 0;
5232
5233 #ifdef __KERNEL__
5234         if (!in->myInode) {
5235                 immediateDeletion = 1;
5236         }
5237 #else
5238         if (in->inUse <= 0) {
5239                 immediateDeletion = 1;
5240         }
5241 #endif
5242
5243         if (immediateDeletion) {
5244                 retVal =
5245                     yaffs_ChangeObjectName(in, in->myDev->deletedDir,
5246                                            _Y("deleted"), 0, 0);
5247                 T(YAFFS_TRACE_TRACING,
5248                   (TSTR("yaffs: immediate deletion of file %d" TENDSTR),
5249                    in->objectId));
5250                 in->deleted = 1;
5251                 in->myDev->nDeletedFiles++;
5252                 if (1 || in->myDev->isYaffs2) {
5253                         yaffs_ResizeFile(in, 0);
5254                 }
5255                 yaffs_SoftDeleteFile(in);
5256         } else {
5257                 retVal =
5258                     yaffs_ChangeObjectName(in, in->myDev->unlinkedDir,
5259                                            _Y("unlinked"), 0, 0);
5260         }
5261
5262
5263         return retVal;
5264 }
5265
5266 int yaffs_DeleteFile(yaffs_Object * in)
5267 {
5268         int retVal = YAFFS_OK;
5269         int deleted = in->deleted;
5270
5271         yaffs_ResizeFile(in,0);
5272
5273         if (in->nDataChunks > 0) {
5274                 /* Use soft deletion if there is data in the file.
5275                  * That won't be the case if it has been resized to zero.
5276                  */
5277                 if (!in->unlinked) {
5278                         retVal = yaffs_UnlinkFile(in);
5279                 }
5280                 if (retVal == YAFFS_OK && in->unlinked && !in->deleted) {
5281                         in->deleted = deleted = 1;
5282                         in->myDev->nDeletedFiles++;
5283                         yaffs_SoftDeleteFile(in);
5284                 }
5285                 return deleted ? YAFFS_OK : YAFFS_FAIL;
5286         } else {
5287                 /* The file has no data chunks so we toss it immediately */
5288                 yaffs_FreeTnode(in->myDev, in->variant.fileVariant.top);
5289                 in->variant.fileVariant.top = NULL;
5290                 yaffs_DoGenericObjectDeletion(in);
5291
5292                 return YAFFS_OK;
5293         }
5294 }
5295
5296 static int yaffs_DeleteDirectory(yaffs_Object * in)
5297 {
5298         /* First check that the directory is empty. */
5299         if (ylist_empty(&in->variant.directoryVariant.children)) {
5300                 return yaffs_DoGenericObjectDeletion(in);
5301         }
5302
5303         return YAFFS_FAIL;
5304
5305 }
5306
5307 static int yaffs_DeleteSymLink(yaffs_Object * in)
5308 {
5309         YFREE(in->variant.symLinkVariant.alias);
5310
5311         return yaffs_DoGenericObjectDeletion(in);
5312 }
5313
5314 static int yaffs_DeleteHardLink(yaffs_Object * in)
5315 {
5316         /* remove this hardlink from the list assocaited with the equivalent
5317          * object
5318          */
5319         ylist_del_init(&in->hardLinks);
5320         return yaffs_DoGenericObjectDeletion(in);
5321 }
5322
5323 static void yaffs_DestroyObject(yaffs_Object * obj)
5324 {
5325         switch (obj->variantType) {
5326         case YAFFS_OBJECT_TYPE_FILE:
5327                 yaffs_DeleteFile(obj);
5328                 break;
5329         case YAFFS_OBJECT_TYPE_DIRECTORY:
5330                 yaffs_DeleteDirectory(obj);
5331                 break;
5332         case YAFFS_OBJECT_TYPE_SYMLINK:
5333                 yaffs_DeleteSymLink(obj);
5334                 break;
5335         case YAFFS_OBJECT_TYPE_HARDLINK:
5336                 yaffs_DeleteHardLink(obj);
5337                 break;
5338         case YAFFS_OBJECT_TYPE_SPECIAL:
5339                 yaffs_DoGenericObjectDeletion(obj);
5340                 break;
5341         case YAFFS_OBJECT_TYPE_UNKNOWN:
5342                 break;          /* should not happen. */
5343         }
5344 }
5345
5346 static int yaffs_UnlinkWorker(yaffs_Object * obj)
5347 {
5348
5349         if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
5350                 return yaffs_DeleteHardLink(obj);
5351         } else if (!ylist_empty(&obj->hardLinks)) {
5352                 /* Curve ball: We're unlinking an object that has a hardlink.
5353                  *
5354                  * This problem arises because we are not strictly following
5355                  * The Linux link/inode model.
5356                  *
5357                  * We can't really delete the object.
5358                  * Instead, we do the following:
5359                  * - Select a hardlink.
5360                  * - Unhook it from the hard links
5361                  * - Unhook it from its parent directory (so that the rename can work)
5362                  * - Rename the object to the hardlink's name.
5363                  * - Delete the hardlink
5364                  */
5365
5366                 yaffs_Object *hl;
5367                 int retVal;
5368                 YCHAR name[YAFFS_MAX_NAME_LENGTH + 1];
5369
5370                 hl = ylist_entry(obj->hardLinks.next, yaffs_Object, hardLinks);
5371
5372                 ylist_del_init(&hl->hardLinks);
5373                 ylist_del_init(&hl->siblings);
5374
5375                 yaffs_GetObjectName(hl, name, YAFFS_MAX_NAME_LENGTH + 1);
5376
5377                 retVal = yaffs_ChangeObjectName(obj, hl->parent, name, 0, 0);
5378
5379                 if (retVal == YAFFS_OK) {
5380                         retVal = yaffs_DoGenericObjectDeletion(hl);
5381                 }
5382                 return retVal;
5383
5384         } else {
5385                 switch (obj->variantType) {
5386                 case YAFFS_OBJECT_TYPE_FILE:
5387                         return yaffs_UnlinkFile(obj);
5388                         break;
5389                 case YAFFS_OBJECT_TYPE_DIRECTORY:
5390                         return yaffs_DeleteDirectory(obj);
5391                         break;
5392                 case YAFFS_OBJECT_TYPE_SYMLINK:
5393                         return yaffs_DeleteSymLink(obj);
5394                         break;
5395                 case YAFFS_OBJECT_TYPE_SPECIAL:
5396                         return yaffs_DoGenericObjectDeletion(obj);
5397                         break;
5398                 case YAFFS_OBJECT_TYPE_HARDLINK:
5399                 case YAFFS_OBJECT_TYPE_UNKNOWN:
5400                 default:
5401                         return YAFFS_FAIL;
5402                 }
5403         }
5404 }
5405
5406
5407 static int yaffs_UnlinkObject( yaffs_Object *obj)
5408 {
5409
5410         if (obj && obj->unlinkAllowed) {
5411                 return yaffs_UnlinkWorker(obj);
5412         }
5413
5414         return YAFFS_FAIL;
5415
5416 }
5417 int yaffs_Unlink(yaffs_Object * dir, const YCHAR * name)
5418 {
5419         yaffs_Object *obj;
5420
5421         obj = yaffs_FindObjectByName(dir, name);
5422         return yaffs_UnlinkObject(obj);
5423 }
5424
5425 /*----------------------- Initialisation Scanning ---------------------- */
5426
5427 static void yaffs_HandleShadowedObject(yaffs_Device * dev, int objId,
5428                                        int backwardScanning)
5429 {
5430         yaffs_Object *obj;
5431
5432         if (!backwardScanning) {
5433                 /* Handle YAFFS1 forward scanning case
5434                  * For YAFFS1 we always do the deletion
5435                  */
5436
5437         } else {
5438                 /* Handle YAFFS2 case (backward scanning)
5439                  * If the shadowed object exists then ignore.
5440                  */
5441                 if (yaffs_FindObjectByNumber(dev, objId)) {
5442                         return;
5443                 }
5444         }
5445
5446         /* Let's create it (if it does not exist) assuming it is a file so that it can do shrinking etc.
5447          * We put it in unlinked dir to be cleaned up after the scanning
5448          */
5449         obj =
5450             yaffs_FindOrCreateObjectByNumber(dev, objId,
5451                                              YAFFS_OBJECT_TYPE_FILE);
5452         yaffs_AddObjectToDirectory(dev->unlinkedDir, obj);
5453         obj->variant.fileVariant.shrinkSize = 0;
5454         obj->valid = 1;         /* So that we don't read any other info for this file */
5455
5456 }
5457
5458 typedef struct {
5459         int seq;
5460         int block;
5461 } yaffs_BlockIndex;
5462
5463
5464 static void yaffs_HardlinkFixup(yaffs_Device *dev, yaffs_Object *hardList)
5465 {
5466         yaffs_Object *hl;
5467         yaffs_Object *in;
5468
5469         while (hardList) {
5470                 hl = hardList;
5471                 hardList = (yaffs_Object *) (hardList->hardLinks.next);
5472
5473                 in = yaffs_FindObjectByNumber(dev,
5474                                               hl->variant.hardLinkVariant.
5475                                               equivalentObjectId);
5476
5477                 if (in) {
5478                         /* Add the hardlink pointers */
5479                         hl->variant.hardLinkVariant.equivalentObject = in;
5480                         ylist_add(&hl->hardLinks, &in->hardLinks);
5481                 } else {
5482                         /* Todo Need to report/handle this better.
5483                          * Got a problem... hardlink to a non-existant object
5484                          */
5485                         hl->variant.hardLinkVariant.equivalentObject = NULL;
5486                         YINIT_LIST_HEAD(&hl->hardLinks);
5487
5488                 }
5489
5490         }
5491
5492 }
5493
5494
5495
5496
5497
5498 static int ybicmp(const void *a, const void *b){
5499     register int aseq = ((yaffs_BlockIndex *)a)->seq;
5500     register int bseq = ((yaffs_BlockIndex *)b)->seq;
5501     register int ablock = ((yaffs_BlockIndex *)a)->block;
5502     register int bblock = ((yaffs_BlockIndex *)b)->block;
5503     if( aseq == bseq )
5504         return ablock - bblock;
5505     else
5506         return aseq - bseq;
5507
5508 }
5509
5510
5511 struct yaffs_ShadowFixerStruct {
5512         int objectId;
5513         int shadowedId;
5514         struct yaffs_ShadowFixerStruct *next;
5515 };
5516
5517
5518 static void yaffs_StripDeletedObjects(yaffs_Device *dev)
5519 {
5520         /*
5521         *  Sort out state of unlinked and deleted objects after scanning.
5522         */
5523         struct ylist_head *i;
5524         struct ylist_head *n;
5525         yaffs_Object *l;
5526
5527         /* Soft delete all the unlinked files */
5528         ylist_for_each_safe(i, n,
5529                 &dev->unlinkedDir->variant.directoryVariant.children) {
5530                 if (i) {
5531                         l = ylist_entry(i, yaffs_Object, siblings);
5532                         yaffs_DestroyObject(l);
5533                 }
5534         }
5535
5536         ylist_for_each_safe(i, n,
5537                 &dev->deletedDir->variant.directoryVariant.children) {
5538                 if (i) {
5539                         l = ylist_entry(i, yaffs_Object, siblings);
5540                         yaffs_DestroyObject(l);
5541                 }
5542         }
5543
5544 }
5545
5546 static int yaffs_Scan(yaffs_Device * dev)
5547 {
5548         yaffs_ExtendedTags tags;
5549         int blk;
5550         int blockIterator;
5551         int startIterator;
5552         int endIterator;
5553         int result;
5554
5555         int chunk;
5556         int c;
5557         int deleted;
5558         yaffs_BlockState state;
5559         yaffs_Object *hardList = NULL;
5560         yaffs_BlockInfo *bi;
5561         __u32 sequenceNumber;
5562         yaffs_ObjectHeader *oh;
5563         yaffs_Object *in;
5564         yaffs_Object *parent;
5565
5566         int alloc_failed = 0;
5567
5568         struct yaffs_ShadowFixerStruct *shadowFixerList = NULL;
5569
5570
5571         __u8 *chunkData;
5572
5573
5574
5575         T(YAFFS_TRACE_SCAN,
5576           (TSTR("yaffs_Scan starts  intstartblk %d intendblk %d..." TENDSTR),
5577            dev->internalStartBlock, dev->internalEndBlock));
5578
5579         chunkData = yaffs_GetTempBuffer(dev, __LINE__);
5580
5581         dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
5582
5583         /* Scan all the blocks to determine their state */
5584         for (blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++) {
5585                 bi = yaffs_GetBlockInfo(dev, blk);
5586                 yaffs_ClearChunkBits(dev, blk);
5587                 bi->pagesInUse = 0;
5588                 bi->softDeletions = 0;
5589
5590                 yaffs_QueryInitialBlockState(dev, blk, &state, &sequenceNumber);
5591
5592                 bi->blockState = state;
5593                 bi->sequenceNumber = sequenceNumber;
5594
5595                 T(YAFFS_TRACE_SCAN_DEBUG,
5596                   (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
5597                    state, sequenceNumber));
5598
5599                 if (state == YAFFS_BLOCK_STATE_DEAD) {
5600                         T(YAFFS_TRACE_BAD_BLOCKS,
5601                           (TSTR("block %d is bad" TENDSTR), blk));
5602                 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
5603                         T(YAFFS_TRACE_SCAN_DEBUG,
5604                           (TSTR("Block empty " TENDSTR)));
5605                         dev->nErasedBlocks++;
5606                         dev->nFreeChunks += dev->nChunksPerBlock;
5607                 }
5608         }
5609
5610         startIterator = dev->internalStartBlock;
5611         endIterator = dev->internalEndBlock;
5612
5613         /* For each block.... */
5614         for (blockIterator = startIterator; !alloc_failed && blockIterator <= endIterator;
5615              blockIterator++) {
5616
5617                 YYIELD();
5618
5619                 YYIELD();
5620
5621                 blk = blockIterator;
5622
5623                 bi = yaffs_GetBlockInfo(dev, blk);
5624                 state = bi->blockState;
5625
5626                 deleted = 0;
5627
5628                 /* For each chunk in each block that needs scanning....*/
5629                 for (c = 0; !alloc_failed && c < dev->nChunksPerBlock &&
5630                      state == YAFFS_BLOCK_STATE_NEEDS_SCANNING; c++) {
5631                         /* Read the tags and decide what to do */
5632                         chunk = blk * dev->nChunksPerBlock + c;
5633
5634                         result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk, NULL,
5635                                                         &tags);
5636
5637                         /* Let's have a good look at this chunk... */
5638
5639                         if (tags.eccResult == YAFFS_ECC_RESULT_UNFIXED || tags.chunkDeleted) {
5640                                 /* YAFFS1 only...
5641                                  * A deleted chunk
5642                                  */
5643                                 deleted++;
5644                                 dev->nFreeChunks++;
5645                                 /*T((" %d %d deleted\n",blk,c)); */
5646                         } else if (!tags.chunkUsed) {
5647                                 /* An unassigned chunk in the block
5648                                  * This means that either the block is empty or
5649                                  * this is the one being allocated from
5650                                  */
5651
5652                                 if (c == 0) {
5653                                         /* We're looking at the first chunk in the block so the block is unused */
5654                                         state = YAFFS_BLOCK_STATE_EMPTY;
5655                                         dev->nErasedBlocks++;
5656                                 } else {
5657                                         /* this is the block being allocated from */
5658                                         T(YAFFS_TRACE_SCAN,
5659                                           (TSTR
5660                                            (" Allocating from %d %d" TENDSTR),
5661                                            blk, c));
5662                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
5663                                         dev->allocationBlock = blk;
5664                                         dev->allocationPage = c;
5665                                         dev->allocationBlockFinder = blk;
5666                                         /* Set it to here to encourage the allocator to go forth from here. */
5667
5668                                 }
5669
5670                                 dev->nFreeChunks += (dev->nChunksPerBlock - c);
5671                         } else if (tags.chunkId > 0) {
5672                                 /* chunkId > 0 so it is a data chunk... */
5673                                 unsigned int endpos;
5674
5675                                 yaffs_SetChunkBit(dev, blk, c);
5676                                 bi->pagesInUse++;
5677
5678                                 in = yaffs_FindOrCreateObjectByNumber(dev,
5679                                                                       tags.
5680                                                                       objectId,
5681                                                                       YAFFS_OBJECT_TYPE_FILE);
5682                                 /* PutChunkIntoFile checks for a clash (two data chunks with
5683                                  * the same chunkId).
5684                                  */
5685
5686                                 if(!in)
5687                                         alloc_failed = 1;
5688
5689                                 if(in){
5690                                         if(!yaffs_PutChunkIntoFile(in, tags.chunkId, chunk,1))
5691                                                 alloc_failed = 1;
5692                                 }
5693
5694                                 endpos =
5695                                     (tags.chunkId - 1) * dev->nDataBytesPerChunk +
5696                                     tags.byteCount;
5697                                 if (in &&
5698                                     in->variantType == YAFFS_OBJECT_TYPE_FILE
5699                                     && in->variant.fileVariant.scannedFileSize <
5700                                     endpos) {
5701                                         in->variant.fileVariant.
5702                                             scannedFileSize = endpos;
5703                                         if (!dev->useHeaderFileSize) {
5704                                                 in->variant.fileVariant.
5705                                                     fileSize =
5706                                                     in->variant.fileVariant.
5707                                                     scannedFileSize;
5708                                         }
5709
5710                                 }
5711                                 /* T((" %d %d data %d %d\n",blk,c,tags.objectId,tags.chunkId));   */
5712                         } else {
5713                                 /* chunkId == 0, so it is an ObjectHeader.
5714                                  * Thus, we read in the object header and make the object
5715                                  */
5716                                 yaffs_SetChunkBit(dev, blk, c);
5717                                 bi->pagesInUse++;
5718
5719                                 result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk,
5720                                                                 chunkData,
5721                                                                 NULL);
5722
5723                                 oh = (yaffs_ObjectHeader *) chunkData;
5724
5725                                 in = yaffs_FindObjectByNumber(dev,
5726                                                               tags.objectId);
5727                                 if (in && in->variantType != oh->type) {
5728                                         /* This should not happen, but somehow
5729                                          * Wev'e ended up with an objectId that has been reused but not yet
5730                                          * deleted, and worse still it has changed type. Delete the old object.
5731                                          */
5732
5733                                         yaffs_DestroyObject(in);
5734
5735                                         in = 0;
5736                                 }
5737
5738                                 in = yaffs_FindOrCreateObjectByNumber(dev,
5739                                                                       tags.
5740                                                                       objectId,
5741                                                                       oh->type);
5742
5743                                 if(!in)
5744                                         alloc_failed = 1;
5745
5746                                 if (in && oh->shadowsObject > 0) {
5747
5748                                         struct yaffs_ShadowFixerStruct *fixer;
5749                                         fixer = YMALLOC(sizeof(struct yaffs_ShadowFixerStruct));
5750                                         if(fixer){
5751                                                 fixer-> next = shadowFixerList;
5752                                                 shadowFixerList = fixer;
5753                                                 fixer->objectId = tags.objectId;
5754                                                 fixer->shadowedId = oh->shadowsObject;
5755                                         }
5756
5757                                 }
5758
5759                                 if (in && in->valid) {
5760                                         /* We have already filled this one. We have a duplicate and need to resolve it. */
5761
5762                                         unsigned existingSerial = in->serial;
5763                                         unsigned newSerial = tags.serialNumber;
5764
5765                                         if (((existingSerial + 1) & 3) == newSerial) {
5766                                                 /* Use new one - destroy the exisiting one */
5767                                                 yaffs_DeleteChunk(dev,
5768                                                                   in->hdrChunk,
5769                                                                   1, __LINE__);
5770                                                 in->valid = 0;
5771                                         } else {
5772                                                 /* Use existing - destroy this one. */
5773                                                 yaffs_DeleteChunk(dev, chunk, 1,
5774                                                                   __LINE__);
5775                                         }
5776                                 }
5777
5778                                 if (in && !in->valid &&
5779                                     (tags.objectId == YAFFS_OBJECTID_ROOT ||
5780                                      tags.objectId == YAFFS_OBJECTID_LOSTNFOUND)) {
5781                                         /* We only load some info, don't fiddle with directory structure */
5782                                         in->valid = 1;
5783                                         in->variantType = oh->type;
5784
5785                                         in->yst_mode = oh->yst_mode;
5786 #ifdef CONFIG_YAFFS_WINCE
5787                                         in->win_atime[0] = oh->win_atime[0];
5788                                         in->win_ctime[0] = oh->win_ctime[0];
5789                                         in->win_mtime[0] = oh->win_mtime[0];
5790                                         in->win_atime[1] = oh->win_atime[1];
5791                                         in->win_ctime[1] = oh->win_ctime[1];
5792                                         in->win_mtime[1] = oh->win_mtime[1];
5793 #else
5794                                         in->yst_uid = oh->yst_uid;
5795                                         in->yst_gid = oh->yst_gid;
5796                                         in->yst_atime = oh->yst_atime;
5797                                         in->yst_mtime = oh->yst_mtime;
5798                                         in->yst_ctime = oh->yst_ctime;
5799                                         in->yst_rdev = oh->yst_rdev;
5800 #endif
5801                                         in->hdrChunk = chunk;
5802                                         in->serial = tags.serialNumber;
5803
5804                                 } else if (in && !in->valid) {
5805                                         /* we need to load this info */
5806
5807                                         in->valid = 1;
5808                                         in->variantType = oh->type;
5809
5810                                         in->yst_mode = oh->yst_mode;
5811 #ifdef CONFIG_YAFFS_WINCE
5812                                         in->win_atime[0] = oh->win_atime[0];
5813                                         in->win_ctime[0] = oh->win_ctime[0];
5814                                         in->win_mtime[0] = oh->win_mtime[0];
5815                                         in->win_atime[1] = oh->win_atime[1];
5816                                         in->win_ctime[1] = oh->win_ctime[1];
5817                                         in->win_mtime[1] = oh->win_mtime[1];
5818 #else
5819                                         in->yst_uid = oh->yst_uid;
5820                                         in->yst_gid = oh->yst_gid;
5821                                         in->yst_atime = oh->yst_atime;
5822                                         in->yst_mtime = oh->yst_mtime;
5823                                         in->yst_ctime = oh->yst_ctime;
5824                                         in->yst_rdev = oh->yst_rdev;
5825 #endif
5826                                         in->hdrChunk = chunk;
5827                                         in->serial = tags.serialNumber;
5828
5829                                         yaffs_SetObjectName(in, oh->name);
5830                                         in->dirty = 0;
5831
5832                                         /* directory stuff...
5833                                          * hook up to parent
5834                                          */
5835
5836                                         parent =
5837                                             yaffs_FindOrCreateObjectByNumber
5838                                             (dev, oh->parentObjectId,
5839                                              YAFFS_OBJECT_TYPE_DIRECTORY);
5840                                         if (parent->variantType ==
5841                                             YAFFS_OBJECT_TYPE_UNKNOWN) {
5842                                                 /* Set up as a directory */
5843                                                 parent->variantType =
5844                                                     YAFFS_OBJECT_TYPE_DIRECTORY;
5845                                                 YINIT_LIST_HEAD(&parent->variant.
5846                                                                directoryVariant.
5847                                                                children);
5848                                         } else if (parent->variantType !=
5849                                                    YAFFS_OBJECT_TYPE_DIRECTORY)
5850                                         {
5851                                                 /* Hoosterman, another problem....
5852                                                  * We're trying to use a non-directory as a directory
5853                                                  */
5854
5855                                                 T(YAFFS_TRACE_ERROR,
5856                                                   (TSTR
5857                                                    ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
5858                                                     TENDSTR)));
5859                                                 parent = dev->lostNFoundDir;
5860                                         }
5861
5862                                         yaffs_AddObjectToDirectory(parent, in);
5863
5864                                         if (0 && (parent == dev->deletedDir ||
5865                                                   parent == dev->unlinkedDir)) {
5866                                                 in->deleted = 1;        /* If it is unlinked at start up then it wants deleting */
5867                                                 dev->nDeletedFiles++;
5868                                         }
5869                                         /* Note re hardlinks.
5870                                          * Since we might scan a hardlink before its equivalent object is scanned
5871                                          * we put them all in a list.
5872                                          * After scanning is complete, we should have all the objects, so we run through this
5873                                          * list and fix up all the chains.
5874                                          */
5875
5876                                         switch (in->variantType) {
5877                                         case YAFFS_OBJECT_TYPE_UNKNOWN:
5878                                                 /* Todo got a problem */
5879                                                 break;
5880                                         case YAFFS_OBJECT_TYPE_FILE:
5881                                                 if (dev->useHeaderFileSize)
5882
5883                                                         in->variant.fileVariant.
5884                                                             fileSize =
5885                                                             oh->fileSize;
5886
5887                                                 break;
5888                                         case YAFFS_OBJECT_TYPE_HARDLINK:
5889                                                 in->variant.hardLinkVariant.
5890                                                     equivalentObjectId =
5891                                                     oh->equivalentObjectId;
5892                                                 in->hardLinks.next =
5893                                                     (struct ylist_head *)
5894                                                     hardList;
5895                                                 hardList = in;
5896                                                 break;
5897                                         case YAFFS_OBJECT_TYPE_DIRECTORY:
5898                                                 /* Do nothing */
5899                                                 break;
5900                                         case YAFFS_OBJECT_TYPE_SPECIAL:
5901                                                 /* Do nothing */
5902                                                 break;
5903                                         case YAFFS_OBJECT_TYPE_SYMLINK:
5904                                                 in->variant.symLinkVariant.alias =
5905                                                     yaffs_CloneString(oh->alias);
5906                                                 if(!in->variant.symLinkVariant.alias)
5907                                                         alloc_failed = 1;
5908                                                 break;
5909                                         }
5910
5911 /*
5912                                         if (parent == dev->deletedDir) {
5913                                                 yaffs_DestroyObject(in);
5914                                                 bi->hasShrinkHeader = 1;
5915                                         }
5916 */
5917                                 }
5918                         }
5919                 }
5920
5921                 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
5922                         /* If we got this far while scanning, then the block is fully allocated.*/
5923                         state = YAFFS_BLOCK_STATE_FULL;
5924                 }
5925
5926                 bi->blockState = state;
5927
5928                 /* Now let's see if it was dirty */
5929                 if (bi->pagesInUse == 0 &&
5930                     !bi->hasShrinkHeader &&
5931                     bi->blockState == YAFFS_BLOCK_STATE_FULL) {
5932                         yaffs_BlockBecameDirty(dev, blk);
5933                 }
5934
5935         }
5936
5937
5938         /* Ok, we've done all the scanning.
5939          * Fix up the hard link chains.
5940          * We should now have scanned all the objects, now it's time to add these
5941          * hardlinks.
5942          */
5943
5944         yaffs_HardlinkFixup(dev,hardList);
5945
5946         /* Fix up any shadowed objects */
5947         {
5948                 struct yaffs_ShadowFixerStruct *fixer;
5949                 yaffs_Object *obj;
5950
5951                 while(shadowFixerList){
5952                         fixer = shadowFixerList;
5953                         shadowFixerList = fixer->next;
5954                         /* Complete the rename transaction by deleting the shadowed object
5955                          * then setting the object header to unshadowed.
5956                          */
5957                         obj = yaffs_FindObjectByNumber(dev,fixer->shadowedId);
5958                         if(obj)
5959                                 yaffs_DestroyObject(obj);
5960
5961                         obj = yaffs_FindObjectByNumber(dev,fixer->objectId);
5962                         if(obj){
5963                                 yaffs_UpdateObjectHeader(obj,NULL,1,0,0);
5964                         }
5965
5966                         YFREE(fixer);
5967                 }
5968         }
5969
5970         yaffs_ReleaseTempBuffer(dev, chunkData, __LINE__);
5971
5972         if(alloc_failed){
5973                 return YAFFS_FAIL;
5974         }
5975
5976         T(YAFFS_TRACE_SCAN, (TSTR("yaffs_Scan ends" TENDSTR)));
5977
5978
5979         return YAFFS_OK;
5980 }
5981
5982 static void yaffs_CheckObjectDetailsLoaded(yaffs_Object *in)
5983 {
5984         __u8 *chunkData;
5985         yaffs_ObjectHeader *oh;
5986         yaffs_Device *dev;
5987         yaffs_ExtendedTags tags;
5988         int result;
5989         int alloc_failed = 0;
5990
5991         if(!in)
5992                 return;
5993
5994         dev = in->myDev;
5995
5996 #if 0
5997         T(YAFFS_TRACE_SCAN,(TSTR("details for object %d %s loaded" TENDSTR),
5998                 in->objectId,
5999                 in->lazyLoaded ? "not yet" : "already"));
6000 #endif
6001
6002         if(in->lazyLoaded && in->hdrChunk > 0){
6003                 in->lazyLoaded = 0;
6004                 chunkData = yaffs_GetTempBuffer(dev, __LINE__);
6005
6006                 result = yaffs_ReadChunkWithTagsFromNAND(dev,in->hdrChunk,chunkData,&tags);
6007                 oh = (yaffs_ObjectHeader *) chunkData;
6008
6009                 in->yst_mode = oh->yst_mode;
6010 #ifdef CONFIG_YAFFS_WINCE
6011                 in->win_atime[0] = oh->win_atime[0];
6012                 in->win_ctime[0] = oh->win_ctime[0];
6013                 in->win_mtime[0] = oh->win_mtime[0];
6014                 in->win_atime[1] = oh->win_atime[1];
6015                 in->win_ctime[1] = oh->win_ctime[1];
6016                 in->win_mtime[1] = oh->win_mtime[1];
6017 #else
6018                 in->yst_uid = oh->yst_uid;
6019                 in->yst_gid = oh->yst_gid;
6020                 in->yst_atime = oh->yst_atime;
6021                 in->yst_mtime = oh->yst_mtime;
6022                 in->yst_ctime = oh->yst_ctime;
6023                 in->yst_rdev = oh->yst_rdev;
6024
6025 #endif
6026                 yaffs_SetObjectName(in, oh->name);
6027
6028                 if(in->variantType == YAFFS_OBJECT_TYPE_SYMLINK){
6029                          in->variant.symLinkVariant.alias =
6030                                                     yaffs_CloneString(oh->alias);
6031                         if(!in->variant.symLinkVariant.alias)
6032                                 alloc_failed = 1; /* Not returned to caller */
6033                 }
6034
6035                 yaffs_ReleaseTempBuffer(dev,chunkData, __LINE__);
6036         }
6037 }
6038
6039 static int yaffs_ScanBackwards(yaffs_Device * dev)
6040 {
6041         yaffs_ExtendedTags tags;
6042         int blk;
6043         int blockIterator;
6044         int startIterator;
6045         int endIterator;
6046         int nBlocksToScan = 0;
6047
6048         int chunk;
6049         int result;
6050         int c;
6051         int deleted;
6052         yaffs_BlockState state;
6053         yaffs_Object *hardList = NULL;
6054         yaffs_BlockInfo *bi;
6055         __u32 sequenceNumber;
6056         yaffs_ObjectHeader *oh;
6057         yaffs_Object *in;
6058         yaffs_Object *parent;
6059         int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
6060         int itsUnlinked;
6061         __u8 *chunkData;
6062
6063         int fileSize;
6064         int isShrink;
6065         int foundChunksInBlock;
6066         int equivalentObjectId;
6067         int alloc_failed = 0;
6068
6069
6070         yaffs_BlockIndex *blockIndex = NULL;
6071         int altBlockIndex = 0;
6072
6073         if (!dev->isYaffs2) {
6074                 T(YAFFS_TRACE_SCAN,
6075                   (TSTR("yaffs_ScanBackwards is only for YAFFS2!" TENDSTR)));
6076                 return YAFFS_FAIL;
6077         }
6078
6079         T(YAFFS_TRACE_SCAN,
6080           (TSTR
6081            ("yaffs_ScanBackwards starts  intstartblk %d intendblk %d..."
6082             TENDSTR), dev->internalStartBlock, dev->internalEndBlock));
6083
6084
6085         dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
6086
6087         blockIndex = YMALLOC(nBlocks * sizeof(yaffs_BlockIndex));
6088
6089         if(!blockIndex) {
6090                 blockIndex = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockIndex));
6091                 altBlockIndex = 1;
6092         }
6093
6094         if(!blockIndex) {
6095                 T(YAFFS_TRACE_SCAN,
6096                   (TSTR("yaffs_Scan() could not allocate block index!" TENDSTR)));
6097                 return YAFFS_FAIL;
6098         }
6099
6100         dev->blocksInCheckpoint = 0;
6101
6102         chunkData = yaffs_GetTempBuffer(dev, __LINE__);
6103
6104         /* Scan all the blocks to determine their state */
6105         for (blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++) {
6106                 bi = yaffs_GetBlockInfo(dev, blk);
6107                 yaffs_ClearChunkBits(dev, blk);
6108                 bi->pagesInUse = 0;
6109                 bi->softDeletions = 0;
6110
6111                 yaffs_QueryInitialBlockState(dev, blk, &state, &sequenceNumber);
6112
6113                 bi->blockState = state;
6114                 bi->sequenceNumber = sequenceNumber;
6115
6116                 if(bi->sequenceNumber == YAFFS_SEQUENCE_CHECKPOINT_DATA)
6117                         bi->blockState = state = YAFFS_BLOCK_STATE_CHECKPOINT;
6118
6119                 T(YAFFS_TRACE_SCAN_DEBUG,
6120                   (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
6121                    state, sequenceNumber));
6122
6123
6124                 if(state == YAFFS_BLOCK_STATE_CHECKPOINT){
6125                         dev->blocksInCheckpoint++;
6126
6127                 } else if (state == YAFFS_BLOCK_STATE_DEAD) {
6128                         T(YAFFS_TRACE_BAD_BLOCKS,
6129                           (TSTR("block %d is bad" TENDSTR), blk));
6130                 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
6131                         T(YAFFS_TRACE_SCAN_DEBUG,
6132                           (TSTR("Block empty " TENDSTR)));
6133                         dev->nErasedBlocks++;
6134                         dev->nFreeChunks += dev->nChunksPerBlock;
6135                 } else if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
6136
6137                         /* Determine the highest sequence number */
6138                         if (sequenceNumber >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
6139                             sequenceNumber < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
6140
6141                                 blockIndex[nBlocksToScan].seq = sequenceNumber;
6142                                 blockIndex[nBlocksToScan].block = blk;
6143
6144                                 nBlocksToScan++;
6145
6146                                 if (sequenceNumber >= dev->sequenceNumber) {
6147                                         dev->sequenceNumber = sequenceNumber;
6148                                 }
6149                         } else {
6150                                 /* TODO: Nasty sequence number! */
6151                                 T(YAFFS_TRACE_SCAN,
6152                                   (TSTR
6153                                    ("Block scanning block %d has bad sequence number %d"
6154                                     TENDSTR), blk, sequenceNumber));
6155
6156                         }
6157                 }
6158         }
6159
6160         T(YAFFS_TRACE_SCAN,
6161         (TSTR("%d blocks to be sorted..." TENDSTR), nBlocksToScan));
6162
6163
6164
6165         YYIELD();
6166
6167         /* Sort the blocks */
6168 #ifndef CONFIG_YAFFS_USE_OWN_SORT
6169         {
6170                 /* Use qsort now. */
6171                 yaffs_qsort(blockIndex, nBlocksToScan, sizeof(yaffs_BlockIndex), ybicmp);
6172         }
6173 #else
6174         {
6175                 /* Dungy old bubble sort... */
6176
6177                 yaffs_BlockIndex temp;
6178                 int i;
6179                 int j;
6180
6181                 for (i = 0; i < nBlocksToScan; i++)
6182                         for (j = i + 1; j < nBlocksToScan; j++)
6183                                 if (blockIndex[i].seq > blockIndex[j].seq) {
6184                                         temp = blockIndex[j];
6185                                         blockIndex[j] = blockIndex[i];
6186                                         blockIndex[i] = temp;
6187                                 }
6188         }
6189 #endif
6190
6191         YYIELD();
6192
6193         T(YAFFS_TRACE_SCAN, (TSTR("...done" TENDSTR)));
6194
6195         /* Now scan the blocks looking at the data. */
6196         startIterator = 0;
6197         endIterator = nBlocksToScan - 1;
6198         T(YAFFS_TRACE_SCAN_DEBUG,
6199           (TSTR("%d blocks to be scanned" TENDSTR), nBlocksToScan));
6200
6201         /* For each block.... backwards */
6202         for (blockIterator = endIterator; !alloc_failed && blockIterator >= startIterator;
6203              blockIterator--) {
6204                 /* Cooperative multitasking! This loop can run for so
6205                    long that watchdog timers expire. */
6206                 YYIELD();
6207
6208                 /* get the block to scan in the correct order */
6209                 blk = blockIndex[blockIterator].block;
6210
6211                 bi = yaffs_GetBlockInfo(dev, blk);
6212
6213
6214                 state = bi->blockState;
6215
6216                 deleted = 0;
6217
6218                 /* For each chunk in each block that needs scanning.... */
6219                 foundChunksInBlock = 0;
6220                 for (c = dev->nChunksPerBlock - 1;
6221                      !alloc_failed && c >= 0 &&
6222                      (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
6223                       state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
6224                         /* Scan backwards...
6225                          * Read the tags and decide what to do
6226                          */
6227
6228                         chunk = blk * dev->nChunksPerBlock + c;
6229
6230                         result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk, NULL,
6231                                                         &tags);
6232
6233                         /* Let's have a good look at this chunk... */
6234
6235                         if (!tags.chunkUsed) {
6236                                 /* An unassigned chunk in the block.
6237                                  * If there are used chunks after this one, then
6238                                  * it is a chunk that was skipped due to failing the erased
6239                                  * check. Just skip it so that it can be deleted.
6240                                  * But, more typically, We get here when this is an unallocated
6241                                  * chunk and his means that either the block is empty or
6242                                  * this is the one being allocated from
6243                                  */
6244
6245                                 if(foundChunksInBlock)
6246                                 {
6247                                         /* This is a chunk that was skipped due to failing the erased check */
6248
6249                                 } else if (c == 0) {
6250                                         /* We're looking at the first chunk in the block so the block is unused */
6251                                         state = YAFFS_BLOCK_STATE_EMPTY;
6252                                         dev->nErasedBlocks++;
6253                                 } else {
6254                                         if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
6255                                             state == YAFFS_BLOCK_STATE_ALLOCATING) {
6256                                                 if(dev->sequenceNumber == bi->sequenceNumber) {
6257                                                         /* this is the block being allocated from */
6258
6259                                                         T(YAFFS_TRACE_SCAN,
6260                                                           (TSTR
6261                                                            (" Allocating from %d %d"
6262                                                             TENDSTR), blk, c));
6263
6264                                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
6265                                                         dev->allocationBlock = blk;
6266                                                         dev->allocationPage = c;
6267                                                         dev->allocationBlockFinder = blk;
6268                                                 }
6269                                                 else {
6270                                                         /* This is a partially written block that is not
6271                                                          * the current allocation block. This block must have
6272                                                          * had a write failure, so set up for retirement.
6273                                                          */
6274
6275                                                          /* bi->needsRetiring = 1; ??? TODO */
6276                                                          bi->gcPrioritise = 1;
6277
6278                                                          T(YAFFS_TRACE_ALWAYS,
6279                                                          (TSTR("Partially written block %d detected" TENDSTR),
6280                                                          blk));
6281                                                 }
6282
6283                                         }
6284
6285                                 }
6286
6287                                 dev->nFreeChunks++;
6288
6289                         } else if (tags.chunkId > 0) {
6290                                 /* chunkId > 0 so it is a data chunk... */
6291                                 unsigned int endpos;
6292                                 __u32 chunkBase =
6293                                     (tags.chunkId - 1) * dev->nDataBytesPerChunk;
6294
6295                                 foundChunksInBlock = 1;
6296
6297
6298                                 yaffs_SetChunkBit(dev, blk, c);
6299                                 bi->pagesInUse++;
6300
6301                                 in = yaffs_FindOrCreateObjectByNumber(dev,
6302                                                                       tags.
6303                                                                       objectId,
6304                                                                       YAFFS_OBJECT_TYPE_FILE);
6305                                 if(!in){
6306                                         /* Out of memory */
6307                                         alloc_failed = 1;
6308                                 }
6309
6310                                 if (in &&
6311                                     in->variantType == YAFFS_OBJECT_TYPE_FILE
6312                                     && chunkBase <
6313                                     in->variant.fileVariant.shrinkSize) {
6314                                         /* This has not been invalidated by a resize */
6315                                         if(!yaffs_PutChunkIntoFile(in, tags.chunkId,
6316                                                                chunk, -1)){
6317                                                 alloc_failed = 1;
6318                                         }
6319
6320                                         /* File size is calculated by looking at the data chunks if we have not
6321                                          * seen an object header yet. Stop this practice once we find an object header.
6322                                          */
6323                                         endpos =
6324                                             (tags.chunkId -
6325                                              1) * dev->nDataBytesPerChunk +
6326                                             tags.byteCount;
6327
6328                                         if (!in->valid &&       /* have not got an object header yet */
6329                                             in->variant.fileVariant.
6330                                             scannedFileSize < endpos) {
6331                                                 in->variant.fileVariant.
6332                                                     scannedFileSize = endpos;
6333                                                 in->variant.fileVariant.
6334                                                     fileSize =
6335                                                     in->variant.fileVariant.
6336                                                     scannedFileSize;
6337                                         }
6338
6339                                 } else if(in) {
6340                                         /* This chunk has been invalidated by a resize, so delete */
6341                                         yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
6342
6343                                 }
6344                         } else {
6345                                 /* chunkId == 0, so it is an ObjectHeader.
6346                                  * Thus, we read in the object header and make the object
6347                                  */
6348                                 foundChunksInBlock = 1;
6349
6350                                 yaffs_SetChunkBit(dev, blk, c);
6351                                 bi->pagesInUse++;
6352
6353                                 oh = NULL;
6354                                 in = NULL;
6355
6356                                 if (tags.extraHeaderInfoAvailable) {
6357                                         in = yaffs_FindOrCreateObjectByNumber
6358                                             (dev, tags.objectId,
6359                                              tags.extraObjectType);
6360                                 }
6361
6362                                 if (!in ||
6363 #ifdef CONFIG_YAFFS_DISABLE_LAZY_LOAD
6364                                     !in->valid ||
6365 #endif
6366                                     tags.extraShadows ||
6367                                     (!in->valid &&
6368                                     (tags.objectId == YAFFS_OBJECTID_ROOT ||
6369                                      tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))
6370                                     ) {
6371
6372                                         /* If we don't have  valid info then we need to read the chunk
6373                                          * TODO In future we can probably defer reading the chunk and
6374                                          * living with invalid data until needed.
6375                                          */
6376
6377                                         result = yaffs_ReadChunkWithTagsFromNAND(dev,
6378                                                                         chunk,
6379                                                                         chunkData,
6380                                                                         NULL);
6381
6382                                         oh = (yaffs_ObjectHeader *) chunkData;
6383
6384                                         if(dev->inbandTags){
6385                                                 /* Fix up the header if they got corrupted by inband tags */
6386                                                 oh->shadowsObject = oh->inbandShadowsObject;
6387                                                 oh->isShrink = oh->inbandIsShrink;
6388                                         }
6389
6390                                         if (!in)
6391                                                 in = yaffs_FindOrCreateObjectByNumber(dev, tags.objectId, oh->type);
6392
6393                                 }
6394
6395                                 if (!in) {
6396                                         /* TODO Hoosterman we have a problem! */
6397                                         T(YAFFS_TRACE_ERROR,
6398                                           (TSTR
6399                                            ("yaffs tragedy: Could not make object for object  %d at chunk %d during scan"
6400                                             TENDSTR), tags.objectId, chunk));
6401
6402                                 }
6403
6404                                 if (in->valid) {
6405                                         /* We have already filled this one.
6406                                          * We have a duplicate that will be discarded, but
6407                                          * we first have to suck out resize info if it is a file.
6408                                          */
6409
6410                                         if ((in->variantType == YAFFS_OBJECT_TYPE_FILE) &&
6411                                              ((oh &&
6412                                                oh-> type == YAFFS_OBJECT_TYPE_FILE)||
6413                                               (tags.extraHeaderInfoAvailable  &&
6414                                                tags.extraObjectType == YAFFS_OBJECT_TYPE_FILE))
6415                                             ) {
6416                                                 __u32 thisSize =
6417                                                     (oh) ? oh->fileSize : tags.
6418                                                     extraFileLength;
6419                                                 __u32 parentObjectId =
6420                                                     (oh) ? oh->
6421                                                     parentObjectId : tags.
6422                                                     extraParentObjectId;
6423
6424
6425                                                 isShrink =
6426                                                     (oh) ? oh->isShrink : tags.
6427                                                     extraIsShrinkHeader;
6428
6429                                                 /* If it is deleted (unlinked at start also means deleted)
6430                                                  * we treat the file size as being zeroed at this point.
6431                                                  */
6432                                                 if (parentObjectId ==
6433                                                     YAFFS_OBJECTID_DELETED
6434                                                     || parentObjectId ==
6435                                                     YAFFS_OBJECTID_UNLINKED) {
6436                                                         thisSize = 0;
6437                                                         isShrink = 1;
6438                                                 }
6439
6440                                                 if (isShrink &&
6441                                                     in->variant.fileVariant.
6442                                                     shrinkSize > thisSize) {
6443                                                         in->variant.fileVariant.
6444                                                             shrinkSize =
6445                                                             thisSize;
6446                                                 }
6447
6448                                                 if (isShrink) {
6449                                                         bi->hasShrinkHeader = 1;
6450                                                 }
6451
6452                                         }
6453                                         /* Use existing - destroy this one. */
6454                                         yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
6455
6456                                 }
6457
6458                                 if (!in->valid &&
6459                                     (tags.objectId == YAFFS_OBJECTID_ROOT ||
6460                                      tags.objectId ==
6461                                      YAFFS_OBJECTID_LOSTNFOUND)) {
6462                                         /* We only load some info, don't fiddle with directory structure */
6463                                         in->valid = 1;
6464
6465                                         if(oh) {
6466                                                 in->variantType = oh->type;
6467
6468                                                 in->yst_mode = oh->yst_mode;
6469 #ifdef CONFIG_YAFFS_WINCE
6470                                                 in->win_atime[0] = oh->win_atime[0];
6471                                                 in->win_ctime[0] = oh->win_ctime[0];
6472                                                 in->win_mtime[0] = oh->win_mtime[0];
6473                                                 in->win_atime[1] = oh->win_atime[1];
6474                                                 in->win_ctime[1] = oh->win_ctime[1];
6475                                                 in->win_mtime[1] = oh->win_mtime[1];
6476 #else
6477                                                 in->yst_uid = oh->yst_uid;
6478                                                 in->yst_gid = oh->yst_gid;
6479                                                 in->yst_atime = oh->yst_atime;
6480                                                 in->yst_mtime = oh->yst_mtime;
6481                                                 in->yst_ctime = oh->yst_ctime;
6482                                                 in->yst_rdev = oh->yst_rdev;
6483
6484 #endif
6485                                         } else {
6486                                                 in->variantType = tags.extraObjectType;
6487                                                 in->lazyLoaded = 1;
6488                                         }
6489
6490                                         in->hdrChunk = chunk;
6491
6492                                 } else if (!in->valid) {
6493                                         /* we need to load this info */
6494
6495                                         in->valid = 1;
6496                                         in->hdrChunk = chunk;
6497
6498                                         if(oh) {
6499                                                 in->variantType = oh->type;
6500
6501                                                 in->yst_mode = oh->yst_mode;
6502 #ifdef CONFIG_YAFFS_WINCE
6503                                                 in->win_atime[0] = oh->win_atime[0];
6504                                                 in->win_ctime[0] = oh->win_ctime[0];
6505                                                 in->win_mtime[0] = oh->win_mtime[0];
6506                                                 in->win_atime[1] = oh->win_atime[1];
6507                                                 in->win_ctime[1] = oh->win_ctime[1];
6508                                                 in->win_mtime[1] = oh->win_mtime[1];
6509 #else
6510                                                 in->yst_uid = oh->yst_uid;
6511                                                 in->yst_gid = oh->yst_gid;
6512                                                 in->yst_atime = oh->yst_atime;
6513                                                 in->yst_mtime = oh->yst_mtime;
6514                                                 in->yst_ctime = oh->yst_ctime;
6515                                                 in->yst_rdev = oh->yst_rdev;
6516 #endif
6517
6518                                                 if (oh->shadowsObject > 0)
6519                                                         yaffs_HandleShadowedObject(dev,
6520                                                                            oh->
6521                                                                            shadowsObject,
6522                                                                            1);
6523
6524
6525                                                 yaffs_SetObjectName(in, oh->name);
6526                                                 parent =
6527                                                     yaffs_FindOrCreateObjectByNumber
6528                                                         (dev, oh->parentObjectId,
6529                                                          YAFFS_OBJECT_TYPE_DIRECTORY);
6530
6531                                                  fileSize = oh->fileSize;
6532                                                  isShrink = oh->isShrink;
6533                                                  equivalentObjectId = oh->equivalentObjectId;
6534
6535                                         }
6536                                         else {
6537                                                 in->variantType = tags.extraObjectType;
6538                                                 parent =
6539                                                     yaffs_FindOrCreateObjectByNumber
6540                                                         (dev, tags.extraParentObjectId,
6541                                                          YAFFS_OBJECT_TYPE_DIRECTORY);
6542                                                  fileSize = tags.extraFileLength;
6543                                                  isShrink = tags.extraIsShrinkHeader;
6544                                                  equivalentObjectId = tags.extraEquivalentObjectId;
6545                                                 in->lazyLoaded = 1;
6546
6547                                         }
6548                                         in->dirty = 0;
6549
6550                                         /* directory stuff...
6551                                          * hook up to parent
6552                                          */
6553
6554                                         if (parent->variantType ==
6555                                             YAFFS_OBJECT_TYPE_UNKNOWN) {
6556                                                 /* Set up as a directory */
6557                                                 parent->variantType =
6558                                                     YAFFS_OBJECT_TYPE_DIRECTORY;
6559                                                 YINIT_LIST_HEAD(&parent->variant.
6560                                                                directoryVariant.
6561                                                                children);
6562                                         } else if (parent->variantType !=
6563                                                    YAFFS_OBJECT_TYPE_DIRECTORY)
6564                                         {
6565                                                 /* Hoosterman, another problem....
6566                                                  * We're trying to use a non-directory as a directory
6567                                                  */
6568
6569                                                 T(YAFFS_TRACE_ERROR,
6570                                                   (TSTR
6571                                                    ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
6572                                                     TENDSTR)));
6573                                                 parent = dev->lostNFoundDir;
6574                                         }
6575
6576                                         yaffs_AddObjectToDirectory(parent, in);
6577
6578                                         itsUnlinked = (parent == dev->deletedDir) ||
6579                                                       (parent == dev->unlinkedDir);
6580
6581                                         if (isShrink) {
6582                                                 /* Mark the block as having a shrinkHeader */
6583                                                 bi->hasShrinkHeader = 1;
6584                                         }
6585
6586                                         /* Note re hardlinks.
6587                                          * Since we might scan a hardlink before its equivalent object is scanned
6588                                          * we put them all in a list.
6589                                          * After scanning is complete, we should have all the objects, so we run
6590                                          * through this list and fix up all the chains.
6591                                          */
6592
6593                                         switch (in->variantType) {
6594                                         case YAFFS_OBJECT_TYPE_UNKNOWN:
6595                                                 /* Todo got a problem */
6596                                                 break;
6597                                         case YAFFS_OBJECT_TYPE_FILE:
6598
6599                                                 if (in->variant.fileVariant.
6600                                                     scannedFileSize < fileSize) {
6601                                                         /* This covers the case where the file size is greater
6602                                                          * than where the data is
6603                                                          * This will happen if the file is resized to be larger
6604                                                          * than its current data extents.
6605                                                          */
6606                                                         in->variant.fileVariant.fileSize = fileSize;
6607                                                         in->variant.fileVariant.scannedFileSize =
6608                                                             in->variant.fileVariant.fileSize;
6609                                                 }
6610
6611                                                 if (isShrink &&
6612                                                     in->variant.fileVariant.shrinkSize > fileSize) {
6613                                                         in->variant.fileVariant.shrinkSize = fileSize;
6614                                                 }
6615
6616                                                 break;
6617                                         case YAFFS_OBJECT_TYPE_HARDLINK:
6618                                                 if(!itsUnlinked) {
6619                                                   in->variant.hardLinkVariant.equivalentObjectId =
6620                                                     equivalentObjectId;
6621                                                   in->hardLinks.next =
6622                                                     (struct ylist_head *) hardList;
6623                                                   hardList = in;
6624                                                 }
6625                                                 break;
6626                                         case YAFFS_OBJECT_TYPE_DIRECTORY:
6627                                                 /* Do nothing */
6628                                                 break;
6629                                         case YAFFS_OBJECT_TYPE_SPECIAL:
6630                                                 /* Do nothing */
6631                                                 break;
6632                                         case YAFFS_OBJECT_TYPE_SYMLINK:
6633                                                 if(oh){
6634                                                    in->variant.symLinkVariant.alias =
6635                                                     yaffs_CloneString(oh->
6636                                                                       alias);
6637                                                    if(!in->variant.symLinkVariant.alias)
6638                                                         alloc_failed = 1;
6639                                                 }
6640                                                 break;
6641                                         }
6642
6643                                 }
6644
6645                         }
6646
6647                 } /* End of scanning for each chunk */
6648
6649                 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
6650                         /* If we got this far while scanning, then the block is fully allocated. */
6651                         state = YAFFS_BLOCK_STATE_FULL;
6652                 }
6653
6654                 bi->blockState = state;
6655
6656                 /* Now let's see if it was dirty */
6657                 if (bi->pagesInUse == 0 &&
6658                     !bi->hasShrinkHeader &&
6659                     bi->blockState == YAFFS_BLOCK_STATE_FULL) {
6660                         yaffs_BlockBecameDirty(dev, blk);
6661                 }
6662
6663         }
6664
6665         if (altBlockIndex)
6666                 YFREE_ALT(blockIndex);
6667         else
6668                 YFREE(blockIndex);
6669
6670         /* Ok, we've done all the scanning.
6671          * Fix up the hard link chains.
6672          * We should now have scanned all the objects, now it's time to add these
6673          * hardlinks.
6674          */
6675         yaffs_HardlinkFixup(dev,hardList);
6676
6677
6678         yaffs_ReleaseTempBuffer(dev, chunkData, __LINE__);
6679
6680         if(alloc_failed){
6681                 return YAFFS_FAIL;
6682         }
6683
6684         T(YAFFS_TRACE_SCAN, (TSTR("yaffs_ScanBackwards ends" TENDSTR)));
6685
6686         return YAFFS_OK;
6687 }
6688
6689 /*------------------------------  Directory Functions ----------------------------- */
6690
6691 static void yaffs_VerifyObjectInDirectory(yaffs_Object *obj)
6692 {
6693         struct ylist_head *lh;
6694         yaffs_Object *listObj;
6695
6696         int count = 0;
6697
6698         if(!obj){
6699                 T(YAFFS_TRACE_ALWAYS, (TSTR("No object to verify" TENDSTR)));
6700                 YBUG();
6701         }
6702
6703         if(yaffs_SkipVerification(obj->myDev))
6704                 return;
6705
6706         if(!obj->parent){
6707                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object does not have parent" TENDSTR)));
6708                 YBUG();
6709         }
6710
6711         if(obj->parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY){
6712                 T(YAFFS_TRACE_ALWAYS, (TSTR("Parent is not directory" TENDSTR)));
6713                 YBUG();
6714         }
6715
6716         /* Iterate through the objects in each hash entry */
6717
6718         ylist_for_each(lh, &obj->parent->variant.directoryVariant.children) {
6719                 if (lh) {
6720                         listObj = ylist_entry(lh, yaffs_Object, siblings);
6721                         yaffs_VerifyObject(listObj);
6722                         if(obj == listObj)
6723                                 count ++;
6724                 }
6725          }
6726
6727          if(count != 1){
6728                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory %d times" TENDSTR),count));
6729                 YBUG();
6730         }
6731
6732 }
6733
6734 static void yaffs_VerifyDirectory(yaffs_Object *directory)
6735 {
6736
6737         struct ylist_head *lh;
6738         yaffs_Object *listObj;
6739
6740         if(!directory)
6741                 YBUG();
6742
6743         if(yaffs_SkipFullVerification(directory->myDev))
6744                 return;
6745
6746
6747         if(directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY){
6748                 T(YAFFS_TRACE_ALWAYS, (TSTR("Directory has wrong type: %d" TENDSTR),directory->variantType));
6749                 YBUG();
6750         }
6751
6752         /* Iterate through the objects in each hash entry */
6753
6754         ylist_for_each(lh, &directory->variant.directoryVariant.children) {
6755                 if (lh) {
6756                         listObj = ylist_entry(lh, yaffs_Object, siblings);
6757                         if(listObj->parent != directory){
6758                                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory list has wrong parent %p" TENDSTR),listObj->parent));
6759                                 YBUG();
6760                         }
6761                         yaffs_VerifyObjectInDirectory(listObj);
6762                 }
6763          }
6764
6765 }
6766
6767
6768 static void yaffs_RemoveObjectFromDirectory(yaffs_Object * obj)
6769 {
6770         yaffs_Device *dev = obj->myDev;
6771         yaffs_Object *parent;
6772
6773         yaffs_VerifyObjectInDirectory(obj);
6774         parent = obj->parent;
6775
6776         yaffs_VerifyDirectory(parent);
6777
6778         if(dev && dev->removeObjectCallback)
6779                 dev->removeObjectCallback(obj);
6780
6781
6782         ylist_del_init(&obj->siblings);
6783         obj->parent = NULL;
6784
6785         yaffs_VerifyDirectory(parent);
6786
6787 }
6788
6789
6790 static void yaffs_AddObjectToDirectory(yaffs_Object * directory,
6791                                        yaffs_Object * obj)
6792 {
6793
6794         if (!directory) {
6795                 T(YAFFS_TRACE_ALWAYS,
6796                   (TSTR
6797                    ("tragedy: Trying to add an object to a null pointer directory"
6798                     TENDSTR)));
6799                 YBUG();
6800         }
6801         if (directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
6802                 T(YAFFS_TRACE_ALWAYS,
6803                   (TSTR
6804                    ("tragedy: Trying to add an object to a non-directory"
6805                     TENDSTR)));
6806                 YBUG();
6807         }
6808
6809         if (obj->siblings.prev == NULL) {
6810                 /* Not initialised */
6811                 YBUG();
6812
6813         } else if (ylist_empty(&obj->siblings)) {
6814                 YBUG();
6815         }
6816
6817
6818         yaffs_VerifyDirectory(directory);
6819
6820         yaffs_RemoveObjectFromDirectory(obj);
6821
6822
6823         /* Now add it */
6824         ylist_add(&obj->siblings, &directory->variant.directoryVariant.children);
6825         obj->parent = directory;
6826
6827         if (directory == obj->myDev->unlinkedDir
6828             || directory == obj->myDev->deletedDir) {
6829                 obj->unlinked = 1;
6830                 obj->myDev->nUnlinkedFiles++;
6831                 obj->renameAllowed = 0;
6832         }
6833
6834         yaffs_VerifyDirectory(directory);
6835         yaffs_VerifyObjectInDirectory(obj);
6836
6837
6838 }
6839
6840 yaffs_Object *yaffs_FindObjectByName(yaffs_Object * directory,
6841                                      const YCHAR * name)
6842 {
6843         int sum;
6844
6845         struct ylist_head *i;
6846         YCHAR buffer[YAFFS_MAX_NAME_LENGTH + 1];
6847
6848         yaffs_Object *l;
6849
6850         if (!name) {
6851                 return NULL;
6852         }
6853
6854         if (!directory) {
6855                 T(YAFFS_TRACE_ALWAYS,
6856                   (TSTR
6857                    ("tragedy: yaffs_FindObjectByName: null pointer directory"
6858                     TENDSTR)));
6859                 YBUG();
6860         }
6861         if (directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
6862                 T(YAFFS_TRACE_ALWAYS,
6863                   (TSTR
6864                    ("tragedy: yaffs_FindObjectByName: non-directory" TENDSTR)));
6865                 YBUG();
6866         }
6867
6868         sum = yaffs_CalcNameSum(name);
6869
6870         ylist_for_each(i, &directory->variant.directoryVariant.children) {
6871                 if (i) {
6872                         l = ylist_entry(i, yaffs_Object, siblings);
6873
6874                         if(l->parent != directory)
6875                                 YBUG();
6876
6877                         yaffs_CheckObjectDetailsLoaded(l);
6878
6879                         /* Special case for lost-n-found */
6880                         if (l->objectId == YAFFS_OBJECTID_LOSTNFOUND) {
6881                                 if (yaffs_strcmp(name, YAFFS_LOSTNFOUND_NAME) == 0) {
6882                                         return l;
6883                                 }
6884                         } else if (yaffs_SumCompare(l->sum, sum) || l->hdrChunk <= 0){
6885                                 /* LostnFound chunk called Objxxx
6886                                  * Do a real check
6887                                  */
6888                                 yaffs_GetObjectName(l, buffer,
6889                                                     YAFFS_MAX_NAME_LENGTH);
6890                                 if (yaffs_strncmp(name, buffer,YAFFS_MAX_NAME_LENGTH) == 0) {
6891                                         return l;
6892                                 }
6893
6894                         }
6895                 }
6896         }
6897
6898         return NULL;
6899 }
6900
6901
6902 #if 0
6903 int yaffs_ApplyToDirectoryChildren(yaffs_Object * theDir,
6904                                    int (*fn) (yaffs_Object *))
6905 {
6906         struct ylist_head *i;
6907         yaffs_Object *l;
6908
6909         if (!theDir) {
6910                 T(YAFFS_TRACE_ALWAYS,
6911                   (TSTR
6912                    ("tragedy: yaffs_FindObjectByName: null pointer directory"
6913                     TENDSTR)));
6914                 YBUG();
6915         }
6916         if (theDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
6917                 T(YAFFS_TRACE_ALWAYS,
6918                   (TSTR
6919                    ("tragedy: yaffs_FindObjectByName: non-directory" TENDSTR)));
6920                 YBUG();
6921         }
6922
6923         ylist_for_each(i, &theDir->variant.directoryVariant.children) {
6924                 if (i) {
6925                         l = ylist_entry(i, yaffs_Object, siblings);
6926                         if (l && !fn(l)) {
6927                                 return YAFFS_FAIL;
6928                         }
6929                 }
6930         }
6931
6932         return YAFFS_OK;
6933
6934 }
6935 #endif
6936
6937 /* GetEquivalentObject dereferences any hard links to get to the
6938  * actual object.
6939  */
6940
6941 yaffs_Object *yaffs_GetEquivalentObject(yaffs_Object * obj)
6942 {
6943         if (obj && obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
6944                 /* We want the object id of the equivalent object, not this one */
6945                 obj = obj->variant.hardLinkVariant.equivalentObject;
6946                 yaffs_CheckObjectDetailsLoaded(obj);
6947         }
6948         return obj;
6949
6950 }
6951
6952 int yaffs_GetObjectName(yaffs_Object * obj, YCHAR * name, int buffSize)
6953 {
6954         memset(name, 0, buffSize * sizeof(YCHAR));
6955
6956         yaffs_CheckObjectDetailsLoaded(obj);
6957
6958         if (obj->objectId == YAFFS_OBJECTID_LOSTNFOUND) {
6959                 yaffs_strncpy(name, YAFFS_LOSTNFOUND_NAME, buffSize - 1);
6960         } else if (obj->hdrChunk <= 0) {
6961                 YCHAR locName[20];
6962                 YCHAR numString[20];
6963                 YCHAR *x = &numString[19];
6964                 unsigned v = obj->objectId;
6965                 numString[19] = 0;
6966                 while(v>0){
6967                         x--;
6968                         *x = '0' + (v % 10);
6969                         v /= 10;
6970                 }
6971                 /* make up a name */
6972                 yaffs_strcpy(locName, YAFFS_LOSTNFOUND_PREFIX);
6973                 yaffs_strcat(locName,x);
6974                 yaffs_strncpy(name, locName, buffSize - 1);
6975
6976         }
6977 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
6978         else if (obj->shortName[0]) {
6979                 yaffs_strcpy(name, obj->shortName);
6980         }
6981 #endif
6982         else {
6983                 int result;
6984                 __u8 *buffer = yaffs_GetTempBuffer(obj->myDev, __LINE__);
6985
6986                 yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *) buffer;
6987
6988                 memset(buffer, 0, obj->myDev->nDataBytesPerChunk);
6989
6990                 if (obj->hdrChunk > 0) {
6991                         result = yaffs_ReadChunkWithTagsFromNAND(obj->myDev,
6992                                                         obj->hdrChunk, buffer,
6993                                                         NULL);
6994                 }
6995                 yaffs_strncpy(name, oh->name, buffSize - 1);
6996
6997                 yaffs_ReleaseTempBuffer(obj->myDev, buffer, __LINE__);
6998         }
6999
7000         return yaffs_strlen(name);
7001 }
7002
7003 int yaffs_GetObjectFileLength(yaffs_Object * obj)
7004 {
7005
7006         /* Dereference any hard linking */
7007         obj = yaffs_GetEquivalentObject(obj);
7008
7009         if (obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
7010                 return obj->variant.fileVariant.fileSize;
7011         }
7012         if (obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK) {
7013                 return yaffs_strlen(obj->variant.symLinkVariant.alias);
7014         } else {
7015                 /* Only a directory should drop through to here */
7016                 return obj->myDev->nDataBytesPerChunk;
7017         }
7018 }
7019
7020 int yaffs_GetObjectLinkCount(yaffs_Object * obj)
7021 {
7022         int count = 0;
7023         struct ylist_head *i;
7024
7025         if (!obj->unlinked) {
7026                 count++;        /* the object itself */
7027         }
7028         ylist_for_each(i, &obj->hardLinks) {
7029                 count++;        /* add the hard links; */
7030         }
7031         return count;
7032
7033 }
7034
7035 int yaffs_GetObjectInode(yaffs_Object * obj)
7036 {
7037         obj = yaffs_GetEquivalentObject(obj);
7038
7039         return obj->objectId;
7040 }
7041
7042 unsigned yaffs_GetObjectType(yaffs_Object * obj)
7043 {
7044         obj = yaffs_GetEquivalentObject(obj);
7045
7046         switch (obj->variantType) {
7047         case YAFFS_OBJECT_TYPE_FILE:
7048                 return DT_REG;
7049                 break;
7050         case YAFFS_OBJECT_TYPE_DIRECTORY:
7051                 return DT_DIR;
7052                 break;
7053         case YAFFS_OBJECT_TYPE_SYMLINK:
7054                 return DT_LNK;
7055                 break;
7056         case YAFFS_OBJECT_TYPE_HARDLINK:
7057                 return DT_REG;
7058                 break;
7059         case YAFFS_OBJECT_TYPE_SPECIAL:
7060                 if (S_ISFIFO(obj->yst_mode))
7061                         return DT_FIFO;
7062                 if (S_ISCHR(obj->yst_mode))
7063                         return DT_CHR;
7064                 if (S_ISBLK(obj->yst_mode))
7065                         return DT_BLK;
7066                 if (S_ISSOCK(obj->yst_mode))
7067                         return DT_SOCK;
7068         default:
7069                 return DT_REG;
7070                 break;
7071         }
7072 }
7073
7074 YCHAR *yaffs_GetSymlinkAlias(yaffs_Object * obj)
7075 {
7076         obj = yaffs_GetEquivalentObject(obj);
7077         if (obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK) {
7078                 return yaffs_CloneString(obj->variant.symLinkVariant.alias);
7079         } else {
7080                 return yaffs_CloneString(_Y(""));
7081         }
7082 }
7083
7084 #ifndef CONFIG_YAFFS_WINCE
7085
7086 int yaffs_SetAttributes(yaffs_Object * obj, struct iattr *attr)
7087 {
7088         unsigned int valid = attr->ia_valid;
7089
7090         if (valid & ATTR_MODE)
7091                 obj->yst_mode = attr->ia_mode;
7092         if (valid & ATTR_UID)
7093                 obj->yst_uid = attr->ia_uid;
7094         if (valid & ATTR_GID)
7095                 obj->yst_gid = attr->ia_gid;
7096
7097         if (valid & ATTR_ATIME)
7098                 obj->yst_atime = Y_TIME_CONVERT(attr->ia_atime);
7099         if (valid & ATTR_CTIME)
7100                 obj->yst_ctime = Y_TIME_CONVERT(attr->ia_ctime);
7101         if (valid & ATTR_MTIME)
7102                 obj->yst_mtime = Y_TIME_CONVERT(attr->ia_mtime);
7103
7104         if (valid & ATTR_SIZE)
7105                 yaffs_ResizeFile(obj, attr->ia_size);
7106
7107         yaffs_UpdateObjectHeader(obj, NULL, 1, 0, 0);
7108
7109         return YAFFS_OK;
7110
7111 }
7112 int yaffs_GetAttributes(yaffs_Object * obj, struct iattr *attr)
7113 {
7114         unsigned int valid = 0;
7115
7116         attr->ia_mode = obj->yst_mode;
7117         valid |= ATTR_MODE;
7118         attr->ia_uid = obj->yst_uid;
7119         valid |= ATTR_UID;
7120         attr->ia_gid = obj->yst_gid;
7121         valid |= ATTR_GID;
7122
7123         Y_TIME_CONVERT(attr->ia_atime) = obj->yst_atime;
7124         valid |= ATTR_ATIME;
7125         Y_TIME_CONVERT(attr->ia_ctime) = obj->yst_ctime;
7126         valid |= ATTR_CTIME;
7127         Y_TIME_CONVERT(attr->ia_mtime) = obj->yst_mtime;
7128         valid |= ATTR_MTIME;
7129
7130         attr->ia_size = yaffs_GetFileSize(obj);
7131         valid |= ATTR_SIZE;
7132
7133         attr->ia_valid = valid;
7134
7135         return YAFFS_OK;
7136
7137 }
7138
7139 #endif
7140
7141 #if 0
7142 int yaffs_DumpObject(yaffs_Object * obj)
7143 {
7144         YCHAR name[257];
7145
7146         yaffs_GetObjectName(obj, name, 256);
7147
7148         T(YAFFS_TRACE_ALWAYS,
7149           (TSTR
7150            ("Object %d, inode %d \"%s\"\n dirty %d valid %d serial %d sum %d"
7151             " chunk %d type %d size %d\n"
7152             TENDSTR), obj->objectId, yaffs_GetObjectInode(obj), name,
7153            obj->dirty, obj->valid, obj->serial, obj->sum, obj->hdrChunk,
7154            yaffs_GetObjectType(obj), yaffs_GetObjectFileLength(obj)));
7155
7156         return YAFFS_OK;
7157 }
7158 #endif
7159
7160 /*---------------------------- Initialisation code -------------------------------------- */
7161
7162 static int yaffs_CheckDevFunctions(const yaffs_Device * dev)
7163 {
7164
7165         /* Common functions, gotta have */
7166         if (!dev->eraseBlockInNAND || !dev->initialiseNAND)
7167                 return 0;
7168
7169 #ifdef CONFIG_YAFFS_YAFFS2
7170
7171         /* Can use the "with tags" style interface for yaffs1 or yaffs2 */
7172         if (dev->writeChunkWithTagsToNAND &&
7173             dev->readChunkWithTagsFromNAND &&
7174             !dev->writeChunkToNAND &&
7175             !dev->readChunkFromNAND &&
7176             dev->markNANDBlockBad && dev->queryNANDBlock)
7177                 return 1;
7178 #endif
7179
7180         /* Can use the "spare" style interface for yaffs1 */
7181         if (!dev->isYaffs2 &&
7182             !dev->writeChunkWithTagsToNAND &&
7183             !dev->readChunkWithTagsFromNAND &&
7184             dev->writeChunkToNAND &&
7185             dev->readChunkFromNAND &&
7186             !dev->markNANDBlockBad && !dev->queryNANDBlock)
7187                 return 1;
7188
7189         return 0;               /* bad */
7190 }
7191
7192
7193 static int yaffs_CreateInitialDirectories(yaffs_Device *dev)
7194 {
7195         /* Initialise the unlinked, deleted, root and lost and found directories */
7196
7197         dev->lostNFoundDir = dev->rootDir =  NULL;
7198         dev->unlinkedDir = dev->deletedDir = NULL;
7199
7200         dev->unlinkedDir =
7201             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_UNLINKED, S_IFDIR);
7202
7203         dev->deletedDir =
7204             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_DELETED, S_IFDIR);
7205
7206         dev->rootDir =
7207             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_ROOT,
7208                                       YAFFS_ROOT_MODE | S_IFDIR);
7209         dev->lostNFoundDir =
7210             yaffs_CreateFakeDirectory(dev, YAFFS_OBJECTID_LOSTNFOUND,
7211                                       YAFFS_LOSTNFOUND_MODE | S_IFDIR);
7212
7213         if(dev->lostNFoundDir && dev->rootDir && dev->unlinkedDir && dev->deletedDir){
7214                 yaffs_AddObjectToDirectory(dev->rootDir, dev->lostNFoundDir);
7215                 return YAFFS_OK;
7216         }
7217
7218         return YAFFS_FAIL;
7219 }
7220
7221 int yaffs_GutsInitialise(yaffs_Device * dev)
7222 {
7223         int init_failed = 0;
7224         unsigned x;
7225         int bits;
7226
7227         T(YAFFS_TRACE_TRACING, (TSTR("yaffs: yaffs_GutsInitialise()" TENDSTR)));
7228
7229         /* Check stuff that must be set */
7230
7231         if (!dev) {
7232                 T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs: Need a device" TENDSTR)));
7233                 return YAFFS_FAIL;
7234         }
7235
7236         dev->internalStartBlock = dev->startBlock;
7237         dev->internalEndBlock = dev->endBlock;
7238         dev->blockOffset = 0;
7239         dev->chunkOffset = 0;
7240         dev->nFreeChunks = 0;
7241
7242         dev->gcBlock = -1;
7243
7244         if (dev->startBlock == 0) {
7245                 dev->internalStartBlock = dev->startBlock + 1;
7246                 dev->internalEndBlock = dev->endBlock + 1;
7247                 dev->blockOffset = 1;
7248                 dev->chunkOffset = dev->nChunksPerBlock;
7249         }
7250
7251         /* Check geometry parameters. */
7252
7253         if ((!dev->inbandTags && dev->isYaffs2 && dev->totalBytesPerChunk < 1024) ||
7254             (!dev->isYaffs2 && dev->totalBytesPerChunk < 512) ||
7255             (dev->inbandTags && !dev->isYaffs2 ) ||
7256              dev->nChunksPerBlock < 2 ||
7257              dev->nReservedBlocks < 2 ||
7258              dev->internalStartBlock <= 0 ||
7259              dev->internalEndBlock <= 0 ||
7260              dev->internalEndBlock <= (dev->internalStartBlock + dev->nReservedBlocks + 2)      // otherwise it is too small
7261             ) {
7262                 T(YAFFS_TRACE_ALWAYS,
7263                   (TSTR
7264                    ("yaffs: NAND geometry problems: chunk size %d, type is yaffs%s, inbandTags %d "
7265                     TENDSTR), dev->totalBytesPerChunk, dev->isYaffs2 ? "2" : "", dev->inbandTags));
7266                 return YAFFS_FAIL;
7267         }
7268
7269         if (yaffs_InitialiseNAND(dev) != YAFFS_OK) {
7270                 T(YAFFS_TRACE_ALWAYS,
7271                   (TSTR("yaffs: InitialiseNAND failed" TENDSTR)));
7272                 return YAFFS_FAIL;
7273         }
7274
7275         /* Sort out space for inband tags, if required */
7276         if(dev->inbandTags)
7277                 dev->nDataBytesPerChunk = dev->totalBytesPerChunk - sizeof(yaffs_PackedTags2TagsPart);
7278         else
7279                 dev->nDataBytesPerChunk = dev->totalBytesPerChunk;
7280
7281         /* Got the right mix of functions? */
7282         if (!yaffs_CheckDevFunctions(dev)) {
7283                 /* Function missing */
7284                 T(YAFFS_TRACE_ALWAYS,
7285                   (TSTR
7286                    ("yaffs: device function(s) missing or wrong\n" TENDSTR)));
7287
7288                 return YAFFS_FAIL;
7289         }
7290
7291         /* This is really a compilation check. */
7292         if (!yaffs_CheckStructures()) {
7293                 T(YAFFS_TRACE_ALWAYS,
7294                   (TSTR("yaffs_CheckStructures failed\n" TENDSTR)));
7295                 return YAFFS_FAIL;
7296         }
7297
7298         if (dev->isMounted) {
7299                 T(YAFFS_TRACE_ALWAYS,
7300                   (TSTR("yaffs: device already mounted\n" TENDSTR)));
7301                 return YAFFS_FAIL;
7302         }
7303
7304         /* Finished with most checks. One or two more checks happen later on too. */
7305
7306         dev->isMounted = 1;
7307
7308         /* OK now calculate a few things for the device */
7309
7310         /*
7311          *  Calculate all the chunk size manipulation numbers:
7312          */
7313         x = dev->nDataBytesPerChunk;
7314         /* We always use dev->chunkShift and dev->chunkDiv */
7315         dev->chunkShift = Shifts(x);
7316         x >>= dev->chunkShift;
7317         dev->chunkDiv = x;
7318         /* We only use chunk mask if chunkDiv is 1 */
7319         dev->chunkMask = (1<<dev->chunkShift) - 1;
7320
7321         /*
7322          * Calculate chunkGroupBits.
7323          * We need to find the next power of 2 > than internalEndBlock
7324          */
7325
7326         x = dev->nChunksPerBlock * (dev->internalEndBlock + 1);
7327
7328         bits = ShiftsGE(x);
7329
7330         /* Set up tnode width if wide tnodes are enabled. */
7331         if(!dev->wideTnodesDisabled){
7332                 /* bits must be even so that we end up with 32-bit words */
7333                 if(bits & 1)
7334                         bits++;
7335                 if(bits < 16)
7336                         dev->tnodeWidth = 16;
7337                 else
7338                         dev->tnodeWidth = bits;
7339         }
7340         else
7341                 dev->tnodeWidth = 16;
7342
7343         dev->tnodeMask = (1<<dev->tnodeWidth)-1;
7344
7345         /* Level0 Tnodes are 16 bits or wider (if wide tnodes are enabled),
7346          * so if the bitwidth of the
7347          * chunk range we're using is greater than 16 we need
7348          * to figure out chunk shift and chunkGroupSize
7349          */
7350
7351         if (bits <= dev->tnodeWidth)
7352                 dev->chunkGroupBits = 0;
7353         else
7354                 dev->chunkGroupBits = bits - dev->tnodeWidth;
7355
7356
7357         dev->chunkGroupSize = 1 << dev->chunkGroupBits;
7358
7359         if (dev->nChunksPerBlock < dev->chunkGroupSize) {
7360                 /* We have a problem because the soft delete won't work if
7361                  * the chunk group size > chunks per block.
7362                  * This can be remedied by using larger "virtual blocks".
7363                  */
7364                 T(YAFFS_TRACE_ALWAYS,
7365                   (TSTR("yaffs: chunk group too large\n" TENDSTR)));
7366
7367                 return YAFFS_FAIL;
7368         }
7369
7370         /* OK, we've finished verifying the device, lets continue with initialisation */
7371
7372         /* More device initialisation */
7373         dev->garbageCollections = 0;
7374         dev->passiveGarbageCollections = 0;
7375         dev->currentDirtyChecker = 0;
7376         dev->bufferedBlock = -1;
7377         dev->doingBufferedBlockRewrite = 0;
7378         dev->nDeletedFiles = 0;
7379         dev->nBackgroundDeletions = 0;
7380         dev->nUnlinkedFiles = 0;
7381         dev->eccFixed = 0;
7382         dev->eccUnfixed = 0;
7383         dev->tagsEccFixed = 0;
7384         dev->tagsEccUnfixed = 0;
7385         dev->nErasureFailures = 0;
7386         dev->nErasedBlocks = 0;
7387         dev->isDoingGC = 0;
7388         dev->hasPendingPrioritisedGCs = 1; /* Assume the worst for now, will get fixed on first GC */
7389
7390         /* Initialise temporary buffers and caches. */
7391         if(!yaffs_InitialiseTempBuffers(dev))
7392                 init_failed = 1;
7393
7394         dev->srCache = NULL;
7395         dev->gcCleanupList = NULL;
7396
7397
7398         if (!init_failed &&
7399             dev->nShortOpCaches > 0) {
7400                 int i;
7401                 void *buf;
7402                 int srCacheBytes = dev->nShortOpCaches * sizeof(yaffs_ChunkCache);
7403
7404                 if (dev->nShortOpCaches > YAFFS_MAX_SHORT_OP_CACHES) {
7405                         dev->nShortOpCaches = YAFFS_MAX_SHORT_OP_CACHES;
7406                 }
7407
7408                 dev->srCache =  YMALLOC(srCacheBytes);
7409
7410                 buf = (__u8 *) dev->srCache;
7411
7412                 if(dev->srCache)
7413                         memset(dev->srCache,0,srCacheBytes);
7414
7415                 for (i = 0; i < dev->nShortOpCaches && buf; i++) {
7416                         dev->srCache[i].object = NULL;
7417                         dev->srCache[i].lastUse = 0;
7418                         dev->srCache[i].dirty = 0;
7419                         dev->srCache[i].data = buf = YMALLOC_DMA(dev->totalBytesPerChunk);
7420                 }
7421                 if(!buf)
7422                         init_failed = 1;
7423
7424                 dev->srLastUse = 0;
7425         }
7426
7427         dev->cacheHits = 0;
7428
7429         if(!init_failed){
7430                 dev->gcCleanupList = YMALLOC(dev->nChunksPerBlock * sizeof(__u32));
7431                 if(!dev->gcCleanupList)
7432                         init_failed = 1;
7433         }
7434
7435         if (dev->isYaffs2) {
7436                 dev->useHeaderFileSize = 1;
7437         }
7438         if(!init_failed && !yaffs_InitialiseBlocks(dev))
7439                 init_failed = 1;
7440
7441         yaffs_InitialiseTnodes(dev);
7442         yaffs_InitialiseObjects(dev);
7443
7444         if(!init_failed && !yaffs_CreateInitialDirectories(dev))
7445                 init_failed = 1;
7446
7447
7448         if(!init_failed){
7449                 /* Now scan the flash. */
7450                 if (dev->isYaffs2) {
7451                         if(yaffs_CheckpointRestore(dev)) {
7452                                 yaffs_CheckObjectDetailsLoaded(dev->rootDir);
7453                                 T(YAFFS_TRACE_ALWAYS,
7454                                   (TSTR("yaffs: restored from checkpoint" TENDSTR)));
7455                         } else {
7456
7457                                 /* Clean up the mess caused by an aborted checkpoint load
7458                                  * and scan backwards.
7459                                  */
7460                                 yaffs_DeinitialiseBlocks(dev);
7461                                 yaffs_DeinitialiseTnodes(dev);
7462                                 yaffs_DeinitialiseObjects(dev);
7463
7464
7465                                 dev->nErasedBlocks = 0;
7466                                 dev->nFreeChunks = 0;
7467                                 dev->allocationBlock = -1;
7468                                 dev->allocationPage = -1;
7469                                 dev->nDeletedFiles = 0;
7470                                 dev->nUnlinkedFiles = 0;
7471                                 dev->nBackgroundDeletions = 0;
7472                                 dev->oldestDirtySequence = 0;
7473
7474                                 if(!init_failed && !yaffs_InitialiseBlocks(dev))
7475                                         init_failed = 1;
7476
7477                                 yaffs_InitialiseTnodes(dev);
7478                                 yaffs_InitialiseObjects(dev);
7479
7480                                 if(!init_failed && !yaffs_CreateInitialDirectories(dev))
7481                                         init_failed = 1;
7482
7483                                 if(!init_failed && !yaffs_ScanBackwards(dev))
7484                                         init_failed = 1;
7485                         }
7486                 }else
7487                         if(!yaffs_Scan(dev))
7488                                 init_failed = 1;
7489
7490                 yaffs_StripDeletedObjects(dev);
7491         }
7492
7493         if(init_failed){
7494                 /* Clean up the mess */
7495                 T(YAFFS_TRACE_TRACING,
7496                   (TSTR("yaffs: yaffs_GutsInitialise() aborted.\n" TENDSTR)));
7497
7498                 yaffs_Deinitialise(dev);
7499                 return YAFFS_FAIL;
7500         }
7501
7502         /* Zero out stats */
7503         dev->nPageReads = 0;
7504         dev->nPageWrites = 0;
7505         dev->nBlockErasures = 0;
7506         dev->nGCCopies = 0;
7507         dev->nRetriedWrites = 0;
7508
7509         dev->nRetiredBlocks = 0;
7510
7511         yaffs_VerifyFreeChunks(dev);
7512         yaffs_VerifyBlocks(dev);
7513
7514
7515         T(YAFFS_TRACE_TRACING,
7516           (TSTR("yaffs: yaffs_GutsInitialise() done.\n" TENDSTR)));
7517         return YAFFS_OK;
7518
7519 }
7520
7521 void yaffs_Deinitialise(yaffs_Device * dev)
7522 {
7523         if (dev->isMounted) {
7524                 int i;
7525
7526                 yaffs_DeinitialiseBlocks(dev);
7527                 yaffs_DeinitialiseTnodes(dev);
7528                 yaffs_DeinitialiseObjects(dev);
7529                 if (dev->nShortOpCaches > 0 &&
7530                     dev->srCache) {
7531
7532                         for (i = 0; i < dev->nShortOpCaches; i++) {
7533                                 if(dev->srCache[i].data)
7534                                         YFREE(dev->srCache[i].data);
7535                                 dev->srCache[i].data = NULL;
7536                         }
7537
7538                         YFREE(dev->srCache);
7539                         dev->srCache = NULL;
7540                 }
7541
7542                 YFREE(dev->gcCleanupList);
7543
7544                 for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
7545                         YFREE(dev->tempBuffer[i].buffer);
7546                 }
7547
7548
7549                 dev->isMounted = 0;
7550
7551                 if(dev->deinitialiseNAND)
7552                         dev->deinitialiseNAND(dev);
7553         }
7554
7555 }
7556
7557 static int yaffs_CountFreeChunks(yaffs_Device * dev)
7558 {
7559         int nFree;
7560         int b;
7561
7562         yaffs_BlockInfo *blk;
7563
7564         for (nFree = 0, b = dev->internalStartBlock; b <= dev->internalEndBlock;
7565              b++) {
7566                 blk = yaffs_GetBlockInfo(dev, b);
7567
7568                 switch (blk->blockState) {
7569                 case YAFFS_BLOCK_STATE_EMPTY:
7570                 case YAFFS_BLOCK_STATE_ALLOCATING:
7571                 case YAFFS_BLOCK_STATE_COLLECTING:
7572                 case YAFFS_BLOCK_STATE_FULL:
7573                         nFree +=
7574                             (dev->nChunksPerBlock - blk->pagesInUse +
7575                              blk->softDeletions);
7576                         break;
7577                 default:
7578                         break;
7579                 }
7580
7581         }
7582
7583         return nFree;
7584 }
7585
7586 int yaffs_GetNumberOfFreeChunks(yaffs_Device * dev)
7587 {
7588         /* This is what we report to the outside world */
7589
7590         int nFree;
7591         int nDirtyCacheChunks;
7592         int blocksForCheckpoint;
7593
7594 #if 1
7595         nFree = dev->nFreeChunks;
7596 #else
7597         nFree = yaffs_CountFreeChunks(dev);
7598 #endif
7599
7600         nFree += dev->nDeletedFiles;
7601
7602         /* Now count the number of dirty chunks in the cache and subtract those */
7603
7604         {
7605                 int i;
7606                 for (nDirtyCacheChunks = 0, i = 0; i < dev->nShortOpCaches; i++) {
7607                         if (dev->srCache[i].dirty)
7608                                 nDirtyCacheChunks++;
7609                 }
7610         }
7611
7612         nFree -= nDirtyCacheChunks;
7613
7614         nFree -= ((dev->nReservedBlocks + 1) * dev->nChunksPerBlock);
7615
7616         /* Now we figure out how much to reserve for the checkpoint and report that... */
7617         blocksForCheckpoint = yaffs_CalcCheckpointBlocksRequired(dev) - dev->blocksInCheckpoint;
7618         if(blocksForCheckpoint < 0)
7619                 blocksForCheckpoint = 0;
7620
7621         nFree -= (blocksForCheckpoint * dev->nChunksPerBlock);
7622
7623         if (nFree < 0)
7624                 nFree = 0;
7625
7626         return nFree;
7627
7628 }
7629
7630 static int yaffs_freeVerificationFailures;
7631
7632 static void yaffs_VerifyFreeChunks(yaffs_Device * dev)
7633 {
7634         int counted;
7635         int difference;
7636
7637         if(yaffs_SkipVerification(dev))
7638                 return;
7639
7640         counted = yaffs_CountFreeChunks(dev);
7641
7642         difference = dev->nFreeChunks - counted;
7643
7644         if (difference) {
7645                 T(YAFFS_TRACE_ALWAYS,
7646                   (TSTR("Freechunks verification failure %d %d %d" TENDSTR),
7647                    dev->nFreeChunks, counted, difference));
7648                 yaffs_freeVerificationFailures++;
7649         }
7650 }
7651
7652 /*---------------------------------------- YAFFS test code ----------------------*/
7653
7654 #define yaffs_CheckStruct(structure,syze, name) \
7655         do { \
7656            if(sizeof(structure) != syze) \
7657                { \
7658                  T(YAFFS_TRACE_ALWAYS,(TSTR("%s should be %d but is %d\n" TENDSTR),\
7659                  name,syze,sizeof(structure))); \
7660                  return YAFFS_FAIL; \
7661                 } \
7662         } while(0)
7663
7664 static int yaffs_CheckStructures(void)
7665 {
7666 /*      yaffs_CheckStruct(yaffs_Tags,8,"yaffs_Tags"); */
7667 /*      yaffs_CheckStruct(yaffs_TagsUnion,8,"yaffs_TagsUnion"); */
7668 /*      yaffs_CheckStruct(yaffs_Spare,16,"yaffs_Spare"); */
7669 #ifndef CONFIG_YAFFS_TNODE_LIST_DEBUG
7670         yaffs_CheckStruct(yaffs_Tnode, 2 * YAFFS_NTNODES_LEVEL0, "yaffs_Tnode");
7671 #endif
7672 #ifndef CONFIG_YAFFS_WINCE
7673                 yaffs_CheckStruct(yaffs_ObjectHeader, 512, "yaffs_ObjectHeader");
7674 #endif
7675             return YAFFS_OK;
7676 }