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 reset_cache(struct exfat* ef, struct exfat_node* node)
 461 {
 462         struct exfat_node* child;
 463         struct exfat_node* next;
 464
 465         for (child = node->child; child; child = next)
 466         {
 467                 reset_cache(ef, child);
 468                 next = child->next;
 469                 free(child);
 470         }
 471         if (node->references != 0)
 472         {
 473                 char buffer[EXFAT_NAME_MAX + 1];
 474                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
 475                 exfat_warn("non-zero reference counter (%d) for `%s'",
 476                                 node->references, buffer);
 477         }
 478         while (node->references--)
 479                 exfat_put_node(ef, node);
 480         node->child = NULL;
 481         node->flags &= ~EXFAT_ATTRIB_CACHED;
 482 }
 483
 484 void exfat_reset_cache(struct exfat* ef)
 485 {
 486         reset_cache(ef, ef->root);
 487 }
 488
 489 void next_entry(struct exfat* ef, const struct exfat_node* parent,
 490                 cluster_t* cluster, off_t* offset)
 491 {
 492         *offset += sizeof(struct exfat_entry);
 493         if (*offset % CLUSTER_SIZE(*ef->sb) == 0)
 494                 /* next cluster cannot be invalid */
 495                 *cluster = exfat_next_cluster(ef, parent, *cluster);
 496 }
 497
 498 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 499 {
 500         cluster_t cluster;
 501         off_t offset;
 502         off_t meta1_offset, meta2_offset;
 503         struct exfat_entry_meta1 meta1;
 504         struct exfat_entry_meta2 meta2;
 505
 506         if (ef->ro)
 507                 exfat_bug("unable to flush node to read-only FS");
 508
 509         if (node->parent == NULL)
 510                 return; /* do not flush unlinked node */
 511
 512         cluster = node->entry_cluster;
 513         offset = node->entry_offset;
 514         meta1_offset = co2o(ef, cluster, offset);
 515         next_entry(ef, node->parent, &cluster, &offset);
 516         meta2_offset = co2o(ef, cluster, offset);
 517
 518         exfat_pread(ef->dev, &meta1, sizeof(meta1), meta1_offset);
 519         if (meta1.type != EXFAT_ENTRY_FILE)
 520                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
 521         meta1.attrib = cpu_to_le16(node->flags);
 522         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime, &meta1.mtime_cs);
 523         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime, NULL);
 524
 525         exfat_pread(ef->dev, &meta2, sizeof(meta2), meta2_offset);
 526         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
 527                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
 528         meta2.size = meta2.real_size = cpu_to_le64(node->size);
 529         meta2.start_cluster = cpu_to_le32(node->start_cluster);
 530         meta2.flags = EXFAT_FLAG_ALWAYS1;
 531         /* empty files must not be marked as contiguous */
 532         if (node->size != 0 && IS_CONTIGUOUS(*node))
 533                 meta2.flags |= EXFAT_FLAG_CONTIGUOUS;
 534         /* name hash remains unchanged, no need to recalculate it */
 535
 536         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 537
 538         exfat_pwrite(ef->dev, &meta1, sizeof(meta1), meta1_offset);
 539         exfat_pwrite(ef->dev, &meta2, sizeof(meta2), meta2_offset);
 540
 541         node->flags &= ~EXFAT_ATTRIB_DIRTY;
 542 }
 543
 544 static void erase_entry(struct exfat* ef, struct exfat_node* node)
 545 {
 546         cluster_t cluster = node->entry_cluster;
 547         off_t offset = node->entry_offset;
 548         int name_entries = DIV_ROUND_UP(utf16_length(node->name), EXFAT_ENAME_MAX);
 549         uint8_t entry_type;
 550
 551         entry_type = EXFAT_ENTRY_FILE & ~EXFAT_ENTRY_VALID;
 552         exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
 553
 554         next_entry(ef, node->parent, &cluster, &offset);
 555         entry_type = EXFAT_ENTRY_FILE_INFO & ~EXFAT_ENTRY_VALID;
 556         exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
 557
 558         while (name_entries--)
 559         {
 560                 next_entry(ef, node->parent, &cluster, &offset);
 561                 entry_type = EXFAT_ENTRY_FILE_NAME & ~EXFAT_ENTRY_VALID;
 562                 exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
 563         }
 564 }
 565
 566 static void tree_detach(struct exfat_node* node)
 567 {
 568         if (node->prev)
 569                 node->prev->next = node->next;
 570         else /* this is the first node in the list */
 571                 node->parent->child = node->next;
 572         if (node->next)
 573                 node->next->prev = node->prev;
 574         node->parent = NULL;
 575         node->prev = NULL;
 576         node->next = NULL;
 577 }
 578
 579 static void tree_attach(struct exfat_node* dir, struct exfat_node* node)
 580 {
 581         node->parent = dir;
 582         if (dir->child)
 583         {
 584                 dir->child->prev = node;
 585                 node->next = dir->child;
 586         }
 587         dir->child = node;
 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                 if (existing->flags & EXFAT_ATTRIB_DIR)
 914                 {
 915                         if (node->flags & EXFAT_ATTRIB_DIR)
 916                                 rc = exfat_rmdir(ef, existing);
 917                         else
 918                                 rc = -ENOTDIR;
 919                 }
 920                 else
 921                 {
 922                         if (!(node->flags & EXFAT_ATTRIB_DIR))
 923                                 rc = exfat_unlink(ef, existing);
 924                         else
 925                                 rc = -EISDIR;
 926                 }
 927                 exfat_put_node(ef, existing);
 928                 if (rc != 0)
 929                 {
 930                         exfat_put_node(ef, dir);
 931                         exfat_put_node(ef, node);
 932                         return rc;
 933                 }
 934         }
 935
 936         rc = find_slot(ef, dir, &cluster, &offset,
 937                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 938         if (rc != 0)
 939         {
 940                 exfat_put_node(ef, dir);
 941                 exfat_put_node(ef, node);
 942                 return rc;
 943         }
 944         rename_entry(ef, dir, node, name, cluster, offset);
 945         exfat_put_node(ef, dir);
 946         exfat_put_node(ef, node);
 947         return 0;
 948 }
 949
 950 void exfat_utimes(struct exfat_node* node, const struct timespec tv[2])
 951 {
 952         node->atime = tv[0].tv_sec;
 953         node->mtime = tv[1].tv_sec;
 954         node->flags |= EXFAT_ATTRIB_DIRTY;
 955 }
 956
 957 void exfat_update_atime(struct exfat_node* node)
 958 {
 959         node->atime = time(NULL);
 960         node->flags |= EXFAT_ATTRIB_DIRTY;
 961 }
 962
 963 void exfat_update_mtime(struct exfat_node* node)
 964 {
 965         node->mtime = time(NULL);
 966         node->flags |= EXFAT_ATTRIB_DIRTY;
 967 }
 968
 969 const char* exfat_get_label(struct exfat* ef)
 970 {
 971         return ef->label;
 972 }
 973
 974 static int find_label(struct exfat* ef, cluster_t* cluster, off_t* offset)
 975 {
 976         struct iterator it;
 977         int rc;
 978
 979         rc = opendir(ef, ef->root, &it);
 980         if (rc != 0)
 981                 return rc;
 982
 983         for (;;)
 984         {
 985                 if (it.offset >= ef->root->size)
 986                 {
 987                         closedir(&it);
 988                         return -ENOENT;
 989                 }
 990
 991                 if (get_entry_ptr(ef, &it)->type == EXFAT_ENTRY_LABEL)
 992                 {
 993                         *cluster = it.cluster;
 994                         *offset = it.offset;
 995                         closedir(&it);
 996                         return 0;
 997                 }
 998
 999                 if (fetch_next_entry(ef, ef->root, &it) != 0)
1000                 {
1001                         closedir(&it);
1002                         return -EIO;
1003                 }
1004         }
1005 }
1006
1007 int exfat_set_label(struct exfat* ef, const char* label)
1008 {
1009         le16_t label_utf16[EXFAT_ENAME_MAX + 1];
1010         int rc;
1011         cluster_t cluster;
1012         off_t offset;
1013         struct exfat_entry_label entry;
1014
1015         memset(label_utf16, 0, sizeof(label_utf16));
1016         rc = utf8_to_utf16(label_utf16, label, EXFAT_ENAME_MAX, strlen(label));
1017         if (rc != 0)
1018                 return rc;
1019
1020         rc = find_label(ef, &cluster, &offset);
1021         if (rc == -ENOENT)
1022                 rc = find_slot(ef, ef->root, &cluster, &offset, 1);
1023         if (rc != 0)
1024                 return rc;
1025
1026         entry.type = EXFAT_ENTRY_LABEL;
1027         entry.length = utf16_length(label_utf16);
1028         memcpy(entry.name, label_utf16, sizeof(entry.name));
1029         if (entry.length == 0)
1030                 entry.type ^= EXFAT_ENTRY_VALID;
1031
1032         exfat_pwrite(ef->dev, &entry, sizeof(struct exfat_entry_label),
1033                         co2o(ef, cluster, offset));
1034         return 0;
1035 }