Imported Upstream version 1.0.0
[sven/exfat-utils.git] / libexfat / node.c
1 /*
2         node.c (09.10.09)
3         exFAT file system implementation library.
4
5         Copyright (C) 2010-2013  Andrew Nayenko
6
7         This program is free software: you can redistribute it and/or modify
8         it under the terms of the GNU General Public License as published by
9         the Free Software Foundation, either version 3 of the License, or
10         (at your option) any later version.
11
12         This program is distributed in the hope that it will be useful,
13         but WITHOUT ANY WARRANTY; without even the implied warranty of
14         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15         GNU General Public License for more details.
16
17         You should have received a copy of the GNU General Public License
18         along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include "exfat.h"
22 #include <errno.h>
23 #include <string.h>
24 #include <inttypes.h>
25
26 /* on-disk nodes iterator */
27 struct iterator
28 {
29         cluster_t cluster;
30         off_t offset;
31         int contiguous;
32         char* chunk;
33 };
34
35 struct exfat_node* exfat_get_node(struct exfat_node* node)
36 {
37         /* if we switch to multi-threaded mode we will need atomic
38            increment here and atomic decrement in exfat_put_node() */
39         node->references++;
40         return node;
41 }
42
43 void exfat_put_node(struct exfat* ef, struct exfat_node* node)
44 {
45         if (--node->references < 0)
46         {
47                 char buffer[EXFAT_NAME_MAX + 1];
48                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
49                 exfat_bug("reference counter of `%s' is below zero", buffer);
50         }
51
52         if (node->references == 0)
53         {
54                 if (node->flags & EXFAT_ATTRIB_DIRTY)
55                         exfat_flush_node(ef, node);
56                 if (node->flags & EXFAT_ATTRIB_UNLINKED)
57                 {
58                         /* free all clusters and node structure itself */
59                         exfat_truncate(ef, node, 0);
60                         free(node);
61                 }
62                 if (ef->cmap.dirty)
63                         exfat_flush_cmap(ef);
64         }
65 }
66
67 /**
68  * Cluster + offset from the beginning of the directory to absolute offset.
69  */
70 static off_t co2o(struct exfat* ef, cluster_t cluster, off_t offset)
71 {
72         return exfat_c2o(ef, cluster) + offset % CLUSTER_SIZE(*ef->sb);
73 }
74
75 static int opendir(struct exfat* ef, const struct exfat_node* dir,
76                 struct iterator* it)
77 {
78         if (!(dir->flags & EXFAT_ATTRIB_DIR))
79                 exfat_bug("not a directory");
80         it->cluster = dir->start_cluster;
81         it->offset = 0;
82         it->contiguous = IS_CONTIGUOUS(*dir);
83         it->chunk = malloc(CLUSTER_SIZE(*ef->sb));
84         if (it->chunk == NULL)
85         {
86                 exfat_error("out of memory");
87                 return -ENOMEM;
88         }
89         exfat_pread(ef->dev, it->chunk, CLUSTER_SIZE(*ef->sb),
90                         exfat_c2o(ef, it->cluster));
91         return 0;
92 }
93
94 static void closedir(struct iterator* it)
95 {
96         it->cluster = 0;
97         it->offset = 0;
98         it->contiguous = 0;
99         free(it->chunk);
100         it->chunk = NULL;
101 }
102
103 static int fetch_next_entry(struct exfat* ef, const struct exfat_node* parent,
104                 struct iterator* it)
105 {
106         /* move iterator to the next entry in the directory */
107         it->offset += sizeof(struct exfat_entry);
108         /* fetch the next cluster if needed */
109         if ((it->offset & (CLUSTER_SIZE(*ef->sb) - 1)) == 0)
110         {
111                 /* reached the end of directory; the caller should check this
112                    condition too */
113                 if (it->offset >= parent->size)
114                         return 0;
115                 it->cluster = exfat_next_cluster(ef, parent, it->cluster);
116                 if (CLUSTER_INVALID(it->cluster))
117                 {
118                         exfat_error("invalid cluster 0x%x while reading directory",
119                                         it->cluster);
120                         return 1;
121                 }
122                 exfat_pread(ef->dev, it->chunk, CLUSTER_SIZE(*ef->sb),
123                                 exfat_c2o(ef, it->cluster));
124         }
125         return 0;
126 }
127
128 static struct exfat_node* allocate_node(void)
129 {
130         struct exfat_node* node = malloc(sizeof(struct exfat_node));
131         if (node == NULL)
132         {
133                 exfat_error("failed to allocate node");
134                 return NULL;
135         }
136         memset(node, 0, sizeof(struct exfat_node));
137         return node;
138 }
139
140 static void init_node_meta1(struct exfat_node* node,
141                 const struct exfat_entry_meta1* meta1)
142 {
143         node->flags = le16_to_cpu(meta1->attrib);
144         node->mtime = exfat_exfat2unix(meta1->mdate, meta1->mtime,
145                         meta1->mtime_cs);
146         /* there is no centiseconds field for atime */
147         node->atime = exfat_exfat2unix(meta1->adate, meta1->atime, 0);
148 }
149
150 static void init_node_meta2(struct exfat_node* node,
151                 const struct exfat_entry_meta2* meta2)
152 {
153         node->size = le64_to_cpu(meta2->size);
154         node->start_cluster = le32_to_cpu(meta2->start_cluster);
155         node->fptr_cluster = node->start_cluster;
156         if (meta2->flags & EXFAT_FLAG_CONTIGUOUS)
157                 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
158 }
159
160 static const struct exfat_entry* get_entry_ptr(const struct exfat* ef,
161                 const struct iterator* it)
162 {
163         return (const struct exfat_entry*)
164                         (it->chunk + it->offset % CLUSTER_SIZE(*ef->sb));
165 }
166
167 /*
168  * Reads one entry in directory at position pointed by iterator and fills
169  * node structure.
170  */
171 static int readdir(struct exfat* ef, const struct exfat_node* parent,
172                 struct exfat_node** node, struct iterator* it)
173 {
174         int rc = -EIO;
175         const struct exfat_entry* entry;
176         const struct exfat_entry_meta1* meta1;
177         const struct exfat_entry_meta2* meta2;
178         const struct exfat_entry_name* file_name;
179         const struct exfat_entry_upcase* upcase;
180         const struct exfat_entry_bitmap* bitmap;
181         const struct exfat_entry_label* label;
182         uint8_t continuations = 0;
183         le16_t* namep = NULL;
184         uint16_t reference_checksum = 0;
185         uint16_t actual_checksum = 0;
186         uint64_t real_size = 0;
187
188         *node = NULL;
189
190         for (;;)
191         {
192                 if (it->offset >= parent->size)
193                 {
194                         if (continuations != 0)
195                         {
196                                 exfat_error("expected %hhu continuations", continuations);
197                                 goto error;
198                         }
199                         return -ENOENT; /* that's OK, means end of directory */
200                 }
201
202                 entry = get_entry_ptr(ef, it);
203                 switch (entry->type)
204                 {
205                 case EXFAT_ENTRY_FILE:
206                         if (continuations != 0)
207                         {
208                                 exfat_error("expected %hhu continuations before new entry",
209                                                 continuations);
210                                 goto error;
211                         }
212                         meta1 = (const struct exfat_entry_meta1*) entry;
213                         continuations = meta1->continuations;
214                         /* each file entry must have at least 2 continuations:
215                            info and name */
216                         if (continuations < 2)
217                         {
218                                 exfat_error("too few continuations (%hhu)", continuations);
219                                 goto error;
220                         }
221                         reference_checksum = le16_to_cpu(meta1->checksum);
222                         actual_checksum = exfat_start_checksum(meta1);
223                         *node = allocate_node();
224                         if (*node == NULL)
225                         {
226                                 rc = -ENOMEM;
227                                 goto error;
228                         }
229                         /* new node has zero reference counter */
230                         (*node)->entry_cluster = it->cluster;
231                         (*node)->entry_offset = it->offset;
232                         init_node_meta1(*node, meta1);
233                         namep = (*node)->name;
234                         break;
235
236                 case EXFAT_ENTRY_FILE_INFO:
237                         if (continuations < 2)
238                         {
239                                 exfat_error("unexpected continuation (%hhu)",
240                                                 continuations);
241                                 goto error;
242                         }
243                         meta2 = (const struct exfat_entry_meta2*) entry;
244                         if (meta2->flags & ~(EXFAT_FLAG_ALWAYS1 | EXFAT_FLAG_CONTIGUOUS))
245                         {
246                                 exfat_error("unknown flags in meta2 (0x%hhx)", meta2->flags);
247                                 goto error;
248                         }
249                         init_node_meta2(*node, meta2);
250                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
251                         real_size = le64_to_cpu(meta2->real_size);
252                         /* empty files must be marked as non-contiguous */
253                         if ((*node)->size == 0 && (meta2->flags & EXFAT_FLAG_CONTIGUOUS))
254                         {
255                                 exfat_error("empty file marked as contiguous (0x%hhx)",
256                                                 meta2->flags);
257                                 goto error;
258                         }
259                         /* directories must be aligned on at cluster boundary */
260                         if (((*node)->flags & EXFAT_ATTRIB_DIR) &&
261                                 (*node)->size % CLUSTER_SIZE(*ef->sb) != 0)
262                         {
263                                 exfat_error("directory has invalid size %"PRIu64" bytes",
264                                                 (*node)->size);
265                                 goto error;
266                         }
267                         --continuations;
268                         break;
269
270                 case EXFAT_ENTRY_FILE_NAME:
271                         if (continuations == 0)
272                         {
273                                 exfat_error("unexpected continuation");
274                                 goto error;
275                         }
276                         file_name = (const struct exfat_entry_name*) entry;
277                         actual_checksum = exfat_add_checksum(entry, actual_checksum);
278
279                         memcpy(namep, file_name->name, EXFAT_ENAME_MAX * sizeof(le16_t));
280                         namep += EXFAT_ENAME_MAX;
281                         if (--continuations == 0)
282                         {
283                                 /*
284                                    There are two fields that contain file size. Maybe they
285                                    plan to add compression support in the future and one of
286                                    those fields is visible (uncompressed) size and the other
287                                    is real (compressed) size. Anyway, currently it looks like
288                                    exFAT does not support compression and both fields must be
289                                    equal.
290
291                                    There is an exception though: pagefile.sys (its real_size
292                                    is always 0).
293                                 */
294                                 if (real_size != (*node)->size)
295                                 {
296                                         char buffer[EXFAT_NAME_MAX + 1];
297
298                                         exfat_get_name(*node, buffer, EXFAT_NAME_MAX);
299                                         exfat_error("`%s' real size does not equal to size "
300                                                         "(%"PRIu64" != %"PRIu64")", buffer,
301                                                         real_size, (*node)->size);
302                                         goto error;
303                                 }
304                                 if (actual_checksum != reference_checksum)
305                                 {
306                                         char buffer[EXFAT_NAME_MAX + 1];
307
308                                         exfat_get_name(*node, buffer, EXFAT_NAME_MAX);
309                                         exfat_error("`%s' has invalid checksum (0x%hx != 0x%hx)",
310                                                         buffer, actual_checksum, reference_checksum);
311                                         goto error;
312                                 }
313                                 if (fetch_next_entry(ef, parent, it) != 0)
314                                         goto error;
315                                 return 0; /* entry completed */
316                         }
317                         break;
318
319                 case EXFAT_ENTRY_UPCASE:
320                         if (ef->upcase != NULL)
321                                 break;
322                         upcase = (const struct exfat_entry_upcase*) entry;
323                         if (CLUSTER_INVALID(le32_to_cpu(upcase->start_cluster)))
324                         {
325                                 exfat_error("invalid cluster 0x%x in upcase table",
326                                                 le32_to_cpu(upcase->start_cluster));
327                                 goto error;
328                         }
329                         if (le64_to_cpu(upcase->size) == 0 ||
330                                 le64_to_cpu(upcase->size) > 0xffff * sizeof(uint16_t) ||
331                                 le64_to_cpu(upcase->size) % sizeof(uint16_t) != 0)
332                         {
333                                 exfat_error("bad upcase table size (%"PRIu64" bytes)",
334                                                 le64_to_cpu(upcase->size));
335                                 goto error;
336                         }
337                         ef->upcase = malloc(le64_to_cpu(upcase->size));
338                         if (ef->upcase == NULL)
339                         {
340                                 exfat_error("failed to allocate upcase table (%"PRIu64" bytes)",
341                                                 le64_to_cpu(upcase->size));
342                                 rc = -ENOMEM;
343                                 goto error;
344                         }
345                         ef->upcase_chars = le64_to_cpu(upcase->size) / sizeof(le16_t);
346
347                         exfat_pread(ef->dev, ef->upcase, le64_to_cpu(upcase->size),
348                                         exfat_c2o(ef, le32_to_cpu(upcase->start_cluster)));
349                         break;
350
351                 case EXFAT_ENTRY_BITMAP:
352                         bitmap = (const struct exfat_entry_bitmap*) entry;
353                         ef->cmap.start_cluster = le32_to_cpu(bitmap->start_cluster);
354                         if (CLUSTER_INVALID(ef->cmap.start_cluster))
355                         {
356                                 exfat_error("invalid cluster 0x%x in clusters bitmap",
357                                                 ef->cmap.start_cluster);
358                                 goto error;
359                         }
360                         ef->cmap.size = le32_to_cpu(ef->sb->cluster_count) -
361                                 EXFAT_FIRST_DATA_CLUSTER;
362                         if (le64_to_cpu(bitmap->size) < (ef->cmap.size + 7) / 8)
363                         {
364                                 exfat_error("invalid clusters bitmap size: %"PRIu64
365                                                 " (expected at least %u)",
366                                                 le64_to_cpu(bitmap->size), (ef->cmap.size + 7) / 8);
367                                 goto error;
368                         }
369                         /* FIXME bitmap can be rather big, up to 512 MB */
370                         ef->cmap.chunk_size = ef->cmap.size;
371                         ef->cmap.chunk = malloc(le64_to_cpu(bitmap->size));
372                         if (ef->cmap.chunk == NULL)
373                         {
374                                 exfat_error("failed to allocate clusters bitmap chunk "
375                                                 "(%"PRIu64" bytes)", le64_to_cpu(bitmap->size));
376                                 rc = -ENOMEM;
377                                 goto error;
378                         }
379
380                         exfat_pread(ef->dev, ef->cmap.chunk, le64_to_cpu(bitmap->size),
381                                         exfat_c2o(ef, ef->cmap.start_cluster));
382                         break;
383
384                 case EXFAT_ENTRY_LABEL:
385                         label = (const struct exfat_entry_label*) entry;
386                         if (label->length > EXFAT_ENAME_MAX)
387                         {
388                                 exfat_error("too long label (%hhu chars)", label->length);
389                                 goto error;
390                         }
391                         if (utf16_to_utf8(ef->label, label->name,
392                                                 sizeof(ef->label), EXFAT_ENAME_MAX) != 0)
393                                 goto error;
394                         break;
395
396                 default:
397                         if (entry->type & EXFAT_ENTRY_VALID)
398                         {
399                                 exfat_error("unknown entry type 0x%hhx", entry->type);
400                                 goto error;
401                         }
402                         break;
403                 }
404
405                 if (fetch_next_entry(ef, parent, it) != 0)
406                         goto error;
407         }
408         /* we never reach here */
409
410 error:
411         free(*node);
412         *node = NULL;
413         return rc;
414 }
415
416 int exfat_cache_directory(struct exfat* ef, struct exfat_node* dir)
417 {
418         struct iterator it;
419         int rc;
420         struct exfat_node* node;
421         struct exfat_node* current = NULL;
422
423         if (dir->flags & EXFAT_ATTRIB_CACHED)
424                 return 0; /* already cached */
425
426         rc = opendir(ef, dir, &it);
427         if (rc != 0)
428                 return rc;
429         while ((rc = readdir(ef, dir, &node, &it)) == 0)
430         {
431                 node->parent = dir;
432                 if (current != NULL)
433                 {
434                         current->next = node;
435                         node->prev = current;
436                 }
437                 else
438                         dir->child = node;
439
440                 current = node;
441         }
442         closedir(&it);
443
444         if (rc != -ENOENT)
445         {
446                 /* rollback */
447                 for (current = dir->child; current; current = node)
448                 {
449                         node = current->next;
450                         free(current);
451                 }
452                 dir->child = NULL;
453                 return rc;
454         }
455
456         dir->flags |= EXFAT_ATTRIB_CACHED;
457         return 0;
458 }
459
460 static void tree_attach(struct exfat_node* dir, struct exfat_node* node)
461 {
462         node->parent = dir;
463         if (dir->child)
464         {
465                 dir->child->prev = node;
466                 node->next = dir->child;
467         }
468         dir->child = node;
469 }
470
471 static void tree_detach(struct exfat_node* node)
472 {
473         if (node->prev)
474                 node->prev->next = node->next;
475         else /* this is the first node in the list */
476                 node->parent->child = node->next;
477         if (node->next)
478                 node->next->prev = node->prev;
479         node->parent = NULL;
480         node->prev = NULL;
481         node->next = NULL;
482 }
483
484 static void reset_cache(struct exfat* ef, struct exfat_node* node)
485 {
486         while (node->child)
487         {
488                 struct exfat_node* p = node->child;
489                 reset_cache(ef, p);
490                 tree_detach(p);
491                 free(p);
492         }
493         node->flags &= ~EXFAT_ATTRIB_CACHED;
494         if (node->references != 0)
495         {
496                 char buffer[EXFAT_NAME_MAX + 1];
497                 exfat_get_name(node, buffer, EXFAT_NAME_MAX);
498                 exfat_warn("non-zero reference counter (%d) for `%s'",
499                                 node->references, buffer);
500         }
501         while (node->references)
502                 exfat_put_node(ef, node);
503 }
504
505 void exfat_reset_cache(struct exfat* ef)
506 {
507         reset_cache(ef, ef->root);
508 }
509
510 void next_entry(struct exfat* ef, const struct exfat_node* parent,
511                 cluster_t* cluster, off_t* offset)
512 {
513         *offset += sizeof(struct exfat_entry);
514         if (*offset % CLUSTER_SIZE(*ef->sb) == 0)
515                 /* next cluster cannot be invalid */
516                 *cluster = exfat_next_cluster(ef, parent, *cluster);
517 }
518
519 void exfat_flush_node(struct exfat* ef, struct exfat_node* node)
520 {
521         cluster_t cluster;
522         off_t offset;
523         off_t meta1_offset, meta2_offset;
524         struct exfat_entry_meta1 meta1;
525         struct exfat_entry_meta2 meta2;
526
527         if (ef->ro)
528                 exfat_bug("unable to flush node to read-only FS");
529
530         if (node->parent == NULL)
531                 return; /* do not flush unlinked node */
532
533         cluster = node->entry_cluster;
534         offset = node->entry_offset;
535         meta1_offset = co2o(ef, cluster, offset);
536         next_entry(ef, node->parent, &cluster, &offset);
537         meta2_offset = co2o(ef, cluster, offset);
538
539         exfat_pread(ef->dev, &meta1, sizeof(meta1), meta1_offset);
540         if (meta1.type != EXFAT_ENTRY_FILE)
541                 exfat_bug("invalid type of meta1: 0x%hhx", meta1.type);
542         meta1.attrib = cpu_to_le16(node->flags);
543         exfat_unix2exfat(node->mtime, &meta1.mdate, &meta1.mtime, &meta1.mtime_cs);
544         exfat_unix2exfat(node->atime, &meta1.adate, &meta1.atime, NULL);
545
546         exfat_pread(ef->dev, &meta2, sizeof(meta2), meta2_offset);
547         if (meta2.type != EXFAT_ENTRY_FILE_INFO)
548                 exfat_bug("invalid type of meta2: 0x%hhx", meta2.type);
549         meta2.size = meta2.real_size = cpu_to_le64(node->size);
550         meta2.start_cluster = cpu_to_le32(node->start_cluster);
551         meta2.flags = EXFAT_FLAG_ALWAYS1;
552         /* empty files must not be marked as contiguous */
553         if (node->size != 0 && IS_CONTIGUOUS(*node))
554                 meta2.flags |= EXFAT_FLAG_CONTIGUOUS;
555         /* name hash remains unchanged, no need to recalculate it */
556
557         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
558
559         exfat_pwrite(ef->dev, &meta1, sizeof(meta1), meta1_offset);
560         exfat_pwrite(ef->dev, &meta2, sizeof(meta2), meta2_offset);
561
562         node->flags &= ~EXFAT_ATTRIB_DIRTY;
563 }
564
565 static void erase_entry(struct exfat* ef, struct exfat_node* node)
566 {
567         cluster_t cluster = node->entry_cluster;
568         off_t offset = node->entry_offset;
569         int name_entries = DIV_ROUND_UP(utf16_length(node->name), EXFAT_ENAME_MAX);
570         uint8_t entry_type;
571
572         entry_type = EXFAT_ENTRY_FILE & ~EXFAT_ENTRY_VALID;
573         exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
574
575         next_entry(ef, node->parent, &cluster, &offset);
576         entry_type = EXFAT_ENTRY_FILE_INFO & ~EXFAT_ENTRY_VALID;
577         exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
578
579         while (name_entries--)
580         {
581                 next_entry(ef, node->parent, &cluster, &offset);
582                 entry_type = EXFAT_ENTRY_FILE_NAME & ~EXFAT_ENTRY_VALID;
583                 exfat_pwrite(ef->dev, &entry_type, 1, co2o(ef, cluster, offset));
584         }
585 }
586
587 static int shrink_directory(struct exfat* ef, struct exfat_node* dir,
588                 off_t deleted_offset)
589 {
590         const struct exfat_node* node;
591         const struct exfat_node* last_node;
592         uint64_t entries = 0;
593         uint64_t new_size;
594         int rc;
595
596         if (!(dir->flags & EXFAT_ATTRIB_DIR))
597                 exfat_bug("attempted to shrink a file");
598         if (!(dir->flags & EXFAT_ATTRIB_CACHED))
599                 exfat_bug("attempted to shrink uncached directory");
600
601         for (last_node = node = dir->child; node; node = node->next)
602         {
603                 if (deleted_offset < node->entry_offset)
604                 {
605                         /* there are other entries after the removed one, no way to shrink
606                            this directory */
607                         return 0;
608                 }
609                 if (last_node->entry_offset < node->entry_offset)
610                         last_node = node;
611         }
612
613         if (last_node)
614         {
615                 /* offset of the last entry */
616                 entries += last_node->entry_offset / sizeof(struct exfat_entry);
617                 /* two subentries with meta info */
618                 entries += 2;
619                 /* subentries with file name */
620                 entries += DIV_ROUND_UP(utf16_length(last_node->name),
621                                 EXFAT_ENAME_MAX);
622         }
623
624         new_size = DIV_ROUND_UP(entries * sizeof(struct exfat_entry),
625                                  CLUSTER_SIZE(*ef->sb)) * CLUSTER_SIZE(*ef->sb);
626         if (new_size == 0) /* directory always has at least 1 cluster */
627                 new_size = CLUSTER_SIZE(*ef->sb);
628         if (new_size == dir->size)
629                 return 0;
630         rc = exfat_truncate(ef, dir, new_size);
631         if (rc != 0)
632                 return rc;
633         return 0;
634 }
635
636 static int delete(struct exfat* ef, struct exfat_node* node)
637 {
638         struct exfat_node* parent = node->parent;
639         off_t deleted_offset = node->entry_offset;
640         int rc;
641
642         exfat_get_node(parent);
643         erase_entry(ef, node);
644         exfat_update_mtime(parent);
645         tree_detach(node);
646         rc = shrink_directory(ef, parent, deleted_offset);
647         exfat_put_node(ef, parent);
648         /* file clusters will be freed when node reference counter becomes 0 */
649         node->flags |= EXFAT_ATTRIB_UNLINKED;
650         return rc;
651 }
652
653 int exfat_unlink(struct exfat* ef, struct exfat_node* node)
654 {
655         if (node->flags & EXFAT_ATTRIB_DIR)
656                 return -EISDIR;
657         return delete(ef, node);
658 }
659
660 int exfat_rmdir(struct exfat* ef, struct exfat_node* node)
661 {
662         if (!(node->flags & EXFAT_ATTRIB_DIR))
663                 return -ENOTDIR;
664         /* check that directory is empty */
665         exfat_cache_directory(ef, node);
666         if (node->child)
667                 return -ENOTEMPTY;
668         return delete(ef, node);
669 }
670
671 static int grow_directory(struct exfat* ef, struct exfat_node* dir,
672                 uint64_t asize, uint32_t difference)
673 {
674         return exfat_truncate(ef, dir,
675                         DIV_ROUND_UP(asize + difference, CLUSTER_SIZE(*ef->sb))
676                                 * CLUSTER_SIZE(*ef->sb));
677 }
678
679 static int find_slot(struct exfat* ef, struct exfat_node* dir,
680                 cluster_t* cluster, off_t* offset, int subentries)
681 {
682         struct iterator it;
683         int rc;
684         const struct exfat_entry* entry;
685         int contiguous = 0;
686
687         rc = opendir(ef, dir, &it);
688         if (rc != 0)
689                 return rc;
690         for (;;)
691         {
692                 if (contiguous == 0)
693                 {
694                         *cluster = it.cluster;
695                         *offset = it.offset;
696                 }
697                 entry = get_entry_ptr(ef, &it);
698                 if (entry->type & EXFAT_ENTRY_VALID)
699                         contiguous = 0;
700                 else
701                         contiguous++;
702                 if (contiguous == subentries)
703                         break;  /* suitable slot is found */
704                 if (it.offset + sizeof(struct exfat_entry) >= dir->size)
705                 {
706                         rc = grow_directory(ef, dir, dir->size,
707                                         (subentries - contiguous) * sizeof(struct exfat_entry));
708                         if (rc != 0)
709                         {
710                                 closedir(&it);
711                                 return rc;
712                         }
713                 }
714                 if (fetch_next_entry(ef, dir, &it) != 0)
715                 {
716                         closedir(&it);
717                         return -EIO;
718                 }
719         }
720         closedir(&it);
721         return 0;
722 }
723
724 static int write_entry(struct exfat* ef, struct exfat_node* dir,
725                 const le16_t* name, cluster_t cluster, off_t offset, uint16_t attrib)
726 {
727         struct exfat_node* node;
728         struct exfat_entry_meta1 meta1;
729         struct exfat_entry_meta2 meta2;
730         const size_t name_length = utf16_length(name);
731         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
732         int i;
733
734         node = allocate_node();
735         if (node == NULL)
736                 return -ENOMEM;
737         node->entry_cluster = cluster;
738         node->entry_offset = offset;
739         memcpy(node->name, name, name_length * sizeof(le16_t));
740
741         memset(&meta1, 0, sizeof(meta1));
742         meta1.type = EXFAT_ENTRY_FILE;
743         meta1.continuations = 1 + name_entries;
744         meta1.attrib = cpu_to_le16(attrib);
745         exfat_unix2exfat(time(NULL), &meta1.crdate, &meta1.crtime,
746                         &meta1.crtime_cs);
747         meta1.adate = meta1.mdate = meta1.crdate;
748         meta1.atime = meta1.mtime = meta1.crtime;
749         meta1.mtime_cs = meta1.crtime_cs; /* there is no atime_cs */
750
751         memset(&meta2, 0, sizeof(meta2));
752         meta2.type = EXFAT_ENTRY_FILE_INFO;
753         meta2.flags = EXFAT_FLAG_ALWAYS1;
754         meta2.name_length = name_length;
755         meta2.name_hash = exfat_calc_name_hash(ef, node->name);
756         meta2.start_cluster = cpu_to_le32(EXFAT_CLUSTER_FREE);
757
758         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, node->name);
759
760         exfat_pwrite(ef->dev, &meta1, sizeof(meta1), co2o(ef, cluster, offset));
761         next_entry(ef, dir, &cluster, &offset);
762         exfat_pwrite(ef->dev, &meta2, sizeof(meta2), co2o(ef, cluster, offset));
763         for (i = 0; i < name_entries; i++)
764         {
765                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
766                 memcpy(name_entry.name, node->name + i * EXFAT_ENAME_MAX,
767                                 EXFAT_ENAME_MAX * sizeof(le16_t));
768                 next_entry(ef, dir, &cluster, &offset);
769                 exfat_pwrite(ef->dev, &name_entry, sizeof(name_entry),
770                                 co2o(ef, cluster, offset));
771         }
772
773         init_node_meta1(node, &meta1);
774         init_node_meta2(node, &meta2);
775
776         tree_attach(dir, node);
777         exfat_update_mtime(dir);
778         return 0;
779 }
780
781 static int create(struct exfat* ef, const char* path, uint16_t attrib)
782 {
783         struct exfat_node* dir;
784         struct exfat_node* existing;
785         cluster_t cluster = EXFAT_CLUSTER_BAD;
786         off_t offset = -1;
787         le16_t name[EXFAT_NAME_MAX + 1];
788         int rc;
789
790         rc = exfat_split(ef, &dir, &existing, name, path);
791         if (rc != 0)
792                 return rc;
793         if (existing != NULL)
794         {
795                 exfat_put_node(ef, existing);
796                 exfat_put_node(ef, dir);
797                 return -EEXIST;
798         }
799
800         rc = find_slot(ef, dir, &cluster, &offset,
801                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
802         if (rc != 0)
803         {
804                 exfat_put_node(ef, dir);
805                 return rc;
806         }
807         rc = write_entry(ef, dir, name, cluster, offset, attrib);
808         exfat_put_node(ef, dir);
809         return rc;
810 }
811
812 int exfat_mknod(struct exfat* ef, const char* path)
813 {
814         return create(ef, path, EXFAT_ATTRIB_ARCH);
815 }
816
817 int exfat_mkdir(struct exfat* ef, const char* path)
818 {
819         int rc;
820         struct exfat_node* node;
821
822         rc = create(ef, path, EXFAT_ATTRIB_ARCH | EXFAT_ATTRIB_DIR);
823         if (rc != 0)
824                 return rc;
825         rc = exfat_lookup(ef, &node, path);
826         if (rc != 0)
827                 return 0;
828         /* directories always have at least one cluster */
829         rc = exfat_truncate(ef, node, CLUSTER_SIZE(*ef->sb));
830         if (rc != 0)
831         {
832                 delete(ef, node);
833                 exfat_put_node(ef, node);
834                 return rc;
835         }
836         exfat_put_node(ef, node);
837         return 0;
838 }
839
840 static void rename_entry(struct exfat* ef, struct exfat_node* dir,
841                 struct exfat_node* node, const le16_t* name, cluster_t new_cluster,
842                 off_t new_offset)
843 {
844         struct exfat_entry_meta1 meta1;
845         struct exfat_entry_meta2 meta2;
846         cluster_t old_cluster = node->entry_cluster;
847         off_t old_offset = node->entry_offset;
848         const size_t name_length = utf16_length(name);
849         const int name_entries = DIV_ROUND_UP(name_length, EXFAT_ENAME_MAX);
850         int i;
851
852         exfat_pread(ef->dev, &meta1, sizeof(meta1),
853                         co2o(ef, old_cluster, old_offset));
854         next_entry(ef, node->parent, &old_cluster, &old_offset);
855         exfat_pread(ef->dev, &meta2, sizeof(meta2),
856                         co2o(ef, old_cluster, old_offset));
857         meta1.continuations = 1 + name_entries;
858         meta2.name_hash = exfat_calc_name_hash(ef, name);
859         meta2.name_length = name_length;
860         meta1.checksum = exfat_calc_checksum(&meta1, &meta2, name);
861
862         erase_entry(ef, node);
863
864         node->entry_cluster = new_cluster;
865         node->entry_offset = new_offset;
866
867         exfat_pwrite(ef->dev, &meta1, sizeof(meta1),
868                         co2o(ef, new_cluster, new_offset));
869         next_entry(ef, dir, &new_cluster, &new_offset);
870         exfat_pwrite(ef->dev, &meta2, sizeof(meta2),
871                         co2o(ef, new_cluster, new_offset));
872
873         for (i = 0; i < name_entries; i++)
874         {
875                 struct exfat_entry_name name_entry = {EXFAT_ENTRY_FILE_NAME, 0};
876                 memcpy(name_entry.name, name + i * EXFAT_ENAME_MAX,
877                                 EXFAT_ENAME_MAX * sizeof(le16_t));
878                 next_entry(ef, dir, &new_cluster, &new_offset);
879                 exfat_pwrite(ef->dev, &name_entry, sizeof(name_entry),
880                                 co2o(ef, new_cluster, new_offset));
881         }
882
883         memcpy(node->name, name, (EXFAT_NAME_MAX + 1) * sizeof(le16_t));
884         tree_detach(node);
885         tree_attach(dir, node);
886 }
887
888 int exfat_rename(struct exfat* ef, const char* old_path, const char* new_path)
889 {
890         struct exfat_node* node;
891         struct exfat_node* existing;
892         struct exfat_node* dir;
893         cluster_t cluster = EXFAT_CLUSTER_BAD;
894         off_t offset = -1;
895         le16_t name[EXFAT_NAME_MAX + 1];
896         int rc;
897
898         rc = exfat_lookup(ef, &node, old_path);
899         if (rc != 0)
900                 return rc;
901
902         rc = exfat_split(ef, &dir, &existing, name, new_path);
903         if (rc != 0)
904         {
905                 exfat_put_node(ef, node);
906                 return rc;
907         }
908         if (existing != NULL)
909         {
910                 /* remove target if it's not the same node as source */
911                 if (existing != node)
912                 {
913                         if (existing->flags & EXFAT_ATTRIB_DIR)
914                         {
915                                 if (node->flags & EXFAT_ATTRIB_DIR)
916                                         rc = exfat_rmdir(ef, existing);
917                                 else
918                                         rc = -ENOTDIR;
919                         }
920                         else
921                         {
922                                 if (!(node->flags & EXFAT_ATTRIB_DIR))
923                                         rc = exfat_unlink(ef, existing);
924                                 else
925                                         rc = -EISDIR;
926                         }
927                         exfat_put_node(ef, existing);
928                         if (rc != 0)
929                         {
930                                 exfat_put_node(ef, dir);
931                                 exfat_put_node(ef, node);
932                                 return rc;
933                         }
934                 }
935                 else
936                         exfat_put_node(ef, existing);
937         }
938
939         rc = find_slot(ef, dir, &cluster, &offset,
940                         2 + DIV_ROUND_UP(utf16_length(name), EXFAT_ENAME_MAX));
941         if (rc != 0)
942         {
943                 exfat_put_node(ef, dir);
944                 exfat_put_node(ef, node);
945                 return rc;
946         }
947         rename_entry(ef, dir, node, name, cluster, offset);
948         exfat_put_node(ef, dir);
949         exfat_put_node(ef, node);
950         return 0;
951 }
952
953 void exfat_utimes(struct exfat_node* node, const struct timespec tv[2])
954 {
955         node->atime = tv[0].tv_sec;
956         node->mtime = tv[1].tv_sec;
957         node->flags |= EXFAT_ATTRIB_DIRTY;
958 }
959
960 void exfat_update_atime(struct exfat_node* node)
961 {
962         node->atime = time(NULL);
963         node->flags |= EXFAT_ATTRIB_DIRTY;
964 }
965
966 void exfat_update_mtime(struct exfat_node* node)
967 {
968         node->mtime = time(NULL);
969         node->flags |= EXFAT_ATTRIB_DIRTY;
970 }
971
972 const char* exfat_get_label(struct exfat* ef)
973 {
974         return ef->label;
975 }
976
977 static int find_label(struct exfat* ef, cluster_t* cluster, off_t* offset)
978 {
979         struct iterator it;
980         int rc;
981
982         rc = opendir(ef, ef->root, &it);
983         if (rc != 0)
984                 return rc;
985
986         for (;;)
987         {
988                 if (it.offset >= ef->root->size)
989                 {
990                         closedir(&it);
991                         return -ENOENT;
992                 }
993
994                 if (get_entry_ptr(ef, &it)->type == EXFAT_ENTRY_LABEL)
995                 {
996                         *cluster = it.cluster;
997                         *offset = it.offset;
998                         closedir(&it);
999                         return 0;
1000                 }
1001
1002                 if (fetch_next_entry(ef, ef->root, &it) != 0)
1003                 {
1004                         closedir(&it);
1005                         return -EIO;
1006                 }
1007         }
1008 }
1009
1010 int exfat_set_label(struct exfat* ef, const char* label)
1011 {
1012         le16_t label_utf16[EXFAT_ENAME_MAX + 1];
1013         int rc;
1014         cluster_t cluster;
1015         off_t offset;
1016         struct exfat_entry_label entry;
1017
1018         memset(label_utf16, 0, sizeof(label_utf16));
1019         rc = utf8_to_utf16(label_utf16, label, EXFAT_ENAME_MAX, strlen(label));
1020         if (rc != 0)
1021                 return rc;
1022
1023         rc = find_label(ef, &cluster, &offset);
1024         if (rc == -ENOENT)
1025                 rc = find_slot(ef, ef->root, &cluster, &offset, 1);
1026         if (rc != 0)
1027                 return rc;
1028
1029         entry.type = EXFAT_ENTRY_LABEL;
1030         entry.length = utf16_length(label_utf16);
1031         memcpy(entry.name, label_utf16, sizeof(entry.name));
1032         if (entry.length == 0)
1033                 entry.type ^= EXFAT_ENTRY_VALID;
1034
1035         exfat_pwrite(ef->dev, &entry, sizeof(struct exfat_entry_label),
1036                         co2o(ef, cluster, offset));
1037         return 0;
1038 }