1 /* 2 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de. 3 * This file may be used under the terms of the MIT License. 4 */ 5 6 7 #include "DirectoryIterator.h" 8 9 #include <string.h> 10 11 #include <AutoDeleter.h> 12 #include <util/VectorSet.h> 13 14 #include "CachedBlock.h" 15 #include "CRCTable.h" 16 #include "HTree.h" 17 #include "Inode.h" 18 19 20 #undef ASSERT 21 22 //#define TRACE_EXT2 23 #ifdef TRACE_EXT2 24 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 25 # define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); } 26 #else 27 # define TRACE(x...) ; 28 # define ASSERT(x) ; 29 #endif 30 31 32 struct HashedEntry 33 { 34 uint8* position; 35 uint32 hash; 36 37 bool operator<(const HashedEntry& other) const 38 { 39 return hash <= other.hash; 40 } 41 42 bool operator>(const HashedEntry& other) const 43 { 44 return hash >= other.hash; 45 } 46 }; 47 48 49 DirectoryIterator::DirectoryIterator(Inode* directory, off_t start, 50 HTreeEntryIterator* parent) 51 : 52 fDirectory(directory), 53 fVolume(directory->GetVolume()), 54 fBlockSize(fVolume->BlockSize()), 55 fParent(parent), 56 fNumBlocks(directory->Size() == 0 ? 0 57 : (directory->Size() - 1) / fBlockSize + 1), 58 fLogicalBlock(start / fBlockSize), 59 fDisplacement(start % fBlockSize), 60 fPreviousDisplacement(fDisplacement), 61 fStartLogicalBlock(fLogicalBlock), 62 fStartDisplacement(fDisplacement) 63 { 64 TRACE("DirectoryIterator::DirectoryIterator() %" B_PRIdINO ": num blocks: " 65 "%" B_PRIu32 "\n", fDirectory->ID(), fNumBlocks); 66 fIndexing = parent != NULL; 67 fInitStatus = fDirectory->FindBlock(start, fPhysicalBlock); 68 fStartPhysicalBlock = fPhysicalBlock; 69 } 70 71 72 DirectoryIterator::~DirectoryIterator() 73 { 74 TRACE("DirectoryIterator::~DirectoryIterator(): %p, parent: %p\n", this, 75 fParent); 76 delete fParent; 77 TRACE("DirectoryIterator::~DirectoryIterator(): Deleted the parent\n"); 78 } 79 80 81 status_t 82 DirectoryIterator::InitCheck() 83 { 84 return fInitStatus; 85 } 86 87 88 status_t 89 DirectoryIterator::Get(char* name, size_t* _nameLength, ino_t* _id) 90 { 91 TRACE("DirectoryIterator::Get() ID %" B_PRIdINO "\n", fDirectory->ID()); 92 if (_Offset() >= fDirectory->Size()) { 93 TRACE("DirectoryIterator::Get() out of entries\n"); 94 return B_ENTRY_NOT_FOUND; 95 } 96 97 CachedBlock cached(fVolume); 98 const uint8* block = cached.SetTo(fPhysicalBlock); 99 if (block == NULL) 100 return B_IO_ERROR; 101 102 ASSERT(_CheckBlock(block) == B_OK); 103 104 TRACE("DirectoryIterator::Get(): Displacement: %" B_PRIu32 "\n", 105 fDisplacement); 106 const ext2_dir_entry* entry = (const ext2_dir_entry*)&block[fDisplacement]; 107 108 if (entry->Length() == 0 || entry->InodeID() == 0) 109 return B_BAD_DATA; 110 111 if (entry->NameLength() != 0) { 112 size_t length = entry->NameLength(); 113 114 TRACE("block %" B_PRIu32 ", displacement %" B_PRIu32 ": entry ino %" 115 B_PRIu32 ", length %u, name length %" B_PRIuSIZE ", type %u\n", 116 fLogicalBlock, fDisplacement, entry->InodeID(), entry->Length(), 117 length, entry->FileType()); 118 119 if (*_nameLength > 0) { 120 if (length + 1 > *_nameLength) 121 return B_BUFFER_OVERFLOW; 122 123 memcpy(name, entry->name, length); 124 name[length] = '\0'; 125 126 *_nameLength = length; 127 } 128 129 *_id = entry->InodeID(); 130 } else 131 *_nameLength = 0; 132 133 return B_OK; 134 } 135 136 137 status_t 138 DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id) 139 { 140 status_t status; 141 while ((status = Get(name, _nameLength, _id)) == B_BAD_DATA) { 142 status = Next(); 143 if (status != B_OK) 144 return status; 145 } 146 return status; 147 } 148 149 150 status_t 151 DirectoryIterator::Next() 152 { 153 TRACE("DirectoryIterator::Next() fDirectory->ID() %" B_PRIdINO "\n", 154 fDirectory->ID()); 155 156 if (_Offset() >= fDirectory->Size()) { 157 TRACE("DirectoryIterator::Next() out of entries\n"); 158 return B_ENTRY_NOT_FOUND; 159 } 160 161 TRACE("DirectoryIterator::Next(): Creating cached block\n"); 162 163 CachedBlock cached(fVolume); 164 ext2_dir_entry* entry; 165 166 TRACE("DirectoryIterator::Next(): Loading cached block\n"); 167 const uint8* block = cached.SetTo(fPhysicalBlock); 168 if (block == NULL) 169 return B_IO_ERROR; 170 171 ASSERT(_CheckBlock(block) == B_OK); 172 173 entry = (ext2_dir_entry*)(block + fDisplacement); 174 175 do { 176 TRACE("Checking entry at block %" B_PRIu64 ", displacement %" B_PRIu32 177 " entry inodeid %" B_PRIu32 "\n", fPhysicalBlock, fDisplacement, 178 entry->InodeID()); 179 180 if (entry->Length() != 0) { 181 if (!entry->IsValid()) { 182 TRACE("invalid entry.\n"); 183 return B_BAD_DATA; 184 } 185 fPreviousDisplacement = fDisplacement; 186 fDisplacement += entry->Length(); 187 } else 188 fDisplacement = fBlockSize; 189 190 if (fDisplacement == fBlockSize) { 191 TRACE("Reached end of block\n"); 192 193 fDisplacement = 0; 194 195 status_t status = _NextBlock(); 196 if (status != B_OK) 197 return status; 198 199 if ((off_t)(_Offset() + ext2_dir_entry::MinimumSize()) 200 >= fDirectory->Size()) { 201 TRACE("DirectoryIterator::Next() end of directory file\n"); 202 return B_ENTRY_NOT_FOUND; 203 } 204 status = fDirectory->FindBlock(_Offset(), fPhysicalBlock); 205 if (status != B_OK) 206 return status; 207 208 block = cached.SetTo(fPhysicalBlock); 209 if (block == NULL) 210 return B_IO_ERROR; 211 ASSERT(_CheckBlock(block) == B_OK); 212 213 } else if (fDisplacement > fBlockSize) { 214 TRACE("The entry isn't block aligned.\n"); 215 // TODO: Is block alignment obligatory? 216 return B_BAD_DATA; 217 } 218 219 entry = (ext2_dir_entry*)(block + fDisplacement); 220 221 TRACE("DirectoryIterator::Next() skipping entry %d %" B_PRIu32 "\n", 222 entry->Length(), entry->InodeID()); 223 } while (entry->Length() == 0 || entry->InodeID() == 0); 224 225 TRACE("DirectoryIterator::Next() entry->Length() %d entry->name %*s\n", 226 entry->Length(), entry->NameLength(), entry->name); 227 228 return B_OK; 229 } 230 231 232 status_t 233 DirectoryIterator::Rewind() 234 { 235 fDisplacement = 0; 236 fPreviousDisplacement = 0; 237 fLogicalBlock = 0; 238 239 return fDirectory->FindBlock(0, fPhysicalBlock); 240 } 241 242 243 void 244 DirectoryIterator::Restart() 245 { 246 TRACE("DirectoryIterator::Restart(): (logical, physical, displacement): " 247 "current: (%" B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 "), start: (%" 248 B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 ")\n", fLogicalBlock, 249 fPhysicalBlock, fDisplacement, fStartLogicalBlock, fStartPhysicalBlock, 250 fStartDisplacement); 251 fLogicalBlock = fStartLogicalBlock; 252 fPhysicalBlock = fStartPhysicalBlock; 253 fDisplacement = fPreviousDisplacement = fStartDisplacement; 254 } 255 256 257 status_t 258 DirectoryIterator::AddEntry(Transaction& transaction, const char* name, 259 size_t _nameLength, ino_t id, uint8 type) 260 { 261 TRACE("DirectoryIterator::AddEntry(%s, ...)\n", name); 262 263 uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH 264 : _nameLength; 265 266 status_t status = B_OK; 267 while (status == B_OK) { 268 uint16 pos = 0; 269 uint16 newLength; 270 271 status = _AllocateBestEntryInBlock(nameLength, pos, newLength); 272 if (status == B_OK) { 273 return _AddEntry(transaction, name, nameLength, id, type, newLength, 274 pos); 275 } else if (status != B_DEVICE_FULL) 276 return status; 277 278 fDisplacement = 0; 279 status = _NextBlock(); 280 if (status == B_OK) 281 status = fDirectory->FindBlock(_Offset(), fPhysicalBlock); 282 } 283 284 if (status != B_ENTRY_NOT_FOUND) 285 return status; 286 287 bool firstSplit = fNumBlocks == 1 && fVolume->IndexedDirectories(); 288 289 fNumBlocks++; 290 291 if (fIndexing) { 292 TRACE("DirectoryIterator::AddEntry(): Adding another HTree leaf\n"); 293 fNumBlocks += fParent->BlocksNeededForNewEntry(); 294 } else if (firstSplit) { 295 // Allocate another block (fNumBlocks should become 3) 296 TRACE("DirectoryIterator::AddEntry(): Creating index for directory\n"); 297 fNumBlocks++; 298 } else 299 TRACE("DirectoryIterator::AddEntry(): Enlarging directory\n"); 300 301 status = fDirectory->Resize(transaction, fNumBlocks * fBlockSize); 302 if (status != B_OK) 303 return status; 304 305 if (firstSplit || fIndexing) { 306 // firstSplit and fIndexing are mutually exclusive 307 return _SplitIndexedBlock(transaction, name, nameLength, id, type, 308 fNumBlocks - 1, firstSplit); 309 } 310 311 fLogicalBlock = fNumBlocks - 1; 312 status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock); 313 if (status != B_OK) 314 return status; 315 316 return _AddEntry(transaction, name, nameLength, id, type, fBlockSize, 0, 317 false); 318 } 319 320 321 status_t 322 DirectoryIterator::FindEntry(const char* name, ino_t* _id) 323 { 324 TRACE("DirectoryIterator::FindEntry(): %p %p\n", this, name); 325 char buffer[EXT2_NAME_LENGTH + 1]; 326 ino_t id; 327 328 status_t status = B_OK; 329 size_t length = strlen(name); 330 while (status == B_OK) { 331 size_t nameLength = EXT2_NAME_LENGTH; 332 status = Get(buffer, &nameLength, &id); 333 if (status == B_OK) { 334 if (length == nameLength 335 && strncmp(name, buffer, nameLength) == 0) { 336 if (_id != NULL) 337 *_id = id; 338 return B_OK; 339 } 340 } else if (status != B_BAD_DATA) 341 break; 342 status = Next(); 343 } 344 345 return status; 346 } 347 348 349 status_t 350 DirectoryIterator::RemoveEntry(Transaction& transaction) 351 { 352 TRACE("DirectoryIterator::RemoveEntry()\n"); 353 ext2_dir_entry* previousEntry; 354 ext2_dir_entry* dirEntry; 355 CachedBlock cached(fVolume); 356 357 uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 358 uint32 maxSize = _MaxSize(); 359 360 if (fDisplacement == 0) { 361 previousEntry = (ext2_dir_entry*)&block[fDisplacement]; 362 363 fPreviousDisplacement = fDisplacement; 364 fDisplacement += previousEntry->Length(); 365 366 if (fDisplacement == maxSize) { 367 previousEntry->SetInodeID(0); 368 fDisplacement = 0; 369 return B_OK; 370 } else if (fDisplacement > maxSize) { 371 TRACE("DirectoryIterator::RemoveEntry(): Entry isn't aligned to " 372 "block entry."); 373 return B_BAD_DATA; 374 } 375 376 dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 377 memcpy(&block[fPreviousDisplacement], &block[fDisplacement], 378 dirEntry->Length()); 379 380 previousEntry->SetLength(fDisplacement - fPreviousDisplacement 381 + previousEntry->Length()); 382 383 fDirectory->SetDirEntryChecksum(block); 384 385 ASSERT(_CheckBlock(block) == B_OK); 386 387 return B_OK; 388 } 389 390 TRACE("DirectoryIterator::RemoveEntry() fDisplacement %" B_PRIu32 "\n", 391 fDisplacement); 392 393 if (fPreviousDisplacement == fDisplacement) { 394 char buffer[EXT2_NAME_LENGTH + 1]; 395 396 dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 397 398 memcpy(buffer, dirEntry->name, (uint32)dirEntry->name_length); 399 400 fDisplacement = 0; 401 status_t status = FindEntry(dirEntry->name); 402 if (status == B_ENTRY_NOT_FOUND) 403 return B_BAD_DATA; 404 if (status != B_OK) 405 return status; 406 } 407 408 previousEntry = (ext2_dir_entry*)&block[fPreviousDisplacement]; 409 dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 410 411 previousEntry->SetLength(previousEntry->Length() + dirEntry->Length()); 412 413 memset(&block[fDisplacement], 0, 414 fPreviousDisplacement + previousEntry->Length() - fDisplacement); 415 416 fDirectory->SetDirEntryChecksum(block); 417 418 ASSERT(_CheckBlock(block) == B_OK); 419 420 return B_OK; 421 } 422 423 424 status_t 425 DirectoryIterator::ChangeEntry(Transaction& transaction, ino_t id, 426 uint8 fileType) 427 { 428 CachedBlock cached(fVolume); 429 430 uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 431 if (block == NULL) 432 return B_IO_ERROR; 433 434 ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 435 dirEntry->SetInodeID(id); 436 dirEntry->file_type = fileType; 437 438 fDirectory->SetDirEntryChecksum(block); 439 440 ASSERT(_CheckBlock(block) == B_OK); 441 442 return B_OK; 443 } 444 445 446 status_t 447 DirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos, 448 uint16& newLength) 449 { 450 TRACE("DirectoryIterator::_AllocateBestEntryInBlock()\n"); 451 CachedBlock cached(fVolume); 452 const uint8* block = cached.SetTo(fPhysicalBlock); 453 454 ASSERT(_CheckBlock(block) == B_OK); 455 456 uint16 requiredLength = EXT2_DIR_REC_LEN(nameLength); 457 uint32 maxSize = _MaxSize(); 458 459 uint16 bestPos = maxSize; 460 uint16 bestLength = maxSize; 461 uint16 bestRealLength = maxSize; 462 ext2_dir_entry* dirEntry; 463 464 while (pos < maxSize) { 465 dirEntry = (ext2_dir_entry*)&block[pos]; 466 if (!_CheckDirEntry(dirEntry, block)) { 467 TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): invalid " 468 "dirEntry->Length() pos %d\n", pos); 469 return B_BAD_DATA; 470 } 471 472 uint16 realLength = EXT2_DIR_REC_LEN(dirEntry->NameLength()); 473 uint16 emptySpace = dirEntry->Length(); 474 if (dirEntry->InodeID() != 0) 475 emptySpace -= realLength; 476 if (emptySpace == requiredLength) { 477 // Found an exact match 478 TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found an " 479 "exact length match\n"); 480 newLength = realLength; 481 482 return B_OK; 483 } else if (emptySpace > requiredLength && emptySpace < bestLength) { 484 bestPos = pos; 485 bestLength = emptySpace; 486 bestRealLength = realLength; 487 } 488 489 pos += dirEntry->Length(); 490 } 491 492 if (bestPos == maxSize) 493 return B_DEVICE_FULL; 494 495 TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found a suitable " 496 "location: %u\n", bestPos); 497 pos = bestPos; 498 newLength = bestRealLength; 499 500 return B_OK; 501 } 502 503 504 status_t 505 DirectoryIterator::_AddEntry(Transaction& transaction, const char* name, 506 uint8 nameLength, ino_t id, uint8 type, uint16 newLength, uint16 pos, 507 bool hasPrevious) 508 { 509 TRACE("DirectoryIterator::_AddEntry(%s, %d, %" B_PRIdINO ", %d, %d, %d, " 510 "%c)\n", name, nameLength, id, type, newLength, pos, 511 hasPrevious ? 't' : 'f'); 512 CachedBlock cached(fVolume); 513 514 uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 515 if (block == NULL) 516 return B_IO_ERROR; 517 518 ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos]; 519 520 if (hasPrevious) { 521 uint16 previousLength = dirEntry->Length(); 522 dirEntry->SetLength(newLength); 523 524 dirEntry = (ext2_dir_entry*)&block[pos + newLength]; 525 newLength = previousLength - newLength; 526 } 527 528 dirEntry->SetLength(newLength); 529 dirEntry->name_length = nameLength; 530 dirEntry->SetInodeID(id); 531 dirEntry->file_type = type; 532 memcpy(dirEntry->name, name, nameLength); 533 534 fDirectory->SetDirEntryChecksum(block); 535 536 ASSERT(_CheckBlock(block) == B_OK); 537 538 TRACE("DirectoryIterator::_AddEntry(): Done\n"); 539 540 return B_OK; 541 } 542 543 544 status_t 545 DirectoryIterator::_SplitIndexedBlock(Transaction& transaction, 546 const char* name, uint8 nameLength, ino_t id, uint8 type, 547 uint32 newBlocksPos, bool firstSplit) 548 { 549 // Block is full, split required 550 TRACE("DirectoryIterator::_SplitIndexedBlock(.., %s, %u, %" B_PRIdINO ", %" 551 B_PRIu32 ", %c)\n", name, nameLength, id, newBlocksPos, 552 firstSplit ? 't' : 'f'); 553 554 // Allocate a buffer for the entries in the block 555 uint8* buffer = new(std::nothrow) uint8[fBlockSize]; 556 if (buffer == NULL) 557 return B_NO_MEMORY; 558 ArrayDeleter<uint8> bufferDeleter(buffer); 559 560 fsblock_t firstPhysicalBlock = 0; 561 uint32 maxSize = _MaxSize(); 562 563 // Prepare block to hold the first half of the entries and fill the buffer 564 CachedBlock cachedFirst(fVolume); 565 566 if (firstSplit) { 567 // Save all entries to the buffer 568 status_t status = fDirectory->FindBlock(0, firstPhysicalBlock); 569 if (status != B_OK) 570 return status; 571 572 const uint8* srcBlock = cachedFirst.SetTo(firstPhysicalBlock); 573 if (srcBlock == NULL) 574 return B_IO_ERROR; 575 576 memcpy(buffer, srcBlock, fBlockSize); 577 578 status = fDirectory->FindBlock(fBlockSize, fPhysicalBlock); 579 if (status != B_OK) 580 return status; 581 } 582 583 uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock); 584 uint8* secondBlock = NULL; 585 if (firstBlock == NULL) 586 return B_IO_ERROR; 587 588 status_t status; 589 590 if (!firstSplit) { 591 // Save all entries to the buffer 592 memcpy(buffer, firstBlock, fBlockSize); 593 } else { 594 // Initialize the root node 595 fDirectory->Node().SetFlag(EXT2_INODE_INDEXED); 596 HTreeRoot* root; 597 598 secondBlock = cachedFirst.SetToWritable(transaction, 599 firstPhysicalBlock, true); 600 if (secondBlock == NULL) 601 return B_IO_ERROR; 602 603 status = fDirectory->WriteBack(transaction); 604 if (status != B_OK) 605 return status; 606 607 memcpy(secondBlock, buffer, 2 * (sizeof(HTreeFakeDirEntry) + 4)); 608 609 root = (HTreeRoot*)secondBlock; 610 611 HTreeFakeDirEntry* dotdot = &root->dotdot; 612 dotdot->SetEntryLength(maxSize - (sizeof(HTreeFakeDirEntry) + 4)); 613 614 root->hash_version = fVolume->DefaultHashVersion(); 615 root->root_info_length = 8; 616 root->indirection_levels = 0; 617 618 root->count_limit->SetLimit((maxSize 619 - ((uint8*)root->count_limit - secondBlock)) / sizeof(HTreeEntry)); 620 root->count_limit->SetCount(2); 621 } 622 623 // Sort entries 624 VectorSet<HashedEntry> entrySet; 625 626 HTree htree(fVolume, fDirectory); 627 status = htree.PrepareForHash(); 628 if (status != B_OK) 629 return status; 630 631 uint32 displacement = firstSplit ? 2 * (sizeof(HTreeFakeDirEntry) + 4) : 0; 632 633 HashedEntry entry; 634 ext2_dir_entry* dirEntry = NULL; 635 636 while (displacement < maxSize) { 637 entry.position = &buffer[displacement]; 638 dirEntry = (ext2_dir_entry*)entry.position; 639 640 TRACE("DirectoryIterator::_SplitIndexedBlock(): pos: %p, name " 641 "length: %u, entry length: %u\n", entry.position, 642 dirEntry->name_length, 643 dirEntry->Length()); 644 645 char cbuffer[256]; 646 memcpy(cbuffer, dirEntry->name, dirEntry->name_length); 647 cbuffer[dirEntry->name_length] = '\0'; 648 entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length); 649 TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n", 650 cbuffer, entry.hash); 651 652 status = entrySet.Insert(entry); 653 if (status != B_OK) 654 return status; 655 656 displacement += dirEntry->Length(); 657 } 658 659 // Prepare the new entry to be included as well 660 ext2_dir_entry newEntry; 661 662 uint16 newLength = EXT2_DIR_REC_LEN(nameLength); 663 664 newEntry.name_length = nameLength; 665 newEntry.SetLength(newLength); 666 newEntry.SetInodeID(id); 667 newEntry.file_type = type; 668 memcpy(newEntry.name, name, nameLength); 669 670 entry.position = (uint8*)&newEntry; 671 entry.hash = htree.Hash(name, nameLength); 672 TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n", 673 name, entry.hash); 674 675 entrySet.Insert(entry); 676 677 // Move first half of entries to the first block 678 VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin(); 679 int32 median = entrySet.Count() / 2; 680 displacement = 0; 681 TRACE("DirectoryIterator::_SplitIndexedBlock(): Count: %" B_PRId32 682 ", median: %" B_PRId32 "\n", entrySet.Count(), median); 683 684 uint32 previousHash = (*iterator).hash; 685 686 for (int32 i = 0; i < median; ++i) { 687 dirEntry = (ext2_dir_entry*)(*iterator).position; 688 previousHash = (*iterator).hash; 689 690 uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length); 691 692 dirEntry->SetLength((uint16)realLength); 693 memcpy(&firstBlock[displacement], dirEntry, realLength); 694 695 displacement += realLength; 696 iterator++; 697 } 698 699 // Update last entry in the block 700 uint16 oldLength = dirEntry->Length(); 701 dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength]; 702 dirEntry->SetLength(maxSize - displacement + oldLength); 703 704 fDirectory->SetDirEntryChecksum(firstBlock); 705 706 bool collision = false; 707 708 while (iterator != entrySet.End() && (*iterator).hash == previousHash) { 709 // Keep collisions on the same block 710 TRACE("DirectoryIterator::_SplitIndexedBlock(): Handling collisions\n"); 711 712 // This isn't the ideal solution, but it is a rare occurance 713 dirEntry = (ext2_dir_entry*)(*iterator).position; 714 715 if (displacement + dirEntry->Length() > maxSize) { 716 // Doesn't fit on the block 717 collision = true; 718 break; 719 } 720 721 memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length()); 722 723 displacement += dirEntry->Length(); 724 iterator++; 725 } 726 727 // Save the hash to store in the parent 728 uint32 medianHash = (*iterator).hash; 729 730 // Update parent 731 if (firstSplit) { 732 TRACE("DirectoryIterator::_SplitIndexedBlock(): Updating root\n"); 733 HTreeRoot* root = (HTreeRoot*)secondBlock; 734 HTreeEntry* htreeEntry = (HTreeEntry*)root->count_limit; 735 htreeEntry->SetBlock(1); 736 737 ++htreeEntry; 738 htreeEntry->SetBlock(2); 739 htreeEntry->SetHash(medianHash); 740 741 742 off_t start = (off_t)root->root_info_length 743 + 2 * (sizeof(HTreeFakeDirEntry) + 4); 744 _SetHTreeEntryChecksum(secondBlock, start, 2); 745 fParent = new(std::nothrow) HTreeEntryIterator(start, fDirectory); 746 if (fParent == NULL) 747 return B_NO_MEMORY; 748 749 fLogicalBlock = 1; 750 status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, 751 fPhysicalBlock); 752 753 fPreviousDisplacement = fDisplacement = 0; 754 755 status = fParent->Init(); 756 } 757 else { 758 status = fParent->InsertEntry(transaction, medianHash, fNumBlocks - 1, 759 newBlocksPos, collision); 760 } 761 if (status != B_OK) 762 return status; 763 764 // Prepare last block to hold the second half of the entries 765 TRACE("DirectoryIterator::_SplitIndexedBlock(): Preparing second leaf " 766 "block\n"); 767 fDisplacement = 0; 768 769 status = fDirectory->FindBlock(fDirectory->Size() - 1, fPhysicalBlock); 770 if (status != B_OK) 771 return status; 772 773 CachedBlock cachedSecond(fVolume); 774 secondBlock = cachedSecond.SetToWritable(transaction, 775 fPhysicalBlock); 776 if (secondBlock == NULL) 777 return B_IO_ERROR; 778 779 // Move the second half of the entries to the second block 780 VectorSet<HashedEntry>::Iterator end = entrySet.End(); 781 displacement = 0; 782 783 while (iterator != end) { 784 dirEntry = (ext2_dir_entry*)(*iterator).position; 785 786 uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length); 787 788 dirEntry->SetLength((uint16)realLength); 789 memcpy(&secondBlock[displacement], dirEntry, realLength); 790 791 displacement += realLength; 792 iterator++; 793 } 794 795 // Update last entry in the block 796 oldLength = dirEntry->Length(); 797 dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength]; 798 dirEntry->SetLength(maxSize - displacement + oldLength); 799 800 fDirectory->SetDirEntryChecksum(secondBlock); 801 802 ASSERT(_CheckBlock(firstBlock) == B_OK); 803 ASSERT(_CheckBlock(secondBlock) == B_OK); 804 805 TRACE("DirectoryIterator::_SplitIndexedBlock(): Done\n"); 806 return B_OK; 807 } 808 809 810 status_t 811 DirectoryIterator::_NextBlock() 812 { 813 TRACE("DirectoryIterator::_NextBlock()\n"); 814 if (fIndexing) { 815 TRACE("DirectoryIterator::_NextBlock(): Indexing\n"); 816 if (!fParent->HasCollision()) { 817 TRACE("DirectoryIterator::_NextBlock(): next block doesn't " 818 "contain collisions from previous block\n"); 819 #ifndef COLLISION_TEST 820 return B_ENTRY_NOT_FOUND; 821 #endif 822 } 823 824 return fParent->GetNext(fLogicalBlock); 825 } 826 827 if (++fLogicalBlock > fNumBlocks) 828 return B_ENTRY_NOT_FOUND; 829 830 return B_OK; 831 } 832 833 834 bool 835 DirectoryIterator::_CheckDirEntry(const ext2_dir_entry* dirEntry, const uint8* buffer) 836 { 837 const char *errmsg = NULL; 838 if (dirEntry->Length() < EXT2_DIR_REC_LEN(1)) 839 errmsg = "Length is too small"; 840 else if (dirEntry->Length() % 4 != 0) 841 errmsg = "Length is not a multiple of 4"; 842 else if (dirEntry->Length() < EXT2_DIR_REC_LEN(dirEntry->NameLength())) 843 errmsg = "Length is too short for the name"; 844 else if (((uint8*)dirEntry - buffer) + dirEntry->Length() 845 > (ptrdiff_t)fBlockSize) { 846 errmsg = "Length is too big for the blocksize"; 847 } 848 849 TRACE("DirectoryIterator::_CheckDirEntry() %s\n", errmsg != NULL ? errmsg : "null"); 850 return errmsg == NULL; 851 } 852 853 854 status_t 855 DirectoryIterator::_CheckBlock(const uint8* buffer) 856 { 857 uint32 maxSize = fBlockSize; 858 if (fVolume->HasMetaGroupChecksumFeature()) 859 maxSize -= sizeof(ext2_dir_entry_tail); 860 861 status_t err = B_OK; 862 uint16 pos = 0; 863 while (pos < maxSize) { 864 const ext2_dir_entry *dirEntry = (const ext2_dir_entry*)&buffer[pos]; 865 866 if (!_CheckDirEntry(dirEntry, buffer)) { 867 TRACE("DirectoryIterator::_CheckBlock(): invalid " 868 "dirEntry pos %d\n", pos); 869 err = B_BAD_DATA; 870 } 871 872 pos += dirEntry->Length(); 873 } 874 return err; 875 } 876 877 878 ext2_htree_tail* 879 DirectoryIterator::_HTreeEntryTail(uint8* block, uint16 offset) const 880 { 881 HTreeEntry* entries = (HTreeEntry*)block; 882 uint16 firstEntry = offset % fBlockSize / sizeof(HTreeEntry); 883 HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[firstEntry]; 884 uint16 limit = countLimit->Limit(); 885 TRACE("DirectoryIterator::_HTreeEntryTail() %p %p\n", block, &entries[firstEntry + limit]); 886 return (ext2_htree_tail*)(&entries[firstEntry + limit]); 887 } 888 889 890 uint32 891 DirectoryIterator::_HTreeRootChecksum(uint8* block, uint16 offset, uint16 count) const 892 { 893 uint32 number = fDirectory->ID(); 894 uint32 checksum = calculate_crc32c(fVolume->ChecksumSeed(), 895 (uint8*)&number, sizeof(number)); 896 uint32 gen = fDirectory->Node().generation; 897 checksum = calculate_crc32c(checksum, (uint8*)&gen, sizeof(gen)); 898 checksum = calculate_crc32c(checksum, block, 899 offset + count * sizeof(HTreeEntry)); 900 TRACE("DirectoryIterator::_HTreeRootChecksum() size %" B_PRIu64 "\n", 901 offset + count * sizeof(HTreeEntry)); 902 ext2_htree_tail dummy; 903 dummy.reserved = 0; 904 checksum = calculate_crc32c(checksum, (uint8*)&dummy, sizeof(dummy)); 905 return checksum; 906 } 907 908 909 void 910 DirectoryIterator::_SetHTreeEntryChecksum(uint8* block, uint16 offset, uint16 count) 911 { 912 TRACE("DirectoryIterator::_SetHTreeEntryChecksum()\n"); 913 if (fVolume->HasMetaGroupChecksumFeature()) { 914 ext2_htree_tail* tail = _HTreeEntryTail(block, offset); 915 tail->reserved = 0x0; 916 tail->checksum = _HTreeRootChecksum(block, offset, count); 917 } 918 } 919 920 921 uint32 922 DirectoryIterator::_MaxSize() 923 { 924 uint32 maxSize = fBlockSize; 925 if (fVolume->HasMetaGroupChecksumFeature()) 926 maxSize -= sizeof(ext2_dir_entry_tail); 927 return maxSize; 928 } 929 930