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 "Inode.h" 8 #include "BPlusTree.h" 9 10 void 11 xfs_inode_t::SwapEndian() 12 { 13 di_magic = B_BENDIAN_TO_HOST_INT16(di_magic); 14 di_mode = B_BENDIAN_TO_HOST_INT16(di_mode); 15 di_onlink = B_BENDIAN_TO_HOST_INT16(di_onlink); 16 di_uid = B_BENDIAN_TO_HOST_INT32(di_uid); 17 di_gid = B_BENDIAN_TO_HOST_INT32(di_gid); 18 di_nlink = B_BENDIAN_TO_HOST_INT32(di_nlink); 19 di_projid = B_BENDIAN_TO_HOST_INT16(di_projid); 20 di_flushiter = B_BENDIAN_TO_HOST_INT16(di_flushiter); 21 di_atime.t_sec = B_BENDIAN_TO_HOST_INT32(di_atime.t_sec); 22 di_atime.t_nsec = B_BENDIAN_TO_HOST_INT32(di_atime.t_nsec); 23 di_mtime.t_sec = B_BENDIAN_TO_HOST_INT32(di_mtime.t_sec); 24 di_mtime.t_nsec = B_BENDIAN_TO_HOST_INT32(di_mtime.t_nsec); 25 di_ctime.t_sec = B_BENDIAN_TO_HOST_INT32(di_ctime.t_sec); 26 di_ctime.t_nsec = B_BENDIAN_TO_HOST_INT32(di_ctime.t_nsec); 27 di_size = B_BENDIAN_TO_HOST_INT64(di_size); 28 di_nblocks = B_BENDIAN_TO_HOST_INT64(di_nblocks); 29 di_extsize = B_BENDIAN_TO_HOST_INT32(di_extsize); 30 di_nextents = B_BENDIAN_TO_HOST_INT32(di_nextents); 31 di_anextents = B_BENDIAN_TO_HOST_INT16(di_anextents); 32 di_dmevmask = B_BENDIAN_TO_HOST_INT32(di_dmevmask); 33 di_dmstate = B_BENDIAN_TO_HOST_INT16(di_dmstate); 34 di_flags = B_BENDIAN_TO_HOST_INT16(di_flags); 35 di_gen = B_BENDIAN_TO_HOST_INT32(di_gen); 36 di_next_unlinked = B_BENDIAN_TO_HOST_INT32(di_next_unlinked); 37 } 38 39 40 uint8 41 xfs_inode_t::ForkOffset() const 42 { 43 return di_forkoff; 44 } 45 46 47 xfs_rfsblock_t 48 xfs_inode_t::BlockCount() const 49 { 50 return di_nblocks; 51 } 52 53 54 xfs_fsize_t 55 xfs_inode_t::Size() const 56 { 57 return di_size; 58 } 59 60 61 mode_t 62 xfs_inode_t::Mode() const 63 { 64 return di_mode; 65 } 66 67 68 uint32 69 xfs_inode_t::UserId() const 70 { 71 return di_uid; 72 } 73 74 75 uint32 76 xfs_inode_t::GroupId() const 77 { 78 return di_gid; 79 } 80 81 82 void 83 xfs_inode_t::GetModificationTime(struct timespec& stamp) 84 { 85 stamp.tv_sec = di_mtime.t_sec; 86 stamp.tv_nsec = di_mtime.t_nsec; 87 } 88 89 90 void 91 xfs_inode_t::GetAccessTime(struct timespec& stamp) 92 { 93 stamp.tv_sec = di_atime.t_sec; 94 stamp.tv_nsec = di_atime.t_nsec; 95 } 96 97 98 void 99 xfs_inode_t::GetChangeTime(struct timespec& stamp) 100 { 101 stamp.tv_sec = di_ctime.t_sec; 102 stamp.tv_nsec = di_ctime.t_nsec; 103 } 104 105 106 uint32 107 xfs_inode_t::NLink() const 108 { 109 return di_nlink; 110 } 111 112 113 int8 114 xfs_inode_t::Version() const 115 { 116 return di_version; 117 } 118 119 120 uint16 121 xfs_inode_t::Flags() const 122 { 123 return di_flags; 124 } 125 126 127 int8 128 xfs_inode_t::Format() const 129 { 130 return di_format; 131 } 132 133 134 xfs_extnum_t 135 xfs_inode_t::DataExtentsCount() const 136 { 137 return di_nextents; 138 } 139 140 141 Inode::Inode(Volume* volume, xfs_ino_t id) 142 : 143 fVolume(volume), 144 fId(id), 145 fBuffer(NULL), 146 fExtents(NULL) 147 { 148 } 149 150 151 status_t 152 Inode::Init() 153 { 154 fNode = new(std::nothrow) xfs_inode_t; 155 if (fNode == NULL) 156 return B_NO_MEMORY; 157 158 uint16 inodeSize = fVolume->InodeSize(); 159 fBuffer = new(std::nothrow) char[inodeSize]; 160 if (fBuffer == NULL) 161 return B_NO_MEMORY; 162 163 status_t status = GetFromDisk(); 164 if (status == B_OK) { 165 if (fNode->di_magic == INODE_MAGIC) { 166 TRACE("Init(): Inode successfully read.\n"); 167 status = B_OK; 168 } else { 169 TRACE("Init(): Inode wasn't read successfully!\n"); 170 status = B_BAD_VALUE; 171 } 172 } 173 174 return status; 175 } 176 177 178 Inode::~Inode() 179 { 180 delete fNode; 181 delete[] fBuffer; 182 delete[] fExtents; 183 } 184 185 186 bool 187 Inode::HasFileTypeField() const 188 { 189 return fVolume->SuperBlockFeatures2() & XFS_SB_VERSION2_FTYPE; 190 } 191 192 193 status_t 194 Inode::CheckPermissions(int accessMode) const 195 { 196 // you never have write access to a read-only volume 197 if ((accessMode & W_OK) != 0 && fVolume->IsReadOnly()) 198 return B_READ_ONLY_DEVICE; 199 200 return check_access_permissions(accessMode, Mode(), 201 (uint32)fNode->GroupId(), (uint32)fNode->UserId()); 202 } 203 204 205 void 206 Inode::UnWrapExtentFromWrappedEntry(uint64 wrappedExtent[2], 207 ExtentMapEntry* entry) 208 { 209 uint64 first = B_BENDIAN_TO_HOST_INT64(wrappedExtent[0]); 210 uint64 second = B_BENDIAN_TO_HOST_INT64(wrappedExtent[1]); 211 entry->br_state = first >> 63; 212 entry->br_startoff = (first & MASK(63)) >> 9; 213 entry->br_startblock = ((first & MASK(9)) << 43) | (second >> 21); 214 entry->br_blockcount = second & MASK(21); 215 } 216 217 218 status_t 219 Inode::ReadExtentsFromExtentBasedInode() 220 { 221 fExtents = new(std::nothrow) ExtentMapEntry[DataExtentsCount()]; 222 char* dataStart = (char*) DIR_DFORK_PTR(Buffer()); 223 uint64 wrappedExtent[2]; 224 for (int i = 0; i < DataExtentsCount(); i++) { 225 wrappedExtent[0] = *(uint64*)(dataStart); 226 wrappedExtent[1] = *(uint64*)(dataStart + sizeof(uint64)); 227 dataStart += 2 * sizeof(uint64); 228 UnWrapExtentFromWrappedEntry(wrappedExtent, &fExtents[i]); 229 } 230 return B_OK; 231 } 232 233 234 size_t 235 Inode::MaxRecordsPossibleInTreeRoot() 236 { 237 size_t lengthOfDataFork; 238 if (ForkOffset() != 0) 239 lengthOfDataFork = ForkOffset() << 3; 240 else if(ForkOffset() == 0) { 241 lengthOfDataFork = GetVolume()->InodeSize() 242 - INODE_CORE_UNLINKED_SIZE; 243 } 244 245 lengthOfDataFork -= sizeof(BlockInDataFork); 246 return lengthOfDataFork / (XFS_KEY_SIZE + XFS_PTR_SIZE); 247 } 248 249 250 size_t 251 Inode::GetPtrOffsetIntoRoot(int pos) 252 { 253 size_t maxRecords = MaxRecordsPossibleInTreeRoot(); 254 return (sizeof(BlockInDataFork) 255 + maxRecords * XFS_KEY_SIZE + (pos - 1) * XFS_PTR_SIZE); 256 } 257 258 259 TreePointer* 260 Inode::GetPtrFromRoot(int pos) 261 { 262 return (TreePointer*) 263 ((char*)DIR_DFORK_PTR(Buffer()) + GetPtrOffsetIntoRoot(pos)); 264 } 265 266 267 size_t 268 Inode::MaxRecordsPossibleNode() 269 { 270 size_t availableSpace = GetVolume()->BlockSize() - XFS_BTREE_LBLOCK_SIZE; 271 return availableSpace / (XFS_KEY_SIZE + XFS_PTR_SIZE); 272 } 273 274 275 size_t 276 Inode::GetPtrOffsetIntoNode(int pos) 277 { 278 size_t maxRecords = MaxRecordsPossibleNode(); 279 return XFS_BTREE_LBLOCK_SIZE + maxRecords * XFS_KEY_SIZE 280 + (pos - 1) * XFS_PTR_SIZE; 281 } 282 283 284 TreePointer* 285 Inode::GetPtrFromNode(int pos, void* buffer) 286 { 287 size_t offsetIntoNode = GetPtrOffsetIntoNode(pos); 288 return (TreePointer*)((char*)buffer + offsetIntoNode); 289 } 290 291 292 status_t 293 Inode::GetNodefromTree(uint16& levelsInTree, Volume* volume, 294 size_t& len, size_t DirBlockSize, char* block) { 295 296 char* node = new(std::nothrow) char[len]; 297 if (node == NULL) 298 return B_NO_MEMORY; 299 // This isn't for a directory block but for one of the tree nodes 300 301 ArrayDeleter<char> nodeDeleter(node); 302 303 TRACE("levels:(%d)\n", levelsInTree); 304 TRACE("Numrecs:(%d)\n", fRoot->NumRecords()); 305 306 TreePointer* ptrToNode = GetPtrFromRoot(1); 307 uint64 fileSystemBlockNo = B_BENDIAN_TO_HOST_INT64(*ptrToNode); 308 uint64 readPos = FileSystemBlockToAddr(fileSystemBlockNo); 309 // Go down the tree by taking the leftmost pointer to the first leaf 310 while (levelsInTree != 1) { 311 fileSystemBlockNo = B_BENDIAN_TO_HOST_INT64(*ptrToNode); 312 // The fs block that contains node at next lower level. Now read. 313 readPos = FileSystemBlockToAddr(fileSystemBlockNo); 314 if (read_pos(volume->Device(), readPos, node, len) != len) { 315 ERROR("Extent::FillBlockBuffer(): IO Error"); 316 return B_IO_ERROR; 317 } 318 LongBlock* curLongBlock = (LongBlock*)node; 319 ASSERT(curLongBlock->Magic() == XFS_BMAP_MAGIC); 320 ptrToNode = GetPtrFromNode(1, (void*)curLongBlock); 321 // Get's the first pointer. This points to next node. 322 levelsInTree--; 323 } 324 // Next level wil contain leaf nodes. Now Read Directory Buffer 325 len = DirBlockSize; 326 if (read_pos(volume->Device(), readPos, block, len) 327 != len) { 328 ERROR("Extent::FillBlockBuffer(): IO Error"); 329 return B_IO_ERROR; 330 } 331 levelsInTree--; 332 if (levelsInTree != 0) 333 return B_BAD_VALUE; 334 return B_OK; 335 } 336 337 338 status_t 339 Inode::ReadExtentsFromTreeInode() 340 { 341 fExtents = new(std::nothrow) ExtentMapEntry[DataExtentsCount()]; 342 BlockInDataFork* root = new(std::nothrow) BlockInDataFork; 343 if (root == NULL) 344 return B_NO_MEMORY; 345 memcpy((void*)root, 346 DIR_DFORK_PTR(Buffer()), sizeof(BlockInDataFork)); 347 348 size_t maxRecords = MaxRecordsPossibleInTreeRoot(); 349 TRACE("Maxrecords: (%d)\n", maxRecords); 350 351 uint16 levelsInTree = root->Levels(); 352 delete root; 353 354 Volume* volume = GetVolume(); 355 size_t len = volume->BlockSize(); 356 357 len = DirBlockSize(); 358 char* block = new(std::nothrow) char[len]; 359 if (block == NULL) 360 return B_NO_MEMORY; 361 362 ArrayDeleter<char> blockDeleter(block); 363 364 GetNodefromTree(levelsInTree, volume, len, DirBlockSize(), block); 365 366 uint64 fileSystemBlockNo; 367 uint64 wrappedExtent[2]; 368 int indexIntoExtents = 0; 369 // We should be at the left most leaf node. 370 // This could be a multilevel node type directory 371 while (1) { 372 // Run till you have leaf blocks to checkout 373 char* leafBuffer = block; 374 ASSERT(((LongBlock*)leafBuffer)->Magic() == XFS_BMAP_MAGIC); 375 uint32 offset = sizeof(LongBlock); 376 int numRecs = ((LongBlock*)leafBuffer)->NumRecs(); 377 378 for (int i = 0; i < numRecs; i++) { 379 wrappedExtent[0] = *(uint64*)(leafBuffer + offset); 380 wrappedExtent[1] 381 = *(uint64*)(leafBuffer + offset + sizeof(uint64)); 382 offset += sizeof(ExtentMapUnwrap); 383 UnWrapExtentFromWrappedEntry(wrappedExtent, 384 &fExtents[indexIntoExtents]); 385 indexIntoExtents++; 386 } 387 388 fileSystemBlockNo = ((LongBlock*)leafBuffer)->Right(); 389 TRACE("Next leaf is at: (%d)\n", fileSystemBlockNo); 390 if (fileSystemBlockNo == -1) 391 break; 392 uint64 readPos = FileSystemBlockToAddr(fileSystemBlockNo); 393 if (read_pos(volume->Device(), readPos, block, len) 394 != len) { 395 ERROR("Extent::FillBlockBuffer(): IO Error"); 396 return B_IO_ERROR; 397 } 398 } 399 TRACE("Total covered: (%d)\n", indexIntoExtents); 400 return B_OK; 401 } 402 403 404 status_t 405 Inode::ReadExtents() 406 { 407 if (fExtents != NULL) 408 return B_OK; 409 if (Format() == XFS_DINODE_FMT_BTREE) 410 return ReadExtentsFromTreeInode(); 411 if (Format() == XFS_DINODE_FMT_EXTENTS) 412 return ReadExtentsFromExtentBasedInode(); 413 return B_BAD_VALUE; 414 } 415 416 417 int 418 Inode::SearchMapInAllExtent(int blockNo) 419 { 420 for (int i = 0; i < DataExtentsCount(); i++) { 421 if (fExtents[i].br_startoff <= blockNo 422 && (blockNo <= fExtents[i].br_startoff 423 + fExtents[i].br_blockcount - 1)) { 424 // Map found 425 return i; 426 } 427 } 428 return -1; 429 } 430 431 432 status_t 433 Inode::ReadAt(off_t pos, uint8* buffer, size_t* length) 434 { 435 TRACE("Inode::ReadAt: pos:(%ld), *length:(%ld)\n", pos, *length); 436 status_t status; 437 if (fExtents == NULL) { 438 status = ReadExtents(); 439 if (status != B_OK) 440 return status; 441 } 442 443 // set/check boundaries for pos/length 444 if (pos < 0) { 445 ERROR("inode %" B_PRIdINO ": ReadAt failed(pos %" B_PRIdOFF 446 ", length %lu)\n", ID(), pos, length); 447 return B_BAD_VALUE; 448 } 449 450 if (pos >= Size() || length == 0) { 451 TRACE("inode %" B_PRIdINO ": ReadAt 0 (pos %" B_PRIdOFF 452 ", length %lu)\n", ID(), pos, length); 453 *length = 0; 454 return B_NO_ERROR; 455 } 456 457 uint32 blockNo = BLOCKNO_FROM_POSITION(pos, GetVolume()); 458 uint32 offsetIntoBlock = BLOCKOFFSET_FROM_POSITION(pos, this); 459 460 size_t lengthOfBlock = BlockSize(); 461 char* block = new(std::nothrow) char[lengthOfBlock]; 462 if (block == NULL) 463 return B_NO_MEMORY; 464 465 ArrayDeleter<char> blockDeleter(block); 466 467 size_t lengthRead = 0; 468 size_t lengthLeftInFile; 469 size_t lengthLeftInBlock; 470 size_t lengthToRead; 471 TRACE("What is blockLen:(%d)\n", lengthOfBlock); 472 while (*length > 0) { 473 TRACE("Inode::ReadAt: pos:(%ld), *length:(%ld)\n", pos, *length); 474 // As long as you can read full blocks, read. 475 lengthLeftInFile = Size() - pos; 476 lengthLeftInBlock = lengthOfBlock - offsetIntoBlock; 477 478 // We could be almost at the end of the file 479 if (lengthLeftInFile <= lengthLeftInBlock) 480 lengthToRead = lengthLeftInFile; 481 else lengthToRead = lengthLeftInBlock; 482 483 // But we might not be able to read all of the 484 // data because of less buffer length 485 if (lengthToRead > *length) 486 lengthToRead = *length; 487 488 int indexForMap = SearchMapInAllExtent(blockNo); 489 if (indexForMap == -1) 490 return B_BAD_VALUE; 491 492 xfs_daddr_t readPos 493 = FileSystemBlockToAddr(fExtents[indexForMap].br_startblock 494 + blockNo - fExtents[indexForMap].br_startoff); 495 496 if (read_pos(GetVolume()->Device(), readPos, block, lengthOfBlock) 497 != lengthOfBlock) { 498 ERROR("TreeDirectory::FillBlockBuffer(): IO Error"); 499 return B_IO_ERROR; 500 } 501 502 503 memcpy((void*) (buffer + lengthRead), 504 (void*)(block + offsetIntoBlock), lengthToRead); 505 506 pos += lengthToRead; 507 *length -= lengthToRead; 508 lengthRead += lengthToRead; 509 blockNo = BLOCKNO_FROM_POSITION(pos, GetVolume()); 510 offsetIntoBlock = BLOCKOFFSET_FROM_POSITION(pos, this); 511 } 512 513 TRACE("lengthRead:(%d)\n", lengthRead); 514 *length = lengthRead; 515 return B_OK; 516 } 517 518 519 status_t 520 Inode::GetFromDisk() 521 { 522 xfs_agnumber_t agNo = INO_TO_AGNO(fId, fVolume); 523 // Get the AG number from the inode 524 uint32 agRelativeInodeNo = INO_TO_AGINO(fId, fVolume->AgInodeBits()); 525 // AG relative ino # 526 xfs_agblock_t agBlock = INO_TO_AGBLOCK(agRelativeInodeNo, fVolume); 527 // AG relative block number 528 xfs_off_t offset = INO_TO_BLOCKOFFSET(fId, fVolume); 529 // Offset into the block1 530 uint32 len = fVolume->InodeSize(); 531 // Inode len to read (size of inode) 532 533 TRACE("AgNumber: (%d), AgRelativeIno: (%d), AgRelativeBlockNum: (%d)," 534 "Offset: (%d), len: (%d)\n", agNo, 535 agRelativeInodeNo, agBlock, offset, len); 536 537 if (agNo > fVolume->AgCount()) { 538 ERROR("Inode::GetFromDisk : AG Number more than number of AGs"); 539 return B_ENTRY_NOT_FOUND; 540 } 541 542 xfs_agblock_t numberOfBlocksInAg = fVolume->AgBlocks(); 543 544 xfs_fsblock_t blockToRead = FSBLOCKS_TO_BASICBLOCKS(fVolume->BlockLog(), 545 ((uint64)(agNo * numberOfBlocksInAg) + agBlock)); 546 547 xfs_daddr_t readPos = blockToRead * BASICBLOCKSIZE + offset * len; 548 549 if (read_pos(fVolume->Device(), readPos, fBuffer, len) != len) { 550 ERROR("Inode::Inode(): IO Error"); 551 return B_IO_ERROR; 552 } 553 554 memcpy(fNode, fBuffer, INODE_CORE_UNLINKED_SIZE); 555 fNode->SwapEndian(); 556 557 return B_OK; 558 } 559 560 561 uint64 562 Inode::FileSystemBlockToAddr(uint64 block) 563 { 564 xfs_agblock_t numberOfBlocksInAg = fVolume->AgBlocks(); 565 566 uint64 agNo = FSBLOCKS_TO_AGNO(block, fVolume); 567 uint64 agBlockNo = FSBLOCKS_TO_AGBLOCKNO(block, fVolume); 568 569 xfs_fsblock_t actualBlockToRead = 570 FSBLOCKS_TO_BASICBLOCKS(fVolume->BlockLog(), 571 ((uint64)(agNo * numberOfBlocksInAg) + agBlockNo)); 572 TRACE("blockToRead:(%d)\n", actualBlockToRead); 573 574 uint64 readPos = actualBlockToRead * (BASICBLOCKSIZE); 575 return readPos; 576 } 577 578 579 /* 580 * Basically take 4 characters at a time as long as you can, and xor with 581 * previous hashVal after rotating 4 bits of hashVal. Likewise, continue 582 * xor and rotating. This is quite a generic hash function. 583 */ 584 uint32 585 hashfunction(const char* name, int length) 586 { 587 uint32 hashVal = 0; 588 int lengthCovered = 0; 589 int index = 0; 590 if (length >= 4) { 591 for (; index < length && (length - index) >= 4; index += 4) 592 { 593 lengthCovered += 4; 594 hashVal = (name[index] << 21) ^ (name[index + 1] << 14) 595 ^ (name[index + 2] << 7) ^ (name[index + 3] << 0) 596 ^ ((hashVal << 28) | (hashVal >> 4)); 597 } 598 } 599 600 int leftToCover = length - lengthCovered; 601 if (leftToCover == 3) { 602 hashVal = (name[index] << 14) ^ (name[index + 1] << 7) 603 ^ (name[index + 2] << 0) ^ ((hashVal << 21) | (hashVal >> 11)); 604 } 605 if (leftToCover == 2) { 606 hashVal = (name[index] << 7) ^ (name[index + 1] << 0) 607 ^ ((hashVal << 14) | (hashVal >> (32 - 14))); 608 } 609 if (leftToCover == 1) { 610 hashVal = (name[index] << 0) 611 ^ ((hashVal << 7) | (hashVal >> (32 - 7))); 612 } 613 614 return hashVal; 615 } 616