yaffs_guts.c

full package of jaffs file system

/*
 * YAFFS: Yet another FFS. A NAND-flash specific file system. 
 *
 * Copyright (C) 2002 Aleph One Ltd.
 *   for Toby Churchill Ltd and Brightstar Engineering
 *
 * Created by Charles Manning <[e-mail]>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 */
 //yaffs_guts.c

const char *yaffs_guts_c_version="$Id: yaffs_guts.c,v 1.4 2004/12/17 04:39:04 charles Exp $";

#include "yportenv.h"

#include "yaffsinterface.h"
#include "yaffs_guts.h"

#include "yaffs_tagscompat.h"

#ifdef CONFIG_YAFFS_WINCE
void yfsd_LockYAFFS(BOOL fsLockOnly);
void yfsd_UnlockYAFFS(BOOL fsLockOnly);
#endif

#define YAFFS_PASSIVE_GC_CHUNKS 2

#if 0
// Use Steven Hill's ECC struff instead
// External functions for ECC on data
void nand_calculate_ecc (const u_char *dat, u_char *ecc_code);
int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc);
#define yaffs_ECCCalculate(data,ecc) nand_calculate_ecc(data,ecc)
#define yaffs_ECCCorrect(data,read_ecc,calc_ecc) nand_correct_ecc(data,read_ecc,calc_ecc)
#else
#include "yaffs_ecc.h"
#endif

// countBits is a quick way of counting the number of bits in a byte.
// ie. countBits[n] holds the number of 1 bits in a byte with the value n.

static const char yaffs_countBitsTable[256] =
{
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};

static int yaffs_CountBits(__u8 x)
{
	int retVal;
	retVal = yaffs_countBitsTable[x];
	return retVal;
}


#if 0
// Stuff using yea olde tags
static void yaffs_LoadTagsIntoSpare(yaffs_Spare *sparePtr, yaffs_Tags *tagsPtr);
static void yaffs_GetTagsFromSpare(yaffs_Device *dev, yaffs_Spare *sparePtr,yaffs_Tags *tagsPtr);

static int yaffs_ReadChunkTagsFromNAND(yaffs_Device *dev,int chunkInNAND, yaffs_Tags *tags, int *chunkDeleted);
static int yaffs_TagsMatch(const yaffs_Tags *tags, int objectId, int chunkInObject, int chunkDeleted);
#else
#endif

// NAND access


static Y_INLINE int yaffs_ReadChunkWithTagsFromNAND(yaffs_Device *dev,int chunkInNAND, __u8 *buffer, yaffs_ExtendedTags *tags);
static Y_INLINE int yaffs_WriteChunkWithTagsToNAND(yaffs_Device *dev,int chunkInNAND, const __u8 *data, yaffs_ExtendedTags *tags);
static Y_INLINE int yaffs_MarkBlockBad(yaffs_Device *dev, int blockNo);
static Y_INLINE int yaffs_QueryInitialBlockState(yaffs_Device *dev,int blockNo, yaffs_BlockState *state,unsigned *sequenceNumber);
// Local prototypes
static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device *dev, const __u8 *buffer, yaffs_ExtendedTags *tags, int useReserve);
static int yaffs_CheckObjectHashSanity(yaffs_Device *dev);
static int yaffs_PutChunkIntoFile(yaffs_Object *in,int chunkInInode, int chunkInNAND, int inScan);

static yaffs_Object *yaffs_CreateNewObject(yaffs_Device *dev,int number,yaffs_ObjectType type);
static void yaffs_AddObjectToDirectory(yaffs_Object *directory, yaffs_Object *obj);
static int yaffs_UpdateObjectHeader(yaffs_Object *in,const YCHAR *name, int force,int isShrink);
static void yaffs_RemoveObjectFromDirectory(yaffs_Object *obj);
static int yaffs_CheckStructures(void);
static int yaffs_DeleteWorker(yaffs_Object *in, yaffs_Tnode *tn, __u32 level, int chunkOffset,int *limit);
static int yaffs_DoGenericObjectDeletion(yaffs_Object *in);

static yaffs_BlockInfo *yaffs_GetBlockInfo(yaffs_Device *dev,int blockNo);

static __u8 *yaffs_GetTempBuffer(yaffs_Device *dev,int lineNo);
static void yaffs_ReleaseTempBuffer(yaffs_Device *dev, __u8 *buffer, int lineNo);


static int  yaffs_ValidateTags(yaffs_ExtendedTags *tags);

// Robustification (if it ever comes about...)
static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND);
static void yaffs_HandleReadDataError(yaffs_Device *dev,int chunkInNAND);
static void yaffs_HandleWriteChunkError(yaffs_Device *dev,int chunkInNAND);
static void yaffs_HandleWriteChunkOk(yaffs_Device *dev,int chunkInNAND,const __u8 *data, const yaffs_ExtendedTags *tags);
static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND,  const yaffs_ExtendedTags *tags);

