haiku.git

/*
 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com
 * All rights reserved. Distributed under the terms of the MIT License.
 */


#include "BPlusTree.h"

#include "VerifyHeader.h"


TreeDirectory::TreeDirectory(Inode* inode)
	:
	fInode(inode),
	fInitStatus(B_OK),
	fRoot(NULL),
	fExtents(NULL),
	fCountOfFilledExtents(0),
	fSingleDirBlock(NULL),
	fOffsetOfSingleDirBlock(-1),
	fCurMapIndex(0),
	fOffset(0),
	fCurBlockNumber(0)
{
	fRoot = new(std::nothrow) BlockInDataFork;
	if (fRoot == NULL) {
		fInitStatus = B_NO_MEMORY;
		return;
	}

	fSingleDirBlock = new(std::nothrow) char[fInode->DirBlockSize()];
	if (fSingleDirBlock == NULL) {
		fInitStatus = B_NO_MEMORY;
		return;
	}

	memcpy((void*)fRoot,
		DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()), sizeof(BlockInDataFork));

	for (int i = 0; i < MAX_TREE_DEPTH; i++) {
		fPathForLeaves[i].blockData = NULL;
		fPathForData[i].blockData = NULL;
	}
}


TreeDirectory::~TreeDirectory()
{
	delete fRoot;
	delete[] fExtents;
	delete[] fSingleDirBlock;
}


status_t
TreeDirectory::InitCheck()
{
	return fInitStatus;
}


uint32
TreeDirectory::BlockLen()
{
	return fInode->SizeOfLongBlock();
}


size_t
TreeDirectory::KeySize()
{
	return XFS_KEY_SIZE;
}


size_t
TreeDirectory::PtrSize()
{
	return XFS_PTR_SIZE;
}


size_t
TreeDirectory::MaxRecordsPossibleRoot()
{
	size_t lengthOfDataFork = 0;
	if (fInode->ForkOffset() != 0)
		lengthOfDataFork = fInode->ForkOffset() << 3;
	if (fInode->ForkOffset() == 0) {
		lengthOfDataFork = fInode->GetVolume()->InodeSize()
			- fInode->CoreInodeSize();
	}

	lengthOfDataFork -= sizeof(BlockInDataFork);
	return lengthOfDataFork / (KeySize() + PtrSize());
}


size_t
TreeDirectory::GetPtrOffsetIntoRoot(int pos)
{
	size_t maxRecords = MaxRecordsPossibleRoot();
	return sizeof(BlockInDataFork) + maxRecords * KeySize()
		+ (pos - 1) * PtrSize();
}


size_t
TreeDirectory::MaxRecordsPossibleNode()
{
	size_t availableSpace = fInode->GetVolume()->BlockSize() - BlockLen();
	return availableSpace / (KeySize() + PtrSize());
}


size_t
TreeDirectory::GetPtrOffsetIntoNode(int pos)
{
	size_t maxRecords = MaxRecordsPossibleNode();
	return BlockLen() + maxRecords * KeySize() + (pos - 1) * PtrSize();
}


TreePointer*
TreeDirectory::GetPtrFromRoot(int pos)
{
	return (TreePointer*)
		((char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize())
			+ GetPtrOffsetIntoRoot(pos));
}


TreePointer*
TreeDirectory::GetPtrFromNode(int pos, void* buffer)
{
	size_t offsetIntoNode = GetPtrOffsetIntoNode(pos);
	return (TreePointer*)((char*)buffer + offsetIntoNode);
}


TreeKey*
TreeDirectory::GetKeyFromNode(int pos, void* buffer)
{
	return (TreeKey*)
		((char*)buffer + BlockLen() + (pos - 1) * KeySize());
}


TreeKey*
TreeDirectory::GetKeyFromRoot(int pos)
{
	off_t offset = (pos - 1) * KeySize();
	char* base = (char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize())
		+ sizeof(BlockInDataFork);
	return (TreeKey*) (base + offset);
}


status_t
TreeDirectory::SearchOffsetInTreeNode(uint32 offset,
	TreePointer** pointer, int pathIndex)
{
	// This is O(MaxRecords). Next is to implement this using upper bound
	// binary search and get O(log(MaxRecords))
	*pointer = NULL;
	TreeKey* offsetKey = NULL;
	size_t maxRecords = MaxRecordsPossibleNode();
	for (int i = maxRecords - 1; i >= 0; i--) {
		offsetKey
			= GetKeyFromNode(i + 1, (void*)fPathForLeaves[pathIndex].blockData);
		if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) {
			*pointer = GetPtrFromNode(i + 1, (void*)
				fPathForLeaves[pathIndex].blockData);

			break;
		}
	}

	if (offsetKey == NULL || *pointer == NULL)
		return B_BAD_VALUE;

	return B_OK;
}


