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