libexfat/node.c

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