1 /* 2 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com 3 * All rights reserved. Distributed under the terms of the MIT License. 4 */ 5 6 7 #include "LeafDirectory.h" 8 9 10 LeafDirectory::LeafDirectory(Inode* inode) 11 : 12 fInode(inode), 13 fOffset(0), 14 fDataBuffer(NULL), 15 fLeafBuffer(NULL), 16 fLeafMap(NULL), 17 fDataMap(NULL), 18 fCurBlockNumber(-1) 19 { 20 } 21 22 23 LeafDirectory::~LeafDirectory() 24 { 25 delete fDataMap; 26 delete fLeafMap; 27 delete fDataBuffer; 28 delete fLeafBuffer; 29 } 30 31 32 status_t 33 LeafDirectory::Init() 34 { 35 fLeafMap = new(std::nothrow) ExtentMapEntry; 36 if (fLeafMap == NULL) 37 return B_NO_MEMORY; 38 39 fDataMap = new(std::nothrow) ExtentMapEntry; 40 if (fDataMap == NULL) 41 return B_NO_MEMORY; 42 43 FillMapEntry(fInode->DataExtentsCount()-1, fLeafMap); 44 FillMapEntry(0, fDataMap); 45 return B_OK; 46 } 47 48 49 bool 50 LeafDirectory::IsLeafType() 51 { 52 bool status = true; 53 if (fInode->BlockCount() == 1 54 || fInode->DataExtentsCount() == 1 55 || fInode->Size() != 56 (fInode->BlockCount() - 1) * fInode->DirBlockSize()) 57 status = false; 58 59 if (status == false) 60 return status; 61 62 FillMapEntry(fInode->DataExtentsCount() - 1, fLeafMap); 63 TRACE("leaf_Startoffset:(%ld)\n", 64 LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog())); 65 66 if (fLeafMap->br_startoff 67 != LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog())) 68 status = false; 69 70 return status; 71 } 72 73 74 void 75 LeafDirectory::FillMapEntry(int num, ExtentMapEntry* fMap) 76 { 77 void* directoryFork = DIR_DFORK_PTR(fInode->Buffer()); 78 uint64* pointerToMap = (uint64*)((char*)directoryFork + num * EXTENT_SIZE); 79 uint64 firstHalf = pointerToMap[0]; 80 uint64 secondHalf = pointerToMap[1]; 81 //dividing the 128 bits into 2 parts. 82 83 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 84 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 85 fMap->br_state = firstHalf >> 63; 86 fMap->br_startoff = (firstHalf & MASK(63)) >> 9; 87 fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 88 fMap->br_blockcount = secondHalf & MASK(21); 89 TRACE("FillMapEntry: startoff:(%ld), startblock:(%ld), blockcount:(%ld)," 90 "state:(%d)\n", fMap->br_startoff, fMap->br_startblock, 91 fMap->br_blockcount, fMap->br_state); 92 } 93 94 95 status_t 96 LeafDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur) 97 { 98 TRACE("FILLBUFFER\n"); 99 ExtentMapEntry* map; 100 if (type == DATA) 101 map = fDataMap; 102 103 if (type == LEAF) 104 map = fLeafMap; 105 106 if (map->br_state !=0) 107 return B_BAD_VALUE; 108 109 int len = fInode->DirBlockSize(); 110 if (blockBuffer == NULL) { 111 blockBuffer = new(std::nothrow) char[len]; 112 if (blockBuffer == NULL) 113 return B_NO_MEMORY; 114 } 115 116 Volume* volume = fInode->GetVolume(); 117 xfs_agblock_t numberOfBlocksInAg = volume->AgBlocks(); 118 119 uint64 agNo = 120 FSBLOCKS_TO_AGNO(map->br_startblock + howManyBlocksFurthur, volume); 121 uint64 agBlockNo = 122 FSBLOCKS_TO_AGBLOCKNO(map->br_startblock + howManyBlocksFurthur, volume); 123 124 xfs_fsblock_t blockToRead = FSBLOCKS_TO_BASICBLOCKS(volume->BlockLog(), 125 (agNo * numberOfBlocksInAg + agBlockNo)); 126 127 xfs_daddr_t readPos = blockToRead * BASICBLOCKSIZE; 128 129 TRACE("blockToRead: (%ld), readPos: (%ld)\n", blockToRead, readPos); 130 if (read_pos(volume->Device(), readPos, blockBuffer, len) != len) { 131 ERROR("Extent::FillBlockBuffer(): IO Error"); 132 return B_IO_ERROR; 133 } 134 135 if (type == DATA) 136 fDataBuffer = blockBuffer; 137 138 if (type == LEAF) 139 fLeafBuffer = blockBuffer; 140 141 if (type == LEAF) { 142 ExtentLeafHeader* header = (ExtentLeafHeader*) fLeafBuffer; 143 TRACE("NumberOfEntries in leaf: (%d)\n", 144 B_BENDIAN_TO_HOST_INT16(header->count)); 145 } 146 if (type == DATA) { 147 ExtentDataHeader* header = (ExtentDataHeader*) fDataBuffer; 148 if (B_BENDIAN_TO_HOST_INT32(header->magic) == HEADER_MAGIC) 149 TRACE("DATA BLOCK VALID\n"); 150 else { 151 TRACE("DATA BLOCK INVALID\n"); 152 return B_BAD_VALUE; 153 } 154 } 155 return B_OK; 156 } 157 158 159 uint32 160 LeafDirectory::GetOffsetFromAddress(uint32 address) 161 { 162 address = address * 8; 163 // block offset in eight bytes, hence multiply with 8 164 return address & (fInode->DirBlockSize() - 1); 165 } 166 167 168 ExtentLeafEntry* 169 LeafDirectory::FirstLeaf() 170 { 171 TRACE("LeafDirectory: FirstLeaf\n"); 172 if (fLeafBuffer == NULL) { 173 ASSERT(fLeafMap != NULL); 174 status_t status = FillBuffer(LEAF, fLeafBuffer, 0); 175 if (status != B_OK) 176 return NULL; 177 } 178 return (ExtentLeafEntry*)((char*)fLeafBuffer + sizeof(ExtentLeafHeader)); 179 } 180 181 182 int 183 LeafDirectory::EntrySize(int len) const 184 { 185 int entrySize= sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 186 // uint16 is for the tag 187 if (fInode->HasFileTypeField()) 188 entrySize += sizeof(uint8); 189 190 return (entrySize + 7) & -8; 191 // rounding off to closest multiple of 8 192 } 193 194 195 void 196 LeafDirectory::SearchAndFillDataMap(int blockNo) 197 { 198 int len = fInode->DataExtentsCount(); 199 200 for(int i = 0; i < len - 1; i++) { 201 FillMapEntry(i, fDataMap); 202 if (fDataMap->br_startoff <= blockNo 203 && (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1)) 204 // Map found 205 return; 206 } 207 } 208 209 210 status_t 211 LeafDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino) 212 { 213 TRACE("LeafDirectory::GetNext\n"); 214 status_t status; 215 216 if (fDataBuffer == NULL) { 217 status = FillBuffer(DATA, fDataBuffer, 0); 218 if (status != B_OK) 219 return status; 220 } 221 222 Volume* volume = fInode->GetVolume(); 223 void* entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 224 // This could be an unused entry so we should check 225 226 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 227 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) 228 entry = (void*)(fDataBuffer 229 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode)); 230 // This gets us a little faster to the next entry 231 232 uint32 curDirectorySize = fInode->Size(); 233 234 while (fOffset != curDirectorySize) { 235 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 236 237 TRACE("fOffset:(%d), blockNoFromAddress:(%d)\n", 238 fOffset, blockNoFromAddress); 239 if (fCurBlockNumber != blockNoFromAddress 240 && blockNoFromAddress > fDataMap->br_startoff 241 && blockNoFromAddress 242 <= fDataMap->br_startoff + fDataMap->br_blockcount - 1) { 243 // When the block is mapped in the same data 244 // map entry but is not the first block 245 status = FillBuffer(DATA, fDataBuffer, 246 blockNoFromAddress - fDataMap->br_startoff); 247 if (status != B_OK) 248 return status; 249 entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 250 fOffset = fOffset + sizeof(ExtentDataHeader); 251 fCurBlockNumber = blockNoFromAddress; 252 } else if (fCurBlockNumber != blockNoFromAddress) { 253 // When the block isn't mapped in the current data map entry 254 SearchAndFillDataMap(blockNoFromAddress); 255 status = FillBuffer(DATA, fDataBuffer, 256 blockNoFromAddress - fDataMap->br_startoff); 257 if (status != B_OK) 258 return status; 259 entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 260 fOffset = fOffset + sizeof(ExtentDataHeader); 261 fCurBlockNumber = blockNoFromAddress; 262 } 263 264 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 265 266 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 267 TRACE("Unused entry found\n"); 268 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 269 entry = (void*) 270 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 271 continue; 272 } 273 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 274 275 uint16 currentOffset = (char*)dataEntry - fDataBuffer; 276 TRACE("GetNext: fOffset:(%d), currentOffset:(%d)\n", 277 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset); 278 279 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) { 280 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 281 continue; 282 } 283 284 if (dataEntry->namelen > *length) 285 return B_BUFFER_OVERFLOW; 286 287 fOffset = fOffset + EntrySize(dataEntry->namelen); 288 memcpy(name, dataEntry->name, dataEntry->namelen); 289 name[dataEntry->namelen] = '\0'; 290 *length = dataEntry->namelen + 1; 291 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 292 293 TRACE("Entry found. Name: (%s), Length: (%ld),ino: (%ld)\n", name, 294 *length, *ino); 295 return B_OK; 296 } 297 298 return B_ENTRY_NOT_FOUND; 299 } 300 301 302 status_t 303 LeafDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino) 304 { 305 TRACE("LeafDirectory: Lookup\n"); 306 TRACE("Name: %s\n", name); 307 uint32 hashValueOfRequest = hashfunction(name, length); 308 TRACE("Hashval:(%ld)\n", hashValueOfRequest); 309 310 status_t status; 311 if (fLeafBuffer == NULL) 312 status = FillBuffer(LEAF, fLeafBuffer, 0); 313 if (status != B_OK) 314 return status; 315 316 ExtentLeafHeader* leafHeader = (ExtentLeafHeader*)(void*)fLeafBuffer; 317 ExtentLeafEntry* leafEntry = FirstLeaf(); 318 if (leafEntry == NULL) 319 return B_NO_MEMORY; 320 321 int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT16(leafHeader->count); 322 TRACE("numberOfLeafEntries:(%d)\n", numberOfLeafEntries); 323 int left = 0; 324 int mid; 325 int right = numberOfLeafEntries - 1; 326 Volume* volume = fInode->GetVolume(); 327 328 /* 329 * Trying to find the lowerbound of hashValueOfRequest 330 * This is slightly different from bsearch(), as we want the first 331 * instance of hashValueOfRequest and not any instance. 332 */ 333 while (left < right) { 334 mid = (left+right)/2; 335 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 336 if (hashval >= hashValueOfRequest) { 337 right = mid; 338 continue; 339 } 340 if (hashval < hashValueOfRequest) { 341 left = mid+1; 342 } 343 } 344 TRACE("left:(%d), right:(%d)\n", left, right); 345 346 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 347 == hashValueOfRequest) { 348 349 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 350 if (address == 0) { 351 left++; 352 continue; 353 } 354 355 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 356 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 357 358 TRACE("DataBlockNumber:(%d), offset:(%d)\n", dataBlockNumber, offset); 359 if (dataBlockNumber != fCurBlockNumber) { 360 fCurBlockNumber = dataBlockNumber; 361 SearchAndFillDataMap(dataBlockNumber); 362 status = FillBuffer(DATA, fDataBuffer, 363 dataBlockNumber - fDataMap->br_startoff); 364 if (status != B_OK) 365 return B_OK; 366 } 367 368 TRACE("offset:(%d)\n", offset); 369 ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset); 370 371 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 372 if (retVal == 0) { 373 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 374 TRACE("ino:(%d)\n", *ino); 375 return B_OK; 376 } 377 left++; 378 } 379 380 return B_ENTRY_NOT_FOUND; 381 } 382