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 "Node.h"
8
9#include "VerifyHeader.h"
10
11
12NodeDirectory::NodeDirectory(Inode* inode)
13	:
14	fInode(inode),
15	fDataMap(NULL),
16	fLeafMap(NULL),
17	fOffset(0),
18	fDataBuffer(NULL),
19	fLeafBuffer(NULL),
20	fCurBlockNumber(-1)
21{
22	fFirstLeafMapIndex = FirstLeafMapIndex();
23}
24
25
26NodeDirectory::~NodeDirectory()
27{
28	delete fDataMap;
29	delete fLeafMap;
30	delete fDataBuffer;
31	delete fLeafBuffer;
32}
33
34
35xfs_extnum_t
36NodeDirectory::FirstLeafMapIndex()
37{
38	int len = fInode->DataExtentsCount();
39
40	for (int i = 0; i < len; i++) {
41		void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize());
42		void* pointerToMap = (void*)((char*)directoryFork + i * EXTENT_SIZE);
43
44		uint64 startoff = *((uint64*)pointerToMap);
45		startoff = B_BENDIAN_TO_HOST_INT64(startoff);
46		startoff = (startoff & MASK(63)) >> 9;
47
48		// First Leaf Map found
49		if (startoff == LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog()))
50			return i;
51	}
52
53	// No Leaf
54	return -1;
55}
56
57
58status_t
59NodeDirectory::Init()
60{
61	TRACE("Node directory : init()\n");
62	fLeafMap = new(std::nothrow) ExtentMapEntry;
63	if (fLeafMap == NULL)
64		return B_NO_MEMORY;
65
66	fDataMap = new(std::nothrow) ExtentMapEntry;
67	if (fDataMap == NULL)
68		return B_NO_MEMORY;
69
70	FillMapEntry(fFirstLeafMapIndex, fLeafMap);
71	fCurLeafMapNumber = 1;
72	FillMapEntry(0, fDataMap);
73	return B_OK;
74}
75
76
77bool
78NodeDirectory::IsNodeType()
79{
80	if (fFirstLeafMapIndex == -1)
81		return false;
82	return true;
83}
84
85
86void
87NodeDirectory::FillMapEntry(int num, ExtentMapEntry* fMap)
88{
89	void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize());
90	void* pointerToMap = (void*)((char*)directoryFork + num * EXTENT_SIZE);
91	uint64 firstHalf = *((uint64*)pointerToMap);
92	uint64 secondHalf = *((uint64*)pointerToMap + 1);
93		//dividing the 128 bits into 2 parts.
94
95	firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
96	secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
97	fMap->br_state = firstHalf >> 63;
98	fMap->br_startoff = (firstHalf & MASK(63)) >> 9;
99	fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
100	fMap->br_blockcount = secondHalf & MASK(21);
101	TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
102		"blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock,
103		fMap->br_blockcount, fMap->br_state);
104}
105
106
107status_t
108NodeDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur)
109{
110	TRACE("FILLBUFFER\n");
111	ExtentMapEntry* map;
112	if (type == DATA)
113		map = fDataMap;
114	else if (type == LEAF)
115		map = fLeafMap;
116	else
117		return B_BAD_VALUE;
118
119	if (map->br_state != 0)
120		return B_BAD_VALUE;
121
122	ssize_t len = fInode->DirBlockSize();
123	if (blockBuffer == NULL) {
124		blockBuffer = new(std::nothrow) char[len];
125		if (blockBuffer == NULL)
126			return B_NO_MEMORY;
127	}
128
129	xfs_daddr_t readPos = fInode->FileSystemBlockToAddr(map->br_startblock
130		+ howManyBlocksFurthur);
131
132	if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len)
133		!= len) {
134		ERROR("NodeDirectory::FillBlockBuffer(): IO Error");
135		return B_IO_ERROR;
136	}
137
138	if (type == DATA) {
139		fDataBuffer = blockBuffer;
140		ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fDataBuffer);
141		if(header == NULL)
142			return B_NO_MEMORY;
143		if (!VerifyHeader<ExtentDataHeader>(header, fDataBuffer, fInode,
144				howManyBlocksFurthur, fDataMap, XFS_NODE)) {
145			ERROR("DATA BLOCK INVALID\n");
146			delete header;
147			return B_BAD_VALUE;
148		}
149		delete header;
150
151	} else if (type == LEAF) {
152		fLeafBuffer = blockBuffer;
153		/*
154			This could be leaf or node block perform check for both
155			based on magic number found.
156		*/
157		ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fLeafBuffer);
158		if (leaf == NULL)
159			return B_NO_MEMORY;
160
161		if ((leaf->Magic() == XFS_DIR2_LEAFN_MAGIC
162				|| leaf->Magic() == XFS_DIR3_LEAFN_MAGIC)
163			&& !VerifyHeader<ExtentLeafHeader>(leaf, fLeafBuffer, fInode,
164				howManyBlocksFurthur, fLeafMap, XFS_NODE)) {
165			TRACE("Leaf block invalid");
166			delete leaf;
167			return B_BAD_VALUE;
168		}
169		delete leaf;
170		leaf = NULL;
171
172		NodeHeader* node = NodeHeader::Create(fInode, fLeafBuffer);
173		if (node == NULL)
174			return B_NO_MEMORY;
175
176		if ((node->Magic() == XFS_DA_NODE_MAGIC
177				|| node->Magic() == XFS_DA3_NODE_MAGIC)
178			&& !VerifyHeader<NodeHeader>(node, fLeafBuffer, fInode,
179				howManyBlocksFurthur, fLeafMap, XFS_NODE)) {
180			TRACE("Node block invalid");
181			delete node;
182			return B_BAD_VALUE;
183		}
184		delete node;
185	}
186
187	return B_OK;
188}
189
190
191uint32
192NodeDirectory::GetOffsetFromAddress(uint32 address)
193{
194	address = address * 8;
195		// block offset in eight bytes, hence multiple with 8
196	return address & (fInode->DirBlockSize() - 1);
197}
198
199
200status_t
201NodeDirectory::FindHashInNode(uint32 hashVal, uint32* rightMapOffset)
202{
203	NodeHeader* header = NodeHeader::Create(fInode, fLeafBuffer);
204	if (header == NULL)
205		return B_NO_MEMORY;
206
207	NodeEntry* entry = (NodeEntry*)(void*)(fLeafBuffer + NodeHeader::Size(fInode));
208	int count = header->Count();
209	delete header;
210	if ((NodeEntry*)(void*)fLeafBuffer + fInode->DirBlockSize()
211		< &entry[count]) {
212			return B_BAD_VALUE;
213	}
214
215	for (int i = 0; i < count; i++) {
216		if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval)) {
217			*rightMapOffset = B_BENDIAN_TO_HOST_INT32(entry[i].before);
218			return B_OK;
219		}
220	}
221
222	*rightMapOffset = 1;
223	return B_OK;
224}
225
226
227int
228NodeDirectory::EntrySize(int len) const
229{
230	int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
231			// uint16 is for the tag
232	if (fInode->HasFileTypeField())
233		entrySize += sizeof(uint8);
234
235	return ROUNDUP(entrySize, 8);
236			// rounding off to closest multiple of 8
237}
238
239
240void
241NodeDirectory::SearchAndFillDataMap(uint64 blockNo)
242{
243	int len = fInode->DataExtentsCount();
244
245	for (int i = 0; i <= len - fFirstLeafMapIndex; i++) {
246		FillMapEntry(i, fDataMap);
247		if (fDataMap->br_startoff <= blockNo
248			&& (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1))
249			// Map found
250			return;
251	}
252}
253
254
255status_t
256NodeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino)
257{
258	TRACE("NodeDirectory::GetNext\n");
259	status_t status;
260
261	if (fDataBuffer == NULL) {
262		status = FillBuffer(DATA, fDataBuffer, 0);
263		if (status != B_OK)
264			return status;
265	}
266
267	Volume* volume = fInode->GetVolume();
268
269	void* entry; // This could be unused entry so we should check
270
271	entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode));
272
273	uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
274	if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) {
275		entry = (void*)(fDataBuffer
276			+ BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode));
277		// This gets us a little faster to the next entry
278	}
279
280	uint32 curDirectorySize = fInode->Size();
281
282	while (fOffset != curDirectorySize) {
283		blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
284
285		TRACE("fOffset:(%" B_PRIu32 "), blockNoFromAddress:(%" B_PRIu32 ")\n",
286			fOffset, blockNoFromAddress);
287		if (fCurBlockNumber != blockNoFromAddress
288			&& blockNoFromAddress > fDataMap->br_startoff
289			&& blockNoFromAddress
290				<= fDataMap->br_startoff + fDataMap->br_blockcount - 1) {
291			// When the block is mapped in the same data
292			// map entry but is not the first block
293			status = FillBuffer(DATA, fDataBuffer,
294				blockNoFromAddress - fDataMap->br_startoff);
295			if (status != B_OK)
296				return status;
297			entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode));
298			fOffset = fOffset + ExtentDataHeader::Size(fInode);
299			fCurBlockNumber = blockNoFromAddress;
300		} else if (fCurBlockNumber != blockNoFromAddress) {
301			// When the block isn't mapped in the current data map entry
302			SearchAndFillDataMap(blockNoFromAddress);
303			status = FillBuffer(DATA, fDataBuffer,
304				blockNoFromAddress - fDataMap->br_startoff);
305			if (status != B_OK)
306				return status;
307			entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode));
308			fOffset = fOffset + ExtentDataHeader::Size(fInode);
309			fCurBlockNumber = blockNoFromAddress;
310		}
311
312		ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;
313
314		if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
315			TRACE("Unused entry found\n");
316			fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
317			entry = (void*)
318				((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
319			continue;
320		}
321		ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;
322
323		uint16 currentOffset = (char*)dataEntry - fDataBuffer;
324		TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n",
325			BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset);
326
327		if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) {
328			entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
329			continue;
330		}
331
332		if ((size_t)(dataEntry->namelen) >= *length)
333			return B_BUFFER_OVERFLOW;
334
335		fOffset = fOffset + EntrySize(dataEntry->namelen);
336		memcpy(name, dataEntry->name, dataEntry->namelen);
337		name[dataEntry->namelen] = '\0';
338		*length = dataEntry->namelen + 1;
339		*ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);
340
341		TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n",
342			name,*length, *ino);
343		return B_OK;
344	}
345
346	return B_ENTRY_NOT_FOUND;
347}
348
349
350status_t
351NodeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino)
352{
353	TRACE("NodeDirectory: Lookup\n");
354	TRACE("Name: %s\n", name);
355	uint32 hashValueOfRequest = hashfunction(name, length);
356	TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);
357
358	status_t status;
359	if (fCurLeafBufferNumber != 1) {
360		if (fCurLeafMapNumber != 1) {
361			FillMapEntry(fFirstLeafMapIndex, fLeafMap);
362			fCurLeafMapNumber = 1;
363		}
364		status = FillBuffer(LEAF, fLeafBuffer, 0);
365		if (status != B_OK)
366			return status;
367		fCurLeafBufferNumber = 1;
368	}
369	/* Leaf now has the nodes. */
370	uint32 rightMapOffset;
371	status = FindHashInNode(hashValueOfRequest, &rightMapOffset);
372	if(status != B_OK)
373		return status;
374
375	if (rightMapOffset == 1) {
376		TRACE("Not in this directory.\n");
377		return B_ENTRY_NOT_FOUND;
378	}
379
380	TRACE("rightMapOffset:(%" B_PRIu32 ")\n", rightMapOffset);
381
382	for(int i = fFirstLeafMapIndex; i < fInode->DataExtentsCount(); i++)
383	{
384		FillMapEntry(i, fLeafMap);
385		fCurLeafMapNumber = 2;
386		status = FillBuffer(LEAF, fLeafBuffer,
387			rightMapOffset - fLeafMap->br_startoff);
388		if (status != B_OK)
389			return status;
390		fCurLeafBufferNumber = 2;
391		ExtentLeafHeader* leafHeader = ExtentLeafHeader::Create(fInode, fLeafBuffer);
392		if(leafHeader == NULL)
393			return B_NO_MEMORY;
394		ExtentLeafEntry* leafEntry =
395			(ExtentLeafEntry*)(void*)(fLeafBuffer + ExtentLeafHeader::Size(fInode));
396		if (leafEntry == NULL)
397			return B_NO_MEMORY;
398
399		int numberOfLeafEntries = leafHeader->Count();
400		TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries);
401		int left = 0;
402		int right = numberOfLeafEntries - 1;
403		Volume* volume = fInode->GetVolume();
404
405		hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest);
406
407		while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
408				== hashValueOfRequest) {
409
410			uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
411			if (address == 0) {
412				left++;
413				continue;
414			}
415
416			uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume);
417			uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode);
418
419			TRACE("DataBlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n",
420				dataBlockNumber, offset);
421			if (dataBlockNumber != fCurBlockNumber) {
422				fCurBlockNumber = dataBlockNumber;
423				SearchAndFillDataMap(dataBlockNumber);
424				status = FillBuffer(DATA, fDataBuffer,
425					dataBlockNumber - fDataMap->br_startoff);
426				if (status != B_OK)
427					return status;
428			}
429
430			TRACE("offset:(%" B_PRIu32 ")\n", offset);
431			ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset);
432
433			int retVal = strncmp(name, (char*)entry->name, entry->namelen);
434			if (retVal == 0) {
435				*ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
436				TRACE("ino:(%" B_PRIu64 ")\n", *ino);
437				return B_OK;
438			}
439			left++;
440		}
441		delete leafHeader;
442	}
443
444	return B_ENTRY_NOT_FOUND;
445}
446
447
448NodeHeader::~NodeHeader()
449{
450}
451
452
453/*
454	In NodeHeader we have same magic number for all forms of
455	directory so return magic number as per Inode Version.
456*/
457uint32
458NodeHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode)
459{
460	if (inode->Version() == 1 || inode->Version() == 2)
461		return XFS_DA_NODE_MAGIC;
462	else
463		return XFS_DA3_NODE_MAGIC;
464}
465
466
467uint32
468NodeHeader::CRCOffset()
469{
470	return offsetof(NodeHeaderV5::OnDiskData, info.crc);
471}
472
473
474NodeHeader*
475NodeHeader::Create(Inode* inode, const char* buffer)
476{
477	if (inode->Version() == 1 || inode->Version() == 2) {
478		NodeHeaderV4* header = new (std::nothrow) NodeHeaderV4(buffer);
479		return header;
480	} else {
481		NodeHeaderV5* header = new (std::nothrow) NodeHeaderV5(buffer);
482		return header;
483	}
484}
485
486
487/*
488	This Function returns Actual size of leaf header
489	in all forms of directory.
490	Never use sizeof() operator because we now have
491	vtable as well and it will give wrong results
492*/
493uint32
494NodeHeader::Size(Inode* inode)
495{
496	if (inode->Version() == 1 || inode->Version() == 2)
497		return sizeof(NodeHeaderV4::OnDiskData);
498	else
499		return sizeof(NodeHeaderV5::OnDiskData);
500}
501
502
503void
504NodeHeaderV4::SwapEndian()
505{
506	fData.info.forw	=	B_BENDIAN_TO_HOST_INT32(fData.info.forw);
507	fData.info.back	=	B_BENDIAN_TO_HOST_INT32(fData.info.back);
508	fData.info.magic	= 	B_BENDIAN_TO_HOST_INT16(fData.info.magic);
509	fData.info.pad	=	B_BENDIAN_TO_HOST_INT16(fData.info.pad);
510	fData.count		=	B_BENDIAN_TO_HOST_INT16(fData.count);
511	fData.level		=	B_BENDIAN_TO_HOST_INT16(fData.level);
512}
513
514
515NodeHeaderV4::NodeHeaderV4(const char* buffer)
516{
517	uint32 offset = 0;
518
519	fData.info = *(BlockInfo*)(buffer + offset);
520	offset += sizeof(BlockInfo);
521
522	fData.count = *(uint16*)(buffer + offset);
523	offset += sizeof(uint16);
524
525	fData.level = *(uint16*)(buffer + offset);
526
527	SwapEndian();
528}
529
530
531NodeHeaderV4::~NodeHeaderV4()
532{
533}
534
535
536uint16
537NodeHeaderV4::Magic()
538{
539	return fData.info.magic;
540}
541
542
543uint64
544NodeHeaderV4::Blockno()
545{
546	return B_BAD_VALUE;
547}
548
549
550uint64
551NodeHeaderV4::Lsn()
552{
553	return B_BAD_VALUE;
554}
555
556
557uint64
558NodeHeaderV4::Owner()
559{
560	return B_BAD_VALUE;
561}
562
563
564const uuid_t&
565NodeHeaderV4::Uuid()
566{
567	static uuid_t nullUuid = {0};
568	return nullUuid;
569}
570
571
572uint16
573NodeHeaderV4::Count()
574{
575	return fData.count;
576}
577
578
579void
580NodeHeaderV5::SwapEndian()
581{
582	fData.info.forw		=	B_BENDIAN_TO_HOST_INT32(fData.info.forw);
583	fData.info.back		=	B_BENDIAN_TO_HOST_INT32(fData.info.back);
584	fData.info.magic	= 	B_BENDIAN_TO_HOST_INT16(fData.info.magic);
585	fData.info.pad		=	B_BENDIAN_TO_HOST_INT16(fData.info.pad);
586	fData.info.blkno	=	B_BENDIAN_TO_HOST_INT64(fData.info.blkno);
587	fData.info.lsn		=	B_BENDIAN_TO_HOST_INT64(fData.info.lsn);
588	fData.info.owner	=	B_BENDIAN_TO_HOST_INT64(fData.info.owner);
589	fData.count			=	B_BENDIAN_TO_HOST_INT16(fData.count);
590	fData.level			=	B_BENDIAN_TO_HOST_INT16(fData.level);
591	fData.pad32			=	B_BENDIAN_TO_HOST_INT32(fData.pad32);
592}
593
594
595NodeHeaderV5::NodeHeaderV5(const char* buffer)
596{
597	memcpy(&fData, buffer, sizeof(fData));
598	SwapEndian();
599}
600
601
602NodeHeaderV5::~NodeHeaderV5()
603{
604}
605
606
607uint16
608NodeHeaderV5::Magic()
609{
610	return fData.info.magic;
611}
612
613
614uint64
615NodeHeaderV5::Blockno()
616{
617	return fData.info.blkno;
618}
619
620
621uint64
622NodeHeaderV5::Lsn()
623{
624	return fData.info.lsn;
625}
626
627
628uint64
629NodeHeaderV5::Owner()
630{
631	return fData.info.owner;
632}
633
634
635const uuid_t&
636NodeHeaderV5::Uuid()
637{
638	return fData.info.uuid;
639}
640
641
642uint16
643NodeHeaderV5::Count()
644{
645	return fData.count;
646}
647