1 /* 2 * Copyright 2010, Haiku Inc. All rights reserved. 3 * This file may be used under the terms of the MIT License. 4 * 5 * Authors: 6 * Janito V. Ferreira Filho 7 */ 8 9 10 #include "HTreeEntryIterator.h" 11 12 #include <new> 13 14 #include "CachedBlock.h" 15 #include "HTree.h" 16 #include "Inode.h" 17 18 19 //#define TRACE_EXT2 20 #ifdef TRACE_EXT2 21 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 22 #else 23 # define TRACE(x...) ; 24 #endif 25 #define ERROR(x...) dprintf("\33[34mext2:\33[0m " x) 26 27 28 HTreeEntryIterator::HTreeEntryIterator(off_t offset, Inode* directory) 29 : 30 fDirectory(directory), 31 fVolume(directory->GetVolume()), 32 fHasCollision(false), 33 fBlockSize(directory->GetVolume()->BlockSize()), 34 fParent(NULL), 35 fChild(NULL) 36 { 37 fInitStatus = fDirectory->FindBlock(offset, fBlockNum); 38 39 if (fInitStatus == B_OK) { 40 fFirstEntry = offset % fBlockSize / sizeof(HTreeEntry); 41 fCurrentEntry = fFirstEntry; 42 } 43 44 TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %llu, " 45 "entry no. %lu, parent: %p\n", this, fBlockNum, (uint32)fCurrentEntry, 46 fParent); 47 } 48 49 50 HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize, 51 Inode* directory, HTreeEntryIterator* parent, bool hasCollision) 52 : 53 fDirectory(directory), 54 fVolume(directory->GetVolume()), 55 fHasCollision(hasCollision), 56 fFirstEntry(1), 57 fCurrentEntry(1), 58 fBlockSize(blockSize), 59 fBlockNum(block), 60 fParent(parent), 61 fChild(NULL) 62 { 63 // fCurrentEntry is initialized to 1 to skip the fake directory entry 64 fInitStatus = B_OK; 65 66 TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %lu, " 67 "parent: %p\n", this, block, fParent); 68 } 69 70 71 status_t 72 HTreeEntryIterator::Init() 73 { 74 TRACE("HTreeEntryIterator::Init() first entry: %lu\n", 75 (uint32)fFirstEntry); 76 77 if (fInitStatus != B_OK) 78 return fInitStatus; 79 80 CachedBlock cached(fVolume); 81 const uint8* block = cached.SetTo(fBlockNum); 82 if (block == NULL) { 83 ERROR("Failed to read htree entry block.\n"); 84 fCount = fLimit = 0; 85 return B_IO_ERROR; 86 } 87 88 HTreeCountLimit* countLimit = (HTreeCountLimit*)( 89 &((HTreeEntry*)block)[fFirstEntry]); 90 91 fCount = countLimit->Count(); 92 fLimit = countLimit->Limit(); 93 94 if (fCount > fLimit) { 95 ERROR("HTreeEntryIterator::Init() bad fCount %u (fLimit %u)\n", 96 fCount, fLimit); 97 fCount = fLimit = 0; 98 return B_ERROR; 99 } 100 101 if (fLimit != fBlockSize / sizeof(HTreeEntry) - fFirstEntry) { 102 ERROR("HTreeEntryIterator::Init() bad fLimit %lu should be %lu " 103 "at block %llu\n", (uint32)fLimit, fBlockSize / sizeof(HTreeEntry) 104 - fFirstEntry, fBlockNum); 105 fCount = fLimit = 0; 106 return B_ERROR; 107 } 108 109 TRACE("HTreeEntryIterator::Init() count %lu limit %lu\n", 110 (uint32)fCount, (uint32)fLimit); 111 112 return B_OK; 113 } 114 115 116 HTreeEntryIterator::~HTreeEntryIterator() 117 { 118 TRACE("HTreeEntryIterator::~HTreeEntryIterator(): %p, parent: %p\n", this, 119 fParent); 120 delete fParent; 121 TRACE("HTreeEntryIterator::~HTreeEntryIterator(): Deleted the parent\n"); 122 } 123 124 125 status_t 126 HTreeEntryIterator::Lookup(uint32 hash, int indirections, 127 DirectoryIterator** directoryIterator, bool& detachRoot) 128 { 129 TRACE("HTreeEntryIterator::Lookup()\n"); 130 131 if (fCount == 0) 132 return B_ENTRY_NOT_FOUND; 133 134 CachedBlock cached(fVolume); 135 const uint8* block = cached.SetTo(fBlockNum); 136 if (block == NULL) { 137 ERROR("Failed to read htree entry block.\n"); 138 // Fallback to linear search 139 *directoryIterator = new(std::nothrow) 140 DirectoryIterator(fDirectory); 141 142 if (*directoryIterator == NULL) 143 return B_NO_MEMORY; 144 145 return B_OK; 146 } 147 148 HTreeEntry* start = (HTreeEntry*)block + fCurrentEntry + 1; 149 HTreeEntry* end = (HTreeEntry*)block + fCount + fFirstEntry - 1; 150 HTreeEntry* middle = start; 151 152 TRACE("HTreeEntryIterator::Lookup() current entry: %lu\n", 153 (uint32)fCurrentEntry); 154 TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n", 155 indirections, start, middle, end); 156 157 while (start <= end) { 158 middle = (HTreeEntry*)((end - start) / 2 159 + start); 160 161 TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n", 162 indirections, start, middle, end); 163 164 TRACE("HTreeEntryIterator::Lookup() %lx %lx\n", hash, middle->Hash()); 165 166 if (hash >= middle->Hash()) 167 start = middle + 1; 168 else 169 end = middle - 1; 170 } 171 172 --start; 173 174 fCurrentEntry = ((uint8*)start - block) / sizeof(HTreeEntry); 175 176 if (indirections == 0) { 177 TRACE("HTreeEntryIterator::Lookup(): Creating an indexed directory " 178 "iterator starting at block: %lu, hash: 0x%lX\n", start->Block(), 179 start->Hash()); 180 *directoryIterator = new(std::nothrow) 181 DirectoryIterator(fDirectory, start->Block() * fBlockSize, this); 182 183 if (*directoryIterator == NULL) 184 return B_NO_MEMORY; 185 186 detachRoot = true; 187 return B_OK; 188 } 189 190 TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator " 191 "starting at block: %lu, hash: 0x%lX\n", start->Block(), start->Hash()); 192 fsblock_t blockNum; 193 status_t status = fDirectory->FindBlock(start->Block() * fBlockSize, 194 blockNum); 195 if (status != B_OK) 196 return status; 197 198 delete fChild; 199 200 fChild = new(std::nothrow) HTreeEntryIterator(blockNum, fBlockSize, 201 fDirectory, this, (start->Hash() & 1) == 1); 202 if (fChild == NULL) 203 return B_NO_MEMORY; 204 205 status = fChild->Init(); 206 if (status != B_OK) 207 return status; 208 209 return fChild->Lookup(hash, indirections - 1, directoryIterator, 210 detachRoot); 211 } 212 213 214 status_t 215 HTreeEntryIterator::GetNext(uint32& childBlock) 216 { 217 fCurrentEntry++; 218 TRACE("HTreeEntryIterator::GetNext(): current entry: %lu count: %lu, " 219 "limit: %lu\n", (uint32)fCurrentEntry, (uint32)fCount, (uint32)fLimit); 220 bool endOfBlock = fCurrentEntry >= (fCount + fFirstEntry); 221 222 if (endOfBlock) { 223 TRACE("HTreeEntryIterator::GetNext(): end of entries in the block\n"); 224 if (fParent == NULL) { 225 TRACE("HTreeEntryIterator::GetNext(): block was the root block\n"); 226 return B_ENTRY_NOT_FOUND; 227 } 228 229 uint32 logicalBlock; 230 status_t status = fParent->GetNext(logicalBlock); 231 if (status != B_OK) 232 return status; 233 234 TRACE("HTreeEntryIterator::GetNext(): moving to next block: %lu\n", 235 logicalBlock); 236 237 status = fDirectory->FindBlock(logicalBlock * fBlockSize, fBlockNum); 238 if (status != B_OK) 239 return status; 240 241 fFirstEntry = 1; // Skip fake directory entry 242 fCurrentEntry = 1; 243 status = Init(); 244 if (status != B_OK) 245 return status; 246 247 fHasCollision = fParent->HasCollision(); 248 } 249 250 CachedBlock cached(fVolume); 251 const uint8* block = cached.SetTo(fBlockNum); 252 if (block == NULL) 253 return B_IO_ERROR; 254 255 HTreeEntry* entry = &((HTreeEntry*)block)[fCurrentEntry]; 256 257 if (!endOfBlock) 258 fHasCollision = (entry[fCurrentEntry].Hash() & 1) == 1; 259 260 TRACE("HTreeEntryIterator::GetNext(): next block: %lu\n", 261 entry->Block()); 262 263 childBlock = entry->Block(); 264 265 return B_OK; 266 } 267 268 269 uint32 270 HTreeEntryIterator::BlocksNeededForNewEntry() 271 { 272 TRACE("HTreeEntryIterator::BlocksNeededForNewEntry(): block num: %llu, " 273 "volume: %p\n", fBlockNum, fVolume); 274 CachedBlock cached(fVolume); 275 276 const uint8* blockData = cached.SetTo(fBlockNum); 277 const HTreeEntry* entries = (const HTreeEntry*)blockData; 278 const HTreeCountLimit* countLimit = 279 (const HTreeCountLimit*)&entries[fFirstEntry]; 280 281 uint32 newBlocks = 0; 282 if (countLimit->IsFull()) { 283 newBlocks++; 284 285 if (fParent != NULL) 286 newBlocks += fParent->BlocksNeededForNewEntry(); 287 else { 288 // Need a new level 289 HTreeRoot* root = (HTreeRoot*)entries; 290 291 if (root->indirection_levels == 1) { 292 // Maximum supported indirection levels reached 293 return B_DEVICE_FULL; 294 } 295 296 newBlocks++; 297 } 298 } 299 300 return newBlocks; 301 } 302 303 304 status_t 305 HTreeEntryIterator::InsertEntry(Transaction& transaction, uint32 hash, 306 off_t blockNum, off_t newBlocksPos, bool hasCollision) 307 { 308 TRACE("HTreeEntryIterator::InsertEntry(): block num: %llu\n", fBlockNum); 309 CachedBlock cached(fVolume); 310 311 uint8* blockData = cached.SetToWritable(transaction, fBlockNum); 312 if (blockData == NULL) 313 return B_IO_ERROR; 314 315 HTreeEntry* entries = (HTreeEntry*)blockData; 316 317 HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry]; 318 uint16 count = countLimit->Count(); 319 320 if (count == countLimit->Limit()) { 321 TRACE("HTreeEntryIterator::InsertEntry(): Splitting the node\n"); 322 panic("Splitting a HTree node required, but isn't yet fully " 323 "supported\n"); 324 325 fsblock_t physicalBlock; 326 status_t status = fDirectory->FindBlock(newBlocksPos, physicalBlock); 327 if (status != B_OK) 328 return status; 329 330 CachedBlock secondCached(fVolume); 331 uint8* secondBlockData = secondCached.SetToWritable(transaction, 332 physicalBlock); 333 if (secondBlockData == NULL) 334 return B_IO_ERROR; 335 336 HTreeFakeDirEntry* fakeEntry = (HTreeFakeDirEntry*)secondBlockData; 337 fakeEntry->inode_id = 0; // ? 338 fakeEntry->SetEntryLength(fBlockSize); 339 fakeEntry->name_length = 0; 340 fakeEntry->file_type = 0; // ? 341 342 HTreeEntry* secondBlockEntries = (HTreeEntry*)secondBlockData; 343 memmove(&entries[fFirstEntry + count / 2], &secondBlockEntries[1], 344 (count - count / 2) * sizeof(HTreeEntry)); 345 } 346 347 TRACE("HTreeEntryIterator::InsertEntry(): Inserting node. Count: %u, " 348 "current entry: %u\n", count, fCurrentEntry); 349 350 if (count > 0) { 351 TRACE("HTreeEntryIterator::InsertEntry(): memmove(%u, %u, %u)\n", 352 fCurrentEntry + 2, fCurrentEntry + 1, count + fFirstEntry 353 - fCurrentEntry - 1); 354 memmove(&entries[fCurrentEntry + 2], &entries[fCurrentEntry + 1], 355 (count + fFirstEntry - fCurrentEntry - 1) * sizeof(HTreeEntry)); 356 } 357 358 uint32 oldHash = entries[fCurrentEntry].Hash(); 359 entries[fCurrentEntry].SetHash(hasCollision ? oldHash | 1 : oldHash & ~1); 360 entries[fCurrentEntry + 1].SetHash((oldHash & 1) == 0 ? hash & ~1 361 : hash | 1); 362 entries[fCurrentEntry + 1].SetBlock(blockNum); 363 364 countLimit->SetCount(count + 1); 365 366 return B_OK; 367 } 368