fs/exfat/cache.c

   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 }