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>
min(const C & a,const C & b)51 static inline C min(const C &a, const C &b) { return (a < b ? a : b); }
52 template<typename C>
max(const C & a,const C & b)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
Volume()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
~Volume()85 Volume::~Volume()
86 {
87 Unmount();
88 }
89
90
91 // Identify
92 status_t
Identify(int fd,partition_data * partition)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
Mount(fs_volume * fsVolume,const char * path)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
Unmount()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
GetBlockSize() const234 Volume::GetBlockSize() const
235 {
236 return fSuperBlock->GetBlockSize();
237 }
238
239 // CountBlocks
240 off_t
CountBlocks() const241 Volume::CountBlocks() const
242 {
243 return fSuperBlock->CountBlocks();
244 }
245
246 // CountFreeBlocks
247 off_t
CountFreeBlocks() const248 Volume::CountFreeBlocks() const
249 {
250 return fSuperBlock->CountFreeBlocks();
251 }
252
253 // GetName
254 const char *
GetName() const255 Volume::GetName() const
256 {
257 return fVolumeName;
258 }
259
260
261 // UpdateName
262 void
UpdateName(partition_id partitionID)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 *
GetDeviceName() const276 Volume::GetDeviceName() const
277 {
278 return fDeviceName;
279 }
280
281 // GetKeyOffsetForName
282 status_t
GetKeyOffsetForName(const char * name,int len,uint64 * result)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
GetVNode(ino_t id,VNode ** node)297 Volume::GetVNode(ino_t id, VNode **node)
298 {
299 return get_vnode(GetFSVolume(), id, (void**)node);
300 }
301
302 // PutVNode
303 status_t
PutVNode(ino_t id)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
FindVNode(ino_t id,VNode * node)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
FindVNode(uint32 dirID,uint32 objectID,VNode * node)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
FindDirEntry(VNode * dir,const char * entryName,VNode * foundNode,bool failIfHidden)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
ReadLink(VNode * node,char * buffer,size_t bufferSize,size_t * linkLength)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
FindEntry(const VNode * rootDir,const char * path,VNode * foundNode)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
IsNegativeEntry(ino_t id)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
IsNegativeEntry(uint32 dirID,uint32 objectID)499 Volume::IsNegativeEntry(uint32 dirID, uint32 objectID)
500 {
501 return IsNegativeEntry(VNode::GetIDFor(dirID, objectID));
502 }
503
504 // GetHideEsoteric
505 bool
GetHideEsoteric() const506 Volume::GetHideEsoteric() const
507 {
508 return fSettings->GetHideEsoteric();
509 }
510
511 // _ReadSuperBlock
512 status_t
_ReadSuperBlock()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
hash_function_for_code(uint32 code)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
_InitHashFunction()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
_DetectHashFunction()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
_VerifyHashFunction(hash_function_t function)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
_InitNegativeEntries()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