1 /****************************************************************************
2 * fs/inode/fs_inodesearch.c
3 *
4 * Copyright (C) 2007-2009, 2011-2012, 2016-2017 Gregory Nutt. All rights reserved.
5 * Author: Gregory Nutt <gnutt@nuttx.org>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * 3. Neither the name NuttX nor the names of its contributors may be
18 * used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
28 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *
34 ****************************************************************************/
35
36 /****************************************************************************
37 * Included Files
38 ****************************************************************************/
39
40 #include "vfs_config.h"
41
42 #include "assert.h"
43 #include "errno.h"
44 #include "semaphore.h"
45 #include "stdlib.h"
46 #include "fs/fs.h"
47
48 #include "inode/inode.h"
49 /****************************************************************************
50 * Public Data
51 ****************************************************************************/
52
53 FAR struct inode *g_root_inode = NULL;
54
55 /****************************************************************************
56 * Private Functions
57 ****************************************************************************/
58
59 /****************************************************************************
60 * Name: _inode_compare
61 *
62 * Description:
63 * Compare two inode names
64 *
65 ****************************************************************************/
66
_inode_compare(FAR const char * fname,FAR struct inode * node)67 static int _inode_compare(FAR const char *fname, FAR struct inode *node)
68 {
69 char *nname = node->i_name;
70
71 if (!nname)
72 {
73 return 1;
74 }
75
76 if (!fname)
77 {
78 return -1;
79 }
80
81 for (; ; )
82 {
83 /* At the end of the node name? */
84
85 if (!*nname)
86 {
87 /* Yes.. also at the end of find name? */
88
89 if (!*fname || *fname == '/')
90 {
91 /* Yes.. return match */
92
93 return 0;
94 }
95 else
96 {
97 /* No... return find name > node name */
98
99 return 1;
100 }
101 }
102
103 /* At end of the find name? */
104
105 else if (!*fname || *fname == '/')
106 {
107 /* Yes... return find name < node name */
108
109 return -1;
110 }
111
112 /* Check for non-matching characters */
113
114 else if (*fname > *nname)
115 {
116 return 1;
117 }
118 else if (*fname < *nname)
119 {
120 return -1;
121 }
122
123 /* Not at the end of either string and all of the
124 * characters still match. keep looking.
125 */
126
127 else
128 {
129 fname++;
130 nname++;
131 }
132 }
133 }
134
135
136
137 /****************************************************************************
138 * Name: inode_search
139 *
140 * Description:
141 * Find the inode associated with 'path' returning the inode references
142 * and references to its companion nodes.
143 *
144 * Assumptions:
145 * The caller holds the g_inode_sem semaphore
146 *
147 * TODO: Nuttx 8.2 inode_search() uses struct inode_search_s as parameter
148 ****************************************************************************/
149
inode_search(FAR const char ** path,FAR struct inode ** peer,FAR struct inode ** parent,FAR const char ** relpath)150 FAR struct inode *inode_search(FAR const char **path,
151 FAR struct inode **peer,
152 FAR struct inode **parent,
153 FAR const char **relpath)
154 {
155 FAR const char *name = *path;
156 FAR struct inode *ret_inode = NULL;
157 FAR struct inode *node = g_root_inode;
158 FAR struct inode *left = NULL;
159 FAR struct inode *above = NULL;
160
161 while (node)
162 {
163 int result = _inode_compare(name, node);
164
165 /* Case 1: The name is less than the name of the node.
166 * Since the names are ordered, these means that there
167 * is no peer node with this name and that there can be
168 * no match in the fileystem.
169 */
170
171 if (result < 0)
172 {
173 node = NULL;
174 break;
175 }
176
177 /* Case 2: the name is greater than the name of the node.
178 * In this case, the name may still be in the list to the
179 * "right"
180 */
181
182 else if (result > 0)
183 {
184 left = node;
185 node = node->i_peer;
186 }
187
188 /* The names match */
189
190 else
191 {
192 /* Now there are three more possibilities:
193 * (1) This is the node that we are looking for or,
194 * (2) The node we are looking for is "below" this one.
195 * (3) This node is a mountpoint and will absorb all request
196 * below this one
197 */
198
199 name = inode_nextname(name);
200
201 if (!INODE_IS_MOUNTPT(g_root_inode))
202 {
203 /* This g_root_inode is not a mountpoint and will handle the
204 * remaining part of the pathname
205 */
206
207 if (relpath != NULL)
208 {
209 ret_inode = node;
210 *relpath = name;
211 }
212 }
213
214 if (INODE_IS_MOUNTPT(node))
215 {
216 /* This node is a mountpoint and will handle the
217 * remaining part of the pathname
218 */
219
220 if (relpath != NULL)
221 {
222 ret_inode = node;
223 *relpath = name;
224 }
225 }
226
227 if (!*name)
228 {
229 /* We are at the end of the path, so this must be the
230 * node we are looking for
231 */
232 ret_inode = node;
233 if (relpath != NULL)
234 {
235 *relpath = name;
236 }
237 break;
238 }
239 else
240 {
241 /* More to go, keep looking at the next level "down" */
242 above = node;
243 left = NULL;
244 if ((g_root_inode != NULL) && VfsPermissionCheck(node->i_uid, node->i_gid, node->i_mode, EXEC_OP))
245 {
246 /* If g_root_inode has set and node has not execution authority, while break */
247
248 ret_inode = NULL;
249 node = NULL;
250 break;
251 }
252
253 node = node->i_child;
254 }
255 }
256 }
257
258 /* The node may or may not be null as per one of the following four cases
259 * cases:
260 *
261 * With node = NULL
262 *
263 * (1) We went left past the final peer: The new node name is larger
264 * than any existing node name at that level.
265 * (2) We broke out in the middle of the list of peers because the name
266 * was not found in the ordered list.
267 * (3) We went down past the final parent: The new node name is
268 * "deeper" than anything that we currently have in the tree.
269 *
270 * With node != NULL
271 *
272 * (4) When the node matching the full path is found
273 */
274
275 if (peer != NULL)
276 {
277 *peer = left;
278 }
279
280 if (parent != NULL)
281 {
282 *parent = above;
283 }
284
285 *path = name;
286 return ret_inode;
287 }
288
289 /****************************************************************************
290 * Name: inode_free
291 *
292 * Description:
293 * Free resources used by an inode
294 *
295 ****************************************************************************/
296
inode_free(FAR struct inode * node)297 void inode_free(FAR struct inode *node)
298 {
299 if (node != NULL)
300 {
301 inode_free(node->i_peer);
302 inode_free(node->i_child);
303 (VOID)LOS_MemFree(m_aucSysMem0, node);
304 }
305 }
306
307 /****************************************************************************
308 * Name: inode_nextname
309 *
310 * Description:
311 * Given a path with node names separated by '/', return the next path
312 * segment name.
313 *
314 ****************************************************************************/
315
inode_nextname(FAR const char * name)316 FAR const char *inode_nextname(FAR const char *name)
317 {
318 /* Search for the '/' delimiter or the NUL terminator at the end of the
319 * path segment.
320 */
321
322 while (*name != '\0' && *name != '/')
323 {
324 name++;
325 }
326
327 /* If we found the '/' delimiter, then the path segment we want begins at
328 * the next character (which might also be the NUL terminator).
329 */
330
331 while (*name == '/')
332 {
333 name++;
334 }
335
336 return name;
337 }
338