Changeset 9bb85f3 in mainline

Timestamp:

2008-03-01T17:02:17Z (16 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

d6084ef

Parents:

1e50f81

Message:

Add canonify() for file system path canonization.
Not yet used by VFS.

Location:

uspace

Files:

• lib/libfs/libfs.c (modified) (1 diff)
• srv/vfs/vfs_lookup.c (modified) (3 diffs)

uspace/lib/libfs/libfs.c

@@ -124 +124 @@
 
 /** Lookup VFS triplet by name in the file system name space.
+ *
+ * The path passed in the PLB must be in the canonical file system path format
+ * as returned by the canonify() function.
  *
  * @param ops           libfs operations structure with function pointers to

uspace/srv/vfs/vfs_lookup.c

@@ -40 +40 @@
 #include <errno.h>
 #include <string.h>
+#include <stdlib.h>
 #include <bool.h>
 #include <futex.h>
@@ -47 +48 @@
 
 #define min(a, b)       ((a) < (b) ? (a) : (b))
+
+/* Forward static declarations. */
+static char *canonify(char *path);
 
 atomic_t plb_futex = FUTEX_INITIALIZER;
@@ -175 +179 @@
 }
 
+/** 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)
+{
+        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 to be canonified.
+ *
+ * @return              Canonified path or NULL on failure.
+ */
+char *canonify(char *path)
+{
+        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;
+        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:
+                return tfsl.start; 
+        default:
+                abort();
+        }
+}
+
 /**
  * @}
- */ 
+ */