yaffs_guts.c

YAFFS的升级版本YAFFS2

	// search harder.
	// else (we're doing a leasurely gc), then we only bother to do this if the
	// block has only a few pages in use.
	

	nonAggressiveSkip--;

	if(!aggressive &&(nonAggressiveSkip > 0))
	{
		return -1;
	}

	pagesInUse = (aggressive)? dev->nChunksPerBlock : YAFFS_PASSIVE_GC_CHUNKS + 1;
	if(aggressive)
	{
		iterations = dev->endBlock - dev->startBlock + 1;
	}
	else
	{
		iterations = dev->endBlock - dev->startBlock + 1;
		iterations = iterations / 16; 
		if(iterations > 200)
		{
			iterations = 200;
		}
	}
	
	for(i = 0; i <= iterations && pagesInUse > 0 ; i++)
	{
		b++;
		if ( b < dev->startBlock || b > dev->endBlock)
		{
			b =  dev->startBlock;
		}

		if(b < dev->startBlock || b > dev->endBlock)
		{
			T(YAFFS_TRACE_ERROR,(TSTR("**>> Block %d is not valid" TENDSTR),b));
			YBUG();
		}
		
		bi = yaffs_GetBlockInfo(dev,b);
		
		if(bi->blockState == YAFFS_BLOCK_STATE_FULL &&
		   (bi->pagesInUse - bi->softDeletions )< pagesInUse &&
		   yaffs_BlockNotDisqualifiedFromGC(dev,bi))
		{
			dirtiest = b;
			pagesInUse = (bi->pagesInUse - bi->softDeletions);
		}
	}
	
	dev->currentDirtyChecker = b;
	
	if(dirtiest > 0)
	{
		T(YAFFS_TRACE_GC,(TSTR("GC Selected block %d with %d free" TENDSTR),dirtiest,dev->nChunksPerBlock - pagesInUse));
	}
	
	dev->oldestDirtySequence = 0; // clear this
	
	if(dirtiest > 0)
	{
		nonAggressiveSkip = 4;
	}

	return dirtiest;
}


static void yaffs_BlockBecameDirty(yaffs_Device *dev,int blockNo)
{
	yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,blockNo);
	
	int erasedOk = 0;
	
	// If the block is still healthy erase it and mark as clean.
	// If the block has had a data failure, then retire it.
	bi->blockState = YAFFS_BLOCK_STATE_DIRTY;

	if(!bi->needsRetiring)
	{
		erasedOk = yaffs_EraseBlockInNAND(dev,blockNo);
		if(!erasedOk)
		{
			dev->nErasureFailures++;
			T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,(TSTR("**>> Erasure failed %d" TENDSTR),blockNo));
		}
	}

	if(erasedOk && (yaffs_traceMask & YAFFS_TRACE_ERASE))
	{
			int i;
			for(i = 0; i < dev->nChunksPerBlock; i++)
			{
					if(!yaffs_CheckChunkErased(dev,blockNo * dev->nChunksPerBlock + i))
					{
						T(YAFFS_TRACE_ERROR,(TSTR(">>Block %d erasure supposedly OK, but chunk %d not erased" TENDSTR),blockNo,i));
					}
			}
	}
	
	if( erasedOk )
	{
		// Clean it up...
		bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
		dev->nErasedBlocks++;
		bi->pagesInUse = 0;
		bi->softDeletions = 0;
		bi->hasShrinkHeader=0;
		yaffs_ClearChunkBits(dev,blockNo);
	
		T(YAFFS_TRACE_ERASE,(TSTR("Erased block %d" TENDSTR),blockNo));
	}
	else
	{
		yaffs_RetireBlock(dev,blockNo);
		T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,(TSTR("**>> Block %d retired" TENDSTR),blockNo));
	}
}

