/*
- * lookup.c
- * exFAT file system implementation library.
- *
- * Created by Andrew Nayenko on 02.09.09.
- * This software is distributed under the GNU General Public License
- * version 3 or any later.
- */
+ lookup.c (02.09.09)
+ exFAT file system implementation library.
+
+ Copyright (C) 2009, 2010 Andrew Nayenko
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
#include "exfat.h"
#include <string.h>
#include <errno.h>
#include <inttypes.h>
-void exfat_opendir(struct exfat_node* node, struct exfat_iterator* it)
+int exfat_opendir(struct exfat* ef, struct exfat_node* dir,
+ struct exfat_iterator* it)
{
- if (!(node->flags & EXFAT_ATTRIB_DIR))
- exfat_bug("`%s' is not a directory", node->name);
- it->cluster = node->start_cluster;
- it->offset = 0;
- it->contiguous = IS_CONTIGUOUS(*node);
- it->chunk = NULL;
+ int rc;
+
+ exfat_get_node(dir);
+ it->parent = dir;
+ it->current = NULL;
+ rc = exfat_cache_directory(ef, dir);
+ if (rc != 0)
+ exfat_put_node(ef, dir);
+ return rc;
}
-void exfat_closedir(struct exfat_iterator* it)
+void exfat_closedir(struct exfat* ef, struct exfat_iterator* it)
{
- it->cluster = 0;
- it->offset = 0;
- it->contiguous = 0;
- free(it->chunk);
- it->chunk = NULL;
+ exfat_put_node(ef, it->parent);
+ it->parent = NULL;
+ it->current = NULL;
}
-/*
- * Reads one entry in directory at position pointed by iterator and fills
- * node structure.
- */
-int exfat_readdir(struct exfat* ef, struct exfat_node* node,
- struct exfat_iterator* it)
+struct exfat_node* exfat_readdir(struct exfat* ef, struct exfat_iterator* it)
{
- const struct exfat_entry* entry;
- const struct exfat_file* file;
- const struct exfat_file_info* file_info;
- const struct exfat_file_name* file_name;
- const struct exfat_upcase* upcase;
- const struct exfat_bitmap* bitmap;
- uint8_t continuations = 0;
- le16_t* namep = NULL;
-
- if (it->chunk == NULL)
- {
- it->chunk = malloc(CLUSTER_SIZE(*ef->sb));
- if (it->chunk == NULL)
- {
- exfat_error("out of memory");
- return -ENOMEM;
- }
- exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
- exfat_c2o(ef, it->cluster), ef->fd);
- }
-
- for (;;)
- {
- /* every directory (even empty one) occupies at least one cluster and
- must contain EOD entry */
- entry = (const struct exfat_entry*)
- (it->chunk + it->offset % CLUSTER_SIZE(*ef->sb));
- /* move iterator to the next entry in the directory */
- it->offset += sizeof(struct exfat_entry);
-
- switch (entry->type)
- {
- case EXFAT_ENTRY_EOD:
- if (continuations != 0)
- {
- exfat_error("expected %hhu continuations before EOD",
- continuations);
- return -EIO;
- }
- return -ENOENT; /* that's OK, means end of directory */
-
- case EXFAT_ENTRY_FILE:
- if (continuations != 0)
- {
- exfat_error("expected %hhu continuations before new entry",
- continuations);
- return -EIO;
- }
- memset(node, 0, sizeof(struct exfat_node));
- file = (const struct exfat_file*) entry;
- node->flags = le16_to_cpu(file->attrib);
- node->mtime = exfat_exfat2unix(file->mdate, file->mtime);
- node->atime = exfat_exfat2unix(file->adate, file->atime);
- namep = node->name;
- continuations = file->continuations;
- /* each file entry must have at least 2 continuations:
- info and name */
- if (continuations < 2)
- {
- exfat_error("too few continuations (%hhu)", continuations);
- return -EIO;
- }
- break;
-
- case EXFAT_ENTRY_FILE_INFO:
- if (continuations < 2)
- {
- exfat_error("unexpected continuation (%hhu)",
- continuations);
- return -EIO;
- }
- file_info = (const struct exfat_file_info*) entry;
- node->size = le64_to_cpu(file_info->size);
- node->start_cluster = le32_to_cpu(file_info->start_cluster);
- if (file_info->flag == EXFAT_FLAG_CONTIGUOUS)
- node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
- --continuations;
- break;
-
- case EXFAT_ENTRY_FILE_NAME:
- if (continuations == 0)
- {
- exfat_error("unexpected continuation");
- return -EIO;
- }
- file_name = (const struct exfat_file_name*) entry;
- memcpy(namep, file_name->name, EXFAT_ENAME_MAX * sizeof(le16_t));
- namep += EXFAT_ENAME_MAX;
- if (--continuations == 0)
- return 0; /* entry completed */
- break;
-
- case EXFAT_ENTRY_UPCASE:
- if (ef->upcase != NULL)
- break;
- upcase = (const struct exfat_upcase*) entry;
- if (CLUSTER_INVALID(le32_to_cpu(upcase->start_cluster)))
- {
- exfat_error("invalid cluster in upcase table");
- return -EIO;
- }
- if (le64_to_cpu(upcase->size) == 0 ||
- le64_to_cpu(upcase->size) > 0xffff * sizeof(uint16_t) ||
- le64_to_cpu(upcase->size) % sizeof(uint16_t) != 0)
- {
- exfat_error("bad upcase table size (%"PRIu64" bytes)",
- le64_to_cpu(upcase->size));
- return -EIO;
- }
- ef->upcase = malloc(le64_to_cpu(upcase->size));
- if (ef->upcase == NULL)
- {
- exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
- le64_to_cpu(upcase->size));
- return -ENOMEM;
- }
- ef->upcase_chars = le64_to_cpu(upcase->size) / sizeof(le16_t);
-
- exfat_read_raw(ef->upcase, le64_to_cpu(upcase->size),
- exfat_c2o(ef, le32_to_cpu(upcase->start_cluster)), ef->fd);
- break;
-
- case EXFAT_ENTRY_BITMAP:
- bitmap = (const struct exfat_bitmap*) entry;
- if (CLUSTER_INVALID(le32_to_cpu(bitmap->start_cluster)))
- {
- exfat_error("invalid cluster in clusters bitmap");
- return -EIO;
- }
- if (le64_to_cpu(bitmap->size) !=
- ((le32_to_cpu(ef->sb->cluster_count) + 7) / 8))
- {
- exfat_error("invalid bitmap size: %"PRIu64" (expected %u)",
- le64_to_cpu(bitmap->size),
- (le32_to_cpu(ef->sb->cluster_count) + 7) / 8);
- return -EIO;
- }
- break;
- }
+ if (it->current == NULL)
+ it->current = it->parent->child;
+ else
+ it->current = it->current->next;
- /* fetch the next cluster if needed */
- if ((it->offset & (CLUSTER_SIZE(*ef->sb) - 1)) == 0)
- {
- it->cluster = exfat_next_cluster(ef, it->cluster, it->contiguous);
- if (CLUSTER_INVALID(it->cluster))
- {
- exfat_error("invalid cluster while reading directory");
- return -EIO;
- }
- exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
- exfat_c2o(ef, it->cluster), ef->fd);
- }
- }
- /* we never reach here */
+ if (it->current != NULL)
+ return exfat_get_node(it->current);
+ else
+ return NULL;
}
static int compare_char(struct exfat* ef, uint16_t a, uint16_t b)
{
if (a >= ef->upcase_chars || b >= ef->upcase_chars)
- return a - b;
- else
- return le16_to_cpu(ef->upcase[a]) - le16_to_cpu(ef->upcase[b]);
+ return (int) a - (int) b;
+
+ return (int) le16_to_cpu(ef->upcase[a]) - (int) le16_to_cpu(ef->upcase[b]);
}
static int compare_name(struct exfat* ef, const le16_t* a, const le16_t* b)
{
while (le16_to_cpu(*a) && le16_to_cpu(*b))
{
- if (compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b)) != 0)
- break;
+ int rc = compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b));
+ if (rc != 0)
+ return rc;
a++;
b++;
}
- return le16_to_cpu(*a) - le16_to_cpu(*b);
+ return compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b));
}
-static int lookup_name(struct exfat* ef, struct exfat_node* node,
- const le16_t* name)
+static int lookup_name(struct exfat* ef, struct exfat_node* parent,
+ struct exfat_node** node, const char* name, size_t n)
{
struct exfat_iterator it;
+ le16_t buffer[EXFAT_NAME_MAX + 1];
+ int rc;
+
+ *node = NULL;
+
+ rc = utf8_to_utf16(buffer, name, EXFAT_NAME_MAX, n);
+ if (rc != 0)
+ return rc;
- exfat_opendir(node, &it);
- while (exfat_readdir(ef, node, &it) == 0)
+ rc = exfat_opendir(ef, parent, &it);
+ if (rc != 0)
+ return rc;
+ while ((*node = exfat_readdir(ef, &it)))
{
- if (compare_name(ef, name, node->name) == 0)
+ if (compare_name(ef, buffer, (*node)->name) == 0)
{
- exfat_closedir(&it);
+ exfat_closedir(ef, &it);
return 0;
}
+ exfat_put_node(ef, *node);
}
- exfat_closedir(&it);
+ exfat_closedir(ef, &it);
return -ENOENT;
}
-int exfat_lookup(struct exfat* ef, struct exfat_node* node,
+static size_t get_comp(const char* path, const char** comp)
+{
+ const char* end;
+
+ *comp = path + strspn(path, "/"); /* skip leading slashes */
+ end = strchr(*comp, '/');
+ if (end == NULL)
+ return strlen(*comp);
+ else
+ return end - *comp;
+}
+
+int exfat_lookup(struct exfat* ef, struct exfat_node** node,
const char* path)
{
- le16_t buffer[EXFAT_NAME_MAX + 1];
- int rc;
- le16_t* p;
- le16_t* subpath;
+ struct exfat_node* parent;
+ const char* p;
+ size_t n;
- if (strlen(path) > EXFAT_NAME_MAX)
+ /* start from the root directory */
+ parent = *node = exfat_get_node(ef->root);
+ for (p = path; (n = get_comp(p, &p)); p += n)
{
- exfat_error("file name `%s' is too long", path);
- return -ENAMETOOLONG;
+ if (n == 1 && *p == '.') /* skip "." component */
+ continue;
+ if (lookup_name(ef, parent, node, p, n) != 0)
+ {
+ exfat_put_node(ef, parent);
+ return -ENOENT;
+ }
+ exfat_put_node(ef, parent);
+ parent = *node;
}
+ return 0;
+}
- rc = utf8_to_utf16(buffer, path, EXFAT_NAME_MAX, strlen(path));
- if (rc != 0)
- return rc;
+static int is_last_comp(const char* comp, size_t length)
+{
+ const char* p = comp + length;
- /* start from the root directory */
- node->flags = EXFAT_ATTRIB_DIR;
- node->size = 0;
- node->start_cluster = le32_to_cpu(ef->sb->rootdir_cluster);
- node->name[0] = cpu_to_le16('\0');
- /* exFAT does not have time attributes for the root directory */
- node->mtime = ef->mount_time;
- node->atime = ef->mount_time;
+ return get_comp(p, &p) == 0;
+}
- for (subpath = p = buffer; p; subpath = p + 1)
+static int is_allowed(const char* comp, size_t length)
+{
+ return strcspn(comp, "/\\:*?\"<>|") >= length;
+}
+
+int exfat_split(struct exfat* ef, struct exfat_node** parent,
+ struct exfat_node** node, le16_t* name, const char* path)
+{
+ const char* p;
+ size_t n;
+
+ *parent = *node = exfat_get_node(ef->root);
+ for (p = path; (n = get_comp(p, &p)); p += n)
{
- while (le16_to_cpu(*subpath) == '/')
- subpath++; /* skip leading slashes */
- for (p = subpath; ; p++)
+ if (n == 1 && *p == '.')
+ continue;
+ if (is_last_comp(p, n))
{
- if (le16_to_cpu(*p) == '\0')
+ int rc;
+
+ if (!is_allowed(p, n))
{
- p = NULL;
- break;
+ /* contains characters that are not allowed */
+ exfat_put_node(ef, *parent);
+ return -ENOENT;
}
- if (le16_to_cpu(*p) == '/')
+ rc = utf8_to_utf16(name, p, EXFAT_NAME_MAX, n);
+ if (rc != 0)
{
- *p = cpu_to_le16('\0');
- break;
+ exfat_put_node(ef, *parent);
+ return rc;
}
+
+ rc = lookup_name(ef, *parent, node, p, n);
+ if (rc != 0 && rc != -ENOENT)
+ {
+ exfat_put_node(ef, *parent);
+ return rc;
+ }
+ return 0;
}
- if (le16_to_cpu(*subpath) == '\0')
- break; /* skip trailing slashes */
- if (le16_to_cpu(subpath[0]) == '.' && le16_to_cpu(subpath[1]) == '\0')
- continue; /* skip "." component */
- if (lookup_name(ef, node, subpath) != 0)
+ if (lookup_name(ef, *parent, node, p, n) != 0)
+ {
+ exfat_put_node(ef, *parent);
return -ENOENT;
+ }
+ exfat_put_node(ef, *parent);
+ *parent = *node;
}
- return 0;
+ exfat_bug("impossible");
}