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