static void yaffs_DumpBlockStats(yaffs_Device *dev)
{
	int i,j;
	yaffs_BlockInfo *bi;
	
	for(i= dev->startBlock; i <=dev->endBlock; i++)
	{
		bi = yaffs_GetBlockInfo(dev,i);
		T(YAFFS_TRACE_ALLOCATE,(TSTR("%3d state %d shrink %d inuse %d/%d seq %d pages"),i,
		bi->blockState,bi->hasShrinkHeader,bi->pagesInUse,bi->softDeletions,bi->sequenceNumber));	
		
		for(j = 0; j < dev->nChunksPerBlock; j++)
		{
			if(yaffs_CheckChunkBit(dev,i,j))
			{
				T(YAFFS_TRACE_ALLOCATE,(TSTR(" %d"),j));

			}
		}
		T(YAFFS_TRACE_ALLOCATE,(TSTR(" " TENDSTR)));

	}
}


static int yaffs_FindBlockForAllocation(yaffs_Device *dev)
{
	int i;
	
	yaffs_BlockInfo *bi;
	
#if 0
	static int j = 0;
	j++;
	if(j < 0 || j > 100)
	{
		j = 0;
		yaffs_DumpBlockStats(dev);
	}
	
#endif
	
	if(dev->nErasedBlocks < 1)
	{
		// Hoosterman we've got a problem.
		// Can't get space to gc
		T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: no more eraased blocks" TENDSTR)));

		return -1;
	}
	
	// Find an empty block.
	
	for(i = dev->startBlock; i <= dev->endBlock; i++)
	{
		dev->allocationBlockFinder++;
		if(dev->allocationBlockFinder < dev->startBlock || dev->allocationBlockFinder> dev->endBlock) 
		{
			dev->allocationBlockFinder = dev->startBlock;
		}
		
		bi = yaffs_GetBlockInfo(dev,dev->allocationBlockFinder);

		if(bi->blockState == YAFFS_BLOCK_STATE_EMPTY)
		{
			bi->blockState = YAFFS_BLOCK_STATE_ALLOCATING;
			dev->sequenceNumber++;
			bi->sequenceNumber = dev->sequenceNumber;
			dev->nErasedBlocks--;		
			T(YAFFS_TRACE_ALLOCATE,(TSTR("Allocated block %d, seq  %d" TENDSTR),dev->allocationBlockFinder,dev->sequenceNumber));	
			return dev->allocationBlockFinder;
		}
	}
		T(YAFFS_TRACE_ERROR, (TSTR("yaffs tragedy: no more eraased blocks, but there should have been one" TENDSTR)));

	
	return -1;	
}



static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve)
{
	int retVal;
	yaffs_BlockInfo *bi;
	
	if(dev->allocationBlock < 0)
	{
		// Get next block to allocate off
		dev->allocationBlock = yaffs_FindBlockForAllocation(dev);
		dev->allocationPage = 0;
	}
	
	if(!useReserve &&  dev->nErasedBlocks </*=*/ dev->nReservedBlocks)
	{
		// Not enough space to allocate unless we're allowed to use the reserve.
		return -1;
	}

	if(dev->nErasedBlocks < dev->nReservedBlocks && dev->allocationPage == 0)
	{
		T(YAFFS_TRACE_ALLOCATE,(TSTR("Allocating reserve" TENDSTR)));	
	}

	
	// Next page please....
	if(dev->allocationBlock >= 0)
	{
		bi = yaffs_GetBlockInfo(dev,dev->allocationBlock);
		
		retVal = (dev->allocationBlock * dev->nChunksPerBlock) + 
			  	  dev->allocationPage;
		bi->pagesInUse++;
		yaffs_SetChunkBit(dev,dev->allocationBlock,dev->allocationPage);

		dev->allocationPage++;
		
		dev->nFreeChunks--;
		
		// If the block is full set the state to full
		if(dev->allocationPage >= dev->nChunksPerBlock)
		{
			bi->blockState = YAFFS_BLOCK_STATE_FULL;
			dev->allocationBlock = -1;
		}


		return retVal;
		
	}
	T(YAFFS_TRACE_ERROR,(TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));

	return -1;	
}


// To determine if we have enough space we just look at the 
// number of erased blocks.
// The cache is allowed to use reserved blocks.

static int yaffs_CheckSpaceForChunkCache(yaffs_Device *dev)
{
	return (dev->nErasedBlocks >= dev->nReservedBlocks);
}


