]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
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> | |
5a0e3ad6 | 12 | #include <linux/slab.h> |
1da177e4 | 13 | #include <linux/buffer_head.h> |
9e975dae | 14 | #include "fat.h" |
1da177e4 LT |
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 | ||
e18b890b | 38 | static struct kmem_cache *fat_cache_cachep; |
1da177e4 | 39 | |
51cc5068 | 40 | static void init_once(void *foo) |
1da177e4 LT |
41 | { |
42 | struct fat_cache *cache = (struct fat_cache *)foo; | |
43 | ||
a35afb83 | 44 | INIT_LIST_HEAD(&cache->cache_list); |
1da177e4 LT |
45 | } |
46 | ||
47 | int __init fat_cache_init(void) | |
48 | { | |
49 | fat_cache_cachep = kmem_cache_create("fat_cache", | |
50 | sizeof(struct fat_cache), | |
4b6a9316 | 51 | 0, SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD, |
20c2df83 | 52 | init_once); |
1da177e4 LT |
53 | if (fat_cache_cachep == NULL) |
54 | return -ENOMEM; | |
55 | return 0; | |
56 | } | |
57 | ||
ef6689ef | 58 | void fat_cache_destroy(void) |
1da177e4 | 59 | { |
1a1d92c1 | 60 | kmem_cache_destroy(fat_cache_cachep); |
1da177e4 LT |
61 | } |
62 | ||
63 | static inline struct fat_cache *fat_cache_alloc(struct inode *inode) | |
64 | { | |
8f593427 | 65 | return kmem_cache_alloc(fat_cache_cachep, GFP_NOFS); |
1da177e4 LT |
66 | } |
67 | ||
68 | static inline void fat_cache_free(struct fat_cache *cache) | |
69 | { | |
70 | BUG_ON(!list_empty(&cache->cache_list)); | |
71 | 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 | if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list) | |
78 | list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru); | |
79 | } | |
80 | ||
81 | 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 | list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) { | |
92 | /* Find the cache of "fclus" or nearest cache. */ | |
93 | if (p->fcluster <= fclus && hit->fcluster < p->fcluster) { | |
94 | hit = p; | |
95 | if ((hit->fcluster + hit->nr_contig) < fclus) { | |
96 | offset = hit->nr_contig; | |
97 | } else { | |
98 | offset = fclus - hit->fcluster; | |
99 | break; | |
100 | } | |
101 | } | |
102 | } | |
103 | if (hit != &nohit) { | |
104 | fat_cache_update_lru(inode, hit); | |
105 | ||
106 | cid->id = MSDOS_I(inode)->cache_valid_id; | |
107 | cid->nr_contig = hit->nr_contig; | |
108 | cid->fcluster = hit->fcluster; | |
109 | cid->dcluster = hit->dcluster; | |
110 | *cached_fclus = cid->fcluster + offset; | |
111 | *cached_dclus = cid->dcluster + offset; | |
112 | } | |
113 | spin_unlock(&MSDOS_I(inode)->cache_lru_lock); | |
114 | ||
115 | return offset; | |
116 | } | |
117 | ||
118 | static struct fat_cache *fat_cache_merge(struct inode *inode, | |
119 | struct fat_cache_id *new) | |
120 | { | |
121 | struct fat_cache *p; | |
122 | ||
123 | list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) { | |
124 | /* Find the same part as "new" in cluster-chain. */ | |
125 | if (p->fcluster == new->fcluster) { | |
126 | BUG_ON(p->dcluster != new->dcluster); | |
127 | if (new->nr_contig > p->nr_contig) | |
128 | p->nr_contig = new->nr_contig; | |
129 | return p; | |
130 | } | |
131 | } | |
132 | return NULL; | |
133 | } | |
134 | ||
135 | static void fat_cache_add(struct inode *inode, struct fat_cache_id *new) | |
136 | { | |
137 | struct fat_cache *cache, *tmp; | |
138 | ||
139 | if (new->fcluster == -1) /* dummy cache */ | |
140 | return; | |
141 | ||
142 | spin_lock(&MSDOS_I(inode)->cache_lru_lock); | |
143 | if (new->id != FAT_CACHE_VALID && | |
144 | new->id != MSDOS_I(inode)->cache_valid_id) | |
145 | goto out; /* this cache was invalidated */ | |
146 | ||
147 | cache = fat_cache_merge(inode, new); | |
148 | if (cache == NULL) { | |
149 | if (MSDOS_I(inode)->nr_caches < fat_max_cache(inode)) { | |
150 | MSDOS_I(inode)->nr_caches++; | |
151 | spin_unlock(&MSDOS_I(inode)->cache_lru_lock); | |
152 | ||
153 | tmp = fat_cache_alloc(inode); | |
70030929 OH |
154 | if (!tmp) { |
155 | spin_lock(&MSDOS_I(inode)->cache_lru_lock); | |
156 | MSDOS_I(inode)->nr_caches--; | |
157 | spin_unlock(&MSDOS_I(inode)->cache_lru_lock); | |
158 | return; | |
159 | } | |
160 | ||
1da177e4 LT |
161 | spin_lock(&MSDOS_I(inode)->cache_lru_lock); |
162 | cache = fat_cache_merge(inode, new); | |
163 | if (cache != NULL) { | |
164 | MSDOS_I(inode)->nr_caches--; | |
165 | fat_cache_free(tmp); | |
166 | goto out_update_lru; | |
167 | } | |
168 | cache = tmp; | |
169 | } else { | |
170 | struct list_head *p = MSDOS_I(inode)->cache_lru.prev; | |
171 | cache = list_entry(p, struct fat_cache, cache_list); | |
172 | } | |
173 | cache->fcluster = new->fcluster; | |
174 | cache->dcluster = new->dcluster; | |
175 | 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 | 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 | while (!list_empty(&i->cache_lru)) { | |
c9051829 CJB |
193 | cache = list_entry(i->cache_lru.next, |
194 | struct fat_cache, cache_list); | |
1da177e4 LT |
195 | list_del_init(&cache->cache_list); |
196 | i->nr_caches--; | |
197 | fat_cache_free(cache); | |
198 | } | |
199 | /* Update. The copy of caches before this id is discarded. */ | |
200 | i->cache_valid_id++; | |
201 | if (i->cache_valid_id == FAT_CACHE_VALID) | |
202 | i->cache_valid_id++; | |
203 | } | |
204 | ||
205 | void fat_cache_inval_inode(struct inode *inode) | |
206 | { | |
207 | spin_lock(&MSDOS_I(inode)->cache_lru_lock); | |
208 | __fat_cache_inval_inode(inode); | |
209 | spin_unlock(&MSDOS_I(inode)->cache_lru_lock); | |
210 | } | |
211 | ||
212 | static inline int cache_contiguous(struct fat_cache_id *cid, int dclus) | |
213 | { | |
214 | cid->nr_contig++; | |
215 | 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 | cid->id = FAT_CACHE_VALID; | |
221 | cid->fcluster = fclus; | |
222 | cid->dcluster = dclus; | |
223 | cid->nr_contig = 0; | |
224 | } | |
225 | ||
226 | int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus) | |
227 | { | |
228 | struct super_block *sb = inode->i_sb; | |
229 | 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 | BUG_ON(MSDOS_I(inode)->i_start == 0); | |
235 | ||
236 | *fclus = 0; | |
237 | *dclus = MSDOS_I(inode)->i_start; | |
238 | if (cluster == 0) | |
239 | return 0; | |
240 | ||
241 | 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 | while (*fclus < cluster) { | |
251 | /* prevent the infinite loop of cluster chain */ | |
252 | if (*fclus > limit) { | |
aaa04b48 OH |
253 | fat_fs_error_ratelimit(sb, |
254 | "%s: detected the cluster chain loop" | |
255 | " (i_pos %lld)", __func__, | |
256 | MSDOS_I(inode)->i_pos); | |
1da177e4 LT |
257 | nr = -EIO; |
258 | goto out; | |
259 | } | |
260 | ||
261 | nr = fat_ent_read(inode, &fatent, *dclus); | |
262 | if (nr < 0) | |
263 | goto out; | |
264 | else if (nr == FAT_ENT_FREE) { | |
c9051829 CJB |
265 | fat_fs_error_ratelimit(sb, |
266 | "%s: invalid cluster chain (i_pos %lld)", | |
267 | __func__, | |
268 | MSDOS_I(inode)->i_pos); | |
1da177e4 LT |
269 | nr = -EIO; |
270 | goto out; | |
271 | } else if (nr == FAT_ENT_EOF) { | |
272 | fat_cache_add(inode, &cid); | |
273 | goto out; | |
274 | } | |
275 | (*fclus)++; | |
276 | *dclus = nr; | |
277 | if (!cache_contiguous(&cid, *dclus)) | |
278 | cache_init(&cid, *fclus, *dclus); | |
279 | } | |
280 | nr = 0; | |
281 | fat_cache_add(inode, &cid); | |
282 | out: | |
283 | fatent_brelse(&fatent); | |
284 | return nr; | |
285 | } | |
286 | ||
287 | static int fat_bmap_cluster(struct inode *inode, int cluster) | |
288 | { | |
289 | struct super_block *sb = inode->i_sb; | |
290 | int ret, fclus, dclus; | |
291 | ||
292 | if (MSDOS_I(inode)->i_start == 0) | |
293 | return 0; | |
294 | ||
295 | ret = fat_get_cluster(inode, cluster, &fclus, &dclus); | |
296 | if (ret < 0) | |
297 | return ret; | |
298 | else if (ret == FAT_ENT_EOF) { | |
85c78591 | 299 | fat_fs_error(sb, "%s: request beyond EOF (i_pos %lld)", |
8e24eea7 | 300 | __func__, MSDOS_I(inode)->i_pos); |
1da177e4 LT |
301 | return -EIO; |
302 | } | |
303 | return dclus; | |
304 | } | |
305 | ||
e5174baa | 306 | int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys, |
2bdf67eb | 307 | unsigned long *mapped_blocks, int create) |
1da177e4 LT |
308 | { |
309 | struct super_block *sb = inode->i_sb; | |
310 | struct msdos_sb_info *sbi = MSDOS_SB(sb); | |
2bdf67eb OH |
311 | const unsigned long blocksize = sb->s_blocksize; |
312 | const unsigned char blocksize_bits = sb->s_blocksize_bits; | |
1da177e4 LT |
313 | sector_t last_block; |
314 | int cluster, offset; | |
315 | ||
316 | *phys = 0; | |
e5174baa | 317 | *mapped_blocks = 0; |
1da177e4 | 318 | if ((sbi->fat_bits != 32) && (inode->i_ino == MSDOS_ROOT_INO)) { |
e5174baa | 319 | if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits)) { |
1da177e4 | 320 | *phys = sector + sbi->dir_start; |
e5174baa OH |
321 | *mapped_blocks = 1; |
322 | } | |
1da177e4 LT |
323 | return 0; |
324 | } | |
2bdf67eb OH |
325 | |
326 | last_block = (i_size_read(inode) + (blocksize - 1)) >> blocksize_bits; | |
327 | if (sector >= last_block) { | |
328 | if (!create) | |
329 | return 0; | |
330 | ||
331 | /* | |
332 | * ->mmu_private can access on only allocation path. | |
333 | * (caller must hold ->i_mutex) | |
334 | */ | |
335 | last_block = (MSDOS_I(inode)->mmu_private + (blocksize - 1)) | |
336 | >> blocksize_bits; | |
337 | if (sector >= last_block) | |
338 | return 0; | |
339 | } | |
1da177e4 LT |
340 | |
341 | cluster = sector >> (sbi->cluster_bits - sb->s_blocksize_bits); | |
342 | offset = sector & (sbi->sec_per_clus - 1); | |
343 | cluster = fat_bmap_cluster(inode, cluster); | |
344 | if (cluster < 0) | |
345 | return cluster; | |
e5174baa | 346 | else if (cluster) { |
1da177e4 | 347 | *phys = fat_clus_to_blknr(sbi, cluster) + offset; |
e5174baa OH |
348 | *mapped_blocks = sbi->sec_per_clus - offset; |
349 | if (*mapped_blocks > last_block - sector) | |
350 | *mapped_blocks = last_block - sector; | |
351 | } | |
1da177e4 LT |
352 | return 0; |
353 | } |