1/*
2 * Copyright 2002-2012, Axel D��rfler, axeld@pinc-software.de.
3 * Copyright 2012, Andreas Henriksson, sausageboy@gmail.com
4 * This file may be used under the terms of the MIT License.
5 */
6
7
8//! Traversing the file system
9
10
11#include "FileSystemVisitor.h"
12
13#include "BPlusTree.h"
14#include "Debug.h"
15#include "Inode.h"
16#include "Volume.h"
17
18
19FileSystemVisitor::FileSystemVisitor(Volume* volume)
20	:
21	fVolume(volume),
22	fIterator(NULL)
23{
24}
25
26
27FileSystemVisitor::~FileSystemVisitor()
28{
29	Stop();
30}
31
32
33//	#pragma mark - file system traversal
34
35
36/*! Visit the next inode.
37
38	\return
39	- \c B_ENTRY_NOT_FOUND : All nodes specified in Start() have been
40	  traversed
41	- Any error code returned by the overridable functions
42*/
43status_t
44FileSystemVisitor::Next()
45{
46	status_t status;
47
48	while (true) {
49		const char* name = NULL;
50		char treeName[B_FILE_NAME_LENGTH];
51		Inode* inode;
52		Vnode vnode;
53
54		if (fIterator == NULL) {
55			if (!fStack.Pop(&fCurrent)) {
56				// we're done
57				return B_ENTRY_NOT_FOUND;
58			}
59
60			// open inode
61			vnode.SetTo(fVolume, fCurrent);
62			status = vnode.Get(&inode);
63
64			// release the reference we acquired when pushing the node to
65			// the stack
66			put_vnode(fVolume->FSVolume(), fVolume->ToVnode(fCurrent));
67
68			if (status != B_OK) {
69				if (inode != NULL && inode->IsDeleted())
70					continue;
71
72				status = OpenInodeFailed(status, fVolume->ToBlock(fCurrent),
73					NULL, NULL, NULL);
74				if (status == B_OK)
75					continue;
76				return status;
77			}
78
79			if (inode->IsContainer()) {
80				// open directory
81				BPlusTree* tree = inode->Tree();
82				if (tree == NULL) {
83					status = OpenBPlusTreeFailed(inode);
84					if (status == B_OK)
85						continue;
86					return status;
87				}
88
89				fParent = inode;
90
91				// get iterator for the next directory
92				fIterator = new(std::nothrow) TreeIterator(tree);
93				if (fIterator == NULL)
94					RETURN_ERROR(B_NO_MEMORY);
95
96				// the inode must stay locked in memory until the iterator
97				// is freed
98				vnode.Keep();
99			}
100		} else {
101			uint16 length;
102			ino_t id;
103
104			status_t status = fIterator->GetNextEntry(treeName, &length,
105				B_FILE_NAME_LENGTH, &id);
106			if (status != B_OK) {
107				// we no longer need this iterator
108				delete fIterator;
109				fIterator = NULL;
110
111				// unlock the directory's inode from memory
112				put_vnode(fVolume->FSVolume(),
113					fVolume->ToVnode(fCurrent));
114
115				if (status == B_ENTRY_NOT_FOUND) {
116					// We iterated over all entries already, just go on
117					// to the next
118					continue;
119				}
120
121				// iterating over the B+tree failed
122				//return TreeIterationFailed(status, fParent);
123				status = TreeIterationFailed(status, fParent);
124				if (status == B_OK)
125					continue;
126				return status;
127			}
128
129			// ignore "." and ".." entries
130			if (!strcmp(treeName, ".") || !strcmp(treeName, ".."))
131				continue;
132
133			vnode.SetTo(fVolume, id);
134			status = vnode.Get(&inode);
135			if (status != B_OK) {
136				status = OpenInodeFailed(status, id, fParent, treeName,
137					fIterator);
138				if (status == B_OK)
139					continue;
140				return status;
141			}
142
143			status = VisitDirectoryEntry(inode, fParent, treeName);
144			if (status != B_OK)
145				return status;
146
147			if (inode->IsContainer() && !inode->IsIndex()) {
148				// push the directory on the stack, it will be visited after
149				// its children
150				fStack.Push(inode->BlockRun());
151
152				// the inode may be deleted behind our back, we keep a
153				// reference so we can check for this
154				vnode.Keep();
155				continue;
156			}
157
158			name = treeName;
159		}
160
161		// If the inode has an attribute directory that we want to visit,
162		// push it on the stack
163		if ((fFlags & VISIT_ATTRIBUTE_DIRECTORIES)
164				&& !inode->Attributes().IsZero()) {
165			fStack.Push(inode->Attributes());
166
167			// We may already be keeping the associated Vnode, so we can't
168			// just call vnode.Keep() here, but rather acquire another reference
169			// to it specifically.
170			Vnode attrNode(fVolume, inode->Attributes());
171			attrNode.Keep();
172		}
173
174		bool visitingCurrentDirectory = inode->BlockRun() == fCurrent;
175
176		status = VisitInode(inode, name);
177
178		// the inode id is allowed to change in the VisitInode() call, so we
179		// may need to change the inode reference
180		if (visitingCurrentDirectory)
181			fCurrent = inode->BlockRun();
182
183		return status;
184	}
185	// is never reached
186}
187
188
189/*! Start/restart traversal. \a flags is used to specify the nodes visited:
190	- \c VISIT_REGULAR :	Visit the nodes that are reachable by traversing
191							the file system from the root directory.
192	- \c VISIT_INDICES :	Visit the index directory and indices
193	- \c VISIT_REMOVED :	Visit removed vnodes
194	- \c VISIT_ATTRIBUTE_DIRECTORIES :	Visit the attribute directory and
195										attributes of files that have them.
196*/
197void
198FileSystemVisitor::Start(uint32 flags)
199{
200	// initialize state
201	Stop();
202	fCurrent.SetTo(0, 0, 0);
203	fParent = NULL;
204	fStack.MakeEmpty();
205
206	fFlags = flags;
207
208	if (fFlags & VISIT_REGULAR) {
209		Vnode vnode(fVolume, fVolume->Root());
210		vnode.Keep();
211		fStack.Push(fVolume->Root());
212	}
213
214	if (fFlags & VISIT_INDICES) {
215		Vnode vnode(fVolume, fVolume->Indices());
216		vnode.Keep();
217		fStack.Push(fVolume->Indices());
218	}
219
220	if (fFlags & VISIT_REMOVED) {
221		// Put removed vnodes to the stack -- they are not reachable by
222		// traversing the file system anymore.
223		InodeList::Iterator iterator = fVolume->RemovedInodes().GetIterator();
224		while (Inode* inode = iterator.Next()) {
225			Vnode vnode(fVolume, inode->ID());
226			vnode.Keep();
227			fStack.Push(inode->BlockRun());
228		}
229	}
230}
231
232
233/*! Free aquired resources. This function is called from the destructor.
234*/
235void
236FileSystemVisitor::Stop()
237{
238	if (fIterator != NULL) {
239		delete fIterator;
240		fIterator = NULL;
241
242		// the current directory inode is still locked in memory
243		put_vnode(fVolume->FSVolume(), fVolume->ToVnode(fCurrent));
244	}
245
246	// release the references to the vnodes on the stack
247	block_run run;
248	while (fStack.Pop(&run))
249		put_vnode(fVolume->FSVolume(), fVolume->ToVnode(run));
250}
251
252
253//	#pragma mark - overrideable actions
254
255
256/*! Called when an inode is opened while iterating through its parent
257	directory. Note that this function is not called for inodes which
258	don't have a proper parent directory, namely:
259	- The root directory
260	- The index directory
261	- Attribute directories
262	- Removed nodes
263
264	Return \c B_OK to continue traversing, any other error code to stop
265	traversal and propagate the error to the caller of Next(). In the
266	latter case, VisitInode() will never be called for this inode.
267*/
268status_t
269FileSystemVisitor::VisitDirectoryEntry(Inode* inode, Inode* parent,
270	const char* treeName)
271{
272	return B_OK;
273}
274
275
276/*! Called for every inode, some time after VisitDirectoryEntry(). For
277	directories, all subdirectories will be traversed before this
278	function is called.
279
280	Unless traversal has been stopped by an error handling function, all
281	calls to Next() end by invoking this function, and the return value
282	is passed along to the caller.
283
284	This call may change the inode ID.
285*/
286status_t
287FileSystemVisitor::VisitInode(Inode* inode, const char* treeName)
288{
289	return B_OK;
290}
291
292
293/*! Called when opening an inode fails. If the failure happened while
294	iterating through a directory, \a parent, \a treeName and \a iterator
295	will be provided. Otherwise, they will be \c NULL.
296
297	\return
298	- \c B_OK : The traversal continues to the next inode
299	- Other : The traversal stops and the error code is propagated to the
300	  caller of Next().
301*/
302status_t
303FileSystemVisitor::OpenInodeFailed(status_t reason, ino_t id, Inode* parent,
304	char* treeName, TreeIterator* iterator)
305{
306	return B_OK;
307}
308
309
310/*! Called when opening a b+tree fails.
311
312	\return
313	- \c B_OK : The traversal continues to the next inode
314	- Other : The traversal stops and the error code is propagated to the
315	  caller of Next().
316*/
317status_t
318FileSystemVisitor::OpenBPlusTreeFailed(Inode* inode)
319{
320	return B_OK;
321}
322
323
324/*! Called if we failed to get the next node while iterating a container.
325
326	\return
327	- \c B_OK : The traversal continues to the next inode
328	- Other : The traversal stops and the error code is propagated to the
329	  caller of Next().
330*/
331status_t
332FileSystemVisitor::TreeIterationFailed(status_t reason, Inode* parent)
333{
334	return B_OK;
335}
336