cache.c 7.4 KB

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