blob: 2215636c60dcc9104ee6409eb4727f5c651b1aaa [file] [log] [blame]
bigbiff bigbiff9c754052013-01-09 09:09:08 -05001/*
2 cluster.c (03.09.09)
3 exFAT file system implementation library.
4
bigbiff bigbiff61cdc022013-08-08 08:35:06 -04005 Free exFAT implementation.
bigbiff bigbiffca829c42013-01-28 08:14:25 -05006 Copyright (C) 2010-2013 Andrew Nayenko
bigbiff bigbiff9c754052013-01-09 09:09:08 -05007
bigbiff bigbiff61cdc022013-08-08 08:35:06 -04008 This program is free software; you can redistribute it and/or modify
bigbiff bigbiff9c754052013-01-09 09:09:08 -05009 it under the terms of the GNU General Public License as published by
bigbiff bigbiff61cdc022013-08-08 08:35:06 -040010 the Free Software Foundation, either version 2 of the License, or
bigbiff bigbiff9c754052013-01-09 09:09:08 -050011 (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
bigbiff bigbiff61cdc022013-08-08 08:35:06 -040018 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.
bigbiff bigbiff9c754052013-01-09 09:09:08 -050021*/
22
23#include "exfat.h"
24#include <errno.h>
25#include <string.h>
bigbiff bigbiff61cdc022013-08-08 08:35:06 -040026#include <inttypes.h>
bigbiff bigbiff9c754052013-01-09 09:09:08 -050027
28/*
29 * Sector to absolute offset.
30 */
31static off64_t s2o(const struct exfat* ef, off64_t sector)
32{
33 return sector << ef->sb->sector_bits;
34}
35
36/*
37 * Cluster to sector.
38 */
39static off64_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 ((off64_t) (cluster - EXFAT_FIRST_DATA_CLUSTER) << ef->sb->spc_bits);
45}
46
47/*
48 * Cluster to absolute offset.
49 */
50off64_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 */
58static cluster_t s2c(const struct exfat* ef, off64_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 */
67static 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
73cluster_t exfat_next_cluster(const struct exfat* ef,
74 const struct exfat_node* node, cluster_t cluster)
75{
76 le32_t next;
77 off64_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);
bigbiff bigbiff61cdc022013-08-08 08:35:06 -040086 /* FIXME handle I/O error */
87 if (exfat_pread(ef->dev, &next, sizeof(next), fat_offset) < 0)
88 exfat_bug("failed to read the next cluster after %#x", cluster);
bigbiff bigbiff9c754052013-01-09 09:09:08 -050089 return le32_to_cpu(next);
90}
91
92cluster_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
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400114static cluster_t find_bit_and_set(bitmap_t* bitmap, size_t start, size_t end)
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500115{
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400116 const size_t start_index = start / sizeof(bitmap_t) / 8;
117 const size_t end_index = DIV_ROUND_UP(end, sizeof(bitmap_t) * 8);
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500118 size_t i;
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400119 size_t start_bitindex;
120 size_t end_bitindex;
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500121 size_t c;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500122
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500123 for (i = start_index; i < end_index; i++)
124 {
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400125 if (bitmap[i] == ~((bitmap_t) 0))
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500126 continue;
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400127 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++)
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500130 if (BMAP_GET(bitmap, c) == 0)
131 {
132 BMAP_SET(bitmap, c);
133 return c + EXFAT_FIRST_DATA_CLUSTER;
134 }
135 }
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500136 return EXFAT_CLUSTER_END;
137}
138
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400139int exfat_flush(struct exfat* ef)
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500140{
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400141 if (ef->cmap.dirty)
142 {
143 if (exfat_pwrite(ef->dev, ef->cmap.chunk,
144 BMAP_SIZE(ef->cmap.chunk_size),
145 exfat_c2o(ef, ef->cmap.start_cluster)) < 0)
146 {
147 exfat_error("failed to write clusters bitmap");
148 return -EIO;
149 }
150 ef->cmap.dirty = false;
151 }
152 return 0;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500153}
154
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400155static bool set_next_cluster(const struct exfat* ef, bool contiguous,
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500156 cluster_t current, cluster_t next)
157{
158 off64_t fat_offset;
159 le32_t next_le32;
160
161 if (contiguous)
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400162 return true;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500163 fat_offset = s2o(ef, le32_to_cpu(ef->sb->fat_sector_start))
164 + current * sizeof(cluster_t);
165 next_le32 = cpu_to_le32(next);
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400166 if (exfat_pwrite(ef->dev, &next_le32, sizeof(next_le32), fat_offset) < 0)
167 {
168 exfat_error("failed to write the next cluster %#x after %#x", next,
169 current);
170 return false;
171 }
172 return true;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500173}
174
175static cluster_t allocate_cluster(struct exfat* ef, cluster_t hint)
176{
177 cluster_t cluster;
178
179 hint -= EXFAT_FIRST_DATA_CLUSTER;
180 if (hint >= ef->cmap.chunk_size)
181 hint = 0;
182
183 cluster = find_bit_and_set(ef->cmap.chunk, hint, ef->cmap.chunk_size);
184 if (cluster == EXFAT_CLUSTER_END)
185 cluster = find_bit_and_set(ef->cmap.chunk, 0, hint);
186 if (cluster == EXFAT_CLUSTER_END)
187 {
188 exfat_error("no free space left");
189 return EXFAT_CLUSTER_END;
190 }
191
192 ef->cmap.dirty = true;
193 return cluster;
194}
195
196static void free_cluster(struct exfat* ef, cluster_t cluster)
197{
198 if (CLUSTER_INVALID(cluster))
199 exfat_bug("freeing invalid cluster 0x%x", cluster);
200 if (cluster - EXFAT_FIRST_DATA_CLUSTER >= ef->cmap.size)
201 exfat_bug("freeing non-existing cluster 0x%x (0x%x)", cluster,
202 ef->cmap.size);
203
204 BMAP_CLR(ef->cmap.chunk, cluster - EXFAT_FIRST_DATA_CLUSTER);
205 ef->cmap.dirty = true;
206}
207
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400208static bool make_noncontiguous(const struct exfat* ef, cluster_t first,
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500209 cluster_t last)
210{
211 cluster_t c;
212
213 for (c = first; c < last; c++)
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400214 if (!set_next_cluster(ef, false, c, c + 1))
215 return false;
216 return true;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500217}
218
219static int shrink_file(struct exfat* ef, struct exfat_node* node,
220 uint32_t current, uint32_t difference);
221
222static int grow_file(struct exfat* ef, struct exfat_node* node,
223 uint32_t current, uint32_t difference)
224{
225 cluster_t previous;
226 cluster_t next;
227 uint32_t allocated = 0;
228
229 if (difference == 0)
230 exfat_bug("zero clusters count passed");
231
232 if (node->start_cluster != EXFAT_CLUSTER_FREE)
233 {
234 /* get the last cluster of the file */
235 previous = exfat_advance_cluster(ef, node, current - 1);
236 if (CLUSTER_INVALID(previous))
237 {
238 exfat_error("invalid cluster 0x%x while growing", previous);
239 return -EIO;
240 }
241 }
242 else
243 {
244 if (node->fptr_index != 0)
245 exfat_bug("non-zero pointer index (%u)", node->fptr_index);
246 /* file does not have clusters (i.e. is empty), allocate
247 the first one for it */
248 previous = allocate_cluster(ef, 0);
249 if (CLUSTER_INVALID(previous))
250 return -ENOSPC;
251 node->fptr_cluster = node->start_cluster = previous;
252 allocated = 1;
253 /* file consists of only one cluster, so it's contiguous */
254 node->flags |= EXFAT_ATTRIB_CONTIGUOUS;
255 }
256
257 while (allocated < difference)
258 {
259 next = allocate_cluster(ef, previous + 1);
260 if (CLUSTER_INVALID(next))
261 {
262 if (allocated != 0)
263 shrink_file(ef, node, current + allocated, allocated);
264 return -ENOSPC;
265 }
266 if (next != previous - 1 && IS_CONTIGUOUS(*node))
267 {
268 /* it's a pity, but we are not able to keep the file contiguous
269 anymore */
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400270 if (!make_noncontiguous(ef, node->start_cluster, previous))
271 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500272 node->flags &= ~EXFAT_ATTRIB_CONTIGUOUS;
273 node->flags |= EXFAT_ATTRIB_DIRTY;
274 }
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400275 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), previous, next))
276 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500277 previous = next;
278 allocated++;
279 }
280
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400281 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), previous,
282 EXFAT_CLUSTER_END))
283 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500284 return 0;
285}
286
287static int shrink_file(struct exfat* ef, struct exfat_node* node,
288 uint32_t current, uint32_t difference)
289{
290 cluster_t previous;
291 cluster_t next;
292
293 if (difference == 0)
294 exfat_bug("zero difference passed");
295 if (node->start_cluster == EXFAT_CLUSTER_FREE)
296 exfat_bug("unable to shrink empty file (%u clusters)", current);
297 if (current < difference)
298 exfat_bug("file underflow (%u < %u)", current, difference);
299
300 /* crop the file */
301 if (current > difference)
302 {
303 cluster_t last = exfat_advance_cluster(ef, node,
304 current - difference - 1);
305 if (CLUSTER_INVALID(last))
306 {
307 exfat_error("invalid cluster 0x%x while shrinking", last);
308 return -EIO;
309 }
310 previous = exfat_next_cluster(ef, node, last);
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400311 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), last,
312 EXFAT_CLUSTER_END))
313 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500314 }
315 else
316 {
317 previous = node->start_cluster;
318 node->start_cluster = EXFAT_CLUSTER_FREE;
319 }
320 node->fptr_index = 0;
321 node->fptr_cluster = node->start_cluster;
322
323 /* free remaining clusters */
324 while (difference--)
325 {
326 if (CLUSTER_INVALID(previous))
327 {
328 exfat_error("invalid cluster 0x%x while freeing after shrink",
329 previous);
330 return -EIO;
331 }
332 next = exfat_next_cluster(ef, node, previous);
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400333 if (!set_next_cluster(ef, IS_CONTIGUOUS(*node), previous,
334 EXFAT_CLUSTER_FREE))
335 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500336 free_cluster(ef, previous);
337 previous = next;
338 }
339 return 0;
340}
341
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400342static bool erase_raw(struct exfat* ef, size_t size, off64_t offset)
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500343{
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400344 if (exfat_pwrite(ef->dev, ef->zero_cluster, size, offset) < 0)
345 {
346 exfat_error("failed to erase %zu bytes at %"PRId64, size, offset);
347 return false;
348 }
349 return true;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500350}
351
352static int erase_range(struct exfat* ef, struct exfat_node* node,
353 uint64_t begin, uint64_t end)
354{
355 uint64_t cluster_boundary;
356 cluster_t cluster;
357
358 if (begin >= end)
359 return 0;
360
361 cluster_boundary = (begin | (CLUSTER_SIZE(*ef->sb) - 1)) + 1;
362 cluster = exfat_advance_cluster(ef, node,
363 begin / CLUSTER_SIZE(*ef->sb));
364 if (CLUSTER_INVALID(cluster))
365 {
366 exfat_error("invalid cluster 0x%x while erasing", cluster);
367 return -EIO;
368 }
369 /* erase from the beginning to the closest cluster boundary */
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400370 if (!erase_raw(ef, MIN(cluster_boundary, end) - begin,
371 exfat_c2o(ef, cluster) + begin % CLUSTER_SIZE(*ef->sb)))
372 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500373 /* erase whole clusters */
374 while (cluster_boundary < end)
375 {
376 cluster = exfat_next_cluster(ef, node, cluster);
377 /* the cluster cannot be invalid because we have just allocated it */
378 if (CLUSTER_INVALID(cluster))
379 exfat_bug("invalid cluster 0x%x after allocation", cluster);
bigbiff bigbiff61cdc022013-08-08 08:35:06 -0400380 if (!erase_raw(ef, CLUSTER_SIZE(*ef->sb), exfat_c2o(ef, cluster)))
381 return -EIO;
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500382 cluster_boundary += CLUSTER_SIZE(*ef->sb);
383 }
384 return 0;
385}
386
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500387int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size,
388 bool erase)
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500389{
390 uint32_t c1 = bytes2clusters(ef, node->size);
391 uint32_t c2 = bytes2clusters(ef, size);
392 int rc = 0;
393
394 if (node->references == 0 && node->parent)
395 exfat_bug("no references, node changes can be lost");
396
397 if (node->size == size)
398 return 0;
399
400 if (c1 < c2)
401 rc = grow_file(ef, node, c1, c2 - c1);
402 else if (c1 > c2)
403 rc = shrink_file(ef, node, c1, c1 - c2);
404
405 if (rc != 0)
406 return rc;
407
bigbiff bigbiff998716f2013-03-07 09:59:37 -0500408 if (erase)
409 {
410 rc = erase_range(ef, node, node->size, size);
411 if (rc != 0)
412 return rc;
413 }
bigbiff bigbiff9c754052013-01-09 09:09:08 -0500414
415 exfat_update_mtime(node);
416 node->size = size;
417 node->flags |= EXFAT_ATTRIB_DIRTY;
418 return 0;
419}
420
421uint32_t exfat_count_free_clusters(const struct exfat* ef)
422{
423 uint32_t free_clusters = 0;
424 uint32_t i;
425
426 for (i = 0; i < ef->cmap.size; i++)
427 if (BMAP_GET(ef->cmap.chunk, i) == 0)
428 free_clusters++;
429 return free_clusters;
430}
431
432static int find_used_clusters(const struct exfat* ef,
433 cluster_t* a, cluster_t* b)
434{
435 const cluster_t end = le32_to_cpu(ef->sb->cluster_count);
436
437 /* find first used cluster */
438 for (*a = *b + 1; *a < end; (*a)++)
439 if (BMAP_GET(ef->cmap.chunk, *a - EXFAT_FIRST_DATA_CLUSTER))
440 break;
441 if (*a >= end)
442 return 1;
443
444 /* find last contiguous used cluster */
445 for (*b = *a; *b < end; (*b)++)
446 if (BMAP_GET(ef->cmap.chunk, *b - EXFAT_FIRST_DATA_CLUSTER) == 0)
447 {
448 (*b)--;
449 break;
450 }
451
452 return 0;
453}
454
455int exfat_find_used_sectors(const struct exfat* ef, off64_t* a, off64_t* b)
456{
457 cluster_t ca, cb;
458
459 if (*a == 0 && *b == 0)
460 ca = cb = EXFAT_FIRST_DATA_CLUSTER - 1;
461 else
462 {
463 ca = s2c(ef, *a);
464 cb = s2c(ef, *b);
465 }
466 if (find_used_clusters(ef, &ca, &cb) != 0)
467 return 1;
468 if (*a != 0 || *b != 0)
469 *a = c2s(ef, ca);
470 *b = c2s(ef, cb) + (CLUSTER_SIZE(*ef->sb) - 1) / SECTOR_SIZE(*ef->sb);
471 return 0;
472}