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
Extent(Inode * inode)13 Extent::Extent(Inode* inode)
14 :
15 fInode(inode),
16 fOffset(0)
17 {
18 }
19
20
~Extent()21 Extent::~Extent()
22 {
23 }
24
25
26 void
FillMapEntry(void * pointerToMap)27 Extent::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
44 status_t
FillBlockBuffer()45 Extent::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
68 status_t
Init()69 Extent::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
99 ExtentBlockTail*
BlockTail()100 Extent::BlockTail()
101 {
102 return (ExtentBlockTail*)
103 (fBlockBuffer + fInode->DirBlockSize() - sizeof(ExtentBlockTail));
104 }
105
106
107 uint32
GetOffsetFromAddress(uint32 address)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*
BlockFirstLeaf(ExtentBlockTail * tail)117 Extent::BlockFirstLeaf(ExtentBlockTail* tail)
118 {
119 return (ExtentLeafEntry*)tail - B_BENDIAN_TO_HOST_INT32(tail->count);
120 }
121
122
123 bool
IsBlockType()124 Extent::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
139 int
EntrySize(int len) const140 Extent::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
152 status_t
GetNext(char * name,size_t * length,xfs_ino_t * ino)153 Extent::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
206 status_t
Lookup(const char * name,size_t length,xfs_ino_t * ino)207 Extent::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
~ExtentDataHeader()248 ExtentDataHeader::~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 */
257 uint32
ExpectedMagic(int8 WhichDirectory,Inode * inode)258 ExtentDataHeader::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
274 uint32
CRCOffset()275 ExtentDataHeader::CRCOffset()
276 {
277 return offsetof(ExtentDataHeaderV5::OnDiskData, crc);
278 }
279
280
281 ExtentDataHeader*
Create(Inode * inode,const char * buffer)282 ExtentDataHeader::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 */
300 uint32
Size(Inode * inode)301 ExtentDataHeader::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
310 void
_SwapEndian()311 ExtentDataHeaderV4::_SwapEndian()
312 {
313 fData.magic = (B_BENDIAN_TO_HOST_INT32(fData.magic));
314 }
315
316
ExtentDataHeaderV4(const char * buffer)317 ExtentDataHeaderV4::ExtentDataHeaderV4(const char* buffer)
318 {
319 memcpy(&fData, buffer, sizeof(fData));
320 _SwapEndian();
321 }
322
323
~ExtentDataHeaderV4()324 ExtentDataHeaderV4::~ExtentDataHeaderV4()
325 {
326 }
327
328
329 uint32
Magic()330 ExtentDataHeaderV4::Magic()
331 {
332 return fData.magic;
333 }
334
335
336 uint64
Blockno()337 ExtentDataHeaderV4::Blockno()
338 {
339 return B_BAD_VALUE;
340 }
341
342
343 uint64
Lsn()344 ExtentDataHeaderV4::Lsn()
345 {
346 return B_BAD_VALUE;
347 }
348
349
350 uint64
Owner()351 ExtentDataHeaderV4::Owner()
352 {
353 return B_BAD_VALUE;
354 }
355
356
357 const uuid_t&
Uuid()358 ExtentDataHeaderV4::Uuid()
359 {
360 static uuid_t nullUuid;
361 return nullUuid;
362 }
363
364
365 void
_SwapEndian()366 ExtentDataHeaderV5::_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
ExtentDataHeaderV5(const char * buffer)376 ExtentDataHeaderV5::ExtentDataHeaderV5(const char* buffer)
377 {
378 memcpy(&fData, buffer, sizeof(fData));
379 _SwapEndian();
380 }
381
382
~ExtentDataHeaderV5()383 ExtentDataHeaderV5::~ExtentDataHeaderV5()
384 {
385 }
386
387
388 uint32
Magic()389 ExtentDataHeaderV5::Magic()
390 {
391 return fData.magic;
392 }
393
394
395 uint64
Blockno()396 ExtentDataHeaderV5::Blockno()
397 {
398 return fData.blkno;
399 }
400
401
402 uint64
Lsn()403 ExtentDataHeaderV5::Lsn()
404 {
405 return fData.lsn;
406 }
407
408
409 uint64
Owner()410 ExtentDataHeaderV5::Owner()
411 {
412 return fData.owner;
413 }
414
415
416 const uuid_t&
Uuid()417 ExtentDataHeaderV5::Uuid()
418 {
419 return fData.uuid;
420 }
421