static int  yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND);

static int yaffs_UnlinkWorker(yaffs_Object *obj);
static void yaffs_DestroyObject(yaffs_Object *obj);

#if 0
static int yaffs_VerifyCompare(const __u8 *d0, const __u8 * d1, const yaffs_Spare *s0, const yaffs_Spare *s1,int dataSize);
#endif

static int yaffs_TagsMatch(const yaffs_ExtendedTags *tags, int objectId, int chunkInObject);


loff_t yaffs_GetFileSize(yaffs_Object *obj);


static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve);

#ifdef YAFFS_PARANOID
static int yaffs_CheckFileSanity(yaffs_Object *in);
#else
#define yaffs_CheckFileSanity(in)
#endif

static void yaffs_InvalidateWholeChunkCache(yaffs_Object *in);
static void yaffs_InvalidateChunkCache(yaffs_Object *object, int chunkId);

static int yaffs_ReadChunkWithTagsFromNAND(yaffs_Device *dev,int chunkInNAND, __u8 *buffer, yaffs_ExtendedTags *tags)
{
	if(dev->readChunkWithTagsFromNAND)
		return dev->readChunkWithTagsFromNAND(dev,chunkInNAND,buffer,tags);
	else
		return yaffs_TagsCompatabilityReadChunkWithTagsFromNAND(dev,chunkInNAND,buffer,tags);
}

static Y_INLINE int yaffs_WriteChunkWithTagsToNAND(yaffs_Device *dev,int chunkInNAND, const __u8 *buffer, yaffs_ExtendedTags *tags)
{
	if(tags)
	{
		tags->sequenceNumber = dev->sequenceNumber;
		tags->chunkUsed = 1;
		if(!yaffs_ValidateTags(tags))
		{
			T(YAFFS_TRACE_ERROR,(TSTR("Writing uninitialised tags" TENDSTR)));
			YBUG();
		}
		T(YAFFS_TRACE_WRITE,(TSTR("Writing chunk %d tags %d %d"TENDSTR),chunkInNAND,tags->objectId,tags->chunkId));
	}
	else
	{
			T(YAFFS_TRACE_ERROR,(TSTR("Writing with no tags" TENDSTR)));
			YBUG();
	}

	if(dev->writeChunkWithTagsToNAND)
		return dev->writeChunkWithTagsToNAND(dev,chunkInNAND,buffer,tags);
	else
		return yaffs_TagsCompatabilityWriteChunkWithTagsToNAND(dev,chunkInNAND,buffer,tags);
}

static Y_INLINE int yaffs_MarkBlockBad(yaffs_Device *dev, int blockNo)
{
	if(dev->markNANDBlockBad)
		return dev->markNANDBlockBad(dev,blockNo);
	else
		return yaffs_TagsCompatabilityMarkNANDBlockBad(dev,blockNo);
}
static Y_INLINE int yaffs_QueryInitialBlockState(yaffs_Device *dev,int blockNo, yaffs_BlockState *state, unsigned *sequenceNumber)
{
	if(dev->queryNANDBlock)
		return dev->queryNANDBlock(dev,blockNo,state,sequenceNumber);
	else
		return yaffs_TagsCompatabilityQueryNANDBlock(dev,blockNo,state,sequenceNumber);
}

int yaffs_EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND)
{
	int result;

	dev->nBlockErasures++;
	result = dev->eraseBlockInNAND(dev,blockInNAND);

	if(!result)result = dev->eraseBlockInNAND(dev,blockInNAND); // If at first we don't succeed, try again *once*.
	return result;
}

static int yaffs_InitialiseNAND(struct yaffs_DeviceStruct *dev)
{
	return dev->initialiseNAND(dev);
}




// Temporary buffer manipulations

static __u8 *yaffs_GetTempBuffer(yaffs_Device *dev,int lineNo)
{
	int i,j;
	for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
	{
		if(dev->tempBuffer[i].line == 0)
		{
			dev->tempBuffer[i].line = lineNo;
			if((i+1) > dev->maxTemp)
			{
				dev->maxTemp = i + 1;
				for(j = 0; j <= i; j++)
					dev->tempBuffer[j].maxLine = dev->tempBuffer[j].line;
			}	
			
			return dev->tempBuffer[i].buffer;
		}
	}

	T(YAFFS_TRACE_BUFFERS,(TSTR("Out of temp buffers at line %d, other held by lines:"),lineNo));
	for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
	{
		T(YAFFS_TRACE_BUFFERS,(TSTR(" %d "),dev->tempBuffer[i].line));
	}
	T(YAFFS_TRACE_BUFFERS,(TSTR(" "TENDSTR)));
	
	dev->unmanagedTempAllocations++;
	// Get an unmanaged one
	return YMALLOC(dev->nBytesPerChunk);	
	
	
}

