yaffs_guts.c

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