xref: /haiku/src/add-ons/kernel/file_systems/xfs/Node.cpp (revision 6f80a9801fedbe7355c4360bd204ba746ec3ec2d)
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 
10 NodeDirectory::NodeDirectory(Inode* inode)
11 	:
12 	fInode(inode),
13 	fDataMap(NULL),
14 	fLeafMap(NULL),
15 	fOffset(0),
16 	fDataBuffer(NULL),
17 	fLeafBuffer(NULL),
18 	fCurBlockNumber(-1)
19 {
20 }
21 
22 
23 NodeDirectory::~NodeDirectory()
24 {
25 	delete fDataMap;
26 	delete fLeafMap;
27 	delete fDataBuffer;
28 	delete fLeafBuffer;
29 }
30 
31 
32 status_t
33 NodeDirectory::Init()
34 {
35 	fLeafMap = new(std::nothrow) ExtentMapEntry;
36 	if (fLeafMap == NULL)
37 		return B_NO_MEMORY;
38 
39 	fDataMap = new(std::nothrow) ExtentMapEntry;
40 	if (fDataMap == NULL)
41 		return B_NO_MEMORY;
42 
43 	FillMapEntry(fInode->DataExtentsCount() - 3, fLeafMap);
44 	fCurLeafMapNumber = 1;
45 	FillMapEntry(0, fDataMap);
46 	return B_OK;
47 }
48 
49 
50 bool
51 NodeDirectory::IsNodeType()
52 {
53 	if (fCurLeafMapNumber != 1) {
54 		FillMapEntry(fInode->DataExtentsCount() - 3, fLeafMap);
55 		fCurLeafMapNumber = 1;
56 	}
57 	return fLeafMap->br_startoff
58 		== LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog());
59 }
60 
61 
62 void
63 NodeDirectory::FillMapEntry(int num, ExtentMapEntry* fMap)
64 {
65 	void* directoryFork = DIR_DFORK_PTR(fInode->Buffer());
66 	void* pointerToMap = (void*)((char*)directoryFork + num * EXTENT_SIZE);
67 	uint64 firstHalf = *((uint64*)pointerToMap);
68 	uint64 secondHalf = *((uint64*)pointerToMap + 1);
69 		//dividing the 128 bits into 2 parts.
70 
71 	firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
72 	secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
73 	fMap->br_state = firstHalf >> 63;
74 	fMap->br_startoff = (firstHalf & MASK(63)) >> 9;
75 	fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
76 	fMap->br_blockcount = secondHalf & MASK(21);
77 	TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
78 		"blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock,
79 		fMap->br_blockcount, fMap->br_state);
80 }
81 
82 
83 status_t
84 NodeDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur)
85 {
86 	TRACE("FILLBUFFER\n");
87 	ExtentMapEntry* map;
88 	if (type == DATA)
89 		map = fDataMap;
90 	else if (type == LEAF)
91 		map = fLeafMap;
92 	else
93 		return B_BAD_VALUE;
94 
95 	if (map->br_state != 0)
96 		return B_BAD_VALUE;
97 
98 	ssize_t len = fInode->DirBlockSize();
99 	if (blockBuffer == NULL) {
100 		blockBuffer = new(std::nothrow) char[len];
101 		if (blockBuffer == NULL)
102 			return B_NO_MEMORY;
103 	}
104 
105 	xfs_daddr_t readPos = fInode->FileSystemBlockToAddr(map->br_startblock
106 		+ howManyBlocksFurthur);
107 
108 	if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len)
109 		!= len) {
110 		ERROR("NodeDirectory::FillBlockBuffer(): IO Error");
111 		return B_IO_ERROR;
112 	}
113 
114 	if (type == DATA) {
115 		fDataBuffer = blockBuffer;
116 		ExtentDataHeader* header = (ExtentDataHeader*) fDataBuffer;
117 		if (B_BENDIAN_TO_HOST_INT32(header->magic) == DATA_HEADER_MAGIC) {
118 			TRACE("DATA BLOCK VALID\n");
119 		} else {
120 			TRACE("DATA BLOCK INVALID\n");
121 			return B_BAD_VALUE;
122 		}
123 	} else if (type == LEAF) {
124 		fLeafBuffer = blockBuffer;
125 		//TODO : see if we can do something with this header
126 		//ExtentLeafHeader* header = (ExtentLeafHeader*) fLeafBuffer;
127 	}
128 
129 	return B_OK;
130 }
131 
132 
133 uint32
134 NodeDirectory::GetOffsetFromAddress(uint32 address)
135 {
136 	address = address * 8;
137 		// block offset in eight bytes, hence multiple with 8
138 	return address & (fInode->DirBlockSize() - 1);
139 }
140 
141 
142 uint32
143 NodeDirectory::FindHashInNode(uint32 hashVal)
144 {
145 	NodeHeader* header = (NodeHeader*)(void*)(fLeafBuffer);
146 	NodeEntry* entry = (NodeEntry*)(void*)(fLeafBuffer + sizeof(NodeHeader));
147 	int count = B_BENDIAN_TO_HOST_INT16(header->count);
148 	if ((NodeEntry*)(void*)fLeafBuffer + fInode->DirBlockSize()
149 		< &entry[count]) {
150 			return B_BAD_VALUE;
151 	}
152 
153 	for (int i = 0; i < count; i++) {
154 		if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval))
155 			return B_BENDIAN_TO_HOST_INT32(entry[i].before);
156 	}
157 
158 	return 1;
159 }
160 
161 
162 int
163 NodeDirectory::EntrySize(int len) const
164 {
165 	int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
166 			// uint16 is for the tag
167 	if (fInode->HasFileTypeField())
168 		entrySize += sizeof(uint8);
169 
170 	return ROUNDUP(entrySize, 8);
171 			// rounding off to closest multiple of 8
172 }
173 
174 
175 void
176 NodeDirectory::SearchAndFillDataMap(uint64 blockNo)
177 {
178 	int len = fInode->DataExtentsCount();
179 
180 	for (int i = 0; i < len - 3; i++) {
181 		FillMapEntry(i, fDataMap);
182 		if (fDataMap->br_startoff <= blockNo
183 			&& (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1))
184 			// Map found
185 			return;
186 	}
187 }
188 
189 
190 status_t
191 NodeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino)
192 {
193 	TRACE("NodeDirectory::GetNext\n");
194 	status_t status;
195 
196 	if (fDataBuffer == NULL) {
197 		status = FillBuffer(DATA, fDataBuffer, 0);
198 		if (status != B_OK)
199 			return status;
200 	}
201 
202 	Volume* volume = fInode->GetVolume();
203 	void* entry = (void*)((ExtentDataHeader*)fDataBuffer + 1);
204 		// This could be an unused entry so we should check
205 
206 	uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
207 	if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) {
208 		entry = (void*)(fDataBuffer
209 			+ BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode));
210 		// This gets us a little faster to the next entry
211 	}
212 
213 	uint32 curDirectorySize = fInode->Size();
214 
215 	while (fOffset != curDirectorySize) {
216 		blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
217 
218 		TRACE("fOffset:(%" B_PRIu32 "), blockNoFromAddress:(%" B_PRIu32 ")\n",
219 			fOffset, blockNoFromAddress);
220 		if (fCurBlockNumber != blockNoFromAddress
221 			&& blockNoFromAddress > fDataMap->br_startoff
222 			&& blockNoFromAddress
223 				<= fDataMap->br_startoff + fDataMap->br_blockcount - 1) {
224 			// When the block is mapped in the same data
225 			// map entry but is not the first block
226 			status = FillBuffer(DATA, fDataBuffer,
227 				blockNoFromAddress - fDataMap->br_startoff);
228 			if (status != B_OK)
229 				return status;
230 			entry = (void*)((ExtentDataHeader*)fDataBuffer + 1);
231 			fOffset = fOffset + sizeof(ExtentDataHeader);
232 			fCurBlockNumber = blockNoFromAddress;
233 		} else if (fCurBlockNumber != blockNoFromAddress) {
234 			// When the block isn't mapped in the current data map entry
235 			SearchAndFillDataMap(blockNoFromAddress);
236 			status = FillBuffer(DATA, fDataBuffer,
237 				blockNoFromAddress - fDataMap->br_startoff);
238 			if (status != B_OK)
239 				return status;
240 			entry = (void*)((ExtentDataHeader*)fDataBuffer + 1);
241 			fOffset = fOffset + sizeof(ExtentDataHeader);
242 			fCurBlockNumber = blockNoFromAddress;
243 		}
244 
245 		ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;
246 
247 		if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
248 			TRACE("Unused entry found\n");
249 			fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
250 			entry = (void*)
251 				((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
252 			continue;
253 		}
254 		ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;
255 
256 		uint16 currentOffset = (char*)dataEntry - fDataBuffer;
257 		TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n",
258 			BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset);
259 
260 		if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) {
261 			entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
262 			continue;
263 		}
264 
265 		if ((size_t)(dataEntry->namelen) >= *length)
266 			return B_BUFFER_OVERFLOW;
267 
268 		fOffset = fOffset + EntrySize(dataEntry->namelen);
269 		memcpy(name, dataEntry->name, dataEntry->namelen);
270 		name[dataEntry->namelen] = '\0';
271 		*length = dataEntry->namelen + 1;
272 		*ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);
273 
274 		TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n",
275 			name,*length, *ino);
276 		return B_OK;
277 	}
278 
279 	return B_ENTRY_NOT_FOUND;
280 }
281 
282 
283 status_t
284 NodeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino)
285 {
286 	TRACE("NodeDirectory: Lookup\n");
287 	TRACE("Name: %s\n", name);
288 	uint32 hashValueOfRequest = hashfunction(name, length);
289 	TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);
290 
291 	status_t status;
292 	if (fCurLeafBufferNumber != 1) {
293 		if (fCurLeafMapNumber != 1) {
294 			FillMapEntry(fInode->DataExtentsCount() - 3, fLeafMap);
295 			fCurLeafMapNumber = 1;
296 		}
297 		status = FillBuffer(LEAF, fLeafBuffer, 0);
298 		if (status != B_OK)
299 			return status;
300 		fCurLeafBufferNumber = 1;
301 	}
302 	/* Leaf now has the nodes. */
303 	uint32 rightMapOffset = FindHashInNode(hashValueOfRequest);
304 	if (rightMapOffset == 1){
305 		TRACE("Not in this directory.\n");
306 		return B_ENTRY_NOT_FOUND;
307 	}
308 
309 	TRACE("rightMapOffset:(%" B_PRIu32 ")\n", rightMapOffset);
310 
311 	FillMapEntry(fInode->DataExtentsCount() - 2, fLeafMap);
312 	fCurLeafMapNumber = 2;
313 	status = FillBuffer(LEAF, fLeafBuffer,
314 		rightMapOffset - fLeafMap->br_startoff);
315 	if (status != B_OK)
316 		return status;
317 	fCurLeafBufferNumber = 2;
318 
319 	ExtentLeafHeader* leafHeader = (ExtentLeafHeader*)(void*)fLeafBuffer;
320 	ExtentLeafEntry* leafEntry =
321 		(ExtentLeafEntry*)(void*)(fLeafBuffer + sizeof(ExtentLeafHeader));
322 	if (leafEntry == NULL)
323 		return B_NO_MEMORY;
324 
325 	int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT16(leafHeader->count);
326 	TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries);
327 	int left = 0;
328 	int mid;
329 	int right = numberOfLeafEntries - 1;
330 	Volume* volume = fInode->GetVolume();
331 
332 	/*
333 	* Trying to find the lowerbound of hashValueOfRequest
334 	* This is slightly different from bsearch(), as we want the first
335 	* instance of hashValueOfRequest and not any instance.
336 	*/
337 	while (left < right) {
338 		mid = (left + right) / 2;
339 		uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval);
340 		if (hashval >= hashValueOfRequest) {
341 			right = mid;
342 			continue;
343 		}
344 		if (hashval < hashValueOfRequest) {
345 			left = mid + 1;
346 		}
347 	}
348 	TRACE("left:(%" B_PRId32 "), right:(%" B_PRId32 ")\n", left, right);
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",
363 			dataBlockNumber, offset);
364 		if (dataBlockNumber != fCurBlockNumber) {
365 			fCurBlockNumber = dataBlockNumber;
366 			SearchAndFillDataMap(dataBlockNumber);
367 			status = FillBuffer(DATA, fDataBuffer,
368 				dataBlockNumber - fDataMap->br_startoff);
369 			if (status != B_OK)
370 				return B_OK;
371 		}
372 
373 		TRACE("offset:(%" B_PRIu32 ")\n", offset);
374 		ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset);
375 
376 		int retVal = strncmp(name, (char*)entry->name, entry->namelen);
377 		if (retVal == 0) {
378 			*ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
379 			TRACE("ino:(%" B_PRIu64 ")\n", *ino);
380 			return B_OK;
381 		}
382 		left++;
383 	}
384 
385 	return B_ENTRY_NOT_FOUND;
386 }
387