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 = CreateDataHeader(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 = CreateLeafHeader(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 = CreateLeafHeader(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 + SizeOfLeafHeader(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 + SizeOfDataHeader(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 + SizeOfDataHeader(fInode)); 268 fOffset = fOffset + SizeOfDataHeader(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 + SizeOfDataHeader(fInode)); 278 fOffset = fOffset + SizeOfDataHeader(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 = CreateLeafHeader(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 mid; 346 int right = numberOfLeafEntries - 1; 347 Volume* volume = fInode->GetVolume(); 348 349 /* 350 * Trying to find the lowerbound of hashValueOfRequest 351 * This is slightly different from bsearch(), as we want the first 352 * instance of hashValueOfRequest and not any instance. 353 */ 354 while (left < right) { 355 mid = (left+right)/2; 356 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 357 if (hashval >= hashValueOfRequest) { 358 right = mid; 359 continue; 360 } 361 if (hashval < hashValueOfRequest) { 362 left = mid+1; 363 } 364 } 365 TRACE("left:(%" B_PRId32 "), right:(%" B_PRId32 ")\n", left, right); 366 367 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 368 == hashValueOfRequest) { 369 370 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 371 if (address == 0) { 372 left++; 373 continue; 374 } 375 376 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 377 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 378 379 TRACE("DataBlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset); 380 if (dataBlockNumber != fCurBlockNumber) { 381 fCurBlockNumber = dataBlockNumber; 382 SearchAndFillDataMap(dataBlockNumber); 383 status = FillBuffer(DATA, fDataBuffer, 384 dataBlockNumber - fDataMap->br_startoff); 385 if (status != B_OK) 386 return status; 387 } 388 389 TRACE("offset:(%" B_PRIu32 ")\n", offset); 390 ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset); 391 392 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 393 if (retVal == 0) { 394 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 395 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 396 return B_OK; 397 } 398 left++; 399 } 400 401 delete leafHeader; 402 403 return B_ENTRY_NOT_FOUND; 404 } 405 406 407 ExtentLeafHeader::~ExtentLeafHeader() 408 { 409 } 410 411 412 /* 413 First see which type of directory we reading then 414 return magic number as per Inode Version. 415 */ 416 uint32 417 ExtentLeafHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode) 418 { 419 if (WhichDirectory == XFS_LEAF) { 420 if (inode->Version() == 1 || inode->Version() == 2) 421 return V4_LEAF_HEADER_MAGIC; 422 else 423 return V5_LEAF_HEADER_MAGIC; 424 } else { 425 if (inode->Version() == 1 || inode->Version() == 2) 426 return XFS_DIR2_LEAFN_MAGIC; 427 else 428 return XFS_DIR3_LEAFN_MAGIC; 429 } 430 } 431 432 433 uint32 434 ExtentLeafHeader::CRCOffset() 435 { 436 return XFS_LEAF_CRC_OFF - XFS_LEAF_V5_VPTR_OFF; 437 } 438 439 440 void 441 ExtentLeafHeaderV4::SwapEndian() 442 { 443 info.forw = B_BENDIAN_TO_HOST_INT32(info.forw); 444 info.back = B_BENDIAN_TO_HOST_INT32(info.back); 445 info.magic = B_BENDIAN_TO_HOST_INT16(info.magic); 446 info.pad = B_BENDIAN_TO_HOST_INT16(info.pad); 447 count = B_BENDIAN_TO_HOST_INT16(count); 448 stale = B_BENDIAN_TO_HOST_INT16(stale); 449 } 450 451 452 ExtentLeafHeaderV4::ExtentLeafHeaderV4(const char* buffer) 453 { 454 uint32 offset = 0; 455 456 info = *(BlockInfo*)(buffer + offset); 457 offset += sizeof(BlockInfo); 458 459 count = *(uint16*)(buffer + offset); 460 offset += sizeof(uint16); 461 462 stale = *(uint16*)(buffer + offset); 463 464 SwapEndian(); 465 } 466 467 468 ExtentLeafHeaderV4::~ExtentLeafHeaderV4() 469 { 470 } 471 472 473 uint16 474 ExtentLeafHeaderV4::Magic() 475 { 476 return info.magic; 477 } 478 479 480 uint64 481 ExtentLeafHeaderV4::Blockno() 482 { 483 return B_BAD_VALUE; 484 } 485 486 487 uint64 488 ExtentLeafHeaderV4::Lsn() 489 { 490 return B_BAD_VALUE; 491 } 492 493 494 uint64 495 ExtentLeafHeaderV4::Owner() 496 { 497 return B_BAD_VALUE; 498 } 499 500 501 uuid_t* 502 ExtentLeafHeaderV4::Uuid() 503 { 504 return NULL; 505 } 506 507 508 uint16 509 ExtentLeafHeaderV4::Count() 510 { 511 return count; 512 } 513 514 515 uint32 516 ExtentLeafHeaderV4::Forw() 517 { 518 return info.forw; 519 } 520 521 522 void 523 ExtentLeafHeaderV5::SwapEndian() 524 { 525 info.forw = B_BENDIAN_TO_HOST_INT32(info.forw); 526 info.back = B_BENDIAN_TO_HOST_INT32(info.back); 527 info.magic = B_BENDIAN_TO_HOST_INT16(info.magic); 528 info.pad = B_BENDIAN_TO_HOST_INT16(info.pad); 529 info.blkno = B_BENDIAN_TO_HOST_INT64(info.blkno); 530 info.lsn = B_BENDIAN_TO_HOST_INT64(info.lsn); 531 info.owner = B_BENDIAN_TO_HOST_INT64(info.owner); 532 count = B_BENDIAN_TO_HOST_INT16(count); 533 stale = B_BENDIAN_TO_HOST_INT16(stale); 534 pad = B_BENDIAN_TO_HOST_INT32(pad); 535 } 536 537 538 ExtentLeafHeaderV5::ExtentLeafHeaderV5(const char* buffer) 539 { 540 uint32 offset = 0; 541 542 info = *(BlockInfoV5*)(buffer + offset); 543 offset += sizeof(BlockInfoV5); 544 545 count = *(uint16*)(buffer + offset); 546 offset += sizeof(uint16); 547 548 stale = *(uint16*)(buffer + offset); 549 offset += sizeof(uint16); 550 551 pad = *(uint32*)(buffer + offset); 552 553 SwapEndian(); 554 } 555 556 557 ExtentLeafHeaderV5::~ExtentLeafHeaderV5() 558 { 559 } 560 561 562 uint16 563 ExtentLeafHeaderV5::Magic() 564 { 565 return info.magic; 566 } 567 568 569 uint64 570 ExtentLeafHeaderV5::Blockno() 571 { 572 return info.blkno; 573 } 574 575 576 uint64 577 ExtentLeafHeaderV5::Lsn() 578 { 579 return info.lsn; 580 } 581 582 583 uint64 584 ExtentLeafHeaderV5::Owner() 585 { 586 return info.owner; 587 } 588 589 590 uuid_t* 591 ExtentLeafHeaderV5::Uuid() 592 { 593 return &info.uuid; 594 } 595 596 597 uint16 598 ExtentLeafHeaderV5::Count() 599 { 600 return count; 601 } 602 603 604 uint32 605 ExtentLeafHeaderV5::Forw() 606 { 607 return info.forw; 608 } 609 610 611 //Function to get V4 or V5 leaf header instance 612 ExtentLeafHeader* 613 CreateLeafHeader(Inode* inode, const char* buffer) 614 { 615 if (inode->Version() == 1 || inode->Version() == 2) { 616 ExtentLeafHeaderV4* header = new (std::nothrow) ExtentLeafHeaderV4(buffer); 617 return header; 618 } else { 619 ExtentLeafHeaderV5* header = new (std::nothrow) ExtentLeafHeaderV5(buffer); 620 return header; 621 } 622 } 623 624 625 /* 626 This Function returns Actual size of leaf header 627 in all forms of directory. 628 Never use sizeof() operator because we now have 629 vtable as well and it will give wrong results 630 */ 631 uint32 632 SizeOfLeafHeader(Inode* inode) 633 { 634 if (inode->Version() == 1 || inode->Version() == 2) 635 return sizeof(ExtentLeafHeaderV4) - XFS_LEAF_V4_VPTR_OFF; 636 else 637 return sizeof(ExtentLeafHeaderV5) - XFS_LEAF_V5_VPTR_OFF; 638 } 639