yaffs_guts.c

yaffs2

/*
 * 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.
 *
 */

const char *yaffs_guts_c_version =
    "$Id: yaffs_guts.c,v 1.35 2006/06/05 04:10:49 charles Exp $";

#include "yportenv.h"

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

#include "yaffs_tagscompat.h"
#ifndef CONFIG_YAFFS_OWN_SORT
#include "yaffs_qsort.h"
#endif
#include "yaffs_nand.h"

#include "yaffs_checkptrw.h"

#include "yaffs_nand.h"


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

#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);
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 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 __u8 *yaffs_GetTempBuffer(yaffs_Device * dev, int lineNo);
static void yaffs_ReleaseTempBuffer(yaffs_Device * dev, __u8 * buffer,
				    int lineNo);

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);

static void yaffs_VerifyFreeChunks(yaffs_Device * dev);

#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 void yaffs_InvalidateCheckpoint(yaffs_Device *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)));

	/*
	 * If we got here then we have to allocate an unmanaged one
	 * This is not good.
	 */

	dev->unmanagedTempAllocations++;
	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++;
	}

}

/*
 * 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_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;
}

/*
 *  Simple hash function. Needs to have a reasonable spread
 */
 
static Y_INLINE int yaffs_HashFunction(int n)
{
	n = abs(n);
	return (n % YAFFS_NOBJECT_BUCKETS);
}

/*
 * Access functions to useful fake objects
 */
 
yaffs_Object *yaffs_Root(yaffs_Device * dev)
{
	return dev->rootDir;
}

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


/*
 *  Erased NAND checking functions
 */
 
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;

	yaffs_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;

}

static int yaffs_WriteNewChunkWithTagsToNAND(struct yaffs_DeviceStruct *dev,
					     const __u8 * data,
					     yaffs_ExtendedTags * tags,
					     int useReserve)
{
	int chunk;

	int writeOk = 1;
	int attempts = 0;
	
	yaffs_InvalidateCheckpoint(dev);

	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;
}

/*
 * Block retiring for handling a broken block.
 */
 
static void yaffs_RetireBlock(yaffs_Device * dev, int blockInNAND)
{

	yaffs_InvalidateCheckpoint(dev);
	
	yaffs_MarkBlockBad(dev, blockInNAND);

	yaffs_GetBlockInfo(dev, blockInNAND)->blockState =
	    YAFFS_BLOCK_STATE_DEAD;

	dev->nRetiredBlocks++;
}

/*
 * Functions for robustisizing TODO
 *
 */
 
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 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, __LINE__);
}


/*---------------- Name handling functions ------------*/ 

static __u16 yaffs_CalcNameSum(const YCHAR * name)
{
	__u16 sum = 0;
	__u16 i = 1;

	YUCHAR *bname = (YUCHAR *) name;
	if (bname) {
		while ((*bname) && (i <= YAFFS_MAX_NAME_LENGTH)) {

#ifdef CONFIG_YAFFS_CASE_INSENSITIVE
			sum += yaffs_toupper(*bname) * i;
#else
			sum += (*bname) * i;
#endif
			i++;
			bname++;
		}
	}
	return sum;
}

static void yaffs_SetObjectName(yaffs_Object * obj, const YCHAR * name)
{
#ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
	if (name && yaffs_strlen(name) <= YAFFS_SHORT_NAME_LENGTH) {
		yaffs_strcpy(obj->shortName, name);
	} else {
		obj->shortName[0] = _Y('\0');
	}
#endif
	obj->sum = yaffs_CalcNameSum(name);
}

/*-------------------- TNODES -------------------

 * List of spare tnodes
 * The list is hooked together using the first pointer
 * in the tnode.
 */
 
/* yaffs_CreateTnodes creates a bunch more tnodes and
 * adds them to the tnode free list.
 * Don't use this function directly
 */

static int yaffs_CreateTnodes(yaffs_Device * dev, int nTnodes)
{
	int i;
	int tnodeSize;
	yaffs_Tnode *newTnodes;
	__u8 *mem;
	yaffs_Tnode *curr;
	yaffs_Tnode *next;
	yaffs_TnodeList *tnl;

	if (nTnodes < 1)
		return YAFFS_OK;
		
	/* Calculate the tnode size in bytes for variable width tnode support.
	 * Must be a multiple of 32-bits  */
	tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;

	/* make these things */

	newTnodes = YMALLOC(nTnodes * tnodeSize);
	mem = (__u8 *)newTnodes;

	if (!newTnodes) {
		T(YAFFS_TRACE_ERROR,
		  (TSTR("yaffs: Could not allocate Tnodes" TENDSTR)));
		return YAFFS_FAIL;
	}

	/* Hook them into the free list */
#if 0
	for (i = 0; i < nTnodes - 1; i++) {
		newTnodes[i].internal[0] = &newTnodes[i + 1];
#ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
		newTnodes[i].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
#endif
	}

	newTnodes[nTnodes - 1].internal[0] = dev->freeTnodes;
#ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
	newTnodes[nTnodes - 1].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
#endif
	dev->freeTnodes = newTnodes;
#else
	/* New hookup for wide tnodes */
	for(i = 0; i < nTnodes -1; i++) {
		curr = (yaffs_Tnode *) &mem[i * tnodeSize];
		next = (yaffs_Tnode *) &mem[(i+1) * tnodeSize];
		curr->internal[0] = next;
	}
	
	curr = (yaffs_Tnode *) &mem[(nTnodes - 1) * tnodeSize];
	curr->internal[0] = dev->freeTnodes;
	dev->freeTnodes = (yaffs_Tnode *)mem;

#endif


	dev->nFreeTnodes += nTnodes;
	dev->nTnodesCreated += nTnodes;

	/* Now add this bunch of tnodes to a list for freeing up.
	 * NB If we can't add this to the management list it isn't fatal
	 * but it just means we can't free this bunch of tnodes later.
	 */
	 
	tnl = YMALLOC(sizeof(yaffs_TnodeList));
	if (!tnl) {
		T(YAFFS_TRACE_ERROR,
		  (TSTR
		   ("yaffs: Could not add tnodes to management list" TENDSTR)));

	} else {
		tnl->tnodes = newTnodes;
		tnl->next = dev->allocatedTnodeList;
		dev->allocatedTnodeList = tnl;
	}

	T(YAFFS_TRACE_ALLOCATE, (TSTR("yaffs: Tnodes added" TENDSTR)));

	return YAFFS_OK;
}