status_t
TreeDirectory::SearchAndFillPath(uint32 offset, int type)
{
	TRACE("SearchAndFillPath:\n");
	PathNode* path;
	if (type == DATA)
		path = fPathForData;
	else if (type == LEAF)
		path = fPathForLeaves;
	else
		return B_BAD_VALUE;

	TreePointer* ptrToNode = NULL;
	TreeKey* offsetKey = NULL;
	// Go down the root of the tree first
	for (int i = fRoot->NumRecords() - 1; i >= 0; i--) {
		offsetKey = GetKeyFromRoot(i + 1);
		if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) {
			ptrToNode = GetPtrFromRoot(i + 1);
			break;
		}
	}
	if (ptrToNode == NULL || offsetKey == NULL) {
		//Corrupt tree
		return B_BAD_VALUE;
	}

	// We now have gone down the root and save path if not saved.
	int level = fRoot->Levels() - 1;
	Volume* volume = fInode->GetVolume();
	status_t status;
	for (int i = 0; i < MAX_TREE_DEPTH && level >= 0; i++, level--) {
		uint64 requiredBlock = B_BENDIAN_TO_HOST_INT64(*ptrToNode);
		TRACE("requiredBlock:(%" B_PRIu64 ")\n", requiredBlock);
		if (path[i].blockNumber == requiredBlock) {
			// This block already has what we need
			if (path[i].type == 2)
				break;
			status = SearchOffsetInTreeNode(offset, &ptrToNode, i);
			if (status != B_OK)
				return status;
			continue;
		}
		// We do not have the block we need
		ssize_t len;
		if (level == 0) {
			// The size of buffer should be the directory block size
			len = fInode->DirBlockSize();
			TRACE("path node type:(%" B_PRId32 ")\n", path[i].type);
			if (path[i].type != 2) {
				// Size is not directory block size.
				delete path[i].blockData;
				path[i].type = 0;
				path[i].blockData = new(std::nothrow) char[len];
				if (path[i].blockData == NULL)
					return B_NO_MEMORY;
				path[i].type = 2;
			}
			uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock);
			if (read_pos(volume->Device(), readPos, path[i].blockData, len)
				!= len) {
				ERROR("FillPath::FillBlockBuffer(): IO Error");
				return B_IO_ERROR;
			}
			path[i].blockNumber = requiredBlock;
			break;
		}
		// The size of buffer should be the block size
		len = volume->BlockSize();
		if (path[i].type != 1) {
			delete path[i].blockData;
			path[i].type = 0;
			path[i].blockData = new(std::nothrow) char[len];
			if (path[i].blockData == NULL)
				return B_NO_MEMORY;
			path[i].type = 1;
		}
		uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock);
		if (read_pos(volume->Device(), readPos, path[i].blockData, len)
			!= len) {
			ERROR("FillPath::FillBlockBuffer(): IO Error");
			return B_IO_ERROR;
		}
		path[i].blockNumber = requiredBlock;
		status = SearchOffsetInTreeNode(offset, &ptrToNode, i);
		if (status != B_OK)
			return status;
	}

	return B_OK;
}


