1/*
2 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com
3 * All rights reserved. Distributed under the terms of the MIT License.
4 */
5
6
7#include "BPlusTree.h"
8
9#include "VerifyHeader.h"
10
11
12TreeDirectory::TreeDirectory(Inode* inode)
13	:
14	fInode(inode),
15	fInitStatus(B_OK),
16	fRoot(NULL),
17	fExtents(NULL),
18	fCountOfFilledExtents(0),
19	fSingleDirBlock(NULL),
20	fOffsetOfSingleDirBlock(-1),
21	fCurMapIndex(0),
22	fOffset(0),
23	fCurBlockNumber(0)
24{
25	fRoot = new(std::nothrow) BlockInDataFork;
26	if (fRoot == NULL) {
27		fInitStatus = B_NO_MEMORY;
28		return;
29	}
30
31	fSingleDirBlock = new(std::nothrow) char[fInode->DirBlockSize()];
32	if (fSingleDirBlock == NULL) {
33		fInitStatus = B_NO_MEMORY;
34		return;
35	}
36
37	memcpy((void*)fRoot,
38		DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()), sizeof(BlockInDataFork));
39
40	for (int i = 0; i < MAX_TREE_DEPTH; i++) {
41		fPathForLeaves[i].blockData = NULL;
42		fPathForData[i].blockData = NULL;
43	}
44}
45
46
47TreeDirectory::~TreeDirectory()
48{
49	delete fRoot;
50	delete[] fExtents;
51	delete[] fSingleDirBlock;
52}
53
54
55status_t
56TreeDirectory::InitCheck()
57{
58	return fInitStatus;
59}
60
61
62uint32
63TreeDirectory::BlockLen()
64{
65	return fInode->SizeOfLongBlock();
66}
67
68
69size_t
70TreeDirectory::KeySize()
71{
72	return XFS_KEY_SIZE;
73}
74
75
76size_t
77TreeDirectory::PtrSize()
78{
79	return XFS_PTR_SIZE;
80}
81
82
83size_t
84TreeDirectory::MaxRecordsPossibleRoot()
85{
86	size_t lengthOfDataFork = 0;
87	if (fInode->ForkOffset() != 0)
88		lengthOfDataFork = fInode->ForkOffset() << 3;
89	if (fInode->ForkOffset() == 0) {
90		lengthOfDataFork = fInode->GetVolume()->InodeSize()
91			- fInode->CoreInodeSize();
92	}
93
94	lengthOfDataFork -= sizeof(BlockInDataFork);
95	return lengthOfDataFork / (KeySize() + PtrSize());
96}
97
98
99size_t
100TreeDirectory::GetPtrOffsetIntoRoot(int pos)
101{
102	size_t maxRecords = MaxRecordsPossibleRoot();
103	return sizeof(BlockInDataFork) + maxRecords * KeySize()
104		+ (pos - 1) * PtrSize();
105}
106
107
108size_t
109TreeDirectory::MaxRecordsPossibleNode()
110{
111	size_t availableSpace = fInode->GetVolume()->BlockSize() - BlockLen();
112	return availableSpace / (KeySize() + PtrSize());
113}
114
115
116size_t
117TreeDirectory::GetPtrOffsetIntoNode(int pos)
118{
119	size_t maxRecords = MaxRecordsPossibleNode();
120	return BlockLen() + maxRecords * KeySize() + (pos - 1) * PtrSize();
121}
122
123
124TreePointer*
125TreeDirectory::GetPtrFromRoot(int pos)
126{
127	return (TreePointer*)
128		((char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize())
129			+ GetPtrOffsetIntoRoot(pos));
130}
131
132
133TreePointer*
134TreeDirectory::GetPtrFromNode(int pos, void* buffer)
135{
136	size_t offsetIntoNode = GetPtrOffsetIntoNode(pos);
137	return (TreePointer*)((char*)buffer + offsetIntoNode);
138}
139
140
141TreeKey*
142TreeDirectory::GetKeyFromNode(int pos, void* buffer)
143{
144	return (TreeKey*)
145		((char*)buffer + BlockLen() + (pos - 1) * KeySize());
146}
147
148
149TreeKey*
150TreeDirectory::GetKeyFromRoot(int pos)
151{
152	off_t offset = (pos - 1) * KeySize();
153	char* base = (char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize())
154		+ sizeof(BlockInDataFork);
155	return (TreeKey*) (base + offset);
156}
157
158
159status_t
160TreeDirectory::SearchOffsetInTreeNode(uint32 offset,
161	TreePointer** pointer, int pathIndex)
162{
163	// This is O(MaxRecords). Next is to implement this using upper bound
164	// binary search and get O(log(MaxRecords))
165	*pointer = NULL;
166	TreeKey* offsetKey = NULL;
167	size_t maxRecords = MaxRecordsPossibleNode();
168	for (int i = maxRecords - 1; i >= 0; i--) {
169		offsetKey
170			= GetKeyFromNode(i + 1, (void*)fPathForLeaves[pathIndex].blockData);
171		if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) {
172			*pointer = GetPtrFromNode(i + 1, (void*)
173				fPathForLeaves[pathIndex].blockData);
174
175			break;
176		}
177	}
178
179	if (offsetKey == NULL || *pointer == NULL)
180		return B_BAD_VALUE;
181
182	return B_OK;
183}
184
185
186status_t
187TreeDirectory::SearchAndFillPath(uint32 offset, int type)
188{
189	TRACE("SearchAndFillPath:\n");
190	PathNode* path;
191	if (type == DATA)
192		path = fPathForData;
193	else if (type == LEAF)
194		path = fPathForLeaves;
195	else
196		return B_BAD_VALUE;
197
198	TreePointer* ptrToNode = NULL;
199	TreeKey* offsetKey = NULL;
200	// Go down the root of the tree first
201	for (int i = fRoot->NumRecords() - 1; i >= 0; i--) {
202		offsetKey = GetKeyFromRoot(i + 1);
203		if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) {
204			ptrToNode = GetPtrFromRoot(i + 1);
205			break;
206		}
207	}
208	if (ptrToNode == NULL || offsetKey == NULL) {
209		//Corrupt tree
210		return B_BAD_VALUE;
211	}
212
213	// We now have gone down the root and save path if not saved.
214	int level = fRoot->Levels() - 1;
215	Volume* volume = fInode->GetVolume();
216	status_t status;
217	for (int i = 0; i < MAX_TREE_DEPTH && level >= 0; i++, level--) {
218		uint64 requiredBlock = B_BENDIAN_TO_HOST_INT64(*ptrToNode);
219		TRACE("requiredBlock:(%" B_PRIu64 ")\n", requiredBlock);
220		if (path[i].blockNumber == requiredBlock) {
221			// This block already has what we need
222			if (path[i].type == 2)
223				break;
224			status = SearchOffsetInTreeNode(offset, &ptrToNode, i);
225			if (status != B_OK)
226				return status;
227			continue;
228		}
229		// We do not have the block we need
230		ssize_t len;
231		if (level == 0) {
232			// The size of buffer should be the directory block size
233			len = fInode->DirBlockSize();
234			TRACE("path node type:(%" B_PRId32 ")\n", path[i].type);
235			if (path[i].type != 2) {
236				// Size is not directory block size.
237				delete path[i].blockData;
238				path[i].type = 0;
239				path[i].blockData = new(std::nothrow) char[len];
240				if (path[i].blockData == NULL)
241					return B_NO_MEMORY;
242				path[i].type = 2;
243			}
244			uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock);
245			if (read_pos(volume->Device(), readPos, path[i].blockData, len)
246				!= len) {
247				ERROR("FillPath::FillBlockBuffer(): IO Error");
248				return B_IO_ERROR;
249			}
250			path[i].blockNumber = requiredBlock;
251			break;
252		}
253		// The size of buffer should be the block size
254		len = volume->BlockSize();
255		if (path[i].type != 1) {
256			delete path[i].blockData;
257			path[i].type = 0;
258			path[i].blockData = new(std::nothrow) char[len];
259			if (path[i].blockData == NULL)
260				return B_NO_MEMORY;
261			path[i].type = 1;
262		}
263		uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock);
264		if (read_pos(volume->Device(), readPos, path[i].blockData, len)
265			!= len) {
266			ERROR("FillPath::FillBlockBuffer(): IO Error");
267			return B_IO_ERROR;
268		}
269		path[i].blockNumber = requiredBlock;
270		status = SearchOffsetInTreeNode(offset, &ptrToNode, i);
271		if (status != B_OK)
272			return status;
273	}
274
275	return B_OK;
276}
277
278
279status_t
280TreeDirectory::GetAllExtents()
281{
282	xfs_extnum_t noOfExtents = fInode->DataExtentsCount();
283
284	ExtentMapUnwrap* extentsWrapped
285		= new(std::nothrow) ExtentMapUnwrap[noOfExtents];
286	if (extentsWrapped == NULL)
287		return B_NO_MEMORY;
288
289	ArrayDeleter<ExtentMapUnwrap> extentsWrappedDeleter(extentsWrapped);
290
291	Volume* volume = fInode->GetVolume();
292	ssize_t len = volume->BlockSize();
293
294	uint16 levelsInTree = fRoot->Levels();
295	status_t status = fInode->GetNodefromTree(levelsInTree, volume, len,
296		fInode->DirBlockSize(), fSingleDirBlock);
297	if (status != B_OK)
298		return status;
299
300	// We should be at the left most leaf node.
301	// This could be a multilevel node type directory
302	uint64 fileSystemBlockNo;
303	while (1) {
304		// Run till you have leaf blocks to checkout
305		char* leafBuffer = fSingleDirBlock;
306		if (!VerifyHeader<LongBlock>((LongBlock*)leafBuffer, leafBuffer, fInode,
307				0, NULL, XFS_BTREE)) {
308			TRACE("Invalid Long Block");
309			return B_BAD_VALUE;
310		}
311
312		uint32 offset = fInode->SizeOfLongBlock();
313		int numRecs = ((LongBlock*)leafBuffer)->NumRecs();
314
315		for (int i = 0; i < numRecs; i++) {
316			extentsWrapped[fCountOfFilledExtents].first =
317				*(uint64*)(leafBuffer + offset);
318			extentsWrapped[fCountOfFilledExtents].second =
319				*(uint64*)(leafBuffer + offset + sizeof(uint64));
320			offset += sizeof(ExtentMapUnwrap);
321			fCountOfFilledExtents++;
322		}
323
324		fileSystemBlockNo = ((LongBlock*)leafBuffer)->Right();
325		TRACE("Next leaf is at: (%" B_PRIu64 ")\n", fileSystemBlockNo);
326		if (fileSystemBlockNo == (uint64) -1)
327			break;
328		uint64 readPos = fInode->FileSystemBlockToAddr(fileSystemBlockNo);
329		if (read_pos(volume->Device(), readPos, fSingleDirBlock, len)
330				!= len) {
331				ERROR("Extent::FillBlockBuffer(): IO Error");
332				return B_IO_ERROR;
333		}
334	}
335	TRACE("Total covered: (%" B_PRIu32 ")\n", fCountOfFilledExtents);
336
337	status = UnWrapExtents(extentsWrapped);
338
339	return status;
340}
341
342
343status_t
344TreeDirectory::FillBuffer(char* blockBuffer, int howManyBlocksFurther,
345	ExtentMapEntry* targetMap)
346{
347	TRACE("FILLBUFFER\n");
348	ExtentMapEntry map;
349	if (targetMap == NULL)
350		map = fExtents[fCurMapIndex];
351	if (targetMap != NULL)
352		map = *targetMap;
353
354	if (map.br_state != 0)
355		return B_BAD_VALUE;
356
357	ssize_t len = fInode->DirBlockSize();
358	if (blockBuffer == NULL) {
359		blockBuffer = new(std::nothrow) char[len];
360		if (blockBuffer == NULL)
361			return B_NO_MEMORY;
362	}
363
364	xfs_daddr_t readPos = fInode->FileSystemBlockToAddr(
365		map.br_startblock + howManyBlocksFurther);
366
367	if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len)
368		!= len) {
369		ERROR("TreeDirectory::FillBlockBuffer(): IO Error");
370		return B_IO_ERROR;
371	}
372
373	if (targetMap == NULL) {
374		fSingleDirBlock = blockBuffer;
375		ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fSingleDirBlock);
376		if (header == NULL)
377			return B_NO_MEMORY;
378		if (!VerifyHeader<ExtentDataHeader>(header, fSingleDirBlock, fInode,
379				howManyBlocksFurther, &map, XFS_BTREE)) {
380			ERROR("Invalid Data block");
381			delete header;
382			return B_BAD_VALUE;
383		}
384		delete header;
385	}
386	if (targetMap != NULL) {
387		fSingleDirBlock = blockBuffer;
388		/*
389			This could be leaf or node block perform check for both
390			based on magic number found.
391		*/
392		ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
393		if (leaf == NULL)
394			return B_NO_MEMORY;
395
396		if ((leaf->Magic() == XFS_DIR2_LEAFN_MAGIC
397				|| leaf->Magic() == XFS_DIR3_LEAFN_MAGIC)
398			&& !VerifyHeader<ExtentLeafHeader>(leaf, fSingleDirBlock, fInode,
399				howManyBlocksFurther, &map, XFS_BTREE)) {
400			TRACE("Leaf block invalid");
401			delete leaf;
402			return B_BAD_VALUE;
403		}
404		delete leaf;
405		leaf = NULL;
406
407		NodeHeader* node = NodeHeader::Create(fInode, fSingleDirBlock);
408		if (node == NULL)
409			return B_NO_MEMORY;
410
411		if ((node->Magic() == XFS_DA_NODE_MAGIC
412				|| node->Magic() == XFS_DA3_NODE_MAGIC)
413			&& !VerifyHeader<NodeHeader>(node, fSingleDirBlock, fInode,
414				howManyBlocksFurther, &map, XFS_BTREE)) {
415			TRACE("Node block invalid");
416			delete node;
417			return B_BAD_VALUE;
418		}
419		delete node;
420	}
421	return B_OK;
422}
423
424
425int
426TreeDirectory::EntrySize(int len) const
427{
428	int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
429		// uint16 is for the tag
430	if (fInode->HasFileTypeField())
431		entrySize += sizeof(uint8);
432
433	return ROUNDUP(entrySize, 8);
434		// rounding off to next greatest multiple of 8
435}
436
437
438/*
439 * Throw in the desired block number and get the index of it
440 */
441status_t
442TreeDirectory::SearchMapInAllExtent(uint64 blockNo, uint32& mapIndex)
443{
444	ExtentMapEntry map;
445	for (uint32 i = 0; i < fCountOfFilledExtents; i++) {
446		map = fExtents[i];
447		if (map.br_startoff <= blockNo
448			&& (blockNo <= map.br_startoff + map.br_blockcount - 1)) {
449			// Map found
450			mapIndex = i;
451			return B_OK;
452		}
453	}
454
455	return B_ENTRY_NOT_FOUND;
456}
457
458
459status_t
460TreeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino)
461{
462	TRACE("TreeDirectory::GetNext\n");
463	status_t status;
464	if (fExtents == NULL) {
465		status = GetAllExtents();
466		if (status != B_OK)
467			return status;
468	}
469	status = FillBuffer(fSingleDirBlock, 0);
470	if (status != B_OK)
471		return status;
472
473	Volume* volume = fInode->GetVolume();
474
475	void* entry; // This could be unused entry so we should check
476	entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
477
478	uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
479	if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) {
480		entry = (void*)(fSingleDirBlock
481			+ BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode));
482		// This gets us a little faster to the next entry
483	}
484
485	uint32 curDirectorySize = fInode->Size();
486	ExtentMapEntry& map = fExtents[fCurMapIndex];
487	while (fOffset != curDirectorySize) {
488		blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
489
490		TRACE("fOffset:(%" B_PRIu64 "), blockNoFromAddress:(%" B_PRIu32 ")\n",
491			fOffset, blockNoFromAddress);
492		if (fCurBlockNumber != blockNoFromAddress
493			&& blockNoFromAddress > map.br_startoff
494			&& blockNoFromAddress
495				<= map.br_startoff + map.br_blockcount - 1) {
496			// When the block is mapped in the same data
497			// map entry but is not the first block
498			status = FillBuffer(fSingleDirBlock,
499				blockNoFromAddress - map.br_startoff);
500			if (status != B_OK)
501				return status;
502			entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
503			fOffset = fOffset + ExtentDataHeader::Size(fInode);
504			fCurBlockNumber = blockNoFromAddress;
505		} else if (fCurBlockNumber != blockNoFromAddress) {
506			// When the block isn't mapped in the current data map entry
507			uint32 curMapIndex;
508			status = SearchMapInAllExtent(blockNoFromAddress, curMapIndex);
509			if (status != B_OK)
510				return status;
511			fCurMapIndex = curMapIndex;
512			map = fExtents[fCurMapIndex];
513			status = FillBuffer(fSingleDirBlock,
514				blockNoFromAddress - map.br_startoff);
515			if (status != B_OK)
516				return status;
517			entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode));
518			fOffset = fOffset + ExtentDataHeader::Size(fInode);
519			fCurBlockNumber = blockNoFromAddress;
520		}
521
522		ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;
523
524		if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
525			TRACE("Unused entry found\n");
526			fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
527			entry = (void*)
528				((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
529			continue;
530		}
531		ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;
532
533		uint16 currentOffset = (char*)dataEntry - fSingleDirBlock;
534		TRACE("GetNext: fOffset:(%" B_PRIu64 "), currentOffset:(%" B_PRIu16 ")\n",
535			BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset);
536
537		if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) {
538			entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
539			continue;
540		}
541
542		if ((size_t)(dataEntry->namelen) >= *length)
543			return B_BUFFER_OVERFLOW;
544
545		fOffset = fOffset + EntrySize(dataEntry->namelen);
546		memcpy(name, dataEntry->name, dataEntry->namelen);
547		name[dataEntry->namelen] = '\0';
548		*length = dataEntry->namelen + 1;
549		*ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);
550
551		TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "), ino: (%" B_PRIu64 ")\n", name,
552			*length, *ino);
553		return B_OK;
554	}
555
556	return B_ENTRY_NOT_FOUND;
557}
558
559
560status_t
561TreeDirectory::UnWrapExtents(ExtentMapUnwrap* extentsWrapped)
562{
563	fExtents = new(std::nothrow) ExtentMapEntry[fCountOfFilledExtents];
564	if (fExtents == NULL)
565		return B_NO_MEMORY;
566	uint64 first, second;
567
568	for (uint32 i = 0; i < fCountOfFilledExtents; i++) {
569		first = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].first);
570		second = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].second);
571		fExtents[i].br_state = first >> 63;
572		fExtents[i].br_startoff = (first & MASK(63)) >> 9;
573		fExtents[i].br_startblock = ((first & MASK(9)) << 43) | (second >> 21);
574		fExtents[i].br_blockcount = second & MASK(21);
575	}
576
577	return B_OK;
578}
579
580
581void
582TreeDirectory::FillMapEntry(int num, ExtentMapEntry** fMap,
583	int type, int pathIndex)
584{
585	void* pointerToMap;
586	if (type == DATA) {
587		char* base = fPathForData[pathIndex].blockData + BlockLen();
588		off_t offset = num * EXTENT_SIZE;
589		pointerToMap = (void*)(base + offset);
590	} else {
591		char* base = fPathForLeaves[pathIndex].blockData + BlockLen();
592		off_t offset = num * EXTENT_SIZE;
593		pointerToMap = (void*)(base + offset);
594	}
595	uint64 firstHalf = *((uint64*)pointerToMap);
596	uint64 secondHalf = *((uint64*)pointerToMap + 1);
597		//dividing the 128 bits into 2 parts.
598
599	firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
600	secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
601	(*fMap)->br_state = firstHalf >> 63;
602	(*fMap)->br_startoff = (firstHalf & MASK(63)) >> 9;
603	(*fMap)->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
604	(*fMap)->br_blockcount = secondHalf & MASK(21);
605	TRACE("FillMapEntry: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
606		"blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", (*fMap)->br_startoff,
607		(*fMap)->br_startblock,(*fMap)->br_blockcount, (*fMap)->br_state);
608}
609
610
611void
612TreeDirectory::SearchForMapInDirectoryBlock(uint64 blockNo,
613	int entries, ExtentMapEntry** map, int type, int pathIndex)
614{
615	TRACE("SearchForMapInDirectoryBlock: blockNo:(%" B_PRIu64 ")\n", blockNo);
616	for (int i = 0; i < entries; i++) {
617		FillMapEntry(i, map, type, pathIndex);
618		if ((*map)->br_startoff <= blockNo
619			&& (blockNo <= (*map)->br_startoff + (*map)->br_blockcount - 1)) {
620			// Map found
621			return;
622		}
623	}
624	// Map wasn't found. Some kind of corruption. This is checked by caller.
625	*map = NULL;
626}
627
628
629uint32
630TreeDirectory::SearchForHashInNodeBlock(uint32 hashVal)
631{
632	NodeHeader* header = NodeHeader::Create(fInode, fSingleDirBlock);
633	if (header == NULL)
634		return B_NO_MEMORY;
635	NodeEntry* entry = (NodeEntry*)(fSingleDirBlock + NodeHeader::Size(fInode));
636	int count = header->Count();
637	delete header;
638
639	for (int i = 0; i < count; i++) {
640		if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval))
641			return B_BENDIAN_TO_HOST_INT32(entry[i].before);
642	}
643	return 0;
644}
645
646
647status_t
648TreeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino)
649{
650	TRACE("TreeDirectory: Lookup\n");
651	TRACE("Name: %s\n", name);
652	uint32 hashValueOfRequest = hashfunction(name, length);
653	TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);
654
655	Volume* volume = fInode->GetVolume();
656	status_t status;
657
658	ExtentMapEntry* targetMap = new(std::nothrow) ExtentMapEntry;
659	if (targetMap == NULL)
660		return B_NO_MEMORY;
661	int pathIndex = -1;
662	uint32 rightOffset = LEAF_STARTOFFSET(volume->BlockLog());
663
664	// In node directories, the "node blocks" had a single level
665	// Here we could have multiple levels. With each iteration of
666	// the loop we go a level lower.
667	while (rightOffset != fOffsetOfSingleDirBlock && 1) {
668		status = SearchAndFillPath(rightOffset, LEAF);
669		if (status != B_OK)
670			return status;
671
672		// The path should now have the Tree Leaf at appropriate level
673		// Find the directory block in the path
674		for (int i = 0; i < MAX_TREE_DEPTH; i++) {
675			if (fPathForLeaves[i].type == 2) {
676				pathIndex = i;
677				break;
678			}
679		}
680		if (pathIndex == -1) {
681			// corrupt tree
682			return B_BAD_VALUE;
683		}
684
685		// Get the node block from directory block
686		// If level is non-zero, reiterate with new "rightOffset"
687		// Else, we are at leaf block, then break
688		LongBlock* curDirBlock
689			= (LongBlock*)fPathForLeaves[pathIndex].blockData;
690
691		if (!VerifyHeader<LongBlock>(curDirBlock, fPathForLeaves[pathIndex].blockData, fInode,
692				0, NULL, XFS_BTREE)) {
693			TRACE("Invalid Long Block");
694			return B_BAD_VALUE;
695		}
696
697		SearchForMapInDirectoryBlock(rightOffset, curDirBlock->NumRecs(),
698			&targetMap, LEAF, pathIndex);
699		if (targetMap == NULL)
700			return B_BAD_VALUE;
701
702		FillBuffer(fSingleDirBlock, rightOffset - targetMap->br_startoff,
703			targetMap);
704		fOffsetOfSingleDirBlock = rightOffset;
705		ExtentLeafHeader* dirBlock = ExtentLeafHeader::Create(fInode, fSingleDirBlock);
706		if (dirBlock == NULL)
707			return B_NO_MEMORY;
708		if (dirBlock->Magic() == XFS_DIR2_LEAFN_MAGIC
709			|| dirBlock->Magic() == XFS_DIR3_LEAFN_MAGIC) {
710			// Got the potential leaf. Break.
711			delete dirBlock;
712			break;
713		}
714		if (dirBlock->Magic() == XFS_DA_NODE_MAGIC
715			|| dirBlock->Magic() == XFS_DA3_NODE_MAGIC) {
716			rightOffset = SearchForHashInNodeBlock(hashValueOfRequest);
717			if (rightOffset == 0)
718				return B_ENTRY_NOT_FOUND;
719			delete dirBlock;
720			continue;
721		}
722	}
723	// We now have the leaf block that might contain the entry we need.
724	// Else go to the right subling if it might contain it. Else break.
725	while (1) {
726		ExtentLeafHeader* leafHeader
727			= ExtentLeafHeader::Create(fInode, fSingleDirBlock);
728		if (leafHeader == NULL)
729			return B_NO_MEMORY;
730		ExtentLeafEntry* leafEntry
731			= (ExtentLeafEntry*)(fSingleDirBlock + ExtentLeafHeader::Size(fInode));
732
733		int numberOfLeafEntries = leafHeader->Count();
734		TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries);
735		int left = 0;
736		int right = numberOfLeafEntries - 1;
737
738		hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest);
739
740		uint32 nextLeaf = leafHeader->Forw();
741		uint32 lastHashVal = B_BENDIAN_TO_HOST_INT32(
742			leafEntry[numberOfLeafEntries - 1].hashval);
743
744		while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
745				== hashValueOfRequest) {
746			uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
747			if (address == 0) {
748				left++;
749				continue;
750			}
751
752			uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume);
753			uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode);
754
755			TRACE("BlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset);
756
757			status = SearchAndFillPath(dataBlockNumber, DATA);
758			int pathIndex = -1;
759			for (int i = 0; i < MAX_TREE_DEPTH; i++) {
760				if (fPathForData[i].type == 2) {
761					pathIndex = i;
762					break;
763				}
764			}
765			if (pathIndex == -1)
766				return B_BAD_VALUE;
767
768			LongBlock* curDirBlock
769				= (LongBlock*)fPathForData[pathIndex].blockData;
770
771			SearchForMapInDirectoryBlock(dataBlockNumber,
772				curDirBlock->NumRecs(), &targetMap, DATA, pathIndex);
773			if (targetMap == NULL)
774				return B_BAD_VALUE;
775
776			FillBuffer(fSingleDirBlock,
777				dataBlockNumber - targetMap->br_startoff, targetMap);
778			fOffsetOfSingleDirBlock = dataBlockNumber;
779
780			TRACE("offset:(%" B_PRIu32 ")\n", offset);
781			ExtentDataEntry* entry
782				= (ExtentDataEntry*)(fSingleDirBlock + offset);
783
784			int retVal = strncmp(name, (char*)entry->name, entry->namelen);
785			if (retVal == 0) {
786				*ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
787				TRACE("ino:(%" B_PRIu64 ")\n", *ino);
788				return B_OK;
789			}
790			left++;
791		}
792		if (lastHashVal == hashValueOfRequest && nextLeaf != (uint32) -1) {
793			// Go to forward neighbor. We might find an entry there.
794			status = SearchAndFillPath(nextLeaf, LEAF);
795			if (status != B_OK)
796				return status;
797
798			pathIndex = -1;
799			for (int i = 0; i < MAX_TREE_DEPTH; i++) {
800				if (fPathForLeaves[i].type == 2) {
801					pathIndex = i;
802					break;
803				}
804			}
805			if (pathIndex == -1)
806				return B_BAD_VALUE;
807
808			LongBlock* curDirBlock
809				= (LongBlock*)fPathForLeaves[pathIndex].blockData;
810
811			SearchForMapInDirectoryBlock(nextLeaf, curDirBlock->NumRecs(),
812				&targetMap, LEAF, pathIndex);
813			if (targetMap == NULL)
814				return B_BAD_VALUE;
815
816			FillBuffer(fSingleDirBlock,
817				nextLeaf - targetMap->br_startoff, targetMap);
818			fOffsetOfSingleDirBlock = nextLeaf;
819
820			continue;
821		} else {
822			break;
823		}
824		delete leafHeader;
825	}
826	return B_ENTRY_NOT_FOUND;
827}
828
829
830uint32
831LongBlock::ExpectedMagic(int8 WhichDirectory, Inode* inode)
832{
833	if(inode->Version() == 3)
834		return XFS_BMAP_CRC_MAGIC;
835	else
836		return XFS_BMAP_MAGIC;
837}
838
839
840uint32
841LongBlock::CRCOffset()
842{
843	return offsetof(LongBlock, bb_crc);
844}