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