Commit | Line | Data |
---|---|---|
1e49a94c NJ |
1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* | |
3 | * Copyright (C) 2012-2013 Samsung Electronics Co., Ltd. | |
4 | */ | |
5 | ||
6 | #include <linux/blkdev.h> | |
7 | #include <linux/slab.h> | |
8 | #include <linux/buffer_head.h> | |
9 | ||
10 | #include "exfat_raw.h" | |
11 | #include "exfat_fs.h" | |
12 | ||
13 | static const unsigned char free_bit[] = { | |
14 | 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/* 0 ~ 19*/ | |
15 | 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3,/* 20 ~ 39*/ | |
16 | 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/* 40 ~ 59*/ | |
17 | 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/* 60 ~ 79*/ | |
18 | 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,/* 80 ~ 99*/ | |
19 | 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,/*100 ~ 119*/ | |
20 | 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*120 ~ 139*/ | |
21 | 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,/*140 ~ 159*/ | |
22 | 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/*160 ~ 179*/ | |
23 | 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3,/*180 ~ 199*/ | |
24 | 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*200 ~ 219*/ | |
25 | 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/*220 ~ 239*/ | |
26 | 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /*240 ~ 254*/ | |
27 | }; | |
28 | ||
29 | static const unsigned char used_bit[] = { | |
30 | 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3,/* 0 ~ 19*/ | |
31 | 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4,/* 20 ~ 39*/ | |
32 | 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,/* 40 ~ 59*/ | |
33 | 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,/* 60 ~ 79*/ | |
34 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,/* 80 ~ 99*/ | |
35 | 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,/*100 ~ 119*/ | |
36 | 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,/*120 ~ 139*/ | |
37 | 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,/*140 ~ 159*/ | |
38 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,/*160 ~ 179*/ | |
39 | 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,/*180 ~ 199*/ | |
40 | 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6,/*200 ~ 219*/ | |
41 | 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,/*220 ~ 239*/ | |
42 | 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /*240 ~ 255*/ | |
43 | }; | |
44 | ||
45 | /* | |
46 | * Allocation Bitmap Management Functions | |
47 | */ | |
48 | static int exfat_allocate_bitmap(struct super_block *sb, | |
49 | struct exfat_dentry *ep) | |
50 | { | |
51 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
52 | long long map_size; | |
53 | unsigned int i, need_map_size; | |
54 | sector_t sector; | |
55 | ||
56 | sbi->map_clu = le32_to_cpu(ep->dentry.bitmap.start_clu); | |
57 | map_size = le64_to_cpu(ep->dentry.bitmap.size); | |
58 | need_map_size = ((EXFAT_DATA_CLUSTER_COUNT(sbi) - 1) / BITS_PER_BYTE) | |
59 | + 1; | |
60 | if (need_map_size != map_size) { | |
d1727d55 JP |
61 | exfat_err(sb, "bogus allocation bitmap size(need : %u, cur : %lld)", |
62 | need_map_size, map_size); | |
1e49a94c NJ |
63 | /* |
64 | * Only allowed when bogus allocation | |
65 | * bitmap size is large | |
66 | */ | |
67 | if (need_map_size > map_size) | |
68 | return -EIO; | |
69 | } | |
70 | sbi->map_sectors = ((need_map_size - 1) >> | |
71 | (sb->s_blocksize_bits)) + 1; | |
72 | sbi->vol_amap = kmalloc_array(sbi->map_sectors, | |
73 | sizeof(struct buffer_head *), GFP_KERNEL); | |
74 | if (!sbi->vol_amap) | |
75 | return -ENOMEM; | |
76 | ||
77 | sector = exfat_cluster_to_sector(sbi, sbi->map_clu); | |
78 | for (i = 0; i < sbi->map_sectors; i++) { | |
79 | sbi->vol_amap[i] = sb_bread(sb, sector + i); | |
80 | if (!sbi->vol_amap[i]) { | |
81 | /* release all buffers and free vol_amap */ | |
82 | int j = 0; | |
83 | ||
84 | while (j < i) | |
85 | brelse(sbi->vol_amap[j++]); | |
86 | ||
87 | kfree(sbi->vol_amap); | |
88 | sbi->vol_amap = NULL; | |
89 | return -EIO; | |
90 | } | |
91 | } | |
92 | ||
1e49a94c NJ |
93 | return 0; |
94 | } | |
95 | ||
96 | int exfat_load_bitmap(struct super_block *sb) | |
97 | { | |
98 | unsigned int i, type; | |
99 | struct exfat_chain clu; | |
100 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
101 | ||
102 | exfat_chain_set(&clu, sbi->root_dir, 0, ALLOC_FAT_CHAIN); | |
103 | while (clu.dir != EXFAT_EOF_CLUSTER) { | |
104 | for (i = 0; i < sbi->dentries_per_clu; i++) { | |
105 | struct exfat_dentry *ep; | |
106 | struct buffer_head *bh; | |
107 | ||
108 | ep = exfat_get_dentry(sb, &clu, i, &bh, NULL); | |
109 | if (!ep) | |
110 | return -EIO; | |
111 | ||
112 | type = exfat_get_entry_type(ep); | |
113 | if (type == TYPE_UNUSED) | |
114 | break; | |
115 | if (type != TYPE_BITMAP) | |
116 | continue; | |
117 | if (ep->dentry.bitmap.flags == 0x0) { | |
118 | int err; | |
119 | ||
120 | err = exfat_allocate_bitmap(sb, ep); | |
121 | brelse(bh); | |
122 | return err; | |
123 | } | |
124 | brelse(bh); | |
125 | } | |
126 | ||
127 | if (exfat_get_next_cluster(sb, &clu.dir)) | |
128 | return -EIO; | |
129 | } | |
130 | ||
131 | return -EINVAL; | |
132 | } | |
133 | ||
134 | void exfat_free_bitmap(struct exfat_sb_info *sbi) | |
135 | { | |
136 | int i; | |
137 | ||
1e49a94c NJ |
138 | for (i = 0; i < sbi->map_sectors; i++) |
139 | __brelse(sbi->vol_amap[i]); | |
140 | ||
141 | kfree(sbi->vol_amap); | |
142 | } | |
143 | ||
23befe49 | 144 | int exfat_set_bitmap(struct inode *inode, unsigned int clu, bool sync) |
1e49a94c NJ |
145 | { |
146 | int i, b; | |
147 | unsigned int ent_idx; | |
148 | struct super_block *sb = inode->i_sb; | |
149 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
150 | ||
151 | WARN_ON(clu < EXFAT_FIRST_CLUSTER); | |
152 | ent_idx = CLUSTER_TO_BITMAP_ENT(clu); | |
153 | i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); | |
154 | b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); | |
155 | ||
156 | set_bit_le(b, sbi->vol_amap[i]->b_data); | |
23befe49 | 157 | exfat_update_bh(sbi->vol_amap[i], sync); |
1e49a94c NJ |
158 | return 0; |
159 | } | |
160 | ||
f728760a | 161 | void exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync) |
1e49a94c NJ |
162 | { |
163 | int i, b; | |
164 | unsigned int ent_idx; | |
165 | struct super_block *sb = inode->i_sb; | |
166 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
167 | struct exfat_mount_options *opts = &sbi->options; | |
168 | ||
169 | WARN_ON(clu < EXFAT_FIRST_CLUSTER); | |
170 | ent_idx = CLUSTER_TO_BITMAP_ENT(clu); | |
171 | i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); | |
172 | b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); | |
173 | ||
174 | clear_bit_le(b, sbi->vol_amap[i]->b_data); | |
f728760a | 175 | exfat_update_bh(sbi->vol_amap[i], sync); |
1e49a94c NJ |
176 | |
177 | if (opts->discard) { | |
178 | int ret_discard; | |
179 | ||
180 | ret_discard = sb_issue_discard(sb, | |
77edfc6e | 181 | exfat_cluster_to_sector(sbi, clu), |
1e49a94c NJ |
182 | (1 << sbi->sect_per_clus_bits), GFP_NOFS, 0); |
183 | ||
184 | if (ret_discard == -EOPNOTSUPP) { | |
d1727d55 | 185 | exfat_err(sb, "discard not supported by device, disabling"); |
1e49a94c NJ |
186 | opts->discard = 0; |
187 | } | |
188 | } | |
189 | } | |
190 | ||
191 | /* | |
192 | * If the value of "clu" is 0, it means cluster 2 which is the first cluster of | |
193 | * the cluster heap. | |
194 | */ | |
195 | unsigned int exfat_find_free_bitmap(struct super_block *sb, unsigned int clu) | |
196 | { | |
197 | unsigned int i, map_i, map_b, ent_idx; | |
198 | unsigned int clu_base, clu_free; | |
199 | unsigned char k, clu_mask; | |
200 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
201 | ||
202 | WARN_ON(clu < EXFAT_FIRST_CLUSTER); | |
203 | ent_idx = CLUSTER_TO_BITMAP_ENT(clu); | |
204 | clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx & ~(BITS_PER_BYTE_MASK)); | |
205 | clu_mask = IGNORED_BITS_REMAINED(clu, clu_base); | |
206 | ||
207 | map_i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); | |
208 | map_b = BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent_idx); | |
209 | ||
210 | for (i = EXFAT_FIRST_CLUSTER; i < sbi->num_clusters; | |
211 | i += BITS_PER_BYTE) { | |
212 | k = *(sbi->vol_amap[map_i]->b_data + map_b); | |
213 | if (clu_mask > 0) { | |
214 | k |= clu_mask; | |
215 | clu_mask = 0; | |
216 | } | |
217 | if (k < 0xFF) { | |
218 | clu_free = clu_base + free_bit[k]; | |
219 | if (clu_free < sbi->num_clusters) | |
220 | return clu_free; | |
221 | } | |
222 | clu_base += BITS_PER_BYTE; | |
223 | ||
224 | if (++map_b >= sb->s_blocksize || | |
225 | clu_base >= sbi->num_clusters) { | |
226 | if (++map_i >= sbi->map_sectors) { | |
227 | clu_base = EXFAT_FIRST_CLUSTER; | |
228 | map_i = 0; | |
229 | } | |
230 | map_b = 0; | |
231 | } | |
232 | } | |
233 | ||
234 | return EXFAT_EOF_CLUSTER; | |
235 | } | |
236 | ||
237 | int exfat_count_used_clusters(struct super_block *sb, unsigned int *ret_count) | |
238 | { | |
239 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
240 | unsigned int count = 0; | |
241 | unsigned int i, map_i = 0, map_b = 0; | |
242 | unsigned int total_clus = EXFAT_DATA_CLUSTER_COUNT(sbi); | |
243 | unsigned int last_mask = total_clus & BITS_PER_BYTE_MASK; | |
244 | unsigned char clu_bits; | |
245 | const unsigned char last_bit_mask[] = {0, 0b00000001, 0b00000011, | |
246 | 0b00000111, 0b00001111, 0b00011111, 0b00111111, 0b01111111}; | |
247 | ||
248 | total_clus &= ~last_mask; | |
249 | for (i = 0; i < total_clus; i += BITS_PER_BYTE) { | |
250 | clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b); | |
251 | count += used_bit[clu_bits]; | |
252 | if (++map_b >= (unsigned int)sb->s_blocksize) { | |
253 | map_i++; | |
254 | map_b = 0; | |
255 | } | |
256 | } | |
257 | ||
258 | if (last_mask) { | |
259 | clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b); | |
260 | clu_bits &= last_bit_mask[last_mask]; | |
261 | count += used_bit[clu_bits]; | |
262 | } | |
263 | ||
264 | *ret_count = count; | |
265 | return 0; | |
266 | } | |
654762df HK |
267 | |
268 | int exfat_trim_fs(struct inode *inode, struct fstrim_range *range) | |
269 | { | |
270 | unsigned int trim_begin, trim_end, count, next_free_clu; | |
271 | u64 clu_start, clu_end, trim_minlen, trimmed_total = 0; | |
272 | struct super_block *sb = inode->i_sb; | |
273 | struct exfat_sb_info *sbi = EXFAT_SB(sb); | |
274 | int err = 0; | |
275 | ||
276 | clu_start = max_t(u64, range->start >> sbi->cluster_size_bits, | |
277 | EXFAT_FIRST_CLUSTER); | |
278 | clu_end = clu_start + (range->len >> sbi->cluster_size_bits) - 1; | |
279 | trim_minlen = range->minlen >> sbi->cluster_size_bits; | |
280 | ||
281 | if (clu_start >= sbi->num_clusters || range->len < sbi->cluster_size) | |
282 | return -EINVAL; | |
283 | ||
284 | if (clu_end >= sbi->num_clusters) | |
285 | clu_end = sbi->num_clusters - 1; | |
286 | ||
287 | mutex_lock(&sbi->bitmap_lock); | |
288 | ||
289 | trim_begin = trim_end = exfat_find_free_bitmap(sb, clu_start); | |
290 | if (trim_begin == EXFAT_EOF_CLUSTER) | |
291 | goto unlock; | |
292 | ||
293 | next_free_clu = exfat_find_free_bitmap(sb, trim_end + 1); | |
294 | if (next_free_clu == EXFAT_EOF_CLUSTER) | |
295 | goto unlock; | |
296 | ||
297 | do { | |
298 | if (next_free_clu == trim_end + 1) { | |
299 | /* extend trim range for continuous free cluster */ | |
300 | trim_end++; | |
301 | } else { | |
302 | /* trim current range if it's larger than trim_minlen */ | |
303 | count = trim_end - trim_begin + 1; | |
304 | if (count >= trim_minlen) { | |
305 | err = sb_issue_discard(sb, | |
306 | exfat_cluster_to_sector(sbi, trim_begin), | |
307 | count * sbi->sect_per_clus, GFP_NOFS, 0); | |
308 | if (err) | |
309 | goto unlock; | |
310 | ||
311 | trimmed_total += count; | |
312 | } | |
313 | ||
314 | /* set next start point of the free hole */ | |
315 | trim_begin = trim_end = next_free_clu; | |
316 | } | |
317 | ||
318 | if (next_free_clu >= clu_end) | |
319 | break; | |
320 | ||
321 | if (fatal_signal_pending(current)) { | |
322 | err = -ERESTARTSYS; | |
323 | goto unlock; | |
324 | } | |
325 | ||
326 | next_free_clu = exfat_find_free_bitmap(sb, next_free_clu + 1); | |
327 | } while (next_free_clu != EXFAT_EOF_CLUSTER && | |
328 | next_free_clu > trim_end); | |
329 | ||
330 | /* try to trim remainder */ | |
331 | count = trim_end - trim_begin + 1; | |
332 | if (count >= trim_minlen) { | |
333 | err = sb_issue_discard(sb, exfat_cluster_to_sector(sbi, trim_begin), | |
334 | count * sbi->sect_per_clus, GFP_NOFS, 0); | |
335 | if (err) | |
336 | goto unlock; | |
337 | ||
338 | trimmed_total += count; | |
339 | } | |
340 | ||
341 | unlock: | |
342 | mutex_unlock(&sbi->bitmap_lock); | |
343 | range->len = trimmed_total << sbi->cluster_size_bits; | |
344 | ||
345 | return err; | |
346 | } |