status_t
TreeDirectory::GetAllExtents()
{
	xfs_extnum_t noOfExtents = fInode->DataExtentsCount();

	ExtentMapUnwrap* extentsWrapped
		= new(std::nothrow) ExtentMapUnwrap[noOfExtents];
	if (extentsWrapped == NULL)
		return B_NO_MEMORY;

	ArrayDeleter<ExtentMapUnwrap> extentsWrappedDeleter(extentsWrapped);

	Volume* volume = fInode->GetVolume();
	ssize_t len = volume->BlockSize();

	uint16 levelsInTree = fRoot->Levels();
	status_t status = fInode->GetNodefromTree(levelsInTree, volume, len,
		fInode->DirBlockSize(), fSingleDirBlock);
	if (status != B_OK)
		return status;

	// We should be at the left most leaf node.
	// This could be a multilevel node type directory
	uint64 fileSystemBlockNo;
	while (1) {
		// Run till you have leaf blocks to checkout
		char* leafBuffer = fSingleDirBlock;
		if (!VerifyHeader<LongBlock>((LongBlock*)leafBuffer, leafBuffer, fInode,
				0, NULL, XFS_BTREE)) {
			TRACE("Invalid Long Block");
			return B_BAD_VALUE;
		}

		uint32 offset = fInode->SizeOfLongBlock();
		int numRecs = ((LongBlock*)leafBuffer)->NumRecs();

		for (int i = 0; i < numRecs; i++) {
			extentsWrapped[fCountOfFilledExtents].first =
				*(uint64*)(leafBuffer + offset);
			extentsWrapped[fCountOfFilledExtents].second =
				*(uint64*)(leafBuffer + offset + sizeof(uint64));
			offset += sizeof(ExtentMapUnwrap);
			fCountOfFilledExtents++;
		}

		fileSystemBlockNo = ((LongBlock*)leafBuffer)->Right();
		TRACE("Next leaf is at: (%" B_PRIu64 ")\n", fileSystemBlockNo);
		if (fileSystemBlockNo == (uint64) -1)
			break;
		uint64 readPos = fInode->FileSystemBlockToAddr(fileSystemBlockNo);
		if (read_pos(volume->Device(), readPos, fSingleDirBlock, len)
				!= len) {
				ERROR("Extent::FillBlockBuffer(): IO Error");
				return B_IO_ERROR;
		}
	}
	TRACE("Total covered: (%" B_PRIu32 ")\n", fCountOfFilledExtents);

	status = UnWrapExtents(extentsWrapped);

	return status;
}


status_t
TreeDirectory::FillBuffer(char* blockBuffer, int howManyBlocksFurther,
	ExtentMapEntry* targetMap)
{
	TRACE("FILLBUFFER\n");
	ExtentMapEntry map;
	if (targetMap == NULL)
		map = fExtents[fCurMapIndex];
	if (targetMap != NULL)
		map = *targetMap;

	if (map.br_state != 0)
		return B_BAD_VALUE;

	ssize_t len = fInode->DirBlockSize();
	if (blockBuffer == NULL) {
		blockBuffer = new(std::nothrow) char[len];
		if (blockBuffer == NULL)
			return B_NO_MEMORY;
	}

	xfs_daddr_t readPos = fInode->FileSystemBlockToAddr(
		map.br_startblock + howManyBlocksFurther);

	if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len)
		!= len) {
		ERROR("TreeDirectory::FillBlockBuffer(): IO Error");
		return B_IO_ERROR;
	}

	if (targetMap == NULL) {
		fSingleDirBlock = blockBuffer;
		ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fSingleDirBlock);
		if (header == NULL)
			return B_NO_MEMORY;
		if (!VerifyHeader<ExtentDataHeader>(header, fSingleDirBlock, fInode,
				howManyBlocksFurther, &map, XFS_BTREE)) {
			ERROR("Invalid Data block");
			delete header;
			return B_BAD_VALUE;
		}
		delete header;
	}
	if (targetMap != NULL) {
		fSingleDirBlock = blockBuffer;
		/*
			This could be leaf or node block perform check for both
			based on magic number found.
		*/
		ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
		if (leaf == NULL)
			return B_NO_MEMORY;

		if ((leaf->Magic() == XFS_DIR2_LEAFN_MAGIC
				|| leaf->Magic() == XFS_DIR3_LEAFN_MAGIC)
			&& !VerifyHeader<ExtentLeafHeader>(leaf, fSingleDirBlock, fInode,
				howManyBlocksFurther, &map, XFS_BTREE)) {
			TRACE("Leaf block invalid");
			delete leaf;
			return B_BAD_VALUE;
		}
		delete leaf;
		leaf = NULL;

		NodeHeader* node = NodeHeader::Create(fInode, fSingleDirBlock);
		if (node == NULL)
			return B_NO_MEMORY;

		if ((node->Magic() == XFS_DA_NODE_MAGIC
				|| node->Magic() == XFS_DA3_NODE_MAGIC)
			&& !VerifyHeader<NodeHeader>(node, fSingleDirBlock, fInode,
				howManyBlocksFurther, &map, XFS_BTREE)) {
			TRACE("Node block invalid");
			delete node;
			return B_BAD_VALUE;
		}
		delete node;
	}
	return B_OK;
}


int
TreeDirectory::EntrySize(int len) const
{
	int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
		// uint16 is for the tag
	if (fInode->HasFileTypeField())
		entrySize += sizeof(uint8);

	return ROUNDUP(entrySize, 8);
		// rounding off to next greatest multiple of 8
}


