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 = CreateDataHeader(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 + SizeOfDataHeader(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 mid; 219 int right = numberOfLeafEntries - 1; 220 221 /* 222 * Trying to find the lowerbound of hashValueOfRequest 223 * This is slightly different from bsearch(), as we want the first 224 * instance of hashValueOfRequest and not any instance. 225 */ 226 while (left < right) { 227 mid = (left+right)/2; 228 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 229 if (hashval >= hashValueOfRequest) { 230 right = mid; 231 continue; 232 } 233 if (hashval < hashValueOfRequest) { 234 left = mid+1; 235 } 236 } 237 TRACE("left:(%" B_PRId32 "), right:(%" B_PRId32 ")\n", left, right); 238 239 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 240 == hashValueOfRequest) { 241 242 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 243 if (address == 0) { 244 left++; 245 continue; 246 } 247 248 uint32 offset = GetOffsetFromAddress(address); 249 TRACE("offset:(%" B_PRIu32 ")\n", offset); 250 ExtentDataEntry* entry = (ExtentDataEntry*)(fBlockBuffer + offset); 251 252 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 253 if (retVal == 0) { 254 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 255 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 256 return B_OK; 257 } 258 left++; 259 } 260 261 return B_ENTRY_NOT_FOUND; 262 } 263 264 265 ExtentDataHeader::~ExtentDataHeader() 266 { 267 } 268 269 270 /* 271 First see which type of directory we reading then 272 return magic number as per Inode Version. 273 */ 274 uint32 275 ExtentDataHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode) 276 { 277 if (WhichDirectory == XFS_BLOCK) { 278 if (inode->Version() == 1 || inode->Version() == 2) 279 return DIR2_BLOCK_HEADER_MAGIC; 280 else 281 return DIR3_BLOCK_HEADER_MAGIC; 282 } else { 283 if (inode->Version() == 1 || inode->Version() == 2) 284 return V4_DATA_HEADER_MAGIC; 285 else 286 return V5_DATA_HEADER_MAGIC; 287 } 288 } 289 290 291 uint32 292 ExtentDataHeader::CRCOffset() 293 { 294 return XFS_EXTENT_CRC_OFF - XFS_EXTENT_V5_VPTR_OFF; 295 } 296 297 298 void 299 ExtentDataHeaderV4::SwapEndian() 300 { 301 magic = B_BENDIAN_TO_HOST_INT32(magic); 302 } 303 304 305 ExtentDataHeaderV4::ExtentDataHeaderV4(const char* buffer) 306 { 307 uint32 offset = 0; 308 309 magic = *(uint32*)(buffer + offset); 310 offset += sizeof(uint32); 311 312 memcpy(bestfree, buffer + offset, XFS_DIR2_DATA_FD_COUNT * sizeof(FreeRegion)); 313 314 SwapEndian(); 315 } 316 317 318 ExtentDataHeaderV4::~ExtentDataHeaderV4() 319 { 320 } 321 322 323 uint32 324 ExtentDataHeaderV4::Magic() 325 { 326 return magic; 327 } 328 329 330 uint64 331 ExtentDataHeaderV4::Blockno() 332 { 333 return B_BAD_VALUE; 334 } 335 336 337 uint64 338 ExtentDataHeaderV4::Lsn() 339 { 340 return B_BAD_VALUE; 341 } 342 343 344 uint64 345 ExtentDataHeaderV4::Owner() 346 { 347 return B_BAD_VALUE; 348 } 349 350 351 uuid_t* 352 ExtentDataHeaderV4::Uuid() 353 { 354 return NULL; 355 } 356 357 358 void 359 ExtentDataHeaderV5::SwapEndian() 360 { 361 magic = B_BENDIAN_TO_HOST_INT32(magic); 362 blkno = B_BENDIAN_TO_HOST_INT64(blkno); 363 lsn = B_BENDIAN_TO_HOST_INT64(lsn); 364 owner = B_BENDIAN_TO_HOST_INT64(owner); 365 pad = B_BENDIAN_TO_HOST_INT32(pad); 366 } 367 368 369 ExtentDataHeaderV5::ExtentDataHeaderV5(const char* buffer) 370 { 371 uint32 offset = 0; 372 373 magic = *(uint32*)(buffer + offset); 374 offset += sizeof(uint32); 375 376 crc = *(uint32*)(buffer + offset); 377 offset += sizeof(uint32); 378 379 blkno = *(uint64*)(buffer + offset); 380 offset += sizeof(uint64); 381 382 lsn = *(uint64*)(buffer + offset); 383 offset += sizeof(uint64); 384 385 memcpy(&uuid, buffer + offset, sizeof(uuid_t)); 386 offset += sizeof(uuid_t); 387 388 owner = *(uint64*)(buffer + offset); 389 offset += sizeof(uint64); 390 391 memcpy(bestfree, buffer + offset, XFS_DIR2_DATA_FD_COUNT * sizeof(FreeRegion)); 392 offset += XFS_DIR2_DATA_FD_COUNT * sizeof(FreeRegion); 393 394 pad = *(uint32*)(buffer + offset); 395 396 SwapEndian(); 397 } 398 399 400 ExtentDataHeaderV5::~ExtentDataHeaderV5() 401 { 402 } 403 404 405 uint32 406 ExtentDataHeaderV5::Magic() 407 { 408 return magic; 409 } 410 411 412 uint64 413 ExtentDataHeaderV5::Blockno() 414 { 415 return blkno; 416 } 417 418 419 uint64 420 ExtentDataHeaderV5::Lsn() 421 { 422 return lsn; 423 } 424 425 426 uint64 427 ExtentDataHeaderV5::Owner() 428 { 429 return owner; 430 } 431 432 433 uuid_t* 434 ExtentDataHeaderV5::Uuid() 435 { 436 return &uuid; 437 } 438 439 440 //Function to get V4 or V5 data header instance 441 ExtentDataHeader* 442 CreateDataHeader(Inode* inode, const char* buffer) 443 { 444 if (inode->Version() == 1 || inode->Version() == 2) { 445 ExtentDataHeaderV4* header = new (std::nothrow) ExtentDataHeaderV4(buffer); 446 return header; 447 } else { 448 ExtentDataHeaderV5* header = new (std::nothrow) ExtentDataHeaderV5(buffer); 449 return header; 450 } 451 } 452 453 454 /* 455 This Function returns Actual size of data header 456 in all forms of directory. 457 Never use sizeof() operator because we now have 458 vtable as well and it will give wrong results 459 */ 460 uint32 461 SizeOfDataHeader(Inode* inode) 462 { 463 if (inode->Version() == 1 || inode->Version() == 2) 464 return sizeof(ExtentDataHeaderV4) - XFS_EXTENT_V4_VPTR_OFF; 465 else 466 return sizeof(ExtentDataHeaderV5) - XFS_EXTENT_V5_VPTR_OFF; 467 } 468