libexfat/node.c

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