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