]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - fs/exfat/balloc.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) 2012-2013 Samsung Electronics Co., Ltd.
6 #include <linux/blkdev.h>
7 #include <linux/slab.h>
8 #include <linux/buffer_head.h>
10 #include "exfat_raw.h"
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*/
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*/
46 * Allocation Bitmap Management Functions
48 static int exfat_allocate_bitmap(struct super_block
*sb
,
49 struct exfat_dentry
*ep
)
51 struct exfat_sb_info
*sbi
= EXFAT_SB(sb
);
53 unsigned int i
, need_map_size
;
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
)
60 if (need_map_size
!= map_size
) {
61 exfat_err(sb
, "bogus allocation bitmap size(need : %u, cur : %lld)",
62 need_map_size
, map_size
);
64 * Only allowed when bogus allocation
65 * bitmap size is large
67 if (need_map_size
> map_size
)
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
);
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 */
85 brelse(sbi
->vol_amap
[j
++]);
96 int exfat_load_bitmap(struct super_block
*sb
)
99 struct exfat_chain clu
;
100 struct exfat_sb_info
*sbi
= EXFAT_SB(sb
);
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
;
108 ep
= exfat_get_dentry(sb
, &clu
, i
, &bh
, NULL
);
112 type
= exfat_get_entry_type(ep
);
113 if (type
== TYPE_UNUSED
)
115 if (type
!= TYPE_BITMAP
)
117 if (ep
->dentry
.bitmap
.flags
== 0x0) {
120 err
= exfat_allocate_bitmap(sb
, ep
);
127 if (exfat_get_next_cluster(sb
, &clu
.dir
))
134 void exfat_free_bitmap(struct exfat_sb_info
*sbi
)
138 for (i
= 0; i
< sbi
->map_sectors
; i
++)
139 __brelse(sbi
->vol_amap
[i
]);
141 kfree(sbi
->vol_amap
);
144 int exfat_set_bitmap(struct inode
*inode
, unsigned int clu
, bool sync
)
147 unsigned int ent_idx
;
148 struct super_block
*sb
= inode
->i_sb
;
149 struct exfat_sb_info
*sbi
= EXFAT_SB(sb
);
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
);
156 set_bit_le(b
, sbi
->vol_amap
[i
]->b_data
);
157 exfat_update_bh(sbi
->vol_amap
[i
], sync
);
161 void exfat_clear_bitmap(struct inode
*inode
, unsigned int clu
, bool sync
)
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
;
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
);
174 clear_bit_le(b
, sbi
->vol_amap
[i
]->b_data
);
175 exfat_update_bh(sbi
->vol_amap
[i
], sync
);
180 ret_discard
= sb_issue_discard(sb
,
181 exfat_cluster_to_sector(sbi
, clu
),
182 (1 << sbi
->sect_per_clus_bits
), GFP_NOFS
, 0);
184 if (ret_discard
== -EOPNOTSUPP
) {
185 exfat_err(sb
, "discard not supported by device, disabling");
192 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of
195 unsigned int exfat_find_free_bitmap(struct super_block
*sb
, unsigned int clu
)
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
);
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
);
207 map_i
= BITMAP_OFFSET_SECTOR_INDEX(sb
, ent_idx
);
208 map_b
= BITMAP_OFFSET_BYTE_IN_SECTOR(sb
, ent_idx
);
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
);
218 clu_free
= clu_base
+ free_bit
[k
];
219 if (clu_free
< sbi
->num_clusters
)
222 clu_base
+= BITS_PER_BYTE
;
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
;
234 return EXFAT_EOF_CLUSTER
;
237 int exfat_count_used_clusters(struct super_block
*sb
, unsigned int *ret_count
)
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};
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
) {
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
];
268 int exfat_trim_fs(struct inode
*inode
, struct fstrim_range
*range
)
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
);
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
;
281 if (clu_start
>= sbi
->num_clusters
|| range
->len
< sbi
->cluster_size
)
284 if (clu_end
>= sbi
->num_clusters
)
285 clu_end
= sbi
->num_clusters
- 1;
287 mutex_lock(&sbi
->bitmap_lock
);
289 trim_begin
= trim_end
= exfat_find_free_bitmap(sb
, clu_start
);
290 if (trim_begin
== EXFAT_EOF_CLUSTER
)
293 next_free_clu
= exfat_find_free_bitmap(sb
, trim_end
+ 1);
294 if (next_free_clu
== EXFAT_EOF_CLUSTER
)
298 if (next_free_clu
== trim_end
+ 1) {
299 /* extend trim range for continuous free cluster */
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);
311 trimmed_total
+= count
;
314 /* set next start point of the free hole */
315 trim_begin
= trim_end
= next_free_clu
;
318 if (next_free_clu
>= clu_end
)
321 if (fatal_signal_pending(current
)) {
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
);
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);
338 trimmed_total
+= count
;
342 mutex_unlock(&sbi
->bitmap_lock
);
343 range
->len
= trimmed_total
<< sbi
->cluster_size_bits
;