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