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 13 LeafDirectory::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 26 LeafDirectory::~LeafDirectory() 27 { 28 delete fDataMap; 29 delete fLeafMap; 30 delete fDataBuffer; 31 delete fLeafBuffer; 32 } 33 34 35 status_t 36 LeafDirectory::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 81 bool 82 LeafDirectory::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 108 void 109 LeafDirectory::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 130 status_t 131 LeafDirectory::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 175 uint32 176 LeafDirectory::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 184 ExtentLeafEntry* 185 LeafDirectory::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 198 int 199 LeafDirectory::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 211 void 212 LeafDirectory::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 226 status_t 227 LeafDirectory::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 320 status_t 321 LeafDirectory::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 390 ExtentLeafHeader::~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 */ 399 uint32 400 ExtentLeafHeader::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 416 uint32 417 ExtentLeafHeader::CRCOffset() 418 { 419 return offsetof(ExtentLeafHeaderV5::OnDiskData, info.crc); 420 } 421 422 423 ExtentLeafHeader* 424 ExtentLeafHeader::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 */ 442 uint32 443 ExtentLeafHeader::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 452 void 453 ExtentLeafHeaderV4::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 464 ExtentLeafHeaderV4::ExtentLeafHeaderV4(const char* buffer) 465 { 466 memcpy(&fData, buffer, sizeof(fData)); 467 SwapEndian(); 468 } 469 470 471 ExtentLeafHeaderV4::~ExtentLeafHeaderV4() 472 { 473 } 474 475 476 uint16 477 ExtentLeafHeaderV4::Magic() 478 { 479 return fData.info.magic; 480 } 481 482 483 uint64 484 ExtentLeafHeaderV4::Blockno() 485 { 486 return B_BAD_VALUE; 487 } 488 489 490 uint64 491 ExtentLeafHeaderV4::Lsn() 492 { 493 return B_BAD_VALUE; 494 } 495 496 497 uint64 498 ExtentLeafHeaderV4::Owner() 499 { 500 return B_BAD_VALUE; 501 } 502 503 504 const uuid_t& 505 ExtentLeafHeaderV4::Uuid() 506 { 507 static uuid_t nullUuid = {0}; 508 return nullUuid; 509 } 510 511 512 uint16 513 ExtentLeafHeaderV4::Count() 514 { 515 return fData.count; 516 } 517 518 519 uint32 520 ExtentLeafHeaderV4::Forw() 521 { 522 return fData.info.forw; 523 } 524 525 526 void 527 ExtentLeafHeaderV5::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 542 ExtentLeafHeaderV5::ExtentLeafHeaderV5(const char* buffer) 543 { 544 memcpy(&fData, buffer, sizeof(fData)); 545 SwapEndian(); 546 } 547 548 549 ExtentLeafHeaderV5::~ExtentLeafHeaderV5() 550 { 551 } 552 553 554 uint16 555 ExtentLeafHeaderV5::Magic() 556 { 557 return fData.info.magic; 558 } 559 560 561 uint64 562 ExtentLeafHeaderV5::Blockno() 563 { 564 return fData.info.blkno; 565 } 566 567 568 uint64 569 ExtentLeafHeaderV5::Lsn() 570 { 571 return fData.info.lsn; 572 } 573 574 575 uint64 576 ExtentLeafHeaderV5::Owner() 577 { 578 return fData.info.owner; 579 } 580 581 582 const uuid_t& 583 ExtentLeafHeaderV5::Uuid() 584 { 585 return fData.info.uuid; 586 } 587 588 589 uint16 590 ExtentLeafHeaderV5::Count() 591 { 592 return fData.count; 593 } 594 595 596 uint32 597 ExtentLeafHeaderV5::Forw() 598 { 599 return fData.info.forw; 600 } 601