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