1// Volume.cpp 2// 3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4// 5// This program is free software; you can redistribute it and/or modify 6// it under the terms of the GNU General Public License as published by 7// the Free Software Foundation; either version 2 of the License, or 8// (at your option) any later version. 9// 10// This program is distributed in the hope that it will be useful, 11// but WITHOUT ANY WARRANTY; without even the implied warranty of 12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13// GNU General Public License for more details. 14// 15// You should have received a copy of the GNU General Public License 16// along with this program; if not, write to the Free Software 17// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18// 19// You can alternatively use *this file* under the terms of the the MIT 20// license included in this package. 21 22#include <errno.h> 23#include <fcntl.h> 24#include <stdio.h> 25#include <stdlib.h> 26#include <string.h> 27#include <unistd.h> 28 29#include "Volume.h" 30#include "Block.h" 31#include "BlockCache.h" 32#include "Debug.h" 33#include "DirItem.h" 34#include "IndirectItem.h" 35#include "Iterators.h" 36#include "reiserfs.h" 37#include "Settings.h" 38#include "StatItem.h" 39#include "SuperBlock.h" 40#include "Tree.h" 41#include "VNode.h" 42 43// min and max 44// We don't want to include <algobase.h> otherwise we also get <iostream.h> 45// and other undesired things. 46template<typename C> 47static inline C min(const C &a, const C &b) { return (a < b ? a : b); } 48template<typename C> 49static inline C max(const C &a, const C &b) { return (a > b ? a : b); } 50 51/*! 52 \class Volume 53 \brief Represents a volume. 54 55 The Volume class bundles all functionality related to a volume. 56 It knows the superblock and has some basic functionality needed 57 for handling VNodes. Actually it should be the layer that provides the 58 abstraction from VNodes. The design is not strict in this respect 59 (the whole thing evolved while I was in the process of understanding 60 the structures ;-), since the kernel interface does a good part of that 61 too (e.g. concerning dir iteration). 62*/ 63 64// constructor 65Volume::Volume() 66 : fID(0), 67 fDevice(-1), 68 fBlockCache(NULL), 69 fTree(NULL), 70 fSuperBlock(NULL), 71 fHashFunction(NULL), 72 fRootVNode(NULL), 73 fDeviceName(NULL), 74 fSettings(NULL), 75 fNegativeEntries() 76{ 77} 78 79// destructor 80Volume::~Volume() 81{ 82 Unmount(); 83} 84 85// Mount 86status_t 87Volume::Mount(nspace_id id, const char *path) 88{ 89 Unmount(); 90 status_t error = (path ? B_OK : B_BAD_VALUE); 91 fID = id; 92 // load the settings 93 if (error == B_OK) { 94 fSettings = new(nothrow) Settings; 95 if (fSettings) 96 error = fSettings->SetTo(path); 97 else 98 error = B_NO_MEMORY; 99 } 100 // copy the device name 101 if (error == B_OK) { 102 fDeviceName = new(nothrow) char[strlen(path) + 1]; 103 if (fDeviceName) 104 strcpy(fDeviceName, path); 105 else 106 error = B_NO_MEMORY; 107 } 108 // open disk 109 if (error == B_OK) { 110 fDevice = open(path, O_RDONLY); 111 if (fDevice < 0) 112 SET_ERROR(error, errno); 113 } 114 // read and analyze superblock 115 if (error == B_OK) 116 error = _ReadSuperBlock(); 117 // create and init block cache 118 if (error == B_OK) { 119 fBlockCache = new(nothrow) BlockCache; 120 if (fBlockCache) { 121 error = fBlockCache->Init(fDevice, CountBlocks(), GetBlockSize(), 122 fSettings->GetCacheDisabled(), 123 fSettings->GetCacheSize()); 124 } else 125 error = B_NO_MEMORY; 126 } 127 // create the tree 128 if (error == B_OK) { 129 fTree = new(nothrow) Tree; 130 if (!fTree) 131 error = B_NO_MEMORY; 132 } 133 // get the root node and init the tree 134 if (error == B_OK) { 135 Block *rootBlock = NULL; 136 error = fBlockCache->GetBlock(fSuperBlock->GetRootBlock(), &rootBlock); 137REPORT_ERROR(error); 138 if (error == B_OK) { 139 rootBlock->SetKind(Block::KIND_FORMATTED); 140 error = fTree->Init(this, rootBlock->ToNode(), 141 fSuperBlock->GetTreeHeight()); 142REPORT_ERROR(error); 143 rootBlock->Put(); 144 } 145 } 146 // get the root VNode (i.e. the root dir) 147 if (error == B_OK) { 148 fRootVNode = new(nothrow) VNode; 149 if (fRootVNode) { 150 error = FindVNode(REISERFS_ROOT_PARENT_OBJECTID, 151 REISERFS_ROOT_OBJECTID, fRootVNode); 152REPORT_ERROR(error); 153 if (error == B_OK) 154 error = new_vnode(fID, fRootVNode->GetID(), fRootVNode); 155REPORT_ERROR(error); 156 } else 157 error = B_NO_MEMORY; 158 } 159 // init the hash function 160 if (error == B_OK) 161 _InitHashFunction(); 162 // init the negative entry list 163 if (error == B_OK) 164 _InitNegativeEntries(); 165 // cleanup on error 166 if (error != B_OK) 167 Unmount(); 168 RETURN_ERROR(error); 169} 170 171// Unmount 172status_t 173Volume::Unmount() 174{ 175 if (fRootVNode) { 176 delete fRootVNode; 177 fRootVNode = NULL; 178 } 179 if (fTree) { 180 delete fTree; 181 fTree = NULL; 182 } 183 if (fSuperBlock) { 184 delete fSuperBlock; 185 fSuperBlock = NULL; 186 } 187 if (fBlockCache) { 188 delete fBlockCache; 189 fBlockCache = NULL; 190 } 191 if (fDeviceName) { 192 delete[] fDeviceName; 193 fDeviceName = NULL; 194 } 195 if (fDevice >= 0) { 196 close(fDevice); 197 fDevice = -1; 198 } 199 if (fSettings) { 200 delete fSettings; 201 fSettings = NULL; 202 } 203 fNegativeEntries.MakeEmpty(); 204 fHashFunction = NULL; 205 fID = 0; 206 return B_OK; 207} 208 209// GetBlockSize 210off_t 211Volume::GetBlockSize() const 212{ 213 return fSuperBlock->GetBlockSize(); 214} 215 216// CountBlocks 217off_t 218Volume::CountBlocks() const 219{ 220 return fSuperBlock->CountBlocks(); 221} 222 223// CountFreeBlocks 224off_t 225Volume::CountFreeBlocks() const 226{ 227 return fSuperBlock->CountFreeBlocks(); 228} 229 230// GetName 231const char * 232Volume::GetName() const 233{ 234 return fSettings->GetVolumeName(); 235} 236 237// GetDeviceName 238const char * 239Volume::GetDeviceName() const 240{ 241 return fDeviceName; 242} 243 244// GetKeyOffsetForName 245status_t 246Volume::GetKeyOffsetForName(const char *name, int len, uint64 *result) 247{ 248 status_t error = (name && result ? B_OK : B_BAD_VALUE); 249 if (error == B_OK) { 250 if (fHashFunction) 251 *result = key_offset_for_name(fHashFunction, name, len); 252 else 253 error = B_ERROR; 254 } 255 return error; 256} 257 258// GetVNode 259status_t 260Volume::GetVNode(vnode_id id, VNode **node) 261{ 262 return get_vnode(GetID(), id, (void**)node); 263} 264 265// PutVNode 266status_t 267Volume::PutVNode(vnode_id id) 268{ 269 return put_vnode(GetID(), id); 270} 271 272// FindVNode 273/*! \brief Finds the node identified by a vnode_id. 274 275 \note The method does not initialize the parent ID for non-directory nodes. 276 277 \param id ID of the node to be found. 278 \param node pointer to a pre-allocated VNode to be initialized to 279 the found node. 280 \return \c B_OK, if everything went fine. 281*/ 282status_t 283Volume::FindVNode(vnode_id id, VNode *node) 284{ 285 return FindVNode(VNode::GetDirIDFor(id), VNode::GetObjectIDFor(id), node); 286} 287 288// FindVNode 289/*! \brief Finds the node identified by a directory ID, object ID pair. 290 291 \note The method does not initialize the parent ID for non-directory nodes. 292 293 \param dirID Directory ID of the node to be found. 294 \param objectID Object ID of the node to be found. 295 \param node pointer to a pre-allocated VNode to be initialized to 296 the found node. 297 \return \c B_OK, if everything went fine. 298*/ 299status_t 300Volume::FindVNode(uint32 dirID, uint32 objectID, VNode *node) 301{ 302 // NOTE: The node's parent dir ID is not initialized! 303 status_t error = (node ? B_OK : B_BAD_VALUE); 304 // init the node 305 if (error == B_OK) 306 error = node->SetTo(dirID, objectID); 307 // find the stat item 308 StatItem item; 309 if (error == B_OK) { 310 error = fTree->FindStatItem(dirID, objectID, &item); 311 if (error != B_OK) { 312 FATAL(("Couldn't find stat item for node (%lu, %lu)\n", 313 dirID, objectID)); 314 } 315 } 316 // get the stat data 317 if (error == B_OK) 318 SET_ERROR(error, item.GetStatData(node->GetStatData(), true)); 319 // for dirs get the ".." entry, since we need the parent dir ID 320 if (error == B_OK && node->IsDir()) { 321 DirItem dirItem; 322 int32 index = 0; 323 error = fTree->FindDirEntry(dirID, objectID, "..", &dirItem, &index); 324 if (error == B_OK) { 325 DirEntry *entry = dirItem.EntryAt(index); 326 node->SetParentID(entry->GetDirID(), entry->GetObjectID()); 327 } 328 else { 329 FATAL(("failed to find `..' entry for dir node (%lu, %ld)\n", 330 dirID, objectID)); 331 } 332 } 333 return error; 334} 335 336// FindDirEntry 337/*! \brief Searches an entry in a directory. 338 339 \note Must not be called with \a entryName "." or ".."! 340 341 \param dir The directory. 342 \param entryName Name of the entry. 343 \param foundNode pointer to a pre-allocated VNode to be initialized to 344 the found entry. 345 \param failIfHidden The method shall fail, if the entry is hidden. 346 \return \c B_OK, if everything went fine. 347*/ 348status_t 349Volume::FindDirEntry(VNode *dir, const char *entryName, VNode *foundNode, 350 bool failIfHidden) 351{ 352 status_t error = (dir && foundNode ? B_OK : B_BAD_VALUE); 353 // find the DirEntry 354 DirItem item; 355 int32 entryIndex = 0; 356 if (error == B_OK) { 357 error = fTree->FindDirEntry(dir->GetDirID(), dir->GetObjectID(), 358 entryName, &item, &entryIndex); 359 } 360 // find the child node 361 if (error == B_OK) { 362 DirEntry *entry = item.EntryAt(entryIndex); 363 error = FindVNode(entry->GetDirID(), entry->GetObjectID(), foundNode); 364 if (error == B_OK && failIfHidden && entry->IsHidden()) 365 error = B_ENTRY_NOT_FOUND; 366 } 367 return error; 368} 369 370// ReadObject 371/*! \brief Reads data from an object. 372 373 For subsequent reads better use a StreamReader. 374 375 \param node The object to be read from. 376 \param offset The file offset at which to start with reading. 377 \param buffer The buffer into which the data shall be written. 378 \param bufferSize The number of bytes to be read. 379 \param bytesRead Pointer to a size_t to be set to the number of bytes 380 actually read. 381 \return \c B_OK, if everything went fine. 382*/ 383status_t 384Volume::ReadObject(VNode *node, off_t offset, void *buffer, size_t bufferSize, 385 size_t *bytesRead) 386{ 387 status_t error = (node && buffer && bytesRead && offset >= 0 388 ? B_OK : B_BAD_VALUE); 389 // read files or symlinks only 390 if (error == B_OK && !(node->IsFile() || node->IsSymlink())) 391 error = B_BAD_VALUE; 392 // let a StreamReader do the actual work 393 if (error == B_OK) { 394 StreamReader reader(fTree, node->GetDirID(), node->GetObjectID()); 395 error = reader.InitCheck(); 396 if (error == B_OK) 397 error = reader.ReadAt(offset, buffer, bufferSize, bytesRead); 398 } 399 return error; 400} 401 402// ReadLink 403/*! \brief Reads a symlink. 404 405 \note It is not check whether the object is a symlink or not! The caller 406 is responsible for that. 407 408 \param node The symlink to be read from. 409 \param buffer The buffer into which the data shall be written. 410 \param bufferSize The number of bytes to be read. 411 \param bytesRead Pointer to a size_t to be set to the number of bytes 412 actually read. 413 \return \c B_OK, if everything went fine. 414*/ 415status_t 416Volume::ReadLink(VNode *node, char *buffer, size_t bufferSize, 417 size_t *bytesRead) 418{ 419 return ReadObject(node, 0, buffer, bufferSize, bytesRead); 420} 421 422// FindEntry 423status_t 424Volume::FindEntry(const VNode *rootDir, const char *path, VNode *foundNode) 425{ 426// Note: does not resolve links. 427PRINT(("Volume::FindEntry(`%s')\n", path)); 428 status_t error = (rootDir && path && foundNode ? B_OK : B_BAD_VALUE); 429 if (error == B_OK && (path[0] == '\0' || path[0] == '/')) 430 error = B_ENTRY_NOT_FOUND; 431 // start at the given root dir 432 if (error == B_OK) 433 *foundNode = *rootDir; 434 // resolve until we hit the end of the string 435 while (error == B_OK && path[0] != '\0') { 436PRINT((" remaining path: `%s'\n", path)); 437 int32 len = strlen(path); 438 // find the first `/' 439 const char *componentNameEnd = strchr(path, '/'); 440 if (!componentNameEnd) 441 componentNameEnd = path + len; 442 // get the name of the first component 443 int32 componentLen = componentNameEnd - path; 444 if (componentLen >= B_FILE_NAME_LENGTH) 445 return B_NAME_TOO_LONG; 446 char component[B_FILE_NAME_LENGTH]; 447 strncpy(component, path, componentLen); 448 component[componentLen] = '\0'; 449 // get the component 450PRINT((" looking for dir entry: `%s'\n", component)); 451 error = FindDirEntry(foundNode, component, foundNode); 452 // skip trailing `/'s 453 if (error == B_OK) { 454 path = componentNameEnd; 455 while (*path == '/') 456 path++; 457 } 458 } 459PRINT(("Volume::FindEntry(`%s') done: %s\n", path, strerror(error))); 460 return error; 461} 462 463// IsNegativeEntry 464bool 465Volume::IsNegativeEntry(vnode_id id) 466{ 467 for (int32 i = fNegativeEntries.CountItems() - 1; i >= 0; i--) { 468 if (fNegativeEntries.ItemAt(i) == id) 469 return true; 470 } 471 return false; 472} 473 474// IsNegativeEntry 475bool 476Volume::IsNegativeEntry(uint32 dirID, uint32 objectID) 477{ 478 return IsNegativeEntry(VNode::GetIDFor(dirID, objectID)); 479} 480 481// GetHideEsoteric 482bool 483Volume::GetHideEsoteric() const 484{ 485 return fSettings->GetHideEsoteric(); 486} 487 488// _ReadSuperBlock 489status_t 490Volume::_ReadSuperBlock() 491{ 492 status_t error = B_OK; 493 fSuperBlock = new(nothrow) SuperBlock; 494 if (fSuperBlock) 495 error = fSuperBlock->Init(fDevice); 496 else 497 error = B_NO_MEMORY; 498 // check FS state 499 if (error == B_OK && fSuperBlock->GetState() != REISERFS_VALID_FS) { 500 FATAL(("The superblock indicates a non-valid FS! Bailing out.")); 501 error = B_ERROR; 502 } 503 // check FS version 504 if (error == B_OK && fSuperBlock->GetVersion() > REISERFS_VERSION_2) { 505 FATAL(("The superblock indicates a version greater than 2 (%u)! " 506 "Bailing out.", fSuperBlock->GetVersion())); 507 error = B_ERROR; 508 } 509 RETURN_ERROR(error); 510} 511 512// hash_function_for_code 513static 514hash_function_t 515hash_function_for_code(uint32 code) 516{ 517 hash_function_t function = NULL; 518 // find the hash function 519 switch (code) { 520 case TEA_HASH: 521 function = keyed_hash; 522 break; 523 case YURA_HASH: 524 function = yura_hash; 525 break; 526 case R5_HASH: 527 function = r5_hash; 528 break; 529 case UNSET_HASH: 530 default: 531 break; 532 } 533 return function; 534} 535 536// _InitHashFunction 537void 538Volume::_InitHashFunction() 539{ 540 // get the hash function 541 fHashFunction = hash_function_for_code(fSuperBlock->GetHashFunctionCode()); 542 // try to detect it, if it is not set or is not the right one 543 if (!fHashFunction || !_VerifyHashFunction(fHashFunction)) { 544 INFORM(("No or wrong directory hash function. Try to detect...\n")); 545 uint32 code = _DetectHashFunction(); 546 fHashFunction = hash_function_for_code(code); 547 // verify it 548 if (fHashFunction) { 549 if (_VerifyHashFunction(fHashFunction)) { 550 INFORM(("Directory hash function successfully detected: %lu\n", 551 code)); 552 } else { 553 fHashFunction = NULL; 554 INFORM(("Detected directory hash function is not the right " 555 "one.\n")); 556 } 557 } else 558 INFORM(("Failed to detect the directory hash function.\n")); 559 } 560} 561 562// _DetectHashFunction 563uint32 564Volume::_DetectHashFunction() 565{ 566 // iterate over the entries in the root dir until we find an entry, that 567 // let us draw an unambiguous conclusion 568 DirEntryIterator iterator(fTree, fRootVNode->GetDirID(), 569 fRootVNode->GetObjectID(), DOT_DOT_OFFSET + 1); 570 uint32 foundCode = UNSET_HASH; 571 DirItem item; 572 int32 index = 0; 573 while (foundCode == UNSET_HASH 574 && iterator.GetNext(&item, &index) == B_OK) { 575 DirEntry *entry = item.EntryAt(index); 576 uint64 offset = entry->GetOffset(); 577 uint32 hashCodes[] = { TEA_HASH, YURA_HASH, R5_HASH }; 578 int32 hashCodeCount = sizeof(hashCodes) / sizeof(uint32); 579 size_t nameLen = 0; 580 const char *name = item.EntryNameAt(index, &nameLen); 581 if (!name) // bad data! 582 continue; 583 // try each hash function -- if there's a single winner, we're done, 584 // otherwise the next entry must help 585 for (int32 i = 0; i < hashCodeCount; i++) { 586 hash_function_t function = hash_function_for_code(hashCodes[i]); 587 uint64 testOffset = key_offset_for_name(function, name, nameLen); 588 if (offset_hash_value(offset) == offset_hash_value(testOffset)) { 589 if (foundCode != UNSET_HASH) { 590 // ambiguous 591 foundCode = UNSET_HASH; 592 break; 593 } else 594 foundCode = hashCodes[i]; 595 } 596 } 597 } 598 return foundCode; 599} 600 601// _VerifyHashFunction 602bool 603Volume::_VerifyHashFunction(hash_function_t function) 604{ 605 bool result = true; 606 // iterate over the entries in the root dir until we find an entry, that 607 // doesn't falsify the hash function 608 DirEntryIterator iterator(fTree, fRootVNode->GetDirID(), 609 fRootVNode->GetObjectID(), DOT_DOT_OFFSET + 1); 610 DirItem item; 611 int32 index = 0; 612 while (iterator.GetNext(&item, &index) == B_OK) { 613 DirEntry *entry = item.EntryAt(index); 614 uint64 offset = entry->GetOffset(); 615 // try the hash function 616 size_t nameLen = 0; 617 if (const char *name = item.EntryNameAt(index, &nameLen)) { 618 uint64 testOffset = key_offset_for_name(function, name, nameLen); 619 if (offset_hash_value(offset) != offset_hash_value(testOffset)) { 620 result = false; 621 break; 622 } 623 } // else: bad data 624 } 625 return result; 626} 627 628// _InitNegativeEntries 629void 630Volume::_InitNegativeEntries() 631{ 632 // build a list of vnode IDs 633 for (int32 i = 0; const char *entry = fSettings->HiddenEntryAt(i); i++) { 634 if (entry && strlen(entry) > 0 && entry[0] != '/') { 635 VNode node; 636 if (FindEntry(fRootVNode, entry, &node) == B_OK 637 && node.GetID() != fRootVNode->GetID()) { 638 fNegativeEntries.AddItem(node.GetID()); 639 } else 640 INFORM(("WARNING: negative entry not found: `%s'\n", entry)); 641 } 642 } 643} 644 645