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