/*
 * 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 "CRCTable.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(
		fsVolume->Has64bitFeature());
	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),
	fOwner(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),
	fChecksumEnabled(false),
	fChecksumV3Enabled(false),
	fFeature64bits(false)
{
	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);

	if (fChecksumEnabled)
		superblock.SetChecksum(_Checksum(&superblock));

	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()
{
	STATIC_ASSERT(sizeof(struct JournalHeader) == 12);
	STATIC_ASSERT(sizeof(struct JournalSuperBlock) == 1024);

	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) {
		TRACE("Journal::_LoadSuperBlock(): incompatible features %" B_PRIx32
			", read-only features %" B_PRIx32 "\n",
			superblock.IncompatibleFeatures(),
			superblock.ReadOnlyCompatibleFeatures());

		status = _CheckFeatures(&superblock);

		if (status != B_OK)
			return status;

		if (fChecksumEnabled) {
			if (superblock.Checksum() != _Checksum(&superblock)) {
				ERROR("Journal::_LoadSuperBlock(): Invalid checksum\n");
				return B_BAD_DATA;
			}
			fChecksumSeed = calculate_crc32c(0xffffffff, (uint8*)superblock.uuid,
				sizeof(superblock.uuid));
		}
	}

	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)
{
	uint32 readonly = superblock->ReadOnlyCompatibleFeatures();
	uint32 incompatible = superblock->IncompatibleFeatures();
	bool hasReadonly = (readonly & ~JOURNAL_KNOWN_READ_ONLY_COMPATIBLE_FEATURES)
		!= 0;
	bool hasIncompatible = (incompatible
		& ~JOURNAL_KNOWN_INCOMPATIBLE_FEATURES) != 0;
	if (hasReadonly || hasIncompatible ) {
		ERROR("Journal::_CheckFeatures(): Unsupported features: %" B_PRIx32
			" %" B_PRIx32 "\n", readonly, incompatible);
		return B_UNSUPPORTED;
	}

	bool hasCsumV2 =
		(superblock->IncompatibleFeatures() & JOURNAL_FEATURE_INCOMPATIBLE_CSUM_V2) != 0;
	bool hasCsumV3 =
		(superblock->IncompatibleFeatures() & JOURNAL_FEATURE_INCOMPATIBLE_CSUM_V3) != 0;
	if (hasCsumV2 && hasCsumV3) {
		return B_BAD_VALUE;
	}

	fChecksumEnabled = hasCsumV2 && hasCsumV3;
	fChecksumV3Enabled = hasCsumV3;
	fFeature64bits =
		(superblock->IncompatibleFeatures() & JOURNAL_FEATURE_INCOMPATIBLE_64BIT) != 0;
	return B_OK;
}


uint32
Journal::_Checksum(JournalSuperBlock* superblock)
{
	uint32 oldChecksum = superblock->checksum;
	superblock->checksum = 0;
	uint32 checksum = calculate_crc32c(0xffffffff, (uint8*)superblock,
		sizeof(JournalSuperBlock));
	superblock->checksum = oldChecksum;
	return checksum;
}


bool
Journal::_Checksum(uint8* block, bool set)
{
	JournalBlockTail *tail = (JournalBlockTail*)(block + fBlockSize
		- sizeof(JournalBlockTail));
	uint32 oldChecksum = tail->checksum;
	tail->checksum = 0;
	uint32 checksum = calculate_crc32c(0xffffffff, block, fBlockSize);
	if (set) {
		tail->checksum = checksum;
	} else {
		tail->checksum = oldChecksum;
	}
	return checksum == oldChecksum;
}


uint32
Journal::_CountTags(JournalHeader* descriptorBlock)
{
	uint32 count = 0;
	size_t tagSize = _TagSize();
	size_t size = fBlockSize;

	if (fChecksumEnabled)
		size -= sizeof(JournalBlockTail);

	JournalBlockTag* tags = (JournalBlockTag*)descriptorBlock->data;
		// Skip the header
	JournalBlockTag* lastTag = (JournalBlockTag*)
		(descriptorBlock + size - tagSize);

	while (tags < lastTag && (tags->Flags() & JOURNAL_FLAG_LAST_TAG) == 0) {
		if ((tags->Flags() & JOURNAL_FLAG_SAME_UUID) == 0)
			tags = (JournalBlockTag*)((uint8*)tags + 16); // Skip new UUID

		TRACE("Journal::_CountTags(): Tag block: %" B_PRIu32 "\n",
			tags->BlockNumber());

		tags = (JournalBlockTag*)((uint8*)tags + tagSize); // 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;
}


size_t
Journal::_TagSize()
{
	if (fChecksumV3Enabled)
		return sizeof(JournalBlockTagV3);

	size_t size = sizeof(JournalBlockTag);
	if (fChecksumEnabled)
		size += sizeof(uint16);
	if (!fFeature64bits)
		size -= sizeof(uint32);
	return size;
}


/*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) {
			if (fChecksumEnabled && !_Checksum((uint8*)header, false)) {
				ERROR("Journal::_RecoverPassScan(): Invalid checksum\n");
				return B_BAD_DATA;
			}
			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);
}