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