libexfat/node.c

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