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                         break;
 352
 353                 default:
 354                         if (entry->type & EXFAT_ENTRY_VALID)
 355                         {
 356                                 exfat_error("unknown entry type 0x%hhu", entry->type);
 357                                 goto error;
 358                         }
 359                         break;
 360                 }
 361
 362                 if (fetch_next_entry(ef, parent, it) != 0)
 363                         goto error;
 364         }
 365         /* we never reach here */
 366
 367 error:
 368         free(*node);
 369         *node = NULL;
 370         return -EIO;
 371 }
 372
 373 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
 374 {
 375         struct iterator it;
 376         int rc;
 377         struct exfat_node* node;
 378         struct exfat_node* current = NULL;
 379
 380         if (dir->flags & EXFAT_ATTRIB_CACHED)
 381                 return 0; /* already cached */
 382
 383         rc = opendir(ef, dir, &it);
 384         if (rc != 0)
 385                 return rc;
 386         while ((rc = readdir(ef, dir, &node, &it)) == 0)
 387         {
 388                 node->parent = dir;
 389                 if (current != NULL)
 390                 {
 391                         current->next = node;
 392                         node->prev = current;
 393                 }
 394                 else
 395                         dir->child = node;
 396
 397                 current = node;
 398         }
 399         closedir(&it);
 400
 401         if (rc != -ENOENT)
 402         {
 403                 /* rollback */
 404                 for (current = dir->child; current; current = node)
 405                 {
 406                         node = current->next;
 407                         free(current);
 408                 }
 409                 dir->child = NULL;
 410                 return rc;
 411         }
 412
 413         dir->flags |= EXFAT_ATTRIB_CACHED;
 414         return 0;
 415 }
 416
 417 static void reset_cache(struct exfat* ef, struct exfat_node* node)
 418 {
 419         struct exfat_node* child;
 420         struct exfat_node* next;
 421
 422         for (child = node->child; child; child = next)
 423         {
 424                 reset_cache(ef, child);
 425                 next = child->next;
 426                 free(child);
 427         }
 428         if (node->references != 0)
 429         {
 430                 char buffer[EXFAT_NAME_MAX + 1];
 431                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
 432                 exfat_warn("non-zero reference counter (%d) for `%s'",
 433                                 node->references, buffer);
 434         }
 435         while (node->references--)
 436                 exfat_put_node(ef, node);
 437         node->child = NULL;
 438         node->flags &= ~EXFAT_ATTRIB_CACHED;
 439 }
 440
 441 void exfat_reset_cache(struct exfat* ef)
 442 {
 443         reset_cache(ef, ef->root);
 444 }
 445
 446 void next_entry(struct exfat* ef, const struct exfat_node* parent,
 447                 cluster_t* cluster, off_t* offset)
 448 {
 449         *offset += sizeof(struct exfat_entry);
 450         if (*offset % CLUSTER_SIZE(*ef->sb) == 0)
 451                 /* next cluster cannot be invalid */
 452                 *cluster = exfat_next_cluster(ef, parent, *cluster);
 453 }
 454
 455 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 456 {
 457         cluster_t cluster;
 458         off_t offset;
 459         off_t meta1_offset, meta2_offset;
 460         struct exfat_entry_meta1 meta1;
 461         struct exfat_entry_meta2 meta2;
 462
 463         if (ef->ro)
 464                 exfat_bug("unable to flush node to read-only FS");
 465
 466         if (node->parent == NULL)
 467                 return; /* do not flush unlinked node */
 468
 469         cluster = node->entry_cluster;
 470         offset = node->entry_offset;
 471         meta1_offset = co2o(ef, cluster, offset);
 472         next_entry(ef, node->parent, &cluster, &offset);
 473         meta2_offset = co2o(ef, cluster, offset);
 474
 475         exfat_read_raw(&meta1, sizeof(meta1), meta1_offset, ef->fd);
 476         if (meta1.type != EXFAT_ENTRY_FILE)
 477                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
 478         meta1.attrib = cpu_to_le16(node->flags);
 479         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime, &meta1.mtime_cs);
 480         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime, NULL);
 481
 482         exfat_read_raw(&meta2, sizeof(meta2), meta2_offset, ef->fd);
 483         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
 484                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
 485         meta2.size = meta2.real_size = cpu_to_le64(node->size);
 486         meta2.start_cluster = cpu_to_le32(node->start_cluster);
 487         /* empty files must be marked as fragmented */
 488         if (node->size != 0 && IS_CONTIGUOUS(*node))
 489                 meta2.flag = EXFAT_FLAG_CONTIGUOUS;
 490         else
 491                 meta2.flag = EXFAT_FLAG_FRAGMENTED;
 492         /* name hash remains unchanged, no need to recalculate it */
 493
 494         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 495
 496         exfat_write_raw(&meta1, sizeof(meta1), meta1_offset, ef->fd);
 497         exfat_write_raw(&meta2, sizeof(meta2), meta2_offset, ef->fd);
 498
 499         node->flags &= ~EXFAT_ATTRIB_DIRTY;
 500 }
 501
 502 static void erase_entry(struct exfat* ef, struct exfat_node* node)
 503 {
 504         cluster_t cluster = node->entry_cluster;
 505         off_t offset = node->entry_offset;
 506         int name_entries = DIV_ROUND_UP(utf16_length(node->name), EXFAT_ENAME_MAX);
 507         uint8_t entry_type;
 508
 509         entry_type = EXFAT_ENTRY_FILE & ~EXFAT_ENTRY_VALID;
 510         exfat_write_raw(&entry_type, 1, co2o(ef, cluster, offset), ef->fd);
 511
 512         next_entry(ef, node->parent, &cluster, &offset);
 513         entry_type = EXFAT_ENTRY_FILE_INFO & ~EXFAT_ENTRY_VALID;
 514         exfat_write_raw(&entry_type, 1, co2o(ef, cluster, offset), ef->fd);
 515
 516         while (name_entries--)
 517         {
 518                 next_entry(ef, node->parent, &cluster, &offset);
 519                 entry_type = EXFAT_ENTRY_FILE_NAME & ~EXFAT_ENTRY_VALID;
 520                 exfat_write_raw(&entry_type, 1, co2o(ef, cluster, offset), ef->fd);
 521         }
 522 }
 523
 524 static void tree_detach(struct exfat_node* node)
 525 {
 526         if (node->prev)
 527                 node->prev->next = node->next;
 528         else /* this is the first node in the list */
 529                 node->parent->child = node->next;
 530         if (node->next)
 531                 node->next->prev = node->prev;
 532         node->parent = NULL;
 533         node->prev = NULL;
 534         node->next = NULL;
 535 }
 536
 537 static void tree_attach(struct exfat_node* dir, struct exfat_node* node)
 538 {
 539         node->parent = dir;
 540         if (dir->child)
 541         {
 542                 dir->child->prev = node;
 543                 node->next = dir->child;
 544         }
 545         dir->child = node;
 546 }
 547
 548 static int shrink_directory(struct exfat* ef, struct exfat_node* dir,
 549                 off_t deleted_offset)
 550 {
 551         const struct exfat_node* node;
 552         const struct exfat_node* last_node;
 553         uint64_t entries = 1; /* a directory always has at leat 1 entry (EOD) */
 554         uint64_t new_size;
 555         struct exfat_entry eod;
 556         off_t eod_offset;
 557         int rc;
 558
 559         if (!(dir->flags & EXFAT_ATTRIB_DIR))
 560                 exfat_bug("attempted to shrink a file");
 561         if (!(dir->flags & EXFAT_ATTRIB_CACHED))
 562                 exfat_bug("attempted to shrink uncached directory");
 563
 564         for (last_node = node = dir->child; node; node = node->next)
 565         {
 566                 if (deleted_offset < node->entry_offset)
 567                 {
 568                         /* there are other entries after the removed one, no way to shrink
 569                            this directory */
 570                         return 0;
 571                 }
 572                 if (last_node->entry_offset < node->entry_offset)
 573                         last_node = node;
 574         }
 575
 576         if (last_node)
 577         {
 578                 /* offset of the last entry */
 579                 entries += last_node->entry_offset / sizeof(struct exfat_entry);
 580                 /* two subentries with meta info */
 581                 entries += 2;
 582                 /* subentries with file name */
 583                 entries += DIV_ROUND_UP(utf16_length(last_node->name),
 584                                 EXFAT_ENAME_MAX);
 585         }
 586
 587         new_size = DIV_ROUND_UP(entries * sizeof(struct exfat_entry),
 588                                  CLUSTER_SIZE(*ef->sb)) * CLUSTER_SIZE(*ef->sb);
 589         if (new_size == dir->size)
 590                 return 0;
 591         rc = exfat_truncate(ef, dir, new_size);
 592         if (rc != 0)
 593                 return rc;
 594
 595         /* put EOD entry at the end of the last cluster */
 596         memset(&eod, 0, sizeof(eod));
 597         eod_offset = new_size - sizeof(struct exfat_entry);
 598         if (last_node)
 599                 exfat_write_raw(&eod, sizeof(eod),
 600                                 co2o(ef, last_node->entry_cluster, eod_offset), ef->fd);
 601         else
 602                 exfat_write_raw(&eod, sizeof(eod),
 603                                 co2o(ef, dir->start_cluster, eod_offset), ef->fd);
 604         return 0;
 605 }
 606
 607 static int delete(struct exfat* ef, struct exfat_node* node)
 608 {
 609         struct exfat_node* parent = node->parent;
 610         off_t deleted_offset = node->entry_offset;
 611         int rc;
 612
 613         exfat_get_node(parent);
 614         erase_entry(ef, node);
 615         exfat_update_mtime(parent);
 616         tree_detach(node);
 617         rc = shrink_directory(ef, parent, deleted_offset);
 618         exfat_put_node(ef, parent);
 619         /* file clusters will be freed when node reference counter becomes 0 */
 620         node->flags |= EXFAT_ATTRIB_UNLINKED;
 621         return rc;
 622 }
 623
 624 int exfat_unlink(struct exfat* ef, struct exfat_node* node)
 625 {
 626         if (node->flags & EXFAT_ATTRIB_DIR)
 627                 return -EISDIR;
 628         return delete(ef, node);
 629 }
 630
 631 int exfat_rmdir(struct exfat* ef, struct exfat_node* node)
 632 {
 633         if (!(node->flags & EXFAT_ATTRIB_DIR))
 634                 return -ENOTDIR;
 635         /* check that directory is empty */
 636         exfat_cache_directory(ef, node);
 637         if (node->child)
 638                 return -ENOTEMPTY;
 639         return delete(ef, node);
 640 }
 641
 642 static int grow_directory(struct exfat* ef, struct exfat_node* dir,
 643                 uint64_t asize, uint32_t difference)
 644 {
 645         return exfat_truncate(ef, dir,
 646                         DIV_ROUND_UP(asize + difference, CLUSTER_SIZE(*ef->sb))
 647                                 * CLUSTER_SIZE(*ef->sb));
 648 }
 649
 650 static int find_slot(struct exfat* ef, struct exfat_node* dir,
 651                 cluster_t* cluster, off_t* offset, int subentries)
 652 {
 653         struct iterator it;
 654         int rc;
 655         const struct exfat_entry* entry;
 656         int contiguous = 0;
 657
 658         rc = opendir(ef, dir, &it);
 659         if (rc != 0)
 660                 return rc;
 661         for (;;)
 662         {
 663                 if (contiguous == 0)
 664                 {
 665                         *cluster = it.cluster;
 666                         *offset = it.offset;
 667                 }
 668                 entry = (const struct exfat_entry*)
 669                                 (it.chunk + it.offset % CLUSTER_SIZE(*ef->sb));
 670                 if (entry->type == EXFAT_ENTRY_EOD)
 671                 {
 672                         rc = grow_directory(ef, dir,
 673                                         it.offset + sizeof(struct exfat_entry), /* actual size */
 674                                         (subentries - contiguous) * sizeof(struct exfat_entry));
 675                         if (rc != 0)
 676                         {
 677                                 closedir(&it);
 678                                 return rc;
 679                         }
 680                         break;
 681                 }
 682                 if (entry->type & EXFAT_ENTRY_VALID)
 683                         contiguous = 0;
 684                 else
 685                         contiguous++;
 686                 if (contiguous == subentries)
 687                         break;  /* suitable slot it found */
 688                 if (fetch_next_entry(ef, dir, &it) != 0)
 689                 {
 690                         closedir(&it);
 691                         return -EIO;
 692                 }
 693         }
 694         closedir(&it);
 695         return 0;
 696 }
 697
 698 static int write_entry(struct exfat* ef, struct exfat_node* dir,
 699                 const le16_t* name, cluster_t cluster, off_t offset, uint16_t attrib)
 700 {
 701         struct exfat_node* node;
 702         struct exfat_entry_meta1 meta1;
 703         struct exfat_entry_meta2 meta2;
 704         const size_t name_length = utf16_length(name);
 705         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 706         int i;
 707
 708         node = allocate_node();
 709         if (node == NULL)
 710                 return -ENOMEM;
 711         node->entry_cluster = cluster;
 712         node->entry_offset = offset;
 713         memcpy(node->name, name, name_length * sizeof(le16_t));
 714
 715         memset(&meta1, 0, sizeof(meta1));
 716         meta1.type = EXFAT_ENTRY_FILE;
 717         meta1.continuations = 1 + name_entries;
 718         meta1.attrib = cpu_to_le16(attrib);
 719         exfat_unix2exfat(time(NULL), &meta1.crdate, &meta1.crtime,
 720                         &meta1.crtime_cs);
 721         meta1.adate = meta1.mdate = meta1.crdate;
 722         meta1.atime = meta1.mtime = meta1.crtime;
 723         /* crtime_cs and mtime_cs contain addition to the time in centiseconds;
 724            just ignore those fields because we operate with 2 sec resolution */
 725
 726         memset(&meta2, 0, sizeof(meta2));
 727         meta2.type = EXFAT_ENTRY_FILE_INFO;
 728         meta2.flag = EXFAT_FLAG_FRAGMENTED;
 729         meta2.name_length = name_length;
 730         meta2.name_hash = exfat_calc_name_hash(ef, node->name);
 731         meta2.start_cluster = cpu_to_le32(EXFAT_CLUSTER_FREE);
 732
 733         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
 734
 735         exfat_write_raw(&meta1, sizeof(meta1), co2o(ef, cluster, offset), ef->fd);
 736         next_entry(ef, dir, &cluster, &offset);
 737         exfat_write_raw(&meta2, sizeof(meta2), co2o(ef, cluster, offset), ef->fd);
 738         for (i = 0; i < name_entries; i++)
 739         {
 740                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
 741                 memcpy(name_entry.name, node->name + i * EXFAT_ENAME_MAX,
 742                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 743                 next_entry(ef, dir, &cluster, &offset);
 744                 exfat_write_raw(&name_entry, sizeof(name_entry),
 745                                 co2o(ef, cluster, offset), ef->fd);
 746         }
 747
 748         init_node_meta1(node, &meta1);
 749         init_node_meta2(node, &meta2);
 750
 751         tree_attach(dir, node);
 752         exfat_update_mtime(dir);
 753         return 0;
 754 }
 755
 756 static int create(struct exfat* ef, const char* path, uint16_t attrib)
 757 {
 758         struct exfat_node* dir;
 759         struct exfat_node* existing;
 760         cluster_t cluster = EXFAT_CLUSTER_BAD;
 761         off_t offset = -1;
 762         le16_t name[EXFAT_NAME_MAX + 1];
 763         int rc;
 764
 765         rc = exfat_split(ef, &dir, &existing, name, path);
 766         if (rc != 0)
 767                 return rc;
 768         if (existing != NULL)
 769         {
 770                 exfat_put_node(ef, existing);
 771                 exfat_put_node(ef, dir);
 772                 return -EEXIST;
 773         }
 774
 775         rc = find_slot(ef, dir, &cluster, &offset,
 776                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 777         if (rc != 0)
 778         {
 779                 exfat_put_node(ef, dir);
 780                 return rc;
 781         }
 782         rc = write_entry(ef, dir, name, cluster, offset, attrib);
 783         exfat_put_node(ef, dir);
 784         return rc;
 785 }
 786
 787 int exfat_mknod(struct exfat* ef, const char* path)
 788 {
 789         return create(ef, path, EXFAT_ATTRIB_ARCH);
 790 }
 791
 792 int exfat_mkdir(struct exfat* ef, const char* path)
 793 {
 794         int rc;
 795         struct exfat_node* node;
 796
 797         rc = create(ef, path, EXFAT_ATTRIB_ARCH | EXFAT_ATTRIB_DIR);
 798         if (rc != 0)
 799                 return rc;
 800         rc = exfat_lookup(ef, &node, path);
 801         if (rc != 0)
 802                 return 0;
 803         /* directories always have at least one cluster */
 804         rc = exfat_truncate(ef, node, CLUSTER_SIZE(*ef->sb));
 805         if (rc != 0)
 806         {
 807                 delete(ef, node);
 808                 exfat_put_node(ef, node);
 809                 return rc;
 810         }
 811         exfat_put_node(ef, node);
 812         return 0;
 813 }
 814
 815 static void rename_entry(struct exfat* ef, struct exfat_node* dir,
 816                 struct exfat_node* node, const le16_t* name, cluster_t new_cluster,
 817                 off_t new_offset)
 818 {
 819         struct exfat_entry_meta1 meta1;
 820         struct exfat_entry_meta2 meta2;
 821         cluster_t old_cluster = node->entry_cluster;
 822         off_t old_offset = node->entry_offset;
 823         const size_t name_length = utf16_length(name);
 824         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 825         int i;
 826
 827         exfat_read_raw(&meta1, sizeof(meta1), co2o(ef, old_cluster, old_offset),
 828                         ef->fd);
 829         next_entry(ef, node->parent, &old_cluster, &old_offset);
 830         exfat_read_raw(&meta2, sizeof(meta2), co2o(ef, old_cluster, old_offset),
 831                         ef->fd);
 832         meta1.continuations = 1 + name_entries;
 833         meta2.name_hash = exfat_calc_name_hash(ef, name);
 834         meta2.name_length = name_length;
 835         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, name);
 836
 837         erase_entry(ef, node);
 838
 839         node->entry_cluster = new_cluster;
 840         node->entry_offset = new_offset;
 841
 842         exfat_write_raw(&meta1, sizeof(meta1), co2o(ef, new_cluster, new_offset),
 843                         ef->fd);
 844         next_entry(ef, dir, &new_cluster, &new_offset);
 845         exfat_write_raw(&meta2, sizeof(meta2), co2o(ef, new_cluster, new_offset),
 846                         ef->fd);
 847
 848         for (i = 0; i < name_entries; i++)
 849         {
 850                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
 851                 memcpy(name_entry.name, name + i * EXFAT_ENAME_MAX,
 852                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 853                 next_entry(ef, dir, &new_cluster, &new_offset);
 854                 exfat_write_raw(&name_entry, sizeof(name_entry),
 855                                 co2o(ef, new_cluster, new_offset), ef->fd);
 856         }
 857
 858         memcpy(node->name, name, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
 859         tree_detach(node);
 860         tree_attach(dir, node);
 861 }
 862
 863 int exfat_rename(struct exfat* ef, const char* old_path, const char* new_path)
 864 {
 865         struct exfat_node* node;
 866         struct exfat_node* existing;
 867         struct exfat_node* dir;
 868         cluster_t cluster = EXFAT_CLUSTER_BAD;
 869         off_t offset = -1;
 870         le16_t name[EXFAT_NAME_MAX + 1];
 871         int rc;
 872
 873         rc = exfat_lookup(ef, &node, old_path);
 874         if (rc != 0)
 875                 return rc;
 876
 877         rc = exfat_split(ef, &dir, &existing, name, new_path);
 878         if (rc != 0)
 879         {
 880                 exfat_put_node(ef, node);
 881                 return rc;
 882         }
 883         if (existing != NULL)
 884         {
 885                 if (existing->flags & EXFAT_ATTRIB_DIR)
 886                 {
 887                         if (node->flags & EXFAT_ATTRIB_DIR)
 888                                 rc = exfat_rmdir(ef, existing);
 889                         else
 890                                 rc = -ENOTDIR;
 891                 }
 892                 else
 893                 {
 894                         if (!(node->flags & EXFAT_ATTRIB_DIR))
 895                                 rc = exfat_unlink(ef, existing);
 896                         else
 897                                 rc = -EISDIR;
 898                 }
 899                 exfat_put_node(ef, existing);
 900                 if (rc != 0)
 901                 {
 902                         exfat_put_node(ef, dir);
 903                         exfat_put_node(ef, node);
 904                         return rc;
 905                 }
 906         }
 907
 908         rc = find_slot(ef, dir, &cluster, &offset,
 909                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 910         if (rc != 0)
 911         {
 912                 exfat_put_node(ef, dir);
 913                 exfat_put_node(ef, node);
 914                 return rc;
 915         }
 916         rename_entry(ef, dir, node, name, cluster, offset);
 917         exfat_put_node(ef, dir);
 918         exfat_put_node(ef, node);
 919         return 0;
 920 }
 921
 922 void exfat_utimes(struct exfat_node* node, const struct timespec tv[2])
 923 {
 924         node->atime = tv[0].tv_sec;
 925         node->mtime = tv[1].tv_sec;
 926         node->flags |= EXFAT_ATTRIB_DIRTY;
 927 }
 928
 929 void exfat_update_atime(struct exfat_node* node)
 930 {
 931         node->atime = time(NULL);
 932         node->flags |= EXFAT_ATTRIB_DIRTY;
 933 }
 934
 935 void exfat_update_mtime(struct exfat_node* node)
 936 {
 937         node->mtime = time(NULL);
 938         node->flags |= EXFAT_ATTRIB_DIRTY;
 939 }