// Volume.cpp
//
// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// You can alternatively use *this file* under the terms of the the MIT
// license included in this package.
 
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
 
#include "Volume.h"
#include "Block.h"
#include "BlockCache.h"
#include "Debug.h"
#include "DirItem.h"
#include "IndirectItem.h"
#include "Iterators.h"
#include "reiserfs.h"
#include "Settings.h"
#include "StatItem.h"
#include "SuperBlock.h"
#include "Tree.h"
#include "VNode.h"
 
 
extern fs_vnode_ops gReiserFSVnodeOps;
 
 
// min and max
// We don't want to include <algobase.h> otherwise we also get <iostream.h>
// and other undesired things.
template<typename C>
static inline C min(const C &a, const C &b) { return (a < b ? a : b); }
template<typename C>
static inline C max(const C &a, const C &b) { return (a > b ? a : b); }
 
/*!
	\class Volume
	\brief Represents a volume.
 
	The Volume class bundles all functionality related to a volume.
	It knows the superblock and has some basic functionality needed
	for handling VNodes. Actually it should be the layer that provides the
	abstraction from VNodes. The design is not strict in this respect
	(the whole thing evolved while I was in the process of understanding
	the structures ;-), since the kernel interface does a good part of that
	too (e.g. concerning dir iteration).
*/
 
// constructor
Volume::Volume()
	: fFSVolume(NULL),
	  fDevice(-1),
	  fBlockCache(NULL),
	  fTree(NULL),
	  fSuperBlock(NULL),
	  fHashFunction(NULL),
	  fRootVNode(NULL),
	  fDeviceName(NULL),
	  fSettings(NULL),
	  fNegativeEntries()
{
	fVolumeName[0] = '\0';
}
 
// destructor
Volume::~Volume()
{
	Unmount();
}
 
 
// Identify
status_t
Volume::Identify(int fd, partition_data *partition)
{
	// open disk
	fDevice = dup(fd);
	if (fDevice < 0)
		return B_ERROR;
 
	// read and analyze superblock
	return _ReadSuperBlock();
}
 
// Mount
status_t
Volume::Mount(fs_volume *fsVolume, const char *path)
{
	Unmount();
	status_t error = (path ? B_OK : B_BAD_VALUE);
	fFSVolume = fsVolume;
	// load the settings
	if (error == B_OK) {
		fSettings = new(nothrow) Settings;
		if (fSettings)
			error = fSettings->SetTo(path);
		else
			error = B_NO_MEMORY;
	}
	// copy the device name
	if (error == B_OK) {
		fDeviceName = new(nothrow) char[strlen(path) + 1];
		if (fDeviceName)
			strcpy(fDeviceName, path);
		else
			error = B_NO_MEMORY;
	}
	// open disk
	if (error == B_OK) {
		fDevice = open(path, O_RDONLY);
		if (fDevice < 0)
			SET_ERROR(error, errno);
	}
	// read and analyze superblock
	if (error == B_OK)
		error = _ReadSuperBlock();
 
	if (error == B_OK)
		UpdateName(fsVolume->partition);
 
	// create and init block cache
	if (error == B_OK) {
		fBlockCache = new(nothrow) BlockCache;
		if (fBlockCache)
			error = fBlockCache->Init(fDevice, CountBlocks(), GetBlockSize());
		else
			error = B_NO_MEMORY;
	}
	// create the tree
	if (error == B_OK) {
		fTree = new(nothrow) Tree;
		if (!fTree)
			error = B_NO_MEMORY;
	}
	// get the root node and init the tree
	if (error == B_OK) {
		Block *rootBlock = NULL;
		error = fBlockCache->GetBlock(fSuperBlock->GetRootBlock(), &rootBlock);
REPORT_ERROR(error);
		if (error == B_OK) {
			rootBlock->SetKind(Block::KIND_FORMATTED);
			error = fTree->Init(this, rootBlock->ToNode(),
								fSuperBlock->GetTreeHeight());
REPORT_ERROR(error);
			rootBlock->Put();
		}
	}
	// get the root VNode (i.e. the root dir)
	if (error == B_OK) {
		fRootVNode = new(nothrow) VNode;
		if (fRootVNode) {
			error = FindVNode(REISERFS_ROOT_PARENT_OBJECTID,
							  REISERFS_ROOT_OBJECTID, fRootVNode);
REPORT_ERROR(error);
			if (error == B_OK) {
				error = publish_vnode(fFSVolume, fRootVNode->GetID(),
					fRootVNode, &gReiserFSVnodeOps, S_IFDIR, 0);
			}
REPORT_ERROR(error);
		} else
			error = B_NO_MEMORY;
	}
	// init the hash function
	if (error == B_OK)
		_InitHashFunction();
	// init the negative entry list
	if (error == B_OK)
		_InitNegativeEntries();
	// cleanup on error
	if (error != B_OK)
		Unmount();
	RETURN_ERROR(error);
}
 
