+ return YAFFS_FAIL;
+}
+
+/*------------------------- Block Management and Page Allocation ----------------*/
+
+static int yaffs_InitialiseBlocks(yaffs_Device *dev)
+{
+ int nBlocks = dev->internalEndBlock - dev->internalStartBlock + 1;
+
+ dev->blockInfo = NULL;
+ dev->chunkBits = NULL;
+
+ dev->allocationBlock = -1; /* force it to get a new one */
+
+ /* If the first allocation strategy fails, thry the alternate one */
+ dev->blockInfo = YMALLOC(nBlocks * sizeof(yaffs_BlockInfo));
+ if (!dev->blockInfo) {
+ dev->blockInfo = YMALLOC_ALT(nBlocks * sizeof(yaffs_BlockInfo));
+ dev->blockInfoAlt = 1;
+ } else
+ dev->blockInfoAlt = 0;
+
+ if (dev->blockInfo) {
+ /* Set up dynamic blockinfo stuff. */
+ dev->chunkBitmapStride = (dev->nChunksPerBlock + 7) / 8; /* round up bytes */
+ dev->chunkBits = YMALLOC(dev->chunkBitmapStride * nBlocks);
+ if (!dev->chunkBits) {
+ dev->chunkBits = YMALLOC_ALT(dev->chunkBitmapStride * nBlocks);
+ dev->chunkBitsAlt = 1;
+ } else
+ dev->chunkBitsAlt = 0;
+ }
+
+ if (dev->blockInfo && dev->chunkBits) {
+ memset(dev->blockInfo, 0, nBlocks * sizeof(yaffs_BlockInfo));
+ memset(dev->chunkBits, 0, dev->chunkBitmapStride * nBlocks);
+ return YAFFS_OK;
+ }
+
+ return YAFFS_FAIL;
+}
+
+static void yaffs_DeinitialiseBlocks(yaffs_Device *dev)
+{
+ if (dev->blockInfoAlt && dev->blockInfo)
+ YFREE_ALT(dev->blockInfo);
+ else if (dev->blockInfo)
+ YFREE(dev->blockInfo);
+
+ dev->blockInfoAlt = 0;
+
+ dev->blockInfo = NULL;
+
+ if (dev->chunkBitsAlt && dev->chunkBits)
+ YFREE_ALT(dev->chunkBits);
+ else if (dev->chunkBits)
+ YFREE(dev->chunkBits);
+ dev->chunkBitsAlt = 0;
+ dev->chunkBits = NULL;
+}
+
+static int yaffs_BlockNotDisqualifiedFromGC(yaffs_Device *dev,
+ yaffs_BlockInfo *bi)
+{
+ int i;
+ __u32 seq;
+ yaffs_BlockInfo *b;
+
+ if (!dev->isYaffs2)
+ return 1; /* disqualification only applies to yaffs2. */
+
+ if (!bi->hasShrinkHeader)
+ return 1; /* can gc */
+
+ /* Find the oldest dirty sequence number if we don't know it and save it
+ * so we don't have to keep recomputing it.
+ */
+ if (!dev->oldestDirtySequence) {
+ seq = dev->sequenceNumber;
+
+ for (i = dev->internalStartBlock; i <= dev->internalEndBlock;
+ i++) {
+ b = yaffs_GetBlockInfo(dev, i);
+ if (b->blockState == YAFFS_BLOCK_STATE_FULL &&
+ (b->pagesInUse - b->softDeletions) <
+ dev->nChunksPerBlock && b->sequenceNumber < seq) {
+ seq = b->sequenceNumber;
+ }
+ }
+ dev->oldestDirtySequence = seq;
+ }
+
+ /* Can't do gc of this block if there are any blocks older than this one that have
+ * discarded pages.
+ */
+ return (bi->sequenceNumber <= dev->oldestDirtySequence);
+}
+
+/* FindDiretiestBlock is used to select the dirtiest block (or close enough)
+ * for garbage collection.
+ */
+
+static int yaffs_FindBlockForGarbageCollection(yaffs_Device *dev,
+ int aggressive)
+{
+ int b = dev->currentDirtyChecker;
+
+ int i;
+ int iterations;
+ int dirtiest = -1;
+ int pagesInUse = 0;
+ int prioritised = 0;
+ yaffs_BlockInfo *bi;
+ int pendingPrioritisedExist = 0;
+
+ /* First let's see if we need to grab a prioritised block */
+ if (dev->hasPendingPrioritisedGCs) {
+ for (i = dev->internalStartBlock; i < dev->internalEndBlock && !prioritised; i++) {
+
+ bi = yaffs_GetBlockInfo(dev, i);
+ /* yaffs_VerifyBlock(dev,bi,i); */
+
+ if (bi->gcPrioritise) {
+ pendingPrioritisedExist = 1;
+ if (bi->blockState == YAFFS_BLOCK_STATE_FULL &&
+ yaffs_BlockNotDisqualifiedFromGC(dev, bi)) {
+ pagesInUse = (bi->pagesInUse - bi->softDeletions);
+ dirtiest = i;
+ prioritised = 1;
+ aggressive = 1; /* Fool the non-aggressive skip logiv below */
+ }
+ }
+ }
+
+ if (!pendingPrioritisedExist) /* None found, so we can clear this */
+ dev->hasPendingPrioritisedGCs = 0;
+ }
+
+ /* If we're doing aggressive GC then we are happy to take a less-dirty block, and
+ * search harder.
+ * else (we're doing a leasurely gc), then we only bother to do this if the
+ * block has only a few pages in use.
+ */
+
+ dev->nonAggressiveSkip--;
+
+ if (!aggressive && (dev->nonAggressiveSkip > 0))
+ return -1;
+
+ if (!prioritised)
+ pagesInUse =
+ (aggressive) ? dev->nChunksPerBlock : YAFFS_PASSIVE_GC_CHUNKS + 1;
+
+ if (aggressive)
+ iterations =
+ dev->internalEndBlock - dev->internalStartBlock + 1;
+ else {
+ iterations =
+ dev->internalEndBlock - dev->internalStartBlock + 1;
+ iterations = iterations / 16;
+ if (iterations > 200)
+ iterations = 200;
+ }
+
+ for (i = 0; i <= iterations && pagesInUse > 0 && !prioritised; i++) {
+ b++;
+ if (b < dev->internalStartBlock || b > dev->internalEndBlock)
+ b = dev->internalStartBlock;
+
+ if (b < dev->internalStartBlock || b > dev->internalEndBlock) {
+ T(YAFFS_TRACE_ERROR,
+ (TSTR("**>> Block %d is not valid" TENDSTR), b));
+ YBUG();
+ }
+
+ bi = yaffs_GetBlockInfo(dev, b);
+
+ if (bi->blockState == YAFFS_BLOCK_STATE_FULL &&
+ (bi->pagesInUse - bi->softDeletions) < pagesInUse &&
+ yaffs_BlockNotDisqualifiedFromGC(dev, bi)) {
+ dirtiest = b;
+ pagesInUse = (bi->pagesInUse - bi->softDeletions);
+ }
+ }
+
+ dev->currentDirtyChecker = b;
+
+ if (dirtiest > 0) {
+ T(YAFFS_TRACE_GC,
+ (TSTR("GC Selected block %d with %d free, prioritised:%d" TENDSTR), dirtiest,
+ dev->nChunksPerBlock - pagesInUse, prioritised));
+ }
+
+ dev->oldestDirtySequence = 0;
+
+ if (dirtiest > 0)
+ dev->nonAggressiveSkip = 4;
+
+ return dirtiest;
+}
+
+static void yaffs_BlockBecameDirty(yaffs_Device *dev, int blockNo)
+{
+ yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, blockNo);
+
+ int erasedOk = 0;
+
+ /* If the block is still healthy erase it and mark as clean.
+ * If the block has had a data failure, then retire it.
+ */
+
+ T(YAFFS_TRACE_GC | YAFFS_TRACE_ERASE,
+ (TSTR("yaffs_BlockBecameDirty block %d state %d %s"TENDSTR),
+ blockNo, bi->blockState, (bi->needsRetiring) ? "needs retiring" : ""));
+
+ bi->blockState = YAFFS_BLOCK_STATE_DIRTY;
+
+ if (!bi->needsRetiring) {
+ yaffs_InvalidateCheckpoint(dev);
+ erasedOk = yaffs_EraseBlockInNAND(dev, blockNo);
+ if (!erasedOk) {
+ dev->nErasureFailures++;
+ T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
+ (TSTR("**>> Erasure failed %d" TENDSTR), blockNo));
+ }
+ }
+
+ if (erasedOk &&
+ ((yaffs_traceMask & YAFFS_TRACE_ERASE) || !yaffs_SkipVerification(dev))) {
+ int i;
+ for (i = 0; i < dev->nChunksPerBlock; i++) {
+ if (!yaffs_CheckChunkErased
+ (dev, blockNo * dev->nChunksPerBlock + i)) {
+ T(YAFFS_TRACE_ERROR,
+ (TSTR
+ (">>Block %d erasure supposedly OK, but chunk %d not erased"
+ TENDSTR), blockNo, i));
+ }
+ }
+ }
+
+ if (erasedOk) {
+ /* Clean it up... */
+ bi->blockState = YAFFS_BLOCK_STATE_EMPTY;
+ dev->nErasedBlocks++;
+ bi->pagesInUse = 0;
+ bi->softDeletions = 0;
+ bi->hasShrinkHeader = 0;
+ bi->skipErasedCheck = 1; /* This is clean, so no need to check */
+ bi->gcPrioritise = 0;
+ yaffs_ClearChunkBits(dev, blockNo);
+
+ T(YAFFS_TRACE_ERASE,
+ (TSTR("Erased block %d" TENDSTR), blockNo));
+ } else {
+ dev->nFreeChunks -= dev->nChunksPerBlock; /* We lost a block of free space */
+
+ yaffs_RetireBlock(dev, blockNo);
+ T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
+ (TSTR("**>> Block %d retired" TENDSTR), blockNo));
+ }
+}
+
+static int yaffs_FindBlockForAllocation(yaffs_Device *dev)
+{
+ int i;
+
+ yaffs_BlockInfo *bi;
+
+ 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 erased blocks" TENDSTR)));
+
+ return -1;
+ }
+
+ /* Find an empty block. */
+
+ for (i = dev->internalStartBlock; i <= dev->internalEndBlock; i++) {
+ dev->allocationBlockFinder++;
+ if (dev->allocationBlockFinder < dev->internalStartBlock
+ || dev->allocationBlockFinder > dev->internalEndBlock) {
+ dev->allocationBlockFinder = dev->internalStartBlock;
+ }
+
+ 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, %d left" TENDSTR),
+ dev->allocationBlockFinder, dev->sequenceNumber,
+ dev->nErasedBlocks));
+ return dev->allocationBlockFinder;
+ }
+ }
+
+ T(YAFFS_TRACE_ALWAYS,
+ (TSTR
+ ("yaffs tragedy: no more erased blocks, but there should have been %d"
+ TENDSTR), dev->nErasedBlocks));
+
+ return -1;
+}
+
+
+
+static int yaffs_CalcCheckpointBlocksRequired(yaffs_Device *dev)
+{
+ if (!dev->nCheckpointBlocksRequired &&
+ dev->isYaffs2) {
+ /* Not a valid value so recalculate */
+ int nBytes = 0;
+ int nBlocks;
+ int devBlocks = (dev->endBlock - dev->startBlock + 1);
+ int tnodeSize;
+
+ tnodeSize = (dev->tnodeWidth * YAFFS_NTNODES_LEVEL0)/8;
+
+ if (tnodeSize < sizeof(yaffs_Tnode))
+ tnodeSize = sizeof(yaffs_Tnode);
+
+ nBytes += sizeof(yaffs_CheckpointValidity);
+ nBytes += sizeof(yaffs_CheckpointDevice);
+ nBytes += devBlocks * sizeof(yaffs_BlockInfo);
+ nBytes += devBlocks * dev->chunkBitmapStride;
+ nBytes += (sizeof(yaffs_CheckpointObject) + sizeof(__u32)) * (dev->nObjectsCreated - dev->nFreeObjects);
+ nBytes += (tnodeSize + sizeof(__u32)) * (dev->nTnodesCreated - dev->nFreeTnodes);
+ nBytes += sizeof(yaffs_CheckpointValidity);
+ nBytes += sizeof(__u32); /* checksum*/
+
+ /* Round up and add 2 blocks to allow for some bad blocks, so add 3 */
+
+ nBlocks = (nBytes/(dev->nDataBytesPerChunk * dev->nChunksPerBlock)) + 3;
+
+ dev->nCheckpointBlocksRequired = nBlocks;
+ }
+
+ return dev->nCheckpointBlocksRequired;
+}
+
+/*
+ * Check if there's space to allocate...
+ * Thinks.... do we need top make this ths same as yaffs_GetFreeChunks()?
+ */
+static int yaffs_CheckSpaceForAllocation(yaffs_Device *dev)
+{
+ int reservedChunks;
+ int reservedBlocks = dev->nReservedBlocks;
+ int checkpointBlocks;
+
+ if (dev->isYaffs2) {
+ checkpointBlocks = yaffs_CalcCheckpointBlocksRequired(dev) -
+ dev->blocksInCheckpoint;
+ if (checkpointBlocks < 0)
+ checkpointBlocks = 0;
+ } else {
+ checkpointBlocks = 0;
+ }
+
+ reservedChunks = ((reservedBlocks + checkpointBlocks) * dev->nChunksPerBlock);
+
+ return (dev->nFreeChunks > reservedChunks);
+}
+
+static int yaffs_AllocateChunk(yaffs_Device *dev, int useReserve,
+ yaffs_BlockInfo **blockUsedPtr)
+{
+ 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 && !yaffs_CheckSpaceForAllocation(dev)) {
+ /* 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;
+ }
+
+ if (blockUsedPtr)
+ *blockUsedPtr = bi;
+
+ return retVal;
+ }
+
+ T(YAFFS_TRACE_ERROR,
+ (TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));
+
+ return -1;
+}
+
+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;
+
+}
+
+static int yaffs_GarbageCollectBlock(yaffs_Device *dev, int block,
+ int wholeBlock)
+{
+ int oldChunk;
+ int newChunk;
+ int markNAND;
+ int retVal = YAFFS_OK;
+ int cleanups = 0;
+ int i;
+ int isCheckpointBlock;
+ int matchingChunk;
+ int maxCopies;
+
+ int chunksBefore = yaffs_GetErasedChunks(dev);
+ int chunksAfter;
+
+ yaffs_ExtendedTags tags;
+
+ yaffs_BlockInfo *bi = yaffs_GetBlockInfo(dev, block);
+
+ yaffs_Object *object;
+
+ isCheckpointBlock = (bi->blockState == YAFFS_BLOCK_STATE_CHECKPOINT);
+
+
+ T(YAFFS_TRACE_TRACING,
+ (TSTR("Collecting block %d, in use %d, shrink %d, wholeBlock %d" TENDSTR),
+ block,
+ bi->pagesInUse,
+ bi->hasShrinkHeader,
+ wholeBlock));
+
+ /*yaffs_VerifyFreeChunks(dev); */
+
+ if(bi->blockState == YAFFS_BLOCK_STATE_FULL)
+ bi->blockState = YAFFS_BLOCK_STATE_COLLECTING;