static void yaffs_ReleaseTempBuffer(yaffs_Device *dev, __u8 *buffer, int lineNo)
{
	int i;
	for(i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
	{
		if(dev->tempBuffer[i].buffer == buffer)
		{
			dev->tempBuffer[i].line = 0;
			return;
		}
	}
	
	if(buffer)
	{
		// assume it is an unmanaged one.
		T(YAFFS_TRACE_BUFFERS,(TSTR("Releasing unmanaged temp buffer in line %d" TENDSTR),lineNo));
		YFREE(buffer);
		dev->unmanagedTempDeallocations++;
	}

}


// Chunk bitmap manipulations

static Y_INLINE __u8 *yaffs_BlockBits(yaffs_Device *dev, int blk)
{
	if(blk < dev->startBlock || blk > dev->endBlock)
	{
		T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs: BlockBits block %d is not valid" TENDSTR),blk));
		YBUG();
	}
	return dev->chunkBits + (dev->chunkBitmapStride * (blk - dev->startBlock));
}

static Y_INLINE void yaffs_ClearChunkBits(yaffs_Device *dev,int blk)
{
	__u8 *blkBits = yaffs_BlockBits(dev,blk);

	 memset(blkBits,0,dev->chunkBitmapStride);
}

static Y_INLINE void yaffs_ClearChunkBit(yaffs_Device *dev,int blk,int chunk)
{
	__u8 *blkBits = yaffs_BlockBits(dev,blk);
	
	blkBits[chunk/8] &=  ~ (1<<(chunk & 7));
}

static Y_INLINE void yaffs_SetChunkBit(yaffs_Device *dev,int blk,int chunk)
{
	__u8 *blkBits = yaffs_BlockBits(dev,blk);

	blkBits[chunk/8] |=   (1<<(chunk & 7));
}

static Y_INLINE int yaffs_CheckChunkBit(yaffs_Device *dev,int blk,int chunk)
{
	__u8 *blkBits = yaffs_BlockBits(dev,blk);
	return (blkBits[chunk/8] &  (1<<(chunk & 7))) ? 1 :0;
}

static Y_INLINE int yaffs_StillSomeChunkBits(yaffs_Device *dev,int blk)
{
	__u8 *blkBits = yaffs_BlockBits(dev,blk);
	int i;
	for(i = 0; i < dev->chunkBitmapStride; i++)
	{
		if(*blkBits) return 1;
		blkBits++;
	}
	return 0;
}

#if 0
// Function to manipulate block info
static  Y_INLINE yaffs_BlockInfo* yaffs_GetBlockInfo(yaffs_Device *dev, int blk)
{
	if(blk < dev->startBlock || blk > dev->endBlock)
	{
		T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs: getBlockInfo block %d is not valid" TENDSTR),blk));
		YBUG();
	}
	return &dev->blockInfo[blk - dev->startBlock];
}
#endif


static  Y_INLINE int yaffs_HashFunction(int n)
{
	return (n % YAFFS_NOBJECT_BUCKETS);
}


yaffs_Object *yaffs_Root(yaffs_Device *dev)
{
	return dev->rootDir;
}

yaffs_Object *yaffs_LostNFound(yaffs_Device *dev)
{
	return dev->lostNFoundDir;
}

#if 0
static int yaffs_WriteChunkToNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND, const __u8 *data, yaffs_Spare *spare)
{
	if(chunkInNAND < dev->startBlock * dev->nChunksPerBlock)
	{
		T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs chunk %d is not valid" TENDSTR),chunkInNAND));
		return YAFFS_FAIL;
	}

	dev->nPageWrites++;
	return dev->writeChunkToNAND(dev,chunkInNAND,data,spare);
}



