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