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