Index: uspace/srv/vfs/vfs_lookup.c =================================================================== --- uspace/srv/vfs/vfs_lookup.c (revision ee68e4bc4d0b10815e4ef17fd625a9a33dd1242d) +++ uspace/srv/vfs/vfs_lookup.c (revision 9bb85f3480d8697d332ae4f46dabcd45bc5ab0c5) @@ -40,4 +40,5 @@ #include #include +#include #include #include @@ -47,4 +48,7 @@ #define min(a, b) ((a) < (b) ? (a) : (b)) + +/* Forward static declarations. */ +static char *canonify(char *path); atomic_t plb_futex = FUTEX_INITIALIZER; @@ -175,5 +179,296 @@ } +/** 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(); + } +} + /** * @} - */ + */