// Unmount
status_t
Volume::Unmount()
{
	if (fRootVNode) {
		delete fRootVNode;
		fRootVNode = NULL;
	}
	if (fTree) {
		delete fTree;
		fTree = NULL;
	}
	if (fSuperBlock) {
		delete fSuperBlock;
		fSuperBlock = NULL;
	}
	if (fBlockCache) {
		delete fBlockCache;
		fBlockCache = NULL;
	}
	if (fDeviceName) {
		delete[] fDeviceName;
		fDeviceName = NULL;
	}
	if (fDevice >= 0) {
		close(fDevice);
		fDevice = -1;
	}
	if (fSettings) {
		delete fSettings;
		fSettings = NULL;
	}
	fNegativeEntries.MakeEmpty();
	fHashFunction = NULL;
	fFSVolume = NULL;
	return B_OK;
}
 
// GetBlockSize
off_t
Volume::GetBlockSize() const
{
	return fSuperBlock->GetBlockSize();
}
 
// CountBlocks
off_t
Volume::CountBlocks() const
{
	return fSuperBlock->CountBlocks();
}
 
// CountFreeBlocks
off_t
Volume::CountFreeBlocks() const
{
	return fSuperBlock->CountFreeBlocks();
}
 
// GetName
const char *
Volume::GetName() const
{
	return fVolumeName;
}
 
 
// UpdateName
void
Volume::UpdateName(partition_id partitionID)
{
	if (fSuperBlock->GetLabel(fVolumeName, sizeof(fVolumeName)) == B_OK)
		return;
	if (get_default_partition_content_name(partitionID, "ReiserFS",
			fVolumeName, sizeof(fVolumeName)) == B_OK)
		return;
	strlcpy(fVolumeName, "ReiserFS Volume", sizeof(fVolumeName));
}
 
 
// GetDeviceName
const char *
Volume::GetDeviceName() const
{
	return fDeviceName;
}
 
// GetKeyOffsetForName
status_t
Volume::GetKeyOffsetForName(const char *name, int len, uint64 *result)
{
	status_t error = (name && result ? B_OK : B_BAD_VALUE);
	if (error == B_OK) {
		if (fHashFunction)
			*result = key_offset_for_name(fHashFunction, name, len);
		else
			error = B_ERROR;
	}
	return error;
}
 
// GetVNode
status_t
Volume::GetVNode(ino_t id, VNode **node)
{
	return get_vnode(GetFSVolume(), id, (void**)node);
}
 
// PutVNode
status_t
Volume::PutVNode(ino_t id)
{
	return put_vnode(GetFSVolume(), id);
}
 
// FindVNode
/*!	\brief Finds the node identified by a ino_t.
 
	\note The method does not initialize the parent ID for non-directory nodes.
 
	\param id ID of the node to be found.
	\param node pointer to a pre-allocated VNode to be initialized to
		   the found node.
	\return \c B_OK, if everything went fine.
*/
status_t
Volume::FindVNode(ino_t id, VNode *node)
{
	return FindVNode(VNode::GetDirIDFor(id), VNode::GetObjectIDFor(id), node);
}
 
