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 superblock 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 superblock 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 superblock 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 (fSuperBlock->GetLabel(fVolumeName, sizeof(fVolumeName)) == B_OK) 266 return; 267 if (get_default_partition_content_name(partitionID, "ReiserFS", 268 fVolumeName, sizeof(fVolumeName)) == B_OK) 269 return; 270 strlcpy(fVolumeName, "ReiserFS Volume", sizeof(fVolumeName)); 271 } 272 273 274 // GetDeviceName 275 const char * 276 Volume::GetDeviceName() const 277 { 278 return fDeviceName; 279 } 280 281 // GetKeyOffsetForName 282 status_t 283 Volume::GetKeyOffsetForName(const char *name, int len, uint64 *result) 284 { 285 status_t error = (name && result ? B_OK : B_BAD_VALUE); 286 if (error == B_OK) { 287 if (fHashFunction) 288 *result = key_offset_for_name(fHashFunction, name, len); 289 else 290 error = B_ERROR; 291 } 292 return error; 293 } 294 295 // GetVNode 296 status_t 297 Volume::GetVNode(ino_t id, VNode **node) 298 { 299 return get_vnode(GetFSVolume(), id, (void**)node); 300 } 301 302 // PutVNode 303 status_t 304 Volume::PutVNode(ino_t id) 305 { 306 return put_vnode(GetFSVolume(), id); 307 } 308 309 // FindVNode 310 /*! \brief Finds the node identified by a ino_t. 311 312 \note The method does not initialize the parent ID for non-directory nodes. 313 314 \param id ID of the node to be found. 315 \param node pointer to a pre-allocated VNode to be initialized to 316 the found node. 317 \return \c B_OK, if everything went fine. 318 */ 319 status_t 320 Volume::FindVNode(ino_t id, VNode *node) 321 { 322 return FindVNode(VNode::GetDirIDFor(id), VNode::GetObjectIDFor(id), node); 323 } 324 325 // FindVNode 326 /*! \brief Finds the node identified by a directory ID, object ID pair. 327 328 \note The method does not initialize the parent ID for non-directory nodes. 329 330 \param dirID Directory ID of the node to be found. 331 \param objectID Object ID of the node to be found. 332 \param node pointer to a pre-allocated VNode to be initialized to 333 the found node. 334 \return \c B_OK, if everything went fine. 335 */ 336 status_t 337 Volume::FindVNode(uint32 dirID, uint32 objectID, VNode *node) 338 { 339 // NOTE: The node's parent dir ID is not initialized! 340 status_t error = (node ? B_OK : B_BAD_VALUE); 341 // init the node 342 if (error == B_OK) 343 error = node->SetTo(dirID, objectID); 344 // find the stat item 345 StatItem item; 346 if (error == B_OK) { 347 error = fTree->FindStatItem(dirID, objectID, &item); 348 if (error != B_OK) { 349 FATAL(("Couldn't find stat item for node " 350 "(%" B_PRIu32 ", %" B_PRIu32 ")\n", 351 dirID, objectID)); 352 } 353 } 354 // get the stat data 355 if (error == B_OK) 356 SET_ERROR(error, item.GetStatData(node->GetStatData(), true)); 357 // for dirs get the ".." entry, since we need the parent dir ID 358 if (error == B_OK && node->IsDir()) { 359 DirItem dirItem; 360 int32 index = 0; 361 error = fTree->FindDirEntry(dirID, objectID, "..", &dirItem, &index); 362 if (error == B_OK) { 363 DirEntry *entry = dirItem.EntryAt(index); 364 node->SetParentID(entry->GetDirID(), entry->GetObjectID()); 365 } 366 else { 367 FATAL(("failed to find `..' entry for dir node " 368 "(%" B_PRIu32 ", %" B_PRIu32 ")\n", 369 dirID, objectID)); 370 } 371 } 372 return error; 373 } 374 375 // FindDirEntry 376 /*! \brief Searches an entry in a directory. 377 378 \note Must not be called with \a entryName "." or ".."! 379 380 \param dir The directory. 381 \param entryName Name of the entry. 382 \param foundNode pointer to a pre-allocated VNode to be initialized to 383 the found entry. 384 \param failIfHidden The method shall fail, if the entry is hidden. 385 \return \c B_OK, if everything went fine. 386 */ 387 status_t 388 Volume::FindDirEntry(VNode *dir, const char *entryName, VNode *foundNode, 389 bool failIfHidden) 390 { 391 status_t error = (dir && foundNode ? B_OK : B_BAD_VALUE); 392 // find the DirEntry 393 DirItem item; 394 int32 entryIndex = 0; 395 if (error == B_OK) { 396 error = fTree->FindDirEntry(dir->GetDirID(), dir->GetObjectID(), 397 entryName, &item, &entryIndex); 398 } 399 // find the child node 400 if (error == B_OK) { 401 DirEntry *entry = item.EntryAt(entryIndex); 402 error = FindVNode(entry->GetDirID(), entry->GetObjectID(), foundNode); 403 if (error == B_OK && failIfHidden && entry->IsHidden()) 404 error = B_ENTRY_NOT_FOUND; 405 } 406 return error; 407 } 408 409 // ReadObject 410 /*! \brief Reads data from an object. 411 412 For subsequent reads better use a StreamReader. 413 414 \param node The object to be read from. 415 \param offset The file offset at which to start with reading. 416 \param buffer The buffer into which the data shall be written. 417 \param bufferSize The number of bytes to be read. 418 \param bytesRead Pointer to a size_t to be set to the number of bytes 419 actually read. 420 \return \c B_OK, if everything went fine. 421 */ 422 status_t 423 Volume::ReadObject(VNode *node, off_t offset, void *buffer, size_t bufferSize, 424 size_t *bytesRead) 425 { 426 status_t error = (node && buffer && bytesRead && offset >= 0 427 ? B_OK : B_BAD_VALUE); 428 // read files or symlinks only 429 if (error == B_OK && !(node->IsFile() || node->IsSymlink())) 430 error = B_BAD_VALUE; 431 // let a StreamReader do the actual work 432 if (error == B_OK) { 433 StreamReader reader(fTree, node->GetDirID(), node->GetObjectID()); 434 error = reader.InitCheck(); 435 if (error == B_OK) 436 error = reader.ReadAt(offset, buffer, bufferSize, bytesRead); 437 } 438 return error; 439 } 440 441 // ReadLink 442 /*! \brief Reads a symlink. 443 444 \note It is not check whether the object is a symlink or not! The caller 445 is responsible for that. 446 447 \param node The symlink to be read from. 448 \param buffer The buffer into which the data shall be written. 449 \param bufferSize The number of bytes to be read. 450 \param bytesRead Pointer to a size_t to be set to the number of bytes 451 actually read. 452 \return \c B_OK, if everything went fine. 453 */ 454 status_t 455 Volume::ReadLink(VNode *node, char *buffer, size_t bufferSize, 456 size_t *bytesRead) 457 { 458 return ReadObject(node, 0, buffer, bufferSize, bytesRead); 459 } 460 461 // FindEntry 462 status_t 463 Volume::FindEntry(const VNode *rootDir, const char *path, VNode *foundNode) 464 { 465 // Note: does not resolve links. 466 PRINT(("Volume::FindEntry(`%s')\n", path)); 467 status_t error = (rootDir && path && foundNode ? B_OK : B_BAD_VALUE); 468 if (error == B_OK && (path[0] == '\0' || path[0] == '/')) 469 error = B_ENTRY_NOT_FOUND; 470 // start at the given root dir 471 if (error == B_OK) 472 *foundNode = *rootDir; 473 // resolve until we hit the end of the string 474 while (error == B_OK && path[0] != '\0') { 475 PRINT((" remaining path: `%s'\n", path)); 476 int32 len = strlen(path); 477 // find the first `/' 478 const char *componentNameEnd = strchr(path, '/'); 479 if (!componentNameEnd) 480 componentNameEnd = path + len; 481 // get the name of the first component 482 int32 componentLen = componentNameEnd - path; 483 if (componentLen >= B_FILE_NAME_LENGTH) 484 return B_NAME_TOO_LONG; 485 char component[B_FILE_NAME_LENGTH]; 486 strncpy(component, path, componentLen); 487 component[componentLen] = '\0'; 488 // get the component 489 PRINT((" looking for dir entry: `%s'\n", component)); 490 error = FindDirEntry(foundNode, component, foundNode); 491 // skip trailing `/'s 492 if (error == B_OK) { 493 path = componentNameEnd; 494 while (*path == '/') 495 path++; 496 } 497 } 498 PRINT(("Volume::FindEntry(`%s') done: %s\n", path, strerror(error))); 499 return error; 500 } 501 502 // IsNegativeEntry 503 bool 504 Volume::IsNegativeEntry(ino_t id) 505 { 506 for (int32 i = fNegativeEntries.CountItems() - 1; i >= 0; i--) { 507 if (fNegativeEntries.ItemAt(i) == id) 508 return true; 509 } 510 return false; 511 } 512 513 // IsNegativeEntry 514 bool 515 Volume::IsNegativeEntry(uint32 dirID, uint32 objectID) 516 { 517 return IsNegativeEntry(VNode::GetIDFor(dirID, objectID)); 518 } 519 520 // GetHideEsoteric 521 bool 522 Volume::GetHideEsoteric() const 523 { 524 return fSettings->GetHideEsoteric(); 525 } 526 527 // _ReadSuperBlock 528 status_t 529 Volume::_ReadSuperBlock() 530 { 531 status_t error = B_OK; 532 fSuperBlock = new(nothrow) SuperBlock; 533 if (fSuperBlock) 534 error = fSuperBlock->Init(fDevice); 535 else 536 error = B_NO_MEMORY; 537 // check FS state 538 if (error == B_OK && fSuperBlock->GetState() != REISERFS_VALID_FS) { 539 FATAL(("The superblock indicates a non-valid FS! Bailing out.")); 540 error = B_ERROR; 541 } 542 // check FS version 543 if (error == B_OK && fSuperBlock->GetVersion() > REISERFS_VERSION_2) { 544 FATAL(("The superblock indicates a version greater than 2 (%u)! " 545 "Bailing out.", fSuperBlock->GetVersion())); 546 error = B_ERROR; 547 } 548 RETURN_ERROR(error); 549 } 550 551 // hash_function_for_code 552 static 553 hash_function_t 554 hash_function_for_code(uint32 code) 555 { 556 hash_function_t function = NULL; 557 // find the hash function 558 switch (code) { 559 case TEA_HASH: 560 function = keyed_hash; 561 break; 562 case YURA_HASH: 563 function = yura_hash; 564 break; 565 case R5_HASH: 566 function = r5_hash; 567 break; 568 case UNSET_HASH: 569 default: 570 break; 571 } 572 return function; 573 } 574 575 // _InitHashFunction 576 void 577 Volume::_InitHashFunction() 578 { 579 // get the hash function 580 fHashFunction = hash_function_for_code(fSuperBlock->GetHashFunctionCode()); 581 // try to detect it, if it is not set or is not the right one 582 if (!fHashFunction || !_VerifyHashFunction(fHashFunction)) { 583 INFORM(("No or wrong directory hash function. Try to detect...\n")); 584 uint32 code = _DetectHashFunction(); 585 fHashFunction = hash_function_for_code(code); 586 // verify it 587 if (fHashFunction) { 588 if (_VerifyHashFunction(fHashFunction)) { 589 INFORM(("Directory hash function successfully detected: " 590 "%" B_PRIu32 "\n", code)); 591 } else { 592 fHashFunction = NULL; 593 INFORM(("Detected directory hash function is not the right " 594 "one.\n")); 595 } 596 } else 597 INFORM(("Failed to detect the directory hash function.\n")); 598 } 599 } 600 601 // _DetectHashFunction 602 uint32 603 Volume::_DetectHashFunction() 604 { 605 // iterate over the entries in the root dir until we find an entry, that 606 // let us draw an unambiguous conclusion 607 DirEntryIterator iterator(fTree, fRootVNode->GetDirID(), 608 fRootVNode->GetObjectID(), DOT_DOT_OFFSET + 1); 609 uint32 foundCode = UNSET_HASH; 610 DirItem item; 611 int32 index = 0; 612 while (foundCode == UNSET_HASH 613 && iterator.GetNext(&item, &index) == B_OK) { 614 DirEntry *entry = item.EntryAt(index); 615 uint64 offset = entry->GetOffset(); 616 uint32 hashCodes[] = { TEA_HASH, YURA_HASH, R5_HASH }; 617 int32 hashCodeCount = sizeof(hashCodes) / sizeof(uint32); 618 size_t nameLen = 0; 619 const char *name = item.EntryNameAt(index, &nameLen); 620 if (!name) // bad data! 621 continue; 622 // try each hash function -- if there's a single winner, we're done, 623 // otherwise the next entry must help 624 for (int32 i = 0; i < hashCodeCount; i++) { 625 hash_function_t function = hash_function_for_code(hashCodes[i]); 626 uint64 testOffset = key_offset_for_name(function, name, nameLen); 627 if (offset_hash_value(offset) == offset_hash_value(testOffset)) { 628 if (foundCode != UNSET_HASH) { 629 // ambiguous 630 foundCode = UNSET_HASH; 631 break; 632 } else 633 foundCode = hashCodes[i]; 634 } 635 } 636 } 637 return foundCode; 638 } 639 640 // _VerifyHashFunction 641 bool 642 Volume::_VerifyHashFunction(hash_function_t function) 643 { 644 bool result = true; 645 // iterate over the entries in the root dir until we find an entry, that 646 // doesn't falsify the hash function 647 DirEntryIterator iterator(fTree, fRootVNode->GetDirID(), 648 fRootVNode->GetObjectID(), DOT_DOT_OFFSET + 1); 649 DirItem item; 650 int32 index = 0; 651 while (iterator.GetNext(&item, &index) == B_OK) { 652 DirEntry *entry = item.EntryAt(index); 653 uint64 offset = entry->GetOffset(); 654 // try the hash function 655 size_t nameLen = 0; 656 if (const char *name = item.EntryNameAt(index, &nameLen)) { 657 uint64 testOffset = key_offset_for_name(function, name, nameLen); 658 if (offset_hash_value(offset) != offset_hash_value(testOffset)) { 659 result = false; 660 break; 661 } 662 } // else: bad data 663 } 664 return result; 665 } 666 667 // _InitNegativeEntries 668 void 669 Volume::_InitNegativeEntries() 670 { 671 // build a list of vnode IDs 672 for (int32 i = 0; const char *entry = fSettings->HiddenEntryAt(i); i++) { 673 if (entry && strlen(entry) > 0 && entry[0] != '/') { 674 VNode node; 675 if (FindEntry(fRootVNode, entry, &node) == B_OK 676 && node.GetID() != fRootVNode->GetID()) { 677 fNegativeEntries.AddItem(node.GetID()); 678 } else 679 INFORM(("WARNING: negative entry not found: `%s'\n", entry)); 680 } 681 } 682 } 683