source: mainline/uspace/srv/vfs/vfs_lookup.c@ 9bb85f3

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

Add canonify() for file system path canonization.
Not yet used by VFS.
  • Property mode set to 100644
File size: 10.1 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);
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 needn't be an ASCIIZ string.
61 * @param len Number of path characters pointed by path.
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, size_t len, int lflag,
71 vfs_lookup_res_t *result, vfs_pair_t *altroot)
72{
73 vfs_pair_t *root;
74
75 if (!len)
76 return EINVAL;
77
78 if (altroot)
79 root = altroot;
80 else
81 root = (vfs_pair_t *) &rootfs;
82
83 if (!root->fs_handle)
84 return ENOENT;
85
86 futex_down(&plb_futex);
87
88 plb_entry_t entry;
89 link_initialize(&entry.plb_link);
90 entry.len = len;
91
92 off_t first; /* the first free index */
93 off_t last; /* the last free index */
94
95 if (list_empty(&plb_head)) {
96 first = 0;
97 last = PLB_SIZE - 1;
98 } else {
99 plb_entry_t *oldest = list_get_instance(plb_head.next,
100 plb_entry_t, plb_link);
101 plb_entry_t *newest = list_get_instance(plb_head.prev,
102 plb_entry_t, plb_link);
103
104 first = (newest->index + newest->len) % PLB_SIZE;
105 last = (oldest->index - 1) % PLB_SIZE;
106 }
107
108 if (first <= last) {
109 if ((last - first) + 1 < len) {
110 /*
111 * The buffer cannot absorb the path.
112 */
113 futex_up(&plb_futex);
114 return ELIMIT;
115 }
116 } else {
117 if (PLB_SIZE - ((first - last) + 1) < len) {
118 /*
119 * The buffer cannot absorb the path.
120 */
121 futex_up(&plb_futex);
122 return ELIMIT;
123 }
124 }
125
126 /*
127 * We know the first free index in PLB and we also know that there is
128 * enough space in the buffer to hold our path.
129 */
130
131 entry.index = first;
132 entry.len = len;
133
134 /*
135 * Claim PLB space by inserting the entry into the PLB entry ring
136 * buffer.
137 */
138 list_append(&entry.plb_link, &plb_head);
139
140 futex_up(&plb_futex);
141
142 /*
143 * Copy the path into PLB.
144 */
145 size_t cnt1 = min(len, (PLB_SIZE - first) + 1);
146 size_t cnt2 = len - cnt1;
147
148 memcpy(&plb[first], path, cnt1);
149 memcpy(plb, &path[cnt1], cnt2);
150
151 ipc_call_t answer;
152 int phone = vfs_grab_phone(root->fs_handle);
153 aid_t req = async_send_4(phone, VFS_LOOKUP, (ipcarg_t) first,
154 (ipcarg_t) (first + len - 1) % PLB_SIZE,
155 (ipcarg_t) root->dev_handle, (ipcarg_t) lflag, &answer);
156 vfs_release_phone(phone);
157
158 ipcarg_t rc;
159 async_wait_for(req, &rc);
160
161 futex_down(&plb_futex);
162 list_remove(&entry.plb_link);
163 /*
164 * Erasing the path from PLB will come handy for debugging purposes.
165 */
166 memset(&plb[first], 0, cnt1);
167 memset(plb, 0, cnt2);
168 futex_up(&plb_futex);
169
170 if ((rc == EOK) && result) {
171 result->triplet.fs_handle = (int) IPC_GET_ARG1(answer);
172 result->triplet.dev_handle = (int) IPC_GET_ARG2(answer);
173 result->triplet.index = (int) IPC_GET_ARG3(answer);
174 result->size = (size_t) IPC_GET_ARG4(answer);
175 result->lnkcnt = (unsigned) IPC_GET_ARG5(answer);
176 }
177
178 return rc;
179}
180
181/** Token types used for tokenization of path. */
182typedef enum {
183 TK_INVALID,
184 TK_SLASH,
185 TK_DOT,
186 TK_DOTDOT,
187 TK_COMP,
188 TK_NUL
189} tokval_t;
190
191typedef struct {
192 tokval_t kind;
193 char *start;
194 char *stop;
195} token_t;
196
197/** Fake up the TK_SLASH token. */
198static token_t slash_token(char *start)
199{
200 token_t ret;
201 ret.kind = TK_SLASH;
202 ret.start = start;
203 ret.stop = start;
204 return ret;
205}
206
207/** Given a token, return the next token. */
208static token_t next_token(token_t *cur)
209{
210 token_t ret;
211
212 if (cur->stop[1] == '\0') {
213 ret.kind = TK_NUL;
214 ret.start = cur->stop + 1;
215 ret.stop = ret.start;
216 return ret;
217 }
218 if (cur->stop[1] == '/') {
219 ret.kind = TK_SLASH;
220 ret.start = cur->stop + 1;
221 ret.stop = ret.start;
222 return ret;
223 }
224 if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) {
225 ret.kind = TK_DOT;
226 ret.start = cur->stop + 1;
227 ret.stop = ret.start;
228 return ret;
229 }
230 if (cur->stop[1] == '.' && cur->stop[2] == '.' &&
231 (!cur->stop[3] || cur->stop[3] == '/')) {
232 ret.kind = TK_DOTDOT;
233 ret.start = cur->stop + 1;
234 ret.stop = cur->stop + 2;
235 return ret;
236 }
237 unsigned i;
238 for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++)
239 ;
240 ret.kind = TK_COMP;
241 ret.start = &cur->stop[1];
242 ret.stop = &cur->stop[i - 1];
243 return ret;
244}
245
246/** States used by canonify(). */
247typedef enum {
248 S_INI,
249 S_A,
250 S_B,
251 S_C,
252 S_ACCEPT,
253 S_RESTART,
254 S_REJECT
255} state_t;
256
257typedef struct {
258 state_t s;
259 void (* f)(token_t *, token_t *, token_t *);
260} change_state_t;
261
262/*
263 * Actions that can be performed when transitioning from one
264 * state of canonify() to another.
265 */
266static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
267{
268 *tfsl = *t;
269}
270static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
271{
272 *tlcomp = *t;
273}
274static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
275{
276 tfsl->stop[1] = '\0';
277}
278static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
279{
280 t->start[-1] = '\0';
281}
282/** Eat the extra '/'..
283 *
284 * @param t The current TK_SLASH token.
285 */
286static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
287{
288 char *p = t->start;
289 char *q = t->stop + 1;
290 while ((*p++ = *q++))
291 ;
292}
293/** Eat the extra '.'.
294 *
295 * @param t The current TK_DOT token.
296 */
297static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
298{
299 char *p = t->start;
300 char *q = t->stop + 1;
301 while ((*p++ = *q++))
302 ;
303}
304/** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern.
305 *
306 * @param t The current TK_DOTDOT token.
307 * @param tlcomp The last TK_COMP token.
308 */
309static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
310{
311 char *p = tlcomp->start;
312 char *q = t->stop + 1;
313 while ((*p++ = *q++))
314 ;
315}
316
317/** Transition function for canonify(). */
318static change_state_t trans[4][6] = {
319 [S_INI] = {
320 [TK_SLASH] = {
321 .s = S_A,
322 .f = set_first_slash,
323 },
324 [TK_DOT] = {
325 .s = S_REJECT,
326 .f = NULL,
327 },
328 [TK_DOTDOT] = {
329 .s = S_REJECT,
330 .f = NULL,
331 },
332 [TK_COMP] = {
333 .s = S_REJECT,
334 .f = NULL,
335 },
336 [TK_NUL] = {
337 .s = S_REJECT,
338 .f = NULL,
339 },
340 [TK_INVALID] = {
341 .s = S_REJECT,
342 .f = NULL,
343 },
344 },
345 [S_A] = {
346 [TK_SLASH] = {
347 .s = S_A,
348 .f = set_first_slash,
349 },
350 [TK_DOT] = {
351 .s = S_A,
352 .f = NULL,
353 },
354 [TK_DOTDOT] = {
355 .s = S_A,
356 .f = NULL,
357 },
358 [TK_COMP] = {
359 .s = S_B,
360 .f = save_component,
361 },
362 [TK_NUL] = {
363 .s = S_ACCEPT,
364 .f = terminate_slash,
365 },
366 [TK_INVALID] = {
367 .s = S_REJECT,
368 .f = NULL,
369 },
370 },
371 [S_B] = {
372 [TK_SLASH] = {
373 .s = S_C,
374 .f = NULL,
375 },
376 [TK_DOT] = {
377 .s = S_REJECT,
378 .f = NULL,
379 },
380 [TK_DOTDOT] = {
381 .s = S_REJECT,
382 .f = NULL,
383 },
384 [TK_COMP] = {
385 .s = S_REJECT,
386 .f = NULL,
387 },
388 [TK_NUL] = {
389 .s = S_ACCEPT,
390 .f = NULL,
391 },
392 [TK_INVALID] = {
393 .s = S_REJECT,
394 .f = NULL,
395 },
396 },
397 [S_C] = {
398 [TK_SLASH] = {
399 .s = S_RESTART,
400 .f = shift_slash,
401 },
402 [TK_DOT] = {
403 .s = S_RESTART,
404 .f = shift_dot,
405 },
406 [TK_DOTDOT] = {
407 .s = S_RESTART,
408 .f = shift_dotdot,
409 },
410 [TK_COMP] = {
411 .s = S_B,
412 .f = save_component,
413 },
414 [TK_NUL] = {
415 .s = S_ACCEPT,
416 .f = remove_trailing_slash,
417 },
418 [TK_INVALID] = {
419 .s = S_REJECT,
420 .f = NULL,
421 },
422 }
423};
424
425/** Canonify a file system path.
426 *
427 * A file system path is canonical, if the following holds:
428 * 1) the path is absolute (i.e. a/b/c is not canonical)
429 * 2) there is no trailing slash in the path (i.e. /a/b/c is not canonical)
430 * 3) there is no extra slash in the path (i.e. /a//b/c is not canonical)
431 * 4) there is no '.' component in the path (i.e. /a/./b/c is not canonical)
432 * 5) there is no '..' component in the path (i.e. /a/b/../c is not canonical)
433 *
434 * This function makes a potentially non-canonical file system path canonical.
435 * It works in-place and requires a NULL-terminated input string.
436 *
437 * @param Path to be canonified.
438 *
439 * @return Canonified path or NULL on failure.
440 */
441char *canonify(char *path)
442{
443 state_t state;
444 token_t t;
445 token_t tfsl; /* first slash */
446 token_t tlcomp; /* last component */
447 if (*path != '/')
448 return NULL;
449 tfsl = slash_token(path);
450restart:
451 state = S_INI;
452 t = tfsl;
453 while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
454 if (trans[state][t.kind].f)
455 trans[state][t.kind].f(&t, &tfsl, &tlcomp);
456 state = trans[state][t.kind].s;
457 t = next_token(&t);
458 }
459
460 switch (state) {
461 case S_RESTART:
462 goto restart;
463 case S_REJECT:
464 return NULL;
465 case S_ACCEPT:
466 return tfsl.start;
467 default:
468 abort();
469 }
470}
471
472/**
473 * @}
474 */
Note: See TracBrowser for help on using the repository browser.