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