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) < DIV_ROUND_UP(ef->cmap.size, 8))
 372                         {
 373                                 exfat_error("invalid clusters bitmap size: %"PRIu64
 374                                                 " (expected at least %u)",
 375                                                 le64_to_cpu(bitmap->size),
 376                                                 DIV_ROUND_UP(ef->cmap.size, 8));
 377                                 goto error;
 378                         }
 379                         /* FIXME bitmap can be rather big, up to 512 MB */
 380                         ef->cmap.chunk_size = ef->cmap.size;
 381                         ef->cmap.chunk = malloc(BMAP_SIZE(ef->cmap.chunk_size));
 382                         if (ef->cmap.chunk == NULL)
 383                         {
 384                                 exfat_error("failed to allocate clusters bitmap chunk "
 385                                                 "(%"PRIu64" bytes)", le64_to_cpu(bitmap->size));
 386                                 rc = -ENOMEM;
 387                                 goto error;
 388                         }
 389
 390                         exfat_pread(ef->dev, ef->cmap.chunk,
 391                                         BMAP_SIZE(ef->cmap.chunk_size),
 392                                         exfat_c2o(ef, ef->cmap.start_cluster));
 393                         break;
 394
 395                 case EXFAT_ENTRY_LABEL:
 396                         label = (const struct exfat_entry_label*) entry;
 397                         if (label->length > EXFAT_ENAME_MAX)
 398                         {
 399                                 exfat_error("too long label (%hhu chars)", label->length);
 400                                 goto error;
 401                         }
 402                         if (utf16_to_utf8(ef->label, label->name,
 403                                                 sizeof(ef->label) - 1, EXFAT_ENAME_MAX) != 0)
 404                                 goto error;
 405                         break;
 406
 407                 default:
 408                         if (entry->type & EXFAT_ENTRY_VALID)
 409                         {
 410                                 exfat_error("unknown entry type 0x%hhx", entry->type);
 411                                 goto error;
 412                         }
 413                         break;
 414                 }
 415
 416                 if (fetch_next_entry(ef, parent, it) != 0)
 417                         goto error;
 418         }
 419         /* we never reach here */
 420
 421 error:
 422         free(*node);
 423         *node = NULL;
 424         return rc;
 425 }
 426
 427 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
 428 {
 429         struct iterator it;
 430         int rc;
 431         struct exfat_node* node;
 432         struct exfat_node* current = NULL;
 433
 434         if (dir->flags & EXFAT_ATTRIB_CACHED)
 435                 return 0; /* already cached */
 436
 437         rc = opendir(ef, dir, &it);
 438         if (rc != 0)
 439                 return rc;
 440         while ((rc = readdir(ef, dir, &node, &it)) == 0)
 441         {
 442                 node->parent = dir;
 443                 if (current != NULL)
 444                 {
 445                         current->next = node;
 446                         node->prev = current;
 447                 }
 448                 else
 449                         dir->child = node;
 450
 451                 current = node;
 452         }
 453         closedir(&it);
 454
 455         if (rc != -ENOENT)
 456         {
 457                 /* rollback */
 458                 for (current = dir->child; current; current = node)
 459                 {
 460                         node = current->next;
 461                         free(current);
 462                 }
 463                 dir->child = NULL;
 464                 return rc;
 465         }
 466
 467         dir->flags |= EXFAT_ATTRIB_CACHED;
 468         return 0;
 469 }
 470
 471 static void tree_attach(struct exfat_node* dir, struct exfat_node* node)
 472 {
 473         node->parent = dir;
 474         if (dir->child)
 475         {
 476                 dir->child->prev = node;
 477                 node->next = dir->child;
 478         }
 479         dir->child = node;
 480 }
 481
 482 static void tree_detach(struct exfat_node* node)
 483 {
 484         if (node->prev)
 485                 node->prev->next = node->next;
 486         else /* this is the first node in the list */
 487                 node->parent->child = node->next;
 488         if (node->next)
 489                 node->next->prev = node->prev;
 490         node->parent = NULL;
 491         node->prev = NULL;
 492         node->next = NULL;
 493 }
 494
 495 static void reset_cache(struct exfat* ef, struct exfat_node* node)
 496 {
 497         while (node->child)
 498         {
 499                 struct exfat_node* p = node->child;
 500                 reset_cache(ef, p);
 501                 tree_detach(p);
 502                 free(p);
 503         }
 504         node->flags &= ~EXFAT_ATTRIB_CACHED;
 505         if (node->references != 0)
 506         {
 507                 char buffer[UTF8_BYTES(EXFAT_NAME_MAX) + 1];
 508                 exfat_get_name(node, buffer, sizeof(buffer) - 1);
 509                 exfat_warn("non-zero reference counter (%d) for `%s'",
 510                                 node->references, buffer);
 511         }
 512         while (node->references)
 513                 exfat_put_node(ef, node);
 514 }
 515
 516 void exfat_reset_cache(struct exfat* ef)
 517 {
 518         reset_cache(ef, ef->root);
 519 }
 520
 521 static void next_entry(struct exfat* ef, const struct exfat_node* parent,
 522                 cluster_t* cluster, off_t* offset)
 523 {
 524         *offset += sizeof(struct exfat_entry);
 525         if (*offset % CLUSTER_SIZE(*ef->sb) == 0)
 526                 /* next cluster cannot be invalid */
 527                 *cluster = exfat_next_cluster(ef, parent, *cluster);
 528 }
 529
 530 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 531 {
 532         cluster_t cluster;
 533         off_t offset;
 534         off_t meta1_offset, meta2_offset;
 535         struct exfat_entry_meta1 meta1;
 536         struct exfat_entry_meta2 meta2;
 537
 538         if (!(node->flags & EXFAT_ATTRIB_DIRTY))
 539                 return; /* no need to flush */
 540
 541         if (ef->ro)
 542                 exfat_bug("unable to flush node to read-only FS");
 543
 544         if (node->parent == NULL)
 545                 return; /* do not flush unlinked node */
 546
 547         cluster = node->entry_cluster;
 548         offset = node->entry_offset;
 549         meta1_offset = co2o(ef, cluster, offset);
 550         next_entry(ef, node->parent, &cluster, &offset);
 551         meta2_offset = co2o(ef, cluster, offset);
 552
 553         exfat_pread(ef->dev, &meta1, sizeof(meta1), meta1_offset);
 554         if (meta1.type != EXFAT_ENTRY_FILE)
 555                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
 556         meta1.attrib = cpu_to_le16(node->flags);
 557         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime, &meta1.mtime_cs);
 558         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime, NULL);
 559
 560         exfat_pread(ef->dev, &meta2, sizeof(meta2), meta2_offset);
 561         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
 562                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
 563         meta2.size = meta2.real_size = cpu_to_le64(node->size);
 564         meta2.start_cluster = cpu_to_le32(node->start_cluster);
 565         meta2.flags = EXFAT_FLAG_ALWAYS1;
 566         /* empty files must not be marked as contiguous */
 567         if (node->size != 0 && IS_CONTIGUOUS(*node))
 568                 meta2.flags |= EXFAT_FLAG_CONTIGUOUS;
 569         /* name hash remains unchanged, no need to recalculate it */
 570
 571         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 572
 573         exfat_pwrite(ef->dev, &meta1, sizeof(meta1), meta1_offset);
 574         exfat_pwrite(ef->dev, &meta2, sizeof(meta2), meta2_offset);
 575
 576         node->flags &= ~EXFAT_ATTRIB_DIRTY;
 577 }
 578
 579 static void erase_entry(struct exfat* ef, struct exfat_node* node)
 580 {
 581         cluster_t cluster = node->entry_cluster;
 582         off_t offset = node->entry_offset;
 583         int name_entries = DIV_ROUND_UP(utf16_length(node->name), EXFAT_ENAME_MAX);
 584         uint8_t entry_type;
 585
 586         entry_type = EXFAT_ENTRY_FILE & ~EXFAT_ENTRY_VALID;
 587         exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
 588
 589         next_entry(ef, node->parent, &cluster, &offset);
 590         entry_type = EXFAT_ENTRY_FILE_INFO & ~EXFAT_ENTRY_VALID;
 591         exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
 592
 593         while (name_entries--)
 594         {
 595                 next_entry(ef, node->parent, &cluster, &offset);
 596                 entry_type = EXFAT_ENTRY_FILE_NAME & ~EXFAT_ENTRY_VALID;
 597                 exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
 598         }
 599 }
 600
 601 static int shrink_directory(struct exfat* ef, struct exfat_node* dir,
 602                 off_t deleted_offset)
 603 {
 604         const struct exfat_node* node;
 605         const struct exfat_node* last_node;
 606         uint64_t entries = 0;
 607         uint64_t new_size;
 608         int rc;
 609
 610         if (!(dir->flags & EXFAT_ATTRIB_DIR))
 611                 exfat_bug("attempted to shrink a file");
 612         if (!(dir->flags & EXFAT_ATTRIB_CACHED))
 613                 exfat_bug("attempted to shrink uncached directory");
 614
 615         for (last_node = node = dir->child; node; node = node->next)
 616         {
 617                 if (deleted_offset < node->entry_offset)
 618                 {
 619                         /* there are other entries after the removed one, no way to shrink
 620                            this directory */
 621                         return 0;
 622                 }
 623                 if (last_node->entry_offset < node->entry_offset)
 624                         last_node = node;
 625         }
 626
 627         if (last_node)
 628         {
 629                 /* offset of the last entry */
 630                 entries += last_node->entry_offset / sizeof(struct exfat_entry);
 631                 /* two subentries with meta info */
 632                 entries += 2;
 633                 /* subentries with file name */
 634                 entries += DIV_ROUND_UP(utf16_length(last_node->name),
 635                                 EXFAT_ENAME_MAX);
 636         }
 637
 638         new_size = DIV_ROUND_UP(entries * sizeof(struct exfat_entry),
 639                                  CLUSTER_SIZE(*ef->sb)) * CLUSTER_SIZE(*ef->sb);
 640         if (new_size == 0) /* directory always has at least 1 cluster */
 641                 new_size = CLUSTER_SIZE(*ef->sb);
 642         if (new_size == dir->size)
 643                 return 0;
 644         rc = exfat_truncate(ef, dir, new_size, true);
 645         if (rc != 0)
 646                 return rc;
 647         return 0;
 648 }
 649
 650 static int delete(struct exfat* ef, struct exfat_node* node)
 651 {
 652         struct exfat_node* parent = node->parent;
 653         off_t deleted_offset = node->entry_offset;
 654         int rc;
 655
 656         exfat_get_node(parent);
 657         erase_entry(ef, node);
 658         exfat_update_mtime(parent);
 659         tree_detach(node);
 660         rc = shrink_directory(ef, parent, deleted_offset);
 661         exfat_put_node(ef, parent);
 662         /* file clusters will be freed when node reference counter becomes 0 */
 663         node->flags |= EXFAT_ATTRIB_UNLINKED;
 664         return rc;
 665 }
 666
 667 int exfat_unlink(struct exfat* ef, struct exfat_node* node)
 668 {
 669         if (node->flags & EXFAT_ATTRIB_DIR)
 670                 return -EISDIR;
 671         return delete(ef, node);
 672 }
 673
 674 int exfat_rmdir(struct exfat* ef, struct exfat_node* node)
 675 {
 676         if (!(node->flags & EXFAT_ATTRIB_DIR))
 677                 return -ENOTDIR;
 678         /* check that directory is empty */
 679         exfat_cache_directory(ef, node);
 680         if (node->child)
 681                 return -ENOTEMPTY;
 682         return delete(ef, node);
 683 }
 684
 685 static int grow_directory(struct exfat* ef, struct exfat_node* dir,
 686                 uint64_t asize, uint32_t difference)
 687 {
 688         return exfat_truncate(ef, dir,
 689                         DIV_ROUND_UP(asize + difference, CLUSTER_SIZE(*ef->sb))
 690                                 * CLUSTER_SIZE(*ef->sb), true);
 691 }
 692
 693 static int find_slot(struct exfat* ef, struct exfat_node* dir,
 694                 cluster_t* cluster, off_t* offset, int subentries)
 695 {
 696         struct iterator it;
 697         int rc;
 698         const struct exfat_entry* entry;
 699         int contiguous = 0;
 700
 701         rc = opendir(ef, dir, &it);
 702         if (rc != 0)
 703                 return rc;
 704         for (;;)
 705         {
 706                 if (contiguous == 0)
 707                 {
 708                         *cluster = it.cluster;
 709                         *offset = it.offset;
 710                 }
 711                 entry = get_entry_ptr(ef, &it);
 712                 if (entry->type & EXFAT_ENTRY_VALID)
 713                         contiguous = 0;
 714                 else
 715                         contiguous++;
 716                 if (contiguous == subentries)
 717                         break;  /* suitable slot is found */
 718                 if (it.offset + sizeof(struct exfat_entry) >= dir->size)
 719                 {
 720                         rc = grow_directory(ef, dir, dir->size,
 721                                         (subentries - contiguous) * sizeof(struct exfat_entry));
 722                         if (rc != 0)
 723                         {
 724                                 closedir(&it);
 725                                 return rc;
 726                         }
 727                 }
 728                 if (fetch_next_entry(ef, dir, &it) != 0)
 729                 {
 730                         closedir(&it);
 731                         return -EIO;
 732                 }
 733         }
 734         closedir(&it);
 735         return 0;
 736 }
 737
 738 static int write_entry(struct exfat* ef, struct exfat_node* dir,
 739                 const le16_t* name, cluster_t cluster, off_t offset, uint16_t attrib)
 740 {
 741         struct exfat_node* node;
 742         struct exfat_entry_meta1 meta1;
 743         struct exfat_entry_meta2 meta2;
 744         const size_t name_length = utf16_length(name);
 745         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 746         int i;
 747
 748         node = allocate_node();
 749         if (node == NULL)
 750                 return -ENOMEM;
 751         node->entry_cluster = cluster;
 752         node->entry_offset = offset;
 753         memcpy(node->name, name, name_length * sizeof(le16_t));
 754
 755         memset(&meta1, 0, sizeof(meta1));
 756         meta1.type = EXFAT_ENTRY_FILE;
 757         meta1.continuations = 1 + name_entries;
 758         meta1.attrib = cpu_to_le16(attrib);
 759         exfat_unix2exfat(time(NULL), &meta1.crdate, &meta1.crtime,
 760                         &meta1.crtime_cs);
 761         meta1.adate = meta1.mdate = meta1.crdate;
 762         meta1.atime = meta1.mtime = meta1.crtime;
 763         meta1.mtime_cs = meta1.crtime_cs; /* there is no atime_cs */
 764
 765         memset(&meta2, 0, sizeof(meta2));
 766         meta2.type = EXFAT_ENTRY_FILE_INFO;
 767         meta2.flags = EXFAT_FLAG_ALWAYS1;
 768         meta2.name_length = name_length;
 769         meta2.name_hash = exfat_calc_name_hash(ef, node->name);
 770         meta2.start_cluster = cpu_to_le32(EXFAT_CLUSTER_FREE);
 771
 772         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 773
 774         exfat_pwrite(ef->dev, &meta1, sizeof(meta1), co2o(ef, cluster, offset));
 775         next_entry(ef, dir, &cluster, &offset);
 776         exfat_pwrite(ef->dev, &meta2, sizeof(meta2), co2o(ef, cluster, offset));
 777         for (i = 0; i < name_entries; i++)
 778         {
 779                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
 780                 memcpy(name_entry.name, node->name + i * EXFAT_ENAME_MAX,
 781                                 MIN(EXFAT_ENAME_MAX, EXFAT_NAME_MAX - i * EXFAT_ENAME_MAX) *
 782                                 sizeof(le16_t));
 783                 next_entry(ef, dir, &cluster, &offset);
 784                 exfat_pwrite(ef->dev, &name_entry, sizeof(name_entry),
 785                                 co2o(ef, cluster, offset));
 786         }
 787
 788         init_node_meta1(node, &meta1);
 789         init_node_meta2(node, &meta2);
 790
 791         tree_attach(dir, node);
 792         exfat_update_mtime(dir);
 793         return 0;
 794 }
 795
 796 static int create(struct exfat* ef, const char* path, uint16_t attrib)
 797 {
 798         struct exfat_node* dir;
 799         struct exfat_node* existing;
 800         cluster_t cluster = EXFAT_CLUSTER_BAD;
 801         off_t offset = -1;
 802         le16_t name[EXFAT_NAME_MAX + 1];
 803         int rc;
 804
 805         rc = exfat_split(ef, &dir, &existing, name, path);
 806         if (rc != 0)
 807                 return rc;
 808         if (existing != NULL)
 809         {
 810                 exfat_put_node(ef, existing);
 811                 exfat_put_node(ef, dir);
 812                 return -EEXIST;
 813         }
 814
 815         rc = find_slot(ef, dir, &cluster, &offset,
 816                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 817         if (rc != 0)
 818         {
 819                 exfat_put_node(ef, dir);
 820                 return rc;
 821         }
 822         rc = write_entry(ef, dir, name, cluster, offset, attrib);
 823         exfat_put_node(ef, dir);
 824         return rc;
 825 }
 826
 827 int exfat_mknod(struct exfat* ef, const char* path)
 828 {
 829         return create(ef, path, EXFAT_ATTRIB_ARCH);
 830 }
 831
 832 int exfat_mkdir(struct exfat* ef, const char* path)
 833 {
 834         int rc;
 835         struct exfat_node* node;
 836
 837         rc = create(ef, path, EXFAT_ATTRIB_ARCH | EXFAT_ATTRIB_DIR);
 838         if (rc != 0)
 839                 return rc;
 840         rc = exfat_lookup(ef, &node, path);
 841         if (rc != 0)
 842                 return 0;
 843         /* directories always have at least one cluster */
 844         rc = exfat_truncate(ef, node, CLUSTER_SIZE(*ef->sb), true);
 845         if (rc != 0)
 846         {
 847                 delete(ef, node);
 848                 exfat_put_node(ef, node);
 849                 return rc;
 850         }
 851         exfat_put_node(ef, node);
 852         return 0;
 853 }
 854
 855 static void rename_entry(struct exfat* ef, struct exfat_node* dir,
 856                 struct exfat_node* node, const le16_t* name, cluster_t new_cluster,
 857                 off_t new_offset)
 858 {
 859         struct exfat_entry_meta1 meta1;
 860         struct exfat_entry_meta2 meta2;
 861         cluster_t old_cluster = node->entry_cluster;
 862         off_t old_offset = node->entry_offset;
 863         const size_t name_length = utf16_length(name);
 864         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 865         int i;
 866
 867         exfat_pread(ef->dev, &meta1, sizeof(meta1),
 868                         co2o(ef, old_cluster, old_offset));
 869         next_entry(ef, node->parent, &old_cluster, &old_offset);
 870         exfat_pread(ef->dev, &meta2, sizeof(meta2),
 871                         co2o(ef, old_cluster, old_offset));
 872         meta1.continuations = 1 + name_entries;
 873         meta2.name_hash = exfat_calc_name_hash(ef, name);
 874         meta2.name_length = name_length;
 875         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, name);
 876
 877         erase_entry(ef, node);
 878
 879         node->entry_cluster = new_cluster;
 880         node->entry_offset = new_offset;
 881
 882         exfat_pwrite(ef->dev, &meta1, sizeof(meta1),
 883                         co2o(ef, new_cluster, new_offset));
 884         next_entry(ef, dir, &new_cluster, &new_offset);
 885         exfat_pwrite(ef->dev, &meta2, sizeof(meta2),
 886                         co2o(ef, new_cluster, new_offset));
 887
 888         for (i = 0; i < name_entries; i++)
 889         {
 890                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
 891                 memcpy(name_entry.name, name + i * EXFAT_ENAME_MAX,
 892                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 893                 next_entry(ef, dir, &new_cluster, &new_offset);
 894                 exfat_pwrite(ef->dev, &name_entry, sizeof(name_entry),
 895                                 co2o(ef, new_cluster, new_offset));
 896         }
 897
 898         memcpy(node->name, name, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
 899         tree_detach(node);
 900         tree_attach(dir, node);
 901 }
 902
 903 int exfat_rename(struct exfat* ef, const char* old_path, const char* new_path)
 904 {
 905         struct exfat_node* node;
 906         struct exfat_node* existing;
 907         struct exfat_node* dir;
 908         cluster_t cluster = EXFAT_CLUSTER_BAD;
 909         off_t offset = -1;
 910         le16_t name[EXFAT_NAME_MAX + 1];
 911         int rc;
 912
 913         rc = exfat_lookup(ef, &node, old_path);
 914         if (rc != 0)
 915                 return rc;
 916
 917         rc = exfat_split(ef, &dir, &existing, name, new_path);
 918         if (rc != 0)
 919         {
 920                 exfat_put_node(ef, node);
 921                 return rc;
 922         }
 923
 924         /* check that target is not a subdirectory of the source */
 925         if (node->flags & EXFAT_ATTRIB_DIR)
 926         {
 927                 struct exfat_node* p;
 928
 929                 for (p = dir; p; p = p->parent)
 930                         if (node == p)
 931                         {
 932                                 if (existing != NULL)
 933                                         exfat_put_node(ef, existing);
 934                                 exfat_put_node(ef, dir);
 935                                 exfat_put_node(ef, node);
 936                                 return -EINVAL;
 937                         }
 938         }
 939
 940         if (existing != NULL)
 941         {
 942                 /* remove target if it's not the same node as source */
 943                 if (existing != node)
 944                 {
 945                         if (existing->flags & EXFAT_ATTRIB_DIR)
 946                         {
 947                                 if (node->flags & EXFAT_ATTRIB_DIR)
 948                                         rc = exfat_rmdir(ef, existing);
 949                                 else
 950                                         rc = -ENOTDIR;
 951                         }
 952                         else
 953                         {
 954                                 if (!(node->flags & EXFAT_ATTRIB_DIR))
 955                                         rc = exfat_unlink(ef, existing);
 956                                 else
 957                                         rc = -EISDIR;
 958                         }
 959                         exfat_put_node(ef, existing);
 960                         if (rc != 0)
 961                         {
 962                                 exfat_put_node(ef, dir);
 963                                 exfat_put_node(ef, node);
 964                                 return rc;
 965                         }
 966                 }
 967                 else
 968                         exfat_put_node(ef, existing);
 969         }
 970
 971         rc = find_slot(ef, dir, &cluster, &offset,
 972                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 973         if (rc != 0)
 974         {
 975                 exfat_put_node(ef, dir);
 976                 exfat_put_node(ef, node);
 977                 return rc;
 978         }
 979         rename_entry(ef, dir, node, name, cluster, offset);
 980         exfat_put_node(ef, dir);
 981         exfat_put_node(ef, node);
 982         return 0;
 983 }
 984
 985 void exfat_utimes(struct exfat_node* node, const struct timespec tv[2])
 986 {
 987         node->atime = tv[0].tv_sec;
 988         node->mtime = tv[1].tv_sec;
 989         node->flags |= EXFAT_ATTRIB_DIRTY;
 990 }
 991
 992 void exfat_update_atime(struct exfat_node* node)
 993 {
 994         node->atime = time(NULL);
 995         node->flags |= EXFAT_ATTRIB_DIRTY;
 996 }
 997
 998 void exfat_update_mtime(struct exfat_node* node)
 999 {
1000         node->mtime = time(NULL);
1001         node->flags |= EXFAT_ATTRIB_DIRTY;
1002 }
1003
1004 const char* exfat_get_label(struct exfat* ef)
1005 {
1006         return ef->label;
1007 }
1008
1009 static int find_label(struct exfat* ef, cluster_t* cluster, off_t* offset)
1010 {
1011         struct iterator it;
1012         int rc;
1013
1014         rc = opendir(ef, ef->root, &it);
1015         if (rc != 0)
1016                 return rc;
1017
1018         for (;;)
1019         {
1020                 if (it.offset >= ef->root->size)
1021                 {
1022                         closedir(&it);
1023                         return -ENOENT;
1024                 }
1025
1026                 if (get_entry_ptr(ef, &it)->type == EXFAT_ENTRY_LABEL)
1027                 {
1028                         *cluster = it.cluster;
1029                         *offset = it.offset;
1030                         closedir(&it);
1031                         return 0;
1032                 }
1033
1034                 if (fetch_next_entry(ef, ef->root, &it) != 0)
1035                 {
1036                         closedir(&it);
1037                         return -EIO;
1038                 }
1039         }
1040 }
1041
1042 int exfat_set_label(struct exfat* ef, const char* label)
1043 {
1044         le16_t label_utf16[EXFAT_ENAME_MAX + 1];
1045         int rc;
1046         cluster_t cluster;
1047         off_t offset;
1048         struct exfat_entry_label entry;
1049
1050         memset(label_utf16, 0, sizeof(label_utf16));
1051         rc = utf8_to_utf16(label_utf16, label, EXFAT_ENAME_MAX, strlen(label));
1052         if (rc != 0)
1053                 return rc;
1054
1055         rc = find_label(ef, &cluster, &offset);
1056         if (rc == -ENOENT)
1057                 rc = find_slot(ef, ef->root, &cluster, &offset, 1);
1058         if (rc != 0)
1059                 return rc;
1060
1061         entry.type = EXFAT_ENTRY_LABEL;
1062         entry.length = utf16_length(label_utf16);
1063         memcpy(entry.name, label_utf16, sizeof(entry.name));
1064         if (entry.length == 0)
1065                 entry.type ^= EXFAT_ENTRY_VALID;
1066
1067         exfat_pwrite(ef->dev, &entry, sizeof(struct exfat_entry_label),
1068                         co2o(ef, cluster, offset));
1069         strcpy(ef->label, label);
1070         return 0;
1071 }