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"
23 #include "yaffs_verify.h"
26 * Checkpoints are really no benefit on very small partitions.
28 * To save space on small partitions don't bother with checkpoints unless
29 * the partition is at least this big.
31 #define YAFFS_CHECKPOINT_MIN_BLOCKS 60
33 #define YAFFS_SMALL_HOLE_THRESHOLD 4
37 * Oldest Dirty Sequence Number handling.
40 /* yaffs2_CalcOldestDirtySequence()
41 * yaffs2_FindOldestDirtySequence()
42 * Calculate the oldest dirty sequence number if we don't know it.
44 void yaffs2_CalcOldestDirtySequence(yaffs_Device *dev)
51 if(!dev->param.isYaffs2)
54 /* Find the oldest dirty sequence number. */
55 seq = dev->sequenceNumber + 1;
57 for (i = dev->internalStartBlock; i <= dev->internalEndBlock; i++) {
58 if (b->blockState == YAFFS_BLOCK_STATE_FULL &&
59 (b->pagesInUse - b->softDeletions) < dev->param.nChunksPerBlock &&
60 b->sequenceNumber < seq) {
61 seq = b->sequenceNumber;
68 dev->oldestDirtySequence = seq;
69 dev->oldestDirtyBlock = blockNo;
75 void yaffs2_FindOldestDirtySequence(yaffs_Device *dev)
77 if(!dev->param.isYaffs2)
80 if(!dev->oldestDirtySequence)
81 yaffs2_CalcOldestDirtySequence(dev);
85 * yaffs_ClearOldestDirtySequence()
86 * Called when a block is erased or marked bad. (ie. when its sequenceNumber
87 * becomes invalid). If the value matches the oldest then we clear
88 * dev->oldestDirtySequence to force its recomputation.
90 void yaffs2_ClearOldestDirtySequence(yaffs_Device *dev, yaffs_BlockInfo *bi)
93 if(!dev->param.isYaffs2)
96 if(!bi || bi->sequenceNumber == dev->oldestDirtySequence){
97 dev->oldestDirtySequence = 0;
98 dev->oldestDirtyBlock = 0;
103 * yaffs2_UpdateOldestDirtySequence()
104 * Update the oldest dirty sequence number whenever we dirty a block.
105 * Only do this if the oldestDirtySequence is actually being tracked.
107 void yaffs2_UpdateOldestDirtySequence(yaffs_Device *dev, unsigned blockNo, yaffs_BlockInfo *bi)
109 if(!dev->param.isYaffs2)
112 if(dev->oldestDirtySequence){
113 if(dev->oldestDirtySequence > bi->sequenceNumber){
114 dev->oldestDirtySequence = bi->sequenceNumber;
115 dev->oldestDirtyBlock = blockNo;
120 int yaffs2_BlockNotDisqualifiedFromGC(yaffs_Device *dev,
124 if (!dev->param.isYaffs2)
125 return 1; /* disqualification only applies to yaffs2. */
127 if (!bi->hasShrinkHeader)
128 return 1; /* can gc */
130 yaffs2_FindOldestDirtySequence(dev);
132 /* Can't do gc of this block if there are any blocks older than this one that have
135 return (bi->sequenceNumber <= dev->oldestDirtySequence);
139 * yaffs2_FindRefreshBlock()
140 * periodically finds the oldest full block by sequence number for refreshing.
143 __u32 yaffs2_FindRefreshBlock(yaffs_Device *dev)
148 __u32 oldestSequence = 0;
152 if(!dev->param.isYaffs2)
156 * If refresh period < 10 then refreshing is disabled.
158 if(dev->param.refreshPeriod < 10)
164 if(dev->refreshSkip > dev->param.refreshPeriod)
165 dev->refreshSkip = dev->param.refreshPeriod;
167 if(dev->refreshSkip > 0)
171 * Refresh skip is now zero.
172 * We'll do a refresh this time around....
173 * Update the refresh skip and find the oldest block.
175 dev->refreshSkip = dev->param.refreshPeriod;
178 for (b = dev->internalStartBlock; b <=dev->internalEndBlock; b++){
180 if (bi->blockState == YAFFS_BLOCK_STATE_FULL){
183 bi->sequenceNumber < oldestSequence){
185 oldestSequence = bi->sequenceNumber;
193 (TSTR("GC refresh count %d selected block %d with sequenceNumber %d" TENDSTR),
194 dev->refreshCount, oldest, oldestSequence));
200 int yaffs2_CheckpointRequired(yaffs_Device *dev)
204 if(!dev->param.isYaffs2)
207 nblocks = dev->internalEndBlock - dev->internalStartBlock + 1 ;
209 return !dev->param.skipCheckpointWrite &&
211 (nblocks >= YAFFS_CHECKPOINT_MIN_BLOCKS);
214 int yaffs2_CalcCheckpointBlocksRequired(yaffs_Device *dev)
218 if(!dev->param.isYaffs2)
221 if (!dev->nCheckpointBlocksRequired &&
222 yaffs2_CheckpointRequired(dev)){
223 /* Not a valid value so recalculate */
226 int devBlocks = (dev->param.endBlock - dev->param.startBlock + 1);
228 nBytes += sizeof(yaffs_CheckpointValidity);
229 nBytes += sizeof(yaffs_CheckpointDevice);
230 nBytes += devBlocks * sizeof(yaffs_BlockInfo);
231 nBytes += devBlocks * dev->chunkBitmapStride;
232 nBytes += (sizeof(yaffs_CheckpointObject) + sizeof(__u32)) * (dev->nObjects);
233 nBytes += (dev->tnodeSize + sizeof(__u32)) * (dev->nTnodes);
234 nBytes += sizeof(yaffs_CheckpointValidity);
235 nBytes += sizeof(__u32); /* checksum*/
237 /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
239 nBlocks = (nBytes/(dev->nDataBytesPerChunk * dev->param.nChunksPerBlock)) + 3;
241 dev->nCheckpointBlocksRequired = nBlocks;
244 retval = dev->nCheckpointBlocksRequired - dev->blocksInCheckpoint;
250 /*--------------------- Checkpointing --------------------*/
253 static int yaffs2_WriteCheckpointValidityMarker(yaffs_Device *dev, int head)
255 yaffs_CheckpointValidity cp;
257 memset(&cp, 0, sizeof(cp));
259 cp.structType = sizeof(cp);
260 cp.magic = YAFFS_MAGIC;
261 cp.version = YAFFS_CHECKPOINT_VERSION;
262 cp.head = (head) ? 1 : 0;
264 return (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp)) ?
268 static int yaffs2_ReadCheckpointValidityMarker(yaffs_Device *dev, int head)
270 yaffs_CheckpointValidity cp;
273 ok = (yaffs2_CheckpointRead(dev, &cp, sizeof(cp)) == sizeof(cp));
276 ok = (cp.structType == sizeof(cp)) &&
277 (cp.magic == YAFFS_MAGIC) &&
278 (cp.version == YAFFS_CHECKPOINT_VERSION) &&
279 (cp.head == ((head) ? 1 : 0));
283 static void yaffs2_DeviceToCheckpointDevice(yaffs_CheckpointDevice *cp,
286 cp->nErasedBlocks = dev->nErasedBlocks;
287 cp->allocationBlock = dev->allocationBlock;
288 cp->allocationPage = dev->allocationPage;
289 cp->nFreeChunks = dev->nFreeChunks;
291 cp->nDeletedFiles = dev->nDeletedFiles;
292 cp->nUnlinkedFiles = dev->nUnlinkedFiles;
293 cp->nBackgroundDeletions = dev->nBackgroundDeletions;
294 cp->sequenceNumber = dev->sequenceNumber;
298 static void yaffs2_CheckpointDeviceToDevice(yaffs_Device *dev,
299 yaffs_CheckpointDevice *cp)
301 dev->nErasedBlocks = cp->nErasedBlocks;
302 dev->allocationBlock = cp->allocationBlock;
303 dev->allocationPage = cp->allocationPage;
304 dev->nFreeChunks = cp->nFreeChunks;
306 dev->nDeletedFiles = cp->nDeletedFiles;
307 dev->nUnlinkedFiles = cp->nUnlinkedFiles;
308 dev->nBackgroundDeletions = cp->nBackgroundDeletions;
309 dev->sequenceNumber = cp->sequenceNumber;
313 static int yaffs2_WriteCheckpointDevice(yaffs_Device *dev)
315 yaffs_CheckpointDevice cp;
317 __u32 nBlocks = (dev->internalEndBlock - dev->internalStartBlock + 1);
321 /* Write device runtime values*/
322 yaffs2_DeviceToCheckpointDevice(&cp, dev);
323 cp.structType = sizeof(cp);
325 ok = (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp));
327 /* Write block info */
329 nBytes = nBlocks * sizeof(yaffs_BlockInfo);
330 ok = (yaffs2_CheckpointWrite(dev, dev->blockInfo, nBytes) == nBytes);
333 /* Write chunk bits */
335 nBytes = nBlocks * dev->chunkBitmapStride;
336 ok = (yaffs2_CheckpointWrite(dev, dev->chunkBits, nBytes) == nBytes);
342 static int yaffs2_ReadCheckpointDevice(yaffs_Device *dev)
344 yaffs_CheckpointDevice cp;
346 __u32 nBlocks = (dev->internalEndBlock - dev->internalStartBlock + 1);
350 ok = (yaffs2_CheckpointRead(dev, &cp, sizeof(cp)) == sizeof(cp));
354 if (cp.structType != sizeof(cp))
358 yaffs2_CheckpointDeviceToDevice(dev, &cp);
360 nBytes = nBlocks * sizeof(yaffs_BlockInfo);
362 ok = (yaffs2_CheckpointRead(dev, dev->blockInfo, nBytes) == nBytes);
366 nBytes = nBlocks * dev->chunkBitmapStride;
368 ok = (yaffs2_CheckpointRead(dev, dev->chunkBits, nBytes) == nBytes);
373 static void yaffs2_ObjectToCheckpointObject(yaffs_CheckpointObject *cp,
377 cp->objectId = obj->objectId;
378 cp->parentId = (obj->parent) ? obj->parent->objectId : 0;
379 cp->hdrChunk = obj->hdrChunk;
380 cp->variantType = obj->variantType;
381 cp->deleted = obj->deleted;
382 cp->softDeleted = obj->softDeleted;
383 cp->unlinked = obj->unlinked;
384 cp->fake = obj->fake;
385 cp->renameAllowed = obj->renameAllowed;
386 cp->unlinkAllowed = obj->unlinkAllowed;
387 cp->serial = obj->serial;
388 cp->nDataChunks = obj->nDataChunks;
390 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE)
391 cp->fileSizeOrEquivalentObjectId = obj->variant.fileVariant.fileSize;
392 else if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
393 cp->fileSizeOrEquivalentObjectId = obj->variant.hardLinkVariant.equivalentObjectId;
396 static int yaffs2_CheckpointObjectToObject(yaffs_Object *obj, yaffs_CheckpointObject *cp)
399 yaffs_Object *parent;
401 if (obj->variantType != cp->variantType) {
402 T(YAFFS_TRACE_ERROR, (TSTR("Checkpoint read object %d type %d "
403 TCONT("chunk %d does not match existing object type %d")
404 TENDSTR), cp->objectId, cp->variantType, cp->hdrChunk,
409 obj->objectId = cp->objectId;
412 parent = yaffs_FindOrCreateObjectByNumber(
415 YAFFS_OBJECT_TYPE_DIRECTORY);
420 if (parent->variantType != YAFFS_OBJECT_TYPE_DIRECTORY) {
421 T(YAFFS_TRACE_ALWAYS, (TSTR("Checkpoint read object %d parent %d type %d"
422 TCONT(" chunk %d Parent type, %d, not directory")
424 cp->objectId, cp->parentId, cp->variantType,
425 cp->hdrChunk, parent->variantType));
428 yaffs_AddObjectToDirectory(parent, obj);
431 obj->hdrChunk = cp->hdrChunk;
432 obj->variantType = cp->variantType;
433 obj->deleted = cp->deleted;
434 obj->softDeleted = cp->softDeleted;
435 obj->unlinked = cp->unlinked;
436 obj->fake = cp->fake;
437 obj->renameAllowed = cp->renameAllowed;
438 obj->unlinkAllowed = cp->unlinkAllowed;
439 obj->serial = cp->serial;
440 obj->nDataChunks = cp->nDataChunks;
442 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE)
443 obj->variant.fileVariant.fileSize = cp->fileSizeOrEquivalentObjectId;
444 else if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK)
445 obj->variant.hardLinkVariant.equivalentObjectId = cp->fileSizeOrEquivalentObjectId;
447 if (obj->hdrChunk > 0)
454 static int yaffs2_CheckpointTnodeWorker(yaffs_Object *in, yaffs_Tnode *tn,
455 __u32 level, int chunkOffset)
458 yaffs_Device *dev = in->myDev;
464 for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) {
465 if (tn->internal[i]) {
466 ok = yaffs2_CheckpointTnodeWorker(in,
469 (chunkOffset<<YAFFS_TNODES_INTERNAL_BITS) + i);
472 } else if (level == 0) {
473 __u32 baseOffset = chunkOffset << YAFFS_TNODES_LEVEL0_BITS;
474 ok = (yaffs2_CheckpointWrite(dev, &baseOffset, sizeof(baseOffset)) == sizeof(baseOffset));
476 ok = (yaffs2_CheckpointWrite(dev, tn, dev->tnodeSize) == dev->tnodeSize);
484 static int yaffs2_WriteCheckpointTnodes(yaffs_Object *obj)
486 __u32 endMarker = ~0;
489 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
490 ok = yaffs2_CheckpointTnodeWorker(obj,
491 obj->variant.fileVariant.top,
492 obj->variant.fileVariant.topLevel,
495 ok = (yaffs2_CheckpointWrite(obj->myDev, &endMarker, sizeof(endMarker)) ==
502 static int yaffs2_ReadCheckpointTnodes(yaffs_Object *obj)
506 yaffs_Device *dev = obj->myDev;
507 yaffs_FileStructure *fileStructPtr = &obj->variant.fileVariant;
511 ok = (yaffs2_CheckpointRead(dev, &baseChunk, sizeof(baseChunk)) == sizeof(baseChunk));
513 while (ok && (~baseChunk)) {
515 /* Read level 0 tnode */
518 tn = yaffs_GetTnode(dev);
520 ok = (yaffs2_CheckpointRead(dev, tn, dev->tnodeSize) == dev->tnodeSize);
525 ok = yaffs_AddOrFindLevel0Tnode(dev,
531 ok = (yaffs2_CheckpointRead(dev, &baseChunk, sizeof(baseChunk)) == sizeof(baseChunk));
535 T(YAFFS_TRACE_CHECKPOINT, (
536 TSTR("Checkpoint read tnodes %d records, last %d. ok %d" TENDSTR),
537 nread, baseChunk, ok));
543 static int yaffs2_WriteCheckpointObjects(yaffs_Device *dev)
546 yaffs_CheckpointObject cp;
549 struct ylist_head *lh;
552 /* Iterate through the objects in each hash entry,
553 * dumping them to the checkpointing stream.
556 for (i = 0; ok && i < YAFFS_NOBJECT_BUCKETS; i++) {
557 ylist_for_each(lh, &dev->objectBucket[i].list) {
559 obj = ylist_entry(lh, yaffs_Object, hashLink);
560 if (!obj->deferedFree) {
561 yaffs2_ObjectToCheckpointObject(&cp, obj);
562 cp.structType = sizeof(cp);
564 T(YAFFS_TRACE_CHECKPOINT, (
565 TSTR("Checkpoint write object %d parent %d type %d chunk %d obj addr %p" TENDSTR),
566 cp.objectId, cp.parentId, cp.variantType, cp.hdrChunk, obj));
568 ok = (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp));
570 if (ok && obj->variantType == YAFFS_OBJECT_TYPE_FILE)
571 ok = yaffs2_WriteCheckpointTnodes(obj);
577 /* Dump end of list */
578 memset(&cp, 0xFF, sizeof(yaffs_CheckpointObject));
579 cp.structType = sizeof(cp);
582 ok = (yaffs2_CheckpointWrite(dev, &cp, sizeof(cp)) == sizeof(cp));
587 static int yaffs2_ReadCheckpointObjects(yaffs_Device *dev)
590 yaffs_CheckpointObject cp;
593 yaffs_Object *hardList = NULL;
595 while (ok && !done) {
596 ok = (yaffs2_CheckpointRead(dev, &cp, sizeof(cp)) == sizeof(cp));
597 if (cp.structType != sizeof(cp)) {
598 T(YAFFS_TRACE_CHECKPOINT, (TSTR("struct size %d instead of %d ok %d"TENDSTR),
599 cp.structType, (int)sizeof(cp), ok));
603 T(YAFFS_TRACE_CHECKPOINT, (TSTR("Checkpoint read object %d parent %d type %d chunk %d " TENDSTR),
604 cp.objectId, cp.parentId, cp.variantType, cp.hdrChunk));
606 if (ok && cp.objectId == ~0)
609 obj = yaffs_FindOrCreateObjectByNumber(dev, cp.objectId, cp.variantType);
611 ok = yaffs2_CheckpointObjectToObject(obj, &cp);
614 if (obj->variantType == YAFFS_OBJECT_TYPE_FILE) {
615 ok = yaffs2_ReadCheckpointTnodes(obj);
616 } else if (obj->variantType == YAFFS_OBJECT_TYPE_HARDLINK) {
617 obj->hardLinks.next =
618 (struct ylist_head *) hardList;
627 yaffs_HardlinkFixup(dev, hardList);
632 static int yaffs2_WriteCheckpointSum(yaffs_Device *dev)
637 yaffs2_GetCheckpointSum(dev, &checkpointSum);
639 ok = (yaffs2_CheckpointWrite(dev, &checkpointSum, sizeof(checkpointSum)) == sizeof(checkpointSum));
647 static int yaffs2_ReadCheckpointSum(yaffs_Device *dev)
649 __u32 checkpointSum0;
650 __u32 checkpointSum1;
653 yaffs2_GetCheckpointSum(dev, &checkpointSum0);
655 ok = (yaffs2_CheckpointRead(dev, &checkpointSum1, sizeof(checkpointSum1)) == sizeof(checkpointSum1));
660 if (checkpointSum0 != checkpointSum1)
667 static int yaffs2_WriteCheckpointData(yaffs_Device *dev)
671 if (!yaffs2_CheckpointRequired(dev)) {
672 T(YAFFS_TRACE_CHECKPOINT, (TSTR("skipping checkpoint write" TENDSTR)));
677 ok = yaffs2_CheckpointOpen(dev, 1);
680 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint validity" TENDSTR)));
681 ok = yaffs2_WriteCheckpointValidityMarker(dev, 1);
684 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint device" TENDSTR)));
685 ok = yaffs2_WriteCheckpointDevice(dev);
688 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint objects" TENDSTR)));
689 ok = yaffs2_WriteCheckpointObjects(dev);
692 T(YAFFS_TRACE_CHECKPOINT, (TSTR("write checkpoint validity" TENDSTR)));
693 ok = yaffs2_WriteCheckpointValidityMarker(dev, 0);
697 ok = yaffs2_WriteCheckpointSum(dev);
699 if (!yaffs2_CheckpointClose(dev))
703 dev->isCheckpointed = 1;
705 dev->isCheckpointed = 0;
707 return dev->isCheckpointed;
710 static int yaffs2_ReadCheckpointData(yaffs_Device *dev)
714 if(!dev->param.isYaffs2)
717 if (ok && dev->param.skipCheckpointRead) {
718 T(YAFFS_TRACE_CHECKPOINT, (TSTR("skipping checkpoint read" TENDSTR)));
723 ok = yaffs2_CheckpointOpen(dev, 0); /* open for read */
726 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint validity" TENDSTR)));
727 ok = yaffs2_ReadCheckpointValidityMarker(dev, 1);
730 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint device" TENDSTR)));
731 ok = yaffs2_ReadCheckpointDevice(dev);
734 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint objects" TENDSTR)));
735 ok = yaffs2_ReadCheckpointObjects(dev);
738 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint validity" TENDSTR)));
739 ok = yaffs2_ReadCheckpointValidityMarker(dev, 0);
743 ok = yaffs2_ReadCheckpointSum(dev);
744 T(YAFFS_TRACE_CHECKPOINT, (TSTR("read checkpoint checksum %d" TENDSTR), ok));
747 if (!yaffs2_CheckpointClose(dev))
751 dev->isCheckpointed = 1;
753 dev->isCheckpointed = 0;
759 void yaffs2_InvalidateCheckpoint(yaffs_Device *dev)
761 if (dev->isCheckpointed ||
762 dev->blocksInCheckpoint > 0) {
763 dev->isCheckpointed = 0;
764 yaffs2_CheckpointInvalidateStream(dev);
766 if (dev->param.markSuperBlockDirty)
767 dev->param.markSuperBlockDirty(dev);
771 int yaffs_CheckpointSave(yaffs_Device *dev)
774 T(YAFFS_TRACE_CHECKPOINT, (TSTR("save entry: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
776 yaffs_VerifyObjects(dev);
777 yaffs_VerifyBlocks(dev);
778 yaffs_VerifyFreeChunks(dev);
780 if (!dev->isCheckpointed) {
781 yaffs2_InvalidateCheckpoint(dev);
782 yaffs2_WriteCheckpointData(dev);
785 T(YAFFS_TRACE_ALWAYS, (TSTR("save exit: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
787 return dev->isCheckpointed;
790 int yaffs2_CheckpointRestore(yaffs_Device *dev)
793 T(YAFFS_TRACE_CHECKPOINT, (TSTR("restore entry: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
795 retval = yaffs2_ReadCheckpointData(dev);
797 if (dev->isCheckpointed) {
798 yaffs_VerifyObjects(dev);
799 yaffs_VerifyBlocks(dev);
800 yaffs_VerifyFreeChunks(dev);
803 T(YAFFS_TRACE_CHECKPOINT, (TSTR("restore exit: isCheckpointed %d"TENDSTR), dev->isCheckpointed));
808 int yaffs2_HandleHole(yaffs_Object *obj, loff_t newSize)
810 /* if newsSize > oldFileSize.
811 * We're going to be writing a hole.
812 * If the hole is small then write zeros otherwise write a start of hole marker.
819 int result = YAFFS_OK;
820 yaffs_Device *dev = NULL;
822 __u8 *localBuffer = NULL;
824 int smallIncreaseOk = 0;
829 if(obj->variantType != YAFFS_OBJECT_TYPE_FILE)
834 /* Bail out if not yaffs2 mode */
835 if(!dev->param.isYaffs2)
838 oldFileSize = obj->variant.fileVariant.fileSize;
840 if (newSize <= oldFileSize)
843 increase = newSize - oldFileSize;
845 if(increase < YAFFS_SMALL_HOLE_THRESHOLD * dev->nDataBytesPerChunk &&
846 yaffs_CheckSpaceForAllocation(dev, YAFFS_SMALL_HOLE_THRESHOLD + 1))
852 localBuffer= yaffs_GetTempBuffer(dev, __LINE__);
855 /* fill hole with zero bytes */
856 int pos = oldFileSize;
859 memset(localBuffer,0,dev->nDataBytesPerChunk);
862 while(increase > 0 && smallIncreaseOk){
863 thisWrite = increase;
864 if(thisWrite > dev->nDataBytesPerChunk)
865 thisWrite = dev->nDataBytesPerChunk;
866 written = yaffs_DoWriteDataToFile(obj,localBuffer,pos,thisWrite,0);
867 if(written == thisWrite){
869 increase -= thisWrite;
874 yaffs_ReleaseTempBuffer(dev,localBuffer,__LINE__);
876 /* If we were out of space then reverse any chunks we've added */
878 yaffs_ResizeDown(obj, oldFileSize);
881 if (!smallIncreaseOk &&
883 obj->parent->objectId != YAFFS_OBJECTID_UNLINKED &&
884 obj->parent->objectId != YAFFS_OBJECTID_DELETED){
885 /* Write a hole start header with the old file size */
886 yaffs_UpdateObjectHeader(obj, NULL, 0, 1, 0, NULL);
900 static int yaffs2_ybicmp(const void *a, const void *b)
902 register int aseq = ((yaffs_BlockIndex *)a)->seq;
903 register int bseq = ((yaffs_BlockIndex *)b)->seq;
904 register int ablock = ((yaffs_BlockIndex *)a)->block;
905 register int bblock = ((yaffs_BlockIndex *)b)->block;
907 return ablock - bblock;
912 int yaffs2_ScanBackwards(yaffs_Device *dev)
914 yaffs_ExtendedTags tags;
919 int nBlocksToScan = 0;
925 yaffs_BlockState state;
926 yaffs_Object *hardList = NULL;
928 __u32 sequenceNumber;
929 yaffs_ObjectHeader *oh;
931 yaffs_Object *parent;
932 int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
938 int foundChunksInBlock;
939 int equivalentObjectId;
940 int alloc_failed = 0;
943 yaffs_BlockIndex *blockIndex = NULL;
944 int altBlockIndex = 0;
948 ("yaffs2_ScanBackwards starts intstartblk %d intendblk %d..."
949 TENDSTR), dev->internalStartBlock, dev->internalEndBlock));
952 dev->sequenceNumber = YAFFS_LOWEST_SEQUENCE_NUMBER;
954 blockIndex = YMALLOC(nBlocks * sizeof(yaffs_BlockIndex));
957 blockIndex = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockIndex));
963 (TSTR("yaffs2_ScanBackwards() could not allocate block index!" TENDSTR)));
967 dev->blocksInCheckpoint = 0;
969 chunkData = yaffs_GetTempBuffer(dev, __LINE__);
971 /* Scan all the blocks to determine their state */
973 for (blk = dev->internalStartBlock; blk <= dev->internalEndBlock; blk++) {
974 yaffs_ClearChunkBits(dev, blk);
976 bi->softDeletions = 0;
978 yaffs_QueryInitialBlockState(dev, blk, &state, &sequenceNumber);
980 bi->blockState = state;
981 bi->sequenceNumber = sequenceNumber;
983 if (bi->sequenceNumber == YAFFS_SEQUENCE_CHECKPOINT_DATA)
984 bi->blockState = state = YAFFS_BLOCK_STATE_CHECKPOINT;
985 if (bi->sequenceNumber == YAFFS_SEQUENCE_BAD_BLOCK)
986 bi->blockState = state = YAFFS_BLOCK_STATE_DEAD;
988 T(YAFFS_TRACE_SCAN_DEBUG,
989 (TSTR("Block scanning block %d state %d seq %d" TENDSTR), blk,
990 state, sequenceNumber));
993 if (state == YAFFS_BLOCK_STATE_CHECKPOINT) {
994 dev->blocksInCheckpoint++;
996 } else if (state == YAFFS_BLOCK_STATE_DEAD) {
997 T(YAFFS_TRACE_BAD_BLOCKS,
998 (TSTR("block %d is bad" TENDSTR), blk));
999 } else if (state == YAFFS_BLOCK_STATE_EMPTY) {
1000 T(YAFFS_TRACE_SCAN_DEBUG,
1001 (TSTR("Block empty " TENDSTR)));
1002 dev->nErasedBlocks++;
1003 dev->nFreeChunks += dev->param.nChunksPerBlock;
1004 } else if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1006 /* Determine the highest sequence number */
1007 if (sequenceNumber >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
1008 sequenceNumber < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
1010 blockIndex[nBlocksToScan].seq = sequenceNumber;
1011 blockIndex[nBlocksToScan].block = blk;
1015 if (sequenceNumber >= dev->sequenceNumber)
1016 dev->sequenceNumber = sequenceNumber;
1018 /* TODO: Nasty sequence number! */
1021 ("Block scanning block %d has bad sequence number %d"
1022 TENDSTR), blk, sequenceNumber));
1030 (TSTR("%d blocks to be sorted..." TENDSTR), nBlocksToScan));
1036 /* Sort the blocks by sequence number*/
1037 yaffs_qsort(blockIndex, nBlocksToScan, sizeof(yaffs_BlockIndex), yaffs2_ybicmp);
1041 T(YAFFS_TRACE_SCAN, (TSTR("...done" TENDSTR)));
1043 /* Now scan the blocks looking at the data. */
1045 endIterator = nBlocksToScan - 1;
1046 T(YAFFS_TRACE_SCAN_DEBUG,
1047 (TSTR("%d blocks to be scanned" TENDSTR), nBlocksToScan));
1049 /* For each block.... backwards */
1050 for (blockIterator = endIterator; !alloc_failed && blockIterator >= startIterator;
1052 /* Cooperative multitasking! This loop can run for so
1053 long that watchdog timers expire. */
1056 /* get the block to scan in the correct order */
1057 blk = blockIndex[blockIterator].block;
1059 bi = yaffs_GetBlockInfo(dev, blk);
1062 state = bi->blockState;
1066 /* For each chunk in each block that needs scanning.... */
1067 foundChunksInBlock = 0;
1068 for (c = dev->param.nChunksPerBlock - 1;
1069 !alloc_failed && c >= 0 &&
1070 (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1071 state == YAFFS_BLOCK_STATE_ALLOCATING); c--) {
1072 /* Scan backwards...
1073 * Read the tags and decide what to do
1076 chunk = blk * dev->param.nChunksPerBlock + c;
1078 result = yaffs_ReadChunkWithTagsFromNAND(dev, chunk, NULL,
1081 /* Let's have a good look at this chunk... */
1083 if (!tags.chunkUsed) {
1084 /* An unassigned chunk in the block.
1085 * If there are used chunks after this one, then
1086 * it is a chunk that was skipped due to failing the erased
1087 * check. Just skip it so that it can be deleted.
1088 * But, more typically, We get here when this is an unallocated
1089 * chunk and his means that either the block is empty or
1090 * this is the one being allocated from
1093 if (foundChunksInBlock) {
1094 /* This is a chunk that was skipped due to failing the erased check */
1095 } else if (c == 0) {
1096 /* We're looking at the first chunk in the block so the block is unused */
1097 state = YAFFS_BLOCK_STATE_EMPTY;
1098 dev->nErasedBlocks++;
1100 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
1101 state == YAFFS_BLOCK_STATE_ALLOCATING) {
1102 if (dev->sequenceNumber == bi->sequenceNumber) {
1103 /* this is the block being allocated from */
1107 (" Allocating from %d %d"
1110 state = YAFFS_BLOCK_STATE_ALLOCATING;
1111 dev->allocationBlock = blk;
1112 dev->allocationPage = c;
1113 dev->allocationBlockFinder = blk;
1115 /* This is a partially written block that is not
1116 * the current allocation block.
1120 (TSTR("Partially written block %d detected" TENDSTR),
1128 } else if (tags.eccResult == YAFFS_ECC_RESULT_UNFIXED) {
1130 (TSTR(" Unfixed ECC in chunk(%d:%d), chunk ignored"TENDSTR),
1135 } else if (tags.objectId > YAFFS_MAX_OBJECT_ID ||
1136 tags.chunkId > YAFFS_MAX_CHUNK_ID ||
1137 (tags.chunkId > 0 && tags.byteCount > dev->nDataBytesPerChunk) ||
1138 tags.sequenceNumber != bi->sequenceNumber ) {
1140 (TSTR("Chunk (%d:%d) with bad tags:obj = %d, chunkId = %d, byteCount = %d, ignored"TENDSTR),
1141 blk, c,tags.objectId, tags.chunkId, tags.byteCount));
1145 } else if (tags.chunkId > 0) {
1146 /* chunkId > 0 so it is a data chunk... */
1147 unsigned int endpos;
1149 (tags.chunkId - 1) * dev->nDataBytesPerChunk;
1151 foundChunksInBlock = 1;
1154 yaffs_SetChunkBit(dev, blk, c);
1157 in = yaffs_FindOrCreateObjectByNumber(dev,
1160 YAFFS_OBJECT_TYPE_FILE);
1167 in->variantType == YAFFS_OBJECT_TYPE_FILE
1168 && chunkBase < in->variant.fileVariant.shrinkSize) {
1169 /* This has not been invalidated by a resize */
1170 if (!yaffs_PutChunkIntoFile(in, tags.chunkId, chunk, -1)) {
1174 /* File size is calculated by looking at the data chunks if we have not
1175 * seen an object header yet. Stop this practice once we find an object header.
1177 endpos = chunkBase + tags.byteCount;
1179 if (!in->valid && /* have not got an object header yet */
1180 in->variant.fileVariant.scannedFileSize < endpos) {
1181 in->variant.fileVariant.scannedFileSize = endpos;
1182 in->variant.fileVariant.fileSize = endpos;
1186 /* This chunk has been invalidated by a resize, or a past file deletion
1187 * so delete the chunk*/
1188 yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
1192 /* chunkId == 0, so it is an ObjectHeader.
1193 * Thus, we read in the object header and make the object
1195 foundChunksInBlock = 1;
1197 yaffs_SetChunkBit(dev, blk, c);
1203 if (tags.extraHeaderInfoAvailable) {
1204 in = yaffs_FindOrCreateObjectByNumber(dev,
1206 tags.extraObjectType);
1212 (!in->valid && dev->param.disableLazyLoad) ||
1213 tags.extraShadows ||
1215 (tags.objectId == YAFFS_OBJECTID_ROOT ||
1216 tags.objectId == YAFFS_OBJECTID_LOSTNFOUND))) {
1218 /* If we don't have valid info then we need to read the chunk
1219 * TODO In future we can probably defer reading the chunk and
1220 * living with invalid data until needed.
1223 result = yaffs_ReadChunkWithTagsFromNAND(dev,
1228 oh = (yaffs_ObjectHeader *) chunkData;
1230 if (dev->param.inbandTags) {
1231 /* Fix up the header if they got corrupted by inband tags */
1232 oh->shadowsObject = oh->inbandShadowsObject;
1233 oh->isShrink = oh->inbandIsShrink;
1237 in = yaffs_FindOrCreateObjectByNumber(dev, tags.objectId, oh->type);
1245 /* TODO Hoosterman we have a problem! */
1246 T(YAFFS_TRACE_ERROR,
1248 ("yaffs tragedy: Could not make object for object %d at chunk %d during scan"
1249 TENDSTR), tags.objectId, chunk));
1254 /* We have already filled this one.
1255 * We have a duplicate that will be discarded, but
1256 * we first have to suck out resize info if it is a file.
1259 if ((in->variantType == YAFFS_OBJECT_TYPE_FILE) &&
1261 oh->type == YAFFS_OBJECT_TYPE_FILE) ||
1262 (tags.extraHeaderInfoAvailable &&
1263 tags.extraObjectType == YAFFS_OBJECT_TYPE_FILE))) {
1265 (oh) ? oh->fileSize : tags.
1267 __u32 parentObjectId =
1269 parentObjectId : tags.
1270 extraParentObjectId;
1274 (oh) ? oh->isShrink : tags.
1275 extraIsShrinkHeader;
1277 /* If it is deleted (unlinked at start also means deleted)
1278 * we treat the file size as being zeroed at this point.
1280 if (parentObjectId ==
1281 YAFFS_OBJECTID_DELETED
1282 || parentObjectId ==
1283 YAFFS_OBJECTID_UNLINKED) {
1288 if (isShrink && in->variant.fileVariant.shrinkSize > thisSize)
1289 in->variant.fileVariant.shrinkSize = thisSize;
1292 bi->hasShrinkHeader = 1;
1295 /* Use existing - destroy this one. */
1296 yaffs_DeleteChunk(dev, chunk, 1, __LINE__);
1300 if (!in->valid && in->variantType !=
1301 (oh ? oh->type : tags.extraObjectType))
1302 T(YAFFS_TRACE_ERROR, (
1303 TSTR("yaffs tragedy: Bad object type, "
1304 TCONT("%d != %d, for object %d at chunk ")
1305 TCONT("%d during scan")
1307 oh->type : tags.extraObjectType,
1308 in->variantType, tags.objectId,
1312 (tags.objectId == YAFFS_OBJECTID_ROOT ||
1314 YAFFS_OBJECTID_LOSTNFOUND)) {
1315 /* We only load some info, don't fiddle with directory structure */
1320 in->yst_mode = oh->yst_mode;
1321 #ifdef CONFIG_YAFFS_WINCE
1322 in->win_atime[0] = oh->win_atime[0];
1323 in->win_ctime[0] = oh->win_ctime[0];
1324 in->win_mtime[0] = oh->win_mtime[0];
1325 in->win_atime[1] = oh->win_atime[1];
1326 in->win_ctime[1] = oh->win_ctime[1];
1327 in->win_mtime[1] = oh->win_mtime[1];
1329 in->yst_uid = oh->yst_uid;
1330 in->yst_gid = oh->yst_gid;
1331 in->yst_atime = oh->yst_atime;
1332 in->yst_mtime = oh->yst_mtime;
1333 in->yst_ctime = oh->yst_ctime;
1334 in->yst_rdev = oh->yst_rdev;
1342 in->hdrChunk = chunk;
1344 } else if (!in->valid) {
1345 /* we need to load this info */
1348 in->hdrChunk = chunk;
1351 in->variantType = oh->type;
1353 in->yst_mode = oh->yst_mode;
1354 #ifdef CONFIG_YAFFS_WINCE
1355 in->win_atime[0] = oh->win_atime[0];
1356 in->win_ctime[0] = oh->win_ctime[0];
1357 in->win_mtime[0] = oh->win_mtime[0];
1358 in->win_atime[1] = oh->win_atime[1];
1359 in->win_ctime[1] = oh->win_ctime[1];
1360 in->win_mtime[1] = oh->win_mtime[1];
1362 in->yst_uid = oh->yst_uid;
1363 in->yst_gid = oh->yst_gid;
1364 in->yst_atime = oh->yst_atime;
1365 in->yst_mtime = oh->yst_mtime;
1366 in->yst_ctime = oh->yst_ctime;
1367 in->yst_rdev = oh->yst_rdev;
1370 if (oh->shadowsObject > 0)
1371 yaffs_HandleShadowedObject(dev,
1378 yaffs_SetObjectNameFromOH(in, oh);
1380 yaffs_FindOrCreateObjectByNumber
1381 (dev, oh->parentObjectId,
1382 YAFFS_OBJECT_TYPE_DIRECTORY);
1384 fileSize = oh->fileSize;
1385 isShrink = oh->isShrink;
1386 equivalentObjectId = oh->equivalentObjectId;
1389 in->variantType = tags.extraObjectType;
1391 yaffs_FindOrCreateObjectByNumber
1392 (dev, tags.extraParentObjectId,
1393 YAFFS_OBJECT_TYPE_DIRECTORY);
1394 fileSize = tags.extraFileLength;
1395 isShrink = tags.extraIsShrinkHeader;
1396 equivalentObjectId = tags.extraEquivalentObjectId;
1405 /* directory stuff...
1409 if (parent && parent->variantType ==
1410 YAFFS_OBJECT_TYPE_UNKNOWN) {
1411 /* Set up as a directory */
1412 parent->variantType =
1413 YAFFS_OBJECT_TYPE_DIRECTORY;
1414 YINIT_LIST_HEAD(&parent->variant.
1417 } else if (!parent || parent->variantType !=
1418 YAFFS_OBJECT_TYPE_DIRECTORY) {
1419 /* Hoosterman, another problem....
1420 * We're trying to use a non-directory as a directory
1423 T(YAFFS_TRACE_ERROR,
1425 ("yaffs tragedy: attempting to use non-directory as a directory in scan. Put in lost+found."
1427 parent = dev->lostNFoundDir;
1430 yaffs_AddObjectToDirectory(parent, in);
1432 itsUnlinked = (parent == dev->deletedDir) ||
1433 (parent == dev->unlinkedDir);
1436 /* Mark the block as having a shrinkHeader */
1437 bi->hasShrinkHeader = 1;
1440 /* Note re hardlinks.
1441 * Since we might scan a hardlink before its equivalent object is scanned
1442 * we put them all in a list.
1443 * After scanning is complete, we should have all the objects, so we run
1444 * through this list and fix up all the chains.
1447 switch (in->variantType) {
1448 case YAFFS_OBJECT_TYPE_UNKNOWN:
1449 /* Todo got a problem */
1451 case YAFFS_OBJECT_TYPE_FILE:
1453 if (in->variant.fileVariant.
1454 scannedFileSize < fileSize) {
1455 /* This covers the case where the file size is greater
1456 * than where the data is
1457 * This will happen if the file is resized to be larger
1458 * than its current data extents.
1460 in->variant.fileVariant.fileSize = fileSize;
1461 in->variant.fileVariant.scannedFileSize = fileSize;
1464 if (in->variant.fileVariant.shrinkSize > fileSize)
1465 in->variant.fileVariant.shrinkSize = fileSize;
1469 case YAFFS_OBJECT_TYPE_HARDLINK:
1471 in->variant.hardLinkVariant.equivalentObjectId =
1473 in->hardLinks.next =
1474 (struct ylist_head *) hardList;
1478 case YAFFS_OBJECT_TYPE_DIRECTORY:
1481 case YAFFS_OBJECT_TYPE_SPECIAL:
1484 case YAFFS_OBJECT_TYPE_SYMLINK:
1486 in->variant.symLinkVariant.alias =
1487 yaffs_CloneString(oh->alias);
1488 if (!in->variant.symLinkVariant.alias)
1498 } /* End of scanning for each chunk */
1500 if (state == YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
1501 /* If we got this far while scanning, then the block is fully allocated. */
1502 state = YAFFS_BLOCK_STATE_FULL;
1506 bi->blockState = state;
1508 /* Now let's see if it was dirty */
1509 if (bi->pagesInUse == 0 &&
1510 !bi->hasShrinkHeader &&
1511 bi->blockState == YAFFS_BLOCK_STATE_FULL) {
1512 yaffs_BlockBecameDirty(dev, blk);
1517 yaffs_SkipRestOfBlock(dev);
1520 YFREE_ALT(blockIndex);
1524 /* Ok, we've done all the scanning.
1525 * Fix up the hard link chains.
1526 * We should now have scanned all the objects, now it's time to add these
1529 yaffs_HardlinkFixup(dev, hardList);
1532 yaffs_ReleaseTempBuffer(dev, chunkData, __LINE__);
1537 T(YAFFS_TRACE_SCAN, (TSTR("yaffs2_ScanBackwards ends" TENDSTR)));