/* * YAFFS: Yet another FFS. A NAND-flash specific file system. * yaffs_guts.c  The main guts of YAFFS * * Copyright (C) 2002 Aleph One Ltd. *   for Toby Churchill Ltd and Brightstar Engineering * * Created by Charles Manning <charles@aleph1.co.uk> * * 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.cconst char *yaffs_guts_c_version="$Id: yaffs_guts.c,v 1.34 2004/06/08 08:47:55 charles Exp $";#include "yportenv.h"#include "yaffsinterface.h"#include "yaffs_guts.h"#define YAFFS_PASSIVE_GC_CHUNKS 2#if 0// Use Steven Hill's ECC struff instead// External functions for ECC on datavoid 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;}// Local prototypesstatic int yaffs_CheckObjectHashSanity(yaffs_Device *dev);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_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 char *name, int force);static void yaffs_DeleteChunk(yaffs_Device *dev,int chunkId,int markNAND);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);// Robustificationstatic 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_Spare *spare);static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND, const yaffs_Spare *spare);static int  yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND);static int yaffs_UnlinkWorker(yaffs_Object *obj);static void yaffs_AbortHalfCreatedObject(yaffs_Object *obj);static int yaffs_VerifyCompare(const __u8 *d0, const __u8 * d1, const yaffs_Spare *s0, const yaffs_Spare *s1);loff_t yaffs_GetFileSize(yaffs_Object *obj);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);static int yaffs_AllocateChunk(yaffs_Device *dev,int useReserve);#ifdef YAFFS_PARANOIDstatic int yaffs_CheckFileSanity(yaffs_Object *in);#else#define yaffs_CheckFileSanity(in)#endifstatic void yaffs_InvalidateWholeChunkCache(yaffs_Object *in);static void yaffs_InvalidateChunkCache(yaffs_Object *object, int chunkId);// Chunk bitmap manipulationsstatic __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 __inline__ void yaffs_ClearChunkBits(yaffs_Device *dev,int blk){	__u8 *blkBits = yaffs_BlockBits(dev,blk);	 memset(blkBits,0,dev->chunkBitmapStride);}static __inline__ void yaffs_ClearChunkBit(yaffs_Device *dev,int blk,int chunk){	__u8 *blkBits = yaffs_BlockBits(dev,blk);		blkBits[chunk/8] &=  ~ (1<<(chunk & 7));}static __inline__ void yaffs_SetChunkBit(yaffs_Device *dev,int blk,int chunk){	__u8 *blkBits = yaffs_BlockBits(dev,blk);	blkBits[chunk/8] |=   (1<<(chunk & 7));}static __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 __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;}// Function to manipulate block infostatic  __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];}static  __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;}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);}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;}static int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,int chunkInNAND){	static int init = 0;	static __u8 cmpbuf[YAFFS_BYTES_PER_CHUNK];	static __u8 data[YAFFS_BYTES_PER_CHUNK];    // Might as well always allocate the larger size for dev->useNANDECC == true;	static __u8 spare[sizeof(struct yaffs_NANDSpare)];	  	dev->readChunkFromNAND(dev,chunkInNAND,data,(yaffs_Spare *)spare);		if(!init)	{		memset(cmpbuf,0xff,YAFFS_BYTES_PER_CHUNK);		init = 1;	}		if(memcmp(cmpbuf,data,YAFFS_BYTES_PER_CHUNK)) return  YAFFS_FAIL;	if(memcmp(cmpbuf,spare,16)) return YAFFS_FAIL;		return YAFFS_OK;	}int yaffs_EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND){	dev->nBlockErasures++;	return dev->eraseBlockInNAND(dev,blockInNAND);}int yaffs_InitialiseNAND(struct yaffs_DeviceStruct *dev){	return dev->initialiseNAND(dev);}static int yaffs_WriteNewChunkToNAND(struct yaffs_DeviceStruct *dev, const __u8 *data, yaffs_Spare *spare,int useReserve){	int chunk;		int writeOk = 1;	int attempts = 0;		unsigned char rbData[YAFFS_BYTES_PER_CHUNK];	yaffs_Spare rbSpare;		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_WriteChunkToNAND(dev,chunk,data,spare);			}			attempts++;			if(writeOk)			{				// Readback & verify				// If verify fails, then delete this chunk and try again				// To verify we compare everything except the block and 				// page status bytes.				// NB We check a raw read without ECC correction applied				yaffs_ReadChunkFromNAND(dev,chunk,rbData,&rbSpare,0);				#ifndef CONFIG_YAFFS_DISABLE_WRITE_VERIFY				if(!yaffs_VerifyCompare(data,rbData,spare,&rbSpare))				{					// Didn't verify					T(YAFFS_TRACE_ERROR,(TSTR("**>> yaffs write verify failed on chunk %d" TENDSTR), chunk));					writeOk = 0;				}	#endif											}			if(writeOk)			{				// Copy the data into the write buffer.				// NB We do this at the end to prevent duplicates in the case of a write error.				//Todo				yaffs_HandleWriteChunkOk(dev,chunk,data,spare);			}			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;}///// Functions for robustisizing////static void yaffs_RetireBlock(yaffs_Device *dev,int blockInNAND){	// Ding the blockStatus in the first two pages of the block.		yaffs_Spare spare;	memset(&spare, 0xff,sizeof(yaffs_Spare));	spare.blockStatus = 0;		// TODO change this retirement marking for other NAND types	yaffs_WriteChunkToNAND(dev, blockInNAND * dev->nChunksPerBlock, NULL , &spare);	yaffs_WriteChunkToNAND(dev, blockInNAND * dev->nChunksPerBlock + 1, NULL , &spare);		yaffs_GetBlockInfo(dev,blockInNAND)->blockState = YAFFS_BLOCK_STATE_DEAD;	dev->nRetiredBlocks++;}static int yaffs_RewriteBufferedBlock(yaffs_Device *dev){	dev->doingBufferedBlockRewrite = 1;	//	//	Remove erased chunks	//  Rewrite existing chunks to a new block	//	Set current write block to the new block		dev->doingBufferedBlockRewrite = 0;		return 1;}static void yaffs_HandleReadDataError(yaffs_Device *dev,int chunkInNAND){	int blockInNAND = chunkInNAND/dev->nChunksPerBlock;	// Mark the block for retirement	yaffs_GetBlockInfo(dev,blockInNAND)->needsRetiring = 1;	T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,(TSTR("**>>Block %d marked for retirement" TENDSTR),blockInNAND));	//TODO		// Just do a garbage collection on the affected block then retire the block	// NB recursion}static void yaffs_CheckWrittenBlock(yaffs_Device *dev,int chunkInNAND){}static void yaffs_HandleWriteChunkOk(yaffs_Device *dev,int chunkInNAND,const __u8 *data, const yaffs_Spare *spare){}static void yaffs_HandleUpdateChunk(yaffs_Device *dev,int chunkInNAND, const yaffs_Spare *spare){}static void yaffs_HandleWriteChunkError(yaffs_Device *dev,int chunkInNAND){	int blockInNAND = chunkInNAND/dev->nChunksPerBlock;	// Mark the block for retirement	yaffs_GetBlockInfo(dev,blockInNAND)->needsRetiring = 1;	// Delete the chunk	yaffs_DeleteChunk(dev,chunkInNAND,1);}static int yaffs_VerifyCompare(const __u8 *d0, const __u8 * d1, const yaffs_Spare *s0, const yaffs_Spare *s1){	if( memcmp(d0,d1,YAFFS_BYTES_PER_CHUNK) != 0 ||		s0->tagByte0 != s1->tagByte0 ||		s0->tagByte1 != s1->tagByte1 ||		s0->tagByte2 != s1->tagByte2 ||		s0->tagByte3 != s1->tagByte3 ||		s0->tagByte4 != s1->tagByte4 ||		s0->tagByte5 != s1->tagByte5 ||		s0->tagByte6 != s1->tagByte6 ||		s0->tagByte7 != s1->tagByte7 ||		s0->ecc1[0]  != s1->ecc1[0]  ||		s0->ecc1[1]  != s1->ecc1[1]  ||		s0->ecc1[2]  != s1->ecc1[2]  ||		s0->ecc2[0]  != s1->ecc2[0]  ||		s0->ecc2[1]  != s1->ecc2[1]  ||		s0->ecc2[2]  != s1->ecc2[2] )		{			return 0;		}		return 1;}///////////////////////// Object management //////////////////// List of spare objects// The list is hooked together using the first pointer// in the object// static yaffs_Object *yaffs_freeObjects = NULL;// static int yaffs_nFreeObjects;// static yaffs_ObjectList *yaffs_allocatedObjectList = NULL;// static yaffs_ObjectBucket yaffs_objectBucket[YAFFS_NOBJECT_BUCKETS];static __u16 yaffs_CalcNameSum(const char *name){	__u16 sum = 0;	__u16 i = 1;		__u8 *bname = (__u8 *)name;	if(bname)	{		while ((*bname) && (i <=YAFFS_MAX_NAME_LENGTH))		{#ifdef CONFIG_YAFFS_CASE_INSENSITIVE			sum += toupper(*bname) * i;#else			sum += (*bname) * i;#endif			i++;			bname++;		}	}	return sum;}void yaffs_SetObjectName(yaffs_Object *obj, const char *name){#ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM					if(name && strlen(name) <= YAFFS_SHORT_NAME_LENGTH)					{