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