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 %" B_PRIu64 ", " 45 "entry no. %u, parent: %p\n", this, fBlockNum, 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 %" 67 B_PRIu32 ", parent: %p\n", this, block, fParent); 68 } 69 70 71 status_t 72 HTreeEntryIterator::Init() 73 { 74 TRACE("HTreeEntryIterator::Init() first entry: %u\n", 75 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 %u should be %" B_PRIu32 103 " at block %" B_PRIu64 "\n", fLimit, 104 (uint32)(fBlockSize / sizeof(HTreeEntry) - fFirstEntry), fBlockNum); 105 fCount = fLimit = 0; 106 return B_ERROR; 107 } 108 109 TRACE("HTreeEntryIterator::Init() count %u limit %u\n", 110 fCount, 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: %u\n", 153 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() %" B_PRIx32 " %" B_PRIx32 "\n", 165 hash, middle->Hash()); 166 167 if (hash >= middle->Hash()) 168 start = middle + 1; 169 else 170 end = middle - 1; 171 } 172 173 --start; 174 175 fCurrentEntry = ((uint8*)start - block) / sizeof(HTreeEntry); 176 177 if (indirections == 0) { 178 TRACE("HTreeEntryIterator::Lookup(): Creating an indexed directory " 179 "iterator starting at block: %" B_PRIu32 ", hash: 0x%" B_PRIx32 180 "\n", start->Block(), start->Hash()); 181 *directoryIterator = new(std::nothrow) 182 DirectoryIterator(fDirectory, start->Block() * fBlockSize, this); 183 184 if (*directoryIterator == NULL) 185 return B_NO_MEMORY; 186 187 detachRoot = true; 188 return B_OK; 189 } 190 191 TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator " 192 "starting at block: %" B_PRIu32 ", hash: 0x%" B_PRIx32 "\n", 193 start->Block(), start->Hash()); 194 fsblock_t blockNum; 195 status_t status = fDirectory->FindBlock(start->Block() * fBlockSize, 196 blockNum); 197 if (status != B_OK) 198 return status; 199 200 delete fChild; 201 202 fChild = new(std::nothrow) HTreeEntryIterator(blockNum, fBlockSize, 203 fDirectory, this, (start->Hash() & 1) == 1); 204 if (fChild == NULL) 205 return B_NO_MEMORY; 206 207 status = fChild->Init(); 208 if (status != B_OK) 209 return status; 210 211 return fChild->Lookup(hash, indirections - 1, directoryIterator, 212 detachRoot); 213 } 214 215 216 status_t 217 HTreeEntryIterator::GetNext(uint32& childBlock) 218 { 219 fCurrentEntry++; 220 TRACE("HTreeEntryIterator::GetNext(): current entry: %u count: %u, " 221 "limit: %u\n", fCurrentEntry, fCount, fLimit); 222 bool endOfBlock = fCurrentEntry >= (fCount + fFirstEntry); 223 224 if (endOfBlock) { 225 TRACE("HTreeEntryIterator::GetNext(): end of entries in the block\n"); 226 if (fParent == NULL) { 227 TRACE("HTreeEntryIterator::GetNext(): block was the root block\n"); 228 return B_ENTRY_NOT_FOUND; 229 } 230 231 uint32 logicalBlock; 232 status_t status = fParent->GetNext(logicalBlock); 233 if (status != B_OK) 234 return status; 235 236 TRACE("HTreeEntryIterator::GetNext(): moving to next block: %" B_PRIx32 237 "\n", logicalBlock); 238 239 status = fDirectory->FindBlock(logicalBlock * fBlockSize, fBlockNum); 240 if (status != B_OK) 241 return status; 242 243 fFirstEntry = 1; // Skip fake directory entry 244 fCurrentEntry = 1; 245 status = Init(); 246 if (status != B_OK) 247 return status; 248 249 fHasCollision = fParent->HasCollision(); 250 } 251 252 CachedBlock cached(fVolume); 253 const uint8* block = cached.SetTo(fBlockNum); 254 if (block == NULL) 255 return B_IO_ERROR; 256 257 HTreeEntry* entry = &((HTreeEntry*)block)[fCurrentEntry]; 258 259 if (!endOfBlock) 260 fHasCollision = (entry[fCurrentEntry].Hash() & 1) == 1; 261 262 TRACE("HTreeEntryIterator::GetNext(): next block: %" B_PRIu32 "\n", 263 entry->Block()); 264 265 childBlock = entry->Block(); 266 267 return B_OK; 268 } 269 270 271 uint32 272 HTreeEntryIterator::BlocksNeededForNewEntry() 273 { 274 TRACE("HTreeEntryIterator::BlocksNeededForNewEntry(): block num: %" 275 B_PRIu64 ", volume: %p\n", fBlockNum, fVolume); 276 CachedBlock cached(fVolume); 277 278 const uint8* blockData = cached.SetTo(fBlockNum); 279 const HTreeEntry* entries = (const HTreeEntry*)blockData; 280 const HTreeCountLimit* countLimit = 281 (const HTreeCountLimit*)&entries[fFirstEntry]; 282 283 uint32 newBlocks = 0; 284 if (countLimit->IsFull()) { 285 newBlocks++; 286 287 if (fParent != NULL) 288 newBlocks += fParent->BlocksNeededForNewEntry(); 289 else { 290 // Need a new level 291 HTreeRoot* root = (HTreeRoot*)entries; 292 293 if (root->indirection_levels == 1) { 294 // Maximum supported indirection levels reached 295 return B_DEVICE_FULL; 296 } 297 298 newBlocks++; 299 } 300 } 301 302 return newBlocks; 303 } 304 305 306 status_t 307 HTreeEntryIterator::InsertEntry(Transaction& transaction, uint32 hash, 308 off_t blockNum, off_t newBlocksPos, bool hasCollision) 309 { 310 TRACE("HTreeEntryIterator::InsertEntry(): block num: %" B_PRIu64 "\n", 311 fBlockNum); 312 CachedBlock cached(fVolume); 313 314 uint8* blockData = cached.SetToWritable(transaction, fBlockNum); 315 if (blockData == NULL) 316 return B_IO_ERROR; 317 318 HTreeEntry* entries = (HTreeEntry*)blockData; 319 320 HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry]; 321 uint16 count = countLimit->Count(); 322 323 if (count == countLimit->Limit()) { 324 TRACE("HTreeEntryIterator::InsertEntry(): Splitting the node\n"); 325 panic("Splitting a HTree node required, but isn't yet fully " 326 "supported\n"); 327 328 fsblock_t physicalBlock; 329 status_t status = fDirectory->FindBlock(newBlocksPos, physicalBlock); 330 if (status != B_OK) 331 return status; 332 333 CachedBlock secondCached(fVolume); 334 uint8* secondBlockData = secondCached.SetToWritable(transaction, 335 physicalBlock); 336 if (secondBlockData == NULL) 337 return B_IO_ERROR; 338 339 HTreeFakeDirEntry* fakeEntry = (HTreeFakeDirEntry*)secondBlockData; 340 fakeEntry->inode_id = 0; // ? 341 fakeEntry->SetEntryLength(fBlockSize); 342 fakeEntry->name_length = 0; 343 fakeEntry->file_type = 0; // ? 344 345 HTreeEntry* secondBlockEntries = (HTreeEntry*)secondBlockData; 346 memmove(&entries[fFirstEntry + count / 2], &secondBlockEntries[1], 347 (count - count / 2) * sizeof(HTreeEntry)); 348 } 349 350 TRACE("HTreeEntryIterator::InsertEntry(): Inserting node. Count: %u, " 351 "current entry: %u\n", count, fCurrentEntry); 352 353 if (count > 0) { 354 TRACE("HTreeEntryIterator::InsertEntry(): memmove(%u, %u, %u)\n", 355 fCurrentEntry + 2, fCurrentEntry + 1, count + fFirstEntry 356 - fCurrentEntry - 1); 357 memmove(&entries[fCurrentEntry + 2], &entries[fCurrentEntry + 1], 358 (count + fFirstEntry - fCurrentEntry - 1) * sizeof(HTreeEntry)); 359 } 360 361 uint32 oldHash = entries[fCurrentEntry].Hash(); 362 entries[fCurrentEntry].SetHash(hasCollision ? oldHash | 1 : oldHash & ~1); 363 entries[fCurrentEntry + 1].SetHash((oldHash & 1) == 0 ? hash & ~1 364 : hash | 1); 365 entries[fCurrentEntry + 1].SetBlock(blockNum); 366 367 countLimit->SetCount(count + 1); 368 369 return B_OK; 370 } 371