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 offsetof(ExtentDataHeaderV5::OnDiskData, crc); 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::OnDiskData); 305 else 306 return sizeof(ExtentDataHeaderV5::OnDiskData); 307 } 308 309 310 void 311 ExtentDataHeaderV4::_SwapEndian() 312 { 313 fData.magic = (B_BENDIAN_TO_HOST_INT32(fData.magic)); 314 } 315 316 317 ExtentDataHeaderV4::ExtentDataHeaderV4(const char* buffer) 318 { 319 memcpy(&fData, buffer, sizeof(fData)); 320 _SwapEndian(); 321 } 322 323 324 ExtentDataHeaderV4::~ExtentDataHeaderV4() 325 { 326 } 327 328 329 uint32 330 ExtentDataHeaderV4::Magic() 331 { 332 return fData.magic; 333 } 334 335 336 uint64 337 ExtentDataHeaderV4::Blockno() 338 { 339 return B_BAD_VALUE; 340 } 341 342 343 uint64 344 ExtentDataHeaderV4::Lsn() 345 { 346 return B_BAD_VALUE; 347 } 348 349 350 uint64 351 ExtentDataHeaderV4::Owner() 352 { 353 return B_BAD_VALUE; 354 } 355 356 357 const uuid_t& 358 ExtentDataHeaderV4::Uuid() 359 { 360 static uuid_t nullUuid; 361 return nullUuid; 362 } 363 364 365 void 366 ExtentDataHeaderV5::_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 376 ExtentDataHeaderV5::ExtentDataHeaderV5(const char* buffer) 377 { 378 memcpy(&fData, buffer, sizeof(fData)); 379 _SwapEndian(); 380 } 381 382 383 ExtentDataHeaderV5::~ExtentDataHeaderV5() 384 { 385 } 386 387 388 uint32 389 ExtentDataHeaderV5::Magic() 390 { 391 return fData.magic; 392 } 393 394 395 uint64 396 ExtentDataHeaderV5::Blockno() 397 { 398 return fData.blkno; 399 } 400 401 402 uint64 403 ExtentDataHeaderV5::Lsn() 404 { 405 return fData.lsn; 406 } 407 408 409 uint64 410 ExtentDataHeaderV5::Owner() 411 { 412 return fData.owner; 413 } 414 415 416 const uuid_t& 417 ExtentDataHeaderV5::Uuid() 418 { 419 return fData.uuid; 420 } 421