yaffs_guts.c

full package of jaffs file system

					}
			}
	}
	
	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.
// Passive gc only inspects smaller areas and will only accept cleaner blocks.
//
// The idea is to help clear out space in a more spread-out manner.
// Dunno if it really does anything useful.
//
int yaffs_CheckGarbageCollection(yaffs_Device *dev)
{
	int block;
	int aggressive; 
	int gcOk = YAFFS_OK;
	int maxTries = 0;
	
	//yaffs_DoUnlinkedFileDeletion(dev);

	// This loop should pass the first time.
	// We'll only see looping here if the erase of the collected block fails.
	
	do{
		maxTries++;
		if(dev->nErasedBlocks <= (dev->nReservedBlocks + 2))
		{
			// We need a block soon...
			aggressive = 1;
		}
		else 
		{
			// We're in no hurry
			aggressive = 0;
		}
	
		block = yaffs_FindBlockForGarbageCollection(dev,aggressive);
	
		if(block > 0)
		{
			dev->garbageCollections++;
			if(!aggressive)
			{
				dev->passiveGarbageCollections++;
			}

			T(YAFFS_TRACE_GC,(TSTR("yaffs: GC erasedBlocks %d aggressive %d" TENDSTR),dev->nErasedBlocks,aggressive));

			gcOk =  yaffs_GarbageCollectBlock(dev,block);
		}

		if(dev->nErasedBlocks <= (dev->nReservedBlocks + 1)) 
		{
			T(YAFFS_TRACE_GC,(TSTR("yaffs: GC !!!no reclaim!!! erasedBlocks %d after try %d block %d" TENDSTR),dev->nErasedBlocks,maxTries,block));
		}
	} while((dev->nErasedBlocks <= (dev->nReservedBlocks + 1)) && (block > 0) && (maxTries < 5));

	return aggressive ? gcOk: YAFFS_OK;
}


//////////////////////////// TAGS ///////////////////////////////////////


void yaffs_InitialiseTags(yaffs_ExtendedTags *tags)
{
	memset(tags,0,sizeof(yaffs_ExtendedTags));
	tags->validMarker0 = 0xAAAAAAAA;
	tags->validMarker1 = 0x55555555;
}

static int yaffs_ValidateTags(yaffs_ExtendedTags *tags)
{
	return (tags->validMarker0 == 0xAAAAAAAA &&	tags->validMarker1 == 0x55555555);

}


#if 0

void yaffs_CalcTagsECC(yaffs_Tags *tags)
{
	// Calculate an ecc
	
	unsigned char *b = ((yaffs_TagsUnion *)tags)->asBytes;
	unsigned  i,j;
	unsigned  ecc = 0;
	unsigned bit = 0;

	tags->ecc = 0;
	
	for(i = 0; i < 8; i++)
	{
		for(j = 1; j &0xff; j<<=1)
		{
			bit++;
			if(b[i] & j)
			{
				ecc ^= bit;
			}
		}
	}
	
	tags->ecc = ecc;
	
	
}

int  yaffs_CheckECCOnTags(yaffs_Tags *tags)
{
	unsigned ecc = tags->ecc;
	
	yaffs_CalcTagsECC(tags);
	
	ecc ^= tags->ecc;
	
	if(ecc && ecc <= 64)
	{
		// TODO: Handle the failure better. Retire?
		unsigned char *b = ((yaffs_TagsUnion *)tags)->asBytes;

		ecc--;
				
		b[ecc / 8] ^= (1 << (ecc & 7));
		
		// Now recvalc the ecc
		yaffs_CalcTagsECC(tags);
		
		return 1; // recovered error
	}
	else if(ecc)
	{
		// Wierd ecc failure value
		// TODO Ne