cache.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386
  1. // SPDX-License-Identifier: GPL-2.0
  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. */
  11. #include <linux/slab.h>
  12. #include "fat.h"
  13. /* this must be > 0. */
  14. #define FAT_MAX_CACHE 8
  15. struct fat_cache {
  16. struct list_head cache_list;
  17. int nr_contig; /* number of contiguous clusters */
  18. int fcluster; /* cluster number in the file. */
  19. int dcluster; /* cluster number on disk. */
  20. };
  21. struct fat_cache_id {
  22. unsigned int id;
  23. int nr_contig;
  24. int fcluster;
  25. int dcluster;
  26. };
  27. static inline int fat_max_cache(struct inode *inode)
  28. {
  29. return FAT_MAX_CACHE;
  30. }
  31. static struct kmem_cache *fat_cache_cachep;
  32. static void init_once(void *foo)
  33. {
  34. struct fat_cache *cache = (struct fat_cache *)foo;
  35. INIT_LIST_HEAD(&cache->cache_list);
  36. }
  37. int __init fat_cache_init(void)
  38. {
  39. fat_cache_cachep = kmem_cache_create("fat_cache",
  40. sizeof(struct fat_cache),
  41. 0, SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD,
  42. init_once);
  43. if (fat_cache_cachep == NULL)
  44. return -ENOMEM;
  45. return 0;
  46. }
  47. void fat_cache_destroy(void)
  48. {
  49. kmem_cache_destroy(fat_cache_cachep);
  50. }
  51. static inline struct fat_cache *fat_cache_alloc(struct inode *inode)
  52. {
  53. return kmem_cache_alloc(fat_cache_cachep, GFP_NOFS);
  54. }
  55. static inline void fat_cache_free(struct fat_cache *cache)
  56. {
  57. BUG_ON(!list_empty(&cache->cache_list));
  58. kmem_cache_free(fat_cache_cachep, cache);
  59. }
  60. static inline void fat_cache_update_lru(struct inode *inode,
  61. struct fat_cache *cache)
  62. {
  63. if (MSDOS_I(inode)->cache_lru.next != &cache->cache_list)
  64. list_move(&cache->cache_list, &MSDOS_I(inode)->cache_lru);
  65. }
  66. static int fat_cache_lookup(struct inode *inode, int fclus,
  67. struct fat_cache_id *cid,
  68. int *cached_fclus, int *cached_dclus)
  69. {
  70. static struct fat_cache nohit = { .fcluster = 0, };
  71. struct fat_cache *hit = &nohit, *p;
  72. int offset = -1;
  73. spin_lock(&MSDOS_I(inode)->cache_lru_lock);
  74. list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
  75. /* Find the cache of "fclus" or nearest cache. */
  76. if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {
  77. hit = p;
  78. if ((hit->fcluster + hit->nr_contig) < fclus) {
  79. offset = hit->nr_contig;
  80. } else {
  81. offset = fclus - hit->fcluster;
  82. break;
  83. }
  84. }
  85. }
  86. if (hit != &nohit) {
  87. fat_cache_update_lru(inode, hit);
  88. cid->id = MSDOS_I(inode)->cache_valid_id;
  89. cid->nr_contig = hit->nr_contig;
  90. cid->fcluster = hit->fcluster;
  91. cid->dcluster = hit->dcluster;
  92. *cached_fclus = cid->fcluster + offset;
  93. *cached_dclus = cid->dcluster + offset;
  94. }
  95. spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
  96. return offset;
  97. }
  98. static struct fat_cache *fat_cache_merge(struct inode *inode,
  99. struct fat_cache_id *new)
  100. {
  101. struct fat_cache *p;
  102. list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {
  103. /* Find the same part as "new" in cluster-chain. */
  104. if (p->fcluster == new->fcluster) {
  105. BUG_ON(p->dcluster != new->dcluster);
  106. if (new->nr_contig > p->nr_contig)
  107. p->nr_contig = new->nr_contig;
  108. return p;
  109. }
  110. }
  111. return NULL;
  112. }
  113. static void fat_cache_add(struct inode *inode, struct fat_cache_id *new)
  114. {
  115. struct fat_cache *cache, *tmp;
  116. if (new->fcluster == -1) /* dummy cache */
  117. return;
  118. spin_lock(&MSDOS_I(inode)->cache_lru_lock);
  119. if (new->id != FAT_CACHE_VALID &&
  120. new->id != MSDOS_I(inode)->cache_valid_id)
  121. goto out; /* this cache was invalidated */
  122. cache = fat_cache_merge(inode, new);
  123. if (cache == NULL) {
  124. if (MSDOS_I(inode)->nr_caches < fat_max_cache(inode)) {
  125. MSDOS_I(inode)->nr_caches++;
  126. spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
  127. tmp = fat_cache_alloc(inode);
  128. if (!tmp) {
  129. spin_lock(&MSDOS_I(inode)->cache_lru_lock);
  130. MSDOS_I(inode)->nr_caches--;
  131. spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
  132. return;
  133. }
  134. spin_lock(&MSDOS_I(inode)->cache_lru_lock);
  135. cache = fat_cache_merge(inode, new);
  136. if (cache != NULL) {
  137. MSDOS_I(inode)->nr_caches--;
  138. fat_cache_free(tmp);
  139. goto out_update_lru;
  140. }
  141. cache = tmp;
  142. } else {
  143. struct list_head *p = MSDOS_I(inode)->cache_lru.prev;
  144. cache = list_entry(p, struct fat_cache, cache_list);
  145. }
  146. cache->fcluster = new->fcluster;
  147. cache->dcluster = new->dcluster;
  148. cache->nr_contig = new->nr_contig;
  149. }
  150. out_update_lru:
  151. fat_cache_update_lru(inode, cache);
  152. out:
  153. spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
  154. }
  155. /*
  156. * Cache invalidation occurs rarely, thus the LRU chain is not updated. It
  157. * fixes itself after a while.
  158. */
  159. static void __fat_cache_inval_inode(struct inode *inode)
  160. {
  161. struct msdos_inode_info *i = MSDOS_I(inode);
  162. struct fat_cache *cache;
  163. while (!list_empty(&i->cache_lru)) {
  164. cache = list_entry(i->cache_lru.next,
  165. struct fat_cache, cache_list);
  166. list_del_init(&cache->cache_list);
  167. i->nr_caches--;
  168. fat_cache_free(cache);
  169. }
  170. /* Update. The copy of caches before this id is discarded. */
  171. i->cache_valid_id++;
  172. if (i->cache_valid_id == FAT_CACHE_VALID)
  173. i->cache_valid_id++;
  174. }
  175. void fat_cache_inval_inode(struct inode *inode)
  176. {
  177. spin_lock(&MSDOS_I(inode)->cache_lru_lock);
  178. __fat_cache_inval_inode(inode);
  179. spin_unlock(&MSDOS_I(inode)->cache_lru_lock);
  180. }
  181. static inline int cache_contiguous(struct fat_cache_id *cid, int dclus)
  182. {
  183. cid->nr_contig++;
  184. return ((cid->dcluster + cid->nr_contig) == dclus);
  185. }
  186. static inline void cache_init(struct fat_cache_id *cid, int fclus, int dclus)
  187. {
  188. cid->id = FAT_CACHE_VALID;
  189. cid->fcluster = fclus;
  190. cid->dcluster = dclus;
  191. cid->nr_contig = 0;
  192. }
  193. int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus)
  194. {
  195. struct super_block *sb = inode->i_sb;
  196. struct msdos_sb_info *sbi = MSDOS_SB(sb);
  197. const int limit = sb->s_maxbytes >> sbi->cluster_bits;
  198. struct fat_entry fatent;
  199. struct fat_cache_id cid;
  200. int nr;
  201. BUG_ON(MSDOS_I(inode)->i_start == 0);
  202. *fclus = 0;
  203. *dclus = MSDOS_I(inode)->i_start;
  204. if (!fat_valid_entry(sbi, *dclus)) {
  205. fat_fs_error_ratelimit(sb,
  206. "%s: invalid start cluster (i_pos %lld, start %08x)",
  207. __func__, MSDOS_I(inode)->i_pos, *dclus);
  208. return -EIO;
  209. }
  210. if (cluster == 0)
  211. return 0;
  212. if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) {
  213. /*
  214. * dummy, always not contiguous
  215. * This is reinitialized by cache_init(), later.
  216. */
  217. cache_init(&cid, -1, -1);
  218. }
  219. fatent_init(&fatent);
  220. while (*fclus < cluster) {
  221. /* prevent the infinite loop of cluster chain */
  222. if (*fclus > limit) {
  223. fat_fs_error_ratelimit(sb,
  224. "%s: detected the cluster chain loop (i_pos %lld)",
  225. __func__, MSDOS_I(inode)->i_pos);
  226. nr = -EIO;
  227. goto out;
  228. }
  229. nr = fat_ent_read(inode, &fatent, *dclus);
  230. if (nr < 0)
  231. goto out;
  232. else if (nr == FAT_ENT_FREE) {
  233. fat_fs_error_ratelimit(sb,
  234. "%s: invalid cluster chain (i_pos %lld)",
  235. __func__, MSDOS_I(inode)->i_pos);
  236. nr = -EIO;
  237. goto out;
  238. } else if (nr == FAT_ENT_EOF) {
  239. fat_cache_add(inode, &cid);
  240. goto out;
  241. }
  242. (*fclus)++;
  243. *dclus = nr;
  244. if (!cache_contiguous(&cid, *dclus))
  245. cache_init(&cid, *fclus, *dclus);
  246. }
  247. nr = 0;
  248. fat_cache_add(inode, &cid);
  249. out:
  250. fatent_brelse(&fatent);
  251. return nr;
  252. }
  253. static int fat_bmap_cluster(struct inode *inode, int cluster)
  254. {
  255. struct super_block *sb = inode->i_sb;
  256. int ret, fclus, dclus;
  257. if (MSDOS_I(inode)->i_start == 0)
  258. return 0;
  259. ret = fat_get_cluster(inode, cluster, &fclus, &dclus);
  260. if (ret < 0)
  261. return ret;
  262. else if (ret == FAT_ENT_EOF) {
  263. fat_fs_error(sb, "%s: request beyond EOF (i_pos %lld)",
  264. __func__, MSDOS_I(inode)->i_pos);
  265. return -EIO;
  266. }
  267. return dclus;
  268. }
  269. int fat_get_mapped_cluster(struct inode *inode, sector_t sector,
  270. sector_t last_block,
  271. unsigned long *mapped_blocks, sector_t *bmap)
  272. {
  273. struct super_block *sb = inode->i_sb;
  274. struct msdos_sb_info *sbi = MSDOS_SB(sb);
  275. int cluster, offset;
  276. cluster = sector >> (sbi->cluster_bits - sb->s_blocksize_bits);
  277. offset = sector & (sbi->sec_per_clus - 1);
  278. cluster = fat_bmap_cluster(inode, cluster);
  279. if (cluster < 0)
  280. return cluster;
  281. else if (cluster) {
  282. *bmap = fat_clus_to_blknr(sbi, cluster) + offset;
  283. *mapped_blocks = sbi->sec_per_clus - offset;
  284. if (*mapped_blocks > last_block - sector)
  285. *mapped_blocks = last_block - sector;
  286. }
  287. return 0;
  288. }
  289. static int is_exceed_eof(struct inode *inode, sector_t sector,
  290. sector_t *last_block, int create)
  291. {
  292. struct super_block *sb = inode->i_sb;
  293. const unsigned long blocksize = sb->s_blocksize;
  294. const unsigned char blocksize_bits = sb->s_blocksize_bits;
  295. *last_block = (i_size_read(inode) + (blocksize - 1)) >> blocksize_bits;
  296. if (sector >= *last_block) {
  297. if (!create)
  298. return 1;
  299. /*
  300. * ->mmu_private can access on only allocation path.
  301. * (caller must hold ->i_mutex)
  302. */
  303. *last_block = (MSDOS_I(inode)->mmu_private + (blocksize - 1))
  304. >> blocksize_bits;
  305. if (sector >= *last_block)
  306. return 1;
  307. }
  308. return 0;
  309. }
  310. int fat_bmap(struct inode *inode, sector_t sector, sector_t *phys,
  311. unsigned long *mapped_blocks, int create, bool from_bmap)
  312. {
  313. struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
  314. sector_t last_block;
  315. *phys = 0;
  316. *mapped_blocks = 0;
  317. if (!is_fat32(sbi) && (inode->i_ino == MSDOS_ROOT_INO)) {
  318. if (sector < (sbi->dir_entries >> sbi->dir_per_block_bits)) {
  319. *phys = sector + sbi->dir_start;
  320. *mapped_blocks = 1;
  321. }
  322. return 0;
  323. }
  324. if (!from_bmap) {
  325. if (is_exceed_eof(inode, sector, &last_block, create))
  326. return 0;
  327. } else {
  328. last_block = inode->i_blocks >>
  329. (inode->i_sb->s_blocksize_bits - 9);
  330. if (sector >= last_block)
  331. return 0;
  332. }
  333. return fat_get_mapped_cluster(inode, sector, last_block, mapped_blocks,
  334. phys);
  335. }