1/* 2 * Copyright 2022, Raghav Sharma, raghavself28@gmail.com 3 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com 4 * All rights reserved. Distributed under the terms of the MIT License. 5 */ 6 7 8#include "LeafDirectory.h" 9 10#include "VerifyHeader.h" 11 12 13LeafDirectory::LeafDirectory(Inode* inode) 14 : 15 fInode(inode), 16 fDataMap(NULL), 17 fLeafMap(NULL), 18 fOffset(0), 19 fDataBuffer(NULL), 20 fLeafBuffer(NULL), 21 fCurBlockNumber(-1) 22{ 23} 24 25 26LeafDirectory::~LeafDirectory() 27{ 28 delete fDataMap; 29 delete fLeafMap; 30 delete fDataBuffer; 31 delete fLeafBuffer; 32} 33 34 35status_t 36LeafDirectory::Init() 37{ 38 fLeafMap = new(std::nothrow) ExtentMapEntry; 39 if (fLeafMap == NULL) 40 return B_NO_MEMORY; 41 42 fDataMap = new(std::nothrow) ExtentMapEntry; 43 if (fDataMap == NULL) 44 return B_NO_MEMORY; 45 46 FillMapEntry(fInode->DataExtentsCount()-1, fLeafMap); 47 FillMapEntry(0, fDataMap); 48 49 // check data buffer 50 status_t status = FillBuffer(DATA, fDataBuffer, 0); 51 if (status != B_OK) 52 return status; 53 ExtentDataHeader* data = ExtentDataHeader::Create(fInode, fDataBuffer); 54 if (data == NULL) 55 return B_NO_MEMORY; 56 if (!VerifyHeader<ExtentDataHeader>(data, fDataBuffer, fInode, 0, fDataMap, XFS_LEAF)) { 57 ERROR("Invalid data header"); 58 delete data; 59 return B_BAD_VALUE; 60 } 61 delete data; 62 63 // check leaf buffer 64 status = FillBuffer(LEAF, fLeafBuffer, 0); 65 if (status != B_OK) 66 return status; 67 ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fLeafBuffer); 68 if (leaf == NULL) 69 return B_NO_MEMORY; 70 if (!VerifyHeader<ExtentLeafHeader>(leaf, fLeafBuffer, fInode, 0, fLeafMap, XFS_LEAF)) { 71 ERROR("Invalid leaf header"); 72 delete leaf; 73 return B_BAD_VALUE; 74 } 75 delete leaf; 76 77 return B_OK; 78} 79 80 81bool 82LeafDirectory::IsLeafType() 83{ 84 bool status = true; 85 if (fInode->BlockCount() == 1 86 || fInode->DataExtentsCount() == 1 87 || (uint64) fInode->Size() != 88 (fInode->BlockCount() - 1) * fInode->DirBlockSize()) 89 status = false; 90 91 if (status == false) 92 return status; 93 94 void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()); 95 96 uint64* pointerToMap = (uint64*)((char*)directoryFork 97 + (fInode->DataExtentsCount() - 1) * EXTENT_SIZE); 98 99 xfs_fileoff_t startoff = (B_BENDIAN_TO_HOST_INT64(*pointerToMap) & MASK(63)) >> 9; 100 101 if (startoff != LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog())) 102 status = false; 103 104 return status; 105} 106 107 108void 109LeafDirectory::FillMapEntry(int num, ExtentMapEntry* fMap) 110{ 111 void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()); 112 113 uint64* pointerToMap = (uint64*)((char*)directoryFork + num * EXTENT_SIZE); 114 uint64 firstHalf = pointerToMap[0]; 115 uint64 secondHalf = pointerToMap[1]; 116 //dividing the 128 bits into 2 parts. 117 118 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 119 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 120 fMap->br_state = firstHalf >> 63; 121 fMap->br_startoff = (firstHalf & MASK(63)) >> 9; 122 fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 123 fMap->br_blockcount = secondHalf & MASK(21); 124 TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 ")," 125 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock, 126 fMap->br_blockcount, fMap->br_state); 127} 128 129 130status_t 131LeafDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur) 132{ 133 TRACE("FILLBUFFER\n"); 134 ExtentMapEntry* map; 135 if (type == DATA) 136 map = fDataMap; 137 else if (type == LEAF) 138 map = fLeafMap; 139 else 140 return B_BAD_VALUE; 141 142 if (map->br_state !=0) 143 return B_BAD_VALUE; 144 145 int len = fInode->DirBlockSize(); 146 if (blockBuffer == NULL) { 147 blockBuffer = new(std::nothrow) char[len]; 148 if (blockBuffer == NULL) 149 return B_NO_MEMORY; 150 } 151 152 xfs_daddr_t readPos = 153 fInode->FileSystemBlockToAddr(map->br_startblock + howManyBlocksFurthur); 154 155 if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len) 156 != len) { 157 ERROR("LeafDirectory::FillBlockBuffer(): IO Error"); 158 return B_IO_ERROR; 159 } 160 161 if (type == DATA) { 162 fDataBuffer = blockBuffer; 163 } else if (type == LEAF) { 164 fLeafBuffer = blockBuffer; 165 ExtentLeafHeader* header = ExtentLeafHeader::Create(fInode, fLeafBuffer); 166 if (header == NULL) 167 return B_NO_MEMORY; 168 TRACE("NumberOfEntries in leaf: (%" B_PRIu16 ")\n", header->Count()); 169 delete header; 170 } 171 return B_OK; 172} 173 174 175uint32 176LeafDirectory::GetOffsetFromAddress(uint32 address) 177{ 178 address = address * 8; 179 // block offset in eight bytes, hence multiply with 8 180 return address & (fInode->DirBlockSize() - 1); 181} 182 183 184ExtentLeafEntry* 185LeafDirectory::FirstLeaf() 186{ 187 TRACE("LeafDirectory: FirstLeaf\n"); 188 if (fLeafBuffer == NULL) { 189 ASSERT(fLeafMap != NULL); 190 status_t status = FillBuffer(LEAF, fLeafBuffer, 0); 191 if (status != B_OK) 192 return NULL; 193 } 194 return (ExtentLeafEntry*)((char*)fLeafBuffer + ExtentLeafHeader::Size(fInode)); 195} 196 197 198int 199LeafDirectory::EntrySize(int len) const 200{ 201 int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 202 // uint16 is for the tag 203 if (fInode->HasFileTypeField()) 204 entrySize += sizeof(uint8); 205 206 return (entrySize + 7) & -8; 207 // rounding off to closest multiple of 8 208} 209 210 211void 212LeafDirectory::SearchAndFillDataMap(uint64 blockNo) 213{ 214 int len = fInode->DataExtentsCount(); 215 216 for(int i = 0; i < len - 1; i++) { 217 FillMapEntry(i, fDataMap); 218 if (fDataMap->br_startoff <= blockNo 219 && (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1)) 220 // Map found 221 return; 222 } 223} 224 225 226status_t 227LeafDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino) 228{ 229 TRACE("LeafDirectory::GetNext\n"); 230 status_t status; 231 232 if (fDataBuffer == NULL) { 233 status = FillBuffer(DATA, fDataBuffer, 0); 234 if (status != B_OK) 235 return status; 236 } 237 238 Volume* volume = fInode->GetVolume(); 239 240 void* entry; // This could be unused entry so we should check 241 242 entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode)); 243 244 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 245 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) 246 entry = (void*)(fDataBuffer 247 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode)); 248 // This gets us a little faster to the next entry 249 250 uint32 curDirectorySize = fInode->Size(); 251 252 while (fOffset != curDirectorySize) { 253 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 254 255 TRACE("fOffset:(%" B_PRIu32 "), blockNoFromAddress:(%" B_PRIu32 ")\n", 256 fOffset, blockNoFromAddress); 257 if (fCurBlockNumber != blockNoFromAddress 258 && blockNoFromAddress > fDataMap->br_startoff 259 && blockNoFromAddress 260 <= fDataMap->br_startoff + fDataMap->br_blockcount - 1) { 261 // When the block is mapped in the same data 262 // map entry but is not the first block 263 status = FillBuffer(DATA, fDataBuffer, 264 blockNoFromAddress - fDataMap->br_startoff); 265 if (status != B_OK) 266 return status; 267 entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode)); 268 fOffset = fOffset + ExtentDataHeader::Size(fInode); 269 fCurBlockNumber = blockNoFromAddress; 270 } else if (fCurBlockNumber != blockNoFromAddress) { 271 // When the block isn't mapped in the current data map entry 272 SearchAndFillDataMap(blockNoFromAddress); 273 status = FillBuffer(DATA, fDataBuffer, 274 blockNoFromAddress - fDataMap->br_startoff); 275 if (status != B_OK) 276 return status; 277 entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode)); 278 fOffset = fOffset + ExtentDataHeader::Size(fInode); 279 fCurBlockNumber = blockNoFromAddress; 280 } 281 282 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 283 284 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 285 TRACE("Unused entry found\n"); 286 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 287 entry = (void*) 288 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 289 continue; 290 } 291 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 292 293 uint16 currentOffset = (char*)dataEntry - fDataBuffer; 294 TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n", 295 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset); 296 297 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) { 298 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 299 continue; 300 } 301 302 if ((size_t)(dataEntry->namelen) >= *length) 303 return B_BUFFER_OVERFLOW; 304 305 fOffset = fOffset + EntrySize(dataEntry->namelen); 306 memcpy(name, dataEntry->name, dataEntry->namelen); 307 name[dataEntry->namelen] = '\0'; 308 *length = dataEntry->namelen + 1; 309 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 310 311 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n", 312 name, *length, *ino); 313 return B_OK; 314 } 315 316 return B_ENTRY_NOT_FOUND; 317} 318 319 320status_t 321LeafDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino) 322{ 323 TRACE("LeafDirectory: Lookup\n"); 324 TRACE("Name: %s\n", name); 325 uint32 hashValueOfRequest = hashfunction(name, length); 326 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest); 327 328 status_t status = B_OK; 329 if (fLeafBuffer == NULL) 330 status = FillBuffer(LEAF, fLeafBuffer, 0); 331 if (status != B_OK) 332 return status; 333 334 ExtentLeafHeader* leafHeader = ExtentLeafHeader::Create(fInode, fLeafBuffer); 335 if (leafHeader == NULL) 336 return B_NO_MEMORY; 337 338 ExtentLeafEntry* leafEntry = FirstLeaf(); 339 if (leafEntry == NULL) 340 return B_NO_MEMORY; 341 342 int numberOfLeafEntries = leafHeader->Count(); 343 TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries); 344 int left = 0; 345 int right = numberOfLeafEntries - 1; 346 Volume* volume = fInode->GetVolume(); 347 348 hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest); 349 350 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 351 == hashValueOfRequest) { 352 353 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 354 if (address == 0) { 355 left++; 356 continue; 357 } 358 359 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 360 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 361 362 TRACE("DataBlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset); 363 if (dataBlockNumber != fCurBlockNumber) { 364 fCurBlockNumber = dataBlockNumber; 365 SearchAndFillDataMap(dataBlockNumber); 366 status = FillBuffer(DATA, fDataBuffer, 367 dataBlockNumber - fDataMap->br_startoff); 368 if (status != B_OK) 369 return status; 370 } 371 372 TRACE("offset:(%" B_PRIu32 ")\n", offset); 373 ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset); 374 375 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 376 if (retVal == 0) { 377 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 378 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 379 return B_OK; 380 } 381 left++; 382 } 383 384 delete leafHeader; 385 386 return B_ENTRY_NOT_FOUND; 387} 388 389 390ExtentLeafHeader::~ExtentLeafHeader() 391{ 392} 393 394 395/* 396 First see which type of directory we reading then 397 return magic number as per Inode Version. 398*/ 399uint32 400ExtentLeafHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode) 401{ 402 if (WhichDirectory == XFS_LEAF) { 403 if (inode->Version() == 1 || inode->Version() == 2) 404 return V4_LEAF_HEADER_MAGIC; 405 else 406 return V5_LEAF_HEADER_MAGIC; 407 } else { 408 if (inode->Version() == 1 || inode->Version() == 2) 409 return XFS_DIR2_LEAFN_MAGIC; 410 else 411 return XFS_DIR3_LEAFN_MAGIC; 412 } 413} 414 415 416uint32 417ExtentLeafHeader::CRCOffset() 418{ 419 return offsetof(ExtentLeafHeaderV5::OnDiskData, info.crc); 420} 421 422 423ExtentLeafHeader* 424ExtentLeafHeader::Create(Inode* inode, const char* buffer) 425{ 426 if (inode->Version() == 1 || inode->Version() == 2) { 427 ExtentLeafHeaderV4* header = new (std::nothrow) ExtentLeafHeaderV4(buffer); 428 return header; 429 } else { 430 ExtentLeafHeaderV5* header = new (std::nothrow) ExtentLeafHeaderV5(buffer); 431 return header; 432 } 433} 434 435 436/* 437 This Function returns Actual size of leaf header 438 in all forms of directory. 439 Never use sizeof() operator because we now have 440 vtable as well and it will give wrong results 441*/ 442uint32 443ExtentLeafHeader::Size(Inode* inode) 444{ 445 if (inode->Version() == 1 || inode->Version() == 2) 446 return sizeof(ExtentLeafHeaderV4::OnDiskData); 447 else 448 return sizeof(ExtentLeafHeaderV5::OnDiskData); 449} 450 451 452void 453ExtentLeafHeaderV4::SwapEndian() 454{ 455 fData.info.forw = B_BENDIAN_TO_HOST_INT32(fData.info.forw); 456 fData.info.back = B_BENDIAN_TO_HOST_INT32(fData.info.back); 457 fData.info.magic = B_BENDIAN_TO_HOST_INT16(fData.info.magic); 458 fData.info.pad = B_BENDIAN_TO_HOST_INT16(fData.info.pad); 459 fData.count = B_BENDIAN_TO_HOST_INT16(fData.count); 460 fData.stale = B_BENDIAN_TO_HOST_INT16(fData.stale); 461} 462 463 464ExtentLeafHeaderV4::ExtentLeafHeaderV4(const char* buffer) 465{ 466 memcpy(&fData, buffer, sizeof(fData)); 467 SwapEndian(); 468} 469 470 471ExtentLeafHeaderV4::~ExtentLeafHeaderV4() 472{ 473} 474 475 476uint16 477ExtentLeafHeaderV4::Magic() 478{ 479 return fData.info.magic; 480} 481 482 483uint64 484ExtentLeafHeaderV4::Blockno() 485{ 486 return B_BAD_VALUE; 487} 488 489 490uint64 491ExtentLeafHeaderV4::Lsn() 492{ 493 return B_BAD_VALUE; 494} 495 496 497uint64 498ExtentLeafHeaderV4::Owner() 499{ 500 return B_BAD_VALUE; 501} 502 503 504const uuid_t& 505ExtentLeafHeaderV4::Uuid() 506{ 507 static uuid_t nullUuid = {0}; 508 return nullUuid; 509} 510 511 512uint16 513ExtentLeafHeaderV4::Count() 514{ 515 return fData.count; 516} 517 518 519uint32 520ExtentLeafHeaderV4::Forw() 521{ 522 return fData.info.forw; 523} 524 525 526void 527ExtentLeafHeaderV5::SwapEndian() 528{ 529 fData.info.forw = B_BENDIAN_TO_HOST_INT32(fData.info.forw); 530 fData.info.back = B_BENDIAN_TO_HOST_INT32(fData.info.back); 531 fData.info.magic = B_BENDIAN_TO_HOST_INT16(fData.info.magic); 532 fData.info.pad = B_BENDIAN_TO_HOST_INT16(fData.info.pad); 533 fData.info.blkno = B_BENDIAN_TO_HOST_INT64(fData.info.blkno); 534 fData.info.lsn = B_BENDIAN_TO_HOST_INT64(fData.info.lsn); 535 fData.info.owner = B_BENDIAN_TO_HOST_INT64(fData.info.owner); 536 fData.count = B_BENDIAN_TO_HOST_INT16(fData.count); 537 fData.stale = B_BENDIAN_TO_HOST_INT16(fData.stale); 538 fData.pad = B_BENDIAN_TO_HOST_INT32(fData.pad); 539} 540 541 542ExtentLeafHeaderV5::ExtentLeafHeaderV5(const char* buffer) 543{ 544 memcpy(&fData, buffer, sizeof(fData)); 545 SwapEndian(); 546} 547 548 549ExtentLeafHeaderV5::~ExtentLeafHeaderV5() 550{ 551} 552 553 554uint16 555ExtentLeafHeaderV5::Magic() 556{ 557 return fData.info.magic; 558} 559 560 561uint64 562ExtentLeafHeaderV5::Blockno() 563{ 564 return fData.info.blkno; 565} 566 567 568uint64 569ExtentLeafHeaderV5::Lsn() 570{ 571 return fData.info.lsn; 572} 573 574 575uint64 576ExtentLeafHeaderV5::Owner() 577{ 578 return fData.info.owner; 579} 580 581 582const uuid_t& 583ExtentLeafHeaderV5::Uuid() 584{ 585 return fData.info.uuid; 586} 587 588 589uint16 590ExtentLeafHeaderV5::Count() 591{ 592 return fData.count; 593} 594 595 596uint32 597ExtentLeafHeaderV5::Forw() 598{ 599 return fData.info.forw; 600} 601