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