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