4 * Written 1992,1993 by Werner Almesberger
6 * Mar 1999. AV. Changed cache, so that it uses the starting cluster instead
8 * May 1999. AV. Fixed the bogosity with FAT32 (read "FAT28"). Fscking lusers.
12 #include <linux/msdos_fs.h>
13 #include <linux/buffer_head.h>
15 /* this must be > 0. */
16 #define FAT_MAX_CACHE 8
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. */
32 static inline int fat_max_cache(struct inode *inode)
37 static kmem_cache_t *fat_cache_cachep;
39 static void init_once(void *foo, kmem_cache_t *cachep, unsigned long flags)
41 struct fat_cache *cache = (struct fat_cache *)foo;
43 if ((flags & (SLAB_CTOR_VERIFY|SLAB_CTOR_CONSTRUCTOR)) ==
44 SLAB_CTOR_CONSTRUCTOR)
45 INIT_LIST_HEAD(&cache->cache_list);
48 int __init fat_cache_init(void)
50 fat_cache_cachep = kmem_cache_create("fat_cache",
51 sizeof(struct fat_cache),
52 0, SLAB_RECLAIM_ACCOUNT,
54 if (fat_cache_cachep == NULL)
59 void __exit fat_cache_destroy(void)
61 if (kmem_cache_destroy(fat_cache_cachep))
62 printk(KERN_INFO "fat_cache: not all structures were freed\n");
65 static inline struct fat_cache *fat_cache_alloc(struct inode *inode)
67 return kmem_cache_alloc(fat_cache_cachep, SLAB_KERNEL);
70 static inline void fat_cache_free(struct fat_cache *cache)
72 BUG_ON(!list_empty(&cache->cache_list));
73 kmem_cache_free(fat_cache_cachep, cache);
76 static inline void fat_cache_update_lru(struct inode *inode,
77 struct fat_cache *cache)
79 if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list)
80 list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru);
83 static int fat_cache_lookup(struct inode *inode, int fclus,
84 struct fat_cache_id *cid,
85 int *cached_fclus, int *cached_dclus)
87 static struct fat_cache nohit = { .fcluster = 0, };
89 struct fat_cache *hit = &nohit, *p;
92 spin_lock(&MSDOS_I(inode)->cache_lru_lock);
93 list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
94 /* Find the cache of "fclus" or nearest cache. */
95 if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {
97 if ((hit->fcluster + hit->nr_contig) < fclus) {
98 offset = hit->nr_contig;
100 offset = fclus - hit->fcluster;
106 fat_cache_update_lru(inode, hit);
108 cid->id = MSDOS_I(inode)->cache_valid_id;
109 cid->nr_contig = hit->nr_contig;
110 cid->fcluster = hit->fcluster;
111 cid->dcluster = hit->dcluster;
112 *cached_fclus = cid->fcluster + offset;
113 *cached_dclus = cid->dcluster + offset;
115 spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
120 static struct fat_cache *fat_cache_merge(struct inode *inode,
121 struct fat_cache_id *new)
125 list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
126 /* Find the same part as "new" in cluster-chain. */
127 if (p->fcluster == new->fcluster) {
128 BUG_ON(p->dcluster != new->dcluster);
129 if (new->nr_contig > p->nr_contig)
130 p->nr_contig = new->nr_contig;
137 static void fat_cache_add(struct inode *inode, struct fat_cache_id *new)
139 struct fat_cache *cache, *tmp;
141 if (new->fcluster == -1) /* dummy cache */
144 spin_lock(&MSDOS_I(inode)->cache_lru_lock);
145 if (new->id != FAT_CACHE_VALID &&
146 new->id != MSDOS_I(inode)->cache_valid_id)
147 goto out; /* this cache was invalidated */
149 cache = fat_cache_merge(inode, new);
151 if (MSDOS_I(inode)->nr_caches < fat_max_cache(inode)) {
152 MSDOS_I(inode)->nr_caches++;
153 spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
155 tmp = fat_cache_alloc(inode);
156 spin_lock(&MSDOS_I(inode)->cache_lru_lock);
157 cache = fat_cache_merge(inode, new);
159 MSDOS_I(inode)->nr_caches--;
165 struct list_head *p = MSDOS_I(inode)->cache_lru.prev;
166 cache = list_entry(p, struct fat_cache, cache_list);
168 cache->fcluster = new->fcluster;
169 cache->dcluster = new->dcluster;
170 cache->nr_contig = new->nr_contig;
173 fat_cache_update_lru(inode, cache);
175 spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
179 * Cache invalidation occurs rarely, thus the LRU chain is not updated. It
180 * fixes itself after a while.
182 static void __fat_cache_inval_inode(struct inode *inode)
184 struct msdos_inode_info *i = MSDOS_I(inode);
185 struct fat_cache *cache;
187 while (!list_empty(&i->cache_lru)) {
188 cache = list_entry(i->cache_lru.next, struct fat_cache, cache_list);
189 list_del_init(&cache->cache_list);
191 fat_cache_free(cache);
193 /* Update. The copy of caches before this id is discarded. */
195 if (i->cache_valid_id == FAT_CACHE_VALID)
199 void fat_cache_inval_inode(struct inode *inode)
201 spin_lock(&MSDOS_I(inode)->cache_lru_lock);
202 __fat_cache_inval_inode(inode);
203 spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
206 int __fat_access(struct super_block *sb, int nr, int new_value)
208 struct msdos_sb_info *sbi = MSDOS_SB(sb);
209 struct buffer_head *bh, *bh2, *c_bh, *c_bh2;
210 unsigned char *p_first, *p_last;
211 int copy, first, last, next, b;
213 if (sbi->fat_bits == 32) {
215 } else if (sbi->fat_bits == 16) {
221 b = sbi->fat_start + (first >> sb->s_blocksize_bits);
222 if (!(bh = sb_bread(sb, b))) {
223 printk(KERN_ERR "FAT: bread(block %d) in"
224 " fat_access failed\n", b);
227 if ((first >> sb->s_blocksize_bits) == (last >> sb->s_blocksize_bits)) {
230 if (!(bh2 = sb_bread(sb, b + 1))) {
232 printk(KERN_ERR "FAT: bread(block %d) in"
233 " fat_access failed\n", b + 1);
237 if (sbi->fat_bits == 32) {
238 p_first = p_last = NULL; /* GCC needs that stuff */
239 next = le32_to_cpu(((__le32 *) bh->b_data)[(first &
240 (sb->s_blocksize - 1)) >> 2]);
241 /* Fscking Microsoft marketing department. Their "32" is 28. */
243 } else if (sbi->fat_bits == 16) {
244 p_first = p_last = NULL; /* GCC needs that stuff */
245 next = le16_to_cpu(((__le16 *) bh->b_data)[(first &
246 (sb->s_blocksize - 1)) >> 1]);
248 p_first = &((__u8 *)bh->b_data)[first & (sb->s_blocksize - 1)];
249 p_last = &((__u8 *)bh2->b_data)[(first + 1) & (sb->s_blocksize - 1)];
251 next = ((*p_first >> 4) | (*p_last << 4)) & 0xfff;
253 next = (*p_first+(*p_last << 8)) & 0xfff;
255 if (new_value != -1) {
256 if (sbi->fat_bits == 32) {
257 ((__le32 *)bh->b_data)[(first & (sb->s_blocksize - 1)) >> 2]
258 = cpu_to_le32(new_value);
259 } else if (sbi->fat_bits == 16) {
260 ((__le16 *)bh->b_data)[(first & (sb->s_blocksize - 1)) >> 1]
261 = cpu_to_le16(new_value);
264 *p_first = (*p_first & 0xf) | (new_value << 4);
265 *p_last = new_value >> 4;
268 *p_first = new_value & 0xff;
269 *p_last = (*p_last & 0xf0) | (new_value >> 8);
271 mark_buffer_dirty(bh2);
273 mark_buffer_dirty(bh);
274 for (copy = 1; copy < sbi->fats; copy++) {
275 b = sbi->fat_start + (first >> sb->s_blocksize_bits)
276 + sbi->fat_length * copy;
277 if (!(c_bh = sb_bread(sb, b)))
280 if (!(c_bh2 = sb_bread(sb, b+1))) {
284 memcpy(c_bh2->b_data, bh2->b_data, sb->s_blocksize);
285 mark_buffer_dirty(c_bh2);
288 memcpy(c_bh->b_data, bh->b_data, sb->s_blocksize);
289 mark_buffer_dirty(c_bh);
300 * Returns the this'th FAT entry, -1 if it is an end-of-file entry. If
301 * new_value is != -1, that FAT entry is replaced by it.
303 int fat_access(struct super_block *sb, int nr, int new_value)
308 if (nr < 2 || MSDOS_SB(sb)->clusters + 2 <= nr) {
309 fat_fs_panic(sb, "invalid access to FAT (entry 0x%08x)", nr);
312 if (new_value == FAT_ENT_EOF)
313 new_value = EOF_FAT(sb);
315 next = __fat_access(sb, nr, new_value);
318 if (next >= BAD_FAT(sb))
324 static inline int cache_contiguous(struct fat_cache_id *cid, int dclus)
327 return ((cid->dcluster + cid->nr_contig) == dclus);
330 static inline void cache_init(struct fat_cache_id *cid, int fclus, int dclus)
332 cid->id = FAT_CACHE_VALID;
333 cid->fcluster = fclus;
334 cid->dcluster = dclus;
338 int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus)
340 struct super_block *sb = inode->i_sb;
341 const int limit = sb->s_maxbytes >> MSDOS_SB(sb)->cluster_bits;
342 struct fat_cache_id cid;
345 BUG_ON(MSDOS_I(inode)->i_start == 0);
348 *dclus = MSDOS_I(inode)->i_start;
352 if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) {
354 * dummy, always not contiguous
355 * This is reinitialized by cache_init(), later.
357 cache_init(&cid, -1, -1);
360 while (*fclus < cluster) {
361 /* prevent the infinite loop of cluster chain */
362 if (*fclus > limit) {
363 fat_fs_panic(sb, "%s: detected the cluster chain loop"
364 " (i_pos %lld)", __FUNCTION__,
365 MSDOS_I(inode)->i_pos);
369 nr = fat_access(sb, *dclus, -1);
372 else if (nr == FAT_ENT_FREE) {
373 fat_fs_panic(sb, "%s: invalid cluster chain"
374 " (i_pos %lld)", __FUNCTION__,
375 MSDOS_I(inode)->i_pos);
377 } else if (nr == FAT_ENT_EOF) {
378 fat_cache_add(inode, &cid);
383 if (!cache_contiguous(&cid, *dclus))
384 cache_init(&cid, *fclus, *dclus);
386 fat_cache_add(inode, &cid);
390 static int fat_bmap_cluster(struct inode *inode, int cluster)
392 struct super_block *sb = inode->i_sb;
393 int ret, fclus, dclus;
395 if (MSDOS_I(inode)->i_start == 0)
398 ret = fat_get_cluster(inode, cluster, &fclus, &dclus);
401 else if (ret == FAT_ENT_EOF) {
402 fat_fs_panic(sb, "%s: request beyond EOF (i_pos %lld)",
403 __FUNCTION__, MSDOS_I(inode)->i_pos);
409 int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys)
411 struct super_block *sb = inode->i_sb;
412 struct msdos_sb_info *sbi = MSDOS_SB(sb);
417 if ((sbi->fat_bits != 32) &&
418 (inode->i_ino == MSDOS_ROOT_INO || (S_ISDIR(inode->i_mode) &&
419 !MSDOS_I(inode)->i_start))) {
420 if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits))
421 *phys = sector + sbi->dir_start;
424 last_block = (MSDOS_I(inode)->mmu_private + (sb->s_blocksize - 1))
425 >> sb->s_blocksize_bits;
426 if (sector >= last_block)
429 cluster = sector >> (sbi->cluster_bits - sb->s_blocksize_bits);
430 offset = sector & (sbi->sec_per_clus - 1);
431 cluster = fat_bmap_cluster(inode, cluster);
435 *phys = ((sector_t)cluster - 2) * sbi->sec_per_clus
436 + sbi->data_start + offset;
441 /* Free all clusters after the skip'th cluster. */
442 int fat_free(struct inode *inode, int skip)
444 struct super_block *sb = inode->i_sb;
445 int nr, ret, fclus, dclus;
447 if (MSDOS_I(inode)->i_start == 0)
451 ret = fat_get_cluster(inode, skip - 1, &fclus, &dclus);
454 else if (ret == FAT_ENT_EOF)
457 nr = fat_access(sb, dclus, -1);
458 if (nr == FAT_ENT_EOF)
462 * write a new EOF, and get the remaining cluster
465 nr = fat_access(sb, dclus, FAT_ENT_EOF);
470 fat_cache_inval_inode(inode);
472 fat_cache_inval_inode(inode);
474 nr = MSDOS_I(inode)->i_start;
475 MSDOS_I(inode)->i_start = 0;
476 MSDOS_I(inode)->i_logstart = 0;
477 mark_inode_dirty(inode);
482 nr = fat_access(sb, nr, FAT_ENT_FREE);
485 else if (nr == FAT_ENT_FREE) {
486 fat_fs_panic(sb, "%s: deleting beyond EOF (i_pos %lld)",
487 __FUNCTION__, MSDOS_I(inode)->i_pos);
491 if (MSDOS_SB(sb)->free_clusters != -1)
492 MSDOS_SB(sb)->free_clusters++;
493 inode->i_blocks -= MSDOS_SB(sb)->cluster_size >> 9;
494 } while (nr != FAT_ENT_EOF);
495 fat_clusters_flush(sb);