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