fs/exfat/cache.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  *  linux/fs/fat/cache.c
0004  *
0005  *  Written 1992,1993 by Werner Almesberger
0006  *
0007  *  Mar 1999. AV. Changed cache, so that it uses the starting cluster instead
0008  *  of inode number.
0009  *  May 1999. AV. Fixed the bogosity with FAT32 (read "FAT28"). Fscking lusers.
0010  *  Copyright (C) 2012-2013 Samsung Electronics Co., Ltd.
0011  */
0012
0013 #include <linux/slab.h>
0014 #include <asm/unaligned.h>
0015 #include <linux/buffer_head.h>
0016
0017 #include "exfat_raw.h"
0018 #include "exfat_fs.h"
0019
0020 #define EXFAT_MAX_CACHE     16
0021
0022 struct exfat_cache {
0023     struct list_head cache_list;
0024     unsigned int nr_contig; /* number of contiguous clusters */
0025     unsigned int fcluster;  /* cluster number in the file. */
0026     unsigned int dcluster;  /* cluster number on disk. */
0027 };
0028
0029 struct exfat_cache_id {
0030     unsigned int id;
0031     unsigned int nr_contig;
0032     unsigned int fcluster;
0033     unsigned int dcluster;
0034 };
0035
0036 static struct kmem_cache *exfat_cachep;
0037
0038 static void exfat_cache_init_once(void *c)
0039 {
0040     struct exfat_cache *cache = (struct exfat_cache *)c;
0041
0042     INIT_LIST_HEAD(&cache->cache_list);
0043 }
0044
0045 int exfat_cache_init(void)
0046 {
0047     exfat_cachep = kmem_cache_create("exfat_cache",
0048                 sizeof(struct exfat_cache),
0049                 0, SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD,
0050                 exfat_cache_init_once);
0051     if (!exfat_cachep)
0052         return -ENOMEM;
0053     return 0;
0054 }
0055
0056 void exfat_cache_shutdown(void)
0057 {
0058     if (!exfat_cachep)
0059         return;
0060     kmem_cache_destroy(exfat_cachep);
0061 }
0062
0063 static inline struct exfat_cache *exfat_cache_alloc(void)
0064 {
0065     return kmem_cache_alloc(exfat_cachep, GFP_NOFS);
0066 }
0067
0068 static inline void exfat_cache_free(struct exfat_cache *cache)
0069 {
0070     WARN_ON(!list_empty(&cache->cache_list));
0071     kmem_cache_free(exfat_cachep, cache);
0072 }
0073
0074 static inline void exfat_cache_update_lru(struct inode *inode,
0075         struct exfat_cache *cache)
0076 {
0077     struct exfat_inode_info *ei = EXFAT_I(inode);
0078
0079     if (ei->cache_lru.next != &cache->cache_list)
0080         list_move(&cache->cache_list, &ei->cache_lru);
0081 }
0082
0083 static unsigned int exfat_cache_lookup(struct inode *inode,
0084         unsigned int fclus, struct exfat_cache_id *cid,
0085         unsigned int *cached_fclus, unsigned int *cached_dclus)
0086 {
0087     struct exfat_inode_info *ei = EXFAT_I(inode);
0088     static struct exfat_cache nohit = { .fcluster = 0, };
0089     struct exfat_cache *hit = &nohit, *p;
0090     unsigned int offset = EXFAT_EOF_CLUSTER;
0091
0092     spin_lock(&ei->cache_lru_lock);
0093     list_for_each_entry(p, &ei->cache_lru, cache_list) {
0094         /* Find the cache of "fclus" or nearest cache. */
0095         if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {
0096             hit = p;
0097             if (hit->fcluster + hit->nr_contig < fclus) {
0098                 offset = hit->nr_contig;
0099             } else {
0100                 offset = fclus - hit->fcluster;
0101                 break;
0102             }
0103         }
0104     }
0105     if (hit != &nohit) {
0106         exfat_cache_update_lru(inode, hit);
0107
0108         cid->id = ei->cache_valid_id;
0109         cid->nr_contig = hit->nr_contig;
0110         cid->fcluster = hit->fcluster;
0111         cid->dcluster = hit->dcluster;
0112         *cached_fclus = cid->fcluster + offset;
0113         *cached_dclus = cid->dcluster + offset;
0114     }
0115     spin_unlock(&ei->cache_lru_lock);
0116
0117     return offset;
0118 }
0119
0120 static struct exfat_cache *exfat_cache_merge(struct inode *inode,
0121         struct exfat_cache_id *new)
0122 {
0123     struct exfat_inode_info *ei = EXFAT_I(inode);
0124     struct exfat_cache *p;
0125
0126     list_for_each_entry(p, &ei->cache_lru, cache_list) {
0127         /* Find the same part as "new" in cluster-chain. */
0128         if (p->fcluster == new->fcluster) {
0129             if (new->nr_contig > p->nr_contig)
0130                 p->nr_contig = new->nr_contig;
0131             return p;
0132         }
0133     }
0134     return NULL;
0135 }
0136
0137 static void exfat_cache_add(struct inode *inode,
0138         struct exfat_cache_id *new)
0139 {
0140     struct exfat_inode_info *ei = EXFAT_I(inode);
0141     struct exfat_cache *cache, *tmp;
0142
0143     if (new->fcluster == EXFAT_EOF_CLUSTER) /* dummy cache */
0144         return;
0145
0146     spin_lock(&ei->cache_lru_lock);
0147     if (new->id != EXFAT_CACHE_VALID &&
0148         new->id != ei->cache_valid_id)
0149         goto unlock;    /* this cache was invalidated */
0150
0151     cache = exfat_cache_merge(inode, new);
0152     if (cache == NULL) {
0153         if (ei->nr_caches < EXFAT_MAX_CACHE) {
0154             ei->nr_caches++;
0155             spin_unlock(&ei->cache_lru_lock);
0156
0157             tmp = exfat_cache_alloc();
0158             if (!tmp) {
0159                 spin_lock(&ei->cache_lru_lock);
0160                 ei->nr_caches--;
0161                 spin_unlock(&ei->cache_lru_lock);
0162                 return;
0163             }
0164
0165             spin_lock(&ei->cache_lru_lock);
0166             cache = exfat_cache_merge(inode, new);
0167             if (cache != NULL) {
0168                 ei->nr_caches--;
0169                 exfat_cache_free(tmp);
0170                 goto out_update_lru;
0171             }
0172             cache = tmp;
0173         } else {
0174             struct list_head *p = ei->cache_lru.prev;
0175
0176             cache = list_entry(p,
0177                     struct exfat_cache, cache_list);
0178         }
0179         cache->fcluster = new->fcluster;
0180         cache->dcluster = new->dcluster;
0181         cache->nr_contig = new->nr_contig;
0182     }
0183 out_update_lru:
0184     exfat_cache_update_lru(inode, cache);
0185 unlock:
0186     spin_unlock(&ei->cache_lru_lock);
0187 }
0188
0189 /*
0190  * Cache invalidation occurs rarely, thus the LRU chain is not updated. It
0191  * fixes itself after a while.
0192  */
0193 static void __exfat_cache_inval_inode(struct inode *inode)
0194 {
0195     struct exfat_inode_info *ei = EXFAT_I(inode);
0196     struct exfat_cache *cache;
0197
0198     while (!list_empty(&ei->cache_lru)) {
0199         cache = list_entry(ei->cache_lru.next,
0200                    struct exfat_cache, cache_list);
0201         list_del_init(&cache->cache_list);
0202         ei->nr_caches--;
0203         exfat_cache_free(cache);
0204     }
0205     /* Update. The copy of caches before this id is discarded. */
0206     ei->cache_valid_id++;
0207     if (ei->cache_valid_id == EXFAT_CACHE_VALID)
0208         ei->cache_valid_id++;
0209 }
0210
0211 void exfat_cache_inval_inode(struct inode *inode)
0212 {
0213     struct exfat_inode_info *ei = EXFAT_I(inode);
0214
0215     spin_lock(&ei->cache_lru_lock);
0216     __exfat_cache_inval_inode(inode);
0217     spin_unlock(&ei->cache_lru_lock);
0218 }
0219
0220 static inline int cache_contiguous(struct exfat_cache_id *cid,
0221         unsigned int dclus)
0222 {
0223     cid->nr_contig++;
0224     return cid->dcluster + cid->nr_contig == dclus;
0225 }
0226
0227 static inline void cache_init(struct exfat_cache_id *cid,
0228         unsigned int fclus, unsigned int dclus)
0229 {
0230     cid->id = EXFAT_CACHE_VALID;
0231     cid->fcluster = fclus;
0232     cid->dcluster = dclus;
0233     cid->nr_contig = 0;
0234 }
0235
0236 int exfat_get_cluster(struct inode *inode, unsigned int cluster,
0237         unsigned int *fclus, unsigned int *dclus,
0238         unsigned int *last_dclus, int allow_eof)
0239 {
0240     struct super_block *sb = inode->i_sb;
0241     struct exfat_sb_info *sbi = EXFAT_SB(sb);
0242     unsigned int limit = sbi->num_clusters;
0243     struct exfat_inode_info *ei = EXFAT_I(inode);
0244     struct exfat_cache_id cid;
0245     unsigned int content;
0246
0247     if (ei->start_clu == EXFAT_FREE_CLUSTER) {
0248         exfat_fs_error(sb,
0249             "invalid access to exfat cache (entry 0x%08x)",
0250             ei->start_clu);
0251         return -EIO;
0252     }
0253
0254     *fclus = 0;
0255     *dclus = ei->start_clu;
0256     *last_dclus = *dclus;
0257
0258     /*
0259      * Don`t use exfat_cache if zero offset or non-cluster allocation
0260      */
0261     if (cluster == 0 || *dclus == EXFAT_EOF_CLUSTER)
0262         return 0;
0263
0264     cache_init(&cid, EXFAT_EOF_CLUSTER, EXFAT_EOF_CLUSTER);
0265
0266     if (exfat_cache_lookup(inode, cluster, &cid, fclus, dclus) ==
0267             EXFAT_EOF_CLUSTER) {
0268         /*
0269          * dummy, always not contiguous
0270          * This is reinitialized by cache_init(), later.
0271          */
0272         WARN_ON(cid.id != EXFAT_CACHE_VALID ||
0273             cid.fcluster != EXFAT_EOF_CLUSTER ||
0274             cid.dcluster != EXFAT_EOF_CLUSTER ||
0275             cid.nr_contig != 0);
0276     }
0277
0278     if (*fclus == cluster)
0279         return 0;
0280
0281     while (*fclus < cluster) {
0282         /* prevent the infinite loop of cluster chain */
0283         if (*fclus > limit) {
0284             exfat_fs_error(sb,
0285                 "detected the cluster chain loop (i_pos %u)",
0286                 (*fclus));
0287             return -EIO;
0288         }
0289
0290         if (exfat_ent_get(sb, *dclus, &content))
0291             return -EIO;
0292
0293         *last_dclus = *dclus;
0294         *dclus = content;
0295         (*fclus)++;
0296
0297         if (content == EXFAT_EOF_CLUSTER) {
0298             if (!allow_eof) {
0299                 exfat_fs_error(sb,
0300                        "invalid cluster chain (i_pos %u, last_clus 0x%08x is EOF)",
0301                        *fclus, (*last_dclus));
0302                 return -EIO;
0303             }
0304
0305             break;
0306         }
0307
0308         if (!cache_contiguous(&cid, *dclus))
0309             cache_init(&cid, *fclus, *dclus);
0310     }
0311
0312     exfat_cache_add(inode, &cid);
0313     return 0;
0314 }