// FindVNode
/*!	\brief Finds the node identified by a directory ID, object ID pair.
 
	\note The method does not initialize the parent ID for non-directory nodes.
 
	\param dirID Directory ID of the node to be found.
	\param objectID Object ID of the node to be found.
	\param node pointer to a pre-allocated VNode to be initialized to
		   the found node.
	\return \c B_OK, if everything went fine.
*/
status_t
Volume::FindVNode(uint32 dirID, uint32 objectID, VNode *node)
{
	// NOTE: The node's parent dir ID is not initialized!
	status_t error = (node ? B_OK : B_BAD_VALUE);
	// init the node
	if (error == B_OK)
		error = node->SetTo(dirID, objectID);
	// find the stat item
	StatItem item;
	if (error == B_OK) {
		error = fTree->FindStatItem(dirID, objectID, &item);
		if (error != B_OK) {
			FATAL(("Couldn't find stat item for node (%lu, %lu)\n",
				   dirID, objectID));
		}
	}
	// get the stat data
	if (error == B_OK)
		SET_ERROR(error, item.GetStatData(node->GetStatData(), true));
	// for dirs get the ".." entry, since we need the parent dir ID
	if (error == B_OK && node->IsDir()) {
		DirItem dirItem;
		int32 index = 0;
		error = fTree->FindDirEntry(dirID, objectID, "..", &dirItem, &index);
		if (error == B_OK) {
			DirEntry *entry = dirItem.EntryAt(index);
			node->SetParentID(entry->GetDirID(), entry->GetObjectID());
		}
		else {
			FATAL(("failed to find `..' entry for dir node (%lu, %ld)\n",
				   dirID, objectID));
		}
	}
	return error;
}
 
// FindDirEntry
/*!	\brief Searches an entry in a directory.
 
	\note Must not be called with \a entryName "." or ".."!
 
	\param dir The directory.
	\param entryName Name of the entry.
	\param foundNode pointer to a pre-allocated VNode to be initialized to
		   the found entry.
	\param failIfHidden The method shall fail, if the entry is hidden.
	\return \c B_OK, if everything went fine.
*/
status_t
Volume::FindDirEntry(VNode *dir, const char *entryName, VNode *foundNode,
					 bool failIfHidden)
{
	status_t error = (dir && foundNode ? B_OK : B_BAD_VALUE);
	// find the DirEntry
	DirItem item;
	int32 entryIndex = 0;
	if (error == B_OK) {
		error = fTree->FindDirEntry(dir->GetDirID(), dir->GetObjectID(),
									entryName, &item, &entryIndex);
	}
	// find the child node
	if (error == B_OK) {
		DirEntry *entry = item.EntryAt(entryIndex);
		error = FindVNode(entry->GetDirID(), entry->GetObjectID(), foundNode);
		if (error == B_OK && failIfHidden && entry->IsHidden())
			error = B_ENTRY_NOT_FOUND;
	}
	return error;
}
 
// ReadObject
/*!	\brief Reads data from an object.
 
	For subsequent reads better use a StreamReader.
 
	\param node The object to be read from.
	\param offset The file offset at which to start with reading.
	\param buffer The buffer into which the data shall be written.
	\param bufferSize The number of bytes to be read.
	\param bytesRead Pointer to a size_t to be set to the number of bytes
		   actually read.
	\return \c B_OK, if everything went fine.
*/
status_t
Volume::ReadObject(VNode *node, off_t offset, void *buffer, size_t bufferSize,
				   size_t *bytesRead)
{
	status_t error = (node && buffer && bytesRead && offset >= 0
					  ? B_OK : B_BAD_VALUE);
	// read files or symlinks only
	if (error == B_OK && !(node->IsFile() || node->IsSymlink()))
		error = B_BAD_VALUE;
	// let a StreamReader do the actual work
	if (error == B_OK) {
		StreamReader reader(fTree, node->GetDirID(), node->GetObjectID());
		error = reader.InitCheck();
		if (error == B_OK)
			error = reader.ReadAt(offset, buffer, bufferSize, bytesRead);
	}
	return error;
}
 
