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 
exfat_cache_init_once(void * c)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 
exfat_cache_init(void)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|SLAB_MEM_SPREAD,
50 				exfat_cache_init_once);
51 	if (!exfat_cachep)
52 		return -ENOMEM;
53 	return 0;
54 }
55 
exfat_cache_shutdown(void)56 void exfat_cache_shutdown(void)
57 {
58 	if (!exfat_cachep)
59 		return;
60 	kmem_cache_destroy(exfat_cachep);
61 }
62 
exfat_cache_alloc(void)63 static inline struct exfat_cache *exfat_cache_alloc(void)
64 {
65 	return kmem_cache_alloc(exfat_cachep, GFP_NOFS);
66 }
67 
exfat_cache_free(struct exfat_cache * cache)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 
exfat_cache_update_lru(struct inode * inode,struct exfat_cache * cache)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 
exfat_cache_lookup(struct inode * inode,unsigned int fclus,struct exfat_cache_id * cid,unsigned int * cached_fclus,unsigned int * cached_dclus)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 
exfat_cache_merge(struct inode * inode,struct exfat_cache_id * new)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 
exfat_cache_add(struct inode * inode,struct exfat_cache_id * new)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  */
__exfat_cache_inval_inode(struct inode * inode)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 
exfat_cache_inval_inode(struct inode * inode)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 
cache_contiguous(struct exfat_cache_id * cid,unsigned int dclus)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 
cache_init(struct exfat_cache_id * cid,unsigned int fclus,unsigned int dclus)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 
exfat_get_cluster(struct inode * inode,unsigned int cluster,unsigned int * fclus,unsigned int * dclus,unsigned int * last_dclus,int allow_eof)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