yaffs_guts.c

   1 /*
   2  * YAFFS: Yet another FFS. A NAND-flash specific file system.
   3  * yaffs_guts.c  The main guts of YAFFS
   4  *
   5  * Copyright (C) 2002 Aleph One Ltd.
   6  *   for Toby Churchill Ltd and Brightstar Engineering
   7  *
   8  * Created by Charles Manning <charles@aleph1.co.uk>
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License version 2 as
  12  * published by the Free Software Foundation.
  13  *
  14  */
  15  //yaffs_guts.c
  16
  17 #include "yportenv.h"
  18
  19 #include "yaffsinterface.h"
  20 #include "yaffs_guts.h"
  21
  22
  23 #define YAFFS_GARBAGE_COLLECT_LOW_WATER 2
  24
  25
  26 // External functions for ECC on data
  27 void nand_calculate_ecc (const u_char *dat, u_char *ecc_code);
  28 int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc);
  29
  30
  31 // countBits is a quick way of counting the number of bits in a byte.
  32 // ie. countBits[n] holds the number of 1 bits in a byte with the value n.
  33
  34 static const char yaffs_countBitsTable[256] =
  35 {
  36 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
  37 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  38 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  39 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  40 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  41 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  42 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  43 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  44 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  45 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  46 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  47 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  48 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  49 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  50 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  51 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
  52 };
  53
  54 static int yaffs_CountBits(__u8 x)
  55 {
  56         int retVal;
  57         retVal = yaffs_countBitsTable[x];
  58         return retVal;
  59 }
  60
  61
  62
  63 // Local prototypes
  64 static int yaffs_CheckObjectHashSanity(yaffs_Device *dev);
  65 static void yaffs_LoadTagsIntoSpare(yaffs_Spare *sparePtr, yaffs_Tags *tagsPtr);
  66 static void yaffs_GetTagsFromSpare(yaffs_Spare *sparePtr,yaffs_Tags *tagsPtr);
  67 static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan);
  68
  69 static yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type);
  70 static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj);
  71 static int yaffs_UpdateObjectHeader(yaffs_Object *in,const char *name, int force);
  72 static void yaffs_DeleteChunk(yaffs_Device *dev,int chunkId);
  73 static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj);
  74 static int yaffs_CheckStructures(void);
  75 static void yaffs_DeleteWorker(yaffs_Object *in, yaffs_Tnode *tn, __u32 level, int chunkOffset,int *limit);
  76 static int yaffs_DoGenericObjectDeletion(yaffs_Object *in);
  77
  78 static yaffs_BlockInfo *yaffs_GetBlockInfo(yaffs_Device *dev,int blockNo);
  79
  80 // Robustification
  81 static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND);
  82 static void yaffs_HandleReadDataError(yaffs_Device *dev,int chunkInNAND);
  83 static void yaffs_HandleWriteChunkError(yaffs_Device *dev,int chunkInNAND);
  84 static void yaffs_HandleWriteChunkOk(yaffs_Device *dev,int chunkInNAND,const __u8 *data, const yaffs_Spare *spare);
  85 static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND, const yaffs_Spare *spare);
  86
  87 static int  yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND);
  88
  89 static int yaffs_UnlinkWorker(yaffs_Object *obj);
  90
  91
  92 static int yaffs_VerifyCompare(const __u8 *d0, const __u8 * d1, const yaffs_Spare *s0, const yaffs_Spare *s1);
  93
  94
  95
  96 loff_t yaffs_GetFileSize(yaffs_Object *obj);
  97
  98 static int yaffs_ReadChunkTagsFromNAND(yaffs_Device *dev,int chunkInNAND, yaffs_Tags *tags, int *chunkDeleted);
  99 static int yaffs_TagsMatch(const yaffs_Tags *tags, int objectId, int chunkInObject, int chunkDeleted);
 100
 101
 102 static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve);
 103
 104 #ifdef YAFFS_PARANOID
 105 static int yaffs_CheckFileSanity(yaffs_Object *in);
 106 #else
 107 #define yaffs_CheckFileSanity(in)
 108 #endif
 109
 110 #ifdef CONFIG_YAFFS_SHORT_OP_CACHE
 111 static void yaffs_InvalidateChunkCache(yaffs_Object *in);
 112 #define yaffs_INVALIDATECHUNKCACHE(in) yaffs_InvalidateChunkCache(in)
 113 #else
 114 #define yaffs_INVALIDATECHUNKCACHE(in)
 115 #endif
 116
 117
 118 static  __inline__ yaffs_BlockInfo* yaffs_GetBlockInfo(yaffs_Device *dev, int blk)
 119 {
 120         if(blk < dev->startBlock || blk > dev->endBlock)
 121         {
 122                 YBUG();
 123         }
 124         return &dev->blockInfo[blk - dev->startBlock];
 125 }
 126
 127
 128 static  __inline__ int yaffs_HashFunction(int n)
 129 {
 130         return (n % YAFFS_NOBJECT_BUCKETS);
 131 }
 132
 133
 134 yaffs_Object *yaffs_Root(yaffs_Device *dev)
 135 {
 136         return dev->rootDir;
 137 }
 138
 139 yaffs_Object *yaffs_LostNFound(yaffs_Device *dev)
 140 {
 141         return dev->lostNFoundDir;
 142 }
 143
 144
 145 static int yaffs_WriteChunkToNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND, const __u8 *data, yaffs_Spare *spare)
 146 {
 147         dev->nPageWrites++;
 148         return dev->writeChunkToNAND(dev,chunkInNAND,data,spare);
 149 }
 150
 151
 152 int yaffs_ReadChunkFromNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND, __u8 *data, yaffs_Spare *spare,int doErrorCorrection)
 153 {
 154         int retVal;
 155         __u8 calcEcc[3];
 156         yaffs_Spare localSpare;
 157         int eccResult1,eccResult2;
 158
 159         dev->nPageReads++;
 160
 161         if(!spare && data)
 162         {
 163                 // If we don't have a real spare, then we use a local one.
 164                 // Need this for the calculation of the ecc
 165                 spare = &localSpare;
 166         }
 167
 168         retVal  = dev->readChunkFromNAND(dev,chunkInNAND,data,spare);
 169         if(data && doErrorCorrection)
 170         {
 171                 // Do ECC correction
 172                 //Todo handle any errors
 173                  nand_calculate_ecc(data,calcEcc);
 174                  eccResult1 = nand_correct_data (data,spare->ecc1, calcEcc);
 175                  nand_calculate_ecc(&data[256],calcEcc);
 176                  eccResult2 = nand_correct_data (&data[256],spare->ecc2, calcEcc);
 177
 178                  if(eccResult1>0)
 179                  {
 180                         T((TSTR("**>>ecc error fix performed on chunk %d:0" TENDSTR),chunkInNAND));
 181                  }
 182                  else if(eccResult1<0)
 183                  {
 184                         T((TSTR("**>>ecc error unfixed on chunk %d:0" TENDSTR),chunkInNAND));
 185                  }
 186
 187                  if(eccResult2>0)
 188                  {
 189                         T((TSTR("**>>ecc error fix performed on chunk %d:1" TENDSTR),chunkInNAND));
 190                  }
 191                  else if(eccResult2<0)
 192                  {
 193                         T((TSTR("**>>ecc error unfixed on chunk %d:1" TENDSTR),chunkInNAND));
 194                  }
 195
 196                  if(eccResult1 || eccResult2)
 197                  {
 198                         // Hoosterman, we had a data problem on this page
 199                         yaffs_HandleReadDataError(dev,chunkInNAND);
 200                  }
 201         }
 202         return retVal;
 203 }
 204
 205
 206 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND)
 207 {
 208
 209         static int init = 0;
 210         static __u8 cmpbuf[YAFFS_BYTES_PER_CHUNK];
 211         static __u8 data[YAFFS_BYTES_PER_CHUNK];
 212         static __u8 spare[16];
 213
 214
 215         dev->readChunkFromNAND(dev,chunkInNAND,data,(yaffs_Spare *)spare);
 216
 217
 218
 219         if(!init)
 220         {
 221                 memset(cmpbuf,0xff,YAFFS_BYTES_PER_CHUNK);
 222                 init = 1;
 223         }
 224
 225         if(memcmp(cmpbuf,data,YAFFS_BYTES_PER_CHUNK)) return  YAFFS_FAIL;
 226         if(memcmp(cmpbuf,spare,16)) return YAFFS_FAIL;
 227
 228
 229         return YAFFS_OK;
 230
 231 }
 232
 233
 234
 235 int yaffs_EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND)
 236 {
 237         dev->nBlockErasures++;
 238         return dev->eraseBlockInNAND(dev,blockInNAND);
 239 }
 240
 241 int yaffs_InitialiseNAND(struct yaffs_DeviceStruct *dev)
 242 {
 243         return dev->initialiseNAND(dev);
 244 }
 245
 246 static int yaffs_WriteNewChunkToNAND(struct yaffs_DeviceStruct *dev, const __u8 *data, yaffs_Spare *spare,int useReserve)
 247 {
 248         int chunk;
 249
 250         int writeOk = 1;
 251         int attempts = 0;
 252
 253         unsigned char rbData[YAFFS_BYTES_PER_CHUNK];
 254         yaffs_Spare rbSpare;
 255
 256         do{
 257                 chunk = yaffs_AllocateChunk(dev,useReserve);
 258
 259                 if(chunk >= 0)
 260                 {
 261
 262                         // First check this chunk is erased...
 263 #ifndef CONFIG_YAFFS_DISABLE_CHUNK_ERASED_CHECK
 264                         writeOk = yaffs_CheckChunkErased(dev,chunk);
 265 #endif
 266                         if(!writeOk)
 267                         {
 268                                 T((TSTR("**>> yaffs chunk %d was not erased" TENDSTR),chunk));
 269                         }
 270                         else
 271                         {
 272                                 writeOk =  yaffs_WriteChunkToNAND(dev,chunk,data,spare);
 273                         }
 274                         attempts++;
 275                         if(writeOk)
 276                         {
 277                                 // Readback & verify
 278                                 // If verify fails, then delete this chunk and try again
 279                                 // To verify we compare everything except the block and
 280                                 // page status bytes.
 281                                 // NB We check a raw read without ECC correction applied
 282                                 yaffs_ReadChunkFromNAND(dev,chunk,rbData,&rbSpare,0);
 283
 284 #ifndef CONFIG_YAFFS_DISABLE_WRITE_VERIFY
 285                                 if(!yaffs_VerifyCompare(data,rbData,spare,&rbSpare))
 286                                                         {
 287                                         // Didn't verify
 288                                         T((TSTR("**>> yaffs write verify failed on chunk %d" TENDSTR), chunk));
 289
 290                                         writeOk = 0;
 291                                 }
 292 #endif
 293
 294                         }
 295                         if(writeOk)
 296                         {
 297                                 // Copy the data into the write buffer.
 298                                 // NB We do this at the end to prevent duplicates in the case of a write error.
 299                                 //Todo
 300                                 yaffs_HandleWriteChunkOk(dev,chunk,data,spare);
 301                         }
 302                         else
 303                         {
 304                                 yaffs_HandleWriteChunkError(dev,chunk);
 305                         }
 306                 }
 307
 308         } while(chunk >= 0 && ! writeOk);
 309
 310         if(attempts > 1)
 311         {
 312                 T((TSTR("**>> yaffs write required %d attempts" TENDSTR),attempts));
 313                 dev->nRetriedWrites+= (attempts - 1);
 314         }
 315
 316         return chunk;
 317 }
 318
 319 ///
 320 // Functions for robustisizing
 321 //
 322 //
 323
 324 static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND)
 325 {
 326         // Ding the blockStatus in the first two pages of the block.
 327
 328         yaffs_Spare spare;
 329
 330         memset(&spare, 0xff,sizeof(yaffs_Spare));
 331
 332         spare.blockStatus = 0;
 333
 334         yaffs_WriteChunkToNAND(dev, blockInNAND * YAFFS_CHUNKS_PER_BLOCK, NULL , &spare);
 335         yaffs_WriteChunkToNAND(dev, blockInNAND * YAFFS_CHUNKS_PER_BLOCK + 1, NULL , &spare);
 336
 337         yaffs_GetBlockInfo(dev,blockInNAND)->blockState = YAFFS_BLOCK_STATE_DEAD;
 338         dev->nRetiredBlocks++;
 339 }
 340
 341
 342
 343 static int yaffs_RewriteBufferedBlock(yaffs_Device *dev)
 344 {
 345         dev->doingBufferedBlockRewrite = 1;
 346         //
 347         //      Remove erased chunks
 348         //  Rewrite existing chunks to a new block
 349         //      Set current write block to the new block
 350
 351         dev->doingBufferedBlockRewrite = 0;
 352
 353         return 1;
 354 }
 355
 356
 357 static void yaffs_HandleReadDataError(yaffs_Device *dev,int chunkInNAND)
 358 {
 359         int blockInNAND = chunkInNAND/YAFFS_CHUNKS_PER_BLOCK;
 360
 361         // Mark the block for retirement
 362         yaffs_GetBlockInfo(dev,blockInNAND)->needsRetiring = 1;
 363         T((TSTR("**>>Block %d marked for retirement" TENDSTR),blockInNAND));
 364
 365
 366         //TODO
 367         // Just do a garbage collection on the affected block then retire the block
 368         // NB recursion
 369 }
 370
 371
 372 static void yaffs_CheckWrittenBlock(yaffs_Device *dev,int chunkInNAND)
 373 {
 374 }
 375
 376 static void yaffs_HandleWriteChunkOk(yaffs_Device *dev,int chunkInNAND,const __u8 *data, const yaffs_Spare *spare)
 377 {
 378 }
 379
 380 static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND, const yaffs_Spare *spare)
 381 {
 382 }
 383
 384 static void yaffs_HandleWriteChunkError(yaffs_Device *dev,int chunkInNAND)
 385 {
 386         int blockInNAND = chunkInNAND/YAFFS_CHUNKS_PER_BLOCK;
 387
 388         // Mark the block for retirement
 389         yaffs_GetBlockInfo(dev,blockInNAND)->needsRetiring = 1;
 390         // Delete the chunk
 391         yaffs_DeleteChunk(dev,chunkInNAND);
 392 }
 393
 394
 395
 396
 397 static int yaffs_VerifyCompare(const __u8 *d0, const __u8 * d1, const yaffs_Spare *s0, const yaffs_Spare *s1)
 398 {
 399
 400
 401         if( memcmp(d0,d1,YAFFS_BYTES_PER_CHUNK) != 0 ||
 402                 s0->tagByte0 != s1->tagByte0 ||
 403                 s0->tagByte1 != s1->tagByte1 ||
 404                 s0->tagByte2 != s1->tagByte2 ||
 405                 s0->tagByte3 != s1->tagByte3 ||
 406                 s0->tagByte4 != s1->tagByte4 ||
 407                 s0->tagByte5 != s1->tagByte5 ||
 408                 s0->tagByte6 != s1->tagByte6 ||
 409                 s0->tagByte7 != s1->tagByte7 ||
 410                 s0->ecc1[0]  != s1->ecc1[0]  ||
 411                 s0->ecc1[1]  != s1->ecc1[1]  ||
 412                 s0->ecc1[2]  != s1->ecc1[2]  ||
 413                 s0->ecc2[0]  != s1->ecc2[0]  ||
 414                 s0->ecc2[1]  != s1->ecc2[1]  ||
 415                 s0->ecc2[2]  != s1->ecc2[2] )
 416                 {
 417                         return 0;
 418                 }
 419
 420         return 1;
 421 }
 422
 423
 424 ///////////////////////// Object management //////////////////
 425 // List of spare objects
 426 // The list is hooked together using the first pointer
 427 // in the object
 428
 429 // static yaffs_Object *yaffs_freeObjects = NULL;
 430
 431 // static int yaffs_nFreeObjects;
 432
 433 // static yaffs_ObjectList *yaffs_allocatedObjectList = NULL;
 434
 435 // static yaffs_ObjectBucket yaffs_objectBucket[YAFFS_NOBJECT_BUCKETS];
 436
 437
 438 static __u16 yaffs_CalcNameSum(const char *name)
 439 {
 440         __u16 sum = 0;
 441         __u16 i = 1;
 442
 443         __u8 *bname = (__u8 *)name;
 444         if(bname)
 445         {
 446                 while (*bname)
 447                 {
 448                         sum += (*bname) * i;
 449                         i++;
 450                         bname++;
 451                 }
 452         }
 453         return sum;
 454 }
 455
 456
 457 void yaffs_CalcECC(const __u8 *data, yaffs_Spare *spare)
 458 {
 459         nand_calculate_ecc (data , spare->ecc1);
 460         nand_calculate_ecc (&data[256] , spare->ecc2);
 461 }
 462
 463 void yaffs_CalcTagsECC(yaffs_Tags *tags)
 464 {
 465         // Calculate an ecc
 466
 467         unsigned char *b = ((yaffs_TagsUnion *)tags)->asBytes;
 468         unsigned  i,j;
 469         unsigned  ecc = 0;
 470         unsigned bit = 0;
 471
 472         tags->ecc = 0;
 473
 474         for(i = 0; i < 8; i++)
 475         {
 476                 for(j = 1; j &0xff; j<<=1)
 477                 {
 478                         bit++;
 479                         if(b[i] & j)
 480                         {
 481                                 ecc ^= bit;
 482                         }
 483                 }
 484         }
 485
 486         tags->ecc = ecc;
 487
 488
 489 }
 490
 491 void yaffs_CheckECCOnTags(yaffs_Tags *tags)
 492 {
 493         unsigned ecc = tags->ecc;
 494
 495         yaffs_CalcTagsECC(tags);
 496
 497         ecc ^= tags->ecc;
 498
 499         if(ecc)
 500         {
 501                 // Needs fixing
 502                 unsigned char *b = ((yaffs_TagsUnion *)tags)->asBytes;
 503
 504                 ecc--;
 505
 506                 b[ecc / 8] ^= (1 << (ecc & 7));
 507
 508                 // Now recvalc the ecc
 509                 yaffs_CalcTagsECC(tags);
 510         }
 511 }
 512
 513
 514 ///////////////////////// TNODES ///////////////////////
 515
 516 // List of spare tnodes
 517 // The list is hooked together using the first pointer
 518 // in the tnode.
 519
 520 //static yaffs_Tnode *yaffs_freeTnodes = NULL;
 521
 522 // static int yaffs_nFreeTnodes;
 523
 524 //static yaffs_TnodeList *yaffs_allocatedTnodeList = NULL;
 525
 526
 527
 528 // yaffs_CreateTnodes creates a bunch more tnodes and
 529 // adds them to the tnode free list.
 530 // Don't use this function directly
 531
 532 static int yaffs_CreateTnodes(yaffs_Device *dev,int nTnodes)
 533 {
 534     int i;
 535     yaffs_Tnode *newTnodes;
 536     yaffs_TnodeList *tnl;
 537
 538     if(nTnodes < 1) return YAFFS_OK;
 539
 540         // make these things
 541
 542     newTnodes = YMALLOC(nTnodes * sizeof(yaffs_Tnode));
 543
 544     if (!newTnodes)
 545     {
 546                 YALERT("Could not malloc tnodes");
 547                 return YAFFS_FAIL;
 548     }
 549
 550     // Hook them into the free list
 551     for(i = 0; i < nTnodes - 1; i++)
 552     {
 553         newTnodes[i].internal[0] = &newTnodes[i+1];
 554     }
 555
 556         newTnodes[nTnodes - 1].internal[0] = dev->freeTnodes;
 557         dev->freeTnodes = newTnodes;
 558         dev->nFreeTnodes+= nTnodes;
 559         dev->nTnodesCreated += nTnodes;
 560
 561         // Now add this bunch of tnodes to a list for freeing up.
 562
 563         tnl = YMALLOC(sizeof(yaffs_TnodeList));
 564         if(!tnl)
 565         {
 566                 YALERT("Could not add tnodes to management list");
 567         }
 568         else
 569         {
 570                 tnl->tnodes = newTnodes;
 571                 tnl->next = dev->allocatedTnodeList;
 572                 dev->allocatedTnodeList = tnl;
 573         }
 574
 575
 576         YINFO("Tnodes created");
 577
 578
 579         return YAFFS_OK;
 580 }
 581
 582
 583 // GetTnode gets us a clean tnode. Tries to make allocate more if we run out
 584 static yaffs_Tnode *yaffs_GetTnode(yaffs_Device *dev)
 585 {
 586         yaffs_Tnode *tn = NULL;
 587
 588         // If there are none left make more
 589         if(!dev->freeTnodes)
 590         {
 591                 yaffs_CreateTnodes(dev,YAFFS_ALLOCATION_NTNODES);
 592         }
 593
 594         if(dev->freeTnodes)
 595         {
 596                 tn = dev->freeTnodes;
 597                 dev->freeTnodes = dev->freeTnodes->internal[0];
 598                 dev->nFreeTnodes--;
 599                 // zero out
 600                 memset(tn,0,sizeof(yaffs_Tnode));
 601         }
 602
 603
 604         return tn;
 605 }
 606
 607
 608 // FreeTnode frees up a tnode and puts it back on the free list
 609 static void yaffs_FreeTnode(yaffs_Device*dev, yaffs_Tnode *tn)
 610 {
 611         tn->internal[0] = dev->freeTnodes;
 612         dev->freeTnodes = tn;
 613         dev->nFreeTnodes++;
 614 }
 615
 616
 617 static void yaffs_DeinitialiseTnodes(yaffs_Device*dev)
 618 {
 619         // Free the list of allocated tnodes
 620
 621         while(dev->allocatedTnodeList)
 622         {
 623                 YFREE(dev->allocatedTnodeList->tnodes);
 624                 dev->allocatedTnodeList =  dev->allocatedTnodeList->next;
 625         }
 626
 627         dev->freeTnodes = NULL;
 628         dev->nFreeTnodes = 0;
 629 }
 630
 631 static void yaffs_InitialiseTnodes(yaffs_Device*dev)
 632 {
 633         dev->allocatedTnodeList = NULL;
 634         dev->freeTnodes = NULL;
 635         dev->nFreeTnodes = 0;
 636         dev->nTnodesCreated = 0;
 637
 638 }
 639
 640 void yaffs_TnodeTest(yaffs_Device *dev)
 641 {
 642
 643         int i;
 644         int j;
 645         yaffs_Tnode *tn[1000];
 646
 647         YINFO("Testing TNodes");
 648
 649         for(j = 0; j < 50; j++)
 650         {
 651                 for(i = 0; i < 1000; i++)
 652                 {
 653                         tn[i] = yaffs_GetTnode(dev);
 654                         if(!tn[i])
 655                         {
 656                                 YALERT("Getting tnode failed");
 657                         }
 658                 }
 659                 for(i = 0; i < 1000; i+=3)
 660                 {
 661                         yaffs_FreeTnode(dev,tn[i]);
 662                         tn[i] = NULL;
 663                 }
 664
 665         }
 666 }
 667
 668 ////////////////// END OF TNODE MANIPULATION ///////////////////////////
 669
 670 /////////////// Functions to manipulate the look-up tree (made up of tnodes)
 671 // The look up tree is represented by the top tnode and the number of topLevel
 672 // in the tree. 0 means only the level 0 tnode is in the tree.
 673
 674
 675 // FindLevel0Tnode finds the level 0 tnode, if one exists.
 676 // Used when reading.....
 677 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device *dev,yaffs_FileStructure *fStruct, __u32 chunkId)
 678 {
 679
 680         yaffs_Tnode *tn = fStruct->top;
 681         __u32 i;
 682         int requiredTallness;
 683         int level = fStruct->topLevel;
 684
 685         // Check sane level and chunk Id
 686         if(level < 0 || level > YAFFS_TNODES_MAX_LEVEL)
 687         {
 688                 char str[50];
 689                 sprintf(str,"Bad level %d",level);
 690                 YALERT(str);
 691                 return NULL;
 692         }
 693
 694         if(chunkId > YAFFS_MAX_CHUNK_ID)
 695         {
 696                 char str[50];
 697                 sprintf(str,"Bad chunkId %d",chunkId);
 698                 YALERT(str);
 699                 return NULL;
 700         }
 701
 702         // First check we're tall enough (ie enough topLevel)
 703
 704         i = chunkId >> (/*dev->chunkGroupBits  + */YAFFS_TNODES_LEVEL0_BITS);
 705         requiredTallness = 0;
 706         while(i)
 707         {
 708                 i >>= YAFFS_TNODES_INTERNAL_BITS;
 709                 requiredTallness++;
 710         }
 711
 712
 713         if(requiredTallness > fStruct->topLevel)
 714         {
 715                 // Not tall enough, so we can't find it, return NULL.
 716                 return NULL;
 717         }
 718
 719
 720         // Traverse down to level 0
 721         while (level > 0 && tn)
 722         {
 723             tn = tn->internal[(chunkId >>(/* dev->chunkGroupBits + */ YAFFS_TNODES_LEVEL0_BITS + (level-1) * YAFFS_TNODES_INTERNAL_BITS)) &
 724                                YAFFS_TNODES_INTERNAL_MASK];
 725                 level--;
 726
 727         }
 728
 729         return tn;
 730 }
 731
 732 // AddOrFindLevel0Tnode finds the level 0 tnode if it exists, otherwise first expands the tree.
 733 // This happens in two steps:
 734 //  1. If the tree isn't tall enough, then make it taller.
 735 //  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
 736 //
 737 // Used when modifying the tree.
 738 //
 739 static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device *dev, yaffs_FileStructure *fStruct, __u32 chunkId)
 740 {
 741
 742         yaffs_Tnode *tn;
 743
 744         int requiredTallness;
 745
 746         __u32 i;
 747         __u32 l;
 748
 749
 750         //T((TSTR("AddOrFind topLevel=%d, chunk=%d"),fStruct->topLevel,chunkId));
 751
 752         // Check sane level and page Id
 753         if(fStruct->topLevel < 0 || fStruct->topLevel > YAFFS_TNODES_MAX_LEVEL)
 754         {
 755                 char str[50];
 756                 sprintf(str,"Bad level %d",fStruct->topLevel);
 757                 YALERT(str);
 758                 return NULL;
 759         }
 760
 761         if(chunkId > YAFFS_MAX_CHUNK_ID)
 762         {
 763                 char str[50];
 764                 sprintf(str,"Bad chunkId %d",chunkId);
 765                 YALERT(str);
 766                 return NULL;
 767         }
 768
 769         // First check we're tall enough (ie enough topLevel)
 770
 771         i = chunkId >> (/*dev->chunkGroupBits + */YAFFS_TNODES_LEVEL0_BITS);
 772         requiredTallness = 0;
 773         while(i)
 774         {
 775                 i >>= YAFFS_TNODES_INTERNAL_BITS;
 776                 requiredTallness++;
 777         }
 778
 779         //T((TSTR(" required=%d"),requiredTallness));
 780
 781
 782         if(requiredTallness > fStruct->topLevel)
 783         {
 784                 // Not tall enough,gotta make the tree taller
 785                 for(i = fStruct->topLevel; i < requiredTallness; i++)
 786                 {
 787                         //T((TSTR(" add new top")));
 788
 789                         tn = yaffs_GetTnode(dev);
 790
 791                         if(tn)
 792                         {
 793                                 tn->internal[0] = fStruct->top;
 794                                 fStruct->top = tn;
 795                         }
 796                         else
 797                         {
 798                                 YALERT("No more tnodes");
 799                         }
 800                 }
 801
 802                 fStruct->topLevel = requiredTallness;
 803         }
 804
 805
 806         // Traverse down to level 0, adding anything we need
 807
 808         l = fStruct->topLevel;
 809         tn = fStruct->top;
 810         while (l > 0 && tn)
 811         {
 812                 i = (chunkId >> (/*dev->chunkGroupBits + */YAFFS_TNODES_LEVEL0_BITS + (l-1) * YAFFS_TNODES_INTERNAL_BITS)) &
 813                                YAFFS_TNODES_INTERNAL_MASK;
 814
 815                 //T((TSTR(" [%d:%d]"),l,i));
 816
 817             if(!tn->internal[i])
 818             {
 819                 //T((TSTR(" added")));
 820
 821                 tn->internal[i] = yaffs_GetTnode(dev);
 822             }
 823
 824             tn =        tn->internal[i];
 825                 l--;
 826
 827         }
 828
 829         //TSTR(TENDSTR)));
 830
 831         return tn;
 832 }
 833
 834 // DeleteWorker scans backwards through the tnode tree and deletes all the
 835 // chunks and tnodes in the file
 836
 837 static void 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_Tags tags;
 843         int found;
 844         int chunkDeleted;
 845
 846
 847         if(tn)
 848         {
 849                 if(level > 0)
 850                 {
 851
 852                         for(i = YAFFS_NTNODES_INTERNAL -1; i >= 0 && (!limit || *limit > 0); i--)
 853                         {
 854                             if(tn->internal[i])
 855                         {
 856                                         yaffs_DeleteWorker(in,tn->internal[i],level - 1,
 857                                                                                 (chunkOffset << YAFFS_TNODES_INTERNAL_BITS ) + i ,limit);
 858                                         yaffs_FreeTnode(in->myDev,tn->internal[i]);
 859                                 tn->internal[i] = NULL;
 860                             }
 861
 862                         }
 863                 }
 864                 else if(level == 0)
 865                 {
 866                         for(i = YAFFS_NTNODES_LEVEL0 -1; i >= 0; i--) //NB Don't apply the limit here, always delete a whole level0
 867                         {
 868                             if(tn->level0[i])
 869                         {
 870                                         int j;
 871
 872                                         chunkInInode = (chunkOffset << YAFFS_TNODES_LEVEL0_BITS ) + i;
 873
 874                                         theChunk =  tn->level0[i] << in->myDev->chunkGroupBits;
 875
 876                                         // Now we need to search for it
 877                                         for(j = 0,found = 0; theChunk && j < in->myDev->chunkGroupSize && !found; j++)
 878                                         {
 879                                                 yaffs_ReadChunkTagsFromNAND(in->myDev,theChunk,&tags,&chunkDeleted);
 880                                                 if(yaffs_TagsMatch(&tags,in->objectId,chunkInInode,chunkDeleted))
 881                                                 {
 882                                                         // found it;
 883                                                         found = 1;
 884
 885                                                 }
 886                                                 else
 887                                                 {
 888                                                         theChunk++;
 889                                                 }
 890                                         }
 891
 892                                         if(found)
 893                                         {
 894                                                 yaffs_DeleteChunk(in->myDev,theChunk);
 895                                                 in->nDataChunks--;
 896                                                 if(limit)
 897                                                 {
 898                                                         *limit = *limit-1;
 899                                                 }
 900
 901                                         }
 902
 903                                 tn->level0[i] = 0;
 904                             }
 905
 906                         }
 907
 908                 }
 909
 910         }
 911
 912 }
 913
 914
 915
 916
 917 // Pruning removes any part of the file structure tree that is beyond the
 918 // bounds of the file (ie that does not point to chunks).
 919 //
 920 // A file should only get pruned when its size is reduced.
 921 //
 922 // Before pruning, the chunks must be pulled from the tree and the
 923 // level 0 tnode entries must be zeroed out.
 924 // Could also use this for file deletion, but that's probably better handled
 925 // by a special case.
 926
 927 // yaffs_PruneWorker should only be called by yaffs_PruneFileStructure()
 928
 929 static yaffs_Tnode *yaffs_PruneWorker(yaffs_Device *dev, yaffs_Tnode *tn, __u32 level, int del0)
 930 {
 931         int i;
 932         int hasData;
 933
 934         if(tn)
 935         {
 936                 hasData = 0;
 937
 938                 for(i = 0; i < YAFFS_NTNODES_INTERNAL; i++)
 939                 {
 940                     if(tn->internal[i] && level > 0)
 941                     {
 942                         tn->internal[i] = yaffs_PruneWorker(dev,tn->internal[i],level - 1, ( i == 0) ? del0 : 1);
 943                     }
 944
 945                     if(tn->internal[i])
 946                     {
 947                         hasData++;
 948                         }
 949                 }
 950
 951                 if(hasData == 0 && del0)
 952                 {
 953                         // Free and return NULL
 954
 955                         yaffs_FreeTnode(dev,tn);
 956                         tn = NULL;
 957                 }
 958
 959         }
 960
 961         return tn;
 962
 963 }
 964
 965 static int yaffs_PruneFileStructure(yaffs_Device *dev, yaffs_FileStructure *fStruct)
 966 {
 967         int i;
 968         int hasData;
 969         int done = 0;
 970         yaffs_Tnode *tn;
 971
 972         if(fStruct->topLevel > 0)
 973         {
 974                 fStruct->top = yaffs_PruneWorker(dev,fStruct->top, fStruct->topLevel,0);
 975
 976                 // Now we have a tree with all the non-zero branches NULL but the height
 977                 // is the same as it was.
 978                 // Let's see if we can trim internal tnodes to shorten the tree.
 979                 // We can do this if only the 0th element in the tnode is in use
 980                 // (ie all the non-zero are NULL)
 981
 982                 while(fStruct->topLevel && !done)
 983                 {
 984                         tn = fStruct->top;
 985
 986                         hasData = 0;
 987                         for(i = 1; i <YAFFS_NTNODES_INTERNAL; i++)
 988                         {
 989                                 if(tn->internal[i])
 990                         {
 991                                 hasData++;
 992                                 }
 993                         }
 994
 995                         if(!hasData)
 996                         {
 997                                 fStruct->top = tn->internal[0];
 998                                 fStruct->topLevel--;
 999                                 yaffs_FreeTnode(dev,tn);
1000                         }
1001                         else
1002                         {
1003                                 done = 1;
1004                         }
1005                 }
1006         }
1007
1008         return YAFFS_OK;
1009 }
1010
1011
1012
1013
1014 /////////////////////// End of File Structure functions. /////////////////
1015
1016 // yaffs_CreateFreeObjects creates a bunch more objects and
1017 // adds them to the object free list.
1018 static int yaffs_CreateFreeObjects(yaffs_Device *dev, int nObjects)
1019 {
1020     int i;
1021     yaffs_Object *newObjects;
1022     yaffs_ObjectList *list;
1023
1024     if(nObjects < 1) return YAFFS_OK;
1025
1026         // make these things
1027
1028     newObjects = YMALLOC(nObjects * sizeof(yaffs_Object));
1029
1030     if (!newObjects)
1031     {
1032                 YALERT("Could not allocate more objects");
1033                 return YAFFS_FAIL;
1034     }
1035
1036     // Hook them into the free list
1037     for(i = 0; i < nObjects - 1; i++)
1038     {
1039         (yaffs_Object *)newObjects[i].siblings.next = &newObjects[i+1];
1040     }
1041
1042         newObjects[nObjects - 1].siblings.next = (void *)dev->freeObjects;
1043         dev->freeObjects = newObjects;
1044         dev->nFreeObjects+= nObjects;
1045         dev->nObjectsCreated+= nObjects;
1046
1047         // Now add this bunch of Objects to a list for freeing up.
1048
1049         list = YMALLOC(sizeof(yaffs_ObjectList));
1050         if(!list)
1051         {
1052                 YALERT("Could not add Objects to management list");
1053         }
1054         else
1055         {
1056                 list->objects = newObjects;
1057                 list->next = dev->allocatedObjectList;
1058                 dev->allocatedObjectList = list;
1059         }
1060
1061
1062         YINFO("Objects created");
1063
1064
1065         return YAFFS_OK;
1066 }
1067
1068
1069 // AllocateEmptyObject gets us a clean Object. Tries to make allocate more if we run out
1070 static yaffs_Object *yaffs_AllocateEmptyObject(yaffs_Device *dev)
1071 {
1072         yaffs_Object *tn = NULL;
1073
1074         // If there are none left make more
1075         if(!dev->freeObjects)
1076         {
1077                 yaffs_CreateFreeObjects(dev,YAFFS_ALLOCATION_NOBJECTS);
1078         }
1079
1080         if(dev->freeObjects)
1081         {
1082                 tn = dev->freeObjects;
1083                 dev->freeObjects = (yaffs_Object *)(dev->freeObjects->siblings.next);
1084                 dev->nFreeObjects--;
1085
1086                 // Now sweeten it up...
1087
1088                 memset(tn,0,sizeof(yaffs_Object));
1089                 tn->myDev = dev;
1090                 tn->chunkId = -1;
1091                 tn->variantType = YAFFS_OBJECT_TYPE_UNKNOWN;
1092                 INIT_LIST_HEAD(&(tn->hardLinks));
1093                 INIT_LIST_HEAD(&(tn->hashLink));
1094                 INIT_LIST_HEAD(&tn->siblings);
1095
1096                 // Add it to the lost and found directory.
1097                 // NB Can't put root or lostNFound in lostNFound so
1098                 // check if lostNFound exists first
1099                 if(dev->lostNFoundDir)
1100                 {
1101                         yaffs_AddObjectToDirectory(dev->lostNFoundDir,tn);
1102                 }
1103         }
1104
1105
1106         return tn;
1107 }
1108
1109 static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device *dev,int number,__u32 mode)
1110 {
1111
1112         yaffs_Object *obj = yaffs_CreateNewObject(dev,number,YAFFS_OBJECT_TYPE_DIRECTORY);
1113         if(obj)
1114         {
1115                 obj->fake = 1;                  // it is fake so it has no NAND presence...
1116                 obj->renameAllowed= 0;  // ... and we're not allowed to rename it...
1117                 obj->unlinkAllowed= 0;  // ... or unlink it
1118                 obj->deleted = 0;
1119                 obj->unlinked = 0;
1120                 obj->st_mode = mode;
1121                 obj->myDev = dev;
1122                 obj->chunkId = 0; // Not a valid chunk.
1123         }
1124
1125         return obj;
1126
1127 }
1128
1129
1130 static void yaffs_UnhashObject(yaffs_Object *tn)
1131 {
1132         int bucket;
1133         yaffs_Device *dev = tn->myDev;
1134
1135
1136         // If it is still linked into the bucket list, free from the list
1137         if(!list_empty(&tn->hashLink))
1138         {
1139                 list_del_init(&tn->hashLink);
1140                 bucket =  yaffs_HashFunction(tn->objectId);
1141                 dev->objectBucket[bucket].count--;
1142         }
1143
1144 }
1145
1146
1147 // FreeObject frees up a Object and puts it back on the free list
1148 static void yaffs_FreeObject(yaffs_Object *tn)
1149 {
1150
1151         yaffs_Device *dev = tn->myDev;
1152
1153         yaffs_UnhashObject(tn);
1154
1155         // Link into the free list.
1156         (yaffs_Object *)(tn->siblings.next) = dev->freeObjects;
1157         dev->freeObjects = tn;
1158         dev->nFreeObjects++;
1159 }
1160
1161
1162
1163
1164 static void yaffs_DeinitialiseObjects(yaffs_Device *dev)
1165 {
1166         // Free the list of allocated Objects
1167
1168         while( dev->allocatedObjectList)
1169         {
1170                 YFREE(dev->allocatedObjectList->objects);
1171                 dev->allocatedObjectList =  dev->allocatedObjectList->next;
1172         }
1173
1174         dev->freeObjects = NULL;
1175         dev->nFreeObjects = 0;
1176 }
1177
1178 static void yaffs_InitialiseObjects(yaffs_Device *dev)
1179 {
1180         int i;
1181
1182         dev->allocatedObjectList = NULL;
1183         dev->freeObjects = NULL;
1184         dev->nFreeObjects = 0;
1185
1186         for(i = 0; i < YAFFS_NOBJECT_BUCKETS; i++)
1187         {
1188                 INIT_LIST_HEAD(&dev->objectBucket[i].list);
1189                 dev->objectBucket[i].count = 0;
1190         }
1191
1192 }
1193
1194
1195
1196
1197
1198
1199 int yaffs_FindNiceObjectBucket(yaffs_Device *dev)
1200 {
1201         static int x = 0;
1202         int i;
1203         int l = 999;
1204         int lowest = 999999;
1205
1206
1207         // First let's see if we can find one that's empty.
1208
1209         for(i = 0; i < 10 && lowest > 0; i++)
1210          {
1211                 x++;
1212                 x %=  YAFFS_NOBJECT_BUCKETS;
1213                 if(dev->objectBucket[x].count < lowest)
1214                 {
1215                         lowest = dev->objectBucket[x].count;
1216                         l = x;
1217                 }
1218
1219         }
1220
1221         // If we didn't find an empty list, then try
1222         // looking a bit further for a short one
1223
1224         for(i = 0; i < 10 && lowest > 3; i++)
1225          {
1226                 x++;
1227                 x %=  YAFFS_NOBJECT_BUCKETS;
1228                 if(dev->objectBucket[x].count < lowest)
1229                 {
1230                         lowest = dev->objectBucket[x].count;
1231                         l = x;
1232                 }
1233
1234         }
1235
1236         return l;
1237 }
1238
1239 static int yaffs_CreateNewObjectNumber(yaffs_Device *dev)
1240 {
1241         int bucket = yaffs_FindNiceObjectBucket(dev);
1242
1243         // Now find an object value that has not already been taken
1244         // by scanning the list.
1245
1246         int found = 0;
1247         struct list_head *i;
1248
1249         int n = bucket;
1250
1251         //yaffs_CheckObjectHashSanity();
1252
1253         while(!found)
1254         {
1255                 found = 1;
1256                 n +=  YAFFS_NOBJECT_BUCKETS;
1257                 if(1 ||dev->objectBucket[bucket].count > 0)
1258                 {
1259                         list_for_each(i,&dev->objectBucket[bucket].list)
1260                         {
1261                                 // If there is already one in the list
1262                                 if(list_entry(i, yaffs_Object,hashLink)->objectId == n)
1263                                 {
1264                                         found = 0;
1265                                 }
1266                         }
1267                 }
1268         }
1269
1270         //T(("bucket %d count %d inode %d\n",bucket,yaffs_objectBucket[bucket].count,n);
1271
1272         return n;
1273 }
1274
1275 void yaffs_HashObject(yaffs_Object *in)
1276 {
1277         int bucket = yaffs_HashFunction(in->objectId);
1278         yaffs_Device *dev = in->myDev;
1279
1280         if(!list_empty(&in->hashLink))
1281         {
1282                 YINFO("!!!");
1283         }
1284
1285
1286         list_add(&in->hashLink,&dev->objectBucket[bucket].list);
1287         dev->objectBucket[bucket].count++;
1288
1289 }
1290
1291 yaffs_Object *yaffs_FindObjectByNumber(yaffs_Device *dev,int number)
1292 {
1293         int bucket = yaffs_HashFunction(number);
1294         struct list_head *i;
1295         yaffs_Object *in;
1296
1297         list_for_each(i,&dev->objectBucket[bucket].list)
1298         {
1299                 // Look if it is in the list
1300                 in = list_entry(i, yaffs_Object,hashLink);
1301                 if(in->objectId == number)
1302                 {
1303                         return in;
1304                 }
1305         }
1306
1307         return NULL;
1308 }
1309
1310
1311
1312 yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type)
1313 {
1314
1315         yaffs_Object *theObject;
1316
1317         if(number < 0)
1318         {
1319                 number = yaffs_CreateNewObjectNumber(dev);
1320         }
1321
1322         theObject = yaffs_AllocateEmptyObject(dev);
1323
1324         if(theObject)
1325         {
1326                 theObject->fake = 0;
1327                 theObject->renameAllowed = 1;
1328                 theObject->unlinkAllowed = 1;
1329                 theObject->objectId = number;
1330                 yaffs_HashObject(theObject);
1331                 theObject->variantType = type;
1332                 theObject->st_atime = theObject->st_mtime =     theObject->st_ctime = CURRENT_TIME;
1333
1334                 switch(type)
1335                 {
1336                         case YAFFS_OBJECT_TYPE_FILE:
1337                                 theObject->variant.fileVariant.fileSize = 0;
1338                                 theObject->variant.fileVariant.scannedFileSize = 0;
1339                                 theObject->variant.fileVariant.topLevel = 0;
1340                                 theObject->variant.fileVariant.top  = yaffs_GetTnode(dev);
1341                                 break;
1342                         case YAFFS_OBJECT_TYPE_DIRECTORY:
1343                                 INIT_LIST_HEAD(&theObject->variant.directoryVariant.children);
1344                                 break;
1345                         case YAFFS_OBJECT_TYPE_SYMLINK:
1346                                 // No action required
1347                                 break;
1348                         case YAFFS_OBJECT_TYPE_HARDLINK:
1349                                 // No action required
1350                                 break;
1351                         case YAFFS_OBJECT_TYPE_SPECIAL:
1352                                 // No action required
1353                                 break;
1354                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1355                                 // todo this should not happen
1356                                 break;
1357                 }
1358         }
1359
1360         return theObject;
1361 }
1362
1363 yaffs_Object *yaffs_FindOrCreateObjectByNumber(yaffs_Device *dev, int number,yaffs_ObjectType type)
1364 {
1365         yaffs_Object *theObject = NULL;
1366
1367         if(number > 0)
1368         {
1369                 theObject = yaffs_FindObjectByNumber(dev,number);
1370         }
1371
1372         if(!theObject)
1373         {
1374                 theObject = yaffs_CreateNewObject(dev,number,type);
1375         }
1376
1377         return theObject;
1378
1379 }
1380
1381 char *yaffs_CloneString(const char *str)
1382 {
1383         char *newStr = NULL;
1384
1385         if(str && *str)
1386         {
1387                 newStr = YMALLOC(strlen(str) + 1);
1388                 strcpy(newStr,str);
1389         }
1390
1391         return newStr;
1392
1393 }
1394
1395 //
1396 // Mknod (create) a new object.
1397 // equivalentObject only has meaning for a hard link;
1398 // aliasString only has meaning for a sumlink.
1399 // rdev only has meaning for devices (a subset of special objects)
1400 yaffs_Object *yaffs_MknodObject( yaffs_ObjectType type,
1401                                                                  yaffs_Object *parent,
1402                                                                  const char *name,
1403                                                                  __u32 mode,
1404                                                                  __u32 uid,
1405                                                                  __u32 gid,
1406                                                                  yaffs_Object *equivalentObject,
1407                                                                  const char *aliasString,
1408                                                                  __u32 rdev)
1409 {
1410         yaffs_Object *in;
1411
1412         yaffs_Device *dev = parent->myDev;
1413
1414         // Check if the entry exists. If it does then fail the call since we don't want a dup.
1415         if(yaffs_FindObjectByName(parent,name))
1416         {
1417                 return NULL;
1418         }
1419
1420         in = yaffs_CreateNewObject(dev,-1,type);
1421
1422         if(in)
1423         {
1424                 in->chunkId = -1;
1425                 in->valid = 1;
1426                 in->variantType = type;
1427
1428                 in->st_mode  = mode;
1429                 in->st_rdev  = rdev;
1430                 in->st_uid   = uid;
1431                 in->st_gid   = gid;
1432                 in->st_atime =  in->st_mtime =  in->st_ctime = CURRENT_TIME;
1433
1434                 in->nDataChunks = 0;
1435
1436                 in->sum = yaffs_CalcNameSum(name);
1437                 in->dirty = 1;
1438
1439                 yaffs_AddObjectToDirectory(parent,in);
1440
1441                 in->myDev = parent->myDev;
1442
1443
1444                 switch(type)
1445                 {
1446                         case YAFFS_OBJECT_TYPE_SYMLINK:
1447                                 in->variant.symLinkVariant.alias = yaffs_CloneString(aliasString);
1448                                 break;
1449                         case YAFFS_OBJECT_TYPE_HARDLINK:
1450                                 in->variant.hardLinkVariant.equivalentObject = equivalentObject;
1451                                 in->variant.hardLinkVariant.equivalentObjectId = equivalentObject->objectId;
1452                                 list_add(&in->hardLinks,&equivalentObject->hardLinks);
1453                                 break;
1454                         case YAFFS_OBJECT_TYPE_FILE: // do nothing
1455                         case YAFFS_OBJECT_TYPE_DIRECTORY: // do nothing
1456                         case YAFFS_OBJECT_TYPE_SPECIAL: // do nothing
1457                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1458                                 break;
1459                 }
1460
1461                 if(yaffs_GetNumberOfFreeChunks(dev) <= 0 ||
1462                    yaffs_UpdateObjectHeader(in,name,0) < 0)
1463                 {
1464                         // Could not create the object header, fail the creation
1465                         yaffs_UnlinkWorker(in);
1466                         in = NULL;
1467                 }
1468
1469         }
1470
1471         return in;
1472 }
1473
1474 yaffs_Object *yaffs_MknodFile(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid)
1475 {
1476         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_FILE,parent,name,mode,uid,gid,NULL,NULL,0);
1477 }
1478
1479 yaffs_Object *yaffs_MknodDirectory(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid)
1480 {
1481         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_DIRECTORY,parent,name,mode,uid,gid,NULL,NULL,0);
1482 }
1483
1484 yaffs_Object *yaffs_MknodSpecial(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid, __u32 rdev)
1485 {
1486         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_DIRECTORY,parent,name,mode,uid,gid,NULL,NULL,rdev);
1487 }
1488
1489 yaffs_Object *yaffs_MknodSymLink(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid,const char *alias)
1490 {
1491         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SYMLINK,parent,name,mode,uid,gid,NULL,alias,0);
1492 }
1493
1494 // NB yaffs_Link returns the object id of the equivalent object.
1495 yaffs_Object *yaffs_Link(yaffs_Object *parent, const char *name, yaffs_Object *equivalentObject)
1496 {
1497         // Get the real object in case we were fed a hard link as an equivalent object
1498         equivalentObject = yaffs_GetEquivalentObject(equivalentObject);
1499
1500         if(yaffs_MknodObject(YAFFS_OBJECT_TYPE_HARDLINK,parent,name,0,0,0,equivalentObject,NULL,0))
1501         {
1502                 return equivalentObject;
1503         }
1504         else
1505         {
1506                 return NULL;
1507         }
1508
1509 }
1510
1511
1512 static int yaffs_ChangeObjectName(yaffs_Object *obj, yaffs_Object *newDir, const char *newName)
1513 {
1514         int unlinkOp;
1515
1516         if(newDir == NULL)
1517         {
1518                 newDir = obj->parent; // use the old directory
1519         }
1520
1521         unlinkOp = (newDir == obj->myDev->unlinkedDir && obj->variantType == YAFFS_OBJECT_TYPE_FILE);
1522
1523         // If the object is a file going into the unlinked directory, then it is OK to just stuff it in since
1524         // duplicate names are allowed.
1525         // Otherwise only proceed if the new name does not exist and if we're putting it into a directory.
1526         if( unlinkOp||
1527             (!yaffs_FindObjectByName(newDir,newName) &&
1528              newDir->variantType == YAFFS_OBJECT_TYPE_DIRECTORY))
1529         {
1530                 obj->sum = yaffs_CalcNameSum(newName);
1531                 obj->dirty = 1;
1532
1533                 yaffs_AddObjectToDirectory(newDir,obj);
1534
1535                 if(unlinkOp) obj->unlinked = 1;
1536
1537
1538                 if(yaffs_UpdateObjectHeader(obj,newName,0) >= 0)
1539                 {
1540                         return YAFFS_OK;
1541                 }
1542         }
1543
1544         return YAFFS_FAIL;
1545 }
1546
1547 int yaffs_RenameObject(yaffs_Object *oldDir, const char *oldName, yaffs_Object *newDir, const char *newName)
1548 {
1549         yaffs_Object *obj;
1550
1551         obj = yaffs_FindObjectByName(oldDir,oldName);
1552         if(obj && obj->renameAllowed)
1553         {
1554                 return yaffs_ChangeObjectName(obj,newDir,newName);
1555         }
1556         return YAFFS_FAIL;
1557 }
1558
1559
1560
1561 static int yaffs_CheckObjectHashSanity(yaffs_Device *dev)
1562 {
1563         // Scan the buckets and check that the lists
1564         // have as many members as the count says there are
1565         int bucket;
1566         int countEm;
1567         struct list_head *j;
1568         int ok = YAFFS_OK;
1569
1570         for(bucket = 0; bucket < YAFFS_NOBJECT_BUCKETS; bucket++)
1571         {
1572                 countEm = 0;
1573
1574                 list_for_each(j,&dev->objectBucket[bucket].list)
1575                 {
1576                         countEm++;
1577                 }
1578
1579                 if(countEm != dev->objectBucket[bucket].count)
1580                 {
1581                         YALERT("Inode hash inconsistency");
1582                         ok = YAFFS_FAIL;
1583                 }
1584         }
1585
1586         return ok;
1587 }
1588
1589 void yaffs_ObjectTest(yaffs_Device *dev)
1590 {
1591         yaffs_Object *in[1000];
1592         int inNo[1000];
1593         yaffs_Object *inold[1000];
1594         int i;
1595         int j;
1596
1597         memset(in,0,1000*sizeof(yaffs_Object *));
1598         memset(inold,0,1000*sizeof(yaffs_Object *));
1599
1600         yaffs_CheckObjectHashSanity(dev);
1601
1602         for(j = 0; j < 10; j++)
1603         {
1604                 //T(("%d\n",j));
1605
1606                 for(i = 0; i < 1000; i++)
1607                 {
1608                         in[i] = yaffs_CreateNewObject(dev,-1,YAFFS_OBJECT_TYPE_FILE);
1609                         if(!in[i])
1610                         {
1611                                 YINFO("No more inodes");
1612                         }
1613                         else
1614                         {
1615                                 inNo[i] = in[i]->objectId;
1616                         }
1617                 }
1618
1619                 for(i = 0; i < 1000; i++)
1620                 {
1621                         if(yaffs_FindObjectByNumber(dev,inNo[i]) != in[i])
1622                         {
1623                                 //T(("Differnce in look up test\n"));
1624                         }
1625                         else
1626                         {
1627                                 // T(("Look up ok\n"));
1628                         }
1629                 }
1630
1631                 yaffs_CheckObjectHashSanity(dev);
1632
1633                 for(i = 0; i < 1000; i+=3)
1634                 {
1635                         yaffs_FreeObject(in[i]);
1636                         in[i] = NULL;
1637                 }
1638
1639
1640                 yaffs_CheckObjectHashSanity(dev);
1641         }
1642
1643 }
1644
1645
1646
1647 /////////////////////////// Block Management and Page Allocation ///////////////////
1648
1649
1650 static int yaffs_InitialiseBlocks(yaffs_Device *dev,int nBlocks)
1651 {
1652         dev->allocationBlock = -1; // force it to get a new one
1653         //Todo we're assuming the malloc will pass.
1654         dev->blockInfo = YMALLOC(nBlocks * sizeof(yaffs_BlockInfo));
1655         if(dev->blockInfo)
1656         {
1657                 memset(dev->blockInfo,0,nBlocks * sizeof(yaffs_BlockInfo));
1658                 return YAFFS_OK;
1659         }
1660         return YAFFS_FAIL;
1661
1662 }
1663
1664 static void yaffs_DeinitialiseBlocks(yaffs_Device *dev)
1665 {
1666         YFREE(dev->blockInfo);
1667 }
1668
1669 // FindDiretiestBlock is used to select the dirtiest block (or close enough)
1670 // for garbage collection.
1671
1672 static int yaffs_FindDirtiestBlock(yaffs_Device *dev)
1673 {
1674
1675         int b = dev->currentDirtyChecker;
1676
1677         int i;
1678         int dirtiest = -1;
1679         int pagesInUse = 100; // silly big number
1680         yaffs_BlockInfo *bi;
1681
1682         for(i = dev->startBlock; i <= dev->endBlock && pagesInUse > 2 ; i++)
1683         {
1684                 b++;
1685                 if (b > dev->endBlock)
1686                 {
1687                         b =  dev->startBlock;
1688                 }
1689
1690                 bi = yaffs_GetBlockInfo(dev,b);
1691
1692                 if(bi->blockState == YAFFS_BLOCK_STATE_FULL &&
1693                    bi->pagesInUse < pagesInUse)
1694                 {
1695                         dirtiest = b;
1696                         pagesInUse = bi->pagesInUse;
1697                 }
1698         }
1699
1700         dev->currentDirtyChecker = b;
1701
1702         return dirtiest;
1703 }
1704
1705
1706 static void yaffs_BlockBecameDirty(yaffs_Device *dev,int blockNo)
1707 {
1708         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,blockNo);
1709
1710         int erasedOk = 0;
1711
1712         // If the block is still healthy erase it and mark as clean.
1713         // If the block has had a data failure, then retire it.
1714         bi->blockState = YAFFS_BLOCK_STATE_DIRTY;
1715
1716         if(!bi->needsRetiring)
1717         {
1718                 erasedOk = yaffs_EraseBlockInNAND(dev,blockNo);
1719                 if(!erasedOk)
1720                 {
1721                         T((TSTR("**>> Erasure failed %d" TENDSTR),blockNo));
1722                 }
1723         }
1724
1725         if( erasedOk )
1726         {
1727                 bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
1728                 dev->nErasedBlocks++;
1729                 bi->pagesInUse = 0;
1730                 bi->pageBits = 0;
1731
1732                 T((TSTR("Erased block %d" TENDSTR),blockNo));
1733         }
1734         else
1735         {
1736                 yaffs_RetireBlock(dev,blockNo);
1737                 T((TSTR("**>> Block %d retired" TENDSTR),blockNo));
1738         }
1739 }
1740
1741
1742 static int yaffs_FindBlockForAllocation(yaffs_Device *dev)
1743 {
1744         int i;
1745         yaffs_BlockInfo *bi;
1746
1747         if(dev->nErasedBlocks < 1)
1748         {
1749                 // Hoosterman we've got a problem.
1750                 // Can't get space to gc
1751                 return -1;
1752         }
1753
1754         // Find an empty block.
1755
1756         for(i = dev->startBlock; i <= dev->endBlock; i++)
1757         {
1758                 bi = yaffs_GetBlockInfo(dev,i);
1759                 if(bi->blockState == YAFFS_BLOCK_STATE_EMPTY)
1760                 {
1761                         bi->blockState = YAFFS_BLOCK_STATE_ALLOCATING;
1762                         dev->nErasedBlocks--;
1763                         return i;
1764                 }
1765         }
1766
1767         return -1;
1768 }
1769
1770
1771
1772 static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve)
1773 {
1774         int retVal;
1775         yaffs_BlockInfo *bi;
1776
1777         if(dev->allocationBlock < 0)
1778         {
1779                 // Get next block to allocate off
1780                 dev->allocationBlock = yaffs_FindBlockForAllocation(dev);
1781                 dev->allocationPage = 0;
1782         }
1783
1784         if(!useReserve &&  dev->nErasedBlocks <= YAFFS_RESERVED_BLOCKS)
1785         {
1786                 // Not enough space to allocate unless we're allowed to use the reserve.
1787                 return -1;
1788         }
1789
1790         // Next page please....
1791         if(dev->allocationBlock >= 0)
1792         {
1793                 bi = yaffs_GetBlockInfo(dev,dev->allocationBlock);
1794
1795                 retVal = (dev->allocationBlock * YAFFS_CHUNKS_PER_BLOCK) +
1796                                   dev->allocationPage;
1797                 bi->pagesInUse++;
1798                 bi->pageBits |= (1 << (dev->allocationPage));
1799
1800                 dev->allocationPage++;
1801
1802                 dev->nFreeChunks--;
1803
1804                 // If the block is full set the state to full
1805                 if(dev->allocationPage >= YAFFS_CHUNKS_PER_BLOCK)
1806                 {
1807                         bi->blockState = YAFFS_BLOCK_STATE_FULL;
1808                         dev->allocationBlock = -1;
1809                 }
1810
1811
1812                 return retVal;
1813
1814         }
1815         T((TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));
1816
1817         return -1;
1818 }
1819
1820
1821 int  yaffs_GarbageCollectBlock(yaffs_Device *dev,int block)
1822 {
1823         int oldChunk;
1824         int newChunk;
1825         __u32 mask;
1826
1827
1828         yaffs_Spare spare;
1829         yaffs_Tags  tags;
1830                 __u8  buffer[YAFFS_BYTES_PER_CHUNK];
1831
1832         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,block);
1833
1834         yaffs_Object *object;
1835
1836         //T(("Collecting block %d n %d bits %x\n",block, bi->pagesInUse, bi->pageBits));
1837
1838         for(mask = 1,oldChunk = block * YAFFS_CHUNKS_PER_BLOCK;
1839             mask && bi->pageBits;
1840             mask <<= 1, oldChunk++ )
1841         {
1842                 if(bi->pageBits & mask)
1843                 {
1844
1845                         // This page is in use and needs to be copied off
1846
1847                         dev->nGCCopies++;
1848
1849                         //T(("copying page %x from %d to %d\n",mask,oldChunk,newChunk));
1850
1851                         yaffs_ReadChunkFromNAND(dev,oldChunk,buffer, &spare,1);
1852
1853                         yaffs_GetTagsFromSpare(&spare,&tags);
1854                         tags.serialNumber++;
1855                         yaffs_LoadTagsIntoSpare(&spare,&tags);
1856
1857 #if 0
1858                         newChunk = yaffs_AllocatePage(dev,1);
1859                         if(newChunk < 0)
1860                         {
1861                                 return YAFFS_FAIL;
1862                         }
1863
1864                         yaffs_WriteChunkToNAND(dev,newChunk, buffer, &spare);
1865
1866 #else
1867                         newChunk = yaffs_WriteNewChunkToNAND(dev, buffer, &spare,1);
1868 #endif
1869                         if(newChunk < 0)
1870                         {
1871                                 return YAFFS_FAIL;
1872                         }
1873
1874                         object = yaffs_FindObjectByNumber(dev,tags.objectId);
1875
1876                         // Ok, now fix up the Tnodes etc.
1877
1878                         if(tags.chunkId == 0)
1879                         {
1880                                 // It's a header
1881                                 object->chunkId = newChunk;
1882                         }
1883                         else
1884                         {
1885                                 // It's a data chunk
1886                                 yaffs_PutChunkIntoFile(object, tags.chunkId, newChunk,0);
1887
1888                         }
1889
1890                         yaffs_DeleteChunk(dev,oldChunk);
1891
1892                 }
1893         }
1894
1895         return YAFFS_OK;
1896 }
1897
1898
1899 static yaffs_Object *yaffs_FindDeletedUnlinkedFile(yaffs_Device *dev)
1900 {
1901         // todo find a file to delete
1902         struct list_head *i;
1903         yaffs_Object *l;
1904
1905
1906         // To the free chunks add the chunks that are in the deleted unlinked files.
1907         list_for_each(i,&dev->unlinkedDir->variant.directoryVariant.children)
1908         {
1909                 l = list_entry(i, yaffs_Object,siblings);
1910                 if(l->deleted)
1911                 {
1912                         return l;
1913                 }
1914         }
1915         return NULL;
1916 }
1917
1918 static void yaffs_DoUnlinkedFileDeletion(yaffs_Device *dev)
1919 {
1920         // This does background deletion on unlinked files.. only deleted ones.
1921         // If we don't have a file we're working on then find one
1922         if(!dev->unlinkedDeletion && dev->nDeletedFiles > 0)
1923         {
1924                 dev->unlinkedDeletion = yaffs_FindDeletedUnlinkedFile(dev);
1925         }
1926
1927         // OK, we're working on a file...
1928         if(dev->unlinkedDeletion)
1929         {
1930                 yaffs_Object *obj = dev->unlinkedDeletion;
1931                 int limit;
1932                 limit = 50; // Max number of chunks to delete in a file. NB this can be exceeded, but not by much.
1933                 yaffs_DeleteWorker(obj, obj->variant.fileVariant.top, obj->variant.fileVariant.topLevel, 0,&limit);
1934                 if(obj->nDataChunks == 0)
1935                 {
1936                         // Done all the deleting of data chunks.
1937                         // Now dump the header and clean up
1938                         yaffs_DoGenericObjectDeletion(dev->unlinkedDeletion);
1939                         dev->nDeletedFiles--;
1940                         dev->unlinkedDeletion = NULL;
1941                 }
1942         }
1943 }
1944
1945 static int yaffs_CheckGarbageCollection(yaffs_Device *dev)
1946 {
1947         int block;
1948
1949         yaffs_DoUnlinkedFileDeletion(dev);
1950
1951         if(dev->nErasedBlocks <= (YAFFS_RESERVED_BLOCKS + YAFFS_GARBAGE_COLLECT_LOW_WATER))
1952         {
1953                 dev->garbageCollectionRequired = 1;
1954         }
1955
1956         if(dev->garbageCollectionRequired)
1957         {
1958                 dev->garbageCollections++;
1959                 dev->garbageCollectionRequired = 0;
1960                 if(dev->blockSelectedForGC >= 0)
1961                 {
1962                         block = dev->blockSelectedForGC;
1963                 }
1964                 else
1965                 {
1966                         block = yaffs_FindDirtiestBlock(dev);
1967                 }
1968
1969                 if(block >= 0)
1970                 {
1971                         return yaffs_GarbageCollectBlock(dev,block);
1972                 }
1973                 else
1974                 {
1975                         return YAFFS_FAIL;
1976                 }
1977         }
1978
1979         return YAFFS_OK;
1980 }
1981
1982
1983 //////////////////////////// TAGS ///////////////////////////////////////
1984
1985 static void yaffs_LoadTagsIntoSpare(yaffs_Spare *sparePtr, yaffs_Tags *tagsPtr)
1986 {
1987         yaffs_TagsUnion *tu = (yaffs_TagsUnion *)tagsPtr;
1988
1989         yaffs_CalcTagsECC(tagsPtr);
1990
1991         sparePtr->tagByte0 = tu->asBytes[0];
1992         sparePtr->tagByte1 = tu->asBytes[1];
1993         sparePtr->tagByte2 = tu->asBytes[2];
1994         sparePtr->tagByte3 = tu->asBytes[3];
1995         sparePtr->tagByte4 = tu->asBytes[4];
1996         sparePtr->tagByte5 = tu->asBytes[5];
1997         sparePtr->tagByte6 = tu->asBytes[6];
1998         sparePtr->tagByte7 = tu->asBytes[7];
1999 }
2000
2001 static void yaffs_GetTagsFromSpare(yaffs_Spare *sparePtr,yaffs_Tags *tagsPtr)
2002 {
2003         yaffs_TagsUnion *tu = (yaffs_TagsUnion *)tagsPtr;
2004
2005         tu->asBytes[0]= sparePtr->tagByte0;
2006         tu->asBytes[1]= sparePtr->tagByte1;
2007         tu->asBytes[2]= sparePtr->tagByte2;
2008         tu->asBytes[3]= sparePtr->tagByte3;
2009         tu->asBytes[4]= sparePtr->tagByte4;
2010         tu->asBytes[5]= sparePtr->tagByte5;
2011         tu->asBytes[6]= sparePtr->tagByte6;
2012         tu->asBytes[7]= sparePtr->tagByte7;
2013
2014         yaffs_CheckECCOnTags(tagsPtr);
2015 }
2016
2017 static void yaffs_SpareInitialise(yaffs_Spare *spare)
2018 {
2019         memset(spare,0xFF,sizeof(yaffs_Spare));
2020 }
2021
2022 static int yaffs_ReadChunkTagsFromNAND(yaffs_Device *dev,int chunkInNAND, yaffs_Tags *tags, int *chunkDeleted)
2023 {
2024         if(tags)
2025         {
2026                 yaffs_Spare spare;
2027                 if(yaffs_ReadChunkFromNAND(dev,chunkInNAND,NULL,&spare,1) == YAFFS_OK)
2028                 {
2029                         *chunkDeleted = (yaffs_CountBits(spare.pageStatus) < 7) ? 1 : 0;
2030                         yaffs_GetTagsFromSpare(&spare,tags);
2031                         return YAFFS_OK;
2032                 }
2033                 else
2034                 {
2035                         return YAFFS_FAIL;
2036                 }
2037         }
2038
2039         return YAFFS_OK;
2040 }
2041
2042 #if 0
2043 static int yaffs_WriteChunkWithTagsToNAND(yaffs_Device *dev,int chunkInNAND, const __u8 *buffer, yaffs_Tags *tags)
2044 {
2045         // NB There must be tags, data is optional
2046         // If there is data, then an ECC is calculated on it.
2047
2048         yaffs_Spare spare;
2049
2050         if(!tags)
2051         {
2052                 return YAFFS_FAIL;
2053         }
2054
2055         yaffs_SpareInitialise(&spare);
2056
2057
2058         if(buffer)
2059         {
2060                 yaffs_CalcECC(buffer,&spare);
2061         }
2062
2063         yaffs_LoadTagsIntoSpare(&spare,tags);
2064
2065         return yaffs_WriteChunkToNAND(dev,chunkInNAND,buffer,&spare);
2066
2067 }
2068 #endif
2069
2070
2071 static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device *dev, const __u8 *buffer, yaffs_Tags *tags, int useReserve)
2072 {
2073         // NB There must be tags, data is optional
2074         // If there is data, then an ECC is calculated on it.
2075
2076         yaffs_Spare spare;
2077
2078         if(!tags)
2079         {
2080                 return YAFFS_FAIL;
2081         }
2082
2083         yaffs_SpareInitialise(&spare);
2084
2085
2086         if(buffer)
2087         {
2088                 yaffs_CalcECC(buffer,&spare);
2089         }
2090
2091         yaffs_LoadTagsIntoSpare(&spare,tags);
2092
2093         return yaffs_WriteNewChunkToNAND(dev,buffer,&spare,useReserve);
2094
2095 }
2096
2097 static int yaffs_TagsMatch(const yaffs_Tags *tags, int objectId, int chunkInObject, int chunkDeleted)
2098 {
2099         return  (  tags->chunkId == chunkInObject &&
2100                            tags->objectId == objectId &&
2101                            !chunkDeleted) ? 1 : 0;
2102
2103 }
2104
2105
2106
2107 int yaffs_FindChunkInFile(yaffs_Object *in,int chunkInInode,yaffs_Tags *tags)
2108 {
2109         //Get the Tnode, then get the level 0 offset chunk offset
2110     yaffs_Tnode *tn;
2111     int theChunk = -1;
2112     yaffs_Tags localTags;
2113     int i;
2114     int found = 0;
2115     int chunkDeleted;
2116
2117     yaffs_Device *dev = in->myDev;
2118
2119
2120     if(!tags)
2121     {
2122         // Passed a NULL, so use our own tags space
2123         tags = &localTags;
2124     }
2125
2126     tn = yaffs_FindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
2127
2128     if(tn)
2129     {
2130                 theChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] << dev->chunkGroupBits;
2131
2132                 // Now we need to do the shifting etc and search for it
2133                 for(i = 0,found = 0; theChunk && i < dev->chunkGroupSize && !found; i++)
2134                 {
2135                         yaffs_ReadChunkTagsFromNAND(dev,theChunk,tags,&chunkDeleted);
2136                         if(yaffs_TagsMatch(tags,in->objectId,chunkInInode,chunkDeleted))
2137                         {
2138                                 // found it;
2139                                 found = 1;
2140                         }
2141                         else
2142                         {
2143                                 theChunk++;
2144                         }
2145                 }
2146     }
2147     return found ? theChunk : -1;
2148 }
2149
2150 int yaffs_FindAndDeleteChunkInFile(yaffs_Object *in,int chunkInInode,yaffs_Tags *tags)
2151 {
2152         //Get the Tnode, then get the level 0 offset chunk offset
2153     yaffs_Tnode *tn;
2154     int theChunk = -1;
2155     yaffs_Tags localTags;
2156     int i;
2157     int found = 0;
2158     yaffs_Device *dev = in->myDev;
2159     int chunkDeleted;
2160
2161     if(!tags)
2162     {
2163         // Passed a NULL, so use our own tags space
2164         tags = &localTags;
2165     }
2166
2167     tn = yaffs_FindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
2168
2169     if(tn)
2170     {
2171
2172                 theChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] << dev->chunkGroupBits;
2173
2174                 // Now we need to do the shifting etc and search for it
2175                 for(i = 0,found = 0; theChunk && i < dev->chunkGroupSize && !found; i++)
2176                 {
2177                         yaffs_ReadChunkTagsFromNAND(dev,theChunk,tags,&chunkDeleted);
2178                         if(yaffs_TagsMatch(tags,in->objectId,chunkInInode,chunkDeleted))
2179                         {
2180                                 // found it;
2181                                 found = 1;
2182                         }
2183                         else
2184                         {
2185                                 theChunk++;
2186                         }
2187                 }
2188
2189                 // Delete the entry in the filestructure
2190                 if(found)
2191                 {
2192                         tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] = 0;
2193                 }
2194     }
2195     else
2196     {
2197         //T(("No level 0 found for %d\n", chunkInInode));
2198     }
2199
2200     if(!found)
2201     {
2202         //T(("Could not find %d to delete\n",chunkInInode));
2203     }
2204     return found ? theChunk : -1;
2205 }
2206
2207
2208 #if YAFFS_PARANOID
2209
2210 static int yaffs_CheckFileSanity(yaffs_Object *in)
2211 {
2212         int chunk;
2213         int nChunks;
2214         int fSize;
2215         int failed = 0;
2216         int objId;
2217         yaffs_Tnode *tn;
2218     yaffs_Tags localTags;
2219     yaffs_Tags *tags = &localTags;
2220     int theChunk;
2221     int chunkDeleted;
2222
2223
2224         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
2225         {
2226                 //T(("Object not a file\n"));
2227                 return YAFFS_FAIL;
2228         }
2229
2230         objId = in->objectId;
2231         fSize  = in->variant.fileVariant.fileSize;
2232         nChunks = (fSize + YAFFS_BYTES_PER_CHUNK -1)/YAFFS_BYTES_PER_CHUNK;
2233
2234         for(chunk = 1; chunk <= nChunks; chunk++)
2235         {
2236                 tn = yaffs_FindLevel0Tnode(in->myDev,&in->variant.fileVariant, chunk);
2237
2238                 if(tn)
2239                 {
2240
2241                         theChunk = tn->level0[chunk & YAFFS_TNODES_LEVEL0_MASK] << in->myDev->chunkGroupBits;
2242
2243
2244                                 yaffs_ReadChunkTagsFromNAND(in->myDev,theChunk,tags,&chunkDeleted);
2245                                 if(yaffs_TagsMatch(tags,in->objectId,chunk,chunkDeleted))
2246                                 {
2247                                         // found it;
2248
2249                                 }
2250                                 else
2251                                 {
2252                                         //T(("File problem file [%d,%d] NAND %d  tags[%d,%d]\n",
2253                                         //              objId,chunk,theChunk,tags->chunkId,tags->objectId);
2254
2255                                         failed = 1;
2256
2257                                 }
2258
2259                 }
2260                 else
2261                 {
2262                         //T(("No level 0 found for %d\n", chunk));
2263                 }
2264         }
2265
2266         return failed ? YAFFS_FAIL : YAFFS_OK;
2267 }
2268
2269 #endif
2270
2271 static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan)
2272 {
2273         yaffs_Tnode *tn;
2274         yaffs_Device *dev = in->myDev;
2275         int existingChunk;
2276         yaffs_Tags existingTags;
2277         yaffs_Tags newTags;
2278         unsigned existingSerial, newSerial;
2279
2280         int newChunkDeleted;
2281
2282
2283         tn = yaffs_AddOrFindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
2284         if(!tn)
2285         {
2286                 return YAFFS_FAIL;
2287         }
2288
2289         existingChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK];
2290
2291         if(inScan)
2292         {
2293                 // If we're scanning then we need to test for duplicates
2294                 // NB This does not need to be efficient since it should only ever
2295                 // happen when the power fails during a write, then only one
2296                 // chunk should ever be affected.
2297
2298
2299                 if(existingChunk != 0)
2300                 {
2301                         // NB Right now existing chunk will not be real chunkId if the device >= 32MB
2302                         //    thus we have to do a FindChunkInFile to get the real chunk id.
2303                         //
2304                         // We have a duplicate now we need to decide which one to use
2305                         // To do this we get both sets of tags and compare serial numbers.
2306                         yaffs_ReadChunkTagsFromNAND(dev,chunkInNAND, &newTags,&newChunkDeleted);
2307
2308
2309                         // Do a proper find
2310                         existingChunk = yaffs_FindChunkInFile(in,chunkInInode, &existingTags);
2311
2312                         if(existingChunk <=0)
2313                         {
2314                                 //Hoosterman - how did this happen?
2315                                 // todo
2316                         }
2317
2318
2319                         // NB The deleted flags should be false, otherwise the chunks will
2320                         // not be loaded during a scan
2321
2322                         newSerial = newTags.serialNumber;
2323                         existingSerial = existingTags.serialNumber;
2324
2325                         if( existingChunk <= 0 ||
2326                             ((existingSerial+1) & 3) == newSerial)
2327                         {
2328                                 // Use new
2329                                 // Delete the old one and drop through to update the tnode
2330                                 yaffs_DeleteChunk(dev,existingChunk);
2331                         }
2332                         else
2333                         {
2334                                 // Use existing.
2335                                 // Delete the new one and return early so that the tnode isn't changed
2336                                 yaffs_DeleteChunk(dev,chunkInNAND);
2337                                 return YAFFS_OK;
2338                         }
2339                 }
2340
2341         }
2342
2343         if(existingChunk == 0)
2344         {
2345                 in->nDataChunks++;
2346         }
2347
2348         tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] = (chunkInNAND >> dev->chunkGroupBits);
2349
2350         return YAFFS_OK;
2351 }
2352
2353
2354
2355 int yaffs_ReadChunkDataFromObject(yaffs_Object *in,int chunkInInode, __u8 *buffer)
2356 {
2357     int chunkInNAND = yaffs_FindChunkInFile(in,chunkInInode,NULL);
2358
2359     if(chunkInNAND >= 0)
2360     {
2361                 return yaffs_ReadChunkFromNAND(in->myDev,chunkInNAND,buffer,NULL,1);
2362         }
2363         else
2364         {
2365                 return 0;
2366         }
2367
2368 }
2369
2370
2371 static void yaffs_DeleteChunk(yaffs_Device *dev,int chunkId)
2372 {
2373         int block;
2374         int page;
2375         yaffs_Spare spare;
2376         yaffs_BlockInfo *bi;
2377
2378         if(chunkId <= 0) return;
2379
2380         block = chunkId / YAFFS_CHUNKS_PER_BLOCK;
2381         page = chunkId % YAFFS_CHUNKS_PER_BLOCK;
2382         yaffs_SpareInitialise(&spare);
2383
2384         spare.pageStatus = 0; // To mark it as deleted.
2385
2386
2387         yaffs_WriteChunkToNAND(dev,chunkId,NULL,&spare);
2388         yaffs_HandleUpdateChunk(dev,chunkId,&spare);
2389         bi = yaffs_GetBlockInfo(dev,block);
2390
2391
2392         // Pull out of the management area.
2393         // If the whole block became dirty, this will kick off an erasure.
2394         if(     bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING ||
2395             bi->blockState == YAFFS_BLOCK_STATE_FULL)
2396         {
2397                 dev->nFreeChunks++;
2398
2399                 bi->pageBits &= ~(1 << page);
2400                 bi->pagesInUse--;
2401
2402                 if(bi->pagesInUse == 0 &&
2403                bi->blockState == YAFFS_BLOCK_STATE_FULL)
2404             {
2405                 yaffs_BlockBecameDirty(dev,block);
2406             }
2407
2408         }
2409         else
2410         {
2411                 // T(("Bad news deleting chunk %d\n",chunkId));
2412         }
2413
2414 }
2415
2416
2417
2418
2419 int yaffs_WriteChunkDataToObject(yaffs_Object *in,int chunkInInode, const __u8 *buffer,int nBytes,int useReserve)
2420 {
2421         // Find old chunk Need to do this to get serial number
2422         // Write new one and patch into tree.
2423         // Invalidate old tags.
2424
2425     int prevChunkId;
2426     yaffs_Tags prevTags;
2427
2428     int newChunkId;
2429     yaffs_Tags newTags;
2430
2431     yaffs_Device *dev = in->myDev;
2432
2433         yaffs_CheckGarbageCollection(dev);
2434
2435         // Get the previous chunk at this location in the file if it exists
2436     prevChunkId  = yaffs_FindChunkInFile(in,chunkInInode,&prevTags);
2437
2438     // Set up new tags
2439         newTags.chunkId = chunkInInode;
2440         newTags.objectId = in->objectId;
2441         newTags.serialNumber = (prevChunkId >= 0) ? prevTags.serialNumber + 1 : 1;
2442         newTags.byteCount = nBytes;
2443         newTags.unusedStuff = 0xFFFFFFFF;
2444
2445         yaffs_CalcTagsECC(&newTags);
2446
2447
2448  #if 0
2449     // Create new chunk in NAND
2450     newChunkId = yaffs_AllocatePage(dev,useReserve);
2451
2452
2453     if(newChunkId >= 0)
2454     {
2455
2456
2457                 yaffs_WriteChunkWithTagsToNAND(dev,newChunkId,buffer,&newTags);
2458
2459                 yaffs_PutChunkIntoFile(in,chunkInInode,newChunkId);
2460
2461
2462                 if(prevChunkId >= 0)
2463                 {
2464                         yaffs_DeleteChunk(dev,prevChunkId);
2465
2466                 }
2467
2468                 yaffs_CheckFileSanity(in);
2469
2470                 return newChunkId;
2471     }
2472
2473
2474     return -1;
2475 #else
2476
2477         newChunkId = yaffs_WriteNewChunkWithTagsToNAND(dev,buffer,&newTags,useReserve);
2478         if(newChunkId >= 0)
2479         {
2480                 yaffs_PutChunkIntoFile(in,chunkInInode,newChunkId,0);
2481
2482
2483                 if(prevChunkId >= 0)
2484                 {
2485                         yaffs_DeleteChunk(dev,prevChunkId);
2486
2487                 }
2488
2489                 yaffs_CheckFileSanity(in);
2490         }
2491         return newChunkId;
2492
2493 #endif
2494
2495
2496
2497 }
2498
2499
2500 // UpdateObjectHeader updates the header on NAND for an object.
2501 // If name is not NULL, then that new name is used.
2502 //
2503 int yaffs_UpdateObjectHeader(yaffs_Object *in,const char *name, int force)
2504 {
2505
2506         yaffs_Device *dev = in->myDev;
2507
2508     int prevChunkId;
2509
2510     int newChunkId;
2511     yaffs_Tags newTags;
2512     __u8 bufferNew[YAFFS_BYTES_PER_CHUNK];
2513     __u8 bufferOld[YAFFS_BYTES_PER_CHUNK];
2514
2515     yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)bufferNew;
2516     yaffs_ObjectHeader *ohOld = (yaffs_ObjectHeader *)bufferOld;
2517
2518         yaffs_INVALIDATECHUNKCACHE(in);
2519
2520     if(!in->fake || force)
2521     {
2522
2523                 yaffs_CheckGarbageCollection(dev);
2524
2525                 memset(bufferNew,0xFF,YAFFS_BYTES_PER_CHUNK);
2526
2527                 prevChunkId = in->chunkId;
2528
2529                 if(prevChunkId >= 0)
2530                 {
2531                         yaffs_ReadChunkFromNAND(dev,prevChunkId,bufferOld,NULL,1);
2532                 }
2533
2534                 // Header data
2535                 oh->type = in->variantType;
2536
2537                 oh->st_mode = in->st_mode;
2538                 oh->st_uid = in->st_uid;
2539                 oh->st_gid = in->st_gid;
2540                 oh->st_atime = in->st_atime;
2541                 oh->st_mtime = in->st_mtime;
2542                 oh->st_ctime = in->st_ctime;
2543                 oh->st_rdev = in->st_rdev;
2544
2545                 if(in->parent)
2546                 {
2547                         oh->parentObjectId = in->parent->objectId;
2548                 }
2549                 else
2550                 {
2551                         oh->parentObjectId = 0;
2552                 }
2553
2554                 oh->sum = in->sum;
2555                 if(name && *name)
2556                 {
2557                         memset(oh->name,0,YAFFS_MAX_NAME_LENGTH + 1);
2558                         strncpy(oh->name,name,YAFFS_MAX_NAME_LENGTH);
2559                 }
2560                 else if(prevChunkId)
2561                 {
2562                         memcpy(oh->name, ohOld->name,YAFFS_MAX_NAME_LENGTH + 1);
2563                 }
2564                 else
2565                 {
2566                         memset(oh->name,0,YAFFS_MAX_NAME_LENGTH + 1);
2567                 }
2568
2569                 switch(in->variantType)
2570                 {
2571                         case YAFFS_OBJECT_TYPE_UNKNOWN:
2572                                 // Should not happen
2573                                 break;
2574                         case YAFFS_OBJECT_TYPE_FILE:
2575                                 oh->fileSize = in->variant.fileVariant.fileSize;
2576                                 break;
2577                         case YAFFS_OBJECT_TYPE_HARDLINK:
2578                                 oh->equivalentObjectId = in->variant.hardLinkVariant.equivalentObjectId;
2579                                 break;
2580                         case YAFFS_OBJECT_TYPE_SPECIAL:
2581                                 // Do nothing
2582                                 break;
2583                         case YAFFS_OBJECT_TYPE_DIRECTORY:
2584                                 // Do nothing
2585                                 break;
2586                         case YAFFS_OBJECT_TYPE_SYMLINK:
2587                                 strncpy(oh->alias,in->variant.symLinkVariant.alias,YAFFS_MAX_ALIAS_LENGTH);
2588                                 oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
2589                                 break;
2590                 }
2591
2592                 // Tags
2593                 in->serial++;
2594                 newTags.chunkId = 0;
2595                 newTags.objectId = in->objectId;
2596                 newTags.serialNumber = in->serial;
2597                 newTags.byteCount =   0xFFFFFFFF;
2598                 newTags.unusedStuff = 0xFFFFFFFF;
2599
2600                 yaffs_CalcTagsECC(&newTags);
2601
2602
2603
2604 #if 0
2605                 // Create new chunk in NAND
2606                 newChunkId = yaffs_AllocatePage(dev,1);
2607
2608                 if(newChunkId >= 0)
2609                 {
2610
2611                         yaffs_WriteChunkWithTagsToNAND(dev,newChunkId,bufferNew,&newTags);
2612
2613                         in->chunkId = newChunkId;
2614
2615                         if(prevChunkId >= 0)
2616                         {
2617                                 yaffs_DeleteChunk(dev,prevChunkId);
2618                         }
2619
2620                         in->dirty = 0;
2621                         return newChunkId;
2622                 }
2623
2624                 return -1;
2625 #else
2626                 // Create new chunk in NAND
2627                 newChunkId = yaffs_WriteNewChunkWithTagsToNAND(dev,bufferNew,&newTags,1);
2628
2629                 if(newChunkId >= 0)
2630                 {
2631
2632                         in->chunkId = newChunkId;
2633
2634                         if(prevChunkId >= 0)
2635                         {
2636                                 yaffs_DeleteChunk(dev,prevChunkId);
2637                         }
2638
2639                         in->dirty = 0;
2640                 }
2641
2642                 return newChunkId;
2643
2644 #endif
2645     }
2646     return 0;
2647 }
2648
2649
2650 /////////////////////// Short Read Cache ////////////////////////////////
2651 //      In many siturations where there is no high level buffering a lot of
2652 //      reads might be short sequential reads. eg. scanning a jpeg file.
2653 //      In these cases, a shoprt read cache can provide a huge perfomance benefit
2654 //  with dumb-as-a-rock code.
2655 //  There are a limited number (~10) of cache chunks per device
2656
2657
2658 #ifdef CONFIG_YAFFS_SHORT_OP_CACHE
2659
2660 // Invalidate all the cache pages associated with this object
2661 // Do this whenever ther file is modified... dumb as a rock remember!
2662 static void yaffs_InvalidateChunkCache(yaffs_Object *in)
2663 {
2664         int i;
2665         yaffs_Device *dev = in->myDev;
2666         int id = in->objectId;
2667
2668         for(i = 0; i < YAFFS_N_CACHE_CHUNKS; i++)
2669         {
2670                 if(dev->srCache[i].objectId == id)
2671                 {
2672                         dev->srCache[i].objectId = 0;
2673                 }
2674         }
2675 }
2676
2677
2678 // Grab us a chunk for use.
2679 // First look for an empty one.
2680 // Then look for the least recently used one.
2681 static yaffs_ChunkCache *yaffs_GrabChunkCache(yaffs_Device *dev)
2682 {
2683         int i;
2684         int usage;
2685         int theOne;
2686
2687         for(i = 0; i < YAFFS_N_CACHE_CHUNKS; i++)
2688         {
2689                 if(dev->srCache[i].objectId == 0)
2690                 {
2691                         //T(("Grabbing empty %d\n",i));
2692
2693                         return &dev->srCache[i];
2694                 }
2695         }
2696
2697
2698         usage = dev->srCache[i].lastUse;
2699         theOne = 0;
2700
2701         for(i = 1; i < YAFFS_N_CACHE_CHUNKS; i++)
2702         {
2703                 if(dev->srCache[i].lastUse < usage)
2704                 {
2705                         usage = dev->srCache[i].lastUse;
2706                         theOne = i;
2707                 }
2708         }
2709
2710         //T(("Grabbing non-empty %d\n",theOne));
2711         return  &dev->srCache[theOne];
2712
2713 }
2714
2715
2716 // Find a cached chunk
2717 static yaffs_ChunkCache *yaffs_FindChunkCache(yaffs_Device *dev, int objectId, int chunkId)
2718 {
2719         int i;
2720 ;
2721
2722         for(i = 0; i < YAFFS_N_CACHE_CHUNKS; i++)
2723         {
2724                 if(dev->srCache[i].objectId == objectId &&
2725                    dev->srCache[i].chunkId == chunkId)
2726                 {
2727                         dev->cacheHits++;
2728
2729                         return &dev->srCache[i];
2730                 }
2731         }
2732
2733         return NULL;
2734 }
2735
2736 // Mark the chunk for the least recently used algorithym
2737 static void yaffs_UseChunkCache(yaffs_Device *dev, yaffs_ChunkCache *cache)
2738 {
2739         if( dev->srLastUse < 0 ||
2740                 dev->srLastUse > 1000000)
2741         {
2742                 // Reset the cache usages
2743                 int i;
2744                 for(i = 1; i < YAFFS_N_CACHE_CHUNKS; i++)
2745                 {
2746                         dev->srCache[i].lastUse = 0;
2747                 }
2748                 dev->srLastUse = 0;
2749         }
2750
2751         dev->srLastUse++;
2752
2753         cache->lastUse = dev->srLastUse;
2754
2755 }
2756
2757
2758
2759 #endif
2760
2761
2762
2763 ///////////////////////// File read/write ///////////////////////////////
2764 // Read and write have very similar structures.
2765 // In general the read/write has three parts to it
2766 // * An incomplete chunk to start with (if the read/write is not chunk-aligned)
2767 // * Some complete chunks
2768 // * An incomplete chunk to end off with
2769 //
2770 // Curve-balls: the first chunk might also be the last chunk.
2771
2772 int yaffs_ReadDataFromFile(yaffs_Object *in, __u8 * buffer, __u32 offset, int nBytes)
2773 {
2774
2775 //      yaffs_Device *dev = in->myDev;
2776
2777 #ifdef CONFIG_YAFFS_SHORT_OP_CACHE
2778         yaffs_ChunkCache *cache;
2779 #else
2780         __u8 localBuffer[YAFFS_BYTES_PER_CHUNK];
2781 #endif
2782
2783         int chunk;
2784         int start;
2785         int nToCopy;
2786         int n = nBytes;
2787         int nDone = 0;
2788
2789         while(n > 0)
2790         {
2791                 chunk = offset / YAFFS_BYTES_PER_CHUNK + 1; // The first chunk is 1
2792                 start = offset % YAFFS_BYTES_PER_CHUNK;
2793
2794                 // OK now check for the curveball where the start and end are in
2795                 // the same chunk.
2796                 if(     (start + n) < YAFFS_BYTES_PER_CHUNK)
2797                 {
2798                         nToCopy = n;
2799                 }
2800                 else
2801                 {
2802                         nToCopy = YAFFS_BYTES_PER_CHUNK - start;
2803                 }
2804
2805                 if(nToCopy != YAFFS_BYTES_PER_CHUNK)
2806                 {
2807                         // An incomplete start or end chunk (or maybe both start and end chunk)
2808 #ifdef CONFIG_YAFFS_SHORT_OP_CACHE
2809                         // If we can't find the data in the cache, then load it up.
2810                         cache = yaffs_FindChunkCache(in->myDev,in->objectId,chunk);
2811                         if(!cache)
2812                         {
2813                                 cache = yaffs_GrabChunkCache(in->myDev);
2814                                 cache->objectId = in->objectId;
2815                                 cache->chunkId = chunk;
2816                                 yaffs_ReadChunkDataFromObject(in,chunk,cache->data);
2817                         }
2818
2819                         yaffs_UseChunkCache(in->myDev,cache);
2820
2821                         memcpy(buffer,&cache->data[start],nToCopy);
2822 #else
2823                         // Read into the local buffer then copy...
2824                         yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
2825                         memcpy(buffer,&localBuffer[start],nToCopy);
2826 #endif
2827                 }
2828                 else
2829                 {
2830                         // A full chunk. Read directly into the supplied buffer.
2831                         yaffs_ReadChunkDataFromObject(in,chunk,buffer);
2832                 }
2833
2834                 n -= nToCopy;
2835                 offset += nToCopy;
2836                 buffer += nToCopy;
2837                 nDone += nToCopy;
2838
2839         }
2840
2841         return nDone;
2842 }
2843
2844
2845 int yaffs_WriteDataToFile(yaffs_Object *in,const __u8 * buffer, __u32 offset, int nBytes)
2846 {
2847         __u8 localBuffer[YAFFS_BYTES_PER_CHUNK];
2848
2849         int chunk;
2850         int start;
2851         int nToCopy;
2852         int n = nBytes;
2853         int nDone = 0;
2854         int nToWriteBack;
2855         int endOfWrite = offset+nBytes;
2856         int chunkWritten = 0;
2857
2858         yaffs_INVALIDATECHUNKCACHE(in);
2859
2860         while(n > 0 && chunkWritten >= 0)
2861         {
2862                 chunk = offset / YAFFS_BYTES_PER_CHUNK + 1;
2863                 start = offset % YAFFS_BYTES_PER_CHUNK;
2864
2865
2866                 // OK now check for the curveball where the start and end are in
2867                 // the same chunk.
2868                 if(     (start + n) < YAFFS_BYTES_PER_CHUNK)
2869                 {
2870                         nToCopy = n;
2871                         nToWriteBack = (start + n);
2872                 }
2873                 else
2874                 {
2875                         nToCopy = YAFFS_BYTES_PER_CHUNK - start;
2876                         nToWriteBack = YAFFS_BYTES_PER_CHUNK;
2877                 }
2878
2879                 if(nToCopy != YAFFS_BYTES_PER_CHUNK)
2880                 {
2881                         // An incomplete start or end chunk (or maybe both start and end chunk)
2882                         // Read into the local buffer then copy, then copy over and write back.
2883
2884                         yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
2885
2886                         memcpy(&localBuffer[start],buffer,nToCopy);
2887
2888                         chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,localBuffer,nToWriteBack,0);
2889
2890                         //T(("Write with readback to chunk %d %d\n",chunk,chunkWritten));
2891
2892                 }
2893                 else
2894                 {
2895                         // A full chunk. Write directly from the supplied buffer.
2896                         chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,buffer,YAFFS_BYTES_PER_CHUNK,0);
2897                         //T(("Write to chunk %d %d\n",chunk,chunkWritten));
2898                 }
2899
2900                 if(chunkWritten >= 0)
2901                 {
2902                         n -= nToCopy;
2903                         offset += nToCopy;
2904                         buffer += nToCopy;
2905                         nDone += nToCopy;
2906                 }
2907
2908         }
2909
2910         // Update file object
2911
2912         if(endOfWrite > in->variant.fileVariant.fileSize)
2913         {
2914                 in->variant.fileVariant.fileSize = endOfWrite;
2915         }
2916
2917         in->dirty = 1;
2918         /*in->st_mtime = CURRENT_TIME; only update in flush*/
2919
2920         return nDone;
2921 }
2922
2923
2924 int yaffs_ResizeFile(yaffs_Object *in, int newSize)
2925 {
2926         int i;
2927         int chunkId;
2928         int oldFileSize = in->variant.fileVariant.fileSize;
2929         int sizeOfPartialChunk = newSize % YAFFS_BYTES_PER_CHUNK;
2930
2931         yaffs_Device *dev = in->myDev;
2932
2933         __u8 localBuffer[YAFFS_BYTES_PER_CHUNK];
2934
2935         yaffs_INVALIDATECHUNKCACHE(in);
2936
2937         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
2938         {
2939                 return yaffs_GetFileSize(in);
2940         }
2941
2942         if(newSize < oldFileSize)
2943         {
2944
2945                 int lastDel = 1 + (oldFileSize-1)/YAFFS_BYTES_PER_CHUNK;
2946
2947                 int startDel = 1 + (newSize + YAFFS_BYTES_PER_CHUNK - 1)/
2948                                                         YAFFS_BYTES_PER_CHUNK;
2949
2950                 // Delete backwards so that we don't end up with holes if
2951                 // power is lost part-way through the operation.
2952                 for(i = lastDel; i >= startDel; i--)
2953                 {
2954                         // NB this could be optimised somewhat,
2955                         // eg. could retrieve the tags and write them without
2956                         // using yaffs_DeleteChunk
2957
2958                         chunkId = yaffs_FindAndDeleteChunkInFile(in,i,NULL);
2959                         if(chunkId <= 0 || chunkId >= (dev->endBlock * 32))
2960                         {
2961                                 //T(("Found daft chunkId %d for %d\n",chunkId,i));
2962                         }
2963                         else
2964                         {
2965                                 in->nDataChunks--;
2966                                 yaffs_DeleteChunk(dev,chunkId);
2967                         }
2968                 }
2969
2970
2971                 if(sizeOfPartialChunk != 0)
2972                 {
2973                         int lastChunk = 1+ newSize/YAFFS_BYTES_PER_CHUNK;
2974
2975                         // Got to read and rewrite the last chunk with its new size.
2976                         yaffs_ReadChunkDataFromObject(in,lastChunk,localBuffer);
2977
2978                         yaffs_WriteChunkDataToObject(in,lastChunk,localBuffer,sizeOfPartialChunk,1);
2979
2980                 }
2981
2982                 in->variant.fileVariant.fileSize = newSize;
2983
2984                 yaffs_PruneFileStructure(dev,&in->variant.fileVariant);
2985
2986                 return newSize;
2987
2988         }
2989         else
2990         {
2991                 return oldFileSize;
2992         }
2993 }
2994
2995
2996 loff_t yaffs_GetFileSize(yaffs_Object *obj)
2997 {
2998         obj = yaffs_GetEquivalentObject(obj);
2999
3000         switch(obj->variantType)
3001         {
3002                 case YAFFS_OBJECT_TYPE_FILE:
3003                         return obj->variant.fileVariant.fileSize;
3004                 case YAFFS_OBJECT_TYPE_SYMLINK:
3005                         return strlen(obj->variant.symLinkVariant.alias);
3006                 default:
3007                         return 0;
3008         }
3009 }
3010
3011
3012
3013 // yaffs_FlushFile() updates the file's
3014 // objectId in NAND
3015
3016 int yaffs_FlushFile(yaffs_Object *in)
3017 {
3018         int retVal;
3019         if(in->dirty)
3020         {
3021                 //T(("flushing object header\n"));
3022
3023                 in->st_mtime = CURRENT_TIME;
3024
3025                 retVal = yaffs_UpdateObjectHeader(in,NULL,0);
3026         }
3027         else
3028         {
3029                 retVal = YAFFS_OK;
3030         }
3031
3032         return retVal;
3033
3034 }
3035
3036
3037 static int yaffs_DoGenericObjectDeletion(yaffs_Object *in)
3038 {
3039         yaffs_INVALIDATECHUNKCACHE(in);
3040         yaffs_RemoveObjectFromDirectory(in);
3041         yaffs_DeleteChunk(in->myDev,in->chunkId);
3042 #if __KERNEL__
3043         if(in->myInode)
3044         {
3045                 in->myInode->u.generic_ip = NULL;
3046                 in->myInode = 0;
3047         }
3048 #endif
3049         yaffs_FreeObject(in);
3050         return YAFFS_OK;
3051
3052 }
3053
3054 // yaffs_DeleteFile deletes the whole file data
3055 // and the inode associated with the file.
3056 // It does not delete the links associated with the file.
3057 static int yaffs_UnlinkFile(yaffs_Object *in)
3058 {
3059
3060 #ifdef CONFIG_YAFFS_DISABLE_BACKGROUND_DELETION
3061         // Delete the file data & tnodes
3062 #if 0
3063         yaffs_ResizeFile(in,0);
3064 #else
3065          yaffs_DeleteWorker(in, in->variant.fileVariant.top, in->variant.fileVariant.topLevel, 0,NULL);
3066
3067 #endif
3068
3069         yaffs_FreeTnode(in->myDev,in->variant.fileVariant.top);
3070
3071         return  yaffs_DoGenericObjectDeletion(in);
3072 #else
3073         int retVal;
3074         retVal = yaffs_ChangeObjectName(in, in->myDev->unlinkedDir,NULL);
3075         if(retVal == YAFFS_OK)
3076         {
3077                 in->unlinked = 1;
3078                 in->renameAllowed = 0;
3079         }
3080         return retVal;
3081
3082
3083 #endif
3084 }
3085
3086 int yaffs_DeleteFile(yaffs_Object *in)
3087 {
3088         int retVal = YAFFS_OK;
3089         if(!in->unlinked)
3090         {
3091                 retVal = yaffs_UnlinkFile(in);
3092         }
3093         if(retVal == YAFFS_OK && in->unlinked)
3094         {
3095                 in->deleted = 1;
3096         }
3097         return in->deleted ? YAFFS_OK : YAFFS_FAIL;
3098 }
3099
3100 static int yaffs_DeleteDirectory(yaffs_Object *in)
3101 {
3102         //First check that the directory is empty.
3103         if(list_empty(&in->variant.directoryVariant.children))
3104         {
3105                 return  yaffs_DoGenericObjectDeletion(in);
3106         }
3107
3108         return YAFFS_FAIL;
3109
3110 }
3111
3112 static int yaffs_DeleteSymLink(yaffs_Object *in)
3113 {
3114         YFREE(in->variant.symLinkVariant.alias);
3115
3116         return  yaffs_DoGenericObjectDeletion(in);
3117 }
3118
3119 static int yaffs_DeleteHardLink(yaffs_Object *in)
3120 {
3121         // remove this hardlink from the list assocaited with the equivalent
3122         // object
3123         list_del(&in->hardLinks);
3124         return  yaffs_DoGenericObjectDeletion(in);
3125 }
3126
3127
3128 static int yaffs_UnlinkWorker(yaffs_Object *obj)
3129 {
3130
3131
3132         if(obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
3133         {
3134                 return  yaffs_DeleteHardLink(obj);
3135         }
3136         else if(!list_empty(&obj->hardLinks))
3137         {
3138 #if 0
3139                 // Curve ball: We're unlinking an object that has a hardlink.
3140                 // Therefore we can't really delete the object.
3141                 // Instead, we do the following:
3142                 // - Select a hardlink.
3143                 // - Re-type a hardlink as the equivalent object and populate the fields, including the
3144                 //  objectId. Updating the object id is important so that all the hardlinks do not need
3145                 // to be rewritten.
3146                 // - Update the equivalet object pointers.
3147                 // - Delete all object.
3148
3149                 yaffs_Object *hl;
3150                 struct list_head *i;
3151
3152
3153                 yaffs_RemoveObjectFromDirectory(obj);
3154
3155
3156
3157                 hl =  list_entry(obj->hardLinks.next, yaffs_Object,hardLinks);
3158
3159                 hl->dirty = 1;
3160                 hl->st_mode = obj->st_mode;
3161                 hl->st_uid = obj->st_uid;
3162                 hl->st_gid = obj->st_gid;
3163                 hl->st_atime = obj->st_atime;
3164                 hl->st_mtime = obj->st_mtime;
3165                 hl->st_ctime = obj->st_ctime;
3166                 hl->st_rdev = obj->st_rdev;
3167
3168                 hl->variantType = obj->variantType;
3169
3170                 switch(hl->variantType)
3171                 {
3172                         case YAFFS_OBJECT_TYPE_FILE:
3173                         case YAFFS_OBJECT_TYPE_SYMLINK:
3174                         case YAFFS_OBJECT_TYPE_SPECIAL:
3175                                 // These types are OK to just copy across.
3176                                 hl->variant = obj->variant;
3177                                 break;
3178                         case YAFFS_OBJECT_TYPE_DIRECTORY:
3179                                 // Fix the list up
3180                                 list_add(&hl->variant.directoryVariant.children,
3181                                             &obj->variant.directoryVariant.children);
3182                                 list_del(&obj->variant.directoryVariant.children);
3183
3184                                 // Now change all the directory children to point to the new parent.
3185                                 list_for_each(i,&hl->variant.directoryVariant.children)
3186                                 {
3187                                         list_entry(i,yaffs_Object,siblings)->parent = hl;
3188                                 }
3189                                 break;
3190
3191                         case YAFFS_OBJECT_TYPE_HARDLINK:
3192                         case YAFFS_OBJECT_TYPE_UNKNOWN:
3193                                 // Should not be either of these types.
3194                 }
3195
3196                 // Now fix up the hardlink chain
3197                 list_del(&obj->hardLinks);
3198
3199                 list_for_each(i,&hl->hardLinks)
3200                 {
3201                         list_entry(i,yaffs_Object,hardLinks)->variant.hardLinkVariant.equivalentObject = hl;
3202                         list_entry(i,yaffs_Object,hardLinks)->variant.hardLinkVariant.equivalentObjectId = hl->objectId;
3203                 }
3204
3205                 // Now fix up the hash links.
3206                 yaffs_UnhashObject(hl);
3207                 hl->objectId = obj->objectId;
3208                 yaffs_HashObject(hl);
3209
3210                 // Update the hardlink which has become an object
3211                 yaffs_UpdateObjectHeader(hl,NULL,0);
3212
3213                 // Finally throw away the deleted object
3214                 yaffs_DeleteChunk(obj->myDev,obj->chunkId);
3215                 yaffs_FreeObject(obj);
3216
3217                 return YAFFS_OK;
3218 #else
3219                 // Curve ball: We're unlinking an object that has a hardlink.
3220                 //
3221                 //      This problem arises because we are not strictly following
3222                 //  The Linux link/inode model.
3223                 //
3224                 // We can't really delete the object.
3225                 // Instead, we do the following:
3226                 // - Select a hardlink.
3227                 // - Unhook it from the hard links
3228                 // - Unhook it from its parent directory (so that the rename can work)
3229                 // - Rename the object to the hardlink's name.
3230                 // - Delete the hardlink
3231
3232
3233                 yaffs_Object *hl;
3234                 int retVal;
3235                 char name[YAFFS_MAX_NAME_LENGTH+1];
3236
3237                 hl = list_entry(obj->hardLinks.next,yaffs_Object,hardLinks);
3238
3239                 list_del_init(&hl->hardLinks);
3240                 list_del_init(&hl->siblings);
3241
3242                 yaffs_GetObjectName(hl,name,YAFFS_MAX_NAME_LENGTH+1);
3243
3244                 retVal = yaffs_ChangeObjectName(obj, hl->parent, name);
3245
3246                 if(retVal == YAFFS_OK)
3247                 {
3248                         retVal = yaffs_DoGenericObjectDeletion(hl);
3249                 }
3250                 return retVal;
3251
3252 #endif
3253
3254
3255         }
3256         else
3257         {
3258                 switch(obj->variantType)
3259                 {
3260                         case YAFFS_OBJECT_TYPE_FILE:
3261                                 return yaffs_UnlinkFile(obj);
3262                                 break;
3263                         case YAFFS_OBJECT_TYPE_DIRECTORY:
3264                                 return yaffs_DeleteDirectory(obj);
3265                                 break;
3266                         case YAFFS_OBJECT_TYPE_SYMLINK:
3267                                 return yaffs_DeleteSymLink(obj);
3268                                 break;
3269                         case YAFFS_OBJECT_TYPE_HARDLINK:
3270                         case YAFFS_OBJECT_TYPE_UNKNOWN:
3271                         default:
3272                                 return YAFFS_FAIL;
3273                 }
3274         }
3275 }
3276
3277 int yaffs_Unlink(yaffs_Object *dir, const char *name)
3278 {
3279         yaffs_Object *obj;
3280
3281          obj = yaffs_FindObjectByName(dir,name);
3282
3283          if(obj && obj->unlinkAllowed)
3284          {
3285                 return yaffs_UnlinkWorker(obj);
3286          }
3287
3288          return YAFFS_FAIL;
3289
3290 }
3291
3292 //////////////// Initialisation Scanning /////////////////
3293
3294
3295
3296 // For now we use the SmartMedia check.
3297 // We look at the blockStatus byte in the first two chunks
3298 // These must be 0xFF to pass as OK.
3299 // todo: this function needs to be modifyable foir different NAND types
3300 // and different chunk sizes.  Suggest make this into a per-device configurable
3301 // function.
3302 static int yaffs_IsBlockBad(yaffs_Device *dev, int blk)
3303 {
3304         yaffs_Spare spare;
3305
3306         yaffs_ReadChunkFromNAND(dev,blk * YAFFS_CHUNKS_PER_BLOCK,NULL,&spare,1);
3307 #if 1
3308         if(yaffs_CountBits(spare.blockStatus) < 7)
3309         {
3310                 return 1;
3311         }
3312 #else
3313         if(spare.blockStatus != 0xFF)
3314         {
3315                 return 1;
3316         }
3317 #endif
3318         yaffs_ReadChunkFromNAND(dev,blk * YAFFS_CHUNKS_PER_BLOCK + 1,NULL,&spare,1);
3319
3320 #if 1
3321         if(yaffs_CountBits(spare.blockStatus) < 7)
3322         {
3323                 return 1;
3324         }
3325 #else
3326         if(spare.blockStatus != 0xFF)
3327         {
3328                 return 1;
3329         }
3330 #endif
3331
3332         return 0;
3333
3334 }
3335
3336 static int yaffs_Scan(yaffs_Device *dev)
3337 {
3338         yaffs_Spare spare;
3339         yaffs_Tags tags;
3340         int blk;
3341         int chunk;
3342         int c;
3343         int deleted;
3344         yaffs_BlockState state;
3345         yaffs_Object *hardList = NULL;
3346         yaffs_Object *hl;
3347         yaffs_BlockInfo *bi;
3348
3349
3350         yaffs_ObjectHeader *oh;
3351         yaffs_Object *in;
3352         yaffs_Object *parent;
3353
3354         __u8 chunkData[YAFFS_BYTES_PER_CHUNK];
3355
3356
3357         // Scan all the blocks...
3358
3359         for(blk = dev->startBlock; blk <= dev->endBlock; blk++)
3360         {
3361                 deleted = 0;
3362                 bi = yaffs_GetBlockInfo(dev,blk);
3363                 bi->pageBits = 0;
3364                 bi->pagesInUse = 0;
3365                 state = YAFFS_BLOCK_STATE_SCANNING;
3366
3367
3368                 if(yaffs_IsBlockBad(dev,blk))
3369                 {
3370                         state = YAFFS_BLOCK_STATE_DEAD;
3371                         T((TSTR("block %d is bad" TENDSTR),blk));
3372                 }
3373
3374                 // Read each chunk in the block.
3375
3376                 for(c = 0; c < YAFFS_CHUNKS_PER_BLOCK &&
3377                                    state == YAFFS_BLOCK_STATE_SCANNING; c++)
3378                 {
3379                         // Read the spare area and decide what to do
3380                         chunk = blk * YAFFS_CHUNKS_PER_BLOCK + c;
3381
3382                         yaffs_ReadChunkFromNAND(dev,chunk,NULL,&spare,1);
3383
3384
3385                         // This block looks ok, now what's in this chunk?
3386                         yaffs_GetTagsFromSpare(&spare,&tags);
3387
3388                         if(yaffs_CountBits(spare.pageStatus) < 6)
3389                         {
3390                                 // A deleted chunk
3391                                 deleted++;
3392                                 dev->nFreeChunks ++;
3393                                 //T((" %d %d deleted\n",blk,c));
3394                         }
3395                         else if(tags.objectId == YAFFS_UNUSED_OBJECT_ID)
3396                         {
3397                                 // An unassigned chunk in the block
3398                                 // This means that either the block is empty or
3399                                 // this is the one being allocated from
3400
3401                                 if(c == 0)
3402                                 {
3403                                         // the block is unused
3404                                         state = YAFFS_BLOCK_STATE_EMPTY;
3405                                         dev->nErasedBlocks++;
3406                                 }
3407                                 else
3408                                 {
3409                                         // this is the block being allocated from
3410                                         T((TSTR(" Allocating from %d %d" TENDSTR),blk,c));
3411                                         state = YAFFS_BLOCK_STATE_ALLOCATING;
3412                                         dev->allocationBlock = blk;
3413                                         dev->allocationPage = c;
3414                                 }
3415
3416                                 dev->nFreeChunks += (YAFFS_CHUNKS_PER_BLOCK - c);
3417                         }
3418                         else if(tags.chunkId > 0)
3419                         {
3420                                 int endpos;
3421                                 // A data chunk.
3422                                 bi->pageBits |= (1 << c);
3423                                 bi->pagesInUse++;
3424
3425                                 in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,YAFFS_OBJECT_TYPE_FILE);
3426                                 // PutChunkIntoFIle checks for a clash (two data chunks with
3427                                 // the same chunkId).
3428                                 yaffs_PutChunkIntoFile(in,tags.chunkId,chunk,1);
3429                                 endpos = (tags.chunkId - 1)* YAFFS_BYTES_PER_CHUNK + tags.byteCount;
3430                                 if(in->variant.fileVariant.scannedFileSize <endpos)
3431                                 {
3432                                         in->variant.fileVariant.scannedFileSize = endpos;
3433 #ifndef CONFIG_YAFFS_USE_HEADER_FILE_SIZE
3434                                                 in->variant.fileVariant.fileSize =
3435                                                         in->variant.fileVariant.scannedFileSize;
3436 #endif
3437
3438                                 }
3439                                 //T((" %d %d data %d %d\n",blk,c,tags.objectId,tags.chunkId));
3440                         }
3441                         else
3442                         {
3443                                 // chunkId == 0, so it is an ObjectHeader.
3444                                 // Thus, we read in the object header and make the object
3445                                 bi->pageBits |= (1 << c);
3446                                 bi->pagesInUse++;
3447
3448                                 yaffs_ReadChunkFromNAND(dev,chunk,chunkData,NULL,1);
3449
3450                                 oh = (yaffs_ObjectHeader *)chunkData;
3451
3452                                 in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,oh->type);
3453
3454                                 if(in->valid)
3455                                 {
3456                                         // We have already filled this one. We have a duplicate and need to resolve it.
3457
3458                                         unsigned existingSerial = in->serial;
3459                                         unsigned newSerial = tags.serialNumber;
3460
3461                                         if(((existingSerial+1) & 3) == newSerial)
3462                                         {
3463                                                 // Use new one - destroy the exisiting one
3464                                                 yaffs_DeleteChunk(dev,in->chunkId);
3465                                                 in->valid = 0;
3466                                         }
3467                                         else
3468                                         {
3469                                                 // Use existing - destroy this one.
3470                                                 yaffs_DeleteChunk(dev,chunk);
3471                                         }
3472                                 }
3473
3474                                 if(!in->valid &&
3475                                    (tags.objectId == YAFFS_OBJECTID_ROOT ||
3476                                     tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))
3477                                 {
3478                                         // We only load some info, don't fiddle with directory structure
3479                                         in->valid = 1;
3480                                         in->variantType = oh->type;
3481
3482                                         in->st_mode  = oh->st_mode;
3483                                         in->st_uid   = oh->st_uid;
3484                                         in->st_gid   = oh->st_gid;
3485                                         in->st_atime = oh->st_atime;
3486                                         in->st_mtime = oh->st_mtime;
3487                                         in->st_ctime = oh->st_ctime;
3488                                         in->st_rdev = oh->st_rdev;
3489                                         in->chunkId  = chunk;
3490
3491                                 }
3492                                 else if(!in->valid)
3493                                 {
3494                                         // we need to load this info
3495
3496                                         in->valid = 1;
3497                                         in->variantType = oh->type;
3498
3499                                         in->st_mode  = oh->st_mode;
3500                                         in->st_uid   = oh->st_uid;
3501                                         in->st_gid   = oh->st_gid;
3502                                         in->st_atime = oh->st_atime;
3503                                         in->st_mtime = oh->st_mtime;
3504                                         in->st_ctime = oh->st_ctime;
3505                                         in->st_rdev = oh->st_rdev;
3506                                         in->chunkId  = chunk;
3507
3508                                         in->sum = oh->sum;
3509                                         in->dirty = 0;
3510
3511                                         // directory stuff...
3512                                         // hook up to parent
3513
3514                                         parent = yaffs_FindOrCreateObjectByNumber(dev,oh->parentObjectId,YAFFS_OBJECT_TYPE_DIRECTORY);
3515                                         if(parent->variantType == YAFFS_OBJECT_TYPE_UNKNOWN)
3516                                         {
3517                                                 // Set up as a directory
3518                                                 parent->variantType = YAFFS_OBJECT_TYPE_DIRECTORY;
3519                                                 INIT_LIST_HEAD(&parent->variant.directoryVariant.children);
3520                                         }
3521                                         else if(parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
3522                                         {
3523                                                 // Hoosterman, another problem....
3524                                                 // We're trying to use a non-directory as a directory
3525                                                 // Todo ... handle
3526                                         }
3527
3528                                         yaffs_AddObjectToDirectory(parent,in);
3529                                         if(parent == dev->unlinkedDir)
3530                                         {
3531                                                 in->deleted = 1; // If it is unlinked at start up then it wants deleting
3532                                                 dev->nDeletedFiles++;
3533                                         }
3534
3535                                         // Note re hardlinks.
3536                                         // Since we might scan a hardlink before its equivalent object is scanned
3537                                         // we put them all in a list.
3538                                         // After scanning is complete, we should have all the objects, so we run through this
3539                                         // list and fix up all the chains.
3540
3541                                         switch(in->variantType)
3542                                         {
3543                                                 case YAFFS_OBJECT_TYPE_UNKNOWN:         // Todo got a problem
3544                                                         break;
3545                                                 case YAFFS_OBJECT_TYPE_FILE:
3546 #ifdef CONFIG_YAFFS_USE_HEADER_FILE_SIZE
3547                                                         in->variant.fileVariant.fileSize = oh->fileSize;
3548 #endif
3549                                                         break;
3550                                                 case YAFFS_OBJECT_TYPE_HARDLINK:
3551                                                         in->variant.hardLinkVariant.equivalentObjectId = oh->equivalentObjectId;
3552                                                         (yaffs_Object *)(in->hardLinks.next) = hardList;
3553                                                         hardList = in;
3554                                                         break;
3555                                                 case YAFFS_OBJECT_TYPE_DIRECTORY:       // Do nothing
3556                                                         break;
3557                                                 case YAFFS_OBJECT_TYPE_SPECIAL: // Do nothing
3558                                                         break;
3559                                                 case YAFFS_OBJECT_TYPE_SYMLINK:         // Do nothing
3560                                                         in->variant.symLinkVariant.alias = yaffs_CloneString(oh->alias);
3561                                                         break;
3562                                         }
3563                                         //T((" %d %d header %d \"%s\" type %d\n",blk,c,tags.objectId,oh->name,in->variantType));
3564                                 }
3565                         }
3566                 }
3567
3568                 if(state == YAFFS_BLOCK_STATE_SCANNING)
3569                 {
3570                         // If we got this far while scanning, then the block is fully allocated.
3571                         state = YAFFS_BLOCK_STATE_FULL;
3572                 }
3573
3574                 bi->blockState = state;
3575
3576                 // Now let's see if it was dirty
3577                 if(     bi->pagesInUse == 0 &&
3578                 bi->blockState == YAFFS_BLOCK_STATE_FULL)
3579             {
3580                 yaffs_BlockBecameDirty(dev,blk);
3581             }
3582
3583         }
3584
3585         // Fix up the hard link chains.
3586         // We should now have scanned all the objects, now it's time to add these
3587         // hardlinks.
3588         while(hardList)
3589         {
3590                 hl = hardList;
3591                 hardList = (yaffs_Object *)(hardList->hardLinks.next);
3592
3593                 in = yaffs_FindObjectByNumber(dev,hl->variant.hardLinkVariant.equivalentObjectId);
3594
3595                 if(in)
3596                 {
3597                         // Add the hardlink pointers
3598                         hl->variant.hardLinkVariant.equivalentObject=in;
3599                         list_add(&hl->hardLinks,&in->hardLinks);
3600                 }
3601                 else
3602                 {
3603                         //Todo Need to report/handle this better.
3604                         // Got a problem... hardlink to a non-existant object
3605                         hl->variant.hardLinkVariant.equivalentObject=NULL;
3606                         INIT_LIST_HEAD(&hl->hardLinks);
3607
3608                 }
3609
3610         }
3611
3612
3613
3614         return YAFFS_OK;
3615 }
3616
3617
3618 ////////////////////////// Directory Functions /////////////////////////
3619
3620
3621 static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj)
3622 {
3623
3624         if(obj->siblings.prev == NULL)
3625         {
3626                 // Not initialised
3627                 INIT_LIST_HEAD(&obj->siblings);
3628
3629         }
3630         else if(!list_empty(&obj->siblings))
3631         {
3632                 // If it is holed up somewhere else, un hook it
3633                 list_del_init(&obj->siblings);
3634         }
3635         // Now add it
3636         list_add(&obj->siblings,&directory->variant.directoryVariant.children);
3637         obj->parent = directory;
3638
3639         if(directory == obj->myDev->unlinkedDir)
3640         {
3641                 obj->unlinked = 1;
3642                 obj->renameAllowed = 0;
3643         }
3644 }
3645
3646 static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj)
3647 {
3648         list_del_init(&obj->siblings);
3649         obj->parent = NULL;
3650 }
3651
3652 yaffs_Object *yaffs_FindObjectByName(yaffs_Object *directory,const char *name)
3653 {
3654         int sum;
3655
3656         struct list_head *i;
3657         char buffer[YAFFS_MAX_NAME_LENGTH+1];
3658
3659         yaffs_Object *l;
3660
3661         sum = yaffs_CalcNameSum(name);
3662
3663         list_for_each(i,&directory->variant.directoryVariant.children)
3664         {
3665                 l = list_entry(i, yaffs_Object,siblings);
3666
3667                 // Special case for lost-n-found
3668                 if(l->objectId == YAFFS_OBJECTID_LOSTNFOUND)
3669                 {
3670                         if(yaffs_strcmp(name,YAFFS_LOSTNFOUND_NAME) == 0)
3671                         {
3672                                 return l;
3673                         }
3674                 }
3675                 else if(yaffs_SumCompare(l->sum, sum))
3676                 {
3677                         // Do a real check
3678                         yaffs_GetObjectName(l,buffer,YAFFS_MAX_NAME_LENGTH);
3679                         if(yaffs_strcmp(name,buffer) == 0)
3680                         {
3681                                 return l;
3682                         }
3683
3684
3685                 }
3686         }
3687
3688         return NULL;
3689 }
3690
3691
3692 int yaffs_ApplyToDirectoryChildren(yaffs_Object *theDir,int (*fn)(yaffs_Object *))
3693 {
3694         struct list_head *i;
3695         yaffs_Object *l;
3696
3697
3698         list_for_each(i,&theDir->variant.directoryVariant.children)
3699         {
3700                 l = list_entry(i, yaffs_Object,siblings);
3701                 if(!fn(l))
3702                 {
3703                         return YAFFS_FAIL;
3704                 }
3705         }
3706
3707         return YAFFS_OK;
3708
3709 }
3710
3711
3712 // GetEquivalentObject dereferences any hard links to get to the
3713 // actual object.
3714
3715 yaffs_Object *yaffs_GetEquivalentObject(yaffs_Object *obj)
3716 {
3717         if(obj && obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
3718         {
3719                 // We want the object id of the equivalent object, not this one
3720                 obj = obj->variant.hardLinkVariant.equivalentObject;
3721         }
3722         return obj;
3723
3724 }
3725
3726 int yaffs_GetObjectName(yaffs_Object *obj,char *name,int buffSize)
3727 {
3728         memset(name,0,buffSize);
3729
3730         if(obj->objectId == YAFFS_OBJECTID_LOSTNFOUND)
3731         {
3732                 strncpy(name,YAFFS_LOSTNFOUND_NAME,buffSize - 1);
3733         }
3734         else if(obj->chunkId <= 0)
3735         {
3736                 char locName[20];
3737                 // make up a name
3738                 sprintf(locName,"%s%d",YAFFS_LOSTNFOUND_PREFIX,obj->objectId);
3739                 strncpy(name,locName,buffSize - 1);
3740
3741         }
3742         else
3743         {
3744                 __u8 buffer[YAFFS_BYTES_PER_CHUNK];
3745                 yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
3746
3747                 memset(buffer,0,YAFFS_BYTES_PER_CHUNK);
3748
3749                 if(obj->chunkId >= 0)
3750                 {
3751                         yaffs_ReadChunkFromNAND(obj->myDev,obj->chunkId,buffer,NULL,1);
3752                 }
3753                 strncpy(name,oh->name,buffSize - 1);
3754         }
3755
3756         return strlen(name);
3757 }
3758
3759 int yaffs_GetObjectFileLength(yaffs_Object *obj)
3760 {
3761
3762         // Dereference any hard linking
3763         obj = yaffs_GetEquivalentObject(obj);
3764
3765         if(obj->variantType == YAFFS_OBJECT_TYPE_FILE)
3766         {
3767                 return obj->variant.fileVariant.fileSize;
3768         }
3769         if(obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK)
3770         {
3771                 return strlen(obj->variant.symLinkVariant.alias);
3772         }
3773         else
3774         {
3775                 // Only a directory should drop through to here
3776                 return YAFFS_BYTES_PER_CHUNK;
3777         }
3778 }
3779
3780 int yaffs_GetObjectLinkCount(yaffs_Object *obj)
3781 {
3782         int count = 0;
3783         struct list_head *i;
3784
3785         if(!obj->unlinked)
3786         {
3787                 count++;        // the object itself
3788         }
3789         list_for_each(i,&obj->hardLinks)
3790         {
3791                 count++;        // add the hard links;
3792         }
3793         return count;
3794
3795 }
3796
3797
3798 int yaffs_GetObjectInode(yaffs_Object *obj)
3799 {
3800         obj = yaffs_GetEquivalentObject(obj);
3801
3802         return obj->objectId;
3803 }
3804
3805 unsigned yaffs_GetObjectType(yaffs_Object *obj)
3806 {
3807         obj = yaffs_GetEquivalentObject(obj);
3808
3809         switch(obj->variantType)
3810         {
3811                 case YAFFS_OBJECT_TYPE_FILE:            return DT_REG; break;
3812                 case YAFFS_OBJECT_TYPE_DIRECTORY:       return DT_DIR; break;
3813                 case YAFFS_OBJECT_TYPE_SYMLINK:         return DT_LNK; break;
3814                 case YAFFS_OBJECT_TYPE_HARDLINK:        return DT_REG; break;
3815                 case YAFFS_OBJECT_TYPE_SPECIAL:
3816                         if(S_ISFIFO(obj->st_mode)) return DT_FIFO;
3817                         if(S_ISCHR(obj->st_mode)) return DT_CHR;
3818                         if(S_ISBLK(obj->st_mode)) return DT_BLK;
3819                         if(S_ISSOCK(obj->st_mode)) return DT_SOCK;
3820                 default: return DT_REG; break;
3821         }
3822 }
3823
3824 char *yaffs_GetSymlinkAlias(yaffs_Object *obj)
3825 {
3826         obj = yaffs_GetEquivalentObject(obj);
3827         if(obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK)
3828         {
3829                 return yaffs_CloneString(obj->variant.symLinkVariant.alias);
3830         }
3831         else
3832         {
3833                 return yaffs_CloneString("");
3834         }
3835 }
3836
3837
3838 int yaffs_SetAttributes(yaffs_Object *obj, struct iattr *attr)
3839 {
3840         unsigned int valid = attr->ia_valid;
3841
3842         if(valid & ATTR_MODE) obj->st_mode = attr->ia_mode;
3843         if(valid & ATTR_UID) obj->st_uid = attr->ia_uid;
3844         if(valid & ATTR_GID) obj->st_gid = attr->ia_gid;
3845
3846         if(valid & ATTR_ATIME) obj->st_atime = attr->ia_atime;
3847         if(valid & ATTR_CTIME) obj->st_ctime = attr->ia_ctime;
3848         if(valid & ATTR_MTIME) obj->st_mtime = attr->ia_mtime;
3849
3850         if(valid & ATTR_SIZE) yaffs_ResizeFile(obj,attr->ia_size);
3851
3852         yaffs_UpdateObjectHeader(obj,NULL,1);
3853
3854         return YAFFS_OK;
3855
3856 }
3857 int yaffs_GetAttributes(yaffs_Object *obj, struct iattr *attr)
3858 {
3859         unsigned int valid = 0;
3860
3861         attr->ia_mode = obj->st_mode;   valid |= ATTR_MODE;
3862         attr->ia_uid = obj->st_uid;             valid |= ATTR_UID;
3863         attr->ia_gid = obj->st_gid;             valid |= ATTR_GID;
3864
3865         attr->ia_atime = obj->st_atime; valid |= ATTR_ATIME;
3866         attr->ia_ctime = obj->st_ctime; valid |= ATTR_CTIME;
3867         attr->ia_mtime = obj->st_mtime; valid |= ATTR_MTIME;
3868
3869         attr->ia_size = yaffs_GetFileSize(obj); valid |= ATTR_SIZE;
3870
3871         attr->ia_valid = valid;
3872
3873         return YAFFS_OK;
3874
3875 }
3876
3877
3878
3879 int yaffs_DumpObject(yaffs_Object *obj)
3880 {
3881 //      __u8 buffer[YAFFS_BYTES_PER_CHUNK];
3882         char name[257];
3883 //      yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
3884
3885 //      memset(buffer,0,YAFFS_BYTES_PER_CHUNK);
3886
3887 //      if(obj->chunkId >= 0)
3888 //      {
3889 //              yaffs_ReadChunkFromNAND(obj->myDev,obj->chunkId,buffer,NULL);
3890 //      }
3891
3892         yaffs_GetObjectName(obj,name,256);
3893
3894         YPRINTF(("Object %d, inode %d \"%s\"\n dirty %d valid %d serial %d sum %d chunk %d type %d size %d\n",
3895                         obj->objectId,yaffs_GetObjectInode(obj), name, obj->dirty, obj->valid, obj->serial,
3896                         obj->sum, obj->chunkId, yaffs_GetObjectType(obj), yaffs_GetObjectFileLength(obj)));
3897
3898 #if 0
3899         YPRINTF(("Object %d \"%s\"\n dirty %d valid %d serial %d sum %d chunk %d\n",
3900                         obj->objectId, oh->name, obj->dirty, obj->valid, obj->serial,
3901                         obj->sum, obj->chunkId));
3902                 switch(obj->variantType)
3903         {
3904                 case YAFFS_OBJECT_TYPE_FILE:
3905                         YPRINTF((" FILE length %d\n",obj->variant.fileVariant.fileSize));
3906                         break;
3907                 case YAFFS_OBJECT_TYPE_DIRECTORY:
3908                         YPRINTF((" DIRECTORY\n"));
3909                         break;
3910                 case YAFFS_OBJECT_TYPE_HARDLINK: //todo
3911                 case YAFFS_OBJECT_TYPE_SYMLINK:
3912                 case YAFFS_OBJECT_TYPE_UNKNOWN:
3913                 default:
3914         }
3915 #endif
3916
3917         return YAFFS_OK;
3918 }
3919
3920
3921 ///////////////////////// Initialisation code ///////////////////////////
3922
3923
3924
3925 int yaffs_GutsInitialise(yaffs_Device *dev)
3926 {
3927         unsigned x;
3928         int bits;
3929         int extraBits;
3930         int nBlocks;
3931
3932
3933
3934         if(!yaffs_CheckStructures())
3935         {
3936                 YPRINTF(("yaffs_CheckStructures failed\n"));
3937                 return YAFFS_FAIL;
3938         }
3939
3940         if(dev->startBlock <= 0 ||
3941            (dev->endBlock - dev->startBlock) < 10)
3942         {
3943                 YPRINTF(("startBlock %d or endBlock %d invalid\n",
3944                                 dev->startBlock, dev->endBlock));
3945                 return YAFFS_FAIL;
3946         }
3947
3948         nBlocks = dev->endBlock - dev->startBlock + 1;
3949
3950
3951
3952         // OK now calculate a few things for the device
3953         // Calculate chunkGroupBits.
3954         // We need to find the next power of 2 > than endBlock
3955
3956         x = YAFFS_CHUNKS_PER_BLOCK * (dev->endBlock+1);
3957
3958         for(bits = extraBits = 0; x > 1; bits++)
3959         {
3960                 if(x & 1) extraBits++;
3961                 x >>= 1;
3962         }
3963
3964         if(extraBits > 0) bits++;
3965
3966
3967         // Level0 Tnodes are 16 bits, so if the bitwidth of the
3968         // chunk range we're using is greater than 16 we need
3969         // to figure out chunk shift and chunkGroupSize
3970         if(bits <= 16)
3971         {
3972                 dev->chunkGroupBits = 0;
3973         }
3974         else
3975         {
3976                 dev->chunkGroupBits = bits - 16;
3977         }
3978         dev->chunkGroupSize = 1 << dev->chunkGroupBits;
3979
3980
3981         // More device initialisation
3982         dev->garbageCollectionRequired  = 0;
3983         dev->garbageCollections = 0;
3984         dev->currentDirtyChecker = 0;
3985         dev->bufferedBlock = -1;
3986         dev->doingBufferedBlockRewrite = 0;
3987         dev->blockSelectedForGC = -1;
3988         dev->nDeletedFiles = 0;
3989
3990         yaffs_InitialiseBlocks(dev,nBlocks);
3991
3992         yaffs_InitialiseTnodes(dev);
3993
3994         yaffs_InitialiseObjects(dev);
3995
3996 #ifdef CONFIG_YAFFS_SHORT_OP_CACHE
3997         {
3998                 int i;
3999                 for(i=0; i < YAFFS_N_CACHE_CHUNKS; i++)
4000                 {
4001                         dev->srCache[i].objectId = 0;
4002                         dev->srCache[i].lastUse = 0;
4003                 }
4004                 dev->srLastUse = 0;
4005         }
4006 #endif
4007
4008         dev->cacheHits = 0;
4009
4010
4011         // Initialise the unlinked, root and lost and found directories
4012         dev->lostNFoundDir = dev->rootDir = dev->unlinkedDir = NULL;
4013
4014         dev->unlinkedDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_UNLINKED, S_IFDIR);
4015
4016         dev->rootDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_ROOT,YAFFS_ROOT_MODE | S_IFDIR);
4017         dev->lostNFoundDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_LOSTNFOUND,YAFFS_LOSTNFOUND_MODE | S_IFDIR);
4018         yaffs_AddObjectToDirectory(dev->rootDir,dev->lostNFoundDir);
4019
4020
4021         // Now scan the flash.
4022         yaffs_Scan(dev);
4023
4024         // Zero out stats
4025         dev->nPageReads = 0;
4026     dev->nPageWrites =  0;
4027         dev->nBlockErasures = 0;
4028         dev->nGCCopies = 0;
4029         dev->nRetriedWrites = 0;
4030         dev->nRetiredBlocks = 0;
4031
4032
4033         return YAFFS_OK;
4034
4035 }
4036
4037 void yaffs_Deinitialise(yaffs_Device *dev)
4038 {
4039         yaffs_DeinitialiseBlocks(dev);
4040         yaffs_DeinitialiseTnodes(dev);
4041         yaffs_DeinitialiseObjects(dev);
4042
4043 }
4044
4045 int  yaffs_GetNumberOfFreeChunks(yaffs_Device *dev)
4046 {
4047         int nFree = dev->nFreeChunks - (YAFFS_CHUNKS_PER_BLOCK * YAFFS_RESERVED_BLOCKS);
4048
4049         struct list_head *i;
4050         yaffs_Object *l;
4051
4052
4053         // To the free chunks add the chunks that are in the deleted unlinked files.
4054         list_for_each(i,&dev->unlinkedDir->variant.directoryVariant.children)
4055         {
4056                 l = list_entry(i, yaffs_Object,siblings);
4057                 if(l->deleted)
4058                 {
4059                         nFree++;
4060                         nFree += l->nDataChunks;
4061                 }
4062         }
4063
4064
4065         return (nFree < 0) ? 0 : nFree;
4066
4067 }
4068
4069
4070 /////////////////// YAFFS test code //////////////////////////////////
4071
4072 #define yaffs_CheckStruct(structure,syze, name) \
4073            if(sizeof(structure) != syze) \
4074                { YPRINTF(("%s should be %d but is %d\n",name,syze,sizeof(structure))); \
4075                  return YAFFS_FAIL; \
4076                    }
4077
4078
4079 static int yaffs_CheckStructures(void)
4080 {
4081         yaffs_CheckStruct(yaffs_Tags,8,"yaffs_Tags")
4082         yaffs_CheckStruct(yaffs_TagsUnion,8,"yaffs_TagsUnion")
4083         yaffs_CheckStruct(yaffs_Spare,16,"yaffs_Spare")
4084         yaffs_CheckStruct(yaffs_Tnode,2* YAFFS_NTNODES_LEVEL0,"yaffs_Tnode")
4085         yaffs_CheckStruct(yaffs_ObjectHeader,512,"yaffs_ObjectHeader")
4086
4087
4088         return YAFFS_OK;
4089 }
4090
4091 void yaffs_GutsTest(yaffs_Device *dev)
4092 {
4093
4094         if(yaffs_CheckStructures() != YAFFS_OK)
4095         {
4096                 YPRINTF(("One or more structures malformed-- aborting\n"));
4097                 return;
4098         }
4099         else
4100         {
4101                 YPRINTF(("Structures OK\n"));
4102         }
4103
4104         yaffs_TnodeTest(dev);
4105         yaffs_ObjectTest(dev);
4106 }
4107
4108