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
44extern 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.
50template<typename C>
51static inline C min(const C &a, const C &b) { return (a < b ? a : b); }
52template<typename C>
53static 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
69Volume::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
85Volume::~Volume()
86{
87	Unmount();
88}
89
90
91// Identify
92status_t
93Volume::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
105status_t
106Volume::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);
158REPORT_ERROR(error);
159		if (error == B_OK) {
160			rootBlock->SetKind(Block::KIND_FORMATTED);
161			error = fTree->Init(this, rootBlock->ToNode(),
162								fSuperBlock->GetTreeHeight());
163REPORT_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);
173REPORT_ERROR(error);
174			if (error == B_OK) {
175				error = publish_vnode(fFSVolume, fRootVNode->GetID(),
176					fRootVNode, &gReiserFSVnodeOps, S_IFDIR, 0);
177			}
178REPORT_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
195status_t
196Volume::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
233off_t
234Volume::GetBlockSize() const
235{
236	return fSuperBlock->GetBlockSize();
237}
238
239// CountBlocks
240off_t
241Volume::CountBlocks() const
242{
243	return fSuperBlock->CountBlocks();
244}
245
246// CountFreeBlocks
247off_t
248Volume::CountFreeBlocks() const
249{
250	return fSuperBlock->CountFreeBlocks();
251}
252
253// GetName
254const char *
255Volume::GetName() const
256{
257	return fVolumeName;
258}
259
260
261// UpdateName
262void
263Volume::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
275const char *
276Volume::GetDeviceName() const
277{
278	return fDeviceName;
279}
280
281// GetKeyOffsetForName
282status_t
283Volume::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
296status_t
297Volume::GetVNode(ino_t id, VNode **node)
298{
299	return get_vnode(GetFSVolume(), id, (void**)node);
300}
301
302// PutVNode
303status_t
304Volume::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*/
319status_t
320Volume::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*/
336status_t
337Volume::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*/
387status_t
388Volume::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*/
422status_t
423Volume::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
446status_t
447Volume::FindEntry(const VNode *rootDir, const char *path, VNode *foundNode)
448{
449// Note: does not resolve links.
450PRINT(("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') {
459PRINT(("  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
473PRINT(("  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	}
482PRINT(("Volume::FindEntry(`%s') done: %s\n", path, strerror(error)));
483	return error;
484}
485
486// IsNegativeEntry
487bool
488Volume::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
498bool
499Volume::IsNegativeEntry(uint32 dirID, uint32 objectID)
500{
501	return IsNegativeEntry(VNode::GetIDFor(dirID, objectID));
502}
503
504// GetHideEsoteric
505bool
506Volume::GetHideEsoteric() const
507{
508	return fSettings->GetHideEsoteric();
509}
510
511// _ReadSuperBlock
512status_t
513Volume::_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
536static
537hash_function_t
538hash_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
560void
561Volume::_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
586uint32
587Volume::_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
625bool
626Volume::_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
652void
653Volume::_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