Rev 2730 | Rev 2752 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2730 | Rev 2751 | ||
---|---|---|---|
Line 37... | Line 37... | ||
37 | 37 | ||
38 | #include <ipc/ipc.h> |
38 | #include <ipc/ipc.h> |
39 | #include <async.h> |
39 | #include <async.h> |
40 | #include <errno.h> |
40 | #include <errno.h> |
41 | #include <string.h> |
41 | #include <string.h> |
- | 42 | #include <stdlib.h> |
|
42 | #include <bool.h> |
43 | #include <bool.h> |
43 | #include <futex.h> |
44 | #include <futex.h> |
44 | #include <libadt/list.h> |
45 | #include <libadt/list.h> |
45 | #include <atomic.h> |
46 | #include <atomic.h> |
46 | #include "vfs.h" |
47 | #include "vfs.h" |
47 | 48 | ||
48 | #define min(a, b) ((a) < (b) ? (a) : (b)) |
49 | #define min(a, b) ((a) < (b) ? (a) : (b)) |
49 | 50 | ||
- | 51 | /* Forward static declarations. */ |
|
- | 52 | static char *canonify(char *path); |
|
- | 53 | ||
50 | atomic_t plb_futex = FUTEX_INITIALIZER; |
54 | atomic_t plb_futex = FUTEX_INITIALIZER; |
51 | link_t plb_head; /**< PLB entry ring buffer. */ |
55 | link_t plb_head; /**< PLB entry ring buffer. */ |
52 | uint8_t *plb = NULL; |
56 | uint8_t *plb = NULL; |
53 | 57 | ||
54 | /** Perform a path lookup. |
58 | /** Perform a path lookup. |
Line 172... | Line 176... | ||
172 | } |
176 | } |
173 | 177 | ||
174 | return rc; |
178 | return rc; |
175 | } |
179 | } |
176 | 180 | ||
- | 181 | /** Token types used for tokenization of path. */ |
|
- | 182 | typedef enum { |
|
- | 183 | TK_INVALID, |
|
- | 184 | TK_SLASH, |
|
- | 185 | TK_DOT, |
|
- | 186 | TK_DOTDOT, |
|
- | 187 | TK_COMP, |
|
- | 188 | TK_NUL |
|
- | 189 | } tokval_t; |
|
- | 190 | ||
- | 191 | typedef struct { |
|
- | 192 | tokval_t kind; |
|
- | 193 | char *start; |
|
- | 194 | char *stop; |
|
- | 195 | } token_t; |
|
- | 196 | ||
- | 197 | /** Fake up the TK_SLASH token. */ |
|
- | 198 | static token_t slash_token(char *start) |
|
- | 199 | { |
|
- | 200 | token_t ret; |
|
- | 201 | ret.kind = TK_SLASH; |
|
- | 202 | ret.start = start; |
|
- | 203 | ret.stop = start; |
|
- | 204 | return ret; |
|
- | 205 | } |
|
- | 206 | ||
- | 207 | /** Given a token, return the next token. */ |
|
- | 208 | static token_t next_token(token_t *cur) |
|
- | 209 | { |
|
- | 210 | token_t ret; |
|
- | 211 | ||
- | 212 | if (cur->stop[1] == '\0') { |
|
- | 213 | ret.kind = TK_NUL; |
|
- | 214 | ret.start = cur->stop + 1; |
|
- | 215 | ret.stop = ret.start; |
|
- | 216 | return ret; |
|
- | 217 | } |
|
- | 218 | if (cur->stop[1] == '/') { |
|
- | 219 | ret.kind = TK_SLASH; |
|
- | 220 | ret.start = cur->stop + 1; |
|
- | 221 | ret.stop = ret.start; |
|
- | 222 | return ret; |
|
- | 223 | } |
|
- | 224 | if (cur->stop[1] == '.' && (!cur->stop[2] || cur->stop[2] == '/')) { |
|
- | 225 | ret.kind = TK_DOT; |
|
- | 226 | ret.start = cur->stop + 1; |
|
- | 227 | ret.stop = ret.start; |
|
- | 228 | return ret; |
|
- | 229 | } |
|
- | 230 | if (cur->stop[1] == '.' && cur->stop[2] == '.' && |
|
- | 231 | (!cur->stop[3] || cur->stop[3] == '/')) { |
|
- | 232 | ret.kind = TK_DOTDOT; |
|
- | 233 | ret.start = cur->stop + 1; |
|
- | 234 | ret.stop = cur->stop + 2; |
|
- | 235 | return ret; |
|
- | 236 | } |
|
- | 237 | unsigned i; |
|
- | 238 | for (i = 1; cur->stop[i] && cur->stop[i] != '/'; i++) |
|
- | 239 | ; |
|
- | 240 | ret.kind = TK_COMP; |
|
- | 241 | ret.start = &cur->stop[1]; |
|
- | 242 | ret.stop = &cur->stop[i - 1]; |
|
- | 243 | return ret; |
|
- | 244 | } |
|
- | 245 | ||
- | 246 | /** States used by canonify(). */ |
|
- | 247 | typedef enum { |
|
- | 248 | S_INI, |
|
- | 249 | S_A, |
|
- | 250 | S_B, |
|
- | 251 | S_C, |
|
- | 252 | S_ACCEPT, |
|
- | 253 | S_RESTART, |
|
- | 254 | S_REJECT |
|
- | 255 | } state_t; |
|
- | 256 | ||
- | 257 | typedef struct { |
|
- | 258 | state_t s; |
|
- | 259 | void (* f)(token_t *, token_t *, token_t *); |
|
- | 260 | } change_state_t; |
|
- | 261 | ||
- | 262 | /* |
|
- | 263 | * Actions that can be performed when transitioning from one |
|
- | 264 | * state of canonify() to another. |
|
- | 265 | */ |
|
- | 266 | static void set_first_slash(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 267 | { |
|
- | 268 | *tfsl = *t; |
|
- | 269 | } |
|
- | 270 | static void save_component(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 271 | { |
|
- | 272 | *tlcomp = *t; |
|
- | 273 | } |
|
- | 274 | static void terminate_slash(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 275 | { |
|
- | 276 | tfsl->stop[1] = '\0'; |
|
- | 277 | } |
|
- | 278 | static void remove_trailing_slash(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 279 | { |
|
- | 280 | t->start[-1] = '\0'; |
|
- | 281 | } |
|
- | 282 | /** Eat the extra '/'.. |
|
- | 283 | * |
|
- | 284 | * @param t The current TK_SLASH token. |
|
- | 285 | */ |
|
- | 286 | static void shift_slash(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 287 | { |
|
- | 288 | char *p = t->start; |
|
- | 289 | char *q = t->stop + 1; |
|
- | 290 | while ((*p++ = *q++)) |
|
- | 291 | ; |
|
- | 292 | } |
|
- | 293 | /** Eat the extra '.'. |
|
- | 294 | * |
|
- | 295 | * @param t The current TK_DOT token. |
|
- | 296 | */ |
|
- | 297 | static void shift_dot(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 298 | { |
|
- | 299 | char *p = t->start; |
|
- | 300 | char *q = t->stop + 1; |
|
- | 301 | while ((*p++ = *q++)) |
|
- | 302 | ; |
|
- | 303 | } |
|
- | 304 | /** Collapse the TK_COMP TK_SLASH TK_DOTDOT pattern. |
|
- | 305 | * |
|
- | 306 | * @param t The current TK_DOTDOT token. |
|
- | 307 | * @param tlcomp The last TK_COMP token. |
|
- | 308 | */ |
|
- | 309 | static void shift_dotdot(token_t *t, token_t *tfsl, token_t *tlcomp) |
|
- | 310 | { |
|
- | 311 | char *p = tlcomp->start; |
|
- | 312 | char *q = t->stop + 1; |
|
- | 313 | while ((*p++ = *q++)) |
|
- | 314 | ; |
|
- | 315 | } |
|
- | 316 | ||
- | 317 | /** Transition function for canonify(). */ |
|
- | 318 | static change_state_t trans[4][6] = { |
|
- | 319 | [S_INI] = { |
|
- | 320 | [TK_SLASH] = { |
|
- | 321 | .s = S_A, |
|
- | 322 | .f = set_first_slash, |
|
- | 323 | }, |
|
- | 324 | [TK_DOT] = { |
|
- | 325 | .s = S_REJECT, |
|
- | 326 | .f = NULL, |
|
- | 327 | }, |
|
- | 328 | [TK_DOTDOT] = { |
|
- | 329 | .s = S_REJECT, |
|
- | 330 | .f = NULL, |
|
- | 331 | }, |
|
- | 332 | [TK_COMP] = { |
|
- | 333 | .s = S_REJECT, |
|
- | 334 | .f = NULL, |
|
- | 335 | }, |
|
- | 336 | [TK_NUL] = { |
|
- | 337 | .s = S_REJECT, |
|
- | 338 | .f = NULL, |
|
- | 339 | }, |
|
- | 340 | [TK_INVALID] = { |
|
- | 341 | .s = S_REJECT, |
|
- | 342 | .f = NULL, |
|
- | 343 | }, |
|
- | 344 | }, |
|
- | 345 | [S_A] = { |
|
- | 346 | [TK_SLASH] = { |
|
- | 347 | .s = S_A, |
|
- | 348 | .f = set_first_slash, |
|
- | 349 | }, |
|
- | 350 | [TK_DOT] = { |
|
- | 351 | .s = S_A, |
|
- | 352 | .f = NULL, |
|
- | 353 | }, |
|
- | 354 | [TK_DOTDOT] = { |
|
- | 355 | .s = S_A, |
|
- | 356 | .f = NULL, |
|
- | 357 | }, |
|
- | 358 | [TK_COMP] = { |
|
- | 359 | .s = S_B, |
|
- | 360 | .f = save_component, |
|
- | 361 | }, |
|
- | 362 | [TK_NUL] = { |
|
- | 363 | .s = S_ACCEPT, |
|
- | 364 | .f = terminate_slash, |
|
- | 365 | }, |
|
- | 366 | [TK_INVALID] = { |
|
- | 367 | .s = S_REJECT, |
|
- | 368 | .f = NULL, |
|
- | 369 | }, |
|
- | 370 | }, |
|
- | 371 | [S_B] = { |
|
- | 372 | [TK_SLASH] = { |
|
- | 373 | .s = S_C, |
|
- | 374 | .f = NULL, |
|
- | 375 | }, |
|
- | 376 | [TK_DOT] = { |
|
- | 377 | .s = S_REJECT, |
|
- | 378 | .f = NULL, |
|
- | 379 | }, |
|
- | 380 | [TK_DOTDOT] = { |
|
- | 381 | .s = S_REJECT, |
|
- | 382 | .f = NULL, |
|
- | 383 | }, |
|
- | 384 | [TK_COMP] = { |
|
- | 385 | .s = S_REJECT, |
|
- | 386 | .f = NULL, |
|
- | 387 | }, |
|
- | 388 | [TK_NUL] = { |
|
- | 389 | .s = S_ACCEPT, |
|
- | 390 | .f = NULL, |
|
- | 391 | }, |
|
- | 392 | [TK_INVALID] = { |
|
- | 393 | .s = S_REJECT, |
|
- | 394 | .f = NULL, |
|
- | 395 | }, |
|
- | 396 | }, |
|
- | 397 | [S_C] = { |
|
- | 398 | [TK_SLASH] = { |
|
- | 399 | .s = S_RESTART, |
|
- | 400 | .f = shift_slash, |
|
- | 401 | }, |
|
- | 402 | [TK_DOT] = { |
|
- | 403 | .s = S_RESTART, |
|
- | 404 | .f = shift_dot, |
|
- | 405 | }, |
|
- | 406 | [TK_DOTDOT] = { |
|
- | 407 | .s = S_RESTART, |
|
- | 408 | .f = shift_dotdot, |
|
- | 409 | }, |
|
- | 410 | [TK_COMP] = { |
|
- | 411 | .s = S_B, |
|
- | 412 | .f = save_component, |
|
- | 413 | }, |
|
- | 414 | [TK_NUL] = { |
|
- | 415 | .s = S_ACCEPT, |
|
- | 416 | .f = remove_trailing_slash, |
|
- | 417 | }, |
|
- | 418 | [TK_INVALID] = { |
|
- | 419 | .s = S_REJECT, |
|
- | 420 | .f = NULL, |
|
- | 421 | }, |
|
- | 422 | } |
|
- | 423 | }; |
|
- | 424 | ||
- | 425 | /** Canonify a file system path. |
|
- | 426 | * |
|
- | 427 | * A file system path is canonical, if the following holds: |
|
- | 428 | * 1) the path is absolute (i.e. a/b/c is not canonical) |
|
- | 429 | * 2) there is no trailing slash in the path (i.e. /a/b/c is not canonical) |
|
- | 430 | * 3) there is no extra slash in the path (i.e. /a//b/c is not canonical) |
|
- | 431 | * 4) there is no '.' component in the path (i.e. /a/./b/c is not canonical) |
|
- | 432 | * 5) there is no '..' component in the path (i.e. /a/b/../c is not canonical) |
|
- | 433 | * |
|
- | 434 | * This function makes a potentially non-canonical file system path canonical. |
|
- | 435 | * It works in-place and requires a NULL-terminated input string. |
|
- | 436 | * |
|
- | 437 | * @param Path to be canonified. |
|
- | 438 | * |
|
- | 439 | * @return Canonified path or NULL on failure. |
|
- | 440 | */ |
|
- | 441 | char *canonify(char *path) |
|
- | 442 | { |
|
- | 443 | state_t state; |
|
- | 444 | token_t t; |
|
- | 445 | token_t tfsl; /* first slash */ |
|
- | 446 | token_t tlcomp; /* last component */ |
|
- | 447 | if (*path != '/') |
|
- | 448 | return NULL; |
|
- | 449 | tfsl = slash_token(path); |
|
- | 450 | restart: |
|
- | 451 | state = S_INI; |
|
- | 452 | t = tfsl; |
|
- | 453 | while (state != S_ACCEPT && state != S_RESTART && state != S_REJECT) { |
|
- | 454 | if (trans[state][t.kind].f) |
|
- | 455 | trans[state][t.kind].f(&t, &tfsl, &tlcomp); |
|
- | 456 | state = trans[state][t.kind].s; |
|
- | 457 | t = next_token(&t); |
|
- | 458 | } |
|
- | 459 | ||
- | 460 | switch (state) { |
|
- | 461 | case S_RESTART: |
|
- | 462 | goto restart; |
|
- | 463 | case S_REJECT: |
|
- | 464 | return NULL; |
|
- | 465 | case S_ACCEPT: |
|
- | 466 | return tfsl.start; |
|
- | 467 | default: |
|
- | 468 | abort(); |
|
- | 469 | } |
|
- | 470 | } |
|
- | 471 | ||
177 | /** |
472 | /** |
178 | * @} |
473 | * @} |
179 | */ |
474 | */ |