libexfat/node.c

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