static int yaffs_GetErasedChunks(yaffs_Device *dev)
{
		int n;

		n = dev->nErasedBlocks * dev->nChunksPerBlock;

		if(dev->allocationBlock> 0)
		{
			n += (dev->nChunksPerBlock - dev->allocationPage);
		}

		return n;

}

int  yaffs_GarbageCollectBlock(yaffs_Device *dev,int block)
{
	int oldChunk;
	int newChunk;
	int chunkInBlock;
	int markNAND;
	int retVal = YAFFS_OK;
	int cleanups = 0;
	int i;

	int chunksBefore = yaffs_GetErasedChunks(dev);
	int chunksAfter;

	yaffs_ExtendedTags  tags;
	
	yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,block);
	
	yaffs_Object *object;
	
	bi->blockState = YAFFS_BLOCK_STATE_COLLECTING;

	T(YAFFS_TRACE_TRACING,(TSTR("Collecting block %d, in use %d, shrink %d, " TENDSTR),block,bi->pagesInUse,bi->hasShrinkHeader));
	//T(("Collecting block %d n %d bits %x\n",block, bi->pagesInUse, bi->pageBits));	

	bi->hasShrinkHeader = 0; // clear the flag so that the block can erase


	if(!yaffs_StillSomeChunkBits(dev,block))
	{
		T(YAFFS_TRACE_TRACING,(TSTR("Collecting block %d that has no chunks in use" TENDSTR),block));
		yaffs_BlockBecameDirty(dev,block);
	}
	else
	{

			__u8  *buffer = yaffs_GetTempBuffer(dev,__LINE__);

	for(chunkInBlock = 0,oldChunk = block * dev->nChunksPerBlock; 
	    chunkInBlock < dev->nChunksPerBlock && yaffs_StillSomeChunkBits(dev,block);
	    chunkInBlock++, oldChunk++ )
	{
		if(yaffs_CheckChunkBit(dev,block,chunkInBlock))
		{
			
			// This page is in use and might need to be copied off
			
			markNAND = 1;
			
			//T(("copying page %x from %d to %d\n",mask,oldChunk,newChunk));
			
			yaffs_InitialiseTags(&tags);
			
			yaffs_ReadChunkWithTagsFromNAND(dev,oldChunk,buffer, &tags);

			object = yaffs_FindObjectByNumber(dev,tags.objectId);
			
			T(YAFFS_TRACE_GC_DETAIL,(TSTR("Collecting page %d, %d %d %d " TENDSTR),chunkInBlock,tags.objectId,tags.chunkId,tags.byteCount));
			
			if(!object)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("page %d in gc has no object " TENDSTR),oldChunk));
			}
			
			if(object && object->deleted && tags.chunkId != 0)
			{
				// Data chunk in a deleted file, throw it away
				// It's a deleted data chunk,
				// No need to copy this, just forget about it and fix up the
				// object.
				
				//yaffs_PutChunkIntoFile(object, tags.chunkId, 0,0); 
				object->nDataChunks--;
				
				if(object->nDataChunks <= 0)
				{
					// remeber to clean up the object
					dev->gcCleanupList[cleanups] = tags.objectId;
					cleanups++;
 				}
				markNAND = 0;
			}
			else if( 0 /* Todo object && object->deleted && object->nDataChunks == 0 */)
			{
				// Deleted object header with no data chunks.
				// Can be discarded and the file deleted.
				object->chunkId = 0;
				yaffs_FreeTnode(object->myDev,object->variant.fileVariant.top);
				object->variant.fileVariant.top = NULL;
				yaffs_DoGenericObjectDeletion(object);
				
			}
			else if(object)
			{
				// It's either a data chunk in a live file or
				// an ObjectHeader, so we're interested in it.
				// NB Need to keep the ObjectHeaders of deleted files
				// until the whole file has been deleted off
				tags.serialNumber++;

				dev->nGCCopies++;

				newChunk = yaffs_WriteNewChunkWithTagsToNAND(dev, buffer, &tags,1);
			
				if(newChunk < 0)
				{
					retVal =  YAFFS_FAIL;
				}
				else
				{
			
					// Ok, now fix up the Tnodes etc.
			
					if(tags.chunkId == 0)
					{
						// It's a header
						object->chunkId = newChunk;
						object->serial = tags.serialNumber;
					}
					else
					{
						// It's a data chunk
						yaffs_PutChunkIntoFile(object, tags.chunkId, newChunk,0);
					}
				}
			}
			
			yaffs_DeleteChunk(dev,oldChunk,markNAND,__LINE__);			
			
		}
	}

	yaffs_ReleaseTempBuffer(dev,buffer,__LINE__);


	// Do any required cleanups
	for(i = 0; i < cleanups; i++)
	{						
		// Time to delete the file too
		object =  yaffs_FindObjectByNumber(dev,dev->gcCleanupList[i]);
		if(object)
		{
			yaffs_FreeTnode(dev,object->variant.fileVariant.top);
			object->variant.fileVariant.top = NULL;
			T(YAFFS_TRACE_GC,(TSTR("yaffs: About to finally delete object %d" TENDSTR),object->objectId));
			yaffs_DoGenericObjectDeletion(object);
		}

	}

	}

	if(chunksBefore >= (chunksAfter = yaffs_GetErasedChunks(dev)))
	{
			T(YAFFS_TRACE_GC,(TSTR("gc did not increase free chunks before %d after %d" TENDSTR),chunksBefore,chunksAfter));
	}
			
	return YAFFS_OK;
}

