1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * linux/fs/fat/cache.c 4 * 5 * Written 1992,1993 by Werner Almesberger 6 * 7 * Mar 1999. AV. Changed cache, so that it uses the starting cluster instead 8 * of inode number. 9 * May 1999. AV. Fixed the bogosity with FAT32 (read "FAT28"). Fscking lusers. 10 * Copyright (C) 2012-2013 Samsung Electronics Co., Ltd. 11 */ 12 13 #include <linux/slab.h> 14 #include <asm/unaligned.h> 15 #include <linux/buffer_head.h> 16 17 #include "exfat_raw.h" 18 #include "exfat_fs.h" 19 20 #define EXFAT_MAX_CACHE 16 21 22 struct exfat_cache { 23 struct list_head cache_list; 24 unsigned int nr_contig; /* number of contiguous clusters */ 25 unsigned int fcluster; /* cluster number in the file. */ 26 unsigned int dcluster; /* cluster number on disk. */ 27 }; 28 29 struct exfat_cache_id { 30 unsigned int id; 31 unsigned int nr_contig; 32 unsigned int fcluster; 33 unsigned int dcluster; 34 }; 35 36 static struct kmem_cache *exfat_cachep; 37 38 static void exfat_cache_init_once(void *c) 39 { 40 struct exfat_cache *cache = (struct exfat_cache *)c; 41 42 INIT_LIST_HEAD(&cache->cache_list); 43 } 44 45 int exfat_cache_init(void) 46 { 47 exfat_cachep = kmem_cache_create("exfat_cache", 48 sizeof(struct exfat_cache), 49 0, SLAB_RECLAIM_ACCOUNT, 50 exfat_cache_init_once); 51 if (!exfat_cachep) 52 return -ENOMEM; 53 return 0; 54 } 55 56 void exfat_cache_shutdown(void) 57 { 58 if (!exfat_cachep) 59 return; 60 kmem_cache_destroy(exfat_cachep); 61 } 62 63 static inline struct exfat_cache *exfat_cache_alloc(void) 64 { 65 return kmem_cache_alloc(exfat_cachep, GFP_NOFS); 66 } 67 68 static inline void exfat_cache_free(struct exfat_cache *cache) 69 { 70 WARN_ON(!list_empty(&cache->cache_list)); 71 kmem_cache_free(exfat_cachep, cache); 72 } 73 74 static inline void exfat_cache_update_lru(struct inode *inode, 75 struct exfat_cache *cache) 76 { 77 struct exfat_inode_info *ei = EXFAT_I(inode); 78 79 if (ei->cache_lru.next != &cache->cache_list) 80 list_move(&cache->cache_list, &ei->cache_lru); 81 } 82 83 static unsigned int exfat_cache_lookup(struct inode *inode, 84 unsigned int fclus, struct exfat_cache_id *cid, 85 unsigned int *cached_fclus, unsigned int *cached_dclus) 86 { 87 struct exfat_inode_info *ei = EXFAT_I(inode); 88 static struct exfat_cache nohit = { .fcluster = 0, }; 89 struct exfat_cache *hit = &nohit, *p; 90 unsigned int offset = EXFAT_EOF_CLUSTER; 91 92 spin_lock(&ei->cache_lru_lock); 93 list_for_each_entry(p, &ei->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 exfat_cache_update_lru(inode, hit); 107 108 cid->id = ei->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(&ei->cache_lru_lock); 116 117 return offset; 118 } 119 120 static struct exfat_cache *exfat_cache_merge(struct inode *inode, 121 struct exfat_cache_id *new) 122 { 123 struct exfat_inode_info *ei = EXFAT_I(inode); 124 struct exfat_cache *p; 125 126 list_for_each_entry(p, &ei->cache_lru, cache_list) { 127 /* Find the same part as "new" in cluster-chain. */ 128 if (p->fcluster == new->fcluster) { 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 exfat_cache_add(struct inode *inode, 138 struct exfat_cache_id *new) 139 { 140 struct exfat_inode_info *ei = EXFAT_I(inode); 141 struct exfat_cache *cache, *tmp; 142 143 if (new->fcluster == EXFAT_EOF_CLUSTER) /* dummy cache */ 144 return; 145 146 spin_lock(&ei->cache_lru_lock); 147 if (new->id != EXFAT_CACHE_VALID && 148 new->id != ei->cache_valid_id) 149 goto unlock; /* this cache was invalidated */ 150 151 cache = exfat_cache_merge(inode, new); 152 if (cache == NULL) { 153 if (ei->nr_caches < EXFAT_MAX_CACHE) { 154 ei->nr_caches++; 155 spin_unlock(&ei->cache_lru_lock); 156 157 tmp = exfat_cache_alloc(); 158 if (!tmp) { 159 spin_lock(&ei->cache_lru_lock); 160 ei->nr_caches--; 161 spin_unlock(&ei->cache_lru_lock); 162 return; 163 } 164 165 spin_lock(&ei->cache_lru_lock); 166 cache = exfat_cache_merge(inode, new); 167 if (cache != NULL) { 168 ei->nr_caches--; 169 exfat_cache_free(tmp); 170 goto out_update_lru; 171 } 172 cache = tmp; 173 } else { 174 struct list_head *p = ei->cache_lru.prev; 175 176 cache = list_entry(p, 177 struct exfat_cache, cache_list); 178 } 179 cache->fcluster = new->fcluster; 180 cache->dcluster = new->dcluster; 181 cache->nr_contig = new->nr_contig; 182 } 183 out_update_lru: 184 exfat_cache_update_lru(inode, cache); 185 unlock: 186 spin_unlock(&ei->cache_lru_lock); 187 } 188 189 /* 190 * Cache invalidation occurs rarely, thus the LRU chain is not updated. It 191 * fixes itself after a while. 192 */ 193 static void __exfat_cache_inval_inode(struct inode *inode) 194 { 195 struct exfat_inode_info *ei = EXFAT_I(inode); 196 struct exfat_cache *cache; 197 198 while (!list_empty(&ei->cache_lru)) { 199 cache = list_entry(ei->cache_lru.next, 200 struct exfat_cache, cache_list); 201 list_del_init(&cache->cache_list); 202 ei->nr_caches--; 203 exfat_cache_free(cache); 204 } 205 /* Update. The copy of caches before this id is discarded. */ 206 ei->cache_valid_id++; 207 if (ei->cache_valid_id == EXFAT_CACHE_VALID) 208 ei->cache_valid_id++; 209 } 210 211 void exfat_cache_inval_inode(struct inode *inode) 212 { 213 struct exfat_inode_info *ei = EXFAT_I(inode); 214 215 spin_lock(&ei->cache_lru_lock); 216 __exfat_cache_inval_inode(inode); 217 spin_unlock(&ei->cache_lru_lock); 218 } 219 220 static inline int cache_contiguous(struct exfat_cache_id *cid, 221 unsigned int dclus) 222 { 223 cid->nr_contig++; 224 return cid->dcluster + cid->nr_contig == dclus; 225 } 226 227 static inline void cache_init(struct exfat_cache_id *cid, 228 unsigned int fclus, unsigned int dclus) 229 { 230 cid->id = EXFAT_CACHE_VALID; 231 cid->fcluster = fclus; 232 cid->dcluster = dclus; 233 cid->nr_contig = 0; 234 } 235 236 int exfat_get_cluster(struct inode *inode, unsigned int cluster, 237 unsigned int *fclus, unsigned int *dclus, 238 unsigned int *last_dclus, int allow_eof) 239 { 240 struct super_block *sb = inode->i_sb; 241 struct exfat_sb_info *sbi = EXFAT_SB(sb); 242 unsigned int limit = sbi->num_clusters; 243 struct exfat_inode_info *ei = EXFAT_I(inode); 244 struct exfat_cache_id cid; 245 unsigned int content; 246 247 if (ei->start_clu == EXFAT_FREE_CLUSTER) { 248 exfat_fs_error(sb, 249 "invalid access to exfat cache (entry 0x%08x)", 250 ei->start_clu); 251 return -EIO; 252 } 253 254 *fclus = 0; 255 *dclus = ei->start_clu; 256 *last_dclus = *dclus; 257 258 /* 259 * Don`t use exfat_cache if zero offset or non-cluster allocation 260 */ 261 if (cluster == 0 || *dclus == EXFAT_EOF_CLUSTER) 262 return 0; 263 264 cache_init(&cid, EXFAT_EOF_CLUSTER, EXFAT_EOF_CLUSTER); 265 266 if (exfat_cache_lookup(inode, cluster, &cid, fclus, dclus) == 267 EXFAT_EOF_CLUSTER) { 268 /* 269 * dummy, always not contiguous 270 * This is reinitialized by cache_init(), later. 271 */ 272 WARN_ON(cid.id != EXFAT_CACHE_VALID || 273 cid.fcluster != EXFAT_EOF_CLUSTER || 274 cid.dcluster != EXFAT_EOF_CLUSTER || 275 cid.nr_contig != 0); 276 } 277 278 if (*fclus == cluster) 279 return 0; 280 281 while (*fclus < cluster) { 282 /* prevent the infinite loop of cluster chain */ 283 if (*fclus > limit) { 284 exfat_fs_error(sb, 285 "detected the cluster chain loop (i_pos %u)", 286 (*fclus)); 287 return -EIO; 288 } 289 290 if (exfat_ent_get(sb, *dclus, &content)) 291 return -EIO; 292 293 *last_dclus = *dclus; 294 *dclus = content; 295 (*fclus)++; 296 297 if (content == EXFAT_EOF_CLUSTER) { 298 if (!allow_eof) { 299 exfat_fs_error(sb, 300 "invalid cluster chain (i_pos %u, last_clus 0x%08x is EOF)", 301 *fclus, (*last_dclus)); 302 return -EIO; 303 } 304 305 break; 306 } 307 308 if (!cache_contiguous(&cid, *dclus)) 309 cache_init(&cid, *fclus, *dclus); 310 } 311 312 exfat_cache_add(inode, &cid); 313 return 0; 314 } 315