libexfat/node.c

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