GNU Linux-libre 5.19-rc6-gnu
[releases.git] / fs / exfat / cache.c
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|SLAB_MEM_SPREAD,
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 }