// ReadLink
/*!	\brief Reads a symlink.
 
	\note It is not check whether the object is a symlink or not! The caller
		  is responsible for that.
 
	\param node The symlink to be read from.
	\param buffer The buffer into which the data shall be written.
	\param bufferSize The number of bytes to be read.
	\param bytesRead Pointer to a size_t to be set to the number of bytes
		   actually read.
	\return \c B_OK, if everything went fine.
*/
status_t
Volume::ReadLink(VNode *node, char *buffer, size_t bufferSize,
				 size_t *bytesRead)
{
	return ReadObject(node, 0, buffer, bufferSize, bytesRead);
}
 
// FindEntry
status_t
Volume::FindEntry(const VNode *rootDir, const char *path, VNode *foundNode)
{
// Note: does not resolve links.
PRINT(("Volume::FindEntry(`%s')\n", path));
	status_t error = (rootDir && path && foundNode ? B_OK : B_BAD_VALUE);
	if (error == B_OK && (path[0] == '\0' || path[0] == '/'))
		error = B_ENTRY_NOT_FOUND;
	// start at the given root dir
	if (error == B_OK)
		*foundNode = *rootDir;
	// resolve until we hit the end of the string
	while (error == B_OK && path[0] != '\0') {
PRINT(("  remaining path: `%s'\n", path));
		int32 len = strlen(path);
		// find the first `/'
		const char *componentNameEnd = strchr(path, '/');
		if (!componentNameEnd)
			componentNameEnd = path + len;
		// get the name of the first component
		int32 componentLen = componentNameEnd - path;
		if (componentLen >= B_FILE_NAME_LENGTH)
			return B_NAME_TOO_LONG;
		char component[B_FILE_NAME_LENGTH];
		strncpy(component, path, componentLen);
		component[componentLen] = '\0';
		// get the component
PRINT(("  looking for dir entry: `%s'\n", component));
		error = FindDirEntry(foundNode, component, foundNode);
		// skip trailing `/'s
		if (error == B_OK) {
			path = componentNameEnd;
			while (*path == '/')
				path++;
		}
	}
PRINT(("Volume::FindEntry(`%s') done: %s\n", path, strerror(error)));
	return error;
}
 
// IsNegativeEntry
bool
Volume::IsNegativeEntry(ino_t id)
{
	for (int32 i = fNegativeEntries.CountItems() - 1; i >= 0; i--) {
		if (fNegativeEntries.ItemAt(i) == id)
			return true;
	}
	return false;
}
 
// IsNegativeEntry
bool
Volume::IsNegativeEntry(uint32 dirID, uint32 objectID)
{
	return IsNegativeEntry(VNode::GetIDFor(dirID, objectID));
}
 
// GetHideEsoteric
bool
Volume::GetHideEsoteric() const
{
	return fSettings->GetHideEsoteric();
}
 
// _ReadSuperBlock
status_t
Volume::_ReadSuperBlock()
{
	status_t error = B_OK;
	fSuperBlock = new(nothrow) SuperBlock;
	if (fSuperBlock)
		error = fSuperBlock->Init(fDevice);
	else
		error = B_NO_MEMORY;
	// check FS state
	if (error == B_OK && fSuperBlock->GetState() != REISERFS_VALID_FS) {
		FATAL(("The superblock indicates a non-valid FS! Bailing out."));
		error = B_ERROR;
	}
	// check FS version
	if (error == B_OK && fSuperBlock->GetVersion() > REISERFS_VERSION_2) {
		FATAL(("The superblock indicates a version greater than 2 (%u)! "
			   "Bailing out.", fSuperBlock->GetVersion()));
		error = B_ERROR;
	}
	RETURN_ERROR(error);
}
 
// hash_function_for_code
static
hash_function_t
hash_function_for_code(uint32 code)
{
	hash_function_t function = NULL;
	// find the hash function
	switch (code) {
		case TEA_HASH:
			function = keyed_hash;
			break;
		case YURA_HASH:
			function = yura_hash;
			break;
		case R5_HASH:
			function = r5_hash;
			break;
		case UNSET_HASH:
		default:
			break;
	}
	return function;
}
 
