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