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