1 /*
2 cluster.c (03.09.09)
3 exFAT file system implementation library.
4
5 Free exFAT implementation.
6 Copyright (C) 2010-2018 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 */
s2o(const struct exfat * ef,off_t sector)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 */
c2s(const struct exfat * ef,cluster_t cluster)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 */
exfat_c2o(const struct exfat * ef,cluster_t cluster)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 */
s2c(const struct exfat * ef,off_t sector)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 */
bytes2clusters(const struct exfat * ef,uint64_t bytes)67 static uint32_t bytes2clusters(const struct exfat* ef, uint64_t bytes)
68 {
69 uint64_t cluster_size = CLUSTER_SIZE(*ef->sb);
70 return DIV_ROUND_UP(bytes, cluster_size);
71 }
72
exfat_next_cluster(const struct exfat * ef,const struct exfat_node * node,cluster_t cluster)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 (node->is_contiguous)
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
exfat_advance_cluster(const struct exfat * ef,struct exfat_node * node,uint32_t count)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(*ef->sb, 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
find_bit_and_set(bitmap_t * bitmap,size_t start,size_t end)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
flush_nodes(struct exfat * ef,struct exfat_node * node)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
exfat_flush_nodes(struct exfat * ef)152 int exfat_flush_nodes(struct exfat* ef)
153 {
154 return flush_nodes(ef, ef->root);
155 }
156
exfat_flush(struct exfat * ef)157 int exfat_flush(struct exfat* ef)
158 {
159 if (ef->cmap.dirty)
160 {
161 if (exfat_pwrite(ef->dev, ef->cmap.chunk,
162 BMAP_SIZE(ef->cmap.chunk_size),
163 exfat_c2o(ef, ef->cmap.start_cluster)) < 0)
164 {
165 exfat_error("failed to write clusters bitmap");
166 return -EIO;
167 }
168 ef->cmap.dirty = false;
169 }
170
171 return 0;
172 }
173
set_next_cluster(const struct exfat * ef,bool contiguous,cluster_t current,cluster_t next)174 static bool set_next_cluster(const struct exfat* ef, bool contiguous,
175 cluster_t current, cluster_t next)
176 {
177 off_t fat_offset;
178 le32_t next_le32;
179
180 if (contiguous)
181 return true;
182 fat_offset = s2o(ef, le32_to_cpu(ef->sb->fat_sector_start))
183 + current * sizeof(cluster_t);
184 next_le32 = cpu_to_le32(next);
185 if (exfat_pwrite(ef->dev, &next_le32, sizeof(next_le32), fat_offset) < 0)
186 {
187 exfat_error("failed to write the next cluster %#x after %#x", next,
188 current);
189 return false;
190 }
191 return true;
192 }
193
allocate_cluster(struct exfat * ef,cluster_t hint)194 static cluster_t allocate_cluster(struct exfat* ef, cluster_t hint)
195 {
196 cluster_t cluster;
197
198 hint -= EXFAT_FIRST_DATA_CLUSTER;
199 if (hint >= ef->cmap.chunk_size)
200 hint = 0;
201
202 cluster = find_bit_and_set(ef->cmap.chunk, hint, ef->cmap.chunk_size);
203 if (cluster == EXFAT_CLUSTER_END)
204 cluster = find_bit_and_set(ef->cmap.chunk, 0, hint);
205 if (cluster == EXFAT_CLUSTER_END)
206 {
207 exfat_error("no free space left");
208 return EXFAT_CLUSTER_END;
209 }
210
211 ef->cmap.dirty = true;
212 return cluster;
213 }
214
free_cluster(struct exfat * ef,cluster_t cluster)215 static void free_cluster(struct exfat* ef, cluster_t cluster)
216 {
217 if (cluster - EXFAT_FIRST_DATA_CLUSTER >= ef->cmap.size)
218 exfat_bug("caller must check cluster validity (%#x, %#x)", cluster,
219 ef->cmap.size);
220
221 BMAP_CLR(ef->cmap.chunk, cluster - EXFAT_FIRST_DATA_CLUSTER);
222 ef->cmap.dirty = true;
223 }
224
make_noncontiguous(const struct exfat * ef,cluster_t first,cluster_t last)225 static bool make_noncontiguous(const struct exfat* ef, cluster_t first,
226 cluster_t last)
227 {
228 cluster_t c;
229
230 for (c = first; c < last; c++)
231 if (!set_next_cluster(ef, false, c, c + 1))
232 return false;
233 return true;
234 }
235
236 static int shrink_file(struct exfat* ef, struct exfat_node* node,
237 uint32_t current, uint32_t difference);
238
grow_file(struct exfat * ef,struct exfat_node * node,uint32_t current,uint32_t difference)239 static int grow_file(struct exfat* ef, struct exfat_node* node,
240 uint32_t current, uint32_t difference)
241 {
242 cluster_t previous;
243 cluster_t next;
244 uint32_t allocated = 0;
245
246 if (difference == 0)
247 exfat_bug("zero clusters count passed");
248
249 if (node->start_cluster != EXFAT_CLUSTER_FREE)
250 {
251 /* get the last cluster of the file */
252 previous = exfat_advance_cluster(ef, node, current - 1);
253 if (CLUSTER_INVALID(*ef->sb, previous))
254 {
255 exfat_error("invalid cluster 0x%x while growing", previous);
256 return -EIO;
257 }
258 }
259 else
260 {
261 if (node->fptr_index != 0)
262 exfat_bug("non-zero pointer index (%u)", node->fptr_index);
263 /* file does not have clusters (i.e. is empty), allocate
264 the first one for it */
265 previous = allocate_cluster(ef, 0);
266 if (CLUSTER_INVALID(*ef->sb, previous))
267 return -ENOSPC;
268 node->fptr_cluster = node->start_cluster = previous;
269 allocated = 1;
270 /* file consists of only one cluster, so it's contiguous */
271 node->is_contiguous = true;
272 }
273
274 while (allocated < difference)
275 {
276 next = allocate_cluster(ef, previous + 1);
277 if (CLUSTER_INVALID(*ef->sb, next))
278 {
279 if (allocated != 0)
280 shrink_file(ef, node, current + allocated, allocated);
281 return -ENOSPC;
282 }
283 if (next != previous - 1 && node->is_contiguous)
284 {
285 /* it's a pity, but we are not able to keep the file contiguous
286 anymore */
287 if (!make_noncontiguous(ef, node->start_cluster, previous))
288 return -EIO;
289 node->is_contiguous = false;
290 node->is_dirty = true;
291 }
292 if (!set_next_cluster(ef, node->is_contiguous, previous, next))
293 return -EIO;
294 previous = next;
295 allocated++;
296 }
297
298 if (!set_next_cluster(ef, node->is_contiguous, previous,
299 EXFAT_CLUSTER_END))
300 return -EIO;
301 return 0;
302 }
303
shrink_file(struct exfat * ef,struct exfat_node * node,uint32_t current,uint32_t difference)304 static int shrink_file(struct exfat* ef, struct exfat_node* node,
305 uint32_t current, uint32_t difference)
306 {
307 cluster_t previous;
308 cluster_t next;
309
310 if (difference == 0)
311 exfat_bug("zero difference passed");
312 if (node->start_cluster == EXFAT_CLUSTER_FREE)
313 exfat_bug("unable to shrink empty file (%u clusters)", current);
314 if (current < difference)
315 exfat_bug("file underflow (%u < %u)", current, difference);
316
317 /* crop the file */
318 if (current > difference)
319 {
320 cluster_t last = exfat_advance_cluster(ef, node,
321 current - difference - 1);
322 if (CLUSTER_INVALID(*ef->sb, last))
323 {
324 exfat_error("invalid cluster 0x%x while shrinking", last);
325 return -EIO;
326 }
327 previous = exfat_next_cluster(ef, node, last);
328 if (!set_next_cluster(ef, node->is_contiguous, last,
329 EXFAT_CLUSTER_END))
330 return -EIO;
331 }
332 else
333 {
334 previous = node->start_cluster;
335 node->start_cluster = EXFAT_CLUSTER_FREE;
336 node->is_dirty = true;
337 }
338 node->fptr_index = 0;
339 node->fptr_cluster = node->start_cluster;
340
341 /* free remaining clusters */
342 while (difference--)
343 {
344 if (CLUSTER_INVALID(*ef->sb, previous))
345 {
346 exfat_error("invalid cluster 0x%x while freeing after shrink",
347 previous);
348 return -EIO;
349 }
350
351 next = exfat_next_cluster(ef, node, previous);
352 if (!set_next_cluster(ef, node->is_contiguous, previous,
353 EXFAT_CLUSTER_FREE))
354 return -EIO;
355 free_cluster(ef, previous);
356 previous = next;
357 }
358 return 0;
359 }
360
erase_raw(struct exfat * ef,size_t size,off_t offset)361 static bool erase_raw(struct exfat* ef, size_t size, off_t offset)
362 {
363 if (exfat_pwrite(ef->dev, ef->zero_cluster, size, offset) < 0)
364 {
365 exfat_error("failed to erase %zu bytes at %"PRId64, size, offset);
366 return false;
367 }
368 return true;
369 }
370
erase_range(struct exfat * ef,struct exfat_node * node,uint64_t begin,uint64_t end)371 static int erase_range(struct exfat* ef, struct exfat_node* node,
372 uint64_t begin, uint64_t end)
373 {
374 uint64_t cluster_boundary;
375 cluster_t cluster;
376
377 if (begin >= end)
378 return 0;
379
380 cluster_boundary = (begin | (CLUSTER_SIZE(*ef->sb) - 1)) + 1;
381 cluster = exfat_advance_cluster(ef, node,
382 begin / CLUSTER_SIZE(*ef->sb));
383 if (CLUSTER_INVALID(*ef->sb, cluster))
384 {
385 exfat_error("invalid cluster 0x%x while erasing", cluster);
386 return -EIO;
387 }
388 /* erase from the beginning to the closest cluster boundary */
389 if (!erase_raw(ef, MIN(cluster_boundary, end) - begin,
390 exfat_c2o(ef, cluster) + begin % CLUSTER_SIZE(*ef->sb)))
391 return -EIO;
392 /* erase whole clusters */
393 while (cluster_boundary < end)
394 {
395 cluster = exfat_next_cluster(ef, node, cluster);
396 /* the cluster cannot be invalid because we have just allocated it */
397 if (CLUSTER_INVALID(*ef->sb, cluster))
398 exfat_bug("invalid cluster 0x%x after allocation", cluster);
399 if (!erase_raw(ef, CLUSTER_SIZE(*ef->sb), exfat_c2o(ef, cluster)))
400 return -EIO;
401 cluster_boundary += CLUSTER_SIZE(*ef->sb);
402 }
403 return 0;
404 }
405
exfat_truncate(struct exfat * ef,struct exfat_node * node,uint64_t size,bool erase)406 int exfat_truncate(struct exfat* ef, struct exfat_node* node, uint64_t size,
407 bool erase)
408 {
409 uint32_t c1 = bytes2clusters(ef, node->size);
410 uint32_t c2 = bytes2clusters(ef, size);
411 int rc = 0;
412
413 if (node->references == 0 && node->parent)
414 exfat_bug("no references, node changes can be lost");
415
416 if (node->size == size)
417 return 0;
418
419 if (c1 < c2)
420 rc = grow_file(ef, node, c1, c2 - c1);
421 else if (c1 > c2)
422 rc = shrink_file(ef, node, c1, c1 - c2);
423
424 if (rc != 0)
425 return rc;
426
427 if (erase)
428 {
429 rc = erase_range(ef, node, node->size, size);
430 if (rc != 0)
431 return rc;
432 }
433
434 exfat_update_mtime(node);
435 node->size = size;
436 node->is_dirty = true;
437 return 0;
438 }
439
exfat_count_free_clusters(const struct exfat * ef)440 uint32_t exfat_count_free_clusters(const struct exfat* ef)
441 {
442 uint32_t free_clusters = 0;
443 uint32_t i;
444
445 for (i = 0; i < ef->cmap.size; i++)
446 if (BMAP_GET(ef->cmap.chunk, i) == 0)
447 free_clusters++;
448 return free_clusters;
449 }
450
find_used_clusters(const struct exfat * ef,cluster_t * a,cluster_t * b)451 static int find_used_clusters(const struct exfat* ef,
452 cluster_t* a, cluster_t* b)
453 {
454 const cluster_t end = le32_to_cpu(ef->sb->cluster_count);
455
456 /* find first used cluster */
457 for (*a = *b + 1; *a < end; (*a)++)
458 if (BMAP_GET(ef->cmap.chunk, *a - EXFAT_FIRST_DATA_CLUSTER))
459 break;
460 if (*a >= end)
461 return 1;
462
463 /* find last contiguous used cluster */
464 for (*b = *a; *b < end; (*b)++)
465 if (BMAP_GET(ef->cmap.chunk, *b - EXFAT_FIRST_DATA_CLUSTER) == 0)
466 {
467 (*b)--;
468 break;
469 }
470
471 return 0;
472 }
473
exfat_find_used_sectors(const struct exfat * ef,off_t * a,off_t * b)474 int exfat_find_used_sectors(const struct exfat* ef, off_t* a, off_t* b)
475 {
476 cluster_t ca, cb;
477
478 if (*a == 0 && *b == 0)
479 ca = cb = EXFAT_FIRST_DATA_CLUSTER - 1;
480 else
481 {
482 ca = s2c(ef, *a);
483 cb = s2c(ef, *b);
484 }
485 if (find_used_clusters(ef, &ca, &cb) != 0)
486 return 1;
487 if (*a != 0 || *b != 0)
488 *a = c2s(ef, ca);
489 *b = c2s(ef, cb) + (CLUSTER_SIZE(*ef->sb) - 1) / SECTOR_SIZE(*ef->sb);
490 return 0;
491 }
492