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