yaffs_guts.c

   1 /*
   2  * YAFFS: Yet another FFS. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002 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  //yaffs_guts.c
  15
  16 const char *yaffs_guts_c_version="$Id: yaffs_guts.c,v 1.17 2005-08-09 04:17:30 charles Exp $";
  17
  18 #include "yportenv.h"
  19
  20 #include "yaffsinterface.h"
  21 #include "yaffs_guts.h"
  22 #include "yaffs_tagsvalidity.h"
  23
  24
  25 #include "yaffs_tagscompat.h"
  26
  27 #ifdef CONFIG_YAFFS_WINCE
  28 void yfsd_LockYAFFS(BOOL fsLockOnly);
  29 void yfsd_UnlockYAFFS(BOOL fsLockOnly);
  30 #endif
  31
  32 #define YAFFS_PASSIVE_GC_CHUNKS 2
  33
  34
  35 #include "yaffs_ecc.h"
  36
  37
  38
  39 // NAND access
  40
  41
  42 static Y_INLINE int yaffs_ReadChunkWithTagsFromNAND(yaffs_Device *dev,int chunkInNAND, __u8 *buffer, yaffs_ExtendedTags *tags);
  43 static Y_INLINE int yaffs_WriteChunkWithTagsToNAND(yaffs_Device *dev,int chunkInNAND, const __u8 *data, yaffs_ExtendedTags *tags);
  44 static Y_INLINE int yaffs_MarkBlockBad(yaffs_Device *dev, int blockNo);
  45 static Y_INLINE int yaffs_QueryInitialBlockState(yaffs_Device *dev,int blockNo, yaffs_BlockState *state,unsigned *sequenceNumber);
  46 // Local prototypes
  47 static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device *dev, const __u8 *buffer, yaffs_ExtendedTags *tags, int useReserve);
  48 static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan);
  49
  50 static yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type);
  51 static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj);
  52 static int yaffs_UpdateObjectHeader(yaffs_Object *in,const YCHAR *name, int force,int isShrink, int shadows);
  53 static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj);
  54 static int yaffs_CheckStructures(void);
  55 static int yaffs_DeleteWorker(yaffs_Object *in, yaffs_Tnode *tn, __u32 level, int chunkOffset,int *limit);
  56 static int yaffs_DoGenericObjectDeletion(yaffs_Object *in);
  57
  58 static yaffs_BlockInfo *yaffs_GetBlockInfo(yaffs_Device *dev,int blockNo);
  59
  60 static __u8 *yaffs_GetTempBuffer(yaffs_Device *dev,int lineNo);
  61 static void yaffs_ReleaseTempBuffer(yaffs_Device *dev, __u8 *buffer, int lineNo);
  62
  63
  64 // Robustification (if it ever comes about...)
  65 static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND);
  66 static void yaffs_HandleWriteChunkError(yaffs_Device *dev,int chunkInNAND);
  67 static void yaffs_HandleWriteChunkOk(yaffs_Device *dev,int chunkInNAND,const __u8 *data, const yaffs_ExtendedTags *tags);
  68 static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND,  const yaffs_ExtendedTags *tags);
  69
  70 static int  yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND);
  71
  72 static int yaffs_UnlinkWorker(yaffs_Object *obj);
  73 static void yaffs_DestroyObject(yaffs_Object *obj);
  74
  75
  76 static int yaffs_TagsMatch(const yaffs_ExtendedTags *tags, int objectId, int chunkInObject);
  77
  78
  79 loff_t yaffs_GetFileSize(yaffs_Object *obj);
  80
  81
  82 static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve);
  83
  84 static void yaffs_VerifyFreeChunks(yaffs_Device *dev);
  85
  86 #ifdef YAFFS_PARANOID
  87 static int yaffs_CheckFileSanity(yaffs_Object *in);
  88 #else
  89 #define yaffs_CheckFileSanity(in)
  90 #endif
  91
  92 static void yaffs_InvalidateWholeChunkCache(yaffs_Object *in);
  93 static void yaffs_InvalidateChunkCache(yaffs_Object *object, int chunkId);
  94
  95 static int yaffs_ReadChunkWithTagsFromNAND(yaffs_Device *dev,int chunkInNAND, __u8 *buffer, yaffs_ExtendedTags *tags)
  96 {
  97         chunkInNAND -= dev->chunkOffset;
  98
  99         if(dev->readChunkWithTagsFromNAND)
 100                 return dev->readChunkWithTagsFromNAND(dev,chunkInNAND,buffer,tags);
 101         else
 102                 return yaffs_TagsCompatabilityReadChunkWithTagsFromNAND(dev,chunkInNAND,buffer,tags);
 103 }
 104
 105 static Y_INLINE int yaffs_WriteChunkWithTagsToNAND(yaffs_Device *dev,int chunkInNAND, const __u8 *buffer, yaffs_ExtendedTags *tags)
 106 {
 107         chunkInNAND -= dev->chunkOffset;
 108
 109         if(tags)
 110         {
 111                 tags->sequenceNumber = dev->sequenceNumber;
 112                 tags->chunkUsed = 1;
 113                 if(!yaffs_ValidateTags(tags))
 114                 {
 115                         T(YAFFS_TRACE_ERROR,(TSTR("Writing uninitialised tags" TENDSTR)));
 116                         YBUG();
 117                 }
 118                 T(YAFFS_TRACE_WRITE,(TSTR("Writing chunk %d tags %d %d"TENDSTR),chunkInNAND,tags->objectId,tags->chunkId));
 119         }
 120         else
 121         {
 122                         T(YAFFS_TRACE_ERROR,(TSTR("Writing with no tags" TENDSTR)));
 123                         YBUG();
 124         }
 125
 126         if(dev->writeChunkWithTagsToNAND)
 127                 return dev->writeChunkWithTagsToNAND(dev,chunkInNAND,buffer,tags);
 128         else
 129                 return yaffs_TagsCompatabilityWriteChunkWithTagsToNAND(dev,chunkInNAND,buffer,tags);
 130 }
 131
 132 static Y_INLINE int yaffs_MarkBlockBad(yaffs_Device *dev, int blockNo)
 133 {
 134         blockNo -= dev->blockOffset;
 135
 136         if(dev->markNANDBlockBad)
 137                 return dev->markNANDBlockBad(dev,blockNo);
 138         else
 139                 return yaffs_TagsCompatabilityMarkNANDBlockBad(dev,blockNo);
 140 }
 141 static Y_INLINE int yaffs_QueryInitialBlockState(yaffs_Device *dev,int blockNo, yaffs_BlockState *state, unsigned *sequenceNumber)
 142 {
 143         blockNo -= dev->blockOffset;
 144
 145         if(dev->queryNANDBlock)
 146                 return dev->queryNANDBlock(dev,blockNo,state,sequenceNumber);
 147         else
 148                 return yaffs_TagsCompatabilityQueryNANDBlock(dev,blockNo,state,sequenceNumber);
 149 }
 150
 151 static int yaffs_EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND)
 152 {
 153         int result;
 154
 155         blockInNAND -= dev->blockOffset;
 156
 157         dev->nBlockErasures++;
 158         result = dev->eraseBlockInNAND(dev,blockInNAND);
 159
 160         if(!result)result = dev->eraseBlockInNAND(dev,blockInNAND); // If at first we don't succeed, try again *once*.
 161         return result;
 162 }
 163
 164 static int yaffs_InitialiseNAND(struct yaffs_DeviceStruct *dev)
 165 {
 166         return dev->initialiseNAND(dev);
 167 }
 168
 169
 170
 171
 172 // Temporary buffer manipulations
 173
 174 static __u8 *yaffs_GetTempBuffer(yaffs_Device *dev,int lineNo)
 175 {
 176         int i,j;
 177         for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
 178         {
 179                 if(dev->tempBuffer[i].line == 0)
 180                 {
 181                         dev->tempBuffer[i].line = lineNo;
 182                         if((i+1) > dev->maxTemp)
 183                         {
 184                                 dev->maxTemp = i + 1;
 185                                 for(j = 0; j <= i; j++)
 186                                         dev->tempBuffer[j].maxLine = dev->tempBuffer[j].line;
 187                         }
 188
 189                         return dev->tempBuffer[i].buffer;
 190                 }
 191         }
 192
 193         T(YAFFS_TRACE_BUFFERS,(TSTR("Out of temp buffers at line %d, other held by lines:"),lineNo));
 194         for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
 195         {
 196                 T(YAFFS_TRACE_BUFFERS,(TSTR(" %d "),dev->tempBuffer[i].line));
 197         }
 198         T(YAFFS_TRACE_BUFFERS,(TSTR(" "TENDSTR)));
 199
 200         dev->unmanagedTempAllocations++;
 201         // Get an unmanaged one
 202         return YMALLOC(dev->nBytesPerChunk);
 203
 204
 205 }
 206
 207 static void yaffs_ReleaseTempBuffer(yaffs_Device *dev, __u8 *buffer, int lineNo)
 208 {
 209         int i;
 210         for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
 211         {
 212                 if(dev->tempBuffer[i].buffer == buffer)
 213                 {
 214                         dev->tempBuffer[i].line = 0;
 215                         return;
 216                 }
 217         }
 218
 219         if(buffer)
 220         {
 221                 // assume it is an unmanaged one.
 222                 T(YAFFS_TRACE_BUFFERS,(TSTR("Releasing unmanaged temp buffer in line %d" TENDSTR),lineNo));
 223                 YFREE(buffer);
 224                 dev->unmanagedTempDeallocations++;
 225         }
 226
 227 }
 228
 229
 230 // Chunk bitmap manipulations
 231
 232 static Y_INLINE __u8 *yaffs_BlockBits(yaffs_Device *dev, int blk)
 233 {
 234         if(blk < dev->internalStartBlock || blk > dev->internalEndBlock)
 235         {
 236                 T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs: BlockBits block %d is not valid" TENDSTR),blk));
 237                 YBUG();
 238         }
 239         return dev->chunkBits + (dev->chunkBitmapStride * (blk - dev->internalStartBlock));
 240 }
 241
 242 static Y_INLINE void yaffs_ClearChunkBits(yaffs_Device *dev,int blk)
 243 {
 244         __u8 *blkBits = yaffs_BlockBits(dev,blk);
 245
 246          memset(blkBits,0,dev->chunkBitmapStride);
 247 }
 248
 249 static Y_INLINE void yaffs_ClearChunkBit(yaffs_Device *dev,int blk,int chunk)
 250 {
 251         __u8 *blkBits = yaffs_BlockBits(dev,blk);
 252
 253         blkBits[chunk/8] &=  ~ (1<<(chunk & 7));
 254 }
 255
 256 static Y_INLINE void yaffs_SetChunkBit(yaffs_Device *dev,int blk,int chunk)
 257 {
 258         __u8 *blkBits = yaffs_BlockBits(dev,blk);
 259
 260         blkBits[chunk/8] |=   (1<<(chunk & 7));
 261 }
 262
 263 static Y_INLINE int yaffs_CheckChunkBit(yaffs_Device *dev,int blk,int chunk)
 264 {
 265         __u8 *blkBits = yaffs_BlockBits(dev,blk);
 266         return (blkBits[chunk/8] &  (1<<(chunk & 7))) ? 1 :0;
 267 }
 268
 269 static Y_INLINE int yaffs_StillSomeChunkBits(yaffs_Device *dev,int blk)
 270 {
 271         __u8 *blkBits = yaffs_BlockBits(dev,blk);
 272         int i;
 273         for(i = 0; i < dev->chunkBitmapStride; i++)
 274         {
 275                 if(*blkBits) return 1;
 276                 blkBits++;
 277         }
 278         return 0;
 279 }
 280
 281
 282 static  Y_INLINE int yaffs_HashFunction(int n)
 283 {
 284         return (n % YAFFS_NOBJECT_BUCKETS);
 285 }
 286
 287
 288 yaffs_Object *yaffs_Root(yaffs_Device *dev)
 289 {
 290         return dev->rootDir;
 291 }
 292
 293 yaffs_Object *yaffs_LostNFound(yaffs_Device *dev)
 294 {
 295         return dev->lostNFoundDir;
 296 }
 297
 298
 299
 300
 301 int yaffs_CheckFF(__u8 *buffer,int nBytes)
 302 {
 303         //Horrible, slow implementation
 304         while(nBytes--)
 305         {
 306                 if(*buffer != 0xFF) return 0;
 307                 buffer++;
 308         }
 309         return 1;
 310 }
 311
 312 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND)
 313 {
 314
 315         int retval = YAFFS_OK;
 316         __u8 *data = yaffs_GetTempBuffer(dev,__LINE__);
 317         yaffs_ExtendedTags tags;
 318
 319 // NCB          dev->readChunkWithTagsFromNAND(dev,chunkInNAND,data,&tags);
 320         yaffs_ReadChunkWithTagsFromNAND(dev,chunkInNAND,data,&tags);
 321
 322         if(!yaffs_CheckFF(data,dev->nBytesPerChunk) || tags.chunkUsed)
 323         {
 324                 T(YAFFS_TRACE_NANDACCESS,(TSTR("Chunk %d not erased" TENDSTR),chunkInNAND));
 325                 retval = YAFFS_FAIL;
 326         }
 327
 328         yaffs_ReleaseTempBuffer(dev,data,__LINE__);
 329
 330         return retval;
 331
 332 }
 333
 334
 335
 336 static int yaffs_WriteNewChunkWithTagsToNAND(struct yaffs_DeviceStruct *dev, const __u8 *data, yaffs_ExtendedTags *tags,int useReserve)
 337 {
 338         int chunk;
 339
 340         int writeOk = 1;
 341         int attempts = 0;
 342
 343
 344
 345         do{
 346                 chunk = yaffs_AllocateChunk(dev,useReserve);
 347
 348                 if(chunk >= 0)
 349                 {
 350
 351                         // First check this chunk is erased...
 352 #ifndef CONFIG_YAFFS_DISABLE_CHUNK_ERASED_CHECK
 353                         writeOk = yaffs_CheckChunkErased(dev,chunk);
 354 #endif
 355                         if(!writeOk)
 356                         {
 357                                 T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs chunk %d was not erased" TENDSTR),chunk));
 358                         }
 359                         else
 360                         {
 361                                 writeOk =  yaffs_WriteChunkWithTagsToNAND(dev,chunk,data,tags);
 362                         }
 363                         attempts++;
 364
 365                         if(writeOk)
 366                         {
 367                                 // Copy the data into the robustification buffer.
 368                                 // NB We do this at the end to prevent duplicates in the case of a write error.
 369                                 //Todo
 370                                 yaffs_HandleWriteChunkOk(dev,chunk,data,tags);
 371                         }
 372                         else
 373                         {
 374                                 yaffs_HandleWriteChunkError(dev,chunk);
 375                         }
 376                 }
 377
 378         } while(chunk >= 0 && ! writeOk);
 379
 380         if(attempts > 1)
 381         {
 382                 T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs write required %d attempts" TENDSTR),attempts));
 383                 dev->nRetriedWrites+= (attempts - 1);
 384         }
 385
 386
 387
 388         return chunk;
 389 }
 390
 391
 392
 393 ///
 394 // Functions for robustisizing
 395 //
 396 //
 397
 398 static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND)
 399 {
 400
 401         yaffs_MarkBlockBad(dev,blockInNAND);
 402
 403         yaffs_GetBlockInfo(dev,blockInNAND)->blockState = YAFFS_BLOCK_STATE_DEAD;
 404
 405         dev->nRetiredBlocks++;
 406 }
 407
 408
 409
 410 static void yaffs_HandleWriteChunkOk(yaffs_Device *dev,int chunkInNAND,const __u8 *data, const yaffs_ExtendedTags *tags)
 411 {
 412 }
 413
 414 static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND, const yaffs_ExtendedTags *tags)
 415 {
 416 }
 417
 418 static void yaffs_HandleWriteChunkError(yaffs_Device *dev,int chunkInNAND)
 419 {
 420         int blockInNAND = chunkInNAND/dev->nChunksPerBlock;
 421
 422         // Mark the block for retirement
 423         yaffs_GetBlockInfo(dev,blockInNAND)->needsRetiring = 1;
 424         // Delete the chunk
 425         yaffs_DeleteChunk(dev,chunkInNAND,1,__LINE__);
 426 }
 427
 428
 429
 430 ///////////////////////// Object management //////////////////
 431 // List of spare objects
 432 // The list is hooked together using the first pointer
 433 // in the object
 434
 435 // static yaffs_Object *yaffs_freeObjects = NULL;
 436
 437 // static int yaffs_nFreeObjects;
 438
 439 // static yaffs_ObjectList *yaffs_allocatedObjectList = NULL;
 440
 441 // static yaffs_ObjectBucket yaffs_objectBucket[YAFFS_NOBJECT_BUCKETS];
 442
 443
 444 static __u16 yaffs_CalcNameSum(const YCHAR *name)
 445 {
 446         __u16 sum = 0;
 447         __u16 i = 1;
 448
 449         YUCHAR *bname = (YUCHAR *)name;
 450         if(bname)
 451         {
 452                 while ((*bname) && (i <=YAFFS_MAX_NAME_LENGTH))
 453                 {
 454
 455 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
 456                         sum += yaffs_toupper(*bname) * i;
 457 #else
 458                         sum += (*bname) * i;
 459 #endif
 460                         i++;
 461                         bname++;
 462                 }
 463         }
 464         return sum;
 465 }
 466
 467 static void yaffs_SetObjectName(yaffs_Object *obj, const YCHAR *name)
 468 {
 469 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
 470                                         if(name && yaffs_strlen(name) <= YAFFS_SHORT_NAME_LENGTH)
 471                                         {
 472                                                 yaffs_strcpy(obj->shortName,name);
 473                                         }
 474                                         else
 475                                         {
 476                                                 obj->shortName[0]=_Y('\0');
 477                                         }
 478 #endif
 479                                         obj->sum = yaffs_CalcNameSum(name);
 480 }
 481
 482
 483
 484 ///////////////////////// TNODES ///////////////////////
 485
 486 // List of spare tnodes
 487 // The list is hooked together using the first pointer
 488 // in the tnode.
 489
 490 //static yaffs_Tnode *yaffs_freeTnodes = NULL;
 491
 492 // static int yaffs_nFreeTnodes;
 493
 494 //static yaffs_TnodeList *yaffs_allocatedTnodeList = NULL;
 495
 496
 497
 498 // yaffs_CreateTnodes creates a bunch more tnodes and
 499 // adds them to the tnode free list.
 500 // Don't use this function directly
 501
 502 static int yaffs_CreateTnodes(yaffs_Device *dev,int nTnodes)
 503 {
 504     int i;
 505     yaffs_Tnode *newTnodes;
 506     yaffs_TnodeList *tnl;
 507
 508     if(nTnodes < 1) return YAFFS_OK;
 509
 510         // make these things
 511
 512     newTnodes = YMALLOC(nTnodes * sizeof(yaffs_Tnode));
 513
 514     if (!newTnodes)
 515     {
 516                 T(YAFFS_TRACE_ERROR,(TSTR("yaffs: Could not allocate Tnodes"TENDSTR)));
 517                 return YAFFS_FAIL;
 518     }
 519
 520     // Hook them into the free list
 521     for(i = 0; i < nTnodes - 1; i++)
 522     {
 523         newTnodes[i].internal[0] = &newTnodes[i+1];
 524 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 525         newTnodes[i].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
 526 #endif
 527     }
 528
 529         newTnodes[nTnodes - 1].internal[0] = dev->freeTnodes;
 530 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 531         newTnodes[nTnodes - 1].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
 532 #endif
 533         dev->freeTnodes = newTnodes;
 534         dev->nFreeTnodes+= nTnodes;
 535         dev->nTnodesCreated += nTnodes;
 536
 537         // Now add this bunch of tnodes to a list for freeing up.
 538         // NB If we can't add this to the management list it isn't fatal
 539         // but it just means we can't free this bunch of tnodes later.
 540         tnl = YMALLOC(sizeof(yaffs_TnodeList));
 541         if(!tnl)
 542         {
 543                 T(YAFFS_TRACE_ERROR,(TSTR("yaffs: Could not add tnodes to management list" TENDSTR)));
 544
 545         }
 546         else
 547         {
 548                 tnl->tnodes = newTnodes;
 549                 tnl->next = dev->allocatedTnodeList;
 550                 dev->allocatedTnodeList = tnl;
 551         }
 552
 553
 554         T(YAFFS_TRACE_ALLOCATE,(TSTR("yaffs: Tnodes added" TENDSTR)));
 555
 556
 557         return YAFFS_OK;
 558 }
 559
 560
 561 // GetTnode gets us a clean tnode. Tries to make allocate more if we run out
 562 static yaffs_Tnode *yaffs_GetTnode(yaffs_Device *dev)
 563 {
 564         yaffs_Tnode *tn = NULL;
 565
 566         // If there are none left make more
 567         if(!dev->freeTnodes)
 568         {
 569                 yaffs_CreateTnodes(dev,YAFFS_ALLOCATION_NTNODES);
 570         }
 571
 572         if(dev->freeTnodes)
 573         {
 574                 tn = dev->freeTnodes;
 575 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 576         if(tn->internal[YAFFS_NTNODES_INTERNAL] != (void *)1)
 577                 {
 578                         // Hoosterman, this thing looks like it isn't in the list
 579                                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: Tnode list bug 1" TENDSTR)));
 580                 }
 581 #endif
 582                 dev->freeTnodes = dev->freeTnodes->internal[0];
 583                 dev->nFreeTnodes--;
 584                 // zero out
 585                 memset(tn,0,sizeof(yaffs_Tnode));
 586         }
 587
 588
 589         return tn;
 590 }
 591
 592
 593 // FreeTnode frees up a tnode and puts it back on the free list
 594 static void yaffs_FreeTnode(yaffs_Device*dev, yaffs_Tnode *tn)
 595 {
 596         if(tn)
 597         {
 598 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 599         if(tn->internal[YAFFS_NTNODES_INTERNAL] != 0)
 600                 {
 601                         // Hoosterman, this thing looks like it is already in the list
 602                                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: Tnode list bug 2" TENDSTR)));
 603                 }
 604                 tn->internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
 605 #endif
 606                 tn->internal[0] = dev->freeTnodes;
 607                 dev->freeTnodes = tn;
 608                 dev->nFreeTnodes++;
 609         }
 610 }
 611
 612
 613 static void yaffs_DeinitialiseTnodes(yaffs_Device*dev)
 614 {
 615         // Free the list of allocated tnodes
 616         yaffs_TnodeList *tmp;
 617
 618         while(dev->allocatedTnodeList)
 619         {
 620                 tmp =  dev->allocatedTnodeList->next;
 621
 622                 YFREE(dev->allocatedTnodeList->tnodes);
 623                 YFREE(dev->allocatedTnodeList);
 624                 dev->allocatedTnodeList = tmp;
 625
 626         }
 627
 628         dev->freeTnodes = NULL;
 629         dev->nFreeTnodes = 0;
 630 }
 631
 632 static void yaffs_InitialiseTnodes(yaffs_Device*dev)
 633 {
 634         dev->allocatedTnodeList = NULL;
 635         dev->freeTnodes = NULL;
 636         dev->nFreeTnodes = 0;
 637         dev->nTnodesCreated = 0;
 638
 639 }
 640
 641
 642
 643 ////////////////// END OF TNODE MANIPULATION ///////////////////////////
 644
 645 /////////////// Functions to manipulate the look-up tree (made up of tnodes)
 646 // The look up tree is represented by the top tnode and the number of topLevel
 647 // in the tree. 0 means only the level 0 tnode is in the tree.
 648
 649
 650 // FindLevel0Tnode finds the level 0 tnode, if one exists.
 651 // Used when reading.....
 652 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device *dev,yaffs_FileStructure *fStruct, __u32 chunkId)
 653 {
 654
 655         yaffs_Tnode *tn = fStruct->top;
 656         __u32 i;
 657         int requiredTallness;
 658         int level = fStruct->topLevel;
 659
 660         // Check sane level and chunk Id
 661         if(level < 0 || level > YAFFS_TNODES_MAX_LEVEL)
 662         {
 663 //              char str[50];
 664 //              sprintf(str,"Bad level %d",level);
 665 //              YALERT(str);
 666                 return NULL;
 667         }
 668
 669         if(chunkId > YAFFS_MAX_CHUNK_ID)
 670         {
 671 //              char str[50];
 672 //              sprintf(str,"Bad chunkId %d",chunkId);
 673 //              YALERT(str);
 674                 return NULL;
 675         }
 676
 677         // First check we're tall enough (ie enough topLevel)
 678
 679         i = chunkId >> (/*dev->chunkGroupBits  + */YAFFS_TNODES_LEVEL0_BITS);
 680         requiredTallness = 0;
 681         while(i)
 682         {
 683                 i >>= YAFFS_TNODES_INTERNAL_BITS;
 684                 requiredTallness++;
 685         }
 686
 687
 688         if(requiredTallness > fStruct->topLevel)
 689         {
 690                 // Not tall enough, so we can't find it, return NULL.
 691                 return NULL;
 692         }
 693
 694
 695         // Traverse down to level 0
 696         while (level > 0 && tn)
 697         {
 698             tn = tn->internal[(chunkId >>(/* dev->chunkGroupBits + */ YAFFS_TNODES_LEVEL0_BITS + (level-1) * YAFFS_TNODES_INTERNAL_BITS)) &
 699                                YAFFS_TNODES_INTERNAL_MASK];
 700                 level--;
 701
 702         }
 703
 704         return tn;
 705 }
 706
 707 // AddOrFindLevel0Tnode finds the level 0 tnode if it exists, otherwise first expands the tree.
 708 // This happens in two steps:
 709 //  1. If the tree isn't tall enough, then make it taller.
 710 //  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
 711 //
 712 // Used when modifying the tree.
 713 //
 714 static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device *dev, yaffs_FileStructure *fStruct, __u32 chunkId)
 715 {
 716
 717         yaffs_Tnode *tn;
 718
 719         int requiredTallness;
 720         int i;
 721         int l;
 722
 723         __u32 x;
 724
 725
 726         //T((TSTR("AddOrFind topLevel=%d, chunk=%d"),fStruct->topLevel,chunkId));
 727
 728         // Check sane level and page Id
 729         if(fStruct->topLevel < 0 || fStruct->topLevel > YAFFS_TNODES_MAX_LEVEL)
 730         {
 731 //              char str[50];
 732 //              sprintf(str,"Bad level %d",fStruct->topLevel);
 733 //              YALERT(str);
 734                 return NULL;
 735         }
 736
 737         if(chunkId > YAFFS_MAX_CHUNK_ID)
 738         {
 739 //              char str[50];
 740 //              sprintf(str,"Bad chunkId %d",chunkId);
 741 //              YALERT(str);
 742                 return NULL;
 743         }
 744
 745         // First check we're tall enough (ie enough topLevel)
 746
 747         x = chunkId >> (/*dev->chunkGroupBits + */YAFFS_TNODES_LEVEL0_BITS);
 748         requiredTallness = 0;
 749         while(x)
 750         {
 751                 x >>= YAFFS_TNODES_INTERNAL_BITS;
 752                 requiredTallness++;
 753         }
 754
 755         //T((TSTR(" required=%d"),requiredTallness));
 756
 757
 758         if(requiredTallness > fStruct->topLevel)
 759         {
 760                 // Not tall enough,gotta make the tree taller
 761                 for(i = fStruct->topLevel; i < requiredTallness; i++)
 762                 {
 763                         //T((TSTR(" add new top")));
 764
 765                         tn = yaffs_GetTnode(dev);
 766
 767                         if(tn)
 768                         {
 769                                 tn->internal[0] = fStruct->top;
 770                                 fStruct->top = tn;
 771                         }
 772                         else
 773                         {
 774                                         T(YAFFS_TRACE_ERROR,(TSTR("yaffs: no more tnodes" TENDSTR)));
 775                         }
 776                 }
 777
 778                 fStruct->topLevel = requiredTallness;
 779         }
 780
 781
 782         // Traverse down to level 0, adding anything we need
 783
 784         l = fStruct->topLevel;
 785         tn = fStruct->top;
 786         while (l > 0 && tn)
 787         {
 788                 x = (chunkId >> (/*dev->chunkGroupBits + */YAFFS_TNODES_LEVEL0_BITS + (l-1) * YAFFS_TNODES_INTERNAL_BITS)) &
 789                                YAFFS_TNODES_INTERNAL_MASK;
 790
 791                 //T((TSTR(" [%d:%d]"),l,i));
 792
 793             if(!tn->internal[x])
 794             {
 795                 //T((TSTR(" added")));
 796
 797                 tn->internal[x] = yaffs_GetTnode(dev);
 798             }
 799
 800             tn =        tn->internal[x];
 801                 l--;
 802
 803         }
 804
 805         //TSTR(TENDSTR)));
 806
 807         return tn;
 808 }
 809
 810
 811 static int yaffs_FindChunkInGroup(yaffs_Device *dev, int theChunk, yaffs_ExtendedTags *tags, int objectId, int chunkInInode)
 812 {
 813         int j;
 814
 815
 816         for(j = 0; theChunk && j < dev->chunkGroupSize; j++)
 817         {
 818                 if(yaffs_CheckChunkBit(dev,theChunk / dev->nChunksPerBlock,theChunk % dev->nChunksPerBlock))
 819                 {
 820                         yaffs_ReadChunkWithTagsFromNAND(dev,theChunk,NULL,tags);
 821                         if(yaffs_TagsMatch(tags,objectId,chunkInInode))
 822                         {
 823                                 // found it;
 824                                 return theChunk;
 825
 826                         }
 827                 }
 828                 theChunk++;
 829         }
 830         return -1;
 831 }
 832
 833 // DeleteWorker scans backwards through the tnode tree and deletes all the
 834 // chunks and tnodes in the file
 835 // Returns 1 if the tree was deleted. Returns 0 if it stopped early due to hitting the limit and the delete is incomplete.
 836
 837 static int yaffs_DeleteWorker(yaffs_Object *in, yaffs_Tnode *tn, __u32 level, int chunkOffset,int *limit)
 838 {
 839         int i;
 840         int chunkInInode;
 841         int theChunk;
 842         yaffs_ExtendedTags tags;
 843         int foundChunk;
 844         yaffs_Device *dev = in->myDev;
 845
 846         int allDone = 1;
 847
 848
 849         if(tn)
 850         {
 851                 if(level > 0)
 852                 {
 853
 854                         for(i = YAFFS_NTNODES_INTERNAL -1; allDone && i >= 0; i--)
 855                         {
 856                             if(tn->internal[i])
 857                         {
 858                                         if(limit && (*limit) < 0)
 859                                         {
 860                                                 allDone = 0;
 861                                         }
 862                                         else
 863                                         {
 864                                                 allDone = yaffs_DeleteWorker(in,tn->internal[i],level - 1,
 865                                                                                 (chunkOffset << YAFFS_TNODES_INTERNAL_BITS ) + i ,limit);
 866                                         }
 867                                         if(allDone)
 868                                         {
 869                                                 yaffs_FreeTnode(dev,tn->internal[i]);
 870                                         tn->internal[i] = NULL;
 871                                         }
 872                             }
 873
 874                         }
 875                         return (allDone) ? 1 : 0;
 876                 }
 877                 else if(level == 0)
 878                 {
 879                         int hitLimit = 0;
 880
 881                         for(i = YAFFS_NTNODES_LEVEL0 -1; i >= 0 && !hitLimit; i--)
 882                         {
 883                             if(tn->level0[i])
 884                         {
 885
 886                                         chunkInInode = (chunkOffset << YAFFS_TNODES_LEVEL0_BITS ) + i;
 887
 888                                         theChunk =  tn->level0[i] << dev->chunkGroupBits;
 889
 890                                         foundChunk = yaffs_FindChunkInGroup(dev,theChunk,&tags,in->objectId,chunkInInode);
 891
 892                                         if(foundChunk > 0)
 893                                         {
 894                                                 yaffs_DeleteChunk(dev,foundChunk,1,__LINE__);
 895                                                 in->nDataChunks--;
 896                                                 if(limit)
 897                                                 {
 898                                                         *limit = *limit-1;
 899                                                         if(*limit <= 0)
 900                                                         {
 901                                                                 hitLimit = 1;
 902                                                         }
 903                                                 }
 904
 905                                         }
 906
 907                                 tn->level0[i] = 0;
 908                             }
 909
 910                         }
 911                         return (i < 0) ? 1 : 0;
 912
 913
 914                 }
 915
 916         }
 917
 918         return 1;
 919
 920 }
 921
 922
 923 static void yaffs_SoftDeleteChunk(yaffs_Device *dev, int chunk)
 924 {
 925
 926         yaffs_BlockInfo *theBlock;
 927
 928         T(YAFFS_TRACE_DELETION,(TSTR("soft delete chunk %d" TENDSTR),chunk));
 929
 930         theBlock =      yaffs_GetBlockInfo(dev,  chunk/dev->nChunksPerBlock);
 931         if(theBlock)
 932         {
 933                 theBlock->softDeletions++;
 934                 dev->nFreeChunks++;
 935         }
 936 }
 937
 938 // SoftDeleteWorker scans backwards through the tnode tree and soft deletes all the chunks in the file.
 939 // All soft deleting does is increment the block's softdelete count and pulls the chunk out
 940 // of the tnode.
 941 // THus, essentially this is the same as DeleteWorker except that the chunks are soft deleted.
 942 //
 943 static int yaffs_SoftDeleteWorker(yaffs_Object *in, yaffs_Tnode *tn, __u32 level, int chunkOffset)
 944 {
 945         int i;
 946         int theChunk;
 947         int allDone = 1;
 948         yaffs_Device *dev = in->myDev;
 949
 950
 951         if(tn)
 952         {
 953                 if(level > 0)
 954                 {
 955
 956                         for(i = YAFFS_NTNODES_INTERNAL -1; allDone && i >= 0; i--)
 957                         {
 958                             if(tn->internal[i])
 959                         {
 960                                                 allDone = yaffs_SoftDeleteWorker(in,tn->internal[i],level - 1,
 961                                                                                 (chunkOffset << YAFFS_TNODES_INTERNAL_BITS ) + i);
 962                                         if(allDone)
 963                                         {
 964                                                 yaffs_FreeTnode(dev,tn->internal[i]);
 965                                         tn->internal[i] = NULL;
 966                                         }
 967                                         else
 968                                         {
 969                                                 //Hoosterman... how could this happen.
 970                                         }
 971                                 }
 972                         }
 973                         return (allDone) ? 1 : 0;
 974                 }
 975                 else if(level == 0)
 976                 {
 977
 978                         for(i = YAFFS_NTNODES_LEVEL0 -1; i >=0; i--)
 979                         {
 980                             if(tn->level0[i])
 981                         {
 982                                         // Note this does not find the real chunk, only the chunk group.
 983                                         // We make an assumption that a chunk group is niot larger than a block.
 984                                         theChunk =  (tn->level0[i] << dev->chunkGroupBits);
 985
 986                                         yaffs_SoftDeleteChunk(dev,theChunk);
 987                                 tn->level0[i] = 0;
 988                             }
 989
 990                         }
 991                         return 1;
 992
 993                 }
 994
 995         }
 996
 997         return 1;
 998
 999 }
