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 "Extent.h" 9 10#include "VerifyHeader.h" 11 12 13Extent::Extent(Inode* inode) 14 : 15 fInode(inode), 16 fOffset(0) 17{ 18} 19 20 21Extent::~Extent() 22{ 23} 24 25 26void 27Extent::FillMapEntry(void* pointerToMap) 28{ 29 uint64 firstHalf = *((uint64*)pointerToMap); 30 uint64 secondHalf = *((uint64*)pointerToMap + 1); 31 // dividing the 128 bits into 2 parts. 32 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 33 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 34 fMap->br_state = (firstHalf >> 63); 35 fMap->br_startoff = (firstHalf & MASK(63)) >> 9; 36 fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 37 fMap->br_blockcount = (secondHalf & MASK(21)); 38 TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 ")," 39 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock, 40 fMap->br_blockcount, fMap->br_state); 41} 42 43 44status_t 45Extent::FillBlockBuffer() 46{ 47 if (fMap->br_state != 0) 48 return B_BAD_VALUE; 49 50 int len = fInode->DirBlockSize(); 51 fBlockBuffer = new(std::nothrow) char[len]; 52 if (fBlockBuffer == NULL) 53 return B_NO_MEMORY; 54 55 xfs_daddr_t readPos = 56 fInode->FileSystemBlockToAddr(fMap->br_startblock); 57 58 if (read_pos(fInode->GetVolume()->Device(), readPos, fBlockBuffer, len) 59 != len) { 60 ERROR("Extent::FillBlockBuffer(): IO Error"); 61 return B_IO_ERROR; 62 } 63 64 return B_OK; 65} 66 67 68status_t 69Extent::Init() 70{ 71 fMap = new(std::nothrow) ExtentMapEntry; 72 if (fMap == NULL) 73 return B_NO_MEMORY; 74 75 ASSERT(IsBlockType() == true); 76 void* pointerToMap = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()); 77 FillMapEntry(pointerToMap); 78 ASSERT(fMap->br_blockcount == 1); 79 // TODO: This is always true for block directories 80 // If we use this implementation for leaf directories, this is not 81 // always true 82 status_t status = FillBlockBuffer(); 83 if (status != B_OK) 84 return status; 85 86 ExtentDataHeader* header = ExtentDataHeader::Create(fInode, fBlockBuffer); 87 if (header == NULL) 88 return B_NO_MEMORY; 89 if (!VerifyHeader<ExtentDataHeader>(header, fBlockBuffer, fInode, 0, fMap, XFS_BLOCK)) { 90 status = B_BAD_VALUE; 91 ERROR("Extent:Init(): Bad Block!\n"); 92 } 93 94 delete header; 95 return status; 96} 97 98 99ExtentBlockTail* 100Extent::BlockTail() 101{ 102 return (ExtentBlockTail*) 103 (fBlockBuffer + fInode->DirBlockSize() - sizeof(ExtentBlockTail)); 104} 105 106 107uint32 108Extent::GetOffsetFromAddress(uint32 address) 109{ 110 address = address * 8; 111 // block offset in eight bytes, hence multiple with 8 112 return address & (fInode->DirBlockSize() - 1); 113} 114 115 116ExtentLeafEntry* 117Extent::BlockFirstLeaf(ExtentBlockTail* tail) 118{ 119 return (ExtentLeafEntry*)tail - B_BENDIAN_TO_HOST_INT32(tail->count); 120} 121 122 123bool 124Extent::IsBlockType() 125{ 126 bool status = true; 127 if (fInode->BlockCount() != 1) 128 status = false; 129 if (fInode->Size() != fInode->DirBlockSize()) 130 status = false; 131 void* pointerToMap = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize()); 132 xfs_fileoff_t startoff = (*((uint64*)pointerToMap) & MASK(63)) >> 9; 133 if (startoff != 0) 134 status = false; 135 return status; 136} 137 138 139int 140Extent::EntrySize(int len) const 141{ 142 int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 143 // uint16 is for the tag 144 if (fInode->HasFileTypeField()) 145 entrySize += sizeof(uint8); 146 147 return (entrySize + 7) & -8; 148 // rounding off to closest multiple of 8 149} 150 151 152status_t 153Extent::GetNext(char* name, size_t* length, xfs_ino_t* ino) 154{ 155 TRACE("Extend::GetNext\n"); 156 157 void* entry; // This could be unused entry so we should check 158 159 entry = (void*)(fBlockBuffer + ExtentDataHeader::Size(fInode)); 160 161 int numberOfEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->count); 162 int numberOfStaleEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->stale); 163 164 // We don't read stale entries. 165 numberOfEntries -= numberOfStaleEntries; 166 TRACE("numberOfEntries:(%" B_PRId32 ")\n", numberOfEntries); 167 uint16 currentOffset = (char*)entry - fBlockBuffer; 168 169 for (int i = 0; i < numberOfEntries; i++) { 170 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 171 172 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 173 TRACE("Unused entry found\n"); 174 currentOffset += B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 175 entry = (void*) 176 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 177 i--; 178 continue; 179 } 180 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 181 182 if (fOffset >= currentOffset) { 183 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 184 currentOffset += EntrySize(dataEntry->namelen); 185 continue; 186 } 187 188 if ((size_t)(dataEntry->namelen) >= *length) 189 return B_BUFFER_OVERFLOW; 190 191 fOffset = currentOffset; 192 memcpy(name, dataEntry->name, dataEntry->namelen); 193 name[dataEntry->namelen] = '\0'; 194 *length = dataEntry->namelen + 1; 195 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 196 197 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n", name, 198 *length, *ino); 199 return B_OK; 200 } 201 202 return B_ENTRY_NOT_FOUND; 203} 204 205 206status_t 207Extent::Lookup(const char* name, size_t length, xfs_ino_t* ino) 208{ 209 TRACE("Extent: Lookup\n"); 210 TRACE("Name: %s\n", name); 211 uint32 hashValueOfRequest = hashfunction(name, length); 212 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest); 213 ExtentBlockTail* blockTail = BlockTail(); 214 ExtentLeafEntry* leafEntry = BlockFirstLeaf(blockTail); 215 216 int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT32(blockTail->count); 217 int left = 0; 218 int right = numberOfLeafEntries - 1; 219 220 hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest); 221 222 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 223 == hashValueOfRequest) { 224 225 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 226 if (address == 0) { 227 left++; 228 continue; 229 } 230 231 uint32 offset = GetOffsetFromAddress(address); 232 TRACE("offset:(%" B_PRIu32 ")\n", offset); 233 ExtentDataEntry* entry = (ExtentDataEntry*)(fBlockBuffer + offset); 234 235 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 236 if (retVal == 0) { 237 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 238 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 239 return B_OK; 240 } 241 left++; 242 } 243 244 return B_ENTRY_NOT_FOUND; 245} 246 247 248ExtentDataHeader::~ExtentDataHeader() 249{ 250} 251 252 253/* 254 First see which type of directory we reading then 255 return magic number as per Inode Version. 256*/ 257uint32 258ExtentDataHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode) 259{ 260 if (WhichDirectory == XFS_BLOCK) { 261 if (inode->Version() == 1 || inode->Version() == 2) 262 return DIR2_BLOCK_HEADER_MAGIC; 263 else 264 return DIR3_BLOCK_HEADER_MAGIC; 265 } else { 266 if (inode->Version() == 1 || inode->Version() == 2) 267 return V4_DATA_HEADER_MAGIC; 268 else 269 return V5_DATA_HEADER_MAGIC; 270 } 271} 272 273 274uint32 275ExtentDataHeader::CRCOffset() 276{ 277 return offsetof(ExtentDataHeaderV5::OnDiskData, crc); 278} 279 280 281ExtentDataHeader* 282ExtentDataHeader::Create(Inode* inode, const char* buffer) 283{ 284 if (inode->Version() == 1 || inode->Version() == 2) { 285 ExtentDataHeaderV4* header = new (std::nothrow) ExtentDataHeaderV4(buffer); 286 return header; 287 } else { 288 ExtentDataHeaderV5* header = new (std::nothrow) ExtentDataHeaderV5(buffer); 289 return header; 290 } 291} 292 293 294/* 295 This Function returns Actual size of data header 296 in all forms of directory. 297 Never use sizeof() operator because we now have 298 vtable as well and it will give wrong results 299*/ 300uint32 301ExtentDataHeader::Size(Inode* inode) 302{ 303 if (inode->Version() == 1 || inode->Version() == 2) 304 return sizeof(ExtentDataHeaderV4::OnDiskData); 305 else 306 return sizeof(ExtentDataHeaderV5::OnDiskData); 307} 308 309 310void 311ExtentDataHeaderV4::_SwapEndian() 312{ 313 fData.magic = (B_BENDIAN_TO_HOST_INT32(fData.magic)); 314} 315 316 317ExtentDataHeaderV4::ExtentDataHeaderV4(const char* buffer) 318{ 319 memcpy(&fData, buffer, sizeof(fData)); 320 _SwapEndian(); 321} 322 323 324ExtentDataHeaderV4::~ExtentDataHeaderV4() 325{ 326} 327 328 329uint32 330ExtentDataHeaderV4::Magic() 331{ 332 return fData.magic; 333} 334 335 336uint64 337ExtentDataHeaderV4::Blockno() 338{ 339 return B_BAD_VALUE; 340} 341 342 343uint64 344ExtentDataHeaderV4::Lsn() 345{ 346 return B_BAD_VALUE; 347} 348 349 350uint64 351ExtentDataHeaderV4::Owner() 352{ 353 return B_BAD_VALUE; 354} 355 356 357const uuid_t& 358ExtentDataHeaderV4::Uuid() 359{ 360 static uuid_t nullUuid; 361 return nullUuid; 362} 363 364 365void 366ExtentDataHeaderV5::_SwapEndian() 367{ 368 fData.magic = B_BENDIAN_TO_HOST_INT32(fData.magic); 369 fData.blkno = B_BENDIAN_TO_HOST_INT64(fData.blkno); 370 fData.lsn = B_BENDIAN_TO_HOST_INT64(fData.lsn); 371 fData.owner = B_BENDIAN_TO_HOST_INT64(fData.owner); 372 fData.pad = B_BENDIAN_TO_HOST_INT32(fData.pad); 373} 374 375 376ExtentDataHeaderV5::ExtentDataHeaderV5(const char* buffer) 377{ 378 memcpy(&fData, buffer, sizeof(fData)); 379 _SwapEndian(); 380} 381 382 383ExtentDataHeaderV5::~ExtentDataHeaderV5() 384{ 385} 386 387 388uint32 389ExtentDataHeaderV5::Magic() 390{ 391 return fData.magic; 392} 393 394 395uint64 396ExtentDataHeaderV5::Blockno() 397{ 398 return fData.blkno; 399} 400 401 402uint64 403ExtentDataHeaderV5::Lsn() 404{ 405 return fData.lsn; 406} 407 408 409uint64 410ExtentDataHeaderV5::Owner() 411{ 412 return fData.owner; 413} 414 415 416const uuid_t& 417ExtentDataHeaderV5::Uuid() 418{ 419 return fData.uuid; 420} 421