WebSVN – HelenOS – Diff – /trunk/uspace/srv/vfs/vfs_lookup.c

 /*
  * Copyright (c) 2008 Jakub Jermar
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
+ *
  * - Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
  * - Redistributions in binary form must reproduce the above copyright
  *   notice, this list of conditions and the following disclaimer in the
  *   documentation and/or other materials provided with the distribution.
  * - The name of the author may not be used to endorse or promote products
  *   derived from this software without specific prior written permission.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 /** @addtogroup fs
  * @{
  */
 /**
  * @file    vfs_lookup.c
  * @brief
  */
+#include "vfs.h"
 #include <ipc/ipc.h>
 #include <async.h>
 #include <errno.h>
 #include <string.h>
-#include <stdlib.h>
 #include <bool.h>
 #include <futex.h>
 #include <libadt/list.h>
 #include <atomic.h>
-#include "vfs.h"
+#include <vfs/canonify.h>
 #define min(a, b)   ((a) < (b) ? (a) : (b))
-/* Forward static declarations. */
-static char *canonify(char *path, size_t *lenp);
 atomic_t plb_futex = FUTEX_INITIALIZER;
 link_t plb_head;    /**< PLB entry ring buffer. */
 uint8_t *plb = NULL;
 /** Perform a path lookup.
+ *
  * @param path      Path to be resolved; it must be a NULL-terminated
  *          string.
  * @param lflag     Flags to be used during lookup.
  * @param result    Empty structure where the lookup result will be stored.
  *          Can be NULL.
  * @param altroot   If non-empty, will be used instead of rootfs as the root
  *          of the whole VFS tree.
+ *
  * @return      EOK on success or an error code from errno.h.
  */
 int vfs_lookup_internal(char *path, int lflag, vfs_lookup_res_t *result,
     vfs_pair_t *altroot)
