Update the Homepage field in d/control.
[sven/exfat-utils.git] / libexfat / cluster.c
1 /*
2         cluster.c (03.09.09)
3         exFAT file system implementation library.
4
5         Free exFAT implementation.
6         Copyright (C) 2010-2015  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 /*
29  * Sector to absolute offset.
30  */
31 static off_t s2o(const struct exfat* ef, off_t sector)
32 {
33         return sector << ef->sb->sector_bits;
34 }
35
36 /*
37  * Cluster to sector.
38  */
39 static off_t c2s(const struct exfat* ef, cluster_t cluster)
40 {
41         if (cluster < EXFAT_FIRST_DATA_CLUSTER)
42                 exfat_bug("invalid cluster number %u", cluster);
43         return le32_to_cpu(ef->sb->cluster_sector_start) +
44                 ((off_t) (cluster - EXFAT_FIRST_DATA_CLUSTER) << ef->sb->spc_bits);
45 }
46
47 /*
48  * Cluster to absolute offset.
49  */
50 off_t exfat_c2o(const struct exfat* ef, cluster_t cluster)
51 {
52         return s2o(ef, c2s(ef, cluster));
53 }
54
55 /*
56  * Sector to cluster.
57  */
58 static cluster_t s2c(const struct exfat* ef, off_t sector)
59 {
60         return ((sector - le32_to_cpu(ef->sb->cluster_sector_start)) >>
61                         ef->sb->spc_bits) + EXFAT_FIRST_DATA_CLUSTER;
62 }
63
64 /*
65  * Size in bytes to size in clusters (rounded upwards).
66  */
67 static uint32_t bytes2clusters(const struct exfat* ef, uint64_t bytes)
68 {
69         uint64_t cluster_size = CLUSTER_SIZE(*ef->sb);
70         return (bytes + cluster_size - 1) / cluster_size;
71 }
72
73 cluster_t exfat_next_cluster(const struct exfat* ef,
74                 const struct exfat_node* node, cluster_t cluster)
75 {
76         le32_t next;
77         off_t fat_offset;
78
79         if (cluster < EXFAT_FIRST_DATA_CLUSTER)
80                 exfat_bug("bad cluster 0x%x", cluster);
81
82         if (IS_CONTIGUOUS(*node))
83                 return cluster + 1;
84         fat_offset = s2o(ef, le32_to_cpu(ef->sb->fat_sector_start))
85                 + cluster * sizeof(cluster_t);
86         if (exfat_pread(ef->dev, &next, sizeof(next), fat_offset) < 0)
87                 return EXFAT_CLUSTER_BAD; /* the caller should handle this and print
88                                              appropriate error message */
89         return le32_to_cpu(next);
90 }
91
92 cluster_t exfat_advance_cluster(const struct exfat* ef,
93                 struct exfat_node* node, uint32_t count)
94 {
95         uint32_t i;
96
97         if (node->fptr_index > count)
98         {
99                 node->fptr_index = 0;
100                 node->fptr_cluster = node->start_cluster;
101         }
102
103         for (i = node->fptr_index; i < count; i++)
104         {
105                 node->fptr_cluster = exfat_next_cluster(ef, node, node->fptr_cluster);
106                 if (CLUSTER_INVALID(node->fptr_cluster))
107                         break; /* the caller should handle this and print appropriate 
108                                   error message */
109         }
110         node->fptr_index = count;
111         return node->fptr_cluster;
112 }
113
114 static cluster_t find_bit_and_set(bitmap_t* bitmap, size_t start, size_t end)
115 {
116         const size_t start_index = start / sizeof(bitmap_t) / 8;
117         const size_t end_index = DIV_ROUND_UP(end, sizeof(bitmap_t) * 8);
118         size_t i;
119         size_t start_bitindex;
120         size_t end_bitindex;
121         size_t c;
122
123         for (i = start_index; i < end_index; i++)
124         {
125                 if (bitmap[i] == ~((bitmap_t) 0))
126                         continue;
127                 start_bitindex = MAX(i * sizeof(bitmap_t) * 8, start);
128                 end_bitindex = MIN((i + 1) * sizeof(bitmap_t) * 8, end);
129                 for (c = start_bitindex; c < end_bitindex; c++)
130                         if (BMAP_GET(bitmap, c) == 0)
131                         {
132                                 BMAP_SET(bitmap, c);
133                                 return c + EXFAT_FIRST_DATA_CLUSTER;
134                         }
135         }
136         return EXFAT_CLUSTER_END;
137 }
138
139 static int flush_nodes(struct exfat* ef, struct exfat_node* node)
140 {
141         struct exfat_node* p;
142
143         for (p = node->child; p != NULL; p = p->next)
144         {
145                 int rc = flush_nodes(ef, p);
146                 if (rc != 0)
147                         return rc;
148         }
149         return exfat_flush_node(ef, node);
150 }
151
152 int exfat_flush(struct exfat* ef)
153 {
154         int rc = flush_nodes(ef, ef->root);
155
156         if (ef->cmap.dirty)
157         {
158                 if (exfat_pwrite(ef->dev, ef->cmap.chunk,
159                                 BMAP_SIZE(ef->cmap.chunk_size),
160                                 exfat_c2o(ef, ef->cmap.start_cluster)) < 0)
161                 {
162                         exfat_error("failed to write clusters bitmap");
163                         return -EIO;
164                 }
165                 ef->cmap.dirty = false;
166         }
167
168         return rc;
169 }
170
171 static bool set_next_cluster(const struct exfat* ef, bool contiguous,
172                 cluster_t current, cluster_t next)
173 {
174         off_t fat_offset;
175         le32_t next_le32;
176
177         if (contiguous)
178                 return true;
179         fat_offset = s2o(ef, le32_to_cpu(ef->sb->fat_sector_start))
180                 + current * sizeof(cluster_t);
181         next_le32 = cpu_to_le32(next);
182         if (exfat_pwrite(ef->dev, &next_le32, sizeof(next_le32), fat_offset) < 0)
183         {
184                 exfat_error("failed to write the next cluster %#x after %#x", next,
185                                 current);
186                 return false;
187         }
188         return true;
189 }
190
191 static cluster_t allocate_cluster(struct exfat* ef, cluster_t hint)
192 {
193         cluster_t cluster;
194
195         hint -= EXFAT_FIRST_DATA_CLUSTER;
196         if (hint >= ef->cmap.chunk_size)
197                 hint = 0;
198
199         cluster = find_bit_and_set(ef->cmap.chunk, hint, ef->cmap.chunk_size);
200         if (cluster == EXFAT_CLUSTER_END)
201                 cluster = find_bit_and_set(ef->cmap.chunk, 0, hint);
202         if (cluster == EXFAT_CLUSTER_END)
203         {
204                 exfat_error("no free space left");
205                 return EXFAT_CLUSTER_END;
206         }
207
208         ef->cmap.dirty = true;
209         return cluster;
210 }
211
212 static void free_cluster(struct exfat* ef, cluster_t cluster)
213 {
214         if (CLUSTER_INVALID(cluster))
215                 exfat_bug("freeing invalid cluster 0x%x", cluster);
216         if (cluster - EXFAT_FIRST_DATA_CLUSTER >= ef->cmap.size)
217                 exfat_bug("freeing non-existing cluster 0x%x (0x%x)", cluster,
218                                 ef->cmap.size);
219
220         BMAP_CLR(ef->cmap.chunk, cluster - EXFAT_FIRST_DATA_CLUSTER);
221         ef->cmap.dirty = true;
222 }
223
224 static bool make_noncontiguous(const struct exfat* ef, cluster_t first,
225                 cluster_t last)
226 {
227         cluster_t c;
228
229         for (c = first; c < last; c++)
230                 if (!set_next_cluster(ef, false, c, c + 1))
231                         return false;
232         return true;
233 }
234
235 static int shrink_file(struct exfat* ef, struct exfat_node* node,
236                 uint32_t current, uint32_t difference);
237
238 static int grow_file(struct exfat* ef, struct exfat_node* node,
239                 uint32_t current, uint32_t difference)
240 {
241         cluster_t previous;
242         cluster_t next;
243         uint32_t allocated = 0;
244
245         if (difference == 0)
246                 exfat_bug("zero clusters count passed");
247
248         if (node->start_cluster != EXFAT_CLUSTER_FREE)
249         {
250                 /* get the last cluster of the file */
251                 previous = exfat_advance_cluster(ef, node, current - 1);
252                 if (CLUSTER_INVALID(previous))
253                 {
254                         exfat_error("invalid cluster 0x%x while growing", previous);
255                         return -EIO;
256                 }
257         }
258         else
259         {
260                 if (node->fptr_index != 0)
261                         exfat_bug("non-zero pointer index (%u)", node->fptr_index);
262                 /* file does not have clusters (i.e. is empty), allocate
263                    the first one for it */
264                 previous = allocate_cluster(ef, 0);
265                 if (CLUSTER_INVALID(previous))
266                         return -ENOSPC;
267                 node->fptr_cluster = node->start_cluster = previous;
268                 allocated = 1;
269                 /* file consists of only one cluster, so it's contiguous */
270                 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
271         }
272
273         while (allocated < difference)
274         {
275                 next = allocate_cluster(ef, previous + 1);
276                 if (CLUSTER_INVALID(next))
277                 {
278                         if (allocated != 0)
279                                 shrink_file(ef, node, current + allocated, allocated);
280                         return -ENOSPC;
281                 }
282                 if (next != previous - 1 && IS_CONTIGUOUS(*node))
283                 {
284                         /* it's a pity, but we are not able to keep the file contiguous
285                            anymore */
286                         if (!make_noncontiguous(ef, node->start_cluster, previous))
287                                 return -EIO;
288                         node->flags &= ~EXFAT_ATTRIB_CONTIGUOUS;
289                         node->flags |= EXFAT_ATTRIB_DIRTY;
290                 }
291                 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), previous, next))
292                         return -EIO;
293                 previous = next;
294                 allocated++;
295         }
296
297         if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), previous,
298                         EXFAT_CLUSTER_END))
299                 return -EIO;
300         return 0;
301 }
302
303 static int shrink_file(struct exfat* ef, struct exfat_node* node,
304                 uint32_t current, uint32_t difference)
305 {
306         cluster_t previous;
307         cluster_t next;
308
309         if (difference == 0)
310                 exfat_bug("zero difference passed");
311         if (node->start_cluster == EXFAT_CLUSTER_FREE)
312                 exfat_bug("unable to shrink empty file (%u clusters)", current);
313         if (current < difference)
314                 exfat_bug("file underflow (%u < %u)", current, difference);
315
316         /* crop the file */
317         if (current > difference)
318         {
319                 cluster_t last = exfat_advance_cluster(ef, node,
320                                 current - difference - 1);
321                 if (CLUSTER_INVALID(last))
322                 {
323                         exfat_error("invalid cluster 0x%x while shrinking", last);
324                         return -EIO;
325                 }
326                 previous = exfat_next_cluster(ef, node, last);
327                 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), last,
328                                 EXFAT_CLUSTER_END))
329                         return -EIO;
330         }
331         else
332         {
333                 previous = node->start_cluster;
334                 node->start_cluster = EXFAT_CLUSTER_FREE;
335                 node->flags |= EXFAT_ATTRIB_DIRTY;
336         }
337         node->fptr_index = 0;
338         node->fptr_cluster = node->start_cluster;
339
340         /* free remaining clusters */
341         while (difference--)
342         {
343                 if (CLUSTER_INVALID(previous))
344                 {
345                         exfat_error("invalid cluster 0x%x while freeing after shrink",
346                                         previous);
347                         return -EIO;
348                 }
349                 next = exfat_next_cluster(ef, node, previous);
350                 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), previous,
351                                 EXFAT_CLUSTER_FREE))
352                         return -EIO;
353                 free_cluster(ef, previous);
354                 previous = next;
355         }
356         return 0;
357 }
358
359 static bool erase_raw(struct exfat* ef, size_t size, off_t offset)
360 {
361         if (exfat_pwrite(ef->dev, ef->zero_cluster, size, offset) < 0)
362         {
363                 exfat_error("failed to erase %zu bytes at %"PRId64, size, offset);
364                 return false;
365         }
366         return true;
367 }
368
369 static int erase_range(struct exfat* ef, struct exfat_node* node,
370                 uint64_t begin, uint64_t end)
371 {
372         uint64_t cluster_boundary;
373         cluster_t cluster;
374
375         if (begin >= end)
376                 return 0;
377
378         cluster_boundary = (begin | (CLUSTER_SIZE(*ef->sb) - 1)) + 1;
379         cluster = exfat_advance_cluster(ef, node,
380                         begin / CLUSTER_SIZE(*ef->sb));
381         if (CLUSTER_INVALID(cluster))
382         {
383                 exfat_error("invalid cluster 0x%x while erasing", cluster);
384                 return -EIO;
385         }
386         /* erase from the beginning to the closest cluster boundary */
387         if (!erase_raw(ef, MIN(cluster_boundary, end) - begin,
388                         exfat_c2o(ef, cluster) + begin % CLUSTER_SIZE(*ef->sb)))
389                 return -EIO;
390         /* erase whole clusters */
391         while (cluster_boundary < end)
392         {
393                 cluster = exfat_next_cluster(ef, node, cluster);
394                 /* the cluster cannot be invalid because we have just allocated it */
395                 if (CLUSTER_INVALID(cluster))
396                         exfat_bug("invalid cluster 0x%x after allocation", cluster);
397                 if (!erase_raw(ef, CLUSTER_SIZE(*ef->sb), exfat_c2o(ef, cluster)))
398                         return -EIO;
399                 cluster_boundary += CLUSTER_SIZE(*ef->sb);
400         }
401         return 0;
402 }
403
404 int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size,
405                 bool erase)
406 {
407         uint32_t c1 = bytes2clusters(ef, node->size);
408         uint32_t c2 = bytes2clusters(ef, size);
409         int rc = 0;
410
411         if (node->references == 0 && node->parent)
412                 exfat_bug("no references, node changes can be lost");
413
414         if (node->size == size)
415                 return 0;
416
417         if (c1 < c2)
418                 rc = grow_file(ef, node, c1, c2 - c1);
419         else if (c1 > c2)
420                 rc = shrink_file(ef, node, c1, c1 - c2);
421
422         if (rc != 0)
423                 return rc;
424
425         if (erase)
426         {
427                 rc = erase_range(ef, node, node->size, size);
428                 if (rc != 0)
429                         return rc;
430         }
431
432         exfat_update_mtime(node);
433         node->size = size;
434         node->flags |= EXFAT_ATTRIB_DIRTY;
435         return 0;
436 }
437
438 uint32_t exfat_count_free_clusters(const struct exfat* ef)
439 {
440         uint32_t free_clusters = 0;
441         uint32_t i;
442
443         for (i = 0; i < ef->cmap.size; i++)
444                 if (BMAP_GET(ef->cmap.chunk, i) == 0)
445                         free_clusters++;
446         return free_clusters;
447 }
448
449 static int find_used_clusters(const struct exfat* ef,
450                 cluster_t* a, cluster_t* b)
451 {
452         const cluster_t end = le32_to_cpu(ef->sb->cluster_count);
453
454         /* find first used cluster */
455         for (*a = *b + 1; *a < end; (*a)++)
456                 if (BMAP_GET(ef->cmap.chunk, *a - EXFAT_FIRST_DATA_CLUSTER))
457                         break;
458         if (*a >= end)
459                 return 1;
460
461         /* find last contiguous used cluster */
462         for (*b = *a; *b < end; (*b)++)
463                 if (BMAP_GET(ef->cmap.chunk, *b - EXFAT_FIRST_DATA_CLUSTER) == 0)
464                 {
465                         (*b)--;
466                         break;
467                 }
468
469         return 0;
470 }
471
472 int exfat_find_used_sectors(const struct exfat* ef, off_t* a, off_t* b)
473 {
474         cluster_t ca, cb;
475
476         if (*a == 0 && *b == 0)
477                 ca = cb = EXFAT_FIRST_DATA_CLUSTER - 1;
478         else
479         {
480                 ca = s2c(ef, *a);
481                 cb = s2c(ef, *b);
482         }
483         if (find_used_clusters(ef, &ca, &cb) != 0)
484                 return 1;
485         if (*a != 0 || *b != 0)
486                 *a = c2s(ef, ca);
487         *b = c2s(ef, cb) + (CLUSTER_SIZE(*ef->sb) - 1) / SECTOR_SIZE(*ef->sb);
488         return 0;
489 }