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