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 "BPlusTree.h" 8 9 #include "VerifyHeader.h" 10 11 12 TreeDirectory::TreeDirectory(Inode* inode) 13 : 14 fInode(inode), 15 fInitStatus(B_OK), 16 fRoot(NULL), 17 fExtents(NULL), 18 fCountOfFilledExtents(0), 19 fSingleDirBlock(NULL), 20 fOffsetOfSingleDirBlock(-1), 21 fCurMapIndex(0), 22 fOffset(0), 23 fCurBlockNumber(0) 24 { 25 fRoot = new(std::nothrow) BlockInDataFork; 26 if (fRoot == NULL) { 27 fInitStatus = B_NO_MEMORY; 28 return; 29 } 30 31 fSingleDirBlock = new(std::nothrow) char[fInode->DirBlockSize()]; 32 if (fSingleDirBlock == NULL) { 33 fInitStatus = B_NO_MEMORY; 34 return; 35 } 36 37 memcpy((void*)fRoot, 38 DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()), sizeof(BlockInDataFork)); 39 40 for (int i = 0; i < MAX_TREE_DEPTH; i++) { 41 fPathForLeaves[i].blockData = NULL; 42 fPathForData[i].blockData = NULL; 43 } 44 } 45 46 47 TreeDirectory::~TreeDirectory() 48 { 49 delete fRoot; 50 delete[] fExtents; 51 delete[] fSingleDirBlock; 52 } 53 54 55 status_t 56 TreeDirectory::InitCheck() 57 { 58 return fInitStatus; 59 } 60 61 62 uint32 63 TreeDirectory::BlockLen() 64 { 65 return fInode->SizeOfLongBlock(); 66 } 67 68 69 size_t 70 TreeDirectory::KeySize() 71 { 72 return XFS_KEY_SIZE; 73 } 74 75 76 size_t 77 TreeDirectory::PtrSize() 78 { 79 return XFS_PTR_SIZE; 80 } 81 82 83 size_t 84 TreeDirectory::MaxRecordsPossibleRoot() 85 { 86 size_t lengthOfDataFork = 0; 87 if (fInode->ForkOffset() != 0) 88 lengthOfDataFork = fInode->ForkOffset() << 3; 89 if (fInode->ForkOffset() == 0) { 90 lengthOfDataFork = fInode->GetVolume()->InodeSize() 91 - fInode->CoreInodeSize(); 92 } 93 94 lengthOfDataFork -= sizeof(BlockInDataFork); 95 return lengthOfDataFork / (KeySize() + PtrSize()); 96 } 97 98 99 size_t 100 TreeDirectory::GetPtrOffsetIntoRoot(int pos) 101 { 102 size_t maxRecords = MaxRecordsPossibleRoot(); 103 return sizeof(BlockInDataFork) + maxRecords * KeySize() 104 + (pos - 1) * PtrSize(); 105 } 106 107 108 size_t 109 TreeDirectory::MaxRecordsPossibleNode() 110 { 111 size_t availableSpace = fInode->GetVolume()->BlockSize() - BlockLen(); 112 return availableSpace / (KeySize() + PtrSize()); 113 } 114 115 116 size_t 117 TreeDirectory::GetPtrOffsetIntoNode(int pos) 118 { 119 size_t maxRecords = MaxRecordsPossibleNode(); 120 return BlockLen() + maxRecords * KeySize() + (pos - 1) * PtrSize(); 121 } 122 123 124 TreePointer* 125 TreeDirectory::GetPtrFromRoot(int pos) 126 { 127 return (TreePointer*) 128 ((char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()) 129 + GetPtrOffsetIntoRoot(pos)); 130 } 131 132 133 TreePointer* 134 TreeDirectory::GetPtrFromNode(int pos, void* buffer) 135 { 136 size_t offsetIntoNode = GetPtrOffsetIntoNode(pos); 137 return (TreePointer*)((char*)buffer + offsetIntoNode); 138 } 139 140 141 TreeKey* 142 TreeDirectory::GetKeyFromNode(int pos, void* buffer) 143 { 144 return (TreeKey*) 145 ((char*)buffer + BlockLen() + (pos - 1) * KeySize()); 146 } 147 148 149 TreeKey* 150 TreeDirectory::GetKeyFromRoot(int pos) 151 { 152 off_t offset = (pos - 1) * KeySize(); 153 char* base = (char*)DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()) 154 + sizeof(BlockInDataFork); 155 return (TreeKey*) (base + offset); 156 } 157 158 159 status_t 160 TreeDirectory::SearchOffsetInTreeNode(uint32 offset, 161 TreePointer** pointer, int pathIndex) 162 { 163 // This is O(MaxRecords). Next is to implement this using upper bound 164 // binary search and get O(log(MaxRecords)) 165 *pointer = NULL; 166 TreeKey* offsetKey = NULL; 167 size_t maxRecords = MaxRecordsPossibleNode(); 168 for (int i = maxRecords - 1; i >= 0; i--) { 169 offsetKey 170 = GetKeyFromNode(i + 1, (void*)fPathForLeaves[pathIndex].blockData); 171 if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) { 172 *pointer = GetPtrFromNode(i + 1, (void*) 173 fPathForLeaves[pathIndex].blockData); 174 175 break; 176 } 177 } 178 179 if (offsetKey == NULL || *pointer == NULL) 180 return B_BAD_VALUE; 181 182 return B_OK; 183 } 184 185 186 status_t 187 TreeDirectory::SearchAndFillPath(uint32 offset, int type) 188 { 189 TRACE("SearchAndFillPath:\n"); 190 PathNode* path; 191 if (type == DATA) 192 path = fPathForData; 193 else if (type == LEAF) 194 path = fPathForLeaves; 195 else 196 return B_BAD_VALUE; 197 198 TreePointer* ptrToNode = NULL; 199 TreeKey* offsetKey = NULL; 200 // Go down the root of the tree first 201 for (int i = fRoot->NumRecords() - 1; i >= 0; i--) { 202 offsetKey = GetKeyFromRoot(i + 1); 203 if (B_BENDIAN_TO_HOST_INT64(*offsetKey) <= offset) { 204 ptrToNode = GetPtrFromRoot(i + 1); 205 break; 206 } 207 } 208 if (ptrToNode == NULL || offsetKey == NULL) { 209 //Corrupt tree 210 return B_BAD_VALUE; 211 } 212 213 // We now have gone down the root and save path if not saved. 214 int level = fRoot->Levels() - 1; 215 Volume* volume = fInode->GetVolume(); 216 status_t status; 217 for (int i = 0; i < MAX_TREE_DEPTH && level >= 0; i++, level--) { 218 uint64 requiredBlock = B_BENDIAN_TO_HOST_INT64(*ptrToNode); 219 TRACE("requiredBlock:(%" B_PRIu64 ")\n", requiredBlock); 220 if (path[i].blockNumber == requiredBlock) { 221 // This block already has what we need 222 if (path[i].type == 2) 223 break; 224 status = SearchOffsetInTreeNode(offset, &ptrToNode, i); 225 if (status != B_OK) 226 return status; 227 continue; 228 } 229 // We do not have the block we need 230 ssize_t len; 231 if (level == 0) { 232 // The size of buffer should be the directory block size 233 len = fInode->DirBlockSize(); 234 TRACE("path node type:(%" B_PRId32 ")\n", path[i].type); 235 if (path[i].type != 2) { 236 // Size is not directory block size. 237 delete path[i].blockData; 238 path[i].type = 0; 239 path[i].blockData = new(std::nothrow) char[len]; 240 if (path[i].blockData == NULL) 241 return B_NO_MEMORY; 242 path[i].type = 2; 243 } 244 uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock); 245 if (read_pos(volume->Device(), readPos, path[i].blockData, len) 246 != len) { 247 ERROR("FillPath::FillBlockBuffer(): IO Error"); 248 return B_IO_ERROR; 249 } 250 path[i].blockNumber = requiredBlock; 251 break; 252 } 253 // The size of buffer should be the block size 254 len = volume->BlockSize(); 255 if (path[i].type != 1) { 256 delete path[i].blockData; 257 path[i].type = 0; 258 path[i].blockData = new(std::nothrow) char[len]; 259 if (path[i].blockData == NULL) 260 return B_NO_MEMORY; 261 path[i].type = 1; 262 } 263 uint64 readPos = fInode->FileSystemBlockToAddr(requiredBlock); 264 if (read_pos(volume->Device(), readPos, path[i].blockData, len) 265 != len) { 266 ERROR("FillPath::FillBlockBuffer(): IO Error"); 267 return B_IO_ERROR; 268 } 269 path[i].blockNumber = requiredBlock; 270 status = SearchOffsetInTreeNode(offset, &ptrToNode, i); 271 if (status != B_OK) 272 return status; 273 } 274 275 return B_OK; 276 } 277 278 279 status_t 280 TreeDirectory::GetAllExtents() 281 { 282 xfs_extnum_t noOfExtents = fInode->DataExtentsCount(); 283 284 ExtentMapUnwrap* extentsWrapped 285 = new(std::nothrow) ExtentMapUnwrap[noOfExtents]; 286 if (extentsWrapped == NULL) 287 return B_NO_MEMORY; 288 289 ArrayDeleter<ExtentMapUnwrap> extentsWrappedDeleter(extentsWrapped); 290 291 Volume* volume = fInode->GetVolume(); 292 ssize_t len = volume->BlockSize(); 293 294 uint16 levelsInTree = fRoot->Levels(); 295 status_t status = fInode->GetNodefromTree(levelsInTree, volume, len, 296 fInode->DirBlockSize(), fSingleDirBlock); 297 if (status != B_OK) 298 return status; 299 300 // We should be at the left most leaf node. 301 // This could be a multilevel node type directory 302 uint64 fileSystemBlockNo; 303 while (1) { 304 // Run till you have leaf blocks to checkout 305 char* leafBuffer = fSingleDirBlock; 306 if (!VerifyHeader<LongBlock>((LongBlock*)leafBuffer, leafBuffer, fInode, 307 0, NULL, XFS_BTREE)) { 308 TRACE("Invalid Long Block"); 309 return B_BAD_VALUE; 310 } 311 312 uint32 offset = fInode->SizeOfLongBlock(); 313 int numRecs = ((LongBlock*)leafBuffer)->NumRecs(); 314 315 for (int i = 0; i < numRecs; i++) { 316 extentsWrapped[fCountOfFilledExtents].first = 317 *(uint64*)(leafBuffer + offset); 318 extentsWrapped[fCountOfFilledExtents].second = 319 *(uint64*)(leafBuffer + offset + sizeof(uint64)); 320 offset += sizeof(ExtentMapUnwrap); 321 fCountOfFilledExtents++; 322 } 323 324 fileSystemBlockNo = ((LongBlock*)leafBuffer)->Right(); 325 TRACE("Next leaf is at: (%" B_PRIu64 ")\n", fileSystemBlockNo); 326 if (fileSystemBlockNo == (uint64) -1) 327 break; 328 uint64 readPos = fInode->FileSystemBlockToAddr(fileSystemBlockNo); 329 if (read_pos(volume->Device(), readPos, fSingleDirBlock, len) 330 != len) { 331 ERROR("Extent::FillBlockBuffer(): IO Error"); 332 return B_IO_ERROR; 333 } 334 } 335 TRACE("Total covered: (%" B_PRIu32 ")\n", fCountOfFilledExtents); 336 337 status = UnWrapExtents(extentsWrapped); 338 339 return status; 340 } 341 342 343 status_t 344 TreeDirectory::FillBuffer(char* blockBuffer, int howManyBlocksFurther, 345 ExtentMapEntry* targetMap) 346 { 347 TRACE("FILLBUFFER\n"); 348 ExtentMapEntry map; 349 if (targetMap == NULL) 350 map = fExtents[fCurMapIndex]; 351 if (targetMap != NULL) 352 map = *targetMap; 353 354 if (map.br_state != 0) 355 return B_BAD_VALUE; 356 357 ssize_t len = fInode->DirBlockSize(); 358 if (blockBuffer == NULL) { 359 blockBuffer = new(std::nothrow) char[len]; 360 if (blockBuffer == NULL) 361 return B_NO_MEMORY; 362 } 363 364 xfs_daddr_t readPos = fInode->FileSystemBlockToAddr( 365 map.br_startblock + howManyBlocksFurther); 366 367 if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len) 368 != len) { 369 ERROR("TreeDirectory::FillBlockBuffer(): IO Error"); 370 return B_IO_ERROR; 371 } 372 373 if (targetMap == NULL) { 374 fSingleDirBlock = blockBuffer; 375 ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fSingleDirBlock); 376 if (header == NULL) 377 return B_NO_MEMORY; 378 if (!VerifyHeader<ExtentDataHeader>(header, fSingleDirBlock, fInode, 379 howManyBlocksFurther, &map, XFS_BTREE)) { 380 ERROR("Invalid Data block"); 381 delete header; 382 return B_BAD_VALUE; 383 } 384 delete header; 385 } 386 if (targetMap != NULL) { 387 fSingleDirBlock = blockBuffer; 388 /* 389 This could be leaf or node block perform check for both 390 based on magic number found. 391 */ 392 ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fSingleDirBlock); 393 if (leaf == NULL) 394 return B_NO_MEMORY; 395 396 if ((leaf->Magic() == XFS_DIR2_LEAFN_MAGIC 397 || leaf->Magic() == XFS_DIR3_LEAFN_MAGIC) 398 && !VerifyHeader<ExtentLeafHeader>(leaf, fSingleDirBlock, fInode, 399 howManyBlocksFurther, &map, XFS_BTREE)) { 400 TRACE("Leaf block invalid"); 401 delete leaf; 402 return B_BAD_VALUE; 403 } 404 delete leaf; 405 leaf = NULL; 406 407 NodeHeader* node = NodeHeader::Create(fInode, fSingleDirBlock); 408 if (node == NULL) 409 return B_NO_MEMORY; 410 411 if ((node->Magic() == XFS_DA_NODE_MAGIC 412 || node->Magic() == XFS_DA3_NODE_MAGIC) 413 && !VerifyHeader<NodeHeader>(node, fSingleDirBlock, fInode, 414 howManyBlocksFurther, &map, XFS_BTREE)) { 415 TRACE("Node block invalid"); 416 delete node; 417 return B_BAD_VALUE; 418 } 419 delete node; 420 } 421 return B_OK; 422 } 423 424 425 int 426 TreeDirectory::EntrySize(int len) const 427 { 428 int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 429 // uint16 is for the tag 430 if (fInode->HasFileTypeField()) 431 entrySize += sizeof(uint8); 432 433 return ROUNDUP(entrySize, 8); 434 // rounding off to next greatest multiple of 8 435 } 436 437 438 /* 439 * Throw in the desired block number and get the index of it 440 */ 441 status_t 442 TreeDirectory::SearchMapInAllExtent(uint64 blockNo, uint32& mapIndex) 443 { 444 ExtentMapEntry map; 445 for (uint32 i = 0; i < fCountOfFilledExtents; i++) { 446 map = fExtents[i]; 447 if (map.br_startoff <= blockNo 448 && (blockNo <= map.br_startoff + map.br_blockcount - 1)) { 449 // Map found 450 mapIndex = i; 451 return B_OK; 452 } 453 } 454 455 return B_ENTRY_NOT_FOUND; 456 } 457 458 459 status_t 460 TreeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino) 461 { 462 TRACE("TreeDirectory::GetNext\n"); 463 status_t status; 464 if (fExtents == NULL) { 465 status = GetAllExtents(); 466 if (status != B_OK) 467 return status; 468 } 469 status = FillBuffer(fSingleDirBlock, 0); 470 if (status != B_OK) 471 return status; 472 473 Volume* volume = fInode->GetVolume(); 474 475 void* entry; // This could be unused entry so we should check 476 entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode)); 477 478 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 479 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) { 480 entry = (void*)(fSingleDirBlock 481 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode)); 482 // This gets us a little faster to the next entry 483 } 484 485 uint32 curDirectorySize = fInode->Size(); 486 ExtentMapEntry& map = fExtents[fCurMapIndex]; 487 while (fOffset != curDirectorySize) { 488 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 489 490 TRACE("fOffset:(%" B_PRIu64 "), blockNoFromAddress:(%" B_PRIu32 ")\n", 491 fOffset, blockNoFromAddress); 492 if (fCurBlockNumber != blockNoFromAddress 493 && blockNoFromAddress > map.br_startoff 494 && blockNoFromAddress 495 <= map.br_startoff + map.br_blockcount - 1) { 496 // When the block is mapped in the same data 497 // map entry but is not the first block 498 status = FillBuffer(fSingleDirBlock, 499 blockNoFromAddress - map.br_startoff); 500 if (status != B_OK) 501 return status; 502 entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode)); 503 fOffset = fOffset + ExtentDataHeader::Size(fInode); 504 fCurBlockNumber = blockNoFromAddress; 505 } else if (fCurBlockNumber != blockNoFromAddress) { 506 // When the block isn't mapped in the current data map entry 507 uint32 curMapIndex; 508 status = SearchMapInAllExtent(blockNoFromAddress, curMapIndex); 509 if (status != B_OK) 510 return status; 511 fCurMapIndex = curMapIndex; 512 map = fExtents[fCurMapIndex]; 513 status = FillBuffer(fSingleDirBlock, 514 blockNoFromAddress - map.br_startoff); 515 if (status != B_OK) 516 return status; 517 entry = (void*)(fSingleDirBlock + ExtentDataHeader::Size(fInode)); 518 fOffset = fOffset + ExtentDataHeader::Size(fInode); 519 fCurBlockNumber = blockNoFromAddress; 520 } 521 522 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 523 524 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 525 TRACE("Unused entry found\n"); 526 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 527 entry = (void*) 528 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 529 continue; 530 } 531 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 532 533 uint16 currentOffset = (char*)dataEntry - fSingleDirBlock; 534 TRACE("GetNext: fOffset:(%" B_PRIu64 "), currentOffset:(%" B_PRIu16 ")\n", 535 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset); 536 537 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) { 538 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 539 continue; 540 } 541 542 if ((size_t)(dataEntry->namelen) >= *length) 543 return B_BUFFER_OVERFLOW; 544 545 fOffset = fOffset + EntrySize(dataEntry->namelen); 546 memcpy(name, dataEntry->name, dataEntry->namelen); 547 name[dataEntry->namelen] = '\0'; 548 *length = dataEntry->namelen + 1; 549 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 550 551 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "), ino: (%" B_PRIu64 ")\n", name, 552 *length, *ino); 553 return B_OK; 554 } 555 556 return B_ENTRY_NOT_FOUND; 557 } 558 559 560 status_t 561 TreeDirectory::UnWrapExtents(ExtentMapUnwrap* extentsWrapped) 562 { 563 fExtents = new(std::nothrow) ExtentMapEntry[fCountOfFilledExtents]; 564 if (fExtents == NULL) 565 return B_NO_MEMORY; 566 uint64 first, second; 567 568 for (uint32 i = 0; i < fCountOfFilledExtents; i++) { 569 first = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].first); 570 second = B_BENDIAN_TO_HOST_INT64(extentsWrapped[i].second); 571 fExtents[i].br_state = first >> 63; 572 fExtents[i].br_startoff = (first & MASK(63)) >> 9; 573 fExtents[i].br_startblock = ((first & MASK(9)) << 43) | (second >> 21); 574 fExtents[i].br_blockcount = second & MASK(21); 575 } 576 577 return B_OK; 578 } 579 580 581 void 582 TreeDirectory::FillMapEntry(int num, ExtentMapEntry** fMap, 583 int type, int pathIndex) 584 { 585 void* pointerToMap; 586 if (type == DATA) { 587 char* base = fPathForData[pathIndex].blockData + BlockLen(); 588 off_t offset = num * EXTENT_SIZE; 589 pointerToMap = (void*)(base + offset); 590 } else { 591 char* base = fPathForLeaves[pathIndex].blockData + BlockLen(); 592 off_t offset = num * EXTENT_SIZE; 593 pointerToMap = (void*)(base + offset); 594 } 595 uint64 firstHalf = *((uint64*)pointerToMap); 596 uint64 secondHalf = *((uint64*)pointerToMap + 1); 597 //dividing the 128 bits into 2 parts. 598 599 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 600 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 601 (*fMap)->br_state = firstHalf >> 63; 602 (*fMap)->br_startoff = (firstHalf & MASK(63)) >> 9; 603 (*fMap)->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 604 (*fMap)->br_blockcount = secondHalf & MASK(21); 605 TRACE("FillMapEntry: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 ")," 606 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", (*fMap)->br_startoff, 607 (*fMap)->br_startblock,(*fMap)->br_blockcount, (*fMap)->br_state); 608 } 609 610 611 void 612 TreeDirectory::SearchForMapInDirectoryBlock(uint64 blockNo, 613 int entries, ExtentMapEntry** map, int type, int pathIndex) 614 { 615 TRACE("SearchForMapInDirectoryBlock: blockNo:(%" B_PRIu64 ")\n", blockNo); 616 for (int i = 0; i < entries; i++) { 617 FillMapEntry(i, map, type, pathIndex); 618 if ((*map)->br_startoff <= blockNo 619 && (blockNo <= (*map)->br_startoff + (*map)->br_blockcount - 1)) { 620 // Map found 621 return; 622 } 623 } 624 // Map wasn't found. Some kind of corruption. This is checked by caller. 625 *map = NULL; 626 } 627 628 629 uint32 630 TreeDirectory::SearchForHashInNodeBlock(uint32 hashVal) 631 { 632 NodeHeader* header = NodeHeader::Create(fInode, fSingleDirBlock); 633 if (header == NULL) 634 return B_NO_MEMORY; 635 NodeEntry* entry = (NodeEntry*)(fSingleDirBlock + NodeHeader::Size(fInode)); 636 int count = header->Count(); 637 delete header; 638 639 for (int i = 0; i < count; i++) { 640 if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval)) 641 return B_BENDIAN_TO_HOST_INT32(entry[i].before); 642 } 643 return 0; 644 } 645 646 647 status_t 648 TreeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino) 649 { 650 TRACE("TreeDirectory: Lookup\n"); 651 TRACE("Name: %s\n", name); 652 uint32 hashValueOfRequest = hashfunction(name, length); 653 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest); 654 655 Volume* volume = fInode->GetVolume(); 656 status_t status; 657 658 ExtentMapEntry* targetMap = new(std::nothrow) ExtentMapEntry; 659 if (targetMap == NULL) 660 return B_NO_MEMORY; 661 int pathIndex = -1; 662 uint32 rightOffset = LEAF_STARTOFFSET(volume->BlockLog()); 663 664 // In node directories, the "node blocks" had a single level 665 // Here we could have multiple levels. With each iteration of 666 // the loop we go a level lower. 667 while (rightOffset != fOffsetOfSingleDirBlock && 1) { 668 status = SearchAndFillPath(rightOffset, LEAF); 669 if (status != B_OK) 670 return status; 671 672 // The path should now have the Tree Leaf at appropriate level 673 // Find the directory block in the path 674 for (int i = 0; i < MAX_TREE_DEPTH; i++) { 675 if (fPathForLeaves[i].type == 2) { 676 pathIndex = i; 677 break; 678 } 679 } 680 if (pathIndex == -1) { 681 // corrupt tree 682 return B_BAD_VALUE; 683 } 684 685 // Get the node block from directory block 686 // If level is non-zero, reiterate with new "rightOffset" 687 // Else, we are at leaf block, then break 688 LongBlock* curDirBlock 689 = (LongBlock*)fPathForLeaves[pathIndex].blockData; 690 691 if (!VerifyHeader<LongBlock>(curDirBlock, fPathForLeaves[pathIndex].blockData, fInode, 692 0, NULL, XFS_BTREE)) { 693 TRACE("Invalid Long Block"); 694 return B_BAD_VALUE; 695 } 696 697 SearchForMapInDirectoryBlock(rightOffset, curDirBlock->NumRecs(), 698 &targetMap, LEAF, pathIndex); 699 if (targetMap == NULL) 700 return B_BAD_VALUE; 701 702 FillBuffer(fSingleDirBlock, rightOffset - targetMap->br_startoff, 703 targetMap); 704 fOffsetOfSingleDirBlock = rightOffset; 705 ExtentLeafHeader* dirBlock = ExtentLeafHeader::Create(fInode, fSingleDirBlock); 706 if (dirBlock == NULL) 707 return B_NO_MEMORY; 708 if (dirBlock->Magic() == XFS_DIR2_LEAFN_MAGIC 709 || dirBlock->Magic() == XFS_DIR3_LEAFN_MAGIC) { 710 // Got the potential leaf. Break. 711 delete dirBlock; 712 break; 713 } 714 if (dirBlock->Magic() == XFS_DA_NODE_MAGIC 715 || dirBlock->Magic() == XFS_DA3_NODE_MAGIC) { 716 rightOffset = SearchForHashInNodeBlock(hashValueOfRequest); 717 if (rightOffset == 0) 718 return B_ENTRY_NOT_FOUND; 719 delete dirBlock; 720 continue; 721 } 722 } 723 // We now have the leaf block that might contain the entry we need. 724 // Else go to the right subling if it might contain it. Else break. 725 while (1) { 726 ExtentLeafHeader* leafHeader 727 = ExtentLeafHeader::Create(fInode, fSingleDirBlock); 728 if (leafHeader == NULL) 729 return B_NO_MEMORY; 730 ExtentLeafEntry* leafEntry 731 = (ExtentLeafEntry*)(fSingleDirBlock + ExtentLeafHeader::Size(fInode)); 732 733 int numberOfLeafEntries = leafHeader->Count(); 734 TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries); 735 int left = 0; 736 int right = numberOfLeafEntries - 1; 737 738 hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest); 739 740 uint32 nextLeaf = leafHeader->Forw(); 741 uint32 lastHashVal = B_BENDIAN_TO_HOST_INT32( 742 leafEntry[numberOfLeafEntries - 1].hashval); 743 744 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 745 == hashValueOfRequest) { 746 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 747 if (address == 0) { 748 left++; 749 continue; 750 } 751 752 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 753 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 754 755 TRACE("BlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset); 756 757 status = SearchAndFillPath(dataBlockNumber, DATA); 758 int pathIndex = -1; 759 for (int i = 0; i < MAX_TREE_DEPTH; i++) { 760 if (fPathForData[i].type == 2) { 761 pathIndex = i; 762 break; 763 } 764 } 765 if (pathIndex == -1) 766 return B_BAD_VALUE; 767 768 LongBlock* curDirBlock 769 = (LongBlock*)fPathForData[pathIndex].blockData; 770 771 SearchForMapInDirectoryBlock(dataBlockNumber, 772 curDirBlock->NumRecs(), &targetMap, DATA, pathIndex); 773 if (targetMap == NULL) 774 return B_BAD_VALUE; 775 776 FillBuffer(fSingleDirBlock, 777 dataBlockNumber - targetMap->br_startoff, targetMap); 778 fOffsetOfSingleDirBlock = dataBlockNumber; 779 780 TRACE("offset:(%" B_PRIu32 ")\n", offset); 781 ExtentDataEntry* entry 782 = (ExtentDataEntry*)(fSingleDirBlock + offset); 783 784 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 785 if (retVal == 0) { 786 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 787 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 788 return B_OK; 789 } 790 left++; 791 } 792 if (lastHashVal == hashValueOfRequest && nextLeaf != (uint32) -1) { 793 // Go to forward neighbor. We might find an entry there. 794 status = SearchAndFillPath(nextLeaf, LEAF); 795 if (status != B_OK) 796 return status; 797 798 pathIndex = -1; 799 for (int i = 0; i < MAX_TREE_DEPTH; i++) { 800 if (fPathForLeaves[i].type == 2) { 801 pathIndex = i; 802 break; 803 } 804 } 805 if (pathIndex == -1) 806 return B_BAD_VALUE; 807 808 LongBlock* curDirBlock 809 = (LongBlock*)fPathForLeaves[pathIndex].blockData; 810 811 SearchForMapInDirectoryBlock(nextLeaf, curDirBlock->NumRecs(), 812 &targetMap, LEAF, pathIndex); 813 if (targetMap == NULL) 814 return B_BAD_VALUE; 815 816 FillBuffer(fSingleDirBlock, 817 nextLeaf - targetMap->br_startoff, targetMap); 818 fOffsetOfSingleDirBlock = nextLeaf; 819 820 continue; 821 } else { 822 break; 823 } 824 delete leafHeader; 825 } 826 return B_ENTRY_NOT_FOUND; 827 } 828 829 830 uint32 831 LongBlock::ExpectedMagic(int8 WhichDirectory, Inode* inode) 832 { 833 if(inode->Version() == 3) 834 return XFS_BMAP_CRC_MAGIC; 835 else 836 return XFS_BMAP_MAGIC; 837 } 838 839 840 uint32 841 LongBlock::CRCOffset() 842 { 843 return offsetof(LongBlock, bb_crc); 844 }