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