/*
* 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 <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"
#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.
*/
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:
}
}
/**
* @}
*/