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