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