Restructure tests
[yaffs2.git] / yaffs_guts.c
1 /*
2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
3  *
4  * Copyright (C) 2002-2007 Aleph One Ltd.
5  *   for Toby Churchill Ltd and Brightstar Engineering
6  *
7  * Created by Charles Manning <charles@aleph1.co.uk>
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License version 2 as
11  * published by the Free Software Foundation.
12  */
13
14 const char *yaffs_guts_c_version =
15     "$Id: yaffs_guts.c,v 1.69 2009-01-04 21:44:23 charles Exp $";
16
17 #include "yportenv.h"
18
19 #include "yaffsinterface.h"
20 #include "yaffs_guts.h"
21 #include "yaffs_tagsvalidity.h"
22 #include "yaffs_getblockinfo.h"
23
24 #include "yaffs_tagscompat.h"
25 #ifndef  CONFIG_YAFFS_USE_OWN_SORT
26 #include "yaffs_qsort.h"
27 #endif
28 #include "yaffs_nand.h"
29
30 #include "yaffs_checkptrw.h"
31
32 #include "yaffs_nand.h"
33 #include "yaffs_packedtags2.h"
34
35
36 #ifdef CONFIG_YAFFS_WINCE
37 void yfsd_LockYAFFS(BOOL fsLockOnly);
38 void yfsd_UnlockYAFFS(BOOL fsLockOnly);
39 #endif
40
41 #define YAFFS_PASSIVE_GC_CHUNKS 2
42
43 #include "yaffs_ecc.h"
44
45
46 /* Robustification (if it ever comes about...) */
47 static void yaffs_RetireBlock(yaffs_Device * dev, int blockInNAND);
48 static void yaffs_HandleWriteChunkError(yaffs_Device * dev, int chunkInNAND, int erasedOk);
49 static void yaffs_HandleWriteChunkOk(yaffs_Device * dev, int chunkInNAND,
50                                      const __u8 * data,
51                                      const yaffs_ExtendedTags * tags);
52 static void yaffs_HandleUpdateChunk(yaffs_Device * dev, int chunkInNAND,
53                                     const yaffs_ExtendedTags * tags);
54
55 /* Other local prototypes */
56 static int yaffs_UnlinkObject( yaffs_Object *obj);
57 static int yaffs_ObjectHasCachedWriteData(yaffs_Object *obj);
58
59 static void yaffs_HardlinkFixup(yaffs_Device *dev, yaffs_Object *hardList);
60
61 static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device * dev,
62                                              const __u8 * buffer,
63                                              yaffs_ExtendedTags * tags,
64                                              int useReserve);
65 static int yaffs_PutChunkIntoFile(yaffs_Object * in, int chunkInInode,
66                                   int chunkInNAND, int inScan);
67
68 static yaffs_Object *yaffs_CreateNewObject(yaffs_Device * dev, int number,
69                                            yaffs_ObjectType type);
70 static void yaffs_AddObjectToDirectory(yaffs_Object * directory,
71                                        yaffs_Object * obj);
72 static int yaffs_UpdateObjectHeader(yaffs_Object * in, const YCHAR * name,
73                                     int force, int isShrink, int shadows);
74 static void yaffs_RemoveObjectFromDirectory(yaffs_Object * obj);
75 static int yaffs_CheckStructures(void);
76 static int yaffs_DeleteWorker(yaffs_Object * in, yaffs_Tnode * tn, __u32 level,
77                               int chunkOffset, int *limit);
78 static int yaffs_DoGenericObjectDeletion(yaffs_Object * in);
79
80 static yaffs_BlockInfo *yaffs_GetBlockInfo(yaffs_Device * dev, int blockNo);
81
82
83 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,
84                                   int chunkInNAND);
85
86 static int yaffs_UnlinkWorker(yaffs_Object * obj);
87 static void yaffs_DestroyObject(yaffs_Object * obj);
88
89 static int yaffs_TagsMatch(const yaffs_ExtendedTags * tags, int objectId,
90                            int chunkInObject);
91
92 loff_t yaffs_GetFileSize(yaffs_Object * obj);
93
94 static int yaffs_AllocateChunk(yaffs_Device * dev, int useReserve, yaffs_BlockInfo **blockUsedPtr);
95
96 static void yaffs_VerifyFreeChunks(yaffs_Device * dev);
97
98 static void yaffs_CheckObjectDetailsLoaded(yaffs_Object *in);
99
100 static void yaffs_VerifyDirectory(yaffs_Object *directory);
101 #ifdef YAFFS_PARANOID
102 static int yaffs_CheckFileSanity(yaffs_Object * in);
103 #else
104 #define yaffs_CheckFileSanity(in)
105 #endif
106
107 static void yaffs_InvalidateWholeChunkCache(yaffs_Object * in);
108 static void yaffs_InvalidateChunkCache(yaffs_Object * object, int chunkId);
109
110 static void yaffs_InvalidateCheckpoint(yaffs_Device *dev);
111
112 static int yaffs_FindChunkInFile(yaffs_Object * in, int chunkInInode,
113                                  yaffs_ExtendedTags * tags);
114
115 static __u32 yaffs_GetChunkGroupBase(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos);
116 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device * dev,
117                                           yaffs_FileStructure * fStruct,
118                                           __u32 chunkId);
119
120
121 /* Function to calculate chunk and offset */
122
123 static void yaffs_AddrToChunk(yaffs_Device *dev, loff_t addr, int *chunkOut, __u32 *offsetOut)
124 {
125         int chunk;
126         __u32 offset;
127         
128         chunk  = (__u32)(addr >> dev->chunkShift);
129                 
130         if(dev->chunkDiv == 1)
131         {
132                 /* easy power of 2 case */
133                 offset = (__u32)(addr & dev->chunkMask);
134         }
135         else
136         {
137                 /* Non power-of-2 case */
138                 
139                 loff_t chunkBase;
140                 
141                 chunk /= dev->chunkDiv;
142                 
143                 chunkBase = ((loff_t)chunk) * dev->nDataBytesPerChunk;
144                 offset = (__u32)(addr - chunkBase);
145         }
146
147         *chunkOut = chunk;
148         *offsetOut = offset;
149 }
150
151 /* Function to return the number of shifts for a power of 2 greater than or equal 
152  * to the given number
153  * Note we don't try to cater for all possible numbers and this does not have to
154  * be hellishly efficient.
155  */
156  
157 static __u32 ShiftsGE(__u32 x)
158 {
159         int extraBits;
160         int nShifts;
161         
162         nShifts = extraBits = 0;
163         
164         while(x>1){
165                 if(x & 1) extraBits++;
166                 x>>=1;
167                 nShifts++;
168         }
169
170         if(extraBits) 
171                 nShifts++;
172                 
173         return nShifts;
174 }
175
176 /* Function to return the number of shifts to get a 1 in bit 0
177  */
178  
179 static __u32 Shifts(__u32 x)
180 {
181         int nShifts;
182         
183         nShifts =  0;
184         
185         if(!x) return 0;
186         
187         while( !(x&1)){
188                 x>>=1;
189                 nShifts++;
190         }
191                 
192         return nShifts;
193 }
194
195
196
197 /* 
198  * Temporary buffer manipulations.
199  */
200
201 static int yaffs_InitialiseTempBuffers(yaffs_Device *dev)       
202 {
203         int i;
204         __u8 *buf = (__u8 *)1;
205                 
206         memset(dev->tempBuffer,0,sizeof(dev->tempBuffer));
207                 
208         for (i = 0; buf && i < YAFFS_N_TEMP_BUFFERS; i++) {
209                 dev->tempBuffer[i].line = 0;    /* not in use */
210                 dev->tempBuffer[i].buffer = buf =
211                     YMALLOC_DMA(dev->totalBytesPerChunk);
212         }
213                 
214         return buf ? YAFFS_OK : YAFFS_FAIL;
215         
216 }
217
218 __u8 *yaffs_GetTempBuffer(yaffs_Device * dev, int lineNo)
219 {
220         int i, j;
221
222         dev->tempInUse++;
223         if(dev->tempInUse > dev->maxTemp)
224                 dev->maxTemp = dev->tempInUse;
225
226         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
227                 if (dev->tempBuffer[i].line == 0) {
228                         dev->tempBuffer[i].line = lineNo;
229                         if ((i + 1) > dev->maxTemp) {
230                                 dev->maxTemp = i + 1;
231                                 for (j = 0; j <= i; j++)
232                                         dev->tempBuffer[j].maxLine =
233                                             dev->tempBuffer[j].line;
234                         }
235
236                         return dev->tempBuffer[i].buffer;
237                 }
238         }
239
240         T(YAFFS_TRACE_BUFFERS,
241           (TSTR("Out of temp buffers at line %d, other held by lines:"),
242            lineNo));
243         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
244                 T(YAFFS_TRACE_BUFFERS, (TSTR(" %d "), dev->tempBuffer[i].line));
245         }
246         T(YAFFS_TRACE_BUFFERS, (TSTR(" " TENDSTR)));
247
248         /*
249          * If we got here then we have to allocate an unmanaged one
250          * This is not good.
251          */
252
253         dev->unmanagedTempAllocations++;
254         return YMALLOC(dev->nDataBytesPerChunk);
255
256 }
257
258 void yaffs_ReleaseTempBuffer(yaffs_Device * dev, __u8 * buffer,
259                                     int lineNo)
260 {
261         int i;
262         
263         dev->tempInUse--;
264         
265         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
266                 if (dev->tempBuffer[i].buffer == buffer) {
267                         dev->tempBuffer[i].line = 0;
268                         return;
269                 }
270         }
271
272         if (buffer) {
273                 /* assume it is an unmanaged one. */
274                 T(YAFFS_TRACE_BUFFERS,
275                   (TSTR("Releasing unmanaged temp buffer in line %d" TENDSTR),
276                    lineNo));
277                 YFREE(buffer);
278                 dev->unmanagedTempDeallocations++;
279         }
280
281 }
282
283 /*
284  * Determine if we have a managed buffer.
285  */
286 int yaffs_IsManagedTempBuffer(yaffs_Device * dev, const __u8 * buffer)
287 {
288         int i;
289         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
290                 if (dev->tempBuffer[i].buffer == buffer)
291                         return 1;
292
293         }
294
295     for (i = 0; i < dev->nShortOpCaches; i++) {
296         if( dev->srCache[i].data == buffer )
297             return 1;
298
299     }
300
301     if (buffer == dev->checkpointBuffer)
302       return 1;
303
304     T(YAFFS_TRACE_ALWAYS,
305           (TSTR("yaffs: unmaged buffer detected.\n" TENDSTR)));
306     return 0;
307 }
308
309
310
311 /*
312  * Chunk bitmap manipulations
313  */
314
315 static Y_INLINE __u8 *yaffs_BlockBits(yaffs_Device * dev, int blk)
316 {
317         if (blk < dev->internalStartBlock || blk > dev->internalEndBlock) {
318                 T(YAFFS_TRACE_ERROR,
319                   (TSTR("**>> yaffs: BlockBits block %d is not valid" TENDSTR),
320                    blk));
321                 YBUG();
322         }
323         return dev->chunkBits +
324             (dev->chunkBitmapStride * (blk - dev->internalStartBlock));
325 }
326
327 static Y_INLINE void yaffs_VerifyChunkBitId(yaffs_Device *dev, int blk, int chunk)
328 {
329         if(blk < dev->internalStartBlock || blk > dev->internalEndBlock ||
330            chunk < 0 || chunk >= dev->nChunksPerBlock) {
331            T(YAFFS_TRACE_ERROR,
332             (TSTR("**>> yaffs: Chunk Id (%d:%d) invalid"TENDSTR),blk,chunk));
333             YBUG();
334         }
335 }
336
337 static Y_INLINE void yaffs_ClearChunkBits(yaffs_Device * dev, int blk)
338 {
339         __u8 *blkBits = yaffs_BlockBits(dev, blk);
340
341         memset(blkBits, 0, dev->chunkBitmapStride);
342 }
343
344 static Y_INLINE void yaffs_ClearChunkBit(yaffs_Device * dev, int blk, int chunk)
345 {
346         __u8 *blkBits = yaffs_BlockBits(dev, blk);
347
348         yaffs_VerifyChunkBitId(dev,blk,chunk);
349
350         blkBits[chunk / 8] &= ~(1 << (chunk & 7));
351 }
352
353 static Y_INLINE void yaffs_SetChunkBit(yaffs_Device * dev, int blk, int chunk)
354 {
355         __u8 *blkBits = yaffs_BlockBits(dev, blk);
356         
357         yaffs_VerifyChunkBitId(dev,blk,chunk);
358
359         blkBits[chunk / 8] |= (1 << (chunk & 7));
360 }
361
362 static Y_INLINE int yaffs_CheckChunkBit(yaffs_Device * dev, int blk, int chunk)
363 {
364         __u8 *blkBits = yaffs_BlockBits(dev, blk);
365         yaffs_VerifyChunkBitId(dev,blk,chunk);
366
367         return (blkBits[chunk / 8] & (1 << (chunk & 7))) ? 1 : 0;
368 }
369
370 static Y_INLINE int yaffs_StillSomeChunkBits(yaffs_Device * dev, int blk)
371 {
372         __u8 *blkBits = yaffs_BlockBits(dev, blk);
373         int i;
374         for (i = 0; i < dev->chunkBitmapStride; i++) {
375                 if (*blkBits)
376                         return 1;
377                 blkBits++;
378         }
379         return 0;
380 }
381
382 static int yaffs_CountChunkBits(yaffs_Device * dev, int blk)
383 {
384         __u8 *blkBits = yaffs_BlockBits(dev, blk);
385         int i;
386         int n = 0;
387         for (i = 0; i < dev->chunkBitmapStride; i++) {
388                 __u8 x = *blkBits;
389                 while(x){
390                         if(x & 1)
391                                 n++;
392                         x >>=1;
393                 }
394                         
395                 blkBits++;
396         }
397         return n;
398 }
399
400 /* 
401  * Verification code
402  */
403  
404 static int yaffs_SkipVerification(yaffs_Device *dev)
405 {
406         return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY | YAFFS_TRACE_VERIFY_FULL));
407 }
408
409 static int yaffs_SkipFullVerification(yaffs_Device *dev)
410 {
411         return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY_FULL));
412 }
413
414 static int yaffs_SkipNANDVerification(yaffs_Device *dev)
415 {
416         return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY_NAND));
417 }
418
419 static const char * blockStateName[] = {
420 "Unknown",
421 "Needs scanning",
422 "Scanning",
423 "Empty",
424 "Allocating",
425 "Full",
426 "Dirty",
427 "Checkpoint",
428 "Collecting",
429 "Dead"
430 };
431
432 static void yaffs_VerifyBlock(yaffs_Device *dev,yaffs_BlockInfo *bi,int n)
433 {
434         int actuallyUsed;
435         int inUse;
436         
437         if(yaffs_SkipVerification(dev))
438                 return;
439                 
440         /* Report illegal runtime states */
441         if(bi->blockState >= YAFFS_NUMBER_OF_BLOCK_STATES)
442                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has undefined state %d"TENDSTR),n,bi->blockState));
443                 
444         switch(bi->blockState){
445          case YAFFS_BLOCK_STATE_UNKNOWN:
446          case YAFFS_BLOCK_STATE_SCANNING:
447          case YAFFS_BLOCK_STATE_NEEDS_SCANNING:
448                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has bad run-state %s"TENDSTR),
449                 n,blockStateName[bi->blockState]));
450         }
451         
452         /* Check pages in use and soft deletions are legal */
453         
454         actuallyUsed = bi->pagesInUse - bi->softDeletions;
455         
456         if(bi->pagesInUse < 0 || bi->pagesInUse > dev->nChunksPerBlock ||
457            bi->softDeletions < 0 || bi->softDeletions > dev->nChunksPerBlock ||
458            actuallyUsed < 0 || actuallyUsed > dev->nChunksPerBlock)
459                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has illegal values pagesInUsed %d softDeletions %d"TENDSTR),
460                 n,bi->pagesInUse,bi->softDeletions));
461         
462                 
463         /* Check chunk bitmap legal */
464         inUse = yaffs_CountChunkBits(dev,n);
465         if(inUse != bi->pagesInUse)
466                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has inconsistent values pagesInUse %d counted chunk bits %d"TENDSTR),
467                         n,bi->pagesInUse,inUse));
468         
469         /* Check that the sequence number is valid.
470          * Ten million is legal, but is very unlikely 
471          */
472         if(dev->isYaffs2 && 
473            (bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING || bi->blockState == YAFFS_BLOCK_STATE_FULL) &&
474            (bi->sequenceNumber < YAFFS_LOWEST_SEQUENCE_NUMBER || bi->sequenceNumber > 10000000 ))
475                 T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has suspect sequence number of %d"TENDSTR),
476                 n,bi->sequenceNumber));
477                 
478 }
479
480 static void yaffs_VerifyCollectedBlock(yaffs_Device *dev,yaffs_BlockInfo *bi,int n)
481 {
482         yaffs_VerifyBlock(dev,bi,n);
483         
484         /* After collection the block should be in the erased state */
485         /* This will need to change if we do partial gc */
486         
487         if(bi->blockState != YAFFS_BLOCK_STATE_COLLECTING &&
488            bi->blockState != YAFFS_BLOCK_STATE_EMPTY){
489                 T(YAFFS_TRACE_ERROR,(TSTR("Block %d is in state %d after gc, should be erased"TENDSTR),
490                         n,bi->blockState));
491         }
492 }
493
494 static void yaffs_VerifyBlocks(yaffs_Device *dev)
495 {
496         int i;
497         int nBlocksPerState[YAFFS_NUMBER_OF_BLOCK_STATES];
498         int nIllegalBlockStates = 0;
499         
500
501         if(yaffs_SkipVerification(dev))
502                 return;
503
504         memset(nBlocksPerState,0,sizeof(nBlocksPerState));
505
506                 
507         for(i = dev->internalStartBlock; i <= dev->internalEndBlock; i++){
508                 yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,i);
509                 yaffs_VerifyBlock(dev,bi,i);
510
511                 if(bi->blockState < YAFFS_NUMBER_OF_BLOCK_STATES)
512                         nBlocksPerState[bi->blockState]++;
513                 else
514                         nIllegalBlockStates++;
515                                         
516         }
517         
518         T(YAFFS_TRACE_VERIFY,(TSTR(""TENDSTR)));
519         T(YAFFS_TRACE_VERIFY,(TSTR("Block summary"TENDSTR)));
520         
521         T(YAFFS_TRACE_VERIFY,(TSTR("%d blocks have illegal states"TENDSTR),nIllegalBlockStates));
522         if(nBlocksPerState[YAFFS_BLOCK_STATE_ALLOCATING] > 1)
523                 T(YAFFS_TRACE_VERIFY,(TSTR("Too many allocating blocks"TENDSTR)));
524
525         for(i = 0; i < YAFFS_NUMBER_OF_BLOCK_STATES; i++)
526                 T(YAFFS_TRACE_VERIFY,
527                   (TSTR("%s %d blocks"TENDSTR),
528                   blockStateName[i],nBlocksPerState[i]));
529         
530         if(dev->blocksInCheckpoint != nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT])
531                 T(YAFFS_TRACE_VERIFY,
532                  (TSTR("Checkpoint block count wrong dev %d count %d"TENDSTR),
533                  dev->blocksInCheckpoint, nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT]));
534                  
535         if(dev->nErasedBlocks != nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY])
536                 T(YAFFS_TRACE_VERIFY,
537                  (TSTR("Erased block count wrong dev %d count %d"TENDSTR),
538                  dev->nErasedBlocks, nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY]));
539                  
540         if(nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING] > 1)
541                 T(YAFFS_TRACE_VERIFY,
542                  (TSTR("Too many collecting blocks %d (max is 1)"TENDSTR),
543                  nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING]));
544
545         T(YAFFS_TRACE_VERIFY,(TSTR(""TENDSTR)));
546
547 }
548
549 /*
550  * Verify the object header. oh must be valid, but obj and tags may be NULL in which
551  * case those tests will not be performed.
552  */
553 static void yaffs_VerifyObjectHeader(yaffs_Object *obj, yaffs_ObjectHeader *oh, yaffs_ExtendedTags *tags, int parentCheck)
554 {
555         if(obj && yaffs_SkipVerification(obj->myDev))
556                 return;
557                 
558         if(!(tags && obj && oh)){
559                 T(YAFFS_TRACE_VERIFY,
560                                 (TSTR("Verifying object header tags %x obj %x oh %x"TENDSTR),
561                                 (__u32)tags,(__u32)obj,(__u32)oh));
562                 return;
563         }
564         
565         if(oh->type <= YAFFS_OBJECT_TYPE_UNKNOWN ||
566            oh->type > YAFFS_OBJECT_TYPE_MAX)
567                 T(YAFFS_TRACE_VERIFY,
568                  (TSTR("Obj %d header type is illegal value 0x%x"TENDSTR),
569                  tags->objectId, oh->type));
570
571         if(tags->objectId != obj->objectId)
572                 T(YAFFS_TRACE_VERIFY,
573                  (TSTR("Obj %d header mismatch objectId %d"TENDSTR),
574                  tags->objectId, obj->objectId));
575
576
577         /*
578          * Check that the object's parent ids match if parentCheck requested.
579          * 
580          * Tests do not apply to the root object.
581          */
582         
583         if(parentCheck && tags->objectId > 1 && !obj->parent)
584                 T(YAFFS_TRACE_VERIFY,
585                  (TSTR("Obj %d header mismatch parentId %d obj->parent is NULL"TENDSTR),
586                  tags->objectId, oh->parentObjectId));
587                 
588         
589         if(parentCheck && obj->parent &&
590            oh->parentObjectId != obj->parent->objectId && 
591            (oh->parentObjectId != YAFFS_OBJECTID_UNLINKED ||
592             obj->parent->objectId != YAFFS_OBJECTID_DELETED))
593                 T(YAFFS_TRACE_VERIFY,
594                  (TSTR("Obj %d header mismatch parentId %d parentObjectId %d"TENDSTR),
595                  tags->objectId, oh->parentObjectId, obj->parent->objectId));
596                 
597         
598         if(tags->objectId > 1 && oh->name[0] == 0) /* Null name */
599                 T(YAFFS_TRACE_VERIFY,
600                 (TSTR("Obj %d header name is NULL"TENDSTR),
601                  obj->objectId));
602
603         if(tags->objectId > 1 && ((__u8)(oh->name[0])) == 0xff) /* Trashed name */
604                 T(YAFFS_TRACE_VERIFY,
605                 (TSTR("Obj %d header name is 0xFF"TENDSTR),
606                  obj->objectId));
607 }
608
609
610
611 static int yaffs_VerifyTnodeWorker(yaffs_Object * obj, yaffs_Tnode * tn,
612                                         __u32 level, int chunkOffset)
613 {
614         int i;
615         yaffs_Device *dev = obj->myDev;
616         int ok = 1;
617
618         if (tn) {
619                 if (level > 0) {
620
621                         for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++){
622                                 if (tn->internal[i]) {
623                                         ok = yaffs_VerifyTnodeWorker(obj,
624                                                         tn->internal[i],
625                                                         level - 1,
626                                                         (chunkOffset<<YAFFS_TNODES_INTERNAL_BITS) + i);
627                                 }
628                         }
629                 } else if (level == 0) {
630                         yaffs_ExtendedTags tags;
631                         __u32 objectId = obj->objectId;
632                         
633                         chunkOffset <<=  YAFFS_TNODES_LEVEL0_BITS;
634                         
635                         for(i = 0; i < YAFFS_NTNODES_LEVEL0; i++){
636                                 __u32 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
637                                 
638                                 if(theChunk > 0){
639                                         /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),tags.objectId,tags.chunkId,theChunk)); */
640                                         yaffs_ReadChunkWithTagsFromNAND(dev,theChunk,NULL, &tags);
641                                         if(tags.objectId != objectId || tags.chunkId != chunkOffset){
642                                                 T(~0,(TSTR("Object %d chunkId %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR),
643                                                         objectId, chunkOffset, theChunk,
644                                                         tags.objectId, tags.chunkId));
645                                         }
646                                 }
647                                 chunkOffset++;
648                         }
649                 }
650         }
651
652         return ok;
653
654 }
655
656
657 static void yaffs_VerifyFile(yaffs_Object *obj)
658 {
659         int requiredTallness;
660         int actualTallness;
661         __u32 lastChunk;
662         __u32 x;
663         __u32 i;
664         yaffs_Device *dev;
665         yaffs_ExtendedTags tags;
666         yaffs_Tnode *tn;
667         __u32 objectId;
668         
669         if(!obj)
670                 return;
671
672         if(yaffs_SkipVerification(obj->myDev))
673                 return;
674         
675         dev = obj->myDev;
676         objectId = obj->objectId;
677         
678         /* Check file size is consistent with tnode depth */
679         lastChunk =  obj->variant.fileVariant.fileSize / dev->nDataBytesPerChunk + 1;
680         x = lastChunk >> YAFFS_TNODES_LEVEL0_BITS;
681         requiredTallness = 0;
682         while (x> 0) {
683                 x >>= YAFFS_TNODES_INTERNAL_BITS;
684                 requiredTallness++;
685         }
686         
687         actualTallness = obj->variant.fileVariant.topLevel;
688         
689         if(requiredTallness > actualTallness )
690                 T(YAFFS_TRACE_VERIFY,
691                 (TSTR("Obj %d had tnode tallness %d, needs to be %d"TENDSTR),
692                  obj->objectId,actualTallness, requiredTallness));
693         
694         
695         /* Check that the chunks in the tnode tree are all correct. 
696          * We do this by scanning through the tnode tree and
697          * checking the tags for every chunk match.
698          */
699
700         if(yaffs_SkipNANDVerification(dev))
701                 return;
702                 
703         for(i = 1; i <= lastChunk; i++){
704                 tn = yaffs_FindLevel0Tnode(dev, &obj->variant.fileVariant,i);
705
706                 if (tn) {
707                         __u32 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
708                         if(theChunk > 0){
709                                 /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),objectId,i,theChunk)); */
710                                 yaffs_ReadChunkWithTagsFromNAND(dev,theChunk,NULL, &tags);
711                                 if(tags.objectId != objectId || tags.chunkId != i){
712                                         T(~0,(TSTR("Object %d chunkId %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR),
713                                                 objectId, i, theChunk,
714                                                 tags.objectId, tags.chunkId));
715                                 }
716                         }
717                 }
718
719         }
720
721 }
722
723
724 static void yaffs_VerifyHardLink(yaffs_Object *obj)
725 {
726         if(obj && yaffs_SkipVerification(obj->myDev))
727                 return;
728                 
729         /* Verify sane equivalent object */
730 }
731
732 static void yaffs_VerifySymlink(yaffs_Object *obj)
733 {
734         if(obj && yaffs_SkipVerification(obj->myDev))
735                 return;
736                 
737         /* Verify symlink string */
738 }
739
740 static void yaffs_VerifySpecial(yaffs_Object *obj)
741 {
742         if(obj && yaffs_SkipVerification(obj->myDev))
743                 return;
744 }
745
746 static void yaffs_VerifyObject(yaffs_Object *obj)
747 {
748         yaffs_Device *dev;
749         
750         __u32 chunkMin;
751         __u32 chunkMax;
752         
753         __u32 chunkIdOk;
754         __u32 chunkIsLive;
755         
756         if(!obj)
757                 return;
758         
759         dev = obj->myDev;
760         
761         if(yaffs_SkipVerification(dev))
762                 return;
763                 
764         /* Check sane object header chunk */
765
766         chunkMin = dev->internalStartBlock * dev->nChunksPerBlock;
767         chunkMax = (dev->internalEndBlock+1) * dev->nChunksPerBlock - 1;
768
769         chunkIdOk = (((unsigned)(obj->hdrChunk)) >= chunkMin && ((unsigned)(obj->hdrChunk)) <= chunkMax);
770         chunkIsLive = chunkIdOk &&
771                         yaffs_CheckChunkBit(dev,
772                                             obj->hdrChunk / dev->nChunksPerBlock,
773                                             obj->hdrChunk % dev->nChunksPerBlock);
774         if(!obj->fake &&
775             (!chunkIdOk || !chunkIsLive)) {
776            T(YAFFS_TRACE_VERIFY,
777            (TSTR("Obj %d has chunkId %d %s %s"TENDSTR),
778            obj->objectId,obj->hdrChunk,
779            chunkIdOk ? "" : ",out of range",
780            chunkIsLive || !chunkIdOk ? "" : ",marked as deleted"));
781         }
782         
783         if(chunkIdOk && chunkIsLive &&!yaffs_SkipNANDVerification(dev)) {
784                 yaffs_ExtendedTags tags;
785                 yaffs_ObjectHeader *oh;
786                 __u8 *buffer = yaffs_GetTempBuffer(dev,__LINE__);
787                 
788                 oh = (yaffs_ObjectHeader *)buffer;
789
790                 yaffs_ReadChunkWithTagsFromNAND(dev, obj->hdrChunk,buffer, &tags);
791
792                 yaffs_VerifyObjectHeader(obj,oh,&tags,1);
793                 
794                 yaffs_ReleaseTempBuffer(dev,buffer,__LINE__);
795         }
796         
797         /* Verify it has a parent */
798         if(obj && !obj->fake &&
799            (!obj->parent || obj->parent->myDev != dev)){
800            T(YAFFS_TRACE_VERIFY,
801            (TSTR("Obj %d has parent pointer %p which does not look like an object"TENDSTR),
802            obj->objectId,obj->parent));    
803         }
804         
805         /* Verify parent is a directory */
806         if(obj->parent && obj->parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY){
807            T(YAFFS_TRACE_VERIFY,
808            (TSTR("Obj %d's parent is not a directory (type %d)"TENDSTR),
809            obj->objectId,obj->parent->variantType));       
810         }
811         
812         switch(obj->variantType){
813         case YAFFS_OBJECT_TYPE_FILE:
814                 yaffs_VerifyFile(obj);
815                 break;
816         case YAFFS_OBJECT_TYPE_SYMLINK:
817                 yaffs_VerifySymlink(obj);
818                 break;
819         case YAFFS_OBJECT_TYPE_DIRECTORY:
820                 yaffs_VerifyDirectory(obj);
821                 break;
822         case YAFFS_OBJECT_TYPE_HARDLINK:
823                 yaffs_VerifyHardLink(obj);
824                 break;
825         case YAFFS_OBJECT_TYPE_SPECIAL:
826                 yaffs_VerifySpecial(obj);
827                 break;
828         case YAFFS_OBJECT_TYPE_UNKNOWN:
829         default:
830                 T(YAFFS_TRACE_VERIFY,
831                 (TSTR("Obj %d has illegaltype %d"TENDSTR),
832                 obj->objectId,obj->variantType));          
833                 break;
834         }
835         
836         
837 }
838
839 static void yaffs_VerifyObjects(yaffs_Device *dev)
840 {
841         yaffs_Object *obj;
842         int i;
843         struct ylist_head *lh;
844
845         if(yaffs_SkipVerification(dev))
846                 return;
847         
848         /* Iterate through the objects in each hash entry */
849          
850          for(i = 0; i <  YAFFS_NOBJECT_BUCKETS; i++){
851                 ylist_for_each(lh, &dev->objectBucket[i].list) {
852                         if (lh) {
853                                 obj = ylist_entry(lh, yaffs_Object, hashLink);
854                                 yaffs_VerifyObject(obj);
855                         }
856                 }
857          }
858
859 }
860
861
862 /*
863  *  Simple hash function. Needs to have a reasonable spread
864  */
865  
866 static Y_INLINE int yaffs_HashFunction(int n)
867 {
868         n = abs(n);
869         return (n % YAFFS_NOBJECT_BUCKETS);
870 }
871
872 /*
873  * Access functions to useful fake objects.
874  * Note that root might have a presence in NAND if permissions are set.
875  */
876  
877 yaffs_Object *yaffs_Root(yaffs_Device * dev)
878 {
879         return dev->rootDir;
880 }
881
882 yaffs_Object *yaffs_LostNFound(yaffs_Device * dev)
883 {
884         return dev->lostNFoundDir;
885 }
886
887
888 /*
889  *  Erased NAND checking functions
890  */
891  
892 int yaffs_CheckFF(__u8 * buffer, int nBytes)
893 {
894         /* Horrible, slow implementation */
895         while (nBytes--) {
896                 if (*buffer != 0xFF)
897                         return 0;
898                 buffer++;
899         }
900         return 1;
901 }
902
903 static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,
904                                   int chunkInNAND)
905 {
906
907         int retval = YAFFS_OK;
908         __u8 *data = yaffs_GetTempBuffer(dev, __LINE__);
909         yaffs_ExtendedTags tags;
910         int result;
911
912         result = yaffs_ReadChunkWithTagsFromNAND(dev, chunkInNAND, data, &tags);
913         
914         if(tags.eccResult > YAFFS_ECC_RESULT_NO_ERROR)
915                 retval = YAFFS_FAIL;
916                 
917
918         if (!yaffs_CheckFF(data, dev->nDataBytesPerChunk) || tags.chunkUsed) {
919                 T(YAFFS_TRACE_NANDACCESS,
920                   (TSTR("Chunk %d not erased" TENDSTR), chunkInNAND));
921                 retval = YAFFS_FAIL;
922         }
923
924         yaffs_ReleaseTempBuffer(dev, data, __LINE__);
925
926         return retval;
927
928 }
929
930 static int yaffs_WriteNewChunkWithTagsToNAND(struct yaffs_DeviceStruct *dev,
931                                              const __u8 * data,
932                                              yaffs_ExtendedTags * tags,
933                                              int useReserve)
934 {
935         int attempts = 0;
936         int writeOk = 0;
937         int chunk;
938
939         yaffs_InvalidateCheckpoint(dev);
940
941         do {
942                 yaffs_BlockInfo *bi = 0;
943                 int erasedOk = 0;
944
945                 chunk = yaffs_AllocateChunk(dev, useReserve, &bi);
946                 if (chunk < 0) {
947                         /* no space */
948                         break;
949                 }
950
951                 /* First check this chunk is erased, if it needs
952                  * checking.  The checking policy (unless forced
953                  * always on) is as follows:
954                  *
955                  * Check the first page we try to write in a block.
956                  * If the check passes then we don't need to check any
957                  * more.        If the check fails, we check again...
958                  * If the block has been erased, we don't need to check.
959                  *
960                  * However, if the block has been prioritised for gc,
961                  * then we think there might be something odd about
962                  * this block and stop using it.
963                  *
964                  * Rationale: We should only ever see chunks that have
965                  * not been erased if there was a partially written
966                  * chunk due to power loss.  This checking policy should
967                  * catch that case with very few checks and thus save a
968                  * lot of checks that are most likely not needed.
969                  */
970                 if (bi->gcPrioritise) {
971                         yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
972                         /* try another chunk */
973                         continue;
974                 }
975
976                 /* let's give it a try */
977                 attempts++;
978
979 #ifdef CONFIG_YAFFS_ALWAYS_CHECK_CHUNK_ERASED
980                 bi->skipErasedCheck = 0;
981 #endif
982                 if (!bi->skipErasedCheck) {
983                         erasedOk = yaffs_CheckChunkErased(dev, chunk);
984                         if (erasedOk != YAFFS_OK) {
985                                 T(YAFFS_TRACE_ERROR,
986                                 (TSTR ("**>> yaffs chunk %d was not erased"
987                                 TENDSTR), chunk));
988
989                                 /* try another chunk */
990                                 continue;
991                         }
992                         bi->skipErasedCheck = 1;
993                 }
994
995                 writeOk = yaffs_WriteChunkWithTagsToNAND(dev, chunk,
996                                 data, tags);
997                 if (writeOk != YAFFS_OK) {
998                         yaffs_HandleWriteChunkError(dev, chunk, erasedOk);
999                         /* try another chunk */
1000                         continue;
1001                 }
1002
1003                 /* Copy the data into the robustification buffer */
1004                 yaffs_HandleWriteChunkOk(dev, chunk, data, tags);
1005
1006         } while (writeOk != YAFFS_OK && 
1007                 (yaffs_wr_attempts <= 0 || attempts <= yaffs_wr_attempts));
1008         
1009         if(!writeOk)
1010                 chunk = -1;
1011
1012         if (attempts > 1) {
1013                 T(YAFFS_TRACE_ERROR,
1014                         (TSTR("**>> yaffs write required %d attempts" TENDSTR),
1015                         attempts));
1016
1017                 dev->nRetriedWrites += (attempts - 1);
1018         }
1019
1020         return chunk;
1021 }
1022
1023 /*
1024  * Block retiring for handling a broken block.
1025  */
1026  
1027 static void yaffs_RetireBlock(yaffs_Device * dev, int blockInNAND)
1028 {
1029         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockInNAND);
1030
1031         yaffs_InvalidateCheckpoint(dev);
1032         
1033         yaffs_MarkBlockBad(dev, blockInNAND);
1034
1035         bi->blockState = YAFFS_BLOCK_STATE_DEAD;
1036         bi->gcPrioritise = 0;
1037         bi->needsRetiring = 0;
1038
1039         dev->nRetiredBlocks++;
1040 }
1041
1042 /*
1043  * Functions for robustisizing TODO
1044  *
1045  */
1046  
1047 static void yaffs_HandleWriteChunkOk(yaffs_Device * dev, int chunkInNAND,
1048                                      const __u8 * data,
1049                                      const yaffs_ExtendedTags * tags)
1050 {
1051 }
1052
1053 static void yaffs_HandleUpdateChunk(yaffs_Device * dev, int chunkInNAND,
1054                                     const yaffs_ExtendedTags * tags)
1055 {
1056 }
1057
1058 void yaffs_HandleChunkError(yaffs_Device *dev, yaffs_BlockInfo *bi)
1059 {
1060         if(!bi->gcPrioritise){
1061                 bi->gcPrioritise = 1;
1062                 dev->hasPendingPrioritisedGCs = 1;
1063                 bi->chunkErrorStrikes ++;
1064                 
1065                 if(bi->chunkErrorStrikes > 3){
1066                         bi->needsRetiring = 1; /* Too many stikes, so retire this */
1067                         T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs: Block struck out" TENDSTR)));
1068
1069                 }
1070                 
1071         }
1072 }
1073
1074 static void yaffs_HandleWriteChunkError(yaffs_Device * dev, int chunkInNAND, int erasedOk)
1075 {
1076
1077         int blockInNAND = chunkInNAND / dev->nChunksPerBlock;
1078         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockInNAND);
1079
1080         yaffs_HandleChunkError(dev,bi);
1081                 
1082         
1083         if(erasedOk ) {
1084                 /* Was an actual write failure, so mark the block for retirement  */
1085                 bi->needsRetiring = 1;
1086                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
1087                   (TSTR("**>> Block %d needs retiring" TENDSTR), blockInNAND));
1088
1089                 
1090         }
1091         
1092         /* Delete the chunk */
1093         yaffs_DeleteChunk(dev, chunkInNAND, 1, __LINE__);
1094 }
1095
1096
1097 /*---------------- Name handling functions ------------*/ 
1098
1099 static __u16 yaffs_CalcNameSum(const YCHAR * name)
1100 {
1101         __u16 sum = 0;
1102         __u16 i = 1;
1103
1104         const YUCHAR *bname = (const YUCHAR *) name;
1105         if (bname) {
1106                 while ((*bname) && (i < (YAFFS_MAX_NAME_LENGTH/2))) {
1107
1108 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
1109                         sum += yaffs_toupper(*bname) * i;
1110 #else
1111                         sum += (*bname) * i;
1112 #endif
1113                         i++;
1114                         bname++;
1115                 }
1116         }
1117         
1118         return sum;
1119 }
1120
1121 static void yaffs_SetObjectName(yaffs_Object * obj, const YCHAR * name)
1122 {
1123 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
1124         memset(obj->shortName,0,sizeof (YCHAR) * (YAFFS_SHORT_NAME_LENGTH+1)); 
1125         if (name && yaffs_strlen(name) <= YAFFS_SHORT_NAME_LENGTH) {
1126                 yaffs_strcpy(obj->shortName, name);
1127         } else {
1128                 obj->shortName[0] = _Y('\0');
1129         }
1130 #endif
1131         obj->sum = yaffs_CalcNameSum(name);
1132 }
1133
1134 /*-------------------- TNODES -------------------
1135
1136  * List of spare tnodes
1137  * The list is hooked together using the first pointer
1138  * in the tnode.
1139  */
1140  
1141 /* yaffs_CreateTnodes creates a bunch more tnodes and
1142  * adds them to the tnode free list.
1143  * Don't use this function directly
1144  */
1145
1146 static int yaffs_CreateTnodes(yaffs_Device * dev, int nTnodes)
1147 {
1148         int i;
1149         int tnodeSize;
1150         yaffs_Tnode *newTnodes;
1151         __u8 *mem;
1152         yaffs_Tnode *curr;
1153         yaffs_Tnode *next;
1154         yaffs_TnodeList *tnl;
1155
1156         if (nTnodes < 1)
1157                 return YAFFS_OK;
1158                 
1159         /* Calculate the tnode size in bytes for variable width tnode support.
1160          * Must be a multiple of 32-bits  */
1161         tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
1162
1163         if(tnodeSize < sizeof(yaffs_Tnode))
1164                 tnodeSize = sizeof(yaffs_Tnode);
1165                 
1166
1167         /* make these things */
1168
1169         newTnodes = YMALLOC(nTnodes * tnodeSize);
1170         mem = (__u8 *)newTnodes;
1171
1172         if (!newTnodes) {
1173                 T(YAFFS_TRACE_ERROR,
1174                   (TSTR("yaffs: Could not allocate Tnodes" TENDSTR)));
1175                 return YAFFS_FAIL;
1176         }
1177
1178         /* Hook them into the free list */
1179 #if 0
1180         for (i = 0; i < nTnodes - 1; i++) {
1181                 newTnodes[i].internal[0] = &newTnodes[i + 1];
1182 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1183                 newTnodes[i].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
1184 #endif
1185         }
1186
1187         newTnodes[nTnodes - 1].internal[0] = dev->freeTnodes;
1188 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1189         newTnodes[nTnodes - 1].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
1190 #endif
1191         dev->freeTnodes = newTnodes;
1192 #else
1193         /* New hookup for wide tnodes */
1194         for(i = 0; i < nTnodes -1; i++) {
1195                 curr = (yaffs_Tnode *) &mem[i * tnodeSize];
1196                 next = (yaffs_Tnode *) &mem[(i+1) * tnodeSize];
1197                 curr->internal[0] = next;
1198         }
1199         
1200         curr = (yaffs_Tnode *) &mem[(nTnodes - 1) * tnodeSize];
1201         curr->internal[0] = dev->freeTnodes;
1202         dev->freeTnodes = (yaffs_Tnode *)mem;
1203
1204 #endif
1205
1206
1207         dev->nFreeTnodes += nTnodes;
1208         dev->nTnodesCreated += nTnodes;
1209
1210         /* Now add this bunch of tnodes to a list for freeing up.
1211          * NB If we can't add this to the management list it isn't fatal
1212          * but it just means we can't free this bunch of tnodes later.
1213          */
1214          
1215         tnl = YMALLOC(sizeof(yaffs_TnodeList));
1216         if (!tnl) {
1217                 T(YAFFS_TRACE_ERROR,
1218                   (TSTR
1219                    ("yaffs: Could not add tnodes to management list" TENDSTR)));
1220                    return YAFFS_FAIL;
1221
1222         } else {
1223                 tnl->tnodes = newTnodes;
1224                 tnl->next = dev->allocatedTnodeList;
1225                 dev->allocatedTnodeList = tnl;
1226         }
1227
1228         T(YAFFS_TRACE_ALLOCATE, (TSTR("yaffs: Tnodes added" TENDSTR)));
1229
1230         return YAFFS_OK;
1231 }
1232
1233 /* GetTnode gets us a clean tnode. Tries to make allocate more if we run out */
1234
1235 static yaffs_Tnode *yaffs_GetTnodeRaw(yaffs_Device * dev)
1236 {
1237         yaffs_Tnode *tn = NULL;
1238
1239         /* If there are none left make more */
1240         if (!dev->freeTnodes) {
1241                 yaffs_CreateTnodes(dev, YAFFS_ALLOCATION_NTNODES);
1242         }
1243
1244         if (dev->freeTnodes) {
1245                 tn = dev->freeTnodes;
1246 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1247                 if (tn->internal[YAFFS_NTNODES_INTERNAL] != (void *)1) {
1248                         /* Hoosterman, this thing looks like it isn't in the list */
1249                         T(YAFFS_TRACE_ALWAYS,
1250                           (TSTR("yaffs: Tnode list bug 1" TENDSTR)));
1251                 }
1252 #endif
1253                 dev->freeTnodes = dev->freeTnodes->internal[0];
1254                 dev->nFreeTnodes--;
1255         }
1256
1257         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
1258
1259         return tn;
1260 }
1261
1262 static yaffs_Tnode *yaffs_GetTnode(yaffs_Device * dev)
1263 {
1264         yaffs_Tnode *tn = yaffs_GetTnodeRaw(dev);
1265         int tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
1266
1267         if(tnodeSize < sizeof(yaffs_Tnode))
1268                 tnodeSize = sizeof(yaffs_Tnode);
1269         
1270         if(tn)
1271                 memset(tn, 0, tnodeSize);
1272
1273         return tn;      
1274 }
1275
1276 /* FreeTnode frees up a tnode and puts it back on the free list */
1277 static void yaffs_FreeTnode(yaffs_Device * dev, yaffs_Tnode * tn)
1278 {
1279         if (tn) {
1280 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
1281                 if (tn->internal[YAFFS_NTNODES_INTERNAL] != 0) {
1282                         /* Hoosterman, this thing looks like it is already in the list */
1283                         T(YAFFS_TRACE_ALWAYS,
1284                           (TSTR("yaffs: Tnode list bug 2" TENDSTR)));
1285                 }
1286                 tn->internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
1287 #endif
1288                 tn->internal[0] = dev->freeTnodes;
1289                 dev->freeTnodes = tn;
1290                 dev->nFreeTnodes++;
1291         }
1292         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
1293         
1294 }
1295
1296 static void yaffs_DeinitialiseTnodes(yaffs_Device * dev)
1297 {
1298         /* Free the list of allocated tnodes */
1299         yaffs_TnodeList *tmp;
1300
1301         while (dev->allocatedTnodeList) {
1302                 tmp = dev->allocatedTnodeList->next;
1303
1304                 YFREE(dev->allocatedTnodeList->tnodes);
1305                 YFREE(dev->allocatedTnodeList);
1306                 dev->allocatedTnodeList = tmp;
1307
1308         }
1309
1310         dev->freeTnodes = NULL;
1311         dev->nFreeTnodes = 0;
1312 }
1313
1314 static void yaffs_InitialiseTnodes(yaffs_Device * dev)
1315 {
1316         dev->allocatedTnodeList = NULL;
1317         dev->freeTnodes = NULL;
1318         dev->nFreeTnodes = 0;
1319         dev->nTnodesCreated = 0;
1320
1321 }
1322
1323
1324 void yaffs_PutLevel0Tnode(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos, unsigned val)
1325 {
1326   __u32 *map = (__u32 *)tn;
1327   __u32 bitInMap;
1328   __u32 bitInWord;
1329   __u32 wordInMap;
1330   __u32 mask;
1331   
1332   pos &= YAFFS_TNODES_LEVEL0_MASK;
1333   val >>= dev->chunkGroupBits;
1334   
1335   bitInMap = pos * dev->tnodeWidth;
1336   wordInMap = bitInMap /32;
1337   bitInWord = bitInMap & (32 -1);
1338   
1339   mask = dev->tnodeMask << bitInWord;
1340   
1341   map[wordInMap] &= ~mask;
1342   map[wordInMap] |= (mask & (val << bitInWord));
1343   
1344   if(dev->tnodeWidth > (32-bitInWord)) {
1345     bitInWord = (32 - bitInWord);
1346     wordInMap++;;
1347     mask = dev->tnodeMask >> (/*dev->tnodeWidth -*/ bitInWord);
1348     map[wordInMap] &= ~mask;
1349     map[wordInMap] |= (mask & (val >> bitInWord));
1350   }
1351 }
1352
1353 static __u32 yaffs_GetChunkGroupBase(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos)
1354 {
1355   __u32 *map = (__u32 *)tn;
1356   __u32 bitInMap;
1357   __u32 bitInWord;
1358   __u32 wordInMap;
1359   __u32 val;
1360   
1361   pos &= YAFFS_TNODES_LEVEL0_MASK;
1362   
1363   bitInMap = pos * dev->tnodeWidth;
1364   wordInMap = bitInMap /32;
1365   bitInWord = bitInMap & (32 -1);
1366   
1367   val = map[wordInMap] >> bitInWord;
1368   
1369   if(dev->tnodeWidth > (32-bitInWord)) {
1370     bitInWord = (32 - bitInWord);
1371     wordInMap++;;
1372     val |= (map[wordInMap] << bitInWord);
1373   }
1374   
1375   val &= dev->tnodeMask;
1376   val <<= dev->chunkGroupBits;
1377   
1378   return val;
1379 }
1380
1381 /* ------------------- End of individual tnode manipulation -----------------*/
1382
1383 /* ---------Functions to manipulate the look-up tree (made up of tnodes) ------
1384  * The look up tree is represented by the top tnode and the number of topLevel
1385  * in the tree. 0 means only the level 0 tnode is in the tree.
1386  */
1387
1388 /* FindLevel0Tnode finds the level 0 tnode, if one exists. */
1389 static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device * dev,
1390                                           yaffs_FileStructure * fStruct,
1391                                           __u32 chunkId)
1392 {
1393
1394         yaffs_Tnode *tn = fStruct->top;
1395         __u32 i;
1396         int requiredTallness;
1397         int level = fStruct->topLevel;
1398
1399         /* Check sane level and chunk Id */
1400         if (level < 0 || level > YAFFS_TNODES_MAX_LEVEL) {
1401                 return NULL;
1402         }
1403
1404         if (chunkId > YAFFS_MAX_CHUNK_ID) {
1405                 return NULL;
1406         }
1407
1408         /* First check we're tall enough (ie enough topLevel) */
1409
1410         i = chunkId >> YAFFS_TNODES_LEVEL0_BITS;
1411         requiredTallness = 0;
1412         while (i) {
1413                 i >>= YAFFS_TNODES_INTERNAL_BITS;
1414                 requiredTallness++;
1415         }
1416
1417         if (requiredTallness > fStruct->topLevel) {
1418                 /* Not tall enough, so we can't find it, return NULL. */
1419                 return NULL;
1420         }
1421
1422         /* Traverse down to level 0 */
1423         while (level > 0 && tn) {
1424                 tn = tn->
1425                     internal[(chunkId >>
1426                                ( YAFFS_TNODES_LEVEL0_BITS + 
1427                                  (level - 1) *
1428                                  YAFFS_TNODES_INTERNAL_BITS)
1429                               ) &
1430                              YAFFS_TNODES_INTERNAL_MASK];
1431                 level--;
1432
1433         }
1434
1435         return tn;
1436 }
1437
1438 /* AddOrFindLevel0Tnode finds the level 0 tnode if it exists, otherwise first expands the tree.
1439  * This happens in two steps:
1440  *  1. If the tree isn't tall enough, then make it taller.
1441  *  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
1442  *
1443  * Used when modifying the tree.
1444  *
1445  *  If the tn argument is NULL, then a fresh tnode will be added otherwise the specified tn will
1446  *  be plugged into the ttree.
1447  */
1448  
1449 static yaffs_Tnode *yaffs_AddOrFindLevel0Tnode(yaffs_Device * dev,
1450                                                yaffs_FileStructure * fStruct,
1451                                                __u32 chunkId,
1452                                                yaffs_Tnode *passedTn)
1453 {
1454
1455         int requiredTallness;
1456         int i;
1457         int l;
1458         yaffs_Tnode *tn;
1459
1460         __u32 x;
1461
1462
1463         /* Check sane level and page Id */
1464         if (fStruct->topLevel < 0 || fStruct->topLevel > YAFFS_TNODES_MAX_LEVEL) {
1465                 return NULL;
1466         }
1467
1468         if (chunkId > YAFFS_MAX_CHUNK_ID) {
1469                 return NULL;
1470         }
1471
1472         /* First check we're tall enough (ie enough topLevel) */
1473
1474         x = chunkId >> YAFFS_TNODES_LEVEL0_BITS;
1475         requiredTallness = 0;
1476         while (x) {
1477                 x >>= YAFFS_TNODES_INTERNAL_BITS;
1478                 requiredTallness++;
1479         }
1480
1481
1482         if (requiredTallness > fStruct->topLevel) {
1483                 /* Not tall enough,gotta make the tree taller */
1484                 for (i = fStruct->topLevel; i < requiredTallness; i++) {
1485                 
1486                         tn = yaffs_GetTnode(dev);
1487
1488                         if (tn) {
1489                                 tn->internal[0] = fStruct->top;
1490                                 fStruct->top = tn;
1491                         } else {
1492                                 T(YAFFS_TRACE_ERROR,
1493                                   (TSTR("yaffs: no more tnodes" TENDSTR)));
1494                         }
1495                 }
1496
1497                 fStruct->topLevel = requiredTallness;
1498         }
1499
1500         /* Traverse down to level 0, adding anything we need */
1501
1502         l = fStruct->topLevel;
1503         tn = fStruct->top;
1504         
1505         if(l > 0) {
1506                 while (l > 0 && tn) {
1507                         x = (chunkId >>
1508                              ( YAFFS_TNODES_LEVEL0_BITS +
1509                               (l - 1) * YAFFS_TNODES_INTERNAL_BITS)) &
1510                             YAFFS_TNODES_INTERNAL_MASK;
1511
1512
1513                         if((l>1) && !tn->internal[x]){
1514                                 /* Add missing non-level-zero tnode */
1515                                 tn->internal[x] = yaffs_GetTnode(dev);
1516
1517                         } else if(l == 1) {
1518                                 /* Looking from level 1 at level 0 */
1519                                 if (passedTn) {
1520                                         /* If we already have one, then release it.*/
1521                                         if(tn->internal[x])
1522                                                 yaffs_FreeTnode(dev,tn->internal[x]);
1523                                         tn->internal[x] = passedTn;
1524                         
1525                                 } else if(!tn->internal[x]) {
1526                                         /* Don't have one, none passed in */
1527                                         tn->internal[x] = yaffs_GetTnode(dev);
1528                                 }
1529                         }
1530                 
1531                         tn = tn->internal[x];
1532                         l--;
1533                 }
1534         } else {
1535                 /* top is level 0 */
1536                 if(passedTn) {
1537                         memcpy(tn,passedTn,(dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8);
1538                         yaffs_FreeTnode(dev,passedTn);
1539                 }
1540         }
1541
1542         return tn;
1543 }
1544
1545 static int yaffs_FindChunkInGroup(yaffs_Device * dev, int theChunk,
1546                                   yaffs_ExtendedTags * tags, int objectId,
1547                                   int chunkInInode)
1548 {
1549         int j;
1550
1551         for (j = 0; theChunk && j < dev->chunkGroupSize; j++) {
1552                 if (yaffs_CheckChunkBit
1553                     (dev, theChunk / dev->nChunksPerBlock,
1554                      theChunk % dev->nChunksPerBlock)) {
1555                         yaffs_ReadChunkWithTagsFromNAND(dev, theChunk, NULL,
1556                                                         tags);
1557                         if (yaffs_TagsMatch(tags, objectId, chunkInInode)) {
1558                                 /* found it; */
1559                                 return theChunk;
1560
1561                         }
1562                 }
1563                 theChunk++;
1564         }
1565         return -1;
1566 }
1567
1568
1569 /* DeleteWorker scans backwards through the tnode tree and deletes all the
1570  * chunks and tnodes in the file
1571  * Returns 1 if the tree was deleted. 
1572  * Returns 0 if it stopped early due to hitting the limit and the delete is incomplete.
1573  */
1574
1575 static int yaffs_DeleteWorker(yaffs_Object * in, yaffs_Tnode * tn, __u32 level,
1576                               int chunkOffset, int *limit)
1577 {
1578         int i;
1579         int chunkInInode;
1580         int theChunk;
1581         yaffs_ExtendedTags tags;
1582         int foundChunk;
1583         yaffs_Device *dev = in->myDev;
1584
1585         int allDone = 1;
1586
1587         if (tn) {
1588                 if (level > 0) {
1589
1590                         for (i = YAFFS_NTNODES_INTERNAL - 1; allDone && i >= 0;
1591                              i--) {
1592                                 if (tn->internal[i]) {
1593                                         if (limit && (*limit) < 0) {
1594                                                 allDone = 0;
1595                                         } else {
1596                                                 allDone =
1597                                                     yaffs_DeleteWorker(in,
1598                                                                        tn->
1599                                                                        internal
1600                                                                        [i],
1601                                                                        level -
1602                                                                        1,
1603                                                                        (chunkOffset
1604                                                                         <<
1605                                                                         YAFFS_TNODES_INTERNAL_BITS)
1606                                                                        + i,
1607                                                                        limit);
1608                                         }
1609                                         if (allDone) {
1610                                                 yaffs_FreeTnode(dev,
1611                                                                 tn->
1612                                                                 internal[i]);
1613                                                 tn->internal[i] = NULL;
1614                                         }
1615                                 }
1616
1617                         }
1618                         return (allDone) ? 1 : 0;
1619                 } else if (level == 0) {
1620                         int hitLimit = 0;
1621
1622                         for (i = YAFFS_NTNODES_LEVEL0 - 1; i >= 0 && !hitLimit;
1623                              i--) {
1624                                 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
1625                                 if (theChunk) {
1626
1627                                         chunkInInode =
1628                                             (chunkOffset <<
1629                                              YAFFS_TNODES_LEVEL0_BITS) + i;
1630
1631                                         foundChunk =
1632                                             yaffs_FindChunkInGroup(dev,
1633                                                                    theChunk,
1634                                                                    &tags,
1635                                                                    in->objectId,
1636                                                                    chunkInInode);
1637
1638                                         if (foundChunk > 0) {
1639                                                 yaffs_DeleteChunk(dev,
1640                                                                   foundChunk, 1,
1641                                                                   __LINE__);
1642                                                 in->nDataChunks--;
1643                                                 if (limit) {
1644                                                         *limit = *limit - 1;
1645                                                         if (*limit <= 0) {
1646                                                                 hitLimit = 1;
1647                                                         }
1648                                                 }
1649
1650                                         }
1651
1652                                         yaffs_PutLevel0Tnode(dev,tn,i,0);
1653                                 }
1654
1655                         }
1656                         return (i < 0) ? 1 : 0;
1657
1658                 }
1659
1660         }
1661
1662         return 1;
1663
1664 }
1665
1666 static void yaffs_SoftDeleteChunk(yaffs_Device * dev, int chunk)
1667 {
1668
1669         yaffs_BlockInfo *theBlock;
1670
1671         T(YAFFS_TRACE_DELETION, (TSTR("soft delete chunk %d" TENDSTR), chunk));
1672
1673         theBlock = yaffs_GetBlockInfo(dev, chunk / dev->nChunksPerBlock);
1674         if (theBlock) {
1675                 theBlock->softDeletions++;
1676                 dev->nFreeChunks++;
1677         }
1678 }
1679
1680 /* SoftDeleteWorker scans backwards through the tnode tree and soft deletes all the chunks in the file.
1681  * All soft deleting does is increment the block's softdelete count and pulls the chunk out
1682  * of the tnode.
1683  * Thus, essentially this is the same as DeleteWorker except that the chunks are soft deleted.
1684  */
1685  
1686 static int yaffs_SoftDeleteWorker(yaffs_Object * in, yaffs_Tnode * tn,
1687                                   __u32 level, int chunkOffset)
1688 {
1689         int i;
1690         int theChunk;
1691         int allDone = 1;
1692         yaffs_Device *dev = in->myDev;
1693
1694         if (tn) {
1695                 if (level > 0) {
1696
1697                         for (i = YAFFS_NTNODES_INTERNAL - 1; allDone && i >= 0;
1698                              i--) {
1699                                 if (tn->internal[i]) {
1700                                         allDone =
1701                                             yaffs_SoftDeleteWorker(in,
1702                                                                    tn->
1703                                                                    internal[i],
1704                                                                    level - 1,
1705                                                                    (chunkOffset
1706                                                                     <<
1707                                                                     YAFFS_TNODES_INTERNAL_BITS)
1708                                                                    + i);
1709                                         if (allDone) {
1710                                                 yaffs_FreeTnode(dev,
1711                                                                 tn->
1712                                                                 internal[i]);
1713                                                 tn->internal[i] = NULL;
1714                                         } else {
1715                                                 /* Hoosterman... how could this happen? */
1716                                         }
1717                                 }
1718                         }
1719                         return (allDone) ? 1 : 0;
1720                 } else if (level == 0) {
1721
1722                         for (i = YAFFS_NTNODES_LEVEL0 - 1; i >= 0; i--) {
1723                                 theChunk = yaffs_GetChunkGroupBase(dev,tn,i);
1724                                 if (theChunk) {
1725                                         /* Note this does not find the real chunk, only the chunk group.
1726                                          * We make an assumption that a chunk group is not larger than 
1727                                          * a block.
1728                                          */
1729                                         yaffs_SoftDeleteChunk(dev, theChunk);
1730                                         yaffs_PutLevel0Tnode(dev,tn,i,0);
1731                                 }
1732
1733                         }
1734                         return 1;
1735
1736                 }
1737
1738         }
1739
1740         return 1;
1741
1742 }
1743
1744 static void yaffs_SoftDeleteFile(yaffs_Object * obj)
1745 {
1746         if (obj->deleted &&
1747             obj->variantType == YAFFS_OBJECT_TYPE_FILE && !obj->softDeleted) {
1748                 if (obj->nDataChunks <= 0) {
1749                         /* Empty file with no duplicate object headers, just delete it immediately */
1750                         yaffs_FreeTnode(obj->myDev,
1751                                         obj->variant.fileVariant.top);
1752                         obj->variant.fileVariant.top = NULL;
1753                         T(YAFFS_TRACE_TRACING,
1754                           (TSTR("yaffs: Deleting empty file %d" TENDSTR),
1755                            obj->objectId));
1756                         yaffs_DoGenericObjectDeletion(obj);
1757                 } else {
1758                         yaffs_SoftDeleteWorker(obj,
1759                                                obj->variant.fileVariant.top,
1760                                                obj->variant.fileVariant.
1761                                                topLevel, 0);
1762                         obj->softDeleted = 1;
1763                 }
1764         }
1765 }
1766
1767 /* Pruning removes any part of the file structure tree that is beyond the
1768  * bounds of the file (ie that does not point to chunks).
1769  *
1770  * A file should only get pruned when its size is reduced.
1771  *
1772  * Before pruning, the chunks must be pulled from the tree and the
1773  * level 0 tnode entries must be zeroed out.
1774  * Could also use this for file deletion, but that's probably better handled
1775  * by a special case.
1776  */
1777
1778 static yaffs_Tnode *yaffs_PruneWorker(yaffs_Device * dev, yaffs_Tnode * tn,
1779                                       __u32 level, int del0)
1780 {
1781         int i;
1782         int hasData;
1783
1784         if (tn) {
1785                 hasData = 0;
1786
1787                 for (i = 0; i < YAFFS_NTNODES_INTERNAL; i++) {
1788                         if (tn->internal[i] && level > 0) {
1789                                 tn->internal[i] =
1790                                     yaffs_PruneWorker(dev, tn->internal[i],
1791                                                       level - 1,
1792                                                       (i == 0) ? del0 : 1);
1793                         }
1794
1795                         if (tn->internal[i]) {
1796                                 hasData++;
1797                         }
1798                 }
1799
1800                 if (hasData == 0 && del0) {
1801                         /* Free and return NULL */
1802
1803                         yaffs_FreeTnode(dev, tn);
1804                         tn = NULL;
1805                 }
1806
1807         }
1808
1809         return tn;
1810
1811 }
1812
1813 static int yaffs_PruneFileStructure(yaffs_Device * dev,
1814                                     yaffs_FileStructure * fStruct)
1815 {
1816         int i;
1817         int hasData;
1818         int done = 0;
1819         yaffs_Tnode *tn;
1820
1821         if (fStruct->topLevel > 0) {
1822                 fStruct->top =
1823                     yaffs_PruneWorker(dev, fStruct->top, fStruct->topLevel, 0);
1824
1825                 /* Now we have a tree with all the non-zero branches NULL but the height
1826                  * is the same as it was.
1827                  * Let's see if we can trim internal tnodes to shorten the tree.
1828                  * We can do this if only the 0th element in the tnode is in use 
1829                  * (ie all the non-zero are NULL)
1830                  */
1831
1832                 while (fStruct->topLevel && !done) {
1833                         tn = fStruct->top;
1834
1835                         hasData = 0;
1836                         for (i = 1; i < YAFFS_NTNODES_INTERNAL; i++) {
1837                                 if (tn->internal[i]) {
1838                                         hasData++;
1839                                 }
1840                         }
1841
1842                         if (!hasData) {
1843                                 fStruct->top = tn->internal[0];
1844                                 fStruct->topLevel--;
1845                                 yaffs_FreeTnode(dev, tn);
1846                         } else {
1847                                 done = 1;
1848                         }
1849                 }
1850         }
1851
1852         return YAFFS_OK;
1853 }
1854
1855 /*-------------------- End of File Structure functions.-------------------*/
1856
1857 /* yaffs_CreateFreeObjects creates a bunch more objects and
1858  * adds them to the object free list.
1859  */
1860 static int yaffs_CreateFreeObjects(yaffs_Device * dev, int nObjects)
1861 {
1862         int i;
1863         yaffs_Object *newObjects;
1864         yaffs_ObjectList *list;
1865
1866         if (nObjects < 1)
1867                 return YAFFS_OK;
1868
1869         /* make these things */
1870         newObjects = YMALLOC(nObjects * sizeof(yaffs_Object));
1871         list = YMALLOC(sizeof(yaffs_ObjectList));
1872
1873         if (!newObjects || !list) {
1874                 if(newObjects)
1875                         YFREE(newObjects);
1876                 if(list)
1877                         YFREE(list);
1878                 T(YAFFS_TRACE_ALLOCATE,
1879                   (TSTR("yaffs: Could not allocate more objects" TENDSTR)));
1880                 return YAFFS_FAIL;
1881         }
1882         
1883         /* Hook them into the free list */
1884         for (i = 0; i < nObjects - 1; i++) {
1885                 newObjects[i].siblings.next =
1886                     (struct ylist_head *)(&newObjects[i + 1]);
1887         }
1888
1889         newObjects[nObjects - 1].siblings.next = (void *)dev->freeObjects;
1890         dev->freeObjects = newObjects;
1891         dev->nFreeObjects += nObjects;
1892         dev->nObjectsCreated += nObjects;
1893
1894         /* Now add this bunch of Objects to a list for freeing up. */
1895
1896         list->objects = newObjects;
1897         list->next = dev->allocatedObjectList;
1898         dev->allocatedObjectList = list;
1899
1900         return YAFFS_OK;
1901 }
1902
1903
1904 /* AllocateEmptyObject gets us a clean Object. Tries to make allocate more if we run out */
1905 static yaffs_Object *yaffs_AllocateEmptyObject(yaffs_Device * dev)
1906 {
1907         yaffs_Object *tn = NULL;
1908
1909 #ifdef VALGRIND_TEST
1910         tn = YMALLOC(sizeof(yaffs_Object));
1911 #else
1912         /* If there are none left make more */
1913         if (!dev->freeObjects) {
1914                 yaffs_CreateFreeObjects(dev, YAFFS_ALLOCATION_NOBJECTS);
1915         }
1916
1917         if (dev->freeObjects) {
1918                 tn = dev->freeObjects;
1919                 dev->freeObjects =
1920                     (yaffs_Object *) (dev->freeObjects->siblings.next);
1921                 dev->nFreeObjects--;
1922         }
1923 #endif
1924         if(tn){
1925                 /* Now sweeten it up... */
1926
1927                 memset(tn, 0, sizeof(yaffs_Object));
1928                 tn->myDev = dev;
1929                 tn->hdrChunk = 0;
1930                 tn->variantType = YAFFS_OBJECT_TYPE_UNKNOWN;
1931                 YINIT_LIST_HEAD(&(tn->hardLinks));
1932                 YINIT_LIST_HEAD(&(tn->hashLink));
1933                 YINIT_LIST_HEAD(&tn->siblings);
1934                 
1935
1936                 /* Now make the directory sane */
1937                 if(dev->rootDir){
1938                         tn->parent = dev->rootDir;
1939                         ylist_add(&(tn->siblings),&dev->rootDir->variant.directoryVariant.children);
1940                 }
1941
1942                 /* Add it to the lost and found directory.
1943                  * NB Can't put root or lostNFound in lostNFound so
1944                  * check if lostNFound exists first
1945                  */
1946                 if (dev->lostNFoundDir) {
1947                         yaffs_AddObjectToDirectory(dev->lostNFoundDir, tn);
1948                 }
1949         }
1950         
1951         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
1952
1953         return tn;
1954 }
1955
1956 static yaffs_Object *yaffs_CreateFakeDirectory(yaffs_Device * dev, int number,
1957                                                __u32 mode)
1958 {
1959
1960         yaffs_Object *obj =
1961             yaffs_CreateNewObject(dev, number, YAFFS_OBJECT_TYPE_DIRECTORY);
1962         if (obj) {
1963                 obj->fake = 1;          /* it is fake so it might have no NAND presence... */
1964                 obj->renameAllowed = 0; /* ... and we're not allowed to rename it... */
1965                 obj->unlinkAllowed = 0; /* ... or unlink it */
1966                 obj->deleted = 0;
1967                 obj->unlinked = 0;
1968                 obj->yst_mode = mode;
1969                 obj->myDev = dev;
1970                 obj->hdrChunk = 0;      /* Not a valid chunk. */
1971         }
1972
1973         return obj;
1974
1975 }
1976
1977 static void yaffs_UnhashObject(yaffs_Object * tn)
1978 {
1979         int bucket;
1980         yaffs_Device *dev = tn->myDev;
1981
1982         /* If it is still linked into the bucket list, free from the list */
1983         if (!ylist_empty(&tn->hashLink)) {
1984                 ylist_del_init(&tn->hashLink);
1985                 bucket = yaffs_HashFunction(tn->objectId);
1986                 dev->objectBucket[bucket].count--;
1987         }
1988
1989 }
1990
1991 /*  FreeObject frees up a Object and puts it back on the free list */
1992 static void yaffs_FreeObject(yaffs_Object * tn)
1993 {
1994
1995         yaffs_Device *dev = tn->myDev;
1996
1997         
1998         if(tn->parent)
1999                 YBUG();
2000         if(!ylist_empty(&tn->siblings))
2001                 YBUG();
2002
2003
2004 #ifdef  __KERNEL__
2005         if (tn->myInode) {
2006                 /* We're still hooked up to a cached inode.
2007                  * Don't delete now, but mark for later deletion
2008                  */
2009                 tn->deferedFree = 1;
2010                 return;
2011         }
2012 #endif
2013
2014         yaffs_UnhashObject(tn);
2015
2016 #ifdef VALGRIND_TEST
2017         YFREE(tn);
2018 #else
2019         /* Link into the free list. */
2020         tn->siblings.next = (struct ylist_head *)(dev->freeObjects);
2021         dev->freeObjects = tn;
2022         dev->nFreeObjects++;
2023 #endif
2024         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
2025
2026 }
2027
2028 #ifdef __KERNEL__
2029
2030 void yaffs_HandleDeferedFree(yaffs_Object * obj)
2031 {
2032         if (obj->deferedFree) {
2033                 yaffs_FreeObject(obj);
2034         }
2035 }
2036
2037 #endif
2038
2039 static void yaffs_DeinitialiseObjects(yaffs_Device * dev)
2040 {
2041         /* Free the list of allocated Objects */
2042
2043         yaffs_ObjectList *tmp;
2044
2045         while (dev->allocatedObjectList) {
2046                 tmp = dev->allocatedObjectList->next;
2047                 YFREE(dev->allocatedObjectList->objects);
2048                 YFREE(dev->allocatedObjectList);
2049
2050                 dev->allocatedObjectList = tmp;
2051         }
2052
2053         dev->freeObjects = NULL;
2054         dev->nFreeObjects = 0;
2055 }
2056
2057 static void yaffs_InitialiseObjects(yaffs_Device * dev)
2058 {
2059         int i;
2060
2061         dev->allocatedObjectList = NULL;
2062         dev->freeObjects = NULL;
2063         dev->nFreeObjects = 0;
2064
2065         for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) {
2066                 YINIT_LIST_HEAD(&dev->objectBucket[i].list);
2067                 dev->objectBucket[i].count = 0;
2068         }
2069
2070 }
2071
2072 static int yaffs_FindNiceObjectBucket(yaffs_Device * dev)
2073 {
2074         static int x = 0;
2075         int i;
2076         int l = 999;
2077         int lowest = 999999;
2078
2079         /* First let's see if we can find one that's empty. */
2080
2081         for (i = 0; i < 10 && lowest > 0; i++) {
2082                 x++;
2083                 x %= YAFFS_NOBJECT_BUCKETS;
2084                 if (dev->objectBucket[x].count < lowest) {
2085                         lowest = dev->objectBucket[x].count;
2086                         l = x;
2087                 }
2088
2089         }
2090
2091         /* If we didn't find an empty list, then try
2092          * looking a bit further for a short one
2093          */
2094
2095         for (i = 0; i < 10 && lowest > 3; i++) {
2096                 x++;
2097                 x %= YAFFS_NOBJECT_BUCKETS;
2098                 if (dev->objectBucket[x].count < lowest) {
2099                         lowest = dev->objectBucket[x].count;
2100                         l = x;
2101                 }
2102
2103         }
2104
2105         return l;
2106 }
2107
2108 static int yaffs_CreateNewObjectNumber(yaffs_Device * dev)
2109 {
2110         int bucket = yaffs_FindNiceObjectBucket(dev);
2111
2112         /* Now find an object value that has not already been taken
2113          * by scanning the list.
2114          */
2115
2116         int found = 0;
2117         struct ylist_head *i;
2118
2119         __u32 n = (__u32) bucket;
2120
2121         /* yaffs_CheckObjectHashSanity();  */
2122
2123         while (!found) {
2124                 found = 1;
2125                 n += YAFFS_NOBJECT_BUCKETS;
2126                 if (1 || dev->objectBucket[bucket].count > 0) {
2127                         ylist_for_each(i, &dev->objectBucket[bucket].list) {
2128                                 /* If there is already one in the list */
2129                                 if (i
2130                                     && ylist_entry(i, yaffs_Object,
2131                                                   hashLink)->objectId == n) {
2132                                         found = 0;
2133                                 }
2134                         }
2135                 }
2136         }
2137
2138
2139         return n;
2140 }
2141
2142 static void yaffs_HashObject(yaffs_Object * in)
2143 {
2144         int bucket = yaffs_HashFunction(in->objectId);
2145         yaffs_Device *dev = in->myDev;
2146
2147         ylist_add(&in->hashLink, &dev->objectBucket[bucket].list);
2148         dev->objectBucket[bucket].count++;
2149
2150 }
2151
2152 yaffs_Object *yaffs_FindObjectByNumber(yaffs_Device * dev, __u32 number)
2153 {
2154         int bucket = yaffs_HashFunction(number);
2155         struct ylist_head *i;
2156         yaffs_Object *in;
2157
2158         ylist_for_each(i, &dev->objectBucket[bucket].list) {
2159                 /* Look if it is in the list */
2160                 if (i) {
2161                         in = ylist_entry(i, yaffs_Object, hashLink);
2162                         if (in->objectId == number) {
2163 #ifdef __KERNEL__
2164                                 /* Don't tell the VFS about this one if it is defered free */
2165                                 if (in->deferedFree)
2166                                         return NULL;
2167 #endif
2168
2169                                 return in;
2170                         }
2171                 }
2172         }
2173
2174         return NULL;
2175 }
2176
2177 yaffs_Object *yaffs_CreateNewObject(yaffs_Device * dev, int number,
2178                                     yaffs_ObjectType type)
2179 {
2180
2181         yaffs_Object *theObject;
2182         yaffs_Tnode *tn = NULL;
2183
2184         if (number < 0) {
2185                 number = yaffs_CreateNewObjectNumber(dev);
2186         }
2187
2188         theObject = yaffs_AllocateEmptyObject(dev);
2189         if(!theObject)
2190                 return NULL;
2191                 
2192         if(type == YAFFS_OBJECT_TYPE_FILE){
2193                 tn = yaffs_GetTnode(dev);
2194                 if(!tn){
2195                         yaffs_FreeObject(theObject);
2196                         return NULL;
2197                 }
2198         }
2199                 
2200         
2201
2202         if (theObject) {
2203                 theObject->fake = 0;
2204                 theObject->renameAllowed = 1;
2205                 theObject->unlinkAllowed = 1;
2206                 theObject->objectId = number;
2207                 yaffs_HashObject(theObject);
2208                 theObject->variantType = type;
2209 #ifdef CONFIG_YAFFS_WINCE
2210                 yfsd_WinFileTimeNow(theObject->win_atime);
2211                 theObject->win_ctime[0] = theObject->win_mtime[0] =
2212                     theObject->win_atime[0];
2213                 theObject->win_ctime[1] = theObject->win_mtime[1] =
2214                     theObject->win_atime[1];
2215
2216 #else
2217
2218                 theObject->yst_atime = theObject->yst_mtime =
2219                     theObject->yst_ctime = Y_CURRENT_TIME;
2220 #endif
2221
2222 #if 0
2223                 theObject->sum_prev = 12345;
2224                 theObject->sum_trailer = 6789;
2225 #endif
2226
2227                 switch (type) {
2228                 case YAFFS_OBJECT_TYPE_FILE:
2229                         theObject->variant.fileVariant.fileSize = 0;
2230                         theObject->variant.fileVariant.scannedFileSize = 0;
2231                         theObject->variant.fileVariant.shrinkSize = 0xFFFFFFFF; /* max __u32 */
2232                         theObject->variant.fileVariant.topLevel = 0;
2233                         theObject->variant.fileVariant.top = tn;
2234                         break;
2235                 case YAFFS_OBJECT_TYPE_DIRECTORY:
2236                         YINIT_LIST_HEAD(&theObject->variant.directoryVariant.
2237                                        children);
2238                         break;
2239                 case YAFFS_OBJECT_TYPE_SYMLINK:
2240                 case YAFFS_OBJECT_TYPE_HARDLINK:
2241                 case YAFFS_OBJECT_TYPE_SPECIAL:
2242                         /* No action required */
2243                         break;
2244                 case YAFFS_OBJECT_TYPE_UNKNOWN:
2245                         /* todo this should not happen */
2246                         break;
2247                 }
2248         }
2249
2250         return theObject;
2251 }
2252
2253 static yaffs_Object *yaffs_FindOrCreateObjectByNumber(yaffs_Device * dev,
2254                                                       int number,
2255                                                       yaffs_ObjectType type)
2256 {
2257         yaffs_Object *theObject = NULL;
2258
2259         if (number > 0) {
2260                 theObject = yaffs_FindObjectByNumber(dev, number);
2261         }
2262
2263         if (!theObject) {
2264                 theObject = yaffs_CreateNewObject(dev, number, type);
2265         }
2266
2267         return theObject;
2268
2269 }
2270                         
2271
2272 static YCHAR *yaffs_CloneString(const YCHAR * str)
2273 {
2274         YCHAR *newStr = NULL;
2275
2276         if (str && *str) {
2277                 newStr = YMALLOC((yaffs_strlen(str) + 1) * sizeof(YCHAR));
2278                 if(newStr)
2279                         yaffs_strcpy(newStr, str);
2280         }
2281
2282         return newStr;
2283
2284 }
2285
2286 /*
2287  * Mknod (create) a new object.
2288  * equivalentObject only has meaning for a hard link;
2289  * aliasString only has meaning for a sumlink.
2290  * rdev only has meaning for devices (a subset of special objects)
2291  */
2292  
2293 static yaffs_Object *yaffs_MknodObject(yaffs_ObjectType type,
2294                                        yaffs_Object * parent,
2295                                        const YCHAR * name,
2296                                        __u32 mode,
2297                                        __u32 uid,
2298                                        __u32 gid,
2299                                        yaffs_Object * equivalentObject,
2300                                        const YCHAR * aliasString, __u32 rdev)
2301 {
2302         yaffs_Object *in;
2303         YCHAR *str = NULL;
2304
2305         yaffs_Device *dev = parent->myDev;
2306
2307         /* Check if the entry exists. If it does then fail the call since we don't want a dup.*/
2308         if (yaffs_FindObjectByName(parent, name)) {
2309                 return NULL;
2310         }
2311
2312         in = yaffs_CreateNewObject(dev, -1, type);
2313
2314         if(!in)
2315                 return YAFFS_FAIL;
2316         
2317         if(type == YAFFS_OBJECT_TYPE_SYMLINK){
2318                 str = yaffs_CloneString(aliasString);
2319                 if(!str){
2320                         yaffs_FreeObject(in);
2321                         return NULL;
2322                 }
2323         }
2324         
2325         
2326
2327         if (in) {
2328                 in->hdrChunk = 0;
2329                 in->valid = 1;
2330                 in->variantType = type;
2331
2332                 in->yst_mode = mode;
2333
2334 #ifdef CONFIG_YAFFS_WINCE
2335                 yfsd_WinFileTimeNow(in->win_atime);
2336                 in->win_ctime[0] = in->win_mtime[0] = in->win_atime[0];
2337                 in->win_ctime[1] = in->win_mtime[1] = in->win_atime[1];
2338
2339 #else
2340                 in->yst_atime = in->yst_mtime = in->yst_ctime = Y_CURRENT_TIME;
2341
2342                 in->yst_rdev = rdev;
2343                 in->yst_uid = uid;
2344                 in->yst_gid = gid;
2345 #endif
2346                 in->nDataChunks = 0;
2347
2348                 yaffs_SetObjectName(in, name);
2349                 in->dirty = 1;
2350
2351                 yaffs_AddObjectToDirectory(parent, in);
2352
2353                 in->myDev = parent->myDev;
2354
2355                 switch (type) {
2356                 case YAFFS_OBJECT_TYPE_SYMLINK:
2357                         in->variant.symLinkVariant.alias = str;
2358                         break;
2359                 case YAFFS_OBJECT_TYPE_HARDLINK:
2360                         in->variant.hardLinkVariant.equivalentObject =
2361                             equivalentObject;
2362                         in->variant.hardLinkVariant.equivalentObjectId =
2363                             equivalentObject->objectId;
2364                         ylist_add(&in->hardLinks, &equivalentObject->hardLinks);
2365                         break;
2366                 case YAFFS_OBJECT_TYPE_FILE:    
2367                 case YAFFS_OBJECT_TYPE_DIRECTORY:
2368                 case YAFFS_OBJECT_TYPE_SPECIAL:
2369                 case YAFFS_OBJECT_TYPE_UNKNOWN:
2370                         /* do nothing */
2371                         break;
2372                 }
2373
2374                 if (yaffs_UpdateObjectHeader(in, name, 0, 0, 0) < 0) {
2375                         /* Could not create the object header, fail the creation */
2376                         yaffs_DestroyObject(in);
2377                         in = NULL;
2378                 }
2379
2380         }
2381
2382         return in;
2383 }
2384
2385 yaffs_Object *yaffs_MknodFile(yaffs_Object * parent, const YCHAR * name,
2386                               __u32 mode, __u32 uid, __u32 gid)
2387 {
2388         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_FILE, parent, name, mode,
2389                                  uid, gid, NULL, NULL, 0);
2390 }
2391
2392 yaffs_Object *yaffs_MknodDirectory(yaffs_Object * parent, const YCHAR * name,
2393                                    __u32 mode, __u32 uid, __u32 gid)
2394 {
2395         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_DIRECTORY, parent, name,
2396                                  mode, uid, gid, NULL, NULL, 0);
2397 }
2398
2399 yaffs_Object *yaffs_MknodSpecial(yaffs_Object * parent, const YCHAR * name,
2400                                  __u32 mode, __u32 uid, __u32 gid, __u32 rdev)
2401 {
2402         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SPECIAL, parent, name, mode,
2403                                  uid, gid, NULL, NULL, rdev);
2404 }
2405
2406 yaffs_Object *yaffs_MknodSymLink(yaffs_Object * parent, const YCHAR * name,
2407                                  __u32 mode, __u32 uid, __u32 gid,
2408                                  const YCHAR * alias)
2409 {
2410         return yaffs_MknodObject(YAFFS_OBJECT_TYPE_SYMLINK, parent, name, mode,
2411                                  uid, gid, NULL, alias, 0);
2412 }
2413
2414 /* yaffs_Link returns the object id of the equivalent object.*/
2415 yaffs_Object *yaffs_Link(yaffs_Object * parent, const YCHAR * name,
2416                          yaffs_Object * equivalentObject)
2417 {
2418         /* Get the real object in case we were fed a hard link as an equivalent object */
2419         equivalentObject = yaffs_GetEquivalentObject(equivalentObject);
2420
2421         if (yaffs_MknodObject
2422             (YAFFS_OBJECT_TYPE_HARDLINK, parent, name, 0, 0, 0,
2423              equivalentObject, NULL, 0)) {
2424                 return equivalentObject;
2425         } else {
2426                 return NULL;
2427         }
2428
2429 }
2430
2431 static int yaffs_ChangeObjectName(yaffs_Object * obj, yaffs_Object * newDir,
2432                                   const YCHAR * newName, int force, int shadows)
2433 {
2434         int unlinkOp;
2435         int deleteOp;
2436
2437         yaffs_Object *existingTarget;
2438
2439         if (newDir == NULL) {
2440                 newDir = obj->parent;   /* use the old directory */
2441         }
2442
2443         if (newDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
2444                 T(YAFFS_TRACE_ALWAYS,
2445                   (TSTR
2446                    ("tragedy: yaffs_ChangeObjectName: newDir is not a directory"
2447                     TENDSTR)));
2448                 YBUG();
2449         }
2450         
2451         /* TODO: Do we need this different handling for YAFFS2 and YAFFS1?? */
2452         if (obj->myDev->isYaffs2) {
2453                 unlinkOp = (newDir == obj->myDev->unlinkedDir);
2454         } else {
2455                 unlinkOp = (newDir == obj->myDev->unlinkedDir
2456                             && obj->variantType == YAFFS_OBJECT_TYPE_FILE);
2457         }
2458
2459         deleteOp = (newDir == obj->myDev->deletedDir);
2460
2461         existingTarget = yaffs_FindObjectByName(newDir, newName);
2462
2463         /* If the object is a file going into the unlinked directory, 
2464          *   then it is OK to just stuff it in since duplicate names are allowed.
2465          *   else only proceed if the new name does not exist and if we're putting 
2466          *   it into a directory.
2467          */
2468         if ((unlinkOp ||
2469              deleteOp ||
2470              force ||
2471              (shadows > 0) ||
2472              !existingTarget) &&
2473             newDir->variantType == YAFFS_OBJECT_TYPE_DIRECTORY) {
2474                 yaffs_SetObjectName(obj, newName);
2475                 obj->dirty = 1;
2476
2477                 yaffs_AddObjectToDirectory(newDir, obj);
2478
2479                 if (unlinkOp)
2480                         obj->unlinked = 1;
2481
2482                 /* If it is a deletion then we mark it as a shrink for gc purposes. */
2483                 if (yaffs_UpdateObjectHeader(obj, newName, 0, deleteOp, shadows)>= 0)
2484                         return YAFFS_OK;
2485         }
2486
2487         return YAFFS_FAIL;
2488 }
2489
2490 int yaffs_RenameObject(yaffs_Object * oldDir, const YCHAR * oldName,
2491                        yaffs_Object * newDir, const YCHAR * newName)
2492 {
2493         yaffs_Object *obj=NULL;
2494         yaffs_Object *existingTarget=NULL;
2495         int force = 0;
2496         
2497         
2498         if(!oldDir || oldDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
2499                 YBUG();
2500         if(!newDir || newDir->variantType != YAFFS_OBJECT_TYPE_DIRECTORY)
2501                 YBUG();
2502
2503 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
2504         /* Special case for case insemsitive systems (eg. WinCE).
2505          * While look-up is case insensitive, the name isn't.
2506          * Therefore we might want to change x.txt to X.txt
2507         */
2508         if (oldDir == newDir && yaffs_strcmp(oldName, newName) == 0) {
2509                 force = 1;
2510         }
2511 #endif
2512
2513         else if (yaffs_strlen(newName) > YAFFS_MAX_NAME_LENGTH)
2514           /* ENAMETOOLONG */
2515           return YAFFS_FAIL;
2516
2517         obj = yaffs_FindObjectByName(oldDir, oldName);
2518
2519         if (obj && obj->renameAllowed) {
2520
2521                 /* Now do the handling for an existing target, if there is one */
2522
2523                 existingTarget = yaffs_FindObjectByName(newDir, newName);
2524                 if (existingTarget &&
2525                     existingTarget->variantType == YAFFS_OBJECT_TYPE_DIRECTORY &&
2526                     !ylist_empty(&existingTarget->variant.directoryVariant.children)) {
2527                         /* There is a target that is a non-empty directory, so we fail */
2528                         return YAFFS_FAIL;      /* EEXIST or ENOTEMPTY */
2529                 } else if (existingTarget && existingTarget != obj) {
2530                         /* Nuke the target first, using shadowing, 
2531                          * but only if it isn't the same object
2532                          */
2533                         yaffs_ChangeObjectName(obj, newDir, newName, force,
2534                                                existingTarget->objectId);
2535                         yaffs_UnlinkObject(existingTarget);
2536                 }
2537
2538                 return yaffs_ChangeObjectName(obj, newDir, newName, 1, 0);
2539         }
2540         return YAFFS_FAIL;
2541 }
2542
2543 /*------------------------- Block Management and Page Allocation ----------------*/
2544
2545 static int yaffs_InitialiseBlocks(yaffs_Device * dev)
2546 {
2547         int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
2548         
2549         dev->blockInfo = NULL;
2550         dev->chunkBits = NULL;
2551         
2552         dev->allocationBlock = -1;      /* force it to get a new one */
2553
2554         /* If the first allocation strategy fails, thry the alternate one */
2555         dev->blockInfo = YMALLOC(nBlocks * sizeof(yaffs_BlockInfo));
2556         if(!dev->blockInfo){
2557                 dev->blockInfo = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockInfo));
2558                 dev->blockInfoAlt = 1;
2559         }
2560         else
2561                 dev->blockInfoAlt = 0;
2562                 
2563         if(dev->blockInfo){
2564         
2565                 /* Set up dynamic blockinfo stuff. */
2566                 dev->chunkBitmapStride = (dev->nChunksPerBlock + 7) / 8; /* round up bytes */
2567                 dev->chunkBits = YMALLOC(dev->chunkBitmapStride * nBlocks);
2568                 if(!dev->chunkBits){
2569                         dev->chunkBits = YMALLOC_ALT(dev->chunkBitmapStride * nBlocks);
2570                         dev->chunkBitsAlt = 1;
2571                 }
2572                 else
2573                         dev->chunkBitsAlt = 0;
2574         }
2575         
2576         if (dev->blockInfo && dev->chunkBits) {
2577                 memset(dev->blockInfo, 0, nBlocks * sizeof(yaffs_BlockInfo));
2578                 memset(dev->chunkBits, 0, dev->chunkBitmapStride * nBlocks);
2579                 return YAFFS_OK;
2580         }
2581
2582         return YAFFS_FAIL;
2583
2584 }
2585
2586 static void yaffs_DeinitialiseBlocks(yaffs_Device * dev)
2587 {
2588         if(dev->blockInfoAlt && dev->blockInfo)
2589                 YFREE_ALT(dev->blockInfo);
2590         else if(dev->blockInfo)
2591                 YFREE(dev->blockInfo);
2592
2593         dev->blockInfoAlt = 0;
2594
2595         dev->blockInfo = NULL;
2596         
2597         if(dev->chunkBitsAlt && dev->chunkBits)
2598                 YFREE_ALT(dev->chunkBits);
2599         else if(dev->chunkBits)
2600                 YFREE(dev->chunkBits);
2601         dev->chunkBitsAlt = 0;
2602         dev->chunkBits = NULL;
2603 }
2604
2605 static int yaffs_BlockNotDisqualifiedFromGC(yaffs_Device * dev,
2606                                             yaffs_BlockInfo * bi)
2607 {
2608         int i;
2609         __u32 seq;
2610         yaffs_BlockInfo *b;
2611
2612         if (!dev->isYaffs2)
2613                 return 1;       /* disqualification only applies to yaffs2. */
2614
2615         if (!bi->hasShrinkHeader)
2616                 return 1;       /* can gc */
2617
2618         /* Find the oldest dirty sequence number if we don't know it and save it
2619          * so we don't have to keep recomputing it.
2620          */
2621         if (!dev->oldestDirtySequence) {
2622                 seq = dev->sequenceNumber;
2623
2624                 for (i = dev->internalStartBlock; i <= dev->internalEndBlock;
2625                      i++) {
2626                         b = yaffs_GetBlockInfo(dev, i);
2627                         if (b->blockState == YAFFS_BLOCK_STATE_FULL &&
2628                             (b->pagesInUse - b->softDeletions) <
2629                             dev->nChunksPerBlock && b->sequenceNumber < seq) {
2630                                 seq = b->sequenceNumber;
2631                         }
2632                 }
2633                 dev->oldestDirtySequence = seq;
2634         }
2635
2636         /* Can't do gc of this block if there are any blocks older than this one that have
2637          * discarded pages.
2638          */
2639         return (bi->sequenceNumber <= dev->oldestDirtySequence);
2640
2641 }
2642
2643 /* FindDiretiestBlock is used to select the dirtiest block (or close enough)
2644  * for garbage collection.
2645  */
2646
2647 static int yaffs_FindBlockForGarbageCollection(yaffs_Device * dev,
2648                                                int aggressive)
2649 {
2650
2651         int b = dev->currentDirtyChecker;
2652
2653         int i;
2654         int iterations;
2655         int dirtiest = -1;
2656         int pagesInUse = 0;
2657         int prioritised=0;
2658         yaffs_BlockInfo *bi;
2659         int pendingPrioritisedExist = 0;
2660         
2661         /* First let's see if we need to grab a prioritised block */
2662         if(dev->hasPendingPrioritisedGCs){
2663                 for(i = dev->internalStartBlock; i < dev->internalEndBlock && !prioritised; i++){
2664
2665                         bi = yaffs_GetBlockInfo(dev, i);
2666                         //yaffs_VerifyBlock(dev,bi,i);
2667                         
2668                         if(bi->gcPrioritise) {
2669                                 pendingPrioritisedExist = 1;
2670                                 if(bi->blockState == YAFFS_BLOCK_STATE_FULL &&
2671                                    yaffs_BlockNotDisqualifiedFromGC(dev, bi)){
2672                                         pagesInUse = (bi->pagesInUse - bi->softDeletions);
2673                                         dirtiest = i;
2674                                         prioritised = 1;
2675                                         aggressive = 1; /* Fool the non-aggressive skip logiv below */
2676                                 }
2677                         }
2678                 }
2679                 
2680                 if(!pendingPrioritisedExist) /* None found, so we can clear this */
2681                         dev->hasPendingPrioritisedGCs = 0;
2682         }
2683
2684         /* If we're doing aggressive GC then we are happy to take a less-dirty block, and
2685          * search harder.
2686          * else (we're doing a leasurely gc), then we only bother to do this if the
2687          * block has only a few pages in use.
2688          */
2689
2690         dev->nonAggressiveSkip--;
2691
2692         if (!aggressive && (dev->nonAggressiveSkip > 0)) {
2693                 return -1;
2694         }
2695
2696         if(!prioritised)
2697                 pagesInUse =
2698                         (aggressive) ? dev->nChunksPerBlock : YAFFS_PASSIVE_GC_CHUNKS + 1;
2699
2700         if (aggressive) {
2701                 iterations =
2702                     dev->internalEndBlock - dev->internalStartBlock + 1;
2703         } else {
2704                 iterations =
2705                     dev->internalEndBlock - dev->internalStartBlock + 1;
2706                 iterations = iterations / 16;
2707                 if (iterations > 200) {
2708                         iterations = 200;
2709                 }
2710         }
2711
2712         for (i = 0; i <= iterations && pagesInUse > 0 && !prioritised; i++) {
2713                 b++;
2714                 if (b < dev->internalStartBlock || b > dev->internalEndBlock) {
2715                         b = dev->internalStartBlock;
2716                 }
2717
2718                 if (b < dev->internalStartBlock || b > dev->internalEndBlock) {
2719                         T(YAFFS_TRACE_ERROR,
2720                           (TSTR("**>> Block %d is not valid" TENDSTR), b));
2721                         YBUG();
2722                 }
2723
2724                 bi = yaffs_GetBlockInfo(dev, b);
2725
2726 #if 0
2727                 if (bi->blockState == YAFFS_BLOCK_STATE_CHECKPOINT) {
2728                         dirtiest = b;
2729                         pagesInUse = 0;
2730                 }
2731                 else 
2732 #endif
2733
2734                 if (bi->blockState == YAFFS_BLOCK_STATE_FULL &&
2735                        (bi->pagesInUse - bi->softDeletions) < pagesInUse &&
2736                         yaffs_BlockNotDisqualifiedFromGC(dev, bi)) {
2737                         dirtiest = b;
2738                         pagesInUse = (bi->pagesInUse - bi->softDeletions);
2739                 }
2740         }
2741
2742         dev->currentDirtyChecker = b;
2743
2744         if (dirtiest > 0) {
2745                 T(YAFFS_TRACE_GC,
2746                   (TSTR("GC Selected block %d with %d free, prioritised:%d" TENDSTR), dirtiest,
2747                    dev->nChunksPerBlock - pagesInUse,prioritised));
2748         }
2749
2750         dev->oldestDirtySequence = 0;
2751
2752         if (dirtiest > 0) {
2753                 dev->nonAggressiveSkip = 4;
2754         }
2755
2756         return dirtiest;
2757 }
2758
2759 static void yaffs_BlockBecameDirty(yaffs_Device * dev, int blockNo)
2760 {
2761         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockNo);
2762
2763         int erasedOk = 0;
2764
2765         /* If the block is still healthy erase it and mark as clean.
2766          * If the block has had a data failure, then retire it.
2767          */
2768          
2769         T(YAFFS_TRACE_GC | YAFFS_TRACE_ERASE,
2770                 (TSTR("yaffs_BlockBecameDirty block %d state %d %s"TENDSTR),
2771                 blockNo, bi->blockState, (bi->needsRetiring) ? "needs retiring" : ""));
2772                 
2773         bi->blockState = YAFFS_BLOCK_STATE_DIRTY;
2774
2775         if (!bi->needsRetiring) {
2776                 yaffs_InvalidateCheckpoint(dev);
2777                 erasedOk = yaffs_EraseBlockInNAND(dev, blockNo);
2778                 if (!erasedOk) {
2779                         dev->nErasureFailures++;
2780                         T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
2781                           (TSTR("**>> Erasure failed %d" TENDSTR), blockNo));
2782                 }
2783         }
2784
2785         if (erasedOk && 
2786             ((yaffs_traceMask & YAFFS_TRACE_ERASE) || !yaffs_SkipVerification(dev))) {
2787                 int i;
2788                 for (i = 0; i < dev->nChunksPerBlock; i++) {
2789                         if (!yaffs_CheckChunkErased
2790                             (dev, blockNo * dev->nChunksPerBlock + i)) {
2791                                 T(YAFFS_TRACE_ERROR,
2792                                   (TSTR
2793                                    (">>Block %d erasure supposedly OK, but chunk %d not erased"
2794                                     TENDSTR), blockNo, i));
2795                         }
2796                 }
2797         }
2798
2799         if (erasedOk) {
2800                 /* Clean it up... */
2801                 bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
2802                 dev->nErasedBlocks++;
2803                 bi->pagesInUse = 0;
2804                 bi->softDeletions = 0;
2805                 bi->hasShrinkHeader = 0;
2806                 bi->skipErasedCheck = 1;  /* This is clean, so no need to check */
2807                 bi->gcPrioritise = 0;
2808                 yaffs_ClearChunkBits(dev, blockNo);
2809
2810                 T(YAFFS_TRACE_ERASE,
2811                   (TSTR("Erased block %d" TENDSTR), blockNo));
2812         } else {
2813                 dev->nFreeChunks -= dev->nChunksPerBlock;       /* We lost a block of free space */
2814
2815                 yaffs_RetireBlock(dev, blockNo);
2816                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
2817                   (TSTR("**>> Block %d retired" TENDSTR), blockNo));
2818         }
2819 }
2820
2821 static int yaffs_FindBlockForAllocation(yaffs_Device * dev)
2822 {
2823         int i;
2824
2825         yaffs_BlockInfo *bi;
2826
2827         if (dev->nErasedBlocks < 1) {
2828                 /* Hoosterman we've got a problem.
2829                  * Can't get space to gc
2830                  */
2831                 T(YAFFS_TRACE_ERROR,
2832                   (TSTR("yaffs tragedy: no more erased blocks" TENDSTR)));
2833
2834                 return -1;
2835         }
2836         
2837         /* Find an empty block. */
2838
2839         for (i = dev->internalStartBlock; i <= dev->internalEndBlock; i++) {
2840                 dev->allocationBlockFinder++;
2841                 if (dev->allocationBlockFinder < dev->internalStartBlock
2842                     || dev->allocationBlockFinder > dev->internalEndBlock) {
2843                         dev->allocationBlockFinder = dev->internalStartBlock;
2844                 }
2845
2846                 bi = yaffs_GetBlockInfo(dev, dev->allocationBlockFinder);
2847
2848                 if (bi->blockState == YAFFS_BLOCK_STATE_EMPTY) {
2849                         bi->blockState = YAFFS_BLOCK_STATE_ALLOCATING;
2850                         dev->sequenceNumber++;
2851                         bi->sequenceNumber = dev->sequenceNumber;
2852                         dev->nErasedBlocks--;
2853                         T(YAFFS_TRACE_ALLOCATE,
2854                           (TSTR("Allocated block %d, seq  %d, %d left" TENDSTR),
2855                            dev->allocationBlockFinder, dev->sequenceNumber,
2856                            dev->nErasedBlocks));
2857                         return dev->allocationBlockFinder;
2858                 }
2859         }
2860
2861         T(YAFFS_TRACE_ALWAYS,
2862           (TSTR
2863            ("yaffs tragedy: no more erased blocks, but there should have been %d"
2864             TENDSTR), dev->nErasedBlocks));
2865
2866         return -1;
2867 }
2868
2869
2870
2871 static int yaffs_CalcCheckpointBlocksRequired(yaffs_Device *dev)
2872 {
2873         if(!dev->nCheckpointBlocksRequired &&
2874            dev->isYaffs2){
2875                 /* Not a valid value so recalculate */
2876                 int nBytes = 0;
2877                 int nBlocks;
2878                 int devBlocks = (dev->endBlock - dev->startBlock + 1);
2879                 int tnodeSize;
2880
2881                 tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
2882
2883                 if(tnodeSize < sizeof(yaffs_Tnode))
2884                         tnodeSize = sizeof(yaffs_Tnode);
2885                 
2886                 nBytes += sizeof(yaffs_CheckpointValidity);
2887                 nBytes += sizeof(yaffs_CheckpointDevice);
2888                 nBytes += devBlocks * sizeof(yaffs_BlockInfo);
2889                 nBytes += devBlocks * dev->chunkBitmapStride;
2890                 nBytes += (sizeof(yaffs_CheckpointObject) + sizeof(__u32)) * (dev->nObjectsCreated - dev->nFreeObjects);
2891                 nBytes += (tnodeSize + sizeof(__u32)) * (dev->nTnodesCreated - dev->nFreeTnodes);
2892                 nBytes += sizeof(yaffs_CheckpointValidity);
2893                 nBytes += sizeof(__u32); /* checksum*/
2894         
2895                 /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
2896         
2897                 nBlocks = (nBytes/(dev->nDataBytesPerChunk * dev->nChunksPerBlock)) + 3;
2898         
2899                 dev->nCheckpointBlocksRequired = nBlocks;
2900         }
2901
2902         return dev->nCheckpointBlocksRequired;
2903 }
2904
2905 // Check if there's space to allocate...
2906 // Thinks.... do we need top make this ths same as yaffs_GetFreeChunks()?
2907 static int yaffs_CheckSpaceForAllocation(yaffs_Device * dev)
2908 {
2909         int reservedChunks;
2910         int reservedBlocks = dev->nReservedBlocks;
2911         int checkpointBlocks;
2912         
2913         if(dev->isYaffs2){
2914                 checkpointBlocks =  yaffs_CalcCheckpointBlocksRequired(dev) - 
2915                                     dev->blocksInCheckpoint;
2916                 if(checkpointBlocks < 0)
2917                         checkpointBlocks = 0;
2918         } else {
2919                 checkpointBlocks =0;
2920         }
2921         
2922         reservedChunks = ((reservedBlocks + checkpointBlocks) * dev->nChunksPerBlock);
2923         
2924         return (dev->nFreeChunks > reservedChunks);
2925 }
2926
2927 static int yaffs_AllocateChunk(yaffs_Device * dev, int useReserve, yaffs_BlockInfo **blockUsedPtr)
2928 {
2929         int retVal;
2930         yaffs_BlockInfo *bi;
2931
2932         if (dev->allocationBlock < 0) {
2933                 /* Get next block to allocate off */
2934                 dev->allocationBlock = yaffs_FindBlockForAllocation(dev);
2935                 dev->allocationPage = 0;
2936         }
2937
2938         if (!useReserve && !yaffs_CheckSpaceForAllocation(dev)) {
2939                 /* Not enough space to allocate unless we're allowed to use the reserve. */
2940                 return -1;
2941         }
2942
2943         if (dev->nErasedBlocks < dev->nReservedBlocks
2944             && dev->allocationPage == 0) {
2945                 T(YAFFS_TRACE_ALLOCATE, (TSTR("Allocating reserve" TENDSTR)));
2946         }
2947
2948         /* Next page please.... */
2949         if (dev->allocationBlock >= 0) {
2950                 bi = yaffs_GetBlockInfo(dev, dev->allocationBlock);
2951
2952                 retVal = (dev->allocationBlock * dev->nChunksPerBlock) +
2953                     dev->allocationPage;
2954                 bi->pagesInUse++;
2955                 yaffs_SetChunkBit(dev, dev->allocationBlock,
2956                                   dev->allocationPage);
2957
2958                 dev->allocationPage++;
2959
2960                 dev->nFreeChunks--;
2961
2962                 /* If the block is full set the state to full */
2963                 if (dev->allocationPage >= dev->nChunksPerBlock) {
2964                         bi->blockState = YAFFS_BLOCK_STATE_FULL;
2965                         dev->allocationBlock = -1;
2966                 }
2967
2968                 if(blockUsedPtr)
2969                         *blockUsedPtr = bi;
2970                         
2971                 return retVal;
2972         }
2973         
2974         T(YAFFS_TRACE_ERROR,
2975           (TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));
2976
2977         return -1;
2978 }
2979
2980 static int yaffs_GetErasedChunks(yaffs_Device * dev)
2981 {
2982         int n;
2983
2984         n = dev->nErasedBlocks * dev->nChunksPerBlock;
2985
2986         if (dev->allocationBlock > 0) {
2987                 n += (dev->nChunksPerBlock - dev->allocationPage);
2988         }
2989
2990         return n;
2991
2992 }
2993
2994 static int yaffs_GarbageCollectBlock(yaffs_Device * dev, int block, int wholeBlock)
2995 {
2996         int oldChunk;
2997         int newChunk;
2998         int markNAND;
2999         int retVal = YAFFS_OK;
3000         int cleanups = 0;
3001         int i;
3002         int isCheckpointBlock;
3003         int matchingChunk;
3004         int maxCopies;
3005
3006         int chunksBefore = yaffs_GetErasedChunks(dev);
3007         int chunksAfter;
3008
3009         yaffs_ExtendedTags tags;
3010
3011         yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, block);
3012
3013         yaffs_Object *object;
3014
3015         isCheckpointBlock = (bi->blockState == YAFFS_BLOCK_STATE_CHECKPOINT);
3016         
3017         bi->blockState = YAFFS_BLOCK_STATE_COLLECTING;
3018
3019         T(YAFFS_TRACE_TRACING,
3020           (TSTR("Collecting block %d, in use %d, shrink %d, wholeBlock %d" TENDSTR), 
3021           block,
3022           bi->pagesInUse,
3023           bi->hasShrinkHeader,
3024           wholeBlock));
3025
3026         /*yaffs_VerifyFreeChunks(dev); */
3027
3028         bi->hasShrinkHeader = 0;        /* clear the flag so that the block can erase */
3029
3030         /* Take off the number of soft deleted entries because
3031          * they're going to get really deleted during GC.
3032          */
3033         dev->nFreeChunks -= bi->softDeletions;
3034
3035         dev->isDoingGC = 1;
3036
3037         if (isCheckpointBlock ||
3038             !yaffs_StillSomeChunkBits(dev, block)) {
3039                 T(YAFFS_TRACE_TRACING,
3040                   (TSTR
3041                    ("Collecting block %d that has no chunks in use" TENDSTR),
3042                    block));
3043                 yaffs_BlockBecameDirty(dev, block);
3044         } else {
3045
3046                 __u8 *buffer = yaffs_GetTempBuffer(dev, __LINE__);
3047                 
3048                 yaffs_VerifyBlock(dev,bi,block);
3049
3050                 maxCopies = (wholeBlock) ? dev->nChunksPerBlock : 10;
3051                 oldChunk = block * dev->nChunksPerBlock + dev->gcChunk;
3052                 
3053                 for ( /* init already done */;
3054                      retVal == YAFFS_OK &&
3055                      dev->gcChunk < dev->nChunksPerBlock &&
3056                      (bi->blockState == YAFFS_BLOCK_STATE_COLLECTING)&&
3057                      maxCopies > 0;
3058                      dev->gcChunk++, oldChunk++) {
3059                         if (yaffs_CheckChunkBit(dev, block, dev->gcChunk)) {
3060
3061                                 /* This page is in use and might need to be copied off */
3062                                 
3063                                 maxCopies--;
3064
3065                                 markNAND = 1;
3066
3067                                 yaffs_InitialiseTags(&tags);
3068
3069                                 yaffs_ReadChunkWithTagsFromNAND(dev, oldChunk,
3070                                                                 buffer, &tags);
3071
3072                                 object =
3073                                     yaffs_FindObjectByNumber(dev,
3074                                                              tags.objectId);
3075
3076                                 T(YAFFS_TRACE_GC_DETAIL,
3077                                   (TSTR
3078                                    ("Collecting chunk in block %d, %d %d %d " TENDSTR),
3079                                    dev->gcChunk, tags.objectId, tags.chunkId,
3080                                    tags.byteCount));
3081                                    
3082                                 if(object && !yaffs_SkipVerification(dev)){
3083                                         if(tags.chunkId == 0)
3084                                                 matchingChunk = object->hdrChunk;
3085                                         else if(object->softDeleted)
3086                                                 matchingChunk = oldChunk; /* Defeat the test */
3087                                         else
3088                                                 matchingChunk = yaffs_FindChunkInFile(object,tags.chunkId,NULL);
3089                                         
3090                                         if(oldChunk != matchingChunk)
3091                                                 T(YAFFS_TRACE_ERROR,
3092                                                   (TSTR("gc: page in gc mismatch: %d %d %d %d"TENDSTR),
3093                                                   oldChunk,matchingChunk,tags.objectId, tags.chunkId));
3094                                                 
3095                                 }
3096
3097                                 if (!object) {
3098                                         T(YAFFS_TRACE_ERROR,
3099                                           (TSTR
3100                                            ("page %d in gc has no object: %d %d %d "
3101                                             TENDSTR), oldChunk,
3102                                             tags.objectId, tags.chunkId, tags.byteCount));
3103                                 }
3104
3105                                 if (object && 
3106                                     object->deleted &&
3107                                     object->softDeleted &&
3108                                     tags.chunkId != 0) {
3109                                         /* Data chunk in a soft deleted file, throw it away
3110                                          * It's a soft deleted data chunk,
3111                                          * No need to copy this, just forget about it and 
3112                                          * fix up the object.
3113                                          */
3114
3115                                         object->nDataChunks--;
3116
3117                                         if (object->nDataChunks <= 0) {
3118                                                 /* remeber to clean up the object */
3119                                                 dev->gcCleanupList[cleanups] =
3120                                                     tags.objectId;
3121                                                 cleanups++;
3122                                         }
3123                                         markNAND = 0;
3124                                 } else if (0
3125                                            /* Todo object && object->deleted && object->nDataChunks == 0 */
3126                                            ) {
3127                                         /* Deleted object header with no data chunks.
3128                                          * Can be discarded and the file deleted.
3129                                          */
3130                                         object->hdrChunk = 0;
3131                                         yaffs_FreeTnode(object->myDev,
3132                                                         object->variant.
3133                                                         fileVariant.top);
3134                                         object->variant.fileVariant.top = NULL;
3135                                         yaffs_DoGenericObjectDeletion(object);
3136
3137                                 } else if (object) {
3138                                         /* It's either a data chunk in a live file or
3139                                          * an ObjectHeader, so we're interested in it.
3140                                          * NB Need to keep the ObjectHeaders of deleted files
3141                                          * until the whole file has been deleted off
3142                                          */
3143                                         tags.serialNumber++;
3144
3145                                         dev->nGCCopies++;
3146
3147                                         if (tags.chunkId == 0) {
3148                                                 /* It is an object Id,
3149                                                  * We need to nuke the shrinkheader flags first
3150                                                  * We no longer want the shrinkHeader flag since its work is done
3151                                                  * and if it is left in place it will mess up scanning.
3152                                                  * Also, clear out any shadowing stuff
3153                                                  */
3154
3155                                                 yaffs_ObjectHeader *oh;
3156                                                 oh = (yaffs_ObjectHeader *)buffer;
3157                                                 oh->isShrink = 0;
3158                                                 tags.extraShadows = 0;
3159                                                 tags.extraIsShrinkHeader = 0;
3160                                                 
3161                                                 yaffs_VerifyObjectHeader(object,oh,&tags,1);
3162                                         }
3163
3164                                         newChunk =
3165                                             yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &tags, 1);
3166
3167                                         if (newChunk < 0) {
3168                                                 retVal = YAFFS_FAIL;
3169                                         } else {
3170
3171                                                 /* Ok, now fix up the Tnodes etc. */
3172
3173                                                 if (tags.chunkId == 0) {
3174                                                         /* It's a header */
3175                                                         object->hdrChunk =  newChunk;
3176                                                         object->serial =   tags.serialNumber;
3177                                                 } else {
3178                                                         /* It's a data chunk */
3179                                                         yaffs_PutChunkIntoFile
3180                                                             (object,
3181                                                              tags.chunkId,
3182                                                              newChunk, 0);
3183                                                 }
3184                                         }
3185                                 }
3186
3187                                 if(retVal == YAFFS_OK)
3188                                         yaffs_DeleteChunk(dev, oldChunk, markNAND, __LINE__);
3189
3190                         }
3191                 }
3192
3193                 yaffs_ReleaseTempBuffer(dev, buffer, __LINE__);
3194                 
3195
3196
3197                 /* Do any required cleanups */
3198                 for (i = 0; i < cleanups; i++) {
3199                         /* Time to delete the file too */
3200                         object =
3201                             yaffs_FindObjectByNumber(dev,
3202                                                      dev->gcCleanupList[i]);
3203                         if (object) {
3204                                 yaffs_FreeTnode(dev,
3205                                                 object->variant.fileVariant.
3206                                                 top);
3207                                 object->variant.fileVariant.top = NULL;
3208                                 T(YAFFS_TRACE_GC,
3209                                   (TSTR
3210                                    ("yaffs: About to finally delete object %d"
3211                                     TENDSTR), object->objectId));
3212                                 yaffs_DoGenericObjectDeletion(object);
3213                                 object->myDev->nDeletedFiles--;
3214                         }
3215
3216                 }
3217
3218         }
3219
3220         yaffs_VerifyCollectedBlock(dev,bi,block);
3221           
3222         if (chunksBefore >= (chunksAfter = yaffs_GetErasedChunks(dev))) {
3223                 T(YAFFS_TRACE_GC,
3224                   (TSTR
3225                    ("gc did not increase free chunks before %d after %d"
3226                     TENDSTR), chunksBefore, chunksAfter));
3227         }
3228
3229         /* If the gc completed then clear the current gcBlock so that we find another. */
3230         if(bi->blockState != YAFFS_BLOCK_STATE_COLLECTING){
3231                 dev->gcBlock = -1;
3232                 dev->gcChunk = 0;
3233         }
3234         
3235         dev->isDoingGC = 0;
3236
3237         return retVal;
3238 }
3239
3240 /* New garbage collector
3241  * If we're very low on erased blocks then we do aggressive garbage collection
3242  * otherwise we do "leasurely" garbage collection.
3243  * Aggressive gc looks further (whole array) and will accept less dirty blocks.
3244  * Passive gc only inspects smaller areas and will only accept more dirty blocks.
3245  *
3246  * The idea is to help clear out space in a more spread-out manner.
3247  * Dunno if it really does anything useful.
3248  */
3249 static int yaffs_CheckGarbageCollection(yaffs_Device * dev)
3250 {
3251         int block;
3252         int aggressive;
3253         int gcOk = YAFFS_OK;
3254         int maxTries = 0;
3255         
3256         int checkpointBlockAdjust;
3257
3258         if (dev->isDoingGC) {
3259                 /* Bail out so we don't get recursive gc */
3260                 return YAFFS_OK;
3261         }
3262         
3263         /* This loop should pass the first time.
3264          * We'll only see looping here if the erase of the collected block fails.
3265          */
3266
3267         do {
3268                 maxTries++;
3269                 
3270                 checkpointBlockAdjust = yaffs_CalcCheckpointBlocksRequired(dev) - dev->blocksInCheckpoint;
3271                 if(checkpointBlockAdjust < 0)
3272                         checkpointBlockAdjust = 0;
3273
3274                 if (dev->nErasedBlocks < (dev->nReservedBlocks + checkpointBlockAdjust + 2)) {
3275                         /* We need a block soon...*/
3276                         aggressive = 1;
3277                 } else {
3278                         /* We're in no hurry */
3279                         aggressive = 0;
3280                 }
3281
3282                 if(dev->gcBlock <= 0){
3283                         dev->gcBlock = yaffs_FindBlockForGarbageCollection(dev, aggressive);
3284                         dev->gcChunk = 0;
3285                 }
3286                 
3287                 block = dev->gcBlock;
3288
3289                 if (block > 0) {
3290                         dev->garbageCollections++;
3291                         if (!aggressive) {
3292                                 dev->passiveGarbageCollections++;
3293                         }
3294
3295                         T(YAFFS_TRACE_GC,
3296                           (TSTR
3297                            ("yaffs: GC erasedBlocks %d aggressive %d" TENDSTR),
3298                            dev->nErasedBlocks, aggressive));
3299
3300                         gcOk = yaffs_GarbageCollectBlock(dev,block,aggressive);
3301                 }
3302
3303                 if (dev->nErasedBlocks < (dev->nReservedBlocks) && block > 0) {
3304                         T(YAFFS_TRACE_GC,
3305                           (TSTR
3306                            ("yaffs: GC !!!no reclaim!!! erasedBlocks %d after try %d block %d"
3307                             TENDSTR), dev->nErasedBlocks, maxTries, block));
3308                 }
3309         } while ((dev->nErasedBlocks < dev->nReservedBlocks) && 
3310                  (block > 0) &&
3311                  (maxTries < 2));
3312
3313         return aggressive ? gcOk : YAFFS_OK;
3314 }
3315
3316 /*-------------------------  TAGS --------------------------------*/
3317
3318 static int yaffs_TagsMatch(const yaffs_ExtendedTags * tags, int objectId,
3319                            int chunkInObject)
3320 {
3321         return (tags->chunkId == chunkInObject &&
3322                 tags->objectId == objectId && !tags->chunkDeleted) ? 1 : 0;
3323
3324 }
3325
3326
3327 /*-------------------- Data file manipulation -----------------*/
3328
3329 static int yaffs_FindChunkInFile(yaffs_Object * in, int chunkInInode,
3330                                  yaffs_ExtendedTags * tags)
3331 {
3332         /*Get the Tnode, then get the level 0 offset chunk offset */
3333         yaffs_Tnode *tn;
3334         int theChunk = -1;
3335         yaffs_ExtendedTags localTags;
3336         int retVal = -1;
3337
3338         yaffs_Device *dev = in->myDev;
3339
3340         if (!tags) {
3341                 /* Passed a NULL, so use our own tags space */
3342                 tags = &localTags;
3343         }
3344
3345         tn = yaffs_FindLevel0Tnode(dev, &in->variant.fileVariant, chunkInInode);
3346
3347         if (tn) {
3348                 theChunk = yaffs_GetChunkGroupBase(dev,tn,chunkInInode);
3349
3350                 retVal =
3351                     yaffs_FindChunkInGroup(dev, theChunk, tags, in->objectId,
3352                                            chunkInInode);
3353         }
3354         return retVal;
3355 }
3356
3357 static int yaffs_FindAndDeleteChunkInFile(yaffs_Object * in, int chunkInInode,
3358                                           yaffs_ExtendedTags * tags)
3359 {
3360         /* Get the Tnode, then get the level 0 offset chunk offset */
3361         yaffs_Tnode *tn;
3362         int theChunk = -1;
3363         yaffs_ExtendedTags localTags;
3364
3365         yaffs_Device *dev = in->myDev;
3366         int retVal = -1;
3367
3368         if (!tags) {
3369                 /* Passed a NULL, so use our own tags space */
3370                 tags = &localTags;
3371         }
3372
3373         tn = yaffs_FindLevel0Tnode(dev, &in->variant.fileVariant, chunkInInode);
3374
3375         if (tn) {
3376
3377                 theChunk = yaffs_GetChunkGroupBase(dev,tn,chunkInInode);
3378
3379                 retVal =
3380                     yaffs_FindChunkInGroup(dev, theChunk, tags, in->objectId,
3381                                            chunkInInode);
3382
3383                 /* Delete the entry in the filestructure (if found) */
3384                 if (retVal != -1) {
3385                         yaffs_PutLevel0Tnode(dev,tn,chunkInInode,0);
3386                 }
3387         } else {
3388                 /*T(("No level 0 found for %d\n", chunkInInode)); */
3389         }
3390
3391         if (retVal == -1) {
3392                 /* T(("Could not find %d to delete\n",chunkInInode)); */
3393         }
3394         return retVal;
3395 }
3396
3397 #ifdef YAFFS_PARANOID
3398
3399 static int yaffs_CheckFileSanity(yaffs_Object * in)
3400 {
3401         int chunk;
3402         int nChunks;
3403         int fSize;
3404         int failed = 0;
3405         int objId;
3406         yaffs_Tnode *tn;
3407         yaffs_Tags localTags;
3408         yaffs_Tags *tags = &localTags;
3409         int theChunk;
3410         int chunkDeleted;
3411
3412         if (in->variantType != YAFFS_OBJECT_TYPE_FILE) {
3413                 /* T(("Object not a file\n")); */
3414                 return YAFFS_FAIL;
3415         }
3416
3417         objId = in->objectId;
3418         fSize = in->variant.fileVariant.fileSize;
3419         nChunks =
3420             (fSize + in->myDev->nDataBytesPerChunk - 1) / in->myDev->nDataBytesPerChunk;
3421
3422         for (chunk = 1; chunk <= nChunks; chunk++) {
3423                 tn = yaffs_FindLevel0Tnode(in->myDev, &in->variant.fileVariant,
3424                                            chunk);
3425
3426                 if (tn) {
3427
3428                         theChunk = yaffs_GetChunkGroupBase(dev,tn,chunk);
3429
3430                         if (yaffs_CheckChunkBits
3431                             (dev, theChunk / dev->nChunksPerBlock,
3432                              theChunk % dev->nChunksPerBlock)) {
3433
3434                                 yaffs_ReadChunkTagsFromNAND(in->myDev, theChunk,
3435                                                             tags,
3436                                                             &chunkDeleted);
3437                                 if (yaffs_TagsMatch
3438                                     (tags, in->objectId, chunk, chunkDeleted)) {
3439                                         /* found it; */
3440
3441                                 }
3442                         } else {
3443
3444                                 failed = 1;
3445                         }
3446
3447                 } else {
3448                         /* T(("No level 0 found for %d\n", chunk)); */
3449                 }
3450         }
3451
3452         return failed ? YAFFS_FAIL : YAFFS_OK;
3453 }
3454
3455 #endif
3456
3457 static int yaffs_PutChunkIntoFile(yaffs_Object * in, int chunkInInode,
3458                                   int chunkInNAND, int inScan)
3459 {
3460         /* NB inScan is zero unless scanning. 
3461          * For forward scanning, inScan is > 0; 
3462          * for backward scanning inScan is < 0
3463          */
3464          
3465         yaffs_Tnode *tn;
3466         yaffs_Device *dev = in->myDev;
3467         int existingChunk;
3468         yaffs_ExtendedTags existingTags;
3469         yaffs_ExtendedTags newTags;
3470         unsigned existingSerial, newSerial;
3471
3472         if (in->variantType != YAFFS_OBJECT_TYPE_FILE) {
3473                 /* Just ignore an attempt at putting a chunk into a non-file during scanning
3474                  * If it is not during Scanning then something went wrong!
3475                  */
3476                 if (!inScan) {
3477                         T(YAFFS_TRACE_ERROR,
3478                           (TSTR
3479                            ("yaffs tragedy:attempt to put data chunk into a non-file"
3480                             TENDSTR)));
3481                         YBUG();
3482                 }
3483
3484                 yaffs_DeleteChunk(dev, chunkInNAND, 1, __LINE__);
3485                 return YAFFS_OK;
3486         }
3487
3488         tn = yaffs_AddOrFindLevel0Tnode(dev, 
3489                                         &in->variant.fileVariant,
3490                                         chunkInInode,
3491                                         NULL);
3492         if (!tn) {
3493                 return YAFFS_FAIL;
3494         }
3495
3496         existingChunk = yaffs_GetChunkGroupBase(dev,tn,chunkInInode);
3497
3498         if (inScan != 0) {
3499                 /* If we're scanning then we need to test for duplicates
3500                  * NB This does not need to be efficient since it should only ever 
3501                  * happen when the power fails during a write, then only one
3502                  * chunk should ever be affected.
3503                  *
3504                  * Correction for YAFFS2: This could happen quite a lot and we need to think about efficiency! TODO
3505                  * Update: For backward scanning we don't need to re-read tags so this is quite cheap.
3506                  */
3507
3508                 if (existingChunk > 0) {
3509                         /* NB Right now existing chunk will not be real chunkId if the device >= 32MB
3510                          *    thus we have to do a FindChunkInFile to get the real chunk id.
3511                          *
3512                          * We have a duplicate now we need to decide which one to use:
3513                          *
3514                          * Backwards scanning YAFFS2: The old one is what we use, dump the new one.
3515                          * Forward scanning YAFFS2: The new one is what we use, dump the old one.
3516                          * YAFFS1: Get both sets of tags and compare serial numbers.
3517                          */
3518
3519                         if (inScan > 0) {
3520                                 /* Only do this for forward scanning */
3521                                 yaffs_ReadChunkWithTagsFromNAND(dev,
3522                                                                 chunkInNAND,
3523                                                                 NULL, &newTags);
3524
3525                                 /* Do a proper find */
3526                                 existingChunk =
3527                                     yaffs_FindChunkInFile(in, chunkInInode,
3528                                                           &existingTags);
3529                         }
3530
3531                         if (existingChunk <= 0) {
3532                                 /*Hoosterman - how did this happen? */
3533
3534                                 T(YAFFS_TRACE_ERROR,
3535                                   (TSTR
3536                                    ("yaffs tragedy: existing chunk < 0 in scan"
3537                                     TENDSTR)));
3538
3539                         }
3540
3541                         /* NB The deleted flags should be false, otherwise the chunks will 
3542                          * not be loaded during a scan
3543                          */
3544
3545                         if(inScan > 0) {
3546                                 newSerial = newTags.serialNumber;
3547                                 existingSerial = existingTags.serialNumber;
3548                         }
3549
3550                         if ((inScan > 0) &&
3551                             (in->myDev->isYaffs2 ||
3552                              existingChunk <= 0 ||
3553                              ((existingSerial + 1) & 3) == newSerial)) {
3554                                 /* Forward scanning.                            
3555                                  * Use new
3556                                  * Delete the old one and drop through to update the tnode
3557                                  */
3558                                 yaffs_DeleteChunk(dev, existingChunk, 1,
3559                                                   __LINE__);
3560                         } else {
3561                                 /* Backward scanning or we want to use the existing one
3562                                  * Use existing.
3563                                  * Delete the new one and return early so that the tnode isn't changed
3564                                  */
3565                                 yaffs_DeleteChunk(dev, chunkInNAND, 1,
3566                                                   __LINE__);
3567                                 return YAFFS_OK;
3568                         }
3569                 }
3570
3571         }
3572
3573         if (existingChunk == 0) {
3574                 in->nDataChunks++;
3575         }
3576
3577         yaffs_PutLevel0Tnode(dev,tn,chunkInInode,chunkInNAND);
3578
3579         return YAFFS_OK;
3580 }
3581
3582 static int yaffs_ReadChunkDataFromObject(yaffs_Object * in, int chunkInInode,
3583                                          __u8 * buffer)
3584 {
3585         int chunkInNAND = yaffs_FindChunkInFile(in, chunkInInode, NULL);
3586
3587         if (chunkInNAND >= 0) {
3588                 return yaffs_ReadChunkWithTagsFromNAND(in->myDev, chunkInNAND,
3589                                                        buffer,NULL);
3590         } else {
3591                 T(YAFFS_TRACE_NANDACCESS,
3592                   (TSTR("Chunk %d not found zero instead" TENDSTR),
3593                    chunkInNAND));
3594                 /* get sane (zero) data if you read a hole */
3595                 memset(buffer, 0, in->myDev->nDataBytesPerChunk);       
3596                 return 0;
3597         }
3598
3599 }
3600
3601 void yaffs_DeleteChunk(yaffs_Device * dev, int chunkId, int markNAND, int lyn)
3602 {
3603         int block;
3604         int page;
3605         yaffs_ExtendedTags tags;
3606         yaffs_BlockInfo *bi;
3607
3608         if (chunkId <= 0)
3609                 return;
3610                 
3611
3612         dev->nDeletions++;
3613         block = chunkId / dev->nChunksPerBlock;
3614         page = chunkId % dev->nChunksPerBlock;
3615
3616
3617         if(!yaffs_CheckChunkBit(dev,block,page))
3618                 T(YAFFS_TRACE_VERIFY,
3619                         (TSTR("Deleting invalid chunk %d"TENDSTR),
3620                          chunkId));
3621
3622         bi = yaffs_GetBlockInfo(dev, block);
3623
3624         T(YAFFS_TRACE_DELETION,
3625           (TSTR("line %d delete of chunk %d" TENDSTR), lyn, chunkId));
3626
3627         if (markNAND &&
3628             bi->blockState != YAFFS_BLOCK_STATE_COLLECTING && !dev->isYaffs2) {
3629
3630                 yaffs_InitialiseTags(&tags);
3631
3632                 tags.chunkDeleted = 1;
3633
3634                 yaffs_WriteChunkWithTagsToNAND(dev, chunkId, NULL, &tags);
3635                 yaffs_HandleUpdateChunk(dev, chunkId, &tags);
3636         } else {
3637                 dev->nUnmarkedDeletions++;
3638         }
3639
3640         /* Pull out of the management area.
3641          * If the whole block became dirty, this will kick off an erasure.
3642          */
3643         if (bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING ||
3644             bi->blockState == YAFFS_BLOCK_STATE_FULL ||
3645             bi->blockState == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
3646             bi->blockState == YAFFS_BLOCK_STATE_COLLECTING) {
3647                 dev->nFreeChunks++;
3648
3649                 yaffs_ClearChunkBit(dev, block, page);
3650
3651                 bi->pagesInUse--;
3652
3653                 if (bi->pagesInUse == 0 &&
3654                     !bi->hasShrinkHeader &&
3655                     bi->blockState != YAFFS_BLOCK_STATE_ALLOCATING &&
3656                     bi->blockState != YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
3657                         yaffs_BlockBecameDirty(dev, block);
3658                 }
3659
3660         } else {
3661                 /* T(("Bad news deleting chunk %d\n",chunkId)); */
3662         }
3663
3664 }
3665
3666 static int yaffs_WriteChunkDataToObject(yaffs_Object * in, int chunkInInode,
3667                                         const __u8 * buffer, int nBytes,
3668                                         int useReserve)
3669 {
3670         /* Find old chunk Need to do this to get serial number
3671          * Write new one and patch into tree.
3672          * Invalidate old tags.
3673          */
3674
3675         int prevChunkId;
3676         yaffs_ExtendedTags prevTags;
3677
3678         int newChunkId;
3679         yaffs_ExtendedTags newTags;
3680
3681         yaffs_Device *dev = in->myDev;
3682
3683         yaffs_CheckGarbageCollection(dev);
3684
3685         /* Get the previous chunk at this location in the file if it exists */
3686         prevChunkId = yaffs_FindChunkInFile(in, chunkInInode, &prevTags);
3687
3688         /* Set up new tags */
3689         yaffs_InitialiseTags(&newTags);
3690
3691         newTags.chunkId = chunkInInode;
3692         newTags.objectId = in->objectId;
3693         newTags.serialNumber =
3694             (prevChunkId >= 0) ? prevTags.serialNumber + 1 : 1;
3695         newTags.byteCount = nBytes;
3696         
3697         if(nBytes < 1 || nBytes > dev->totalBytesPerChunk){
3698           T(YAFFS_TRACE_ERROR,
3699           (TSTR("Writing %d bytes to chunk!!!!!!!!!" TENDSTR), nBytes));
3700           while(1){}
3701         }
3702         
3703         
3704
3705         newChunkId =
3706             yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &newTags,
3707                                               useReserve);
3708
3709         if (newChunkId >= 0) {
3710                 yaffs_PutChunkIntoFile(in, chunkInInode, newChunkId, 0);
3711
3712                 if (prevChunkId >= 0) {
3713                         yaffs_DeleteChunk(dev, prevChunkId, 1, __LINE__);
3714
3715                 }
3716
3717                 yaffs_CheckFileSanity(in);
3718         }
3719         return newChunkId;
3720
3721 }
3722
3723 /* UpdateObjectHeader updates the header on NAND for an object.
3724  * If name is not NULL, then that new name is used.
3725  */
3726 int yaffs_UpdateObjectHeader(yaffs_Object * in, const YCHAR * name, int force,
3727                              int isShrink, int shadows)
3728 {
3729
3730         yaffs_BlockInfo *bi;
3731
3732         yaffs_Device *dev = in->myDev;
3733
3734         int prevChunkId;
3735         int retVal = 0;
3736         int result = 0;
3737
3738         int newChunkId;
3739         yaffs_ExtendedTags newTags;
3740         yaffs_ExtendedTags oldTags;
3741
3742         __u8 *buffer = NULL;
3743         YCHAR oldName[YAFFS_MAX_NAME_LENGTH + 1];
3744
3745         yaffs_ObjectHeader *oh = NULL;
3746         
3747         yaffs_strcpy(oldName,_Y("silly old name"));
3748
3749
3750         if (!in->fake || 
3751             in == dev->rootDir || /* The rootDir should also be saved */
3752             force) {
3753
3754                 yaffs_CheckGarbageCollection(dev);
3755                 yaffs_CheckObjectDetailsLoaded(in);
3756
3757                 buffer = yaffs_GetTempBuffer(in->myDev, __LINE__);
3758                 oh = (yaffs_ObjectHeader *) buffer;
3759
3760                 prevChunkId = in->hdrChunk;
3761
3762                 if (prevChunkId > 0) {
3763                         result = yaffs_ReadChunkWithTagsFromNAND(dev, prevChunkId,
3764                                                         buffer, &oldTags);
3765                         
3766                         yaffs_VerifyObjectHeader(in,oh,&oldTags,0);
3767                                                                                 
3768                         memcpy(oldName, oh->name, sizeof(oh->name));
3769                 }
3770
3771                 memset(buffer, 0xFF, dev->nDataBytesPerChunk);
3772
3773                 oh->type = in->variantType;
3774                 oh->yst_mode = in->yst_mode;
3775                 oh->shadowsObject = oh->inbandShadowsObject = shadows;
3776
3777 #ifdef CONFIG_YAFFS_WINCE
3778                 oh->win_atime[0] = in->win_atime[0];
3779                 oh->win_ctime[0] = in->win_ctime[0];
3780                 oh->win_mtime[0] = in->win_mtime[0];
3781                 oh->win_atime[1] = in->win_atime[1];
3782                 oh->win_ctime[1] = in->win_ctime[1];
3783                 oh->win_mtime[1] = in->win_mtime[1];
3784 #else
3785                 oh->yst_uid = in->yst_uid;
3786                 oh->yst_gid = in->yst_gid;
3787                 oh->yst_atime = in->yst_atime;
3788                 oh->yst_mtime = in->yst_mtime;
3789                 oh->yst_ctime = in->yst_ctime;
3790                 oh->yst_rdev = in->yst_rdev;
3791 #endif
3792                 if (in->parent) {
3793                         oh->parentObjectId = in->parent->objectId;
3794                 } else {
3795                         oh->parentObjectId = 0;
3796                 }
3797
3798                 if (name && *name) {
3799                         memset(oh->name, 0, sizeof(oh->name));
3800                         yaffs_strncpy(oh->name, name, YAFFS_MAX_NAME_LENGTH);
3801                 } else if (prevChunkId>=0) {
3802                         memcpy(oh->name, oldName, sizeof(oh->name));
3803                 } else {
3804                         memset(oh->name, 0, sizeof(oh->name));
3805                 }
3806
3807                 oh->isShrink = isShrink;
3808
3809                 switch (in->variantType) {
3810                 case YAFFS_OBJECT_TYPE_UNKNOWN:
3811                         /* Should not happen */
3812                         break;
3813                 case YAFFS_OBJECT_TYPE_FILE:
3814                         oh->fileSize =
3815                             (oh->parentObjectId == YAFFS_OBJECTID_DELETED
3816                              || oh->parentObjectId ==
3817                              YAFFS_OBJECTID_UNLINKED) ? 0 : in->variant.
3818                             fileVariant.fileSize;
3819                         break;
3820                 case YAFFS_OBJECT_TYPE_HARDLINK:
3821                         oh->equivalentObjectId =
3822                             in->variant.hardLinkVariant.equivalentObjectId;
3823                         break;
3824                 case YAFFS_OBJECT_TYPE_SPECIAL:
3825                         /* Do nothing */
3826                         break;
3827                 case YAFFS_OBJECT_TYPE_DIRECTORY:
3828                         /* Do nothing */
3829                         break;
3830                 case YAFFS_OBJECT_TYPE_SYMLINK:
3831                         yaffs_strncpy(oh->alias,
3832                                       in->variant.symLinkVariant.alias,
3833                                       YAFFS_MAX_ALIAS_LENGTH);
3834                         oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
3835                         break;
3836                 }
3837
3838                 /* Tags */
3839                 yaffs_InitialiseTags(&newTags);
3840                 in->serial++;
3841                 newTags.chunkId = 0;
3842                 newTags.objectId = in->objectId;
3843                 newTags.serialNumber = in->serial;
3844
3845                 /* Add extra info for file header */
3846
3847                 newTags.extraHeaderInfoAvailable = 1;
3848                 newTags.extraParentObjectId = oh->parentObjectId;
3849                 newTags.extraFileLength = oh->fileSize;
3850                 newTags.extraIsShrinkHeader = oh->isShrink;
3851                 newTags.extraEquivalentObjectId = oh->equivalentObjectId;
3852                 newTags.extraShadows = (oh->shadowsObject > 0) ? 1 : 0;
3853                 newTags.extraObjectType = in->variantType;
3854
3855                 yaffs_VerifyObjectHeader(in,oh,&newTags,1);
3856
3857                 /* Create new chunk in NAND */
3858                 newChunkId =
3859                     yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &newTags,
3860                                                       (prevChunkId >= 0) ? 1 : 0);
3861
3862                 if (newChunkId >= 0) {
3863
3864                         in->hdrChunk = newChunkId;
3865
3866                         if (prevChunkId >= 0) {
3867                                 yaffs_DeleteChunk(dev, prevChunkId, 1,
3868                                                   __LINE__);
3869                         }
3870
3871                         if(!yaffs_ObjectHasCachedWriteData(in))
3872                                 in->dirty = 0;
3873
3874                         /* If this was a shrink, then mark the block that the chunk lives on */
3875                         if (isShrink) {
3876                                 bi = yaffs_GetBlockInfo(in->myDev,
3877                      &nbs