150477Speter/* 21817Sdg * Copyright 2008, Axel D��rfler, axeld@pinc-software.de. 31817Sdg * This file may be used under the terms of the MIT License. 41541Srgrimes */ 51541Srgrimes 61541Srgrimes 7160798Sjhb#include "DirectoryIterator.h" 81541Srgrimes 9146806Srwatson#include <string.h> 10146806Srwatson 11146806Srwatson#include <AutoDeleter.h> 12146806Srwatson#include <util/VectorSet.h> 13146806Srwatson 14194390Sjhb#include "CachedBlock.h" 15203660Sed#include "CRCTable.h" 16194390Sjhb#include "HTree.h" 17194390Sjhb#include "Inode.h" 1811294Sswallace 1910905Sbde 201541Srgrimes#undef ASSERT 2110905Sbde 2210905Sbde//#define TRACE_EXT2 231541Srgrimes#ifdef TRACE_EXT2 241541Srgrimes# define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 251541Srgrimes# define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); } 261541Srgrimes#else 271541Srgrimes# define TRACE(x...) ; 2899855Salfred# define ASSERT(x) ; 29194645Sjhb#endif 30194833Sjhb 311541Srgrimes 321541Srgrimesstruct HashedEntry 3369449Salfred{ 34194383Sjhb uint8* position; 35160797Sjhb uint32 hash; 36181972Sobrien 37181972Sobrien bool operator<(const HashedEntry& other) const 38183361Sjhb { 39181972Sobrien return hash <= other.hash; 40181972Sobrien } 41181972Sobrien 42181972Sobrien bool operator>(const HashedEntry& other) const 43211838Skib { 44104747Srwatson return hash >= other.hash; 45104747Srwatson } 46123408Speter}; 47123408Speter 481541Srgrimes 491541SrgrimesDirectoryIterator::DirectoryIterator(Inode* directory, off_t start, 5011294Sswallace HTreeEntryIterator* parent) 5111294Sswallace : 5211294Sswallace fDirectory(directory), 5311294Sswallace fVolume(directory->GetVolume()), 541541Srgrimes fBlockSize(fVolume->BlockSize()), 551541Srgrimes fParent(parent), 561541Srgrimes fNumBlocks(directory->Size() == 0 ? 0 571541Srgrimes : (directory->Size() - 1) / fBlockSize + 1), 581541Srgrimes fLogicalBlock(start / fBlockSize), 591541Srgrimes fDisplacement(start % fBlockSize), 60160798Sjhb fPreviousDisplacement(fDisplacement), 61160798Sjhb fStartLogicalBlock(fLogicalBlock), 62146806Srwatson fStartDisplacement(fDisplacement) 63160798Sjhb{ 64160798Sjhb TRACE("DirectoryIterator::DirectoryIterator() %" B_PRIdINO ": num blocks: " 65146806Srwatson "%" B_PRIu32 "\n", fDirectory->ID(), fNumBlocks); 66160798Sjhb fIndexing = parent != NULL; 67146806Srwatson fInitStatus = fDirectory->FindBlock(start, fPhysicalBlock); 68160798Sjhb fStartPhysicalBlock = fPhysicalBlock; 6912216Sbde} 7012216Sbde 7112216Sbde 72160798SjhbDirectoryIterator::~DirectoryIterator() 73160798Sjhb{ 74146806Srwatson TRACE("DirectoryIterator::~DirectoryIterator(): %p, parent: %p\n", this, 75146806Srwatson fParent); 76162991Srwatson delete fParent; 77160798Sjhb TRACE("DirectoryIterator::~DirectoryIterator(): Deleted the parent\n"); 78160798Sjhb} 79146806Srwatson 80160798Sjhb 81160798Sjhbstatus_t 82160798SjhbDirectoryIterator::InitCheck() 83160798Sjhb{ 84160798Sjhb return fInitStatus; 85160798Sjhb} 86146806Srwatson 87160798Sjhb 88146806Srwatsonstatus_t 89160798SjhbDirectoryIterator::Get(char* name, size_t* _nameLength, ino_t* _id) 90146806Srwatson{ 91160798Sjhb TRACE("DirectoryIterator::Get() ID %" B_PRIdINO "\n", fDirectory->ID()); 92160798Sjhb if (_Offset() >= fDirectory->Size()) { 93146806Srwatson TRACE("DirectoryIterator::Get() out of entries\n"); 9412216Sbde return B_ENTRY_NOT_FOUND; 95160798Sjhb } 96160798Sjhb 97160798Sjhb CachedBlock cached(fVolume); 98160798Sjhb const uint8* block = cached.SetTo(fPhysicalBlock); 99160798Sjhb if (block == NULL) 100146806Srwatson return B_IO_ERROR; 101160798Sjhb 102146806Srwatson ASSERT(_CheckBlock(block) == B_OK); 103160798Sjhb 104146806Srwatson TRACE("DirectoryIterator::Get(): Displacement: %" B_PRIu32 "\n", 105160798Sjhb fDisplacement); 106146806Srwatson const ext2_dir_entry* entry = (const ext2_dir_entry*)&block[fDisplacement]; 107146806Srwatson 108146806Srwatson if (entry->Length() == 0 || entry->InodeID() == 0) 109160798Sjhb return B_BAD_DATA; 110146806Srwatson 111146806Srwatson if (entry->NameLength() != 0) { 112160798Sjhb size_t length = entry->NameLength(); 113146806Srwatson 114146806Srwatson TRACE("block %" B_PRIu32 ", displacement %" B_PRIu32 ": entry ino %" 115160798Sjhb B_PRIu32 ", length %u, name length %" B_PRIuSIZE ", type %u\n", 116146806Srwatson fLogicalBlock, fDisplacement, entry->InodeID(), entry->Length(), 117146806Srwatson length, entry->FileType()); 118227691Sed 119160798Sjhb if (*_nameLength > 0) { 120160798Sjhb if (length + 1 > *_nameLength) 121160798Sjhb return B_BUFFER_OVERFLOW; 122160798Sjhb 123160798Sjhb memcpy(name, entry->name, length); 124160798Sjhb name[length] = '\0'; 125160798Sjhb 126160798Sjhb *_nameLength = length; 127160798Sjhb } 128160798Sjhb 129160798Sjhb *_id = entry->InodeID(); 130146806Srwatson } else 131160798Sjhb *_nameLength = 0; 132146806Srwatson 133160798Sjhb return B_OK; 134146806Srwatson} 135146806Srwatson 136160798Sjhb 137160798Sjhbstatus_t 13821776SbdeDirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id) 13921776Sbde{ 14021776Sbde status_t status; 141160798Sjhb while ((status = Get(name, _nameLength, _id)) == B_BAD_DATA) { 142146806Srwatson status = Next(); 143160798Sjhb if (status != B_OK) 144160798Sjhb return status; 145160798Sjhb } 146162373Srwatson return status; 147146806Srwatson} 148160798Sjhb 149146806Srwatson 150160798Sjhbstatus_t 151160798SjhbDirectoryIterator::Next() 152160798Sjhb{ 153176215Sru TRACE("DirectoryIterator::Next() fDirectory->ID() %" B_PRIdINO "\n", 154176215Sru fDirectory->ID()); 155160798Sjhb 156146806Srwatson if (_Offset() >= fDirectory->Size()) { 157160798Sjhb TRACE("DirectoryIterator::Next() out of entries\n"); 158146806Srwatson return B_ENTRY_NOT_FOUND; 159160798Sjhb } 160160798Sjhb 161160798Sjhb TRACE("DirectoryIterator::Next(): Creating cached block\n"); 162146806Srwatson 163146806Srwatson CachedBlock cached(fVolume); 164162991Srwatson ext2_dir_entry* entry; 165146806Srwatson 166160798Sjhb TRACE("DirectoryIterator::Next(): Loading cached block\n"); 167146806Srwatson const uint8* block = cached.SetTo(fPhysicalBlock); 168160798Sjhb if (block == NULL) 169146806Srwatson return B_IO_ERROR; 170146806Srwatson 171160798Sjhb ASSERT(_CheckBlock(block) == B_OK); 172160798Sjhb 173160798Sjhb entry = (ext2_dir_entry*)(block + fDisplacement); 174146806Srwatson 175160798Sjhb do { 176146806Srwatson TRACE("Checking entry at block %" B_PRIu64 ", displacement %" B_PRIu32 177160798Sjhb " entry inodeid %" B_PRIu32 "\n", fPhysicalBlock, fDisplacement, 178160798Sjhb entry->InodeID()); 179146806Srwatson 180160798Sjhb if (entry->Length() != 0) { 181146806Srwatson if (!entry->IsValid()) { 182146806Srwatson TRACE("invalid entry.\n"); 183146806Srwatson return B_BAD_DATA; 184160798Sjhb } 185146806Srwatson fPreviousDisplacement = fDisplacement; 186160798Sjhb fDisplacement += entry->Length(); 187146806Srwatson } else 188160798Sjhb fDisplacement = fBlockSize; 189146806Srwatson 190160798Sjhb if (fDisplacement == fBlockSize) { 191160798Sjhb TRACE("Reached end of block\n"); 192160798Sjhb 193146806Srwatson fDisplacement = 0; 194160798Sjhb 195160798Sjhb status_t status = _NextBlock(); 196160798Sjhb if (status != B_OK) 197146806Srwatson return status; 198160798Sjhb 199146806Srwatson if ((off_t)(_Offset() + ext2_dir_entry::MinimumSize()) 200146806Srwatson >= fDirectory->Size()) { 201160798Sjhb TRACE("DirectoryIterator::Next() end of directory file\n"); 202146806Srwatson return B_ENTRY_NOT_FOUND; 203146806Srwatson } 204160798Sjhb status = fDirectory->FindBlock(_Offset(), fPhysicalBlock); 205160798Sjhb if (status != B_OK) 206146806Srwatson return status; 207160798Sjhb 208123750Speter block = cached.SetTo(fPhysicalBlock); 20912216Sbde if (block == NULL) 210160798Sjhb return B_IO_ERROR; 211146806Srwatson ASSERT(_CheckBlock(block) == B_OK); 212146806Srwatson 213160798Sjhb } else if (fDisplacement > fBlockSize) { 214160798Sjhb TRACE("The entry isn't block aligned.\n"); 215146806Srwatson // TODO: Is block alignment obligatory? 216160798Sjhb return B_BAD_DATA; 217146806Srwatson } 218160798Sjhb 219146806Srwatson entry = (ext2_dir_entry*)(block + fDisplacement); 220194390Sjhb 221146806Srwatson TRACE("DirectoryIterator::Next() skipping entry %d %" B_PRIu32 "\n", 222160798Sjhb entry->Length(), entry->InodeID()); 223160798Sjhb } while (entry->Length() == 0 || entry->InodeID() == 0); 224146806Srwatson 225160798Sjhb TRACE("DirectoryIterator::Next() entry->Length() %d entry->name %*s\n", 226146806Srwatson entry->Length(), entry->NameLength(), entry->name); 227160798Sjhb 228146806Srwatson return B_OK; 229160798Sjhb} 230146806Srwatson 231160798Sjhb 232146806Srwatsonstatus_t 233160798SjhbDirectoryIterator::Rewind() 234146806Srwatson{ 235160798Sjhb fDisplacement = 0; 236146806Srwatson fPreviousDisplacement = 0; 237160798Sjhb fLogicalBlock = 0; 238160798Sjhb 239160798Sjhb return fDirectory->FindBlock(0, fPhysicalBlock); 24021776Sbde} 24121776Sbde 242160798Sjhb 243146806Srwatsonvoid 244160798SjhbDirectoryIterator::Restart() 245146806Srwatson{ 246160798Sjhb TRACE("DirectoryIterator::Restart(): (logical, physical, displacement): " 247146806Srwatson "current: (%" B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 "), start: (%" 248146806Srwatson B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 ")\n", fLogicalBlock, 249160798Sjhb fPhysicalBlock, fDisplacement, fStartLogicalBlock, fStartPhysicalBlock, 250146806Srwatson fStartDisplacement); 251160798Sjhb fLogicalBlock = fStartLogicalBlock; 252146806Srwatson fPhysicalBlock = fStartPhysicalBlock; 253160798Sjhb fDisplacement = fPreviousDisplacement = fStartDisplacement; 254146806Srwatson} 255146806Srwatson 256160798Sjhb 257146806Srwatsonstatus_t 258160798SjhbDirectoryIterator::AddEntry(Transaction& transaction, const char* name, 259146806Srwatson size_t _nameLength, ino_t id, uint8 type) 260160798Sjhb{ 261146806Srwatson TRACE("DirectoryIterator::AddEntry(%s, ...)\n", name); 262160798Sjhb 263160798Sjhb uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH 264194390Sjhb : _nameLength; 265146806Srwatson 266146806Srwatson status_t status = B_OK; 267146806Srwatson while (status == B_OK) { 268160798Sjhb uint16 pos = 0; 269160798Sjhb uint16 newLength; 270160798Sjhb 271160798Sjhb status = _AllocateBestEntryInBlock(nameLength, pos, newLength); 272160798Sjhb if (status == B_OK) { 273160798Sjhb return _AddEntry(transaction, name, nameLength, id, type, newLength, 274160798Sjhb pos); 275160798Sjhb } else if (status != B_DEVICE_FULL) 276146806Srwatson return status; 277160798Sjhb 278160798Sjhb fDisplacement = 0; 279146806Srwatson status = _NextBlock(); 280160798Sjhb if (status == B_OK) 281160798Sjhb status = fDirectory->FindBlock(_Offset(), fPhysicalBlock); 282160798Sjhb } 283146806Srwatson 284146806Srwatson if (status != B_ENTRY_NOT_FOUND) 285160798Sjhb return status; 286146806Srwatson 287160798Sjhb bool firstSplit = fNumBlocks == 1 && fVolume->IndexedDirectories(); 288146806Srwatson 289160798Sjhb fNumBlocks++; 290160798Sjhb 291160798Sjhb if (fIndexing) { 292146806Srwatson TRACE("DirectoryIterator::AddEntry(): Adding another HTree leaf\n"); 293160798Sjhb fNumBlocks += fParent->BlocksNeededForNewEntry(); 294146806Srwatson } else if (firstSplit) { 295160798Sjhb // Allocate another block (fNumBlocks should become 3) 296160798Sjhb TRACE("DirectoryIterator::AddEntry(): Creating index for directory\n"); 297160798Sjhb fNumBlocks++; 298146806Srwatson } else 299160798Sjhb TRACE("DirectoryIterator::AddEntry(): Enlarging directory\n"); 300194390Sjhb 301146806Srwatson status = fDirectory->Resize(transaction, fNumBlocks * fBlockSize); 302146806Srwatson if (status != B_OK) 3031541Srgrimes return status; 3041541Srgrimes 3051541Srgrimes if (firstSplit || fIndexing) { 3061541Srgrimes // firstSplit and fIndexing are mutually exclusive 3071541Srgrimes return _SplitIndexedBlock(transaction, name, nameLength, id, type, 308146806Srwatson fNumBlocks - 1, firstSplit); 309146806Srwatson } 310146806Srwatson 311177633Sdfr fLogicalBlock = fNumBlocks - 1; 312177633Sdfr status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock); 31330740Sphk if (status != B_OK) 314161325Sjhb return status; 315160798Sjhb 316146806Srwatson return _AddEntry(transaction, name, nameLength, id, type, fBlockSize, 0, 317160798Sjhb false); 318146806Srwatson} 319160798Sjhb 320146806Srwatson 321146806Srwatsonstatus_t 322160798SjhbDirectoryIterator::FindEntry(const char* name, ino_t* _id) 323146806Srwatson{ 324160798Sjhb TRACE("DirectoryIterator::FindEntry(): %p %p\n", this, name); 325146806Srwatson char buffer[EXT2_NAME_LENGTH + 1]; 326184789Sed ino_t id; 327146806Srwatson 328184789Sed status_t status = B_OK; 329146806Srwatson size_t length = strlen(name); 330184789Sed while (status == B_OK) { 331161952Srwatson size_t nameLength = EXT2_NAME_LENGTH; 332161952Srwatson status = Get(buffer, &nameLength, &id); 333146806Srwatson if (status == B_OK) { 334146806Srwatson if (length == nameLength 335146806Srwatson && strncmp(name, buffer, nameLength) == 0) { 336160798Sjhb if (_id != NULL) 337146806Srwatson *_id = id; 338123750Speter return B_OK; 339160798Sjhb } 340146806Srwatson } else if (status != B_BAD_DATA) 341123750Speter break; 342160798Sjhb status = Next(); 343146806Srwatson } 344123750Speter 345146806Srwatson return status; 346171209Speter} 347146806Srwatson 348171209Speter 349171209Speterstatus_t 350146806SrwatsonDirectoryIterator::RemoveEntry(Transaction& transaction) 351178888Sjulian{ 352161946Srwatson TRACE("DirectoryIterator::RemoveEntry()\n"); 353146806Srwatson ext2_dir_entry* previousEntry; 354146806Srwatson ext2_dir_entry* dirEntry; 355146806Srwatson CachedBlock cached(fVolume); 356146806Srwatson 3571541Srgrimes uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 35849428Sjkh uint32 maxSize = _MaxSize(); 359160798Sjhb 360160798Sjhb if (fDisplacement == 0) { 361160798Sjhb previousEntry = (ext2_dir_entry*)&block[fDisplacement]; 362146806Srwatson 363146806Srwatson fPreviousDisplacement = fDisplacement; 364146806Srwatson fDisplacement += previousEntry->Length(); 365146806Srwatson 366160798Sjhb if (fDisplacement == maxSize) { 367160798Sjhb previousEntry->SetInodeID(0); 368160798Sjhb fDisplacement = 0; 369160798Sjhb return B_OK; 370160798Sjhb } else if (fDisplacement > maxSize) { 371146806Srwatson TRACE("DirectoryIterator::RemoveEntry(): Entry isn't aligned to " 372160798Sjhb "block entry."); 373146806Srwatson return B_BAD_DATA; 374146806Srwatson } 375160798Sjhb 376146806Srwatson dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 377146806Srwatson memcpy(&block[fPreviousDisplacement], &block[fDisplacement], 378160798Sjhb dirEntry->Length()); 379146806Srwatson 380171209Speter previousEntry->SetLength(fDisplacement - fPreviousDisplacement 381171209Speter + previousEntry->Length()); 382171209Speter 383183361Sjhb fDirectory->SetDirEntryChecksum(block); 384146806Srwatson 385171209Speter ASSERT(_CheckBlock(block) == B_OK); 386171209Speter 387171209Speter return B_OK; 388146806Srwatson } 389171209Speter 390146806Srwatson TRACE("DirectoryIterator::RemoveEntry() fDisplacement %" B_PRIu32 "\n", 391160798Sjhb fDisplacement); 392146806Srwatson 393146806Srwatson if (fPreviousDisplacement == fDisplacement) { 394160798Sjhb char buffer[EXT2_NAME_LENGTH + 1]; 395160798Sjhb 396160798Sjhb dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 397160798Sjhb 398160798Sjhb memcpy(buffer, dirEntry->name, (uint32)dirEntry->name_length); 399146806Srwatson 400160798Sjhb fDisplacement = 0; 401146806Srwatson status_t status = FindEntry(dirEntry->name); 4022124Sdg if (status == B_ENTRY_NOT_FOUND) 4032124Sdg return B_BAD_DATA; 4042124Sdg if (status != B_OK) 4052124Sdg return status; 406209579Skib } 407209579Skib 408209579Skib previousEntry = (ext2_dir_entry*)&block[fPreviousDisplacement]; 409209579Skib dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 410209579Skib 411209579Skib previousEntry->SetLength(previousEntry->Length() + dirEntry->Length()); 412209579Skib 413209579Skib memset(&block[fDisplacement], 0, 414209579Skib fPreviousDisplacement + previousEntry->Length() - fDisplacement); 415209579Skib 41612864Speter fDirectory->SetDirEntryChecksum(block); 41712864Speter 41814215Speter ASSERT(_CheckBlock(block) == B_OK); 419194910Sjhb 420194910Sjhb return B_OK; 421160798Sjhb} 422146806Srwatson 423160798Sjhb 424146806Srwatsonstatus_t 425146806SrwatsonDirectoryIterator::ChangeEntry(Transaction& transaction, ino_t id, 426194910Sjhb uint8 fileType) 427194910Sjhb{ 428160798Sjhb CachedBlock cached(fVolume); 429160798Sjhb 430146806Srwatson uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 431160798Sjhb if (block == NULL) 432146806Srwatson return B_IO_ERROR; 433160798Sjhb 434146806Srwatson ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 435194910Sjhb dirEntry->SetInodeID(id); 436194910Sjhb dirEntry->file_type = fileType; 437160798Sjhb 438160798Sjhb fDirectory->SetDirEntryChecksum(block); 439146806Srwatson 44014219Speter ASSERT(_CheckBlock(block) == B_OK); 441160798Sjhb 442146806Srwatson return B_OK; 443161952Srwatson} 444161952Srwatson 445146806Srwatson 446160798Sjhbstatus_t 447146806SrwatsonDirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos, 448160798Sjhb uint16& newLength) 449156134Sdavidxu{ 450160798Sjhb TRACE("DirectoryIterator::_AllocateBestEntryInBlock()\n"); 451160798Sjhb CachedBlock cached(fVolume); 452151576Sdavidxu const uint8* block = cached.SetTo(fPhysicalBlock); 453151576Sdavidxu 454160798Sjhb ASSERT(_CheckBlock(block) == B_OK); 455151576Sdavidxu 456160798Sjhb uint16 requiredLength = EXT2_DIR_REC_LEN(nameLength); 457160798Sjhb uint32 maxSize = _MaxSize(); 458146806Srwatson 459227776Slstewart uint16 bestPos = maxSize; 460227776Slstewart uint16 bestLength = maxSize; 461227776Slstewart uint16 bestRealLength = maxSize; 462227776Slstewart ext2_dir_entry* dirEntry; 463227776Slstewart 464146806Srwatson while (pos < maxSize) { 465146806Srwatson dirEntry = (ext2_dir_entry*)&block[pos]; 466146806Srwatson if (!_CheckDirEntry(dirEntry, block)) { 467146806Srwatson TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): invalid " 468160798Sjhb "dirEntry->Length() pos %d\n", pos); 469146806Srwatson return B_BAD_DATA; 47014219Speter } 471160798Sjhb 472146806Srwatson uint16 realLength = EXT2_DIR_REC_LEN(dirEntry->NameLength()); 473160798Sjhb uint16 emptySpace = dirEntry->Length(); 474160798Sjhb if (dirEntry->InodeID() != 0) 475146806Srwatson emptySpace -= realLength; 476160798Sjhb if (emptySpace == requiredLength) { 477160798Sjhb // Found an exact match 478160798Sjhb TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found an " 479160798Sjhb "exact length match\n"); 480160798Sjhb newLength = realLength; 481151867Sdavidxu 482151867Sdavidxu return B_OK; 483152845Sdavidxu } else if (emptySpace > requiredLength && emptySpace < bestLength) { 484152845Sdavidxu bestPos = pos; 485152845Sdavidxu bestLength = emptySpace; 486152845Sdavidxu bestRealLength = realLength; 487152845Sdavidxu } 488152845Sdavidxu 489146806Srwatson pos += dirEntry->Length(); 490146806Srwatson } 491146806Srwatson 492146806Srwatson if (bestPos == maxSize) 493146806Srwatson return B_DEVICE_FULL; 494146806Srwatson 495146806Srwatson TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found a suitable " 496146806Srwatson "location: %u\n", bestPos); 497160798Sjhb pos = bestPos; 498146806Srwatson newLength = bestRealLength; 499146806Srwatson 500160798Sjhb return B_OK; 501160798Sjhb} 502146806Srwatson 503146806Srwatson 504160798Sjhbstatus_t 505146806SrwatsonDirectoryIterator::_AddEntry(Transaction& transaction, const char* name, 506160798Sjhb uint8 nameLength, ino_t id, uint8 type, uint16 newLength, uint16 pos, 507146806Srwatson bool hasPrevious) 508160798Sjhb{ 509160798Sjhb TRACE("DirectoryIterator::_AddEntry(%s, %d, %" B_PRIdINO ", %d, %d, %d, " 510160798Sjhb "%c)\n", name, nameLength, id, type, newLength, pos, 511146806Srwatson hasPrevious ? 't' : 'f'); 512146806Srwatson CachedBlock cached(fVolume); 513146806Srwatson 514146806Srwatson uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 515146806Srwatson if (block == NULL) 516146806Srwatson return B_IO_ERROR; 517146806Srwatson 518146806Srwatson ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos]; 519147813Sjhb 520161952Srwatson if (hasPrevious) { 521147813Sjhb uint16 previousLength = dirEntry->Length(); 522161952Srwatson dirEntry->SetLength(newLength); 523147813Sjhb 524146806Srwatson dirEntry = (ext2_dir_entry*)&block[pos + newLength]; 525146806Srwatson newLength = previousLength - newLength; 526146806Srwatson } 527146806Srwatson 528146806Srwatson dirEntry->SetLength(newLength); 529146806Srwatson dirEntry->name_length = nameLength; 53051138Salfred dirEntry->SetInodeID(id); 531160798Sjhb dirEntry->file_type = type; 532146806Srwatson memcpy(dirEntry->name, name, nameLength); 533146806Srwatson 534160798Sjhb fDirectory->SetDirEntryChecksum(block); 535146806Srwatson 536160798Sjhb ASSERT(_CheckBlock(block) == B_OK); 537146806Srwatson 53825537Sdfr TRACE("DirectoryIterator::_AddEntry(): Done\n"); 539160798Sjhb 540160798Sjhb return B_OK; 541146806Srwatson} 542160798Sjhb 543160798Sjhb 544160798Sjhbstatus_t 545160798SjhbDirectoryIterator::_SplitIndexedBlock(Transaction& transaction, 546160798Sjhb const char* name, uint8 nameLength, ino_t id, uint8 type, 547160798Sjhb uint32 newBlocksPos, bool firstSplit) 548160798Sjhb{ 549146806Srwatson // Block is full, split required 550160798Sjhb TRACE("DirectoryIterator::_SplitIndexedBlock(.., %s, %u, %" B_PRIdINO ", %" 551160798Sjhb B_PRIu32 ", %c)\n", name, nameLength, id, newBlocksPos, 552160798Sjhb firstSplit ? 't' : 'f'); 553146806Srwatson 554160798Sjhb // Allocate a buffer for the entries in the block 555146806Srwatson uint8* buffer = new(std::nothrow) uint8[fBlockSize]; 556146806Srwatson if (buffer == NULL) 557160798Sjhb return B_NO_MEMORY; 558160798Sjhb ArrayDeleter<uint8> bufferDeleter(buffer); 559146806Srwatson 560146806Srwatson fsblock_t firstPhysicalBlock = 0; 561160798Sjhb uint32 maxSize = _MaxSize(); 562146806Srwatson 563160798Sjhb // Prepare block to hold the first half of the entries and fill the buffer 564160798Sjhb CachedBlock cachedFirst(fVolume); 565160798Sjhb 566160798Sjhb if (firstSplit) { 567151867Sdavidxu // Save all entries to the buffer 568151867Sdavidxu status_t status = fDirectory->FindBlock(0, firstPhysicalBlock); 569160798Sjhb if (status != B_OK) 570146806Srwatson return status; 571146806Srwatson 572160798Sjhb const uint8* srcBlock = cachedFirst.SetTo(firstPhysicalBlock); 573160798Sjhb if (srcBlock == NULL) 574161952Srwatson return B_IO_ERROR; 57534925Sdufault 576160798Sjhb memcpy(buffer, srcBlock, fBlockSize); 577146806Srwatson 578160798Sjhb status = fDirectory->FindBlock(fBlockSize, fPhysicalBlock); 579146806Srwatson if (status != B_OK) 58034925Sdufault return status; 581160798Sjhb } 582146806Srwatson 583146806Srwatson uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock); 584160798Sjhb uint8* secondBlock = NULL; 58534925Sdufault if (firstBlock == NULL) 586160798Sjhb return B_IO_ERROR; 587160798Sjhb 588160798Sjhb status_t status; 589160798Sjhb 590146806Srwatson if (!firstSplit) { 591160798Sjhb // Save all entries to the buffer 592160798Sjhb memcpy(buffer, firstBlock, fBlockSize); 593146806Srwatson } else { 594146806Srwatson // Initialize the root node 595146806Srwatson fDirectory->Node().SetFlag(EXT2_INODE_INDEXED); 596160798Sjhb HTreeRoot* root; 597146806Srwatson 598160798Sjhb secondBlock = cachedFirst.SetToWritable(transaction, 599211998Skib firstPhysicalBlock, true); 600211998Skib if (secondBlock == NULL) 601211998Skib return B_IO_ERROR; 602160798Sjhb 603146806Srwatson status = fDirectory->WriteBack(transaction); 604160798Sjhb if (status != B_OK) 605160798Sjhb return status; 606146806Srwatson 607146806Srwatson memcpy(secondBlock, buffer, 2 * (sizeof(HTreeFakeDirEntry) + 4)); 608160798Sjhb 609160798Sjhb root = (HTreeRoot*)secondBlock; 610146806Srwatson 611160798Sjhb HTreeFakeDirEntry* dotdot = &root->dotdot; 612146806Srwatson dotdot->SetEntryLength(maxSize - (sizeof(HTreeFakeDirEntry) + 4)); 613146806Srwatson 614160798Sjhb root->hash_version = fVolume->DefaultHashVersion(); 615146806Srwatson root->root_info_length = 8; 616160798Sjhb root->indirection_levels = 0; 617146806Srwatson 618160798Sjhb root->count_limit->SetLimit((maxSize 619146806Srwatson - ((uint8*)root->count_limit - secondBlock)) / sizeof(HTreeEntry)); 620160798Sjhb root->count_limit->SetCount(2); 621146806Srwatson } 622160798Sjhb 623146806Srwatson // Sort entries 624160798Sjhb VectorSet<HashedEntry> entrySet; 625146806Srwatson 626160798Sjhb HTree htree(fVolume, fDirectory); 627146806Srwatson status = htree.PrepareForHash(); 628160798Sjhb if (status != B_OK) 629146806Srwatson return status; 630160798Sjhb 631146806Srwatson uint32 displacement = firstSplit ? 2 * (sizeof(HTreeFakeDirEntry) + 4) : 0; 632160798Sjhb 633146806Srwatson HashedEntry entry; 634146806Srwatson ext2_dir_entry* dirEntry = NULL; 635160798Sjhb 636160111Swsalamon while (displacement < maxSize) { 637160111Swsalamon entry.position = &buffer[displacement]; 638160111Swsalamon dirEntry = (ext2_dir_entry*)entry.position; 639160798Sjhb 640160111Swsalamon TRACE("DirectoryIterator::_SplitIndexedBlock(): pos: %p, name " 641160111Swsalamon "length: %u, entry length: %u\n", entry.position, 642160111Swsalamon dirEntry->name_length, 643160798Sjhb dirEntry->Length()); 644146806Srwatson 645146806Srwatson char cbuffer[256]; 646160798Sjhb memcpy(cbuffer, dirEntry->name, dirEntry->name_length); 647146806Srwatson cbuffer[dirEntry->name_length] = '\0'; 648146806Srwatson entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length); 649160798Sjhb TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n", 650146806Srwatson cbuffer, entry.hash); 651160798Sjhb 652146806Srwatson status = entrySet.Insert(entry); 653161952Srwatson if (status != B_OK) 654160798Sjhb return status; 655146806Srwatson 656146806Srwatson displacement += dirEntry->Length(); 657146806Srwatson } 658146806Srwatson 659146806Srwatson // Prepare the new entry to be included as well 660146806Srwatson ext2_dir_entry newEntry; 661146806Srwatson 662146806Srwatson uint16 newLength = EXT2_DIR_REC_LEN(nameLength); 663146806Srwatson 664183361Sjhb newEntry.name_length = nameLength; 665160798Sjhb newEntry.SetLength(newLength); 666146806Srwatson newEntry.SetInodeID(id); 667146806Srwatson newEntry.file_type = type; 668160798Sjhb memcpy(newEntry.name, name, nameLength); 669146806Srwatson 670146806Srwatson entry.position = (uint8*)&newEntry; 671160798Sjhb entry.hash = htree.Hash(name, nameLength); 672146806Srwatson TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n", 673146806Srwatson name, entry.hash); 674160798Sjhb 675194383Sjhb entrySet.Insert(entry); 676227691Sed 677211998Skib // Move first half of entries to the first block 678211998Skib VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin(); 679211998Skib int32 median = entrySet.Count() / 2; 680160798Sjhb displacement = 0; 681146806Srwatson TRACE("DirectoryIterator::_SplitIndexedBlock(): Count: %" B_PRId32 682177091Sjeff ", median: %" B_PRId32 "\n", entrySet.Count(), median); 683177091Sjeff 684177091Sjeff uint32 previousHash = (*iterator).hash; 685177091Sjeff 686177091Sjeff for (int32 i = 0; i < median; ++i) { 687160798Sjhb dirEntry = (ext2_dir_entry*)(*iterator).position; 688160798Sjhb previousHash = (*iterator).hash; 689160798Sjhb 690146806Srwatson uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length); 691160798Sjhb 692146806Srwatson dirEntry->SetLength((uint16)realLength); 693160798Sjhb memcpy(&firstBlock[displacement], dirEntry, realLength); 694146806Srwatson 695160798Sjhb displacement += realLength; 696146806Srwatson iterator++; 697160798Sjhb } 698146806Srwatson 699160798Sjhb // Update last entry in the block 700160798Sjhb uint16 oldLength = dirEntry->Length(); 701146806Srwatson dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength]; 702160798Sjhb dirEntry->SetLength(maxSize - displacement + oldLength); 703146806Srwatson 704146806Srwatson fDirectory->SetDirEntryChecksum(firstBlock); 705160798Sjhb 706146806Srwatson bool collision = false; 707160798Sjhb 708146806Srwatson while (iterator != entrySet.End() && (*iterator).hash == previousHash) { 709160798Sjhb // Keep collisions on the same block 710146806Srwatson TRACE("DirectoryIterator::_SplitIndexedBlock(): Handling collisions\n"); 711160798Sjhb 712161952Srwatson // This isn't the ideal solution, but it is a rare occurance 713146806Srwatson dirEntry = (ext2_dir_entry*)(*iterator).position; 714146806Srwatson 715160798Sjhb if (displacement + dirEntry->Length() > maxSize) { 716160798Sjhb // Doesn't fit on the block 717160798Sjhb collision = true; 718160798Sjhb break; 719160798Sjhb } 720146806Srwatson 721160798Sjhb memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length()); 722146806Srwatson 723146806Srwatson displacement += dirEntry->Length(); 724160798Sjhb iterator++; 725160798Sjhb } 726160798Sjhb 727160798Sjhb // Save the hash to store in the parent 728146806Srwatson uint32 medianHash = (*iterator).hash; 729160798Sjhb 730146806Srwatson // Update parent 731160798Sjhb if (firstSplit) { 732146806Srwatson TRACE("DirectoryIterator::_SplitIndexedBlock(): Updating root\n"); 733160798Sjhb HTreeRoot* root = (HTreeRoot*)secondBlock; 734160111Swsalamon HTreeEntry* htreeEntry = (HTreeEntry*)root->count_limit; 735160111Swsalamon htreeEntry->SetBlock(1); 736160111Swsalamon 737160798Sjhb ++htreeEntry; 738160111Swsalamon htreeEntry->SetBlock(2); 739160111Swsalamon htreeEntry->SetHash(medianHash); 740160111Swsalamon 741160798Sjhb 742160111Swsalamon off_t start = (off_t)root->root_info_length 743146806Srwatson + 2 * (sizeof(HTreeFakeDirEntry) + 4); 744160798Sjhb _SetHTreeEntryChecksum(secondBlock, start, 2); 745146806Srwatson fParent = new(std::nothrow) HTreeEntryIterator(start, fDirectory); 746160798Sjhb if (fParent == NULL) 747146806Srwatson return B_NO_MEMORY; 748146806Srwatson 749160798Sjhb fLogicalBlock = 1; 750146806Srwatson status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, 751146806Srwatson fPhysicalBlock); 752146806Srwatson 753146806Srwatson fPreviousDisplacement = fDisplacement = 0; 754160798Sjhb 755160798Sjhb status = fParent->Init(); 756146806Srwatson } 757160798Sjhb else { 758146806Srwatson status = fParent->InsertEntry(transaction, medianHash, fNumBlocks - 1, 759160798Sjhb newBlocksPos, collision); 760160798Sjhb } 761146806Srwatson if (status != B_OK) 762160798Sjhb return status; 763146806Srwatson 764160798Sjhb // Prepare last block to hold the second half of the entries 765146806Srwatson TRACE("DirectoryIterator::_SplitIndexedBlock(): Preparing second leaf " 766160798Sjhb "block\n"); 767146806Srwatson fDisplacement = 0; 768160798Sjhb 769146806Srwatson status = fDirectory->FindBlock(fDirectory->Size() - 1, fPhysicalBlock); 770160798Sjhb if (status != B_OK) 771146806Srwatson return status; 772160798Sjhb 773160798Sjhb CachedBlock cachedSecond(fVolume); 774160798Sjhb secondBlock = cachedSecond.SetToWritable(transaction, 775160798Sjhb fPhysicalBlock); 776160798Sjhb if (secondBlock == NULL) 777160798Sjhb return B_IO_ERROR; 778160798Sjhb 779146806Srwatson // Move the second half of the entries to the second block 780146806Srwatson VectorSet<HashedEntry>::Iterator end = entrySet.End(); 781160798Sjhb displacement = 0; 782146806Srwatson 783146806Srwatson while (iterator != end) { 784160798Sjhb dirEntry = (ext2_dir_entry*)(*iterator).position; 785146806Srwatson 786146806Srwatson uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length); 787177091Sjeff 788160798Sjhb dirEntry->SetLength((uint16)realLength); 789151445Sstefanf memcpy(&secondBlock[displacement], dirEntry, realLength); 790160798Sjhb 791146806Srwatson displacement += realLength; 792160798Sjhb iterator++; 793161952Srwatson } 794160798Sjhb 795146806Srwatson // Update last entry in the block 796160798Sjhb oldLength = dirEntry->Length(); 797146806Srwatson dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength]; 798160798Sjhb dirEntry->SetLength(maxSize - displacement + oldLength); 799160798Sjhb 800160798Sjhb fDirectory->SetDirEntryChecksum(secondBlock); 801160798Sjhb 802160798Sjhb ASSERT(_CheckBlock(firstBlock) == B_OK); 803146806Srwatson ASSERT(_CheckBlock(secondBlock) == B_OK); 804146806Srwatson 805160798Sjhb TRACE("DirectoryIterator::_SplitIndexedBlock(): Done\n"); 806146806Srwatson return B_OK; 807146806Srwatson} 808160798Sjhb 809161678Sdavidxu 810163449Sdavidxustatus_t 811160798SjhbDirectoryIterator::_NextBlock() 812146806Srwatson{ 813160798Sjhb TRACE("DirectoryIterator::_NextBlock()\n"); 814160798Sjhb if (fIndexing) { 815152845Sdavidxu TRACE("DirectoryIterator::_NextBlock(): Indexing\n"); 816160798Sjhb if (!fParent->HasCollision()) { 817152845Sdavidxu TRACE("DirectoryIterator::_NextBlock(): next block doesn't " 818152845Sdavidxu "contain collisions from previous block\n"); 819160798Sjhb#ifndef COLLISION_TEST 820152845Sdavidxu return B_ENTRY_NOT_FOUND; 821152845Sdavidxu#endif 822152845Sdavidxu } 823160798Sjhb 824152845Sdavidxu return fParent->GetNext(fLogicalBlock); 825152845Sdavidxu } 826152845Sdavidxu 827160798Sjhb if (++fLogicalBlock > fNumBlocks) 828152845Sdavidxu return B_ENTRY_NOT_FOUND; 829160798Sjhb 830160798Sjhb return B_OK; 831160798Sjhb} 832160798Sjhb 833162497Sdavidxu 834162497Sdavidxubool 835162497SdavidxuDirectoryIterator::_CheckDirEntry(const ext2_dir_entry* dirEntry, const uint8* buffer) 836162497Sdavidxu{ 837161367Speter const char *errmsg = NULL; 838161367Speter if (dirEntry->Length() < EXT2_DIR_REC_LEN(1)) 839163953Srrs errmsg = "Length is too small"; 840163953Srrs else if (dirEntry->Length() % 4 != 0) 841163953Srrs errmsg = "Length is not a multiple of 4"; 842163953Srrs else if (dirEntry->Length() < EXT2_DIR_REC_LEN(dirEntry->NameLength())) 843163953Srrs errmsg = "Length is too short for the name"; 844163953Srrs else if (((uint8*)dirEntry - buffer) + dirEntry->Length() 845163953Srrs > (ptrdiff_t)fBlockSize) { 846163953Srrs errmsg = "Length is too big for the blocksize"; 847163953Srrs } 848163953Srrs 849171209Speter TRACE("DirectoryIterator::_CheckDirEntry() %s\n", errmsg != NULL ? errmsg : "null"); 850171209Speter return errmsg == NULL; 851171209Speter} 852171209Speter 853171209Speter 854171209Speterstatus_t 855171209SpeterDirectoryIterator::_CheckBlock(const uint8* buffer) 856171209Speter{ 857171209Speter uint32 maxSize = fBlockSize; 858171209Speter if (fVolume->HasMetaGroupChecksumFeature()) 859171859Sdavidxu maxSize -= sizeof(ext2_dir_entry_tail); 860175517Srwatson 861175164Sjhb status_t err = B_OK; 862175517Srwatson uint16 pos = 0; 863176730Sjeff while (pos < maxSize) { 864176730Sjeff const ext2_dir_entry *dirEntry = (const ext2_dir_entry*)&buffer[pos]; 865176730Sjeff 866176730Sjeff if (!_CheckDirEntry(dirEntry, buffer)) { 867176730Sjeff TRACE("DirectoryIterator::_CheckBlock(): invalid " 868176730Sjeff "dirEntry pos %d\n", pos); 869176730Sjeff err = B_BAD_DATA; 870177597Sru } 871177597Sru 872176730Sjeff pos += dirEntry->Length(); 873177597Sru } 874177597Sru return err; 875227691Sed} 876177788Skib 877177788Skib 878177788Skibext2_htree_tail* 879177788SkibDirectoryIterator::_HTreeEntryTail(uint8* block, uint16 offset) const 880177788Skib{ 881177788Skib HTreeEntry* entries = (HTreeEntry*)block; 882177788Skib uint16 firstEntry = offset % fBlockSize / sizeof(HTreeEntry); 883177788Skib HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[firstEntry]; 884177788Skib uint16 limit = countLimit->Limit(); 885177788Skib TRACE("DirectoryIterator::_HTreeEntryTail() %p %p\n", block, &entries[firstEntry + limit]); 886177788Skib return (ext2_htree_tail*)(&entries[firstEntry + limit]); 887177788Skib} 888177788Skib 889177788Skib 890177788Skibuint32 891177788SkibDirectoryIterator::_HTreeRootChecksum(uint8* block, uint16 offset, uint16 count) const 892177788Skib{ 893177788Skib uint32 number = fDirectory->ID(); 894177788Skib uint32 checksum = calculate_crc32c(fVolume->ChecksumSeed(), 895177788Skib (uint8*)&number, sizeof(number)); 896177788Skib uint32 gen = fDirectory->Node().generation; 897177788Skib checksum = calculate_crc32c(checksum, (uint8*)&gen, sizeof(gen)); 898177788Skib checksum = calculate_crc32c(checksum, block, 899177788Skib offset + count * sizeof(HTreeEntry)); 900177788Skib TRACE("DirectoryIterator::_HTreeRootChecksum() size %" B_PRIu64 "\n", 901177788Skib offset + count * sizeof(HTreeEntry)); 902177788Skib ext2_htree_tail dummy; 903182123Srwatson dummy.reserved = 0; 904184588Sdfr checksum = calculate_crc32c(checksum, (uint8*)&dummy, sizeof(dummy)); 905184588Sdfr return checksum; 906191673Sjamie} 907191673Sjamie 908191673Sjamie 909191673Sjamievoid 910191673SjamieDirectoryIterator::_SetHTreeEntryChecksum(uint8* block, uint16 offset, uint16 count) 911194262Sjhb{ 912194910Sjhb TRACE("DirectoryIterator::_SetHTreeEntryChecksum()\n"); 913194910Sjhb if (fVolume->HasMetaGroupChecksumFeature()) { 914194910Sjhb ext2_htree_tail* tail = _HTreeEntryTail(block, offset); 915194910Sjhb tail->reserved = 0x0; 916194910Sjhb tail->checksum = _HTreeRootChecksum(block, offset, count); 917194910Sjhb } 918195458Strasz} 919224066Sjonathan 920224066Sjonathan 921224066Sjonathanuint32 922219129SrwatsonDirectoryIterator::_MaxSize() 923219129Srwatson{ 924224987Sjonathan uint32 maxSize = fBlockSize; 925224987Sjonathan if (fVolume->HasMetaGroupChecksumFeature()) 926224987Sjonathan maxSize -= sizeof(ext2_dir_entry_tail); 927224987Sjonathan return maxSize; 928198508Skib} 929198508Skib 930198508Skib