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