#if 0
static yaffs_Object *yaffs_FindDeletedUnlinkedFile(yaffs_Device *dev)
{
	// find a file to delete
	struct list_head *i;	
	yaffs_Object *l;


	//Scan the unlinked files looking for one to delete
	list_for_each(i,&dev->unlinkedDir->variant.directoryVariant.children)
	{
		if(i)
		{
			l = list_entry(i, yaffs_Object,siblings);
			if(l->deleted)
			{
				return l;			
			}
		}
	}	
	return NULL;
}


static void yaffs_DoUnlinkedFileDeletion(yaffs_Device *dev)
{
	// This does background deletion on unlinked files.. only deleted ones.
	// If we don't have a file we're working on then find one
	if(!dev->unlinkedDeletion && dev->nDeletedFiles > 0)
	{
		dev->unlinkedDeletion = yaffs_FindDeletedUnlinkedFile(dev);
	}
	
	// OK, we're working on a file...
	if(dev->unlinkedDeletion)
	{
		yaffs_Object *obj = dev->unlinkedDeletion;
		int delresult;
		int limit; // Number of chunks to delete in a file.
				   // NB this can be exceeded, but not by much.
				   
		limit = -1;

		delresult = yaffs_DeleteWorker(obj, obj->variant.fileVariant.top, obj->variant.fileVariant.topLevel, 0,&limit);
		
		if(obj->nDataChunks == 0)
		{
			// Done all the deleting of data chunks.
			// Now dump the header and clean up
			yaffs_FreeTnode(dev,obj->variant.fileVariant.top);
			obj->variant.fileVariant.top = NULL;
			yaffs_DoGenericObjectDeletion(obj);
			dev->nDeletedFiles--;
			dev->nUnlinkedFiles--;
			dev->nBackgroundDeletions++;
			dev->unlinkedDeletion = NULL;	
		}
	}
}

#endif

#if 0
#define YAFFS_GARBAGE_COLLECT_LOW_WATER 2
static int yaffs_CheckGarbageCollection(yaffs_Device *dev)
{
	int block;
	int aggressive=0;
	
	//yaffs_DoUnlinkedFileDeletion(dev);
	
	if(dev->nErasedBlocks <= (dev->nReservedBlocks + YAFFS_GARBAGE_COLLECT_LOW_WATER))
	{
		aggressive = 1;
	}		
	
	if(aggressive)
	{
		block = yaffs_FindBlockForGarbageCollection(dev,aggressive);
		
		if(block >= 0)
		{
			dev->garbageCollections++;
			return yaffs_GarbageCollectBlock(dev,block);
		}	
		else
		{
			return YAFFS_FAIL;
		}
	}

	return YAFFS_OK;
}
#endif

// New garbage collector
// If we're very low on erased blocks then we do aggressive garbage collection
// otherwise we do "leasurely" garbage collection.
// Aggressive gc looks further (whole array) and will accept dirtier blocks.