1000
1001
1002
1003 static void yaffs_SoftDeleteFile(yaffs_Object *obj)
1004 {
1005         if(obj->deleted &&
1006            obj->variantType == YAFFS_OBJECT_TYPE_FILE &&
1007            !obj->softDeleted)
1008         {
1009                 if(obj->nDataChunks <= 0)
1010                 {
1011                                 // Empty file with no duplicate object headers, just delete it immediately
1012                                 yaffs_FreeTnode(obj->myDev,obj->variant.fileVariant.top);
1013                                 obj->variant.fileVariant.top = NULL;
1014                                 T(YAFFS_TRACE_TRACING,(TSTR("yaffs: Deleting empty file %d" TENDSTR),obj->objectId));
1015                                 yaffs_DoGenericObjectDeletion(obj);
1016                 }
1017                 else
1018                 {
1019                         yaffs_SoftDeleteWorker(obj, obj->variant.fileVariant.top, obj->variant.fileVariant.topLevel, 0);
1020                         obj->softDeleted = 1;
1021                 }
1022         }
1023 }
1024
1025
1026
1027
1028
1029 // Pruning removes any part of the file structure tree that is beyond the
1030 // bounds of the file (ie that does not point to chunks).
1031 //
1032 // A file should only get pruned when its size is reduced.
1033 //
1034 // Before pruning, the chunks must be pulled from the tree and the
1035 // level 0 tnode entries must be zeroed out.
1036 // Could also use this for file deletion, but that's probably better handled
1037 // by a special case.
1038
1039 // yaffs_PruneWorker should only be called by yaffs_PruneFileStructure()
1040
1041 static yaffs_Tnode *yaffs_PruneWorker(yaffs_Device *dev, yaffs_Tnode *tn, __u32 level, int del0)
1042 {
1043         int i;
1044         int hasData;
1045
1046         if(tn)
1047         {
1048                 hasData = 0;
1049
1050                 for(i = 0; i < YAFFS_NTNODES_INTERNAL; i++)
1051                 {
1052                     if(tn->internal[i] && level > 0)
1053                     {
1054                         tn->internal[i] = yaffs_PruneWorker(dev,tn->internal[i],level - 1, ( i == 0) ? del0 : 1);
1055                     }
1056
1057                     if(tn->internal[i])
1058                     {
1059                         hasData++;
1060                         }
1061                 }
1062
1063                 if(hasData == 0 && del0)
1064                 {
1065                         // Free and return NULL
1066
1067                         yaffs_FreeTnode(dev,tn);
1068                         tn = NULL;
1069                 }
1070
1071         }
1072
1073         return tn;
1074
1075 }
1076
1077 static int yaffs_PruneFileStructure(yaffs_Device *dev, yaffs_FileStructure *fStruct)
1078 {
1079         int i;
1080         int hasData;
1081         int done = 0;
1082         yaffs_Tnode *tn;
1083
1084         if(fStruct->topLevel > 0)
1085         {
1086                 fStruct->top = yaffs_PruneWorker(dev,fStruct->top, fStruct->topLevel,0);
1087
1088                 // Now we have a tree with all the non-zero branches NULL but the height
1089                 // is the same as it was.
1090                 // Let's see if we can trim internal tnodes to shorten the tree.
1091                 // We can do this if only the 0th element in the tnode is in use
1092                 // (ie all the non-zero are NULL)
1093
1094                 while(fStruct->topLevel && !done)
1095                 {
1096                         tn = fStruct->top;
1097
1098                         hasData = 0;
1099                         for(i = 1; i <YAFFS_NTNODES_INTERNAL; i++)
1100                         {
1101                                 if(tn->internal[i])
1102                         {
1103                                 hasData++;
1104                                 }
1105                         }
1106
1107                         if(!hasData)
1108                         {
1109                                 fStruct->top = tn->internal[0];
1110                                 fStruct->topLevel--;
1111                                 yaffs_FreeTnode(dev,tn);
1112                         }
1113                         else
1114                         {
1115                                 done = 1;
1116                         }
1117                 }
1118         }
1119
1120         return YAFFS_OK;
1121 }
1122
1123
1124
1125
1126
1127 /////////////////////// End of File Structure functions. /////////////////
1128
1129 // yaffs_CreateFreeObjects creates a bunch more objects and
1130 // adds them to the object free list.
1131 static int yaffs_CreateFreeObjects(yaffs_Device *dev, int nObjects)
1132 {
1133     int i;
1134     yaffs_Object *newObjects;
1135     yaffs_ObjectList *list;
1136
1137     if(nObjects < 1) return YAFFS_OK;
1138
1139         // make these things
1140
1141     newObjects = YMALLOC(nObjects * sizeof(yaffs_Object));
1142
1143     if (!newObjects)
1144     {
1145                 T(YAFFS_TRACE_ALLOCATE,(TSTR("yaffs: Could not allocate more objects" TENDSTR)));
1146                 return YAFFS_FAIL;
1147     }
1148
1149     // Hook them into the free list
1150     for(i = 0; i < nObjects - 1; i++)
1151     {
1152         newObjects[i].siblings.next = (struct list_head *)(&newObjects[i+1]);
1153     }
1154
1155         newObjects[nObjects - 1].siblings.next = (void *)dev->freeObjects;
1156         dev->freeObjects = newObjects;
1157         dev->nFreeObjects+= nObjects;
1158         dev->nObjectsCreated+= nObjects;
1159
1160         // Now add this bunch of Objects to a list for freeing up.
1161
1162         list = YMALLOC(sizeof(yaffs_ObjectList));
1163         if(!list)
1164         {
1165                 T(YAFFS_TRACE_ALLOCATE,(TSTR("Could not add objects to management list" TENDSTR)));
1166         }
1167         else
1168         {
1169                 list->objects = newObjects;
1170                 list->next = dev->allocatedObjectList;
1171                 dev->allocatedObjectList = list;
1172         }
1173
1174
1175
1176         return YAFFS_OK;
1177 }
1178
1179
1180 // AllocateEmptyObject gets us a clean Object. Tries to make allocate more if we run out
1181 static yaffs_Object *yaffs_AllocateEmptyObject(yaffs_Device *dev)
1182 {
1183         yaffs_Object *tn = NULL;
1184
1185         // If there are none left make more
1186         if(!dev->freeObjects)
1187         {
1188                 yaffs_CreateFreeObjects(dev,YAFFS_ALLOCATION_NOBJECTS);
1189         }
1190
1191         if(dev->freeObjects)
1192         {
1193                 tn = dev->freeObjects;
1194                 dev->freeObjects = (yaffs_Object *)(dev->freeObjects->siblings.next);
1195                 dev->nFreeObjects--;
1196
1197                 // Now sweeten it up...
1198
1199                 memset(tn,0,sizeof(yaffs_Object));
1200                 tn->myDev = dev;
1201                 tn->chunkId = -1;
1202                 tn->variantType = YAFFS_OBJECT_TYPE_UNKNOWN;
1203                 INIT_LIST_HEAD(&(tn->hardLinks));
1204                 INIT_LIST_HEAD(&(tn->hashLink));
1205                 INIT_LIST_HEAD(&tn->siblings);
1206
1207                 // Add it to the lost and found directory.
1208                 // NB Can't put root or lostNFound in lostNFound so
1209                 // check if lostNFound exists first
1210                 if(dev->lostNFoundDir)
1211                 {
1212                         yaffs_AddObjectToDirectory(dev->lostNFoundDir,tn);
1213                 }
1214         }
1215
1216
1217         return tn;
1218 }
1219
1220 static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device *dev,int number,__u32 mode)
1221 {
1222
1223         yaffs_Object *obj = yaffs_CreateNewObject(dev,number,YAFFS_OBJECT_TYPE_DIRECTORY);
1224         if(obj)
1225         {
1226                 obj->fake = 1;                  // it is fake so it has no NAND presence...
1227                 obj->renameAllowed= 0;  // ... and we're not allowed to rename it...
1228                 obj->unlinkAllowed= 0;  // ... or unlink it
1229                 obj->deleted = 0;
1230                 obj->unlinked = 0;
1231                 obj->yst_mode = mode;
1232                 obj->myDev = dev;
1233                 obj->chunkId = 0; // Not a valid chunk.
1234         }
1235
1236         return obj;
1237
1238 }
1239
1240
1241 static void yaffs_UnhashObject(yaffs_Object *tn)
1242 {
1243         int bucket;
1244         yaffs_Device *dev = tn->myDev;
1245
1246
1247         // If it is still linked into the bucket list, free from the list
1248         if(!list_empty(&tn->hashLink))
1249         {
1250                 list_del_init(&tn->hashLink);
1251                 bucket =  yaffs_HashFunction(tn->objectId);
1252                 dev->objectBucket[bucket].count--;
1253         }
1254
1255 }
1256
1257
1258 // FreeObject frees up a Object and puts it back on the free list
1259 static void yaffs_FreeObject(yaffs_Object *tn)
1260 {
1261
1262         yaffs_Device *dev = tn->myDev;
1263
1264 #ifdef  __KERNEL__
1265         if(tn->myInode)
1266         {
1267                 // We're still hooked up to a cached inode.
1268                 // Don't delete now, but mark for later deletion
1269                 tn->deferedFree = 1;
1270                 return;
1271         }
1272 #endif
1273
1274         yaffs_UnhashObject(tn);
1275
1276         // Link into the free list.
1277         tn->siblings.next = (struct list_head *)(dev->freeObjects);
1278         dev->freeObjects = tn;
1279         dev->nFreeObjects++;
1280 }
1281
1282
1283
1284 #ifdef __KERNEL__
1285
1286 void yaffs_HandleDeferedFree(yaffs_Object *obj)
1287 {
1288         if(obj->deferedFree)
1289         {
1290            yaffs_FreeObject(obj);
1291         }
1292 }
1293
1294 #endif
1295
1296
1297
1298 static void yaffs_DeinitialiseObjects(yaffs_Device *dev)
1299 {
1300         // Free the list of allocated Objects
1301
1302         yaffs_ObjectList *tmp;
1303
1304         while( dev->allocatedObjectList)
1305         {
1306                 tmp =  dev->allocatedObjectList->next;
1307                 YFREE(dev->allocatedObjectList->objects);
1308                 YFREE(dev->allocatedObjectList);
1309
1310                 dev->allocatedObjectList =  tmp;
1311         }
1312
1313         dev->freeObjects = NULL;
1314         dev->nFreeObjects = 0;
1315 }
1316
1317 static void yaffs_InitialiseObjects(yaffs_Device *dev)
1318 {
1319         int i;
1320
1321         dev->allocatedObjectList = NULL;
1322         dev->freeObjects = NULL;
1323         dev->nFreeObjects = 0;
1324
1325         for(i = 0; i < YAFFS_NOBJECT_BUCKETS; i++)
1326         {
1327                 INIT_LIST_HEAD(&dev->objectBucket[i].list);
1328                 dev->objectBucket[i].count = 0;
1329         }
1330
1331 }
1332
1333
1334
1335
1336
1337
1338 static int yaffs_FindNiceObjectBucket(yaffs_Device *dev)
1339 {
1340         static int x = 0;
1341         int i;
1342         int l = 999;
1343         int lowest = 999999;
1344
1345
1346         // First let's see if we can find one that's empty.
1347
1348         for(i = 0; i < 10 && lowest > 0; i++)
1349          {
1350                 x++;
1351                 x %=  YAFFS_NOBJECT_BUCKETS;
1352                 if(dev->objectBucket[x].count < lowest)
1353                 {
1354                         lowest = dev->objectBucket[x].count;
1355                         l = x;
1356                 }
1357
1358         }
1359
1360         // If we didn't find an empty list, then try
1361         // looking a bit further for a short one
1362
1363         for(i = 0; i < 10 && lowest > 3; i++)
1364          {
1365                 x++;
1366                 x %=  YAFFS_NOBJECT_BUCKETS;
1367                 if(dev->objectBucket[x].count < lowest)
1368                 {
1369                         lowest = dev->objectBucket[x].count;
1370                         l = x;
1371                 }
1372
1373         }
1374
1375         return l;
1376 }
1377
1378 static int yaffs_CreateNewObjectNumber(yaffs_Device *dev)
1379 {
1380         int bucket = yaffs_FindNiceObjectBucket(dev);
1381
1382         // Now find an object value that has not already been taken
1383         // by scanning the list.
1384
1385         int found = 0;
1386         struct list_head *i;
1387
1388         __u32 n = (__u32)bucket;
1389
1390         //yaffs_CheckObjectHashSanity();
1391
1392         while(!found)
1393         {
1394                 found = 1;
1395                 n +=  YAFFS_NOBJECT_BUCKETS;
1396                 if(1 ||dev->objectBucket[bucket].count > 0)
1397                 {
1398                         list_for_each(i,&dev->objectBucket[bucket].list)
1399                         {
1400                                 // If there is already one in the list
1401                                 if(i && list_entry(i, yaffs_Object,hashLink)->objectId == n)
1402                                 {
1403                                         found = 0;
1404                                 }
1405                         }
1406                 }
1407         }
1408
1409         //T(("bucket %d count %d inode %d\n",bucket,yaffs_objectBucket[bucket].count,n);
1410
1411         return n;
1412 }
1413
1414 static void yaffs_HashObject(yaffs_Object *in)
1415 {
1416         int bucket = yaffs_HashFunction(in->objectId);
1417         yaffs_Device *dev = in->myDev;
1418
1419         if(!list_empty(&in->hashLink))
1420         {
1421                 //YINFO("!!!");
1422         }
1423
1424
1425         list_add(&in->hashLink,&dev->objectBucket[bucket].list);
1426         dev->objectBucket[bucket].count++;
1427
1428 }
1429
1430 yaffs_Object *yaffs_FindObjectByNumber(yaffs_Device *dev,__u32 number)
1431 {
1432         int bucket = yaffs_HashFunction(number);
1433         struct list_head *i;
1434         yaffs_Object *in;
1435
1436         list_for_each(i,&dev->objectBucket[bucket].list)
1437         {
1438                 // Look if it is in the list
1439                 if(i)
1440                 {
1441                         in = list_entry(i, yaffs_Object,hashLink);
1442                         if(in->objectId == number)
1443                         {
1444 #ifdef __KERNEL__
1445                                 // Don't tell the VFS about this one if it is defered free
1446                                 if(in->deferedFree)
1447                                   return NULL;
1448 #endif
1449
1450                                 return in;
1451                         }
1452                 }
1453         }
1454
1455         return NULL;
1456 }
1457
1458
1459
1460 yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type)
1461 {
1462
1463         yaffs_Object *theObject;
1464
1465         if(number < 0)
1466         {
1467                 number = yaffs_CreateNewObjectNumber(dev);
1468         }
1469
1470         theObject = yaffs_AllocateEmptyObject(dev);
1471
1472         if(theObject)
1473         {
1474                 theObject->fake = 0;
1475                 theObject->renameAllowed = 1;
1476                 theObject->unlinkAllowed = 1;
1477                 theObject->objectId = number;
1478                 yaffs_HashObject(theObject);
1479                 theObject->variantType = type;
1480 #ifdef CONFIG_YAFFS_WINCE
1481                 yfsd_WinFileTimeNow(theObject->win_atime);
1482                 theObject->win_ctime[0] = theObject->win_mtime[0] = theObject->win_atime[0];
1483                 theObject->win_ctime[1] = theObject->win_mtime[1] = theObject->win_atime[1];
1484
1485 #else
1486
1487                 theObject->yst_atime = theObject->yst_mtime = theObject->yst_ctime = Y_CURRENT_TIME;
1488 #endif
1489                 switch(type)
1490                 {
1491                         case YAFFS_OBJECT_TYPE_FILE:
1492                                 theObject->variant.fileVariant.fileSize = 0;
1493                                 theObject->variant.fileVariant.scannedFileSize = 0;
1494                                 theObject->variant.fileVariant.shrinkSize = 0xFFFFFFFF; // max __u32
1495                                 theObject->variant.fileVariant.topLevel = 0;
1496                                 theObject->variant.fileVariant.top  = yaffs_GetTnode(dev);
1497                                 break;
1498                         case YAFFS_OBJECT_TYPE_DIRECTORY:
1499                                 INIT_LIST_HEAD(&theObject->variant.directoryVariant.children);
1500                                 break;
1501                         case YAFFS_OBJECT_TYPE_SYMLINK:
1502                                 // No action required
1503                                 break;
1504                         case YAFFS_OBJECT_TYPE_HARDLINK:
1505                                 // No action required
1506                                 break;
1507                         case YAFFS_OBJECT_TYPE_SPECIAL:
1508                                 // No action required
1509                                 break;
1510                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1511                                 // todo this should not happen
1512                                 break;
1513                 }
1514         }
1515
1516         return theObject;
1517 }
1518
1519 static yaffs_Object *yaffs_FindOrCreateObjectByNumber(yaffs_Device *dev, int number,yaffs_ObjectType type)
1520 {
1521         yaffs_Object *theObject = NULL;
1522
1523         if(number > 0)
1524         {
1525                 theObject = yaffs_FindObjectByNumber(dev,number);
1526         }
1527
1528         if(!theObject)
1529         {
1530                 theObject = yaffs_CreateNewObject(dev,number,type);
1531         }
1532
1533         return theObject;
1534
1535 }
1536
1537 static YCHAR *yaffs_CloneString(const YCHAR *str)
1538 {
1539         YCHAR *newStr = NULL;
1540
1541         if(str && *str)
1542         {
1543                 newStr = YMALLOC((yaffs_strlen(str) + 1) * sizeof(YCHAR));
1544                 yaffs_strcpy(newStr,str);
1545         }
1546
1547         return newStr;
1548
1549 }
1550
1551 //
1552 // Mknod (create) a new object.
1553 // equivalentObject only has meaning for a hard link;
1554 // aliasString only has meaning for a sumlink.
1555 // rdev only has meaning for devices (a subset of special objects)
1556 static yaffs_Object *yaffs_MknodObject( yaffs_ObjectType type,
1557                                                                  yaffs_Object *parent,
1558                                                                  const YCHAR *name,
1559                                                                  __u32 mode,
1560                                                                  __u32 uid,
1561                                                                  __u32 gid,
1562                                                                  yaffs_Object *equivalentObject,
1563                                                                  const YCHAR *aliasString,
1564                                                                  __u32 rdev)
1565 {
1566         yaffs_Object *in;
1567
1568         yaffs_Device *dev = parent->myDev;
1569
1570         // Check if the entry exists. If it does then fail the call since we don't want a dup.
1571         if(yaffs_FindObjectByName(parent,name))
1572         {
1573                 return NULL;
1574         }
1575
1576         in = yaffs_CreateNewObject(dev,-1,type);
1577
1578         if(in)
1579         {
1580                 in->chunkId = -1;
1581                 in->valid = 1;
1582                 in->variantType = type;
1583
1584                 in->yst_mode  = mode;
1585
1586 #ifdef CONFIG_YAFFS_WINCE
1587                 yfsd_WinFileTimeNow(in->win_atime);
1588                 in->win_ctime[0] = in->win_mtime[0] = in->win_atime[0];
1589                 in->win_ctime[1] = in->win_mtime[1] = in->win_atime[1];
1590
1591 #else
1592                 in->yst_atime = in->yst_mtime = in->yst_ctime = Y_CURRENT_TIME;
1593
1594                 in->yst_rdev  = rdev;
1595                 in->yst_uid   = uid;
1596                 in->yst_gid   = gid;
1597 #endif
1598                 in->nDataChunks = 0;
1599
1600                 yaffs_SetObjectName(in,name);
1601                 in->dirty = 1;
1602
1603                 yaffs_AddObjectToDirectory(parent,in);
1604
1605                 in->myDev = parent->myDev;
1606
1607
1608                 switch(type)
1609                 {
1610                         case YAFFS_OBJECT_TYPE_SYMLINK:
1611                                 in->variant.symLinkVariant.alias = yaffs_CloneString(aliasString);
1612                                 break;
1613                         case YAFFS_OBJECT_TYPE_HARDLINK:
1614                                 in->variant.hardLinkVariant.equivalentObject = equivalentObject;
1615                                 in->variant.hardLinkVariant.equivalentObjectId = equivalentObject->objectId;
1616                                 list_add(&in->hardLinks,&equivalentObject->hardLinks);
1617                                 break;
1618                         case YAFFS_OBJECT_TYPE_FILE: // do nothing
1619                         case YAFFS_OBJECT_TYPE_DIRECTORY: // do nothing
1620                         case YAFFS_OBJECT_TYPE_SPECIAL: // do nothing
1621                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1622                                 break;
1623                 }
1624
1625                 if(/*yaffs_GetNumberOfFreeChunks(dev) <= 0 || */
1626                    yaffs_UpdateObjectHeader(in,name,0,0,0) < 0)
1627                 {
1628                         // Could not create the object header, fail the creation
1629                         yaffs_DestroyObject(in);
1630                         in = NULL;
1631                 }
1632
1633         }
1634
1635         return in;
1636 }
1637
1638 yaffs_Object *yaffs_MknodFile(yaffs_Object *parent,const YCHAR *name, __u32 mode, __u32 uid, __u32 gid)
1639 {
1640         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_FILE,parent,name,mode,uid,gid,NULL,NULL,0);
1641 }
1642
1643 yaffs_Object *yaffs_MknodDirectory(yaffs_Object *parent,const YCHAR *name, __u32 mode, __u32 uid, __u32 gid)
1644 {
1645         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_DIRECTORY,parent,name,mode,uid,gid,NULL,NULL,0);
1646 }
1647
1648 yaffs_Object *yaffs_MknodSpecial(yaffs_Object *parent,const YCHAR *name, __u32 mode, __u32 uid, __u32 gid, __u32 rdev)
1649 {
1650         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SPECIAL,parent,name,mode,uid,gid,NULL,NULL,rdev);
1651 }
1652
1653 yaffs_Object *yaffs_MknodSymLink(yaffs_Object *parent,const YCHAR *name, __u32 mode, __u32 uid, __u32 gid,const YCHAR *alias)
1654 {
1655         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SYMLINK,parent,name,mode,uid,gid,NULL,alias,0);
1656 }
1657
1658 // NB yaffs_Link returns the object id of the equivalent object.
1659 yaffs_Object *yaffs_Link(yaffs_Object *parent, const YCHAR *name, yaffs_Object *equivalentObject)
1660 {
1661         // Get the real object in case we were fed a hard link as an equivalent object
1662         equivalentObject = yaffs_GetEquivalentObject(equivalentObject);
1663
1664         if(yaffs_MknodObject(YAFFS_OBJECT_TYPE_HARDLINK,parent,name,0,0,0,equivalentObject,NULL,0))
1665         {
1666                 return equivalentObject;
1667         }
1668         else
1669         {
1670                 return NULL;
1671         }
1672
1673 }
1674
1675
1676 static int yaffs_ChangeObjectName(yaffs_Object *obj, yaffs_Object *newDir, const YCHAR *newName,int force,int shadows)
1677 {
1678         int unlinkOp;
1679         int deleteOp;
1680
1681         yaffs_Object * existingTarget;
1682
1683         if(newDir == NULL)
1684         {
1685                 newDir = obj->parent; // use the old directory
1686         }
1687
1688         if(newDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
1689         {
1690                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragendy: yaffs_ChangeObjectName: newDir is not a directory"TENDSTR)));
1691                 YBUG();
1692         }
1693
1694         // TODO: Do we need this different handling for YAFFS2 and YAFFS1??
1695         if(obj->myDev->isYaffs2)
1696         {
1697                 unlinkOp = (newDir == obj->myDev->unlinkedDir);
1698         }
1699         else
1700         {
1701                 unlinkOp = (newDir == obj->myDev->unlinkedDir && obj->variantType == YAFFS_OBJECT_TYPE_FILE);
1702         }
1703
1704         deleteOp = (newDir == obj->myDev->deletedDir);
1705
1706         existingTarget = yaffs_FindObjectByName(newDir,newName);
1707
1708         // If the object is a file going into the unlinked directory, then it is OK to just stuff it in since
1709         // duplicate names are allowed.
1710         // Otherwise only proceed if the new name does not exist and if we're putting it into a directory.
1711         if( (unlinkOp||
1712                  deleteOp ||
1713                  force ||
1714                  (shadows > 0) ||
1715                  !existingTarget)  &&
1716              newDir->variantType == YAFFS_OBJECT_TYPE_DIRECTORY)
1717         {
1718                 yaffs_SetObjectName(obj,newName);
1719                 obj->dirty = 1;
1720
1721                 yaffs_AddObjectToDirectory(newDir,obj);
1722
1723                 if(unlinkOp) obj->unlinked = 1;
1724
1725                 // If it is a deletion then we mark it as a shrink for gc purposes.
1726                 if(yaffs_UpdateObjectHeader(obj,newName,0,deleteOp,shadows) >= 0)
1727                 {
1728                         return YAFFS_OK;
1729                 }
1730         }
1731
1732         return YAFFS_FAIL;
1733 }
1734
1735
1736
1737 int yaffs_RenameObject(yaffs_Object *oldDir, const YCHAR *oldName, yaffs_Object *newDir, const YCHAR *newName)
1738 {
1739         yaffs_Object *obj;
1740         yaffs_Object *existingTarget;
1741         int force = 0;
1742
1743 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
1744         // Special case for case insemsitive systems (eg. WinCE).
1745         // While look-up is case insensitive, the name isn't.
1746         // THerefore we might want to change x.txt to X.txt
1747         if(oldDir == newDir && yaffs_strcmp(oldName,newName) == 0)
1748         {
1749                 force = 1;
1750         }
1751 #endif
1752
1753         obj = yaffs_FindObjectByName(oldDir,oldName);
1754
1755         if(obj && obj->renameAllowed)
1756         {
1757
1758                 // Now do the handling for an existing target, if there is one
1759
1760                 existingTarget = yaffs_FindObjectByName(newDir,newName);
1761                 if(existingTarget &&
1762                    existingTarget->variantType == YAFFS_OBJECT_TYPE_DIRECTORY &&
1763                    !list_empty(&existingTarget->variant.directoryVariant.children))
1764                  {
1765                         // There is a target that is a non-empty directory, so we have to fail
1766                         return YAFFS_FAIL; // EEXIST or ENOTEMPTY
1767                  }
1768                  else if(existingTarget &&
1769                          existingTarget != obj)
1770                  {
1771                         // Nuke the target first, using shadowing,
1772                         // but only if it isn't the same object
1773                          yaffs_ChangeObjectName(obj,newDir,newName,force,existingTarget->objectId);
1774                          yaffs_Unlink(newDir,newName);
1775                  }
1776
1777
1778                 return yaffs_ChangeObjectName(obj,newDir,newName,force,0);
1779         }
1780         return YAFFS_FAIL;
1781 }
1782
1783
1784
1785 /////////////////////////// Block Management and Page Allocation ///////////////////
1786
1787
1788 static int yaffs_InitialiseBlocks(yaffs_Device *dev,int nBlocks)
1789 {
1790         dev->allocationBlock = -1; // force it to get a new one
1791         //Todo we're assuming the malloc will pass.
1792         dev->blockInfo = YMALLOC(nBlocks * sizeof(yaffs_BlockInfo));
1793         // Set up dynamic blockinfo stuff.
1794         dev->chunkBitmapStride = (dev->nChunksPerBlock+7)/8;
1795         dev->chunkBits = YMALLOC(dev->chunkBitmapStride * nBlocks);
1796         if(dev->blockInfo && dev->chunkBits)
1797         {
1798                 memset(dev->blockInfo,0,nBlocks * sizeof(yaffs_BlockInfo));
1799                 memset(dev->chunkBits,0,dev->chunkBitmapStride * nBlocks);
1800                 return YAFFS_OK;
1801         }
1802
1803         return YAFFS_FAIL;
1804
1805 }
1806
1807 static void yaffs_DeinitialiseBlocks(yaffs_Device *dev)
1808 {
1809         YFREE(dev->blockInfo);
1810         dev->blockInfo = NULL;
1811         YFREE(dev->chunkBits);
1812         dev->chunkBits = NULL;
1813 }
1814
1815
1816 static int yaffs_BlockNotDisqualifiedFromGC(yaffs_Device *dev, yaffs_BlockInfo *bi)
1817 {
1818         int i;
1819         __u32 seq;
1820         yaffs_BlockInfo *b;
1821
1822         if(!dev->isYaffs2) return 1; // disqualification only applies to yaffs2.
1823
1824         if(!bi->hasShrinkHeader) return 1; // can gc
1825
1826
1827         // Find the oldest dirty sequence number if we don't know it and save it
1828         // so we don't have to keep recomputing it.
1829         if(!dev->oldestDirtySequence)
1830         {
1831                 seq = dev->sequenceNumber;
1832
1833                 for(i = dev->internalStartBlock; i <= dev->internalEndBlock; i++)
1834                 {
1835                         b = yaffs_GetBlockInfo(dev,i);
1836                         if(b->blockState == YAFFS_BLOCK_STATE_FULL &&
1837                         (b->pagesInUse - b->softDeletions )< dev->nChunksPerBlock &&
1838                         b->sequenceNumber < seq)
1839                         {
1840                                 seq = b->sequenceNumber;
1841                         }
1842                 }
1843                 dev->oldestDirtySequence = seq;
1844         }
1845
1846
1847         // Can't do gc of this block if there are any blocks older than this one that have
1848         // discarded pages.
1849         return (bi->sequenceNumber <= dev->oldestDirtySequence);
1850
1851
1852         return 1;
1853
1854 }
1855
1856 // FindDiretiestBlock is used to select the dirtiest block (or close enough)
1857 // for garbage collection.
1858 //
1859
1860
1861
1862 static int yaffs_FindBlockForGarbageCollection(yaffs_Device *dev,int aggressive)
1863 {
1864
1865         int b = dev->currentDirtyChecker;
1866
1867         int i;
1868         int iterations;
1869         int dirtiest = -1;
1870         int pagesInUse;
1871         yaffs_BlockInfo *bi;
1872         static int  nonAggressiveSkip = 0;
1873
1874         // If we're doing aggressive GC then we are happy to take a less-dirty block, and
1875         // search harder.
1876         // else (we're doing a leasurely gc), then we only bother to do this if the
1877         // block has only a few pages in use.
1878
1879
1880         nonAggressiveSkip--;
1881
1882         if(!aggressive &&(nonAggressiveSkip > 0))
1883         {
1884                 return -1;
1885         }
1886
1887         pagesInUse = (aggressive)? dev->nChunksPerBlock : YAFFS_PASSIVE_GC_CHUNKS + 1;
1888
1889         if(aggressive)
1890         {
1891                 iterations = dev->internalEndBlock - dev->internalStartBlock + 1;
1892         }
1893         else
1894         {
1895                 iterations = dev->internalEndBlock - dev->internalStartBlock + 1;
1896                 iterations = iterations / 16;
1897                 if(iterations > 200)
1898                 {
1899                         iterations = 200;
1900                 }
1901         }
1902
1903         for(i = 0; i <= iterations && pagesInUse > 0 ; i++)
1904         {
1905                 b++;
1906                 if ( b < dev->internalStartBlock || b > dev->internalEndBlock)
1907                 {
1908                         b =  dev->internalStartBlock;
1909                 }
1910
1911                 if(b < dev->internalStartBlock || b > dev->internalEndBlock)
1912                 {
1913                         T(YAFFS_TRACE_ERROR,(TSTR("**>> Block %d is not valid" TENDSTR),b));
1914                         YBUG();
1915                 }
1916
1917                 bi = yaffs_GetBlockInfo(dev,b);
1918
1919                 if(bi->blockState == YAFFS_BLOCK_STATE_FULL &&
1920                    (bi->pagesInUse - bi->softDeletions )< pagesInUse &&
1921                    yaffs_BlockNotDisqualifiedFromGC(dev,bi))
1922                 {
1923                         dirtiest = b;
1924                         pagesInUse = (bi->pagesInUse - bi->softDeletions);
1925                 }
1926         }
1927
1928         dev->currentDirtyChecker = b;
1929
1930         if(dirtiest > 0)
1931         {
1932                 T(YAFFS_TRACE_GC,(TSTR("GC Selected block %d with %d free" TENDSTR),dirtiest,dev->nChunksPerBlock - pagesInUse));
1933         }
1934
1935         dev->oldestDirtySequence = 0; // clear this
1936
1937         if(dirtiest > 0)
1938         {
1939                 nonAggressiveSkip = 4;
1940         }
1941
1942         return dirtiest;
1943 }
1944
1945
1946 static void yaffs_BlockBecameDirty(yaffs_Device *dev,int blockNo)
1947 {
1948         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,blockNo);
1949
1950         int erasedOk = 0;
1951
1952         // If the block is still healthy erase it and mark as clean.
1953         // If the block has had a data failure, then retire it.
1954         bi->blockState = YAFFS_BLOCK_STATE_DIRTY;
1955
1956         if(!bi->needsRetiring)
1957         {
1958                 erasedOk = yaffs_EraseBlockInNAND(dev,blockNo);
1959                 if(!erasedOk)
1960                 {
1961                         dev->nErasureFailures++;
1962                         T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,(TSTR("**>> Erasure failed %d" TENDSTR),blockNo));
1963                 }
1964         }
1965
1966         if(erasedOk && (yaffs_traceMask & YAFFS_TRACE_ERASE))
1967         {
1968                         int i;
1969                         for(i = 0; i < dev->nChunksPerBlock; i++)
1970                         {
1971                                         if(!yaffs_CheckChunkErased(dev,blockNo * dev->nChunksPerBlock + i))
1972                                         {
1973                                                 T(YAFFS_TRACE_ERROR,(TSTR(">>Block %d erasure supposedly OK, but chunk %d not erased" TENDSTR),blockNo,i));
1974                                         }
1975                         }
1976         }
1977
1978         if( erasedOk )
1979         {
1980                 // Clean it up...
1981                 bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
1982                 dev->nErasedBlocks++;
1983                 bi->pagesInUse = 0;
1984                 bi->softDeletions = 0;
1985                 bi->hasShrinkHeader=0;
1986                 yaffs_ClearChunkBits(dev,blockNo);
1987
1988                 T(YAFFS_TRACE_ERASE,(TSTR("Erased block %d" TENDSTR),blockNo));
1989         }
1990         else
1991         {
1992                 dev->nFreeChunks -= dev->nChunksPerBlock; // We lost a block of free space
1993
1994                 yaffs_RetireBlock(dev,blockNo);
1995                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,(TSTR("**>> Block %d retired" TENDSTR),blockNo));
1996         }
1997 }
1998
1999
2000 static int yaffs_FindBlockForAllocation(yaffs_Device *dev)
2001 {
2002         int i;
2003
2004         yaffs_BlockInfo *bi;
2005
2006         if(dev->nErasedBlocks < 1)
2007         {
2008                 // Hoosterman we've got a problem.
2009                 // Can't get space to gc
2010                 T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: no more eraased blocks" TENDSTR)));
2011
2012                 return -1;
2013         }
2014
2015         // Find an empty block.
2016
2017         for(i = dev->internalStartBlock; i <= dev->internalEndBlock; i++)
2018         {
2019                 dev->allocationBlockFinder++;
2020                 if(dev->allocationBlockFinder < dev->internalStartBlock || dev->allocationBlockFinder> dev->internalEndBlock)
2021                 {
2022                         dev->allocationBlockFinder = dev->internalStartBlock;
2023                 }
2024
2025                 bi = yaffs_GetBlockInfo(dev,dev->allocationBlockFinder);
2026
2027                 if(bi->blockState == YAFFS_BLOCK_STATE_EMPTY)
2028                 {
2029                         bi->blockState = YAFFS_BLOCK_STATE_ALLOCATING;
2030                         dev->sequenceNumber++;
2031                         bi->sequenceNumber = dev->sequenceNumber;
2032                         dev->nErasedBlocks--;
2033                         T(YAFFS_TRACE_ALLOCATE,(TSTR("Allocated block %d, seq  %d, %d left" TENDSTR),dev->allocationBlockFinder,dev->sequenceNumber, dev->nErasedBlocks));
2034                         return dev->allocationBlockFinder;
2035                 }
2036         }
2037
2038
2039         T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs tragedy: no more eraased blocks, but there should have been %d" TENDSTR),dev->nErasedBlocks));
2040
2041
2042
2043
2044
2045         return -1;
2046 }
2047
2048
2049 // To determine if we have enough space we just look at the
2050 // number of erased blocks.
2051
2052 static int yaffs_CheckSpaceForAllocation(yaffs_Device *dev)
2053 {
2054         int reservedChunks = (dev->nReservedBlocks * dev->nChunksPerBlock);
2055         return (dev->nFreeChunks > reservedChunks);
2056 }
2057
2058
2059 static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve)
2060 {
2061         int retVal;
2062         yaffs_BlockInfo *bi;
2063
2064         if(dev->allocationBlock < 0)
2065         {
2066                 // Get next block to allocate off
2067                 dev->allocationBlock = yaffs_FindBlockForAllocation(dev);
2068                 dev->allocationPage = 0;
2069         }
2070
2071         if(!useReserve &&  !yaffs_CheckSpaceForAllocation(dev))
2072         {
2073                 // Not enough space to allocate unless we're allowed to use the reserve.
2074                 return -1;
2075         }
2076
2077         if(dev->nErasedBlocks < dev->nReservedBlocks && dev->allocationPage == 0)
2078         {
2079                 T(YAFFS_TRACE_ALLOCATE,(TSTR("Allocating reserve" TENDSTR)));
2080         }
2081
2082
2083         // Next page please....
2084         if(dev->allocationBlock >= 0)
2085         {
2086                 bi = yaffs_GetBlockInfo(dev,dev->allocationBlock);
2087
2088                 retVal = (dev->allocationBlock * dev->nChunksPerBlock) +
2089                                   dev->allocationPage;
2090                 bi->pagesInUse++;
2091                 yaffs_SetChunkBit(dev,dev->allocationBlock,dev->allocationPage);
2092
2093                 dev->allocationPage++;
2094
2095                 dev->nFreeChunks--;
2096
2097                 // If the block is full set the state to full
2098                 if(dev->allocationPage >= dev->nChunksPerBlock)
2099                 {
2100                         bi->blockState = YAFFS_BLOCK_STATE_FULL;
2101                         dev->allocationBlock = -1;
2102                 }
2103
2104
2105                 return retVal;
2106
2107         }
2108         T(YAFFS_TRACE_ERROR,(TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));
2109
2110         return -1;
2111 }
2112
2113
2114
2115
2116 static int yaffs_GetErasedChunks(yaffs_Device *dev)
2117 {
2118                 int n;
2119
2120                 n = dev->nErasedBlocks * dev->nChunksPerBlock;
2121
2122                 if(dev->allocationBlock> 0)
2123                 {
2124                         n += (dev->nChunksPerBlock - dev->allocationPage);
2125                 }
2126
2127                 return n;
2128
2129 }
2130
2131 static int  yaffs_GarbageCollectBlock(yaffs_Device *dev,int block)
2132 {
2133         int oldChunk;
2134         int newChunk;
2135         int chunkInBlock;
2136         int markNAND;
2137         int retVal = YAFFS_OK;
2138         int cleanups = 0;
2139         int i;
2140
2141         int chunksBefore = yaffs_GetErasedChunks(dev);
2142         int chunksAfter;
2143
2144         yaffs_ExtendedTags  tags;
2145
2146         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,block);
2147
2148         yaffs_Object *object;
2149
2150         bi->blockState = YAFFS_BLOCK_STATE_COLLECTING;
2151
2152         T(YAFFS_TRACE_TRACING,(TSTR("Collecting block %d, in use %d, shrink %d, " TENDSTR),block,bi->pagesInUse,bi->hasShrinkHeader));
2153         //T(("Collecting block %d n %d bits %x\n",block, bi->pagesInUse, bi->pageBits));
2154
2155         //yaffs_VerifyFreeChunks(dev);
2156
2157         bi->hasShrinkHeader = 0; // clear the flag so that the block can erase
2158
2159         dev->nFreeChunks -= bi->softDeletions;  // Take off the number of soft deleted entries because
2160                                                 // they're going to get really deleted during GC.
2161
2162         dev->isDoingGC = 1;
2163
2164         if(!yaffs_StillSomeChunkBits(dev,block))
2165         {
2166                 T(YAFFS_TRACE_TRACING,(TSTR("Collecting block %d that has no chunks in use" TENDSTR),block));
2167                 yaffs_BlockBecameDirty(dev,block);
2168         }
2169         else
2170         {
2171
2172         __u8  *buffer = yaffs_GetTempBuffer(dev,__LINE__);
2173
2174         for(chunkInBlock = 0,oldChunk = block * dev->nChunksPerBlock;
2175             chunkInBlock < dev->nChunksPerBlock && yaffs_StillSomeChunkBits(dev,block);
2176             chunkInBlock++, oldChunk++ )
2177         {
2178                 if(yaffs_CheckChunkBit(dev,block,chunkInBlock))
2179                 {
2180
2181                         // This page is in use and might need to be copied off
2182
2183                         markNAND = 1;
2184
2185                         //T(("copying page %x from %d to %d\n",mask,oldChunk,newChunk));
2186
2187                         yaffs_InitialiseTags(&tags);
2188
2189                         yaffs_ReadChunkWithTagsFromNAND(dev,oldChunk,buffer, &tags);
2190
2191                         object = yaffs_FindObjectByNumber(dev,tags.objectId);
2192
2193                         T(YAFFS_TRACE_GC_DETAIL,(TSTR("Collecting page %d, %d %d %d " TENDSTR),chunkInBlock,tags.objectId,tags.chunkId,tags.byteCount));
2194
2195                         if(!object)
2196                         {
2197                                 T(YAFFS_TRACE_ERROR,(TSTR("page %d in gc has no object " TENDSTR),oldChunk));
2198                         }
2199
2200                         if(object && object->deleted && tags.chunkId != 0)
2201                         {
2202                                 // Data chunk in a deleted file, throw it away
2203                                 // It's a soft deleted data chunk,
2204                                 // No need to copy this, just forget about it and fix up the
2205                                 // object.
2206
2207                                 //yaffs_PutChunkIntoFile(object, tags.chunkId, 0,0);
2208                                 object->nDataChunks--;
2209
2210                                 if(object->nDataChunks <= 0)
2211                                 {
2212                                         // remeber to clean up the object
2213                                         dev->gcCleanupList[cleanups] = tags.objectId;
2214                                         cleanups++;
2215                                 }
2216                                 markNAND = 0;
2217                         }
2218                         else if( 0 /* Todo object && object->deleted && object->nDataChunks == 0 */)
2219                         {
2220                                 // Deleted object header with no data chunks.
2221                                 // Can be discarded and the file deleted.
2222                                 object->chunkId = 0;
2223                                 yaffs_FreeTnode(object->myDev,object->variant.fileVariant.top);
2224                                 object->variant.fileVariant.top = NULL;
2225                                 yaffs_DoGenericObjectDeletion(object);
2226
2227                         }
2228                         else if(object)
2229                         {
2230                                 // It's either a data chunk in a live file or
2231                                 // an ObjectHeader, so we're interested in it.
2232                                 // NB Need to keep the ObjectHeaders of deleted files
2233                                 // until the whole file has been deleted off
2234                                 tags.serialNumber++;
2235
2236                                 dev->nGCCopies++;
2237
2238                                 if(tags.chunkId == 0)
2239                                 {
2240                                         // It is an object Id,
2241                                         // We need to nuke the shrinkheader flags first
2242                                         // We no longer want the shrinkHeader flag since its work is done
2243                                         // and if it is left in place it will mess up scanning.
2244                                         // Also, clear out any shadowing stuff
2245
2246                                         yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
2247                                         oh->isShrink = 0;
2248                                         oh->shadowsObject = -1;
2249                                         tags.extraShadows = 0;
2250                                         tags.extraIsShrinkHeader = 0;
2251                                 }
2252
2253                                 newChunk = yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &tags,1);
2254
2255                                 if(newChunk < 0)
2256                                 {
2257                                         retVal =  YAFFS_FAIL;
2258                                 }
2259                                 else
2260                                 {
2261
2262                                         // Ok, now fix up the Tnodes etc.
2263
2264                                         if(tags.chunkId == 0)
2265                                         {
2266                                                 // It's a header
2267                                                 object->chunkId = newChunk;
2268                                                 object->serial = tags.serialNumber;
2269                                         }
2270                                         else
2271                                         {
2272                                                 // It's a data chunk
2273                                                 yaffs_PutChunkIntoFile(object, tags.chunkId, newChunk,0);
2274                                         }
2275                                 }
2276                         }
2277
2278                         yaffs_DeleteChunk(dev,oldChunk,markNAND,__LINE__);
2279
2280                 }
2281         }
2282
2283         yaffs_ReleaseTempBuffer(dev,buffer,__LINE__);
2284
2285         //yaffs_VerifyFreeChunks(dev);
2286
2287         // Do any required cleanups
2288         for(i = 0; i < cleanups; i++)
2289         {
2290                 // Time to delete the file too
2291                 object =  yaffs_FindObjectByNumber(dev,dev->gcCleanupList[i]);
2292                 if(object)
2293                 {
2294                         yaffs_FreeTnode(dev,object->variant.fileVariant.top);
2295                         object->variant.fileVariant.top = NULL;
2296                         T(YAFFS_TRACE_GC,(TSTR("yaffs: About to finally delete object %d" TENDSTR),object->objectId));
2297                         yaffs_DoGenericObjectDeletion(object);
2298                 }
2299
2300         }
2301
2302         }
2303
2304         if(chunksBefore >= (chunksAfter = yaffs_GetErasedChunks(dev)))
2305         {
2306                         T(YAFFS_TRACE_GC,(TSTR("gc did not increase free chunks before %d after %d" TENDSTR),chunksBefore,chunksAfter));
2307         }
2308
2309
2310         dev->isDoingGC = 0;
2311
2312         //yaffs_VerifyFreeChunks(dev);
2313
2314         return YAFFS_OK;
2315 }
2316
2317
2318 // New garbage collector
2319 // If we're very low on erased blocks then we do aggressive garbage collection
2320 // otherwise we do "leasurely" garbage collection.
2321 // Aggressive gc looks further (whole array) and will accept dirtier blocks.
2322 // Passive gc only inspects smaller areas and will only accept cleaner blocks.
2323 //
2324 // The idea is to help clear out space in a more spread-out manner.
2325 // Dunno if it really does anything useful.
2326 //
2327 static int yaffs_CheckGarbageCollection(yaffs_Device *dev)
2328 {
2329         int block;
2330         int aggressive;
2331         int gcOk = YAFFS_OK;
2332         int maxTries = 0;
2333
2334         //yaffs_VerifyFreeChunks(dev);
2335
2336         if(dev->isDoingGC)
2337         {
2338                 // Bail out so we don't get recursive gc
2339                 return YAFFS_OK;
2340         }
2341
2342         // This loop should pass the first time.
2343         // We'll only see looping here if the erase of the collected block fails.
2344
2345         do{
2346                 maxTries++;
2347                 if(dev->nErasedBlocks < dev->nReservedBlocks)
2348                 {
2349                         // We need a block soon...
2350                         aggressive = 1;
2351                 }
2352                 else
2353                 {
2354                         // We're in no hurry
2355                         aggressive = 0;
2356                 }
2357
2358                 block = yaffs_FindBlockForGarbageCollection(dev,aggressive);
2359
2360                 if(block > 0)
2361                 {
2362                         dev->garbageCollections++;
2363                         if(!aggressive)
2364                         {
2365                                 dev->passiveGarbageCollections++;
2366                         }
2367
2368                         T(YAFFS_TRACE_GC,(TSTR("yaffs: GC erasedBlocks %d aggressive %d" TENDSTR),dev->nErasedBlocks,aggressive));
2369
2370                         gcOk =  yaffs_GarbageCollectBlock(dev,block);
2371                 }
2372
2373                 if(dev->nErasedBlocks < (dev->nReservedBlocks) && block > 0)
2374                 {
2375                         T(YAFFS_TRACE_GC,(TSTR("yaffs: GC !!!no reclaim!!! erasedBlocks %d after try %d block %d" TENDSTR),dev->nErasedBlocks,maxTries,block));
2376                 }
2377         } while((dev->nErasedBlocks < dev->nReservedBlocks) && (block > 0) && (maxTries < 2));
2378
2379         return aggressive ? gcOk: YAFFS_OK;
2380 }
2381
2382
2383 //////////////////////////// TAGS ///////////////////////////////////////
2384
2385
2386
2387 static int yaffs_TagsMatch(const yaffs_ExtendedTags *tags, int objectId, int chunkInObject)
2388 {
2389         return  (  tags->chunkId == chunkInObject &&
2390                            tags->objectId == objectId &&
2391                            !tags->chunkDeleted) ? 1 : 0;
2392
2393 }
2394
2395 /////////////////////////////////////////////////////////////////////////////////////////////////////////
2396
2397
2398 static int yaffs_FindChunkInFile(yaffs_Object *in,int chunkInInode,yaffs_ExtendedTags *tags)
2399 {
2400         //Get the Tnode, then get the level 0 offset chunk offset
2401     yaffs_Tnode *tn;
2402     int theChunk = -1;
2403     yaffs_ExtendedTags localTags;
2404     int retVal = -1;
2405
2406     yaffs_Device *dev = in->myDev;
2407
2408
2409     if(!tags)
2410     {
2411         // Passed a NULL, so use our own tags space
2412         tags = &localTags;
2413     }
2414
2415     tn = yaffs_FindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
2416
2417     if(tn)
2418     {
2419                 theChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] << dev->chunkGroupBits;
2420
2421                 retVal = yaffs_FindChunkInGroup(dev,theChunk,tags,in->objectId,chunkInInode);
2422     }
2423     return retVal;
2424 }
2425
2426 static int yaffs_FindAndDeleteChunkInFile(yaffs_Object *in,int chunkInInode,yaffs_ExtendedTags *tags)
2427 {
2428         //Get the Tnode, then get the level 0 offset chunk offset
2429     yaffs_Tnode *tn;
2430     int theChunk = -1;
2431     yaffs_ExtendedTags localTags;
2432
2433     yaffs_Device *dev = in->myDev;
2434     int retVal = -1;
2435
2436     if(!tags)
2437     {
2438         // Passed a NULL, so use our own tags space
2439         tags = &localTags;
2440     }
2441
2442     tn = yaffs_FindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
2443
2444     if(tn)
2445     {
2446
2447                 theChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] << dev->chunkGroupBits;
2448
2449                 retVal = yaffs_FindChunkInGroup(dev,theChunk,tags,in->objectId,chunkInInode);
2450
2451                 // Delete the entry in the filestructure (if found)
2452                 if(retVal != -1)
2453                 {
2454                         tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] = 0;
2455                 }
2456     }
2457     else
2458     {
2459         //T(("No level 0 found for %d\n", chunkInInode));
2460     }
2461
2462     if(retVal == -1)
2463     {
2464         //T(("Could not find %d to delete\n",chunkInInode));
2465     }
2466     return retVal;
2467 }
2468
2469
2470 #ifdef YAFFS_PARANOID
2471
2472 static int yaffs_CheckFileSanity(yaffs_Object *in)
2473 {
2474         int chunk;
2475         int nChunks;
2476         int fSize;
2477         int failed = 0;
2478         int objId;
2479         yaffs_Tnode *tn;
2480     yaffs_Tags localTags;
2481     yaffs_Tags *tags = &localTags;
2482     int theChunk;
2483     int chunkDeleted;
2484
2485
2486         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
2487         {
2488                 //T(("Object not a file\n"));
2489                 return YAFFS_FAIL;
2490         }
2491
2492         objId = in->objectId;
2493         fSize  = in->variant.fileVariant.fileSize;
2494         nChunks = (fSize + in->myDev->nBytesPerChunk -1)/in->myDev->nBytesPerChunk;
2495
2496         for(chunk = 1; chunk <= nChunks; chunk++)
2497         {
2498                 tn = yaffs_FindLevel0Tnode(in->myDev,&in->variant.fileVariant, chunk);
2499
2500                 if(tn)
2501                 {
2502
2503                         theChunk = tn->level0[chunk & YAFFS_TNODES_LEVEL0_MASK] << in->myDev->chunkGroupBits;
2504
2505                 if(yaffs_CheckChunkBits(dev,theChunk/dev->nChunksPerBlock,theChunk%dev->nChunksPerBlock))
2506                         {
2507
2508
2509                                 yaffs_ReadChunkTagsFromNAND(in->myDev,theChunk,tags,&chunkDeleted);
2510                                 if(yaffs_TagsMatch(tags,in->objectId,chunk,chunkDeleted))
2511                                 {
2512                                         // found it;
2513
2514                                 }
2515                         }
2516                         else
2517                         {
2518                                 //T(("File problem file [%d,%d] NAND %d  tags[%d,%d]\n",
2519                                 //              objId,chunk,theChunk,tags->chunkId,tags->objectId);
2520
2521                                 failed = 1;
2522
2523                         }
2524
2525                 }
2526                 else
2527                 {
2528                         //T(("No level 0 found for %d\n", chunk));
2529                 }
2530         }
2531
2532         return failed ? YAFFS_FAIL : YAFFS_OK;
2533 }
2534
2535 #endif
2536
2537 static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan)
2538 {
2539         // NB inScan is zero unless scanning. For forward scanning, inScan is > 0; for backward scanning inScan is < 0
2540         yaffs_Tnode *tn;
2541         yaffs_Device *dev = in->myDev;
2542         int existingChunk;
2543         yaffs_ExtendedTags existingTags;
2544         yaffs_ExtendedTags newTags;
2545         unsigned existingSerial, newSerial;
2546
2547         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
2548         {
2549                 // Just ignore an attempt at putting a chunk into a non-file during scanning
2550                 // If it is not during Scanning then something went wrong!
2551                 if(!inScan)
2552                 {
2553                         T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy:attempt to put data chunk into a non-file" TENDSTR)));
2554                         YBUG();
2555                 }
2556
2557                 yaffs_DeleteChunk(dev,chunkInNAND,1,__LINE__);
2558                 return YAFFS_OK;
2559         }
2560
2561         tn = yaffs_AddOrFindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
2562         if(!tn)
2563         {
2564                 return YAFFS_FAIL;
2565         }
2566
2567         existingChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK];
2568
2569         if(inScan != 0)
2570         {
2571                 // If we're scanning then we need to test for duplicates
2572                 // NB This does not need to be efficient since it should only ever
2573                 // happen when the power fails during a write, then only one
2574                 // chunk should ever be affected.
2575                 //
2576                 // Correction for YAFFS2: This could happen quite a lot and we need to think about efficiency! TODO
2577                 // Update: For backward scanning we don't need to re-read tags so this is quite cheap.
2578
2579
2580
2581                 if(existingChunk != 0)
2582                 {
2583                         // NB Right now existing chunk will not be real chunkId if the device >= 32MB
2584                         //    thus we have to do a FindChunkInFile to get the real chunk id.
2585                         //
2586                         // We have a duplicate now we need to decide which one to use:
2587                         //
2588                         // Backwards scanning YAFFS2: The old one is what we use, dump the new one.
2589                         // Forward scanning YAFFS2: The new one is what we use, dump the old one.
2590                         // YAFFS1: Get both sets of tags and compare serial numbers.
2591                         //
2592                         //
2593
2594                         if(inScan > 0)
2595                         {
2596                                 // Only do this for forward scanning
2597                                 yaffs_ReadChunkWithTagsFromNAND(dev,chunkInNAND, NULL,&newTags);
2598
2599
2600                                 // Do a proper find
2601                                 existingChunk = yaffs_FindChunkInFile(in,chunkInInode, &existingTags);
2602                         }
2603
2604                         if(existingChunk <=0)
2605                         {
2606                                 //Hoosterman - how did this happen?
2607
2608                                 T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: existing chunk < 0 in scan" TENDSTR)));
2609
2610                         }
2611
2612
2613                         // NB The deleted flags should be false, otherwise the chunks will
2614                         // not be loaded during a scan
2615
2616                         newSerial = newTags.serialNumber;
2617                         existingSerial = existingTags.serialNumber;
2618
2619                         if( (inScan > 0) &&
2620                             ( in->myDev->isYaffs2  ||
2621                               existingChunk <= 0 ||
2622                              ((existingSerial+1) & 3) == newSerial))
2623                         {
2624                                 // Forward scanning.
2625                                 // Use new
2626                                 // Delete the old one and drop through to update the tnode
2627                                 yaffs_DeleteChunk(dev,existingChunk,1,__LINE__);
2628                         }
2629                         else
2630                         {
2631                                 // Backward scanning or we want to use the existing one
2632                                 // Use existing.
2633                                 // Delete the new one and return early so that the tnode isn't changed
2634                                 yaffs_DeleteChunk(dev,chunkInNAND,1,__LINE__);
2635                                 return YAFFS_OK;
2636                         }
2637                 }
2638
2639         }
2640
2641         if(existingChunk == 0)
2642         {
2643                 in->nDataChunks++;
2644         }
2645
2646         tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] = (chunkInNAND >> dev->chunkGroupBits);
2647
2648         return YAFFS_OK;
2649 }
2650
2651
2652
2653 static int yaffs_ReadChunkDataFromObject(yaffs_Object *in,int chunkInInode, __u8 *buffer)
2654 {
2655     int chunkInNAND = yaffs_FindChunkInFile(in,chunkInInode,NULL);
2656
2657     if(chunkInNAND >= 0)
2658     {
2659                 return yaffs_ReadChunkWithTagsFromNAND(in->myDev,chunkInNAND,buffer,NULL);
2660         }
2661         else
2662         {
2663                 T(YAFFS_TRACE_NANDACCESS,(TSTR("Chunk %d not found zero instead" TENDSTR),chunkInNAND));
2664
2665                 memset(buffer,0,in->myDev->nBytesPerChunk); // get sane data if you read a hole
2666                 return 0;
2667         }
2668
2669 }
2670
2671
2672 void yaffs_DeleteChunk(yaffs_Device *dev,int chunkId,int markNAND,int lyn)
2673 {
2674         int block;
2675         int page;
2676         yaffs_ExtendedTags tags;
2677         yaffs_BlockInfo *bi;
2678
2679         if(chunkId <= 0) return;
2680
2681         dev->nDeletions++;
2682         block = chunkId / dev->nChunksPerBlock;
2683         page = chunkId % dev->nChunksPerBlock;
2684
2685         bi = yaffs_GetBlockInfo(dev,block);
2686
2687         T(YAFFS_TRACE_DELETION,(TSTR("line %d delete of chunk %d" TENDSTR),lyn,chunkId));
2688
2689         if(markNAND &&
2690           bi->blockState != YAFFS_BLOCK_STATE_COLLECTING &&
2691           !dev->isYaffs2)
2692         {
2693 //              yaffs_SpareInitialise(&spare);
2694
2695 #ifdef CONFIG_MTD_NAND_VERIFY_WRITE
2696
2697                 //read data before write, to ensure correct ecc
2698                 //if we're using MTD verification under Linux
2699                 yaffs_ReadChunkFromNAND(dev,chunkId,NULL,&spare,0);
2700 #endif
2701
2702                 yaffs_InitialiseTags(&tags);
2703
2704                 tags.chunkDeleted = 1;
2705
2706
2707                 yaffs_WriteChunkWithTagsToNAND(dev,chunkId,NULL,&tags);
2708                 yaffs_HandleUpdateChunk(dev,chunkId,&tags);
2709         }
2710         else
2711         {
2712                         dev->nUnmarkedDeletions++;
2713         }
2714
2715
2716         // Pull out of the management area.
2717         // If the whole block became dirty, this will kick off an erasure.
2718         if(     bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING ||
2719             bi->blockState == YAFFS_BLOCK_STATE_FULL ||
2720             bi->blockState == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
2721             bi->blockState == YAFFS_BLOCK_STATE_COLLECTING)
2722         {
2723                 dev->nFreeChunks++;
2724
2725                 yaffs_ClearChunkBit(dev,block,page);
2726
2727                 bi->pagesInUse--;
2728
2729                 if(bi->pagesInUse == 0 &&
2730                    !bi->hasShrinkHeader &&
2731                bi->blockState != YAFFS_BLOCK_STATE_ALLOCATING &&
2732                bi->blockState != YAFFS_BLOCK_STATE_NEEDS_SCANNING)
2733             {
2734                 yaffs_BlockBecameDirty(dev,block);
2735             }
2736
2737         }
2738         else
2739         {
2740                 // T(("Bad news deleting chunk %d\n",chunkId));
2741         }
2742
2743 }
2744
2745
2746
2747
2748 static int yaffs_WriteChunkDataToObject(yaffs_Object *in,int chunkInInode, const __u8 *buffer,int nBytes,int useReserve)
2749 {
2750         // Find old chunk Need to do this to get serial number
2751         // Write new one and patch into tree.
2752         // Invalidate old tags.
2753
2754     int prevChunkId;
2755     yaffs_ExtendedTags prevTags;
2756
2757     int newChunkId;
2758     yaffs_ExtendedTags newTags;
2759
2760     yaffs_Device *dev = in->myDev;
2761
2762         yaffs_CheckGarbageCollection(dev);
2763
2764         // Get the previous chunk at this location in the file if it exists
2765     prevChunkId  = yaffs_FindChunkInFile(in,chunkInInode,&prevTags);
2766
2767     // Set up new tags
2768     yaffs_InitialiseTags(&newTags);
2769
2770         newTags.chunkId = chunkInInode;
2771         newTags.objectId = in->objectId;
2772         newTags.serialNumber = (prevChunkId >= 0) ? prevTags.serialNumber + 1 : 1;
2773         newTags.byteCount = nBytes;
2774
2775 //      yaffs_CalcTagsECC(&newTags);
2776
2777         newChunkId = yaffs_WriteNewChunkWithTagsToNAND(dev,buffer,&newTags,useReserve);
2778
2779         if(newChunkId >= 0)
2780         {
2781                 yaffs_PutChunkIntoFile(in,chunkInInode,newChunkId,0);
2782
2783
2784                 if(prevChunkId >= 0)
2785                 {
2786                         yaffs_DeleteChunk(dev,prevChunkId,1,__LINE__);
2787
2788                 }
2789
2790                 yaffs_CheckFileSanity(in);
2791         }
2792         return newChunkId;
2793
2794
2795
2796
2797
2798 }
2799
2800
2801 // UpdateObjectHeader updates the header on NAND for an object.
2802 // If name is not NULL, then that new name is used.
2803 //
2804 int yaffs_UpdateObjectHeader(yaffs_Object *in,const YCHAR *name, int force,int isShrink,int shadows)
2805 {
2806
2807         yaffs_BlockInfo *bi;
2808
2809         yaffs_Device *dev = in->myDev;
2810
2811     int prevChunkId;
2812     int retVal = 0;
2813
2814     int newChunkId;
2815     yaffs_ExtendedTags newTags;
2816
2817     __u8 *buffer = NULL;
2818     YCHAR oldName[YAFFS_MAX_NAME_LENGTH+1];
2819
2820    // __u8 bufferOld[YAFFS_BYTES_PER_CHUNK];
2821
2822     yaffs_ObjectHeader *oh = NULL;
2823     // yaffs_ObjectHeader *ohOld = (yaffs_ObjectHeader *)bufferOld;
2824
2825
2826     if(!in->fake || force)
2827     {
2828
2829                 yaffs_CheckGarbageCollection(dev);
2830
2831             buffer = yaffs_GetTempBuffer(in->myDev,__LINE__);
2832             oh  = (yaffs_ObjectHeader *)buffer;
2833
2834                 prevChunkId = in->chunkId;
2835
2836                 if(prevChunkId >= 0)
2837                 {
2838                         yaffs_ReadChunkWithTagsFromNAND(dev,prevChunkId,buffer,NULL);
2839                         memcpy(oldName,oh->name,sizeof(oh->name));
2840                 }
2841
2842                 memset(buffer,0xFF,dev->nBytesPerChunk);
2843
2844                 // Header data
2845                 oh->type = in->variantType;
2846
2847                 oh->yst_mode = in->yst_mode;
2848
2849                 // shadowing
2850                 oh->shadowsObject = shadows;
2851
2852 #ifdef CONFIG_YAFFS_WINCE
2853                 oh->win_atime[0] = in->win_atime[0];
2854                 oh->win_ctime[0] = in->win_ctime[0];
2855                 oh->win_mtime[0] = in->win_mtime[0];
2856                 oh->win_atime[1] = in->win_atime[1];
2857                 oh->win_ctime[1] = in->win_ctime[1];
2858                 oh->win_mtime[1] = in->win_mtime[1];
2859 #else
2860                 oh->yst_uid = in->yst_uid;
2861                 oh->yst_gid = in->yst_gid;
2862                 oh->yst_atime = in->yst_atime;
2863                 oh->yst_mtime = in->yst_mtime;
2864                 oh->yst_ctime = in->yst_ctime;
2865                 oh->yst_rdev = in->yst_rdev;
2866 #endif
2867                 if(in->parent)
2868                 {
2869                         oh->parentObjectId = in->parent->objectId;
2870                 }
2871                 else
2872                 {
2873                         oh->parentObjectId = 0;
2874                 }
2875
2876                 //oh->sum = in->sum;
2877                 if(name && *name)
2878                 {
2879                         memset(oh->name,0,sizeof(oh->name));
2880                         yaffs_strncpy(oh->name,name,YAFFS_MAX_NAME_LENGTH);
2881                 }
2882                 else if(prevChunkId)
2883                 {
2884                         memcpy(oh->name, oldName,sizeof(oh->name));
2885                 }
2886                 else
2887                 {
2888                         memset(oh->name,0,sizeof(oh->name));
2889                 }
2890
2891                 oh->isShrink = isShrink;
2892
2893                 switch(in->variantType)
2894                 {
2895                         case YAFFS_OBJECT_TYPE_UNKNOWN:
2896                                 // Should not happen
2897                                 break;
2898                         case YAFFS_OBJECT_TYPE_FILE:
2899                                 oh->fileSize = (oh->parentObjectId == YAFFS_OBJECTID_DELETED ||
2900                                                 oh->parentObjectId == YAFFS_OBJECTID_UNLINKED) ? 0 : in->variant.fileVariant.fileSize;
2901                                 break;
2902                         case YAFFS_OBJECT_TYPE_HARDLINK:
2903                                 oh->equivalentObjectId = in->variant.hardLinkVariant.equivalentObjectId;
2904                                 break;
2905                         case YAFFS_OBJECT_TYPE_SPECIAL:
2906                                 // Do nothing
2907                                 break;
2908                         case YAFFS_OBJECT_TYPE_DIRECTORY:
2909                                 // Do nothing
2910                                 break;
2911                         case YAFFS_OBJECT_TYPE_SYMLINK:
2912                                 yaffs_strncpy(oh->alias,in->variant.symLinkVariant.alias,YAFFS_MAX_ALIAS_LENGTH);
2913                                 oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
2914                                 break;
2915                 }
2916
2917                 // Tags
2918                 yaffs_InitialiseTags(&newTags);
2919                 in->serial++;
2920                 newTags.chunkId = 0;
2921                 newTags.objectId = in->objectId;
2922                 newTags.serialNumber = in->serial;
2923
2924                 // Add extra info for file header
2925
2926                 newTags.extraHeaderInfoAvailable = 1;
2927                 newTags.extraParentObjectId = oh->parentObjectId;
2928                 newTags.extraFileLength = oh->fileSize;
2929                 newTags.extraIsShrinkHeader = oh->isShrink;
2930                 newTags.extraEquivalentObjectId = oh->equivalentObjectId;
2931                 newTags.extraShadows = (oh->shadowsObject > 0) ? 1 : 0;
2932                 newTags.extraObjectType  = in->variantType;
2933
2934                 // Create new chunk in NAND
2935                 newChunkId = yaffs_WriteNewChunkWithTagsToNAND(dev,buffer,&newTags, (prevChunkId >= 0) ? 1 : 0 );
2936
2937                 if(newChunkId >= 0)
2938                 {
2939
2940                         in->chunkId = newChunkId;
2941
2942                         if(prevChunkId >= 0)
2943                         {
2944                                 yaffs_DeleteChunk(dev,prevChunkId,1,__LINE__);
2945                         }
2946
2947                         in->dirty = 0;
2948
2949                         // If this was a shrink, then mark the block that the chunk lives on
2950                         if(isShrink)
2951                         {
2952                                 bi = yaffs_GetBlockInfo(in->myDev,newChunkId / in->myDev->nChunksPerBlock);
2953                                 bi->hasShrinkHeader = 1;
2954                         }
2955
2956                 }
2957
2958                 retVal =  newChunkId;
2959
2960     }
2961
2962         if(buffer)
2963                 yaffs_ReleaseTempBuffer(dev,buffer,__LINE__);
2964
2965     return retVal;
2966 }
2967
2968
2969 /////////////////////// Short Operations Cache ////////////////////////////////
2970 //      In many siturations where there is no high level buffering (eg WinCE) a lot of
2971 //      reads might be short sequential reads, and a lot of writes may be short
2972 //  sequential writes. eg. scanning/writing a jpeg file.
2973 //      In these cases, a short read/write cache can provide a huge perfomance benefit
2974 //  with dumb-as-a-rock code.
2975 //  There are a limited number (~10) of cache chunks per device so that we don't
2976 //  need a very intelligent search.
2977
2978
2979
2980
2981
2982 static void yaffs_FlushFilesChunkCache(yaffs_Object *obj)
2983 {
2984         yaffs_Device *dev = obj->myDev;
2985         int lowest = -99; // Stop compiler whining.
2986         int i;
2987         yaffs_ChunkCache *cache;
2988         int chunkWritten = 0;
2989         //int nBytes;
2990         int nCaches = obj->myDev->nShortOpCaches;
2991
2992         if  (nCaches > 0)
2993         {
2994                 do{
2995                         cache = NULL;
2996
2997                         // Find the dirty cache for this object with the lowest chunk id.
2998                         for(i = 0; i < nCaches; i++)
2999                         {
3000                                 if(dev->srCache[i].object == obj &&
3001                                    dev->srCache[i].dirty)
3002                                 {
3003                                         if(!cache ||  dev->srCache[i].chunkId < lowest)
3004                                         {
3005                                                 cache = &dev->srCache[i];
3006                                                 lowest = cache->chunkId;
3007                                         }
3008                                 }
3009                         }
3010
3011                         if(cache && !cache->locked)
3012                         {
3013                                 //Write it out and free it up
3014
3015                                 chunkWritten = yaffs_WriteChunkDataToObject(cache->object,
3016                                                                                 cache->chunkId,
3017                                                                                 cache->data,
3018                                                                                 cache->nBytes,1);
3019                                 cache->dirty = 0;
3020                                 cache->object = NULL;
3021                         }
3022
3023                 } while(cache && chunkWritten > 0);
3024
3025                 if(cache)
3026                 {
3027                         //Hoosterman, disk full while writing cache out.
3028                         T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: no space during cache write" TENDSTR)));
3029
3030                 }
3031         }
3032
3033 }
3034
3035
3036 // Grab us a chunk for use.
3037 // First look for an empty one.
3038 // Then look for the least recently used non-dirty one.
3039 // Then look for the least recently used dirty one...., flush and look again.
3040 static yaffs_ChunkCache *yaffs_GrabChunkCacheWorker(yaffs_Device *dev)
3041 {
3042         int i;
3043         int usage;
3044         int theOne;
3045
3046         if(dev->nShortOpCaches > 0)
3047         {
3048                 for(i = 0; i < dev->nShortOpCaches; i++)
3049                 {
3050                         if(!dev->srCache[i].object)
3051                         {
3052                                 //T(("Grabbing empty %d\n",i));
3053
3054                                 //printf("Grabbing empty %d\n",i);
3055
3056                                 return &dev->srCache[i];
3057                         }
3058                 }
3059
3060                 return NULL;
3061
3062                 theOne = -1;
3063                 usage = 0; // just to stop the compiler grizzling
3064
3065                 for(i = 0; i < dev->nShortOpCaches; i++)
3066                 {
3067                         if(!dev->srCache[i].dirty &&
3068                         ((dev->srCache[i].lastUse < usage  && theOne >= 0)||
3069                                 theOne < 0))
3070                         {
3071                                 usage = dev->srCache[i].lastUse;
3072                                 theOne = i;
3073                         }
3074                 }
3075
3076                 //T(("Grabbing non-empty %d\n",theOne));
3077
3078                 //if(theOne >= 0) printf("Grabbed non-empty cache %d\n",theOne);
3079
3080                 return  theOne >= 0 ?  &dev->srCache[theOne] : NULL;
3081         }
3082         else
3083         {
3084                 return NULL;
3085         }
3086
3087 }
3088
3089
3090 static yaffs_ChunkCache *yaffs_GrabChunkCache(yaffs_Device *dev)
3091 {
3092         yaffs_ChunkCache *cache;
3093         yaffs_Object *theObj;
3094         int usage;
3095         int i;
3096         int pushout;
3097
3098         if(dev->nShortOpCaches > 0)
3099         {
3100                 // Try find a non-dirty one...
3101
3102                 cache = yaffs_GrabChunkCacheWorker(dev);
3103
3104                 if(!cache)
3105                 {
3106                         // They were all dirty, find the last recently used object and flush
3107                         // its cache, then  find again.
3108                         // NB what's here is not very accurate, we actually flush the object
3109                         // the last recently used page.
3110
3111                         // With locking we can't assume we can use entry zero
3112
3113
3114                         theObj = NULL;
3115                         usage = -1;
3116                         cache = NULL;
3117                         pushout = -1;
3118
3119                         for(i = 0; i < dev->nShortOpCaches; i++)
3120                         {
3121                                 if( dev->srCache[i].object &&
3122                                         !dev->srCache[i].locked &&
3123                                         (dev->srCache[i].lastUse < usage || !cache))
3124                                 {
3125                                         usage  = dev->srCache[i].lastUse;
3126                                         theObj = dev->srCache[i].object;
3127                                         cache = &dev->srCache[i];
3128                                         pushout = i;
3129                                 }
3130                         }
3131
3132                         if(!cache || cache->dirty)
3133                         {
3134
3135                                 //printf("Dirty ");
3136                                 yaffs_FlushFilesChunkCache(theObj);
3137
3138                                 // Try again
3139                                 cache = yaffs_GrabChunkCacheWorker(dev);
3140                         }
3141                         else
3142                         {
3143                                 //printf(" pushout %d\n",pushout);
3144                         }
3145
3146                 }
3147                 return cache;
3148         }
3149         else
3150                 return NULL;
3151
3152 }
3153
3154
3155 // Find a cached chunk
3156 static yaffs_ChunkCache *yaffs_FindChunkCache(const yaffs_Object *obj, int chunkId)
3157 {
3158         yaffs_Device *dev = obj->myDev;
3159         int i;
3160         if(dev->nShortOpCaches > 0)
3161         {
3162                 for(i = 0; i < dev->nShortOpCaches; i++)
3163                 {
3164                         if(dev->srCache[i].object == obj &&
3165                         dev->srCache[i].chunkId == chunkId)
3166                         {
3167                                 dev->cacheHits++;
3168
3169                                 return &dev->srCache[i];
3170                         }
3171                 }
3172         }
3173         return NULL;
3174 }
3175
3176 // Mark the chunk for the least recently used algorithym
3177 static void yaffs_UseChunkCache(yaffs_Device *dev, yaffs_ChunkCache *cache, int isAWrite)
3178 {
3179
3180         if(dev->nShortOpCaches > 0)
3181         {
3182                 if( dev->srLastUse < 0 ||
3183                         dev->srLastUse > 100000000)
3184                 {
3185                         // Reset the cache usages
3186                         int i;
3187                         for(i = 1; i < dev->nShortOpCaches; i++)
3188                         {
3189                                 dev->srCache[i].lastUse = 0;
3190                         }
3191                         dev->srLastUse = 0;
3192                 }
3193
3194                 dev->srLastUse++;
3195
3196                 cache->lastUse = dev->srLastUse;
3197
3198                 if(isAWrite)
3199                 {
3200                         cache->dirty = 1;
3201                 }
3202         }
3203 }
3204
3205 // Invalidate a single cache page.
3206 // Do this when a whole page gets written,
3207 // ie the short cache for this page is no longer valid.
3208 static void yaffs_InvalidateChunkCache(yaffs_Object *object, int chunkId)
3209 {
3210         if(object->myDev->nShortOpCaches > 0)
3211         {
3212                 yaffs_ChunkCache *cache = yaffs_FindChunkCache(object,chunkId);
3213
3214                 if(cache)
3215                 {
3216                         cache->object = NULL;
3217                 }
3218         }
3219 }
3220
3221
3222 // Invalidate all the cache pages associated with this object
3223 // Do this whenever ther file is deleted or resized.
3224 static void yaffs_InvalidateWholeChunkCache(yaffs_Object *in)
3225 {
3226         int i;
3227         yaffs_Device *dev = in->myDev;
3228
3229         if(dev->nShortOpCaches > 0)
3230         {
3231                 // Now invalidate it.
3232                 for(i = 0; i < dev->nShortOpCaches; i++)
3233                 {
3234                         if(dev->srCache[i].object == in)
3235                         {
3236                                 dev->srCache[i].object = NULL;
3237                         }
3238                 }
3239         }
3240 }
3241
3242
3243
3244
3245
3246 ///////////////////////// File read/write ///////////////////////////////
3247 // Read and write have very similar structures.
3248 // In general the read/write has three parts to it
3249 // * An incomplete chunk to start with (if the read/write is not chunk-aligned)
3250 // * Some complete chunks
3251 // * An incomplete chunk to end off with
3252 //
3253 // Curve-balls: the first chunk might also be the last chunk.
3254
3255 int yaffs_ReadDataFromFile(yaffs_Object *in, __u8 * buffer, __u32 offset, int nBytes)
3256 {
3257
3258
3259         int chunk;
3260         int start;
3261         int nToCopy;
3262         int n = nBytes;
3263         int nDone = 0;
3264         yaffs_ChunkCache *cache;
3265
3266         yaffs_Device *dev;
3267
3268         dev = in->myDev;
3269
3270         while(n > 0)
3271         {
3272                 chunk = offset / dev->nBytesPerChunk + 1; // The first chunk is 1
3273                 start = offset % dev->nBytesPerChunk;
3274
3275                 // OK now check for the curveball where the start and end are in
3276                 // the same chunk.
3277                 if(     (start + n) < dev->nBytesPerChunk)
3278                 {
3279                         nToCopy = n;
3280                 }
3281                 else
3282                 {
3283                         nToCopy = dev->nBytesPerChunk - start;
3284                 }
3285
3286                 cache = yaffs_FindChunkCache(in,chunk);
3287
3288                 // If the chunk is already in the cache or it is less than a whole chunk
3289                 // then use the cache (if there is caching)
3290                 // else bypass the cache.
3291                 if( cache || nToCopy != dev->nBytesPerChunk)
3292                 {
3293                         if(dev->nShortOpCaches > 0)
3294                         {
3295
3296                                 // If we can't find the data in the cache, then load it up.
3297
3298                                 if(!cache)
3299                                 {
3300                                         cache = yaffs_GrabChunkCache(in->myDev);
3301                                         cache->object = in;
3302                                         cache->chunkId = chunk;
3303                                         cache->dirty = 0;
3304                                         cache->locked = 0;
3305                                         yaffs_ReadChunkDataFromObject(in,chunk,cache->data);
3306                                         cache->nBytes = 0;
3307                                 }
3308
3309                                 yaffs_UseChunkCache(dev,cache,0);
3310
3311                                 cache->locked = 1;
3312
3313 #ifdef CONFIG_YAFFS_WINCE
3314                                 yfsd_UnlockYAFFS(TRUE);
3315 #endif
3316                                 memcpy(buffer,&cache->data[start],nToCopy);
3317
3318 #ifdef CONFIG_YAFFS_WINCE
3319                                 yfsd_LockYAFFS(TRUE);
3320 #endif
3321                                 cache->locked = 0;
3322                         }
3323                         else
3324                         {
3325                                 // Read into the local buffer then copy...
3326
3327                                 __u8 *localBuffer = yaffs_GetTempBuffer(dev,__LINE__);
3328                                 yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
3329 #ifdef CONFIG_YAFFS_WINCE
3330                                 yfsd_UnlockYAFFS(TRUE);
3331 #endif
3332                                 memcpy(buffer,&localBuffer[start],nToCopy);
3333
3334 #ifdef CONFIG_YAFFS_WINCE
3335                                 yfsd_LockYAFFS(TRUE);
3336 #endif
3337                                 yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
3338                         }
3339
3340                 }
3341                 else
3342                 {
3343 #ifdef CONFIG_YAFFS_WINCE
3344                         __u8 *localBuffer = yaffs_GetTempBuffer(dev,__LINE__);
3345
3346                         // Under WinCE can't do direct transfer. Need to use a local buffer.
3347                         // This is because we otherwise screw up WinCE's memory mapper
3348                         yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
3349
3350 #ifdef CONFIG_YAFFS_WINCE
3351                                 yfsd_UnlockYAFFS(TRUE);
3352 #endif
3353                         memcpy(buffer,localBuffer,dev->nBytesPerChunk);
3354
3355 #ifdef CONFIG_YAFFS_WINCE
3356                                 yfsd_LockYAFFS(TRUE);
3357                                 yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
3358 #endif
3359
3360 #else
3361                         // A full chunk. Read directly into the supplied buffer.
3362                         yaffs_ReadChunkDataFromObject(in,chunk,buffer);
3363 #endif
3364                 }
3365
3366                 n -= nToCopy;
3367                 offset += nToCopy;
3368                 buffer += nToCopy;
3369                 nDone += nToCopy;
3370
3371         }
3372
3373         return nDone;
3374 }
3375
3376
3377
3378 int yaffs_WriteDataToFile(yaffs_Object *in,const __u8 * buffer, __u32 offset, int nBytes, int writeThrough)
3379 {
3380
3381         int chunk;
3382         int start;
3383         int nToCopy;
3384         int n = nBytes;
3385         int nDone = 0;
3386         int nToWriteBack;
3387         int startOfWrite = offset;
3388         int chunkWritten = 0;
3389         int nBytesRead;
3390
3391         yaffs_Device *dev;
3392
3393         dev = in->myDev;
3394
3395
3396         while(n > 0 && chunkWritten >= 0)
3397         {
3398                 chunk = offset / dev->nBytesPerChunk + 1;
3399                 start = offset % dev->nBytesPerChunk;
3400
3401
3402                 // OK now check for the curveball where the start and end are in
3403                 // the same chunk.
3404
3405                 if((start + n) < dev->nBytesPerChunk)
3406                 {
3407                         nToCopy = n;
3408
3409                         // Now folks, to calculate how many bytes to write back....
3410                         // If we're overwriting and not writing to then end of file then
3411                         // we need to write back as much as was there before.
3412
3413                         nBytesRead = in->variant.fileVariant.fileSize - ((chunk -1) * dev->nBytesPerChunk);
3414
3415                         if(nBytesRead > dev->nBytesPerChunk)
3416                         {
3417                                 nBytesRead = dev->nBytesPerChunk;
3418                         }
3419
3420                         nToWriteBack = (nBytesRead > (start + n)) ? nBytesRead : (start +n);
3421
3422                 }
3423                 else
3424                 {
3425                         nToCopy = dev->nBytesPerChunk - start;
3426                         nToWriteBack = dev->nBytesPerChunk;
3427                 }
3428
3429                 if(nToCopy != dev->nBytesPerChunk)
3430                 {
3431                         // An incomplete start or end chunk (or maybe both start and end chunk)
3432                         if(dev->nShortOpCaches > 0)
3433                            {
3434                                 yaffs_ChunkCache *cache;
3435                                 // If we can't find the data in the cache, then load it up.
3436                                 cache = yaffs_FindChunkCache(in,chunk);
3437                                 if(!cache && yaffs_CheckSpaceForAllocation(in->myDev))
3438                                 {
3439                                         cache = yaffs_GrabChunkCache(in->myDev);
3440                                         cache->object = in;
3441                                         cache->chunkId = chunk;
3442                                         cache->dirty = 0;
3443                                         cache->locked = 0;
3444                                         yaffs_ReadChunkDataFromObject(in,chunk,cache->data);
3445                                 }
3446
3447                                 if(cache)
3448                                 {
3449                                         yaffs_UseChunkCache(dev,cache,1);
3450                                         cache->locked = 1;
3451 #ifdef CONFIG_YAFFS_WINCE
3452                                 yfsd_UnlockYAFFS(TRUE);
3453 #endif
3454
3455                                         memcpy(&cache->data[start],buffer,nToCopy);
3456
3457 #ifdef CONFIG_YAFFS_WINCE
3458                                 yfsd_LockYAFFS(TRUE);
3459 #endif
3460                                         cache->locked = 0;
3461                                         cache->nBytes = nToWriteBack;
3462
3463                                         if(writeThrough)
3464                                         {
3465                                                 chunkWritten = yaffs_WriteChunkDataToObject(cache->object,
3466                                                                                             cache->chunkId,
3467                                                                                             cache->data,
3468                                                                                             cache->nBytes,1);
3469                                                 cache->dirty = 0;
3470                                         }
3471
3472                                 }
3473                                 else
3474                                 {
3475                                         chunkWritten = -1; // fail the write
3476                                 }
3477                         }
3478                         else
3479                         {
3480                                 // An incomplete start or end chunk (or maybe both start and end chunk)
3481                                 // Read into the local buffer then copy, then copy over and write back.
3482
3483                                 __u8 *localBuffer = yaffs_GetTempBuffer(dev,__LINE__);
3484
3485                                 yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
3486
3487 #ifdef CONFIG_YAFFS_WINCE
3488                                 yfsd_UnlockYAFFS(TRUE);
3489 #endif
3490
3491                                 memcpy(&localBuffer[start],buffer,nToCopy);
3492
3493 #ifdef CONFIG_YAFFS_WINCE
3494                                 yfsd_LockYAFFS(TRUE);
3495 #endif
3496                                 chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,localBuffer,nToWriteBack,0);
3497
3498                                 yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
3499
3500                                 //T(("Write with readback to chunk %d %d  start %d  copied %d wrote back %d\n",chunk,chunkWritten,start, nToCopy, nToWriteBack));
3501                         }
3502
3503                 }
3504                 else
3505                 {
3506
3507 #ifdef CONFIG_YAFFS_WINCE
3508                         // Under WinCE can't do direct transfer. Need to use a local buffer.
3509                         // This is because we otherwise screw up WinCE's memory mapper
3510                                 __u8 *localBuffer = yaffs_GetTempBuffer(dev,__LINE__);
3511 #ifdef CONFIG_YAFFS_WINCE
3512                                 yfsd_UnlockYAFFS(TRUE);
3513 #endif
3514                         memcpy(localBuffer,buffer,dev->nBytesPerChunk);
3515 #ifdef CONFIG_YAFFS_WINCE
3516                                 yfsd_LockYAFFS(TRUE);
3517 #endif
3518                         chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,localBuffer,dev->nBytesPerChunk,0);
3519                         yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
3520 #else
3521                         // A full chunk. Write directly from the supplied buffer.
3522                         chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,buffer,dev->nBytesPerChunk,0);
3523 #endif
3524                         // Since we've overwritten the cached data, we better invalidate it.
3525                         yaffs_InvalidateChunkCache(in,chunk);
3526                         //T(("Write to chunk %d %d\n",chunk,chunkWritten));
3527                 }
3528
3529                 if(chunkWritten >= 0)
3530                 {
3531                         n -= nToCopy;
3532                         offset += nToCopy;
3533                         buffer += nToCopy;
3534                         nDone += nToCopy;
3535                 }
3536
3537         }
3538
3539         // Update file object
3540
3541         if((startOfWrite + nDone) > in->variant.fileVariant.fileSize)
3542         {
3543                 in->variant.fileVariant.fileSize = (startOfWrite + nDone);
3544         }
3545
3546         in->dirty = 1;
3547
3548         return nDone;
3549 }
3550
3551 static void yaffs_PruneResizedChunks(yaffs_Object *in, int newSize)
3552 {
3553
3554         yaffs_Device *dev = in->myDev;
3555         int oldFileSize = in->variant.fileVariant.fileSize;
3556
3557
3558         int lastDel = 1 + (oldFileSize-1)/dev->nBytesPerChunk;
3559
3560         int startDel = 1 + (newSize + dev->nBytesPerChunk - 1)/
3561                                                 dev->nBytesPerChunk;
3562         int i;
3563         int chunkId;
3564
3565         // Delete backwards so that we don't end up with holes if
3566         // power is lost part-way through the operation.
3567         for(i = lastDel; i >= startDel; i--)
3568         {
3569                 // NB this could be optimised somewhat,
3570                 // eg. could retrieve the tags and write them without
3571                 // using yaffs_DeleteChunk
3572
3573                 chunkId = yaffs_FindAndDeleteChunkInFile(in,i,NULL);
3574                 if(chunkId > 0)
3575                 {
3576                         if(chunkId < (dev->internalStartBlock * dev->nChunksPerBlock) ||
3577                        chunkId >= ((dev->internalEndBlock+1) * dev->nChunksPerBlock))
3578                         {
3579                                 T(YAFFS_TRACE_ALWAYS,(TSTR("Found daft chunkId %d for %d"TENDSTR),chunkId,i));
3580                         }
3581                         else
3582                         {
3583                                 in->nDataChunks--;
3584                                 yaffs_DeleteChunk(dev,chunkId,1,__LINE__);
3585                         }
3586                 }
3587         }
3588
3589 }
3590
3591 int yaffs_ResizeFile(yaffs_Object *in, int newSize)
3592 {
3593
3594         int oldFileSize = in->variant.fileVariant.fileSize;
3595         int sizeOfPartialChunk;
3596         yaffs_Device *dev = in->myDev;
3597
3598          sizeOfPartialChunk  = newSize % dev->nBytesPerChunk;
3599
3600
3601         yaffs_FlushFilesChunkCache(in);
3602         yaffs_InvalidateWholeChunkCache(in);
3603
3604         yaffs_CheckGarbageCollection(dev);
3605
3606         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
3607         {
3608                 return yaffs_GetFileSize(in);
3609         }
3610
3611         if(newSize == oldFileSize)
3612         {
3613                 return oldFileSize;
3614         }
3615
3616         if(newSize < oldFileSize)
3617         {
3618
3619                 yaffs_PruneResizedChunks(in,newSize);
3620
3621                 if(sizeOfPartialChunk != 0)
3622                 {
3623                         int lastChunk = 1+ newSize/dev->nBytesPerChunk;
3624                         __u8 *localBuffer = yaffs_GetTempBuffer(dev,__LINE__);
3625
3626                         // Got to read and rewrite the last chunk with its new size and zero pad
3627                         yaffs_ReadChunkDataFromObject(in,lastChunk,localBuffer);
3628
3629                         memset(localBuffer + sizeOfPartialChunk,0, dev->nBytesPerChunk - sizeOfPartialChunk);
3630
3631                         yaffs_WriteChunkDataToObject(in,lastChunk,localBuffer,sizeOfPartialChunk,1);
3632
3633                         yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
3634                 }
3635
3636                 in->variant.fileVariant.fileSize = newSize;
3637
3638                 yaffs_PruneFileStructure(dev,&in->variant.fileVariant);
3639         }
3640
3641         // Write a new object header.
3642         // show we've shrunk the file, if need be
3643         // Do this only if the file is not in the deleted directories.
3644         if(in->parent->objectId != YAFFS_OBJECTID_UNLINKED &&
3645            in->parent->objectId != YAFFS_OBJECTID_DELETED
3646           )
3647         {
3648                 yaffs_UpdateObjectHeader(in,NULL, 0, (newSize < oldFileSize) ? 1 : 0 ,0);
3649         }
3650
3651
3652         return newSize;
3653 }
3654
3655
3656 loff_t yaffs_GetFileSize(yaffs_Object *obj)
3657 {
3658         obj = yaffs_GetEquivalentObject(obj);
3659
3660         switch(obj->variantType)
3661         {
3662                 case YAFFS_OBJECT_TYPE_FILE:
3663                         return obj->variant.fileVariant.fileSize;
3664                 case YAFFS_OBJECT_TYPE_SYMLINK:
3665                         return yaffs_strlen(obj->variant.symLinkVariant.alias);
3666                 default:
3667                         return 0;
3668         }
3669 }
3670
3671
3672
3673 // yaffs_FlushFile() updates the file's
3674 // objectId in NAND
3675
3676 int yaffs_FlushFile(yaffs_Object *in, int updateTime)
3677 {
3678         int retVal;
3679         if(in->dirty)
3680         {
3681                 //T(("flushing object header\n"));
3682
3683                 yaffs_FlushFilesChunkCache(in);
3684                 if(updateTime)
3685                 {
3686 #ifdef CONFIG_YAFFS_WINCE
3687                         yfsd_WinFileTimeNow(in->win_mtime);
3688 #else
3689
3690                         in->yst_mtime = Y_CURRENT_TIME;
3691
3692 #endif
3693                 }
3694
3695                 retVal = (yaffs_UpdateObjectHeader(in,NULL,0,0,0) >= 0)? YAFFS_OK : YAFFS_FAIL;
3696         }
3697         else
3698         {
3699                 retVal = YAFFS_OK;
3700         }
3701
3702         return retVal;
3703
3704 }
3705
3706
3707 static int yaffs_DoGenericObjectDeletion(yaffs_Object *in)
3708 {
3709
3710         // First off, invalidate the file's data in the cache, without flushing.
3711         yaffs_InvalidateWholeChunkCache(in);
3712
3713         if(in->myDev->isYaffs2 && (in->parent != in->myDev->deletedDir))
3714         {
3715                 // Move to the unlinked directory so we have a record that it was deleted.
3716                 yaffs_ChangeObjectName(in, in->myDev->deletedDir,NULL,0,0);
3717
3718         }
3719
3720
3721         yaffs_RemoveObjectFromDirectory(in);
3722         yaffs_DeleteChunk(in->myDev,in->chunkId,1,__LINE__);
3723         in->chunkId = -1;
3724
3725         yaffs_FreeObject(in);
3726         return YAFFS_OK;
3727
3728 }
3729
3730 // yaffs_DeleteFile deletes the whole file data
3731 // and the inode associated with the file.
3732 // It does not delete the links associated with the file.
3733 static int yaffs_UnlinkFile(yaffs_Object *in)
3734 {
3735
3736
3737         int retVal;
3738         int immediateDeletion=0;
3739
3740         if(1)
3741         {
3742                 //in->unlinked = 1;
3743                 //in->myDev->nUnlinkedFiles++;
3744                 //in->renameAllowed = 0;
3745 #ifdef __KERNEL__
3746                 if(!in->myInode)
3747                 {
3748                         immediateDeletion = 1;
3749
3750                 }
3751 #else
3752                 if(in->inUse <= 0)
3753                 {
3754                         immediateDeletion = 1;
3755
3756                 }
3757 #endif
3758                 if(immediateDeletion)
3759                 {
3760                         retVal = yaffs_ChangeObjectName(in, in->myDev->deletedDir,NULL,0,0);
3761                         T(YAFFS_TRACE_TRACING,(TSTR("yaffs: immediate deletion of file %d" TENDSTR),in->objectId));
3762                         in->deleted=1;
3763                         in->myDev->nDeletedFiles++;
3764                         if( 0 && in->myDev->isYaffs2)
3765                         {
3766                                 yaffs_ResizeFile(in,0);
3767                         }
3768                         yaffs_SoftDeleteFile(in);
3769                 }
3770                 else
3771                 {
3772                         retVal = yaffs_ChangeObjectName(in, in->myDev->unlinkedDir,NULL,0,0);
3773                 }
3774
3775         }
3776         return retVal;
3777 }
3778
3779 int yaffs_DeleteFile(yaffs_Object *in)
3780 {
3781         int retVal = YAFFS_OK;
3782
3783         if(in->nDataChunks > 0)
3784         {
3785                 // Use soft deletion
3786                 if(!in->unlinked)
3787                 {
3788                         retVal = yaffs_UnlinkFile(in);
3789                 }
3790                 if(retVal == YAFFS_OK &&
3791                 in->unlinked &&
3792                 !in->deleted)
3793                 {
3794                         in->deleted = 1;
3795                         in->myDev->nDeletedFiles++;
3796                         yaffs_SoftDeleteFile(in);
3797                 }
3798                 return in->deleted ? YAFFS_OK : YAFFS_FAIL;
3799         }
3800         else
3801         {
3802                 // The file has no data chunks so we toss it immediately
3803                 yaffs_FreeTnode(in->myDev,in->variant.fileVariant.top);
3804                 in->variant.fileVariant.top = NULL;
3805                 yaffs_DoGenericObjectDeletion(in);
3806
3807                 return YAFFS_OK;
3808         }
3809 }
3810
3811 static int yaffs_DeleteDirectory(yaffs_Object *in)
3812 {
3813         //First check that the directory is empty.
3814         if(list_empty(&in->variant.directoryVariant.children))
3815         {
3816                 return  yaffs_DoGenericObjectDeletion(in);
3817         }
3818
3819         return YAFFS_FAIL;
3820
3821 }
3822
3823 static int yaffs_DeleteSymLink(yaffs_Object *in)
3824 {
3825         YFREE(in->variant.symLinkVariant.alias);
3826
3827         return  yaffs_DoGenericObjectDeletion(in);
3828 }
3829
3830 static int yaffs_DeleteHardLink(yaffs_Object *in)
3831 {
3832         // remove this hardlink from the list assocaited with the equivalent
3833         // object
3834         list_del(&in->hardLinks);
3835         return  yaffs_DoGenericObjectDeletion(in);
3836 }
3837
3838
3839 static void yaffs_DestroyObject(yaffs_Object *obj)
3840 {
3841         switch(obj->variantType)
3842         {
3843                 case YAFFS_OBJECT_TYPE_FILE: yaffs_DeleteFile(obj); break;
3844                 case YAFFS_OBJECT_TYPE_DIRECTORY: yaffs_DeleteDirectory(obj); break;
3845                 case YAFFS_OBJECT_TYPE_SYMLINK: yaffs_DeleteSymLink(obj); break;
3846                 case YAFFS_OBJECT_TYPE_HARDLINK: yaffs_DeleteHardLink(obj); break;
3847                 case YAFFS_OBJECT_TYPE_SPECIAL: yaffs_DoGenericObjectDeletion(obj); break;
3848                 case YAFFS_OBJECT_TYPE_UNKNOWN: break; // should not happen.
3849         }
3850 }
3851
3852
3853 static int yaffs_UnlinkWorker(yaffs_Object *obj)
3854 {
3855
3856
3857         if(obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
3858         {
3859                 return  yaffs_DeleteHardLink(obj);
3860         }
3861         else if(!list_empty(&obj->hardLinks))
3862         {
3863                 // Curve ball: We're unlinking an object that has a hardlink.
3864                 //
3865                 //      This problem arises because we are not strictly following
3866                 //  The Linux link/inode model.
3867                 //
3868                 // We can't really delete the object.
3869                 // Instead, we do the following:
3870                 // - Select a hardlink.
3871                 // - Unhook it from the hard links
3872                 // - Unhook it from its parent directory (so that the rename can work)
3873                 // - Rename the object to the hardlink's name.
3874                 // - Delete the hardlink
3875
3876
3877                 yaffs_Object *hl;
3878                 int retVal;
3879                 YCHAR name[YAFFS_MAX_NAME_LENGTH+1];
3880
3881                 hl = list_entry(obj->hardLinks.next,yaffs_Object,hardLinks);
3882
3883                 list_del_init(&hl->hardLinks);
3884                 list_del_init(&hl->siblings);
3885
3886                 yaffs_GetObjectName(hl,name,YAFFS_MAX_NAME_LENGTH+1);
3887
3888                 retVal = yaffs_ChangeObjectName(obj, hl->parent, name,0,0);
3889
3890                 if(retVal == YAFFS_OK)
3891                 {
3892                         retVal = yaffs_DoGenericObjectDeletion(hl);
3893                 }
3894                 return retVal;
3895
3896         }
3897         else
3898         {
3899                 switch(obj->variantType)
3900                 {
3901                         case YAFFS_OBJECT_TYPE_FILE:
3902                                 return yaffs_UnlinkFile(obj);
3903                                 break;
3904                         case YAFFS_OBJECT_TYPE_DIRECTORY:
3905                                 return yaffs_DeleteDirectory(obj);
3906                                 break;
3907                         case YAFFS_OBJECT_TYPE_SYMLINK:
3908                                 return yaffs_DeleteSymLink(obj);
3909                                 break;
3910                         case YAFFS_OBJECT_TYPE_SPECIAL:
3911                                 return yaffs_DoGenericObjectDeletion(obj);
3912                                 break;
3913                         case YAFFS_OBJECT_TYPE_HARDLINK:
3914                         case YAFFS_OBJECT_TYPE_UNKNOWN:
3915                         default:
3916                                 return YAFFS_FAIL;
3917                 }
3918         }
3919 }
3920
3921 int yaffs_Unlink(yaffs_Object *dir, const YCHAR *name)
3922 {
3923         yaffs_Object *obj;
3924
3925          obj = yaffs_FindObjectByName(dir,name);
3926
3927          if(obj && obj->unlinkAllowed)
3928          {
3929                 return yaffs_UnlinkWorker(obj);
3930          }
3931
3932          return YAFFS_FAIL;
3933
3934 }
3935
3936 //////////////// Initialisation Scanning /////////////////
3937
3938
3939 static void yaffs_HandleShadowedObject(yaffs_Device *dev, int objId, int backwardScanning)
3940 {
3941         yaffs_Object *obj;
3942
3943         if(!backwardScanning)
3944         {
3945                 // Handle YAFFS1 forward scanning case
3946                 // For YAFFS1 we always do the deletion
3947
3948         }
3949         else
3950         {       // Handle YAFFS2 case (backward scanning)
3951                 // If the shadowed object exists then ignore.
3952                 if(yaffs_FindObjectByNumber(dev,objId))
3953                 {
3954                         return;
3955                 }
3956         }
3957
3958         // Let's create it (if it does not exist) assuming it is a file so that it can do shrinking etc.
3959         // We put it in unlinked dir to be cleaned up after the scanning
3960         obj = yaffs_FindOrCreateObjectByNumber(dev,objId,YAFFS_OBJECT_TYPE_FILE);
3961         yaffs_AddObjectToDirectory(dev->unlinkedDir,obj);
3962         obj->variant.fileVariant.shrinkSize = 0;
3963         obj->valid = 1; // So that we don't read any other infor for this file
3964
3965 }
3966
3967
3968
3969
3970 typedef struct
3971 {
3972         int seq;
3973         int block;
3974 } yaffs_BlockIndex;
3975
3976
3977
3978 static int yaffs_Scan(yaffs_Device *dev)
3979 {
3980         yaffs_ExtendedTags tags;
3981         int blk;
3982         int blockIterator;
3983         int startIterator;
3984         int endIterator;
3985         int nBlocksToScan = 0;
3986
3987         int chunk;
3988         int c;
3989         int deleted;
3990         yaffs_BlockState state;
3991         yaffs_Object *hardList = NULL;
3992         yaffs_Object *hl;
3993         yaffs_BlockInfo *bi;
3994         int sequenceNumber;
3995         yaffs_ObjectHeader *oh;
3996         yaffs_Object *in;
3997         yaffs_Object *parent;
3998         int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
3999
4000         __u8 *chunkData;
4001
4002         yaffs_BlockIndex *blockIndex = NULL;
4003
4004         T(YAFFS_TRACE_SCAN,(TSTR("yaffs_Scan starts  intstartblk %d intendblk %d..." TENDSTR),dev->internalStartBlock,dev->internalEndBlock));
4005
4006         chunkData = yaffs_GetTempBuffer(dev,__LINE__);
4007
4008
4009         dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
4010
4011         if(dev->isYaffs2)
4012         {
4013                 blockIndex = YMALLOC(nBlocks * sizeof(yaffs_BlockIndex));
4014         }
4015
4016
4017         // Scan all the blocks to determine their state
4018         for(blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++)
4019         {
4020                 bi = yaffs_GetBlockInfo(dev,blk);
4021                 yaffs_ClearChunkBits(dev,blk);
4022                 bi->pagesInUse = 0;
4023                 bi->softDeletions = 0;
4024
4025                 yaffs_QueryInitialBlockState(dev,blk,&state,&sequenceNumber);
4026
4027                 bi->blockState = state;
4028                 bi->sequenceNumber = sequenceNumber;
4029
4030                 T(YAFFS_TRACE_SCAN_DEBUG,(TSTR("Block scanning block %d state %d seq %d" TENDSTR),blk,state,sequenceNumber));
4031
4032                 if(state == YAFFS_BLOCK_STATE_DEAD)
4033                 {
4034                         T(YAFFS_TRACE_BAD_BLOCKS,(TSTR("block %d is bad" TENDSTR),blk));
4035                 }
4036                 else if(state == YAFFS_BLOCK_STATE_EMPTY)
4037                 {
4038                         T(YAFFS_TRACE_SCAN_DEBUG,(TSTR("Block empty " TENDSTR)));
4039                         dev->nErasedBlocks++;
4040                         dev->nFreeChunks += dev->nChunksPerBlock;
4041                 }
4042                 else if(state == YAFFS_BLOCK_STATE_NEEDS_SCANNING)
4043                 {
4044
4045                         // Determine the highest sequence number
4046                         if( dev->isYaffs2 &&
4047                             sequenceNumber >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
4048                             sequenceNumber < YAFFS_HIGHEST_SEQUENCE_NUMBER)
4049                          {
4050
4051                                 blockIndex[nBlocksToScan].seq = sequenceNumber;
4052                                 blockIndex[nBlocksToScan].block = blk;
4053
4054                                 nBlocksToScan++;
4055
4056                                 if(sequenceNumber >= dev->sequenceNumber)
4057                                 {
4058                                         dev->sequenceNumber = sequenceNumber;
4059                                 }
4060                         }
4061                         else if(dev->isYaffs2)
4062                         {
4063                                 // TODO: Nasty sequence number!
4064                                 T(YAFFS_TRACE_SCAN,(TSTR("Block scanning block %d has bad sequence number %d" TENDSTR),blk,sequenceNumber));
4065
4066                         }
4067                 }
4068         }
4069
4070         // Sort the blocks
4071         // Dungy old bubble sort for now...
4072         if(dev->isYaffs2)
4073         {
4074                 yaffs_BlockIndex temp;
4075                 int i;
4076                 int j;
4077
4078                 for(i = 0; i < nBlocksToScan; i++)
4079                         for(j = i+1; j < nBlocksToScan; j++)
4080                          if(blockIndex[i].seq > blockIndex[j].seq)
4081                          {
4082                                 temp = blockIndex[j];
4083                                 blockIndex[j] = blockIndex[i];
4084                                 blockIndex[i] = temp;
4085                          }
4086         }
4087
4088
4089         // Now scan the blocks looking at the data.
4090         if(dev->isYaffs2)
4091         {
4092                 startIterator = 0;
4093                 endIterator = nBlocksToScan-1;
4094                 T(YAFFS_TRACE_SCAN_DEBUG,(TSTR("%d blocks to be scanned" TENDSTR),nBlocksToScan));
4095         }
4096         else
4097         {
4098                 startIterator = dev->internalStartBlock;
4099                 endIterator = dev->internalEndBlock;
4100         }
4101
4102         // For each block....
4103         for(blockIterator = startIterator; blockIterator <= endIterator; blockIterator++)
4104         {
4105
4106                 if(dev->isYaffs2)
4107                 {
4108                         // get the block to scan in the correct order
4109                         blk = blockIndex[blockIterator].block;
4110                 }
4111                 else
4112                 {
4113                         blk = blockIterator;
4114                 }
4115
4116
4117                 bi = yaffs_GetBlockInfo(dev,blk);
4118                 state = bi->blockState;
4119
4120                 deleted = 0;
4121
4122                 // For each chunk in each block that needs scanning....
4123                 for(c = 0; c < dev->nChunksPerBlock &&
4124                                    state == YAFFS_BLOCK_STATE_NEEDS_SCANNING; c++)
4125                 {
4126                         // Read the tags and decide what to do
4127                         chunk = blk * dev->nChunksPerBlock + c;
4128
4129                         yaffs_ReadChunkWithTagsFromNAND(dev,chunk,NULL,&tags);
4130
4131                         // Let's have a good look at this chunk...
4132
4133
4134                         if(!dev->isYaffs2 && tags.chunkDeleted)
4135                         {
4136                                 // YAFFS1 only...
4137                                 // A deleted chunk
4138                                 deleted++;
4139                                 dev->nFreeChunks ++;
4140                                 //T((" %d %d deleted\n",blk,c));
4141                         }
4142                         else if(!tags.chunkUsed)
4143                         {
4144                                 // An unassigned chunk in the block
4145                                 // This means that either the block is empty or
4146                                 // this is the one being allocated from
4147
4148                                 if(c == 0)
4149                                 {
4150                                         // We're looking at the first chunk in the block so the block is unused
4151                                         state = YAFFS_BLOCK_STATE_EMPTY;
4152                                         dev->nErasedBlocks++;
4153                                 }
4154                                 else
4155                                 {
4156                                         // this is the block being allocated from
4157                                         T(YAFFS_TRACE_SCAN,(TSTR(" Allocating from %d %d" TENDSTR),blk,c));
4158                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
4159                                         dev->allocationBlock = blk;
4160                                         dev->allocationPage = c;
4161                                         dev->allocationBlockFinder = blk; // Set it to here to encourage the allocator to
4162                                                                                                           // go forth from here.
4163                                         //Yaffs2 sanity check:
4164                                         // This should be the one with the highest sequence number
4165                                         if(dev->isYaffs2 && (dev->sequenceNumber != bi->sequenceNumber))
4166                                         {
4167                                                 T(YAFFS_TRACE_ALWAYS,
4168                                                                 (TSTR("yaffs: Allocation block %d was not highest sequence id: block seq = %d, dev seq = %d" TENDSTR),
4169                                                                 blk,bi->sequenceNumber,dev->sequenceNumber));
4170                                         }
4171                                 }
4172
4173                                 dev->nFreeChunks += (dev->nChunksPerBlock - c);
4174                         }
4175                         else if(tags.chunkId > 0)
4176                         {
4177                                 // chunkId > 0 so it is a data chunk...
4178                                 unsigned int endpos;
4179
4180                                 yaffs_SetChunkBit(dev,blk,c);
4181                                 bi->pagesInUse++;
4182
4183                                 in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,YAFFS_OBJECT_TYPE_FILE);
4184                                 // PutChunkIntoFile checks for a clash (two data chunks with
4185                                 // the same chunkId).
4186                                 yaffs_PutChunkIntoFile(in,tags.chunkId,chunk,1);
4187                                 endpos = (tags.chunkId - 1)* dev->nBytesPerChunk + tags.byteCount;
4188                                 if(in->variantType == YAFFS_OBJECT_TYPE_FILE && in->variant.fileVariant.scannedFileSize <endpos)
4189                                 {
4190                                         in->variant.fileVariant.scannedFileSize = endpos;
4191                                         if(!dev->useHeaderFileSize)
4192                                         {
4193                                                         in->variant.fileVariant.fileSize = in->variant.fileVariant.scannedFileSize;
4194                                         }
4195
4196                                 }
4197                                 //T((" %d %d data %d %d\n",blk,c,tags.objectId,tags.chunkId));
4198                         }
4199                         else
4200                         {
4201                                 // chunkId == 0, so it is an ObjectHeader.
4202                                 // Thus, we read in the object header and make the object
4203                                 yaffs_SetChunkBit(dev,blk,c);
4204                                 bi->pagesInUse++;
4205
4206                                 yaffs_ReadChunkWithTagsFromNAND(dev,chunk,chunkData,NULL);
4207
4208                                 oh = (yaffs_ObjectHeader *)chunkData;
4209
4210                                 in = yaffs_FindObjectByNumber(dev,tags.objectId);
4211                                 if(in && in->variantType != oh->type)
4212                                 {
4213                                         // This should not happen, but somehow
4214                                         // Wev'e ended up with an objectId that has been reused but not yet
4215                                         // deleted, and worse still it has changed type. Delete the old object.
4216
4217                                         yaffs_DestroyObject(in);
4218
4219                                         in = 0;
4220                                 }
4221
4222                                 in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,oh->type);
4223
4224                                 if(oh->shadowsObject > 0)
4225                                 {
4226                                         yaffs_HandleShadowedObject(dev,oh->shadowsObject,0);
4227                                 }
4228
4229                                 if(in->valid)
4230                                 {
4231                                         // We have already filled this one. We have a duplicate and need to resolve it.
4232
4233                                         unsigned existingSerial = in->serial;
4234                                         unsigned newSerial = tags.serialNumber;
4235
4236                                         if( dev->isYaffs2 ||
4237                                             ((existingSerial+1) & 3) == newSerial)
4238                                         {
4239                                                 // Use new one - destroy the exisiting one
4240                                                 yaffs_DeleteChunk(dev,in->chunkId,1,__LINE__);
4241                                                 in->valid = 0;
4242                                         }
4243                                         else
4244                                         {
4245                                                 // Use existing - destroy this one.
4246                                                 yaffs_DeleteChunk(dev,chunk,1,__LINE__);
4247                                         }
4248                                 }
4249
4250                                 if(!in->valid &&
4251                                    (tags.objectId == YAFFS_OBJECTID_ROOT ||
4252                                     tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))
4253                                 {
4254                                         // We only load some info, don't fiddle with directory structure
4255                                         in->valid = 1;
4256                                         in->variantType = oh->type;
4257
4258                                         in->yst_mode  = oh->yst_mode;
4259 #ifdef CONFIG_YAFFS_WINCE
4260                                         in->win_atime[0] = oh->win_atime[0];
4261                                         in->win_ctime[0] = oh->win_ctime[0];
4262                                         in->win_mtime[0] = oh->win_mtime[0];
4263                                         in->win_atime[1] = oh->win_atime[1];
4264                                         in->win_ctime[1] = oh->win_ctime[1];
4265                                         in->win_mtime[1] = oh->win_mtime[1];
4266 #else
4267                                         in->yst_uid   = oh->yst_uid;
4268                                         in->yst_gid   = oh->yst_gid;
4269                                         in->yst_atime = oh->yst_atime;
4270                                         in->yst_mtime = oh->yst_mtime;
4271                                         in->yst_ctime = oh->yst_ctime;
4272                                         in->yst_rdev = oh->yst_rdev;
4273 #endif
4274                                         in->chunkId  = chunk;
4275
4276                                 }
4277                                 else if(!in->valid)
4278                                 {
4279                                         // we need to load this info
4280
4281                                         in->valid = 1;
4282                                         in->variantType = oh->type;
4283
4284                                         in->yst_mode  = oh->yst_mode;
4285 #ifdef CONFIG_YAFFS_WINCE
4286                                         in->win_atime[0] = oh->win_atime[0];
4287                                         in->win_ctime[0] = oh->win_ctime[0];
4288                                         in->win_mtime[0] = oh->win_mtime[0];
4289                                         in->win_atime[1] = oh->win_atime[1];
4290                                         in->win_ctime[1] = oh->win_ctime[1];
4291                                         in->win_mtime[1] = oh->win_mtime[1];
4292 #else
4293                                         in->yst_uid   = oh->yst_uid;
4294                                         in->yst_gid   = oh->yst_gid;
4295                                         in->yst_atime = oh->yst_atime;
4296                                         in->yst_mtime = oh->yst_mtime;
4297                                         in->yst_ctime = oh->yst_ctime;
4298                                         in->yst_rdev = oh->yst_rdev;
4299 #endif
4300                                         in->chunkId  = chunk;
4301
4302                                         yaffs_SetObjectName(in,oh->name);
4303                                         in->dirty = 0;
4304
4305                                         // directory stuff...
4306                                         // hook up to parent
4307
4308                                         parent = yaffs_FindOrCreateObjectByNumber(dev,oh->parentObjectId,YAFFS_OBJECT_TYPE_DIRECTORY);
4309                                         if(parent->variantType == YAFFS_OBJECT_TYPE_UNKNOWN)
4310                                         {
4311                                                 // Set up as a directory
4312                                                 parent->variantType = YAFFS_OBJECT_TYPE_DIRECTORY;
4313                                                 INIT_LIST_HEAD(&parent->variant.directoryVariant.children);
4314                                         }
4315                                         else if(parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
4316                                         {
4317                                                 // Hoosterman, another problem....
4318                                                 // We're trying to use a non-directory as a directory
4319
4320                                                 T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found." TENDSTR)));
4321                                                 parent = dev->lostNFoundDir;
4322                                         }
4323
4324                                         yaffs_AddObjectToDirectory(parent,in);
4325
4326                                         if(0 && (parent == dev->deletedDir ||
4327                                            parent == dev->unlinkedDir))
4328                                         {
4329                                                 in->deleted = 1; // If it is unlinked at start up then it wants deleting
4330                                                 dev->nDeletedFiles++;
4331                                         }
4332
4333                                         // Note re hardlinks.
4334                                         // Since we might scan a hardlink before its equivalent object is scanned
4335                                         // we put them all in a list.
4336                                         // After scanning is complete, we should have all the objects, so we run through this
4337                                         // list and fix up all the chains.
4338
4339                                         switch(in->variantType)
4340                                         {
4341                                                 case YAFFS_OBJECT_TYPE_UNKNOWN:         // Todo got a problem
4342                                                         break;
4343                                                 case YAFFS_OBJECT_TYPE_FILE:
4344                                                         if(dev->isYaffs2 && oh->isShrink)
4345                                                         {
4346                                                                 // Prune back the shrunken chunks
4347                                                                 yaffs_PruneResizedChunks(in,oh->fileSize);
4348                                                                 // Mark the block as having a shrinkHeader
4349                                                                 bi->hasShrinkHeader = 1;
4350                                                         }
4351
4352                                                         if(dev->useHeaderFileSize)
4353
4354                                                                 in->variant.fileVariant.fileSize = oh->fileSize;
4355
4356                                                         break;
4357                                                 case YAFFS_OBJECT_TYPE_HARDLINK:
4358                                                         in->variant.hardLinkVariant.equivalentObjectId = oh->equivalentObjectId;
4359                                                         in->hardLinks.next = (struct list_head *)hardList;
4360                                                         hardList = in;
4361                                                         break;
4362                                                 case YAFFS_OBJECT_TYPE_DIRECTORY:       // Do nothing
4363                                                         break;
4364                                                 case YAFFS_OBJECT_TYPE_SPECIAL: // Do nothing
4365                                                         break;
4366                                                 case YAFFS_OBJECT_TYPE_SYMLINK:         // Do nothing
4367                                                         in->variant.symLinkVariant.alias = yaffs_CloneString(oh->alias);
4368                                                         break;
4369                                         }
4370
4371                                         if(parent == dev->deletedDir)
4372                                         {
4373                                                 yaffs_DestroyObject(in);
4374                                                 bi->hasShrinkHeader = 1;
4375                                         }
4376                                         //T((" %d %d header %d \"%s\" type %d\n",blk,c,tags.objectId,oh->name,in->variantType));
4377                                 }
4378                         }
4379                 }
4380
4381                 if(state == YAFFS_BLOCK_STATE_NEEDS_SCANNING)
4382                 {
4383                         // If we got this far while scanning, then the block is fully allocated.
4384                         state = YAFFS_BLOCK_STATE_FULL;
4385                 }
4386
4387                 bi->blockState = state;
4388
4389                 // Now let's see if it was dirty
4390                 if(     bi->pagesInUse == 0 &&
4391                         !bi->hasShrinkHeader &&
4392                 bi->blockState == YAFFS_BLOCK_STATE_FULL)
4393             {
4394                 yaffs_BlockBecameDirty(dev,blk);
4395             }
4396
4397         }
4398
4399         if(blockIndex)
4400         {
4401                 YFREE(blockIndex);
4402         }
4403
4404         // Ok, we've done all the scanning.
4405
4406         // Fix up the hard link chains.
4407         // We should now have scanned all the objects, now it's time to add these
4408         // hardlinks.
4409         while(hardList)
4410         {
4411                 hl = hardList;
4412                 hardList = (yaffs_Object *)(hardList->hardLinks.next);
4413
4414                 in = yaffs_FindObjectByNumber(dev,hl->variant.hardLinkVariant.equivalentObjectId);
4415
4416                 if(in)
4417                 {
4418                         // Add the hardlink pointers
4419                         hl->variant.hardLinkVariant.equivalentObject=in;
4420                         list_add(&hl->hardLinks,&in->hardLinks);
4421                 }
4422                 else
4423                 {
4424                         //Todo Need to report/handle this better.
4425                         // Got a problem... hardlink to a non-existant object
4426                         hl->variant.hardLinkVariant.equivalentObject=NULL;
4427                         INIT_LIST_HEAD(&hl->hardLinks);
4428
4429                 }
4430
4431         }
4432
4433         // Handle the unlinked files. Since they were left in an unlinked state we should
4434         // just delete them.
4435         {
4436                 struct list_head *i;
4437                 struct list_head *n;
4438
4439                 yaffs_Object *l;
4440                 // Soft delete all the unlinked files
4441                 list_for_each_safe(i,n,&dev->unlinkedDir->variant.directoryVariant.children)
4442                 {
4443                         if(i)
4444                         {
4445                                 l = list_entry(i, yaffs_Object,siblings);
4446                                 yaffs_DestroyObject(l);
4447                         }
4448                 }
4449         }
4450
4451         yaffs_ReleaseTempBuffer(dev,chunkData,__LINE__);
4452
4453         T(YAFFS_TRACE_SCAN,(TSTR("yaffs_Scan ends" TENDSTR)));
4454
4455         return YAFFS_OK;
4456 }
4457
4458
4459 static int yaffs_ScanBackwards(yaffs_Device *dev)
4460 {
4461         yaffs_ExtendedTags tags;
4462         int blk;
4463         int blockIterator;
4464         int startIterator;
4465         int endIterator;
4466         int nBlocksToScan = 0;
4467
4468         int chunk;
4469         int c;
4470         int deleted;
4471         yaffs_BlockState state;
4472         yaffs_Object *hardList = NULL;
4473         yaffs_Object *hl;
4474         yaffs_BlockInfo *bi;
4475         int sequenceNumber;
4476         yaffs_ObjectHeader *oh;
4477         yaffs_Object *in;
4478         yaffs_Object *parent;
4479         int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
4480
4481         __u8 *chunkData;
4482
4483         yaffs_BlockIndex *blockIndex = NULL;
4484
4485
4486         if(!dev->isYaffs2)
4487         {
4488                 T(YAFFS_TRACE_SCAN,(TSTR("yaffs_ScanBackwards is only for YAFFS2!" TENDSTR)));
4489                 return YAFFS_FAIL;
4490         }
4491
4492         T(YAFFS_TRACE_SCAN,(TSTR("yaffs_ScanBackwards starts  intstartblk %d intendblk %d..." TENDSTR),dev->internalStartBlock,dev->internalEndBlock));
4493
4494         chunkData = yaffs_GetTempBuffer(dev,__LINE__);
4495
4496
4497         dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
4498
4499         blockIndex = YMALLOC(nBlocks * sizeof(yaffs_BlockIndex));
4500
4501
4502         // Scan all the blocks to determine their state
4503         for(blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++)
4504         {
4505                 bi = yaffs_GetBlockInfo(dev,blk);
4506                 yaffs_ClearChunkBits(dev,blk);
4507                 bi->pagesInUse = 0;
4508                 bi->softDeletions = 0;
4509
4510                 yaffs_QueryInitialBlockState(dev,blk,&state,&sequenceNumber);
4511
4512                 bi->blockState = state;
4513                 bi->sequenceNumber = sequenceNumber;
4514
4515                 T(YAFFS_TRACE_SCAN_DEBUG,(TSTR("Block scanning block %d state %d seq %d" TENDSTR),blk,state,sequenceNumber));
4516
4517                 if(state == YAFFS_BLOCK_STATE_DEAD)
4518                 {
4519                         T(YAFFS_TRACE_BAD_BLOCKS,(TSTR("block %d is bad" TENDSTR),blk));
4520                 }
4521                 else if(state == YAFFS_BLOCK_STATE_EMPTY)
4522                 {
4523                         T(YAFFS_TRACE_SCAN_DEBUG,(TSTR("Block empty " TENDSTR)));
4524                         dev->nErasedBlocks++;
4525                         dev->nFreeChunks += dev->nChunksPerBlock;
4526                 }
4527                 else if(state == YAFFS_BLOCK_STATE_NEEDS_SCANNING)
4528                 {
4529
4530                         // Determine the highest sequence number
4531                         if( dev->isYaffs2 &&
4532                             sequenceNumber >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
4533                             sequenceNumber < YAFFS_HIGHEST_SEQUENCE_NUMBER)
4534                          {
4535
4536                                 blockIndex[nBlocksToScan].seq = sequenceNumber;
4537                                 blockIndex[nBlocksToScan].block = blk;
4538
4539                                 nBlocksToScan++;
4540
4541                                 if(sequenceNumber >= dev->sequenceNumber)
4542                                 {
4543                                         dev->sequenceNumber = sequenceNumber;
4544                                 }
4545                         }
4546                         else if(dev->isYaffs2)
4547                         {
4548                                 // TODO: Nasty sequence number!
4549                                 T(YAFFS_TRACE_SCAN,(TSTR("Block scanning block %d has bad sequence number %d" TENDSTR),blk,sequenceNumber));
4550
4551                         }
4552                 }
4553         }
4554
4555         // Sort the blocks
4556         // Dungy old bubble sort for now...
4557         {
4558                 yaffs_BlockIndex temp;
4559                 int i;
4560                 int j;
4561
4562                 for(i = 0; i < nBlocksToScan; i++)
4563                         for(j = i+1; j < nBlocksToScan; j++)
4564                          if(blockIndex[i].seq > blockIndex[j].seq)
4565                          {
4566                                 temp = blockIndex[j];
4567                                 blockIndex[j] = blockIndex[i];
4568                                 blockIndex[i] = temp;
4569                          }
4570         }
4571
4572
4573         // Now scan the blocks looking at the data.
4574         startIterator = 0;
4575         endIterator = nBlocksToScan-1;
4576         T(YAFFS_TRACE_SCAN_DEBUG,(TSTR("%d blocks to be scanned" TENDSTR),nBlocksToScan));
4577
4578
4579         // For each block.... backwards
4580         for(blockIterator = endIterator; blockIterator >= startIterator; blockIterator--)
4581         {
4582
4583                 // get the block to scan in the correct order
4584                 blk = blockIndex[blockIterator].block;
4585
4586
4587                 bi = yaffs_GetBlockInfo(dev,blk);
4588                 state = bi->blockState;
4589
4590                 deleted = 0;
4591
4592                 if( 0 && // Disable since this is redundant.
4593                     state == YAFFS_BLOCK_STATE_NEEDS_SCANNING)
4594                 {
4595                         // Let's look at the first chunk in the block
4596                         chunk = blk * dev->nChunksPerBlock;
4597
4598                         yaffs_ReadChunkWithTagsFromNAND(dev,chunk,NULL,&tags);
4599
4600                         // Let's have a good look at this chunk...
4601
4602                         if(!tags.chunkUsed)
4603                         {
4604                                 // An unassigned chunk in the block
4605                                 // This means that either the block is empty or
4606                                 // this is the one being allocated from
4607
4608                                 // We're looking at the first chunk in the block so the block is unused
4609                                 state = YAFFS_BLOCK_STATE_EMPTY;
4610                                 dev->nErasedBlocks++;
4611                                 dev->nFreeChunks += dev->nChunksPerBlock;
4612                         }
4613
4614                 }
4615
4616                 // For each chunk in each block that needs scanning....
4617                 for(c = dev->nChunksPerBlock-1; c >= 0 &&
4618                                   (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
4619                                    state == YAFFS_BLOCK_STATE_ALLOCATING); c--)
4620                 {
4621                         // Scan backwards...
4622                         // Read the tags and decide what to do
4623                         chunk = blk * dev->nChunksPerBlock + c;
4624
4625                         yaffs_ReadChunkWithTagsFromNAND(dev,chunk,NULL,&tags);
4626
4627                         // Let's have a good look at this chunk...
4628
4629                         if(!tags.chunkUsed)
4630                         {
4631                                 // An unassigned chunk in the block
4632                                 // This means that either the block is empty or
4633                                 // this is the one being allocated from
4634
4635                                 if(c == 0)
4636                                 {
4637                                         // We're looking at the first chunk in the block so the block is unused
4638                                         state = YAFFS_BLOCK_STATE_EMPTY;
4639                                         dev->nErasedBlocks++;
4640                                 }
4641                                 else
4642                                 {
4643                                         // this is the block being allocated from
4644                                         if(state == YAFFS_BLOCK_STATE_NEEDS_SCANNING)
4645                                         {
4646                                           T(YAFFS_TRACE_SCAN,(TSTR(" Allocating from %d %d" TENDSTR),blk,c));
4647                                         }
4648                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
4649                                         dev->allocationBlock = blk;
4650                                         dev->allocationPage = c;
4651                                         dev->allocationBlockFinder = blk; // Set it to here to encourage the allocator to
4652                                                                                                           // go forth from here.
4653                                         //Yaffs2 sanity check:
4654                                         // This should be the one with the highest sequence number
4655                                         if(dev->isYaffs2 && (dev->sequenceNumber != bi->sequenceNumber))
4656                                         {
4657                                                 T(YAFFS_TRACE_ALWAYS,
4658                                                                 (TSTR("yaffs: Allocation block %d was not highest sequence id: block seq = %d, dev seq = %d" TENDSTR),
4659                                                                 blk,bi->sequenceNumber,dev->sequenceNumber));
4660                                         }
4661                                 }
4662
4663                                 dev->nFreeChunks ++;
4664                         }
4665                         else if(tags.chunkId > 0)
4666                         {
4667                                 // chunkId > 0 so it is a data chunk...
4668                                 unsigned int endpos;
4669
4670                                 __u32 chunkBase = (tags.chunkId - 1)* dev->nBytesPerChunk;
4671
4672                                 yaffs_SetChunkBit(dev,blk,c);
4673                                 bi->pagesInUse++;
4674
4675                                 in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,YAFFS_OBJECT_TYPE_FILE);
4676                                 if(in->variantType == YAFFS_OBJECT_TYPE_FILE &&
4677                                    chunkBase < in->variant.fileVariant.shrinkSize)
4678                                 {
4679                                         // This has not been invalidated by a resize
4680                                         yaffs_PutChunkIntoFile(in,tags.chunkId,chunk,-1);
4681
4682
4683                                         // File size is calculated by looking at the data chunks if we have not
4684                                         // seen an object header yet. Stop this practice once we find an object header.
4685                                         endpos = (tags.chunkId - 1)* dev->nBytesPerChunk + tags.byteCount;
4686                                         if(!in->valid && // have not got an object header yet
4687                                            in->variant.fileVariant.scannedFileSize <endpos)
4688                                         {
4689                                                 in->variant.fileVariant.scannedFileSize = endpos;
4690                                                 in->variant.fileVariant.fileSize = in->variant.fileVariant.scannedFileSize;
4691                                         }
4692
4693                                 }
4694                                 else
4695                                 {
4696                                         // This chunk has been invalidated by a resize, so delete
4697                                         yaffs_DeleteChunk(dev,chunk,1,__LINE__);
4698
4699
4700                                 }
4701                                 //T((" %d %d data %d %d\n",blk,c,tags.objectId,tags.chunkId));
4702                         }
4703                         else
4704                         {
4705                                 // chunkId == 0, so it is an ObjectHeader.
4706                                 // Thus, we read in the object header and make the object
4707                                 yaffs_SetChunkBit(dev,blk,c);
4708                                 bi->pagesInUse++;
4709
4710                                 oh = NULL;
4711                                 in = NULL;
4712
4713                                 if(tags.extraHeaderInfoAvailable)
4714                                 {
4715                                         in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,tags.extraObjectType);
4716                                 }
4717
4718
4719                                 if(!in || !in->valid)
4720                                 {
4721
4722                                         // If we don't have  valid info then we need to read the chunk
4723                                         // TODO In future we can probably defer reading the chunk and
4724                                         // living with invalid data until needed.
4725
4726                                         yaffs_ReadChunkWithTagsFromNAND(dev,chunk,chunkData,NULL);
4727
4728                                         oh = (yaffs_ObjectHeader *)chunkData;
4729
4730                                         if(!in)
4731                                            in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,oh->type);
4732
4733                                 }
4734
4735                                 if(!in)
4736                                 {
4737                                         // TODO Hoosterman we have a problem!
4738                                         T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: Could not make object for object  %d  at chunk %d during scan" TENDSTR),tags.objectId,chunk));
4739
4740                                 }
4741
4742                                 if(in->valid)
4743                                 {
4744                                         // We have already filled this one. We have a duplicate that will be discarded, but
4745                                         // we first have to suck out resize info if it is a file.
4746
4747                                         if( (in->variantType == YAFFS_OBJECT_TYPE_FILE) &&
4748                                             ((oh && oh->type == YAFFS_OBJECT_TYPE_FILE) ||
4749                                             (tags.extraHeaderInfoAvailable && tags.extraObjectType == YAFFS_OBJECT_TYPE_FILE))
4750                                            )
4751                                         {
4752                                                 __u32 thisSize = (oh) ? oh->fileSize : tags.extraFileLength;
4753                                                 __u32 parentObjectId = (oh) ? oh->parentObjectId : tags.extraParentObjectId;
4754                                                 unsigned isShrink = (oh)  ? oh->isShrink : tags.extraIsShrinkHeader;
4755
4756                                                 // If it is deleted (unlinked at start also means deleted)
4757                                                 // we treat the file size as being zeroed at this point.
4758                                                 if(parentObjectId == YAFFS_OBJECTID_DELETED ||
4759                                                    parentObjectId == YAFFS_OBJECTID_UNLINKED)
4760                                                 {
4761                                                         thisSize = 0;
4762                                                         isShrink = 1;
4763                                                 }
4764
4765                                                 if(isShrink &&
4766                                                    in->variant.fileVariant.shrinkSize > thisSize)
4767                                                 {
4768                                                         in->variant.fileVariant.shrinkSize = thisSize;
4769                                                 }
4770
4771                                                 if(isShrink)
4772                                                 {
4773                                                         bi->hasShrinkHeader = 1;
4774                                                 }
4775
4776                                         }
4777                                         // Use existing - destroy this one.
4778                                         yaffs_DeleteChunk(dev,chunk,1,__LINE__);
4779
4780                                 }
4781
4782                                 if(!in->valid &&
4783                                    (tags.objectId == YAFFS_OBJECTID_ROOT ||
4784                                     tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))
4785                                 {
4786                                         // We only load some info, don't fiddle with directory structure
4787                                         in->valid = 1;
4788                                         in->variantType = oh->type;
4789
4790                                         in->yst_mode  = oh->yst_mode;
4791 #ifdef CONFIG_YAFFS_WINCE
4792                                         in->win_atime[0] = oh->win_atime[0];
4793                                         in->win_ctime[0] = oh->win_ctime[0];
4794                                         in->win_mtime[0] = oh->win_mtime[0];
4795                                         in->win_atime[1] = oh->win_atime[1];
4796                                         in->win_ctime[1] = oh->win_ctime[1];
4797                                         in->win_mtime[1] = oh->win_mtime[1];
4798 #else
4799                                         in->yst_uid   = oh->yst_uid;
4800                                         in->yst_gid   = oh->yst_gid;
4801                                         in->yst_atime = oh->yst_atime;
4802                                         in->yst_mtime = oh->yst_mtime;
4803                                         in->yst_ctime = oh->yst_ctime;
4804                                         in->yst_rdev = oh->yst_rdev;
4805 #endif
4806                                         in->chunkId  = chunk;
4807
4808                                 }
4809                                 else if(!in->valid)
4810                                 {
4811                                         // we need to load this info
4812
4813                                         in->valid = 1;
4814                                         in->variantType = oh->type;
4815
4816                                         in->yst_mode  = oh->yst_mode;
4817 #ifdef CONFIG_YAFFS_WINCE
4818                                         in->win_atime[0] = oh->win_atime[0];
4819                                         in->win_ctime[0] = oh->win_ctime[0];
4820                                         in->win_mtime[0] = oh->win_mtime[0];
4821                                         in->win_atime[1] = oh->win_atime[1];
4822                                         in->win_ctime[1] = oh->win_ctime[1];
4823                                         in->win_mtime[1] = oh->win_mtime[1];
4824 #else
4825                                         in->yst_uid   = oh->yst_uid;
4826                                         in->yst_gid   = oh->yst_gid;
4827                                         in->yst_atime = oh->yst_atime;
4828                                         in->yst_mtime = oh->yst_mtime;
4829                                         in->yst_ctime = oh->yst_ctime;
4830                                         in->yst_rdev = oh->yst_rdev;
4831 #endif
4832                                         in->chunkId  = chunk;
4833
4834                                         if(oh->shadowsObject > 0)
4835                                         {
4836                                                 yaffs_HandleShadowedObject(dev,oh->shadowsObject,1);
4837                                         }
4838
4839
4840                                         yaffs_SetObjectName(in,oh->name);
4841                                         in->dirty = 0;
4842
4843                                         // directory stuff...
4844                                         // hook up to parent
4845
4846                                         parent = yaffs_FindOrCreateObjectByNumber(dev,oh->parentObjectId,YAFFS_OBJECT_TYPE_DIRECTORY);
4847                                         if(parent->variantType == YAFFS_OBJECT_TYPE_UNKNOWN)
4848                                         {
4849                                                 // Set up as a directory
4850                                                 parent->variantType = YAFFS_OBJECT_TYPE_DIRECTORY;
4851                                                 INIT_LIST_HEAD(&parent->variant.directoryVariant.children);
4852                                         }
4853                                         else if(parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
4854                                         {
4855                                                 // Hoosterman, another problem....
4856                                                 // We're trying to use a non-directory as a directory
4857
4858                                                 T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found." TENDSTR)));
4859                                                 parent = dev->lostNFoundDir;
4860                                         }
4861
4862                                         yaffs_AddObjectToDirectory(parent,in);
4863
4864                                         if((parent == dev->deletedDir ||
4865                                            parent == dev->unlinkedDir))
4866                                         {
4867                                                 in->deleted = 1; // If it is unlinked at start up then it wants deleting
4868                                         }
4869
4870                                         if( oh->isShrink)
4871                                         {
4872                                                 // Mark the block as having a shrinkHeader
4873                                                 bi->hasShrinkHeader = 1;
4874                                         }
4875
4876
4877                                         // Note re hardlinks.
4878                                         // Since we might scan a hardlink before its equivalent object is scanned
4879                                         // we put them all in a list.
4880                                         // After scanning is complete, we should have all the objects, so we run through this
4881                                         // list and fix up all the chains.
4882
4883                                         switch(in->variantType)
4884                                         {
4885                                                 case YAFFS_OBJECT_TYPE_UNKNOWN:         // Todo got a problem
4886                                                         break;
4887                                                 case YAFFS_OBJECT_TYPE_FILE:
4888
4889
4890                                                         if(in->variant.fileVariant.scannedFileSize < oh->fileSize)
4891                                                         {
4892                                                                 // This covers the case where the file size is > than where the data is
4893                                                                 // This will happen if the file is resized to be larger than its current
4894                                                                 // data extents.
4895                                                                 in->variant.fileVariant.fileSize = oh->fileSize;
4896                                                                 in->variant.fileVariant.scannedFileSize = in->variant.fileVariant.fileSize;
4897                                                         }
4898
4899                                                         if(oh->isShrink &&
4900                                                            in->variant.fileVariant.shrinkSize > oh->fileSize)
4901                                                         {
4902                                                                 in->variant.fileVariant.shrinkSize = oh->fileSize;
4903                                                         }
4904
4905                                                         break;
4906                                                 case YAFFS_OBJECT_TYPE_HARDLINK:
4907                                                         in->variant.hardLinkVariant.equivalentObjectId = oh->equivalentObjectId;
4908                                                         in->hardLinks.next = (struct list_head *)hardList;
4909                                                         hardList = in;
4910                                                         break;
4911                                                 case YAFFS_OBJECT_TYPE_DIRECTORY:       // Do nothing
4912                                                         break;
4913                                                 case YAFFS_OBJECT_TYPE_SPECIAL: // Do nothing
4914                                                         break;
4915                                                 case YAFFS_OBJECT_TYPE_SYMLINK:         // Do nothing
4916                                                         in->variant.symLinkVariant.alias = yaffs_CloneString(oh->alias);
4917                                                         break;
4918                                         }
4919
4920                                 //T((" %d %d header %d \"%s\" type %d\n",blk,c,tags.objectId,oh->name,in->variantType));
4921                                 }
4922                         }
4923                 }
4924
4925                 if(state == YAFFS_BLOCK_STATE_NEEDS_SCANNING)
4926                 {
4927                         // If we got this far while scanning, then the block is fully allocated.
4928                         state = YAFFS_BLOCK_STATE_FULL;
4929                 }
4930
4931                 bi->blockState = state;
4932
4933                 // Now let's see if it was dirty
4934                 if(     bi->pagesInUse == 0 &&
4935                         !bi->hasShrinkHeader &&
4936                 bi->blockState == YAFFS_BLOCK_STATE_FULL)
4937             {
4938                 yaffs_BlockBecameDirty(dev,blk);
4939             }
4940
4941         }
4942
4943         if(blockIndex)
4944         {
4945                 YFREE(blockIndex);
4946         }
4947
4948         // Ok, we've done all the scanning.
4949
4950         // Fix up the hard link chains.
4951         // We should now have scanned all the objects, now it's time to add these
4952         // hardlinks.
4953         while(hardList)
4954         {
4955                 hl = hardList;
4956                 hardList = (yaffs_Object *)(hardList->hardLinks.next);
4957
4958                 in = yaffs_FindObjectByNumber(dev,hl->variant.hardLinkVariant.equivalentObjectId);
4959
4960                 if(in)
4961                 {
4962                         // Add the hardlink pointers
4963                         hl->variant.hardLinkVariant.equivalentObject=in;
4964                         list_add(&hl->hardLinks,&in->hardLinks);
4965                 }
4966                 else
4967                 {
4968                         //Todo Need to report/handle this better.
4969                         // Got a problem... hardlink to a non-existant object
4970                         hl->variant.hardLinkVariant.equivalentObject=NULL;
4971                         INIT_LIST_HEAD(&hl->hardLinks);
4972
4973                 }
4974
4975         }
4976
4977         {
4978                 struct list_head *i;
4979                 struct list_head *n;
4980
4981                 yaffs_Object *l;
4982
4983                 // Soft delete all the unlinked files
4984                 list_for_each_safe(i,n,&dev->unlinkedDir->variant.directoryVariant.children)
4985                 {
4986                         if(i)
4987                         {
4988                                 l = list_entry(i, yaffs_Object,siblings);
4989                                 yaffs_DestroyObject(l);
4990                         }
4991                 }
4992
4993                 // Soft delete all the deletedDir files
4994                 list_for_each_safe(i,n,&dev->deletedDir->variant.directoryVariant.children)
4995                 {
4996                         if(i)
4997                         {
4998                                 l = list_entry(i, yaffs_Object,siblings);
4999                                 yaffs_DestroyObject(l);
5000
5001                         }
5002                 }
5003         }
5004
5005         yaffs_ReleaseTempBuffer(dev,chunkData,__LINE__);
5006
5007         T(YAFFS_TRACE_SCAN,(TSTR("yaffs_ScanBackwards ends" TENDSTR)));
5008
5009         return YAFFS_OK;
5010 }
5011
5012
5013
5014 ////////////////////////// Directory Functions /////////////////////////
5015
5016
5017 static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj)
5018 {
5019
5020         if(!directory)
5021         {
5022                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragedy: Trying to add an object to a null pointer directory" TENDSTR)));
5023                 YBUG();
5024         }
5025         if(directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
5026         {
5027                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragedy: Trying to add an object to a non-directory" TENDSTR)));
5028                 YBUG();
5029         }
5030
5031                 if(obj->siblings.prev == NULL)
5032         {
5033                 // Not initialised
5034                 INIT_LIST_HEAD(&obj->siblings);
5035
5036         }
5037         else if(!list_empty(&obj->siblings))
5038         {
5039                 // If it is holed up somewhere else, un hook it
5040                 list_del_init(&obj->siblings);
5041         }
5042         // Now add it
5043         list_add(&obj->siblings,&directory->variant.directoryVariant.children);
5044         obj->parent = directory;
5045
5046         if(directory == obj->myDev->unlinkedDir || directory == obj->myDev->deletedDir)
5047         {
5048                 obj->unlinked = 1;
5049                 obj->myDev->nUnlinkedFiles++;
5050                 obj->renameAllowed = 0;
5051         }
5052 }
5053
5054 static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj)
5055 {
5056         list_del_init(&obj->siblings);
5057         obj->parent = NULL;
5058 }
5059
5060 yaffs_Object *yaffs_FindObjectByName(yaffs_Object *directory,const YCHAR *name)
5061 {
5062         int sum;
5063
5064         struct list_head *i;
5065         YCHAR buffer[YAFFS_MAX_NAME_LENGTH+1];
5066
5067         yaffs_Object *l;
5068
5069         if(!name)
5070         {
5071                 return NULL;
5072         }
5073
5074         if(!directory)
5075         {
5076                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragedy: yaffs_FindObjectByName: null pointer directory"TENDSTR)));
5077                 YBUG();
5078         }
5079         if(directory->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
5080         {
5081                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragedy: yaffs_FindObjectByName: non-directory"TENDSTR)));
5082                 YBUG();
5083         }
5084
5085         sum = yaffs_CalcNameSum(name);
5086
5087         list_for_each(i,&directory->variant.directoryVariant.children)
5088         {
5089                 if(i)
5090                 {
5091                         l = list_entry(i, yaffs_Object,siblings);
5092
5093                         // Special case for lost-n-found
5094                         if(l->objectId == YAFFS_OBJECTID_LOSTNFOUND)
5095                         {
5096                                 if(yaffs_strcmp(name,YAFFS_LOSTNFOUND_NAME) == 0)
5097                                 {
5098                                         return l;
5099                                 }
5100                         }
5101                         else if(yaffs_SumCompare(l->sum, sum)||
5102                                     l->chunkId <= 0) //LostnFound cunk called Objxxx
5103                         {
5104                                 // Do a real check
5105                                 yaffs_GetObjectName(l,buffer,YAFFS_MAX_NAME_LENGTH);
5106                                 if(yaffs_strcmp(name,buffer) == 0)
5107                                 {
5108                                         return l;
5109                                 }
5110
5111                         }
5112                 }
5113         }
5114
5115         return NULL;
5116 }
5117
5118
5119 int yaffs_ApplyToDirectoryChildren(yaffs_Object *theDir,int (*fn)(yaffs_Object *))
5120 {
5121         struct list_head *i;
5122         yaffs_Object *l;
5123
5124
5125         if(!theDir)
5126         {
5127                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragedy: yaffs_FindObjectByName: null pointer directory"TENDSTR)));
5128                 YBUG();
5129         }
5130         if(theDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
5131         {
5132                 T(YAFFS_TRACE_ALWAYS,(TSTR("tragedy: yaffs_FindObjectByName: non-directory"TENDSTR)));
5133                 YBUG();
5134         }
5135
5136         list_for_each(i,&theDir->variant.directoryVariant.children)
5137         {
5138                 if(i)
5139                 {
5140                         l = list_entry(i, yaffs_Object,siblings);
5141                         if(l && !fn(l))
5142                         {
5143                                 return YAFFS_FAIL;
5144                         }
5145                 }
5146         }
5147
5148         return YAFFS_OK;
5149
5150 }
5151
5152
5153 // GetEquivalentObject dereferences any hard links to get to the
5154 // actual object.
5155
5156 yaffs_Object *yaffs_GetEquivalentObject(yaffs_Object *obj)
5157 {
5158         if(obj && obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
5159         {
5160                 // We want the object id of the equivalent object, not this one
5161                 obj = obj->variant.hardLinkVariant.equivalentObject;
5162         }
5163         return obj;
5164
5165 }
5166
5167 int yaffs_GetObjectName(yaffs_Object *obj,YCHAR *name,int buffSize)
5168 {
5169         memset(name,0,buffSize * sizeof(YCHAR));
5170
5171         if(obj->objectId == YAFFS_OBJECTID_LOSTNFOUND)
5172         {
5173                 yaffs_strncpy(name,YAFFS_LOSTNFOUND_NAME,buffSize - 1);
5174         }
5175         else if(obj->chunkId <= 0)
5176         {
5177                 YCHAR locName[20];
5178                 // make up a name
5179                 yaffs_sprintf(locName,_Y("%s%d"),YAFFS_LOSTNFOUND_PREFIX,obj->objectId);
5180                 yaffs_strncpy(name,locName,buffSize - 1);
5181
5182         }
5183 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
5184         else if(obj->shortName[0])
5185         {
5186                 yaffs_strcpy(name,obj->shortName);
5187         }
5188 #endif
5189         else
5190         {
5191                 __u8 *buffer = yaffs_GetTempBuffer(obj->myDev,__LINE__);
5192
5193                 yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
5194
5195                 memset(buffer,0,obj->myDev->nBytesPerChunk);
5196
5197                 if(obj->chunkId >= 0)
5198                 {
5199                         yaffs_ReadChunkWithTagsFromNAND(obj->myDev,obj->chunkId,buffer,NULL);
5200                 }
5201                 yaffs_strncpy(name,oh->name,buffSize - 1);
5202
5203                 yaffs_ReleaseTempBuffer(obj->myDev,buffer,__LINE__);
5204         }
5205
5206         return yaffs_strlen(name);
5207 }
5208
5209 int yaffs_GetObjectFileLength(yaffs_Object *obj)
5210 {
5211
5212         // Dereference any hard linking
5213         obj = yaffs_GetEquivalentObject(obj);
5214
5215         if(obj->variantType == YAFFS_OBJECT_TYPE_FILE)
5216         {
5217                 return obj->variant.fileVariant.fileSize;
5218         }
5219         if(obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK)
5220         {
5221                 return yaffs_strlen(obj->variant.symLinkVariant.alias);
5222         }
5223         else
5224         {
5225                 // Only a directory should drop through to here
5226                 return obj->myDev->nBytesPerChunk;
5227         }
5228 }
5229
5230 int yaffs_GetObjectLinkCount(yaffs_Object *obj)
5231 {
5232         int count = 0;
5233         struct list_head *i;
5234
5235         if(!obj->unlinked)
5236         {
5237                 count++;        // the object itself
5238         }
5239         list_for_each(i,&obj->hardLinks)
5240         {
5241                 count++;        // add the hard links;
5242         }
5243         return count;
5244
5245 }
5246
5247
5248 int yaffs_GetObjectInode(yaffs_Object *obj)
5249 {
5250         obj = yaffs_GetEquivalentObject(obj);
5251
5252         return obj->objectId;
5253 }
5254
5255 unsigned yaffs_GetObjectType(yaffs_Object *obj)
5256 {
5257         obj = yaffs_GetEquivalentObject(obj);
5258
5259         switch(obj->variantType)
5260         {
5261                 case YAFFS_OBJECT_TYPE_FILE:            return DT_REG; break;
5262                 case YAFFS_OBJECT_TYPE_DIRECTORY:       return DT_DIR; break;
5263                 case YAFFS_OBJECT_TYPE_SYMLINK:         return DT_LNK; break;
5264                 case YAFFS_OBJECT_TYPE_HARDLINK:        return DT_REG; break;
5265                 case YAFFS_OBJECT_TYPE_SPECIAL:
5266                         if(S_ISFIFO(obj->yst_mode)) return DT_FIFO;
5267                         if(S_ISCHR(obj->yst_mode)) return DT_CHR;
5268                         if(S_ISBLK(obj->yst_mode)) return DT_BLK;
5269                         if(S_ISSOCK(obj->yst_mode)) return DT_SOCK;
5270                 default: return DT_REG; break;
5271         }
5272 }
5273
5274 YCHAR *yaffs_GetSymlinkAlias(yaffs_Object *obj)
5275 {
5276         obj = yaffs_GetEquivalentObject(obj);
5277         if(obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK)
5278         {
5279                 return yaffs_CloneString(obj->variant.symLinkVariant.alias);
5280         }
5281         else
5282         {
5283                 return yaffs_CloneString(_Y(""));
5284         }
5285 }
5286
5287 #ifndef CONFIG_YAFFS_WINCE
5288
5289 int yaffs_SetAttributes(yaffs_Object *obj, struct iattr *attr)
5290 {
5291         unsigned int valid = attr->ia_valid;
5292
5293         if(valid & ATTR_MODE) obj->yst_mode = attr->ia_mode;
5294         if(valid & ATTR_UID) obj->yst_uid = attr->ia_uid;
5295         if(valid & ATTR_GID) obj->yst_gid = attr->ia_gid;
5296
5297         if(valid & ATTR_ATIME) obj->yst_atime = Y_TIME_CONVERT(attr->ia_atime);
5298         if(valid & ATTR_CTIME) obj->yst_ctime = Y_TIME_CONVERT(attr->ia_ctime);
5299         if(valid & ATTR_MTIME) obj->yst_mtime = Y_TIME_CONVERT(attr->ia_mtime);
5300
5301         if(valid & ATTR_SIZE) yaffs_ResizeFile(obj,attr->ia_size);
5302
5303         yaffs_UpdateObjectHeader(obj,NULL,1,0,0);
5304
5305         return YAFFS_OK;
5306
5307 }
5308 int yaffs_GetAttributes(yaffs_Object *obj, struct iattr *attr)
5309 {
5310         unsigned int valid = 0;
5311
5312         attr->ia_mode = obj->yst_mode;  valid |= ATTR_MODE;
5313         attr->ia_uid = obj->yst_uid;            valid |= ATTR_UID;
5314         attr->ia_gid = obj->yst_gid;            valid |= ATTR_GID;
5315
5316         Y_TIME_CONVERT(attr->ia_atime)= obj->yst_atime; valid |= ATTR_ATIME;
5317         Y_TIME_CONVERT(attr->ia_ctime) = obj->yst_ctime;        valid |= ATTR_CTIME;
5318         Y_TIME_CONVERT(attr->ia_mtime) = obj->yst_mtime;        valid |= ATTR_MTIME;
5319
5320         attr->ia_size = yaffs_GetFileSize(obj); valid |= ATTR_SIZE;
5321
5322         attr->ia_valid = valid;
5323
5324         return YAFFS_OK;
5325
5326 }
5327
5328 #endif
5329
5330 int yaffs_DumpObject(yaffs_Object *obj)
5331 {
5332 //      __u8 buffer[YAFFS_BYTES_PER_CHUNK];
5333         YCHAR name[257];
5334 //      yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
5335
5336 //      memset(buffer,0,YAFFS_BYTES_PER_CHUNK);
5337
5338 //      if(obj->chunkId >= 0)
5339 //      {
5340 //              yaffs_ReadChunkFromNAND(obj->myDev,obj->chunkId,buffer,NULL);
5341 //      }
5342
5343         yaffs_GetObjectName(obj,name,256);
5344
5345         T(YAFFS_TRACE_ALWAYS,(TSTR("Object %d, inode %d \"%s\"\n dirty %d valid %d serial %d sum %d chunk %d type %d size %d\n" TENDSTR),
5346                         obj->objectId,yaffs_GetObjectInode(obj), name, obj->dirty, obj->valid, obj->serial,
5347                         obj->sum, obj->chunkId, yaffs_GetObjectType(obj), yaffs_GetObjectFileLength(obj)));
5348
5349
5350
5351         return YAFFS_OK;
5352 }
5353
5354
5355 ///////////////////////// Initialisation code ///////////////////////////
5356
5357
5358 static int yaffs_CheckDevFunctions(const yaffs_Device *dev)
5359 {
5360
5361         // Common functions, gotta have
5362         if(!dev->eraseBlockInNAND ||
5363            !dev->initialiseNAND) return 0;
5364
5365 #ifdef CONFIG_YAFFS_YAFFS2
5366
5367         // Can use the "with tags" style interface for yaffs1 or yaffs2
5368         if(dev->writeChunkWithTagsToNAND &&
5369            dev->readChunkWithTagsFromNAND &&
5370            !dev->writeChunkToNAND &&
5371            !dev->readChunkFromNAND &&
5372            dev->markNANDBlockBad &&
5373            dev->queryNANDBlock) return 1;
5374 #endif
5375
5376         // Can use the "spare" style interface for yaffs1
5377         if(!dev->isYaffs2 &&
5378            !dev->writeChunkWithTagsToNAND &&
5379            !dev->readChunkWithTagsFromNAND &&
5380            dev->writeChunkToNAND &&
5381            dev->readChunkFromNAND &&
5382            !dev->markNANDBlockBad &&
5383            !dev->queryNANDBlock) return 1;
5384
5385         return 0; // bad
5386 }
5387
5388
5389 int yaffs_GutsInitialise(yaffs_Device *dev)
5390 {
5391         unsigned x;
5392         int bits;
5393         int extraBits;
5394         int nBlocks;
5395
5396         T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: yaffs_GutsInitialise()" TENDSTR)));
5397         // Check stuff that must be set
5398
5399         if(!dev)
5400         {
5401                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: Need a device" TENDSTR)));
5402                 return YAFFS_FAIL;
5403         }
5404
5405         dev->internalStartBlock = dev->startBlock;
5406         dev->internalEndBlock =  dev->endBlock;
5407         dev->blockOffset = 0;
5408         dev->chunkOffset = 0;
5409         dev->nFreeChunks = 0;
5410
5411         if(dev->startBlock == 0)
5412         {
5413                 dev->internalStartBlock = dev->startBlock + 1;
5414                 dev->internalEndBlock =  dev->endBlock + 1;
5415                 dev->blockOffset = 1;
5416                 dev->chunkOffset = dev->nChunksPerBlock;
5417         }
5418
5419         // Check geometry parameters.
5420
5421         if(     (dev->isYaffs2 && dev->nBytesPerChunk <1024)  ||
5422                 (!dev->isYaffs2 && dev->nBytesPerChunk !=512)  ||
5423                 dev->nChunksPerBlock < 2 ||
5424                 dev->nReservedBlocks < 2 ||
5425                 dev->internalStartBlock <= 0 ||
5426                 dev->internalEndBlock <= 0 ||
5427                 dev->internalEndBlock <= (dev->internalStartBlock + dev->nReservedBlocks + 2) // otherwise it is too small
5428           )
5429         {
5430                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: NAND geometry problems: chunk size %d, type is yaffs%s " TENDSTR),
5431                    dev->nBytesPerChunk, dev->isYaffs2 ? "2" : ""));
5432                 return YAFFS_FAIL;
5433         }
5434
5435         if(yaffs_InitialiseNAND(dev) != YAFFS_OK)
5436         {
5437                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: InitialiseNAND failed" TENDSTR)));
5438                 return YAFFS_FAIL;
5439         }
5440
5441         // Got the right mix of functions?
5442         //
5443         if(!yaffs_CheckDevFunctions(dev))
5444         {
5445                 //Function missing
5446                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: device function(s) missing or wrong\n" TENDSTR)));
5447
5448                 return YAFFS_FAIL;
5449         }
5450
5451         // This is really a compilation check.
5452         if(!yaffs_CheckStructures())
5453         {
5454                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs_CheckStructures failed\n" TENDSTR)));
5455                 return YAFFS_FAIL;
5456         }
5457
5458         if(dev->isMounted)
5459         {
5460                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: device already mounted\n" TENDSTR)));
5461                 return YAFFS_FAIL;
5462         }
5463
5464         //
5465         //
5466         // Finished with most checks. One or two more checks happen later on too.
5467         //
5468
5469         dev->isMounted = 1;
5470
5471
5472         nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
5473
5474
5475
5476         // OK now calculate a few things for the device
5477         // Calculate chunkGroupBits.
5478         // We need to find the next power of 2 > than internalEndBlock
5479
5480         x = dev->nChunksPerBlock * (dev->internalEndBlock+1);
5481
5482         for(bits = extraBits = 0; x > 1; bits++)
5483         {
5484                 if(x & 1) extraBits++;
5485                 x >>= 1;
5486         }
5487
5488         if(extraBits > 0) bits++;
5489
5490
5491         // Level0 Tnodes are 16 bits, so if the bitwidth of the
5492         // chunk range we're using is greater than 16 we need
5493         // to figure out chunk shift and chunkGroupSize
5494         if(bits <= 16)
5495         {
5496                 dev->chunkGroupBits = 0;
5497         }
5498         else
5499         {
5500                 dev->chunkGroupBits = bits - 16;
5501         }
5502
5503         dev->chunkGroupSize = 1 << dev->chunkGroupBits;
5504
5505         if(dev->nChunksPerBlock < dev->chunkGroupSize)
5506         {
5507                 // We have a problem because the soft delete won't work if
5508                 // the chunk group size > chunks per block.
5509                 // This can be remedied by using larger "virtual blocks".
5510                 T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: chunk group too large\n" TENDSTR)));
5511
5512                 return YAFFS_FAIL;
5513         }
5514
5515
5516         // OK, we've finished verifying the device, lets continue with initialisation
5517
5518         // More device initialisation
5519         dev->garbageCollections = 0;
5520         dev->passiveGarbageCollections = 0;
5521         dev->currentDirtyChecker = 0;
5522         dev->bufferedBlock = -1;
5523         dev->doingBufferedBlockRewrite = 0;
5524         dev->nDeletedFiles = 0;
5525         dev->nBackgroundDeletions=0;
5526         dev->nUnlinkedFiles = 0;
5527         dev->eccFixed=0;
5528         dev->eccUnfixed=0;
5529         dev->tagsEccFixed=0;
5530         dev->tagsEccUnfixed=0;
5531         dev->nErasureFailures = 0;
5532         dev->nErasedBlocks = 0;
5533         dev->isDoingGC = 0;
5534
5535         //dev->localBuffer = YMALLOC(dev->nBytesPerChunk);
5536         // Initialise temporary buffers
5537         {
5538                 int i;
5539                 for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
5540                 {
5541                         dev->tempBuffer[i].line = 0; // not in use
5542                         dev->tempBuffer[i].buffer = YMALLOC(dev->nBytesPerChunk);
5543                 }
5544         }
5545
5546
5547
5548         yaffs_InitialiseBlocks(dev,nBlocks);
5549
5550         yaffs_InitialiseTnodes(dev);
5551
5552         yaffs_InitialiseObjects(dev);
5553
5554         dev->gcCleanupList = YMALLOC(dev->nChunksPerBlock * sizeof(__u32));
5555
5556         if(dev->nShortOpCaches > 0)
5557         {
5558                 int i;
5559
5560                 if(dev->nShortOpCaches >  YAFFS_MAX_SHORT_OP_CACHES)
5561                 {
5562                         dev->nShortOpCaches = YAFFS_MAX_SHORT_OP_CACHES;
5563                 }
5564
5565                 dev->srCache = YMALLOC( dev->nShortOpCaches * sizeof(yaffs_ChunkCache));
5566
5567                 for(i=0; i < dev->nShortOpCaches; i++)
5568                 {
5569                         dev->srCache[i].object = NULL;
5570                         dev->srCache[i].lastUse = 0;
5571                         dev->srCache[i].dirty = 0;
5572                         dev->srCache[i].data = YMALLOC(dev->nBytesPerChunk);
5573                 }
5574                 dev->srLastUse = 0;
5575         }
5576
5577         dev->cacheHits = 0;
5578
5579
5580         // Initialise the unlinked, root and lost and found directories
5581         dev->lostNFoundDir = dev->rootDir = dev->unlinkedDir = dev->deletedDir = NULL;
5582
5583         dev->unlinkedDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_UNLINKED, S_IFDIR);
5584         dev->deletedDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_DELETED, S_IFDIR);
5585
5586         dev->rootDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_ROOT,YAFFS_ROOT_MODE | S_IFDIR);
5587         dev->lostNFoundDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_LOSTNFOUND,YAFFS_LOSTNFOUND_MODE | S_IFDIR);
5588         yaffs_AddObjectToDirectory(dev->rootDir,dev->lostNFoundDir);
5589
5590         if(dev->isYaffs2)
5591         {
5592                 dev->useHeaderFileSize = 1;
5593         }
5594
5595         // Now scan the flash.
5596
5597         if(dev->isYaffs2)
5598                 yaffs_ScanBackwards(dev);
5599         else
5600                 yaffs_Scan(dev);
5601
5602         // Zero out stats
5603         dev->nPageReads = 0;
5604         dev->nPageWrites =  0;
5605         dev->nBlockErasures = 0;
5606         dev->nGCCopies = 0;
5607         dev->nRetriedWrites = 0;
5608
5609         dev->nRetiredBlocks = 0;
5610
5611         yaffs_VerifyFreeChunks(dev);
5612
5613         T(YAFFS_TRACE_ALWAYS,(TSTR("yaffs: yaffs_GutsInitialise() done.\n" TENDSTR)));
5614         return YAFFS_OK;
5615
5616 }
5617
5618 void yaffs_Deinitialise(yaffs_Device *dev)
5619 {
5620         if(dev->isMounted)
5621         {
5622                 int i;
5623
5624                 yaffs_DeinitialiseBlocks(dev);
5625                 yaffs_DeinitialiseTnodes(dev);
5626                 yaffs_DeinitialiseObjects(dev);
5627                 if(dev->nShortOpCaches > 0)
5628                 {
5629
5630                         for(i=0; i < dev->nShortOpCaches; i++)
5631                         {
5632                                 YFREE(dev->srCache[i].data);
5633                         }
5634
5635                         YFREE(dev->srCache);
5636                 }
5637
5638                 YFREE(dev->gcCleanupList);
5639
5640                 for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
5641                 {
5642                         YFREE(dev->tempBuffer[i].buffer);
5643                 }
5644
5645                 dev->isMounted = 0;
5646         }
5647
5648 }
5649
5650
5651 static int  yaffs_CountFreeChunks(yaffs_Device *dev)
5652 {
5653         int nFree;
5654         int b;
5655
5656         yaffs_BlockInfo *blk;
5657
5658
5659         for(nFree = 0, b = dev->internalStartBlock; b <= dev->internalEndBlock; b++)
5660         {
5661                 blk = yaffs_GetBlockInfo(dev,b);
5662
5663                 switch(blk->blockState)
5664                 {
5665                         case YAFFS_BLOCK_STATE_EMPTY:
5666                         case YAFFS_BLOCK_STATE_ALLOCATING:
5667                         case YAFFS_BLOCK_STATE_COLLECTING:
5668                         case YAFFS_BLOCK_STATE_FULL: nFree += (dev->nChunksPerBlock - blk->pagesInUse + blk->softDeletions); break;
5669                         default: break;
5670                 }
5671
5672         }
5673
5674         return nFree;
5675 }
5676
5677
5678
5679 int yaffs_GetNumberOfFreeChunks(yaffs_Device *dev)
5680 {
5681         // This is what we report to the outside world
5682
5683         int nFree;
5684         int nDirtyCacheChunks;
5685
5686 #if 1
5687         nFree = dev->nFreeChunks;
5688 #else
5689         nFree = yaffs_CountFreeChunks(dev);
5690 #endif
5691
5692         // Now count the number of dirty chunks in the cache and subtract those
5693
5694         {
5695                 int i;
5696                 for( nDirtyCacheChunks = 0,i = 0; i < dev->nShortOpCaches; i++)
5697                 {
5698                         if(dev->srCache[i].dirty) nDirtyCacheChunks++;
5699                 }
5700         }
5701
5702         nFree -= nDirtyCacheChunks;
5703
5704         nFree -= ((dev->nReservedBlocks + 1) * dev->nChunksPerBlock);
5705
5706         if(nFree < 0) nFree = 0;
5707
5708         return nFree;
5709
5710 }
5711
5712 static int  yaffs_freeVerificationFailures;
5713
5714 static void yaffs_VerifyFreeChunks(yaffs_Device *dev)
5715 {
5716         int counted = yaffs_CountFreeChunks(dev);
5717
5718         int difference = dev->nFreeChunks - counted;
5719
5720         if(difference)
5721         {
5722                 T(YAFFS_TRACE_ALWAYS,(TSTR("Freechunks verification failure %d %d %d" TENDSTR),dev->nFreeChunks,counted,difference));
5723                 yaffs_freeVerificationFailures++;
5724         }
5725 }
5726
5727 /////////////////// YAFFS test code //////////////////////////////////
5728
5729 #define yaffs_CheckStruct(structure,syze, name) \
5730            if(sizeof(structure) != syze) \
5731                { \
5732                  T(YAFFS_TRACE_ALWAYS,(TSTR("%s should be %d but is %d\n" TENDSTR),name,syze,sizeof(structure))); \
5733                  return YAFFS_FAIL; \
5734                    }
5735
5736
5737 static int yaffs_CheckStructures(void)
5738 {
5739 //      yaffs_CheckStruct(yaffs_Tags,8,"yaffs_Tags")
5740 //      yaffs_CheckStruct(yaffs_TagsUnion,8,"yaffs_TagsUnion")
5741 //      yaffs_CheckStruct(yaffs_Spare,16,"yaffs_Spare")
5742 #ifndef CONFIG_YAFFS_TNODE_LIST_DEBUG
5743         yaffs_CheckStruct(yaffs_Tnode,2* YAFFS_NTNODES_LEVEL0,"yaffs_Tnode")
5744 #endif
5745         yaffs_CheckStruct(yaffs_ObjectHeader,512,"yaffs_ObjectHeader")
5746
5747
5748         return YAFFS_OK;
5749 }
5750
5751
5752
5753