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 79 uint64* pointerToMap = (uint64*)((char*)directoryFork + num * EXTENT_SIZE); 80 uint64 firstHalf = pointerToMap[0]; 81 uint64 secondHalf = pointerToMap[1]; 82 //dividing the 128 bits into 2 parts. 83 84 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 85 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 86 fMap->br_state = firstHalf >> 63; 87 fMap->br_startoff = (firstHalf & MASK(63)) >> 9; 88 fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 89 fMap->br_blockcount = secondHalf & MASK(21); 90 TRACE("FillMapEntry: startoff:(%ld), startblock:(%ld), blockcount:(%ld)," 91 "state:(%d)\n", fMap->br_startoff, fMap->br_startblock, 92 fMap->br_blockcount, fMap->br_state); 93 } 94 95 96 status_t 97 LeafDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur) 98 { 99 TRACE("FILLBUFFER\n"); 100 ExtentMapEntry* map; 101 if (type == DATA) 102 map = fDataMap; 103 else if (type == LEAF) 104 map = fLeafMap; 105 else 106 return B_BAD_VALUE; 107 108 if (map->br_state !=0) 109 return B_BAD_VALUE; 110 111 int len = fInode->DirBlockSize(); 112 if (blockBuffer == NULL) { 113 blockBuffer = new(std::nothrow) char[len]; 114 if (blockBuffer == NULL) 115 return B_NO_MEMORY; 116 } 117 118 xfs_daddr_t readPos = 119 fInode->FileSystemBlockToAddr(map->br_startblock + howManyBlocksFurthur); 120 121 if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len) 122 != len) { 123 ERROR("LeafDirectory::FillBlockBuffer(): IO Error"); 124 return B_IO_ERROR; 125 } 126 127 if (type == DATA) { 128 fDataBuffer = blockBuffer; 129 ExtentDataHeader* header = (ExtentDataHeader*) fDataBuffer; 130 if (B_BENDIAN_TO_HOST_INT32(header->magic) == DATA_HEADER_MAGIC) 131 TRACE("DATA BLOCK VALID\n"); 132 else { 133 TRACE("DATA BLOCK INVALID\n"); 134 return B_BAD_VALUE; 135 } 136 } else if (type == LEAF) { 137 fLeafBuffer = blockBuffer; 138 ExtentLeafHeader* header = (ExtentLeafHeader*) fLeafBuffer; 139 TRACE("NumberOfEntries in leaf: (%d)\n", 140 B_BENDIAN_TO_HOST_INT16(header->count)); 141 } 142 return B_OK; 143 } 144 145 146 uint32 147 LeafDirectory::GetOffsetFromAddress(uint32 address) 148 { 149 address = address * 8; 150 // block offset in eight bytes, hence multiply with 8 151 return address & (fInode->DirBlockSize() - 1); 152 } 153 154 155 ExtentLeafEntry* 156 LeafDirectory::FirstLeaf() 157 { 158 TRACE("LeafDirectory: FirstLeaf\n"); 159 if (fLeafBuffer == NULL) { 160 ASSERT(fLeafMap != NULL); 161 status_t status = FillBuffer(LEAF, fLeafBuffer, 0); 162 if (status != B_OK) 163 return NULL; 164 } 165 return (ExtentLeafEntry*)((char*)fLeafBuffer + sizeof(ExtentLeafHeader)); 166 } 167 168 169 int 170 LeafDirectory::EntrySize(int len) const 171 { 172 int entrySize= sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 173 // uint16 is for the tag 174 if (fInode->HasFileTypeField()) 175 entrySize += sizeof(uint8); 176 177 return (entrySize + 7) & -8; 178 // rounding off to closest multiple of 8 179 } 180 181 182 void 183 LeafDirectory::SearchAndFillDataMap(int blockNo) 184 { 185 int len = fInode->DataExtentsCount(); 186 187 for(int i = 0; i < len - 1; i++) { 188 FillMapEntry(i, fDataMap); 189 if (fDataMap->br_startoff <= blockNo 190 && (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1)) 191 // Map found 192 return; 193 } 194 } 195 196 197 status_t 198 LeafDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino) 199 { 200 TRACE("LeafDirectory::GetNext\n"); 201 status_t status; 202 203 if (fDataBuffer == NULL) { 204 status = FillBuffer(DATA, fDataBuffer, 0); 205 if (status != B_OK) 206 return status; 207 } 208 209 Volume* volume = fInode->GetVolume(); 210 void* entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 211 // This could be an unused entry so we should check 212 213 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 214 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) 215 entry = (void*)(fDataBuffer 216 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode)); 217 // This gets us a little faster to the next entry 218 219 uint32 curDirectorySize = fInode->Size(); 220 221 while (fOffset != curDirectorySize) { 222 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 223 224 TRACE("fOffset:(%d), blockNoFromAddress:(%d)\n", 225 fOffset, blockNoFromAddress); 226 if (fCurBlockNumber != blockNoFromAddress 227 && blockNoFromAddress > fDataMap->br_startoff 228 && blockNoFromAddress 229 <= fDataMap->br_startoff + fDataMap->br_blockcount - 1) { 230 // When the block is mapped in the same data 231 // map entry but is not the first block 232 status = FillBuffer(DATA, fDataBuffer, 233 blockNoFromAddress - fDataMap->br_startoff); 234 if (status != B_OK) 235 return status; 236 entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 237 fOffset = fOffset + sizeof(ExtentDataHeader); 238 fCurBlockNumber = blockNoFromAddress; 239 } else if (fCurBlockNumber != blockNoFromAddress) { 240 // When the block isn't mapped in the current data map entry 241 SearchAndFillDataMap(blockNoFromAddress); 242 status = FillBuffer(DATA, fDataBuffer, 243 blockNoFromAddress - fDataMap->br_startoff); 244 if (status != B_OK) 245 return status; 246 entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 247 fOffset = fOffset + sizeof(ExtentDataHeader); 248 fCurBlockNumber = blockNoFromAddress; 249 } 250 251 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 252 253 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 254 TRACE("Unused entry found\n"); 255 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 256 entry = (void*) 257 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 258 continue; 259 } 260 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 261 262 uint16 currentOffset = (char*)dataEntry - fDataBuffer; 263 TRACE("GetNext: fOffset:(%d), currentOffset:(%d)\n", 264 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset); 265 266 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) { 267 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 268 continue; 269 } 270 271 if (dataEntry->namelen + 1 > *length) 272 return B_BUFFER_OVERFLOW; 273 274 fOffset = fOffset + EntrySize(dataEntry->namelen); 275 memcpy(name, dataEntry->name, dataEntry->namelen); 276 name[dataEntry->namelen] = '\0'; 277 *length = dataEntry->namelen + 1; 278 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 279 280 TRACE("Entry found. Name: (%s), Length: (%ld),ino: (%ld)\n", name, 281 *length, *ino); 282 return B_OK; 283 } 284 285 return B_ENTRY_NOT_FOUND; 286 } 287 288 289 status_t 290 LeafDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino) 291 { 292 TRACE("LeafDirectory: Lookup\n"); 293 TRACE("Name: %s\n", name); 294 uint32 hashValueOfRequest = hashfunction(name, length); 295 TRACE("Hashval:(%ld)\n", hashValueOfRequest); 296 297 status_t status; 298 if (fLeafBuffer == NULL) 299 status = FillBuffer(LEAF, fLeafBuffer, 0); 300 if (status != B_OK) 301 return status; 302 303 ExtentLeafHeader* leafHeader = (ExtentLeafHeader*)(void*)fLeafBuffer; 304 ExtentLeafEntry* leafEntry = FirstLeaf(); 305 if (leafEntry == NULL) 306 return B_NO_MEMORY; 307 308 int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT16(leafHeader->count); 309 TRACE("numberOfLeafEntries:(%d)\n", numberOfLeafEntries); 310 int left = 0; 311 int mid; 312 int right = numberOfLeafEntries - 1; 313 Volume* volume = fInode->GetVolume(); 314 315 /* 316 * Trying to find the lowerbound of hashValueOfRequest 317 * This is slightly different from bsearch(), as we want the first 318 * instance of hashValueOfRequest and not any instance. 319 */ 320 while (left < right) { 321 mid = (left+right)/2; 322 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 323 if (hashval >= hashValueOfRequest) { 324 right = mid; 325 continue; 326 } 327 if (hashval < hashValueOfRequest) { 328 left = mid+1; 329 } 330 } 331 TRACE("left:(%d), right:(%d)\n", left, right); 332 333 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 334 == hashValueOfRequest) { 335 336 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 337 if (address == 0) { 338 left++; 339 continue; 340 } 341 342 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 343 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 344 345 TRACE("DataBlockNumber:(%d), offset:(%d)\n", dataBlockNumber, offset); 346 if (dataBlockNumber != fCurBlockNumber) { 347 fCurBlockNumber = dataBlockNumber; 348 SearchAndFillDataMap(dataBlockNumber); 349 status = FillBuffer(DATA, fDataBuffer, 350 dataBlockNumber - fDataMap->br_startoff); 351 if (status != B_OK) 352 return B_OK; 353 } 354 355 TRACE("offset:(%d)\n", offset); 356 ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset); 357 358 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 359 if (retVal == 0) { 360 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 361 TRACE("ino:(%d)\n", *ino); 362 return B_OK; 363 } 364 left++; 365 } 366 367 return B_ENTRY_NOT_FOUND; 368 } 369