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
FileSystemVisitor(Volume * volume)19 FileSystemVisitor::FileSystemVisitor(Volume* volume)
20 :
21 fVolume(volume),
22 fIterator(NULL)
23 {
24 }
25
26
~FileSystemVisitor()27 FileSystemVisitor::~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 */
43 status_t
Next()44 FileSystemVisitor::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 */
197 void
Start(uint32 flags)198 FileSystemVisitor::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 */
235 void
Stop()236 FileSystemVisitor::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 */
268 status_t
VisitDirectoryEntry(Inode * inode,Inode * parent,const char * treeName)269 FileSystemVisitor::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 */
286 status_t
VisitInode(Inode * inode,const char * treeName)287 FileSystemVisitor::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 */
302 status_t
OpenInodeFailed(status_t reason,ino_t id,Inode * parent,char * treeName,TreeIterator * iterator)303 FileSystemVisitor::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 */
317 status_t
OpenBPlusTreeFailed(Inode * inode)318 FileSystemVisitor::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 */
331 status_t
TreeIterationFailed(status_t reason,Inode * parent)332 FileSystemVisitor::TreeIterationFailed(status_t reason, Inode* parent)
333 {
334 return B_OK;
335 }
336