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 #if 0
  24 #define T(x) printf x
  25 #else
  26 #define T(x)
  27 #endif
  28
  29 // External functions for ECC on data
  30 void nand_calculate_ecc (const u_char *dat, u_char *ecc_code);
  31 int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc);
  32
  33
  34 // countBits is a quick way of counting the number of bits in a byte.
  35 // ie. countBits[n] holds the number of 1 bits in a byte with the value n.
  36
  37 static const char yaffs_countBits[256] =
  38 {
  39 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
  40 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  41 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  42 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  43 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  44 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  45 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  46 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  47 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  48 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  49 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  50 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  51 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  52 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  53 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  54 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
  55 };
  56
  57
  58
  59 // Device info
  60 //static yaffs_Device *yaffs_device;
  61 //yaffs_Object *yaffs_rootDir;
  62 //yaffs_Object *yaffs_lostNFound;
  63
  64
  65
  66 // Local prototypes
  67 static int yaffs_CheckObjectHashSanity(yaffs_Device *dev);
  68 static void yaffs_LoadTagsIntoSpare(yaffs_Spare *sparePtr, yaffs_Tags *tagsPtr);
  69 static void yaffs_GetTagsFromSpare(yaffs_Spare *sparePtr,yaffs_Tags *tagsPtr);
  70 static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan);
  71
  72 static yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type);
  73 static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj);
  74 static int yaffs_UpdateObjectHeader(yaffs_Object *in,const char *name);
  75 static void yaffs_DeleteChunk(yaffs_Device *dev,int chunkId);
  76 static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj);
  77 static int yaffs_CheckStructures(void);
  78 static yaffs_Object *yaffs_GetEquivalentObject(yaffs_Object *obj);
  79
  80 loff_t yaffs_GetFileSize(yaffs_Object *obj);
  81
  82
  83 static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve);
  84
  85 #ifdef YAFFS_PARANOID
  86 static int yaffs_CheckFileSanity(yaffs_Object *in);
  87 #else
  88 #define yaffs_CheckFileSanity(in)
  89 #endif
  90
  91 static int __inline__ yaffs_HashFunction(int n)
  92 {
  93         return (n % YAFFS_NOBJECT_BUCKETS);
  94 }
  95
  96
  97 yaffs_Object *yaffs_Root(yaffs_Device *dev)
  98 {
  99         return dev->rootDir;
 100 }
 101
 102 yaffs_Object *yaffs_LostNFound(yaffs_Device *dev)
 103 {
 104         return dev->lostNFoundDir;
 105 }
 106
 107
 108 static int yaffs_WriteChunkToNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND, const __u8 *data, yaffs_Spare *spare)
 109 {
 110         return dev->writeChunkToNAND(dev,chunkInNAND,data,spare);
 111 }
 112
 113 int yaffs_ReadChunkFromNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND, __u8 *data, yaffs_Spare *spare)
 114 {
 115         int retVal;
 116         __u8 calcEcc[3];
 117         yaffs_Spare localSpare;
 118
 119         if(!spare && data)
 120         {
 121                 // If we don't have a real spare, then we use a local one.
 122                 // Need this for the calculation of the ecc
 123                 spare = &localSpare;
 124         }
 125
 126         retVal  = dev->readChunkFromNAND(dev,chunkInNAND,data,spare);
 127         if(data)
 128         {
 129                 // Do ECC correction
 130                 //Todo handle any errors
 131                  nand_calculate_ecc(data,calcEcc);
 132                  nand_correct_data (data,spare->ecc1, calcEcc);
 133                  nand_calculate_ecc(&data[256],calcEcc);
 134                  nand_correct_data (&data[256],spare->ecc2, calcEcc);
 135         }
 136         return retVal;
 137 }
 138
 139 #ifdef YAFFS_PARANOID
 140
 141 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND)
 142 {
 143         static int init = 0;
 144         static __u8 cmpbuf[YAFFS_BYTES_PER_CHUNK];
 145         static __u8 data[YAFFS_BYTES_PER_CHUNK];
 146         static __u8 spare[16];
 147
 148         int retVal;
 149
 150         retVal  = YAFFS_OK;
 151
 152         dev->readChunkFromNAND(dev,chunkInNAND,data,(yaffs_Spare *)spare);
 153
 154
 155
 156         if(!init)
 157         {
 158                 memset(cmpbuf,0xff,YAFFS_BYTES_PER_CHUNK);
 159                 init = 1;
 160         }
 161
 162         if(memcmp(cmpbuf,data,YAFFS_BYTES_PER_CHUNK)) retVal = YAFFS_FAIL;
 163         if(memcmp(cmpbuf,spare,16)) retVal = YAFFS_FAIL;
 164
 165         return retVal;
 166
 167 }
 168
 169 #endif
 170
 171
 172 int yaffs_EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND)
 173 {
 174         return dev->eraseBlockInNAND(dev,blockInNAND);
 175 }
 176
 177 int yaffs_InitialiseNAND(struct yaffs_DeviceStruct *dev)
 178 {
 179         return dev->initialiseNAND(dev);
 180 }
 181
 182 static int yaffs_WriteNewChunkToNAND(struct yaffs_DeviceStruct *dev, const __u8 *data, yaffs_Spare *spare,int useReserve)
 183 {
 184         int chunk;
 185
 186         int writeOk = 0;
 187
 188         unsigned char rbData[YAFFS_BYTES_PER_CHUNK];
 189         yaffs_Spare rbSpare;
 190
 191         do{
 192                 chunk = yaffs_AllocateChunk(dev,useReserve);
 193
 194                 if(chunk >= 0)
 195                 {
 196                         writeOk =  yaffs_WriteChunkToNAND(dev,chunk,data,spare);
 197                         if(writeOk)
 198                         {
 199                                 // Readback & verify
 200                                 // If verify fails, then delete this chunk and try again
 201                                 // To verify we compare everything except the block and
 202                                 // page status bytes.
 203                                 yaffs_ReadChunkFromNAND(dev,chunk,rbData,&rbSpare);
 204
 205                                 if(memcmp(data,rbData,YAFFS_BYTES_PER_CHUNK) != 0 ||
 206                                         spare->tagByte0 != rbSpare.tagByte0 ||
 207                                         spare->tagByte1 != rbSpare.tagByte1 ||
 208                                         spare->tagByte2 != rbSpare.tagByte2 ||
 209                                         spare->tagByte3 != rbSpare.tagByte3 ||
 210                                         spare->tagByte4 != rbSpare.tagByte4 ||
 211                                         spare->tagByte5 != rbSpare.tagByte5 ||
 212                                         spare->tagByte6 != rbSpare.tagByte6 ||
 213                                         spare->tagByte7 != rbSpare.tagByte7 ||
 214                                         spare->ecc1[0]  != rbSpare.ecc1[0]  ||
 215                                         spare->ecc1[1]  != rbSpare.ecc1[1]  ||
 216                                         spare->ecc1[2]  != rbSpare.ecc1[2]  ||
 217                                         spare->ecc2[0]  != rbSpare.ecc2[0]  ||
 218                                         spare->ecc2[1]  != rbSpare.ecc2[1]  ||
 219                                         spare->ecc2[2]  != rbSpare.ecc2[2] )
 220                                 {
 221                                         // Didn't verify
 222                                         yaffs_DeleteChunk(dev,chunk);
 223                                         writeOk = 0;
 224                                 }
 225
 226                         }
 227                 }
 228         } while(chunk >= 0 && ! writeOk);
 229
 230         return chunk;
 231 }
 232
 233
 234
 235
 236 ///////////////////////// Object management //////////////////
 237 // List of spare objects
 238 // The list is hooked together using the first pointer
 239 // in the object
 240
 241 // static yaffs_Object *yaffs_freeObjects = NULL;
 242
 243 // static int yaffs_nFreeObjects;
 244
 245 // static yaffs_ObjectList *yaffs_allocatedObjectList = NULL;
 246
 247 // static yaffs_ObjectBucket yaffs_objectBucket[YAFFS_NOBJECT_BUCKETS];
 248
 249
 250 static __u16 yaffs_CalcNameSum(const char *name)
 251 {
 252         __u16 sum = 0;
 253         __u16 i = 1;
 254
 255         __u8 *bname = (__u8 *)name;
 256
 257         while (*bname)
 258         {
 259                 sum += (*bname) * i;
 260                 i++;
 261                 bname++;
 262         }
 263         return sum;
 264 }
 265
 266
 267 void yaffs_CalcECC(const __u8 *data, yaffs_Spare *spare)
 268 {
 269         nand_calculate_ecc (data , spare->ecc1);
 270         nand_calculate_ecc (&data[256] , spare->ecc2);
 271 }
 272
 273 void yaffs_CalcTagsECC(yaffs_Tags *tags)
 274 {
 275         // Todo don't do anything yet. Need to calculate ecc
 276         unsigned char *b = ((yaffs_TagsUnion *)tags)->asBytes;
 277         unsigned  i,j;
 278         unsigned  ecc = 0;
 279         unsigned bit = 0;
 280
 281         tags->ecc = 0;
 282
 283         for(i = 0; i < 8; i++)
 284         {
 285                 for(j = 1; j &0x7f; j<<=1)
 286                 {
 287                         bit++;
 288                         if(b[i] & j)
 289                         {
 290                                 ecc ^= bit;
 291                         }
 292                 }
 293         }
 294
 295         tags->ecc = ecc;
 296
 297
 298 }
 299
 300 void yaffs_CheckECCOnTags(yaffs_Tags *tags)
 301 {
 302         unsigned ecc = tags->ecc;
 303
 304         yaffs_CalcTagsECC(tags);
 305
 306         ecc ^= tags->ecc;
 307
 308         if(ecc)
 309         {
 310                 // Needs fixing
 311                 unsigned char *b = ((yaffs_TagsUnion *)tags)->asBytes;
 312
 313                 ecc--;
 314
 315                 b[ecc / 8] ^= (1 << (ecc & 7));
 316
 317                 // Now recvalc the ecc
 318                 yaffs_CalcTagsECC(tags);
 319         }
 320 }
 321
 322
 323 ///////////////////////// TNODES ///////////////////////
 324
 325 // List of spare tnodes
 326 // The list is hooked together using the first pointer
 327 // in the tnode.
 328
 329 //static yaffs_Tnode *yaffs_freeTnodes = NULL;
 330
 331 // static int yaffs_nFreeTnodes;
 332
 333 //static yaffs_TnodeList *yaffs_allocatedTnodeList = NULL;
 334
 335
 336
 337 // yaffs_CreateTnodes creates a bunch more tnodes and
 338 // adds them to the tnode free list.
 339 // Don't use this function directly
 340
 341 static int yaffs_CreateTnodes(yaffs_Device *dev,int nTnodes)
 342 {
 343     int i;
 344     yaffs_Tnode *newTnodes;
 345     yaffs_TnodeList *tnl;
 346
 347     if(nTnodes < 1) return YAFFS_OK;
 348
 349         // make these things
 350
 351     newTnodes = YMALLOC(nTnodes * sizeof(yaffs_Tnode));
 352
 353     if (!newTnodes)
 354     {
 355                 YALERT("Could not malloc tnodes");
 356                 return YAFFS_FAIL;
 357     }
 358
 359     // Hook them into the free list
 360     for(i = 0; i < nTnodes - 1; i++)
 361     {
 362         newTnodes[i].internal[0] = &newTnodes[i+1];
 363     }
 364
 365         newTnodes[nTnodes - 1].internal[0] = dev->freeTnodes;
 366         dev->freeTnodes = newTnodes;
 367         dev->nFreeTnodes+= nTnodes;
 368         dev->nTnodesCreated += nTnodes;
 369
 370         // Now add this bunch of tnodes to a list for freeing up.
 371
 372         tnl = YMALLOC(sizeof(yaffs_TnodeList));
 373         if(!tnl)
 374         {
 375                 YALERT("Could not add tnodes to management list");
 376         }
 377         else
 378         {
 379                 tnl->tnodes = newTnodes;
 380                 tnl->next = dev->allocatedTnodeList;
 381                 dev->allocatedTnodeList = tnl;
 382         }
 383
 384
 385         YINFO("Tnodes created");
 386
 387
 388         return YAFFS_OK;
 389 }
 390
 391
 392 // GetTnode gets us a clean tnode. Tries to make allocate more if we run out
 393 static yaffs_Tnode *yaffs_GetTnode(yaffs_Device *dev)
 394 {
 395         yaffs_Tnode *tn = NULL;
 396
 397         // If there are none left make more
 398         if(!dev->freeTnodes)
 399         {
 400                 yaffs_CreateTnodes(dev,YAFFS_ALLOCATION_NTNODES);
 401         }
 402
 403         if(dev->freeTnodes)
 404         {
 405                 tn = dev->freeTnodes;
 406                 dev->freeTnodes = dev->freeTnodes->internal[0];
 407                 dev->nFreeTnodes--;
 408                 // zero out
 409                 memset(tn,0,sizeof(yaffs_Tnode));
 410         }
 411
 412
 413         return tn;
 414 }
 415
 416
 417 // FreeTnode frees up a tnode and puts it back on the free list
 418 static void yaffs_FreeTnode(yaffs_Device*dev, yaffs_Tnode *tn)
 419 {
 420         tn->internal[0] = dev->freeTnodes;
 421         dev->freeTnodes = tn;
 422         dev->nFreeTnodes++;
 423 }
 424
 425
 426 static void yaffs_DeinitialiseTnodes(yaffs_Device*dev)
 427 {
 428         // Free the list of allocated tnodes
 429
 430         while(dev->allocatedTnodeList)
 431         {
 432                 YFREE(dev->allocatedTnodeList->tnodes);
 433                 dev->allocatedTnodeList =  dev->allocatedTnodeList->next;
 434         }
 435
 436         dev->freeTnodes = NULL;
 437         dev->nFreeTnodes = 0;
 438 }
 439
 440 static void yaffs_InitialiseTnodes(yaffs_Device*dev)
 441 {
 442         dev->allocatedTnodeList = NULL;
 443         dev->freeTnodes = NULL;
 444         dev->nFreeTnodes = 0;
 445         dev->nTnodesCreated = 0;
 446
 447 }
 448
 449 void yaffs_TnodeTest(yaffs_Device *dev)
 450 {
 451
 452         int i;
 453         int j;
 454         yaffs_Tnode *tn[1000];
 455
 456         YINFO("Testing TNodes");
 457
 458         for(j = 0; j < 50; j++)
 459         {
 460                 for(i = 0; i < 1000; i++)
 461                 {
 462                         tn[i] = yaffs_GetTnode(dev);
 463                         if(!tn[i])
 464                         {
 465                                 YALERT("Getting tnode failed");
 466                         }
 467                 }
 468                 for(i = 0; i < 1000; i+=3)
 469                 {
 470                         yaffs_FreeTnode(dev,tn[i]);
 471                         tn[i] = NULL;
 472                 }
 473
 474         }
 475 }
 476
 477 ////////////////// END OF TNODE MANIPULATION ///////////////////////////
 478
 479 /////////////// Functions to manipulate the look-up tree (made up of tnodes)
 480 // The look up tree is represented by the top tnode and the number of topLevel
 481 // in the tree. 0 means only the level 0 tnode is in the tree.
 482
 483
 484 // FindLevel0Tnode finds the level 0 tnode, if one exists.
 485 // Used when reading.....
 486 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device *dev,yaffs_FileStructure *fStruct, __u32 chunkId)
 487 {
 488
 489         yaffs_Tnode *tn = fStruct->top;
 490         __u32 i;
 491         int requiredTallness;
 492         int level = fStruct->topLevel;
 493
 494         // Check sane level and chunk Id
 495         if(level < 0 || level > YAFFS_TNODES_MAX_LEVEL)
 496         {
 497                 char str[50];
 498                 sprintf(str,"Bad level %d",level);
 499                 YALERT(str);
 500                 return NULL;
 501         }
 502         if(chunkId > YAFFS_MAX_CHUNK_ID)
 503         {
 504                 char str[50];
 505                 sprintf(str,"Bad chunkId %d",chunkId);
 506                 YALERT(str);
 507                 return NULL;
 508         }
 509
 510         // First check we're tall enough (ie enough topLevel)
 511
 512         i = chunkId >> (dev->chunkGroupBits + YAFFS_TNODES_LEVEL0_BITS);
 513         requiredTallness = 0;
 514         while(i)
 515         {
 516                 i >>= YAFFS_TNODES_INTERNAL_BITS;
 517                 requiredTallness++;
 518         }
 519
 520
 521         if(requiredTallness > fStruct->topLevel)
 522         {
 523                 // Not tall enough, so we can't find it, return NULL.
 524                 return NULL;
 525         }
 526
 527
 528         // Traverse down to level 0
 529         while (level > 0 && tn)
 530         {
 531             tn = tn->internal[(chunkId >>(dev->chunkGroupBits + YAFFS_TNODES_LEVEL0_BITS + (level-1) * YAFFS_TNODES_INTERNAL_BITS)) &
 532                                YAFFS_TNODES_INTERNAL_MASK];
 533                 level--;
 534
 535         }
 536
 537         return tn;
 538 }
 539
 540 // AddOrFindLevel0Tnode finds the level 0 tnode if it exists, otherwise first expands the tree.
 541 // This happens in two steps:
 542 //  1. If the tree isn't tall enough, then make it taller.
 543 //  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
 544 //
 545 // Used when modifying the tree.
 546 //
 547 static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device *dev, yaffs_FileStructure *fStruct, __u32 chunkId)
 548 {
 549
 550         yaffs_Tnode *tn;
 551
 552         int requiredTallness;
 553
 554         __u32 i;
 555         __u32 l;
 556
 557
 558         T(("AddOrFind topLevel=%d, chunk=%d",fStruct->topLevel,chunkId));
 559
 560         // Check sane level and page Id
 561         if(fStruct->topLevel < 0 || fStruct->topLevel > YAFFS_TNODES_MAX_LEVEL)
 562         {
 563                 char str[50];
 564                 sprintf(str,"Bad level %d",fStruct->topLevel);
 565                 YALERT(str);
 566                 return NULL;
 567         }
 568
 569         if(chunkId > YAFFS_MAX_CHUNK_ID)
 570         {
 571                 char str[50];
 572                 sprintf(str,"Bad chunkId %d",chunkId);
 573                 YALERT(str);
 574                 return NULL;
 575         }
 576
 577         // First check we're tall enough (ie enough topLevel)
 578
 579         i = chunkId >> (dev->chunkGroupBits + YAFFS_TNODES_LEVEL0_BITS);
 580         requiredTallness = 0;
 581         while(i)
 582         {
 583                 i >>= YAFFS_TNODES_INTERNAL_BITS;
 584                 requiredTallness++;
 585         }
 586
 587         T((" required=%d",requiredTallness));
 588
 589
 590         if(requiredTallness > fStruct->topLevel)
 591         {
 592                 // Not tall enough,gotta make the tree taller
 593                 for(i = fStruct->topLevel; i < requiredTallness; i++)
 594                 {
 595                         T((" add new top"));
 596
 597                         tn = yaffs_GetTnode(dev);
 598
 599                         if(tn)
 600                         {
 601                                 tn->internal[0] = fStruct->top;
 602                                 fStruct->top = tn;
 603                         }
 604                         else
 605                         {
 606                                 YALERT("No more tnodes");
 607                         }
 608                 }
 609
 610                 fStruct->topLevel = requiredTallness;
 611         }
 612
 613
 614         // Traverse down to level 0, adding anything we need
 615
 616         l = fStruct->topLevel;
 617         tn = fStruct->top;
 618         while (l > 0 && tn)
 619         {
 620                 i = (chunkId >> (dev->chunkGroupBits +YAFFS_TNODES_LEVEL0_BITS + (l-1) * YAFFS_TNODES_INTERNAL_BITS)) &
 621                                YAFFS_TNODES_INTERNAL_MASK;
 622
 623                 T((" [%d:%d]",l,i));
 624
 625             if(!tn->internal[i])
 626             {
 627                 T((" added"));
 628
 629                 tn->internal[i] = yaffs_GetTnode(dev);
 630             }
 631
 632             tn =        tn->internal[i];
 633                 l--;
 634
 635         }
 636
 637         T(("\n"));
 638
 639         return tn;
 640 }
 641
 642
 643 // Pruning removes any part of the file structure tree that is beyond the
 644 // bounds of the file.
 645 // A file should only get pruned when its size is reduced.
 646 //
 647 // Before pruning, the chunks must be pulled from the tree and the
 648 // level 0 tnode entries must be zeroed out.
 649 // Could also use this for file deletion, but that's probably better handled
 650 // by a special case.
 651
 652 // yaffs_PruneWorker should only be called by yaffs_PruneFileStructure()
 653
 654 static yaffs_Tnode *yaffs_PruneWorker(yaffs_Device *dev, yaffs_Tnode *tn, __u32 level, int del0)
 655 {
 656         int i;
 657         int hasData;
 658
 659         if(tn)
 660         {
 661                 hasData = 0;
 662
 663                 for(i = 0; i < YAFFS_NTNODES_INTERNAL; i++)
 664                 {
 665                     if(tn->internal[i] && level > 0)
 666                     {
 667                         tn->internal[i] = yaffs_PruneWorker(dev,tn->internal[i],level - 1, ( i == 0) ? del0 : 1);
 668                     }
 669
 670                     if(tn->internal[i])
 671                     {
 672                         hasData++;
 673                         }
 674                 }
 675
 676                 if(hasData == 0 && del0)
 677                 {
 678                         // Free and return NULL
 679
 680                         yaffs_FreeTnode(dev,tn);
 681                         tn = NULL;
 682                 }
 683
 684         }
 685
 686         return tn;
 687
 688 }
 689
 690 static int yaffs_PruneFileStructure(yaffs_Device *dev, yaffs_FileStructure *fStruct)
 691 {
 692         int i;
 693         int hasData;
 694         int done = 0;
 695         yaffs_Tnode *tn;
 696
 697         if(fStruct->topLevel > 0)
 698         {
 699                 fStruct->top = yaffs_PruneWorker(dev,fStruct->top, fStruct->topLevel,0);
 700
 701                 // Now we have a tree with all the non-zero branches NULL but the height
 702                 // is the same as it was.
 703                 // Let's see if we can trim internal tnodes to shorten the tree.
 704                 // We can do this if only the 0th element in the tnode is in use
 705                 // (ie all the non-zero are NULL)
 706
 707                 while(fStruct->topLevel && !done)
 708                 {
 709                         tn = fStruct->top;
 710
 711                         hasData = 0;
 712                         for(i = 1; i <YAFFS_NTNODES_INTERNAL; i++)
 713                         {
 714                                 if(tn->internal[i])
 715                         {
 716                                 hasData++;
 717                                 }
 718                         }
 719
 720                         if(!hasData)
 721                         {
 722                                 fStruct->top = tn->internal[0];
 723                                 fStruct->topLevel--;
 724                                 yaffs_FreeTnode(dev,tn);
 725                         }
 726                         else
 727                         {
 728                                 done = 1;
 729                         }
 730                 }
 731         }
 732
 733         return YAFFS_OK;
 734 }
 735
 736
 737
 738
 739 /////////////////////// End of File Structure functions. /////////////////
 740
 741 // yaffs_CreateFreeObjects creates a bunch more objects and
 742 // adds them to the object free list.
 743 static int yaffs_CreateFreeObjects(yaffs_Device *dev, int nObjects)
 744 {
 745     int i;
 746     yaffs_Object *newObjects;
 747     yaffs_ObjectList *list;
 748
 749     if(nObjects < 1) return YAFFS_OK;
 750
 751         // make these things
 752
 753     newObjects = YMALLOC(nObjects * sizeof(yaffs_Object));
 754
 755     if (!newObjects)
 756     {
 757                 YALERT("Could not allocate more objects");
 758                 return YAFFS_FAIL;
 759     }
 760
 761     // Hook them into the free list
 762     for(i = 0; i < nObjects - 1; i++)
 763     {
 764         (yaffs_Object *)newObjects[i].siblings.next = &newObjects[i+1];
 765     }
 766
 767         newObjects[nObjects - 1].siblings.next = (void *)dev->freeObjects;
 768         dev->freeObjects = newObjects;
 769         dev->nFreeObjects+= nObjects;
 770         dev->nObjectsCreated+= nObjects;
 771
 772         // Now add this bunch of Objects to a list for freeing up.
 773
 774         list = YMALLOC(sizeof(yaffs_ObjectList));
 775         if(!list)
 776         {
 777                 YALERT("Could not add Objects to management list");
 778         }
 779         else
 780         {
 781                 list->objects = newObjects;
 782                 list->next = dev->allocatedObjectList;
 783                 dev->allocatedObjectList = list;
 784         }
 785
 786
 787         YINFO("Objects created");
 788
 789
 790         return YAFFS_OK;
 791 }
 792
 793
 794 // AllocateEmptyObject gets us a clean Object. Tries to make allocate more if we run out
 795 static yaffs_Object *yaffs_AllocateEmptyObject(yaffs_Device *dev)
 796 {
 797         yaffs_Object *tn = NULL;
 798
 799         // If there are none left make more
 800         if(!dev->freeObjects)
 801         {
 802                 yaffs_CreateFreeObjects(dev,YAFFS_ALLOCATION_NOBJECTS);
 803         }
 804
 805         if(dev->freeObjects)
 806         {
 807                 tn = dev->freeObjects;
 808                 dev->freeObjects = (yaffs_Object *)(dev->freeObjects->siblings.next);
 809                 dev->nFreeObjects--;
 810
 811                 // Now sweeten it up...
 812
 813                 memset(tn,0,sizeof(yaffs_Object));
 814                 tn->chunkId = -1;
 815                 tn->variantType = YAFFS_OBJECT_TYPE_UNKNOWN;
 816                 INIT_LIST_HEAD(&(tn->hardLinks));
 817                 INIT_LIST_HEAD(&(tn->hashLink));
 818                 INIT_LIST_HEAD(&tn->siblings);
 819
 820                 // Add it to the lost and found directory.
 821                 // NB Can't put root or lostNFound in lostNFound so
 822                 // check if lostNFound exists first
 823                 if(dev->lostNFoundDir)
 824                 {
 825                         yaffs_AddObjectToDirectory(dev->lostNFoundDir,tn);
 826                 }
 827         }
 828
 829
 830         return tn;
 831 }
 832
 833 static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device *dev,int number,__u32 mode)
 834 {
 835
 836         yaffs_Object *obj = yaffs_CreateNewObject(dev,number,YAFFS_OBJECT_TYPE_DIRECTORY);
 837         if(obj)
 838         {
 839                 obj->fake = 1;                  // it is fake so it has no NAND presence...
 840                 obj->renameAllowed= 0;  // ... and we're not allowed to rename it...
 841                 obj->unlinkAllowed= 0;  // ... or unlink it
 842                 obj->st_mode = mode;
 843                 obj->myDev = dev;
 844                 obj->chunkId = 0; // Not a valid chunk.
 845         }
 846
 847         return obj;
 848
 849 }
 850
 851
 852 static void yaffs_UnhashObject(yaffs_Object *tn)
 853 {
 854         int bucket;
 855         yaffs_Device *dev = tn->myDev;
 856
 857
 858         // If it is still linked into the bucket list, free from the list
 859         if(!list_empty(&tn->hashLink))
 860         {
 861                 list_del_init(&tn->hashLink);
 862                 bucket =  yaffs_HashFunction(tn->objectId);
 863                 dev->objectBucket[bucket].count--;
 864         }
 865
 866 }
 867
 868
 869 // FreeObject frees up a Object and puts it back on the free list
 870 static void yaffs_FreeObject(yaffs_Object *tn)
 871 {
 872
 873         yaffs_Device *dev = tn->myDev;
 874
 875         yaffs_UnhashObject(tn);
 876
 877         // Link into the free list.
 878         (yaffs_Object *)(tn->siblings.next) = dev->freeObjects;
 879         dev->freeObjects = tn;
 880         dev->nFreeObjects++;
 881 }
 882
 883
 884
 885
 886 static void yaffs_DeinitialiseObjects(yaffs_Device *dev)
 887 {
 888         // Free the list of allocated Objects
 889
 890         while( dev->allocatedObjectList)
 891         {
 892                 YFREE(dev->allocatedObjectList->objects);
 893                 dev->allocatedObjectList =  dev->allocatedObjectList->next;
 894         }
 895
 896         dev->freeObjects = NULL;
 897         dev->nFreeObjects = 0;
 898 }
 899
 900 static void yaffs_InitialiseObjects(yaffs_Device *dev)
 901 {
 902         int i;
 903
 904         dev->allocatedObjectList = NULL;
 905         dev->freeObjects = NULL;
 906         dev->nFreeObjects = 0;
 907
 908         for(i = 0; i < YAFFS_NOBJECT_BUCKETS; i++)
 909         {
 910                 INIT_LIST_HEAD(&dev->objectBucket[i].list);
 911                 dev->objectBucket[i].count = 0;
 912         }
 913
 914 }
 915
 916
 917
 918
 919
 920
 921 int yaffs_FindNiceObjectBucket(yaffs_Device *dev)
 922 {
 923         static int x = 0;
 924         int i;
 925         int l = 999;
 926         int lowest = 999999;
 927
 928
 929         // First let's see if we can find one that's empty.
 930
 931         for(i = 0; i < 10 && lowest > 0; i++)
 932          {
 933                 x++;
 934                 x %=  YAFFS_NOBJECT_BUCKETS;
 935                 if(dev->objectBucket[x].count < lowest)
 936                 {
 937                         lowest = dev->objectBucket[x].count;
 938                         l = x;
 939                 }
 940
 941         }
 942
 943         // If we didn't find an empty list, then try
 944         // looking a bit further for a short one
 945
 946         for(i = 0; i < 10 && lowest > 3; i++)
 947          {
 948                 x++;
 949                 x %=  YAFFS_NOBJECT_BUCKETS;
 950                 if(dev->objectBucket[x].count < lowest)
 951                 {
 952                         lowest = dev->objectBucket[x].count;
 953                         l = x;
 954                 }
 955
 956         }
 957
 958         return l;
 959 }
 960
 961 static int yaffs_CreateNewObjectNumber(yaffs_Device *dev)
 962 {
 963         int bucket = yaffs_FindNiceObjectBucket(dev);
 964
 965         // Now find an object value that has not already been taken
 966         // by scanning the list.
 967
 968         int found = 0;
 969         struct list_head *i;
 970
 971         int n = bucket;
 972
 973         //yaffs_CheckObjectHashSanity();
 974
 975         while(!found)
 976         {
 977                 found = 1;
 978                 n +=  YAFFS_NOBJECT_BUCKETS;
 979                 if(1 ||dev->objectBucket[bucket].count > 0)
 980                 {
 981                         list_for_each(i,&dev->objectBucket[bucket].list)
 982                         {
 983                                 // If there is already one in the list
 984                                 if(list_entry(i, yaffs_Object,hashLink)->objectId == n)
 985                                 {
 986                                         found = 0;
 987                                 }
 988                         }
 989                 }
 990         }
 991
 992         //T(("bucket %d count %d inode %d\n",bucket,yaffs_objectBucket[bucket].count,n);
 993
 994         return n;
 995 }
 996
 997 void yaffs_HashObject(yaffs_Object *in)
 998 {
 999         int bucket = yaffs_HashFunction(in->objectId);
1000         yaffs_Device *dev = in->myDev;
1001
1002         if(!list_empty(&in->hashLink))
1003         {
1004                 YINFO("!!!");
1005         }
1006
1007
1008         list_add(&in->hashLink,&dev->objectBucket[bucket].list);
1009         dev->objectBucket[bucket].count++;
1010
1011 }
1012
1013 yaffs_Object *yaffs_FindObjectByNumber(yaffs_Device *dev,int number)
1014 {
1015         int bucket = yaffs_HashFunction(number);
1016         struct list_head *i;
1017         yaffs_Object *in;
1018
1019         list_for_each(i,&dev->objectBucket[bucket].list)
1020         {
1021                 // Lookm if it is in the list
1022                 in = list_entry(i, yaffs_Object,hashLink);
1023                 if(in->objectId == number)
1024                 {
1025                         return in;
1026                 }
1027         }
1028
1029         return NULL;
1030 }
1031
1032
1033
1034 yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type)
1035 {
1036
1037         yaffs_Object *theObject;
1038
1039         if(number < 0)
1040         {
1041                 number = yaffs_CreateNewObjectNumber(dev);
1042         }
1043
1044         theObject = yaffs_AllocateEmptyObject(dev);
1045
1046         if(theObject)
1047         {
1048                 theObject->fake = 0;
1049                 theObject->renameAllowed = 1;
1050                 theObject->unlinkAllowed = 1;
1051                 theObject->objectId = number;
1052                 theObject->myDev = dev;
1053                 yaffs_HashObject(theObject);
1054                 theObject->variantType = type;
1055                 theObject->st_atime = theObject->st_mtime =     theObject->st_ctime = CURRENT_TIME;
1056
1057                 switch(type)
1058                 {
1059                         case YAFFS_OBJECT_TYPE_FILE:
1060                                 theObject->variant.fileVariant.fileSize = 0;
1061                                 theObject->variant.fileVariant.topLevel = 0;
1062                                 theObject->variant.fileVariant.top  = yaffs_GetTnode(dev);
1063                                 break;
1064                         case YAFFS_OBJECT_TYPE_DIRECTORY:
1065                                 INIT_LIST_HEAD(&theObject->variant.directoryVariant.children);
1066                                 break;
1067                         case YAFFS_OBJECT_TYPE_SYMLINK:
1068                                 // No action required
1069                                 break;
1070                         case YAFFS_OBJECT_TYPE_HARDLINK:
1071                                 // No action required
1072                                 break;
1073                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1074                                 // todo this should not happen
1075                 }
1076         }
1077
1078         return theObject;
1079 }
1080
1081 yaffs_Object *yaffs_FindOrCreateObjectByNumber(yaffs_Device *dev, int number,yaffs_ObjectType type)
1082 {
1083         yaffs_Object *theObject = NULL;
1084
1085         if(number >= 0)
1086         {
1087                 theObject = yaffs_FindObjectByNumber(dev,number);
1088         }
1089
1090         if(!theObject)
1091         {
1092                 theObject = yaffs_CreateNewObject(dev,number,type);
1093         }
1094
1095         return theObject;
1096
1097 }
1098
1099 char *yaffs_CloneString(const char *str)
1100 {
1101         char *newStr = NULL;
1102
1103         if(str && *str)
1104         {
1105                 newStr = YMALLOC(strlen(str) + 1);
1106                 strcpy(newStr,str);
1107         }
1108
1109         return newStr;
1110
1111 }
1112
1113 //
1114 // Mknod (create) a new object.
1115 // equivalentObject only has meaning for a hard link;
1116 // aliasString only has meaning for a sumlink.
1117 yaffs_Object *yaffs_MknodObject( yaffs_ObjectType type,
1118                                                                  yaffs_Object *parent,
1119                                                                  const char *name,
1120                                                                  __u32 mode,
1121                                                                  __u32 uid,
1122                                                                  __u32 gid,
1123                                                                  yaffs_Object *equivalentObject,
1124                                                                  const char *aliasString)
1125 {
1126         yaffs_Object *in;
1127
1128         yaffs_Device *dev = parent->myDev;
1129
1130         in = yaffs_CreateNewObject(dev,-1,type);
1131
1132         if(in)
1133         {
1134                 in->chunkId = -1;
1135                 in->valid = 1;
1136                 in->variantType = type;
1137
1138                 in->st_mode  = mode;
1139                 in->st_uid   = uid;
1140                 in->st_gid   = gid;
1141                 in->st_atime =  in->st_mtime =  in->st_ctime = CURRENT_TIME;
1142
1143                 in->sum = yaffs_CalcNameSum(name);
1144                 in->dirty = 1;
1145
1146                 yaffs_AddObjectToDirectory(parent,in);
1147
1148                 in->myDev = parent->myDev;
1149
1150
1151                 switch(type)
1152                 {
1153                         case YAFFS_OBJECT_TYPE_SYMLINK:
1154                                 in->variant.symLinkVariant.alias = yaffs_CloneString(aliasString);
1155                                 break;
1156                         case YAFFS_OBJECT_TYPE_HARDLINK:
1157                                 in->variant.hardLinkVariant.equivalentObject = equivalentObject;
1158                                 in->variant.hardLinkVariant.equivalentObjectId = equivalentObject->objectId;
1159                                 list_add(&in->hardLinks,&equivalentObject->hardLinks);
1160                                 break;
1161                         case YAFFS_OBJECT_TYPE_FILE: // do nothing
1162                         case YAFFS_OBJECT_TYPE_DIRECTORY: // do nothing
1163                         case YAFFS_OBJECT_TYPE_UNKNOWN:
1164                 }
1165
1166                 yaffs_UpdateObjectHeader(in,name);
1167
1168         }
1169
1170         return in;
1171 }
1172
1173 yaffs_Object *yaffs_MknodFile(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid)
1174 {
1175         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_FILE,parent,name,mode,uid,gid,NULL,NULL);
1176 }
1177
1178 yaffs_Object *yaffs_MknodDirectory(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid)
1179 {
1180         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_DIRECTORY,parent,name,mode,uid,gid,NULL,NULL);
1181 }
1182
1183 yaffs_Object *yaffs_MknodSymLink(yaffs_Object *parent,const char *name, __u32 mode, __u32 uid, __u32 gid,const char *alias)
1184 {
1185         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SYMLINK,parent,name,mode,uid,gid,NULL,alias);
1186 }
1187
1188 // NB yaffs_Link returns the object id of the equivalent object.
1189 yaffs_Object *yaffs_Link(yaffs_Object *parent, const char *name, yaffs_Object *equivalentObject)
1190 {
1191         // Get the real object in case we were fed a hard link as an equivalent object
1192         equivalentObject = yaffs_GetEquivalentObject(equivalentObject);
1193
1194         if(yaffs_MknodObject(YAFFS_OBJECT_TYPE_HARDLINK,parent,name,0,0,0,equivalentObject,NULL))
1195         {
1196                 return equivalentObject;
1197         }
1198         else
1199         {
1200                 return NULL;
1201         }
1202
1203 }
1204
1205
1206 static int yaffs_ChangeObjectName(yaffs_Object *obj, yaffs_Object *newDir, const char *newName)
1207 {
1208         //yaffs_Device *dev = obj->myDev;
1209
1210         if(newDir == NULL)
1211         {
1212                 newDir = obj->parent; // use the old directory
1213         }
1214
1215         // Only proceed if the new name does not exist and
1216         // if we're putting it into a directory.
1217         if(!yaffs_FindObjectByName(newDir,newName) &&
1218             newDir->variantType == YAFFS_OBJECT_TYPE_DIRECTORY)
1219         {
1220                 obj->sum = yaffs_CalcNameSum(newName);
1221                 obj->dirty = 1;
1222                 yaffs_AddObjectToDirectory(newDir,obj);
1223
1224                 return yaffs_UpdateObjectHeader(obj,newName);
1225         }
1226
1227         return YAFFS_FAIL;
1228 }
1229
1230 int yaffs_RenameObject(yaffs_Object *oldDir, const char *oldName, yaffs_Object *newDir, const char *newName)
1231 {
1232         yaffs_Object *obj;
1233
1234         obj = yaffs_FindObjectByName(oldDir,oldName);
1235         if(obj && obj->renameAllowed)
1236         {
1237                 return yaffs_ChangeObjectName(obj,newDir,newName);
1238         }
1239         return YAFFS_FAIL;
1240 }
1241
1242
1243
1244 static int yaffs_CheckObjectHashSanity(yaffs_Device *dev)
1245 {
1246         // Scan the buckets and check that the lists
1247         // have as many members as the count says there are
1248         int bucket;
1249         int countEm;
1250         struct list_head *j;
1251         int ok = YAFFS_OK;
1252
1253         for(bucket = 0; bucket < YAFFS_NOBJECT_BUCKETS; bucket++)
1254         {
1255                 countEm = 0;
1256
1257                 list_for_each(j,&dev->objectBucket[bucket].list)
1258                 {
1259                         countEm++;
1260                 }
1261
1262                 if(countEm != dev->objectBucket[bucket].count)
1263                 {
1264                         YALERT("Inode hash inconsistency");
1265                         ok = YAFFS_FAIL;
1266                 }
1267         }
1268
1269         return ok;
1270 }
1271
1272 void yaffs_ObjectTest(yaffs_Device *dev)
1273 {
1274         yaffs_Object *in[1000];
1275         int inNo[1000];
1276         yaffs_Object *inold[1000];
1277         int i;
1278         int j;
1279
1280         memset(in,0,1000*sizeof(yaffs_Object *));
1281         memset(inold,0,1000*sizeof(yaffs_Object *));
1282
1283         yaffs_CheckObjectHashSanity(dev);
1284
1285         for(j = 0; j < 10; j++)
1286         {
1287                 T(("%d\n",j));
1288
1289                 for(i = 0; i < 1000; i++)
1290                 {
1291                         in[i] = yaffs_CreateNewObject(dev,-1,YAFFS_OBJECT_TYPE_FILE);
1292                         if(!in[i])
1293                         {
1294                                 YINFO("No more inodes");
1295                         }
1296                         else
1297                         {
1298                                 inNo[i] = in[i]->objectId;
1299                         }
1300                 }
1301
1302                 for(i = 0; i < 1000; i++)
1303                 {
1304                         if(yaffs_FindObjectByNumber(dev,inNo[i]) != in[i])
1305                         {
1306                                 T(("Differnce in look up test\n"));
1307                         }
1308                         else
1309                         {
1310                                 // T(("Look up ok\n"));
1311                         }
1312                 }
1313
1314                 yaffs_CheckObjectHashSanity(dev);
1315
1316                 for(i = 0; i < 1000; i+=3)
1317                 {
1318                         yaffs_FreeObject(in[i]);
1319                         in[i] = NULL;
1320                 }
1321
1322
1323                 yaffs_CheckObjectHashSanity(dev);
1324         }
1325
1326 }
1327
1328
1329
1330 /////////////////////////// Block Management and Page Allocation ///////////////////
1331
1332
1333 static void yaffs_InitialiseBlocks(yaffs_Device *dev)
1334 {
1335         dev->blockInfo = YMALLOC(dev->nBlocks * sizeof(yaffs_BlockInfo));
1336         memset(dev->blockInfo,0,dev->nBlocks * sizeof(yaffs_BlockInfo));
1337         dev->allocationBlock = -1; // force it to get a new one
1338 }
1339
1340 static void yaffs_DeinitialiseBlocks(yaffs_Device *dev)
1341 {
1342         YFREE(dev->blockInfo);
1343 }
1344
1345 // FindDiretiestBlock is used to select the dirtiest block (or close enough)
1346 // for garbage collection.
1347
1348 static int yaffs_FindDirtiestBlock(yaffs_Device *dev)
1349 {
1350
1351         int b = dev->currentDirtyChecker;
1352
1353         int i;
1354         int dirtiest = -1;
1355         int pagesInUse = 100; // silly big number
1356
1357         for(i = dev->startBlock; i <= dev->endBlock && pagesInUse > 2 ; i++)
1358         {
1359                 b++;
1360                 if (b > dev->endBlock)
1361                 {
1362                         b =  dev->startBlock;
1363                 }
1364
1365                 if(dev->blockInfo[b].blockState == YAFFS_BLOCK_STATE_FULL &&
1366                    (dev->blockInfo)[b].pagesInUse < pagesInUse)
1367                 {
1368                         dirtiest = b;
1369                         pagesInUse = (dev->blockInfo)[b].pagesInUse;
1370                 }
1371         }
1372
1373         dev->currentDirtyChecker = b;
1374
1375         return dirtiest;
1376 }
1377
1378
1379 static int yaffs_FindBlockForAllocation(yaffs_Device *dev,int useReserve)
1380 {
1381         int i;
1382
1383         if(useReserve && dev->nErasedBlocks < 1)
1384         {
1385                 // Hoosterman we've got a problem.
1386                 // Can't get space to gc
1387                 return -1;
1388         }
1389         else if(!useReserve && dev->nErasedBlocks <= YAFFS_RESERVED_BLOCKS)
1390         {
1391                 // We are not in GC, so we hold some in reserve so we can get
1392                 // a gc done.
1393         }
1394
1395         // Find an empty block.
1396
1397         for(i = dev->startBlock; i <= dev->endBlock; i++)
1398         {
1399
1400                 if(dev->blockInfo[i].blockState == YAFFS_BLOCK_STATE_EMPTY)
1401                 {
1402                         dev->blockInfo[i].blockState = YAFFS_BLOCK_STATE_ALLOCATING;
1403                         dev->nErasedBlocks--;
1404                         if(dev->nErasedBlocks <= YAFFS_RESERVED_BLOCKS)
1405                         {
1406                                 dev->garbageCollectionRequired = 1;
1407                         }
1408
1409                         return i;
1410                 }
1411         }
1412
1413         return -1;
1414 }
1415
1416
1417 static void yaffs_BlockBecameDirty(yaffs_Device *dev,int blockNo)
1418 {
1419         yaffs_BlockInfo *bi = &dev->blockInfo[blockNo];
1420
1421         // Mark as dirty, erase it and mark as clean.
1422         bi->blockState = YAFFS_BLOCK_STATE_DIRTY;
1423         yaffs_EraseBlockInNAND(dev,blockNo);
1424         bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
1425         dev->nErasedBlocks++;
1426         bi->pagesInUse = 0;
1427         bi->pageBits = 0;
1428
1429         T(("Erased block %d\n",blockNo));
1430 }
1431
1432
1433 static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve)
1434 {
1435         int retVal;
1436
1437         if(dev->allocationBlock < 0)
1438         {
1439                 // Get next block to allocate off
1440                 dev->allocationBlock = yaffs_FindBlockForAllocation(dev,useReserve);
1441                 dev->allocationPage = 0;
1442         }
1443
1444         // Next page please....
1445         if(dev->allocationBlock >= 0)
1446         {
1447                 retVal = (dev->allocationBlock * YAFFS_CHUNKS_PER_BLOCK) +
1448                                   dev->allocationPage;
1449                 dev->blockInfo[dev->allocationBlock].pagesInUse++;
1450                 dev->blockInfo[dev->allocationBlock].pageBits |=
1451                                 (1 << (dev->allocationPage));
1452
1453                 dev->allocationPage++;
1454
1455                 dev->nFreeChunks--;
1456
1457                 // If the block is full set the state to full
1458                 if(dev->allocationPage >= YAFFS_CHUNKS_PER_BLOCK)
1459                 {
1460                         dev->blockInfo[dev->allocationBlock].blockState = YAFFS_BLOCK_STATE_FULL;
1461                         dev->allocationBlock = -1;
1462                 }
1463
1464 #ifdef YAFFS_PARANOID
1465                 if(yaffs_CheckChunkErased(dev,retVal) == YAFFS_FAIL)
1466                 {
1467                         T(("..................Trying to allocate non-erased page %d\n",retVal));
1468                 }
1469 #endif
1470                 return retVal;
1471
1472         }
1473         T(("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!\n"));
1474
1475         return -1;
1476 }
1477
1478
1479 int  yaffs_GarbageCollectBlock(yaffs_Device *dev,int block)
1480 {
1481         int oldChunk;
1482         int newChunk;
1483         __u32 mask;
1484
1485
1486         yaffs_Spare spare;
1487         yaffs_Tags  tags;
1488                 __u8  buffer[YAFFS_BYTES_PER_CHUNK];
1489
1490         yaffs_BlockInfo *bi = &dev->blockInfo[block];
1491
1492         yaffs_Object *object;
1493
1494         T(("Collecting block %d n %d bits %x\n",block, bi->pagesInUse, bi->pageBits));
1495
1496         for(mask = 1,oldChunk = block * YAFFS_CHUNKS_PER_BLOCK;
1497             mask && bi->pageBits;
1498             mask <<= 1, oldChunk++ )
1499         {
1500                 if(bi->pageBits & mask)
1501                 {
1502
1503                         // This page is in use and needs to be copied off
1504
1505                         T(("copying page %x from %d to %d\n",mask,oldChunk,newChunk));
1506
1507                         yaffs_ReadChunkFromNAND(dev,oldChunk,buffer, &spare);
1508
1509                         yaffs_GetTagsFromSpare(&spare,&tags);
1510                         tags.serialNumber++;
1511                         yaffs_LoadTagsIntoSpare(&spare,&tags);
1512
1513 #if 0
1514                         newChunk = yaffs_AllocatePage(dev,1);
1515                         if(newChunk < 0)
1516                         {
1517                                 return YAFFS_FAIL;
1518                         }
1519
1520                         yaffs_WriteChunkToNAND(dev,newChunk, buffer, &spare);
1521
1522 #else
1523                         newChunk = yaffs_WriteNewChunkToNAND(dev, buffer, &spare,1);
1524 #endif
1525                         if(newChunk < 0)
1526                         {
1527                                 return YAFFS_FAIL;
1528                         }
1529
1530                         object = yaffs_FindObjectByNumber(dev,tags.objectId);
1531
1532                         // Ok, now fix up the Tnodes etc.
1533
1534                         if(tags.chunkId == 0)
1535                         {
1536                                 // It's a header
1537                                 object->chunkId = newChunk;
1538                         }
1539                         else
1540                         {
1541                                 // It's a data chunk
1542                                 yaffs_PutChunkIntoFile(object, tags.chunkId, newChunk,0);
1543
1544                         }
1545
1546                         yaffs_DeleteChunk(dev,oldChunk);
1547
1548                 }
1549         }
1550
1551         return YAFFS_OK;
1552 }
1553
1554 int yaffs_CheckGarbageCollection(yaffs_Device *dev)
1555 {
1556         int block;
1557
1558         if(dev->garbageCollectionRequired)
1559         {
1560                 dev->garbageCollectionRequired = 0;
1561                 block = yaffs_FindDirtiestBlock(dev);
1562                 if(block >= 0)
1563                 {
1564                         return yaffs_GarbageCollectBlock(dev,block);
1565                 }
1566                 else
1567                 {
1568                         return YAFFS_FAIL;
1569                 }
1570         }
1571
1572         return YAFFS_OK;
1573 }
1574
1575
1576 //////////////////////////// TAGS ///////////////////////////////////////
1577
1578 static void yaffs_LoadTagsIntoSpare(yaffs_Spare *sparePtr, yaffs_Tags *tagsPtr)
1579 {
1580         yaffs_TagsUnion *tu = (yaffs_TagsUnion *)tagsPtr;
1581
1582         yaffs_CalcTagsECC(tagsPtr);
1583
1584         sparePtr->tagByte0 = tu->asBytes[0];
1585         sparePtr->tagByte1 = tu->asBytes[1];
1586         sparePtr->tagByte2 = tu->asBytes[2];
1587         sparePtr->tagByte3 = tu->asBytes[3];
1588         sparePtr->tagByte4 = tu->asBytes[4];
1589         sparePtr->tagByte5 = tu->asBytes[5];
1590         sparePtr->tagByte6 = tu->asBytes[6];
1591         sparePtr->tagByte7 = tu->asBytes[7];
1592 }
1593
1594 static void yaffs_GetTagsFromSpare(yaffs_Spare *sparePtr,yaffs_Tags *tagsPtr)
1595 {
1596         yaffs_TagsUnion *tu = (yaffs_TagsUnion *)tagsPtr;
1597
1598         tu->asBytes[0]= sparePtr->tagByte0;
1599         tu->asBytes[1]= sparePtr->tagByte1;
1600         tu->asBytes[2]= sparePtr->tagByte2;
1601         tu->asBytes[3]= sparePtr->tagByte3;
1602         tu->asBytes[4]= sparePtr->tagByte4;
1603         tu->asBytes[5]= sparePtr->tagByte5;
1604         tu->asBytes[6]= sparePtr->tagByte6;
1605         tu->asBytes[7]= sparePtr->tagByte7;
1606
1607         yaffs_CheckECCOnTags(tagsPtr);
1608 }
1609
1610 static void yaffs_SpareInitialise(yaffs_Spare *spare)
1611 {
1612         memset(spare,0xFF,sizeof(yaffs_Spare));
1613 }
1614
1615 static int yaffs_ReadChunkTagsFromNAND(yaffs_Device *dev,int chunkInNAND, yaffs_Tags *tags)
1616 {
1617         if(tags)
1618         {
1619                 yaffs_Spare spare;
1620                 if(yaffs_ReadChunkFromNAND(dev,chunkInNAND,NULL,&spare) == YAFFS_OK)
1621                 {
1622                         yaffs_GetTagsFromSpare(&spare,tags);
1623                         return YAFFS_OK;
1624                 }
1625                 else
1626                 {
1627                         return YAFFS_FAIL;
1628                 }
1629         }
1630
1631         return YAFFS_OK;
1632 }
1633
1634 static int yaffs_WriteChunkWithTagsToNAND(yaffs_Device *dev,int chunkInNAND, const __u8 *buffer, yaffs_Tags *tags)
1635 {
1636         // NB There must be tags, data is optional
1637         // If there is data, then an ECC is calculated on it.
1638
1639         yaffs_Spare spare;
1640
1641         if(!tags)
1642         {
1643                 return YAFFS_FAIL;
1644         }
1645
1646         yaffs_SpareInitialise(&spare);
1647
1648
1649         if(buffer)
1650         {
1651                 yaffs_CalcECC(buffer,&spare);
1652         }
1653
1654         yaffs_LoadTagsIntoSpare(&spare,tags);
1655
1656         return yaffs_WriteChunkToNAND(dev,chunkInNAND,buffer,&spare);
1657
1658 }
1659
1660 static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device *dev, const __u8 *buffer, yaffs_Tags *tags, int useReserve)
1661 {
1662         // NB There must be tags, data is optional
1663         // If there is data, then an ECC is calculated on it.
1664
1665         yaffs_Spare spare;
1666
1667         if(!tags)
1668         {
1669                 return YAFFS_FAIL;
1670         }
1671
1672         yaffs_SpareInitialise(&spare);
1673
1674
1675         if(buffer)
1676         {
1677                 yaffs_CalcECC(buffer,&spare);
1678         }
1679
1680         yaffs_LoadTagsIntoSpare(&spare,tags);
1681
1682         return yaffs_WriteNewChunkToNAND(dev,buffer,&spare,useReserve);
1683
1684 }
1685
1686
1687
1688
1689 int yaffs_FindChunkInFile(yaffs_Object *in,int chunkInInode,yaffs_Tags *tags)
1690 {
1691         //Get the Tnode, then get the level 0 offset chunk offset
1692     yaffs_Tnode *tn;
1693     int theChunk = -1;
1694     yaffs_Tags localTags;
1695     int i;
1696     int found = 0;
1697     yaffs_Device *dev = in->myDev;
1698
1699
1700     if(!tags)
1701     {
1702         // Passed a NULL, so use our own tags space
1703         tags = &localTags;
1704     }
1705
1706     tn = yaffs_FindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
1707
1708     if(tn)
1709     {
1710                 theChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] << dev->chunkGroupBits;
1711
1712                 // Now we need to do the shifting etc and search for it
1713                 for(i = 0,found = 0; theChunk && i < dev->chunkGroupSize && !found; i++)
1714                 {
1715                         yaffs_ReadChunkTagsFromNAND(dev,theChunk,tags);
1716                         if(tags->chunkId == chunkInInode &&
1717                         tags->objectId == in->objectId)
1718                         {
1719                                 // found it;
1720                                 found = 1;
1721                         }
1722                         else
1723                         {
1724                                 theChunk++;
1725                         }
1726                 }
1727     }
1728     return found ? theChunk : -1;
1729 }
1730
1731 int yaffs_FindAndDeleteChunkInFile(yaffs_Object *in,int chunkInInode,yaffs_Tags *tags)
1732 {
1733         //Get the Tnode, then get the level 0 offset chunk offset
1734     yaffs_Tnode *tn;
1735     int theChunk = -1;
1736     yaffs_Tags localTags;
1737     int i;
1738     int found = 0;
1739     yaffs_Device *dev = in->myDev;
1740
1741     if(!tags)
1742     {
1743         // Passed a NULL, so use our own tags space
1744         tags = &localTags;
1745     }
1746
1747     tn = yaffs_FindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
1748
1749     if(tn)
1750     {
1751
1752                 theChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] << dev->chunkGroupBits;
1753
1754                 // Now we need to do the shifting etc and search for it
1755                 for(i = 0,found = 0; theChunk && i < dev->chunkGroupSize && !found; i++)
1756                 {
1757                         yaffs_ReadChunkTagsFromNAND(dev,theChunk,tags);
1758                         if(tags->chunkId == chunkInInode &&
1759                         tags->objectId == in->objectId)
1760                         {
1761                                 // found it;
1762                                 found = 1;
1763                         }
1764                         else
1765                         {
1766                                 theChunk++;
1767                         }
1768                 }
1769
1770                 // Delete the entry in the filestructure
1771                 if(found)
1772                 {
1773                         tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] = 0;
1774                 }
1775     }
1776     else
1777     {
1778         T(("No level 0 found for %d\n", chunkInInode));
1779     }
1780
1781     if(!found)
1782     {
1783         T(("Could not find %d to delete\n",chunkInInode));
1784     }
1785     return found ? theChunk : -1;
1786 }
1787
1788
1789 #if YAFFS_PARANOID
1790
1791 static int yaffs_CheckFileSanity(yaffs_Object *in)
1792 {
1793         int chunk;
1794         int nChunks;
1795         int fSize;
1796         int failed = 0;
1797         int objId;
1798         yaffs_Tnode *tn;
1799     yaffs_Tags localTags;
1800     yaffs_Tags *tags = &localTags;
1801     int theChunk;
1802
1803
1804         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
1805         {
1806                 T(("Object not a file\n"));
1807                 return YAFFS_FAIL;
1808         }
1809
1810         objId = in->objectId;
1811         fSize  = in->variant.fileVariant.fileSize;
1812         nChunks = (fSize + YAFFS_BYTES_PER_CHUNK -1)/YAFFS_BYTES_PER_CHUNK;
1813
1814         for(chunk = 1; chunk <= nChunks; chunk++)
1815         {
1816                 tn = yaffs_FindLevel0Tnode(in->myDev,&in->variant.fileVariant, chunk);
1817
1818                 if(tn)
1819                 {
1820
1821                         theChunk = tn->level0[chunk & YAFFS_TNODES_LEVEL0_MASK] << in->myDev->chunkGroupBits;
1822
1823
1824                                 yaffs_ReadChunkTagsFromNAND(in->myDev,theChunk,tags);
1825                                 if(tags->chunkId == chunk &&
1826                                 tags->objectId == in->objectId)
1827                                 {
1828                                         // found it;
1829
1830                                 }
1831                                 else
1832                                 {
1833                                         //T(("File problem file [%d,%d] NAND %d  tags[%d,%d]\n",
1834                                         //              objId,chunk,theChunk,tags->chunkId,tags->objectId);
1835
1836                                         failed = 1;
1837
1838                                 }
1839
1840                 }
1841                 else
1842                 {
1843                         T(("No level 0 found for %d\n", chunk));
1844                 }
1845         }
1846
1847         return failed ? YAFFS_FAIL : YAFFS_OK;
1848 }
1849
1850 #endif
1851
1852 static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan)
1853 {
1854         yaffs_Tnode *tn;
1855         yaffs_Device *dev = in->myDev;
1856         int existingChunk;
1857         yaffs_Tags existingTags;
1858         yaffs_Tags newTags;
1859         unsigned existingSerial, newSerial;
1860
1861
1862         tn = yaffs_AddOrFindLevel0Tnode(dev,&in->variant.fileVariant, chunkInInode);
1863
1864         if(inScan)
1865         {
1866                 // If we're scanning then we need to test for duplicates
1867                 // NB This does not need to be efficient since it should only ever
1868                 // happen when the power fails during a write, then only one
1869                 // chunk should ever be affected.
1870
1871                 existingChunk = tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK];
1872
1873                 if(existingChunk != 0)
1874                 {
1875                         // We have a duplicate now we need to decide which one to use
1876                         // To do this we get both sets of tags and compare serial numbers.
1877                         yaffs_ReadChunkTagsFromNAND(dev,chunkInInode, &newTags);
1878                         yaffs_ReadChunkTagsFromNAND(dev,existingChunk, &existingTags);
1879                         newSerial = newTags.serialNumber;
1880                         existingSerial = existingTags.serialNumber;
1881                         if(((existingSerial+1) & 3) == newSerial)
1882                         {
1883                                 // Use new
1884                                 // Delete the old one and drop through to update the tnode
1885                                 yaffs_DeleteChunk(dev,existingChunk);
1886                         }
1887                         else
1888                         {
1889                                 // Use existing.
1890                                 // Delete the new one and return early so that the tnode isn't changed
1891                                 yaffs_DeleteChunk(dev,chunkInInode);
1892                                 return YAFFS_OK;
1893                         }
1894                 }
1895         }
1896
1897         tn->level0[chunkInInode & YAFFS_TNODES_LEVEL0_MASK] = chunkInNAND;
1898
1899         return YAFFS_OK;
1900 }
1901
1902
1903
1904 int yaffs_ReadChunkDataFromObject(yaffs_Object *in,int chunkInInode, __u8 *buffer)
1905 {
1906     int chunkInNAND = yaffs_FindChunkInFile(in,chunkInInode,NULL);
1907
1908     if(chunkInNAND >= 0)
1909     {
1910                 return yaffs_ReadChunkFromNAND(in->myDev,chunkInNAND,buffer,NULL);
1911         }
1912         else
1913         {
1914                 return 0;
1915         }
1916
1917 }
1918
1919
1920 static void yaffs_DeleteChunk(yaffs_Device *dev,int chunkId)
1921 {
1922         int block = chunkId / YAFFS_CHUNKS_PER_BLOCK;
1923         int page = chunkId % YAFFS_CHUNKS_PER_BLOCK;
1924         yaffs_Tags tags;
1925
1926         // Mark the deleted NAND page as deleted
1927         tags.chunkId = 0;
1928         tags.objectId = 0;
1929         tags.byteCount = 0;
1930         tags.ecc = 0;
1931
1932         yaffs_WriteChunkWithTagsToNAND(dev,chunkId,NULL,&tags);
1933
1934
1935         // Pull out of the management area.
1936         if(     dev->blockInfo[block].blockState == YAFFS_BLOCK_STATE_ALLOCATING ||
1937             dev->blockInfo[block].blockState == YAFFS_BLOCK_STATE_FULL)
1938         {
1939                 dev->nFreeChunks++;
1940
1941                 dev->blockInfo[block].pageBits &= ~(1 << page);
1942                 dev->blockInfo[block].pagesInUse--;
1943
1944                 if(     dev->blockInfo[block].pagesInUse == 0 &&
1945             dev->blockInfo[block].blockState == YAFFS_BLOCK_STATE_FULL)
1946             {
1947                 yaffs_BlockBecameDirty(dev,block);
1948             }
1949
1950         }
1951         else
1952         {
1953                 T(("Bad news deleting chunk %d\n",chunkId));
1954         }
1955
1956 }
1957
1958
1959
1960
1961 int yaffs_WriteChunkDataToObject(yaffs_Object *in,int chunkInInode, const __u8 *buffer,int nBytes,int useReserve)
1962 {
1963         // Find old chunk Need to do this to get serial number
1964         // Write new one and patch into tree.
1965         // Invalidate old tags.
1966
1967     int prevChunkId;
1968     yaffs_Tags prevTags;
1969
1970     int newChunkId;
1971     yaffs_Tags newTags;
1972
1973     yaffs_Device *dev = in->myDev;
1974
1975         yaffs_CheckGarbageCollection(dev);
1976
1977         // Get the previous chunk at this location in the file if it exists
1978     prevChunkId  = yaffs_FindChunkInFile(in,chunkInInode,&prevTags);
1979
1980     // Set up new tags
1981         newTags.chunkId = chunkInInode;
1982         newTags.objectId = in->objectId;
1983         newTags.serialNumber = (prevChunkId >= 0) ? prevTags.serialNumber + 1 : 1;
1984         newTags.byteCount = nBytes;
1985         newTags.unusedStuff = 0xFFFFFFFF;
1986
1987         yaffs_CalcTagsECC(&newTags);
1988
1989
1990  #if 0
1991     // Create new chunk in NAND
1992     newChunkId = yaffs_AllocatePage(dev,useReserve);
1993
1994
1995     if(newChunkId >= 0)
1996     {
1997
1998
1999                 yaffs_WriteChunkWithTagsToNAND(dev,newChunkId,buffer,&newTags);
2000
2001                 yaffs_PutChunkIntoFile(in,chunkInInode,newChunkId);
2002
2003
2004                 if(prevChunkId >= 0)
2005                 {
2006                         yaffs_DeleteChunk(dev,prevChunkId);
2007
2008                 }
2009
2010                 yaffs_CheckFileSanity(in);
2011
2012                 return newChunkId;
2013     }
2014
2015
2016     return -1;
2017 #else
2018
2019         newChunkId = yaffs_WriteNewChunkWithTagsToNAND(dev,buffer,&newTags,useReserve);
2020         if(newChunkId >= 0)
2021         {
2022                 yaffs_PutChunkIntoFile(in,chunkInInode,newChunkId,0);
2023
2024
2025                 if(prevChunkId >= 0)
2026                 {
2027                         yaffs_DeleteChunk(dev,prevChunkId);
2028
2029                 }
2030
2031                 yaffs_CheckFileSanity(in);
2032         }
2033         return newChunkId;
2034
2035 #endif
2036
2037
2038
2039 }
2040
2041
2042 // UpdateObjectHeader updates the header on NAND for an object.
2043 // If name is not NULL, then that new name is used.
2044 //
2045 int yaffs_UpdateObjectHeader(yaffs_Object *in,const char *name)
2046 {
2047
2048         yaffs_Device *dev = in->myDev;
2049
2050     int prevChunkId;
2051
2052     int newChunkId;
2053     yaffs_Tags newTags;
2054     __u8 bufferNew[YAFFS_BYTES_PER_CHUNK];
2055     __u8 bufferOld[YAFFS_BYTES_PER_CHUNK];
2056
2057     yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)bufferNew;
2058     yaffs_ObjectHeader *ohOld = (yaffs_ObjectHeader *)bufferOld;
2059
2060     if(!in->fake)
2061     {
2062
2063                 yaffs_CheckGarbageCollection(dev);
2064
2065                 memset(bufferNew,0xFF,YAFFS_BYTES_PER_CHUNK);
2066
2067                 prevChunkId = in->chunkId;
2068
2069                 if(prevChunkId >= 0)
2070                 {
2071                         yaffs_ReadChunkFromNAND(dev,prevChunkId,bufferOld,NULL);
2072                 }
2073
2074                 // Header data
2075                 oh->type = in->variantType;
2076
2077                 oh->st_mode = in->st_mode;
2078                 oh->st_uid = in->st_uid;
2079                 oh->st_gid = in->st_gid;
2080                 oh->st_atime = in->st_atime;
2081                 oh->st_mtime = in->st_mtime;
2082                 oh->st_ctime = in->st_ctime;
2083
2084                 oh->parentObjectId = in->parent->objectId;
2085                 oh->sum = in->sum;
2086                 if(name && *name)
2087                 {
2088                         memset(oh->name,0,YAFFS_MAX_NAME_LENGTH + 1);
2089                         strncpy(oh->name,name,YAFFS_MAX_NAME_LENGTH);
2090                 }
2091                 else
2092                 {
2093                         memcpy(oh->name, ohOld->name,YAFFS_MAX_NAME_LENGTH + 1);
2094                 }
2095
2096                 switch(in->variantType)
2097                 {
2098                         case YAFFS_OBJECT_TYPE_UNKNOWN:
2099                                 // Should not happen
2100                                 break;
2101                         case YAFFS_OBJECT_TYPE_FILE:
2102                                 oh->fileSize = in->variant.fileVariant.fileSize;
2103                                 break;
2104                         case YAFFS_OBJECT_TYPE_HARDLINK:
2105                                 oh->equivalentObjectId = in->variant.hardLinkVariant.equivalentObjectId;
2106                                 break;
2107                         case YAFFS_OBJECT_TYPE_DIRECTORY:
2108                                 // Do nothing
2109                                 break;
2110                         case YAFFS_OBJECT_TYPE_SYMLINK:
2111                                 strncpy(oh->alias,in->variant.symLinkVariant.alias,YAFFS_MAX_ALIAS_LENGTH);
2112                                 oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
2113                                 break;
2114                 }
2115
2116                 // Tags
2117                 in->serial++;
2118                 newTags.chunkId = 0;
2119                 newTags.objectId = in->objectId;
2120                 newTags.serialNumber = in->serial;
2121                 newTags.byteCount =   0xFFFFFFFF;
2122                 newTags.unusedStuff = 0xFFFFFFFF;
2123
2124                 yaffs_CalcTagsECC(&newTags);
2125
2126
2127
2128 #if 0
2129                 // Create new chunk in NAND
2130                 newChunkId = yaffs_AllocatePage(dev,1);
2131
2132                 if(newChunkId >= 0)
2133                 {
2134
2135                         yaffs_WriteChunkWithTagsToNAND(dev,newChunkId,bufferNew,&newTags);
2136
2137                         in->chunkId = newChunkId;
2138
2139                         if(prevChunkId >= 0)
2140                         {
2141                                 yaffs_DeleteChunk(dev,prevChunkId);
2142                         }
2143
2144                         in->dirty = 0;
2145                         return newChunkId;
2146                 }
2147
2148                 return -1;
2149 #else
2150                 // Create new chunk in NAND
2151                 newChunkId = yaffs_WriteNewChunkWithTagsToNAND(dev,bufferNew,&newTags,1);
2152
2153                 if(newChunkId >= 0)
2154                 {
2155
2156                         in->chunkId = newChunkId;
2157
2158                         if(prevChunkId >= 0)
2159                         {
2160                                 yaffs_DeleteChunk(dev,prevChunkId);
2161                         }
2162
2163                         in->dirty = 0;
2164                 }
2165
2166                 return newChunkId;
2167
2168 #endif
2169     }
2170     return 0;
2171 }
2172
2173
2174
2175 ///////////////////////// File read/write ///////////////////////////////
2176 // Read and write have very similar structures.
2177 // In general the read/write has three parts to it
2178 // * An incomplete chunk to start with (if the read/write is not chunk-aligned)
2179 // * Some complete chunks
2180 // * An incomplete chunk to end off with
2181 //
2182 // Curve-balls: the first chunk might also be the last chunk.
2183
2184 int yaffs_ReadDataFromFile(yaffs_Object *in, __u8 * buffer, __u32 offset, int nBytes)
2185 {
2186
2187 //      yaffs_Device *dev = in->myDev;
2188
2189         __u8 localBuffer[YAFFS_BYTES_PER_CHUNK];
2190
2191         int chunk;
2192         int start;
2193         int nToCopy;
2194         int n = nBytes;
2195         int nDone = 0;
2196
2197         while(n > 0)
2198         {
2199                 chunk = offset / YAFFS_BYTES_PER_CHUNK + 1; // The first chunk is 1
2200                 start = offset % YAFFS_BYTES_PER_CHUNK;
2201
2202                 // OK now check for the curveball where the start and end are in
2203                 // the same chunk.
2204                 if(     (start + n) < YAFFS_BYTES_PER_CHUNK)
2205                 {
2206                         nToCopy = n;
2207                 }
2208                 else
2209                 {
2210                         nToCopy = YAFFS_BYTES_PER_CHUNK - start;
2211                 }
2212
2213                 if(nToCopy != YAFFS_BYTES_PER_CHUNK)
2214                 {
2215                         // An incomplete start or end chunk (or maybe both start and end chunk)
2216                         // Read into the local buffer then copy...
2217
2218                         yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
2219                         memcpy(buffer,&localBuffer[start],nToCopy);
2220                 }
2221                 else
2222                 {
2223                         // A full chunk. Read directly into the supplied buffer.
2224                         yaffs_ReadChunkDataFromObject(in,chunk,buffer);
2225                 }
2226
2227                 n -= nToCopy;
2228                 offset += nToCopy;
2229                 buffer += nToCopy;
2230                 nDone += nToCopy;
2231
2232         }
2233
2234         return nDone;
2235 }
2236
2237
2238 int yaffs_WriteDataToFile(yaffs_Object *in,const __u8 * buffer, __u32 offset, int nBytes)
2239 {
2240         __u8 localBuffer[YAFFS_BYTES_PER_CHUNK];
2241
2242         int chunk;
2243         int start;
2244         int nToCopy;
2245         int n = nBytes;
2246         int nDone = 0;
2247         int nToWriteBack;
2248         int endOfWrite = offset+nBytes;
2249         int chunkWritten = 0;
2250
2251         while(n > 0 && chunkWritten >= 0)
2252         {
2253                 chunk = offset / YAFFS_BYTES_PER_CHUNK + 1;
2254                 start = offset % YAFFS_BYTES_PER_CHUNK;
2255
2256
2257                 // OK now check for the curveball where the start and end are in
2258                 // the same chunk.
2259                 if(     (start + n) < YAFFS_BYTES_PER_CHUNK)
2260                 {
2261                         nToCopy = n;
2262                         nToWriteBack = (start + n);
2263                 }
2264                 else
2265                 {
2266                         nToCopy = YAFFS_BYTES_PER_CHUNK - start;
2267                         nToWriteBack = YAFFS_BYTES_PER_CHUNK;
2268                 }
2269
2270                 if(nToCopy != YAFFS_BYTES_PER_CHUNK)
2271                 {
2272                         // An incomplete start or end chunk (or maybe both start and end chunk)
2273                         // Read into the local buffer then copy, then copy over and write back.
2274
2275                         yaffs_ReadChunkDataFromObject(in,chunk,localBuffer);
2276
2277                         memcpy(&localBuffer[start],buffer,nToCopy);
2278
2279                         chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,localBuffer,nToWriteBack,0);
2280
2281                         T(("Write with readback to chunk %d %d\n",chunk,chunkWritten));
2282
2283                 }
2284                 else
2285                 {
2286                         // A full chunk. Write directly from the supplied buffer.
2287                         chunkWritten = yaffs_WriteChunkDataToObject(in,chunk,buffer,YAFFS_BYTES_PER_CHUNK,0);
2288                         T(("Write to chunk %d %d\n",chunk,chunkWritten));
2289                 }
2290
2291                 if(chunkWritten >= 0)
2292                 {
2293                         n -= nToCopy;
2294                         offset += nToCopy;
2295                         buffer += nToCopy;
2296                         nDone += nToCopy;
2297                 }
2298
2299         }
2300
2301         // Update file object
2302
2303         if(endOfWrite > in->variant.fileVariant.fileSize)
2304         {
2305                 in->variant.fileVariant.fileSize = endOfWrite;
2306         }
2307
2308         in->dirty = 1;
2309         in->st_mtime = CURRENT_TIME;
2310
2311         return nDone;
2312 }
2313
2314
2315 int yaffs_ResizeFile(yaffs_Object *in, int newSize)
2316 {
2317         int i;
2318         int chunkId;
2319         int oldFileSize = in->variant.fileVariant.fileSize;
2320         int sizeOfLastChunk = newSize % YAFFS_BYTES_PER_CHUNK;
2321
2322         yaffs_Device *dev = in->myDev;
2323
2324         __u8 localBuffer[YAFFS_BYTES_PER_CHUNK];
2325
2326         if(in->variantType != YAFFS_OBJECT_TYPE_FILE)
2327         {
2328                 return yaffs_GetFileSize(in);
2329         }
2330
2331         if(newSize < oldFileSize)
2332         {
2333
2334                 int lastDel = 1 + oldFileSize/YAFFS_BYTES_PER_CHUNK;
2335
2336                 int startDel = 1 + (newSize + YAFFS_BYTES_PER_CHUNK - 1)/
2337                                                         YAFFS_BYTES_PER_CHUNK;
2338
2339                 for(i = startDel; i <= lastDel; i++)
2340                 {
2341                         // NB this could be optimised somewhat,
2342                         // eg. could retrieve the tags and write them without
2343                         // using yaffs_DeleteChunk
2344                         chunkId = yaffs_FindAndDeleteChunkInFile(in,i,NULL);
2345                         if(chunkId < 0 || chunkId >= (dev->endBlock * 32))
2346                         {
2347                                 T(("Found daft chunkId %d for %d\n",chunkId,i));
2348                         }
2349                         else
2350                         {
2351                                 yaffs_DeleteChunk(dev,chunkId);
2352                         }
2353                 }
2354
2355
2356                 if(sizeOfLastChunk != 0)
2357                 {
2358                         int lastChunk = 1+ newSize/YAFFS_BYTES_PER_CHUNK;
2359
2360                         // Got to read and rewrite the last chunk with its new size.
2361                         yaffs_ReadChunkDataFromObject(in,lastChunk,localBuffer);
2362
2363                         yaffs_WriteChunkDataToObject(in,lastChunk,localBuffer,sizeOfLastChunk,1);
2364
2365                 }
2366
2367                 in->variant.fileVariant.fileSize = newSize;
2368
2369                 yaffs_PruneFileStructure(dev,&in->variant.fileVariant);
2370
2371                 return newSize;
2372
2373         }
2374         else
2375         {
2376                 return oldFileSize;
2377         }
2378 }
2379
2380
2381 loff_t yaffs_GetFileSize(yaffs_Object *obj)
2382 {
2383         obj = yaffs_GetEquivalentObject(obj);
2384
2385         switch(obj->variantType)
2386         {
2387                 case YAFFS_OBJECT_TYPE_FILE:
2388                         return obj->variant.fileVariant.fileSize;
2389                 case YAFFS_OBJECT_TYPE_SYMLINK:
2390                         return strlen(obj->variant.symLinkVariant.alias);
2391                 default:
2392                         return 0;
2393         }
2394 }
2395
2396
2397
2398 // yaffs_FlushFile() updates the file's
2399 // objectId in NAND
2400
2401 int yaffs_FlushFile(yaffs_Object *in)
2402 {
2403         int retVal;
2404         if(in->dirty)
2405         {
2406                 T(("flushing object header\n"));
2407                 retVal = yaffs_UpdateObjectHeader(in,NULL);
2408         }
2409         else
2410         {
2411                 retVal = YAFFS_OK;
2412         }
2413
2414         return retVal;
2415
2416 }
2417
2418
2419 static int yaffs_DoGenericObjectDeletion(yaffs_Object *in)
2420 {
2421         yaffs_RemoveObjectFromDirectory(in);
2422         yaffs_DeleteChunk(in->myDev,in->chunkId);
2423         yaffs_FreeObject(in);
2424         return YAFFS_OK;
2425
2426 }
2427
2428 // yaffs_DeleteFile deletes the whole file data
2429 // and the inode associated with the file.
2430 // It does not delete the links associated with the file.
2431 static int yaffs_DeleteFile(yaffs_Object *in)
2432 {
2433         // Delete the file data & tnodes
2434         yaffs_ResizeFile(in,0);
2435         yaffs_FreeTnode(in->myDev,in->variant.fileVariant.top);
2436
2437         return  yaffs_DoGenericObjectDeletion(in);
2438 }
2439
2440 static int yaffs_DeleteDirectory(yaffs_Object *in)
2441 {
2442         //First check that the directory is empty.
2443         if(list_empty(&in->variant.directoryVariant.children))
2444         {
2445                 return  yaffs_DoGenericObjectDeletion(in);
2446         }
2447
2448         return YAFFS_FAIL;
2449
2450 }
2451
2452 static int yaffs_DeleteSymLink(yaffs_Object *in)
2453 {
2454         YFREE(in->variant.symLinkVariant.alias);
2455
2456         return  yaffs_DoGenericObjectDeletion(in);
2457 }
2458
2459 static int yaffs_DeleteHardLink(yaffs_Object *in)
2460 {
2461         // remove this hardlink from the list assocaited with the equivalent
2462         // object
2463         list_del(&in->hardLinks);
2464         return  yaffs_DoGenericObjectDeletion(in);
2465 }
2466
2467
2468 static int yaffs_UnlinkWorker(yaffs_Object *obj)
2469 {
2470
2471
2472         if(obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
2473         {
2474                 return  yaffs_DeleteHardLink(obj);
2475         }
2476         else if(!list_empty(&obj->hardLinks))
2477         {
2478 #if 0
2479                 // Curve ball: We're unlinking an object that has a hardlink.
2480                 // Therefore we can't really delete the object.
2481                 // Instead, we do the following:
2482                 // - Select a hardlink.
2483                 // - Re-type a hardlink as the equivalent object and populate the fields, including the
2484                 //  objectId. Updating the object id is important so that all the hardlinks do not need
2485                 // to be rewritten.
2486                 // - Update the equivalet object pointers.
2487                 // - Delete all object.
2488
2489                 yaffs_Object *hl;
2490                 struct list_head *i;
2491
2492
2493                 yaffs_RemoveObjectFromDirectory(obj);
2494
2495
2496
2497                 hl =  list_entry(obj->hardLinks.next, yaffs_Object,hardLinks);
2498
2499                 hl->dirty = 1;
2500                 hl->st_mode = obj->st_mode;
2501                 hl->st_uid = obj->st_uid;
2502                 hl->st_gid = obj->st_gid;
2503                 hl->st_atime = obj->st_atime;
2504                 hl->st_mtime = obj->st_mtime;
2505                 hl->st_ctime = obj->st_ctime;
2506
2507                 hl->variantType = obj->variantType;
2508
2509                 switch(hl->variantType)
2510                 {
2511                         case YAFFS_OBJECT_TYPE_FILE:
2512                         case YAFFS_OBJECT_TYPE_SYMLINK:
2513                                 // These types are OK to just copy across.
2514                                 hl->variant = obj->variant;
2515                                 break;
2516                         case YAFFS_OBJECT_TYPE_DIRECTORY:
2517                                 // Fix the list up
2518                                 list_add(&hl->variant.directoryVariant.children,
2519                                             &obj->variant.directoryVariant.children);
2520                                 list_del(&obj->variant.directoryVariant.children);
2521
2522                                 // Now change all the directory children to point to the new parent.
2523                                 list_for_each(i,&hl->variant.directoryVariant.children)
2524                                 {
2525                                         list_entry(i,yaffs_Object,siblings)->parent = hl;
2526                                 }
2527                                 break;
2528
2529                         case YAFFS_OBJECT_TYPE_HARDLINK:
2530                         case YAFFS_OBJECT_TYPE_UNKNOWN:
2531                                 // Should not be either of these types.
2532                 }
2533
2534                 // Now fix up the hardlink chain
2535                 list_del(&obj->hardLinks);
2536
2537                 list_for_each(i,&hl->hardLinks)
2538                 {
2539                         list_entry(i,yaffs_Object,hardLinks)->variant.hardLinkVariant.equivalentObject = hl;
2540                         list_entry(i,yaffs_Object,hardLinks)->variant.hardLinkVariant.equivalentObjectId = hl->objectId;
2541                 }
2542
2543                 // Now fix up the hash links.
2544                 yaffs_UnhashObject(hl);
2545                 hl->objectId = obj->objectId;
2546                 yaffs_HashObject(hl);
2547
2548                 // Update the hardlink which has become an object
2549                 yaffs_UpdateObjectHeader(hl,NULL);
2550
2551                 // Finally throw away the deleted object
2552                 yaffs_DeleteChunk(obj->myDev,obj->chunkId);
2553                 yaffs_FreeObject(obj);
2554
2555                 return YAFFS_OK;
2556 #else
2557                 // Curve ball: We're unlinking an object that has a hardlink.
2558                 //
2559                 //      This problem arises because we are not strictly following
2560                 //  The Linux link/inode model.
2561                 //
2562                 // We can't really delete the object.
2563                 // Instead, we do the following:
2564                 // - Select a hardlink.
2565                 // - Unhook it from the hard links
2566                 // - Unhook it from its parent directory (so that the rename can work)
2567                 // - Rename the object to the hardlink's name.
2568                 // - Delete the hardlink
2569
2570
2571                 yaffs_Object *hl;
2572                 int retVal;
2573                 char name[YAFFS_MAX_NAME_LENGTH+1];
2574
2575                 hl = list_entry(obj->hardLinks.next,yaffs_Object,hardLinks);
2576                 list_del_init(&hl->hardLinks);
2577                 list_del_init(&hl->siblings);
2578
2579                 yaffs_GetObjectName(hl,name,YAFFS_MAX_NAME_LENGTH+1);
2580
2581                 retVal = yaffs_ChangeObjectName(obj, hl->parent, name);
2582                 if(retVal == YAFFS_OK)
2583                 {
2584                         retVal = yaffs_DoGenericObjectDeletion(hl);
2585                 }
2586                 return retVal;
2587
2588 #endif
2589
2590
2591         }
2592         else
2593         {
2594                 switch(obj->variantType)
2595                 {
2596                         case YAFFS_OBJECT_TYPE_FILE:
2597                                 return yaffs_DeleteFile(obj);
2598                                 break;
2599                         case YAFFS_OBJECT_TYPE_DIRECTORY:
2600                                 return yaffs_DeleteDirectory(obj);
2601                                 break;
2602                         case YAFFS_OBJECT_TYPE_SYMLINK:
2603                                 return yaffs_DeleteSymLink(obj);
2604                                 break;
2605                         case YAFFS_OBJECT_TYPE_HARDLINK:
2606                         case YAFFS_OBJECT_TYPE_UNKNOWN:
2607                         default:
2608                                 return YAFFS_FAIL;
2609                 }
2610         }
2611 }
2612
2613 int yaffs_Unlink(yaffs_Object *dir, const char *name)
2614 {
2615         yaffs_Object *obj;
2616
2617          obj = yaffs_FindObjectByName(dir,name);
2618
2619          if(obj && obj->unlinkAllowed)
2620          {
2621                 return yaffs_UnlinkWorker(obj);
2622          }
2623
2624          return YAFFS_FAIL;
2625
2626 }
2627
2628 //////////////// Initialisation Scanning /////////////////
2629
2630
2631 static int yaffs_Scan(yaffs_Device *dev)
2632 {
2633         yaffs_Spare spare;
2634         yaffs_Tags tags;
2635         int blk;
2636         int chunk;
2637         int c;
2638         int deleted;
2639         int inuse;
2640         yaffs_BlockState state;
2641         yaffs_Object *hardList = NULL;
2642         yaffs_Object *hl;
2643
2644         __u32 pageBits;
2645
2646         yaffs_ObjectHeader *oh;
2647         yaffs_Object *in;
2648         yaffs_Object *parent;
2649
2650         __u8 chunkData[YAFFS_BYTES_PER_CHUNK];
2651
2652         for(blk = dev->startBlock; blk <= dev->endBlock; blk++)
2653         {
2654                 deleted = 0;
2655                 pageBits = 0;
2656                 inuse = 0;
2657                 state = YAFFS_BLOCK_STATE_UNKNOWN;
2658
2659                 for(c = 0; c < YAFFS_CHUNKS_PER_BLOCK &&
2660                                    state == YAFFS_BLOCK_STATE_UNKNOWN; c++)
2661                 {
2662                         // Read the spare area and decide what to do
2663                         chunk = blk * YAFFS_CHUNKS_PER_BLOCK + c;
2664                         yaffs_ReadChunkFromNAND(dev,chunk,NULL,&spare);
2665
2666
2667                         // Is this a valid block?
2668                         if(yaffs_countBits[spare.blockStatus] >= 7)
2669                         {
2670                                 // This block looks ok, now what's in this chunk?
2671                                 yaffs_GetTagsFromSpare(&spare,&tags);
2672
2673                                 if(tags.objectId == YAFFS_UNUSED_OBJECT_ID)
2674                                 {
2675                                         // An unassigned chunk in the block
2676                                         // This means that either the block is empty or
2677                                         // this is the one being allocated from
2678
2679                                         if(c == 0)
2680                                         {
2681                                                 // the block is unused
2682                                                 state = YAFFS_BLOCK_STATE_EMPTY;
2683                                                 dev->nErasedBlocks++;
2684                                         }
2685                                         else
2686                                         {
2687                                                 // this is the block being allocated from
2688                                                 T((" allocating %d %d\n",blk,c));
2689                                                 state = YAFFS_BLOCK_STATE_ALLOCATING;
2690                                                 dev->allocationBlock = blk;
2691                                                 dev->allocationPage = c;
2692                                         }
2693
2694                                         dev->nFreeChunks += (YAFFS_CHUNKS_PER_BLOCK - c);
2695                                 }
2696                                 else if(tags.objectId == 0)
2697                                 {
2698                                         // A deleted chunk
2699                                         deleted++;
2700                                         dev->nFreeChunks ++;
2701                                         T((" %d %d deleted\n",blk,c));
2702                                 }
2703                                 else if(tags.chunkId > 0)
2704                                 {
2705                                         // A data chunk.
2706                                         inuse++;
2707                                         pageBits |= ( 1 <<c);
2708                                         in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,YAFFS_OBJECT_TYPE_FILE);
2709                                         // PutChuunkIntoFIle checks for a clash (two data chunks with
2710                                         // the same chunkId).
2711                                         yaffs_PutChunkIntoFile(in,tags.chunkId,chunk,1);
2712                                         T((" %d %d data %d %d\n",blk,c,tags.objectId,tags.chunkId));
2713                                 }
2714                                 else
2715                                 {
2716                                         // chunkId == 0, so it is an ObjectHeader.
2717                                         inuse++;
2718                                         pageBits |= ( 1 <<c);
2719                                         yaffs_ReadChunkFromNAND(dev,chunk,chunkData,NULL);
2720                                         oh = (yaffs_ObjectHeader *)chunkData;
2721
2722                                         in = yaffs_FindOrCreateObjectByNumber(dev,tags.objectId,oh->type);
2723                                         if(in->valid)
2724                                         {
2725                                                 // todo we have already filled this one. We have
2726                                                 // a duplicate. Need to fix
2727                                         }
2728
2729                                         // we don't have a duplicate...
2730
2731                                         in->valid = 1;
2732                                         in->variantType = oh->type;
2733
2734                                         in->st_mode  = oh->st_mode;
2735                                         in->st_uid   = oh->st_uid;
2736                                         in->st_gid   = oh->st_gid;
2737                                         in->st_atime = oh->st_atime;
2738                                         in->st_mtime = oh->st_mtime;
2739                                         in->st_ctime = oh->st_ctime;
2740                                         in->chunkId  = chunk;
2741
2742                                         in->sum = oh->sum;
2743                                         in->dirty = 0;
2744
2745                                         // directory stuff...
2746                                         // hook up to parent
2747
2748                                         parent = yaffs_FindOrCreateObjectByNumber(dev,oh->parentObjectId,YAFFS_OBJECT_TYPE_DIRECTORY);
2749                                         if(parent->variantType == YAFFS_OBJECT_TYPE_UNKNOWN)
2750                                         {
2751                                                 // Set up as a directory
2752                                                 parent->variantType = YAFFS_OBJECT_TYPE_DIRECTORY;
2753                                                 INIT_LIST_HEAD(&parent->variant.directoryVariant.children);
2754                                         }
2755                                         else if(parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
2756                                         {
2757                                                 // Hoosterman, another problem....
2758                                                 // We're trying to use a non-directory as a directory
2759                                                 // Todo ... handle
2760                                         }
2761
2762                                         yaffs_AddObjectToDirectory(parent,in);
2763
2764                                         // Note re hardlinks.
2765                                         // Since we might scan a hardlink before its equivalent object is scanned
2766                                         // we put them all in a list.
2767                                         // After scanning is complete, we should have all the objects, so we run through this
2768                                         // list and fix up all the chains.
2769
2770                                         switch(in->variantType)
2771                                         {
2772                                                 case YAFFS_OBJECT_TYPE_UNKNOWN:         // Todo got a problem
2773                                                         break;
2774                                                 case YAFFS_OBJECT_TYPE_FILE:
2775                                                         in->variant.fileVariant.fileSize = oh->fileSize;
2776                                                         break;
2777                                                 case YAFFS_OBJECT_TYPE_HARDLINK:
2778                                                         in->variant.hardLinkVariant.equivalentObjectId = oh->equivalentObjectId;
2779                                                         (yaffs_Object *)(in->hardLinks.next) = hardList;
2780                                                         hardList = in;
2781                                                         break;
2782                                                 case YAFFS_OBJECT_TYPE_DIRECTORY:       // Do nothing
2783                                                         break;
2784                                                 case YAFFS_OBJECT_TYPE_SYMLINK:         // Do nothing
2785                                                         in->variant.symLinkVariant.alias = yaffs_CloneString(oh->alias);
2786                                                         break;
2787                                         }
2788                                         T((" %d %d header %d \"%s\" type %d\n",blk,c,tags.objectId,oh->name,in->variantType));
2789                                 }
2790                         }
2791                         else
2792                         {
2793                                 // it's a bad block
2794                                 state = YAFFS_BLOCK_STATE_DEAD;
2795                         }
2796                 }
2797
2798                 if(state == YAFFS_BLOCK_STATE_UNKNOWN)
2799                 {
2800                         // If we got this far, then the block is fully allocated.
2801                         // ie. Full or Dirty
2802                         state = (inuse) ? YAFFS_BLOCK_STATE_FULL : YAFFS_BLOCK_STATE_DIRTY;
2803
2804                 }
2805
2806                 dev->blockInfo[blk].pageBits = pageBits;
2807                 dev->blockInfo[blk].pagesInUse = inuse;
2808                 dev->blockInfo[blk].blockState = state;
2809
2810         }
2811
2812         // Todo fix up the hard link chains
2813         while(hardList)
2814         {
2815                 hl = hardList;
2816                 hardList = (yaffs_Object *)(hardList->hardLinks.next);
2817
2818                 in = yaffs_FindObjectByNumber(dev,hl->variant.hardLinkVariant.equivalentObjectId);
2819
2820                 if(in)
2821                 {
2822                         hl->variant.hardLinkVariant.equivalentObject=in;
2823                         list_add(&hl->hardLinks,&in->hardLinks);
2824                 }
2825                 else
2826                 {
2827                         //Todo Need to report this better.
2828                         hl->variant.hardLinkVariant.equivalentObject=NULL;
2829                         INIT_LIST_HEAD(&hl->hardLinks);
2830
2831                 }
2832
2833         }
2834
2835
2836
2837         return YAFFS_OK;
2838 }
2839
2840
2841 ////////////////////////// Directory Functions /////////////////////////
2842
2843
2844 static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj)
2845 {
2846
2847         if(obj->siblings.prev == NULL)
2848         {
2849                 // Not initialised
2850                 INIT_LIST_HEAD(&obj->siblings);
2851
2852         }
2853         else if(!list_empty(&obj->siblings))
2854         {
2855                 // If it is holed up somewhere else, un hook it
2856                 list_del_init(&obj->siblings);
2857         }
2858         // Now add it
2859         list_add(&obj->siblings,&directory->variant.directoryVariant.children);
2860         obj->parent = directory;
2861 }
2862
2863 static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj)
2864 {
2865         list_del_init(&obj->siblings);
2866         obj->parent = NULL;
2867 }
2868
2869 yaffs_Object *yaffs_FindObjectByName(yaffs_Object *directory,const char *name)
2870 {
2871         int sum;
2872
2873         struct list_head *i;
2874         __u8 buffer[YAFFS_BYTES_PER_CHUNK];
2875         yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
2876
2877         yaffs_Object *l;
2878
2879         sum = yaffs_CalcNameSum(name);
2880
2881         list_for_each(i,&directory->variant.directoryVariant.children)
2882         {
2883                 l = list_entry(i, yaffs_Object,siblings);
2884
2885                 // Special case for lost-n-found
2886                 if(l->objectId == YAFFS_OBJECTID_LOSTNFOUND)
2887                 {
2888                         if(strcmp(name,YAFFS_LOSTNFOUND_NAME) == 0)
2889                         {
2890                                 return l;
2891                         }
2892                 }
2893                 else if(l->sum == sum)
2894                 {
2895                         // Do a real check
2896                         yaffs_ReadChunkFromNAND(l->myDev,l->chunkId,buffer,NULL);
2897                         if(strcmp(name,oh->name) == 0)
2898                         {
2899                                 return l;
2900                         }
2901
2902
2903                 }
2904         }
2905
2906         return NULL;
2907 }
2908
2909
2910 int yaffs_ApplyToDirectoryChildren(yaffs_Object *theDir,int (*fn)(yaffs_Object *))
2911 {
2912         struct list_head *i;
2913         yaffs_Object *l;
2914
2915
2916         list_for_each(i,&theDir->variant.directoryVariant.children)
2917         {
2918                 l = list_entry(i, yaffs_Object,siblings);
2919                 if(!fn(l))
2920                 {
2921                         return YAFFS_FAIL;
2922                 }
2923         }
2924
2925         return YAFFS_OK;
2926
2927 }
2928
2929
2930 // GetEquivalentObject dereferences any hard links to get to the
2931 // actual object.
2932
2933 static yaffs_Object *yaffs_GetEquivalentObject(yaffs_Object *obj)
2934 {
2935         if(obj && obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
2936         {
2937                 // We want the object id of the equivalent object, not this one
2938                 obj = obj->variant.hardLinkVariant.equivalentObject;
2939         }
2940         return obj;
2941
2942 }
2943
2944 int yaffs_GetObjectName(yaffs_Object *obj,char *name,int buffSize)
2945 {
2946         memset(name,0,buffSize);
2947
2948         if(obj->objectId == YAFFS_OBJECTID_LOSTNFOUND)
2949         {
2950                 strncpy(name,YAFFS_LOSTNFOUND_NAME,buffSize - 1);
2951         }
2952         else
2953         {
2954                 __u8 buffer[YAFFS_BYTES_PER_CHUNK];
2955                 yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
2956
2957                 memset(buffer,0,YAFFS_BYTES_PER_CHUNK);
2958
2959                 if(obj->chunkId >= 0)
2960                 {
2961                         yaffs_ReadChunkFromNAND(obj->myDev,obj->chunkId,buffer,NULL);
2962                 }
2963                 strncpy(name,oh->name,buffSize - 1);
2964         }
2965
2966         return strlen(name);
2967 }
2968
2969 int yaffs_GetObjectFileLength(yaffs_Object *obj)
2970 {
2971
2972         // Dereference any hard linking
2973         obj = yaffs_GetEquivalentObject(obj);
2974
2975         if(obj->variantType == YAFFS_OBJECT_TYPE_FILE)
2976         {
2977                 return obj->variant.fileVariant.fileSize;
2978         }
2979         if(obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK)
2980         {
2981                 return strlen(obj->variant.symLinkVariant.alias);
2982         }
2983         else
2984         {
2985                 // Only a directory should drop through to here
2986                 return YAFFS_BYTES_PER_CHUNK;
2987         }
2988 }
2989
2990 int yaffs_GetObjectLinkCount(yaffs_Object *obj)
2991 {
2992         int count = 1; // the object itself
2993         struct list_head *i;
2994
2995         list_for_each(i,&obj->hardLinks)
2996         {
2997                 count++;
2998         }
2999         return count;
3000
3001 }
3002
3003
3004 int yaffs_GetObjectInode(yaffs_Object *obj)
3005 {
3006         obj = yaffs_GetEquivalentObject(obj);
3007
3008         return obj->objectId;
3009 }
3010
3011 unsigned yaffs_GetObjectType(yaffs_Object *obj)
3012 {
3013         obj = yaffs_GetEquivalentObject(obj);
3014
3015         switch(obj->variantType)
3016         {
3017                 case YAFFS_OBJECT_TYPE_FILE:            return DT_REG; break;
3018                 case YAFFS_OBJECT_TYPE_DIRECTORY:       return DT_DIR; break;
3019                 case YAFFS_OBJECT_TYPE_SYMLINK:         return DT_LNK; break;
3020                 case YAFFS_OBJECT_TYPE_HARDLINK:        return DT_REG; break;
3021                 default: return DT_REG; break;
3022         }
3023 }
3024
3025 char *yaffs_GetSymlinkAlias(yaffs_Object *obj)
3026 {
3027         obj = yaffs_GetEquivalentObject(obj);
3028         if(obj->variantType == YAFFS_OBJECT_TYPE_SYMLINK)
3029         {
3030                 return yaffs_CloneString(obj->variant.symLinkVariant.alias);
3031         }
3032         else
3033         {
3034                 return yaffs_CloneString("");
3035         }
3036 }
3037
3038
3039 int yaffs_SetAttributes(yaffs_Object *obj, struct iattr *attr)
3040 {
3041         unsigned int valid = attr->ia_valid;
3042
3043         if(valid & ATTR_MODE) obj->st_mode = attr->ia_mode;
3044         if(valid & ATTR_UID) obj->st_uid = attr->ia_uid;
3045         if(valid & ATTR_GID) obj->st_gid = attr->ia_gid;
3046
3047         if(valid & ATTR_ATIME) obj->st_atime = attr->ia_atime;
3048         if(valid & ATTR_CTIME) obj->st_ctime = attr->ia_ctime;
3049         if(valid & ATTR_MTIME) obj->st_mtime = attr->ia_mtime;
3050
3051         if(valid & ATTR_SIZE) yaffs_ResizeFile(obj,attr->ia_size);
3052
3053         yaffs_UpdateObjectHeader(obj,NULL);
3054
3055         return YAFFS_OK;
3056
3057 }
3058 int yaffs_GetAttributes(yaffs_Object *obj, struct iattr *attr)
3059 {
3060         unsigned int valid = 0;
3061
3062         attr->ia_mode = obj->st_mode;   valid |= ATTR_MODE;
3063         attr->ia_uid = obj->st_uid;             valid |= ATTR_UID;
3064         attr->ia_gid = obj->st_gid;             valid |= ATTR_GID;
3065
3066         attr->ia_atime = obj->st_atime; valid |= ATTR_ATIME;
3067         attr->ia_ctime = obj->st_ctime; valid |= ATTR_CTIME;
3068         attr->ia_mtime = obj->st_mtime; valid |= ATTR_MTIME;
3069
3070         attr->ia_size = yaffs_GetFileSize(obj); valid |= ATTR_SIZE;
3071
3072         attr->ia_valid = valid;
3073
3074         return YAFFS_OK;
3075
3076 }
3077
3078
3079
3080 int yaffs_DumpObject(yaffs_Object *obj)
3081 {
3082         __u8 buffer[YAFFS_BYTES_PER_CHUNK];
3083         char name[256];
3084 //      yaffs_ObjectHeader *oh = (yaffs_ObjectHeader *)buffer;
3085
3086         memset(buffer,0,YAFFS_BYTES_PER_CHUNK);
3087
3088         if(obj->chunkId >= 0)
3089         {
3090                 yaffs_ReadChunkFromNAND(obj->myDev,obj->chunkId,buffer,NULL);
3091         }
3092
3093         yaffs_GetObjectName(obj,name,256);
3094
3095         YPRINTF(("Object %d \"%s\"\n dirty %d valid %d serial %d sum %d chunk %d type %d size %d\n",
3096                         yaffs_GetObjectInode(obj), name, obj->dirty, obj->valid, obj->serial,
3097                         obj->sum, obj->chunkId, yaffs_GetObjectType(obj), yaffs_GetObjectFileLength(obj)));
3098
3099 #if 0
3100         YPRINTF(("Object %d \"%s\"\n dirty %d valid %d serial %d sum %d chunk %d\n",
3101                         obj->objectId, oh->name, obj->dirty, obj->valid, obj->serial,
3102                         obj->sum, obj->chunkId));
3103                 switch(obj->variantType)
3104         {
3105                 case YAFFS_OBJECT_TYPE_FILE:
3106                         YPRINTF((" FILE length %d\n",obj->variant.fileVariant.fileSize));
3107                         break;
3108                 case YAFFS_OBJECT_TYPE_DIRECTORY:
3109                         YPRINTF((" DIRECTORY\n"));
3110                         break;
3111                 case YAFFS_OBJECT_TYPE_HARDLINK: //todo
3112                 case YAFFS_OBJECT_TYPE_SYMLINK:
3113                 case YAFFS_OBJECT_TYPE_UNKNOWN:
3114                 default:
3115         }
3116 #endif
3117
3118         return YAFFS_OK;
3119 }
3120
3121
3122 ///////////////////////// Initialisation code ///////////////////////////
3123
3124
3125
3126 int yaffs_GutsInitialise(yaffs_Device *dev)
3127 {
3128         unsigned  nChunks,x;
3129         int bits;
3130
3131
3132         dev = dev;
3133
3134         if(!yaffs_CheckStructures())
3135         {
3136                 return YAFFS_FAIL;
3137         }
3138
3139
3140         // OK now calculate a few things for the device
3141         // Calculate chunkGroupBits.
3142         // If there are 64k or less chunks then this is 1
3143         // Else it is log2(nChunks) - 16
3144         //
3145         x = nChunks = YAFFS_CHUNKS_PER_BLOCK * dev->nBlocks;
3146
3147         for(bits = 0, x = nChunks; (x & 1) == 0; bits++)
3148         {
3149                 x >>= 1;
3150         }
3151
3152         if( x != 1)
3153         {
3154                 // Not a power of 2
3155                 YPRINTF(("nBlocks should be a power of 2 but is %u\n",
3156                         dev->nBlocks));
3157                 return YAFFS_FAIL;
3158         }
3159
3160         if(bits <= 16)
3161         {
3162                 dev->chunkGroupBits = 0;
3163                 dev->chunkGroupSize = 1;
3164         }
3165         else
3166         {
3167                 dev->chunkGroupBits = bits - 16;
3168                 dev->chunkGroupSize = nChunks/0x10000;
3169         }
3170
3171         // More device initialisation
3172         dev->garbageCollectionRequired  = 0;
3173         dev->currentDirtyChecker = 0;
3174
3175         yaffs_InitialiseBlocks(dev);
3176
3177         yaffs_InitialiseTnodes(dev);
3178
3179         yaffs_InitialiseObjects(dev);
3180
3181
3182         // Initialise the root and lost and found directories
3183         dev->lostNFoundDir = dev->rootDir = NULL;
3184         dev->rootDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_ROOT,YAFFS_ROOT_MODE | S_IFDIR);
3185         dev->lostNFoundDir = yaffs_CreateFakeDirectory(dev,YAFFS_OBJECTID_LOSTNFOUND,YAFFS_ROOT_MODE | S_IFDIR);
3186         yaffs_AddObjectToDirectory(dev->rootDir,dev->lostNFoundDir);
3187
3188         // Now scan the flash.
3189         yaffs_Scan(dev);
3190
3191
3192         return YAFFS_OK;
3193
3194 }
3195
3196 void yaffs_Deinitialise(yaffs_Device *dev)
3197 {
3198         yaffs_DeinitialiseBlocks(dev);
3199         yaffs_DeinitialiseTnodes(dev);
3200         yaffs_DeinitialiseObjects(dev);
3201
3202 }
3203
3204 int  yaffs_GetNumberOfFreeChunks(yaffs_Device *dev)
3205 {
3206         int nFree = dev->nFreeChunks - (YAFFS_CHUNKS_PER_BLOCK * YAFFS_RESERVED_BLOCKS);
3207
3208         return (nFree < 0) ? 0 : nFree;
3209
3210 }
3211
3212
3213 /////////////////// YAFFS test code //////////////////////////////////
3214
3215 #define yaffs_CheckStruct(structure,syze, name) \
3216            if(sizeof(structure) != syze) \
3217                { YPRINTF(("%s should be %d but is %d\n",name,syze,sizeof(structure))); \
3218                  return YAFFS_FAIL; \
3219                    }
3220
3221
3222 static int yaffs_CheckStructures(void)
3223 {
3224         yaffs_CheckStruct(yaffs_Tags,8,"yaffs_Tags")
3225         yaffs_CheckStruct(yaffs_TagsUnion,8,"yaffs_TagsUnion")
3226         yaffs_CheckStruct(yaffs_Spare,16,"yaffs_Spare")
3227         yaffs_CheckStruct(yaffs_Tnode,2* YAFFS_NTNODES_LEVEL0,"yaffs_Tnode")
3228         yaffs_CheckStruct(yaffs_ObjectHeader,512,"yaffs_ObjectHeader")
3229
3230
3231         return YAFFS_OK;
3232 }
3233
3234 void yaffs_GutsTest(yaffs_Device *dev)
3235 {
3236
3237         if(yaffs_CheckStructures() != YAFFS_OK)
3238         {
3239                 YPRINTF(("One or more structures malformed-- aborting\n"));
3240         }
3241         else
3242         {
3243                 YPRINTF(("Structures OK\n"));
3244         }
3245
3246         yaffs_TnodeTest(dev);
3247         yaffs_ObjectTest(dev);
3248 }
3249
3250