libexfat/node.c

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