libexfat/node.c

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