Subversion Repositories HelenOS

Rev

Rev 2752 | Rev 2763 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2752 Rev 2753
Line 33... Line 33...
33 
/**
 33 
/**
34 
 * @file    vfs_lookup.c
 34 
 * @file    vfs_lookup.c
35 
 * @brief
 35 
 * @brief
36 
 */
 36 
 */
37 
 
 37 
 
- 
 
 38 
#include "vfs.h"
38 
#include <ipc/ipc.h>
 39 
#include <ipc/ipc.h>
39 
#include <async.h>
 40 
#include <async.h>
40 
#include <errno.h>
 41 
#include <errno.h>
41 
#include <string.h>
 42 
#include <string.h>
42 
#include <stdlib.h>
 - 
 
43 
#include <bool.h>
 43 
#include <bool.h>
44 
#include <futex.h>
 44 
#include <futex.h>
45 
#include <libadt/list.h>
 45 
#include <libadt/list.h>
46 
#include <atomic.h>
 46 
#include <atomic.h>
47 
#include "vfs.h"
 47 
#include <vfs/canonify.h>
48 
 
 48 
 
49 
#define min(a, b)   ((a) < (b) ? (a) : (b))
 49 
#define min(a, b)   ((a) < (b) ? (a) : (b))
50 
 
 50 
 
51 
/* Forward static declarations. */
 - 
 
52 
static char *canonify(char *path, size_t *lenp);
 - 
 
53 
 
 - 
 
54 
atomic_t plb_futex = FUTEX_INITIALIZER;
 51 
atomic_t plb_futex = FUTEX_INITIALIZER;
55 
link_t plb_head;    /**< PLB entry ring buffer. */
 52 
link_t plb_head;    /**< PLB entry ring buffer. */
56 
uint8_t *plb = NULL;
 53 
uint8_t *plb = NULL;
57 
 
 54 
 
58 
/** Perform a path lookup.
 55 
/** Perform a path lookup.
Line 178... Line 175...
178 
    }
 175 
    }
179 
 
 176 
 
180 
    return rc;
 177 
    return rc;
181 
}
 178 
}
182 
 
 179 
 
183 
/** Token types used for tokenization of path. */
 - 
 
184 
typedef enum {
 - 
 
185 
    TK_INVALID,
 - 
 
186 
    TK_SLASH,
 - 
 
187 
    TK_DOT,
 - 
 
188 
    TK_DOTDOT,
 - 
 
189 
    TK_COMP,
 - 
 
190 
    TK_NUL
 - 
 
191 
} tokval_t;
 - 
 
192 
 
 - 
 
193 
typedef struct {
 - 
 
194 
    tokval_t kind;
 - 
 
195 
    char *start;
 - 
 
196 
    char *stop;
 - 
 
197 
} token_t;
 - 
 
198 
 
 - 
 
199 
/** Fake up the TK_SLASH token. */
 - 
 
200 
static 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. */
 - 
 
210 
static 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(). */
 - 
 
249 
typedef 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 
 
 - 
 
259 
typedef 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 
 */
 - 
 
268 
static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
 - 
 
269 
{
 - 
 
270 
    *tfsl = *t;
 - 
 
271 
}
 - 
 
272 
static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
 - 
 
273 
{
 - 
 
274 
    *tlcomp = *t;
 - 
 
275 
}
 - 
 
276 
static 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 
}
 - 
 
281 
static 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 
 */
 - 
 
289 
static 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 
 */
 - 
 
300 
static 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 
 */
 - 
 
312 
static 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(). */
 - 
 
321 
static 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 
 */
 - 
 
446 
char *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);
 - 
 
455 
restart:
 - 
 
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 
/**
 180 
/**
481 
 * @}
 181 
 * @}
482 
 */
 182 
 */