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