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 = CreateDataHeader(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 = CreateLeafHeader(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 = CreateNodeHeader(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 = CreateNodeHeader(fInode, fLeafBuffer); 204 if (header == NULL) 205 return B_NO_MEMORY; 206 207 NodeEntry* entry = (NodeEntry*)(void*)(fLeafBuffer + SizeOfNodeHeader(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 + SizeOfDataHeader(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 + SizeOfDataHeader(fInode)); 298 fOffset = fOffset + SizeOfDataHeader(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 + SizeOfDataHeader(fInode)); 308 fOffset = fOffset + SizeOfDataHeader(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 = CreateLeafHeader(fInode, fLeafBuffer); 392 if(leafHeader == NULL) 393 return B_NO_MEMORY; 394 ExtentLeafEntry* leafEntry = 395 (ExtentLeafEntry*)(void*)(fLeafBuffer + SizeOfLeafHeader(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 XFS_NODE_CRC_OFF - XFS_NODE_V5_VPTR_OFF; 471 } 472 473 474 void 475 NodeHeaderV4::SwapEndian() 476 { 477 info.forw = B_BENDIAN_TO_HOST_INT32(info.forw); 478 info.back = B_BENDIAN_TO_HOST_INT32(info.back); 479 info.magic = B_BENDIAN_TO_HOST_INT16(info.magic); 480 info.pad = B_BENDIAN_TO_HOST_INT16(info.pad); 481 count = B_BENDIAN_TO_HOST_INT16(count); 482 level = B_BENDIAN_TO_HOST_INT16(level); 483 } 484 485 486 NodeHeaderV4::NodeHeaderV4(const char* buffer) 487 { 488 uint32 offset = 0; 489 490 info = *(BlockInfo*)(buffer + offset); 491 offset += sizeof(BlockInfo); 492 493 count = *(uint16*)(buffer + offset); 494 offset += sizeof(uint16); 495 496 level = *(uint16*)(buffer + offset); 497 498 SwapEndian(); 499 } 500 501 502 NodeHeaderV4::~NodeHeaderV4() 503 { 504 } 505 506 507 uint16 508 NodeHeaderV4::Magic() 509 { 510 return info.magic; 511 } 512 513 514 uint64 515 NodeHeaderV4::Blockno() 516 { 517 return B_BAD_VALUE; 518 } 519 520 521 uint64 522 NodeHeaderV4::Lsn() 523 { 524 return B_BAD_VALUE; 525 } 526 527 528 uint64 529 NodeHeaderV4::Owner() 530 { 531 return B_BAD_VALUE; 532 } 533 534 535 uuid_t* 536 NodeHeaderV4::Uuid() 537 { 538 return NULL; 539 } 540 541 542 uint16 543 NodeHeaderV4::Count() 544 { 545 return count; 546 } 547 548 549 void 550 NodeHeaderV5::SwapEndian() 551 { 552 info.forw = B_BENDIAN_TO_HOST_INT32(info.forw); 553 info.back = B_BENDIAN_TO_HOST_INT32(info.back); 554 info.magic = B_BENDIAN_TO_HOST_INT16(info.magic); 555 info.pad = B_BENDIAN_TO_HOST_INT16(info.pad); 556 info.blkno = B_BENDIAN_TO_HOST_INT64(info.blkno); 557 info.lsn = B_BENDIAN_TO_HOST_INT64(info.lsn); 558 info.owner = B_BENDIAN_TO_HOST_INT64(info.owner); 559 count = B_BENDIAN_TO_HOST_INT16(count); 560 level = B_BENDIAN_TO_HOST_INT16(level); 561 pad32 = B_BENDIAN_TO_HOST_INT32(pad32); 562 } 563 564 565 NodeHeaderV5::NodeHeaderV5(const char* buffer) 566 { 567 uint32 offset = 0; 568 569 info = *(BlockInfoV5*)(buffer + offset); 570 offset += sizeof(BlockInfoV5); 571 572 count = *(uint16*)(buffer + offset); 573 offset += sizeof(uint16); 574 575 level = *(uint16*)(buffer + offset); 576 offset += sizeof(uint16); 577 578 pad32 = *(uint32*)(buffer + offset); 579 580 SwapEndian(); 581 } 582 583 584 NodeHeaderV5::~NodeHeaderV5() 585 { 586 } 587 588 589 uint16 590 NodeHeaderV5::Magic() 591 { 592 return info.magic; 593 } 594 595 596 uint64 597 NodeHeaderV5::Blockno() 598 { 599 return info.blkno; 600 } 601 602 603 uint64 604 NodeHeaderV5::Lsn() 605 { 606 return info.lsn; 607 } 608 609 610 uint64 611 NodeHeaderV5::Owner() 612 { 613 return info.owner; 614 } 615 616 617 uuid_t* 618 NodeHeaderV5::Uuid() 619 { 620 return &info.uuid; 621 } 622 623 624 uint16 625 NodeHeaderV5::Count() 626 { 627 return count; 628 } 629 630 631 //Function to get V4 or V5 leaf header instance 632 NodeHeader* 633 CreateNodeHeader(Inode* inode, const char* buffer) 634 { 635 if (inode->Version() == 1 || inode->Version() == 2) { 636 NodeHeaderV4* header = new (std::nothrow) NodeHeaderV4(buffer); 637 return header; 638 } else { 639 NodeHeaderV5* header = new (std::nothrow) NodeHeaderV5(buffer); 640 return header; 641 } 642 } 643 644 645 /* 646 This Function returns Actual size of leaf header 647 in all forms of directory. 648 Never use sizeof() operator because we now have 649 vtable as well and it will give wrong results 650 */ 651 uint32 652 SizeOfNodeHeader(Inode* inode) 653 { 654 if (inode->Version() == 1 || inode->Version() == 2) 655 return sizeof(NodeHeaderV4) - XFS_NODE_V4_VPTR_OFF; 656 else 657 return sizeof(NodeHeaderV5) - XFS_NODE_V5_VPTR_OFF; 658 }