libexfat/node.c

   1 /*
   2  *  node.c
   3  *  exFAT file system implementation library.
   4  *
   5  *  Created by Andrew Nayenko on 09.10.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 <errno.h>
  12 #include <string.h>
  13 #include <inttypes.h>
  14
  15 /* on-disk nodes iterator */
  16 struct iterator
  17 {
  18         cluster_t cluster;
  19         off_t offset;
  20         int contiguous;
  21         char* chunk;
  22 };
  23
  24 struct exfat_node* exfat_get_node(struct exfat_node* node)
  25 {
  26         /* if we switch to multi-threaded mode we will need atomic
  27            increment here and atomic decrement in exfat_put_node() */
  28         node->references++;
  29         return node;
  30 }
  31
  32 void exfat_put_node(struct exfat* ef, struct exfat_node* node)
  33 {
  34         if (--node->references < 0)
  35         {
  36                 char buffer[EXFAT_NAME_MAX + 1];
  37                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
  38                 exfat_bug("reference counter of `%s' is below zero", buffer);
  39         }
  40
  41         if (node->references == 0)
  42         {
  43                 if (node->flags & EXFAT_ATTRIB_DIRTY)
  44                         exfat_flush_node(ef, node);
  45                 if (ef->cmap.dirty)
  46                         exfat_flush_cmap(ef);
  47         }
  48 }
  49
  50 static void opendir(const struct exfat_node* dir, struct iterator* it)
  51 {
  52         if (!(dir->flags & EXFAT_ATTRIB_DIR))
  53                 exfat_bug("`%s' is not a directory", dir->name);
  54         it->cluster = dir->start_cluster;
  55         it->offset = 0;
  56         it->contiguous = IS_CONTIGUOUS(*dir);
  57         it->chunk = NULL;
  58 }
  59
  60 static void closedir(struct iterator* it)
  61 {
  62         it->cluster = 0;
  63         it->offset = 0;
  64         it->contiguous = 0;
  65         free(it->chunk);
  66         it->chunk = NULL;
  67 }
  68
  69 static int fetch_next_entry(struct exfat* ef, const struct exfat_node* parent,
  70                 struct iterator* it)
  71 {
  72         /* move iterator to the next entry in the directory */
  73         it->offset += sizeof(struct exfat_entry);
  74         /* fetch the next cluster if needed */
  75         if ((it->offset & (CLUSTER_SIZE(*ef->sb) - 1)) == 0)
  76         {
  77                 it->cluster = exfat_next_cluster(ef, parent, it->cluster);
  78                 if (CLUSTER_INVALID(it->cluster))
  79                 {
  80                         exfat_error("invalid cluster while reading directory");
  81                         return 1;
  82                 }
  83                 exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
  84                                 exfat_c2o(ef, it->cluster), ef->fd);
  85         }
  86         return 0;
  87 }
  88
  89 /*
  90  * Reads one entry in directory at position pointed by iterator and fills
  91  * node structure.
  92  */
  93 static int readdir(struct exfat* ef, const struct exfat_node* parent,
  94                 struct exfat_node** node, struct iterator* it)
  95 {
  96         const struct exfat_entry* entry;
  97         const struct exfat_file* file;
  98         const struct exfat_file_info* file_info;
  99         const struct exfat_file_name* file_name;
 100         const struct exfat_upcase* upcase;
 101         const struct exfat_bitmap* bitmap;
 102         const struct exfat_label* label;
 103         uint8_t continuations = 0;
 104         le16_t* namep = NULL;
 105         uint16_t reference_checksum = 0;
 106         uint16_t actual_checksum = 0;
 107
 108         *node = NULL;
 109
 110         if (it->chunk == NULL)
 111         {
 112                 it->chunk = malloc(CLUSTER_SIZE(*ef->sb));
 113                 if (it->chunk == NULL)
 114                 {
 115                         exfat_error("out of memory");
 116                         return -ENOMEM;
 117                 }
 118                 exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
 119                                 exfat_c2o(ef, it->cluster), ef->fd);
 120         }
 121
 122         for (;;)
 123         {
 124                 /* every directory (even empty one) occupies at least one cluster and
 125                    must contain EOD entry */
 126                 entry = (const struct exfat_entry*)
 127                                 (it->chunk + it->offset % CLUSTER_SIZE(*ef->sb));
 128
 129                 switch (entry->type)
 130                 {
 131                 case EXFAT_ENTRY_EOD:
 132                         if (continuations != 0)
 133                         {
 134                                 exfat_error("expected %hhu continuations before EOD",
 135                                                 continuations);
 136                                 goto error;
 137                         }
 138                         return -ENOENT; /* that's OK, means end of directory */
 139
 140                 case EXFAT_ENTRY_FILE:
 141                         if (continuations != 0)
 142                         {
 143                                 exfat_error("expected %hhu continuations before new entry",
 144                                                 continuations);
 145                                 goto error;
 146                         }
 147                         file = (const struct exfat_file*) entry;
 148                         continuations = file->continuations;
 149                         /* each file entry must have at least 2 continuations:
 150                            info and name */
 151                         if (continuations < 2)
 152                         {
 153                                 exfat_error("too few continuations (%hhu)", continuations);
 154                                 return -EIO;
 155                         }
 156                         reference_checksum = le16_to_cpu(file->checksum);
 157                         actual_checksum = exfat_start_checksum(file);
 158                         *node = malloc(sizeof(struct exfat_node));
 159                         if (*node == NULL)
 160                         {
 161                                 exfat_error("failed to allocate node");
 162                                 return -ENOMEM;
 163                         }
 164                         memset(*node, 0, sizeof(struct exfat_node));
 165                         /* new node has zero reference counter */
 166                         (*node)->entry_cluster = it->cluster;
 167                         (*node)->entry_offset = it->offset % CLUSTER_SIZE(*ef->sb);
 168                         (*node)->flags = le16_to_cpu(file->attrib);
 169                         (*node)->mtime = exfat_exfat2unix(file->mdate, file->mtime);
 170                         (*node)->atime = exfat_exfat2unix(file->adate, file->atime);
 171                         namep = (*node)->name;
 172                         break;
 173
 174                 case EXFAT_ENTRY_FILE_INFO:
 175                         if (continuations < 2)
 176                         {
 177                                 exfat_error("unexpected continuation (%hhu)",
 178                                                 continuations);
 179                                 goto error;
 180                         }
 181                         file_info = (const struct exfat_file_info*) entry;
 182                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
 183                         (*node)->size = le64_to_cpu(file_info->size);
 184                         /* directories must be aligned on at cluster boundary */
 185                         if (((*node)->flags & EXFAT_ATTRIB_DIR) &&
 186                                 (*node)->size % CLUSTER_SIZE(*ef->sb) != 0)
 187                         {
 188                                 char buffer[EXFAT_NAME_MAX + 1];
 189
 190                                 exfat_get_name(*node, buffer, EXFAT_NAME_MAX);
 191                                 exfat_error("directory `%s' has invalid size %"PRIu64" bytes",
 192                                                 buffer, (*node)->size);
 193                                 goto error;
 194                         }
 195                         (*node)->start_cluster = le32_to_cpu(file_info->start_cluster);
 196                         (*node)->fptr_cluster = (*node)->start_cluster;
 197                         if (file_info->flag == EXFAT_FLAG_CONTIGUOUS)
 198                                 (*node)->flags |= EXFAT_ATTRIB_CONTIGUOUS;
 199                         --continuations;
 200                         break;
 201
 202                 case EXFAT_ENTRY_FILE_NAME:
 203                         if (continuations == 0)
 204                         {
 205                                 exfat_error("unexpected continuation");
 206                                 goto error;
 207                         }
 208                         file_name = (const struct exfat_file_name*) entry;
 209                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
 210
 211                         memcpy(namep, file_name->name, EXFAT_ENAME_MAX * sizeof(le16_t));
 212                         namep += EXFAT_ENAME_MAX;
 213                         if (--continuations == 0)
 214                         {
 215                                 if (actual_checksum != reference_checksum)
 216                                 {
 217                                         exfat_error("invalid checksum (0x%hx != 0x%hx)",
 218                                                         actual_checksum, reference_checksum);
 219                                         return -EIO;
 220                                 }
 221                                 if (fetch_next_entry(ef, parent, it) != 0)
 222                                         goto error;
 223                                 return 0; /* entry completed */
 224                         }
 225                         break;
 226
 227                 case EXFAT_ENTRY_UPCASE:
 228                         if (ef->upcase != NULL)
 229                                 break;
 230                         upcase = (const struct exfat_upcase*) entry;
 231                         if (CLUSTER_INVALID(le32_to_cpu(upcase->start_cluster)))
 232                         {
 233                                 exfat_error("invalid cluster in upcase table");
 234                                 return -EIO;
 235                         }
 236                         if (le64_to_cpu(upcase->size) == 0 ||
 237                                 le64_to_cpu(upcase->size) > 0xffff * sizeof(uint16_t) ||
 238                                 le64_to_cpu(upcase->size) % sizeof(uint16_t) != 0)
 239                         {
 240                                 exfat_error("bad upcase table size (%"PRIu64" bytes)",
 241                                                 le64_to_cpu(upcase->size));
 242                                 return -EIO;
 243                         }
 244                         ef->upcase = malloc(le64_to_cpu(upcase->size));
 245                         if (ef->upcase == NULL)
 246                         {
 247                                 exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
 248                                                 le64_to_cpu(upcase->size));
 249                                 return -ENOMEM;
 250                         }
 251                         ef->upcase_chars = le64_to_cpu(upcase->size) / sizeof(le16_t);
 252
 253                         exfat_read_raw(ef->upcase, le64_to_cpu(upcase->size),
 254                                         exfat_c2o(ef, le32_to_cpu(upcase->start_cluster)), ef->fd);
 255                         break;
 256
 257                 case EXFAT_ENTRY_BITMAP:
 258                         bitmap = (const struct exfat_bitmap*) entry;
 259                         if (CLUSTER_INVALID(le32_to_cpu(bitmap->start_cluster)))
 260                         {
 261                                 exfat_error("invalid cluster in clusters bitmap");
 262                                 return -EIO;
 263                         }
 264                         ef->cmap.size = le32_to_cpu(ef->sb->cluster_count) -
 265                                 EXFAT_FIRST_DATA_CLUSTER;
 266                         if (le64_to_cpu(bitmap->size) != (ef->cmap.size + 7) / 8)
 267                         {
 268                                 exfat_error("invalid bitmap size: %"PRIu64" (expected %u)",
 269                                                 le64_to_cpu(bitmap->size), (ef->cmap.size + 7) / 8);
 270                                 return -EIO;
 271                         }
 272                         ef->cmap.start_cluster = le32_to_cpu(bitmap->start_cluster);
 273                         /* FIXME bitmap can be rather big, up to 512 MB */
 274                         ef->cmap.chunk_size = ef->cmap.size;
 275                         ef->cmap.chunk = malloc(le64_to_cpu(bitmap->size));
 276                         if (ef->cmap.chunk == NULL)
 277                         {
 278                                 exfat_error("failed to allocate clusters map chunk "
 279                                                 "(%"PRIu64" bytes)", le64_to_cpu(bitmap->size));
 280                                 return -ENOMEM;
 281                         }
 282
 283                         exfat_read_raw(ef->cmap.chunk, le64_to_cpu(bitmap->size),
 284                                         exfat_c2o(ef, ef->cmap.start_cluster), ef->fd);
 285                         break;
 286
 287                 case EXFAT_ENTRY_LABEL:
 288                         label = (const struct exfat_label*) entry;
 289                         if (label->length > EXFAT_ENAME_MAX)
 290                         {
 291                                 exfat_error("too long label (%hhu chars)", label->length);
 292                                 return -EIO;
 293                         }
 294                         break;
 295
 296                 default:
 297                         if (entry->type & EXFAT_ENTRY_VALID)
 298                         {
 299                                 exfat_error("unknown entry type 0x%hhu", entry->type);
 300                                 goto error;
 301                         }
 302                         break;
 303                 }
 304
 305                 if (fetch_next_entry(ef, parent, it) != 0)
 306                         goto error;
 307         }
 308         /* we never reach here */
 309
 310 error:
 311         free(*node);
 312         *node = NULL;
 313         return -EIO;
 314 }
 315
 316 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
 317 {
 318         struct iterator it;
 319         int rc;
 320         struct exfat_node* node;
 321         struct exfat_node* current = NULL;
 322
 323         if (dir->flags & EXFAT_ATTRIB_CACHED)
 324                 return 0; /* already cached */
 325
 326         opendir(dir, &it);
 327         while ((rc = readdir(ef, dir, &node, &it)) == 0)
 328         {
 329                 node->parent = dir;
 330                 if (current != NULL)
 331                 {
 332                         current->next = node;
 333                         node->prev = current;
 334                 }
 335                 else
 336                         dir->child = node;
 337
 338                 current = node;
 339         }
 340         closedir(&it);
 341
 342         if (rc != -ENOENT)
 343         {
 344                 /* rollback */
 345                 for (current = dir->child; current; current = node)
 346                 {
 347                         node = current->next;
 348                         free(current);
 349                 }
 350                 dir->child = NULL;
 351                 return rc;
 352         }
 353
 354         dir->flags |= EXFAT_ATTRIB_CACHED;
 355         return 0;
 356 }
 357
 358 static void reset_cache(struct exfat* ef, struct exfat_node* node)
 359 {
 360         struct exfat_node* child;
 361         struct exfat_node* next;
 362
 363         for (child = node->child; child; child = next)
 364         {
 365                 reset_cache(ef, child);
 366                 next = child->next;
 367                 free(child);
 368         }
 369         if (node->references != 0)
 370         {
 371                 char buffer[EXFAT_NAME_MAX + 1];
 372                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
 373                 exfat_warn("non-zero reference counter (%d) for `%s'",
 374                                 node->references, buffer);
 375         }
 376         while (node->references--)
 377                 exfat_put_node(ef, node);
 378         node->child = NULL;
 379         node->flags &= ~EXFAT_ATTRIB_CACHED;
 380 }
 381
 382 void exfat_reset_cache(struct exfat* ef)
 383 {
 384         reset_cache(ef, ef->root);
 385 }
 386
 387 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 388 {
 389         off_t meta1_offset, meta2_offset;
 390         struct exfat_file meta1;
 391         struct exfat_file_info meta2;
 392         uint16_t checksum;
 393         uint8_t i;
 394
 395         meta1_offset = exfat_c2o(ef, node->entry_cluster) + node->entry_offset;
 396         if (node->entry_offset + sizeof(struct exfat_entry)
 397                         == CLUSTER_SIZE(*ef->sb))
 398                 /* next cluster cannot be invalid */
 399                 meta2_offset = exfat_c2o(ef,
 400                                 exfat_next_cluster(ef, node, node->entry_cluster));
 401         else
 402                 meta2_offset = meta1_offset + sizeof(struct exfat_entry);
 403
 404         exfat_read_raw(&meta1, sizeof(meta1), meta1_offset, ef->fd);
 405         if (meta1.type != EXFAT_ENTRY_FILE)
 406                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
 407         meta1.attrib = cpu_to_le16(node->flags);
 408         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime);
 409         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime);
 410
 411         exfat_read_raw(&meta2, sizeof(meta2), meta2_offset, ef->fd);
 412         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
 413                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
 414         meta2.size = cpu_to_le64(node->size);
 415         meta2.start_cluster = cpu_to_le32(node->start_cluster);
 416         meta2.flag = (IS_CONTIGUOUS(*node) ?
 417                         EXFAT_FLAG_CONTIGUOUS : EXFAT_FLAG_FRAGMENTED);
 418         /* FIXME name hash */
 419
 420         checksum = exfat_start_checksum(&meta1);
 421         checksum = exfat_add_checksum(&meta2, checksum);
 422         for (i = 1; i < meta1.continuations; i++)
 423         {
 424                 struct exfat_file_name name = {EXFAT_ENTRY_FILE_NAME, 0};
 425                 memcpy(name.name, node->name + (i - 1) * EXFAT_ENAME_MAX,
 426                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 427                 checksum = exfat_add_checksum(&name, checksum);
 428         }
 429         meta1.checksum = cpu_to_le16(checksum);
 430
 431         exfat_write_raw(&meta1, sizeof(meta1), meta1_offset, ef->fd);
 432         exfat_write_raw(&meta2, sizeof(meta2), meta2_offset, ef->fd);
 433
 434         node->flags &= ~EXFAT_ATTRIB_DIRTY;
 435 }