// _InitHashFunction
void
Volume::_InitHashFunction()
{
	// get the hash function
	fHashFunction = hash_function_for_code(fSuperBlock->GetHashFunctionCode());
	// try to detect it, if it is not set or is not the right one
	if (!fHashFunction || !_VerifyHashFunction(fHashFunction)) {
		INFORM(("No or wrong directory hash function. Try to detect...\n"));
		uint32 code = _DetectHashFunction();
		fHashFunction = hash_function_for_code(code);
		// verify it
		if (fHashFunction) {
			if (_VerifyHashFunction(fHashFunction)) {
				INFORM(("Directory hash function successfully detected: %lu\n",
						code));
			} else {
				fHashFunction = NULL;
				INFORM(("Detected directory hash function is not the right "
						"one.\n"));
			}
		} else
			INFORM(("Failed to detect the directory hash function.\n"));
	}
}
 
// _DetectHashFunction
uint32
Volume::_DetectHashFunction()
{
	// iterate over the entries in the root dir until we find an entry, that
	// let us draw an unambiguous conclusion
	DirEntryIterator iterator(fTree, fRootVNode->GetDirID(),
							  fRootVNode->GetObjectID(), DOT_DOT_OFFSET + 1);
	uint32 foundCode = UNSET_HASH;
	DirItem item;
	int32 index = 0;
	while (foundCode == UNSET_HASH
		   && iterator.GetNext(&item, &index) == B_OK) {
		DirEntry *entry = item.EntryAt(index);
		uint64 offset = entry->GetOffset();
		uint32 hashCodes[] = { TEA_HASH, YURA_HASH, R5_HASH };
		int32 hashCodeCount = sizeof(hashCodes) / sizeof(uint32);
		size_t nameLen = 0;
		const char *name = item.EntryNameAt(index, &nameLen);
		if (!name)	// bad data!
			continue;
		// try each hash function -- if there's a single winner, we're done,
		// otherwise the next entry must help
		for (int32 i = 0; i < hashCodeCount; i++) {
			hash_function_t function = hash_function_for_code(hashCodes[i]);
			uint64 testOffset = key_offset_for_name(function, name, nameLen);
			if (offset_hash_value(offset) == offset_hash_value(testOffset)) {
				if (foundCode != UNSET_HASH) {
					// ambiguous
					foundCode = UNSET_HASH;
					break;
				} else
					foundCode = hashCodes[i];
			}
		}
	}
	return foundCode;
}
 
// _VerifyHashFunction
bool
Volume::_VerifyHashFunction(hash_function_t function)
{
	bool result = true;
	// iterate over the entries in the root dir until we find an entry, that
	// doesn't falsify the hash function
	DirEntryIterator iterator(fTree, fRootVNode->GetDirID(),
							  fRootVNode->GetObjectID(), DOT_DOT_OFFSET + 1);
	DirItem item;
	int32 index = 0;
	while (iterator.GetNext(&item, &index) == B_OK) {
		DirEntry *entry = item.EntryAt(index);
		uint64 offset = entry->GetOffset();
		// try the hash function
		size_t nameLen = 0;
		if (const char *name = item.EntryNameAt(index, &nameLen)) {
			uint64 testOffset = key_offset_for_name(function, name, nameLen);
			if (offset_hash_value(offset) != offset_hash_value(testOffset)) {
				result = false;
				break;
			}
		} // else: bad data
	}
	return result;
}
 
// _InitNegativeEntries
void
Volume::_InitNegativeEntries()
{
	// build a list of vnode IDs
	for (int32 i = 0; const char *entry = fSettings->HiddenEntryAt(i); i++) {
		if (entry && strlen(entry) > 0 && entry[0] != '/') {
			VNode node;
			if (FindEntry(fRootVNode, entry, &node) == B_OK
				&& node.GetID() != fRootVNode->GetID()) {
				fNegativeEntries.AddItem(node.GetID());
			} else
				INFORM(("WARNING: negative entry not found: `%s'\n", entry));
		}
	}
}