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 fDataMap(NULL), 14 fLeafMap(NULL), 15 fOffset(0), 16 fDataBuffer(NULL), 17 fLeafBuffer(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("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 ")," 78 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\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 ssize_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 //TODO : see if we can do something with this header 126 //ExtentLeafHeader* header = (ExtentLeafHeader*) fLeafBuffer; 127 } 128 129 return B_OK; 130 } 131 132 133 uint32 134 NodeDirectory::GetOffsetFromAddress(uint32 address) 135 { 136 address = address * 8; 137 // block offset in eight bytes, hence multiple with 8 138 return address & (fInode->DirBlockSize() - 1); 139 } 140 141 142 uint32 143 NodeDirectory::FindHashInNode(uint32 hashVal) 144 { 145 NodeHeader* header = (NodeHeader*)(void*)(fLeafBuffer); 146 NodeEntry* entry = (NodeEntry*)(void*)(fLeafBuffer + sizeof(NodeHeader)); 147 int count = B_BENDIAN_TO_HOST_INT16(header->count); 148 if ((NodeEntry*)(void*)fLeafBuffer + fInode->DirBlockSize() 149 < &entry[count]) { 150 return B_BAD_VALUE; 151 } 152 153 for (int i = 0; i < count; i++) { 154 if (hashVal <= B_BENDIAN_TO_HOST_INT32(entry[i].hashval)) 155 return B_BENDIAN_TO_HOST_INT32(entry[i].before); 156 } 157 158 return 1; 159 } 160 161 162 int 163 NodeDirectory::EntrySize(int len) const 164 { 165 int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 166 // uint16 is for the tag 167 if (fInode->HasFileTypeField()) 168 entrySize += sizeof(uint8); 169 170 return ROUNDUP(entrySize, 8); 171 // rounding off to closest multiple of 8 172 } 173 174 175 void 176 NodeDirectory::SearchAndFillDataMap(uint64 blockNo) 177 { 178 int len = fInode->DataExtentsCount(); 179 180 for (int i = 0; i < len - 3; i++) { 181 FillMapEntry(i, fDataMap); 182 if (fDataMap->br_startoff <= blockNo 183 && (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1)) 184 // Map found 185 return; 186 } 187 } 188 189 190 status_t 191 NodeDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino) 192 { 193 TRACE("NodeDirectory::GetNext\n"); 194 status_t status; 195 196 if (fDataBuffer == NULL) { 197 status = FillBuffer(DATA, fDataBuffer, 0); 198 if (status != B_OK) 199 return status; 200 } 201 202 Volume* volume = fInode->GetVolume(); 203 void* entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 204 // This could be an unused entry so we should check 205 206 uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 207 if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber) { 208 entry = (void*)(fDataBuffer 209 + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode)); 210 // This gets us a little faster to the next entry 211 } 212 213 uint32 curDirectorySize = fInode->Size(); 214 215 while (fOffset != curDirectorySize) { 216 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume); 217 218 TRACE("fOffset:(%" B_PRIu32 "), blockNoFromAddress:(%" B_PRIu32 ")\n", 219 fOffset, blockNoFromAddress); 220 if (fCurBlockNumber != blockNoFromAddress 221 && blockNoFromAddress > fDataMap->br_startoff 222 && blockNoFromAddress 223 <= fDataMap->br_startoff + fDataMap->br_blockcount - 1) { 224 // When the block is mapped in the same data 225 // map entry but is not the first block 226 status = FillBuffer(DATA, fDataBuffer, 227 blockNoFromAddress - fDataMap->br_startoff); 228 if (status != B_OK) 229 return status; 230 entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 231 fOffset = fOffset + sizeof(ExtentDataHeader); 232 fCurBlockNumber = blockNoFromAddress; 233 } else if (fCurBlockNumber != blockNoFromAddress) { 234 // When the block isn't mapped in the current data map entry 235 SearchAndFillDataMap(blockNoFromAddress); 236 status = FillBuffer(DATA, fDataBuffer, 237 blockNoFromAddress - fDataMap->br_startoff); 238 if (status != B_OK) 239 return status; 240 entry = (void*)((ExtentDataHeader*)fDataBuffer + 1); 241 fOffset = fOffset + sizeof(ExtentDataHeader); 242 fCurBlockNumber = blockNoFromAddress; 243 } 244 245 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 246 247 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 248 TRACE("Unused entry found\n"); 249 fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 250 entry = (void*) 251 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 252 continue; 253 } 254 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 255 256 uint16 currentOffset = (char*)dataEntry - fDataBuffer; 257 TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n", 258 BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset); 259 260 if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) { 261 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 262 continue; 263 } 264 265 if ((size_t)(dataEntry->namelen) >= *length) 266 return B_BUFFER_OVERFLOW; 267 268 fOffset = fOffset + EntrySize(dataEntry->namelen); 269 memcpy(name, dataEntry->name, dataEntry->namelen); 270 name[dataEntry->namelen] = '\0'; 271 *length = dataEntry->namelen + 1; 272 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 273 274 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n", 275 name,*length, *ino); 276 return B_OK; 277 } 278 279 return B_ENTRY_NOT_FOUND; 280 } 281 282 283 status_t 284 NodeDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino) 285 { 286 TRACE("NodeDirectory: Lookup\n"); 287 TRACE("Name: %s\n", name); 288 uint32 hashValueOfRequest = hashfunction(name, length); 289 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest); 290 291 status_t status; 292 if (fCurLeafBufferNumber != 1) { 293 if (fCurLeafMapNumber != 1) { 294 FillMapEntry(fInode->DataExtentsCount() - 3, fLeafMap); 295 fCurLeafMapNumber = 1; 296 } 297 status = FillBuffer(LEAF, fLeafBuffer, 0); 298 if (status != B_OK) 299 return status; 300 fCurLeafBufferNumber = 1; 301 } 302 /* Leaf now has the nodes. */ 303 uint32 rightMapOffset = FindHashInNode(hashValueOfRequest); 304 if (rightMapOffset == 1){ 305 TRACE("Not in this directory.\n"); 306 return B_ENTRY_NOT_FOUND; 307 } 308 309 TRACE("rightMapOffset:(%" B_PRIu32 ")\n", rightMapOffset); 310 311 FillMapEntry(fInode->DataExtentsCount() - 2, fLeafMap); 312 fCurLeafMapNumber = 2; 313 status = FillBuffer(LEAF, fLeafBuffer, 314 rightMapOffset - fLeafMap->br_startoff); 315 if (status != B_OK) 316 return status; 317 fCurLeafBufferNumber = 2; 318 319 ExtentLeafHeader* leafHeader = (ExtentLeafHeader*)(void*)fLeafBuffer; 320 ExtentLeafEntry* leafEntry = 321 (ExtentLeafEntry*)(void*)(fLeafBuffer + sizeof(ExtentLeafHeader)); 322 if (leafEntry == NULL) 323 return B_NO_MEMORY; 324 325 int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT16(leafHeader->count); 326 TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries); 327 int left = 0; 328 int mid; 329 int right = numberOfLeafEntries - 1; 330 Volume* volume = fInode->GetVolume(); 331 332 /* 333 * Trying to find the lowerbound of hashValueOfRequest 334 * This is slightly different from bsearch(), as we want the first 335 * instance of hashValueOfRequest and not any instance. 336 */ 337 while (left < right) { 338 mid = (left + right) / 2; 339 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 340 if (hashval >= hashValueOfRequest) { 341 right = mid; 342 continue; 343 } 344 if (hashval < hashValueOfRequest) { 345 left = mid + 1; 346 } 347 } 348 TRACE("left:(%" B_PRId32 "), right:(%" B_PRId32 ")\n", left, right); 349 350 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 351 == hashValueOfRequest) { 352 353 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 354 if (address == 0) { 355 left++; 356 continue; 357 } 358 359 uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume); 360 uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode); 361 362 TRACE("DataBlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", 363 dataBlockNumber, offset); 364 if (dataBlockNumber != fCurBlockNumber) { 365 fCurBlockNumber = dataBlockNumber; 366 SearchAndFillDataMap(dataBlockNumber); 367 status = FillBuffer(DATA, fDataBuffer, 368 dataBlockNumber - fDataMap->br_startoff); 369 if (status != B_OK) 370 return B_OK; 371 } 372 373 TRACE("offset:(%" B_PRIu32 ")\n", offset); 374 ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset); 375 376 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 377 if (retVal == 0) { 378 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 379 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 380 return B_OK; 381 } 382 left++; 383 } 384 385 return B_ENTRY_NOT_FOUND; 386 } 387