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 fId(id), 144 fVolume(volume), 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 ssize_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:(%" B_PRIu16 ")\n", levelsInTree); 304 305 TreePointer* ptrToNode = GetPtrFromRoot(1); 306 uint64 fileSystemBlockNo = B_BENDIAN_TO_HOST_INT64(*ptrToNode); 307 uint64 readPos = FileSystemBlockToAddr(fileSystemBlockNo); 308 // Go down the tree by taking the leftmost pointer to the first leaf 309 while (levelsInTree != 1) { 310 fileSystemBlockNo = B_BENDIAN_TO_HOST_INT64(*ptrToNode); 311 // The fs block that contains node at next lower level. Now read. 312 readPos = FileSystemBlockToAddr(fileSystemBlockNo); 313 if (read_pos(volume->Device(), readPos, node, len) != len) { 314 ERROR("Extent::FillBlockBuffer(): IO Error"); 315 return B_IO_ERROR; 316 } 317 LongBlock* curLongBlock = (LongBlock*)node; 318 ASSERT(curLongBlock->Magic() == XFS_BMAP_MAGIC); 319 ptrToNode = GetPtrFromNode(1, (void*)curLongBlock); 320 // Get's the first pointer. This points to next node. 321 levelsInTree--; 322 } 323 // Next level wil contain leaf nodes. Now Read Directory Buffer 324 len = DirBlockSize; 325 if (read_pos(volume->Device(), readPos, block, len) 326 != len) { 327 ERROR("Extent::FillBlockBuffer(): IO Error"); 328 return B_IO_ERROR; 329 } 330 levelsInTree--; 331 if (levelsInTree != 0) 332 return B_BAD_VALUE; 333 return B_OK; 334 } 335 336 337 status_t 338 Inode::ReadExtentsFromTreeInode() 339 { 340 fExtents = new(std::nothrow) ExtentMapEntry[DataExtentsCount()]; 341 BlockInDataFork* root = new(std::nothrow) BlockInDataFork; 342 if (root == NULL) 343 return B_NO_MEMORY; 344 memcpy((void*)root, 345 DIR_DFORK_PTR(Buffer()), sizeof(BlockInDataFork)); 346 347 size_t maxRecords = MaxRecordsPossibleInTreeRoot(); 348 TRACE("Maxrecords: (%" B_PRIuSIZE ")\n", maxRecords); 349 350 uint16 levelsInTree = root->Levels(); 351 delete root; 352 353 Volume* volume = GetVolume(); 354 ssize_t len = volume->BlockSize(); 355 356 len = DirBlockSize(); 357 char* block = new(std::nothrow) char[len]; 358 if (block == NULL) 359 return B_NO_MEMORY; 360 361 ArrayDeleter<char> blockDeleter(block); 362 363 GetNodefromTree(levelsInTree, volume, len, DirBlockSize(), block); 364 365 uint64 fileSystemBlockNo; 366 uint64 wrappedExtent[2]; 367 int indexIntoExtents = 0; 368 // We should be at the left most leaf node. 369 // This could be a multilevel node type directory 370 while (1) { 371 // Run till you have leaf blocks to checkout 372 char* leafBuffer = block; 373 ASSERT(((LongBlock*)leafBuffer)->Magic() == XFS_BMAP_MAGIC); 374 uint32 offset = sizeof(LongBlock); 375 int numRecs = ((LongBlock*)leafBuffer)->NumRecs(); 376 377 for (int i = 0; i < numRecs; i++) { 378 wrappedExtent[0] = *(uint64*)(leafBuffer + offset); 379 wrappedExtent[1] 380 = *(uint64*)(leafBuffer + offset + sizeof(uint64)); 381 offset += sizeof(ExtentMapUnwrap); 382 UnWrapExtentFromWrappedEntry(wrappedExtent, 383 &fExtents[indexIntoExtents]); 384 indexIntoExtents++; 385 } 386 387 fileSystemBlockNo = ((LongBlock*)leafBuffer)->Right(); 388 TRACE("Next leaf is at: (%" B_PRIu64 ")\n", fileSystemBlockNo); 389 if (fileSystemBlockNo == (uint64) -1) 390 break; 391 uint64 readPos = FileSystemBlockToAddr(fileSystemBlockNo); 392 if (read_pos(volume->Device(), readPos, block, len) 393 != len) { 394 ERROR("Extent::FillBlockBuffer(): IO Error"); 395 return B_IO_ERROR; 396 } 397 } 398 TRACE("Total covered: (%" B_PRId32 ")\n", indexIntoExtents); 399 return B_OK; 400 } 401 402 403 status_t 404 Inode::ReadExtents() 405 { 406 if (fExtents != NULL) 407 return B_OK; 408 if (Format() == XFS_DINODE_FMT_BTREE) 409 return ReadExtentsFromTreeInode(); 410 if (Format() == XFS_DINODE_FMT_EXTENTS) 411 return ReadExtentsFromExtentBasedInode(); 412 return B_BAD_VALUE; 413 } 414 415 416 int 417 Inode::SearchMapInAllExtent(uint64 blockNo) 418 { 419 for (int i = 0; i < DataExtentsCount(); i++) { 420 if (fExtents[i].br_startoff <= blockNo 421 && (blockNo <= fExtents[i].br_startoff 422 + fExtents[i].br_blockcount - 1)) { 423 // Map found 424 return i; 425 } 426 } 427 return -1; 428 } 429 430 431 status_t 432 Inode::ReadAt(off_t pos, uint8* buffer, size_t* length) 433 { 434 TRACE("Inode::ReadAt: pos:(%" B_PRIdOFF "), *length:(%" B_PRIuSIZE ")\n", pos, *length); 435 status_t status; 436 if (fExtents == NULL) { 437 status = ReadExtents(); 438 if (status != B_OK) 439 return status; 440 } 441 442 // set/check boundaries for pos/length 443 if (pos < 0) { 444 ERROR("inode %" B_PRIdINO ": ReadAt failed(pos %" B_PRIdOFF 445 ", length %lu)\n", ID(), pos, *length); 446 return B_BAD_VALUE; 447 } 448 449 if (pos >= Size() || length == 0) { 450 TRACE("inode %" B_PRIdINO ": ReadAt 0 (pos %" B_PRIdOFF 451 ", length %" B_PRIuSIZE ")\n", ID(), pos, *length); 452 *length = 0; 453 return B_NO_ERROR; 454 } 455 456 uint32 blockNo = BLOCKNO_FROM_POSITION(pos, GetVolume()); 457 uint32 offsetIntoBlock = BLOCKOFFSET_FROM_POSITION(pos, this); 458 459 ssize_t lengthOfBlock = BlockSize(); 460 char* block = new(std::nothrow) char[lengthOfBlock]; 461 if (block == NULL) 462 return B_NO_MEMORY; 463 464 ArrayDeleter<char> blockDeleter(block); 465 466 size_t lengthRead = 0; 467 size_t lengthLeftInFile; 468 size_t lengthLeftInBlock; 469 size_t lengthToRead; 470 TRACE("What is blockLen:(%" B_PRId64 ")\n", lengthOfBlock); 471 while (*length > 0) { 472 TRACE("Inode::ReadAt: pos:(%" B_PRIdOFF "), *length:(%" B_PRIuSIZE ")\n", pos, *length); 473 // As long as you can read full blocks, read. 474 lengthLeftInFile = Size() - pos; 475 lengthLeftInBlock = lengthOfBlock - offsetIntoBlock; 476 477 // We could be almost at the end of the file 478 if (lengthLeftInFile <= lengthLeftInBlock) 479 lengthToRead = lengthLeftInFile; 480 else lengthToRead = lengthLeftInBlock; 481 482 // But we might not be able to read all of the 483 // data because of less buffer length 484 if (lengthToRead > *length) 485 lengthToRead = *length; 486 487 int indexForMap = SearchMapInAllExtent(blockNo); 488 if (indexForMap == -1) 489 return B_BAD_VALUE; 490 491 xfs_daddr_t readPos 492 = FileSystemBlockToAddr(fExtents[indexForMap].br_startblock 493 + blockNo - fExtents[indexForMap].br_startoff); 494 495 if (read_pos(GetVolume()->Device(), readPos, block, lengthOfBlock) 496 != lengthOfBlock) { 497 ERROR("TreeDirectory::FillBlockBuffer(): IO Error"); 498 return B_IO_ERROR; 499 } 500 501 502 memcpy((void*) (buffer + lengthRead), 503 (void*)(block + offsetIntoBlock), lengthToRead); 504 505 pos += lengthToRead; 506 *length -= lengthToRead; 507 lengthRead += lengthToRead; 508 blockNo = BLOCKNO_FROM_POSITION(pos, GetVolume()); 509 offsetIntoBlock = BLOCKOFFSET_FROM_POSITION(pos, this); 510 } 511 512 TRACE("lengthRead:(%" B_PRIuSIZE ")\n", lengthRead); 513 *length = lengthRead; 514 return B_OK; 515 } 516 517 518 status_t 519 Inode::GetFromDisk() 520 { 521 xfs_agnumber_t agNo = INO_TO_AGNO(fId, fVolume); 522 // Get the AG number from the inode 523 uint32 agRelativeInodeNo = INO_TO_AGINO(fId, fVolume->AgInodeBits()); 524 // AG relative ino # 525 xfs_agblock_t agBlock = INO_TO_AGBLOCK(agRelativeInodeNo, fVolume); 526 // AG relative block number 527 xfs_off_t offset = INO_TO_BLOCKOFFSET(fId, fVolume); 528 // Offset into the block1 529 uint32 len = fVolume->InodeSize(); 530 // Inode len to read (size of inode) 531 532 TRACE("AgNumber: (%" B_PRIu32 "), AgRelativeIno: (%" B_PRIu32 ")," 533 "AgRelativeBlockNum: (%" B_PRIu32 "),Offset: (%" B_PRId64 ")," 534 "len: (%" B_PRIu32 ")\n", agNo,agRelativeInodeNo, agBlock, offset, len); 535 536 if (agNo > fVolume->AgCount()) { 537 ERROR("Inode::GetFromDisk : AG Number more than number of AGs"); 538 return B_ENTRY_NOT_FOUND; 539 } 540 541 xfs_agblock_t numberOfBlocksInAg = fVolume->AgBlocks(); 542 543 xfs_fsblock_t blockToRead = FSBLOCKS_TO_BASICBLOCKS(fVolume->BlockLog(), 544 ((uint64)(agNo * numberOfBlocksInAg) + agBlock)); 545 546 xfs_daddr_t readPos = blockToRead * BASICBLOCKSIZE + offset * len; 547 548 if (read_pos(fVolume->Device(), readPos, fBuffer, len) != len) { 549 ERROR("Inode::Inode(): IO Error"); 550 return B_IO_ERROR; 551 } 552 553 memcpy(fNode, fBuffer, INODE_CORE_UNLINKED_SIZE); 554 fNode->SwapEndian(); 555 556 return B_OK; 557 } 558 559 560 uint64 561 Inode::FileSystemBlockToAddr(uint64 block) 562 { 563 xfs_agblock_t numberOfBlocksInAg = fVolume->AgBlocks(); 564 565 uint64 agNo = FSBLOCKS_TO_AGNO(block, fVolume); 566 uint64 agBlockNo = FSBLOCKS_TO_AGBLOCKNO(block, fVolume); 567 568 xfs_fsblock_t actualBlockToRead = 569 FSBLOCKS_TO_BASICBLOCKS(fVolume->BlockLog(), 570 ((uint64)(agNo * numberOfBlocksInAg) + agBlockNo)); 571 TRACE("blockToRead:(%" B_PRIu64 ")\n", actualBlockToRead); 572 573 uint64 readPos = actualBlockToRead * (BASICBLOCKSIZE); 574 return readPos; 575 } 576 577 578 /* 579 * Basically take 4 characters at a time as long as you can, and xor with 580 * previous hashVal after rotating 4 bits of hashVal. Likewise, continue 581 * xor and rotating. This is quite a generic hash function. 582 */ 583 uint32 584 hashfunction(const char* name, int length) 585 { 586 uint32 hashVal = 0; 587 int lengthCovered = 0; 588 int index = 0; 589 if (length >= 4) { 590 for (; index < length && (length - index) >= 4; index += 4) 591 { 592 lengthCovered += 4; 593 hashVal = (name[index] << 21) ^ (name[index + 1] << 14) 594 ^ (name[index + 2] << 7) ^ (name[index + 3] << 0) 595 ^ ((hashVal << 28) | (hashVal >> 4)); 596 } 597 } 598 599 int leftToCover = length - lengthCovered; 600 if (leftToCover == 3) { 601 hashVal = (name[index] << 14) ^ (name[index + 1] << 7) 602 ^ (name[index + 2] << 0) ^ ((hashVal << 21) | (hashVal >> 11)); 603 } 604 if (leftToCover == 2) { 605 hashVal = (name[index] << 7) ^ (name[index + 1] << 0) 606 ^ ((hashVal << 14) | (hashVal >> (32 - 14))); 607 } 608 if (leftToCover == 1) { 609 hashVal = (name[index] << 0) 610 ^ ((hashVal << 7) | (hashVal >> (32 - 7))); 611 } 612 613 return hashVal; 614 } 615