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