2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
4 * Copyright (C) 2002-2010 Aleph One Ltd.
5 * for Toby Churchill Ltd and Brightstar Engineering
7 * Created by Charles Manning <charles@aleph1.co.uk>
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.
15 #include "yaffs_guts.h"
16 #include "yaffs_trace.h"
17 #include "yaffs_yaffs2.h"
18 #include "yaffs_checkptrw.h"
19 #include "yaffs_bitmap.h"
20 #include "yaffs_qsort.h"
21 #include "yaffs_nand.h"
22 #include "yaffs_getblockinfo.h"
25 * Checkpoints are really no benefit on very small partitions.
27 * To save space on small partitions don't bother with checkpoints unless
28 * the partition is at least this big.
30 #define YAFFS_CHECKPOINT_MIN_BLOCKS 60
32 #define YAFFS_SMALL_HOLE_THRESHOLD 4
36 * Oldest Dirty Sequence Number handling.
39 /* yaffs2_CalcOldestDirtySequence()
40 * yaffs2_FindOldestDirtySequence()
41 * Calculate the oldest dirty sequence number if we don't know it.
43 void yaffs2_CalcOldestDirtySequence(yaffs_Device *dev)
50 if(!dev->param.isYaffs2)
53 /* Find the oldest dirty sequence number. */
54 seq = dev->sequenceNumber + 1;
56 for (i = dev->internalStartBlock; i <= dev->internalEndBlock; i++) {
57 if (b->blockState == YAFFS_BLOCK_STATE_FULL &&
58 (b->pagesInUse - b->softDeletions) < dev->param.nChunksPerBlock &&
59 b->sequenceNumber < seq) {
60 seq = b->sequenceNumber;
67 dev->oldestDirtySequence = seq;
68 dev->oldestDirtyBlock = blockNo;
74 void yaffs2_FindOldestDirtySequence(yaffs_Device *dev)
76 if(!dev->param.isYaffs2)
79 if(!dev->oldestDirtySequence)
80 yaffs2_CalcOldestDirtySequence(dev);
84 * yaffs_ClearOldestDirtySequence()
85 * Called when a block is erased or marked bad. (ie. when its sequenceNumber
86 * becomes invalid). If the value matches the oldest then we clear
87 * dev->oldestDirtySequence to force its recomputation.
89 void yaffs2_ClearOldestDirtySequence(yaffs_Device *dev, yaffs_BlockInfo *bi)
92 if(!dev->param.isYaffs2)
95 if(!bi || bi->sequenceNumber == dev->oldestDirtySequence){
96 dev->oldestDirtySequence = 0;
97 dev->oldestDirtyBlock = 0;
102 * yaffs2_UpdateOldestDirtySequence()
103 * Update the oldest dirty sequence number whenever we dirty a block.
104 * Only do this if the oldestDirtySequence is actually being tracked.
106 void yaffs2_UpdateOldestDirtySequence(yaffs_Device *dev, unsigned blockNo, yaffs_BlockInfo *bi)
108 if(!dev->param.isYaffs2)
111 if(dev->oldestDirtySequence){
112 if(dev->oldestDirtySequence > bi->sequenceNumber){
113 dev->oldestDirtySequence = bi->sequenceNumber;
114 dev->oldestDirtyBlock = blockNo;
119 int yaffs2_BlockNotDisqualifiedFromGC(yaffs_Device *dev,
123 if (!dev->param.isYaffs2)
124 return 1; /* disqualification only applies to yaffs2. */
126 if (!bi->hasShrinkHeader)
127 return 1; /* can gc */
129 yaffs2_FindOldestDirtySequence(dev);
131 /* Can't do gc of this block if there are any blocks older than this one that have
134 return (bi->sequenceNumber <= dev->oldestDirtySequence);
138 * yaffs2_FindRefreshBlock()
139 * periodically finds the oldest full block by sequence number for refreshing.
142 __u32 yaffs2_FindRefreshBlock(yaffs_Device *dev)
147 __u32 oldestSequence = 0;
151 if(!dev->param.isYaffs2)
155 * If refresh period < 10 then refreshing is disabled.
157 if(dev->param.refreshPeriod < 10)
163 if(dev->refreshSkip > dev->param.refreshPeriod)
164 dev->refreshSkip = dev->param.refreshPeriod;
166 if(dev->refreshSkip > 0)
170 * Refresh skip is now zero.
171 * We'll do a refresh this time around....
172 * Update the refresh skip and find the oldest block.
174 dev->refreshSkip = dev->param.refreshPeriod;
177 for (b = dev->internalStartBlock; b <=dev->internalEndBlock; b++){
179 if (bi->blockState == YAFFS_BLOCK_STATE_FULL){
182 bi->sequenceNumber < oldestSequence){
184 oldestSequence = bi->sequenceNumber;
192 (TSTR("GC refresh count %d selected block %d with sequenceNumber %d" TENDSTR),
193 dev->refreshCount, oldest, oldestSequence));
199 int yaffs2_CheckpointRequired(yaffs_Device *dev)
203 if(!dev->param.isYaffs2)
206 nblocks = dev->internalEndBlock - dev->internalStartBlock + 1 ;
208 return !dev->param.skipCheckpointWrite &&
210 (nblocks >= YAFFS_CHECKPOINT_MIN_BLOCKS);
213 int yaffs2_CalcCheckpointBlocksRequired(yaffs_Device *dev)
217 if(!dev->param.isYaffs2)
220 if (!dev->nCheckpointBlocksRequired &&
221 yaffs2_CheckpointRequired(dev)){
222 /* Not a valid value so recalculate */
225 int devBlocks = (dev->param.endBlock - dev->param.startBlock + 1);
227 nBytes += sizeof(yaffs_CheckpointValidity);
228 nBytes += sizeof(yaffs_CheckpointDevice);
229 nBytes += devBlocks * sizeof(yaffs_BlockInfo);
230 nBytes += devBlocks * dev->chunkBitmapStride;
231 nBytes += (sizeof(yaffs_CheckpointObject) + sizeof(__u32)) * (dev->nObjects);
232 nBytes += (dev->tnodeSize + sizeof(__u32)) * (dev->nTnodes);
233 nBytes += sizeof(yaffs_CheckpointValidity);
234 nBytes += sizeof(__u32); /* checksum*/
236 /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
238 nBlocks = (nBytes/(dev->nDataBytesPerChunk * dev->param.nChunksPerBlock)) + 3;
240 dev->nCheckpointBlocksRequired = nBlocks;
243 retval = dev->nCheckpointBlocksRequired - dev->blocksInCheckpoint;
249 /*--------------------- Checkpointing --------------------*/
252 static int yaffs2_WriteCheckpointValidityMarker(yaffs_Device *dev, int head)
254 yaffs_CheckpointValidity cp;
256 memset(&cp, 0, sizeof(cp));
258 cp.structType = sizeof(cp);
259 cp.magic = YAFFS_MAGIC;
260 cp.version = YAFFS_CHECKPOINT_VERSION;
261 cp.head = (head) ? 1 : 0;
263 return (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp)) ?
267 static int yaffs2_ReadCheckpointValidityMarker(yaffs_Device *dev, int head)
269 yaffs_CheckpointValidity cp;
272 ok = (yaffs2_CheckpointRead(dev, &cp, sizeof(cp)) == sizeof(cp));
275 ok = (cp.structType == sizeof(cp)) &&
276 (cp.magic == YAFFS_MAGIC) &&
277 (cp.version == YAFFS_CHECKPOINT_VERSION) &&
278 (cp.head == ((head) ? 1 : 0));
282 static void yaffs2_DeviceToCheckpointDevice(yaffs_CheckpointDevice *cp,
285 cp->nErasedBlocks = dev->nErasedBlocks;
286 cp->allocationBlock = dev->allocationBlock;
287 cp->allocationPage = dev->allocationPage;
288 cp->nFreeChunks = dev->nFreeChunks;
290 cp->nDeletedFiles = dev->nDeletedFiles;
291 cp->nUnlinkedFiles = dev->nUnlinkedFiles;
292 cp->nBackgroundDeletions = dev->nBackgroundDeletions;
293 cp->sequenceNumber = dev->sequenceNumber;
297 static void yaffs2_CheckpointDeviceToDevice(yaffs_Device *dev,
298 yaffs_CheckpointDevice *cp)
300 dev->nErasedBlocks = cp->nErasedBlocks;
301 dev->allocationBlock = cp->allocationBlock;
302 dev->allocationPage = cp->allocationPage;
303 dev->nFreeChunks = cp->nFreeChunks;
305 dev->nDeletedFiles = cp->nDeletedFiles;
306 dev->nUnlinkedFiles = cp->nUnlinkedFiles;
307 dev->nBackgroundDeletions = cp->nBackgroundDeletions;
308 dev->sequenceNumber = cp->sequenceNumber;
312 static int yaffs2_WriteCheckpointDevice(yaffs_Device *dev)
314 yaffs_CheckpointDevice cp;
316 __u32 nBlocks = (dev->internalEndBlock - dev->internalStartBlock + 1);
320 /* Write device runtime values*/
321 yaffs2_DeviceToCheckpointDevice(&cp, dev);
322 cp.structType = sizeof(cp);
324 ok = (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp));
326 /* Write block info */
328 nBytes = nBlocks * sizeof(yaffs_BlockInfo);
329 ok = (yaffs2_CheckpointWrite(dev, dev->blockInfo, nBytes) == nBytes);
332 /* Write chunk bits */
334 nBytes = nBlocks * dev->chunkBitmapStride;
335 ok = (yaffs2_CheckpointWrite(dev, dev->chunkBits, nBytes) == nBytes);
341 static int yaffs2_ReadCheckpointDevice(yaffs_Device *dev)
343 yaffs_CheckpointDevice cp;
345 __u32 nBlocks = (dev->internalEndBlock - dev->internalStartBlock + 1);
349 ok = (yaffs2_CheckpointRead(dev, &cp, sizeof(cp)) == sizeof(cp));
353 if (cp.structType != sizeof(cp))
357 yaffs2_CheckpointDeviceToDevice(dev, &cp);
359 nBytes = nBlocks * sizeof(yaffs_BlockInfo);
361 ok = (yaffs2_CheckpointRead(dev, dev->blockInfo, nBytes) == nBytes);
365 nBytes = nBlocks * dev->chunkBitmapStride;
367 ok = (yaffs2_CheckpointRead(dev, dev->chunkBits, nBytes) == nBytes);
372 static void yaffs2_ObjectToCheckpointObject(yaffs_CheckpointObject *cp,
376 cp->objectId = obj->objectId;
377 cp->parentId = (obj->parent) ? obj->parent->objectId : 0;
378 cp->hdrChunk = obj->hdrChunk;
379 cp->variantType = obj->variantType;
380 cp->deleted = obj->deleted;
381 cp->softDeleted = obj->softDeleted;
382 cp->unlinked = obj->unlinked;
383 cp->fake = obj->fake;
384 cp->renameAllowed = obj->renameAllowed;
385 cp->unlinkAllowed = obj->unlinkAllowed;
386 cp->serial = obj->serial;
387 cp->nDataChunks = obj->nDataChunks;
389 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE)
390 cp->fileSizeOrEquivalentObjectId = obj->variant.fileVariant.fileSize;
391 else if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
392 cp->fileSizeOrEquivalentObjectId = obj->variant.hardLinkVariant.equivalentObjectId;
395 static int yaffs2_CheckpointObjectToObject(yaffs_Object *obj, yaffs_CheckpointObject *cp)
398 yaffs_Object *parent;
400 if (obj->variantType != cp->variantType) {
401 T(YAFFS_TRACE_ERROR, (TSTR("Checkpoint read object %d type %d "
402 TCONT("chunk %d does not match existing object type %d")
403 TENDSTR), cp->objectId, cp->variantType, cp->hdrChunk,
408 obj->objectId = cp->objectId;
411 parent = yaffs_FindOrCreateObjectByNumber(
414 YAFFS_OBJECT_TYPE_DIRECTORY);
419 if (parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
420 T(YAFFS_TRACE_ALWAYS, (TSTR("Checkpoint read object %d parent %d type %d"
421 TCONT(" chunk %d Parent type, %d, not directory")
423 cp->objectId, cp->parentId, cp->variantType,
424 cp->hdrChunk, parent->variantType));
427 yaffs_AddObjectToDirectory(parent, obj);
430 obj->hdrChunk = cp->hdrChunk;
431 obj->variantType = cp->variantType;
432 obj->deleted = cp->deleted;
433 obj->softDeleted = cp->softDeleted;
434 obj->unlinked = cp->unlinked;
435 obj->fake = cp->fake;
436 obj->renameAllowed = cp->renameAllowed;
437 obj->unlinkAllowed = cp->unlinkAllowed;
438 obj->serial = cp->serial;
439 obj->nDataChunks = cp->nDataChunks;
441 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE)
442 obj->variant.fileVariant.fileSize = cp->fileSizeOrEquivalentObjectId;
443 else if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
444 obj->variant.hardLinkVariant.equivalentObjectId = cp->fileSizeOrEquivalentObjectId;
446 if (obj->hdrChunk > 0)
453 static int yaffs2_CheckpointTnodeWorker(yaffs_Object *in, yaffs_Tnode *tn,
454 __u32 level, int chunkOffset)
457 yaffs_Device *dev = in->myDev;
463 for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) {
464 if (tn->internal[i]) {
465 ok = yaffs2_CheckpointTnodeWorker(in,
468 (chunkOffset<<YAFFS_TNODES_INTERNAL_BITS) + i);
471 } else if (level == 0) {
472 __u32 baseOffset = chunkOffset << YAFFS_TNODES_LEVEL0_BITS;
473 ok = (yaffs2_CheckpointWrite(dev, &baseOffset, sizeof(baseOffset)) == sizeof(baseOffset));
475 ok = (yaffs2_CheckpointWrite(dev, tn, dev->tnodeSize) == dev->tnodeSize);
483 static int yaffs2_WriteCheckpointTnodes(yaffs_Object *obj)
485 __u32 endMarker = ~0;
488 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
489 ok = yaffs2_CheckpointTnodeWorker(obj,
490 obj->variant.fileVariant.top,
491 obj->variant.fileVariant.topLevel,
494 ok = (yaffs2_CheckpointWrite(obj->myDev, &endMarker, sizeof(endMarker)) ==
501 static int yaffs2_ReadCheckpointTnodes(yaffs_Object *obj)
505 yaffs_Device *dev = obj->myDev;
506 yaffs_FileStructure *fileStructPtr = &obj->variant.fileVariant;
510 ok = (yaffs2_CheckpointRead(dev, &baseChunk, sizeof(baseChunk)) == sizeof(baseChunk));
512 while (ok && (~baseChunk)) {
514 /* Read level 0 tnode */
517 tn = yaffs_GetTnode(dev);
519 ok = (yaffs2_CheckpointRead(dev, tn, dev->tnodeSize) == dev->tnodeSize);
524 ok = yaffs_AddOrFindLevel0Tnode(dev,
530 ok = (yaffs2_CheckpointRead(dev, &baseChunk, sizeof(baseChunk)) == sizeof(baseChunk));
534 T(YAFFS_TRACE_CHECKPOINT, (
535 TSTR("Checkpoint read tnodes %d records, last %d. ok %d" TENDSTR),
536 nread, baseChunk, ok));
542 static int yaffs2_WriteCheckpointObjects(yaffs_Device *dev)
545 yaffs_CheckpointObject cp;
548 struct ylist_head *lh;
551 /* Iterate through the objects in each hash entry,
552 * dumping them to the checkpointing stream.
555 for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
556 ylist_for_each(lh, &dev->objectBucket[i].list) {
558 obj = ylist_entry(lh, yaffs_Object, hashLink);
559 if (!obj->deferedFree) {
560 yaffs2_ObjectToCheckpointObject(&cp, obj);
561 cp.structType = sizeof(cp);
563 T(YAFFS_TRACE_CHECKPOINT, (
564 TSTR("Checkpoint write object %d parent %d type %d chunk %d obj addr %p" TENDSTR),
565 cp.objectId, cp.parentId, cp.variantType, cp.hdrChunk, obj));
567 ok = (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp));
569 if (ok && obj->variantType == YAFFS_OBJECT_TYPE_FILE)
570 ok = yaffs2_WriteCheckpointTnodes(obj);
576 /* Dump end of list */
577 memset(&cp, 0xFF, sizeof(yaffs_CheckpointObject));
578 cp.structType = sizeof(cp);
581 ok = (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp));
586 static int yaffs2_ReadCheckpointObjects(yaffs_Device *dev)
589 yaffs_CheckpointObject cp;
592 yaffs_Object *hardList = NULL;
594 while (ok && !done) {
595 ok = (yaffs2_CheckpointRead(dev, &cp, sizeof(cp)) == sizeof(cp));
596 if (cp.structType != sizeof(cp)) {
597 T(YAFFS_TRACE_CHECKPOINT, (TSTR("struct size %d instead of %d ok %d"TENDSTR),
598 cp.structType, (int)sizeof(cp), ok));
602 T(YAFFS_TRACE_CHECKPOINT, (TSTR("Checkpoint read object %d parent %d type %d chunk %d " TENDSTR),
603 cp.objectId, cp.parentId, cp.variantType, cp.hdrChunk));
605 if (ok && cp.objectId == ~0)
608 obj = yaffs_FindOrCreateObjectByNumber(dev, cp.objectId, cp.variantType);
610 ok = yaffs2_CheckpointObjectToObject(obj, &cp);
613 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
614 ok = yaffs2_ReadCheckpointTnodes(obj);
615 } else if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
616 obj->hardLinks.next =
617 (struct ylist_head *) hardList;
626 yaffs_HardlinkFixup(dev, hardList);
631 static int yaffs2_WriteCheckpointSum(yaffs_Device *dev)
636 yaffs2_GetCheckpointSum(dev, &checkpointSum);
638 ok = (yaffs2_CheckpointWrite(dev, &checkpointSum, sizeof(checkpointSum)) == sizeof(checkpointSum));
646 static int yaffs2_ReadCheckpointSum(yaffs_Device *dev)
648 __u32 checkpointSum0;
649 __u32 checkpointSum1;
652 yaffs2_GetCheckpointSum(dev, &checkpointSum0);
654 ok = (yaffs2_CheckpointRead(dev, &checkpointSum1, sizeof(checkpointSum1)) == sizeof(checkpointSum1));
659 if (checkpointSum0 != checkpointSum1)
666 static int yaffs2_WriteCheckpointData(yaffs_Device *dev)
670 if (!yaffs2_CheckpointRequired(dev)) {
671 T(YAFFS_TRACE_CHECKPOINT, (TSTR("skipping checkpoint write" TENDSTR)));
676 ok = yaffs2_CheckpointOpen(dev, 1);
679 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint validity" TENDSTR)));
680 ok = yaffs2_WriteCheckpointValidityMarker(dev, 1);
683 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint device" TENDSTR)));
684 ok = yaffs2_WriteCheckpointDevice(dev);
687 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint objects" TENDSTR)));
688 ok = yaffs2_WriteCheckpointObjects(dev);
691 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint validity" TENDSTR)));
692 ok = yaffs2_WriteCheckpointValidityMarker(dev, 0);
696 ok = yaffs2_WriteCheckpointSum(dev);
698 if (!yaffs2_CheckpointClose(dev))
702 dev->isCheckpointed = 1;
704 dev->isCheckpointed = 0;
706 return dev->isCheckpointed;
709 static int yaffs2_ReadCheckpointData(yaffs_Device *dev)
713 if(!dev->param.isYaffs2)
716 if (ok && dev->param.skipCheckpointRead) {
717 T(YAFFS_TRACE_CHECKPOINT, (TSTR("skipping checkpoint read" TENDSTR)));
722 ok = yaffs2_CheckpointOpen(dev, 0); /* open for read */
725 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint validity" TENDSTR)));
726 ok = yaffs2_ReadCheckpointValidityMarker(dev, 1);
729 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint device" TENDSTR)));
730 ok = yaffs2_ReadCheckpointDevice(dev);
733 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint objects" TENDSTR)));
734 ok = yaffs2_ReadCheckpointObjects(dev);
737 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint validity" TENDSTR)));
738 ok = yaffs2_ReadCheckpointValidityMarker(dev, 0);
742 ok = yaffs2_ReadCheckpointSum(dev);
743 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint checksum %d" TENDSTR), ok));
746 if (!yaffs2_CheckpointClose(dev))
750 dev->isCheckpointed = 1;
752 dev->isCheckpointed = 0;
758 void yaffs2_InvalidateCheckpoint(yaffs_Device *dev)
760 if (dev->isCheckpointed ||
761 dev->blocksInCheckpoint > 0) {
762 dev->isCheckpointed = 0;
763 yaffs2_CheckpointInvalidateStream(dev);
765 if (dev->param.markSuperBlockDirty)
766 dev->param.markSuperBlockDirty(dev);
770 int yaffs_CheckpointSave(yaffs_Device *dev)
773 T(YAFFS_TRACE_CHECKPOINT, (TSTR("save entry: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
775 yaffs_VerifyObjects(dev);
776 yaffs_VerifyBlocks(dev);
777 yaffs_VerifyFreeChunks(dev);
779 if (!dev->isCheckpointed) {
780 yaffs2_InvalidateCheckpoint(dev);
781 yaffs2_WriteCheckpointData(dev);
784 T(YAFFS_TRACE_ALWAYS, (TSTR("save exit: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
786 return dev->isCheckpointed;
789 int yaffs2_CheckpointRestore(yaffs_Device *dev)
792 T(YAFFS_TRACE_CHECKPOINT, (TSTR("restore entry: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
794 retval = yaffs2_ReadCheckpointData(dev);
796 if (dev->isCheckpointed) {
797 yaffs_VerifyObjects(dev);
798 yaffs_VerifyBlocks(dev);
799 yaffs_VerifyFreeChunks(dev);
802 T(YAFFS_TRACE_CHECKPOINT, (TSTR("restore exit: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
807 int yaffs2_HandleHole(yaffs_Object *obj, loff_t newSize)
809 /* if newsSize > oldFileSize.
810 * We're going to be writing a hole.
811 * If the hole is small then write zeros otherwise write a start of hole marker.
818 int result = YAFFS_OK;
819 yaffs_Device *dev = NULL;
821 __u8 *localBuffer = NULL;
823 int smallIncreaseOk = 0;
828 if(obj->variantType != YAFFS_OBJECT_TYPE_FILE)
833 /* Bail out if not yaffs2 mode */
834 if(!dev->param.isYaffs2)
837 oldFileSize = obj->variant.fileVariant.fileSize;
839 if (newSize <= oldFileSize)
842 increase = newSize - oldFileSize;
844 if(increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->nDataBytesPerChunk &&
845 yaffs_CheckSpaceForAllocation(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
851 localBuffer= yaffs_GetTempBuffer(dev, __LINE__);
854 /* fill hole with zero bytes */
855 int pos = oldFileSize;
858 memset(localBuffer,0,dev->nDataBytesPerChunk);
861 while(increase > 0 && smallIncreaseOk){
862 thisWrite = increase;
863 if(thisWrite > dev->nDataBytesPerChunk)
864 thisWrite = dev->nDataBytesPerChunk;
865 written = yaffs_DoWriteDataToFile(obj,localBuffer,pos,thisWrite,0);
866 if(written == thisWrite){
868 increase -= thisWrite;
873 yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
875 /* If we were out of space then reverse any chunks we've added */
877 yaffs_ResizeDown(obj, oldFileSize);
880 if (!smallIncreaseOk &&
882 obj->parent->objectId != YAFFS_OBJECTID_UNLINKED &&
883 obj->parent->objectId != YAFFS_OBJECTID_DELETED){
884 /* Write a hole start header with the old file size */
885 yaffs_UpdateObjectHeader(obj, NULL, 0, 1, 0, NULL);
899 static int yaffs2_ybicmp(const void *a, const void *b)
901 register int aseq = ((yaffs_BlockIndex *)a)->seq;
902 register int bseq = ((yaffs_BlockIndex *)b)->seq;
903 register int ablock = ((yaffs_BlockIndex *)a)->block;
904 register int bblock = ((yaffs_BlockIndex *)b)->block;
906 return ablock - bblock;
911 int yaffs2_ScanBackwards(yaffs_Device *dev)
913 yaffs_ExtendedTags tags;
918 int nBlocksToScan = 0;
924 yaffs_BlockState state;
925 yaffs_Object *hardList = NULL;
927 __u32 sequenceNumber;
928 yaffs_ObjectHeader *oh;
930 yaffs_Object *parent;
931 int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
937 int foundChunksInBlock;
938 int equivalentObjectId;
939 int alloc_failed = 0;
942 yaffs_BlockIndex *blockIndex = NULL;
943 int altBlockIndex = 0;
947 ("yaffs2_ScanBackwards starts intstartblk %d intendblk %d..."
948 TENDSTR), dev->internalStartBlock, dev->internalEndBlock));
951 dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
953 blockIndex = YMALLOC(nBlocks * sizeof(yaffs_BlockIndex));
956 blockIndex = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockIndex));
962 (TSTR("yaffs2_ScanBackwards() could not allocate block index!" TENDSTR)));
966 dev->blocksInCheckpoint = 0;
968 chunkData = yaffs_GetTempBuffer(dev, __LINE__);
970 /* Scan all the blocks to determine their state */
972 for (blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++) {
973 yaffs_ClearChunkBits(dev, blk);
975 bi->softDeletions = 0;
977 yaffs_QueryInitialBlockState(dev, blk, &state, &sequenceNumber);
979 bi->blockState = state;
980 bi->sequenceNumber = sequenceNumber;
982 if (bi->sequenceNumber == YAFFS_SEQUENCE_CHECKPOINT_DATA)
983 bi->blockState = state = YAFFS_BLOCK_STATE_CHECKPOINT;
984 if (bi->sequenceNumber == YAFFS_SEQUENCE_BAD_BLOCK)
985 bi->blockState = state = YAFFS_BLOCK_STATE_DEAD;
987 T(YAFFS_TRACE_SCAN_DEBUG,
988 (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
989 state, sequenceNumber));
992 if (state == YAFFS_BLOCK_STATE_CHECKPOINT) {
993 dev->blocksInCheckpoint++;
995 } else if (state == YAFFS_BLOCK_STATE_DEAD) {
996 T(YAFFS_TRACE_BAD_BLOCKS,
997 (TSTR("block %d is bad" TENDSTR), blk));
998 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
999 T(YAFFS_TRACE_SCAN_DEBUG,
1000 (TSTR("Block empty " TENDSTR)));
1001 dev->nErasedBlocks++;
1002 dev->nFreeChunks += dev->param.nChunksPerBlock;
1003 } else if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1005 /* Determine the highest sequence number */
1006 if (sequenceNumber >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1007 sequenceNumber < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1009 blockIndex[nBlocksToScan].seq = sequenceNumber;
1010 blockIndex[nBlocksToScan].block = blk;
1014 if (sequenceNumber >= dev->sequenceNumber)
1015 dev->sequenceNumber = sequenceNumber;
1017 /* TODO: Nasty sequence number! */
1020 ("Block scanning block %d has bad sequence number %d"
1021 TENDSTR), blk, sequenceNumber));
1029 (TSTR("%d blocks to be sorted..." TENDSTR), nBlocksToScan));
1035 /* Sort the blocks by sequence number*/
1036 yaffs_qsort(blockIndex, nBlocksToScan, sizeof(yaffs_BlockIndex), yaffs2_ybicmp);
1040 T(YAFFS_TRACE_SCAN, (TSTR("...done" TENDSTR)));
1042 /* Now scan the blocks looking at the data. */
1044 endIterator = nBlocksToScan - 1;
1045 T(YAFFS_TRACE_SCAN_DEBUG,
1046 (TSTR("%d blocks to be scanned" TENDSTR), nBlocksToScan));
1048 /* For each block.... backwards */
1049 for (blockIterator = endIterator; !alloc_failed && blockIterator >= startIterator;
1051 /* Cooperative multitasking! This loop can run for so
1052 long that watchdog timers expire. */
1055 /* get the block to scan in the correct order */
1056 blk = blockIndex[blockIterator].block;
1058 bi = yaffs_GetBlockInfo(dev, blk);
1061 state = bi->blockState;
1065 /* For each chunk in each block that needs scanning.... */
1066 foundChunksInBlock = 0;
1067 for (c = dev->param.nChunksPerBlock - 1;
1068 !alloc_failed && c >= 0 &&
1069 (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1070 state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
1071 /* Scan backwards...
1072 * Read the tags and decide what to do
1075 chunk = blk * dev->param.nChunksPerBlock + c;
1077 result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk, NULL,
1080 /* Let's have a good look at this chunk... */
1082 if (!tags.chunkUsed) {
1083 /* An unassigned chunk in the block.
1084 * If there are used chunks after this one, then
1085 * it is a chunk that was skipped due to failing the erased
1086 * check. Just skip it so that it can be deleted.
1087 * But, more typically, We get here when this is an unallocated
1088 * chunk and his means that either the block is empty or
1089 * this is the one being allocated from
1092 if (foundChunksInBlock) {
1093 /* This is a chunk that was skipped due to failing the erased check */
1094 } else if (c == 0) {
1095 /* We're looking at the first chunk in the block so the block is unused */
1096 state = YAFFS_BLOCK_STATE_EMPTY;
1097 dev->nErasedBlocks++;
1099 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1100 state == YAFFS_BLOCK_STATE_ALLOCATING) {
1101 if (dev->sequenceNumber == bi->sequenceNumber) {
1102 /* this is the block being allocated from */
1106 (" Allocating from %d %d"
1109 state = YAFFS_BLOCK_STATE_ALLOCATING;
1110 dev->allocationBlock = blk;
1111 dev->allocationPage = c;
1112 dev->allocationBlockFinder = blk;
1114 /* This is a partially written block that is not
1115 * the current allocation block.
1119 (TSTR("Partially written block %d detected" TENDSTR),
1127 } else if (tags.eccResult == YAFFS_ECC_RESULT_UNFIXED) {
1129 (TSTR(" Unfixed ECC in chunk(%d:%d), chunk ignored"TENDSTR),
1134 } else if (tags.objectId > YAFFS_MAX_OBJECT_ID ||
1135 tags.chunkId > YAFFS_MAX_CHUNK_ID ||
1136 (tags.chunkId > 0 && tags.byteCount > dev->nDataBytesPerChunk) ||
1137 tags.sequenceNumber != bi->sequenceNumber ) {
1139 (TSTR("Chunk (%d:%d) with bad tags:obj = %d, chunkId = %d, byteCount = %d, ignored"TENDSTR),
1140 blk, c,tags.objectId, tags.chunkId, tags.byteCount));
1144 } else if (tags.chunkId > 0) {
1145 /* chunkId > 0 so it is a data chunk... */
1146 unsigned int endpos;
1148 (tags.chunkId - 1) * dev->nDataBytesPerChunk;
1150 foundChunksInBlock = 1;
1153 yaffs_SetChunkBit(dev, blk, c);
1156 in = yaffs_FindOrCreateObjectByNumber(dev,
1159 YAFFS_OBJECT_TYPE_FILE);
1166 in->variantType == YAFFS_OBJECT_TYPE_FILE
1167 && chunkBase < in->variant.fileVariant.shrinkSize) {
1168 /* This has not been invalidated by a resize */
1169 if (!yaffs_PutChunkIntoFile(in, tags.chunkId, chunk, -1)) {
1173 /* File size is calculated by looking at the data chunks if we have not
1174 * seen an object header yet. Stop this practice once we find an object header.
1176 endpos = chunkBase + tags.byteCount;
1178 if (!in->valid && /* have not got an object header yet */
1179 in->variant.fileVariant.scannedFileSize < endpos) {
1180 in->variant.fileVariant.scannedFileSize = endpos;
1181 in->variant.fileVariant.fileSize = endpos;
1185 /* This chunk has been invalidated by a resize, or a past file deletion
1186 * so delete the chunk*/
1187 yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
1191 /* chunkId == 0, so it is an ObjectHeader.
1192 * Thus, we read in the object header and make the object
1194 foundChunksInBlock = 1;
1196 yaffs_SetChunkBit(dev, blk, c);
1202 if (tags.extraHeaderInfoAvailable) {
1203 in = yaffs_FindOrCreateObjectByNumber(dev,
1205 tags.extraObjectType);
1211 (!in->valid && dev->param.disableLazyLoad) ||
1212 tags.extraShadows ||
1214 (tags.objectId == YAFFS_OBJECTID_ROOT ||
1215 tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))) {
1217 /* If we don't have valid info then we need to read the chunk
1218 * TODO In future we can probably defer reading the chunk and
1219 * living with invalid data until needed.
1222 result = yaffs_ReadChunkWithTagsFromNAND(dev,
1227 oh = (yaffs_ObjectHeader *) chunkData;
1229 if (dev->param.inbandTags) {
1230 /* Fix up the header if they got corrupted by inband tags */
1231 oh->shadowsObject = oh->inbandShadowsObject;
1232 oh->isShrink = oh->inbandIsShrink;
1236 in = yaffs_FindOrCreateObjectByNumber(dev, tags.objectId, oh->type);
1244 /* TODO Hoosterman we have a problem! */
1245 T(YAFFS_TRACE_ERROR,
1247 ("yaffs tragedy: Could not make object for object %d at chunk %d during scan"
1248 TENDSTR), tags.objectId, chunk));
1253 /* We have already filled this one.
1254 * We have a duplicate that will be discarded, but
1255 * we first have to suck out resize info if it is a file.
1258 if ((in->variantType == YAFFS_OBJECT_TYPE_FILE) &&
1260 oh->type == YAFFS_OBJECT_TYPE_FILE) ||
1261 (tags.extraHeaderInfoAvailable &&
1262 tags.extraObjectType == YAFFS_OBJECT_TYPE_FILE))) {
1264 (oh) ? oh->fileSize : tags.
1266 __u32 parentObjectId =
1268 parentObjectId : tags.
1269 extraParentObjectId;
1273 (oh) ? oh->isShrink : tags.
1274 extraIsShrinkHeader;
1276 /* If it is deleted (unlinked at start also means deleted)
1277 * we treat the file size as being zeroed at this point.
1279 if (parentObjectId ==
1280 YAFFS_OBJECTID_DELETED
1281 || parentObjectId ==
1282 YAFFS_OBJECTID_UNLINKED) {
1287 if (isShrink && in->variant.fileVariant.shrinkSize > thisSize)
1288 in->variant.fileVariant.shrinkSize = thisSize;
1291 bi->hasShrinkHeader = 1;
1294 /* Use existing - destroy this one. */
1295 yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
1299 if (!in->valid && in->variantType !=
1300 (oh ? oh->type : tags.extraObjectType))
1301 T(YAFFS_TRACE_ERROR, (
1302 TSTR("yaffs tragedy: Bad object type, "
1303 TCONT("%d != %d, for object %d at chunk ")
1304 TCONT("%d during scan")
1306 oh->type : tags.extraObjectType,
1307 in->variantType, tags.objectId,
1311 (tags.objectId == YAFFS_OBJECTID_ROOT ||
1313 YAFFS_OBJECTID_LOSTNFOUND)) {
1314 /* We only load some info, don't fiddle with directory structure */
1319 in->yst_mode = oh->yst_mode;
1320 #ifdef CONFIG_YAFFS_WINCE
1321 in->win_atime[0] = oh->win_atime[0];
1322 in->win_ctime[0] = oh->win_ctime[0];
1323 in->win_mtime[0] = oh->win_mtime[0];
1324 in->win_atime[1] = oh->win_atime[1];
1325 in->win_ctime[1] = oh->win_ctime[1];
1326 in->win_mtime[1] = oh->win_mtime[1];
1328 in->yst_uid = oh->yst_uid;
1329 in->yst_gid = oh->yst_gid;
1330 in->yst_atime = oh->yst_atime;
1331 in->yst_mtime = oh->yst_mtime;
1332 in->yst_ctime = oh->yst_ctime;
1333 in->yst_rdev = oh->yst_rdev;
1341 in->hdrChunk = chunk;
1343 } else if (!in->valid) {
1344 /* we need to load this info */
1347 in->hdrChunk = chunk;
1350 in->variantType = oh->type;
1352 in->yst_mode = oh->yst_mode;
1353 #ifdef CONFIG_YAFFS_WINCE
1354 in->win_atime[0] = oh->win_atime[0];
1355 in->win_ctime[0] = oh->win_ctime[0];
1356 in->win_mtime[0] = oh->win_mtime[0];
1357 in->win_atime[1] = oh->win_atime[1];
1358 in->win_ctime[1] = oh->win_ctime[1];
1359 in->win_mtime[1] = oh->win_mtime[1];
1361 in->yst_uid = oh->yst_uid;
1362 in->yst_gid = oh->yst_gid;
1363 in->yst_atime = oh->yst_atime;
1364 in->yst_mtime = oh->yst_mtime;
1365 in->yst_ctime = oh->yst_ctime;
1366 in->yst_rdev = oh->yst_rdev;
1369 if (oh->shadowsObject > 0)
1370 yaffs_HandleShadowedObject(dev,
1377 yaffs_SetObjectNameFromOH(in, oh);
1379 yaffs_FindOrCreateObjectByNumber
1380 (dev, oh->parentObjectId,
1381 YAFFS_OBJECT_TYPE_DIRECTORY);
1383 fileSize = oh->fileSize;
1384 isShrink = oh->isShrink;
1385 equivalentObjectId = oh->equivalentObjectId;
1388 in->variantType = tags.extraObjectType;
1390 yaffs_FindOrCreateObjectByNumber
1391 (dev, tags.extraParentObjectId,
1392 YAFFS_OBJECT_TYPE_DIRECTORY);
1393 fileSize = tags.extraFileLength;
1394 isShrink = tags.extraIsShrinkHeader;
1395 equivalentObjectId = tags.extraEquivalentObjectId;
1404 /* directory stuff...
1408 if (parent && parent->variantType ==
1409 YAFFS_OBJECT_TYPE_UNKNOWN) {
1410 /* Set up as a directory */
1411 parent->variantType =
1412 YAFFS_OBJECT_TYPE_DIRECTORY;
1413 YINIT_LIST_HEAD(&parent->variant.
1416 } else if (!parent || parent->variantType !=
1417 YAFFS_OBJECT_TYPE_DIRECTORY) {
1418 /* Hoosterman, another problem....
1419 * We're trying to use a non-directory as a directory
1422 T(YAFFS_TRACE_ERROR,
1424 ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1426 parent = dev->lostNFoundDir;
1429 yaffs_AddObjectToDirectory(parent, in);
1431 itsUnlinked = (parent == dev->deletedDir) ||
1432 (parent == dev->unlinkedDir);
1435 /* Mark the block as having a shrinkHeader */
1436 bi->hasShrinkHeader = 1;
1439 /* Note re hardlinks.
1440 * Since we might scan a hardlink before its equivalent object is scanned
1441 * we put them all in a list.
1442 * After scanning is complete, we should have all the objects, so we run
1443 * through this list and fix up all the chains.
1446 switch (in->variantType) {
1447 case YAFFS_OBJECT_TYPE_UNKNOWN:
1448 /* Todo got a problem */
1450 case YAFFS_OBJECT_TYPE_FILE:
1452 if (in->variant.fileVariant.
1453 scannedFileSize < fileSize) {
1454 /* This covers the case where the file size is greater
1455 * than where the data is
1456 * This will happen if the file is resized to be larger
1457 * than its current data extents.
1459 in->variant.fileVariant.fileSize = fileSize;
1460 in->variant.fileVariant.scannedFileSize = fileSize;
1463 if (in->variant.fileVariant.shrinkSize > fileSize)
1464 in->variant.fileVariant.shrinkSize = fileSize;
1468 case YAFFS_OBJECT_TYPE_HARDLINK:
1470 in->variant.hardLinkVariant.equivalentObjectId =
1472 in->hardLinks.next =
1473 (struct ylist_head *) hardList;
1477 case YAFFS_OBJECT_TYPE_DIRECTORY:
1480 case YAFFS_OBJECT_TYPE_SPECIAL:
1483 case YAFFS_OBJECT_TYPE_SYMLINK:
1485 in->variant.symLinkVariant.alias =
1486 yaffs_CloneString(oh->alias);
1487 if (!in->variant.symLinkVariant.alias)
1497 } /* End of scanning for each chunk */
1499 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1500 /* If we got this far while scanning, then the block is fully allocated. */
1501 state = YAFFS_BLOCK_STATE_FULL;
1505 bi->blockState = state;
1507 /* Now let's see if it was dirty */
1508 if (bi->pagesInUse == 0 &&
1509 !bi->hasShrinkHeader &&
1510 bi->blockState == YAFFS_BLOCK_STATE_FULL) {
1511 yaffs_BlockBecameDirty(dev, blk);
1516 yaffs_SkipRestOfBlock(dev);
1519 YFREE_ALT(blockIndex);
1523 /* Ok, we've done all the scanning.
1524 * Fix up the hard link chains.
1525 * We should now have scanned all the objects, now it's time to add these
1528 yaffs_HardlinkFixup(dev, hardList);
1531 yaffs_ReleaseTempBuffer(dev, chunkData, __LINE__);
1536 T(YAFFS_TRACE_SCAN, (TSTR("yaffs2_ScanBackwards ends" TENDSTR)));