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 "Extent.h" 8 9 10 Extent::Extent(Inode* inode) 11 : 12 fInode(inode), 13 fOffset(0) 14 { 15 } 16 17 18 void 19 Extent::FillMapEntry(void* pointerToMap) 20 { 21 uint64 firstHalf = *((uint64*)pointerToMap); 22 uint64 secondHalf = *((uint64*)pointerToMap + 1); 23 //dividing the 128 bits into 2 parts. 24 firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf); 25 secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf); 26 fMap->br_state = (firstHalf >> 63); 27 fMap->br_startoff = (firstHalf & MASK(63)) >> 9; 28 fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21); 29 fMap->br_blockcount = (secondHalf & MASK(21)); 30 TRACE("Extent::Init: startoff:(%ld), startblock:(%ld), blockcount:(%ld)," 31 "state:(%d)\n", 32 fMap->br_startoff, 33 fMap->br_startblock, 34 fMap->br_blockcount, 35 fMap->br_state 36 ); 37 } 38 39 40 status_t 41 Extent::FillBlockBuffer() 42 { 43 if (fMap->br_state != 0) 44 return B_BAD_VALUE; 45 46 int len = fInode->DirBlockSize(); 47 fBlockBuffer = new(std::nothrow) char[len]; 48 if (fBlockBuffer == NULL) 49 return B_NO_MEMORY; 50 51 Volume* volume = fInode->GetVolume(); 52 xfs_agblock_t numberOfBlocksInAg = volume->AgBlocks(); 53 54 uint64 agNo = FSBLOCKS_TO_AGNO(fMap->br_startblock, volume); 55 uint64 agBlockNo = FSBLOCKS_TO_AGBLOCKNO(fMap->br_startblock, volume); 56 xfs_fsblock_t blockToRead = FSBLOCKS_TO_BASICBLOCKS(volume->BlockLog(), 57 ((uint64)(agNo * numberOfBlocksInAg) + agBlockNo)); 58 59 xfs_daddr_t readPos = blockToRead * (BASICBLOCKSIZE) + fMap->br_startoff; 60 61 TRACE("blockToRead: (%ld), readPos: (%ld)\n", blockToRead, readPos); 62 if (read_pos(volume->Device(), readPos, fBlockBuffer, len) != len) { 63 ERROR("Extent::FillBlockBuffer(): IO Error"); 64 return B_IO_ERROR; 65 } 66 67 return B_OK; 68 } 69 70 71 status_t 72 Extent::Init() 73 { 74 fMap = new(std::nothrow) ExtentMapEntry; 75 if (fMap == NULL) 76 return B_NO_MEMORY; 77 78 ASSERT(BlockType() == true); 79 void* pointerToMap = DIR_DFORK_PTR(fInode->Buffer()); 80 FillMapEntry(pointerToMap); 81 ASSERT(fMap->br_blockcount == 1); 82 //TODO: This is always true for block directories 83 //If we use this implementation for leaf directories, this is not 84 //always true 85 status_t status = FillBlockBuffer(); 86 ExtentDataHeader* header = (ExtentDataHeader*)fBlockBuffer; 87 if (B_BENDIAN_TO_HOST_INT32(header->magic) == DIR2_BLOCK_HEADER_MAGIC) { 88 status = B_OK; 89 TRACE("Extent:Init(): Block read successfully\n"); 90 } else { 91 status = B_BAD_VALUE; 92 TRACE("Extent:Init(): Bad Block!\n"); 93 } 94 95 return status; 96 } 97 98 99 ExtentBlockTail* 100 Extent::BlockTail() 101 { 102 return (ExtentBlockTail*) 103 (fBlockBuffer + fInode->DirBlockSize() - sizeof(ExtentBlockTail)); 104 } 105 106 107 uint32 108 Extent::GetOffsetFromAddress(uint32 address) 109 { 110 address = address * 8; 111 // block offset in eight bytes, hence multiple with 8 112 return address & (fInode->DirBlockSize() - 1); 113 } 114 115 116 ExtentLeafEntry* 117 Extent::BlockFirstLeaf(ExtentBlockTail* tail) 118 { 119 return (ExtentLeafEntry*)tail - B_BENDIAN_TO_HOST_INT32(tail->count); 120 } 121 122 123 bool 124 Extent::BlockType() 125 { 126 bool status = true; 127 if (fInode->NoOfBlocks() != 1) 128 status = false; 129 if (fInode->Size() != fInode->DirBlockSize()) 130 status = false; 131 return status; 132 //TODO: Checks: Fileoffset must be 0 and 133 //length = directory block size / filesystem block size 134 } 135 136 137 int 138 Extent::EntrySize(int len) const 139 { 140 int entrySize= sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16); 141 // uint16 is for the tag 142 if (fInode->HasFileTypeField()) 143 entrySize += sizeof(uint8); 144 145 return (entrySize + 7) & -8; 146 // rounding off to closest multiple of 8 147 } 148 149 150 status_t 151 Extent::GetNext(char* name, size_t* length, xfs_ino_t* ino) 152 { 153 TRACE("Extend::GetNext\n"); 154 void* entry = (void*)((ExtentDataHeader*)fBlockBuffer + 1); 155 // This could be an unused entry so we should check 156 157 int numberOfEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->count); 158 TRACE("numberOfEntries:(%d)\n", numberOfEntries); 159 160 for (int i = 0; i < numberOfEntries; i++) { 161 TRACE("i:(%d)\n", i); 162 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 163 164 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 165 TRACE("Unused entry found\n"); 166 entry = (void*) 167 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 168 continue; 169 } 170 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 171 172 uint16 currentOffset = (char*)dataEntry - fBlockBuffer; 173 TRACE("GetNext: fOffset:(%d), currentOffset:(%d)\n", 174 fOffset, currentOffset); 175 176 if (fOffset >= currentOffset) { 177 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 178 continue; 179 } 180 181 if (dataEntry->namelen > *length) 182 return B_BUFFER_OVERFLOW; 183 184 fOffset = currentOffset; 185 memcpy(name, dataEntry->name, dataEntry->namelen); 186 name[dataEntry->namelen] = '\0'; 187 *length = dataEntry->namelen + 1; 188 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 189 190 TRACE("Entry found. Name: (%s), Length: (%ld),ino: (%ld)\n", name, 191 *length, *ino); 192 return B_OK; 193 } 194 195 return B_ENTRY_NOT_FOUND; 196 } 197 198 199 status_t 200 Extent::Lookup(const char* name, size_t length, xfs_ino_t* ino) 201 { 202 TRACE("Extent: Lookup\n"); 203 TRACE("Name: %s\n", name); 204 uint32 hashValueOfRequest = hashfunction(name, length); 205 TRACE("Hashval:(%ld)\n", hashValueOfRequest); 206 ExtentBlockTail* blockTail = BlockTail(); 207 ExtentLeafEntry* leafEntry = BlockFirstLeaf(blockTail); 208 209 int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT32(blockTail->count); 210 int left = 0; 211 int mid; 212 int right = numberOfLeafEntries - 1; 213 214 /* 215 * Trying to find the lowerbound of hashValueOfRequest 216 * This is slightly different from bsearch(), as we want the first 217 * instance of hashValueOfRequest and not any instance. 218 */ 219 while (left < right) { 220 mid = (left+right)/2; 221 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 222 if (hashval >= hashValueOfRequest) { 223 right = mid; 224 continue; 225 } 226 if (hashval < hashValueOfRequest) { 227 left = mid+1; 228 } 229 } 230 TRACE("left:(%d), right:(%d)\n", left, right); 231 232 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 233 == hashValueOfRequest) { 234 235 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 236 if (address == 0) { 237 left++; 238 continue; 239 } 240 241 uint32 offset = GetOffsetFromAddress(address); 242 TRACE("offset:(%d)\n", offset); 243 ExtentDataEntry* entry = (ExtentDataEntry*)(fBlockBuffer + offset); 244 245 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 246 if (retVal == 0) { 247 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 248 TRACE("ino:(%d)\n", *ino); 249 return B_OK; 250 } 251 left++; 252 } 253 254 return B_ENTRY_NOT_FOUND; 255 } 256 257