libexfat/lookup.c

   1 /*
   2  *  lookup.c
   3  *  exFAT file system implementation library.
   4  *
   5  *  Created by Andrew Nayenko on 02.09.09.
   6  *  This software is distributed under the GNU General Public License
   7  *  version 3 or any later.
   8  */
   9
  10 #include "exfat.h"
  11 #include <string.h>
  12 #include <errno.h>
  13 #include <inttypes.h>
  14
  15 void exfat_opendir(struct exfat_node* node, struct exfat_iterator* it)
  16 {
  17         if (!(node->flags & EXFAT_ATTRIB_DIR))
  18                 exfat_bug("`%s' is not a directory", node->name);
  19         it->cluster = node->start_cluster;
  20         it->offset = 0;
  21         it->contiguous = IS_CONTIGUOUS(*node);
  22         it->chunk = NULL;
  23 }
  24
  25 void exfat_closedir(struct exfat_iterator* it)
  26 {
  27         it->cluster = 0;
  28         it->offset = 0;
  29         it->contiguous = 0;
  30         free(it->chunk);
  31         it->chunk = NULL;
  32 }
  33
  34 /*
  35  * Reads one entry in directory at position pointed by iterator and fills
  36  * node structure.
  37  */
  38 int exfat_readdir(struct exfat* ef, struct exfat_node* node,
  39                 struct exfat_iterator* it)
  40 {
  41         const struct exfat_entry* entry;
  42         const struct exfat_file* file;
  43         const struct exfat_file_info* file_info;
  44         const struct exfat_file_name* file_name;
  45         const struct exfat_upcase* upcase;
  46         const struct exfat_bitmap* bitmap;
  47         uint8_t continuations = 0;
  48         le16_t* namep = NULL;
  49
  50         if (it->chunk == NULL)
  51         {
  52                 it->chunk = malloc(CLUSTER_SIZE(*ef->sb));
  53                 if (it->chunk == NULL)
  54                 {
  55                         exfat_error("out of memory");
  56                         return -ENOMEM;
  57                 }
  58                 exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
  59                                 exfat_c2o(ef, it->cluster), ef->fd);
  60         }
  61
  62         for (;;)
  63         {
  64                 /* every directory (even empty one) occupies at least one cluster and
  65                    must contain EOD entry */
  66                 entry = (const struct exfat_entry*)
  67                                 (it->chunk + it->offset % CLUSTER_SIZE(*ef->sb));
  68                 /* move iterator to the next entry in the directory */
  69                 it->offset += sizeof(struct exfat_entry);
  70
  71                 switch (entry->type)
  72                 {
  73                 case EXFAT_ENTRY_EOD:
  74                         if (continuations != 0)
  75                         {
  76                                 exfat_error("expected %hhu continuations before EOD",
  77                                                 continuations);
  78                                 return -EIO;
  79                         }
  80                         return -ENOENT; /* that's OK, means end of directory */
  81
  82                 case EXFAT_ENTRY_FILE:
  83                         if (continuations != 0)
  84                         {
  85                                 exfat_error("expected %hhu continuations before new entry",
  86                                                 continuations);
  87                                 return -EIO;
  88                         }
  89                         memset(node, 0, sizeof(struct exfat_node));
  90                         file = (const struct exfat_file*) entry;
  91                         node->flags = le16_to_cpu(file->attrib);
  92                         node->mtime = exfat_exfat2unix(file->mdate, file->mtime);
  93                         node->atime = exfat_exfat2unix(file->adate, file->atime);
  94                         namep = node->name;
  95                         continuations = file->continuations;
  96                         /* each file entry must have at least 2 continuations:
  97                            info and name */
  98                         if (continuations < 2)
  99                         {
 100                                 exfat_error("too few continuations (%hhu)", continuations);
 101                                 return -EIO;
 102                         }
 103                         break;
 104
 105                 case EXFAT_ENTRY_FILE_INFO:
 106                         if (continuations < 2)
 107                         {
 108                                 exfat_error("unexpected continuation (%hhu)",
 109                                                 continuations);
 110                                 return -EIO;
 111                         }
 112                         file_info = (const struct exfat_file_info*) entry;
 113                         node->size = le64_to_cpu(file_info->size);
 114                         node->start_cluster = le32_to_cpu(file_info->start_cluster);
 115                         if (file_info->flag == EXFAT_FLAG_CONTIGUOUS)
 116                                 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
 117                         --continuations;
 118                         break;
 119
 120                 case EXFAT_ENTRY_FILE_NAME:
 121                         if (continuations == 0)
 122                         {
 123                                 exfat_error("unexpected continuation");
 124                                 return -EIO;
 125                         }
 126                         file_name = (const struct exfat_file_name*) entry;
 127                         memcpy(namep, file_name->name, EXFAT_ENAME_MAX * sizeof(le16_t));
 128                         namep += EXFAT_ENAME_MAX;
 129                         if (--continuations == 0)
 130                                 return 0; /* entry completed */
 131                         break;
 132
 133                 case EXFAT_ENTRY_UPCASE:
 134                         if (ef->upcase != NULL)
 135                                 break;
 136                         upcase = (const struct exfat_upcase*) entry;
 137                         if (CLUSTER_INVALID(le32_to_cpu(upcase->start_cluster)))
 138                         {
 139                                 exfat_error("invalid cluster in upcase table");
 140                                 return -EIO;
 141                         }
 142                         if (le64_to_cpu(upcase->size) == 0 ||
 143                                 le64_to_cpu(upcase->size) > 0xffff * sizeof(uint16_t) ||
 144                                 le64_to_cpu(upcase->size) % sizeof(uint16_t) != 0)
 145                         {
 146                                 exfat_error("bad upcase table size (%"PRIu64" bytes)",
 147                                                 le64_to_cpu(upcase->size));
 148                                 return -EIO;
 149                         }
 150                         ef->upcase = malloc(le64_to_cpu(upcase->size));
 151                         if (ef->upcase == NULL)
 152                         {
 153                                 exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
 154                                                 le64_to_cpu(upcase->size));
 155                                 return -ENOMEM;
 156                         }
 157                         ef->upcase_chars = le64_to_cpu(upcase->size) / sizeof(le16_t);
 158
 159                         exfat_read_raw(ef->upcase, le64_to_cpu(upcase->size),
 160                                         exfat_c2o(ef, le32_to_cpu(upcase->start_cluster)), ef->fd);
 161                         break;
 162
 163                 case EXFAT_ENTRY_BITMAP:
 164                         bitmap = (const struct exfat_bitmap*) entry;
 165                         if (CLUSTER_INVALID(le32_to_cpu(bitmap->start_cluster)))
 166                         {
 167                                 exfat_error("invalid cluster in clusters bitmap");
 168                                 return -EIO;
 169                         }
 170                         if (le64_to_cpu(bitmap->size) !=
 171                                         ((le32_to_cpu(ef->sb->cluster_count) + 7) / 8))
 172                         {
 173                                 exfat_error("invalid bitmap size: %"PRIu64" (expected %u)",
 174                                                 le64_to_cpu(bitmap->size),
 175                                                 (le32_to_cpu(ef->sb->cluster_count) + 7) / 8);
 176                                 return -EIO;
 177                         }
 178                         break;
 179                 }
 180
 181                 /* fetch the next cluster if needed */
 182                 if ((it->offset & (CLUSTER_SIZE(*ef->sb) - 1)) == 0)
 183                 {
 184                         it->cluster = exfat_next_cluster(ef, it->cluster, it->contiguous);
 185                         if (CLUSTER_INVALID(it->cluster))
 186                         {
 187                                 exfat_error("invalid cluster while reading directory");
 188                                 return -EIO;
 189                         }
 190                         exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
 191                                         exfat_c2o(ef, it->cluster), ef->fd);
 192                 }
 193         }
 194         /* we never reach here */
 195 }
 196
 197 static int compare_char(struct exfat* ef, uint16_t a, uint16_t b)
 198 {
 199         if (a >= ef->upcase_chars || b >= ef->upcase_chars)
 200                 return a - b;
 201         else
 202                 return le16_to_cpu(ef->upcase[a]) - le16_to_cpu(ef->upcase[b]);
 203 }
 204
 205 static int compare_name(struct exfat* ef, const le16_t* a, const le16_t* b)
 206 {
 207         while (le16_to_cpu(*a) && le16_to_cpu(*b))
 208         {
 209                 if (compare_char(ef, le16_to_cpu(*a), le16_to_cpu(*b)) != 0)
 210                         break;
 211                 a++;
 212                 b++;
 213         }
 214         return le16_to_cpu(*a) - le16_to_cpu(*b);
 215 }
 216
 217 static int lookup_name(struct exfat* ef, struct exfat_node* node,
 218                 const le16_t* name)
 219 {
 220         struct exfat_iterator it;
 221
 222         exfat_opendir(node, &it);
 223         while (exfat_readdir(ef, node, &it) == 0)
 224         {
 225                 if (compare_name(ef, name, node->name) == 0)
 226                 {
 227                         exfat_closedir(&it);
 228                         return 0;
 229                 }
 230         }
 231         exfat_closedir(&it);
 232         return -ENOENT;
 233 }
 234
 235 int exfat_lookup(struct exfat* ef, struct exfat_node* node,
 236                 const char* path)
 237 {
 238         le16_t buffer[EXFAT_NAME_MAX + 1];
 239         int rc;
 240         le16_t* p;
 241         le16_t* subpath;
 242
 243         if (strlen(path) > EXFAT_NAME_MAX)
 244         {
 245                 exfat_error("file name `%s' is too long", path);
 246                 return -ENAMETOOLONG;
 247         }
 248
 249         rc = utf8_to_utf16(buffer, path, EXFAT_NAME_MAX, strlen(path));
 250         if (rc != 0)
 251                 return rc;
 252
 253         /* start from the root directory */
 254         node->flags = EXFAT_ATTRIB_DIR;
 255         node->size = 0;
 256         node->start_cluster = le32_to_cpu(ef->sb->rootdir_cluster);
 257         node->name[0] = cpu_to_le16('\0');
 258         /* exFAT does not have time attributes for the root directory */
 259         node->mtime = ef->mount_time;
 260         node->atime = ef->mount_time;
 261
 262         for (subpath = p = buffer; p; subpath = p + 1)
 263         {
 264                 while (le16_to_cpu(*subpath) == '/')
 265                         subpath++;              /* skip leading slashes */
 266                 for (p = subpath; ; p++)
 267                 {
 268                         if (le16_to_cpu(*p) == '\0')
 269                         {
 270                                 p = NULL;
 271                                 break;
 272                         }
 273                         if (le16_to_cpu(*p) == '/')
 274                         {
 275                                 *p = cpu_to_le16('\0');
 276                                 break;
 277                         }
 278                 }
 279                 if (le16_to_cpu(*subpath) == '\0')
 280                         break;                  /* skip trailing slashes */
 281                 if (le16_to_cpu(subpath[0]) == '.' && le16_to_cpu(subpath[1]) == '\0')
 282                         continue;               /* skip "." component */
 283                 if (lookup_name(ef, node, subpath) != 0)
 284                         return -ENOENT;
 285         }
 286         return 0;
 287 }