libexfat/node.c

   1 /*
   2         node.c (09.10.09)
   3         exFAT file system implementation library.
   4
   5         Free exFAT implementation.
   6         Copyright (C) 2010-2017  Andrew Nayenko
   7
   8         This program is free software; you can redistribute it and/or modify
   9         it under the terms of the GNU General Public License as published by
  10         the Free Software Foundation, either version 2 of the License, or
  11         (at your option) any later version.
  12
  13         This program is distributed in the hope that it will be useful,
  14         but WITHOUT ANY WARRANTY; without even the implied warranty of
  15         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16         GNU General Public License for more details.
  17
  18         You should have received a copy of the GNU General Public License along
  19         with this program; if not, write to the Free Software Foundation, Inc.,
  20         51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21 */
  22
  23 #include "exfat.h"
  24 #include <errno.h>
  25 #include <string.h>
  26 #include <inttypes.h>
  27
  28 #define EXFAT_ENTRY_NONE (-1)
  29
  30 struct exfat_node* exfat_get_node(struct exfat_node* node)
  31 {
  32         /* if we switch to multi-threaded mode we will need atomic
  33            increment here and atomic decrement in exfat_put_node() */
  34         node->references++;
  35         return node;
  36 }
  37
  38 void exfat_put_node(struct exfat* ef, struct exfat_node* node)
  39 {
  40         char buffer[EXFAT_UTF8_NAME_BUFFER_MAX];
  41
  42         --node->references;
  43         if (node->references < 0)
  44         {
  45                 exfat_get_name(node, buffer);
  46                 exfat_bug("reference counter of '%s' is below zero", buffer);
  47         }
  48         else if (node->references == 0 && node != ef->root)
  49         {
  50                 if (node->is_dirty)
  51                 {
  52                         exfat_get_name(node, buffer);
  53                         exfat_warn("dirty node '%s' with zero references", buffer);
  54                 }
  55         }
  56 }
  57
  58 /**
  59  * This function must be called on rmdir and unlink (after the last
  60  * exfat_put_node()) to free clusters.
  61  */
  62 int exfat_cleanup_node(struct exfat* ef, struct exfat_node* node)
  63 {
  64         int rc = 0;
  65
  66         if (node->references != 0)
  67                 exfat_bug("unable to cleanup a node with %d references",
  68                                 node->references);
  69
  70         if (node->is_unlinked)
  71         {
  72                 /* free all clusters and node structure itself */
  73                 rc = exfat_truncate(ef, node, 0, true);
  74                 /* free the node even in case of error or its memory will be lost */
  75                 free(node);
  76         }
  77         return rc;
  78 }
  79
  80 static int read_entries(struct exfat* ef, struct exfat_node* dir,
  81                 struct exfat_entry* entries, int n, off_t offset)
  82 {
  83         ssize_t size;
  84
  85         if (!(dir->attrib & EXFAT_ATTRIB_DIR))
  86                 exfat_bug("attempted to read entries from a file");
  87
  88         size = exfat_generic_pread(ef, dir, entries,
  89                         sizeof(struct exfat_entry[n]), offset);
  90         if (size == sizeof(struct exfat_entry[n]))
  91                 return 0; /* success */
  92         if (size == 0)
  93                 return -ENOENT;
  94         if (size < 0)
  95                 return -EIO;
  96         exfat_error("read %zd bytes instead of %zu bytes", size,
  97                         sizeof(struct exfat_entry[n]));
  98         return -EIO;
  99 }
 100
 101 static int write_entries(struct exfat* ef, struct exfat_node* dir,
 102                 const struct exfat_entry* entries, int n, off_t offset)
 103 {
 104         ssize_t size;
 105
 106         if (!(dir->attrib & EXFAT_ATTRIB_DIR))
 107                 exfat_bug("attempted to write entries into a file");
 108
 109         size = exfat_generic_pwrite(ef, dir, entries,
 110                         sizeof(struct exfat_entry[n]), offset);
 111         if (size == sizeof(struct exfat_entry[n]))
 112                 return 0; /* success */
 113         if (size < 0)
 114                 return -EIO;
 115         exfat_error("wrote %zd bytes instead of %zu bytes", size,
 116                         sizeof(struct exfat_entry[n]));
 117         return -EIO;
 118 }
 119
 120 static struct exfat_node* allocate_node(void)
 121 {
 122         struct exfat_node* node = malloc(sizeof(struct exfat_node));
 123         if (node == NULL)
 124         {
 125                 exfat_error("failed to allocate node");
 126                 return NULL;
 127         }
 128         memset(node, 0, sizeof(struct exfat_node));
 129         return node;
 130 }
 131
 132 static void init_node_meta1(struct exfat_node* node,
 133                 const struct exfat_entry_meta1* meta1)
 134 {
 135         node->attrib = le16_to_cpu(meta1->attrib);
 136         node->continuations = meta1->continuations;
 137         node->mtime = exfat_exfat2unix(meta1->mdate, meta1->mtime,
 138                         meta1->mtime_cs);
 139         /* there is no centiseconds field for atime */
 140         node->atime = exfat_exfat2unix(meta1->adate, meta1->atime, 0);
 141 }
 142
 143 static void init_node_meta2(struct exfat_node* node,
 144                 const struct exfat_entry_meta2* meta2)
 145 {
 146         node->size = le64_to_cpu(meta2->size);
 147         node->start_cluster = le32_to_cpu(meta2->start_cluster);
 148         node->fptr_cluster = node->start_cluster;
 149         node->is_contiguous = ((meta2->flags & EXFAT_FLAG_CONTIGUOUS) != 0);
 150 }
 151
 152 static void init_node_name(struct exfat_node* node,
 153                 const struct exfat_entry* entries, int n)
 154 {
 155         int i;
 156
 157         for (i = 0; i < n; i++)
 158                 memcpy(node->name + i * EXFAT_ENAME_MAX,
 159                                 ((const struct exfat_entry_name*) &entries[i])->name,
 160                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 161 }
 162
 163 static bool check_entries(const struct exfat_entry* entry, int n)
 164 {
 165         int previous = EXFAT_ENTRY_NONE;
 166         int current;
 167         int i;
 168
 169         /* check transitions between entries types */
 170         for (i = 0; i < n + 1; previous = current, i++)
 171         {
 172                 bool valid = false;
 173
 174                 current = (i < n) ? entry[i].type : EXFAT_ENTRY_NONE;
 175                 switch (previous)
 176                 {
 177                 case EXFAT_ENTRY_NONE:
 178                         valid = (current == EXFAT_ENTRY_FILE);
 179                         break;
 180                 case EXFAT_ENTRY_FILE:
 181                         valid = (current == EXFAT_ENTRY_FILE_INFO);
 182                         break;
 183                 case EXFAT_ENTRY_FILE_INFO:
 184                         valid = (current == EXFAT_ENTRY_FILE_NAME);
 185                         break;
 186                 case EXFAT_ENTRY_FILE_NAME:
 187                         valid = (current == EXFAT_ENTRY_FILE_NAME ||
 188                                  current == EXFAT_ENTRY_NONE ||
 189                                  current >= EXFAT_ENTRY_FILE_TAIL);
 190                         break;
 191                 case EXFAT_ENTRY_FILE_TAIL ... 0xff:
 192                         valid = (current >= EXFAT_ENTRY_FILE_TAIL ||
 193                                  current == EXFAT_ENTRY_NONE);
 194                         break;
 195                 }
 196
 197                 if (!valid)
 198                 {
 199                         exfat_error("unexpected entry type %#x after %#x at %d/%d",
 200                                         current, previous, i, n);
 201                         return false;
 202                 }
 203         }
 204         return true;
 205 }
 206
 207 static bool check_node(const struct exfat* ef, struct exfat_node* node,
 208                 le16_t actual_checksum, const struct exfat_entry_meta1* meta1,
 209                 const struct exfat_entry_meta2* meta2)
 210 {
 211         int cluster_size = CLUSTER_SIZE(*ef->sb);
 212         uint64_t clusters_heap_size =
 213                         (uint64_t) le32_to_cpu(ef->sb->cluster_count) * cluster_size;
 214         char buffer[EXFAT_UTF8_NAME_BUFFER_MAX];
 215         bool ret = true;
 216
 217         /*
 218            Validate checksum first. If it's invalid all other fields probably
 219            contain just garbage.
 220         */
 221         if (le16_to_cpu(actual_checksum) != le16_to_cpu(meta1->checksum))
 222         {
 223                 exfat_get_name(node, buffer);
 224                 exfat_error("'%s' has invalid checksum (%#hx != %#hx)", buffer,
 225                                 le16_to_cpu(actual_checksum), le16_to_cpu(meta1->checksum));
 226                 ret = false;
 227         }
 228
 229         /*
 230            exFAT does not support sparse files but allows files with uninitialized
 231            clusters. For such files valid_size means initialized data size and
 232            cannot be greater than file size. See SetFileValidData() function
 233            description in MSDN.
 234         */
 235         if (le64_to_cpu(meta2->valid_size) > node->size)
 236         {
 237                 exfat_get_name(node, buffer);
 238                 exfat_error("'%s' has valid size (%"PRIu64") greater than size "
 239                                 "(%"PRIu64")", buffer, le64_to_cpu(meta2->valid_size),
 240                                 node->size);
 241                 ret = false;
 242         }
 243
 244         /*
 245            Empty file must have zero start cluster. Non-empty file must start
 246            with a valid cluster. Directories cannot be empty (i.e. must always
 247            have a valid start cluster), but we will check this later while
 248            reading that directory to give user a chance to read this directory.
 249         */
 250         if (node->size == 0 && node->start_cluster != EXFAT_CLUSTER_FREE)
 251         {
 252                 exfat_get_name(node, buffer);
 253                 exfat_error("'%s' is empty but start cluster is %#x", buffer,
 254                                 node->start_cluster);
 255                 ret = false;
 256         }
 257         if (node->size > 0 && CLUSTER_INVALID(*ef->sb, node->start_cluster))
 258         {
 259                 exfat_get_name(node, buffer);
 260                 exfat_error("'%s' points to invalid cluster %#x", buffer,
 261                                 node->start_cluster);
 262                 ret = false;
 263         }
 264
 265         /* File or directory cannot be larger than clusters heap. */
 266         if (node->size > clusters_heap_size)
 267         {
 268                 exfat_get_name(node, buffer);
 269                 exfat_error("'%s' is larger than clusters heap: %"PRIu64" > %"PRIu64,
 270                                 buffer, node->size, clusters_heap_size);
 271                 ret = false;
 272         }
 273
 274         /* Empty file or directory must be marked as non-contiguous. */
 275         if (node->size == 0 && node->is_contiguous)
 276         {
 277                 exfat_get_name(node, buffer);
 278                 exfat_error("'%s' is empty but marked as contiguous (%#hx)", buffer,
 279                                 node->attrib);
 280                 ret = false;
 281         }
 282
 283         /* Directory size must be aligned on at cluster boundary. */
 284         if ((node->attrib & EXFAT_ATTRIB_DIR) && node->size % cluster_size != 0)
 285         {
 286                 exfat_get_name(node, buffer);
 287                 exfat_error("'%s' directory size %"PRIu64" is not divisible by %d", buffer,
 288                                 node->size, cluster_size);
 289                 ret = false;
 290         }
 291
 292         return ret;
 293 }
 294
 295 static int parse_file_entries(struct exfat* ef, struct exfat_node* node,
 296                 const struct exfat_entry* entries, int n)
 297 {
 298         const struct exfat_entry_meta1* meta1;
 299         const struct exfat_entry_meta2* meta2;
 300         int mandatory_entries;
 301
 302         if (!check_entries(entries, n))
 303                 return -EIO;
 304
 305         meta1 = (const struct exfat_entry_meta1*) &entries[0];
 306         if (meta1->continuations < 2)
 307         {
 308                 exfat_error("too few continuations (%hhu)", meta1->continuations);
 309                 return -EIO;
 310         }
 311         meta2 = (const struct exfat_entry_meta2*) &entries[1];
 312         if (meta2->flags & ~(EXFAT_FLAG_ALWAYS1 | EXFAT_FLAG_CONTIGUOUS))
 313         {
 314                 exfat_error("unknown flags in meta2 (%#hhx)", meta2->flags);
 315                 return -EIO;
 316         }
 317         mandatory_entries = 2 + DIV_ROUND_UP(meta2->name_length, EXFAT_ENAME_MAX);
 318         if (meta1->continuations < mandatory_entries - 1)
 319         {
 320                 exfat_error("too few continuations (%hhu < %d)",
 321                                 meta1->continuations, mandatory_entries - 1);
 322                 return -EIO;
 323         }
 324
 325         init_node_meta1(node, meta1);
 326         init_node_meta2(node, meta2);
 327         init_node_name(node, entries + 2, mandatory_entries - 2);
 328
 329         if (!check_node(ef, node, exfat_calc_checksum(entries, n), meta1, meta2))
 330                 return -EIO;
 331
 332         return 0;
 333 }
 334
 335 static int parse_file_entry(struct exfat* ef, struct exfat_node* parent,
 336                 struct exfat_node** node, off_t* offset, int n)
 337 {
 338         struct exfat_entry entries[n];
 339         int rc;
 340
 341         rc = read_entries(ef, parent, entries, n, *offset);
 342         if (rc != 0)
 343                 return rc;
 344
 345         /* a new node has zero references */
 346         *node = allocate_node();
 347         if (*node == NULL)
 348                 return -ENOMEM;
 349         (*node)->entry_offset = *offset;
 350
 351         rc = parse_file_entries(ef, *node, entries, n);
 352         if (rc != 0)
 353         {
 354                 free(*node);
 355                 return rc;
 356         }
 357
 358         *offset += sizeof(struct exfat_entry[n]);
 359         return 0;
 360 }
 361
 362 static void decompress_upcase(uint16_t* output, const le16_t* source,
 363                 size_t size)
 364 {
 365         size_t si;
 366         size_t oi;
 367
 368         for (oi = 0; oi < EXFAT_UPCASE_CHARS; oi++)
 369                 output[oi] = oi;
 370
 371         for (si = 0, oi = 0; si < size && oi < EXFAT_UPCASE_CHARS; si++)
 372         {
 373                 uint16_t ch = le16_to_cpu(source[si]);
 374
 375                 if (ch == 0xffff && si + 1 < size)      /* indicates a run */
 376                         oi += le16_to_cpu(source[++si]);
 377                 else
 378                         output[oi++] = ch;
 379         }
 380 }
 381
 382 /*
 383  * Read one entry in a directory at offset position and build a new node
 384  * structure.
 385  */
 386 static int readdir(struct exfat* ef, struct exfat_node* parent,
 387                 struct exfat_node** node, off_t* offset)
 388 {
 389         int rc;
 390         struct exfat_entry entry;
 391         const struct exfat_entry_meta1* meta1;
 392         const struct exfat_entry_upcase* upcase;
 393         const struct exfat_entry_bitmap* bitmap;
 394         const struct exfat_entry_label* label;
 395         uint64_t upcase_size = 0;
 396         le16_t* upcase_comp = NULL;
 397
 398         for (;;)
 399         {
 400                 rc = read_entries(ef, parent, &entry, 1, *offset);
 401                 if (rc != 0)
 402                         return rc;
 403
 404                 switch (entry.type)
 405                 {
 406                 case EXFAT_ENTRY_FILE:
 407                         meta1 = (const struct exfat_entry_meta1*) &entry;
 408                         return parse_file_entry(ef, parent, node, offset,
 409                                         1 + meta1->continuations);
 410
 411                 case EXFAT_ENTRY_UPCASE:
 412                         if (ef->upcase != NULL)
 413                                 break;
 414                         upcase = (const struct exfat_entry_upcase*) &entry;
 415                         if (CLUSTER_INVALID(*ef->sb, le32_to_cpu(upcase->start_cluster)))
 416                         {
 417                                 exfat_error("invalid cluster 0x%x in upcase table",
 418                                                 le32_to_cpu(upcase->start_cluster));
 419                                 return -EIO;
 420                         }
 421                         upcase_size = le64_to_cpu(upcase->size);
 422                         if (upcase_size == 0 ||
 423                                 upcase_size > EXFAT_UPCASE_CHARS * sizeof(uint16_t) ||
 424                                 upcase_size % sizeof(uint16_t) != 0)
 425                         {
 426                                 exfat_error("bad upcase table size (%"PRIu64" bytes)",
 427                                                 upcase_size);
 428                                 return -EIO;
 429                         }
 430                         upcase_comp = malloc(upcase_size);
 431                         if (upcase_comp == NULL)
 432                         {
 433                                 exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
 434                                                 upcase_size);
 435                                 return -ENOMEM;
 436                         }
 437
 438                         /* read compressed upcase table */
 439                         if (exfat_pread(ef->dev, upcase_comp, upcase_size,
 440                                         exfat_c2o(ef, le32_to_cpu(upcase->start_cluster))) < 0)
 441                         {
 442                                 free(upcase_comp);
 443                                 exfat_error("failed to read upper case table "
 444                                                 "(%"PRIu64" bytes starting at cluster %#x)",
 445                                                 upcase_size,
 446                                                 le32_to_cpu(upcase->start_cluster));
 447                                 return -EIO;
 448                         }
 449
 450                         /* decompress upcase table */
 451                         ef->upcase = calloc(EXFAT_UPCASE_CHARS, sizeof(uint16_t));
 452                         if (ef->upcase == NULL)
 453                         {
 454                                 free(upcase_comp);
 455                                 exfat_error("failed to allocate decompressed upcase table");
 456                                 return -ENOMEM;
 457                         }
 458                         decompress_upcase(ef->upcase, upcase_comp,
 459                                         upcase_size / sizeof(uint16_t));
 460                         free(upcase_comp);
 461                         break;
 462
 463                 case EXFAT_ENTRY_BITMAP:
 464                         bitmap = (const struct exfat_entry_bitmap*) &entry;
 465                         ef->cmap.start_cluster = le32_to_cpu(bitmap->start_cluster);
 466                         if (CLUSTER_INVALID(*ef->sb, ef->cmap.start_cluster))
 467                         {
 468                                 exfat_error("invalid cluster 0x%x in clusters bitmap",
 469                                                 ef->cmap.start_cluster);
 470                                 return -EIO;
 471                         }
 472                         ef->cmap.size = le32_to_cpu(ef->sb->cluster_count);
 473                         if (le64_to_cpu(bitmap->size) < DIV_ROUND_UP(ef->cmap.size, 8))
 474                         {
 475                                 exfat_error("invalid clusters bitmap size: %"PRIu64
 476                                                 " (expected at least %u)",
 477                                                 le64_to_cpu(bitmap->size),
 478                                                 DIV_ROUND_UP(ef->cmap.size, 8));
 479                                 return -EIO;
 480                         }
 481                         /* FIXME bitmap can be rather big, up to 512 MB */
 482                         ef->cmap.chunk_size = ef->cmap.size;
 483                         ef->cmap.chunk = malloc(BMAP_SIZE(ef->cmap.chunk_size));
 484                         if (ef->cmap.chunk == NULL)
 485                         {
 486                                 exfat_error("failed to allocate clusters bitmap chunk "
 487                                                 "(%"PRIu64" bytes)", le64_to_cpu(bitmap->size));
 488                                 return -ENOMEM;
 489                         }
 490
 491                         if (exfat_pread(ef->dev, ef->cmap.chunk,
 492                                         BMAP_SIZE(ef->cmap.chunk_size),
 493                                         exfat_c2o(ef, ef->cmap.start_cluster)) < 0)
 494                         {
 495                                 exfat_error("failed to read clusters bitmap "
 496                                                 "(%"PRIu64" bytes starting at cluster %#x)",
 497                                                 le64_to_cpu(bitmap->size), ef->cmap.start_cluster);
 498                                 return -EIO;
 499                         }
 500                         break;
 501
 502                 case EXFAT_ENTRY_LABEL:
 503                         label = (const struct exfat_entry_label*) &entry;
 504                         if (label->length > EXFAT_ENAME_MAX)
 505                         {
 506                                 exfat_error("too long label (%hhu chars)", label->length);
 507                                 return -EIO;
 508                         }
 509                         if (utf16_to_utf8(ef->label, label->name,
 510                                                 sizeof(ef->label), EXFAT_ENAME_MAX) != 0)
 511                                 return -EIO;
 512                         break;
 513
 514                 default:
 515                         if (!(entry.type & EXFAT_ENTRY_VALID))
 516                                 break; /* deleted entry, ignore it */
 517
 518                         exfat_error("unknown entry type %#hhx", entry.type);
 519                         return -EIO;
 520                 }
 521                 *offset += sizeof(entry);
 522         }
 523         /* we never reach here */
 524 }
 525
 526 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
 527 {
 528         off_t offset = 0;
 529         int rc;
 530         struct exfat_node* node;
 531         struct exfat_node* current = NULL;
 532
 533         if (dir->is_cached)
 534                 return 0; /* already cached */
 535
 536         while ((rc = readdir(ef, dir, &node, &offset)) == 0)
 537         {
 538                 node->parent = dir;
 539                 if (current != NULL)
 540                 {
 541                         current->next = node;
 542                         node->prev = current;
 543                 }
 544                 else
 545                         dir->child = node;
 546
 547                 current = node;
 548         }
 549
 550         if (rc != -ENOENT)
 551         {
 552                 /* rollback */
 553                 for (current = dir->child; current; current = node)
 554                 {
 555                         node = current->next;
 556                         free(current);
 557                 }
 558                 dir->child = NULL;
 559                 return rc;
 560         }
 561
 562         dir->is_cached = true;
 563         return 0;
 564 }
 565
 566 static void tree_attach(struct exfat_node* dir, struct exfat_node* node)
 567 {
 568         node->parent = dir;
 569         if (dir->child)
 570         {
 571                 dir->child->prev = node;
 572                 node->next = dir->child;
 573         }
 574         dir->child = node;
 575 }
 576
 577 static void tree_detach(struct exfat_node* node)
 578 {
 579         if (node->prev)
 580                 node->prev->next = node->next;
 581         else /* this is the first node in the list */
 582                 node->parent->child = node->next;
 583         if (node->next)
 584                 node->next->prev = node->prev;
 585         node->parent = NULL;
 586         node->prev = NULL;
 587         node->next = NULL;
 588 }
 589
 590 static void reset_cache(struct exfat* ef, struct exfat_node* node)
 591 {
 592         char buffer[EXFAT_UTF8_NAME_BUFFER_MAX];
 593
 594         while (node->child)
 595         {
 596                 struct exfat_node* p = node->child;
 597                 reset_cache(ef, p);
 598                 tree_detach(p);
 599                 free(p);
 600         }
 601         node->is_cached = false;
 602         if (node->references != 0)
 603         {
 604                 exfat_get_name(node, buffer);
 605                 exfat_warn("non-zero reference counter (%d) for '%s'",
 606                                 node->references, buffer);
 607         }
 608         if (node != ef->root && node->is_dirty)
 609         {
 610                 exfat_get_name(node, buffer);
 611                 exfat_bug("node '%s' is dirty", buffer);
 612         }
 613         while (node->references)
 614                 exfat_put_node(ef, node);
 615 }
 616
 617 void exfat_reset_cache(struct exfat* ef)
 618 {
 619         reset_cache(ef, ef->root);
 620 }
 621
 622 int exfat_flush_node(struct exfat* ef, struct exfat_node* node)
 623 {
 624         struct exfat_entry entries[1 + node->continuations];
 625         struct exfat_entry_meta1* meta1 = (struct exfat_entry_meta1*) &entries[0];
 626         struct exfat_entry_meta2* meta2 = (struct exfat_entry_meta2*) &entries[1];
 627         int rc;
 628
 629         if (!node->is_dirty)
 630                 return 0; /* no need to flush */
 631
 632         if (ef->ro)
 633                 exfat_bug("unable to flush node to read-only FS");
 634
 635         if (node->parent == NULL)
 636                 return 0; /* do not flush unlinked node */
 637
 638         rc = read_entries(ef, node->parent, entries, 1 + node->continuations,
 639                         node->entry_offset);
 640         if (rc != 0)
 641                 return rc;
 642         if (!check_entries(entries, 1 + node->continuations))
 643                 return -EIO;
 644
 645         meta1->attrib = cpu_to_le16(node->attrib);
 646         exfat_unix2exfat(node->mtime, &meta1->mdate, &meta1->mtime,
 647                         &meta1->mtime_cs);
 648         exfat_unix2exfat(node->atime, &meta1->adate, &meta1->atime, NULL);
 649         meta2->size = meta2->valid_size = cpu_to_le64(node->size);
 650         meta2->start_cluster = cpu_to_le32(node->start_cluster);
 651         meta2->flags = EXFAT_FLAG_ALWAYS1;
 652         /* empty files must not be marked as contiguous */
 653         if (node->size != 0 && node->is_contiguous)
 654                 meta2->flags |= EXFAT_FLAG_CONTIGUOUS;
 655         /* name hash remains unchanged, no need to recalculate it */
 656
 657         meta1->checksum = exfat_calc_checksum(entries, 1 + node->continuations);
 658         rc = write_entries(ef, node->parent, entries, 1 + node->continuations,
 659                         node->entry_offset);
 660         if (rc != 0)
 661                 return rc;
 662
 663         node->is_dirty = false;
 664         return exfat_flush(ef);
 665 }
 666
 667 static int erase_entries(struct exfat* ef, struct exfat_node* dir, int n,
 668                 off_t offset)
 669 {
 670         struct exfat_entry entries[n];
 671         int rc;
 672         int i;
 673
 674         rc = read_entries(ef, dir, entries, n, offset);
 675         if (rc != 0)
 676                 return rc;
 677         for (i = 0; i < n; i++)
 678                 entries[i].type &= ~EXFAT_ENTRY_VALID;
 679         return write_entries(ef, dir, entries, n, offset);
 680 }
 681
 682 static int erase_node(struct exfat* ef, struct exfat_node* node)
 683 {
 684         int rc;
 685
 686         exfat_get_node(node->parent);
 687         rc = erase_entries(ef, node->parent, 1 + node->continuations,
 688                         node->entry_offset);
 689         if (rc != 0)
 690         {
 691                 exfat_put_node(ef, node->parent);
 692                 return rc;
 693         }
 694         rc = exfat_flush_node(ef, node->parent);
 695         exfat_put_node(ef, node->parent);
 696         return rc;
 697 }
 698
 699 static int shrink_directory(struct exfat* ef, struct exfat_node* dir,
 700                 off_t deleted_offset)
 701 {
 702         const struct exfat_node* node;
 703         const struct exfat_node* last_node;
 704         uint64_t entries = 0;
 705         uint64_t new_size;
 706
 707         if (!(dir->attrib & EXFAT_ATTRIB_DIR))
 708                 exfat_bug("attempted to shrink a file");
 709         if (!dir->is_cached)
 710                 exfat_bug("attempted to shrink uncached directory");
 711
 712         for (last_node = node = dir->child; node; node = node->next)
 713         {
 714                 if (deleted_offset < node->entry_offset)
 715                 {
 716                         /* there are other entries after the removed one, no way to shrink
 717                            this directory */
 718                         return 0;
 719                 }
 720                 if (last_node->entry_offset < node->entry_offset)
 721                         last_node = node;
 722         }
 723
 724         if (last_node)
 725         {
 726                 /* offset of the last entry */
 727                 entries += last_node->entry_offset / sizeof(struct exfat_entry);
 728                 /* two subentries with meta info */
 729                 entries += 2;
 730                 /* subentries with file name */
 731                 entries += DIV_ROUND_UP(utf16_length(last_node->name),
 732                                 EXFAT_ENAME_MAX);
 733         }
 734
 735         new_size = DIV_ROUND_UP(entries * sizeof(struct exfat_entry),
 736                                  CLUSTER_SIZE(*ef->sb)) * CLUSTER_SIZE(*ef->sb);
 737         if (new_size == 0) /* directory always has at least 1 cluster */
 738                 new_size = CLUSTER_SIZE(*ef->sb);
 739         if (new_size == dir->size)
 740                 return 0;
 741         return exfat_truncate(ef, dir, new_size, true);
 742 }
 743
 744 static int delete(struct exfat* ef, struct exfat_node* node)
 745 {
 746         struct exfat_node* parent = node->parent;
 747         off_t deleted_offset = node->entry_offset;
 748         int rc;
 749
 750         exfat_get_node(parent);
 751         rc = erase_node(ef, node);
 752         if (rc != 0)
 753         {
 754                 exfat_put_node(ef, parent);
 755                 return rc;
 756         }
 757         tree_detach(node);
 758         rc = shrink_directory(ef, parent, deleted_offset);
 759         node->is_unlinked = true;
 760         if (rc != 0)
 761         {
 762                 exfat_flush_node(ef, parent);
 763                 exfat_put_node(ef, parent);
 764                 return rc;
 765         }
 766         exfat_update_mtime(parent);
 767         rc = exfat_flush_node(ef, parent);
 768         exfat_put_node(ef, parent);
 769         return rc;
 770 }
 771
 772 int exfat_unlink(struct exfat* ef, struct exfat_node* node)
 773 {
 774         if (node->attrib & EXFAT_ATTRIB_DIR)
 775                 return -EISDIR;
 776         return delete(ef, node);
 777 }
 778
 779 int exfat_rmdir(struct exfat* ef, struct exfat_node* node)
 780 {
 781         int rc;
 782
 783         if (!(node->attrib & EXFAT_ATTRIB_DIR))
 784                 return -ENOTDIR;
 785         /* check that directory is empty */
 786         rc = exfat_cache_directory(ef, node);
 787         if (rc != 0)
 788                 return rc;
 789         if (node->child)
 790                 return -ENOTEMPTY;
 791         return delete(ef, node);
 792 }
 793
 794 static int check_slot(struct exfat* ef, struct exfat_node* dir, off_t offset,
 795                 int n)
 796 {
 797         struct exfat_entry entries[n];
 798         int rc;
 799         size_t i;
 800
 801         /* Root directory contains entries, that don't have any nodes associated
 802            with them (clusters bitmap, upper case table, label). We need to be
 803            careful not to overwrite them. */
 804         if (dir != ef->root)
 805                 return 0;
 806
 807         rc = read_entries(ef, dir, entries, n, offset);
 808         if (rc != 0)
 809                 return rc;
 810         for (i = 0; i < n; i++)
 811                 if (entries[i].type & EXFAT_ENTRY_VALID)
 812                         return -EINVAL;
 813         return 0;
 814 }
 815
 816 static int find_slot(struct exfat* ef, struct exfat_node* dir,
 817                 off_t* offset, int n)
 818 {
 819         bitmap_t* dmap;
 820         struct exfat_node* p;
 821         size_t i;
 822         int contiguous = 0;
 823
 824         if (!dir->is_cached)
 825                 exfat_bug("directory is not cached");
 826
 827         /* build a bitmap of valid entries in the directory */
 828         dmap = calloc(BMAP_SIZE(dir->size / sizeof(struct exfat_entry)),
 829                         sizeof(bitmap_t));
 830         if (dmap == NULL)
 831         {
 832                 exfat_error("failed to allocate directory bitmap (%"PRIu64")",
 833                                 dir->size / sizeof(struct exfat_entry));
 834                 return -ENOMEM;
 835         }
 836         for (p = dir->child; p != NULL; p = p->next)
 837                 for (i = 0; i < 1 + p->continuations; i++)
 838                         BMAP_SET(dmap, p->entry_offset / sizeof(struct exfat_entry) + i);
 839
 840         /* find a slot in the directory entries bitmap */
 841         for (i = 0; i < dir->size / sizeof(struct exfat_entry); i++)
 842         {
 843                 if (BMAP_GET(dmap, i) == 0)
 844                 {
 845                         if (contiguous++ == 0)
 846                                 *offset = (off_t) i * sizeof(struct exfat_entry);
 847                         if (contiguous == n)
 848                                 /* suitable slot is found, check that it's not occupied */
 849                                 switch (check_slot(ef, dir, *offset, n))
 850                                 {
 851                                 case 0:
 852                                         free(dmap);
 853                                         return 0;
 854                                 case -EIO:
 855                                         free(dmap);
 856                                         return -EIO;
 857                                 case -EINVAL:
 858                                         /* slot is occupied, continue searching */
 859                                         contiguous = 0;
 860                                         break;
 861                                 }
 862                 }
 863                 else
 864                         contiguous = 0;
 865         }
 866         free(dmap);
 867
 868         /* no suitable slots found, extend the directory */
 869         if (contiguous == 0)
 870                 *offset = dir->size;
 871         return exfat_truncate(ef, dir,
 872                         ROUND_UP(dir->size + sizeof(struct exfat_entry[n - contiguous]),
 873                                         CLUSTER_SIZE(*ef->sb)),
 874                         true);
 875 }
 876
 877 static int commit_entry(struct exfat* ef, struct exfat_node* dir,
 878                 const le16_t* name, off_t offset, uint16_t attrib)
 879 {
 880         struct exfat_node* node;
 881         const size_t name_length = utf16_length(name);
 882         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
 883         struct exfat_entry entries[2 + name_entries];
 884         struct exfat_entry_meta1* meta1 = (struct exfat_entry_meta1*) &entries[0];
 885         struct exfat_entry_meta2* meta2 = (struct exfat_entry_meta2*) &entries[1];
 886         int i;
 887         int rc;
 888
 889         memset(entries, 0, sizeof(struct exfat_entry[2]));
 890
 891         meta1->type = EXFAT_ENTRY_FILE;
 892         meta1->continuations = 1 + name_entries;
 893         meta1->attrib = cpu_to_le16(attrib);
 894         exfat_unix2exfat(time(NULL), &meta1->crdate, &meta1->crtime,
 895                         &meta1->crtime_cs);
 896         meta1->adate = meta1->mdate = meta1->crdate;
 897         meta1->atime = meta1->mtime = meta1->crtime;
 898         meta1->mtime_cs = meta1->crtime_cs; /* there is no atime_cs */
 899
 900         meta2->type = EXFAT_ENTRY_FILE_INFO;
 901         meta2->flags = EXFAT_FLAG_ALWAYS1;
 902         meta2->name_length = name_length;
 903         meta2->name_hash = exfat_calc_name_hash(ef, name, name_length);
 904         meta2->start_cluster = cpu_to_le32(EXFAT_CLUSTER_FREE);
 905
 906         for (i = 0; i < name_entries; i++)
 907         {
 908                 struct exfat_entry_name* name_entry;
 909
 910                 name_entry = (struct exfat_entry_name*) &entries[2 + i];
 911                 name_entry->type = EXFAT_ENTRY_FILE_NAME;
 912                 name_entry->__unknown = 0;
 913                 memcpy(name_entry->name, name + i * EXFAT_ENAME_MAX,
 914                                 EXFAT_ENAME_MAX * sizeof(le16_t));
 915         }
 916
 917         meta1->checksum = exfat_calc_checksum(entries, 2 + name_entries);
 918         rc = write_entries(ef, dir, entries, 2 + name_entries, offset);
 919         if (rc != 0)
 920                 return rc;
 921
 922         node = allocate_node();
 923         if (node == NULL)
 924                 return -ENOMEM;
 925         node->entry_offset = offset;
 926         memcpy(node->name, name, name_length * sizeof(le16_t));
 927         init_node_meta1(node, meta1);
 928         init_node_meta2(node, meta2);
 929
 930         tree_attach(dir, node);
 931         return 0;
 932 }
 933
 934 static int create(struct exfat* ef, const char* path, uint16_t attrib)
 935 {
 936         struct exfat_node* dir;
 937         struct exfat_node* existing;
 938         off_t offset = -1;
 939         le16_t name[EXFAT_NAME_MAX + 1];
 940         int rc;
 941
 942         rc = exfat_split(ef, &dir, &existing, name, path);
 943         if (rc != 0)
 944                 return rc;
 945         if (existing != NULL)
 946         {
 947                 exfat_put_node(ef, existing);
 948                 exfat_put_node(ef, dir);
 949                 return -EEXIST;
 950         }
 951
 952         rc = find_slot(ef, dir, &offset,
 953                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
 954         if (rc != 0)
 955         {
 956                 exfat_put_node(ef, dir);
 957                 return rc;
 958         }
 959         rc = commit_entry(ef, dir, name, offset, attrib);
 960         if (rc != 0)
 961         {
 962                 exfat_put_node(ef, dir);
 963                 return rc;
 964         }
 965         exfat_update_mtime(dir);
 966         rc = exfat_flush_node(ef, dir);
 967         exfat_put_node(ef, dir);
 968         return rc;
 969 }
 970
 971 int exfat_mknod(struct exfat* ef, const char* path)
 972 {
 973         return create(ef, path, EXFAT_ATTRIB_ARCH);
 974 }
 975
 976 int exfat_mkdir(struct exfat* ef, const char* path)
 977 {
 978         int rc;
 979         struct exfat_node* node;
 980
 981         rc = create(ef, path, EXFAT_ATTRIB_DIR);
 982         if (rc != 0)
 983                 return rc;
 984         rc = exfat_lookup(ef, &node, path);
 985         if (rc != 0)
 986                 return 0;
 987         /* directories always have at least one cluster */
 988         rc = exfat_truncate(ef, node, CLUSTER_SIZE(*ef->sb), true);
 989         if (rc != 0)
 990         {
 991                 delete(ef, node);
 992                 exfat_put_node(ef, node);
 993                 return rc;
 994         }
 995         rc = exfat_flush_node(ef, node);
 996         if (rc != 0)
 997         {
 998                 delete(ef, node);
 999                 exfat_put_node(ef, node);
1000                 return rc;
1001         }
1002         exfat_put_node(ef, node);
1003         return 0;
1004 }
1005
1006 static int rename_entry(struct exfat* ef, struct exfat_node* dir,
1007                 struct exfat_node* node, const le16_t* name, off_t new_offset)
1008 {
1009         const size_t name_length = utf16_length(name);
1010         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
1011         struct exfat_entry entries[2 + name_entries];
1012         struct exfat_entry_meta1* meta1 = (struct exfat_entry_meta1*) &entries[0];
1013         struct exfat_entry_meta2* meta2 = (struct exfat_entry_meta2*) &entries[1];
1014         int rc;
1015         int i;
1016
1017         rc = read_entries(ef, node->parent, entries, 2, node->entry_offset);
1018         if (rc != 0)
1019                 return rc;
1020
1021         meta1->continuations = 1 + name_entries;
1022         meta2->name_length = name_length;
1023         meta2->name_hash = exfat_calc_name_hash(ef, name, name_length);
1024
1025         rc = erase_node(ef, node);
1026         if (rc != 0)
1027                 return rc;
1028
1029         node->entry_offset = new_offset;
1030         node->continuations = 1 + name_entries;
1031
1032         for (i = 0; i < name_entries; i++)
1033         {
1034                 struct exfat_entry_name* name_entry;
1035
1036                 name_entry = (struct exfat_entry_name*) &entries[2 + i];
1037                 name_entry->type = EXFAT_ENTRY_FILE_NAME;
1038                 name_entry->__unknown = 0;
1039                 memcpy(name_entry->name, name + i * EXFAT_ENAME_MAX,
1040                                 EXFAT_ENAME_MAX * sizeof(le16_t));
1041         }
1042
1043         meta1->checksum = exfat_calc_checksum(entries, 2 + name_entries);
1044         rc = write_entries(ef, dir, entries, 2 + name_entries, new_offset);
1045         if (rc != 0)
1046                 return rc;
1047
1048         memcpy(node->name, name, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
1049         tree_detach(node);
1050         tree_attach(dir, node);
1051         return 0;
1052 }
1053
1054 int exfat_rename(struct exfat* ef, const char* old_path, const char* new_path)
1055 {
1056         struct exfat_node* node;
1057         struct exfat_node* existing;
1058         struct exfat_node* dir;
1059         off_t offset = -1;
1060         le16_t name[EXFAT_NAME_MAX + 1];
1061         int rc;
1062
1063         rc = exfat_lookup(ef, &node, old_path);
1064         if (rc != 0)
1065                 return rc;
1066
1067         rc = exfat_split(ef, &dir, &existing, name, new_path);
1068         if (rc != 0)
1069         {
1070                 exfat_put_node(ef, node);
1071                 return rc;
1072         }
1073
1074         /* check that target is not a subdirectory of the source */
1075         if (node->attrib & EXFAT_ATTRIB_DIR)
1076         {
1077                 struct exfat_node* p;
1078
1079                 for (p = dir; p; p = p->parent)
1080                         if (node == p)
1081                         {
1082                                 if (existing != NULL)
1083                                         exfat_put_node(ef, existing);
1084                                 exfat_put_node(ef, dir);
1085                                 exfat_put_node(ef, node);
1086                                 return -EINVAL;
1087                         }
1088         }
1089
1090         if (existing != NULL)
1091         {
1092                 /* remove target if it's not the same node as source */
1093                 if (existing != node)
1094                 {
1095                         if (existing->attrib & EXFAT_ATTRIB_DIR)
1096                         {
1097                                 if (node->attrib & EXFAT_ATTRIB_DIR)
1098                                         rc = exfat_rmdir(ef, existing);
1099                                 else
1100                                         rc = -ENOTDIR;
1101                         }
1102                         else
1103                         {
1104                                 if (!(node->attrib & EXFAT_ATTRIB_DIR))
1105                                         rc = exfat_unlink(ef, existing);
1106                                 else
1107                                         rc = -EISDIR;
1108                         }
1109                         exfat_put_node(ef, existing);
1110                         if (rc != 0)
1111                         {
1112                                 /* free clusters even if something went wrong; overwise they
1113                                    will be just lost */
1114                                 exfat_cleanup_node(ef, existing);
1115                                 exfat_put_node(ef, dir);
1116                                 exfat_put_node(ef, node);
1117                                 return rc;
1118                         }
1119                         rc = exfat_cleanup_node(ef, existing);
1120                         if (rc != 0)
1121                         {
1122                                 exfat_put_node(ef, dir);
1123                                 exfat_put_node(ef, node);
1124                                 return rc;
1125                         }
1126                 }
1127                 else
1128                         exfat_put_node(ef, existing);
1129         }
1130
1131         rc = find_slot(ef, dir, &offset,
1132                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
1133         if (rc != 0)
1134         {
1135                 exfat_put_node(ef, dir);
1136                 exfat_put_node(ef, node);
1137                 return rc;
1138         }
1139         rc = rename_entry(ef, dir, node, name, offset);
1140         if (rc != 0)
1141         {
1142                 exfat_put_node(ef, dir);
1143                 exfat_put_node(ef, node);
1144                 return rc;
1145         }
1146         rc = exfat_flush_node(ef, dir);
1147         exfat_put_node(ef, dir);
1148         exfat_put_node(ef, node);
1149         /* node itself is not marked as dirty, no need to flush it */
1150         return rc;
1151 }
1152
1153 void exfat_utimes(struct exfat_node* node, const struct timespec tv[2])
1154 {
1155         node->atime = tv[0].tv_sec;
1156         node->mtime = tv[1].tv_sec;
1157         node->is_dirty = true;
1158 }
1159
1160 void exfat_update_atime(struct exfat_node* node)
1161 {
1162         node->atime = time(NULL);
1163         node->is_dirty = true;
1164 }
1165
1166 void exfat_update_mtime(struct exfat_node* node)
1167 {
1168         node->mtime = time(NULL);
1169         node->is_dirty = true;
1170 }
1171
1172 const char* exfat_get_label(struct exfat* ef)
1173 {
1174         return ef->label;
1175 }
1176
1177 static int find_label(struct exfat* ef, off_t* offset)
1178 {
1179         struct exfat_entry entry;
1180         int rc;
1181
1182         for (*offset = 0; ; *offset += sizeof(entry))
1183         {
1184                 rc = read_entries(ef, ef->root, &entry, 1, *offset);
1185                 if (rc != 0)
1186                         return rc;
1187
1188                 if (entry.type == EXFAT_ENTRY_LABEL)
1189                         return 0;
1190         }
1191 }
1192
1193 int exfat_set_label(struct exfat* ef, const char* label)
1194 {
1195         le16_t label_utf16[EXFAT_ENAME_MAX + 1];
1196         int rc;
1197         off_t offset;
1198         struct exfat_entry_label entry;
1199
1200         memset(label_utf16, 0, sizeof(label_utf16));
1201         rc = utf8_to_utf16(label_utf16, label, EXFAT_ENAME_MAX + 1, strlen(label));
1202         if (rc != 0)
1203                 return rc;
1204
1205         rc = find_label(ef, &offset);
1206         if (rc == -ENOENT)
1207                 rc = find_slot(ef, ef->root, &offset, 1);
1208         if (rc != 0)
1209                 return rc;
1210
1211         entry.type = EXFAT_ENTRY_LABEL;
1212         entry.length = utf16_length(label_utf16);
1213         memcpy(entry.name, label_utf16, sizeof(entry.name));
1214         if (entry.length == 0)
1215                 entry.type ^= EXFAT_ENTRY_VALID;
1216
1217         rc = write_entries(ef, ef->root, (struct exfat_entry*) &entry, 1, offset);
1218         if (rc != 0)
1219                 return rc;
1220
1221         strcpy(ef->label, label);
1222         return 0;
1223 }