/*
 * Throw in the desired block number and get the index of it
 */
status_t
TreeDirectory::SearchMapInAllExtent(uint64 blockNo, uint32& mapIndex)
{
	ExtentMapEntry map;
	for (uint32 i = 0; i < fCountOfFilledExtents; i++) {
		map = fExtents[i];
		if (map.br_startoff <= blockNo
			&& (blockNo <= map.br_startoff + map.br_blockcount - 1)) {
			// Map found
			mapIndex = i;
			return B_OK;
		}
	}

	return B_ENTRY_NOT_FOUND;
}


status_t
TreeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino)
{
	TRACE("TreeDirectory::GetNext\n");
	status_t status;
	if (fExtents == NULL) {
		status = GetAllExtents();
		if (status != B_OK)
			return status;
	}
	status = FillBuffer(fSingleDirBlock, 0);
	if (status != B_OK)
		return status;

	Volume* volume = fInode->GetVolume();

	void* entry; // This could be unused entry so we should check
	entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));

	uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
	if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) {
		entry = (void*)(fSingleDirBlock
			+ BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode));
		// This gets us a little faster to the next entry
	}

	uint32 curDirectorySize = fInode->Size();
	ExtentMapEntry& map = fExtents[fCurMapIndex];
	while (fOffset != curDirectorySize) {
		blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);

		TRACE("fOffset:(%" B_PRIu64 "), blockNoFromAddress:(%" B_PRIu32 ")\n",
			fOffset, blockNoFromAddress);
		if (fCurBlockNumber != blockNoFromAddress
			&& blockNoFromAddress > map.br_startoff
			&& blockNoFromAddress
				<= map.br_startoff + map.br_blockcount - 1) {
			// When the block is mapped in the same data
			// map entry but is not the first block
			status = FillBuffer(fSingleDirBlock,
				blockNoFromAddress - map.br_startoff);
			if (status != B_OK)
				return status;
			entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
			fOffset = fOffset + ExtentDataHeader::Size(fInode);
			fCurBlockNumber = blockNoFromAddress;
		} else if (fCurBlockNumber != blockNoFromAddress) {
			// When the block isn't mapped in the current data map entry
			uint32 curMapIndex;
			status = SearchMapInAllExtent(blockNoFromAddress, curMapIndex);
			if (status != B_OK)
				return status;
			fCurMapIndex = curMapIndex;
			map = fExtents[fCurMapIndex];
			status = FillBuffer(fSingleDirBlock,
				blockNoFromAddress - map.br_startoff);
			if (status != B_OK)
				return status;
			entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
			fOffset = fOffset + ExtentDataHeader::Size(fInode);
			fCurBlockNumber = blockNoFromAddress;
		}

		ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;

		if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
			TRACE("Unused entry found\n");
			fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
			entry = (void*)
				((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
			continue;
		}
		ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;

		uint16 currentOffset = (char*)dataEntry - fSingleDirBlock;
		TRACE("GetNext: fOffset:(%" B_PRIu64 "), currentOffset:(%" B_PRIu16 ")\n",
			BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset);

		if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) {
			entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
			continue;
		}

		if ((size_t)(dataEntry->namelen) >= *length)
			return B_BUFFER_OVERFLOW;

		fOffset = fOffset + EntrySize(dataEntry->namelen);
		memcpy(name, dataEntry->name, dataEntry->namelen);
		name[dataEntry->namelen] = '\0';
		*length = dataEntry->namelen + 1;
		*ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);

		TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "), ino: (%" B_PRIu64 ")\n", name,
			*length, *ino);
		return B_OK;
	}

	return B_ENTRY_NOT_FOUND;
}


status_t
TreeDirectory::UnWrapExtents(ExtentMapUnwrap* extentsWrapped)
{
	fExtents = new(std::nothrow) ExtentMapEntry[fCountOfFilledExtents];
	if (fExtents == NULL)
		return B_NO_MEMORY;
	uint64 first, second;

	for (uint32 i = 0; i < fCountOfFilledExtents; i++) {
		first = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].first);
		second = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].second);
		fExtents[i].br_state = first >> 63;
		fExtents[i].br_startoff = (first & MASK(63)) >> 9;
		fExtents[i].br_startblock = ((first & MASK(9)) << 43) | (second >> 21);
		fExtents[i].br_blockcount = second & MASK(21);
	}

	return B_OK;
}


