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