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:(%" B_PRIu64 "), startblock:(%" B_PRIu64 ")," 36 "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\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 int numberOfStaleEntries = B_BENDIAN_TO_HOST_INT32(BlockTail()->stale); 153 154 // We don't read stale entries. 155 numberOfEntries -= numberOfStaleEntries; 156 TRACE("numberOfEntries:(%" B_PRId32 ")\n", numberOfEntries); 157 uint16 currentOffset = (char*)entry - fBlockBuffer; 158 159 for (int i = 0; i < numberOfEntries; i++) { 160 TRACE("EntryNumber:(%" B_PRId32 ")\n", i); 161 ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry; 162 163 if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) { 164 TRACE("Unused entry found\n"); 165 currentOffset += B_BENDIAN_TO_HOST_INT16(unusedEntry->length); 166 entry = (void*) 167 ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length)); 168 i--; 169 continue; 170 } 171 ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry; 172 173 TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n", 174 fOffset, currentOffset); 175 176 if (fOffset >= currentOffset) { 177 entry = (void*)((char*)entry + EntrySize(dataEntry->namelen)); 178 currentOffset += EntrySize(dataEntry->namelen); 179 continue; 180 } 181 182 if ((size_t)(dataEntry->namelen) >= *length) 183 return B_BUFFER_OVERFLOW; 184 185 fOffset = currentOffset; 186 memcpy(name, dataEntry->name, dataEntry->namelen); 187 name[dataEntry->namelen] = '\0'; 188 *length = dataEntry->namelen + 1; 189 *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber); 190 191 TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n", name, 192 *length, *ino); 193 return B_OK; 194 } 195 196 return B_ENTRY_NOT_FOUND; 197 } 198 199 200 status_t 201 Extent::Lookup(const char* name, size_t length, xfs_ino_t* ino) 202 { 203 TRACE("Extent: Lookup\n"); 204 TRACE("Name: %s\n", name); 205 uint32 hashValueOfRequest = hashfunction(name, length); 206 TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest); 207 ExtentBlockTail* blockTail = BlockTail(); 208 ExtentLeafEntry* leafEntry = BlockFirstLeaf(blockTail); 209 210 int numberOfLeafEntries = B_BENDIAN_TO_HOST_INT32(blockTail->count); 211 int left = 0; 212 int mid; 213 int right = numberOfLeafEntries - 1; 214 215 /* 216 * Trying to find the lowerbound of hashValueOfRequest 217 * This is slightly different from bsearch(), as we want the first 218 * instance of hashValueOfRequest and not any instance. 219 */ 220 while (left < right) { 221 mid = (left+right)/2; 222 uint32 hashval = B_BENDIAN_TO_HOST_INT32(leafEntry[mid].hashval); 223 if (hashval >= hashValueOfRequest) { 224 right = mid; 225 continue; 226 } 227 if (hashval < hashValueOfRequest) { 228 left = mid+1; 229 } 230 } 231 TRACE("left:(%" B_PRId32 "), right:(%" B_PRId32 ")\n", left, right); 232 233 while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval) 234 == hashValueOfRequest) { 235 236 uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address); 237 if (address == 0) { 238 left++; 239 continue; 240 } 241 242 uint32 offset = GetOffsetFromAddress(address); 243 TRACE("offset:(%" B_PRIu32 ")\n", offset); 244 ExtentDataEntry* entry = (ExtentDataEntry*)(fBlockBuffer + offset); 245 246 int retVal = strncmp(name, (char*)entry->name, entry->namelen); 247 if (retVal == 0) { 248 *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber); 249 TRACE("ino:(%" B_PRIu64 ")\n", *ino); 250 return B_OK; 251 } 252 left++; 253 } 254 255 return B_ENTRY_NOT_FOUND; 256 } 257 258