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