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