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