xref: /haiku/src/add-ons/kernel/file_systems/xfs/Extent.cpp (revision 8c78892580f132d10e624aef96f835df8d94bf19)
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 "Extent.h"
8 
9 
10 Extent::Extent(Inode* inode)
11 	:
12 	fInode(inode),
13 	fOffset(0)
14 {
15 }
16 
17 
18 void
19 Extent::FillMapEntry(void* pointerToMap)
20 {
21 	uint64 firstHalf = *((uint64*)pointerToMap);
22 	uint64 secondHalf = *((uint64*)pointerToMap + 1);
23 		//dividing the 128 bits into 2 parts.
24 	firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
25 	secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
26 	fMap->br_state = (firstHalf >> 63);
27 	fMap->br_startoff = (firstHalf & MASK(63)) >> 9;
28 	fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
29 	fMap->br_blockcount = (secondHalf & MASK(21));
30 	TRACE("Extent::Init: startoff:(%ld), startblock:(%ld), blockcount:(%ld),"
31 			"state:(%d)\n",
32 		fMap->br_startoff,
33 		fMap->br_startblock,
34 		fMap->br_blockcount,
35 		fMap->br_state
36 		);
37 }
38 
39 
40 status_t
41 Extent::FillBlockBuffer()
42 {
43 	if (fMap->br_state != 0)
44 		return B_BAD_VALUE;
45 
46 	int len = fInode->DirBlockSize();
47 	fBlockBuffer = new(std::nothrow) char[len];
48 	if (fBlockBuffer == NULL)
49 		return B_NO_MEMORY;
50 
51 	Volume* volume = fInode->GetVolume();
52 	xfs_agblock_t numberOfBlocksInAg = volume->AgBlocks();
53 
54 	uint64 agNo = FSBLOCKS_TO_AGNO(fMap->br_startblock, volume);
55 	uint64 agBlockNo = FSBLOCKS_TO_AGBLOCKNO(fMap->br_startblock, volume);
56 	xfs_fsblock_t blockToRead = FSBLOCKS_TO_BASICBLOCKS(volume->BlockLog(),
57 		((uint64)(agNo * numberOfBlocksInAg) + agBlockNo));
58 
59 	xfs_daddr_t readPos = blockToRead * (BASICBLOCKSIZE) + fMap->br_startoff;
60 
61 	TRACE("blockToRead: (%ld), readPos: (%ld)\n", blockToRead, readPos);
62 	if (read_pos(volume->Device(), readPos, fBlockBuffer, len) != len) {
63 		ERROR("Extent::FillBlockBuffer(): IO Error");
64 		return B_IO_ERROR;
65 	}
66 
67 	return B_OK;
68 }
69 
70 
71 status_t
72 Extent::Init()
73 {
74 	fMap = new(std::nothrow) ExtentMapEntry;
75 	if (fMap == NULL)
76 		return B_NO_MEMORY;
77 
78 	ASSERT(BlockType() == true);
79 	void* pointerToMap = DIR_DFORK_PTR(fInode->Buffer());
80 	FillMapEntry(pointerToMap);
81 	ASSERT(fMap->br_blockcount == 1);
82 		//TODO: This is always true for block directories
83 		//If we use this implementation for leaf directories, this is not
84 		//always true
85 	status_t status = FillBlockBuffer();
86 	ExtentDataHeader* header = (ExtentDataHeader*)fBlockBuffer;
87 	if (B_BENDIAN_TO_HOST_INT32(header->magic) == DIR2_BLOCK_HEADER_MAGIC) {
88 		status = B_OK;
89 		TRACE("Extent:Init(): Block read successfully\n");
90 	} else {
91 		status = B_BAD_VALUE;
92 		TRACE("Extent:Init(): Bad Block!\n");
93 	}
94 
95 	return status;
96 }
97 
98 
99 ExtentBlockTail*
100 Extent::BlockTail()
101 {
102 	return (ExtentBlockTail*)
103 		(fBlockBuffer + fInode->DirBlockSize() - sizeof(ExtentBlockTail));
104 }
105 
106 
107 uint32
108 Extent::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 
116 ExtentLeafEntry*
117 Extent::BlockFirstLeaf(ExtentBlockTail* tail)
118 {
119 	return (ExtentLeafEntry*)tail - B_BENDIAN_TO_HOST_INT32(tail->count);
120 }
121 
122 
123 bool
124 Extent::BlockType()
125 {
126 	bool status = true;
127 	if (fInode->NoOfBlocks() != 1)
128 		status = false;
129 	if (fInode->Size() != fInode->DirBlockSize())
130 		status = false;
131 	return status;
132 	//TODO: Checks: Fileoffset must be 0 and
133 	//length = directory block size / filesystem block size
134 }
135 
136 
137 int
138 Extent::EntrySize(int len) const
139 {
140 	int entrySize= sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
141 			// uint16 is for the tag
142 	if (fInode->HasFileTypeField())
143 		entrySize += sizeof(uint8);
144 
145 	return (entrySize + 7) & -8;
146 			// rounding off to closest multiple of 8
147 }
148 
149 
150 status_t
151 Extent::GetNext(char* name, size_t* length, xfs_ino_t* ino)
152 {
153 	TRACE("Extend::GetNext\n");
154 	void* entry = (void*)((ExtentDataHeader*)fBlockBuffer + 1);
155 		// This could be an unused entry so we should check
156 
157 	int numberOfEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->count);
158 	TRACE("numberOfEntries:(%d)\n", numberOfEntries);
159 
160 	for (int i = 0; i < numberOfEntries; i++) {
161 		TRACE("i:(%d)\n", i);
162 		ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;
163 
164 		if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
165 			TRACE("Unused entry found\n");
166 			entry = (void*)
167 				((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
168 			continue;
169 		}
170 		ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;
171 
172 		uint16 currentOffset = (char*)dataEntry - fBlockBuffer;
173 		TRACE("GetNext: fOffset:(%d), currentOffset:(%d)\n",
174 			fOffset, currentOffset);
175 
176 		if (fOffset >= currentOffset) {
177 			entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
178 			continue;
179 		}
180 
181 		if (dataEntry->namelen > *length)
182 				return B_BUFFER_OVERFLOW;
183 
184 		fOffset = currentOffset;
185 		memcpy(name, dataEntry->name, dataEntry->namelen);
186 		name[dataEntry->namelen] = '\0';
187 		*length = dataEntry->namelen + 1;
188 		*ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);
189 
190 		TRACE("Entry found. Name: (%s), Length: (%ld),ino: (%ld)\n", name,
191 			*length, *ino);
192 		return B_OK;
193 	}
194 
195 	return B_ENTRY_NOT_FOUND;
196 }
197 
198 
199 status_t
200 Extent::Lookup(const char* name, size_t length, xfs_ino_t* ino)
201 {
202 	TRACE("Extent: Lookup\n");
203 	TRACE("Name: %s\n", name);
204 	uint32 hashValueOfRequest = hashfunction(name, length);
205 	TRACE("Hashval:(%ld)\n", hashValueOfRequest);
206 	ExtentBlockTail* blockTail = BlockTail();
207 	ExtentLeafEntry* leafEntry = BlockFirstLeaf(blockTail);
208 
209 	int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT32(blockTail->count);
210 	int left = 0;
211 	int mid;
212 	int right = numberOfLeafEntries - 1;
213 
214 	/*
215 	* Trying to find the lowerbound of hashValueOfRequest
216 	* This is slightly different from bsearch(), as we want the first
217 	* instance of hashValueOfRequest and not any instance.
218 	*/
219 	while (left < right) {
220 		mid = (left+right)/2;
221 		uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval);
222 		if (hashval >= hashValueOfRequest) {
223 			right = mid;
224 			continue;
225 		}
226 		if (hashval < hashValueOfRequest) {
227 			left = mid+1;
228 		}
229 	}
230 	TRACE("left:(%d), right:(%d)\n", left, right);
231 
232 	while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
233 			== hashValueOfRequest) {
234 
235 		uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
236 		if (address == 0) {
237 			left++;
238 			continue;
239 		}
240 
241 		uint32 offset = GetOffsetFromAddress(address);
242 		TRACE("offset:(%d)\n", offset);
243 		ExtentDataEntry* entry = (ExtentDataEntry*)(fBlockBuffer + offset);
244 
245 		int retVal = strncmp(name, (char*)entry->name, entry->namelen);
246 		if (retVal == 0) {
247 			*ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
248 			TRACE("ino:(%d)\n", *ino);
249 			return B_OK;
250 		}
251 		left++;
252 	}
253 
254 	return B_ENTRY_NOT_FOUND;
255 }
256 
257