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