void
TreeDirectory::FillMapEntry(int num, ExtentMapEntry** fMap,
	int type, int pathIndex)
{
	void* pointerToMap;
	if (type == DATA) {
		char* base = fPathForData[pathIndex].blockData + BlockLen();
		off_t offset = num * EXTENT_SIZE;
		pointerToMap = (void*)(base + offset);
	} else {
		char* base = fPathForLeaves[pathIndex].blockData + BlockLen();
		off_t offset = num * EXTENT_SIZE;
		pointerToMap = (void*)(base + offset);
	}
	uint64 firstHalf = *((uint64*)pointerToMap);
	uint64 secondHalf = *((uint64*)pointerToMap + 1);
		//dividing the 128 bits into 2 parts.

	firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
	secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
	(*fMap)->br_state = firstHalf >> 63;
	(*fMap)->br_startoff = (firstHalf & MASK(63)) >> 9;
	(*fMap)->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
	(*fMap)->br_blockcount = secondHalf & MASK(21);
	TRACE("FillMapEntry: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
		"blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", (*fMap)->br_startoff,
		(*fMap)->br_startblock,(*fMap)->br_blockcount, (*fMap)->br_state);
}


void
TreeDirectory::SearchForMapInDirectoryBlock(uint64 blockNo,
	int entries, ExtentMapEntry** map, int type, int pathIndex)
{
	TRACE("SearchForMapInDirectoryBlock: blockNo:(%" B_PRIu64 ")\n", blockNo);
	for (int i = 0; i < entries; i++) {
		FillMapEntry(i, map, type, pathIndex);
		if ((*map)->br_startoff <= blockNo
			&& (blockNo <= (*map)->br_startoff + (*map)->br_blockcount - 1)) {
			// Map found
			return;
		}
	}
	// Map wasn't found. Some kind of corruption. This is checked by caller.
	*map = NULL;
}


uint32
TreeDirectory::SearchForHashInNodeBlock(uint32 hashVal)
{
	NodeHeader* header = NodeHeader::Create(fInode, fSingleDirBlock);
	if (header == NULL)
		return B_NO_MEMORY;
	NodeEntry* entry = (NodeEntry*)(fSingleDirBlock + NodeHeader::Size(fInode));
	int count = header->Count();
	delete header;

	for (int i = 0; i < count; i++) {
		if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval))
			return B_BENDIAN_TO_HOST_INT32(entry[i].before);
	}
	return 0;
}


