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 #include "VerifyHeader.h" 10 11 12 NodeDirectory::NodeDirectory(Inode* inode) 13 : 14 fInode(inode), 15 fDataMap(NULL), 16 fLeafMap(NULL), 17 fOffset(0), 18 fDataBuffer(NULL), 19 fLeafBuffer(NULL), 20 fCurBlockNumber(-1) 21 { 22 fFirstLeafMapIndex = FirstLeafMapIndex(); 23 } 24 25 26 NodeDirectory::~NodeDirectory() 27 { 28 delete fDataMap; 29 delete fLeafMap; 30 delete fDataBuffer; 31 delete fLeafBuffer; 32 } 33 34 35 xfs_extnum_t 36 NodeDirectory::FirstLeafMapIndex() 37 { 38 int len = fInode->DataExtentsCount(); 39 40 for (int i = 0; i < len; i++) { 41 void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()); 42 void* pointerToMap = (void*)((char*)directoryFork + i * EXTENT_SIZE); 43 44 uint64 startoff = *((uint64*)pointerToMap); 45 startoff = B_BENDIAN_TO_HOST_INT64(startoff); 46 startoff = (startoff & MASK(63)) >> 9; 47 48 // First Leaf Map found 49 if (startoff == LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog())) 50 return i; 51 } 52 53 // No Leaf 54 return -1; 55 } 56 57 58 status_t 59 NodeDirectory::Init() 60 { 61 TRACE("Node directory : init()\n"); 62 fLeafMap = new(std::nothrow) ExtentMapEntry; 63 if (fLeafMap == NULL) 64 return B_NO_MEMORY; 65 66 fDataMap = new(std::nothrow) ExtentMapEntry; 67 if (fDataMap == NULL) 68 return B_NO_MEMORY; 69 70 FillMapEntry(fFirstLeafMapIndex, fLeafMap); 71 fCurLeafMapNumber = 1; 72 FillMapEntry(0, fDataMap); 73 return B_OK; 74 } 75 76 77 bool 78 NodeDirectory::IsNodeType() 79 { 80 if (fFirstLeafMapIndex == -1) 81 return false; 82 return true; 83 } 84 85 86 void 87 NodeDirectory::FillMapEntry(int num, ExtentMapEntry* fMap) 88 { 89 void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()); 90 void* pointerToMap = (void*)((char*)directoryFork + num * EXTENT_SIZE); 91 uint64 firstHalf = *((uint64*)pointerToMap); 92 uint64 secondHalf = *((uint64*)pointerToMap + 1); 93 //dividing the 128 bits into 2 parts. 94 95 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 96 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 97 fMap->br_state = firstHalf >> 63; 98 fMap->br_startoff = (firstHalf & MASK(63)) >> 9; 99 fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 100 fMap->br_blockcount = secondHalf & MASK(21); 101 TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 ")," 102 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock, 103 fMap->br_blockcount, fMap->br_state); 104 } 105 106 107 status_t 108 NodeDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur) 109 { 110 TRACE("FILLBUFFER\n"); 111 ExtentMapEntry* map; 112 if (type == DATA) 113 map = fDataMap; 114 else if (type == LEAF) 115 map = fLeafMap; 116 else 117 return B_BAD_VALUE; 118 119 if (map->br_state != 0) 120 return B_BAD_VALUE; 121 122 ssize_t len = fInode->DirBlockSize(); 123 if (blockBuffer == NULL) { 124 blockBuffer = new(std::nothrow) char[len]; 125 if (blockBuffer == NULL) 126 return B_NO_MEMORY; 127 } 128 129 xfs_daddr_t readPos = fInode->FileSystemBlockToAddr(map->br_startblock 130 + howManyBlocksFurthur); 131 132 if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len) 133 != len) { 134 ERROR("NodeDirectory::FillBlockBuffer(): IO Error"); 135 return B_IO_ERROR; 136 } 137 138 if (type == DATA) { 139 fDataBuffer = blockBuffer; 140 ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fDataBuffer); 141 if(header == NULL) 142 return B_NO_MEMORY; 143 if (!VerifyHeader<ExtentDataHeader>(header, fDataBuffer, fInode, 144 howManyBlocksFurthur, fDataMap, XFS_NODE)) { 145 ERROR("DATA BLOCK INVALID\n"); 146 delete header; 147 return B_BAD_VALUE; 148 } 149 delete header; 150 151 } else if (type == LEAF) { 152 fLeafBuffer = blockBuffer; 153 /* 154 This could be leaf or node block perform check for both 155 based on magic number found. 156 */ 157 ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fLeafBuffer); 158 if (leaf == NULL) 159 return B_NO_MEMORY; 160 161 if ((leaf->Magic() == XFS_DIR2_LEAFN_MAGIC 162 || leaf->Magic() == XFS_DIR3_LEAFN_MAGIC) 163 && !VerifyHeader<ExtentLeafHeader>(leaf, fLeafBuffer, fInode, 164 howManyBlocksFurthur, fLeafMap, XFS_NODE)) { 165 TRACE("Leaf block invalid"); 166 delete leaf; 167 return B_BAD_VALUE; 168 } 169 delete leaf; 170 leaf = NULL; 171 172 NodeHeader* node = NodeHeader::Create(fInode, fLeafBuffer); 173 if (node == NULL) 174 return B_NO_MEMORY; 175 176 if ((node->Magic() == XFS_DA_NODE_MAGIC 177 || node->Magic() == XFS_DA3_NODE_MAGIC) 178 && !VerifyHeader<NodeHeader>(node, fLeafBuffer, fInode, 179 howManyBlocksFurthur, fLeafMap, XFS_NODE)) { 180 TRACE("Node block invalid"); 181 delete node; 182 return B_BAD_VALUE; 183 } 184 delete node; 185 } 186 187 return B_OK; 188 } 189 190 191 uint32 192 NodeDirectory::GetOffsetFromAddress(uint32 address) 193 { 194 address = address * 8; 195 // block offset in eight bytes, hence multiple with 8 196 return address & (fInode->DirBlockSize() - 1); 197 } 198 199 200 status_t 201 NodeDirectory::FindHashInNode(uint32 hashVal, uint32* rightMapOffset) 202 { 203 NodeHeader* header = NodeHeader::Create(fInode, fLeafBuffer); 204 if (header == NULL) 205 return B_NO_MEMORY; 206 207 NodeEntry* entry = (NodeEntry*)(void*)(fLeafBuffer + NodeHeader::Size(fInode)); 208 int count = header->Count(); 209 delete header; 210 if ((NodeEntry*)(void*)fLeafBuffer + fInode->DirBlockSize() 211 < &entry[count]) { 212 return B_BAD_VALUE; 213 } 214 215 for (int i = 0; i < count; i++) { 216 if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval)) { 217 *rightMapOffset = B_BENDIAN_TO_HOST_INT32(entry[i].before); 218 return B_OK; 219 } 220 } 221 222 *rightMapOffset = 1; 223 return B_OK; 224 } 225 226 227 int 228 NodeDirectory::EntrySize(int len) const 229 { 230 int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 231 // uint16 is for the tag 232 if (fInode->HasFileTypeField()) 233 entrySize += sizeof(uint8); 234 235 return ROUNDUP(entrySize, 8); 236 // rounding off to closest multiple of 8 237 } 238 239 240 void 241 NodeDirectory::SearchAndFillDataMap(uint64 blockNo) 242 { 243 int len = fInode->DataExtentsCount(); 244 245 for (int i = 0; i <= len - fFirstLeafMapIndex; i++) { 246 FillMapEntry(i, fDataMap); 247 if (fDataMap->br_startoff <= blockNo 248 && (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1)) 249 // Map found 250 return; 251 } 252 } 253 254 255 status_t 256 NodeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino) 257 { 258 TRACE("NodeDirectory::GetNext\n"); 259 status_t status; 260 261 if (fDataBuffer == NULL) { 262 status = FillBuffer(DATA, fDataBuffer, 0); 263 if (status != B_OK) 264 return status; 265 } 266 267 Volume* volume = fInode->GetVolume(); 268 269 void* entry; // This could be unused entry so we should check 270 271 entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode)); 272 273 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 274 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) { 275 entry = (void*)(fDataBuffer 276 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode)); 277 // This gets us a little faster to the next entry 278 } 279 280 uint32 curDirectorySize = fInode->Size(); 281 282 while (fOffset != curDirectorySize) { 283 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 284 285 TRACE("fOffset:(%" B_PRIu32 "), blockNoFromAddress:(%" B_PRIu32 ")\n", 286 fOffset, blockNoFromAddress); 287 if (fCurBlockNumber != blockNoFromAddress 288 && blockNoFromAddress > fDataMap->br_startoff 289 && blockNoFromAddress 290 <= fDataMap->br_startoff + fDataMap->br_blockcount - 1) { 291 // When the block is mapped in the same data 292 // map entry but is not the first block 293 status = FillBuffer(DATA, fDataBuffer, 294 blockNoFromAddress - fDataMap->br_startoff); 295 if (status != B_OK) 296 return status; 297 entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode)); 298 fOffset = fOffset + ExtentDataHeader::Size(fInode); 299 fCurBlockNumber = blockNoFromAddress; 300 } else if (fCurBlockNumber != blockNoFromAddress) { 301 // When the block isn't mapped in the current data map entry 302 SearchAndFillDataMap(blockNoFromAddress); 303 status = FillBuffer(DATA, fDataBuffer, 304 blockNoFromAddress - fDataMap->br_startoff); 305 if (status != B_OK) 306 return status; 307 entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode)); 308 fOffset = fOffset + ExtentDataHeader::Size(fInode); 309 fCurBlockNumber = blockNoFromAddress; 310 } 311 312 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 313 314 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 315 TRACE("Unused entry found\n"); 316 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 317 entry = (void*) 318 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 319 continue; 320 } 321 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 322 323 uint16 currentOffset = (char*)dataEntry - fDataBuffer; 324 TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n", 325 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset); 326 327 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) { 328 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 329 continue; 330 } 331 332 if ((size_t)(dataEntry->namelen) >= *length) 333 return B_BUFFER_OVERFLOW; 334 335 fOffset = fOffset + EntrySize(dataEntry->namelen); 336 memcpy(name, dataEntry->name, dataEntry->namelen); 337 name[dataEntry->namelen] = '\0'; 338 *length = dataEntry->namelen + 1; 339 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 340 341 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n", 342 name,*length, *ino); 343 return B_OK; 344 } 345 346 return B_ENTRY_NOT_FOUND; 347 } 348 349 350 status_t 351 NodeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino) 352 { 353 TRACE("NodeDirectory: Lookup\n"); 354 TRACE("Name: %s\n", name); 355 uint32 hashValueOfRequest = hashfunction(name, length); 356 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest); 357 358 status_t status; 359 if (fCurLeafBufferNumber != 1) { 360 if (fCurLeafMapNumber != 1) { 361 FillMapEntry(fFirstLeafMapIndex, fLeafMap); 362 fCurLeafMapNumber = 1; 363 } 364 status = FillBuffer(LEAF, fLeafBuffer, 0); 365 if (status != B_OK) 366 return status; 367 fCurLeafBufferNumber = 1; 368 } 369 /* Leaf now has the nodes. */ 370 uint32 rightMapOffset; 371 status = FindHashInNode(hashValueOfRequest, &rightMapOffset); 372 if(status != B_OK) 373 return status; 374 375 if (rightMapOffset == 1) { 376 TRACE("Not in this directory.\n"); 377 return B_ENTRY_NOT_FOUND; 378 } 379 380 TRACE("rightMapOffset:(%" B_PRIu32 ")\n", rightMapOffset); 381 382 for(int i = fFirstLeafMapIndex; i < fInode->DataExtentsCount(); i++) 383 { 384 FillMapEntry(i, fLeafMap); 385 fCurLeafMapNumber = 2; 386 status = FillBuffer(LEAF, fLeafBuffer, 387 rightMapOffset - fLeafMap->br_startoff); 388 if (status != B_OK) 389 return status; 390 fCurLeafBufferNumber = 2; 391 ExtentLeafHeader* leafHeader = ExtentLeafHeader::Create(fInode, fLeafBuffer); 392 if(leafHeader == NULL) 393 return B_NO_MEMORY; 394 ExtentLeafEntry* leafEntry = 395 (ExtentLeafEntry*)(void*)(fLeafBuffer + ExtentLeafHeader::Size(fInode)); 396 if (leafEntry == NULL) 397 return B_NO_MEMORY; 398 399 int numberOfLeafEntries = leafHeader->Count(); 400 TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries); 401 int left = 0; 402 int right = numberOfLeafEntries - 1; 403 Volume* volume = fInode->GetVolume(); 404 405 hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest); 406 407 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 408 == hashValueOfRequest) { 409 410 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 411 if (address == 0) { 412 left++; 413 continue; 414 } 415 416 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 417 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 418 419 TRACE("DataBlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", 420 dataBlockNumber, offset); 421 if (dataBlockNumber != fCurBlockNumber) { 422 fCurBlockNumber = dataBlockNumber; 423 SearchAndFillDataMap(dataBlockNumber); 424 status = FillBuffer(DATA, fDataBuffer, 425 dataBlockNumber - fDataMap->br_startoff); 426 if (status != B_OK) 427 return status; 428 } 429 430 TRACE("offset:(%" B_PRIu32 ")\n", offset); 431 ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset); 432 433 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 434 if (retVal == 0) { 435 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 436 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 437 return B_OK; 438 } 439 left++; 440 } 441 delete leafHeader; 442 } 443 444 return B_ENTRY_NOT_FOUND; 445 } 446 447 448 NodeHeader::~NodeHeader() 449 { 450 } 451 452 453 /* 454 In NodeHeader we have same magic number for all forms of 455 directory so return magic number as per Inode Version. 456 */ 457 uint32 458 NodeHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode) 459 { 460 if (inode->Version() == 1 || inode->Version() == 2) 461 return XFS_DA_NODE_MAGIC; 462 else 463 return XFS_DA3_NODE_MAGIC; 464 } 465 466 467 uint32 468 NodeHeader::CRCOffset() 469 { 470 return offsetof(NodeHeaderV5::OnDiskData, info.crc); 471 } 472 473 474 NodeHeader* 475 NodeHeader::Create(Inode* inode, const char* buffer) 476 { 477 if (inode->Version() == 1 || inode->Version() == 2) { 478 NodeHeaderV4* header = new (std::nothrow) NodeHeaderV4(buffer); 479 return header; 480 } else { 481 NodeHeaderV5* header = new (std::nothrow) NodeHeaderV5(buffer); 482 return header; 483 } 484 } 485 486 487 /* 488 This Function returns Actual size of leaf header 489 in all forms of directory. 490 Never use sizeof() operator because we now have 491 vtable as well and it will give wrong results 492 */ 493 uint32 494 NodeHeader::Size(Inode* inode) 495 { 496 if (inode->Version() == 1 || inode->Version() == 2) 497 return sizeof(NodeHeaderV4::OnDiskData); 498 else 499 return sizeof(NodeHeaderV5::OnDiskData); 500 } 501 502 503 void 504 NodeHeaderV4::SwapEndian() 505 { 506 fData.info.forw = B_BENDIAN_TO_HOST_INT32(fData.info.forw); 507 fData.info.back = B_BENDIAN_TO_HOST_INT32(fData.info.back); 508 fData.info.magic = B_BENDIAN_TO_HOST_INT16(fData.info.magic); 509 fData.info.pad = B_BENDIAN_TO_HOST_INT16(fData.info.pad); 510 fData.count = B_BENDIAN_TO_HOST_INT16(fData.count); 511 fData.level = B_BENDIAN_TO_HOST_INT16(fData.level); 512 } 513 514 515 NodeHeaderV4::NodeHeaderV4(const char* buffer) 516 { 517 uint32 offset = 0; 518 519 fData.info = *(BlockInfo*)(buffer + offset); 520 offset += sizeof(BlockInfo); 521 522 fData.count = *(uint16*)(buffer + offset); 523 offset += sizeof(uint16); 524 525 fData.level = *(uint16*)(buffer + offset); 526 527 SwapEndian(); 528 } 529 530 531 NodeHeaderV4::~NodeHeaderV4() 532 { 533 } 534 535 536 uint16 537 NodeHeaderV4::Magic() 538 { 539 return fData.info.magic; 540 } 541 542 543 uint64 544 NodeHeaderV4::Blockno() 545 { 546 return B_BAD_VALUE; 547 } 548 549 550 uint64 551 NodeHeaderV4::Lsn() 552 { 553 return B_BAD_VALUE; 554 } 555 556 557 uint64 558 NodeHeaderV4::Owner() 559 { 560 return B_BAD_VALUE; 561 } 562 563 564 const uuid_t& 565 NodeHeaderV4::Uuid() 566 { 567 static uuid_t nullUuid = {0}; 568 return nullUuid; 569 } 570 571 572 uint16 573 NodeHeaderV4::Count() 574 { 575 return fData.count; 576 } 577 578 579 void 580 NodeHeaderV5::SwapEndian() 581 { 582 fData.info.forw = B_BENDIAN_TO_HOST_INT32(fData.info.forw); 583 fData.info.back = B_BENDIAN_TO_HOST_INT32(fData.info.back); 584 fData.info.magic = B_BENDIAN_TO_HOST_INT16(fData.info.magic); 585 fData.info.pad = B_BENDIAN_TO_HOST_INT16(fData.info.pad); 586 fData.info.blkno = B_BENDIAN_TO_HOST_INT64(fData.info.blkno); 587 fData.info.lsn = B_BENDIAN_TO_HOST_INT64(fData.info.lsn); 588 fData.info.owner = B_BENDIAN_TO_HOST_INT64(fData.info.owner); 589 fData.count = B_BENDIAN_TO_HOST_INT16(fData.count); 590 fData.level = B_BENDIAN_TO_HOST_INT16(fData.level); 591 fData.pad32 = B_BENDIAN_TO_HOST_INT32(fData.pad32); 592 } 593 594 595 NodeHeaderV5::NodeHeaderV5(const char* buffer) 596 { 597 memcpy(&fData, buffer, sizeof(fData)); 598 SwapEndian(); 599 } 600 601 602 NodeHeaderV5::~NodeHeaderV5() 603 { 604 } 605 606 607 uint16 608 NodeHeaderV5::Magic() 609 { 610 return fData.info.magic; 611 } 612 613 614 uint64 615 NodeHeaderV5::Blockno() 616 { 617 return fData.info.blkno; 618 } 619 620 621 uint64 622 NodeHeaderV5::Lsn() 623 { 624 return fData.info.lsn; 625 } 626 627 628 uint64 629 NodeHeaderV5::Owner() 630 { 631 return fData.info.owner; 632 } 633 634 635 const uuid_t& 636 NodeHeaderV5::Uuid() 637 { 638 return fData.info.uuid; 639 } 640 641 642 uint16 643 NodeHeaderV5::Count() 644 { 645 return fData.count; 646 } 647