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