/* * YAFFS: Yet Another Flash File System. A NAND-flash specific file system. * * Copyright (C) 2002-2007 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. */const char *yaffs_guts_c_version =    "$Id: yaffs_guts.c,v 1.78 2009/01/27 02:52:45 charles Exp $";#include "yportenv.h"#include "yaffsinterface.h"#include "yaffs_guts.h"#include "yaffs_tagsvalidity.h"#include "yaffs_getblockinfo.h"#include "yaffs_tagscompat.h"#ifndef  CONFIG_YAFFS_USE_OWN_SORT#include "yaffs_qsort.h"#endif#include "yaffs_nand.h"#include "yaffs_checkptrw.h"#include "yaffs_nand.h"#include "yaffs_packedtags2.h"#define YAFFS_PASSIVE_GC_CHUNKS 2#include "yaffs_ecc.h"/* Robustification (if it ever comes about...) */static void yaffs_RetireBlock(yaffs_Device * dev, int blockInNAND);static void yaffs_HandleWriteChunkError(yaffs_Device * dev, int chunkInNAND, int erasedOk);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);/* Other local prototypes */static int yaffs_UnlinkObject( yaffs_Object *obj);static int yaffs_ObjectHasCachedWriteData(yaffs_Object *obj);static void yaffs_HardlinkFixup(yaffs_Device *dev, yaffs_Object *hardList);static int yaffs_WriteNewChunkWithTagsToNAND(yaffs_Device * dev,					     const __u8 * buffer,					     yaffs_ExtendedTags * tags,					     int useReserve);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, int shadows);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 int yaffs_CheckChunkErased(struct yaffs_DeviceStruct *dev,				  int chunkInNAND);static int yaffs_UnlinkWorker(yaffs_Object * obj);static void yaffs_DestroyObject(yaffs_Object * obj);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, yaffs_BlockInfo **blockUsedPtr);static void yaffs_VerifyFreeChunks(yaffs_Device * dev);static void yaffs_CheckObjectDetailsLoaded(yaffs_Object *in);static void yaffs_VerifyDirectory(yaffs_Object *directory);#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);static void yaffs_InvalidateCheckpoint(yaffs_Device *dev);static int yaffs_FindChunkInFile(yaffs_Object * in, int chunkInInode,				 yaffs_ExtendedTags * tags);static __u32 yaffs_GetChunkGroupBase(yaffs_Device *dev, yaffs_Tnode *tn, unsigned pos);static yaffs_Tnode *yaffs_FindLevel0Tnode(yaffs_Device * dev,					  yaffs_FileStructure * fStruct,					  __u32 chunkId);/* Function to calculate chunk and offset */static void yaffs_AddrToChunk(yaffs_Device *dev, loff_t addr, int *chunkOut, __u32 *offsetOut){	int chunk;	__u32 offset;		chunk  = (__u32)(addr >> dev->chunkShift);			if(dev->chunkDiv == 1)	{		/* easy power of 2 case */		offset = (__u32)(addr & dev->chunkMask);	}	else	{		/* Non power-of-2 case */				loff_t chunkBase;				chunk /= dev->chunkDiv;				chunkBase = ((loff_t)chunk) * dev->nDataBytesPerChunk;		offset = (__u32)(addr - chunkBase);	}	*chunkOut = chunk;	*offsetOut = offset;}/* Function to return the number of shifts for a power of 2 greater than or equal  * to the given number * Note we don't try to cater for all possible numbers and this does not have to * be hellishly efficient. */ static __u32 ShiftsGE(__u32 x){	int extraBits;	int nShifts;		nShifts = extraBits = 0;		while(x>1){		if(x & 1) extraBits++;		x>>=1;		nShifts++;	}	if(extraBits) 		nShifts++;			return nShifts;}/* Function to return the number of shifts to get a 1 in bit 0 */ static __u32 Shifts(__u32 x){	int nShifts;		nShifts =  0;		if(!x) return 0;		while( !(x&1)){		x>>=1;		nShifts++;	}			return nShifts;}/*  * Temporary buffer manipulations. */static int yaffs_InitialiseTempBuffers(yaffs_Device *dev)	{	int i;	__u8 *buf = (__u8 *)1;			memset(dev->tempBuffer,0,sizeof(dev->tempBuffer));			for (i = 0; buf && i < YAFFS_N_TEMP_BUFFERS; i++) {		dev->tempBuffer[i].line = 0;	/* not in use */		dev->tempBuffer[i].buffer = buf =		    YMALLOC_DMA(dev->totalBytesPerChunk);	}			return buf ? YAFFS_OK : YAFFS_FAIL;	}__u8 *yaffs_GetTempBuffer(yaffs_Device * dev, int lineNo){	int i, j;	dev->tempInUse++;	if(dev->tempInUse > dev->maxTemp)		dev->maxTemp = dev->tempInUse;	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)));	/*	 * If we got here then we have to allocate an unmanaged one	 * This is not good.	 */	dev->unmanagedTempAllocations++;	return YMALLOC(dev->nDataBytesPerChunk);}void yaffs_ReleaseTempBuffer(yaffs_Device * dev, __u8 * buffer,				    int lineNo){	int i;		dev->tempInUse--;		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++;	}}/* * Determine if we have a managed buffer. */int yaffs_IsManagedTempBuffer(yaffs_Device * dev, const __u8 * buffer){	int i;	for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {		if (dev->tempBuffer[i].buffer == buffer)			return 1;	}    for (i = 0; i < dev->nShortOpCaches; i++) {        if( dev->srCache[i].data == buffer )            return 1;    }    if (buffer == dev->checkpointBuffer)      return 1;    T(YAFFS_TRACE_ALWAYS,	  (TSTR("yaffs: unmaged buffer detected.\n" TENDSTR)));    return 0;}/* * Chunk bitmap manipulations */static Y_INLINE __u8 *yaffs_BlockBits(yaffs_Device * dev, int blk){	if (blk < dev->internalStartBlock || blk > dev->internalEndBlock) {		T(YAFFS_TRACE_ERROR,		  (TSTR("**>> yaffs: BlockBits block %d is not valid" TENDSTR),		   blk));		YBUG();	}	return dev->chunkBits +	    (dev->chunkBitmapStride * (blk - dev->internalStartBlock));}static Y_INLINE void yaffs_VerifyChunkBitId(yaffs_Device *dev, int blk, int chunk){	if(blk < dev->internalStartBlock || blk > dev->internalEndBlock ||	   chunk < 0 || chunk >= dev->nChunksPerBlock) {	   T(YAFFS_TRACE_ERROR,	    (TSTR("**>> yaffs: Chunk Id (%d:%d) invalid"TENDSTR),blk,chunk));	    YBUG();	}}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);	yaffs_VerifyChunkBitId(dev,blk,chunk);	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);		yaffs_VerifyChunkBitId(dev,blk,chunk);	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);	yaffs_VerifyChunkBitId(dev,blk,chunk);	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;}static int yaffs_CountChunkBits(yaffs_Device * dev, int blk){	__u8 *blkBits = yaffs_BlockBits(dev, blk);	int i;	int n = 0;	for (i = 0; i < dev->chunkBitmapStride; i++) {		__u8 x = *blkBits;		while(x){			if(x & 1)				n++;			x >>=1;		}					blkBits++;	}	return n;}/*  * Verification code */ static int yaffs_SkipVerification(yaffs_Device *dev){	return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY | YAFFS_TRACE_VERIFY_FULL));}static int yaffs_SkipFullVerification(yaffs_Device *dev){	return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY_FULL));}static int yaffs_SkipNANDVerification(yaffs_Device *dev){	return !(yaffs_traceMask & (YAFFS_TRACE_VERIFY_NAND));}static const char * blockStateName[] = {"Unknown","Needs scanning","Scanning","Empty","Allocating","Full","Dirty","Checkpoint","Collecting","Dead"};static void yaffs_VerifyBlock(yaffs_Device *dev,yaffs_BlockInfo *bi,int n){	int actuallyUsed;	int inUse;		if(yaffs_SkipVerification(dev))		return;			/* Report illegal runtime states */	if(bi->blockState >= YAFFS_NUMBER_OF_BLOCK_STATES)		T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has undefined state %d"TENDSTR),n,bi->blockState));			switch(bi->blockState){	 case YAFFS_BLOCK_STATE_UNKNOWN:	 case YAFFS_BLOCK_STATE_SCANNING:	 case YAFFS_BLOCK_STATE_NEEDS_SCANNING:		T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has bad run-state %s"TENDSTR),		n,blockStateName[bi->blockState]));	}		/* Check pages in use and soft deletions are legal */		actuallyUsed = bi->pagesInUse - bi->softDeletions;		if(bi->pagesInUse < 0 || bi->pagesInUse > dev->nChunksPerBlock ||	   bi->softDeletions < 0 || bi->softDeletions > dev->nChunksPerBlock ||	   actuallyUsed < 0 || actuallyUsed > dev->nChunksPerBlock)		T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has illegal values pagesInUsed %d softDeletions %d"TENDSTR),		n,bi->pagesInUse,bi->softDeletions));				/* Check chunk bitmap legal */	inUse = yaffs_CountChunkBits(dev,n);	if(inUse != bi->pagesInUse)		T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has inconsistent values pagesInUse %d counted chunk bits %d"TENDSTR),			n,bi->pagesInUse,inUse));		/* Check that the sequence number is valid.	 * Ten million is legal, but is very unlikely 	 */	if(dev->isYaffs2 && 	   (bi->blockState == YAFFS_BLOCK_STATE_ALLOCATING || bi->blockState == YAFFS_BLOCK_STATE_FULL) &&	   (bi->sequenceNumber < YAFFS_LOWEST_SEQUENCE_NUMBER || bi->sequenceNumber > 10000000 ))		T(YAFFS_TRACE_VERIFY,(TSTR("Block %d has suspect sequence number of %d"TENDSTR),		n,bi->sequenceNumber));		}static void yaffs_VerifyCollectedBlock(yaffs_Device *dev,yaffs_BlockInfo *bi,int n){	yaffs_VerifyBlock(dev,bi,n);		/* After collection the block should be in the erased state */	/* This will need to change if we do partial gc */		if(bi->blockState != YAFFS_BLOCK_STATE_COLLECTING &&	   bi->blockState != YAFFS_BLOCK_STATE_EMPTY){		T(YAFFS_TRACE_ERROR,(TSTR("Block %d is in state %d after gc, should be erased"TENDSTR),			n,bi->blockState));	}}static void yaffs_VerifyBlocks(yaffs_Device *dev){	int i;	int nBlocksPerState[YAFFS_NUMBER_OF_BLOCK_STATES];	int nIllegalBlockStates = 0;		if(yaffs_SkipVerification(dev))		return;	memset(nBlocksPerState,0,sizeof(nBlocksPerState));			for(i = dev->internalStartBlock; i <= dev->internalEndBlock; i++){		yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev,i);		yaffs_VerifyBlock(dev,bi,i);		if(bi->blockState < YAFFS_NUMBER_OF_BLOCK_STATES)			nBlocksPerState[bi->blockState]++;		else			nIllegalBlockStates++;						}		T(YAFFS_TRACE_VERIFY,(TSTR(""TENDSTR)));	T(YAFFS_TRACE_VERIFY,(TSTR("Block summary"TENDSTR)));		T(YAFFS_TRACE_VERIFY,(TSTR("%d blocks have illegal states"TENDSTR),nIllegalBlockStates));	if(nBlocksPerState[YAFFS_BLOCK_STATE_ALLOCATING] > 1)		T(YAFFS_TRACE_VERIFY,(TSTR("Too many allocating blocks"TENDSTR)));	for(i = 0; i < YAFFS_NUMBER_OF_BLOCK_STATES; i++)		T(YAFFS_TRACE_VERIFY,		  (TSTR("%s %d blocks"TENDSTR),		  blockStateName[i],nBlocksPerState[i]));		if(dev->blocksInCheckpoint != nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT])		T(YAFFS_TRACE_VERIFY,		 (TSTR("Checkpoint block count wrong dev %d count %d"TENDSTR),		 dev->blocksInCheckpoint, nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT]));		 	if(dev->nErasedBlocks != nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY])		T(YAFFS_TRACE_VERIFY,		 (TSTR("Erased block count wrong dev %d count %d"TENDSTR),		 dev->nErasedBlocks, nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY]));		 	if(nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING] > 1)		T(YAFFS_TRACE_VERIFY,