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