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