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(list: &cache->cache_list); |
43 | } |
44 | |
45 | int exfat_cache_init(void) |
46 | { |
47 | exfat_cachep = kmem_cache_create(name: "exfat_cache" , |
48 | size: sizeof(struct exfat_cache), |
49 | align: 0, SLAB_RECLAIM_ACCOUNT, |
50 | ctor: 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(s: exfat_cachep); |
61 | } |
62 | |
63 | static inline struct exfat_cache *exfat_cache_alloc(void) |
64 | { |
65 | return kmem_cache_alloc(cachep: 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(s: exfat_cachep, objp: 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(list: &cache->cache_list, head: &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(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, cache: 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(lock: &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(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(lock: &ei->cache_lru_lock); |
156 | |
157 | tmp = exfat_cache_alloc(); |
158 | if (!tmp) { |
159 | spin_lock(lock: &ei->cache_lru_lock); |
160 | ei->nr_caches--; |
161 | spin_unlock(lock: &ei->cache_lru_lock); |
162 | return; |
163 | } |
164 | |
165 | spin_lock(lock: &ei->cache_lru_lock); |
166 | cache = exfat_cache_merge(inode, new); |
167 | if (cache != NULL) { |
168 | ei->nr_caches--; |
169 | exfat_cache_free(cache: 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(lock: &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(head: &ei->cache_lru)) { |
199 | cache = list_entry(ei->cache_lru.next, |
200 | struct exfat_cache, cache_list); |
201 | list_del_init(entry: &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(lock: &ei->cache_lru_lock); |
216 | __exfat_cache_inval_inode(inode); |
217 | spin_unlock(lock: &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: &cid, EXFAT_EOF_CLUSTER, EXFAT_EOF_CLUSTER); |
265 | |
266 | if (exfat_cache_lookup(inode, fclus: cluster, cid: &cid, cached_fclus: fclus, cached_dclus: 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, loc: *dclus, content: &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: &cid, dclus: *dclus)) |
309 | cache_init(cid: &cid, fclus: *fclus, dclus: *dclus); |
310 | } |
311 | |
312 | exfat_cache_add(inode, new: &cid); |
313 | return 0; |
314 | } |
315 | |