35,22 → 35,19 |
* @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; |
180,303 → 177,6 |
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(); |
} |
} |
|
/** |
* @} |
*/ |