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 (node->flags & EXFAT_ATTRIB_UNLINKED)
  46                 {
  47                         /* free all clusters and node structure itself */
  48                         exfat_truncate(ef, node, 0);
  49                         free(node);
  50                 }
  51                 if (ef->cmap.dirty)
  52                         exfat_flush_cmap(ef);
  53         }
  54 }
  55
  56 static int opendir(struct exfat* ef, const struct exfat_node* dir,
  57                 struct iterator* it)
  58 {
  59         if (!(dir->flags & EXFAT_ATTRIB_DIR))
  60                 exfat_bug("`%s' is not a directory", dir->name);
  61         it->cluster = dir->start_cluster;
  62         it->offset = 0;
  63         it->contiguous = IS_CONTIGUOUS(*dir);
  64         it->chunk = malloc(CLUSTER_SIZE(*ef->sb));
  65         if (it->chunk == NULL)
  66         {
  67                 exfat_error("out of memory");
  68                 return -ENOMEM;
  69         }
  70         exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
  71                         exfat_c2o(ef, it->cluster), ef->fd);
  72         return 0;
  73 }
  74
  75 static void closedir(struct iterator* it)
  76 {
  77         it->cluster = 0;
  78         it->offset = 0;
  79         it->contiguous = 0;
  80         free(it->chunk);
  81         it->chunk = NULL;
  82 }
  83
  84 static int fetch_next_entry(struct exfat* ef, const struct exfat_node* parent,
  85                 struct iterator* it)
  86 {
  87         /* move iterator to the next entry in the directory */
  88         it->offset += sizeof(struct exfat_entry);
  89         /* fetch the next cluster if needed */
  90         if ((it->offset & (CLUSTER_SIZE(*ef->sb) - 1)) == 0)
  91         {
  92                 it->cluster = exfat_next_cluster(ef, parent, it->cluster);
  93                 if (CLUSTER_INVALID(it->cluster))
  94                 {
  95                         exfat_error("invalid cluster while reading directory");
  96                         return 1;
  97                 }
  98                 exfat_read_raw(it->chunk, CLUSTER_SIZE(*ef->sb),
  99                                 exfat_c2o(ef, it->cluster), ef->fd);
 100         }
 101         return 0;
 102 }
 103
 104 static struct exfat_node* allocate_node(void)
 105 {
 106         struct exfat_node* node = malloc(sizeof(struct exfat_node));
 107         if (node == NULL)
 108         {
 109                 exfat_error("failed to allocate node");
 110                 return NULL;
 111         }
 112         memset(node, 0, sizeof(struct exfat_node));
 113         return node;
 114 }
 115
 116 static void init_node_meta1(struct exfat_node* node,
 117                 const struct exfat_file* meta1)
 118 {
 119         node->flags = le16_to_cpu(meta1->attrib);
 120         node->mtime = exfat_exfat2unix(meta1->mdate, meta1->mtime);
 121         node->atime = exfat_exfat2unix(meta1->adate, meta1->atime);
 122 }
 123
 124 static void init_node_meta2(struct exfat_node* node,
 125                 const struct exfat_file_info* meta2)
 126 {
 127         node->size = le64_to_cpu(meta2->size);
 128         node->start_cluster = le32_to_cpu(meta2->start_cluster);
 129         node->fptr_cluster = node->start_cluster;
 130         if (meta2->flag == EXFAT_FLAG_CONTIGUOUS)
 131                 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
 132 }
 133
 134 /*
 135  * Reads one entry in directory at position pointed by iterator and fills
 136  * node structure.
 137  */
 138 static int readdir(struct exfat* ef, const struct exfat_node* parent,
 139                 struct exfat_node** node, struct iterator* it)
 140 {
 141         const struct exfat_entry* entry;
 142         const struct exfat_file* file;
 143         const struct exfat_file_info* file_info;
 144         const struct exfat_file_name* file_name;
 145         const struct exfat_upcase* upcase;
 146         const struct exfat_bitmap* bitmap;
 147         const struct exfat_label* label;
 148         uint8_t continuations = 0;
 149         le16_t* namep = NULL;
 150         uint16_t reference_checksum = 0;
 151         uint16_t actual_checksum = 0;
 152
 153         *node = NULL;
 154
 155         for (;;)
 156         {
 157                 /* every directory (even empty one) occupies at least one cluster and
 158                    must contain EOD entry */
 159                 entry = (const struct exfat_entry*)
 160                                 (it->chunk + it->offset % CLUSTER_SIZE(*ef->sb));
 161
 162                 switch (entry->type)
 163                 {
 164                 case EXFAT_ENTRY_EOD:
 165                         if (continuations != 0)
 166                         {
 167                                 exfat_error("expected %hhu continuations before EOD",
 168                                                 continuations);
 169                                 goto error;
 170                         }
 171                         return -ENOENT; /* that's OK, means end of directory */
 172
 173                 case EXFAT_ENTRY_FILE:
 174                         if (continuations != 0)
 175                         {
 176                                 exfat_error("expected %hhu continuations before new entry",
 177                                                 continuations);
 178                                 goto error;
 179                         }
 180                         file = (const struct exfat_file*) entry;
 181                         continuations = file->continuations;
 182                         /* each file entry must have at least 2 continuations:
 183                            info and name */
 184                         if (continuations < 2)
 185                         {
 186                                 exfat_error("too few continuations (%hhu)", continuations);
 187                                 return -EIO;
 188                         }
 189                         reference_checksum = le16_to_cpu(file->checksum);
 190                         actual_checksum = exfat_start_checksum(file);
 191                         *node = allocate_node();
 192                         if (*node == NULL)
 193                                 return -ENOMEM;
 194                         /* new node has zero reference counter */
 195                         (*node)->entry_cluster = it->cluster;
 196                         (*node)->entry_offset = it->offset % CLUSTER_SIZE(*ef->sb);
 197                         init_node_meta1(*node, file);
 198                         namep = (*node)->name;
 199                         break;
 200
 201                 case EXFAT_ENTRY_FILE_INFO:
 202                         if (continuations < 2)
 203                         {
 204                                 exfat_error("unexpected continuation (%hhu)",
 205                                                 continuations);
 206                                 goto error;
 207                         }
 208                         file_info = (const struct exfat_file_info*) entry;
 209                         init_node_meta2(*node, file_info);
 210                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
 211                         /* directories must be aligned on at cluster boundary */
 212                         if (((*node)->flags & EXFAT_ATTRIB_DIR) &&
 213                                 (*node)->size % CLUSTER_SIZE(*ef->sb) != 0)
 214                         {
 215                                 char buffer[EXFAT_NAME_MAX + 1];
 216
 217                                 exfat_get_name(*node, buffer, EXFAT_NAME_MAX);
 218                                 exfat_error("directory `%s' has invalid size %"PRIu64" bytes",
 219                                                 buffer, (*node)->size);
 220                                 goto error;
 221                         }
 222                         --continuations;
 223                         break;
 224
 225                 case EXFAT_ENTRY_FILE_NAME:
 226                         if (continuations == 0)
 227                         {
 228                                 exfat_error("unexpected continuation");
 229                                 goto error;
 230                         }
 231                         file_name = (const struct exfat_file_name*) entry;
 232                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
 233
 234                         memcpy(namep, file_name->name, EXFAT_ENAME_MAX * sizeof(le16_t));
 235                         namep += EXFAT_ENAME_MAX;
 236                         if (--continuations == 0)
 237                         {
 238                                 if (actual_checksum != reference_checksum)
 239                                 {
 240                                         exfat_error("invalid checksum (0x%hx != 0x%hx)",
 241                                                         actual_checksum, reference_checksum);
 242                                         return -EIO;
 243                                 }
 244                                 if (fetch_next_entry(ef, parent, it) != 0)
 245                                         goto error;
 246                                 return 0; /* entry completed */
 247                         }
 248                         break;
 249
 250                 case EXFAT_ENTRY_UPCASE:
 251                         if (ef->upcase != NULL)
 252                                 break;
 253                         upcase = (const struct exfat_upcase*) entry;
 254                         if (CLUSTER_INVALID(le32_to_cpu(upcase->start_cluster)))
 255                         {
 256                                 exfat_error("invalid cluster in upcase table");
 257                                 return -EIO;
 258                         }
 259                         if (le64_to_cpu(upcase->size) == 0 ||
 260                                 le64_to_cpu(upcase->size) > 0xffff * sizeof(uint16_t) ||
 261                                 le64_to_cpu(upcase->size) % sizeof(uint16_t) != 0)
 262                         {
 263                                 exfat_error("bad upcase table size (%"PRIu64" bytes)",
 264                                                 le64_to_cpu(upcase->size));
 265                                 return -EIO;
 266                         }
 267                         ef->upcase = malloc(le64_to_cpu(upcase->size));
 268                         if (ef->upcase == NULL)
 269                         {
 270                                 exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
 271                                                 le64_to_cpu(upcase->size));
 272                                 return -ENOMEM;
 273                         }
 274                         ef->upcase_chars = le64_to_cpu(upcase->size) / sizeof(le16_t);
 275
 276                         exfat_read_raw(ef->upcase, le64_to_cpu(upcase->size),
 277                                         exfat_c2o(ef, le32_to_cpu(upcase->start_cluster)), ef->fd);
 278                         break;
 279
 280                 case EXFAT_ENTRY_BITMAP:
 281                         bitmap = (const struct exfat_bitmap*) entry;
 282                         if (CLUSTER_INVALID(le32_to_cpu(bitmap->start_cluster)))
 283                         {
 284                                 exfat_error("invalid cluster in clusters bitmap");
 285                                 return -EIO;
 286                         }
 287                         ef->cmap.size = le32_to_cpu(ef->sb->cluster_count) -
 288                                 EXFAT_FIRST_DATA_CLUSTER;
 289                         if (le64_to_cpu(bitmap->size) != (ef->cmap.size + 7) / 8)
 290                         {
 291                                 exfat_error("invalid bitmap size: %"PRIu64" (expected %u)",
 292                                                 le64_to_cpu(bitmap->size), (ef->cmap.size + 7) / 8);
 293                                 return -EIO;
 294                         }
 295                         ef->cmap.start_cluster = le32_to_cpu(bitmap->start_cluster);
 296                         /* FIXME bitmap can be rather big, up to 512 MB */
 297                         ef->cmap.chunk_size = ef->cmap.size;
 298                         ef->cmap.chunk = malloc(le64_to_cpu(bitmap->size));
 299                         if (ef->cmap.chunk == NULL)
 300                         {
 301                                 exfat_error("failed to allocate clusters map chunk "
 302                                                 "(%"PRIu64" bytes)", le64_to_cpu(bitmap->size));
 303                                 return -ENOMEM;
 304                         }
 305
 306                         exfat_read_raw(ef->cmap.chunk, le64_to_cpu(bitmap->size),
 307                                         exfat_c2o(ef, ef->cmap.start_cluster), ef->fd);
 308                         break;
 309
 310                 case EXFAT_ENTRY_LABEL:
 311                         label = (const struct exfat_label*) entry;
 312                         if (label->length > EXFAT_ENAME_MAX)
 313                         {
 314                                 exfat_error("too long label (%hhu chars)", label->length);
 315                                 return -EIO;
 316                         }
 317                         break;
 318
 319                 default:
 320                         if (entry->type & EXFAT_ENTRY_VALID)
 321                         {
 322                                 exfat_error("unknown entry type 0x%hhu", entry->type);
 323                                 goto error;
 324                         }
 325                         break;
 326                 }
 327
 328                 if (fetch_next_entry(ef, parent, it) != 0)
 329                         goto error;
 330         }
 331         /* we never reach here */
 332
 333 error:
 334         free(*node);
 335         *node = NULL;
 336         return -EIO;
 337 }
 338
 339 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
 340 {
 341         struct iterator it;
 342         int rc;
 343         struct exfat_node* node;
 344         struct exfat_node* current = NULL;
 345
 346         if (dir->flags & EXFAT_ATTRIB_CACHED)
 347                 return 0; /* already cached */
 348
 349         rc = opendir(ef, dir, &it);
 350         if (rc != 0)
 351                 return rc;
 352         while ((rc = readdir(ef, dir, &node, &it)) == 0)
 353         {
 354                 node->parent = dir;
 355                 if (current != NULL)
 356                 {
 357                         current->next = node;
 358                         node->prev = current;
 359                 }
 360                 else
 361                         dir->child = node;
 362
 363                 current = node;
 364         }
 365         closedir(&it);
 366
 367         if (rc != -ENOENT)
 368         {
 369                 /* rollback */
 370                 for (current = dir->child; current; current = node)
 371                 {
 372                         node = current->next;
 373                         free(current);
 374                 }
 375                 dir->child = NULL;
 376                 return rc;
 377         }
 378
 379         dir->flags |= EXFAT_ATTRIB_CACHED;
 380         return 0;
 381 }
 382
 383 static void reset_cache(struct exfat* ef, struct exfat_node* node)
 384 {
 385         struct exfat_node* child;
 386         struct exfat_node* next;
 387
 388         for (child = node->child; child; child = next)
 389         {
 390                 reset_cache(ef, child);
 391                 next = child->next;
 392                 free(child);
 393         }
 394         if (node->references != 0)
 395         {
 396                 char buffer[EXFAT_NAME_MAX + 1];
 397                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
 398                 exfat_warn("non-zero reference counter (%d) for `%s'",
 399                                 node->references, buffer);
 400         }
 401         while (node->references--)
 402                 exfat_put_node(ef, node);
 403         node->child = NULL;
 404         node->flags &= ~EXFAT_ATTRIB_CACHED;
 405 }
 406
 407 void exfat_reset_cache(struct exfat* ef)
 408 {
 409         reset_cache(ef, ef->root);
 410 }
 411
 412 void next_entry(struct exfat* ef, const struct exfat_node* parent,
 413                 cluster_t* cluster, off_t* offset)
 414 {
 415         if (*offset + sizeof(struct exfat_entry) == CLUSTER_SIZE(*ef->sb))
 416         {
 417                 /* next cluster cannot be invalid */
 418                 *cluster = exfat_next_cluster(ef, parent, *cluster);
 419                 *offset = 0;
 420         }
 421         else
 422                 *offset += sizeof(struct exfat_entry);
 423
 424 }
 425
 426 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 427 {
 428         cluster_t cluster;
 429         off_t offset;
 430         off_t meta1_offset, meta2_offset;
 431         struct exfat_file meta1;
 432         struct exfat_file_info meta2;
 433
 434         if (node->parent == NULL)
 435                 return; /* do not flush unlinked node */
 436
 437         cluster = node->entry_cluster;
 438         offset = node->entry_offset;
 439         meta1_offset = exfat_c2o(ef, cluster) + offset;
 440         next_entry(ef, node->parent, &cluster, &offset);
 441         meta2_offset = exfat_c2o(ef, cluster) + offset;
 442
 443         exfat_read_raw(&meta1, sizeof(meta1), meta1_offset, ef->fd);
 444         if (meta1.type != EXFAT_ENTRY_FILE)
 445                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
 446         meta1.attrib = cpu_to_le16(node->flags);
 447         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime);
 448         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime);
 449
 450         exfat_read_raw(&meta2, sizeof(meta2), meta2_offset, ef->fd);
 451         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
 452                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
 453         meta2.size = cpu_to_le64(node->size);
 454         meta2.start_cluster = cpu_to_le32(node->start_cluster);
 455         meta2.flag = (IS_CONTIGUOUS(*node) ?
 456                         EXFAT_FLAG_CONTIGUOUS : EXFAT_FLAG_FRAGMENTED);
 457         /* FIXME name hash */
 458
 459         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 460
 461         exfat_write_raw(&meta1, sizeof(meta1), meta1_offset, ef->fd);
 462         exfat_write_raw(&meta2, sizeof(meta2), meta2_offset, ef->fd);
 463
 464         node->flags &= ~EXFAT_ATTRIB_DIRTY;
 465 }
 466
 467 static void erase_entry(struct exfat* ef, struct exfat_node* node)
 468 {
 469         cluster_t cluster = node->entry_cluster;
 470         off_t offset = node->entry_offset;
 471         int name_entries = DIV_ROUND_UP(utf16_length(node->name), EXFAT_ENAME_MAX);
 472         uint8_t entry_type;
 473
 474         entry_type = EXFAT_ENTRY_FILE & ~EXFAT_ENTRY_VALID;
 475         exfat_write_raw(&entry_type, 1, exfat_c2o(ef, cluster) + offset, ef->fd);
 476
 477         next_entry(ef, node->parent, &cluster, &offset);
 478         entry_type = EXFAT_ENTRY_FILE_INFO & ~EXFAT_ENTRY_VALID;
 479         exfat_write_raw(&entry_type, 1, exfat_c2o(ef, cluster) + offset, ef->fd);
 480
 481         while (name_entries--)
 482         {
 483                 next_entry(ef, node->parent, &cluster, &offset);
 484                 entry_type = EXFAT_ENTRY_FILE_NAME & ~EXFAT_ENTRY_VALID;
 485                 exfat_write_raw(&entry_type, 1, exfat_c2o(ef, cluster) + offset,
 486                                 ef->fd);
 487         }
 488 }
 489
 490 static void delete(struct exfat* ef, struct exfat_node* node)
 491 {
 492         erase_entry(ef, node);
 493         if (node->prev)
 494                 node->prev->next = node->next;
 495         else /* this is the first node in the list */
 496                 node->parent->child = node->next;
 497         if (node->next)
 498                 node->next->prev = node->prev;
 499         node->parent = NULL;
 500         node->prev = NULL;
 501         node->next = NULL;
 502         /* file clusters will be freed when node reference counter becomes 0 */
 503         node->flags |= EXFAT_ATTRIB_UNLINKED;
 504 }
 505
 506 int exfat_unlink(struct exfat* ef, struct exfat_node* node)
 507 {
 508         if (node->flags & EXFAT_ATTRIB_DIR)
 509                 return -EISDIR;
 510         delete(ef, node);
 511         return 0;
 512 }
 513
 514 int exfat_rmdir(struct exfat* ef, struct exfat_node* node)
 515 {
 516         if (!(node->flags & EXFAT_ATTRIB_DIR))
 517                 return -ENOTDIR;
 518         /* check that directory is empty */
 519         exfat_cache_directory(ef, node);
 520         if (node->child)
 521                 return -ENOTEMPTY;
 522         delete(ef, node);
 523         return 0;
 524 }