/*
 * Copyright 2010, Haiku Inc. All rights reserved.
 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
 * This file may be used under the terms of the MIT License.
 *
 * Authors:
 *		Janito V. Ferreira Filho
 */
 
 
#include "Journal.h"
 
#include <new>
#include <string.h>
#include <unistd.h>
 
#include <fs_cache.h>
 
#include "CachedBlock.h"
#include "HashRevokeManager.h"
 
 
//#define TRACE_EXT2
#ifdef TRACE_EXT2
#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
#else
#	define TRACE(x...) ;
#endif
#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
#define WARN(x...) dprintf("\33[34mext2:\33[0m " x)
 
 
class LogEntry : public DoublyLinkedListLinkImpl<LogEntry> {
public:
							LogEntry(Journal* journal, uint32 logStart,
								uint32 length);
							~LogEntry();
 
			uint32			Start() const { return fStart; }
			uint32			CommitID() const { return fCommitID; }
 
			Journal*		GetJournal() { return fJournal; }
 
private:
			Journal*		fJournal;
			uint32			fStart;
			uint32			fCommitID;
};
 
 
LogEntry::LogEntry(Journal* journal, uint32 logStart, uint32 commitID)
	:
	fJournal(journal),
	fStart(logStart),
	fCommitID(commitID)
{
}
 
 
LogEntry::~LogEntry()
{
}
 
 
void
JournalHeader::MakeDescriptor(uint32 sequence)
{
	this->magic = B_HOST_TO_BENDIAN_INT32(JOURNAL_MAGIC);
	this->sequence = B_HOST_TO_BENDIAN_INT32(sequence);
	this->block_type = B_HOST_TO_BENDIAN_INT32(JOURNAL_DESCRIPTOR_BLOCK);
}
 
 
void
JournalHeader::MakeCommit(uint32 sequence)
{
	this->magic = B_HOST_TO_BENDIAN_INT32(JOURNAL_MAGIC);
	this->sequence = B_HOST_TO_BENDIAN_INT32(sequence);
	this->block_type = B_HOST_TO_BENDIAN_INT32(JOURNAL_COMMIT_BLOCK);
}
 
 
Journal::Journal(Volume* fsVolume, Volume* jVolume)
	:
	fJournalVolume(jVolume),
	fJournalBlockCache(jVolume->BlockCache()),
	fFilesystemVolume(fsVolume),
	fFilesystemBlockCache(fsVolume->BlockCache()),
	fRevokeManager(NULL),
	fInitStatus(B_OK),
	fBlockSize(sizeof(JournalSuperBlock)),
	fFirstCommitID(0),
	fFirstCacheCommitID(0),
	fFirstLogBlock(1),
	fLogSize(0),
	fVersion(0),
	fLogStart(0),
	fLogEnd(0),
	fFreeBlocks(0),
	fMaxTransactionSize(0),
	fCurrentCommitID(0),
	fHasSubTransaction(false),
	fSeparateSubTransactions(false),
	fUnwrittenTransactions(0),
	fTransactionID(0)
{
	recursive_lock_init(&fLock, "ext2 journal");
	mutex_init(&fLogEntriesLock, "ext2 journal log entries");
 
	HashRevokeManager* revokeManager = new(std::nothrow) HashRevokeManager;
	TRACE("Journal::Journal(): Allocated a hash revoke manager at %p\n",
		revokeManager);
 
	if (revokeManager == NULL)
		fInitStatus = B_NO_MEMORY;
	else {
		fInitStatus = revokeManager->Init();
 
		if (fInitStatus == B_OK) {
			fRevokeManager = revokeManager;
			fInitStatus = _LoadSuperBlock();
		} else
			delete revokeManager;
	}
}
 
 
Journal::Journal()
	:
	fJournalVolume(NULL),
	fJournalBlockCache(NULL),
	fFilesystemVolume(NULL),
	fFilesystemBlockCache(NULL),
	fRevokeManager(NULL),
	fInitStatus(B_OK),
	fBlockSize(sizeof(JournalSuperBlock)),
	fFirstCommitID(0),
	fFirstCacheCommitID(0),
	fFirstLogBlock(1),
	fLogSize(0),
	fVersion(0),
	fIsStarted(false),
	fLogStart(0),
	fLogEnd(0),
	fFreeBlocks(0),
	fMaxTransactionSize(0),
	fCurrentCommitID(0),
	fHasSubTransaction(false),
	fSeparateSubTransactions(false),
	fUnwrittenTransactions(0),
	fTransactionID(0)
{
	recursive_lock_init(&fLock, "ext2 journal");
	mutex_init(&fLogEntriesLock, "ext2 journal log entries");
}
 
 
Journal::~Journal()
{
	TRACE("Journal destructor.\n");
 
	TRACE("Journal::~Journal(): Attempting to delete revoke manager at %p\n",
		fRevokeManager);
	delete fRevokeManager;
 
	recursive_lock_destroy(&fLock);
	mutex_destroy(&fLogEntriesLock);
}
 
 
status_t
Journal::InitCheck()
{
	return fInitStatus;
}
 
 
status_t
Journal::Uninit()
{
	if (!fIsStarted)
		return B_OK;
 
	status_t status = FlushLogAndBlocks();
 
	if (status == B_OK) {
		// Mark journal as clean
		fLogStart = 0;
		status = _SaveSuperBlock();
	}
 
	fIsStarted = false;
 
	return status;
}
 
 
/*virtual*/ status_t
Journal::StartLog()
{
	fLogStart = fFirstLogBlock;
	fLogEnd = fFirstLogBlock;
	fFreeBlocks = 0;
	fIsStarted = true;
 
	fCurrentCommitID = fFirstCommitID;
 
	return _SaveSuperBlock();
}
 
 
status_t
Journal::RestartLog()
{
	fFirstCommitID = 1;
 
	return B_OK;
}
 
 
/*virtual*/ status_t
Journal::Lock(Transaction* owner, bool separateSubTransactions)
{
	TRACE("Journal::Lock()\n");
	status_t status = recursive_lock_lock(&fLock);
	if (status != B_OK)
		return status;
 
	TRACE("Journal::Lock(): Aquired lock\n");
 
	if (!fSeparateSubTransactions && recursive_lock_get_recursion(&fLock) > 1) {
		// reuse current transaction
		TRACE("Journal::Lock(): Reusing current transaction\n");
		return B_OK;
	}
 
	if (separateSubTransactions)
		fSeparateSubTransactions = true;
 
	if (owner != NULL)
		owner->SetParent(fOwner);
 
	fOwner = owner;
 
	if (fOwner != NULL) {
		if (fUnwrittenTransactions > 0) {
			// start a sub transaction
			TRACE("Journal::Lock(): Starting sub transaction\n");
			cache_start_sub_transaction(fFilesystemBlockCache, fTransactionID);
			fHasSubTransaction = true;
		} else {
			TRACE("Journal::Lock(): Starting new transaction\n");
			fTransactionID = cache_start_transaction(fFilesystemBlockCache);
		}
 
		if (fTransactionID < B_OK) {
			recursive_lock_unlock(&fLock);
			return fTransactionID;
		}
 
		cache_add_transaction_listener(fFilesystemBlockCache, fTransactionID,
			TRANSACTION_IDLE, _TransactionIdle, this);
	}
 
	return B_OK;
}
 
 
/*virtual*/ status_t
Journal::Unlock(Transaction* owner, bool success)
{
	TRACE("Journal::Unlock(): Lock recursion: %" B_PRId32 "\n",
		recursive_lock_get_recursion(&fLock));
	if (fSeparateSubTransactions
		|| recursive_lock_get_recursion(&fLock) == 1) {
		// we only end the transaction if we unlock it
		if (owner != NULL) {
			TRACE("Journal::Unlock(): Calling _TransactionDone\n");
			status_t status = _TransactionDone(success);
			if (status != B_OK)
				return status;
 
			TRACE("Journal::Unlock(): Returned from _TransactionDone\n");
			bool separateSubTransactions = fSeparateSubTransactions;
			fSeparateSubTransactions = true;
			TRACE("Journal::Unlock(): Notifying listeners for: %p\n", owner);
			owner->NotifyListeners(success);
			TRACE("Journal::Unlock(): Done notifying listeners\n");
			fSeparateSubTransactions = separateSubTransactions;
 
			fOwner = owner->Parent();
		} else
			fOwner = NULL;
 
		if (fSeparateSubTransactions
			&& recursive_lock_get_recursion(&fLock) == 1)
			fSeparateSubTransactions = false;
	} else
		owner->MoveListenersTo(fOwner);
 
	TRACE("Journal::Unlock(): Unlocking the lock\n");
 
	recursive_lock_unlock(&fLock);
	return B_OK;
}
 
 
status_t
Journal::MapBlock(off_t logical, fsblock_t& physical)
{
	TRACE("Journal::MapBlock()\n");
	physical = logical;
 
	return B_OK;
}
 
 
inline uint32
Journal::FreeLogBlocks() const
{
	TRACE("Journal::FreeLogBlocks(): start: %" B_PRIu32 ", end: %" B_PRIu32
		", size: %" B_PRIu32 "\n", fLogStart, fLogEnd, fLogSize);
	return fLogStart <= fLogEnd
		? fLogSize - fLogEnd + fLogStart - 1
		: fLogStart - fLogEnd;
}
 
 
status_t
Journal::FlushLogAndBlocks()
{
	return _FlushLog(true, true);
}
 
 
int32
Journal::TransactionID() const
{
	return fTransactionID;
}
 
 
status_t
Journal::_WritePartialTransactionToLog(JournalHeader* descriptorBlock,
	bool detached, uint8** _escapedData, uint32 &logBlock, off_t& blockNumber,
	long& cookie, ArrayDeleter<uint8>& escapedDataDeleter, uint32& blockCount,
	bool& finished)
{
	TRACE("Journal::_WritePartialTransactionToLog()\n");
 
	uint32 descriptorBlockPos = logBlock;
	uint8* escapedData = *_escapedData;
 
	JournalBlockTag* tag = (JournalBlockTag*)descriptorBlock->data;
	JournalBlockTag* lastTag = (JournalBlockTag*)((uint8*)descriptorBlock
		+ fBlockSize - sizeof(JournalHeader));
 
	finished = false;
	status_t status = B_OK;
 
	while (tag < lastTag && status == B_OK) {
		tag->SetBlockNumber(blockNumber);
		tag->SetFlags(0);
 
		CachedBlock data(fFilesystemVolume);
		const JournalHeader* blockData = (JournalHeader*)data.SetTo(
			blockNumber);
		if (blockData == NULL) {
			panic("Got a NULL pointer while iterating through transaction "
				"blocks.\n");
			return B_ERROR;
		}
 
		void* finalData;
 
		if (blockData->CheckMagic()) {
			// The journaled block starts with the magic value
			// We must remove it to prevent confusion
			TRACE("Journal::_WritePartialTransactionToLog(): Block starts with "
				"magic number. Escaping it\n");
			tag->SetEscapedFlag();
 
			if (escapedData == NULL) {
				TRACE("Journal::_WritePartialTransactionToLog(): Allocating "
					"space for escaped block (%" B_PRIu32 ")\n", fBlockSize);
				escapedData = new(std::nothrow) uint8[fBlockSize];
				if (escapedData == NULL) {
					TRACE("Journal::_WritePartialTransactionToLof(): Failed to "
						"allocate buffer for escaped data block\n");
					return B_NO_MEMORY;
				}
				escapedDataDeleter.SetTo(escapedData);
				*_escapedData = escapedData;
 
				((int32*)escapedData)[0] = 0; // Remove magic
			}
 
			memcpy(escapedData + 4, blockData->data, fBlockSize - 4);
			finalData = escapedData;
		} else
			finalData = (void*)blockData;
 
		// TODO: use iovecs?
 
		logBlock = _WrapAroundLog(logBlock + 1);
 
		fsblock_t physicalBlock;
		status = MapBlock(logBlock, physicalBlock);
		if (status != B_OK)
			return status;
 
		off_t logOffset = physicalBlock * fBlockSize;
 
		TRACE("Journal::_WritePartialTransactionToLog(): Writing from memory: "
			"%p, to disk: %" B_PRIdOFF "\n", finalData, logOffset);
		size_t written = write_pos(fJournalVolume->Device(), logOffset,
			finalData, fBlockSize);
		if (written != fBlockSize) {
			TRACE("Failed to write journal block.\n");
			return B_IO_ERROR;
		}
 
		TRACE("Journal::_WritePartialTransactionToLog(): Wrote a journal block "
			"at: %" B_PRIu32 "\n", logBlock);
 
		blockCount++;
		tag++;
 
		status = cache_next_block_in_transaction(fFilesystemBlockCache,
			fTransactionID, detached, &cookie, &blockNumber, NULL, NULL);
	}
 
	finished = status != B_OK;
 
	// Write descriptor block
	--tag;
	tag->SetLastTagFlag();
 
	fsblock_t physicalBlock;
	status = MapBlock(descriptorBlockPos, physicalBlock);
	if (status != B_OK)
		return status;
 
	off_t descriptorBlockOffset = physicalBlock * fBlockSize;
 
	TRACE("Journal::_WritePartialTransactionToLog(): Writing to: %" B_PRIdOFF
		"\n", descriptorBlockOffset);
	size_t written = write_pos(fJournalVolume->Device(),
		descriptorBlockOffset, descriptorBlock, fBlockSize);
	if (written != fBlockSize) {
		TRACE("Failed to write journal descriptor block.\n");
		return B_IO_ERROR;
	}
 
	blockCount++;
	logBlock = _WrapAroundLog(logBlock + 1);
 
	return B_OK;
}
 
 
status_t
Journal::_WriteTransactionToLog()
{
	TRACE("Journal::_WriteTransactionToLog()\n");
	// Transaction enters the Flush state
	bool detached = false;
	TRACE("Journal::_WriteTransactionToLog(): Attempting to get transaction "
		"size\n");
	size_t size = _FullTransactionSize();
	TRACE("Journal::_WriteTransactionToLog(): transaction size: %" B_PRIuSIZE
		"\n", size);
 
	if (size > fMaxTransactionSize) {
		TRACE("Journal::_WriteTransactionToLog(): not enough free space "
			"for the transaction. Attempting to free some space.\n");
		size = _MainTransactionSize();
		TRACE("Journal::_WriteTransactionToLog(): main transaction size: %"
			B_PRIuSIZE "\n", size);
 
		if (fHasSubTransaction && size < fMaxTransactionSize) {
			TRACE("Journal::_WriteTransactionToLog(): transaction doesn't fit, "
				"but it can be separated\n");
			detached = true;
		} else {
			// Error: transaction can't fit in log
			panic("transaction too large (size: %" B_PRIuSIZE ", max size: %"
				B_PRIu32 ", log size: %" B_PRIu32 ")\n", size,
				fMaxTransactionSize, fLogSize);
			return B_BUFFER_OVERFLOW;
		}
	}
 
	TRACE("Journal::_WriteTransactionToLog(): free log blocks: %" B_PRIu32
		"\n", FreeLogBlocks());
	if (size > FreeLogBlocks()) {
		TRACE("Journal::_WriteTransactionToLog(): Syncing block cache\n");
		cache_sync_transaction(fFilesystemBlockCache, fTransactionID);
 
		if (size > FreeLogBlocks()) {
			panic("Transaction fits, but sync didn't result in enough"
				"free space.\n\tGot %" B_PRIu32 " when at least %" B_PRIuSIZE
				" was expected.", FreeLogBlocks(), size);
		}
	}
 
	TRACE("Journal::_WriteTransactionToLog(): finished managing space for "
		"the transaction\n");
 
	fHasSubTransaction = false;
	if (!fIsStarted)
		StartLog();
 
	// Prepare Descriptor block
	TRACE("Journal::_WriteTransactionToLog(): attempting to allocate space for "
		"the descriptor block, block size %" B_PRIu32 "\n", fBlockSize);
	JournalHeader* descriptorBlock =
		(JournalHeader*)new(std::nothrow) uint8[fBlockSize];
	if (descriptorBlock == NULL) {
		TRACE("Journal::_WriteTransactionToLog(): Failed to allocate a buffer "
			"for the descriptor block\n");
		return B_NO_MEMORY;
	}
	ArrayDeleter<uint8> descriptorBlockDeleter((uint8*)descriptorBlock);
 
	descriptorBlock->MakeDescriptor(fCurrentCommitID);
 
	// Prepare Commit block
	TRACE("Journal::_WriteTransactionToLog(): attempting to allocate space for "
		"the commit block, block size %" B_PRIu32 "\n", fBlockSize);
	JournalHeader* commitBlock =
		(JournalHeader*)new(std::nothrow) uint8[fBlockSize];
	if (commitBlock == NULL) {
		TRACE("Journal::_WriteTransactionToLog(): Failed to allocate a buffer "
			"for the commit block\n");
		return B_NO_MEMORY;
	}
	ArrayDeleter<uint8> commitBlockDeleter((uint8*)commitBlock);
 
	commitBlock->MakeCommit(fCurrentCommitID + 1);
	memset(commitBlock->data, 0, fBlockSize - sizeof(JournalHeader));
		// TODO: This probably isn't necessary
 
	uint8* escapedData = NULL;
	ArrayDeleter<uint8> escapedDataDeleter;
 
	off_t blockNumber;
	long cookie = 0;
 
	status_t status = cache_next_block_in_transaction(fFilesystemBlockCache,
		fTransactionID, detached, &cookie, &blockNumber, NULL, NULL);
	if (status != B_OK) {
		TRACE("Journal::_WriteTransactionToLog(): Transaction has no blocks to "
			"write\n");
		return B_OK;
	}
 
	uint32 blockCount = 0;
 
	uint32 logBlock = _WrapAroundLog(fLogEnd);
 
	bool finished = false;
 
	status = _WritePartialTransactionToLog(descriptorBlock, detached,
		&escapedData, logBlock, blockNumber, cookie, escapedDataDeleter,
		blockCount, finished);
	if (!finished && status != B_OK)
		return status;
 
	uint32 commitBlockPos = logBlock;
 
	while (!finished) {
		descriptorBlock->IncrementSequence();
 
		status = _WritePartialTransactionToLog(descriptorBlock, detached,
			&escapedData, logBlock, blockNumber, cookie, escapedDataDeleter,
			blockCount, finished);
		if (!finished && status != B_OK)
			return status;
 
		// It is okay to write the commit blocks of the partial transactions
		// as long as the commit block of the first partial transaction isn't
		// written. When it recovery reaches where the first commit should be
		// and doesn't find it, it considers it found the end of the log.
 
		fsblock_t physicalBlock;
		status = MapBlock(logBlock, physicalBlock);
		if (status != B_OK)
			return status;
 
		off_t logOffset = physicalBlock * fBlockSize;
 
		TRACE("Journal::_WriteTransactionToLog(): Writting commit block to "
			"%" B_PRIdOFF "\n", logOffset);
		off_t written = write_pos(fJournalVolume->Device(), logOffset,
			commitBlock, fBlockSize);
		if (written != fBlockSize) {
			TRACE("Failed to write journal commit block.\n");
			return B_IO_ERROR;
		}
 
		commitBlock->IncrementSequence();
		blockCount++;
 
		logBlock = _WrapAroundLog(logBlock + 1);
	}
 
	// Transaction will enter the Commit state
	fsblock_t physicalBlock;
	status = MapBlock(commitBlockPos, physicalBlock);
	if (status != B_OK)
		return status;
 
	off_t logOffset = physicalBlock * fBlockSize;
 
	TRACE("Journal::_WriteTransactionToLog(): Writing to: %" B_PRIdOFF "\n",
		logOffset);
	off_t written = write_pos(fJournalVolume->Device(), logOffset, commitBlock,
		fBlockSize);
	if (written != fBlockSize) {
		TRACE("Failed to write journal commit block.\n");
		return B_IO_ERROR;
	}
 
	blockCount++;
	fLogEnd = _WrapAroundLog(fLogEnd + blockCount);
 
	status = _SaveSuperBlock();
 
	// Transaction will enter Finished state
	LogEntry *logEntry = new LogEntry(this, fLogEnd, fCurrentCommitID++);
	TRACE("Journal::_WriteTransactionToLog(): Allocating log entry at %p\n",
		logEntry);
	if (logEntry == NULL) {
		panic("no memory to allocate log entries!");
		return B_NO_MEMORY;
	}
 
	mutex_lock(&fLogEntriesLock);
	fLogEntries.Add(logEntry);
	mutex_unlock(&fLogEntriesLock);
 
	if (detached) {
		fTransactionID = cache_detach_sub_transaction(fFilesystemBlockCache,
			fTransactionID, _TransactionWritten, logEntry);
		fUnwrittenTransactions = 1;
 
		if (status == B_OK && _FullTransactionSize() > fLogSize) {
			// If the transaction is too large after writing, there is no way to
			// recover, so let this transaction fail.
			ERROR("transaction too large (%" B_PRIuSIZE " blocks, log size %"
				B_PRIu32 ")!\n", _FullTransactionSize(), fLogSize);
			return B_BUFFER_OVERFLOW;
		}
	} else {
		cache_end_transaction(fFilesystemBlockCache, fTransactionID,
			_TransactionWritten, logEntry);
		fUnwrittenTransactions = 0;
	}
 
	return B_OK;
}
 
 
status_t
Journal::_SaveSuperBlock()
{
	TRACE("Journal::_SaveSuperBlock()\n");
	fsblock_t physicalBlock;
	status_t status = MapBlock(0, physicalBlock);
	if (status != B_OK)
		return status;
 
	off_t superblockPos = physicalBlock * fBlockSize;
 
	JournalSuperBlock superblock;
	size_t bytesRead = read_pos(fJournalVolume->Device(), superblockPos,
		&superblock, sizeof(superblock));
 
	if (bytesRead != sizeof(superblock))
		return B_IO_ERROR;
 
	superblock.SetFirstCommitID(fFirstCommitID);
	superblock.SetLogStart(fLogStart);
 
	TRACE("Journal::SaveSuperBlock(): Write to %" B_PRIdOFF "\n",
		superblockPos);
	size_t bytesWritten = write_pos(fJournalVolume->Device(), superblockPos,
		&superblock, sizeof(superblock));
 
	if (bytesWritten != sizeof(superblock))
		return B_IO_ERROR;
 
	TRACE("Journal::_SaveSuperBlock(): Done\n");
 
	return B_OK;
}
 
 
status_t
Journal::_LoadSuperBlock()
{
	TRACE("Journal::_LoadSuperBlock()\n");
	fsblock_t superblockPos;
 
	status_t status = MapBlock(0, superblockPos);
	if (status != B_OK)
		return status;
 
	TRACE("Journal::_LoadSuperBlock(): superblock physical block: %" B_PRIu64
		"\n", superblockPos);
 
	JournalSuperBlock superblock;
	size_t bytesRead = read_pos(fJournalVolume->Device(), superblockPos
		* fJournalVolume->BlockSize(), &superblock, sizeof(superblock));
 
	if (bytesRead != sizeof(superblock)) {
		ERROR("Journal::_LoadSuperBlock(): failed to read superblock\n");
		return B_IO_ERROR;
	}
 
	if (!superblock.header.CheckMagic()) {
		ERROR("Journal::_LoadSuperBlock(): Invalid superblock magic %" B_PRIx32
			"\n", superblock.header.Magic());
		return B_BAD_VALUE;
	}
 
	if (superblock.header.BlockType() == JOURNAL_SUPERBLOCK_V1) {
		TRACE("Journal::_LoadSuperBlock(): Journal superblock version 1\n");
		fVersion = 1;
	} else if (superblock.header.BlockType() == JOURNAL_SUPERBLOCK_V2) {
		TRACE("Journal::_LoadSuperBlock(): Journal superblock version 2\n");
		fVersion = 2;
	} else {
		ERROR("Journal::_LoadSuperBlock(): Invalid superblock version\n");
		return B_BAD_VALUE;
	}
 
	if (fVersion >= 2) {
		status = _CheckFeatures(&superblock);
 
		if (status != B_OK) {
			ERROR("Journal::_LoadSuperBlock(): Unsupported features\n");
			return status;
		}
	}
 
	fBlockSize = superblock.BlockSize();
	fFirstCommitID = superblock.FirstCommitID();
	fFirstLogBlock = superblock.FirstLogBlock();
	fLogStart = superblock.LogStart();
	fLogSize = superblock.NumBlocks();
 
	uint32 descriptorTags = (fBlockSize - sizeof(JournalHeader))
		/ sizeof(JournalBlockTag);
		// Maximum tags per descriptor block
	uint32 maxDescriptors = (fLogSize - 1) / (descriptorTags + 2);
		// Maximum number of full journal transactions
	fMaxTransactionSize = maxDescriptors * descriptorTags;
	fMaxTransactionSize += (fLogSize - 1) - fMaxTransactionSize - 2;
		// Maximum size of a "logical" transaction
		// TODO: Why is "superblock.MaxTransactionBlocks();" zero?
	//fFirstCacheCommitID = fFirstCommitID - fTransactionID /*+ 1*/;
 
	TRACE("Journal::_LoadSuperBlock(): block size: %" B_PRIu32 ", first commit"
		" id: %" B_PRIu32 ", first log block: %" B_PRIu32 ", log start: %"
		B_PRIu32 ", log size: %" B_PRIu32 ", max transaction size: %" B_PRIu32
		"\n", fBlockSize, fFirstCommitID, fFirstLogBlock, fLogStart,
		fLogSize, fMaxTransactionSize);
 
	return B_OK;
}
 
 
status_t
Journal::_CheckFeatures(JournalSuperBlock* superblock)
{
	if ((superblock->ReadOnlyCompatibleFeatures()
			& ~JOURNAL_KNOWN_READ_ONLY_COMPATIBLE_FEATURES) != 0
		|| (superblock->IncompatibleFeatures()
			& ~JOURNAL_KNOWN_INCOMPATIBLE_FEATURES) != 0)
		return B_UNSUPPORTED;
 
	return B_OK;
}
 
 
uint32
Journal::_CountTags(JournalHeader* descriptorBlock)
{
	uint32 count = 0;
 
	JournalBlockTag* tags = (JournalBlockTag*)descriptorBlock->data;
		// Skip the header
	JournalBlockTag* lastTag = (JournalBlockTag*)
		(descriptorBlock + fBlockSize - sizeof(JournalBlockTag));
 
	while (tags < lastTag && (tags->Flags() & JOURNAL_FLAG_LAST_TAG) == 0) {
		if ((tags->Flags() & JOURNAL_FLAG_SAME_UUID) == 0) {
			// sizeof(UUID) = 16 = 2*sizeof(JournalBlockTag)
			tags += 2;	// Skip new UUID
		}
 
		TRACE("Journal::_CountTags(): Tag block: %" B_PRIu32 "\n",
			tags->BlockNumber());
 
		tags++; // Go to next tag
		count++;
	}
 
	if ((tags->Flags() & JOURNAL_FLAG_LAST_TAG) != 0)
		count++;
 
	TRACE("Journal::_CountTags(): counted tags: %" B_PRIu32 "\n", count);
 
	return count;
}
 
 
/*virtual*/ status_t
Journal::Recover()
{
	TRACE("Journal::Recover()\n");
	if (fLogStart == 0) // Journal was cleanly unmounted
		return B_OK;
 
	TRACE("Journal::Recover(): Journal needs recovery\n");
 
	uint32 lastCommitID;
 
	status_t status = _RecoverPassScan(lastCommitID);
	if (status != B_OK)
		return status;
 
	status = _RecoverPassRevoke(lastCommitID);
	if (status != B_OK)
		return status;
 
	return _RecoverPassReplay(lastCommitID);
}
 
 
// First pass: Find the end of the log
status_t
Journal::_RecoverPassScan(uint32& lastCommitID)
{
	TRACE("Journal Recover: 1st Pass: Scan\n");
 
	CachedBlock cached(fJournalVolume);
	JournalHeader* header;
	uint32 nextCommitID = fFirstCommitID;
	uint32 nextBlock = fLogStart;
	fsblock_t nextBlockPos;
 
	status_t status = MapBlock(nextBlock, nextBlockPos);
	if (status != B_OK)
		return status;
 
	header = (JournalHeader*)cached.SetTo(nextBlockPos);
 
	while (header->CheckMagic() && header->Sequence() == nextCommitID) {
		uint32 blockType = header->BlockType();
 
		if (blockType == JOURNAL_DESCRIPTOR_BLOCK) {
			uint32 tags = _CountTags(header);
			nextBlock += tags;
			TRACE("Journal recover pass scan: Found a descriptor block with "
				"%" B_PRIu32 " tags\n", tags);
		} else if (blockType == JOURNAL_COMMIT_BLOCK) {
			nextCommitID++;
			TRACE("Journal recover pass scan: Found a commit block. Next "
				"commit ID: %" B_PRIu32 "\n", nextCommitID);
		} else if (blockType != JOURNAL_REVOKE_BLOCK) {
			TRACE("Journal recover pass scan: Reached an unrecognized block, "
				"assuming as log's end.\n");
			break;
		} else {
			TRACE("Journal recover pass scan: Found a revoke block, "
				"skipping it\n");
		}
 
		nextBlock = _WrapAroundLog(nextBlock + 1);
 
		status = MapBlock(nextBlock, nextBlockPos);
		if (status != B_OK)
			return status;
 
		header = (JournalHeader*)cached.SetTo(nextBlockPos);
	}
 
	TRACE("Journal Recovery pass scan: Last detected transaction ID: %"
		B_PRIu32 "\n", nextCommitID);
 
	lastCommitID = nextCommitID;
	return B_OK;
}
 
 
// Second pass: Collect all revoked blocks
status_t
Journal::_RecoverPassRevoke(uint32 lastCommitID)
{
	TRACE("Journal Recover: 2nd Pass: Revoke\n");
 
	CachedBlock cached(fJournalVolume);
	JournalHeader* header;
	uint32 nextCommitID = fFirstCommitID;
	uint32 nextBlock = fLogStart;
	fsblock_t nextBlockPos;
 
	status_t status = MapBlock(nextBlock, nextBlockPos);
	if (status != B_OK)
		return status;
 
	header = (JournalHeader*)cached.SetTo(nextBlockPos);
 
	while (nextCommitID < lastCommitID) {
		if (!header->CheckMagic() || header->Sequence() != nextCommitID) {
			// Somehow the log is different than the expexted
			return B_ERROR;
		}
 
		uint32 blockType = header->BlockType();
 
		if (blockType == JOURNAL_DESCRIPTOR_BLOCK)
			nextBlock += _CountTags(header);
		else if (blockType == JOURNAL_COMMIT_BLOCK)
			nextCommitID++;
		else if (blockType == JOURNAL_REVOKE_BLOCK) {
			TRACE("Journal::_RecoverPassRevoke(): Found a revoke block\n");
			status = fRevokeManager->ScanRevokeBlock(
				(JournalRevokeHeader*)header, nextCommitID);
 
			if (status != B_OK)
				return status;
		} else {
			WARN("Journal::_RecoverPassRevoke(): Found an unrecognized block\n");
			break;
		}
 
		nextBlock = _WrapAroundLog(nextBlock + 1);
 
		status = MapBlock(nextBlock, nextBlockPos);
		if (status != B_OK)
			return status;
 
		header = (JournalHeader*)cached.SetTo(nextBlockPos);
	}
 
	if (nextCommitID != lastCommitID) {
		// Possibly because of some sort of IO error
		TRACE("Journal::_RecoverPassRevoke(): Incompatible commit IDs\n");
		return B_ERROR;
	}
 
	TRACE("Journal recovery pass revoke: Revoked blocks: %" B_PRIu32 "\n",
		fRevokeManager->NumRevokes());
 
	return B_OK;
}
 
 
// Third pass: Replay log
status_t
Journal::_RecoverPassReplay(uint32 lastCommitID)
{
	TRACE("Journal Recover: 3rd Pass: Replay\n");
 
	uint32 nextCommitID = fFirstCommitID;
	uint32 nextBlock = fLogStart;
	fsblock_t nextBlockPos;
 
	status_t status = MapBlock(nextBlock, nextBlockPos);
	if (status != B_OK)
		return status;
 
	CachedBlock cached(fJournalVolume);
	JournalHeader* header = (JournalHeader*)cached.SetTo(nextBlockPos);
 
	int count = 0;
 
	uint8* data = new(std::nothrow) uint8[fBlockSize];
	if (data == NULL) {
		TRACE("Journal::_RecoverPassReplay(): Failed to allocate memory for "
			"data\n");
		return B_NO_MEMORY;
	}
 
	ArrayDeleter<uint8> dataDeleter(data);
 
	while (nextCommitID < lastCommitID) {
		if (!header->CheckMagic() || header->Sequence() != nextCommitID) {
			// Somehow the log is different than the expected
			ERROR("Journal::_RecoverPassReplay(): Weird problem with block\n");
			return B_ERROR;
		}
 
		uint32 blockType = header->BlockType();
 
		if (blockType == JOURNAL_DESCRIPTOR_BLOCK) {
			JournalBlockTag* last_tag = (JournalBlockTag*)((uint8*)header
				+ fBlockSize - sizeof(JournalBlockTag));
 
			for (JournalBlockTag* tag = (JournalBlockTag*)header->data;
				tag <= last_tag; ++tag) {
				nextBlock = _WrapAroundLog(nextBlock + 1);
 
				status = MapBlock(nextBlock, nextBlockPos);
				if (status != B_OK)
					return status;
 
				if (!fRevokeManager->Lookup(tag->BlockNumber(),
						nextCommitID)) {
					// Block isn't revoked
					size_t read = read_pos(fJournalVolume->Device(),
						nextBlockPos * fBlockSize, data, fBlockSize);
					if (read != fBlockSize)
						return B_IO_ERROR;
 
					if ((tag->Flags() & JOURNAL_FLAG_ESCAPED) != 0) {
						// Block is escaped
						((int32*)data)[0]
							= B_HOST_TO_BENDIAN_INT32(JOURNAL_MAGIC);
					}
 
					TRACE("Journal::_RevoverPassReplay(): Write to %" B_PRIu32
						"\n", tag->BlockNumber() * fBlockSize);
					size_t written = write_pos(fFilesystemVolume->Device(),
						tag->BlockNumber() * fBlockSize, data, fBlockSize);
 
					if (written != fBlockSize)
						return B_IO_ERROR;
 
					++count;
				}
 
				if ((tag->Flags() & JOURNAL_FLAG_LAST_TAG) != 0)
					break;
				if ((tag->Flags() & JOURNAL_FLAG_SAME_UUID) == 0) {
					// TODO: Check new UUID with file system UUID
					tag += 2;
						// sizeof(JournalBlockTag) = 8
						// sizeof(UUID) = 16
				}
			}
		} else if (blockType == JOURNAL_COMMIT_BLOCK)
			nextCommitID++;
		else if (blockType != JOURNAL_REVOKE_BLOCK) {
			WARN("Journal::_RecoverPassReplay(): Found an unrecognized block\n");
			break;
		} // If blockType == JOURNAL_REVOKE_BLOCK we just skip it
 
		nextBlock = _WrapAroundLog(nextBlock + 1);
 
		status = MapBlock(nextBlock, nextBlockPos);
		if (status != B_OK)
			return status;
 
		header = (JournalHeader*)cached.SetTo(nextBlockPos);
	}
 
	if (nextCommitID != lastCommitID) {
		// Possibly because of some sort of IO error
		return B_ERROR;
	}
 
	TRACE("Journal recovery pass replay: Replayed blocks: %u\n", count);
 
	return B_OK;
}
 
 
status_t
Journal::_FlushLog(bool canWait, bool flushBlocks)
{
	TRACE("Journal::_FlushLog()\n");
	status_t status = canWait ? recursive_lock_lock(&fLock)
		: recursive_lock_trylock(&fLock);
 
	TRACE("Journal::_FlushLog(): Acquired fLock, recursion: %" B_PRId32 "\n",
		recursive_lock_get_recursion(&fLock));
	if (status != B_OK)
		return status;
 
	if (recursive_lock_get_recursion(&fLock) > 1) {
		// Called from inside a transaction
		recursive_lock_unlock(&fLock);
		TRACE("Journal::_FlushLog(): Called from a transaction. Leaving...\n");
		return B_OK;
	}
 
	if (fUnwrittenTransactions != 0 && _FullTransactionSize() != 0) {
		status = _WriteTransactionToLog();
		if (status < B_OK)
			panic("Failed flushing transaction: %s\n", strerror(status));
	}
 
	TRACE("Journal::_FlushLog(): Attempting to flush journal volume at %p\n",
		fJournalVolume);
 
	// TODO: Not sure this is correct. Need to review...
	// NOTE: Not correct. Causes double lock of a block cache mutex
	// TODO: Need some other way to synchronize the journal...
	/*status = fJournalVolume->FlushDevice();
	if (status != B_OK)
		return status;*/
 
	TRACE("Journal::_FlushLog(): Flushed journal volume\n");
 
	if (flushBlocks) {
		TRACE("Journal::_FlushLog(): Attempting to flush file system volume "
			"at %p\n", fFilesystemVolume);
		status = fFilesystemVolume->FlushDevice();
		if (status == B_OK)
			TRACE("Journal::_FlushLog(): Flushed file system volume\n");
	}
 
	TRACE("Journal::_FlushLog(): Finished. Releasing lock\n");
 
	recursive_lock_unlock(&fLock);
 
	TRACE("Journal::_FlushLog(): Done, final status: %s\n", strerror(status));
	return status;
}
 
 
inline uint32
Journal::_WrapAroundLog(uint32 block)
{
	TRACE("Journal::_WrapAroundLog()\n");
	if (block >= fLogSize)
		return block - fLogSize + fFirstLogBlock;
	else
		return block;
}
 
 
size_t
Journal::_CurrentTransactionSize() const
{
	TRACE("Journal::_CurrentTransactionSize(): transaction %" B_PRIu32 "\n",
		fTransactionID);
 
	size_t count;
 
	if (fHasSubTransaction) {
		count = cache_blocks_in_sub_transaction(fFilesystemBlockCache,
			fTransactionID);
 
		TRACE("\tSub transaction size: %" B_PRIuSIZE "\n", count);
	} else {
		count =  cache_blocks_in_transaction(fFilesystemBlockCache,
			fTransactionID);
 
		TRACE("\tTransaction size: %" B_PRIuSIZE "\n", count);
	}
 
	return count;
}
 
 
size_t
Journal::_FullTransactionSize() const
{
	TRACE("Journal::_FullTransactionSize(): transaction %" B_PRIu32 "\n",
		fTransactionID);
	TRACE("\tFile sytem block cache: %p\n", fFilesystemBlockCache);
 
	size_t count = cache_blocks_in_transaction(fFilesystemBlockCache,
		 fTransactionID);
 
	TRACE("\tFull transaction size: %" B_PRIuSIZE "\n", count);
 
	return count;
}
 
 
size_t
Journal::_MainTransactionSize() const
{
	TRACE("Journal::_MainTransactionSize(): transaction %" B_PRIu32 "\n",
		fTransactionID);
 
	size_t count =  cache_blocks_in_main_transaction(fFilesystemBlockCache,
		fTransactionID);
 
	TRACE("\tMain transaction size: %" B_PRIuSIZE "\n", count);
 
	return count;
}
 
 
status_t
Journal::_TransactionDone(bool success)
{
	if (!success) {
		if (fHasSubTransaction) {
			TRACE("Journal::_TransactionDone(): transaction %" B_PRIu32
				" failed, aborting subtransaction\n", fTransactionID);
			cache_abort_sub_transaction(fFilesystemBlockCache, fTransactionID);
			// parent is unaffected
		} else {
			TRACE("Journal::_TransactionDone(): transaction %" B_PRIu32
				" failed, aborting\n", fTransactionID);
			cache_abort_transaction(fFilesystemBlockCache, fTransactionID);
			fUnwrittenTransactions = 0;
		}
 
		TRACE("Journal::_TransactionDone(): returning B_OK\n");
		return B_OK;
	}
 
	// If possible, delay flushing the transaction
	uint32 size = _FullTransactionSize();
	TRACE("Journal::_TransactionDone(): full transaction size: %" B_PRIu32
		", max transaction size: %" B_PRIu32 ", free log blocks: %" B_PRIu32
		"\n", size, fMaxTransactionSize, FreeLogBlocks());
	if (fMaxTransactionSize > 0 && size < fMaxTransactionSize) {
		TRACE("Journal::_TransactionDone(): delaying flush of transaction "
			"%" B_PRIu32 "\n", fTransactionID);
 
		// Make sure the transaction fits in the log
		if (size < FreeLogBlocks())
			cache_sync_transaction(fFilesystemBlockCache, fTransactionID);
 
		fUnwrittenTransactions++;
		TRACE("Journal::_TransactionDone(): returning B_OK\n");
		return B_OK;
	}
 
	return _WriteTransactionToLog();
}
 
 
/*static*/ void
Journal::_TransactionWritten(int32 transactionID, int32 event, void* _logEntry)
{
	LogEntry* logEntry = (LogEntry*)_logEntry;
 
	TRACE("Journal::_TransactionWritten(): Transaction %" B_PRIu32
		" checkpointed\n", transactionID);
 
	Journal* journal = logEntry->GetJournal();
 
	TRACE("Journal::_TransactionWritten(): log entry: %p, journal: %p\n",
		logEntry, journal);
	TRACE("Journal::_TransactionWritten(): log entries: %p\n",
		&journal->fLogEntries);
 
	mutex_lock(&journal->fLogEntriesLock);
 
	TRACE("Journal::_TransactionWritten(): first log entry: %p\n",
		journal->fLogEntries.First());
	if (logEntry == journal->fLogEntries.First()) {
		TRACE("Journal::_TransactionWritten(): Moving start of log to %"
			B_PRIu32 "\n", logEntry->Start());
		journal->fLogStart = logEntry->Start();
		journal->fFirstCommitID = logEntry->CommitID();
		TRACE("Journal::_TransactionWritten(): Setting commit ID to %" B_PRIu32
			"\n", logEntry->CommitID());
 
		if (journal->_SaveSuperBlock() != B_OK)
			panic("ext2: Failed to write journal superblock\n");
	}
 
	TRACE("Journal::_TransactionWritten(): Removing log entry\n");
	journal->fLogEntries.Remove(logEntry);
 
	TRACE("Journal::_TransactionWritten(): Unlocking entries list\n");
	mutex_unlock(&journal->fLogEntriesLock);
 
	TRACE("Journal::_TransactionWritten(): Deleting log entry at %p\n", logEntry);
	delete logEntry;
}
 
 
/*static*/ void
Journal::_TransactionIdle(int32 transactionID, int32 event, void* _journal)
{
	Journal* journal = (Journal*)_journal;
	journal->_FlushLog(false, false);
}