source: mainline/uspace/srv/vfs/vfs_lookup.c@ d6084ef

lfn serial ticket/834-toolchain-update topic/fix-logger-deadlock topic/msim-upgrade topic/simplify-dev-export
Last change on this file since d6084ef was d6084ef, checked in by Jakub Jermar <jakub@…>, 18 years ago

Make VFS canonify path names on lookup.
  • Property mode set to 100644
File size: 10.4 KB
Line 
1/*
2 * Copyright (c) 2008 Jakub Jermar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup fs
30 * @{
31 */
32
33/**
34 * @file vfs_lookup.c
35 * @brief
36 */
37
38#include <ipc/ipc.h>
39#include <async.h>
40#include <errno.h>
41#include <string.h>
42#include <stdlib.h>
43#include <bool.h>
44#include <futex.h>
45#include <libadt/list.h>
46#include <atomic.h>
47#include "vfs.h"
48
49#define min(a, b) ((a) < (b) ? (a) : (b))
50
51/* Forward static declarations. */
52static char *canonify(char *path, size_t *lenp);
53
54atomic_t plb_futex = FUTEX_INITIALIZER;
55link_t plb_head; /**< PLB entry ring buffer. */
56uint8_t *plb = NULL;
57
58/** Perform a path lookup.
59 *
60 * @param path Path to be resolved; it must be a NULL-terminated
61 * string.
62 * @param lflag Flags to be used during lookup.
63 * @param result Empty structure where the lookup result will be stored.
64 * Can be NULL.
65 * @param altroot If non-empty, will be used instead of rootfs as the root
66 * of the whole VFS tree.
67 *
68 * @return EOK on success or an error code from errno.h.
69 */
70int vfs_lookup_internal(char *path, int lflag, vfs_lookup_res_t *result,
71 vfs_pair_t *altroot)
72{
73 vfs_pair_t *root;
74
75 if (altroot)
76 root = altroot;
77 else
78 root = (vfs_pair_t *) &rootfs;
79
80 if (!root->fs_handle)
81 return ENOENT;
82
83 size_t len;
84 path = canonify(path, &len);
85 if (!path)
86 return EINVAL;
87
88 futex_down(&plb_futex);
89
90 plb_entry_t entry;
91 link_initialize(&entry.plb_link);
92 entry.len = len;
93
94 off_t first; /* the first free index */
95 off_t last; /* the last free index */
96
97 if (list_empty(&plb_head)) {
98 first = 0;
99 last = PLB_SIZE - 1;
100 } else {
101 plb_entry_t *oldest = list_get_instance(plb_head.next,
102 plb_entry_t, plb_link);
103 plb_entry_t *newest = list_get_instance(plb_head.prev,
104 plb_entry_t, plb_link);
105
106 first = (newest->index + newest->len) % PLB_SIZE;
107 last = (oldest->index - 1) % PLB_SIZE;
108 }
109
110 if (first <= last) {
111 if ((last - first) + 1 < len) {
112 /*
113 * The buffer cannot absorb the path.
114 */
115 futex_up(&plb_futex);
116 return ELIMIT;
117 }
118 } else {
119 if (PLB_SIZE - ((first - last) + 1) < len) {
120 /*
121 * The buffer cannot absorb the path.
122 */
123 futex_up(&plb_futex);
124 return ELIMIT;
125 }
126 }
127
128 /*
129 * We know the first free index in PLB and we also know that there is
130 * enough space in the buffer to hold our path.
131 */
132
133 entry.index = first;
134 entry.len = len;
135
136 /*
137 * Claim PLB space by inserting the entry into the PLB entry ring
138 * buffer.
139 */
140 list_append(&entry.plb_link, &plb_head);
141
142 futex_up(&plb_futex);
143
144 /*
145 * Copy the path into PLB.
146 */
147 size_t cnt1 = min(len, (PLB_SIZE - first) + 1);
148 size_t cnt2 = len - cnt1;
149
150 memcpy(&plb[first], path, cnt1);
151 memcpy(plb, &path[cnt1], cnt2);
152
153 ipc_call_t answer;
154 int phone = vfs_grab_phone(root->fs_handle);
155 aid_t req = async_send_4(phone, VFS_LOOKUP, (ipcarg_t) first,
156 (ipcarg_t) (first + len - 1) % PLB_SIZE,
157 (ipcarg_t) root->dev_handle, (ipcarg_t) lflag, &answer);
158 vfs_release_phone(phone);
159
160 ipcarg_t rc;
161 async_wait_for(req, &rc);
162
163 futex_down(&plb_futex);
164 list_remove(&entry.plb_link);
165 /*
166 * Erasing the path from PLB will come handy for debugging purposes.
167 */
168 memset(&plb[first], 0, cnt1);
169 memset(plb, 0, cnt2);
170 futex_up(&plb_futex);
171
172 if ((rc == EOK) && result) {
173 result->triplet.fs_handle = (int) IPC_GET_ARG1(answer);
174 result->triplet.dev_handle = (int) IPC_GET_ARG2(answer);
175 result->triplet.index = (int) IPC_GET_ARG3(answer);
176 result->size = (size_t) IPC_GET_ARG4(answer);
177 result->lnkcnt = (unsigned) IPC_GET_ARG5(answer);
178 }
179
180 return rc;
181}
182
183/** Token types used for tokenization of path. */
184typedef enum {
185 TK_INVALID,
186 TK_SLASH,
187 TK_DOT,
188 TK_DOTDOT,
189 TK_COMP,
190 TK_NUL
191} tokval_t;
192
193typedef struct {
194 tokval_t kind;
195 char *start;
196 char *stop;
197} token_t;
198
199/** Fake up the TK_SLASH token. */
200static token_t slash_token(char *start)
201{
202 token_t ret;
203 ret.kind = TK_SLASH;
204 ret.start = start;
205 ret.stop = start;
206 return ret;
207}
208
209/** Given a token, return the next token. */
210static token_t next_token(token_t *cur)
211{
212 token_t ret;
213
214 if (cur->stop[1] == '\0') {
215 ret.kind = TK_NUL;
216 ret.start = cur->stop + 1;
217 ret.stop = ret.start;
218 return ret;
219 }
220 if (cur->stop[1] == '/') {
221 ret.kind = TK_SLASH;
222 ret.start = cur->stop + 1;
223 ret.stop = ret.start;
224 return ret;
225 }
226 if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) {
227 ret.kind = TK_DOT;
228 ret.start = cur->stop + 1;
229 ret.stop = ret.start;
230 return ret;
231 }
232 if (cur->stop[1] == '.' && cur->stop[2] == '.' &&
233 (!cur->stop[3] || cur->stop[3] == '/')) {
234 ret.kind = TK_DOTDOT;
235 ret.start = cur->stop + 1;
236 ret.stop = cur->stop + 2;
237 return ret;
238 }
239 unsigned i;
240 for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++)
241 ;
242 ret.kind = TK_COMP;
243 ret.start = &cur->stop[1];
244 ret.stop = &cur->stop[i - 1];
245 return ret;
246}
247
248/** States used by canonify(). */
249typedef enum {
250 S_INI,
251 S_A,
252 S_B,
253 S_C,
254 S_ACCEPT,
255 S_RESTART,
256 S_REJECT
257} state_t;
258
259typedef struct {
260 state_t s;
261 void (* f)(token_t *, token_t *, token_t *);
262} change_state_t;
263
264/*
265 * Actions that can be performed when transitioning from one
266 * state of canonify() to another.
267 */
268static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
269{
270 *tfsl = *t;
271}
272static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
273{
274 *tlcomp = *t;
275}
276static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
277{
278 if (tfsl->stop[1]) /* avoid writing to a well-formatted path */
279 tfsl->stop[1] = '\0';
280}
281static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
282{
283 t->start[-1] = '\0';
284}
285/** Eat the extra '/'..
286 *
287 * @param t The current TK_SLASH token.
288 */
289static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
290{
291 char *p = t->start;
292 char *q = t->stop + 1;
293 while ((*p++ = *q++))
294 ;
295}
296/** Eat the extra '.'.
297 *
298 * @param t The current TK_DOT token.
299 */
300static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
301{
302 char *p = t->start;
303 char *q = t->stop + 1;
304 while ((*p++ = *q++))
305 ;
306}
307/** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern.
308 *
309 * @param t The current TK_DOTDOT token.
310 * @param tlcomp The last TK_COMP token.
311 */
312static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
313{
314 char *p = tlcomp->start;
315 char *q = t->stop + 1;
316 while ((*p++ = *q++))
317 ;
318}
319
320/** Transition function for canonify(). */
321static change_state_t trans[4][6] = {
322 [S_INI] = {
323 [TK_SLASH] = {
324 .s = S_A,
325 .f = set_first_slash,
326 },
327 [TK_DOT] = {
328 .s = S_REJECT,
329 .f = NULL,
330 },
331 [TK_DOTDOT] = {
332 .s = S_REJECT,
333 .f = NULL,
334 },
335 [TK_COMP] = {
336 .s = S_REJECT,
337 .f = NULL,
338 },
339 [TK_NUL] = {
340 .s = S_REJECT,
341 .f = NULL,
342 },
343 [TK_INVALID] = {
344 .s = S_REJECT,
345 .f = NULL,
346 },
347 },
348 [S_A] = {
349 [TK_SLASH] = {
350 .s = S_A,
351 .f = set_first_slash,
352 },
353 [TK_DOT] = {
354 .s = S_A,
355 .f = NULL,
356 },
357 [TK_DOTDOT] = {
358 .s = S_A,
359 .f = NULL,
360 },
361 [TK_COMP] = {
362 .s = S_B,
363 .f = save_component,
364 },
365 [TK_NUL] = {
366 .s = S_ACCEPT,
367 .f = terminate_slash,
368 },
369 [TK_INVALID] = {
370 .s = S_REJECT,
371 .f = NULL,
372 },
373 },
374 [S_B] = {
375 [TK_SLASH] = {
376 .s = S_C,
377 .f = NULL,
378 },
379 [TK_DOT] = {
380 .s = S_REJECT,
381 .f = NULL,
382 },
383 [TK_DOTDOT] = {
384 .s = S_REJECT,
385 .f = NULL,
386 },
387 [TK_COMP] = {
388 .s = S_REJECT,
389 .f = NULL,
390 },
391 [TK_NUL] = {
392 .s = S_ACCEPT,
393 .f = NULL,
394 },
395 [TK_INVALID] = {
396 .s = S_REJECT,
397 .f = NULL,
398 },
399 },
400 [S_C] = {
401 [TK_SLASH] = {
402 .s = S_RESTART,
403 .f = shift_slash,
404 },
405 [TK_DOT] = {
406 .s = S_RESTART,
407 .f = shift_dot,
408 },
409 [TK_DOTDOT] = {
410 .s = S_RESTART,
411 .f = shift_dotdot,
412 },
413 [TK_COMP] = {
414 .s = S_B,
415 .f = save_component,
416 },
417 [TK_NUL] = {
418 .s = S_ACCEPT,
419 .f = remove_trailing_slash,
420 },
421 [TK_INVALID] = {
422 .s = S_REJECT,
423 .f = NULL,
424 },
425 }
426};
427
428/** Canonify a file system path.
429 *
430 * A file system path is canonical, if the following holds:
431 * 1) the path is absolute (i.e. a/b/c is not canonical)
432 * 2) there is no trailing slash in the path (i.e. /a/b/c is not canonical)
433 * 3) there is no extra slash in the path (i.e. /a//b/c is not canonical)
434 * 4) there is no '.' component in the path (i.e. /a/./b/c is not canonical)
435 * 5) there is no '..' component in the path (i.e. /a/b/../c is not canonical)
436 *
437 * This function makes a potentially non-canonical file system path canonical.
438 * It works in-place and requires a NULL-terminated input string.
439 *
440 * @param path Path to be canonified.
441 * @param lenp Pointer where the length of the final path will be
442 * stored. Can be NULL.
443 *
444 * @return Canonified path or NULL on failure.
445 */
446char *canonify(char *path, size_t *lenp)
447{
448 state_t state;
449 token_t t;
450 token_t tfsl; /* first slash */
451 token_t tlcomp; /* last component */
452 if (*path != '/')
453 return NULL;
454 tfsl = slash_token(path);
455restart:
456 state = S_INI;
457 t = tfsl;
458 tlcomp = tfsl;
459 while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
460 if (trans[state][t.kind].f)
461 trans[state][t.kind].f(&t, &tfsl, &tlcomp);
462 state = trans[state][t.kind].s;
463 t = next_token(&t);
464 }
465
466 switch (state) {
467 case S_RESTART:
468 goto restart;
469 case S_REJECT:
470 return NULL;
471 case S_ACCEPT:
472 if (lenp)
473 *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
474 return tfsl.start;
475 default:
476 abort();
477 }
478}
479
480/**
481 * @}
482 */
Note: See TracBrowser for help on using the repository browser.