static int yaffs_ReadChunkFromNAND(struct yaffs_DeviceStruct *dev,
							int chunkInNAND, 
							__u8 *data, 
							yaffs_Spare *spare, 
							int doErrorCorrection)
{
	int retVal;
	yaffs_Spare localSpare;

	dev->nPageReads++;
	
	

	
	if(!spare && data)
	{
		// If we don't have a real spare, then we use a local one.
		// Need this for the calculation of the ecc
		spare = &localSpare;
	}
	

	if(!dev->useNANDECC)
	{
		retVal  = dev->readChunkFromNAND(dev,chunkInNAND,data,spare);
		if(data && doErrorCorrection)
		{
			// Do ECC correction
			//Todo handle any errors
         	int eccResult1,eccResult2;
        	__u8 calcEcc[3];
                
			yaffs_ECCCalculate(data,calcEcc);
			eccResult1 = yaffs_ECCCorrect (data,spare->ecc1, calcEcc);
			yaffs_ECCCalculate(&data[256],calcEcc);
			eccResult2 = yaffs_ECCCorrect(&data[256],spare->ecc2, calcEcc);

			if(eccResult1>0)
			{
				T(YAFFS_TRACE_ERROR, (TSTR("**>>ecc error fix performed on chunk %d:0" TENDSTR),chunkInNAND));
				dev->eccFixed++;
			}
			else if(eccResult1<0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error unfixed on chunk %d:0" TENDSTR),chunkInNAND));
				dev->eccUnfixed++;
			}

			if(eccResult2>0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error fix performed on chunk %d:1" TENDSTR),chunkInNAND));
				dev->eccFixed++;
			}
			else if(eccResult2<0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error unfixed on chunk %d:1" TENDSTR),chunkInNAND));
				dev->eccUnfixed++;
			}

			if(eccResult1 || eccResult2)
			{
				// Hoosterman, we had a data problem on this page
				yaffs_HandleReadDataError(dev,chunkInNAND);
			}
		}
	}
	else
	{
        // Must allocate enough memory for spare+2*sizeof(int) for ecc results from device.
    	struct yaffs_NANDSpare nspare;
		retVal  = dev->readChunkFromNAND(dev,chunkInNAND,data,(yaffs_Spare*)&nspare);
		memcpy (spare, &nspare, sizeof(yaffs_Spare));
		if(data && doErrorCorrection)
		{
			if(nspare.eccres1>0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error fix performed on chunk %d:0" TENDSTR),chunkInNAND));
			}
			else if(nspare.eccres1<0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error unfixed on chunk %d:0" TENDSTR),chunkInNAND));
			}

			if(nspare.eccres2>0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error fix performed on chunk %d:1" TENDSTR),chunkInNAND));
			}
			else if(nspare.eccres2<0)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>>ecc error unfixed on chunk %d:1" TENDSTR),chunkInNAND));
			}

			if(nspare.eccres1 || nspare.eccres2)
			{
				// Hoosterman, we had a data problem on this page
				yaffs_HandleReadDataError(dev,chunkInNAND);
			}

		}
	}
	return retVal;
}

#endif



int yaffs_CheckFF(__u8 *buffer,int nBytes)
{
	//Horrible, slow implementation
	while(nBytes--)
	{
		if(*buffer != 0xFF) return 0;
		buffer++;
	}
	return 1;
}

static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND)
{

	int retval = YAFFS_OK;
	__u8 *data = yaffs_GetTempBuffer(dev,__LINE__);
	yaffs_ExtendedTags tags;

  	dev->readChunkWithTagsFromNAND(dev,chunkInNAND,data,&tags);
	
	if(!yaffs_CheckFF(data,dev->nBytesPerChunk) || tags.chunkUsed)
	{
		T(YAFFS_TRACE_NANDACCESS,(TSTR("Chunk %d not erased" TENDSTR),chunkInNAND));
		retval = YAFFS_FAIL;
	}

	yaffs_ReleaseTempBuffer(dev,data,__LINE__);
	
	return retval;
	
}



#if 1
static int yaffs_WriteNewChunkWithTagsToNAND(struct yaffs_DeviceStruct *dev, const __u8 *data, yaffs_ExtendedTags *tags,int useReserve)
{
	int chunk;
	
	int writeOk = 1;
	int attempts = 0;
	

	
	do{
		chunk = yaffs_AllocateChunk(dev,useReserve);
	
		if(chunk >= 0)
		{

			// First check this chunk is erased...
#ifndef CONFIG_YAFFS_DISABLE_CHUNK_ERASED_CHECK
			writeOk = yaffs_CheckChunkErased(dev,chunk);
#endif		
			if(!writeOk)
			{
				T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs chunk %d was not erased" TENDSTR),chunk));
			}
			else
			{
				writeOk =  yaffs_WriteChunkWithTagsToNAND(dev,chunk,data,tags);
			}
			attempts++;

			if(writeOk)
			{
				// Copy the data into the robustification buffer.
				// NB We do this at the end to prevent duplicates in the case of a write error.
				//Todo
				yaffs_HandleWriteChunkOk(dev,chunk,data,tags);
			}
			else
			{
				yaffs_HandleWriteChunkError(dev,chunk);
			}
		}
		
	} while(chunk >= 0 && ! writeOk);
	
	if(attempts > 1)
	{
		T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs write required %d attempts" TENDSTR),attempts));
		dev->nRetriedWrites+= (attempts - 1);	
	}
	

	
	return chunk;
}
#endif


///
// Functions for robustisizing
//
//

static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND)
{