Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0
2 : : /*
3 : : * linux/fs/fat/cache.c
4 : : *
5 : : * Written 1992,1993 by Werner Almesberger
6 : : *
7 : : * Mar 1999. AV. Changed cache, so that it uses the starting cluster instead
8 : : * of inode number.
9 : : * May 1999. AV. Fixed the bogosity with FAT32 (read "FAT28"). Fscking lusers.
10 : : */
11 : :
12 : : #include <linux/slab.h>
13 : : #include "fat.h"
14 : :
15 : : /* this must be > 0. */
16 : : #define FAT_MAX_CACHE 8
17 : :
18 : : struct fat_cache {
19 : : struct list_head cache_list;
20 : : int nr_contig; /* number of contiguous clusters */
21 : : int fcluster; /* cluster number in the file. */
22 : : int dcluster; /* cluster number on disk. */
23 : : };
24 : :
25 : : struct fat_cache_id {
26 : : unsigned int id;
27 : : int nr_contig;
28 : : int fcluster;
29 : : int dcluster;
30 : : };
31 : :
32 : 0 : static inline int fat_max_cache(struct inode *inode)
33 : : {
34 [ # # ]: 0 : return FAT_MAX_CACHE;
35 : : }
36 : :
37 : : static struct kmem_cache *fat_cache_cachep;
38 : :
39 : 0 : static void init_once(void *foo)
40 : : {
41 : 0 : struct fat_cache *cache = (struct fat_cache *)foo;
42 : :
43 : 0 : INIT_LIST_HEAD(&cache->cache_list);
44 : 0 : }
45 : :
46 : 13 : int __init fat_cache_init(void)
47 : : {
48 : 13 : fat_cache_cachep = kmem_cache_create("fat_cache",
49 : : sizeof(struct fat_cache),
50 : : 0, SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD,
51 : : init_once);
52 [ - + ]: 13 : if (fat_cache_cachep == NULL)
53 : 0 : return -ENOMEM;
54 : : return 0;
55 : : }
56 : :
57 : 0 : void fat_cache_destroy(void)
58 : : {
59 : 0 : kmem_cache_destroy(fat_cache_cachep);
60 : 0 : }
61 : :
62 : 0 : static inline struct fat_cache *fat_cache_alloc(struct inode *inode)
63 : : {
64 : 0 : return kmem_cache_alloc(fat_cache_cachep, GFP_NOFS);
65 : : }
66 : :
67 : 0 : static inline void fat_cache_free(struct fat_cache *cache)
68 : : {
69 [ # # ]: 0 : BUG_ON(!list_empty(&cache->cache_list));
70 : 0 : kmem_cache_free(fat_cache_cachep, cache);
71 : 0 : }
72 : :
73 : 0 : static inline void fat_cache_update_lru(struct inode *inode,
74 : : struct fat_cache *cache)
75 : : {
76 : 0 : if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list)
77 : 0 : list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru);
78 : : }
79 : :
80 : 0 : static int fat_cache_lookup(struct inode *inode, int fclus,
81 : : struct fat_cache_id *cid,
82 : : int *cached_fclus, int *cached_dclus)
83 : : {
84 : 0 : static struct fat_cache nohit = { .fcluster = 0, };
85 : :
86 : 0 : struct fat_cache *hit = &nohit, *p;
87 : 0 : int offset = -1;
88 : :
89 : 0 : spin_lock(&MSDOS_I(inode)->cache_lru_lock);
90 [ # # ]: 0 : list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
91 : : /* Find the cache of "fclus" or nearest cache. */
92 [ # # # # ]: 0 : if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {
93 : 0 : hit = p;
94 [ # # ]: 0 : if ((hit->fcluster + hit->nr_contig) < fclus) {
95 : : offset = hit->nr_contig;
96 : : } else {
97 : 0 : offset = fclus - hit->fcluster;
98 : 0 : break;
99 : : }
100 : : }
101 : : }
102 [ # # ]: 0 : if (hit != &nohit) {
103 [ # # ]: 0 : fat_cache_update_lru(inode, hit);
104 : :
105 : 0 : cid->id = MSDOS_I(inode)->cache_valid_id;
106 : 0 : cid->nr_contig = hit->nr_contig;
107 : 0 : cid->fcluster = hit->fcluster;
108 : 0 : cid->dcluster = hit->dcluster;
109 : 0 : *cached_fclus = cid->fcluster + offset;
110 : 0 : *cached_dclus = cid->dcluster + offset;
111 : : }
112 : 0 : spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
113 : :
114 : 0 : return offset;
115 : : }
116 : :
117 : 0 : static struct fat_cache *fat_cache_merge(struct inode *inode,
118 : : struct fat_cache_id *new)
119 : : {
120 : 0 : struct fat_cache *p;
121 : :
122 [ # # ]: 0 : list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
123 : : /* Find the same part as "new" in cluster-chain. */
124 [ # # ]: 0 : if (p->fcluster == new->fcluster) {
125 [ # # ]: 0 : BUG_ON(p->dcluster != new->dcluster);
126 [ # # ]: 0 : if (new->nr_contig > p->nr_contig)
127 : 0 : p->nr_contig = new->nr_contig;
128 : 0 : return p;
129 : : }
130 : : }
131 : : return NULL;
132 : : }
133 : :
134 : 0 : static void fat_cache_add(struct inode *inode, struct fat_cache_id *new)
135 : : {
136 : 0 : struct fat_cache *cache, *tmp;
137 : :
138 [ # # ]: 0 : if (new->fcluster == -1) /* dummy cache */
139 : : return;
140 : :
141 : 0 : spin_lock(&MSDOS_I(inode)->cache_lru_lock);
142 [ # # ]: 0 : if (new->id != FAT_CACHE_VALID &&
143 [ # # ]: 0 : new->id != MSDOS_I(inode)->cache_valid_id)
144 : 0 : goto out; /* this cache was invalidated */
145 : :
146 : 0 : cache = fat_cache_merge(inode, new);
147 [ # # ]: 0 : if (cache == NULL) {
148 [ # # ]: 0 : if (MSDOS_I(inode)->nr_caches < fat_max_cache(inode)) {
149 : 0 : MSDOS_I(inode)->nr_caches++;
150 : 0 : spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
151 : :
152 : 0 : tmp = fat_cache_alloc(inode);
153 [ # # ]: 0 : if (!tmp) {
154 : 0 : spin_lock(&MSDOS_I(inode)->cache_lru_lock);
155 : 0 : MSDOS_I(inode)->nr_caches--;
156 : 0 : spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
157 : 0 : return;
158 : : }
159 : :
160 : 0 : spin_lock(&MSDOS_I(inode)->cache_lru_lock);
161 : 0 : cache = fat_cache_merge(inode, new);
162 [ # # ]: 0 : if (cache != NULL) {
163 : 0 : MSDOS_I(inode)->nr_caches--;
164 : 0 : fat_cache_free(tmp);
165 : 0 : goto out_update_lru;
166 : : }
167 : : cache = tmp;
168 : : } else {
169 : 0 : struct list_head *p = MSDOS_I(inode)->cache_lru.prev;
170 : 0 : cache = list_entry(p, struct fat_cache, cache_list);
171 : : }
172 : 0 : cache->fcluster = new->fcluster;
173 : 0 : cache->dcluster = new->dcluster;
174 : 0 : cache->nr_contig = new->nr_contig;
175 : : }
176 : 0 : out_update_lru:
177 [ # # ]: 0 : fat_cache_update_lru(inode, cache);
178 : 0 : out:
179 : 0 : spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
180 : : }
181 : :
182 : : /*
183 : : * Cache invalidation occurs rarely, thus the LRU chain is not updated. It
184 : : * fixes itself after a while.
185 : : */
186 : 0 : static void __fat_cache_inval_inode(struct inode *inode)
187 : : {
188 : 0 : struct msdos_inode_info *i = MSDOS_I(inode);
189 : 0 : struct fat_cache *cache;
190 : :
191 [ # # ]: 0 : while (!list_empty(&i->cache_lru)) {
192 : 0 : cache = list_entry(i->cache_lru.next,
193 : : struct fat_cache, cache_list);
194 : 0 : list_del_init(&cache->cache_list);
195 : 0 : i->nr_caches--;
196 : 0 : fat_cache_free(cache);
197 : : }
198 : : /* Update. The copy of caches before this id is discarded. */
199 : 0 : i->cache_valid_id++;
200 [ # # ]: 0 : if (i->cache_valid_id == FAT_CACHE_VALID)
201 : 0 : i->cache_valid_id++;
202 : 0 : }
203 : :
204 : 0 : void fat_cache_inval_inode(struct inode *inode)
205 : : {
206 : 0 : spin_lock(&MSDOS_I(inode)->cache_lru_lock);
207 : 0 : __fat_cache_inval_inode(inode);
208 : 0 : spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
209 : 0 : }
210 : :
211 : 0 : static inline int cache_contiguous(struct fat_cache_id *cid, int dclus)
212 : : {
213 : 0 : cid->nr_contig++;
214 : 0 : return ((cid->dcluster + cid->nr_contig) == dclus);
215 : : }
216 : :
217 : 0 : static inline void cache_init(struct fat_cache_id *cid, int fclus, int dclus)
218 : : {
219 : 0 : cid->id = FAT_CACHE_VALID;
220 : 0 : cid->fcluster = fclus;
221 : 0 : cid->dcluster = dclus;
222 : 0 : cid->nr_contig = 0;
223 : 0 : }
224 : :
225 : 0 : int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus)
226 : : {
227 : 0 : struct super_block *sb = inode->i_sb;
228 [ # # ]: 0 : struct msdos_sb_info *sbi = MSDOS_SB(sb);
229 : 0 : const int limit = sb->s_maxbytes >> sbi->cluster_bits;
230 : 0 : struct fat_entry fatent;
231 : 0 : struct fat_cache_id cid;
232 : 0 : int nr;
233 : :
234 [ # # ]: 0 : BUG_ON(MSDOS_I(inode)->i_start == 0);
235 : :
236 : 0 : *fclus = 0;
237 [ # # ]: 0 : *dclus = MSDOS_I(inode)->i_start;
238 [ # # # # ]: 0 : if (!fat_valid_entry(sbi, *dclus)) {
239 : 0 : fat_fs_error_ratelimit(sb,
240 : : "%s: invalid start cluster (i_pos %lld, start %08x)",
241 : : __func__, MSDOS_I(inode)->i_pos, *dclus);
242 : 0 : return -EIO;
243 : : }
244 [ # # ]: 0 : if (cluster == 0)
245 : : return 0;
246 : :
247 [ # # ]: 0 : if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) {
248 : : /*
249 : : * dummy, always not contiguous
250 : : * This is reinitialized by cache_init(), later.
251 : : */
252 : 0 : cache_init(&cid, -1, -1);
253 : : }
254 : :
255 : 0 : fatent_init(&fatent);
256 [ # # ]: 0 : while (*fclus < cluster) {
257 : : /* prevent the infinite loop of cluster chain */
258 [ # # ]: 0 : if (*fclus > limit) {
259 : 0 : fat_fs_error_ratelimit(sb,
260 : : "%s: detected the cluster chain loop (i_pos %lld)",
261 : : __func__, MSDOS_I(inode)->i_pos);
262 : 0 : nr = -EIO;
263 : 0 : goto out;
264 : : }
265 : :
266 : 0 : nr = fat_ent_read(inode, &fatent, *dclus);
267 [ # # ]: 0 : if (nr < 0)
268 : 0 : goto out;
269 [ # # ]: 0 : else if (nr == FAT_ENT_FREE) {
270 : 0 : fat_fs_error_ratelimit(sb,
271 : : "%s: invalid cluster chain (i_pos %lld)",
272 : : __func__, MSDOS_I(inode)->i_pos);
273 : 0 : nr = -EIO;
274 : 0 : goto out;
275 [ # # ]: 0 : } else if (nr == FAT_ENT_EOF) {
276 : 0 : fat_cache_add(inode, &cid);
277 : 0 : goto out;
278 : : }
279 : 0 : (*fclus)++;
280 : 0 : *dclus = nr;
281 [ # # ]: 0 : if (!cache_contiguous(&cid, *dclus))
282 : 0 : cache_init(&cid, *fclus, *dclus);
283 : : }
284 : 0 : nr = 0;
285 : 0 : fat_cache_add(inode, &cid);
286 : 0 : out:
287 : 0 : fatent_brelse(&fatent);
288 : 0 : return nr;
289 : : }
290 : :
291 : 0 : static int fat_bmap_cluster(struct inode *inode, int cluster)
292 : : {
293 : 0 : struct super_block *sb = inode->i_sb;
294 : 0 : int ret, fclus, dclus;
295 : :
296 [ # # ]: 0 : if (MSDOS_I(inode)->i_start == 0)
297 : : return 0;
298 : :
299 : 0 : ret = fat_get_cluster(inode, cluster, &fclus, &dclus);
300 [ # # ]: 0 : if (ret < 0)
301 : : return ret;
302 [ # # ]: 0 : else if (ret == FAT_ENT_EOF) {
303 : 0 : fat_fs_error(sb, "%s: request beyond EOF (i_pos %lld)",
304 : : __func__, MSDOS_I(inode)->i_pos);
305 : 0 : return -EIO;
306 : : }
307 : 0 : return dclus;
308 : : }
309 : :
310 : 0 : int fat_get_mapped_cluster(struct inode *inode, sector_t sector,
311 : : sector_t last_block,
312 : : unsigned long *mapped_blocks, sector_t *bmap)
313 : : {
314 : 0 : struct super_block *sb = inode->i_sb;
315 : 0 : struct msdos_sb_info *sbi = MSDOS_SB(sb);
316 : 0 : int cluster, offset;
317 : :
318 : 0 : cluster = sector >> (sbi->cluster_bits - sb->s_blocksize_bits);
319 : 0 : offset = sector & (sbi->sec_per_clus - 1);
320 : 0 : cluster = fat_bmap_cluster(inode, cluster);
321 [ # # ]: 0 : if (cluster < 0)
322 : : return cluster;
323 [ # # ]: 0 : else if (cluster) {
324 [ # # ]: 0 : *bmap = fat_clus_to_blknr(sbi, cluster) + offset;
325 : 0 : *mapped_blocks = sbi->sec_per_clus - offset;
326 [ # # ]: 0 : if (*mapped_blocks > last_block - sector)
327 : 0 : *mapped_blocks = last_block - sector;
328 : : }
329 : :
330 : : return 0;
331 : : }
332 : :
333 : 0 : static int is_exceed_eof(struct inode *inode, sector_t sector,
334 : : sector_t *last_block, int create)
335 : : {
336 : 0 : struct super_block *sb = inode->i_sb;
337 : 0 : const unsigned long blocksize = sb->s_blocksize;
338 : 0 : const unsigned char blocksize_bits = sb->s_blocksize_bits;
339 : :
340 : 0 : *last_block = (i_size_read(inode) + (blocksize - 1)) >> blocksize_bits;
341 [ # # ]: 0 : if (sector >= *last_block) {
342 [ # # ]: 0 : if (!create)
343 : : return 1;
344 : :
345 : : /*
346 : : * ->mmu_private can access on only allocation path.
347 : : * (caller must hold ->i_mutex)
348 : : */
349 [ # # ]: 0 : *last_block = (MSDOS_I(inode)->mmu_private + (blocksize - 1))
350 : 0 : >> blocksize_bits;
351 [ # # ]: 0 : if (sector >= *last_block)
352 : : return 1;
353 : : }
354 : :
355 : : return 0;
356 : : }
357 : :
358 : 0 : int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys,
359 : : unsigned long *mapped_blocks, int create, bool from_bmap)
360 : : {
361 [ # # ]: 0 : struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
362 : 0 : sector_t last_block;
363 : :
364 : 0 : *phys = 0;
365 : 0 : *mapped_blocks = 0;
366 [ # # # # ]: 0 : if (!is_fat32(sbi) && (inode->i_ino == MSDOS_ROOT_INO)) {
367 [ # # ]: 0 : if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits)) {
368 : 0 : *phys = sector + sbi->dir_start;
369 : 0 : *mapped_blocks = 1;
370 : : }
371 : 0 : return 0;
372 : : }
373 : :
374 [ # # ]: 0 : if (!from_bmap) {
375 [ # # ]: 0 : if (is_exceed_eof(inode, sector, &last_block, create))
376 : : return 0;
377 : : } else {
378 : 0 : last_block = inode->i_blocks >>
379 : 0 : (inode->i_sb->s_blocksize_bits - 9);
380 [ # # ]: 0 : if (sector >= last_block)
381 : : return 0;
382 : : }
383 : :
384 : 0 : return fat_get_mapped_cluster(inode, sector, last_block, mapped_blocks,
385 : : phys);
386 : : }
|
