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 "Extent.h"
9
10#include "VerifyHeader.h"
11
12
13Extent::Extent(Inode* inode)
14	:
15	fInode(inode),
16	fOffset(0)
17{
18}
19
20
21Extent::~Extent()
22{
23}
24
25
26void
27Extent::FillMapEntry(void* pointerToMap)
28{
29	uint64 firstHalf = *((uint64*)pointerToMap);
30	uint64 secondHalf = *((uint64*)pointerToMap + 1);
31		// dividing the 128 bits into 2 parts.
32	firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
33	secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
34	fMap->br_state = (firstHalf >> 63);
35	fMap->br_startoff = (firstHalf & MASK(63)) >> 9;
36	fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
37	fMap->br_blockcount = (secondHalf & MASK(21));
38	TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
39		"blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock,
40		fMap->br_blockcount, fMap->br_state);
41}
42
43
44status_t
45Extent::FillBlockBuffer()
46{
47	if (fMap->br_state != 0)
48		return B_BAD_VALUE;
49
50	int len = fInode->DirBlockSize();
51	fBlockBuffer = new(std::nothrow) char[len];
52	if (fBlockBuffer == NULL)
53		return B_NO_MEMORY;
54
55	xfs_daddr_t readPos =
56		fInode->FileSystemBlockToAddr(fMap->br_startblock);
57
58	if (read_pos(fInode->GetVolume()->Device(), readPos, fBlockBuffer, len)
59		!= len) {
60		ERROR("Extent::FillBlockBuffer(): IO Error");
61		return B_IO_ERROR;
62	}
63
64	return B_OK;
65}
66
67
68status_t
69Extent::Init()
70{
71	fMap = new(std::nothrow) ExtentMapEntry;
72	if (fMap == NULL)
73		return B_NO_MEMORY;
74
75	ASSERT(IsBlockType() == true);
76	void* pointerToMap = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize());
77	FillMapEntry(pointerToMap);
78	ASSERT(fMap->br_blockcount == 1);
79		// TODO: This is always true for block directories
80		// If we use this implementation for leaf directories, this is not
81		// always true
82	status_t status = FillBlockBuffer();
83	if (status != B_OK)
84		return status;
85
86	ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fBlockBuffer);
87	if (header == NULL)
88		return B_NO_MEMORY;
89	if (!VerifyHeader<ExtentDataHeader>(header, fBlockBuffer, fInode, 0, fMap, XFS_BLOCK)) {
90		status = B_BAD_VALUE;
91		ERROR("Extent:Init(): Bad Block!\n");
92	}
93
94	delete header;
95	return status;
96}
97
98
99ExtentBlockTail*
100Extent::BlockTail()
101{
102	return (ExtentBlockTail*)
103		(fBlockBuffer + fInode->DirBlockSize() - sizeof(ExtentBlockTail));
104}
105
106
107uint32
108Extent::GetOffsetFromAddress(uint32 address)
109{
110	address = address * 8;
111		// block offset in eight bytes, hence multiple with 8
112	return address & (fInode->DirBlockSize() - 1);
113}
114
115
116ExtentLeafEntry*
117Extent::BlockFirstLeaf(ExtentBlockTail* tail)
118{
119	return (ExtentLeafEntry*)tail - B_BENDIAN_TO_HOST_INT32(tail->count);
120}
121
122
123bool
124Extent::IsBlockType()
125{
126	bool status = true;
127	if (fInode->BlockCount() != 1)
128		status = false;
129	if (fInode->Size() != fInode->DirBlockSize())
130		status = false;
131	void* pointerToMap = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize());
132	xfs_fileoff_t startoff = (*((uint64*)pointerToMap) & MASK(63)) >> 9;
133	if (startoff != 0)
134		status = false;
135	return status;
136}
137
138
139int
140Extent::EntrySize(int len) const
141{
142	int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
143			// uint16 is for the tag
144	if (fInode->HasFileTypeField())
145		entrySize += sizeof(uint8);
146
147	return (entrySize + 7) & -8;
148			// rounding off to closest multiple of 8
149}
150
151
152status_t
153Extent::GetNext(char* name, size_t* length, xfs_ino_t* ino)
154{
155	TRACE("Extend::GetNext\n");
156
157	void* entry; // This could be unused entry so we should check
158
159	entry = (void*)(fBlockBuffer + ExtentDataHeader::Size(fInode));
160
161	int numberOfEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->count);
162	int numberOfStaleEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->stale);
163
164	// We don't read stale entries.
165	numberOfEntries -= numberOfStaleEntries;
166	TRACE("numberOfEntries:(%" B_PRId32 ")\n", numberOfEntries);
167	uint16 currentOffset = (char*)entry - fBlockBuffer;
168
169	for (int i = 0; i < numberOfEntries; i++) {
170		ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;
171
172		if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
173			TRACE("Unused entry found\n");
174			currentOffset += B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
175			entry = (void*)
176				((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
177			i--;
178			continue;
179		}
180		ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;
181
182		if (fOffset >= currentOffset) {
183			entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
184			currentOffset += EntrySize(dataEntry->namelen);
185			continue;
186		}
187
188		if ((size_t)(dataEntry->namelen) >= *length)
189				return B_BUFFER_OVERFLOW;
190
191		fOffset = currentOffset;
192		memcpy(name, dataEntry->name, dataEntry->namelen);
193		name[dataEntry->namelen] = '\0';
194		*length = dataEntry->namelen + 1;
195		*ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);
196
197		TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n", name,
198			*length, *ino);
199		return B_OK;
200	}
201
202	return B_ENTRY_NOT_FOUND;
203}
204
205
206status_t
207Extent::Lookup(const char* name, size_t length, xfs_ino_t* ino)
208{
209	TRACE("Extent: Lookup\n");
210	TRACE("Name: %s\n", name);
211	uint32 hashValueOfRequest = hashfunction(name, length);
212	TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);
213	ExtentBlockTail* blockTail = BlockTail();
214	ExtentLeafEntry* leafEntry = BlockFirstLeaf(blockTail);
215
216	int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT32(blockTail->count);
217	int left = 0;
218	int right = numberOfLeafEntries - 1;
219
220	hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest);
221
222	while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
223			== hashValueOfRequest) {
224
225		uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
226		if (address == 0) {
227			left++;
228			continue;
229		}
230
231		uint32 offset = GetOffsetFromAddress(address);
232		TRACE("offset:(%" B_PRIu32 ")\n", offset);
233		ExtentDataEntry* entry = (ExtentDataEntry*)(fBlockBuffer + offset);
234
235		int retVal = strncmp(name, (char*)entry->name, entry->namelen);
236		if (retVal == 0) {
237			*ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
238			TRACE("ino:(%" B_PRIu64 ")\n", *ino);
239			return B_OK;
240		}
241		left++;
242	}
243
244	return B_ENTRY_NOT_FOUND;
245}
246
247
248ExtentDataHeader::~ExtentDataHeader()
249{
250}
251
252
253/*
254	First see which type of directory we reading then
255	return magic number as per Inode Version.
256*/
257uint32
258ExtentDataHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode)
259{
260	if (WhichDirectory == XFS_BLOCK) {
261		if (inode->Version() == 1 || inode->Version() == 2)
262			return DIR2_BLOCK_HEADER_MAGIC;
263		else
264			return DIR3_BLOCK_HEADER_MAGIC;
265	} else {
266		if (inode->Version() == 1 || inode->Version() == 2)
267			return V4_DATA_HEADER_MAGIC;
268		else
269			return V5_DATA_HEADER_MAGIC;
270	}
271}
272
273
274uint32
275ExtentDataHeader::CRCOffset()
276{
277	return offsetof(ExtentDataHeaderV5::OnDiskData, crc);
278}
279
280
281ExtentDataHeader*
282ExtentDataHeader::Create(Inode* inode, const char* buffer)
283{
284	if (inode->Version() == 1 || inode->Version() == 2) {
285		ExtentDataHeaderV4* header = new (std::nothrow) ExtentDataHeaderV4(buffer);
286		return header;
287	} else {
288		ExtentDataHeaderV5* header = new (std::nothrow) ExtentDataHeaderV5(buffer);
289		return header;
290	}
291}
292
293
294/*
295	This Function returns Actual size of data header
296	in all forms of directory.
297	Never use sizeof() operator because we now have
298	vtable as well and it will give wrong results
299*/
300uint32
301ExtentDataHeader::Size(Inode* inode)
302{
303	if (inode->Version() == 1 || inode->Version() == 2)
304		return sizeof(ExtentDataHeaderV4::OnDiskData);
305	else
306		return sizeof(ExtentDataHeaderV5::OnDiskData);
307}
308
309
310void
311ExtentDataHeaderV4::_SwapEndian()
312{
313	fData.magic = (B_BENDIAN_TO_HOST_INT32(fData.magic));
314}
315
316
317ExtentDataHeaderV4::ExtentDataHeaderV4(const char* buffer)
318{
319	memcpy(&fData, buffer, sizeof(fData));
320	_SwapEndian();
321}
322
323
324ExtentDataHeaderV4::~ExtentDataHeaderV4()
325{
326}
327
328
329uint32
330ExtentDataHeaderV4::Magic()
331{
332	return fData.magic;
333}
334
335
336uint64
337ExtentDataHeaderV4::Blockno()
338{
339	return B_BAD_VALUE;
340}
341
342
343uint64
344ExtentDataHeaderV4::Lsn()
345{
346	return B_BAD_VALUE;
347}
348
349
350uint64
351ExtentDataHeaderV4::Owner()
352{
353	return B_BAD_VALUE;
354}
355
356
357const uuid_t&
358ExtentDataHeaderV4::Uuid()
359{
360	static uuid_t nullUuid;
361	return nullUuid;
362}
363
364
365void
366ExtentDataHeaderV5::_SwapEndian()
367{
368	fData.magic	=	B_BENDIAN_TO_HOST_INT32(fData.magic);
369	fData.blkno	=	B_BENDIAN_TO_HOST_INT64(fData.blkno);
370	fData.lsn		=	B_BENDIAN_TO_HOST_INT64(fData.lsn);
371	fData.owner	=	B_BENDIAN_TO_HOST_INT64(fData.owner);
372	fData.pad		=	B_BENDIAN_TO_HOST_INT32(fData.pad);
373}
374
375
376ExtentDataHeaderV5::ExtentDataHeaderV5(const char* buffer)
377{
378	memcpy(&fData, buffer, sizeof(fData));
379	_SwapEndian();
380}
381
382
383ExtentDataHeaderV5::~ExtentDataHeaderV5()
384{
385}
386
387
388uint32
389ExtentDataHeaderV5::Magic()
390{
391	return fData.magic;
392}
393
394
395uint64
396ExtentDataHeaderV5::Blockno()
397{
398	return fData.blkno;
399}
400
401
402uint64
403ExtentDataHeaderV5::Lsn()
404{
405	return fData.lsn;
406}
407
408
409uint64
410ExtentDataHeaderV5::Owner()
411{
412	return fData.owner;
413}
414
415
416const uuid_t&
417ExtentDataHeaderV5::Uuid()
418{
419	return fData.uuid;
420}
421