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