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