libexfat/node.c

   1 /*
   2         node.c (09.10.09)
   3         exFAT file system implementation library.
   4
   5         Free exFAT implementation.
   6         Copyright (C) 2010-2013  Andrew Nayenko
   7
   8         This program is free software; you can redistribute it and/or modify
   9         it under the terms of the GNU General Public License as published by
  10         the Free Software Foundation, either version 2 of the License, or
  11         (at your option) any later version.
  12
  13         This program is distributed in the hope that it will be useful,
  14         but WITHOUT ANY WARRANTY; without even the implied warranty of
  15         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16         GNU General Public License for more details.
  17
  18         You should have received a copy of the GNU General Public License along
  19         with this program; if not, write to the Free Software Foundation, Inc.,
  20         51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21 */
  22
  23 #include "exfat.h"
  24 #include <errno.h>
  25 #include <string.h>
  26 #include <inttypes.h>
  27
  28 /* on-disk nodes iterator */
  29 struct iterator
  30 {
  31         cluster_t cluster;
  32         off_t offset;
  33         int contiguous;
  34         char* chunk;
  35 };
  36
  37 struct exfat_node* exfat_get_node(struct exfat_node* node)
  38 {
  39         /* if we switch to multi-threaded mode we will need atomic
  40            increment here and atomic decrement in exfat_put_node() */
  41         node->references++;
  42         return node;
  43 }
  44
  45 void exfat_put_node(struct exfat* ef, struct exfat_node* node)
  46 {
  47         if (--node->references < 0)
  48         {
  49                 char buffer[UTF8_BYTES(EXFAT_NAME_MAX) + 1];
  50                 exfat_get_name(node, buffer, sizeof(buffer) - 1);
  51                 exfat_bug("reference counter of `%s' is below zero", buffer);
  52         }
  53
  54         if (node->references == 0)
  55         {
  56                 exfat_flush_node(ef, node);
  57                 if (node->flags & EXFAT_ATTRIB_UNLINKED)
  58                 {
  59                         /* free all clusters and node structure itself */
  60                         exfat_truncate(ef, node, 0, true);
  61                         free(node);
  62                 }
  63                 exfat_flush(ef);
  64         }
  65 }
  66
  67 /**
  68  * Cluster + offset from the beginning of the directory to absolute offset.
  69  */
  70 static off_t co2o(struct exfat* ef, cluster_t cluster, off_t offset)
  71 {
  72         return exfat_c2o(ef, cluster) + offset % CLUSTER_SIZE(*ef->sb);
  73 }
  74
  75 static int opendir(struct exfat* ef, const struct exfat_node* dir,
  76                 struct iterator* it)
  77 {
  78         if (!(dir->flags & EXFAT_ATTRIB_DIR))
  79                 exfat_bug("not a directory");
  80         it->cluster = dir->start_cluster;
  81         it->offset = 0;
  82         it->contiguous = IS_CONTIGUOUS(*dir);
  83         it->chunk = malloc(CLUSTER_SIZE(*ef->sb));
  84         if (it->chunk == NULL)
  85         {
  86                 exfat_error("out of memory");
  87                 return -ENOMEM;
  88         }
  89         if (exfat_pread(ef->dev, it->chunk, CLUSTER_SIZE(*ef->sb),
  90                         exfat_c2o(ef, it->cluster)) < 0)
  91         {
  92                 exfat_error("failed to read directory cluster %#x", it->cluster);
  93                 return -EIO;
  94         }
  95         return 0;
  96 }
  97
  98 static void closedir(struct iterator* it)
  99 {
 100         it->cluster = 0;
 101         it->offset = 0;
 102         it->contiguous = 0;
 103         free(it->chunk);
 104         it->chunk = NULL;
 105 }
 106
 107 static int fetch_next_entry(struct exfat* ef, const struct exfat_node* parent,
 108                 struct iterator* it)
 109 {
 110         /* move iterator to the next entry in the directory */
 111         it->offset += sizeof(struct exfat_entry);
 112         /* fetch the next cluster if needed */
 113         if ((it->offset & (CLUSTER_SIZE(*ef->sb) - 1)) == 0)
 114         {
 115                 /* reached the end of directory; the caller should check this
 116                    condition too */
 117                 if (it->offset >= parent->size)
 118                         return 0;
 119                 it->cluster = exfat_next_cluster(ef, parent, it->cluster);
 120                 if (CLUSTER_INVALID(it->cluster))
 121                 {
 122                         exfat_error("invalid cluster 0x%x while reading directory",
 123                                         it->cluster);
 124                         return 1;
 125                 }
 126                 if (exfat_pread(ef->dev, it->chunk, CLUSTER_SIZE(*ef->sb),
 127                                 exfat_c2o(ef, it->cluster)) < 0)
 128                 {
 129                         exfat_error("failed to read the next directory cluster %#x",
 130                                         it->cluster);
 131                         return 1;
 132                 }
 133         }
 134         return 0;
 135 }
 136
 137 static struct exfat_node* allocate_node(void)
 138 {
 139         struct exfat_node* node = malloc(sizeof(struct exfat_node));
 140         if (node == NULL)
 141         {
 142                 exfat_error("failed to allocate node");
 143                 return NULL;
 144         }
 145         memset(node, 0, sizeof(struct exfat_node));
 146         return node;
 147 }
 148
 149 static void init_node_meta1(struct exfat_node* node,
 150                 const struct exfat_entry_meta1* meta1)
 151 {
 152         node->flags = le16_to_cpu(meta1->attrib);
 153         node->mtime = exfat_exfat2unix(meta1->mdate, meta1->mtime,
 154                         meta1->mtime_cs);
 155         /* there is no centiseconds field for atime */
 156         node->atime = exfat_exfat2unix(meta1->adate, meta1->atime, 0);
 157 }
 158
 159 static void init_node_meta2(struct exfat_node* node,
 160                 const struct exfat_entry_meta2* meta2)
 161 {
 162         node->size = le64_to_cpu(meta2->size);
 163         node->start_cluster = le32_to_cpu(meta2->start_cluster);
 164         node->fptr_cluster = node->start_cluster;
 165         if (meta2->flags & EXFAT_FLAG_CONTIGUOUS)
 166                 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
 167 }
 168
 169 static const struct exfat_entry* get_entry_ptr(const struct exfat* ef,
 170                 const struct iterator* it)
 171 {
 172         return (const struct exfat_entry*)
 173                         (it->chunk + it->offset % CLUSTER_SIZE(*ef->sb));
 174 }
 175
 176 /*
 177  * Reads one entry in directory at position pointed by iterator and fills
 178  * node structure.
 179  */
 180 static int readdir(struct exfat* ef, const struct exfat_node* parent,
 181                 struct exfat_node** node, struct iterator* it)
 182 {
 183         int rc = -EIO;
 184         const struct exfat_entry* entry;
 185         const struct exfat_entry_meta1* meta1;
 186         const struct exfat_entry_meta2* meta2;
 187         const struct exfat_entry_name* file_name;
 188         const struct exfat_entry_upcase* upcase;
 189         const struct exfat_entry_bitmap* bitmap;
 190         const struct exfat_entry_label* label;
 191         uint8_t continuations = 0;
 192         le16_t* namep = NULL;
 193         uint16_t reference_checksum = 0;
 194         uint16_t actual_checksum = 0;
 195         uint64_t real_size = 0;
 196
 197         *node = NULL;
 198
 199         for (;;)
 200         {
 201                 if (it->offset >= parent->size)
 202                 {
 203                         if (continuations != 0)
 204                         {
 205                                 exfat_error("expected %hhu continuations", continuations);
 206                                 goto error;
 207                         }
 208                         return -ENOENT; /* that's OK, means end of directory */
 209                 }
 210
 211                 entry = get_entry_ptr(ef, it);
 212                 switch (entry->type)
 213                 {
 214                 case EXFAT_ENTRY_FILE:
 215                         if (continuations != 0)
 216                         {
 217                                 exfat_error("expected %hhu continuations before new entry",
 218                                                 continuations);
 219                                 goto error;
 220                         }
 221                         meta1 = (const struct exfat_entry_meta1*) entry;
 222                         continuations = meta1->continuations;
 223                         /* each file entry must have at least 2 continuations:
 224                            info and name */
 225                         if (continuations < 2)
 226                         {
 227                                 exfat_error("too few continuations (%hhu)", continuations);
 228                                 goto error;
 229                         }
 230                         if (continuations > 1 +
 231                                         DIV_ROUND_UP(EXFAT_NAME_MAX, EXFAT_ENAME_MAX))
 232                         {
 233                                 exfat_error("too many continuations (%hhu)", continuations);
 234                                 goto error;
 235                         }
 236                         reference_checksum = le16_to_cpu(meta1->checksum);
 237                         actual_checksum = exfat_start_checksum(meta1);
 238                         *node = allocate_node();
 239                         if (*node == NULL)
 240                         {
 241                                 rc = -ENOMEM;
 242                                 goto error;
 243                         }
 244                         /* new node has zero reference counter */
 245                         (*node)->entry_cluster = it->cluster;
 246                         (*node)->entry_offset = it->offset;
 247                         init_node_meta1(*node, meta1);
 248                         namep = (*node)->name;
 249                         break;
 250
 251                 case EXFAT_ENTRY_FILE_INFO:
 252                         if (continuations < 2)
 253                         {
 254                                 exfat_error("unexpected continuation (%hhu)",
 255                                                 continuations);
 256                                 goto error;
 257                         }
 258                         meta2 = (const struct exfat_entry_meta2*) entry;
 259                         if (meta2->flags & ~(EXFAT_FLAG_ALWAYS1 | EXFAT_FLAG_CONTIGUOUS))
 260                         {
 261                                 exfat_error("unknown flags in meta2 (0x%hhx)", meta2->flags);
 262                                 goto error;
 263                         }
 264                         init_node_meta2(*node, meta2);
 265                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
 266                         real_size = le64_to_cpu(meta2->real_size);
 267                         /* empty files must be marked as non-contiguous */
 268                         if ((*node)->size == 0 && (meta2->flags & EXFAT_FLAG_CONTIGUOUS))
 269                         {
 270                                 exfat_error("empty file marked as contiguous (0x%hhx)",
 271                                                 meta2->flags);
 272                                 goto error;
 273                         }
 274                         /* directories must be aligned on at cluster boundary */
 275                         if (((*node)->flags & EXFAT_ATTRIB_DIR) &&
 276                                 (*node)->size % CLUSTER_SIZE(*ef->sb) != 0)
 277                         {
 278                                 exfat_error("directory has invalid size %"PRIu64" bytes",
 279                                                 (*node)->size);
 280                                 goto error;
 281                         }
 282                         --continuations;
 283                         break;
 284
 285                 case EXFAT_ENTRY_FILE_NAME:
 286                         if (continuations == 0)
 287                         {
 288                                 exfat_error("unexpected continuation");
 289                                 goto error;
 290                         }
 291                         file_name = (const struct exfat_entry_name*) entry;
 292                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
 293
 294                         memcpy(namep, file_name->name,
 295                                         MIN(EXFAT_ENAME_MAX,
 296                                                 ((*node)->name + EXFAT_NAME_MAX - namep)) *
 297                                         sizeof(le16_t));
 298                         namep += EXFAT_ENAME_MAX;
 299                         if (--continuations == 0)
 300                         {
 301                                 /*
 302                                    There are two fields that contain file size. Maybe they
 303                                    plan to add compression support in the future and one of
 304                                    those fields is visible (uncompressed) size and the other
 305                                    is real (compressed) size. Anyway, currently it looks like
 306                                    exFAT does not support compression and both fields must be
 307                                    equal.
 308
 309                                    There is an exception though: pagefile.sys (its real_size
 310                                    is always 0).
 311                                 */
 312                                 if (real_size != (*node)->size)
 313                                 {
 314                                         char buffer[UTF8_BYTES(EXFAT_NAME_MAX) + 1];
 315
 316                                         exfat_get_name(*node, buffer, sizeof(buffer) - 1);
 317                                         exfat_error("`%s' real size does not equal to size "
 318                                                         "(%"PRIu64" != %"PRIu64")", buffer,
 319                                                         real_size, (*node)->size);
 320                                         goto error;
 321                                 }
 322                                 if (actual_checksum != reference_checksum)
 323                                 {
 324                                         char buffer[UTF8_BYTES(EXFAT_NAME_MAX) + 1];
 325
 326                                         exfat_get_name(*node, buffer, sizeof(buffer) - 1);
 327                                         exfat_error("`%s' has invalid checksum (0x%hx != 0x%hx)",
 328                                                         buffer, actual_checksum, reference_checksum);
 329                                         goto error;
 330                                 }
 331                                 if (fetch_next_entry(ef, parent, it) != 0)
 332                                         goto error;
 333                                 return 0; /* entry completed */
 334                         }
 335                         break;
 336
 337                 case EXFAT_ENTRY_UPCASE:
 338                         if (ef->upcase != NULL)
 339                                 break;
 340                         upcase = (const struct exfat_entry_upcase*) entry;
 341                         if (CLUSTER_INVALID(le32_to_cpu(upcase->start_cluster)))
 342                         {
 343                                 exfat_error("invalid cluster 0x%x in upcase table",
 344                                                 le32_to_cpu(upcase->start_cluster));
 345                                 goto error;
 346                         }
 347                         if (le64_to_cpu(upcase->size) == 0 ||
 348                                 le64_to_cpu(upcase->size) > 0xffff * sizeof(uint16_t) ||
 349                                 le64_to_cpu(upcase->size) % sizeof(uint16_t) != 0)
 350                         {
 351                                 exfat_error("bad upcase table size (%"PRIu64" bytes)",
 352                                                 le64_to_cpu(upcase->size));
 353                                 goto error;
 354                         }
 355                         ef->upcase = malloc(le64_to_cpu(upcase->size));
 356                         if (ef->upcase == NULL)
 357                         {
 358                                 exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
 359                                                 le64_to_cpu(upcase->size));
 360                                 rc = -ENOMEM;
 361                                 goto error;
 362                         }
 363                         ef->upcase_chars = le64_to_cpu(upcase->size) / sizeof(le16_t);
 364
 365                         if (exfat_pread(ef->dev, ef->upcase, le64_to_cpu(upcase->size),
 366                                         exfat_c2o(ef, le32_to_cpu(upcase->start_cluster))) < 0)
 367                         {
 368                                 exfat_error("failed to read upper case table "
 369                                                 "(%"PRIu64" bytes starting at cluster %#x)",
 370                                                 le64_to_cpu(upcase->size),
 371                                                 le32_to_cpu(upcase->start_cluster));
 372                                 goto error;
 373                         }
 374                         break;
 375
 376                 case EXFAT_ENTRY_BITMAP:
 377                         bitmap = (const struct exfat_entry_bitmap*) entry;
 378                         ef->cmap.start_cluster = le32_to_cpu(bitmap->start_cluster);
 379                         if (CLUSTER_INVALID(ef->cmap.start_cluster))
 380                         {
 381                                 exfat_error("invalid cluster 0x%x in clusters bitmap",
 382                                                 ef->cmap.start_cluster);
 383                                 goto error;
 384                         }
 385                         ef->cmap.size = le32_to_cpu(ef->sb->cluster_count) -
 386                                 EXFAT_FIRST_DATA_CLUSTER;
 387                         if (le64_to_cpu(bitmap->size) < DIV_ROUND_UP(ef->cmap.size, 8))
 388                         {
 389                                 exfat_error("invalid clusters bitmap size: %"PRIu64
 390                                                 " (expected at least %u)",
 391                                                 le64_to_cpu(bitmap->size),
 392                                                 DIV_ROUND_UP(ef->cmap.size, 8));
 393                                 goto error;
 394                         }
 395                         /* FIXME bitmap can be rather big, up to 512 MB */
 396                         ef->cmap.chunk_size = ef->cmap.size;
 397                         ef->cmap.chunk = malloc(BMAP_SIZE(ef->cmap.chunk_size));
 398                         if (ef->cmap.chunk == NULL)
 399                         {
 400                                 exfat_error("failed to allocate clusters bitmap chunk "
 401                                                 "(%"PRIu64" bytes)", le64_to_cpu(bitmap->size));
 402                                 rc = -ENOMEM;
 403                                 goto error;
 404                         }
 405
 406                         if (exfat_pread(ef->dev, ef->cmap.chunk,
 407                                         BMAP_SIZE(ef->cmap.chunk_size),
 408                                         exfat_c2o(ef, ef->cmap.start_cluster)) < 0)
 409                         {
 410                                 exfat_error("failed to read clusters bitmap "
 411                                                 "(%"PRIu64" bytes starting at cluster %#x)",
 412                                                 le64_to_cpu(bitmap->size), ef->cmap.start_cluster);
 413                                 goto error;
 414                         }
 415                         break;
 416
 417                 case EXFAT_ENTRY_LABEL:
 418                         label = (const struct exfat_entry_label*) entry;
 419                         if (label->length > EXFAT_ENAME_MAX)
 420                         {
 421                                 exfat_error("too long label (%hhu chars)", label->length);
 422                                 goto error;
 423                         }
 424                         if (utf16_to_utf8(ef->label, label->name,
 425                                                 sizeof(ef->label) - 1, EXFAT_ENAME_MAX) != 0)
 426                                 goto error;
 427                         break;
 428
 429                 default:
 430                         if (entry->type & EXFAT_ENTRY_VALID)
 431                         {
 432                                 exfat_error("unknown entry type 0x%hhx", entry->type);
 433                                 goto error;
 434                         }
 435                         break;
 436                 }
 437
 438                 if (fetch_next_entry(ef, parent, it) != 0)
 439                         goto error;
 440         }
 441         /* we never reach here */
 442
 443 error:
 444         free(*node);
 445         *node = NULL;
 446         return rc;
 447 }
 448
 449 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
 450 {
 451         struct iterator it;
 452         int rc;
 453         struct exfat_node* node;
 454         struct exfat_node* current = NULL;
 455
 456         if (dir->flags & EXFAT_ATTRIB_CACHED)
 457                 return 0; /* already cached */
 458
 459         rc = opendir(ef, dir, &it);
 460         if (rc != 0)
 461                 return rc;
 462         while ((rc = readdir(ef, dir, &node, &it)) == 0)
 463         {
 464                 node->parent = dir;
 465                 if (current != NULL)
 466                 {
 467                         current->next = node;
 468                         node->prev = current;
 469                 }
 470                 else
 471                         dir->child = node;
 472
 473                 current = node;
 474         }
 475         closedir(&it);
 476
 477         if (rc != -ENOENT)
 478         {
 479                 /* rollback */
 480                 for (current = dir->child; current; current = node)
 481                 {
 482                         node = current->next;
 483                         free(current);
 484                 }
 485                 dir->child = NULL;
 486                 return rc;
 487         }
 488
 489         dir->flags |= EXFAT_ATTRIB_CACHED;
 490         return 0;
 491 }
 492
 493 static void tree_attach(struct exfat_node* dir, struct exfat_node* node)
 494 {
 495         node->parent = dir;
 496         if (dir->child)
 497         {
 498                 dir->child->prev = node;
 499                 node->next = dir->child;
 500         }
 501         dir->child = node;
 502 }
 503
 504 static void tree_detach(struct exfat_node* node)
 505 {
 506         if (node->prev)
 507                 node->prev->next = node->next;
 508         else /* this is the first node in the list */
 509                 node->parent->child = node->next;
 510         if (node->next)
 511                 node->next->prev = node->prev;
 512         node->parent = NULL;
 513         node->prev = NULL;
 514         node->next = NULL;
 515 }
 516
 517 static void reset_cache(struct exfat* ef, struct exfat_node* node)
 518 {
 519         while (node->child)
 520         {
 521                 struct exfat_node* p = node->child;
 522                 reset_cache(ef, p);
 523                 tree_detach(p);
 524                 free(p);
 525         }
 526         node->flags &= ~EXFAT_ATTRIB_CACHED;
 527         if (node->references != 0)
 528         {
 529                 char buffer[UTF8_BYTES(EXFAT_NAME_MAX) + 1];
 530                 exfat_get_name(node, buffer, sizeof(buffer) - 1);
 531                 exfat_warn("non-zero reference counter (%d) for `%s'",
 532                                 node->references, buffer);
 533         }
 534         while (node->references)
 535                 exfat_put_node(ef, node);
 536 }
 537
 538 void exfat_reset_cache(struct exfat* ef)
 539 {
 540         reset_cache(ef, ef->root);
 541 }
 542
 543 static void next_entry(struct exfat* ef, const struct exfat_node* parent,
 544                 cluster_t* cluster, off_t* offset)
 545 {
 546         *offset += sizeof(struct exfat_entry);
 547         if (*offset % CLUSTER_SIZE(*ef->sb) == 0)
 548                 /* next cluster cannot be invalid */
 549                 *cluster = exfat_next_cluster(ef, parent, *cluster);
 550 }
 551
 552 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 553 {
 554         cluster_t cluster;
 555         off_t offset;
 556         off_t meta1_offset, meta2_offset;
 557         struct exfat_entry_meta1 meta1;
 558         struct exfat_entry_meta2 meta2;
 559
 560         if (!(node->flags & EXFAT_ATTRIB_DIRTY))
 561                 return; /* no need to flush */
 562
 563         if (ef->ro)
 564                 exfat_bug("unable to flush node to read-only FS");
 565
 566         if (node->parent == NULL)
 567                 return; /* do not flush unlinked node */
 568
 569         cluster = node->entry_cluster;
 570         offset = node->entry_offset;
 571         meta1_offset = co2o(ef, cluster, offset);
 572         next_entry(ef, node->parent, &cluster, &offset);
 573         meta2_offset = co2o(ef, cluster, offset);
 574
 575         /* FIXME handle I/O error */
 576         if (exfat_pread(ef->dev, &meta1, sizeof(meta1), meta1_offset) < 0)
 577                 exfat_bug("failed to read meta1 entry on flush");
 578         if (meta1.type != EXFAT_ENTRY_FILE)
 579                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
 580         meta1.attrib = cpu_to_le16(node->flags);
 581         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime, &meta1.mtime_cs);
 582         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime, NULL);
 583
 584         /* FIXME handle I/O error */
 585         if (exfat_pread(ef->dev, &meta2, sizeof(meta2), meta2_offset) < 0)
 586                 exfat_bug("failed to read meta2 entry on flush");
 587         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
 588                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
 589         meta2.size = meta2.real_size = cpu_to_le64(node->size);
 590         meta2.start_cluster = cpu_to_le32(node->start_cluster);
 591         meta2.flags = EXFAT_FLAG_ALWAYS1;
 592         /* empty files must not be marked as contiguous */
 593         if (node->size != 0 && IS_CONTIGUOUS(*node))
 594                 meta2.flags |= EXFAT_FLAG_CONTIGUOUS;
 595         /* name hash remains unchanged, no need to recalculate it */
 596
 597         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 598
 599         /* FIXME handle I/O error */
 600         if (exfat_pwrite(ef->dev, &meta1, sizeof(meta1), meta1_offset) < 0)
 601                 exfat_bug("failed to write meta1 entry on flush");
 602         /* FIXME handle I/O error */
 603         if (exfat_pwrite(ef->dev, &meta2, sizeof(meta2), meta2_offset) < 0)
 604                 exfat_bug("failed to write meta2 entry on flush");
 605
 606         node->flags &= ~EXFAT_ATTRIB_DIRTY;
 607 }
 608
 609 static bool erase_entry(struct exfat* ef, struct exfat_node* node)
 610 {
 611         cluster_t cluster = node->entry_cluster;
 612         off_t offset = node->entry_offset;
 613         int name_entries = DIV_ROUND_UP(utf16_length(node->name), EXFAT_ENAME_MAX);
 614         uint8_t entry_type;
 615
 616         entry_type = EXFAT_ENTRY_FILE & ~EXFAT_ENTRY_VALID;
 617         if (exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset)) < 0)
 618         {
 619                 exfat_error("failed to erase meta1 entry");
 620                 return false;
 621         }
 622
 623         next_entry(ef, node->parent, &cluster, &offset);
 624         entry_type = EXFAT_ENTRY_FILE_INFO & ~EXFAT_ENTRY_VALID;
 625         if (exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset)) < 0)
 626         {
 627                 exfat_error("failed to erase meta2 entry");
 628                 return false;
 629         }
 630
 631         while (name_entries--)
 632         {
 633                 next_entry(ef, node->parent, &cluster, &offset);
 634                 entry_type = EXFAT_ENTRY_FILE_NAME & ~EXFAT_ENTRY_VALID;
 635                 if (exfat_pwrite(ef->dev, &entry_type, 1,
 636                                 co2o(ef, cluster, offset)) < 0)
 637                 {
 638                         exfat_error("failed to erase name entry");
 639                         return false;
 640                 }
 641         }
 642         return true;
 643 }
 644
 645 static int shrink_directory(struct exfat* ef, struct exfat_node* dir,
 646                 off_t deleted_offset)
 647 {
 648         const struct exfat_node* node;
 649         const struct exfat_node* last_node;
 650         uint64_t entries = 0;
 651         uint64_t new_size;
 652         int rc;
 653
 654         if (!(dir->flags & EXFAT_ATTRIB_DIR))
 655                 exfat_bug("attempted to shrink a file");
 656         if (!(dir->flags & EXFAT_ATTRIB_CACHED))
 657                 exfat_bug("attempted to shrink uncached directory");
 658
 659         for (last_node = node = dir->child; node; node = node->next)
 660         {
 661                 if (deleted_offset < node->entry_offset)
 662                 {
 663                         /* there are other entries after the removed one, no way to shrink
 664                            this directory */
 665                         return 0;
 666                 }
 667                 if (last_node->entry_offset < node->entry_offset)
 668                         last_node = node;
 669         }
 670
 671         if (last_node)
 672         {
 673                 /* offset of the last entry */
 674                 entries += last_node->entry_offset / sizeof(struct exfat_entry);
 675                 /* two subentries with meta info */
 676                 entries += 2;
 677                 /* subentries with file name */
 678                 entries += DIV_ROUND_UP(utf16_length(last_node->name),
 679                                 EXFAT_ENAME_MAX);
 680         }
 681
 682         new_size = DIV_ROUND_UP(entries * sizeof(struct exfat_entry),
 683                                  CLUSTER_SIZE(*ef->sb)) * CLUSTER_SIZE(*ef->sb);
 684         if (new_size == 0) /* directory always has at least 1 cluster */
 685                 new_size = CLUSTER_SIZE(*ef->sb);
 686         if (new_size == dir->size)
 687                 return 0;
 688         rc = exfat_truncate(ef, dir, new_size, true);
 689         if (rc != 0)
 690                 return rc;
 691         return 0;
 692 }
 693
 694 static int delete(struct exfat* ef, struct exfat_node* node)
 695 {
 696         struct exfat_node* parent = node->parent;
 697         off_t deleted_offset = node->entry_offset;
 698         int rc;
 699
 700         exfat_get_node(parent);
 701         if (!erase_entry(ef, node))
 702         {
 703                 exfat_put_node(ef, parent);
 704                 return -EIO;
 705         }
 706         exfat_update_mtime(parent);
 707         tree_detach(node);
 708         rc = shrink_directory(ef, parent, deleted_offset);
 709         exfat_put_node(ef, parent);
 710         /* file clusters will be freed when node reference counter becomes 0 */
 711         node->flags |= EXFAT_ATTRIB_UNLINKED;
 712         return rc;
 713 }
 714
 715 int exfat_unlink(struct exfat* ef, struct exfat_node* node)
 716 {
 717         if (node->flags & EXFAT_ATTRIB_DIR)
 718                 return -EISDIR;
 719         return delete(ef, node);
 720 }
 721
 722 int exfat_rmdir(struct exfat* ef, struct exfat_node* node)
 723 {
 724         if (!(node->flags & EXFAT_ATTRIB_DIR))
 725                 return -ENOTDIR;
 726         /* check that directory is empty */
 727         exfat_cache_directory(ef, node);
 728         if (node->child)
 729                 return -ENOTEMPTY;
 730         return delete(ef, node);
 731 }
 732
 733 static int grow_directory(struct exfat* ef, struct exfat_node* dir,
 734                 uint64_t asize, uint32_t difference)
 735 {
 736         return exfat_truncate(ef, dir,
 737                         DIV_ROUND_UP(asize + difference, CLUSTER_SIZE(*ef->sb))
 738                                 * CLUSTER_SIZE(*ef->sb), true);
 739 }
 740
 741 static int find_slot(struct exfat* ef, struct exfat_node* dir,
 742                 cluster_t* cluster, off_t* offset, int subentries)
 743 {
 744         struct iterator it;
 745         int rc;
 746         const struct exfat_entry* entry;
 747         int contiguous = 0;
 748
 749         rc = opendir(ef, dir, &it);
 750         if (rc != 0)
 751                 return rc;
 752         for (;;)
 753         {
 754                 if (contiguous == 0)
 755                 {
 756                         *cluster = it.cluster;
 757                         *offset = it.offset;
 758                 }
 759                 entry = get_entry_ptr(ef, &it);
 760                 if (entry->type & EXFAT_ENTRY_VALID)
 761                         contiguous = 0;
 762                 else
 763                         contiguous++;
 764                 if (contiguous == subentries)
 765                         break;  /* suitable slot is found */
 766                 if (it.offset + sizeof(struct exfat_entry) >= dir->size)
 767                 {
 768                         rc = grow_directory(ef, dir, dir->size,
 769                                         (subentries - contiguous) * sizeof(struct exfat_entry));
 770                         if (rc != 0)
 771                         {
 772                                 closedir(&it);
 773                                 return rc;
 774                         }
 775                 }
 776                 if (fetch_next_entry(ef, dir, &it) != 0)
 777                 {
 778                         closedir(&it);
 779                         return -EIO;
 780                 }
 781         }
 782         closedir(&it);
 783         return 0;
 784 }
 785
 786 static int write_entry(struct exfat* ef, struct exfat_node* dir,
 787                 const le16_t* name, cluster_t cluster, off_t offset, uint16_t attrib)
 788 {
 789         struct exfat_node* node;
 790         struct exfat_entry_meta1 meta1;
 791         struct exfat_entry_meta2 meta2;
 792         const size_t name_length = utf16_length(name);
 793         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 794         int i;
 795
 796         node = allocate_node();
 797         if (node == NULL)
 798                 return -ENOMEM;
 799         node->entry_cluster = cluster;
 800         node->entry_offset = offset;
 801         memcpy(node->name, name, name_length * sizeof(le16_t));
 802
 803         memset(&meta1, 0, sizeof(meta1));
 804         meta1.type = EXFAT_ENTRY_FILE;
 805         meta1.continuations = 1 + name_entries;
 806         meta1.attrib = cpu_to_le16(attrib);
 807         exfat_unix2exfat(time(NULL), &meta1.crdate, &meta1.crtime,
 808                         &meta1.crtime_cs);
 809         meta1.adate = meta1.mdate = meta1.crdate;
 810         meta1.atime = meta1.mtime = meta1.crtime;
 811         meta1.mtime_cs = meta1.crtime_cs; /* there is no atime_cs */
 812
 813         memset(&meta2, 0, sizeof(meta2));
 814         meta2.type = EXFAT_ENTRY_FILE_INFO;
 815         meta2.flags = EXFAT_FLAG_ALWAYS1;
 816         meta2.name_length = name_length;
 817         meta2.name_hash = exfat_calc_name_hash(ef, node->name);
 818         meta2.start_cluster = cpu_to_le32(EXFAT_CLUSTER_FREE);
 819
 820         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 821
 822         if (exfat_pwrite(ef->dev, &meta1, sizeof(meta1),
 823                         co2o(ef, cluster, offset)) < 0)
 824         {
 825                 exfat_error("failed to write meta1 entry");
 826                 return -EIO;
 827         }
 828         next_entry(ef, dir, &cluster, &offset);
 829         if (exfat_pwrite(ef->dev, &meta2, sizeof(meta2),
 830                         co2o(ef, cluster, offset)) < 0)
 831         {
 832                 exfat_error("failed to write meta2 entry");
 833                 return -EIO;
 834         }
 835         for (i = 0; i < name_entries; i++)
 836         {
 837                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
 838                 memcpy(name_entry.name, node->name + i * EXFAT_ENAME_MAX,
 839                                 MIN(EXFAT_ENAME_MAX, EXFAT_NAME_MAX - i * EXFAT_ENAME_MAX) *
 840                                 sizeof(le16_t));
 841                 next_entry(ef, dir, &cluster, &offset);
 842                 if (exfat_pwrite(ef->dev, &name_entry, sizeof(name_entry),
 843                                 co2o(ef, cluster, offset)) < 0)
 844                 {
 845                         exfat_error("failed to write name entry");
 846                         return -EIO;
 847                 }
 848         }
 849
 850         init_node_meta1(node, &meta1);
 851         init_node_meta2(node, &meta2);
 852
 853         tree_attach(dir, node);
 854         exfat_update_mtime(dir);
 855         return 0;
 856 }
 857
 858 static int create(struct exfat* ef, const char* path, uint16_t attrib)
 859 {
 860         struct exfat_node* dir;
 861         struct exfat_node* existing;
 862         cluster_t cluster = EXFAT_CLUSTER_BAD;
 863         off_t offset = -1;
 864         le16_t name[EXFAT_NAME_MAX + 1];
 865         int rc;
 866
 867         rc = exfat_split(ef, &dir, &existing, name, path);
 868         if (rc != 0)
 869                 return rc;
 870         if (existing != NULL)
 871         {
 872                 exfat_put_node(ef, existing);
 873                 exfat_put_node(ef, dir);
 874                 return -EEXIST;
 875         }
 876
 877         rc = find_slot(ef, dir, &cluster, &offset,
 878                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 879         if (rc != 0)
 880         {
 881                 exfat_put_node(ef, dir);
 882                 return rc;
 883         }
 884         rc = write_entry(ef, dir, name, cluster, offset, attrib);
 885         exfat_put_node(ef, dir);
 886         return rc;
 887 }
 888
 889 int exfat_mknod(struct exfat* ef, const char* path)
 890 {
 891         return create(ef, path, EXFAT_ATTRIB_ARCH);
 892 }
 893
 894 int exfat_mkdir(struct exfat* ef, const char* path)
 895 {
 896         int rc;
 897         struct exfat_node* node;
 898
 899         rc = create(ef, path, EXFAT_ATTRIB_ARCH | EXFAT_ATTRIB_DIR);
 900         if (rc != 0)
 901                 return rc;
 902         rc = exfat_lookup(ef, &node, path);
 903         if (rc != 0)
 904                 return 0;
 905         /* directories always have at least one cluster */
 906         rc = exfat_truncate(ef, node, CLUSTER_SIZE(*ef->sb), true);
 907         if (rc != 0)
 908         {
 909                 delete(ef, node);
 910                 exfat_put_node(ef, node);
 911                 return rc;
 912         }
 913         exfat_put_node(ef, node);
 914         return 0;
 915 }
 916
 917 static int rename_entry(struct exfat* ef, struct exfat_node* dir,
 918                 struct exfat_node* node, const le16_t* name, cluster_t new_cluster,
 919                 off_t new_offset)
 920 {
 921         struct exfat_entry_meta1 meta1;
 922         struct exfat_entry_meta2 meta2;
 923         cluster_t old_cluster = node->entry_cluster;
 924         off_t old_offset = node->entry_offset;
 925         const size_t name_length = utf16_length(name);
 926         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 927         int i;
 928
 929         if (exfat_pread(ef->dev, &meta1, sizeof(meta1),
 930                         co2o(ef, old_cluster, old_offset)) < 0)
 931         {
 932                 exfat_error("failed to read meta1 entry on rename");
 933                 return -EIO;
 934         }
 935         next_entry(ef, node->parent, &old_cluster, &old_offset);
 936         if (exfat_pread(ef->dev, &meta2, sizeof(meta2),
 937                         co2o(ef, old_cluster, old_offset)) < 0)
 938         {
 939                 exfat_error("failed to read meta2 entry on rename");
 940                 return -EIO;
 941         }
 942         meta1.continuations = 1 + name_entries;
 943         meta2.name_hash = exfat_calc_name_hash(ef, name);
 944         meta2.name_length = name_length;
 945         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, name);
 946
 947         if (!erase_entry(ef, node))
 948                 return -EIO;
 949
 950         node->entry_cluster = new_cluster;
 951         node->entry_offset = new_offset;
 952
 953         if (exfat_pwrite(ef->dev, &meta1, sizeof(meta1),
 954                         co2o(ef, new_cluster, new_offset)) < 0)
 955         {
 956                 exfat_error("failed to write meta1 entry on rename");
 957                 return -EIO;
 958         }
 959         next_entry(ef, dir, &new_cluster, &new_offset);
 960         if (exfat_pwrite(ef->dev, &meta2, sizeof(meta2),
 961                         co2o(ef, new_cluster, new_offset)) < 0)
 962         {
 963                 exfat_error("failed to write meta2 entry on rename");
 964                 return -EIO;
 965         }
 966
 967         for (i = 0; i < name_entries; i++)
 968         {
 969                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
 970                 memcpy(name_entry.name, name + i * EXFAT_ENAME_MAX,
 971                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 972                 next_entry(ef, dir, &new_cluster, &new_offset);
 973                 if (exfat_pwrite(ef->dev, &name_entry, sizeof(name_entry),
 974                                 co2o(ef, new_cluster, new_offset)) < 0)
 975                 {
 976                         exfat_error("failed to write name entry on rename");
 977                         return -EIO;
 978                 }
 979         }
 980
 981         memcpy(node->name, name, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
 982         tree_detach(node);
 983         tree_attach(dir, node);
 984         return 0;
 985 }
 986
 987 int exfat_rename(struct exfat* ef, const char* old_path, const char* new_path)
 988 {
 989         struct exfat_node* node;
 990         struct exfat_node* existing;
 991         struct exfat_node* dir;
 992         cluster_t cluster = EXFAT_CLUSTER_BAD;
 993         off_t offset = -1;
 994         le16_t name[EXFAT_NAME_MAX + 1];
 995         int rc;
 996
 997         rc = exfat_lookup(ef, &node, old_path);
 998         if (rc != 0)
 999                 return rc;
1000
1001         rc = exfat_split(ef, &dir, &existing, name, new_path);
1002         if (rc != 0)
1003         {
1004                 exfat_put_node(ef, node);
1005                 return rc;
1006         }
1007
1008         /* check that target is not a subdirectory of the source */
1009         if (node->flags & EXFAT_ATTRIB_DIR)
1010         {
1011                 struct exfat_node* p;
1012
1013                 for (p = dir; p; p = p->parent)
1014                         if (node == p)
1015                         {
1016                                 if (existing != NULL)
1017                                         exfat_put_node(ef, existing);
1018                                 exfat_put_node(ef, dir);
1019                                 exfat_put_node(ef, node);
1020                                 return -EINVAL;
1021                         }
1022         }
1023
1024         if (existing != NULL)
1025         {
1026                 /* remove target if it's not the same node as source */
1027                 if (existing != node)
1028                 {
1029                         if (existing->flags & EXFAT_ATTRIB_DIR)
1030                         {
1031                                 if (node->flags & EXFAT_ATTRIB_DIR)
1032                                         rc = exfat_rmdir(ef, existing);
1033                                 else
1034                                         rc = -ENOTDIR;
1035                         }
1036                         else
1037                         {
1038                                 if (!(node->flags & EXFAT_ATTRIB_DIR))
1039                                         rc = exfat_unlink(ef, existing);
1040                                 else
1041                                         rc = -EISDIR;
1042                         }
1043                         exfat_put_node(ef, existing);
1044                         if (rc != 0)
1045                         {
1046                                 exfat_put_node(ef, dir);
1047                                 exfat_put_node(ef, node);
1048                                 return rc;
1049                         }
1050                 }
1051                 else
1052                         exfat_put_node(ef, existing);
1053         }
1054
1055         rc = find_slot(ef, dir, &cluster, &offset,
1056                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
1057         if (rc != 0)
1058         {
1059                 exfat_put_node(ef, dir);
1060                 exfat_put_node(ef, node);
1061                 return rc;
1062         }
1063         rc = rename_entry(ef, dir, node, name, cluster, offset);
1064         exfat_put_node(ef, dir);
1065         exfat_put_node(ef, node);
1066         return 0;
1067 }
1068
1069 void exfat_utimes(struct exfat_node* node, const struct timespec tv[2])
1070 {
1071         node->atime = tv[0].tv_sec;
1072         node->mtime = tv[1].tv_sec;
1073         node->flags |= EXFAT_ATTRIB_DIRTY;
1074 }
1075
1076 void exfat_update_atime(struct exfat_node* node)
1077 {
1078         node->atime = time(NULL);
1079         node->flags |= EXFAT_ATTRIB_DIRTY;
1080 }
1081
1082 void exfat_update_mtime(struct exfat_node* node)
1083 {
1084         node->mtime = time(NULL);
1085         node->flags |= EXFAT_ATTRIB_DIRTY;
1086 }
1087
1088 const char* exfat_get_label(struct exfat* ef)
1089 {
1090         return ef->label;
1091 }
1092
1093 static int find_label(struct exfat* ef, cluster_t* cluster, off_t* offset)
1094 {
1095         struct iterator it;
1096         int rc;
1097
1098         rc = opendir(ef, ef->root, &it);
1099         if (rc != 0)
1100                 return rc;
1101
1102         for (;;)
1103         {
1104                 if (it.offset >= ef->root->size)
1105                 {
1106                         closedir(&it);
1107                         return -ENOENT;
1108                 }
1109
1110                 if (get_entry_ptr(ef, &it)->type == EXFAT_ENTRY_LABEL)
1111                 {
1112                         *cluster = it.cluster;
1113                         *offset = it.offset;
1114                         closedir(&it);
1115                         return 0;
1116                 }
1117
1118                 if (fetch_next_entry(ef, ef->root, &it) != 0)
1119                 {
1120                         closedir(&it);
1121                         return -EIO;
1122                 }
1123         }
1124 }
1125
1126 int exfat_set_label(struct exfat* ef, const char* label)
1127 {
1128         le16_t label_utf16[EXFAT_ENAME_MAX + 1];
1129         int rc;
1130         cluster_t cluster;
1131         off_t offset;
1132         struct exfat_entry_label entry;
1133
1134         memset(label_utf16, 0, sizeof(label_utf16));
1135         rc = utf8_to_utf16(label_utf16, label, EXFAT_ENAME_MAX, strlen(label));
1136         if (rc != 0)
1137                 return rc;
1138
1139         rc = find_label(ef, &cluster, &offset);
1140         if (rc == -ENOENT)
1141                 rc = find_slot(ef, ef->root, &cluster, &offset, 1);
1142         if (rc != 0)
1143                 return rc;
1144
1145         entry.type = EXFAT_ENTRY_LABEL;
1146         entry.length = utf16_length(label_utf16);
1147         memcpy(entry.name, label_utf16, sizeof(entry.name));
1148         if (entry.length == 0)
1149                 entry.type ^= EXFAT_ENTRY_VALID;
1150
1151         if (exfat_pwrite(ef->dev, &entry, sizeof(struct exfat_entry_label),
1152                         co2o(ef, cluster, offset)) < 0)
1153         {
1154                 exfat_error("failed to write label entry");
1155                 return -EIO;
1156         }
1157         strcpy(ef->label, label);
1158         return 0;
1159 }