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/msdos_fs.h> 13 #include <linux/buffer_head.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 static inline int fat_max_cache(struct inode *inode) 33 { 34 return FAT_MAX_CACHE; 35 } 36 37 static kmem_cache_t *fat_cache_cachep; 38 39 static void init_once(void *foo, kmem_cache_t *cachep, unsigned long flags) 40 { 41 struct fat_cache *cache = (struct fat_cache *)foo; 42 43 if ((flags & (SLAB_CTOR_VERIFY|SLAB_CTOR_CONSTRUCTOR)) == 44 SLAB_CTOR_CONSTRUCTOR) 45 INIT_LIST_HEAD(&cache->cache_list); 46 } 47 48 int __init fat_cache_init(void) 49 { 50 fat_cache_cachep = kmem_cache_create("fat_cache", 51 sizeof(struct fat_cache), 52 0, SLAB_RECLAIM_ACCOUNT, 53 init_once, NULL); 54 if (fat_cache_cachep == NULL) 55 return -ENOMEM; 56 return 0; 57 } 58 59 void fat_cache_destroy(void) 60 { 61 if (kmem_cache_destroy(fat_cache_cachep)) 62 printk(KERN_INFO "fat_cache: not all structures were freed\n"); 63 } 64 65 static inline struct fat_cache *fat_cache_alloc(struct inode *inode) 66 { 67 return kmem_cache_alloc(fat_cache_cachep, SLAB_KERNEL); 68 } 69 70 static inline void fat_cache_free(struct fat_cache *cache) 71 { 72 BUG_ON(!list_empty(&cache->cache_list)); 73 kmem_cache_free(fat_cache_cachep, cache); 74 } 75 76 static inline void fat_cache_update_lru(struct inode *inode, 77 struct fat_cache *cache) 78 { 79 if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list) 80 list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru); 81 } 82 83 static int fat_cache_lookup(struct inode *inode, int fclus, 84 struct fat_cache_id *cid, 85 int *cached_fclus, int *cached_dclus) 86 { 87 static struct fat_cache nohit = { .fcluster = 0, }; 88 89 struct fat_cache *hit = &nohit, *p; 90 int offset = -1; 91 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) { 96 hit = p; 97 if ((hit->fcluster + hit->nr_contig) < fclus) { 98 offset = hit->nr_contig; 99 } else { 100 offset = fclus - hit->fcluster; 101 break; 102 } 103 } 104 } 105 if (hit != &nohit) { 106 fat_cache_update_lru(inode, hit); 107 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; 114 } 115 spin_unlock(&MSDOS_I(inode)->cache_lru_lock); 116 117 return offset; 118 } 119 120 static struct fat_cache *fat_cache_merge(struct inode *inode, 121 struct fat_cache_id *new) 122 { 123 struct fat_cache *p; 124 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; 131 return p; 132 } 133 } 134 return NULL; 135 } 136 137 static void fat_cache_add(struct inode *inode, struct fat_cache_id *new) 138 { 139 struct fat_cache *cache, *tmp; 140 141 if (new->fcluster == -1) /* dummy cache */ 142 return; 143 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 */ 148 149 cache = fat_cache_merge(inode, new); 150 if (cache == NULL) { 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); 154 155 tmp = fat_cache_alloc(inode); 156 spin_lock(&MSDOS_I(inode)->cache_lru_lock); 157 cache = fat_cache_merge(inode, new); 158 if (cache != NULL) { 159 MSDOS_I(inode)->nr_caches--; 160 fat_cache_free(tmp); 161 goto out_update_lru; 162 } 163 cache = tmp; 164 } else { 165 struct list_head *p = MSDOS_I(inode)->cache_lru.prev; 166 cache = list_entry(p, struct fat_cache, cache_list); 167 } 168 cache->fcluster = new->fcluster; 169 cache->dcluster = new->dcluster; 170 cache->nr_contig = new->nr_contig; 171 } 172 out_update_lru: 173 fat_cache_update_lru(inode, cache); 174 out: 175 spin_unlock(&MSDOS_I(inode)->cache_lru_lock); 176 } 177 178 /* 179 * Cache invalidation occurs rarely, thus the LRU chain is not updated. It 180 * fixes itself after a while. 181 */ 182 static void __fat_cache_inval_inode(struct inode *inode) 183 { 184 struct msdos_inode_info *i = MSDOS_I(inode); 185 struct fat_cache *cache; 186 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); 190 i->nr_caches--; 191 fat_cache_free(cache); 192 } 193 /* Update. The copy of caches before this id is discarded. */ 194 i->cache_valid_id++; 195 if (i->cache_valid_id == FAT_CACHE_VALID) 196 i->cache_valid_id++; 197 } 198 199 void fat_cache_inval_inode(struct inode *inode) 200 { 201 spin_lock(&MSDOS_I(inode)->cache_lru_lock); 202 __fat_cache_inval_inode(inode); 203 spin_unlock(&MSDOS_I(inode)->cache_lru_lock); 204 } 205 206 static inline int cache_contiguous(struct fat_cache_id *cid, int dclus) 207 { 208 cid->nr_contig++; 209 return ((cid->dcluster + cid->nr_contig) == dclus); 210 } 211 212 static inline void cache_init(struct fat_cache_id *cid, int fclus, int dclus) 213 { 214 cid->id = FAT_CACHE_VALID; 215 cid->fcluster = fclus; 216 cid->dcluster = dclus; 217 cid->nr_contig = 0; 218 } 219 220 int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus) 221 { 222 struct super_block *sb = inode->i_sb; 223 const int limit = sb->s_maxbytes >> MSDOS_SB(sb)->cluster_bits; 224 struct fat_entry fatent; 225 struct fat_cache_id cid; 226 int nr; 227 228 BUG_ON(MSDOS_I(inode)->i_start == 0); 229 230 *fclus = 0; 231 *dclus = MSDOS_I(inode)->i_start; 232 if (cluster == 0) 233 return 0; 234 235 if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) { 236 /* 237 * dummy, always not contiguous 238 * This is reinitialized by cache_init(), later. 239 */ 240 cache_init(&cid, -1, -1); 241 } 242 243 fatent_init(&fatent); 244 while (*fclus < cluster) { 245 /* prevent the infinite loop of cluster chain */ 246 if (*fclus > limit) { 247 fat_fs_panic(sb, "%s: detected the cluster chain loop" 248 " (i_pos %lld)", __FUNCTION__, 249 MSDOS_I(inode)->i_pos); 250 nr = -EIO; 251 goto out; 252 } 253 254 nr = fat_ent_read(inode, &fatent, *dclus); 255 if (nr < 0) 256 goto out; 257 else if (nr == FAT_ENT_FREE) { 258 fat_fs_panic(sb, "%s: invalid cluster chain" 259 " (i_pos %lld)", __FUNCTION__, 260 MSDOS_I(inode)->i_pos); 261 nr = -EIO; 262 goto out; 263 } else if (nr == FAT_ENT_EOF) { 264 fat_cache_add(inode, &cid); 265 goto out; 266 } 267 (*fclus)++; 268 *dclus = nr; 269 if (!cache_contiguous(&cid, *dclus)) 270 cache_init(&cid, *fclus, *dclus); 271 } 272 nr = 0; 273 fat_cache_add(inode, &cid); 274 out: 275 fatent_brelse(&fatent); 276 return nr; 277 } 278 279 static int fat_bmap_cluster(struct inode *inode, int cluster) 280 { 281 struct super_block *sb = inode->i_sb; 282 int ret, fclus, dclus; 283 284 if (MSDOS_I(inode)->i_start == 0) 285 return 0; 286 287 ret = fat_get_cluster(inode, cluster, &fclus, &dclus); 288 if (ret < 0) 289 return ret; 290 else if (ret == FAT_ENT_EOF) { 291 fat_fs_panic(sb, "%s: request beyond EOF (i_pos %lld)", 292 __FUNCTION__, MSDOS_I(inode)->i_pos); 293 return -EIO; 294 } 295 return dclus; 296 } 297 298 int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys, 299 unsigned long *mapped_blocks) 300 { 301 struct super_block *sb = inode->i_sb; 302 struct msdos_sb_info *sbi = MSDOS_SB(sb); 303 sector_t last_block; 304 int cluster, offset; 305 306 *phys = 0; 307 *mapped_blocks = 0; 308 if ((sbi->fat_bits != 32) && (inode->i_ino == MSDOS_ROOT_INO)) { 309 if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits)) { 310 *phys = sector + sbi->dir_start; 311 *mapped_blocks = 1; 312 } 313 return 0; 314 } 315 last_block = (MSDOS_I(inode)->mmu_private + (sb->s_blocksize - 1)) 316 >> sb->s_blocksize_bits; 317 if (sector >= last_block) 318 return 0; 319 320 cluster = sector >> (sbi->cluster_bits - sb->s_blocksize_bits); 321 offset = sector & (sbi->sec_per_clus - 1); 322 cluster = fat_bmap_cluster(inode, cluster); 323 if (cluster < 0) 324 return cluster; 325 else if (cluster) { 326 *phys = fat_clus_to_blknr(sbi, cluster) + offset; 327 *mapped_blocks = sbi->sec_per_clus - offset; 328 if (*mapped_blocks > last_block - sector) 329 *mapped_blocks = last_block - sector; 330 } 331 return 0; 332 } 333