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 XFS_LEAF_CRC_OFF - XFS_LEAF_V5_VPTR_OFF; 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) - XFS_LEAF_V4_VPTR_OFF; 447 else 448 return sizeof(ExtentLeafHeaderV5) - XFS_LEAF_V5_VPTR_OFF; 449 } 450 451 452 void 453 ExtentLeafHeaderV4::SwapEndian() 454 { 455 info.forw = B_BENDIAN_TO_HOST_INT32(info.forw); 456 info.back = B_BENDIAN_TO_HOST_INT32(info.back); 457 info.magic = B_BENDIAN_TO_HOST_INT16(info.magic); 458 info.pad = B_BENDIAN_TO_HOST_INT16(info.pad); 459 count = B_BENDIAN_TO_HOST_INT16(count); 460 stale = B_BENDIAN_TO_HOST_INT16(stale); 461 } 462 463 464 ExtentLeafHeaderV4::ExtentLeafHeaderV4(const char* buffer) 465 { 466 uint32 offset = 0; 467 468 info = *(BlockInfo*)(buffer + offset); 469 offset += sizeof(BlockInfo); 470 471 count = *(uint16*)(buffer + offset); 472 offset += sizeof(uint16); 473 474 stale = *(uint16*)(buffer + offset); 475 476 SwapEndian(); 477 } 478 479 480 ExtentLeafHeaderV4::~ExtentLeafHeaderV4() 481 { 482 } 483 484 485 uint16 486 ExtentLeafHeaderV4::Magic() 487 { 488 return info.magic; 489 } 490 491 492 uint64 493 ExtentLeafHeaderV4::Blockno() 494 { 495 return B_BAD_VALUE; 496 } 497 498 499 uint64 500 ExtentLeafHeaderV4::Lsn() 501 { 502 return B_BAD_VALUE; 503 } 504 505 506 uint64 507 ExtentLeafHeaderV4::Owner() 508 { 509 return B_BAD_VALUE; 510 } 511 512 513 uuid_t* 514 ExtentLeafHeaderV4::Uuid() 515 { 516 return NULL; 517 } 518 519 520 uint16 521 ExtentLeafHeaderV4::Count() 522 { 523 return count; 524 } 525 526 527 uint32 528 ExtentLeafHeaderV4::Forw() 529 { 530 return info.forw; 531 } 532 533 534 void 535 ExtentLeafHeaderV5::SwapEndian() 536 { 537 info.forw = B_BENDIAN_TO_HOST_INT32(info.forw); 538 info.back = B_BENDIAN_TO_HOST_INT32(info.back); 539 info.magic = B_BENDIAN_TO_HOST_INT16(info.magic); 540 info.pad = B_BENDIAN_TO_HOST_INT16(info.pad); 541 info.blkno = B_BENDIAN_TO_HOST_INT64(info.blkno); 542 info.lsn = B_BENDIAN_TO_HOST_INT64(info.lsn); 543 info.owner = B_BENDIAN_TO_HOST_INT64(info.owner); 544 count = B_BENDIAN_TO_HOST_INT16(count); 545 stale = B_BENDIAN_TO_HOST_INT16(stale); 546 pad = B_BENDIAN_TO_HOST_INT32(pad); 547 } 548 549 550 ExtentLeafHeaderV5::ExtentLeafHeaderV5(const char* buffer) 551 { 552 uint32 offset = 0; 553 554 info = *(BlockInfoV5*)(buffer + offset); 555 offset += sizeof(BlockInfoV5); 556 557 count = *(uint16*)(buffer + offset); 558 offset += sizeof(uint16); 559 560 stale = *(uint16*)(buffer + offset); 561 offset += sizeof(uint16); 562 563 pad = *(uint32*)(buffer + offset); 564 565 SwapEndian(); 566 } 567 568 569 ExtentLeafHeaderV5::~ExtentLeafHeaderV5() 570 { 571 } 572 573 574 uint16 575 ExtentLeafHeaderV5::Magic() 576 { 577 return info.magic; 578 } 579 580 581 uint64 582 ExtentLeafHeaderV5::Blockno() 583 { 584 return info.blkno; 585 } 586 587 588 uint64 589 ExtentLeafHeaderV5::Lsn() 590 { 591 return info.lsn; 592 } 593 594 595 uint64 596 ExtentLeafHeaderV5::Owner() 597 { 598 return info.owner; 599 } 600 601 602 uuid_t* 603 ExtentLeafHeaderV5::Uuid() 604 { 605 return &info.uuid; 606 } 607 608 609 uint16 610 ExtentLeafHeaderV5::Count() 611 { 612 return count; 613 } 614 615 616 uint32 617 ExtentLeafHeaderV5::Forw() 618 { 619 return info.forw; 620 }