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