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 13 Extent::Extent(Inode* inode) 14 : 15 fInode(inode), 16 fOffset(0) 17 { 18 } 19 20 21 Extent::~Extent() 22 { 23 } 24 25 26 void 27 Extent::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 44 status_t 45 Extent::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 68 status_t 69 Extent::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 99 ExtentBlockTail* 100 Extent::BlockTail() 101 { 102 return (ExtentBlockTail*) 103 (fBlockBuffer + fInode->DirBlockSize() - sizeof(ExtentBlockTail)); 104 } 105 106 107 uint32 108 Extent::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 116 ExtentLeafEntry* 117 Extent::BlockFirstLeaf(ExtentBlockTail* tail) 118 { 119 return (ExtentLeafEntry*)tail - B_BENDIAN_TO_HOST_INT32(tail->count); 120 } 121 122 123 bool 124 Extent::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 139 int 140 Extent::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 152 status_t 153 Extent::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 206 status_t 207 Extent::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 248 ExtentDataHeader::~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 */ 257 uint32 258 ExtentDataHeader::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 274 uint32 275 ExtentDataHeader::CRCOffset() 276 { 277 return XFS_EXTENT_CRC_OFF - XFS_EXTENT_V5_VPTR_OFF; 278 } 279 280 281 ExtentDataHeader* 282 ExtentDataHeader::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 */ 300 uint32 301 ExtentDataHeader::Size(Inode* inode) 302 { 303 if (inode->Version() == 1 || inode->Version() == 2) 304 return sizeof(ExtentDataHeaderV4) - XFS_EXTENT_V4_VPTR_OFF; 305 else 306 return sizeof(ExtentDataHeaderV5) - XFS_EXTENT_V5_VPTR_OFF; 307 } 308 309 310 void 311 ExtentDataHeaderV4::SwapEndian() 312 { 313 magic = B_BENDIAN_TO_HOST_INT32(magic); 314 } 315 316 317 ExtentDataHeaderV4::ExtentDataHeaderV4(const char* buffer) 318 { 319 uint32 offset = 0; 320 321 magic = *(uint32*)(buffer + offset); 322 offset += sizeof(uint32); 323 324 memcpy(bestfree, buffer + offset, XFS_DIR2_DATA_FD_COUNT * sizeof(FreeRegion)); 325 326 SwapEndian(); 327 } 328 329 330 ExtentDataHeaderV4::~ExtentDataHeaderV4() 331 { 332 } 333 334 335 uint32 336 ExtentDataHeaderV4::Magic() 337 { 338 return magic; 339 } 340 341 342 uint64 343 ExtentDataHeaderV4::Blockno() 344 { 345 return B_BAD_VALUE; 346 } 347 348 349 uint64 350 ExtentDataHeaderV4::Lsn() 351 { 352 return B_BAD_VALUE; 353 } 354 355 356 uint64 357 ExtentDataHeaderV4::Owner() 358 { 359 return B_BAD_VALUE; 360 } 361 362 363 uuid_t* 364 ExtentDataHeaderV4::Uuid() 365 { 366 return NULL; 367 } 368 369 370 void 371 ExtentDataHeaderV5::SwapEndian() 372 { 373 magic = B_BENDIAN_TO_HOST_INT32(magic); 374 blkno = B_BENDIAN_TO_HOST_INT64(blkno); 375 lsn = B_BENDIAN_TO_HOST_INT64(lsn); 376 owner = B_BENDIAN_TO_HOST_INT64(owner); 377 pad = B_BENDIAN_TO_HOST_INT32(pad); 378 } 379 380 381 ExtentDataHeaderV5::ExtentDataHeaderV5(const char* buffer) 382 { 383 uint32 offset = 0; 384 385 magic = *(uint32*)(buffer + offset); 386 offset += sizeof(uint32); 387 388 crc = *(uint32*)(buffer + offset); 389 offset += sizeof(uint32); 390 391 blkno = *(uint64*)(buffer + offset); 392 offset += sizeof(uint64); 393 394 lsn = *(uint64*)(buffer + offset); 395 offset += sizeof(uint64); 396 397 memcpy(&uuid, buffer + offset, sizeof(uuid_t)); 398 offset += sizeof(uuid_t); 399 400 owner = *(uint64*)(buffer + offset); 401 offset += sizeof(uint64); 402 403 memcpy(bestfree, buffer + offset, XFS_DIR2_DATA_FD_COUNT * sizeof(FreeRegion)); 404 offset += XFS_DIR2_DATA_FD_COUNT * sizeof(FreeRegion); 405 406 pad = *(uint32*)(buffer + offset); 407 408 SwapEndian(); 409 } 410 411 412 ExtentDataHeaderV5::~ExtentDataHeaderV5() 413 { 414 } 415 416 417 uint32 418 ExtentDataHeaderV5::Magic() 419 { 420 return magic; 421 } 422 423 424 uint64 425 ExtentDataHeaderV5::Blockno() 426 { 427 return blkno; 428 } 429 430 431 uint64 432 ExtentDataHeaderV5::Lsn() 433 { 434 return lsn; 435 } 436 437 438 uint64 439 ExtentDataHeaderV5::Owner() 440 { 441 return owner; 442 } 443 444 445 uuid_t* 446 ExtentDataHeaderV5::Uuid() 447 { 448 return &uuid; 449 }