Commit | Line | Data |
---|---|---|
c35b6810 NJ |
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 | } |