+{
     vfs_pair_t *root;
     if (altroot)
         root = altroot;
     else
         root = (vfs_pair_t *) &rootfs;
     if (!root->fs_handle)
         return ENOENT;
     size_t len;
     path = canonify(path, &len);
     if (!path)
         return EINVAL;
     futex_down(&plb_futex);
     plb_entry_t entry;
     link_initialize(&entry.plb_link);
     entry.len = len;
     off_t first;    /* the first free index */
     off_t last; /* the last free index */
     if (list_empty(&plb_head)) {
         first = 0;
         last = PLB_SIZE - 1;
     } else {
         plb_entry_t *oldest = list_get_instance(plb_head.next,
             plb_entry_t, plb_link);
         plb_entry_t *newest = list_get_instance(plb_head.prev,
             plb_entry_t, plb_link);
         first = (newest->index + newest->len) % PLB_SIZE;
         last = (oldest->index - 1) % PLB_SIZE;
+    }
     if (first <= last) {
         if ((last - first) + 1 < len) {
             /*
              * The buffer cannot absorb the path.
              */
             futex_up(&plb_futex);
             return ELIMIT;
+        }
     } else {
         if (PLB_SIZE - ((first - last) + 1) < len) {
             /*
              * The buffer cannot absorb the path.
              */
             futex_up(&plb_futex);
             return ELIMIT;
+        }
+    }
     /*
      * We know the first free index in PLB and we also know that there is
      * enough space in the buffer to hold our path.
      */
     entry.index = first;
     entry.len = len;
     /*
      * Claim PLB space by inserting the entry into the PLB entry ring
      * buffer.
      */
     list_append(&entry.plb_link, &plb_head);
     futex_up(&plb_futex);
     /*
      * Copy the path into PLB.
      */
     size_t cnt1 = min(len, (PLB_SIZE - first) + 1);
     size_t cnt2 = len - cnt1;
     memcpy(&plb[first], path, cnt1);
     memcpy(plb, &path[cnt1], cnt2);
     ipc_call_t answer;
     int phone = vfs_grab_phone(root->fs_handle);
     aid_t req = async_send_4(phone, VFS_LOOKUP, (ipcarg_t) first,
         (ipcarg_t) (first + len - 1) % PLB_SIZE,
         (ipcarg_t) root->dev_handle, (ipcarg_t) lflag, &answer);
     vfs_release_phone(phone);
     ipcarg_t rc;
     async_wait_for(req, &rc);
     futex_down(&plb_futex);
     list_remove(&entry.plb_link);
     /*
      * Erasing the path from PLB will come handy for debugging purposes.
      */
     memset(&plb[first], 0, cnt1);
     memset(plb, 0, cnt2);
     futex_up(&plb_futex);
     if ((rc == EOK) && result) {
         result->triplet.fs_handle = (int) IPC_GET_ARG1(answer);
         result->triplet.dev_handle = (int) IPC_GET_ARG2(answer);
         result->triplet.index = (int) IPC_GET_ARG3(answer);
         result->size = (size_t) IPC_GET_ARG4(answer);
         result->lnkcnt = (unsigned) IPC_GET_ARG5(answer);
+    }
     return rc;
+}
-/** Token types used for tokenization of path. */
-typedef enum {
-    TK_INVALID,
-    TK_SLASH,
-    TK_DOT,
-    TK_DOTDOT,
-    TK_COMP,
-    TK_NUL
-} tokval_t;
-typedef struct {
-    tokval_t kind;
-    char *start;
-    char *stop;
-} token_t;
-/** Fake up the TK_SLASH token. */
-static token_t slash_token(char *start)
-{
-    token_t ret;
-    ret.kind = TK_SLASH;
-    ret.start = start;
-    ret.stop = start;
-    return ret;
-}
-/** Given a token, return the next token. */
-static token_t next_token(token_t *cur)
-{
-    token_t ret;
-    if (cur->stop[1] == '\0') {
-        ret.kind = TK_NUL;
-        ret.start = cur->stop + 1;
-        ret.stop = ret.start;
-        return ret;
-    }
-    if (cur->stop[1] == '/') {
-        ret.kind = TK_SLASH;
-        ret.start = cur->stop + 1;
-        ret.stop = ret.start;
-        return ret;
-    }
-    if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) {
-        ret.kind = TK_DOT;
-        ret.start = cur->stop + 1;
-        ret.stop = ret.start;
-        return ret;
-    }
-    if (cur->stop[1] == '.' && cur->stop[2] == '.' &&
-        (!cur->stop[3] || cur->stop[3] == '/')) {
-        ret.kind = TK_DOTDOT;
-        ret.start = cur->stop + 1;
-        ret.stop = cur->stop + 2;
-        return ret;
-    }
-    unsigned i;
-    for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++)
-        ;
-    ret.kind = TK_COMP;
-    ret.start = &cur->stop[1];
-    ret.stop = &cur->stop[i - 1];
-    return ret;
-}
-/** States used by canonify(). */
-typedef enum {
-    S_INI,
-    S_A,
-    S_B,
-    S_C,
-    S_ACCEPT,
-    S_RESTART,
-    S_REJECT
-} state_t;
-typedef struct {
-    state_t s;
-    void (* f)(token_t *, token_t *, token_t *);
-} change_state_t;
-/*
- * Actions that can be performed when transitioning from one
- * state of canonify() to another.
- */
-static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    *tfsl = *t;
-}
-static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    *tlcomp = *t;
-}
-static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    if (tfsl->stop[1])  /* avoid writing to a well-formatted path */
-        tfsl->stop[1] = '\0';
-}
-static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    t->start[-1] = '\0';
-}
-/** Eat the extra '/'..
- *
- * @param t     The current TK_SLASH token.
- */
-static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    char *p = t->start;
-    char *q = t->stop + 1;
-    while ((*p++ = *q++))
-        ;
-}
-/** Eat the extra '.'.
- *
- * @param t     The current TK_DOT token.
- */
-static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    char *p = t->start;
-    char *q = t->stop + 1;
-    while ((*p++ = *q++))
-        ;
-}
-/** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern.
- *
- * @param t     The current TK_DOTDOT token.
- * @param tlcomp    The last TK_COMP token.
- */
-static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp)
-{
-    char *p = tlcomp->start;
-    char *q = t->stop + 1;
-    while ((*p++ = *q++))
-        ;
-}
-/** Transition function for canonify(). */
-static change_state_t trans[4][6] = {
-    [S_INI] = {
-        [TK_SLASH] = {
-            .s = S_A,
-            .f = set_first_slash,
-        },
-        [TK_DOT] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_DOTDOT] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_COMP] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_NUL] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_INVALID] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-    },
-    [S_A] = {
-        [TK_SLASH] = {
-            .s = S_A,
-            .f = set_first_slash,
-        },
-        [TK_DOT] = {
-            .s = S_A,
-            .f = NULL,
-        },
-        [TK_DOTDOT] = {
-            .s = S_A,
-            .f = NULL,
-        },
-        [TK_COMP] = {
-            .s = S_B,
-            .f = save_component,
-        },
-        [TK_NUL] = {
-            .s = S_ACCEPT,
-            .f = terminate_slash,
-        },
-        [TK_INVALID] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-    },
-    [S_B] = {
-        [TK_SLASH] = {
-            .s = S_C,
-            .f = NULL,
-        },
-        [TK_DOT] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_DOTDOT] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_COMP] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-        [TK_NUL] = {
-            .s = S_ACCEPT,
-            .f = NULL,
-        },
-        [TK_INVALID] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-    },
-    [S_C] = {
-        [TK_SLASH] = {
-            .s = S_RESTART,
-            .f = shift_slash,
-        },
-        [TK_DOT] = {
-            .s = S_RESTART,
-            .f = shift_dot,
-        },
-        [TK_DOTDOT] = {
-            .s = S_RESTART,
-            .f = shift_dotdot,
-        },
-        [TK_COMP] = {
-            .s = S_B,
-            .f = save_component,
-        },
-        [TK_NUL] = {
-            .s = S_ACCEPT,
-            .f = remove_trailing_slash,
-        },
-        [TK_INVALID] = {
-            .s = S_REJECT,
-            .f = NULL,
-        },
-    }
-};
-/** Canonify a file system path.
- *
- * A file system path is canonical, if the following holds:
- * 1) the path is absolute (i.e. a/b/c is not canonical)
- * 2) there is no trailing slash in the path (i.e. /a/b/c is not canonical)
- * 3) there is no extra slash in the path (i.e. /a//b/c is not canonical)
- * 4) there is no '.' component in the path (i.e. /a/./b/c is not canonical)
- * 5) there is no '..' component in the path (i.e. /a/b/../c is not canonical)
- *
- * This function makes a potentially non-canonical file system path canonical.
- * It works in-place and requires a NULL-terminated input string.
- *
- * @param path      Path to be canonified.
- * @param lenp      Pointer where the length of the final path will be
- *          stored. Can be NULL.
- *
- * @return      Canonified path or NULL on failure.
- */
-char *canonify(char *path, size_t *lenp)
-{
-    state_t state;
-    token_t t;
-    token_t tfsl;       /* first slash */
-    token_t tlcomp;     /* last component */
-    if (*path != '/')
-        return NULL;
-    tfsl = slash_token(path);
-restart:
-    state = S_INI;
-    t = tfsl;
-    tlcomp = tfsl;
-    while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) {
-        if (trans[state][t.kind].f)
-            trans[state][t.kind].f(&t, &tfsl, &tlcomp);
-        state = trans[state][t.kind].s;
-        t = next_token(&t);
-    }
-    switch (state) {
-    case S_RESTART:
-        goto restart;
-    case S_REJECT:
-        return NULL;
-    case S_ACCEPT:
-        if (lenp)
-            *lenp = (size_t)((tlcomp.stop - tfsl.start) + 1);
-        return tfsl.start;
-    default:
-        abort();
-    }
-}
 /**
  * @}
  */

Subversion Repositories HelenOS

(root)/trunk/uspace/srv/vfs/vfs_lookup.c – Rev 2752 → 2753