status_t
TreeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino)
{
	TRACE("TreeDirectory: Lookup\n");
	TRACE("Name: %s\n", name);
	uint32 hashValueOfRequest = hashfunction(name, length);
	TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);

	Volume* volume = fInode->GetVolume();
	status_t status;

	ExtentMapEntry* targetMap = new(std::nothrow) ExtentMapEntry;
	if (targetMap == NULL)
		return B_NO_MEMORY;
	int pathIndex = -1;
	uint32 rightOffset = LEAF_STARTOFFSET(volume->BlockLog());

	// In node directories, the "node blocks" had a single level
	// Here we could have multiple levels. With each iteration of
	// the loop we go a level lower.
	while (rightOffset != fOffsetOfSingleDirBlock && 1) {
		status = SearchAndFillPath(rightOffset, LEAF);
		if (status != B_OK)
			return status;

		// The path should now have the Tree Leaf at appropriate level
		// Find the directory block in the path
		for (int i = 0; i < MAX_TREE_DEPTH; i++) {
			if (fPathForLeaves[i].type == 2) {
				pathIndex = i;
				break;
			}
		}
		if (pathIndex == -1) {
			// corrupt tree
			return B_BAD_VALUE;
		}

		// Get the node block from directory block
		// If level is non-zero, reiterate with new "rightOffset"
		// Else, we are at leaf block, then break
		LongBlock* curDirBlock
			= (LongBlock*)fPathForLeaves[pathIndex].blockData;

		if (!VerifyHeader<LongBlock>(curDirBlock, fPathForLeaves[pathIndex].blockData, fInode,
				0, NULL, XFS_BTREE)) {
			TRACE("Invalid Long Block");
			return B_BAD_VALUE;
		}

		SearchForMapInDirectoryBlock(rightOffset, curDirBlock->NumRecs(),
			&targetMap, LEAF, pathIndex);
		if (targetMap == NULL)
			return B_BAD_VALUE;

		FillBuffer(fSingleDirBlock, rightOffset - targetMap->br_startoff,
			targetMap);
		fOffsetOfSingleDirBlock = rightOffset;
		ExtentLeafHeader* dirBlock = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
		if (dirBlock == NULL)
			return B_NO_MEMORY;
		if (dirBlock->Magic() == XFS_DIR2_LEAFN_MAGIC
			|| dirBlock->Magic() == XFS_DIR3_LEAFN_MAGIC) {
			// Got the potential leaf. Break.
			delete dirBlock;
			break;
		}
		if (dirBlock->Magic() == XFS_DA_NODE_MAGIC
			|| dirBlock->Magic() == XFS_DA3_NODE_MAGIC) {
			rightOffset = SearchForHashInNodeBlock(hashValueOfRequest);
			if (rightOffset == 0)
				return B_ENTRY_NOT_FOUND;
			delete dirBlock;
			continue;
		}
	}
	// We now have the leaf block that might contain the entry we need.
	// Else go to the right subling if it might contain it. Else break.
	while (1) {
		ExtentLeafHeader* leafHeader
			= ExtentLeafHeader::Create(fInode, fSingleDirBlock);
		if (leafHeader == NULL)
			return B_NO_MEMORY;
		ExtentLeafEntry* leafEntry
			= (ExtentLeafEntry*)(fSingleDirBlock + ExtentLeafHeader::Size(fInode));

		int numberOfLeafEntries = leafHeader->Count();
		TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries);
		int left = 0;
		int right = numberOfLeafEntries - 1;

		hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest);

		uint32 nextLeaf = leafHeader->Forw();
		uint32 lastHashVal = B_BENDIAN_TO_HOST_INT32(
			leafEntry[numberOfLeafEntries - 1].hashval);

		while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
				== hashValueOfRequest) {
			uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
			if (address == 0) {
				left++;
				continue;
			}

			uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume);
			uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode);

			TRACE("BlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset);

			status = SearchAndFillPath(dataBlockNumber, DATA);
			int pathIndex = -1;
			for (int i = 0; i < MAX_TREE_DEPTH; i++) {
				if (fPathForData[i].type == 2) {
					pathIndex = i;
					break;
				}
			}
			if (pathIndex == -1)
				return B_BAD_VALUE;

			LongBlock* curDirBlock
				= (LongBlock*)fPathForData[pathIndex].blockData;

			SearchForMapInDirectoryBlock(dataBlockNumber,
				curDirBlock->NumRecs(), &targetMap, DATA, pathIndex);
			if (targetMap == NULL)
				return B_BAD_VALUE;

			FillBuffer(fSingleDirBlock,
				dataBlockNumber - targetMap->br_startoff, targetMap);
			fOffsetOfSingleDirBlock = dataBlockNumber;

			TRACE("offset:(%" B_PRIu32 ")\n", offset);
			ExtentDataEntry* entry
				= (ExtentDataEntry*)(fSingleDirBlock + offset);

			int retVal = strncmp(name, (char*)entry->name, entry->namelen);
			if (retVal == 0) {
				*ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
				TRACE("ino:(%" B_PRIu64 ")\n", *ino);
				return B_OK;
			}
			left++;
		}
		if (lastHashVal == hashValueOfRequest && nextLeaf != (uint32) -1) {
			// Go to forward neighbor. We might find an entry there.
			status = SearchAndFillPath(nextLeaf, LEAF);
			if (status != B_OK)
				return status;

			pathIndex = -1;
			for (int i = 0; i < MAX_TREE_DEPTH; i++) {
				if (fPathForLeaves[i].type == 2) {
					pathIndex = i;
					break;
				}
			}
			if (pathIndex == -1)
				return B_BAD_VALUE;

			LongBlock* curDirBlock
				= (LongBlock*)fPathForLeaves[pathIndex].blockData;

			SearchForMapInDirectoryBlock(nextLeaf, curDirBlock->NumRecs(),
				&targetMap, LEAF, pathIndex);
			if (targetMap == NULL)
				return B_BAD_VALUE;

			FillBuffer(fSingleDirBlock,
				nextLeaf - targetMap->br_startoff, targetMap);
			fOffsetOfSingleDirBlock = nextLeaf;

			continue;
		} else {
			break;
		}
		delete leafHeader;
	}
	return B_ENTRY_NOT_FOUND;
}


uint32
LongBlock::ExpectedMagic(int8 WhichDirectory, Inode* inode)
{
	if(inode->Version() == 3)
		return XFS_BMAP_CRC_MAGIC;
	else
		return XFS_BMAP_MAGIC;
}


uint32
LongBlock::CRCOffset()
{
	return offsetof(LongBlock, bb_crc);
}