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