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